Ｈ．２６４／ＡＶＣ幀內預測模式選擇的快速算法

摘要：H.264視頻編解碼標準中，幀內預測是很重要的一部分，它顯著提高了壓縮率，但增加了計算復雜性。H.264幀內預測編碼包括9種Intra_4×4和4種Intra_16×16的共13種預測模式，在分析當前幀內預測模式快速算法的基礎上，提出設置閾值與變換域相結合的方法來快速選擇Intra_4×4、Intra_16×16預測模式的最優模式，并以此對原算法進行了改進。仿真實驗表明，改進的算法在保持PSNR和碼率微小變化的情況下，計算復雜度能明顯降低。

關鍵詞：H.264；幀內預測；模式選擇；變換域

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)34-1709-02

Fast Mode Selective Algorithm of Intra Prediction for H.264/AVC

GONGBao-fu， HUO Chun-bao， ZHANG Yang

(Information Science Engineering College， Liaoning University of Technology， Jinzhou 121001， China)

Abstract: Intra-prediction is an important feature in the new H. 264 video coding standard ， which raised the compression ratio， but increase the computing complexity as well. Intra-prediction coding includes 9 Intra_4×4 and 4 Intra_16×16 13 prediction modes .Based on the analysis of the features of Intra_4×4 and Intra_16×16， a threshold and Integer Transform was proposed to save computation. Then， the algorithms for intra-prediction mode decision was modified. The experimental results show that the proposed algorithm can increase the speed of intra coding significantly with negligible loss of PNSR and a few increase ofbite rate.

Key words: H.264; intra prediction; mode select; integer transform

1 引言

H.264是ITU -T（國際電信聯盟）的VCEG(Video Code Expert Group)和ISO（國際標準化組織）的MPEG(Motion Picture Expert Group)兩個國際標準化組織的視頻編碼專家組成的JVT(Joint Video Team)頻編碼標準[1]。與視頻編碼標準H.263相比，H.264節約了50%的碼率，而且對網絡傳輸具有更好的支持功能，具有較強的抗誤碼特性，可適應丟包率高、干擾嚴重的無線信道中的視頻傳輸。H.264標準中引入了幀內預測編碼等新技術。H.264幀內預測編碼充分利用圖像的空間相關性，用圖像塊周圍的像素來進行幀內預測，并利用率失真優化(Rate-Distortion Optimization ，RDO)技術來進行最優幀內編碼模式的選擇，這降低了空間冗余，提高了視頻編碼的壓縮效率。然而，高效的幀內預測編碼也大大增加了編碼器的計算復雜度。幀內預測編碼模式選擇的計算復雜度成為影響H.264編碼速率，實現實時性應用的瓶頸之一。為了滿足實時視頻通信的要求，須使用快速算法，降低幀內預測編碼模式選擇的運算復雜度。

本文在分析當前幀內預測模式快速算法的基礎上，提出設置閾值與變換域相結合的方法來快速選擇Intra_16×16、Intra_4×4預測模式的最優模式，并以此對原算法進行了改進。

2 H.264現有的幀內預測算法

H.264在幀內預測模式中，預測塊P是基于已編碼重建塊和當前塊形成的[6]。對亮度像素而言，預測塊P可以是16×16的宏塊，或是4×4的亮度子塊。對于16×16的宏塊有4個可選的預測模式，適用于平坦區域圖像編碼，而對于4×4的亮度子塊則有9個可選的預測模式，獨立預測每一個4×4亮度子塊，適用于帶有大量細節的圖像編碼。色度塊也有4種預測模式，類似于16×16亮度塊預測模式。編碼器通常選擇使P塊和編碼塊之間差異最小的預測模式。

1) 4×4亮度塊預測模式

如圖1所示，4 ×4亮度塊的上方和左方像素A~M為已編碼并重構的像素[3]，用作編解碼器中的預測參考像素。a~p為待預測像素，利用A~M值和9種預測模式實現。其中模式2（DC預測）根據A~M中已編碼像素進行預測，而其余模式只有在所需預測像素全部提供后才能使用。圖2中的箭頭表明了每種模式的預測方向。對模式0和1，待預測的像素值是預測像素的直接拷貝。比如預測模式0中，待預測像素a，e，i，m的數值應該都是A。對模式3~8，預測像素由A~M加權平均而得。例如，模式4中，p=round(B/4+C/2+D/4)。

2) 16×16亮度塊預測模式

當使用16×16亮度預測模式時，宏塊中的所有亮度成分都被預測。支持四種16×16預測模式。分別稱為垂直預測模式（Vertical）、水平預測模式（Horizontal）、均值預測模式（DC）、 和平面預測模式（Plane）。16×16與4×4預測模式相似。其預測模式如圖3。

■

圖3 16×16亮度塊預測模式

3) 8×8色度塊預測模式

每個幀內編碼宏塊的8×8色度成分由已編碼左上方色度像素的預測而得，兩種色度成分常用同一種預測模式。4種預測模式類似于幀內16 ×16預測的4種預測模式，只是編號不同。其中DC為模式0，水平為模式1，垂直為模式2，平面為模式3。

為了保證在獲得盡可能好的編碼質量的同時， 能夠將編碼后的數據比特率降至最小， H.264/AVC 采用式RD_cost=SATD+λ·R率失真優化RDO(Rate Distortion Optimization) 判決，式中， SATD 表示編碼后的預測殘差絕對值之和， 即編碼后的總失真；λ表示拉格朗日優化參數( 與量化參數QP 有很強的相關性)；R表示編碼后的總的比特率。

一般校驗模型給出的都是一種幀內預測全搜索算法， 它通過遍歷592 種亮度宏塊和色度宏塊的組合， 計算出每種組合的RD_cost。從中選擇RD_cost 最小的一種預測模式作為此宏塊的幀內預測模式， 同時確定此宏塊的最佳尺寸。很顯然， 這種全搜索算法的復雜度和計算量很大。因此， 研究快速幀內模式選擇算法來提高編碼速度是很有必要的。

3 一種幀內預測模式選擇的快速算法

基于目前的現狀，減小幀內預測復雜度的方法大體上可分為三種，一種是縮小預測模式選擇范圍，另一類是簡化代價函數。還有一種就是在實現軟硬件上的結構上的優化。

對于這第一類方法，主要是利用當前塊及其周圍像素的某些特征，預先排除某些可能性很小的預測模式，或提前終止某些可能性小的模式的代價計算，從而降低幀內預測的復雜度。第二類方法主要對算法本身進行優化，以提高計算速度，常用的算法是通過分析算法本身特點，采用適合于計算的新的技術，如單指令多數據流技術，該技術可由一條單一指令完成多條操作，這種并行技術使運算速度得到顯著提高。此類算法的優點是對編碼圖像的質量沒有任何影響，不足之處是沒有充分利用到相鄰宏塊及圖像本身的信息。最后一類方法就是在硬件結構上優化程序，使得軟件程序更適應具體的硬件，需要進行移植程序。目前研究的主要方向還是主要集中在通過縮小預測模式選擇范圍的快速幀內模式選擇方法上。本文也將通過對比優秀算法的基礎上提出一種通過縮小預測模式范圍來降低運算復雜度的方法。

文獻[4]提出的快速算法是通過改變傳統的先進行4×4子塊的預測，后進行16×16宏塊的預測的順序等一些方法在算法復雜度降低的基礎上取得了一定的效果。因為在幀內預測中，一個宏塊如采用4 ×4 預測，其16 個4×4 塊的9 種模式須花費大量比特進行編碼，而如采用16 ×16 預測，只須對一個16×16 塊的4 種模式進行編碼，比特數大大減少。 同時，只有在圖像的細節部分進行幀內預測時，須使用4 ×4 預測來提高預測的精度，而對圖像中大量的平坦區域可使用16×16 預測。 因此，在幀內預測時可優先考慮16 ×16 預測，在保證預測精度的同時降低比特數及運算復雜度。但是在4×4 子塊的預測還沒有達到比較好的運算量。

文獻[5]提出了一種基于變換域的專門針對4 ×4 亮度子塊預測的算法。其算法中，通過變換域特性來過濾掉大部分的備選預測模式，從而在4 ×4 子塊的預測模式中大幅度的減少了運算復雜度。在空間域中，對于每一種預測模式，可以通過計算原像素和預測像素之間的絕對差之和（SAD）。客觀地說，最佳的預測模式必然是使SAD較小的一種預測模式。根據帕塞瓦爾定理，即在空間域和變換域中能量不變的原理，最佳預測模式對應的變換域系數絕對差之和也應該是最小的，對應得SATD計算公式為：

■ （1）

其中，I和P分別代表原像素和預測像素的數值。T表示一種特定的正交變換。在H.264中選擇的是Hadamard變換。其算法中通過分別計算 4 ×4 子塊的9中預測模式的SATD 值，并將SATD值從大到小排列。根據9個SATD值從被選模式中選擇n種模式作為最后的預測模式（1≤n≤9）。n 越大，測試結果與測試模型的算法越接近。根據相關的實驗測試，如果選擇SATD值最小的一種模式作為最后的預測模式，同全局RDO優化算法相比，新算法能夠得到平均60~70%的最優預測模式；如果選擇SATD值最小的2種模式作為預選模式，則能夠得到平均85%的最優預測模式；如果選擇SATD值最小的3種模式作為預選模式，則能夠得到平均94%的最優預測模式；如果選擇SATD值最小的6種模式作為預選模式，則99%的最優預測模式能夠得到；這種快速的算法使得能夠避免計算RDO優化算法中的代價J的繁重計算量，并且可以根據具體的精度要求來改變n的值，計算量只減無增。

本文基于上述分析提出了基于模式預測的快速算法，其主要步驟如下：

1) 對待預測的宏塊，利用前一幀相應位置的宏塊，如果相應的宏塊也為Intra_16×16，取其模式作為當前宏塊的預測模式記為Mode1。如果當前宏塊幀內其上方和左方的宏塊都為Intra_16×16，取其中小的模式作為當前宏塊的預測模式記為Mode2。如果以上均不滿足則預測模式定為DC 模式。2) 計算預測模式的cost值（如果有兩個預測模式則取其中cost值的較小者）并與閥值TH1進行比較。如小于TH1則跳到11，否則轉至3。3) 計算其余Intra_16×16預測模式的cost值，并選取4個模式中最小cost值作為Cost16×16，其對應的模式為Intra_16×16預測的最佳模式記為Mode16×16。4) 如果Cost16 ×16小于閥值TH2，則跳至11，否則轉至5。5) 根據圖2中的9種也測模式，由相鄰像素分別得到9種預測模式的預測像素值4×4矩陣。6) 分別對9種模式的預測4×4塊做Hadamard變換，并根據公式（1）計算出各種模式下的SATD值。7) 利用計算出的9種預測模式的SATD值從小到大進行排列，然后選出SATD值最小的3種預測模式作為預選模式。8) 將選擇的3種預選模式進行RDO優化算法中的代價計算，最終選出最佳預測模式。9) 遍歷所有的16個4×4塊，做步驟6~8的計算。并將所有的4×4塊的Cost4×4相加。10) 最后比較得出，當前宏塊采用4×4子塊或16×16宏塊預測。11)以SATD為判決依據來確定色度塊8×8的幀內最佳預測模式。12)預測過程結束。

在以上的快速算法中，對于16×16宏塊預測閥值的選取是個關鍵的問題，它會影響到編碼速度和圖象質量：當閥值選取過大時，有大量塊的預測模式被判為最佳模式，因而跳過其余模式的計算，減少了運算量，但是發生誤判的概率比較大。反過來，當閥值選取過小，計算量減少的不是很明顯，于是快速算法失去了意義。文獻[4]中給出當T H1和T H2都為前幀對應宏塊的Costmin×1.1時，能在復雜度和圖像質量間取得一個很好的折衷。同時，這樣的閾值選取也滿足根據不同內容自適應調整的要求。（下轉第1744頁）

（上接第1710頁）

4 實驗結果與分析

仿真試驗是以JVT提供的JM10.1算法[6]測試平臺，對其算法相關部分進行修改而進行的。為了檢驗本文提出的快速算法，采用4個不同運動順序的測試序列。Foreman、Claire、Coastguard、Bus。實驗數據如下表1（QP=16）和表2（QP=38）。

表1 QP=16的實驗結果對比

■

表2QP=38的實驗結果對比

■

仿真結果表明，快速算法取得了很好的效果。和原遍歷模式選擇算法相比，對應運行計算復雜度降低。而同時編碼質量的降低也在可接受范圍之內。

參考文獻：

[1] Pan F，Lin X，Susanto R，et al.Fast mode decision algorithm for Intra prediction in JVT，Doc.JVT-G013[C].7th JVT meeting，Pattaya，Thailand，2003.

[2] CHAN C C， CHANG T S. Fast Three Step Intra Prediction Algorithm for 4×4 Blocks in H.264[C].IEEE International Conference on Multimedia and Expo，2005:1509-1512.

[3] 畢厚杰，新一代視頻壓縮編碼標準——H.264/AVC[M].北京:人民郵電出版社，2005:92-96.

[4] 楊黎波，唐慧明，徐華根.H.264快速幀內預測算法[J].浙江大學學報:理學版，2006(2):42-46.

[5] 劉中華，劉陽.H.264幀內預測快速算法[J].科技信息:學術研究，2007(32):41-43.

[6] JVT Reference Software JM10.1[EB/OL].http://bs.hhi.de/sue2hring/tml/download/jm72.zip，2005.