魏鴻磊，張文孝，華順剛

(1.大連海洋大學機械與動力工程學院，遼寧大連 116023;2.大連理工大學機械工程學院，遼寧大連 116023)

指紋匹配是指通過比較指紋間的特征來評估指紋相似性的過程，它是自動指紋識別系統(tǒng)的關(guān)鍵環(huán)節(jié)，一直是模式識別領(lǐng)域的重要研究課題.基于細節(jié)特征的指紋匹配算法通過提取細節(jié)特征(主要是指紋脊線的端點和分叉點)，將圖像的匹配轉(zhuǎn)變?yōu)橐幌盗悬c的空間分布相似性的評估，以精度高、存儲量低等優(yōu)勢獲得了廣泛的應(yīng)用，成為指紋匹配的主流算法.這種算法的應(yīng)用條件是指紋應(yīng)有較多的細節(jié)特征可供比對，然而在實際應(yīng)用中有一部分人的手指上僅有少量的細節(jié)點，或者由于采集角度等原因，僅采集到了局部指紋，造成細節(jié)點偏少.在這2種情況下無法應(yīng)用基于細節(jié)特征的指紋匹配算法，需要從指紋的脊線中尋找其他特征進行匹配.脊線的形狀具有較強的區(qū)分力，可用于指紋比對，但是采用脊線特征需要較大的特征存儲量，且脊線集的配準較為困難;因此目前常用方法是根據(jù)細節(jié)點的位置和方向，將與細節(jié)點相連的少量脊線對齊后進行局部匹配［1-4］.但是在上述提到的細節(jié)點數(shù)量較少的情況下，可用來進行比對的脊線也相應(yīng)較少，對指紋匹配的幫助有限，因此提取指紋脊線的宏觀特征用于匹配的方法目前得到了廣泛關(guān)注［5-8］，其中典型算法是Jain等的 FingerCode方法［7］.該方法采用 Gabor小波對指紋中心點周圍的局部區(qū)域進行8方向濾波并計算各扇區(qū)的灰度方差，組成固定長度的編碼，稱為FingerCode，通過計算不同指紋的 Finger-Code編碼之間的歐氏距離來評估相似性.但這種方法需要對圖像進行卷積計算，計算量很大，且不能應(yīng)用于沒有或無法精確定位中心點的指紋，使得應(yīng)用范圍受到很大限制.Ross等對FingerCode算法進行了改進，通過傅里葉變換將卷積運算轉(zhuǎn)換到頻域進行，從而減少了計算量，通過配準細節(jié)點來配準指紋，再用類似FingerCode編碼的脊線特征圖進行匹配［8］.這種方法不要求提取中心點，但需要對更大面積的指紋圖像進行卷積運算，計算量仍然較大.

針對上述問題，本文提出一種新的利用脊線形狀為主要匹配特征的指紋匹配算法.在特征提取階段，通過定長距離采樣以提取脊線形狀，并對采樣點進行優(yōu)選以減少冗余，從而減少模板存儲量;在匹配階段，根據(jù)細節(jié)特征配準脊線集，對脊線進行定長編碼，利用編碼進行模糊匹配，從而得到指紋相似度.算法在多個指紋庫上進行比對實驗，取得了較好的結(jié)果.

1 脊線的提取

指紋的脊線形狀各異，很難用確定的函數(shù)對其進行描述.本文對脊線進行采樣時，通過采樣點的比較來評估脊線形狀的相似性，由于準確描述脊線形狀需要記錄大量的脊線采樣點，所以為減小計算量和存儲負擔，在保證脊線重建精度的條件下，對采樣點進行優(yōu)選，以刪除冗余采樣點.

1.1 脊線采樣

脊線采樣在二值化的指紋圖像上進行.從端點開始，逐點跟蹤脊線，并將像素值改變以標記已跟蹤過的像素，避免重復(fù)跟蹤.每隔1個固定間距記錄1個采樣點，直到脊線的末端.如果跟蹤過程中發(fā)現(xiàn)當前點為分叉點，則將每個分叉都記錄為一條獨立的脊線，并分別采樣.

1.2 采樣點優(yōu)選

保留每條脊線的起始點和終止點，對中間采樣點進行優(yōu)選.如果舍棄某個采樣點使得近似脊線和原脊線之間產(chǎn)生過大的差異，則該點必須被保留，否則該點不保留.具體方法以圖1為例進行說明.

1)當且僅當L1、L2和L3都小于預(yù)定閾值t(本文取為t=3)時，pn+3為冗余點;當 L1、L2和L3中至少有1個大于閾值時，說明pn+3不可刪除，即pn+3為需保留的優(yōu)選點.

圖2是脊線重建示例.在原脊線圖2(a)上以間隔8個像素采樣，共得到1 126個點，以允許誤差3個像素優(yōu)選出280個關(guān)鍵點，只有原總數(shù)的25%左右，以此重建的脊線圖如2(b)所示.

圖2 重建脊線示例Fig.2 Sketch map of reconstructed ridge images

2 脊線的模糊匹配

首先根據(jù)細節(jié)點匹配得到的配準參數(shù)將脊線采樣點坐標進行轉(zhuǎn)換，以對齊兩脊線集，然后對兩指紋重合區(qū)域的脊線進行編碼，并進行編碼的模糊匹配，最后計算脊線的總匹配分值.

2.1 脊線配準

沒有細節(jié)點的指紋是十分少見的，本文研究的是具有少量細節(jié)點的指紋匹配問題.為了能夠迅速、準確配準脊線集，首先進行細節(jié)點匹配［9］，根據(jù)得到的配準參數(shù)將脊線采樣點進行坐標轉(zhuǎn)換，即對齊脊線集，過程如圖3所示.

圖3 脊線的對齊Fig.3 Alignment of ridges

2.2 脊線編碼

為使兩指紋脊線能夠快速準確地匹配，需要對兩指紋重合區(qū)域的脊線進行編碼，脊線編碼過程如圖4所示.

圖4 脊線的編碼方法Fig.4 The method of ridges coding

1)求出兩指紋配準后重疊區(qū)域的外包矩形，然后在重疊矩形上以間距λ畫豎直線(本文取為λ=10)，設(shè)共有K條豎直線.

2)為每條脊線生成一個2×(K+2)大小的編碼數(shù)組，存儲該脊線與K條豎直線交點的y坐標.該編碼的第1位是與該脊線相交的第1根豎直線在編碼中的位置，第2位是與該脊線相交的最后一根豎直線在編碼中的位置，從第3位開始記錄每根豎直線與該脊線交點的y坐標，當沒有交點時，認為是無效編碼位，在其位置補0.由于每條脊線經(jīng)常與豎直線有2個交點，因此該編碼共有2行，第1行記錄第1個交點的y坐標，第2行記錄第2個交點的y坐標.

3)同樣采用2)的方法，根據(jù)水平線與每條脊線的交點的x坐標得到x編碼.

在實際編程實現(xiàn)過程中，無需恢復(fù)脊線圖，只求出由線段組成的脊線與柵格的交點坐標，按規(guī)則填入編碼數(shù)組即可.

2.3 脊線的模糊匹配

假設(shè)有2條脊線(分別屬于2個指紋)將要比對，其x和y編碼的個數(shù)分別為K和L.比較相同位置的編碼值，如果兩編碼所有坐標的差值都小于預(yù)定閾值D，則認為這2條脊線相似.以脊線相同位置編碼為模糊集的論域，以相同位置編碼的相似程度為隸屬度，建立衡量兩脊線相似程度的模糊集.兩脊線相同位置編碼的隸屬度按式(1)計算.

式中:c1i和c2i分別是兩脊線相同位置的編碼值，若兩脊線相同位置編碼都為0，則隸屬度記為0.兩脊線相似模糊集可用式(2)表示.

式中:n表示編碼中公共區(qū)域的長度.兩脊線編碼中無效編碼值(即編碼中0的位置)的隸屬度為0.若有多條脊線與一條脊線相似，則通過式(3)計算隸屬度均值，選取均值最大的一對作為匹配對.

若兩指紋共組成了m對匹配脊線模糊集，則評判向量為

對每一模糊匹配集賦予相同的權(quán)重，采用加權(quán)平均法進行相似度綜合評判，如式(4):

若兩指紋在公共區(qū)內(nèi)分別有N和M條脊線，共組成了m對模糊匹配對，則以組成匹配對的脊線數(shù)目占總脊線數(shù)目的比值作為綜合評判的權(quán)重，從而可采用式(5)來衡量兩指紋脊線的相似程度.

2.4 綜合匹配分值的計算

綜合考慮細節(jié)點匹配和脊線匹配結(jié)果，以更準確地評估指紋的相似性.假設(shè)Sm(I，J)為指紋I和J采用細節(jié)點匹配的分值，而Sr(I，J)為脊線匹配的分值，取λ1和λ2分別為這2種不同特征對應(yīng)的權(quán)系數(shù)，則細節(jié)特征和脊線特征的綜合匹配分值計算如式(6):

3 實驗結(jié)果與分析

按 FVC2000［10］的 測 試 標準，在 CPU 主 頻1.6 GHz、內(nèi) 存 512MB 的筆 記 本 微機 上，采 用FVC2004公布的4個指紋庫進行實驗，每個庫包含800(100×8)張指紋圖像.每個樣本與相同手指未能匹配上的其余樣本的比率稱為錯誤拒絕率(false non-match rate，F(xiàn)NMR)，每個庫FNMR的實際測試總數(shù)為((8×7)/2)×100=2 800次.每個手指的第1個樣本與其他手指的第1個樣本匹配成功的比率稱為錯誤接受率(false match rate，F(xiàn)MR)，每個庫FMR實際測試的總數(shù)為(100×99)/2=4 950次.EER(equal error rate)也叫等錯誤率，是當FNMR=FMR時的FNMR值，ROC是采用對數(shù)坐標的FMR與FNMR的關(guān)系曲線.

本文同時實現(xiàn)了4種算法，分別是細節(jié)點匹配算法［9］、局部脊線匹配算法［1］、FingerCode 算法［8］以及本文脊線匹配算法，分別記為 M、MLR、MFC和MGR，其中MLR、MFC和MGR中均以M算法為基礎(chǔ)，再融合各自特有的算法.為便于比較，在進行MFC和本文MGR算法實驗時，首先進行細節(jié)匹配，同時檢查獲得最佳匹配值時參與匹配的細節(jié)點數(shù)，如果細節(jié)點數(shù)少于5個，則分別實施這2種算法，并且都根據(jù)式(6)與細節(jié)點算法加權(quán)融合，以進行2種算法的性能比較，其中細節(jié)點相似度的權(quán)值λ1取為0.6，脊線或 FingerCode算法的權(quán)值 λ2取為0.4.

表1是4種算法對4個指紋庫進行特征提取的耗時比較，表2是4種算法在4個庫中的匹配等錯誤率和平均耗時的比較，表3給出了MLR、MFC和MGR 3種算法與M算法相比，等錯誤率下降程度的統(tǒng)計結(jié)果，圖5是4種算法在4個指紋庫上的ROC曲線.由表1可見，與算法 M相比，MLR、MFC和MGR 3種算法都需要更大的計算量，其中以MFC算法耗時最長，平均達到了1.32 s，本文算法MGR次之，平均耗時0.81 s，MLR算法最少.由表2可見，與算法M相比，MLR、MFC和MGR 3種算法都明顯降低了等錯誤率 EER，但從表3可見，本文算法MGR使EER平均下降了21.5%，明顯優(yōu)于MLR算法的6.34%和MFC算法的9.65%.由于指紋匹配錯誤大都是由于低質(zhì)量指紋、不完整指紋或少細節(jié)點指紋引起的，MLR算法中參與匹配的脊線數(shù)量較少，雖特征提取耗時短，但對算法精度的提高也相對較低;MFC算法采用的是指紋脊線的紋理和流向等較“粗”的特征，精度提高有限，且特征提取計算量較大;本文算法MGR采用的脊線匹配更好地提高了不完整指紋或少細節(jié)點指紋的匹配精度，從而有效提高了整體匹配的精度.從表2知，在匹配時間方面(即每種算法在4個庫中所有匹配的平均時間，不包括預(yù)處理和特征提取時間)，由于實際采用脊線匹配的次數(shù)較少(經(jīng)統(tǒng)計，脊線匹配的次數(shù)約占總匹配次數(shù)的6%左右)，所以每個庫的平均匹配時間沒有明顯增加.

表1 特征提取耗時比較Table 1 Comparison of time consuming for feature extraction s

表2 EER及特征匹配耗時比較Table 2 Comparison of EER and matching time consuming

表3 EER下降程度比較Table 3 Comparison of the decrease level on EER %

圖5 在FVC2004 4個指紋庫上的ROC曲線比較Fig.5 Comparative ROC curves of three algorithms on FVC2004 fingerprint databases

4 結(jié)束語

雖然基于細節(jié)特征的指紋匹配算法應(yīng)用最為廣泛，但在很多情況下可參與指紋匹配的細節(jié)點數(shù)量較少，此時采用細節(jié)點匹配不可靠.采用脊線特征可以充分利用指紋脊線信息，提高識別精度，但是采用脊線匹配存在模板存儲量大、對齊困難、計算量較大等缺點，影響了脊線特征的應(yīng)用.本文算法采用優(yōu)選脊線采樣點減少特征存儲量，通過脊線編碼模糊匹配減少計算量.在FVC2004的4個指紋庫上的測試表明，本文算法能夠有效提高指紋匹配的精度.該算法的不足之處在于與單獨采用細節(jié)特征相比，仍需較大的計算量和存儲量.考慮到僅需對細節(jié)特征可靠性不高的指紋使用本算法，因此大量指紋匹配時的平均計算量的增加并不顯著.在對指紋存儲量有較高要求時，可以僅存儲脊線信息，而其他信息如細節(jié)特征、方向場特征等可以從脊線信息中提取，從而減少存儲量.進一步的研究將考慮采用樣條曲線等數(shù)學工具擬合脊線進行匹配，以減少存儲量和計算量，并提高準確性.

［1］HE Yuliang，TIAN Jie，LUO Xiping，et al.Fingerprint matching based on global comprehensive similarity［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(6):850-862.

［2］ZHONG Weibo，NING Xinbao.A fingerprint matching method based on minutiae and ridges［C］//Proceedings of 2008 3rd International Conference on Intelligent System and Knowledge Engineering. Xiamen， China，2008:1071-1074.

［3］ZHENG Xiaolong，WANG Yangsheng.Fingprint matching based on ridge similarity［C］//Proceedings of 2008 IEEE International Conference on Acoustics，Speech and Signal Processing.Las Vegas，USA，2008:1701-1704.

［4］VATSA M，SINGH R，NOORE A，et al.Combining pores and ridges with minutiae for improved fingerprint verification［J］.Signal Processing，2009，89(12):2676-2685.

［5］JAIN A K，F(xiàn)ENG Jianjiang.Latent fingerprint matching［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(1):88-100.

［6］CHOI Heeseung，CHOI Kyoungtaek，KIM Jaihie.Fingerprint matching incorporating ridge features with minutiae［J］.IEEE Transactions on Information Forensics and Security，2011，6(2):338-345.

［7］JAIN A K，PRABHAKAR S，HONG L，et al.Filterbankbased fingerprint matching［J］.IEEE Transactions on Image Processing，2000，9(5):846-859.

［8］ROSS A，JAIN A K，REISMAN J.A hybrid fingerprint matcher［C］//Proceedings of the 16th International Conference on Pattern Recognition.Quebec City，Canada，2002，3:795-798.

［9］魏鴻磊，歐宗瑛，甘樹坤，等.采用逐級配準和分值加權(quán)的指紋匹配算法［J］.計算機輔助設(shè)計與圖形學學報，2006，18(6):832-837.

WEI Honglei，OU Zongying，GAN Shukun，et al.Fingerprint matching using gradual alignment and weighted matc-hing score［J］.Journal of Computer-Aided Design ＆ Computer Graphics，2006，18(6):832-837.

［10］MAIO D，MALTONI D，CAPPELLI R，et al.FVC2000:fingerprint verification competition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(3):402-412.