基于Kmeans算法的二步迭代道路检测算法

1、 基于Kmeans算法的二步迭代道路检测算法 史迪玮 毛剑琳Summary：为增强现有基于机器视觉的自动导引车AGV对非结构化路面的适应能力，提出一种基于Kmeans聚类分析算法的二步迭代道路检测算法。算法实现了自动选择路面样本区域与自主动态添加路面样本，克服了基于其它机器学习算法的道路识别方法需要人工收集大量路面样本进行训练的缺陷。实验仿真结果显示，该方法能有效降低光照、阴影、车道线等对道路识别的影响，能够适应含有多种不同障碍物的道路场合。Key：非结构化路面;路面检测;聚类分析;二步迭代;机器视觉DOIDOI：10.11907/rjdk.181137：TP312：A：16727800（20

2、18）009011005英文标题Twostep Iterative Road Detection Algorithm Based on Kmeans Algorithm-副标题英文作者SHI Diwei，MAO Jianlin英文作者单位（Faculty of Information Engineering and Automation，Kunming University of Science and Technology， Kunming 650500， China）英文SummaryAbstract：This paper proposes a twostep iterative road

3、 detection algorithm based on Kmeans clustering analysis algorithmto enhance the adaptability of current automated guided vehicles （AGV） based on machine vision to unstructured pavement.Thisalgorithm implements the automatic selection of pavement sample areas and autonomous dynamic addition of pavem

4、ent samples.However other road recognition methods based onmachine learning algorithmsneed to manually collect a large number of pavement samples for training，this algorithm has overcome the defects.The simulation results show that this method can effectively reduce the influence of illumination，sha

5、dow and lane line on road recognition，and it can adapt to roadsituation with many different obstacles.英文關键词Key Words：unstructured pavement;pavement detection;cluster analysis;twostep iterative;machine vision0引言道路识别技术是指利用计算机对采集的路面图像进行分析处理，从而区分画面中的道路区域与非道路背景及障碍物的技术1。道路识别技术是自动导引车辆（AGV，Automated Guided

6、Vehicles）视觉导引的关键技术2，随着人工智能技术在导航控制、辅助驾驶、物流运输领域的广泛应用，该技术已成为相关领域的研究重点34。道路识别技术的难点在于对非结构化道路路面的识别5，非结构化道路路面是指没有相对清晰的车道线和明确的道路边界，且道路形状多样、周围环境复杂的道路路面6。此类路面一般没有相对明显的标志线与明确的道路边界线，且易受到光照与天气变化、环境阴影及路面缝隙等因素影响7。钟鹏飞8提出先提取非结构化道路的路面边缘点，然后基于 Hough检测道路边缘直线线段，并对边缘点进行优化，最后基于最小二乘法理论，对道路图像中的左右边缘点和两侧边缘线进行拟合，得到道路左右边缘直线，进而确

7、定路面区域。然而，单纯的基于检测并拟合道路边缘直线的方法无法很好地适用于路况复杂的路型：当路面上有车道线且较为明显，或是有较清晰的光影边界线时，根据某些算法，容易将此类车道线或光影边界线误识别为道路的某一侧边缘;对于多叉路路口，普通算法无法对道路的具体岔路模式进行识别。为改善并解决相关缺陷，王海、蔡英凤、贾允毅等12提出一种基于深度卷积神经网络（DCNN）与自编码器的场景自适应道路分割算法，并在 KITTI数据集上进行测试，结果表明，该算法相较于现有的非场景自适应道路分割算法，其对相关路面分割的准确率提升了约4.5%;李春阳10围绕基于视觉信息的道路区域检测方法，将深度学习（Deep Lear

8、ning）技术应用于道路场景的路面特征提取环节，并引入人工鱼群算法对监督学习框架进行参数优化，以实现对道路区域的检测。根据多个由连续帧组成数据集上的检验结果显示，该算法的通用性和鲁棒性良好，能够适应多种复杂场景，并得到令人满意的结果。然而，现有大量基于机器学习理论的道路识别方法为了适应不同路面环境，需要人工收集海量路面图片样本数据并制作训练集，再利用人工神经网络等技术进行多次训练11，从而严重降低了道路检测技术的普适性。只有完整提取当前道路路面的具体形状，才能进一步判别出当前道路的实际类型（如直路、弯道、叉路等），再根据道路路面的具体模式对智能移动设备进行局部定位，并与全局路径和全局地图相结合

9、，从而提出合理的局部路径规划。因此，完整提取当前所处道路路面的具体形状是首要研究方向。本文提出的基于Kmeans聚类分析12的两步迭代道路检测算法能针对路面样本进行主动选择，基于视觉的自动导引车可依靠自身的软件和硬件设备，自主添加道路图像作为动态样本，且能自动选择适合的样本区域。该算法可降低光影、障碍物、车道线等负面环境因素对道路识别准确性的影响，能够适应多种道路条件，减少运行过程中的人工需求，并缩短机器学习过程中的训练时间。1二步迭代道路检测算法重复进行某种反馈过程的活动称为迭代，为了逼近所需目标或结果，通常需要进行多次迭代。算法中每一次对某个过程的完全重复，称为一次“迭代”，而每一次迭代结

10、束得到结果量之后，会作为下一次迭代开始的初始量，再对一系列运算过程进行重复执行13。该过程每一次得到的结果，都是对前一次所得结果进行相同运算后得到的。迭代思想是利用计算机解决问题的一种基本思想14。根据实际应用需要，设计一种基于两步迭代思想的道路路面检测算法。通过实时连续不间断地采集行驶方向前方路面图像，根据相邻两张图像中路面区域的近似程度，判断前方道路的连续性与可通行程度。算法默认初始位置为完全可通行区域，每次基于两张连续且相邻的图像进行迭代，首先在前一张图片Pn中选择安全可行的路面区域Sn作为样本区域，然后利用聚类算法提取道路样本区域聚类特征，再将区域Sn移植到后一张图片Pn+1中，以选取

11、相同路面区域作为第二次聚类样本，提取出后一张图片道路样本区域的聚类特征后，对前后两组聚类特征的相似性作比较，以判断当前道路是否为可通行路面。2算法关键技术步骤2.1样本区域自动选择实时连续不间断地采集行驶方向前方路面图像，根据算法流程，先选取任意图像Pn对图像进行预处理，再转换为单通道灰度图像，选用 Canny算子提取道路图像中的边缘信息。在道路图像背景部分中，道路边缘界线一般表现为大量方向呈随机分布的短线段，且在道路实际边界附近，短线段分布密度明显高于道路路面部分。通常情况下，在路面的实际真实边界附近，边缘线分布密度最高，且道路边界内侧和外侧存在较大的边缘线密度差。检测图像中道路主体部分（直

12、线部分）的左右两条近似边界，利用霍夫变换（Hough Transform）方法拟合并提取道路边界直线。完成路面主体部分（主要指直线部分）两侧近似直线边界的提取后，在样本区域的左右两侧边界上各选择一边界中点an、bn，获得两点坐标an（xn，1，yn，1）、bn（xn，2，yn，2），并确定左右直线边界交点及其坐标cn（xn，3，yn，3）。根据3点坐标即可确定拟合出的近似道路边界ln，1、ln，2。左右直线分别记为ln，1、ln，2，边界内部区域即为样本区域，记为Sn，1，样本区域内部像素点（空间）将作为算法后续步骤的输入，用于提取当前路面的具体颜色特征和纹理特征。随后以图像Pn的样本区域Sn

13、，1为样本空间，对其中的像素点进行聚类分析。2.2样本区域移植在确定了左右直线边界的交点及其坐标cn后，根据3点坐标在图像Pn+1中找出对应的3个点an+1（xn+1，1，yn+1，1）、bn+1（xn+1，2，yn+1，2）和cn+1（xn+1，3，yn+1，3）。以an+1、cn+1兩点确定出拟合的近似道路左侧边界ln+1，1，以bn+1、cn+1两点确定出拟合的近似道路边界ln+1，2。左右直线边界内部区域即为样本区域，记为Sn+1，1，样本区域内部像素点（空间）将作为算法后续步骤的输入，用于表征当前道路路面的实际颜色特征和纹理特征，至此即完成基于图像Pn对于图像Pn+1的样本区域移植。

14、2.3聚类中心提取K-means（K均值）聚类算法属于基于数据划分思想的无监督聚类算法。样本区域Sn，1中的每个像素点作为输入样本集，随机设置K个聚类中心，再设置最大迭代次数max_iter，以标准K-means算法进行聚类，采用K-means+算法15初始化聚类中心，得到K个聚类中心（Centroids，记为Cn，1、Cn，2.Cn，k）及相应的样本类别标记（Labels，记为Ln，1、Ln，2.Ln，k）。标准K-means算法步骤如下：步骤1：从样本集合中随机选择K个样本数据作为聚类中心（随机产生），每个聚类中心代表一个样本类别。步骤2：计算样本集合中所有数据样本与每个聚类中心的欧氏距离

15、，将数据样本加入与其欧氏距离最短的聚类中心簇中（记录其数据样本编号），即对数据样本进行归类。步骤3：重新计算现在每个簇的聚类中心，更新样本类别的聚类中心，判断新聚类中心是否与原聚类中心相等。若相等，则迭代结束;若不相等，则回到步骤2继续迭代，直至迭代总次数到达算法预设的最大迭代次数。根据标准K-means算法，初始所有聚类中心均采用随机采样的方式，这意味着不能确保得到预期的聚类结果。为了优化并获得更好的聚类结果，则需要多次随机初始化所有聚类中心，将得到的多组结果进行相互对比及选择，但该方法会严重降低算法运行速度。最简单且有效的改进方法是由David Arthur提出的K-means+算法，该算

16、法可以更有效地产生初始聚类中心，确保初始化的K-means聚类后可以得到O（logk）的近似解。根据该算法思想，首先随机地初始化一个聚类中心C=C1，然后通过迭代方式计算出最大概率值：x*=argxmaxd（x，C）j=1，.，nd（xj，C）加入下一个聚类中心：CCx*直到选择K个中心。K-means+算法复杂度为O（knd），与之前方法相比，不但没有过多地增加计算负担，同时能确保算法更显著地近似于理论最优解。对于均值聚类分析算法，一般需要预先人工设定聚类类别数量。根据实际实验结果，适当地增加样本类别数量，能在一定程度上提高算法最终检测效果。然而，当聚类中心的初始设定数量过大时，单纯地提升样

17、本类别数量将不再对识别效果带来显著改善，反而会影响道路识别的有效性。为了兼顾算法的实时性，并保证其实际检测效果，将聚类中心的数量设定为5。不同聚类中心表征相应路面不同的纹理、颜色、光照强度、车道线及障碍物等路面特征。5个聚类中心（Centroids，记为Cn，1、Cn，2、Cn，3、Cn，4、Cn，5）及相应的样本类别标记（Labels，记为Ln，1、Ln，2、Ln，3、Ln，4、Ln，5），代表样本区域Sn，1中5种不同路面特征。提取经过聚类分析得到的聚类中心Cn，1、Cn，2、Cn，3、Cn，4、Cn，5的具体参数，并使其与相应的样本类别标记一一对应，构建聚类中心特征值矩阵Mn。以样本区域

18、Sn+1，2中的每个像素点作为输入样本集，经过前文所述聚类分析计算步骤后，即得到与之对应的5个聚类中心（Centroids，记为Cn+1，1、Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5）及相应的样本类别标记（Labels，记为Ln+1，1、Ln+1，2、Ln+1，3、Ln+1，4、Ln+1，5），代表樣本区域Sn+1，2的5种不同路面特征。同样提取经过聚类分析得到聚类中心Cn+1，1、Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5的具体参数，并使其与相应样本类别标记一一对应，构建聚类中心特征值矩阵Mn+1。2.4相似度判断将由图像Pn中提取出的聚类中心Cn，1、Cn，2、C

19、n，3、Cn，4、Cn，5和由图像Pn+1提取出的聚类中心Cn+1，1、Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5进行对比，若数组Cn+1与Cn相比有相似的单个数据，则判定该数据代表的样本类别为路面。例如假设图像Pn显示的路面为完全可通行路面区域，若Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5与Cn，2、Cn，3、Cn，4、Cn，5相似度较高，Cn+1，1与Cn，1有明显差异，则判定在图像Pn+1中，将Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5对应的样本类别标记为路面，Cn+1，1对应的样本类别标记为非路面特征。然后以图片Pn+1作为基准对图片Pn进行处理，得

20、到样本区域Sn+2，1与相应的聚类中心及样本类别标记;再以图片Pn+2作为对象，在图像预处理后以样本区域Sn+2，1为准，进行样本区域移植，对移植后样本区域中的样本进行聚类分析，得到聚类中心及样本类别标记，进行聚类中心特征值的相似度判断;不断迭代循环上述处理和运算步骤，即可完成对当前路径的道路检测。若检测不到任何可通行路面区域，则算法中断，自动跳出至结束。3仿真结果与分析3.1仿真平台及数据集本文计算机仿真工作在Windows 7 （x64）操作系统下完成，开发平台为Matlab R2016a。采用西安交通大学人工智能与机器人研究所（IAIR）的道路车辆数据集（Road-Vehicle Dat

21、aset ，RVD）作为图像数据来源。RVD数据集中包含了丰富的道路场景图像数据，涵盖了有着不同车道数量的城区道路与高速道路。同时，数据集涵盖了多种天气状况。3.2仿真结果利用前文所述道路车辆数据集（RVD）中的Curve_Lane（曲线车道）数据集，对本文提出的算法进行验证。该数据子集中含有数千张连续拍摄的道路图像数据，所指示的道路交通情形大体分为障碍物不影响正常行驶和障碍物影响正常行驶两种状态。其中障碍物不影响正常行驶有前方无障碍物和仅侧方有障碍物两种情形，前方有障碍物的情况即为障碍物影响正常行驶。在连续拍摄的n张图片中，选取含有3种不同障碍物分布情况的图片数据，对算法的准确性及有效性作出

22、说明。根据图4、图5两组聚类结果的散点图及聚类中心分布可以看出，两幅图片的聚类中心点C（x，y）均大多分布在区间S=127x130，128y134中。与原始数据图2、图3的实际路况作对比后可知，该分布区间S所涵盖的聚类中心点，即为可正常通行的路面区域对应的样本空间分布区间。即若某聚类中心点在区间S内，则该聚类中心点对应的实际路面特征可判定为路面区域。选取数据集中某时刻有侧方并行车辆的图片，代表仅侧方有障碍物，且障碍物不影响向前正常行驶的情形，如图6所示;选取数据集中某时刻行驶方向前方有较近距离车辆的图片，代表前方有障碍物，且障碍物影响正常行驶的情形，如图7所示。根据图8聚类结果散点图及聚类中心

23、分布可以看出，基于图6的聚类中心点C6（x，y）均分布在区间S6=128x129，128y134中。与之前判定的可正常通行路面区域对应的样本空间分布区间S进行对比可得，S6S，得到S6涵盖的聚类中心点即为可正常通行路面区域对应的样本空间分布区间，即图6所表征的道路路况为可正常通行道路。根据图9的聚类结果散点图及聚类中心分布可以看出，基于图7的聚类中心点C7（x，y）有一部分的确分布在区间S=127x130，128y134中，有3点C7，3（131，132）、C7，4（131，135）、C7，5（134，137）超出了区间分布。根据算法设定，判定此3点对应的像素特征点集合为存在障碍物，剩余两点C

24、7，1（128，128）、C7，2（129，133）在区间S中，判定为路面区域。与实际路况图像图7进行对比，C7，3、C7，4、C7，53点对应的物体为道路正前方距离较近的一辆黑色小型汽车与路面上的浅色减速带，其判断的是否有障碍物情况与路面实际障碍物情况吻合，成功验证了算法的准确性和有效性。4结语针对智能车视觉导引中的道路检测问题，提出一种基于Kmeans算法的AGV二步迭代道路检测算法。以间隔一定周期拍摄的连续道路图像为数据输入，与传统利用拍摄实时视频作为数据输入的方式相比，大大减少了数据存取及传输量，节约了设备硬件资源;在传统根据道路边界进行路径检测的基础上，加入基于Kmeans聚类中值算

25、法的无监督机器学习技术，既可以实现路面样本的动态添加与判断，又避免了针对大量路面样本的提前训练工作;将传统的道路形态学检测与针对像素点的特征聚类及分析判定技术相结合，大大增强了对正常路面及非路面的识别能力，提高了检测速度，降低了道路检测技术对硬件设备的要求，增强了实用性。未来的研究方向为：继续针对多个连续图像，对其相关性进行发掘，以提高路面识别速度与检测效果;改进现有聚类中心提取方法，实现自适应确定聚类中心个数，进一步减少人工操作;设计完善的连续采样机制和特征学习方法，增强算法对具体障碍物的判别能力。ReferenceReference：1潘奎刚.智能车辆基于视觉的可通行区域检测方法D.南京：南京理工大学，2017.2张舒原.视觉导引AGV及其在制造业厂内的应用J.物流技术与应用，2016，21（3）：114117.3娄会东.视觉导引的物料搬运AGV关键技术研究D.广州：华南理