近几十年来，各国研究者提出了自顶向下[7]、自底向上[6, 8-13]的人工设计算法，抽取道路特征解析道路，但是难于普适多种道路，而且往往侧重于当前车辆两侧的两条车道线。其中，最为经典的方法是基于Hough变换检测车道[8]，但其计算速度低。因此，Satzoda等[9]提出利用多层次Hough变换来提高计算速度，Katru[10]采用分支、合并的并行方法提高计算速度。另外，Wang等[11]提出基于B-snake的车道模型以描述更广泛的车道结构，Jung和Kelber[12]提出近场采用线性函数、远场采用二次函数的抛物线车道模型，Bertozzi和Broggi[13]采用附加非线性项的扩展双曲线处理直线和曲线之间的过渡。近十年来，深度学习迅猛发展，迅速出现了LaneNet[14]、3D-LaneNet[15]、LaneNet+H-Net[16]、LineNet[17]、SCNN[18]、UPSNet[19]等准确自动化解析道路的网络，能够结构化解析道路上的全部车道，但是计算设备复杂、昂贵，并不适合架设在车上。
传统的车道检测算法把图像空间的边缘线经Hough变换到ρ-θ空间，根据车道线总是长线的特点定位到累加值较大的候选点，再回到图像空间筛选候选线段。这种思路具有以下缺点：①需要把图像空间边缘上的所有点都投影到离散的ρ-θ空间，然后对ρ-θ空间的每个点进行筛选，并对每条候选线段再次筛选，流程长，算法复杂，时间和空间复杂度都很高；②得到的ρ-θ空间候选点并不与道路线一一对应，而是零散、重复甚至包含不相关的线段，导致图像空间筛选候选线段的处理比较复杂，检测结果不准确。因此，Ding等[20]采用增强RANSAC进行线段筛选。事实上，图像空间边缘点上就有梯度信息，对此梯度计算直方图，长线总是峰值，而且此直方图比Hough变换后的ρ-θ空间更直观。但是，此直方图综合了整个图像各个位置相同角度线段的梯度，并不能独立筛选出车道线。而Hough变换后的ρ-θ空间中有距离ρ变量，因此能够将各个直线区分开来。如果结合这2种信息，就可以简化ρ-θ空间和直线段的筛选步骤，简化算法，提升检测效果。
基于以上思路，本文提出了梯度直方图和Hough变换互补的算法，具有以下优点：①用边缘点的梯度直方图筛选ρ-θ空间的候选点；②用动态规划的方法在剩余的ρ-θ空间候选点中寻找最合理的车道线组合。这种算法能够大幅降低时间和空间复杂度，提高检测效率，并且能够定位道路上的所有车道，为动态执法提供结构化的道路信息。
1 车道结构化解析算法 本文算法流程如图 1所示，分为边缘检测、边缘点梯度统计、Hough变换、非最大值抑制和动态规划等步骤，最后输出检测到的多车道数据。
 |
| 图 1 本文算法流程 Fig. 1 Flowchart of proposed algorithm |
| 图选项 |
1.1 边缘检测 采用常规的边缘检测方法，如canny算子，对输入的图像抽取边缘。为提高计算速度，采取了以下2个措施：①由于定位车道计算出车道线在图像中的相对位置，把分辨率较高的输入车道图像降采样为只有960×800的低分辨率图像；②由于车道主要位于图像的下半部分，并且车道线的消失点通常位于图像中间的一个矩形框内，假设矩形框高度和宽度为整个图像的1/10，同时车道线的角度在-80°~80°范围内，将图像的下半部分、-80°~80°的范围设置为感兴趣区域。预处理效果如图 2所示。
 |
| 图 2 输入图像及感兴趣区域部分的边缘 Fig. 2 Original image and edges of ROI |
| 图选项 |
1.2 边缘点梯度统计直方图 对感兴趣区域中的所有点，在原图像的灰度图中计算梯度。为提高梯度的准确性，扩大了邻域范围，采用5×5的滤波器，权重如图 3所示。统计每个梯度角度上的边缘点数目，得到边缘点梯度统计直方图，如图 4所示。因为是对整个感兴趣区域进行统计，同一倾角但不同线段上的边缘点会被合计成一个值。
 |
| 图 3 梯度滤波器 Fig. 3 Gradient filter |
| 图选项 |
 |
| 图 4 边缘点梯度统计直方图 Fig. 4 Gradient statistic histogram of edge points |
| 图选项 |
1.3 Hough变换 Hough变换将图像空间的参数离散化成累加器[2]。Hough变换如下：
 | (1) |
将图像中的点坐标(x，y)转换到参数空间(ρ，θ)，每个点对应的累加器值加1。通过改变ρ和θ值，能获得大量累加器，如图 5中灰点所示。由于参数空间中的累加器会出现局部最大值，通过检测该局部最大值，能够寻找到覆盖多数点(x，y)的直线参数方程(ρ，θ)。
 |
| 图 5 边缘的Hough空间图像 Fig. 5 Image of Hough space of all edges |
| 图选项 |
1.4 非最大值抑制 车道线往往是图像下半部分中最长的线，因此取边缘点梯度统计直方图中的峰值mi。Hough变换进行了离散化处理，每个峰值mi向左右2个方向拓展Δm，因此在Hough变换的ρ-θ空间中，保留[mi-Δm，mi+Δm]间的候选点，去除非其余最大值角度中的候选点，如图 6所示。图 6中绿色的区间就是结合梯度的方向和Hough变换的位置信息筛选出的候选区域。
 |
| 图 6 Hough空间候选点的三次筛选 Fig. 6 Candidate points in Hough space filtered for 3 times |
| 图选项 |
车道线往往是各个角度最长的线，因此只保留每列的最大值，如图 6所示。图 6绿色区间的白色点就是每列的最大候选点。相邻车道线间存在夹角，因此把每个候选区域中的候选点[ci1，ci2，…, cij，…]合并成一个候选点ci，ci的位置参数(ρi，θi)为此段候选点[ci1，ci2，…, cij，…]中累加值最大的候选点的位置参数，累加值Ai为候选点[ci1，ci2，…, cij，…]中累加值[Ai1，Ai2，…，Aij，…]的平均值：
 | (2) |
筛选后的候选点，相比由Hough变换得到的初始候选点，数量大为减少，仅有几十个。如图 6中红色叉点所示，候选点的准确性提高。
1.5 动态规划优选Hough候选点 将候选点升序排列，分别做为概率矩阵K的行和列。概率矩阵K中，(θl，θr)位置的元素为plr，表示左车道线的角度为θl、右车道线的角度为θr时车道成立的概率。在非最大值抑制步骤已经确定了θl的距离为ρl、θr的距离为ρr，因此(ρl，θl)代表了左车道线、(ρr，θr)代表了右车道线。概率plr为
 | (3) |
式中：pl为左车道线成立的概率；pr为右车道线成立的概率；pw为左右车道线间宽度成立的概率；ps为左右车道线长度成立的概率。
 | (4) |
式中：pl为左车道线(ρl，θl)Hough变换后累加值Al与候选点中最大累加值Am的比值；pr为右车道线(ρr，θr)Hough变换后累加值Ar与Am的比值；pw为左右车道线间宽度dlr与车道经验宽度d0的比率；H为图像的高度；ps为左右车道线累加值比值接近1或接近0.33的程度；r0为左右车道线累加值比值。
按照高速道路的设计规则，最左边或者最右边的车道线是实线，其余车道线是虚线，虚线实线长2m，间隔长4m，占空比为0.33。如果左右车道线累加比值为1或者0.33，左右车道线成为相邻车道线的概率最大，其余比值下概率就小。
因此，概率矩阵K中的元素包括左车道线(ρl，θl)、右车道线(ρr，θr)、宽度dlr和概率plr等4个属性。概率矩阵中的元素是一条车道的成立概率，因此车道检测就是在概率矩阵中从左上角到右下角的路径寻找最优的车道组合方案。采用动态规划选择路径内各车道概率均值最大、宽度方差最小的方案为最优的组合。目标函数s定义为
 | (5) |
式中：plri和dlri分别为路径中车道的概率和宽度；λ1和λ2分别为车道概率均值和宽度方差的加权系数。
动态规划步骤如下：
步骤1??在概率矩阵中找到最大的k个值，构成k个初始种子组合。
步骤2??从步骤1的种子方案向右边生长，如第i个方案为pi=[pi1，pi2，…，pij，…]，其最后车道pij在矩阵中的位置为(li，ri)。在ri行找到宽度相近、概率最大的m个车道，其概率值为rit(t∈[0，m])，放入方案中作为新的、最右边的成员pi(j+1)，计算此方案的概率均值和宽度方差。
步骤3??从所有种子方案中挑选出概率均值和宽度方差加权和最大的前k个组合。
步骤4??迭代步骤2、步骤3，直到右边没有候选点。
步骤5??将种子方案向左边生长，按步骤2、步骤3迭代直到左边没有候选点。
步骤6??选择概率均值和宽度方差加权和最大的方案作为结果。
按高速道路设计原则，道路最左和最右的车道线是实线，最右车道线的右边是路肩。因此，动态规划寻优得到的方案中，最左线段累加值与此方案中各线段最大累加值的比值应接近1；如果最左的多条相邻线段的比值相近且都接近1，那么选择该多条相邻线段中最右的线段为方案的最左车道线，其余作为围栏等干扰，从方案中去除；如果最右的多条相邻线段的比值相近且都接近1，那么选择该多条相邻线段中最左的线段为方案的最右车道线，最左的线段右边邻接线段作为路肩，其余作为围栏等干扰，也从方案中去除。
2 实验 2.1 自有高速数据的检测实验 从笔者拍摄的高速行驶视频中抽取200张评测本文算法，结果如图 7所示。图 7中红线是最左、最右车道线，紫线是路肩的车道线，绿线是淘汰的干扰线，中间的红点为消失点。可以看出，本文算法能够准确地检测出实车道线、虚车道线、路肩，结构化解析高速道路，可以用于高速道路的动态执法。
 |
| 图 7 高速道路的车道检测结果 Fig. 7 Lane detection results of expressways |
| 图选项 |
2.2 自有非高速数据的检测实验 本文算法主要针对高速道路的结构化解析。为了验证本文算法对普通道路的效果，也从笔者拍摄的行驶视频中抽取50张进行评测。与高速道路不同，普通道路最右实车道线的右边没有路肩，因此对动态规划的规则进行了相应修改，结果如图 8所示。与图 7相同，图中红线是最左、最右车道线，绿线是淘汰的干扰线，中间的红点为消失点。图 8中间的例子，由于停车的遮挡，左边的实车道线被误检为虚线。可以看出，本文算法能够较准确地检测出实车道线、虚车道线，结构化解析普通道路，也可以用于普通道路的动态执法。
 |
| 图 8 普通道路的车道检测结果 Fig. 8 Lane detection results of urban roads |
| 图选项 |
2.3 对比实验 为了评比本文算法的性能，将其与传统的Hough变换车道检测[8]、层次化Hough变换车道检测[9]、扩展双曲线模型车道检测[13]及深度学习的LaneNet[14]、UPSNet[19]在i7-6700K处理器(无GPU)、MATLAB2017的平台上进行了对比。从KITTI[21]的高速道路中选择100张样本作为测试集。如果检测到的车道线段有30%或者以上落在ground truth中，就认为是正确检测到车道；否则失败。定义准确率为检测到的车道线是真正车道线的数量比例，即
 | (6) |
召回率为检测正确的车道线占ground truth中全部车道线的比率，即
 | (7) |
式中：TP(True Positive)为正确检测到的真实车道线数量；TN(True Negative)为将非车道线检测为真实车道线的数量；FP(False Negative)为未检测到的真实车道线数量。
实验结果如表 1所示。
表 1 不同算法的性能对比 Table 1 Comparison of performance between different algorithms
| 算法 | 准确率/% | 召回率/% | 速度/FPS |
| 文献[8] | 63.47 | 59.04 | 8.2 |
| 文献[9] | 76.29 | 73.34 | 32.7 |
| 文献[13] | 79.57 | 87.13 | 23.6 |
| LaneNet[14] | 92.81 | 93.19 | 18.4 |
| UPSNet[19] | 89.96 | 91.37 | 13.6 |
| 本文算法 | 91.23 | 94.18 | 36.5 |
| ??注：FPS为帧/s。 | |||
表选项
基于传统的Hough变换车道检测[8]的准确率和召回率只有63.47%和59.04%，速度只有8.2FPS；基于层次化Hough变换的车道检测[9]的准确率和召回率均有较大提高，达到了76.29%和73.34%，速度提高更快，达到了32.7FPS；基于扩展双曲线模型车道检测[13]的准确率和召回率一步提高到79.57%和87.13%，速度为23.6FPS；LaneNet[14]和UPSNet[19]都是基于深度学习，没有GPU的支持，速度只有18.4FPS和13.6FPS，但是准确率分别达到92.81%(最大值)和89.96%，召回率也分别达到93.19%和91.37%；本文算法筛选掉了大部分伪车道线，能够去掉阴影和近似印迹，但是容易受车辆遮挡，准确率为91.23%，不如LaneNet算法的92.81%，但是召回率达到了最大值94.18%，而且检测速度也达到了最大值36.5FPS。
3 结论 1) 相比于传统的基于Hough变换车道检测的算法，本文算法利用边缘梯度减少了Hough变换后候选点的数量，基本上排除了不含车道线信息的Hough空间候选点，保留了包含车道线信息的候选点，并采用动态规划筛选出真实车道线，定位到道路上的全部车道，结构化解析高速道路，能够用于道路的动态执法。
2) 算法简单，计算资源耗费少，能够用于实时的道路分析检测。
参考文献
| [1] | ZHANG X Q, HU W M, XIE N H, et al. A robust tracking system for low frame rate video[J]. International Journal of Computer Vision, 2015, 115(3): 279-304. |
| [2] | ZHANG X Q, HU W M, CHEN S Y, et al. Graph-embedding-based learning for robust object tracking[J]. IEEE Transactions on Industrial Electronics, 2014, 61(2): 1072-1084. DOI:10.1109/TIE.2013.2258306 |
| [3] | ZHANG X Q, WANG D, ZHOU Z Y, et al.Robust low-rank tensor recovery with rectification and alignment[J/OL].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019(2019-07-16)[2020-03-01].DOI:10.1109/TPAMI.2019.2929043. |
| [4] | LINGWORTH J, KITTLER J. A survey of the Hough transforms[J]. Computer Vision, Graphics, and Image Processing, 1988, 43(2): 280-289. |
| [5] | ZHANG X Q, HU W M, QU W, et al. Multiple object tracking via species-based particle swarm optimization[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2010, 20(11): 1590-1602. DOI:10.1109/TCSVT.2010.2087455 |
| [6] | ZHANG X Q, LI C C, HU W M, et al. Human pose estimation and tracking via parsing a tree structure based human model[J]. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2014, 44(5): 580-592. DOI:10.1109/TSMC.2013.2280438 |
| [7] | ZHANG X Q, HU W M, BAO H J, et al. Robust head tracking based on multiple cues fusion in the kernel-Bayesian framework[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(7): 1197-1208. DOI:10.1109/TCSVT.2013.2241354 |
| [8] | SHIN B S, TAO J, KLETTE R. A superparticle filter for lane detection[J]. Pattern Recognition, 2015, 48(11): 3333-3345. DOI:10.1016/j.patcog.2014.10.011 |
| [9] | 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. DOI:10.1109/LES.2010.2051412 |
| [10] | KATRU A. Improved parallel lane detection using modified additive Hough transform[J]. International Journal of Image, Graphics and Signal Processing, 2016, 8(11): 10-17. DOI:10.5815/ijigsp.2016.11.02 |
| [11] | WANG Y, TEOH E K, SHEN D. Lane detection and tracking using B-snake[J]. Image and Vision Computing, 2004, 22(4): 269-280. |
| [12] | JUNG C R, KELBER C R. Lane following and lane departure using a linear parabolic model[J]. Image and Vision Computing, 2005, 23(13): 1192-1202. DOI:10.1016/j.imavis.2005.07.018 |
| [13] | 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. |
| [14] | WANG Z, REN W Q, QIU Q.LaneNet: Real-time lane detection networks for autonomous driving[EB/OL].(2018-07-04)[2020-03-01].https://arxiv.org/abs/1807.01726. |
| [15] | GARNETT N, COHEN R, PE-ER T, et al.3D-LaneNet: End-to-end 3D multiple lane detection[EB/OL].(2018-11-26)[2020-03-01].https://arxiv.org/abs/1811.10203. |
| [16] | NEVEN D, BRABANDERE B D, GEORGOULIS S, et al.https://bhxb.buaa.edu.cn/article/2020/1001-5965/Towards%20end-to-end%20lane%20detection:%20An%20instance%20segmentation%20approach[C]//IEEE Intelligent Vehicles Symposium(IV).Piscataway: IEEE Press, 2018: 286-291. https://bhxb.buaa.edu.cn/article/2020/1001-5965/Towards%20end-to-end%20lane%20detection:%20An%20instance%20segmentation%20approach |
| [17] | LIANG D, GUO Y C, ZHANG S K, et al.LineNet: A zoomable CNN for crowdsourced high definition maps modeling in urban environments[EB/OL].(2018-07-16)[2020-03-01].https://arxiv.org/abs/1807.05696v1. |
| [18] | PAN X, SHI J, LUO P, et al.Spatial as deep: Spatial CNN for traffic scene understanding[C]//The 32nd AAAI Conference on Artificial Intelligence(AAAI-18).Palo Alto: AAAI, 2019. |
| [19] | XIONG Y W, LIAO R J, ZHAO H S, et al.UPSNet: A unified panoptic segmentation network[C]//IEEE Conference on Computer Vision and Pattern Recognition(CVPR).Piscataway: IEEE Press, 2019. https://www.researchgate.net/publication/330382643_UPSNet_A_Unified_Panoptic_Segmentation_Network |
| [20] | DING Y, XU Z, ZHANG Y B, et al. Fast lane detection based on bird's eye view and improved random sample consensus algorithm[J]. Multimedia Tools and Applications, 2017, 76(21): 22979-22998. DOI:10.1007/s11042-016-4184-6 |
| [21] | GEIGER A, LENZ P, STILLER C, et al. Vision meets robotics:The KITTI dataset[J]. International Journal of Robotics Research, 2013, 32(11): 1231-1237. DOI:10.1177/0278364913491297 |
