范 旭，曹中清

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

0 引 言

圖像匹配[1-5]大致可分為特征匹配與灰度匹配兩類。特征匹配是指將圖像的特征信息進行匹配，特征信息包括點、線、面等。特征匹配計算量小，但對特征復(fù)雜，提取困難的圖像實現(xiàn)效果不理想。灰度匹配是指對圖像的像素值利用某種相似性度量如：差平方和(SSD)、差絕對值(SAD)、歸一化互相關(guān)(NCC)等?；叶绕ヅ鋵崿F(xiàn)簡單，精度高，但計算量大，運算速度慢不適合用于有較高要求的場合。

在圖像處理領(lǐng)域，智能算法常作為優(yōu)化工具被廣泛應(yīng)用。智能算法是一種模擬自然界行為的優(yōu)化算法，常通過某種準則采用迭代的方式計算最優(yōu)值。文獻[6-8]將遺傳算法、粒子群、人工峰群等智能算法引入灰度匹配法，提高圖像的匹配速度。

風驅(qū)動優(yōu)化算法是一種基于群體的全局優(yōu)化算法，具有搜索力強，收斂速度快的特點?？梢詮V泛用于解決多維、連續(xù)、離散問題等。本文利用新型風驅(qū)動優(yōu)化智能算法對圖像的匹配過程進行優(yōu)化。將灰色關(guān)聯(lián)分析與圖像的直方圖信息結(jié)合構(gòu)造風驅(qū)動優(yōu)化算法的適應(yīng)度函數(shù)，利用風驅(qū)動優(yōu)化算法迭代尋優(yōu)，快速尋找匹配位置，實現(xiàn)對圖像的快速魯棒匹配。

1 粒子群算法

粒子群算法(PSO)是一種模擬自然界鳥群捕食行為的一種智能算法。被廣泛的應(yīng)用于函數(shù)優(yōu)化，全局尋優(yōu)。設(shè)每個問題的一個解為一個粒子，衡量每個粒子的好壞的函數(shù)為適應(yīng)度函數(shù)，每個粒子根據(jù)其它粒子和自身的飛行經(jīng)驗，從全局空間中搜索最優(yōu)值。粒子群算法的計算過程如下：

首先初始化所有粒子，隨機生成初始位置、初始速度。然后根據(jù)適應(yīng)度函數(shù)計算各粒子的適應(yīng)度值。將每個粒子的適應(yīng)度值與自身優(yōu)化解比較與全體優(yōu)化解比較，記錄優(yōu)化解與最好解。重復(fù)之前的過程，直到尋優(yōu)結(jié)束。

2 人工蜂群算法

人工蜂群算法(ABC)是一種群集智能隨機優(yōu)化算法。其思想來源于對蜜蜂采蜜行為的模擬，觀察蜂、偵查蜂和采蜜蜂構(gòu)成了蜂群。優(yōu)化問題的一個可能解用蜜源位置來表示。每個蜜源的花蜜量構(gòu)成相應(yīng)的適應(yīng)度函數(shù)值。人工蜂群算法的計算過程如下：首先隨機產(chǎn)生初始蜂群，然后蜜蜂對蜜源進行搜索，采蜜蜂先對相應(yīng)的蜜源搜索，選擇適應(yīng)度值高的即蜜源量多的蜜源，全部采蜜蜂搜索完成后，將信息傳遞給觀察蜂，觀察蜂獲得信息后，按照蜜源量多被選擇概率大的規(guī)則選擇蜜源。然后觀察蜂進行領(lǐng)域搜索，選擇好的解。如果某個蜜源經(jīng)過固定循環(huán)次數(shù)后，不能被改進即該處的解要舍棄，則該蜜源處的蜜蜂變?yōu)閭刹榉洚a(chǎn)生一個新的解代替原來的解。如此循環(huán)直到達到最大迭代次數(shù)，尋找到最優(yōu)解。

3 基于灰色關(guān)聯(lián)和風驅(qū)動優(yōu)化的圖像匹配方法

3.1 灰色關(guān)聯(lián)匹配模型

灰色關(guān)聯(lián)分析是判斷數(shù)據(jù)序列之間相關(guān)度的一種方法，其根據(jù)數(shù)據(jù)序列間的發(fā)展趨勢、相似性，找出信息系統(tǒng)中各因素的影響關(guān)系。本文利用灰色關(guān)聯(lián)匹配模型來判斷匹配的相似關(guān)系，圖像的直方圖反應(yīng)了圖像像素灰度分布，即各個灰度級與對應(yīng)頻數(shù)的關(guān)系。本文將模板圖像與待匹配子圖像的直方圖信息做灰色關(guān)聯(lián)分析，判斷兩幅圖像的相似性。灰色關(guān)聯(lián)分析常包括以下步驟：確定分析數(shù)列，變量的無量綱化、計算關(guān)聯(lián)系數(shù)，計算關(guān)聯(lián)度。

灰色關(guān)聯(lián)分析的參考序列為模板圖像的直方圖信息，設(shè)為Tim,灰色關(guān)聯(lián)分析的比較序列為最佳位置處子圖像的直方圖信息，設(shè)為Sim，這兩幅圖像的灰色關(guān)聯(lián)度為

(1)

其中

(2)

(3)

(4)

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

(5)

式中：n為關(guān)聯(lián)序列長度，其取值為直方圖的灰度級，n常取值255；to(k)為參考序列Tim中的元素，si(k)為比較序列Sim中的元素。如果兩個圖的匹配度越高，灰色關(guān)聯(lián)度的值就越大，若兩個圖完全匹配則灰色關(guān)聯(lián)度的值為1。

3.2 風驅(qū)動優(yōu)化算法

風驅(qū)動算法[9-11](WDO)是一種自然啟發(fā)算法，其原理是根據(jù)空氣的壓力差促使空氣流動并且最終達到平衡。每個空氣單元達到平衡的最終位置值為目標值，將其作為最優(yōu)解，是一種新型全局優(yōu)化算法。算法將影響大氣運動的4個主要力[12,13]：摩擦力、氣壓梯度壓力、重力和科氏力帶入牛頓第二定律結(jié)合理想氣體狀態(tài)方程得出速度更新方程用于迭代尋優(yōu)。

摩擦力使空氣粒子對之前的速度信息進行 “繼承”起到認知的作用；氣壓梯度力使空氣粒子追隨自身經(jīng)過的最優(yōu)位置，起到自我認知學習的作用；重力增加了算法全局尋優(yōu)性能，可以防止空氣粒子在尋優(yōu)過程中困于邊界?？剖狭υ鰪娏怂惴ㄋ阉餍聟^(qū)域的能力，其通過將其它維度的速度加入搜索區(qū)域，促使了各個空氣粒子的信息共享。這4個力相互合作，相互制約使風驅(qū)動算法具有較強的搜索能力。

風驅(qū)動優(yōu)化的算法的原理如下。

一個由S個空氣單元，D維搜索空間組成的空氣種群可以表示為如下矩陣

(6)

空氣粒子在空氣種群空間中進行搜索，每一維度的每一個粒子均賦予一個速度值u，則所有空氣粒子的速度構(gòu)成其一個S×D的空氣粒子速度矩陣，即

(7)

其中，1≤k≤T，T為最大迭代次數(shù)。對于粒子的速度，常設(shè)定一個速度邊界，粒子的智能在速度邊界內(nèi)運動，當速度超過速度邊界時將會被約束回邊界內(nèi)?？諝鈫卧乃俣燃s束如下

(8)

在空氣單元的運動搜索中，其速度不斷不變化，同時導(dǎo)致空氣單元的位置也不斷變化。種群的中空氣粒子的位置仍然是一個S×D的矩陣

(9)

其中，1≤i≤S,1≤d≤D,1≤k≤T。本文WDO算法的適應(yīng)度函數(shù)為兩幅圖像的灰色關(guān)聯(lián)度的倒數(shù)，即適應(yīng)度(fitness)的值越小，匹配度越大，完全匹配時fitness的值為1。適應(yīng)度值的計算如式(10)所示

(10)

空氣粒子速度和位置根據(jù)方程式(11)、式(12)更新

(11)

(12)

3.3 基于灰色關(guān)聯(lián)分析與風驅(qū)動優(yōu)化算法的圖像匹配

基于灰色關(guān)聯(lián)分析與風驅(qū)動優(yōu)化算法的圖像匹配算法流程如圖1所示。

圖1 本文算法流程

主要步驟如下：

(1)初始化空氣單元數(shù)量，最大迭代次數(shù)，各參數(shù)。設(shè)風驅(qū)動空氣單元總量為N，并且產(chǎn)生初始解集xij,為了提高算法的初始搜索性能，將初始空氣粒子均勻分布在搜索圖像中。將搜索圖像均分為n個均勻的小區(qū)域，在各區(qū)域內(nèi)隨機產(chǎn)生N/n個空氣粒子。過程如圖2所示，圖2(a)為將圖分為16塊，即n=16。圖2(b)為將N=50個粒子均勻分布到各區(qū)域當中。

圖2 空氣單元的均勻初始化

(2)根據(jù)模板直方圖信息與搜索子圖直方圖信息利用灰色關(guān)聯(lián)分析計算各個xij的適應(yīng)度值。

(3)對每個空氣單元個體分別與個體歷史最佳位置比較、總體歷史最佳位置比較，記錄歷史最佳位置、總體歷史最佳位置。

(4)根據(jù)式(11)、式(12)對速度位置更新。

(5)是否達到結(jié)束條件，如果達到則結(jié)束。否則繼續(xù)循環(huán)。

4 實驗與分析

本文在Centrino 2 PC，2.93 Ghz，Matlab 2014a環(huán)境中進行實驗，并和基于人工蜂群的快速圖像匹配算法(GABC)，基于粒子群優(yōu)化的快速圖像匹配算法(GPSO)進行比較，衡量算法性能。實驗中搜索圖像為256×256的圖像“cameramen”，以該圖坐標(80,80)為左上角，截取大小為80×80的子圖做模板圖像。實驗圖像如圖3所示，圖3(a)為搜索圖像，圖3(b)為模板圖像。

圖3 實驗圖像

風驅(qū)動優(yōu)化算法的參數(shù)設(shè)置如下：空氣單元數(shù)量為50，RT的值為3，g的值為0.3，c的值為0.42，α的值為0.4，最大迭代次數(shù)k為50，最大速度vmax為5。粒子群算法的參數(shù)設(shè)置為：種群數(shù)量為50，c1=2，c2=2，最大速度vmax為5，最大迭代次數(shù)為50。人工蜂群算法的參數(shù)設(shè)置為：蜂群大小為50，最大循環(huán)迭代數(shù)為50，分別進行25次實驗，實驗結(jié)果如表1和圖4，圖5所示。圖4為無噪聲情況下GWDO的實驗結(jié)果，圖5為各算法的適應(yīng)度函數(shù)曲線。表1為無噪聲情況下的實驗數(shù)據(jù)。

表1 無噪聲情況下的實驗數(shù)據(jù)

圖4 無噪聲情況下GWDO的實驗結(jié)果

圖5 適應(yīng)度曲線

從表1中可以看出，這3種算法在無噪聲情況下的實驗結(jié)果均比較好，3種算法的匹配精度都為100%，但是從表1中可以看出GPSO算法的平均運行時間最慢為2.02 s，GABC算法的平均運行時間次之為1.89 s，GWDO算法的收斂速度更快，平均運行時間最短為1.56 s。

從圖5中的適應(yīng)度曲線來看，GPSO算法達到收斂的最小迭代步數(shù)約為43步，GABC算法達到收斂的最小迭代步數(shù)約為20步，GWDO算法達到收斂的最小迭代步數(shù)約為12步，可以看出GWDO算法的收斂速度最快。因此在無噪聲情況GWDO算法收斂速度具有明顯的優(yōu)勢。

為了驗證算法的抗噪性，將搜索圖像加入強度為0.08的椒鹽噪聲，實驗的匹配結(jié)果如圖6和表2所示。

圖6 加噪聲后的GWDO匹配結(jié)果

算法實驗次數(shù)最大迭代次數(shù)匹配精度/%平均運行時間/sGPSO2550883.22GABC25501002.29GWDO25501002.06

由圖6可以看出，在加入噪聲后，GWDO算法仍然能在噪聲圖像中找到正確的匹配位置，其匹配效果仍然較好。從表2中可以看出，加入噪聲后，GPSO算法匹配結(jié)果開始出現(xiàn)一定的誤差，25次實驗中，有3次出現(xiàn)誤匹配，匹配精度約為88%。而GABC算法與GWDO算法的匹配精度仍然較高，25次實驗中均正確匹配，匹配精度為100%。從平均運行時間來看，3種算法的平均運行時間相比無噪聲情況下的平均運行時間都有所增加。這是由于噪聲的加入，使算法的搜索時間變長，收斂速度變慢。在噪聲情況下，GPSO算法的平均運行時間為3.22 s，GABC的平均運行時間為2.29 s，GWDO的平均運行時間為2.06 s。可見GWDO算法的平均運行時間最短。由此可見，GWDO算法相對GPSO算法與GABC算法在速度和抗噪上均具有優(yōu)勢。

5 結(jié)束語

本文成功的將風驅(qū)動優(yōu)化算法與灰色關(guān)聯(lián)分析結(jié)合，提出了一種圖像匹配算法，該算法空氣單元位置矢量為圖像的坐標，適應(yīng)度值為當前搜索位置子圖像與模板圖像的直方圖信息的灰色關(guān)聯(lián)度。經(jīng)過迭代計算找到匹配位置。經(jīng)過實驗分析可知，GWDO算法在無噪聲情況下的收斂速度均優(yōu)于GPSO算法與GABC算法，收斂速度具有明顯的優(yōu)勢。在噪聲情況下GWDO算法收斂速度明顯優(yōu)于其它兩種算法，且GWDO算法的抗噪性明顯優(yōu)于GPSO算法，具有抗噪性強的優(yōu)點。實驗結(jié)果表明GWDO算法具有收斂速度快，匹配精度高，魯棒性強的優(yōu)點，可以用于圖像的匹配。