基于時空預測的H.264快速幀內預測模式選擇算法

徐平，佘青山，金朝陽，徐偉棟

（杭州電子科技大學 自動化學院，浙江 杭州 310018）

1 引言

在H.264標準中，為了獲得高質量和高壓縮比，采用率失真優化RDO (rate distortion optimization)模型[1,2]進行幀內預測模式選擇。但同時，幀內預測模式選擇算法的高計算復雜度是制約H.264實際應用的主要因素之一。

針對幀內預測模式選擇的改進策略研究，成為近年來國內外的研究熱點。現有的幀內預測模式選擇改進算法，大體可分為2類：1) 簡化RDO代價函數[3]，尋找可以替代RDO，且基本不影響編碼質量的簡化RDO代價函數；2) 通過概率預測或者閾值判斷減少候選模式數[4～16]，預測各模式被選擇為最佳模式的概率，減少小概率模式的編碼；通過實驗統計等方法獲得閾值，在編碼過程中一旦滿足閾值條件，提前終止后續的模式選擇過程，減少候選模式數。

上述的第 2類方法是目前業界的主要研究趨勢。Pan等人基于邊緣方向直方圖預測最佳幀內模式，僅在幾個大概率模式中進行選擇，顯著減少候選模式數，提高編碼速度[4,5]。Wang等人提出基于邊緣強度的幀內預測算法，將4×4亮度塊的9個幀內預測模式中垂直、水平、45°、135°和DC模式作為主模式，分情況確定候選模式[6]。Wei等人采用基于NHT(non-normalized Haar transform)，提取邊緣的方向信息，排除冗余的模式[7]。Tsai等人采用梯度強度濾波算子，以確定宏塊的方向性，減少候選模式數量[8]。蔣剛毅等人計算4×4亮度參考塊的方差，對于方差較小的亮度塊，僅采用幾種概率高的預測模式[9]。賈克斌等人提出了一種基于自相關性的幀內預測算法，該算法在進行幀內預測之前先進行宏塊預判，從2種預測模式中選擇一種，從而減少算法的復雜度[10]。蘇睿等人利用變換域的信息得到圖像紋理方向，僅在的幾個高概率模式中進行模式選擇，降低運算量[11]。陸璐等人對塊的細節程度和紋理方向進行分析，根據細節程度和紋理方向對模式進行篩選，從而提高模式搜索速度[12]。黃凱等人在Sobel模式判決算法的基礎上，提出一種面向VLSI的模式優化算法[13]。騰國偉等人利用色度塊和亮度塊以及4×4亮度塊和16×16亮度塊模式選擇之間的相關性，提出一種基于 RDO的快速模式選擇算法[14]。文獻[15]通過大量實驗觀察得出以下結論：多參考幀運動估計中的最佳匹配塊的幀內模式是當前塊時域的最佳幀內預測模式。基于此結論，采用與最佳匹配塊重疊像素最多已編碼塊的幀內模式作為當前塊的最佳幀內預測模式。文獻[16]提出了基于時空相關性的快速模式選擇算法。該算法應用于 AVS-M 平臺，其模式預測是基于以下假設：圖像塊時域間的距離越近，時域相關性越高，預測模式相關性越強。由于該算法不是基于文獻[15]的觀察結果，算法的時域預測準確性有待進一步提高。

Pan等人[4,5]提出的基于邊緣方向直方圖的快速幀內預測模式選擇算法（以下簡稱Pan算法）是第2類方法中具有代表性的一種算法，可在保持較好的編碼圖像質量的同時較大地提升編碼速度。但是，該算法僅利用了塊內部紋理信息進行候選模式的概率預測，沒有充分利用編碼過程中存在的時域和空域相關性，因此，編碼效率還有待提高。本文在Pan算法的基礎上，充分考慮編碼過程中的時域和空域相關性，提出了基于時空預測的H.264快速幀內預測模式選擇算法，進一步精簡候選模式數，從而進一步提高幀內預測模式選擇的速度。

2 Pan算法的空域改進

在Pan算法中，分3種塊類型(16×16亮度塊、4×4亮度塊和8×8色度塊)分別建立各自的邊緣方向幀內預測模式概率直方圖，減少候選模式數。Pan算法通過在初始化過程中引入高計算復雜度的Sobel算子運算獲得內部塊的紋理方向概率直方圖，確定候選模式數。Pan算法僅利用了塊內部的紋理信息，而未充分利用空域已編碼鄰塊的信息。本文通過引入已編碼鄰塊信息，利用已編碼鄰塊幀內模式構建當前編碼塊的空域最佳模式概率直方圖，確定空域候選模式。

3 Pan算法的時域改進

Pan算法僅利用當前塊的內部信息來預測最佳幀內模式，以提高幀內預測模式選擇的速度，沒有考慮視頻序列的時域相關性。此外，在初始化階段的Sobel算子求概率過程，復雜度較大，較大地增加了編碼開銷。

視頻圖像不僅在空域上具有較高的相關性，而且在時域上也有很高的相關性。由于H.264中是先進行多參考幀運動估計，然后進行幀內模式選擇確定最終編碼模式，因此在進行幀內模式選擇之前已獲得最佳匹配塊。本文利用最佳匹配塊構建當前編碼塊的時域最佳模式概率直方圖，預測當前塊的最佳幀內模式，并避免復雜的 Sobel算子運算。

4 算法實現

基于時空預測的快速幀內預測模式選擇算法利用了幀間運動估計最佳匹配塊的信息，為了盡量減少幀間編碼的差錯擴散，算法對 I幀采用全搜索方法，從而得到 I幀的最佳幀內模式，并保存下來。

基于時空預測的快速幀內預測模式選擇算法的流程如圖1所示，詳細步驟描述如下。

1) 初始化

當一個塊編碼完畢，保存其最佳幀內模式。每一幀編碼結束后，保存該幀的所有不同大小塊（每個塊包括1個16×16亮度塊、16個4×4亮度塊和2個8×8色度塊）的最佳幀內模式，保存的幀數等于參考幀的總數。

圖1 基于時空預測的快速幀內模式選擇算法流程

2) 基于空域的模式預測

通過相鄰已編碼塊預測當前塊的幀內模式。圖2給出了空域模式預測的當前塊E及其相鄰已編碼塊A、B、C和D的示意圖，由式（1）可求得當前塊E的空域最佳模式概率直方圖：

其中，M[0]、M[1]、M[2]和M[3]分別為相鄰已編碼塊A、B、C和D的最佳幀內模式；a[0]、a[1]、a[2]和a[3]分別表示A、B、C、D與當前塊E的相關程度(值為0到1之間)，h(M[i])表示幀內模式M[i]為當前塊最佳預測模式的概率。考慮到A和B與E直接相鄰，相關程度較大，而C和D與E是對角相鄰，其相關程度相對較小，假定有如下關系：a[2]+a[3]＞a[1]=a[0]＞a[2]=a[3]。實驗中，a[0]、a[1]、a[2]和a[3]分別設為1、1、0.7和0.7。

圖2 基于空域的模式預測

利用式（1），可以分別得到4×4亮度塊、16×16亮度塊和8×8色度塊的空域最佳幀內模式概率直方圖。圖3給出了當4×4亮度塊的相鄰已編碼塊A、B、C和D的幀內編碼模式分別是模式5、模式2、模式3和模式3時，即M[0]、M[1]、M[2]和M[3]的值分別為5、2、3和3，當前塊E的空域最佳幀內模式概率直方圖。可以看出，模式3的概率最大，模式2和模式5的概率次之，而其余模式的概率很小。將概率直方圖中幅值最大者作為空域最佳幀內預測模式，記為P[0]。

圖3給出僅存在一個最佳空域幀內預測模式的情況。當A、B、C和D的編碼模式均不相同時，A和B的編碼模式同為最大概率模式，此時將A和B的模式均作為最佳空域幀內預測模式，分別記為P[0]和 P[1]。

圖3 4×4亮度塊的空域最佳幀內模式概率直方圖

3) 基于時域的模式預測

通過最佳匹配塊從時域預測最佳幀內模式。如圖4所示，經過多參考幀運動估計得到當前塊E的最佳匹配塊為R。根據最佳匹配塊R在參考幀中與已編碼塊重疊的位置，可分為R1、R2、R3和R4 4個子塊。利用各子塊所屬已編碼塊的最佳幀內模式和各子塊的像素面積可求得時域最佳模式概率直方圖。

圖4 最優匹配塊幀內模式預測

幀內模式網格的構造過程如下：每一幀編碼結束后，按照每個塊的空間位置存儲每個塊的最佳幀內模式，構成幀內模式網格。網格的大小等于塊的個數。針對3種不同類型的塊(4×4亮度塊、16×16亮度塊和8×8色度塊)，采用3個大小不同的網格來存儲不同類型塊的最佳幀內模式。

記 1R、 2R、 3R和 4R所包括的像素個數分別為 N[0]、N[1]、N[2]和 N[3]。M[0]、M[1]、M[2]和M[3]分別保存 R1、R2、R3和 R4所屬已編碼塊的最佳幀內模式，塊內總的像素數為

由式（2）可以得到時域最佳幀內模式概率直方圖。

圖5給出了4×4亮度塊E的最佳匹配塊R的子塊R1、R2、R3和R4所屬已編碼4×4亮度塊的最佳幀內模式分別是2、2、4和5時的最佳幀內模式概率直方圖。可以看出，模式5的概率最大，模式2的概率次之，接著是模式 4，其余模式的概率很小。取概率直方圖中幅值最大者作為時域最佳幀內預測模式，記為C[0]。當出現k個相同的概率最大模式時，將這 k個時域最佳幀內預測模式記為C[k-1]。

圖5 4×4亮度塊的時域最佳幀內模式概率直方圖

針對C[k-1]中是否包括DC模式，進行以下討論。

a) 對于4×4亮度塊，分以下2種情況：

第1種情況，C[k-1]中包括DC模式，此時認為DC模式概率很大，舍棄其他模式，最終只保留DC模式；

第2種情況，C[k-1]中不包括DC模式，將DC模式增加為候選模式。

b) 對于16×16亮度塊和8×8色度塊，分以下2種情況：

第1種情況，當C[k-1]中存在DC模式時，此時認為DC模式概率很大，舍棄其他模式，最終只保留DC模式；

第2種情況，當C[k-1]中不存在DC模式時，增加DC模式作為候選模式。

4) 得到最終的候選模式

合并上述空域和時域最佳幀內預測模式的結果，得到最終候選模式。

5) 經過以上步驟，候選模式數顯著減少，對最終候選模式采用RDO算法求得最佳模式。

5 算法復雜度分析

表1給出了JM98、Pan算法（記為Pan）、基于空域預測的快速幀內預測模式選擇算法（記為New1）和基于時空預測的快速幀內預測模式選擇算法（記為 New2）的復雜度比較，采用最終候選模式數和是否采用Sobel算子衡量算法復雜度。其中，基于空域預測的快速幀內預測模式選擇算法在初始化過程中與Pan算法一樣也采用了Sobel算子確定初始的幀內模式，帶來了較大的編碼代價。基于時空預測的快速幀內預測模式選擇算法在 4×4亮度塊的基于空域和時域的預測部分時各取得一種模式的概率較高，再加上可能的DC模式，最終的候選模式一般為1或2或3種。

表1 各算法復雜度比較

6 實驗結果

實驗采用的硬件環境：AMD Athlon(tm) 64 Processor 3200+ 2.0GHz ；512MB內存；操作系統：Windows XP Professional Sevice Pack 2；軟件實現平臺：JM98校驗模型。實驗采用5個標準測試序列，包括3個QCIF序列(News、Foreman和Silent)和2個CIF序列(Mobile和Container)。實驗參數設置如下。

1) 采用 RDO；

2) 采用CABAC；

3) 采用hardama變換；

4) 幀率，QCIF：10Hz；CIF：30Hz；

5) QP 取值：28、32、36、40；

6) 編碼幀數：100；

7) GOP類型：IPPP格式；

8) 運動估計搜索半徑，QCIF：16像素；CIF：32像素；

9) 參考幀數：5；

10) 運動估計精度：1/4像素。

采用編碼時間、比特率和平均信噪比的減少百分數來衡量算法的優化性能。其中編碼時間減少百分數采用式（3）計算。

比特率減少百分數采用式（4）計算。

平均信噪比（PSNR）減少百分數采用式（5）計算。

表2給出了Pan、New1和New2 3種算法CPU總耗時減少百分數比較，基于時空預測的快速算法與其他 3種算法相比，平均編碼耗時分別降低35.81%、13.10%和9.98%，編碼時間顯著減少。表3給出3種算法輸出碼率減少百分數的比較，基于時空預測的快速算法與其他3種算法輸出碼率相差不大。表4給出3種算法亮度分量的平均PSNR減少百分數的比較，4種算法的平均PSNR值基本一致。圖6給出這5個標準測試序列的率失真比較，這4種算法的率失真曲線基本是重合的，這說明基于時空預測的快速幀內預測模式選擇算法與其他3種算法相比，具有基本相同的率失真性能。

表2 編碼時間的比較

表3 輸出碼率的比較

表4 輸出PSNR的比較

圖6 算法的率失真曲線

7 結束語

通過以上實驗和分析，可以得出以下結論，與JM98全搜索算法、Pan快速算法和基于空域的預測算法相比較，基于時空預測的快速幀內預測模式選擇算法在保持較好的編碼圖像質量的同時，平均編碼總耗時分別降低35.81%、13.10%和9.98%，顯著提高編碼速度，從而顯著提升H.264的編碼性能。

[1] ORTEGA A, RAMCHANDRAN K. Rate-distortion methods for image and video compression[J]. IEEE Signal Processing Magazine,1998, 15∶ 23-50.

[2] WIEGAND T, GIROD B. Lagrange multiplier selection in hybrid video coder control[A]. IEEE International Conference on Image Processing[C]. 2001. 542-545.

[3] KIM H, ALTUNBASAK Y. Low-complexity macroblock mode selection for H.264/AVC encoders[A]. Proceedings of the 2004 Interna-tional Conference on Image Processing[C]. 2004. 765-768.

[4] PAN F, LIN X, RAHARDJA S, et al. Fast Mode Decision for Intra Prediction[R]. JVT 7th Meeting Pattaya, Thailand IEEE JVT-G013,2003.

[5] PAN F, LIN X, RAHARDJA S, et al. Fast mode decision algorithm for intraprediction in H.264/AVC video[J]. Coding Circuits and Systems For Video Technology, IEEE Transactions, 2005, 15(7)∶ 813-822.

[6] WANG J, WANG J, CHEN J, et al. A novel fast algorithm for intra mode decision in H.264/AVC encoders[A]. Proceedings of the IEEE International Symposium[C]. 2006. 3498-3501.

[7] WEI Z Y, LI H L, KING N N. An efficient intra mode selection algorithm for H.264 based on fast edge classification[A]. ISCAS 2007[C].2007. 3630-3633.

[8] TSAI A C, PAUL A, WANG J C, et al. Efficient intra prediction in H.264 based on intensity gradient approach[A]. IEEE International Symposium[C]. 2007. 3952-3955.

[9] 蔣剛毅, 李世平, 葉錫恩等. 基于塊參考像素特征的快速幀內預測模式選擇新算法[J]. 電子與信息學報, 2006, 28(10).1874-1878.JIANG G Y, LI S P, YE X E, et al. A novel fast mode selection algorithm for intra prediction based on characteristics of block’s reference pixels[J]. Journal of Electronics & Information Technology, 2006,28(10)∶ 1874-1878.

[10] 賈克斌, 謝晶, 方晟. 一種基于自相關法的H.264/AVC高效幀內預測算法[J]. 電子學報, 2006, 34(1).152-154.JIA K B, XIE J, FANG S. An efficient intra-frame prediction algorithm based on autocorrelation for H.264/AVC[J]. Acta Electronica Sinica,2006, 34(1)∶152-154.

[11] 蘇睿, 劉貴忠, 張彤宇等. 利用變換域信息快速實現H.264 幀內預測編碼的新算法[J], 電子與信息學報, 2007, 29(1)∶161-165.SU R, LIU G Z, ZHANG T Y, et al. Fast mode decision algorithm for intraprediction in H.264/AVC with integer transform[J]. Journal of Electronics & Information Technology, 2007, 29(1)∶161-165.

[12] 陸璐, 周維. 適用于 H.264 的快速模式選擇算法[J]. 通信學報,2006, 27(7)∶117-121.LU L, ZHOU W. Efficient inter mode selection algorithm for H.264[J].Journal on Communications, 2006, 27(7)∶117-121.

[13] 黃凱, 秦興, 嚴曉浪等. 一種 H.264 幀內預測模式判決算法及VLSI 實現體系[J]. 電子學報, 2007, 35(2)∶207-211.HUANG K, QIN X, YAN X L, et al. A H.264 intra prediction mode decision algorithm and VLSI implementation[J]. Acta Electronica Sinica, 2007, 35(2)∶207-211.

[14] 騰國偉, 王國中, 張兆揚等. 一種基于自適應閾值的H.264/AVC幀內預測模式快速選擇算法[J]. 自動化學報, 2006, 32(4)∶526-533.TENG G W, WANG G Z, ZHANG Z Y, et al. A fast intra-prediction mode selection algorithm of H.264/AVC based on adaptive thresholds[J]. Acta Automatica Sinica, 2006, 32(4)∶526-533.

[15] HWANG M C, CHO J K, KIM J S, et al. Fast Intra Prediction Mode Selection Scheme Using Temporal Correlation in H.264[R]. IEEE Region 10 TENCON 2005, 2005. 1-5.

[16] 戴聲奎, 喻莉, 朱光喜等. 基于視頻時空相關性的幀內預測模式抉擇[J]. 通信學報, 2005, 26(11)∶ 43-48.DAI S K, YU L, ZHU G X, et al. Intra-prediction mode decision based on video temporal and spatial correlation[J]. Journal on Communications, 2005, 26(11)∶43-48.