汪霜霜　李春貴

摘??? 要：車輛軌跡學習可用于視頻監(jiān)控系統(tǒng)，以識別正常和異常車輛運動模式，用于交通運營、公共服務和執(zhí)法管理.本文的目的是研究一種新的基于視頻監(jiān)控系統(tǒng)的車輛軌跡學習自適應稀疏重構方法.由于[l1]和[l2]最小化的解的稀疏性會受到范數中項的值的損害，在實踐中不能保證得到足夠稀疏的解，本文提出了一種改進的基于[lp][0<p<1]最小化的車輛軌跡學習方法，應用[lp]范數的下限理論獲得更稀疏的重構系數向量，以獲得比[l1]或[l2]最小化更稀疏的解.通過實驗分析，所提出的方法可以解決過擬合問題，獲得更稀疏的解.

關鍵詞：稀疏重構;范數;正則化;最小化

中圖分類號：TP277.2;U495??????????? DOI：10.16375/j.cnki.cn45-1395/t.2019.02.008

0??? 引言

伴隨著人們對實時交通的管理和安全上的需求逐步增長，視頻監(jiān)控系統(tǒng)被廣泛用于交通道路.由于傳輸和存儲視頻數據的成本顯著降低，大量交通視頻被收集并應用于車輛運動模式、交通違規(guī)和車輛碰撞的研究.但是難以連續(xù)手動監(jiān)控和分析如此大量的視頻，致使研究人員開發(fā)智能方法，從存儲的視頻數據中自動識別交通事件和交通活動.OH Cheol等[1]提出了一種用于學習車輛行為的新型高速公路交通監(jiān)控系統(tǒng)，通過檢測車輛換道引起的潛在碰撞來進行監(jiān)控跟蹤，設置碰撞時間和停車距離指數這兩個指標來學習車輛行為.然而，當前大多數的視頻監(jiān)控系統(tǒng)只能捕獲交通量和車輛變道或超速行為，不能滿足諸如車輛行為識別和異常行為檢測的需求.因此，當務之急是需要研究一種有效的方法來進行關于交通運營、公共服務和執(zhí)法的視頻中監(jiān)控的車輛軌跡的學習.

有研究學者聲稱，稀疏表示可以表現出對大量噪聲和面部遮擋的魯棒性[2].稀疏重建技術能很好地避免樣本不足、特征描述不完整、額外的噪聲和失真等問題[3].稀疏重建的核心是解決[l0]最小化問題.現有的研究成果通常是將[l0]最小化問題歸結為[l1]或[l2]最小化問題，并應用凸優(yōu)化求解器，如二階核心規(guī)劃求解器，甚至啟發(fā)式算法，如正交匹配追蹤算法等[4].ADU-GYAMFI等[5]應用稀疏表示技術來識別交通標志.CONG等[6]應用具有組約束的稀疏重建模型來檢測基于視頻數據的異常事件.然而，來自[l1]和[l2]最小化的解的稀疏性會受到范數中項的值的損害，導致不能保證得到足夠稀疏的解，這將會損害基于[l1]和[l2]最小化的學習方法的辨別能力.

因此，在車輛軌跡學習的領域中，要找到一種更稀疏的解決方案來減少規(guī)范中的有害影響，從而增強稀疏重構的能力.為此，本文提出了一種改進的基于[lp][0<p<1]最小化的車輛軌跡學習的方法，應用[lp]范數的下限理論獲得更稀疏的重構系數向量，通過實驗作比較，獲得比[l1]或[l2]最小化更稀疏的解，為后續(xù)利用基于軌跡的稀疏重建方法來檢測車輛異常行為的研究做準備.

1???? 相關理論

1.1??? 稀疏規(guī)則化和最小化誤差

稀疏正則化能被廣泛應用在于它的一個關鍵優(yōu)點——能夠自動選擇特征.通常，輸入[xi]的大多數元素或特征與最終的輸出[yi]無關.若在求解目標函數最小化的時候使用這些[7]，雖然可以讓結果的訓練誤差更小，但是在對新樣本進行預測的時候，由于有了這些無關信息的干擾，從而影響了對正確[yi]的預測.稀疏正則化算子會學習怎樣去刪除這些無關緊要的特征，其做法就是將與這些特征對應的權重值設置為零，其引入的作用就是為了能夠進行自動選擇特征.

為了讓模型更好地擬合訓練數據，一般是將誤差最小化，而使用正則化參數則是避免模型過分擬合訓練數據.所謂過度擬合，就是在訓練樣本中，已建立好的學習模型表現過于優(yōu)越，然而在驗證數據集和測試數據集中表現出的性能卻不如意.過度擬合的根本原因是模型學習過于精確，甚至將訓練集中的樣本噪聲也進行了訓練.參數越多，模型的復雜性就不斷增加，并且易出現過度擬合現象，影響預測新樣本的正確性.要在盡可能保證模型“簡單”的基礎上去訓練誤差達到最小化，這樣所得的參數才具備好的泛化性能，即得到的測試誤差小.正則函數的使用可以使模型“簡單”化.把與模型相關的先驗知識融入到模型的學習當中，讓其具有所需要的特性，例如稀疏、低秩、平滑等.[l1]和[l2]正則化常被用來解決過擬合問題.

1.2?? [l1]范數

[l1]范數被稱為“稀疏規(guī)則算子”.因為[l0]范數很難進行優(yōu)化求解，而[l1]范數是[l0]范數的最優(yōu)凸近似，比較容易優(yōu)化求解，更得研究者的喜愛和重視.

對于[l1]正則化，是指權值向量[w]中各個元素的絕對值之和，通常表示為[w1]，數學表示如式（1）所示：

[Ωθ=12w1=12i=1nwi]???????????????????????????? （1）

用線性代數表示損失函數為：

[Jw;X，y=αw1+Jw;X，y]???????????????????????? （2）

對權重求取梯度，得：

[?wJw;X，y=αsignw+?wJw;X，y]?????????????????????????????????????????? （3）

其中[signw]表示取[w]中各個元素的正負號.從上面的等式可以看出，正則化對梯度的影響并不是線性地縮放每個[wi]，而是添加了一項與[wi]相同符號的常數.通過[l1]正則化，可以利用足夠大的[α]實現稀疏.也就是說[l1]正則化可以產生稀疏權值矩陣，即產生一個稀疏模型，可以用于特征選擇機制[8].

1.3?? [l2]范數

[l2]范數又稱歐幾里德距離之和.它是指權值向量[w]中各個元素的平方和然后再求平方根，通常表示為[w2]， 數學表示為：

[Ωθ=12w22=12i=1nwi2]?????????????????????????? （4）

讓[l2]范數的規(guī)則項[w2]最小，即讓[w]的每個元素都很小，都接近于0.參數越小，模型越簡單;模型越簡單，過度擬合的可能性就越低.那么損失函數就變成了如式（5）所示：

[Jw;X，y=αwTw+Jw;X，y]??????????????????????????????????????????????????????????????????&nbsp;? （5）

求解梯度后，其梯度表示為：

[?wJw;X，y=αw+?wJw;X，y]???????????????????????????? （6）

因此在梯度下降過程中權重的更新如下式所示：

[w←w-βαw+?wJw;X，y]

其中，[β]為梯度下降的步長，最終得到了：

[w←1-βαw-?wJw;X，y]

可以看到，在梯度更新的每個步驟之前收縮權重向量，并讓權重向量乘以常數因子，加入權重衰減量后導致學習規(guī)則被修改. 通過[l2]范數，既可以實現對模型空間的抑制[9]，還可以實現正則化，在一定程度上避免過擬合，提升了模型的泛化能力.但是，[l2]范數不能夠得出稀疏解.

1.4?? 殘差

所謂殘差，是指觀測值與預測值（擬合值）之間的差，即是因變量的觀測值[yi]與根據估計的回歸方程求出的預測[yi]之差，用[e]表示.反映了用估計的回歸方程去預測[yi]而引起的誤差，第[i]個觀察值的殘差為：

[ei=yi-yi].

通過對殘差及殘差圖的分析，以考察模型假設的合理性的方法，稱為殘差分析.可以利用殘差所提供的信息分析出數據的可靠性、周期性以及其他干擾項，可用來判定分析模型的假定正確與否，運用殘差分析的方法來檢查回歸線的異常點比較直觀，效果也好.

2??? 車輛軌跡的稀疏重構

2.1?? 基于[l1]和[l2]范數的車輛軌跡的稀疏重構

通過訓練車輛軌跡，可以近似線性組合任何一個新的車輛軌跡[10-11].對于給定的第[i]類足夠訓練的軌跡（總共有M個類），同一類的測試軌跡[yi∈Rm]可以通過訓練軌跡的線性組合來表示，如下所示：

[yi=Aiσi=σi，1θi，1+σi，2θi，2+…+σi，nθi，n（σi∈Rn）]????????????????????? （7）

也可以用訓練字典來表達為：

[yi=Aiσi∈Rm]????????????????????????????????????????????????????????????????????? （8）

其中[σ=0，…，0， σTi， 0，…，0T∈Rn]是一個系數向量，其中大多數條目具有零元素，[θi，n]是[A]的特征值.

稀疏重建在車輛軌跡學習中的應用如圖1所示.

由圖1可見，字典[A]由訓練軌跡組成，它包含M個類.根據稀疏重構模型，測試軌跡[y]的系數向量[σ]為：

[σall=[0， 0， 0， 0， 0， 0，…， 0.87， 0， 0， 0.33，-0.21， 0， …，0， 0， 0， 0， 0， 0]T]

基于系數向量[σall]，[y]可以通過稀疏重構來學習. 為了尋找[y=Aσ]的最稀疏解，可以采用式（9）解決：

[minσ0：=σ0]

[s.t.]???????????? [y=Aσ]????????????????????????????????????????????????????????????????????? （9）

其中，[σ0]表示[σ]的[l0]范數，計算[σ]中非零項的數量.式（9）表示的是眾所周知的非確定性多項式問題，由于其目標函數是非凸的，所涉及的問題是要找到最稀疏解.通常的解決方法是將[l0]范數放寬為如[l1]范數或[l2]范數這樣的凸目標函數，就可使問題變得容易處理[12].[l1]范數或[l2]范數的數學公式如式（10）—式（11）所示：

[minσ1：=σ1]

[s.t.]???????????? [y=Aσ]????????????????????????????????????????????????????&nbsp;?????????? （10）

[minσ2：=σ2]

[s.t.]???????????? [y=Aσ]???????????????????????????????? （11）

式（10）所表達的具有[l1]范數的模型被認為是[l0]范數和[l2]范數之間的折衷，這是一個凸優(yōu)化問題，可以通過二階核心編程或者甚至標準線性編程求解器在多項式時間內求解來解決[13].式（11）的優(yōu)點在于它的精確解（全局最小值）只需使用一些啟發(fā)式算法就能很快找到，如正交匹配追蹤（OMP）算法.

2.2??? 一種改進[lp]范數的車輛軌跡的稀疏重構

由于[l2]范數的稀疏性會被范數中元素的平方值顯著削弱，造成式（11）的解與稀疏性相去甚遠.根據稀疏表示和壓縮感知理論可知，如果[σ0]的解足夠稀疏，[l0]極小化問題的解就等于下一個[l1]極小化問題的解，但是實現這樣的條件很難，在實踐中的大多數情況下也是沒用的.因此對于一些對稀疏性要求很高的地方，式（10）同樣不適用.

對此應該引入較小的[lp][0<p<1]范數來保證稀疏解.然而，[lp]范數[0<p<1]的目標函數是非凸的，它的精確解（全局極?。┩瑯邮欠谴_定性多項式問題.由于等式約束在實踐中過于嚴格，因此通常是通過引入一個有效的小誤差[ε]轉換為不等式形式[14]，即[Aσ-y≤ε].通過引入正則項[γσpp]將約束最小化問題轉化為無約束最小化問題，如式（12）所示：

[minfσ：=Aσ-y22+γσpp]??????????????????????????? （12）

其中[p]= 0和1分別對應于式（9）和式（10）的[l0]正則化和[l1]正則化.

根據式（12），在正則化項中使用[lp][0<p<1]范數通?？梢哉业奖仁褂肹l1]范數更稀疏的解，可以建立更強的學習模型，但是它的求解過程有很強的不確定性，其計算復雜度、時間和空間復雜度都難以控制.為了解決這個問題，引入了[lp]正則化的下限定理[15]，以保證在比[l1]正則化更弱的條件下得到更稀疏的解.[lp]正則化的下限定理的內容如式（13）所示：

[L=γp2Afσ01/（1-p）][0<p<1]????????????????????????????????????????????????????????????????? （13）

對于式（12），大多數最小化算法本質上都是下降迭代，它們生成一系列點[σv]，[v=0， 1， …]，這樣目標函數值[fσv]就沿序列嚴格遞減.因此，在水平集[σ：? fσ≤fσ0]中，下降算法可以找到局部極小值，包括全局極小值（其中，[σ0]是任意給定的初始點）.令[Li=γp1-p2ai21/（2-p），i∈N]，對于任意的[σ*∈δ*p]，有任意的[i∈N]，[σ*i∈-L， L?σ*i=0]. 對于有限大的[γ]，[σ*0]減小到0就意味著[σ*=0]是唯一的全局極小值.但[σ*]中的非零條目數有如下限制：

[σ*0≤minm， fσ0γLp]

該定理揭示了：如果在[lp][0<p<1]極小化的局部極小化器[σ*i]中獲得的[σ*i]項滿足條件，即[σ*i∈（-L， L）]，那么就可以知道全局極小化器中的相應項是0.因此，該定理可用于使獲得的解更稀疏，并且更接近全局最小值的[θ=I?+θ=I?+γμα?1/21/2-1]

記[H1/2，γ=I?+γα?1/21/2-1].利用[l1/2]正則化求稀疏解的算法有兩種：Reweighted-[l1]算法和Half算法.在數據集[D=θ，c]，利用Reweighted-[l1]算法[17]，來學習[mingθ-c22+γθ1/21/2]的解[θ]的基本思想是：用[θ01/2+12θ1/2θ-θ0]近似[σ1/2]，并取分母部分作為當前值;利用[l1]中交叉驗證的方法設置正則化參數.

一般情況下采用Half算法進行求解，本文所采用的算法也是Half算法.該算法的基本思想是對[l1/2]解的解析形式[θ=I·+γμα·1/21/2-1Buθ]使用逐次逼近;假定稀疏度k已知，通過下述迭代過程求解問題的k-稀疏解：

[θn+1=Hγnμn，1/2Bμnθn ， θ0∈RNγn=969μBμnθn3/2（k+1） ，? μ=μ0∈0，1/L]

采用逐次近似取[γt=4/3μBtk+13/2]來逼近[γ*]，利用該算法，對于足夠小的[μ]，可得到[θt+1-θt2→0].將原問題分解成若干個k-稀疏解的問題，通過不斷迭代獲得一組[k]-稀疏解，比較得出最優(yōu)解.其算法步驟如下：

Step 1? 隨機選取[θ0∈R]，設[B0=θ0+ATc-Aθ0]，[γ0=μ4/3B0k+13/2]，其中[k]為問題稀疏度的預估值，[θ0k+1]為[θ0]的第[k+1]大的分量，取定[0<μ<1]和誤差容限[ε].置[t=0];

Step 2? 計算[θt+1=H1/2，γtθt+ATc-Aθt];

Step 3? 令[Bt=θt+ATc-Aθt，γt+1=4/3μBtk+13/2];

Step 4? 若[θt+1-θt2<ε]，算法終止;否則，置[t=t+1]并轉Step 2繼續(xù)進行.

綜上，Reweighted-[l1]算法和Half算法這兩種算法常用于[l1/2]正則化和稀疏解的求解，并且得到廣泛應用[18-19].

4??? 實驗分析

為了檢測所提出方法的性能，實驗環(huán)境為Win10系統(tǒng)，系統(tǒng)配置16 GB內存，3.60 GHz CPU，Visual Studio Community 2015，使用CROSS數據集，CROSS數據集由加州大學提供.它包含1 900條訓練軌跡和? 9 700條測試軌跡，其中9 500條為正常軌跡，200條為異常軌跡（如非法環(huán)路、越野駕駛、非法左轉和其他異常行為）.在數據集中選擇第四類測試軌跡的其中之一，在當[p]= 2、1和0.5時分別顯示其系數向量[σL2]、[σL1]和[σLp]（[0<p<1]），實驗結果如圖3所示.其中，系數向量[σL1]和[σL2]都是式（10）和式（11）的全局極小值，而[σLp][0<p<1]是在[p]= 0.5時由定理修正的近似最優(yōu)極小值.

以系數為縱坐標，字典為橫坐標，圖3（a）—圖3（c）分別顯示了[σL2]、[σL1]和[σLp]的結果;以殘差為縱坐標，類別為橫坐標，圖3（d）—圖3（f）分別顯示了對應于這些解的殘差，而對應于最小殘差的類將被標記為測試軌跡的類.

從圖3（a）—圖3（c）中可以很明顯地看出，[σLp]比[σL2]和[σL1]要稀疏得多;圖3（d）和圖3（e）顯示，由于在分類過程中幾十個非零條目的干擾，[σL2]和[σL1]的殘差會根據不同的類別產生很大的變化.相比之下，圖3（f）顯示了除了第四和第七個殘差（其中第四個殘差是最小的）之外，[σLp]的大部分殘差是相同的.更重要的是，來自[σLp]的最小殘差對應于圖3（c）中正確的類別（即第四類別），這就意味著測試軌跡可以通過[σLp]最小化的方法正確分類，而圖3（d）和圖3（e）分別顯示的[σL2]和[σL1]的最小殘差對應于? 圖3（a）和??????? 圖3（b），它們都不對應于正確的類別（它們都對應于第七類別）.

實驗表明，來自[σLp]最小化的改進的局部最小化器會獲得比來自[σL1]和[σL2]最小化的全局最小化器更稀疏的解，能保證對于車輛軌跡的學習性能，且能夠達到正確的分類，使得最終結果能夠更準確，為后續(xù)利用基于軌跡的稀疏重建方法來檢測車輛異常行為的研究做更精確的準備.

5??? 總結

本文研究了一種用于車輛軌跡學習的[lp][0<p<1]正則化稀疏重建的方法.由于[l1]和[l2]最小化的解的稀疏性會在求解過程中受到范數中項的值的損害，不能保證能夠得到足夠稀疏的解.本文主要的改進思路是應用[lp]范數的下限理論來解決NP-hard問題，得到更稀疏的重構系數向量，從而獲得比[l1]或[l2]最小化更稀疏的解.通過與[l1]和[l2]正則化的實驗分析比較，得知所提出的模型可以達到目標，獲得更稀疏的解.

參考文獻

[1]???? CHEOL O，JUTAEK O，JOONYOUNG M.Real-time detection of hazardous traffic events on freeways methodology and prototypical implementation[J].Transportation Research Record Journal of the Transportation Research Board，2009，2129：35-44.

[2]???? 秦勝君.基于稀疏自動編碼器的微博情感分類應用研究[J].廣西科技大學學報，2015，26（3）：36-40.

[3]???? CHONG Y W，CHEN W，LI Z L，et al.Method for preceding vehicle type classification based on sparse representation[J].Transportation Research Record Journal of the Transportation Research Board，2011，2243：74-80.

[4]???? CHEOL O，EUNBI J，KYUNGPYO K.Hazardous driving event detection and analysis system in vehicular networks methodology and field implementation[J].Transportation Research Record Journal of the Transportation Research Board，2013，2381：9-19.

[5]???? ADU-GYAMFI Y，ATTOH-OKINE N.Traffic sign recognition using sparse representations and active contour models[J].Transportation Research Record Journal of the Transportation Research Board，2014，2463，35-45.

[6]???? CONG Y，YUAN J S，LIU J.Abnormal event detection in crowded scenes using sparse representation[J].Pattern Recognition，2013，46：1851-1864.

[7]???? 段淑玉，徐奕奕，李春貴，等.一種基于運動矢量時域遞歸的運動估計算法[J].廣西科技大學學報，2015，26（2）：36-40.

[8]???? 朱華，岳峻，李振波，等.基于l（2，1）范數原子選擇的圖像分塊稀疏重構[J].計算機應用研究，2019，36（6）：1-3.

[9]???? 陳鵬清，黃尉.基于l1-l2范數的塊稀疏信號重構[J].應用數學和力學，2017，38（8）：932-942.

[10]?? XU Y，ZHONG Z F，YANG J E，et al.A new discriminative sparse representation method for robust face recognition via l2 regularization[J].IEEE Transportation on Neural Networks and Learning Systems，2017，10：2233-2242.

[11]?? MO X，MONGA V，BALA R，et al.Adaptive sparse representations for video anomaly detection[J].IEEE Transportation on Circuits and Systems for Video Technology，2014，24（4）：631-645.

[12]?? 周巍.L1范數最小化算法及應用[D].廣州：華南理工大學，2013.

[13]?? DONOHO D L，MALEKI A，MONTANARI A.Message-passing algorithms for compressed sensing[J].Proceedings of the National Academy of Sciences of the United States of America，2009，45：18914-18919.

[14]?? STOJNIC M.l2/l1-optimization in block-sparse compressed sensing and its strong thresholds[J].IEEE Journal of Selected Topics in Signal Processing，2010，4（2）：350-357.

[15]?? CHEN X J，XU F M，YE Y Y.Lower bound theory of nonzero entries in solutions of l2-lp minimization[J].Siam Journal on Scientific Computing，2010，5：2832-2852.

[16]?? 徐宗本，吳一戎，張冰塵，等.基于L（1/2）正則化理論的稀疏雷達成像[J].科學通報，2018，63（14）：1306-1319.

[17]?? 董衛(wèi)東，彭宏京.緊框架域重加權L1范數正則化圖像恢復模型[J].小型微型計算機系統(tǒng)，2018，39（1）：179-184.

[18]?? 葉丹，張成毅，羅雙華.基于稀疏指數追蹤模型的SOR-Half閾值算法[J].紡織高?；A科學學報，2015，28（4）：457-462.

[19]?? 張亞飛，張成毅，羅雙華.基于稀疏魯棒M-投資選擇模型的魯棒Half算法[J].西安工程大學學報，2017，31（1）：135-140.

An improved minimization of vehicle trajectory learning

WANG Shuangshuanga， LI Chungui*b

（a. School of Electrical and Information Engineering; b.School of Computer Science and Communication

Engineering， Guangxi University of Science and Technology， Liuzhou 545006， China）

Abstract： Vehicle trajectory learning can be used in video surveillance system to identify normal and abnormal vehicle movement patterns for traffic operation， public service and law enforcement???????? management. The paper aims to study a new adaptive sparse reconstruction method for vehicle?????????? trajectory?? learning based on video surveillance system. Enough sparse solution cannot be guaranteed in practice because the sparsity of the minimized solution will be impaired by the value of the term in the norm. A new method of vehicle trajectory learning based on minimization is proposed in this paper. The lower bound theory of norm is applied to obtain more sparse reconstruction coefficient vectors in order to obtain more sparse solutions than or minimization. Through experimental analysis， the???????? proposed method can solve the over-fitting problem and obtain more sparse solutions.

Key words： sparse reconstruction; norm; regularization; minimization