第11卷第5期 智能系统学报 Vol.11 No.5 2016年10月 CAAI Transactions on Intelligent Systems 0ct.2016 D0I:10.11992/is.201601038 网络出版地址：htp:/www.cnki.net/kcms/detail/23.1538.TP.20160718.1522.008.html 基于混沌蜂群优化的指纹匹配算法 史骏鹏，吴一全12 (1.南京航空航天大学电子信息工程学院，江苏南京211106；2.南京理工大学江苏省社会安全图像与视频理解重 点实验室，江苏南京210094) 摘要：为了进一步加快指纹匹配算法的运算速度、提高识别效率，提出了一种基于混沌蜂群优化和可变界限盒的 指纹匹配算法。首先，结合人工蜂群优化算法收敛速度快、，控制参数少、能够避免局部最优等优点以及混沌策略的 类随机性、高遍历性等特点，在指纹点匹配中引入混沌蜂群优化算法，并设计兼顾了匹配精度和运算时间的适应度 函数：然后利用适应度函数估计出指纹特征匹配的几何变换参数并进行指纹点特征的粗匹配：最后，利用可变界限 盒进行精匹配，避免指纹图像局部形变带来的影响。大量实验结果表明，与基于局部特征的指纹匹配算法、基于遗 传算法优化的指纹匹配算法相比，本文提出的算法所需运算时间更短，匹配精度更高。 关键词：指纹识别：特征点匹配：群智能优化；人工蜂群：混沌策略：可变界限盒：适应度函数：极坐标 中图分类号：TP391.4文献标志码：A文章编号：1673-4785(2016)05-0613-06 中文引用格式：史骏鹏，吴一全.基于混沌蜂群优化的指纹匹配算法[J].智能系统学报，2016,11(5)：613-618. 英文引用格式：SHIJunpeng,WU Yiquan..A fingerprint minutiae matching algorithm based on chaotic bee colony optimization[J]. CAAI transactions on intelligent systems,2016,11(5):613-618. A fingerprint minutiae matching algorithm based on chaotic bee colony optimization SHI Junpeng',WU Yiquan2 (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) Abstract:In order to further improve the operational speed and the recognition efficiency of fingerprint matching al- gorithms,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. Keywords: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)：江苏省社会安全图像与视频键环节之一，直接影响识别的速度和精度。如何保 理解重点实验室（南京理工大学）开放基金项目(JSK201302): 江苏省高校优势学科建设工程项目(2012). 证指纹特征匹配算法的实时性和识别率，一直是国 通信作者：吴一全.E-mail:nuaaimage(@163.com
第 １１ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．５ ２０１６ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０１０３８ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０７１８．１５２２．００８．ｈｔｍｌ 基于混沌蜂群优化的指纹匹配算法 史骏鹏１ ，吴一全１，２ （１．南京航空航天大学 电子信息工程学院，江苏 南京 ２１１１０６； ２．南京理工大学 江苏省社会安全图像与视频理解重 点实验室，江苏 南京 ２１００９４） 摘 要：为了进一步加快指纹匹配算法的运算速度、提高识别效率，提出了一种基于混沌蜂群优化和可变界限盒的 指纹匹配算法。 首先，结合人工蜂群优化算法收敛速度快、控制参数少、能够避免局部最优等优点以及混沌策略的 类随机性、高遍历性等特点，在指纹点匹配中引入混沌蜂群优化算法，并设计兼顾了匹配精度和运算时间的适应度 函数；然后利用适应度函数估计出指纹特征匹配的几何变换参数并进行指纹点特征的粗匹配；最后，利用可变界限 盒进行精匹配，避免指纹图像局部形变带来的影响。 大量实验结果表明，与基于局部特征的指纹匹配算法、基于遗 传算法优化的指纹匹配算法相比，本文提出的算法所需运算时间更短，匹配精度更高。 关键词：指纹识别；特征点匹配；群智能优化；人工蜂群；混沌策略；可变界限盒；适应度函数；极坐标 中图分类号：ＴＰ３９１．４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０５⁃０６１３⁃０６ 中文引用格式：史骏鹏，吴一全．基于混沌蜂群优化的指纹匹配算法［Ｊ］． 智能系统学报， ２０１６， １１（５）： ６１３⁃６１８． 英文引用格式：ＳＨＩ Ｊｕｎｐｅｎｇ， ＷＵ Ｙｉｑｕａｎ． Ａ ｆｉｎｇｅｒｐｒｉｎｔ ｍｉｎｕｔｉａｅ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｈａｏｔｉｃ ｂｅｅ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（５）： ６１３⁃６１８． Ａ ｆｉｎｇｅｒｐｒｉｎｔ ｍｉｎｕｔｉａｅ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｈａｏｔｉｃ ｂｅｅ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ＳＨＩ Ｊｕｎｐｅｎｇ １ ， ＷＵ Ｙｉｑｕａｎ １，２ （１． Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ａｅｒｏｎａｕｔｉｃｓ ａｎｄ Ａｓｔｒｏｎａｕｔｉｃｓ， Ｎａｎｊｉｎｇ ２１１１０６， Ｃｈｉｎａ； ２． Ｊｉａｎｇｓｕ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｉｍａｇｅ ａｎｄ Ｖｉｄｅｏ Ｕｎｄｅｒｓｔａｎｄｉｎｇ ｆｏｒ Ｓｏｃｉａｌ Ｓａｆｅｔｙ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ ２１００９４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｆｕｒｔｈｅｒ ｉｍｐｒｏｖｅ ｔｈｅ ｏｐｅｒａｔｉｏｎａｌ ｓｐｅｅｄ ａｎｄ ｔｈｅ ｒｅｃｏｇｎｉｔｉｏｎ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ａｌ⁃ ｇｏｒｉｔｈｍｓ， ａ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｈａｏｔｉｃ ｂｅｅ ｃｏｌｏｎｙ ａｃｔｉｖｉｔｙ ａｎｄ ａ ｖａｒｉａｂｌｅ ｂｏｕｎｄａｒｙ ｂｏｘ ｗａｓ ｐｒｏｐｏｓｅｄ． Ｆｉｒｓｔｌｙ， ｂｙ ｃｏｍｂｉｎｉｎｇ ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆ ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｎｃｌｕｄｉｎｇ ｆａｓｔ ｃｏｎｖｅｒｇｅｎｃｅ ｔｉｍｅｓ， ｆｅｗｅｒ ｃｏｎｔｒｏｌ ｐａｒａｍｅｔｅｒｓ， ａｎｄ ｔｈｅ ｌａｃｋ ｏｆ ｌｏｃａｌ ｏｐｔｉｍａ， ｗｉｔｈ ｔｈｅ ｆｅａｔｕｒｅｓ ｏｆ ａ ｃｈａｏｓ ｓｔｒａｔｅｇｙ ｉｎｃｌｕｄｉｎｇ ｉｔｓ ｒａｎｄｏｍ⁃ｌｉｋｅ ｐｒｏｐｅｒｔｙ ａｎｄ ｅｒｇｏｄｉｃｉｔｙ， ｔｈｅ ｃｈａｏｔｉｃ ｂｅｅ ｃｏｌｏｎｙ ａｃｔｉｖｉｔｙ ｗａｓ ｉｎｔｒｏｄｕｃｅｄ ｉｎｔｏ ｐｏｉｎｔ ｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ ｆｏｒ ｆｉｎｇｅｒｐｒｉｎｔ ｉｍａｇｅｓ． Ａ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ ｉｎｃｏｒｐｏｒａｔｉｎｇ ｂｏｔｈ ｍａｔｃｈｉｎｇ ａｃｃｕｒａｃｙ ａｎｄ ｏｐｅｒａｔｉｏｎａｌ ｔｉｍｅ ｗａｓ ｔｈｅｎ ｄｅｓｉｇｎｅｄ． Ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ ｗａｓ ｔｈｅｎ ｕｓｅｄ ｔｏ ｅｓｔｉｍａｔｅ ｔｈｅ ｇｅｏｍｅｔｒｉｃ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｐａｒａｍｅｔｅｒｓ ｆｏｒ ｆｉｎｇｅｒｐｒｉｎｔ ｒｏｕｇｈ ｍａｔｃｈｉｎｇ． Ｆｉｎａｌｌｙ， ａ ｖａｒｉａｂｌｅ ｂｏｕｎｄａｒｙ ｂｏｘ ｃａｎ ｂｅ ｕｓｅｄ ｆｏｒ ｆｉｎｅ ｍａｔｃｈｉｎｇ， ｂｅｃａｕｓｅ ｉｔ ａｖｏｉｄｓ ａｎｙ ｉｎｆｌｕｅｎｃｅｓ ｒｅｌａｔｉｎｇ ｔｏ ｌｏｃａｌ ｄｅｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｆｉｎｇｅｒｐｒｉｎｔ ｉｍａｇｅｓ． Ａ ｌａｒｇｅ ｎｕｍｂｅｒ ｏｆ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ， ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｗｏ ａｌｔｅｒｎａｔｉｖｅ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍｓ （ｂａｓｅｄ ｏｎ ｌｏｃａｌ ｆｅａｔｕｒｅｓ ａｎｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ｒｅｓｐｅｃｔｉｖｅｌｙ） ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｈａｓ ａ ｓｈｏｒｔｅｒ ｏｐｅｒａｔｉｏｎａｌ ｔｉｍｅ ａｎｄ ｈａｓ ｈｉｇｈｅｒ ｍａｔｃｈｉｎｇ ａｃｃｕｒａｃｙ． Ｋｅｙｗｏｒｄｓ：ｆｉｎｇｅｒｐｒｉｎｔ ｒｅｃｏｇｎｉｔｉｏｎ； ｍｉｎｕｔｉａｅ ｍａｔｃｈｉｎｇ； ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ ｏｐｔｉｍｉｚａｔｉｏｎ； ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ； ｃｈａｏｓ ｓｔｒａｔｅｇｙ； ｖａｒｉａｂｌｅ ｂｏｕｎｄａｒｙ ｂｏｘ； ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ； ｐｏｌａｒ ｃｏｏｒｄｉｎａｔｅｓ 收稿日期：２０１６⁃０１⁃２８． 网络出版日期：２０１６⁃０７⁃１８． 基金项目：国家自然科学基金项目（６１５７３１８３）；江苏省社会安全图像与视频 理解重点实验室（南京理工大学）开放基金项目（ＪＳＫＬ２０１３０２）； 江苏省高校优势学科建设工程项目（２０１２）． 通信作者：吴一全．Ｅ⁃ｍａｉｌ：ｎｕａａｉｍａｇｅ＠ １６３．ｃｏｍ． 指纹作为人体的基本特征之一，具有唯一性、终 身不变性的特点，已被广泛用于个体身份的验证和 识别。 指纹图像的特征匹配作为指纹识别系统的关 键环节之一，直接影响识别的速度和精度。 如何保 证指纹特征匹配算法的实时性和识别率，一直是国
·614. 智能系统学报 第11卷 内外学者关注的问题之一。 传算法对指纹匹配算法进行优化，匹配效率得到一 目前主流的指纹匹配算法可以分为整体匹 定的提升。文献「15]在指纹匹配中采用三角描述 配3]和特征点匹配[4]两大类。其中特征点匹配 符作为初始种群，提高了遗传算法的收敛速度。粒 通过对指纹特征点进行某些几何变换（平移、旋转、 子群算法与遗传算法类似，但不涉及遗传算法的交 缩放)，使待匹配的指纹特征点和模板指纹特征点 叉和变异，而是粒子在解空间中搜索最优位置，易于 一一对应，从而达到指纹识别的目的。指纹采集过 实现。文献[l6]提出了一种基于Tent映射混沌粒 程中无法避免的噪声和非线性形变干扰，对最终的 子群的快速指纹特征匹配算法，在Tent映射和混沌 指纹匹配结果影响很大。文献[1-3]使用全局特征 粒子群优化的基础上快速寻找适合的参考点并进行 进行整体匹配，但容易受到指纹脊部结构形变和噪 精确匹配。然而粒子群算法的优化性能会随着问题 声带来的影响。文献[4]通过获取相邻细节特征点 维数的增加而不断下降，与之相比，人工蜂群(artifi 的角度差和距离差，构建特征向量进行局部匹配，提 cial bee colony,ABC)算法控制参数较少，全局寻优 高了指纹匹配的精度，但未考虑到指纹图像非线性 能力较强，能解决较为复杂的优化问题，可望应用于 形变所造成的干扰。界限盒准则限定了匹配点之间 指纹匹配中[-20 角度误差和距离误差的容许范围，能够在一定程度 本文提出了一种基于混沌蜂群优化和可变界限 上克服非线性形变的干扰。文献[5]结合半可变界 盒的分层指纹匹配算法。首先，利用蜂群优化算法 限盒对指纹特征点进行二次匹配，虽然提高了匹配 收敛快、可避免局部最优、控制参数少等优点以及混 的精度，但匹配时间波动较大。文献[6]提出了一 沌策略的类随机性、高遍历性等特点，将混沌蜂群优 种基于细节点局部配准的指纹匹配算法，以特征点 化算法引入指纹图像的点模式匹配中，搜索两幅指 的纹理信息和结构信息为特征，进行全局匹配获得 纹图像之间可能存在的平移、旋转等几何变换参数： 指纹间的公共区域：然后将公共区域内的细节特征 其中，混沌蜂群优化的适应度函数将兼顾匹配精度 点及其邻近的参照点进行分组：最后根据界限盒约 和运行时间的：然后利用可变界限盒柔性匹配进行 束条件，在极坐标系下进行指纹的匹配。文献[7] 精匹配，避免指纹图像局部形变和噪声的干扰。在 建立局部特征点的三角模型，利用可变界限盒进行 实验结果与分析部分，将本文算法与基于局部特征 指纹特征点匹配，匹配结果精度较高。此外，许多学 的指纹匹配算法[1]、基于遗传算法优化的指纹匹配 者还考虑将指纹特征点和其他特征信息相结合共同 算法[进行了对比实验。 用于指纹匹配，也有利于提高匹配的精度。文献 1 基于混沌蜂群优化的点匹配算法 「8]从原本筛选别除出的非匹配特征点对中提取出 被忽视的细节信息，结合未剔除的匹配特征点，一起 指纹图像在采集过程中，由于指纹本身的旋转、 用于指纹的匹配。指纹的采集区域和采集方向不 平移以及形变等问题，导致采集到的指纹特征点和 同，往往导致指纹图像中提取出的特征点相似度很 数据库中的模板特征点存在差异。假设集合P是 低，影响匹配的结果。针对这一问题，文献[9]提出 采集的待匹配指纹图像特征点集，特征点的个数为 了一种具有全局特性的“利手特征”用于指纹图像 M:集合Q是预先存储在数据库中的模板指纹图像 匹配，一定程度上提高了匹配精度。文献[10]利用 特征点集，特征点的个数为N。这两个点集分别表 局部特征点之间的距离、特征点类型等信息构建新 示为 的特征向量，用以实现指纹的全局匹配。文献[11] P={(x,,d,),…,(axM,,d,)} (1) 提出了一种基于脊线特征的指纹模糊匹配算法，建 Q={(x,,d,),…,(x8,y%,d,)} 立衡量相似程度的模糊集合，并利用加权平均法综 式中：(x,,d,)和(x,,d,)分别记录了点 合评判脊线总体相似度，然后结合特征点相似度最 集P和Q中第i个特征点的4种信息：x和x为特 终得出匹配结果。但是上述算法较为复杂，均需要 征点横坐标，y和y为特征点纵坐标，d和d表示 较长的运算时间。 特征点的类型（端点、分叉点），和为特征点的 为了满足指纹识别实时性的要求，人们开始考 方向。 虑基于群体智能的优化算法，并应用到指纹匹配中。 1.1指纹细节特征匹配 遗传算法、粒子群优化算法等能对搜索策略实时调 假设指纹特征点集P和Q为匹配的指纹图像， 整，避免了繁琐冗余的遍历性匹配，有效地提升了指 则可以通过一定的平移、旋转、缩放等几何处理，将 纹特征匹配的搜索效率。文献[13]和[14]利用遗 特征点集P近似变换成特征点集Q。通过搜索这些
内外学者关注的问题之一。 目前主流的指纹匹配算法可以分为整体匹 配［１⁃３］和特征点匹配［４⁃１２］ 两大类。 其中特征点匹配 通过对指纹特征点进行某些几何变换（平移、旋转、 缩放），使待匹配的指纹特征点和模板指纹特征点 一一对应，从而达到指纹识别的目的。 指纹采集过 程中无法避免的噪声和非线性形变干扰，对最终的 指纹匹配结果影响很大。 文献［１⁃３］使用全局特征 进行整体匹配，但容易受到指纹脊部结构形变和噪 声带来的影响。 文献［４］通过获取相邻细节特征点 的角度差和距离差，构建特征向量进行局部匹配，提 高了指纹匹配的精度，但未考虑到指纹图像非线性 形变所造成的干扰。 界限盒准则限定了匹配点之间 角度误差和距离误差的容许范围，能够在一定程度 上克服非线性形变的干扰。 文献［５］结合半可变界 限盒对指纹特征点进行二次匹配，虽然提高了匹配 的精度，但匹配时间波动较大。 文献［６］ 提出了一 种基于细节点局部配准的指纹匹配算法，以特征点 的纹理信息和结构信息为特征，进行全局匹配获得 指纹间的公共区域；然后将公共区域内的细节特征 点及其邻近的参照点进行分组；最后根据界限盒约 束条件，在极坐标系下进行指纹的匹配。 文献［７］ 建立局部特征点的三角模型，利用可变界限盒进行 指纹特征点匹配，匹配结果精度较高。 此外，许多学 者还考虑将指纹特征点和其他特征信息相结合共同 用于指纹匹配，也有利于提高匹配的精度。 文献 ［８］从原本筛选剔除出的非匹配特征点对中提取出 被忽视的细节信息，结合未剔除的匹配特征点，一起 用于指纹的匹配。 指纹的采集区域和采集方向不 同，往往导致指纹图像中提取出的特征点相似度很 低，影响匹配的结果。 针对这一问题，文献［９］提出 了一种具有全局特性的“利手特征”用于指纹图像 匹配，一定程度上提高了匹配精度。 文献［１０］利用 局部特征点之间的距离、特征点类型等信息构建新 的特征向量，用以实现指纹的全局匹配。 文献［１１］ 提出了一种基于脊线特征的指纹模糊匹配算法，建 立衡量相似程度的模糊集合，并利用加权平均法综 合评判脊线总体相似度，然后结合特征点相似度最 终得出匹配结果。 但是上述算法较为复杂，均需要 较长的运算时间。 为了满足指纹识别实时性的要求，人们开始考 虑基于群体智能的优化算法，并应用到指纹匹配中。 遗传算法、粒子群优化算法等能对搜索策略实时调 整，避免了繁琐冗余的遍历性匹配，有效地提升了指 纹特征匹配的搜索效率。 文献［１３］和［１４］利用遗 传算法对指纹匹配算法进行优化，匹配效率得到一 定的提升。 文献［１５］在指纹匹配中采用三角描述 符作为初始种群，提高了遗传算法的收敛速度。 粒 子群算法与遗传算法类似，但不涉及遗传算法的交 叉和变异，而是粒子在解空间中搜索最优位置，易于 实现。 文献［１６］提出了一种基于 Ｔｅｎｔ 映射混沌粒 子群的快速指纹特征匹配算法，在 Ｔｅｎｔ 映射和混沌 粒子群优化的基础上快速寻找适合的参考点并进行 精确匹配。 然而粒子群算法的优化性能会随着问题 维数的增加而不断下降，与之相比，人工蜂群（ａｒｔｉｆｉ⁃ ｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ， ＡＢＣ）算法控制参数较少，全局寻优 能力较强，能解决较为复杂的优化问题，可望应用于 指纹匹配中［１７⁃２０］ 。 本文提出了一种基于混沌蜂群优化和可变界限 盒的分层指纹匹配算法。 首先，利用蜂群优化算法 收敛快、可避免局部最优、控制参数少等优点以及混 沌策略的类随机性、高遍历性等特点，将混沌蜂群优 化算法引入指纹图像的点模式匹配中，搜索两幅指 纹图像之间可能存在的平移、旋转等几何变换参数； 其中，混沌蜂群优化的适应度函数将兼顾匹配精度 和运行时间的；然后利用可变界限盒柔性匹配进行 精匹配，避免指纹图像局部形变和噪声的干扰。 在 实验结果与分析部分，将本文算法与基于局部特征 的指纹匹配算法［１０］ 、基于遗传算法优化的指纹匹配 算法［１４］进行了对比实验。 １ 基于混沌蜂群优化的点匹配算法 指纹图像在采集过程中，由于指纹本身的旋转、 平移以及形变等问题，导致采集到的指纹特征点和 数据库中的模板特征点存在差异。 假设集合 Ｐ 是 采集的待匹配指纹图像特征点集，特征点的个数为 Ｍ；集合 Ｑ 是预先存储在数据库中的模板指纹图像 特征点集，特征点的个数为 Ｎ。 这两个点集分别表 示为 Ｐ ＝ ｘ ｐ １ ，ｙ ｐ １ ，ｄ ｐ １ ，θ ｐ １ ( ) ，…， ｘ ｐ Ｍ ，ｙ ｐ Ｍ ，ｄ ｐ Ｍ ，θ ｐ Ｍ { ( ) } Ｑ ＝ ｘ ｑ １ ，ｙ ｑ １ ，ｄ ｑ １ ，θ ｑ １ ( ) ，…， ｘ ｑ Ｎ，ｙ ｑ Ｎ，ｄ ｑ Ｎ，θ ｑ Ｎ { ( ) } （１） 式中： ｘ ｐ ｉ ，ｙ ｐ ｉ ，ｄ ｐ ｉ ，θ ｐ ｉ ( ) 和 ｘ ｑ ｉ ，ｙ ｑ ｉ ，ｄ ｑ ｉ ，θ ｑ ｉ ( ) 分别记录了点 集 Ｐ 和 Ｑ 中第 ｉ 个特征点的 ４ 种信息：ｘ ｐ ｉ 和 ｘ ｑ ｉ 为特 征点横坐标，ｙ ｐ ｉ 和 ｙ ｑ ｉ 为特征点纵坐标，ｄ ｐ ｉ 和 ｄ ｑ ｉ 表示 特征点的类型（端点、分叉点），θ ｐ ｉ 和 θ ｑ ｉ 为特征点的 方向。 １．１ 指纹细节特征匹配 假设指纹特征点集 Ｐ 和 Ｑ 为匹配的指纹图像， 则可以通过一定的平移、旋转、缩放等几何处理，将 特征点集 Ｐ 近似变换成特征点集 Ｑ。 通过搜索这些 ·６１４· 智 能 系 统 学 报 第 １１ 卷
第5期 史骏鹏，等：基于混沌蜂群优化的指纹匹配算法 ·615. 几何变换参数，使一组特征点经几何变换后与另一 像采集时的噪声干扰和非线性形变，指纹图像的去 组特征点尽可能多的对应，达成一定的阈值条件，即 噪、增强、细化等预处理也会对最终参与匹配的指纹 可判断这两组指纹图像是匹配的。特征点集的变换 特征点造成影响。即使是同一手指的两幅指纹图 包括平移、旋转和尺度变换，由于采集得到的指纹图 像，也不一定能获得位置、方向及数目高度一致的两 像大小基本一致，因此尺度变换往往可以忽略，只需 组特征点集。因此设计一个合适的匹配适应度函数 通过平移旋转矩阵Hr对特征点进行变换： 是很有必要的，它在诸多干扰下依旧能较为准确地 判断出指纹的匹配关系。 c0s(△0) -sin(△0)00△x y 为了提升指纹匹配过程中的匹配速度和精度， sin(A0) c0s(40) 00△ 本文算法引入了分层匹配的思想，将匹配过程分为 d 0 0 10 0 粗匹配和精匹配2个部分。粗匹配通过全局仿射变 0 0 0 1 换确定大致相符的匹配，点对：精匹配则将匹配点对 0 0 0 0 变换到极坐标系下，并根据可变限界盒准则设计匹 (2) 配适应度函数，对其进行比较。 式中：4x和△y分别为横坐标和纵坐标的平移因子， 1)粗匹配。假定变换因子分别为△x、△y和△0 △0为旋转因子。通过这3个因子对P进行几何变 利用式(2)的平移旋转变换矩阵将指纹特征点集P 换，获得特征点集T,若T中某特征点：= 变换成特征点集T:计算T和Q中所有特征点的欧 (x,y,,)与Q中某特征点9=(x,,d,明)近 氏距离和特征点类型差，并将结果放在集合J中： 似相等，则可认定这两个特征点为匹配特征点对。 (aa.6a)laa=vxx)+(y:-y)2; 1.2人工蜂群优化及混沌策略 I= 84=|d-d|,1≤i≤M,1≤k≤N 人工蜂群优化算法由3个部分组成，即引领蜂 观察蜂和侦查蜂（也称雇佣蜂、跟随蜂和侦查蜂）， (4) 其具体过程为：1)每只引领蜂都对应一个确定的食 式中：a为指纹特征点间的欧氏距离：δ为特征点类 物源，并在其邻域随机搜索一个新的食物源，然后将 型是否一致的判断指标。若6为0，则两个特征点 食物源的信息进行反馈，送到观察蜂处：2)比较反 类型一致：若不为0，则两个特征点类型不一致，肯 馈回的食物源收益度大小后，观察蜂会选取一个食 定不匹配。 物源作为目标并在其附近重复进行搜索，不断寻找 对集合J中的值，根据a,从小到大的顺序进行 更优的食物源：3)当观察蜂在搜索某个食物源时， 判断：若a,小于给定的阈值T,并且相应的8，为0， 若收益度基本不再发生变化，便放弃该食物源，转化 则确定P:=(x,,d,)和g=(x,y,d9,明)为粗 为侦查蜂重新开始搜索。不断循环迭代这一过程直 匹配特征点对：否则，继续对下一个a4进行判断，直 到搜索到最佳的食物源位置。需要注意的是，在迭 到其满足条件，产生一对粗匹配特征点对；若α4均 代过程中，蜂群对于食物源位置的搜索需要遵循一 大于阈值T,则不存在P:的粗匹配特征点。对T中 定的规则：引领蜂和食物源是一一对应的关系，其数 所有的特征点都进行粗匹配点对搜索，并记录粗匹 目必须和食物源数目保持一致：观察蜂的数目也需 配特征点对的数目n,利用式(5)计算相似度f (5) 要和引领蜂的数目一一对应。 fm=(n×nr)/(M×N) 为了更好地避免蜂群陷入局部极值，在蜂群优 如果f小于阈值Tm,那么就将其作为匹配适应度 化算法中引入具有类随机性和遍历性等特点的混沌 f(△x,△y,△)，无需进行精匹配。否则，需要进行 精匹配。 策略，对侦查蜂进行初始化，循环迭代跳出局部最优 解位置，最终遍历搜寻出全局最优解位置。混沌序 2)精匹配。首先将特征点集P和Q转换到极 坐标系下，转换公式为 列的公式为 23, 0≤B≤0.5 √(xm-x)2+(ym-ye) B+1= (3) 2(1-B), 0.5<B.≤1 e arctan2 式中：B表示序列中的参数，B1表示下一个序列的 (6) d 参数。 d 1.3适应度函数 0m-0 指纹特征点受到很多因素的制约，除了指纹图 式中：(xm,ym,dn,Bm)为待转换的匹配特征点
几何变换参数，使一组特征点经几何变换后与另一 组特征点尽可能多的对应，达成一定的阈值条件，即 可判断这两组指纹图像是匹配的。 特征点集的变换 包括平移、旋转和尺度变换，由于采集得到的指纹图 像大小基本一致，因此尺度变换往往可以忽略，只需 通过平移旋转矩阵 ＨＲＴ对特征点进行变换： ｘ ｔ ｉ ｙ ｔ ｉ ｄ ｔ ｉ θ ｔ ｉ １ é ë ê ê ê ê ê ê êê ù û ú ú ú ú ú ú úú ＝ ｃｏｓ（Δθ） － ｓｉｎ（Δθ） ０ ０ Δｘ ｓｉｎ（Δθ） ｃｏｓ（Δθ） ０ ０ Δｙ ０ ０ １ ０ ０ ０ ０ ０ １ Δθ ０ ０ ０ ０ １ é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú ｘ ｐ ｉ ｙ ｐ ｉ ｄ ｐ ｉ θ ｐ ｉ １ é ë ê ê ê ê ê ê êê ù û ú ú ú ú ú ú úú （２） 式中：Δｘ 和 Δｙ 分别为横坐标和纵坐标的平移因子， Δθ 为旋转因子。 通过这 ３ 个因子对 Ｐ 进行几何变 换， 获 得 特 征 点 集 Ｔ， 若 Ｔ 中 某 特 征 点 ｔ ｉ ＝ ｘ ｔ ｉ，ｙ ｔ ｉ，ｄ ｔ ｉ，θ ｔ ｉ ( ) 与 Ｑ 中某特征点 ｑｊ ＝ ｘ ｑ ｊ ，ｙ ｑ ｊ ，ｄ ｑ ｊ ，θ ｑ ｊ ( ) 近 似相等，则可认定这两个特征点为匹配特征点对。 １．２ 人工蜂群优化及混沌策略 人工蜂群优化算法由 ３ 个部分组成，即引领蜂、 观察蜂和侦查蜂（也称雇佣蜂、跟随蜂和侦查蜂）， 其具体过程为：１）每只引领蜂都对应一个确定的食 物源，并在其邻域随机搜索一个新的食物源，然后将 食物源的信息进行反馈，送到观察蜂处；２） 比较反 馈回的食物源收益度大小后，观察蜂会选取一个食 物源作为目标并在其附近重复进行搜索，不断寻找 更优的食物源；３） 当观察蜂在搜索某个食物源时， 若收益度基本不再发生变化，便放弃该食物源，转化 为侦查蜂重新开始搜索。 不断循环迭代这一过程直 到搜索到最佳的食物源位置。 需要注意的是，在迭 代过程中， 蜂群对于食物源位置的搜索需要遵循一 定的规则：引领蜂和食物源是一一对应的关系，其数 目必须和食物源数目保持一致；观察蜂的数目也需 要和引领蜂的数目一一对应。 为了更好地避免蜂群陷入局部极值，在蜂群优 化算法中引入具有类随机性和遍历性等特点的混沌 策略，对侦查蜂进行初始化，循环迭代跳出局部最优 解位置，最终遍历搜寻出全局最优解位置。 混沌序 列的公式为 βｋ＋１ ＝ ２βｋ， ０ ≤ βｋ ≤ ０．５ ２ １ － βｋ { ( ) ， ０．５ ＜ βｋ ≤ １ （３） 式中：βｋ 表示序列中的参数，βｋ＋１表示下一个序列的 参数。 １．３ 适应度函数 指纹特征点受到很多因素的制约，除了指纹图 像采集时的噪声干扰和非线性形变，指纹图像的去 噪、增强、细化等预处理也会对最终参与匹配的指纹 特征点造成影响。 即使是同一手指的两幅指纹图 像，也不一定能获得位置、方向及数目高度一致的两 组特征点集。 因此设计一个合适的匹配适应度函数 是很有必要的，它在诸多干扰下依旧能较为准确地 判断出指纹的匹配关系。 为了提升指纹匹配过程中的匹配速度和精度， 本文算法引入了分层匹配的思想，将匹配过程分为 粗匹配和精匹配 ２ 个部分。 粗匹配通过全局仿射变 换确定大致相符的匹配点对；精匹配则将匹配点对 变换到极坐标系下，并根据可变限界盒准则设计匹 配适应度函数，对其进行比较。 １）粗匹配。 假定变换因子分别为 Δｘ、Δｙ 和 Δθ， 利用式（２）的平移旋转变换矩阵将指纹特征点集 Ｐ 变换成特征点集 Ｔ；计算 Ｔ 和 Ｑ 中所有特征点的欧 氏距离和特征点类型差，并将结果放在集合 Ｊ 中： Ｊ ＝ ａｉｋ，δｉｋ ( ) ａｉｋ ＝ ｘ ｔ ｉ － ｘ ｑ ｋ ( ) ２ ＋ ｙ ｔ ｉ － ｙ ｑ ｋ ( ) ２ ； δｉｋ ＝ ｄ ｔ ｉ － ｄ ｑ { ｋ ，１ ≤ ｉ ≤ Ｍ，１ ≤ ｋ ≤ Ｎ （４） 式中：ａｉｋ为指纹特征点间的欧氏距离；δｉｋ为特征点类 型是否一致的判断指标。 若 δｉｋ为 ０，则两个特征点 类型一致；若不为 ０，则两个特征点类型不一致，肯 定不匹配。 对集合 Ｊ 中的值，根据 ａｉｋ从小到大的顺序进行 判断：若 ａｉｊ小于给定的阈值 Ｔａ ，并且相应的 δｉｊ为 ０， 则确定 ｐｉ ＝ ｘ ｐ ｉ ，ｙ ｐ ｉ ，ｄ ｐ ｉ ，θ ｐ ｉ ( ) 和 ｑｊ ＝ ｘ ｑ ｊ ，ｙ ｑ ｊ ，ｄ ｑ ｊ ，θ ｑ ｊ ( ) 为粗 匹配特征点对；否则，继续对下一个 ａｉｋ进行判断，直 到其满足条件，产生一对粗匹配特征点对；若 ａｉｋ均 大于阈值 Ｔａ ，则不存在 ｐｉ 的粗匹配特征点。 对 Ｔ 中 所有的特征点都进行粗匹配点对搜索，并记录粗匹 配特征点对的数目 ｎｆ，利用式（５）计算相似度 ｆ ｓｉｍ ｆ ｓｉｍ ＝ （ｎｆ × ｎｆ） ／ （Ｍ × Ｎ） （５） 如果 ｆ ｓｉｍ小于阈值 Ｔｓｉｍ ，那么就将其作为匹配适应度 ｆ ｆｉｔ (Δｘ，Δｙ，Δθ) ，无需进行精匹配。 否则，需要进行 精匹配。 ２）精匹配。 首先将特征点集 Ｐ 和 Ｑ 转换到极 坐标系下，转换公式为 ｒ ｅ ｄ η æ è ç ç ç ç ö ø ÷ ÷ ÷ ÷ ＝ （ｘｍ － ｘｃ） ２ ＋ （ｙｍ － ｙｃ） ２ ａｒｃｔａｎ２ ｙｍ － ｙｃ ｘｍ － ｘｃ æ è ç ö ø ÷ － θｃ ｄｍ θｍ － θｃ æ è ç ç ç ç ç ç ç ö ø ÷ ÷ ÷ ÷ ÷ ÷ ÷ （６） 式中： ｘｍ ，ｙｍ ，ｄｍ ，θｍ ( ) 为 待 转 换 的 匹 配 特 征 点， 第 ５ 期 史骏鹏，等：基于混沌蜂群优化的指纹匹配算法 ·６１５·
·616 智能系统学报 第11卷 (x,yc,d。,9)为极坐标原点，(r,e,d,n)则为转换后 -l≤T, 特征点在极坐标系下的极径、极角、特征点类型以及 le-el≤T 特征点方向差。 (10) 1d-d1=0 相较于其他指纹匹配算法，本文算法无需预先 计算出指纹中心点作为极坐标原点，而是挑选粗匹 n-n|≤T, 配特征点作为极坐标的原点。分别对P和Q进行 式中T,为设定的极坐标方向差阈值。 极坐标变换，并根据极角递增的方向进行排序，获得 记录满足条件的精匹配特征点对数目n,并利 新的特征点集，表示为 用式(11)计算相似度sm: (11) U=(ri,ei,di,n),,(ri,en,du,nu) sim=(n.×n,)/(M×N) (7) 由于粗匹配点的数目有很多，为了兼顾运行时 W={(,ei,d,ni),…,(r0,e,dw,n)} 间和匹配效率，从中选取欧氏距离最小的3对粗匹 式中(r,e,d,n)和(r,e,d,n)分别记录了点 配点作为极坐标变换的原点，重复进行精匹配，并不 集U和W中第i个特征点的4种信息：和为极 断更新数值最大的sm。 径，e和e为极角，dB和d?表示特征点的类型（端 设定T为匹配相似度阈值，构建匹配适应度 点、分叉点)，和n为特征点的方向差。 函数f(△x,△y,△9)： 为了消除局部形变的影响，在此引入可变界限 fn,fm≤T 盒。界限盒限定了匹配，点之间角度和距离误差的容 fa(4x,4y,A0)= (12) 许范围，而可变界限盒更具弹性。如图1所示，可变 界限盒的形状大小根据特征点的极径和极角动态可 2算法实现步骤 变，当匹配点距离原点越近，则界限盒的角度越大， 1)将蜂群的总体数量设为40，其中引领蜂和观 半径越小：反之，当匹配点距离原点越远，则界限盒 察蜂的数量各占20：将最大的循环次数定为20，局 的角度越小，半径越大。 部极值的循环次数设为3，搜索维数设为3：全局最 优几何变换参数(4x,△y,△0)，其范围分别为 极径 [-300,300]、[-300,300]以及[-T,π]。 2)初始化引领蜂对应的食物源位置，即设置 (△x,△y,△9)的初始值。利用该参数以及式(3)，将 采集的指纹特征点集几何变换成新的指纹特征点 极角 集，并和模板指纹特征点集进行匹配。依据式(12) 图1可变界限盒 所示的适应度函数f,(△x,△y,△0)评价2组指纹特 Fig.1 Variable boundary box 征点集的匹配相似度，作为当前食物源的收益度。 可以利用式(8)和式(9)获得可变的极径阈值 3)在每个引领蜂的邻域部分随机搜索一个新 T,和极角阈值T: 的食物源，并按照步骤2)的方式得到一个新的收益 度：同时与之前的收益度进行比较，选择较优的食物 源位置。 T.= Tsml≤r≤rirg (8) 4)观察蜂根据食物源的优劣，在一个引领蜂的 邻域部分随机搜索一个新的食物源。利用步骤2) esmall e<esmall 的方式，得到一个新的收益度，同时与之前的收益度 T.={E/r, eml≤e≤elarge (9) 进行比较，选择较优的食物源位置，并将引领蜂移动 elarge 到该处。 式中：r为匹配特征点的极径，「ml、ra和ema、eag 5)如果在经过3次循环后，某些引领蜂所对应 分别是极径阈值和极角阈值的最大值和最小值。V 的食物源的收益度仍没有发生改善，则将混沌序列 和ε是预先设定的常数。 代替侦查峰进行食物源位置的重置搜索，以跳出局 如果两个指纹特征点满足一定的匹配准则，则 部极值。 可以确定该特征点对满足匹配要求，匹配准则为 6)在一次循环结束后，记录本次循环的最优
ｘｃ，ｙｃ，ｄｃ，θｃ ( ) 为极坐标原点， (ｒ，ｅ，ｄ，η) 则为转换后 特征点在极坐标系下的极径、极角、特征点类型以及 特征点方向差。 相较于其他指纹匹配算法，本文算法无需预先 计算出指纹中心点作为极坐标原点，而是挑选粗匹 配特征点作为极坐标的原点。 分别对 Ｐ 和 Ｑ 进行 极坐标变换，并根据极角递增的方向进行排序，获得 新的特征点集，表示为 Ｕ ＝ ｒ ｕ １ ，ｅ ｕ １ ，ｄ ｕ １ ，η ｕ １ ( ) ，…， ｒ ｕ Ｍ ，ｅ ｕ Ｍ ，ｄ ｕ Ｍ ，η ｕ Ｍ { ( ) } Ｗ ＝ ｒ ｗ １ ，ｅ ｗ １ ，ｄ ｗ １ ，η ｗ １ ( ) ，…， ｒ ｗ Ｎ，ｅ ｗ Ｎ，ｄ ｗ Ｎ，η ｗ Ｎ { ( ) } （７） 式中： ｒ ｕ ｉ ，ｅ ｕ ｉ ，ｄ ｕ ｉ ，η ｕ ｉ ( ) 和 ｒ ｗ ｉ ，ｅ ｗ ｉ ，ｄ ｗ ｉ ，η ｗ ｉ ( ) 分别记录了点 集 Ｕ 和 Ｗ 中第 ｉ 个特征点的 ４ 种信息：ｒ ｕ ｉ 和 ｒ ｗ ｉ 为极 径，ｅ ｕ ｉ 和 ｅ ｗ ｉ 为极角，ｄ ｐ ｉ 和 ｄ ｑ ｉ 表示特征点的类型（端 点、分叉点），η ｕ ｉ 和 η ｗ ｉ 为特征点的方向差。 为了消除局部形变的影响，在此引入可变界限 盒。 界限盒限定了匹配点之间角度和距离误差的容 许范围，而可变界限盒更具弹性。 如图 １ 所示，可变 界限盒的形状大小根据特征点的极径和极角动态可 变，当匹配点距离原点越近，则界限盒的角度越大， 半径越小；反之，当匹配点距离原点越远，则界限盒 的角度越小，半径越大。 图 １ 可变界限盒 Ｆｉｇ．１ Ｖａｒｉａｂｌｅ ｂｏｕｎｄａｒｙ ｂｏｘ 可以利用式（８）和式（９）获得可变的极径阈值 Ｔｒ 和极角阈值 Ｔｅ： Ｔｒ ＝ ｒｓｍａｌｌ， ｒ ＜ ｒｓｍａｌｌ ｒ／ υ， ｒｓｍａｌｌ ≤ ｒ ≤ ｒｌａｒｇｅ ｒｌａｒｇｅ， ｒｌａｒｇｅ ＜ ｒ ì î í ï ï ï ï （８） Ｔｅ ＝ ｅｓｍａｌｌ， ｅ ＜ ｅｓｍａｌｌ ε ／ ｒ， ｅｓｍａｌｌ ≤ ｅ ≤ ｅｌａｒｇｅ ｅｌａｒｇｅ， ｅｌａｒｇｅ ＜ ｅ ì î í ï ï ï ï （９） 式中：ｒ 为匹配特征点的极径，ｒｓｍａｌｌ、ｒｌａｒｇｅ和 ｅｓｍａｌｌ、ｅｌａｒｇｅ 分别是极径阈值和极角阈值的最大值和最小值。 υ 和 ε 是预先设定的常数。 如果两个指纹特征点满足一定的匹配准则，则 可以确定该特征点对满足匹配要求，匹配准则为 ｒ ｕ ｉ － ｒ ｗ ｊ ≤ Ｔｒ ｅ ｕ ｉ － ｅ ｗ ｊ ≤ Ｔｅ ｄ ｕ ｉ － ｄ ｗ ｊ ＝ ０ η ｕ ｉ － η ｗ ｊ ≤ Ｔη ì î í ï ï ï ï ï ï （１０） 式中 Ｔη 为设定的极坐标方向差阈值。 记录满足条件的精匹配特征点对数目 ｎｓ，并利 用式（１１）计算相似度 ｓｓｉｍ ： ｓｓｉｍ ＝ （ｎｓ × ｎｓ） ／ （Ｍ × Ｎ） （１１） 由于粗匹配点的数目有很多，为了兼顾运行时 间和匹配效率，从中选取欧氏距离最小的 ３ 对粗匹 配点作为极坐标变换的原点，重复进行精匹配，并不 断更新数值最大的 ｓｓｉｍ 。 设定 Ｔｓｉｍ为匹配相似度阈值，构建匹配适应度 函数 ｆ ｆｉｔ (Δｘ，Δｙ，Δθ) ： ｆ ｆｉｔ (Δｘ，Δｙ，Δθ) ＝ ｆ ｓｉｍ ， ｆ ｓｉｍ ≤ Ｔｓｉｍ ｓｓｉｍ ， ｆ ｓｉｍ ＞ Ｔｓｉｍ { （１２） ２ 算法实现步骤 １）将蜂群的总体数量设为 ４０，其中引领蜂和观 察蜂的数量各占 ２０；将最大的循环次数定为 ２０，局 部极值的循环次数设为 ３，搜索维数设为 ３；全局最 优几 何 变 换 参 数 (Δｘ，Δｙ，Δθ) ， 其 范 围 分 别 为 ［－３００，３００］、［－３００，３００］以及［－π，π］。 ２）初始化引领蜂对应的食物源位置，即设置 (Δｘ，Δｙ，Δθ) 的初始值。 利用该参数以及式（３），将 采集的指纹特征点集几何变换成新的指纹特征点 集，并和模板指纹特征点集进行匹配。 依据式（１２） 所示的适应度函数 ｆ ｆｉｔ (Δｘ，Δｙ，Δθ) 评价 ２ 组指纹特 征点集的匹配相似度，作为当前食物源的收益度。 ３）在每个引领蜂的邻域部分随机搜索一个新 的食物源，并按照步骤 ２）的方式得到一个新的收益 度；同时与之前的收益度进行比较，选择较优的食物 源位置。 ４）观察蜂根据食物源的优劣，在一个引领蜂的 邻域部分随机搜索一个新的食物源。 利用步骤 ２） 的方式，得到一个新的收益度，同时与之前的收益度 进行比较，选择较优的食物源位置，并将引领蜂移动 到该处。 ５）如果在经过 ３ 次循环后，某些引领蜂所对应 的食物源的收益度仍没有发生改善，则将混沌序列 代替侦查峰进行食物源位置的重置搜索，以跳出局 部极值。 ６）在一次循环结束后，记录本次循环的最优 ·６１６· 智 能 系 统 学 报 第 １１ 卷
第5期 史骏鹏，等：基于混沌蜂群优化的指纹匹配算法 ·617· 解，并且循环次数加1。 表1指纹细节特征匹配的FRR值、FAR值及匹配时间 7)若循环次数达到最大值20后，停止迭代，选 Table 1 FRR,FAR and matching time of fingerprint mi. 择当前最优解作为几何变换参数，并获得最后的匹 nutiae matching 配相似度；否则，转到步骤3继续进行搜索。 匹配算法指纹图库fRm/% fE/%匹配时间/ms DB. 3实验结果与分析 5.66 1.35 63 DB2 5.17 1.48 68 为了验证基于混沌蜂群优化和可变界限盒的分 文献[10]算法 DB: 5.85 1.67 66 层指纹匹配算法的有效性，利用VC2002提供的指 DB. 5.74 1.58 纹库DB,、DB,、DB,和DB,中的指纹进行了测试。 64 DB. 3.98 0.28 每个指纹库中由100个手指指纹组成，每个指纹采 85 集8次，共800幅指纹图像，均为未压缩的灰度图 DB, 3.05 0.66 89 文献[14]算法 像。将拒识率(false rejection rate,FRR)、误识率 DB: 5.25 0.89 86 (false accept rate,FAR)和平均运行时间作为指纹 DB. 4.97 1.20 84 匹配算法精度和速度的客观评价指标。拒识率是将 DB, 3.50 0.04 52 同一手指的指纹误认为非同一手指的指纹而加以拒 DB, 2.61 0.23 哈 绝的出错概率，每个指纹库中的总匹配次数为 本文算法 DB: 4.56 0.50 53 (8×7)/2)×100=2800:误识率则是指将非同一手指 DB 3.92 0.42 52 的指纹误认为是同一手指的指纹而加以接受的出错概 率，每个指纹库中的总匹配次数为(100×99)/2=4950。 4 结束语 计算公式分别如式(13)和式(14)： 本文利用混沌蜂群算法优化指纹细节特征匹 错误拒绝次数 配，将混沌引入蜂群优化算法中，使人工蜂群优化算 ×100% (13) 总匹配次数 法收敛快、避免局部最优、控制参数少等优，点和混沌 错误接受次数 FFAR= ×100% (14) 策略的类随机性、高遍历性的特点有机结合起来，用 总匹配次数 于几何变换参数的搜索：并依据分层匹配的思想设 为了进行比较和分析，同时给出了基于局部特 计匹配适应度函数，引入可变界限盒柔性匹配，克服 征的指纹匹配算法、基于遗传优化的指纹匹配算法 了指纹图像非线性形变的影响。此外，本文算法无 需预先找出指纹中心点位置，而是用匹配相似度最 以及本文算法的fR值fAR值及匹配时间，列于表 1。所有算法的运行环境为Intel(R)Core(TM)2 高的3对匹配点对作为精匹配的极坐标原点，迭代 Duo CPU2.5GHz/4GB内存、MATLAB2013。 得出最高的匹配相似度，因此只需较少的特征点就 从表1的实验结果可以看出，本文基于混沌蜂 能进行较为准确的匹配，降低了指纹特征提取的难 群优化和可变界限盒的分层指纹匹配算法匹配精度 度，易于实现。实验结果表明，本文算法不仅运算速 高、运行速度快，足以满足实时性的要求。与文献 度快，满足实时处理的要求，而且匹配精度更高，能 [10]算法相比，本文算法利用群体智能算法进行几 更好地用于个人身份的识别。 何变换参数的搜索，避免了大量无意义的重复性匹 参考文献： 配，挑选出较为优秀的特征点对参与匹配，并且采用 相似度最高的3组粗匹配点对作为精匹配极坐标的 [1]ITO K,NAKAJIMA H,KOBAYASHI K,et al.A finger- 原点，匹配精度更高：与文献[14]算法相比，本文的 print matching algorithm using phase-only correlation J]. IEICE transactions on fundamentals of electronics,commu- 混沌蜂群优化算法避免了遗传算法的选择、交叉和 nications and computer sciences,2004,E87-A(3):682- 变异等复杂操作，运算速度提高了约20%：同时，采 691. 用分层匹配的方式，除了进一步提高匹配的精度外， [2]HE Yuliang,TIAN Jie,LI Liang,et al.Fingerprint matc- 还利用了可变界限盒的自适应性，有效地避免了外 hing based on global comprehensive similarity[J].IEEE 界的非线性形变对匹配特征点的影响。 transactions on pattern analysis and machine intelligence, 2006,28(6):850-862
解，并且循环次数加 １。 ７）若循环次数达到最大值 ２０ 后，停止迭代，选 择当前最优解作为几何变换参数，并获得最后的匹 配相似度；否则，转到步骤 ３ 继续进行搜索。 ３ 实验结果与分析 为了验证基于混沌蜂群优化和可变界限盒的分 层指纹匹配算法的有效性，利用 ＦＶＣ２００２ 提供的指 纹库 ＤＢ１ 、ＤＢ２ 、ＤＢ３ 和 ＤＢ４ 中的指纹进行了测试。 每个指纹库中由 １００ 个手指指纹组成，每个指纹采 集 ８ 次，共 ８００ 幅指纹图像，均为未压缩的灰度图 像。 将拒识率（ ｆａｌｓｅ ｒｅｊｅｃｔｉｏｎ ｒａｔｅ， ＦＲＲ）、误识率 （ｆａｌｓｅ ａｃｃｅｐｔ ｒａｔｅ， ＦＡＲ）和平均运行时间作为指纹 匹配算法精度和速度的客观评价指标。 拒识率是将 同一手指的指纹误认为非同一手指的指纹而加以拒 绝的出 错 概 率， 每 个 指 纹 库 中 的 总 匹 配 次 数 为 ( (８×７) ／ ２) ×１００＝ ２ ８００；误识率则是指将非同一手指 的指纹误认为是同一手指的指纹而加以接受的出错概 率，每个指纹库中的总匹配次数为(１００×９９) ／ ２＝ ４ ９５０。 计算公式分别如式（１３）和式（１４）： ｆＦＲＲ ＝ 错误拒绝次数 总匹配次数 × １００％ （１３） ｆＦＡＲ ＝ 错误接受次数 总匹配次数 × １００％ （１４） 为了进行比较和分析，同时给出了基于局部特 征的指纹匹配算法、基于遗传优化的指纹匹配算法 以及本文算法的 ｆＦＲＲ值、ｆＦＡＲ值及匹配时间，列于表 １。 所有算法的运行环境为 Ｉｎｔｅｌ（Ｒ） Ｃｏｒｅ（ ＴＭ） ２ Ｄｕｏ ＣＰＵ ２．５ＧＨｚ／ ４ＧＢ 内存、ＭＡＴＬＡＢ２０１３。 从表 １ 的实验结果可以看出，本文基于混沌蜂 群优化和可变界限盒的分层指纹匹配算法匹配精度 高、运行速度快，足以满足实时性的要求。 与文献 ［１０］算法相比，本文算法利用群体智能算法进行几 何变换参数的搜索，避免了大量无意义的重复性匹 配，挑选出较为优秀的特征点对参与匹配，并且采用 相似度最高的 ３ 组粗匹配点对作为精匹配极坐标的 原点，匹配精度更高；与文献［１４］算法相比，本文的 混沌蜂群优化算法避免了遗传算法的选择、交叉和 变异等复杂操作，运算速度提高了约 ２０％；同时，采 用分层匹配的方式，除了进一步提高匹配的精度外， 还利用了可变界限盒的自适应性，有效地避免了外 界的非线性形变对匹配特征点的影响。 表 １ 指纹细节特征匹配的 ＦＲＲ 值、ＦＡＲ 值及匹配时间 Ｔａｂｌｅ １ ＦＲＲ、ＦＡＲ ａｎｄ ｍａｔｃｈｉｎｇ ｔｉｍｅ ｏｆ ｆｉｎｇｅｒｐｒｉｎｔ ｍｉ⁃ ｎｕｔｉａｅ ｍａｔｃｈｉｎｇ 匹配算法 指纹图库 ｆＦＲＲ ／ ％ ｆＦＡＲ ／ ％ 匹配时间／ ｍｓ 文献［１０］算法 ＤＢ１ ５．６６ １．３５ ６３ ＤＢ２ ５．１７ １．４８ ６８ ＤＢ３ ５．８５ １．６７ ６６ ＤＢ４ ５．７４ １．５８ ６４ 文献［１４］算法 ＤＢ１ ３．９８ ０．２８ ８５ ＤＢ２ ３．０５ ０．６６ ８９ ＤＢ３ ５．２５ ０．８９ ８６ ＤＢ４ ４．９７ １．２０ ８４ 本文算法 ＤＢ１ ３．５０ ０．０４ ５２ ＤＢ２ ２．６１ ０．２３ ５６ ＤＢ３ ４．５６ ０．５０ ５３ ＤＢ４ ３．９２ ０．４２ ５２ ４ 结束语 本文利用混沌蜂群算法优化指纹细节特征匹 配，将混沌引入蜂群优化算法中，使人工蜂群优化算 法收敛快、避免局部最优、控制参数少等优点和混沌 策略的类随机性、高遍历性的特点有机结合起来，用 于几何变换参数的搜索；并依据分层匹配的思想设 计匹配适应度函数，引入可变界限盒柔性匹配，克服 了指纹图像非线性形变的影响。 此外，本文算法无 需预先找出指纹中心点位置，而是用匹配相似度最 高的 ３ 对匹配点对作为精匹配的极坐标原点，迭代 得出最高的匹配相似度，因此只需较少的特征点就 能进行较为准确的匹配，降低了指纹特征提取的难 度，易于实现。 实验结果表明，本文算法不仅运算速 度快，满足实时处理的要求，而且匹配精度更高，能 更好地用于个人身份的识别。 参考文献： ［１］ＩＴＯ Ｋ， ＮＡＫＡＪＩＭＡ Ｈ， ＫＯＢＡＹＡＳＨＩ Ｋ， ｅｔ ａｌ． Ａ ｆｉｎｇｅｒ⁃ ｐｒｉｎｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｐｈａｓｅ⁃ｏｎｌｙ ｃｏｒｒｅｌａｔｉｏｎ ［ Ｊ］． ＩＥＩＣＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｆｕｎｄａｍｅｎｔａｌｓ ｏｆ ｅｌｅｃｔｒｏｎｉｃｓ， ｃｏｍｍｕ⁃ ｎｉｃａｔｉｏｎｓ ａｎｄ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅｓ， ２００４， Ｅ８７⁃Ａ（ ３）： ６８２⁃ ６９１． ［２］ＨＥ Ｙｕｌｉａｎｇ， ＴＩＡＮ Ｊｉｅ， ＬＩ Ｌｉａｎｇ， ｅｔ ａｌ． Ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃ⁃ ｈｉｎｇ ｂａｓｅｄ ｏｎ ｇｌｏｂａｌ ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｓｉｍｉｌａｒｉｔｙ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００６， ２８（６）： ８５０⁃８６２． 第 ５ 期 史骏鹏，等：基于混沌蜂群优化的指纹匹配算法 ·６１７·
·618 智能系统学报 第11卷 [3]LUMINI A,NANNI L.Two-class fingerprint matcher [J] based fingerprint matching algorithm and its application in Patter recognition,2006,39(4):714-716. automated fingerprint recognition system[J].Journal of [4]JIANG Xudong,YAU W Y.Fingerprint minutiae matching software,2000,11(4):488-493 based on the local and global structures[C]//Proceedings [14]SHENG W,HOWELLS G.FAIRHUST M C.et al.Con- of the 15th International Conference on Pattern Recognition. sensus fingerprint matching with genetically optimised ap- Barcelona,Spain,2000,2:1038-1041. proach[J].Pattern recognition,2009,42(7):1399- [5]于明，皮海龙，王岩，等.基于k近邻法和脊线追踪的指 1407. 纹匹配算法[].吉林大学学报：工学版，2014,44(6)： [15]GHAZVINI M,SUFIKARIMI H,MOHAMMADI K.Fin- 1806-1810. gerprint matching using genetic algorithm and triangle de- YU Ming,PI Hailong,WANG Yan,et al.Fingerprint scriptors[C]//Proceedings of the 19th Iranian Conference matching algorithm based on k-nearest neighbor and ridge on Electrical Engineering.Tehran,Iran,2011:1-6. line tracking methods[J].Journal of Jilin university:engi- [l6]吴一全，张金矿.基于Tent映射混沌粒子群的快速指 neering and technology edition,2014,44(6):1806-1810. 纹特征匹配[J].信号处理，2011,27(2)：168-173. [6]曹国，孙权森，毛志红，等.一种新的形变指纹匹配方 WU Yiquan,ZHANG Jinkuang.Fast fingerprint minutiae 法[J].中国图象图形学报，2010,15(4)：645-649. matching based on Tent map chaotic particle swarm optimi- CAO Guo,SUN Quansen,MAO Zhihong,et al.A new al- zation[]Sigal processing,2011,27(2):168-173. gorithm for distorted fingerprint matching[J].Journal of im- [17]KARABOGA D,BASTURK B.On the performance of arti- age and graphics,2010,15(4):645-649. ficial bee colony (ABC)algorithm[J].Applied soft com- [7]袁东锋，杜恒，秦小铁.基于三角形局部特征点模型指 puting,2008,8(1):687-697. 纹匹配算法[J].重庆师范大学学报：自然科学版， [18]KARABOGA D,OZTURK C.A novel clustering approach: 2013,30(2):69-73. Artificial bee colony (ABC)algorithm[J].Applied soft YUAN Dongfeng,DU Heng,QIN Xiaotie.Fingerprint mate- computing,2011,11(1):652-657. hing algorithm based on local triangular feature point model [19]秦全德，程适，李丽，等.人工蜂群算法研究综述[J] [J].Journal of Chongqing normal university:nature sci- 智能系统学报，2014,9(2)：127-135. ence,2013,30(2):69.73. QIN Quande,CHENG Shi,LI Li,et al.Artificial bee col- [8]ZHANG Qing,YIN Yilong,YANG Gongping.Unmatched ony algorithm:a survey[J].CAAI transactions on intelli- minutiae:useful information to boost fingerprint recognition gent systems,2014,9(2):127-135. [J].Neurocomputing,2016,171:1401-1413. [20]吴一全，王凯，曹鹏祥.蜂群优化的二维非对称Tsallis [9]CAO Kai,YANG Xin,CHEN Xinjian,et al.Minutia hand- 交叉嫡图像阈值选取[J].智能系统学报，2015,10 edness:a novel global feature for minutiae-based fingerprint (1):103-112. matching[J].Pattern recognition letters,2012,33(10): WU Yiquan,WANG Kai,CAO Pengxiang.Two-dimen- 1411-1421. sional asymmetric tsallis cross entropy image threshold se- [10]朱宁，施荣华，吴科桦.一种新的点模式指纹匹配方法 lection using bee colony optimization[J].CAAI transac- [J].计算机工程与应用，2006,42(5)：74-76 tions on intelligent systems,2015,10(1):103-112 ZHU Ning,SHI Ronghua,WU Kehua.A new fingerprint 作者简介： matching method of minutiae[J].Computer engineering 史骏鹏，男，1990年生，硕士研究 and applications,2006,42(5):74-76. 生，主要研究方向为图像处理与视频通 [11]魏鸿磊，张文孝，华顺刚.一种采用脊线特征的指纹模 信。发表学术论文3篇。 糊匹配方法[J刀.智能系统学报，2012,7(3)：235-240. WEI Honglei,ZHANG Wenxiao,HUA Shungang.A fuzzy fin- gerprint matching method based on ridge features[].CAAI transactions on intelligent systems,2012,7(3):235-240. [12]LIU Feng,ZHANG D.3D fingerprint reconstruction system 吴一全，男，1963年生.博士，教授 using feature correspondences and prior estimated finger 博士生导师，主要研究方向为图像处理 model[J].Pattern recognition,2014,47(1):178-193. 与分析、目标检测与识别、智能信息处 「13]漆远.田捷，邓翔.基于遗传算法的指纹图匹配算法及 理。发表学术论文250余篇。 应用J].软件学报，2000,11(4)：488-493. QI Yuan,TIAN Jie,DENG Xiang.Genetic algorithm
［３］ ＬＵＭＩＮＩ Ａ， ＮＡＮＮＩ Ｌ． Ｔｗｏ⁃ｃｌａｓｓ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｅｒ［ Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２００６， ３９（４）： ７１４⁃７１６． ［４］ＪＩＡＮＧ Ｘｕｄｏｎｇ， ＹＡＵ Ｗ Ｙ． Ｆｉｎｇｅｒｐｒｉｎｔ ｍｉｎｕｔｉａｅ ｍａｔｃｈｉｎｇ ｂａｓｅｄ ｏｎ ｔｈｅ ｌｏｃａｌ ａｎｄ ｇｌｏｂａｌ ｓｔｒｕｃｔｕｒｅｓ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｂａｒｃｅｌｏｎａ， Ｓｐａｉｎ， ２０００， ２： １０３８⁃１０４１． ［５］于明， 皮海龙， 王岩， 等． 基于 ｋ 近邻法和脊线追踪的指 纹匹配算法［Ｊ］． 吉林大学学报： 工学版， ２０１４， ４４（６）： １８０６⁃１８１０． ＹＵ Ｍｉｎｇ， ＰＩ Ｈａｉｌｏｎｇ， ＷＡＮＧ Ｙａｎ， ｅｔ ａｌ． Ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｋ⁃ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ａｎｄ ｒｉｄｇｅ ｌｉｎｅ ｔｒａｃｋｉｎｇ ｍｅｔｈｏｄｓ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｊｉｌｉｎ ｕｎｉｖｅｒｓｉｔｙ： ｅｎｇｉ⁃ ｎｅｅｒｉｎｇ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ ｅｄｉｔｉｏｎ， ２０１４， ４４（６）： １８０６⁃１８１０． ［６］曹国， 孙权森， 毛志红， 等． 一种新的形变指纹匹配方 法［Ｊ］． 中国图象图形学报， ２０１０， １５（４）： ６４５⁃６４９． ＣＡＯ Ｇｕｏ， ＳＵＮ Ｑｕａｎｓｅｎ， ＭＡＯ Ｚｈｉｈｏｎｇ， ｅｔ ａｌ． Ａ ｎｅｗ ａｌ⁃ ｇｏｒｉｔｈｍ ｆｏｒ ｄｉｓｔｏｒｔｅｄ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｉｍ⁃ ａｇｅ ａｎｄ ｇｒａｐｈｉｃｓ， ２０１０， １５（４）： ６４５⁃６４９． ［７］袁东锋， 杜恒， 秦小铁． 基于三角形局部特征点模型指 纹匹配算法 ［ Ｊ］． 重庆师范大学学报： 自然科学版， ２０１３， ３０（２）： ６９⁃７３． ＹＵＡＮ Ｄｏｎｇｆｅｎｇ， ＤＵ Ｈｅｎｇ， ＱＩＮ Ｘｉａｏｔｉｅ． Ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃ⁃ ｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｌｏｃａｌ ｔｒｉａｎｇｕｌａｒ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｍｏｄｅｌ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｏｎｇｑｉｎｇ ｎｏｒｍａｌ ｕｎｉｖｅｒｓｉｔｙ： ｎａｔｕｒｅ ｓｃｉ⁃ ｅｎｃｅ， ２０１３， ３０（２）： ６９⁃７３． ［８］ ＺＨＡＮＧ Ｑｉｎｇ， ＹＩＮ Ｙｉｌｏｎｇ， ＹＡＮＧ Ｇｏｎｇｐｉｎｇ． Ｕｎｍａｔｃｈｅｄ ｍｉｎｕｔｉａｅ： ｕｓｅｆｕｌ ｉｎｆｏｒｍａｔｉｏｎ ｔｏ ｂｏｏｓｔ ｆｉｎｇｅｒｐｒｉｎｔ ｒｅｃｏｇｎｉｔｉｏｎ ［Ｊ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２０１６， １７１： １４０１⁃１４１３． ［９］ＣＡＯ Ｋａｉ， ＹＡＮＧ Ｘｉｎ， ＣＨＥＮ Ｘｉｎｊｉａｎ， ｅｔ ａｌ． Ｍｉｎｕｔｉａ ｈａｎｄ⁃ ｅｄｎｅｓｓ： ａ ｎｏｖｅｌ ｇｌｏｂａｌ ｆｅａｔｕｒｅ ｆｏｒ ｍｉｎｕｔｉａｅ⁃ｂａｓｅｄ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ［Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ ｌｅｔｔｅｒｓ， ２０１２， ３３ （ １０）： １４１１⁃１４２１． ［１０］朱宁， 施荣华， 吴科桦． 一种新的点模式指纹匹配方法 ［Ｊ］． 计算机工程与应用， ２００６， ４２（５）： ７４⁃７６． ＺＨＵ Ｎｉｎｇ， ＳＨＩ Ｒｏｎｇｈｕａ， ＷＵ Ｋｅｈｕａ． Ａ ｎｅｗ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ｍｅｔｈｏｄ ｏｆ ｍｉｎｕｔｉａｅ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２００６， ４２（５）： ７４⁃７６． ［１１］魏鸿磊， 张文孝， 华顺刚． 一种采用脊线特征的指纹模 糊匹配方法［Ｊ］． 智能系统学报， ２０１２， ７（３）： ２３５⁃２４０． ＷＥＩ Ｈｏｎｇｌｅｉ， ＺＨＡＮＧ Ｗｅｎｘｉａｏ， ＨＵＡ Ｓｈｕｎｇａｎｇ． Ａ ｆｕｚｚｙ ｆｉｎ⁃ ｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｒｉｄｇｅ ｆｅａｔｕｒｅｓ ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１２，７（３）：２３５⁃２４０． ［１２］ＬＩＵ Ｆｅｎｇ， ＺＨＡＮＧ Ｄ． ３Ｄ ｆｉｎｇｅｒｐｒｉｎｔ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｓｙｓｔｅｍ ｕｓｉｎｇ ｆｅａｔｕｒｅ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅｓ ａｎｄ ｐｒｉｏｒ ｅｓｔｉｍａｔｅｄ ｆｉｎｇｅｒ ｍｏｄｅｌ［Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１４， ４７（１）： １７８⁃１９３． ［１３］漆远， 田捷， 邓翔． 基于遗传算法的指纹图匹配算法及 应用［Ｊ］． 软件学报， ２０００， １１（４）： ４８８⁃４９３． ＱＩ Ｙｕａｎ， ＴＩＡＮ Ｊｉｅ， ＤＥＮＧ Ｘｉａｎｇ． Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ａｕｔｏｍａｔｅｄ ｆｉｎｇｅｒｐｒｉｎｔ ｒｅｃｏｇｎｉｔｉｏｎ ｓｙｓｔｅｍ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ， ２０００， １１（４）： ４８８⁃４９３． ［１４］ＳＨＥＮＧ Ｗ， ＨＯＷＥＬＬＳ Ｇ， ＦＡＩＲＨＵＳＴ Ｍ Ｃ， ｅｔ ａｌ． Ｃｏｎ⁃ ｓｅｎｓｕｓ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ｗｉｔｈ ｇｅｎｅｔｉｃａｌｌｙ ｏｐｔｉｍｉｓｅｄ ａｐ⁃ ｐｒｏａｃｈ［ Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２００９， ４２ （ ７ ）： １３９９⁃ １４０７． ［１５］ ＧＨＡＺＶＩＮＩ Ｍ， ＳＵＦＩＫＡＲＩＭＩ Ｈ， ＭＯＨＡＭＭＡＤＩ Ｋ． Ｆｉｎ⁃ ｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ｕｓｉｎｇ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｒｉａｎｇｌｅ ｄｅ⁃ ｓｃｒｉｐｔｏｒｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９ｔｈ Ｉｒａｎｉａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ． Ｔｅｈｒａｎ， Ｉｒａｎ， ２０１１： １⁃６． ［１６］吴一全， 张金矿． 基于 Ｔｅｎｔ 映射混沌粒子群的快速指 纹特征匹配［Ｊ］． 信号处理， ２０１１， ２７（２）： １６８⁃１７３． ＷＵ Ｙｉｑｕａｎ， ＺＨＡＮＧ Ｊｉｎｋｕａｎｇ． Ｆａｓｔ ｆｉｎｇｅｒｐｒｉｎｔ ｍｉｎｕｔｉａｅ ｍａｔｃｈｉｎｇ ｂａｓｅｄ ｏｎ Ｔｅｎｔ ｍａｐ ｃｈａｏｔｉｃ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉ⁃ ｚａｔｉｏｎ［Ｊ］． Ｓｉｇａｌ ｐｒｏｃｅｓｓｉｎｇ， ２０１１， ２７（２）： １６８⁃１７３． ［１７］ＫＡＲＡＢＯＧＡ Ｄ， ＢＡＳＴＵＲＫ Ｂ． Ｏｎ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ａｒｔｉ⁃ ｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ （ＡＢＣ） ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ａｐｐｌｉｅｄ ｓｏｆｔ ｃｏｍ⁃ ｐｕｔｉｎｇ， ２００８， ８（１）： ６８７⁃６９７． ［１８］ＫＡＲＡＢＯＧＡ Ｄ， ＯＺＴＵＲＫ Ｃ． Ａ ｎｏｖｅｌ ｃｌｕｓｔｅｒｉｎｇ ａｐｐｒｏａｃｈ： Ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ （ ＡＢＣ） ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ａｐｐｌｉｅｄ ｓｏｆｔ ｃｏｍｐｕｔｉｎｇ， ２０１１， １１（１）： ６５２⁃６５７． ［１９］秦全德， 程适， 李丽， 等． 人工蜂群算法研究综述［ Ｊ］． 智能系统学报， ２０１４， ９（２）： １２７⁃１３５． ＱＩＮ Ｑｕａｎｄｅ， ＣＨＥＮＧ Ｓｈｉ， ＬＩ Ｌｉ， ｅｔ ａｌ． Ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌ⁃ ｏｎｙ ａｌｇｏｒｉｔｈｍ： ａ ｓｕｒｖｅｙ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉ⁃ ｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１４， ９（２）： １２７⁃１３５． ［２０］吴一全， 王凯， 曹鹏祥． 蜂群优化的二维非对称 Ｔｓａｌｌｉｓ 交叉熵图像阈值选取［ Ｊ］． 智能系统学报， ２０１５， １０ （１）： １０３⁃１１２． ＷＵ Ｙｉｑｕａｎ， ＷＡＮＧ Ｋａｉ， ＣＡＯ Ｐｅｎｇｘｉａｎｇ． Ｔｗｏ⁃ｄｉｍｅｎ⁃ ｓｉｏｎａｌ ａｓｙｍｍｅｔｒｉｃ ｔｓａｌｌｉｓ ｃｒｏｓｓ ｅｎｔｒｏｐｙ ｉｍａｇｅ ｔｈｒｅｓｈｏｌｄ ｓｅ⁃ ｌｅｃｔｉｏｎ ｕｓｉｎｇ ｂｅｅ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１５， １０（１）： １０３⁃１１２． 作者简介： 史骏鹏，男，１９９０ 年生，硕士研究 生，主要研究方向为图像处理与视频通 信。 发表学术论文 ３ 篇。 吴一全，男，１９６３ 年生，博士，教授， 博士生导师，主要研究方向为图像处理 与分析、目标检测与识别、智能信息处 理。 发表学术论文 ２５０ 余篇。 ·６１８· 智 能 系 统 学 报 第 １１ 卷