馬志偉， 金小峰

（延邊大學(xué)工學(xué)院計算機科學(xué)與技術(shù)系 智能信息處理研究室，吉林 延吉133002）

基于場景復(fù)雜度的移動機器人目標(biāo)搜索方法的研究

馬志偉， 金小峰＊

（延邊大學(xué)工學(xué)院計算機科學(xué)與技術(shù)系 智能信息處理研究室，吉林 延吉133002）

借鑒人類搜索經(jīng)驗，將場景復(fù)雜度概念應(yīng)用到移動機器人目標(biāo)搜索過程，提出了一種基于場景復(fù)雜度的移動機器人目標(biāo)搜索方法．首先，通過分析影響場景復(fù)雜度的主要因素，給出了融合圖像和激光深度信息的場景復(fù)雜度形式化定義；其次，結(jié)合視覺目標(biāo)檢測過程，描述了基于場景復(fù)雜度的目標(biāo)搜索方法，該方法通過對各個場景按復(fù)雜度進行篩選來確定待搜索場景，并根據(jù)場景深度信息確定該場景的待搜索點．實驗結(jié)果表明：本文提出的場景復(fù)雜度計算方法符合人的復(fù)雜度主觀感受，較好地反映了場景的內(nèi)在特征；基于場景復(fù)雜度的目標(biāo)搜索方法可以有效地搜索目標(biāo)，具有較好的魯棒性．

移動機器人；目標(biāo)搜索；環(huán)境探索；場景復(fù)雜度

0 引言

移動機器人是機器人研究領(lǐng)域的重要分支，它集中體現(xiàn)了人工智能與信息科學(xué)的最新成果，在事故救援、軍事偵察、爆炸物搜索與處理、防止核污染等方面有著廣泛的應(yīng)用［1］．在多數(shù)應(yīng)用中，移動機器人必須首先具備物品識別和目標(biāo)搜索的能力，然后才能對目標(biāo)進行進一步處理．移動機器人目標(biāo)搜索屬于最優(yōu)搜索理論與機器人自動化相結(jié)合的前沿課題，研究內(nèi)容除了搜索理論，還涉及到環(huán)境感知、環(huán)境探索、運動控制和模式識別等多個研究內(nèi)容，是移動機器人領(lǐng)域最具挑戰(zhàn)的研究課題之一［2］．

針對未知環(huán)境移動機器人視覺目標(biāo)搜索問題，國內(nèi)外學(xué)者進行了廣泛研究．Ye和Tsotsos［3］證明了3－D空間的視覺目標(biāo)搜索是1個N－P完備性問題．Connolly［4］認為，搜索過程中的視角選擇問題類似于未知場景中獲得新的觀察數(shù)據(jù)的場景重建問題．為了降低搜索代價，Alper［5］提出了1種間接搜索方法，即首先搜索與目標(biāo)有關(guān)的“中間對象”，然后根據(jù)空間關(guān)聯(lián)關(guān)系指導(dǎo)目標(biāo)搜索過程．Shubina和Tsotsos［6］將視覺注意引入了視覺搜索過程，利用視覺注意的內(nèi)在優(yōu)化機制改善目標(biāo)搜索進程，提高了搜索效率．此外，很多學(xué)者對多機器人目標(biāo)搜索問題也進行了廣泛的研究［7－8］．上述搜索方法多數(shù)需要在特定假設(shè)條件下才能完成，不具有通用性，因此，本文借鑒人類的搜索經(jīng)驗，將復(fù)雜度概念應(yīng)用到移動機器人目標(biāo)搜索任務(wù)中，提出一種基于場景復(fù)雜度的移動機器人目標(biāo)搜索方法．該方法有效地整合了未知環(huán)境探索和目標(biāo)檢測，通過分析各場景的復(fù)雜度指導(dǎo)目標(biāo)搜索過程，算法結(jié)構(gòu)簡單、通用性良好，在真實環(huán)境搜索實驗中取得了很好的實驗結(jié)果．

1 場景復(fù)雜度

在目標(biāo)搜索過程中，人們往往對那些隱蔽、雜亂、不規(guī)則的場景給予更多的關(guān)注，認為目標(biāo)在這些場景中出現(xiàn)的可能性更大，因而，場景的復(fù)雜程度直接決定了搜索的方向．根據(jù)生理學(xué)和神經(jīng)學(xué)研究發(fā)現(xiàn)，人類從視覺場景中可以獲得由二維圖像信息和一維深度信息構(gòu)成的三維場景信息，所以對于場景的復(fù)雜度分析也需要在圖像和深度2個方面進行．本文借助單目視覺傳感器和激光深度測距傳感器獲得相應(yīng)的三維場景信息．機器人目標(biāo)搜索過程中的場景復(fù)雜度計算方法如公式（1）所示：

其中fc（I）為視覺圖像數(shù)據(jù)I提供的圖像復(fù)雜度，fc（D）為激光深度數(shù)據(jù)D提供的深度復(fù)雜度，wi和wd分別為圖像和深度在總體場景復(fù)雜度中的歸一化影響因子．

1．1 場景圖像復(fù)雜度

圖像復(fù)雜度是對圖像內(nèi)在復(fù)雜程度的描述，文獻［9］提出了1種綜合整體、區(qū)域、目標(biāo)角度的圖像復(fù)雜度描述方法，該方法通過計算圖像的信息熵、紋理特征和邊緣比率獲得圖像的復(fù)雜度．對于目標(biāo)搜索任務(wù)，為使復(fù)雜度計算有利于目標(biāo)搜索過程，本文在此基礎(chǔ)上引入了圖像顯著性和目標(biāo)似然度2部分，具體計算方法如下描述．

如果1幅圖像中顯著性區(qū)域較多，則表明圖像比較復(fù)雜．一般認為，顯著性就是稀有性，但它同時還會受到尺度的影響，選擇不同尺度的特征會產(chǎn)生不同的顯著性區(qū)域．當(dāng)前，顯著性區(qū)域提取的方法有很多種［10］，但要獲得越好的效果其相應(yīng)的計算代價就越大．鑒于此，本文采用文獻［11］提出的基于DCT系數(shù)稀疏編碼的方法進行顯著性區(qū)域提取，并將其轉(zhuǎn)化為圖像復(fù)雜度的評價指標(biāo)，如式（2）和（3）所示：

其中sign（·）為符號函數(shù)，dct2（·）和idct2（·）為圖像的正、逆DCT變換函數(shù)，I′為變換后的圖像，M和N分別為圖像的行數(shù)和列數(shù)，PI′為I′閾值化后顯著性區(qū)域像素的總個數(shù)．

目標(biāo)似然度是指目標(biāo)在場景中被檢測出的概率，不同于目標(biāo)識別的精確檢測，它給出的是場景中與目標(biāo)相似的區(qū)域比例．目標(biāo)似然度可以利用目標(biāo)圖像與場景圖像的顏色直方圖反向投影圖像計算得出，其計算方法如式（4）所示：

其中Pproject為場景圖像對應(yīng)的目標(biāo)顏色直方圖反向投影圖像中非零像素數(shù)．

整合紋理TI、顯著性SI、邊緣比率RI和目標(biāo)似然度LI，圖像復(fù)雜度計算方法如公式（5）所示，其中wi1、wi2、wi3和wi4分別為4個部分的歸一化影響因子．

其中σ為方差，μ為均值，wd1和wd2分別為方差σ和均值μ的歸一化影響因子．

1．2 場景深度復(fù)雜度

場景深度反映了場景中物品的距離變化，距離變化越劇烈，說明分布越混亂，對應(yīng)場景整體越復(fù)雜；同時，若場景深度的平均距離越大，表明場景空間越大，相應(yīng)場景也就越復(fù)雜．本文采用變異系數(shù)與平均距離的加權(quán)來計算場景深度復(fù)雜度fc（D），如式（6）所示：

2 視覺目標(biāo)搜索方法

針對室內(nèi)未知環(huán)境靜止視覺目標(biāo)搜索問題，本文提出了基于場景復(fù)雜度的目標(biāo)搜索方法，該方法采用文獻［12］中提出的Harris－SIFT局部不變特征作為目標(biāo)模型進行視覺目標(biāo)檢測，并利用上文中的場景復(fù)雜度計算方法對各個場景進行篩選，并保留復(fù)雜的場景做進一步的搜索．假定待搜索目標(biāo)只為1種，數(shù)量為n，借助激光測距和單目視覺傳感器，其相應(yīng)算法描述如下：

算法1 基于場景復(fù)雜度的目標(biāo)搜索．

輸入：待搜索目標(biāo)O和相應(yīng)的目標(biāo)分類器C，機器人起始定位P，搜索點鏈表L，最大搜索時間Tmax．

輸出：目標(biāo)定位列表Pos＿List，機器人搜索軌跡Path，環(huán)境地圖m．

步驟1 根據(jù)起始定位P初始化環(huán)境地圖m，清空待搜索點鏈表L；

步驟2 獲得機器人當(dāng)前位置對應(yīng)的各個場景信息，更新環(huán)境地圖m，并將當(dāng)前定位信息存入Path；

步驟3 利用目標(biāo)檢測算法對各個場景進行精確目標(biāo)檢測，若目標(biāo)被檢測到且并未在Pos＿List中出現(xiàn)過，則將此定位信息放入Pos＿List中；否則，按式（1）計算此場景的復(fù)雜度；

步驟4 保留復(fù)雜度大于給定閾值φ的場景；

步驟5 依據(jù)激光深度數(shù)據(jù)depth計算各個場景的中心位置，并增加最大搜索距離約束，判斷其是否滿足待搜索條件，若滿足，則將其存入待搜索點鏈表L中；

步驟6 從待搜索點鏈表L中選擇當(dāng)前待搜索點，利用A＊算法進行路徑規(guī)劃，確定可行路徑，執(zhí)行搜索過程，并將其從待搜索點鏈表中刪除；

步驟7 重復(fù)執(zhí)行步驟2—步驟6，直到待搜索點鏈表為空或搜索時間超過Tmax．

從該算法的描述中可知，復(fù)雜度閾值在目標(biāo)搜索過程中起到了重要的作用，不同復(fù)雜度閾值將產(chǎn)生不同類型的搜索結(jié)果：閾值越小，搜索越精細；閾值越大，搜索越粗糙．

3 實驗結(jié)果及分析

為了驗證本文方法的有效性，在室內(nèi)環(huán)境進行多組實驗．實驗平臺為AS－R移動機器人（攜帶車載計算機，Pentium（R）4 3．00 GHz，1 G RAM），見圖1．實驗環(huán)境如圖2和圖3所示．

在實驗中，設(shè)機器人的行駛速度為0．3 m/s，單目視覺采樣率為15幀/s，激光傳感器的響應(yīng)時間為26 ms，角度分辨率為0．5°，距離分辨率為10 mm，掃描范圍為180°，環(huán)境柵格地圖的比例尺為1∶50 mm．

圖1 AS－R移動機器人

圖2 實驗環(huán)境1

圖3 實驗環(huán)境2

由于單目視覺的水平視域為60°，故需要在同1個位置轉(zhuǎn)動5次才能獲取與當(dāng)前位置對應(yīng)的360°范圍內(nèi)的6個不重疊場景信息（圖像和激光測距數(shù)據(jù)）．同時，在場景復(fù)雜度計算過程中，需要利用與視覺重合的中間60°范圍內(nèi)的激光測距數(shù)據(jù)．

1）場景復(fù)雜度實驗 實驗在圖3所示的環(huán)境中進行．圖4從左到右、從上到下分別為6個不同視角的場景圖像和場景深度信息，表1為其對應(yīng)的復(fù)雜度信息．

圖4 環(huán)境1中不同朝向的場景信息

表1 環(huán)境1的場景復(fù)雜度

從圖4和表1可以看出：場景復(fù)雜度的計算結(jié)果與人的復(fù)雜度主觀感受一致，較好地反映了場景的內(nèi)在特征．盡管場景a的深度復(fù)雜度比場景d大，但場景d的圖像復(fù)雜度遠大于場景a，因而總體上場景d的場景復(fù)雜度大于場景a．場景c和場景e的圖像復(fù)雜度比較接近，但由于場景c中的黑色物體吸收了部分激光信號，產(chǎn)生了較大的偏差，使得場景c的深度復(fù)雜度大于場景e，故場景c的場景復(fù)雜度大于場景e．對于復(fù)雜度計算公式中的權(quán)值確定問題，通常與特定任務(wù)性質(zhì)和環(huán)境類型相關(guān)，可通過實驗加以確定．

2）視覺目標(biāo)搜索實驗 為驗證復(fù)雜度閾值與目標(biāo)搜索之間的關(guān)系，對不同復(fù)雜度閾值下的搜索實驗進行了對比．實驗過程中，假定未知環(huán)境中僅存在1個靜止的待搜索目標(biāo)，各算法按最近鄰原則選擇下1個待搜索點，算法終止條件為找到既定目標(biāo)或無待搜索點．

搜索實驗在圖2和圖3所示的環(huán)境中進行，每組實驗在同一環(huán)境中的3個不同起點運行2次，目標(biāo)放置在與起點不同的位置，各評價指標(biāo)取6次實驗的平均值，場景復(fù)雜度閾值分別設(shè)為0．00、0．15、0．25、0．35、0．45、0．55．搜索算法性能評價指標(biāo)由搜索成功率、搜索時間、軌跡長度和單次平均搜索步長組成，實驗結(jié)果如表2和表3所示．

表2 目標(biāo)搜索實驗1

表3 目標(biāo)搜索實驗2

從表2和表3可以看出，本文提出的目標(biāo)搜索方法可以有效地搜索目標(biāo)，其中算法中的復(fù)雜度閾值對搜索結(jié)果有著重要的影響．復(fù)雜度閾值越低，搜索過程越精細，搜索步長越小，進而搜索成功率越高，但相應(yīng)的搜索時間和軌跡長度也越大；復(fù)雜度閾值越高，搜索過程越粗糙，搜索步長越大，進而搜索成功率越低，同時搜索時間和軌跡長度也就越?。C合考慮搜索成功率和搜索效率，搜索實驗1中的最佳復(fù)雜度閾值為0．0，搜索實驗2中的最佳復(fù)雜度閾值為0．25，這說明最佳復(fù)雜度閾值與特定搜索環(huán)境有關(guān)．

4 結(jié)束語

本文提出的場景復(fù)雜度計算方法符合人的復(fù)雜度主觀感受，較好地反映了場景的內(nèi)在特征．實驗結(jié)果表明：文中提出的場景復(fù)雜度可以應(yīng)用于移動機器人目標(biāo)搜索任務(wù)，但是復(fù)雜度閾值會影響搜索算法的性能，閾值越低搜索越精細，閾值越高搜索越粗糙．如何根據(jù)不同的搜索環(huán)境自適應(yīng)地確定復(fù)雜度閾值是下一步的研究內(nèi)容．

［1］ Murphy R R．人工智能機器人學(xué)導(dǎo)論［M］．杜軍平，吳立成，胡金春，等譯．北京：電子工業(yè)出版社，2004：10－11．

［2］ 張林．家庭服務(wù)機器人物品搜尋與定位技術(shù)研究［D］．山東大學(xué)控制科學(xué)與控制工程學(xué)院，2009：1－5．

［3］ Tsotsos J K．The complexity of perceptual search tasks［C］//Proceedings of the 11th International Joint Conference on Artificial Intelligence：Vol．2．Menlo Park，California，USA：AAAI，1989：1571－1577．

［4］ Connolly C I．Determination of next best views［C］//IEEE International Conference on Robotics and Automation．Piscataway，N J，USA：IEEE，1985：432－435．

［5］ Alper A，Kristoffer S，Patric J．Object search on a mobile robot using relational spatial information［C］//Proceedings of the 11th International Conference on Intelligent Autonomous Systems．Amsterdam，Netherlands：IOS，2010：111－120．

［6］ Shubina K，Tsotsos J K．Visual search for an object in a 3D environment using a mobile robot［J］．Computer Vision and Image Understanding，2010，114（5）：535－547．

［7］ Pham H N．A comprehensive cooperative exploration framework for ground and air vehicles in unknown environments［D］．Master thesis of School of Aerospace，Mechanical and Mechatronic Engineering，The University of Sydney，2007：116－149．

［8］ Hollinger G A．Search in the physical world［D］．Doctor thesis of Robotics Institute Carnegie Mellon University，2010：1－7．

［9］ 高振宇，楊曉梅，龔劍明，等．圖像復(fù)雜度描述方法研究［J］．中國圖像圖形學(xué)報，2010，15（1）：129－135．

［10］ 胡正平，孟鵬權(quán)．全局孤立性和局部同質(zhì)性圖表示的隨機游走顯著目標(biāo)檢測算法［J］．自動化學(xué)報，2011，37（10）：1279－1284．

［11］ Hou X D，Hare J，Koch C．Image signature：highlighting sparse salient regions［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（1）：194－201．

［12］ Azad P，Asfour T，Dillmann R．Combining harris interest points and the SIFT descriptor for fast scale－invariant object recognition［C］//IEEE Conference on Intelligent Robots and Systems．Piscataway，N J，USA：IEEE，2009：4275－4280．

Research on target search method for mobile robot based on scene complexity

MA Zhi－wei， JIN Xiao－feng＊
（Intelligent Information Processing Lab．，Department of Computer Science ＆Technology，College of Engineering，Yanbian University，Yanji 133002，China）

Base on the concept of scene complexity which was from the human search experience，we present a novel target search method for mobile robot．In the method，formalization definition of scene complexity was firstly given by analyzing the main factors relative to scene complexity which combined image complexity with laser ranges complexity．Then，combined the processes of visual target detection，the complexity of several scenes were calculated according to the definition．Thirdly，the next search scene was selected by comparing the obtained scenes complexity and the next search point was determined by the laser ranges of the scene．Experimental results show that the method of scene complexity is in accord with the human evaluation and reflects the scene’s intrinsic characteristics，and the proposed target search method is effective and robust．

mobile robot；target search；environment exploration；scene complexity

TP242．6

A

1004－4353（2012）02－0158－05

2012－05－06

＊通信作者：金小峰（1970—），男，副教授，研究方向為語音識別、機器視覺及機器人技術(shù)．