摘 要 在高性能视频编解码算法H.264中，运动搜索过程是计算复杂度最密集的部分，也是影响系统实时性能的瓶颈。针对这一问题，文中提出一种基于参考帧提前截止的全局判决方法，即在运动搜索中和整数余弦变换前进行准全零块判决。实验结果表明，在图像质量基本不变和码率不增加的情况下，该方法可以大幅度减少运动搜索过程的计算量。
1引言
远距离音视频同步交互是多媒体技术应用和发展的一个重要方向和趋势，而这其中的一个关键技术就是视频压缩技术。H.264/AVC是由ISO/IEC MPEG(运动图像专家组) 和ITU-T VPEG(视频编码专家组)组成的JVT( 联合视频专家组) 制定的一项视频压缩技术标准，它使得运动图像压缩技术上升到了一个更高的阶段。在较低带宽上提供高质量的视频传输服务是H.264/AVC应用亮点，在同样的视觉质量前提下，比H.263和MPEG-4节约了50%的码率[1]，而且对IP和无线网络传输具有更好的支持功能。原因是引入了当前视频编码中的许多新技术，包括多种宏块分割模式、多参考帧、4×4整数变换等。新技术的使用使H.264获得优越的性能，但同时也使其复杂度大幅度增加，严重限制了H.264在实时要求下的应用。其中，大部分的编码时间都集中在运动搜索上，因此，要降低编码器的复杂度，首先要对运动搜索算法进行优化。
在视频电话、视频会议等低比特率的视频应用中，图像序列往往是运动平缓、背景静止的头肩序列。这些序列经运动补偿后残差的绝对值一般都很小，再经过DCT变换和量化后很容易成为全零块。如果能提前预测出这些准全零块，就可以节约大量的编码时间。本文根据H.264中采用的4×4整数DCT变换和量化的原理，给出了准全零块的检测条件，然后通过运动搜索的中间值SAD，将检测条件与搜索算法有机结合在一起，有效提高了编码效率。
2 H.264的运动搜索结果在DCT变换和量化中的变换过程
为了解决以往视频编码标准中DCT正反变换的失配问题，H.264中采用了基于4×4子块的整数DCT变换，其正向变换公式为：
（1）
其中，X是 4×4块残差信号；W 是二维DCT的变换核，通过加减法和移位运算就能完成；Q称为正变换尺度调整矩阵；符号⊕ 表示W中的每个元素乘以矩阵Q中对应位置上的系数值的运算；正变换矩阵Cf定义为：
（2）
H.264采用标量量化技术，将每个图像样点编码映射成较小的数值，并灵活地使用计算技巧，避免了除法和浮点运算。具体的量化过程的运算为：
（3）
其中，Wij 为W的系数，f是一个修正参数，对于帧内编码宏块取2qbits/3，对于帧间编码宏块取2qbits/6。倍增因子MF在不同位置的取值为：
（4）
当r =0时，(i, j) = {(0, 0)，(0, 2)，(2, 0)，( 2, 2) }；
当r =1时，(i , j) = {(0, 1)，(0, 3)，(1, 0)，(1, 2)，(2, 1)，(2, 3)，(3, 0)，(3, 2)}；
当r =2时，(i, j) ={(1, 1)，(1, 3)，(3, 1)，(3, 3) }。
在量化过程中，量化参数QP共有52个值。当QP取最大值51时，表示最粗糙的量化，当取最小值0时，代表最精细的量化。在实际应用中，可以根据需要在0～51范围内灵活选择。从量化公式可以看出，H.264中的量化为整数运算，并且避免了使用除法，确保用16位算法来处理数据，实现了最小的运算复杂度。
3 基于参考帧提前截止的运动搜索算法
运动搜索是找出当前宏块在参考图像中最匹配位置的过程，即在指定的搜索路径中寻找最匹配的运动矢量。在所有的匹配搜索算法中，全局搜索法可以得到最佳的匹配结果，但计算量很大。由于视频序列的时间相关性远大于其空间相关性，若被编码宏块相对静止或仅有小范围内的平动，经过运动补偿所得到的残差信号通常比较小，再经整数变换和量化后将成为全零，在这种情况下，继续进行搜索必将浪费大量的时间。基于此，在运动搜索的过程中设置适当的门限，这样，量化后成为全零的宏块将被提前检测出来，最匹配的运动矢量便为小于该门限的第一个矢量。下面通过推导给出全零块的检测门限。
在公式（3）中，W的系数Wij 可以表述为：
（5）
其中，Ciu为Cjv的系数Cf，残差矩阵的系数为Xuv。
根据三角不等式的特点，对上式进行变形，可得：
（6）
又由正变换矩阵Cf的定义，在不同位置的最大值归纳
（7）
将（6）式中不等号右边的式子展开，并代入（7）式的结果，得到该部分的最大值：
（8）
其中，
根据以上各分支的推导，（3）式中量化值的上限为：
（9）
在（9）式中， 恰好为4×4块的绝对差和SAD4×4，如果的上限小于1,则当前的4×4块为全零块，即全零块必定满足下面的条件：
（10）
通过分析（4）、（9）和（10）式，可知r取不同值时，门限Tr和量化值的关系
（11）
由于和Tr都是r的函数，r发生变化，两者的关系也在相应的改变，Tr有三种取值状态，当Tr取T0或T1时，或r = 0, 1位置的量化值为零，即r = 1, 2
或r = 2时的值不定，为了使 在所有位置上取值为零，将T2作为4×4块的检测门限。
另外，如图1所示，其中宏块按照四种方式分割，即16×16、8×16、16×8和8×8，8×8模式还可以继续分解为4×8、8×4和4×4三种亚宏块。在运动搜索过程中，匹配搜索算法需要在每一种块模式中展开，若能及时确定宏块分割模式，模式选择的开销也必然会降低。
图1 7种宏块分割模式
考虑到多种宏块编码模式，结合4×4块检测门限的定义，得出适合于各种块模式的门限
（12）
其中M, N= 4、8或16，BM×N是M×N 块中4×4块的个数，a2为r = 2时a的取值。在判决公式（10）给定的情况下，自适应门限值会随着量化参数、MF、βW和块模式的改变而改变，当与运动搜索算法结合使用时，只需在匹配搜索过程中，将门限作为停止搜索的条件，其间用到的SAD由于是运动搜索的中间结果，对它的调用并不会增加编码器的复杂性。
基于以上分析，运动搜索的提前中止算法为：对于一种块模式M×N，计算其包含的每一个4×4块的值，得到自适应门限TM×N后，将其与当前块的SAD进行比较，若 SAD小于该门限，确定最匹配的运动矢量和块模式，同时跳出当前块的运动搜索；否则，记录当前的最佳矢量和块模式，并执行下一模式的搜索。
4 实验结果
实验采用JM9.0测试模型，选取了四种有代表性的QCIF序列（①Miss am，②Mother & Daughter，③Silent和④Forman），其中，Forman的运动最为剧烈，且人物和镜头都在晃动；Silent的背景纹理复杂度最高，运动复杂度一般：Miss am和 Mother & Daughter （简称：M&D）中人物运动幅度较平缓，Miss am 的背景纹理最不明显。为了测试结果的准确性，各序列均取其前150帧。主要的编码参数设置搜索范围为16，5个参考帧，帧率为30帧/秒，编码结构为I, CAVLC熵编码，Hadamard变换，率失真优化(RDO)和快速全运动搜索(FFMS)算法。
表1
表1通过比较FFMS和基于全零块检测的运动搜索算法(AZBMS)的运行时间，给出了运用AZBMS后计算复杂度下降的百分比(单位：% )。由表中数据可知，随着QP的增加，各个序列计算复杂度下降的百分比也在增加，原因在于自适应门限值 门限值越大，运动搜索中止的越早，运行时间越短。对于运动剧烈的视频序列，其计算复杂度在QP为48时下降约71% ；对于背景纹理复杂的序列，当QP值大于23时，其计算复杂度下降的幅度几乎不受其纹理的影响，而对于运动幅度较小的序列，其复杂度下降的平均值为58%，最多可达82% ～90%。
表2
测试指标采用峰值信噪比(PSNR)和比特率(Bit Rate)。表2为两种算法相比四幅序列的PSNR和比特率的变化量(负号表示降低)，ΔP(单位：dB)表示PSNR 的变化，ΔB表示比特率变化的百分比。从表中可以看出，对实验中的视频序列，基于参考帧提前截止的运动搜索算法对PSNR 和比特率影响很小，且出现了少数信噪比不变或略有上升和比特率下降的情况，可见，该算法代价很小，对图像质量几乎没有影响。
5 结论
本文创新点在于通过对H.264中整数DCT变换和量化的理论分析，推导了基于4×4块的运动搜索提前截止检测门限，并将其进行扩展，使其适应7种块模式，然后以运动搜索的中间结果SAD为桥梁，将判决门限与运动搜索算法结合起来，得出运动搜索的提前截止条件。实验证明，在峰值信噪比和比特率基本不变的情况下，基于参考帧提前截止的运动搜索算法可以有效降低运动搜索的复杂度。
参考文献
[1] T Wiegand, G Sullivan．G Bjontegaard, A Luthra Overview of the H.264 / AVC Video Coding Standard [J] IEEE Transactions on Circuits and Systems for Video Technology．2003, 13(7) 560-576
毕厚华．新一代视频压缩编码标准—H1264/ AVC[M]1．北京：人民邮电出版社.2005
Yoog Ho Moon．Gyu Yeong Kim, Jea-Ho Kim An improved early detection algorithm for all-zero blocks in H264-video enconding [J] I EE E Transactions on Circuits and Systems for Video Technology．2005 , 15(8) 1053-1057
T Wiegand, G Sullivan, G Bjontegaard, A Luthra. Overview of the H.264 / AVC Video Coding Standard [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2003, 13(7): 560-576
Yong Ho Moon, Gyu Yeong Kim, Jae Ho Kim. An improved early detection algorithm for all-zero blocks in H.264 video encoding [ J ] . I EE E Transactions on Circuits and Systems f or Video Technology， 2005 , 15 (8) :1053 1057
毕厚杰，新一代视频压缩编码标准—H1264/ AVC[M]1 北京：人民邮电出版社，2005
