基于颜色特征聚类的路径标线检测算法

孟德欣，王民权，胡国伟

（宁波职业技术学院 a.电子信息学院；b.海天机电学院，浙江 宁波315800）

基于颜色特征聚类的路径标线检测算法

孟德欣a，王民权b，胡国伟a

（宁波职业技术学院 a.电子信息学院；b.海天机电学院，浙江 宁波315800）

针对视觉导航中路径彩色图像数据量大、维数高，引导标线检测算法耗时较长的问题，提出一种基于颜色特征聚类的快速标线检测算法。在分析常见的标线检测算法特征基础上，建立彩色图像的颜色稀疏矩阵，隔行检测疑似标线的颜色特征点，计算各特征点之间的近邻系数，利用近邻函数法对颜色特征点聚类分析，找出特征点最多的目标类作为标线，按路径结构将特征点连通，并提供路径导航信息。实验结果表明，与传统颜色空间转换和基于霍夫变换的边缘检测算法相比，该算法运算速度较快，能够满足实时性要求。

视觉导航；标线检测；最近邻函数法；颜色特征；聚类

DO I：10.3969/j.issn.1000-3428.2015.10.044

1 概述

视觉导航的智能车通常采用标线跟踪导航，通过计算机视觉技术对路径和障碍物图像理解并提供自动导引，相比较其他导航法如磁导航、激光导航、毫米波雷达法、GPS导航等，视觉导航法具有高精度、柔性控制、环境适应性和应用成本等方面的优势，基于视觉导航的智能车应用广泛［1-3］。

目前，智能车采集的路径图像多为彩色图像，相比于灰度图像其信息量大，标线检测和跟踪的速度对计算机图像处理提出更高的实时性要求。在运动速度较快的情况下，标线检测的速度和准确性对后续路径跟踪导航效果有很大影响［4］。现有的标线检测算法为提高实时性常见做法是把采集到的彩色图像转换为灰度图像，然后再检测标线信息，这种算法由于丢失了色彩信息，目标的分割并不准确，而且灰度图像对光照不均匀、阴影、水渍等的鲁棒性较差［5-6］。

针对路径彩色图像数据量大、维数高，标线检测算法耗时的问题，本文在分析彩色路径图像的颜色特征基础上，采用近邻函数法聚类模型对疑似标线的特征点进行聚类分析，检测标线的边界特征，然后按路径结构将其连通，从而识别标线的位置和形状［7-9］，使运动控制模块根据路径信息做出相应的移动。

2 近邻函数法的聚类模型

常见的C-均值法适合于类别数确定及初始聚类中心选定的情况，对于类内球状分布一般都能够达到理想的聚类效果，但易受类别数及初始聚类中心的影响，是一种局部最优的聚类算法［10］。

近邻函数法与C-均值法不同，特别适合于类内条状或线状分布的情况，如图1所示。

图1 类内条状或线状分布

考虑到路径图像中标线为条状分布，本文采用近邻函数法对标线特征点进行聚类，引入类内、类间损失函数作为评价依据，构造聚类准则函数，最后选出聚类结果中包含特征点最多的类设为目标类。

定义1 近邻函数

在图像矩阵中，考虑像素点样本χi，计算χi与其他各样本间的近邻函数值，表示为：

式（1）表示连接损失Lij是样本χi与χj连接损失最小值，如χi与 χj没有实际连接，则不存在连接损失L。

定义2 类内连接损失

设样本集共有c类，表示为 wP（P=1，2，…，c），则总的类内连接损失定义为：

定义3 类间连接损失

设聚类wP和 wq（P，q=1，2，…，c；q≠P），则总的类间连接损失定义为：

其中，类wP和 wq（P，q=1，2，…，c；q≠P）的样本之间最小近邻函数值为：

式（4）表示除wP类内样本外，wq中的某一个样本与wP中的某一个样本最近邻，近邻函数值为βPq，此时还需要考虑 wP和 wk是否可以合并，如要合并则进行迭代运算。

记wP类的类内最大近邻函数值：

则wP和wq类的类间损失函数定义如下：

其中，当 βPq＞γPmaχ，βPq＞γkmaχ，表示类间近邻函数值大于类内最大近邻函数值，说明聚类结果是合理，其他情况则需进行调整。

定义4 聚类准则函数

在计算出类间损失函数 χPq的基础上，类间总损失函数定义如下：

聚类的目标是使各 βPq尽可能大，γPmaχ尽可能小，则构造聚类准则函数如下：

每次对2个类合并，这样聚类准则函数的值每次都要增加，若是函数值的增加在每一次合并时都是最小的，则得到的分类结果为最优。否则，则需重复此过程。

3 标线检测算法

在采集路径图像过程中，由于受到环境噪声的干扰等原因造成噪声产生，图像信息会有所丢失。故在标线检测算法先对图像预处理，包括去噪、设置适当的阈值建立颜色稀疏矩阵这样可以减少算法处理时间，利用隔行检测疑似标线的颜色特征点，接着利用近邻函数法对特征点聚类，选取特征点最多的类别为目标类，即为标线，同时给出控制指令，下达给运动控制模块。

标线检测算法的执行过程如下：

（1）图像预处理

包括图像滤波、增强和颜色空间转换等。采集图像由于各种原因会存在噪声和畸变，需要进行滤波处理和图像增强，达到改善图像的目的。均值滤波能有效去除随机噪声，但当噪声比较密集时效果明显减弱，中值滤波是一种快速抑制图像噪声的非线性技术，其原理是把图像中的一点（χ，y）的值用该点邻域S内的各点（s，t）的中值代替，邻域窗口大小通常取一个包含奇数个像素点的窗口，窗口大小为3×3或5×5时，在去噪方面通常具有良好的滤波效果［11］。 中值滤波公式为：

其中，f（χ，y）表示像素点（χ，y）的灰度值；s，t分别表示水平、垂直方向的范围。中值滤波时使用大小为3×3或5×5的采样窗口扫描图像，直到找到符合条件的像素点，然后在采样窗口中取出奇数个像素点进行排序，并用排序后的中值取代要处理的像素点数据即可。

考虑到人眼对亮度信息的敏感程度较色差信息要高的视觉特点以及标线为红色、蓝色的特征，本文算法将RGB的路径彩色图像转换为YUV颜色空间。在YUV颜色空间中，每一个颜色有一个亮度分量矩阵Y和2个色差分量矩阵U和V。其中，亮度分量矩阵Y把RGB信号的亮度部分叠加到一起，色

差分量矩阵U，V实际上就是蓝色差信号和红色差信号，一定程度上间接的代表了蓝色和红色的强度［11］。该模型将亮度和色调分开，适用于图像处理中对光照比较敏感的情况。

在YUV颜色空间中，辨识图像的主要依据来源于亮度分量矩阵Y。YUV颜色空间和RGB颜色空间之间的关系如下式所示［12］：

然后，考虑到标线为红色、蓝色，在YUV颜色空间进行YUV三通道分解，增加其中的红色、蓝色分量矩阵U，V通道的亮度信息。

（2）隔行检测颜色特征点

在对图像预处理后，通过设置阈值对图像水平方面进行隔行扫描，检测标线的颜色特征点。考虑到标线连续颜色无跳跃的实际情况，隔行扫描的处理算法是合理的，能够有效节省算法执行时间。经实验得出，行间距设置为40行 ～60行之间比较合适。在扫描过程中，颜色特征点检测需设置阈值来进行判断，算法中根据标线的宽度等先验知识预先设置了标线颜色、宽度等信息的阈值，在隔行扫描过程中只有满足大于颜色、宽度阈值的一些像素点才被确认为特征点并存储起来。

（3）对疑似颜色特征点进行聚类

接下来，对特征点进行聚类分析。对于特征点样本集｛χ1，χ2，…，χn｝，计算特征点的距离矩阵 D，D表示如下：

其中，d（χi，χj）表示 χi和 χj特征点之间的距离。在距离矩阵D中计算出近邻系数矩阵M，M为一个稀疏矩阵，其元素为各样本间的近邻系数。

接着生成近邻函数矩阵 L，置主对角线元素Lij=2N，如果χi和χj有连接，则Lij则是连接损失即近邻函数值，同时对矩阵L进行遍历，将每个特征点与它的最小近邻函数值的特征点连接起来，从而形成初始聚类。

在初始聚类中，计算 βPq，γPmaχ，γkmaχ，如 βPq小于或等于γPmaχ或γkmaχ，则合并wP和wk，将以上过程迭代执行，最终使得准则函数 JL稳定到最小值，聚类过程结束。

（4）选取特征点最多的聚类为目标类

聚类过程所产生的包含特征点最多的目标类即标线，然后输出标线信息，再由运动控制模块计算出转向角、速度等控制参数，进而控制智能车的移动［13］。

4 实验结果与分析

在仿真实验中，智能车由电源模块、信息获取和处理模块、导航控制与运动模块等组成，智能车的路径图像获取通过数码摄像头来采集，并以文件形式保存在计算机中，通过VC++软件平台对此图像文件进行处理和分析，最后通过标线检测算法实现标线信息的检测。对于工作环境中有多个疑似标线的复杂情况，本文算法能够实时、准确地检测并检测出疑似标线特征，识别出特征点最多的目标类，即标线。

实验中，在测试场地中的引导线为红色，停止位（或工作位）为蓝色。原始采集图像为RGB彩色图像，分辨率为320×240像素，采集频率为30 f/s。图2中垂直方向中心线为智能车正前方的中心引导线，垂直方向的4条粗标线为引导线，水平方向的1条粗标线为停止位，引导线中已标示出已检测出的特征点。其中，引导线和停止位的特征点检测结果如图3所示。

图2 标线

图3 标线的特征点

实验中设置引导线的红色阈值为185，停止位标线的蓝色阈值为165，标线最大宽度阈值为100，标线最小宽度阈值为30。算法对引导线的特征点计算结果如图4所示。

图4 结果输出

图4一共有4段引导线，运算时间为28.371 1 ms，算法共检测出4个聚类。其中，第3类包含特征点最多（10个）被确定为目标类，即真正的引导标线。另外，第4类的特征点数为2，由于少于3个，考虑到标线较长的实际情况，因此忽略不计。检测结果如表1所示。

表1 疑似标线检测结果

可见本文算法可以快速检测标线，满足视觉导航智能车对实时性的要求。实验结果说明本文算法可行有效。

5 结束语

针对彩色路径图像中的标线检测算法，本文采用近邻函数法对颜色特征点进行聚类分析，构造基于类内类间距离的准则函数，找出特征点最多的目标类即引导标线，然后按标线结构将其连通，并输出运动控制模块。实验结果表明，与传统颜色空间转换以及基于霍夫变换的边缘检测算法相比，该算法的实时性较好，对于视觉导航的智能车有一定的应用价值。

［1］ Yu Qifeng，Shang Yang，Liu Xiaochun，et al.Fullparameter Vision Navigation Based on Scene Matching for Aircrafts［J］.Science China Inform ation Sciences，2014，57（5）：1-10.

［2］ Morioka H，Sangkyu Y，Hasegawa O.Vision-based Mobile Robot’s SLAM and Navigation in Crowded Environments［C］//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Washington D.C.，USA：IEEE Press，2011：3998-4005.

［3］ Yang Ming，Lu Zhengchen，Guo Lindong，et al.Visionbased Environmental Perception and Navigation of Micro-intelligent Vehicles［M］//Sun Fuchun，Li Tianrui，Li Hongbo.Foundations and Applications of Intelligent Systems.Berlin，Germany：Springer，2014：653-665.

［4］ Park C H，K im N H.Precise and Reliable Positioning Based on the Integration of Navigation Satellite System and Vision System［J］.International Journal of Automotive Technology，2014，15（1）：79-87.

［5］ Zang Guoquan，Li Zhanming.Research on Preprocessing of Color Im age for Vision Based Mobile Robot Navigation［J］.Information Technology Journal，2011，10（3）：597-601.

［6］ Bertozzi M，Broggi A，Fascioli A.Vision-based Intelligent Vehicles：State of the A rt and Perspectives［J］. Robotics and Autonomous System，2000，32（1）：1-16.

［7］ Kim Y H，Lee S W，Yang H S，et al.Toward Autonomous Robotic Containment Booms：Visual Servoing for Robust Inter-vehicle Docking of Surface Vehicles［J］. Intelligent Service Robotics，2012，5（1）：1-18.

［8］ Li Ying，Hong Sheng，Huang Jieming，et al.The New Environment Model Building Method of Penetration Mission Based on the Artificial Potencial Field Approach［C］//Proceedings of IEEE International Multidisciplinary Conference on Cognitive Methods in Situation Awareness and Decision Support.Washington D.C.，USA：IEEE Press，2012：121-124.

［9］ 徐 超，沈晓蓉，罗宇锋，等.视觉导航特征点匹配及误匹配剔除算法［J］.计算机仿真，2010，27（4）：236-239.

［10］ 朱铮涛，张 宏.基于特征点的形状匹配技术及其算法实现［J］.计算机工程与设计，2010，31（5）：1096-1099.

［11］ 孙即祥.现代模式识别［M］.长沙：国防科技大学出版社，2002.

［12］ Wei Weiyi，Li Zhanming，Zang Guoquan.Novel Fuzzy Clustering-based Image Segmentation with Simultaneous Uneven Illumination Estimation［J］.Information Technology Journal，2011，10（3）：607-610.

［13］ 吴建民，王民钢.基于视觉的轮式移动机器人导航问题研究［J］.计算机工程，2014，40（8）：143-146.

编辑 刘 冰

Path Marking Detection Algorithm Based on Color Feature Clustering

MENG Dexina，WANG Minquanb，HU Guoweia
（a.Electronics&Information Institute；b.Haitian M echanical&Electrical Institute，Ningbo Polytechnic，Ningbo 315800，China）

According to the path of color image data volume，high dimension，guide marking detection algorithm and time-consuming problem in visual navigation，a fast marking detection algorithm in path image based on color feature clustering is proposed.Based on the analysis of the common features of marking detection algorithm，it establishes a color sparse matrix on color image，adopts interlacing detection feature point in suspected marking，calculates neighbor coefficient between the each feature point and clusters by using of neighbor function method，finds out the target class with most feature point which is marking，connects the path structure with feature points set，and provides the route navigation information. Experimental results indicate that compared with the conventional color space conversion or edge detection algorithm based on the Hough transform，the speed of this algorithm is fast，and can meet the real-time requirements.

visual navigation；marking detection；nearest neighbors function method；color feature；clustering

孟德欣，王民权，胡国伟.基于颜色特征聚类的路径标线检测算法［J］.计算机工程，2015，41（10）：236-239.

英文引用格式：Meng Dexin，Wang Minquan，Hu Guowei.Path Marking Detection Algorithm Based on Color Feature Clustering［J］.Computer Engineering，2015，41（10）：236-239.

1000-3428（2015）10-0236-04

A

TP391.9

宁波市2014年自然科学基金资助项目“基于动态辐射的跟踪式光伏板聚光量增益的研究”（2014A 610075）。

孟德欣（1976-），男，副教授、硕士，主研方向：图像处理，模式识别；王民权，教授；胡国伟，博士研究生。

2014-10-28

2014-11-24E-mail：78924661@qq.com