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

??? 關鍵詞: 指紋分類 方向圖 脊線跟蹤? 圖像分割?

?

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

?

?

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

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

1 分類算法概述?

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

??? 本文提出了一種基于結構的實現方法,依照指紋的方向圖信息,尋找奇異點。根據奇異點的數目和相關位置,設計邏輯規(guī)則進行判決。主要處理過程如圖2所示。?

?

?

2 圖像預分割?

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

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

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

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

?????

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

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

?

?

3 方向圖計算?

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

??? 若點(i,j) 的方向為K(i,j), 則:?

?????

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

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

??? 為了實際計算的方便,通常使用一個9×9的模板對以上公式進行簡化(參見文獻[1]、[2]),如圖3所示。?

??? 選取圖4所示的8個方向,分別對每一個方向計算求和式:?

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

?

?

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

?????

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

?

?

4 分類?

4.1 奇異點提取?

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

?

?

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

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

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

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

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

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

4.2 分類判決?

??? 指紋的不同類別有不同數目的奇異點和位置關系,這些奇異點的數目和相對位置決定了指紋的最終分類。決策過程如下:?

??? 設中心點的數目為N_c,三角區(qū)的數目為N_d。?

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

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

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

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

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

??? 規(guī)則的作用是檢測指紋奇異點的相對位置關系,確保判決的準確性。?

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

?

?

??? (1)以中心點的坐標為初始點(x₀,y₀)。?

??? (2)將當前點相鄰兩個方向塊的方向的平均值設為主方向。?

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

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

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

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

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

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

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

5 實驗結果?

??? 本算法對1737張指紋圖像進行了測試,最終總的分類錯誤率為3.3%(詳見表1)。從錯誤率指標來說,與文獻[4]大致相當,但本算法的測試樣本數要多。同時,我們對文獻[1]、[3]、[5]所述的算法進行模擬。實驗表明,在相同預處理條件下,本算法的判決的穩(wěn)定性更好,準確率更高。?

?

?

??? 本算法是一種改進型的結構分類算法,利用指紋圖像的方向圖信息尋找奇異點,并根據這些奇異點的數目和相對位置進行判決,確定最終類別。相比于其它算法,本算法在預處理方面進行兩步預分割工作,減小了誤檢風險;同時設計了新的判決規(guī)則,利用脊線跟蹤和規(guī)則檢測,判斷左、右箕型指紋,提高分類穩(wě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 陳 勇,楊 新.基于方向場的指紋分類快速算法.模式識別與人工智能,2000;13(4)?

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