基于CKPCA-HOG和支持向量機的運動目標分類算法

聞帆，屈楨深，閆紀紅

(1.哈爾濱工業大學 機電工程學院，黑龍江 哈爾濱 150001;2.哈爾濱工業大學 空間控制與慣性技術研究中心，黑龍江哈爾濱150001)

智能化的視頻監控(intelligent video surveillance，IVS)是將圖像與事件建立一種映射關系，借助計算機強大的數據處理能力對監控視頻的內容進行描述、理解和分析，并能根據分析的結果對視頻監控系統進行控制，從而使視頻監控系統具有較高層次的智能化水平.其中，運動目標的自動分類是其中不可或缺的一個重要環節.在交通領域中的智能交通控制管理系統中，通過提取車輛目標的特征可計算出交通流參數，依此來設定信號配時［1］.在交叉口碰撞檢測中，正確地識別出運動目標并根據其運行軌跡，可以預測是否有碰撞發生［2］.除此之外，目標分類算法還可以實現智能車輛對周邊環境中感興趣目標的檢測、分類和存儲等功能［3］.

目前，目標分類算法主要分為兩類:基于樣本或模板的方法和基于形狀特征［4］的方法.相對于前者，基于形狀的方法在描述同類目標或具有相似運動的目標時很難用統一的模型加以表征，因此在對目標進行精細分類時存在明顯的不足.雖然國內外學者提出了諸多分類算法，但是迄今為止，如何對目標進行有效地分類，還是一個尚未得到很好解決的問題.

目前，基于梯度方向直方圖［5］的紋理描述符已用于目標分類.文獻［6］找到一個解決彌補在某些情況下單個分類器不足問題的方法，就如何將特征與分類器進行組合展開了研究.文獻［7］提出了一種基于boosted HOG特征和線性SVM的目標分類算法.在文獻［8］中，利用局部梯度最大方法來估計感興趣區域(ROIs)的位置，然后利用AdaBoost分類器對這些假進行驗證.文獻［9］為了更加快速地檢測行人，將人臉檢測中Boosted Cascade算法用在特征選取上，不僅訓練時間短、檢測速度快，而且檢測精度比較高.從各文獻實驗結果中看出，這些方法在針對行人和車輛目標分類中都取得了很好的效果.

雖然HOG特征能夠得到很高的檢測率，但是高達幾千維的特征向量限制了訓練樣本的數量，同時增加了在分類過程中的計算時間.由于CKPCA在特征降維中的優越性能，本文將高維的 HOG特征用CKPCA降到低維，縮短了分類器的訓練時間并未影響檢測精度.然后利用降維后的特征向量訓練二叉決策樹支持向量機，得到最終的分類器.最后，利用訓練好的分類器對視頻序列出現的新目標進行分類，并對分類結果進行評價.

1 圖像特征描述及CKPCA方法

1.1 圖像特征描述

為了對圖像進行有效地分析和理解，需要將給定的原始圖像用有利于人或機器分析和理解的簡單明確的數值、符號或圖形表示出來，這些數值、符號或圖形稱為圖像的特征.目標分類是對于未知目標的觀測數據，利用一組能夠代表目標的合適特征作為輸入，得到此目標的類別或者屬于不同目標類別的可能性.現階段，對目標特征表達可以歸納為兩方面:全局特征與局部特征.通過檢測圖像的局部特征，形成易于區分、穩定性好的特征向量，把目標分類問題轉化為特征空間中特征向量的聚類問題.由于目標的局部特征易于提取和表示，具有很強的魯棒性，因此在目標分類領域獲得了廣泛的應用.

2005年，Dalall提出了基于HOG特征的算法，并成功應用于行人檢測.梯度方向直方圖描述子(descriptors)的本質思想是圖像內的局部對象的外觀和形狀可以通過梯度強度或邊緣方向的分布加以描述.如圖1所示，這些描述子的應用可以通過將圖像劃分成稱之為細胞(cell)的小的連通區域，對每個單元內的像素計算梯度方向或邊緣方向的直方圖，然后對這些直方圖加以組合構成最終的描述子.為了提高描述子的性能，計算由若干單元組成的塊內所有像素梯度強度值的和，然后利用該值歸一化塊內所有單元，得到歸一化的描述子.

圖1 HOG特征算子Fig.1 HOG operator

1.2 CKPCA方法

對于場景中的運動目標，首先提取能夠有效描述該目標的特征向量.由于獲取的特征向量維數比較高，這樣會影響目標分類的運算速度，因此需要通過數據降維的方法得到一個能夠有效描述目標特征并且數據維數比較小的特征向量.PCA為特征向量由高維降為低維提供了一個很好的解決方法.通過對從現場采集的目標特征向量進行分析后發現，這些特征向量之間往往是線性不可分的，而PCA又不能解決非線性問題，因此采用CKPCA方法實現上述目標.該方法首先通過核函數將輸入非線性空間變換到高維線性空間，然后在高維空間利用主成分分析的方法對特征向量進行數據降維［10］.

設xi∈RP(i=1，2，…，n)為樣本點，RP表示輸入空間，F表示特征空間.非線性變換φ:RP→F實現兩者間的映射，將樣本點xi映射為特征空間的樣本點φ(xi)，其中i=1，2，…，n.

F空間中樣本的協方差矩陣C為

根據Cv=λv計算C的特征值λ和對應的特征向量V∈F{0}.

設C的特征值為0≤λ1≤λ2≤…≤λn，對應的特征向量為v1，v2，…，vn.另外，v1，v2，…，vn可由F空間中的樣本φ(xi)張成.記:

考慮等式

將式(1)、(2)代入式(3)，令

得到

式中:K稱為核矩陣，是n×n矩陣，nλi是K的特征值，α1，α2，…，αn是對應的特征向量.按一定的標準(前m個特征值占總特征值的比例≥90%)，取前m (m＜n)個特征值和對應的標準化后的特征向量α1，α2，…，αm，其中…，m).

對F空間中樣本φ(xj)(j=1，2，…，n)在vr上進行投影:

稱gr(xj)為對應φ的第r個非線性主元分量.將所有的投影值形成一個矢量g(x)=(g1(xj)，g2(xj)，…，gm(xj))作為樣本的特征值.根據Mercer定理，利用核函數K(xi，xj)=(φ(xi)·φ(xj))代替F空間中的內積運算，式(5)可寫為

核函數有很多選擇，常用的核函數如下:

1)多項式核函數:

2)Sigmoid核函數:

3)徑向基核函數:

式中:d、β0、β1和σ需要事先確定，這些參量可以通過K-Means聚類算法來得到.這里采用徑向基核函數，其中σ表示函數的寬度參數，就是距離中心的半徑.這個半徑等于聚類中心向量和屬于該類的樣本之間的距離的平均值.

不同的核函數決定了由原始空間到特征空間的不同映射.對于主元分析算法，數據需要在特征空間中心化.這可以由取代K來實現:

式中:Li，j=1/l.

從上面計算可以看到，核矩陣與樣本點的個數相關，PCA不能解決非線性問題，KPCA雖能解決，但由于樣本點的個數比較大，帶來核矩陣的維數比較大，造成計算復雜度增加.為了解決核矩陣的計算復雜性，選擇疏散的貪婪矩陣近似(sparse greedy matrix approximation，SGA)［11］的方法縮減樣本點個數來達到降低核矩陣的階數.

1.3 CKPCA-HOG計算過程

CKPCA-HOG計算過程主要由兩部分組成:第1部分是特征提取，利用HOG算子獲取目標梯度向量;第2部分是特征數據降維，利用CKPCA將HOG高維數據影射到一個線性子空間，在去掉冗余信息的同時保留了主要的特征，而且不影響分類精度.

令I∈Rm×n表示一個具有寬度為m高度為n的圖像，I(x，y)表示位于(x，y)處像素的灰度值，其中x=1，2，…，m，y=1，2，…，n.下面給出CKPCA-HOG算子的計算流程:

1)計算圖像梯度:首先，圖像I經過一個尺寸為wg標準差為σg的高斯濾波器濾除噪聲.然后，利用1維的中心點導數離散掩模DX和DY沿x和y方向對圖像卷積:

式中:DX=［－1 0 1］，DY=［－1 0 1］T.

根據式(11)和(12)可得到點的梯度幅值|G(x，y)|和方向θ(x，y).

其中，梯度的幅值為

梯度的方向為

為了使CKPCA-HOG對目標的顏色不具有敏感性，根據文獻［5］，將式(14)修改如下:

2)創建cell直方圖:圖像按空間位置均勻的分成sw×sh個相鄰的網格，每個網格稱為“cell”，在cell內按照設定好的方向量化間隔統計梯度方向直方圖，應用梯度的幅值或者梯度幅值的平方或者平方根進行投票.

3)描述符塊:為了解釋照度或對比度的變化，梯度幅值必須局部歸一化.將相鄰的cell(2×2)組成一個大塊(block)，相鄰的block之間相互重疊，意味著每個cell對于最終的描述子的貢獻多于一次.HOG描述子是一個由塊內所有歸一化的cell直方圖組成的向量.

4)塊歸一化:在block內采用二范數(L2)歸一化直方圖消除光照的影響.一個檢測窗口內所有block內的歸一化直方圖組成圖像I最后的特征向量H∈Rnf，nf=ss×sh×sb.

5)計算非線性主元分向量:

①對于給定的數據xk∈Rm(k=1，2，…，N)，利用式(9)計算對應的核矩陣K∈RN×N;

②在特征空間中利用式(10)對數據進行中心化處理.

③解特征方程Nλα=K～α，利用公式αk·αk= 1/λk標準化特征向量αk.

④對正常數據x，通過式(6)計算非線性主元的分向量.

⑤令Γ∈Rnp×nf表示從訓練圖像HOG描述子獲得的前np個主成分，將HOG描述子H投影到由主成分Γ構成的線性子空間:

2 基于二叉決策樹SVM分類器

在交叉口，交通目標主要有行人和車輛，而目標分類的目的是將從視頻圖像序列中檢測出來的目標根據某種或者某些特征的組合將它們分類為行人和車輛，然后在此基礎上再進一步將車輛分為大型車、中型車和小型車.由于支持向量機僅能夠解決兩類分類問題，當需要解決實際應用中的確定多類分類問題時，需要構造新的多類分類器.目前，常見的多類分類器主要有以下4種類型:一對多組合、一對一組合、決策有向無環圖和全局優化分類.

為了有效地對目標進行區分，如圖2所示，在一對多組合類型分類器的基礎上設計了基于二叉決策樹方案的支持向量機分類器.基于二叉樹的多類SVM是先將所有類別分成2個子類，再將子類進一步劃分成2個次級子類，如此循環，直到所有的節點都只包含1個獨立的類別為止.該方法將原有多類分類問題分解成一系列的2類分類問題，其中2個子類間的分類函數采用SVM，二叉樹方法可以避免傳統方法的不可分情況，并只需構造k-1個SVM分類器，測試時并不一定需要計算所有的分類器判別函數，從而可以節省測試時間.

圖2 二叉決策樹SVM分類器Fig.2 Binary decision tree SVM classifier

基于SVM的二叉樹多類分類決策算法原理如下［12-13］:

給定一個k類分類問題，學習樣本為{(x1，y1)，(x2，y2)，…，(xl，yl)}，xi∈Rn，yi∈{1，2，…，k}，i= 1，2，…，l.

一個二叉樹分類結構是一個4元組＜F，P，SVM，SC＞，其中F={f1，f2，…，fk}，是二叉樹的終節點的集合，由待識別的k個運動目標類別構成; P={p1，p2，…，pk}，P表示目標分類的優先級，根據各種目標在場景中發生頻率的高低來確定.最可能出現的狀態優先級為p1，發生可能性最低的狀態定為最后一級pk.

SVM={SVMP1，SVMP2，…，SVMPk－1}是由所設計的k－1個SVM組成的二叉樹的全部非終止節點集合.對一個k類分類問題，需要構造k－1個SVM.其中第i個SVM決定的目標類別為pi.

SC={SC1，SC2，…，SCk}為屬于k個目標類別的全部學習樣本集合，其中SCi={(x1，yi)，(x2，yi)，…，(xli，yi)}表示第i類的樣本組成，xj∈Rn，yi∈{1，2，…，k}.ΣSCili=l構成全部學習樣本.

第i級支持向量SVMPi的訓練樣本SPi按下述原則確定:

第i個SVM解決以下問題:

如果yi=i，則

如果yj≠i，則

這樣可得到k－1個決策函數:

對每一級SVM訓練后找出對應該級的支持向量，建立最優分類超平面.由于k－1個SVM是按照優先級由高到低排列的，新模式產生時，只需按照二叉樹由高到低進行搜索，就可得出結論.

二叉決策樹SVM總體上屬于基于SVM的多類策略中的第一大類，相對于“one against all”和“one against one”策略，大大降低了樣本的重復訓練量.

3 實驗及結果分析

為了驗證本文提出的目標分類算法的有效性，在臺式計算機上進行相關測試.其中，計算機的配置為Intel Pentium IV 2.0 CPU，內存2G，軟件在Visual C++6.0下開發完成.測試所用圖像主要來自兩部分:一部分來自http://cvrr.ucsd.edu/aton/shadow的UIUC數據庫，圖像分辨率為138×87.另外一部分來自于哈爾濱市區某路口拍攝到的實際視頻圖像序列，使用CCTV視頻監控模擬攝像機，通過圖像采集卡完成圖像采集，圖像分辨率為320×240，本文的分類方法全部在灰度圖像上處理.

3.1 CKPCA-HOG描述子性能分析

利用CKPCA-HOG描述子提取目標特征，選用徑向基核函數 K(xi，xj)=exp(－|xi－xj|2/σ2.KPCA-HOG描述子中的各個參數為ωg=5，σg=1.2，sw=2，sh=2，sb=8，nf=200，np=20.方向量化間隔為5度，每個特征向量為72維.經過KPCA分析，每個目標由20維的CKPCA-HOG描述子進行描述.

表1給出了基于HOG、PCA-HOG、KPCA-HOG和CKPCA-HOG 4種描述子進行目標分類時的運算時間比較結果.從表中可以看出，HOG特征高達上千維，而PCA-HOG特征和KPCA-HOG和CKPCAHOG特征僅20維.數據維數的降低，意味著計算速度的加快.從運算時間上看，基于HOG特征的目標分類時間最慢，基于PCA-HOG特征的目標分類時間最快，基于CKPCA-HOG的分類時間介于前面兩者所花的時間.從表中可以看出，基于CKPCA-HOG方法，大大提高了KPCA計算核矩陣的速度，而且隨著數據個數的增多，幾乎不影響原來的計算速度.另外，雖然該算法較PCA-HOG算法慢些，但是目標分類精度卻提高很多.

表1 運算時間比較Fig.1 Comparison of computation time

3.2 實驗目標分類結果

3.2.1 訓練階段

訓練階段為了能使支持向量機能夠準確地對目標進行分類，需要輸入一些有代表性的包含運動對象的靜態圖像訓練樣本對其進行訓練.首先收集M幅正樣本和Q幅負樣本圖像作為訓練器的訓練圖像.這里的正樣本指的是待檢測目標樣本，包括行人、小轎車、中型車和大型車等.正樣本可以由單個的目標圖片或者一系列的事先標記好的圖片來創建，也可以從一個預先標記好的圖像集合中獲取.負樣本來自于其它任意的圖片，但這些圖片不能包含目標特征.通常負樣本由背景描述文件來描述.如果樣本圖像尺寸不同，統一調整成為大小為N×N的圖像.然后計算每幅圖像的CKPCA-HOG特征，從而獲得進行支持向量機分類模型訓練所需要的特征向量樣本點，并將這些樣本點輸入到SVM中進行訓練，通過優化理論調整分類器的參數，最終獲得對象分類的支持向量機分類模型.圖3給出了用于訓練支持向量機的一組數據，該數據取自UIUC測試圖像庫.文中共有1050幅測試圖像，其中正樣本圖像為500幅(M=500)，負樣本圖像為550幅(Q= 550).

圖3 SVM訓練數據Fig.3 Training data for SVM

本文中，場景中的目標為車輛(小型車、中型車和大型車).因此，訓練樣本共有C(=3)類，分別計為A1，A2，A3.針對每個分類器SVMi(i=1，2，3)，將訓練樣本中的第i類樣本Ai作為正樣本訓練，其他所有的樣本作為負樣本訓練.在完成目標特征提取后，將這些特征數據組合成特征向量X.根據每幅圖像生成的特征向量xi，以及該圖像隊應的視頻對象yi，組成用于測試的樣本點(xi，yi).將由N幅圖像組成的樣本點集合作為支持向量機的輸入，訓練第i類分類器SVMi，得到相應的分類平面，用來區分該類與其他類目標.

文中采用的特征有:全局特征中的形狀特征，長度、寬度和長寬比，局部特征中的HOG描述符.對于行人和車輛目標的區分，主要采用的特征是:外形尺寸、復雜度、長寬比、緊湊度.首先，根據目標的外形尺寸、復雜度、長寬比和緊湊度將運動目標分為行人和車輛.然后再根據CKPCA-HOG特征描述符將車輛分為小型車、中型車和大型車.

緊湊度:C=4π*Area/Perimeter2，其中Perimeter表示目標邊界所有像素個數的總和.

3.2.2 識別階段

在識別階段，首先導入訓練好的支持向量機分類模型.然后利用特征描述子CKPCA-HOG提取目標的特征向量，并將該特征向量輸入到支持向量機中，通過判別公式獲得最后的目標分類結果.

下面給出針對UIUC數據庫的分類結果.對于待分類的170幅圖像，訓練好的車輛分類器成功地檢測到 156個車輛，漏檢 14個，檢測率達到了91.7%.圖4給出了其中正確識別的結果;圖5給出了錯誤分類和漏檢的結果.

圖4 正確分類結果Fig.4 Correct classification results

圖6給出了城市道路實際場景中目標分類結果.該圖像取自哈爾濱市某交叉口監控視頻序列.該場景中不但有機動車、非機動車和行人，而且路面上有雪、晃動的攝像頭、搖擺的數目以及圖像噪聲都對目標分類產生不利的影響.首先，利用背景減除算法獲得前景運動目標，在完成陰影檢測和消除后得到最終的運動目標掩模.從圖6給出的分類結果中可以看出，本文提出的算法能夠對場景的車輛和行人進行準確的分類.

圖5 錯誤和漏檢結果Fig.5 False and leak classification results

圖6 實際場景分類結果Fig.6 Classification results of real scenes

4 結束語

文中提出一種魯棒的目標分類算法.在訓練階段，利用CKPCA-HOG特征描述子得到目標特征向量，然后對二叉決策樹SVM進行訓練.相對于基于HOG和SVM的目標分類方法相比，本算法在保證識別準確率的同時，系統運行時間在2個方面得到了明顯改善:利用CKPCA-HOG特征描述子大大降低了目標特征數據維數;利用二叉決策樹SVM在進行多類目標分類的時候節省了測試時間.

本文提出的算法對場景中出現的目標能夠很好地區分，下一步將機器學習引入到分類器訓練數據提取中，依此來改進分類器性能.由于傳統的分類器在訓練過程中由人工事先將訓練樣本定義好類別，這種方法太費時，而且容易導致內在的模糊.此外，由于目標提取不當造成的定義類的錯誤和分配標簽不正確所產生的誤差將最終被傳播到最終分類，影響目標檢測性能.如果在目標分類過程中，系統根據分類結果提取合適的訓練樣本，這樣使系統適應能力更強，從而可以提高分類器的性能.

［1］VEERARAGHAVAN H，MASOUD O，PAPANIKOLO_ POULOS N P.Computer vision algorithms for intersection monitoring［J］.IEEE Trans on Intelligent Transportation Systems，2003，4(2):78-89.

［2］ATEV S，ARUMUGAM H，MASSOUD O，JANARDAN R，PAPANIKOLOPOULOS N.A vision-based approach to collision prediction at traffic intersections［J］.IEEE Trans on Intelligent Transportation Systems，2005，6(4):416-423.

［3］GANDHI T，TRIVEDI M M.Video based surround vehicle detection，classification and logging from moving platforms: issues and approaches［C］//IEEE Intelligent Vehicles Symposium.［s.l.］，2007:1067-1071.

［4］趙秀娟，劉志勇，樊可清.基于支持向量機的車輛自動分類方法［J］.公路交通科技，2003，20(5):108-110.

ZHAO Xiujuan，LIU Zhiyong，FAN Keqing.SVM based method for vehicle automatic-classification［J］.Journal of Highway and Transportation Research and Development，2003，20(5):108-110.

［5］DALA N，TRIGGS B.Histograms of oriented gradients for human detection［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Beijing，2005:886-893.

［6］OLIVEIRA L，NUNES U.On integration of features and classifiers for robust vehicle detection［C］//Proceedings of the 11th International Conference on Intelligent Transportation Systems.Beijing，2008:414-419.

［7］WANG Zhenrui，JIA Yulan，HUANG Hua，TANG Shuming.Pedestrian detection using boosted HOG features［C］//Proceedings of the 11th International Conference on Intelligent Transportation Systems.Beijing，2008:1155-1160.

［8］KHAMMARI A，NASHASHIBI F，ABRAMSON Y，LA_ URGEAU C.Vehicle detection combining gradient analysis and AdaBoost classification［C］//IEEE Conference on Intelligent Transportation Systems.［s.l.］，2005:1084-1089.

［9］朱文佳，戚飛虎.基于Gentle Adaboost的行人檢測［J］.中國圖象圖形學報，2007，12(10):1095-1098.

ZHU Wenjia，QI Feihu.Gentle adaboost based pedestrian detection［J］.Journal of Image and Graphics，2007，12 (10):1095-1098.

［10］王和勇，姚正安，李磊.基于聚類的核主成分分析在特征提取中的應用［J］.計算機科學，2005，32(4): 64-66.

WANG Heyong，YAO Zhengan，LI Lei.The application of feature extraction on using kernel principal component analysis based on clustering［J］.Computer Science，2005，32(4):64-66.

［11］SMOLA A J，SCHOLKOPF B.Sparse greedy matrix approximation for maehine leaming［C］//Proc of ICML＇00，Bochum，Germany，2000:911-918.

［12］韓順杰，趙丁選.基于SVM的二叉樹多類分類算法在工程車輛擋位決策中的應用［J］.中國公路學報，2007，20(5):122-126.

HAN Shunjie，ZHAO Dingxuan.Application to shift decision for construction vehicle based on SVM binary tree multi-class classification algorithm［J］.China Journal of Highway and Transport，2007，20(5):122-126.

［13］馬笑瀟，黃席樾，柴毅.基于SVM的二叉樹多類分類算法及其在故障診斷中的應用［J］.控制與決策，2003，18(3):272-276.

MA Xiaoxiao，HUANG Xiyue，CHAI Yi.2PTMC classification algorithm based on support vector machines and its application to fault diagnosis［J］.Control and Decision，2003，18(3):272-276.