??? 摘? 要： MPEG4 AVC/ITU-T H.264視頻編碼標準因其優異的編碼效率和性能而被廣泛采用，但其模式決策問題導致運動估計器運算復雜度非常大。本文提出一種快速模式決策算法的實現方法。仿真結果證明，本方法在編碼質量降低較小的情況下，能夠減少80%以上的編碼時間。
??? 關鍵詞： H.264? 快速模式決策? 編碼器復雜度
?
1 現有的快速決策算法
??? ITU-T和ISO/IEC組成的聯合視頻專家組(JVT)于2003年3月公布了H.264/MPEG-4 AVC標準(以下簡稱H.264)。與MPEG-4 ASP標準相比，在編碼質量相同的情況下，編碼率可以減少50%。這一優異性能的取得很大程度上得益于H.264所采用的多模式、多參考幀的運動估計編碼算法和多模式幀內預測編碼算法。但是，其采用的基于最佳碼率和失真折衷（Rate-Distortion Optimization，RDO）的模式決策算法，使編碼算法的復雜度提高了3倍，編碼時間也大大增加。而且，H.264用于模式決策的時間占整個編碼時間的80%~90%。所以，如何有效加快模式決策過程的實現速度，成為當前研究的熱點。
??? 針對運動估計模式的快速決策算法已有如下幾種：(1)通過3×3的Sobel計算得到當前宏塊的邊緣矢量圖(Edge Map)，然后利用每點邊緣矢量的幅度值之和的統計特性去判斷宏塊的空間一致性，并根據一致性越強所采用的運動估計塊越大的原則，減少進行復雜的碼率和失真折衷值（Rate-Distortion Cost，RDC）計算的候選模式數量。但是，由于Sobel計算涉及每個象素點，因此它本身的計算量也很大。(2)利用模式間的相關性把7種模式分組，計算有代表性的16×16、8×8、4×4三種模式的RDC值，通過分析結果選擇出最佳的模式組，然后只對組內的候選模式進行RDC計算。這種算法沒有考慮編碼圖像自身的特性，能夠刪除的候選模式不多。(3)只進行基于8×8子塊的運動估計，通過分析得到的4個運動矢量間的相似性進行估計塊(即模式)的合并，合并后得到的模式即為最佳模式。此外，也有學者針對幀內編碼模式的選擇，提出了多種快速算法。
??? 本文提出一種適合在移動終端設備等計算能力有限的應用場合下進行H.264實時編碼的快速模式決策算法的實現方法。該方法具有計算復雜度低和邏輯簡單的特點。實驗證明，在圖像質量和壓縮效率降低很少的情況下，該方法使編碼速度提高了80%以上。
2? H.264的模式決策算法
??? H.264采用8種幀間編碼模式，包括7種采用不同大小和形狀的運動估計塊對宏塊進行運動估計的編碼模式和SKIP模式。H.264幀間預測模式如圖1所示，其決策算法是：首先，對宏塊分別計算16×16、16×8、8×16和SKIP 4種模式下的RDC值；然后，對宏塊中的每一個8×8子塊分別計算8×8、8×4、4×8和4×4 4種子模式下的RDC值，得到具有最小值的最佳子模式，再將子塊的最小RDC值相加得到宏塊在模式下的RDC值；最后，在宏塊層次上比較各模式RDC值，選取值最小的模式作為宏塊最佳編碼模式。
?
??? 在幀內編碼方面，H.264采用基于4×4子塊和基于16×16宏塊的2種預測模式，其中4×4模式有9個預測方向，宏塊模式有4個預測方向。在最新的參考軟件JM9.3中加入了基于8×8子塊的預測模式。每一種預測模式都是利用相鄰已編碼塊的樣點值去預測當前塊的樣點值。H.264要分別計算宏塊在基于4×4、16×16和8×8 3種模式下的各個預測方向的RDC值，并選擇值最小的模式作為最佳幀內預測模式。如果當前編碼宏塊屬于幀間預測幀（P幀），該最小值還要與最佳幀間編碼模式的RDC值進行比較來確定最佳模式。
??? H.264協議采用Lagrange代價函數計算每種模式下宏塊的RDC值，其定義如下：
??? 
??? 式(1)中，JMODE表示相應模式的RDC值，λMODE是Lagrange因子，其值與量化系數有關。R(s，c，MODE)指的是該模式所需的編碼比特數。SSD(s，c，MODE)指的是原始宏塊和重建宏塊之間的平方差之和，其定義如下：
??? 
式(2)中，S(x，y)表示原始宏塊，C(x，y)表示重建宏塊。
??? 通過上面的分析可以看到，H.264在進行宏塊模式決策時，運動估計、量化、反量化和DCT變換等操作被多次反復調用，這樣的計算強度對于實時性要求較高的視頻通信應用及處理能力相對較弱的手持設備而言是很難被接受的。
3? 模式決策算法的快速實現
3.1 提出方法的動機
??? H.264協議幀間模式決策的基本原則是：對只含有背景成分、全局運動成分或很少量局部運動成分的宏塊采用大估計塊模式進行編碼；對于含有豐富運動成分的宏塊采用小估計塊模式進行編碼。由此可以得出：隨著7種運動估計塊自大向小被調用，宏塊的RDC值呈現出近似的單調變化趨勢。所以，通過對這種趨勢的分析，很可能在不調用所有模式的情況下得到最佳編碼模式。
??? 使用H.264參考軟件JM9.3對9個QCIF和CIF格式的圖像序列進行編碼實驗，編碼模式的分配情況如表1所示。從表中可以得到很多關于圖像統計特性的信息：(1)SKIP模式被使用的概率相當高，特別是那些類似于視頻通信應用的圖像序列，如Claire、News等序列。這表明對這些圖像進行編碼時如果能夠盡早確定是否采用SKIP模式，將使模式決策過程所需的時間大大減少。(2)P幀中的宏塊使用幀內預測編碼模式（表中INTRA列）的概率很低，所以對P幀中的宏塊不采用幀內模式對編碼質量不會產生大的影響。(3)對于8×8的子塊采用8×4、4×8、4×4 3種子模式的概率較低，特別是在那些類似于視頻通信應用的序列中，這3種子模式被使用的概率只有1%左右，而含有許多運動成分的圖像序列使用這3種子模式的概率大約是2%～10%。由于算法主要針對小尺寸視頻圖像在移動終端設備中的應用，為了大幅度降低算法復雜度可以去掉這3種子模式。
?
3.2 幀間模式決策算法的快速實現
??? 通過分析，本文提出一種快速模式決策算法的實現方法。具體步驟如下。
??? 第1步：計算編碼宏塊SKIP模式的RDC值JSKIP并與閾值TSKIP比較，若小于閾值則表示SKIP模式為最佳模式，模式決策過程結束；否則，到第2步。其中閾值TSKIP的確定方法是根據經驗確定一個比較小的初值，在編碼過程中利用所有用SKIP模式編碼的已編碼宏塊的RDC值的均值動態改變它。
??? 第2步：計算16×16模式的RDC值J16×16和16×8模式的代價函數值J16×8，若J16×8-J16×16≥T16，則表示隨著運動估計塊的變小，宏塊RDC值增大的趨勢已經明顯，所以設16×16模式為最佳模式，模式決策過程結束；否則，到第3步。其中閾值T16的確定方法與第1步中TSKIP的確定方法類似。
??? 第3步：計算8×16模式的RDC值J8×16，若J8×16-J16×16≥T16，則根據與第2步相同的原因，設16×16模式為最佳模式，模式決策過程結束；若J16×8-J16×16≥T16且J8×16-J16×16≥T8，也可認為隨著運動估計塊的變小，宏塊RDC值有增大趨勢，所以設16×16模式為最佳模式，模式決策過程結束；若J8×16
??? 第4步：計算8×8模式的RDC值J8×8，并與上面得到的各種模式的值進行比較，得到最佳模式。
3.3 幀內模式決策算法的快速實現
??? 關于幀內預測模式決策算法的快速實現，本文提出的方法的核心思想是利用反映圖像空間特性的原始圖像和預測圖像在變換域中的絕對差值之和（SATD）與JMODE值之間的相關性，減少需要RDC計算的候選模式的數量。SATD定義如下：
??? 
式中I(x，y)表示原始圖像值，P(x，y)表示預測圖像值，T{}表示Hadamard變換，bk表示取值范圍，即塊的大小。
??? 方法的具體步驟是：(1)計算每個4×4子塊基于4×4預測模式的可能預測方向上的SATD值。(2)選擇具有最小SATD值的3個模式進行RDC值的計算，如果由相鄰的已編碼塊得出的最可能模式沒有被包含其中，則還要計算這種模式的RDC值。(3)選出具有最小RDC值的模式為4×4子塊的最佳模式。對基于8×8塊的預測模式的選擇采用同樣的辦法。
4? 仿真結果
??? 根據本文提出的方法，修改軟件JM9.3的相應部分，并對8個格式為CIF和QCIF的圖像序列進行了編碼仿真。具體的仿真環境：編碼幀數為100，參考幀數為5，序列形式為IPPP，固定的量化系數（28、38），CAVLC熵編碼。此外，采用JM軟件默認的運動估計算法，搜索范圍為16。本方法的仿真結果如表2所示。表中ΔPSNR-Y表示本方法與原算法編碼圖像亮度信號之間的PSNR差值，ΔBitrate表示比特的增加比率，Speed Up表示編碼時間的減少比率。仿真結果表明，本方法雖然使得圖像質量有所下降，但明顯減少了編碼時間。
?
5? 結束語
??? 本文提出的H.264模式決策算法的快速實現方法，有效利用了圖像序列和編碼模式的統計特性和空間特性。因此，本方法能夠在編碼質量下降不多的情況下，大幅度地降低編碼時間和算法復雜度，使H.264協議更適于移動終端設備的視頻通信應用。下一步的工作重點是改進運動估計的搜索算法，擬采用自適應路徑搜索算法（Adaptive Root Pattern Search，ARPS），以及整個決策算法的硬件實現和仿真。
參考文獻
1?? Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification.ITU-T Rec.H.264 | ISO/IEC 14496-10 AVC，2003
2?? Wiegand T，Sullivan G J，Bjontegaard G et al.Overview of H.264 Video Coding Standartd.IEEE Trans on Circuits?and Systems for Video Technology，2003；13(7)
3?? Wu D，Wu S，Lim K P et al.Block Inter Mode Decision for Fast Encoding of H.264.In：IEEE Int′l Conference on?Speech Acoustics and Signal Processing，2004
4?? Yin P，Tourapis H Y，Tourapis A M et al.Fast Mode Decision and Motion Estimation for H.264.In：IEEE Int′l Conference on Image Processing，2003
5?? Tu Y，Yang J，Shen Y et al.Fast Variable-size Block Motion Estimation Using Merging Procedure with an Adaptive Threshold.In：IEEE Int′l Conference on Multimedia & Expo，Baltimore，Maryland，2003
6?? Kim C S，Shih H H，Kuo C J.Feature Based Intra-prediction Mode Decision for H.264.In：IEEE International Conference on Image Processing，2004