基于樽海鞘群算法的图像匹配方法

王斐; 贾晓洪; 李丽娟; 王忠勇

doi:10.15892/j.cnki.djzdxb.2019.05.026

弹箭与制导学报 >

2019 , Vol. 39 >Issue 5: 111 - 114

DOI: https://doi.org/10.15892/j.cnki.djzdxb.2019.05.026

基于樽海鞘群算法的图像匹配方法

王斐 ¹ ,
贾晓洪 ¹ ,
李丽娟 ¹ ,
王忠勇 ²

展开

¹ 中国空空导弹研究院, 河南洛阳 471009
² 郑州大学信息工程学院, 郑州 450001

王斐(1976-),男,河南洛阳人,工程师,博士,研究方向:图像处理、信息融合、系统建模与仿真。

收稿日期: 2018-10-31

网络出版日期: 2025-05-12

基金资助

河南省自然科学基金(162300410096)

河南科技大学青年基金资助

收起

Image Matching Based on Salp Swarm Algorithm

WANG Fei ¹ ,
JIA Xiaohong ¹ ,
LI Lijuan ¹ ,
WANG Zhongyong ²

Expand

¹ China Airborne Missile Academy, Henan Luoyang 471009, China
² School of Information Engineering, Zhengzhou University, Zhengzhou 450001, China

Received date: 2018-10-31

Online published: 2025-05-12

Fold

摘要

针对传统群智能优化图像匹配算法存在参数调节多、匹配精度低等问题,文中提出一种新的樽海鞘群算法图像匹配方法。分析了樽海鞘群算法基本原理;将图像匹配过程转化为求解组合优化问题;利用HOG特征提取图像的特征块,计算相似度量,实现了目标的全局性快速稳定特征匹配。实验结果验证了匹配精度和匹配效率,证明了新方法的有效性。

关键词： 图像匹配; 方向梯度直方图; 全局最优; 群智能优化算法; 樽海鞘群算法

本文引用格式

王斐 , 贾晓洪 , 李丽娟 , 王忠勇 . 基于樽海鞘群算法的图像匹配方法[J]. 弹箭与制导学报, 2019 , 39(5) : 111 -114 . DOI: 10.15892/j.cnki.djzdxb.2019.05.026

Abstract

Traditional swarm intelligence optimization algorithms have the problems such as complex adjustment parameters and low matching precision in the image matching.A novel swarm intelligence optimization algorithm for image matching, Salp Swarm Algorithm (SSA), is introduced to overcome the shortcomings of complex adjustment parameters and low matching precision. Firstly, the fundamental principle of SSA is analyzed. Then, the image matching is transformed into combinatorial optimization problem. Finally, the feature blocks of the image are extracted with HOG feature, the similarity degree of the feature blocks are calculated. Thus, the quickly and steadily global feature matching about target block image is achieved. Simulations show that SSA has high matching precision and matching efficiency. Experimental results show that the proposed algorithm is effective.

Key words： image matching; histogram of oriented gradient; global optima; swarm intelligence optimization algorithm; salp-swarm-algorithm

0 引言

图像匹配是指利用已知目标图像在另一幅图像中搜寻相似目标区域的过程,又称模板匹配,已经成功应用于多个领域 ^[1-2]。

传统的图像匹配算法利用遍历式搜索策略,匹配点对多,匹配效率低。近年来,研究者将群智能优化算法引入图像匹配,大大减少了图像匹配块的数量和计算量^[3-4]。群智能优化算法是一种基于群体行为的方法,通过个体间的协同合作实现全局搜索,有效解决了大多数全局优化问题,提高了匹配效果。文献[5]利用蚁群算法对像素进行聚类,设置了初始聚类中心,将蚂蚁与聚类中心的相似度作为引导函数,实现了快速匹配。文献[6]针对传统粒子群优化(PSO)算法局部收敛能力不强,易出现早熟收敛现象问题,改进了速度更新公式,获得了较好的匹配精度。

传统群智能优化算法及其改进算法,虽然可以获得较好的匹配效果,但这些算法均存在参数较多,调节复杂,匹配精度和匹配效率有待提高的问题。樽海鞘群算法(salp swarm algorithm, SSA) 模拟了樽海鞘链的群体行为,是一种较新颖的群智能优化算法。每次迭代中,领导者指导追随者,以一种链式行为,向食物移动。移动过程中,领导者进行全局探索,而追随者则充分进行局部探索,大大减少了陷入局部最优的情况。SSA的控制参数较少且易于调节,避免了因参数调节复杂而使匹配失败。

文中将SSA算法引入图像匹配,将匹配问题看作组合优化问题,通过对参数调节、匹配精度、匹配效率等进行分析,证明算法在图像匹配中的有效性和优越性。

1 SSA算法

1.1 算法描述

樽海鞘是一种海洋无脊椎动物,身体呈桶状且几乎完全透明,以水中浮游植物为食,通过吸入和喷出海水完成在水中移动。在深海中,樽海鞘以一种链式的群行为进行移动和觅食,这种“奇特”的群行为引起了研究者的兴趣。

樽海鞘的链式群行为,通常个体首尾相接,形成一条“链”,依次跟随进行移动。在樽海鞘链中,分为领导者和追随者,领导者朝着食物移动并且指导着紧随其后的追随者的移动,追随者的移动按照严格的“等级”制度,只受前一个樽海鞘影响。这样的运动模式使樽海鞘链有很强的全局探索和局部开发能力。

Seyedali等人于2017年建立了基于樽海鞘链的数学模型,提出了用SSA来解决一系列优化问题^[7]。

1.2 种群初始化

设搜索空间为D×N的欧氏空间,D为空间维数,N为种群数量。空间中樽海鞘的位置用X_n=

[X n 1, X n 2, X n 3, …, X n D] T

表示,食物的位置用F_n=

[F n 1, F n 2, F n 3, …, F n D] T

表示,n=1,2,3,…,N。搜索空间的上界为ub=[ub₁,ub₂,ub₃,…,ub_j,…,ub_D],下界为lb=[lb₁,lb₂,lb₃,…,lb_j,…,lb_D],j=1,2,3,…,N。

(1)X_D_×_N=rand(D,N)·(ub-lb)+lb

种群中领导者用

X d 1

表示,追随者用

X d i

表示,i=2,3,4,…,N;d=1,2,3,…D。

1.3 领导者位置更新

在樽海鞘链移动和觅食过程中,领导者的位置更新表示为:

(2)

X d 1 = F d + c 1 u b − lb c 2 + lb, c 3 ≥ 0.5 F d − c 1 u b − lb c 2 + lb, c 3 < 0.5

式中:

X d 1

和F_d分别是第d维中第一个樽海鞘(领导者)的位置和食物的位置;ub和lb分别是对应的上下界。其中,c₁、c₂、c₃是控制参数。

式(2)表明,领导者的位置更新仅与食物的位置有关。c₁是优化算法中的收敛因子,起到平衡全局探索和局部开发的作用,是SSA中最重要的控制参数。c₁的表达式为:

(3)

c 1 = 2 e − 4 l L 2

式中:l是当前迭代次数;L是最大迭代次数。收敛因子是一个2~0的递减函数。

控制参数c₂、c₃是[0,1]的随机数,用来增强

X d 1

的随机性,提高链群的全局搜索和个体多样性。

1.4 追随者位置更新

在樽海鞘链移动和觅食的过程中,追随者通过前后个体间的彼此影响,呈链状依次前进。它们的位移符合牛顿运动定律,追随者的运动位移为:

(4)

X = 12 a t 2 + v 0 t

式中:t是时间;a是加速度,计算公式为a=(v_final-v₀)/t;v₀是初始速度,并且

v f i n a l = (X d i − X d (i − 1)) / t

。

考虑到在优化算法中,t是迭代的,设迭代过程中t=1,并且v₀=0。那么式(4)可以表示为:

(5)

X = X d i − X d i − 1 2

式中:i≥2;

X d i

和

X d i - 1

分别是第d维中彼此紧连的两个樽海鞘的位置。

因此,追随者的位置表示为:

(6)

X d i' = X d i + X d i − 1 2

式中,

X d i'

和

X d i

分别是第d维中更新后的追随者的位置和更新前追随者的位置。

2 基于SSA算法的图像匹配

图像匹配过程中,有3个关键要素,分别是:特征提取、搜索策略和相似度量。在SSA算法图像匹配中,用HOG特征对待匹配图像进行特征提取,以SSA算法对待匹配图像进行搜索,并用相关系数函数进行相似度量。

在相似度量过程中,保留每次与目标相似度值最大的候选图像块,直至达到终止条件。此时与目标相似度值最大的候选图像块便是匹配目标。

2.1 特征提取

方向梯度直方图(histogram of oriented gradient, HOG)特征是通过计算和统计局部区域的梯度直方图来构成特征。它可以通过梯度或边缘的方向密度很好地描述图像中局部目标的表象和形状。HOG特征将目标位置和方向量化为梯度的幅值和方向,对图像的平移和旋转运动均具有适应性,并且对光照变化具有鲁棒性。文中选择HOG特征对目标图像块与样本图像块进行特征提取,像素点(x,y)处的梯度幅值和梯度方向分别为m(x,y),θ(x,y):

(7)

m x, y = G x 2 + G y 2

(8)

θ x, y = arctan G x G y

式中:G_x和G_y分别是水平方向和竖直方向梯度。

特征提取中,先根据式(7)和式(8)计算目标或样本图像块中每个像素的梯度幅值与方向,再将目标或样本图像块均匀地划分成多个单元细胞图像块(CELL),并且将梯度方向化为9个BIIN,分别统计其梯度方向直方图,得到CELL的HOG特征。将相邻的CELL组成一个BLOCK,将BLOCK进行归一化处理,得到BLOCK的HOG特征。

最后,统计BLOCK的梯度方向直方图,得到目标或样本图像块的HOG特征,此时便完成了特征提取。

2.2 相似度量

相似度量是为了测量目标图像块的HOG特征和候选图像块的HOG特征的相似程度。文中使用相关系数函数来度量两者之间的相似程度。设目标图像块的HOG特征用X表示,候选图像块的HOG特征用Y表示,则

(9)

ρ X, Y = c o v X, Y D X · D Y

式(9)表示两者的相关系数,其中:D(·)代表方差;cov(·)代表协方差;ρ(X,Y)代表相关系数。相关系数的值越大,两者的相似程度越大;反之,则两者的相似程度越小。

2.3 基于SSA算法的图像匹配

将图像匹配过程看作为一个组合优化问题,采用SSA优化策略完成图像匹配任务。

首先将待匹配图像看作是搜索空间,樽海鞘链中的领导者和追随者在搜索空间中移动,产生一系列初始候选图像块并提取特征;

然后计算候选图像块与目标图像块的相似度值,找出相似度值最大的图像块并保存,且此时的樽海鞘当作搜索空间中的食物;

根据式(2)和式(6)将樽海鞘链进行位置更新,从而产生新的候选图像块,计算出对应的相似度值,之后通过比较得到相似度最大的图像块并保存,同样的将此时的樽海鞘与当前食物的相似度值比较,保留其最大的并作为新的食物。

当达到最大迭代次数时,完成目标匹配。

基于SSA算法的图像匹配步骤如下:

初始化:待匹配图像的上界ub,下界lb;迭代次数l or 停止条件;目标图像T;利用式(1)初始化规模为N、维数为2的樽海鞘链群,由此产生N块候选图像块X(i) (i=1,2,3,…,N);

排序:for i=1:N

将群体中的樽海鞘按照R(i) 排序,相似度值大的一半视为领导者X₁(j)(j=2,3,4,…,N/2),另一半视为追随者X₂(k)(k=N/2+1,N/2+2,N/2+3,…,N)

end for

当前迭代次数l< 最大迭代次数L or 停止条件

for i=1:N

由式(2)得到X'₁(j),由式(6)得到X'₂(k),即得到X'(i),计算X'(i)与T的相似度R'(i) ;

if R'(i)>Ft then Ft'=R'(i) ; F'=F;

end if

end for

输出F'

3 实验与分析

实验运行环境为:Intel(R)Core(TM) i5-7300HQ CPU 2.5 GHz计算机;8GB内存;2G显卡;操作系统为64位windows10;软件平台为:Matlab R2017b。

实验中,选择粒子群优化算法(PSO)、蚁狮优化算法(ALO)以及文中SSA算法进行对比。

为了获得文中算法在实际图像的匹配效果,选择一幅大小为480像素×360像素的图像作为原始图像1,如图1(a);将原始图像1加入高斯噪声作为原始图像2,如图1(b);选取图中第170行,144列的点坐标作为模板图像的左上点,且模板图像大小为120像素×75像素,如图1(c)。

显示原图|下载原图ZIP|生成PPT

图1 原始图像

为了证明SSA在图像匹配过程中的鲁棒性和匹配效果,本实验采用原始图像2作为待匹配图像,如图2(a),分别使用3个优化算法进行100次实验。其中,种群规模设置为100,最大迭代次数为150。

显示原图|下载原图ZIP|生成PPT

图2 匹配结果

本实验通过平均匹配时间、正确匹配次数和匹配成功率3个指标对实验结果进行评价。从匹配时间上看,SSA的匹配速度不是最快,但其匹配成功率和PSO一样高,并且匹配速度较ALO只差了1.2 s,这是由于本实验中所选参数并非是SSA的最优参数。

表1 不同算法匹配实验结果

算法名称	平均匹配时间/s		匹配成功概率/%
SSA	5.82	100	100
ALO	4.62	83	83
PSO	6.24	100	100

SSA的快速匹配和高匹配精度得益于它特有的链式群更新模型。此模型中,追随者依靠前后彼此首尾相接的樽海鞘的位置实现位置更新,并非有强随机性,这使得樽海鞘链在搜索空间中搜索时很难错过最优位置以及陷入局部最优。并且个体的多样性大大加强了SSA的局部开发能力。而领导者在移动过程中会受到食物影响以及收敛因子作用,所以在全局探索和局部开发这两个状态转换中速度非常快,这大大加快了算法收敛速度,提高了SSA匹配速度以及匹配效果。

4 结论

针对传统群智能优化算法在图像匹配中调节参数多、匹配效果不理想问题,利用SSA算法链式群更新模型优势,平衡了优化算法在搜索过程中的全局探索和局部开发,提高了全局优化能力,避免了陷入局部最优。通过ALO和PSO以及SSA对比实验,实验结果验证了SSA算法在图像匹配中的匹配速度、匹配精度和鲁棒性。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序

[1]	刘炳国, 陈力, 刘国栋. 基于改进SIFT与互信息的异源图像匹配[J]. 航空兵器, 2014(5):15-18.

[2]	何国经, 刘德连, 张建奇. CUDA架构下高光谱图像光谱匹配的快速实现[J]. 航空兵器, 2011(4):3-6.

[3]	张焕龙, 张秀娇, 贺振东, 等. 基于布谷鸟搜索的图像匹配方法研究[J]. 郑州大学学报(理学版), 2017, 49(4):51-56.

[4]	张焕龙, 郑卫东, 舒云星. 基于增量式互信息的图像快速匹配方法[J]. 弹箭与制导学报, 2015, 35(1):135-138. DOI

[5]	石鸿雁, 贝肇宇. 基于蚁群算法的图像匹配方法[C]《控制与决策》编辑委员会.// 2009中国控制与决策会议论文集(3). 沈阳: 《控制与决策》编辑部, 2009:428-431.

[6]	朱进进. 改进粒子群优化算法的图像匹配[D]. 河南新乡: 河南师范大学, 2017.

[7]	MIRJALILI S, GANDOMI A H, MIRJALILI S Z, et al. Salp swarm algorithm: a bio-inspired optimizer for engineering design problems[J]. Advances in Engineering Software, 2017, 114:163-191.

Options

文章导航

模态框（Modal）标题

摘要