基于宏塊預判的快速幀內預測模式選擇算法①

王 林, 贠境孺

(西安理工大學 自動化與信息工程學院,西安 710048)

H.264/AVC[1]是國際電信聯盟ITU-T的視頻編碼專家組VCEG和國際標準化組織ISO/IEC的運動圖像專家組MPEG聯合制定的新一代視頻編碼標準. 為了提高編碼效率,H.264采用了許多新的編碼技術,其中幀內預測編碼是消除空間冗余的關鍵技術. 幀內預測編碼中引入率失真優化(Rate Distortion Optimization,RDO)[1]技術求最優預測模式,有效地降低了空間冗余,但為了得到一個最優幀內預測模式需要計算592種[2]組合模式的代價函數,大幅度增加了編碼時間和計算復雜度. 因此,研究一種快速幀內預測模式選擇算法替代原有復雜算法成為研究的重點方向. 針對幀內預測模式選擇算法計算復雜度降低問題,國內外學者主要進行了兩方面的研究：一是通過簡化代價函數; 二是通過減少候選模式數量. Pan等人[3]最早用Sobel算子對當前待編碼塊每個點進行邊緣矢量強度計算,根據邊緣方向直方圖的特點,確定候選模式,降低了的編碼時間,但該算法需要對當前塊中所有像素點的邊緣方向矢量進行計算,計算復雜度仍然很高. Manuel等人[4]為了減少梯度計算數量使用Roberts算子代替Pan算法中的Sobel算子,編碼時間比Pan算法平均減少了22.32%,但Roberts算子對斜向邊緣提取效果較差,容易忽略少量邊緣信息. Tsai等人[5]運用像素梯度檢測預測方向的邊緣強度提出了一個模式過濾算法,取得編碼性能和計算復雜度之間的平衡. Joohyeok Kim等人[6]提出了一種基于絕對誤差和(SATD)的快速幀內預測模式選擇算法,實驗結果表明在碼率和峰值信噪比允許范圍內減少了大約70%編碼時間. Wang等人[7]計算幀內預測模式中四個主要預測方向(水平、垂直、45°和135°)的梯度強度,然后選擇最小的梯度強度及鄰近的預測模式,獲得最佳預測模式. 楊軍等人[8]提出了一種基于MAD值的自適應閾值快速幀內預測算法,先對宏塊周圍像素使用絕對誤差(MAD)進行預判,雖然該算法編碼效率不是很高,但與其它幀內預測模式選擇快速算法結合使用可以取得較好效果. 宋云等人[9]提出一種基于方向梯度的幀內預測模式選擇算法,使用參考像素與當前塊之間的方向梯度檢測出預測方向與邊緣強度,優先篩選部分方向梯度較大的預測模式,實驗結果減少了50%的編碼時間,碼率上升1.477%. 王欣欣等人[10]針對Pan算法中存在的缺陷加以改進,并與中心8×8塊邊界信息判定算法相結合,最大編碼時間減少最大超過40%,但中心8×8塊邊界信息采用的像素過多,存在計算誤差. Kau等人[11,12]針對Sobel算子存在像素使用多問題,提出一種新的邊緣檢測算子三點梯度算子,邊緣檢測率比Sobel算子高很多. Bhimani等人[13,14]針對預測應用程序視頻運行需要高性能并行計算提出了FIM方法,采用兩種模型馬爾科夫模型和機器學習模型來提高迭代計算時間和多級的數據處理,為大規模視頻處理減少更多的運行時間.

雖然上述研究對幀內預測模式選擇計算復雜度降低具有一定貢獻,但是研究的焦點一直圍繞如何提高某一宏塊的編碼效率,只是對當前編碼塊內進行方向與邊緣強度進行預測模式的篩選,通過改進算法篩選出最有可能的幾個預測模式,再進行率失真優化計算,得到最佳預測模式,沒有充分考慮到H.264幀內預測中Intra_4×4、Intra_16×16宏塊類型與QP量化參數之間的關系. 本文為了提高預判準確度提出了一種基于宏塊預判的快速幀內預測模式選擇組合算法,先根據MAD值[8]與QP結合定義閾值判斷宏塊的類型,然后采用三點梯度算子[11]使用較少的像素求梯度矢量,進而得到邊緣方向,最后通過邊緣方向與預測模式方向的關系對宏塊進行預測,篩選出最佳的預測模式.

1 相關理論與算法

1.1 H.264幀內預測編碼

H.264幀內預測編碼利用相鄰像素的相關性,通過當前宏塊的上邊和左邊相鄰的像素進行預測,對實際值和預測值的差值進行變換、量化、熵編碼,以消除空間冗余達到壓縮目的[1,3]. 編碼以宏塊單位,分為亮度塊預測和色度塊預測兩部分. 亮度塊預測包括9種4×4預測模式(4×4預測模式)和4種16×16塊的預測模式(16×16預測模式),色度塊預測包含4種8×8預測模式. 圖1(a)中的a～p的值可用相鄰塊的A～M來預測,其中,a～p表示當前需要預測的像素,A～M表示已編碼并進行重建的像素. 圖1(b)是Intra_4×4預測模式及方向示意圖,包括8種方向的預測模式和DC模式.對于亮度16×16塊和色度8×8塊僅支持垂直、水平、直流和平面模式. 圖2的4個子圖分別表示Intra_16×16四種預測模式.

圖1 4×4亮度預測

1.2 幀內預測模式選擇

H.264JM8.6[15]模型中對幀內預測模式選擇運用全搜索 (Full Search,FS)算法[1]. 采用率失真優化(Rate Distortion Optimization,RDO)策略進行最優化編碼模式選擇,通過遍歷所有可能的編碼模式,最后選擇最小率失真代價模式作為最佳幀內預測模式.

圖2 16×16亮度預測

其中SSD表示原始塊與重建塊的均方差值(Sum of Squared Differences,SSD);lmode=0.85×2(QP-12)/3表示拉格朗日算子(QP為量化參數);R表示熵編碼后的比特率. H.264在基本檔次下,以色度模式為外循環,依次掃描亮度的所有模式,每一個宏塊需要進行M8×(M4×16+M16)=592次RDO計算才能得到最優的預測模式,其中M8、M4、M16分別代表8×8塊、4×4塊和16×16塊的預測模式個數,可見獲得最優的幀內預測模式的計算量非常大[2].

2 幀內預測模式選擇組合算法

2.1 基于MAD值與QP結合的宏塊預判算法

H.264幀內預測標準中指出,Intra_16×16模式適用于平坦區域圖像編碼,Intra_4×4模式適用于有大量細節的圖像編碼[1]. 如果能提前判斷出宏塊編碼類型,就可以對預測宏塊只進行一種方式的搜索. 經過對6個不同30幀視頻序列在全搜素算法編碼下的測試,得到6個視頻序列采用不同編碼類型的匯總. 表1是6個視頻序列兩種類型中DC模式所占比例; 表2是幀內預測宏塊類型數量統計,可以看出Intra_4×4編碼類型平均占82.7%,Intra_16×16編碼類型平均占17.3%,所以提前判斷宏塊類型很有必要. 本算法主要是選取何種圖像特征來表示宏塊類型. 目前表征圖像宏塊平坦程度方法主要有計算交流系數AC與直流系數DC的比值[16]、圖像的信息熵[16]、二維直方圖[17]、相鄰像素差值[2]、MAD值[8]. 交流系數與直流系數的比值和信息熵在某些情況下不能準確表示圖像的平滑程度[16]; 直方圖統計圖像中各個像素灰度值出現的次數和頻率,計算比較復雜; 由于基于相鄰像素差值只考慮水平和垂直像素的差值存在一定誤差; 而MAD值計算只涉及到簡單的加法、絕對值和移位操作,計算復雜度上相對較小.

如果MAD值偏小,則圖像細節平坦; 如果MAD值偏大,則圖像細節豐富. 使用碼流分析工具H264Visa對全搜索算法編碼得到的碼流進行模式分析,圖3表示原始視頻第一幀,圖4表示運用JM8.6模型編碼后宏塊類型選擇(小方格表示采用Intra_4×4,大方格表示采用Intra_16×16),可以看出不同宏塊使用的是不同的編碼方式,小方格區域圖像細節豐富,大方格區域圖像細節較為平坦.

圖3 原始視頻序列第一幀

圖4 編碼后宏塊類型選擇

MAD值是指宏塊中每個像素值相對均值的離差絕對值的平均值,預測點像素與宏塊中所有像素的平均值的絕對值.

其中,p(x,y)是坐標為(x,y)處的像素值,Mean是此宏塊所有像素的平均值

表1 6個30幀視頻序列DC預測模式比例(單位：%)

表2 幀內預測宏塊類型數量統計

為解決宏塊預判不夠精確通過設置動態閾值T1、T2決定宏塊采用Intra_4×4亮度塊類型,還是采用Intra_16×16亮度塊類型,不在閾值范圍內的宏塊使用全搜索算法. 從表2可以看出QP值對宏塊類型有很大的影響. QP越小,編碼宏塊使用Intra_4×4類型越多.為了使預判更準確,動態閾值的設定與QP有關,隨QP值得變化而變化. 通過大量仿真實驗,得出QP下的動態閾值如式(4).

表3是QP=28時對預判宏塊的準確度統計,可以看出6個視頻序列在Intra_4×4、Intra_16×16的宏塊選擇中基本誤差很小,最高的誤判是Foreman視頻序列在Intra_16×16宏塊類型選擇時達到10.6%,序列的宏塊類型誤判符合誤差范圍,以上可以說明預判算法與QP值的結合是必要的. 表4是基于MAD值的宏塊預判算法與JM8.6全搜索算法的性能比較,可以看出碼率(Bit Rate)和峰值信噪比(PSNR)的變化都比較小,但是編碼時間平均下降了11.23%.

2.2 Pan算法

Pan算法[3]的基本思想是在H.264幀內預測編碼中,沿局部邊緣方向的像素具有相似的亮度值,并且大部分的預測模式都是基于方向性的模式,即得到某一方向對應的預測模式,證明該塊的方向具有該模式對應的方向. Pan利用Sobel算子提取邊緣方向信息,利用每個像素的邊緣方向直方圖來得到當前編碼塊方向的統計特性. 對于Intra_4×4亮度塊的8種方向性的預測模式,用二分法將預測方向圖劃分成8個幀內預測模式選擇區間,確定每個像素的邊緣方向矢量所處的預測區間,根據預測區間判斷預測模式.

表3 QP = 28時誤判宏塊統計(單位：%)

表4 基于MAD值的宏塊預判算法與全搜索算法的性能比較

2.2.1 建立邊緣方向圖

Pan算法[2,3]中利用Sobel算子獲得邊緣方向信息,Sobel算子是常用的邊緣檢測算子,有兩個分別反映垂直方向變化程度和反映水平方向變化程度的卷積核.原始視頻幀序列分別與Sobel算子的兩個卷積核卷積后,得到第i行第j列像素pi,j相應的邊緣矢量：

dxi,j和dyi,j分別表示垂直和水平的變化強度,定義如下：

邊緣矢量強度為：

邊緣矢量的方向：

2.2.2 建立預測模式直方圖

3 改進的Pan算法

Pan算法[3]利用邊緣方向直方圖篩選出可能性較小的候選模式,大大減少計算量,但在Pan算法中使用的Sobel算子使用周圍像素較多以及在任何情況下都將DC模式作為候選模式之一,從表1可以看出DC模式在不同編碼類型中作為候選模式的比例不同. 針對以上缺陷提出以下改進方法.

3.1 減少周圍像素計算

Pan算法利用Sobel算子求邊緣矢量,使用3×3卷積模板時使用周圍像素至少6個,計算量較大. 采用三點梯度算子[11],只使用4個相鄰像素中的3個像素得到預測像素的梯度矢量和邊緣方向. 圖5是像素x周圍的3個像素,也就是邊緣檢測時使用的像素. 三點梯度算子示意圖如圖6所示,其中待求像素為x和周圍像素a,b,c,虛線部分表示邊緣方向,實線表示梯度矢量.

圖5 邊緣檢測時使用像素

圖6 三點梯度算子示意圖

三點梯度算子：定義圖像幀f的梯度

對角像素差：

梯度矢量：

3.2 DC模式選擇

Pan算法在任何情況下都計算DC模式的率失真代價值,為了降低計算復雜度,設定DC模式的選擇依據,判斷是否采用DC模式[12].

DC模式的選擇依據：

判斷條件：

則將DC模式作為候選模式. 其中s24×4表示像素方差,即圖1中12個像素A-L的平均值與待求像素的方差.θ4×4表示設定的閾值,Qstep表示量化步長,而量化參數是量化步長的編號,可以通過查表得到.

3.3 基于宏塊預判快速幀內預測模式組合算法的具體描述

宏塊預判算法與改進Pan算法的組合算法步驟如下：

1) 編碼某I幀前,先獲得視頻序列的第一幀,利用公式(2)得到各個宏塊的MAD值;

2) 設置不同QP值,獲得多個視頻序列中各個宏塊的MAD值,通過仿真實驗得到公式(4)閾值,根據閾值來判斷新的編碼視頻序列宏塊類型. 如果能判斷出則不需要遍歷兩種編碼類型,否則使用全搜索算法來計算;

3) 通過公式(14)(15)DC模式的判斷依據,判斷DC模式是否作為候選模式之一,如果滿足條件DC模式可以作為候選模式;

4) 在1)、2)步預判算法的基礎上,采用改進Pan算法中三點梯度算子計算待求宏塊像素的梯度矢量,進而得到邊緣方向,根據邊緣方向得到預測模式,通過預測宏塊中具有相同的預測模式的像素點的個數求和來確定預測模式直方圖. 最后通過預測模式直方圖得到更小范圍的候選預測模式;

5) 在4)得到的候選預測模式與3)判斷DC模式兩者結合得到候選模式之后,再通過率失真優化 (RDO)來計算得編碼塊最優的預測模式.

4 實驗結果

為了驗證本文組合算法的有效性,將本文算法分別與JM8.6標準算法以及Pan算法,在編碼時間、輸出碼率和峰值信噪比3個方面進行比較. 實驗的硬件環境：CPU 2.6 GHz、內存4 GB、Windows7 64位操作系統; 軟件環境：VC++ 6.0,JM8.6模型; 參數設置：基本檔次(baseline)、全I幀編碼、6個不同運動特性的QCIF格式視頻測試序列(Bus,Claire,Foreman,Carphone,Suzie,News),在不同量化參數QP下對每個視頻序列取前30幀進行編碼.

(1) 評價指標

其中,峰值信噪比PSNR單位為dB,時間Time單位為s,碼率Bit rate單位為kbit/s.

(2) 實驗結果用3個部分表示

① 3種算法之間性能比較見表5、表6. 由表5和表6可見,組合算法比全搜索算法、Pan算法編碼時間下降很多,平均降低分別是72.4%、28.6%; 以碼率升高作為代價,比全搜索算法、Pan算法碼率分別升高4.21%、1.8%.

② 圖7、圖8分別是Claire和News序列在3種算法下的性能對比圖; 圖7、圖8的子圖(a)是率失真對比圖,(b)是編碼時間對比圖. 從圖7(a)、(b)及圖8(a)、(b) 可以看出Claire 、News視頻序列分別在3種算法編碼下得到的率失真對比,三者之間的誤差較小,可以忽略影; 而編碼時間的變化,組合算法明顯優于其他單個算法,大幅度降低.

表5 組合算法與全搜索算法的性能比較

表6 組合算法與Pan算法的性能比較

③ 圖9、圖10分別是Claire和News視頻序列在不同算法下解碼的主觀質量圖; 圖9、圖10的子圖(a)、(b)、(c)分別是JM8.6、Pan算法以及組合算法下的圖. 從圖9和圖10可以看出3種算法下的視頻幀主觀質量相差很小. 綜上編碼時間可以衡量算法的復雜度,在碼率稍高情況下,組合算法比單個算法有效,大幅度降低計算復雜度,減少編碼時間.

圖7 Claire視頻序列在三種不同算法下的性能對比圖

圖8 New視頻序列在三種不同算法下的性能對比圖

圖9 三種不同算法下Claire視頻幀對比圖

圖10 三種不同算法下的News視頻幀對比圖

5 結語

本文針對幀內預測模式選擇部分計算復雜度問題以及現有快速幀內預測模式選擇算法中Pan算法中Sobel算子存在的缺點,找到一種更有效的快速幀內預測模式組合算法. 提出了考慮QP變化的MAD宏塊預判算法與三點梯度算子相結合的幀內預測模式選擇算法,避免了遍歷所有模式. 通過實驗可以得到：在視頻幀主觀質量基本不變,碼率稍增高的情況下,可以大幅度降低計算復雜度,減少編碼時間.

1 畢厚杰,王健. 新一代視頻壓縮編碼標準——H.264/AVC.2版. 北京：人民郵電出版社,2009.

2王慧,常建平. 改進的H.264快速幀內預測模式選擇算法.計算機工程,2008,34(19)：228-229. [doi：10.3969/j.issn.1000-3428.2008.19.077]

3 Pan F,Lin X,Rahardja S,et al. Fast mode decision algorithm for intraprediction in H.264/AVC video coding. IEEE Transactions on Circuits and Systems for Video Technology,2005,15(7)：813-822. [doi：10.1109/TCSVT.2005.848356]

4 De-Frutos-López M,Orellana-Quirós D,Pujol-Alcolado JC,et al. An improved fast mode decision algorithm for intraprediction in H.264/AVC video coding. Signal Processing：Image Communication,2010,25(10)：709-716.[doi：10.1016/j.image.2010.10.005]

5 Tsai AC,Paul A,Wang JC,et al. Intensity gradient technique for efficient intra-prediction in H.264/AVC. IEEE Transactions on Circuits and Systems for Video Technology,2008,18(5)：694-698. [doi：10.1109/TCSVT.2008.919113]

6 Kim J,Jeong J. Fast intra mode decision algorithm using the sum of absolute transformed differences. Proceedings of 2011 International Conference on Digital Image Computing Techniques and Applications. Noosa,QLD,Australia. 2011.655-659.

7 Wang JC,Wang JF,Yang JF,et al. A fast mode decision algorithm and its VLSI design for H.264/AVC intraprediction. IEEE Transactions on Circuits and Systems for Video Technology,2007,17(10)：1414-1422. [doi：10.1109/TCSVT.2007.903786]

8 楊軍,龔聲蓉,劉純平. 自適應閾值的宏塊MAD快速幀內算法. 計算機工程與應用,2009,45(34)：189-191.

9 宋云,沈燕飛,龍際珍,等. 基于方向梯度的H.264幀內預測模式選擇算法. 計算機學報,2013,36(8)：1757-1764.

10 王欣欣,陸中成,程欣欣. H.264/AVC標準中幀內預測宏塊模式選擇的優化. 計算機工程與應用,2011,47(16)：182-184. [doi：10.3778/j.issn.1002-8331.2011.16.055]

11 Kau LJ,Chen CS. A low complexity dual mode edge detector. Proceedings of 2011 Visual Communications and Image Processing (VCIP). Tainan,China. 2011. 1-4.

12 Kau LJ,Leng JW. A gradient intensity-adapted algorithm for the fast decision of H.264/AVC intra-prediction modes.Proceedings of 2013 IEEE Workshop on Signal Processing Systems (SiPS). Taipei City,Taiwan,China. 2013. 272-277.

13 Bhimani J,Mi NF,Leeser M,et al. FiM：Performance prediction for parallel computation in iterative data processing applications. Proceedings of the 2017 IEEE 10th International Conference on Cloud Computing (CLOUD).Honolulu,HI,USA. 2017. 359-366.

14 Bhimani J,Leeser M,Mi NF. Accelerating K-means clustering with parallel implementations and GPU computing. Proceedings of 2015 IEEE High Performance Extreme Computing Conference (HPEC). Waltham,MA,USA. 2015. 1-6.

15 劉佳,董金明. 一種新的H.264/AVC快速幀內預測模式選擇判決算法. 電子與信息學報,2009,31(5)：1072-1076.

16 謝晶,賈克斌. 一種基于二維直方圖的H.264/AVC快速幀內預測判決算法. 電子與信息學報,2005,27(7)：1053-1057.

17 Joint Video Team. H.264/AVC Reference Software JM8.6.http：//iphome.hhi.de/suehring/tml/download/old_jm/jm8.6.zi p. 2004-09.