智能系统：一种采用脊线特征的指纹模糊匹配方法

第7卷第3期 智能系统学报 Vol.7 No.3 2012年6月 CAAI Transactions on Intelligent Systems Jun.2012 D0I:10.3969/i.issn.16734785.201105015 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20120507.1509.001.html 一种采用脊线特征的指纹模糊匹配方法 魏鸿磊2，张文孝，华顺刚2 (1.大连海洋大学机械与动力工程学院，辽宁大连116023；2.大连理工大学机械工程学院，辽宁大连116023) 摘要：针对目前指纹识别系统主要采用手指上细节点的分布来表征和匹配指纹，提出了一种采用指纹脊线特征的 匹配算法，以提高细节点数量较少情况下的匹配精度.在特征提取阶段，通过脊线采样，只存储脊线采样点集以降低 存储量；在匹配时，对欲匹配的两指纹利用细节特征配准脊线集，在重合区域内对两指纹脊线统一进行编码，通过编 码的比较确定相似脊线；以相似脊线的相同位置编码为论域，以相同位置编码的相似程度为隶属度，建立衡量脊线 相似程度的模糊集，采用加权平均法对多个相似脊线模糊集进行综合评判得到两指纹脊线总体相似度.最后将脊线 匹配相似度与细节点匹配相似度进行加权融合得到两指纹最终的相似度.在VC2004指纹库上的实验表明该算法 能够有效提高指纹匹配的准确性. 关键词：指纹识别：指纹匹配；模糊匹配；指纹脊线特征；指纹细节点特征 中图分类号：TP391文献标志码：A文章编号：16734785(2012)03023506 A fuzzy fingerprint matching method based on ridge features WEI Honglei2,ZHANG Wenxiao',HUA Shungang? (1.School of Mechanical and Power Engineering,Dalian Ocean University,Dalian 116023,China;2.School of Mechanical Engi- neering,Dalian University of Technology,Dalian 116023,China) Abstract:Most fingerprint matching systems rely on the distribution of minutiae on the fingertip to represent and match fingerprints.This paper describes a matching scheme that used ridge flow information to represent and match fingerprints in order to improve the accuracy of fingerprints matching in case of a lack of sufficient minutiae.In the phase of features extraction,the ridges were sampled into sets of points so that the size of the template for storage could be shrunk significantly.In the matching phase,two fingerprints were aligned first,and the ridges in the over- lap area were coded into sets of ridge codes.By comparing the ridge codes,similar ridge pairs were found.Taking the same position code of similar ridges as the domain,and the degree of similarity of the same position code as the degree of membership,the fuzzy sets of ridge similarity could be achieved.The ridge similarity of two fingerprints could be achieved through evaluating the fuzzy set using the weighted average method.Finally,the weighting fusion was made to calculate the final similarity of two fingerprints based on ridge matching similarity and minutiae matc- hing similarity.Experiments show that this fingerprint matching technique can noticeably improve the accuracy. Keywords:fingerprint identification;fingerprint matching;fuzzy matching;fingerprint ridge features;fingerprint minutiae features 指纹匹配是指通过比较指纹间的特征来评估指 特征的指纹匹配算法通过提取细节特征（主要是指 纹相似性的过程，它是自动指纹识别系统的关键环 纹脊线的端点和分叉点)，将图像的匹配转变为一 节，一直是模式识别领域的重要研究课题.基于细节 系列点的空间分布相似性的评估，以精度高、存储量 低等优势获得了广泛的应用，成为指纹匹配的主流 收稿日期：20110523.网络出版日期：2012-0507 基金项目：辽宁省博土科研启动基金资助项目(20071066)：辽宁省教 算法.这种算法的应用条件是指纹应有较多的细节 育厅科研计划资助项目(L2010072). 通信作者：魏鸿磊.E-mail:whl@dlou.edu.cm. 特征可供比对，然而在实际应用中有一部分人的手

·236 智能系统学报 第7卷 指上仅有少量的细节点，或者由于采集角度等原因， 个采样点，直到脊线的末端.如果跟踪过程中发现当 仅采集到了局部指纹，造成细节点偏少.在这2种情 前点为分叉点，则将每个分叉都记录为一条独立的 况下无法应用基于细节特征的指纹匹配算法，需要 脊线，并分别采样。 从指纹的脊线中寻找其他特征进行匹配.脊线的形 1.2采样点优选 状具有较强的区分力，可用于指纹比对，但是采用脊 保留每条脊线的起始点和终止点，对中间采样 线特征需要较大的特征存储量，且脊线集的配准较 点进行优选.如果舍弃某个采样点使得近似脊线和 为困难；因此目前常用方法是根据细节点的位置和 原脊线之间产生过大的差异，则该点必须被保留，否 方向，将与细节点相连的少量脊线对齐后进行局部 则该点不保留.具体方法以图1为例进行说明， 匹配14.但是在上述提到的细节点数量较少的情 况下，可用来进行比对的脊线也相应较少，对指纹匹 y 配的帮助有限，因此提取指纹脊线的宏观特征用于 匹配的方法目前得到了广泛关注51，其中典型算 图1采样点优选 法是Jain等的FingerCode方法[.该方法采用Ga Fig.1 The sketch of ridge sampling point deleting bor小波对指纹中心点周围的局部区域进行8方向 假设Pn是优选点，而Pa+1和P+2是冗余点，现 滤波并计算各扇区的灰度方差，组成固定长度的编 考察Pn+3是否为冗余点P+1Pn+2Pn+33个点到连 码，称为FingerCode,通过计算不同指纹的Finger- 线PP+4的距离分别为L1、L2和L3, Code编码之间的欧氏距离来评估相似性.但这种方 1)当且仅当L1、L2和L3都小于预定阈值t(本 法需要对图像进行卷积计算，计算量很大，且不能应 文取为t=3)时，Pa+3为冗余点；当L1、L2和L3中至 用于没有或无法精确定位中心点的指纹，使得应用 少有1个大于阂值时，说明P+3不可删除，即Pn+3为 范围受到很大限制.Ross等对FingerCode算法进行 需保留的优选点， 了改进，通过傅里叶变换将卷积运算转换到频域进 2)如果Pn+3为优选点，则根据上述方法以Pa+3 行，从而减少了计算量，通过配准细节点来配准指 为起点继续搜寻下一个优选点；如果P.+3是冗余点， 纹，再用类似FingerCode编码的脊线特征图进行匹 则根据P.+1~P+4到连线PP+5的距离L1~L4判断 配们.这种方法不要求提取中心点，但需要对更大 Pa+4是否为冗余点；如果下一个点是脊线终止点，则 面积的指纹图像进行卷积运算，计算量仍然较大. 结束优选过程。 针对上述问题，本文提出一种新的利用脊线形 图2是脊线重建示例.在原脊线图2(a)上以间 状为主要匹配特征的指纹匹配算法.在特征提取阶 隔8个像素采样，共得到1126个点，以允许误差3 段，通过定长距离采样以提取脊线形状，并对采样点 个像素优选出280个关键点，只有原总数的25%左 进行优选以减少冗余，从而减少模板存储量；在匹配 右，以此重建的脊线图如2(b)所示。 阶段，根据细节特征配准脊线集，对脊线进行定长编 码，利用编码进行模糊匹配，从而得到指纹相似度 算法在多个指纹库上进行比对实验，取得了较好的 结果。 1脊线的提取 指纹的脊线形状各异，很难用确定的函数对其 进行描述，本文对脊线进行采样时，通过采样点的比 (a)原图像 (b)重建图像 较来评估脊线形状的相似性，由于准确描述脊线形 图2重建脊线示例 状需要记录大量的脊线采样点，所以为减小计算量 Fig.2 Sketch map of reconstructed ridge images 和存储负担，在保证脊线重建精度的条件下，对采样 2 脊线的模糊匹配 点进行优选，以删除冗余采样点， 1.1脊线采样 首先根据细节点匹配得到的配准参数将脊线采 脊线采样在二值化的指纹图像上进行.从端点 样点坐标进行转换，以对齐两脊线集，然后对两指纹 开始，逐点跟踪脊线，并将像素值改变以标记已跟踪 重合区域的脊线进行编码，并进行编码的模糊匹配， 过的像素，避免重复跟踪.每隔1个固定间距记录1 最后计算脊线的总匹配分值

第3期 魏鸿磊，等：一种采用脊线特征的指纹模糊匹配方法 237 2.1脊线配准 位，在其位置补0.由于每条脊线经常与竖直线有2个 没有细节点的指纹是十分少见的，本文研究的 交点，因此该编码共有2行，第1行记录第1个交点 是具有少量细节点的指纹匹配问题.为了能够迅速、 的y坐标，第2行记录第2个交点的y坐标 准确配准脊线集，首先进行细节点匹配9，根据得 3)同样采用2)的方法，根据水平线与每条脊线 到的配准参数将脊线采样点进行坐标转换，即对齐 的交点的x坐标得到x编码. 脊线集，过程如图3所示 在实际编程实现过程中，无需恢复脊线图，只求 出由线段组成的脊线与栅格的交点坐标，按规则填 人编码数组即可. 2.3脊线的模糊匹配 假设有2条脊线（分别属于2个指纹）将要比 对，其x和y编码的个数分别为K和L.比较相同位 (a)原图像指纹 门()坐标转换后的图像 置的编码值，如果两编码所有坐标的差值都小于预 指纹 定阈值D,则认为这2条脊线相似.以脊线相同位置 编码为模糊集的论域，以相同位置编码的相似程度 为隶属度，建立衡量两脊线相似程度的模糊集.两脊 线相同位置编码的隶属度按式(1)计算. (c)对齐后的图像指纹 =1-1cu-cal D (1) 图3脊线的对齐 式中：c:和c2x分别是两脊线相同位置的编码值，若 Fig.3 Alignment of ridges 两脊线相同位置编码都为0，则隶属度记为0.两脊 2.2脊线编码 线相似模糊集可用式(2)表示. 为使两指纹脊线能够快速准确地匹配，需要对 2 L 两指纹重合区域的脊线进行编码，脊线编码过程如 A= 十…+ （cu,c21）（c2,c22） (cm,ca)' 图4所示. (2) 007 式中：n表示编码中公共区域的长度.两脊线编码中 2163226 无效编码值（即编码中0的位置）的隶属度为0.若 1723575 14804 有多条脊线与一条脊线相似，则通过式(3)计算隶 12403 属度均值，选取均值最大的一对作为匹配对. 9902 01 (3) 0 6 6 若两指纹共组成了m对匹配脊线模糊集，则评 25 判向量为 21102943243473633903953683303012720 R=[1h…4m]. 00000000000000 对每一模糊匹配集赋予相同的权重，采用加权平均 123456789101112 法进行相似度综合评判，如式(4)： 图4脊线的编码方法 Fig.4 The method of ridges coding b= (4) m 1)求出两指纹配准后重叠区域的外包矩形，然 若两指纹在公共区内分别有N和M条脊线，共 后在重叠矩形上以间距入画竖直线（本文取为入= 组成了m对模糊匹配对，则以组成匹配对的脊线数 10),设共有K条竖直线。 目占总脊线数目的比值作为综合评判的权重，从而 2)为每条脊线生成一个2×(K+2)大小的编码 可采用式(5)来衡量两指纹脊线的相似程度. 数组，存储该脊线与K条竖直线交点的y坐标.该编 2m (5) 码的第1位是与该脊线相交的第1根竖直线在编码 s=N+Mxb. 中的位置，第2位是与该脊线相交的最后一根竖直线 2.4综合匹配分值的计算 在编码中的位置，从第3位开始记录每根竖直线与该 综合考虑细节点匹配和脊线匹配结果，以更准 脊线交点的y坐标，当没有交点时，认为是无效编码 确地评估指纹的相似性.假设S(I,J)为指纹I和J

·238 智能系统学报 第7卷 采用细节点匹配的分值，而S,（I,J)为脊线匹配的 点指纹引起的，MLR算法中参与匹配的脊线数量较 分值，取入，和入2分别为这2种不同特征对应的权 少，虽特征提取耗时短，但对算法精度的提高也相对 系数，则细节特征和脊线特征的综合匹配分值计算 较低；MF℃算法采用的是指纹脊线的纹理和流向等 如式(6)： 较“粗”的特征，精度提高有限，且特征提取计算量 S=A S(I,J)+A2S,(I,J). (6) 较大；本文算法MGR采用的脊线匹配更好地提高 了不完整指纹或少细节点指纹的匹配精度，从而有 3实验结果与分析 效提高了整体匹配的精度.从表2知，在匹配时间方 按FVC20001o]的测试标准，在CPU主频 面（即每种算法在4个库中所有匹配的平均时间， 1.6GHz、内存512MB的笔记本微机上，采用 不包括预处理和特征提取时间)，由于实际采用脊 FVC2004公布的4个指纹库进行实验，每个库包含 线匹配的次数较少（经统计，脊线匹配的次数约占 800(100×8)张指纹图像.每个样本与相同手指未 总匹配次数的6%左右)，所以每个库的平均匹配时 能匹配上的其余样本的比率称为错误拒绝率(false 间没有明显增加. non-match rate,FNMR),每个库FNMR的实际测试 表1特征提取耗时比较 总数为((8×7)/2)×100=2800次.每个手指的第 Table 1 Comparison of time consuming for feature extraction s 1个样本与其他手指的第1个样本匹配成功的比率 算法 DB1 DB2 DB3 DB4 平均 称为错误接受率(false match rate,FMR),每个库 M 0.27 0.25 0.33 0.26 0.28 FMR实际测试的总数为(100×99)/2=4950次 MLR 0.32 0.27 0.39 0.29 0.32 EER(equal error rate)也叫等错误率，是当FNMR= MFC 1.31 1.24 1.61 1.13 1.32 MGR 0.87 0.71 0.98 0.68 0.81 FMR时的FNMR值，ROC是采用对数坐标的FMR 与FNMR的关系曲线. 表2EER及特征匹配耗时比较 本文同时实现了4种算法，分别是细节点匹配 Table 2 Comparison of EER and matching time consuming 算法[9]、局部脊线匹配算法山、FingerCode算法[81以 EER/% 及本文脊线匹配算法，分别记为M、MLR、MF℃和 算法 耗时/s DB1 DB2 DB3 DB4 MGR,其中MLR、MFC和MGR中均以M算法为基 M 9.15 7.07 6.01 4.35 0.04 础，再融合各自特有的算法.为便于比较，在进行 MLR 8.21 6.71 5.55 4.25 0.04 MFC和本文MGR算法实验时，首先进行细节匹配， MFC 8.04 6.62 5.27 4.01 0.04 同时检查获得最佳匹配值时参与匹配的细节点数， MGR 7.32 5.93 4.45 3.32 0.04 如果细节点数少于5个，则分别实施这2种算法，并 且都根据式(6)与细节点算法加权融合，以进行2 表3EER下降程度比较 种算法的性能比较，其中细节点相似度的权值入，取 Table 3 Comparison of the decrease level on EER 为0.6，脊线或FingerCode算法的权值入2取为0.4. 算法 DB1 DB2 DB3 DB4 平均 表1是4种算法对4个指纹库进行特征提取的 MLR 10.3 5.09 7.65 2.30 6.34 耗时比较，表2是4种算法在4个库中的匹配等错 MFC 12.1 6.36 12.3 7.82 9.65 MGR 20.0 16.1 26.0 23.7 21.5 误率和平均耗时的比较，表3给出了MLR、MFC和 MGR3种算法与M算法相比，等错误率下降程度的 统计结果，图5是4种算法在4个指纹库上的R0C 曲线.由表1可见，与算法M相比，MLR、MFC和 MGR3种算法都需要更大的计算量，其中以MFC算 △一M 法耗时最长，平均达到了1.328，本文算法MGR次 MLR 之，平均耗时0.818，MLR算法最少.由表2可见， MFC ◇一MGR EER 与算法M相比，MLR、MFC和MGR3种算法都明显 降低了等错误率EER,但从表3可见，本文算法 MGR使EER平均下降了21.5%，明显优于MLR算 -2 lg(FMR) 法的6.34%和MF℃算法的9.65%.由于指纹匹配 (a)DB1匹配的ROC曲线 错误大都是由于低质量指纹、不完整指纹或少细节

第3期 魏鸿磊，等：一种采用脊线特征的指纹模糊匹配方法 ·239 表明，本文算法能够有效提高指纹匹配的精度.该算 0 法的不足之处在于与单独采用细节特征相比，仍需 较大的计算量和存储量.考虑到仅需对细节特征可 靠性不高的指纹使用本算法，因此大量指纹匹配时 (HWN) △M 的平均计算量的增加并不显著.在对指纹存储量有 关MLR EER 较高要求时，可以仅存储脊线信息，而其他信息如细 MFC MGR 节特征、方向场特征等可以从脊线信息中提取，从而 减少存储量.进一步的研究将考虑采用样条曲线等 -3 -2 数学工具拟合脊线进行匹配，以减少存储量和计算 lg(FMR) 量，并提高准确性。 (b)DB2匹配的ROC曲线 参考文献： [1]HE Yuliang,TIAN Jie,LUO Xiping,et al.Fingerprint 000 matching based on global comprehensive similarity J]. IEEE Transactions on Pattern Analysis and Machine Intelli- △一M gence,2006,28(6):850-862. 9×-MLB EER [2 ZHONG Weibo,NING Xinbao.A fingerprint matching MFC -MGR method based on minutiae and ridges[C]//Proceedings of 2008 3rd International Conference on Intelligent System and -3 -2 Knowledge Engineering.Xiamen,China,2008:1071- g(FMR) 1074. (c)DB3匹配的ROC曲线 [3]ZHENG Xiaolong,WANG Yangsheng.Fingprint matching based on ridge similarity C]//Proceedings of 2008 IEEE International Conference on Acoustics,Speech and Signal Processing.Las Vegas,USA,2008:1701-1704. -1 [4]VATSA M,SINGH R,NOORE A,et al.Combining pores and ridges with minutiae for improved fingerprint verification M -2 ×一MLR [J].Signal Proces9ing,2009,89(12):2676-2685, 口-M'C EER -O—MGIR [5]JAIN A K,FENG Jianjiang.Latent fingerprint matching [J].IEEE Transactions on Pattern Analysis and Machine -3 Intelligence,2011,33(1):88-100. g(FMR) [6]CHOI Heeseung,CHOI Kyoungtaek,KIM Jaihie.Finger- (d)DB4匹配的ROC曲线 print matching incorporating ridge features with minutiae 图5在VC20044个指纹库上的R0C曲线比较 [J].IEEE Transactions on Information Forensics and Secu- Fig.5 Comparative ROC curves of three algorithms on iy,2011,6(2):338-345. FVC2004 fingerprint databases [7]JAIN A K,PRABHAKAR S,HONG L,et al.Filterbank- 4 结束语 based fingerprint matching[J].IEEE Transactions on Image Processing,2000,9(5):846859. 虽然基于细节特征的指纹匹配算法应用最为广 [8]ROSS A,JAIN A K,REISMAN J.A hybrid fingerprint 泛，但在很多情况下可参与指纹匹配的细节点数量 matcher[C]//Proceedings of the 16th Intemational Confer- 较少，此时采用细节点匹配不可靠.采用脊线特征可 ence on Patter Recognition.Quebee City,Canada,2002, 以充分利用指纹脊线信息，提高识别精度，但是采用 3:795-798. 脊线匹配存在模板存储量大、对齐困难、计算量较大 [9]魏鸿磊，欧宗瑛，甘树坤，等.采用逐级配准和分值加权 等缺点，影响了脊线特征的应用.本文算法采用优选 的指纹匹配算法[J].计算机辅助设计与图形学学报， 脊线采样点减少特征存储量，通过脊线编码模糊匹 2006,18(6):832-837. 配减少计算量.在FVC2004的4个指纹库上的测试 WEI Honglei,OU Zongying,GAN Shukun,et al.Finger- print matching using gradual alignment and weighted matc-

.240. 智能系统学报 第7卷 hing score[J].Journal of Computer-Aided Design Com- 张文孝，男，1963年生，教授，博士， puter Graphics,2006,18(6):832-837. 主要研究方向为模式识别、系统仿真， [10]MAIO D,MALTONI D,CAPPELLI R,et al.FVC2000: 发表学术论文30余篇。 fingerprint verification competition[J].IEEE Transactions on Pattem Analysis and Machine Intelligence,2002,24 (3):402-412. 作者简介： 魏鸿磊，男，1973年生，副教授，博 华顺刚，男，1964年生，副教授，博 士，目前在大连理工大学控制科学与工 士，主要研究方向为图像处理、模式识 程博士后流动站从事博士后研究工作， 别，发表学术论文40余篇。 主要研究方向为模式识别、图像处理， 主持或参与省级基金项目4项，发表学 术论文20余篇， 5th International Conference on Agents and Artificial Intelligence 第5届代理和人工智能国际会议 The purpose of the 5th Interational Conference on Agents and Artificial Intelligence(ICAART)is to bring together re- searchers,engineers and practitioners interested in the theory and applications in these areas.Two simultaneous but strongly related tracks will be held,covering both applications and current research work within the area of agents,multi- agent systems and software platforms,distributed problem solving and distributed AI in general,including web applica- tions,on one hand,and within the area of non-distributed AI,including the more traditional areas such as knowledge rep- resentation,planning,learning,scheduling,perception and also not so traditional areas such as reactive AI systems,evo- lutionary computing and other aspects of computational intelligence and many other areas related to intelligent systems,on the other hand. Important Dates Conference Date:15-18 February,2013 Regular Paper Submission:July 24,2012 Authors Notification (regular papers):October 24,2012 Final Regular Paper Submission and Registration:November 14,2012 ICAART Secretariat Address:Av.D.Manuel I,27A,2 esq.2910-595 Setubal-Portugal Tel:+351265100033 Fax:+442030148556 E-mail:icaart.secretariat@insticc.org Web:http://www.icaart.org/