1、基于連續方向場的多尺度指紋奇異點檢測算法湯婷,孫林森,吳小培安徽大學計算機科學與技術系，合肥 (230039）（）摘 要:本文在連續方向場的基礎上，對經典Poincaré Index公式進行了改進，結合點方向場和塊方向場，提出了一種基于多尺度的指紋奇異點檢測算法。傳統基于點方向場的奇異點檢測精度較高，但是速度較慢，且對于低質量的指紋圖像容易誤判；傳統基于塊方向場的奇異點檢測不會發生誤判，但是精度不高。本文將二者有機結合起來，既實現了指紋奇異點檢測的精度，又避免了誤判現象。關鍵詞:指紋；奇異點檢測；方向場；Poincaré Index中圖法分類號 TP391.411 引 言每

2、個人的指紋各不相同，指紋因具有終生的穩定性、可靠性、可采集性和方便性等突出優點1已經成為個人身份認定的重要手段。因而,自動指紋識別系統(Automated Fingerprint Identification System,AFIS）已成為當前一個重要的研究課題,有著非常廣闊的應用前景2。一般來講，基于計算機的自動指紋識別系統通常由圖像輸入、預處理、特征提取、匹配等幾部分組成。雖然近年來，國內外提出了很多有效的指紋識別方法，但在實際應用中仍然存在一定的問題，特別在如何進一步提高指紋識別的運算速度等方面還有不少有待于提高的地方。為了減少搜索時間和計算的復雜度,必須對指紋進行分類,這樣查詢、匹配只

3、需在指紋數據庫中的一個相應子集中進行,從而節省了運算時間,降低了運算復雜度.所以,指紋分類不僅能夠為大型指紋庫提供重要的索引機制,而且還能夠優化系統的運行,提高AFIS的效率和性能,為AFIS的普及應用奠定良好的基礎3.而指紋分類算法大多是根據指紋模式區（pattern area）4中奇異點(Singular point or singularity)的類型、數目和相對位置等信息來實現的。所以，準確可靠地檢測奇異點的類型、數目和位置，是自動指紋識別系統中的一項關鍵技術。2 傳統算法介紹傳統算法一般有兩種:(1)利用指紋點方向場(point orientation field)6對圖像中所有的點

4、進行旋轉角度差值的計算得到Poincaré Index值5,從而得到奇異點的位置。很顯然,這種做法雖然能夠最終求得奇異點，但由于對所有點進行運算,使得這種算法過于耗時且有時還會漏判.(2)利用指紋的塊方向場(block orientation field)7來計算Poincaré Index值，進而檢測指紋奇異點，而塊方向場的變化是分塊連續的，整體連續過渡性差,精確度不高,不能精確地反映指紋脊線的真實走向，這使得奇異點的定位誤差較大,將會對以后的匹配帶來很大的影響.另外，由于傳統的Poincaré Index只能反映向量場的旋轉角度，而不能完全反映向量場的旋轉方向

5、，而且計算Poincaré Index時只用一條封閉曲線，因而會提取出大量的偽奇異點。 本文結合了點方向場和塊方向場的優點，在此基礎上，提出了基于連續方向場8的多尺度指紋奇異點檢測算法。由于用了點方向和塊方向兩種尺度，因而能有效提高指紋奇異點的定位精度；同時，對Poincaré Index公式進行了改進，改進后的Poincaré Index不僅能精確表示向量場的旋轉角度，而且還能精確表示向量場的旋轉方向;在此基礎上，對指紋連續方向場中的每一點，用大小兩條封閉數字曲線計算Poincaré Index 值來精確定位指紋奇異點.所以，該算法能夠在像素級水平精確

6、定位指紋奇異點(core點和delta點）,精確度達到一個像素，并且，使每個有效的奇異點區域只檢測到一個候選奇異點，有效地解決了低質量指紋圖像奇異點檢測中精確定位和可靠性判斷的難題，為AFIS中高精度的指紋分類、匹配等關鍵技術奠定了良好的基礎。本文第3章介紹了多尺度檢測的具體算法。第4章詳細描述基于多尺度的指紋奇異點檢測算法的實現。第5章給出了實驗結果。最后總結全文。3 基于連續方向場的多尺度指紋奇異點檢測算法3.1 指紋圖像的背景分割 從采集到的的原指紋圖像中分割出有效的指紋區域，是指紋圖像預處理的首要步驟，所有的后繼處理都是針對有效指紋區域進行的。3.2 計算指紋點方向圖本文采用鄰域方向模

7、板法9計算指紋的點方向場,并在此基礎上進一步計算連續方向場8,設P表示輸入的灰度指紋圖像，其大小為M×N，M，N的取值范圍一般由指紋輸入設備的分辨率決定。P(x,y)表示像素點(x,y)的灰度，取值范圍一般是0到255的整數，表示輸入圖像有256個灰度級。將指紋紋線的方向在02之內劃分成8個方向,即以圖像中每個像素點為中心,每隔/8確定一個方向,方向的取值分別為1,2,3,8,具體的方向劃分見下圖:7654387654328211C112234567834567圖1 8方向的9×9方向模板具體計算步驟如下9:（1） 對指紋圖像中的每一點P(x,y),在以該點為中心的9

8、15;9 窗口內，分別計算8個方向上的灰度和Si，Si也叫做該方向上的切縫和, 即對圖1中標有i（ i=1， 2， 3， ， 8； 分別代表8個方向）的位置的像素灰度值求和,然后對灰度和進行平均，得到8個方向的灰度平均值；（2）將這8個平均值按兩兩垂直的方向分成4 組:1和5為一組，2和6為一組， 3和7為一組,4和8為一組，分別計算每組中兩個平均值差的絕對值: （1）其中，i為脊線方向(i=1，2，3，4)；(3)取差值的絕對值最大的兩個方向作為可能的脊線方向,即若imax=ord（） （2）其中:ord(Ai)=i, ord()為取數組(向量）A 的元素Ai的下標i的函數，則方向imax

9、和imax+4 為像素P(x,y)處可能的脊線方向；(4)取imax和imax+4兩個方向中像素灰度平均值與像素P(x,y)的灰度值S比較接近的方向,作為該像素點P(x,y)的脊線方向D(x,y):(3)imax 若|S-|<|S-|imax+4 否則D(x,y)=以此方法分別對指紋圖像中每一個像素點進行處理,便可得到指紋的點方向場D(x,y)。3.3 連續方向場8在計算出指紋的點方向場D(x,y)后， 采用連續滑動的w×w窗口（模板）來對點方向圖D(x,y)進行平滑處理,本文取17×17 的平滑窗口對點方向場中每一點P(x,y)進行平滑，即在以此點為中心的w

10、5;w窗口范圍內，進行方向直方圖統計，具體做法為10:（1）分別統計該w×w窗口內方向值為i（i=1， 2， 2， ， 8，分別代表8個方向）的像素個數Ni；（2）把方向直方圖中峰值所對應的方向（即w×w窗口內方向統計數最大的一個方向） 作為該點P(x,y)的方向O(x,y): （4） 其中: ord(Ai)=i, ord()為取數組(向量)A的元素Ai 的下標i的函數。以此方法分別對點方向場D(x,y)中的每一點進行平滑處理，便可得到平滑點方向場O(x,y),也叫指紋的連續方向場(continuous orientation field)。3.4 對指紋連續方向場分塊將連

11、續方向場劃分成多個不相重疊的圖像塊,大小為w×w,方向值為i(i=1，2，3，8,分別代表8個方向），然后統計每個小塊里方向值為i的像素個數ni；把方向直方圖中峰值所對應的方向（ 即w×w窗口內方向統計數最大的一個方向）作為該塊M(x,y)的方向。塊方向圖是一個矩陣，每個元素都是18。塊方向以塊為單位。4 基于連續方向場的多尺度指紋奇異點檢測算法在求得的指紋分塊后的方向場M(x,y)后,奇異點的檢測主要分以下兩步:4.1 指紋圖像Poincaré Index的計算Poincaré Index法是指紋奇異點檢測最經典、直觀而簡潔的方法，是在指紋方向場中計算

12、Poincaré Index值來檢測指紋奇異點，早在1984年就被Kawagoe和Tojo5用來檢測指紋奇異點。設(x,y)是指紋圖像的方向場,在方向場中的給定點(i,j)的Poincaré Index值計算公式如下:Poincare（i，j）= （5） + if - otherwise(k)= if|<(6) (7)其中,(xk,yk)以給定點(i,j)為中心的具有N 個像素的封閉數字曲線上沿逆時針方向第k 個點的坐標,k =0， 1， 2， ， N-1，在封閉數字曲線上沿逆時針方向遞增。如果Poincaré Index值為1/2， 那么該給定點（i，j）

13、就是core點，若為-1/2,則為delta點。當/2(k)時,(k）=-(k)就大于0,且有0(k）/2,表示當方向場逆時針旋轉一個正角度(k)時，還等價于逆時針旋轉一個正的補角（-(k)）,顯然是不對的，因此，(k)就不能完全反映向量場的旋轉方向，由此計算出的Poincaré Index只能反映向量場的旋轉角度，而不能完全反映向量場的旋轉方向。因此,根據奇異點附近指紋方向變化的規律和Poincaré Index的物理意義，本文對以上經典的Poincaré Index計算公式進行了如下四點改進10:(8)（1）將(k) 的計算公式（6） 中的“-(k) ”改為“

14、(k)- ”，即將公式(6)改為公式(8): (k) if|(k)|</2(k)- otherwise(k)=(k)+ if(k)-/2 這樣， 當/2(k)時,(k)= (k)- 就小于0，且有- /2(k）0， 表示當方向場逆時針旋轉一個正角度(k)時，等價于順時針旋轉一個負的補角（(k)-）,因此，(k)就能精確表示向量場的旋轉方向，由此計算出的Poincaré Index既能精確表示向量場的旋轉角度，又能精確表示向量場的旋轉方向。(2) 對指紋連續方向場O(x,y)中的每一點P(x,y)，我們分別計算兩個Poincaré Index值，所用的封閉數字曲線有兩個

15、：一個是點P(x,y)鄰域的 2×2 矩形數字曲線1，如圖2所示，其周長為 4 個象素；另一個是以點P(x,y)為圓心，半徑為 4 個象素的圓形數字曲線2，其周長為 24 個象素，對應的Poincaré Index值分別記為Poincare1(x,y)和Poincare2(x,y)。取這兩個模板的主要原因是：模板尺寸越小，檢測的奇異點位置越精確，且圖像邊緣處的奇異點越易檢測到，同時計算量也較小；用兩個封閉數字曲線分別計算兩個Poincaré Index值，可以有效地去除偽奇異點，使每個奇異點區域只有一個候選點符合條件，提高了算法的魯棒性，避免了對候選奇異點的后處理

16、過程。(x,y+1)（x+1，y+1）(x,y)（x+1，y）圖2 檢測奇異點使用的封閉數字曲線(3)為了簡化計算，直接用方向碼18來計算Poincaré Index值，而不是用角度值，這樣就避免了三角函數運算和乘除法運算，大大降低了計算復雜度，提高了運算速度。(4）因為是用18方向碼來代替像素值,所以本文將（8）式中的用數字8來代替計算Poincaré Index的值，即(k) if|(k)|<4(9)(k)=(k)+ 8 if(k)-4(k)- 8 otherwise4.1.1 計算以塊為單位的方向場的Poincaré Index值對分塊后求出的指紋塊方

17、向場，以塊為單位，取w×w個塊，在該領域內對每一塊(點)計算Poincaré Index值,所用的封閉數字曲線塊M(x,y)鄰域的2×2矩形數字曲線,如圖2所示，其周長為4個像素。對應的Poincaré Index值記為Poincare(x,y)。4.1.2 指紋圖像奇異點的檢測用上述方法將奇異點的位置大致找出來,確定了在哪個塊內可能有奇異點。然后在回到分過塊后的連續方向場中，對那些可能存在奇異點的塊,計算以該塊M(x,y)為中心的3×3領域塊中的每一點，對其分別計算該點的Poincaré Index值，所用的封閉數字曲線是點P(x,

18、y)領域的2×2矩形數字曲線1,如圖2所示,其周長為4個像素，對應的Poincaré Index值記為Poincare1(x,y)。然后再用半徑是4個象素的封閉數字曲線計算該塊M(x,y)中每個點的Poincaré Index值,并將其記為Poincare2(x,y).同理，直接用方向碼18 來計算Poincaré Index值。4.2 指紋圖像奇異點判據4.2.1 對以塊為單位的塊方向場中的每一像素點M(i,j)根據4.1.1所求得的Poincaré Index值，設置奇異點的判據如下:（1） 若Poincare（i,j）=+0.5，則該塊M

19、(i,j)含有core點；（2） 若Poincare（i,j）=-0.5，則該塊M(i,j)含有delta點；（3） 否則，該塊M(i,j)為普通塊（即不含奇異點） 。4.2.2 對4.2.1所確定的塊M(i,j)內的每一點P(x,y)根據4.1.2的方法所求得的Poincaré Index值,設置奇異點的判據如下:（1） 若Poincare1(x,y)=+0.5，且Poincare2(x,y)>=+0.5,則該點P(x,y)是core點；（2） 若Poincare1(x,y)= -0.5，且Poincare2(x,y)<= -0.5,則該點P(x,y)是delta點；（

20、3） 否則，該點P(x,y)為普通點(非奇異點）。 如果檢測到core點的總數Nc大于2， 或者delta點的總數Nd大于2，則返回到3.3 節，對平滑后的點方向場O(x,y)，按3.3節方法（公式(4)）再進行一次平滑處理,然后按以上4.14.2方法重復，直到core點的總數Nc和delta點的總數Nd都不大于2為止。5 實驗結果及分析為了驗證本文所述算法的有效性，筆者在微機上用MATLAB語言實現了上述算法并對指紋圖像進行了實驗測試。從實驗結果中選擇了右旋型、雙螺紋型和螺紋型各一幅具有代表性的指紋列于文中，如圖3所示,分別用點方向場,塊方向場和本文的算法提取出奇異點并進行了比較，實驗結果如

21、圖所示， 圖中白色正方形的中心點為core點，白色三角形的中心點為delta點。 圖3 各指紋原圖圖4 用點方向場檢測奇異點 圖5 用塊方向場檢測奇異點 圖6 本文算法檢測指紋奇異點6 結束語本文在點方向圖和塊方向圖的基礎上提出了一種新的基于兩種方向圖的多尺度奇異點檢測算法。從結果中可以看出,用點方向圖檢測奇異點容易錯判,而用塊方向圖檢測奇異點時點位置不夠精確.本文的方法則很好的解決了上述問題,能夠在像素級水平精確定位指紋奇異點(core點和delta點）,每個有效的奇異點區域只檢測到一個候選奇異點，有效地解決了低質量指紋圖像奇異點檢測中精確定位和可靠性判斷的難題，為自動指紋識別系統中高精度的

22、指紋分類、匹配等關鍵技術奠定了良好的基礎。參考文獻:1PANKANTI S, PRABHAKAR S, JAIN A K.On the individuality of fingerprintsJ.IEEE Transactions on PAMI, 2002, 24(8) : 1010- 1025.2 JAIN A K, HONG L, BOLLE R.On- line fingerprint verificationJ.IEEE Transactions on PAMI, 1997, 19( 4) : 302- 314.3 ZHANG W W,WANG S,WANG Y S.Structu

23、re matching algorithm of fingerprint minutiae based on core point J.Acta Automatica Sinica, 2003, 29( 6) : 842- 850.4 Federal Bureau of science of fingerprints: classification and usesM.Washington D C: U S Government Printing Office,1984.5KAWAGOE M, TOJO A.Fingerprint pattern classificationJ.Pattern

24、 Recognition, 1984, 17( 3) : 295- 303.6Rao A R.A taxonomy for texture description and York:Springer verlag,1990.7L OGorman,J V approach to fingerprint filter rn Recognition.1989(1):29-388 聶桂軍, 吳陳.自動指紋識別系統中連續分布方向圖的研究J.中國圖象圖形學報, 2005,10(3):315-319.9 馬笑瀟,黃席樾,周欣,等.指紋自動識別系統中的關鍵技術方向圖J.重慶大學學報(自然科學版),2001,2

25、4(3):9194.10 聶桂軍,吳陳.基于連續分布方向圖的指紋奇異點檢測J.計算機工程與應用， 2006.35:198-20211D. Maio and D. Maltoni, Direct Gray-Scale Minutiae Detection in Fingerprints, IEEE Transactions on PAMI, 1997.12R. Cappelli, A. Lumini, D. Maio and D. Maltoni, Fingerprint Classification by Directional Image Partitioning, IEEE Transac

26、tions on PAMI, 1999.13Maio and D. Maltoni, Real-Time Face Location on Gray-Scale Static Images", Pattern Recognition, vol.33, no.9, pp.1525-1539, 2000.14R. Cappelli, D. Maio and D. Maltoni, Multi-space KL for Pattern Representation and Classification", IEEE Transactions on PAMI, 2001. 15D.

27、 Maio, D. Maltoni, R. Cappelli, J.L. Wayman and A.K. Jain, FVC2000: Fingerprint Verification Competition", IEEE Transactions on PAMI, 2002.16R. Cappelli, D. Maio and D. Maltoni, A Multi-Classifier Approach to Fingerprint Classification", Pattern Analysis and Applications, 2002.17R. Cappell

28、i, D. Maio, D. Maltoni, J.L. Wayman and A.K. Jain, Performance Evaluation of Fingerprint Verification Systems", IEEE Transactions on PAMI, 2006.作者簡介:湯婷 1985年生,女,碩士研究生,主要研究方向為數字圖像處理、生物特征識別;孫林森 1984年生,男, 碩士研究生,主要研究方向為數字圖像處理、生物特征識別;吳小培 1966年生,男,教授,博士生導師,主要研究方向為智能信息處理、模式識別與人工智能、數字圖像處理.A Multi-Scale Fingerprint Singular Points Detection Algorithm Based on Continuous Orientation FieldTang Ting, Sun Linsen, Wu XiaopeiDepartment of Computer Scienc