沈 皓

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

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

沈 皓1，2

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

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

音視頻編碼標準；H.264/AVC；快速轉(zhuǎn)碼；K最鄰近結(jié)點算法

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

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

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

1 AVS到H.264/AVC轉(zhuǎn)碼分析及動機

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

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

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

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個序列分別在量化參數(shù)（Quantization Parameter，QP）為28和32兩種情況下的命中率，具體測試結(jié)果如圖2所示。

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

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

2 基于改進KNN算法的快速轉(zhuǎn)碼方法

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

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

圖3 基于改進KNN算法的快速轉(zhuǎn)碼工作示意圖

2.1 特征提取

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

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

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

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

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

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

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

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

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

步驟5，判斷當前宏塊是否為最后一個宏塊，若是，則結(jié)束，否則轉(zhuǎn)向步驟1。

步驟6，構(gòu)建跟Vector2具有相同屬性的特征矢量Vec?tor1，并保存，然后轉(zhuǎn)向步驟4。

3 實驗結(jié)果與分析

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

式中：Tori表示傳統(tǒng)級聯(lián)轉(zhuǎn)碼器所花費的時間；Tφ表示對比方法（提出的方法和文獻[8]方法）所花費的時間。

式中：Rori表示傳統(tǒng)級聯(lián)轉(zhuǎn)碼器的碼率；Rφ表示對比方法（提出的方法和文獻[8]方法）的碼率。

圖4 不同參數(shù)下不同序列的測試結(jié)果

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

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

表1 測試結(jié)果

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

4 結(jié)論

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

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

[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視頻轉(zhuǎn)碼快速算法[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—），碩士生，主要研究方向為視頻的編碼與轉(zhuǎn)碼。責任編輯：時 雯

2014-07-22

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