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

李芍，陳建文，何蕓

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

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

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

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

1 UMHexagonS整象素搜索算法簡介

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

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

1.1 搜索起始預(yù)測

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

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

1.2 主模型搜索

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

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

1.3 提前截止算法

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

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

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

2 UMHexagonS在Type-1平臺的分析

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

2.1 Type-1平臺配置介紹

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

表1 H.264/AVC與Type-1幀間技術(shù)對比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中的時域預(yù)測被移除，中值預(yù)測則被替換成Type-1平臺中所對應(yīng)的預(yù)測值，預(yù)測結(jié)構(gòu)使用IPPP，其余保持不變.

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

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

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

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

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

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

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

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

3 UMHexagonS算法的改進

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

3.1 起始搜索點的確定

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

3.1.1 16×16 塊的預(yù)測點位置

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

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

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

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

3.1.2 8×8 塊的預(yù)測點位置

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

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

3.1.3 4 ×4 塊的預(yù)測點位置

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

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

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

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

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

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

表6 MCOST相關(guān)系數(shù)(IPPP/IBBP)Table 6 Correlation coefficient of MCOST(IPPP/IBBP)

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

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

4 實驗結(jié)果

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

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

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

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

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

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

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

5 結(jié)束語

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