第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)为待转换的匹配特征点，几何变换参数，使一组特征点经几何变换后与另一 组特征点尽可能多的对应，达成一定的阈值条件，即 可判断这两组指纹图像是匹配的。 特征点集的变换 包括平移、旋转和尺度变换，由于采集得到的指纹图 像大小基本一致，因此尺度变换往往可以忽略，只需 通过平移旋转矩阵 ＨＲＴ对特征点进行变换： ｘ ｔ ｉ ｙ ｔ ｉ ｄ ｔ ｉ θ ｔ ｉ １ é ë ê ê ê ê ê ê êê ù û ú ú ú ú ú ú úú ＝ ｃｏｓ（Δθ） － ｓｉｎ（Δθ） ０ ０ Δｘ ｓｉｎ（Δθ） ｃｏｓ（Δθ） ０ ０ Δｙ ０ ０ １ ０ ０ ０ ０ ０ １ Δθ ０ ０ ０ ０ １ é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú ｘ ｐ ｉ ｙ ｐ ｉ ｄ ｐ ｉ θ ｐ ｉ １ é ë ê ê ê ê ê ê êê ù û ú ú ú ú ú ú úú （２） 式中：Δｘ 和 Δｙ 分别为横坐标和纵坐标的平移因子， Δθ 为旋转因子。 通过这 ３ 个因子对 Ｐ 进行几何变 换， 获 得 特 征 点 集 Ｔ， 若 Ｔ 中 某 特 征 点 ｔ ｉ ＝ ｘ ｔ ｉ，ｙ ｔ ｉ，ｄ ｔ ｉ，θ ｔ ｉ ( ) 与 Ｑ 中某特征点 ｑｊ ＝ ｘ ｑ ｊ ，ｙ ｑ ｊ ，ｄ ｑ ｊ ，θ ｑ ｊ ( ) 近 似相等，则可认定这两个特征点为匹配特征点对。 １．２ 人工蜂群优化及混沌策略 人工蜂群优化算法由 ３ 个部分组成，即引领蜂、 观察蜂和侦查蜂（也称雇佣蜂、跟随蜂和侦查蜂）， 其具体过程为：１）每只引领蜂都对应一个确定的食 物源，并在其邻域随机搜索一个新的食物源，然后将 食物源的信息进行反馈，送到观察蜂处；２） 比较反 馈回的食物源收益度大小后，观察蜂会选取一个食 物源作为目标并在其附近重复进行搜索，不断寻找 更优的食物源；３） 当观察蜂在搜索某个食物源时， 若收益度基本不再发生变化，便放弃该食物源，转化 为侦查蜂重新开始搜索。 不断循环迭代这一过程直 到搜索到最佳的食物源位置。 需要注意的是，在迭 代过程中， 蜂群对于食物源位置的搜索需要遵循一 定的规则：引领蜂和食物源是一一对应的关系，其数 目必须和食物源数目保持一致；观察蜂的数目也需 要和引领蜂的数目一一对应。 为了更好地避免蜂群陷入局部极值，在蜂群优 化算法中引入具有类随机性和遍历性等特点的混沌 策略，对侦查蜂进行初始化，循环迭代跳出局部最优 解位置，最终遍历搜寻出全局最优解位置。 混沌序 列的公式为 βｋ＋１ ＝ ２βｋ， ０ ≤ βｋ ≤ ０．５ ２ １ － βｋ { ( ) ， ０．５ ＜ βｋ ≤ １ （３） 式中：βｋ 表示序列中的参数，βｋ＋１表示下一个序列的 参数。 １．３ 适应度函数 指纹特征点受到很多因素的制约，除了指纹图 像采集时的噪声干扰和非线性形变，指纹图像的去 噪、增强、细化等预处理也会对最终参与匹配的指纹 特征点造成影响。 即使是同一手指的两幅指纹图 像，也不一定能获得位置、方向及数目高度一致的两 组特征点集。 因此设计一个合适的匹配适应度函数 是很有必要的，它在诸多干扰下依旧能较为准确地 判断出指纹的匹配关系。 为了提升指纹匹配过程中的匹配速度和精度， 本文算法引入了分层匹配的思想，将匹配过程分为 粗匹配和精匹配 ２ 个部分。 粗匹配通过全局仿射变 换确定大致相符的匹配点对；精匹配则将匹配点对 变换到极坐标系下，并根据可变限界盒准则设计匹 配适应度函数，对其进行比较。 １）粗匹配。 假定变换因子分别为 Δｘ、Δｙ 和 Δθ， 利用式（２）的平移旋转变换矩阵将指纹特征点集 Ｐ 变换成特征点集 Ｔ；计算 Ｔ 和 Ｑ 中所有特征点的欧 氏距离和特征点类型差，并将结果放在集合 Ｊ 中： Ｊ ＝ ａｉｋ，δｉｋ ( ) ａｉｋ ＝ ｘ ｔ ｉ － ｘ ｑ ｋ ( ) ２ ＋ ｙ ｔ ｉ － ｙ ｑ ｋ ( ) ２ ； δｉｋ ＝ ｄ ｔ ｉ － ｄ ｑ { ｋ ，１ ≤ ｉ ≤ Ｍ，１ ≤ ｋ ≤ Ｎ （４） 式中：ａｉｋ为指纹特征点间的欧氏距离；δｉｋ为特征点类 型是否一致的判断指标。 若 δｉｋ为 ０，则两个特征点 类型一致；若不为 ０，则两个特征点类型不一致，肯 定不匹配。 对集合 Ｊ 中的值，根据 ａｉｋ从小到大的顺序进行 判断：若 ａｉｊ小于给定的阈值 Ｔａ ，并且相应的 δｉｊ为 ０， 则确定 ｐｉ ＝ ｘ ｐ ｉ ，ｙ ｐ ｉ ，ｄ ｐ ｉ ，θ ｐ ｉ ( ) 和 ｑｊ ＝ ｘ ｑ ｊ ，ｙ ｑ ｊ ，ｄ ｑ ｊ ，θ ｑ ｊ ( ) 为粗 匹配特征点对；否则，继续对下一个 ａｉｋ进行判断，直 到其满足条件，产生一对粗匹配特征点对；若 ａｉｋ均 大于阈值 Ｔａ ，则不存在 ｐｉ 的粗匹配特征点。 对 Ｔ 中 所有的特征点都进行粗匹配点对搜索，并记录粗匹 配特征点对的数目 ｎｆ，利用式（５）计算相似度 ｆ ｓｉｍ ｆ ｓｉｍ ＝ （ｎｆ × ｎｆ） ／ （Ｍ × Ｎ） （５） 如果 ｆ ｓｉｍ小于阈值 Ｔｓｉｍ ，那么就将其作为匹配适应度 ｆ ｆｉｔ (Δｘ，Δｙ，Δθ) ，无需进行精匹配。 否则，需要进行 精匹配。 ２）精匹配。 首先将特征点集 Ｐ 和 Ｑ 转换到极 坐标系下，转换公式为 ｒ ｅ ｄ η æ è ç ç ç ç ö ø ÷ ÷ ÷ ÷ ＝ （ｘｍ － ｘｃ） ２ ＋ （ｙｍ － ｙｃ） ２ ａｒｃｔａｎ２ ｙｍ － ｙｃ ｘｍ － ｘｃ æ è ç ö ø ÷ － θｃ ｄｍ θｍ － θｃ æ è ç ç ç ç ç ç ç ö ø ÷ ÷ ÷ ÷ ÷ ÷ ÷ （６） 式中： ｘｍ ，ｙｍ ，ｄｍ ，θｍ ( ) 为 待 转 换 的 匹 配 特 征 点， 第 ５ 期 史骏鹏，等：基于混沌蜂群优化的指纹匹配算法 ·６１５·