二維直方圖的HEVC幀內快速深度決策算法

許東旭, 林其偉

(華僑大學 信息科學與工程學院， 福建 廈門 361021)

二維直方圖的HEVC幀內快速深度決策算法

許東旭, 林其偉

(華僑大學 信息科學與工程學院， 福建 廈門 361021)

摘要：針對高效率視頻編碼(HEVC)幀內預測高額的計算復雜度，提出一種基于二維直方圖的快速深度決策算法.首先，對當前最大編碼單元(LCU)采用3×3矩陣進行濾波；然后，分別統計原始LCU以及濾波后LCU的像素分布，生成二維灰度直方圖.通過該二維直方圖所表征的紋理特征，進行深度的自適應選擇，減少不必要的深度計算.實驗結果表明：同原始HM10.1相比，文中提出的算法可以節省編碼時間21.6%，同時保證視頻質量幾乎不變.

關鍵詞：高效率視頻編碼； 深度； 二維直方圖； 快速模式選擇； 編碼單元； 灰度直方圖

高效率視頻編碼(high efficiency video coding,HEVC)是繼H.264之后，又一新的視頻編碼標準.相比H.264,它引進了大量的創新技術，即更多編碼單元尺寸的選擇及更多幀內預測模式的選擇.同時，創新性地引入了3種新型編碼單元的概念：編碼單元(coding unit，CU)，預測單元(prediction unit，PU)，變換單元(transform unit，TU).這些創新技術使HEVC相比于H.264在提供相同視頻質量的同時，又可節省將近50%比特率[1]，但是它也引入了巨大的計算復雜度.如為了得到最優的CU，HEVC需窮盡地遞歸搜索CU,PU,TU的最優組合[2]，同時對于每個CU幀內又需要遍歷高達35種的預測模式.所以，現階段很多學者圍繞CU尺寸的快速選擇以及幀內模式的快速決策這2個角度，做了大量的努力.Silva等[3]利用5個濾波模板求得當前PU的主要邊緣方向，并依據求得的主要邊緣方向進一步減少模式計算的數量.Shen等[4]對當前編碼塊與其周圍相鄰的編碼塊的空間相關性做了研究.Jiang等[5]利用Sobel算子提取當前CU的邊緣信息，按生成的邊緣梯度直方圖進一步排除冗余的預測模式.Ting等[6]利用DCT變換后的系數進行邊緣檢測，以此進一步減少模式數量.Xu等[7]的前期工作對基于自相關函數的快速深度決策算法進行了報導.Zhang等[8]采用4個方向的梯度濾波器判斷當前CU的紋理特征，提前決定當前CU是否進行分割.Kim等[9]利用離線設置的率失真代價(rate-distortion cost，RDcost)閾值，提前終止某些CU的進一步分割.文獻[8-9]的主要思想都是采用某種策略終止某些塊的分割進程，即對分割的子樹進行修剪.上述這些算法都在一定程度上減少了HEVC的編碼復雜度，但HEVC仍不利于實時應用，所以有必要進一步研究高效準確的快速算法來優化HEVC編碼器.從子樹修剪的角度加速HEVC的編碼器是個好方法，但搜索深度仍然固定.本文從提取當前最大編碼單元(largest coding unit，LCU)內部的紋理特征角度，利用改進的二維直方圖法[10]，建立二維直方圖與當前LCU深度之間的統計關系，提出了一種新的快速深度決策算法.

圖1　遞歸CU結構的圖解Fig.1　Illustration of the split procedure of recursive CU

1HEVC幀內預測過程

HEVC采用四叉樹的遞歸分割結構，如圖1所示.首先，當CU不劃分時稱為LCU，其尺寸為64×64，深度為0，對該LCU進行預測編碼，得其率失真(rate-distortion，RD)代價.然后，對LCU進行分割，此時CU的尺寸為32×32，深度為1，同樣對當前CU進行預測編碼，得其RD代價.若當前CU尺寸為8×8時，即深度為3時，便不再進行分割.接著,從8×8的CU尺寸開始，往上進行修剪：比較4個8×8的RD代價是否小于其上一深度對應的16×16尺寸CU的RD代價，若小于，則選擇8×8的CU尺寸;否則，選擇16×16尺寸的CU;如此比較下去，直到深度為0.最后,選出具有最小RD代價的CU作為最終的分割模式.

對于幀內2N×2N的CU，其對應的PU尺寸只能為N×N或2N×2N.而N×N的PU在當前CU為8×8時，才被允許使用.

圖2　HEVC的幀內算法流程圖Fig.2　Flowchart of the intra prediction in HEVC

同時，在每個深度級上，HEVC的幀內預測需在包括2~34等33種角度預測模式以及planar和DC模式之間進行率失真優化(rate distortion optimization，RDO)計算后，選取具有最小RD代價的模式作為最優的預測模式.可見其計算量相當巨大.為了緩解對35種模式進行RDO計算所帶來的高額計算復雜度，HEVC進行粗略模式選擇(rough mode decision，RMD)過程[11]：首先，利用Hadamard變換代替RDO計算；然后，從35種模式中粗略選出N個具有最小的Hadamard代價(即對殘差進行Hadamard變換求得該殘差的變換絕對差值和，同時考慮需要編碼的比特數這兩者所花費的代價)作為候選模式，并且考慮了當前CU來自左邊與上邊CU的最有可能模式(most probable modes，MPMs)；最后，對這可能的N到N+2個候選模式進行RDO計算，從中選出代價最小的預測模式作為最優的模式.該算法極大地提高了HEVC的編碼速度.幀內總的預測算法流程，如圖2所示.

2基于二維灰度直方圖的快速深度決策算法

文中算法之所以考慮二維直方圖，是因為普通的一維直方圖只是統計了某一個LCU的像素組成，不能反映出該LCU所有像素的位置信息及其內部特征.通常一個LCU塊內部周圍的像素相關性是非常強的，所以要充分利用這些相關性.基于上述分析，首先，根據當前像素與其周圍像素的相關程度(與當前像素的距離大小)的高低采用不同的權值進行求和，并通過當前像素與濾波后的像素聯立構造二維像素直方圖.可見該二維直方圖不僅利用了該像素本身攜帶的信息，而且還利用了其周圍像素的信息，這在一定程度上可以反映出當前LCU的紋理特征.然后，利用該提取的紋理特征選擇當前LCU最有可能的深度范圍，跳過不必要的深度計算，加快編碼速度.

2.1　二維直方圖的構造

圖像的灰度直方圖是統計某一幅圖像的灰度級內容，它表達了某一幅圖像各個灰度級出現的次數或者概率.其橫軸覆蓋的灰度級范圍可以表示出當前圖像的色調變化情況，縱軸可以表示當前色調范圍內的灰度值數量或者頻率.從灰度直方圖可以讀出該幅圖像的很多信息.比如，如果某一灰度級出現的次數很多，說明組成該幅圖像的灰度值種類較少，該幅圖像色調比較單一，紋理可能相對平坦；相反，如果組成該幅圖像的灰度級有很多種，說明該幅圖像的色調變化劇烈，紋理可能很復雜.由此可知:可以通過統計當前LCU的灰度組成，來判別當前LCU是否平坦.因為直觀上，一個LCU若處于一幅圖像的背景區域，那么其紋理應該相對平坦，對于紋理較為平坦的LCU，一般不可能分割到太小的尺寸；相反，一個LCU若處于圖像的邊緣或細節區域，那么其紋理應該會相對復雜，此類LCU一般要分割到比較小的尺寸.所以,研究一個LCU的紋理特征有助于提前決策出當前LCU需要進行RDO計算的深度級，從而跳過不必要的深度計算.

通過構造二維直方圖來提取當前LCU的紋理特征.因為二維直方圖不僅利用了本身的像素信息，而且也包含了周圍像素的信息，這在很大程度上能夠表示出當前CU的內部紋理特征.而對于紋理比較復雜的編碼塊，一般會分割到比較小的尺寸，即比較大的深度，對于此類編碼塊，可以直接跳過大尺寸分割時的編碼計算；反之亦然.

為了減少計算量，首先對當前64×64 尺寸的LCU分成16×16個4×4的子塊；然后，對每個4×4子塊的像素進行求平均；最后，對于64×64的LCU，可以得到16×16=256個像素值.把由這256個像素所組成的LCU記為P.通常來講，距離當前像素越近的像素與當前像素的相關程度應該越高，所以根據當前像素與其周圍像素相關程度的高低分配不同的權值，同時需要滿足權值的累加和為1.定義矩陣模板為

(1)

利用該模板進行濾波，并把濾波后的LCU記為Q.取P中的任一像素值(記為X)和Q中的任一像素值(記為Y)，X與Y都屬于[0,255]區間內，統計由(X,Y)組成的坐標出現的次數，并把相應坐標出現的次數記為Z，可見Z屬于[0,256]區間內.最后由(X，Y,Z)可以生成當前LCU的二維灰度直方圖.通過以上描述可知，該二維灰度直方圖不僅考慮了當前像素的信息，還包含了其周圍像素的信息.

HEVC中某個典型的紋理較平坦的LCU的二維灰度直方圖，如圖3所示.由圖3可知：通過使用HEVC的編解碼參考軟件HM 10.1，該LCU經過RDO計算后，最終以當前深度0作為最優的深度.HEVC中某個典型的紋理復雜的LCU的二維灰度直方圖，如圖4所示.由圖4可知：該LCU經過RDO計算后，最終分割到了深度3.圖3~4有力地證明了之前的假設，即LCU的二維灰度直方圖確實能在一定程度上反映出當前LCU需要分割到的深度級.

圖3　典型的紋理平坦的LCU二維灰度直方圖　　　　　圖4　典型的紋理復雜的LCU二維灰度直方圖Fig.3　Typical two-dimensional histogram 　　　　　Fig.4　Typical two-dimensional histogram of a homogeneous LCU 　　　　　　　　　of a complicated LCU

2.2　算法流程

從圖3~4所示2種典型紋理的LCU的直方圖特征可以進一步發現：對于圖3的灰度值對應的最大像素個數是一個較大的值，說明這類平坦的LCU主要僅有幾種灰度組成，很有可能是平坦的；相反，對于圖4比較分散，其灰度值對應的最大像素個數值較小，說明該類LCU由多種灰度級構成，該類LCU內部的灰度變化可能會比較劇烈.根據這樣的特點，考慮選取當前LCU生成的二維直方圖中灰度值對應的最大像素個數值，結合設置的閾值進行判斷.

經過以上分析及對大量閾值和不同序列進行測試后，基于二維直方圖的快速深度決策算法具體有如下3個步驟.

步驟1對當前LCU分成16×16個4×4的子塊，然后對每個4×4子塊的像素進行求平均，得到256個像素值.采用式(1)所示的模板對這256個像素進行濾波，統計由該原始LCU以及濾波后的LCU的像素分布，構造二維灰度直方圖.

步驟2找出該二維灰度直方圖最大的像素個數值，記為max_value.

步驟3判斷max_value所屬的區間.如果max_value<10，則當前LCU的最小深度級設置為2；如果10≤max_value<30，則當前LCU的最小深度級設置為1；如果30≤max_value<40，則當前LCU的最小深度級設置為1，同時最大深度級設置為2；如果40≤max_value<50，則當前LCU的最大深度級設置為2；如果max_value≥50，則當前LCU的最小與最大深度級同時設置為0.

經過上述分析可知:文中算法是采用4個閾值，即10,30,40,50，將搜索的深度區間分為5種，即[2,3],[1,2,3],[1,2],[0,1,2],[0].可以看出:相比HEVC原始幀內預測算法均統一進行4個深度級[0,1,2,3]的RDO計算，采用文中算法至少可以減少1個深度級的RDO計算.若此時減少的剛好是深度級3，則可以減少64次CU的RDO計算，減少的編碼時間相當可觀.

為了證明4個閾值(10,30,40,50)的合理性，取紋理特征互不相同的4個序列，量化參數分別選取22，27，32，37，統計其命中率,結果如表1所示.通過表1可以看出：基于二維直方圖快速深度決策算法對于測試序列命中率高達90%以上，說明文中算法可精確排除不必要的深度計算.

表1　文中算法命中率

3實驗結果與分析

采用HM10.1測試模型，測試的環境為具有Intel(R) Core(TM)2 Quad CPUQ9400 @2.66 GHz,4.0 GB內存的計算機，采用VS2008編譯器.因為文中只針對幀內編碼進行優化，故采用的編碼配置為全幀內編碼模式，量化參數(quantization parameter,QP)分別選取22,27,32,37，序列全部統一編碼50幀，其余為默認配置[12].

分別選取了A，B，C，D，E 5個等級的分辨率共11個序列進行測試.需要注意的是，本節所用的11個實驗序列不與表1中的統計序列重合.由于文獻[4]同樣提出了幀內快速深度決策算法，所以本實驗也實現了文獻[4]的快速深度決策算法部分，用以與文中算法進行比較.采用文獻[4]和文中算法與原始HM10.1比較的實驗結果，如表 2所示.表2中：BDBR(Bj?ntegaard delta bit rate)與Y-BDPSNR(Y-Bj?ntegaard delta peak signal-to-noise ratio)是文獻[13]中提出的評價準則，分別表示在同樣的客觀質量下，2種方法的平均碼率節省情況，以及在給定的同等碼率下，2種方法的平均Y-PSNR(Y-peak signal-to-noise ratio)的差異.

時間改變量Δt定義為

(2)

式(2)中:tHM10.1(QPi),tpro(QPi)分別為原始HM10.1和文中算法在不同QP值下的編碼時間.

由表2可知：文中算法與原始HM10.1相比，平均Y-BDPSNR僅降低0.036 dB,平均BDBR僅增加0.865%，同時可以節省21.6%的編碼時間.從表2可以進一步看出：文中算法對于像PartyScene這類紋理清晰的序列有較好的預測，基本不會影響其率失真性能，且同時可以減少23.8%的編碼時間.與文獻[4]相比，兩者的率失真性能幾乎相近，但文中算法編碼時間減少量更多，提高了2.2%.文中算法是基于當前LCU塊的內部紋理特征，而文獻[4]是基于一幀視頻內空間上的連續性，即當前LCU塊與周圍已編碼的LCU塊最優深度之間滿足的較強相關性.所以，文中算法獨立于文獻[4]的算法，可以與其進一步融合，更大地減少HEVC的幀內編碼復雜度.

表2　文中算法與文獻[4]比較的實驗結果

圖5　文中算法與原始HM10.1算法的RD曲線Fig.5　RD curves of the proposed algorithm and original algorithm

Traffic序列(class A 2 560×1 600)分別采用文中算法與原始HM10.1算法的RD曲線，如圖5所示.由圖5可知：該序列采用文中算法后的RD曲線與采用原始算法的RD曲線幾乎重合，即在不同的比特率上,文中算法幾乎與HEVC原始算法取得相同的Y-PSNR，這也進一步說明文中算法具有較高的命中率.

4結束語

通過構造二維直方圖提取當前LCU的紋理特征，并利用該紋理特征進行深度的自適應選擇，跳過不必要的深度計算.實驗結果表明：文中算法可以保證取得與原始HM10.1幾乎相同的率失真性能，同時可以減少編碼時間21.6%，極大地降低了HEVC的編碼復雜度；而且，文中算法獨立于現階段出版的大部分幀內快速算法，可以與其他幀內快速算法融合,進一步減少HEVC的幀內編碼復雜度.現階段所做的研究工作都在快速CU尺寸決策的層面上進行，今后的工作將嘗試對幀內35種預測模式進行優化，使多種方法融合，以更大地減少HEVC的編碼復雜度.

參考文獻：

[1]HAN G J,OHM J R,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]BOSSEN F,BROSS B,SUHRING K,et al. HEVC complexity and implementation analysis[J].IEEE Transactions on Circuits and Systems for Video Technology,2012,22(12):1685-1696.

[3]da SILVA T L,AGOSTINI L V,da SILVA CRUZ L A.Fast HEVC intra prediction mode decision based on EDGE direction information[C]∥20th European Signal Processing Conference.Bucharest:IEEE Press,2012:1214-1218.

[4]SHEN Li-quan,ZHANG Zhao-yang,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.

[5]JIANG Wei,MA Han-jie,CHEN Yao-wu.Gradient based fast mode decision algorithm for intra prediction in HEVC[C]∥2nd International Conference on Consumer Electronics, Communications and Networks.Yichang:IEEE Press,2012:1836-1840.

[6]TING Y C,CHANG T S.Fast intra prediction algorithm with transform domain edge detection for HEVC[C]∥Asia Pacific Conference on Circuits and Systems.Kaohsiung:IEEE Press,2012:144-147.

[7]XU Dong-xu,LIN Qi-wei,DONG Xiao-hui.Fast intracoding unit size decision algorithm for high-efficiency video coding[J].Journal of Electronic Imaging,2014,23(1):1-13.

[8]ZHANG Yong-fei,LI Zhe,LI Bo.Gradient-based fast decision for intra prediction in HEVC[C]∥Visual Communications and Image Processing.San Diego:IEEE Press,2012:1-6.

[9]KIM J,CHOE Y,KIM Y G.Fast coding unit size decision algorithm for intra coding in HEVC[C]∥IEEE International Conference on Consumer Electronics.Las Vegas:IEEE Press,2013:637-638.

[10]謝晶,賈克斌.一種基于二維直方圖的H.264/AVC快速幀內預測判決算法[J].電子與信息學報,2005,27(7):1053-1057.

[11]ZHAO Liang,ZHANG Li,MA Si-wei,et al.Fast mode decision algorithm for intra prediction in HEVC[C]∥Visual Communications and Image Processing.Tainan:IEEE Press,2011:1-4.

[12]BOSSEN F.HM 10 common test conditions and software reference configurations[C]∥12th Joint Collaborative Team on Video Coding Meeting.Geneva:[s.n.],2013:JCTVC-L1100.

[13]BJONTEGARD G.Calculation of average PSNR differences between RD-curves[C]∥13th Video Coding Experts Group Meeting.Austin:ITU-T VCEG,2001：VCEG-M33.

(責任編輯： 黃曉楠英文審校： 吳逢鐵)

Fast Depth Decision Algorithm Based on Two-Dimensional

Histogram for HEVC Intra Coding

XU Dong-xu, LIN Qi-wei

(College of Information Science and Engineering, Huaqiao University, Xiamen 361021, China)

Abstract：In order to further reduce the great computational complexity for high efficiency video coding (HEVC) intra coding prediction high cost case, a fast depth decision algorithm based on two-dimensional histogram has been proposed in this paper. First, a 3×3 matrix is used to filter the current largest coding unit (LCU). Then, a two-dimensional histogram which is based on the distribution of gray values of the original LCU and the filtered LCU can be generated. By using the two-dimensional histogram, some of the depth levels which are unnecessary can be skipped. Experimental results show that the proposed algorithm can save 21.6% of the encoding time on average with negligible loss of coding efficiency compared with the original HM10.1.

Keywords：high efficiency video coding; depth; two-dimensional histogram; fast mode decision; coding unit; gray histogram

基金項目：福建省自然科學基金資助項目(2012J01275)

通信作者：林其偉(1959-)，男，副教授，主要從事HEVC中的快速算法的研究.E-mail:qwlin@hqu.edu.cn.

收稿日期：2013-12-23

中圖分類號：TN 919.81

文獻標志碼：A

doi:10.11830/ISSN.1000-5013.2015.01.0023

文章編號：1000-5013(2015)01-0023-06