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

劉蕓 許華宇 劉衍

在均衡的熵切片技術的基礎上提出了基于流的均衡的熵切片技術。通過UCF運動數據集來評估該方法的有效性。大量實驗結果表明這種方法能以在線工作的方式獲取更高質量的分割結果，同時花費的時間和內存更少。

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

1 引言

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

2 背景介紹

為了詳細地說明視頻分割的復雜性，本文在總結前人研究成果的基礎上提出了以下3個主要挑戰：

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

（2）自動處理：隨著時間去追蹤區域對分割動態場景中感知相似的區域有很大的影響。與追蹤相反，去追蹤哪一塊區域是很難判斷哪些幀有這些區域或者追蹤的時間方向（向前或者向后）。

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

視頻的層分割方法表現地很好，歸因于相似的多尺度區域被作為產生的層被再評估，但是卻沒有被廣泛采用。結果層包含了豐富的視頻多尺度信息，但不能片面地取一層，這樣做會丟失一些信息。

基于上述三個方面的挑戰，本文提出了一種新的方法去滿足這些問題。此方法在獲取了足夠的幀后，會開始構建一個基于層結構的樹。為了獲取一個最優的樹切片，就會使用特征標準并且使用一個標準的解決方案（IBM CPLEX）去獲取樹切片。在完成這些之后，系統會輸出結果并保存一些信息，然后開始下一次的處理，并將一直循環處理，直到所有的幀都被處理完。

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

視頻分割問題在概念上可以想象成一個聚類的問題，就是通過掃描物體移動時通過的空間和時間，把許多超體元聚集成可以展現的更大單元。從另一方面說，本文所描述的超體元都是聚集成時空體的，如果這個時空體改變了，比如物體從場景中消失，就可以視為一個分割。如果有其他的新物體進入到視頻的場景中，這將會使問題變得更加復雜。

一開始視頻分割是嘗試去把一個視頻分割成時間相干的場景。由于視頻的信息量是十分龐大的，如果在像素點或者體像素的級別上去分割視頻的話也算是時空等價的。因此，大多數研究者傾向于基于超像素或者超體元的研究。他們是把一些相似或相關的像素聚集在一起形成的，而且都是比像素點和體像素都大的實體，現在的很多視頻分割方法不是基于超像素的就是基于體像素的。超像素的本質是空間對象，因為需要考慮物體間時空上的關聯，所以無論如何都要把從運動或者顏色對比線索獲取的像素點的時間方面考慮進去。動作線索可以考慮成一個像素流，簡單地說，就是使用光流算法去計算幀與幀之間像素點的移動。其中光流算法是連接兩個視頻幀之間相同像素的向量，這是一個可以把運動線索合并到視頻中的方法。在本文中，只考慮使用超體元去進行視頻分割。

3.1 均衡的熵切片技術

Felzenszwalb和Huttenlocher提出了一種基于圖的圖片分割算法[10]，他們的算法被Grundmann擴展成了基于圖的視頻分割算法（Graph-based Hierarchy Video Segmentation，GBH）[11]。然而GBH在低層會過分割，在高層會欠分割，因此在高層的時候會包含太少的分割域，在低層的時候會包含太多的分割域。所以，需要在這么多層的分割結果中，找到一個平衡，而這是一個十分復雜的過程。因為需要去平衡不同層之間的信息分布，而一個基于熵概念的均衡的熵切片方法[12]可以解決這個問題。

均衡的熵切片技術包含一個模型（均衡的熵切片模型）和一個能通過一個二進制規劃解決這個問題的公式。它只考慮樹形的超體元層，比如每一個節點有且僅有一個父節點（除了根節點）而且每一個節點至少有一個子節點（除了葉節點）。GBH可以產生這樣的一個樹。

均衡熵切片技術需要一個樹切片在已經選擇的超體元中去幫助它平衡大量的信息，基于一個給出的特征標準，這個特征標準可以是顏色直方圖。這個樹切片是很多個從根節點到葉節點路徑所組成的節點集，圖1顯示了一個分割樹上的樹切片。

假設每一個切片都能提供一個扁平的層次結構，比如把結合了切片上所有的節點的樹形層次結構平鋪在同一層上，就可以從原始視頻的超體元層級結構中獲得一個新的分割組成。本文之所以會平鋪層級結構是因為在不同的層級上對不同的物體進行分割是不可能的。但是一旦平鋪了樹的層級結構，所有的物體都會被聚集在同一層上，這些物體就會更加適合被分析。所有的樹形切片集都包含有用的和無用的節點選擇信息，有用的意思是可以使視頻的分割結果趨向于精確，無用的意思是使視頻的分割結果趨向于模糊。

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

首先讓P表示一個p×N的二進制矩陣。p=|V1|是樹T的葉子的節點數，而且N=|T|是樹T中所有的節點數。矩陣P的每一行通過設定相應路徑上節點的列值（不是1就是0）來編碼一條根到葉節點的路徑。這樣的一個矩陣就列舉了樹T中所有可能的根到葉路徑。更多的細節可以在圖2中看到。

為了確保一個樹切片是有效的，本文用了下面這個約束：

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

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

特征標準對一個節點的信息量有很大的影響。層級結構中每個節點的信息量可以通過計算確定的動作或者人為線索的特征去獲取熵。假設有一個特征標準F（·）映射一個節點Vs到一個離散特征變量分布，就可以得到：

隨著二維離散特征變量的變化而變化，如果希望切片主要關注視頻背景是靜止的區域，就可以使用一個無人監督的動作特征標準，比如說：光流。

為了去尋找一個樹切片，這個樹切片不僅可以平衡所有被選擇節點所包含的信息量，而且可以同時考慮節點的信息量，于是本文提出了均衡的熵切片技術。它通過最小化被選擇節點不同的熵來尋找一個有效的樹切片，而且最小化的過程是通過所有有效樹切片得到的：

直接最小化式（3）太復雜了，因為它要求枚舉出所有有效的切片和包含一個只選擇了根節點退化了的最小值。此時就可以使用二進制規劃的方法，，即均衡的熵切片技術：

雖然樹的高層節點的熵比低層節點的熵要大，但是高層節點的數量要比低層節點的數量少很多。通過添加體積因素，向下去選擇層級結構直到獲取一個均衡的熵。

在獲取了第一次視頻塊的分割信息后，就嘗試著去把這些標記信息傳遞下去，以此來達到連續分割視頻的效果。

3.2 基于流的均衡的熵切片技術

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

在步驟（1）中，獲取一個視頻的層級結構是很重要的，GBH就可以獲取一個這樣的結果。本文提出的方法只能處理樹形的超體元層級結構。步驟（2）到步驟（6）會一直持續下去直到所有的視頻幀被處理完。在步驟（3）中，使用了一個創新的方法去構建一個樹形結構。一開始先把幀的RGB值改為索引值，通過矩陣變換，就可以從層與層之間獲取一個相互有關聯的層級數據結構的值。這些數據可以用來構建樹形結構，具體如圖3所示。

在步驟（4）中，使用光流方法去計算視頻中每一幀的特征，它的核心思想是使用共軛梯度替代賽德爾或者逐次超松馳方法，使大的線性系統的解決方案變得十分簡單。如果有一個很大的線性方程式Ax=b，其中x是流域，它需要在每個內部步驟中被計算出來，而且還需要找到一個可以被分解為篩選和權重的串聯矩陣A。這樣它就不需要在使用共軛梯度解決方法過程中去記錄矩陣A，但是需要去寫一個由篩選和權重構成的方程去應用到A得到x的值。在這一步中也會構建一元和二元的項。

因為視頻在本文所提出方法的處理過程中是用一個樹形結構去展現的，所以就很難保持每一次處理視頻過程中顏色的連續性，樹的結構信息很難被傳送到下一次視頻分割中。為了解決這個問題，首先用一個顏色池，在每一次的視頻塊的處理中，在得到了CPLEX結果后，把從每一層選取的結果畫到同一層上。

在這個過程中，從顏色池中選擇顏色，因為CPLEX的結果是不可控的，它不會在每一次視頻塊的處理過程中選擇同一塊區域。比如人的手在第一次視頻塊處理中是藍色的，在第二次視頻塊處理中，人的手就會從其他層去選擇，所以就會變成其他顏色。在第一次處理過程中儲存了顏色和其相對應的位置信息（CPLEX的結果），當其他視頻塊開始把結果畫出來的時候，先對比儲存的信息，當找到對應的顏色信息后，就會使用第一次視頻塊處理過程的位置信息，以此來保持顏色的連續性。這個方法可以總結為一個偽代碼，具體如下面的算法所示：

4 實驗結果與分析

本文提出的算法中，線性和二次項的變量十分重要。實際上可以觀察到，層級之間有關聯的超體元的選擇對σ的變化不是很敏感。正則化這些可以影響視頻分割結果的項并通過大量實驗結果的對比，最終確定把σ設為10為最優，也就是說本文所提出的方法獲取的結果更加傾向于二次項而不是線性的。

本文使用了M.Rodriguez提供的UCF運動數據集[15]來評估本文提出的方法。這個數據集包含了各種各樣的運動場地而且具有代表性，所收集的150個視頻序列的分辨率都是720×480的，是一個擁有廣泛的場景和視角的自然運動特征視頻庫。

圖4到圖6展示了相關結果，可以顯示出對今后做視頻分析很有用的許多細節，并且可以很好地處理本文選擇的數據集。

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

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

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

5 結束語

本文的方法不但可以以流的方式不間斷地工作，而且可以找到一個樹切片，這個樹切片不僅可以平衡所有被選擇節點所包含的信息量，而且可以同時考慮節點的信息量。通過包含的信息量選擇大的或者小的超體元，如果信息量少，就選擇大的超體元；反之，就會選擇小的超體元。光流被用來作為一個后置的特征標準去驅動信息的選擇，它跟原始的超體元處理無關。實驗結果表明這種方法不但能以流的方式工作，而且可以獲取更高質量的分割結果，同時在時間和內存方面的花費更少。

參考文獻：

[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.