基于模式分組的幀內(nèi)預(yù)測模式快速選擇算法

謝曉燕，王 歡

(西安郵電大學(xué) 計算機學(xué)院，陜西 西安 710061)

近年來，數(shù)字視頻技術(shù)迅速發(fā)展，而已頒布的視頻標(biāo)準(zhǔn)H.264/AVC 在面對高清晰率、高幀率、高壓縮率這些需求時，已經(jīng)無法提供最佳的壓縮效率［1］。因此在2010 年1 月，視頻編碼專家組ITU－T VCEG(Video Coding Experts Group)和運動圖像專家組ISO/IEC MPEG(Moving Picture Experts Group)成立了JCT－VC(Joint Collaborative Team on Video Coding)聯(lián)合小組，制定了新一代高效率視頻編碼標(biāo)準(zhǔn)HEVC(High Efficiency Video Coding)［2］，其核心目的是在H.264/AVC 的基礎(chǔ)上，將壓縮效率提高一倍［3］。為了達到這個目標(biāo)，HEVC 必須采用更高復(fù)雜度的視頻編解碼算法，因此也引入了極高的計算復(fù)雜度［4］。

1 HEVC 預(yù)測編碼

HEVC 預(yù)測編碼包括幀內(nèi)預(yù)測編碼和幀間預(yù)測編碼。幀內(nèi)預(yù)測編碼消除了大量空域冗余，它是利用同一幀已編碼完成的像素點對即將編碼的像素點進行預(yù)測。HEVC 幀內(nèi)預(yù)測模式由原有的9 種增加到35 種，即DC 模式(模式0)，Planar平面模式(模式1)，和33 種角度預(yù)測模式(模式2 ～35)。33種角度預(yù)測方向與其對應(yīng)的預(yù)測模式編號分別如圖1 和圖2所示。

預(yù)測模式的增加大大提高了幀內(nèi)預(yù)測的準(zhǔn)確性，但同時也帶來了非常高的計算復(fù)雜度。HEVC 幀內(nèi)預(yù)測通過采用粗模式選擇(Rough Mode Decision，RMD)和最有可能預(yù)測模式(Most Probable Mode，MPM)相結(jié)合的方法來減少預(yù)測過程中所需的預(yù)測模式，從而降低計算復(fù)雜度。HEVC 幀內(nèi)預(yù)測編碼過程首先要進行RMD，遍歷35 種預(yù)測模式，對每一種預(yù)測模式進行代價函數(shù)的計算，篩選出N 個代價值較小的預(yù)測模式作為候選模式，候選模式N 的數(shù)目在文獻［5］中提出，如表1 所示。MPM 分別利用當(dāng)前編碼塊的左方預(yù)測塊與上方預(yù)測塊的最佳預(yù)測模式來預(yù)測當(dāng)前塊的MPM，同時判斷當(dāng)前塊的MPM 是否已經(jīng)包含在RMD 的候選模式集中，若沒有包含在內(nèi)，則將當(dāng)前塊的MPM 加入到候選模式集中一起進行高精度的率失真優(yōu)化(Rate Distortion Optimization，RDO)計算，最終選擇出最優(yōu)幀內(nèi)預(yù)測模式。

圖1 HEVC 幀內(nèi)預(yù)測的33 個方向

圖2 HEVC 幀內(nèi)預(yù)測模式編號

表1 不同PU 尺寸的N 值

在幀內(nèi)預(yù)測過程中，RMD 要對全部的預(yù)測模式進行代價函數(shù)計算，其運算量非常巨大。如果可以通過預(yù)先判斷，在進行代價函數(shù)計算之前減少預(yù)測模式的數(shù)量，就能夠有效地降低幀內(nèi)預(yù)測的計算復(fù)雜度。很多學(xué)者就此提出了一些優(yōu)化算法。文獻［6］提出跳過變換量化等步驟，通過預(yù)處理提前排除一些可能性極小的預(yù)測模式。文獻［7］提出了一種基于邊緣信息的快速算法，利用圖像處理中的索貝爾算子(Sobel operator)對4×4 的子塊進行邊緣檢測，然后通過邊緣方向的灰度直方圖來確定最后的預(yù)測模式。文獻［8］在文獻［7］的基礎(chǔ)上進行改進，提出一種基于顯著邊沿強度的快速模式選擇算法，采用了不同的邊緣檢測算子，結(jié)果說明比文獻［7］中的算法有了一定的提升。

文獻［9］提出了一種基于梯度的HEVC 幀內(nèi)預(yù)測快速模式選擇算法。主要利用Sobel 算子計算當(dāng)前PU 每個像素的梯度向量角。然后，在35 種預(yù)測模式里找到與梯度向量角最接近的角度對應(yīng)的預(yù)測模式;與此預(yù)測模式垂直的預(yù)測模式就是此像素的最優(yōu)預(yù)測模式。該算法在減少20%的編碼時間同時，平均增加1%的碼率。

文獻［10］在幀內(nèi)預(yù)測快速預(yù)處理階段定義了一種簡單的代價函數(shù)計算公式，并結(jié)合基于貝葉斯決策原理在幀內(nèi)預(yù)測模式選擇過程中訓(xùn)練的基于SATD(Hadamard transformed SAD)的率失真代價最佳閾值，最終將進行RMD 的35 種預(yù)測模式減少到9 種。這種低復(fù)雜度的幀內(nèi)預(yù)測算法減少了近一半的編碼時間，信噪比PSNR 減少了0.12 dB，但是這種方法與原編碼相比平均增加了2.4%的碼率。

在連續(xù)的視頻圖像中，相鄰幀之間的圖像紋理具有很強的相關(guān)性，根據(jù)這一特點文獻［11］提出利用Co－located PU 及相鄰PU 塊的預(yù)測模式進行預(yù)判，來減少RMD 過程的預(yù)測模式數(shù)量，使得RMD 選擇過程中預(yù)測模式數(shù)量減少到17 種，但是這種方法引起了碼率明顯的升高。

文獻［12］使用邊緣匹配檢測器對預(yù)測模式進行選擇，利用類似統(tǒng)計直方圖的核密度估計方法來提高邊緣匹配檢測器的準(zhǔn)確度，平均降低了36.7%的編碼時間，與原有的算法相比增加了1.65%的碼率。

文獻［13］利用變換域邊緣檢測來縮小預(yù)測模式的選擇范圍。根據(jù)不同尺寸的PU，采用不同的類別系數(shù)，計算選取的類別系數(shù)絕對值之和，根據(jù)和值選取對應(yīng)的權(quán)重對幀內(nèi)預(yù)測模式進行選擇。這樣，只對一部分的預(yù)測模式進行計算，然而，這種方法使碼率增加了2.8%。

以上幾種快速算法都是利用一些額外的編碼信息來減少計算復(fù)雜度。雖然算法的性能極其逼近標(biāo)準(zhǔn)算法，但是編碼時間減少的幅度并不大，并且碼率的增加也比較明顯，均在1%以上。本文在不引進額外編碼信息的基礎(chǔ)上對RMD 過程進行優(yōu)化，充分利用候選模式集中排列第一的預(yù)測模式與最優(yōu)預(yù)測模式之間的強相關(guān)性，提出一種基于模式分組的幀內(nèi)預(yù)測模式快速選擇算法。該算法有效地降低了HEVC 幀內(nèi)預(yù)測算法的計算復(fù)雜度，與HEVC 的測試模型HM10.0 相比，所提出的算法在基本不改變圖像的質(zhì)量下，編碼時間平均減少了41.8%，而碼率僅增加0.78%。

2 快速幀內(nèi)預(yù)測模式選擇算法

2.1 幀內(nèi)預(yù)測模式選擇可優(yōu)化處的分析

HEVC 的測試模型(HEVC Test Model)HM［14］是由JCTVC 編寫的一個標(biāo)準(zhǔn)代碼庫，可以對不同的測試場景進行仿真編碼。在HM 中，RMD 過程的候選列表和其對應(yīng)的代價值列表分別存放在uiRdModeList 和CandCostList 數(shù)組中。其中，CandCostList 按照代價值從小到大進行排列，uiRdModeList 存放的預(yù)測模式是按照其對應(yīng)的代價值的大小進行排序，即候選列表uiRdModeList 中第1 個候選模式的代價值最小，第2個次之。一般情況下，代價值小的預(yù)測模式所對應(yīng)的率失真代價值也低。因此，uiRdModeList 中排列第一的預(yù)測模式被選為最優(yōu)預(yù)測模式的概率最高。為此，本文對uiRdModeList排列前3 位預(yù)測模式分別被選為最優(yōu)預(yù)測模式的比例進行了統(tǒng)計，結(jié)果如圖3 所示，排列第一的預(yù)測模式作為最優(yōu)預(yù)測模式的比例為75.4%，第2 個模式和第3 模式平均比例分別為24.2%和0.04%。

圖3 候選模式被選為最優(yōu)預(yù)測模式所占的比例

為了使預(yù)測結(jié)果更加精確，HEVC 還將MPM 模式加入到uiRdModeList 中。接下來對最優(yōu)預(yù)測模式在MPM 中的PU 比例進行統(tǒng)計，實驗發(fā)現(xiàn)MPM 成為最優(yōu)預(yù)測模式的概率高達85.1%。實驗數(shù)據(jù)如表2 所示。

表2 MPM 選為最優(yōu)預(yù)測模式的比例

由于uiRdModeList 中排列第一的預(yù)測模式及MPM 被作為最優(yōu)預(yù)測模式的概率非常高，因此可以利用這一特性對算法進行優(yōu)化，減少不必要的率失真代價的計算，從而提高編碼效率。

2.2 基于模式分組的幀內(nèi)預(yù)測模式快速選擇算法

根據(jù)1.1 節(jié)的統(tǒng)計分析，得到MPM 以及uiRdModeList 中排列第一的預(yù)測模式被作為最優(yōu)預(yù)測模式的比例非常高。因此如何在35 種預(yù)測模式中快速精確地找到成為候選模式集中排列第一的預(yù)測模式對降低幀內(nèi)預(yù)測的計算復(fù)雜度至關(guān)重要。針對這一問題，本文提出了一種基于模式分組的快速模式選擇算法。具體算法流程如下:

1)初次篩選:選取編號從3 開始，且編號為3 的倍數(shù)的所有角度預(yù)測模式進入初始的RMD 篩選模式列表。由于平面模式0、DC 模式1、水平預(yù)測模式10 以及垂直預(yù)測模式26 的預(yù)測值的計算比較特殊，所以將這4 種模式添加到篩選模式列表中。初始的RMD 篩選模式列表集為{0，1，3，6，9，10，12，15，18，21，24，26，27，30，33}。然后計算篩選模式列表中各模式的代價值，按照代價值從小到大的順序?qū)?yīng)的模式加入到uiRdModeList 中。

2)再次篩選:由于相鄰的角度預(yù)測模式間的預(yù)測值很接近，為了更加精確地找到最小代價值所對應(yīng)的預(yù)測模式，本文繼續(xù)對存放在uiRdModeList 中前3 個最小代價值對應(yīng)的模式進行篩選。篩選過程如下:假設(shè)uiRdModeList 的前3 個預(yù)測模式分別為A，B，C，對應(yīng)的代價值用CX表示，X 表示模式序號。分別對如下3 個組的模式進行計算:(A－1，A，A+1)(B－1，B，B+1)(C－1，C，C+1)。比較每組3 個模式的代價值之和與其標(biāo)準(zhǔn)差的和的大小，記為gi;即比較g1=(CA－1+CA+CA+1+δ1)，g2=(CB－1+CB+CB+1+ δ2)，g3=(CC－1+CC+CC+1+δ3)的大小，即

其中:δj為每組3 個代價值x1，x2，x3的標(biāo)準(zhǔn)差，μ 為它們的均值。

3)找出g1，g2，g3的最小值，該最小值所對應(yīng)的組則包含可能的最優(yōu)預(yù)測方向。將該組的3 個模式再次進行代價值的計算，直到找出代價值最小的模式作為uiRdModeList 中第1個預(yù)測模式，并將MPM 添加到uiRdModeList 中作為第2 個預(yù)測模式一起進行RDO 計算，最終選擇出最優(yōu)的預(yù)測模式。算法流程如圖4 所示。

本文提出的快速算法首先對35 種預(yù)測模式進行初次篩選，選取15 個預(yù)測模式進入RMD 計算，這樣大大減少了代價函數(shù)的運算量;經(jīng)過再次篩選保證了每個預(yù)測模式都能被覆蓋到，確保了算法對所有預(yù)測模式的適用性。經(jīng)過這兩步篩選，最終快速精確的求出候選列表uiRdModeList 中排列第一的預(yù)測模式。

圖4 兩種算法比較

3 仿真與驗證

為了驗證文中所提算法的有效性，將優(yōu)化的算法集成到HEVC 的測試環(huán)境HM10.0 上。在全I 幀的結(jié)構(gòu)下，采用18個通用視頻標(biāo)準(zhǔn)序列進行實驗，量化參數(shù)QP 取值分別為22，27，32，37，分別測試10 幀。這里主要從所提算法節(jié)省的編碼時間以及付出的相應(yīng)代價—峰值信噪比與編碼碼率來考慮算法的性能，具體包括Δtime，Δbitrate 和ΔY_PSNR［15］。

1)Δtime 指本文所提出的方法與HM 的編碼時間之差的百分比，編碼器計算復(fù)雜度的度量采用編碼器平均執(zhí)行時間的減少量Δtime 表示，定義如下

2)Δbitrate 指本文所提出的方法與HM 的編碼碼率之差的百分比，定義如下

其中:bitrateproposed(QPi)表示文中方法的編碼碼率;bitrateHM(QPi)表示HM 編碼器得到的編碼碼率;編碼碼率越小說明視頻圖像的壓縮效率越好。

3)ΔY_PSNR 指本文所提出的方法與HM 的峰值信噪比的百分比，定義為

式中:Y_PSNRpro(QPi)表示文中方法的亮度峰值信噪比;Y_PSNRHM(QPi)表示HM 編碼器得到的亮度峰值信噪比。PSNR 表示視頻圖像的質(zhì)量，PSNR 越高，表明圖像的質(zhì)量越好。

由于本文的快速算法是略過部分編碼模式來達到降低計算復(fù)雜度的目的，所以從原理上講選擇出來的最終預(yù)測模式有可能不是最優(yōu)的，必然會導(dǎo)致編碼性能的降低——PSNR的下降或者輸出的碼率增大。但所提出的算法在明顯的降低編碼時間的同時只有極小碼率增加和很小的PSNR 下降。表3 的數(shù)據(jù)可以看出本文所提出的方法與HM－10.0 相比，編碼時間平均減少了41.8%，而Y_PSNR 降低了0.12 dB，bitrate僅增加了0.78%。對比文獻［9－13］，碼率的增加幅度平均在1%以上，本文所提的算法在大幅度降低編碼時間的同時，碼率僅控制在0.78%的增加。因此，本文的方法在保證視頻質(zhì)量基本不變的前提下，有效地降低了編碼時間，提高了編碼效率。

表3 節(jié)省的編碼時間與編碼質(zhì)量的對比

為了更直觀地表示本文所提出的算法對HEVC 編碼器性能造成的影響。圖5、圖6 和圖7 分別對CLASS A(2 560×1 600)、CLASS B(1 920×1 080)和CLASS E(1 280×720)的RD 曲線進行比較。橫坐標(biāo)表示輸出的碼率，縱坐標(biāo)表示亮度峰值信噪比。

圖5 Traffic(Class A)的RD 曲線

圖6 Kimomo(Class B)的RD 曲線

圖7 Vidyo3(Class E)的RD 曲線

從圖中可以看出，本文中的算法與HM－10.0 原有的算法RD 曲線幾乎重疊，表明本文算法與HEVC 算法相比，兩者編碼性能差異極小。由此證明了本文所提出的算法的有效性。

4 小結(jié)

基于模式分組的幀內(nèi)預(yù)測模式快速選擇算法充分利用了候選模式集中排列第一的預(yù)測模式與最優(yōu)預(yù)測模式之間的強相關(guān)性。通過對35 種預(yù)測模式進行初次篩選和再次篩選，快速精確地找到成為最優(yōu)預(yù)測模式概率最大的候選模式，大大減少了進入RDO 過程的模式數(shù)量，有效地降低了原有幀內(nèi)預(yù)測編碼算法的計算復(fù)雜度。實驗結(jié)果表明，新的算法在犧牲了0.78%的碼率與0.12 dB 的信噪比的同時，節(jié)省了41.8%的編碼時間，提高編碼效率，為將來多視點、高效率視頻編碼的研究及應(yīng)用打下基礎(chǔ)。

［1］KIM J，CHOE Y，KIM Y G.Fast coding unit size decision algorithm for intra coding in HEVC［C］//Proc.2013 IEEE Iternational Comference Consumer Electronics(ICCE).［S.l］:IEEE Press，2013:637－638.

［2］LAINEMA J，BOSSEN F，HAN W J，et al.Intra coding of the HEVC standard［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，22(12):1792－1801.

［3］田小平，田永召.面向交互應(yīng)用的HEVC 編碼性能分析［J］.西安郵電大學(xué)學(xué)報，2014，19(3):6－10.

［4］齊美彬，朱廣輝. 利用紋理和空間相關(guān)性的HEVC 幀內(nèi)預(yù)測模式選擇［J］.中國圖象圖形學(xué)報，2014，19(8):1119－1125.

［5］ZHAO L，ZHANG L，MA S W，et al.Fast mode decision algorithm for intra prediction in HEVC［C］//Proc. IEEE Visual Communications and Image Processing(VCIP).［S.l］:IEEE Press，2011:1－4.

［6］MIN J，LEE S，KIM I，et al.Unification of the directional intra prediction methods in TMuC:B100［R］.Geneva，Switzerland:JCT－VC，2011.

［7］PAN F，LIN X，RAHARDJA S，et al.Fast mode decision algorithm for intra－prediction in H.264/AVC video coding［J］.IEEE Trans.Circuits and Systems for Video Technology，2005，15(7):813－822.

［8］WANG Jiaching，WANG Jhingfa，YANG Jarferr，et al. A fast mode decision algorithm and its VLSI design for H.264/AVC intra－prediction［J］.IEEE Trans. Circuits and Systems for Video Technology，2007，17(10):1414－1422.

［9］JIANG W，MA H，CHEN Y.Gradient based fast mode decision algorithm for intra prediction in HEVC［C］//Proc.IEEE the 2nd International Conference on Consumer Electronics，Communications and Networks(CECNet).［S.l］:IEEE Press，2012:1836－1840.

［10］SUN H M，ZHOU D J，GOTO S.A low－complexity HEVC intra－prediction algorithm based on level and mode filtering［C］//Proc.IEEE International Conference on Multimedia and Expo(ICME).［S.l］:IEEE Press，2012:1085－1090.

［11］MOTRAC A S，GUPTA A，SHUKLA M.Fast intra mode decision for HEVC video encoder［C］//Proc. IEEE the 20th International Conference on Software，Telecommunications and Computer Networks(SoftCOM).［S.l］:IEEE Press，2012:1－5.

［12］CHEN G，LIU Z Y，AKESHI I.Fast HEVC intra mode decision using matching edge detector and kernel density estimation alike histogram generation［C］//Proc. IEEE International Symposium on Circuits and Systems(ISCAS).［S.l］:IEEE Press，2013:53－56.

［13］TING Y C，CHANG T S，SHUKLA M.Fast intra prediction algorithm with transform domain edge detection for HEVC［C］//Proc.IEEE Asia Pacific Conference on Circuits and Systems(APCCAS).［S.l］:IEEE Press，2012:144－147.

［14］嚴(yán)順卿.HEVC 幀內(nèi)預(yù)測快速模式選擇算法研究［D］.上海:上海交通大學(xué)，2012.

［15］蔣潔，郭寶龍.利用平滑區(qū)域檢測的HEVC 幀內(nèi)編碼快速算法［J］.西安電子科技大學(xué)學(xué)報:自然科學(xué)版，2013，19(3):194－200.