H.264中基于参考帧提前截止的快速运动搜索算法.doc

H.264中基于参考帧提前截止的快速运动搜索算法　　摘要在高性能视频编解码算法H.264中，运动搜索过程是计算复杂度最密集的部分，也是影响系统实时性能的瓶颈针对这一问题，文中提出一种基于参考帧提前截止的全局判决方法，即在运动搜索中和整数余弦变换前进行准全零块判决实验结果表明，在图像质量基本不变和码率不增加的情况下，该方法可以大幅度减少运动搜索过程的计算量　　关键词视频编解码；运动搜索；绝对误差和；提前截止　　远距离音视频同步交互是多媒体技术应用和发展的一个重要方向和趋势，而这其中的一个关键技术就是视频压缩技术H.264/AV是由IS/IEPEG(运动图像专家组)和ITU-TVPEG(视频编码专家组)组成的JVT(联合视频专家组)制定的一项视频压缩技术标准，它使得运动图像压缩技术上升到了一个更高的阶段在较低带宽上提供高质量的视频传输服务是H.264/AV应用亮点，在同样的视觉质量前提下，比H.263和PEG-4节约了50%的码率[1]，而且对IP和无线网络传输具有更好的支持功能原因是引入了当前视频编码中的许多新技术，包括多种宏块分割模式、多参考症4×4整数变换等新技术的使用使H.264获得优越的性能，但同时也使其复杂度大幅度增加，严重限制了H.264在实时要求下的应用。

其中，大部分的编码时间都集中在运动搜索上[2]，因此，要降低编码器的复杂度，首先要对运动搜索算法进行优化　　在视频、视频会议等低比特率的视频应用中，图像序列往往是运动平缓、背景静止的头肩序列这些序列经运动补偿后残差的绝对值一般都很小，再经过DT变换和量化后很容易成为全零块如果能提前预测出这些准全零块，就可以节约大量的编码时间本文根据H.264中采用的4×4整数DT变换和量化的原理，给出了准全零块的检测条件，然后通过运动搜索的中间值SAD，将检测条件与搜索算法有机结合在一起，有效提高了编码效率　　为了解决以往视频编码标准中DT正反变换的失配问题，H.264中采用了基于4×4子块的整数DT变换，其正向变换公式[3]为：　　（1）　　其中，X是4×4块残差信号；是二维DT的变换核，通过加减法和移位运算就能完成；Q称为正变换尺度调整矩阵；符号⊕表示中的每个元素乘以矩阵Q中对应位置上的系数值的运算；正变换矩阵f定义为：　　（2）　　H.264采用标量量化技术，将每个图像样点编码映射成较小的数值，并灵活地使用计算技巧，避免了除法和浮点运算具体的量化过程的运算为：　　（3）　　其中，ij为的系数，f是一个修正参数，对于帧内编码宏块取2qbits/3，对于帧间编码宏块取2qbits/6。

倍增因子F在不同位置的取值为：　　（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）中，的系数ij可以表述为：　　（5）　　其中，iu为jv的系数f，残差矩阵的系数为Xuv　　根据三角不等式的特点，对上式进行变形，可得：　　（6）　　又由正变换矩阵f的定义，在不同位置的最大值归纳如下：　　（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三种亚宏块。

在运动搜索过程中，匹配搜索算法需要在每一种块模式中展开，若能及时确定宏块分割模式，模式选择的开销也必然会降低　　图17种宏块分割模式　　考虑到多种宏块编码模式，结合4×4块检测门限的定义，得出适合于各种块模式的门限如下：　　（12）　　其中,N=4、8或16，B×N是×N块中4×4块的个数，a2为r=2时a的取值在判决公式（10）给定的情况下，自适应门限值会随着量化参数、F、β和块模式的改变而改变，当与运动搜索算法结合使用时，只需在匹配搜索过程中，将门限作为停止搜索的条件，其间用到的SAD由于是运动搜索的中间结果，对它的调用并不会增加编码器的复杂性　　基于以上分析，运动搜索的提前中止算法为：对于一种块模式×N，计算其包含的每一个4×4块的值，得到自适应门限T×N后，将其与当前块的SAD进行比较，若SAD小于该门限，确定最匹配的运动矢量和块模式，同时跳出当前块的运动搜索；否则，记录当前的最佳矢量和块模式，并执行下一模式的搜索　　实验采用J9.0测试模型，选取了四种有代表性的QIF序列（①issa，②therDaughter，③Silent和④Fran），其中，Fran的运动最为剧烈，且人物和镜头都在晃动；Silent的背景纹理复杂度最高，运动复杂度一般：issa和therDaughter（简称：D）中人物运动幅度较平缓，issa的背景纹理最不明显。

为了测试结果的准确性，各序列均取其前150郑主要的编码参数设置如下：搜索范围为16，5个参考帧，帧率为30帧/秒，编码结构为I,AVL熵编码，Hadaard变换，率失真优化(RD)和快速全运动搜索(FFS)算法　　表1　　表1通过比较FFS和基于全零块检测的运动搜索算法(AZBS)的运行时间，给出了运用AZBS后计算复杂度下降的百分比(单位：%)由表中数据可知，随着QP的增加，各个序列计算复杂度下降的百分比也在增加，原因在于自适应门限值门限值越大，运动搜索中止的越早，运行时间越短对于运动剧烈的视频序列，其计算复杂度在QP为48时下降约71%；对于背景纹理复杂的序列，当QP值大于23时，其计算复杂度下降的幅度几乎不受其纹理的影响，而对于运动幅度较小的序列，其复杂度下降的平均值为58%，最多可达82%～90%　　表2　　测试指标采用峰值信噪比(PSNR)和比特率(BitRate)表2为两种算法相比四幅序列的PSNR和比特率的变化量(负号表示降低)，ΔP(单位：dB)表示PSNR的变化，ΔB表示比特率变化的百分比从表中可以看出，对实验中的视频序列，基于参考帧提前截止的运动搜索算法对PSNR和比特率影响很小，且出现了少数信噪比不变或略有上升和比特率下降的情况，可见，该算法代价很小，对图像质量几乎没有影响。

　　本文创新点在于通过对H.264中整数DT变换和量化的理论分析，推导了基于4×4块的运动搜索提前截止检测门限，并将其进行扩展，使其适应7种块模式，然后以运动搜索的中间结果SAD为桥梁，将判决门限与运动搜索算法结合起来，得出运动搜索的提前截止条件实验证明，在峰值信噪比和比特率基本不变的情况下，基于参考帧提前截止的运动搜索算法可以有效降低运动搜索的复杂度　　[1]Tiegand,GSullivan．GBjntegaard,ALuthravervieftheH.264/AVVidedingStandard[J]IEEETransatinsniruitsandSystesfrVideTehnlgy．2003,13(7)560-576　　[2]毕厚华．新一代视频压缩编码标准—H1264/AV[]1．北京：人民邮电出版社.2005　　[3]YgHn．GyuYengKi,Jea-HKiAniprvedearlydetetinalgrithfrall-zerblksinH264-videennding[J]IEEETransatinsniruitsandSystesfrVideTehnlgy．2005,15(8)1053-1057　　[4]Tiegand,GSullivan,GBjntegaard,ALuthra.vervieftheH.264/AVVidedingStandard[J].IEEETransatinsniruitsandSystesfrVideTehnlgy,2003,13(7):560-576　　[5]YngHn,GyuYengKi,JaeHKi.Aniprvedearlydetetinalgrithfrall-zerblksinH.264videending[J].IEEETransatinsniruitsandSystesfrVideTehnlgy，2005,15(8):10531057　　[6]毕厚杰，新一代视频压缩编码标准—H1264/AV[]1北京：人民邮电出版社，2005。