指紋圖像細(xì)化算法的研究

錢(qián) 超， 王福明

（中北大學(xué)，信息與通信工程學(xué)院，山西太原 030051）

0 引言

指紋識(shí)別的效率和好壞很大程度上依賴(lài)于指紋圖像的預(yù)處理。一個(gè)好的預(yù)處理方法將大大減少偽特征點(diǎn)數(shù),減少對(duì)原始采集圖像好壞的依賴(lài)。一個(gè)優(yōu)秀的生物特征識(shí)別系統(tǒng)要求能實(shí)時(shí)迅速有效地完成其識(shí)別過(guò)程。所有的生物特征識(shí)別系統(tǒng)都包括如下幾個(gè)處理過(guò)程：采集、比對(duì)和匹配。指紋識(shí)別處理也一樣，它包括指紋圖像采集、指紋圖像預(yù)處理、特征提取、特征值的比對(duì)與匹配等過(guò)程。使用指紋識(shí)別方式的優(yōu)點(diǎn)在于它的可靠、方便且容易被接受[1]。

預(yù)處理在整個(gè)自動(dòng)指紋識(shí)別系統(tǒng)的過(guò)程中是很關(guān)鍵的一步，是正確地進(jìn)行特征提取、匹配等操作的基礎(chǔ)。采集到的指紋圖像由于各種原因的影響，是一幅含多種不同程度噪聲干擾的灰度圖像，指紋脊線可能被斷開(kāi)、橋接或模糊等，而含有大量噪化的指紋脊線結(jié)構(gòu)會(huì)影響著自動(dòng)指紋識(shí)別系統(tǒng)的性能。指紋預(yù)處理是指紋特征提取前的不可缺少的一個(gè)重要環(huán)節(jié)，主要用于突出指紋圖像中的紋理、方向信息，消除或者減弱噪聲等無(wú)用信息。指紋圖像預(yù)處理通常包括指紋圖像分割、圖像增強(qiáng)、二值化、細(xì)化等[2]。

1 指紋圖像二值化

指紋圖像二值化后，其紋線寬度是不均勻的，這是因?yàn)樵紙D像的質(zhì)量受到壓力大小的影響和圖像采集過(guò)程中噪聲的影響而造成的。雖然紋線的寬度并不包含指紋的特征信息，但它的不均勻性會(huì)影響指紋特征的提取，并且指紋識(shí)別只對(duì)紋線的走向感興趣，并不關(guān)心它的粗細(xì)，因此為了減小數(shù)據(jù)量，提高識(shí)別準(zhǔn)確性，應(yīng)對(duì)指紋圖像進(jìn)行細(xì)化處理[3]。

指紋圖像細(xì)化方法的一種是可以直接從灰度圖像進(jìn)行，但難以尋找紋線的中心點(diǎn)；另一種則是廣泛使用的，把灰度線條圖像變成二值圖像再進(jìn)行細(xì)化。細(xì)化是刪除指紋紋線的邊緣像素，使之只有一個(gè)像素寬度。細(xì)化時(shí)應(yīng)保證紋線的連接性、方向性和特征點(diǎn)不變，還應(yīng)保持紋線的中心基本不變。指紋圖像的細(xì)化是接受二值化后的指紋圖像，并為指紋圖像的特征提取和匹配提供圖像。細(xì)化方法應(yīng)滿足下列條件：

(1)迭代必須收斂。(收斂性)

(2)不破壞紋線的連接性。(連接性)

(3)不引起紋線的逐步吞食。(拓?fù)湫?

(4)保護(hù)指紋的細(xì)節(jié)特征。(保持性)

(5)骨架紋線的寬度為一個(gè)像素。(細(xì)化性)

(6)骨架盡可能接近紋線中心。(中軸性)

(7)算法簡(jiǎn)單、速度快。(快速性)

細(xì)化從實(shí)現(xiàn)的方法上分，可分為兩大類(lèi)：一類(lèi)是從外到內(nèi)逐點(diǎn)剝?nèi)ザ祱D像的邊緣點(diǎn)，如Hildth算法；令一類(lèi)是從內(nèi)到外，找到某一中間點(diǎn)，然后按掃描方向?qū)ふ移?鄰域內(nèi)也為線條紋中間像素的點(diǎn)，逐次取得細(xì)化線。第一種方法中間定位性比較好，易于實(shí)現(xiàn)，但往往要經(jīng)過(guò)若干次迭代運(yùn)算才能得到細(xì)化線，速度較慢：第二種方法能保持較好的連通性，但情況復(fù)雜，中間定位不準(zhǔn)。細(xì)化算法按細(xì)化處理過(guò)程可分為串行細(xì)化、并行細(xì)化和串并行混合細(xì)化。串行細(xì)化一次只能處理一個(gè)像素，下次操作由上次的操作結(jié)果決定。并行細(xì)化算法是同時(shí)對(duì)滿足給定條件的像素進(jìn)行處理，即一次處理所有像素的一個(gè)子集[4]。

按細(xì)化后圖像的連通性可將細(xì)化算法分為4連通細(xì)化、8連通細(xì)化和混合連通細(xì)化，4連通指的是細(xì)化后圖像在水平垂直4個(gè)方向上的連通，8連通是細(xì)化后圖像在水平垂直4個(gè)方向再加上正反45度共8個(gè)方向上的連通，混合連通是指細(xì)化后圖像既有4連通也有8連通。其他常用于指紋細(xì)化的算法還有方向圖中心掃描細(xì)化算法、紋線跟蹤細(xì)化算法等。

淺閱讀是走向深閱讀過(guò)程中的起步階段。在這個(gè)階段，閱讀主體可以大致擬出閱讀的提綱或思維導(dǎo)圖，至少在腦中會(huì)形成對(duì)閱讀內(nèi)容的總體印象，判斷出下一步需要詳讀的部分和略讀的部分。

現(xiàn)有的指紋細(xì)化算法存在很多問(wèn)題，像細(xì)化不徹底、紋線吞噬、骨架偏離紋線中心、細(xì)化效率低下等。其中紋線細(xì)化不徹底特別是紋線分叉點(diǎn)處細(xì)化不徹底，影響紋線分叉點(diǎn)的正確提取。紋線的吞噬往往導(dǎo)致提取的紋線端點(diǎn)位置移動(dòng)較大。

通過(guò)對(duì)一般細(xì)化算法存在的問(wèn)題，進(jìn)行改進(jìn)，以減少偽特征的個(gè)數(shù)，對(duì)細(xì)化算法中的消除模板和保留模板進(jìn)行改進(jìn)，并模糊了消除模版的概念，擴(kuò)大了消除模板的范圍[5]。

2 改進(jìn)的OPTA算法

OPTA算法是一種典型的基于模板的圖像細(xì)化算法（如圖1至圖3所示），算法核心是通過(guò)應(yīng)用消除和保留這兩套模板來(lái)達(dá)到對(duì)原圖細(xì)化的目的。OPTA算法用到的是與其相鄰的10個(gè)像素。從圖像的左上角元素開(kāi)始進(jìn)行，首先用該像素的8個(gè)鄰域與8個(gè)細(xì)化模板(消除模板)相匹配，若與任何消除模板都不匹配，不做任何改變；若與其中的任一消除模板匹配，則再與保留模板相匹配，若存在與一個(gè)保留模板匹配，則不做任何改變，若與任何保留模板都不匹配，則把該像素改為0。該算法按從左上角到右下角的順序進(jìn)行，處理完一個(gè)過(guò)程即為一次迭代，“迭代”反復(fù)進(jìn)行，直到?jīng)]有一個(gè)像素的值被改變?yōu)橹?。其中迭代的次?shù)依賴(lài)于圖像的大小、紋線的形狀和圖像的質(zhì)量[7]。

圖1 OPTA算法所取的鄰域

圖2 OPTA細(xì)化算法的消除模板(×表示任意，可以為0或1)

圖3 OPTA細(xì)化算法的保留模板(×表示任意，可以為0或1)

下面給出幾個(gè)細(xì)化中的定義：

目標(biāo)點(diǎn)與背景點(diǎn)：目標(biāo)點(diǎn)指像素值為1的點(diǎn)，背景點(diǎn)指像素值為O的點(diǎn)。

單像素寬：考察紋線上每一點(diǎn)的8鄰點(diǎn)，紋線端點(diǎn)的8鄰點(diǎn)中只有一個(gè)目標(biāo)點(diǎn)，紋線連續(xù)點(diǎn)的8鄰點(diǎn)有兩個(gè)目標(biāo)點(diǎn)，紋線分叉點(diǎn)有3個(gè)目標(biāo)點(diǎn)，且每點(diǎn)8鄰點(diǎn)最多只有3個(gè)目標(biāo)點(diǎn)。符合上述條件即為單像素寬。

邊界點(diǎn)：屬于目標(biāo)點(diǎn)，且其4鄰點(diǎn)中至少有一個(gè)為背景點(diǎn)。

端點(diǎn)：屬于邊界點(diǎn)，且其8鄰點(diǎn)中只有一個(gè)屬于目標(biāo)點(diǎn)。

關(guān)鍵點(diǎn)：刪除該點(diǎn)后會(huì)引起紋線的不連通，又叫做斷點(diǎn)。

消除模板：判斷是否符合消除的條件。

保留模板：對(duì)符合消除條件的像素，判斷與其相鄰的同一行或同一列是否有非0點(diǎn)，如沒(méi)有則直接刪除該點(diǎn)，否則保留該點(diǎn)[9]。

OPTA算法能滿足收斂性、連接性、拓?fù)湫院捅３中?，能得到較好的細(xì)化效果。但該算法得到的細(xì)化骨架存在在分叉點(diǎn)處細(xì)化不徹底，細(xì)化后的紋線不光滑，紋線有較多毛刺且紋線扭曲不在紋線中心的問(wèn)題。因此不滿足細(xì)化的中軸性和細(xì)化性。同時(shí)，它采用兩個(gè)不同大小模板分兩次進(jìn)行計(jì)算，其速度也受到影響。為了解決OPTA算法存在的問(wèn)題，人們提出了一種改進(jìn)的OPTA算法，改進(jìn)后的OPTA算法（見(jiàn)圖4）消除模板仍采用OPTA的消除模板。而在保留模板中，當(dāng)前中心點(diǎn)的去留除了與消除模板有關(guān)外，還取決于另一個(gè)“l(fā)"值周?chē)c(diǎn)的情況：若該“1"值為中心的3×3鄰域和消除模板相同，則該“1"值應(yīng)該被刪除，否則刪除當(dāng)前中心點(diǎn)。

圖4 改進(jìn)的OPTA算法的保留模板

3 改進(jìn)的OPTA算法的不足及改進(jìn)

改進(jìn)后的OPTA算法仍然存在一定的局限性，突出表現(xiàn)在某些紋線方向位置容易產(chǎn)生毛刺。經(jīng)過(guò)研究發(fā)現(xiàn)，毛刺的出現(xiàn)對(duì)紋線方向十分敏感。紋線方向角在第2像限的時(shí)候容易出現(xiàn)毛刺，特別是紋線近似水平和垂直的時(shí)候.毛刺的出現(xiàn)尤其明顯。故推測(cè)毛刺的產(chǎn)生和模板不完全對(duì)稱(chēng)有關(guān)。對(duì)于圖5(a)，可以看到2個(gè)小的毛刺，但是細(xì)化沒(méi)有去掉。對(duì)于5(c)中的紋線，細(xì)化完成后同樣產(chǎn)生了毛刺。主要原因是由于消除模板中沒(méi)有包含這種情況。

圖5 毛刺的細(xì)化

分叉處的細(xì)化不徹底主要原因是由于消除模板不完善。如圖6（a），第四行第三列的點(diǎn)是個(gè)多余的像素點(diǎn)，刪除這個(gè)點(diǎn)并不影響紋線的連通線；對(duì)于圖6（c），第二行第三列的點(diǎn)是多余的像素點(diǎn)，造成了不完全的細(xì)化，但若只是刪除該點(diǎn)，又會(huì)造成紋線的中斷，所以應(yīng)對(duì)其進(jìn)行一定程度的細(xì)化，即將第二行第三列的點(diǎn)刪除，即置為0，同時(shí)將第二行第四列的點(diǎn)置為1，保持了紋線的連通性[10]。

圖6 分叉點(diǎn)處的細(xì)化

針對(duì)上文中對(duì)毛刺的產(chǎn)生和分義處的細(xì)化小徹底的原因分析，本文使用了針對(duì)性的消除模板和保留模板。針對(duì)毛刺的消除模板如圖7。針對(duì)未完全細(xì)化的情況，引入特定的消除模板，如圖8所示。

圖8中，a-d是對(duì)應(yīng)于第一種未完全細(xì)化的情況的消除模板，e-h是對(duì)應(yīng)于第二種未完全細(xì)化情況的消除模板。a-d模板中的中心點(diǎn)為應(yīng)該刪除的點(diǎn)，e-h中荻色背景的點(diǎn)是進(jìn)行了變換，即將模板中有灰色背景的對(duì)應(yīng)位置中的0變換成1，而l變換成0。選樣，第二種未完全細(xì)化的情況就得到了有效的解決。

圖7 針對(duì)毛刺的消除模板

圖8 針對(duì)未完成細(xì)化的消除模板

圖9 修正后的消除模扳(一)

以在OPTA提出的消除模板為基礎(chǔ)，在基礎(chǔ)上添加上述12個(gè)消除模板；以文獻(xiàn)[6]提出的保留模板為基礎(chǔ).在消除模板的基礎(chǔ)上修正保留模板。修正后的結(jié)果如圖9～圖11所示。

圖10 修正后的消除摸板㈡

圖11 修正后的消除模板(三)

把消除模板分為3類(lèi)：類(lèi)一：如圖 9中(a)-(h)，類(lèi)二：如圖10中(i)-(p)，類(lèi)三：如圖11中(q)-(t)。(i)-(p)是屬于可直接刪除的，不需要進(jìn)行保留模板匹配，因?yàn)?m)-(p)是OPTA原消除模板的特例，這類(lèi)模板應(yīng)先于OPTA原消除模板進(jìn)行匹配，以免重復(fù)計(jì)算。細(xì)化從圖像的左上角開(kāi)始進(jìn)行，對(duì)于每一像素取其8個(gè)鄰域的像素，與類(lèi)二的消除模板匹配，若存在一個(gè)模板與其匹配，則刪除該點(diǎn)(即修改為0)。否則與類(lèi)一、類(lèi)三匹配，若不存在模板與其匹配，則停止：若存在一個(gè)模板與其匹配，記匹配的消除模板為m，并取該像素的i5鄰域的像素，與保留模板相匹配，如不存在任何保留模板匹配時(shí)，若m為類(lèi)一，則刪除該點(diǎn)，否則，對(duì)相對(duì)應(yīng)的模板的對(duì)應(yīng)位置進(jìn)行變換。

4 實(shí)驗(yàn)結(jié)果及分析

在采用OPTA算法對(duì)指紋圖像進(jìn)行細(xì)化操作所得的細(xì)化結(jié)果中產(chǎn)生的毛刺很多，在三叉點(diǎn)處細(xì)化不全，在處理后的結(jié)果圖中可以看到有些指紋的紋線發(fā)生了斷裂的情況，出現(xiàn)了一些相互不連接的斷線。破壞了指紋本身的連接性和拓?fù)湫?。改進(jìn)的OPTA細(xì)化算法與OPTA算法相比在細(xì)化整體效果上有了明顯提高，尤其是對(duì)細(xì)化過(guò)程中產(chǎn)生的毛刺和細(xì)化不徹底的處理得到了很好的效果，紋線連接性好。在計(jì)算速度方面，OPTA算法采用兩個(gè)大小不同的模板進(jìn)行兩次計(jì)算，計(jì)算速度慢，改進(jìn)的OPTA算法克服了OPTA的這個(gè)缺點(diǎn)。經(jīng)過(guò)以上的分析可知，本文中采用MATLAB7.0進(jìn)行實(shí)驗(yàn),指紋庫(kù)采集分辨率為500 dpi,指紋采集設(shè)備為PIS2004光學(xué)指紋采集儀,圖像尺寸大小為640×480，實(shí)驗(yàn)僅作同源樣本間的交叉比對(duì)。這表明指紋頻率能量能準(zhǔn)確反映樣改進(jìn)的OPTA細(xì)化算法是合理可行的，并且能得到較好的細(xì)化結(jié)果，滿足細(xì)化處理的要求。實(shí)驗(yàn)結(jié)果如圖12所示。

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

[1]陳茂林,戚飛虎.基于最優(yōu)梯度估計(jì)及小波變換的指紋圖像處理技術(shù)[J].上海交通大學(xué)學(xué)報(bào),2001,35(2):181-183.

[2]Ling Hong,Wang Yfei,Anil K Jain.Fingerprint image enhancement：algorithm and performance evaluation[J].IEEE Transactions on PaRem Analysis and MachineIntelligence,1 998,20(8):777-789.

[3]柯渝.指紋識(shí)別系統(tǒng)中的預(yù)處理與后處理研究[D].廈門(mén):廈門(mén)大學(xué),2004.

[4 ]Jie Zhou,Jinwei Gu.A model—based method for the computation of fingerprints’orientation field[J].IEEE Transactions On Image Processing,2004,13(6):821-835.

[4]周曄華.指紋圖像預(yù)處理算法研究[D].南京:南京理工大學(xué),2008.

[5]王業(yè)琳,寧新寶,尹義龍.指紋圖像細(xì)化算法的研究[J].南京大學(xué)報(bào),2003(7):468-475.

[6]唐海勇,唐世鋼,邵巖.線條紋圖像的細(xì)化[J].哈爾濱理工大學(xué)學(xué)報(bào),2002(4):50-53.

[7]Jie Zhou,David Zhang,C.Y Wu.Orientation analysis for rotated human facedetection[J].Image Vision Compute,2002(20):257-264.

[8]馮星奎,李林艷,顏?zhàn)嫒?一種新的指紋圖像細(xì)化算法[J].中國(guó)圖象圖形學(xué)報(bào),1999(10):835-838.

[9]趙偉.指紋圖像的預(yù)處理和細(xì)化算法的研究[D].重慶:重慶大學(xué)數(shù)理學(xué)院,2007.

[10]閏俊紅.指紋圖像預(yù)處理研究[D].呼和浩特:內(nèi)蒙古工業(yè)大學(xué),2006.