蔡秀梅, 孙　鹏

(西安邮电大学 自动化学院， 陕西 西安 710121)

基于模板的指纹图像细化算法

蔡秀梅, 孙鹏

(西安邮电大学 自动化学院， 陕西 西安 710121)

摘要:为了提高指纹图像细化处理后的效果,给出一种基于模板的指纹图像细化算法。在逐像素细化(One Pass Thinning Algorithm, OPTA)算法的基础上，构造9个消除模板和7个保留模板；通过迭代方法遍历图像中所有像素，当遇到目标点时，提取该点周围的15-邻域像素；将提取出的像素分别与两套模板匹配，以判断该目标点能否被删除。所给算法在不做任何额外前、后处理的前提下，能够对纹线完全细化，处理后图像光滑无毛刺。

关键词:指纹图像；指纹细化；消除模板；保留模板

指纹识别技术作为一种鉴定身份信息的方法，其应用正在逐渐多元化，例如基于指纹识别的考试随机选座系统[1]。一个优秀的指纹识别系统应该能保证其识别结果的正确性。作为预处理过程中一部分，指纹细化结果的好坏对后续特征提取的准确性有很大的影响。如果细化后纹线发生畸变且毛刺多，在特征提取工作阶段，会出现大量伪特征点，从而导致工作难以进行，无法正确得到匹配结果，因此一种好的细化方法非常重要。

指纹细化算法大致可归类为基于模板的串行细化、基于判决条件的并行细化、串并共用的复合细化及其他细化[2-4]。串行细化是一种逐像素判断的细化算法，在一次迭代中，前一像素是否删除直接影响到后一像素的判断结果，如逐像素细化算法(OnePassThinningAlgorithm,OPTA)[5]及其各种改进算法[6-9]。并行细化算法在一次迭代中对图像中所有像素同时进行处理，如GUO的并行细化算法[10]，ZHANG的快速并行细化算法[11]及其改进算法[12]。

细化最基本、最主要的任务是删除那些不属于骨架的像素，主要通过对图像目标逐步分离直到最后只剩下骨架图来实现。每个像素都必须经过检测，以判定它是否处于图像对象的边缘和能否被删除掉，或者看它是否是骨架像素的一部分而需要保留。

本文拟对基于16-邻域模板的指纹细化算法进行分析[6]，重新构造两套模板，提出基于模板的指纹图像细化算法。

1基于邻域的指纹细化原理

1.1基于16-邻域的指纹细化算法

基于16-邻域模板的指纹细化算法[6](以下简称为16-邻域细化算法)是对OPTA的改进。该算法将原有OPTA的3×3模板改为4×4模板(如图1)，对目标点(P5)提取相邻15个像素进行判决，并将消除模板增多至8个(如图2)，保留模板增多至6个(如图3)，其中“0”代表背景点，“1”代表目标点，“×”代表任意情况。这种改进使纹线可删除情况变多，能提高细化质量。

图1　16-邻域细化算法的统一模板

图2　16-邻域细化算法的消除模板

图3　16-邻域细化算法的保留模板

16-邻域细化算法可描术如下。

步骤1按照从左到右和从上到下的顺序对图像中的像素进行扫描。

步骤2对每个目标点(图中为P5)均提取与其相邻的15个像素,并把P5的8-邻域像素与消除模板逐个比较，如果无一匹配，P5保留。否则，转到步骤3。

步骤3将与P5相邻的15个像素和保留模板一一对比，若能匹配成功，则P5保留，否则，将P5变为背景点。

步骤4判断图像是否细化完全，若没有完全细化，跳转到步骤1，否则，结束。

1.2指纹图像细化的复合式算法

指纹图像细化的复合式算法[8](以下简称为复合式细化算法)综合各算法的优点，结合了16-邻域细化算法的改进模板与快速并行细化算法[11]的约束条件。该算法在细化前先对图像进行去毛刺处理，之后用快速并行细化算法对纹线进行初步细化，最后用改进的模板对图像进行串行细化。

1.3算法性能分析

针对上述算法进行实验研究，结果显示，16-邻域细化算法处理图像后，纹线的毛刺集中出现的地方有以下3种(如图4)：斜线方向(135°)的纹线，平行方向(180°)的纹线和纹线的两端。

图4　毛刺集中出现的3种情况

由图4中可见，除毛刺多之外，部分纹线并非单像素宽，其主要因为细化模板的判断标准不够严谨。图2中前4个消除模板只针对了4种纹线情况进行细化，后4个消除模板只针对了8种纹线情况进行细化，而每个保留模板中的×都达到了8～9个，也就是说每个模板的保留条件都在28～29。16-邻域细化算法的模板消除条件过少，保留条件过多，这正是该算法存在缺陷的原因。

135°方向纹线的毛刺产生过程如图5所示。从该图5(a)可知，第3行第3个黑色目标点与所有消除模板均不匹配，则在本次遍历后未删除。由于串行细化算法的特点，该目标点会影响后续细化结果，最终在细化结束后产生如图5(b)的斜线方向毛刺。

平行方向纹线的毛刺产生过程如图6所示。从图6(a)可知第2行第3个黑色目标点也无任何消除模板与之匹配，则在本次遍历后未删除，最终形成如图6(b)所示的180°方向纹线的毛刺。

纹线两端的毛刺产生过程如图7所示，图7(a)和图7(b)为纹线始端毛刺产生过程，图7(c)和图7(d)为纹线末端毛刺产生过程。纹线始端毛刺产生原因与斜线方向毛刺相同，而纹线尾部的毛刺多出现在纹线下方，这主要因为在尾部之前的细化工作没有做好，且没有专门用来处理末端毛刺的模板。

图5　斜线毛刺产生过程

图6　平行方向纹线毛刺产生过程

图7　纹线两端毛刺产生过程

2新的细化算法

对16-邻域细化算法的两套模板进行改进(如图8和图9)，可以得出一种基于模板的指纹图像细化算法。

对消除模板的改动有：第2个模板第2行第3列的像素值由“1”改为“×”；第3个模板第3行第1列和第3行第2列的像素值由“0”改为“×”；第4个模板第2行第3列和第3行第3列的像素值由“0”改为“×”；第5个模板第2行第3列的像素值由“1”改为“×”；此外，增加一个新的消除模板用以去除纹线两端的毛刺。

对保留模板的改动有：第2个模板第1行第2列的像素值由“×”改为“1”；第3个模板第1行第2列的像素值由“×”改为“0”，第2行第3列的像素值值由“1”改为“×”；第5个模板第3行第2列的像素值由“1”改为“0”；此外，增加一个新的保留模板。

基于模板的指纹图像细化算法可描述如下。

步骤1按照从左到右和从上到下的顺序对图像中的像素进行扫描。

步骤2对如图1所示的目标点(P5) 提取与其相邻的15个像素。先将P5的8-邻域像素与图8所示的9个消除模板进行比较，若比对失败，则保留该目标点，否则，转到步骤3。

步骤3将P5的15个相邻像素与图9所示的7个保留模匹配，若匹配成功，则保留该目标点，否则，删除该目标点(将该目标点改为背景点)。

步骤4判断图像是否细化完全，若没有完全细化，跳转到步骤1，否则，结束。

图8　新算法消除模板

图9　新算法保留模板

3实验结果与分析

为验证新算法的效果，对16-邻域细化算法,复合式细化算法及基于模板的指纹图像细化算法进行编程实现。从FVC指纹库中提取多幅指纹图像作为实验样板。对各样板作二值化处理，之后根据3种不同算法分别进行细化处理。

由随机挑选两组细化结果(图10和图11)可见，3种算法在不做任何前、后处理的条件下，利用16-邻域细化算法细化后，图像毛刺多且不能满足单像素宽度；利用复合式细化算法处理后，纹线满足细化性，但毛刺问题并未得到太大改善；利用改进所得算法，细化后纹线光滑、无毛刺且为单像素宽。

图10　第1组细化效果

图11　第2组细化效果

4结语

基于模板的指纹图像细化算法为一种新的串行细化算法。该算法处理后图像纹线为单像素宽且毛刺少，但细化后在左斜方向纹线的起始端有少量毛刺，造成这种问题的原因主要是该毛刺的邻域像素与135°方向纹线的起始端邻域像素一致，若删除该毛刺会导致纹线不满足连通性，需要在后续工作中对判决条件做进一步改善。

参考文献

[1]白雁.基于指纹识别的考试随机选座系统[J/OL].西安邮电大学学报,2014,19(4):82-84[2015-12-20].http://www.cnki.net/kcms/doi/10.13682/j.issn.2095-6533.2014.04.016.html.

[2]高欣,刘重晋,封举富.基于Gabor相位的指纹图像细化算法[J/OL].北京大学学报：自然科学版,2012,48(1):37-41[2015-12-20].http://www.cnki.com.cn/Article/CJFDTotal-BJDZ201201007.htm.DOI: 10.13209/j.0479-8023.2012.006.

[3]JIAHL,CAOK.Theresearchonthepreprocessingalgorithmforfingerprintimage[C/OL]//2012IEEESymposiumonElectrical&ElectronicsEngineering(EEESYM).KualaLumpur:IEEE, 2012:163-166[2015-12-20].http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6258614.DOI: 10.1109/EEESym.2012.6258614.

[4]杨静.基于神经网络的指纹识别[D/OL].北京:北京工业大学,2003:20-30[2015-12-20].http://d.wanfangdata.com.cn/Thesis/Y512751.

[5]CHINRT,WANHK,STOVERDI,etal.Aonepassthinningalgorithmanditsparallelimplementation[J/OL].ComputerVision,1987,40(1):30-40[2015-12-20].http://www.sciencedirect.com/science/article/pii/0734189X87900545.

[6]冯星奎,李林艳,颜祖泉.一种新的指纹图象细化算法[J/OL].中国图象图形学报,1999,4(10):835-838[2015-12-20].http://www.cnki.com.cn/Article/CJFDTotal-ZGTB199910007.htm.

[7]梅园,孙怀江,夏德深.一种基于改进后模板的图像快速细化算法[J/OL].中国图象图形学报,2006,11(9):1306-1311[2015-12-20].http://d.wanfangdata.com.cn/Periodical/zgtxtxxb-a200609018.DOI:10.3969/j.issn.1006-8961.2006.09.018.

[8]卞维新,徐德琴.指纹图像细化的复合式算法[J/OL].中国图象图形学报,2011,16(6):1015-1021[2015-12-20].http://d.wanfangdata.com.cn/Periodical/zgtxtxxb-a201106016.

[9]陈刚,陈宁,曾勇.基于邻域搜索的OPTA指纹细化改进算法[J/OL].计算机仿真,2012,29(9):300-303[2015-12-20].http://d.wanfangdata.com.cn/Periodical/jsjfz201209074.DOI:10.3969/j.issn.1006-9348.2012.09.074.

[10]GUOZC,RICHARDW.Parallelthinningwithtwosubiterationalgorithms[J/OL].CommunicationsoftheACM,1989,32(3):359-373[2015-12-20].http://dl.acm.org/citation.cfm?id=62074.DOI:10.1145/62065.62074.

[11]ZHANGTY,SUENCY.Afastparallelalgorithmforthinningdigitalpatterns[J/OL].CommunicationsoftheACM,1984,27(3):236-239[2015-12-20].http://dl.acm.org/citation.cfm?id=358023.DOI:10.1145/357994.358023.

[12] 牟少敏,杜海洋,苏平,等.一种改进的快速并行细化算法[J/OL].微电子学与计算机,2013,30(1):53-55[2015-12-20].http://d.wanfangdata.com.cn/Periodical/wdzxyjsj201301014.

[责任编辑:瑞金]

Fingerprintimagethinningalgorithmbasedontemplate

CAIXiumei,SUNPeng

(SchoolofAutomation,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:In order to improve the effect of fingerprint image thinning process, a fingerprint image thinning algorithm based on template is proposed. Based on the one pass thinning algorithm(OPTA), nine elimination template and seven reserved template are constructed, then, all pixels in the image are scanned by an iterative method to find out the target point, and the fifteen pixels around it are picked up. Match these pixels with the elimination templates and reserved templates respectively to determine whether the target point can be deleted or not. Without any additional pre-processing and post-processing, the proposed algorithm can fully refined the ridge line, and the processed image is smooth with little burr.

Keywords:fingerprint image, fingerprint thinning, elimination template, reserved template

doi:10.13682/j.issn.2095-6533.2016.03.009

收稿日期：2016-02-04

基金项目：国家自然科学基金资助项目(61571361)；西安市科技计划资助项目(CXY1516(1))

作者简介：蔡秀梅(1975-)，女，硕士，副教授，从事模式识别、图像处理和测控技术与仪器研究。E-mail:67170179@qq.com 孙鹏(1988-)，男，硕士研究生，研究方向为计算机控制技术、理论与方法。E-mail:tonysp1988@163.com

中图分类号：TP391

文献标识码：A

文章编号：2095-6533(2016)03-0059-05