穩(wěn)健pca在計(jì)算機(jī)視覺(jué)中的應(yīng)用

穩(wěn)健pca在計(jì)算機(jī)視覺(jué)中的應(yīng)用

0基于快速交替方向乘子法的mr凸規(guī)劃當(dāng)前壓縮感知。其中,f:R壓縮感知中信號(hào)恢復(fù)是用l其中,ρ>0,那么當(dāng)穩(wěn)健PCA問(wèn)題其中,ρ>0,M∈R凸規(guī)劃為了有效解決大規(guī)模的穩(wěn)健PCA應(yīng)用問(wèn)題,本文研究快速交替方向乘子法(FastAlternatingDirectionMethodsofMultipliers,FADMM)。本方法先用Nesterov平滑方法1快速交替乘數(shù)法1.1增廣拉格朗日乘子法增廣拉格朗日乘子法在ALM的基礎(chǔ)上,首先加入輔助變量,使變量x分裂為兩個(gè)變量,表示為x,y,則式(1)可寫(xiě)為:設(shè)懲罰參數(shù)為1/μ,則增廣拉格朗日乘子法的目標(biāo)函數(shù)為:關(guān)于x,y的子問(wèn)題如下:對(duì)應(yīng)的拉格朗日乘子更新準(zhǔn)則:重復(fù)這兩個(gè)步驟直到滿足終止條件,得到的解即為約束優(yōu)化問(wèn)題式(5)的最優(yōu)解。1.2交替更新思想下的x、y交替方向乘子法(ADMM)是增廣拉格朗日乘子法(ALM)的變種,在引入ALM中乘子函數(shù)的同時(shí),針對(duì)極小化x,y的困難,引入交替更新思想,固定其它變量,交替最小化變量x,y。那么式(7)就可以改寫(xiě)為:拉格朗日乘子更新準(zhǔn)則不變,具體算法如下:1.3求解近似平滑思想在解決形如式(1)的優(yōu)化問(wèn)題時(shí),往往f(x)和g(x)都是非平滑的,對(duì)于此類問(wèn)題,常規(guī)的ALM、ADMM是無(wú)法解決的。所以本文引入Nesterov近似平滑思想如壓縮感知中l(wèi)其中,z所以gg(x)平滑后,可求解如下的近似平滑函數(shù):為了求解式(2)問(wèn)題,引入如下有關(guān)ε最優(yōu)解的定理定理1假設(shè)證畢由定理1,通過(guò)求解式(13)的ε/2最優(yōu)解,來(lái)得到式(2)的最優(yōu)解。在函數(shù)近似平滑后,針對(duì)ALM、ADMM收斂速度慢的特點(diǎn),為了提高收斂速度,引入FISTA第二次更新λ:并在兩次更新之間加入快速算子FADMM不僅利用當(dāng)前點(diǎn)的信息α2fadm算法求解形如式將FADMM應(yīng)用于穩(wěn)健PCA問(wèn)題時(shí),需要函數(shù)都是凸函數(shù),且是平滑函數(shù)。所以,首先平滑式(2)中的f(X)∶=‖X‖*和g(Y)同理,f(X)∶=‖X‖其中,Wf(X)和g(Y)函數(shù)平滑處理后,就可以應(yīng)用FADMM法解決形如式(20)的問(wèn)題:兩個(gè)子問(wèn)題的迭代公式如下:式(21)的一階優(yōu)化條件是:那么:X∶=UDiag(γ)V令B∶=μW因此式(22)的一階優(yōu)化條件是:則兩個(gè)子問(wèn)題X,Y就很容易通過(guò)本文方法求解。3合成數(shù)據(jù)的穩(wěn)健pca仿真本節(jié)實(shí)驗(yàn)的運(yùn)行平臺(tái)為matlab7.8,CPU為IntelCore2,2GB內(nèi)存,Windows7系統(tǒng)的筆記本。3.1節(jié)介紹合成數(shù)據(jù)的穩(wěn)健PCA仿真;3.2節(jié)給出穩(wěn)健PCA的視頻背景建模實(shí)驗(yàn)。3.1算法的恢復(fù)性檢驗(yàn)本節(jié)利用合成數(shù)據(jù),比較ADMM和FADMM兩種算法對(duì)穩(wěn)健PCA求解的有效性。考慮到視頻背景建模應(yīng)用,所有矩陣維數(shù)取得較大,本次仿真實(shí)驗(yàn)分別考慮m=n=500和1000兩種情況,且對(duì)于稀疏性,只考慮脈沖稀疏矩陣。令M=(X用r和spr分別表示低秩矩陣的秩和稀疏矩陣的稀疏率。實(shí)驗(yàn)表明,無(wú)論兩者中任何一個(gè)相對(duì)較小,算法都能恢復(fù)精確的低秩矩陣。算法中參數(shù)t和μ的選擇:(1)參數(shù)t選取:考慮分解矩陣要有好的稀疏性和低秩性,t選取范圍為0.03至0.06,就能保證恢復(fù)低秩矩陣的正確率,所以設(shè)置參數(shù)t=0.05。(2)參數(shù)μ選取:當(dāng)μ選擇偏大或偏小時(shí),算法需要更多次迭代,所以設(shè)μ=‖sign(M)‖/1.25。算法的迭代終止規(guī)則為:定義低秩矩陣相對(duì)誤差ErrLR和稀疏矩陣相對(duì)誤差ErrSP如下:仿真結(jié)果如表1所示。表1中FADMM的低秩矩陣相對(duì)誤差,稀疏矩陣相對(duì)誤差和實(shí)際相對(duì)誤差都穩(wěn)定在數(shù)量級(jí)10因此,可以證明本文提出的FADMM明顯優(yōu)越于ADMM算法。3.2基于時(shí)分復(fù)用的svp本節(jié)實(shí)驗(yàn)研究從視頻監(jiān)控中提取視頻背景。雖然視頻中的前景是運(yùn)動(dòng)變化的,但是此類問(wèn)題仍舊可以歸結(jié)為求解穩(wěn)健PCA的問(wèn)題。通過(guò)把視頻中每一幀列向量化,得到一個(gè)矩陣M。這個(gè)矩陣可以被分解成兩個(gè)矩陣的和:本節(jié)分別使用經(jīng)典的ALM、ADMM和本文提出的FADMM來(lái)解決視頻背景建模問(wèn)題,并對(duì)3種方法的優(yōu)劣性進(jìn)行對(duì)比分析。測(cè)試視頻序列為機(jī)場(chǎng)監(jiān)控視頻:Hall_airport,數(shù)據(jù)為200幀,分辨率為144×176,由其構(gòu)造的觀測(cè)矩陣M大小為25344×200。初始點(diǎn)設(shè)置(X算法迭代過(guò)程奇異值分解采用MATLAB自帶的[U,S,V]=SVD(X,‘econ’),沒(méi)有采用第三方軟件包。求解式(21)時(shí)無(wú)需計(jì)算整體SVD,只要計(jì)算大于閾值根據(jù)文獻(xiàn)[9]中建議,設(shè)置sv其中,d=min{m,n},svp如圖1和圖2所示,分別是使用ALM(第一行),ADMM(第二行)和FADMM(第三行)的視頻前景背景分離的對(duì)比圖。其中第一列表示原始視頻幀,第二列表示分離出的背景圖像,第三列表示分離出的前景圖像。圖1為視頻第30幀對(duì)比圖,圖2為視頻第100幀對(duì)比圖。表2所示是這3種算法在運(yùn)行時(shí)間和迭代次數(shù)上的對(duì)比。從圖1,圖2可以看出FADMM可將運(yùn)動(dòng)前景有效地從背景中分離出來(lái),與ALM、ADM相比視頻背景圖像中前景陰影較少,圖像清晰度高。表2所示的是3種算法效率對(duì)比,可看出FADMM無(wú)論是在奇異值分解的次數(shù),還是CPU計(jì)算時(shí)間,都優(yōu)于其它兩種方法。實(shí)驗(yàn)結(jié)果表明,FADMM用于實(shí)際背景建模具有很好的效果。其在CPU運(yùn)行時(shí)間以及迭代次數(shù),明顯優(yōu)于ADMM和ALM。所以在解決形如式(20)的穩(wěn)健PCA的問(wèn)題,相比其它兩種算法,FADMM可以更準(zhǔn)確恢復(fù)低秩矩陣,即能從視頻中提取前景運(yùn)動(dòng)目標(biāo)和構(gòu)建低秩背景模型。4fadm算法性能分析本文針對(duì)經(jīng)典ADMM不能解決非平滑函數(shù)的求解問(wèn)題,首先引入Nesterov平滑處理方法,對(duì)非平滑函數(shù)進(jìn)行近似平滑處理。本文提出了FADMM,即在ADMM的基礎(chǔ)上引入快速算子,加速迭代效率,提高收斂速度,并將其應(yīng)用于穩(wěn)健PCA問(wèn)題。本文基于合成數(shù)據(jù)仿真和視頻背景建模實(shí)驗(yàn),仿真實(shí)驗(yàn)結(jié)果表明,FADMM無(wú)論是在算法的收斂速度還是迭代次數(shù)上都明顯優(yōu)越于ADMM,具有更好的魯棒性。對(duì)于FADMM在壓縮感知等領(lǐng)