边界与区域相融合的非结构化道路检测算法_尹建新

计 算 机 工 程 第 34 卷 第15期

Vol.34 No.15 Computer Engineering ·人工智能及识别技术·

文章编号：1000—3428(2008)15—0217—03

文献标识码：A

2008年8月

August 2008

中图分类号：TP391.41

边界与区域相融合的非结构化道路检测算法

尹建新，莫路锋

(浙江林学院信息工程学院，临安 311300)

摘 要：为了提高非结构化道路识别算法的有效性，提出在运用图像分类和使用归一化彩色分量进行判断的基础上，充分利用图像的边缘信息，通过将图像边界范围、边界走向趋势与区域分类的结果相融合，得到道路的边界。使用Kalman滤波器对道路进行跟踪，处理了由于石阶等原因造成的路面扩大、路与非路交界区模糊难以区分和道路受阴影影响等实际情况。实验结果表明，该方法简便有效，能适应各种不同的非结构化道路，具有一定的鲁棒性。

关键词：非结构化道路；Kalman滤波；图像分类；归一化彩色分量

Measurement Arithmetic for Unstructured Road

Based on Boundary and Region

YIN Jian-xin, MO Lu-feng

(School of Information Science and Technology, Zhejiang Forest University, Lin’an 311300)

【Abstract】In order to enhance the validity for the unstructured road recognition, this paper makes full use of the picture edge informationafterimage classification and judgment of normalized color tristimulus coefficient to get the boundary data of the road through the image boundary scope,the boundary line tendency and the region classification. The following step should be tracking the path with Kalman Filter(KF), which solves theproblem of road surface expansion, vagueness in road and un-road border area and shadow influence due to stone steps. The experimental resultindicates that this simple and effective method adapts to every kind of different unstructured road and has certain robustness. 【Key words】unstructured road; Kalman Filter(KF); image classification; normalized color

智能车自主导航时采用何种导航方式，以及道路检测算法的实时性与鲁棒性等，一直是研究的一个探索热点[1-3]，采用机器视觉导航是当前导航技术研究领域的主流方向[4-6]。要使智能车能够自主导航，它必须能够跟踪道路的变化和检测车道内的障碍物。目前，对结构化道路环境的识别算法已经相对成熟，而对于非结构化道路环境来说，由于这类道路没有车道线和清晰的道路边界，加上户外的自然场景受季节、光照、阴影和水迹地等影响，道路区域和非道路区域难以区分，因此针对非结构化道路的检测技术尚处于研究阶段[6]。

1 算法分析

道路图像的分割算法既要讲究分割的准确性，也要考虑处理速度。

通过对现有道路图像分割算法的研究，结合道路图像的彩色信息特征和道路边缘信息特征，提出了一种简单、有效的道路图像实时分割算法：

(1)本文对非结构化道路算法先采用基于道路知识的区域分割法得到基本的可通行范围；

(2)选用边缘检测法得到道路边界，使用不同的彩色分量和图像的边缘信息，对分割的结果进行修正和约束，再把范围和边界进行融合，得到准确的可通行区域；

(3)通过道路曲线模型和Kalman滤波器对道路的边界进行跟踪和预测。

实验结果表明，该方法具有较高的实时性，符合智能车辆实时导航的要求。

该算法具体流程如图1所示。

图1 算法流程

2 图像处理

2.1 图像预处理

图像在数字化过程中会产生随机噪声，直接进行直方图

作者简介：尹建新(1973－)，女，讲师、硕士，主研方向：模式识别，数字图像处理，计算机视觉；莫路锋，讲师、博士研究生 收稿日期：2007-08-07 E-mail：yjxzlm@http://wendang.chazidian.com

—217—

分割一般都会有小峰，影响到图像的进一步分析。

去噪技术一直都是图像处理的一个重要课题，在除去噪声的同时应尽量地保留边缘。本文中处理的方式是使用3×3滑动窗口的中值滤波和高斯金字塔降噪滤波[7]。中值滤波法是常用的图像去噪方法，能较好地滤除椒盐类噪声。但中值滤噪同时也模糊了图像的细节，而高斯金字塔是一种多分辨的信号分析和表示方法，它将图像分解为不同空间分辨率的图像簇，以便提取不同层次的结构特征，并且可用这些图像簇精确重构原图像。试验结果证明在中值滤噪的图像上使用高斯金字塔降噪技术，可以全面地消除随机噪声的影响，大大改善图像的质量，较好地保留清晰的图像边界[8]。 2.2 彩色变换

通过实验发现，道路颜色一般是比较均匀的，而且在分布上基本有规律可寻。对于采集到的彩色道路图像，直接在RGB空间上分割比较困难，所以需要先进行彩色变换，把RGB三维降到一维，然后利用灰度图像分割把道路和非路分开。考虑到降维后丢失了一部分信息，因此采用多种彩色变换来得到较好的结果。考虑到路面颜色的分布范围，在本文中采用如下3个彩色变换：

I1=(R+G+B)/3

I2=B R+128 I=B G+128 3

如图2所示。

非路区域需要重新判断

道路均值所属峰

图2 直方图为2个峰的情况

归一化分量：

r=

RGB

,g=,b= (1)

R+G+BR+G+BR+G+B

其中，I1是亮度，是最主要的区分道路和非路的特征，一般

而言，在图像中道路和非路在亮度上差别最大，因此它是作C1+C2

l= (2)

为主要特征来得到图像的初步分割；I2, I3反映了颜色偏蓝的2

对在峰尖中点一定范围内的灰度级所对应的像素点进行程度，一般而言，道路的颜色往往是中性灰略偏蓝，而道路

重新归类。 阴影部分由于光源主要来自天空的反射光，因此一般更偏蓝

road if(dis(valuei Nmeanroad))<dis(valuei Nmean~road)一些，而水迹如果不是反射周围场景，则一般也都是黑中带

wi∈

蓝，而对于组成非路的如泥土、植物等往往是偏绿、偏红或 ~road else

(3) 偏黄，因此它们是作为分类器进一步细分图像所依据的特征。

其中，wi是原始灰度值满足|grew(wi)-l|<Thr的像素点；Thr

2.3 直方图分割

是离2个峰尖中点的一定范围值；valuei为对应的Wi的归一通过直方图对预处理的图像进行分割，对于相邻的2个

化值；Nmeanroad,Nmean~road分别是由前一帧图像得到的道路峰之间的分界，根据谷的形状采用了如下的策略：(1)对于尖

区域和非路区域在当前帧对应区域的归一化平均值。如果是锐的谷，采用谷点求阈值；(2)对于平坦的谷，采用类间距离

第一帧，道路区域选取图像上方一小块区域作为道路区域，最大的方法来求阈值。这样做是因为求谷点比类间距离最大

而非路区域则选取非路类中灰度级与l相差Thr以外的那些所需要的计算量小，而大部分情况下遇到的谷都属于比较尖

像素点所在的区域。 锐的，所以，这样可以减少平均计算量。

通常，分类出错源于光照的强弱和一些局部阴影的影响，同时还可能受到相机电源的干扰，为了尽量少受这些情况的影响，算法中采用了通常所使用的减弱光照强度和阴影影响的方法——归一化彩色分量法。对于每一个彩色分量，通过除以亮度(R+G+B)来获得相应的归一化图像分量，对于归一化的图像分量，一方面可除去亮度对整个图像的影响，另一方面还能减弱外界干扰并能充分利用周围环境的彩色信息。

判断准则：

首先将道路均值所在的一类划为路面类road，该类的中心为C1，其他的为非路面类~road，该类的中心为C2，2个峰尖的中点为l。

3 后处理

图形即使在预处理以后仍然可能存在一些小峰，因此，这时得到的峰还需要根据以下3个原则将假峰删除：

原则1 真峰必须具有一定的峰高。 原则2 真峰必须具有一定的面积。 原则3 真峰必须具有一定的峰谷比。

对直方图进行分析，只有1个明显的峰，根据其均值和方差将1个峰分成2个部分。有2个明显的峰，直接将图像二值化。有2个以上的明显峰，则通过合并成3个峰，具体选择方法为：道路平均值所在的峰为一个峰，其他的合成 2个峰。

3.1 双峰情况的后处理

使用归一化图像分量对2个峰的情况进行再判断直方图分割以后，原始图像被分成了2类。对于这个分类的结果，要防止在2类中可能存在的错误分类。 一般如果存在分类错误，则错误往往是在2个峰尖之间的那些灰度级，因此，对于2类的情况，将对2个峰尖一定范围的灰度级做重新判断， ——218

3.2 多峰情况的后处理

对比道路均值所在峰灰度低的那部分进行阴影的判断，如图3所示。

非路区域道路均值所属峰

非路区域所属峰

在该峰下进行阴影的判断

图3 直方图为3个峰的情况

设每个像素点的RGB分量分别为r,g,b，与道路区域的平均RGB分量为rm,gm,bm。相应的分量差为bg=b-g,br=b-r, bmgm=bm-gm,bmrm=bm-rm。根据研究表明，在阴影区域，RGB分量在同时衰减的情况下，蓝色分量衰减得最少，绿色分量次之，红色分量衰减得最多。因此，当bg>bmgm且br>bmrm时，表明像素点是在阴影下的道路区域中的点，将该点归为道路区域，反之则归为非路区域。

4 获取图像的基本范围

如果仅仅对原始图像进行边缘提取，将会得到很多虚假的边界，而这些边界将严重影响最后的融合结果。在本文算法中使用Sobel算子来提取图像的边界。在提取边界之前，先对原始图像进行去噪处理，然后在由前一帧图像得到的道路边界的基础上设定一个粗略的范围，使用这个范围中的边缘信息来与区域分类的结果进行融合，这样既能够避免虚假边缘的影响，又能防止道路的扩大化。

最后，采用数学形态学对二值图进行平滑处理，使道路区域的边缘相对平滑。

6 道路边界的提取与道路状态的更新

移动机器人的定位问题也可以看作是一个随机统计系统内的状态滤波问题或状态估计问题。一个随机统计系统可以用下列的动态方程和测量方程表示：

Xk+1=f(Xk,Uk)+ωk,Zk=h(Xk)+νk (6) 其中，函数f()和h()分别是系统动态方程和测量方程，对系统状态而言，也就是机器人位置进行递归的估计。

Minimum Mean Square Error(MMSE)估计是以先前所有观测信息为条件的条件期望，条件期望的计算要求非常大的计算量，一个常用的方法是把统计随机系统看作是一个Markov模型，并且系统状态的概率分布是高斯函数概率分布函数。如果机器人的运动模型和传感器的观测模型是线性的，各种动态不确定和观测不确定是相互独立的高斯变量，则条件概率密度函数是高斯的，它的均值和方差可以用一个递归的Kalman Filter(KF)算法来计算。这个滤波器提供了在MMSE意义上的最优状态估计。Kalman滤波估计是可靠的、鲁棒的、容易执行的，所以广泛用于系统的状态估计。

通过前面的工作，一个二值化的图像确定了道路与非路的区域。通过提取这个二值图的外围轮廓，可以分别得到左右边界点。根据Kalman滤波器预测的结果，当前的边界点变化过大时将被滤除掉。最后对左右边界点进行跟踪，并更新道路的状态。本文使用二次曲线作为道路的模型，然后利用Kalman滤波器对道路的左右2个边界进行滤波与跟踪。

道路二次曲线模型：

x=a2y2+a1y+a0 (7)

5 区域和边界的融合

在得到道路边界的大致范围和走向趋势后，将这个处理

结果和区域分类的结果进行简单的取与操作。这里规定区域分类后的二值图中白色区域为路面类，黑色区域为非路类。而经过Sobel算子提取的边界图中边界为黑色。在取与操作的同时，进行形态学的处理，通过膨胀腐蚀等运算将那些可能扩大的路面区域去除掉：

Imageregion=Imageregion⊕SImageregion=Imageregion∩ImageedgeImageregion=Imageregion SImageregion=Imageregion⊕S

(4)

其中，Imageregion, Imageedge分别表示区域图像和边界图像；S为结构元素；⊕, 分别表示膨胀和腐蚀运算。

区域和边界融合结果如图4所示。

Kalman滤波器方程：

(a)原图 (b)直方图分割结果

****Xk=φk,k 1Xk 1+Kk[Zk Hkφk,k 1Xk 1]T*TKk=Pk*,k 1Hk[HkPk*,k 1Hk+Rk] 1

Pk*,k 1=φk,k 1Pk* 1φkT,k 1

*Pk*=[I KkHk]Pk*,k 1

(8)

*

其中，Xk为道路k时间的状态估计向量；φk,k 1为状态转移矩

阵，这里为单位矩阵；Pk*为估计误差方差矩阵；Hk为观测

(c)边界趋势图 (d)区域和边界融合

*

为Kalman增益；矩阵；Pk*,k 1为一步预测误差方差矩阵；Kk

Zk是观测序列；Rk为系统观测噪声。

图4 区域和边界的融合处理结果

通过区域合并，得到了一个二值的图像。由于前后2帧

相隔的时间极短，所以从整体趋势上看，路面区域应该不会变化很大，因此，如果前后2帧出现大的变化，将认为结果可能出现了错误。通过将前后2个处理的结果——2个二值化的图像一一进行分析与对比，可以防止这种突变情况的出现。对于变化部分，记录下这个变化，如果在接下来的一帧中还出现这种变化，将视这种变化是存在的、正确的，在下一帧里将接受这种变化，用公式表达如下：

wi∈roadframe&wi∈~roadframe&fflag ~road

wi∈

wi∈~roadframe&wi∈roadframe&fflag road

(5)

wi∈roadframe&wi∈~roadframe road,f flag

wi∈

wi∈~roadframe&wi∈roadframe ~road,fflag

j

j+1

i

j+1

j 1

j

j 1

j

以T=0.14 s采集一帧图像为实验，得到Kalman滤波结

果如图5~图10所示。

图5 t=1T时的滤波结果 图6 t=2T时的滤波结果

其中，wi为像素点；framej表示第j帧；fflag表示变化的像素点所组成的集合，它们均被标记过了。

图7 t=3T时的滤波结果 图8 t=4T时的滤波结果

（下转第222页）

—219—

4 实验数据分析

本节通过实验分别对随机选择策略、词频选择策略及基于相关度的关键词选择策略进行效能评价。实验中Deep Web网站为新浪网http://wendang.chazidian.com和搜狐网http://wendang.chazidian.com。 图3反映了每种策略下查询的提交次数与检索到的文档覆盖率之间的关系。可以看出，词频选择策略和相关度选择策略的覆盖率要远远高于随机选择策略。而在达到相同的覆盖率的时候，基于相关度的关键词选择策略提交的查询次数要比词频选择策略少。例如，要达到80％的覆盖率，词频选择策略要提交大约330次查询，而基于关键词相关度的策略只要280次左右。

随机策略

100

80 覆盖度/(%)

60 40 20 0

词频策略

相关度策略

包括如何发现这些接口的问题[7]。另外，大部分Deep Web返回查询结果都是分页显示的，用户需要点击下一页来浏览更多结果。在这种情况下，爬虫应该能确定当前页是否返回了所有结果并能自动地“点击”下一页。由于本文提出的方法是在Deep Web查询接口属性单一的情况下，因此下一步的工作主要是如何将这种策略在多属性结构的查询接口上进行扩展[8]，以更好地适应Deep Web，并提供更为全面的信息检索服务。

参考文献

[1] Bergman M K. The Deep Web: Surfacing Hidden Value[EB/OL].

(2001-07-01). http://www.press.umich.edu/jep/07-01/bergman.html. [2] Chang K C C, He B, Li C, et al. Structured Databases on the Web:

Observations and Implications[J]. SIGMOD Record, 2004, 33(3): 61-70.

[3] He Bin, Patel M, Zhen Zhang, et a1. Accessing the Deep Web: A

Survey[EB/OL]. (2004-10-18). http://eagle.cs.uiuc.edu/tr/dwsurvey- tr-hpzc-ju104.pdf.

[4] Arasu A, Garcia-Molina H. Extracting Structured Data from Web

Pages[C]//Proc. of the ACM SIGMOD International Conference on Management of Data. San Diego, California, USA: ACM Press, 2003: 337-348.

070 140 210 280 350

查询次数/次

[5] He H, Meng W, Yu C, et al. Wise-Integrator: An Automatic

Integrator of Web Search Interfaces for E-commerce[C]//Proc. of the 29th Int’l Conf. on Very Large Data Bases. San Fransisco, USA: Morgan Kaufmann Publishers, 2003: 357-368.

[6] Cormen T H, Leiserson C E, Rivest R L. Introduction to

Algorithms[M]. 2nd ed. [S. l.]: MIT Press/McGraw Hill, 2001. [7] Cope J, Craswell N, Hawking D. Automated Discovery of Search

Interfaces on the Web[C]//Proc. of the 14th Australasian Conference on Database Technologies. 2003.

[8] Chang K C C, He B, Zhang Z. Toward Large Scale Integration:

Building a MetaQuerier over Databases on the Web[C]//Proc. of the 2nd Conference on Innovative Data Systems Research. Asilomar, California, USA: [s. n.], 2005.

图3 3种关键词选择策略的覆盖率比较

5 结束语

传统的爬虫只能通过链接来发现和下载网页，因此对于只能由查询接口访问的Deep Web，它们便不能到达。本文提出了一种新的基于相关度的关键词选择策略，通过关键词的相关性得分来确定在查询接口进行的查询。实验证明该方法在对Deep Web进行爬行时比随机策略和词频选择策略更为有效。

本文仅提出了一个针对Deep Web爬虫爬行策略的理论框架，要设计一个这样的爬虫还有很多实际问题需要解决。例如：这里假设爬虫已经知道要爬行的接口站点，而实际中

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

（上接第219页）

通科技, 2005, 22(5): 132-134.

[2] 杨 明, 陆建业. 基于视觉的道路跟踪[J]. 模式识别与人工智能,

2001, 14(2): 186-193.

[3] Yang Ming, Lu Jianye, Wang Hong, et al. Vision-based Real Time

Vehicle Guidance on THMROV[C]//Proc. of the International

图9 t=5T时的滤波结果 图10 t=6T时的滤波结果

Symposium on Test and Measurement. Shanghai, China: [s. n.], 2001.

[4] 刘化胜, 王友仁. 车辆视觉导航系统中的实时道路检测[J]. 计算

机测量与控制, 2004, 12(10): 901-904.

[5] 苏开娜, 易小琳. 基于运动模型的道路识别与跟踪算法的研

究[J]. 中国图象图形学报, 2000, 5(3): 226-231.

[6] 管琰平, 贺 跃, 刘培志, 等. 基于彩色图像的非结构化道路检

测[J]. 计算机应用, 2005, 25(12): 2931-2934.

[7] 李 青, 郑南宁, 马 琳, 等. 基于主元神经网络的非结构化道

路跟踪[J]. 机器, 2005, 27(3): 247-251.

[8] 杜 歆. 一种基于动态规划的道路图像分割算法[J]. 传感技术

学报, 2004, (3): 386-389.

7 结束语

由于智能车要求道路场景的识别算法具有很强的实时性，根据系统选定的采样周期，必须在0.2 s之内处理完一帧图像并送出指令，因此车道边缘的检测必须在0.15 s左右完成。利用笔者所提出的算法已能满足这个要求。关于障碍物的识别与跟踪，还有大滩能反光的水迹等问题的研究，将在以后的论文中叙述。

参考文献

[1] 孙 涵, 任明武. 基于机器视觉的智能车辆导航综述[J]. 公路交

——222