基于改进RANSAC算法的车道线识别方法*

樊 超，狄 帅，侯利龙，徐静波

(河南工业大学信息科学与工程学院，郑州 450001)

前言

车道线的正确识别是智能车辆实现自主导航和一些安全辅助驾驶系统(如车道偏离预警系统等)正常工作的基本前提。目前，已经提出了一些在复杂路况下的车道线识别方法［1－5］。其中随机抽样一致(random sample consensus，RANSAC)算法［6］由于不需要训练过程或匹配道路模型，相对于Hough变换和模板匹配等方法，更能适应复杂路况下车道线特征点拟合，因此近年来在车道线识别中得到广泛应用［7－10］。

当道路路面结构不均匀、光照变化、阴影遮挡、破损、污迹覆盖、天气变化和其它车辆的存在等使道路图像变得复杂时，提取出的特征点中不仅包括有效点，还会存在大量异常点(即干扰点)，且其分布很不规则。异常点的出现使正确计算车道线参数变得非常困难，原因主要有两点:一方面，RANSAC算法在初始化模型时所选取的特征点是完全随机的，并没有一定的约束规则，导致算法的实时性降低;另一方面，由于RANSAC算法迭代过程彼此之间并不相互独立，即前一个模型中所用到的特征点有可能被应用到计算下一个新的车道线模型中，造成某些特征点的重复使用，严重影响了算法的实时性和鲁棒性。

针对RANSAC算法的上述问题，本文中提出一种实时性强、鲁棒性高的改进RANSAC算法。

1 改进RANSAC算法

本文中提出的改进算法适用于各种车道线模型，为了描述方便，采用直线模型。考虑到RANSAC算法的特点和实时性要求，对左、右车道线进行独立、并行的识别，这里以右车道线的识别为例，其流程图如图1所示，算法步骤如下。

(1)假设特征提取后右车道线存在区域的所有特征点构成集合P，利用图2(b)所示的掩模对该区域进行滤波，令滤波后的右车道线区域的所有特征点构成集合P*，则显然有P*⊆P。

(2)在集合P*中随机抽取n个特征点(本文各工况取n=2)构成集合S，并用S初始化右车道线模型Modr。

(3)选取阈值容限di，并令余集Sc=PS中与右车道线模型Modr的距离小于di的点构成集合Q，Q和S构成一致内点集S*。

(4)若集合S*中内点的个数大于t(本文中各工况取t=12)，则认为得到正确的右车道线参数，并利用集合S*中的点采用最小二乘法计算出新的右车道线模型Modr*;否则，转到步骤(2)执行。

(5)选取另一个删除容限do，并且do≥di，如图3所示。删除构成集合S*的所有内点，和与模型Modr*的距离大于di小于do的全部特征点——最内层外点，并存储已计算出的模型Modr*参数。

(6)在集合P*中重新随机抽取n个特征点构成新的集合S并初始化右车道线参数，重复步骤(3)～(5)。

(7)完成K次抽取后，若未找到一致集则算法失败;否则，选取特征点个数最多的S*内点集合——S*max中的点计算出的车道线参数作为最终右车道线参数。

抽样次数K的确定取决于集合S中n个特征点之间相关性的强弱。在实际应用中很难精确地推算出K的取值，但可以在已知先验概率的情况下，计算出K的统计均值E(K)。若令w表示选中的n个特征点中任一特征点都满足某一车道线模型的概率，则有

其中:b=wn;a=1－b

由幂级数性质可知:

对式(2)求导可得

比较式(1)和式(3)可得

利用上述方法，同理可求出对应于左车道线的参数。

2 实验结果与分析

为了验证改进RANSAC算法的有效性，分别对各种路况下采集到的大量道路图像进行分析测试。因篇幅所限，同时为使实验结果更具代表性，下面仅给出两种典型工况的识别结果:(1)复杂工况——特征点较少且分布不规则;(2)正常工况——特征点较多且分布规则。

2.1 复杂和正常工况下的实验结果

图4(a)和图4(b)为原始道路图像，图4(a)中的车道线被路旁树木等造成的阴影严重遮挡，同时车道线被大面积的污迹覆盖且部分标识已破损。图4(c)、图4(d)为车道线特征点提取结果，由于阴影遮挡、污迹覆盖和破损等原因使图4(c)中提取出的左车道线特征点很少，且左、右车道线特征点的分布很不规则。图4(e)、图4(f)分别是图4(c)、图4(d)的左、右车道线存在区域分别经图2中对应掩模进行滤波的结果。

设图4(c)中左、右车道线区域(即 A1、A2区域)的特征点总数分别为AL、AR，其中属于左、右车道线上(即在圆形或梯形区域内)的特征点个数为aL和aR。图4(e)中对特征提取结果进行滤波后左、右车道线区域的特征点总数分别为ALF、ARF，其中属于左、右车道线上的特征点个数为aLF和aRF。则可得上述数值及其相关比值如表1所示。

表1 复杂工况特征提取与滤波后的特征点数目对比

由表 1 可见:ALF/AL、aLF/aL和 ARF/AR、aRF/aR的值较滤波前均变小，这意味着在特征提取结果的基础上进行滤波后，无论噪声点还是车道线特征点均大幅减少，导致算法随机抽取初始化模型的特征点所需的时间相应地下降，算法的实时性得到很大提高;另外 aL/AL、aLF/ALF的值相差甚微、aR/AR、aRF/ARF的值虽然有差距但aRF/ARF的值仍在50%以上，由此说明滤波后在较大提升算法实时性的同时鲁棒性也能得到有效保证。

正常工况下特征提取点与滤波后的特征点数目对比如表2所示，表中符号含义同表1。

由表 2 可见:ALF/AL、aLF/aL和 ARF/AR、aRF/aR的值相比复杂道路工况变得更小，这是由于正常工况下车道线上的特征点排列比较规则，因此算法随机抽取初始化模型的特征点所需的时间将会更少，算法的实时性更好。

表2 正常工况特征提取与滤波后的特征点数目对比

表3 复杂工况d i=1时车道线参数及删除后剩余点数

表4 复杂工况d i=2时车道线参数及删除后剩余点数

d o=19 删除点过多无法计算参数 0.796 7 80.25 － 51.7

表5 复杂工况d i=3时车道线参数及删除后剩余点数

对特征提取后的复杂工况应用改进算法对其车道 线进行识别，当分别取di=1、2、3，在do取不同值时得到的车道线参数和正确识别参数情况下对应左、右车道线区域所剩余的特征点占总特征点数百分比PL和PR的部分实验结果分别如表3～表5所示。其中 kl、bl和 kr、br分别对应左、右车道线模型y=kx+b的两个参数，由于车道标识线自身具有一定的宽度和RANSAC算法抽样的随机性，导致表3～表5中在能正确拟合车道线情况下，参数bl、br在一定范围内变化。使用相似的方法可以得到正常工况下的参数识别结果。为了更好地研究算法的鲁棒性，将复杂和正常工况参数的识别结果进行了比较，如图5所示。为绘图方便而又不改变原始数据所表征的含义，图5中将车道线参数分别除以各自相应的常数k0和b0，图中位于最顶端的参数标识表示由于删除的特征点过多而无法识别，位于最底端的参数标识则表示随着do的增加而出现的车道线误识别。根据识别出的参数，车道线拟合结果如图6所示，其中虚线表示误识别车道线，实线表示do取不同值时识别出的正确车道线。

2.2 实验结果分析与对比

(1)无论正常还是复杂路况，当do在一定范围内变化时，车道线均能正确识别，并且随着do的增大，删除的特征点数量增加(复杂和正常工况最多可分别删掉特征点总数的1/2和2/3)，算法的实时性提高，而鲁棒性并没有明显降低。例如图5(a)中do≤9以内，随着do的增加，识别出的参数变化范围在0.9～1.1之间。因此，在保证正确识别前提下，可适当增加do以提高实时性，但do值不能取得过大以避免漏检测更佳的车道线参数。大量实验验证和统计分析的结果表明:对于复杂工况do取值为7～9为宜;正常工况do取值为5～7较好。

同时，在do取值相同的情况下，由于正常工况下删除的特征点数更多，导致余下的特征点之间的相关性减弱，从而造成识别出参数的不确定性更大。例如，图5(c)中的左车道线在do=3、5时，正常工况都出现误识别而复杂工况却均能正确识别，然而当do≥7时，由于正常工况下删除的特征点较多，导致有时能正确识别而有时却误识别，而与其不同的是，复杂工况却一直是由于删除点过多而无法识别。

(2)di的选取对于两种路况下车道线参数的识别影响并不显著，例如对于复杂路况下的左车道线识别而言，当di分别取1和2时，do分别取到7和9以后车道线无法识别，而当di=3时，do只取到5以后便无法识别。因此改进RANSAC算法的识别准确性并不随di的增加而提高。究其原因不难发现，参数di用于选取构成一致集中的内点，增加di会使内点数量增多，但会降低它们之间的相关性，显然，此种情形下的特征点增多并不利于算法鲁棒性的增强，因此在使用该算法时，di值取1或2即可。

(3)当do取不同值时，在正确识别车道线情况下，各参数位置总体都在某一定值附近上下波动，变化范围大约在10%以内，由此说明算法实时性提高不以牺牲算法的鲁棒性为代价。

(4)另外，从查阅的国内外文献来看，目前评价拟合结果的量化准则主要是与已知的现实路面信息或仿真的虚拟道路进行对比［11－12］;然而在车辆高速行驶情况下，现实路面精确信息的获取并非易事。但是，从识别算法在车道偏离预警系统的应用而言，提取车道线内侧更利于系统的实时性和可靠性。而当使用图2所示的掩模对特征提取结果进行滤波后，恰恰能较多地提取出车道线的内边缘特征点，从而使拟合出的车道线是内边缘线的概率变大，为建立一个实时、有效的量化准则奠定基础。

2.3 其它工况的实验结果

为了进一步验证改进算法的可靠性和适用性，对多种工况进行了实验研究，因限于篇幅，图7仅给出了一些典型场景。结果表明对于路况较差的雨天、阴影遮挡、破损、夜晚车道线，无论是车道线曲率变化较小的直线道路或是曲率变化大的弯道，改进的RANSAC算法均能准确识别出车道线，具有较好的鲁棒性。同时由于算法在迭代过程中能不断删除特征点，使算法的实时性也得到显著提高。

3 结论

针对特征提取后车道线特征点较少、干扰点多或特征点分布很不规则的光照变化、破损、阴影遮挡、天气变化和污迹覆盖等路况，提出改进的RANSAC算法进行车道线特征点拟合。通过对不同工况下所进行的大量实验，结果表明:改进的RANSAC算法无论对于复杂工况还是正常工况下的直线或曲线道路均能实现车道线的正确识别，因此具有较好的鲁棒性。同时，由于算法引入了删除容限，使迭代过程彼此之间几乎相互独立，这样不仅大大提高了算法的实时性，而且有利于得到最佳车道线参数。

［1］ Bertozzi M，Broggi A．GOLD:a Parallel Real-time Stereo Vision System for Generic Obstacle and Lane Detection［J］．IEEE Transactions on Image Processing，1998，7(1):62 －81．

［2］ Wang Y，Teoh E K，Shen D．Lane Detection and Tracking Using B-Snake［J］．Image Vision Compute，2004，22(4):269 －280．

［3］ Danescu R，Nedevschi S．Probabilistic Lane Tracking in Difficult Road Scenarios Using Stereovision［J］．IEEE Transactions on Intelligent Transportation Systems，2009，10(2):272 －282．

［4］ Cheng H Y，Yu C C，Tseng C C，et al．Environment Classification and Hierarchical Lane Detection for Structured and Unstructured Roads［J］．IET Computer Vision，2010，4(1):37 －49．

［5］ Borkar A，Hayes M，Smith M．A Novel Lane Detection System with Efficient Ground Truth Generation［J］．IEEE Transactions on Intelligent Transportation Systems，2012，13(1):365 －374．

［6］ Fischler M A，Bolles R C．Random Sample Consensus:a Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography［J］．Communications of the ACM，1981，24(6):381－395．

［7］ Lopez A，Serrat J，Lumbreras F，et al．Detection of Lane Markings Based on Ridgeness and RANSAC［C］．Proce．of IEEE Intelligent Transportation Systems，2005，254 －259．

［8］ Kim Z W．Robust Lane Detection and Tracking in Challenging Scenarios［J］．IEEE Transactions on Intelligent Transportation System，2008，9(1):16 －26．

［9］ Lopez A，Serrat J，Lumbreras F，et al．Robust Lane Markings Detection and Road Geometry Computation［J］．International Journal of Automotive Technology，2010，11(3):395 －407．

［10］ Mastorakis G，Davies E R．Improved Line Detection Algorithm for Locating Road Lane Markings［J］．IET Electronics Letters，2011，47(3):183 －184．

［11］ Mccall J C，Trivedi M M．Video-based Lane Estimation and Tracking for Driver Assistance:Survey，System，and Evaluation［J］．IEEE Transactions on Intelligent Transportation Systems，2006，7(1):20 －37．

［12］ Veit T，Tarel JP，Nicolle P，et al．Evaluation of Road Marking Feature Extraction［C］．Proc．of IEEE Intelligent Transportation Systems，2008，12－15．