自動(dòng)指紋識(shí)別系統(tǒng)是生物特征識(shí)別研究的一個(gè)熱點(diǎn)，而指紋分類(lèi)又是指紋識(shí)別系統(tǒng)的核 心技術(shù)。在大型的指紋數(shù)據(jù)庫(kù)中，待識(shí)別指紋與樣本數(shù)據(jù)庫(kù)中的大量指紋逐一進(jìn)行比對(duì)，是及其耗費(fèi)時(shí)間的。為了減少搜索時(shí)間和計(jì)算復(fù)雜性，把樣本數(shù)據(jù)庫(kù)中的指紋分為幾類(lèi)，將屬 于不同類(lèi)別的指紋分別保存在不同的數(shù)據(jù)庫(kù)中，待識(shí)別指紋只需與屬于同類(lèi)的子數(shù)據(jù)庫(kù)中的樣本逐一比對(duì)。從某種意義上講，指紋分類(lèi)實(shí)際上就是粗糙的指紋匹配過(guò)程，它為自動(dòng)指紋識(shí)別系統(tǒng)提供了一個(gè)索引機(jī)制。

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

　　1 分類(lèi)算法概述

　　國(guó)內(nèi)外學(xué)者已經(jīng)對(duì)指紋分類(lèi)算法進(jìn)行了大量的研究。大致可分為下面幾種：種是基于奇異點(diǎn)的分類(lèi)，主要依靠指紋的core點(diǎn)和delta點(diǎn)的個(gè)數(shù)以及它們之間的拓?fù)潢P(guān)系來(lái)確定指紋屬于哪種類(lèi)型。此類(lèi)方法要求指紋圖像必須能夠采集到core點(diǎn)和delta點(diǎn)，但由于一些采集器采集面積的限制，要保證能夠采集到delta點(diǎn)還是比較困難的，而且對(duì)于受噪聲干擾程度比較嚴(yán)重的低質(zhì)量圖像不僅奇異點(diǎn)的定位比較困難，還往往容易檢測(cè)到許多虛假的奇異點(diǎn)，直接導(dǎo)致了此算法的準(zhǔn)確率。第二種是基于結(jié)構(gòu)的指紋分類(lèi)。主要有Raffaele Cappelli等人使用動(dòng)態(tài)模板的分類(lèi)方法，這些方法使用了圖像的一些整體結(jié)構(gòu)，因此比其它大多數(shù)使用局部信息的分類(lèi)方法更加有效，但對(duì)于一些低質(zhì)量的指紋圖像，很難獲取指紋準(zhǔn)確的結(jié)構(gòu)。第三種是結(jié)合奇異點(diǎn)和脊線(xiàn)結(jié)構(gòu)的指紋分類(lèi)方法，此種方法不單單依賴(lài)于奇異點(diǎn)，同時(shí)使用了脊線(xiàn)的結(jié)構(gòu)，但對(duì)于低質(zhì)量的指紋圖像，此方法獲取的奇異點(diǎn)與脊線(xiàn)結(jié)構(gòu)同樣是不準(zhǔn)確的，因此對(duì)于低質(zhì)量指紋依然是不能夠準(zhǔn)確的分類(lèi)。第四種是基于方向場(chǎng)的指紋分類(lèi)，主要是根據(jù)各類(lèi)指紋圖像的方向圖的相似和差異來(lái)確定指紋的類(lèi)型。此方法對(duì)低質(zhì)量也有一定的局限性。目前國(guó)內(nèi)外的指紋分類(lèi)算法大部分都是把指紋分為4類(lèi)或5類(lèi)。

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

　　2 圖像預(yù)分割

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

　　本算法使用的測(cè)試圖像有如下特點(diǎn)（如圖3a所示）：（1）指紋圖像比較模糊，變形時(shí)也很?chē)?yán)重；（2）指紋的位置和大小不定，很多圖像有明顯旋轉(zhuǎn)；（3）背景區(qū)的干擾很多，有很多方字和條紋線(xiàn)。針對(duì)以上情況，本算法采用預(yù)分割技術(shù)來(lái)排除文字、條紋線(xiàn)的干擾，提取圖像的有用信息。預(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īng)度，可以去除部分指紋圖像中第二指節(jié)的冗余部分。

　　通過(guò)兩步限定過(guò)程，我們得到滿(mǎn)意的分割圖像，如圖3（b）所示。

　　3 方向圖計(jì)算

　　方向圖計(jì)算有兩個(gè)功能：一是為后續(xù)處理做準(zhǔn)備，因?yàn)橹讣y奇異點(diǎn)的提取依賴(lài)于方向圖；二是去除噪聲。同一般的濾波技術(shù)相比，它可以利用指紋圖像的局域方向性有效地去除噪聲，保留有用信息。一般有兩種方向圖，一種是點(diǎn)方向圖，表示源指紋圖像中每一象素點(diǎn)脊線(xiàn)的方向；另一種是塊方向圖，表示源指紋圖像中每一個(gè)圖像塊內(nèi)脊線(xiàn)的總體方向。點(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的模板對(duì)以上公式進(jìn)行簡(jiǎn)化，如圖4所示。

　　選取圖4所示的8個(gè)方向，分別對(duì)每一個(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的方向，則：

　　通過(guò)（4）式可以得到指紋的方向圖。通常這是一幅噪聲化嚴(yán)重的圖像，必須利用指紋圖像的領(lǐng)域方向相似性加以處理。去噪的措施有兩種：一種是利用塊方向圖，具體措施是統(tǒng)計(jì)一個(gè)小區(qū)域（如8×8象素的矩形區(qū)）內(nèi)的主要方向。這樣對(duì)于一般的圖像區(qū)域來(lái)說(shuō)，由于脊線(xiàn)走向的規(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è)分量分別加以平滑。但對(duì)于本算法使用的測(cè)試圖像，通過(guò)實(shí)驗(yàn)比較表明，塊方向圖的平滑效果更一些，如圖5的所示。

　　4 分類(lèi)

　　4.1 奇異點(diǎn)提取

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

　　相對(duì)于指紋圖像的其它區(qū)域而言，奇異點(diǎn)有許多特殊性質(zhì)。比如對(duì)于給定指紋圖像的任意一點(diǎn)，在其鄰域內(nèi)作一條包圍該點(diǎn)的閉合曲線(xiàn)，沿該閉合曲線(xià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)，需要加以濾除。可以利用判決規(guī)則來(lái)排除錯(cuò)誤的奇異點(diǎn)。錯(cuò)誤的奇異點(diǎn)主要有兩類(lèi)，一是在指紋圖像邊界，這一部分區(qū)域由于提取指紋時(shí)的受力不均，往往比較模糊，容易形成偽點(diǎn)；二是相鄰的奇異點(diǎn)，這往往是由于某個(gè)區(qū)域局部噪聲過(guò)大引起判決失誤。對(duì)于類(lèi)錯(cuò)誤判決，可以采用限定處理區(qū)域的辦法加以抑制，也就是前面所述的預(yù)分割辦法。而對(duì)于第二類(lèi)錯(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）如果領(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 分類(lèi)判決

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

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

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

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

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

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

　　（5）如果Nc=Nd=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)的位置，可分為左、右箕或尖弓。

    本算法采用了脊線(xiàn)跟蹤技術(shù)，示意圖如圖7所示，具體過(guò)程如下：

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

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

　　（3）沿主方向向下逐塊形成中心分界線(xiàn)。

　　x=x-BlockSize×cosθ

　　y=y+BlockSize×sinθ （5）

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

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

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

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

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

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

　　表1 測(cè)試樣本分類(lèi)結(jié)果

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