灰度直方圖與LDA的路況分類

史曉鵬，何為，韓力群

(北京工商大學(xué)計算機與信息工程學(xué)院，北京 100048)

灰度直方圖與LDA的路況分類

史曉鵬，何為，韓力群

(北京工商大學(xué)計算機與信息工程學(xué)院，北京 100048)

道路路況實時分類研究，是路況信息誘導(dǎo)系統(tǒng)的基礎(chǔ).通過對大量路況圖像進行研究，提出使用路況圖像中道路區(qū)域統(tǒng)計灰度直方圖作為表征路況信息的特征向量，采用LDA(linear discriminat analysis)算法對高維特征向量進行降維，采用改進的K－近鄰分類器實現(xiàn)對道路路況實時分類，并給出實際分類結(jié)果.實驗結(jié)果表明，采用上述方法進行路況分類，其結(jié)果與交通管理部門給出的結(jié)果一致率達91.7%，對路況實時分類具有較高的實用價值.

路況分類;灰度直方圖;LDA;K－近鄰分類器

交通擁堵問題已經(jīng)在中國各大城市日益凸顯，最好的解決方法已經(jīng)不是無限制地修建或擴建道路緩解交通擁堵，而是要發(fā)展智能交通.作為智能交通的一個領(lǐng)域，路況信息的實時獲取顯得尤為重要.通過圖像處理與模式識別等信息處理技術(shù)手段進行路況信息的實時采集，對當(dāng)前道路擁堵狀況做出真實、準(zhǔn)確地描述，是智能交通系統(tǒng)［1］(ITS)中最基本和最重要的工作.

傳統(tǒng)的檢測方法，如線圈檢測［2］需要占用道路埋入感應(yīng)線圈，這無疑增大了該條道路的交通壓力.視頻檢測［3－4］是現(xiàn)在發(fā)展很快的一項檢測方法，運用圖像分割和目標(biāo)跟蹤識別可以提取道路機動車數(shù)量、速度，作為路況特征參數(shù)對路況進行分類，文獻［2］中使用了基于幀間差分方法更新道路背景模型，統(tǒng)計出現(xiàn)頻率最大的灰度值，得到初始背景數(shù)據(jù).該方法在幀圖像較大時，計算量大，實時性不夠好.

通過對大量路況圖像的研究，發(fā)現(xiàn)路況灰度圖像中的道路區(qū)域是一近似灰度平坦區(qū)，對于暢通、緩行、擁堵3種典型路況，由于道路區(qū)域被車輛遮擋的原因，使得該區(qū)域灰度直方圖發(fā)生明顯變化.基于該種特性，提出采用路況圖像的灰度直方圖作為特征，使用LDA算法對直方圖采樣點進行降維，并結(jié)合改進K－近鄰算法對路況進行分類.實踐證明，由于直方圖特征獲取的快速性以及LDA算法降維減少了高維向量計算，該方法對于實時路況分類是行之有效的.

1 灰度直方圖處理

1.1 圖像預(yù)處理

路況圖像中道路區(qū)域［5－7］的提取是必要的.實際場景中的路況圖像，由于采集的地點不同，造成圖像灰度分布極其不均，但是同一地點中道路區(qū)域的灰度分布會呈現(xiàn)出一定規(guī)律，因此首先要分割出路況圖像中的道路區(qū)域.方便起見，采用手動分割的方法確定原始圖像(見圖1(a))中的道路區(qū)域，制作道路區(qū)域提取掩模(見圖1(b))，以提取圖像中的道路部分(見圖1(c)).

圖1 路況圖像中的道路區(qū)域分割Fig.1 Segmentation of a road image

1.2 直方圖重采樣與均值濾波

路況圖像完成道路區(qū)域的提取后，得到只含有道路與車輛的圖像，統(tǒng)計該區(qū)域的灰度直方圖，如圖2(a)所示.在大量統(tǒng)計中發(fā)現(xiàn)所有道路區(qū)域灰度直方圖的右端幾乎為0，因此，在0～255灰度級內(nèi)保留1～200的灰度級(如圖2(b))，形成一個200維的特征向量.

圖像采集過程中，即使使用同一監(jiān)控探頭，也會發(fā)生相鄰兩幀圖像灰度突變的情況，這種突變來自于探頭自身噪聲，因此需要對路況圖像進行濾波.本文將1～200灰度級內(nèi)的統(tǒng)計量進行重采樣與均值濾波一體化處理:將相鄰5個灰度級的統(tǒng)計量取平均值，在保留圖像灰度特性的同時，平滑灰度突變干擾，降低直方圖特征向量維度.經(jīng)重采樣與均值濾波后的直方圖如圖2(c)所示.

圖2(c)顯示了經(jīng)重采樣與濾波后的直方圖保留了原直方圖(圖2a)中的雙峰特性.因此，本文將這40個直方圖平滑采樣點，作為描述一幅路況圖像的高維向量樣本.

圖2 道路區(qū)域直方圖處理Fig.2 Histogram processing of road region image

2 基于LDA的高維向量降維

處理后的灰度直方圖反映了路況圖像的車流量特征，但作為特征向量其分度偏高，不利于了解特征空間樣本的拓撲結(jié)構(gòu).線性判別分析［8］(linear discriminant analysis，LDA)是一種用于分類的有效特征降維方法，其核心思想是通過已知的樣本分類信息，構(gòu)造使判別矢量集達到極大值的最佳降維向量，將輸入的高維向量投影到低維空間以實現(xiàn)數(shù)據(jù)降維，并使降維后的樣本達到最大類間離散度和最小類內(nèi)離散度，具有最佳可分離性，從而幫助樣本在低維空間實現(xiàn)最優(yōu)分類［9－13］.

2.1 LDA算法原理

通過已知的樣本分類信息構(gòu)建輸入樣本的類內(nèi)離散度:

式中:x為D維空間輸入樣本;mi為第i類平均樣本;與類間離散度:

式中:c為樣本類別個數(shù);ni為第i類樣本個數(shù);m為全部樣本平均樣本.

式(1)表征同一類別內(nèi)樣本的分散程度，式(2)表征不同類別間平均樣本的分散程度，然后構(gòu)造最佳降維向量W，并將判別矢量集定義為

圖3 二維樣本LDA降維示意Fig.3 Using LDA in two dimensional space

2.2 LDA應(yīng)用設(shè)計

本文中，將路況圖像的40維向量看作高維向量，使用LDA算法對該向量進行降維.由于已知路況類別為3類，降維后，該向量被降到二維空間.在降維后的二維空間(圖4)中，可以看到數(shù)據(jù)分布具有最佳可分離性.

使用LDA算法時，訓(xùn)練樣本個數(shù)選取不應(yīng)過少.當(dāng)輸入訓(xùn)練樣本個數(shù)小于樣本維數(shù)時，會使類內(nèi)離散度Sw非奇異，而無法構(gòu)造降維向量W;如果訓(xùn)練樣本個數(shù)過多，會增大計算復(fù)雜度，影響LDA降維速度.綜合考慮如上問題，選取120幅典型路況圖像作為訓(xùn)練樣本，這些路況圖像為同一地點、不同時段、不同路況的樣本，并標(biāo)定每幅樣本的路況，即已知樣本分類信息為:暢通樣本40幅，緩行樣本40幅，擁堵樣本40幅.將每幅樣本灰度直方圖的40個采樣點作為40維向量，進行LDA降維.由已知的樣本分類信息為3類，構(gòu)造列數(shù)為2的最佳降維向量W，圖4給出了120幅訓(xùn)練樣本經(jīng)LDA降維到2維空間的分布情況.

圖4 訓(xùn)練樣本經(jīng)LDA降維后在二維空間分布Fig.4 Train-samples in two dimensional space after LDA

圖4表明，輸入的120幅40維向量訓(xùn)練樣本經(jīng)LDA降維到二維空間后，分類特征明顯.因此，在二維空間設(shè)計分類器便可對未標(biāo)定路況的樣本進行分類.

3 基于K－近鄰改進算法的分類

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

K－近鄰(K－nearest neighborhood)算法是分類未知數(shù)據(jù)最直接的方法，其基本思想是:找到和待分類樣本最相似的k個已分類樣本，根據(jù)這k個樣本所屬類別判斷待分類樣本所屬類別，如圖5所示.對于一個待分類樣本，計算其與訓(xùn)練樣本中每一樣本的歐式距離(見式(4))，找出與待分類樣本最近的k個近鄰，依據(jù)k個近鄰在每類中所占比重，將待分類樣本歸入所占比重最大的類別.

式中:x為待分類樣本，μi為訓(xùn)練樣本中第i個樣本.

圖5 K-近鄰算法示意Fig.5 K-NN algorithm

本文選取與訓(xùn)練樣本不同的120幅標(biāo)定路況樣本作為待分類樣本進行測試.其中，暢通樣本40幅，緩行樣本40幅，擁堵樣本40幅，使用傳統(tǒng)K－近鄰算法對路況樣本進行分類，比較分類結(jié)果與標(biāo)定結(jié)果，在表1中給出統(tǒng)計情況.

表1 K－近鄰算法分類結(jié)果統(tǒng)計Table 1 Results of using K-NN algorithm

3.2 對K－近鄰(K－NN)算法的改進

K－近鄰算法中計算了待分類樣本與所有訓(xùn)練樣本的歐式距離，事實上僅使用了其中較小的k個樣本作為分類依據(jù).為了充分利用訓(xùn)練樣本，本文將統(tǒng)計3類別內(nèi)所有距離和作為分類依據(jù)，將當(dāng)前樣本歸入距離和最小的類別.表2給出了相同測試樣本使用改進K－近鄰算法的分類結(jié)果統(tǒng)計.

對比表2與表1可以看出，由于充分利用了類別內(nèi)所有訓(xùn)練樣本，改進K－近鄰算法使分類結(jié)果準(zhǔn)確率有所提升.

表2 改進K－近鄰算法分類結(jié)果統(tǒng)計Table 2 Results of using improved K-NN algorithm

此外，由于路況評價因人而異，本文在使用改進K－近鄰算法得到的3個距離和的同時，去除距離和最大者，計算待分類樣本屬于另外2類的百分比，作為當(dāng)前分類結(jié)果的可信度，為孤立的分類結(jié)果添加人性化的參考.

圖6顯示了3幅標(biāo)定為暢通的場景，表3依次中列舉了這3幅場景用可信度描述的分類結(jié)果.對比表3中的第1、2行可以看出，分類結(jié)果與標(biāo)定結(jié)果相符合，可信度52.9%表明盡管當(dāng)前路況分類結(jié)果為暢通，但暢通和緩行的可信度比例已經(jīng)接近1:1，這為人們對路況分類結(jié)果的理解提供了參考，幫助理解當(dāng)前路況的暢通程度;對比表中的第2、3行可以看出，當(dāng)可信度較低時，分類結(jié)果不能代表當(dāng)前實際路況，實際路況介于暢通和緩行之間.由此可見，可信度反映了分類結(jié)果與實際路況的相似程度.

圖6 標(biāo)定為暢通的場景Fig.6 Scenes of tagging unobstructed

表3 用可信度描述圖6的分類結(jié)果Table 3 Results of Fig.6 with reliability

4結(jié)論

實踐證明，使用路況圖像灰度直方圖統(tǒng)計特征，結(jié)合LDA降維與改進K－近鄰的分類器能夠良好地進行實時路況分類，分類效果與交管局實時發(fā)布路況信息相當(dāng).主要優(yōu)越性概括如下.

1)無需二次投入與占用道路，有效利用現(xiàn)有監(jiān)控攝像頭資源.

2)路況圖像灰度直方圖提取與LDA降維算法計算復(fù)雜度低、效率高、分類效果良好.

3)改變了傳統(tǒng)的孤立分類，分類結(jié)果人性化.

雖然LDA算法對灰度特征向量降維效果良好，但是由于3種典型路況訓(xùn)練樣本的選取因人而異，即同一幅路況圖像，不同人會給出不同分類結(jié)果，因此在實際應(yīng)用中，要合理選取標(biāo)定的訓(xùn)練樣本.此外，由于路況圖像中灰度特性只反應(yīng)了靜止場景特征，且這種特征會因光照影響而發(fā)生變化;因此，在今后的研究工作中，應(yīng)結(jié)合前后幀圖像考慮動態(tài)場景，并研究去除光照影響的方法.

［1］鐘石泉，馬壽峰，賀國光.交通誘導(dǎo)系統(tǒng)路網(wǎng)狀態(tài)描述方法及仿真研究［J］.系統(tǒng)工程學(xué)報，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］葉青.道路交通參數(shù)檢測系統(tǒng)設(shè)計［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］王燕清，陳德運，石朝俠.基于單目視覺的非結(jié)構(gòu)化道路檢測與跟蹤［J］.哈爾濱工程大學(xué)學(xué)報，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］耿凱，姚丹亞，張毅.一種基于灰度直方圖的交通檢測系統(tǒng)［J］. 計算機工程與應(yīng)用，2006，4:222－225.

GENG Kai，YAO Danya，ZHANG Yi.A grey－h(huán)istogram based traffic detection system［J］.Computer Engineering and Applications，2006，4:222－225.

［7］邊肇祺，張學(xué)工.模式識別［M］.2版，北京:清華大學(xué)出版社，1999:140－142.

［8］李曉輝，梨湘，郭桂蓉.基于LDA算法的一維距離像特征提取［J］. 國防科技大學(xué)學(xué)報，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會員，中國人工智能學(xué)會理事，中國人工智能學(xué)會智能產(chǎn)品與產(chǎn)業(yè)工作委員會秘書長，中國計量測試學(xué)會高級會員.主要研究方向為非電量檢測技術(shù)、計算機測控技術(shù)、嵌入式技術(shù)應(yīng)用.主持或參加國家科技攻關(guān)、火炬計劃、省部級、橫向等各類科研項目30余項，獲國家發(fā)明專利3項，發(fā)表學(xué)術(shù)論文30余篇.

韓力群，女，1953年生，教授，中國人工智能學(xué)會副理事長，主要研究方向為事智能信息處理與圖像工程領(lǐng)域研究，主持各類科研課題30余項，出版著作10部;獲國家發(fā)明專利3項，北京發(fā)明創(chuàng)新大賽銀獎1項，發(fā)表學(xué)術(shù)論文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－h(huán)istogram 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－h(huán)istogram;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.