面向MPEG Type-1視頻編碼器的UMHexagonS算法

李芍，陳建文，何蕓

(清華大學 電子工程系 清華信息科學與技術國家實驗室，北京 100084)

2011年1 月，國際標準化組織ISO/IEC JTC1 sc29 wg11，即MPEG工作組在韓國Daegu會議上發(fā)布了一個新的工作項目.Type-1 licensing video coding.與以往的視頻編碼標準不同之處為，編碼器不但要有高的編碼效率，而且每一項技術和每一處標志都要符合 MPEG Type-1 licensing［1］要求.這項計劃的結果將為網絡視頻通信帶來巨大的自由度而被廣泛應用.所以在MPEG 2011年3月日內瓦會議上將 Type-1 video coding命名為“網絡視頻編碼”［2］.

快速運動搜索算法是視頻編碼器中一種有效的簡化算法，在視頻編碼的幀間預測中，編碼器需要在參考幀中找到具有最小MCOST(motion cost)值的塊.如果采用全搜索算法，以H.264/AVC參考軟件JM(JVT Model)為例，大約需要占用60% ～80%的編碼時間［3］.早期的快速運動搜索算法包括三步搜索法［4］、六邊形搜索法［5］等，這些算法的實現簡單，但會帶來較大的編碼性能下降.UMHexagonS［3，6-9］算法是一個高效的運動搜索方法，相比于全搜索算法，該算法能夠節(jié)省90%以上的時間，同時編碼器的率失真性能(R-D性能)也能得到很好的保持.UMHexagonS算法已經被JVT(joint video team)標準組織采納并集成在H.264/AVC的參考軟件JM中，近年來針對UMHexagonS算法的研究給出了多種改進型方法.

針對Type-1平臺的特征，本文提出了一種改進的UMHexagonS整象素快速搜索算法，本算法充分利用了運動矢量和MCOST在時空域上的相關性，改進了UMHexagonS搜索的提前截止閾值，從而提高了原算法在Type-1平臺上的編碼效率.

1 UMHexagonS整象素搜索算法簡介

UMHexagonS的整象素搜索過程如圖1所示.

圖1 UMHexagonS算法流程Fig.1 Flow chart of the UMHexagonS

1.1 搜索起始預測

UMHexagonS算法的第1部分為確定搜索的起始運動矢量，包括空域預測和時域預測，空域預測包括中值預測和上層預測;時域預測包括相鄰參考幀運動矢量預測和參考幀共同位置塊的運動矢量預測，此外，還包括零運動矢量.在不發(fā)生提前截止的條件下，這一步中具有最小MCOST的運動矢量將作為下一步的搜索中心點.對于一個N×M大小的塊來說，MCOST的計算公式如下:

式中:P(i，j，t)和 P(x+i，y+j，t-r)分別代表當前幀中坐標為i、j的象素值和參考幀中坐標為x+i、y+j的象素值，(x，y)代表運動矢量，λBits代表編碼運動矢量帶來的額外的代價.

1.2 主模型搜索

主模型搜索主要包含3個部分:非對稱十字搜索，5×5正方形象素區(qū)域搜索和多尺度六邊形搜索.搜索范圍確定以后，這3種搜索模型需要搜索的象素點的個數和相對位置將被固定，搜索過程中的各個象素間無前后依賴關系，這種特性適合并行計算.在多尺度六邊形搜索之后，如果不滿足提前截止條件，還要進行局部優(yōu)化搜索，例如六邊形和十字型搜索.以16搜索區(qū)域為例，主模型搜索的象素位置如圖2所示.

圖2 UMHexagonS主模型搜索Fig.2 The main searching process of the UMHexagonS

1.3 提前截止算法

UMHexagonS包含2類提前截止條件，第1類跳轉至局部優(yōu)化搜索，第2類則結束搜索過程.第1類提前截止的閾值由當前塊大小、當前量化步長、量化系數QP以及相鄰塊的MCOST值確定［3］:

第2類提前截止條件應用于搜索算法的第1步和最后一步，其閾值的計算［8-9］如下:

式中:QPfactor與Scalefactor分別與編碼當前視頻的量化系數以及當前視頻的尺寸有關，文獻［8-9］中指出:在使用較大的量化系數編碼時應使用較小的QPfactor，編碼較大尺寸視頻序列時應使用較大的Scalefactor.

2 UMHexagonS在Type-1平臺的分析

由于UMHexagonS在H.264/AVC標準算法中具有良好的RD性能、較快的搜索速度和優(yōu)秀的并行性特征，本文嘗試將UMHexagonS算法的整象素搜索部分移植到Type-1平臺.

2.1 Type-1平臺配置介紹

如前所述，在Type-1 Licensing的約束下，Type-1平臺使用的編碼工具較為簡單，表1［10］給出了該平臺與H.264/AVC的主要技術對比.由于該平臺的亞象素僅有1/2精度，因此本文僅探討整象素搜索部分.測試的主要配置如表2所示，這是目前Type-1平臺中所使用的通用配置.實驗的測試序列為正在制訂中的國際標準ISO/IEC JTC1 sc29 wg11和ITUT sg16 Q.6聯合工作組HEVC(high efficiency video coding)［11］的通用測試序列.

表1 H.264/AVC與Type-1幀間技術對比Table 1 Inter frame coding between H.264/AVC and Type-1

表2 Type-1平臺通用測試配置Table 2 Brief test configuration in Type-1 platform

2.2 Type-1平臺UMHexagonS性能測試

實驗1中，由于Type-1平臺只有1個參考幀，因此原UMHexagonS中的時域預測被移除，中值預測則被替換成Type-1平臺中所對應的預測值，預測結構使用IPPP，其余保持不變.

表3中為2個序列在4個不同QP點測試結果的平均值，使用 BD-Rate和 BD-PSNR［12］比較 UMHexagonS算法與全搜索算法的結果，表中BD-Rate的正值說明UMHexagonS相對于全搜索消耗了更多的比特數，BD-PSNR的負值說明UMHexagonS相對于全搜索有客觀性能的下降.這里的衡量標準BDRate和BD-PSNR具有“或”的關系.RaceHorse序列包含較劇烈和較不規(guī)則的運動，而Kimono1則包含有較多模糊的紋理.

表3 原始的UMHexagonS在Type-1平臺的性能Table 3 The Type-1 performance of original UMHexagonS in Type-1

一般來說，用于視頻編碼標準制定的快速運動搜索算法在所有測試序列上允許的平均BD-PSNR下降不能超過0.05dB，單個序列不能超過0.1 dB，這樣才能使編碼器平臺中的其他技術不會受到快速運動搜索的影響.在實驗1中，導致性能下降的主要問題包括2個:1)提前截止的閾值不合適，2)起始搜索點數不足，這里給出Kimono 1和RaceHorse序列的RD曲線(見圖3、4).

圖3 RaceHorse序列搜索性能Fig.3 The Type-1 performance of UMHexagonS in RaceHorse

可以看出，對于RaceHorse序列在不同的碼率下性能損失相近，這對應于搜索起始位置過少而導致搜索算法未能找到最優(yōu)的搜索位置;對于Kimono 1序列而言，其高碼率端的性能損失大于低碼率端，這對應于提前截止條件的缺陷，因為在低碼率端，提前截止的閾值較小，因此算法搜索的點數更多.

圖4 Kimono1序列搜索性能Fig.4 The Type-1 performance of UMHexagonS in Kimono 1

為了驗證提前截止閾值的論斷，在實驗2中采用與實驗1相同的序列和配置，但是取消了UMHexagonS的第2類提前截止算法.測試結果見表4，可以看出，對于Kimono1序列而言，其平均性能已經優(yōu)于全搜索算法，但是對于RaceHorse序列來說，性能損失仍然較大.

表4 無第2類提前截止的UMHexagonS算法性能Table 4 The Type-1 performance of UMHexagonS without early termination Type-2

3 UMHexagonS算法的改進

基于前面的分析，本文的改進包括2個方面:1)增加搜索的起始點以提高預測運動矢量的準確性;2)改變提前截止算法，使得閾值的取值能夠更加的適應序列的特性.

3.1 起始搜索點的確定

在文獻［13］中，搜索的起始點利用了相鄰塊之間的相關性.基于類似的思想，本文提出了一種涵蓋各個方向的運動矢量預測方式，分別對應于16×16、8×8以及4×4大小的塊.

3.1.1 16×16 塊的預測點位置

16×16塊的空域預測運動矢量包括左邊、上邊和右上3種;時域預測運動矢量來自前一個使用幀間編碼的參考幀，共4個.如圖5所示.

A～C塊和當前塊具有空間相鄰的位置關系，D～G塊的實際位置在參考幀中，它們在參考幀中的坐標和當前塊4個角在當前幀上的坐標相同，這樣的設計可以使得當前塊的運動方向總會一定程度上反應在A～G的某一個參考塊中.當參考幀與當前幀之間的距離可變時(例如IBBP結構)，還要使用運動矢量縮放.縮放采用線性運動模型(如圖6所示)，即假設當前幀和參考幀具有共同位置的塊屬于同一個物體，設參考幀中塊的運動矢量為Mref，參考幀序號為t+n，參考幀編碼使用的參考幀序號為t，當前幀的序號為t+n+m，則當前塊的運動矢量M由下式確定:

圖5 16×16塊運動矢量預測Fig.5 Motion vector prediction of 16 ×16 blocks

圖6 時域運動矢量縮放Fig.6 Temporal motion vector scaling

3.1.2 8×8 塊的預測點位置

8×8塊的空域運動矢量預測包括左邊塊、上邊塊、右上方塊和左下方塊的運動矢量;而時域的預測則采用了位于當前8×8塊外部的4個塊，如圖7所示.

圖7 8×8塊運動矢量預測Fig.7 Motion vector prediction of 8 ×8 blocks

3.1.3 4 ×4 塊的預測點位置

在Type-1平臺中的幀間預測中，大多數的塊尺寸為16×16和8×8，4×4塊實際使用的頻率非常低，如表5給出的Type-1平臺編碼序列RaceHorces得到的塊大小分布.UMHexagonS中上層預測的準確性較高，已經能夠很好地預測較小尺寸塊的運動矢量［3］，因此，不采用4×4塊的時域預測而僅添加4個空域運動矢量預測，4×4塊的空域預測方式與8×8塊一致.可見，在最不好情況下，改進的UMHexagonS算法比原算法增加了大約4～8個搜索點.

表5 編碼塊大小分布Table 5 Block size distribution

3.2 第2類提前截止閾值修正

在UMHexagonS算法中，第2類提前截止的閾值計算見式(3)，其中的QPfactor與Scalefactor計算方法如下:

式中:image(QP)表示當前編碼序列的量化系數QP，Img_width表示當前視頻的象素寬度，Min_width=176，a、b為預定義的常數.當序列尺寸為高清時，Scalefacter的取值在3.9左右，此時如果QPfacter較小，提前截止的閾值將達到2倍的Thd_Base左右.這對于具有較大平坦區(qū)域的序列來說較為合適［8-9］，但是對于紋理細節(jié)較多的序列(Kimono 1)則不然.在提前截止算法1中，左邊和上邊塊的MCOST值被用于計算第1類閾值.在本文中，也同樣采用相鄰塊MCOST的估計方法.定義搜索結束后16×16塊與其左邊16×16塊，上邊16×16塊和參考幀內共同位置的16×16塊的MCOST相關系數分別為 ρL、ρT和 ρC:

式中:Bx，y，t代表當前幀 t中坐標為(x，y)的 16 × 16大小塊的 MCOST 值，Bx，y，t'代表參考幀 t'中坐標為(x，y)的16×16大小塊 MCOST 值，代表當前幀和參考幀中所有16×16大小塊MCOST值的方差.此外，這里的均值E(·)不是統(tǒng)計均值，而是算數均值.考慮到某些塊的左邊、上邊塊不存在，因此這里的計算和概率意義下的相關系數不能完全等價.對IPPP預測結構和IBBP預測結構中的P幀進行上述計算，采用前述實驗2的平臺，并加入3.1節(jié)關于起始位置的改進，得到的結果見表6.

表6 MCOST相關系數(IPPP/IBBP)Table 6 Correlation coefficient of MCOST(IPPP/IBBP)

可見，MCOST的空域相關性更為魯棒一些，受到序列特性和預測結構的影響不大;而其時域相關性僅在IPPP預測結構下的某些特定序列上較大，在IBBP預測結構下則較小.因此，采用簡單的空域MCOST對第2類提前截止的閾值進行修正:

式中:Spatial_Thd的值等于當前塊的左邊塊MCOST值與上邊塊MCOST值中的較小者，最終的Threshold值為Spatial_Thd與第2類提前截止閾值Thd的平均.采取簡單修正的目的是為了盡量避免復雜修正算法所帶來的搜索時間增加，例如復雜度較高的相關性漸進擬合算法會提高搜索時間.

4 實驗結果

在實驗中，采取前述的實驗條件配置、改進的搜索算法與Type-1平臺已有的全搜索算法以及原始的UMHexagonS搜索算法進行比較，結果如表7.

表7 改進的UMHexagonS與全搜索算法的性能對比Table 7 Modified UMHexagonS v.s.full search

表7中的平均節(jié)省時間的計算方式以下式計算:

式中:Tfull和Tfast分別代表全搜索占用的時間和改進后的UMHexagonS搜索算法所占用的時間.可以看出，相對于全搜索算法，節(jié)省了97% ～98%的時間，平均PSNR降低控制在0.032dB之內，最壞的情況是IBBP結構下的RaceHorse序列編碼，性能下降達到了0.109dB.表8給出了改進后的UMHexagonS搜索算法和原始的UMHexagonS搜索算法在Type-1平臺上的性能對比，采用IPPP預測結構.

表8 改進的UMHexagonS與原始的UMHexagonS性能對比Table 8 Modified UMHexagonS v.s.original UMHexagonS

表8中的平均節(jié)省時間的計算方式如下:

式中:Torg和Tfast分別代表原始的UMHexagonS算法所占用的時間和改進后的UMHexagonS所占用的時間.可以看出，盡管增加了起始搜索點及修改了第2類提前截止閾值計算，但是幾乎在所有的測試序列中，改進后的算法占用的時間都要少于原算法的時間.其原因包括2個方面:1)雖然增加了起始搜索點，但同時提高了預測的準確性，這將導致更多的提前截止出現;2)改進的第2類閾值計算雖然會在某些時候降低最終的提前截止閾值(Kimono 1)，但在其他其他其他情況下，這將導致最終的提前截止閾值增加，從而使得更多的塊搜索可以提前截止.

5 結束語

本文提出了一種改進的UMHexagonS算法并在Type-1平臺上實現.該算法通過大量使用空域和時域的運動矢量預測，在參考幀數目受限和編碼模式受限的條件下提高了原有快速算法的搜索精度;同時，采用低復雜度自適應MCOST預測方法更好的估計了算法的提前截止閾值.因此，充分地利用時空域中的運動矢量和MCOST信息能夠明顯的改善快速運動搜索算法的搜索精度，同時還能夠一定程度上減少搜索時間，在視頻編碼器中具有很好的實用價值.本算法最近已經集成在最新版本的Type-1編碼器平臺中.在實驗結果中，最大的 BD-PSNR有0.1 dB多的下降，進一步的實驗結果表明這種現象來源于主模型搜索，由于RaceHorse序列中的物體運動不規(guī)則，時空域的預測不準確，主模型搜索由于形狀相對固定，最優(yōu)預測點會無法索引到，故而編碼效率下降.因此，對于UMHexagonS算法的進一步研究將繼續(xù)進行.

［1］ITU-T，ITU-R，ISO/IEC.ITU-T/ITU-R/ISO/IEC common patent policy［Z］.Geneva:ITU and ISO/IEC，2007.

［2］MPEG.Requirements for Internet Video Coding/ISO/IEC JTC1 sc29 wg11 w12045［Z］.Geneva，2011.

［3］CHEN Zhibo，ZHOU Peng，HE Yun，CHEN Yidong.Fast integer pel and fractional pel motion estimation for JVT/JVT-F017［Z］.Joint Video Team(JVT)of ISO/IEC sc29 MPEG ＆ ITU-T SG16 VCEG.Awaji，2002.

［4］KOGA T，IINUMA K，HIRANO A，LIJIANG Y.Motion compensated inter frame coding for video conferencing［C］//Proceedings of National Telecommunications Conference.New Orleans，1981:G5.3.1-G5.3.5.

［5］ZHU Ce，LIN Xiao，CHAU Lap Pui.Hexagon-based search pattern for fast block motion estimation［J］.IEEE Transactions on Circuits and Systems for Video Technology，2002，12(5):349-355.

［6］CHEN Zhibo，ZHOU Peng，HE Yun，et al.Fast motion estimation for JVT/JVT-G016［Z］.Joint Video Team(JVT)of ISO/IEC sc29 MPEG ＆ ITU-T SG16 VCEG.Pattaya，2003.

［7］CHEN Zhibo，XU Jianfeng，HE Yun，et al.Fast integerpel and fractional-pal motion estimation for H.264/AVC［J］.Journal of Visual Communication and Image Representation，2006，17(2):264-290.

［8］XU Xiaozhong，HE Yun.Modification of UMHexagonS fast ME/JVT-R085［Z］.Joint Video Team(JVT)of ISO/IEC sc29 MPEG ＆ ITU-T SG16 VCEG.Bangkok，2006.

［9］XU Xiaozhong，HE Yun.Improvements on fast motion estimation strategy for H.264/AVC［J］.IEEE Transactions on Circuits and Systems for Video Technology，2008，18(3):285-293.

［10］CHEN Jianwen，RONG Yaocheng，XU Feng，et al.Potential option-1 software Platform［Z］.ISO/IEC JTC1 sc29 m19455.Daegu，2011.

［11］WIEGAND T，OHM J R，SULLIVAN G J，et al.Special section on the joint call for proposals on high efficiency video coding(HEVC)standardization［J］.IEEE Transactions on Circuits and Systems for Video Technology，2010，20(12):1661-1666.

［12］BJONTEGAARD G.Calculation of average PSNR differences between RD-Curves［Z］.VCEG-M33，ITU-T sg16 VCEG.Porto Seguro，2001.

［13］XU Jiebin，PO Laiman，CHEUNG Chok Kwan.Adaptive motion tracking block matching algorithms for video coding［J］.IEEE Transactions on Circuits and Systems for Video Technology，1999，9(7):1025-1029.