王 斐，賈曉洪，李麗娟，王忠勇

(1 中國空空導彈研究院，河南洛陽 471009；2 鄭州大學信息工程學院，鄭州 450001)

0 引言

圖像匹配是指利用已知目標圖像在另一幅圖像中搜尋相似目標區(qū)域的過程，又稱模板匹配，已經(jīng)成功應(yīng)用于多個領(lǐng)域[1-2]。

傳統(tǒng)的圖像匹配算法利用遍歷式搜索策略，匹配點對多，匹配效率低。近年來，研究者將群智能優(yōu)化算法引入圖像匹配，大大減少了圖像匹配塊的數(shù)量和計算量[3-4]。群智能優(yōu)化算法是一種基于群體行為的方法，通過個體間的協(xié)同合作實現(xiàn)全局搜索，有效解決了大多數(shù)全局優(yōu)化問題，提高了匹配效果。文獻[5]利用蟻群算法對像素進行聚類，設(shè)置了初始聚類中心，將螞蟻與聚類中心的相似度作為引導函數(shù)，實現(xiàn)了快速匹配。文獻[6]針對傳統(tǒng)粒子群優(yōu)化(PSO)算法局部收斂能力不強，易出現(xiàn)早熟收斂現(xiàn)象問題，改進了速度更新公式，獲得了較好的匹配精度。

傳統(tǒng)群智能優(yōu)化算法及其改進算法，雖然可以獲得較好的匹配效果，但這些算法均存在參數(shù)較多，調(diào)節(jié)復雜，匹配精度和匹配效率有待提高的問題。樽海鞘群算法(salp swarm algorithm,SSA) 模擬了樽海鞘鏈的群體行為，是一種較新穎的群智能優(yōu)化算法。每次迭代中，領(lǐng)導者指導追隨者，以一種鏈式行為，向食物移動。移動過程中，領(lǐng)導者進行全局探索，而追隨者則充分進行局部探索，大大減少了陷入局部最優(yōu)的情況。SSA的控制參數(shù)較少且易于調(diào)節(jié)，避免了因參數(shù)調(diào)節(jié)復雜而使匹配失敗。

文中將SSA算法引入圖像匹配，將匹配問題看作組合優(yōu)化問題，通過對參數(shù)調(diào)節(jié)、匹配精度、匹配效率等進行分析，證明算法在圖像匹配中的有效性和優(yōu)越性。

1 SSA算法

1.1 算法描述

樽海鞘是一種海洋無脊椎動物，身體呈桶狀且?guī)缀跬耆该?，以水中浮游植物為食，通過吸入和噴出海水完成在水中移動。在深海中，樽海鞘以一種鏈式的群行為進行移動和覓食，這種“奇特”的群行為引起了研究者的興趣。

樽海鞘的鏈式群行為，通常個體首尾相接，形成一條“鏈”，依次跟隨進行移動。在樽海鞘鏈中，分為領(lǐng)導者和追隨者，領(lǐng)導者朝著食物移動并且指導著緊隨其后的追隨者的移動，追隨者的移動按照嚴格的“等級”制度，只受前一個樽海鞘影響。這樣的運動模式使樽海鞘鏈有很強的全局探索和局部開發(fā)能力。

Seyedali等人于2017年建立了基于樽海鞘鏈的數(shù)學模型，提出了用SSA來解決一系列優(yōu)化問題[7]。

1.2 種群初始化

設(shè)搜索空間為D×N的歐氏空間，D為空間維數(shù)，N為種群數(shù)量?？臻g中樽海鞘的位置用Xn=[Xn1,Xn2,Xn3,…,XnD]T表示，食物的位置用Fn=[Fn1,Fn2,Fn3,…,FnD]T表示，n=1,2,3,…,N。搜索空間的上界為ub=[ub1,ub2,ub3,…,ubj,…,ubD]，下界為lb=[lb1,lb2,lb3,…,lbj,…,lbD]，j=1,2,3,…,N。

XD×N=rand(D,N)·(ub-lb)+lb

(1)

1.3 領(lǐng)導者位置更新

在樽海鞘鏈移動和覓食過程中，領(lǐng)導者的位置更新表示為：

(2)

式(2)表明，領(lǐng)導者的位置更新僅與食物的位置有關(guān)。c1是優(yōu)化算法中的收斂因子，起到平衡全局探索和局部開發(fā)的作用，是SSA中最重要的控制參數(shù)。c1的表達式為：

(3)

式中：l是當前迭代次數(shù)；L是最大迭代次數(shù)。收斂因子是一個2～0的遞減函數(shù)。

1.4 追隨者位置更新

在樽海鞘鏈移動和覓食的過程中，追隨者通過前后個體間的彼此影響，呈鏈狀依次前進。它們的位移符合牛頓運動定律，追隨者的運動位移為：

(4)

考慮到在優(yōu)化算法中，t是迭代的，設(shè)迭代過程中t=1,并且v0=0。那么式(4)可以表示為：

(5)

因此，追隨者的位置表示為：

(6)

2 基于SSA算法的圖像匹配

圖像匹配過程中，有3個關(guān)鍵要素，分別是：特征提取、搜索策略和相似度量。在SSA算法圖像匹配中，用HOG特征對待匹配圖像進行特征提取，以SSA算法對待匹配圖像進行搜索，并用相關(guān)系數(shù)函數(shù)進行相似度量。

在相似度量過程中，保留每次與目標相似度值最大的候選圖像塊，直至達到終止條件。此時與目標相似度值最大的候選圖像塊便是匹配目標。

2.1 特征提取

方向梯度直方圖(histogram of oriented gradient,HOG)特征是通過計算和統(tǒng)計局部區(qū)域的梯度直方圖來構(gòu)成特征。它可以通過梯度或邊緣的方向密度很好地描述圖像中局部目標的表象和形狀。HOG特征將目標位置和方向量化為梯度的幅值和方向，對圖像的平移和旋轉(zhuǎn)運動均具有適應(yīng)性，并且對光照變化具有魯棒性。文中選擇HOG特征對目標圖像塊與樣本圖像塊進行特征提取，像素點(x,y)處的梯度幅值和梯度方向分別為m(x,y)，θ(x,y)：

(7)

(8)

式中:Gx和Gy分別是水平方向和豎直方向梯度。

特征提取中，先根據(jù)式(7)和式(8)計算目標或樣本圖像塊中每個像素的梯度幅值與方向，再將目標或樣本圖像塊均勻地劃分成多個單元細胞圖像塊(CELL)，并且將梯度方向化為9個BIIN，分別統(tǒng)計其梯度方向直方圖，得到CELL的HOG特征。將相鄰的CELL組成一個BLOCK，將BLOCK進行歸一化處理，得到BLOCK的HOG特征。

最后，統(tǒng)計BLOCK的梯度方向直方圖，得到目標或樣本圖像塊的HOG特征，此時便完成了特征提取。

2.2 相似度量

相似度量是為了測量目標圖像塊的HOG特征和候選圖像塊的HOG特征的相似程度。文中使用相關(guān)系數(shù)函數(shù)來度量兩者之間的相似程度。設(shè)目標圖像塊的HOG特征用X表示，候選圖像塊的HOG特征用Y表示，則

式(9)表示兩者的相關(guān)系數(shù)，其中：D(·)代表方差；cov(·)代表協(xié)方差；ρ(X,Y)代表相關(guān)系數(shù)。相關(guān)系數(shù)的值越大，兩者的相似程度越大；反之，則兩者的相似程度越小。

2.3 基于SSA算法的圖像匹配

將圖像匹配過程看作為一個組合優(yōu)化問題，采用SSA優(yōu)化策略完成圖像匹配任務(wù)。

首先將待匹配圖像看作是搜索空間，樽海鞘鏈中的領(lǐng)導者和追隨者在搜索空間中移動，產(chǎn)生一系列初始候選圖像塊并提取特征；

然后計算候選圖像塊與目標圖像塊的相似度值，找出相似度值最大的圖像塊并保存，且此時的樽海鞘當作搜索空間中的食物；

根據(jù)式(2)和式(6)將樽海鞘鏈進行位置更新，從而產(chǎn)生新的候選圖像塊，計算出對應(yīng)的相似度值，之后通過比較得到相似度最大的圖像塊并保存，同樣的將此時的樽海鞘與當前食物的相似度值比較，保留其最大的并作為新的食物。

當達到最大迭代次數(shù)時，完成目標匹配。

基于SSA算法的圖像匹配步驟如下：

初始化：待匹配圖像的上界ub，下界lb；迭代次數(shù)lor 停止條件；目標圖像T；利用式(1)初始化規(guī)模為N、維數(shù)為2的樽海鞘鏈群，由此產(chǎn)生N塊候選圖像塊X(i) (i=1,2,3,…,N)；

排序：fori=1:N

將群體中的樽海鞘按照R(i) 排序，相似度值大的一半視為領(lǐng)導者X1(j)(j=2,3,4,…，N/2)，另一半視為追隨者X2(k)(k=N/2+1,N/2+2,N/2+3,…,N)

end for

當前迭代次數(shù)l<最大迭代次數(shù)Lor 停止條件

fori=1:N

由式(2)得到X′1(j)，由式(6)得到X′2(k)，即得到X′(i),計算X′(i)與T的相似度R′(i) ；

ifR′(i)>FtthenFt′=R′(i) ;F′=F;

end if

end for

輸出F′

3 實驗與分析

實驗運行環(huán)境為：Intel(R)Core(TM) i5-7300HQ CPU 2.5 GHz計算機；8GB內(nèi)存；2G顯卡；操作系統(tǒng)為64位windows10；軟件平臺為：Matlab R2017b。

實驗中，選擇粒子群優(yōu)化算法(PSO)、蟻獅優(yōu)化算法(ALO)以及文中SSA算法進行對比。

為了獲得文中算法在實際圖像的匹配效果，選擇一幅大小為480像素×360像素的圖像作為原始圖像1，如圖1(a)；將原始圖像1加入高斯噪聲作為原始圖像2，如圖1(b)；選取圖中第170行，144列的點坐標作為模板圖像的左上點，且模板圖像大小為120像素×75像素，如圖1(c)。

圖1 原始圖像

為了證明SSA在圖像匹配過程中的魯棒性和匹配效果，本實驗采用原始圖像2作為待匹配圖像，如圖2(a)，分別使用3個優(yōu)化算法進行100次實驗。其中，種群規(guī)模設(shè)置為100，最大迭代次數(shù)為150。

本實驗通過平均匹配時間、正確匹配次數(shù)和匹配成功率3個指標對實驗結(jié)果進行評價。從匹配時間上看，SSA的匹配速度不是最快，但其匹配成功率和PSO一樣高，并且匹配速度較ALO只差了1.2 s,這是由于本實驗中所選參數(shù)并非是SSA的最優(yōu)參數(shù)。

圖2 匹配結(jié)果

表1 不同算法匹配實驗結(jié)果

SSA的快速匹配和高匹配精度得益于它特有的鏈式群更新模型。此模型中，追隨者依靠前后彼此首尾相接的樽海鞘的位置實現(xiàn)位置更新，并非有強隨機性，這使得樽海鞘鏈在搜索空間中搜索時很難錯過最優(yōu)位置以及陷入局部最優(yōu)。并且個體的多樣性大大加強了SSA的局部開發(fā)能力。而領(lǐng)導者在移動過程中會受到食物影響以及收斂因子作用，所以在全局探索和局部開發(fā)這兩個狀態(tài)轉(zhuǎn)換中速度非?？?，這大大加快了算法收斂速度，提高了SSA匹配速度以及匹配效果。

4 結(jié)論

針對傳統(tǒng)群智能優(yōu)化算法在圖像匹配中調(diào)節(jié)參數(shù)多、匹配效果不理想問題，利用SSA算法鏈式群更新模型優(yōu)勢，平衡了優(yōu)化算法在搜索過程中的全局探索和局部開發(fā)，提高了全局優(yōu)化能力，避免了陷入局部最優(yōu)。通過ALO和PSO以及SSA對比實驗，實驗結(jié)果驗證了SSA算法在圖像匹配中的匹配速度、匹配精度和魯棒性。