一種復合式指紋細化算法

孫鵬 蔡秀梅

摘要：為了提高指紋圖像細化處理后的質量，提出一種復合式指紋細化算法。該算法在并行算法的基礎上，首先構造出一套消除模板和兩個修正模板，然后通過并行算法對圖像進行初步細化，接著用構造的消除模板對圖像進行二次細化，最后通過修正模板對紋線的拓撲結構進行修正。該算法能夠保持圖像連通性，細化后紋線滿足單一像素寬且光滑無毛刺。

關鍵詞：指紋細化 復合式細化 消除模板

中圖分類號： TP391 文獻標識碼：A 文章編號：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 引言

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

2 二-迭代并行細化算法

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

該算法的流程為：

步驟1.遍歷圖像尋找目標點，提取其鄰域的8個像素，分別計算出，的值；

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

步驟3.判斷是否還有目標點需要刪除，若有返回步驟1，否則，結束。

對該算法進行深入分析后發現，其問題產生的原因主要為，第3個約束條件不包含毛刺及階梯形紋線像素的分布情況。所以無論是奇次還是偶次迭代都不能有效的細化。

3一種復合式細化算法

文章提出一種新的復合式細化算法，該算法綜合了并行算法與串行算法的優點，以迭代算法細化圖像后的結果為根據，構造7個消除模板和2個修正模板，有效的解決了上述問題。

3.1 構造消除模板

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

此外，在前四個模板中，若每個模板的兩個X同時取0，則會勿刪掉紋線端點，導致破壞紋線原有結構。所以，給出4個條件與前四個模板共同構成約束條件。當目標點（P）鄰域像素滿足以下條件時：

（1）與第一個模板匹配，則還需鄰域內的P1與P7像素的值不能同時為1，即；

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

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

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

3.2 構造修正模板

針對細化后紋線成階梯形問題，構造了1個修正模板及1個修正后像素值的變化模板，如圖3所示。需注意的是，修正模板是對背景點周圍的鄰域像素進行判斷，而不再是目標點。

研究后發現階梯形紋線大多為直角形走向，如圖3（a）所示，但實際紋線的拓撲結構應該是135度方向走向，故需要用修正模板將紋線結構進行方向性調整。

新的復合式算法步驟為：

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

步驟2.用3.1節的消除模板對圖像進行串行細化，得到二次細化圖像；

步驟3.用3.2節的模板對圖像進行修正處理，得到最終細化圖像。

4實驗結果與分析

為驗證新算法的有效性，使用MATLAB語言對快速算法、迭代算法及本文算法進行編程實現。從FVC2004指紋庫中提取多幅指紋圖像作為實驗樣板，首先對各樣板進行二值化處理，之后用上述3種算法分別進行細化。圖4為隨機挑選的一組細化結果圖。從圖中可看出，快速算法處理圖像后，紋線拓撲性被破壞，部分紋線被刪除，從而導致圖像特征點丟失，影響指紋識別系統性能。迭代算法處理圖像后，毛刺多且存在階梯形紋線，從而多出許多偽特征點。新算法細化后，階梯形紋線數量明顯減少，圖像光滑無毛刺。

5結語

本文對二-迭代并行細化算法進行研究，結合串行與并行算法的各自優點提出一種復合式指紋細化算法。經實驗證明，新算法在原有算法的基礎上，解決了其細化后紋線毛刺多及存在階梯形紋線的問題，細化效果好且速度快。

參考文獻

[1]馮星奎，李林艷，顏祖泉.一種新的指紋圖象細化算法[J].中國圖象圖形學報，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.