基于連續(xù)方向場的多尺度指紋奇異點檢測算法

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

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

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

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

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

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

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

8、15;9 窗口內(nèi)，分別計算8個方向上的灰度和Si，Si也叫做該方向上的切縫和, 即對圖1中標(biāo)有i（ i=1， 2， 3， ， 8； 分別代表8個方向）的位置的像素灰度值求和,然后對灰度和進(jìn)行平均，得到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()為取數(shù)組(向量）A 的元素Ai的下標(biāo)i的函數(shù)，則方向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)=以此方法分別對指紋圖像中每一個像素點進(jìn)行處理,便可得到指紋的點方向場D(x,y)。3.3 連續(xù)方向場8在計算出指紋的點方向場D(x,y)后， 采用連續(xù)滑動的w×w窗口（模板）來對點方向圖D(x,y)進(jìn)行平滑處理,本文取17×17 的平滑窗口對點方向場中每一點P(x,y)進(jìn)行平滑，即在以此點為中心的w

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

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

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

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

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

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

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

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

18、y)領(lǐng)域的2×2矩形數(shù)字曲線1,如圖2所示,其周長為4個像素，對應(yīng)的Poincaré Index值記為Poincare1(x,y)。然后再用半徑是4個象素的封閉數(shù)字曲線計算該塊M(x,y)中每個點的Poincaré Index值,并將其記為Poincare2(x,y).同理，直接用方向碼18 來計算Poincaré Index值。4.2 指紋圖像奇異點判據(jù)4.2.1 對以塊為單位的塊方向場中的每一像素點M(i,j)根據(jù)4.1.1所求得的Poincaré Index值，設(shè)置奇異點的判據(jù)如下:（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)內(nèi)的每一點P(x,y)根據(jù)4.1.2的方法所求得的Poincaré Index值,設(shè)置奇異點的判據(jù)如下:（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點的總數(shù)Nc大于2， 或者delta點的總數(shù)Nd大于2，則返回到3.3 節(jié)，對平滑后的點方向場O(x,y)，按3.3節(jié)方法（公式(4)）再進(jìn)行一次平滑處理,然后按以上4.14.2方法重復(fù)，直到core點的總數(shù)Nc和delta點的總數(shù)Nd都不大于2為止。5 實驗結(jié)果及分析為了驗證本文所述算法的有效性，筆者在微機(jī)上用MATLAB語言實現(xiàn)了上述算法并對指紋圖像進(jìn)行了實驗測試。從實驗結(jié)果中選擇了右旋型、雙螺紋型和螺紋型各一幅具有代表性的指紋列于文中，如圖3所示,分別用點方向場,塊方向場和本文的算法提取出奇異點并進(jìn)行了比較，實驗結(jié)果如

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

22、指紋分類、匹配等關(guān)鍵技術(shù)奠定了良好的基礎(chǔ)。參考文獻(xiàn):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 聶桂軍, 吳陳.自動指紋識別系統(tǒng)中連續(xù)分布方向圖的研究J.中國圖象圖形學(xué)報, 2005,10(3):315-319.9 馬笑瀟,黃席樾,周欣,等.指紋自動識別系統(tǒng)中的關(guān)鍵技術(shù)方向圖J.重慶大學(xué)學(xué)報(自然科學(xué)版),2001,2

25、4(3):9194.10 聶桂軍,吳陳.基于連續(xù)分布方向圖的指紋奇異點檢測J.計算機(jī)工程與應(yīng)用， 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年生,女,碩士研究生,主要研究方向為數(shù)字圖像處理、生物特征識別;孫林森 1984年生,男, 碩士研究生,主要研究方向為數(shù)字圖像處理、生物特征識別;吳小培 1966年生,男,教授,博士生導(dǎo)師,主要研究方向為智能信息處理、模式識別與人工智能、數(shù)字圖像處理.A Multi-Scale Fingerprint Singular Points Detection Algorithm Based on Continuous Orientation FieldTang Ting, Sun Linsen, Wu XiaopeiDepartment of Computer Scienc