基于改进粒子群算法的图像匹配技术研究

冯 浩，李现伟

(1.宿州学院机械与电子工程学院，安徽宿州234000；2.早稻田大学国际情报通信研究科，东京169-8050)

基于改进粒子群算法的图像匹配技术研究

冯 浩1，李现伟2

(1.宿州学院机械与电子工程学院，安徽宿州234000；2.早稻田大学国际情报通信研究科，东京169-8050)

在分析基本粒子群优化算法的基础上，对学习因子进行非线性异步策略调整，改变其固定常数模式，平衡算法在迭代过程中的局部和全局搜索能力；同时引入活力因子，对失活粒子执行变异操作，提高种群多样性。改进算法可以提升对多维空间的全局寻优能力，避免粒子产生早熟收敛现象。将改进粒子群算法引入图像匹配优化问题中，提出了一种基于改进粒子群算法的图像匹配算法，实验结果表明，该算法具有更快的匹配速度以及更高的匹配精度，具有强鲁棒性。

粒子群优化算法；图像匹配；学习因子；活力因子

D01∶10.19329/j.cnki.1673-2928.2016.06.008

引言

随着计算机技术的快速发展，图像匹配技术日渐趋于成熟。作为图像处理的重要技术之一，图像匹配在目标识别、立体视觉、飞行器制导等领域得到较为广泛的应用[1]。目前针对图像匹配方法的研究主要集中于匹配精度、匹配速度以及匹配算法的抗干扰性能等方面。

在图像匹配过程中，特征空间、搜索策略以及相似性度量是其关键的三个要素。针对不同要素选择合适的匹配方法，有利于提高图像匹配的效率。本文以灰度值作为图像匹配特征，同时将模板匹配与粒子群优化(Particle Swarm Optimization，PSO)算法相结合，在研究改进PSO算法的基础上，构建基准图像与模板图像之间的相似性度量数学模型，实现对目标图像的精确匹配。实验结果表明，改进的PSO算法提高了种群多样性，具有更高的收敛精度和收敛速度，全局寻优能力突出。在此基础之上，改进算法可以实现灰度图像的快速匹配，其匹配精度、速度以及抗干扰性均优于对比算法。

1 粒子群优化(PSO)算法

PSO算法是由Kenndy博士和Eberhart博士于1995年提出，它是在研究鸟类群体觅食行为的基础上所提出的一种群智能进化算法，该算法通过模仿鸟群觅食，利用群体协作和信息共享找到食物最优位置[2]。在PSO算法中，单个粒子代表搜索空间中的一个解，并且每个粒子都具有一定的飞行速度，则在D维空间中，假设种群大小为N，每个粒子的飞行速度可表示为vi=(vi1,vi2,···,vid)T，粒子的位置表示为xi=(xi1,xi2,···,xid)T，则第i个粒子根据式(1)、式(2)更新自身速度及位置[3]：

其中：i=1,2,···,N；d=1,2,···,D。w表示惯性权值，取值范围为[0.4,0.9]；c1和c2表示学习因子，反映粒子个体极值和全局极值对下一状态的影响；r1和r2为[0,1]之间的随机数；k表示第k次迭代；在第k次迭代中，表示第i个粒子的飞行速度；表示第i个粒子的位置；表示第i个粒子的个体最优位置；则表示整个粒子群的全局最优位置。

2 改进粒子群优化算法

2.1 学习因子调整策略

由于基本PSO算法在迭代初期收敛速度较快，易产生早熟收敛现象，陷入局部极小，从而使得算法的收敛精度不高，全局寻优能力较差。因此，国内外大量研究学者对标准PSO算法做了改进和优化，如Shi等学者在文献[4]中对惯性权值进行线性调节；Clerc等学者在文献[5]中提出带收缩因子的PSO算法；姜长元等人在文献[6]中提出惯性权重正弦调整的粒子群算法；董平平等人在文献[7]中提出一种改进的自适应惯性权值粒子群优化算法等等，上述算法在收敛性能指标上均有显著提高。

大量实验表明，学习因子的非线性变化可以

更好地解决各种非线性优化问题。本文在此基础上对学习因子进行非线性异步调整，主要思想是：在算法迭代过程中，学习因子c1随迭代次数的增加进行非线性递减，而学习因子c2进行非线性异步递增。通过调整，使得粒子在算法初期的自身调节能力增强，种群多样性增加；而在算法后期，粒子的协作能力逐步提升，社会经验增强，有利于进行全局最优搜索。调整后的学习因子数学模型如下式所示：其中，α(k)表示如下：

实验证明，学习因子上下限在如下范围内变化，算法的收敛速度以及精度可得到较大提升。

2.2 活力因子的引入

本文在构造学习因子策略模型的同时，对标准PSO算法作进一步改进。由PSO算法更新公式可知，当粒子当前位置逐步接近全局最优位置，即二者距离趋于零时，粒子的飞行速度逐渐减小并趋于零，此时粒子运动活力降低，产生停滞现象；反之，二者距离越大，粒子飞行速度也随之加快。因此，可以通过对粒子当前位置进行变异操作来更好地控制粒子飞行速度，从而增加种群多样性，使粒子能够跳出局部极值。为此，引入粒子活力因子σ（σ≥0），通过选择合适的σ，使得当粒子的当前位置与全局最优位置小于σ时，对当前位置执行变异操作，增强全局搜索能力。

在第k次迭代过程中，粒子i的当前位置xi(k)和全局最优位置pg(k)之间的距离定义为d(k)，其数学模型如下：

式（6）中，当d(k)＜σ时，粒子的飞行速度将会以较大概率产生停滞现象，造成算法的陷入局部极值，此时，对粒子i的当前位置xi(k)执行变异操作，改变粒子的飞行方向，通过初始化当前失活粒子的位置来增加种群多样性，使粒子能够以较大概率跳出局部最优。

3 基于AMPSO算法的图像匹配

3.1 图像的模板匹配

由于模板匹配方法具有运算简单、抗干扰性能强的优点，已被广泛应用于图像匹配技术。如图1所示，模板匹配即是在待匹配的基准图像S中，搜索与模板T最为接近的目标子图Si,j的位置。其中，S大小为M×N，模板T大小为X×Y，i,j为目标子图左上角像素点在基准图S中的坐标，i,j满足1≤i≤M-X+1，1≤j≤N-Y+1。

图1 基准图和模板图

本文将改进粒子群优化算法与模板匹配方法进行融合，则图像的模板匹配可以转化为运用PSO算法在二维空间中搜索最优匹配位置，基本流程如图2所示。

图2 基于AMPSO算法的图像匹配流程图

图像的模板匹配算法较多，包括平均绝对差(Mean Absolute Difference，MAD)算法[8]、归一化积相关(Normal Cross Correlation，NCC)算法[9]以及序贯相似性检测法(Sequential Similarity Detection Algo⁃rithm，SSDA算法)[10]等。考虑到匹配速度以及实现难度问题，本文选用MAD算法作为改进PSO算法的适应度评价函数。其数学公式如下：

式（7）中，d(x,y)表示当偏移量为(x,y)时，所对应的匹配度量值，当d(x,y)取最小值时，可以得到最优匹配位置(x,y)。

综合以上分析，将基于改进PSO算法的图像匹配算法简称为AMPSO算法。

3.2 实验仿真

在MATLAB7.0环境下进行实验仿真，同时与传统的模板匹配算法进行对比分析，包括MAD算法以及NCC算法。实验选用Lena灰度图像作为原始待匹配图像，选取原始图像大小254×254，待匹配模板大小为89×86，如图3(a)和(b)所示。利用AMPSO算法对Lena原始图像进行匹配，在无噪声环境下，其最佳匹配结果如图3(c)所示。

图3 原始图像、模板图像以及匹配结果

在AMPSO算法中，惯性权值w选择线性递减策略，其中wmax=0.9，wmin=0.4；设定学习因子上下限分别为，调节系数λ=10；活力因子σ根据实验情况以及经验进行相应设置；设置种群大小为40，最大迭代次数M分别选择30、40、50和60。实验次数为50次。分别与MAD算法以及NCC算法在平均运行时间、正确匹配次数、最优匹配位置、最差匹配位置以及匹配精度指标上进行对比，如表1所示。

由表1可以看出，当最大迭代次数设置较小时，AMPSO算法的匹配精度无法达到100%，而当最大迭代次数大于50时，算法的匹配精度可以得到保证；对于MAD算法和NCC算法，二者匹配精度均可以达到100%，表明这两种算法具有较高的匹配率。同时，可以看出AMPSO算法在平均运行时间指标上明显优于MAD算法和NCC算法，特别是在保证匹配精度的前提下，AMPSO算法的平均运行时间大约是MAD算法的1/16，是NCC算法的1/32，匹配速度明显占优。这也表明AMPSO算法具有快速收敛速度，同时，当选择适当的种群大小以及最大迭代次数时，算法的全局搜索能力会更加突出，在保证匹配速度的同时，可以有效提升图像的匹配精度。

为测试AMPSO算法的抗干扰性能，在图3(a)中加入15%的椒盐噪声，利用AMPSO算法对加噪后的Lena图像进行模板匹配，其最佳匹配结果如图3(d)所示。大量实验证明，在选择合适的种群规模以及迭代次数的前提下，AMPSO算法可以实现对加噪图像的精确匹配。

同时，实验以加噪图像作为基准图像，在模板图像保持不变的前提下，将AMPSO算法和MAD算法以及NCC算法进行图像匹配对比分析。其中，AMPSO算法的种群大小选择40，最大迭代次数选择M=50，其他参数不变。实验次数50次。实验结果见表2所示。

表1 三种匹配算法的不同性能指标比较

表2 加噪环境下三种匹配算法的性能比较

由表2可知，在加噪环境下，AMPSO算法的匹配速度优势明显，耗时少。同时，AMPSO算法在匹配精度上也优于对比算法，可以精确找到模板图像的匹配位置坐标，表现出较好的抗干扰性。

4 结束语

通过对基本PSO算法进行改进优化，改变学习因子的固定模式，实现其非线性异步变化，同时引入活力因子，增加种群多样性，使算法有效跳出局部极值，在提升收敛速度的同时，增强全局寻优能力。将改进PSO算法引入图像匹配技术中，实验结果表明，改进PSO算法可以在保证匹配速度的前提下，实现对目标图像的精确匹配，且抗干扰性能突出，具有强鲁棒性，满足实际应用中对匹配速度和匹配精度的要求，在图像匹配问题优化方面具有一定的实际指导意义。

[1]刘佳，傅卫平，王雯，等.基于改进SIFT算法的图像匹配[J].仪器仪表学报，2013（05）∶1107-1112.

[2]VANDEN BERGH F,ENGELBRECHT A P.Training Prod⁃uct Unit Networks Using Cooperative Particle Swarm Optimiza⁃tion[C]//IEEE International Joint Conference on Neural Net⁃works,Washington DC,USA,2001∶126-131.

[3]KENNEDY J,EBERHART R.Particle swarm optimization [C]//Proceedings of the 4th IEEE International Conference on NeuralNetworks.Piscataway,NJ∶IEEE ServiceCenter,1995∶1942-1948.

[4]SHI Y,EBERHART R.Empirical study of particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolu⁃tionary Computation,Piscataway,NJ∶IEEE press,1999∶1945-1950.

[5]CLERC M.The swarm and the queen∶towards a determin⁃stic and adaptive particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computation.Piscat⁃away,NJ∶IEEE Service Center,1999∶1951-1957.

[6]姜长远，赵曙光，沈士根.惯性权值正弦调整的粒子群算法[J].计算机工程与应用，2012，48（8）∶40-42.

[7]董平平，高东慧,田羽波.一种改进的自适应惯性权值粒子群优化算法[J].计算机仿真，2012，29（12）∶283-286.

[8]刘宝生，闫莉萍，周东华.几种经典相似性度量的比较研究[J].计算机应用研究，2006（11）∶1-3.

[9]杨通钰，彭国华.基于NCC的图像匹配快速算法[J].现代电子技术，2010（22）∶107-109.

[10]王杉，陈翔，司寒羽.基于遥感图像信息特征的单调递增SSDA算法[J].华东交通大学学报，2013（01）∶15-21.

Image Matching Technology Based on Improved Particle Swarm Optimization Algorithm

FENG Hao1,LI Xianwei2
(1.Colloge of Mechanical and Electronic Engineering,Suzhou University,Suzhou AnHui 234000,China; 2.Global Information and Telecommunication Institute,Waseda University,Tokyo,169-8050,Japan)

Based on the analysis of the basic particle swarm optimization algorithm,the thesis adjusted the learn⁃ing factor by the strategy of nonlinear asynchronous,changed the model of fixed constant,and balanced the global and local search ability in the process of iteration;simultaneously the thesis introduced the activity factor to im⁃prove the population diversity which performed mutation for the particles who lost energy.The improved algorithm can improve the global search capability in the multidimensional space,and avoided premature convergence phe⁃nomenon.The improved particle swarm algorithm was introduced into image matching optimization problem,and proposed an image matching algorithm based on the improved particle swarm algorithm,the experimental results showed that The algorithm has the advantages of faster matching speed and higher matching accuracy,and has strong robustness.

particle swarm optimization algorithm;image matching;learning factor;activity factor

TP391

A

1673-2928（2016）06-0022-04

（责任编辑：郝安林）

2016-03-20

宿州学院一般科研项目(2014yyb03)、宿州学院科研平台开发课题(2014YKF44)。

冯浩(1983-)，男，河南安阳人，宿州学院讲师，硕士，主要研究方向：图像处理、智能算法。