一種有效的指紋圖像細化算法

摘 要：OPTA方法是一個經典的指紋圖像細化方法，針對OPTA法的不足提出改進的OPTA方法能夠得到完全細化的指紋圖像，細化后圖像紋線扭曲小。但是改進的OPTA方法還存在細化后的圖像容易產生毛刺的不足，為此提出一組改進模板，即在改進的OPTA 模板的基礎上增加一組去除毛刺的模板。實驗表明，通過該算法得到的細化指紋圖像在保持連通性的基礎上光滑無毛刺，取得了更為理想的細化結果。

關鍵詞：圖像處理；細化；模板；毛刺

中圖分類號：TP391.4 文獻標識碼：B 文章編號：1004373X(2008)1814303

An Effective Thinning Algorithm for Fingerprint Image

HE Jing，FAN 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 引 言

迄今為止，生物特征識別技術已經成為最為方便與安全的識別技術^［1］。由于指紋具有惟一性、穩定性、可采集性、與主體永不分離性等優點，指紋識別成為生物特征識別中關注度很高，應用較多的主要技術^［2，3］。自動指紋識別系統(AFIS)是個人身份認定的一種重要手段。一個完整的指紋識別系統主要包括：指紋圖像采集、濾除圖像噪聲、對圖像進行二值化處理、細化圖像、特征點提取和特征點比對等幾個部分。其中，細化是指紋圖像預處理中耗時最長、要求最高的一部分。

指紋細化又稱骨架化，是自動指紋識別系統中重要的預處理組成部分，細化結果的好壞直接影響特征點提取的有效性。研究人員已經提出了很多細化方法，按迭代方式可分為串行算法、并行算法和串并行混合算法。串行細化算法是指每次迭代的結果依賴于像素處理的先后順序，因而某一像素點的刪除或保留與處理順序有關。并行細化算法進行細化時可以把相同的判定條件應用于所有的像素點，與處理順序無關，所以從原理上將優于串行細化算法。而串并行混合算法就是串行和并行混合的方法。已經提出的并行細化方法有很多：OPTA細化算法、Hall細化算法、Rosedfeld細化算法、ZR細化算法等^［47］。

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

2 OPTA算法

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

板其中模板中的“1”代表該點的像素值為1；“0”代表該點的像素值為0；“×”代表該點的像素值既可以為1也可以為0。該算法是從圖像的左上角開始到右下角結束作為一次循環，反復進行迭代，直到沒有像素值改變為止。

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

3 改進的OPTA算法

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

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

4 修正的算法

對比OPTA細化算法，改進的OPTA細化算法得到的指紋細化圖像除滿足收斂性、連接性、拓撲性和保持性外，在三叉點處細化完全，得到了完全細化的圖像。但是細化后的圖像仍然存在毛刺。

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

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

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

5 實驗結果

在Pentium(R)4，256 MB內存的計算機上用Matlab語言編程實現了該算法，實驗選取了FVC2000指紋庫中的指紋圖像。以下分別為二值化圖像(圖8)和用三種算法細化后的實驗結果(圖9~圖11)。

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

6 結 語

本文算法屬于并行細化算法，可以同時處理指紋圖像中的各個像素點，處理速度快、細化的結果光滑、無毛刺，大大改善了指紋細化的效果。從實驗結果可見，用本文算法細化的圖像在滿足細化的各種要求的基礎上，細化結果光滑無毛刺，無紋線吞噬現象。需要說明的是，本文對所選指紋圖像只進行了一般二值化(分塊閾值法)處理，如果在細化之前對指紋圖像進行一定的增強處理并使用針對于指紋圖像的二值化方法，去除指紋脊線的粘連并連接斷線，效果可能會更好。

參 考 文 獻

［1］朱磊，張雄偉.自動指紋識別系統中校準算法的改進［J］.通信學報，2003，24(1):9197.

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

［3］聶貴軍，吳陳，葉錫君.基于連續分布方向圖和改進的Poincare Index的指紋分類［J］.電子學報，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］馮星奎，李林艷，顏祖泉.一種新的指紋圖像細化算法［J］.中國圖像圖形學報，1999，4(10):835838.

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

作者簡介 何 晶 女，1982年出生，河北承德人，在讀碩士研究生。主要研究方向為信息安全、智能信息處理。

范九倫 男，1964年出生，陜西西安人，教授，博士，博士生導師。主要研究方向為模糊集理論、模糊信息處理、模式識別與圖像處理。