一種采用脊線特征的指紋模糊匹配方法

魏鴻磊，張文孝，華順剛

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

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

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

1 脊線的提取

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

1.1 脊線采樣

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

1.2 采樣點優選

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

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

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

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

2 脊線的模糊匹配

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

2.1 脊線配準

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

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

2.2 脊線編碼

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

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

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

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

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

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

2.3 脊線的模糊匹配

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

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

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

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

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

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

2.4 綜合匹配分值的計算

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

3 實驗結果與分析

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

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

表1是4種算法對4個指紋庫進行特征提取的耗時比較，表2是4種算法在4個庫中的匹配等錯誤率和平均耗時的比較，表3給出了MLR、MFC和MGR 3種算法與M算法相比，等錯誤率下降程度的統計結果，圖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%，明顯優于MLR算法的6.34%和MFC算法的9.65%.由于指紋匹配錯誤大都是由于低質量指紋、不完整指紋或少細節點指紋引起的，MLR算法中參與匹配的脊線數量較少，雖特征提取耗時短，但對算法精度的提高也相對較低;MFC算法采用的是指紋脊線的紋理和流向等較“粗”的特征，精度提高有限，且特征提取計算量較大;本文算法MGR采用的脊線匹配更好地提高了不完整指紋或少細節點指紋的匹配精度，從而有效提高了整體匹配的精度.從表2知，在匹配時間方面(即每種算法在4個庫中所有匹配的平均時間，不包括預處理和特征提取時間)，由于實際采用脊線匹配的次數較少(經統計，脊線匹配的次數約占總匹配次數的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 結束語

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

［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，FENG 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］魏鴻磊，歐宗瑛，甘樹坤，等.采用逐級配準和分值加權的指紋匹配算法［J］.計算機輔助設計與圖形學學報，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.