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

摘要：指紋分類技術(shù)是指紋數(shù)據(jù)庫的一個(gè)重要的索引機(jī)制。提出了一種基于指紋方向圖的結(jié)構(gòu)分類算法。通過圖像分割，抽取圖像的有用部分，而后基于指紋方向圖，尋找指紋奇異點(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ù)庫上進(jìn)行計(jì)算。如果沒有一種有效的數(shù)據(jù)庫分類機(jī)制，輸入的指紋圖像將不得不同數(shù)據(jù)庫中大量的指紋數(shù)據(jù)逐一進(jìn)行比對，系統(tǒng)工作將非常繁重。為了減少搜索時(shí)間和計(jì)算的復(fù)雜度，必須對指紋進(jìn)行分類。這樣查詢只需在指紋數(shù)據(jù)庫中的一個(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)行精確的指紋比對。目前指紋分類算法通常有兩種分類，一種是根據(jù)采用的理論方法劃分，劃分通常劃分為統(tǒng)計(jì)方法、結(jié)構(gòu)方法、人工神經(jīng)網(wǎng)絡(luò)方法、變換域方法等。另一種是從實(shí)際問題考慮的角度出發(fā)，大致可分為兩類：一類是模型方式，這類方法主要基于指紋特征點(diǎn)的數(shù)目和相對集團(tuán)，更接近于人的思維習(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)行判決。主要處理過程如圖2所示。

2 圖像預(yù)分割

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

圖像預(yù)處理的目的就是在盡量保存指紋特征信息條件下，去除原始指紋圖像的錯(cuò)誤信息和冗余部分。預(yù)處理工作的好壞直接影響后續(xù)指紋分類的有效性。由于指紋分類和特征點(diǎn)提取等處理過程必須在預(yù)處理完成之后進(jìn)行，因此預(yù)處理的時(shí)間復(fù)雜度也就成為影響整個(gè)指紋系統(tǒng)運(yùn)行速度的一個(gè)重要因素。同圖像處理中經(jīng)常使用的預(yù)處理技術(shù)不同，指紋的預(yù)處理工作有其特別之片。指紋是由突起的脊線和凹陷的脊溝組成的表皮圖案，這是一個(gè)灰度值交替變化的紋理圖案。在這種情況下，中值濾波、均值濾波一類的去噪措施將無能為力。首先因?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ù)分割；另一是方向圖處理及濾波。

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

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

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

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

3 方向圖計(jì)算

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

若點(diǎn)（i,j）的方向?yàn)镵(i,j)，則：

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

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

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

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

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個(gè)方向中最大的方向和與最小的方向和。p和q代表相應(yīng)的方向。如果C點(diǎn)位于脊溝上，那么C點(diǎn)的方向定義為p，否則為q。用D表示象素點(diǎn)C的方向，則：

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

4 分類

4.1 奇異點(diǎn)提取

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

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

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

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

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

（3）如果領(lǐng)域內(nèi)的所有奇異點(diǎn)同性，即同為中心點(diǎn)或三角區(qū)，則保留最靠后的那個(gè)奇導(dǎo)點(diǎn)，其它點(diǎn)標(biāo)識(shí)為偽奇異點(diǎn)；如果領(lǐng)域內(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ù)目和相對位置決定了指紋的最終分類。決策過程如下：

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

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

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

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

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

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

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

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

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

（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é)果

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

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

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

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