摘 要：OPTA方法是一個(gè)經(jīng)典的指紋圖像細(xì)化方法，針對(duì)OPTA法的不足提出改進(jìn)的OPTA方法能夠得到完全細(xì)化的指紋圖像，細(xì)化后圖像紋線扭曲小。但是改進(jìn)的OPTA方法還存在細(xì)化后的圖像容易產(chǎn)生毛刺的不足，為此提出一組改進(jìn)模板，即在改進(jìn)的OPTA 模板的基礎(chǔ)上增加一組去除毛刺的模板。實(shí)驗(yàn)表明，通過(guò)該算法得到的細(xì)化指紋圖像在保持連通性的基礎(chǔ)上光滑無(wú)毛刺，取得了更為理想的細(xì)化結(jié)果。

關(guān)鍵詞：圖像處理；細(xì)化；模板；毛刺

中圖分類(lèi)號(hào)：TP391.4 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1004373X(2008)1814303

An Effective Thinning Algorithm for Fingerprint Image

HE Jing，F(xiàn)AN Jiulun

(Xi′an Institute of Post and Telecommunications，Xi′an，710061，China)

Abstract：OPTA method is a classical thinning method for fingerprint image.Improved OPTA method，which is proposed to overcome the insufficiency of the OPTA method，can obtain a complete thinning result，and can eliminate the distortion of the skeleton.But the improved OPTA thinning algorithm has a deficiency of being easy to get burrs after thinning.To deal with this problem，a set of ameliorative templates is added in this paper.Experimental results show that the new algorithm can not only keep connective，but also keep smooth without burrs.More ideal thinning result is obtained.

Keywords：image processing;thinning;template;burr

1 引 言

迄今為止，生物特征識(shí)別技術(shù)已經(jīng)成為最為方便與安全的識(shí)別技術(shù)^［1］。由于指紋具有惟一性、穩(wěn)定性、可采集性、與主體永不分離性等優(yōu)點(diǎn)，指紋識(shí)別成為生物特征識(shí)別中關(guān)注度很高，應(yīng)用較多的主要技術(shù)^{［2，3］}。自動(dòng)指紋識(shí)別系統(tǒng)(AFIS)是個(gè)人身份認(rèn)定的一種重要手段。一個(gè)完整的指紋識(shí)別系統(tǒng)主要包括：指紋圖像采集、濾除圖像噪聲、對(duì)圖像進(jìn)行二值化處理、細(xì)化圖像、特征點(diǎn)提取和特征點(diǎn)比對(duì)等幾個(gè)部分。其中，細(xì)化是指紋圖像預(yù)處理中耗時(shí)最長(zhǎng)、要求最高的一部分。

指紋細(xì)化又稱(chēng)骨架化，是自動(dòng)指紋識(shí)別系統(tǒng)中重要的預(yù)處理組成部分，細(xì)化結(jié)果的好壞直接影響特征點(diǎn)提取的有效性。研究人員已經(jīng)提出了很多細(xì)化方法，按迭代方式可分為串行算法、并行算法和串并行混合算法。串行細(xì)化算法是指每次迭代的結(jié)果依賴(lài)于像素處理的先后順序，因而某一像素點(diǎn)的刪除或保留與處理順序有關(guān)。并行細(xì)化算法進(jìn)行細(xì)化時(shí)可以把相同的判定條件應(yīng)用于所有的像素點(diǎn)，與處理順序無(wú)關(guān)，所以從原理上將優(yōu)于串行細(xì)化算法。而串并行混合算法就是串行和并行混合的方法。已經(jīng)提出的并行細(xì)化方法有很多：OPTA細(xì)化算法、Hall細(xì)化算法、Rosedfeld細(xì)化算法、ZR細(xì)化算法等^［47］。

針對(duì)OPTA方法(OnePass Thinning Algorithm，OPTA)中細(xì)化不完全、細(xì)化速度較慢的不足，文獻(xiàn)［8］提出了改進(jìn)的OPTA算法(Improved OPTA Thinning Algorithm)，獲得了較好的細(xì)化效果。但改進(jìn)算法還存在方向敏感性強(qiáng)，在水平和豎直方向容易出現(xiàn)毛刺等問(wèn)題^［9］。本文針對(duì)改進(jìn)的OPTA方法存在的這些不足，在其基礎(chǔ)上增加一組去除毛刺的模板，獲得了更好的細(xì)化效果。

2 OPTA算法

對(duì)于一幅二值指紋圖像，設(shè)其背景點(diǎn)的像素值為0，前景點(diǎn)的像素值為1。OPTA算法是從圖像的左上角開(kāi)始，對(duì)每一個(gè)前景點(diǎn)元素(像素值為1 的點(diǎn)，即模板中的P5)抽取出如圖1所示的模板鄰域，并將該鄰域與給定的刪除模板(見(jiàn)圖2)相比較，如果該鄰域的像素值與8個(gè)刪除模板中的任一個(gè)相匹配則刪除該點(diǎn)，否則保留該點(diǎn)。為了保持連通性，抽取的元素的鄰域再和圖3的2個(gè)保留模板進(jìn)行比較，如果抽取鄰域的第二行和模板(a)的第二行匹配，或者抽取鄰域的第二列和模板(b)中的第二列匹配，則P5點(diǎn)保留，否則P5才真正刪去(對(duì)該點(diǎn)的像素值置0)。

板其中模板中的“1”代表該點(diǎn)的像素值為1；“0”代表該點(diǎn)的像素值為0；“×”代表該點(diǎn)的像素值既可以為1也可以為0。該算法是從圖像的左上角開(kāi)始到右下角結(jié)束作為一次循環(huán)，反復(fù)進(jìn)行迭代，直到?jīng)]有像素值改變?yōu)橹埂?/p>

用OPTA算法對(duì)指紋圖像進(jìn)行細(xì)化可以達(dá)到較好的細(xì)化效果，但是細(xì)化后的圖像細(xì)化不完全，細(xì)化后的指紋脊線不光滑，有毛刺、紋線扭曲。

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

鑒于OPTA方法有著上述的不足，文獻(xiàn)［8］提出了改進(jìn)的OPTA算法，該算法對(duì)OPTA算法中的刪除模板進(jìn)行了一定的改進(jìn)，這樣可以有效去除紋線邊緣上的突出物。另外，它采用大小相同的保留模板，在一定程度上提高了處理速度^［8］。

該算法的具體步驟與OPTA方法相同，都是抽取當(dāng)前像素點(diǎn)的鄰域與刪除模板和保留模板比對(duì)，決定像素點(diǎn)的刪除與否。該算法采用統(tǒng)一的4×4模板，其抽取鄰域以及刪除模板、保留模板如圖4~圖6所示。

4 修正的算法

對(duì)比OPTA細(xì)化算法，改進(jìn)的OPTA細(xì)化算法得到的指紋細(xì)化圖像除滿(mǎn)足收斂性、連接性、拓?fù)湫院捅３中酝?，在三叉點(diǎn)處細(xì)化完全，得到了完全細(xì)化的圖像。但是細(xì)化后的圖像仍然存在毛刺。

毛刺產(chǎn)生的原因主要是由模板的不完善造成的。毛刺的出現(xiàn)對(duì)紋線方向十分敏感，主要分布在細(xì)化圖像的右上部和右中部，特別是在紋線近似水平和垂直的時(shí)候，尤為明顯。改進(jìn)的OPTA算法中的刪除模板只是從圖像的東、南、西、北、東北、東南、西南、西北8個(gè)方向上刪除了圖像的邊緣像素點(diǎn)，但是并沒(méi)有專(zhuān)門(mén)為解決毛刺問(wèn)題提出模板。為此本文提出的算法將在改進(jìn)的OPTA算法刪除模板的基礎(chǔ)上增加一組去毛刺的模板，在細(xì)化的同時(shí)去除毛刺，對(duì)于保留模板仍然采用改進(jìn)的OPTA算法中的模板。

具體算法如下：從圖像的左上角開(kāi)始逐個(gè)抽取圖像中的像素點(diǎn)(像素值為1的非端點(diǎn))，與刪除模板(原刪除模板+圖7所示新增加的去毛刺模板)比對(duì)。抽取像素點(diǎn)在圖像中表示為點(diǎn)P5，其8鄰域分別為P1~P9。若滿(mǎn)足8個(gè)刪除模板中的任意一個(gè)，再將其與保留模板比對(duì)，若滿(mǎn)足則該點(diǎn)保留，不滿(mǎn)足才真正刪除。這樣一直迭代下去直到?jīng)]有像素值變化為止。

另外，本文提出的新算法是對(duì)所有的非端點(diǎn)的前景點(diǎn)使用模板，這是由于要去除水平和豎直方向上的毛刺，計(jì)算機(jī)很可能將這種模板應(yīng)用于端點(diǎn)引起紋線吞噬，而指紋紋線的端點(diǎn)恰恰只是一個(gè)點(diǎn)，沒(méi)有“厚度”，所以可以將它撇開(kāi)，對(duì)其余點(diǎn)應(yīng)用模板，這樣也在一定程度上提高了處理速度。

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

在Pentium(R)4，256 MB內(nèi)存的計(jì)算機(jī)上用Matlab語(yǔ)言編程實(shí)現(xiàn)了該算法，實(shí)驗(yàn)選取了FVC2000指紋庫(kù)中的指紋圖像。以下分別為二值化圖像(圖8)和用三種算法細(xì)化后的實(shí)驗(yàn)結(jié)果(圖9~圖11)。

由以上實(shí)驗(yàn)結(jié)果可見(jiàn)，用OPTA 方法進(jìn)行細(xì)化，得到的指紋圖像細(xì)化不完全，且毛刺較多，紋線扭曲較大；用改進(jìn)的OPTA方法進(jìn)行細(xì)化，得到的指紋圖像毛刺有一定的減少，但是在圖像的右上部和右中部毛刺仍有很多；用本文的修正算法進(jìn)行細(xì)化后，可以看到，細(xì)化后毛刺消除，得到的圖像光滑，效果較好。 同時(shí)，實(shí)驗(yàn)還統(tǒng)計(jì)了分別用以上三種方法細(xì)化后的指紋圖像中特征點(diǎn)(分叉點(diǎn)和端點(diǎn))的個(gè)數(shù)，用OPTA方法細(xì)化得到的指紋圖像中特征點(diǎn)個(gè)數(shù)為17 676個(gè)；用改進(jìn)的OPTA方法得到的指紋圖像中特征點(diǎn)的個(gè)數(shù)為15 285個(gè)；而用本文算法得到的細(xì)化圖像中特征點(diǎn)的個(gè)數(shù)為10 178個(gè)，比OPTA方法減少了42.41%，比改進(jìn)的OPTA方法減少了33.41%，可見(jiàn)本文方法可以在很大程度上減少毛刺，消除偽特征點(diǎn)。

6 結(jié) 語(yǔ)

本文算法屬于并行細(xì)化算法，可以同時(shí)處理指紋圖像中的各個(gè)像素點(diǎn)，處理速度快、細(xì)化的結(jié)果光滑、無(wú)毛刺，大大改善了指紋細(xì)化的效果。從實(shí)驗(yàn)結(jié)果可見(jiàn)，用本文算法細(xì)化的圖像在滿(mǎn)足細(xì)化的各種要求的基礎(chǔ)上，細(xì)化結(jié)果光滑無(wú)毛刺，無(wú)紋線吞噬現(xiàn)象。需要說(shuō)明的是，本文對(duì)所選指紋圖像只進(jìn)行了一般二值化(分塊閾值法)處理，如果在細(xì)化之前對(duì)指紋圖像進(jìn)行一定的增強(qiáng)處理并使用針對(duì)于指紋圖像的二值化方法，去除指紋脊線的粘連并連接斷線，效果可能會(huì)更好。

參 考 文 獻(xiàn)

［1］朱磊，張雄偉.自動(dòng)指紋識(shí)別系統(tǒng)中校準(zhǔn)算法的改進(jìn)［J］.通信學(xué)報(bào)，2003，24(1):9197.

［2］馬君.小波變換技術(shù)在指紋圖像預(yù)處理中的應(yīng)用［J］.西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版，2005，32(4):653656.

［3］聶貴軍，吳陳，葉錫君.基于連續(xù)分布方向圖和改進(jìn)的Poincare Index的指紋分類(lèi)［J］.電子學(xué)報(bào)，2006，34(5):947952.

［4］Chin R T，Wan H K，Stover D L，et al.A Onepass Thinning Algorithm and Its Parallel Implementation［J］.Computer Image Processing，1987，40(1):3040.

［5］Hall R W.Optimally Small Operator Supports for Fully Parallel Thinning Algorithms［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1993，15(8):828833.

［6］Pavlidis T.Algorithms for Graphics and Image Processing［M］.Washington DC，USA:Rockville，Computer Science Press，1982.

［7］Guo Z C，Richard W H.Parallel Thinning with Twosubiteration Algorithms［J］.Communications of ACM，1989，32(3):359373.

［8］馮星奎，李林艷，顏?zhàn)嫒?一種新的指紋圖像細(xì)化算法［J］.中國(guó)圖像圖形學(xué)報(bào)，1999，4(10):835838.

［9］王業(yè)琳，寧新寶，尹義龍.指紋圖像細(xì)化算法的研究［J］.南京大學(xué)學(xué)報(bào):自然科學(xué)版，2003，39(4):468475.

作者簡(jiǎn)介 何 晶 女，1982年出生，河北承德人，在讀碩士研究生。主要研究方向?yàn)樾畔踩?、智能信息處理?/p>

范九倫 男，1964年出生，陜西西安人，教授，博士，博士生導(dǎo)師。主要研究方向?yàn)槟：碚?、模糊信息處理、模式識(shí)別與圖像處理。