??? 摘? 要: 指紋分類技術(shù)是指紋數(shù)據(jù)庫(kù)的一個(gè)重要的索引機(jī)制。提出了一種基于指紋方向圖的結(jié)構(gòu)分類算法。通過(guò)圖像分割,抽取圖像的有用部分,而后基于指紋方向圖,尋找指紋奇異點(diǎn),利用脊線跟蹤技術(shù)和規(guī)則確定指紋的類別。?

??? 關(guān)鍵詞: 指紋分類 方向圖 脊線跟蹤? 圖像分割?

?

??? 指紋識(shí)別是一種重要的生物特征鑒別技術(shù)。每一個(gè)人都有自己特有的指紋特征。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展,自動(dòng)指紋識(shí)別系統(tǒng)(AFIS)已在公安、金融領(lǐng)域得到廣泛的應(yīng)用。圖1顯示了幾種典型的指紋圖像。?

?

?

??? 實(shí)踐表明,指紋識(shí)別技術(shù)具有高準(zhǔn)確性和可信度。但是,指紋識(shí)別常常需要在大規(guī)模的數(shù)據(jù)庫(kù)上進(jìn)行計(jì)算。如果沒有一種有效的數(shù)據(jù)庫(kù)分類機(jī)制,輸入的指紋圖像將不得不同數(shù)據(jù)庫(kù)中大量的指紋數(shù)據(jù)逐一進(jìn)行比對(duì),系統(tǒng)工作將非常繁重。為了減少搜索時(shí)間和計(jì)算的復(fù)雜度,必須對(duì)指紋進(jìn)行分類。這樣查詢只需在指紋數(shù)據(jù)庫(kù)中的一個(gè)相應(yīng)子集中進(jìn)行,從而節(jié)省了運(yùn)算時(shí)間并降低了運(yùn)算復(fù)雜度。?

??? 指紋分類技術(shù)的核心問題是如何確定指紋分類類別。具體分類方法很多,類數(shù)也不確定。依照公安部的標(biāo)準(zhǔn),指紋被分為以下七類:弓型、左箕、右箕、斗型、缺指、其它、未知。?

1 分類算法概述?

??? 指紋分類技術(shù)主要包括計(jì)算機(jī)圖像處理和模式識(shí)別兩方面的內(nèi)容。指紋分類技術(shù)可以看作指紋在大尺度下的粗略匹配。輸入指紋首先被劃歸為預(yù)先已定義好的某一類,而后在更精細(xì)的尺度上,在這一類中進(jìn)行精確的指紋比對(duì)。目前指紋分類算法通常有兩種分法,一種是根據(jù)采用的理論方法劃分,劃分通常劃分為統(tǒng)計(jì)方法、結(jié)構(gòu)方法、人工神經(jīng)網(wǎng)絡(luò)方法、變換域方法等。另一種是從實(shí)際問題考慮的角度出發(fā),大致可分為兩類:一類是模型方式,這類方法主要基于指紋特征點(diǎn)的數(shù)目和相對(duì)位置,更接近于人的思維習(xí)慣;另一類是全局方式,根據(jù)整個(gè)圖像脊線特征或方向信息進(jìn)行分類,這類方法常采用統(tǒng)計(jì)理論方法。?

??? 本文提出了一種基于結(jié)構(gòu)的實(shí)現(xiàn)方法,依照指紋的方向圖信息,尋找奇異點(diǎn)。根據(jù)奇異點(diǎn)的數(shù)目和相關(guān)位置,設(shè)計(jì)邏輯規(guī)則進(jìn)行判決。主要處理過(guò)程如圖2所示。?

?

?

2 圖像預(yù)分割?

??? 在指紋分類的過(guò)程中,輸入的指紋圖像往往是一幅含有大量噪聲的灰度圖像,特別是現(xiàn)場(chǎng)指紋,噪聲化現(xiàn)象更嚴(yán)重。這些干擾和不利因素將影響最終的分類結(jié)果,使得系統(tǒng)的整體性能和準(zhǔn)確率降低。?

??? 圖像預(yù)處理的目的就是在盡量保存指紋特征信息條件下,去除原始指紋圖像的錯(cuò)誤信息和冗余部分。預(yù)處理工作的好壞直接影響后續(xù)指紋分類的有效性。由于指紋分類和特征點(diǎn)提取等處理過(guò)程必須在預(yù)處理完成之后進(jìn)行,因此預(yù)處理的時(shí)間復(fù)雜度也就成為影響整個(gè)指紋系統(tǒng)運(yùn)行速度的一個(gè)重要因素。同圖像處理中經(jīng)常使用的預(yù)處理技術(shù)不同,指紋的預(yù)處理工作有其特別之處。指紋是由突起的脊線和凹陷的脊溝組成的表皮圖案,這是一個(gè)灰度值交替變化的紋理圖案。在這種情況下,中值濾波、均值濾波一類的去噪措施將無(wú)能為力。首先因?yàn)檫@些技術(shù)都是基于圖像象素值平穩(wěn)變化這一假設(shè)的;第二,因?yàn)橹讣y圖像在局部上有很強(qiáng)的空間頻率分布性和方向性。研究表明,效果好的預(yù)處理方法往往是利用了這些先驗(yàn)知識(shí)。目前常用的預(yù)處理方法主要有空域增強(qiáng)法和頻域?yàn)V波法,空域方法包括方向圖、二值化、細(xì)化、修補(bǔ)、腐蝕等,頻域方法包括FFT、Gabor濾波等。本算法主要采用了兩種方法:一是指紋圖像的預(yù)分割;另一是方向圖處理及濾波。?

??? 本算法使用的測(cè)試圖像有如下特點(diǎn)(如圖3a所示):(1)指紋圖像比較模糊,變形有時(shí)也很嚴(yán)重;(2)指紋的位置和大小不定,很多圖像有明顯旋轉(zhuǎn);(3)背景區(qū)的干擾很多,有很多文字和條紋線。針對(duì)以上情況,本算法采用預(yù)分割技術(shù)來(lái)排除文字、條紋線的干擾,提取圖像的有用信息。預(yù)分割主要由兩步組成:粗限定和細(xì)限定。?

??? 根據(jù)指紋圖的灰度分布,粗限定可以大致確定指紋圖中指印的相應(yīng)位置?？刹捎檬?1)所示的8×8的平滑模板對(duì)圖像進(jìn)行平滑和二值化處理。平滑實(shí)際上是一種增強(qiáng)措施,目的是突出指紋圖像的有用部分,便于投影和分割處理。經(jīng)過(guò)處理,孤立噪聲點(diǎn)的影響將被忽略。而后沿水平和豎直兩個(gè)方向?qū)D像進(jìn)行投影,并對(duì)同一方向上的灰度值進(jìn)行累計(jì),根據(jù)灰度值的分布,由外向內(nèi)搜索邊界,從而確定圖像中的有效區(qū)域的范圍。?

?????

??? 粗限定后對(duì)大多數(shù)圖像來(lái)說(shuō),文字和條紋部分都可排除在外,圖像已基本可用。但由于灰度分布隨機(jī)性及背景干擾等原因,有些圖像分割效果不好,對(duì)于后續(xù)判決將會(huì)有很大影響,所以還應(yīng)采用細(xì)限定技術(shù)進(jìn)一步分割圖像。具體過(guò)程是對(duì)粗限定后的圖像再進(jìn)行投影,尋找每一方向上的灰度最大累計(jì)值,根據(jù)這個(gè)峰值確定相對(duì)域值,并由內(nèi)向外搜索邊界,這一過(guò)程是對(duì)粗限定的修正。采用相對(duì)域值來(lái)提高預(yù)處理的適應(yīng)度,可以去除部分指紋圖像中第二指節(jié)的冗余部分。?

??? 通過(guò)兩步限定過(guò)程,我們得到滿意的分割圖像,如圖3(b)所示。?

?

?

3 方向圖計(jì)算?

??? 方向圖計(jì)算有兩個(gè)功能:一是為后續(xù)處理做準(zhǔn)備,因?yàn)橹讣y奇異點(diǎn)的提取依賴于方向圖;二是去除噪聲。方向圖用紋線的方向來(lái)表示該紋線,用方向場(chǎng)代替原圖像,實(shí)際上相當(dāng)于對(duì)指紋原圖像的一種變換表示。同一般的濾波技術(shù)相比,它可以利用指紋圖像的局域方向性有效地去除噪聲,保留有用信息。一般有兩種方向圖,一種是點(diǎn)方向圖,表示源指紋圖像中每一象素點(diǎn)脊線的方向;另一種是塊方向圖,表示源指紋圖像中每一個(gè)圖像塊內(nèi)脊線的總體方向。點(diǎn)方向圖的計(jì)算式如下:?

??? 若點(diǎn)(i,j) 的方向?yàn)镵(i,j), 則:?

?????

??? (ik,jk)∈D_k(i,j)?

??? 式中, D_k(i,j)為以點(diǎn)(i,j)為中心的沿第k方向的連續(xù)N個(gè)象素位置,G(i,j)為(i,j)點(diǎn)象素灰度值。?

??? 為了實(shí)際計(jì)算的方便,通常使用一個(gè)9×9的模板對(duì)以上公式進(jìn)行簡(jiǎn)化(參見文獻(xiàn)[1]、[2]),如圖3所示。?

??? 選取圖4所示的8個(gè)方向,分別對(duì)每一個(gè)方向計(jì)算求和式:?

??? S₀=G(i-2,j-4)+G(i-1,j-2)+G(i+1,j+2)+G(i+2,j+4)?????????? (3)?

?

?

??? 設(shè)S_p和S_q分別代表8個(gè)方向中最大的方向和與最小的方向和。p和q代表相應(yīng)的方向。如果C點(diǎn)位于脊溝上,那么C點(diǎn)的方向定義為p,否則為q。用D表示象素點(diǎn)C的方向,則:?

?????

??? 通過(guò)(4)式可以得到指紋的方向圖。通常這是一幅噪聲化嚴(yán)重的圖像,必須利用指紋圖像的鄰域方向相似性加以處理。去噪的措施有兩種:一種是利用塊方向圖,具體措施是統(tǒng)計(jì)一個(gè)小區(qū)域(如8×8象素的矩形區(qū))內(nèi)的主要方向,亦即將該區(qū)域內(nèi)點(diǎn)方向數(shù)最多的方向作為區(qū)域的主方向^[1～2]。這樣對(duì)于一般的圖像區(qū)域來(lái)說(shuō),由于脊線走向的規(guī)律性,個(gè)別象素點(diǎn)噪聲的影響將被消除。除了去噪作用以外,塊方向圖還可以降低模式空間的維數(shù),減少運(yùn)算量,而數(shù)據(jù)的信息量卻不受很大影響。另外一種措施是計(jì)算每個(gè)點(diǎn)2倍方向角θ(θ∈[0,180°])的正、余弦值,即sin2θ和cos2θ。將一維的角度標(biāo)量值變?yōu)槎S矢量,而后對(duì)這個(gè)二維矢量的每個(gè)分量分別加以平滑^[1～2]。從原理上看,這種平滑工作既可在點(diǎn)方向圖上進(jìn)行,也可在塊方向圖上進(jìn)行。但對(duì)于本算法使用的測(cè)試圖像,通過(guò)實(shí)驗(yàn)比較表明,塊方向圖的平滑效果更好一些,如圖5所示。?

?

?

4 分類?

4.1 奇異點(diǎn)提取?

??? 根據(jù)奇異點(diǎn)的數(shù)目和相對(duì)位置可進(jìn)行判決分類。對(duì)于用于識(shí)別的細(xì)節(jié)特征來(lái)講,這里的奇異點(diǎn)指的是較為“宏觀”的脊線特征。常用的奇異點(diǎn)有兩種:中心點(diǎn)(core)和三角區(qū)(delta)。中心點(diǎn)處于指紋圖像的中心,常用來(lái)進(jìn)行指紋的定位。三角區(qū)則是指紋模式中另一類特征點(diǎn),在該點(diǎn)處指紋的脊線分叉為三種走向,如圖6所示。?

?

?

??? 相對(duì)于指紋圖像的其它區(qū)域而言,奇異點(diǎn)有許多特殊性質(zhì)。比如對(duì)于給定指紋圖像的任意一點(diǎn),在其鄰域內(nèi)作一條包圍該點(diǎn)的閉合曲線,沿該閉合曲線旋轉(zhuǎn)一周計(jì)算所得到的方向向量的旋轉(zhuǎn)總和。對(duì)于不同性質(zhì)的點(diǎn),這個(gè)總和值是不同的,中心點(diǎn)對(duì)應(yīng)的值為180°,三角區(qū)對(duì)應(yīng)的值為-180°,而一般的圖像區(qū)域?qū)?yīng)值為0°。利用這一特性,我們可找出圖像中的奇異點(diǎn)。?

??? 受圖像噪聲的影響,在奇異點(diǎn)提取過(guò)程中往往會(huì)產(chǎn)生大量偽點(diǎn),需要加以濾除?？梢岳门袥Q規(guī)則來(lái)排除錯(cuò)誤的奇異點(diǎn)。錯(cuò)誤的奇異點(diǎn)主要有兩類,一是在指紋圖像邊界,這一部分區(qū)域由于提取指紋時(shí)的受力不均,往往比較模糊,容易形成偽點(diǎn);二是相鄰的奇異點(diǎn),這往往是由于某個(gè)區(qū)域局部噪聲過(guò)大引起判決失誤。對(duì)于第一類錯(cuò)誤判決,可以采用限定處理區(qū)域的辦法加以抑制,也就是前面所述的預(yù)分割辦法。而對(duì)于第二類錯(cuò)誤,則采用如下步驟處理:?

??? (1)記錄所有初步判決產(chǎn)生的奇異點(diǎn),對(duì)于每個(gè)奇異點(diǎn),記錄它的位置信息和屬性值,即是中心點(diǎn)還是三角區(qū)。?

??? (2)沿水平方向逐行掃描,對(duì)于每個(gè)奇異點(diǎn),判斷它的8鄰域內(nèi)是否存在其它奇異點(diǎn)。如果存在,則執(zhí)行步驟(3);否則,掃描下一個(gè)奇異點(diǎn)值。?

??? (3)如果鄰域內(nèi)的所有奇異點(diǎn)同性,即同為中心點(diǎn)或三角區(qū),則保留最靠后的那個(gè)奇異點(diǎn),其它點(diǎn)標(biāo)識(shí)為偽奇異點(diǎn);如果鄰域內(nèi)所有奇異點(diǎn)不同性,則所有點(diǎn)都標(biāo)識(shí)為偽點(diǎn),并繼續(xù)掃描。?

??? (4)當(dāng)執(zhí)行至圖像最后時(shí),重新掃描圖像,去除所有偽奇異點(diǎn)。?

4.2 分類判決?

??? 指紋的不同類別有不同數(shù)目的奇異點(diǎn)和位置關(guān)系,這些奇異點(diǎn)的數(shù)目和相對(duì)位置決定了指紋的最終分類。決策過(guò)程如下:?

??? 設(shè)中心點(diǎn)的數(shù)目為N_c,三角區(qū)的數(shù)目為N_d。?

??? (1)如果N_c>2或N_d>2, 那么執(zhí)行步驟(2);否則跳至步驟(3)。?

??? (2)如果迭代次數(shù)超過(guò)預(yù)設(shè)值,則將指紋類型設(shè)為其它,退出程序;否則平滑塊方向圖,重新計(jì)算奇異點(diǎn),轉(zhuǎn)回步驟(1)。?

??? (3)如果N_c=N_d=1,利用規(guī)則1檢驗(yàn)奇異點(diǎn)的位置關(guān)系。如果滿足,則判為左、右箕紋或弓型紋;否則指紋類型判為其它,退出。?

??? (4)如果N_c=N_d=2,利用規(guī)則2檢驗(yàn)奇異點(diǎn)的位置關(guān)系。如果滿足,則判為斗型紋;否則轉(zhuǎn)回步驟(2)。?

??? (5)如果N_c=N_d=0,則判為弓形紋,退出。?

??? 規(guī)則的作用是檢測(cè)指紋奇異點(diǎn)的相對(duì)位置關(guān)系,確保判決的準(zhǔn)確性。?

??? 規(guī)則1:檢驗(yàn)箕型紋的位置關(guān)系,區(qū)別左、右箕或尖弓。由箕型紋的拓補(bǔ)結(jié)構(gòu)可知,中心點(diǎn)總是位于指紋的上部,根據(jù)三角區(qū)相對(duì)于中心點(diǎn)的位置,可分為左、右箕或尖弓。本算法采用了脊線跟蹤技術(shù),示意圖如圖7所示,具體過(guò)程如下:?

?

?

??? (1)以中心點(diǎn)的坐標(biāo)為初始點(diǎn)(x₀,y₀)。?

??? (2)將當(dāng)前點(diǎn)相鄰兩個(gè)方向塊的方向的平均值設(shè)為主方向。?

??? (3)沿主方向向下逐塊形成中心分界線 。?

??? x=x-BlockSize×cosθ?

??? y=y+BlockSize×sinθ?????????????????????????? ?(5)?

??? 其中,BlockSize代表方向塊的大小,θ表示當(dāng)前位置的主方向。?

??? (4)重復(fù)(2)～(3)步直至到達(dá)圖像邊界為止。?

??? (5)設(shè)定一域值L,以中心線為界,如果三角區(qū)與中心線的最近距離在L內(nèi),則判為尖弓(本算法將其歸入弓類);如果位于分界線的左側(cè),則將指紋判為左箕;如果位于分界線的右側(cè),則判為右箕。?

??? 規(guī)則2:檢驗(yàn)斗型紋的位置關(guān)系。具體判別如下:首先確定最上部的特征點(diǎn)必為中心點(diǎn),同時(shí)保證兩個(gè)中心點(diǎn)位于兩個(gè)三角區(qū)特征點(diǎn)連線的一側(cè)。?

5 實(shí)驗(yàn)結(jié)果?

??? 本算法對(duì)1737張指紋圖像進(jìn)行了測(cè)試,最終總的分類錯(cuò)誤率為3.3%(詳見表1)。從錯(cuò)誤率指標(biāo)來(lái)說(shuō),與文獻(xiàn)[4]大致相當(dāng),但本算法的測(cè)試樣本數(shù)要多。同時(shí),我們對(duì)文獻(xiàn)[1]、[3]、[5]所述的算法進(jìn)行模擬。實(shí)驗(yàn)表明,在相同預(yù)處理?xiàng)l件下,本算法的判決的穩(wěn)定性更好,準(zhǔn)確率更高。?

?

?

??? 本算法是一種改進(jìn)型的結(jié)構(gòu)分類算法,利用指紋圖像的方向圖信息尋找奇異點(diǎn),并根據(jù)這些奇異點(diǎn)的數(shù)目和相對(duì)位置進(jìn)行判決,確定最終類別。相比于其它算法,本算法在預(yù)處理方面進(jìn)行兩步預(yù)分割工作,減小了誤檢風(fēng)險(xiǎn);同時(shí)設(shè)計(jì)了新的判決規(guī)則,利用脊線跟蹤和規(guī)則檢測(cè),判斷左、右箕型指紋,提高分類穩(wěn)定性。?

??? 本算法對(duì)于圖像旋轉(zhuǎn)不敏感,適應(yīng)性強(qiáng)。同時(shí)依照公安部標(biāo)準(zhǔn)設(shè)計(jì),便于實(shí)際使用。?

參考文獻(xiàn)?

1 K. Karu, A.K. Jain. Fingerprint Classificatio. Pattern?Recognition, 1996;29(3): 389～404 ?

2 G.T.Candela. PCASYS─A Pattern-Level Classification Automation System for Fingerprint.NIST Technical Report?NISTIR 5647, Aug .1995?

3 Masahirl Kawagoe,Akio Tojo. Fingerprint Pattern Classification. Pattern Recognition, 1984;17(3): 295～303?

4 陳 勇,楊 新.基于方向場(chǎng)的指紋分類快速算法.模式識(shí)別與人工智能,2000;13(4)?

5 張雪英.指紋分類系統(tǒng)研究.清華大學(xué)畢業(yè)論文,2000