第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.解，并且循环次数加 １。 ７）若循环次数达到最大值 ２０ 后，停止迭代，选 择当前最优解作为几何变换参数，并获得最后的匹 配相似度；否则，转到步骤 ３ 继续进行搜索。 ３ 实验结果与分析 为了验证基于混沌蜂群优化和可变界限盒的分 层指纹匹配算法的有效性，利用 ＦＶＣ２００２ 提供的指 纹库 ＤＢ１ 、ＤＢ２ 、ＤＢ３ 和 ＤＢ４ 中的指纹进行了测试。 每个指纹库中由 １００ 个手指指纹组成，每个指纹采 集 ８ 次，共 ８００ 幅指纹图像，均为未压缩的灰度图 像。 将拒识率（ ｆａｌｓｅ ｒｅｊｅｃｔｉｏｎ ｒａｔｅ， ＦＲＲ）、误识率 （ｆａｌｓｅ ａｃｃｅｐｔ ｒａｔｅ， ＦＡＲ）和平均运行时间作为指纹 匹配算法精度和速度的客观评价指标。 拒识率是将 同一手指的指纹误认为非同一手指的指纹而加以拒 绝的出 错 概 率， 每 个 指 纹 库 中 的 总 匹 配 次 数 为 ( (８×７) ／ ２) ×１００＝ ２ ８００；误识率则是指将非同一手指 的指纹误认为是同一手指的指纹而加以接受的出错概 率，每个指纹库中的总匹配次数为(１００×９９) ／ ２＝ ４ ９５０。 计算公式分别如式（１３）和式（１４）： ｆＦＲＲ ＝ 错误拒绝次数 总匹配次数 × １００％ （１３） ｆＦＡＲ ＝ 错误接受次数 总匹配次数 × １００％ （１４） 为了进行比较和分析，同时给出了基于局部特 征的指纹匹配算法、基于遗传优化的指纹匹配算法 以及本文算法的 ｆＦＲＲ值、ｆＦＡＲ值及匹配时间，列于表 １。 所有算法的运行环境为 Ｉｎｔｅｌ（Ｒ） Ｃｏｒｅ（ ＴＭ） ２ Ｄｕｏ ＣＰＵ ２．５ＧＨｚ／ ４ＧＢ 内存、ＭＡＴＬＡＢ２０１３。 从表 １ 的实验结果可以看出，本文基于混沌蜂 群优化和可变界限盒的分层指纹匹配算法匹配精度 高、运行速度快，足以满足实时性的要求。 与文献 ［１０］算法相比，本文算法利用群体智能算法进行几 何变换参数的搜索，避免了大量无意义的重复性匹 配，挑选出较为优秀的特征点对参与匹配，并且采用 相似度最高的 ３ 组粗匹配点对作为精匹配极坐标的 原点，匹配精度更高；与文献［１４］算法相比，本文的 混沌蜂群优化算法避免了遗传算法的选择、交叉和 变异等复杂操作，运算速度提高了约 ２０％；同时，采 用分层匹配的方式，除了进一步提高匹配的精度外， 还利用了可变界限盒的自适应性，有效地避免了外 界的非线性形变对匹配特征点的影响。 表 １ 指纹细节特征匹配的 ＦＲＲ 值、ＦＡＲ 值及匹配时间 Ｔａｂｌｅ １ ＦＲＲ、ＦＡＲ ａｎｄ ｍａｔｃｈｉｎｇ ｔｉｍｅ ｏｆ ｆｉｎｇｅｒｐｒｉｎｔ ｍｉ⁃ ｎｕｔｉａｅ ｍａｔｃｈｉｎｇ 匹配算法 指纹图库 ｆＦＲＲ ／ ％ ｆＦＡＲ ／ ％ 匹配时间／ ｍｓ 文献［１０］算法 ＤＢ１ ５．６６ １．３５ ６３ ＤＢ２ ５．１７ １．４８ ６８ ＤＢ３ ５．８５ １．６７ ６６ ＤＢ４ ５．７４ １．５８ ６４ 文献［１４］算法 ＤＢ１ ３．９８ ０．２８ ８５ ＤＢ２ ３．０５ ０．６６ ８９ ＤＢ３ ５．２５ ０．８９ ８６ ＤＢ４ ４．９７ １．２０ ８４ 本文算法 ＤＢ１ ３．５０ ０．０４ ５２ ＤＢ２ ２．６１ ０．２３ ５６ ＤＢ３ ４．５６ ０．５０ ５３ ＤＢ４ ３．９２ ０．４２ ５２ ４ 结束语 本文利用混沌蜂群算法优化指纹细节特征匹 配，将混沌引入蜂群优化算法中，使人工蜂群优化算 法收敛快、避免局部最优、控制参数少等优点和混沌 策略的类随机性、高遍历性的特点有机结合起来，用 于几何变换参数的搜索；并依据分层匹配的思想设 计匹配适应度函数，引入可变界限盒柔性匹配，克服 了指纹图像非线性形变的影响。 此外，本文算法无 需预先找出指纹中心点位置，而是用匹配相似度最 高的 ３ 对匹配点对作为精匹配的极坐标原点，迭代 得出最高的匹配相似度，因此只需较少的特征点就 能进行较为准确的匹配，降低了指纹特征提取的难 度，易于实现。 实验结果表明，本文算法不仅运算速 度快，满足实时处理的要求，而且匹配精度更高，能 更好地用于个人身份的识别。 参考文献： ［１］ＩＴＯ Ｋ， ＮＡＫＡＪＩＭＡ Ｈ， ＫＯＢＡＹＡＳＨＩ Ｋ， ｅｔ ａｌ． Ａ ｆｉｎｇｅｒ⁃ ｐｒｉｎｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｐｈａｓｅ⁃ｏｎｌｙ ｃｏｒｒｅｌａｔｉｏｎ ［ Ｊ］． ＩＥＩＣＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｆｕｎｄａｍｅｎｔａｌｓ ｏｆ ｅｌｅｃｔｒｏｎｉｃｓ， ｃｏｍｍｕ⁃ ｎｉｃａｔｉｏｎｓ ａｎｄ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅｓ， ２００４， Ｅ８７⁃Ａ（ ３）： ６８２⁃ ６９１． ［２］ＨＥ Ｙｕｌｉａｎｇ， ＴＩＡＮ Ｊｉｅ， ＬＩ Ｌｉａｎｇ， ｅｔ ａｌ． Ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃ⁃ ｈｉｎｇ ｂａｓｅｄ ｏｎ ｇｌｏｂａｌ ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｓｉｍｉｌａｒｉｔｙ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００６， ２８（６）： ８５０⁃８６２． 第 ５ 期 史骏鹏，等：基于混沌蜂群优化的指纹匹配算法 ·６１７·