面向视频会议的运动估计快速算法

李 群

（北海舰队指挥所 山东 266000 ）

0 引言

在各种网络应用中，视频会议因其便捷高效且节减费用，成为网络的主要业务之一。目前，大多视频会议系统采纳新一代视频压缩标准H.264/AVC。然而，该标准的运动估计模块复杂度较高，对视频会议的实时性能产生不利影响。本文着重分析运动估计模块的计算方法。通过采用积分图像，在保证视频编码质量的前提下，大幅减少运动估计模块的计算量，从而有效改善视频会议的实时性能。

1 运动估计

H.264/AVC为了提高运动估计的精度，提出了一套较为复杂的运动估计算法，包括可变块尺寸和多参考帧等技术[1]。可变块尺寸包括从标准16x16像素到可变8x8像素等4种不同尺寸，当采用8x8模式时还可采用8x4、4x8、4x4像素3种尺寸。在理想状况下，当前帧宏块的运动估计需要在所有参考帧上针对所有块尺寸组合进行搜索窗口内的匹配计算。当前帧与参考帧最匹配块之间的矢量即为当前帧宏块的运动矢量。这种全搜索方案虽然可提供最优运动矢量估计，但是其运算量巨大。例如，在搜索窗口为32像素时，若仅有一幅参考帧，则全搜索运动估计的运算量占视频编码总体的60%。由此可见，优化运动估计算法是提高H.264/AVC整体性能的关键技术。

目前，有大量文献针对运动估计这一问题展开研究，其方法大致可以分为两类。第一类方法着重有效降低块匹配的数量，其中最流行的方法是由参考模型JM推荐的非对称十字型多层次六边形格点运动搜索算法[2][3]（简称UMHexagonS算法）。第二类方法则强调从运动估计模块框架入手，改善其计算效率。本文提出的基于积分图像的运动估计快速算法与以上两类方法有所不同，该方法着重于提高每一次匹配过程的计算效率，从而提高运动估计模块的效率。

2 基于积分图像的运动估计快速算法

2.1 积分图像

积分图像是一种原始图像的表示方法，可以快速处理图像。积分图像上(x,y)位置的值是原始图像左上角至坐标(x,y)的矩形内所有像素的灰度值之和，如图1(a)所示。在图像处理过程中，任意尺寸矩形块内的像素灰度值总和，都可以通过四个顶点所在位置的积分图像数值获得，如图1(b)所示。积分图像表示法被广泛的运用于图像相关的处理中。通过积分图像的预计算过程，可以有效提高相关算法效率[4][5]。

图1 a：积分图示意图；b：积分图的使用

积分图像所提供的块内快速求和功能，对改进视频压缩的宏块运动估计同样有效。但是，积分图像的求和是一个渐进累加的过程。从图像左上位置开始，逐行扫描求和，直至图像右下位置结束。随着求和数量的增加，即使采用长整型存储，仍然存在图像右下位置附近的像素面临数值溢出问题。因此，本文针对宏块的最小组成单位——单元块（4x4像素）进行求和预计算，将降低匹配过程的计算量，同时可避免由积分图像造成的数值溢出问题。

2.2 块匹配与绝对差值和

H.264/AVC的运动估计模块包括三项主要技术：宏块尺寸的选择、块匹配以及运动矢量的搜索策略。其中，块匹配是衡量当前帧宏块与对应的参考帧宏块之间的相似度，其运算结果是搜索运动矢量的依据。目前，ITU/ISO推荐使用绝对误差和SAD衡量最佳块匹配，该相似度指标也是目前应用最广泛的方法。绝对误差和SAD的计算公式为：

其中，（i,j）为待匹配宏块内所有像素的坐标位置，Diff（i,j）=Icur（i,j）-Iref（i,j），Icur为当前帧，Iref为参考帧。假设宏块的尺寸为m×n，由公式(1)可知，每一次SAD需要m×n次减法操作和m×n次取绝对值操作。对于H.264/AVC的可变块尺寸和多参考帧等特性而言，SAD被大量调用，无疑会带来整体性能的下降。本文提出一种新的度量块匹配相似度的指标，旨在降低每一次匹配操作的运算量。

2.3 运动估计快速算法

本文所提出的运动估计快速算法受积分图像方法的启发，将运动估计模块中大量重复运行的求和运算通过预处理方式，预先计算并存储。在运动估计的块匹配过程中，读取并重用预计算的求和结果，从而实现运动估计的快速计算。

由H.264/AVC支持的宏块类型可知，所有宏块均由若干相邻的4x4块组成,以此作为宏块匹配的最小单元，则用于衡量宏块匹配度的运算量将大大降低。本文将每一个4x4块称作“单元块”。由此，像素级块匹配的相似度指标SAD被单元块级所替换。其计算公式为：

根据本文所定义的相似度指标SADnew，结合积分图像方法，可采取如下算法流程进行快速运动估计：

（1）对参考帧Iref进行预处理，生成同样尺寸的图像Bref。图像Bref每个坐标位置的像素值定义为：以该坐标位置为左上角的4x4矩形内像素值的总和。该图像的数值类型可用short 类型来表示。

（2）对当前帧Icur（即需要进行运动估计的帧）进行预处理，生成1/4降采样尺寸的图像Bcur。对每个需要进行运动预测的16x16矩形块，分割成4个单元块。图像Bcur每个坐标位置的像素值为对应单元块的像素总和。

（3）根据宏块可变块尺寸的不同方式，针对步骤2生成的当前帧的备选宏块，在步骤1生成的参考帧Bref上进行运动矢量搜索。运动矢量搜索可以采用任何已有方式。

（4）度量备选宏块在参考帧上的块匹配相似度，使用公式2所给出的单元块级相似度指标SADnew。

在算法流程中，步骤1及步骤2采纳了积分图像方法，通过预计算的策略，将一次块匹配相似度度量的计算量降低。SADnew所需减法操作和取绝对值操作分别减少为原始SAD所需操作数量的1/16。实验结果表明，该算法可以在保证视频编码质量的前提下，显著提高视频压缩的运算效率。

3 实验结果

本小节测试在同一量化因子情况下，采用不同的运动搜索策略时，本文算法性能。针对Stefan测试序列，比较SADnew算法与SAD算法的性能，包括编码质量与处理速度。运动搜索策略包括3种：FS（全搜索）、UMHEX（非均匀多六边形网格搜索）和EPZS（改进的预测式区域搜索），其中后二者为JM推荐方法。量化因子取值为28。

表1和表2给出了相关数据表，性能对比对象为视频编码质量PSNR和运动估计算法的运行时间。数据显示本文提出的算法在计算性能上明显优于原始算法，在编码质量上略有损失。从数据表可知，采用SADnew算法，编码质量平均损失控制在-0.5dB以内。从人眼视觉的生理特性来看，人的主观感觉并不会有明显差异，因而保证了SADnew算法的视频编码质量。从运行时间来看，采用SADnew算法，速度可提高50%～180%，平均可达130%，运算速度得到明显提升，整体性能获得显著改善。

表1 不同搜索策下SADnew与SAD编码质量对比（PSNR）

表2 不同搜索策略下SADnew与SAD处理速度对比（运动估计运行时间）

4 结束语

本文提出了一种面向视频会议的运动估计快速算法。该算法采用了积分图像方法，使用单元块级绝对差值和代替原始算法。通过该算法的改进，视频压缩的计算量明显减少，同时视频编码质量没有显著损失，适用于要求实时视频通信的视频会议等应用。

[1]Thomas Wiegand, Gary J.Sullivan, Gisle Bjontegaard,Ajay Luthra, Overview of the H.264/AVC Video Coding Standard .IEEE Transactions on Circuits and Systems for Video Technology,2003.13(7): p.560-576.

[2]谷会涛,陈书明,孙书为等.多搜索中心的运动估计快速算法[J].电子学报, 2011,39(3):695-699.

[3]张凡,唐作其,张正平等.基于H.264的UMHexagonS算法研究[J].通信技术, 2012,45(1):63-65.

[4]邵平,杨路明.基于模板分解和积分图像的快速Kirsch边缘检测[J].自动化学报, 2007,33(8):795-800.

[5]郭丽,孙兴华,杨静宇等.基于单元块均值的快速块匹配算法[J].计算机应用, 2006,26(7):1595-1597.