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

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

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

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

（浙江師范大學(xué) 數(shù)理與信息工程學(xué)院，浙江 金華 321004）

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

關(guān)鍵詞：指紋圖像；細(xì)化；串并混合；快速算法

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：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

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

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

1 兩種細(xì)化算法簡介

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

定義1 目標(biāo)點和背景點。目標(biāo)點指像素值為1的點，與此對應(yīng)，背景點像素值為0。

定義2 8-鄰點和4-鄰點。如圖1所示，設(shè)有任意像素點P，P的8-鄰點即為以P為中心的3×3區(qū)域中除了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 單像素寬。考察紋線上每一點的8-鄰點，紋線端點的8-鄰點中只有一個目標(biāo)點，紋線連續(xù)點的8-鄰點有兩個目標(biāo)點，紋線分叉點的8-鄰點有三個目標(biāo)點。符合上述條件的紋線即為單像素寬。

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

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

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

11 快速細(xì)化算法

快速細(xì)化的算法描述如下：

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)繼續(xù)尋找下一個邊界點，直到?jīng)]有可刪除的點為止。

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

12 串并混合細(xì)化算法

該算法給出四個比較模板（圖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。

對應(yīng)上述四個模板分別給出關(guān)鍵點的判斷條件如下：

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

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

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

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

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

13 兩種細(xì)化算法的分析

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

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

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

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

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

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

2 新算法的提出

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

3 實驗結(jié)果與分析

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

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

表1 各算法所耗的時間

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

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

從細(xì)化質(zhì)量上看，本文所提出的算法經(jīng)過了消除偽特征點和平滑處理的過程，其效果遠(yuǎn)優(yōu)于文獻(xiàn)[13]，基本可以達(dá)到提取特征點的要求；而從細(xì)化速度上看，本文算法的細(xì)化速度比文獻(xiàn)[13]所提算法的速度快很多，與快速細(xì)化算法在同一個水平。

4 結(jié)束語

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

參考文獻(xiàn)：

[1]王家隆，郭成安.一種改進(jìn)的圖像模板細(xì)化算法[J].中國圖象圖形學(xué)報，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]尹義龍.自動指紋識別系統(tǒng)研究[D].長春:吉林工業(yè)大學(xué)，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]馮星奎，李林艷，顏祖泉.一種新的指紋圖像細(xì)化算法[J].中國圖象圖形學(xué)報，1999，4(10)：835-838.

[8]王業(yè)琳，寧新寶，尹義龍.指紋圖像細(xì)化算法的研究[J].南京大學(xué)學(xué)報：自然科學(xué)版，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]李徐周，于飛.有效的指紋紋線細(xì)化方法[J].計算機(jī)工程與設(shè)計，2006，27(2):626-628.

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

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

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