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

[關(guān)鍵詞] 分層策略 圖像匹配 序貫相似性檢測(cè)算法 自適應(yīng)遺傳算法

一、引言

機(jī)器人的視覺導(dǎo)航控制是利用CCD攝像機(jī)采集路面上的圖像信息，對(duì)當(dāng)前圖像與場(chǎng)景樣本庫(kù)中的圖像進(jìn)行匹配，以確定當(dāng)前位置，由機(jī)器人的處理器識(shí)別出路徑來控制機(jī)器人的運(yùn)動(dòng)方向。圖像匹配算法在圖像信息采集過程中起著至關(guān)重要的作用。影響圖像匹配性能的主要因素不僅包括圖像匹配測(cè)度，還與圖像匹配快速方法相關(guān)。本文主要研究在保持較高匹配正確率的條件下，通過對(duì)算法的改進(jìn)來提高圖像匹配速度，從而縮短機(jī)器人反應(yīng)時(shí)間。在圖像匹配中，采用較多的是基于灰度的匹配算法，因?yàn)榇怂惴ㄆヅ渚雀摺⒁子诠こ虒?shí)現(xiàn)且算法已相當(dāng)成熟，本文的快速算法是基于灰度匹配算法的。

二、圖像的分層搜索

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

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

1.圖像的小波分解

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

小波的選擇對(duì)圖像分解來說是一個(gè)至關(guān)重要的問題。對(duì)于同一個(gè)問題，使用不同的小波會(huì)產(chǎn)生不同的結(jié)果，因此，必須結(jié)合不同的問題選擇適當(dāng)?shù)男〔ㄗ儞Q。哈爾小波是正交小波變換中最簡(jiǎn)單的一個(gè)小波函數(shù)，它的優(yōu)點(diǎn)在于算法簡(jiǎn)單、速度快，缺點(diǎn)是其分解的低頻圖像是對(duì)上一尺度低頻圖像平均得到的，所以圖像的邊緣信息損失較為嚴(yán)重，但由于本文采用的是灰度圖像匹配，邊緣信息的損失對(duì)其影響不大，而且為了加快圖像分解速度，采用的小波變換必須盡量簡(jiǎn)單快速，因此選用的小波變換為哈爾小波。

2.改進(jìn)的序貫相似度檢測(cè)算法

序貫相似度檢測(cè)算法可以用來有效地減少單次匹配中的計(jì)算量， 但算法本身沒有抗干擾性能，在計(jì)算過程中沒有利用圖像自身的特點(diǎn)，采用窮舉搜索，存在效率極低的問題?？紤]到遺傳算法在搜索問題上的優(yōu)越性，本文將圖像匹配問題轉(zhuǎn)化為函數(shù)優(yōu)化問題，采用非遍歷尋優(yōu)的遺傳算法作為優(yōu)化問題的搜索策略，把自適應(yīng)遺傳算法（AGA）和序貫相似度檢測(cè)算法相結(jié)合，提出一種改進(jìn)的快速圖像匹配方法，以大幅減少計(jì)算量。

三、實(shí)驗(yàn)結(jié)果

將本文設(shè)計(jì)的算法應(yīng)用于移動(dòng)機(jī)器人視覺導(dǎo)航系統(tǒng)中，取得了滿意的效果?；镜膶?shí)驗(yàn)環(huán)境描述如下：實(shí)驗(yàn)場(chǎng)所為室內(nèi)，背景不太復(fù)雜。目標(biāo)物體為一個(gè)280mm×310mm×100mm的立方體紙箱，攝像機(jī)初始距離距目標(biāo)物體為4.5m，圖像采集分辨率設(shè)為160×128。移動(dòng)機(jī)器人采用的是三星S3C44B0×32位微處理器，它使用ARM7TDMI核，最高工作在72MHz，芯片中集成了8KB Cache、配置了2MB的FLASH存儲(chǔ)器，以及8MB的SDRAM存儲(chǔ)器。

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

從表中的結(jié)果可以看出，在遺傳算法迭代次數(shù)較低時(shí)，尋優(yōu)過程可能會(huì)陷入局部最優(yōu)而不能跳出，增加到150次后可獲得全局最優(yōu)解，但匹配時(shí)間有所增加。采用150次迭代的自適應(yīng)——序貫相似度檢測(cè)算法進(jìn)行匹配所需要的平均時(shí)間為單純序貫相似度檢測(cè)算法的平均匹配時(shí)間的18.5%。在小波分解的基礎(chǔ)上進(jìn)行的自適應(yīng)——序貫相似度檢測(cè)算法匹配，時(shí)間上比單純的自適應(yīng)——序貫相似度檢測(cè)算法匹配又減少了將近50%。系統(tǒng)運(yùn)行良好，跟蹤目標(biāo)沒有出現(xiàn)大的偏差，基本上始終處于圖像視野的中央位置，運(yùn)動(dòng)軌跡沒有出現(xiàn)振蕩，達(dá)到了機(jī)器人視覺導(dǎo)航的目的?？梢娀诜謱拥淖赃m應(yīng)——序貫相似度檢測(cè)算法既具有很高的匹配速度，又保持了良好的匹配正確率。

四、結(jié)語(yǔ)

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

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文