一种H.264/AVC的帧间运动估计的模式选择方法

摘要

本发明涉及视频编码领域。本文提出一种H.264/AVC帧间运动估计的模式选择方法，它根据宏块的帧间运动的剧烈程度，把宏块划分为不同尺寸的模式，初步获得优选的预测模式；然后根据宏块的帧间运动剧烈程度，用不同的搜索法搜索最佳匹配点进一步获得优选的预测模式，最后在优选的预测模式中使用率失真优化，从而确定最佳模式。采用本发明的方法，编码的运算量大幅减少，而且最佳匹配点的搜索时间大幅度缩短，并且对图像质量的影响可以忽略，使得H.264标准获得更广泛的应用。

说明书

技术领域

本发明涉及视频编码领域，具体的涉及H.264/AVC标准中的帧间运动估计模式的选择和最佳匹配点的选择的方法。

背景技术

H.264是由ISO/IEC和ITU-T两大标准化组织共同制定的新的视频编码标准。H.264/AVC项目最初的目标是希望新的编解码器能够在比相对以前的视频标准(比如MPEG-2或者H.263)低很多的码率下(比如说，一半或者更少)提供很好的视频质量；同时，并不增加很多复杂的编码工具，使得硬件难以实现。另外一个目标是可适应性，即该编解码器能够在一个很广的范围内使用(比如说，即包含高码率也包含低码率，以及不同的视频分辨率)，并且能在各种网络和系统上(比如组播，DVD存储，RTP/IP包网络，ITU-T多媒体电话系统)工作。

同人们熟悉的H.263相比，H.264标准下的视频图像质量更好，同时编码效率可以提高50％以上，并且具有更好的容错能力。这使得它在未来的视频通信领域具有广泛的应用前景。然而由于在图像编码时采用了多帧和多宏块运动估计(multi-frame and multi-block motionestimation)，使得编码计算的复杂度大幅增加，增大编码耗时，使得H.264/AVC的网络适应性变差。

为了提高编码效率，在该标准中采用了许多新技术来提高编码性能。其中一个最重要的技术就是率失真优化(RDO)。现有技术中，在进行率失真优化时，编码器要对视频序列帧间图像的所有可能的宏块模式进行比较，选择最佳的模式。这是一个很大的计算量。因为，对于图像中的一个16×16的宏块，编码器会首先进行16×16和8×16的运动估计(motion estimation)和率失真优化(RDO)，这将需要计算2次率失真度(rdcost)，并将2次计算的结果相加得到一个16×16宏块的Rdcost，再选择三者中16×16宏块的Rdcost最小的作为优选的预测模式。然后再把16×16宏块分成4个8×8的宏块，对每一个8×8宏块分成8×8、8×4、4×8、4×4四种模式分别进行运动估计和RDO。其中，8×4和4×8模式将两次计算的Rdcost相加得到8×8宏块的Rdcost，4×4模式的Rdcost也相加到结果中。4个8×8宏块的Rdcost相加得到一个16×16宏块的Rdcost，从这四种8×8划分中选择16×16宏块Rdcost最小的作为优选的预测模式。最后比较所获得的这2个优选的预测模式，选择率失真值较小的作为最佳的帧间预测模式。编码器需要对一个视频序列的每一个宏块重复以上步骤，直到序列的所有宏块的最佳帧间模式都得到确定。

可以看出这样的编码技术，运算量是非常庞大的。现有技术中对16×16宏块进行运动估计和Rdcost计算的执行次数为：16×16一次，16×8两次和8×16两次。8×8宏块的运动估计和率失真值计算的执行次数为8×8的1×4＝4次，8×4的2×4＝8次，4×8的2×4＝8次，4×4的4×4＝16次。一个16×16宏块总共需要进行的运动估计和Rdcost计算的执行次数是：1+2+2+4+8+8+16＝41次。对于QCIF格式的图像来讲，一帧有99个16×16宏模块，所以编码一帧图像要完成对运动估计和Rdcost计算的执行次数是41×99＝4059次。其中，Rdcost的计算复杂大高。大量重复这样复杂度高的计算，其编码非常耗时，对资源的消耗非常之大，也不便于实时应用。

现有技术中，使用这种常规计算的实现方法是JM软件。JM是ITU-T的专家组在制定标准的过程中，伴随标准不定期地提供相应的测试模型。这些测试模型通常采用标准C语言编写，主要目的是为了验证编码器的正确性并对编码性能进行测试。因此，尽管率失真优化可以带来非常好的编码性能，但是对于编码时所有模式的搜索消耗大量时间，这使得H.264编码器很难用于实时业务。很多快速的运动估计和模式决定的方法被提出用于改善这个情况，比如2003年多媒体国际会议(ICME2003)中发表的《一种新的H.264视频编码中多宏块运动估计的快速实现》以及2003年图像处理国际会议中发表的《JVT/H.264中的快速模式选择和运动估计》中，提出一种利用门限值提前终止的算法，用来减少对于候选预测模式的搜索。

这些快速实现的方法依然有缺陷。主要体现在对于优选的预测模式的选择仍然过于复杂，需要进行亚像素点的搜索和相对较多的计算。

此外，编码过程中需要用到的最佳匹配点的搜索法，例如现在比较典型的三步搜索法(TSS)、菱形搜索法(DS)、六边形搜索法(HEXBS)等，在具体应用到H.264整像素搜索算法上时，仍然有缺陷，主要表现在以下方面：

1、在H.264标准中，为了提高运动估计效果，采用了多个参考帧参与估计的算法，对于同一个宏块，采用七种不同的分块方式。在一个宏块的运动估计过程中，必须对每一个参考帧，每一种分块模式和每一种分块模式下的每一块分别进行运动估计搜索，以计算出最佳匹配点作为运动估计的结果。这样的编码计算过程是繁复而耗时的。

2、搜索最佳匹配点时搜索半径固定。因为对于均匀固定的图像区域，过大的搜索半径对于提高搜寻性能作用不大，因此搜索时不能达到最优效果，对资源造成一定浪费。

3、菱形搜索法和六边形搜索法，对于形状为正方形的块模式，覆盖效果比较好，因为其搜索范围近似于一个圆(实验统计数据表明，50％～90％的运动向量集中在以搜索半径为2的圆内)，但对于16×8、8×16、8×4、4×8块模式，由于块的长宽不一致，其搜索覆盖效果不好。

发明内容

(一)要解决的技术问题

本发明的目的是要克服目前现有技术的缺陷，提出一种效率更高的、应用于H.264/AVC标准的、能快速实现的视频编码方法，解决现有技术中编码时运动估计的帧间模式选择计算复杂度过高、耗时过多的问题，使得H.264/AVC标准的视频编码能更具有实时应用性。

(二)技术方案

本发明提出一种H.264/AVC帧间运动估计中确定最佳匹配点的方法，它包括以下步骤：

(1)视频序列划分成多个宏块；

(2)计算宏块帧间对应像素点的绝对差之和即SAD，根据SAD判断帧宏块的帧间运动剧烈程度；

(3)对运动剧烈程度不同的宏块，划分为大尺寸宏块、中尺寸宏块、小尺寸宏块；

(4)针对步骤(3)的不同尺寸的宏块，采用不同的匹配点搜索方法，确定最佳匹配点。

上述的帧间运动估计中确定最佳匹配点的方法，其中，对步骤(3)运动不剧烈的宏块再划分为大尺寸宏块，尺寸可以是16×16、16×8、8×16；运动比较显著的宏块再划分为中尺寸宏块，尺寸可以是8×8、8×4、4×8；运动非常显著的宏块划分为小尺寸宏块，尺寸是4×4。

上述的帧间运动估计中确定最佳匹配点的方法，一种优选的方案是，对于大尺寸宏块，使用菱形搜索模式确定图像匹配像素点；对于中尺寸宏块，先选用六边形搜索模式确定初步匹配点，再以这个点为中心，使用菱形搜索模式进行运动搜索，确定最佳匹配点；对于小尺寸宏块，先使用大六边形搜索模式进行搜索，找到运动矢量指示的范围，再选用六边形搜索模式进行搜索，找到初步匹配点，再以此点为搜索中心，使用菱形搜索模式确定匹配像素点。

本发明还提出一种H.264/AVC帧间运动估计的模式选择的方法，它包括以下步骤：

(1)把视频序列的帧图像划分为多个宏块；

(2)计算每个宏块帧间对应象素点的SAD；

(3)设定门限值TH1，将步骤(2)所得的SAD值与所设定的门限值TH1进行比较，初步确定优选模式，即对于SAD值小于TH1的情况，使用大宏块模式，对于SAD值大于TH1的情况，使用中、小宏块模式；

(4)对不同的宏块模式选用如权利要求3所述的方法确定图像的最佳匹配点；

(5)计算步骤(4)确定的最佳匹配点的水平相邻和垂直相邻的共4个点像素点的SAD值，其中水平像素点的SAD值标记为SADH，垂直像素点的SAD值标记为SADV；

(6)对步骤(5)中所得的4个SAD值进行比较，根据不同的比较结果进一步选择优选的预测模式；

(7)对步骤(6)获得的优选的预测模式进行率失真优化(RDO)，确定最佳模式。

上述的帧间运动估计的模式选择的方法，一种优选的方案是，步骤(3)中的大宏块模式可以是16×16、16×8、8×16模式；中宏块模式可以是8×8、8×4、4×8模式；小宏块模式可以是4×4模式。

上述的帧间运动估计的模式选择的方法，一种优选的方案是，对于步骤(6)，可以把2个SADH中较大的值标记为SADH_max，把2个SADV中较大的值标记为SADV_max；大宏块模式的情况下，对于SADH_max＞SADV_max的情况，选择16×8和16×16模式作为优选的预测模式；对于SADH_max＜SADV_max的情况，选择8×16和16×16模式作为优选的预测模式；对于SADH_max＝SADV_max的情况，同时选用16×8、8×16和16×16模式作为优选的预测模式。中、小宏块模式的情况下，对于SADH_max＞SADV_max的情况，选择8×4和8×8模式作为优选的预测模式，；对于SADH_max＜SADV_max的情况，选择4×8和8×8模式作为优选的预测模式；对于SADH_max＝SADV_max的情况，同时选用8×4和4×8和8×8模式作为优选的预测模式。

(三)有益效果

使用本发明的H.264/AVC帧间运动估计的模式选择和运动估计的快速实现的方法，能获得以下优点：

1、由于本发明的主要运算在于计算SAD，而SAD容易计算，所以大大减小了编码过程中的计算量，节约资源。

2、由于图像序列中存在很大部分的均匀和平稳部分，这些部分被划分为小尺寸宏块的机会很小，并且没有必要再进行小尺寸宏块类型的RDO计算。因此，对不同的图像部分采用不同的宏块尺寸，可以极大的节约编码时间和降低编码复杂度，使得编码方法适应实时业务的要求。

3、实验结果显示，本发明的方法和现有技术中使用JM9.3方法计算相比较，对于不同的量化步长，可以平均减少70.4％的运动估计耗时，而在图像质量影响方面，图像质量即PSNR的减少仅0.1dB左右，这样的损失是可以忽略的，而输出码流比特率的增加仅在2.5％以内。也就是说，采用本发明的方法后，在大大提高了编码效率的同时对图像质量的负面影响却是非常的小。

附图说明

图1为本发明的帧间运动估计的模式选择的方法中，选择优选的预测模式的流程图；

图2为本发明的帧间运动估计的模式选择的方法中，在已选定的优选的预测模式中确定最佳模式的流程图；

图3为一个最佳匹配点及其相邻的4个像素点的示意图；

图4为实施例中，采用本发明的方法和现有技术的方法，在为了确定最佳匹配点时搜索的像素点的个数的比较；

图5为实施例3的效果对比图；

图6为实施例4的效果对比图；

图7为实施例5的效果对比图。

具体实施方式

本发明提出的H.264/AVC帧间运动估计的模式选择的方法，结合附图和实施例说明如下。以下实施方式仅用于说明本发明，而并非对本发明的限制，有关技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明的范畴，本发明的专利保护范围应由各权利要求限定。

以下各个实施例的实验条件为：

(1)对测试视频序列的前100帧进行编码；

(2)采用CAVLC(基于上下文的变长编码)熵编码；

(3)采用5参考帧；

(4)搜索范围为32像素点；

(5)采用哈达玛(Hadamard)变换；

(6)使用率失真优化(RDO)；

(7)编码序列GOP为IPPP；

(8)实验使用JM9.3软件为对比参考(即JVT Reference Softwareunofficial version JM9.3，软件下载地址为http://bs.hhi.de/～suehring/tml/download)；

(9)实验采用的计算机配置为P4 Celeron 2.66GHz的CPU，256M的内存。

 以下实施例中对各种QCIF、CIF格式的标准视频序列进行了测试，对比两种方式的结果：其中，一种是采用JM9.3原来设置即采用快速搜索的方法对全部宏块模式进行编码，另一种是本文提出的帧间运动估计的模式选择的方法进行编码。

(实施例一)

在本实施例中，对5个视频序列，分别为“container”、“news”、“foreman”、“tempete”和“pairs”进行测试，对比现有技术和采用本发明的方法后，运动估计和RDO的计算次数的改变。

由于现有技术不考虑帧图像之间的时间相关性，所以对于QCIF格式的视频序列，每帧有99个16×16的宏块，因此每帧都需要进行4056次运动估计和率失真值计算。

采用本发明的方法模式选择方法后，每个视频序列的运算次数如表1所示：

序列名称  运动估计和率失真优化的计算次数  container  552  news  796  foreman  661  tempete  1491  pairs  1265

              表1

可见，由于现有技术中，对视频序列进行率失真优化时，编码器要对帧间图像的所有可能的宏块模式进行比较，选择最佳的模式，因此运算量很大；而采用本发明的方法，会先判断帧间图像的运动剧烈程度，初步获得优选的模式，第一次减少运行RDO的次数；然后根据帧间图像的运动剧烈程序使用不同的搜索方法确定最佳匹配点，计算最佳匹配点相邻的SAD值，根据这些值进一步减少了优选的模式个数，最后对这些优选的模式运行RDO。因此，经过这样2次对预测模式个数的减少，对于运动不太剧烈的视频序列如“container”，运算次数大幅减少到原来1/7左右，而即使是最坏的情况，也就是运动非常剧烈的视频序列“tempete”，其运算次数也降低到1491次，相比现有技术有非常大的减幅。

图4显示了采用本发明的方法和现有技术的方法，在为了确定最佳匹配点时搜索的像素点的个数的比较。其中划线柱表示现有技术的方法的像素点搜索个数，无划线柱表示采用本发明的方法的像素点搜索个数，横轴表示本实施例使用的5个测试视频序列，纵轴表示为了确定最佳匹配点时搜索的像素点的个数的比较。可见采用本发明的方法对测试序列进行编码，相比起现有技术，在搜索像素点个数方面大幅减少，对比较好的情况，能减少一半的搜索量。

(实施例二)

本实施例中，针对一个16×16的测试宏块，对比现有技术的JM9.3和本发明的运动估计的快速实现方法，在7种不同尺寸的模式下，对比计算最佳匹配点时所需要搜索的像素点的个数和次数，以及总计算量。

现有技术中，匹配点的搜索中不对运动情况进行分类，对于16×16的模式首先采用六边形搜索模式，然后采用菱形搜索模式，而对于其余所有模式都首先使用大六边形模式，然后是再采用六边形模式和菱形模式搜索方法，因此计算量庞大。

本实施例中，考虑到帧间的运动关系，对不同的宏块采用不同的搜索方法，因此，对于大六边形模式需要搜索152个像素点，六边形模式需要搜索的像素点个数为192个，菱形模式则为128个。

表2给出了采用本发明的方法和现有技术的JM 9.3方法对于一个16×16宏块，所要搜索的像素点的个数和次数对比。可以看出JM9.3方法对于16×16块要搜索320个点，本发明的方法只要128个；对于其余六种模式，现有技术搜索点数都是472，而本发明的方法可以根据图像运动情况选择不同的宏块划分，因此每种划分所要的点数不同，并且对于大尺寸划分搜索点数减少的较多。

  本发明的方法  JM9.3的方法  模式  操作点数×次数  总计算量  操作点数×次数  总计算量  16×16  128×1  128  320×1  320  16×8  128×2  256  472×2  944  8×16  128×2  256  472×2  944  8×8  320×4  1280  472×4  1888  8×4  320×8  2560  472×8  3776  4×8  320×8  2560  472×8  3776  4×4  472×16  7552  472×16  7552

                                表2

(实施例三)

在本实施例中，分别对9个视频序列，其中包括QCIF格式和CIF格式的标准视频序列进行了测试，对比两种方式的结果：一种是采用JM9.3原来设置即采用快速运动估计方法对全部宏块模式进行编码，另一种是本发明提出的帧间运动估计的模式选择和运动估计的快速实现的方法。

为了获得较好的效果，保证编码性能，对于门限值TH₁的选择非常重要。选择依据是在运动补偿耗时和输出码流比特率、图像质量PSNR之间找到一个较好的平衡。

通过多次实验得知，不同TH₁条件下的运动估计耗时减少，图像质量变化和码流速率都不同，综合考虑让图像质量减少和输出码流比特率变化最小。例如在本实施例中，在量化系数QP为28的情况下，选择6000作为门限。在往后的应用中，如果用户对图像质量或编码耗时有特殊要求，可以改变这个门限值，以获得合适的效果。

表3给出了在量化系数QP＝28情况下，对不同的9个序列的测试结果，包括对比现有技术，采用本发明的方法后，运动估计时间的变化，其中负号表示时间的节省；图像质量的变化，其中负号表示失真；和输出码流比特率的变化。

序列名称(格式)  运动估计时间变化(％)  图像质量改变(dB)  比特率改变(％)  news(QCIF)  -72.992  -0.060  2.436  salesman(QCIF)  -74.448  -0.200  1.890  carphone(QCIF)  -67.226  -0.100  3.857  foreman(QCIF)  -55.938  -0.060  6.081  claire(QCIF)  -57.290  -0.140  1.256  container(QCIF)  -69.313  -0.060  0.037  mother&daughter(QCIF)  -84.840  -0.110  1.563  mobile(CIF)  -46.944  -0.040  2.836  tempete(CIF)  -48.234  -0.020  2.763  均值  -64.136  -0.088  2.524

                        表3

图5显示了采用本发明的方法和现有技术的方法在运动估计耗时的比较。其中划线柱表示现有技术的方法运动估计耗时，无划线柱表示采用本发明的方法的耗时，横轴数字1～9顺序表示上面表中的9个标准视频序列，纵轴表示运动估计所需要时间，单位是秒。

可见，对于QP＝28，TH₁＝6000的情况，平稳的图像序列运动估计时间最多可以节省84.8％(“mother and daughter”序列)，对于运动剧烈的图像序列最小也可以提高46.9％(“mobile”序列)，平均可以节省64.1％的运动估计耗时

(实施例四)

在本实施例中，分别对9个视频序列，其中包括QCIF格式和CIF格式的标准视频序列进行了测试，对比两种方式的结果：一种是采用JM9.3原来设置即采用快速运动估计方法对全部宏块模式进行编码，另一种是本发明提出的帧间运动估计的模式选择和运动估计的快速实现的方法。

本实施例中的量化系数QP为32，选择的门限值为10000。

表4给出了对不同的9个序列的测试结果，包括对比现有技术，采用本发明的方法后，运动估计时间的变化，其中负号表示时间的节省；图像质量的变化，其中负号表示失真；和输出码流比特率的变化。

序列名称(格式)  运动估计时间变化(％)  图像质量改变(dB)  比特率改变(％)  news(QCIF)  -86.679  -0.090  1.782  salesman(QCIF)  -82.447  -0.080  2.293  carphone(QCIF)  -75.258  -0.120  2.083  foreman(QCIF)  -64.838  -0.200  3.548

 claire(QCIF)  -65.134  0.190  3.240 container(QCIF)  -69.750  -0.070  0.249 mother&daughter(QCIF)  -81.884  -0.010  2.261 mobile(CIF)  -61.214  -0.070  0.350 tempete(CIF)  -52.589  -0.060  1.162 均值  -71.088  -0.057  1.885

                                表4

可见，对于QP＝32，TH₁＝10000的情况，平稳的图像序列的运动估计时间最大可以节省86.7％(“news”序列)，对于运动剧烈的图像序列最小也可以提高52.6％(“tempete”序列)，平均可以节省71％的运动估计耗时，而图像质量的损耗平均只有0.06分贝，可以忽略。

图6显示了采用本发明的方法和现有技术的方法在运动估计耗时的比较。其中划线柱表示现有技术的方法运动估计耗时，无划线柱表示采用本发明的方法的耗时，横轴数字1～9顺序表示上面表中的9个标准视频序列，纵轴表示运动估计所需要时间，单位是秒。

(实施例五)

在本实施例中，分别对9个视频序列，其中包括QCIF格式和CIF格式的标准视频序列进行了测试，对比两种方式的结果：一种是采用JM9.3原来设置即采用快速运动估计方法对全部宏块模式进行编码，另一种是本发明提出的帧间运动估计的模式选择和运动估计的快速实现的方法。

本实施例中的量化系数QP为36，选择的门限值为14000。

表5给出了对不同的9个序列的测试结果，包括对比现有技术，采用本发明的方法后，运动估计时间的变化，其中负号表示时间的节省；图像质量的变化，其中负号表示失真；和输出码流比特率的变化。

序列名称(格式)  运动估计时间变化(％)  图像质量改变(dB)  比特率改变(％)  news(QCIF)  -82.612  -0.150  2.104  salesman(QCIF)  -84.703  -0.130  0.850  carphone(QCIF)  -81.861  -0.110  1.196  foreman(QCIF)  -77.149  -0.280  5.219  claire(QCIF)  -61.725  -0.210  4.267  container(QCIF)  -73.491  -0.020  0.808  mother&daughter(QCIF)  -83.910  0.020  2.544  mobile(CIF)  -63.528  -0.060  0.237  tempete(CIF)  -74.287  0.000  0.029  均值  -75.919  -0.104  1.917

                           表5

可见，对于QP＝36，TH₁＝14000的情况，平稳的图像序列的运动估计时间最大可以节省84.7％(“salesman”序列)，对于运动剧烈的图像序列最小也可以提高61.7％(“claire”序列)，平均可以节省76％的运动估计耗时，而图像质量的损耗平均只有0.1分贝，可以忽略。

图7显示了采用本发明的方法和现有技术的方法在运动估计耗时的比较。其中划线柱表示现有技术的方法运动估计耗时，无划线柱表示采用本发明的方法的耗时，横轴数字1～9顺序表示上面表中的9个标准视频序列，纵轴表示运动估计所需要时间，单位是秒。