矩陣的低秩稀疏表達(dá)在視頻目標(biāo)分割中的研究

顧 菘，馬 爭(zhēng)，解 梅

?

矩陣的低秩稀疏表達(dá)在視頻目標(biāo)分割中的研究

顧 菘1,2，馬 爭(zhēng)1，解 梅3

(1. 電子科技大學(xué)通信與信息工程學(xué)院 成都 611731；2. 成都航空職業(yè)技術(shù)學(xué)院航空工程學(xué)院 成都 610100； 3. 電子科技大學(xué)電子工程學(xué)院 成都 611731)

提出了一種視頻目標(biāo)跟蹤與分割的在線算法。該算法將每幀圖像中的超級(jí)像素作為一個(gè)數(shù)據(jù)點(diǎn)，根據(jù)已知的目標(biāo)和背景建立模板，當(dāng)前幀中待分割的目標(biāo)可以看成已知模板的稀疏線性表達(dá)。根據(jù)此線性表達(dá)的系數(shù)可以建立描述當(dāng)前幀與模板的相似性矩陣，即表達(dá)子。由于視頻圖像的連續(xù)性，表達(dá)子具有低秩和稀疏的特征。因此通過求解矩陣的低秩稀疏的優(yōu)化問題可以得到當(dāng)前幀中所有數(shù)據(jù)點(diǎn)屬于目標(biāo)的概率分布。為了獲得基于像素級(jí)的分割結(jié)果，通過能量最小框架，并利用圖分割的方法最終實(shí)現(xiàn)目標(biāo)的分割。實(shí)驗(yàn)結(jié)果表明該算法具有良好的分割效果。

能量最小; 圖分割; 低秩; 稀疏; 視頻目標(biāo)分割

基于視頻的目標(biāo)分割(video object segmentation)不僅能夠跟蹤目標(biāo)的位置，還能精確地描述目標(biāo)的形狀。它可以看成是目標(biāo)的精確跟蹤。視頻目標(biāo)分割的關(guān)鍵在于時(shí)間一致性(temporal coherence)和空間一致性(spatial coherence)的表達(dá)。時(shí)間一致性描述了在連續(xù)幀中目標(biāo)的相似性，空間一致性描述了在一幀圖像中目標(biāo)與背景的分辨能力。文獻(xiàn)[1-2]提出了基于水平集(level set)的分割算法。這種算法的缺點(diǎn)在于將運(yùn)動(dòng)估計(jì)與分割過程分別獨(dú)立，將運(yùn)動(dòng)估計(jì)的結(jié)果作為分割的輸入。這樣當(dāng)運(yùn)動(dòng)估計(jì)不準(zhǔn)確時(shí)，會(huì)影響分割的精度。建立能量函數(shù)，利用能量最小化的方法進(jìn)行目標(biāo)分割是當(dāng)前比較流行的方法。文獻(xiàn)[3-6]分別利用目標(biāo)的運(yùn)動(dòng)模型、顏色紋理等信息建立了不同的能量函數(shù)。這種方法的優(yōu)點(diǎn)在于能夠?qū)r(shí)間與空間信息利用概率模型融合在一起，最終獲得較好的分割效果。文獻(xiàn)[3-4]通過對(duì)某些關(guān)鍵幀中已知目標(biāo)的學(xué)習(xí)，提出了一種離線算法。文獻(xiàn)[5]利用深度攝像機(jī)獲得了目標(biāo)的深度信息。但這些方法都大大限制了其應(yīng)用范圍。文獻(xiàn)[6]利用目標(biāo)的顏色信息建立了3D條件隨機(jī)場(chǎng)模型(conditional random field)。但由于其信息量較少，分割精度不高。本文也將利用能量最小的框架結(jié)構(gòu)，創(chuàng)建新的能量函數(shù)，只需要較少的已知信息就能夠進(jìn)行視頻目標(biāo)的在線分割。

另一方面，本文將視頻目標(biāo)分割看作一種目標(biāo)跟蹤算法，將目標(biāo)的分割轉(zhuǎn)化成矩陣的低秩稀疏表達(dá)。近年來，矩陣的低秩稀疏表達(dá)已經(jīng)被廣泛應(yīng)用在目標(biāo)跟蹤上。文獻(xiàn)[7]提出了一種L1范數(shù)模型，將目標(biāo)作為模板集的稀疏表達(dá)形式，實(shí)現(xiàn)了目標(biāo)的在線跟蹤。文獻(xiàn)[8]提出了基于粒子濾波的跟蹤算法，將對(duì)目標(biāo)的跟蹤轉(zhuǎn)化為矩陣低秩稀疏的優(yōu)化問題。

本文提出一種基于區(qū)域的在線目標(biāo)視頻分割算法。首先將圖像過分割(over segmentation)成超級(jí)像素(superpixel)，將超級(jí)像素作為數(shù)據(jù)點(diǎn)，這不僅濾除了不必要的細(xì)節(jié)特征，而且可以大大簡(jiǎn)化計(jì)算量。然后根據(jù)上一幀的分割結(jié)果建立模板集，將當(dāng)前幀所有數(shù)據(jù)點(diǎn)看作模板集的稀疏線性組合。將目標(biāo)分割問題轉(zhuǎn)化為矩陣的低秩稀疏的優(yōu)化問題。根據(jù)計(jì)算出的線性組合系數(shù)矩陣建立當(dāng)前幀中每個(gè)超級(jí)像素的概率分布。最后將此概率分布作為能量函數(shù)的一個(gè)線索(cue)，結(jié)合其他基本信息，構(gòu)建出新的能量函數(shù)，利用能量最小化求得最終的結(jié)果。此外，由于超級(jí)像素的形狀不規(guī)則，本文將采用L2ECM[9](local log-euclidean covariance matrix)算法提取其特征。

1 特征提取

基于區(qū)域的分割算法已經(jīng)被廣泛應(yīng)用。本文將超級(jí)像素[10]作為一個(gè)數(shù)據(jù)點(diǎn)進(jìn)行圖像的分割。這種方法不僅能夠大大地減少計(jì)算的數(shù)據(jù)量，而且超級(jí)像素本身已經(jīng)將某些相似的像素聚集在一起，濾除了大量的細(xì)節(jié)噪聲，增加了算法的魯棒性?？紤]到超級(jí)像素形狀的不規(guī)則性，本文采用L2ECM算法提取其特征。在一幅圖像中，一個(gè)像素的基本特征可以表示為：

(1)

2 低秩稀疏表達(dá)

文獻(xiàn)[12-14]均提出了基于區(qū)域的圖像(視頻)分割算法，它們的基本思想是一幅圖像中的元素可以用其他的元素進(jìn)行線性表達(dá)。結(jié)合文獻(xiàn)[8]，本文將目標(biāo)分割轉(zhuǎn)化為矩陣的低秩稀疏表達(dá)問題進(jìn)行求解。

2.1 模板的建立

2.2 低秩稀疏表達(dá)

式中，的每一列表示的對(duì)應(yīng)列用進(jìn)行線性表達(dá)的系數(shù)，矩陣稱之為表達(dá)子。對(duì)應(yīng)于被分解成和，表達(dá)子。為由于噪聲引起的誤差，如圖1所示。

圖1 線性表達(dá)關(guān)系示意圖(視頻圖像參考文獻(xiàn)[2])

從圖1中可以看出：

3) 根據(jù)文獻(xiàn)[7-8]可知，圖像中的噪聲可以用稀疏模型進(jìn)行擬合。因此也應(yīng)為稀疏矩陣。

通過以上3點(diǎn)，可以得出式(2)的最優(yōu)解為：

(3)

2.3 式(3)的求解

根據(jù)文獻(xiàn)[15]，添加約束條件使變量獨(dú)立，將式(3)轉(zhuǎn)化為(為了表達(dá)清晰，以下將簡(jiǎn)化成)：

(4)

利用增廣拉格朗日乘數(shù)法(augmented lagrange multiplier)得到目標(biāo)函數(shù)為：

(5)

分別對(duì)各參數(shù)進(jìn)行迭代優(yōu)化，則參數(shù)的迭代過程為：

(6)

3 目標(biāo)分割

本文所提出的矩陣低秩稀疏表達(dá)是將超級(jí)像素看為一個(gè)數(shù)據(jù)點(diǎn)，這是一種基于區(qū)域的計(jì)算方法。要想獲得基于像素的分割結(jié)果，本文將圖像分割作為圖分割問題，利用不同的信息為圖像中的每個(gè)像素點(diǎn)建立不同的概率分布，并將此作為能量函數(shù)的線索，通過能量函數(shù)最小化的框架，利用最大流最小割(max flow/min cut)定理進(jìn)行求解，達(dá)到目標(biāo)分割的目的，提高分割精度。

3.1 能量函數(shù)框架

(7)

根據(jù)文獻(xiàn)[6]，相關(guān)能量函數(shù)定義為：

3.2 目標(biāo)表觀特征

基于目標(biāo)與背景的直方圖為圖像中每個(gè)像素建立顏色的概率分布。本文根據(jù)上一幀分割的結(jié)果，在YUV空間中分別建立目標(biāo)與背景的顏色直方圖，并且將此直方圖通過高斯濾波器進(jìn)行平滑。

3.3 目標(biāo)顯著性特征

根據(jù)式(3)求得的表達(dá)子為圖像中每個(gè)超級(jí)像素建立概率模型，使得待分割圖像中的目標(biāo)能夠具有較大的概率。

通過式(2)可知，表達(dá)子表明了當(dāng)前圖像的所有樣本集與模板集的相似程度。矩陣中的任意元素越大，表明模板集中的第個(gè)元素(矩陣中的第列)與樣本集中的第個(gè)元素(矩陣中的第列)越相似。從圖1可以看出，對(duì)于矩陣中的任意一列，可以分解成，其中表示矩陣中第列與矩陣中各個(gè)元素的相似程度，表示矩陣中第列與矩陣中各個(gè)元素的相似程度。根據(jù)以上分析，在當(dāng)前幀中，定義元素屬于目標(biāo)的概率為：

3.4 能量函數(shù)最小化求解與圖像分割

通過目標(biāo)表觀特征和目標(biāo)顯著性特征可以將圖像分別映射到兩個(gè)不同的特征空間，分別構(gòu)建兩個(gè)線索函數(shù)，并結(jié)合式(8)創(chuàng)建能量函數(shù)。根據(jù)文獻(xiàn)[16]，式(7)可以通過圖分割的方式進(jìn)行優(yōu)化求解，達(dá)到目標(biāo)分割的目的。為了提高分割精度，本文采用了文獻(xiàn)[17]的方法，利用形態(tài)學(xué)的理論，在每次分割的基礎(chǔ)上，對(duì)分割結(jié)果進(jìn)行膨脹與腐蝕操作，建立新的粗略劃分(trimap)，利用GrabCut[18]的方法對(duì)圖像進(jìn)行多次分割，提高圖像的分割精度。

4 實(shí)驗(yàn)分析

本文共設(shè)計(jì)了兩個(gè)實(shí)驗(yàn)。第一個(gè)實(shí)驗(yàn)驗(yàn)證了將矩陣的低秩稀疏表達(dá)用于建立目標(biāo)的顯著性特征的可能性，可以將目標(biāo)顯著地表達(dá)在待分割圖像中。第二個(gè)實(shí)驗(yàn)將本文算法與現(xiàn)有的一些算法進(jìn)行比較，并將比較結(jié)果作了詳細(xì)的分析。

4.1 矩陣的低秩稀疏表達(dá)

矩陣的低秩稀疏表達(dá)是本文算法的關(guān)鍵步驟。本文實(shí)驗(yàn)采用GT-SegTrack[3]數(shù)據(jù)庫(kù)中的視頻圖像作為實(shí)驗(yàn)數(shù)據(jù)，顯示了矩陣的低秩稀疏表達(dá)的有效性。圖2為4個(gè)視頻(birdfall, girl, monkey, parachute)中的兩幀圖像。其中左邊4個(gè)圖像分別為上一幀中已經(jīng)分割好的目標(biāo)，將其分別作為模板按照前面介紹的方法進(jìn)行矩陣的低秩稀疏表達(dá)。中間的4個(gè)圖像分別為當(dāng)前幀所計(jì)算出的目標(biāo)顯著性概率圖(salient map)。從中間列可以看出，此方法能夠較好地突出目標(biāo)的形狀和位置，并且去除了大部分的背景噪聲，為后續(xù)的圖像分割打下了堅(jiān)實(shí)的基礎(chǔ)。圖2的右列為計(jì)算矩陣的低秩稀疏表達(dá)時(shí)的收斂情況。其橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為計(jì)算的誤差值，表示為，表示矩陣的Frobenius范數(shù)。從圖2的右列可以看出迭代過程是收斂的。在實(shí)驗(yàn)中可以發(fā)現(xiàn)，矩陣的低秩稀疏表達(dá)與模板樣本的個(gè)數(shù)相關(guān)。當(dāng)超級(jí)像素的個(gè)數(shù)較大時(shí)，模板樣本的個(gè)數(shù)較多，無法精確地表達(dá)目標(biāo)的局部特征，待分割圖像的樣本集與模板樣本中線性相關(guān)的元素較多；當(dāng)超級(jí)像素的個(gè)數(shù)較少時(shí)，目標(biāo)模板中包含了較多的背景噪聲，因此，這兩種情況都會(huì)使得顯著性特征不理想，影響分割的精度。在本文的所有實(shí)驗(yàn)中，超級(jí)像素的最大個(gè)數(shù)為200個(gè)。

對(duì)于整個(gè)算法而言，矩陣的低秩稀疏優(yōu)化的計(jì)算占據(jù)了絕大部分的計(jì)算時(shí)間。然而，對(duì)于矩陣的SVD分解是優(yōu)化計(jì)算的時(shí)間瓶頸。由于矩陣為低秩矩陣，因此其SVD分解的時(shí)間復(fù)雜度為()，其中，為矩陣的秩，并且滿足，則計(jì)算一幀圖像顯著性特征的時(shí)間復(fù)雜度為，這說明它與采樣樣本的個(gè)數(shù)、模板集樣本個(gè)數(shù)和特征維數(shù)均保持線性關(guān)系。圖3為矩陣的低秩稀疏運(yùn)算時(shí)間與采樣樣本個(gè)數(shù)的關(guān)系，其中在計(jì)算式(3)時(shí)的迭代次數(shù)為200。

a. birdfall視頻

b. girl視頻

c. monkey視頻

d. parachute視頻

圖2 矩陣的低秩稀疏表達(dá)和顯著性特征

4.2 對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)采用GT-SegTrack[3]數(shù)據(jù)庫(kù)中的視頻圖像作為實(shí)驗(yàn)數(shù)據(jù)，將文獻(xiàn)[2](在線算法)和文獻(xiàn)[3](離線算法)所提出的方法與本算法進(jìn)行比較。比較結(jié)果如表1所示。

表1 跟蹤精度對(duì)比

其中將每個(gè)視頻中的平均誤差作為分割精度的度量單位，表示為，為視頻圖像的個(gè)數(shù)，為一幀圖像中分割錯(cuò)誤的像素個(gè)數(shù)。表1中的目標(biāo)大小為每個(gè)視頻中目標(biāo)所包含像素個(gè)數(shù)的平均值。

為了體現(xiàn)目標(biāo)表觀特征和顯著性特征在能量最小化框架下不同的關(guān)注程度，本實(shí)驗(yàn)分別列舉了兩個(gè)不同關(guān)注系數(shù)情況下的分割精度，其中為目標(biāo)表觀特征系數(shù)，目標(biāo)顯著性特征系數(shù)?？梢钥闯觯?/p>

1) 由于在視頻parachute中目標(biāo)形狀變化不大，在視頻monkey中背景較為單一，因此不同的關(guān)注系數(shù)對(duì)分割結(jié)果影響不大，并且其分割誤差均小于其他兩種方法。

3) 在視頻birdfall中，由于目標(biāo)較小，背景復(fù)雜，過多的關(guān)注表觀特征(時(shí))會(huì)造成目標(biāo)的漂移(drift)。但目標(biāo)的顯著性特征可以很好地進(jìn)行目標(biāo)分割。

通過以上分析可知，雖然矩陣的低秩稀疏表達(dá)可以在大部分視頻中較好地分割目標(biāo)，但僅僅使用一種特征無法精確地分割圖像，因此利用能量最小框架將多個(gè)特征進(jìn)行融合，可以提高目標(biāo)的分割精度。圖4顯示了本文中所涉及視頻的分割效果。

5 結(jié) 束語(yǔ)

本文通過矩陣的低秩稀疏表達(dá)提出了一種在線的目標(biāo)分割算法。將已知目標(biāo)圖像進(jìn)行過分割，提取每個(gè)超級(jí)像素的L2ECM特征，建立模板集。對(duì)待分割圖像進(jìn)行相對(duì)于模板集的線性表達(dá)；利用視頻圖像的連續(xù)性和噪聲的稀疏性，對(duì)線性表達(dá)方程添加低秩和稀疏約束，將目標(biāo)的顯著性問題轉(zhuǎn)化為方程的低秩稀疏優(yōu)化問題；進(jìn)而通過能量最小化框架，將圖像的多種信息融合，達(dá)到像素級(jí)目標(biāo)跟蹤與分割的目的。在實(shí)驗(yàn)部分本文將該算法與已有的目標(biāo)分割算法進(jìn)行比較，提高了在線算法的分割精度。

但從本文的分析中可知，超級(jí)像素的大小會(huì)影響目標(biāo)的顯著性特征；并且能量最小化框架中不同特征的關(guān)注系數(shù)對(duì)于不同的圖像環(huán)境影響較大。如何實(shí)現(xiàn)這些參數(shù)的自適應(yīng)算法將是未來工作的重點(diǎn)。

[1] NING J, ZHANG L, ZHANG D, et al. Joint registration and active contour segmentation for object tracking[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(9): 1589-1597.

[2] CHOCKALINGAM P, PRADEEP N, BIRCHFIELD S. Adaptive fragments-based tracking of non-rigid objects using level sets[C]//2009 IEEE 12th International Conference on Computer Vision. Kyoto: IEEE, 2009: 1530- 1537.

[3] TSAI D, FLAGG M, NAKAZAWA A, et al. Motion coherent tracking using multi-label MRF optimization[J]. International Journal of Computer Vision, 2012, 100(2): 190-202.

[4] CRIMINISI A, CROSS G, BLAKE A, et al. Bilayer segmentation of live video[C]//2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. NewYork: IEEE, 2006, 1: 53-60.

[5] WANG L, GONG M, ZHANG C, et al. Automatic real-time video matting using time-of-flight camera and multichannel poisson equations[J]. International Journal of Computer Vision, 2012, 97(1): 104-121.

[6] YIN Z, COLLINS R T. Online figure-ground segmentation with edge pixel classification[C]//BMVC. Leeds: IEEE, 2008: 1-10.

[7] BAO C, WU Y, LING H, et al. Real time robust l1 tracker using accelerated proximal gradient approach[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence: IEEE, 2012: 1830-1837.

[8] ZHANG T, GHANEM B, LIU S, et al. Low-rank sparse learning for robust visual tracking[M]//Computer Vision- ECCV 2012. Berlin Heidelberg, Springer, 2012: 470-484.

[9] LI P, WANG Q. Local log-euclidean covariance matrix (L2ECM) for image representation and its applications[M]// Computer Vision-ECCV 2012. Berlin: Springer, 2012: 469- 482.

[10] ACHANTA R, SHAJI A, KEVIN S, et al. SLIC superpixels compared to state-of the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(11): 2274-2282.

[11] LAPTEV I, MARSZALEK M, SCHMID C. Learning realistic human actions from movies[C]//IEEE Conference on Computer Vision and Pattern Recognition. Anchorage: IEEE, 2008: 1-8.

[12] PERAZZI F, KR?HENBüHL P, PRITCH Y, et al. Saliency filters: Contrast based filtering for salient region detection[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence: IEEE, 2012: 733-740.

[13] LI C, LIN L, ZUO W, et al. Sold: Sub-optimal low-rank decomposition for efficient video segmentation[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Boston: IEEE, 2015: 5519-5527.

[14] LIU X, LIN L, YUILLE A L. Robust region grouping via internal patch statistics[C]//2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Oregon: IEEE, 2013: 1931-1938.

[15] ZHUANG L, GAO H, LIN Z, et al. Non-negative low rank and sparse graph for semi-supervised learning[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence: IEEE, 2012: 2328-2335.

[16] KOLMOGOROV V, ZABIN R. What energy functions can be minimized via graph cuts?[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(2): 147-159.

[17] CHENG M, MITRA N J, HUANG X, et al. Global contrast based salient region detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(3): 569-582.

[18] TANG M, GORELICK L, VEKSLER O, et al. Grabcut in one cut[C]//2013 IEEE International Conference on Computer Vision (ICCV). Sydney: IEEE, 2013: 1769- 1776.

編 輯 葉 芳

Video Object Segmentation Via Low-Rank Sparse Representation

GU Song1,2, MA Zheng1, and XIE Mei3

(1. School of Communication and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. Department of Aircraft Maintenance Engineering, Chengdu Aeronautic Polytechnic Chengdu 610100; 3. School of Electronic Engineering, University of Electronic Science and Technology of China Chengdu 611731)

We present a novel on-line algorithm for target segmentation and tracking in video. Superpixels, which are abstracted in every frame, are treated as data points in this paper. The object in current frame is represented as sparse linear combination of dictionary templates, which are generated based on the segmentation result in the previous frame. Then the algorithm capitalizes on the inherent low-rank structure of representation that are learned jointly. A low-rank sparse matrix optimal solution results in the construction of the trimap. At last, a simple energy minimization solution is adopted in segmented stage, leading to a binary pixel-wise segmentation. Experiments demonstrate that our approach is effective.

energy minimization; graph cut; low rank; sparse; video object segmentation

TP39

A

10.3969/j.issn.1001-0548.2017.02.008

2015-11-05；

2016-03-18

國(guó)家自然科學(xué)基金(61271288)；教育部博士點(diǎn)基金(20130185130001)

顧菘(1977-)，男，博士，主要從事數(shù)字圖像處理方面的研究.