车道线的GrowCut快速检测算法

黎 明， 计春雷， 张鸿洲

（1.上海电机学院 电子信息学院，上海 200240；2.公安部第三研究所，上海 201204）

车道线的GrowCut快速检测算法

黎 明1， 计春雷1， 张鸿洲2

（1.上海电机学院 电子信息学院，上海 200240；2.公安部第三研究所，上海 201204）

针对目前智能交通领域中车道线检测算法效率低、鲁棒性差等问题，提出了一种基于GrowCut的车道线快速检测方法。从监控摄像机中采集图像并标定初始种子点，利用GrowCut算法进行边缘分割，对分割结果经过中值平滑滤波、边缘提取、分半处理及曲线拟合，最终得到清晰的车道线。将GrowCut算法与分水岭算法进行了对比，结果表明：该算法简便快捷、鲁棒性好，优于经典算法，可广泛应用于智能交通、公共安全领域。

车道线检测；图像分割；智能交通

车道线检测是PTZ（Pan Tilt Zoom，PTZ）摄像机自动标定、智能视频分析、汽车辅助驾驶以及室外机器人自动导航的首要环节和关键步骤，具体是指从监控摄像头获取的视频图像中，根据车道线的颜色、纹理、形状等特征，将车道线与背景分离，从而获得车道线的走向或标记车道的区域范围［1］，而图像分割是其中的一个重要环节。

经典的图像分割算法大致可以分为阈值分割法［2-3］、区域增长法［4］、聚类法［5］等。阈值分割法是最为基础的图像分割算法，由于计算量小、实现简单、性能稳定等诸多优点而得到广泛应用，但阈值的选取往往是决定分割成败的关键因素。区域增长法由于涉及迭代操作，效率不高，并且容易发生过分割现象，分水岭算法［6］就是其中的典型代表。聚类法对数据维数较为敏感，通常需要耗费大量运算时间和资源，很难满足实时性要求，因此不适用于车道线检测研究领域。当前最流行的图像分割算法还包括：Magic Wand，Intelligent Paint［7］，Intelligent Scissors［8］，Graph Cut［9-10］，GrabCut［11］等。其中，Intelligent Paint和Intelligent Scissors是交互式的图像分割方法，可以快速准确地分割图像中的目标区域。Graph Cut算法将图像作为图形进行处理，每个图像像素代表一个图形节点，然后采用最大流最小割算法计算最优像素点标记。作为Graph Cut算法的扩展，GrabCut算法的分割效果通常更佳。

目前，车道线检测多采用经典的Hough变换及形态学方法，提取车道图像中的强边缘，然后通过曲线拟合来确定车道线。文献［12］中提出了一种基于Hough变换的道路边缘检测和跟踪方法，可以实现低曲率道路（如高速路）的车道线检测。然而实际交通路况中，特别是在智能交通、汽车辅助驾驶等应用中，道路状况复杂多变，多数车道图像中都包含有较高曲率的路段；此外，Hough变换的运算量大，难以满足实时性要求。为了解决这一问题，文献［13］中提出了一种基于分层累加的Hough变换算法，可以大幅提高运算效率。文献［14］中提出了一种基于形态学结构元素建模的车道线检测算法，具有较好的鲁棒性。经典车道线检测方法的检测结果易受视频图像分辨率、道路状况等因素影响，误差通常较大。

针对现有车道线检测技术的不足，本文提出一种基于GrowCut［15］的车道线快速检测算法，采用新的边缘分割方法对车道线进行分割、平滑滤波处理，不仅能有效去除椒盐噪声，还能保留更多的图像边缘信息，最后进行曲线拟合，从而确定车道线。该算法可以对低分辨率、无明显车道边界线及具有较高曲率路段的视频图像进行车道线的快速检测，同时算法对光照、噪声不敏感。

1 GrowCut图像分割

GrowCut算法采用了全新的思路进行像素标记，分割效果更好。具体来讲，GrowCut算法是一种基于元胞自动机［16］的交互式多标记n维图像分割方法。元胞自动机是一个三元组

其中，S为非空状态集，N 为邻域系统，δ：SN→S表示从SN映射到S的一个局部转移函数。

当前一时步的邻近元胞状态已知时，局部转移函数可用于计算下一时步的元胞状态。常用的邻域系统有冯·诺依曼领域和摩尔领域两种。

（1）冯·诺依曼邻域

（2）摩尔邻域

式中，p为当前元胞；q为邻域元胞；Zn为图像像素空间，n为空间维数；∀p∈P⊆Zn，P为元胞空间。

元胞状态Sp是一个三元组（lp，θp，Cp），其中lp为p 的标记；θp为p 的力量，θp∈［0，1］；Cp为元胞特征向量。

对于一幅图像，初始元胞状态为

式中，RGBp为像素p在RGB空间的三维色彩向量。因此，利用元胞自动机进行图像分割的目标就是为图像中的每个像素分配一种状态（或指定一个标记）。

利用GrowCut进行图像分割的原理可以从生物学角度加以解释：把图像像素点的标记化过程看作是多种细菌的生长与竞争过程，其中细菌代表元胞。每种细菌都从种子像素点开始扩散并试图占领整幅图像。在生长过程中，每个细菌都试图攻击其邻近细菌，只有当前细菌的攻击强度大于防守细菌的防守力量时，攻击才成功，此时防守细菌被占领，并改变其标记。如此循环，直至元胞自动机收敛，分割结束。

2 车道线检测

本文基于GrowCut算法提出了新的车道线快速检测算法，流程图如图1所示。

图1 车道线检测算法流程图Fig.1 Flow chart of the proposed lane detection algorithm

2.1 关键帧选取

采集监控视频，通过解帧操作将其序列化为多帧图像，从中挑选一帧图像作为关键帧。从多帧图像中选取关键帧的方法有两种：① 选取清晰度较高、车道分界线相对明显的帧作为关键帧；② 选择图像质量相对稳定，且图像内容没有明显跳变的一段，对多帧图像取平均值作为关键帧。

在关键帧图像中手动标定边缘分割初始种子点，并利用GrowCut算法进行边缘分割，步骤如下：① 获取初始种子点的标记lp，力量θp和特征向量值Cp。② 保存当前状态。③ 元胞开始生长。④ 利用初始状态值计算攻击强度。⑤ 当前元胞尝试攻击邻近元胞。⑥ 判断当前元胞的攻击强度是否大于防守元胞的防守力量，若否，则继续攻击相邻元胞；若是，则防守元胞被占领，同时改变其标记和力量值。⑦ 上述步骤循环进行，直至元胞自动机收敛，边缘分割结束。

2.2 边缘提取

采用中值滤波器对分割结果进行平滑滤波。中值滤波是一种非线性平滑方法，可以有效滤除分割结果图像边缘附近存在的椒盐噪声，同时还可以更多地保留边缘信息。其原理是，将图像中某像素点的值用该像素邻域中其他各点值的中值代替，让周围的像素值更接近真实值，从而消除孤立噪声点。具体操作时，定义一个二维滑动模板，其大小通常是奇数，如3×3或5×5，利用该模板对整幅图像进行滑动平均处理。模板的形状可以根据4邻域、8邻域等分别定义为十字形、圆形或其他拓扑结构。在本文算法中，中值滤波模板大小取值9×9。

平滑滤波之后进行边缘提取。通常，边缘提取采用索贝尔（Sobel）算子，也可用Robert，Canny和Prewitt等算子替代，这对边缘提取的效果不会产生太大差异。这是由于经GrowCut分割且平滑滤波后，图像边缘比较连续、完整，因此边缘提取较易实现。

2.3 车道线分半处理

完成上述步骤之后，需要对提取到的道路边缘进行分半处理，分别得到左侧车道线和右侧车道线。目前，由于我国布控的路况摄像机中，有相当数量的摄像机为模拟设备，视频图像的分辨率不高；同时，由于部分车道并没有划分虚、实线，因此利用传统形态学、分水岭等算法分割出来的车道线往往与实际不符，存在过分割和欠分割现象。而采用GrowCut算法分割后，虽然车道边缘轮廓整体较好，但仍有可能存在粘连、分叉等现象，特别是对于弯曲的道路、十字路口等。故对提取到的边缘进行分半处理，可以使后续步骤的车道线拟合更加准确。对分割出来的车道线进行分半处理的流程如图2所示。

2.4 车道线拟合

利用多项式对车道边缘进行曲线拟合，得到最终车道线。该多项式为

图2 分半处理流程图Fig.2 Flow chart of the splitting procedure

式中，fj（j＝1，2，…，m＋1）为多项式系数，m 为多项式阶数。根据道路的弯曲程度确定相应的阶数，从而实现车道线的拟合。

3 实验结果及分析

为了验证本文算法的鲁棒性，采集了多种环境条件下的图像，分别针对单车道／多车道、无标志线车道／间断标志线车道、直线车道／高曲率车道进行了实验。实验所用图像通过在道路上方架设监控摄像机实时采集得到。

3.1 单车道检测

从单车道监控视频中截取图像，道路中没有标识线，左侧车道线从视觉上尚能分辨，而右侧车道由于边缘不明显，因此很难分辨出车道与人行道的分界线。分别采用经典的分水岭算法和本文提出的算法对该图像进行车道线检测，并比较其效果。

图3（a）和（b）是采用分水岭算法的初始种子点标记及分割的结果。为了取得图中所示的分割效果，需要精心选取种子点，同时种子点数量要尽可能多，才能确保车道右侧边缘能较好地分割出来。尽管如此，在道路上方仍有一小段高曲率的弯曲车道没有分割出来。

图3（c）和（d）是采用本文算法的初始种子点标记及分割的结果。相对于对于分水岭算法，本文算法的初始种子点只有18个，并且不需要精确选择，只需沿着人眼视觉可辨的车道线边缘粗略选取若干标记点即可。但分割效果明显优于分水岭算法，不仅很好地检测出右侧的微弱道路边缘，也成功地检测出了道路上方的高曲率路段。

为了比较2种算法的车道线检测效果，对图3（b）和（d）分别进行了分半处理和曲线拟合，拟合结果分别如图3（e）和（f）所示。从图3（e）可以看出，左侧车道线检测效果较好，而右侧车道线由于分割效果较差，故检测到的车道线偏离实际道路，误差较大。

图3（f）是利用本文算法的车道线检测结果，可以看出车道所在区域已被完整地标记出，便于后续的摄像机标定或者车辆计数、流量监测等研究工作。

3.2 多平道检测

从多车道监控视频中截取到图像，各个车道之间采用白色间断线加以标识。

图4（a）和（b）是采用分水岭算法的初始种子点标记及分割的结果，图4（c）和（d）是采用本文算法的初始种子点标记及分割结果。对图4（b）和（d）分别进行了分半处理和曲线拟合，拟合结果分别如图4（e）和（f）所示。

从图4（e）可以看出，对于有标识线的车道图像，分水岭算法的分割效果优于无标识线的车道分割结果，但是依然需要手动精确选取大量初始种子点，否则在车道线的间断处很容易发生过分割现象，将其他车道的部分划入本车道，影响后续的车辆计数、跟踪识别等操作。此外，由于左侧车道部分路段存在过分割现象，因此拟合后的车道线与实际不符，存在较大误差。而本文算法的车道线分割结果基本上没有发生过分割的情况，虽然初始种子点数目比图3有所增加，但相比分水岭算法仍占据优势，同时车道线检测结果也更好。

4 结 语

本文提出了一种基于GrowCut的车道线快速检测方法。采用GrowCut算法替代传统的形态学、区域增长及分水岭等方法对视频图像进行边缘分割，然后对分割结果进行平滑滤波，在去除椒盐噪声的同时保留更多的边缘细节，最后进行曲线拟合，确定车道线。通过该方法，可以对低分辨率、没有明显车道边界线以及包含高曲率路段的视频图像进行车道线的快速检测。利用本文算法对路况摄像机进行自动标定、辅助汽车自动驾驶以及机器人的自动导航等均能取得较好的效果，目前已在公安系统内部试点应用。

［1］Kastrinaki V，Zervakis M，Kalaitzakis K.A survey of video processing techniques for traffic applications［J］.Image and Vision Computing，2003，21（1）：359－381.

［2］Otsu N.A threshold selection method from graylevel histogram［J］.IEEE Transactions on System，Man and Cybernetics，1979，9（1）：62－66.

［3］肖超云，朱伟兴.基于Otsu准则及图像熵的阈值分割算法［J］.计算机工程，2007，33（14）：188－189，209.

［4］Adams R，Bischof L.Seeded region growing［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1994，16（6）：641－647.

［5］Coleman G B，Andrews H C.Image segmentation by clustering［J］.Proceedings of the IEEE，1979，67（5）：773－785.

［6］Vincent L，Soille P.Watersheds in digital spaces：an efficient algorithm based on immersion simulations［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（6）：583－598.

［7］Reese L J.Intelligent paint：region－based interactive image segmentation［D］.Provo，UT：Brigham Young University，1999：1－20.

［8］Mortensen E N，Barrett W A.Interactive segmentation with intelligent scissors［J］.Graphical Models and Image Processing，1998，60（5）：349－384.

［9］Greig D M，Porteous B T，Seheult A H.Exact maximum a posteriori estimation for binary images［J］.Journal of the Royal Statistical Society：Series B（Methodological），1989，51（2）：271－279.

［10］Boykov Y Y，Jolly M P.Interactive graph cuts for optimal boundary and region segmentation of objects in N－D images［C］／／Proceedings of the Eighth IEEE International Conference on Computer Vision.Vancouver，BC，Canada：IEEE Computer Society，2001：105－112.

［11］Rother C，Kolmogorov V，Blake A.Grabcut：interactive foreground extraction using iterated graph cuts［J］.ACM Transactions on Graphics，2004，23（3）：309－314.

［12］McDonald J B.Application of the Hough transform to lane detection and following on high speed roads［C］／／Proceedings of the Irish Machine Vision and Image Processing Conference.Maynooth，Ireland：National University of Ireland，2001：1－9.

［13］Satzoda R K，Sathyanarayana S，Srikanthan T，et al.Hierarchical additive Hough transform for lane detection［J］.IEEE Embedded Systems Letters，2010，2（2）：23－26.

［14］雷 涛，樊养余，王小鹏，等.基于形态学结构元素建模的车道线检测算法［J］.计算机应用，2009，29（2）：440－443.

［15］Vezhnevets V，Konouchine V.“GrowCut”：Interactive multi－label N－D image segmentation by cellular automata［C］／／Proceedings of the GraphiCon.Novosibirsk Akademgorodok.Russia：Russian A－cademy of Sciences，2005：150－156.

［16］Von Neumann J.Theory of self－reproducing automata［M］.Champaign，IL，USA：University of Illinois Press，1966.

Fast Lane Detection Algorithm Based on GrowCut

LI Ming1， JI Chunlei1， ZHANG Hongzhou2
（1.School of Electronics and Information，Shanghai Dianji University，Shanghai 200240，China；2.The Third Research Institute of Ministry of Public Security，Shanghai 201204，China）

A fast GrowCut－based lane detection algorithm is proposed to improve efficiency and robustness of the lane detection algorithms used in intelligent transportation.An image is captured with a surveillance camera and the initial seeds are marked on it.The GrowCut algorithm is then applied to segment the image.After median filtering，edge extraction，splitting and curve fitting，clear lanes can be obtained.The proposed algorithm is compared with the watershed method.The results show that the proposed approach has better performance and robustness than traditional algorithms.The algorithm can be applied to intelligent transportation and public security.

lane detection；image segmentation；intelligent transportation

TP 391.41

A

2095－0020（2011）03－0187－06

2011－05－10

上海市教育委员会科研创新项目资助（11YZ270）；上海市高校选拔培养优秀青年教师科研专项基金项目资助（sdj10001）

黎 明（1979－），男，讲师，博士，专业方向为图像处理、机器学习，E－mail：ming.lmhost＠gmail.com