一種基于凸殼的壓縮域運動對象快速分割算法*

錢增磊，梁久禎

(江南大學物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122)

摘要：目前在H.264/AVC壓縮域分割領域中現(xiàn)有的方法存在時間復雜度高，且分割運動對象不完整的問題，提出一種新的基于凸殼的壓縮域運動對象快速分割(CHSTF)算法。該方法主要利用碼流中的運動矢量場信息進行分割，即首先利用后向迭代累積對MV進行歸一化處理，再利用時空域濾波(STF)算法對運動矢量場進行濾波得到穩(wěn)定MV場，然后對濾波MV場求解凸殼并對其進行區(qū)域填充，最后對其進行優(yōu)化掩膜達到分割運動對象的效果。本方法著重于快速求得整體運動對象，并獲得較好分割精準度。實驗表明，通過本方法能夠較好地解決上述問題，并且在運動場嚴重缺失的環(huán)境下，相比傳統(tǒng)方法，本方法能獲得更好的效果。

關鍵詞：壓縮域；快速分割；運動矢量；時空域濾波；凸殼

中圖分類號：TP391.4 文獻標志碼：A

doi:10.3969/j.issn.1007-130X.2015.06.024

收稿日期：*2014-03-06;修回日期：2014-09-09

基金項目：國家自然科學基金資助項目(61170121)

作者簡介:

通信地址：214122 江蘇省無錫市江南大學物聯(lián)網(wǎng)工程學院

Address:School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,Jiangsu,P.R.China

Afastsegmentationalgorithmbasedonconvexhullforobjecttrackingincompresseddomain

QIANZeng-lei,LIANGJiu-zhen

(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi214122,China)

Abstract:Most of the current segmentation algorithms in compressed domain are often time-consuming and have incomplete segmentation for moving objects. In this paper,based on convex-hull we propose a novel fast segmentation algorithm for object tracking in compressed domain. This algorithm mainly utilizes information of the motion vector field in bits stream to do segmentation.Firstly,an iteratively backward projection scheme is proposed in normalization to obtain an accumulated motion vector filed.Then the spatio-temporal filter (STF) algorithm is used to preprocess the motion vector field to obtain the stable MV field.The filled MV field is subsequently searched for building a convex hull and filling the region.Finally,the segmentation is accomplished after optimizing and forming a mask.The proposed method focuses on fast obtaining the whole moving object and a better segmentation accuracy,and the experimental results show that it can work well even when motion vector is severely lacking,and is better than the traditional methods.

Keywords:compresseddomain;fastsegmentation;motionvector;spatio-temporalfilter;convexhull

1引言

運動對象分割的方法主要基于像素域和壓縮域，像素域的分割方法現(xiàn)在已頗為成熟，分割的精度高，但其分割速度受其分辨率的影響頗大，隨著視頻分辨率的逐漸提高，像素域的分割漸漸無法滿足其實時性，分割速度到了瓶頸的狀態(tài)，于是提出了壓縮域的分割方法。壓縮域的分割雖然在精度上無法與像素域匹極，但其快速的分割算法使其在視頻檢索與監(jiān)控領域中發(fā)揮了極其重要的作用。

壓縮域分割算法主要有濾波算法和聚類算法兩類。在濾波算法中，主要有三種算法[1～3]，其中MouraRC[3]提出了時空域的濾波方法STF(Spatio-TemporalFilter)。該方法結合了MV空域和時域上的雙重相關性來濾除噪聲并保留運動對象MV。該方法也成為了現(xiàn)在壓縮域?qū)ο蠓指钪兄饕臑V波算法。在分割算法中，基于MPEG視頻操作的有最大期望算法EM(ExpectationMaximization)[4]、區(qū)域生長方法VG(VolumeGrowth)[5]以及多內(nèi)核均值漂移分割MMS(MultikernelMeanshiftSegmentation)[6]等。但是，這些方法都要同時具有MV場合DCT殘差系數(shù)，其計算復雜度也很高。H.264/AVC是現(xiàn)在主流的高壓縮視頻標準，其分割方法主要有馬爾可夫隨機場分割MRF(MarkovianRandomField)[7]，Solana-CipresC等人[8]在2009年提出的基于模糊集的動態(tài)聚類DDOFS(DynamicDesignOfFuzzySets)以及2010年WangPei等人[9]提出的基于壓縮域蟻群算法的分割ACA(AntColonyAlgorithm)。除了這些還有一些新興的方法，如2012年LuY等人[10]提出的基于背景估計的算法，通過用幀間的編碼模式來估計出背景區(qū)域，從而降低全局運動補償?shù)臅r間。同年SunL等人[11]利用宏塊編碼的模式來估計運動區(qū)域，快速高效，但是僅限于室內(nèi)等外界環(huán)境不變的條件。2013年DevKS等人[12]結合過去前人方法的共同特征提出了一種綜合性方法，首先根據(jù)宏塊信息進行分類，然后利用全局運動估計和運動補償去除噪聲，再利用馬爾科夫隨機場來勾勒出粗分割區(qū)域，最后通過匹配策略來重新優(yōu)化邊界。

為了充分發(fā)揮H.264/AVC標準的特性，在滿足實時性的要求上，本文提出了一種基于凸殼(ConvexHull)的運動對象快速分割方法。該方法能夠解決運動矢量缺失造成的分割運動對象不完整的問題，并且由于凸殼[13]點計算的低復雜性，大大提高了分割的速度。

2MV場濾波算法

2.1運動估計

本文采用的是JM8.6平臺的H.264編碼器，該平臺的MV是基于4×4pixel，搜索算法為基于菱形的三步搜索算法DTSS(DiamondThreeStepSearch)，該算法結合了三步搜索算法的快速性與菱形搜索算法的精準性。采用的塊匹配準則是絕對差值和準則SAD(SumofAbsoluteDifference),其計算公式為：

(1)

其中,Ix,y(t)和Ix,y(t-1)為點(x,y)在當前幀和前一幀的灰度值，M×N是宏塊的尺寸，使得SAD最小的點，即為最優(yōu)的匹配點。

2.2MV預處理

由H.264/AVC編碼器編碼得到的MV存在很多噪聲。首先根據(jù)噪聲MV幅值較小的特點，通過設定一個閾值T，將噪聲MV濾除。該閾值較小，一般在零附近，防止閾值過高引起關鍵對象MV被錯誤濾除。

然后采用對連續(xù)N幀的MV進行累積，并求其平均MV。這里采用矢量化的迭代，如式(2)所示：

(2)

其中N(MVt→tref)是歸一化后的運動矢量。于是得出遞推關系式(3)如下：

(3)

根據(jù)式(3)得到圖1，經(jīng)過MV的后向迭代累積后發(fā)現(xiàn)運動對象的MV由于其方向的一致性而被突出了，而噪聲的MV由于其無序性而被縮小了，整個MV場被校正后，得到相對平穩(wěn)的運動場。

Figure 1　Iteratively backward projection of MV 圖1　MV后向迭代累積示意圖

2.3時空域濾波(STF)算法

STF[5]算法的核心思想就是將當前塊的MV與在空域與時域上鄰域塊的MV分別從幅值與方向兩個維度進行一致性比較，當偏離度過小時，即可將該MV視為運動對象的MV。

2.3.1MV的空域校正

噪聲MV具有空間局部性，這里采用對鄰域MV與當前MV的幅值和方向偏離程度作為運動對象MV的檢測標準。首先定義當前MV與鄰域MV的幅值偏離度：

(4)

同樣對于方向，定義當前MV與相鄰MV的方向偏離度為：

(5)

2.3.2MV的時域校正

運動對象不僅在空域內(nèi)具有相關性，在時域內(nèi)的相關性更加突出，根據(jù)后向迭代投影得到的相鄰幀之間的相應塊MV的投影關系，位置(x,y)t在前一幀中的投影為P(x,y)t→(t-1)，將對應MV的方向與幅值一起采用向量匹配比等式來計算：

(6)

式(6)可以計算出兩個不同幀MV之間的偏離程度，根據(jù)相對應的幀數(shù)不斷地計算t-1,t-2,…,t-n幀的偏離度，得到當前運動矢量的偏離度值：

(7)

3基于凸殼的分割算法

經(jīng)過STF濾波，噪聲MV已被大量濾除，同時運動對象MV也存在一并濾除的問題，但導致運動對象MV的局部缺失。為了解決這個問題并不影響整體算法的復雜度，現(xiàn)提出一種基于凸殼的分割算法，其核心思想是通過對濾波后的MV搜索邊界點，然后根據(jù)Graham掃描法求解凸殼，最后對其進行填充，彌補運動對象MV的缺失，形成完整的運動對象區(qū)域。

3.1構建凸殼算法

首先根據(jù)濾波后的MV場標記得到一個掩膜圖像MASK，運動對象MV標記為1，背景標記為0。由于MASK是由多個矩形塊組成的，為了降低凸殼求解復雜度，現(xiàn)提出如下的邊界點約束規(guī)則，見圖2a，其中網(wǎng)狀塊便是根據(jù)準則得到的邊界點。

condition1：ifMaski,j(t)正好在視頻區(qū)域邊界上，then該點為凸點；

condition2：ifMaski,j(t)不在視頻區(qū)域邊界上，andMaski-1,j(t)為0且Maski+1,j(t)為1，andMaski,j-1(t)為0且Maski,j+1(t)為1，then該點為凸點；

condition3：ifMaski,j(t)不在視頻區(qū)域邊界上，andMaski+1,j(t)為0且Maski-1,j(t)為1，andMaski,j-1(t)為0且Maski,j+1(t)為1，then該點為凸點。

Figure 2　Algorithm for constructing convex hull 圖2　構建凸殼算法

為降低計算復雜度，根據(jù)離散塊的特點，對搜索得到的邊界點進行改進Graham掃描[14]尋找凸點。其核心思路是通過確定一個邊界起點，然后利用與其起點的夾角進行排序，濾除部分邊界點，最后通過右手定則對邊界點進行統(tǒng)一方向搜索，從而得到最終的凸點，見圖2b。

凸殼求解完后需要對凸殼進行填充，對Mask中的塊是否在凸殼內(nèi)進行判斷，根據(jù)其離散性的特點，現(xiàn)提出一種射線法進行判斷，如圖3所示。步驟如下:

步驟1計算凸殼的區(qū)域區(qū)間，確定其掃描范圍，可大大縮短計算時間。

步驟2將每個塊的信息以每個塊的中心點代替，從而保證其凸殼邊界不會擴大。

步驟3在掃描區(qū)間內(nèi)向右做射線，若與凸殼邊界相交兩個點或沒有相交，則該點在凸殼外，將Maski,j(t)標記為0；若相交為一個點，則該點在凸殼內(nèi)，并將Maski,j(t)標記為1。

圖3中，外圍粗虛線邊框表示搜索塊的搜索區(qū)域，由凸殼的最大邊界確定，黑色虛箭頭表示射線掃描方向，灰色塊與斜線塊均表示根據(jù)算法填充的區(qū)域，斜線塊表示對先前缺失的部分進行的填充塊。

Figure 3　Process of filling convex hull 圖3　凸殼填充過程

3.2優(yōu)化掩膜

凸殼可能會造成運動對象的局部擴大，為盡可能貼近運動對象的真實形狀，根據(jù)前后幀的掩膜相關性，現(xiàn)提出如下優(yōu)化約束規(guī)則：

condition1：ifMaski,j(t-1)andMaski,j(t+1)同時為0，thenMaski,j(t)校正為0；

condition2：ifMaski,j(t-1)andMaski,j(t+1)同時為1，thenMaski,j(t)校正為1；

condition3：ifMaski,j(t-2)andMaski,j(t+1)同時為0，thenMaski,j(t)校正為0；

condition4：ifMaski,j(t-1)andMaski,j(t+2)同時為1，thenMaski,j(t)校正為0。

3.3算法復雜度分析

在壓縮域分割領域中，以塊為單位，若假設視頻幀分辨率為mpi×npi像素，那么壓縮域處理分辨率為：

(8)

設T1、T2分別為STF濾波部分時間與凸殼分割部分時間，其中STF濾波時間由MV預處理、空域濾波、時域濾波三部分時間組成：

(9)

(10)

綜上分析可得，本文算法的時間復雜度為：

T=T1+T2=

(11)

又由于一般情況下，r是一個小于1的系數(shù)，且在視頻幀中運動對象所占的MV數(shù)量比較小，故有θ>>r，所以本文算法的時間復雜度也可寫成O(θmn)。在處理視頻時，θ便固定為一個常數(shù)，對于本文算法，主要的處理時間是對每幀視頻的光柵掃描，所以該算法的復雜度是相當小的。

4實驗及結果分析

4.1分割效果實驗比對及分析

實驗采用三個序列文件，分別為Hall.264(共31幀)、Walk.264(共141幀)、Container.264(共171幀)，三個實驗序列均為352*288像素分辨率。本次實驗編碼器采用JM8.6版H.264編解碼器，平臺采用AMDAthlon(tm)ⅡX4 645處理器，主頻3.1GHz。圖4～圖6為分割效果圖。

Figure 4　Comparison of “Hall” sequence file in segmentation effect 圖4　Hall序列分割效果對比圖

圖4a、圖4e分別為序列第25幀與第27幀的MV場，圖4b、圖4f為采用STF濾波方法得到的效果圖，圖4c、圖4g為采用ACA分割方法得到的效果圖，圖4d、圖4h為采用本文方法(CHSTF)得到的效果圖。圖5a、圖5e分別為序列第49幀與第74幀的MV場，圖5b、圖5f為采用STF濾波方法得到的效果圖，圖5c、圖5g為采用ACA分割方法得到的效果圖，圖5d、圖5h為采用本文方法(CHSTF)得到的效果圖；上述效果圖是從原圖中截取觀察到的部分，分辨率為45*65。

Figure 5　Comparison of “Walk” sequence file in segmentation effect 圖5　Walk序列文件分割效果對比圖

圖6a為序列Container的MV場，圖6b為采用STF濾波方法得到的效果圖，圖6c為采用ACA分割方法得到的效果圖，圖6d為采用本文方法(CHSTF)得到的效果圖；上述效果圖是從原圖中截取觀察到的部分，分辨率為352*150。

Figure 6　Comparison of “Container” sequence file in segmentation effect 圖6　Container序列分割效果對比圖

從圖4可以看出，由于MV場的局部運動矢量缺失，導致在STF與ACA方法中運動對象掩膜MASK不完整，產(chǎn)生了運動對象分離的現(xiàn)象，而本文方法很好地解決了這個問題，彌補了運動對象的不完整性。由于本文方法在凸殼方法后加入了優(yōu)化掩膜的方法，使運動對象區(qū)域不會盲目擴大，于是有了圖4d的效果。由圖5可知，該運動對象較小，對于STF和ACA的分割效果都比較好，但仍然會存在局部信息的缺失，ACA雖然具有較好的聚合效果，但邊界精準度欠佳，CHSTF在此序列中仍能夠很好地解決這個問題。從圖5a、圖5b可知其MV場在邊界處比較明顯，且變動比較大，所以此處設定好閾值(Damp=0.8,Ddir=0.5)，便能夠分出邊界MV和外界信息。 由圖6a可知其運動場比較弱，由于運動對象運動的速度非常慢，在H.264/AVC編解碼器中的運動估計無法精確地獲得下一幀塊的位置，在運動對象中存在大量的MV缺失，為了保留盡可能多的MV，便會大大增加濾波和分割的難度，故對于此序列無法發(fā)揮STF與ACA的分割優(yōu)勢。從圖6b、圖6c中可以看到，STF方法效果比較差，而ACA雖然盡可能地恢復運動對象區(qū)域，但仍然無法完整，在聚類過程中將部分船身聚類成另一類。而CHSTF雖然彌補了MV場，盡可能地還原運動對象，但由于其船底部的MV場缺失嚴重，無法找到合適的凸點，就無法包括船底部區(qū)域。由于凸殼受外部噪聲點影響較大，會影響整個凸殼結構，所以在利用STF濾波過程中要盡可能濾除MV(Damp=0.3，Ddir=0.5)。

根據(jù)上述分割效果對其進行客觀分割效果評價，視頻序列分辨率均為352*288，總像素個數(shù)為101 376Pixel。表1為三種算法分割精準度對比。

Table 1　 Comparison of the three

從表1中可以看出，由于Walk序列的運動對象非常小，所以整體的準確度很高，而Container序列的運動對象龐大，導致整體的精確度相對較低，但從本文方法與STF和ACA算法比較中可以看出在精準度方面有微弱的優(yōu)勢，并且運動目標越大，其優(yōu)勢越明顯，因為殘缺的區(qū)域會越多。CHSTF能夠保證補全運動對象的缺失部分，雖然擴大了其邊界，但在整體的精準度上有較理想的效果。

4.2分割時間實驗比對及分析

本次實驗對本文方法(CHSTF)與STF濾波方法、蟻群算法(ACA)[11]、高斯混合模型算法(GMM)[15]進行時間復雜度對比，并對每一幀進行算法運行時間的比較。對比結果見表2和表3。

Table 2　 Comparison of the proposed algorithm and

表中，θ為鄰域(4,8)；T為迭代次數(shù)，一般為(10～50)；a表示每次迭代的聚類數(shù)；λ為每塊的像素數(shù)(λ=16)；g為高斯濾波個數(shù)。

Table 3　 Comparison of the proposed algorithm and

從表2中可以得到STF與本文算法時間復雜度相同，而GMM與ACA明顯高于兩者。從表3中可以看到，STF算法的時間是最小的，但該算法并沒有分割部分，只是對MV場的濾波，將具有特定特征的MV顯示出來，實質(zhì)并沒有識別出運動對象，所以該算法用于分割時很不穩(wěn)定，且?guī)в写罅啃畔⒌娜笔?。ACA算法是基于有監(jiān)督的聚類算法，有一個不斷的學習過程，所以該算法有大量的時間消耗。GMM算法是將一個事物分解為若干的基于高斯概率密度函數(shù)(正態(tài)分布曲線)形成的模型，有較好的分割正確率，但仍有大量的運算。在STF算法中測試Container序列時發(fā)現(xiàn)其運算時間超過本文方法，這是因為Container序列的運動對象比較龐大，需要計算的塊復雜度較高；而CHSTF是基于凸殼的分割，只需要MV場中幾個凸點便可完成對運動對象的提取，凸殼的計算量大為降低，才突顯出本文方法的速度性?；谕瑯拥脑?，ACA與GMM均在Container序列測試時存在大量的時間消耗。

5結束語

本文提出的基于凸殼的壓縮域運動對象快速分割方法，首先進行MV預處理，再使用STF算法對其進一步濾波，之后搜索MV對象凸殼點構建凸殼并對其進行填充，最后對其進行優(yōu)化制作成掩膜MASK圖像。從實驗結果顯示，在H.264/AVC高壓縮比的視頻壓縮標準中，在視頻會議及視頻監(jiān)控等不注重分割精度注重實時性的領域中，此方法能夠滿足其該領域的分割精度基礎上，能夠大大提高算法的速度，并補全運動對象，滿足其應用領域的實時性要求。需要指出的是，由于該方法受其外界噪聲點的影響較為嚴重，對濾波時的參數(shù)需要反復調(diào)試，盡可能地濾除噪聲點，故針對小運動單目標的應用領域比較突出。

參考文獻:

[1]SorwarG,MurshedM,DooleyL.Fastglobalmotionestimationusingiterativeleast-squareestimationtechnique[C]//Procofthe2003JointConferenceofthe4thInternationalConferenceonInformation,CommunicationsandSignalProcessing, 2003:282-286.

[2]AhmadAMA,ChenDY,LeeSY.RobustobjectdetectionusingcascadefilterinMPEGvideos[C]//Procofthe5thInternationalSymposiumonMultimediaSoftwareEngineering, 2003:196-203.

[3]MouraRC,HemerlyEM.Aspatiotemporalmotion-vectorfilterforobjecttrackingoncompressedvideo[C]//Procof2010 7thIEEEInternationalConferenceonAdvancedVideoandSignalBasedSurveillance(AVSS), 2010:427-434.

[4]VenkateshBR,RamakrishnanKR.Compresseddomainmotionsegmentationforvideoobjectextraction[C]//Procof2002IEEEInternationalConferenceonAcoustics,Speech,andSignalProcessing(ICASSP), 2002, 1:(IV)3788-3791.

[5]PorikliF,BashirF,SunH.Compresseddomainvideoobjectsegmentation[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology, 2010, 20(1):2-14.

[6]BashirF,PorikliF.Performanceevaluationofobjectdetectionandtrackingsystems[C]//ProcofIEEEInternationalWorkshoponPerformanceEvaluationofTrackingandSurveillance(PETS), 2006:1.

[7]ZengW,DuJ,GaoW,etal.RobustmovingobjectsegmentationonH. 264/AVCcompressedvideousingtheblock-basedMRFmodel[J].Real-TimeImaging, 2005, 11(4):290-299.

[8]Solana-CipresC,Rodriguez-BenitezL,Moreno-GarciaJ,etal.Real-timesegmentationofmovingobjectsinH. 264compresseddomainwithdynamicdesignoffuzzysets[J].Vectors, 2009, 4(4):16.

[9]WangPei,WuZhi-xia.MovingobjectsegmentationinH. 264/AVCcompresseddomainusingantcolonyalgorithm[C]//Procof2010 2ndInternationalConferenceonSignalProcessingSystems(ICSPS), 2010(V2):716-719.

[10]LuY,XuX.EfficientobjectsegmentationusingbackgroundestimationforH.264video[C]//Procof2012 8thInternationalConferenceonWirelessCommunications,NetworkingandMobileComputing(WiCOM), 2012:1-4.

[11]SunL,DaiM,ChenX.AsimpleandfastmovingobjectsegmentationbasedonH.264compresseddomaininformation[C]//Procof2012 4thInternationalConferenceonComputationalandInformationSciences(ICCIS), 2012:481-484.

[12]DeviKS,MalmuruganN,AmbikaH.MovingregionsegmentationfromcompressedvideousingglobalmotionestimationbymacroblockclassificationandMarkovrandomfieldmodel[C]//Procof2013InternationalConferenceonEmergingTrendsinComputing,CommunicationandNanotechnology(ICE-CCN), 2013:163-167.

[13]LiangJ,NavaraM.Implementationofcalculatingsteinerpointfor2Dobjects[C]//Procofthe2007InternationalConferenceonIntelligentSystemsandKnowledgeEngineering, 2007:15-16.

[14]ChanTM.Optimaloutput-sensitiveconvexhullalgorithmsintwoandthreedimensions[J].Discrete&ComputationalGeometry, 1996, 16(4):361-368.

[15]SongT,HanDK,KoH.Robustbackgroundsubtractionusingdatafusionforrealelevatorscene[C]//Procof2011 8thIEEEInternationalConferenceonAdvancedVideoandSignal-BasedSurveillance(AVSS), 2011:392-397.

錢增磊(1989-),男,浙江嘉興人，碩士生，CCF會員(E200036480G)，研究方向為機器視覺和視頻編解碼。E-mail:qianzenglei1989@163.com

QIANZeng-lei,bornin1989,MScandidate,CCFmember(E200036480G)，hisresearchinterestsincludemachinevision,andvideocodec.

梁久禎(1968-),男,山東泰安人，博士，教授，研究方向為機器視覺、圖像處理和模式識別。E-mail:jzliang@jiangnan.edu.cn

LIANGJiu-zhen,bornin1968,PhD,professor,hisresearchinterestsincludemachinevision,imageprocessing,andpatternrecognition.