结合Hough变换与运动估计的车道线提取方法

尤小泉，彭映杰

（1.成都工业学院 通信工程系，四川 成都 610031；2.成都信息工程学院 科技处，四川 成都 610225）

近年来，图像处理与机器视觉已经成为车辆自动驾驶和计算机辅助驾驶系统的重要研究内容，即采用图像处理和计算机视觉技术检测道路交通标志、其他车辆及行人等道路环境状况，以保证车辆的行驶安全，并能对驾驶异常行为做出有效的处理和告警[1]。实现这类系统面临的首要关键问题就是实现快速准确地从车载视频图像中检测到车道线[2]。为了提高车道线检测可靠性和鲁棒性，人们将变形模板和遗传算法、局部奇异值向量和BP神经网络分类器、蚁群算法、粒子滤波、图切割和聚类算法、道路谱等应用于道路检测和识别中，并取得了较好的识别效果[3]。由于受车载计算机的计算能力和经济成本的限制，这些智能算法目前还都处于仿真实验阶段，所以车道线检测的快速算法已经成为目前的研究热点。

Hough变换具有良好的抗噪声性能及对部分遮挡现象的不敏感等特性，使其在计算机视觉和模式识别领域中得到广泛的应用[4-6]，也是目前车道线检测的重要方法[2，7-8]。

为了降低Hough变换的计算复杂度，本文利用Hough变换计算复杂度与图像长宽的乘积成正比这一关系，提出了一种分块Hough变换，并且利用车辆行驶过程中行驶方向具连贯性这一特点，图像中车道线也具有运动方向的一致性，所以可以充分地利用行车辅助系统中的视频编码得到的运动矢量对车道线进行有效跟踪。这样极大程度地降低了此类问题计算复杂度，使车载计算机实现车道线的实时识别与跟踪成为了可能。

1 现有车道线检测方法

车道线的检测主要分为图像边缘提取和车道线检测两个步骤。实现图像边缘提取的方法有很多，比如基于小波分析的图像边缘提取、基于模板的图像边缘提取等方法。考虑到实际应用的实时性要求，通常采用Sobel边缘提取技术，如图1所示。

图1 Sobel边缘提取示意图

边缘提取的结果是一幅二值图像，车道检测是在该二值图像中检测车道线。Hough变换具有良好的抗噪声性能和对部分遮挡现象不敏感等特性，非常适合用来实现车道线的检测。Hough变换从本质上来讲是一种参数变换，其原理如下：

设二值图像XOY平面上一条直线l，这条直线可以用如下参数化方程描述

式中：x、y为直线上一点在图像平面中的坐标；ρ为原点到直线l的距离；θ为直线l的法线与x轴正向的夹角，如图2所示。

图2 直线Hough变换的参数定义

根据几何理论，通过平面中任意一点的直线有无穷多条，在参数ρ-θ平面就对应着一簇曲线，直线l上所有点在参数ρ-θ平面都相交于P点（ρ0，θ0），ρ0和θ0就是直线l到坐标原点的距离和法线与x轴的夹角，图2的变换结果如图3所示。

图3 Hough变换的结果

在实际中，Hough变换利用表决方法，即曲线上的每一点可以表决若干参数组合，赢得多数表决的参数就是胜者。在这种方法中，常把参数平面设计成一个累加器阵列，表示离散参数值。依照变换方程，由图像平面中的边缘点数据区计算Hough空间中的参考点的可能轨迹，并在一个累加器中统计出的参考点数，最后选出峰值。图像中的每一个点可以表决几个参数，而参数平面（或累加器阵列）的峰值就是表征一条直线的参数[6]，根据这种方法，图3中的P点对应的就图2中的直线l。利用Hough变换可以检测出图1中的直线，如图4所示。

图4 车道图像Hough变换的结果

根据Hough变换参数空间和图像空间的对应原理，在参数ρ-θ平面的极大值点都代表着一条直线，如图4中左右两边的高亮处各有一个极值点，这两个极值点分别表示左右两个车道，如图5将车道标出。

图5 车道线的检测结果

2 现有算法存在的问题

根据前面Hough变换的基本原理，Hough变换的计算复杂度0（n）与图像的长p、宽q、直线l可能斜率的个数m的乘积成正比[5]，即

对于数字图像而言，可能的斜率就是图像长宽像素点之和，所以式（2）可以改写为

如图1所示，图像长704个像素，宽576个像素，那么处理完这幅图像就需要处理约5亿次计算，经实验，目前TI公司主流的DSP的处理速度约为1 f/s（帧/秒），所以，整帧实时Hough变换是非常困难实现的。

另一方面，考察车道线的跟踪方法，目前流行的有多种方法，如AURORA的自适应的模板相关法、LOIS的变形模板法、Kalman滤波法等，其中性能较好的是Kalman滤波法[9]。Kalman滤波的核心思想是根据目标的运动轨迹模型，给出一个预测值，利用测量数据得到一个测量值，根据预测值的可信度和测量值的可信度加权平均得到目标的估计值，然后再循环并更新预测值和模型的可信度及测量的可信度[10]。对于车道线的跟踪是用Hough变换的方法在图像序列的各帧中提取车道线的参数（ρθ），然后利用Kalman滤波来一帧一帧地依次跟踪这些参数，这样就将车道线的跟踪转化成车道线参数的跟踪。Kalman跟踪方法的引入，提高了跟踪的准确度[9]。据文献[9]和文献[10]的研究，Kalman预测是对矢量方程的迭代求解，其计算量也是相当可观的。

综合上述两点，实现实时车道检测与跟踪的最大难点在于Hough变换的计算量和车道跟踪的计算复杂度。

3 检测与跟踪算法的改进与结果

考虑到Hough变换的计算复杂度，可以将一幅图像分成若干小块，对每一块单独进行Hough变换，其计算量将大大降低。将图1长宽分别作二等分，根据式（3），所有小块计算复杂度之和为

所有小块的计算量之和为原计算量的50%，并且可以推广到长宽n等分的情况，其总计算量为

经实验证明，随着n的增大，Hough变换的计算量有所减少，但是，其直线检测的精度也会随之下降，一般块的大小取64×64像素比较合适，即把一幅704×576的图像分割成了11×9个子块，每个子块的计算量约为52.5万次，所有子块计算量之和为5 200万次，约为整帧Hough变换的10.5%，可见计算量的降低是非常可观的，其车道检测的结果如图6所示，该精度也能满足车道检测的需要。

图6 分块Hough变换的结果

一般对于辅助行车系统而言，都需要将道路的视频图像压缩后保存，目前主流的压缩算法都是基于图像块的运动估计压缩方式，如MPEG-4和H.264等视频压缩标准。在这些压缩算法中就会得到图像块相对于参考帧的运动矢量MV（如图7所示）和其对应的绝对误差和SAD。

图7 运动矢量示意图

图7中的第i帧就是参考帧，其虚线块标注的SAD按式（6）计算，即当前帧与参考帧对应像素之差的绝对值之和

可见，MV表征了图像中物体的水平移动距离和垂直移动距离，可以利用该MV来跟踪车道线，并且可以利用SAD值来衡量这种跟踪的置信度，如果SAD值小，那么跟踪的置信度高；如果SAD值大，那么跟踪的置信度低，预示着当前块应该重新进行Hough变换。对于SAD门限值的设定经实验测得64×64的块的SAD值为1 000～5 000为佳，实验结果如图8所示。

图8 运动估计跟踪车道线结果

4 小结与讨论

本文算法利用前端视频压缩中得到的运动矢量和绝对误差和用于车道线的跟踪的这种方法几乎没有产生额外的计算开销，并且结果能够满足实际需要。根据实验，在TI公司的DM6446 DSP上能实现25 f/s的车道线的实时检测与跟踪。本文方法有效降低了算法的复杂度，为车载计算机实现实时车道检测提供了可能。

另一方面，本文算法由于是基于块的车道线检测与跟踪，在块边缘还存在检测和跟踪结果不够光滑，需要采用相应的平滑方法，这也是下一步工作的内容。

[1] KIM Z W.Robust lane detection and tracking in challenging scenarios[J].IEEE Trans.Intelligent Transportation Systems，2008，9（1）：16-26.

[2] 王松波.一种车道线检测与跟踪方法[J].计算机工程与应用，2011，47（3）：244-248.

[3] 黄海波，蒋伟荣，刘勇，等.基于SOPC的智能车辆道路识别与跟踪[J].仪器仪表学报，2012，33（2）：83-88.

[4] 孙丰荣，刘积仁.快速霍夫变换算法[J].计算机学报，2001，24（10）：1102-1109.

[5]CHUTATAPE O，GUO L F.A modified Hough transform for line detection and its performance[J].Pattern Recognition，1999（32）：181-192.

[6] 陈震，高满屯，杨声云.基于Hough变换的直线跟踪方法[J].计算机应用，2003，23（10）：30-32.

[7] 余天洪，王荣本，顾柏园，等.基于机器视觉的智能车辆前方道路边界及车道标识识别方法综述[J].公路交通科技，2006，23（1）：143-146.

[8] 朱彤，韩文涛，王波.改进Hough变换方法在车道检测中的应用[J].北京汽车，2005（6）：25-28.

[9] 王松波.一种车道线检测与跟踪方法[J].计算机工程与应用，2011，47（3）：248-252.

[10] 尤小泉，彭映杰.一种基于指令预测的目标跟踪方法[J].电视技术，2010，34（2）：81-84.

[11] 尤小泉，蒋建国，齐美彬，等.H.264中分块运动检测的应用[J].电视技术，2006，30（S1）：114-115.