自动化学报
ACTA AUTOMATICA SINICA
1997年 第23卷 第5期 Vol.23 No.5 1997



基于多传感器信息融合的机器人
障碍检测和环境建模
邬永革　黄　炯　杨静宇
摘　要　通过融合距离图象和彩色图象为移动式机器人构造二维环境模型及进行障碍检测.其中，环境模型采用了多分辨的二维网格表示结构，较好地解决了计算速度和模型精度之间的矛盾；融合算法的设计是以推广的Dempaser-Shafer证据理论(DSTE)为基础，较好地解决了融合信息的相关性问题；所论及的系统和算法已在真实环境下经过测试，其有效性已被实验所证明.
关键词　移动式机器人，环境建模，障碍检测，多传感器融合，证据理论.
MOBILE ROBOT OBSTACLE DETECTION AND ENVIRONMENT
MODELING WITH SENSOR FUSION
WU YONGGE　　HUANG JIONG　　YANG JINGYU
(Dept. of Computer Science, Nanjing Univ. of Sci. & Tech. Nanjing 210094)
Abstract　In this paper, modeling 2D environment and road detection for mobile robot by fusing color and range image information are discussed. The environment model is constructed using multiresolution 2D grid representation, which is proved to be a better solution to the tradeoff between accuracy and computation speed. The fusion algorithm is designed with a generalized Dempster-Shafer theory of evidence (DSTE), which is efficient in dealing with dependent information. The multisensor system and fusion algorithm are tested in real environment and their effectiveness is proved.
Key words　Mobile robot, environment modeling, obstacle detection, sensor fusion, theory of evidence.
1　引言
　　多传感器融合系统可以有效地解决单传感器的模糊点，更精确地观察和解释环境［1，2］.因此近年来多传感器融合系统越来越多地应用于各种智能系统，而移动式智能机器人的自动导航就是其中的一个重要应用.尽管在此领域内已做了大量的工作，但如何描述、处理所有传感器提供的观察信息并将它们融合成能用于导航的环境描述仍是一个没有很好解决的问题，特别是当机器人行驶在野外复杂的环境下.
　　本文主要讨论由激光测距雷达和彩色摄像机集成的移动式机器人上的视觉系统及其传感器信息融合问题.显然，由于彩色图象和距离图象之间的互补性，融合结果能更精确提供有关障碍物和行驶路径的环境信息.
　　信息融合的方法很多，其中Dempster-Shafer's证据理论(DSTE)是应用得较多的一种.但是DSTE在应用中要求合并的证据相互独立，这在许多实际应用中难以满足.例如，在本文所讨论的移动式机器人视觉信息的融合问题中就不满足信息独立的条件.因此，对DSTE作适当的推广，使其也能够处理相关信息是必要的.本文的信息融合算法就是基于推广的DSTE而提出的.
　　另外，在确定环境模型的结构时，本文在2维描述模型的基础上结合多分辨率分析方法，从而较好地兼顾了模型精度和计算速度两方面要求，同时2维环境模型也有利于机器人的道路规划和自主导航.
2　信息的描述和环境模型
　　对于一般的导航任务来说，只要判断在某一特定的道路区间是否有障碍物就够了，而无需其它更详细的描述.因此Elfes等曾提出了一种用于机器人导航的子空间标识法［3］，即通过标记“空区域”、“障碍区域”或“未定区域”来区分各个子空间(常被称为的格或单元)的状态.这种模型的最大好处是便于道路规划，但需要大量的内存和花费较多的计算时间.
　　作为一种改进，本文采用多分辨率的二维子空间标识法，它可有效地减少计算开销，同时保证较高的精度.
　　所谓多分辨率的2维子空间标识法，就是构造多层不同分辨率的2维道路标识图(见图1)，其中层次l,l-1,…，k(k＜l)分别具有2l×2l，2l-1×2l-1,…，2k×2k个单元或格，且任一层上的单元都与下一层中的一个2×2的子块相联系.

图1　多分辨率的2D网格图
　　基于多分辨率二维子空间标识法的环境模型构造过程如下：
　　1)构造道路的2维子空间图；建立摄像机和激光测距雷达到2维子空间图的投影变化矩阵Tc和Tr，并将经过预处理的彩色图象和距离图象信息投影到2维子空间图中；
　　2)在每个单元中进行信息融合处理，并根据融合的结果判断该区域代表的是空、障碍物还是未知的区域，这样就得到环境的一个2维标识图；
　　3)如果此标识图的分辨率满足要求即可终止，否则通过单元网格的分解建立下一层子空间图并将障碍区域和未知区域的信息投影到下一层子空间图中去；
　　4)转2.
　　上述环境模型具有一些很好的性质，如便于不同传感器信息的对应，便于信息融合和路径规划的实现等.
3　证据理论及其在传感器融合中的应用
　　Dempster-Shafer证据理论［5］(DSTE)是贝叶斯推理的推广，由于直观性强，易于描述以及在处理未知及等概率概念方面的有效性，因此被广泛用于多传感器信息融合及其它的人工智能问题.
3.1　DSTE的基本概念及其在多传感器信息融合方面的应用
　　在DSTE里，定义一集合Θ(称为鉴别框架)为某一领域内全部的不相容前提的集合，所有讨论的命题都是Θ的一个子集，DSTE定义了如下的基本概率分配函数(BPA)：

(1)
其中BPA的值大于0的子集称为焦点元素.
　　若m1是当前已知的BPA，当从一个新的独立证据源得到m2后，新的联合BPA可用如下的组合公式计算：

(2)
　　显然，在多传感器融合应用中，每个传感器信息对假设命题的影响可以用BPA函数来描述，而所有传感器信息的共同作用可由组合公式计算，因此DSTE适于解决融合问题.
3.2　D-S证据理论的推广
　　DSTE中的组合规则是在获取新证据(信息)后修改假设命题可信度的重要工具.但是，该规则只有在满足证据独立的条件下才有效，而证据独立是一个很强的条件，很多情况下都不能严格满足［5］.对于这类情况，虽然大多数的研究者假设其近似独立并直接使用Dempster's规则，但本文认为如果将相关证据简单地作为独立证据来处理必然会使融合结果超估计，因此在DSTE中解决相关证据的合并问题是很重要的，特别是在强调可靠性方面.文献［5—8］从几个不同方面讨论了相关证据的融合问题.本文介绍一个广义的证据组合规则，并以此来处理相关证据.
　　在DSTE中一个证据所提供的信息的多少和它产生的焦点元素有关，因此可以定义证据的信息容量E(Ev)如下：

(3)
其中｜Ai｜是焦点元素Ai的基数，n(Ai)是焦点元素的个数.
　　易知，E(Ev)∈［0，1］.若对于任意i,m(Ai)=0,则E(Ev)=0且证据Ev称为空.即Ev不包含任何有用的信息.若｜Ai｜=1且m(Θ)=0,则E(Ev)=1,Ev包含的有用信息最多.
　　设有两个证据Ev1和Ev2，其BPA函数为m1和m2，焦点元素为Ai和Bj.若它们是相关的则这种相关性一定会在它们的某些焦点元素上得到反映，称这种焦点元素为相关焦元，记为Dij,其BPA函数为mD，所含的信息量为

(4)
其中E(Ev1,Ev2)=0表示证据Ev1和Ev2相互独立，E(Ev1,Ev2)=1且E(Ev1)＜E(Ev2)(或E(Ev1)＞E(Ev2))表示Ev1被Ev2包含(或包含Ev2)，故E(Ev1,Ev2)可用于描述证据间的相关性.
　　定义1.证据Ev1和Ev2间的相关度为

(5)
　　定义2.证据Ev1对Ev2的相关数R12

(6)
　　证据Ev2对Ev1的相关系数R21

(7)
则Dempster证据组合规则可推广为定义3.
　　定义3.设证据Ev1和Ev2在同一鉴别框架Θ下的BPA函数分别为m1和m2，焦点元素集分别为
　　｛Ai,i=1,2,…,k｝和｛Bj,j=1,2,…,l｝.若则新的联合BPA为

(8)
其中

(9)

(10)
可以证明，由(8)式计算得到的BPA函数满足(1)式，且当R12=R21=0时退化为(2)式.
4　基于推广的DSTE的彩色和距离图象融合
　　对原始图象进行预处理，将其转化成以传感器为中心的直角坐标系下的绝对距离图象，并使其X-Y坐标平面为地面，则

(11)
其中R为激光测距雷达到采样点间距，ψ,ω分别为扫描线的仰角和水平转角，z0为测距雷达离地面的高度.
　　对于彩色图象，首先用一均值滤波器去噪声，然后通过聚类分析进行图象信息压缩，使之能用很有限的几类色彩值(r,g,b)来代表背景、道路区域和障碍物等.
　　用于融合的彩色图象和距离图象信息必须是描述同一区域的对应信息.信息的对应可以通过传感器校准，分别建立起彩色图象和距离图象信息到2维地面网格单元地图的变换矩阵Tc和Tr［9］来实现.由Tc和Tr分别投影到同一网格单元的距离图象和彩色图象信息被认为是可融合的对应信息，它们融合的结果作为标记网格单元为“空”，“未知”或“障碍物”的依据.
　　设定鉴别框架Θ为｛O，P，I｝，用以代表道路中的可通行区域(用P表示)，障碍物区域(用O表示，定义为高于地面28厘米的物体)和由于信息不足而无法确定的未知区域(用I表示).由于在绝对距离图象中包含了地面上坐标为(x,y)的点的高度z，所以能够很容易地从中抽取三类信息：网格单元的平均高度、单元表面的法向和地面(设为水平)的夹角α、单元高度分布的方差v；另外由彩色图象还可得到色彩值分布特征C(每个单元中出现的颜色值的集合)，所有这四种可作为确定每个网格单元所属类型的证据.现在的问题是
　　1)如何确定每个证据的BPA函数；2)如何确定综合两个证据后得到的新的BPA值.
　　为了确定每个证据的BPA函数，必须分析清楚所使用的证据(特征)和单元类型之间的关系.
　　1)易知，α=90°时单元表面为一平面，故单元中存在障碍的概率正比于fα=cosα.
　　2)理想情况下，地平面的高度分布方差(用v0表示)应为0，但由于噪声的影响v0常常大于0.尽管如此，当v≈v0时即可认为单元表面为地平面，故设单元中存在障碍的概率正比于
　　这里k是一常数.
　　3)一般情况下，如某个单元为地面区域，则在其周围一定存在着其它的路面单元.可以假设：道路是连续的，无突然的介质变化.所以，当根据值来判断一个单元是否为路面时应综合考虑它周围单元的值.为此定义一3×3窗口.设窗口内全部单元平均高度是且窗口中心单元的平均高度为，若趋于0且即中心单元的平均高度与周围的单元一致且接近0，则可认为中心单元为路面区域，因此可设中心单元为路面区域的概率正比于其中k是参数.
　　4)通常，道路区域上的色彩值的先验分布C0可以用统计的方法离线地确定.在路面连续且无明显的介质变化这一假设条件下(这在许多情况下都能被满足)，C0为定值.显然，如某一单元中颜色值的分布C与C0相近，则该单元属于路面区域的可信度较高，因此单元为路面的概率应正比于
　　易见，上述四个特征的BPA函数，mi(i=1,…，4)，不是简单函数，且没有一般的确定方法，因此只能根据大量实验的结果来确定它们的近似形式，如表1所示.
表1
　Φ｛O｝｛P｝｛I｝｛O，P｝｛P,I｝｛O,I｝Θ
m1(*)01-k1fαk1fα00000
m2(*)0k2fv2/3(1-k2fv)1/6(1-k2fv)01/6(1-k2fv)00
m3(*)05/6(1-k3fc)000
m4(*)0(1-k4fc)/3k4fc2/3(1-k4fc)0000

　　这里使用了由距离图象提取的三类特征，原因是距离图象的分辨率低而噪声非常强，作为补偿需要通过提高信息冗余度的方法来保证一定精度的融合结果.但另一方面，来自同源的三个特征(证据)之间显然不独立，因而Dempster组合规则不再有效，须使用上述广义的DSTE.
　　对于某一层上的每个单元，首先根据广义组合规则(8)式来计算单元中所有信息特征的综合BPA值，然后根据如下的分类准则确定该单元的所属类型(‘O’，‘I’，或‘P’).
　　1)所确定的目标类具有最大的BPA值；
　　2)所确定的目标类的BPA值与其它类的BPA值的差大于一阈值；
　　3)如果确定的目标类是‘P’，则其BPA值大于某一较大的阈值.
在上述分类准则中，1)假定可信度最大的类一定是目标类；2)要求对目标类的可信度必须充分大于对其它类的可信度；3)保证当所确定的目标类为‘P’时，它所具有的可信度非常高，从而可以保证机器人行驶的可靠性.
　　当所有的单元都被标记为‘P’，‘O’或‘I’后，一个2D环境模型就构造出来了.若需要更为精确的模型，可对所有的信息特征进行细化，然后投影到下一层网格图上以进一步进行融合.
5　实验结果及分析
　　为了验证上述融合方法的有效性，已在室外做了一系列有代表性的实验，包括多种路面情况，如有、无障碍；平直、交叉道路等.图2和图3为实验环境之一；有障碍物的道路，其中图2为经过预处理的彩色图象，图3为经过预处理的距离图象.图4是由上述融合算法构造出的2D地面结构模型，其中标记为‘O’的是障碍物，‘P’为空区域，‘I’为少数几个未定区域，正如所看到的，图4的分辨率较低.另一方面，由于在本文的融合算法中为单元分类准则(3)设定了一个较高的阈值，它虽然可以确保标记为‘P’的单元中不会有障碍物，但同时会产生较高的虚警率，一些没有或仅有部分区域被障碍物侵占的单元整个被标记为‘O’.故在图4中，标记为空的路径很窄机器人无法通过，而道路的实际情况并非如此.这时机器人要想正确地进行道路规划必须要有更高精度的道路模型.通过投影和细化操作在图4的基础上进一步融合即可得到如图5所示的更高分辨率的环境模型，它标记出的障碍物位置更精确.显然，通过重复该过程还能得到更高分辨率的环境模型.

图2

图3

图4　8×8分辨率的融合结果

图5　16×16分辨率的融合结果
　　所有的实验结果表明本文提出的方法稳定可靠.所采用的基于多分辨率的2D道路模型描述结构不但便于实现信息融合和道路规划，而且明显地降低了计算量.另外所提出的基于推广的DSTE的信息融合算法有效地解决了融合信息的相关问题，提高了融合结果的可靠性.
作者简介：
　　邬永革　1968年生.1990年毕业于南京大学数学系，1993年在南京理工大学计算机系获硕士学位.讲师.研究方向为：计算机视觉、信息融合等.已发表论文20多篇.曾获部级科技进步一等奖.
　　黄　炯　1993年和1996年在南京理工大学分别获学士和硕士学位，现为南京同创信息产业集团总经理助理.目前的研究兴趣为：神经网络控制等.
　　杨静宇　南京理工大学计算机系主任、教授、博士生导师.研究兴趣为：计算机视觉、智能机器人等.已出版著作6部，发表论文80多篇，曾获省部级以上科技奖九项.
作者单位：南京理工大学计算机系　南京　210094
参考文献
［1］　邬永革，杨静宇.多传感器数据融合的概念、方法和实现.机器人，1995(增刊)：564—568.
［2］　杨静宇，邬永革等.战场数据融合技术.北京：兵器工业出版社，1994.
［3］　Elfes A. Using occupancy grids for mobile robot perception and navigating. IEEE Computer, 1989, 21: 46—57.
［4］　shafer G. A mathematical theory of evidence. Princiton, NJ:Princiton University Press, 1976.
［5］　Voorbraak F. On the justfication of Dempster's rule of combination. Artifical Intelligence, 1991 48:171—297.
［6］　Bazzi Y A, Mitchell B T. Reasoning under uncertainty with dependency information.proceeding of SPIE, 1988, 1003: 188—193.
［7］　Cheng Y Q, Wu Y G et al. Generalized integration method of evidence with dependency information. In:Proceeding of SPIE, 1992, 1828:288—293.
［8］　肖人彬等.相关证据合成方法的研究.模式识别与人工智能，1993，6(3)：227—234.
［9］　Liu K et al. Calibration of multiple sensor by a planar calibration object. In:proceeding of SPIE, 1993, 1828: 499—509.
收稿日期　1995-12-12
