基于细化图像的指纹分类方法

1、基于细化图像的指纹分类方法詹小四1 詹小四，博士、副教授，安徽省桐城市人，阜阳师范学院计算机系计算机应用研究所副所长，主要研究方向为图像处理与模式识别、生物特征识别技术以及数字视频监控技术与系统等方面，近年来在软件学报、南京大学学报、中国图象图形学报等刊物上发表论文近十篇。E-mail:xiaoszhan。，陈蕴，陈超(阜阳师范学院计算机系，安徽阜阳 236032)摘 要：在深入研究现有指纹分类算法的基础上，提出了一种利用细化后指纹图像的纹线全局模式进行指纹分类的方法。该方法检测细化后指纹图像的全局模式，并且结合指纹图像的方向流信息，将指纹分为六类：拱型、尖拱型、左环、右环、涡型和孪生型。实验

2、结果表明，在对低质量的指纹图像进行有效增强处理以后，该方法可以快速、准确的对指纹进行分类。 关键词：指纹；指纹分类；全局模式 1. 引言近年来，以指纹为代表的生物识别技术引起了人们的广泛关注，由于具有唯一性、不易丢失且无须记忆、以及终身不变性等特性，生物特征识别技术日益成为当今社会一种重要的身份认证手段，其中指纹识别技术在生物识别技术中应用最为广泛。一般而言，在辨识模式的自动指纹识别系统中，为完成一次自动识别，待识别指纹需要与样本数据库中的大量指纹逐一进行比对，从而确定使用者的真实身份。当样本数据库的容量足够大时，一次识别所消耗的时间是非常大的，无法满足实际应用的需要。为了减少一次识别所需要的

3、时间，一种非常有效的方法就是减少识别过程中所需要进行逐一比对的样本数目，为此前人提出了根据指纹的全局模式对指纹进行分类的思想，将属于不同类别的指纹分别保存在不同的子数据库，待识别指纹只需与归属同一类别的子数据库中的样本指纹进行逐一比对。指纹分类就是根据指纹的整体结构特征将指纹分别归属到几个不同的预先设定的类别中去。从某种意义上讲，指纹分类过程也是一次粗糙的指纹匹配过程。指纹分类实际是为自动指纹识别提供了一个索引机制。在自动指纹分类中，应该考虑以下四个方面的问题：（1）指纹类形的数目；（2）指纹在各类中的分布；（3）分类精度；（4）分类算法的运算量 。（1）表明一个分类算法应该能够把指纹分成数目

4、足够多的类。检索机制的效率依类的数目而定，类的数目越多，检索机制的效率就越高。（2）强调了指纹在各类中分布情况。我们希望每个类中包含相同数量的指纹，指纹在各类中的分布越均衡，检索机制的效率就越高。（3）规定分类方案必须达到一定的分类精度，即能够将每个指纹准确归属到相应的类别中去，而不应出现分类错误或无法分类的问题。（4）指出分类操作的速度应该相当快。如果对样本数据库分类后进行搜索比直接的线性搜索速度慢，用分类方案来检索指纹库就毫无意义了。理想情况下，一个自动指纹分类算法应该能够以令人满意的准确率迅速地将指纹分到相应的类中。在实践中，由于指纹纹线形态的复杂性与噪声的影响，指纹分类技术的研究面临着

5、巨大的挑战。常用的指纹分类方法是统计法1,2,3,4,5 和结构法6,7。统计法是指利用直接从图像的方向信息中获取的特征量对指纹进行分类的方法。结构法是指利用一些突出的指纹特性和它们之间的关系提取和重现指纹整体结构的方法。另外，J.L.Blue等8利用人工神经网络技术对指纹进行分类；K.Karu与A.K.Jain9利用core点和delta点进行指纹分类；K.Rao与K.Black10以及B.Moayer与K.S.Fu11,12则使用了句法模式识别的方法对指纹进行分类。普遍来看，现有指纹分类算法大都存在两个问题，即分类速度较慢和分类准确率不高。如何正确地进行指纹分类，在自动指纹识别研究中是一个

6、难点。一般而言，指纹分类的核心问题是决定用哪些特征对指纹进行分类及如何基于这些特征来定义这些类。前人大量的研究结果表明，指纹的整体结构特征主要与指纹的全局结构和指纹纹线的方向信息有关。为此，本文在深入研究现有指纹分类方法的基础上提出了一种基于指纹图像的全局结构模式和指纹纹线方向信息的分类方法。该方法在对指纹进行一系列预处理之后的细化图像上提取出指纹图像的全局结构模式，然后结合方向信息，将指纹分为六类：拱型、尖拱型、左环、右环、涡型和孪生型。2. 基于细化图像的指纹分类方法2.1 指纹图像细化处理为了获得一幅良好的细化后指纹图像，本文首先对指纹图像进行一系列处理，以便适应实际应用的需要。下面简单

7、介绍一下处理步骤：首先采用多级分块尺寸下的方向信息求取方法，求得更为准确的块方向信息，采用基于统计窗的纹线频率求取方法，提取准确的指纹纹线频率；然后结合指纹方向信息和频率信息，采用Gabor滤波器对指纹进行增强处理，以便有效的提高指纹图像的质量；接着采用自适应阈值的二值化方法对增强后的指纹图像进行二值化操作，将灰度指纹图像转化为二值的黑白图像；最后采用一种改进的模板细化方法对指纹图像进行细化处理，以便获得一个良好的、彻底细化的指纹图像。细化处理是指在指纹图像二值化以后，在不影响纹线连通性的基础上，删除纹线的边缘像素，直到纹线为单像素宽为止。理想细化后的纹线骨架应该是原始纹线的中间位置，并保持纹

8、线的连接性、拓扑结构和细节特征。细化算法的种类很多，按照细化顺序来看主要分为三类：串行细化、并行细化和混合细化。其中快速细化（Quick Thinning Algorithm）和改进的OPTA算法（Improved OPTA Thinning Algorithm）是目前使用较多的两种细化算法。快速细化算法为连通并行细化算法，原理是判断出指纹纹线的边界点并逐步删除。该算法速度很快，但是细化不彻底。改进的OPTA算法是串行细化算法，其原理是构造一定的消除模板和保留模板，将二值化后的指纹图像和模板比较，决定是否删除某点的像素值。这种算法能够基本保证单像素宽，但细化后会产生很多毛刺。而且发现，经过该算

9、法细化的图像在纹线的分叉点处并不是单像素宽的。本文中所采用的细化算法的基本原理如下：首先构建若干个n´n消除模板和保留模板。然后对图像进行遍历，针对图像的每一个像素点，将其n´n邻域与消除模板比较，若都不匹配，保留该点。否则将其邻域与保留模板比较，若满足，保留该点；若不满足，将该点删除。对图像遍历一遍以后，仍按以上步骤再次遍历。直到某次遍历没有像素的值被改变，则细化过程结束。本算法采用统一的4´4模板，如图1所示。P1P2P3P13P4P5P6P14P7P8P9P15P10P11P12´图1. 统一模板结构消除模板：在改进的OPTA算法的8个消除模板（图

10、2）基础上，新构建了8个消除模板（图3），用于消除纹线上的毛刺。两种模板综合起来，作为本算法的消除模板。图1左上角的3´3方窗为消除模板区域。000×1×1110×10110×1111×1×0001×01101×0(a)(b)(c)(d)×00110×1×00×011×1××1×01100××1×110×00(e)(f)(g)(h)图2. 改进的OPTA算法的消除模板0000100110

11、01011000110010000000110100 (a)(b)(c)(d)000010110000011001011010000100110000(e)(f)(g)(h)图3. 新构建的8个消除模板×1×00110×1×0××××××000110××1×××××××1×0110××00××××(a)(b)(c)×0×

12、;×111××1××000××0×××1××110××00××0×××1××011×00××(d)(e)(f)图4. 改进的OPTA算法的保留模板×1×00110×1×0××××××000110××1×××&#

13、215;×××1×0110××00××××(a)(b)(c)图5. 保留模板应去除的三种情况保留模板：在改进的OPTA算法的6个消除模板（图4）基础上，应去除三种情况（图5），用于消除纹线上的毛刺。2.2 纹线全局结构模式求取在对指纹图像进行细化处理以后，本文检测指纹图像中每一条合适的指纹纹线，对其进行一个定性的描述。这里，我们将指纹纹线分为以下几种：拱型纹、尖拱型纹、涡型纹、孪生型纹，其基本形状分别如下图所示。拐点 (a) (b) (c) (d) 图6. 纹线类型示意图（a）涡型（b）孪生型（

14、c）尖拱型（d）拱型）为了能够对这些纹线进行检测，我们设计了如下算法，并对其性能进行了一个有效的评价，为此，本文在这里提出了一种纹线跟踪的纹型检测方法，其基本思想如下所述：第一步，选取每条纹线的起始端点作为纹线跟踪的开始位置。这里，纹线的起始端点的判断方法如下： ( 1 )其中，为所要判断的纹线上点的坐标位置，为点八邻域范围内纹线上的点的数目。第二步，选取一个未跟踪过的纹线起始端点pi，利用纹线跟踪算法对其进行纹线跟踪，并根据纹线所在区域的方向变化程度自适应的选取跟踪步长，依次记录跟踪点，直到跟踪到另一个纹线端点为止，标记已经跟踪过的纹线端点。如在纹线跟踪过程中遇到纹线分叉点，则分别对其进行跟

15、踪，在跟踪结束后选择一条和纹线流方向一致且较长的纹线代表该纹线。在一条纹线跟踪结束后，重新选取另一个未跟踪过的纹线起始点，直到所有的纹线起始点都被处理过。这样，在跟踪完毕后我们得到了整幅细化指纹图像中所有的纹线，记为（）。其中，代表纹线编号，n为相应跟踪点数目。每条曲线由条线段组成。第三步，对每条曲线，计算其所有相邻线段的方向之差，从中找出一个最大值，代表该曲线的最大弯曲程度。第四步，检测每条纹线的拐点，这里所说的拐点是指描述纹线形状改变的“临界点”，即纹线走向发生转折的区域，如图6所示。拐点的判断标准为邻近线段之间的角度偏差大于一个阈值，并记录拐点处的纹线变化方向。第五步，判断每条纹线的基本

16、纹型，其基本的判断规则如下：(1) 如果纹线中没有拐点，则为拱型纹；(2) 如果纹线中只有一个拐点，则为尖拱型纹；(3) 如果纹线中有两个或两个以上的拐点，且存在两个相邻拐点，它们之间的纹线变化方向基本一致，则为孪生型纹；(4) 否则，判定为涡型纹。2.3 指纹分类在检测到指纹图像中所有纹线的基本纹型之后，我们就可以结合指纹图像的方向场信息对指纹图像进行分类，基本方法如下：(1) 如果指纹图像中所有的纹线都为拱型纹，则判定该指纹为拱型；(2) 如果指纹图像中除了拱型纹以外，存在一条以上的孪生型纹，且不存在涡型纹，则判定该指纹为孪生型；(3) 如果指纹图像中除了拱型纹以外，存在一条以上的涡型纹，

17、且不存在孪生型纹，则判定该指纹为孪生型；(4) 如果指纹图像中除了拱型纹以外，存在一条以上的尖拱型纹，且不存在其他类型的纹线，则我们需要结合纹线所在区域的方向场信息对指纹图像进行具体的判断。为了加快算法的运行速度，这里我们选择一条比较典型的尖拱型纹作为处理对象。在本文中，我们选择一条纹线长度大于阈值Tl且最大的一条尖拱型纹线作为我们下一步所要处理的对象，这里称为典型线。为了能够准确的区分尖拱型指纹、左环型指纹和右环型指纹，这里我们需要结合典型线周围的方向场信息，其基本方法如下：以典型线的拐点为分界点，将典型线分为左右两段曲线，分别计算这两段曲线的延伸方向。这里，我们以统计这两段曲线相邻点之间坐

18、标位置变化来确定该曲线的延伸方向，分别记为，则有： ( 2 )其中分别为左边曲线和右边曲线上点的坐标，分别为两条曲线上点的数目。此时，如果有与之间的角度差大于一个给定的阈值qT1（这里我们取为0.42），则认为这两条曲线是从拐点开始向两边发散的，此时判定该指纹为尖拱型；如果有与之间的角度差小于一个给定的阈值qT1，则认为这两条曲线是近似平行的，此时通过典型线的拐点作一条直线，使得典型线的两边沿该直线近似对称，这里我们称之为中心线，如图7所示。根据该中心线的延伸方向对指纹进行分类。如果延伸方向为左下，则判定该指纹为左环型，否则判定为右环型指纹。图7. 中心线示意图3. 实验结果及结论为测试算法性

19、能，选用南京大学活体指纹库(NJU2000)，该库中存放有分别从50个人的不同手指上采集下来的指纹，每个手指有1幅图像，库中共有500幅指纹图像。其中，涡型162枚(占32.4%)；双环型33枚(占6.6%)；左环型144枚(占28.8%)；右环型127枚(占25.4%)；尖拱型10枚(占2%)；拱型24枚(占4.8%)。分类结果如表1所示，其中准确分类为473次，错误分类为22次，无法分类为5次，误识率为4.4%，拒识率1%。从实验结果来看，该算法能够基本准确地对指纹进行分类，达到一定的分类精度。而且该算法是在进行了增强去噪处理以后的图像上进行的，对噪声的抵抗能力得到了一定的加强。在对分类错

20、误的指纹进行分析的结果来看，很多错误所形成的原因是采集区域的面积不够，一些关键性的区域没有采集到，从而导致了分类失败。为此，我们需要在以后的处理过程中引入新的分类依据，以提高算法的分类精度。表1 六类指纹分类结果类别分布分类结果涡 型双环型左环右环尖拱型拱型旋涡型15701000双环型1300100左环02138121右环11112211尖拱型202161拱型0001120无法分类102101参考文献：1 P.Baldi and Y.Chauvin.Neural networks for fingerprint recognition. Neural Computation, 5(3):pp.

21、402-418,1993.2 E.Botha and L. Coezee. Fingerprint recognition with a neuralnet classifier. In Proc.First South African Workshop on Pattern Recognition,volume1,pp. 33-40,1990.3 G.Candela and R.Chellappa.Comparative Performance of Classification Methods for Fingerprints. Tech.Report: NIST TR 5163,1993

22、.4 G.Candela, P.Grother, C.Watson, R.Wikinson. Evaluation of Pattern Classifiers for Fingerprint and OCR Applications.Tech.Report: NIST TR 3162,1993.5 G.T.Candela, P.J.Grother, C.I.Watson, R.A.Wilkinson, C.L.Wilson.PCASYS: A Pattern Level Classification Automation System for Fingerprints.NIST Tech.Report NISTIR 5647,August 1995.6 K.Karu and A.K.Jain. Fingerprint classifications. Pattern Recognition, 29(3): pp.389-404, 1996.7 M.Kawagoe and A.Tojo. Fingerprint pattern classification. Patter