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

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

1 引言

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

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

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

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

2 Pan算法的空域改進

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

3 Pan算法的時域改進

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

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

4 算法實現(xiàn)

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

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

1) 初始化

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

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

2) 基于空域的模式預測

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

其中，M[0]、M[1]、M[2]和M[3]分別為相鄰已編碼塊A、B、C和D的最佳幀內(nèi)模式；a[0]、a[1]、a[2]和a[3]分別表示A、B、C、D與當前塊E的相關(guān)程度(值為0到1之間)，h(M[i])表示幀內(nèi)模式M[i]為當前塊最佳預測模式的概率?？紤]到A和B與E直接相鄰，相關(guān)程度較大，而C和D與E是對角相鄰，其相關(guān)程度相對較小，假定有如下關(guān)系：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色度塊的空域最佳幀內(nèi)模式概率直方圖。圖3給出了當4×4亮度塊的相鄰已編碼塊A、B、C和D的幀內(nèi)編碼模式分別是模式5、模式2、模式3和模式3時，即M[0]、M[1]、M[2]和M[3]的值分別為5、2、3和3，當前塊E的空域最佳幀內(nèi)模式概率直方圖。可以看出，模式3的概率最大，模式2和模式5的概率次之，而其余模式的概率很小。將概率直方圖中幅值最大者作為空域最佳幀內(nèi)預測模式，記為P[0]。

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

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

3) 基于時域的模式預測

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

圖4 最優(yōu)匹配塊幀內(nèi)模式預測

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

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

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

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

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

針對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) 得到最終的候選模式

合并上述空域和時域最佳幀內(nèi)預測模式的結(jié)果，得到最終候選模式。

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

5 算法復雜度分析

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

表1 各算法復雜度比較

6 實驗結(jié)果

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

1) 采用 RDO；

2) 采用CABAC；

3) 采用hardama變換；

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

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

6) 編碼幀數(shù)：100；

7) GOP類型：IPPP格式；

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

9) 參考幀數(shù)：5；

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

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

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

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

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

表2 編碼時間的比較

表3 輸出碼率的比較

表4 輸出PSNR的比較

圖6 算法的率失真曲線

7 結(jié)束語

通過以上實驗和分析，可以得出以下結(jié)論，與JM98全搜索算法、Pan快速算法和基于空域的預測算法相比較，基于時空預測的快速幀內(nèi)預測模式選擇算法在保持較好的編碼圖像質(zhì)量的同時，平均編碼總耗時分別降低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] 蔣剛毅, 李世平, 葉錫恩等. 基于塊參考像素特征的快速幀內(nèi)預測模式選擇新算法[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] 賈克斌, 謝晶, 方晟. 一種基于自相關(guān)法的H.264/AVC高效幀內(nèi)預測算法[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] 蘇睿, 劉貴忠, 張彤宇等. 利用變換域信息快速實現(xiàn)H.264 幀內(nèi)預測編碼的新算法[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 幀內(nèi)預測模式判決算法及VLSI 實現(xiàn)體系[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幀內(nèi)預測模式快速選擇算法[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] 戴聲奎, 喻莉, 朱光喜等. 基于視頻時空相關(guān)性的幀內(nèi)預測模式抉擇[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.