基于零系數(shù)塊和快速MPPM的AVS幀內預測算法

張永強，王雙龍

(河北工程大學信息與電氣工程學院，河北邯鄲056038)

AVS是國內第一個針對音視頻產業(yè)需求而制定的標準，全稱為《信息技術先進音視頻編碼》［1］。相比于MPEG－2標準，AVS編碼效率提高了2～3倍，在編碼高清視頻信號時，獲得與先進視頻編碼標準AVC/H.264主要檔次(MP)相當?shù)木幋a效率，但解碼器的實現(xiàn)復雜度只有60%～70%，實現(xiàn)了算法復雜度和編碼效率的折中。

AVS采用基于時間和空間的預測編碼、變換編碼和熵編碼的混合編碼結構。關于預測編碼中的幀內預測編碼部分，相比H.264幀內編碼，AVS幀內預測不但流程簡潔，實現(xiàn)復雜度低，而且采用的預測模式更少。但其參考軟件在PC平臺廣播檔次下，編碼I幀平均要用1.5 s，編碼P幀要3.5 s，編碼B幀所用時間更多，這樣很難在DSP上實現(xiàn)，而幀內編碼效率存在很大的提升空間。通過分析AVS幀內預測編碼的工作原理及流程，改進幀內預測編碼，提出一種結合零系數(shù)塊和快速MPPM的優(yōu)化算法來提高幀內編碼效率。經實驗驗證，在PSNR降低較小的情況下，改進后的算法明顯提高了編碼效率。

1 零系數(shù)塊的提出及閾值判定

1.1 零系數(shù)塊的提出

AVS幀內編碼以宏塊為單元，在4∶2∶0格式下，宏塊包括4個8×8亮度子塊和2個色度子塊，其中子塊的分隔及序號如圖1所示，0～3為亮度子塊，4～5為色度子塊，編碼的比特流中若包含語法元素cbp，表示當前宏塊中序號從0～5的4個8×8亮度塊和2個色度塊是否包含非零變換系數(shù)，cbp的第n位為0表明序號為n的8×8子塊中沒有非零系數(shù)，即該8×8子塊中的任一像素值都為0，這樣的子塊稱為零系數(shù)塊［2］。

圖1 4∶2∶0下AVS宏塊分隔子塊

在AVS參考軟件GDM2.1中，元素cbp的編碼是在幀內預測編碼的最后階段進行的，前面進行了一系列復雜操作，如利用率失真代價值選取當前宏塊最優(yōu)預測模式(Best Prediction Mode，BPM)，這部分操作極大地降低了系統(tǒng)效率(在后文詳細闡述)。很明顯，如果當前塊是零系數(shù)塊，把當前塊cbp元素的編碼放在幀內編碼的最后是不合適的，基于此，通過推導出子塊為零系數(shù)塊的充分條件，提前判定當前塊是否為零系數(shù)塊，進而決定是直接編碼宏塊cbp元素還是進行后續(xù)編碼操作。

1.2 零系數(shù)塊閾值推導

AVS為減少相鄰像素間空間相關性，采用8×8預縮放整數(shù)變換(Pre－scaled Integer Cosine Transform，ICT)，該變換源于離散余弦變換，是定點余弦變換的擴展，旨在保持相當壓縮性能的同時降低計算復雜度以及避免離散余弦變換(Discrete Cosine Transform，DCT)導致的編解碼失配問題。AVS中整數(shù)變換過程為

式中:A為AVS變換矩陣;X為待變換矩陣，在幀內編碼中即為當前8×8子塊實際值與預測值之差，以下簡稱殘差。如圖2所示，殘差數(shù)據(jù)經過ICT變換、尺度變換、量化，得到量化后的變換系數(shù)，量化后的變換系數(shù)經過反量化、ICT逆變換，得到重建數(shù)據(jù)。參考軟件中尺度變換過程與量化過程是一體的，見圖2中的虛線部分。

圖2 AVS變換量化及數(shù)據(jù)重建

參考軟件中，殘差數(shù)據(jù)Xij經過ICT變換及尺度縮放為

式中:Aui，Ajv為變換矩陣A中的元素。殘差變換系數(shù)X量化過程如下

式中:Fq為殘差X變換、量化后的結果;ScaleM是一個以位置參數(shù)i，j為索引的二維數(shù)組表，值可由式(5)獲得;qp_cost為幀內或幀間編碼常數(shù)，對于幀內編碼等于(1＜＜15)×10/31，對于幀間編碼等于(1＜＜15)×10/62。將式(2)代入式(3)，得到

為方便式子的推導，對式(6)中部分表達式做如下簡化

式中:Bmax=43 969;C1=，由絕對值不等式的性質對式(8)作進一步推導，即

由函數(shù)極限可知，當表達式B、D取最大值時，如果Fq小于1，即量化的變換系數(shù)為0，此時得到的SAD閾值可以作為判定零系數(shù)塊的充分條件。將表達式C1，Bmax，Dmax代入式(6)，得到判定當前子塊是零系數(shù)塊的SAD閾值，即

式中:Q_TAB是一個以量化步長QP為索引的一維常數(shù)數(shù)組表，其值隨QP增大而遞減，例如當QP為24時，Q_TAB=4 467，Th=27。閾值Th只與量化步長QP有關，在程序算法的設計中，將其做成一個以量化步長QP為索引的一維常量閾值數(shù)組表，判定零系數(shù)塊時只需查表即可查到閾值，降低系統(tǒng)開銷。

2 快速幀內預測算法

2.1 AVS 幀內預測

AVS幀內預測編碼基本思路同H.264，但在保證編碼質量相當?shù)那疤嵯?，AVS采用預測模式更少，幀內編碼以8×8子塊為基本單元，亮度預測有5種預測模式，色度預測有4種。下面介紹幀內預測都以亮度子塊預測模式為例假以說明，色度子塊幀內預測與亮度子塊類似，亮度預測模式如表1所示。

表1 AVS幀內預測編碼模式

由文獻［3］知，AVS通過計算率失真代價值(Rate Distortion Optimization，RDO)選擇幀內最優(yōu)預測模式BPM能保證幀內編碼的效率與質量。在AVS標準中，計算幀內預測編碼模式時，采用全搜索算法遍歷計算比較率失真代價函數(shù)值，全搜索算法流程如下:

1)判斷是否使能率失真代價函數(shù)，若沒有使能則直接跳到3)。

2)計算當前8×8子塊殘差數(shù)據(jù)，當前模式下的率失真代價值RDCost，若其值小于min_cost，把當前模式的率失真代價值賦給min_cost。

3)若沒有使能率失真代價函數(shù)，則計算在當前模式下8×8子塊的殘差數(shù)據(jù)，經Hadamard變換，若其值小于min_cost，則把當前模式的代價值賦給min_cost。

4)重復1)、2)或3)步驟，遍歷其他的幀內預測模式，選取min_cost對應的預測模式為當前塊最佳預測模式。

率失真代價值計算函數(shù)為

式中:Sij為實際像素值;Qij為重建像素值;i，j為子塊中像素所在的相對行、列序號(0≤i，j≤7);SSD(Sum of Squared Difference)為當前8×8子塊在某種預測模式下實際值與重建值之差的平方和，微觀上反映幀內預測的準確度;Rate為編碼比特流數(shù)，包括編碼最佳預測模式、當前子塊的位置參數(shù)、類型以及亮度系數(shù)所用的比特數(shù);λ為拉格朗日因子，可從式(14)得到。

2.2 快速算法的提出

由AVS中幀內預測的流程可知，全搜索算法花費不少時間，計算編碼比特數(shù)(Rate)過程中涉及到變換、量化、反量化、反變換的重建操作以及浮點數(shù)操作等。由文獻［4－7］可知目前關于降低最佳幀內預測模式計算復雜度的研究可分為兩個方向，一是減少遍歷預測模式次數(shù);二是簡化求率失真代價值RDcost的操作。權衡之下，本文偏向第一種，優(yōu)化計算搜索幀內預測模式的過程，提出快速MPPM(Most Possible Prediction Mode)算法，也就是快速篩選出最佳幀內預測模式MPPM，算法基于當前子塊紋理方向，通過快速簡易篩選減少幀內預測候選模式，進而快速確定最優(yōu)候選模式，提高AVS的編碼效率。

快速MPPM算法闡述如下:定義各紋理方向的SAD分別為垂直方向SADV、水平方向SADH、135°方向SADDL和45°方向SADDR，8×8子塊及其各預測方向如圖3所示，其中Sij為子塊像素值。分別計算當前8×8子塊的水平、垂直、垂直向左、垂直向右4個方向殘差值的加權絕對值之和，為減少計算量，本文求取SAD值時只取其部分，在不影響編碼質量的前提下降低復雜度，各方向預測模式的SAD值求取范圍如圖4所示，水平和垂直方向取奇數(shù)行(列)的SAD值，垂直向左和垂直向右取對角線各向其兩側水平位置平移兩像素值，具體定義的各SAD值求取方法見式(15)～式(18)，其中Pij為某種預測模式下的像素值，i，j及Sij同式(11)。

圖3 AVS 8×8子塊及各預測方向

圖4 幀內預測方向及SAD值范圍

取MPPM集合α，DC模式固定為MPPM集合固定元素之一，初始化將DC預測模式加入集合，即α={ModeDC}。如式(15)～式(18)所示方法，計算各個方向下的SAD并作比較，將計算得到的兩種最佳預測模式M1和M2加入集合α中;通過對多個測試序列的實驗統(tǒng)計可知，若兩種預測模式的SAD值相差多于1.48倍，則可把兩者中較大者對應的預測模式篩除，即MPPM集合中余下較小者對應的預測模式和DC預測模式;最后計算MPPM集合中余下模式對應的率失真代價值，選擇值最小的所對應的模式為當前子塊的最佳預測模式，并編入比特流。

通過上面算法，剔除了至少兩種預測模式，理論上排除了40%以上的不可能的預測模式，改進后的算法不但能快速篩選出當前子塊的預測模式，而且可以很大程度上提高幀內編碼效率。

2.3 快速算法流程

提出的快速算法結合上面提出的零系數(shù)塊和快速MPPM兩部分，具體算法流程如下:

1)以當前片(宏塊)的量化步長QP為索引，查找前面設計的閾值表得到判定當前8×8子塊為零系數(shù)塊的閾值Th，計算當前8×8子塊的殘差SAD值，若SAD＜Th，即SAD在閾值之內，則直接編碼當前8×8子塊cbp元素，跳過下面的步驟，否則進行下面操作。

2)計算當前8×8子塊SADV，SADH，SADDL和SADDR值，挑選其中SAD值較小的兩個相應的預測模式，設為M1 和M2，則 MPPM 集合 α ={ModeDC，ModeM1，ModeM2}，并做進一步篩選，若SADM1/SADM2＞1.48，則把預測模式M1從MPPM集合中剔除，即α ={ModeDC，ModeM2}。

3)計算MPPM集合中余下模式的率失真代價函數(shù)值，選取其中值最小的相應的預測模式為當前子塊最佳預測模式BPM=MPPMmax。

4)遍歷當前宏塊余下的8×8子塊，重復1)～3)步驟，計算它們的最佳預測模式，并編入視頻比特流。

3 測試結果

為驗證本文提出的算法，選取種不同的CIF測試序列，分別比較采用本改進算法前后AVS的編碼效率。測試條件如下:

GDM2.1參考軟件，測試機Pentium4200，2 Gbyte內存，Enable Hadamard，Enable RD optimization，Off Rate Control，Enable FME，30 Frames，F(xiàn)rame Style IPPP，GoP=8。分別選取量化步長QP=20，24，28，32，36，Bitrate=768 000 bit/s，相應測試序列的PSNR，Time，Bitrate如表2所示。

表2列出了用本算法前后的不同序列的測試結果，可以看出平均PSNR下降控制在1%之內，平均比特數(shù)增加控制在2%，平均編碼時間減少了31%以上。算法改進前后各測試序列在不同QP下平均編碼時間如圖5所示，從圖可以看出改進后的算法大幅度提高了編碼效率。

表2 本算法的測試結果

圖5 改進算法前后編碼效率

4 結語

本文提出了AVS幀內預測編碼的改進算法，將零系數(shù)塊和快速MPPM算法結合一起，把零系數(shù)的判定閾值做成數(shù)組表格，并且簡化求各預測模式的SAD方法。改進后的快速AVS幀內預測算法，使幀內預測編碼流程簡化，算法復雜度下降，與AVS全搜索算法相比，在編碼質量和碼率變化極小情況下，平均編碼時間減少31%以上，大大提高了編碼效率。

［1］數(shù)字音視頻編解碼技術標準工作組.AVS技術創(chuàng)新報告(2002—2010)［M］.北京:人民郵電出版社，2011.

［2］ LEE Y，LIN Y.Zero－block mode decision algorithm for H.264/AVC［J］.IEEE Trans.Image Process，2009，18(3):524－533.

［3］ GB/T20090.2—2006，信息技術先進音視頻編碼第 2部分:視頻［S］.2011.

［4］ KIM D，LEE Y.A fast intra prediction mode decision using DCT and quantization for H.264/AVC［J］.Signal Processing:Image Communication，2011(26):455－465.

［5］ KIM C，SHIH H，KUOC.Fast H.264 Intra－predictionmode selection using joint spatial and transform domain features［J］.J.Vis.Commun.Image R.，2006(17):291－310.

［6］劉代如，宋昊，李曉，等.H.264中的一種快速幀內預測判決算法［J］.電視技術，2007，31(4):10－11.

［7］靳梔艷，高志勇，張小云，等.H.264 High Profile的幀內預測模式快速判決算法研究［J］.電視技術，2012，36(21):8－11.