基于語義樹Markov隨機場模型的地面機器人多尺度道路感知

杜明芳，王軍政1，李多楊1，何玉東1

（1.北京理工大學復雜系統智能控制與決策國家重點實驗室，北京100081；2.北京聯合大學自動化學院，北京100101）

基于語義樹Markov隨機場模型的地面機器人多尺度道路感知

杜明芳1，2，王軍政1，李多楊1，何玉東1

（1.北京理工大學復雜系統智能控制與決策國家重點實驗室，北京100081；2.北京聯合大學自動化學院，北京100101）

道路實時感知是自主式地面移動機器人實現自主導航的關鍵技術，但由于室外道路環境的復雜性與不確定性，其算法開發難度較大。提出了一種基于小波域語義樹Markov模型的多尺度仿生道路感知算法。在時空域上采用三維隨機場對機器人采集到的道路圖像序列進行建模，提出了一種采用樹結構約束、面向道路識別的語義樹Markov隨機場（RT-MRF）模型；采用遺傳算法優化的有監督RT-MRF模型進行道路圖像序列分割；機器人通過跟蹤分割邊界實現道路區域識別及自主導航。采用自主研制的四足仿生機器人作為研究和實驗平臺。實驗結果表明：該方法能夠在具有陰影、裂紋、坑洞、不平整及光照度變化的較差道路檢測條件下魯棒分割出道路邊界，算法實時性高，可滿足室外移動機器人自主導航需求。

控制科學與技術；四足機器人；道路檢測；多尺度仿生感知；語義樹Markov模型；小波域

0 引言

基于視覺的室外移動機器人道路環境感知屬于攝像機運動、目標（道路、動靜態障礙物）運動狀態混合的機器視覺問題范疇，特別是在考慮室外隨機復雜道路環境干擾的情形下，該領域一直缺乏統一且有效的圖像建模與理解方法。機器人在運動過程中采集到一個圖像序列，將二維平面空間的計算問題延伸為三維立體空間的計算問題，因此傳統靜態圖像處理和分析的算法并不完全適用于移動機器人視覺導航系統。目前，室外移動機器人視覺環境感知中，遇到的主要問題集中體現在缺少嚴謹的視覺計算模型，感知算法的實時性和魯棒性，不能完全滿足機器人大范圍移動的需求，機器人對環境的自適應性不強。另外，缺少實際的移動機器人實驗平臺和驗證平臺也是阻礙此項研究進展的關鍵因素。

本文以自主研制的四足仿生機器人BigDog為背景，對自主移動機器人的視覺環境感知問題展開研究。四足仿生機器人是近年來國內外機器人領域研究的熱點［1-4］。美國波士頓動力學工程公司研制的BigDog四足機器人在具有挑戰性的環境中，如斜坡地形、15 m以上巨石障礙、坑洞負障礙、樹干障礙、葉子干擾等，仍能通過視覺和雷達系統有效識別出可通行區域。我國于2011年啟動了高性能四足機器人的研發資助工作，目前僅有北京理工大學、山東大學、國防科學技術大學、哈爾濱工業大學、上海交通大學等少數單位真正研制出了可以承重100 kg以上的BigDog機器人樣機，研究的重點大多集中在驅動與控制部分，對感知系統研究的較少，因此這些樣機尚不具備復雜未知地形感知能力。本文提出了一種基于有監督小波域 Markov隨機場（MRF）模型的非結構化道路圖像建模及多尺度識別方法，可解決BigDog在室外非結構化環境行走時的視覺道路環境理解問題，為室外自主移動機器人有效感知復雜環境奠定堅實基礎。

機器人對道路圖像的正確理解實質上可以簡化成障礙物—非障礙物的圖像二分類問題，因此有效的圖像分割方法是解決問題的關鍵。聚類（如K-均值聚類法）和神經網絡是以往較常用的道路圖像分割方法。聚類法能將圖像分為障礙物和非障礙物兩類，但對應的具體含義無法確定。神經網絡法通過訓練樣本構造分類器，缺點是需要采集大量樣本，訓練耗時長，在線應用較難，且分類器只對應于某時刻和某種道路屬性，無法適應路面介質變化或光照變化。人類視覺認知的最大特點是具有層次性，人腦大腦皮層的視覺區域是分層次工作的，越底層的視覺皮層對底層特征越敏感，這與小波分析的多尺度分析思想是相通的。受此啟發，本文提出一種基于小波分析的道路圖像分析及理解方法。

隨著子波分析及基于子波的統計信號處理方法的發展，多尺度變換域圖像的感知與識別也得到了一些相應的發展。Crouse等［5］、Choi等［6］、Li等［7］提出的子波域隱Markov模型開辟了多尺度變換域統計信號處理這一新領域。迄今為止，學者們提出了多種不同變換域的改進Markov模型，其主要目的是提高建模的準確定性和模型訓練的有效性。由于這些模型主要立足于如何準確描述子波系數間的相關性，忽略了實際應用中模型參數訓練會占用大量處理時間的事實，因此在圖像感知與識別這類實時性要求高的領域，實用價值并不大。本文從室外移動機器人實時性要求高及室外道路圖像噪聲大（將裂紋、陰影、模糊等統一看作噪聲）這兩個本質特點入手，根據先驗知識，提出一種小波域語義樹深度為i（i≤3）、同時僅對關鍵參數進行訓練的改進隱Markov模型，將該模型命名為面向道路識別的語義樹MRF（RT-MRF）.

1 道路圖像的小波域多尺度建模

RT-MRF模型采用樹結構約束的二值Markov時空域三維隨機場序列來建模道路圖像序列。通過空間域分割，將道路圖像分割為具有語義邊界的區域，再通過時域上的邊界跟蹤實現最終的道路區域識別。

在空間域的幀內，每一個二值MRF對應樹結構的一個節點，通過節點與節點之間的相互關系來表達道路圖像的層次結構信息。對機器人環境感知來講，道路圖像的分類類別數和分類結果是已知的，屬于先驗知識，因此采用有監督分割法更加適宜，這可降低分割過程中確定分類樹所需的計算復雜度。語義樹原型為簡單二叉樹，如圖1（a）所示，道路圖像空間域分割的語義樹定義如圖1（b）所示。

在小波分解的每一尺度上均定義相同結構的道路圖像語義樹。將分類層次樹和小波系數四叉樹分別記為CT和WRT.用r（0）表示根節點，m（t）（1≤t≤p）表示中間節點，l（t）（1≤t≤q）表示葉子節點。則

將道路圖像序列定義為大小為M×N×K的三維格網位置集合V=｛v|v=（m，n，k）｝，單幀道路圖像定義為M×N的二維格網位置集合S=｛s|s= （m，n）｝.在某幀內，用二維小波分解把第l尺度上的低頻段道路圖像信號分解成第l+1尺度上的4個道路圖像信號：1個低頻段圖像信號和水平、垂直、對角線3個方向上的高頻段圖像信號。高頻段圖像信號對應水平、垂直和對角線方向的圖像細節信息。這種分解一直繼續下去，直到達到預期尺度為止。

對機器人檢測到的道路圖像作J-1層小波分解，每一小波尺度空間標號用層號j（j∈［0，…，J-1］）表示。分解后的道路圖像在每一尺度上均被分解為4個頻段：SLL（j）、SLH（j）、SHL（j）、SHH（j）.同一分辨率上的不同頻帶具有相同格網位置集合S（j）= SLL（j）=SLH（j）=SHL（j）=SHH（j）.某幀圖像經小波分解后所有分辨率的格網位置集合為S=｛S（j）|0≤j≤J-1｝.相鄰分辨率的格網位置具有1對4的關系，一個低分辨率格網位置對應4個相鄰高分辨率格網位置，從而形成小波系數向量的四叉樹結構。某幀多尺度道路圖像語義模型如圖2所示。

圖2　多尺度道路圖像語義模型Fig.2 Multi scale road image semantic model

2 基于有監督RT-MRF模型的道路圖像分割

RT的T-MRFi模型XWRT表示為各分辨率上RT中各節點的MRF的集合

XWRT的一個現實所對應的聯合分布表示為

（3）式體現了圖像分割時的父節點約束及相鄰分辨率上對應同一節點的兩個MRF的約束關系。

通過求（4）式的極大值來估計各尺度上的分割結果：

式中：ω為多分辨率觀測場。

四足仿生機器人采用離線訓練，在線感知的方式進行道路感知。首先為每一尺度道路區域和非道路區域分別手工選定一個感興趣區域，作為每一類的訓練樣本，將每一尺度的訓練參數保存到指定空間；然后利用RT-MRF模型進行道路圖像分割。在每一尺度上分割時首先讀取模型參數，然后沿道路語義樹自下向上計算似然取值，再沿著語義樹自上而下逐節點計算每一節點的分割結果。首先，在最低分辨率尺度上執行分割算法，然后，再將此分割結果逐層傳遞到更高一級分辨率尺度上。通過遞歸優化運算實現（4）式的最大化。在進行遞歸優化運算時，遍歷所有m（t）（1≤t≤p）節點將占用大部分時間，其中計算參數x（j，t）和 β（j，t）最為復雜，因此采用遺傳算法對其進行優化計算。令遺傳算法的適應度函數為

式中：β（j，t）為T-MRFi模型的雙點勢函數。這樣就將參數的計算轉化為求適應度函數的極值問題。

3 實驗與分析

本文算法的應用平臺—BigDog四足仿生機器人試驗測試系統如圖3所示。

圖3　BigDog研究平臺Fig.3 BigDog research platform

為了說明算法的通用性，采用卡耐基梅隆大學提供的室外移動機器人道路視頻對本文所述算法進行驗證，以隨機選擇的第9幀、第12幀、第15幀、第18幀為例說明實驗效果。用sym4小波對以上幀進行3層分解，為節省計算時間，并不進行圖像重構，且在每一尺度上只采用低頻段圖像信息進行語義樹參數訓練。設置語義樹深度為2，感知后的黑色區域理解為“非路”，類標注為“2”，不可通行；白色區域理解為“路”，類標注為“1”，可通行。通過這種類標注實現了道路語義理解。

原始幀在3個尺度上的小波分解（LL頻段）結果如圖4所示。在3個尺度上的道路感知結果如圖5所示。

實驗結果表明：

1）算法的魯棒性強。對陰影干擾較嚴重（如第12幀、第15幀、第18幀）、有裂紋（如第12幀、第15幀）、有坑洞（如第12幀）的非結構化道路有較強的魯棒性，道路邊界分割準確，完全可以用于指導機器人自主導航。

2）算法的實時性得到了很大改善。本文采用的原始幀的大小均約110 K左右，經過小波分解后變為30 K左右，在滿足系統導航精度的前提下圖像得到有效壓縮，且算法存儲的是小波系數及其他小存儲量參數，因此算法復雜度降低，實時性顯著提高，各幀的分割耗時對比如圖6所示。

3）算法的自適應性強。相較于傳統的僅在最高分辨率級上進行計算的算法，本文算法可以根據路況自由選擇單個尺度或某幾個尺度上的局部頻段進行圖像感知計算，例如針對本文的道路圖像序列，就可以只選擇尺度2作為感知對象，完全可以滿足機器人道路感知需求。

另外，需要說明的是：利用單目圖像感知的方法并不能精確區分陰影和障礙物實體，可利用立體視覺或雷達進一步探測出障礙物的高度信息（凸障礙物高度為正；凹障礙物高度為負），以確定出障礙物的準確位置。道路實際邊界和陰影干擾邊界的區分也是要依靠雷達或立體視覺等給出邊界的高度信息，并綜合數值擬合的結果進行決策。

圖4　3個尺度上的小波分解結果（LL頻段）Fig.4 Wavelet decomposition results（LL band）on three scales

圖5　3個尺度上的道路感知結果Fig.5 Road sensing results on three scales

圖6　算法實時性對比Fig.6 Real-time comparison of algorithms

4 結論

室外移動機器人道路感知的需求特點為實時性要求高，精度要求并不需太高。本文針對該需求，建立了道路圖像的小波域多尺度分析模型，并在該模型基礎上提出了采用遺傳算法優化的基于有監督樹型結構MRF模型的道路圖像分割方法，取得了對道路裂紋、陰影、坑洞等干擾綜合處理最優的結果，算法實時性、魯棒性、自適應性均達到自主移動機器人環境感知系統的基本需求，是一種模擬人眼多粒度感知環境的仿生感知方法。該方法的提出和研制對促進仿生機器人仿生環境感知領域的發展具有積極促進意義，彌補了目前該領域仿生設計的不徹底性的不足。進一步研究計劃為：

1）將機器學習算法引入自主機器人領域［8］，如采用深度學習算法對環境圖像特征進行自主學習，進一步提高方法的智能性。

2）進一步深入研究稀疏度自適應算法［9］并應用到三維時空域上的道路圖像表示中，進一步提高系統實時性。

3）采用三維虛擬樣機技術［10］，使機器人設計更加符合產品研制的一般流程，使樣機更加接近產品。最終達到機器人視覺感知系統與控制系統協同性好、能量優化、抗外力自平衡性好，從而達到綜合性能最優［11-13］。

（References）

［1］ Semini C，Tsagarakis N G，Guglielmino E，et al.Design of HyQ-a hydraulically and electrically actuated quadruped robot［J］.Proceedings of the Institution of Mechanical Engineers，Part I：Journal of Systems and Control Engineering，2011，225（6）：831-849.

［2］ 張秀麗.四足機器人節律運動及環境適應性的生物控制研究［D］.北京：清華大學，2004. ZHANG Xiu-li.Biological-inspired rhythmic motion&environmental adaptability for quadruped robot［D］.Beijing：Tsinghua U-niversity，2004.（in Chinese）

［3］ 李貽斌，李彬，榮學文，等.液壓驅動四足仿生機器人的結構設計和步態規劃［J］.山東大學學報，2011，41（5）：32-36，45. LI Yi-bin，LI Bin，RONG Xue-wen，et al.Mechanical design and gait planning of a hydraulically actuated quadruped bionic robot ［J］.Journal of Shandong University，2011，41（5）：32-36，45. （in Chinese）

［4］ 王立鵬，王軍政，汪首坤，等.基于足端軌跡規劃算法的液壓四足機器人步態控制策略［J］.機械工程學報，2013，49（1）：39-44. WANG Li-peng，WANG Jun-zheng，WANG Shou-kun，et al. Strategy of foot trajectory generation for hydraulic quadruped robots gait planning［J］.Journal of Mechanical Engineering，2013，49（1）：39-44.（in Chinese）

［5］ Crouse M S，Nowak R D，Baraniuk R G.Wavelet-based statistical signal processing using hidden Markov models［J］.IEEE Transactions on Signal Processing，1998，46（4）：886-902.

［6］ Choi H，Baraniuk R.Multiscale image segmentation using waveletdomain hidden Markov models［J］.IEEE Transactions on Image Processing，2001，10（9）：1309-1321.

［7］ Li J，Gray R M，Olshen R A.Multiscale image classification by hierarchical modeling with two dimensional hidden Markov models ［J］.IEEE Transactions on Information Theory，2000，46（5）：1826-1841.

［8］ 周建軍，林春生，趙建揚.無人飛行器背景磁場學習方法研究［J］.兵工學報，2014，35（1）：76-82. ZHOU Jian-jun，LIN Chun-sheng，ZHAO Jian-yang.Research on learning flight for unmanned aircraft in background magnetic field ［J］.Acta Armamentarii，2014，35（1）：76-82.（in Chinese）

［9］ 伍飛云，周躍海，童峰，等.可適應稀疏度變化的非均勻范數約束水聲信道估計算法［J］.兵工學報，2014，35（9）：1503-1509. WU Fei-yun，ZHOU Yue-hai，TONG Feng，et al.Non-uniform norm constraint estimation algorithm for underwater acoustic channels at the presence of varying sparsity［J］.Acta Armamentarii，2014，35（9）：1503-1509.（in Chinese）

［10］ 丁良宏.BigDog四足機器人關鍵技術分析［J］.機械工程學報，2015，51（7）：66-87. DING Liang-hong.Key technology analysis of BigDog quadruped robot［J］.Journal of Mechanical Engineering，2015，51（7）：66-87.（in Chinese）

［11］ 張天，楊晨曦，朱穎.多傳感器信息融合在四足機器人避障中的應用［J］.傳感器與微系統，2015（5）：150-153. ZHANG Tian，YANG Chen-xi，ZHU Ying.Application of multisensor information fusion in obstacle avoidance of quadruped robot ［J］.Transducer and Microsystem Technologies，2015（5）：150-153.（in Chinese）

［12］ Zhang T H，Wei Q，Ma H X.Position/force control for a single leg of a quadruped robot in an operation space［J］.International Journal of Advanced Robotic Systems，2013，10（137）：1-7.

［13］ Lei J T，Wang F，Yu H Y，et al.Energy efficiency analysis of quadruped robot with trot gait and combined cycloid foot trajectory［J］. Chinese Journal of Mechanical Engineering，2014，27（1）：138-145.

Ground Robot Multi-scale Road Perception Based on Semantic Tree MRF Model

DU Ming-fang1，2，WANG Jun-zheng1，LI Duo-yang1，HE Yu-dong1
（1.Key Laboratory of Intelligent Control and Decision of Complex System，Beijing Institute of Technology，Beijing 100081，China；2.College of Automation，Beijing Union University，Beijing 100101，China）

Road real-time perception is the key technology of autonomous ground mobile robot to realize autonomous navigation.But it is difficult to develop a road sensing algorithm because of the complexity and uncertainty of outdoor road environment.A multi-scale biomimetic road sensing algorithm in wavelet domain based on semantic tree Markov model is proposed.In time-space domain，the three-dimensional random field is used to express the road image sequence collected by robot.A road model named road best tree-Markov random field（RT-MRF）using the semantic tree structure Markov random field（MRF）is proposed.The genetic algorithm is used to optimize the supervised RT-MRF model for image segmentation of road sequences.The road recognition and autonomous navigation are realized through tracking segmentation boundary.An independently developed quadruped bionic robot is used as the research and experiment platform.The experimental results show that the proposed algorithm is a robust road image sequence segmentation method，which can be used under the poor detection conditions，such as shadow，cracks，holes，uneven and illumination change.And the real time of the algorithm is enough high to meetthe demand of outdoor mobile robot autonomous navigation.

control science and technology；quadruped robot；road detection；multi-scale biomimetic sensing；semantic tree Markov model；wavelet domain

TP391.41

A

1000-1093（2016）03-0512-06

10.3969/j.issn.1000-1093.2016.03.017

2015-03-24

國家自然科學基金項目（61103157）；北京市教育委員會科技計劃面上項目（SQKM201311417010）

杜明芳（1979—），女，副教授。E-mail：1314310@163.com