1、 第 47 卷第 8 期 2011 年 4 月 机 械 工 程 学 报 JOURNAL OF MECHANICAL ENGINEERING Vol.47 No.8 Apr. 2011 DOI：10.3901/JME.2011.08.141 应用多阶动态规划的车道线识别方法* 高德芝 段建民 杨 磊 杨喜宁 (北京工业大学电子信息与控制工程学院 北京 100124) 摘要：根据图像中车道线特征，提出一种应用多阶动态规划的车道线识别算法。为准确识别车道线，算法利用非均匀 B 样 条曲线拟合车道线，通过多阶动态规划确定非均匀 B 样条曲线的控制点。根据多阶动态规划的起始点和目标点确定车道线 检测区域
2、，进行区域分割确定动态规划的阶数，确定控制点的候选点；根据定义的代价函数和最优化原理，利用多阶动态 规划确定曲线的控制点；拟合车道线，实现车道线的识别。处理各种路况的视频图像进行算法验证，试验结果表明，对于 实车道线和虚车道线的直道、左转、右转的多种路况条件下，算法能有效准确地提取车道线的参数，稳定地实现车道线的 识别。 关键词：B 样条曲线拟合 多阶动态规划 车道线识别 中图分类号：TP39 Lane Recognition Method Using Multi-stage Dynamic Programming GAO Dezhi DUAN Jianmin YANG Lei YANG Xi
3、ning (College of Electronic Information & Control Engineering, Beijing University of Technology, Beijing 100124) Abstract： According to the characteristics of lane lines, the algorithm of lane line recognition based on multi-stage dynamic programming is proposed. In order to recognize the lane lines
4、 accurately, non-uniform B-Spline curve is used to fit the lane lines. The multi-stage dynamic programming is introduced to determine the control points for B-Spline curve. In the algorithm, firstly, according to the region of detection determined by the starting and target points, the candidate con
5、trol points and the order are obtained after image segmentation. Then, the control points are selected according to the defined cost function and optimization principle. Lastly, the lane lines are fitted so as to realize the recognition thereof. The proposed method is applied to a variety of images,
6、 and the experimental results indicate that the algorithm can extract the lane line parameters accurately and effectively for straight line, curved line, continuous line and dotted line, and realize lane recognition stably. Key words：B-Spline curve fitting Multi-stage dynamic programming Lane line r
7、ecognition 0 前言* 在智能车辆技术研究领域，车道线识别无论是 对于车道保持系统还是车辆自巡航系统或是车道控 制系统都是一项关键技术。目前，机器视觉是实现 车道线识别的常用传感器。基于机器视觉的车道线 识别方法可分为基于区域的方法1、基于特征的方 法2和基于模型的方法3。其中最常用的方法是基 于模型的车道线识别算法，其实质是利用图像中车 北京市教育委员会科技创新平台资助项目(JJ002790200802)。 20100728 收到初稿，20101228 收到修改稿 道线特征点与车道线几何模型相匹配，实现车道线 的识别。目前，基于模型的车道线识别算法中，常 用的道路模型有直线模型4、
8、二次曲线模型5、三 次曲线模型6、组合模型7、Snake 曲线模型8和 B 样条曲线9等。鉴于以上研究，在研究非均匀 B 样 条曲线、分析车道线的特征的基础上，利用非均匀 三次 B 样条曲线拟合车道线。 利用非均匀三次 B 样条函数10进行车道线拟 合时，控制点的提取是关键。为了利用样条函数实 现实车道线和虚车道线的拟合，研究多阶动态规划 原理，提出了利用多阶动态规划求取样条曲线控制 点的算法。文中对多阶动态规划代价函数的确定以 机 械 工 程 学 报 第 47 卷第 8 期期 142 及车道线识别算法进行了详细的叙述。 1 非均匀 B 样条曲线 一条 B 样条曲线 C 可以看成一系列控制点
9、(0,1, ) i P in=?与其m阶B样条基函数 , ( ) i m Bu (2,3,1)mn=+?组成如式(1)所示 , 0 ( )( ) n i mi i CBP = = uu (1) 式中，u为节点矢量自变量且取值范围满足 min tu max t。 给定一组数据 i P， 据DEBOOR和COX提出的 非均匀B样条函数的递推定义，可得到其1m次 基函数表达式为 1 , 1 , ( ) 1 0 ii i m Bm + = ut t u 其他 ,1 1 ( )( ) i i mi m i mi BB + =+ ut uu tt 1,11 1 ( ) , 1 i m imii i mi
10、Bm + + + tu uut t tt (2) 约定 0 1 0 = 式中 i t 由顶点得到的节点矢量 i B样条的序号 非均匀B样条的基函数不是唯一的，它们依赖 结点值之间的区间，通过低阶的样条基函数递归定 义。根据递推公式得到三次非均匀B样条曲线的基 函数表达式 1 ,1 1 , ( ) 0 ii i B + = 其他 ut t u 2 ,2,11,1 121 ( )( )( ) ii iii iiii BBB + + + =+ uttu uuu tttt 3 ,3,21,2 231 ( )( )( ) ii iii iiii BBB + + + =+ uttu uuu tttt 4
11、,4,31,3 341 ( )( )( ) ii iii iiii BBB + + + =+ uttu uuu tttt (3) 2 多阶动态规划确定控制点 利用非均匀B样条曲线拟合车道线的关键是如 何提取样条曲线的控制点。为了提高算法的准确度 和实用性，利用多阶动态规划提取控制点。 2.1 多阶动态规划 多阶动态规划是一种全局优化算法。它通过对 每个结点进行局部最小操作，使其从起始点到终止 点的代价全局最小，实现路径优化。如图1所示的 图像待检测边缘点，其中黑点表示前景点，其他点 表示为背景点。多阶动态规划的过程就是寻找从起 始点 s P到目标点 g P代价值最小时的路径。 图 1 多阶动态
12、规划示意图 多阶动态规划是在给定阶数的条件下，考虑各 阶段做出决策， 使目标函数最优。 在控制点选取时， 由于动态规划的阶数和候选点个数都无法事先给 定， 算法利用划分搜索区域确定其阶数和候选点集， 步骤如下：首先，寻找车道线的起始点和消失点作 为动态规划的起点和目标点；然后，根据起始点和 目标点确定车道线收索区域，对此区域进行处理得 到动态规划的阶数与候选点集。分隔示意图如图2 所示， “i”是动态规划的候选点集。由图2可知， 由于两车道线的起始点不一定处在一条直线上，因 此它们的搜索区域及其阶数不一定相同。 目标点 起始点 图 2 搜索区域分割示意图 2.2 代价函数的选取 实现多阶动态规
13、划的关键步骤之一是确定目 标函数，即代价函数。在计算机中，一幅灰度图像 ( , )f x y的梯度函数可以表述为一个矢量f如式(4) 所示 () T T ( , ) xy ff x yG G xy = f (4) 该梯度矢量的幅值与角度关系如式(5)所示 月 2011 年 4 月 高德芝等：应用多阶动态规划的车道线识别方法 143 () 1/2 22 1/2 22 ( , )+ xy ff x yGG xy =+ f ( , )arctan y x G x y G = (5) 利用Sobel边缘检测算子对图2中的原始图像 进行处理，得到的边缘幅值与方向图如图3所示。 图3a是由Sobel得到的
14、梯度幅值图像，图3b是其 方向角度图像。图3中具有相同亮度的点则代表具 有相同的角度值。 (a) 梯度幅值图像 (b) 方向角度图像 图 3 边缘梯度图 在图像中，车道线有着自己的特征，如在右转 时的两车道线， 其控制点均在起始点切线方向以右。 左转时，其控制点均在起始点切线方向以左。以图 4所示的右转时车道线为例，叙述动态规划代价函 数的选取。图像中处于不同阶的两候选点都有各自 的像素梯度值，并且能够决定一条直线。 图 4 角度代价函数示意图 处于不同阶的任意两点所决定直线的斜率 kl k 如式(6)所示。根据图像灰度特征与车道线边缘分布 特点，多阶动态规划代价函数的定义如式(7)所示 ar
15、ctan lk kl lk yy k xx = (6) , ( ( , )( , )() ij klijij kl dp i jp k lkk =+ (7) 式中 ( , )p i j 坐标点( , )i j处的梯度值 ( , )p k l 坐标点( , )k l处的梯度值 ij k 该像素点( , )p i j与上阶段候选点 ( , )p x y决定的斜率 ij kl k 点( , )P k l与其上阶段相关候选点 ( , )p i j决定的斜率 2.3 确定控制点的步骤 确定控制点的步骤如下。 (1) 提取两车道线的起始点和消失点作为动态 规划的起始点和目标点所在的位置，它们分别作为 动态
16、规划的第一阶与最后一阶。 (2) 根据各起始点与目标点确定收索区间，提 取候选点 k p并做标记其中k为候选控制点的序号， 根据相邻阶的候选点( , )p i j与( , )p k l间的关系，计 算各阶段候选点间的代价值。 (3) 根据式(8)求取最小代价值，确定其最优路 径。式中，( , )C i j为起始点 s P到目标点 g P的最小代 价值， ,ij kl d为当前点( , )i j到点( , )k l的代价值， ( , )R i j为点( , )i j相邻阶的点集。 , ( , )min( , ),( , )( , ) ij kl C i jdC k lk lR i j=+ (8)
17、 (4) 根据代价函数从目标点分别向起始点搜 索，此时必须满足式(9)。在此过程中得到的一系列 点即为所求的控制点。 , ( , )( , ) ij kl C i jdC k l= (9) 3 算法实现及结果分析 为了验证算法的效果，在配置CPU P41.0 G， 内存512 M的PC上利用Matlab对视频图像进行处 理。算法启动后，首先对图像进行图像滤波、增强 等预处理； 然后利用自适应阈值对图像实现二值化， 同时算法引入了图像细化处理，为控制点候选点集 合的求取做准备工作，最后确定动态规划的起始点 与目标点并确定候选点集，进行动态规划的寻找控 制点。所提出算法处理两车道线的识别过程是相对
18、 独立，下面以左车道线为例对文中算法进行详述， 图5为左车道线多阶动态规划示意图。 图 5 左车道线多阶动态规划框图 通过文中代价函数计算得到各段代价函数值 如下表所示，根据表格中的代价函数值，利用动态 规划得到左车道线控制点的最小代价值为0.280 rad，在文中动态规划的起始点作为第一个控制点， 得 到 的 最 优 路 径 为 sz322 pabcd 3gz ep，同理右车道线的最小代价值为0.550 8 rad，最优路径为 sr1111gr pabcdp。根 据得到的控制点拟合车道线， 处理结果如图6所示， 机 械 工 程 学 报 第 47 卷第 8 期期 144 表 动态规划代价函数
19、当前状态 下一状态 代价函数值 psz a 0.062 5 a b1 b2 b3 1.090 9 0.479 5 0.033 3 b1 b2 b3 b1c1 b2c2 b1c2 b3c1 b2c1 b3c2 1.013 9 0.980 1 0. 587 7 0.621 1 0.149 6 0.174 9 0.865 5 1.922 8 0. 735 7 2.175 2 0.289 5 1.728 9 1.549 9 1.137 8 0.051 2 0.463 4 0.394 9 0.017 2 b1c1 b2c2 b1c2 b3c1 b2c1 b3c2 c1d1 c1d2 c2d1 c2d2
20、0.019 5 0.167 5 0.516 9 0.052 9 1.606 9 0.104 8 0.108 1 0.039 9 0.644 6 0.074 7 1.479 4 0.232 4 0.909 3 1.891 6 0.516 9 0.942 7 2.496 8 0.785 1 0.141 5 1.163 8 1.106 6 0.174 9 1.728 9 0.017 2 c1d1 c1d2 c2d1 c2d2 d1e1 d2e1 d1e2 d2e2 d1e3 d2e3 0.672 1 0.569 6 0.544 5 0.442 1 1.561 9 1.037 4 0.794 1 0.
21、691 6 0.857 7 0.643 2 0.730 1 0.515 6 1.747 5 1.533 0 0.979 7 0.765 2 0.021 7 0.477 8 0.149 3 0.597 4 0.868 1 0.419 9 0.100 3 0.347 8 d1e1 d2e2 d1e2 d2e1 d1e3 d2e3 e1pgz e2pgz e3pgz 0.430 6 0.6162 0.269 6 0.328 1 0.401 7 0.711 4 0.450 5 0.636 1 0.243 3 0.347 9 0.421 6 0.691 4 0.643 6 0.829 2 0.050 2 0.541 1 0.614 7 0.498 3 注：表格中状态栏中符号，代表每个阶段中的当前状态，符号和表示所对应的列矢量中的下一状态。代价函数值栏中符号如 为代表的状态转换到所代表状态矢量时的代价函数值。 图6a为经过细化后得到的二值图像，图6b中白 色的点为提取的候选控制点。根据文中的方法得到 的控制点与最终车道线拟合结果如图6c、6d所示， 图6c中点是根据文中方法得到车道线的控制点位 置。由图6可以看出经过动态规划能够准确地确定 样条函数所需要的控制点。利用文中方法对各种工
