基于直线段匹配的移动机器人的障碍物检测

目前，基于机器视觉的障碍物检测方法大体上分为三类[1]。第一类方法是从单幅图像中提取已知的障碍物[2]。这种方法的缺点是需要已知障碍物的2D图像模式，或者需要一个学习阶段。第二类方法是利用运动信息提取障碍物，其中最流行的方法是基于光流的障碍物检测[3]。该类方法的缺点是运算量大，而且基于所求出的光流场分割障碍物仍然很困难。第三类方法是利用立体视觉方式提取障碍物，该类方法运算量大，通常需要专用的硬件[4]。本文提出的方法属于第一类方法，但是省去了学习过程。此方法利用人们如下的先验知识：因为大多数人造物体呈现为棱柱状、棱台形状或者圆柱、圆台形状，这些形状左右边缘表现为两条直线段(如电线杆、灯柱、箱子、椅子、桌子等)，而且这两条直线段中的像素点的梯度方向应该是对称的，所以检测出这些近似直线段的边缘就可以重构物体轮廓，从而定位目标。

本文提出的算法主要由三步组成：首先计算原图像中边缘点的梯度值和梯度方向，并且按照"同一条直线段中像素点的梯度方向、梯度值相近似"的原则从边缘点图像中提取出直线段；然后利用提取出来的直线段的各种属性(长度、梯度方向、位置)、两条直线段之间像素点的灰度直方图以及背景灰度直方图对直线段进行匹配，搜索出分别对应于各个物体左右边缘的两两相对的直线段；最后按照匹配函数计算出匹配值重构"障碍物"轮廓，并确定其位置。

1边缘点的提取

本文使用Soble算子(如图1)计算边缘点梯度值，并利用公式(1)～(3)计算出梯度向量的方向角，从而构造梯度图像[5]。本文采用一种基于视觉模型的边缘检测阈值选择策略[6]进行梯度图像的自适应阈值的设定，即利用公式(4)进行阈值设定。

式中，Gx是Soble算子的水平模板；Gy是Soble算子的垂直模板；α(x，y)是梯度向量的方向角；I为背亮度灰度值，也就是象素点的灰度值，I小于a的区域为低暗区，I大于b的区域为高亮区，I在a和b之间为中间区；△I为所定阈值，灰度级为256级；α、β和C为待定参数。

对梯度图进行"空穴捡出"，删除由相互连通的边缘点组成的小块区域。因为小块区域大多由噪声产生，就算是真正的边缘点，它们对算法也不起作用，所以可删除它们以降低算法复杂度。

2直线段的提取

通过综合相位编组法与边界跟踪法的优点，本文提出一种新的直线段的提取方法。这种方法能检测到阶跃形和屋顶形的直线边缘，同时也适用于单像素和多像素宽度的直线边缘的检测。

首先，对边缘点的梯度向量的方向角进行方向离散化，即将其分为0度、45度、135度、180度、270度和315度六个方向类型(如图2)。边缘点的梯度向量的方向角与哪个方向类型的差最小，就把边缘点归为哪个类型。同属于一个方向类型的边缘点互为"同类型边缘点"，同属于一个类型的直线段互为"同类型直线段"。

然后，在垂直于梯度方向角度的方向上的邻域内依次对连通的同类型边缘点搜索并连接，组合成的集合称为线段子元。由于物体的边缘可能出现断裂，以及边缘大多不是单像素宽度，所以还要对线段子元进行组合，构造线段元[7]。

定义1线段子元：连通的同类型边缘点的集合。

定义2线段元：同类型的并且相互间有连接点的线段子元组合成的集合。

由以上的定义可知，线段子元是线段元的子集，一个线段元可由一个也可由多个线段子元构成。本算法的输入是梯度图，输出是对应图像中物体左右边缘的各条线段。整个算法流程如下所述。其中，line-Sub-Cell、line-Cell和line-Segment分别表示存储线段子元、线段元和线段的结构。

Step1：依次扫描梯度图像，取第一个未检测到的边缘点为边界跟踪起点Pi(i=0)。将Pi作为第一个像素保存到线段子元line-Sub-Cell中。

Step2：i=i+1，利用边界跟踪算法沿着跟梯度方向垂直的方向跟踪下一个边界点，根据定义1确定Pi是否属于当前线段子元line-Sub-Cell。若属于则将Pi保存到Line-Sub-Cell中，重复Step2；否则当前线段子元Line-Sub-Cell即为一个完整的线段子元，将其保存，并转Step1。

Step3：对存储了线段子元的数组依次扫描。取第一个未检测到的线段子元为初始线段子元Qj(j=0)。将Qj作为第一个线段子元保存到线段元Line-Cell中。

Step4：j=j+1，根据定义2判断Qj是否属于当前线段元Line-Cell。若属于将Qj加人Line-Cell中，然后重复Step4；否则当前线段元Line-Cell即为一个完整的线段元，并转Step3。

Step5：按照以下的准则(准则1)合并线段元Line-Cell，构成直线段line-Segment。

准则1：判断线段元Line-Cell是否属于线段line-Segment的准则，判断两线段元的端点是否相邻(或接近)，并且两线段元斜率的偏转角是否接近。若满足上述条件即可将两线段元连接起来，则形成一条较长的线段。

3直线段的两两匹配与轮廓重构

因为一个物体的左右两边边缘点的梯度方向应该具有相互对称的属性，所以按照直线段上边缘点的Gy的值GradValue(见公式(2))将直线段分为两种极性：一种是GradValue>0，称为正直线段；一种是GradValue<0，称为负直线段。

首先，从包含所有正直线段的集合D1和包含所有负直线段的集合D2中依次各选取一条直线段。如果选取的两条直线段满足以下三个条件，则称它们是一组"候选直线段对"[8]。

(1)图像中这两条直线段中心点的位置在Y坐标轴上的差小于一个阈值P1，在X坐标轴上的差大于一个阈值P2。P1、P2的值可根据图像大小设定。

(2)两条直线段的长度相差不大。

(3)两条直线段的梯度方向对称。假设左边的直线段为正直线段，右边的直线段为负直线段，则左右两直线段的梯度方向如图3所示。如果左边的直线段为负直线段，右边的直线段为正直线段，则把将梯度方向互换一下位置即可。[!--empirenews.page--]

然后，根据每组"候选直线段对"间内部像素点的灰度直方图计算这两条线段的相关性。因为属于同一个物体的像素点的灰度直方图有一个明显的凸峰，所以把凸峰占整个直方图面积的百分比作为计算"候选直线段对"相关性的第一个度量值定为inner_rela。

属于物体中的像素点的灰度值与它所处背景的像素点的灰度值相差比较大。所以把计算"候选直线段对"相关性的第二个度量值定为

。T1为两直线段间像素的灰度平均值，T2为两直线段构成区域的背景灰度平均值。因为

，所以把exter_rela除以255(作归一处理)，使得

。

总的相关性度量值=inner_rela×exter_rela。如果总的相关性度量值超过一定的阈值，则这一组"候选直线段对"属于同一个物体的左右边缘。

inner_rela的计算方法介绍如下：

Stepl：计算这两条直线段之间的区域中的像素点的灰度分布直方图。

Step2：直方图存在一个明显的凸峰，计算出凸峰的位置Peak，并取凸峰邻域为[Peak-T，Peak+T]，本文取T=32。对灰度值处在凸峰邻域[Peak-T，Peak+T]的像素点的个数进行累加，累加值Count存储到变量中。

Step3：inner_rela=Count／(整个直方图象素点的总数)。

最后，把配对成功的"候选直线段对"的相应端点进行连接，构造出的四边形作为物体的抽象轮廓。因为这些四边形之间会产生连接、包含、重叠等现象，所以取经过轮廓叠加产生的图像做为最终目标图像，从而在图像中实现对物体的定位。

4实验分析

本算法在室内进行了大量实验后发现，对图像中存在的棱柱状、棱台形状物体以及圆柱状、圆台形状物体能够实现90％的检测率；而对边缘为曲线的物体以及其他不规则物体的检测就根本不适用了。当评判匹配相关性的阈值设得偏大时"漏检"的概率变大，"伪检"的概率变小，反之亦然。

本文算法对于一副图像的测试结果如图4(a)～(e)所示，移动机器人平台上的彩色CCD摄像头拍摄的图像包含了一个纸箱、一个叠加在纸箱上的黑色钢管以及一个低矮的黄色木头盒子。对彩色图像运用颜色转换程序，转换成灰度图(图4(a))；在线段图(图4(d))中灰度值为128的线段是负线段，灰度值为0的线段是正线段；输出的最终结果(图(4)e)中直线配对每成功一次，相应的区域像素点的灰度值减去100。

本文提出的利用直线段匹配检测障碍物的方法，不需要事先学习障碍物的2D图像模式，避免了使用计算量大的光流法和立体视觉方法。试验结果表明该方法能有效地实时检测障碍物。

下一步还需要研究如何将图像检测出的障碍物信息与移动机器人的激光雷达数据相融合，以及加入距离信息来提高障碍物检测的准确率和可靠性。