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

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

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

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

實(shí)踐表明,指紋識別技術(shù)具有高準(zhǔn)確性和可信度。但是,指紋識別常常需要在大規(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ī)圖像處理和模式識別兩方面的內(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)知識。目前常用的預(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)位置。可采用式（1）所示的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)行判決分類。對于用于識別的細(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)識為偽奇異點(diǎn);如果領(lǐng)域內(nèi)所有奇異點(diǎn)不同性,則所有點(diǎn)都標(biāo)識為偽點(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í)際使用。