李 俊,周薇娜(上海海事大學(xué)信息工程學(xué)院,上海201306)
?
基于低秩矩陣恢復(fù)的目標(biāo)快速檢測(cè)方法研究
李俊,周薇娜
(上海海事大學(xué)信息工程學(xué)院,上海201306)
摘 要:為了實(shí)現(xiàn)快速運(yùn)動(dòng)目標(biāo)檢測(cè),利用低秩矩陣恢復(fù)原理進(jìn)行視頻前景檢測(cè),主要針對(duì)低秩矩陣恢復(fù)算法存在的耗費(fèi)大部分運(yùn)算時(shí)間且運(yùn)算較為復(fù)雜的奇異值分解問(wèn)題,應(yīng)用統(tǒng)一計(jì)算結(jié)構(gòu)裝置(CUDA)第三方庫(kù)實(shí)現(xiàn)加速計(jì)算奇異值分解的低秩矩陣恢復(fù)算法優(yōu)化,得到快速且高效的前景檢測(cè)方法?;陂_源視頻序列實(shí)驗(yàn),與原有的低秩矩陣恢復(fù)算法進(jìn)行各項(xiàng)參數(shù)的比較,其中加速倍數(shù)達(dá)一倍以上。實(shí)驗(yàn)結(jié)果證明,經(jīng)過(guò)優(yōu)化的算法運(yùn)算時(shí)間變短,具有更高效率。
關(guān)鍵詞:低秩矩陣恢復(fù);前景檢測(cè);統(tǒng)一計(jì)算結(jié)構(gòu)裝置
目標(biāo)檢測(cè)是把視頻序列中感興趣的目標(biāo)分割出來(lái),作為許多視覺應(yīng)用中最基礎(chǔ)的部分,深入探討其相關(guān)算法研究以提高其檢測(cè)性能與精度,顯得相當(dāng)重要。傳統(tǒng)目標(biāo)檢測(cè)算法計(jì)算較為復(fù)雜,檢測(cè)精度相對(duì)較低,性能也較低下。隨著計(jì)算機(jī)技術(shù)的高速發(fā)展,所拍攝的視頻序列圖像分辨率也越來(lái)越高,這使得視頻序列中圖像數(shù)據(jù)量過(guò)大和數(shù)據(jù)維數(shù)過(guò)高,增加目標(biāo)檢測(cè)計(jì)算難度。對(duì)高維數(shù)據(jù)降維,用降維得到的低維數(shù)據(jù)表征原有的高維數(shù)據(jù)從而降低數(shù)據(jù)計(jì)算復(fù)雜度成了視頻圖像數(shù)據(jù)處理的重要方法。主成分分析(Principal Component Analysis,PCA)是一種很有效的分析高維數(shù)據(jù)的工具,把高維數(shù)據(jù)投影到低維空間,奇異值分解(Singular Value Decomposition,SVD)使得PCA有了穩(wěn)定高效的計(jì)算能力,但當(dāng)矩陣元素受到嚴(yán)重破壞時(shí),PCA則對(duì)矩陣估計(jì)不準(zhǔn)確。為了改善PCA對(duì)這種情況的處理,CANDES E J提出了魯棒主成分分析[1](Robust Principle Component Analysis,RPCA),也稱低秩矩陣恢復(fù)[2],指元素受到嚴(yán)重破壞的矩陣也得以恢復(fù)。
一般說(shuō)來(lái)由視頻數(shù)據(jù)構(gòu)造成的觀測(cè)矩陣可以分解為稀疏和低秩兩個(gè)矩陣,矩陣恢復(fù)時(shí)可以用凸優(yōu)化的方法,視頻前景檢測(cè)擬合這種分解特性。前景檢測(cè)是從拍攝的視頻中分離出背景和前景,由于視頻的背景基本是不變的,因此如果把每幀當(dāng)做矩陣的各列,那么此矩陣將是低秩的,低秩矩陣恢復(fù)可以同時(shí)完成背景和前景分離,得到的前景即為需要檢測(cè)的目標(biāo)。
低秩矩陣恢復(fù)算法運(yùn)行在MATLAB平臺(tái)上,MATLAB雖易用性強(qiáng),但是有著計(jì)算慢、效率低等缺點(diǎn)。經(jīng)過(guò)對(duì)算法和CUDA[3]深入分析,使用MATLAB和C++的MEX混合編程,進(jìn)行了在MATLAB內(nèi)調(diào)用CUDA第三方庫(kù)加速原有算法的運(yùn)算,經(jīng)加速優(yōu)化后,低秩矩陣恢復(fù)前景檢測(cè)方法效率更高。最后基于真實(shí)數(shù)據(jù)實(shí)驗(yàn),進(jìn)行經(jīng)過(guò)優(yōu)化后的算法與原算法各項(xiàng)參數(shù)的比較。
觀測(cè)得到的數(shù)據(jù)組成的數(shù)據(jù)矩陣D秩一般很低,為了恢復(fù)它的低秩結(jié)構(gòu),把矩陣D分解成一個(gè)低秩矩陣和一個(gè)稀疏矩陣的和,即D=A+E,A未知是低秩的,E也未知是稀疏的。當(dāng)矩陣E的元素服從獨(dú)立同分布的高斯分布時(shí),PCA可解SVD得到最優(yōu)的矩陣A,即求解下面的最優(yōu)化問(wèn)題:
其中,‖.‖F(xiàn)為F范數(shù),c為子空間維數(shù)。當(dāng)E不理想時(shí),經(jīng)典PCA對(duì)A的估計(jì)就相當(dāng)不準(zhǔn),WRIGHT J等人提出的RPCA很好地解決了上述問(wèn)題。
同PCA一樣,RPCA的問(wèn)題可描述為:觀察數(shù)據(jù)矩陣D為已知,D=A+E,A、E未知,A為低秩的,但是E稀疏且非零元素E可能無(wú)限大,要從中恢復(fù)出A,需得到觀察數(shù)據(jù)D的最小的秩,且干擾誤差是稀疏的。通過(guò)以下優(yōu)化問(wèn)題來(lái)描述:
該問(wèn)題也被稱之為主成分追蹤(Principal Component Pursuit,PCP),在一定條件下,求解式(3)可以得到理想且唯一的A和E。將以上的凸優(yōu)化問(wèn)題稱為RPCA,該方程式在實(shí)際應(yīng)用中性能良好,能從高達(dá)1 /3嚴(yán)重腐蝕的觀測(cè)值中恢復(fù)真實(shí)的低秩矩陣,并且具有優(yōu)秀的理論保證。例如,對(duì)一般的矩陣A,它可以顯示成功糾正錯(cuò)誤恒比,甚至當(dāng)A的秩是近似地正比于環(huán)境度:rank(A)=Cm/log (m)。參考文獻(xiàn)[1]也給出了結(jié)論定理:如果A0為n×n矩陣,其秩rank(A0)≤ρrnμ-1·(log n)-2,E0是隨機(jī)稀疏的n×n矩陣,基數(shù)m≤ρsn2ρrρs,其中ρr為低秩率,ρs為稀疏率,當(dāng)時(shí),PCP能夠準(zhǔn)確恢復(fù)出的概率為1 -O(n-10)。對(duì)于任意矩形矩陣,對(duì)λ=1 /有與上相同的結(jié)論。
前景檢測(cè)是把目標(biāo)由視頻里提取出來(lái)。因?yàn)橐曨l的背景基本是不變的,假設(shè)視頻有n幀圖像,把每幀當(dāng)做矩陣D每一列,由每幀圖像的像素構(gòu)成的m維列向量作為矩陣D每一行,得到大小為m×n低秩矩陣D,因此可用低秩矩陣恢復(fù)來(lái)恢復(fù)出背景。低秩矩陣A可作為視頻中有很大相關(guān)性的背景部分,稀疏矩陣E則可作為分布稀疏的前景部分也即感興趣的目標(biāo)。
有許多方法可求解RPCA問(wèn)題[4-7],本文對(duì)非精確增廣拉格朗日乘子法(IALM)中的奇異值分解計(jì)算進(jìn)行加速優(yōu)化,使得能夠加速計(jì)算奇異值分解,算法運(yùn)算效率提升,運(yùn)行時(shí)間縮減。
構(gòu)造增廣拉格朗日函數(shù):
其中,Y∈Rm×n為約束乘子,μ>0為懲罰參數(shù),[·]表示計(jì)算內(nèi)積,‖·‖F(xiàn)表示F范數(shù)。每一步最小化式(4)時(shí)使用輪流更新的方法,先保持Y與E不變,求得使L最小的A,然后保持Y與A不變,求使L最小的E,這樣迭代次數(shù)就可收斂到這個(gè)子問(wèn)題的最優(yōu)解。更新A時(shí):
更新E時(shí):
輪流更新,直到對(duì)子問(wèn)題求解收斂時(shí)為止,該算法被稱為精確增廣拉格朗日乘子法(EALM),見算法1[4,8]。
算法1
(2)while not converged do
(4)while not converged do
(8)j=j+1
(9)end while
(11)k=k+1
(12)end while
稱算法1為精確增廣拉格朗日乘子法,原因在于最外層的循環(huán)并不需要求出子問(wèn)題的精確解,事實(shí)上,只要將A和E都更新一次得子問(wèn)題的一個(gè)近似解,這樣得到的最優(yōu)解就可使算法收斂到原問(wèn)題,因此可以得到簡(jiǎn)潔且收斂更快的算法——IALM,見算法2[4,8]。
算法2
(1)初始化Y0,E0,μ0,k=0
(2)while not converged do
(7)更新μk
(8)k=k+1
(9)end while
以上算法會(huì)耗費(fèi)大量時(shí)間計(jì)算奇異值分解,所以找到快速處理奇異值分解計(jì)算的方法,對(duì)于整個(gè)算法的執(zhí)行效率將會(huì)大有改善。本文基于CUDA架構(gòu)第三方CULA[9 -10]庫(kù)在MATLAB中實(shí)現(xiàn)加速優(yōu)化算法中奇異值分解的計(jì)算。MATLAB中CUDA加速的原理為:CPU執(zhí)行流程控制的操作代碼,一些需要并行運(yùn)算的操作代碼放在GPU中處理,這樣算法運(yùn)算時(shí)間將大幅度減少。CUDA計(jì)算的流程如圖1所示。
圖1 CUDA計(jì)算流程圖
經(jīng)過(guò)仔細(xì)閱讀CULA參考手冊(cè)和CULA編程指南,分析低秩矩陣恢復(fù)算法,編寫可以在MATLAB里面通過(guò)一些接口使用CULA庫(kù)加速的culaSvd mex源文件。首先,需要在MATLAB里面處理多種CULA的數(shù)據(jù)類型,MATLAB和CULA支持的4個(gè)主要的數(shù)據(jù)類型為:?jiǎn)尉葘?shí)數(shù)、雙精度實(shí)數(shù)、單精度復(fù)數(shù)和雙精度復(fù)數(shù)。由于MATLAB MEX編譯器與CULA支持C++語(yǔ)言,可以通過(guò)代碼來(lái)實(shí)現(xiàn)數(shù)據(jù)類型的處理,用C++模板來(lái)處理所有的4個(gè)MATLAB數(shù)據(jù)類型,使用MATLAB函數(shù)mxGetClassID()和mxIsComplex()確定輸入矩陣的精度和復(fù)雜度。上述代碼主要包括3個(gè)部分,SVD函數(shù)的CULA頭文件和MATLAB數(shù)據(jù)類型和接口的頭文件、支持4種MATLAB數(shù)據(jù)類型的模板函數(shù)、在MATLAB中調(diào)用的C++模板所需要的網(wǎng)關(guān)函數(shù)。其次,因?yàn)镃ULA和MATLAB以不同的類型存儲(chǔ)復(fù)雜的數(shù)據(jù),創(chuàng)建helper函數(shù),實(shí)現(xiàn)兩個(gè)類型之間的轉(zhuǎn)換。創(chuàng)建好helper函數(shù)后,通過(guò)查閱CULA的xGESVD函數(shù)的文檔可以發(fā)現(xiàn),MATLAB中對(duì)角陣返回奇異值,而CULA返回一個(gè)向量,MATLAB返回V,而CULA返回V的轉(zhuǎn)置,為了對(duì)接MATLAB的接口,必須從奇異值向量轉(zhuǎn)換成一個(gè)對(duì)角矩陣并轉(zhuǎn)置。至此完成了culaSvd程序,在MATLAB中用MEX命令編譯culaSvd.cpp源文件生成二進(jìn)制mex文件,完成MATLAB中實(shí)現(xiàn)在底層調(diào)用經(jīng)CULA加速優(yōu)化后的奇異值分解。
本節(jié)將原有算法與基于CUDA優(yōu)化后的算法進(jìn)行運(yùn)行效果比較,測(cè)試是基于拍攝的真實(shí)數(shù)據(jù)進(jìn)行的,試驗(yàn)運(yùn)行環(huán)境配置為:Intel Core i5 M 520 2.40 GHz CPU,4 GB內(nèi)存,Nvidia公司的GT218 GPU,編程環(huán)境為MATLAB R2010a+Visual Studio 2010 +CUDA Toolkit Version 4.0 + CULA R12,選取的視頻是拍攝的學(xué)校路口某個(gè)時(shí)刻的場(chǎng)景。視頻序列總共為200幀,每幀大小為576 768,由此組成的觀測(cè)矩陣為M(27 648×200)。
圖2為選取的第150幀3種算法運(yùn)行效果對(duì)比圖。表1為取150幀進(jìn)行前景檢測(cè),兩種算法及其加速改進(jìn)后算法
圖2 第180幀3種算法仿真對(duì)比圖
的運(yùn)算時(shí)間、迭代次數(shù)、SVD時(shí)間及SVD次數(shù)的比較。
表1 三種算法150幀仿真數(shù)據(jù)的比較
表2為分別取180幀、160幀、140幀、120幀、100幀和80幀進(jìn)行前景檢測(cè),為了得到精確運(yùn)行時(shí)間,分別進(jìn)行100次運(yùn)算,然后取平均運(yùn)行時(shí)間,計(jì)算算法的運(yùn)行時(shí)間、平均加速倍數(shù)。對(duì)視頻進(jìn)行處理,將其裁剪為不同分辨率的視頻,對(duì)其進(jìn)行測(cè)試,表3為分別采用不同分辨率進(jìn)行視頻測(cè)試時(shí)兩種算法的運(yùn)行時(shí)間及其加速倍數(shù)。
表2 IALM算法與基于CULA優(yōu)化后算法不同視頻幀數(shù)仿真數(shù)據(jù)比較
從仿真效果可以看出,經(jīng)CULA優(yōu)化后的算法分離出的背景A3比其他兩種原有的算法得到的背景A1和背景A2相比,前景目標(biāo)更加分明,前景目標(biāo)檢測(cè)效果更好。
表3 IALM算法與基于CULA優(yōu)化后算法不同分辨率視頻仿真數(shù)據(jù)比較
表1表明,優(yōu)化改進(jìn)后的算法運(yùn)行效率有所提升。表2取不同的視頻幀數(shù)進(jìn)行前景目標(biāo)檢測(cè),表明實(shí)現(xiàn)了至少1倍以上加速比。最后表3給出了不同測(cè)試視頻的運(yùn)行結(jié)果,表明隨著圖像尺寸的加大,加速比增大。綜合得知,本文的優(yōu)化改進(jìn)算法效率更高。
本文應(yīng)用CULA加速優(yōu)化后的低秩矩陣恢復(fù)算法實(shí)現(xiàn)前景目標(biāo)檢測(cè),加速優(yōu)化后的算法與原有算法相比,奇異值分解次數(shù)減少,表明算法里的奇異值分解計(jì)算得到加速改進(jìn),因此算法的運(yùn)行時(shí)間得以較大幅度縮短。仿真結(jié)果表明,本文加速優(yōu)化后的算法有更好的前景目標(biāo)檢測(cè)效率。本文的前景目標(biāo)檢測(cè)算法在計(jì)算效率上得到改善,發(fā)揮了軟硬件結(jié)合的效果,這種學(xué)習(xí)成本低廉、使用代價(jià)較小、運(yùn)行效率較高的優(yōu)點(diǎn)彌補(bǔ)了MATLAB計(jì)算速度上的缺點(diǎn),也使得視覺應(yīng)用的研究有了良好的開端。
參考文獻(xiàn)
[1]CANDES E J,Li Xiaodong,Ma Yi,et al.Robust principalcomponent analysis[J].Journal of the ACM,2009,58(3):233-279.
[2]WRIGHT J,GANESH A,RAO S,et al.Robust principal component analysis:exact recovery of corrupted low-rank matrices via convex optim ization[C].Proceedings of Neural Information Processing Systems(NIPS),2009,87(4):20:3-20:56.
[3]NVIDIA Corporation.NVIDIA CUDA programming guide[Z]. 2009.
[4]Lin Zhouchen,Chen Minming,Ma Yi.The augmented Lagrange multip liermethod for exact recovery of a corrupted low-rank matrix[R].Eprint Arxiv,2010.
[5]GANESH A,Lin Zhouchen,WRIGHT J,et al.Fast algorithms for recovering a corrupted low-rank matrix[C].International Workshop on Computational Advances in Multi-Sensor Adaptive Processing,2009:213-216.
[6]Lin Zhouchen,GANESH A,WRIGHT J,et al.Fast convex optim ization algorithms for exact recovery of a corrupted low-rank matrix[C].Proceedings of Computational Advances in Multi-Sensor Adaptive Processing(CAMSAP),2009.
[7]YUAN X,YANG J.Sparse and low-rank matrix decomposition via alternating direction methods[R].Hong Kong:Hong Kong Baptist University,2009.
[8]Chen M inm ing.Algorithms and implementations ofmatrix reconstruction[D].Beijing:Graduate School Chinese Academy of Science,2010.
[9]EM Photonics Corporation.CULA reference guide[Z].2014.
[10]EM Photonics Corporation.CULA programmers guide[Z]. 2014.
李?。?992 -),男,碩士研究生,主要研究方向:圖像處理與模式識(shí)別。
周薇娜(1982 -),通信作者,女,博士,講師,主要研究方向:圖像處理,集成電路設(shè)計(jì)。E-mail:wnzhou@shm tu.edu.cn。
引用格式:李俊,周薇.娜基于低秩矩陣恢復(fù)的目標(biāo)快速檢測(cè)方法研究[J].微型機(jī)與應(yīng)用,2016,35(10):75-78.
Fast object detection based on low-rank matrix recovery theory
Li Jun,Zhou Weina
(College of Information Engineering,Shanghai Maritime University,Shanghai201306,China)
Abstract:In order to implement fastmoving object detection,foreground detection is completed by using low-rank matrix recovery algorithm. As the main computation of low-rank matrix recovery algorithm is the singular value decomposition,most of which is time-consuming and complex,a fast and efficient foreground detection method is obtained by applying the compute unified device architecture(CUDA)and its thirdparty library to realize the low-rank matrix recovery optimized algorithm which implements the faster computing of singular value decomposition. We test our algorithm on open source video and compare itwith original low-rank matrix algorithm on various parameters,and the acceleration ratio achievesmore than one times.The experiment result indicates that the optimized algorithm obtains less running time and ismore efficient.
Key w ords:low-rank matrix recovery;foreground detection;compute unified device architecture
作者簡(jiǎn)介:
收稿日期:(2016-01-23)
中圖分類號(hào):TP312
文獻(xiàn)標(biāo)識(shí)碼:A
DOI:10.19358 /j.issn.1674-7720.2016.09.026