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

謝曉燕，王 歡

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

近年來(lái)，數(shù)字視頻技術(shù)迅速發(fā)展，而已頒布的視頻標(biāo)準(zhǔn)H.264/AVC 在面對(duì)高清晰率、高幀率、高壓縮率這些需求時(shí)，已經(jīng)無(wú)法提供最佳的壓縮效率［1］。因此在2010 年1 月，視頻編碼專家組ITU－T VCEG(Video Coding Experts Group)和運(yùn)動(dòng)圖像專家組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］。為了達(dá)到這個(gè)目標(biāo)，HEVC 必須采用更高復(fù)雜度的視頻編解碼算法，因此也引入了極高的計(jì)算復(fù)雜度［4］。

1 HEVC 預(yù)測(cè)編碼

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

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

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

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

表1 不同PU 尺寸的N 值

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2)再次篩選:由于相鄰的角度預(yù)測(cè)模式間的預(yù)測(cè)值很接近，為了更加精確地找到最小代價(jià)值所對(duì)應(yīng)的預(yù)測(cè)模式，本文繼續(xù)對(duì)存放在uiRdModeList 中前3 個(gè)最小代價(jià)值對(duì)應(yīng)的模式進(jìn)行篩選。篩選過程如下:假設(shè)uiRdModeList 的前3 個(gè)預(yù)測(cè)模式分別為A，B，C，對(duì)應(yīng)的代價(jià)值用CX表示，X 表示模式序號(hào)。分別對(duì)如下3 個(gè)組的模式進(jìn)行計(jì)算:(A－1，A，A+1)(B－1，B，B+1)(C－1，C，C+1)。比較每組3 個(gè)模式的代價(jià)值之和與其標(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 個(gè)代價(jià)值x1，x2，x3的標(biāo)準(zhǔn)差，μ 為它們的均值。

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

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

圖4 兩種算法比較

3 仿真與驗(yàn)證

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

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

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

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

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

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

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

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

為了更直觀地表示本文所提出的算法對(duì)HEVC 編碼器性能造成的影響。圖5、圖6 和圖7 分別對(duì)CLASS A(2 560×1 600)、CLASS B(1 920×1 080)和CLASS E(1 280×720)的RD 曲線進(jìn)行比較。橫坐標(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ù)測(cè)模式快速選擇算法充分利用了候選模式集中排列第一的預(yù)測(cè)模式與最優(yōu)預(yù)測(cè)模式之間的強(qiáng)相關(guān)性。通過對(duì)35 種預(yù)測(cè)模式進(jìn)行初次篩選和再次篩選，快速精確地找到成為最優(yōu)預(yù)測(cè)模式概率最大的候選模式，大大減少了進(jìn)入RDO 過程的模式數(shù)量，有效地降低了原有幀內(nèi)預(yù)測(cè)編碼算法的計(jì)算復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，新的算法在犧牲了0.78%的碼率與0.12 dB 的信噪比的同時(shí)，節(jié)省了41.8%的編碼時(shí)間，提高編碼效率，為將來(lái)多視點(diǎn)、高效率視頻編碼的研究及應(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é)報(bào)，2014，19(3):6－10.

［4］齊美彬，朱廣輝. 利用紋理和空間相關(guān)性的HEVC 幀內(nèi)預(yù)測(cè)模式選擇［J］.中國(guó)圖象圖形學(xué)報(bào)，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ù)測(cè)快速模式選擇算法研究［D］.上海:上海交通大學(xué)，2012.

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