一种采用脊线特征的指纹模糊匹配方法

魏鸿磊，张文孝，华顺刚

(1.大连海洋大学机械与动力工程学院，辽宁大连 116023;2.大连理工大学机械工程学院，辽宁大连 116023)

指纹匹配是指通过比较指纹间的特征来评估指纹相似性的过程，它是自动指纹识别系统的关键环节，一直是模式识别领域的重要研究课题.基于细节特征的指纹匹配算法通过提取细节特征(主要是指纹脊线的端点和分叉点)，将图像的匹配转变为一系列点的空间分布相似性的评估，以精度高、存储量低等优势获得了广泛的应用，成为指纹匹配的主流算法.这种算法的应用条件是指纹应有较多的细节特征可供比对，然而在实际应用中有一部分人的手指上仅有少量的细节点，或者由于采集角度等原因，仅采集到了局部指纹，造成细节点偏少.在这2种情况下无法应用基于细节特征的指纹匹配算法，需要从指纹的脊线中寻找其他特征进行匹配.脊线的形状具有较强的区分力，可用于指纹比对，但是采用脊线特征需要较大的特征存储量，且脊线集的配准较为困难;因此目前常用方法是根据细节点的位置和方向，将与细节点相连的少量脊线对齐后进行局部匹配［1-4］.但是在上述提到的细节点数量较少的情况下，可用来进行比对的脊线也相应较少，对指纹匹配的帮助有限，因此提取指纹脊线的宏观特征用于匹配的方法目前得到了广泛关注［5-8］，其中典型算法是Jain等的 FingerCode方法［7］.该方法采用 Gabor小波对指纹中心点周围的局部区域进行8方向滤波并计算各扇区的灰度方差，组成固定长度的编码，称为FingerCode，通过计算不同指纹的 Finger-Code编码之间的欧氏距离来评估相似性.但这种方法需要对图像进行卷积计算，计算量很大，且不能应用于没有或无法精确定位中心点的指纹，使得应用范围受到很大限制.Ross等对FingerCode算法进行了改进，通过傅里叶变换将卷积运算转换到频域进行，从而减少了计算量，通过配准细节点来配准指纹，再用类似FingerCode编码的脊线特征图进行匹配［8］.这种方法不要求提取中心点，但需要对更大面积的指纹图像进行卷积运算，计算量仍然较大.

针对上述问题，本文提出一种新的利用脊线形状为主要匹配特征的指纹匹配算法.在特征提取阶段，通过定长距离采样以提取脊线形状，并对采样点进行优选以减少冗余，从而减少模板存储量;在匹配阶段，根据细节特征配准脊线集，对脊线进行定长编码，利用编码进行模糊匹配，从而得到指纹相似度.算法在多个指纹库上进行比对实验，取得了较好的结果.

1 脊线的提取

指纹的脊线形状各异，很难用确定的函数对其进行描述.本文对脊线进行采样时，通过采样点的比较来评估脊线形状的相似性，由于准确描述脊线形状需要记录大量的脊线采样点，所以为减小计算量和存储负担，在保证脊线重建精度的条件下，对采样点进行优选，以删除冗余采样点.

1.1 脊线采样

脊线采样在二值化的指纹图像上进行.从端点开始，逐点跟踪脊线，并将像素值改变以标记已跟踪过的像素，避免重复跟踪.每隔1个固定间距记录1个采样点，直到脊线的末端.如果跟踪过程中发现当前点为分叉点，则将每个分叉都记录为一条独立的脊线，并分别采样.

1.2 采样点优选

保留每条脊线的起始点和终止点，对中间采样点进行优选.如果舍弃某个采样点使得近似脊线和原脊线之间产生过大的差异，则该点必须被保留，否则该点不保留.具体方法以图1为例进行说明.

1)当且仅当L1、L2和L3都小于预定阈值t(本文取为t=3)时，pn+3为冗余点;当 L1、L2和L3中至少有1个大于阈值时，说明pn+3不可删除，即pn+3为需保留的优选点.

图2是脊线重建示例.在原脊线图2(a)上以间隔8个像素采样，共得到1 126个点，以允许误差3个像素优选出280个关键点，只有原总数的25%左右，以此重建的脊线图如2(b)所示.

图2 重建脊线示例Fig.2 Sketch map of reconstructed ridge images

2 脊线的模糊匹配

首先根据细节点匹配得到的配准参数将脊线采样点坐标进行转换，以对齐两脊线集，然后对两指纹重合区域的脊线进行编码，并进行编码的模糊匹配，最后计算脊线的总匹配分值.

2.1 脊线配准

没有细节点的指纹是十分少见的，本文研究的是具有少量细节点的指纹匹配问题.为了能够迅速、准确配准脊线集，首先进行细节点匹配［9］，根据得到的配准参数将脊线采样点进行坐标转换，即对齐脊线集，过程如图3所示.

图3 脊线的对齐Fig.3 Alignment of ridges

2.2 脊线编码

为使两指纹脊线能够快速准确地匹配，需要对两指纹重合区域的脊线进行编码，脊线编码过程如图4所示.

图4 脊线的编码方法Fig.4 The method of ridges coding

1)求出两指纹配准后重叠区域的外包矩形，然后在重叠矩形上以间距λ画竖直线(本文取为λ=10)，设共有K条竖直线.

2)为每条脊线生成一个2×(K+2)大小的编码数组，存储该脊线与K条竖直线交点的y坐标.该编码的第1位是与该脊线相交的第1根竖直线在编码中的位置，第2位是与该脊线相交的最后一根竖直线在编码中的位置，从第3位开始记录每根竖直线与该脊线交点的y坐标，当没有交点时，认为是无效编码位，在其位置补0.由于每条脊线经常与竖直线有2个交点，因此该编码共有2行，第1行记录第1个交点的y坐标，第2行记录第2个交点的y坐标.

3)同样采用2)的方法，根据水平线与每条脊线的交点的x坐标得到x编码.

在实际编程实现过程中，无需恢复脊线图，只求出由线段组成的脊线与栅格的交点坐标，按规则填入编码数组即可.

2.3 脊线的模糊匹配

假设有2条脊线(分别属于2个指纹)将要比对，其x和y编码的个数分别为K和L.比较相同位置的编码值，如果两编码所有坐标的差值都小于预定阈值D，则认为这2条脊线相似.以脊线相同位置编码为模糊集的论域，以相同位置编码的相似程度为隶属度，建立衡量两脊线相似程度的模糊集.两脊线相同位置编码的隶属度按式(1)计算.

式中:c1i和c2i分别是两脊线相同位置的编码值，若两脊线相同位置编码都为0，则隶属度记为0.两脊线相似模糊集可用式(2)表示.

式中:n表示编码中公共区域的长度.两脊线编码中无效编码值(即编码中0的位置)的隶属度为0.若有多条脊线与一条脊线相似，则通过式(3)计算隶属度均值，选取均值最大的一对作为匹配对.

若两指纹共组成了m对匹配脊线模糊集，则评判向量为

对每一模糊匹配集赋予相同的权重，采用加权平均法进行相似度综合评判，如式(4):

若两指纹在公共区内分别有N和M条脊线，共组成了m对模糊匹配对，则以组成匹配对的脊线数目占总脊线数目的比值作为综合评判的权重，从而可采用式(5)来衡量两指纹脊线的相似程度.

2.4 综合匹配分值的计算

综合考虑细节点匹配和脊线匹配结果，以更准确地评估指纹的相似性.假设Sm(I，J)为指纹I和J采用细节点匹配的分值，而Sr(I，J)为脊线匹配的分值，取λ1和λ2分别为这2种不同特征对应的权系数，则细节特征和脊线特征的综合匹配分值计算如式(6):

3 实验结果与分析

按 FVC2000［10］的 测 试 标准，在 CPU 主 频1.6 GHz、内 存 512MB 的笔 记 本 微机 上，采 用FVC2004公布的4个指纹库进行实验，每个库包含800(100×8)张指纹图像.每个样本与相同手指未能匹配上的其余样本的比率称为错误拒绝率(false non-match rate，FNMR)，每个库FNMR的实际测试总数为((8×7)/2)×100=2 800次.每个手指的第1个样本与其他手指的第1个样本匹配成功的比率称为错误接受率(false match rate，FMR)，每个库FMR实际测试的总数为(100×99)/2=4 950次.EER(equal error rate)也叫等错误率，是当FNMR=FMR时的FNMR值，ROC是采用对数坐标的FMR与FNMR的关系曲线.

本文同时实现了4种算法，分别是细节点匹配算法［9］、局部脊线匹配算法［1］、FingerCode 算法［8］以及本文脊线匹配算法，分别记为 M、MLR、MFC和MGR，其中MLR、MFC和MGR中均以M算法为基础，再融合各自特有的算法.为便于比较，在进行MFC和本文MGR算法实验时，首先进行细节匹配，同时检查获得最佳匹配值时参与匹配的细节点数，如果细节点数少于5个，则分别实施这2种算法，并且都根据式(6)与细节点算法加权融合，以进行2种算法的性能比较，其中细节点相似度的权值λ1取为0.6，脊线或 FingerCode算法的权值 λ2取为0.4.

表1是4种算法对4个指纹库进行特征提取的耗时比较，表2是4种算法在4个库中的匹配等错误率和平均耗时的比较，表3给出了MLR、MFC和MGR 3种算法与M算法相比，等错误率下降程度的统计结果，图5是4种算法在4个指纹库上的ROC曲线.由表1可见，与算法 M相比，MLR、MFC和MGR 3种算法都需要更大的计算量，其中以MFC算法耗时最长，平均达到了1.32 s，本文算法MGR次之，平均耗时0.81 s，MLR算法最少.由表2可见，与算法M相比，MLR、MFC和MGR 3种算法都明显降低了等错误率 EER，但从表3可见，本文算法MGR使EER平均下降了21.5%，明显优于MLR算法的6.34%和MFC算法的9.65%.由于指纹匹配错误大都是由于低质量指纹、不完整指纹或少细节点指纹引起的，MLR算法中参与匹配的脊线数量较少，虽特征提取耗时短，但对算法精度的提高也相对较低;MFC算法采用的是指纹脊线的纹理和流向等较“粗”的特征，精度提高有限，且特征提取计算量较大;本文算法MGR采用的脊线匹配更好地提高了不完整指纹或少细节点指纹的匹配精度，从而有效提高了整体匹配的精度.从表2知，在匹配时间方面(即每种算法在4个库中所有匹配的平均时间，不包括预处理和特征提取时间)，由于实际采用脊线匹配的次数较少(经统计，脊线匹配的次数约占总匹配次数的6%左右)，所以每个库的平均匹配时间没有明显增加.

表1 特征提取耗时比较Table 1 Comparison of time consuming for feature extraction s

表2 EER及特征匹配耗时比较Table 2 Comparison of EER and matching time consuming

表3 EER下降程度比较Table 3 Comparison of the decrease level on EER %

图5 在FVC2004 4个指纹库上的ROC曲线比较Fig.5 Comparative ROC curves of three algorithms on FVC2004 fingerprint databases

4 结束语

虽然基于细节特征的指纹匹配算法应用最为广泛，但在很多情况下可参与指纹匹配的细节点数量较少，此时采用细节点匹配不可靠.采用脊线特征可以充分利用指纹脊线信息，提高识别精度，但是采用脊线匹配存在模板存储量大、对齐困难、计算量较大等缺点，影响了脊线特征的应用.本文算法采用优选脊线采样点减少特征存储量，通过脊线编码模糊匹配减少计算量.在FVC2004的4个指纹库上的测试表明，本文算法能够有效提高指纹匹配的精度.该算法的不足之处在于与单独采用细节特征相比，仍需较大的计算量和存储量.考虑到仅需对细节特征可靠性不高的指纹使用本算法，因此大量指纹匹配时的平均计算量的增加并不显著.在对指纹存储量有较高要求时，可以仅存储脊线信息，而其他信息如细节特征、方向场特征等可以从脊线信息中提取，从而减少存储量.进一步的研究将考虑采用样条曲线等数学工具拟合脊线进行匹配，以减少存储量和计算量，并提高准确性.

［1］HE Yuliang，TIAN Jie，LUO Xiping，et al.Fingerprint matching based on global comprehensive similarity［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(6):850-862.

［2］ZHONG Weibo，NING Xinbao.A fingerprint matching method based on minutiae and ridges［C］//Proceedings of 2008 3rd International Conference on Intelligent System and Knowledge Engineering. Xiamen， China，2008:1071-1074.

［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.

［4］VATSA M，SINGH R，NOORE A，et al.Combining pores and ridges with minutiae for improved fingerprint verification［J］.Signal Processing，2009，89(12):2676-2685.

［5］JAIN A K，FENG Jianjiang.Latent fingerprint matching［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(1):88-100.

［6］CHOI Heeseung，CHOI Kyoungtaek，KIM Jaihie.Fingerprint matching incorporating ridge features with minutiae［J］.IEEE Transactions on Information Forensics and Security，2011，6(2):338-345.

［7］JAIN A K，PRABHAKAR S，HONG L，et al.Filterbankbased fingerprint matching［J］.IEEE Transactions on Image Processing，2000，9(5):846-859.

［8］ROSS A，JAIN A K，REISMAN J.A hybrid fingerprint matcher［C］//Proceedings of the 16th International Conference on Pattern Recognition.Quebec City，Canada，2002，3:795-798.

［9］魏鸿磊，欧宗瑛，甘树坤，等.采用逐级配准和分值加权的指纹匹配算法［J］.计算机辅助设计与图形学学报，2006，18(6):832-837.

WEI Honglei，OU Zongying，GAN Shukun，et al.Fingerprint matching using gradual alignment and weighted matc-hing score［J］.Journal of Computer-Aided Design ＆ Computer Graphics，2006，18(6):832-837.

［10］MAIO D，MALTONI D，CAPPELLI R，et al.FVC2000:fingerprint verification competition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(3):402-412.