一種有效的混合式指紋快速細化算法

收稿日期：2007-12-06；修回日期：2008-03-03

基金項目：浙江省教育廳科研基金資助項目（20070440）

作者簡介：楊凡（1957-），男，浙江蘭溪人，教授，碩導，主要研究方向為圖像處理與模式識別（fyang@zjnu.cn）；趙順東（1983-），男，湖北襄樊人，碩士研究生，主要研究方向為圖像處理與模式識別*

（浙江師范大學 數理與信息工程學院，浙江 金華 321004）

摘 要：針對現有指紋細化算法存在的模板匹配次數過多、迭代頻繁、細化不完全等現象，在深入分析了快速細化算法和串并混合式細化算法特點的基礎上，提出了一種新的混合式指紋細化算法，有效地提高了細化速度和細化質量。

關鍵詞：指紋圖像；細化；串并混合；快速算法

中圖分類號：TP391

文獻標志碼：A

文章編號：1001-3695(2008)10-3034-02

Effective mixed fingerprint image quick thinning algorithm

YANG Fan，ZHAO Shun-dong

(College of Mathematics Physics Information Engineering， Zhejiang Normal University， Jinhua Zhejiang 321004， China)

Abstract:The current existing fingerprint image thinning algorithms have many disadvantages such as too many template matches， iterate frequently and thinning incompletely. To overcome these disadvantages， this paper proposed an effective mixed thinning algorithm based on the analysis of the quick thinning algorithm and the series-parallel mixed thinning algorithm. Through the experiments， the new algorithm proved that it can significantly improve the thinning speed and the thinning qua-lity.

Key words：fingerprint image; thinning; series-parallel mixed; quick algorithm

在指紋預處理過程中，指紋的細化是非常重要的一步，其目的是得到指紋的骨架。細化后的紋線必須是單像素寬，且要滿足中軸性、連接性及保持原指紋圖像的細節特征。由于指紋系統的實時性，客觀上要求指紋預處理速度越快越好，因此，指紋的細化算法必須滿足快速性。

現有的細化算法按迭代方式不同分為串行細化算法和并行細化算法[1]。其中，串行細化算法的處理結果依賴于對像素處理的先后順序，即邊檢驗邊處理，一次處理一個像素，下次操作由上次操作決定，細化速度較慢；而并行細化算法采用檢驗完成以后一起處理的方式，同時處理所有滿足一定條件的像素，細化速度較快，因此從算法原理上看， 并行方法優于串行方法。由于并行細化算法具有快速而準確的特性， 它一直是人們研究的熱點， 并且相應地提出了如快速細化算法[2]、OPTA 細化算法[3]其改進算法[4，5]等許多并行細化算法[6~10]。其中，快速細化算法的特點是速度很快，但細化不完全，細化后紋線呈雙像素寬；而OPTA算法及其改進算法的細化質量有所改善，但由于算法中存在大量的模板匹配與迭代，細化速度較慢。文獻[11]提出了一種串并混合細化算法。串并混合細化算法執行速度也很快，但該算法得到的細化骨架在分叉點和豎線處細化不徹底，毛刺較多。本文通過對相關算法的分析和實驗發現，將串并混合細化算法與快速細化算法相結合，不僅很好地彌補了采用快速細化算法細化后紋線呈雙像素寬這一缺點，而且其自身的缺點也得到了有效的控制。因此，本文提出了一種新的混合式快速細化算法：首先采用快速細化算法對指紋圖像進行初步細化，然后再用串并混合細化算法進行進一步細化，以達到完全細化的效果。該算法與現有的細化算法包括基于快速細化算法和改進OPTA算法的混合式算法[12，13]相比較，細化更為完全，且細化速度明顯加快。

1 兩種細化算法簡介

為了方便描述，在這里先給出幾個定義[5]：

定義1 目標點和背景點。目標點指像素值為1的點，與此對應，背景點像素值為0。

定義2 8-鄰點和4-鄰點。如圖1所示，設有任意像素點P，P的8-鄰點即為以P為中心的3×3區域中除了P點以外的8個點P1、P2、P3、P4、P5、P6、P7、P8。其中P2、P4、P6、P8為其4-鄰點。

定義3 單像素寬?？疾旒y線上每一點的8-鄰點，紋線端點的8-鄰點中只有一個目標點，紋線連續點的8-鄰點有兩個目標點，紋線分叉點的8-鄰點有三個目標點。符合上述條件的紋線即為單像素寬。

定義4 邊界點。屬于目標點，且其4-鄰點中至少有一個為背景點。

定義5 端點。屬于邊界點，且其8-鄰點中只有一個屬于目標點。

定義6 關鍵點。刪除該點后會引起紋線的不連通，又叫做斷點。

11 快速細化算法

快速細化的算法描述如下：

a)遍歷整個指紋圖像，找出紋線的邊界點。

b)針對圖1的抽取模板對邊界點P定義兩個特征量：nsum=∑Pi，tsum=∑|Pi+1-Pi|； i=1，2，…，8。其中：P9=P1。如果P點同時滿足：tsum=2且nsum!=1且nsum<6，則可將其刪除。

c)繼續尋找下一個邊界點，直到沒有可刪除的點為止。

快速細化算法的運行速度很快，但存在一個嚴重的缺陷：由于該算法是4-連通算法，因此由該算法得出的細化圖像很多不是單像素寬，即細化不徹底。其細化后不完全紋線的局部放大圖如圖2所示。

12 串并混合細化算法

該算法給出四個比較模板（圖3）和一個抽取模板（圖4）。

a)P8=1，P=1，P4=0；b) P2=0，P=1，P6=1；

c)P8=0，P=1，P4=1；d) P2=1，P=1，P6=0。

對應上述四個模板分別給出關鍵點的判斷條件如下：

a)若滿足(P2=0∧P3=1)||(P6=0∧P5=1)，則P為關鍵點。

b)若滿足(P8=0∧P1=1)||(P4=0∧P3=1)，則P為關鍵點。

c)若滿足(P2=0∧P1=1)||(P6=0∧P7=1)，則P為關鍵點。

d)若滿足(P8=0∧P7=1)||(P4=0∧P5=1)，則P為關鍵點。

對滿足某個模板的目標像素，使用上述判斷條件判斷此點是否為關鍵點，若為關鍵點則保留；若不是關鍵點，則再判斷此點是否為端點，若是端點則保留，否則將P點刪除。算法分為四次迭代，每次迭代對應一個模板，即先使用圖3中的模板(a)進行處理，刪除可刪除的點；再將輸出圖像再使用模板(b)進行處理，刪除可刪除點。依此類推，直至第四次迭代輸出即為細化圖像。算法每次迭代內部處理是并行的，各迭代之間是串行的，因此叫做串并混合細化算法。

13 兩種細化算法的分析

本文先從理論的角度對兩種細化算法進行了分析。快速細化算法的細化速度很快，但細化不完全，主要是因為其刪除條件過于嚴格造成的。典型情況如圖5所示。

如圖5(a)，P點為可刪除點，但是其nsum=3，tsum=4，不滿足快速細化算法的刪除條件，故被錯誤地保留下來。

同理，圖5(b)和(c)的P點均為可刪除點，但其nsum的值均為3，tsum的值分別為4和6，都不滿足快速細化算法的刪除條件，故都被錯誤地保留。

可以看出，快速細化算法的刪除條件造成了細化后的紋線呈雙像素寬，而本文通過分析發現，串并混合細化算法的模板可以很好地彌補這一缺陷。

將串并混合細化算法中的第一次迭代拿出來分析，即當滿足圖3中的模板(a)，又不滿足(P2=0∧P3=1)||(P6=0∧P5=1)和nsum=1兩個條件時，將P點刪除。將其轉換為模板的形式，即當滿足圖6中的（a）~（d）模板時，將P點刪除，而若滿足模板（e）（f），只要滿足X中至少有一個為1，則將P點刪除（其中圖6中的模板（a）~（f） 分別要相應地排除圖7中的（a）~（f） 六種情況）。

以上為串并混合細化算法中第一次迭代的刪除條件，通過分析發現，圖6中模板（a）（f）可以消除圖5中的（a）；圖6中的模板（b）（f）可以消除圖5中的（b）；圖6中的模板（b）（e）可以消除圖5中的（c）。同理，其他三個迭代所起到的作用也如上所述。因此本文將快速細化算法與串并混合細化算法結合起來，可以達到非常好的細化效果。

2 新算法的提出

本文所提出的算法具體步驟如下：a)采用快速細化算法進行初步細化；b)采用串并混合細化算法進行完全細化；c)采用脊線跟蹤法[14]消除紋線的偽特征點（包括孤立點、短線、毛刺、小孔、小橋等），并對紋線進行平滑處理；其中，步驟c)的作用是為了去除紋線的偽特征點，亦可以放在細化后提取特征點的過程中進行處理，因此本文在此不作詳細的介紹。

3 實驗結果與分析

本文在主頻1.4 GHz，內存512 MB的PC上用MATLAB 7.0針對典型指紋實現了上述算法，所得到的細化效果和細化時間如圖8~13和表1所示。

各算法細化所需要的時間如表1所示。

表1 各算法所耗的時間

算法所耗時間/s快速細化算法0.590 0串并混合細化算法0.120 0文獻[5]所提算法37.689 0文獻[13]所提算法34.914 0本文算法0.661 0

通過實驗發現，在單獨使用快速細化算法或者串并混合細化算法時，細化速度都很快，但細化效果比較差，不能夠滿足之后特征提取及匹配的需要。文獻[5]所提出的算法是基于改進OPTA算法的，其細化效果仍然不是很理想，出現較多毛刺，且由于其算法中采用了大量的模板匹配和迭代，導致細化速度較慢；文獻[13]所提出的混合算法是基于快速細化算法和文獻[5]細化算法的，其細化效果較好，但由于仍然存在大量的模板匹配和迭代，速度較慢。

從細化質量上看，本文所提出的算法經過了消除偽特征點和平滑處理的過程，其效果遠優于文獻[13]，基本可以達到提取特征點的要求；而從細化速度上看，本文算法的細化速度比文獻[13]所提算法的速度快很多，與快速細化算法在同一個水平。

4 結束語

衡量指紋細化算法的標準必須從細化效果和細化速度兩個方面去評價。本文詳細分析了快速細化算法與串并混合細化算法的特點并將兩者相結合，很好地利用了兩種算法互補的特性以及它們的快速性。通過大量的實驗證明，該算法不僅達到了相當理想的細化效果，而且大幅地減少了細化所需要的時間。從程序設計的角度上講，本文所提出的算法結構簡單，易于實現。該算法是一種快速、有效、實用的指紋細化算法。

參考文獻：

[1]王家隆，郭成安.一種改進的圖像模板細化算法[J].中國圖象圖形學報，2004，9(3):297-301.

[2]ZHANG T Y， SUEN C Y. A fast thinning algorithm for thinning digi-tal patter[J]. Communications of ACM，1984， 27(3):236-239.

[3]HALL R W.Optimally small operator supports for fully parallel thinning algorithms[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1993，15(8): 828-833.

[4]PAVLIDIS T. Algorithms for graphics and image processing[M]. Washington DC: Computer Science Press，1982.

[5]尹義龍.自動指紋識別系統研究[D].長春:吉林工業大學，2000.

[6]CHIN R T，WAN H K，STOVER D L， et al. A one-pass thinning algorithm and its parallel implementation[J].Computer Vision Graphics Image Processing， 1987，40(1):30-40.

[7]馮星奎，李林艷，顏祖泉.一種新的指紋圖像細化算法[J].中國圖象圖形學報，1999，4(10)：835-838.

[8]王業琳，寧新寶，尹義龍.指紋圖像細化算法的研究[J].南京大學學報：自然科學版，2003，39(4): 468-475.

[9]HUANG L， WAN G， LIU C. An improved parallel thinning algorithm[C]//Proc of the 7th Int Conf Document Analysis and Recognition. Edinburgh: IEEE Computer Society，2003:780-783.

[10]BERTRAND G， COUPRIE M. Two-dimensional parallel thinning algorithms based on critical kernels， IGM 2006-2[R]. [S.l.]: Institute Gaspard-Monge， Université de Marne-la-Vallée， 2006.

[11]李徐周，于飛.有效的指紋紋線細化方法[J].計算機工程與設計，2006，27(2):626-628.

[12]卞維新，徐德琴，王俊書.基于兩極復合式指紋圖像細化算法的研究[J].貴州工業大學學報，2005，34(6): 80-84.

[13] 楊小冬，寧新寶，尹義龍.自動指紋識別系統預處理技術及細節特征提取算法的研究[J].南京大學學報：自然科學版，2006，42(4):351-361.

[14]馮國進，顧國華，張保民.指紋圖像預處理與特征提取[J].計算機應用研究，2004，21(5):183-185.