一种基于自适应蚁群智能的空中机器人视觉分层匹配方法

摘要

一种基于自适应蚁群智能的空中机器人视觉分层匹配方法，步骤如下：步骤一：确定搜索单元；首先，将待匹配图像两次分割成与目标图像大小相同的一块块的小图像：其次，计算各小块图像与目标图像的相似度；步骤二：初始化参数；步骤三：根据信息素浓度，通过概率选择公式，确定是否把某个单元归到这次搜索之中；步骤四：更新信息素浓度；步骤五：更新全局最优相似度F_max，以及全局的平均相似度F_mean；步骤六：Nc＝Nc+1，返回步骤三，直到完成预定的算法循环次数N

说明书

(一)技术领域

本发明涉及一种基于自适应蚁群智能(Improved Adaptive Ant ColonyOptimization)的空中机器人视觉分层匹配方法，属于计算机视觉信息处理领域。

(二)背景技术

空中机器人在侦察巡逻、电子干扰、通信中继、自然灾害的监视与支援等很多军事及民用领域具有广泛的应用价值，一直受到世界各国的普遍重视。其中视觉匹配系统是空中机器人系统组成中极其重要的一部分，在空中机器人完成目标检测、定位导航等任务过程中起着不可或缺的关键作用，是空中机器人研究的热点之一。

视觉匹配中对于尺寸很大的搜索图，图像相关匹配的数据量和计算量很大，而图像相关匹配的计算实时性在一定程度上又决定了该技术的实用性。因此，和可靠性、精度一样，图像匹配的速度也是性能的重要体现。为了加快图像匹配速度，常用的快速匹配方法主要有两种：一种是减少在非匹配点上的相关计算总量，如序贯相似性检测算法；另一种是改进搜索策略以避免不必要的计算，如多分辨率塔形结构算法。研究表明，图像匹配的速度主要取决于匹配算法的搜索策略。由于传统匹配算法的基本搜索策略是遍历性的，为了找到最优匹配点，传统方法均必须在搜索区域内的每一个像素点上进行区域相关匹配计算，但除了一个最优匹配点外，绝大部分时间都是在非最优匹配点上作匹配计算。因此，如果能找到一种有效的搜索策略实现非遍历性搜索，则图像匹配速度将大大提高。

蚁群优化(Ant Colony Optimization)算法是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法，该算法采用了正反馈并行自催化机制，具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优点，在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜力。

蚁群优化算法是由蚂蚁觅食行为演化来的优化算法，蚂蚁个体之间是通过一种称之为信息素(Pheromone)的物质进行信息传递，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，在它所经过的路径上会留下一定量的信息素，信息素的强度与路径长度有关。并且蚂蚁在运动过程中能够感知路径上信息素的存在及其强度，并以此指导自己的对路径的选择，蚂蚁倾向于朝着信息素强度较高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法采用了正反馈并行自催化机制，该算法具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优点，在解决其他许多复杂优化问题方面也已经展现出了优异的性能和巨大的发展潜力。

自然界中，像蚂蚁这类社会性动物，单只蚂蚁的能力和智力非常简单，但它们通过相互协调、分工、合作完成不论工蚁还是蚁后都不可能有足够能力来指挥完成的筑巢、觅食、迁徙、清扫蚁穴等复杂行为。蚂蚁的食物源总是随机散布于蚁巢周围，我们只要仔细观察就可以发现，经过一段时间后，蚂蚁总能找到一条从蚁巢到食物源的最短路径。科学家曾经通过“双桥实验”对蚁群的觅食行为进行了研究。发现除了能找到巢穴和食物源之间的最短路径之外，蚁群对环境有着极强的适应能力。例如当原有的最短路径由于一个新的障碍物的出现而变得不可行时，蚁群能迅速找到一条新的最短路径。因此，在现实生活中，我们总可以观察到大量蚂蚁在巢穴与食物源之间形成近乎直线的路径，而不是曲线或者圆等其它形状，如图1(a)所示。蚂蚁群体不仅能完成复杂的任务，而且还能适应环境的变化，如在蚁群运动路线上突然出现障碍物时，一开始各只蚂蚁分布是均匀的，不管路径是否长短，蚂蚁总是先按同等概率选择各条路径，如图1(b)所示。蚂蚁在运动过程中，能够在其经过的路径上留下信息素，而且能感知这种物质的存在及其强度，并以此指导自己运动的方向，蚂蚁倾向于信息素浓度高的方向移动。相等时间内较短路径上的信息量就遗留得比较多，则选择较短路径的蚂蚁也随之增多，如图1(c)所示。不难看出，由于大量蚂蚁组成的蚁群集体行为表现出了一种信息正反馈现象，即某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息交流机制来搜索食物，并最终沿着最短路径行进，如图1(d)所示。

蚁群是如何完成这些复杂任务的呢？仿生学家经过大量的观察、研究发现，蚂蚁在寻找食物时，能在其经过的路径上释放一种蚂蚁特有的信息素，使得一定范围内的其他蚂蚁能够感觉到这种物质，且倾向于朝该物质强度高的方向移动。因此，蚁群的集体行为表现为一种信息正反馈现象：某条路径上经过的蚂蚁数越多，其上留下的信息素也就越多(当然，随时间的推移会逐渐蒸发)，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径上信息素的强度。随着时间的推移，整个蚁群最终会收敛到最短的遍历路径上。

蚁群算法最初是用于解决旅行商问题，旅行商问题的简单形象描述是：给定n个城市，有一个旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径。

作为一种新兴的启发式仿生智能优化算法，目前人们对蚁群优化算法的研究已经由当初单一的旅行商问题领域渗透到了多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内的研究逐渐拓展到了连续域范围内的研究，而且在蚁群优化算法的硬件实现上也取得了很多突破性进展，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。

(三)发明内容

本发明的目的在于提出一种基于自适应蚁群智能的空中机器人视觉分层匹配方法，以提供一种解决空中机器人视觉匹配问题的有效途径，也可应用于其它复杂的智能优化问题。

该方法利用改进的自适应蚁群算法与归一化积相关结合进行图像的快速粗匹配，然后进行图像的精确匹配，从而实现空中机器人的视觉匹配。该方法充分利用了蚁群算法能快速找到准最优匹配点的特点。

蚁群算法最初是用于解决旅行商问题(Traveling Salesman Problem，TSP)，旅行商问题的简单形象描述是：给定n个城市，有一个旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径。

基本蚁群算法的数学模型如下：

设b_i(t)表示t时刻位于元素i的蚂蚁数目，τ_ij(t)为t时刻路径(i，j)上的信息量，n表示TSP规模，即城市总数目，m为蚁群中蚂蚁的总数目，则$m=\underset{i=1}{\overset{n}{\Sigma }}{b}_i\left(t\right);$$\Gamma =\left\{{\tau }_{\mathrm{ij}}\left(t\right)\right|c_i,c_j⋐C\}$是t时刻集合C中元素(城市)两两连接l_ij上残留信息量的集合。在初始时刻各条路径上信息量相等，并设初始信息量为τ_ij(0)＝const。

蚂蚁k(k＝1，2，.....，m)在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表tabu_k(k＝1，2，....，m)来记录蚂蚁k当前所走过的城市，集合tabu_k随着进化过程作动态调整。

搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。

表示在t时刻蚂蚁k由元素(城市)i转移到元素(城市)j的状态转移概率

$p_{\mathrm{ij}}^k\left(t\right)=\left(\begin{array}{cc}\frac{{\left[{\tau }_{\mathrm{ij}}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{\mathrm{ij}}\right]}^{\beta }}{\underset{k\in {\mathrm{allowed}}_k}{\Sigma }{\left[{\tau }_{\mathrm{ik}}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{\mathrm{ik}}\right]}^{\beta }}& \mathrm{ifj}\in {\mathrm{allowed}}_k\\ 0& \mathrm{otherwise}\end{array}\right)---\left(1\right)$

式中，allowed_k＝{C-tabu_k}表示蚂蚁k下一步允许选择的城市。

α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间协作性越强；

β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪心规则。

η_ij(t)为启发函数，其表达式如下

${\eta }_{\mathrm{ij}}\left(t\right)=\frac{1}{d_{\mathrm{ij}}}---\left(2\right)$

式中，d_ij表示相邻两个城市之间的距离。对蚂蚁k而言，d_ij越小，则η_ij(t)越大，也就越大。显然，该启发函数表示蚂蚁从元素(城市)i转移到元素(城市)j的期望程度。

为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存入大脑的同时，存贮在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。

由此，t+n时刻在路径(i，j)上的信息量可按如下规则进行调整

τ_ij(t+n)＝(1-ρ)·τ_ij(t)+Δτ_ij(t)                      (3)

${\mathrm{\Delta \tau }}_{\mathrm{ij}}\left(t\right)=\underset{k=1}{\overset{m}{\Sigma }}{\mathrm{\Delta \tau }}_{\mathrm{ij}}^k\left(t\right)---\left(4\right)$

式中，ρ表示信息素挥发系数，则1-ρ表示信息素残留因子，为了防止信息的无限积累，ρ的取值范围为：$\rho ⋐\left[\mathrm{0,1}\right);$

Δτ_ij(t)表示本次循环中路径(i，j)上的信息素增量，初始时刻${\mathrm{\Delta \tau }}_{\mathrm{ij}}^k\left(0\right)=0$，表示第k只蚂蚁在本次循环中留在路径(i，j)上的信息量。

在Ant-Cycle模型中：

式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；

L_k表示第k只蚂蚁在本次循环中所走过路径的总长度。

本发明是一种基于自适应性蚁群智能的空中机器人视觉分层匹配方法，其具体实现步骤如下(可参见图2)：

步骤一：确定搜索单元。

首先，将待匹配图像两次分割成与目标图像大小相同的一块块的小图像：第一次，将分割的起始坐标放在待匹配图像的(1，1)点，如图3；第二次，将起始坐标放在第一次分割的第一个小图像的中心坐标处，如图4。

其次，计算各小块图像与目标图像的相似度。本发明的相似度计算采用归一化积相关匹配算法，归一化积相关匹配算法的公式如下：

$F(u,v)=\frac{\underset{x,y}{\Sigma }f(u+x,v+y)t(x,y)}{\sqrt{\underset{x,y}{\Sigma }{f}^2(u+x,v+y)}\sqrt{\underset{x,y}{\Sigma }{t}^2(x,y)}}---\left(6\right)$

式中，t(x，y)是目标图像在其坐标为(x，y)的像素点的灰度值，而(u，v)则是待匹配图像中分割的一个小图像的左上角的坐标，f(u+x，v+y)是待匹配图像中相应坐标的像素点的灰度值；

经过计算，每一次分割得到的每个小图像都具有一个自己的与目标图像的相似度。

显然，从图4中可以看到，第二次分割的成的每块小图像都和第一次分割出来的四块相邻的小图像有重叠的部分，把这样的五块小图像记为一个单元。再将每个单元中五个小图像中的最大的相似度作为此单元的相似度。如此，就可以用较少的计算量得到较多的相关图像匹配的信息。

步骤二：初始化参数。

使本代的迭代次数Nc＝1，最大的迭代次数为Nc_max；本次的蚂蚁数目为m＝1，蚂蚁总数为M(根据目标图像的大小来定)；使初始信息素浓度τ_ij＝const，const是一个常数。

计算全局最优的相似度F_max和全局的平均相似度F_mean，如下所示：

F_max＝max(F(i，j))(7)

F_mean＝mean(F(i，j))(8)

式中，F(i，j)为每个单元的相似度。

步骤三：根据信息素浓度，依据概率选择公式

当Nc＝1时，P_ij＝1；

当Nc≠1时，则P_ij的值如下：

其中，randm为随机数；τ_max，τ_min分别是信息素浓度的最大值和最小值。

通过概率选择公式，确定是否把某个单元归到这次搜索之中，即是否成为搜索单元；当P_ij＝1时，就认为这个单元为搜索单元，在搜索的范围之内；这样M只蚂蚁可以在各个搜索单元中随机搜索，即每只蚂蚁随机地在搜索单元中寻找一个与目标图像大小相等的小图像并计算该小图像与目标图像的相似度，记为F_m(i，j)，其中下标m表示是此相似度是第m只蚂蚁搜索的。从而得到M种结果，即M个小图像。

此次搜索完毕后，更新每个搜索单元的相似度F(i，j)，其公式如下：

F(i，j)＝max(F(i，j)，F_m(i，j))         (10)

式中，分别计算此次搜索中的每个搜索单元的M个小图像与目标图像的相似度，记为F_m(i，j)，其中下标m表示是此相似度是第m只蚂蚁搜索的；如果搜索单元中有F_m(i，j)大于这个搜索单元的相似度F(i，j)，则让这个相似度F_m(i，j)作为此单元这一代的相似度F(i，j)。

步骤四：更新信息素浓度

本次迭代结束后，进行信息素更新，其更新规则如下：

τ(t+1)＝ρ·τ(t)+Δτ(t)               (11)

其中，ρ是信息素残留系数，即每一代过后信息素的残留。Δτ是信息素浓度增量矩阵，其值用下式进行计算。

${\mathrm{\Delta \tau }}_{\mathrm{ij}}=\left(\begin{array}{cc}\mathrm{const}1& \mathrm{ifF}(i,j)\ge F\_\max \\ \mathrm{const}2& \mathrm{ifF}\_\mathrm{mean}\le F(i,j)<F\_\max \\ 0& \mathrm{else}\end{array}\right)---\left(12\right)$

其中，F_max为全局最优的相似度；

F_mean为全局的平均相似度；

const1和const2是两个常数，且const1>const2>0。

当计算得到的Δτ_ij＝0时，就把相应的单元暂时排除在精匹配范围之外；Δτ_ij≠0时，就把相应的单元纳入精匹配范围之内。这样，随着迭代次数的增加，在精匹配范围内的单元就会减小，即把相似度小的单元淘汰掉，记在精匹配范围内的单元数目为Ng。

步骤五：更新全局最优相似度F_max，以及全局的平均相似度F_mean。公式如下：

F_max＝max(F(i，j))    (13)

F_mean＝(1/K)×∑F(i，j)    (14)

其中，K为得到的精匹配范围中的单元的数目，F(i，j)是相应单元的相似度

步骤六：Nc＝Nc+1，返回步骤三，直到完成预定的算法循环次数N_Cmax，或者精匹配中的单元数目Ng小于设定阈值T，或者全局最优相似度达到或超过设定的相似度F_t。

一般来说，精匹配中的单元越少，精匹配时计算量越小，但是这样容易进入局部最优，所以限定Ng要大于一个数这是必要的。

步骤七：进行精匹配，寻找最佳匹配位置。

计算待匹配图像中的精匹配区域的所有像素点的相似度，公式为式(6)。其中，t(x，y)是目标图像在其坐标为(x，y)的灰度值，而(u，v)则是待匹配图像中精匹配区域中像素的坐标，f(u+x，v+y)是待匹配图像中相应坐标点的灰度值。

所有像素点都对应一个相似度，找到其中最大的相似度值对应的那个像素点，以这个像素点为左上角像素点，大小和目标图像一样的矩形区域就是最佳的匹配位置。

步骤八：算法结束，并输出最优结果。

本发明一种基于自适应蚁群智能的空中机器人视觉分层匹配方法，其优点及功效在于：应用于空中机器人视觉系统中，能够快速及准确地在待匹配图像中找到目标图像的位置，从而更好地使机器人完成它的任务。

(四)附图说明

图1现实中蚁群寻找食物的过程

图2基于自适应蚁群智能的空中机器人视觉分层匹配的流程

图3待匹配图像的第一次分割图

图4待匹配图像的第二次分割图

图5蚁群聚类进化曲线

图中标号及符号说明如下：

F_max——本代最高的相似度

F_t——粗匹配阶段设定的最高相似度

Ng——本代得到精匹配范围内的搜索单元数目

T——设定的精匹配的最小的搜索单元数目

Nc——算法循环次数

Nc_max——算法最大循环次数

Y——满足条件(是)

N——不满足条件(否)

(五)具体实施方式

下面通过一个具体实施例来验证本发明所提出的基于自适应蚁群智能的空中机器人视觉分层匹配方法的性能，所采用的是空中机器人视觉系统所采集的一幅464×956png格式的待匹配图像和一幅需要空中机器人寻找的目标图像，其为49×42png格式的图像，以此作为验证对象。实验环境为1.8Ghz，2G内存，MATLAB 7.0版本，其具体实现步骤如下：

步骤一：将待匹配图像两次分割成与目标图像大小相同的一块块的小图像：第一次，将分割的起始坐标放在待匹配图像的(1，1)点；第二次，将起始坐标放在(25，21)。第一次分割的小图像中的每四小块和第二次分割的一块小图像作为一个单元，再计算待匹配图像中各小块图像与目标图像的相似度，公式如下：

$F(u,v)=\frac{\underset{x,y}{\Sigma }f(u+x,v+y)t(x,y)}{\sqrt{\underset{x,y}{\Sigma }{f}^2(u+x,v+y)}\sqrt{\underset{x,y}{\Sigma }{t}^2(x,y)}}---\left(6\right)$

式中，t(x，y)是目标图像在其坐标为(x，y)的像素点的灰度值，而(u，v)则是待匹配图像中分割的一个小图像的左上角的坐标，f(u+x，v+y)是待匹配图像中相应坐标的像素点的灰度值；

每个单元中五个小图像中的最大的相似度作为此单元的相似度。如此，得到了168个单元及其相似度。

步骤二：初始化参数。

使本代的迭代次数Nc＝1，最大的迭代次数为Nc_max＝10；蚂蚁数目为m＝1，蚂蚁总数为M＝40；使初始信息素浓度τ_ij＝0.95。

计算全局最优的相似度F_max和全局的平均相似度F_mean，如下所示：

F_max＝max(F(i，j))

F_mean＝mean(F(i，j))

式中，F(i，j)为每个单元的相似度。

步骤三：根据信息素浓度，依据概率选择公式

当Nc＝1时，Pij＝1；

当Nc≠1时，则Pij的值如下：

其中，randm为随机数；τ_max，τ_min分别是信息素浓度的最大值和最小值。

通过概率选择公式，确定是否把某个单元归到这次搜索之中，即是否成为搜索单元。当P_ij＝1时，就认为这个单元为搜索单元，在搜索的范围之内。这样40只蚂蚁可以在各个搜索单元中随机搜索，即每只蚂蚁随机地在搜索单元中寻找一个与目标图像大小相等的小图像并计算该小图像与目标图像的相似度，记为F_m(i，j)，其中下标m表示是此相似度是第m只蚂蚁搜索的。从而得到40种结果。

此次搜索完毕后，更新每个搜索单元的相似度F(i，j)，其公式如下：

F(i，j)＝max(F(i，j)，F_m(i，j))

式中，分别计算此次搜索中的每个搜索单元的40个小图像与目标图像的相似度，记为F_m(i，j)，其中下标m表示是此相似度是第m只蚂蚁搜索的；如果搜索单元中有F_m(i，j)大于这个搜索单元的相似度F(i，j)，则让这个相似度F_m(i，j)作为此单元这一代的相似度F(i，j)

步骤四：更新信息素浓度

本次迭代结束后，进行信息素更新，其更新规则如下

τ(t+1)＝0.9×τ(t)+Δτ(t)

其中，Δτ是信息素浓度增量矩阵，其值用下式进行计算。

${\mathrm{\Delta \tau }}_{\mathrm{ij}}=\left(\begin{array}{cc}0.1& \mathrm{ifF}(i,j)\ge F\_\max \\ 0.08& \mathrm{ifF}\_\mathrm{mean}\le F(i,j)<F\_\max \\ 0& \mathrm{else}\end{array}\right)---\left(12\right)$

其中，F_max为全局最优的相似度；

F_mean为全局的平均相似度；

当计算得到的Δτ_ij＝0时，就把相应的单元暂时排除在精匹配范围之外；Δτ_ij≠0时，就把相应的单元纳入精匹配范围之内。记在精匹配范围内的单元数目为Ng。

步骤五：更新全局最优相似度F_max，以及全局的平均相似度F_mean。

公式如下：

F_max＝max(F(i，j))

F_mean＝(1/K)×∑F(i，j)

其中，K为得到的精匹配范围中的单元的数目，F(i，j)是相应单元的相似度

步骤六：Nc＝Nc+1，返回步骤三，直到完成预定的算法循环次数10，或者精匹配中的单元数目Ng小于设定阈值T＝[168/6]＝22，或者全局最优相似度达到或超过设定的相似度F_t＝0.99。

步骤七：进行精匹配。在上述的粗匹配中，得到精匹配单元的数目为27个。将精匹配区域，即这27个精匹单元中的像素逐点进行匹配计算，从而得到最大的相似度值为0.995，其相对应的坐标为(101，348)。所以，从(101，348)到(149，389)的矩形区域是最佳匹配位置。

步骤八：算法结束，并输出最优结果。

实验运行结果分析：图5所给出的F_max进化过程较为平稳地趋于一个较优值，最后达到稳态收敛，这使得在粗匹配时被纳入精匹配搜索的单元都且有较高的相似度，从而提高了匹配的精准性；在精匹配时，从原本要搜索的168个单元到使用本发明的方法后只要搜索的27个单元，显然计算量大大减少了：由此可见，本发明的方法的快速性和精准性。

该方法是解决空中机器人视觉匹配问题的有效途径，可广泛应用于航空、航天、工业生产等涉及图像信息处理的领域。