陳 紅，齊 華

(西安工業(yè)大學 電子信息工程學院，西安 710021)

?

HEVC幀間快速運動估計及計算復雜度分析

陳 紅，齊 華

(西安工業(yè)大學 電子信息工程學院，西安 710021)

為了降低高性能視頻編碼標準中幀間運動估計的高計算復雜度，提出了一種基于運動矢量相似性的運動估計快速終止算法.該算法利用視頻序列中同一個對象的運動矢量相似性，對當前編碼單元的分割方式進行了選取，提前終止了部分可能性較低的復雜分割模式的運動估計.結合運動相似區(qū)域的編碼單元，在分解后的下一遞歸深度中對小塊預測單元劃分的運動估計進行了裁減.實驗結果表明：所提方法與高性能視頻編碼標準參考代碼中的標準算法相比，在低延時編碼配置下，編碼時間和峰值信噪比分別降低了41.79%和0.052 dB.隨機訪問編碼配置下，編碼時間和峰值信噪比分別降低了41.98%和0.041 dB.運動估計的計算量減小，計算復雜度降低.

高性能視頻編碼標準；運動估計；運動差異; 計算復雜度

高效視頻編碼(High Efficiency Video Coding， HEVC)于2013年被正式確定為最新一代的國際視頻壓縮編碼標準，主要面對高清、超高清視頻應用[1].HEVC編碼沿用了H.26X編碼采用的基于塊的混合編碼框架，在此基礎上對很多編碼技術做了突破性的改進[2].主要包括編碼單元(Coding Unit，CU)中運動融合、遞歸式四叉樹塊劃分結構、高精度運動補償及自適應環(huán)路濾波等.在相同的編碼質量條件下，HEVC編碼對視頻數(shù)據(jù)的壓縮能力是H.264/AVC編碼的2倍[3]，但同時也導致編碼復雜，不利于HEVC編碼應用于實時視頻，因此在不降低編碼性能的前提下降低編碼復雜度是HEVC編碼能否得到廣泛應用的關鍵.

運動估計作為視頻編碼的核心技術，占用了 50%以上的編碼時間，尋找快速高效的運動估計算法一直是視頻編碼領域研究的一個熱點問題.文獻[4]利用光流法計算金字塔運動發(fā)散(Pyramid Movement Divergence，PMD)的特征值決定CU單元的分割情況，在一定程度上降低了復雜度.文獻[5]利用 Bayes 決策規(guī)則判定當前 CU 單元是否進行劃分.文獻[6]提出了一種小塊預測單元(Predicting Unit，PU)劃分快速算法，檢查Cbf標志位以及當前PU單元的率失真(Rate Destortion，RD)代價，若這兩個值符合一定條件，則提前終止下一個PU單元的預測.文獻[7]采用預測殘差的特征計算預測塊和原始塊的平均平方誤差，實現(xiàn)了部分 CU 單元劃分的提前終止.文獻[8]基于視頻內容相關性和時域、空域相鄰 CU 單元預測模式，結合RD 代價信息對當前 CU 單元的預測模式進行了預測，對部分冗余的預測模式進行裁剪.文獻[9-10] 通過前后幀的變化情況來判斷運動劇烈程度，以快速判定編碼模式，取得了較高的編碼效率.由以上可見，根據(jù)當前CU單元自身的特征如RD代價、運動信息，提前終止CU單元或者PU單元的進一步劃分，是一種切實有效的方法.

基于此，文中利用運動矢量相似性，提出了一種HEVC編碼幀間運動估計快速終止算法，根據(jù)當前CU單元的運動矢量差異性，合理選取當前CU單元的分割方式，減少運動估計的計算量.通過對當前CU單元的運動矢量絕對偏差的平均值進行計算，確定出當前CU單元的運動差異性，若運動差異小于給定閾值，則當前CU單元位于運動相似區(qū)，在下一遞歸深度的CU單元中非塊大小為2N×2N(N為2的冪次方，無量綱)分割模式的運動估計被裁減，提前終止運動估計，降低HEVC編碼復雜度.

1 HEVC編碼中幀間復雜度分析

1.1 HEVC編碼中CU單元劃分方式

HEVC編碼中編碼樹單元(Coding Tree Unit，CTU)為最大編碼單元，根據(jù)涵蓋圖像區(qū)域復雜度，通過遞歸，各個CTU單元劃分成較小的編碼單元，最多可以劃分4層，這樣的劃分模式稱為四叉樹劃分[11]，如圖1所示.圖1中split-flag為劃分標志位；CU-Size為編碼單元大小；CU-Depth為編碼單元深度；N0、N1、N2、N3為劃分后編碼子單元大?。籆U0、CU1、CU2、CU3分別為不同深度的編碼單元.

圖1 CU單元的四叉樹結構

若CU單元深度為0 層時，CU單元的大小與CTU單元相同，為64×64；當深度為1 層時，一個CTU單元可劃分為4個CU1單元，每個CU1單元大小為32×32，以此類推，每個CU2單元大小為16×16，CU3單元大小為8×8，在CU單元的四叉樹結構中，深度最大為3 層.CU單元可繼續(xù)被劃分為PU單元，每個PU單元預測信息相同,包括運動矢量、預測模式及參考幀等[12].圖2為幀內預測和幀間預測情況下PU單元劃分方式.圖2中N、U、D、L、R、n為PU單元的劃分尺寸參數(shù).每個CU單元，按劃分方式的不同，可含有1個、2個或者4個PU單元，對于幀間類型，CU單元共有8種劃分方法[13].使用變換單元(Transform Unit，TU)進行殘差變換，TU單元可有4×4、8×8、16×16或32×32等劃分模式.

圖2 PU單元劃分模式

1.2 幀間編碼復雜度分析

HEVC編碼使用全深度搜索方法以獲取最優(yōu)塊劃分方式，每個CU單元分別進行2種幀內劃分和8種幀間劃分，判定最佳劃分的條件是計算該劃分下的總RD代價.以誤差平方和(Sum of Square Error,SSE)作為幀間運動估計中最佳劃分的RD代價為

JSSE=(SSEL+ωchroma×SSEC)+λSSE×Bits

(1)

式中：JSSE為誤差平方和；SSEL和SSEC分別為亮度和色度分量的誤差平方和；λSSE為拉格朗日乘子；ωchroma為色度分量加權因子；Bits為編碼后的碼流大小.

假定編碼中不考慮 Skip 模式 CU 單元不分解的情形，從最大編碼單元(Largest Coding Unit,LCU)分解為最小尺寸的CU單元所需計算的RD代價次數(shù)為3 068次.

對于每一次計算RD代價，均需進行變換、量化、反變換、反量化及熵編碼等過程，在一幅分辨率為1 920×1 080 pixel的視頻圖像中包含超過500個塊大小為64×64的LCU.由此可見，HEVC編碼的幀間預測因CU單元、PU單元的引入使得編碼器的復雜度過高.

2 HEVC編碼幀間運動估計快速終止算法

2.1 CU單元的運動差異程度衡量

同一運動對象區(qū)域中CU單元的運動矢量分布相似，這是由于視頻序列中同一對象具有相似的運動矢量.為此，對于這些區(qū)域進行運動估計時不需要分割成較小的PU單元，這是由于運動矢量通過大塊PU單元運動估計即可得到，且較為準確.對運動變化劇烈區(qū)域內的CU單元，分割成較小塊的PU單元將有助于搜索到正確運動矢量.若不劃分運動特征相似區(qū)域的CU單元，運動估計就能提前終止，因此減少了較小尺寸CU單元的運動估計次數(shù).

通過分析當前運動矢量差異程度可以衡量當前編碼塊是否處于運動相似區(qū)域，測試模型HM中運動矢量以4×4塊大小為單位進行存儲.某個視頻區(qū)具有N個4×4塊，運動矢量在水平和垂直方向的差異程度分別為

(2)

(3)

式中：Hx,Hy分別為運動矢量在水平和垂直方向的差異程度；vx(i)和vy(i)分別為4×4塊在水平和垂直方向的運動矢量.當Hx和Hy小于某閾值時，則判定當前N個4×4塊的視頻區(qū)域屬于運動相似區(qū)域，且Hx和Hy的值越小，說明該區(qū)域的運動特征越相似.通過計算空域相鄰CU單元和當前CU單元的運動差異程度，可以判定當前CU單元是否要劃分為更小塊的CU單元進行運動估計.

2.2 運動估計快速終止準確度統(tǒng)計分析

CU單元進行各PU單元分割模式的運動估計后，若當前CU單元的最佳預測模式是2N×2N，則所有4×4塊的運動矢量是一致的，若最佳預測模式是小塊PU單元的運動估計，每個PU單元的運動矢量可能不同，則以4×4塊為單位存儲的運動矢量呈現(xiàn)一定的差異性.根據(jù)式(2)～(3)，當前CU單元進行運動估計后的運動矢量在水平和垂直方向的差異分別為

(4)

(5)

其中N為當前CU單元的4×4塊的個數(shù).當前CU單元進行運動估計后的運動矢量在水平和垂直方向的總差異為

vart=varx+vary

(6)

vart的值越大則當前CU單元的各個部分的運動差異越大，進行小塊PU單元劃分的可能性越高.因此當vart足夠小，小于一定閾值varth時，當前

CU單元位于運動相似區(qū)域，各個部分的運動矢量的相似度很高，進行小塊PU單元劃分的可能性小，varth設為 0.2.

為了準確分析此閾值下裁減小塊PU單元劃分的運動估計，通過編碼實驗分析vart的分布.編碼配置采用隨機訪問編碼，CU單元在不同vart下的最佳預測模式為2N×2N和非2N×2N，vart值分布情況見表1.表1～4中序列為不同分辨率的測試視頻序列.

表1 vart值分布情況統(tǒng)計表

從表1可以看出vart

通過統(tǒng)計小塊PU單元運動估計判定正確的CU單元個數(shù)占總CU單元個數(shù)的比例，得到裁減小塊PU單元運動估計后的準確率，準確率統(tǒng)計結果見表2.

由表2可以看出，文中所提的運動估計快速終止方法的準確率非常高，平均達到了 98.72%，說明只有少部分需要非2N×2N模式運動估計的CU單元被判定為只進行2N×2N模式運動估計，這部分CU單元對整體效果的影響非常小，由此證明了算法的可靠性.

表2 運動估計快速終止準確率統(tǒng)計

Tab.2 Accuracy statistics of motion estimation quick ending

分辨率/pixel序列準確率/%416×240BlowingBubbles97.22416×240BasketballPass98.89416×240BQSquare99.19832×480BQMall98.71832×480BasketballDrill97.62832×480PartyScene98.591280×720Vidyo399.791280×720Vidyo499.78平均98.72

2.3 算法流程

算法實現(xiàn)步驟如下：①當前遞歸深度Dc為 0 時，進行2N×2N和非2N×2N模式運動估計；如果遞歸深度不為0，當上一遞歸深度Dc-1下的標志位DeepME為True 時,才進行非2N×2N模式運動估計，否則跳過非2N×2N模式運動估計；②如果當前遞歸深度小于最大遞歸深度，根據(jù)式(4)、(5)和(6)計算當前CU單元所有4×4塊運動矢量的運動差異vart；③如果vart

3 實驗結果與分析

為測試所提方法性能，測試了分辨率為2 560×1 600 pixel、1 920×1 080 pixel、1 280×720 pixel、832×480 pixel和416×240 pixel的視頻序列共15個.采用HEVC編碼標準的官方測試模型HM(版本為HM9.0)作為測試平臺.實驗配置：編碼樹單元CTU大小為64×64，最大深度為3，運動搜索模式為快速搜索算法(Enhanced Predictive Zonal Search，EPZS)，搜索區(qū)域的窗口是[-64,64]，將用于編碼中運動搜索加速項(Fast Encoder Decision，F(xiàn)EN)設置為使能.采用低延時(Low Delay,LD )和隨機訪問(Random Access,RA)編碼結構，實驗中采用量化參數(shù)(Quantum Parameter,QP)為22、27、32和37，通過所有幀的信噪比變化量ΔPSNR和碼率變化率ΔBR分析了算法的率失真性能.通過對算法編碼時間變化率ΔT的統(tǒng)計，衡量了計算復雜度的變化，ΔPSNR為負值表示峰值信噪比(Peak Signal to Noise Ratio,PSNR)有所下降，ΔBR為正值表示碼率有所上升，ΔT為負值表示算法編碼時間的減少.

計算公式分別為

(7)

(8)

(9)

表3 本文算法的率失真和性能

從表3可知，在LD、RA編碼配置下，本文算法的編碼時間較編碼器HM9.0分別減少41.79%和41.98%，ΔBR總體平均值分別增加1.73%和1.12%，ΔPSNR總體平均值分別降低0.052dB和0.041dB.這一結果說明，本算法在保證良好的率失真性能的同時，大幅減少了編碼時間.其中對某些視頻序列如Vidyo1序列和Vidyo3序列，在不同配置下，編碼時間減少最高能夠達到58.21%和57.98%.分析vart值分布情況統(tǒng)計表可知，對于分辨率較高的720p高清格式視頻，vart

PMD算法利用光流法計算金字塔運動發(fā)散的特征值決定CU的分割情況，在一定程度上降低了復雜度，但其未考慮運動矢量間的相關性，導致其編碼RD性能并不十分理想，光流法基于圖像序列實現(xiàn)對光流場的精確、快速及魯棒性估計.然而，由于圖像序列目標的特性、場景中照明、光源的變化、運動的速度以及噪聲的影響等多種因素均影響光流法的有效性，因此降低了幀間快速運動估計準確性.金字塔運動發(fā)散特征值的計算存在3個假設：亮度恒定，即圖像場景中目標的像素在幀間運動時外觀上保持不變；時間連續(xù)或者運動是“小運動”，即圖像的運動隨時間的變化比較緩慢；空間一致，即一個場景中同一表面上鄰近的點具有相似的運動.然而，對于多數(shù)30Hz的攝像機，大而連貫的運動是普遍存在的情況，因此光流在實際中的跟蹤效果并不是很好.這就需要增大窗口來捕獲大的運動，而大窗口往往違背運動連貫的假設，導致編碼率失真性能下降，難以實現(xiàn)對更快和更長的運動的跟蹤.而本文算法能充分利用視頻序列中同一個對象的運動矢量相似性來改善編碼RD性能.為此將本文算法與PMD算法進行了橫向比較，表4列出了PMD算法在LD和RA編碼配置下的率失真和性能.

表4 PMD算法的率失真和性能

結合表4和表3可以看出，本文算法在LD、RA編碼配置下，較PMD算法ΔBR分別降低了0.56%和1.15%，ΔPSNR分別提高了0.027dB和0.036dB，提高了編碼的RD性能，同時編碼時間分別節(jié)約了1.19%和3.51%.

圖3 不同算法在LD、RA編碼配置下的RD曲線圖

4 結 論

為降低HEVC編碼中CU單元遞歸劃分的計算復雜度，文中基于運動矢量相似性，提出了一種快速幀間預測算法.

1) 該算法利用視頻序列中同一個對象的運動矢量相似性，通過選取當前CU單元的劃分方式，實現(xiàn)了部分可能性較低的復雜劃分方式下運動估計的提前終止.通過分析當前運動矢量差異程度和判定運動相似區(qū)域內的當前編碼塊，實現(xiàn)了運動相似區(qū)域內編碼塊的運動估計裁剪.

2) 實驗結果表明，本文算法與HM9.0 算法相比，在LD、RA編碼配置下，編碼時間分別減少了41.79%和41.98%，碼率分別增加了1.73%和1.12%，峰值信噪比分別降低了0.052dB和0.041dB.表明本文算法在保證良好的率失真性能的前提下，減少了編碼時間，降低了編碼復雜度.

[1]HANGJ,OHMJR,HANWJ,etal.OverviewoftheHighEfficiencyVideoCoding(HEVC)Standard[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology，2012,22(12):1649.

[2]ZHANGY，WONGSK，WANGX,etal.MachineLearning-basedCodingUnitDepthDecisionsforFlexibleComplexityAllocationinHighEfficiencyVideoCoding[J].IEEETransactionsonImageProcessingaPublicationoftheIEEESignalProcessingSociety,2015,24(7):2225.

[3]LAINEMAJ，BOSSENF，HANWJ，etal.IntraCodingoftheHEVCStandard[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology,2012,22(12):1792.

[4]XIONGJ,LIHL,WUQB,etal.AFastHEVCInterCUSelectionMethodBasedonPyramidMotionDivergence[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology,2014,16(2):559.

[5]KIMJ,KIMM.AnalysisoftheJND-suppressionEffectinQuantizationPerspectiveforHEVC-basedPerceptualVideoCoding[J].Hingorani,2015,4(1):22.

[6]SULLIVANGJ,WIEGANDT.Rate-distortionOptimizationforVideoCompression[J].IEEESignalProcessMagazine,1998,15(6):74.

[7]CMFU,ALSHINAE,ALSHINA，etal.SampleAdaptiveOffsetintheHEVCStandard[J].IEEETransactionsonCircuits&SystemsforVideoTechnology,2012,22(12):1755.

[8]SHENLQ,LIUZ,ZHANGXP,etal.AnEffectiveCUSizeDecisionMethodforHEVCEncoders[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology,2013,15(2):465.

[9]VANLP，PRAETERJD，WALLENDAELGV,etal.EfficientBitRateTranscodingforHighEfficiencyVideoCoding[J].IEEETransactionsonMultimedia,2015,18(3):1.

[10]WIEGANDT，OHMJR，SULLIVANGJ,etal.SpecialSectionontheJointCallforProposalsonHighEfficiencyVideoCoding(HEVC)Standardization[J].IEEETransactionsonCircuits&SystemsforVideoTechnology,2010,20(12):1661.

[11]ZHOUCT,TIANX,CHENYW.FastCodingUnitSizeDecisionforHEVC[J].JournalofZhejiangUniversity(EngineeringScience),2014,48(8):1452.

[12]FANGSQ,YUM,XUSY,etal.ANovelFastInterCodingAlgorithmforHEVC[J].JournalofOptoelectronicsLaser,2015,26(5):932.

[13]LIW,WANGRD,WANGJJ,etal.AFastIntraCodingAlgorithmwithLowComplexityforHEVC[J].JournalofOptoelectronicsLaser,2015,26(3):597.

(責任編輯、校對 張 超)

簡 訊

《西安工業(yè)大學學報》中英文摘要的寫作要點

論文摘要為讀者閱覽起引導作用,又為文獻匯編、計算機儲存、檢索做好準備,成為科技情報的重要來源.科技論文的中英文摘要在寫作時應注意的要點包括：

中文摘要：① 盡量簡短、開門見山.不寫課題研究的背景信息和在第一句話中重復題目或題目的一部分；② 包含正文的要點.重點內容,試驗研究的方法、設備、材料等均不能漏掉，且要得出結論；③ 只列出最關鍵的數(shù)據(jù)，且摘要應具有獨立性；④ 不要標榜自己的研究結果；⑤ 文中不出現(xiàn)圖、表的數(shù)據(jù)；⑥ 內容應在正文中出現(xiàn)，不表述個人觀點和未來計劃，只要純粹的文章概述；⑦ 句子應盡量簡短，只敘述新信息和發(fā)現(xiàn)，刪除和減少研究細節(jié)；⑧ 縮寫詞應附有全稱；⑨語句簡潔，專業(yè)詞匯準確.

英文摘要：不出現(xiàn)以下情況：① 一對一翻譯.避免出現(xiàn)中國式英語，專業(yè)詞匯要用專業(yè)詞語翻譯；② 主謂不一致；③ 時態(tài)不一致.

(張立新)

Estimation Algorithm of Fast Inter-Frame Motion for HEVC and Analysis of the Calculation Complexity

CHENHong,QIHua

(School of Electronic Information Engineering,Xi’an Technological University,Xi’an 710021,China)

In view of highly complicated calculation problems of inter-frame motion estimation of high efficiency video coding (HEVC),a fast termination algorithm of motion estimation on motion homogeneity was proposed.The motion homogeneity of the same object in video sequence was adopted to make a reasonable selection for the division method of current coding unit (CU) and end, in advance, motion estimation of partial and less posible complex division mode.For CU in the similar motion regions,after decomposition of next recursive depth,small prediction unit (PU) splitting motion estimation was cut.The results show:Compared with the original HEVC encoding algorithm,the proposed algorithm reduces en-coding time by 41.79% and 41.98% ,peak signal-to-noise ratio(PSNR) loss by 0.052 dB and 0.041 dB in the low-delay and random-access cases.The amount of calculation of motion estimation and the calculation complexity were reduced.

high efficiency video coding;motion estimation;motion difference;calculation complexity

10.16185/j.jxatu.edu.cn.2016.10.014

2016-03-29

陜西省教育廳科研計劃項目(12JK0503);陜西省科技廳科學技術發(fā)展計劃項目(2014K05-19)

陳 紅(1980—),女,西安工業(yè)大學講師,主要研究方向為圖像處理算法、無線傳感器網(wǎng)絡及信息論與編碼.E-mail:chenhong8008@126.com.

TN919.81

A

1673-9965(2016)10-0848-08