基于二值圖像中心點的指紋分類算法

摘 要：指紋的自動分類對于提高檢出速度和識別率有重要的意義。有效地利用指紋的紋理結構和紋理方向等固有信息，可以提高指紋的分類類別。基于二值指紋圖像進行分類不完全依賴中心點定位的準確性，避免了利用三角點的干擾信息，應用脊線追蹤算法進行指紋分類，賦予了中心脊線方向連續的變化，可以將指紋自動分類算法提高到34類。

關鍵詞：指紋分類;二值圖像;中心點;脊線追蹤

中圖分類號：TP391．41 文獻標志碼：A

文章編號：1001-3695(2008)07-2190-04

Fingerprint classification method based on binary image and core

CHEN Dahai1，2，HAN Songfeng1，JIANG Tao3，ZHAO Bo2



(1.CAMA(Luoyang)Electronics Co. Ltd，AVIC Ι， Luoyang Henan 471000， China;2.Luoyang Reform Development Committee， Luoyang Henan 471000，China; 3.Staion of Computing Centre， Headquarters of the Third General Staff， Beijing 100080， China)



Abstract:Fingerprint automated classification largely contributes to improving identification rate and detecting speed. Making an effective use of intrinsic fingerprint features like texture structure and texture orientation can increase the total of categories being classified. Classifying based on binary fingerprint image incompletely depended on accuracy of core， avoiding the interferential information of using the delta. Applying the ridge following method to classify fingerprint could follow the change of fingerprint ridge orientation.Fingerprints could be classified into 34 categories.

Key words： fingerprint classification; binary image; core; ridge following



指紋自動識別系統(automated fingerprint identification system， AFIS)已在公安、金融領域得到廣泛的應用。近年來，以指紋為代表的生物特征識別技術引起了人們的廣泛關注^[1]。在各類AFIS中，指紋識別常常需要在大規模的數據庫上進行計算。如果沒有一種有效的數據庫分類機制，輸入的指紋圖像將不得不同數據庫中大量的指紋數據逐一進行比對，系統工作將非常繁重。為了縮短搜索時間和降低計算的復雜度，必須對指紋進行分類。這樣查詢只需在指紋數據庫中的一個相應子集中進行，從而節省了運算時間并降低了運行復雜度。數字指紋的分類是相對最難突破的一個不可或缺的重要環節，它的好壞直接影響著整個識別系統的性能。

指紋分類技術主要包括計算機圖像處理和模式識別兩方面的內容。該技術可以看做指紋在大尺度下的粗略匹配。輸入指紋首先被劃歸為預先已定義好的某一類，而后在更精細的尺度上進一步分類，然后在某一級類中進行精確的指紋比對。目前指紋分類算法通常有：根據采用的理論方法劃分，通常劃分為統計方法^[2，3]、結構方法^[4，5]、人工神經網絡方法^[6]等；另外，K.Karu等人^[7]利用core點和delta點進行指紋分類； B.Moayer等人^[8，9]則使用了句法模式識別的方法對指紋進行分類。

普遍來看，現有指紋分類算法大都存在兩個問題，即分類速度較慢和分類準確率不高。從分類方法來看，指紋分類主要趨向于利用指紋自身的紋理特點和適用于大庫指紋識別。相對利用方向圖和奇異點的分類算法較多^[10]， 將通常能夠分為5~7類的識別算法推進到了12類，但是這類算法高度依賴方向圖，可能導致中心點確定的不準確，三角點出現偏離。如果指紋奇異點區域模糊或殘缺，將會導致檢出錯誤。當前利用脊線追蹤算法進行指紋分類的也比較多^[11]，但是這類算法跟蹤的紋線太多，記錄的信息量太大，并且多以紋線的曲率變化值為依據，容易受變性干擾。本文提出了一種新的基本結構的指紋分類方法，采用脊線跟蹤算法，沿著二值指紋圖像的中心點向兩邊進行搜索，依據延續的脊線方向變化，嚴格按照指紋學^[12]的分類方法來計算，實現指紋的三級分類。通過實驗可以看出，本文的一級分類將指紋分為4類，二級分類把指紋推進到了10

類，三級分類可以分出34類，且本文的算法具有很好的適用性。

1 指紋圖像的分類算法

對于灰度指紋圖像，可以通過預處理算法得到二值指紋圖像，也可以采用直接二值化算法后得到平滑的二值指紋圖像^[13，14]。二值圖像的中心點算法，本文采用文獻[15]的算法，但不同的是基于二值圖像的計算量顯然要小得多。算法的流程如圖1所示。



1．1 中心線提取及細化算法

中心線提取（圖2）采用方向優先算法來提取出中心線的大致走向。由于中心點已經確定，并且其位置正處在所要提取的中心線的曲率最大處。相對于它來說，中心線的走向大致就可以僅僅分為左支和右支。提取走向時就左支、右支分開提取。



對于每一支的提取方法是一樣的，只是方向的優先級有所不同而已。這里以左支的提取為例：

a)定義一個大小為3×3的窗口，令其中心落在中心點上。

b)按照“左—左上—左下—上—下—右—右上—右下”的優先順序在窗口內尋找下一個相鄰點。若其鄰域內沒有脊線上的點（即沒有值為1的點了），就結束搜索；否則轉向下一步。

c)將上一步搜索到的點作為窗口的中心，返回b )繼續進行搜索。這樣的優先級的好處是可以保證搜索時不回頭，特別是不會向右進行搜索，使提取出來的紋線一定是中心線上的左支。

右支的方向優先順序為“右—右上—右下—上—下—左—左上—左下”。搜索完成兩支合并，并采用形態學細化算法即可完成。

1．2 中心線分支的跟蹤與離散

1．2．1 中心點重定位

先前的中心點是定位在了中心線上，而當時的中心線并不是細化后的單像素線條。所以并不能保證先前的中心點就一定會在細化后的中心線上。需要進行中心點的重定位。本文中使用了最為簡單但十分有效的方法：

計算細化后中心線上每一個點到先前中線點的歐式距離，然后比較找到距離最短的點，該點便被作為新的中心點。

1．2．2 中分支的跟蹤記錄

分支的跟蹤有兩個目的：a)按順序記錄下每一個分支的所有點，這樣即使離散化后也不會影響到點之間的相對順序，而且在計算點的方向時，需要用到相鄰點的位置關系，按順序記錄可使點之間的位置關系變得十分簡單；b)有效地去除旁支，這些所謂旁支是中心線上的有用信息，是二級分類的重要憑據，但對建立方向向量從而進行一級分類的干擾很大，所以在跟蹤記錄遇到分支時，應該選取走向和先前點更為接近的分支。算法的流程圖如圖3所示。



1．2．3 分支的離散化

如果直接在兩條分支上進行方向的計算，將會引來兩個問題：即計算量相對較大；細化的中心線本身并不理想，會有很多毛刺、凸起凹陷和鋸齒狀的地方，這些地方會極大地影響方向的計算，使方向向量產生波動，使分類變得極為困難。離散化便能夠減少計算量，同時也能部分地避免一些紋線本身的缺陷。經過實驗，本文將離散化步長取為5。

1．3 方向向量與切線角度向量

在細化中心線離散后的前提下，筆者計算了每一個點的切線方向，它與下一相鄰點的連線方向，并根據兩個方向間的關系生成該點相應的方向向量元素。最終兩條分支的方向向量以及由各點的切線角度組成的切線角度向量為一級乃至二級分類提供了有力的工具，它們也是實現指紋的二級分類最為核心的步驟。

1．3．1 紋線上點的方向劃分

以右支為例。沿著它的走向，可以做出某一點的帶方向切線與法線，如圖5所示。



同樣也可以將其看成是一個沿著右支移動的坐標系。在這個坐標系下，連接原點（即當前點）與下一個點可以形成一個向量。筆者將坐標的第一象限稱為外，右支上的外就稱為右外；坐標的第四象限稱為內，右支上的內就稱為右內。如果原點與下一點的連線落在外，就將該向量稱為外向量，右支上的稱為右外向量；同理，落在內的向量稱為內向量，右支上的稱為右內向量。對于左支，有類似的定義。

從上述分析可看出，如果能記錄下一條分支上點的向量類型，那么就可以通過對其分析進行一級分類。這樣的記錄分支上點的向量類型的一維矩陣，稱為該分支的方向向量。

1．3．2 圖像中角度的計算與轉換

也可以將它看成是這樣一個坐標系，其坐標值(x，y)是離散量，并且這些離散坐標使用的是整數值，另外它的原點定義在(x，y)=(0，0)處。沿圖像第一行的下一坐標值為(x，y)=(0，1)，依此類推。所以上述的圖像f(x，y)可以很自然地表示成這樣的矩陣：

相應地，實際應用的坐標系統的原點是(r，c)=(1，1)。這里的r表示行，c表示列。

向量角度的計算:

先計算兩點連線的斜率，再通過反三角函數計算連線的角度。然而，這里兩點的連線是有方向的，即它是個向量，起點是當前點，終點是分支順序記錄的下一個點；另外θ=cot k是一個第一象限和第四象限的單調函數，并不能包含所有象限。因此，文中作了如下調整，以使向量的角度能映射到所有象限：

當該向量在第一象限時，θ=cot k；

當該向量在第二或第三象限時，θ=180°+cot k；

當該向量在第四象限時，θ=360°+cot k。

如果算出的角度超過了360°，那么就要對其進行360°的模除運算。如果計算出的角度成了負值，那么就給它加上360°。

綜上所述，就是要將角度映射到0，360°」中，這為角度的比較帶來極大的方便。

這樣便實現了在圖像矩陣坐標系下向量角度的計算。

1．3．3 方向向量元素的定義及算法描述

方向向量的元素有三種取值-1、0和1。

無論是左支還是右支，只要當前點的切線向量角度大于其指向下一點的連線向量角度，那么該點對應的方向向量元素為-1；反之，該點對應的方向向量元素為1；如果切線向量和它指向下一點的向量恰好重合，那么它對應的元素為0。

左右支的定義和方向向量元素的定義兩者一起，才能夠實現方向向量的意義化，也就是說才能確定當前點指向下一點的向量到底是內向量還是外向量。

1．3．4 生成方向向量和切線角度向量

1)當前點連線向量的角度

連線向量就是形當前點指向分支中跟蹤記錄的下一點的向量，以后均簡稱為連線向量。根據前面所討論過的角度計算方法，便能得到該連線向量的角度。

2)當前點切線向量的角度

先算出當前點與其兩個相鄰點連線向量的角度，然后算出這兩個角的均值，即確定出圖6所示的角的平分線。該平分線便是當前點的法線。



為了確定當前點的切線向量的角度，應該比較當前點指向分支中跟蹤記錄的下一點的連線向量的角度與法線的角度。如果法線向量的角度大于連線向量角度，那么將法線向量角度減去90°，便得到切線向量的角度；反之，將法線向量角加上90°得到切線向量的角度。用tangent來保存相應分支點的切線角度。

3)方向向量元素的生成

方向向量元素的生成取決于1.3節中連線向量角和切線向量角的比較。



4)方向向量的平滑處理

由于中心線自身的缺陷，可能會使細化后的中心線出現凹陷、凸出或者波浪形的地方。對于理想的紋線，如弓形紋的一支，筆者期望方向向量中僅出現一次符號的轉變，如[1 1 1 0 0 1 1 -10-1 -1]（方向向量中的0不起任何實際作用）。而陷和凸出的地方會使方向向量出現突變，如[1 1 1 0 -1 1 0 1 0 -1 -1 -1 0 -1 -1 -1]中的第五個元素；而波浪形的地方會使方向向量出現抖動，如[1 1 1 0 -1 1 -1 1 -1 0 1 -1 0 -1 -1 -1 -1]中第五到第九個元素。這會對分類造成嚴重的影響，所以本文設計了算法，用來將方向向量中的突變元素、抖動元素刪除。方向向量只是一個用來分類的特征向量，刪除這些無意義的點并不會影響其相應分支的特征。

算法的思路如下：

a）設一累加器s，賦初值0。

b）比較當前元素和下一元素，若是同號，則s賦0；若是異號，則s累加1。0值不起實際作用，因而0與任何元素都看做同號。

c）檢查s，若值＜2（表示元素符號只改變了一次，或者沒有改變），則將當前點向后移動一位，返回b）繼續檢測比較；若值＝2（表示元素符號已連續改變了兩次），則該元素就是突變元素，刪除該元素，將當前點向前移動一位，方向向量總長度減1，返回b）。

d）當前點的序號不再小于方向向量總長度時終止。

方向向量的意義化：方向向量中元素的取值0，1和-1僅僅表示切線向量角和連線向量角的比較情況。若要看出它的實際意義，就必須與分支定義結合起來。也就是說，當marker的值是0時（即該支是右支），方向向量中的-1則表示是內向量，簡稱為右內，1表示右外；

當marker的值是1時（即該支是左支），方向向量中的-1則表示是外向量，簡稱為左外，1表示左內。

這樣的記法不甚方便，所以首先將左支的全部信息標以序號1，即分支標志符marker_1，分支方向向量orientation_1;右支類似的標以序號2。其次，用右支的標志符0減去其方向向量中的每一個元素，這樣就可以使方向向量中元素的意義統一起來：1表示內向量；-1表示外向量。同樣，切線角度向量也標以序號，tangent_1和tangent_2。左右支僅僅依靠標志符的序號就能予以區別了。

1．4 基于方向向量和切線角度向量的二級分類

有了前面的所有工作，特別是方向向量和切線角度向量的生成，對指紋進行分類將變得相對簡單。顯而易見，分類分為兩個步驟，也就是所謂的一級分類和二級分類，如圖7所示。

1．4．1 一級分類

對于一級分類，僅需分出弓形紋、斗形紋、箕形紋即可。

對于弓形紋的左支來說，由于它是以中心點作為起點，開始的幾個點的對應向量都是左內向量（即方向向量中為“1”，為了表述方便，后文中仍將以文字來描述內和外），之后必然會從某一點開始所對應的向量變成左外向量；而其右支也會有從右內向量到右外向量的轉變過程。



對于箕形紋，以右箕為例，它的右支類似于弓形紋的右支，點的對應向量會從右內向量變到右外向量，而它左支上點的對應向量則一直是左內向量；右箕有類似的情況。總體來說，箕形紋的一支會出現從內向量到外向量的轉變，而另一支則會一直是內向量。

對于斗形紋來說，情況稍稍有些復雜，但同時借助于方向向量和切線角度向量也可將其鑒別出來。當兩個分支上點的對應向量都是內向量時，或當某一條分支的切線角度轉過了360°時，就將該指紋分類到斗形紋。

1．4．2 二級分類

二級分類是直接建立在一級分類結果基礎上的，對每一種分類在進行細化。它需要利用很多不是中心線上的特征。因而，將整幅圖像進行細化，后面的操作都是在這樣的圖像上進行，不再專門說明。

弓形紋還可分為弧形和帳形。帳形就是中心有支撐線的弓形；弧形就是中心沒有支撐線的弓形。那么，只要能夠檢測出這條支撐線就可以將兩者區分開。本文的做法是：以中心點的法線為對稱軸，切線為寬所在的直線，建立一個長方形區域。 沿著長方形的長度方向依次統計脊線谷線的交替次數，可以看到弧形紋頻繁交替，而帳形紋幾乎沒有變化。若交替次數超過一定閾值（該閾值一般可取五個像素寬度），則該指紋是弧形紋，否則是帳形紋。

箕形紋分為左箕和右箕。根據左右支的方向向量就可以區分：左箕左支的方向向量從內向量轉變到外向量，而右支的方向向量始終都是內向量；右箕則剛好相反。

斗形紋分為六類，即環形斗、囊形斗、螺形斗、絞形斗、曲形斗和雙箕斗。斗形紋的二級分類結構是樹狀的。

第一層：對前面所作的分支跟蹤記錄進行檢測，由于環形斗的中心線是一個封閉的環，分支記錄時中心點會重復。根據這一點，便可以將環形斗分出來。如果不是這種情況，則進入第二層。

第二層：對兩條分支的方向向量進行檢測。如果兩條分支的方向向量都只有內向量，那么就可能是囊形斗、螺形斗或者絞形斗；如果只有一條分支的方向向量都是內向量，那么則可能是曲形斗或者雙箕斗。

第三層：對于第二層的第二種情況，為了區分曲形斗和雙箕斗，筆者發現兩者的中心線幾乎沒有什么區別。惟一的區別就在于雙箕斗的中心線里套有兩個箕形紋。所以取中心點的法線，并沿著法線找到與中心點相鄰的兩個點，計算兩個點到中心點的距離。曲形斗的兩個距離值都基本上與脊線間的距離吻合，而雙箕斗的一個距離值則遠遠大于脊線間的距離，這樣便可將兩者分開。對于第二層的第一種情況，筆者發現，螺形斗和絞形斗的其中一條分支的切線角可以繞紋線轉過180°，甚至360°，而囊形斗則不可能，因而通過對切線角向量的檢測分析便可將囊形斗區分出來。

第四層：只剩下螺形斗和絞形斗了。可以利用區分弓形紋（帳形弓和弧形弓）的長方形區域算法，找到同向旋轉的另一個起始點，便將兩者區分開。

1．4．3 三級分類

三級分類是建立在二級分類的基礎上，對每一種分類繼續細化。對于弓形紋的帳形和弧形，仍然利用中心線內的長方形。長方形過中心點軸線的傾斜方向構成向左或向右的傾角，又可以把帳形和弧形分為左傾和右傾。

對于斗形紋，當左右追蹤的兩個方向向量出現互為180°時，彼此方向相反。如果離中心點較近的方向指向右，則該指紋順時針旋轉，定義為正旋；反之，如果離中心點較近的方向指向左，則該指紋逆時針旋轉，定義為反旋。

對于箕形紋，當兩個不同的方向向量追蹤到同一個點時，表示兩條追蹤線合并，定義為閉口箕；反之，追蹤不到同一個點，表示兩條追蹤線分離，定義為開口箕。

2 實驗

在1 000幅指紋庫上進行測試，如果同源指紋被分在同一類別，則認為分類正確，否則認為分類錯誤。測試結果是：一級分類全部正確，無中心點的殘缺、斷指、模糊的15枚指紋被分到其他組中，分類正確率為100%；二級分類中錯誤分類的指紋一共3枚，都是受中心線數的影響，絞形紋和螺形紋的界限不明顯，所以分類錯誤率為3/1 000。三級分類的左右傾、正反旋和開閉口分類均正確。綜合來看，歸入其他類的指紋占全部的1.5%，即拒識率為1.5%，誤識率為0．3%。這樣的分類性能可以說是達到了極高的水平，也完全滿足了指紋大庫分類算法的要求。

3 結束語

基于二值圖像和中心點的指紋分類算法嚴格依照指紋學的定義，模擬指紋專家進行的自動識別技術可以逐級將指紋分類推進。在筆者的研究中，已經把指紋自動分類技術推進到三級34 類，雖然離指紋學的六級分類尚有一定的距離，但較當前的分類算法已有很大的提高。該算法依據二值圖像，二次校正中心點位置，僅提取中心一條線，計算速度快，并且不用三角來分類，具有很好的魯棒性。實驗效果說明，依據方向向量、切線角度向量和分支追蹤記錄方法實現的指紋分類算法完全具有大庫指紋的分類能力。

參考文獻：

［1］

YIN Y L， NING X B， ZHANG X M. Development and application of automatic fingerprint identification technology[J]. Journal of Nanjing Univesity:Natural Sciences， 2002，38(1):29-35.

[2]BOTHA E ，COEZEE L. Fingerprint recognition with a neuralnet classifier[C]//Proc of the 1st South African Workshop on Pattern Recognition.1990:33-40.

[3]CANDELA G T， GROTHER P J， WATSON C I，et al.PCASYS: a pattern level classification automation system for fingerprints，NISTIR 5647[R].[S.l.]:NIST，1995.

[4]GAI Wu，KANG Gewen.Some algorithms based on structures in automated fingerprint identification system[J]. China Measurement Technology，2003，29(5)119-120，142.

[5]YANG Fengrui， CHENG Yu. Recognition approach of fingerprint based on structural classification and graphical matching[J]. Computer Applications，2005(5):1092-1095.

[6]MA Huimin. SU Guangda， HUANG Ruke. A classification algorithm for fingerprint matching in large database[C]//Proc of the 13th National Conference on Neural Network. 2003.

[7]KARU K ， JAIN A K. Fingerprint classifications[J]. Pattern Recognition，1996，29(3):389-404.

[8]MOAYER B ， FU K S. An application of stochastic language to fingerprint pattern recognition[J]. Pattern Recognition ，1976，8:173-179.

[9]MOAYER B，FU K S. A tree system approach for fingerprint pattern recognition[J]. IEEE Trans Comput，1976，C25:262-274.

[10]KAWAGOE M ， TOJO A. Fingerprint pattern classification[J]. Pattern Recognition， 1984，17(3):295-303.

[11]YANG Xiaodong， NING Xinbao， ZHAN Xiaosi，et al. Fingerprint classification method based on ridgefollowing[J]. Computer Engineering，2005，31(7):170-173.

[12]LIU Shaocong. New dactylography [M].Hefei:Anhui People’s Publishing Agency， 1984.

[13]HEN Dahai， GUO Lei， CHANG Jiang，et al Method for fingerprint image binarization using difference[J]. Journal of Computer Application， 2007， 27(1):169-171.

[14]CHANG Jiang， GUO Lei， CHEN Dahai. Fourier Translatebased bandhinder filter of fingerprint image preprocessing [J]. Application Research of Computer， 2007，24（3）：300-301，305.

[15]HU Ronghua，LIU Guoping. Corepoint searching in poor quality fingerprint image[J].Computer Engineering and Applications，2004，40(15):65-66，84.

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