AVS编码算法全搜索方案优化

郭玉洁，刘彦隆，张 刚

（太原理工大学 信息工程学院，山西 太原 030024）

运动估计与运动补偿是视频编码中一个重要的组成部分。利用该技术可以有效去除视频序列相邻帧存在的时间冗余，极大地降低传输的码率，提高编码效率。块匹配运动估计算法是目前应用最广泛的一种运动估计算法。最基本的块匹配的算法是全搜索（Full Search，FS）算法，通过对搜索范围内所有点进行搜索从而得到最佳匹配点，全搜索算法有描述语言简单、在硬件上容易实现的特点，所以改进全搜索是最基本、对硬件实现有实际的指导意义。在整个视频处理的过程中，98%以上的计算时间被运动估计占用，所以改进运动矢量的搜索对视频处理有极大的意义。时间、码率、信噪比是视频压缩的主要指标，减少时间、降低码率、增强信噪比是每种改进算法的目标。

1 传统全搜索算法

传统全搜索算法先分别计算目标宏块与mvp和（0，0）点所对应的参考宏块的代价值，选二者中较小代价值的为搜索对象，在扩展range=32个像素范围内搜索。在搜索范围内先以16×16模式在前两个恢复帧中搜索出代价值较小的一帧做为整个宏块的参考帧，然后在确定的参考帧中搜索其余模式（顺序为8×8，16×8，8×16以及帧内模式）。在确定8×8模式代价值后与16×16模式代价值比较，若高于16×16模式代价值则结束搜索；否则抛弃16×16模式继续搜索16×8和8×16模式，根据最小代价值原则确定该宏块最佳搜索模式。

一般在码率相同情况下全搜索方案可以获得最好的信噪比，但是计算复杂性太高导致帧率降低。一些改进的搜索算法不做全搜索，针对特定情况设计特殊搜索路径以便缩小搜索范围，但是不具有通用性。降低全搜索方案计算复杂性主要采用两种措施：只搜索16×16模式或缩小各个搜索区域尺寸，对于大多视频序列这种全搜索的改进方案将会导致信噪比下降和码率增高的现象。事实上，基于块匹配原理的各种不同搜索模式所包含的相关性信息有着紧密的关联性，但是传统全搜索方案没有充分利用不同模式搜索结果中蕴含的图像相似性信息来降低计算复杂性。本文提出一种新的全搜索方案，其信噪比和码率与传统全搜索方案具有相同的水平，但计算复杂性仅略高于16×16搜索模式。

2 SMS全搜索方案

本论文提出一种新的基于子模式拼接（Sub-Model Stitching，SMS）的高效运动矢量全搜索方案，充分利用既有搜索模式的代价值和位置信息，通过子模式拼接来确定后续搜索模式和缩小搜索范围，把全搜索的计算量降低到相当于只作16×16模式搜索。由于SMS算法包括了所有模式的更加精细搜索，在处理运动剧烈的视频序列时有较好效果。SMS基本流程如图1所示。

图1 SMS搜索流程

2.1 SMS方案的搜索流程

SMS的基本流程是：先在两个恢复帧中搜索8×8模式得到 4 个最佳匹配子宏块和相应的mv={mv0（i0），...，mv3（i3）}，其中ik=0或ik=1，k=0，1，2，3是参考的恢复帧索引值，并用它们指导后续模式的搜索。若相应的4个恢复帧索引值有3个以上相同，则将其定为唯一的参考帧，否则确定2个参考帧。确定参考帧后，若是唯一的参考帧且含有3个以上相邻mv，则将这4个子宏块直接拼接生成一个16×16的最佳模式，并且不进行其余模式的搜索；若不存在3个以上相邻的mv或者参考帧不唯一，则在一个参考帧或两个参考帧中进行判断：是否有2个相邻的8×8子宏块可以拼接组合成为一个16×8（或8×16）块；如果有则完成拼接并且只在包含该块的小范围内进行相应16×16最佳模式的搜索；如果没有则在4个8×8块的mv周围扩展进行小范围16×16最佳模式的搜索。将搜索的16×16最佳模式代价值与综合后的8×8最佳模式代价值进行比较并确定16×16最佳模式是否为最终模式，若是则搜索过程结束；否则进行16×8（或8×16）模式搜索，此时若在4个mv中可以进行拼接组合则实现拼接并作如下判别，如果存在一组16×8拼接，判断是否存在另一组16×8拼接；如存在另一组16×8拼接则实现拼接并终止搜索，以16×8为候选模式；否则不存在另一组16×8拼接，在余下的2个8×8块周围扩展成16×8块进行搜索，并且不进行8×16模式搜索。如果不存在一组16×8拼接则按上述原则进行8×16模式的处理。若不存在任何可以拼接的情况，4个8×8块的mv周围扩展分别进行16×8模式和8×16模式的搜索，最后比较它们的代价值确定此宏块的最佳模式。

当存在可拼接模式时，前期搜索结果蕴含了图像之间的相关性，表明当前搜索的图像块成为最佳模式的概率大大提升，在此周围扩展搜索的范围可以大大减少。有关搜索范围的讨论将在下文涉及。

2.2 模式的可拼接性

传统全搜索方案中所有宏块必需经过8×8模式和16×16模式的搜索，大部分模块要经过16×8模式或8×16模式搜索。所以若能不经搜索便直接确定这些模式的mv和参考索引，则可以大量节约搜索时间。表1是对新的全搜索方案拼接组合成功比率的测试结果，选取AVS官网提供的5个视频序列，其中cif格式有Foreman，Chil⁃dren和Football，D1格式有Ice和Soccer。

表1的每个模式项下，总数是经过该模式搜索的宏块数目，命中数目指的是可以进行拼接的宏块数目。由表1可知经过8×8模式搜索之后，除了运动较为剧烈的Football码流之外，其余序列可以直接拼接组合生成16×16模式的宏块占比超过60%以上，剩余的宏块中有48%～70%可以经过组合拼接成为16×8块或8×16块，不经搜索直接与其他模式代价值比较。由此可知，新算法主要通过拼接组合而不是搜索获得最佳模式，可以大大降低计算复杂性。

表1 新全搜索方案拼接组合命中率

2.3 确定搜索范围

进行8×8模式搜索后，SMS的mv值所对应的像素块最有可能包含在最佳模式中，因此在其周围区域搜索其余模式，搜索范围可以相应地缩小。在传统全搜索算法中加入测试语句，记录各模式最佳搜索结果的mv与8×8模式mv之间的距离，以其距8×8模式的4个mv中最小者为准。以8×8模式的mv为中心作圆使其覆盖其他各个模式的mv，半径分别取102，82和5 2进行统计，考查不同半径覆盖圆的覆盖效率。取5个cif格式的视频序列，测试结果如表2所示。

表2 覆盖率对比

由表2可知，半径为5的覆盖率不到80%，搜索范围过小；半径为10的覆盖率虽然较理想，但10不是2的整数次幂，不利于硬件实现；半径为8的搜索范围比较合适，运动最快的图像序列也有87.2%的覆盖率，一般的图像序列平均覆盖率在95%左右。由于程序可实现的搜索范围是矩形的，所以将半径为82改为上下左右扩展8个像素点的范围进行测试，结果如表3所示。

表3 覆盖率对比

矩形搜索的覆盖率并没有大幅降低，权衡处理速度和搜索精度后将16×16模式、16×8模式、8×16模式的搜索范围定为在8×8模式的mv上下左右扩展8像素比较合理。

确定8×8模式的搜索范围是range=32和range=16，即对原始数据上下左右都扩展16和32，主要考察其对PSNR、码率和帧率3个参数的影响。表4是新的全搜索方案对搜索范围的测试结果，其中范围①和②分别是range=16和range=32，在进行其余模式搜索时均采用上下左右扩展8像素。

表4 8×8模式搜索范围

由表4的实验数据可知，对于新的全搜索算法，搜索范围①比范围②的PSNR和帧率都高且码率小，因此将全搜索新算法的8×8模式搜索范围定为上下左右扩展16个像素。

3 实验与结果

测试的4个全搜索方案分别是原全搜索方案、原方案1（上下左右扩展32像素，仅16×16搜索）、原方案2（上下左右扩展16像素，仅16×16搜索）和SMS搜索方案。新的全搜索方案中8×8模式的搜索范围为扩展16像素。实验程序用pentium（R）Dull-wre cpu处理器，型号是E5500，主频2.80 GHz，内存2 Gbyte。测试序列采用IPPPP…结构，测试结果列在表5～表8中。

表5 PSNR对比dB

表6 帧率对比f/s

表7 码率对比kbit/s

表8 帧内模式比例%

由表5～表7可知，新搜索方案的PSNR与原搜索方案基本保持一致，表明图像质量保持不变；仅16×16搜索的两个原方案出现PSNR下降的现象，尤其是对运动剧烈的视频序列PSNR下降尤为明显，原因是仅作16×16搜索对图像细节描述粗糙。在帧率方面，原全搜索方案由于搜索模式多、范围大所以搜索时间长、帧率低；新全搜索方案通增加模式拼接，比较原全搜索算法帧率大大提升，几乎能够达到仅16×16搜索的原方案水平。新全搜索与原全搜索两种算法的PSNR和码率基本相同，而仅作16×16搜索的原方案，对运动剧烈的视频序列码率相对较低，而对运动稍微平缓的视频序列码率反而要高，原因是缺少16×8、8×16和8×8模式的精细描述，导致帧内模式比例提高，详见表8。

由上述各表可知，新的全搜索方案与原方案比较，码率基本没有变化，PSNR基本保持不变，帧率提升300%左右，与原方案2的处理速度相当。可见新的全搜索方案码率得到提升，对cif序列和D1序列都有效。

4 结束语

本文将AVS帧间运动矢量搜索算法采用模式拼接新的理念在C语言程序实现。新全搜索方案可以处理cif（352×288）、D1（704×576）的4∶2∶0的视频图像，对视频序列的处理在帧率有大幅提升。本论文的研究内容对AVS帧间运动矢量搜索算法的实现有着实际的参考价值。

：

[1]毕厚杰.视频压缩编码标准——H.264/AVC[M].北京：人民邮电出版社，2005.

[2]肖敏连.一种快速整像素运动估计算法研究[J].湖南人文科技学院学报，2011（10）：129-141.

[3]张子敬，张志华，霍家道.基于运动矢量分散度的增强型MVFAST搜索算法[J].科学技术与工程，2012（12）：9216-9220.

[4]王荃，鲍卫兵，张永智.搜索模式自适应快速运动估计算法[J].电视技术，2009，33（7）：16-17.

[5]包国兴，谌德荣，胡宏华，等.一种快速H.264帧间模式选择算法[J].博士论坛，2010（26）：1-2.

[6]刘海华，雷奕，谢长生.基于块匹配的运动估计搜索算法研究与实现[J].计算机应用，2006（6）：1354-1356.

[7]AVS工作组.GB/T20090.2—2006，信息技术先进音视频编码第二部分：视频[S].北京：中国标准化出版社，2006.