基于改進期望最大化算法的分布式視頻編碼

李志宏，王海芳

(太原科技大學數字媒體與通信研究所，太原 030024)

隨著3G通信技術的飛速發展，低能耗視頻攝取設備大量涌現，如移動攝像機、無線傳感器網等。由于這些設備的電池能量和內存非常有限，它們要求復雜度低的編碼算法，而其解碼端由于連接強計算能力的中心計算機(比如移動基站等)，可以容忍復雜度較高的解碼算法。這種要求和傳統視頻編碼的“高復雜度編碼低復雜度解碼”特點形成對比(如H.264，由于其編碼端使用了復雜的運動估計算法，其編碼算法大致是解碼算法的5-10倍)，對傳統算法提出了挑戰。

分布式視頻編碼(Distributed Video Coding，DVC)[1]是適應低復雜度編碼而出現的一種新型視頻編碼方法，其框架如圖1所示。視頻幀分為關鍵幀(Key frame)和Wyner-Ziv幀(WZ frame)，對關鍵幀采用傳統的幀內編解碼方法，對WZ幀采用一種“獨立編碼聯合解碼”的方式，即編碼端對各個幀不利用時域相關性進行獨立編碼(對WZ幀僅利用一個量化器和信道編碼，編碼端僅傳輸信道編碼產生的伴隨式s)，而解碼端利用相鄰幀的時間相關性進行解碼(首先利用已解碼的相鄰幀產生邊信息，然后用邊信息進行信道解碼和量化重構)，從而將運動估計等計算量較大的去時域相關算法從編碼端轉移到解碼端，實現了復雜度較低的編碼算法(雖然其解碼端造成了較高的計算復雜度)。DVC的這些特點使其非常適用于上述的低能耗視頻攝取設備。

DVC中，邊信息(Side information，SI)是一個很重要的因素，它是由相鄰幀根據時域相關性采用內插(Interpolation)或者外插(Extrapolation)產生的信息。一般而言，邊信息越精確，則整個DVC系統的性能越好。為了提高邊信息的性能，現有DVC方案利用解碼端恢復的相鄰幀進行運動估計內插以產生邊信息[1-2]，然而，因為恢復幀不準確引起了不準確的運動估計，最終造成邊信息性能的下降。為進一步提高邊信息性能，Aaron提出一種hash邊信息算法[3]，編碼器將當前WZ幀的某些特征(如小波高頻系數)表示為hash并傳到解碼器，解碼端利用hash輔助運動估計，從而提高運動估計可靠性，并最終得到高性能的邊信息。然而，由于編碼端需要傳送hash信息，會增加系統的碼率，從而影響整體系統性能。在上述兩種邊信息基礎之上，D.Varodayan等提出一種無監督學習運動矢量[4-6]的邊信息生成方法，利用Wyner-Ziv碼流來學習前向運動矢量，稱之為期望最大化算法(Expectation Maximization，EM)。實驗結果表明，EM是目前性能最好的邊信息生成方法，但同時也是計算復雜度最高的方法。對此，為進一步提高EM算法的實用性，需要在保持其性能的前提下，減低其算法的復雜度。在這種動機下，通過深入研究EM算法的原理，提出了兩種EM的改進算法，在保持性能的前提下，降低了算法的復雜度。

圖1 分布式視頻編碼框架Fig.1 DVC framework

1 期望最大化算法

期望最大化——EM算法分為兩個基本步驟:M-step和E-step，如圖2所示。

圖2 基于無監督運動矢量學習的EM算法Fig.2 EM algorithm with unsupervised motion vector learning

考慮視頻中兩個連續幀X和Y，其中X是量化版本，Y是解碼端的重構版本。設X與Y之間圖像塊的前向運動矢量場用M表示。EM算法的基本思想是:編碼端對X幀進行低密度奇偶校驗(Low Density Parity Check，LDPC)編碼并逐步發送伴隨式比特s，解碼端通過M-step算法從LDPC解碼流中計算X的軟估計θ值，通過E-step將θ與Y值進行比較得到運動矢量場的后驗概率值。反復迭代M-step和E-step，可以使軟估計θ值和運動矢量場M得到不斷更新，邊信息ψ也將隨M更新而更新，最終找到精確的運動矢量場和精確的邊信息。這里，類似于目前所有的DVC方案，LDPC利用接收到的伴隨式s和邊信息進行迭代解碼，如果迭代次數超過預定的次數仍不能解碼成功，則通過反饋信道要求發送額外的伴隨式比特并重新進行上述的迭代解碼。當硬估計產生的伴隨式比特等于s時，解碼成功。

在EM算法中有兩點需要引起注意，其一，運動矢量M表示相鄰兩幀圖像塊之間的運動情況，其值反映了當前塊向某個方向運動的概率大小，會隨著LDPC迭代解碼而更新，因此，在LDPC迭代解碼之前，需要預先設定一個運動矢量場M以引導每次迭代中M-step和E-step的更新，從而一定程度上決定邊信息的性能。其二，E-step利用每次迭代產生的軟估計θ值在參考幀中進行搜索并更新運動矢量場M，每次搜索都采用基于塊的正方形區域全搜索法，因此造成很大的計算量。本文正是針對這兩方面的問題展開研究，實現了EM的兩種改進算法。

2 基于菱形搜索改進的EM算法

2.1 算法設計

由以上介紹可以看出，EM算法在整個壓縮過程中使用了最耗費計算資源的塊匹配運動搜索來更新運動場。EM需要反復進行E-step和M-step步的迭代，反復進行運動矢量場的更新，因此將花費大量時間。在塊匹配運動搜索中，搜索模式設計應符合視頻的運動矢量概率分布特征。因此，可利用視頻的運動分布特征對EM算法進行改進。

文獻[7]的分析和實驗結果表明，在多種常用的塊匹配算法中，當折中考慮搜索性能和速度時，菱形搜索(DS)在是最優的。然而，由于單純DS算法難以與EM算法結合，因此將采用一種固定的菱形搜索模板，如圖3所示。這個模板中，固定地使用正方形的菱形中心，由于菱形中心反映了相鄰視頻幀之間圖像塊的運動規律(即圖像塊向下一幀中相同位置(即中心位置)運動的概率大，向遠離中心位置運動的概率小)，因此這種算法可以很快找到全局最小值，并且搜索性能接近正方形模板全搜索。

圖3 菱形模板搜索范圍Fig.3 Searching region of diamond model

圖4 改進的EM算法Fig.4 Improved EM algorithm

如圖4所示，左下圖中，虛線的正方形區域表示文獻[6]中EM的全搜索區域，實線的菱形區域表示根據圖3的菱形模板所確定的搜索區域。基于菱形搜索的EM算法具體步驟為:對X中的每個k×k塊，根據其LDPC解碼后的軟估計θ值在中Y的菱形區域進行搜索(替代正方形區域的全搜索)，計算運動矢量的概率模型，將此概率模型值與Y中保存的概率模型進行加權和運算求得ψ，并用ψ更新中Y的概率模型。重復下列過程:LDPC迭代解碼→基于軟估計θ值進行菱形模板運動搜索→估計運動矢量概率模型→求得ψ并更新Y→直到某位置的概率達到最大值1，即為最佳的運動矢量，從而得到最好的邊信息Y.

由圖3可以看出，菱形模板搜索次數只有正方行模板的13/25，因此，大大降低了搜索時間;同時，由于菱形窗模板考慮到圖像塊的運動特點(遠離中心點的運動概率小，靠近中心點的運動概率大)，因此，基于菱形模板的運動搜索的性能與正方形相差不大。這里，所采用的菱形搜索初始概率根據式(6)來確定:

其中，u和v分別表示運動矢量的水平和垂直分量，Mu，v表示運動矢量(u，v)的概率，搜索范圍為:u∈[－2，2]，v∈[－2，2]。

2.2 實驗結果與分析

根據文獻[6]提供的程序代碼，實現了變換域分布式視頻編碼，框架如圖5所示。編碼端對WZ幀進行分塊DCT(即，塊離散余弦變換)，然后對變換所得系數進行量化。上述的改進EM算法用于框架中的運動估計部分。利用兩個標準的視頻序列:Foreman和Hall@30 Hz進行測試，運動矢量估計在水平和垂直方向5個像素的范圍內，即u∈[－2，2]，v∈[－2，2]。最大迭代次數為50次。

圖5 基于EM的變換域分布式視頻編碼Fig.5 DVC based on EM Transform domain

實驗結果如圖6和圖7所示，比較了三種算法的率失真(rate-PSNR)性能，包括理想運動矢量、文獻[6]中的正方形模板EM和本文提出的菱形模板EM，相對應的搜索時間如表1所示。結果表明，菱形模板EM算法比文獻[6]中的正方形模板EM節省了30%的搜索學習時間，但其性能并沒有明顯下降。

圖6 GOP=8的Foreman率失真性能Fig.6 Rate-distortion performance of Foreman sequence when GOP=8

圖7 GOP=8的Hall率失真性能Fig.7 Rate-distortion performance of Hall sequence when GOP=8

表1 兩種算法的學習時間比較Tab.1 Comparison of learning time of two methods

3 基于自適應初始概率改進的EM算法

3.1 算法設計

由上述分析可知，在EM算法運動矢量概率模型M的學習過程中，初始概率模型起著關鍵的作用。文獻[6]中，EM算法采用了固定的概率模型，忽略了視頻幀間運動矢量的多變性，對此，提出了根據視頻的實際運動情況采用一種自適應的概率模型來進行改進，即在編碼端首先判斷幀的運動情況，然后根據運動情況預定初始的概率模型。具體而言，采用相鄰兩幀差的絕對值SAD來判斷兩幀之間的運動情況，如果SAD值大于某個事先設定的閾值，則認為這兩幀之間的運動幅度較大，將采用中心概率值小的初始概率模型;如果SAD值小于某個事先設定的閾值，則認為這兩幀之間的運動幅度小，將采用中心概率值大的初始概率模型;其余塊的概率再根據中心概率而定。根據實驗確定閾值Th，每塊的初始化運動矢量概率Mu，v如下，

當兩幀之間的SAD值大于設定的閾值Th時，給中心點概率Xdcenter和Ydcenter賦較小的概率值，相反，當SAD小于閾值Th時，給Xdcenter和Ydcenter賦一個較大的概率值，其他方向的概率會隨著中心概率值的變化而變化。

3.2 實驗結果與分析

采用相同的實驗環境。經過大量實驗，對于Foreman視頻序列，取閾值Th=200000.如果閾值SAD ＞ Th，則 Xdcenter=Ydcenter=0.7;否則 Xdcenter=Ydcenter=0.8.

對于Hall視頻，因為序列整體運動較緩慢，將EM算法的中心概率定為Xdcenter=Ydcenter=0.9，取閾值Th=500000，如果SAD ＞ Th，Xdcenter=Ydcenter=0.8;否則，Xdcenter=Ydcenter=0.9.

表2是兩個概率模型在相同率失真性能下的學習時間比較，很明顯，概率自適應EM算法在保持同樣的率失真性能下，節約了16%的學習時間。

表2 兩種算法的學習時間比較Tab.2 Comparison of learning time of two methods

4 結論

EM算法是一種相對優異的DVC產生邊信息的方法，它是基于塊的全搜索對產生的運動矢量進行學習。由于全搜索非常耗時使得EM的學習時間很長，因此，本文提出了采用菱形搜索優化的改進EM算法，減少了搜索點，并能很快找到全局最小值。同時，由于在運動矢量概率模型的學習過程中，初始概率模型起到很關鍵的作用，對此，本文提出采用基于初始概率模型自適應的EM算法。實驗結果表明，基于菱形搜索的EM算法和初始概率自適應的EM算法在保持同樣的率失真性能下，分別節約了30%和16%的學習時間。

[1]GRIOD B，AARON A，RANE S.Distirbuted Video Coding[J].Proceedings of the IEEE，2005，93(1):71-83.

[2]WYNER A，ZIV J.The Rate-distortion Function for Source Coding with Side Information at the Decoder[J].IEEE Transaction on Information Theory，1976，22(1):1-10.

[3]AARON A，RANE S，GRIOD B.Wyner-Ziv Video Coding with Hash-based Motion Compensation at the Receiver[C]//IEEE Int Conf Image Processing，Singapore，2004:3097-3100.

[4]VARODAYAN D，MAVLANKAR A，FLIERL M，GIROD B.Distributed grayscale stereo image coding with unsupervised learning of disparity[C]//IEEE Data Compression Conf，Snowbird，UT，2007:143-152.

[5]VARODAYAN D，LIN Y C，MAVLANKAR A，FLIERL M，GIROD B.Wyner-Ziv coding of stereo images with unsupervised learning of disparity[C]//Picture Coding Symp，Lisbon，Portugal，2007.

[6]VARODAYAN D，CHEN D，FLIERL M，GIROD B.Wyner-Ziv coding of video with unsupervised motion vector learning[J].Signal Processing:Image Communication，2008，23(5):369-378.

[7]Aroh Barjatya.Block matching algorithm for motion estimation[J].IEEE Transactions Evolution Computation，2004，8(3):225-239.