一种新型图像匹配方法在视觉导引AUV对接中的应用

邢庆龙 王小宁

(91388部队 湛江 524022)



一种新型图像匹配方法在视觉导引AUV对接中的应用

邢庆龙 王小宁

(91388部队 湛江 524022)

针对视觉导引AUV对接过程图像的变化特点,提出一种量子粒子群算法与灰度关联分析方法相结合的图像匹配算法。此算法结合量子粒子群并行搜索的快速性与灰色关联分析方法较强的鲁棒性,对旋转、平移、亮度变化等不敏感,符合视觉导引AUV对接过程中对图像匹配算法的要求。详细介绍了基于量子粒子群优化算法的图像匹配算法,算法以图像灰度直方图的灰色绝对关联度作为适应度函数。利用水池实验所得图像进行测试,实验结果显示,所提出的图像匹配算法准确、快速、鲁棒性强,能够很好地应用于视觉导引AUV对接。

图像匹配; AUV对接; 视觉导引; 量子粒子群; 灰色绝对关联度

Class Number TP391.41

1 引言

图像匹配技术在机器视觉、目标跟踪、飞行器巡航制导等领域得到广泛的应用。AUV视觉导引对接中,图像匹配是关键的一个部分,匹配的精度在很大程度上决定着整个系统的精度,其运算时间也占整个视觉线索求取的很大比例[1]。AUV视觉导引过程中,由于海流等环境影响AUV很难保证自身姿势不变悬停在坞舱上方,所以会有一定艏向角或者平移等,这就使得AUV拍摄的图像产生相应的旋转、平移等变化,此外,水下光照条件很难保证不变,故所拍得的图像会有亮度变化。因此,AUV视觉导引对接过程中的图像匹配,要求算法不仅具有准确性和快速性,还要对旋转、平移、亮度变化等不敏感。

图像匹配算法主要分为两类:基于灰度相关的匹配算法[2～5]和基于图像特征的匹配算法[6]。基于图像特征的匹配通过在待匹配图像中提取点、线、纹理、形状、区域等特征作为匹配基元进行匹配,计算量小,速度快,但对特征复杂的图像匹配精度不高。在灰度图像匹配中,以灰度值或其统计特性为匹配对象,具有代表性的是传统的序贯相似性检测算法(SSDA),其特点是匹配精度高,易于硬件实现,但速度慢,制约其实时应用。本文将量子粒子群优化算法与灰色关联分析中的灰色绝对关联度结合起来,利用量子粒子群算法比粒子群算法更快更准确的寻优能力,使粒子快速准确地逼近最优匹配位置,利用基准图和模板图的灰度直方图作为对比序列,将其灰色绝对关联度作为适应度函数,以增强算法的鲁棒性。

2 算法介绍

2.1 基本粒子群优化算法

粒子群优化(Particle Swarm Optimization,PSO)算法是文献[7]源于对鸟群捕食行为的模拟而提出的一种新型群体智能优化算法。PSO算法初始化为一群随机粒子,然后粒子们根据对个体和群体的飞行经验的综合分析来动态调整自己的速度,在解空间中进行搜索,通过迭代找到最优解[8]。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:一个是个体极值pbest,即粒子自身目前所找到的最优解;另一个是全局极值gbest,即整个种群目前找到的最优解。粒子根据如下公式[9]来更新自己的速度和位置:

(1)

2.2 量子粒子群优化算法

量子粒子群优化(QPSO)算法是受量子物理理论的启发,在粒子群优化算法基础上提出的。QPSO算法与PSO算法的思想一致,但粒子的状态在量子空间中不再用位置和速度表示,而是用波函数来描述。QPSO算法将粒子定义在由概率密度函数决定的一个量子空间内,这样能解决的问题范围就更广义[10～12],而且粒子在量子空间里,可以在整个解空间中进行搜索,因此其全局搜索性能优于标准PSO算法。

粒子的位置由波函数|ψ|(x,t)决定:

(2)

式中,Q为粒子在时刻T出现在位置(X,Y,Z)的概率,通过蒙特卡罗方法将量子状态转换成平常状态,并通过演变最终得到粒子的迭代公式。由此将粒子的速度和位置信息都归结为一个参数,算法的方程如下

(3)

p=φ*pbest+(1-φ)*gbest

(4)

(5)

式中:M为群体中所含粒子数,pi是个体当前位置,pbest为个体极值位置,gbest为全局极值位置,mbest为中值最优位置,φ和u是[0,1]上均匀分布的随机数,β是系数创造力,是QPSO算法唯一的系数,所以参数β的设置关系到算法的收敛性能。在迭代过程中,“±”是由[0,1]之间产生的随机数决定,当产生的随机数大于0.5时取“+”,其余取“-”。系数创造力β由以下公式确定,即:

(6)

式中,β1、β2分别代表参数β的初始值和终止值;Iter是当前进化代数;MIter是最大进化代数。实验表明β1=1,β2=0.5时,QPSO算法具有较好的性能。

2.3 灰色关联分析

灰色关联分析方法对样本量的多少和样本有无规律都同样适用,而且计算量小,十分方便[13]。灰色关联分析的基本思想是根据序列曲线几何形状的相似程度来判断其联系是否紧密。曲线越接近,相应序列之间的关联度就越大,反之就越小。利用灰色关联度评价两个序列的关联程度,由于灰色绝对关联度只与两序列的几何形状有关,平移不改变绝对关联度的值,而且灰色绝对关联度不考虑其他因素,故其没有整体性问题,即其不受环境影响。设序列:

Xi=(xi(1),xi(2),…,xi(n))

Xj=(xj(1),xj(2),…,xj(n))

的始点零化像分别为

令

记折线:

(xi(1)-xi(1),xi(2)-xi(1),…,xi(n)-xi(1))

为Xi-xi(1),令

对于长度相同的序列绝对关联度定义为

(7)

3 基于灰色关联量子粒子群的图像匹配方法

本文采用一种基于图像灰度特征的模板匹配算法,利用量子粒子群优化算法寻找最佳匹配点,以模板图与待匹配子图的灰度直方图序列的灰色绝对关联度为量子粒子群优化算法的适应度函数。

3.1 灰度直方图的灰色绝对关联度

灰度直方图表示图像中每个灰度级上像素的个数,是图像灰度值的重要统计特性,故可以将其作为匹配对象。将模板图的灰度直方图作为参考序列,用下式表示:

XT=(xT(0),xT(1),…,xT(i),…,xT(degT-1))

(9)

其中xT(i)表示模板图中灰度级为i的像素个数。基准图中基准子图Sij的灰度直方图作为比较序列,基准子图的灰度直方图用下式表示:

XSij=(xSij(0),xSij(1),…,xSij(i),…,xSij(degS-1))

(10)

其中degT和degS分别表示模板图和基准子图的像素级数。

本文利用模板图与待匹配子图的灰度直方图的灰色绝对关联度来衡量两幅图像的匹配程度。基本思想如下:

设参考序列XT与比较序列XSij的长度相同,均为deg,即二者具有相同的灰度级数(没有的灰度级数可看作其像素数为0),并且因为像素级数的间隔为1,故XT与XSij皆为1-时距序列,而

分别为XT与XS(i,j)的始点零化像,其中

(11)

则

(12)

(13)

(14)

利用式(7)计算灰度直方图序列的灰色绝对关联度,则参考序列与比较序列的灰色绝对关联度越大,模板图的灰度直方图与标准子图的灰度直方图的关联度就越大,两幅图匹配程度就越大,当ε0i=1时,两幅图完全匹配。

计算适应度函数算法流程:

Step 1 得到模板图像和待搜索子图的灰度直方图;

Step 2 根据两幅图像的灰度直方图,按式(9)、式(10)分别得到参考序列XT与比较序列XSij;

Step 4 通过式(7)计算XT与XSij得灰色绝对关联度ε0i,令适应度函数f=1-ε0i。

3.2 基于灰色关联量子粒子群的图像匹配方法

模板匹配是指用一个较小的图像,即模板与原始图像进行比较,以确定在源图像中是否存在与该模板相同或相似的区域。模板匹配需要用一种测度作为评价匹配程度的标准,本文利用3.1节所述的适应度函数。设T(i,j)为模板图像,大小为M×N,S(i,j)为原始图像,大小为P×Q,且有P>M,Q>N,要搜索的区域大小为(P-M+1,Q-N+1),Sij(m,n)表示以原始图像位置(i,j)为起始位置取出与模板大小相同的待搜索子图。通过计算T(i,j)与Sij(m,n)的适应度函数值得到最佳匹配位置,便可得到匹配图像。

图像匹配算法的流程:

Step 1 初始化群体,随机生成M个粒子(原始图像中的位置(i,j))。用每个粒子的适应度函数值初始化个体当前位置pi,用初始群体中适应度值最小的粒子初始化全局极值位置gbest。

Step 2 用式(3)计算群体中所有粒子的中值最优位置mbest,通过式(4)求出p,然后根据式(5)得到下一代粒子。

Step 3 根据3.1节所述适应度函数值计算方法,计算出每个粒子的适应度值,更新gbest和mbest。

Step 4 判断是否满足终止条件(到达最大迭代次数或适应度值接近0),若是,则gbest指向的粒子就是最优位置(i,j),输出最优解,算法结束;若不是,转Step 3。

算法流程图如图1所示。

图1 GPSO算法流程图

3.3 视觉导引AUV对接过程中的图像特点分析

AUV通常要自带能源在水下工作,工作时间和航行距离都有限制,这就需要回收以补充能量、读取信息和维护保障。水下对接回收方式是一种采用浮船坞型和升降平台进行水下对接回收作业的回收方式[14～15]。AUV对接实验中,用台架模拟坞舱,在台架底部安装目标光源系统,如图2所示。摄像机安装在AUV底部中心位置,目标光源系统中中心位置的心型灯源与AUV底部中心位置相对应。

图2 目标光源系统示意图

在AUV对接过程中,AUV接近坞舱时,根据视觉信息调整位姿,缓慢地向下运动,直到坐落在坞舱中,过程中AUV相对坞舱的高度变化对应图像的尺度变化;调整位姿对应图像的平移和旋转变化;关照条件变化对应图像的亮度变化。

4 仿真实验机分析

在Intel(R)TM6600 2.4 G PC MatlabR2008a环境中进行了仿真实验。实验对象选取水池实验中AUV对接过程中摄像机实际拍得的目标光源的图像作为待匹配图像。摄像机为Tritech的低照度黑白摄像机Tornado,其主要性能参数如表1所示。

表1 水下摄像机主要性能参数

1) 算法的准确性与快速性测试。任意选取一幅AUV实际拍得图像进行算法的准确性与快速性验证。原始图像大小为576×768,在该图中截取大小为148×121的代表对接台架中心位置的模板图像,如图2(a)所示。

令粒子群群体大小为40,迭代次数分别为30,40,50,取β1=1,β2=0.5。进行30次匹配实验,统计分析QPSO算法的匹配精度和平均运行时间,并与SSDA算法作对比,结果如表2所示。

表2 对于原图QPSO算法与SSDA算法的性能比较

其中,N为GPSO算法的最大迭代次数,匹配精度=正确匹配次数/匹配实验次数×100%。表2显示,QPSO算法的匹配时间随迭代次数的增加而增加,当最大迭代次数大于等于40次时匹配精度达到100%。此外,QPSO算法可以在较短时间内实现准确匹配,较SSDA算法有明显的时间优势,在准确性相同的情况下,表现出较好的快速性。图3(a)～(c)为迭代次数为40时的模板图像、原始图像及匹配结果。

图3(d)为粒子适应度函数收敛曲线,算法中全局极值位置gbest对应所有粒子中适应度函数最小的粒子位置,可以看出,当迭代次数超过30次时,粒子的最佳适应度值已经达到0,此时最佳匹配位置为(242,218),即以(242,218)为顶点的大小为148×121的待匹配子图与模板图完全吻合。

2) 算法的鲁棒性测试。迭代次数为40次,其它参数同1)中的设置,在水池实验中实际拍得的图像中选取一幅与图3(b)所示原始图像不同深度的图像,并在该图像上截取与图3(a)中模板图像同样大小的模板图像。进行30次匹配实验,匹配结果和测试数据如图4和表3所示。

图3 算法的准确性与快速性实验

图4 深度变化的模板图像与匹配结果

算法正确匹配次数匹配精度(%)匹配时间QPSO301004．0519SSDA30100259．7384

在水池实验中实际拍得的图像中选取一幅与图3(b)所示原始图像相比AUV向右移动的图像。对图4中每幅图像进行20次实验,统计分析QPSO算法的鲁棒性及准确性,并与SSDA算法进行比较,匹配结果与测试数据如图5和表4所示。

图5 由平移实拍图像变化所得图像匹配结果

图5(b)为图5(a)的匹配结果,最佳匹配位置为(125,211),由此可知平移实拍图像与图3中原始图像并不是单纯的平移,在模板图像不变的情况下,算法仍然能够准确的找到匹配位置。图5(c)为图(a)图经旋转5°所得图像的匹配结果,最佳匹配位置为(150,226)。图5(d)为图5(a)旋转5°再进行亮度变化所得图像的匹配结果,最佳匹配位置为(151,226)。结果表明,在待匹配图像依次进行平移、旋转、亮度变化等情况下,QPSO算法依然可以精确地找到最佳匹配位置,其匹配精度要远远高出SSDA算法。

表4 QPSO算法与SSDA算法的鲁棒性比较

5 结语

本文设计了一种新型图像匹配算法,该算法是基于量子粒子群算法与灰色关联方法,以水池实验得到的图像为待匹配对象测试算法的准确性、鲁棒性及快速性。结果显示,在AUV视觉导引对接过程中实际拍得的图像本身掺杂有噪声的情况下,该算法能够准确地找到最佳匹配位置,并且在AUV的动作有小变化时(即平移、旋转一定角度等)或光照环境发生微小变化时,同样可以准确地找到最佳匹配位置。

[1] Jose’ Santos-Victor, Giulio Sandini. Visual behaviors for docking[J]. Computer Vision and Image Understanding,1997,67(3):223-238.

[2] 陈沈轶,钱徽,吴铮,等.模板图像匹配中互相关的一种快速算法[J].传感技术学报,2007,20(6):1325-1329.

[3] 刘莹,曹剑中,许朝晖,等.基于灰度相关的图像匹配算法的改进[J].应用光学,2007,28(5):536-540.

[4] 李强,张钹.一种基于图像灰度的快速匹配算法[J].软件学报,2006,17(2):216-222.

[5] 鹿艳晶,马苗.基于灰色遗传算法的快速图像匹配算法[J].计算机工程与应用,2008,44(32):169-172.

[6] 刘明烁,吴铁军.一种基于关联规则的图像特征点匹配算法[J].传感技术学报,2009,22(12):1737-1741.

[7] Shamir A. How to share a secret[J]. Communications of the ACM,1979,22(11):612-613.

[8] 杨维,李歧强.粒子群优化算法综述[J].中国工程科学,2004,6(5):87-94.

[9] 黄友锐.智能优化算法及其应用[M].北京:国防工业出版社,2008:95-99.

[10] 黄天赦,叶春明,叶伟.关于多处理机调度问题的量子粒子群算法研究[J].计算机工程与应用,2009,49(19):49-51,50-69.

[11] 黄建江,须文波,孙俊,等.量子行为粒子群优化算法的布局问题研究[J].计算机应用,2006,26(12):3015-3018.

[12] 江家宝,郑尚志.基于QPSO-SA混合算法的多目标投资组合优化[J].计算机工程与应用,2008,44(14):231-234.

[13] 刘思峰,党耀国,方志耕,等.灰色系统理论及其应用[M].第三版.北京:科学出版社,2004:36-57.

[14] Jin-Yeong Park, Bong-huan Jun, Pan-mook Lee. Experiments on vision guided docking of an autonomous underwater vehicle using one camera[J]. Oean Engineering,2009(36):48-61.

[15] M. Caccia. Vision-based ROV horizontal motion control: Near-seafloor experimental results[J]. Control Engineering Practice,2007(15):703-714.

Application of An Novel Image Matching Algorithm in Vision Guided AUV Docking

XING Qinglong WANG Xiaoning

(No. 91388 Troops of PLA, Zhanjiang 524022)

Accoding to the image characters in the process of vision guided Autonomous Underwater Vehicle(AUV) docking, an image matching algirithm based on quanta particle swarm optimization and grey relational analysis is proposed. The algirithm suggested which combines the speediness of quanta particle swarm optimization and the robustness of the grey relational analysis is not sensitive to the changes including rotation,translation,brightness change and so on, so it fits the need of vision guided docking. The grey absolute correlative degree of the image gray histogram is used as fitness function, and the image matching algorithm based on quanta particle swarm optimization is introduced in detail. Using images from tank test, experimental results are presented to demonstrate that the proposed algorithm can be applied in AUV vision guided docking.

image matching, autonomous underwater vehicle docking, vision guided, quanta particle swarm optimization, grey absolute correlative degree

2015年1月4日,

2015年2月14日 作者简介:邢庆龙,男,助理工程师,研究方向:AUV吊放回收。王小宁,男,工程师,研究方向:水下结构设计。

TP391.41

10.3969/j.issn1672-9730.2015.07.018