基于時(shí)空預(yù)測(cè)的H.264快速幀內(nèi)預(yù)測(cè)模式選擇算法

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

（杭州電子科技大學(xué) 自動(dòng)化學(xué)院，浙江 杭州 310018）

1 引言

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

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

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

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

2 Pan算法的空域改進(jìn)

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

3 Pan算法的時(shí)域改進(jìn)

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

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

4 算法實(shí)現(xiàn)

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

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

1) 初始化

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

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

2) 基于空域的模式預(yù)測(cè)

通過相鄰已編碼塊預(yù)測(cè)當(dāng)前塊的幀內(nèi)模式。圖2給出了空域模式預(yù)測(cè)的當(dāng)前塊E及其相鄰已編碼塊A、B、C和D的示意圖，由式（1）可求得當(dāng)前塊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與當(dāng)前塊E的相關(guān)程度(值為0到1之間)，h(M[i])表示幀內(nèi)模式M[i]為當(dāng)前塊最佳預(yù)測(cè)模式的概率?？紤]到A和B與E直接相鄰，相關(guān)程度較大，而C和D與E是對(duì)角相鄰，其相關(guān)程度相對(duì)較小，假定有如下關(guān)系：a[2]+a[3]＞a[1]=a[0]＞a[2]=a[3]。實(shí)驗(yàn)中，a[0]、a[1]、a[2]和a[3]分別設(shè)為1、1、0.7和0.7。

圖2 基于空域的模式預(yù)測(cè)

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

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

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

3) 基于時(shí)域的模式預(yù)測(cè)

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

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

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

記 1R、 2R、 3R和 4R所包括的像素個(gè)數(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)總的像素?cái)?shù)為

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

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

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

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

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

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

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

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

第1種情況，當(dāng)C[k-1]中存在DC模式時(shí)，此時(shí)認(rèn)為DC模式概率很大，舍棄其他模式，最終只保留DC模式；

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

4) 得到最終的候選模式

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

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

5 算法復(fù)雜度分析

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

表1 各算法復(fù)雜度比較

6 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)采用的硬件環(huán)境：AMD Athlon(tm) 64 Processor 3200+ 2.0GHz ；512MB內(nèi)存；操作系統(tǒng)：Windows XP Professional Sevice Pack 2；軟件實(shí)現(xiàn)平臺(tái)：JM98校驗(yàn)?zāi)Ｐ汀?shí)驗(yàn)采用5個(gè)標(biāo)準(zhǔn)測(cè)試序列，包括3個(gè)QCIF序列(News、Foreman和Silent)和2個(gè)CIF序列(Mobile和Container)。實(shí)驗(yàn)參數(shù)設(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) 運(yùn)動(dòng)估計(jì)搜索半徑，QCIF：16像素；CIF：32像素；

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

10) 運(yùn)動(dòng)估計(jì)精度：1/4像素。

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

比特率減少百分?jǐn)?shù)采用式（4）計(jì)算。

平均信噪比（PSNR）減少百分?jǐn)?shù)采用式（5）計(jì)算。

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

表2 編碼時(shí)間的比較

表3 輸出碼率的比較

表4 輸出PSNR的比較

圖6 算法的率失真曲線

7 結(jié)束語

通過以上實(shí)驗(yàn)和分析，可以得出以下結(jié)論，與JM98全搜索算法、Pan快速算法和基于空域的預(yù)測(cè)算法相比較，基于時(shí)空預(yù)測(cè)的快速幀內(nèi)預(yù)測(cè)模式選擇算法在保持較好的編碼圖像質(zhì)量的同時(shí)，平均編碼總耗時(shí)分別降低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)預(yù)測(cè)模式選擇新算法[J]. 電子與信息學(xué)報(bào), 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)預(yù)測(cè)算法[J]. 電子學(xué)報(bào), 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] 蘇睿, 劉貴忠, 張彤宇等. 利用變換域信息快速實(shí)現(xiàn)H.264 幀內(nèi)預(yù)測(cè)編碼的新算法[J], 電子與信息學(xué)報(bào), 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]. 通信學(xué)報(bào),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] 黃凱, 秦興, 嚴(yán)曉浪等. 一種 H.264 幀內(nèi)預(yù)測(cè)模式判決算法及VLSI 實(shí)現(xiàn)體系[J]. 電子學(xué)報(bào), 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] 騰國(guó)偉, 王國(guó)中, 張兆揚(yáng)等. 一種基于自適應(yīng)閾值的H.264/AVC幀內(nèi)預(yù)測(cè)模式快速選擇算法[J]. 自動(dòng)化學(xué)報(bào), 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] 戴聲奎, 喻莉, 朱光喜等. 基于視頻時(shí)空相關(guān)性的幀內(nèi)預(yù)測(cè)模式抉擇[J]. 通信學(xué)報(bào), 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.