基于混沌粒子群的车道线检测算法

樊 超，宋雨佩，焦亚杰

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

0 引 言

对于复杂路况的车道线提取，检测算法的鲁棒性和准确性是该领域的研究重点。目前车道线的检测方法主要分为基于模型和基于特征两种方法。

基于模型的算法主要采用抛物线模型、双曲线模型以及样条曲线模型等。但是对于复杂的车道线模型，由于模型的参数更多，使得算法的计算成本增加。因此，Jung和Kelber提出了一种线性抛物线车道线模型。在图像近景处使用线性模型，在远景处使用抛物线模型。相对于直线模型的鲁棒性，线性抛物线模型提供了抛物线车道线模型的灵活性。但是大部分的道路场景以直线居多，因此本文主要采用直线模型。基于特征的算法例如Hough变换、最小二乘拟合以及RANSAC的车道线检测方法得到了广泛应用[1-4]，在一些阴影、道路标记等干扰因素条件下，能较准确提取车道线。但对于周围环境干扰以及由于光照不均、道路潮湿等因素的干扰，基于Hough变换的车道线检测算法准确率较低。进而提出了DLD(dark-lightdark)模式[5]，较好解决了由于天气引起的路面光照不均使得车道线检测困难的问题，但是对夜晚车道线的识别较为困难。相关学者提出了风扇扫描和共轭高斯模型等车道线检测算法解决了DLD模式的一些缺陷[6-9]，但检测结果容易受到道路上其它车辆的干扰。由上可知，对于复杂路况的车道线检测，往往要同时面对多种检测困难，主要包含以下两大类因素：第一类是天气因素。例如，晴朗的白天和雨天的路面积水都会由于路面光照不均而产生强烈的道路反光；雨天、大风、沙尘和大雾等恶劣天气条件下，由于道路能见度低极易影响车道线的提取；夜间由于路灯和车灯光照不均等都会增加车道线检测的难度。第二类是道路因素。例如，车道线破损以及颜色褪色、道路两旁的植物和围栏阴影干扰、以及路面车辆对车道线的遮挡等。所以，针对以上所提出的算法面对复杂路况车道线识别鲁棒性较差的问题，本文提出一种基于核Fisher线性判别分析灰度变换以及混沌粒子群的车道线检测算法以提高复杂路况下车道线识别的鲁棒性。

该算法首先通过核Fisher线性判别分析(核F-LDA)算法对图像进行有目的的灰度化处理；然后根据车道线的像素特征，采用直线模型利用混沌粒子群算法(CPSO)在车道线的斜率范围之内求解最优解；最后根据得到的最优直线模型拟合车道线。

1 提出的车道线检测算法

在车辆行驶过程中，考虑到绝大多数车道线曲率的缓变性，近景部分可近似看作为直线，因此本文采用直线模型y=kx+b对车道线进行拟合，其中k、b为所要获得的直线参数。而左右车道线的参数取值范围不同，所以对左右车道线分别进行独立检测，以下算法描述以左车道线检测过程为例。

1.1 基于核Fisher LDA灰度化

传统的灰度化方法将RGB这3个通道的取值加权求和，如式(1)所示

lmg(x,y)=α×R(x,y)+β×G(x,y)+γ×B(x,y)

(1)

式中：α、β、γ为R、B、G这3个通道固定的权值，但是由于实际道路图像的多样性和多干扰性，转换后的灰度图不能很好区分车道线与道路间的特征。

因此，为了使得灰度化后的两种元素特征能够更好区分开，本文提出一种基于核F-LDA的灰度化算法。与传统的LDA[10,11]算法不同，核F-LDA将非线性数据投影到特征空间内，使得数据线性可分，然后在特征空间内对数据进行LDA判别分析。算法实现流程如图1所示。

图1 核FDA算法流程

算法步骤可描述为：

步骤1 取20个车道线图像训练样本,从每个样本中分别截取相同大小的只包含车道线像素特征和只包含道路特征的图像。将样本数据X={X1,X2,…,XN} 按照高斯径向基函数： ∑K(X,Xi)=exp[-(X-Xi)T(X-Xi)] 映射到特征空间Z(X1,X2,…,XN)，即ψ：X→Z。

步骤2 在特征空间内分别求类内离散度矩阵和类间离散度矩阵。

在特征空间内，样本均值为

(2)

Ni指的是第i类的样本个数，这里由于只有两种特征，i取1表示车道线特征类，i取2表示道路特征类。

类间离散度矩阵和类内离散度矩阵可由式(3)、式(4)计算

(3)

(4)

步骤3 求解基于特征空间的最佳鉴别向量。

根据Fisher-LDA的判别准则定义核F-LDA的判别准则

(5)

将式(3)、式(4)带入式(5)求解使得J(w) 达到最大的最佳鉴别向量w*

(6)

步骤4 根据基于特征空间的最佳鉴别向量，推导基于样本数据空间的最佳鉴别向量。

在特征空间内对样本进行投影

Y=w*Tψ(X)

(7)

所以最佳鉴别向量w*可由ψ(X) 线性表示，因此

(8)

N为样本的数目，a为线性参数。将式(2)、式(8)代入式(7)，可得

Yi=aTMi,i=1,2

(9)

(10)

式中：Mi为投影后样本的均值，大小为N×1的矩阵。将式(3)和式(8)带入式(5)，可得

(11)

式中：ω为所求的数据集X空间的最佳鉴别向量，同理可得到

(12)

(13)

Ki为第i类核矩阵，E表示相同维度的单位阵，L矩阵所有元素的值为1/XN。 由式(11)、式(12)得到ω实际上是矩阵Q-1的最大特征值对应的特征向量

ω=Q-1(M1-M2)

(14)

式中：M1，M2分别为两类样本的均值。

于是在特征空间内样本数据集X的最佳鉴别向量w*可以转化为数据集空间内的最佳鉴别向量ω。

步骤5 根据步骤1、步骤2获得的道路特征与车道线特征分离的最佳鉴别向量ω，将输入的RGB图像进行核F-LDA处理。

步骤6 通过以下公式将投影后的数据集取值范围映射到[0，255]

(15)

步骤7 确定阈值(根据光照因素取100-150之间)，根据阈值将所有像素点进行分类，大于阈值c的点判别为车道线特征点，小于阈值的点为非道路特征点。

为比较本文算法在复杂路况下的车道线的灰度化效果，图2(a)给出传统灰度化后得到的灰度图，由于3个通道的权值固定，灰度化的图像对比度并没有发生变化，特征点数目众多且没有一个很好的区分。图2(b)为本文算法处理后的灰度图。从图像中可以很明显看出，灰度化后的图像很好地将道路特征与车道线特征区分开来。

图2 传统灰度化和F-LDA灰度化

1.2 混沌粒子群优化算法

从图2(b)中可以看到，灰度化后的图像中除了车道线特征外，仍然还有许多类似于车道线的线条干扰(如护栏等)。为了从混有干扰信息的图像中正确提取出车道线，本文采用了混沌粒子群算法来提取车道线。

粒子群优化算法由美国学者Eberhart和Kennedy提出[12]，该算法源于对鸟群捕食行为的研究。传统的PSO主要有以下两个缺陷：一是过分依赖初始粒子的分布，若初始粒子分布不均，会导致算法迭代次数增加。二是PSO在求解问题时，容易陷入局部最优解，导致迭代后期收敛速度较慢，影响算法的实时性。因此，为了提高初始粒子的随机性，本文结合混沌变量便利性、随机性和规律性的特点，提出混沌粒子群算法，将混沌的思想与原有的粒子群算法相结合，解决传统粒子群算法的缺陷。算法通过混沌映射，将初始粒子均匀分布在粒子变量的取值范围内。根据左右车道线斜率取值范围的不同分别限定粒子的运动范围；当判别函数检测到算法陷入局部最优时增加一个混沌扰动，使得粒子跳出局部最优。算法的具体实现流程如图3所示，其步骤可描述为：

步骤1 确定初始条件。惯性权重按照w=0.9-0.5×(DT/MaxDT)计算(DT表示当前迭代次数，MaxDT表示迭代的总次数)，初始化迭代计数器DT并设置最大迭代值DTMax，初始化停滞代数计数器并设置计数器阈值T(T取10，T值越小算法要求越严格)，确定数据维度N(N为2)以及粒子数目(视算法计算速度与结果准确率调整)，根据直线斜率确定粒子取值范围；

图3 混沌粒子群算法实现框架

步骤2 初始化种群个体的速度与位置。根据生成的Tent混沌序列，将粒子参数与混沌序列相乘；

初始粒子的分布应尽量遍布整个解空间，且粒子数越多、分布越均匀则搜索到全局最优解的概率越高，但是随着粒子数的增加，算法的计算速度越来越慢。同时，当解空间相对于粒子数较大时，粒子不能够均匀的遍布整个解空间，导致算法陷入局部最优。

本文选用Tent混沌映射[13]，在粒子进行初始化时，将直线参数作为位置信息x，速度信息为v。根据直线的斜率范围对粒子群的初始值进行赋值，在赋值的过程中加入Tent混沌映射，混沌映射的表达式为

(16)

Yn+1为当前Tent混沌映射的取值，Yn为上一次的迭代值。将每一次的取值作为下一次函数计算的自变量值。由式(16)可知，当自变量取值为0，0.25，0.5，0.75时，函数值将呈现出循环的规律性，从而失去混沌的特性，此时，通过以下计算

Yn+1=Yn+0.1×rand(1)

(17)

避免了混沌序列陷入局部不动点或者周期的循环。将混沌映射与位置区间进行相乘

Xmk=Xmin+(Xmax-Xmin)×Y

(18)

m=1,2；k=1,2,3,…,n。 这样就把位置范围内的取值均匀分布在n个粒子空间内。

如图4所示为两种粒子的初始值分布情况，图4(a)为未加混沌映射，粒子分布不够均匀，部分粒子较为集中形成粒子簇，使得解空间内有很多的空白。而增加了混沌映射的粒子分布如图4(b)所示，可见增加扰动后粒子在解空间内的分布更加均匀。

图4 初始粒子分布

步骤3 根据适应度函数，求解当前迭代各个粒子的适应度值，比较每个粒子适应度值的变化，得到粒子Pbest(个体极值)和Gbest(全局极值)；

为判定Gbest是否为当前输入的最优解，引入适应度函数值J，该值越大表明当前输出越接近最优解。Gbest包含直线的参数信息，根据参数在图像上画出该直线，以直线上的点为中心坐标点，在灰度化的图像上对n×n的像素子块进行适应度函数的计算，这里车道线特征主要通过以下两个参数来表征：道路灰度的均值与像素块整体的灰度均值的差Ma以及道路灰度均值和车道线灰度均值的差Ta。以3×3的像素块为例，车道线的像素特征主要有以下两种情况：

对于左车道线来说，正常情况下图5(a)特征比较明显，对于右车道线来说图5(b)特征比较明显。根据以上特征，得出适应度函数表达式

(19)

式中：k,b为直线参数，α、β为像素块两个参数差值相应的权系数。n为有效像素点的个数，这里取阈值为20，当n小于20时，认为该线不是车道线，函数值J(k,b)取0。

图5 车道线3×3像素特征

将每个粒子的适应度值与上一次迭代的结果进行比较，如果此次的值优于之前的取值，更新粒子个体适应度值和Pbest。

将此次迭代后的最大适应度值与上一次迭代后的最大适应度值进行比较。若此次得到的适应度函数值较大，则更新群体历史最佳适应度值Gbest；否则，停滞计数器次数加1，如果次数达到了T次，认为陷入了局部最优，将粒子个体最优解Pbest与混沌序列相乘。

步骤4 根据公式，更新粒子位置和速度参数

(20)

(21)

其中，d=1,2,…,D,c1、c2为加速因子,rand为0到1的随机数,w为惯性权数。从式(20)可以得到，影响粒子速度的因素有3个：惯性权数w，个体极值Pbest，全体极值Gbest。

步骤5 判断迭代次数是否达到DTMax, 若没有则跳转到步骤3。否则，输出全局最优解。在原图像上根据最优解得到的直线模型参数，拟合车道线。

2 实验结果及分析

为验证算法的有效性，本文选用了caltech、roma以及BDD100车道数据集，从中选取了1179张实际道路图像数据对车道线的识别效果进行测试，由于篇幅有限只选取了几幅具有代表性的图像展示检测结果。通过测试发现并分析了影响算法鲁棒性的几个主要因素，进而提出了有效的改善方法。

2.1 像素块尺寸选取对适应度函数求解速度和准确率的影响

为比较像素块尺寸对算法的影响，本文分别选用了3×3、5×5以及11×11的像素块进行对比，图6为不同像素块尺寸下适应度函数值与迭代次数间的关系。

图6 不同像素块适应度值变化比较

其中横坐标为迭代次数，纵坐标为当前迭代下最佳适应度函数的极值。从函数取值的曲线变化来看11×11的像素块很快就达到了最大值，迭代次数不到20次，而5×5和3×3的像素块迭代次数约50次和100次，并且适应度值在相当多的迭代次数内几乎没有发生变化。因此，在其它条件相同的情况下，选取的像素块尺寸越大，则需要的迭代次数越少；从纵坐标的函数值来看，11×11的像素块适应度函数的最大值约为60，而5×5和3×3的像素块适应度函数的极值均超过了60，因此选取的像素块越小得到的结果越接近最优结果。但是，随着像素尺寸的减小，图像噪声对适应度函数的计算结果影响越大，进而降低计算精度。

根据以上结果分析，为了在提高计算准确性的同时缩短计算时间，本文提出变像素计算方法，即在迭代初期采用11×11像素块，后期用3×3像素块，实验结果如图7所示。

图7 本文算法适应度值变化情况

将图7与图6(a)比较，在达到相同适应度情况下，本文算法所需要的迭代次数约20次，迭代次数明显减少。与图6(c)比较可以看出，适应度函数的最大值同样也接近70，因此本文算法在减少计算时间的同时，能够保证较高的识别准确率。

2.2 检测结果陷入局部最优的解决方案

传统的PSO在迭代的后期粒子运动速度缓慢，极易陷入局部最优。图8所示为左车道线的检测过程,每次迭代计算后在原图上画出此次迭代的最优结果。图8(a)表示算法认为左侧的黄线为检测结果的最优解，使得算法陷入了局部最优。针对这一问题，本文引入了一个判别函数，若迭代后的粒子群体最优解Gbest多次未发生变化，认为算法陷入了局部最优。此时引入混沌扰动，将每个粒子的个体历史最优解Pbest与Tent映射相乘。由于Pbest是改变粒子速度和位置信息的3个因素之一，再次更新粒子的速度和位置时，可以使失活的粒子获得速度值重新开始运动，进而使粒子群脱离局部最优解。

图8 局部最优问题解决

图8(b)为增加了混沌扰动后的处理结果，从图中可以看出尽管在迭代的过程中有黄线信息(局部最优箭头所指向的直线)，但加入混沌扰动后最终使右边白色直线(全局最优箭头所指直线)成为全局最优解，进而得到了正确的检测结果。

2.3 多场景道路实验效果

为验证本文所提车道线检测算法的适应性，使用了多种路况对算法的检测效果进行了测试，由于文章篇幅受限，仅选取几种具有代表性的测试图片。如图9所示，本文算法对不同光照条件下，如图9(a)所示的强光、图9(b)所示的夜晚道路以及图9(c)所示的由于雨水引起的路面光照不均等条件下都具有较强的鲁棒性。算法对道路上的干扰，如图9(a)所示的车道线褪色，图9(d)、图9(e)所示的车辆阻挡、多车道干扰和车道标识符干扰，图9(f)所示的路面阴影干扰以及图9(g)所示的道路旁的栏杆干扰也具有较好的鲁棒性。算法对于图9(c)所示的单虚线以及图9(h)所示的双黄线(图9(h)左车道线为双黄线)识别依然有较好的鲁棒性。

图9 多种路况车道线拟合结果

图10 算法准确率比较

为了验证算法的实时性，本文选用了caltech、roma以及BDD100车道数据集，从中选取了1179张车道线图像并分成了5个库，库中包含了车道线检测中所面临的各种困难。选取了基于Hough变换提取车道线的算法作为对比算法，两种算法准确率的对比结果如图10所示。横坐标为不同的数据库，纵坐标为算法的识别率。从纵坐标的分布来看，除了库4本文的识别率要低于算法一以外，其它库的识别率都要显著高于算法一。

3 结束语

本文根据核Fisher线性判别的思想，提出了一种基于核F-LDA灰度化的新灰度化算法；在车道线特征提取过程中，在粒子群算法中引入混沌的思想，提出了一种车道线识别算法。大量实验结果表明，本文提出的算法能够识别不同光照、不同天气以及道路不同干扰等情况下的车道线，充分体现了算法优越的鲁棒性。为复杂路况的车道线检测提供了一种高效的算法。从识别结果来看，车道线图像噪声的存在会导致检测失败，因此下一个阶段要着重研究图像噪声的去除方法。