灰度直方图与LDA的路况分类

史晓鹏，何为，韩力群

(北京工商大学计算机与信息工程学院，北京 100048)

灰度直方图与LDA的路况分类

史晓鹏，何为，韩力群

(北京工商大学计算机与信息工程学院，北京 100048)

道路路况实时分类研究，是路况信息诱导系统的基础.通过对大量路况图像进行研究，提出使用路况图像中道路区域统计灰度直方图作为表征路况信息的特征向量，采用LDA(linear discriminat analysis)算法对高维特征向量进行降维，采用改进的K－近邻分类器实现对道路路况实时分类，并给出实际分类结果.实验结果表明，采用上述方法进行路况分类，其结果与交通管理部门给出的结果一致率达91.7%，对路况实时分类具有较高的实用价值.

路况分类;灰度直方图;LDA;K－近邻分类器

交通拥堵问题已经在中国各大城市日益凸显，最好的解决方法已经不是无限制地修建或扩建道路缓解交通拥堵，而是要发展智能交通.作为智能交通的一个领域，路况信息的实时获取显得尤为重要.通过图像处理与模式识别等信息处理技术手段进行路况信息的实时采集，对当前道路拥堵状况做出真实、准确地描述，是智能交通系统［1］(ITS)中最基本和最重要的工作.

传统的检测方法，如线圈检测［2］需要占用道路埋入感应线圈，这无疑增大了该条道路的交通压力.视频检测［3－4］是现在发展很快的一项检测方法，运用图像分割和目标跟踪识别可以提取道路机动车数量、速度，作为路况特征参数对路况进行分类，文献［2］中使用了基于帧间差分方法更新道路背景模型，统计出现频率最大的灰度值，得到初始背景数据.该方法在帧图像较大时，计算量大，实时性不够好.

通过对大量路况图像的研究，发现路况灰度图像中的道路区域是一近似灰度平坦区，对于畅通、缓行、拥堵3种典型路况，由于道路区域被车辆遮挡的原因，使得该区域灰度直方图发生明显变化.基于该种特性，提出采用路况图像的灰度直方图作为特征，使用LDA算法对直方图采样点进行降维，并结合改进K－近邻算法对路况进行分类.实践证明，由于直方图特征获取的快速性以及LDA算法降维减少了高维向量计算，该方法对于实时路况分类是行之有效的.

1 灰度直方图处理

1.1 图像预处理

路况图像中道路区域［5－7］的提取是必要的.实际场景中的路况图像，由于采集的地点不同，造成图像灰度分布极其不均，但是同一地点中道路区域的灰度分布会呈现出一定规律，因此首先要分割出路况图像中的道路区域.方便起见，采用手动分割的方法确定原始图像(见图1(a))中的道路区域，制作道路区域提取掩模(见图1(b))，以提取图像中的道路部分(见图1(c)).

图1 路况图像中的道路区域分割Fig.1 Segmentation of a road image

1.2 直方图重采样与均值滤波

路况图像完成道路区域的提取后，得到只含有道路与车辆的图像，统计该区域的灰度直方图，如图2(a)所示.在大量统计中发现所有道路区域灰度直方图的右端几乎为0，因此，在0～255灰度级内保留1～200的灰度级(如图2(b))，形成一个200维的特征向量.

图像采集过程中，即使使用同一监控探头，也会发生相邻两帧图像灰度突变的情况，这种突变来自于探头自身噪声，因此需要对路况图像进行滤波.本文将1～200灰度级内的统计量进行重采样与均值滤波一体化处理:将相邻5个灰度级的统计量取平均值，在保留图像灰度特性的同时，平滑灰度突变干扰，降低直方图特征向量维度.经重采样与均值滤波后的直方图如图2(c)所示.

图2(c)显示了经重采样与滤波后的直方图保留了原直方图(图2a)中的双峰特性.因此，本文将这40个直方图平滑采样点，作为描述一幅路况图像的高维向量样本.

图2 道路区域直方图处理Fig.2 Histogram processing of road region image

2 基于LDA的高维向量降维

处理后的灰度直方图反映了路况图像的车流量特征，但作为特征向量其分度偏高，不利于了解特征空间样本的拓扑结构.线性判别分析［8］(linear discriminant analysis，LDA)是一种用于分类的有效特征降维方法，其核心思想是通过已知的样本分类信息，构造使判别矢量集达到极大值的最佳降维向量，将输入的高维向量投影到低维空间以实现数据降维，并使降维后的样本达到最大类间离散度和最小类内离散度，具有最佳可分离性，从而帮助样本在低维空间实现最优分类［9－13］.

2.1 LDA算法原理

通过已知的样本分类信息构建输入样本的类内离散度:

式中:x为D维空间输入样本;mi为第i类平均样本;与类间离散度:

式中:c为样本类别个数;ni为第i类样本个数;m为全部样本平均样本.

式(1)表征同一类别内样本的分散程度，式(2)表征不同类别间平均样本的分散程度，然后构造最佳降维向量W，并将判别矢量集定义为

图3 二维样本LDA降维示意Fig.3 Using LDA in two dimensional space

2.2 LDA应用设计

本文中，将路况图像的40维向量看作高维向量，使用LDA算法对该向量进行降维.由于已知路况类别为3类，降维后，该向量被降到二维空间.在降维后的二维空间(图4)中，可以看到数据分布具有最佳可分离性.

使用LDA算法时，训练样本个数选取不应过少.当输入训练样本个数小于样本维数时，会使类内离散度Sw非奇异，而无法构造降维向量W;如果训练样本个数过多，会增大计算复杂度，影响LDA降维速度.综合考虑如上问题，选取120幅典型路况图像作为训练样本，这些路况图像为同一地点、不同时段、不同路况的样本，并标定每幅样本的路况，即已知样本分类信息为:畅通样本40幅，缓行样本40幅，拥堵样本40幅.将每幅样本灰度直方图的40个采样点作为40维向量，进行LDA降维.由已知的样本分类信息为3类，构造列数为2的最佳降维向量W，图4给出了120幅训练样本经LDA降维到2维空间的分布情况.

图4 训练样本经LDA降维后在二维空间分布Fig.4 Train-samples in two dimensional space after LDA

图4表明，输入的120幅40维向量训练样本经LDA降维到二维空间后，分类特征明显.因此，在二维空间设计分类器便可对未标定路况的样本进行分类.

3 基于K－近邻改进算法的分类

3.1 K－近邻(K－NN)算法

K－近邻(K－nearest neighborhood)算法是分类未知数据最直接的方法，其基本思想是:找到和待分类样本最相似的k个已分类样本，根据这k个样本所属类别判断待分类样本所属类别，如图5所示.对于一个待分类样本，计算其与训练样本中每一样本的欧式距离(见式(4))，找出与待分类样本最近的k个近邻，依据k个近邻在每类中所占比重，将待分类样本归入所占比重最大的类别.

式中:x为待分类样本，μi为训练样本中第i个样本.

图5 K-近邻算法示意Fig.5 K-NN algorithm

本文选取与训练样本不同的120幅标定路况样本作为待分类样本进行测试.其中，畅通样本40幅，缓行样本40幅，拥堵样本40幅，使用传统K－近邻算法对路况样本进行分类，比较分类结果与标定结果，在表1中给出统计情况.

表1 K－近邻算法分类结果统计Table 1 Results of using K-NN algorithm

3.2 对K－近邻(K－NN)算法的改进

K－近邻算法中计算了待分类样本与所有训练样本的欧式距离，事实上仅使用了其中较小的k个样本作为分类依据.为了充分利用训练样本，本文将统计3类别内所有距离和作为分类依据，将当前样本归入距离和最小的类别.表2给出了相同测试样本使用改进K－近邻算法的分类结果统计.

对比表2与表1可以看出，由于充分利用了类别内所有训练样本，改进K－近邻算法使分类结果准确率有所提升.

表2 改进K－近邻算法分类结果统计Table 2 Results of using improved K-NN algorithm

此外，由于路况评价因人而异，本文在使用改进K－近邻算法得到的3个距离和的同时，去除距离和最大者，计算待分类样本属于另外2类的百分比，作为当前分类结果的可信度，为孤立的分类结果添加人性化的参考.

图6显示了3幅标定为畅通的场景，表3依次中列举了这3幅场景用可信度描述的分类结果.对比表3中的第1、2行可以看出，分类结果与标定结果相符合，可信度52.9%表明尽管当前路况分类结果为畅通，但畅通和缓行的可信度比例已经接近1:1，这为人们对路况分类结果的理解提供了参考，帮助理解当前路况的畅通程度;对比表中的第2、3行可以看出，当可信度较低时，分类结果不能代表当前实际路况，实际路况介于畅通和缓行之间.由此可见，可信度反映了分类结果与实际路况的相似程度.

图6 标定为畅通的场景Fig.6 Scenes of tagging unobstructed

表3 用可信度描述图6的分类结果Table 3 Results of Fig.6 with reliability

4结论

实践证明，使用路况图像灰度直方图统计特征，结合LDA降维与改进K－近邻的分类器能够良好地进行实时路况分类，分类效果与交管局实时发布路况信息相当.主要优越性概括如下.

1)无需二次投入与占用道路，有效利用现有监控摄像头资源.

2)路况图像灰度直方图提取与LDA降维算法计算复杂度低、效率高、分类效果良好.

3)改变了传统的孤立分类，分类结果人性化.

虽然LDA算法对灰度特征向量降维效果良好，但是由于3种典型路况训练样本的选取因人而异，即同一幅路况图像，不同人会给出不同分类结果，因此在实际应用中，要合理选取标定的训练样本.此外，由于路况图像中灰度特性只反应了静止场景特征，且这种特征会因光照影响而发生变化;因此，在今后的研究工作中，应结合前后帧图像考虑动态场景，并研究去除光照影响的方法.

［1］钟石泉，马寿峰，贺国光.交通诱导系统路网状态描述方法及仿真研究［J］.系统工程学报，2009，24(1):25－31.

ZHONG Shiquan，MA Shoufeng，HE Guoguang.Description and simulation of dynamic route guidance system road network［J］.Journal of System Engineering，2009，24(1):25－31.

［2］叶青.道路交通参数检测系统设计［J］.中南公路工程，2005，30(4):110－112.

YE Qing.Design of traffic flow parameter detection system［J］.Central South Highway Engineering，2005，30(4):110－112.

［3］WANG Guolin，XIAO Deyun.Review on vehicle detection based on video for traffic surveillance［C］//Proceedings of the IEEE International Conference on Automation and Logistics.Qingdao，China:IEEE Press，2008:2961－2965.

［4］SHI Wei，WU Jian，ZHOU Shaolin，et al.Variable message sign and dynamic regional traffic guidance［J］.Intelligent Transportation System Magazine，2009，1(3):15－21.

［5］王燕清，陈德运，石朝侠.基于单目视觉的非结构化道路检测与跟踪［J］.哈尔滨工程大学学报，2011，32(3):334－339.

WANG Yanqing，CHEN Deyun，SHI Chaoxia.Unstructured road detection and tracking based on monocular vision［J］.Journal of Harbin Engineering University，2011，32(3):334－339.

［6］耿凯，姚丹亚，张毅.一种基于灰度直方图的交通检测系统［J］. 计算机工程与应用，2006，4:222－225.

GENG Kai，YAO Danya，ZHANG Yi.A grey－histogram based traffic detection system［J］.Computer Engineering and Applications，2006，4:222－225.

［7］边肇祺，张学工.模式识别［M］.2版，北京:清华大学出版社，1999:140－142.

［8］李晓辉，梨湘，郭桂蓉.基于LDA算法的一维距离像特征提取［J］. 国防科技大学学报，2005，27(6):72－76.

LI Xiaohui，LI Xiang，GUO Guirong.Feature extraction of HRRP based on LDA algorithm［J］.Journal of National university of Defense Technology，2005，27(6):72－76.

［9］LU Juwei，PLATANIOTIS K N，VENETSANOPOULOS A N.Face recognition using LDA－based algorithms［J］.IEEE Transactions on Neural Networks，2003，14(1):195－200.

［10］BRESSAN M，VITRIA J.Nonparametric discriminant analysis and nearest neighbor classification［J］.Pattern Recognition Letters，2003，24(15):2743－2749.

［11］LI Zhifeng，LIN Dahua，TANG Xiaoou.Nonparametric discriminant analysis for face recognition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31(4):755－761.

［12］CEVIKALP H，NEAMTU M，WILKES M，et al.Discriminative common vectors for face recognition［J］.IEEE Transactions on Analysis and Machine Intelligence，2005，27(1):4－13.

［13］WANG Jigang，NESKOVIC P，COOPER L N.Neighborhood size selection in the K－nearest－neighbor rule using statistical confidence［J］.Pattern Recognition，2006，39(3):417－423.

史晓鹏，男，1987年生，硕士研究生，主要研究方向为图像处理与模式识别.

何为，男，1953年生，硕士，高级工程师，IEEE会员，中国人工智能学会理事，中国人工智能学会智能产品与产业工作委员会秘书长，中国计量测试学会高级会员.主要研究方向为非电量检测技术、计算机测控技术、嵌入式技术应用.主持或参加国家科技攻关、火炬计划、省部级、横向等各类科研项目30余项，获国家发明专利3项，发表学术论文30余篇.

韩力群，女，1953年生，教授，中国人工智能学会副理事长，主要研究方向为事智能信息处理与图像工程领域研究，主持各类科研课题30余项，出版著作10部;获国家发明专利3项，北京发明创新大赛银奖1项，发表学术论文120余篇.

Research on traffic information classification based on a grey-histogram and linear discriminant analysis

SHI Xiaopeng，HE Wei，HAN Liqun
(College of Computer Science and Information Engineering，Beijing Technology and Business University，Beijing 100048，China)

Research on real－time traffic information classification is the basis of traffic guidance systems.In this paper，a high dimension feature vector based on a grey－histogram sampling of a road region image was proposed.The classification algorithms of linear discriminant analysis(LDA)and an improved K－Nearest Neighborhood(K－NN)were adopted to reduce the high dimension vector and classify real time traffic information.The experimental results show that the proposed traffic information classification method can supply the same traffic information as what comes from the Beijing Traffic Management Bureau;the rate of identical information is as high as 91.7%.

traffic information classification;grey－histogram;LDA;K－NN

TP391.4

A

1673－4785(2011)04－0328－05

10.3969/j.issn.1673－4785.2011.04.008

2010－08－02.

史晓鹏.E－mail:davidxp87@yahoo.com.cn.