李斌　王凱　徐英杰

摘要摘要：為滿足車輛檢測(cè)實(shí)時(shí)性和準(zhǔn)確性需求，將基于C4.5的決策樹(shù)算法作為AdaBoost算法的弱分類器，產(chǎn)生一種速度快、識(shí)別率高的強(qiáng)分類器，稱之為AdaBoostDT算法。算法訓(xùn)練多個(gè)決策樹(shù)并將之作為弱分類器，之后通過(guò)改進(jìn)級(jí)聯(lián)架構(gòu)的AdaBoost算法將若干弱分類器組合成一個(gè)強(qiáng)分類器。該算法特點(diǎn)在于：相對(duì)于廣泛使用的以SVM作為弱分類器的算法，其以決策樹(shù)作為分類器，速度提高了29%；通過(guò)在AdaBoost算法進(jìn)行強(qiáng)分類器的形成階段加入再判決函數(shù)，準(zhǔn)確率提高了14.1%。

關(guān)鍵詞關(guān)鍵詞：AdaBoost算法；決策樹(shù)；車輛檢測(cè)

DOIDOI：10.11907/rjdk.162868

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）005012903

0引言

隨著我國(guó)城鎮(zhèn)化建設(shè)的飛快發(fā)展及汽車保有量的增加，土地資源越發(fā)緊張，停車難的問(wèn)題越發(fā)嚴(yán)重，由此產(chǎn)生的交通擁堵事故層出不窮。停車引導(dǎo)自動(dòng)化成為一項(xiàng)重要技術(shù)，其解決的主要問(wèn)題是車輛識(shí)別的速度和準(zhǔn)確率。目前存在的識(shí)別方案主要有以下幾種：紅外感應(yīng)、無(wú)線傳感器、圖像識(shí)別。在這些方案中，第一種還需要解決信號(hào)干擾、信號(hào)復(fù)用等問(wèn)題，第二種方法不僅建設(shè)的成本高，而且還需要解決信道可靠傳輸?shù)膯?wèn)題，結(jié)構(gòu)比較復(fù)雜。由此，基于圖像識(shí)別的車輛檢測(cè)與停車位識(shí)別技術(shù)受到人們的廣泛關(guān)注[1]，這其中最受關(guān)注的當(dāng)屬分類器技術(shù)。

分類器技術(shù)不僅能夠用于目標(biāo)檢測(cè)領(lǐng)域，在其它很多領(lǐng)域也發(fā)揮了重要作用，例如在語(yǔ)音信號(hào)處理、數(shù)據(jù)挖掘、信號(hào)聚類、圖像檢索等。目前存在很多能實(shí)現(xiàn)分類功能的算法，其中應(yīng)用比較廣泛的為AdaBoost算法[2]，該算法先對(duì)車輛進(jìn)行特征提取，在此基礎(chǔ)上采用支持向量機(jī)（Support Vector Machhine，SVM）[3]的方法進(jìn)行車輛識(shí)別，取得了一定效果?；赟VM的檢測(cè)方法雖然具有很強(qiáng)的分類能力，但是選取特征的過(guò)程復(fù)雜，且易陷入局部極小。此外，基于SVM的檢測(cè)方法一般都需要比較大的計(jì)算量進(jìn)行特征提取，這在一定程度上影響了算法的性能，很多情況下不能滿足車輛識(shí)別的效率要求。

本文提出的AdaBoostDT算法通過(guò)采用決策樹(shù)[45]作為AdaBoost的弱分類器，提高了車輛識(shí)別速度，并通過(guò)改進(jìn)AdaBoost算法的級(jí)聯(lián)架構(gòu)，彌補(bǔ)決策樹(shù)作為分類器所導(dǎo)致的準(zhǔn)確率下降，從而使集成后的強(qiáng)分類器與基于SVM的分類器相比，在準(zhǔn)確度略微下降的情況下，速度能有很大程度的提升，更好地滿足車輛檢測(cè)系統(tǒng)對(duì)于實(shí)時(shí)性的要求。

1基本原理

1.1AdaBoost算法

AdaBoost算法是一種機(jī)器學(xué)習(xí)算法，它能將弱分類器提升為強(qiáng)分類器，其中分類器的強(qiáng)弱是指識(shí)別率高低。算法是通過(guò)調(diào)整訓(xùn)練集上樣本的權(quán)重來(lái)實(shí)現(xiàn)其功能。開(kāi)始時(shí)每個(gè)樣本的權(quán)重相等且總和為1，隨后AdaBoost算法對(duì)訓(xùn)練集進(jìn)行訓(xùn)練，產(chǎn)生第一個(gè)弱分類器，并計(jì)算錯(cuò)誤率。根據(jù)錯(cuò)誤率調(diào)整權(quán)重，提升錯(cuò)判樣本的權(quán)重，降低辨別正確的樣本的權(quán)重，這樣在之后的訓(xùn)練中就會(huì)更多地考慮這些被錯(cuò)判的樣本。在調(diào)整后的樣本權(quán)重基礎(chǔ)上，再進(jìn)行訓(xùn)練產(chǎn)生新的分類器，次迭代后就產(chǎn)生了N個(gè)檢測(cè)能力一般的弱分類器。AdaBoost再將這些弱分類器按照一定的權(quán)重進(jìn)行一系列的組合，產(chǎn)生強(qiáng)分類器。理論證明，弱分類器的數(shù)量越多，各個(gè)弱分類器之間的差異越大，強(qiáng)分類器的效果越好。

1.2決策樹(shù)

決策樹(shù)算法是一種由J Ross Quinlan等提出的逼近離散函數(shù)值的算法，于20世紀(jì)60年代出現(xiàn)。該算法最初的用處是在已知各種情形出現(xiàn)概率的情況下，通過(guò)決策分支來(lái)獲取期望值及其對(duì)應(yīng)的概率，評(píng)價(jià)項(xiàng)目風(fēng)險(xiǎn)，判斷可行性。由于形狀像一顆擁有很多分枝的樹(shù)，所以稱為決策樹(shù)。

決策樹(shù)算法是典型的分類算法，該算法先處理數(shù)據(jù)，產(chǎn)生一定的規(guī)則和決策樹(shù)，然后再運(yùn)用決策分支對(duì)數(shù)據(jù)進(jìn)行分析，本質(zhì)是按照一定的規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類。典型的決策樹(shù)算法有ID3[6]、C4.5[7]、CART等。本文提出的AdaBoostDT算法采用基于C4.5算法的決策樹(shù)作為弱分類器。C4.5算法作為ID3算法的改進(jìn)算法，彌補(bǔ)了ID3算法的兩個(gè)不足之處[8]：一是ID3算法采用信息熵作為選擇樣本屬性的標(biāo)準(zhǔn)，很多時(shí)候，通過(guò)該標(biāo)準(zhǔn)選擇的屬性并不具有代表性，C4.5算法采用信息增益率作為樣本屬性的選擇標(biāo)準(zhǔn)，彌補(bǔ)了這個(gè)缺點(diǎn)；二是ID3算法只對(duì)屬性離散的數(shù)據(jù)集有處理能力，而不能處理屬性連續(xù)的數(shù)據(jù)集，而C4.5算法則對(duì)屬性離散和屬性連續(xù)的數(shù)據(jù)集都有較好的處理能力。

2AdaBoostDT算法

2.1弱分類器最佳分割闕值方法改進(jìn)

C4.5算法作為ID3算法的改進(jìn)算法，彌補(bǔ)了ID3算法的兩個(gè)缺點(diǎn)，但仍存在一些不足：C4.5算法要隨機(jī)地在屬性的不同取值中插入一些點(diǎn)，計(jì)算這些點(diǎn)的信息增益率，選擇值最大的屬性作為最佳分裂屬性。當(dāng)遇到?jīng)Q策樹(shù)節(jié)點(diǎn)數(shù)量較多的情況時(shí)，將影響到?jīng)Q策樹(shù)的效率。提高決策樹(shù)識(shí)別速度的關(guān)鍵之處在于快速地找到最佳分割闕值。

根據(jù)邊界點(diǎn)原理[9]：連續(xù)數(shù)據(jù)集的最佳分割點(diǎn)總在邊界點(diǎn)處。本文按照遞減的順序?qū)⑦B續(xù)型屬性排列，再?gòu)南噜彽膬蓚€(gè)邊界點(diǎn)附近選擇4個(gè)屬性作為測(cè)試屬性，按遞減的順序依次為：a1、a2、a3、a4。其中a1為類1中屬性的最大值，a2為類1中屬性的最小值，a3為類2中屬性的最大值，a4為類2中屬性的最小值。計(jì)算每個(gè)點(diǎn)的信息增益率，選擇最大的值作為最佳分割闕值，這樣只需計(jì)算4個(gè)屬性值，相對(duì)于傳統(tǒng)需遍歷所有屬性，計(jì)算相應(yīng)的值，能極大提升決策樹(shù)的效率。當(dāng)屬性只有兩個(gè)類別時(shí)，本文算法效率最高；每個(gè)屬性都只有一個(gè)類別時(shí)，本文提出的改進(jìn)算法與傳統(tǒng)算法效率相同，效率最低。

2.2改進(jìn)的分類器級(jí)聯(lián)架構(gòu)

傳統(tǒng)的AdaBoost級(jí)聯(lián)架構(gòu)就是一定數(shù)量的弱分類器簡(jiǎn)單串聯(lián)[10]。由于每一級(jí)的弱分類器都有一定的誤判概率，使得整個(gè)分類器的識(shí)別率較低。例如，6個(gè)正確率為90%的分類器采用傳統(tǒng)方式級(jí)聯(lián)之后準(zhǔn)確率為53.1%，6個(gè)正確率為96%的分類器采用傳統(tǒng)的級(jí)聯(lián)方式之后準(zhǔn)確率也僅為78.3%，這顯然不能滿足車輛識(shí)別的實(shí)際需要。對(duì)此，本文通過(guò)增加再判決函數(shù)改進(jìn)了AdaBoost算法的級(jí)聯(lián)架構(gòu)以滿足算法準(zhǔn)確率的需求，改進(jìn)算法的結(jié)構(gòu)如圖1所示。

在傳統(tǒng)的級(jí)聯(lián)判決中，每個(gè)分類器只考慮當(dāng)前級(jí)別分類器對(duì)樣本的判決結(jié)果，而沒(méi)有考慮到前面分類器的判決結(jié)果，實(shí)際情況是分類器可以將前面分類器的結(jié)果作為參照用來(lái)修正當(dāng)前的分類器，使準(zhǔn)確率得到提高。本文對(duì)AdaBoost算法的每一級(jí)分類器后面增加一個(gè)再判決函數(shù)來(lái)提高準(zhǔn)確率，再判決函數(shù)對(duì)被當(dāng)前分類器判決為假的樣本進(jìn)行再判決。如果再判決函數(shù)判決結(jié)果為假，那么認(rèn)為樣本不是車輛，否則將樣本送到后一級(jí)分類器中。

第t級(jí)的再判決函數(shù)為：

Ht（xi）=γht（xi）+（1-γ）·（1/2）m

其中，γ代表當(dāng)前分類器的權(quán)重系數(shù)，0<γ<1，ht（xi）=∑Dti=1f，表示第i級(jí)分類器判決對(duì)樣本xi判決的隸屬度；Dt為第t級(jí)中分類器數(shù)量；f表示在第t級(jí)分類器中用第i個(gè)弱分類器對(duì)樣本xi進(jìn)行判決得到的結(jié)果；m為樣本Xi被前面t-1級(jí)分類器判斷為假的次數(shù)。

第t級(jí)的再判決為：

Tt（xi）=1，（xt）>bound0，other

其中，bound是第t級(jí)再判決器的閾值，大于該值認(rèn)為是真，小于該值則認(rèn)為是假。

再判決函數(shù)考慮了前面分類器的判決結(jié)果，它的作用相當(dāng)于給后面的分類器設(shè)置了一個(gè)闕值，該闕值可根據(jù)前面各級(jí)分類器對(duì)樣本的判斷結(jié)果而作相應(yīng)調(diào)整：當(dāng)樣本被前面多個(gè)分類器錯(cuò)判時(shí)，闕值變大，反之變小。這樣，對(duì)于正樣本而言，前期被拒絕次數(shù)少，闕值變小，在后面能盡早地通過(guò)判決。對(duì)于負(fù)樣本，前期被拒絕次數(shù)多，闕值很快就會(huì)變得很大，會(huì)盡早地被淘汰。

3實(shí)驗(yàn)

3.1實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)平臺(tái)包括硬件配置和軟件環(huán)境兩部分，硬件配置為配置intel Corei7-3612，16GB內(nèi)存的PC機(jī)，軟件環(huán)境采用了基于Win 10操作系統(tǒng)的VisualStudio2013搭載OpenCV2.4.8視覺(jué)庫(kù)。

下文將對(duì)OpenCV進(jìn)行簡(jiǎn)單介紹，OpenCV是由Intel公司于1999年開(kāi)發(fā)的一個(gè)開(kāi)源計(jì)算機(jī)視覺(jué)庫(kù)，全稱為Open Sorece Computer Vision Library。OpenCV集成了部分C++類和函數(shù)，為使用者提供了與圖像處理相關(guān)的許多通用算法。

3.2測(cè)試數(shù)據(jù)

本文創(chuàng)建了用于車輛識(shí)別的圖像庫(kù)和視頻庫(kù)，以全面檢驗(yàn)決策樹(shù)分類器的性能。

本文建立了針對(duì)車輛前后俯視角度的圖像庫(kù)，該圖像庫(kù)大多數(shù)樣本為從網(wǎng)上搜集來(lái)的照片，從中挑選了100幅各種背景和各種光線強(qiáng)度下的圖片，通過(guò)剪輯使照片的尺寸都在720×480，每幅圖片都包含1～5輛車，總共含有368輛車，圖2為圖像庫(kù)的幾個(gè)示例。

為了測(cè)試算法的實(shí)時(shí)性，還建立了用于測(cè)試的視頻庫(kù)，視頻庫(kù)的視頻是在幾個(gè)不同的停車場(chǎng)進(jìn)行錄制，再通過(guò)后期整理得到，共有6段時(shí)間長(zhǎng)短不同的視頻，視頻分辨率為720×480，幀數(shù)為25fps。

3.3測(cè)試圖像庫(kù)實(shí)驗(yàn)

依次用基于決策樹(shù)的AdaBoost算法、基于SVM的AdaBoost算法和本文提出的改進(jìn)的基于決策樹(shù)的AdaBoostDT算法對(duì)圖像庫(kù)進(jìn)行識(shí)別測(cè)試。3種算法正確識(shí)別車輛數(shù)目、車輛檢測(cè)率、誤檢車輛數(shù)目、誤檢率及對(duì)300張照片進(jìn)行檢測(cè)花費(fèi)的總時(shí)間如表1所示。

3.4測(cè)試視頻庫(kù)實(shí)驗(yàn)

為了檢驗(yàn)分類器是否滿足系統(tǒng)對(duì)實(shí)時(shí)性的要求，運(yùn)用視頻庫(kù)對(duì)上述3種算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)時(shí)，每隔50ms從視頻中取一幀圖像。3種算法對(duì)每一段視頻中車輛的正確識(shí)別率、誤檢率和每一幀圖像的平均處理時(shí)間如表2所示。

圖3為圖像庫(kù)的實(shí)驗(yàn)結(jié)果示例。

3.5實(shí)驗(yàn)結(jié)果分析

通過(guò)運(yùn)用圖像庫(kù)和視頻庫(kù)進(jìn)行實(shí)驗(yàn)，可以看出：

（1）普通的基于決策樹(shù)的識(shí)別算法，在車輛的正確識(shí)別率和誤檢率兩個(gè)方面與其它兩種算法相差很多，其不到80%的正確識(shí)別率明顯不能滿足對(duì)車輛識(shí)別準(zhǔn)確性的要求。

（2）基于SVM的分類器算法，在檢測(cè)所花的時(shí)間上遠(yuǎn)遠(yuǎn)超過(guò)另外兩種算法，可以用在靜態(tài)的車輛檢測(cè)方向，但是對(duì)于停車場(chǎng)這種對(duì)實(shí)時(shí)性要求較高的系統(tǒng)不太適合。

（3）本文提出的AdaBoostDT算法雖然在車輛的正確識(shí)別率上比基于SVM的算法低3個(gè)百分點(diǎn)，但是其高于91%的識(shí)別率也足以滿足車輛檢測(cè)的需要。此外，本文提出的算法在辨別速度上比基于SVM的算法提高了30%，更能滿足及時(shí)性的要求。

（4）用于測(cè)試的照片包括各種光線條件下的、各種背景的照片，另外照片上的車輛也是各種各樣，有普通轎車、SUV甚至卡車。本文算法在復(fù)雜的情況下依然能保持較高的檢測(cè)率，說(shuō)明本文算法的適用范圍很廣。

4結(jié)語(yǔ)

本文提出的AdaBoostDT算法，與傳統(tǒng)的基于SVM的AdaBoost算法不同，采用基于C4.5的決策樹(shù)算法作為弱分類器，顯著提高了AdaBoost算法的效率，得到結(jié)果的速度更快；再通過(guò)對(duì)AdaBoost算法級(jí)聯(lián)架構(gòu)進(jìn)行改良，彌補(bǔ)決策樹(shù)算法相較于SVM算法作為弱分類器導(dǎo)致的準(zhǔn)確率下降問(wèn)題。實(shí)驗(yàn)證明，本文提出的AdaBoostDT算法具有快速的識(shí)別速度和較高的準(zhǔn)確率，更能滿足車輛識(shí)別系統(tǒng)實(shí)時(shí)識(shí)別的需要。

參考文獻(xiàn)參考文獻(xiàn)：

[1]ZHANG J P，WANG F Y，WANG K，et al.Datadriven intelligent transportation systems：asurver[J].IEEE Trans IntellTransp Syst，2011，12（4）：16241639.

[2]FREUND Y，SCHAPIRE R.Adecisiontheoretic generalization of online learning and an application to boosting[J].Journal of Computer and System Sciences，1997，55（1）：119139.

[3]ANOSPIDE J，SALGADOL.Regiondependent vehicle classification using PCA features[C].IEEE International Conference on Image Processing.Washiington DC：IEEE Computer Society，2012：453456.

[4]LI FACHAO，LI PING，JIN CHENXIA.Summary of decision tree algorithm and its application in attribute reduction[R].Shijiazhuang：Hebei Univ.of Seism and Technology，2009：313317.

[5]謝金梅，王艷妮.決策樹(shù)算法綜述[J].軟件導(dǎo)刊，2008，7（11）：8385.

[6]CHEN JIN，LUO DELIN，MU FENXIANG.An improved ID3 decision tree algorithm[C].Chengdu：4th International Conference on IEEE Computer Science and Education，2009：127130.

[7]QUINLAN J R.C4.5：programs for machine learning[M].San Mateo：morgan Kaufmann Publishbers Inc，1993：1742.

[8]YANG XUEBING，ZHANGJUN.Decision tree algorithm and its key techniques[J].Computer Technology and Developmeng，2007，17（1）：4446.

[9]FAYYAD U M，INANIK B.On the handing of continuesvalue attributers in decision tree generation[J].Machine Learning，1992，8（1）：87102.

[10]VDLA P，JONESM.Robust realtiem object detection[C].Second Internationl Workshop on Statistical and Computationsl Theories of Vision：Modeling，Learning，Computing and Sampling，2007.

責(zé)任編輯（責(zé)任編輯：孫娟）