改进人工蜂群算法在数字图像相关中的应用

摘 要： 针对人工蜂群算法存在的收敛速度较慢，易陷入局部最优解的问题，提出一种改进的人工蜂群优化算法，并应用于数字图像相关的整像素位移搜索中。该算法借助相关度值的变化来动态调整跟随蜂的搜索步长，平衡其全局和局部的搜索能力；侦察蜂利用遗传算法的交叉运算产生新解，改善全局搜索能力。实验结果表明，改进的算法能有效地提高收敛速度，改善整像素位移搜索的性能。

关键词： 人工蜂群算法； 数字图像相关； 变形； 整像素位移； 动态步长； 交叉运算

中图分类号： TN919?34； TP301.6 文献标识码： A 文章编号： 1004?373X（2013）24?0070?03

Application of improved artificial bee colony algorithm in digital image correlation

YANG Song1，2， SHAO Long?tan1， JIN Feng3， SHI Peng?hui4， CHI Jian?wei5

（1. State Key Laboratory of Industrial Equipments， Dalian University of Technology， Dalian 116024， China；

2. Education Technology & Computing Center， Dalian Ocean University， Dalian 116023， China；

3. Dalian Municipal Meteorological Bureau， Dalian 116001， China； 4. College of Information Engineering， Dalian Ocean University， Dalian 116023， China；

5. College of Science， Dalian Ocean University， Dalian 116023， China）

Abstract： Aiming at the problems of slow convergence speed and easy to fall into local optimal solution， which exist in artificial bee colony algorithms， an improved artificial bee colony optimization algorithm is proposed for the pixel displacement search in digital image correlation. In the algorithm， the search step of the following bee is adjusted dynamically according to the changes of the correlation to balance the capability of global search and local search， and the scout bee employs crossover operation of genetic algorithm to generate new solution for improving the global search capacity. The experimental results show that the improved algorithm can enhance the convergence capability effectively and improve the performance of integer pixel displacement search.

Keywords： artificial bee colony algorithm； digital image correlation； deformation；pixel displacement； dynamic step； crossover operarion

数字图像相关方法（Digital Image Correlation Method，DICM），又称为数字散斑相关方法 （Digital Speckle Correlation Method，DSCM） 是现代光学测量技术的重要方法之一[1]，用于实现物体表面的位移和变形的测量。数字图像相关方法在1980年由Peters，Ranson和Yamaguchi同时独立提出的。该方法不仅具有其他光学测量方法所具有的全场、非接触测量等优点外，还具有光路简单、对测量环境要求低、便于开展工程现场测量等优点[2]，是一种很有应用前途的光学测量方法。

数字图像相关法研究的核心内容是相关搜索方法。早期采用逐点搜索法，这会花费大量时间，后来很多学者对其进行改进，相继提出了Newton?Rapson算法[3]、爬山法[4]、十字搜索法[5]、小波变换法[6]和神经网络法[7]等，这些算法严重依赖于初值的选取，且部分在理解和实现上比较复杂。相比之下，群智算法有诸多优点，可直接把目标函数值作为搜索信息，避免函数求导，可解决目标函数较复杂的问题。目前应用的主要有差分进化（DE）算法[8]、遗传（GA）算法[9]、粒子群（PSO）算法[10]等，这些算法无需计算梯度和二阶导数，是对图像相关搜索方法的有益补充。近年来一些新兴群智优化算法的出现，为图像相关搜索方法的研究增添了新的动力。

人工蜂群算法（Artificial Bee Colony，ABC）是由土耳其埃尔吉耶斯大学的Karaboga在2005年提出的一种基于蜜蜂群智搜索行为的随机优化算法[11]。蜂群算法采用劳动分工和协作的机制，具有控制参数少，计算简洁及易于实现等优点，既能解决连续优化问题，又能解决组合优化问题[12]。函数优化测试表明[13]，人工蜂群算法比遗传算法、差分进化算法和粒子群算法具有更好的优化性能，且容易与其他算法相结合进行改进。本文提出改进人工蜂群算法（IABC），应用于数字图像相关搜索中，有效提高了整像素位移的搜索能力。

1 数字图像相关法基本原理

数字图像相关法借助物体变形前后两幅图像的局部相关性来计算得到点的位移值，即在变形前图像中以特定点[x，y]为中心取[2M+1×2M+1]个像素的区域，通过一定的搜索方法在变形后的图像上寻找同样大小子区域的中心[x*，y*]，两点位移差为[u，v]，见式（1）。位移量[u，v]的计算要考虑两个区域的相关度，见式（2）。

[x*=x+u， y*=y+v] （1）

[C=y=-My=Mx=-Mx=Mfx，y-fmgx*，y*-gmy=-My=Mx=-Mx=Mfx，y-fm2?y=-My=Mx=-Mx=Mgx*，y*-gm2] （2）

式中：[M]为样本区域半径；[fx，y]为图像上点[x，y]处的灰度值；[gx*，y*]为图像上点[x*，y*]处的灰度值；[fm]，[gm]为对应区域的灰度均值。相关度[c]取值范围为[-1，1]，当参数[u]和[v]为适当值时，两个区域的相关度达到全局最大。搜索位移值[u，v]的过程是求2个区域相关度极值的过程。要计算每个点精确的位移值，可以通过两步法：先粗定位，后细定位。即先计算出整像素位移，然后计算精确的亚像素位移。数字图像相关的搜索时间主要取决于粗定位。相关系数[c]是关于位移值[u，v]的函数，粗定位问题可以看成两个离散整数变量关于相关函数[c]的优化问题，且[u]和[v]被限定在搜索范围内。细定位可以根据相关系数的单峰性近似满足高斯分布的特点，采用相关函数曲面拟合法求极值点来计算亚像素位置[14]。

2 基本人工蜂群算法

人工蜂群算法主要模拟蜂群的智能采蜜行为，蜜蜂根据各自的分工进行不同的采蜜活动，并实现蜜源信息的共享和交流，从而找到问题的最优解。在基本人工蜂群算法中，蜜蜂主要有引领蜂、跟随蜂和侦察蜂。人工蜂群算法在求解优化问题时，蜜源位置被抽象成解空间中的点，蜜蜂采蜜的过程也就是搜寻最优解的过程。引领蜂和跟随蜂根据式（3）进行蜜源位置的更新：

[υij=xij+rijxij-xkj] （3）

式中：[k∈1，2，…，N]，[j∈1，2，…，d]，[k]和[j]都是随机选取的，且[k≠i]，[N]表示解的个数；[rij∈][-1，1]之间的随机数，它控制[xij]邻域的生成范围。

跟随蜂通过观察引领蜂的摇摆舞来判断蜜源的收益率，并依据收益率来选择蜜源。收益率由式（4）可得：

[Pi=fυiji=1Nfυij] （4）

式中[fυi]表示蜜源[υi]的相关度。跟随蜂选择收益率大的蜜源，根据式（3）进行搜索。搜索完毕后，采用贪心选择机制，计算全局最优蜜源位置。

若连续经过limit次迭代后，某个蜜源的相关度没有得到改善，表明此蜜源已陷入局部最优，应该被放弃，与这个蜜源对应的引领蜂转换成侦察蜂，新蜜源位置由式（5）产生：

[xji=xjmin+rxjmax-xjmin] （5）

式中：[xjmax]和[xjmin]分别表示变量的最大值和最小值；[r]是[0，1]之间随机数。通过如此重复搜索，最终找到最优解。

3 基于改进人工蜂群算法的数字相关搜索

3.1 改进人工蜂群算法

跟随蜂在选中的蜜源邻域内按照式（3）进行搜索，其步长具有随机性，算法寻优速度相对较慢，易错过或陷入全局最优解。文献[15]对搜索步长做线性调整，随步长减少，进入局部最优解邻域内也很难跳出。这里将跟随蜂更新蜜源的方法做了修改，步长根据相关度函数值进行动态调整，如式（6）～式（8）所示：

[υij=xij+ωnxij-xkj] （6）

[ωn=e-an/an-1，n=0，1，…，Gmax] （7）

[an=1mi=1mfυni-fυnmax， n=0，1，2，…] （8）式中：[ωn]称为动态步长因子；[fυni]为[υi]在第[n]次迭代时对应的相关度；[fυnmax]为在第[n]次迭代时对应的最优相关度；[Gmax]为最大迭代次数。当[an]为第[n]次迭代时，引领蜂搜索后种群相关度函数的平整度因子，其值根据相关度值进行变换。

在迭代过程中，为防止[anan-1]的值变化过大，采用工程中常用的[e]作为指数，可有效降低比值变化的幅值，使得[ωn]的取值范围在区间[0，1]内。[ωn]的计算充分利用相关度函数的信息，在搜索方向上具有一定的启发性。当[an]变化较大时，[ωn]也就较大，便于大步长搜索；当[an]变化较小时，[ωn]也就较小，便于在相关度极值点附近小步长搜索，这样可以较好地平衡全局搜索和局部搜索能力，不易陷入局部极值。当迭代次数大于limit时，侦查蜂根据式（5）产生新蜜源，式（5）具有一定的随机性，这里提出将被放弃的蜜源与当前的全局最优蜜源进行交叉运算，如式（9）所示：

[υlimit=υmax×p+υlimit×1-p] （9）

式中：[υlimit]为经limit次迭代后相关度没有发生变化的蜜源；[υmax]为当前最优蜜源；[p]为遗传交叉因子。通过运用遗传交叉运算，改善算法的全局搜索能力。

3.2 改进算法的流程

（1）初始化蜜源[υii=1，2，…，N]，[υi]为2维向量[ui，vi]，根据式（1），式（2）计算各个蜜源的相关度；

（2）模拟蜂群行为，引领蜂根据式（3）搜索最优蜜源；

（3）根据式（4）计算各蜜源的收益率，跟随蜂选择收益率高的蜜源，计算[ωn]的值（[a0]为初始时种群相关度函数的平整度因子），并利用式（6）继续搜索；

（4）采用贪心选择机制，更新全局最优蜜源；

（5）若某个蜜源经过limit次迭代后其相关度仍没有得到改善，则根据式（9）得到新的蜜源；

（6）若迭代次数达到设置的最大次数Gmax时，算法结束，否则转到步骤（2）。

4 实验结果与分析

根据文献[16]制作两幅散斑图像，且第二幅图像相对第一幅图像的位移量为（14.3，-5.2）。相关运算的参数设置为：搜索范围设定为40×40 pixel区域，相关运算模板的大小为21×21 pixel，种群个数为50（即引领蜂和跟随蜂各占总数的一半，均为25个），交叉因子为0.9。所用计算机配置为：Intel Core2 CPU（2.8 GHz），2 GB内存。由于优化算法具有随机性，为获得更为一般的规律，故采用统计学方法对随机点（123，87）进行1 000次整像素位移计算，程序采用Matlab编程实现。

分别采用遗传（GA）算法、粒子群（PSO）算法、基本人工蜂群（ABC）算法和改进人工蜂群（IABC）算法进行计算，得到收敛率随迭代次数变化的曲线，如图1所示。

由图1可知，改进算法在55代附近开始接近100%收敛，而其他算法还没达到收敛，表明在种群数相等的条件下，随着迭代次数的增加，改进人工蜂群算法具有更高的收敛率。对计算过程中的迭代时间和收敛率进行拟合，绘制出时间与收敛率的关系图，如图2所示。由图可知，当计算时间在85 s附近时，改进算法已近似100%收敛，而其他算法尚未达到，说明在相同种群数的条件下，改进算法的收敛时间更短。除此之外，还将此方法引入到高维连续函数优化应用中，取得了更为显著的优化效果。

图1 迭代次数与收敛率的关系图

图2 计算时间与收敛率关系图

5 结 语

本文针对人工蜂群优化方法收敛速度慢、易陷入局部最优解的缺点，提出了基于动态步长因子的改进人工蜂群算法。新算法通过适应度值来动态调整搜索步长，改善算法的收敛性能，并借鉴遗传算法的交叉操作，增强群体的优秀特征，加快搜索速度。通过模拟数字散斑图像对算法进行验证表明：本文算法具有较强的全局搜索能力，显著提高数字图像相关中整像素位移的搜索速度。

参考文献

[1] PETERS W H， RANSON W F. Digital imaging techniques in experimental stress analysis [J]. Optical Engineering， 1982， 21（3）： 427?431.

[2] 王怀文，亢一澜，谢和平.数字散斑相关方法与应用研究进展[J].力学进展，2005，35（2）：195?203.

[3] BRUCK H A， MCNEIL S R， SUTTON M A， et al. Digital image correlation using Newton? Rapshon method of partial differential correction [J]. Experimental Mechanics， 1989， 29（3）： 261?267.

[4] ZHAO Wen?zhong， JIN Guan?chang. An experimental study on measurement of Poisson’s ratio with digital correlation method [J]. Journal of Applied Polymer Science， 1996， 60： 1083?1088.

[5] 芮嘉白，金观昌，徐秉业.一种新的数字散斑相关方法及其应用[J].力学学报，1994，26（5）：599?607.

[6] 简龙晖，林碧森，刘宁，等.基于小波变换的新型数字散斑相关方法[J].光学技术，2003（7）：216?218.

[7] PITTER M C， SEE C W， SOMEKH M G. Subpixel microscopic deformation analysis using correlation and artificial neutral networks [J]. Optics Express， 2001， 8（6）： 322?327.

[8] 潘兵，谢惠民.基于差分进化的数字图像相关方法[J].光电子·激光，2007，18（1）：100?103.

[9] 陈华，叶东，陈刚，等.遗传算法的数字图像相关搜索法[J].光学精密工程，2007，15（10）：1633?1637.

[10] 杜亚志，王学滨.基于粒子群算法的整像素数字图像相关方法[J].计算机工程与应用，2012（6）：200?204，208.

[11] KARABOGA D. An idea based on honey bee swarm for numerical optimization， TR06 [R]. UK： Computer Engineering Department， Engineering Faculty， Erciyes University， 2005.

[12] 王慧颖，刘建军，王全洲.改进的人工蜂群算法在函数优化问题中的应用[J].计算机工程与应用，2011（13）：36?39.

[13] 张超群，郑建国，王翔.蜂群算法研究综述[J].计算机应用研究，2011，28（9）：3201?3205，3214.

[14] 于起峰，尚洋.摄影测量学原理与应用研究[M].北京：科学出版社，2009.

[15] 刘俊霞，贾振红，覃锡忠，等.改进人工蜂群算法在信道分配上的应用[J].计算机工程与应用，2013（7）：119?122.

[16] 金观昌.计算机辅助光学测量[M].北京：清华大学出版社， 2007.