??? 摘? 要: 指紋分類技術是指紋數據庫的一個重要的索引機制。提出了一種基于指紋方向圖的結構分類算法。通過圖像分割,抽取圖像的有用部分,而后基于指紋方向圖,尋找指紋奇異點,利用脊線跟蹤技術和規則確定指紋的類別。?
??? 關鍵詞: 指紋分類 方向圖 脊線跟蹤? 圖像分割?
?
??? 指紋識別是一種重要的生物特征鑒別技術。每一個人都有自己特有的指紋特征。隨著計算機技術的不斷發展,自動指紋識別系統(AFIS)已在公安、金融領域得到廣泛的應用。圖1顯示了幾種典型的指紋圖像。?
?
?
??? 實踐表明,指紋識別技術具有高準確性和可信度。但是,指紋識別常常需要在大規模的數據庫上進行計算。如果沒有一種有效的數據庫分類機制,輸入的指紋圖像將不得不同數據庫中大量的指紋數據逐一進行比對,系統工作將非常繁重。為了減少搜索時間和計算的復雜度,必須對指紋進行分類。這樣查詢只需在指紋數據庫中的一個相應子集中進行,從而節省了運算時間并降低了運算復雜度。?
??? 指紋分類技術的核心問題是如何確定指紋分類類別。具體分類方法很多,類數也不確定。依照公安部的標準,指紋被分為以下七類:弓型、左箕、右箕、斗型、缺指、其它、未知。?
1 分類算法概述?
??? 指紋分類技術主要包括計算機圖像處理和模式識別兩方面的內容。指紋分類技術可以看作指紋在大尺度下的粗略匹配。輸入指紋首先被劃歸為預先已定義好的某一類,而后在更精細的尺度上,在這一類中進行精確的指紋比對。目前指紋分類算法通常有兩種分法,一種是根據采用的理論方法劃分,劃分通常劃分為統計方法、結構方法、人工神經網絡方法、變換域方法等。另一種是從實際問題考慮的角度出發,大致可分為兩類:一類是模型方式,這類方法主要基于指紋特征點的數目和相對位置,更接近于人的思維習慣;另一類是全局方式,根據整個圖像脊線特征或方向信息進行分類,這類方法常采用統計理論方法。?
??? 本文提出了一種基于結構的實現方法,依照指紋的方向圖信息,尋找奇異點。根據奇異點的數目和相關位置,設計邏輯規則進行判決。主要處理過程如圖2所示。?
?
?
2 圖像預分割?
??? 在指紋分類的過程中,輸入的指紋圖像往往是一幅含有大量噪聲的灰度圖像,特別是現場指紋,噪聲化現象更嚴重。這些干擾和不利因素將影響最終的分類結果,使得系統的整體性能和準確率降低。?
??? 圖像預處理的目的就是在盡量保存指紋特征信息條件下,去除原始指紋圖像的錯誤信息和冗余部分。預處理工作的好壞直接影響后續指紋分類的有效性。由于指紋分類和特征點提取等處理過程必須在預處理完成之后進行,因此預處理的時間復雜度也就成為影響整個指紋系統運行速度的一個重要因素。同圖像處理中經常使用的預處理技術不同,指紋的預處理工作有其特別之處。指紋是由突起的脊線和凹陷的脊溝組成的表皮圖案,這是一個灰度值交替變化的紋理圖案。在這種情況下,中值濾波、均值濾波一類的去噪措施將無能為力。首先因為這些技術都是基于圖像象素值平穩變化這一假設的;第二,因為指紋圖像在局部上有很強的空間頻率分布性和方向性。研究表明,效果好的預處理方法往往是利用了這些先驗知識。目前常用的預處理方法主要有空域增強法和頻域濾波法,空域方法包括方向圖、二值化、細化、修補、腐蝕等,頻域方法包括FFT、Gabor濾波等。本算法主要采用了兩種方法:一是指紋圖像的預分割;另一是方向圖處理及濾波。?
??? 本算法使用的測試圖像有如下特點(如圖3a所示):(1)指紋圖像比較模糊,變形有時也很嚴重;(2)指紋的位置和大小不定,很多圖像有明顯旋轉;(3)背景區的干擾很多,有很多文字和條紋線。針對以上情況,本算法采用預分割技術來排除文字、條紋線的干擾,提取圖像的有用信息。預分割主要由兩步組成:粗限定和細限定。?
??? 根據指紋圖的灰度分布,粗限定可以大致確定指紋圖中指印的相應位置?？刹捎檬?1)所示的8×8的平滑模板對圖像進行平滑和二值化處理。平滑實際上是一種增強措施,目的是突出指紋圖像的有用部分,便于投影和分割處理。經過處理,孤立噪聲點的影響將被忽略。而后沿水平和豎直兩個方向對圖像進行投影,并對同一方向上的灰度值進行累計,根據灰度值的分布,由外向內搜索邊界,從而確定圖像中的有效區域的范圍。?
????
?
??? 粗限定后對大多數圖像來說,文字和條紋部分都可排除在外,圖像已基本可用。但由于灰度分布隨機性及背景干擾等原因,有些圖像分割效果不好,對于后續判決將會有很大影響,所以還應采用細限定技術進一步分割圖像。具體過程是對粗限定后的圖像再進行投影,尋找每一方向上的灰度最大累計值,根據這個峰值確定相對域值,并由內向外搜索邊界,這一過程是對粗限定的修正。采用相對域值來提高預處理的適應度,可以去除部分指紋圖像中第二指節的冗余部分。?
??? 通過兩步限定過程,我們得到滿意的分割圖像,如圖3(b)所示。?
?
?
3 方向圖計算?
??? 方向圖計算有兩個功能:一是為后續處理做準備,因為指紋奇異點的提取依賴于方向圖;二是去除噪聲。方向圖用紋線的方向來表示該紋線,用方向場代替原圖像,實際上相當于對指紋原圖像的一種變換表示。同一般的濾波技術相比,它可以利用指紋圖像的局域方向性有效地去除噪聲,保留有用信息。一般有兩種方向圖,一種是點方向圖,表示源指紋圖像中每一象素點脊線的方向;另一種是塊方向圖,表示源指紋圖像中每一個圖像塊內脊線的總體方向。點方向圖的計算式如下:?
??? 若點(i,j) 的方向為K(i,j), 則:?
????
?
??? (ik,jk)∈Dk(i,j)?
??? 式中, Dk(i,j)為以點(i,j)為中心的沿第k方向的連續N個象素位置,G(i,j)為(i,j)點象素灰度值。?
??? 為了實際計算的方便,通常使用一個9×9的模板對以上公式進行簡化(參見文獻[1]、[2]),如圖3所示。?
??? 選取圖4所示的8個方向,分別對每一個方向計算求和式:?
??? S0=G(i-2,j-4)+G(i-1,j-2)+G(i+1,j+2)+G(i+2,j+4)?????????? (3)?
?
?
??? 設Sp和Sq分別代表8個方向中最大的方向和與最小的方向和。p和q代表相應的方向。如果C點位于脊溝上,那么C點的方向定義為p,否則為q。用D表示象素點C的方向,則:?
????
?
??? 通過(4)式可以得到指紋的方向圖。通常這是一幅噪聲化嚴重的圖像,必須利用指紋圖像的鄰域方向相似性加以處理。去噪的措施有兩種:一種是利用塊方向圖,具體措施是統計一個小區域(如8×8象素的矩形區)內的主要方向,亦即將該區域內點方向數最多的方向作為區域的主方向[1～2]。這樣對于一般的圖像區域來說,由于脊線走向的規律性,個別象素點噪聲的影響將被消除。除了去噪作用以外,塊方向圖還可以降低模式空間的維數,減少運算量,而數據的信息量卻不受很大影響。另外一種措施是計算每個點2倍方向角θ(θ∈[0,180°])的正、余弦值,即sin2θ和cos2θ。將一維的角度標量值變為二維矢量,而后對這個二維矢量的每個分量分別加以平滑[1～2]。從原理上看,這種平滑工作既可在點方向圖上進行,也可在塊方向圖上進行。但對于本算法使用的測試圖像,通過實驗比較表明,塊方向圖的平滑效果更好一些,如圖5所示。?
?
?
4 分類?
4.1 奇異點提取?
??? 根據奇異點的數目和相對位置可進行判決分類。對于用于識別的細節特征來講,這里的奇異點指的是較為“宏觀”的脊線特征。常用的奇異點有兩種:中心點(core)和三角區(delta)。中心點處于指紋圖像的中心,常用來進行指紋的定位。三角區則是指紋模式中另一類特征點,在該點處指紋的脊線分叉為三種走向,如圖6所示。?
?
?
??? 相對于指紋圖像的其它區域而言,奇異點有許多特殊性質。比如對于給定指紋圖像的任意一點,在其鄰域內作一條包圍該點的閉合曲線,沿該閉合曲線旋轉一周計算所得到的方向向量的旋轉總和。對于不同性質的點,這個總和值是不同的,中心點對應的值為180°,三角區對應的值為-180°,而一般的圖像區域對應值為0°。利用這一特性,我們可找出圖像中的奇異點。?
??? 受圖像噪聲的影響,在奇異點提取過程中往往會產生大量偽點,需要加以濾除?？梢岳门袥Q規則來排除錯誤的奇異點。錯誤的奇異點主要有兩類,一是在指紋圖像邊界,這一部分區域由于提取指紋時的受力不均,往往比較模糊,容易形成偽點;二是相鄰的奇異點,這往往是由于某個區域局部噪聲過大引起判決失誤。對于第一類錯誤判決,可以采用限定處理區域的辦法加以抑制,也就是前面所述的預分割辦法。而對于第二類錯誤,則采用如下步驟處理:?
??? (1)記錄所有初步判決產生的奇異點,對于每個奇異點,記錄它的位置信息和屬性值,即是中心點還是三角區。?
??? (2)沿水平方向逐行掃描,對于每個奇異點,判斷它的8鄰域內是否存在其它奇異點。如果存在,則執行步驟(3);否則,掃描下一個奇異點值。?
??? (3)如果鄰域內的所有奇異點同性,即同為中心點或三角區,則保留最靠后的那個奇異點,其它點標識為偽奇異點;如果鄰域內所有奇異點不同性,則所有點都標識為偽點,并繼續掃描。?
??? (4)當執行至圖像最后時,重新掃描圖像,去除所有偽奇異點。?
4.2 分類判決?
??? 指紋的不同類別有不同數目的奇異點和位置關系,這些奇異點的數目和相對位置決定了指紋的最終分類。決策過程如下:?
??? 設中心點的數目為Nc,三角區的數目為Nd。?
??? (1)如果Nc>2或Nd>2, 那么執行步驟(2);否則跳至步驟(3)。?
??? (2)如果迭代次數超過預設值,則將指紋類型設為其它,退出程序;否則平滑塊方向圖,重新計算奇異點,轉回步驟(1)。?
??? (3)如果Nc=Nd=1,利用規則1檢驗奇異點的位置關系。如果滿足,則判為左、右箕紋或弓型紋;否則指紋類型判為其它,退出。?
??? (4)如果Nc=Nd=2,利用規則2檢驗奇異點的位置關系。如果滿足,則判為斗型紋;否則轉回步驟(2)。?
??? (5)如果Nc=Nd=0,則判為弓形紋,退出。?
??? 規則的作用是檢測指紋奇異點的相對位置關系,確保判決的準確性。?
??? 規則1:檢驗箕型紋的位置關系,區別左、右箕或尖弓。由箕型紋的拓補結構可知,中心點總是位于指紋的上部,根據三角區相對于中心點的位置,可分為左、右箕或尖弓。本算法采用了脊線跟蹤技術,示意圖如圖7所示,具體過程如下:?
?
?
??? (1)以中心點的坐標為初始點(x0,y0)。?
??? (2)將當前點相鄰兩個方向塊的方向的平均值設為主方向。?
??? (3)沿主方向向下逐塊形成中心分界線 。?
??? x=x-BlockSize×cosθ?
??? y=y+BlockSize×sinθ?????????????????????????? ?(5)?
??? 其中,BlockSize代表方向塊的大小,θ表示當前位置的主方向。?
??? (4)重復(2)～(3)步直至到達圖像邊界為止。?
??? (5)設定一域值L,以中心線為界,如果三角區與中心線的最近距離在L內,則判為尖弓(本算法將其歸入弓類);如果位于分界線的左側,則將指紋判為左箕;如果位于分界線的右側,則判為右箕。?
??? 規則2:檢驗斗型紋的位置關系。具體判別如下:首先確定最上部的特征點必為中心點,同時保證兩個中心點位于兩個三角區特征點連線的一側。?
5 實驗結果?
??? 本算法對1737張指紋圖像進行了測試,最終總的分類錯誤率為3.3%(詳見表1)。從錯誤率指標來說,與文獻[4]大致相當,但本算法的測試樣本數要多。同時,我們對文獻[1]、[3]、[5]所述的算法進行模擬。實驗表明,在相同預處理條件下,本算法的判決的穩定性更好,準確率更高。?
?
?
??? 本算法是一種改進型的結構分類算法,利用指紋圖像的方向圖信息尋找奇異點,并根據這些奇異點的數目和相對位置進行判決,確定最終類別。相比于其它算法,本算法在預處理方面進行兩步預分割工作,減小了誤檢風險;同時設計了新的判決規則,利用脊線跟蹤和規則檢測,判斷左、右箕型指紋,提高分類穩定性。?
??? 本算法對于圖像旋轉不敏感,適應性強。同時依照公安部標準設計,便于實際使用。?
參考文獻?
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 張雪英.指紋分類系統研究.清華大學畢業論文,2000