李新德 金曉彬 張秀龍 戴先中

(東南大學(xué)復(fù)雜工程系統(tǒng)測量與控制教育部重點(diǎn)實(shí)驗(yàn)室，南京210096)

計(jì)算機(jī)視覺具有信息豐富、智能化水平高等優(yōu)點(diǎn)，因此廣泛應(yīng)用于移動機(jī)器人的自主導(dǎo)航中.視覺導(dǎo)航中通常采用視覺傳感器來檢測環(huán)境中的一些顯著路標(biāo)，實(shí)現(xiàn)快速自定位.通過路標(biāo)將全局路線分解為片段，不斷地探測路標(biāo)來完成導(dǎo)航［1］.

根據(jù)路標(biāo)的不同可以分為人工路標(biāo)和自然路標(biāo).自然路標(biāo)是早已在環(huán)境中存在并且除了用于導(dǎo)航之外還有一定功能的目標(biāo)或特征;人工路標(biāo)是為機(jī)器人導(dǎo)航而專門設(shè)計(jì)的目標(biāo)或標(biāo)記，如文獻(xiàn)［2-4］中采用了各種具有特殊顏色或者特殊標(biāo)記的人工路標(biāo).人工路標(biāo)導(dǎo)航不易受到環(huán)境干擾而且容易實(shí)現(xiàn)，但是破壞了環(huán)境的協(xié)調(diào)性，且每當(dāng)室內(nèi)環(huán)境發(fā)生變化時，就必須調(diào)整人工路標(biāo)的位置，難以適應(yīng)現(xiàn)代個性化的家庭居住需求.

自然路標(biāo)不改變工作環(huán)境，也不需要額外的設(shè)施或額外信息，受遮擋和噪聲干擾小，因而受到越來越多的關(guān)注.文獻(xiàn)［5-7］采用Hough 變換等方法識別門牌、海報、燈飾、室外建筑物等線條狀的自然路標(biāo)，并取得了一定的效果.蔡自興等［8］提出了一種角點(diǎn)聚類的自然路標(biāo)局部特征模板，利用模板的不變性特征識別自然路標(biāo).該方法對于角點(diǎn)較多的自然路標(biāo)(如柜子)具有較好的識別效果，但是在復(fù)雜環(huán)境下角點(diǎn)數(shù)量龐大，匹配計(jì)算量急劇增長［8］，難以滿足實(shí)時性要求.文獻(xiàn)［9］提出了一種采用SURF 特征的動態(tài)環(huán)境導(dǎo)航算法.該方法需要提前準(zhǔn)備自然路標(biāo)在真實(shí)環(huán)境下的多幅圖像.然而在未知環(huán)境下，提前拍攝自然路標(biāo)的圖像并不可行.

本文模仿人類在未知環(huán)境下的導(dǎo)航方式，采用室內(nèi)常見物體為自然路標(biāo)，結(jié)合BoW 物體識別模型和交互式的手繪地圖，指導(dǎo)機(jī)器人尋找環(huán)境中的關(guān)鍵物體，輔助機(jī)器人快速、高效地到達(dá)目的地.

1 Bag of Words 模型

Csurka 等［10］首先將“自然語言處理”領(lǐng)域的BoW(bag of words)模型［11］引入圖像分類領(lǐng)域，將圖像類比為由若干單詞組成的文檔，每幅圖像表示為視覺單詞頻率直方圖，取得較好的分類效果.BoW 模型的關(guān)鍵在于提取圖像的視覺單詞描述，本文采用SIFT 算法提取圖像中的視覺單詞［12］.通過SIFT 特征檢測后，每幅圖像都由一個128 維特征向量集合描述.采用K 均值聚類，得到K 個聚類中心作為視覺單詞，視覺單詞構(gòu)成視覺詞匯表.由于聚類的不精確性，以及詞匯表大小的隨意性，視覺單詞往往具有一定程度上的冗余.

受文檔分類的啟發(fā)，對每幅圖像中的每個特征向量計(jì)算N 個最近鄰視覺單詞，然后采用下式度量第k 個視覺單詞的質(zhì)量:

式中，Mi表示與視覺單詞tk第i 接近的特征向量數(shù);s(fj，tk)表示特征向量fj與視覺單詞tk之間的相似度，本文中采用歐氏距離.對每個視覺單詞計(jì)算其質(zhì)量，如果滿足

則保留，否則舍去.式中，h 為視覺單詞的質(zhì)量閾值.為了滿足實(shí)時性要求，同時保證識別率，本文取N=3，h=0.8.

為了抽象圖像的BoW 表示，需要將SIFT 特征向量量化為視覺詞匯表中的視覺單詞描述.一般采用最近鄰歸類，將128 維SIFT 特征量化為視覺單詞.然后統(tǒng)計(jì)每幅圖像中視覺單詞出現(xiàn)頻率，構(gòu)造視覺單詞直方圖.

支持向量機(jī)具有小樣本下推廣能力強(qiáng)的優(yōu)勢.針對多分類問題可以對每一類物體構(gòu)建“一對多”支持向量機(jī).通過離線訓(xùn)練的方式，為室內(nèi)常見物體建立基于BoW 模型的線性支持向量機(jī)，將結(jié)果保存為自然路標(biāo)數(shù)據(jù)庫.

2 手繪地圖的表示

本文提出一種與“人類問路”過程中的語義地圖比較類似的手繪地圖，以指導(dǎo)機(jī)器人在局部未知的環(huán)境下快速導(dǎo)航.

假設(shè)實(shí)際環(huán)境地圖為Mr={L，B，C，T，R}，其中，L 為導(dǎo)航設(shè)置的自然路標(biāo);B 為不適宜作為自然路標(biāo)的障礙物;C 為導(dǎo)航環(huán)境中的動態(tài)障礙;T為導(dǎo)航目的地;R 為機(jī)器人的初始位姿.

手繪地圖如圖1所示，其中標(biāo)識了導(dǎo)航過程中可能發(fā)現(xiàn)的“自然路標(biāo)”的位置、名稱和參考路徑.手繪地圖表示為其中，表示自然路標(biāo)L 在手繪地圖中的概略位置.包含路徑的起始點(diǎn)S、終點(diǎn)D 以及手繪路徑.手繪路徑并不是機(jī)器人的導(dǎo)航路徑，而只是指引移動機(jī)器人沿該路徑的大致行走趨勢.手繪路徑具有隨意性、靈活性和不精確性.表示機(jī)器人的初始概略位姿.手繪地圖HM與實(shí)際環(huán)境地圖之間存在“松散”的映射關(guān)系.這是因?yàn)閯討B(tài)環(huán)境的精確大小無法快速獲知.另一方面，手繪路徑對機(jī)器人起到的只是指引作用，因此機(jī)器人沒有必要完全按照指定路徑運(yùn)行.本文將手繪路徑簡化為折線，機(jī)器人在每段線段間采用直線前進(jìn)，可以有效地避免頻繁旋轉(zhuǎn)所帶來的累積誤差.

圖1 手繪地圖

如圖2中大圓圈標(biāo)識，通過計(jì)算手繪路徑每個點(diǎn)的曲率以及自然路標(biāo)的位置影響，可以從手繪地圖中提取出l +1 個關(guān)鍵引導(dǎo)點(diǎn)，將一條手繪地圖路徑劃分為l 個片段，每一段表示為從節(jié)點(diǎn)ni－1到ni的直線，機(jī)器人初始位置為r0≈n0，終點(diǎn)為nl.因此全局的導(dǎo)航過程就可以簡化為每兩個關(guān)鍵引導(dǎo)點(diǎn)間的導(dǎo)航.

圖2 關(guān)鍵引導(dǎo)點(diǎn)的提取

3 基于自然路標(biāo)的視覺導(dǎo)航方法

3.1 自然路標(biāo)篩選

如圖1所示的手繪地圖中，關(guān)鍵引導(dǎo)點(diǎn)附近可能有多個候選自然路標(biāo).然而每個時刻只需要選擇其中一個作為自然路標(biāo)就足以幫助移動機(jī)器人自定位.從候選的自然路標(biāo)中篩選一個最容易被機(jī)器人搜索到的目標(biāo)，不但減輕了機(jī)器人視覺觀察的負(fù)擔(dān)，而且提高了機(jī)器人的導(dǎo)航速度.

如圖3所示，ni－1和ni分別表示當(dāng)前階段的起點(diǎn)和終點(diǎn).假設(shè)機(jī)器人已經(jīng)處在ni－1并且朝向的方向，則節(jié)點(diǎn)N0.5為向量的中點(diǎn).Oj(j =1，2，…，m)是與ni比較接近的m 個候選自然路標(biāo)，dj為候選自然路標(biāo)Oj與ni的物理距離，αj為的相對夾角.經(jīng)過分析候選自然路標(biāo)Oj與節(jié)點(diǎn)ni的距離和角度，選Oj作為自然路標(biāo)Li的權(quán)重函數(shù)，即

式中，f1(d)為距離約束函數(shù);f2(α)為角度約束函數(shù).由式(6)可以計(jì)算出ni附近最容易被發(fā)現(xiàn)的自然路標(biāo)Li.根據(jù)經(jīng)驗(yàn)，若F(Li)＜0.2，則認(rèn)為ni附近的候選自然路標(biāo)離ni太遠(yuǎn)或者角度太偏，機(jī)器人可以依據(jù)手繪地圖和里程計(jì)進(jìn)行慣性導(dǎo)航.若存在多個目標(biāo)都能使Fi取得最大值，則選擇這些目標(biāo)中最小的αi作為參考目標(biāo).

圖3 自然路標(biāo)的篩選

鎖定ni附近的自然路標(biāo)Li后，機(jī)器人加載自然路標(biāo)數(shù)據(jù)庫中的對應(yīng)分類器.參考手繪地圖中路徑先快速行駛至N0.5，計(jì)算自然路標(biāo)Li與之間的夾角β.調(diào)整攝像機(jī)在β 角度附近搜索自然路標(biāo)Li，一旦確認(rèn)檢測到自然路標(biāo)Li，則進(jìn)行視覺粗定位，計(jì)算機(jī)器人相對Li的位姿.

3.2 視覺導(dǎo)航粗定位

本文采用超聲波測距結(jié)合視覺信息進(jìn)行粗定位，從而獲得機(jī)器人在地圖中的相對位姿.

通過關(guān)鍵引導(dǎo)點(diǎn)的提取，可以將一條手繪地圖路徑劃分為l 個片段，每一段表示為從節(jié)點(diǎn)ni－1到ni的線段機(jī)器人起始位置為r0≈n0.手繪地圖的不精確性決定了每一段路程有一個獨(dú)立的比例尺mi，機(jī)器人需要根據(jù)間的實(shí)際行走路程更新比例尺mi+1.由下式計(jì)算路程的初始比例尺m1:

式中，d 為導(dǎo)航環(huán)境中2 點(diǎn)之間的物理距離;d′為手繪地圖中的像素距離.假設(shè)某一時刻機(jī)器人沿前進(jìn)并檢測到ni附近的自然路標(biāo)Li，此刻機(jī)器人與Li之間的粗略米制距離為

式中，s(r，Li)表示聲納測得機(jī)器人相對路標(biāo)Li的距離，機(jī)器人相對Li的方向即為當(dāng)前攝像機(jī)的旋轉(zhuǎn)角度;r 為機(jī)器人在手繪地圖中的當(dāng)前位置;ri－1為機(jī)器人到達(dá)上一個節(jié)點(diǎn)ni－1后經(jīng)過自定位獲得的位置;mi為這段路程的地圖比例尺;t 為像素距離閾值，一般取0.6.當(dāng)機(jī)器人檢測到路標(biāo)Li并且d(r，Li)＜mid′(ni，Li)時，由

計(jì)算自定位后的位置ri，并更新下一段的比例尺mi+1，即

圖4 視覺粗定位示意圖

3.3 避障導(dǎo)航

避障導(dǎo)航的目的是為了避開靜態(tài)或動態(tài)障礙，同時檢測自然路標(biāo)，避障之后，恢復(fù)原始狀態(tài).避障步驟如下:

①在機(jī)器人的直行過程中利用聲納實(shí)時檢測前方是否存在障礙物.若存在，則記錄當(dāng)前的前進(jìn)方向rθ.

②根據(jù)濾波后的聲納數(shù)據(jù)判斷機(jī)器人旋轉(zhuǎn)方向以避開障礙物.

③機(jī)器人旋轉(zhuǎn)一定角度后，根據(jù)聲納數(shù)據(jù)判斷此時其前方是否存在障礙物.若不存在，則停止旋轉(zhuǎn)并前行一小段距離，轉(zhuǎn)向④;否則，繼續(xù)轉(zhuǎn)向③.

④機(jī)器人按照避障前的運(yùn)行模式繼續(xù)運(yùn)行(如前行并調(diào)整攝像頭檢測自然路標(biāo)等)，轉(zhuǎn)向⑤.

⑤判斷機(jī)器人是否到達(dá)下一個關(guān)鍵引導(dǎo)點(diǎn)，若是，則轉(zhuǎn)向⑧;否則，轉(zhuǎn)向⑥.

⑥根據(jù)聲納信息檢測rθ方向處是否存在障礙物，如果存在障礙，則轉(zhuǎn)向⑦;否則，轉(zhuǎn)向⑨.

⑦根據(jù)聲納信息檢測機(jī)器人前方是否存在障礙物，若是，則轉(zhuǎn)向②;否則，轉(zhuǎn)向④.

⑧退出避障狀態(tài)，轉(zhuǎn)入無障礙導(dǎo)航狀態(tài)，并進(jìn)行下一階段的運(yùn)行分析.

⑨機(jī)器人轉(zhuǎn)向rθ方向，轉(zhuǎn)入無障礙導(dǎo)航狀態(tài)，并按照避障前的模式繼續(xù)運(yùn)行.

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

本文以一臺美國Pioneer3-DX 機(jī)器人為實(shí)驗(yàn)平臺.從6 個不同角度進(jìn)行導(dǎo)航實(shí)驗(yàn).

1)實(shí)驗(yàn)1 考察導(dǎo)航方法能否順利到達(dá)不同的目的地.如圖5所示環(huán)境中，假設(shè)任務(wù)1 要使機(jī)器人從0 到達(dá)6 附近，存在一條0－1－2－3－4－5－6的導(dǎo)航路徑，每個點(diǎn)附近分別有電風(fēng)扇、吊蘭、垃圾簍、椅子、吉他、雨傘可以作為路標(biāo).繪制手繪地圖，輸入起止距離約9 m.導(dǎo)航結(jié)果如圖6(a)所示，其中S，D 分別為機(jī)器人的起點(diǎn)和終點(diǎn)，改變3 次目標(biāo)區(qū)域D 的位置(分別為任務(wù)1～任務(wù)3).繪制不同的手繪地圖，實(shí)驗(yàn)結(jié)果如圖6所示.由圖可見，機(jī)器人能夠依據(jù)手繪地圖和自然路標(biāo)準(zhǔn)確地到達(dá)不同的目標(biāo)區(qū)域.部分偏差主要因?yàn)槭掷L地圖為了便捷性而犧牲了精度.另外機(jī)器人的初始位置與手繪地圖提供的起點(diǎn)偏差以及實(shí)際導(dǎo)航過程中遇到的各種障礙都會改變實(shí)際導(dǎo)航路線.

圖5 導(dǎo)航任務(wù)示意圖(單位:cm)

2)實(shí)驗(yàn)2 考察路標(biāo)的繪制偏差對導(dǎo)航的影響.改變路標(biāo)在地圖上的繪制位置，3 次實(shí)驗(yàn)結(jié)果如圖7所示.圖中6 個圓限定了自然路標(biāo)位置變動范圍，里面的3 個符號表示每次實(shí)驗(yàn)時自然路標(biāo)在手繪地圖中的位置.由圖可見，當(dāng)自然路標(biāo)的繪制位置在小范圍內(nèi)發(fā)生變動時，機(jī)器人仍然能夠依據(jù)視覺識別自然路標(biāo)在環(huán)境中的位置，修正手繪地圖中的偏差，指導(dǎo)機(jī)器人完成導(dǎo)航.

圖6 不同目標(biāo)區(qū)域的導(dǎo)航實(shí)驗(yàn)

圖7 自然路標(biāo)的繪制偏差影響

3)實(shí)驗(yàn)3 考察自然路標(biāo)在導(dǎo)航環(huán)境中挪動的影響.每次機(jī)器人從同一個起點(diǎn)以同樣的位姿出發(fā)，僅改變真實(shí)環(huán)境中自然路標(biāo)的擺放位置和姿態(tài).每次實(shí)驗(yàn)路標(biāo)挪動約1 m，結(jié)果如圖8(a)所示.由圖可見，小范圍改變實(shí)驗(yàn)環(huán)境中的自然路標(biāo)位置和姿態(tài)，會輕微影響機(jī)器人的導(dǎo)航路徑.但是機(jī)器人仍然能夠較為準(zhǔn)確地到達(dá)目的地.說明該導(dǎo)航方法能夠適應(yīng)環(huán)境的動態(tài)變化，容許手繪地圖與真實(shí)環(huán)境的位置差異.

圖8 同類自然路標(biāo)多次出現(xiàn)的影響

4)實(shí)驗(yàn)4 考察手繪地圖中部分路標(biāo)在真實(shí)環(huán)境中缺失時的影響.第1 次實(shí)驗(yàn)時環(huán)境中有電風(fēng)扇、吊蘭、垃圾簍、椅子、吉他、雨傘共6 個自然路標(biāo);第2 次實(shí)驗(yàn)時，有電風(fēng)扇、吊蘭、垃圾簍、吉他、雨傘共5 個自然路標(biāo);第3 次實(shí)驗(yàn)有電風(fēng)扇、吊蘭、吉他、雨傘共4 個自然路標(biāo).結(jié)果如圖8(b)所示.由圖可見，當(dāng)部分物體被遮擋或者發(fā)生較大的位置變化導(dǎo)致部分路標(biāo)缺失時，導(dǎo)航路徑與手繪地圖基本一致.因此，只要環(huán)境中的大部分自然路標(biāo)與手繪地圖一致，機(jī)器人仍然能夠到達(dá)目的區(qū)域.

5)實(shí)驗(yàn)5 考察環(huán)境中有多個同類別的自然路標(biāo)對機(jī)器人導(dǎo)航的影響.在8 個自然路標(biāo)中，有3 個自然路標(biāo)都是椅子，通過椅子位置變化，檢測導(dǎo)航算法在不同方位對相同類別的自然路標(biāo)的識別能力.實(shí)驗(yàn)結(jié)果如圖8(c)所示.由圖可見，若環(huán)境中有多個同類別的自然路標(biāo)，利用本導(dǎo)航方法中的路標(biāo)篩選方法，能夠有效預(yù)測出當(dāng)前狀態(tài)下機(jī)器人最可能識別的自然路標(biāo)，因此其導(dǎo)航結(jié)果基本不受影響.進(jìn)一步證明了，本文提出的導(dǎo)航方法能夠適應(yīng)動態(tài)環(huán)境.

6)實(shí)驗(yàn)6 將實(shí)驗(yàn)1 中的自然路標(biāo)替換為同一類別、不同外觀的物體，考察本導(dǎo)航方法在環(huán)境改變下的導(dǎo)航情況，實(shí)驗(yàn)結(jié)果如圖9所示.由圖可見，以同一類別不同外觀的物體作為自然路標(biāo)，只要結(jié)構(gòu)不發(fā)生太大的變化，BoW 物體識別模型仍然能夠準(zhǔn)確識別.以上實(shí)驗(yàn)表明本文提出的自然路標(biāo)識別方法具有一定的通用性，在一定程度上能夠克服同類物體的差異.

圖9 自然路標(biāo)外觀變化的影響

5 結(jié)語

本文提出了一種基于BoW 物體識別模型的視覺導(dǎo)航方法，機(jī)器人以顯著物體作為路標(biāo)，依據(jù)手繪地圖高效地完成導(dǎo)航任務(wù).實(shí)驗(yàn)結(jié)果表明，即使自然路標(biāo)的外觀、位置和數(shù)量、環(huán)境發(fā)生改變，在手繪地圖的粗略指導(dǎo)下，本導(dǎo)航方法仍然能夠快速適應(yīng)這些變化.該方法能容忍手繪地圖的部分偏差，表現(xiàn)出很好的人機(jī)互動性，方便用戶操作.目前自然路標(biāo)數(shù)據(jù)庫中的物體種類相對偏少，今后將會進(jìn)一步擴(kuò)充，實(shí)現(xiàn)更大范圍的導(dǎo)航.

References)

［1］Bonin-Font B，Ortiz A，Oliver G.Visual navigation for mobile robots:a survey［J］.Journal of Intelligent and Robotic Systems，2008，53(3):263-296.

［2］許俊勇，王景川，陳衛(wèi)東.基于全景視覺的移動機(jī)器人同步定位與地圖創(chuàng)建研究［J］.機(jī)器人，2008，30(4):289-297.

Xu Junyong，Wang Jingchuan，Chen Weidong.Omnivision-based simultaneous localization and mapping of mobile robots［J］.Robot，2008，30(4):289-297.(in Chinese)

［3］Guo Yang，Xu Xinhe.Color landmark design for mobile robot localization［C］//IMACS Multi Conference on Computational Engineering in Systems Applications.Beijing，China，2006:1868-1874.

［4］Hu Huosheng，Gu Dongbing.Landmark-based navigation of industrial mobile robots［J］.International Journal of Industry Robot，2000，27(6):458-467.

［5］Hayet J B，Lerasle F，Devy M.A visual landmark framework for indoor mobile robot navigation［C］//Proceedings of ICRA′02 Robotics and Automation.Washington DC，USA，2002，4:3942-3947.

［6］Blanc G，Mezouar Y，Martinet P.Indoor navigation of a wheeled mobile robot along visual routes［C］//IEEE International Conference on Robotics and Automation.Barcelona，Spanish，2005:3354-3359.

［7］Madhavan R，Durrant-Whyte H F.Natural landmarkbased autonomous vehicle navigation［J］.Robotics and Autonomous Systems，2004，46(2):79-95.

［8］蔡自興，王勇，王璐.基于角點(diǎn)聚類的移動機(jī)器人自然路標(biāo)檢測與識別［J］.智能系統(tǒng)學(xué)報，2006，1(1):52-56.

Cai Zixing，Wang Yong，Wang Lu.Corner clustering based detection and recognition of natural landmark for mobile robot［J］.CAAI Transactions on Intelligent Systems，2006，1(1):52-56.(in Chinese)

［9］李新德，吳雪建，朱博，等.一種基于手繪地圖的動態(tài)環(huán)境視覺導(dǎo)航方法［J］.機(jī)器人，2011，33(4):490-501.

Li Xinde，Wu Xuejian，Zhu Bo，et al.A visual navigation method using a hand-drawn-route-map in dynamic environments［J］.Robot，2011，33(4):490-501.(in Chinese)

［10］Csurka G，Dance C，F(xiàn)an L，et al.Visual categorization with bags of keypoints［C］//ECCV’04 Workshop on Statistical Learning in Computer Vision.Prague，Czech，2004:59-74.

［11］Zhao R，Grosky W I.Narrowing the semantic gap-improved text-based web document retrieval using visual features［J］.IEEE Transactions on Multimedia，2002，4(2):15-42.

［12］David G L.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91-110.