一種新型圖像匹配方法在視覺導引AUV對接中的應用

邢慶龍 王小寧

(91388部隊 湛江 524022)

?

一種新型圖像匹配方法在視覺導引AUV對接中的應用

邢慶龍 王小寧

(91388部隊 湛江 524022)

針對視覺導引AUV對接過程圖像的變化特點,提出一種量子粒子群算法與灰度關聯分析方法相結合的圖像匹配算法。此算法結合量子粒子群并行搜索的快速性與灰色關聯分析方法較強的魯棒性,對旋轉、平移、亮度變化等不敏感,符合視覺導引AUV對接過程中對圖像匹配算法的要求。詳細介紹了基于量子粒子群優化算法的圖像匹配算法,算法以圖像灰度直方圖的灰色絕對關聯度作為適應度函數。利用水池實驗所得圖像進行測試,實驗結果顯示,所提出的圖像匹配算法準確、快速、魯棒性強,能夠很好地應用于視覺導引AUV對接。

圖像匹配; AUV對接; 視覺導引; 量子粒子群; 灰色絕對關聯度

Class Number TP391.41

1 引言

圖像匹配技術在機器視覺、目標跟蹤、飛行器巡航制導等領域得到廣泛的應用。AUV視覺導引對接中,圖像匹配是關鍵的一個部分,匹配的精度在很大程度上決定著整個系統的精度,其運算時間也占整個視覺線索求取的很大比例[1]。AUV視覺導引過程中,由于海流等環境影響AUV很難保證自身姿勢不變懸停在塢艙上方,所以會有一定艏向角或者平移等,這就使得AUV拍攝的圖像產生相應的旋轉、平移等變化,此外,水下光照條件很難保證不變,故所拍得的圖像會有亮度變化。因此,AUV視覺導引對接過程中的圖像匹配,要求算法不僅具有準確性和快速性,還要對旋轉、平移、亮度變化等不敏感。

圖像匹配算法主要分為兩類:基于灰度相關的匹配算法[2～5]和基于圖像特征的匹配算法[6]?；趫D像特征的匹配通過在待匹配圖像中提取點、線、紋理、形狀、區域等特征作為匹配基元進行匹配,計算量小,速度快,但對特征復雜的圖像匹配精度不高。在灰度圖像匹配中,以灰度值或其統計特性為匹配對象,具有代表性的是傳統的序貫相似性檢測算法(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]?；疑P聯分析的基本思想是根據序列曲線幾何形狀的相似程度來判斷其聯系是否緊密。曲線越接近,相應序列之間的關聯度就越大,反之就越小。利用灰色關聯度評價兩個序列的關聯程度,由于灰色絕對關聯度只與兩序列的幾何形狀有關,平移不改變絕對關聯度的值,而且灰色絕對關聯度不考慮其他因素,故其沒有整體性問題,即其不受環境影響。設序列:

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的像素個數?；鶞蕡D中基準子圖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