低復雜度的快速降尺寸視頻轉碼算法

呂卓逸，賈克斌，蕭允治

(1. 北京工業大學 電子信息與控制工程系，北京 100124；

2. 香港理工大學 電子資訊與工程系，香港 九龍 999077)

1 引言

H.264是一種面向未來 IP和無線網絡傳輸環境下的視頻壓縮標準，在壓縮高效性和傳輸可靠性方面優于其他標準[1]。隨著網絡技術的飛速發展，H.264在各個領域中得到了廣泛應用，基于H.264的視頻編碼及轉碼技術成為近年來國內外研究的熱點。

由于網絡種類的多樣性（如Internet網、電信網和蜂窩無線網等），終端設備性能（如顯示分辨率、處理能力和存儲能力等）的差異，使得提高視頻碼流在不同應用環境之間的兼容性變得十分重要[1]。轉換空間分辨率的視頻轉碼，為支持各類視頻顯示設備提供了有效的解決方法，它將原始分辨率的視頻碼流轉換為適合接收端顯示的目標分辨率碼流。

理想的視頻轉碼器應具備低運算復雜度，高轉碼質量等性能。運動估計和多尺寸幀間模式預測是H.264編碼中非常關鍵且耗時的模塊，為視頻轉碼帶來極大的運算負擔，影響到算法的實時性[3]。因此，如何有效利用輸入碼流中的編碼信息來提高轉碼速度成為視頻轉碼研究中的關鍵問題。對此，眾多科研人員做了大量工作來優化轉碼器。文獻[2]聯合宏塊的空間和時間特性，通過計算率失真代價從前一參考幀中選擇最優編碼模式。針對基于像素域的轉碼運算復雜度高的問題，許多基于壓縮域的轉碼框架相繼出現。文獻[3]提出的合并分裂算法，在DCT（discrete cosine transform）域內實現了降尺寸轉碼。但是此類方法在重量化過程中易引入誤差產生漂移（drift），影響轉碼圖像質量。因此，如何提高轉碼效率的同時保證圖像質量仍然是一個有待探索的課題。

支持向量機（SVM, support vector machine）是由Vapnik提出的一種學習機制，近幾年來成為模式識別與機器學習領域研究的熱點[4]。SVM以統計學習理論為基礎，基于結構風險最小化原則，有效地避免了經典學習方法中過學習、維數災難、局部極小等傳統分類存在的問題。在解決小樣本、非線性和高維模式識別問題中表現出明顯優勢[5]。現已廣泛應用于文本識別、人臉識別、三維圖像識別和生物信息學等方面。本文首次將SVM理論應用于基于H.264的降尺寸視頻轉碼中，針對特征向量及核函數的選取，分類器決策樹結構的設計展開研究。

本文提出一種將SVM的理論應用于快速降尺寸視頻轉碼的方法。首先從輸入的高分辨率視頻碼流中提取模式特征組成多維特征向量訓練SVM分類器模型，建立高分辨率視頻編碼信息與降尺寸視頻宏塊編碼模式之間的相關性。然后設計構建出分層式SVM分類器，對降尺寸視頻中宏塊的預測模式進行分類，以此縮減預測模式數量，實現轉碼的再編碼過程中率失真優化算法的提前終止，達到降低轉碼運算復雜度的目的。

本文在第 2節中介紹 H.264幀間模式選擇算法，第3節詳細論述基于SVM的降尺寸轉碼快速模式決策算法，第4節給出實驗結果及分析，最后是結束語。

2 H.264幀間模式選擇

H.264編碼標準支持7種不同塊大小的幀間編碼模式。每個宏塊可按照 16×16，16×8，8×16，P8×8進行第1層的大塊模式分割，如果選擇P 8×8模式，還可按照 8×8，8×4，4×8，4×4 進行第2 層的小塊模式亞分割[6]。

另外，幀間編碼還采用直接拷貝模式（SKIP），幀內預測模式I4MB和I16MB。因此，H.264幀間模式選擇算法流程如下。

1) 對宏塊的大塊模式 16×16，16×8，8×16 進行運動估計，利用式(1)計算率失真代價（RDO, rate distortion optimal）。其中D是宏塊的失真，R是需要編碼的信息碼率，λ是用來調節失真與碼率權重的Lagrange系數。

2) 對每個 P8×8塊的小塊模式 8×8，8×4，4×8，4×4進行運動估計，并計算其RDO，選擇RDO最小的模式作為P8×8塊的最佳模式。

3) 計算SKIP模式的運動矢量和RDO值。

4) 計算幀內編碼模式I4MB和I16MB的RDO值。

5) 從 16×16，16×8，8×16，P8×8，SKIP，I4MB和I16MB中選擇RDO值最小的模式作為幀間宏塊編碼模式。

由于需要對每一種候選模式進行運動估計和率失真代價的計算，使得編碼計算量急劇增加，編碼速度下降。為此，本文利用基于SVM的快速模式選擇算法實現了低復雜度的降尺寸視頻轉碼框架。算法的提出以輸入碼流中編碼信息與降尺寸視頻中宏塊編碼模式間有著較強相關性為依據，將H.264模式選擇問題轉化為模式分類問題，即依據編碼信息將預測模式按其特征劃分為不同的類別，以此減少計算率失真代價的模式數量。

3 基于SVM的轉碼模式快速選擇算法

如上所述，H.264編碼器的運算復雜性為引入機器學習方法來提高視頻轉碼速度帶來了良好契機。支持向量機方法是建立在統計學習理論中 VC維（vapnik chervonenkis dimension）[7]理論和結構風險最小原理基礎上的。對訓練樣本集(x1,y1),…,(xl,yl)∈RN×{±1}，其中，xl是從輸入的高分辨率視頻碼流中提取的特征向量，yl為低分辨率視頻中相應宏塊的編碼模式，N為樣本特征（特征向量）空間的維數。SVM的目標是求解能夠將2類樣本正確分開，且使得分類間隔最大的最優分類線。對于非線性可分情況，SVM通過映射 Φ 將非線性問題轉換為高維特征空間中線性問題，利用核函數 K(xi, xj)代替最優分類面中的內積，求解最優分類面的目標函數：

鑒于SVM在模式識別等領域，尤其在解決較復雜分類問題方面表現出來的優越性，本文提出了基于SVM的轉碼模式快速選擇算法。

3.1 分層式SVM分類器

一般來說，視頻序列中分布均勻的區域，例如背景區域，通常采用大塊分割模式（16×16，16×8，8×16），而分布不均勻的區域和邊緣部分通常采用小塊分割模式（8×8，8×4，4×8，4×4）。同時，視頻序列中相鄰圖像之間普遍存在著時間相關性，即相鄰圖像的大部分區域的變化是比較緩慢的，如背景區域中SKIP模式占有相當大的比重，而處于較長時間靜止不動或者變化緩慢區域內的宏塊通常采用大塊分割模式。因此，利用從輸入碼流中提取的編碼信息，減少預測模式，僅對少量可能性大的模式計算率失真代價，將有效降低轉碼的運算復雜度。

SVM方法最初用于數據二分類問題[8]，多分類問題是被分解為多個二分類問題來實現的。目前的多分類算法，例如一對多（one against all）和一對一（one against one）等存在的共同問題是：多數量的二分類問題需要進行大規模的標準二次型優化，造成訓練過程速度慢、算法復雜難以實現以及預測運算量大等問題。為了避免多分類器的弊端，本文采用基于二分類的SVM分類器以期獲得更加準確的預測結果和更優的轉碼效果。

本文構建的分層式 SVM 分類器由以下 3個SVM二分類器組成，在降尺寸視頻轉碼編碼器中對宏塊進行階梯式模式決策。

1) 頂層分類器劃分SKIP模式和non-SKIP模式。如果當前宏塊被劃分為 SKIP模式，則僅預測幀間16×16模式和SKIP模式。換而言之，此分類器用于劃分出位于紋理分布較均勻或運動平緩區域的宏塊。

2) 中間層分類器劃分幀內模式和幀間模式。被劃分為幀內模式類別的宏塊，表明其具有運動劇烈或紋理復雜的特征，采用Intra-refresh模式編碼。

3) 下層分類器對在頂層和中間層SVM分類器中被劃分為non-SKIP模式和non-intra模式的宏塊進行細分，劃分為大塊分割模式和小塊分割模式。

為了保證轉碼后視頻具有較高質量，本文對通過SVM分類后的編碼模式進行小范圍的模式修正，以犧牲少量運算量為代價來獲得更加準確的決策模式。模式修正策略的具體思想是：如果當前宏塊被劃分為大塊分割模式，則預測{inter16×16, inter16×8, inter8×8}和SKIP模式；如果當前宏塊被劃分為小塊分割模式，則預測 7種幀間模式，SKIP模式和幀內模式。算法流程如圖1所示。

圖1 算法流程

分層式SVM分類器實現了模式選擇的階梯式預判，通過縮減預測模式數量提前終止率失真優化算法，達到降低算法復雜度的目的。圖2描述了基于SVM的視頻轉碼器實現框。首先，從高分辨率視頻碼流中提取編碼信息作為特征向量組成 SVM訓練樣本集。其次，利用SVM模型建立的分層式分類器得到最終預測模式，實現低復雜度的H.264視頻轉碼。本文采用離線方法進行SVM模型的訓練及預測，因此不會對轉碼器帶來額外的運算負擔。

圖2 基于SVM的轉碼模式選擇

3.2 特征向量的選取

作為 SVM 理論中的關鍵技術，特征向量的選取直接影響著 SVM 分類器的準確度，是構建SVM分類器的關鍵。特征向量的選擇應滿足與宏塊編碼模式具有強相關性的原則，而直接利用輸入的視頻碼流中的編碼信息作為特征向量組成樣本集得到的分類準確度較低，因此需要對原始數據進行預處理。針對本文提出的3層式模式分類體系，選取4個特征向量分別組成各層分類器的訓練和預測樣本集。

首先，本文針對降尺度因子為1/4的視頻轉碼進行研究，最直接的方法是選擇在高分辨率視頻的4個相鄰宏塊中編碼模式出現頻率最高的作為當前宏塊的編碼模式。實驗數據表明，通常情況下，出現頻率最高的模式往往是通過率失真優化算法得到的最終編碼模式，尤其是當編碼模式為SKIP模式和大塊分割模式時。表1中數據是由式(3)計算獲得，其中，Pmodei表示高分辨率視頻的4個相鄰宏塊中使用頻率不小于2的編碼模式數量(Hmodei)與降尺寸視頻實際采用該模式數量(Lmodei)的比例。因此，宏塊編碼模式在高分辨率視頻中的出現頻率被選作特征向量之一。

表1 出現頻率與編碼模式相關性

其次，幀間模式中各尺寸塊的選擇對編碼質量有著重要影響。選擇大尺寸塊意味著編碼運動矢量和幀間分割模式占用比特較少，而運動劇烈區域內宏塊在運動補償后的殘差較大；相反，如果選擇小尺寸塊則殘差較小，而大量的比特耗費在編碼運動矢量和幀間分割模式上。本文將運動矢量和宏塊殘差作為下層SVM分類器的特征向量，并通過數據預處理來提高預測準確度。利用統計計算方法將運動矢量轉換為運動矢量絕對值之和，將宏塊殘差轉換為殘差均值。經過預處理之后的樣本集，類別分布更加清晰，模式表述更加明確。

另外，鑒于殘差塊不為零的 DCT系數與宏塊特征的緊密聯系，且其提取方法簡單，無需進行DCT逆變換，因此選為上層分類器的特征向量。最后，將降尺寸視頻中宏塊編碼模式規范為 6類：SKIP、non-SKIP、intra、non-intra、big-partition 和small-partition。

綜上所述，分層式SVM分類器的特征向量FV1,FV2和FV3分別包含如下屬性。在對預測準確度的分析比較中（表 2）可以看到，本文選取的特征向量組成樣本集達到了較理想的訓練和預測效果。

FV1=[原視頻模式使用頻率，不為零DCT系統個數]

FV2=[原視頻模式使用頻率，運動矢量絕對值之和]

FV3=[原視頻模式使用頻率，運動矢量絕對值之和，殘差均值]

3.3 核函數的選擇

核函數是支持向量機的重要組成部分，采用不同的核函數會組成不同的支持向量機算法。核函數、映射函數和特征空間一一對應，核函數參數的改變實際上隱含地改變了映射函數，進而改變樣本數據子空間分布的復雜程度。因此，核函數的選取變得十分重要。

目前，在SVM中研究最多的核函數主要有4類：線性(linear)核函數，多項式(polynomial)核函數，徑向基函數(RBF)和sigmoid核函數。總體來說，核函數可以劃分為局部核函數和全局核函數2種[9]。局部核函數的學習能力較強，泛化能力較弱，而全局核函數的泛化能力較強，學習能力較弱。

表2 運用不同特征向量獲得SVM模型預測準確度/%

為了選取適用于視頻轉碼幀內預測算法的最優核函數，本文定義了核函數性能參數 J。假設輸入空間中的 2 類樣本：(x1, x2,…, xl)和(xl+1, xl+2,…, x2l)分別屬于類別 C1和 C2，其中 l為樣本數量。各類中心點在特征空間中表示為

用核函數K(xi, xj)替代映射函數Φ，計算類中心的二次范數：

由式(6)計算獲得各類緊湊度參數δ21和δ22：

類別間的中心距離為

最后，得到核函數性能參數J：

其中，分子代表不同類樣本在特征空間中的可分度，分母代表同類樣本的緊湊度。可見，J值越大則該核函數的性能越好。

從表3中可以看出，對于3層SVM分類器，徑向基函數(RBF)的 J值最大，因此選作最優核函數進行SVM訓練及預測。

表3 核函數J值

4 實驗結果與分析

在實驗中，編碼采用H.264的測試模型JM12.2，實驗平臺使用Visual C++6.0。選擇開源軟件libSVM[10]作為SVM開發工具，并采用離線方法訓練SVM分類器，因此不會給轉碼器帶來額外運算負擔。

為了驗證本文提出算法的轉碼效果，實驗選取常用分辨率格式CIF和4CIF，共16段具有不同運動程度、紋理特征的測試序列訓練SVM分類器模型。首先將高分辨率視頻利用 JM12.2進行編碼再解碼，以便提取編碼信息訓練SVM模型。然后將CIF格式視頻 Foreman，Mother-daughter、Paris和Silent，以及4CIF格式視頻Crew、Harbor、Ice和Soccer以1/4尺寸縮小。編碼采用首幀為幀內編碼（intra-frame，I幀），后續幀為幀間編碼（inter-frame，P幀），QP設置從22～32。

為評估本文選取特征向量的優劣，實驗中另外選用文獻[4]中使用的特征向量 FVo1，FVo2和 FVo3訓練SVM模型Modelo，與本文的SVM模型Modelp進行比較。

FVo1=[不為零DCT系統個數，殘差均值，殘差方差]

FVo2=[不為零DCT系統個數，殘差均值，列差方差]

FVo3=[不為零DCT系統個數，殘差均值，殘差方差，運動矢量均值]

表2所示為采用不同特征向量訓練SVM模型預測編碼模式的準確度。可以看出，基于兩組不同的特征向量，本文模型Modelp達到的預測準確度更高，平均達到83.42%，最高可達97.95%。實驗用于SVM訓練與預測的視頻序列不同，從實驗結果可以看出此SVM分類器具有很好的泛化及推廣能力。

本文提出的基于SVM的視頻轉碼快速模式選擇算法，與全搜索（full mode）算法和文獻[2]中提出的時空域聯合幀間模式預測算法（STMP）在轉碼質量、比特率、預測準確度和轉碼速度幾方面進行比較。文獻[2]針對H.264編碼，利用宏塊的時域和空域特征對幀間模式進行快速選擇；而本文針對H.264視頻轉碼，利用高分辨率視頻碼流中的編碼信息對低分辨率視頻進行快速幀間編碼。由于STMP是最新且編碼效果最好的方法之一，因此作為對比算法，與本文提出的方法在轉碼再編碼過程中進行編碼效果的比較。

表4 幾種算法進行轉碼效果比較

如表4（正值表示增加，負值表示減小）所示，基于SVM的模式選擇算法比傳統的全搜索算法平均節省45.8%時間，并保證PSNR僅下降0.13dB，比特率增加10.1%。文獻[2]提出的算法STMP比full mode方法平均節省 41%運算時間，PSNR下降0.25dB，比特率增加29.7%。

另外，轉碼的效果與視頻序列的內容，即運動快慢和分辨率有關。從PSNR和比特率2個方面考慮，利用STMP方法轉碼4CIF格式視頻比轉碼CIF視頻效果更好，而SVM方法轉碼CIF視頻比轉碼4CIF格式視頻效果更佳。對于4CIF格式視頻STMP算法比SVM算法獲得的圖像質量稍好，但是運算復雜度較高。從圖3和圖4可以看出，總體來說，對于大多數視頻序列而言，本文提出的基于 SVM的模式選擇算法相比STMP方法達到的轉碼效果更好，尤其是運動劇烈的視頻，例如Foreman序列等。

綜合衡量運算復雜度、轉碼質量和壓縮率等因素，本文提出的算法在有效提高降尺寸轉碼速度的同時，與現有算法相比，取得了更優的編碼效果和更廣泛的適用性。

圖3 Ice序列

圖4 算法復雜度

5 結束語

本文重點分析了H.264降尺寸轉碼中模式選擇算法，針對視頻轉碼運算復雜度高的問題，提出一種基于SVM的快速轉碼框架。利用SVM方法建立高分辨率視頻碼流編碼信息與降尺寸視頻中宏塊編碼模式間的聯系。在此基礎上，設計構建分層式SVM分類器來預測宏塊編碼模式。此算法縮減了預測模式的數量，實現轉碼再編碼過程中率失真優化算法的提前終止。實驗結果表明，本文提出的算法有效降低了全搜索算法的轉碼時間，節省了高達67.31%的運算量，并保證極小的圖像質量下降。

本文專門針對基于 H.264的同類視頻轉碼降尺寸轉碼中模式選擇算法進行研究。由于 H.264降尺寸視頻轉碼具有很高的實際應用價值，因此如何在提高轉碼后視頻質量的同時有效降低編碼復雜度方面仍需要進行改進。在下一步的工作中，將對運動矢量合成算法進行研究，以期進一步提高轉碼速度。

[1] STOCKHAMMER T, HANNUKSELA M M. H.264/AVC video for wireless transmission[J]. IEEE Wireless Communication, 2005,12(4):6-13.

[2] SONG-HAK R, YURI V, JOERN O. Fast inter-mode detection in an H.264/AVC encoder using mode and lagrangian cost correlation[J].IEEE Transactions on Circuits and Systems for Video Technology,2009, 19(2): 302-306.

[3] FUNG K T, SIU W C, DCT-based video downscaling transcoder using split and merge technique[J]. IEEE Transaction on Image Processing,2006, 15(2):394-403.

[4] JING X, SIU W C, CHAU L P, et al. Efficient inter mode decision for H.263 to H.264 video transcoding using SVMs[A]. Proceedings IEEE International Symposium on Circuits and Systems[C]. Taipei, China,2009. 2349-2352.

[5] JAEIL K, MUNCHURL K. Block-mode classification using SVMs for early terminatio of block mode decision in H.264|MPEG-4 part 10 AVC[A]. Proceedings, 2009 Seventh International Conference on Advances in Pattern Recognition[C]. Kolkata, India, 2009. 83-86.

[6] 謝晶，賈克斌. 一種基于二維直方圖的 H.264/AVC快速幀內預測判決算法[J]. 電子與信息學報, 2005, 27(7):1053-1057.XIE J, JIA K B. A fast Intra-frame prediction algorithm based on two-dimensional histogram for H.264/AVC[J]. Journal of Electronics& Information Technology, 2005, 27(7): 1053-1057.

[7] VAPNIK V N. Statistical Learning Theory[M]. New York, Wiley,1998.

[8] LIU Z B, JIN L W. A new method for multi-class support vector machines[A]. Proceedings 2008 International Joint Conference on Neural Networks[C]. Hong Kong, China, 2008. 727-732.

[9] SONG H Z, DING Z C, GUO C C, et al. Research on combination kernel function of support vector machine[A]. Proceedings 2008 International Conference on Computer Science and Software Engineer[C]. Wuhan, China, 2008. 838-841.

[10] CHANG C C, LIN C J. LIBSVM: a library for support vector machines[EB/OL]. http://www.csie.ntu.edu.tw/～ lin/libsvm.