一種面向運動目標提取的對稱交替方向RPCA算法

吳高宇，邵振洲，2，渠 瀛，施智平，3，關 永，2

1(首都師范大學 信息工程學院，北京 100048)

2(成像技術北京市高精尖創(chuàng)新中心，北京 100048)

3(首都師范大學 輕型工業(yè)機器人與安全驗證北京市重點實驗室，北京 100048)

4(田納西大學 諾克斯維爾分校工程學院，田納西 美國 37996)

1 引 言

運動目標提取是計算機視覺中基礎而又關鍵的處理步驟[1]，廣泛應用于道路交通監(jiān)控、自動駕駛等領域中.經典的運動目標提取方法有幀差法、背景差分法、光流法等.但是幀差法和背景差分法對背景變化的魯棒性不好，光流法則計算量較大.同時，隨著圖像分辨率的提高，數據的冗余度增加，這對算法效率提出了更高的要求[2].

近年來，基于魯棒主成分分析(Robust Principal Component Analysis，RPCA)的運動目標提取算法有效解決了上述問題，成為該方向的研究熱點[3].采用RPCA的方法對運動目標進行提取，這個模型要求前景目標相對整張圖片要比較小，這使得該方法的實際運用受到很大限制.后來的研究者對此進行了改進，Candes等人[4]提出用凸規(guī)劃方法來解決RPCA問題.在這種方法中，作者將低秩與稀疏矩陣的分解等價為如式(1)所示的凸規(guī)劃問題：

(1)

其中，‖·‖l1為l1范數，‖·‖*為核范數，δ為任意一個大于零的規(guī)整化參數，C為要處理的矩陣，x為稀疏矩陣，y為低秩矩陣.式(1)中的最優(yōu)化問題一般采用迭代閾值技術[5]或加速近端梯度算法(Accelerated Proximal Gradient Descent，APG)[6]解決，收斂速度較慢.后來Lin等人基于增廣拉格朗日乘數法(Augmented Lagrange Method，ALM)提出了EALM(Exact Augmented Lagrange Method)和IALM(Inexact Augmented Lagrange Method)[7].然而，這兩種方法在求解式(1)時，并沒有利用到目標函數與約束條件的可分離結構，影響了算法的提取效果.Yuan 和Yang[8]提出了用交替方向法(Alternating Direction Method，ADM)來求解式(1)，但這種方法在每次迭代過程中需要進行多次奇異值分解(Singular Value Decomposition，SVD)計算，這使得整個算法的計算量很大，耗時較長.同時在迭代求解過程中，由于沒有考慮到低秩和稀疏矩陣之間的關系，最后分解的精度也不高.

Zhang等[9]針對變分不等式問題提出的新交替方向法，具有簡單易行和計算效率高的特點.在上述方法的啟發(fā)下，本文提出了一種基于對稱交替方向法(Symmetrical Alternating Direction Method，SADM)的運動目標提取算法，其流程圖如圖1.該算法核心思想是將視頻序列中連續(xù)的多幀作為輸入，每一幀都轉換成矩陣C的一列，再將矩陣C通過主成分分析的方法分解成一個稀疏矩陣x和一個低秩矩陣y，x矩陣中每一列對應矩陣C中同列圖片的運動目標，y矩陣中每一列則對應背景.SADM根據交替方向法的對稱原理[10]，將求解過程中的線性約束乘數在一次迭代中更新兩次，這個改變將會使得收斂速度更快，從而減少算法的計算時間.同時，本文在算法中引入了新的停機準則和均衡參數，避免了不必要的迭代，通過將規(guī)整化參數δ加入到迭代過程中，使得結果具有更好的分解效果，從而提高目標的提取精度.

圖1 整體流程圖Fig.1 Overall flow chart

從多幀視頻序列組成的矩陣C中提取出運動目標可以等價為求解式(1)的稀疏矩陣x和低秩矩陣y.x包含了運動目標，y則包含了背景.而ADM的求解方法計算量大、耗時長，所以本文采用一種新的方法——SADM來解決式(1).該方法一是改進了ADM的迭代策略；二是將新的均衡參數和停機準則加入到式(1)的迭代求解過程中，接下來做具體介紹.

2 對稱迭代策略

針對前文提到的ADM收斂速度較慢的問題，本文在研究該算法的時候發(fā)現，在每一次的迭代更新過程中，原方法都只對線性約束乘數Z做了一次更新，而Z作為判別算法收斂的參數，其緩慢的更新速度也是導致算法速度慢的重要原因.針對這一問題，本文采用了一種新的對稱迭代策略，以加快Z的更新速度，減少算法的耗時.

通過令f(x)=‖x‖*，g(y)=δ‖y‖l1，式 (1)可以寫成：

min{f(x)+g(y)} subj C=x+y

(2)

其對應的拉格朗日方程為[11，12]：

(3)

其中x∈X為稀疏矩陣，y∈Y為低秩矩陣，C為要處理的矩陣，Z∈r是線性約束乘數，< >為標準跟蹤內積，‖ ‖是誘導F范數，β>0為罰參數，方程定義域為U=X×Y×r.

對于式(2)，原ADM求解過程為：

(4)

其中xk，yk，Zk分別表示第k次迭代時的值，L(xk，yk，Zk)代表對應的拉格朗日方程，Z∈r是線性約束乘數.這種方法雖然利用了所給條件的可分離結構這一特點，但是在求解y時，會多次用到耗時較長的奇異值分解.y的顯式解為：

(5)

其中，UK+1∈m×r，VK+1∈n×r通過

(6)

得到.從上面的步驟可以看出，每次迭代至少需要求解兩次SVD，而該過程是最耗時的.要想有效地減少算法的運行時間，減少迭代次數是最直接的解決方案.

(7)

在y迭代之后完成對Z的第二次更新.

(8)

通過上述改變，線性約束乘數在一次迭代中完成了以前兩次迭代的工作，而線性約束乘數又是收斂的關鍵指標，它更新速度變快，算法的收斂速度也將比以前要快.同時迭代次數的減少也使得SVD次數減少，這是整個算法運行時間縮短的關鍵.

3 新的均衡參數和停機準則

在實驗過程中作者發(fā)現，有時在迭代的末尾階段，稀疏矩陣x變化很小，但卻要耗費大量的迭代次數，這使得算法的效率大打折扣，所以本文引入一個新的停機準則來解決這個問題.而原ADM分解精度不高，主要是由于在迭代分解的過程中沒有考慮矩陣x和y的權重.針對這一問題，本文將規(guī)整化參數δ這一權重參數引入到迭代過程中.而新的均衡參數的加入將會對求解過程的收斂性造成影響，文獻[9]中已經針對變分不等式問題加入新的均衡參數后的收斂性做了證明，但本文基于RPCA的運動目標提取是凸規(guī)劃問題，所以需要重新證明.本文的主要思路是通過證明變分不等式所求的解也是凸規(guī)劃問題的一個最優(yōu)解，得到在加入新的均衡參數的前提下，依然可以求得式(1)的解，即新加入的均衡參數對原最優(yōu)問題的收斂性沒有影響.

3.1 收斂性證明

設(x*，y*，Z*)是式(3)的一個鞍點，對于任意的(x，y，Z)∈U有[15]：

L(x*，y*，Z)≤L(x*，y*，Z*)≤L(x，y，Z*)

(9)

令?θ1(x)和?θ2(y)分別是凸函數θ1(x)和θ2(y)的次微分算子.f(x)∈?θ1(x)和g(y)∈?θ2(y)分別是θ1(x)和θ2(y)的一個次梯度.則求式(3)的一個鞍點等價于：

求u*=(x*，y*，Z*)∈U，f(x*)∈?θ1(x*)和g(y*)∈?θ2(y*)，使得

(10)

式(10)可以看作是式(2)的一階最優(yōu)條件.為了將式(10)緊湊化，現做如下替換：

對于u=(x，y，Z)∈U，f(x)∈?θ1(x)和g(y)∈?θ2(y)，記

(11)

所以，式(10)等價于：

求u*=(x*，y*，Z*)∈U，f(x*)∈?θ1(x*)和g(y*)∈?θ2(y*)使得

(u-u*)TQ(u*)≥0，?u∈U

(12)

(13)

由此可得，在條件相同的前提下，滿足變分不等式問題的解也是凸規(guī)劃問題的一個鞍點.因此，文獻[9]的NADM中的新的均衡參數也可以運用到式(2)求解中.

3.2 改進原理與算法流程

針對迭代末尾階段效率低的問題，本算法加入了一個誤差參數

ey(yk+1，β)=yk+1-Py[yk+1-β(g(yk+1)-Zk+1)]

(14)

作為額外的停機準則，其中Py[.]表示從n到y的投影，yk+1是迭代k+1次后的y值.該參數反映的是每一次迭代后背景矩陣y的變化情況.之所以不直接用yk+1-yk，是由于一般來說背景相對變化較小，并不能真實反映每次迭代后的變化情況，所以有可能造成停機準則的誤判，而改進的誤差參數ey(yk+1，β)將稀疏矩陣x的變化通過Zk+1和y聯系到一起，避免了以y為唯一依據而引起的誤判.改進后的停機準則在每次迭代結束后會進行一次判斷，當誤差小到一定的范圍時，就會觸發(fā)該停機準則，從而避免后面不必要的迭代過程，提高整個算法的計算效率.

針對原ADM提取目標精度不高的問題，本文通過新的均衡參數γ=2e-δ∈(0，2)，將式(1)中的規(guī)整化參數δ加入到線性約束乘數Z中.而δ起著調節(jié)x和y權重的作用，這讓每次迭代中x和y的分配根據權重進行了優(yōu)化，從而使最后的提取精度能得到提高.加入均衡參數后，SADM中對約束乘數的兩次更新分別為：

(15)

(16)

SADM在改變了原ADM迭代策略的基礎上，還引入了一個新的均衡參數和停機準則，這些改進使得算法的耗時減少，同時提取精度也得到了提高.算法流程為：

輸入：圖片序列組成的矩陣C

輸出：輸出x和y矩陣

1)初始化x，y，Z，令

γ∈(0，2)，β∈(0，1)，ε>0

2)更新包含運動目標的稀疏矩陣x

xk+1=argminxLβ(xk，yk；Zk)

3)對約束乘數Z第一次更新

4)更新包含背景的低秩矩陣y

5)對約束乘數Z第二次更新

6)計算停機準則ey

ey(yk+1，β) =yk+1-Py[yk+1-β(g(yk+1)-Zk+1)]

7)若矩陣x和y中變化率較大的都小于設定的臨界值max{‖xk+1-xk‖，‖ey(yk+1，β)‖}≤ε則算法結束，否則進行下一輪迭代.

4 實驗對比與分析

為了對上述改進的有效性進行驗證，實驗在提取精度、運行時間和迭代次數三方面與其它方法進行對比.實驗選取了廣泛使用的Wallflower[17]中的MovedObject(MO)，WavingTrees(WT)，TimeOfDay(TD)，Camouflage(C)，LightSwitch(LS)五個圖片數據集作為測試數據.該數據集是微軟研究員John Krumm等參與制作的，由于其包含的豐富場景對檢測提取算法的潛在問題具有很好的效果，所以該數據集在前背景提取實驗中廣泛采用，具有較高的權威性.

圖2 實驗效果對比Fig.2 Comparison of experimental result

實驗時分別從每個圖片數據集中取100張連續(xù)圖片P1,P2,P3…P100作為輸入數據，組成輸入矩C=matrix{P1,P2,P3…P100}陣.實驗選取EALM[7]、IALM[7]、MoG-RPCA[18]、FPCP[19]、R2PCP[20]和LSADM[10]算法進行對比實驗，同時對比中還加入了去掉均衡參數的試驗結果，以驗證均衡參數對提取精度的影響.

本文的實驗平臺是配置了Windows 7系統，CPU Intel(R)Core(TM) i7-4790 3.60GHz，內存8GB Dell臺式機，程序均用Matlab R2014b編程實現.

4.1 提取效果對比

在提取效果對比試驗中，本文選取了C 的第251幀，MO的第698幀，WT的第251幀，TD的第1850幀以及LS的第1865幀進行實驗效果展示，并分別將分解出的稀疏矩陣x進行二值化，對比效果如圖2所示.從圖2和不同方法的對比中可以看出，SADM都有很好的提取效果；對于五個不同的圖片數據集，SADM的提取效果也比較穩(wěn)定.

同時為了驗證均衡參數對提取精度的影響，本文將去掉均衡參數后的提取效果和SADM提取效果進行對比，結果如圖3所示.

圖3 均衡參數實驗效果對比Fig.3 Comparison of experimental results about equalizing parameter

通過對比結果可以發(fā)現，去掉均衡參數后，提取的目標中有更多噪聲或目標提取的不完全，這說明算法在分低秩和稀疏矩陣的分解上受到影響，使得運動目標的提取精度降低，這也驗證了均衡參數對提取精度的改善作用.

4.2 提取精度對比

為了對提取精度進行量化比較，本文采用Maddalena等[21]用到的F測度對結果進行量化，其計算公式為：

其中，

TP即為True Positive，FN為False Negative，FP為False Positive.本文中TP代表本來屬于運動目標，檢測結果也為運動目標的點；FN和FP依次類推.F測度對比柱狀圖如圖4所示，數據如表1所示.

圖4 F測度對比圖Fig.4 Comparison on F measure

從F測度對比結果來看，測試數據中SADM的效果基本都是最好的，而且整體效果相對其它方法有了很大的改進，從最后一行的均值可以發(fā)現，本文算法的平均值在對比的8種算法中是最高的，平均提高了33.04%.從F測度對比圖可以發(fā)現，SADM的F測度變化相對較小，說明它的魯棒性相比其它方法更好.

表1 F測度對比Table 1 Comparison on F measure

有無均衡參數的量化對比結果如表2所示.從表中可以看出，三個測試數據集的提取精度都是加入均衡參數的高，對比提取精度的均值會發(fā)現，加上均衡參數后比去掉的精度提高了11.91%.

表2 均衡參數結果量化對比Table 2 Comparison of precision quantification about equalizing parameter

4.3 運行時間對比

算法的運行時間對比數據如表3所示.從表中可以看出，相比原ADM算法，SADM運行時間平均縮短了98.8%.

在前文提到，收斂次數與運行時間有一定的關系，隨著收斂次數的減少，算法中最耗時的SVD過程也相應減少，從而使運行時間縮短.為了驗證這一點，實驗檢測了各個算法的迭代次數，數據如表4所示.從表3和表4的實驗結果可以看出，迭代次數較短的算法，其運行時間相對來說也比較短.SADM算法由于采用了新的迭代策略和停機準則，使算法的收斂速度加快，表3較短的運行時間和表4中SADM相對較少的收斂次數也驗證了這一點.

表3 運行時間對比(單位：秒)Table 3 Comparison on running time

表4 迭代次數對比Table 4 Comparison on iteration times

從這些對比實驗中可以發(fā)現，本文的運行時間和迭代次數相對于原ADM都有了很大提升，但在運行時間上，本文算法平均約32s不是最好的，這主要是因為SADM中加入了新的均衡參數，為了提高提取精度而犧牲了一定的運行時間.從表1和表3的實驗結果可以看出，運行時間較短的算法，其F測度相對來說比較低，這是因為如果時間過短，就會造成分解結果相對較差，反映在實驗結果上就是F測度比較低.而本文的方法在保證較短運行時間的同時，F測度也很高，對二者進行了一個很好的均衡.

5 結 語

本文提出了一種基于對稱交替方向魯棒主成分分析的運動目標提取算法，該方法在原ADM基礎上，通過改進算法的迭代方式和加入新的停機準則，使算法耗時減少，算法耗時相對原ADM提高了98.8%，同時通過加入新的均衡參數，使運動目標的提取精度平均提高了33.04%.但該方法在耗時方面還有提升空間，未來可在奇異值分解方法等方面繼續(xù)進行優(yōu)化.

：

[1] Cao X，Yang L，Guo X.Total variation regularized RPCA for irregularly moving object detection under dynamic background[J].IEEE Transactions on Cybernetics，2015，46(4)：1014-1027.

[2] Fang Shuai，Qu Cheng-jia，Yang Xue-zhi，et al.Linear prediction band selection based on optimal combination factors[J].Journal of Image and Graphics，2016，21(2)：255-262.

[3] Cai Nian，Zhou Yang，Liu Gen，et al.A survey：robust principal component analysis methods for moving object detection[J].Journal of Image and Graphics，2016，21(10) ：1265-1275.

[4] Candes E，Li X，Ma Y，et al.Robust principal component analysis[J].International Journal of ACM，2011，58(3)：1-73.

[5] Wright J，Peng Y，Ma Y，et al.Robust principal component analysis：exact recovery of corrupted low-rank matrices by convex optimization[J].Conference and Workshop on Neural Information Processing Systems，2009：2080-2088.

[6] Lin Z，Ganesh A，Wright J，et al.Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix[J].Journal of the Marine Biological Association of the UK，2009，56(3)：707-722.

[7] Lin Z，Liu R，Su Z，et al.Linearized alternating direction method with adaptive penalty for low-rank representation[J].Conference and Workshop on Neural Information Processing Systems，2011：612-620.

[8] Yuan X，Yang J.Sparse and low-rank matrix decomposition via alternating direction methods[J].Pacific Journal of Optimization，2013，9(1)：167-180.

[9] Zhang Min，Han De-ren，He Hong-jin，et al.A new alternating direction method for solving separable variational inequality problems[J].Scientia Sinica Mathematica，2012，42(2)：133-149.

[10] Glowinski R，Le Tallec P.Augmented lagrangian and operator-splitting methods in nonlinear mechanics[M].Society for Industrial and Applied Mathematics，Philadelphia，1989.

[11] Goldfarb D，Ma S，Scheinberg K.Fast alternating linearization methods for minimizing the sum of two convex function[J].Mathematical Programming，2009，141(1-2)：349-382.

[12] Ma S.Algorithms for sparse and low-rank optimization：convergence，complexity and applications[M].Thesis，2011.

[13] Douglas J，Rachford H H.On the numerical solution of heat conduction problem in 2 and 3 space variables[J].Transactions of the American Mathematical Society，1952，82(2)：421-439.

[14] Peaceman D H，Rachford H H.The numerical solution of parabolic elliptic differential equations[J].SIAM Journal on Applied Mathematics，2006，3(1)：28-41.

[15] M H Xu，T Wu.A class of linearized proximal alternating direction methods[J].Journal of Optimization Theory and Applications，2011，151(2)：321-337.

[16] Facchinei F，Pang J S.Finite-dimensional variational inequalities and complementarity problems[M].Berlin：Operations Research,Springer，2003.

[17] Toyama K，Krumm J，Brumitt B，et al.Wallflower：principles and practice of background maintenance[J].IEEE International Conference on Computer Vision，1999，1(1)：255-261.

[18] Zhao Q，Meng D，Xu Z，et al.Robust principal component analysis with complex noise[J].International Conference on Machine Learning，2014：55-63.

[19] Rodriguez P，Wohlberg B.Fast principal component pursuit via alternating minimization[J].IEEE International Conference on Image Processing，2014：69-73.

[20] Hintermüller M，Wu T.Robust principal component pursuit via inexact alternating minimization on matrix manifolds[J].Journal of Mathematical Imaging and Vision，2014，51(3)：361-377.

[21] Maddalena L，Petrosino A.A fuzzy spatial coherence-based approach to background foreground separation for moving object detection[J].Neural Computing and Applications，2010，19(2)：179-186.

附中文參考文獻：

[2] 方 帥，瞿成佳，楊學志，等.組合因子最優(yōu)的線性預測波段選擇[J].中國圖象圖形學報，2016，21(2)：255-262.

[3] 蔡 念，周 楊，劉 根，等.魯棒主成分分析的運動目標檢測綜述[J].中國圖象圖形學報，2016，21(10)：1265-1275.

[9] 張 敏，韓德仁，何洪津，等.解可分離結構變分不等式的一種新的交替方向法[J].中國科學：數學，2012，42(2)：133-149.