基于3D相鄰區域宏塊相關性的多視點視頻快速編碼算法

明 艷

(重慶郵電大學 通信學院，重慶 400065)

基于3D相鄰區域宏塊相關性的多視點視頻快速編碼算法

明 艷

(重慶郵電大學 通信學院，重慶 400065)

針對多視點視頻編碼的高復雜度，提出一種利用相鄰宏塊編碼信息的相關性進行編碼的快速算法。利用多視點視頻相鄰宏塊率失真代價分布的相關性，對當前宏塊進行SKIP模式下的提前判決；根據視點間、時間和空間相鄰區域運動矢量差值對當前宏塊運動類型進行快速分類；針對不同的運動類型調整搜索范圍，選擇相應尺寸大小的編碼模式。通過對具有不同運動特性的多視點視頻編碼性能測試，結果表明，相對于聯合多視點視頻模型(joint multi view video model，JMVM)遍歷模式，在增加0.75%輸出比特率和降低0.04 dB峰值信噪比的情況下，該快速編碼算法能平均減少66%的編碼時間。

多視點視頻編碼；快速算法；相關性；性能測試

0 引 言

多視點視頻是由不同視點的多個攝像機從不同視角拍攝同一場景采集到的一組視頻數據，由于能生動地再現立體感場景，提供交互功能，廣泛應用在自由視點視頻[1]、3D電視、遠程醫學診療、視頻監視等多媒體業務中。因多視點視頻的數據量隨攝像機的數目增加呈線性增長，如何對多視點視頻數據進行高效壓縮是其應用普及和推廣的關鍵。2006年，ITU-T的視頻編碼專家組(video coding experts group，VCEG)和國際標準化組織/國際電工委員會(international organization for standardization/international electrotechnical commission，ISO/IEC)的運動圖像專家組(moving picture experts group，MPEG)完成了多視點視頻編碼的標準化工作，并作為H.264標準的擴展部分。該標準通過對所有尺寸大小模式進行遍歷得到最優模式[2]的方法雖然提高了壓縮性能，但帶來了極高的運算復雜度。

目前多視點視頻編碼快速算法主要分為2類：①優化拉格朗日率失真函數；②最佳模式的提前判決[3]。Zhu[4]提出的快速算法是先利用幀內編碼信息對當前宏塊進行紋理區域分割，然后通過相鄰視點間相同紋理區域SKIP宏塊的率失真代價值對SKIP模式進行提前判決，由于該算法只對SKIP模式進行了快速判決，降低編碼復雜度的效率還有待提高；在文獻[5]中，先計算相鄰視點間SKIP模式的加權因子，如果加權因子大于閾值，判決為SKIP模式，提前終止模式遍歷。該方法在減小運算量方面雖取得了一些效果，但并沒有充分利用時間和空間編碼信息的相關性；Shen[6]提出了一種基于視點間運動矢量的尺寸大小模式選擇方法，根據視點間相鄰宏塊運動矢量的變化來對當前塊運動類型進行判決，但該方法對某些序列效果較差；文獻[7]提出了一種利用視點間率失真代價值的信息對當前塊的紋理區域進行判決，但該方法并沒有對占用編碼時間較大的尺寸大小的模式進行快速判決；文獻[8]提出了通過攝像機的幾何位置關系來減少搜索范圍，因此，需要一些攝像機的位置信息，且只對某些特定的序列效果較好。Zeng[9]使用了3D相鄰區域宏塊的運動矢量信息來對當前塊的運動類型進行分類，不同的運動類型只選擇相應的尺寸大小的模式。該方法能有效地減少編碼復雜度，但對運動類型一致的宏塊編碼效果不好。

本文提出了一種利用視點間、時間和空間的3D相鄰區域的宏塊編碼信息對當前塊進行快速編碼的算法。首先，計算已編碼相應視點的率失真代價值，對當前宏塊做SKIP模式快速判決；然后，通過當前塊3D相鄰宏塊的運動矢量差值信息，對塊的運動類型進行快速分類，并根據確定的運動類型動態調整搜索范圍；最后，利用運動矢量差值信息進行尺寸大小模式選擇。經過對不同類型的多視點視頻序列的性能測試和數據對比，本文算法在比特率增加不多，峰值信噪比下降很小的情況下，能有效地降低編碼復雜度，大幅度減小編碼時間。

1 多視點視頻編碼快速算法原理

多視點視頻編碼有SKIP、幀間(Inter)和幀內(Intra)3種模式。Inter模式預測塊尺寸包括16×16，8×16，16×8，8×8，8×4，4×8和4×4這7種模式，其中，后4種尺寸合并在一起被稱為P4×4。Intra模式預測塊尺寸有16×16，8×8和4×4這3種模式[10]。設計這些不同大小尺寸塊的目的是為了適用不同類型視頻的編碼。大的塊尺寸適用于圖像中靜止或低速運動的平坦區域，小的塊尺寸則適合快速運動的區域。采用拉格朗日率失真優化函數作為最優判決準則，通過對所有預測模式的遍歷，計算出每種模式的率失真代價(Rdcost)值，選擇Rdcost值最小的模式作為該宏塊編碼的最優模式。利用拉格朗日率失真優化函數計算Rdcost的公式為

(1)

(1)式中：J(s,c,MODE|QP,λMODE)為率失真代價；MODE表示當前宏塊的編碼模式；QP為宏塊的量化步長；s和c分別為原始圖像和重建圖像的像素值；λMODE為預測模式所對應的拉格朗日乘子；R(s,c,MODE|QP)表示在所選QP和MODE下，當前宏塊編碼輸出比特數，SSD(s,c,MODE|QP)為圖像失真度。

由上述分析可知，對于編碼幀的每個宏塊有11種預測模式可供選擇，若采用全遍歷的方法，則需計算出每種模式的Rdcost值，而每次Rdcost的計算都十分耗時，因此，全遍歷方法的計算量巨大。如果能提前判斷出最優的編碼模式，省去對其他編碼模式的檢查，就可以降低計算復雜度。本文提出的快速算法就是基于這個思想來減少多視點視頻編碼的算法復雜度。文中算法測試所用的多視點視頻序列參數如表1所示。

1.1 SKIP模式提前判決

SKIP模式是利用運動矢量對當前塊進行預測的。由于沒有運動估計過程，該模式除了能節省對運動矢量編碼的比特數外，還可以降低計算復雜度。表2是附加視點為非關鍵幀時，在不同量化步長QP下，采用基于率失真最優判決和遍歷方法，測試出了表1中視頻序列的各種最優模式所占比例。其中63.3%～84.1%的宏塊選擇的是SKIP模式，選擇其他模式的比例較小，這是因為在多數視頻中，大部分背景區域是靜止的。與其他模式相比，由于計算SKIP模式Rdcost值的時間最少，如果該模式能盡早地被判決為最佳模式，這將可以減小多視點視頻編碼的時間。

表1 多視點視頻測試序列

表2 最優模式的概率分布

由于視點間的視頻內容的相似性，視點間相鄰宏塊的編碼信息，如Rdcost值、運動矢量的分布也很相似。如果能利用相鄰視點宏塊的Rdcost值計算得到一個閾值TSKIP，若當前宏塊SKIP模式的Rdcost值小于TSKIP，則可直接選擇SKIP模式為最佳模式，這樣可以減少所需遍歷的模式數，降低編碼復雜度。TSKIP的計算公式為

(2)

(2)式中：i表示參考視點V幀的宏塊序號；N為參考視點幀的宏塊總數；RDcostVSKIP(i)為第i宏塊的SKIP模式的Rdcost值；kV(i)的定義如(3)式所示。pV(RDcostVSKIP(i))為參考視點V幀中RDcostVSKIP(i)出現的概率，(4)式為該值的計算公式。

(3)

(4)

(4)式中：N(RDcostVSKIP(i))為RDcostVSKIP(i)量化后的個數；NVSKIP是SKIP模式的總個數。由于Rdcost值一般很小，對于(4)式中的率失真代價用RDcostVSKIP(i)/100進行量化。表3是當測試序列采用遍歷模式時，統計出的Rdcost值小于TSKIP的概率分布。從表2可以看出，不同分辨率的序列在采用不同量化步長QP的情況下，最終判決為SKIP模式的概率可達90%～99%，說明采用這種SKIP模式提前判決方法是可行和有效的。

表3 率失真代價值小于TSKIP的模式概率分布

1.2 編碼宏塊運動類型快速分類

在視頻序列中，幀間和幀內不同區域的運動類型一般是不一樣的。不同的運動區域通常會有不同的編碼方式，因此，可先將運動類型進行分類，再根據某些編碼信息對編碼區域的運動類型進行快速判決。在編碼過程中，運動矢量差值能有效地反映出區域的運動狀況。對于靜止和運動一致的區域，其編碼塊的運動矢量差值較小，而運動變化越大的區域，編碼塊的運動矢量差值就越大。因此，可根據視點間、時間和空間的3D相鄰區域宏塊的運動矢量差值的分布不同，對當前塊的運動類型進行快速分類判決。3D相鄰區域宏塊位置如圖1所示。

圖1 3D相鄰區域宏塊位置Fig.1 3D adjacent area macro block location

在圖1中，當前幀編碼宏塊MB0的3D相鄰區域宏塊包括：當前幀中相鄰的3個宏塊MB1～MB3；前一編碼幀中相同位置的宏塊MB4；參考視點中相應宏塊及其周圍的8個宏塊MB5～MB13。MB0的運動類型判決過程如下。

1)根據圖1所示的3D相鄰區域，構建運動矢量差值集合{mvd1,mvd2,…,mvd13}。其中，mvdi是宏塊MBi的運動矢量差值，i=1,2,…,13。

2)按(5)式計算每個mvdi的距離D(mvdi)，xi和yi分別是運動矢量的水平分量和垂直分量。

D(mvdi)=|xi|+|yi|

(5)

3)在運動矢量差值集合中找到mvdi的最大距離值D。

D=max(D(mvdi))

(6)

4)如果D≤D1，或D1≤D≤D2，或D2≤D≤D3，或D3≤D，則判斷當前宏塊MB0的運動類型為“運動一致”“簡單運動”“中度運動”“劇烈運動”。這里的D1和D2分別為1和5，D3的計算式為

D3=μ+2σ

(7)

(7)式中，μ和σ分別為當前宏塊在參考視點幀中D的期望和方差值。

1.3 運動搜索范圍動態調整

運動搜索是為了在參考幀的搜索區域內找到編碼塊的最佳參考塊。在多視點視頻編碼中，搜索范圍(search range，SR)是固定的。而在視頻幀中，不同區域的運動類型一般是不同的，而不同的運動類型，對應有不同的搜索范圍。對于靜止和運動一致的區域，其搜索范圍較小，而運動越劇烈的區域，其搜索范圍就越大。如果能實現編碼塊搜索范圍的動態調整，減少某些編碼塊的搜索區域，就能降低平均編碼時間。針對1.2節中4種運動類型的編碼宏塊，確定了最大搜索范圍如表4所示。

表4 不同運動類型對應的搜索范圍

采用全遍歷方式，對表1中的視頻序列進行編碼，統計出編碼宏塊4種運動類型的搜索范圍，并計算出這些搜索范圍在SRproposal內的概率，統計結果如表5所示。測試時的實驗參數設置為：SR為96，編碼圖像組(group of pictures，GOP)為12，采用基于上下文自適應二進制算術編碼(context-based adaptive binary arithmetic coding，CABAC)。從表5可以看出，運動一致、簡單運動和中度運動的區域搜索范圍在SRproposal內的概率分別達到了94.8%，98.5%和97.2%，說明利用宏塊的運動類型對運動搜索范圍進行動態調整的方法是可行的。

表5 遍歷方式下運動類型在最大搜索范圍內的概率

1.4 模式尺寸的選擇

在多視點視頻編碼中，不同尺寸大小的模式適應于不同的運動類型。對于靜止和運動一致的區域，大尺寸編碼模式更有效，而對于運動較強或劇烈的區域，小尺寸塊編碼模式效果最佳。如果能根據運動類型提前選擇出最適合的尺寸模式，從而可以減少編碼時間。表6是在量化步長QP=28的情況下，采用全遍歷方法，對表1中的測試序列進行編碼，統計出了不同運動類型選擇的最佳模式的概率分布。

對運動一致情況的區域，選擇16×16模式的概率為96%，選擇其他模式的概率為4%，因此，對這種運動類型，可直接選16×16模式為最佳模式；對于簡單運動類型的區域，16×16模式被選擇的概率是85.2%，16×8和8×16模式被選擇的概率分別為5.2%和5.4%，而P8×8模式和Intra模式被選擇的概率僅為3.3%和1.0%，因此，可忽略P8×8模式和Intra模式。而對于中度運動和復雜運動區域，為了得到較高的壓縮比，采用遍歷方式選擇最佳模式。表7總結出了不同運動類型區域需要進行遍歷的模式。

1.5 算法流程

通過前面對多視點視頻快速編碼算法原理的分析，本文快速算法流程如圖2所示。

表7 運動類型及相應的模式

2 算法性能測試與分析

文獻[11]對多視點視頻編碼進行快速模式決策時，將編碼宏塊的運動類型分為運動和背景2種。如果編碼宏塊的運動矢量超過1/4個整數像素值，判定為運動類型，然后遍歷所有大小尺寸模式；如果判斷為背景類型，則只遍歷SKIP，16×16，16×8和8×16這4種預測模式。由于文獻[11]與本文算法具有一定的相似性，所以用于本文算法性能指標的對比。在JMVM測試模型中，對本文算法和文獻[11]算法都進行了實現，并分別與JMVM全遍歷模式算法的性能指標進行了比較。選擇表1的視頻序列做為測試對象，測試用的計算機配置為2.59 GHz的Intel(R) Celeron(R)雙核處理器和1.96 GByte內存，JMVM測試模型的實驗參數設置如表8所示。

表8 實驗參數設置

本文算法、文獻[11]算法與JMVM算法性能指標的對比如表9所示。

表9中，ΔB為平均比特率變化量，ΔPSNR為平均峰值信噪比(peak signal to noise ratio，PSNR)變化量，ΔT是平均時間變化量，其中，“+”表示增加的量，“-”為減少的量。

表9 本文算法、文獻[11]算法與JMVM算法性能指標對比

通過本文算法與JMVM遍歷模式，文獻[11]算法與JMVM遍歷模式的性能數據的對比，本文算法的ΔB和ΔPSNR性能指標均要好于文獻[11]算法，文獻[11]算法的ΔB平均增加1.62%，而本文算法僅增加0.73%，文獻[11]算法的ΔPSNR平均減少0.056 dB，而文本算法平均減小0.043 dB。本文算法的編碼時間與JMVM遍歷模式相比，則大幅度降低，也明顯優于文獻[11]算法。無論是背景靜止、運動簡單的序列還是運動劇烈的序列，本文算法在降低編碼時間上均具有良好的性能。對于靜態背景、運動輕微的Exit序列，本文算法能減少72.1%編碼時間。對于Akko&Kayo，Ballroom，Breakdancers和Uli這些運動比較劇烈的序列，編碼時間也能分別減少65.9%，66.3%，61.7%和67.1%。對于相機移動和大片區域中有劇烈運動的Race1序列，采用本文算法，編碼時間可減少64%。而文獻[11]算法與遍歷模式相比，僅減少了18%的編碼時間。

圖3是采用本文算法和JMVM遍歷模式，Uli和Akko&Kayo 2組測試序列的率失真曲線，從曲線波形上看，本文算法與JMVM遍歷方法率失真性能基本一致。

圖3 本文算法與JMVM遍歷模式率失真曲線對比圖Fig.3 Contrast diagram of the rate distortion curve of proposed algorithm and JMVM ergodic model

3 結 論

本文算法充分利用了3D相鄰區域和當前塊的相關性，減少了多視點視頻編碼的復雜度。通過視點間宏塊率失真代價分布的相關性，對當前宏塊做SKIP模式自適應提前判決；根據3D相鄰區域的運動矢量差值對當前宏塊運動類型進行快速分類；針對不同的運動類型選擇相應的搜索范圍和相應尺寸大小的編碼模式。通過實驗測試表明，本文算法與JMVM遍歷模式相比，在只增加0.73%比特率，降低0.043 dB峰值信噪比的情況下，能平均減少66%的編碼時間。與文獻[11]相比，也能平均減少20%的編碼時間。因此，本文的快速算法可應用于多視點視頻編碼中。

[1] VETRO A，TOURAPIS A M，MULLER K，et al.3D-TV content storage and transmission[J].Broadcasting，IEEE Transactions on，2011，57(2)：384-394.

[2] VETRO A，WIEGAND T，SULLIVAN G J.Overview of the stereo and multiview video coding extensions of the H.264/MPEG-4 AVC standard[J].Proceedings of the IEEE，2011，99(4)：626-642.

[3] ZENG H，CAI C，MA K K.Fast mode decision for H.264/AVC based on macroblock motion activity[J].Circuits and Systems for Video Technology，IEEE Transactions on，2009，19(4)：491-499.

[4] ZHU W，JIANG W，CHEN Y.A fast inter mode decision for multiview video coding[C]//IEEE.Information Engineering and Computer Science，ICIECS 2009，International Conference on.New York：IEEE Press，2009：1-4.

[5] SHEN L，LIU Z，YAN T，et al.Early SKIP mode decision for MVC using inter-view correlation[J].Signal Processing：Image Communication，2010，25(2)：88-93.

[6] SHEN L，LIU Z，LIU S，et al.Selective disparity estimation and variable size motion estimation based on motion homogeneity for multi-view coding[J].Broadcasting，IEEE Transactions on，2009，55(4)：761-766.

[7] ZHU W，TIAN X，ZHOU F，et al.Fast inter mode decision based on textural segmentation and correlations for multiview video coding[J].Consumer Electronics，IEEE Transactions on，2010，56(3)：1696-1704.

[8] LI X，ZHAO D，JI X，et al.A fast inter frame prediction algorithm for multi-view video coding[C]//IEEE.Image Processing，ICIP 2007，IEEE International Conference on. New York：IEEE Press，2007，3：III-417-III-420.

[9] ZENG H，MA K K，CAI C.Motion activity-based block size decision for multi-view video coding[C]∥IEEE.Picture Coding Symposium(PCS).New York：IEEE Press，2010：166-169.[10] 汪博涵，陳婧，曾煥強，等.采用率失真與模式特征的多視點視頻編碼快速模式選擇[J].信號處理，2015，31(12)：1642-1648. WANG Bohan，CHEN Jing，ZENG Huanqiang，et al.Fast Mode Decision for Multiview Video Coding using Rate-distortion and Mode Characteristic[J].Journal of Signal Processing，2015，31(12)：1642-1648.

[11] HAN D H，LEE Y L.Fast mode decision using global disparity vector for multi-view video coding[C]//IEEE.Future Generation Communication and Networking Symposia，2008.FGCNS'08，Second International Conference on. New York：IEEE Press，2008：209-213.

明 艷(1967-)，女，湖南長沙市人，高級工程師，主要研究方向為數字通信技術。E-mail：mingyan@cqupt.edu.cn。

(編輯：王敏琦)

Fast multi view video coding algorithm based on the relativity of 3D adjacent areas macroblock

MING Yan

(Chongqing Key Laboratory of Signal and Information Processing， Chongqing University of Posts and Telecommunications，Chongqing 400065， P.R. China)

Aimed at the high complexity of multi view video coding, a fast algorithm based on the correlation of adjacent macro-block’s coding information is proposed in this paper. Using the relativity of adjacent macro-block’s rate distortion cost distribution in inter views of multi view video, current macro-block’s SKIP mode can be prejudge. According to the motion vector difference in the adjoining domains from visual, temporal and spatial perspective, current macro-block’s motion activity can be classified quickly. Search range is adjusted and suitable mode size is chosen in accordance with the different motion activity. Through coding performance testing on multi view video sequences that has respective motion activity characteristics, the simulation results show that this algorithm achieves a reduction of the encoding time by 66% on average, while incurring only 0.04 dB loss in peak signal-to-noise ratio and 0.75% increment on the total bit rate compare with JMVM ergodic model

multi view video coding；fast algorithm；relativity；performance testing

2016-03-15

2016-10-10

明 艷 mingyan@cqupt.edu.cn

國家自然科學基金(61102131)；重慶市教委科技項目(KJ1400425)

Foundation Items：The National Natural Science Foundation of China(61102131);The Science & Technology Research Project of Chongqing Education Committee of China(KJ1400425)

10.3979/j.issn.1673-825X.2016.06.006

TP919.81；TP39

A

1673-825X(2016)06-0783-06