程德強，姜海龍，鄭 珍，郭 政

(中國礦業(yè)大學 信息與電氣工程學院，江蘇 徐州 221008)

基于可變塊運動矢量的邊信息生成算法

程德強，姜海龍，鄭 珍，郭 政

(中國礦業(yè)大學 信息與電氣工程學院，江蘇 徐州 221008)

在分布式視頻編碼系統(tǒng)中，針對圖像中細節(jié)豐富的區(qū)域易造成嚴重的塊效應，提出了一種基于可變塊運動矢量的邊信息生成算法。根據(jù)前后相鄰關鍵幀對應塊的相關性，將像素塊分為保留塊和運動塊。對保留塊直接作保留處理，對運動塊中的像素塊繼續(xù)進行分割并計算子塊的初始運動矢量。再將全部塊的運動矢量通過加權自適應運動補償?shù)玫竭呅畔?。實驗結果表明，對于運動較劇烈復雜的視頻序列，該算法能夠提高邊信息生成質量， 并且使得改進后的邊信息PSNR值提高了0.98～1.33 dB。

視頻編碼；運動估計；塊分類；邊信息

近年來，隨著信息技術和無線網絡的飛快發(fā)展，多媒體數(shù)據(jù)視頻應用變得越來越普及。但是這些視頻應用受到設備的帶寬、電池耗電量、以及計算能力大小的問題，所以要求編碼端的復雜度很小但解碼端的復雜度可以很高，而以往的視頻編碼技術顯然已經不能達到這些要求，必須尋找到新的視頻壓縮技術。為克服這些缺陷，大家開始關注分布式視頻編碼框架，它具有很多優(yōu)勢，分布式無損編碼理論[1]以及解碼端邊信息的有損編碼理論[2]是DVC理論的依據(jù)所在。該分布式視頻編碼通過在解碼端充分利用信號的相關性，將復雜度從編碼端轉移到解碼端，其中邊信息生成的質量對于編碼性能發(fā)揮著十分關鍵的作用。因為生成的邊信息質量，直接影響到視頻壓縮的效率和圖像的效果。

對于如何得到更加準確的運動矢量仍是生成高質量邊信息非常重要的因素。Aaron等人提出了基于運動補償時域內插[3]，首先對已解碼的關鍵幀進行運動估計，然后計算幀間的運動軌跡，再依據(jù)在很短時間內物體做勻速直線運動假設的原理來估計邊信息。為了獲得更加準確的運動估計矢量，L.Natario 和J.Ascenso 等人提出對前后已解碼的關鍵幀進行前向和雙向運動估計[4-5]，并利用空間矢量平滑技術來平滑運動矢量場，進一步優(yōu)化運動矢量。紀濤等人提出了一種基于混合模型的邊信息預測算法[6]，該方法通過對塊匹配效果較差的區(qū)域采用光流法重新估計其運動矢量從而獲得效果較好的邊信息。S.Ye等人結合傳統(tǒng)運動估計，對已解碼的WZ幀重新進行運動估計[7]，得到更加精準的運動矢量。后來研究者們對于高質量邊信息的生成都是基于怎樣才能進行精確的運動估計，使得到的運動矢量更加接近真實的運動矢量。

以上這些方法都必須假設每個劃分的像素塊在很短的時間內進行勻速直線運動，但現(xiàn)實生活中的視頻序列幀幾乎沒有這樣假設的視頻，所以對于運動畫面較為劇烈的區(qū)域，就會造成生成的邊信息中宏塊與宏塊之間不連續(xù)和重疊的問題。針對上述問題，本文提出了一種可變塊運動矢量的邊信息生成算法，通過把宏塊劃分為尺寸更小的匹配塊進行搜索，以獲取更多運動矢量的細節(jié)，實驗結果表明，本文提出的改進算法能夠使生成的圖像質量有所提高。

1 分布式視頻編碼系統(tǒng)

1.1 基于像素域的分布式視頻編碼系統(tǒng)

像素域的分布式視頻編碼系統(tǒng)基于信源有損編碼理論，Aaron 等人提出了利用幀內編碼和幀間解碼的DVC結構[8]，如圖1所示。系統(tǒng)按照奇偶數(shù)將視頻序列分為關鍵幀(K幀)和Wyner-Ziv幀(WZ幀)兩種類型。在編碼端，K幀采用幀內編碼方式；WZ幀進行編碼時，應將對應位置的DCT轉換系數(shù)經過量化器進行量化，產生量化符號流，然后將量化符號流通過LDPC 編碼器生成校驗比特，緩沖器會暫時存儲系統(tǒng)的校驗碼。在解碼端，K幀只需要普通的幀內解碼即可，然后通過已解碼的K幀得到邊信息。然后，解碼器再利用收到的校驗比特和邊信息進行重構。在達到良好的解碼效果時所需的校驗比特就越少，系統(tǒng)的壓縮性能就越好。

圖1 Wyner-Ziv視頻編/解碼系統(tǒng)

1.2 傳統(tǒng)邊信息生成算法

邊信息是指對原始WZ幀的估計，生成方法中比較典型的有運動補償內插法和運動補償外推法，通過研究發(fā)現(xiàn)，內插法充分利用前后相鄰幀之間的相關運動信息，產生的邊信息較外推法效果更理想[9]。

1.2.1 前向運動估計法

生成前向運動估計的方法如圖2所示，Y2k表示需要生成的邊信息幀，X2k-1表示前關鍵幀，X2k+1表示后關鍵幀。為了預測插值幀Y2k中的塊B2k的運動矢量，首先在后一關鍵幀中找到與塊X2k+1相同位置的塊B2k，用B2k+1在前一關鍵幀X2k-1進行匹配計算，找到最佳匹配塊，通過B2k+1與B2k-1之間的位移矢量得出前后關鍵幀間前向運動矢量MV2k，由于宏塊的運動連續(xù)且視頻幀的時間間隔相同，因而B2k的前向運動矢量MVf2k為MV2k的一半，即滿足表達式(1)

MVf2k=MV2k/2

(1)

邊信息幀Y2k可由式(2)得到

Y2k(p)=X2k-1(p+MVf2k)

(2)

式中：p是邊信息中像素的坐標。

圖2 前向運動估計

1.2.2 雙向運動估計法

由于前向運動估計獲得的圖像容易發(fā)生相鄰塊區(qū)域的不連續(xù)和重疊現(xiàn)象，從而使獲得的運動矢量誤差較大，針對這一現(xiàn)象，J.Ascenso等人以前向運動估計為基礎，提出了雙向運動估計方法[10]，如圖3所示。

圖3 雙向運動佑計

雙向運動估計假設插值幀到前一關鍵幀的運動矢量和到后一關鍵幀的運動矢量是對稱的，即滿足式(3)和式(4)

(x1，y1)=(xk,yk)+MV(Bk)

(3)

(x2，y2)=(xk,yk)+MV(Bk)

(4)

式中：(x1,y1)和(x2,y2)分別表示X2k-1幀和X2k-1幀中相應宏塊的坐標；(xk,yk)生成的邊信息相應宏塊的坐標；MV(Bk)表示在前向運動估計中得到的運動矢量的一半。由于插值幀Y2k到前后兩個關鍵幀的時間間隔是相等的，從而可以得到估計的預測幀，如式(5)所示

(5)

1.2.3 自適應加權運動場濾波

通過雙向運動估計得到的運動矢量容易使某一塊的運動矢量的方向和周圍塊的運動方向不一致，從而使獲得的內插幀出現(xiàn)嚴重的塊效應問題，如圖4所示，獲得的運動矢量比較混亂，當前宏塊B0的運動矢量方向與其相鄰八個方向的宏塊的運動矢量截然相反，所以可以判斷B0宏塊的運動矢量很可能是一個局部最優(yōu)值，不能反映運動場的實際情況，會嚴重影響邊信息重建質量。為了改善這一缺陷，可以通過采用空域平滑算法來修正錯誤的運動矢量，因此卿粼波等人提出了一種自適應加權運動場濾波算法[11]，該算法通過有效利用塊匹配度和相鄰運動矢量的局部相關性，進而達到優(yōu)化孤立異常運動矢量的目的。

圖4 方向不一致的相鄰塊運動矢量

如圖4中為MVi(i=0,1,…,8)為B0塊及其相鄰8個塊的運動矢量，則B0塊進行自適應加權運動場濾波后輸出的運動矢量MV滿足式(6)

(6)

式中：權重wi由式(8)決定，將每個MVi(i=0,1,…,8)作為當前塊的運動矢量，由式(7)計算雙向運動矢量殘差D(MVi)

(7)

式中：(MVix,MViy)是候選塊的運動矢量。

wi=D(MV0)/D(MVi)

(8)

顯然，當D(MVi)越大，則權重wi越小，MVi輸出的可能性也就越小，反之亦然。

2 基于可變塊運動矢量的邊信息生成算法

運動估計的基本思想是將每一幀圖像分成多個互不重疊的宏塊，然后對每個宏塊進行運動搜索，找出與當前塊的相似度最高的宏塊，該塊即為匹配塊。然而對于區(qū)域運動豐富且變化多的視頻幀圖像，多個不同方向的運動矢量就可能存在于同一個宏塊里，導致宏塊的實際運動軌跡并非一個運動矢量就能表示。為了使得到的運動矢量場更加接近真實運動矢量場，可以考慮把這個宏塊劃分為尺寸更小的匹配塊進行搜索，以獲取更多運動矢量的細節(jié)[12]。所以本文提出了一種基于可變塊的運動矢量優(yōu)化算法。

2.1 對塊進行分類

本文采用的塊大小是16×16，將視頻序列的前關鍵幀X2k-1進行分塊，并將對應的像素塊標記為B2k-1,j，對后關鍵幀X2k+1進行分塊，并將對應的像素塊標記為B2k+1,j，同時將邊信息幀對應像素塊標記為B2k,j。

將前后關鍵幀X2k-1、X2k+1的對應像素塊B2k-1,j，B2k+1,j按照式(9)分別進行求和絕對誤差SAD計算，當SAD值越小時表明其相關性越強

(9)

由于視頻序列的運動復雜度不一樣，所以對于前后運動一致性較好的區(qū)域(如靜止的背景)采用較大的塊；而對于前后運動變化較大的區(qū)域(如運動的物體)采用較小的塊，并重新對這些小塊進行運動估計。通過以上分析，首先設定閾值T1，然后對求和絕對誤差值SAD和T1進行比較，將像素塊分為運動塊和保留塊兩類，如圖5所示。具體計算步驟如下：

1)計算各對應塊的SAD并與T1進行比較。若SAD大于T1，則認為像素塊對B2k-1,j和B2k+1,j的運動劇烈程度較大，將其像素塊對判定為運動塊，否則將其判定為保留塊。

2)對于運動塊，將該16×16的塊繼續(xù)劃分為8×8的子塊，并對這些塊做運動估計，重新計算SAD′的值，重新設定新的閾值T2，比較SAD′和T2的大小，若SAD′大于T2，則轉到第3步，并判定該子塊也是運動塊，否則是保留塊。

3)將8×8的運動子塊再劃分為4×4的子塊，并對這些塊做運動估計，算法結束。

圖5 可變塊的劃分

2.2 計算子塊初始運動矢量

由于運動矢量在空域上是高度相關的，因此可以根據(jù)式(7)，分別計算當前子塊B0的8個相鄰子塊的雙向運動矢量殘差D(MVi)，并認為該子塊的初始運動矢就是D(MVi)值最小的那個塊的運動矢量。但是如圖4所示，由于這8個子塊里面有的子塊可能來源于同一個父塊，會發(fā)生重復現(xiàn)象，但是以當前子塊為中心的兩條對角線上對應的4個子塊可以替代所有的8個相鄰塊，所以只要選取兩條對角線上的4個子塊即可[13]。具體計算步驟如下：

1)將內插幀16×16的圖像運動塊劃分為8×8的子塊，并把16×16塊的運動矢量設定為其對應的4個8×8子塊運動矢量，記為MV0。

4)經過步驟1)～3)，內插幀運動矢量場已由16×16的塊表示成8×8的塊，保證了運動矢量的精度，提高了圖像的主觀質量，重復步驟1)～3)，可以獲得更加平滑、精確的4×4級運動矢量場。

2.3 多候選運動補償

因為視頻運動具有不確定性、復雜性以及圖像噪聲等原因，通過以上步驟計算獲得的運動矢量會存在一定的誤差，會使生成的邊信息幀中出現(xiàn)嚴重的塊效應。為了克服上述缺陷，重疊塊運動補償方法可以減少塊效應和改善圖像質量，但是容易產生模糊和過平滑現(xiàn)象。因此，本文采用一種基于多候選運動矢量的加權自適應運動補償算法來得到質量更高的邊信息。

由于都是根據(jù)多假設運動補償?shù)姆椒?，因此本文提出的補償算法與重疊塊運動補償原理一樣。多假設運動補償是基于去噪的思想，選擇多個質量差不多的運動補償預測信號作為原始信號的候選信號，然后將多個預測信號加權線性組合處理，就達到去噪的目的，從而獲得了更加精確的預測值[14]。

如圖6所示，由當前塊及其相鄰塊的運動矢量一起當著當前塊的候選運動矢量集，每個候選矢量都可以生成一個預測信號Yi，如式(10)所示

X2i+1(m-MVkx,n-MVky)]

(10)

式中：(m,n)表示當前塊；i∈[0,N]是候選塊的系數(shù)索引；(MVkx,MVky)是候選塊的運動矢量。當進行線性組合時，各個預測信號的質量決定預測信號的權值wk，通常情況，雙向預測誤差越小，表示前向和后向運動補償塊的匹配度越高，生成當前塊的預測質量效果就越佳，因此wk由式(11)表示為

wk= (X2k-1(m+MVkx,n+MVky)-

X2k+1(m-MVkx,n-MVky))-1

(11)

加權自適應的運動補償插值結果Y2k(m,n)如式(12)所示

(12)

3 實驗結果及分析

本文分別選擇對Foreman序列和Coastguard序列的前100幀進行編碼測試，其中Foreman序列背景時有鏡頭搖晃的場景，前景運動強度中等，Coastguard紋理豐富細節(jié)變化多，運動強度中等。實驗條件及假設：序列格式均為QCIF(176×144)，設置系統(tǒng)GOP為2，且認為K幀能完好地傳到解碼端。為更好地說明算法的優(yōu)越性，在進行測試過程中只考慮WZ幀亮度分量部分。實驗結果如圖6和圖7所示。圖6a和圖7a分別表示Foreman序列和Coastguard序列的第25幀(前關鍵幀)，圖6b和圖7b分別表示Foreman序列和Coastguard序列的第27幀(后關鍵幀)，圖6c和圖7c分別表示Foreman序列和Coastguard序列的第26幀(WZ幀)，圖6d和圖7d分別表示Foreman序列和Coastguard序列用本文算法生成的邊信息。從圖中可以看出本文算法生成的邊信息幀基本上與原始幀沒有差別。

圖6 本文算法生成的Foreman邊信息

圖7 本文算法生成的Coastguard邊信息

計算邊信息的PSNR值采用如下方式：1)單向運動估計；2)雙向運動估計；3)AWMFF；4)可變宏塊大小法。測試結果如表1所示。

表1 不同算法生成邊信息的PSNR值比較dB

圖像PSNR單向雙向AWMFF可變宏塊Foreman3421345034723548Coastguard3372339134213505

如圖8和圖9所示，F(xiàn)oreman序列和Coastguard序列對應3種不同方法下的PSNR分布曲線。

圖8 Foreman序列相應生成邊信息幀的PSNR分布圖

圖9 Coastguard序列相應生成邊信息幀的PSNR分布圖

從圖表可以看出，相比單向運動估計，采用雙向運動估計方法可以使塊效應減少，更加接近真實的圖像效果。由于AWMFF方法剔除了運動估計環(huán)節(jié)產生的部分錯誤運動矢量，使運動矢量更接近真實的運動軌跡，從而提高了圖像的PSNR值。另外，通過圖表可以發(fā)現(xiàn)，本文提出的改進算法生成的邊信息質量，在整個視頻序列上幾乎都要優(yōu)于其他方法。在碼率相同的情況下，對于Foreman序列，改進的算法相比單向運動估計和雙向運動估計，分別提高了1.27 dB和 0.98 dB。 而對于Coastguard序列，改進的算法相比單向運動估計和雙向運動估計，分別提高了1.33 dB和1.14 dB。如圖10和 圖11 所示，還可以通過邊信息的運動矢量圖來分析物體的運動情況，結合圖6和圖7，可以發(fā)現(xiàn)運動矢量圖與Foreman序列和Coastguard序列的運動情況基本保持一致。由此可見，本文算法通過在解碼端進行更為精確可靠的運動估計，使產生的邊信息圖像與原始幀誤差最小，即效果最好。

圖10 Foreman序列第26幀的邊信息運動矢量圖

圖11 Coastguard序列第26幀的邊信息運動矢量圖

4 結束語

如何生成更加準確的邊信息是DVC系統(tǒng)中一個非常關鍵的技術。本文提出的基于可變塊運動矢量的邊信息生成算法，通過把宏塊劃分為尺寸更小的匹配塊進行搜索，以獲取更多運動矢量的細節(jié)。實驗結果表明，本文采用的算法對運動較為劇烈復雜的視頻序列效果更為理想，從而提高了系統(tǒng)的性能。對于今后的研究方向，研究者們可以針對不同運動劇烈程度的視頻序列，研究怎樣才能有效對塊的大小進行分類，從而使系統(tǒng)的編碼性能縮小與H.264 Inter編碼方式的差距。

[1] SLEPIAN J D，WOLF J K. Noiseless coding of correlated information sources[J].IEEE Trans. Information Theory，1973(19)：471-480.

[2] WYNER A D，ZIV J. The rate-distortion function for source coding with side information at the decoder[J]. IEEE Trans. Information Theory，1975，22(1)：1-10.

[3] WORK C K，OSCAR C A. Fast motion compensated temporal interpolation for video[C]//Proc. Process of SPIE.Taipei，China：SPIE Press，1995：1108-1118.

[4] NATARIO L，BRITES C，ASCENSO J，et al. Extrapolating side information for low-delay pixel domain distributed video coding[C]//Proc. Int. Workshop on Very Low Bitrate Video Coding.[S.l.]：IEEE Press，2005：2-17.

[5] ASCENSO J，BRITES C，PEREIRA F. Improving frame interpolation with spatial motion smoothing for pixel domain distributed video coding[C]//Proc. 5th EURASIP Conf. on Speech and Image Processing，Multimedia Communications and Servers. Smolenice，Slovak Republic：[s.n.]，2005：65-69.

[6] 紀濤.分布式視頻編碼中基于混合模型的邊信息生成算法[J].微電子學與計算機，2010，38(9)：16-19.

[7] YE S，OUARET M，DUFAUX F. Improved side information generation with iterative decoding and frame interpolation for distributed video coding[C]//Proc. 15th International Conference on Image Processing. San Deigo，USA：IEEE Press，2008：2228-2231.

[8] AARON A，ZHANG R，GIROD B.Wyner-Ziv coding of motion video[C]//Proc. Conference Record of the Asilomar Conference on Signals，Systems and Computers.[S.l.]：IEEE Press，2002：240-244.

[9] 尹明，蔡述庭，謝云.基于高斯混合模型的Wyner-Ziv視頻編碼[J].計算機學報.2012，34(1)：173-182.

[10] ASCENSO J，BRITES C，PERELRA F. Motion compensated refinement for low complexity pixel based distributed video coding[C]//Proc. IEEE International Conference on Advanced Video and Signal Based Surveillance. Como，Italy：IEEE Press，2005：1-5.

[11] 卿粼波，何小海，呂瑞，等.分布式視頻編碼中邊信息的多策略優(yōu)化[J].四川大學學報，2008，39(12)：7-12.

[12] 全子一.圖像信源壓縮編碼及信道傳輸理論與新技術[M].北京：北京工業(yè)大學出版社，2006.

[13] 劉東，杜明輝.基于塊的分布式視頻編碼邊信息生成技術[J].華南理工大學學報：自然科學版，2011(39)：32-38.

[14] 馬力，蘇卓涵，楊春玲.基于多假設運動補償預測的邊信息改進方法[J].計算機工程,2011，28(2)：71-72.

責任編輯：時 雯

Side Information Generation Algorithm Based on Variable Block Motion Vector

CHENG Deqiang，JIANG Hailong，ZHENG Zhen，GUO Zheng

(DepartmentofInformationandElectricalEngineering，ChinaUniversityofMiningandTechnology，JiangsuXuzhou221008，China)

Aiming at the problem that areas which have rich details can result in serious blocking effects in a distributed video coding system，a side information generation algorithm based on variable block motion vector is proposed.The pixel blocks are divided into preservation blocks and motion blocks according to the correlation between the blocks in adjacent key frames.The preservation blocks are directly retained， and the pixel blocks existed in the motion blocks are continued to divide and its initial motion vectors of the sub-blocks are calculated.At last，in order to get improved side information，it uses the method of weighted adaptive motion compensation to process all the motion vectors of corresponding blocks.The experimental results show that， for the video sequence is severely complex， this algorithm can improve the quality of the side information generation and the PSNR of the improved method proposed in this paper can increase by 0.98～1.33 dB.

video coding； motion estimation； block-classified； side information

國家自然科學基金項目(51204175)

TN919.8

A

10.16280/j.videoe.2015.19.001

程德強(1979— )，教授，博士生導師，主要研究方向為圖像處理與視頻信號編碼、多媒體信息傳輸；

姜海龍(1988— )碩士生，主要研究方向為視頻信號編碼與圖像處理技術；

鄭 珍(1989— )，女，碩士生，主要研究方向為多媒體圖像傳輸、寬帶網絡技術；

郭 政(1990— )碩士生，主要研究方向為礦井圖像處理及應用。

2015-03-14

【本文獻信息】程德強，姜海龍，鄭珍，等.基于可變塊運動矢量的邊信息生成算法[J].電視技術,2015，39(19).