李天平，李亞碩，王帥強，張 擎，尹義龍，任春曉

（1.山東師范大學物理與電子科學學院濟南250014；2.山東大學計算機科學與技術學院濟南250101；3.山東財經(jīng)大學計算機科學與技術學院濟南250014）

0 引 言

指紋識別的核心步驟指紋匹配主要有四種方法：①基于細節(jié)點的匹配方法［1－7］；②基于紋線的匹配方法［8－9］；③基于紋理的匹配方法［10－11］；④基于人工神經(jīng)網(wǎng)絡的匹配方法［12－13］。其中基于細節(jié)點的指紋匹配方法，由于所使用的特征相對穩(wěn)定、可靠，一直是指紋識別中最為基礎、最為主流的匹配方法。但是，現(xiàn)有基于細節(jié)點的指紋匹配中，匹配結果只由成功配對的細節(jié)點數(shù)量來決定。未能形成匹配的細節(jié)點都被視為無用信息，沒有加以利用。而實際上，未能形成匹配的細節(jié)點中，包含著較多的區(qū)分性信息，也應該用于提高指紋識別系統(tǒng)的性能。

基于上述思路，本文對未能形成匹配的細節(jié)點中包含的區(qū)分性信息進行了挖掘和利用，將其作為輔助特征，與一種已有的基于細節(jié)點的指紋匹配方法進行得分級融合，實現(xiàn)指紋識別，從而有效提高了識別性能。

1 問題分析

1.1 相關概念

（1）同源指紋與異源指紋：采集自同一手指的指紋圖像，稱為同源指紋；采集自不同手指的指紋圖像，稱為異源指紋。

（2）同源匹配與異源匹配：如果模板指紋和輸入指紋是同源的，則稱它們之間的匹配為同源匹配；如果模板指紋和輸入指紋是異源的，則稱它們之間的匹配為異源匹配。

（3）匹配區(qū)域：指一對模板指紋和輸入指紋（實際上是特征提取后得到的一對平面細節(jié)點集合）在完成配準、進行匹配（同源匹配或異源匹配）后，所有成功配對的細節(jié)點所圍成的最大區(qū)域。本質上，匹配區(qū)域是可用于相似程度度量的、模板指紋和輸入指紋的有效重疊區(qū)域。

（4）未匹配細節(jié)點：雖位于匹配區(qū)域內(nèi)、但卻沒有形成配對的細節(jié)點。

1.2 未匹配細節(jié)點信息的區(qū)分性分析

在同源匹配中，未匹配細節(jié)點的成因主要有三個方面：①由于圖像本身存在形變、圖像預處理技術不夠完善等因素的影響，使得部分細節(jié)點定位存在較大偏差；②匹配過程中，匹配算法對成功匹配的條件要求比較高，使得部分本應形成匹配的細節(jié)點對難以實現(xiàn)匹配；③個別偽細節(jié)點的存在。

對于異源匹配而言，由于模板指紋和輸入指紋來自不同的手指，匹配的結果只是找到模板指紋和輸入指紋相似性最大的局部區(qū)域作為匹配區(qū)域。顯然，異源指紋的匹配本質上是一種“偽匹配”，但是，當圖像質量比較差、面積比較大、提取的偽細節(jié)點數(shù)量很多、分布比較密集時，也有可能在局部重疊區(qū)域（匹配區(qū)域）產(chǎn)生足夠多的、滿足匹配條件的細節(jié)點對，這也是指紋識別中產(chǎn)生誤識的最主要原因。異源匹配中，未匹配細節(jié)點的產(chǎn)生，本質上只是一個隨機性質的問題。

宏觀上看，同源匹配和異源匹配，匹配區(qū)域內(nèi)未匹配細節(jié)點信息是有明顯差異的：①對同源匹配而言，一般來說，匹配區(qū)域內(nèi)未匹配細節(jié)點的數(shù)量會很少；而對異源匹配來說，匹配區(qū)域內(nèi)未匹配細節(jié)點的數(shù)量往往會比較多；②對同源匹配而言，本應形成匹配、但未能成功匹配的點對，在位置上仍存在著很強的對應關系（盡管有一定的定位偏差）；③對同源匹配而言，匹配區(qū)域內(nèi)的未匹配細節(jié)點在分布上存在著較高的一致性和規(guī)律性；而對異源匹配而言，匹配區(qū)域內(nèi)的未匹配細節(jié)點在分布上幾乎沒有任何一致性和規(guī)律性。

所以，從成因和特點來看，同源匹配和異源匹配中未匹配細節(jié)點是包含了一定的區(qū)分性信息的。如果能有效挖掘其中的區(qū)分性信息并加以利用，可以提高指紋識別系統(tǒng)的性能。

2 未匹配細節(jié)點的特征定義與提取

2.1 未匹配細節(jié)點比例

一般來說，同源匹配和異源匹配中匹配區(qū)域內(nèi)的未匹配細節(jié)點數(shù)量會有一定差異。如在圖1和圖2中，紅色點表示匹配細節(jié)點，藍色點表示匹配區(qū)域內(nèi)未匹配細節(jié)點，紅色框框出匹配區(qū)域。兩幅圖中，雖然匹配細節(jié)點對數(shù)量都為10，但同源匹配（圖1）中未匹配細節(jié)點數(shù)量明顯少于異源匹配（圖2）中未匹配細節(jié)點數(shù)量。

本文用未匹配細節(jié)點與匹配細節(jié)點的比例來刻畫未匹配細節(jié)點數(shù)量上的特點，此比例可以在一定程度上分辨同源匹配和異源匹配，是可以利用的區(qū)分性信息。將此比例記為R，計算式如下：

式中：N1為模板指紋匹配區(qū)域內(nèi)未匹配細節(jié)點個數(shù)；N2為輸入指紋匹配區(qū)域內(nèi)未匹配細節(jié)點個數(shù)；Nc為兩副指紋匹配成功的細節(jié)點對數(shù)。

圖1 兩幅同源指紋的匹配結果Fig.1 Matching result of two homologous fingerprints

圖2 兩幅異源指紋的匹配結果Fig.2 Matching result of two heterologous fingerprints

R越小，兩副指紋的匹配得分越高，因此，用公式（2）中的歸一化方法將R歸一化到［0，1］之間，給出匹配得分Sa。

式中：max R和min R分別代表R的最大值和最小值。

2.2 緊互對原型對距離

對同源匹配而言，本應形成匹配、但未能成功匹配的點對，在位置上仍存在著很強的對應關系（盡管有一定的定位偏差）。但異源匹配中，由于未匹配細節(jié)點的產(chǎn)生在本質上是隨機的，因此，未匹配成功細節(jié)點在位置上不存在任何對應規(guī)律。本文定義了緊互對原型對，并用其描述兩個未匹配細節(jié)點在位置上的對應關系。

定義1 對A和B兩幅指紋進行匹配，若在A和B匹配區(qū)域內(nèi)的兩個未匹配細節(jié)點pi和qi滿足式（3），則稱細節(jié)點對（pi，qi）為緊互對原型對：

用函數(shù)d（·）計算兩點間的歐式距離；Am為指紋A中匹配區(qū)域內(nèi)未匹配細節(jié)點的集合；Bm為指紋B中匹配區(qū)域內(nèi)未匹配細節(jié)點的集合。

圖3中的模板指紋和輸入指紋是同源指紋。紅色點代表匹配成功的細節(jié)點，藍色點代表匹配區(qū)域內(nèi)未匹配成功的細節(jié)點。模板指紋中綠色點代表輸入指紋匹配區(qū)域內(nèi)未匹配細節(jié)點在模板指紋中的位置?？梢钥吹?，有幾個綠色細節(jié)點與藍色細節(jié)點距離很近，根據(jù)定義1，這些細節(jié)點對為緊互對原型對。

圖3 兩幅指紋中的緊互對原型對Fig.3 Tight pair-wise prototypes in two fingerprints

根據(jù)上文分析，在同源匹配中，可能存在較多數(shù)量的緊互對原型對，并且緊互對原型對中兩細節(jié)點間的距離相對較近。而異源匹配中有可能無法提取出緊互對原型對，在提取出的緊互對原型對中兩個細節(jié)點的距離也相對較遠。由此，緊互對原型對中兩細節(jié)點的距離信息應該是具有區(qū)分性的信息。統(tǒng)計兩副指紋中所有緊互對原型對，并用式（4）計算平均距離Davg作為衡量指紋相似度的指標，平均距離越小，兩副指紋的匹配得分越高。

式中：Np為緊互對原型對的個數(shù)；d（pi，qi）為第i個緊互對原型對中兩細節(jié)點的歐式距離。

在計算過程中若未匹配細節(jié)點個數(shù)為0，則置Davg為0，若未匹配細節(jié)點個數(shù)不為0，但緊互對原型對個數(shù)為0，則置Davg為較大值。最后，采用與2.1節(jié)中相同的歸一化方法將Davg歸一化到［0，1］之間，給出匹配得分Sb。

2.3 網(wǎng)格集合距離

利用網(wǎng)格集合距離來對未匹配細節(jié)點的分布一致性進行衡量。將一幅指紋圖像劃分成M×N個大小相同的網(wǎng)格，計算每個網(wǎng)格內(nèi)未匹配細節(jié)點的個數(shù)，其中只計算匹配區(qū)域內(nèi)的未匹配細節(jié)點，設與匹配區(qū)域沒有交集的網(wǎng)格中未匹配細節(jié)點個數(shù)為0。將兩副待匹配指紋中第i（i＝1，2，…，M×N）個網(wǎng)格中的未匹配細節(jié)點集合分別記為Ai和Bi，則兩副指紋的網(wǎng)格距離G由公式（5）給出：

式中：｜Ai｜和｜Bi｜分別代表集合Ai、Bi中的元素個數(shù)。網(wǎng)格距離G越小，認為兩幅指紋中未匹配細節(jié)點在分布上越一致（相似），從而，兩副指紋的匹配得分越高。最后，采用與2.1節(jié)中相同的歸一化方法將G歸一化到［0，1］之間，給出匹配得分S c。

2.4 Hausdorff距離

從另外一個角度，如果把匹配區(qū)域內(nèi)的未匹配細節(jié)點集看作一個集合，則可以直接通過計算兩個集合的相似度來衡量兩幅指紋中未匹配細節(jié)點在分布上的一致性。本文用Hausdorff距離［14］來衡量兩個未匹配細節(jié)點集合的相似度。

對于集合A＝（a1，a2，…，am）與集合B＝（b1，b2，…，bn），Hausdorff距離的計算公式為：

在計算兩個未匹配細節(jié)點集合的Hausdorff距離時，用公式（9）（10）中的歐式距離代替公式（7）（8）中兩元素的差運算：

具體過程如下：設集合A＝（a1，a2，…，am）和集合B＝（b1，b2，…，bn）分別為模板指紋和輸入指紋匹配區(qū)域內(nèi)的未匹配細節(jié)點集合。首先針對A中每個細節(jié)點，計算其到B中所有細節(jié)點距離中的最小距離，然后取集合A中得到的所有該最小距離中的最大值作為集合A到集合B的距離，記為h（A，B）。同理，算得集合B到集合A的距離，記為h（B，A）。最后，取h（A，B）與h（B，A）中較大的值作為集合A和集合B的Hausdorff距離。但上述過程極易受到偽細節(jié)點的影響。例如一個集合中的某偽細節(jié)點與其他細節(jié)點距離都較遠，則用上述方法得到的Hausdorff距離將是一個較大的噪聲值。因此，本文使用Hausdorff距離的改進算法：用集合A中每個細節(jié)點到集合B中所有細節(jié)點距離的平均值代替最小值，取集合A中所有細節(jié)點得到的平均值中的最大值作為集合A到集合B的距離。同理，計算集合B到集合A的距離。最后，取二者的最大值作為集合A和集合B的Hausdorff距離。兩個集合的Hausdorff距離越小，兩幅指紋中未匹配細節(jié)點分布一致性越高，從而，兩副指紋的匹配得分越高。將Hausdorff距離用與2.1節(jié)中相同的歸一化方法歸一化到［0，1］之間，給出匹配得分Sd。

3 得分級融合

本文通過得分級融合方法，將上述從未匹配細節(jié)點中提取的四方面特征的匹配得分與一種已有的細節(jié)點方法［15］的匹配得分進行融合，實現(xiàn)指紋識別。文獻［15］提出了一種多模板融合的指紋識別方法，將指紋模板視為空間中的點，利用同一手指的兩兩模板之間的距離建立空間多面體，通過計算輸入模板與空間多面體中心的距離得到匹配得分。該方法在競賽數(shù)據(jù)庫FVC2000及FVC2002上得到了較好的識別效果。擬通過此融合策略達到兩個目的：①驗證未匹配細節(jié)點中的確存在可利用的區(qū)分性信息；②證明將從未匹配細節(jié)點中提取的區(qū)分性信息作為輔助特征用于指紋識別能夠提高指紋識別系統(tǒng)的性能。

在識別階段，將輸入指紋逐一與每個用戶的模板指紋進行匹配。采用線性加權的得分級融合方法將基于四個輔助特征的匹配得分（Sa、Sb、Sc和Sd）與已有匹配算法的匹配得分（So）進行融合，得到最終匹配得分Sf。計算公式如下：

（1）依據(jù)具體數(shù)據(jù)特性設置權值。不同應用背景下的數(shù)據(jù)特點并不相同，存在指紋質量等因素的差異，融合方法（1）對不同的數(shù)據(jù)庫設置不同的權值。原始匹配得分包含較多信息，仍作為主要的衡量標準，因此，設置權重k1為稍大于0.5的值，然后在每個數(shù)據(jù)庫上，根據(jù)多次實驗的經(jīng)驗值確定較高識別精度時k2～k5的組合。

（2）依據(jù)匹配得分設置權值。匹配得分本身可以在一定程度上反映其對應特征的重要程度。此方法考慮了不同指紋對匹配時的個性化特點。ki（i＝1，…，5）的計算公式如下：這里為了方便表達，分別用S1～S5替代So～Sd。

得到最終的匹配得分Sf后，設置閾值τ，如果Sf大于τ，則認為輸入指紋和模板指紋是同源指紋，將模板指紋對應的用戶ID返回；如果Sf小于等于τ，則認為輸入指紋和模板指紋為異源指紋，用相同方法將輸入指紋與模板庫中其他用戶的模板指紋進行匹配，直到遇到同源指紋，返回相應用戶ID。如果輸入指紋與模板庫中所有用戶的指紋都被認為是異源指紋，則返回錯誤或報警信息。

4 實驗結果及分析

4.1 實驗設置

實驗中選擇文獻［15］的方法為對比方法。該方法屬于典型的基于細節(jié)點的指紋匹配方法，其識別性能優(yōu)于當前同類方法。通過實驗將本文提出的融合方法（1）和融合方法（2）的識別性能與文獻［15］的方法進行了對比。

實驗使用國際指紋識別競賽的三個數(shù)據(jù)庫FVC2000、FVC2002和FVC2004，每個數(shù)據(jù)庫均包含4個子庫，分別稱為DB1、DB2、DB3和DB4。其中的每個子庫中都包含采集自100個手指的指紋，每個手指均采集8幅指紋圖像，即每個子庫包含800幅指紋圖像。FVC2000、FVC2002和FVC2004每個數(shù)據(jù)庫包含3200幅指紋圖像，三個數(shù)據(jù)庫共包含1200個不同手指的9600幅指紋圖像。

對每個手指，取數(shù)據(jù)庫中該手指的前3幅指紋圖像作為模板指紋，剩余的5幅指紋圖像作為測試指紋。分別用等錯誤率（EER）和ROC曲線兩個指標對識別性能進行評價。

4.2 實驗結果及分析

表1～表3列出了在FVC2000、FVC2002和FVC2004所有數(shù)據(jù)庫中本文提出的融合方法和已有方法獲得的EER?？梢钥闯觯疚姆椒ǖ腅ER全部低于已有匹配方法。雖然在不同指紋庫中，本文方法對系統(tǒng)識別性能提高的效果不同，但總體性能都有顯著提高。其中，第（2）種融合方法性能提高幅度最大。融合方法（2）優(yōu)于融合方法（1）的主要原因是其對權重的設置考慮了每次兩幅指紋匹配時的具體情況。

圖4～圖6分別展示了本文方法和已有方法在FVC2000、FVC2002和FVC2004中所有數(shù)據(jù)上的ROC曲線。ROC曲線更加直觀和全面地展示本文提出方法在識別性能方面的優(yōu)越性。在FVC所有數(shù)據(jù)庫上的實驗結果可以充分說明以下兩點：（1）未匹配細節(jié)點中的確含有能夠有效分辨同源指紋和異源指紋的區(qū)分性信息。（2）本文定義和提取的4種輔助特征可以有效挖掘未匹配細節(jié)點的區(qū)分性信息，融合4個輔助特征的匹配方法可以大幅度提升系統(tǒng)性能。

表1 FVC2000數(shù)據(jù)庫上各方法的EER（%）Table 1 EER（%）of different methods on FVC2000

表2 FVC2002數(shù)據(jù)庫上各方法的EER（%）Table 2 EER（%）of different methods on FVC2002

表3 FVC2004數(shù)據(jù)庫上各方法的EER（%）Table 3 EER（%）of different methods on FVC2004

需要特別說明的是：①本文實驗主要是為了驗證所挖掘的未匹配細節(jié)點特征信息的區(qū)分性以及將其與已有的細節(jié)點指紋匹配方法進行融合，是否可以有效提升指紋識別系統(tǒng)的性能。理論上，已有的各種基于細節(jié)點的指紋匹配方法，都可以作為被融合方法。所以，本文實驗中選擇的對比方法（文獻［15］的方法）本身是否為當前性能最優(yōu)的方法、融合后的性能是否為當前算法中最優(yōu)的與本文的貢獻并無直接關系。②本文方法造成系統(tǒng)性能提升的根本原因在于兩點，一是利用了在已有方法中被忽視的未匹配細節(jié)信息，對區(qū)分性信息的利用更加充分；二是未匹配細節(jié)點信息與成功匹配的細節(jié)點信息之間存在一定的互補性。例如在2.1節(jié)的圖1和圖2中，雖然匹配細節(jié)點對數(shù)量都為10，但是未匹配細節(jié)點的數(shù)量成為了有效的補充，為區(qū)分同源匹配和異源匹配提供了證據(jù)。顯然，這種得分級融合策略，與具體融合哪種已有的基于細節(jié)點指紋匹配方法并沒有直接關系?？梢灶A見，將所挖掘的未匹配細節(jié)點信息和各種已有的細節(jié)點匹配方法融合，可以在不同程度上提升識別的性能。

圖4 FVC2000數(shù)據(jù)庫上各方法的ROC曲線Fig.4 ROC curves of different methods on FVC2000

圖5 FVC2002數(shù)據(jù)庫上各方法的ROC曲線Fig.5 ROC curves of different methods on FVC2002

圖6 FVC2004數(shù)據(jù)庫上各方法的ROC曲線Fig.6 ROC curves of different methods on FVC2004

5 結 論

（1）突破了指紋識別中未匹配細節(jié)點屬于無用信息的思維定勢，提出了挖掘和利用未匹配細節(jié)點中所包含的區(qū)分性信息，從而提高指紋識別系統(tǒng)性能的新思路。

（2）基于同源指紋匹配和異源指紋匹配中未匹配細節(jié)點的成因和特點不同，定義和提取了4個方面的特征，實現(xiàn)了對未匹配細節(jié)點中區(qū)分性信息的有效挖掘。

（3）將在未匹配細節(jié)點中提取的區(qū)分性信息作為輔助特征，通過在得分級上與一種已有的基于細節(jié)點的匹配算法進行融合，有效提升了指紋識別系統(tǒng)的性能，驗證了未匹配細節(jié)點中確實存在可以利用的區(qū)分性信息。

［1］He X，Tian J，Li L，et al.Modeling and analysis of local comprehensive minutia relation for fingerprint matching［J］.IEEE Transactions on Systems，Man，and Cybernetics—Part B：Cybernetics，2007，37（5）：1204-1211.

［2］Feng J.Combining minutiae descriptors for fingerprint matching［J］.Pattern Recognition，2008，41（1）：342-352.

［3］Chen F，Zhou J，Yang C.Reconstructing orientation field from fingerprint minutiae to improve minutiae matching accuracy［J］.IEEE Transactions on Image Processing，2009，18（7）：1665-1670.

［4］Jain A K，F(xiàn)eng J.Latent fingerprint matching［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（1）：88-100.

［5］Cao K，Yang X，Chen X，et al.A novel global feature for minutiae-based fingerprint matching［J］. Pattern Recognition Letters，2012，33（10）：1411-1421.

［6］Paulino A A，F(xiàn)eng J，Jain A K.Latent fingerprint matching using descriptor-based hough transform［J］.IEEE Transactions on Information Forensic and Security，2013，8（1）：31-45.

［7］Zhao Q，Zhang Y，Jain A K，et al.A Generative model for fingerprint minutiae［C］∥In Proc International Conference on Biometrics（ICB），Madrid，Spain，2013：1-8.

［8］Wand Y L，Ning X，Yin Y.A new fingerprint matching algorithm［J］.Journal of Image and Graphics，2003，8（2）：203-208.

［9］Feng J，Ouyang Z，Cai A.Fingerprint matching using ridges［J］.Pattern Recognition，2006，39（1）：2131-2140.

［10］Jain A K，Prabhakar S，Hong L，et al.Filterbankbased fingerprint matching［J］.IEEE Transactions on Image Processing，2000，9（5）：846-895.

［11］Yang J C，Park D S.A fingerprint verification algorithm using tessellated invariant moment features［J］.Neurocomputing，2008，71（10-12）：1939-1946.

［12］Queka C，Tana K B，Sagarb V K.Pseudo-outer product based fuzzy neural network fingerprint verification system［J］.Neural Networks，2001，14（3）：305-323.

［13］Labati R D，Genovese A，Piuri V，et al.Contactless fingerprint recognition：A neural approach for perspective and rotation effects reduction［C］∥IEEE Workshop on Computational Intelligence in Biometrics and Identity Management（CIBIM），Singapore，2013：22-30.

［14］Huttenlocher D P，Klanderman G A，Rucklidge W J.Comparing images using the Hausdorff distance［J］.IEEE Trans Pattern Anal Mach Intell，1993，15（9）：850-863.

［15］Ren C，Yin Y，Ma J，et al.A novel method of score level fusion using multiple impressions for fingerprint verification［C］∥IEEE Conference on System，Man and Cybernetics Society（SMCS），San Antonio，TX，2009：5196-5201.

［16］Ross A，Jain A K，Reisman J.A hybrid fingerprint matcher［J］.Pattern Recognition，2003，36（7）：1661-1673.