一種復(fù)合式指紋細(xì)化算法

孫鵬 蔡秀梅

摘要：為了提高指紋圖像細(xì)化處理后的質(zhì)量，提出一種復(fù)合式指紋細(xì)化算法。該算法在并行算法的基礎(chǔ)上，首先構(gòu)造出一套消除模板和兩個(gè)修正模板，然后通過(guò)并行算法對(duì)圖像進(jìn)行初步細(xì)化，接著用構(gòu)造的消除模板對(duì)圖像進(jìn)行二次細(xì)化，最后通過(guò)修正模板對(duì)紋線的拓?fù)浣Y(jié)構(gòu)進(jìn)行修正。該算法能夠保持圖像連通性，細(xì)化后紋線滿足單一像素寬且光滑無(wú)毛刺。

關(guān)鍵詞：指紋細(xì)化 復(fù)合式細(xì)化 消除模板

中圖分類號(hào)： TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）05-0000-00

Abstract： In order to improve the quality of fingerprint image thinning process， a composite fingerprint thinning algorithm is proposed. This algorithm is based on parallel algorithm， firstly， it constructed a set of elimination template and two correction templates， and through parallel algorithms for preliminary refining， and then use elimination template for the secondary refining， finally， through the correction template to modify the topology of the ridge. This algorithm can keep image connectivity， and the ridge meet a single pixel width and smooth without burr after refining.

Key Words： fingerprint thinning， composite thinning， elimination template

1 引言

作為指紋識(shí)別系統(tǒng)預(yù)處理階段的指紋細(xì)化工作，其細(xì)化后的圖像質(zhì)量對(duì)后續(xù)特征識(shí)別階段有著重要影響。一個(gè)好的指紋細(xì)化算法應(yīng)滿足收斂性、連通性、拓?fù)湫?、保持性、?xì)化性、中軸性、快速性[1]。按照迭代方式，可以將指紋細(xì)化算法歸為兩類：串行細(xì)化和并行細(xì)化。常用的細(xì)化算法有OPTA（One pass thinning algorithm）細(xì)化算法[2]、快速并行細(xì)化算法[3]（以下簡(jiǎn)稱為快速算法）、二-迭代并行細(xì)化算法[4]。文章對(duì)二-迭代并行細(xì)化算法進(jìn)行分析，構(gòu)造一套消除模板和一個(gè)修正模板，將其與并行算法相結(jié)合，提出一種復(fù)合式指紋細(xì)化算法。

2 二-迭代并行細(xì)化算法

二-迭代并行細(xì)化算法[4]（以下簡(jiǎn)稱迭代算法）是對(duì)快速算法的一種改進(jìn)，該算法具有細(xì)化后紋線為單一像素寬、速度快等優(yōu)點(diǎn)，但細(xì)化后圖像不能很好的滿足中軸性且斜線方向紋線毛刺多。該算法規(guī)定目標(biāo)點(diǎn)P的8鄰域分布情況如圖1所示。

該算法的流程為：

步驟1.遍歷圖像尋找目標(biāo)點(diǎn)，提取其鄰域的8個(gè)像素，分別計(jì)算出，的值；

步驟2.判斷本次循環(huán)為奇數(shù)還是偶數(shù)，若為奇次循環(huán)，判斷條件1、條件2、條件3（a）是否同時(shí)滿足，如果滿足則刪除改點(diǎn)，否則保留改點(diǎn)；若為偶次循環(huán)，判斷條件1、條件2、條件3（b）是否同時(shí)滿足，如果滿足則刪除改點(diǎn)，否則保留改點(diǎn)。

步驟3.判斷是否還有目標(biāo)點(diǎn)需要?jiǎng)h除，若有返回步驟1，否則，結(jié)束。

對(duì)該算法進(jìn)行深入分析后發(fā)現(xiàn)，其問(wèn)題產(chǎn)生的原因主要為，第3個(gè)約束條件不包含毛刺及階梯形紋線像素的分布情況。所以無(wú)論是奇次還是偶次迭代都不能有效的細(xì)化。

3一種復(fù)合式細(xì)化算法

文章提出一種新的復(fù)合式細(xì)化算法，該算法綜合了并行算法與串行算法的優(yōu)點(diǎn)，以迭代算法細(xì)化圖像后的結(jié)果為根據(jù)，構(gòu)造7個(gè)消除模板和2個(gè)修正模板，有效的解決了上述問(wèn)題。

3.1 構(gòu)造消除模板

針對(duì)上述紋線毛刺問(wèn)題，構(gòu)造了如圖2所示的7個(gè)消除模板。其中前四個(gè)模板用于去除90度及180度方向紋線兩側(cè)的毛刺。后三個(gè)模板用于去除135度方向紋線兩側(cè)的毛刺。

此外，在前四個(gè)模板中，若每個(gè)模板的兩個(gè)X同時(shí)取0，則會(huì)勿刪掉紋線端點(diǎn)，導(dǎo)致破壞紋線原有結(jié)構(gòu)。所以，給出4個(gè)條件與前四個(gè)模板共同構(gòu)成約束條件。當(dāng)目標(biāo)點(diǎn)（P）鄰域像素滿足以下條件時(shí)：

（1）與第一個(gè)模板匹配，則還需鄰域內(nèi)的P1與P7像素的值不能同時(shí)為1，即；

（2）與第二個(gè)模板匹配，則還需鄰域內(nèi)的P1與P3像素的值不能同時(shí)為1，即；

（3）與第三個(gè)模板匹配，則還需鄰域內(nèi)的P3與P5像素的值不能同時(shí)為1，即；

（4）與第四個(gè)模板匹配，則還需鄰域內(nèi)的P5與P7像素的值不能同時(shí)為1，即。

3.2 構(gòu)造修正模板

針對(duì)細(xì)化后紋線成階梯形問(wèn)題，構(gòu)造了1個(gè)修正模板及1個(gè)修正后像素值的變化模板，如圖3所示。需注意的是，修正模板是對(duì)背景點(diǎn)周圍的鄰域像素進(jìn)行判斷，而不再是目標(biāo)點(diǎn)。

研究后發(fā)現(xiàn)階梯形紋線大多為直角形走向，如圖3（a）所示，但實(shí)際紋線的拓?fù)浣Y(jié)構(gòu)應(yīng)該是135度方向走向，故需要用修正模板將紋線結(jié)構(gòu)進(jìn)行方向性調(diào)整。

新的復(fù)合式算法步驟為：

步驟1.采用查表法將迭代算法編程，對(duì)二值化指紋圖像進(jìn)行初步細(xì)化，得到細(xì)化圖像；

步驟2.用3.1節(jié)的消除模板對(duì)圖像進(jìn)行串行細(xì)化，得到二次細(xì)化圖像；

步驟3.用3.2節(jié)的模板對(duì)圖像進(jìn)行修正處理，得到最終細(xì)化圖像。

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

為驗(yàn)證新算法的有效性，使用MATLAB語(yǔ)言對(duì)快速算法、迭代算法及本文算法進(jìn)行編程實(shí)現(xiàn)。從FVC2004指紋庫(kù)中提取多幅指紋圖像作為實(shí)驗(yàn)樣板，首先對(duì)各樣板進(jìn)行二值化處理，之后用上述3種算法分別進(jìn)行細(xì)化。圖4為隨機(jī)挑選的一組細(xì)化結(jié)果圖。從圖中可看出，快速算法處理圖像后，紋線拓?fù)湫员黄茐?，部分紋線被刪除，從而導(dǎo)致圖像特征點(diǎn)丟失，影響指紋識(shí)別系統(tǒng)性能。迭代算法處理圖像后，毛刺多且存在階梯形紋線，從而多出許多偽特征點(diǎn)。新算法細(xì)化后，階梯形紋線數(shù)量明顯減少，圖像光滑無(wú)毛刺。

5結(jié)語(yǔ)

本文對(duì)二-迭代并行細(xì)化算法進(jìn)行研究，結(jié)合串行與并行算法的各自優(yōu)點(diǎn)提出一種復(fù)合式指紋細(xì)化算法。經(jīng)實(shí)驗(yàn)證明，新算法在原有算法的基礎(chǔ)上，解決了其細(xì)化后紋線毛刺多及存在階梯形紋線的問(wèn)題，細(xì)化效果好且速度快。

參考文獻(xiàn)

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

[2] CHIN R T， WAN H K， STOVER D I， et al. A one pass thinning algorithm and its parallel implementation[J].Computer Vision，1987，40（1）：30-40.

[3]ZHANG T Y， SUEN C Y. A fast parallel algorithm for thinning digital patterns[J].Communications of the ACM，1984，27（3）：236-239.

[4]GUO Z C， RICHARD W H. Parallel thinning with two subiteration algorithms[J].Communications of the ACM，1989，32（3）：359-373.