基于結(jié)構(gòu)特征的指紋細(xì)節(jié)點(diǎn)匹配算法

1、基于結(jié)構(gòu)特征的指紋細(xì)節(jié)點(diǎn)匹配算法1呂玉華1，李麗娟1，劉靈麗21. 湖南大學(xué)計算機(jī)與通信學(xué)院，長沙（410082）2. 湘南學(xué)院計算機(jī)系，湖南郴州（423000）E-mail ：摘 要： 提出了一種新的指紋特征匹配方法。首先定位指紋圖像的中心點(diǎn)，然后提取細(xì)節(jié)點(diǎn)，并計算其與中心點(diǎn)的角度差以及到中心點(diǎn)所穿越的脊線數(shù)，將此作為特征向量與細(xì)節(jié)點(diǎn)特征結(jié)合, 最后根據(jù)穿越的脊線數(shù)和角度差對細(xì)節(jié)點(diǎn)進(jìn)行匹配。實(shí)驗(yàn)表明該算法運(yùn)行速度較快，有較強(qiáng)的抗噪聲與圖像形變的能力，能有效地提高指紋圖像匹配的準(zhǔn)確程度。 關(guān)鍵詞： 中心點(diǎn)；細(xì)節(jié)點(diǎn)；穿越的脊線數(shù)；結(jié)構(gòu)特征；匹配中圖分類號：TP309；TP391.411引言近年來

2、，因?yàn)橹讣y的唯一性、不變性和獲取的方便性，指紋識別技術(shù)在安全領(lǐng)域得到廣泛應(yīng)用。作為指紋識別技術(shù)的關(guān)鍵環(huán)節(jié)，特征提取和匹配算法的優(yōu)化能有效的提高指紋識別系統(tǒng)的性能。傳統(tǒng)的細(xì)節(jié)點(diǎn)匹配算法是提取出待識別指紋紋線的端點(diǎn)與分叉點(diǎn)的信息，包括位置坐標(biāo)和方向，與模板指紋的這些信息進(jìn)行比對，從而轉(zhuǎn)化為兩個點(diǎn)的集合的匹配。一般認(rèn)為，只要比對出13個特征點(diǎn)重合，就可以確認(rèn)這兩枚指紋是同一個指紋。這種方法在進(jìn)行匹配操作時非常耗時，需要對兩組特征點(diǎn)進(jìn)行排列組合，大大增加了運(yùn)算時間；另外，指壓、平移和旋轉(zhuǎn)都會造成指紋的彈性形變，引起細(xì)節(jié)點(diǎn)坐標(biāo)和方向的變化，造成匹配結(jié)果的不準(zhǔn)確，所以人們引入了指紋的其它特征如全局特征信息

3、（中心點(diǎn)、三角點(diǎn)等）或者紋線特征（紋線流向、紋數(shù)）等降低錯誤匹配的概率。例如引入指紋中心點(diǎn)與各細(xì)節(jié)點(diǎn)之間的相對距離和相對角度差來實(shí)現(xiàn)兩組特征數(shù)據(jù)的匹配，這種方法對小范圍內(nèi)的圖像形變有效，但是在形變比較嚴(yán)重的情況下，中心點(diǎn)和細(xì)節(jié)點(diǎn)的相對距離和角度差變化較大，會影響特征的匹配準(zhǔn)確度。而采用在特征信息中引入指紋分叉點(diǎn)間連線所穿越的脊線個數(shù)的方法，對虛假細(xì)節(jié)點(diǎn)和遺漏真實(shí)細(xì)節(jié)點(diǎn)比較敏感, 如果這個結(jié)構(gòu)包含了不正確的分叉點(diǎn)信息，就會因?yàn)榉植纥c(diǎn)間的聯(lián)合結(jié)構(gòu)累積誤差，從而影響匹配結(jié)果。本文在以上兩種方法的基礎(chǔ)上提出了一種基于細(xì)節(jié)點(diǎn)和中心點(diǎn)的連線所穿越的脊線數(shù)與角度差相結(jié)合的方法進(jìn)行匹配。比距離、角度差更具有魯

4、棒性，存在少量虛假細(xì)節(jié)點(diǎn)或遺漏真實(shí)細(xì)節(jié)點(diǎn)也不會因?yàn)檎`差的放大而影響匹配結(jié)果，從而減輕了對細(xì)節(jié)點(diǎn)的依賴程度。這種特征信息在一定程度上反映了特征點(diǎn)間的結(jié)構(gòu)特性，在指紋圖像沒有被分割、損壞的情況下，任何程度的變形都不會改變這一特性，所以對提高指紋匹配的準(zhǔn)確度很有幫助。該方法的具體步驟如下：（1）根據(jù)方向圖定位中心點(diǎn)；（2）提取包含結(jié)構(gòu)特征的細(xì)節(jié)點(diǎn)信息。（3）根據(jù)特征信息進(jìn)行匹配提取特征算法是在細(xì)化的二值圖像3上進(jìn)行的。 本課題得到湖南省自然科學(xué)基金（基于點(diǎn)方向的指紋特征提取研究），湖南省教育廳項目（06C790）的資助。- 1 - 12 定位中心點(diǎn)中心點(diǎn)對應(yīng)脊線中曲率最大處，由圖像的幾何特征可知：曲

5、率越大的地方，該點(diǎn)附近一定范圍內(nèi)其它點(diǎn)的方向與該點(diǎn)方向的差異值越大，差異值最大的地方就是中心點(diǎn)，具體的計算過程如下：（1）在已計算的方向圖中，將指紋的中心點(diǎn)初始化為圖像的中心點(diǎn)；（2）以圖像中心點(diǎn)為中心，W/2*H/2（W ，H 分別為指紋圖像的寬和高）范圍內(nèi)對每一點(diǎn)pixel (i c , j c 按下式計算：VS (i c , j c =(i , j R |sin(V (i , j V (i c , j c | （1）其中，V (i c , j c 是像素點(diǎn)pixel (i c , j c 的點(diǎn)方向，V (i , j 是區(qū)域R 內(nèi)像素點(diǎn)pixel (i , j 的點(diǎn)方向，R 是以點(diǎn)pixe

6、l (i c , j c 為中心，半徑為a 的圓形區(qū)域，文中a 的取值為20。VS 值越大，說明該點(diǎn)附近的曲率越大，因而求出VS 的最大值，對應(yīng)的點(diǎn)pixel (i c , j c 便是所求的中心點(diǎn)；（3）計算出A 中的最小值Min1，再求出次最小值Min2，如果Min1Min2，表明該指紋圖像為雙螺旋圖像，則中心點(diǎn)定位于Min1和Min2所在位置的中點(diǎn)，否則取Min1對應(yīng)的點(diǎn)為所求的中心點(diǎn)。3 提取特征量這里所要提取的特征向量結(jié)合了指紋圖像的結(jié)構(gòu)特征，包括細(xì)節(jié)點(diǎn)的位置坐標(biāo)，方向，細(xì)節(jié)點(diǎn)類型，細(xì)節(jié)點(diǎn)與中心點(diǎn)的角度差，細(xì)節(jié)點(diǎn)到中心點(diǎn)連線所穿越的脊線數(shù)。3.1 提取細(xì)節(jié)點(diǎn)對細(xì)化二值圖像，通過一個3

7、×3的模板來提取端點(diǎn)和分叉點(diǎn)。如圖1所示：N 是待檢查的點(diǎn)，P1，P2，. ，P8 是它的8個鄰點(diǎn)，沿順時針方向排列，R(1，R(2，. ，R(8是點(diǎn)P1，P2，. ，P8 的灰度值。點(diǎn)N的交叉數(shù)定義為： 18C N =R (k +1 R (k , 2k =1R (9=R (1 （2） 圖1. N點(diǎn)的8鄰域圖如C N =1，點(diǎn)N 為脊線端點(diǎn)，如C N =3，點(diǎn)N 為脊線分叉點(diǎn)。提取細(xì)節(jié)點(diǎn)時一般會出大量的偽細(xì)節(jié)點(diǎn)，對于指紋識別來說，這些都是不可靠的信息，因此要濾除這些偽細(xì)節(jié)點(diǎn)2。記錄細(xì)節(jié)點(diǎn)的類型，坐標(biāo)，方向，并計算其與中心點(diǎn)的角度差。3.2 求取穿越脊線數(shù)用Ridge_count表示細(xì)

8、節(jié)點(diǎn)與中心點(diǎn)連線所穿越的脊線數(shù)，采用Bresenham 畫線算法4計算Ridge_count。（1）Bresenham 算法的基本原理：過各行、各列像素中心構(gòu)造一組虛擬網(wǎng)格線，按直線從起點(diǎn)到終點(diǎn)的順序計算直線與各垂直網(wǎng)格線的交點(diǎn)，然后確定該列像素中與此交點(diǎn)最近的像素。該算法的巧妙之處在于可以采用增量計算，使得對于每一列，只要檢查一個誤差項的符號，就可以確定所求的像素。假定直線的斜率在0到1之間，如圖2所示： - 2 - 圖2. Bresenham算法示意圖假設(shè)x 列的像素已經(jīng)確定，其行下標(biāo)為y 。那么下一個像素的列坐標(biāo)必為x+1，而行坐標(biāo)有可能不變，也有可能遞增1。而是否遞增1取決于如圖6所示

9、的誤差項d 的值。因?yàn)橹本€的起始點(diǎn)在像素中心，所以誤差項d 的初始值為0。x 的下標(biāo)每增加1，d 的值就相應(yīng)地遞增直線的斜率值，即d=d+k（k=y/x 為直線斜率）。一旦d 1時，就把它減去，這樣保證d 始終在0，1之間。當(dāng)d 0.5時，直線與x+1列垂直網(wǎng)格線交點(diǎn)最接近于當(dāng)前像素(x，y 的右上方像素(x+1，y+1；而當(dāng)d<0.5時，更接近于像素(x+1，y 。當(dāng)d=0.5時，與上述二像素一樣接近，約定取(x+1，y+1。令e=d-0.5，則當(dāng)e 0時，下一個像素的y 下標(biāo)增加1，而當(dāng)e<0時，下一個像素的y 下標(biāo)不增，e 的初始值為-0.5。（2）用Bresenham 算法

10、計算穿越脊線數(shù)：利用Bresenham 算法找出細(xì)節(jié)點(diǎn)和中心點(diǎn)之間的連線，統(tǒng)計該連線上的黑點(diǎn)個數(shù)，這樣就可以計算出穿越脊線數(shù)，如圖3（a ）所示，黑色代表指紋脊線，灰色代表細(xì)節(jié)點(diǎn)和中心點(diǎn)的連線，連線經(jīng)過了脊線上的一點(diǎn)，說明穿過了一條脊線。但在處理過程中會遇到如下兩個問題：問題一：如圖3（b ）所示，連線同樣經(jīng)過一條脊線，但是它并沒有經(jīng)過脊線上的一點(diǎn)，該脊線就會漏掉，這樣所得到的結(jié)構(gòu)信息不準(zhǔn)確。因此在這里增加一個判斷條件，對連線上的白點(diǎn)檢查其8鄰域，如果有兩個點(diǎn)是脊線上的點(diǎn)，那么連線經(jīng)過這條脊線，連線上的下一個點(diǎn)不用檢查。問題二：連線有可能恰好與某條指紋脊線的一段重合，所以對黑點(diǎn)是否可以判斷為一

11、條脊線還要加入一個判定條件, 考計算Ridge_count的具體算法是： （a ） （b ）圖3 計算穿越脊線數(shù)示意圖 慮其距離上一黑點(diǎn)的長度。 a. 用 Bresenham 畫線算法計算由中心點(diǎn)到細(xì)節(jié)點(diǎn)的連線所經(jīng)過的各點(diǎn)的坐標(biāo)，記錄在數(shù)組connect 中；c. 遍歷連線上的點(diǎn)，若遇上黑點(diǎn)，轉(zhuǎn)下一步；若為白點(diǎn)，檢查其8鄰域，判斷是否經(jīng)過脊線，如果是的話，connect+且轉(zhuǎn)下一步；如果不是，檢查連線上的下一點(diǎn)；d. 該點(diǎn)和上一黑點(diǎn)距離大于等于 e 則認(rèn)為遇上一條紋線，Ridge_ count+，遍歷后得出紋線數(shù)目Ridge_ count。 b. 統(tǒng)計出其中白色點(diǎn)個數(shù) W 和黑色點(diǎn)個數(shù) B ，

12、則e=W/B為兩個黑點(diǎn)間的平均距離；4匹配提取出指紋圖像的所有特征向量，若待識別指紋P 有M 個特征點(diǎn)，模板指紋Q 有N 個特征點(diǎn)，則用局部特征向量組P=P1,P2,Pm表示P 的M 個局部特征向量，向量組- 3 - Q=Q1,Q2,Qn表示Q 的N 個局部特征向量。其中每一個局部特征向量組的數(shù)學(xué)表達(dá)為：Pi=（x, y）, T_D,，d ，Ridge_ count） （3）式（3）中：（x ，y ）：細(xì)節(jié)特征點(diǎn)在原始圖像中的坐標(biāo)；T_D：細(xì)節(jié)點(diǎn)的類型；：細(xì)節(jié)點(diǎn)的方向；d ：細(xì)節(jié)點(diǎn)與中心點(diǎn)的角度差；Ridge_ count：細(xì)節(jié)點(diǎn)到中心點(diǎn)連線所穿越的脊線數(shù)。將P 中的每一個局部特征向量Pi(i

13、=1,2,.,M與Q 中的每一個局部向量Qj(j=1,2,N進(jìn)行一一比對，在角度差滿足允許范圍，穿越的脊線數(shù)以及細(xì)節(jié)點(diǎn)類型相同的條件下，這兩個點(diǎn)匹配，匹配的細(xì)節(jié)點(diǎn)數(shù)目Match_number大于等于13則兩個指紋來自同一個手指，否則不是，具體過程如下：1. 比較Pi.Ridge_count 與Qj.Ridge_count，如果Pi.Ridge_count =Qj.Ridge_count，即穿越的脊線數(shù)相等，轉(zhuǎn)下一步；否則，j+，轉(zhuǎn)步驟1；2. 比較Pi . d與 Qj . d，如果|Pi . d- Qj . d|<（為一個比較小的值），轉(zhuǎn)下一步；否則，j+，轉(zhuǎn)步驟1；3. 比較Pi .

14、T_D與 Qj . T_D，如果細(xì)節(jié)點(diǎn)的類型也相同，則判斷Pi 與Qj為一對匹配點(diǎn)，Match_number+，j+，轉(zhuǎn)步驟1；4. 判斷Match_number13是否為真，是的話輸出結(jié)果為匹配，否則，輸出不匹配。5實(shí)驗(yàn)結(jié)果下面是對指紋圖像進(jìn)行預(yù)處理和特征提取的結(jié)果，如圖4所示： (a1 (a2 (a3 (a4 (b1 (b2 (b3 (b4圖4提取特征結(jié)果圖4（a1）、4（a2）、4（a3）、4（a4）是原始指紋圖像，圖4（a1）與4（a2）、圖4（a3）與4（a4）分別是同一個手指兩次錄入的結(jié)果，因?yàn)榘磯簳r用力方向大小的不同，指紋紋線發(fā)生了形變，圖4（b1）、4（b2）、4（b3）、4（

15、b4）是提取特征后的結(jié)果。中間圓圈標(biāo)識中心點(diǎn)，十字符號標(biāo)識端點(diǎn)，矩形標(biāo)識分叉點(diǎn)。特征的詳細(xì)信息包括：細(xì)節(jié)點(diǎn)的位置坐標(biāo)(x, y，方向，細(xì)節(jié)點(diǎn)類型T_D，細(xì)節(jié)點(diǎn)到中心點(diǎn)連線所穿越的脊線數(shù)Ridge_count。比較圖4(b1和圖4 (b2，圖4(b3和圖4 (b4細(xì)節(jié)點(diǎn)的坐標(biāo)位置，方向發(fā)生了變化，但是到中心點(diǎn)穿越的- 4 - 脊線數(shù)不變，相對中心點(diǎn)的角度差變化很小，根據(jù)脊線數(shù)和角度差對細(xì)節(jié)點(diǎn)進(jìn)行匹配，圖4(b1和圖4 (b2 找到13個匹配的點(diǎn)，圖4(b3和圖4 (b4找到16個匹配的點(diǎn)，從而判斷圖4（a1）與4（a2），圖4（a3）與4（a4）分別來自同一個手指。用200幅指紋圖像對整個算法進(jìn)

16、行測試，算法用VC 語言實(shí)現(xiàn)，指紋的誤識率小于2%，拒識率小于1.5%，測試的結(jié)果表明該算法具有較高的識別率，對指紋形變具有較強(qiáng)的魯棒性，并具有算法簡單，速度較快的優(yōu)點(diǎn)。6結(jié)論實(shí)現(xiàn)了一套完整的指紋識別算法，主要介紹了一種結(jié)合結(jié)構(gòu)特征的指紋細(xì)節(jié)點(diǎn)匹配方法，該方法引入細(xì)節(jié)點(diǎn)與中心點(diǎn)的角度差以及細(xì)節(jié)點(diǎn)到中心點(diǎn)所穿越的脊線數(shù)作為細(xì)節(jié)特征的向量，采用一種改進(jìn)的Bresenham 畫線算法計算穿越的脊線數(shù)，準(zhǔn)確地提取出了指紋圖像的結(jié)合結(jié)構(gòu)特征的特征信息，不僅克服了傳統(tǒng)點(diǎn)模式匹配算法中存在的算法復(fù)雜，比較耗時的問題，并對指紋圖像的變形具有較強(qiáng)的魯棒性，最終得到比較理想的匹配結(jié)果。參考文獻(xiàn)1江杰，胡曉莉，李杰

17、。一種新的指紋細(xì)節(jié)點(diǎn)匹配算法的研究。計算機(jī)應(yīng)用，2005，25，114-115.2劉靈麗，李麗娟。指紋圖像預(yù)處理和特征提取。計算機(jī)工程，2006，32(16，190-192.3羅希平，田捷。自動指紋識別中的圖像增強(qiáng)和細(xì)節(jié)匹配算法。軟件學(xué)報，2002，13(5，946-955.4孫家廣。計算機(jī)圖形學(xué)M。北京：清華大學(xué)出版社，1998.5 Lin Hong, Wan, Yi-fei, Jain, A. Fingerprint image enhancement: algorithm and performance evaluation. IEEE Transactions on Pattern A

18、nalysis and Machine Intelligence,1998,20(8:777789.6Anil Jain, Lin Hong, and Ruud Bolle, On-Line Fingerprint Verification. IEEE Transactions On Pattern Analysis And Machine Intelligence. 1997, 19(4:302-314.7 Jiang, Xu-dong, Yau, Wei-Yun. Fingerprint minutiae matching based on the local and global str

19、uctures. In: Sanfeliu, A., Villanueva, J.J., eds. Proceedings of the 15th International Conference on Pattern Recognition. Los Alamitos, CA: IEEE Computer Society Press, 2000,1042-1045.An Algorithm of Matching Fingerprint Minutiae Based onStructure FeatureLv Yuhua1, Li Lijuan1, Liu Lingli21. Department of Computer and Communication, Hunan University, Changsha (4100822. Deptment of computer, Xiangnan University, Hunan, Chenzhou (423000AbstractA new approach to match fingerprint feature is presen