论文部分内容阅读
摘 要： 针对移动通信终端计算能力的不足，提出了一种适用于可视电话视频压缩编码的快速运动估计算法。根据当前块运动矢量类型和可视电话视频对象的运动特点，自动选择不同的搜索策略进行运动估计搜索。该算法在保证图像主客观质量的前提下，有效地减少了运动估计的时间，大大降低了编码计算量。通过对不同类型的视频序列进行测试表明，该算法计算复杂度降低了55.4%～69.6%，且对于不同运动类型的视频具有较强的适应性。
关键词： 移动终端； H.264； 运动估计； 算法
中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2013）03-32-03
0 引言
移动终端和网络技术的不断发展，为移动视频业务的推广提供了必要条件。市场需求和技术进步共同推动着移动视频业务的发展，并使其成为移动运营商、设备制造商和内容提供商的关注焦点之一。目前，消费市场对移动视频业务的认可程度和期望值很高，预计在未来几年内移动视频业务将是推动3G网络发展的源动力。
H.264是由ISO/IEC与ITU-T组成的联合视频组（JVT）制定的新一代视频压缩编码标准，具有较高的图像质量、较强的抗误码性和良好的网络亲和性[1]。H.264目前已广泛地应用在移动通信、无线网络、卫星广播、电视会议、远程监控、远程教育医疗、IPTV等领域。H.264基本档（baseline）的使用不涉及版权，这对商业应用和普及推广具有重要的意义。
移动终端硬件设备的处理能力相对PC机来说有很大的差距，这使得其对视频编解码的运算量提出了极高的要求。因此，针对移动终端设备计算能力不足的特点，对H.264编码器作相应的改进以降低编码复杂度，是十分必要的。
运动估计（Motion Estimation，ME）是H.264编码器的核心模块，H.264编码器的架构结构如图1所示。视频编码时，只需根据ME搜索结果保存运动矢量和残差数据，即可完全恢复当前编码块。根据实验测试分析得知，ME模块的运算量占整个编码器运算量的60%-90%[2]。因此，要想降低H.264编码器的计算复杂度，提高其编码速度，应首先考虑优化ME算法模块。
1 运动矢量相关性验证
头肩序列是可视电话中最常见的一种图像模式。头肩序列具有运动缓慢、背景相对静止等特点，头肩部的运动一般是左右摇摆，上下方向的运动幅度要小于水平方向，因此很大一部分相邻块的运动矢量会具有相似或基本相同的特点。利用这些特点设计新的运动估计搜索方案，可以大大降低计算复杂度，提高编码速度。
本文对forman、missa等测试序列作了统计，实验结果如最佳运动矢量分布表（表1）所示。表1中“相邻相等”指三个参考块的运动矢量相等，“相同”指在相邻块运动矢量相同的基础上，当前块最终运动矢量与预测运动矢量相同的条件概率；“1×1”指最终运动矢量分布在以预测矢量为中心，1为半径的区域内的条件概率。这些数据都是在H.264的JM85模型上用全搜索算法统计的结果。
表1 最佳匹配矢量分布表
[序列名称＼&相邻相等＼&相同＼&1×1＼&foreman＼&69.2%＼&60.8%＼&96.1%＼&missa＼&84.0%＼&96.9%＼&99.6%＼&]
由表1的实验统计结果可知，利用时空上相邻块的运动矢量来预测搜索起始点，能减少搜索范围，提高搜索速度，减少陷入局部最优的可能性。因此，本文选取当前待编码块MB0的左边MB1、上边MB2、右上边MB3等三个相邻块的运动矢量来预测预测搜索起始点，如图2所示。
2 本文自适应搜索的快速运动估计算法
2.1 本文算法搜索策略设计
本文采用中值法来确定预测搜索起始点，其基本思想是：选取参考块MB1、MB2、MB3的匹配矢量的中值来预测搜索起始点。采用中值法预测得到的搜索起始点都是相邻某一块的运动矢量，因此最终搜索所得的运动矢量场较为平滑，节省了对运动矢量编码所需的码率。当前块MB0的预测矢量Vp的计算如公式⑴所示。
其中，Vp为当前块MB0的预测矢量，即预测的运动估计搜索起始点；V1、V2和V3分别为MB1、MB2、MB3的等三个参考块的运动矢量。
考虑到可视电话头肩序列的运动特性，本文设计了如图3所示的三种搜索模板。其中，大模板是为了快速向最佳匹配点逼近，提高算法的位移跟踪能力，减少搜索次数；而小模板则用以进行局部微调和精确定位，保證搜索精度。同时由表1的统计数据可知，当相邻块的匹配矢量相同时，最佳匹配点应在预测的搜索起始点附近，本文算法对这种情况采用小模板搜索。
资料显示各种块匹配函数的性能差别不显著，为了使计算复杂度能够更低，便于硬件实现，本文采用运算量最小的绝对差之和（Sum of Absolute Difference，SAD）作为搜索算法的匹配准则，其计算如公式⑵所示。
通常，可视电话视频序列采用QCIF格式，像素精度为8bit。因此，本文采用的平均峰值信噪比（PSNR）的计算如公式⑶所示：
2.2 本文算法搜索流程
本文基于模板自适应的快速运动估计算法流程图如图4所示，具体搜索过程如下。
⑴ 若V1=V2=V3，即三个参考块的运动矢量相等，则表明当前块所在区域的运动特性一致。因此，当前块只需在预测搜索起始点的周围做小范围搜索，就极有可能找到全局最优匹配块。即使用小模板在预测搜索起始点周围进行匹配计算，直至最小SAD出现，搜索结束；否则，转⑵。
⑵ 继续比较Vd=max（|Vpx|，|Vpy|）与预设阈值T的大小。若满足Vd|Vpy|，表明水平方向的运动强度要比垂直方向大，则对当前块采用水平大模板进行搜索，直至最小SAD点出现。然后扩展搜索水平大模板中心点的左右两点，若最小SAD点仍在中心点，则搜索结束；若最小SAD点发生偏移，则搜索此最小SAD点的上下两点，所得最小SAD点即为最终的搜索结果。
对于|Vpy|>|Vpx|的情况，采用垂直大模板进行搜索，具体搜索方法与步骤⑶中水平大模板类同。
3 实验结果与分析
为了分析、比较各算法的性能，本文从以下几个方面进行实验比较：平均搜索点数，平均ME耗时，码率，平均信噪比（PSNR）等指标。这些比较实验都是在H.264测试模型JM85的baseline上进行的，由于JM代码本身是为算法研究及标准的发展提供的统一测试平台，提供各种实验研究所需的测试参数。对于本文研究的运动估计模块，JM平台也提供了专门的时间统计数据。具体实验参数设置为：Intraperiod=10，QP=30，1个参考帧，FrameRate=25，块匹配范围为-8～+8，采用七种块模式及CAVLC熵编码。PC机操作系统为Windows XP， CPU为Pentium Ⅳ 3G，1G内存，编译软件为Visual C++6.0。
从以上实验测试结果可知，按搜索点数计算，本文算法相对其他快速搜索算法的计算复杂度降低55.4%～69.6%。按平均ME耗时计算，本文算法相对其他快速搜索算法的计算复杂度降低42.3%～55.7%。同时，解码图像的平均信噪比，本文算法都要优于菱形搜索法DS、新三步法NTSS和四步法FSS。而且本文算法的计算复杂度较低，搜索点数和块匹配时间大幅下降，这是其他几种算法无法比拟的。实验中，对两组测试序列都存在本文算法的PSNR远高于其他算法的现象，其原因在于本文快速搜索算法得到的匹配矢量场比其他算法的更为均匀、平滑，从而减少了对矢量场编码所需的比特数，即可留出更多的比特数用于编码残差数据等信息，从整体上提高了重建图像的信噪比。
在本文算法中，阈值T的选取也是一个很重要的问题。随着门限阈值的增加，使用小模板搜索的概率增加，搜索点数会有所下降，得到的矢量场更为均匀，但块匹配误差也随之增加。使用阈值T的优点在于，对不同变化强度的数据片序列可以通过设置阈值T来改进算法性能，对于快速变化序列更是如此。恰当地选择阈值T的大小，将有助于加快搜索速度，提高块匹配精度；本实验里设置T=4。
4 结束语
本文分析了可视电话视频对象的特性，提出了一种适用于可视电话硬件实现的低复杂度快速运动估计算法，获得了良好的率失真性能，大大降低了计算复杂度。本算法以运动矢量相关性为根据，引入简单有效的视频分类方法，使本文算法能根据视频序列的运动类型自适应地选择搜索模板，且对于不同运动类型具有较强的适应性。本文算法可直接应用于极低复杂度实时视频编码软件，经过适当修改可供DSP或制成ASIC用于实时视频编码硬件系统。
在本文算法中，对不同运动强度的视频序列可以通过设置阈值T来改进算法性能。但是，针对不同运动强度和量化级别情况下的阈值设置还需要作进一步的研究，并将该整象素快速运动估计算法应用于亚象素的快速运动估计搜索中。
参考文献：
[1] PENGQ， ZHANGL， YANGTW. Key-frame reference selection for
non-feedback video communication[J]. The Journal of China Universities of Posts and Telecommunications，2009.16（5）：92-102
[2] ZHU SP， TIAN J. An improved fast fractional pel motion
estimation algorithm based on H.264[c]//IEEE. 2010 IEEE International Conference on Industrial Technology. Washington， DC： IEEE Press，2010：179-182
[3] The H.264/AVC Advanced Video Coding Standard： Overview
and Introduction to the Fidelity Range Extensions，Gary J. Sullivan， Pankaj ToPiwala， and Ajay Luthra. Microsoft Corporation，One Microsoft way Redmond， WA98052 Fast VDO LLC， 7150RiverwoodDr.， Columbia， MD21046 Motorola Ine.， BCS， 6420 Sequence Dr.， San Diego，CA9212.
[4] HENG Z J， FENG Z W. A new fast motion estimation method for
H.264[c].//IEEE. International Conference on Image and signal processing. Washington， DC： IEEE Press，2009：1-4
关键词： 移动终端； H.264； 运动估计； 算法
中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2013）03-32-03
0 引言
移动终端和网络技术的不断发展，为移动视频业务的推广提供了必要条件。市场需求和技术进步共同推动着移动视频业务的发展，并使其成为移动运营商、设备制造商和内容提供商的关注焦点之一。目前，消费市场对移动视频业务的认可程度和期望值很高，预计在未来几年内移动视频业务将是推动3G网络发展的源动力。
H.264是由ISO/IEC与ITU-T组成的联合视频组（JVT）制定的新一代视频压缩编码标准，具有较高的图像质量、较强的抗误码性和良好的网络亲和性[1]。H.264目前已广泛地应用在移动通信、无线网络、卫星广播、电视会议、远程监控、远程教育医疗、IPTV等领域。H.264基本档（baseline）的使用不涉及版权，这对商业应用和普及推广具有重要的意义。
移动终端硬件设备的处理能力相对PC机来说有很大的差距，这使得其对视频编解码的运算量提出了极高的要求。因此，针对移动终端设备计算能力不足的特点，对H.264编码器作相应的改进以降低编码复杂度，是十分必要的。
运动估计（Motion Estimation，ME）是H.264编码器的核心模块，H.264编码器的架构结构如图1所示。视频编码时，只需根据ME搜索结果保存运动矢量和残差数据，即可完全恢复当前编码块。根据实验测试分析得知，ME模块的运算量占整个编码器运算量的60%-90%[2]。因此，要想降低H.264编码器的计算复杂度，提高其编码速度，应首先考虑优化ME算法模块。
1 运动矢量相关性验证
头肩序列是可视电话中最常见的一种图像模式。头肩序列具有运动缓慢、背景相对静止等特点，头肩部的运动一般是左右摇摆，上下方向的运动幅度要小于水平方向，因此很大一部分相邻块的运动矢量会具有相似或基本相同的特点。利用这些特点设计新的运动估计搜索方案，可以大大降低计算复杂度，提高编码速度。
本文对forman、missa等测试序列作了统计，实验结果如最佳运动矢量分布表（表1）所示。表1中“相邻相等”指三个参考块的运动矢量相等，“相同”指在相邻块运动矢量相同的基础上，当前块最终运动矢量与预测运动矢量相同的条件概率；“1×1”指最终运动矢量分布在以预测矢量为中心，1为半径的区域内的条件概率。这些数据都是在H.264的JM85模型上用全搜索算法统计的结果。
表1 最佳匹配矢量分布表
[序列名称＼&相邻相等＼&相同＼&1×1＼&foreman＼&69.2%＼&60.8%＼&96.1%＼&missa＼&84.0%＼&96.9%＼&99.6%＼&]
由表1的实验统计结果可知，利用时空上相邻块的运动矢量来预测搜索起始点，能减少搜索范围，提高搜索速度，减少陷入局部最优的可能性。因此，本文选取当前待编码块MB0的左边MB1、上边MB2、右上边MB3等三个相邻块的运动矢量来预测预测搜索起始点，如图2所示。
2 本文自适应搜索的快速运动估计算法
2.1 本文算法搜索策略设计
本文采用中值法来确定预测搜索起始点，其基本思想是：选取参考块MB1、MB2、MB3的匹配矢量的中值来预测搜索起始点。采用中值法预测得到的搜索起始点都是相邻某一块的运动矢量，因此最终搜索所得的运动矢量场较为平滑，节省了对运动矢量编码所需的码率。当前块MB0的预测矢量Vp的计算如公式⑴所示。
其中，Vp为当前块MB0的预测矢量，即预测的运动估计搜索起始点；V1、V2和V3分别为MB1、MB2、MB3的等三个参考块的运动矢量。
考虑到可视电话头肩序列的运动特性，本文设计了如图3所示的三种搜索模板。其中，大模板是为了快速向最佳匹配点逼近，提高算法的位移跟踪能力，减少搜索次数；而小模板则用以进行局部微调和精确定位，保證搜索精度。同时由表1的统计数据可知，当相邻块的匹配矢量相同时，最佳匹配点应在预测的搜索起始点附近，本文算法对这种情况采用小模板搜索。
资料显示各种块匹配函数的性能差别不显著，为了使计算复杂度能够更低，便于硬件实现，本文采用运算量最小的绝对差之和（Sum of Absolute Difference，SAD）作为搜索算法的匹配准则，其计算如公式⑵所示。
通常，可视电话视频序列采用QCIF格式，像素精度为8bit。因此，本文采用的平均峰值信噪比（PSNR）的计算如公式⑶所示：
2.2 本文算法搜索流程
本文基于模板自适应的快速运动估计算法流程图如图4所示，具体搜索过程如下。
⑴ 若V1=V2=V3，即三个参考块的运动矢量相等，则表明当前块所在区域的运动特性一致。因此，当前块只需在预测搜索起始点的周围做小范围搜索，就极有可能找到全局最优匹配块。即使用小模板在预测搜索起始点周围进行匹配计算，直至最小SAD出现，搜索结束；否则，转⑵。
⑵ 继续比较Vd=max（|Vpx|，|Vpy|）与预设阈值T的大小。若满足Vd
对于|Vpy|>|Vpx|的情况，采用垂直大模板进行搜索，具体搜索方法与步骤⑶中水平大模板类同。
3 实验结果与分析
为了分析、比较各算法的性能，本文从以下几个方面进行实验比较：平均搜索点数，平均ME耗时，码率，平均信噪比（PSNR）等指标。这些比较实验都是在H.264测试模型JM85的baseline上进行的，由于JM代码本身是为算法研究及标准的发展提供的统一测试平台，提供各种实验研究所需的测试参数。对于本文研究的运动估计模块，JM平台也提供了专门的时间统计数据。具体实验参数设置为：Intraperiod=10，QP=30，1个参考帧，FrameRate=25，块匹配范围为-8～+8，采用七种块模式及CAVLC熵编码。PC机操作系统为Windows XP， CPU为Pentium Ⅳ 3G，1G内存，编译软件为Visual C++6.0。
从以上实验测试结果可知，按搜索点数计算，本文算法相对其他快速搜索算法的计算复杂度降低55.4%～69.6%。按平均ME耗时计算，本文算法相对其他快速搜索算法的计算复杂度降低42.3%～55.7%。同时，解码图像的平均信噪比，本文算法都要优于菱形搜索法DS、新三步法NTSS和四步法FSS。而且本文算法的计算复杂度较低，搜索点数和块匹配时间大幅下降，这是其他几种算法无法比拟的。实验中，对两组测试序列都存在本文算法的PSNR远高于其他算法的现象，其原因在于本文快速搜索算法得到的匹配矢量场比其他算法的更为均匀、平滑，从而减少了对矢量场编码所需的比特数，即可留出更多的比特数用于编码残差数据等信息，从整体上提高了重建图像的信噪比。
在本文算法中，阈值T的选取也是一个很重要的问题。随着门限阈值的增加，使用小模板搜索的概率增加，搜索点数会有所下降，得到的矢量场更为均匀，但块匹配误差也随之增加。使用阈值T的优点在于，对不同变化强度的数据片序列可以通过设置阈值T来改进算法性能，对于快速变化序列更是如此。恰当地选择阈值T的大小，将有助于加快搜索速度，提高块匹配精度；本实验里设置T=4。
4 结束语
本文分析了可视电话视频对象的特性，提出了一种适用于可视电话硬件实现的低复杂度快速运动估计算法，获得了良好的率失真性能，大大降低了计算复杂度。本算法以运动矢量相关性为根据，引入简单有效的视频分类方法，使本文算法能根据视频序列的运动类型自适应地选择搜索模板，且对于不同运动类型具有较强的适应性。本文算法可直接应用于极低复杂度实时视频编码软件，经过适当修改可供DSP或制成ASIC用于实时视频编码硬件系统。
在本文算法中，对不同运动强度的视频序列可以通过设置阈值T来改进算法性能。但是，针对不同运动强度和量化级别情况下的阈值设置还需要作进一步的研究，并将该整象素快速运动估计算法应用于亚象素的快速运动估计搜索中。
参考文献：
[1] PENGQ， ZHANGL， YANGTW. Key-frame reference selection for
non-feedback video communication[J]. The Journal of China Universities of Posts and Telecommunications，2009.16（5）：92-102
[2] ZHU SP， TIAN J. An improved fast fractional pel motion
estimation algorithm based on H.264[c]//IEEE. 2010 IEEE International Conference on Industrial Technology. Washington， DC： IEEE Press，2010：179-182
[3] The H.264/AVC Advanced Video Coding Standard： Overview
and Introduction to the Fidelity Range Extensions，Gary J. Sullivan， Pankaj ToPiwala， and Ajay Luthra. Microsoft Corporation，One Microsoft way Redmond， WA98052 Fast VDO LLC， 7150RiverwoodDr.， Columbia， MD21046 Motorola Ine.， BCS， 6420 Sequence Dr.， San Diego，CA9212.
[4] HENG Z J， FENG Z W. A new fast motion estimation method for
H.264[c].//IEEE. International Conference on Image and signal processing. Washington， DC： IEEE Press，2009：1-4