基于细节点描述子的指纹检索算法

汤正刚 沈雷 吕葛梁

摘要：针对指纹一对一匹配识别方法严重影响指纹数据库系统识别效率的问题，提出一种基于细节点描述子的指纹检索算法，该算法先根据细节点描述子的结构信息进行粗匹配筛选，剔除虚假细节点产生的影响;然后利用筛选后的细节点位置关系确定最佳参考点;最后基于最佳参考点计算所有指纹图像相似度，将相似度排在前N 0的指纹返回并作为候选指纹。实验结果表明，该算法在时间和空间上都優于传统指纹检索算法。

关键词：指纹分类;指纹检索;细节点描述子;最佳参考点

Fingerprint Indexing Based on Minutiae Descriptor

TANG Zheng gang，SHEN Lei，LV Ge liang

（School of Communication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China）

Abstract：Aiming at the problem that fingerprint one to one matching identification method seriously affects the recognition efficiency of fingerprint database system， a fingerprint retrieval algorithm based on minutiae descriptor is proposed. The algorithm first performs rough matching screening based on the structural information of the minutiae descriptors to remove the influence of false minutiae points， and then uses the filtered results of the location of the minutiae point to determine the best reference point. At last the algorithm calculates the similarity of the fingerprint images based on the best reference point， and selects the fingerprints with the similarity ranked in the top N 0 as the candidate fingerprints according to the the best reference point. Experimental results show that the proposed algorithm outperforms the traditional fingerprint indexing algorithm both in time and space.

Key Words：fingerprint classification;fingerprint indexing;minutiae descriptor;optimal reference point

0 引言

近年来，随着指纹识别产品[1 2]在人们生活中被广泛使用，出现了越来越多的大型指纹数据库（如机场指纹库、公安指纹库等），虽然目前指纹匹配算法在时间和准确率方面有了很大改善[3 5]，但在大型指纹数据库中进行指纹识别时，如果仍然采用一对一匹配，会严重影响指纹识别系统效率。为此，引入预筛选技术缩小指纹匹配空间，提高指纹识别效率。预筛选技术通常可以分为两类：指纹分类、指纹检索[6 8]。

在指纹分类中，指纹数据库被划分为固定类别[9 11]，将输入指纹与同一分类的指纹进行匹配即可。指纹分类最大缺点是指纹类别有限且分布非常不均，在Galton-Henry分类方案中，右环型、左环型和漩涡型3类大约占93%[12]，因此指纹分类并不能有效缩小匹配空间;此外，对于残缺和低质量指纹图像，指纹分类无法准确判断其类型，导致该类指纹识别成功率较低。

指纹检索指首先提取稳定的特征向量，通过寻找与其特征向量相似度较高的一批指纹作为候选指纹模版，然后一对一进行精细匹配。指纹检索很好地避免了指纹分类中对于残缺和低质量指纹类别无法判断的问题，而且该技术的检索性能远远优于指纹分类技术。

目前已提出较多指纹检索算法，如Bhanu[6]和王平等[13]提出了基于三角形结构的指纹特征检索算法;Liang等[14]提出一种基于细节点邻域结构和低阶Delaunay三元组的指纹检索方法;Iloanus等[15]提出基于细节点四元组的指纹检索法等。在传统特征检索中，特征结构中的边长容易受到形变影响，且边长越长或越短，形变影响越大;两细节点之间的脊线数目受到噪声、纹线断裂、纹线模糊等质量因素的影响。细节点信息和特征结构的类型都要通过细节点类型求得，但在很多情况下不能确定细节点类型。

综上可知，传统指纹检索算法利用指纹细节点间的结构信息实现指纹检索，该类算法存在一定缺陷。王平和Iloanus的算法构建的三角形和四元组数量较大，不仅需要消耗大量内存空间且会在一定程度上影响指纹检索效率;Liang的算法构建低阶Delaunay网的拓扑结构是唯一的，容易受到虚假细节点影响，如果提取的细节点中包含一定量的虚假细节点，则会构建许多错误的结构信息，降低指纹检索准确率。本文提出一种基于细节点描述子的指纹检索算法，构建的细节点描述子相互独立，相互之间的影响较小，克服了不同细节点间出现虚假结构信息的影响;而且细节点描述子已在文献[16]中用于指纹匹配，并可取得较好的效果，说明细节点描述子可以准确表示指纹特征信息，该特性可保证检索算法性能。

1 细节点描述子构建

构建的细节点描述子具备以下特性：①细节点描述子具有稳定的结构;②细节点描述子含有准确、可靠的辅助信息。

1.1 细节点描述子

本文主要利用细节点描述子进行指纹搜索，不宜构造复杂的结构。因此，根据文献[16]中细节点描述子的定义，绘制本文构建的细节点描述子，如图1所示。

假設P 0为提取的细节点，θ 0为该点的方向场，以P 0为圆心，绘制领域半径为R的圆，在该圆上均匀地取3个辅助点，分别为P 1、P 2、P 3;辅助点P 1为细节点P 0方向场方向与该圆相交的点，P 1、P 2、P 3之间间隔为120°，其中辅助点P 1、P 2、P 3对应的方向场分别为θ 1、θ 2、θ 3。

如果辅助点位于非指纹区域，则认为该细节点是无效细节点;细节点描述子领域半径R的大小直接影响细节点鉴别能力，下文通过实验给出最佳领域半径R值。

1.2 指纹方向场计算

细节点描述子使用的辅助信息是细节点周围的方向场信息，因此，指纹方向场的准确性会直接影响细节点描述子的效果。通常使用梯度算子计算指纹方向场[17 19]，具体如下：

（1）将指纹图像分成W*W的固定小块。

（2）采用Sobel算子计算每小块内每个像素点梯度  x（i，j）、 y（i，j） 。

（3）根据梯度值计算块方向，公式如下：

文献[17]-[19]提出的算法是在固定分块尺寸后计算指纹方向场，虽然对纹线清晰的指纹图像能够取得较好的效果，但对质量较差的指纹图像则存在明显不足。而本文检测对象是分辨率更高的方向场——点方向场，求每一点的方向场所需时间比块方向场更多。为了加速计算，本文在其基础上设计滑动窗口（见图2）技术，同时使用图像的高斯金字塔分解[20]技术缩小指纹尺度，获得更加准确的指纹方向场。

2 指纹检索算法

本文提出的基于细节点描述子的指纹检索算法，利用细节点描述子对所有细节点进行粗匹配，然后根据粗匹配点间的位置信息寻找最佳参考点，最后基于最佳参考点计算两指纹相似度。算法具体包括： ①从指纹图中提取每个细节点特征信息为（x，y，T，θ 0，θ 1，θ 2，θ 3），其中x、y、T、θ 0分别表示细节点的横坐标、纵坐标、类型（端点、分叉点）及方向场;②θ 1、θ 2、θ 3为图1中细节点描述子中对应三点的方向场。输入两幅指纹A和B，A是待识别指纹，提取的细节点为集合A={a 1，a 2，…，a N}，B为指纹库中的任意指纹，提取的细节点为集合B={b 1，b 2，…，b M}。

2.1 粗糙匹配点集获取

利用细节点描述子局部方向场信息，获取指纹A和B粗糙匹配点集。具体过程如下：

（1）选取指纹图像 A中任意一个细节点a n，遍历指纹图像B中所有细节点，若指纹图像B中存在细节点b m，两个细节点a n、b m 满足类型相同、且位置平移在（±Δ x 0 ，±Δ y 0）范围内的条件，则进入（3）;若遍历指纹图像B中所有细节点后不存在与细节点a n对应的细节点b m，则放弃指纹图像A的细节点a n。

（2）继续从指纹图像A中选取下一个细节点，重复（1），直至遍历完指纹图像A中所有细节点。

（3）计算细节点描述子中两点之间的相对角度差Δ θ k 。

式中k为细节点描述子中相对角度差对应编号，其范围为1≤k≤6。

两细节点描述子间第k角度偏差记为G（k）：

式中，Δ θa n k为细节点a n 的相对角度差，Δ θb m k为细节点b m的相对角度差。

（4）判断两指纹细节点是否匹配：①如果式（5）中任意G（k）大于阈值T 1，说明两细节点不匹配，回到（1），否则进入下一步;②两细节点描述子相似度S计算公式为S=1-16T 1∑6k=1G（k）;③若S大于阈值T 2，则记录相似度Si;④ 重复（1）、（2），直到剩下点都完成匹配（存在指纹A中一个点与指纹B中多个点相似度大于T 2）;⑤选取每组Si中最大S作为匹配点，记录匹配成功的点集Q，匹配对数为L ，每对匹配点之间的指纹匹配点类型为（Δ x i ，Δ y i ，Δ θ i ）。

2.2 指纹图像相似度计算

利用细节点间全局位置关系，确定最佳参考点对，然后计算基于最佳参考点的指纹图像相似度。

（1）确定最佳参考点对。分析第一步中的粗匹配点集，从中寻找最佳匹配点。原理如下：如果两幅指纹图来自同一手指，则每对匹配点（Δ x i ，Δ y i ，Δ θ i ）位置变换相等，允许在一定范围之内变动（Δ x i ±Δ l 0 ，Δ y i ±Δ l 1 ，Δ θ i ±Δ l 2 ）;但如果偏差较大，则说明对应的匹配点是虚假匹配点。具体过程如下：

计算集合 Q （Δ x ，Δ y ，Δ θ ）与每对匹配点（Δ x i ，Δ y i ，Δ θ i）（i=1，2，…，L）的偏差d i：

取d i中小于阈值T 3个数最大值C m对应的匹配点为最佳匹配点，即a i和b i 为最佳匹配点，其位置偏差为（Δ x ij ，Δ y ij ，Δ θ ij ）。

（2）基于最佳参考点计算指纹图像相似度。

式（7）中D（i）是最佳匹配点下偏差d i集合，C m为在最佳参考点下细节点匹配点数，R为匹配点中端点的个数，L为细节点描述子匹配点数，N和M分别为指纹A和指纹B的细节点数。

2.3 指纹检索结果

输入指纹A与指纹库中所有指纹，重复粗糙点集获取和指纹图像相似度计算，得到所有指纹相似度集合Score，再从Score中选出排在前N 0个的指纹作为候选指纹。

3 实验与结果分析

为了得到实验图像数据库，采集1 000组指纹图像建立指纹图像库，每组6幅图像样本，一共6 000幅样本图像，其中约有20%的指纹图指纹质量偏差。为了验证算法性能，从每组人工选取3幅图像，共3 000幅作为指纹数据库Ⅰ，剩下的3 000幅图像作为指纹数据库Ⅱ。

本文采用穿透率（Penetration Rate）及命中率[13]（Hit Rate）指标衡量检索算法性能。假设指纹库有 d组指纹，其中I m是和测试指纹I匹配的库指纹，I m和I的检测分数为S m，即S m为测试指纹I命中时的检索分数，设S m在所有分数中排名为m，可得测试指纹I的穿透率为：

计算某一穿透率P的命中率为：

式中，M为测试指纹数量，n p表示所有穿透率小于P的测试指纹数量。

图3是本文算法和王平、Liang、Iloanus的算法检索特征数量与细节点数量的曲线对比。从中看出本文构建检索特征的数量最少，在一定程度上减少了检索时间，而且每个检索特征相互独立，该属性可保证检索算法性能。

图4是穿透率分别在5%、10%、15%时领域半径R与命中率的性能曲线。从圖4可知，领域半径R在17～24内命中率性能提升幅度较大，同时结合在其它穿透率时的性能提升情况可以看出，本文算法细节点描述子的最佳领域R选取为19时，细节点描述子的鉴别能力最强。

分别在指纹数据库Ⅰ和指纹数据库Ⅱ中，将王平、Liang、Iloanus和本文算法进行指纹检索实验，得到命中率和穿透率的算法曲线（见图5、图6）。图中结果表明本文算法在两个数据库中都展示了更好的性能，在相同搜索能力下所需搜索空间最小。表1是在命中率为95%和100%时，4个算法在指纹库Ⅰ、Ⅱ穿透率的比较，本文算法在两个指纹库中相差0.2%～0.3%，在4个算法中的变化最小。可知本文提出基于细节点描述子的指纹检索算法性能相比于传统的指纹检索算法，有效提高了指纹检索能力，而且算法性能最稳定。

为了验证本文算法运行时间的可行性，将本文算法和王平、Liang、Iloanus的算法在不同规模指纹数据库中进行时间、效率仿真，同时加入文献[8]的匹配算法进行仿真，统计在相同数量的指纹库中匹配一枚指纹的平均时间，如图7所示。在指纹库中进行指纹检索时，4种检索算法所需时间分别为97.3ms、120ms、158ms、213ms，而文献[8]的匹配算法需1 269ms，进一步证明本文指纹检索算法消耗时间较少，可以实现快速检索指纹。

4 结语

本文提出了一种基于细节点描述子的指纹检索算法，利用细节点描述子对指纹细节点进行粗匹配，降低了虚假细节点在检索过程中的影响;同时通过指纹局部和全局信息相结合的方法，从粗匹配点中确定最佳参考点，根据最佳参考点计算指纹相似度，使指纹检索达到很好的效果。

参考文献：

[1] 倪增超，王婧.自动指纹识别技术的发展及应用[J].科技创新与应用，2015（32）：40.

[2] 李庆艳，张文安.浅析指纹识别在移动支付的应用前景[J].广东通信技术，2015，35（8）：2 6.

[3] GHADDAB M H， JOUINI K，KORBAA O， Fast and accurate fingerprint matching using expanded delaunay triangulation[C]. IEEE/ACS 14th International Conference on Computer Systems and Applications， 2017：751 758.

[4] GUTIRREZ P D， LASTRA M， HERRERA F， et al. A high performance fingerprint matching system for large databases based on GPU[J]. IEEE Transactions on Information Forensics and Security， 2014，9（1）：62 71.

[5] PAULINO A A， FENG J， JAIN A K. Latent fingerprint matching using descriptor based hough transform[J]. IEEE Transactions on Information Forensics and Security， 2013，8（1）：31 45.

[6] CAPPELLI R. Fast and accurate fingerprint indexing based on ridge orientation and frequency[J]. IEEE Transactions on Systems， Man and Cybernetics：Part B （Cybernetics），2011，41（6）：1511 1521.

[7] 赵琪.自动指纹识别中若干关键技术的研究[D].长沙：中南大学，2009.

[8] BHANU B， TAN X J. Fingerprint indexing based on novel features of minutiae triplets[J].IEEE Transactions on Pattern Analysis and Machine Intelligence， 2003，25（5）：616 622.

[9] 聂桂军，孟庆杰，朱琳，等.基于方向图跟踪和对称轴的自动指纹分类算法[J].计算机应用，2011，31（1）：70 73.

[10] 杨小冬，宁新宝，詹小四，等.基于纹线跟踪的指纹分类方法[J].计算机工程，2005（7）：170 173.

[11] 杨利敏，杨杰，李钢.基于指纹分类的模式匹配[J].电子学报，2003（7）：1030 1034.

[12] MALTONI D，MAIO D ， JAIN A K， et al. Handbook of fingerprint recognition[M]. New York：Springer Verlag Press，2009.

[13] 王平.指紋图像的检索与匹配算法研究[D].大连：大连理工大学，2004.

[14] LIANG X， BISHNU A， ASANO T. A robust fingerprint indexing scheme using minutia neighborhood structure and low order delaunay triangles[J]. IEEE Transactions on Information Forensics and Security， 2007，2（4）：721 733.

[15] ILOANUSI O， GYAOUROVA A， ROSS A.Indexing fingerprints using minutiae quadruplets[C]. CVPR 2011 WORKSHOPS，2011：127 133.

[16] 陈晖，殷建平，祝恩，等.一种基于细节点局部描述子的指纹图像匹配方法[J].计算机工程与科学，2010，32（1）：87 91.

[17] 刘灵丽，李丽娟.指纹图像预处理和特征提取[J].计算机工程，2006，32（16）：190 192.

[18] 周晔华.指纹图像预处理算法研究[D].南京：南京理工大学，2008.

[19] 王玮，李见为，张腾.指纹图像的预处理算法[J].计算机应用，2004（5）：72 75.

[20] GONZALES R C， WOODS R E. 数字图像处理[M].第三版.阮秋琦，阮宇智，译.北京：电子工业出版社，2011.