一种复合式指纹细化算法

孙鹏 蔡秀梅

摘要：为了提高指纹图像细化处理后的质量，提出一种复合式指纹细化算法。该算法在并行算法的基础上，首先构造出一套消除模板和两个修正模板，然后通过并行算法对图像进行初步细化，接着用构造的消除模板对图像进行二次细化，最后通过修正模板对纹线的拓扑结构进行修正。该算法能够保持图像连通性，细化后纹线满足单一像素宽且光滑无毛刺。

关键词：指纹细化 复合式细化 消除模板

中图分类号： 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.