基于平衡熵切片的視頻流分割算法的研究

劉蕓 許華宇 劉衍

在均衡的熵切片技術(shù)的基礎(chǔ)上提出了基于流的均衡的熵切片技術(shù)。通過(guò)UCF運(yùn)動(dòng)數(shù)據(jù)集來(lái)評(píng)估該方法的有效性。大量實(shí)驗(yàn)結(jié)果表明這種方法能以在線工作的方式獲取更高質(zhì)量的分割結(jié)果，同時(shí)花費(fèi)的時(shí)間和內(nèi)存更少。

視頻分割 均衡的熵切片 流處理 超體元

1 引言

隨著遠(yuǎn)程監(jiān)控系統(tǒng)、無(wú)人駕駛系統(tǒng)的大量實(shí)際應(yīng)用，視頻分割將在生活中扮演十分重要的角色，如場(chǎng)景的識(shí)別感知[1]，陰影/照明的估測(cè)[2]，機(jī)器人學(xué)[3]中已經(jīng)大量使用到了視頻分割技術(shù)。在前期的沒(méi)有長(zhǎng)度限制的視頻處理中，視頻分割技術(shù)似乎已經(jīng)有了一種可靠的方法，它們不像早期的視頻分割方法[4]那樣需要做一個(gè)基于靜態(tài)的背景假設(shè)[4]。視頻分割最新的研究成果是產(chǎn)生時(shí)空的關(guān)聯(lián)性，如文獻(xiàn)[5]、文獻(xiàn)[6]、文獻(xiàn)[7]可以獲得十分出色的視頻分割結(jié)果。有一些方法甚至可以做到在線的流處理，但是在實(shí)際應(yīng)用中還有很多工作要做。

2 背景介紹

為了詳細(xì)地說(shuō)明視頻分割的復(fù)雜性，本文在總結(jié)前人研究成果的基礎(chǔ)上提出了以下3個(gè)主要挑戰(zhàn)：

（1）時(shí)間相干性：在不考慮時(shí)間相干性的情況下，視頻可以被一幀一幀地分割。在這種情況下，作為一個(gè)連續(xù)的方法是不能展現(xiàn)出幀與幀之間很小的變化，但是卻能實(shí)時(shí)地處理視頻。如果使用一個(gè)樹(shù)結(jié)構(gòu)去重構(gòu)整個(gè)視頻，將會(huì)需要占用很大的內(nèi)存和硬件資源。在一些監(jiān)控和交互應(yīng)用中[8]，不可能把整個(gè)視頻都放到內(nèi)存中去處理。所以有些學(xué)者就提出了基于流的層分割方法的近似框架[9]，每個(gè)幀只會(huì)被處理一次并且不會(huì)改變前面的幀的分割結(jié)果。它可以展現(xiàn)出幀與幀之間很小的變化但是效果卻沒(méi)有使用樹(shù)結(jié)構(gòu)去重構(gòu)整個(gè)視頻的好并且仍然具有算法延遲的特性。

（2）自動(dòng)處理：隨著時(shí)間去追蹤區(qū)域?qū)Ψ指顒?dòng)態(tài)場(chǎng)景中感知相似的區(qū)域有很大的影響。與追蹤相反，去追蹤哪一塊區(qū)域是很難判斷哪些幀有這些區(qū)域或者追蹤的時(shí)間方向（向前或者向后）。

（3）可擴(kuò)展性：如果給出一個(gè)視頻中的大量的像素點(diǎn)或者特征，視頻分割方法將趨向于變慢并且需要很大的內(nèi)存。最好的方法就是把視頻分割成多級(jí)的區(qū)域，每個(gè)區(qū)域涉及到時(shí)間和空間，并且每個(gè)區(qū)域也能代表一個(gè)物體。

視頻的層分割方法表現(xiàn)地很好，歸因于相似的多尺度區(qū)域被作為產(chǎn)生的層被再評(píng)估，但是卻沒(méi)有被廣泛采用。結(jié)果層包含了豐富的視頻多尺度信息，但不能片面地取一層，這樣做會(huì)丟失一些信息。

基于上述三個(gè)方面的挑戰(zhàn)，本文提出了一種新的方法去滿足這些問(wèn)題。此方法在獲取了足夠的幀后，會(huì)開(kāi)始構(gòu)建一個(gè)基于層結(jié)構(gòu)的樹(shù)。為了獲取一個(gè)最優(yōu)的樹(shù)切片，就會(huì)使用特征標(biāo)準(zhǔn)并且使用一個(gè)標(biāo)準(zhǔn)的解決方案（IBM CPLEX）去獲取樹(shù)切片。在完成這些之后，系統(tǒng)會(huì)輸出結(jié)果并保存一些信息，然后開(kāi)始下一次的處理，并將一直循環(huán)處理，直到所有的幀都被處理完。

3 基于超體元的視頻分割方法

視頻分割問(wèn)題在概念上可以想象成一個(gè)聚類的問(wèn)題，就是通過(guò)掃描物體移動(dòng)時(shí)通過(guò)的空間和時(shí)間，把許多超體元聚集成可以展現(xiàn)的更大單元。從另一方面說(shuō)，本文所描述的超體元都是聚集成時(shí)空體的，如果這個(gè)時(shí)空體改變了，比如物體從場(chǎng)景中消失，就可以視為一個(gè)分割。如果有其他的新物體進(jìn)入到視頻的場(chǎng)景中，這將會(huì)使問(wèn)題變得更加復(fù)雜。

一開(kāi)始視頻分割是嘗試去把一個(gè)視頻分割成時(shí)間相干的場(chǎng)景。由于視頻的信息量是十分龐大的，如果在像素點(diǎn)或者體像素的級(jí)別上去分割視頻的話也算是時(shí)空等價(jià)的。因此，大多數(shù)研究者傾向于基于超像素或者超體元的研究。他們是把一些相似或相關(guān)的像素聚集在一起形成的，而且都是比像素點(diǎn)和體像素都大的實(shí)體，現(xiàn)在的很多視頻分割方法不是基于超像素的就是基于體像素的。超像素的本質(zhì)是空間對(duì)象，因?yàn)樾枰紤]物體間時(shí)空上的關(guān)聯(lián)，所以無(wú)論如何都要把從運(yùn)動(dòng)或者顏色對(duì)比線索獲取的像素點(diǎn)的時(shí)間方面考慮進(jìn)去。動(dòng)作線索可以考慮成一個(gè)像素流，簡(jiǎn)單地說(shuō)，就是使用光流算法去計(jì)算幀與幀之間像素點(diǎn)的移動(dòng)。其中光流算法是連接兩個(gè)視頻幀之間相同像素的向量，這是一個(gè)可以把運(yùn)動(dòng)線索合并到視頻中的方法。在本文中，只考慮使用超體元去進(jìn)行視頻分割。

3.1 均衡的熵切片技術(shù)

Felzenszwalb和Huttenlocher提出了一種基于圖的圖片分割算法[10]，他們的算法被Grundmann擴(kuò)展成了基于圖的視頻分割算法（Graph-based Hierarchy Video Segmentation，GBH）[11]。然而GBH在低層會(huì)過(guò)分割，在高層會(huì)欠分割，因此在高層的時(shí)候會(huì)包含太少的分割域，在低層的時(shí)候會(huì)包含太多的分割域。所以，需要在這么多層的分割結(jié)果中，找到一個(gè)平衡，而這是一個(gè)十分復(fù)雜的過(guò)程。因?yàn)樾枰テ胶獠煌瑢又g的信息分布，而一個(gè)基于熵概念的均衡的熵切片方法[12]可以解決這個(gè)問(wèn)題。

均衡的熵切片技術(shù)包含一個(gè)模型（均衡的熵切片模型）和一個(gè)能通過(guò)一個(gè)二進(jìn)制規(guī)劃解決這個(gè)問(wèn)題的公式。它只考慮樹(shù)形的超體元層，比如每一個(gè)節(jié)點(diǎn)有且僅有一個(gè)父節(jié)點(diǎn)（除了根節(jié)點(diǎn)）而且每一個(gè)節(jié)點(diǎn)至少有一個(gè)子節(jié)點(diǎn)（除了葉節(jié)點(diǎn)）。GBH可以產(chǎn)生這樣的一個(gè)樹(shù)。

均衡熵切片技術(shù)需要一個(gè)樹(shù)切片在已經(jīng)選擇的超體元中去幫助它平衡大量的信息，基于一個(gè)給出的特征標(biāo)準(zhǔn)，這個(gè)特征標(biāo)準(zhǔn)可以是顏色直方圖。這個(gè)樹(shù)切片是很多個(gè)從根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑所組成的節(jié)點(diǎn)集，圖1顯示了一個(gè)分割樹(shù)上的樹(shù)切片。

假設(shè)每一個(gè)切片都能提供一個(gè)扁平的層次結(jié)構(gòu)，比如把結(jié)合了切片上所有的節(jié)點(diǎn)的樹(shù)形層次結(jié)構(gòu)平鋪在同一層上，就可以從原始視頻的超體元層級(jí)結(jié)構(gòu)中獲得一個(gè)新的分割組成。本文之所以會(huì)平鋪層級(jí)結(jié)構(gòu)是因?yàn)樵诓煌膶蛹?jí)上對(duì)不同的物體進(jìn)行分割是不可能的。但是一旦平鋪了樹(shù)的層級(jí)結(jié)構(gòu)，所有的物體都會(huì)被聚集在同一層上，這些物體就會(huì)更加適合被分析。所有的樹(shù)形切片集都包含有用的和無(wú)用的節(jié)點(diǎn)選擇信息，有用的意思是可以使視頻的分割結(jié)果趨向于精確，無(wú)用的意思是使視頻的分割結(jié)果趨向于模糊。

在樹(shù)形結(jié)構(gòu)T中，本文用一個(gè)二進(jìn)制的變量xs去表示每個(gè)節(jié)點(diǎn)Vs。如果節(jié)點(diǎn)Vs是切片的一部分，則xs的值就取為1；如果不是，就取為0。本文的方法是用x去表示整個(gè)樹(shù)。任何x的實(shí)例都會(huì)影響樹(shù)形結(jié)構(gòu)T中節(jié)點(diǎn)的選擇，但并不是所有的x實(shí)例都是可用的。在一個(gè)有效的切片中，在分割樹(shù)T中，每一條根到葉的路徑有且僅有一個(gè)節(jié)點(diǎn)會(huì)被選中。圖1從另一方面說(shuō)，如果是一個(gè)有效的路徑，那么這條路徑只包含一個(gè)節(jié)點(diǎn)，并以圖1指出的方式把那個(gè)節(jié)點(diǎn)選擇出來(lái)并以線性約束的方式進(jìn)行表達(dá)。

首先讓P表示一個(gè)p×N的二進(jìn)制矩陣。p=|V1|是樹(shù)T的葉子的節(jié)點(diǎn)數(shù)，而且N=|T|是樹(shù)T中所有的節(jié)點(diǎn)數(shù)。矩陣P的每一行通過(guò)設(shè)定相應(yīng)路徑上節(jié)點(diǎn)的列值（不是1就是0）來(lái)編碼一條根到葉節(jié)點(diǎn)的路徑。這樣的一個(gè)矩陣就列舉了樹(shù)T中所有可能的根到葉路徑。更多的細(xì)節(jié)可以在圖2中看到。

為了確保一個(gè)樹(shù)切片是有效的，本文用了下面這個(gè)約束：

公式中1ρ是所有1組成的一個(gè)長(zhǎng)度為ρ的向量。這個(gè)線性約束能確保每一條根到葉路徑有且只有一個(gè)節(jié)點(diǎn)在切片x上。如果有多于一個(gè)的節(jié)點(diǎn)在Pi中被選擇，那么Pix>1。如果沒(méi)有節(jié)點(diǎn)在Pi中被選擇，那么Pix=0。有效的選擇x就被稱之為一個(gè)樹(shù)切片。這就是前面說(shuō)收集包含有用和無(wú)用節(jié)點(diǎn)的原因。有用的信息就是組成根到葉有效的路徑節(jié)點(diǎn)，無(wú)用的信息就是在約束條件下沒(méi)有在根到葉有效的路徑上。

在一個(gè)有效的路徑上，在分割樹(shù)的每條根到葉路徑上有且僅有一條路徑會(huì)被選擇，所以就會(huì)有很多條路徑在切片上。均衡的熵切片技術(shù)可以在一個(gè)層級(jí)中找到最好的切片，這個(gè)切片可以包含最大的信息量。通過(guò)包含的信息量選擇大的或者小的超體元，如果信息量少，本文的方法就選擇大的超體元；反之，就會(huì)選擇小的超體元。

特征標(biāo)準(zhǔn)對(duì)一個(gè)節(jié)點(diǎn)的信息量有很大的影響。層級(jí)結(jié)構(gòu)中每個(gè)節(jié)點(diǎn)的信息量可以通過(guò)計(jì)算確定的動(dòng)作或者人為線索的特征去獲取熵。假設(shè)有一個(gè)特征標(biāo)準(zhǔn)F（·）映射一個(gè)節(jié)點(diǎn)Vs到一個(gè)離散特征變量分布，就可以得到：

隨著二維離散特征變量的變化而變化，如果希望切片主要關(guān)注視頻背景是靜止的區(qū)域，就可以使用一個(gè)無(wú)人監(jiān)督的動(dòng)作特征標(biāo)準(zhǔn)，比如說(shuō)：光流。

為了去尋找一個(gè)樹(shù)切片，這個(gè)樹(shù)切片不僅可以平衡所有被選擇節(jié)點(diǎn)所包含的信息量，而且可以同時(shí)考慮節(jié)點(diǎn)的信息量，于是本文提出了均衡的熵切片技術(shù)。它通過(guò)最小化被選擇節(jié)點(diǎn)不同的熵來(lái)尋找一個(gè)有效的樹(shù)切片，而且最小化的過(guò)程是通過(guò)所有有效樹(shù)切片得到的：

直接最小化式（3）太復(fù)雜了，因?yàn)樗竺杜e出所有有效的切片和包含一個(gè)只選擇了根節(jié)點(diǎn)退化了的最小值。此時(shí)就可以使用二進(jìn)制規(guī)劃的方法，，即均衡的熵切片技術(shù)：

雖然樹(shù)的高層節(jié)點(diǎn)的熵比低層節(jié)點(diǎn)的熵要大，但是高層節(jié)點(diǎn)的數(shù)量要比低層節(jié)點(diǎn)的數(shù)量少很多。通過(guò)添加體積因素，向下去選擇層級(jí)結(jié)構(gòu)直到獲取一個(gè)均衡的熵。

在獲取了第一次視頻塊的分割信息后，就嘗試著去把這些標(biāo)記信息傳遞下去，以此來(lái)達(dá)到連續(xù)分割視頻的效果。

3.2 基于流的均衡的熵切片技術(shù)

把第一次分割視頻的結(jié)果信息傳遞到以后的視頻分割過(guò)程中，綜合考慮了前面提出的問(wèn)題后，本文提出了一種新方法并把它命名為基于流的均衡的熵切片技術(shù)，可以用下面的步驟去描述：

在步驟（1）中，獲取一個(gè)視頻的層級(jí)結(jié)構(gòu)是很重要的，GBH就可以獲取一個(gè)這樣的結(jié)果。本文提出的方法只能處理樹(shù)形的超體元層級(jí)結(jié)構(gòu)。步驟（2）到步驟（6）會(huì)一直持續(xù)下去直到所有的視頻幀被處理完。在步驟（3）中，使用了一個(gè)創(chuàng)新的方法去構(gòu)建一個(gè)樹(shù)形結(jié)構(gòu)。一開(kāi)始先把幀的RGB值改為索引值，通過(guò)矩陣變換，就可以從層與層之間獲取一個(gè)相互有關(guān)聯(lián)的層級(jí)數(shù)據(jù)結(jié)構(gòu)的值。這些數(shù)據(jù)可以用來(lái)構(gòu)建樹(shù)形結(jié)構(gòu)，具體如圖3所示。

在步驟（4）中，使用光流方法去計(jì)算視頻中每一幀的特征，它的核心思想是使用共軛梯度替代賽德?tīng)柣蛘咧鸫纬神Y方法，使大的線性系統(tǒng)的解決方案變得十分簡(jiǎn)單。如果有一個(gè)很大的線性方程式Ax=b，其中x是流域，它需要在每個(gè)內(nèi)部步驟中被計(jì)算出來(lái)，而且還需要找到一個(gè)可以被分解為篩選和權(quán)重的串聯(lián)矩陣A。這樣它就不需要在使用共軛梯度解決方法過(guò)程中去記錄矩陣A，但是需要去寫(xiě)一個(gè)由篩選和權(quán)重構(gòu)成的方程去應(yīng)用到A得到x的值。在這一步中也會(huì)構(gòu)建一元和二元的項(xiàng)。

因?yàn)橐曨l在本文所提出方法的處理過(guò)程中是用一個(gè)樹(shù)形結(jié)構(gòu)去展現(xiàn)的，所以就很難保持每一次處理視頻過(guò)程中顏色的連續(xù)性，樹(shù)的結(jié)構(gòu)信息很難被傳送到下一次視頻分割中。為了解決這個(gè)問(wèn)題，首先用一個(gè)顏色池，在每一次的視頻塊的處理中，在得到了CPLEX結(jié)果后，把從每一層選取的結(jié)果畫(huà)到同一層上。

在這個(gè)過(guò)程中，從顏色池中選擇顏色，因?yàn)镃PLEX的結(jié)果是不可控的，它不會(huì)在每一次視頻塊的處理過(guò)程中選擇同一塊區(qū)域。比如人的手在第一次視頻塊處理中是藍(lán)色的，在第二次視頻塊處理中，人的手就會(huì)從其他層去選擇，所以就會(huì)變成其他顏色。在第一次處理過(guò)程中儲(chǔ)存了顏色和其相對(duì)應(yīng)的位置信息（CPLEX的結(jié)果），當(dāng)其他視頻塊開(kāi)始把結(jié)果畫(huà)出來(lái)的時(shí)候，先對(duì)比儲(chǔ)存的信息，當(dāng)找到對(duì)應(yīng)的顏色信息后，就會(huì)使用第一次視頻塊處理過(guò)程的位置信息，以此來(lái)保持顏色的連續(xù)性。這個(gè)方法可以總結(jié)為一個(gè)偽代碼，具體如下面的算法所示：

4 實(shí)驗(yàn)結(jié)果與分析

本文提出的算法中，線性和二次項(xiàng)的變量十分重要。實(shí)際上可以觀察到，層級(jí)之間有關(guān)聯(lián)的超體元的選擇對(duì)σ的變化不是很敏感。正則化這些可以影響視頻分割結(jié)果的項(xiàng)并通過(guò)大量實(shí)驗(yàn)結(jié)果的對(duì)比，最終確定把σ設(shè)為10為最優(yōu)，也就是說(shuō)本文所提出的方法獲取的結(jié)果更加傾向于二次項(xiàng)而不是線性的。

本文使用了M.Rodriguez提供的UCF運(yùn)動(dòng)數(shù)據(jù)集[15]來(lái)評(píng)估本文提出的方法。這個(gè)數(shù)據(jù)集包含了各種各樣的運(yùn)動(dòng)場(chǎng)地而且具有代表性，所收集的150個(gè)視頻序列的分辨率都是720×480的，是一個(gè)擁有廣泛的場(chǎng)景和視角的自然運(yùn)動(dòng)特征視頻庫(kù)。

圖4到圖6展示了相關(guān)結(jié)果，可以顯示出對(duì)今后做視頻分析很有用的許多細(xì)節(jié)，并且可以很好地處理本文選擇的數(shù)據(jù)集。

圖4中滑滑板的男孩和女孩的外形可以很清楚地顯示出來(lái)，他們的手臂位置的變化速度超過(guò)了他們的身體，但是仍能很好地展現(xiàn)出手臂的變化。

圖5的上半部分是一個(gè)沿著直線滑行的男孩，所以就很難進(jìn)行分割，但仍然可以看出男孩的每個(gè)動(dòng)作。在這幅圖的底部，有一個(gè)女孩坐著不動(dòng)，有一個(gè)男孩向她移動(dòng)，其他的幾個(gè)男孩在附近玩耍，結(jié)果很清晰地顯示了這些。

圖6展示了背景是靜止的和快速變化的分割結(jié)果。上半部分展示的背景是靜止的，有人騎著馬向前走，人和馬的輪廓可以很容易地分辨出來(lái)。下半部分是一個(gè)人騎著馬快速地向前跑，所以背景的變化就很快。在結(jié)果中，背景的顏色改變了，但是人和馬的顏色依舊保持了一致。

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

本文的方法不但可以以流的方式不間斷地工作，而且可以找到一個(gè)樹(shù)切片，這個(gè)樹(shù)切片不僅可以平衡所有被選擇節(jié)點(diǎn)所包含的信息量，而且可以同時(shí)考慮節(jié)點(diǎn)的信息量。通過(guò)包含的信息量選擇大的或者小的超體元，如果信息量少，就選擇大的超體元；反之，就會(huì)選擇小的超體元。光流被用來(lái)作為一個(gè)后置的特征標(biāo)準(zhǔn)去驅(qū)動(dòng)信息的選擇，它跟原始的超體元處理無(wú)關(guān)。實(shí)驗(yàn)結(jié)果表明這種方法不但能以流的方式工作，而且可以獲取更高質(zhì)量的分割結(jié)果，同時(shí)在時(shí)間和內(nèi)存方面的花費(fèi)更少。

參考文獻(xiàn)：

[1] Criminisi A， Cross G， Blake A， et al. Bilayer Segmentation of Live Video[J]. Proc IEEE Computer Vision & Pattern Recognition， 2006（1）： 53-60.

[2] Liu C. Beyond Pixels： Exploring New Representations and Applications for Motion Analysis[J]. Massachusetts Institute of Technology， 2009.

[3] Alexandros P， Chaohui W， Dimitris S， et al. Simultaneous Cast Shadows， Illumination and Geometry Inference Using Hypergraphs[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2013，35（2）： 437-449.

[4] Vijay B， Ignas B， Roberto C. Semi-supervised video segmentation using tree structured graphical models[J]. IEEE Transactions on Software Engineering， 2013，35（11）： 2751-2764.

[5] Grundmann M， Kwatra V， Han M， et al. Efficient Hierarchical Graph-Based Video Segmentation[J]. Georgia Institute of Technology， 2010，26（2）： 2141-2148.

[6] Drucker F， Maccormick J. Fast superpixels for video analysis[A]. Motion and Video Computing， 2009： 1-8.

[7] Corso J J， Sharon E， Dube S， et al. Efficient Multilevel Brain Tumor Segmentation With Integrated Bayesian Model Classification[J]. Medical Imaging IEEE Transactions on， 2008，27（5）： 629-640.

[8] Liu M Y， Tuzel O， Ramalingam S， et al. Entropy rate superpixel segmentation[A]. IEEE Conference on Computer Vision & Pattern Recognition， 2011： 2097-2104.

[9] Xu C， Xiong C， Corso J J. Streaming Hierarchical Video Segmentation[A]. Proceedings of the 12th European conference on Computer Vision-Volume Part VI， Springer-Verlag， 2012： 626-639.

[10] Felzenszwalb P F， Huttenlocher D P. Efficient Graph-Based Image Segmentation[J]. International Journal of Computer Vision， 2004，59（2）： 167-181.

[11] Grundmann M， Kwatra V， Han M， et al. Efficient Hierarchical Graph-Based Video Segmentation[J]. Georgia Institute of Technology， 2010，26（2）： 2141-2148.

[12] Xu C， Whitt S， Corso J J. Flattening Supervoxel Hierarchies by the Uniform Entropy Slice[A]. Computer Vision （ICCV）， 2013 IEEE International Conference on IEEE， 2013： 2240-2247.

[13] Guo R， Hoiem D. Beyond the Line of Sight： Labeling the Underlying Surfaces[J]. Springer Berlin Heidelberg， 2012（1）： 761-774.

[14] Liu C. Beyond Pixels： Exploring New Representations and Applications for Motion Analysis[J]. Massachusetts Institute of Technology， 2009.

[15] Rodriguez M D， Ahmed J， Shah M. Action MACH a spatio-temporal Maximum Average Correlation Height filter for action recognition[A]. IEEE Conference on Computer Vision & Pattern Recognition， 2008： 1-8.