基于分層策略的機器人視覺導航

[摘 要] 本文針對機器人視覺導航系統中彩色圖像匹配的特點，對序貫相似性檢測算法進行了改進，引入自適應遺傳算法，同時，采用了粗——精匹配相結合的分層搜索策略。改進后的算法，在不失匹配精度條件下，可提高圖像匹配速度，從而滿足機器人視覺導航的實時性要求，同時具有較好的魯棒性。

[關鍵詞] 分層策略 圖像匹配 序貫相似性檢測算法 自適應遺傳算法

一、引言

機器人的視覺導航控制是利用CCD攝像機采集路面上的圖像信息，對當前圖像與場景樣本庫中的圖像進行匹配，以確定當前位置，由機器人的處理器識別出路徑來控制機器人的運動方向。圖像匹配算法在圖像信息采集過程中起著至關重要的作用。影響圖像匹配性能的主要因素不僅包括圖像匹配測度，還與圖像匹配快速方法相關。本文主要研究在保持較高匹配正確率的條件下，通過對算法的改進來提高圖像匹配速度，從而縮短機器人反應時間。在圖像匹配中，采用較多的是基于灰度的匹配算法，因為此算法匹配精度高、易于工程實現且算法已相當成熟，本文的快速算法是基于灰度匹配算法的。

二、圖像的分層搜索

在保證圖像匹配精度的基礎上，減少數據處理的運算量，滿足系統實時性要求，是圖像匹配算法首先要解決的問題。分層搜索的過程是一個由粗到精的搜索過程，它的目的是減小搜索空間，進一步加快圖像的匹配速度。分層的方法有很多種，本文設計了一種分層搜索算法。

把圖像進行多分辨率分層處理，得到分辨率比較低和維數較小的圖像。首先在分辨率較低、維數較小的圖像上進行粗匹配，得到粗匹配點；然后返回到較高分辨率圖像，在粗匹配點的鄰域內進行進一步的精匹配，從而得到精匹配點。此過程可反復進行，直到滿足系統設計精度為止。具體分層采用小波分解的方法得到一組不同分辨率的圖像。本文先用小波多分辨率理論對圖像進行分層預處理，然后在低分辨率圖像上采用改進的序貫相似度檢測算法（SSDA）進行粗匹配，得到粗匹配點后，在原始圖像上對應粗匹配點的鄰域內，采用平均絕對差算法(MAD)進行精匹配。

1.圖像的小波分解

Mallat于1987年提出多分辨率理論，在泛函分析的框架下，統一了各種具體小波的構造方法，給出了構造正交小波基的一般方法和與FFT相對應的快速小波算法，并將它應用于圖像分解和重建，成為小波理論與應用上的一個突破性進展。

小波的選擇對圖像分解來說是一個至關重要的問題。對于同一個問題，使用不同的小波會產生不同的結果，因此，必須結合不同的問題選擇適當的小波變換。哈爾小波是正交小波變換中最簡單的一個小波函數，它的優點在于算法簡單、速度快，缺點是其分解的低頻圖像是對上一尺度低頻圖像平均得到的，所以圖像的邊緣信息損失較為嚴重，但由于本文采用的是灰度圖像匹配，邊緣信息的損失對其影響不大，而且為了加快圖像分解速度，采用的小波變換必須盡量簡單快速，因此選用的小波變換為哈爾小波。

2.改進的序貫相似度檢測算法

序貫相似度檢測算法可以用來有效地減少單次匹配中的計算量， 但算法本身沒有抗干擾性能，在計算過程中沒有利用圖像自身的特點，采用窮舉搜索，存在效率極低的問題。考慮到遺傳算法在搜索問題上的優越性，本文將圖像匹配問題轉化為函數優化問題，采用非遍歷尋優的遺傳算法作為優化問題的搜索策略，把自適應遺傳算法（AGA）和序貫相似度檢測算法相結合，提出一種改進的快速圖像匹配方法，以大幅減少計算量。

三、實驗結果

將本文設計的算法應用于移動機器人視覺導航系統中，取得了滿意的效果。基本的實驗環境描述如下：實驗場所為室內，背景不太復雜。目標物體為一個280mm×310mm×100mm的立方體紙箱，攝像機初始距離距目標物體為4.5m，圖像采集分辨率設為160×128。移動機器人采用的是三星S3C44B0×32位微處理器，它使用ARM7TDMI核，最高工作在72MHz，芯片中集成了8KB Cache、配置了2MB的FLASH存儲器，以及8MB的SDRAM存儲器。

對序貫相似度檢測算法與自適應——序貫相似度檢測算法分別進行50次實驗，其中自適應——序貫相似度檢測算法的遺傳算法群體規模為50，迭代次數為50次和150次；在此實驗基礎上，先用小波變換對圖像進行兩級分解，然后在1級圖像上采用自適應——序貫相似度檢測算法進行匹配，選取最后一代適應度值最高的5個位置，把它們映射到原始圖像基準圖上，在這5個位置的5×5領域內采用MAD 進行精匹配，最后獲得真正的匹配位置。自適應——序貫相似度檢測算法的迭代次數為150，實驗結果的比較見下表。

從表中的結果可以看出，在遺傳算法迭代次數較低時，尋優過程可能會陷入局部最優而不能跳出，增加到150次后可獲得全局最優解，但匹配時間有所增加。采用150次迭代的自適應——序貫相似度檢測算法進行匹配所需要的平均時間為單純序貫相似度檢測算法的平均匹配時間的18.5%。在小波分解的基礎上進行的自適應——序貫相似度檢測算法匹配，時間上比單純的自適應——序貫相似度檢測算法匹配又減少了將近50%。系統運行良好，跟蹤目標沒有出現大的偏差，基本上始終處于圖像視野的中央位置，運動軌跡沒有出現振蕩，達到了機器人視覺導航的目的。可見基于分層的自適應——序貫相似度檢測算法既具有很高的匹配速度，又保持了良好的匹配正確率。

四、結語

本文設計的算法充分利用了彩色圖像的特征，對傳統的圖像匹配做了改進，在圖像匹配的過程中引入遺傳算法，提高了機器人圖像匹配的速度。同時該算法具有很強的實時性和魯棒性，并能夠應用于嵌入式系統這樣的實時環境中，有效地縮短了機器人反應時間。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文