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

史曉鵬，何為，韓力群

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

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

史曉鵬，何為，韓力群

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

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

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

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

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

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

1 灰度直方圖處理

1.1 圖像預(yù)處理

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

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

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

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

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

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

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

2 基于LDA的高維向量降維

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

2.1 LDA算法原理

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

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

式中:c為樣本類別個(gè)數(shù);ni為第i類樣本個(gè)數(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è)計(jì)

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

使用LDA算法時(shí)，訓(xùn)練樣本個(gè)數(shù)選取不應(yīng)過(guò)少.當(dāng)輸入訓(xùn)練樣本個(gè)數(shù)小于樣本維數(shù)時(shí)，會(huì)使類內(nèi)離散度Sw非奇異，而無(wú)法構(gòu)造降維向量W;如果訓(xùn)練樣本個(gè)數(shù)過(guò)多，會(huì)增大計(jì)算復(fù)雜度，影響LDA降維速度.綜合考慮如上問(wèn)題，選取120幅典型路況圖像作為訓(xùn)練樣本，這些路況圖像為同一地點(diǎn)、不同時(shí)段、不同路況的樣本，并標(biāo)定每幅樣本的路況，即已知樣本分類信息為:暢通樣本40幅，緩行樣本40幅，擁堵樣本40幅.將每幅樣本灰度直方圖的40個(gè)采樣點(diǎn)作為40維向量，進(jìn)行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è)計(jì)分類器便可對(duì)未標(biāo)定路況的樣本進(jìn)行分類.

3 基于K－近鄰改進(jìn)算法的分類

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

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

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

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

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

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

3.2 對(duì)K－近鄰(K－NN)算法的改進(jìn)

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

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

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

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

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

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

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

4結(jié)論

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

1)無(wú)需二次投入與占用道路，有效利用現(xiàn)有監(jiān)控?cái)z像頭資源.

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

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

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

［1］鐘石泉，馬壽峰，賀國(guó)光.交通誘導(dǎo)系統(tǒng)路網(wǎng)狀態(tài)描述方法及仿真研究［J］.系統(tǒng)工程學(xué)報(bào)，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ù)檢測(cè)系統(tǒng)設(shè)計(jì)［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］王燕清，陳德運(yùn)，石朝俠.基于單目視覺(jué)的非結(jié)構(gòu)化道路檢測(cè)與跟蹤［J］.哈爾濱工程大學(xué)學(xué)報(bào)，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］耿凱，姚丹亞，張毅.一種基于灰度直方圖的交通檢測(cè)系統(tǒng)［J］. 計(jì)算機(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é)工.模式識(shí)別［M］.2版，北京:清華大學(xué)出版社，1999:140－142.

［8］李曉輝，梨湘，郭桂蓉.基于LDA算法的一維距離像特征提?。跩］. 國(guó)防科技大學(xué)學(xué)報(bào)，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年生，碩士研究生，主要研究方向?yàn)閳D像處理與模式識(shí)別.

何為，男，1953年生，碩士，高級(jí)工程師，IEEE會(huì)員，中國(guó)人工智能學(xué)會(huì)理事，中國(guó)人工智能學(xué)會(huì)智能產(chǎn)品與產(chǎn)業(yè)工作委員會(huì)秘書(shū)長(zhǎng)，中國(guó)計(jì)量測(cè)試學(xué)會(huì)高級(jí)會(huì)員.主要研究方向?yàn)榉请娏繖z測(cè)技術(shù)、計(jì)算機(jī)測(cè)控技術(shù)、嵌入式技術(shù)應(yīng)用.主持或參加國(guó)家科技攻關(guān)、火炬計(jì)劃、省部級(jí)、橫向等各類科研項(xiàng)目30余項(xiàng)，獲國(guó)家發(fā)明專利3項(xiàng)，發(fā)表學(xué)術(shù)論文30余篇.

韓力群，女，1953年生，教授，中國(guó)人工智能學(xué)會(huì)副理事長(zhǎng)，主要研究方向?yàn)槭轮悄苄畔⑻幚砼c圖像工程領(lǐng)域研究，主持各類科研課題30余項(xiàng)，出版著作10部;獲國(guó)家發(fā)明專利3項(xiàng)，北京發(fā)明創(chuàng)新大賽銀獎(jiǎng)1項(xiàng)，發(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.