基于混沌蜂群优化的指纹匹配算法

史骏鹏，吴一全,2

(1.南京航空航天大学 电子信息工程学院，江苏 南京 211106； 2.南京理工大学 江苏省社会安全图像与视频理解重点实验室，江苏 南京 210094)



基于混沌蜂群优化的指纹匹配算法

史骏鹏1，吴一全1,2

(1.南京航空航天大学 电子信息工程学院，江苏 南京 211106； 2.南京理工大学 江苏省社会安全图像与视频理解重点实验室，江苏 南京 210094)

为了进一步加快指纹匹配算法的运算速度、提高识别效率，提出了一种基于混沌蜂群优化和可变界限盒的指纹匹配算法。首先，结合人工蜂群优化算法收敛速度快、控制参数少、能够避免局部最优等优点以及混沌策略的类随机性、高遍历性等特点，在指纹点匹配中引入混沌蜂群优化算法，并设计兼顾了匹配精度和运算时间的适应度函数；然后利用适应度函数估计出指纹特征匹配的几何变换参数并进行指纹点特征的粗匹配；最后，利用可变界限盒进行精匹配，避免指纹图像局部形变带来的影响。大量实验结果表明，与基于局部特征的指纹匹配算法、基于遗传算法优化的指纹匹配算法相比，本文提出的算法所需运算时间更短，匹配精度更高。

指纹识别；特征点匹配；群智能优化；人工蜂群；混沌策略；可变界限盒；适应度函数；极坐标

指纹作为人体的基本特征之一，具有唯一性、终身不变性的特点，已被广泛用于个体身份的验证和识别。指纹图像的特征匹配作为指纹识别系统的关键环节之一，直接影响识别的速度和精度。如何保证指纹特征匹配算法的实时性和识别率，一直是国内外学者关注的问题之一。

目前主流的指纹匹配算法可以分为整体匹配[1-3]和特征点匹配[4-12]两大类。其中特征点匹配通过对指纹特征点进行某些几何变换(平移、旋转、缩放)，使待匹配的指纹特征点和模板指纹特征点一一对应，从而达到指纹识别的目的。指纹采集过程中无法避免的噪声和非线性形变干扰，对最终的指纹匹配结果影响很大。文献[1-3]使用全局特征进行整体匹配，但容易受到指纹脊部结构形变和噪声带来的影响。文献[4]通过获取相邻细节特征点的角度差和距离差，构建特征向量进行局部匹配，提高了指纹匹配的精度，但未考虑到指纹图像非线性形变所造成的干扰。界限盒准则限定了匹配点之间角度误差和距离误差的容许范围，能够在一定程度上克服非线性形变的干扰。文献[5]结合半可变界限盒对指纹特征点进行二次匹配，虽然提高了匹配的精度，但匹配时间波动较大。文献[6]提出了一种基于细节点局部配准的指纹匹配算法，以特征点的纹理信息和结构信息为特征，进行全局匹配获得指纹间的公共区域；然后将公共区域内的细节特征点及其邻近的参照点进行分组；最后根据界限盒约束条件，在极坐标系下进行指纹的匹配。文献[7]建立局部特征点的三角模型，利用可变界限盒进行指纹特征点匹配，匹配结果精度较高。此外，许多学者还考虑将指纹特征点和其他特征信息相结合共同用于指纹匹配，也有利于提高匹配的精度。文献[8]从原本筛选剔除出的非匹配特征点对中提取出被忽视的细节信息，结合未剔除的匹配特征点，一起用于指纹的匹配。指纹的采集区域和采集方向不同，往往导致指纹图像中提取出的特征点相似度很低，影响匹配的结果。针对这一问题，文献[9]提出了一种具有全局特性的“利手特征”用于指纹图像匹配，一定程度上提高了匹配精度。文献[10]利用局部特征点之间的距离、特征点类型等信息构建新的特征向量，用以实现指纹的全局匹配。文献[11]提出了一种基于脊线特征的指纹模糊匹配算法，建立衡量相似程度的模糊集合，并利用加权平均法综合评判脊线总体相似度，然后结合特征点相似度最终得出匹配结果。但是上述算法较为复杂，均需要较长的运算时间。

为了满足指纹识别实时性的要求，人们开始考虑基于群体智能的优化算法，并应用到指纹匹配中。遗传算法、粒子群优化算法等能对搜索策略实时调整，避免了繁琐冗余的遍历性匹配，有效地提升了指纹特征匹配的搜索效率。文献[13]和[14]利用遗传算法对指纹匹配算法进行优化，匹配效率得到一定的提升。文献[15]在指纹匹配中采用三角描述符作为初始种群，提高了遗传算法的收敛速度。粒子群算法与遗传算法类似，但不涉及遗传算法的交叉和变异，而是粒子在解空间中搜索最优位置，易于实现。文献[16]提出了一种基于Tent映射混沌粒子群的快速指纹特征匹配算法，在Tent映射和混沌粒子群优化的基础上快速寻找适合的参考点并进行精确匹配。然而粒子群算法的优化性能会随着问题维数的增加而不断下降，与之相比，人工蜂群(artificial bee colony, ABC)算法控制参数较少，全局寻优能力较强，能解决较为复杂的优化问题，可望应用于指纹匹配中[17-20]。

本文提出了一种基于混沌蜂群优化和可变界限盒的分层指纹匹配算法。首先，利用蜂群优化算法收敛快、可避免局部最优、控制参数少等优点以及混沌策略的类随机性、高遍历性等特点，将混沌蜂群优化算法引入指纹图像的点模式匹配中，搜索两幅指纹图像之间可能存在的平移、旋转等几何变换参数；其中，混沌蜂群优化的适应度函数将兼顾匹配精度和运行时间的；然后利用可变界限盒柔性匹配进行精匹配，避免指纹图像局部形变和噪声的干扰。在实验结果与分析部分，将本文算法与基于局部特征的指纹匹配算法[10]、基于遗传算法优化的指纹匹配算法[14]进行了对比实验。

1 基于混沌蜂群优化的点匹配算法

指纹图像在采集过程中，由于指纹本身的旋转、平移以及形变等问题，导致采集到的指纹特征点和数据库中的模板特征点存在差异。假设集合P是采集的待匹配指纹图像特征点集，特征点的个数为M；集合Q是预先存储在数据库中的模板指纹图像特征点集，特征点的个数为N。这两个点集分别表示为

1.1 指纹细节特征匹配

假设指纹特征点集P和Q为匹配的指纹图像，则可以通过一定的平移、旋转、缩放等几何处理，将特征点集P近似变换成特征点集Q。通过搜索这些几何变换参数，使一组特征点经几何变换后与另一组特征点尽可能多的对应，达成一定的阈值条件，即可判断这两组指纹图像是匹配的。特征点集的变换包括平移、旋转和尺度变换，由于采集得到的指纹图像大小基本一致，因此尺度变换往往可以忽略，只需通过平移旋转矩阵HRT对特征点进行变换：

1.2 人工蜂群优化及混沌策略

人工蜂群优化算法由3个部分组成，即引领蜂、观察蜂和侦查蜂(也称雇佣蜂、跟随蜂和侦查蜂)，其具体过程为：1)每只引领蜂都对应一个确定的食物源，并在其邻域随机搜索一个新的食物源，然后将食物源的信息进行反馈，送到观察蜂处；2)比较反馈回的食物源收益度大小后，观察蜂会选取一个食物源作为目标并在其附近重复进行搜索，不断寻找更优的食物源；3)当观察蜂在搜索某个食物源时，若收益度基本不再发生变化，便放弃该食物源，转化为侦查蜂重新开始搜索。不断循环迭代这一过程直到搜索到最佳的食物源位置。需要注意的是，在迭代过程中, 蜂群对于食物源位置的搜索需要遵循一定的规则：引领蜂和食物源是一一对应的关系，其数目必须和食物源数目保持一致；观察蜂的数目也需要和引领蜂的数目一一对应。

为了更好地避免蜂群陷入局部极值，在蜂群优化算法中引入具有类随机性和遍历性等特点的混沌策略，对侦查蜂进行初始化，循环迭代跳出局部最优解位置，最终遍历搜寻出全局最优解位置。混沌序列的公式为

式中：βk表示序列中的参数，βk+1表示下一个序列的参数。

1.3 适应度函数

指纹特征点受到很多因素的制约，除了指纹图像采集时的噪声干扰和非线性形变，指纹图像的去噪、增强、细化等预处理也会对最终参与匹配的指纹特征点造成影响。即使是同一手指的两幅指纹图像，也不一定能获得位置、方向及数目高度一致的两组特征点集。因此设计一个合适的匹配适应度函数是很有必要的，它在诸多干扰下依旧能较为准确地判断出指纹的匹配关系。

为了提升指纹匹配过程中的匹配速度和精度，本文算法引入了分层匹配的思想，将匹配过程分为粗匹配和精匹配2个部分。粗匹配通过全局仿射变换确定大致相符的匹配点对；精匹配则将匹配点对变换到极坐标系下，并根据可变限界盒准则设计匹配适应度函数，对其进行比较。

1)粗匹配。假定变换因子分别为Δx、Δy和Δθ，利用式(2)的平移旋转变换矩阵将指纹特征点集P变换成特征点集T；计算T和Q中所有特征点的欧氏距离和特征点类型差，并将结果放在集合J中：

式中：aik为指纹特征点间的欧氏距离；δik为特征点类型是否一致的判断指标。若δik为0，则两个特征点类型一致；若不为0，则两个特征点类型不一致，肯定不匹配。

2)精匹配。首先将特征点集P和Q转换到极坐标系下，转换公式为

相较于其他指纹匹配算法，本文算法无需预先计算出指纹中心点作为极坐标原点，而是挑选粗匹配特征点作为极坐标的原点。分别对P和Q进行极坐标变换，并根据极角递增的方向进行排序，获得新的特征点集，表示为

为了消除局部形变的影响，在此引入可变界限盒。界限盒限定了匹配点之间角度和距离误差的容许范围，而可变界限盒更具弹性。如图1所示，可变界限盒的形状大小根据特征点的极径和极角动态可变，当匹配点距离原点越近，则界限盒的角度越大，半径越小；反之，当匹配点距离原点越远，则界限盒的角度越小，半径越大。

图1 可变界限盒

可以利用式(8)和式(9)获得可变的极径阈值Tr和极角阈值Te：

式中：r为匹配特征点的极径，rsmall、rlarge和esmall、elarge分别是极径阈值和极角阈值的最大值和最小值。υ和ε是预先设定的常数。

如果两个指纹特征点满足一定的匹配准则，则可以确定该特征点对满足匹配要求，匹配准则为

式中Tη为设定的极坐标方向差阈值。

记录满足条件的精匹配特征点对数目ns，并利用式(11)计算相似度ssim：

由于粗匹配点的数目有很多，为了兼顾运行时间和匹配效率，从中选取欧氏距离最小的3对粗匹配点作为极坐标变换的原点，重复进行精匹配，并不断更新数值最大的ssim。

2 算法实现步骤

3)在每个引领蜂的邻域部分随机搜索一个新的食物源，并按照步骤2)的方式得到一个新的收益度；同时与之前的收益度进行比较，选择较优的食物源位置。

4)观察蜂根据食物源的优劣，在一个引领蜂的邻域部分随机搜索一个新的食物源。利用步骤2)的方式，得到一个新的收益度，同时与之前的收益度进行比较，选择较优的食物源位置，并将引领蜂移动到该处。

5)如果在经过3次循环后，某些引领蜂所对应的食物源的收益度仍没有发生改善，则将混沌序列代替侦查峰进行食物源位置的重置搜索，以跳出局部极值。

6)在一次循环结束后，记录本次循环的最优解，并且循环次数加1。

7)若循环次数达到最大值20后，停止迭代，选择当前最优解作为几何变换参数，并获得最后的匹配相似度；否则，转到步骤3继续进行搜索。

3 实验结果与分析

为了进行比较和分析，同时给出了基于局部特征的指纹匹配算法、基于遗传优化的指纹匹配算法以及本文算法的fFRR值、fFAR值及匹配时间，列于表1。所有算法的运行环境为Intel(R) Core(TM) 2 Duo CPU 2.5GHz/4GB内存、MATLAB2013。

从表1的实验结果可以看出，本文基于混沌蜂群优化和可变界限盒的分层指纹匹配算法匹配精度高、运行速度快，足以满足实时性的要求。与文献[10]算法相比，本文算法利用群体智能算法进行几何变换参数的搜索，避免了大量无意义的重复性匹配，挑选出较为优秀的特征点对参与匹配，并且采用相似度最高的3组粗匹配点对作为精匹配极坐标的原点，匹配精度更高；与文献[14]算法相比，本文的混沌蜂群优化算法避免了遗传算法的选择、交叉和变异等复杂操作，运算速度提高了约20%；同时，采用分层匹配的方式，除了进一步提高匹配的精度外，还利用了可变界限盒的自适应性，有效地避免了外界的非线性形变对匹配特征点的影响。

表1 指纹细节特征匹配的FRR值、FAR值及匹配时间

Table 1 FRR、FAR and matching time of fingerprint minutiae matching

匹配算法指纹图库fFRR/%fFAR/%匹配时间/ms文献[10]算法DB15.661.3563DB25.171.4868DB35.851.6766DB45.741.5864文献[14]算法DB13.980.2885DB23.050.6689DB35.250.8986DB44.971.2084本文算法DB13.500.0452DB22.610.2356DB34.560.5053DB43.920.4252

4 结束语

本文利用混沌蜂群算法优化指纹细节特征匹配，将混沌引入蜂群优化算法中，使人工蜂群优化算法收敛快、避免局部最优、控制参数少等优点和混沌策略的类随机性、高遍历性的特点有机结合起来，用于几何变换参数的搜索；并依据分层匹配的思想设计匹配适应度函数，引入可变界限盒柔性匹配，克服了指纹图像非线性形变的影响。此外，本文算法无需预先找出指纹中心点位置，而是用匹配相似度最高的3对匹配点对作为精匹配的极坐标原点，迭代得出最高的匹配相似度，因此只需较少的特征点就能进行较为准确的匹配，降低了指纹特征提取的难度，易于实现。实验结果表明，本文算法不仅运算速度快，满足实时处理的要求，而且匹配精度更高，能更好地用于个人身份的识别。

[1]ITO K, NAKAJIMA H, KOBAYASHI K, et al. A fingerprint matching algorithm using phase-only correlation[J]. IEICE transactions on fundamentals of electronics, communications and computer sciences, 2004, E87-A(3): 682-691.

[2]HE Yuliang, TIAN Jie, LI Liang, et al. Fingerprint matching based on global comprehensive similarity[J]. IEEE transactions on pattern analysis and machine intelligence, 2006, 28(6): 850-862.

[3]LUMINI A, NANNI L. Two-class fingerprint matcher[J]. Pattern recognition, 2006, 39(4): 714-716.

[4]JIANG Xudong, YAU W Y. Fingerprint minutiae matching based on the local and global structures[C]//Proceedings of the 15th International Conference on Pattern Recognition. Barcelona, Spain, 2000, 2: 1038-1041.

[5]于明, 皮海龙, 王岩, 等. 基于k近邻法和脊线追踪的指纹匹配算法[J]. 吉林大学学报: 工学版, 2014, 44(6): 1806-1810. YU Ming, PI Hailong, WANG Yan, et al. Fingerprint matching algorithm based on k-nearest neighbor and ridge line tracking methods[J]. Journal of Jilin university: engineering and technology edition, 2014, 44(6): 1806-1810.

[6]曹国, 孙权森, 毛志红, 等. 一种新的形变指纹匹配方法[J]. 中国图象图形学报, 2010, 15(4): 645-649. CAO Guo, SUN Quansen, MAO Zhihong, et al. A new algorithm for distorted fingerprint matching[J]. Journal of image and graphics, 2010, 15(4): 645-649.

[7]袁东锋, 杜恒, 秦小铁. 基于三角形局部特征点模型指纹匹配算法[J]. 重庆师范大学学报: 自然科学版, 2013, 30(2): 69-73. YUAN Dongfeng, DU Heng, QIN Xiaotie. Fingerprint matching algorithm based on local triangular feature point model[J]. Journal of Chongqing normal university: nature science, 2013, 30(2): 69-73.

[8]ZHANG Qing, YIN Yilong, YANG Gongping. Unmatched minutiae: useful information to boost fingerprint recognition[J]. Neurocomputing, 2016, 171: 1401-1413.

[9]CAO Kai, YANG Xin, CHEN Xinjian, et al. Minutia handedness: a novel global feature for minutiae-based fingerprint matching[J]. Pattern recognition letters, 2012, 33(10): 1411-1421.

[10]朱宁, 施荣华, 吴科桦. 一种新的点模式指纹匹配方法[J]. 计算机工程与应用, 2006, 42(5): 74-76. ZHU Ning, SHI Ronghua, WU Kehua. A new fingerprint matching method of minutiae[J]. Computer engineering and applications, 2006, 42(5): 74-76.

[11]魏鸿磊, 张文孝, 华顺刚. 一种采用脊线特征的指纹模糊匹配方法[J]. 智能系统学报, 2012, 7(3): 235-240. WEI Honglei, ZHANG Wenxiao, HUA Shungang. A fuzzy fingerprint matching method based on ridge features[J]. CAAI transactions on intelligent systems, 2012,7(3):235-240.

[12]LIU Feng, ZHANG D. 3D fingerprint reconstruction system using feature correspondences and prior estimated finger model[J]. Pattern recognition, 2014, 47(1): 178-193.

[13]漆远, 田捷, 邓翔. 基于遗传算法的指纹图匹配算法及应用[J]. 软件学报, 2000, 11(4): 488-493. QI Yuan, TIAN Jie, DENG Xiang. Genetic algorithm based fingerprint matching algorithm and its application in automated fingerprint recognition system[J]. Journal of software, 2000, 11(4): 488-493.

[14]SHENG W, HOWELLS G, FAIRHUST M C, et al. Consensus fingerprint matching with genetically optimised approach[J]. Pattern recognition, 2009, 42(7): 1399-1407.

[15]GHAZVINI M, SUFIKARIMI H, MOHAMMADI K. Fingerprint matching using genetic algorithm and triangle descriptors[C]//Proceedings of the 19th Iranian Conference on Electrical Engineering. Tehran, Iran, 2011: 1-6.

[16]吴一全, 张金矿. 基于Tent映射混沌粒子群的快速指纹特征匹配[J]. 信号处理, 2011, 27(2): 168-173. WU Yiquan, ZHANG Jinkuang. Fast fingerprint minutiae matching based on Tent map chaotic particle swarm optimization[J]. Sigal processing, 2011, 27(2): 168-173.

[17]KARABOGA D, BASTURK B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied soft computing, 2008, 8(1): 687-697.

[18]KARABOGA D, OZTURK C. A novel clustering approach: Artificial bee colony (ABC) algorithm[J]. Applied soft computing, 2011, 11(1): 652-657.

[19]秦全德, 程适, 李丽, 等. 人工蜂群算法研究综述[J]. 智能系统学报, 2014, 9(2): 127-135. QIN Quande, CHENG Shi, LI Li, et al. Artificial bee colony algorithm: a survey[J]. CAAI transactions on intelligent systems, 2014, 9(2): 127-135.

[20]吴一全, 王凯, 曹鹏祥. 蜂群优化的二维非对称Tsallis交叉熵图像阈值选取[J]. 智能系统学报, 2015, 10(1): 103-112. WU Yiquan, WANG Kai, CAO Pengxiang. Two-dimensional asymmetric tsallis cross entropy image threshold selection using bee colony optimization[J]. CAAI transactions on intelligent systems, 2015, 10(1): 103-112.

史骏鹏,男，1990年生，硕士研究生，主要研究方向为图像处理与视频通信。发表学术论文3篇。

吴一全，男，1963年生，博士，教授，博士生导师，主要研究方向为图像处理与分析、目标检测与识别、智能信息处理。发表学术论文250余篇。

A fingerprint minutiae matching algorithm based on chaotic bee colony optimization

SHI Junpeng1, WU Yiquan1,2

(1. College of Electronic and Information Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China; 2. Jiangsu Key Laboratory of Image and Video Understanding for Social Safety, Nanjing University of Science and Technology, Nanjing 210094, China)

In order to further improve the operational speed and the recognition efficiency of fingerprint matching algorithms, a fingerprint matching algorithm based on chaotic bee colony activity and a variable boundary box was proposed. Firstly, by combining the advantages of artificial bee colony optimization including fast convergence times, fewer control parameters, and the lack of local optima, with the features of a chaos strategy including its random-like property and ergodicity, the chaotic bee colony activity was introduced into point pattern matching for fingerprint images. A corresponding fitness function incorporating both matching accuracy and operational time was then designed. The corresponding fitness function was then used to estimate the geometric transformation parameters for fingerprint rough matching. Finally, a variable boundary box can be used for fine matching, because it avoids any influences relating to local deformation of the fingerprint images. A large number of experimental results show that, compared with two alternative fingerprint matching algorithms (based on local features and genetic algorithm optimization, respectively) the proposed algorithm has a shorter operational time and has higher matching accuracy.

fingerprint recognition; minutiae matching; swarm intelligence optimization; artificial bee colony; chaos strategy; variable boundary box; fitness function; polar coordinates

2016-01-28.

日期：2016-07-18.

国家自然科学基金项目(61573183)；江苏省社会安全图像与视频理解重点实验室(南京理工大学)开放基金项目(JSKL201302)；江苏省高校优势学科建设工程项目(2012).

吴一全.E-mail:nuaaimage@163.com.

TP391.4

A

1673-4785(2016)05-0613-06

10.11992/tis.201601038

http://www.cnki.net/kcms/detail/23.1538.TP.20160718.1522.008.html

史骏鹏，吴一全.基于混沌蜂群优化的指纹匹配算法[J]. 智能系统学报， 2016, 11(5): 613-618.

英文引用格式：SHI Junpeng, WU Yiquan. A fingerprint minutiae matching algorithm based on chaotic bee colony optimization[J]. CAAI transactions on intelligent systems, 2016,11(5): 613-618.