采用已編碼信息的HEVC幀間快速模式決策算法

許東旭，林其偉，董曉慧（華僑大學信息科學與工程學院，福建廈門361021）

采用已編碼信息的HEVC幀間快速模式決策算法

許東旭，林其偉，董曉慧
（華僑大學信息科學與工程學院，福建廈門361021）

針對高效率視頻編碼（HEVC）幀間預測高額的計算復雜度，提出一種利用已編碼塊的相關信息進行快速幀間預測的算法.首先，在每個深度級上，利用當前編碼單元聯合其時空上最近的所有已編碼單元的運動矢量（MV）長度，提前決定2 N×2 N的預測單元（PU）分割尺寸.其次，利用當前深度層獲得的率失真代價（RDcost），結合離線統計出設置的閾值，終止滿足條件的編碼單元的進一步分割進程.實驗結果表明：文中算法可以節省37.8%的編碼時間，并取得與原始算法幾乎相同的率失真性能.

高效率視頻編碼；幀間預測；編碼單元；快速模式選擇；深度

高效率視頻編碼（HEVC）作為新一代高效的視頻編碼標準，允許更大的編碼單元尺寸，最大尺寸可以達到64×64，且首次分離了3種編碼單元類型：編碼單元（CU）、預測單元（PU）、變換單元（TU）.與H.264相比較，在保證相同視頻質量的條件下，HEVC可減少50%的比特率［1］.但與此同時也引入了巨大的計算復雜度，例如，為了得到最優的CU，HEVC需窮盡地遞歸計算各種各樣CU，PU，TU的組合.在每個深度級上，對于幀內預測來說，每個PU又需要進行高達35種幀內預測模式的遍歷選擇；對于幀間預測來說，也需進行較多PU模式的決策.因此，HEVC離實時應用為時尚遠.為了早日使HEVC投入市場應用，很多研究者圍繞幀間預測優化和幀內預測優化這2個角度做了大量的努力［2－9］.本文對CU層與PU層同時進行優化，提出一種利用已編碼信息的HEVC幀間快速模式決策算法.

1 HEVC幀間預測流程

HEVC提出的編碼單元四叉樹的遞歸分割技術，如圖1所示.圖1中：最大的CU稱為編碼樹單元（CTU）.

首先，進行CTU四叉樹的遞歸劃分分割；當其不劃分時，CU尺寸為64×64，深度為0；對其進行預測編碼，得其率失真代價.然后，將該CU分割為4個子CU，每個子CU的尺寸為32×32，深度為1；對其進行預測編碼，可得各自的率失真代價（RDcost），對這4個子CU分別進行進一步的分割，如此遞歸地劃分下去；當子CU的尺寸為8×8時，即深度為3時，結束分割過程.最后，對分割的CU進行選擇，依次比較求得的各個CU的RDcost，選擇具有最小RDcost的CU尺寸作為最優的分割模式.比較4個8×8子CU的代價和是否小于其對應的16×16的CU代價，如果小于，選擇8×8的CU分割模式；否則，選擇16×16的分割模式，如此比較下去，直至當前CU的深度為0.

圖1 編碼單元四叉樹的遞歸分割技術Fig.1 Recursively split technology of quadtree of coding－units

圖1中：在每個深度級上，HEVC需要從SKIP／Merge模式、幀內預測（intra PU）模式及幀間各種PU分割尺寸，如2 N×2 N（N＝32，16，8，4），2 N×N，N×2 N中選出具有最小RDcost的模式作為最優的預測模式.如果當前深度不是最小深度（深度3），則還需對所有AMP分割模式，即對2 N×nU，2 N× nD，nL×2 N和nR×2 N進行運動估計，綜合所有得出的RDcost，從中選出最優的預測模式.在HEVC中，N×N模式只能在最小的CU尺寸時才被允許，如果最小CU的尺寸是8×8，則幀間N×N模式在HEVC中是被禁止的［10］，而在幀內是允許的.

2 快速幀間模式決策算法

2.1 基于RDcost的CU分割提前終止算法

式（1）中：Bmode為編碼當前塊需要的比特數；λmode為拉格朗日因子；SSEluma為當前的亮度塊與參考塊之間的均方差值和；SSEchroma為當前的色度塊與其參考塊之間的均方差值和；wchroma為色度塊的加權因子；Jmode為求得的率失真代價.

利用式（1）的代價函數作為評價準則，HEVC原始幀間預測以遞歸的方式對各種編碼分割進行率失真優化（RDO）計算，求得最優的編碼分割模式.直觀上，1個CU如果分割成4個子CU，那么該CU 的Jmode一般會較大；如果該CU沒有進一步分割成4個子CU，那么該CU的Jmode一般較小.因此，提出以下假設：RDcost分布可能具有一定的規律性，可以利用該規律約束某些塊不必要的分割進程.

為證明提出的假設，對各種序列進行大量的實驗，以研究RDcost隨著不同序列的分布情況.限于篇幅，選取其中一個典型的序列為例進行說明.PartyScene序列在量化參數（QP）為37時，尺寸為16× 16的CU中分割的CU和不分割的CU各自RDcost的取值分布情況，如圖2所示.圖2中：n為CU數.由圖2可知：不分割CU的RDcost集中在相對較小值的范圍內，并呈現如正態分布一樣的“單峰”特性；分割CU的RDcost分散在相對較大值的范圍內，幾乎覆蓋圖2整個橫坐標軸.以上的統計結果是文中設計基于RDcost的CU分割提前終止算法的動機.

假如取圖2中標注的Threshold為不分割CU的閾值，一旦當前深度的CU的最優RDcost小于Threshold，則可終止當前CU的進一步分割處理，即跳過余下的深度計算，這將顯著地降低編碼的計算復雜度.

從以上論述可知：Threshold在率失真性能損失與編碼復雜度減少之間起到權衡的作用.一方面，如果Threshold取得太大，則可以得到可觀的編碼時間減少量，但率失真性能的損失也會加大；另一方面，如果Threshold取得太小，雖然可以使率失真性能的損失微小，但相應減少的編碼時間減少量將相當有限.

圖2 PartyScene序列RDcost取值分布圖Fig.2 Distribution of RDcost in PartyScene sequence

綜上，閾值選取原則：使統計序列在當前深度下CU的不分割概率達到90%左右.同時，由于RDcost依賴于QP，所以閾值還需隨著QP自適應變化.得出的三組閾值（分別對應于64×64，32×32，16×16的CU），分別為

選取5個不同分辨率及運動特征各不相同的序列，證明式（2）～（4）所列閾值的有效性（節2.1算法）.QP為22，37，序列全部編碼20幀，采用HM 10.1原始的幀間CU尺寸決策，在當前CU滿足上述三組閾值條件下，統計不分割的概率，實驗結果如表1所示.表1中：“－”表示滿足條件的CU塊數很少，基本不會影響編碼器的率失真性能與編碼速度.

由表1可知：提出的基于RDcost的CU分割提前終止算法的命中率（η），對于大部分測試序列在不同QP下都達到了90%以上.

表1 基于RDcost的CU分割提前終止算法命中率Tab.1 Hit－rates of RDcost checking based on early split termination algorithm

2.2 基于MV長度的快速PU模式決策

2.2.1 算法設計的動機 一般來說，自然序列中存在大量的靜止背景區域，這些區域每層深度上選中最大的2 N×2 N的PU分割尺寸的概率一般很高.為了證明上面的假設，選擇5個典型序列，QP選取24，30，序列統一編碼30幀，統計各深度上選中2 N×2 N分割尺寸的概率，實驗結果如表2所示.

由表2可知：在每個深度級上，最優分割尺寸為2 N×2 N的概率極高，且隨著QP的增加而增加.在HM當中，首先進行SKIP模式的計算，接著進行2 N×2 N的運動估計，同時SKIP模式也是2 N×2 N分割.因此，假如在2 N×2 N運動估計后，采用有效的策略提前決定當前深度層CU最優分割為2 N× 2 N，則可以合理地跳過余下PU模式（2 N×N，N×2 N，AMP，幀內預測）的RDO計算，這將顯著地降低編碼的計算復雜度.

2.2.2 基于MV長度提前決定2 N×2 NPU分割 運動靜止的編碼單元的MV一般很小，且很可能會選擇較大的分割尺寸，如2 N×2 N分割.由于自然序列時空上的連續性，文中利用6個MV所組成的集合判斷當前編碼單元是否屬于運動靜止的區域，提前決定2 N×2 N的分割尺寸，如圖3所示.具體有以下4個步驟.

表2 各深度上2 N×2 N成為最優分割的概率Tab.2 Probabilities of 2 N×2 NPU partition being optimal partition at different depth levels

圖3 所有MV的位置關系Fig.3 Spatial relationships of all the MVs

步驟1 在當前深度層進行完2 N×2 N的運動估計后，收集所有MV信息（圖3）.

步驟2 計算每個MV的長度，即

步驟3 找出MV長度集合中最大的MV長度，即

步驟4 判斷L是否小于文中給出的閾值.若是，則終止當前深度層余下PU模式的RDO計算，直接編碼下一個深度的CU；否則，對當前深度層余下的PU模式進行RDO計算.

經過大量的實驗統計，并參考HEVC的官方測試條件［11］，得出4個QP（22，27，32，37）下的MV閾值為0，2，4，6.為了進一步證明文中基于MV長度提前決定2 N×2 N分割算法的有效性，采用5個統計序列（表1），序列統一編碼20幀，統計該算法的命中率，統計結果如表3所示.

表3 文中基于MV長度提前決定2 N×2 N分割算法的命中率Tab.3 Hit－rates of MV checking based early 2 N×2 Ndetermination algorithm

2.3 總的算法步驟

快速的幀間模式決策算法必須考慮錯誤傳播的問題.因此，提出的CU級優化算法在I幀中不執行；提出的PU級優化算法需在MV2～MV6中，至少3個存在時才執行.總的算法有以下5個步驟.

步驟1 計算SKIP模式，計算2 N×2 N模式.利用式（5），（6）判斷L是否滿足文中提出的閾值條件.若是，則當前深度層最優的PU模式為SKIP／Merge，或者2 N×2 N模式中具有較小RDcost的模式，轉至步驟3；否則，轉至步驟2.

步驟2 依次計算N×2 N模式，2 N×N模式，所有AMP模式，進行幀內預測.轉至步驟3.

步驟3 比較所有模式計算得出的RDcost，選擇最小RDcost對應的模式作為當前深度層最優的模式.轉至步驟4.

步驟4 判斷當前深度是否為3.若是，轉至步驟1；否則，轉至步驟5.

步驟5 執行節2.1基于RDcost的CU分割提前終止算法，即檢查當前深度層最優的RDcost是否小于節2.1提出的閾值.若是，終止當前CU的進一步分割；否則，將當前CU分為4個子CU，對每個子CU轉至步驟1.

3 結果與討論

實驗采用HM 10.1官方參考軟件，測試的環境為具有Intel（R）Core（TM）2Quad CPUQ9400＠2.66GHz，4.0GB內存的計算機，采用VS2008編譯器.量化參數為22，27，32，37，對HEVC官方規定的Class A～E的18個測試序列［11］進行全部測試，序列全部統一編碼50幀.快速運動估計（TZsearch）和快速編碼器決策（FEN）全開（HM 10.1默認打開）.

采用BDBR與BDPSNR衡量［12］率失真性能，兩者分別表示在同樣的客觀質量下，兩種方法的碼率節省情況，以及在給定的同等碼率下，兩種方法的Y－PSNR的差異.

時間改變量Δt定義為

式（7）中：tHM 10.1（QPi），tpro（QPi）分別為原始HM 10.1算法及提出的算法在不同QP值下的編碼時間.

選取文獻［7］與文中算法進行對比.兩者在低時延編碼配置模式［11］（LDP）編碼模式下的實驗結果，如表4所示.

表4 文中算法與文獻［7］算法的實驗結果比較Tab.4 Experimental results comparison between our overall algorithm and paper［7］

由表4可知：文中算法平均可以節省37.8%的編碼時間，同時只有0.048dB的Y－BDPSNR損失，以及1.566%的BDBR增加.文中提出的RDcost和MV的閾值，可以隨著不同的應用場合進行靈活的控制.一方面，對于實時性要求較高的場合，可以適當使閾值大些，相應地編碼復雜度也會減少得越多，但率失真性能的損失也會越大；另一方面，對視頻質量要求較高的場合，可以設置讓閾值適當小些，率失真性能也會越好，但相應地編碼時間減少量也會越少.另外，文中算法對于平坦序列的優化效果非?？捎^.由表4可知：對于Class E序列可以減少70%以上的編碼時間，同時率失真性能的損失相當微小.與文獻［7］算法對比，雖然文中算法的率失真性能損失略大，但其編碼時間減少量平均提高了17.8%.

4 結束語

針對新一代視頻編碼標準HEVC幀間預測中高額的計算復雜度，提出一種新穎的算法優化HEVC幀間預測中的模式選擇過程.基于RDcost提前終止CU的進一步分割進程；基于已編碼塊的MV長度提前決定2 N×2 N分割.實驗結果表明：文中算法可以節省37.8%編碼時間，同時保證與原始算法取得幾乎相同的率失真性能.揭示出RDcost與CU之間，以及MV與PU模式之間暗含的關系，且文中算法跟現階段大部分已發表的幀間快速算法［4－6］是獨立正交的，可與其進一步融合，更大地降低HEVC幀間編碼的計算復雜度.

［1］ SULLIVAN G J，OHM J，HAN W J，et al.Overview of the high efficiency video coding（HEVC）standard［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1649－1668.

［2］ ZHANG Hao，MA Zan.Fast intra mode decision for high－efficiency video coding（HEVC）［J］.IEEE Transactions on Circuits and Systems for Video Technology，2014，24（4）：660－668.

［3］ SHEN Liquan，ZHANG Zhaoyang，AN Ping.Fast CU size decision and mode decision algorithm for HEVC intra coding［J］.IEEE Transactions on Consumer Electronics，2013，59（1）：207－213.

［4］ CHOI K，PARK S H，JANG E S.Coding tree pruning based CU early termination［C］∥Joint Collaborative Team on Video Coding of ITU－T SG16WP3and ISO／IEC JTC1／SC29／WG11 6th Meeting.Torino：［s.n.］，2011：14－22.

［5］ GWEPM R，LEE Y L.Early termination of CU encoding to reduce HEVC complexity［J］.IEICE Transactions on Fundamentals of Electronics，Communications and Computer Sciences，2012，95（7）：1215－1218.

［6］ YANG J，KIM J，WON K，et al.Early SKIP detection for HEVC［EB／OL］.［2014－08－07］.http：∥phenix.int－evry.fr／jct／.

［7］ LEE H S，KIM K Y，KIM T R，et al.Fast encoding algorithm based on depth of coding－unit for high efficiency video coding［J］.Optical Engineering，2012，51（6）：067402（1－11）.

［8］ SHEN Liquan，LIU Zhi，ZHANG Xinpeng，et al.An effective CU size decision method for HEVC encoders［J］.IEEE Transactions on Multimedia，2013，15（2）：465－470.

［9］ XIONG Jian，LI Hongliang，WU Qingbo，et al.A fast HEVC inter CU selection method based on pyramid motion divergence［J］.IEEE Transactions on Multimedia，2013，16（2）：559－564.

［10］ YUAN Yuan，KIM I K，ZHENG Xiaozhen，et al.Quadtree based nonsquare block structure for inter frame coding in high efficiency video coding［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22 （12）：1707－1719.

［11］ BOSSEN F.HM 10common test conditions and software reference configurations［C］∥Proceedings of the 12th JCT－VC Meeting.Geneva：［s.n.］，2013：1－3.

［12］ BJONTEGARD G.Calculation of average PSNR differences between RD－curves［EB／OL］.［2014－08－07］.http：∥wftp3.itu.int／av－arch／video－site／0104＿Aus／.

（責任編輯：錢筠 英文審校：吳逢鐵）

Fast Inter Mode Decision Algorithm Using the Information of Encoded Coding Units for HEVC

XU Dongxu，LIN Qiwei，DONG Xiaohui
（College of Information Science and Engineering，Huaqiao University，Xiamen 361021，China）

In order to further reduce the great computational complexity for high efficiency video coding （HEVC）inter prediction，a novel algorithm using the information of encoded CUs has been proposed in this paper.Firstly，at each depth level，the lengths of all the MVs which are from current CU and spatially or temporarily adjacent CUs are used to decide 2 N×2 Npartition early.Secondly，by using the minimum RDcost of current CU and the off－line pre－set threshold values，the split of CUs which meet the requirements can be early termination.Experimental results show that the proposed algorithm can save an average of 37.8%of the encoding time with negligible loss of coding efficiency compared with the original algorithm.

high efficiency video coding；inter prediction；coding unit；fast mode decision；depth

TP 391

A

1000－5013（2016）04－0486－06

10.11830／ISSN.1000－5013.201604019

2014－08－07

林其偉（1957－），男，副教授，主要從事視頻編碼與網絡通信的研究.E－mail：qwlin＠hqu.edu.cn.

福建省自然科學基金資助項目（2012J01275）