基于改進KNN算法的AVS到H.264/AVC快速轉碼方法

沈 皓

（1.上海交通大學，上海 200240；2.中國南方航空上海分公司，上海 201202）

基于改進KNN算法的AVS到H.264/AVC快速轉碼方法

沈 皓1，2

（1.上海交通大學，上海 200240；2.中國南方航空上海分公司，上海 201202）

盡管音視頻編碼標準（Audio and Video Coding Standard，AVS）的編碼性能可以與H.264相媲美，但是H.264的應用范圍更加廣泛，因此視頻由AVS標準轉碼成H.264標準具有很大的應用前景。目前，主流的轉碼方法是將AVS的分塊模式與H.264的分塊模式映射的方式降低轉碼復雜度，但是技術之間的差異導致這兩種標準之間的分塊模式并不是一一映射的關系，因此會導致編碼效率大幅度降低。提出一種基于改進KNN（K最鄰近節點）算法的AVS到H.264/AVC快速轉碼方法。充分利用了AVS碼流中的各種信息，通過改進的KNN算法建立了中間信息和H.264分塊模式之間的映射模型。根據AVS中運動矢量信息的差異自適應確定H.264可能的分塊模式，實驗結果表明上述問題得到有效解決，該算法在保證H.264編碼效率的前提下大幅降低了轉碼復雜度。

音視頻編碼標準；H.264/AVC；快速轉碼；K最鄰近結點算法

隨著網絡技術和多媒體技術的飛速發展，視頻轉碼技術[1-2]越來越受到關注。一方面，現存有很多種視頻編碼標準，比如MPEG-1、MPEG-2、MPEG-4、H.264[3]、AVS[4]以及HEVC[5]，因此很多視頻內容經常被壓縮成不同的視頻格式；另一方面，隨著移動通信設備的迅速發展，需要將一種視頻格式轉到另一種視頻格式，或者從一種分辨率轉到另一種分辨率的視頻格式，以適應各種通信終端的需求。作為中國音視頻編碼標準工作專家組牽頭制定的標準，AVS擁有與目前應用更為廣泛的高效視頻壓縮標準H.264/AVC相當的壓縮性能[6]。目前，很多企業都已經生產了基于AVS標準的視頻設備，特別是中國存在很多AVS格式的視頻內容，而市面上很多設備都支持H.264/AVC標準。為了在這些設備中有效地進行視頻內容的共享，AVS到H.264/AVC的轉碼是必不可少的。

最簡單的視頻轉碼技術就是先對視頻完全解碼再重新進行編碼，然而這種方法并未充分利用已編碼的碼流信息，因此轉碼效率很低。目前，國內外很多學者開展了許多快速轉碼研究工作。Wang等人[7]利用AVS的幀內預測模式預測H.264/AVC中的幀內預測模式，跳過H.264/AVC幀內預測模式過程以降低編碼復雜度。Shang等人[8]將AVS標準中幀間編碼宏塊的分割模式信息直接映射到H.264/AVC編碼過程中每個宏塊的分割模式，從而大幅度提升了轉碼速度。Wang等人[9]利用AVS解碼過程中的模式和運動矢量實現快速高效的轉碼。這些方法很好地利用了AVS碼流中的一些信息來加速轉碼，但是沒有結合編碼H.264/AVC碼率后的信息進一步提高轉碼后視頻質量，因此仍有進一步提升的空間。此外，有些研究工作在視頻轉碼中引入了機器學習的理論，Ge?rardo等人[10]假設H.264/AVC的宏塊編碼模式決定過程與MPEG-2中運動補償殘差的分布具有線性關系，利用MPEG-2運動補償殘差的分布與H.264/AVC宏塊編碼模式之間的相關性，利用機器學習的方法加速轉碼過程。這種方法的缺陷是在轉碼過程中會增加訓練時間，在一定程度上會增加轉碼的復雜度。

本文充分利用了AVS碼流中的各種碼流信息，同時為解決機器學習算法在轉碼過程中需要耗費大量訓練時間的問題，提出了一種基于改進型機器學習的AVS到H.264/AVC快速轉碼方法，旨在保證H.264/AVC壓縮效率的前提下降低轉碼的復雜度。

1 AVS到H.264/AVC轉碼分析及動機

H.264/AVC中每個宏塊（Macro Block，MB）編碼會遍歷宏塊分割模式16×16、16×8、8×16和8×8，以及亞宏塊分割模式8×8、8×4、4×8和4×4，這兩種分割模式分別如圖1a和圖1b所示。該方法自適應地根據視頻內容選擇合適的分割模式，從而獲得較好的編碼性能，但是一個宏塊需要重復編碼8次，因此復雜度非常高。AVS為了在盡量保證視頻質量的前提下降低編碼過程的復雜度，每個宏塊只采用了16×16、16×8、8×16和8×8四種分割模式。

圖1 H.264/AVC幀間預測宏塊分割模式

為了探索AVS和H.264/AVC模式之間的相關性，本文測試了4種情況下模式的命中率，命中率表示事件A中的像素數目與事件B中像素數目的比值，并做了如下規定：

1）AVS碼流中某宏塊解碼得出的模式為16×16分割模式，且H.264/AVC最終編碼使用的分割模式也為16×16，該事件記為A；

2）AVS碼流中某宏塊解碼得出的模式為16×8分割模式，且H.264/AVC最終編碼使用的分割模式也為16×8，該事件記為B；

3）AVS碼流中某宏塊解碼得出的模式為8×16分割模式，且H.264/AVC最終編碼使用的分割模式也為8×16，該事件記為C；

4）AVS碼流中某宏塊解碼得出的模式為8×8分割模式，且H.264/AVC最終編碼使用的分割模式也為8×8或者8×4、4×8、4×4，該事件記為D。為了驗證上述4個事件的命中率，本文測試了Party Scene、Book Arrival和Johnny3個序列分別在量化參數（Quantization Parameter，QP）為28和32兩種情況下的命中率，具體測試結果如圖2所示。

圖2 事件A、B、C和D的命中率

從圖2可以發現，事件A、B、C和D的命中率一般都小于60%，只有Book Arrival和Johnny兩個序列事件A的命中率在80%～85%之間。上述實驗結果說明AVS的分割模式和H.264/AVC的分割模式并不是一一對應關系，盡管可以使用這種分割模式映射的方式加速轉碼過程，但是這會造成編碼效率降低。傳統的方法是先解碼AVS碼流，然后再使用H.264/AVC編碼器編碼，盡管該方法編碼性能好，但是編碼復雜度高，不適合實時性要求高的場合。

2 基于改進KNN算法的快速轉碼方法

為了降低AVS轉碼H.264/AVC過程的復雜度，同時保持較好的轉碼性能，本文提出了一種基于改進的K最鄰近結點算法（K-Nearest Neighbor Algorithm，KNN）[11]的快速AVS到H.264/AVC轉碼方法。所提出的方法包括兩個部分，分別為統計階段和轉碼階段。在統計階段，提取了統計幀的AVS碼流中編碼塊的分割模式及相應的運動矢量信息作為特征值，然后編碼幀的待編碼塊編碼時根據相同特征值在統計幀中尋找特征最匹配的M個模式，由于M個模式中可能存在重復，因此將M個模式中不重復的模式結合AVS碼流中的分割模式一起執行率失真優化（Rate Distortion Optimization，RDO）[12]過程，從而加速轉碼過程。

為了提高特征的有效性，本文將待轉碼幀分為統計幀和快速編碼幀兩類。選擇N幀為一個編碼組，且N幀中前L幀為統計幀，其余N-L幀為快速轉碼幀。統計幀不進行快速轉碼，先使用傳統的AVS解碼器解碼碼流再使用H.264/AVC編碼器編碼，在該過程中提取宏塊編碼采用分割模式對應的特征數據，該過程對應于圖3中的統計階段。快速編碼幀使用本文提出算法快速轉碼，首先使用AVS解碼碼流中的數據得到特征數據，然后根據該特征數據在統計幀中的特征數據中利用KNN方法尋找M個最接近的特征數據，并將其對應的統計幀中的分割模式和AVS碼流中的分割模式一起構成備選模式列表，然后該列表中每個模式執行RDO，從而避免全遍歷方式選擇最佳的分割模式。圖3是上述所述方法工作原理示意圖。

圖3 基于改進KNN算法的快速轉碼工作示意圖

2.1 特征提取

根據編碼原理可以，若某個宏塊運動越劇烈，則很可能使用較小的塊編碼，若某個宏塊運動越緩慢，則很可能使用較大的塊編碼。而宏塊的運動矢量（Motion Vector，MV）反映了當前塊的運動情況，因此，本文探索了MV與轉碼中最終使用的分割模式之間的相關性。本文選取AVS碼流中某個宏塊分為16×16、2個16×8和2個8×16分割模式時對應8×8塊之間的方差作為5個特征，并構成一維矢量Fm

式中：Vm,16×16表示16×16內4個8×8塊MV之間的方差；Um,16×8表示16×8分割中上方塊內2個8×8塊MV之間的方差；Dm,16×8表示16×8分割中下方塊內2個8×8塊MV之間的方差；Lm,8×16表示8×16分割中左方塊內2個8×8塊MV之間的方差；Rm,8×16表示8×16分割中右方塊內2個8×8塊MV之間的方差。

2.2 特征提取改進KNN算法的快速AVS到H.264/ AVC轉碼

本文提出方法根據AVS的碼流分割模式信息結合改進的KNN方法確定可能成為最佳宏塊分割模式的列表，取代原有所有模式全遍歷的方式，然后每種模式執行RDO，選擇率失真代價（Rate Distortion Cost，RDCost）最小的模式作為最佳宏塊分割模式。傳統的KNN算法根據訓練樣本集中與新樣本距離最近的K個樣本，并根據這K個樣本所屬類別判斷新樣本的屬性。本文中根據KNN算法選擇K個樣本后，并不是直接判斷其屬性，而且選擇K個樣本對應的所有屬性。

本文提出的基于改進KNN算法的快速轉碼方法的具體方法如下：

步驟1，從AVS碼流解碼一個宏塊，判斷當前幀的標號frame_poc是否為0，若是轉向步驟4，否則轉向步驟2。

步驟2，判斷當前幀的標號frame_poc是否能被N整除，若是轉向步驟6，否則轉向步驟3。

步驟3，構建特征矢量Vector2，然后在前面frame_poc能被N整除幀中所有的Vector1中利用KNN算法選擇M個與Vector2最接近的Vector1，并將M個Vector1對應的不重復模式構建最可能成為最佳宏塊分割模式的分割模式列表，具體該構建方法如下，第一個模式為AVS解碼信息中當前塊編碼使用的分割模式，隨后的所有模式根據在M個模式中占的比例由大到小排列。

步驟4，若當前幀標號frame_poc能被N整除或者等于0，則遍歷H.264/AVC所有發宏塊分割模式編碼一個宏塊，否則使用粗略分割模式列表中的模式編碼一個宏塊，選擇當前宏塊最佳的分割模式并轉向步驟5。

步驟5，判斷當前宏塊是否為最后一個宏塊，若是，則結束，否則轉向步驟1。

步驟6，構建跟Vector2具有相同屬性的特征矢量Vec?tor1，并保存，然后轉向步驟4。

3 實驗結果與分析

為了驗證本文提出算法的有效性，將它與傳統級聯式轉碼器以及文獻[8]中的算法進行對比實驗。使用的AVS參考軟件為rm52j_r1，H.264/AVC參考軟件為JM18，使用了6個不同分辨率不同場景的視頻測試序列，分別是PartyScene，Race?Horses，Johnny，FourPeople，BookArrival和Leavelaptop。在仿真實驗中，圖像編碼格式為IPPP，幀率為30 f/s（幀/秒），測試每個序列100幀。rm52j_r1參考軟件的量化參數為QP=28，最大搜索范圍為16，幀率為30 f/s，參考幀為2幀。M選取不同值時的測試結果如圖4所示。最終的實驗結果使用節省時間（Time Saving，TS）和碼率增加（DBR）兩個指標衡量算法性能，具體的計算如下

式中：Tori表示傳統級聯轉碼器所花費的時間；Tφ表示對比方法（提出的方法和文獻[8]方法）所花費的時間。

式中：Rori表示傳統級聯轉碼器的碼率；Rφ表示對比方法（提出的方法和文獻[8]方法）的碼率。

圖4 不同參數下不同序列的測試結果

從圖4a和圖4b可以發現，針對同一M，不同序列節省時間量和比特率增加量差別很大，這是由于不同序列具有不同的屬性。針對同一序列不同M的情況下，當M小于等于5時，隨著M值的增大，預測得到的備選模式列表中的模式數目增多，造成編碼復雜度增大，編碼效率也隨著增大。當M大于等于10時，盡管M值逐漸增大，但是備選模式列表中得到的不重復模式數目并沒有顯著增加，導致節省時間量和比特率增加量基本不變。

綜合考慮分類精度和轉碼復雜度，本文中N取10，M取值為5。在H.264/AVC編碼中，JM18參考軟件的量化參數（Quantization Parameter，QP）分別為24、28、32、36，最大搜索范圍為16，幀率為30 f/s，參考幀為2幀，本文提出方法與級聯方式轉碼器的對比結果以及文獻[8]方法與級聯方式轉碼器的對比結果如表1所示。

表1 測試結果

由表1實驗結果可以得出，本文提出算法與傳統級聯轉碼器算法相比，在比特率平均增加4.89%的情況下，轉碼時間降低了約56%，文獻[8]方法與傳統級聯轉碼器算法相比，在比特率平均增加18.23%的情況下，轉碼時間降低了約77%。盡管文獻[8]方法的方法能得到更好地降低轉碼過程的復雜度，但是其碼率大幅增長，使得編碼效率顯著降低。雖然本文提出算法對轉碼過程復雜度的優化程度沒有文獻[8]方法好，但是并未引起碼率顯著增加。并且本文中M是可以選擇的，當M更小時，將會導致轉碼過程的復雜度降低更多。

4 結論

由于視頻從AVS標準轉碼成H.264/AVC標準具有很大的應用前景，目前研究主要通過AVS和H.264/AVC之間模式映射的關系減少轉碼復雜度，但是這兩種標準采用技術不同會導致宏塊采用的分割模式不同，這會降低轉碼后視頻的壓縮效率。為了解決上述問題，本文提出一種粗略確定宏塊分割模式的快速轉碼方法。該方法利用AVS的碼流中宏塊分割模式，并結合改進的KNN方法確定最優可能成為最佳宏塊分割模式的列表，從而避免遍歷所有分割模式。大量的實驗結果證明，與傳統級聯方式的轉碼方法相比，本文提出的算法在比特率增加4.89%的情況下，轉碼時間降低了約56%。

盡管本文提出方法可以降低轉碼過程的復雜度，但是由于考慮的因素較少，導致模式預測并不十分準確，還可以通過考慮運動矢量大小、待編碼塊復雜度等因素進一步提高模式預測精度。

[1] TANG Q，NASIOPOULOS P.Efficient motion re-estimation with rate-distortion optimization for MPEG-2 to H.264/AVC transcod?ing[J].IEEE Trans.Circuits Syst.Video Technol.，2010，20（2）：262-274.

[2] AHMAD I，WEI X H，SUN Y，et al.Video transcoding：an over?view of various techniques and research issues[J].IEEE Trans.Circuits Syst.Video Technol.，2005，7（5）：793-804.

[3]WIEGAND T，SULLIVAN G J，BJONTEGAARD G，et al.Over?view of the H.264/AVC video coding standard[J].IEEE Trans.Circuits Syst.Video Technol.，2003，13（7）：560-576.

[4] FAN L，MA S W，WU F.Overview of AVS video standard[C]// Proc.IEEE InternationalConference on Multimedia and Expo.[S.l.]：IEEE Press，2004：423-426.

[5]SULLIVAN G J，OHM J R，HAN W J，et al.Overview of the High Efficiency Video Coding（HEVC）standard[J].IEEE Trans.Cir?cuits Syst.Video Technol.，2012，22（7）：1649-1668.

[6] YU L，YI F，DONG J，et al.Overview of AVS-video：tools，per?formance and complexity[C]//Proc.IEEE visual Communication and Image Processing.Beijing：IEEE Press，2005：12-15.

[7]WANG Z H，GAO W，ZHAO D B，et al.A fast intra mode deci?sion algorithm for AVS to H.264 transcoding[C]//Proc.IEEE Inter?national Conference on Multimedia&Expe.Toronto：IEEE Press，2006：61-64.

[8] 尚凱，張萬緒.AVS-H.264視頻轉碼快速算法[J].計算機工程，2010，36（12）：234-244.

[9] WANG Z H，JI X Y，GAO W，et al.Effective algorithms for fast transcoding of AVS to H.264/AVC in the spatial domain[J].Multi?media Tools and Applications，2007，35（2）：175-202.

[10]FERNANDEZ G，CUENCA P，BARBOSA L O，et al.Very low complexity MPEG-2 to H.264 transcoding using machine learn?ing[C]//Proc.14th Annual ACM International Conference on Mul?timedia.Santa Barbara：ACM Press，2006：931-940.

[11] ZHANG B.Reliable classification of vehicle types based on cas?cade classifier ensembles[J].IEEE Trans.Intelligent Transporta?tion Systems，2013，14（1）：322-332.

[12] SULLIVAN G J，WIEGAND T.Rate-distortion optimization for video compression[J].IEEE Signal Process Magazine，1998，15（6）：74-90.

Fast Transcoding From AVS to H.264/AVC Based on Improved KNN

SHEN Hao1，2
（1.Shanghai Jiao Tong University，Shanghai 200240，China；2.Shanghai Branch of China Southern Airlines，Shanghai 201202，China）

Although the encoding performance of Audio and Video Coding Standard（AVS）can be comparable to H.264/AVC，H.264/AVC has more extensive applications.So the transcoding from AVS to H.264/AVC has great application prospects.Recently，the mainstream transcoding methods reduce the complexity according to the mode mapping method between AVS and H.264/AVC.But for the different techniques between the two standards，the one-to-one mapping of modes is impossible，thus causing a significant reduction in the encoding efficiency.A fast mapping algorithm based on improved KNN is proposed in this paper，which makes full use of various information of AVS bitstream.And the possible mapping mode can be determined adaptively when utilize the motion vector information of AVS.Experimental results show that the above issues are effectively addressed.Large numbers of experimentalresultsshow thatthe proposed method significantly reducesthe transcoding complexity underthe permission of transcoding efficiency decrease.

AVS；H.264/AVC；fast transcode；K-nearest neighbor algorithm

TN919.81

A

10.16280/j.videoe.2015.08.009

沈 皓（1987—），碩士生，主要研究方向為視頻的編碼與轉碼。責任編輯：時 雯

2014-07-22

【本文獻信息】沈皓.基于改進KNN算法的AVS到H.264/AVC快速轉碼方法[J].電視技術，2015，39（8）.