基于灰色关联与风驱动优化的图像匹配算法

范 旭，曹中清

(西南交通大学 机械工程学院，四川 成都 610031)

0 引 言

图像匹配[1-5]大致可分为特征匹配与灰度匹配两类。特征匹配是指将图像的特征信息进行匹配，特征信息包括点、线、面等。特征匹配计算量小，但对特征复杂，提取困难的图像实现效果不理想。灰度匹配是指对图像的像素值利用某种相似性度量如：差平方和(SSD)、差绝对值(SAD)、归一化互相关(NCC)等。灰度匹配实现简单，精度高，但计算量大，运算速度慢不适合用于有较高要求的场合。

在图像处理领域，智能算法常作为优化工具被广泛应用。智能算法是一种模拟自然界行为的优化算法，常通过某种准则采用迭代的方式计算最优值。文献[6-8]将遗传算法、粒子群、人工峰群等智能算法引入灰度匹配法，提高图像的匹配速度。

风驱动优化算法是一种基于群体的全局优化算法，具有搜索力强，收敛速度快的特点。可以广泛用于解决多维、连续、离散问题等。本文利用新型风驱动优化智能算法对图像的匹配过程进行优化。将灰色关联分析与图像的直方图信息结合构造风驱动优化算法的适应度函数，利用风驱动优化算法迭代寻优，快速寻找匹配位置，实现对图像的快速鲁棒匹配。

1 粒子群算法

粒子群算法(PSO)是一种模拟自然界鸟群捕食行为的一种智能算法。被广泛的应用于函数优化，全局寻优。设每个问题的一个解为一个粒子，衡量每个粒子的好坏的函数为适应度函数，每个粒子根据其它粒子和自身的飞行经验，从全局空间中搜索最优值。粒子群算法的计算过程如下：

首先初始化所有粒子，随机生成初始位置、初始速度。然后根据适应度函数计算各粒子的适应度值。将每个粒子的适应度值与自身优化解比较与全体优化解比较，记录优化解与最好解。重复之前的过程，直到寻优结束。

2 人工蜂群算法

人工蜂群算法(ABC)是一种群集智能随机优化算法。其思想来源于对蜜蜂采蜜行为的模拟，观察蜂、侦查蜂和采蜜蜂构成了蜂群。优化问题的一个可能解用蜜源位置来表示。每个蜜源的花蜜量构成相应的适应度函数值。人工蜂群算法的计算过程如下：首先随机产生初始蜂群，然后蜜蜂对蜜源进行搜索，采蜜蜂先对相应的蜜源搜索，选择适应度值高的即蜜源量多的蜜源，全部采蜜蜂搜索完成后，将信息传递给观察蜂，观察蜂获得信息后，按照蜜源量多被选择概率大的规则选择蜜源。然后观察蜂进行领域搜索，选择好的解。如果某个蜜源经过固定循环次数后，不能被改进即该处的解要舍弃，则该蜜源处的蜜蜂变为侦查蜂产生一个新的解代替原来的解。如此循环直到达到最大迭代次数，寻找到最优解。

3 基于灰色关联和风驱动优化的图像匹配方法

3.1 灰色关联匹配模型

灰色关联分析是判断数据序列之间相关度的一种方法，其根据数据序列间的发展趋势、相似性，找出信息系统中各因素的影响关系。本文利用灰色关联匹配模型来判断匹配的相似关系，图像的直方图反应了图像像素灰度分布，即各个灰度级与对应频数的关系。本文将模板图像与待匹配子图像的直方图信息做灰色关联分析，判断两幅图像的相似性。灰色关联分析常包括以下步骤：确定分析数列，变量的无量纲化、计算关联系数，计算关联度。

灰色关联分析的参考序列为模板图像的直方图信息，设为Tim,灰色关联分析的比较序列为最佳位置处子图像的直方图信息，设为Sim，这两幅图像的灰色关联度为

(1)

其中

(2)

(3)

(4)

Δo,i(k)=|to(k)-si(k)|

(5)

式中：n为关联序列长度，其取值为直方图的灰度级，n常取值255；to(k)为参考序列Tim中的元素，si(k)为比较序列Sim中的元素。如果两个图的匹配度越高，灰色关联度的值就越大，若两个图完全匹配则灰色关联度的值为1。

3.2 风驱动优化算法

风驱动算法[9-11](WDO)是一种自然启发算法，其原理是根据空气的压力差促使空气流动并且最终达到平衡。每个空气单元达到平衡的最终位置值为目标值，将其作为最优解，是一种新型全局优化算法。算法将影响大气运动的4个主要力[12,13]：摩擦力、气压梯度压力、重力和科氏力带入牛顿第二定律结合理想气体状态方程得出速度更新方程用于迭代寻优。

摩擦力使空气粒子对之前的速度信息进行 “继承”起到认知的作用；气压梯度力使空气粒子追随自身经过的最优位置，起到自我认知学习的作用；重力增加了算法全局寻优性能，可以防止空气粒子在寻优过程中困于边界。科氏力增强了算法搜索新区域的能力，其通过将其它维度的速度加入搜索区域，促使了各个空气粒子的信息共享。这4个力相互合作，相互制约使风驱动算法具有较强的搜索能力。

风驱动优化的算法的原理如下。

一个由S个空气单元，D维搜索空间组成的空气种群可以表示为如下矩阵

(6)

空气粒子在空气种群空间中进行搜索，每一维度的每一个粒子均赋予一个速度值u，则所有空气粒子的速度构成其一个S×D的空气粒子速度矩阵，即

(7)

其中，1≤k≤T，T为最大迭代次数。对于粒子的速度，常设定一个速度边界，粒子的智能在速度边界内运动，当速度超过速度边界时将会被约束回边界内。空气单元的速度约束如下

(8)

在空气单元的运动搜索中，其速度不断不变化，同时导致空气单元的位置也不断变化。种群的中空气粒子的位置仍然是一个S×D的矩阵

(9)

其中，1≤i≤S,1≤d≤D,1≤k≤T。本文WDO算法的适应度函数为两幅图像的灰色关联度的倒数，即适应度(fitness)的值越小，匹配度越大，完全匹配时fitness的值为1。适应度值的计算如式(10)所示

(10)

空气粒子速度和位置根据方程式(11)、式(12)更新

(11)

(12)

3.3 基于灰色关联分析与风驱动优化算法的图像匹配

基于灰色关联分析与风驱动优化算法的图像匹配算法流程如图1所示。

图1 本文算法流程

主要步骤如下：

(1)初始化空气单元数量，最大迭代次数，各参数。设风驱动空气单元总量为N，并且产生初始解集xij,为了提高算法的初始搜索性能，将初始空气粒子均匀分布在搜索图像中。将搜索图像均分为n个均匀的小区域，在各区域内随机产生N/n个空气粒子。过程如图2所示，图2(a)为将图分为16块，即n=16。图2(b)为将N=50个粒子均匀分布到各区域当中。

图2 空气单元的均匀初始化

(2)根据模板直方图信息与搜索子图直方图信息利用灰色关联分析计算各个xij的适应度值。

(3)对每个空气单元个体分别与个体历史最佳位置比较、总体历史最佳位置比较，记录历史最佳位置、总体历史最佳位置。

(4)根据式(11)、式(12)对速度位置更新。

(5)是否达到结束条件，如果达到则结束。否则继续循环。

4 实验与分析

本文在Centrino 2 PC，2.93 Ghz，Matlab 2014a环境中进行实验，并和基于人工蜂群的快速图像匹配算法(GABC)，基于粒子群优化的快速图像匹配算法(GPSO)进行比较，衡量算法性能。实验中搜索图像为256×256的图像“cameramen”，以该图坐标(80,80)为左上角，截取大小为80×80的子图做模板图像。实验图像如图3所示，图3(a)为搜索图像，图3(b)为模板图像。

图3 实验图像

风驱动优化算法的参数设置如下：空气单元数量为50，RT的值为3，g的值为0.3，c的值为0.42，α的值为0.4，最大迭代次数k为50，最大速度vmax为5。粒子群算法的参数设置为：种群数量为50，c1=2，c2=2，最大速度vmax为5，最大迭代次数为50。人工蜂群算法的参数设置为：蜂群大小为50，最大循环迭代数为50，分别进行25次实验，实验结果如表1和图4，图5所示。图4为无噪声情况下GWDO的实验结果，图5为各算法的适应度函数曲线。表1为无噪声情况下的实验数据。

表1 无噪声情况下的实验数据

图4 无噪声情况下GWDO的实验结果

图5 适应度曲线

从表1中可以看出，这3种算法在无噪声情况下的实验结果均比较好，3种算法的匹配精度都为100%，但是从表1中可以看出GPSO算法的平均运行时间最慢为2.02 s，GABC算法的平均运行时间次之为1.89 s，GWDO算法的收敛速度更快，平均运行时间最短为1.56 s。

从图5中的适应度曲线来看，GPSO算法达到收敛的最小迭代步数约为43步，GABC算法达到收敛的最小迭代步数约为20步，GWDO算法达到收敛的最小迭代步数约为12步，可以看出GWDO算法的收敛速度最快。因此在无噪声情况GWDO算法收敛速度具有明显的优势。

为了验证算法的抗噪性，将搜索图像加入强度为0.08的椒盐噪声，实验的匹配结果如图6和表2所示。

图6 加噪声后的GWDO匹配结果

算法实验次数最大迭代次数匹配精度/%平均运行时间/sGPSO2550883.22GABC25501002.29GWDO25501002.06

由图6可以看出，在加入噪声后，GWDO算法仍然能在噪声图像中找到正确的匹配位置，其匹配效果仍然较好。从表2中可以看出，加入噪声后，GPSO算法匹配结果开始出现一定的误差，25次实验中，有3次出现误匹配，匹配精度约为88%。而GABC算法与GWDO算法的匹配精度仍然较高，25次实验中均正确匹配，匹配精度为100%。从平均运行时间来看，3种算法的平均运行时间相比无噪声情况下的平均运行时间都有所增加。这是由于噪声的加入，使算法的搜索时间变长，收敛速度变慢。在噪声情况下，GPSO算法的平均运行时间为3.22 s，GABC的平均运行时间为2.29 s，GWDO的平均运行时间为2.06 s。可见GWDO算法的平均运行时间最短。由此可见，GWDO算法相对GPSO算法与GABC算法在速度和抗噪上均具有优势。

5 结束语

本文成功的将风驱动优化算法与灰色关联分析结合，提出了一种图像匹配算法，该算法空气单元位置矢量为图像的坐标，适应度值为当前搜索位置子图像与模板图像的直方图信息的灰色关联度。经过迭代计算找到匹配位置。经过实验分析可知，GWDO算法在无噪声情况下的收敛速度均优于GPSO算法与GABC算法，收敛速度具有明显的优势。在噪声情况下GWDO算法收敛速度明显优于其它两种算法，且GWDO算法的抗噪性明显优于GPSO算法，具有抗噪性强的优点。实验结果表明GWDO算法具有收敛速度快，匹配精度高，鲁棒性强的优点，可以用于图像的匹配。