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

目前，基于机器视觉的障碍物检测方法大体上分为三类[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，称为正直线段；一种是GradValue0，称为负直线段。

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

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

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

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