一种改进的基于细节点的脊线追踪算法

李敏敏

（江苏科技大学 江苏 镇江 212003）

目前基于细节点的指纹匹配算法，识别效果很大程度上取决于细节点的数量和准确性，同时受指纹图像质量和大小等因素的影响较大，并且忽略了指纹丰富的脊线信息，极大地限制了指纹识别准确性和鲁棒性的提高。指纹丰富的脊线信息主要是指脊线的一些属性，常见的有：脊线的长度、方向、频率、脊线间的相对关系、脊线的曲率以及脊线上最大曲率点与脊线两端点的距离比等。脊线的上述属性几乎不受指纹图像平移、旋转、缩放以及非线性变形的影响，具有一定的几何不变性。因此，利用脊线属性构建指纹匹配模式可以提高指纹匹配的准确性和鲁棒性。

指纹脊线属性的获取首先需要获得相应的脊线数据，包括脊线的端点、脊线上每个像素点的坐标以及这些像素点的排列顺序，为此，就要进行脊线的追踪。脊线追踪就是从脊线的一端出发，沿着脊线的方向前进，记录下脊线上每个像素点的坐标，按其既定方向排列，最终到达脊线的另一端[1]。因为脊线具有丰富的指纹信息，所以已有很多学者对脊线追踪进行了研究。

文献[2-4]提出利用窗口判断像素点的8邻域纹线点数，利用指纹脊线端点、连续点和叉点的8邻域点分布情况进行脊线像素点的判断，从而对指纹脊线进行追踪并记录追踪到的脊线数据。文献[5]脊线追踪时确定追踪起始点后，在定位下一追踪点时，采用适当的跟踪步长，以保证该点位于前一跟踪点纹线方向的一定角度范围内，跟踪过程中及时调整每一跟踪点的角度，使得纹线跟踪更为精确。文献[6]将模式区分块分别计算每块的灰度方差并从大到小排序得到模式区图像块序列，依次寻找每块的灰度值最小点作为跟踪起始点，并采用文献[7-8]中的纹线追踪算法进行跟踪并记录。文献[9]利用指纹脊线方向的连续性和相邻脊线间的相关性，将要追踪的脊线作为目标采用计算机视觉中的目标追踪技术和反馈技术进行脊线追踪，追踪过程中通过反馈脊线的方向信息不断对其方向进行矫正，确保脊线追踪的准确性。

由以上脊线追踪算法可以看出，脊线追踪的关键问题是如何根据已追踪并记录的纹线点去确定下一个纹线点。然而追踪过程中对像素点方向性的判断算法比较复杂，对于上面提到的较简单的窗口的跟踪方法虽然简单，但由于脊线追踪的每一个步骤都要利用窗口来获得当前点和上一个被跟踪的点，并且按照已定义的规则依次搜索当前点的8邻域像素，从而判断脊线上的下一个跟踪点，因此，算法的运行速度比较慢。

我们在文献[10]中提出以指纹端点和叉点为起点，沿着脊线的方向逐点进行跟踪，从而遍历指纹细化图中所有脊线。由于文献[10]中的脊线追踪算法存在一定的不完善性，导致脊线追踪的结果存在不完全现象，因此本文在文献[10]的基础上对算法进行了改进，实验结果表明，改进后的算法对指纹细化图具有非常理想的脊线追踪效果。

1 算法改进

文献[10]中脊线追踪的算法思想：首先以提取到的细节端点为起始跟踪点，记录该端点位置；从该细节点开始，以其为前驱点，其邻点为当前点，通过一个获取下一像素点的函数寻找脊线上下一像素点；判断该像素点类型，如果为连续点，则更改前驱点和当前点，即以该像素点为当前点，原当前点为前驱点，再通过获取下一像素点的函数继续搜索脊线上下一像素点，直至遇到这条脊线的另一个细节端点或叉点，则该细节点所在脊线的追踪结束；对细节点记录中所有端点，重复进行上面的步骤，如此反复下去，直至完成对指纹细化图中所有端点所在脊线的追踪；然后再以叉点为起点进行剩余脊线的追踪，追踪方法同上，此处需注意叉点连接3条脊线。这样便完成了所有以端点和叉点为起点的脊线的追踪。

文献[10]中获取下一个像素点的函数思想是：对当前点的8邻域进行判断，如果其8邻域内除前驱点外只有一个黑点，则说明当前点的下一个像素点存在，并返回下一个像素点；若没有黑点或多于1个则认为没找到下一像素点，并返回错误。该脊线追踪算法对实例指纹图像的脊线追踪效果如图1（b）所示。

图1 指纹细化图及脊线追踪图Fig.1 The fingerprint thinned image and ridge tracing image

由图1（b）可以看出，叉点连接的脊线追踪不完整；通过对多枚指纹图像脊线追踪结果观察发现，文献[10]中算法对以叉点为起点进行的脊线追踪其结果存在不完整现象，不能获得完整的脊线数据。通过对以上现象分析发现：由叉点开始脊线追踪或脊线追踪到叉点邻近邻域时有时会出现图2所示的情况，图2（a）中1号像素点的8邻域内除前驱点叉点外有两个黑点，2号像素点8邻域内除前驱点也有两个黑点；图2（b）中2号像素点的8邻域内除前驱点外有2个黑点，此时文献[10]中获取下一像素点的函数就不会返回正确的像素点坐标，从而该脊线没有被追踪到。因此，文中对文献[10]中获取下一像素点函数思想进行了改进。

图2 叉点连接脊线追踪问题Fig.2 The tracking problem of bifurcation connection ridge line

文中改进后的算法思想是：首先判断前驱点的类型，如果是端点则直接判断当前点的8邻域，除前驱点外，若有1个黑点则直接返回该像素点，若有2个黑点则返回与当前点在水平或垂直方向紧挨的点，若有多个黑点则返回错误；如果前驱点是叉点，判断当前点的8邻域时，若黑点同时是该叉点的8邻域点则不计，除此以外判断规则同上。算法改进后获取下一个像素点的流程图如图3所示。

图3 寻找脊线上待追踪的下一点流程图Fig.3 The flow chart of looking for the next point to track on the ridge

2 实验结果

根据改进后的脊线追踪算法进行细化指纹图像的脊线追踪，其结果如图1（c）所示，从图上可以看出改进后的脊线追踪算法追踪到了原脊线追踪算法没有追踪完全的叉点连接脊线。通过对多枚指纹细化图脊线追踪的效果分析可知，改进后的脊线追踪算法对指纹所有端点及叉点连接的脊线都能完全追踪。

另外，由图1可以看出，该指纹图像只有左下角两条脊线没有追踪到。经分析可知，因为该两条脊线位于指纹图像的边缘部分，其端点没有被提取到，所以该两条脊线没有被追踪到，该细化指纹图的特征点提取情况如图4所示。通过对大量指纹细化图的脊线追踪结果分析可得，本文改进的脊线追踪算法对于提取到特征点的脊线来说都能够追踪到，也就是说，本文脊线追踪算法具有很好的效果。

图4 指纹细化图特征点提取情况Fig.4 Feature points extraction conditions on fingerprint thinned image

3 结 论

文中对以指纹端点和叉点为起点进行脊线追踪的算法进行了改进，通过对多枚指纹细化图脊线追踪的效果分析可知，改进后的脊线追踪算法对提取到端点或叉点的脊线都能完全追踪，说明改进后的脊线追踪算法对指纹细化图具有非常理想的脊线追踪效果。本文脊线追踪算法的提出为更好地获得指纹信息提供了有效的手段，为提高指纹匹配的精确性和鲁棒性奠定了坚实的基础。由于本文脊线追踪算法的实现是在指纹细化和特征点提取的情况下进行的，因此脊线追踪的效果受指纹细化和特征点提取的影响。

[1]张云光.指纹后处理算法研究[D].沈阳：沈阳工业大学，2006.

[2]刘文星，王肇圻，母国光.纹线跟踪及其在细化指纹后处理中的应用[J].光电子激光，2002，13（2）：184－187.LIU Wen-xing，WANG Zhao-qi，MU Guo-guang.Ridge tracing and application in post-processing of thinned fingerprints[J].Optoelectronic Laser，2002，13（2）：184－187.

[3]RAN Chong-Jie，XIE Mei.A new figerprint matching method based on ridge tracing [C]//Proceedings of the 2007 International Conference on Wavelet Analysis and Pattern Recognition，2007：1108－1113.

[4]王水鱼，刘武，王卓然.基于脊线跟踪的指纹核心点检测[J].计算机系统应用，2011，20（6）：140－143.WANG Shui-yu，LIU Wu，WANG Zhuo-ran.Core point detection of fingerprint based on tracing ridges[J].Computer Systems&Applications，2011，20（6）：140－143.

[5]杨小冬，宁新宝，谭台哲.基于纹线跟踪的指纹细节提取算法[J].计算机应用，2004，24（3）：75－78.YANG Xiao-dong，NING Xin-bao，TAN Tai-zhe.Fingerprint minutiae extraction by following its ridge[J].Computer Application，2004，24（3）：75－78.

[6]杨小冬，宁新宝，詹小四，等.基于纹线跟踪的指纹分类方法[J].计算机工程，2005，31（7）：170－173.YANG Xiao-dong，NING Xin-bao，ZHAN Xiao-si，et al.Fingerprint classification method based on ridge-following[J].Computer Engineering，2005，31（7）：170－173.

[7]Maio D，Maltoni D.Direct gray-scale minutiae detection in fingerprints[J].IEEE Transactions on Pattern Analysis and Machine Intelligencf，1997，19（1）：27－40.

[8]JIANG Xu-dong，YA Wei-Yun，Ser W.Detecting the fingerprint minutiae by adaptive tracing the gray-level ridge[J].Pattern Recognition，2001（34）：999－1013.

[9]MA Rui，QI Ya-xuan，ZHANG Chang-shui，et al.A novel approach to fingerprint ridge line extraction[C]//Proceedings of International Symposium on Communications and Information Technology，2005：2－5.

[10]彭玲，李敏敏.一种基于细节点的脊线追踪算法[J].科学技术与工程，2012，12（6）：1428－1430.PENG Ling，LI Min-min.A fingerprint ridge tracing algorithm based on minutiae[J].Science Technology and Engineering，2012，12（6）：1428－1430.