基于中心點的自適應匹配算法

1、基于中心點的自適應匹配算法吳愛燕1吳愛燕（1980-），河北衡水人，漢族，碩士研究生。通訊地址：河北科技大學（中）研究生院2002級1班，聯(lián)系電話E-mail: way_yijun，魏世澤2，王偉3（1,3 河北科技大學信息工程學院，河北石家莊 050051；2 河北科技大學現(xiàn)教中心，河北石家莊 050051）摘 要：隨著指紋識別技術的廣泛應用，人們對指紋匹配速度和精度的要求越來越高。為了滿足用戶的需求，研究人員提出了許多優(yōu)秀的匹配算法，其中點匹配算法是目前研究較廣泛的一種算法。由于指紋錄入時產(chǎn)生旋轉(zhuǎn)、平移和非線性形變，一般在進行精確的匹配之前先將指紋進行校正。切線校

2、正算法簡單，有利于解決指紋錄入時產(chǎn)生的旋轉(zhuǎn)和平移，提高匹配速度。在點匹配算法中，利用特征點的方向信息和坐標信息進行匹配，同時采用自適應閥值法，對指紋錄入時產(chǎn)生的非線性形變具有較好的魯棒性，可以提高識別率。關鍵詞：指紋識別; 匹配; 校正; 切線; 中心點; 三角點1. 引 言人的指紋具有唯一性和終身不變的穩(wěn)定性。因此，一直以來指紋被公認是可靠的物證和身份鑒定的可靠依據(jù)。指紋匹配是自動指紋識別系統(tǒng)（AFIS）的核心研究內(nèi)容之一，它在指紋特征提取之后，是自動指紋識別的最后一步，也是非常關鍵的一步。指紋匹配要解決的問題是對從兩幅給定指紋圖像中提取的特征信息進行匹配，判斷兩枚指紋是否來自同一個手指。由

3、于一些客觀因素的存在，如：指紋錄入時的隨機性、磨損嚴重或受到不可恢復的意外傷害、特征提取算法的不完善等，使得指紋的匹配技術在提高識別率和識別速度上存在著一定的難度。Isenor等1提出了一種用圖匹配來對兩枚指紋圖像進行匹配的算法。Hrechak等2提出了結構匹配算法。此外，還有Jain等3的串匹配算法，Mital D P等4提出的基于細節(jié)點的匹配算法。但目前最常用的方法是用FBI提出的采用指紋細節(jié)點模型做細節(jié)匹配。它利用指紋脊線的端點和分歧點（如圖1所示）來鑒定指紋。本文在借鑒前人研究經(jīng)驗的基礎上，提出了一種新的校正算法和點匹配算法，在一定程度上增強了指紋識別系統(tǒng)抵抗噪聲和非線性形變的能力，提

4、高了指紋的識別速度和準確率。圖1 脊線的端點和分歧點 2. 基于中心點的自適應匹配算法在實驗中，首先，將輸入的指紋圖像分割成w*w大小的子塊（實驗中取w=16）；其次，求取每塊指紋圖像的方向信息，方向信息的計算采用文獻3提出的公式法，其中采用soble算子計算梯度，采用5*5低通濾波平滑塊的方向信息；然后，利用方向場圖像的Poincare 索引來檢測指紋圖像中的特征點（包括中心點和三角點），其中對圖像中的每個像素都用一個數(shù)字化的閉曲線計算Poincare索引，實驗中設計了一條13個像素點的閉曲線；最后，根據(jù)中心點和三角點的信息給指紋分類，待識指紋首先根據(jù)類型、中心點和三角點的信息進行粗略匹配，

5、然后進行校正，最后進行精確匹配。預處理、特征提取和多級索引不是本文討論的內(nèi)容，因此不做詳細介紹。在指紋細節(jié)匹配中,如何選擇可靠的基準點對一直是個難題,如果將所有可能的點對分別當作基準點對來計算又存在計算量太大的問題。在文獻5提出了一種限界盒的匹配算法，該算法在選取基準點對時引入了脊線信息，大大減少了可能的基準點對的數(shù)目?？s小了計算量，提高了匹配速度；同時在匹配時引入限界盒思想，提高了匹配精度，具體算法詳見文獻5。本文在借鑒其經(jīng)驗的基礎上，提出了一種基于中心點的自適應匹配算法。我們的算法分為兩步：首先用切線校正算法將指紋的坐標信息轉(zhuǎn)換到極坐標系下，然后再進行匹配。在六類指紋中混合形指紋十分罕見，

6、可以直接用其中心點和三角點的個數(shù)進行匹配，弓形指紋沒有中心點，因此不適用該基于中心點的校正、匹配算法，但弓形指紋也較罕見，因此對匹配的速度和精度影響甚微。對于弓形指紋匹配算法，本文在最后闡述。對于其他的四類指紋（尖拱形、左旋形、右旋形、渦形）的匹配方案如下所述。2.1極坐標系下基于中心點的切線校正算法首先，建立極坐標系。1) 取指紋的中心點作為坐標極點；2) 定義與中心點方向（渦形指紋任取其中一個中心點即可）垂直的方向作為中心點的切線方向，該垂線為中心點的切線。將該切線作為極軸，切線方向即極軸的正方向。如下圖所示：圖2 切線圖然后，運用公式(1)進行坐標轉(zhuǎn)換。=+ (1)其中，為直角坐標系下指

7、紋中心點的坐標，為直角坐標系下指紋特征點的坐標，為校正后的指紋特征點坐標，為指紋中心點的切線與直角坐標系下X軸的夾角（夾角小于）。無論指紋在錄入時發(fā)生怎樣的旋轉(zhuǎn)和平移，相對一幅指紋圖而言，以中心點為基準點的相對坐標是不變的，因此采用該校正坐標系對指紋圖像進行校正，有效的解決了指紋錄入時的旋轉(zhuǎn)和平移問題。對指紋錄入時發(fā)生的非線性形變，本文在匹配算法中采用了自適應閥值法進行了有效地解決。2.2 基于中心點的自適應匹配算法指紋的局部特征有很多種，例如：脊線的端點、分歧點、孤立點、小橋、小棒、小孔、毛刺等。各種特征出現(xiàn)的概率并不相等，許多特征是罕見的，其中端點出現(xiàn)的概率最高，其次是分歧點。一般的指紋識

8、別技術選取這兩種特征點足以描述指紋的一般性，因此本文選取端點和分歧點，參見圖1。指紋圖像經(jīng)過校正后，進入最后精確匹配階段。本文設計了一種新的細節(jié)匹配算法，以坐標極點（即中心點core）作為基準點，將其周圍最近的36個特征點與其連接，構成36個特征矢量。在算法中取五個參數(shù)，表示一幅指紋圖像檢測到的端點的個數(shù)，表示檢測到的分歧點的個數(shù)，表示一個特征點到坐標極點的歐氏距離，表示一個特征矢量與極軸的夾角（夾角小于），表示一個端點的方向角或一個分歧點在兩脊線上的方向角之差。根據(jù)公式(2)，(3)進行初步匹配，如果待識指紋和模板指紋同類特征點的個數(shù)相差超過允許限度值，則視為其不匹配。 (2) (3)模板指

9、紋特征序列表示如下：；待識指紋特征序列表示如下：，特征序列中的特征值按升序存放。其中，。模板指紋的某一特征點與待識指紋的某一同類特征點的相似度用f_score表示，模板指紋的特征序列與待識指紋的特征序列的匹配度用w_score表示。在公式(2)和(3)同時成立的前提下，判斷，如果超過了某一臨界值，則視兩枚指紋匹配，否則為不匹配。由于非線性形變一般在一個特定的區(qū)域內(nèi)較大,然后非線性地向外擴張。當特征點的極徑（即特征矢量）較大時，極角較小的改變就會造成特征點位置較大的變動；相對而言，當特征點的極徑較小時,小的形變就可以造成大的極角（即夾角或方向角差）的改變,而特征點位置的改變較小。參見圖3所示A變

10、換到A，與B變換到B改變的角度是相同的，但A的位移變換要大于B的位移變換；而C點變換到C，與A變換到A位移的變換是相同的，但C變換的角度要大于A。相對大的位移變化可能會造成極徑相對較大的變化，因此，我們在借鑒文獻5限界盒的思想上，設計了自適應閥值，用如下公式計算臨界值。 其中圖3 位移與角度變換關系圖當特征矢量低于某一值時，限界值可視為常量，不再隨著特征矢量的變化而變化即。對于弓形指紋，由于這類指紋沒有中心點core，因此，我們采用文獻5提出的尋找基準點對方案，對每一對滿足5的基準點對首先進行切線校正；然后進行匹配，校正和匹配方案均如前所述；最后選擇各基準點對的最大值，如果超過了某一臨界值，則

11、視為匹配，否則視為不匹配。3. 實驗結果我們首先在FVC2000公布的指紋庫DB1上，按照FVC2000的測試標準6，對本文的算法和傳統(tǒng)確定基準點對算法作了實驗，并進行了比較，實驗結果見表1。所有的實驗均在PIII1000MHZ微機及RedHat Linux平臺下實現(xiàn)。測試標準EER(%)、EER*(%)、ZeroFMR(%)、ZeroFNMR(%)詳見文獻6，在此不再贅述。實驗時間用檢索時間來衡量兩個算法，檢索時間包括自特征提取后的一級匹配時間、二級匹配時間、最后精確匹配時間、及指紋圖像的輸出時間。表1 在FVC2000數(shù)據(jù)庫DB1上的測試結果AlgorithmEER(%)EER*(%)Ze

12、roFMR(%)ZeroFNMR(%)確定基準點對算法3693691925100本文算法3713711903100兩種算法的ROC曲線比較如圖4所示。圖4 在FVC2000的DB1上兩算法的ROC比較確定基準點對算法的平均檢索時間為0.46183s，本文算法的平均檢索時間為0.32215s。4. 結論在傳統(tǒng)的校正算法中，待識指紋需與模板指紋一一比對尋找基準點對，本文提出的極坐標系下基于中心點的切線校正算法在一定程度上避免了這一繁瑣步驟，并有效地解決了旋轉(zhuǎn)和平移問題。在基于中心點的自適應匹配算法中，我們采用歐氏距離和方向角雙重確定特征點的位置，特征點的方向角（或方向差角）與特征矢量和極軸的夾角雙

13、重確定了特征點所在脊線的局部方向信息，以及特征點所在脊線與中心點所在脊線的局部方向關系；自適應閥值法的引入，有效地解決了非線性形變問題；特征點集采用升序存儲結構，有助于減小算法的復雜度。因此，該匹配算法用于三級檢索機制有利于提高檢索的速度和準確率。但該方法對中心點檢測要求較高。不過，目前指紋匹配算法一般都需要先定位中心點和三角點，再進行分類，若中心點檢測不準確，匹配的第一步指紋類型的判斷就會出錯?，F(xiàn)有指紋匹配算法證明目前中心點的檢測算法可以滿足指紋分類、匹配的要求。實驗證明，在中心點檢測較準確的前提下，該算法對比于其他算法確實進一步提高了指紋的檢索速度和準確率。參考文獻：1 Isenor D

14、K,Zaky S G. Fingerprint identification using graph matching.Pattern Rcognition,1986,19(2):pp.113-122.2 Hrechak A K,Mchugh J A.Automated fingerprint recognition using structural matching. Pattern Rcognition, 1990, 23(8): pp.893-904.3 Jain A,Hong L,Bolle R.On_line fingerprint verification. IEEE Trans

15、on Pattern Analysis and Machine Intelligence, 1997,19(4):pp.302-313.4 Mital D P,Khwang E.An Automated Matching Technique for Fingerprint Identification. First International Conference on knowledge-based Intelligen Electronic Systems,1997，05：pp. 21-23.5 pp. 946-956。6 .Autoadjust Matching Arithmetic B

16、ased on Core pointWU Aiyan1, WEI Shize2, WANG Wei3(1,3 Computer Science and Project Institute, Hebei Science and Technology University, Shijiazhuang, Hebei Province 050051, China;2 Modern Education Center, Hebei Science and Technology University, Shijiazhuang, Hebei Province 050051, China)Abstract:

17、With the wide use of the fingerprint recognition, people bring forward higher request to fingerprint matching rate and accuracy gradually. Researchers have put forward much excellent matching arithmetic to satisfy user need. Now, the minutiae matching arithmetic is researched widely. When a fingerpr

18、int is taken, it usually has rotation, translation and transformation, so a fingerprint commonly is first adjusted before matching. The tangent adjusting arithmetic is simple, and it makes for solving the problems of fingerprint rotation and translation, and successfully improves matching rate. The minutiae matching arithmetic that uses