第6卷第4期 智能系统学报 Vol.6 No.4 2011年8月 CAAI Transactions on Intelligent Systems Aug.2011 doi:10.3969/i.i8sn.1673-4785.2011.04.008 灰度直方图与LDA的路况分类 史晓鹏，何为，韩力群 (北京工商大学计算机与信息工程学院，北京100048) 摘要：道路路况实时分类研究，是路况信息诱导系统的基础.通过对大量路况图像进行研究，提出使用路况图像中 道路区域统计灰度直方图作为表征路况信息的特征向量，采用LDA(linear discriminat analysis)算法对高维特征向量 进行降维，采用改进的K-近邻分类器实现对道路路况实时分类，并给出实际分类结果.实验结果表明，采用上述方法 进行路况分类，其结果与交通管理部门给出的结果一致率达91.7%，对路况实时分类具有较高的实用价值. 关键词：路况分类；灰度直方图；LDA;K-近邻分类器 中图分类号：TP391.4文献标识码：A文章编号：16734785(2011)04032805 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) Abstract:Research on real-time traffic information classification is the basis of traffic guidance systems.In this pa- per,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%. Keywords:traffic information classification;grey-histogram;LDA;K-NN 交通拥堵问题已经在中国各大城市日益凸显， 图像较大时，计算量大，实时性不够好。 最好的解决方法已经不是无限制地修建或扩建道路 通过对大量路况图像的研究，发现路况灰度图 缓解交通拥堵，而是要发展智能交通.作为智能交通 像中的道路区域是一近似灰度平坦区，对于畅通、缓 的一个领域，路况信息的实时获取显得尤为重要.通 行、拥堵3种典型路况，由于道路区域被车辆遮挡的 过图像处理与模式识别等信息处理技术手段进行路 原因，使得该区域灰度直方图发生明显变化.基于该 况信息的实时采集，对当前道路拥堵状况做出真实、 种特性，提出采用路况图像的灰度直方图作为特征， 准确地描述，是智能交通系统)(T$)中最基本和 使用LDA算法对直方图采样点进行降维，并结合改 最重要的工作. 进K-近邻算法对路况进行分类.实践证明，由于直 传统的检测方法，如线圈检测2]需要占用道路埋 方图特征获取的快速性以及LDA算法降维减少了 入感应线圈，这无疑增大了该条道路的交通压力.视 高维向量计算，该方法对于实时路况分类是行之有 频检测[34是现在发展很快的一项检测方法，运用图 效的， 像分割和目标跟踪识别可以提取道路机动车数量、速 度，作为路况特征参数对路况进行分类，文献[2]中使 1灰度直方图处理 用了基于帧间差分方法更新道路背景模型，统计出现 1.1图像预处理 频率最大的灰度值，得到初始背景数据.该方法在帧 路况图像中道路区域5]的提取是必要的.实 收稿日期：2010-0802. 际场景中的路况图像，由于采集的地点不同，造成图 通信作者：史晓鹏.E-mail:davidxp87@yahoo.com.cm. 像灰度分布极其不均，但是同一地点中道路区域的
第4期 史晓鹏，等：灰度直方图与LDA的路况分类 ·329· 灰度分布会呈现出一定规律，因此首先要分割出路 道路区域提取掩模（见图1(b)),以提取图像中的 况图像中的道路区域.方便起见，采用手动分割的方 道路部分（见图1(c)). 法确定原始图像（见图1(a))中的道路区域，制作 (a,原始路况图像 )道路区域提取掩模 (路况图像中道路区域 图1路况图像中的道路区域分割 Fig.1 Segmentation of a road image 1.2直方图重采样与均值滤波 文将1~200灰度级内的统计量进行重采样与均值 路况图像完成道路区域的提取后，得到只含有 滤波一体化处理：将相邻5个灰度级的统计量取平 道路与车辆的图像，统计该区域的灰度直方图，如图 均值，在保留图像灰度特性的同时，平滑灰度突变干 2(a)所示.在大量统计中发现所有道路区域灰度直 扰，降低直方图特征向量维度.经重采样与均值滤波 方图的右端几乎为0，因此，在0~255灰度级内保 后的直方图如图2(c)所示 留1~200的灰度级（如图2(b)),形成一个200维 图2(c)显示了经重采样与滤波后的直方图保 的特征向量。 留了原直方图（图2a)中的双峰特性.因此，本文将 图像采集过程中，即使使用同一监控探头，也会 这40个直方图平滑采样点，作为描述一幅路况图像 发生相邻两帧图像灰度突变的情况，这种突变来自 的高维向量样本。 于探头自身噪声，因此需要对路况图像进行滤波.本 0.04 0.04 0.03 0.03 0.03 0.02 0.02 0.02 0.01 0.01 0.01 50 150250 0 50100150200 0 10203040 (a)道路X域直方图 b)1-200灰度级直方图 (©)采样后的直方图 图2道路区域直方图处理 Fig.2 Histogram processing of road region image 2基于LDA的高维向量降维 及=名80红-m-川 (1) 处理后的灰度直方图反映了路况图像的车流量 式中：x为D维空间输入样本；m:为第i类平均样 特征，但作为特征向量其分度偏高，不利于了解特征 本；与类间离散度： 空间样本的拓扑结构.线性判别分析8](linear dis- =a(m,-m)(m-m. (2) criminant analysis,.LDA)是一种用于分类的有效特 征降维方法，其核心思想是通过已知的样本分类信 式中：c为样本类别个数；n,为第i类样本个数；m为 息，构造使判别矢量集达到极大值的最佳降维向量， 全部样本平均样本， 将输人的高维向量投影到低维空间以实现数据降 式(1)表征同一类别内样本的分散程度，式(2) 维，并使降维后的样本达到最大类间离散度和最小 表征不同类别间平均样本的分散程度，然后构造最 类内离散度，具有最佳可分离性，从而帮助样本在低 佳降维向量W,并将判别矢量集定义为 维空间实现最优分类93] J.(wM)= S。_WSW ws.W (3) 2.1LDA算法原理 通过已知的样本分类信息构建输入样本的类内 2个离散度降维后，期望类内离散度S。极小， 离散度： 类间离散度S,极大，即式(3)达到极大值.因此W
330 智能系统学报 第6卷 需满足：SW=入SW.若S非奇异，则SS。W= 图4表明，输人的120幅40维向量训练样本经 AW,W每一列由SS。的前c-1个较大特征值对 LDA降维到二维空间后，分类特征明显.因此，在二维 应的特征向量构成，从而得到最佳降维向量W,图3 空间设计分类器便可对未标定路况的样本进行分类 给出了对二维样本进行LDA降维的示意图. 3基于K-近邻改进算法的分类 3.1K-近邻(K-NN)算法 K-近邻(K-nearest neighborhood)算法是分类未 最佳降维 知数据最直接的方法，其基本思想是：找到和待分类 样本最相似的k个已分类样本，根据这k个样本所 属类别判断待分类样本所属类别，如图5所示.对于 一个待分类样本，计算其与训练样本中每一样本的 欧式距离（见式(4）)，找出与待分类样本最近的k 图3二维样本LDA降维示意 个近邻，依据k个近邻在每类中所占比重，将待分类 Fig.3 Using LDA in two dimensional space 样本归入所占比重最大的类别. 2.2LDA应用设计 d,(x)=√(x-4)(x-) (4) 本文中，将路况图像的40维向量看作高维向 式中：x为待分类样本丛为训练样本中第i个样本 量，使用LDA算法对该向量进行降维.由于已知路 况类别为3类，降维后，该向量被降到二维空间.在 0.25 ,畅遇+缓行△拥堵 降维后的二维空间（图4）中，可以看到数据分布具 0.20 待分类样本 有最佳可分离性， 0.15 使用LDA算法时，训练样本个数选取不应过 0.10 少.当输入训练样本个数小于样本维数时，会使类内 0.05 离散度S,非奇异，而无法构造降维向量W;如果训 0 练样本个数过多，会增大计算复杂度，影响LDA降 -0.05 维速度，综合考虑如上问题，选取120幅典型路况图 -0.10 0. 0.1 0.2 0.3 像作为训练样本，这些路况图像为同一地点、不同时 段、不同路况的样本，并标定每幅样本的路况，即已 图5K-近邻算法示意 知样本分类信息为：畅通样本40幅，缓行样本40 Fig.5 K-NN algorithm 幅，拥堵样本40幅.将每幅样本灰度直方图的40个 本文选取与训练样本不同的120幅标定路况样 采样点作为40维向量，进行LDA降维.由已知的样 本作为待分类样本进行测试.其中，畅通样本40幅， 本分类信息为3类，构造列数为2的最佳降维向量 缓行样本40幅，拥堵样本40幅，使用传统K-近邻 W,图4给出了120幅训练样本经LDA降维到2维 算法对路况样本进行分类，比较分类结果与标定结 空间的分布情况， 果，在表1中给出统计情况。 表1K-近邻算法分类结果统计 0.25 Table 1 Results of using K-NN algorithm ·畅遇+缓行△拥堵 0.20 分类结果符合标定幅数不符合标定幅数一致率/% LDA降维空间 0.15 畅通 % 5 85.7 0.10 缓行 37 11 77.1 0.05 拥堵 31 6 83.8 0 + -0.05 3.2对K-近邻(K-NN)算法的改进 -0.10 K-近邻算法中计算了待分类样本与所有训练样 -0.1 0.1 0.20.3 本的欧式距离，事实上仅使用了其中较小的个样 本作为分类依据.为了充分利用训练样本，本文将统 图4训练样本经LDA降维后在二维空间分布 Fig.4 Train-samples in two dimensional space after LDA 计3类别内所有距离和作为分类依据，将当前样本
第4期 史晓鹏，等：灰度直方图与LDA的路况分类 .331· 归入距离和最小的类别.表2给出了相同测试样本 表3用可信度描述图6的分类结果 使用改进K近邻算法的分类结果统计 Table 3 Results of Fig.6 with reliability 对此表2与表1可以看出，由于充分利用了类 标定分类待分类样本与3类样本距离和 分类结果 别内所有训练样本，改进K-近邻算法使分类结果准 结果结果 畅通 缀行 拥堵 可信度/% 确率有所提升. 畅通畅通5.88961.35460 81.3 表2改进K-近邻算法分类结果统计 畅通畅通3.32322.9774 0 52.9 Table 2 Results of using improved K-NN algorithm 畅通缓行3.35393.5472 0 51.4 分类结果符合标定幅数不符合标定幅数 一致率/% 4 结论 畅通 34 3 91.9 实践证明，使用路况图像灰度直方图统计特征， 缓行 5 88.6 结合LDA降维与改进K-近邻的分类器能够良好地 拥堵 37 2 94.8 进行实时路况分类，分类效果与交管局实时发布路 此外，由于路况评价因人而异，本文在使用改进 况信息相当.主要优越性概括如下. K-近邻算法得到的3个距离和的同时，去除距离和 1)无需二次投人与占用道路，有效利用现有监 最大者，计算待分类样本属于另外2类的百分比，作 控摄像头资源。 为当前分类结果的可信度，为孤立的分类结果添加 2)路况图像灰度直方图提取与LDA降维算法 人性化的参考 计算复杂度低、效率高、分类效果良好. 图6显示了3幅标定为畅通的场景，表3依次 3)改变了传统的孤立分类，分类结果人性化 中列举了这3幅场景用可信度描述的分类结果.对 虽然LDA算法对灰度特征向量降维效果良好， 比表3中的第1、2行可以看出，分类结果与标定结 但是由于3种典型路况训练样本的选取因人而异， 果相符合，可信度52.9%表明尽管当前路况分类结 即同一幅路况图像，不同人会给出不同分类结果，因 果为畅通，但畅通和缓行的可信度比例已经接近1： 此在实际应用中，要合理选取标定的训练样本.此 1,这为人们对路况分类结果的理解提供了参考，帮 外，由于路况图像中灰度特性只反应了静止场景特 助理解当前路况的畅通程度；对比表中的第2、3行 征，且这种特征会因光照影响而发生变化；因此，在 可以看出，当可信度较低时，分类结果不能代表当前 今后的研究工作中，应结合前后帧图像考虑动态场 实际路况，实际路况介于畅通和缓行之间.由此可 景，并研究去除光照影响的方法， 见，可信度反映了分类结果与实际路况的相似程度. 参考文献： [1]钟石泉，马寿峰，贺国光。交通诱导系统路网状态描述 方法及仿真研究[J].系统工程学报，2009,24(1)：25 31. ZHONG Shiquan,MA Shoufeng,HE Guoguang.Descrip- tion 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 Logis- tics.Qingdao,China:IEEE Press,2008:2961-2965. [4]SHI Wei,WU Jian,ZHOU Shaolin,et al.Variable message 图6标定为畅通的场景 sign and dynamic regional traffic guidance[J].Intelligent Fig.6 Scenes of tagging unobstructed Transportation System Magazine,2009,1(3):15-21
332· 智能系统学报 第6卷 同王燕清，陈德运，石朝侠.基于单目视觉的非结构化道 inative common vectors for face recognition [J].IEEE 路检测与跟踪[J].哈尔滨工程大学学报，2011,32 Transactions on Analysis and Machine Intelligence,2005, ③)334-339. 27(1)）:4-13. WANG Yanging,CHEN Deyun,SHI Chaoxia.Unstruc- [13]]WANG Jigang,NESKOVIC P,COOPER L N.Neighbor- ured road detection and tracking based on monocular vision hood size selection in the K-nearest-neighbor rule using [I.Journal of Harbin Engineering University,2011,32 statistical confidence[J].Pattern Recognition,2006,39 ③）：334-339. 3):417-423 阿]耿凯，姚丹亚，张毅.一种基于灰度直方图的交通检测 作者简介： 系统[1.计算机工程与应用，2006,4：：222-225. 史晓鹏，男，1987年生，硕士研究生， GENG Kai,YAO Danya,ZHANG Yi.A grey-histogram 主要研究方向为图像处理与模式识别 based traffc detection system[J].Computer Engineering and Applications,2006,4::222-225. [7]边肇祺，张学工.模式识别[M.2版，北京：清华大学 出版社，1999：：140-142. [8李晓辉，梨湘，郭桂蓉.基于LDA算法的一维距离像特 征提取[].国防科技大学学报，2005,27(6)：7公-76 何为，男，1953年生，硕士，高级工程 LI Xiaohui,LI Xiang GCUO Guirong Feature extraction of 师，IEEE会员，中国人工智能学会理事 HRRP based on LDA algorithm[J].Journal of National u- 中国人工智能学会智能产品与产业工作 niversity 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. 或参加国家科技攻关、省部级、横向等各类科研项目30余项，获 [10]BRESSAN M,VITRIA J.Nonparametric discriminant a- 国家发明专利3项，发表学术论文30余篇 nalysis and nearest neighbor classification [J].Pattern Recognition Letters,2003.24(15)):2743-2749. 韩力群女，1953年生，教授，中国人 [11]LI Zhifeng,LIN Dahua,TANG Xiaoou.Nonparametric 工智能学会副理事长，主要研究方向为事 discriminant analysis for face recognition[J].IEEE Trans- 智能信息处理与图像工程领域研究，主持 actions on Pattern Analysis and Machine Intelligence, 各类科研课题30余项，出版著作10部：获 2009,31(4)1:755-761. 国家发明专利3项，北京发明创新大赛银 [12]CEVIKALPH,NEAMTU M,WILKES M,et al.Discrim- 奖1项，发表学术论文120余篇
332· 智 能 系 统 学 报 系统[J].计算机工程与应用,2006,4: 222-225. GENG Kai,YAO Danya,ZHANG Yi. A grey-histogram based traffc detection system[ J]. Computer Engineering and Applications,2006,4: 222-225. [6] 耿凯,姚丹亚,张毅.一种基于灰度直方图的交通检测 [5] 王燕清,陈德运,石朝侠.基于单目视觉的非结构化道 路检测与跟踪[J].哈尔滨工程大学学报,2011,32 (3) :334-339. 史晓鹏,男,1987年生,硕士研究生 主要研究方向为图像处理与模式识别. WANG Yanging,CHEN Deyun,SHI Chaoxia. Unstrucured road detection and tracking based on monocular vision [J]. Journal of Harbin Engineering University,2011,32 (3) : 334-339. [7] 边肇祺,张学工. 模式识别[M] .2版,北京: 清华大学 出版社,1999: 140-142. [8] 李晓辉,梨湘,郭桂蓉.基于LDA算法的一维距离像特 征提取[J].国防科技大学学报,2005,27(6) :72-76. LI Xiaohui,LI Xiang,GCUO Guirong. Feature extraction of HRRP based on LDA algorithm[J] . Journal of National university of Defense Technology,2005,27(6) :72-76. [9] 何为,男,1953年生,硕士,高级工程 师,IEEE会员,中国人工智能学会理事, 中国人工智能学会智能产品与产业工作 委员会秘书长,中国计量测试学会高级会 员.主要研究方向为非电量检测技术、 计算机测控技术、嵌入式技术应用.主持 或参加国家科技攻关、省部级、横向等各类科研项目30 余项,获 国家发明专利3项,发表学术论文30余篇. 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. [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. [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. [10] BRESSAN M,VITRIA J. Nonparametric discriminant analysis and nearest neighbor classification [J] . Pattern Recognition Letters,2003,24(15) :2743-2749. [12] CEVIKALPH,NEAMTU M,WILKES M,et al. Discrim- 韩力群,女,1953年生,教授,中国人 工智能学会副理事长,主要研究方向为事 智能信息处理与图像工程领域研究,主持 各类科研课题30余项,出版著作10部;获 国家发明专利3项,北京发明创新大赛银 奖1项,发表学术论文120余篇. inative common vectors for face recognition [ J] . IEEE Transactions on Analysis and Machine Intelligence,2005 27(1) : 4-13. 第6卷 作者简介:
