基于結(jié)構(gòu)的指紋分類技術(shù)

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

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

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

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

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

1 分類算法概述

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

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

2 圖像預(yù)分割

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

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

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

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

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

通過兩步限定過程，我們得到滿意的分割圖像，如圖3（b）所示。

3 方向圖計算

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

若點（i,j）的方向為K(i,j)，則：

（ik,jk）∈Dk(i,j)

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

為了實際計算的方便，通常使用一個9×9的模板對以上公式進行簡化（參見文獻(xiàn)[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)

設(shè)Sp和Sq分別代表8個方向中最大的方向和與最小的方向和。p和q代表相應(yīng)的方向。如果C點位于脊溝上，那么C點的方向定義為p，否則為q。用D表示象素點C的方向，則：

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

4 分類

4.1 奇異點提取

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

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

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

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

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

（3）如果領(lǐng)域內(nèi)的所有奇異點同性，即同為中心點或三角區(qū)，則保留最靠后的那個奇導(dǎo)點，其它點標(biāo)識為偽奇異點；如果領(lǐng)域內(nèi)所有奇異點不同性，則所有點都標(biāo)識為偽點，并繼續(xù)掃描。

（4）當(dāng)執(zhí)行至圖像是掃時，重新掃描圖像，去除所有偽奇異點。

4.2 分類判決

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

設(shè)中心點的數(shù)目為Nc，三角區(qū)的數(shù)目為Nd。

（1）如果Nc>2或Nd>2，那么執(zhí)行步驟（2）；否則跳至步驟（3）。

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

（3）如果Nc=Nd=1，利用規(guī)則1檢驗奇異點的位置關(guān)系。如果滿足，則判為左、右箕紋或弓型紋；否則指紋類型判為其它，退出。

（4）如果Nc=Nd=2，利用規(guī)則2檢驗奇異點的位置關(guān)系。如果滿足，則判為斗型紋；否則轉(zhuǎn)回步驟（2）。

（5）如果Nc=Nd=0，則判為弓形紋，退出。

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

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

（1）以中心點的坐標(biāo)為初始點（x0,y0）。

（2）將當(dāng)前點相鄰兩個方向塊的方向的平均值設(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：檢驗斗型紋的位置關(guān)系。具體差別如下：首先確定最上部的特征點必將為中心點，同時保證兩個中心點位于兩個三角區(qū)特征點連線的一側(cè)。

5 實驗結(jié)果

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

表1 測試樣本分類結(jié)果

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

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