基于蘭氏距離的H.264/AVC幀內快速算法*

霍利嶺，張有會，王志巍，楊會云，趙 金

（河北師范大學 數學與信息科學學院，河北 石家莊 050016）

1 引言

基于空域的幀內預測是H.264/AVC[1]的重要組成部分。H.264/AVC采用全搜索算法進行幀內預測，使幀內預測具有很高的計算復雜度。因此，人們提出了很多快速算法。F.Pan等提出基于邊緣方向直方圖的幀內模式快速選擇算法[2]；Kim等通過計算4×4塊的SAD和SATD值，根據兩者直方圖的混合特征減少候選模式的個數[3]；Jong-ho Kim等利用幀間信息來進行幀內模式的快速選擇[4]。國內也有大量文獻進行了相關研究[5-7]。筆者利用宏塊內部相鄰像素值的差異判定宏塊的類型，進行Intra_4×4和 Intra_16×16的快速選擇。 對于 Intra_4×4模式，根據4×4塊的紋理方向排除不必要的候選模式。

2 H.264/AVC的幀內預測算法

H.264/AVC的幀內預測充分利用圖像的空間相關性，用當前塊的左邊和上邊像素值進行預測（如圖1所示）。編碼時，只對宏塊實際值和預測值的差值進行編碼，從而減少編碼的碼率。H.264/AVC標準算法有3類幀內預測方式：4×4 亮度塊預測（Intra_4×4）、16×16 亮度塊預測（Intra_16×16）、8×8 色度塊預測（Intra_chroma）。其中，Intra_4×4 有 9種預測模式，包括8種方向性預測和1種均值預測（如圖2所示）。Intra_16×16有4種預測模式 （如圖3所示）。Intra_chroma預測方式與Intra_16×16相似，有4種預測模式[1]。

圖1 宏塊預測

圖2 Intra_4×4預測方向

圖3 Intra_16×16幀內預測模式

JVT提供的參考模型中，色度塊的預測方式較為簡單，亮度塊的預測方式較為復雜。因此這里只討論亮度塊預測方式的快速算法。

3 H.264/AVC幀內快速選擇算法

3.1 宏塊類型的判定

宏塊可以分為平坦宏塊和非平坦宏塊。Intra_16×16模式適用于平坦宏塊，而Intra_4×4模式適用于非平坦宏塊。如果可以提前判斷出宏塊的類型，就可以提前從Intra_4×4和Intra_16×16中選擇一種模式，排除不必要的模式。

通過分析可知，平坦宏塊內部相鄰像素間的灰度值變化不大，即宏塊在水平和垂直方向相鄰像素值的差異較小。因此，可以利用宏塊在水平和垂直方向的相鄰像素值差異來判定宏塊的平坦性。

設Ghor，Gver分別表示水平和垂直方向相鄰像素值的差異，表示如下

其中，f（x，y）為在（x，y）處的像素值。

令G=Ghor+Gver，既考慮了宏塊在水平方向的像素值的差異，又考慮了在垂直方向像素值的差異，因此G的大小可以在一定程度上反映宏塊的平坦性。

如圖4所示，宏塊1、宏塊2、宏塊3為Foreman序列第0幀中的3個平坦程度不同的宏塊。相應的差異值如表1所示。

圖4 Foreman序列的第0幀

表1 不同宏塊的相應差異值

由表1可知，G的值越小宏塊越平坦。因此，可以設定閾值T，如果G＜T，則表明當前宏塊比較平坦，只進行Intra_16×16幀內預測；否則表明當前宏塊紋理復雜，只進行Intra_4×4幀內預測。

3.2 基于蘭氏距離的Intra_4×4模式快速選擇算法

蘭氏距離（也稱Canberra距離）是由Lance和Williams最早提出的[8]，它是聚類分析中一種度量距離的常用方法。X1和X2的蘭氏距離計算公式如下

式中：d（X1，X2）越小表示 X1和 X2的接近程度越大，d（X1，X2）越大表示X1和X2接近程度越小。

本文以蘭氏距離為度量，提取4×4塊的紋理方向，主要思想如下： 計算 4×4 塊在 0°，45°，90°和 135°這 4 個主要方向的蘭氏距離和，然后比較大小，找出最小值。由于蘭氏距離和越小，表示該方向上的像素值變化越小，因此蘭氏距離和的最小值對應的方向即為當前4×4塊的紋理方向。

為了得到更準確的紋理方向，獲取當前4×4子塊的像素值以及上邊一行和左邊一列的像素值，組成1個5×5的圖像塊 X。計算 X 在 0°，45°，90°和 135°這 4 個方向的蘭氏距離 Dθ（θ=0°，45°，90°，135°），每行相鄰像素間的蘭氏距離之和D0的公式如下

式中：f（x，y）為 X 在（x，y）處像素值。 同理可定義 D90為

D45的計算方法如圖5所示，圖中的箭頭方向為差分方向。D135的計算公式與D45類似。

D0，D45，D90，D135中的最小值對應的方向為當前4×4子塊的紋理方向。將與此紋理方向對應的預測模式（mode）加入到預測范圍。考慮到預測模式的相關性以及DC模式的特殊性，將與mode相鄰的2個模式mode1，mode2和DC模式也加入預測范圍，使Intra_4×4的預測模式由9個減少為4個，從而加快編碼速度。

圖5 D45的差分方向

4 幀內模式快速選擇算法描述

算法首先計算宏塊相鄰像素值的差異G，結合給定的閾值T判定宏塊的類型，進行Intra_4×4和Intra_16×16模式的快速選擇。其中，T的取值對編碼的性能影響很大，實驗結果表明，T取值為600時獲得的編碼效果最好。而對于Intra_4×4模式，采用基于蘭氏距離的Intra_4×4模式快速選擇算法。

具體實現步驟如下：

1）獲取宏塊的亮度數據，并設定閾值T。

2）計算當前宏塊內部相鄰像素值的差異G。

3）若 G＜T，轉到 4），只進行 Intra_16×16 模式選擇，否則，轉到5），只進行Intra_4×4模式選擇。

4）采用H.264/AVC標準算法進行Intra_16×16模式選擇，宏塊預測結束。

5）采用基于蘭氏距離的Intra_4×4快速選擇算法，具體過程如下：（1）獲得當前4×4塊的數據以及其上邊行和左邊列的數據，組成一個5×5圖像塊X；（2）計算X在 0°，45°，90°，135°這 4 個方向的蘭氏距離 D0，D45，D90，D135；（3）選取 D0，D45，D90，D135中的最小值對應的模式mode以及與其相鄰的2個模式mode1，mode2和DC模式加入到預測范圍，則Intra_4×4的預測范圍為（mode，mode1，mode2，DC）；（4）計算預測范圍內4個模式的RD_Cost值，選取具有最小RD_Cost值的模式作為Intra_4×4的最佳模式；（5）重復（1）～（4）直到預測完宏塊內所有 4×4 子塊，宏塊預測結束。

6）循環1）～5），直到預測完所有宏塊，算法結束。

5 實驗結果及分析

為了驗證算法的性能，在H.264參考模型JM13.2上對快速算法進行了仿真實驗。編碼配置為：幀率30 f/s（幀/秒）； 全I幀序列； 編碼幀數為100幀；QP=28；RDO開；CAVLC 開。 硬件配置為：AMD Athlon 64 X2 3600＋；主頻 2.0 GHz；內存 1.0 Gbyte。

表2列出了新算法與全搜索算法針對10個QCIF標準視頻序列的的結果比較。

表2 新快速算法與全搜索算法對比結果

表2中，Rt表示編碼時間變化的百分比，ΔPSNR表示峰值信噪比的變化，Rbit表示比特率變化幅度的百分比，由表2可知，本文算法與全搜索算法相比，各指標變化的平均值為：速度提高51.53%；PSNR降低0.06 dB；碼率提高1.98%。

圖6給出了Foreman序列的RD曲線。由圖可知，本文算法的RD曲線與JM13.2全搜索算法的RD曲線基本重合。這表明本文算法在編碼時間明顯降低的同時，圖像質量和碼率的變化很小，從而驗證了本文算法的有效性。

圖6 Foreman序列的RD曲線

6 結論

本文首先利用宏塊相鄰像素值的差異結合預先給定的閾值判定宏塊的類型，進行Intra_16×16和Intra_4×4快速選擇。對于Intra_4×4模式，利用蘭氏距離提取圖像的紋理方向，根據得到的紋理方向排除可能性小的模式，進而進行Intra_4×4模式的快速選擇。實驗結果表明，本文算法在PSNR和碼率變化很小的情況下，極大地提高了編碼速度。

[1]ISO/IEC 14496-10，Information technology coding of audio visual objects，Part 10[S].2004.

[2]PAN F，LIN X，RAHARDJA S，et al.A directional field based fast intra mode decision algorithm for H.264 video coding[EB/OL].[2009-09-10].http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1394420.

[3]KIM C，SHIH H H，KUO C J.Feature-based intra prediction mode decision for H.264[C]//Proc.2004 IEEE International Conference on Image Processing（ICIP）.[S.l.]：IEEE Press， 2004：769-772.

[4]KIM Jong-ho，KIM Byung-gyu.Fast block mode decision algorithm in H.264/AVC video coding[J].Journal of Visual Communication and Image Representation，2008，19（3）：175-183.

[5]劉代如，宋昊，李曉輝，等.H.264中一種快速幀內預測判決算法[J].電視技術，2007，31（4）：10-11.

[6]王日霞，朱偉興，陳先勇.H.264基于宏塊自適應的快速模式選擇算法[J].電視技術，2009，33（2）：14-17.

[7]王海勇，孫雁飛，吳啟宗.H.264編碼中幀內預測算法研究[J].電視技術，2009，33（8）：11－12.

[8]朱玉全，楊鶴標，孫蕾.數據挖掘技術[M].南京:東南大學出版社，2006.