指紋細節大拓撲結構匹配算法的製作方法

2023-10-10 13:21:49

專利名稱：指紋細節大拓撲結構匹配算法的製作方法
技術領域：
本發明是一種在綜合目前指紋識別領域中指紋細節匹配算法的基礎上提出的全新指紋細節快速匹配算法，屬於模式識別領域。
隨著社會的信息化日趨完善，方便可靠的個人身份鑑定手段的要求日益增加，指紋識別作為一種個人身份鑑別手段已經有幾百年的歷史了，和其他的幾種個人身份鑑別方式如虹膜，臉相，掌紋，聲音相比較，指紋有著方便，可靠、成本低廉等優點，因此指紋識別在國內外的學術界和工業界引起廣泛的關注。特別是近幾年來隨著計算機技術的發展，自動指紋識別系統已經達到實用的階段，在很多場合已經投入使用，比如指紋考勤，計算機安全管理，銀行提款，公安偵破，指紋門禁系統等等。自動指紋識別系統的核心就是指紋的比對算法。目前大多數指紋識別系統比對算法採用細節比對方法。從總體講，指紋細節比對算法主要可以分為兩大類有中心比對算法和無中心比對算法。無中心比對算法是藉助細節的某些冗餘特徵輔助匹配，匹配過程中不需要中心點。它的優點是對採集的指紋圖像的定位要求不高，但缺點是比對的效率低下，而且模板中常常由於含有大量的冗餘信息而導致模板過大。不適應對時間要求較高的場合。有中心比對算法是藉助中心點輔助定位指紋圖像並進行匹配。它的優點是比對的速度非常快，模板中冗餘信息少，但缺點是對定位奇異點的精度要求較高，如果奇異點的定位精度不夠準確的話，常常導致比對失敗。可對比的技術文獻主要有以下14篇[1]Anil Jain，Lin Hong and Ruud Boole On-Line Fingerprint Verification，IEEETrans.PAMI，Vo1.19，NO.4，1997，302-314[2]Nalini K.Ratha，Vinayaka D.Pandit，Robust Fingerprint Authentication UsingLocal Structure Similarith，IEEE，2000[3]Andres Almansa，Laurent Cohen，Fingerprint image matching by minimizationof a thin-plate energy using a two-step algorithm with auxiliary vairables，IEEE，2000[4]Zsolt Miklos Kovacs-Vajna，A Fingerprint Verification system Based onTriangular Matching and Dynamic Time Warping，IEEE Trans.PAMI，Vol.22，NO.11，2000，pp1266-1276.[5]A.J.Willis，L..Myers，A Cost-effective fingerprint recognition system for usewith low-quality prints and damaged fingerprint.Pattem Recognition，Vol.34，2001，pp255-270[6]V.s.Srinivasan，N.N.Murthy，Detection of Singular Point in FingerprintImages，Pattem Recognition，Vol.25，NO.2，1992，pp 139-153.[7]Weiwei Zhang，Singular Point Detection in fingerprint image，Accept byACCV2002[8]Asker M.Bazen，Sabih H.Gerez，Extraction of Singular Points fromDirectional Fields of Fingerprints，Annual CTIT Workshop，February 2001，Enschede，Netherlands.[9]Shih-Hsu Chang，Fang-Hsuan Cheng，Fast Algorithm for Point PatternMatchingInvariant to Translations，Rotations and Scale Changes，PatternRecognition，VOL.30，NO.2，1997，pp311-320.[10]D.K.Isenor，S.G.Zaky，Fingerprint Identification Using Graph matching，Pattern Recognition，Vol.19，NO.2，1986，pp113-122[11]Andrew K.Hrechak，James A.Mchugh，Automated Fingerprint RecognitionUsing Structural Matching，Pattern Recognition，Vol.23，NO.8，1990，pp839-904.[12]Z.Chen，CH.Kou，A Toplogy-Based Matching Algorithm for FingerprintAuthentication，IEEE 1991.[13]A.Wahab，Novel Approach to Automated fingerprint Recongnition，IEEProceedings，1998[14]Kou Chin Fan，Cheng W.Liu and Yuan Kai Wang，A randomized approachwith geometric constraints to fingerprint verification，Pattern Recognition，Vol.33，2000，1793-1830.
本發明的目的是在綜合目前大多數指紋匹配算法有點的基礎上提出了一種全新的快速、可靠的指紋比對方法。本發明首先通過多解析度的方向圖快速準確的定位指紋圖像的奇異點，然後對要比對的指紋圖像的細節特徵和奇異點建立大拓撲結構，通過對比兩幅指紋圖像的大拓撲結構，本發明可以快速準確的做出正確判斷。它既克服了無中心匹配算法效率低的缺點，又克服了單純以奇異點作為定為基準從而對奇異點的檢測精度要求非常高的缺點，同時，該方法大大的減小了模板中的冗餘信息，從而大大減小了模板的容量。因此，該方法是一種安全可靠、高效的指紋比對方法。可以廣泛應用於目前絕大多數自動指紋識別系統中。本發明的技術要點在於1多解析度的指紋圖像中心點檢測首先將指紋圖像分成8*8pixel的塊，並求出每塊的方向。Jx(x)Jx(x)=(x,y)=(x,y)x(x,y)y]]>M=Asin(G)=Asin(A(Jyx-Jxy)))]]>利用上述公式求出指紋圖像的中心點，其中M的極值點即指紋圖像的中心點。上述方式之能夠達到8*8的精度，為了進一步的提高算法的精度，再求出的極值點周圍選區一個大小為100*100pixel的區域，將該區域分為4*4或2*2的小塊，並求出每塊的方向，然後重新利用上述公式，再求一次中心點。該方法的主要特點是避免了逐點計算指紋圖像的方向圖，大大的提高的效率，同時能夠獲得較高的檢測精度。中心點方向的定位方法為首先我們將O~PI離散化為16個方向然後分別在16個方向上以中心點為圓心作(參見附

圖1)矩形框，並求該矩形框的內的指紋圖像的方向直方圖。設求得的方向直方圖為Hμ(j)(j，μ＝0~15)其中，μ表示在16個方向上作矩形求得的結果，j表示在每個方向上作矩形框求得的方向直方圖的分量。
其次，令Oμ＝∑Wμ(j)*H(j)其中Wμ(j)為權向量，它的選取方法如下Wμ(μ)＞＞Wμ(j)，對於j不等於μ中心點的方向為Orient＝argmax(Oμ)2基於中心點的大拓撲結構匹配算法1.1建立指紋圖像的大拓撲結構基於中心的大拓撲結構匹配算法的關鍵思想就是以中心點為核心，建立細節點和中心點的拓撲結構圖。通過對比兩幅指紋的拓撲結構，從而實現指紋之間的匹配。建立基於中心點的大拓撲結構所需要計算的特徵為(參見附圖2)●細節點的方向與中心點方向之間的夾角α●細節點的方向與中心點和細節點之間連線的夾角β●細節點和中心點之間的紋線數目D●細節點和中心點之間的拓撲角γ2.2初始對應點的選取2.2.1初始對應點的搜索由於噪聲、圖像處理步驟的影響，往往造成引入偽細節點或丟失真細節點，這將嚴重的影響按照拓撲關係尋找初始對應點的效果。為了減小這些影響，本發明採用了動態搜索初始對應點的方法。總的來講，動態搜索的方法對尋找初始對應點非常有利，它總能找到正確初始對應點。具體搜索方法如下用T代表存儲模板，L代表輸入模板，則搜索的步驟如下1.以中心點為圓心，沿中心點的方向的一個給定角度範圍，在T、L中確定一個搜索範圍。
2.計算T的搜索範圍中所有相鄰的細節所組成的拓撲關係，包括與中心點的紋線間隔，夾角，用T1表示3.從T1中取出一個相鄰細節點的拓撲關係，在L的搜索範圍內尋找與之具有相似拓撲關係的細節點。
4.如果找到則記錄該所有對應細節點，否則返回3。如果T1尋找完畢，返回。
通過上述的搜索步驟，往往會得到很多對對應點，這些對應點對中包含了很多真正的對應點，也可能包含了一些虛假的對應點，如果所有的對應點匹配一遍，然後選用匹配值中最好結果返回，就會導致會算法效率較低和由於虛假對應點的存在可能會引入誤匹配等情況。針對這種情況，本發明採用了對已經尋找到的對應點進行聚類分析。選取其中可能性最大的一些對應點進行匹配，而不是對全部進行匹配。
2.2.2初始對應點的聚類分析設S＝{s1，s2，...，sn}R＝{r1，r2，...，rn}其中，S表示來自T的對應點，R表示來自L的對應點。如果不考慮非線性變形的話，對於真正的對應點，一定有如下關係R＝A*S+b其中，A和b為仿射矩陣。
如果考慮到局部變形的一致性，那麼在一個局部區域之內的對應點之間的仿射矩陣應該一致。根據這個假設，可以對已求得的對應點進行聚類分析。把仿射矩陣一致的對應點聚類。通過聚類，局部的對應點就轉化為幾個聚類，根據聚類中包含的元素數目而給與這些聚類相應的置信度，選用置信度最高的幾對對應點進行匹配，通常，選取3個聚類中心作為對應點進行匹配就足夠了，對於置信度較低的對應點則拋棄。2.3全局匹配2.3.1全局匹配方法在大拓撲結構的匹配算法中，主要選用了3個匹配參數，兩個夾角和一個紋線數目。對於這三個參數而言，距離中心點越近，他們受中心點誤差的影響就越大，而對於離中心點較遠的細節點，這三個參數受中心點誤差的影響較小。因此，假如按照一個統一的標準來進行匹配的話，往往造成大量的中心點附近的細節點無法匹配成功。針對這種情況，本發明提出對離中心點近和離中心點遠的細節點分開匹配，分別採用不同的匹配準則。下面，就介紹一下這種方法。
既然要分別匹配，就要將細節點分開，選用了距離作為一個劃分的標準。設細節點離中心點的距離為r，通過r＞R (1)r＜＝R(2)將細節點劃分為兩部分。對於(1)，仍任採用以前的三個特徵進行匹配，而對(2)，選用如下的特徵1.距離，細節點和中心點之間的距離2.細節點和初始對應點之間方向角的夾角3.細節點和初始對應點與中心點連線的角角通過選用這三個參數，部分的消除了由於中心點的位置誤差對夾角的影響，同時也消除了在中心區域紋線數目計算不準確的影響。對於絕大多數的中心區域的細節點，使用該方法都可以較好的匹配。
為了避免位置相差180度的細節點的誤匹配，例如左下角的細節點和右上角的細節點發生誤匹配，本方法加入一個相對比較寬鬆的位置約束。
約束的具體形式如下R＝A′*S+b′即匹配的細節點應該符合對應點之間的仿射變換。其中，A′和b′比A和b寬鬆。2.3.2匹配判決條件在通常的匹配算法中，大多僅僅根據匹配的細節點的數目來判斷是否匹配，然而很多發生誤匹配的指紋其實無論在形狀還是細節點本身，都有很大的差別，因此如果加入一種有效的判決條件約束的話，就可以大大的降低誤匹配發生機率。本方法中引入了全局距離和誤差殘差判決條件，大大的降低了誤匹配的機率。
誤差殘差的定義為設已知兩幅指紋的仿射矩陣分別為A和b，(事實上，有了對應點，就有了仿射矩陣)S*＝A*S+b其中S*為經過仿射變換的已匹配細節向量。那麼，E=1n(S*-R);]]>設Ts和Ls分別為存儲模板和輸入模板的中心點，它們之間也應該符合已知的仿射矩陣。
設L*s=A*Ls+b]]>令E=Ts-L*s]]>如果在理想情況下，E-E′＝0通常，由於噪聲和形變的影響，這個值並不為零，令η＝E-E′定義η為誤差殘差則，這個值應該小於一個門限。
η＜Tη為了衡量誤差的分散程度，本方法引入匹配細節點之間的標準差σ；對於誤差的標準差，也有一個判決門限。
σ＜Tσ
通過這些約束就可以達到非常精確的判決結果。
圖1是方向直方圖選取矩形區域示意2基於中心的大拓撲結構示意圖3基於大拓撲結構的指紋匹配算法原理示意圖。
圖4～圖6匹配結果示意圖
權利要求
1.一種基於中心點的指紋大拓撲結構匹配算法，其特點在於結合有中心匹配算法和無中心匹配算法的優點，能夠快速可靠的對指紋圖像進行比對。
2.根據權利要求1所述的匹配過程，建立大拓撲結構，利用大拓撲結構進行匹配，並根據匹配的結果進行基於匹配誤差和誤差殘差條件進行判決。
3.根根據權利要求1所述的多解析度的指紋圖像中心點檢測算法。
全文摘要
一種在綜合目前指紋識別領域中指紋細節匹配算法的基礎上提出的全新指紋細節快速匹配算法，屬於模式識別領域。本方法通過建立基於中心點的大拓撲結構，對兩幅指紋圖像進行快速的匹配，他不但克服了無中心匹配算法的效率低，模板容量大等問題，同時也避免了簡單採用中心點作為定為基準而對中心點的檢測精度要求過高的問題，本方法是一種快速，安全可靠的指紋細節比對算法。本方法可廣泛應用於目前絕大多數自動指紋識別系統中。
文檔編號G06K9/00GK1447272SQ0211625
公開日2003年10月8日 申請日期2002年3月26日 優先權日2002年3月26日
發明者王陽生, 張偉偉 申請人:北京中科模識科技有限公司, 中國科學院自動化研究所