基于AFSA和小波变换的快速图像匹配算法研究

2020-10-10何志明闫文耀李显峰陈圣伟熊琴

机电信息 2020年27期

何志明闫文耀李显峰陈圣伟熊琴

摘要：提出了一种基于人工鱼群算法（简称AFSA）和小波变换的快速图像匹配算法，该算法不但能提高匹配速度，而且增强了匹配算法的抗噪性能和鲁棒性。

关键词：鱼群算法;小波变换;快速图像匹配

1 基本人工鱼群优化算法

人工鱼群算法（简称AFSA）是李晓磊在2002年提出的：假设搜索目标空间是一个D维空间，在搜索空间内有N条人工鱼，那么第i条鱼的状态向量就可表示为：xi=（xi1，xi2，xi3，…，xiD），其中i=1，2，…，N。我们可以将目标函数适应度表示成食物的浓度：y=f（x）。每条人工鱼的状态就是潜在的解，通过代入xi，计算出yi，然后再通过比较yi的大小来衡量xi的质量。本文讨论的最优化都是指最大，因为求解极大、极小问题可以相互转换。

人工鱼群优化算法主要模拟自然鱼群觅食的过程，其主要行为有觅食、群聚、追尾和选择四种。在算法开始时，首先初始化一组随机解作为人工鱼群的初始种群，然后人工鱼群将依据周围环境情况在觅食、群聚或是追尾行为中选择最优行为执行，并反复执行该过程，也就是迭代更新，直到找到最优解。所以说，人工鱼群具有一定自适应能力。人工鱼群的主要行为有以下几种：

（1）觅食行为。假设xi、yi分别是第i条人工鱼的当前状态和适应度值，然后该人工鱼将在其感知范围内随机搜索并选择适应度函数值大于yi的状态xv，随后向xv前进，得到一个较好的新状态xinext，若达到最大预设试探次数也无法发现理想xv，那么人工鱼就在视野感知范围内随机移动一步，从而得到新状态xinext。

（2）群聚行为。人工鱼的群聚行为是指人工鱼在游动过程中，尽量向鱼群中心移动，但又要控制与其他人工鱼的距离，从而避免过度拥挤。设第i条人工鱼视野感知范围内的人工鱼集合为Sj，且人工鱼数目记为Nf，若Sj为不为空，表明xi的视野感知内存在其他人工鱼，即Nf>1，若Nf/N（N为人工鱼群种群大小）小于给定阈值δ，说明中心位置不拥挤，向中心位置移动一步。

（3）追尾行为。设xi、yi分别是人工鱼的当前状态及适应度函数值，xmax、ymax分别是其感知范围内适应度函数值最大的人工鱼及适应度函数值。若ymax>yi，统计xmax周围的人工鱼数目Nf，如果满足ymax>yi和Nf·ymax<δ·yi（δ>1），则人工鱼执行追尾行为，否则继续觅食。

人工鱼群优化算法还需设立公告板，公告板一直维持也仅维持最优值。在算法结束时，公告板中数据就是我们搜索的全局最优解。

2 小波变换

分层搜索是一种极为有效且简单的减小搜索空间的方法，能较大程度地提高搜索效率。分层搜索的精髓就是由粗到细地搜索。

小波分解图像的大致过程就是把原图像按不同的顺序在水平和垂直方向进行低通滤波、高通滤波以及抽取，得到不同的分解图和细节图像。

分解过程如图1所示。

3 基于人工鱼群和小波变换的快速图像匹配算法

根据小波变换和人工鱼群算法原理，本文提出了一种抗噪性较好、匹配速度快且匹配率较高的快速图像匹配算法，简称WAFSA。

3.1 算法设计

小波分解层数越多，图像越小，匹配时间也将迅速递减，但图像的信息也会减少，所以匹配概率也会随之降低。但在分层数小于5时，图像匹配概率基本能保持97%以上。因此，若图像较大，那么我们可以将其多分解几层，若图像本身就较小，那么就应该减少分解层数，因为匹配速度主要由运行计算量决定。本图像分层采用三层小波分解以平衡匹配速度和精度之间的矛盾。

在该匹配算法中，图像的像素坐标（i，j）可表示为一个二维向量xij，然后我們用该二维向量表示一条人工鱼。搜索空间是原图像进行三层小波分解后的第三层低频图像，并将新搜索图像分成L个小区域，每个区域内随机产生Number/L条人工鱼，Number是人工鱼群的初始种群大小。

3.2 算法实现

基于人工鱼群和小波变换的快速图像匹配算法基本步骤如下：

（1）将搜索图像、模板图像分别进行三层小波分解，然后将第三层分解层的低频图像作为新的搜索图像及模板图像。

（2）利用改进后的鱼群算法搜索新模板图像在新搜索图像中的最大匹配点（i，j）。

（3）根据相邻尺度下像素点间的位置关系找出第L层的像素点系数（i，j）在第L-1层的对应像素点系数（2×i，2×j），并找出所有与点（2×i，2×j）距离为3的像素点构成点（i，j）在L-1层的候选点集。也可根据需要扩大半径，增加候选点集，提高匹配精度。

（4）在L-l层上的候选点集范围内进行匹配，找出最大匹配点。

（5）重复（3）（4）步骤直到找到第1层上的最大匹配点，即为最佳匹配点。

3.3 实验结果与分析

本实验环境为Pentium Ⅳ 2.4 GHz PC，MATLAB7.0。为减小实验中随机性带来的影响，所有实验次数均为100次。实验结果中，若匹配点与理想匹配点的误差在1个像素内，则认为正确匹配;运行时间则是100次实验的平均时间。

3.3.1 算法的准确性与快速性测试

本实验搜索图像为512×512的lena图像，模板图像则是在该图中以（200，200）为左上角截取的大小为200×200的子图，因此，理想匹配位置就是点（200，200）。本实验中，小波分解层数为3层，鱼群种群初始大小为10，最大循环次数Try_number为8，迭代次数T为50，测试WAFSA的准确性与快速性。

下面同时给出传统的序贯相似性检测算法（SSDA）实验结果进行比较，以衡量新算法的性能。实验结果如图2所示，测试数据如表1所示。

图2（c）中框选部分即为模板图像在搜索图像中的准确位置，该图表明本匹配算法得到的匹配图中，模板图像和搜索图像嵌接较为自然且光滑，纹理也衔接自然、完整。而从表1中我们可以发现：两个算法的匹配正确率都是100%，但WAFSA的匹配时间仅为SSDA算法的4.6%，因此，WAFSA具有較好的快速性。

3.3.2 噪声环境下算法的鲁棒性及快速性测试

现在测试WAFSA的鲁棒性，分别将强度为0.2的椒盐噪声，强度0.2的斑点噪声加入到搜索图像中，然后再进行实验。实验结果如图3所示，测试数据如表2所示。

4 结语

本文首先介绍了基本人工鱼群算法及其主要过程，然后介绍了小波分解的基本思想，再根据小波多分辨率提出了一种新的快速图像匹配算法——基于人工鱼群优化算法和多分辨率小波变换的快速图像匹配算法并进行了进行实验，最后对结果进行了对比分析。

[参考文献]

[1] 李晓磊，路飞，田国会，等.组合优化问题的人工鱼群算法应用[J].山东大学学报（工学版），2004，34（5）：64-67.

[2] 董永峰，雷晓辉，董瑶，等.改进ORB特征提取与匹配算法研究[J].传感器与微系统，2020，39（4）：59-62.

[3] 赵振华，郝晓弘.局部保持鉴别投影及其在人脸识别中的应用[J].电子与信息学报，2013，35（2）：463-467.

[4] 郭倩茜.图像匹配的主要方法分析[J].科技创新与应用，2016（20）：81.

[5] 沈军宇，李林燕，夏振平，等.一种基于YOLO算法的鱼群检测方法[J].中国体视学与图像分析，2018，23（2）：174-180.