基于灰色關(guān)聯(lián)與風(fēng)驅(qū)動(dòng)優(yōu)化的圖像匹配算法

范 旭，曹中清

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

0 引 言

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

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

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

1 粒子群算法

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

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

2 人工蜂群算法

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

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

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

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

灰色關(guān)聯(lián)分析的參考序列為模板圖像的直方圖信息，設(shè)為T(mén)im,灰色關(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)序列長(zhǎng)度，其取值為直方圖的灰度級(jí)，n常取值255；to(k)為參考序列Tim中的元素，si(k)為比較序列Sim中的元素。如果兩個(gè)圖的匹配度越高，灰色關(guān)聯(lián)度的值就越大，若兩個(gè)圖完全匹配則灰色關(guān)聯(lián)度的值為1。

3.2 風(fēng)驅(qū)動(dòng)優(yōu)化算法

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

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

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

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

(11)

(12)

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

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

圖1 本文算法流程

主要步驟如下：

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析

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

圖3 實(shí)驗(yàn)圖像

風(fēng)驅(qū)動(dòng)優(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，分別進(jìn)行25次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1和圖4，圖5所示。圖4為無(wú)噪聲情況下GWDO的實(shí)驗(yàn)結(jié)果，圖5為各算法的適應(yīng)度函數(shù)曲線。表1為無(wú)噪聲情況下的實(shí)驗(yàn)數(shù)據(jù)。

表1 無(wú)噪聲情況下的實(shí)驗(yàn)數(shù)據(jù)

圖4 無(wú)噪聲情況下GWDO的實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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