一種基于分叉點脊線相似度的指紋匹配算法

摘 要：研究了一種基于分叉點脊線相似度的指紋匹配算法，利用可靠性較高的分叉點所在脊線的相似程度尋找出可能的基準細節點對；同時為解決基準點篩選受噪聲影響的問題，提出使用基準點與周圍四個特征點組成子集之間的相互關系來確定最終的基準點對和變換參數的方法；最后利用可變限界盒來實現兩枚指紋的匹配。實驗結果表明，本算法可以快速、準確地定位基準點，精確地求取變換參數，能夠正確、快速地實現指紋匹配。

關鍵詞：分叉點； 脊線相似度； 基準點； 可變限界盒

中圖法分類號：TP391 文獻標識碼：A 文章編號：1001-3695(2006)10-0148-03

Fingerprint Matching Algorithm Based on Bifurcation Ridge Comparability

YIN Xinchun， WANG Qiuping， CHEN Chunxia

(Dept. of Computer Science Engineering， Yangzhou University， Yangzhou Jiangsu 225009， China)

Abstract:This paper proposed a fingerprint matching algorithm based on the bifurcation ridge comparability， which found pairs of possible reference minutiae according to the comparability of two ridges on which the highly reliable bifurcation lied. Meanwhile， in order to solve the problem that the reference minutiae filtering would be influenced by noise， a novel method is proposed taking advantage of the relationship between the reference minutiae and the subsets consisting of four neighboring minutiae to determine the final reference minutiae and the transform parameters. And finally the algorithm implemented the fingerprint matching using the variable bounding box. The experiment results indicated that this algorithm could accurately and quickly locate the reference minutiae and precisely acquire the transform parameters， then correctly and quickly perform the fingerprint matching.

Key words:Bifurcation; Ridge Comparability; Reference Minutiae; Variable Bounding Box

1 引言

指紋識別技術是生物識別技術中最重要、應用最廣泛的技術。它利用指紋特征的唯一性和終身不變性識別個人身份，其基本任務就是判斷兩幅指紋圖像是否來自同一個手指。在匹配特征的選擇上，美國FBI提出了端點—分叉點模型，這兩種特征點在指紋中出現的幾率最大、最穩定，易于檢測，而且足以描述指紋的唯一性。通過將指紋圖像表示為細節點方式，一個自動指紋識別問題就轉換為點模式匹配的問題。目前已有很多文獻對指紋匹配算法進行了研究，大致可以分為兩類：①圖形匹配[1~3]的方式，其實質是基于脊線結構或者細節點間拓撲結構的匹配。這類方法對于圖像的旋轉、平移不敏感，對于少量細節點的缺失、少量偽細節點的存在和細節點的定位誤差具有一定的容錯性。②人工神經網絡[4，5]的方法。由于人工神經網絡具有解決模糊問題的優勢，這類算法的容錯性比較好，但事先要經過足夠數量樣本的訓練系統才能正確地進行工作。這類匹配方法不適合于實時的自動指紋識別系統。

本文提出了一種基于分叉點脊線相似度的指紋匹配算法，首先比較了指紋特征點中可靠性較高的分叉點所在脊線的結構，獲取初步的基準點對，然后通過該點與四個鄰近的特征點之間的相互關系進行進一步篩選，以確定匹配基準點對求取變換參數。本算法在一定程度上加快了基準點對的求取，提高了基準點對的可靠性，使得整個匹配算法的速度有所提高；同時該方法利用多點來確定變換參數，使得變換參數更為精確。

2 匹配算法

基于分叉點脊線相似度的匹配算法主要是在圖像細化結束后對指紋特征點進行離散采樣，然后根據采集到的信息確定基準點進行指紋的匹配。該算法具體包括以下幾個過程：

（1）特征點選取及脊線離散采樣

在每幅指紋圖像中均存在許多特征點，如果對所有特征點所在脊線均進行離散采樣，就會使算法較為復雜和煩瑣，特征點存儲的數據量較大，因此就存在如何選擇特征點的問題。而在實際應用中，考慮到從指紋圖像中提取的分叉點可信度要高于端點，所以選擇分叉點所在脊線進行離散采樣。

由于分叉點有三條紋線與其相連，所以我們首先選擇與相鄰兩脊線分支夾角和最大的脊線作為采樣脊線，我們稱該脊線為脊線1，脊線信息用該脊線上的采樣點來表示。我們從特征點開始進行跟蹤，每隔D個像素采樣一次，記錄下該采樣點與特征點的歐式距離di和連接該點與對應特征點的直線與對應特征點的方向夾角αi，沿著脊線1連續采樣N1次，如果采樣過程中遇到其他特征點則放棄該分叉點。對于其他的兩個脊線，我們分別稱為脊線2和脊線3，同樣每隔像素D采樣一次，記錄下采樣點的坐標（xk，yk），沿著脊線2、脊線3均連續采樣N2次，如果采樣過程中遇到其他特征點，則放棄該分叉點。圖1給出了分叉點對應的脊線以及脊線上采樣點的例子。

經過上述過程后，對每個特征點以如下形式進行存儲：終結(xi，yi，θi，ti)，分叉點(xi，yi，θi，ti，d1，α1，…，dk，αk，x1，y1，…，xm，ym，x1′，y1′，…，xm′，ym′)。其中，（xi，yi）為特征點的坐標，θi為特征點的方向，ti為特征點的類型，（dk，αk）為脊線1上第k個采樣點到特征點的歐式距離和方向夾角，(xm，ym)代表脊線2上第m個采樣點的坐標，(xm′，ym′)代表脊線3上對應的第m個采樣點的坐標。我們將所有模板圖像中的特征點記為集合P，所有待識圖像中的特征點記為集合Q 。

（2）基準點對的初步確定

將模板圖像集合P和待識圖像集合Q中的所有采樣脊線逐一進行匹配，選擇匹配度較大的幾對脊線上的特征點作為初步的基準點對。

對于模板點集中的點Pi和輸入點集中的點Qj，如果它們均為分叉點且均進行了紋線采樣，則計算兩點所在紋線的相似度。我們定義了Sim_dist，Sim_angle，Sim_triangle來衡量脊線的相似度。

用式（1）來衡量脊線1的差異：

Sim_dist=∑ki=1(|(dPi-λdQi)|×ri)(1)

Sim_angle=∑ki=1(|(αPi-αQi)|×ri) ri=dPi∑kj=1dPj

其中，dPi代表P集合中某分叉點中第i個采樣點到該分叉點的距離，dQi代表Q集合中某分叉點中第i個采樣點到該分叉點的距離，k為脊線上采樣點的個數，λ為圖像的放大系數。

脊線1的相似參數計算完成后，繼續使用如下方法來判斷模板圖像中脊線2、脊線3與待識圖像中脊線2、脊線3的相似度。

分別將原圖和待識圖像中脊線2的點(xm，ym)和脊線3中與之對應的點(xm′，ym′)與特征點組成三角形，衡量兩個三角形的相似度Sim_triangle[m]，如果相似度為真，則Sim_triangle[m]=1；在所有三角形的相似度均判斷完成后，利用式(2)計算出兩條脊線的整體相似度Sim_triangle。

Sim_triangle=1m∑mi=1Sim_triangle[i](2)

判斷三角形的相似程度主要是通過三角形的三條邊的長度來完成，分別計算兩個三角形中三個點兩兩之間的距離，按照從大到小的順序排列，分別記為L1，L2，L3和L1′，L2′，L3′，利用式(3)計算它們的相似度，如果St小于某一閾值Ttri，認為兩個三角形是相似的。

St=13∑3i=1|Li-Li′|(3)

如果這兩條脊線的相似度Sim_dist，Sim_angle，Sim_triangle分別小于某個閾值Td，Ta和Tj，則初步將這兩條脊線上的一對特征點作為基準點對。記錄這對基準點的坐標，然后繼續尋找下一對基準點。如果所有采樣脊線均考察過了仍然沒有找到基準點對，則直接判定這兩幅圖像不匹配，結束指紋匹配程序。

（3）基準點的篩選

對于初步確定的基準點對并不一定都是正確的，還需要進一步篩選。文獻[6]提出在待識圖像和模板圖像中尋找與基準點距離最近的兩個特征點，連同基準點本身各組成一個三角形，通過對三角形相似程度的判斷來對基準點對進行取舍。這種方法對于指紋質量較好的圖像能夠完成正確的匹配，但當采集到的指紋圖像質量很差，此時由于噪聲干擾太強，特征提取算法性能急劇下降，通常會檢測到大量的偽特征點而丟失許多真實的特征點，使得特征點的篩選算法錯誤較多。為了提高算法的容錯性，我們對上述算法進行了改進，采用與該特征點最近的四點組成了多個三角形（圖2），從中尋找出最大的匹配三角形數，并以此為條件求取變換參數。

改進后的相似數及變換參數計算方法如下：

①生成兩個數組A{p1pip2，p1pip3，p1pip4，p2pip3，p2pip4，p3pip4}和B{q1qjq2，q1qjq3，q1qjq4，q2qjq3，q2qjq4，q3qjq4}。其中pxpipy，qxqjqy分別代表兩個基準點與周圍兩個點組成的三角形。

②統計出相似三角形的數目Num及計算出各自的變換參數(△x，△y，△θ)。

Num=0;

For x=1 to Count(A)

For y=1 to Count(B)

If (三角形A[x]與B[y]相似) (B[y].checked=1)

{Num++，

B[y].checked=true;

計算A[x]與B[y]的變換參數△x[num]，△y[num]，△θ[num]

Break;

}

③如果Num小于某個閾值Ts，則刪除該基準點對；否則保留該基準點對，并利用以上計算出的最大相似三角形數來確定該對基準點的變換參數：

Δθ=1Num ∑Numk=1Δθ[k]，Δx=1Num ∑Numk=1Δx[k]，Δy=1Num ∑Numk=1Δy[k](4)

（4）待識圖像調整

在保留下來的基準點對中，選擇其中一對作為基準，根據計算出的橫向平移△x、縱向平移△y以及旋轉角度△θ，利用式(5)對待識圖像進行調整。只有在對待識圖像進行調整后，才能對兩幅圖像中的特征點進行匹配。

xqi

yqi

θqi

1T=cosΔθ-sinΔθ0Δx

sinΔθcosΔθ0Δy

001Δθ

0001 xqi

yqi

θqi

1(5)

（5）特征點匹配

由于指紋圖像的匹配是非精確匹配，即使是一對匹配的特征點對，它們之間也不會完全重合，總是在位置、方向上存在有一定的偏差，所以必須有一定的偏差容忍度。為此，我們采用了可變限界盒的方法[7]，當與細節點的距離較小時，小的形變就可以造成較大的方向差的改變，而距離較大時，方向差的較小改變就會導致細節點位置較大的改變。所以，限界盒的大小和角度應隨距離的改變而動態改變，具體如圖3所示。

如果計算出的匹配點數大于閾值TP，則認為兩幅圖像來自同一枚指紋，匹配通過；否則回到過程（4），再使用其他基準點進行匹配。如果均不能匹配，則認定這兩枚指紋不匹配。

3 實驗結果

為驗證本文所提出方法的性能，我們在內存為256MB的P4 2．8GHz的PC機上用程序實現了上述算法。測試時使用了從50個手指采集的500幅圖像，每個手指采集10個樣本，指紋圖像分辨率為500dpi，大小是256×256pixels。在指紋增強部分，我們采用了Lin Hong等人[8]提出的基于Gabor濾波方法對指紋圖像進行增強；然后利用文獻[9，10]提出的方法去除偽細節特征點。在匹配階段，為了計算拒識率，對每一個特征點集Tij，將它與Tik（j

4 結論

本文介紹了一種基于分叉點脊線相似度的指紋匹配算法，與文獻[7]對所有特征點所在紋線均進行離散采樣、文獻[6]對所有紋線端點所在紋線進行離散采樣不同的是，我們采用了可信度更高的分叉點所在脊線進行離散采樣，既保證脊線采樣的可靠性，又減少了采樣數據的存儲量，使得基準點的選取準確且快速。同時在確定基準點時，為了排除噪聲的干擾，采用了與周圍四個特征點組成多個三角形，從中找出最大的匹配三角形數，并利用這些匹配三角形數求出更加準確的變換參數。大量的實驗已經證明了本算法的有效性，但是如果當指紋質量很差，可匹配的分叉點脊線對較少時，就會出現拒識現象。因此，如何在保證識真率的基礎上，盡可能減小拒識率是需要進一步研究的內容。

參考文獻：

[1]A K Jain， L Hong， R Bolle. Online Fingerprint Verification[J]. IEEE Trans.Pattern and Machine Intelligence，1997，19(4):302-314.

[2]X Jiang， W Y Yau. Fingerprint Minutiae Matching Based on the Local and Global Structures[C]. IEEE the 15th International Conference on Pattern Recognition 2， 2000.10421045.

[3]譚臺哲，寧新寶，尹義龍，等.一種基于指紋中心點的匹配算法[J].南京大學學報（自然科學），2003，39(4):483-490.

[4]漆遠，田捷，鄧翔.基于遺傳算法的指紋圖像匹配算法及應用[J].軟件學報，2000，11(4):488-493.

[5]Vinod V V， Ghose S. Point Matching Using Asymmectric Neural Networks[J]. Pattern Recognition， 1993，26(8):12071214.

[6]王業琳，寧新寶，尹義龍.一種新的指紋匹配方法[J].中國圖像圖形學報，2003，8(2):203-208.

[7]羅希平，田捷.自動指紋識別中的圖像增強和細節匹配算法[J]. 軟件學報，2002，13(5):943-956.

[8]Lin H， Wang Y， Jain AK. Fingerprint Image Enhancement: Algorithms and Performance Evaluation[J]. IEEE Trans. Pattern Analysis and Machine Intelligence， 1998，20(8):777-789.

[9]尹義龍，寧新寶，張曉梅.改進的指紋細節特征提取算法[J].中國圖像圖形學報，2002，7(12):13021306.

[10]Xiping Luo， Jie Tian. Knowledgebased Fingerprint Image Enhancement[C]. Barcelona: The 15th ICPR， 2000.783.

作者簡介：

殷新春(1962-)，男，教授，碩士生導師，博士，主要研究方向為網絡與信息安全、并行與分布式計算;王秋平(1978-)，男，碩士研究生，主要研究方向為網絡與信息安全；陳春霞(1979-)，女，主要研究方向為網絡與信息安全。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文