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

目前主流的指纹匹配算法可以分为整体匹配^[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。这两个点集分别表示为

式中：x_i^p,y_i^p,d_i^p,θ_i^p和x_i^q,y_i^q,d_i^q,θ_i^q分别记录了点集P和Q中第i个特征点的4种信息：x_i^p和x_i^q为特征点横坐标，y_i^p和y_i^q为特征点纵坐标，d_i^p和d_i^q表示特征点的类型(端点、分叉点)，θ_i^p和θ_i^q为特征点的方向。

1.1 指纹细节特征匹配

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

式中：Δx和Δy分别为横坐标和纵坐标的平移因子，Δθ为旋转因子。通过这3个因子对P进行几何变换，获得特征点集T，若T中某特征点t_i=x_i^t,y_i^t,d_i^t,θ_i^t与Q中某特征点q_j=x_j^q,y_j^q,d_j^q,θ_j^q近似相等，则可认定这两个特征点为匹配特征点对。

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

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

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

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

1.3 适应度函数

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

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

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

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

对集合J中的值，根据a_ik从小到大的顺序进行判断：若a_ij小于给定的阈值T_a，并且相应的δ_ij为0，则确定p_i=x_i^p,y_i^p,d_i^p,θ_i^p和q_j=x_j^q,y_j^q,d_j^q,θ_j^q为粗匹配特征点对；否则，继续对下一个a_ik进行判断，直到其满足条件，产生一对粗匹配特征点对；若a_ik均大于阈值T_a，则不存在p_i的粗匹配特征点。对T中所有的特征点都进行粗匹配点对搜索，并记录粗匹配特征点对的数目n_f，利用式(5)计算相似度f_sim

如果f_sim小于阈值T_sim，那么就将其作为匹配适应度f_fitΔx,Δy,Δθ，无需进行精匹配。否则，需要进行精匹配。

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

式中：x_m,y_m,d_m,θ_m为待转换的匹配特征点，x_c,y_c,d_c,θ_c为极坐标原点，r,e,d,η则为转换后特征点在极坐标系下的极径、极角、特征点类型以及特征点方向差。

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

式中：r_i^u,e_i^u,d_i^u,η_i^u和r_i^w,e_i^w,d_i^w,η_i^w分别记录了点集U和W中第i个特征点的4种信息：r_i^u和r_i^w为极径，e_i^u和e_i^w为极角，d_i^p和d_i^q表示特征点的类型(端点、分叉点)，η_i^u和η_i^w为特征点的方向差。

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

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

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

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

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

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

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

设定T_sim为匹配相似度阈值，构建匹配适应度函数f_fitΔx,Δy,Δθ：

2 算法实现步骤

1) 将蜂群的总体数量设为40，其中引领蜂和观察蜂的数量各占20；将最大的循环次数定为20，局部极值的循环次数设为3，搜索维数设为3；全局最优几何变换参数Δx,Δy,Δθ，其范围分别为[-300, 300]、[-300, 300]以及[-π,π]。

2) 初始化引领蜂对应的食物源位置，即设置Δx,Δy,Δθ的初始值。利用该参数以及式(3)，将采集的指纹特征点集几何变换成新的指纹特征点集，并和模板指纹特征点集进行匹配。依据式(12)所示的适应度函数f_fitΔx,Δy,Δθ评价2组指纹特征点集的匹配相似度，作为当前食物源的收益度。

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

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

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

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

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

3 实验结果与分析

为了验证基于混沌蜂群优化和可变界限盒的分层指纹匹配算法的有效性，利用FVC2002提供的指纹库DB₁、DB₂、DB₃和DB₄中的指纹进行了测试。每个指纹库中由100个手指指纹组成，每个指纹采集8次，共800幅指纹图像，均为未压缩的灰度图像。将拒识率(false rejection rate,FRR)、误识率(false accept rate,FAR)和平均运行时间作为指纹匹配算法精度和速度的客观评价指标。拒识率是将同一手指的指纹误认为非同一手指的指纹而加以拒绝的出错概率，每个指纹库中的总匹配次数为8×7/2×100=2 800；误识率则是指将非同一手指的指纹误认为是同一手指的指纹而加以接受的出错概率，每个指纹库中的总匹配次数为100×99/2=4 950。计算公式分别如式(13)和式(14)：

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

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

4 结束语

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