基于语义树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