基于改进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）.