一种用于H.264编码的整数运动估计快速搜索方法

摘要

本发明公开了一种用于H.264编码的整数运动估计快速搜索方法，其中包括以下步骤：先对整个搜索窗SW1内的像素点进行亚采样处理，只针对16×16模式进行搜索，根据SAD准则，找出匹配最佳的N个候选样本像素点；根据N个候选点的收敛率及分布位置，重新展开搜索窗SW2；对SW2内的像素点再次搜索，得出最佳的整数运动矢量。根据设定的候选样本像素点数N，可以在图像质量和计算量之间做出取舍。N值越小，搜索点和运算量越少，整数运动估计完成越快，代价是图像质量的下降；反之，N值越大，搜索点和运算量越多，图像质量上升。本发明中设定N的值为1-3。本快速搜索方法运用了粗略、精细两步搜索，有效地减少了需要搜索的像素点，降低了运算复杂度，提高了运算速度。

说明书

技术领域

本发明涉及一种计算机领域中视频图像编码，特别涉及用于 H.264协议的整数运动估计的快速搜索方法。

背景技术

ISO/IEC和ITU-T两大国际标准化组织联手制定了新一代视频 压缩标准H.264。自2003年3月H.264视频压缩标准正式公布以来，被 广泛应用于实时视频监控、低延时模式的视频会议、网络视频点播、 数字视频存储等其他消费电子应用领域。

H.264之所以有这么出色的压缩性能，得益于新引入的多种技术， 如帧内预测、多参考帧、帧间可变尺寸块运动估计、1/4像素精度的 运动矢量、整数变换与量化、上下文自适应的熵编码和去块滤波等技 术。在H.264标准中，运动估计模块是H.264编码器的核心部件，占据 了60％-70％的编码运算时间，决定了整个编码的实时编码性能。运动 估计模块会先进行整数运动估计，然后再进行分数运动估计。其中， 整数运动估计占据了整个编码30％的运算量，成为H.264编码的关键路 径之一。

在整数运动估计方法中，最简单、有效的方法是全搜索方法(FS, Full Search)，及穷尽搜索窗内所有的像素点进行匹配，但此法所 需的运算量十分巨大，很难满足实时编码的要求，因此出现了很多快 速搜索方法，如三步搜索法(TSS,Three Step Search)、新三步法 (NTSS,New Three Step Search)、二维对数搜索法(TDL, 2D-logarithmic search)、交叉搜索法(CS,Cross Search)、钻石搜 索法(DS,Diamond Search)等。

发明内容

本发明要解决的问题是提供一种用于H.264编码的整数运动估 计快速搜索方法，可通过设定内部编码参数，来控制编码图像质量和 运算复杂度，在保证编码图像质量的同时，有效减少整数运动估计搜 索的范围和时间。

为解决上述问题，本发明采用如下技术方案：

一种用于H.264编码的整数运动估计快速搜索方法，包括以下步 骤：

步骤一，在参考帧中，根据外部设定的搜索范围，以搜索中心点 展开搜索窗SW1，其范围为Searchrang_x*Searchrange_y；

步骤二，将搜索窗SW1内所有的像素点进行亚采样。本发明中， 设定亚采样率为1/16，即在一行像素点中每四个像素点进行一次取 点采样，并且在垂直方向上每四行像素点进行一次取点采样，经过这 两步采样过程之后，完成整个亚采样过程。亚采样处理可以有效减少 搜索的点数，减少计算量，是粗略搜索的重要操作；

步骤三，对经过步骤二得到的样本像素点，只针对16×16模式， 根据SAD准则，得到N个SAD值最小的候选样本像素点，进行一下步 的计算。其中，N是由外部设定的值，本发明中设定范围为1-3。N 值越大，得到的候选样本像素点的个数越多，编码图像质量越高，同 时运算量也将增加；反之运算量将减少，代价是编码图像质量也会有 所下降；

步骤四，根据得到的候选样本像素点的SAD值和分布位置，重新 设定整数运动估计的搜索范围，得到新的搜索窗SW2。

情况一，当N＝1时，以新的候选样本像素点为中心展开SW2。

情况二，当N＝2时，需要根据公式(1)判断收敛系数K1：

$K1=\frac{\min 2\left(\mathrm{SAD}\right)-\min 1\left(\mathrm{SAD}\right)}{\min 2\left(\mathrm{SAD}\right)}\left(1\right)$

当K1逼近1时，说明min2(SAD)>>min1(SAD)，此时可以忽略 min2(SAD)对应的候选样本像素点，直接以min1(SAD)对应的点为中 心展开SW2。由于min2(SAD)>>min1(SAD)，忽略min2(SAD)对应的点， 并不会陷入局部最优，在保证编码质量的同时，缩小了SW2的范围。 反之，当K1逼近0时，说明这两点的SAD很接近，为避免陷入局部 最优，此时需要根据两点的分布位置，进一步判断展开SW2。

情况三，当N＝3时，除了执行N＝2的步骤，先判断收敛系数K1 外，还需要根据公式(2)：

$K2=\frac{\min 3\left(\mathrm{SAD}\right)-\min 1\left(\mathrm{SAD}\right)}{\min 3\left(\mathrm{SAD}\right)}\left(2\right)$

判断第三点和第二点之间的收敛系数K2。同样当K2逼近1时， 忽略第三点，根据前两点的位置分布，展开SW2；当K2逼近0时， 根据三点的位置分布，进一步判断，展开SW2。

步骤五，对于SW2内所有的像素点，直接计算SAD值。由于H.264 中，对于一个16×16的宏块，有16×16、16×8、8×16、8×8、8 ×4、4×8、4×4七种分割方式，需要对每种分割方式分别计算出对 应的SAD值，所以共有1+2+2+4+8+8+16＝41个整数运动矢量IMV，此 时完成此次搜索。

由于视频图像中当前编码宏块与周围宏块有很强的空间相关性， 当候选样本像素点SAD值最小时，最佳匹配块在其周围出现的可能性 很大。与现有技术相比，本发明充分利用了这种空间相关性，自适应 的调整整数运动估计的搜索范围，同时可以根据用户的选择自行调整 图像的编码质量和运算复杂度，在牺牲一定编码质量且质量损失控制 在很小范围内时，大大提高搜索准确度，降低运算复杂度。根据减少 率G的计算公式：

$G=\frac{S_{\mathrm{FS}}/16+S_{\mathrm{SW}2}}{S_{\mathrm{FS}}}---\left(3\right)$

可以计算出减少搜索点数的百分比，其中S_FS表示全搜索方法需 要搜索的点数，S_FS/16表示经过第一步1/16亚采样之后需要的点数， S_SW2表示第二步进行SW2展开后需要搜索的点数。

与现有技术相比，本发明充分利用了前编码宏块与周围宏块的空 间相关性，自适应的调整整数运动估计的搜索范围，同时可以根据用 户的选择自行调整图像的编码质量和运算复杂度，在牺牲一定编码质 量且质量损失控制在很小范围内时，大大提高搜索准确度，降低运算 复杂度。

附图说明

图1为本发明中第一次展开的搜索窗SW1示意图；

图2为对SW1中的像素点进行亚采样示意图；

图3为当候选样本像素点个数N＝1时，搜索窗SW2展开的示意图；

图4为当候选样本像素点个数N＝2，且两点水平、垂直间距皆小 于15时，搜索窗SW2展开的示意图；

图5为当候选样本像素点个数N＝2，且两点水平间距大于15，垂 直间距小于15时，搜索窗SW2展开的示意图；

图6为当候选样本像素点个数N＝2，且两点水平、垂直间距皆大 于15时，搜索窗SW2展开的示意图；

图7为当候选样本像素点个数N＝3，且三点间最大的水平、垂直 间距皆小于15时，搜索窗SW2展开的示意图；

图8为当候选样本像素点个数N＝3，且三点间最大水平间距大于 15，最大垂直间距小于15时，搜索窗SW2展开的示意图；

图9为当候选样本像素点个数N＝3，且三点间最大水平、最大垂 直间距皆大于15时，搜索窗SW2展开的示意图；

图10为步骤四中根据设定的不同候选样本像素点的个数N以及 收敛系数、点间距，进行搜索窗SW2展开的判断流程；

图11为本发明的整数运动估计快速搜索方法的流程图。

具体实施方式

下面结合附图与具体实施案例，对本发明进行进一步的详细说 明：

如图11所示，本发明提供了一种用于H.264编码的整数运动估 计快速搜索方法，包括以下步骤：

步骤一，在参考帧中，根据设定的搜索范围，以搜索中心点展开 搜索窗SW1，如附图1所示，图中中心黑色的块表示搜索中心点，以 此为中心，展开大小为Searchrange_x*Searchrange_y的搜索窗 SW1，如图中阴影部分表示；

步骤二，将搜索窗SW1内所有的像素点进行亚采样。本发明中， 亚采样率为1/16，即在一行像素点中每四个像素点进行一次取点采 样，并且在垂直方向上每四行像素点进行一次取点采样，如附图2表 示。经过这两步采样过程之后，完成整个亚采样过程；

步骤三，对经过步骤二得到的样本像素点，以蛇形搜索的顺序， 从左上角的样本像素点开始，使用SAD(Sum of Absolute Difference， 绝对误差和)准则，其数学表达式如下：

$\mathrm{SAD}(i,j)=\underset{m=1}{\overset{M}{\Sigma }}\underset{n=1}{\overset{N}{\Sigma }}|f_k(m,n)-f_l(m+i,n+j)|---\left(4\right)$

其中，(i,j)为运动矢量分别在水平和垂直坐标位置上的分量， f_k，f_l分别为当前帧和参考帧的像素值，MxN为经过亚采样后样本像 素点的个数。经过计算SAD值进行匹配后，得到N个SAD值最小的候 选样本像素点，进行一下步的计算。其中，N是由外部设定的值，本 发明中设定其范围为1-3，N值越大，得到的候选样本像素点的个数 越多，编码图像质量越高，同时运算量也将增加。

步骤四，根据得到的候选样本像素点的分布位置，重新设定整数 运动估计的搜索范围，得到新的搜索窗SW2；根据N的不同取值以及 候选样本像素点的不同位置分布，下面将分别对不同情况进行说明。

情况一，当N＝1时，以唯一的候选样本像素点(x₁,y₁)为中心展开 新的搜索窗SW2，如图3所示。其中，向候选样本像素点的左边、上 边拓展8个像素点，右边、下边拓展7个像素点，得到SW2的大小为 16×16，即一个MB宏块(MicroBlock)的大小。

情况二，当N＝2时，得到两个候选样本像素点(x₁,y₁),(x₂,y₂)， 此时首先判断两点的收敛系数K1，如公式(1)：

$K1=\frac{\min 2\left(\mathrm{SAD}\right)-\min 1\left(\mathrm{SAD}\right)}{\min 2\left(\mathrm{SAD}\right)}\left(1\right)$

当K1逼近1时，由公式(1)可知，min2(SAD)远大于min1(SAD)， 此时可以认为(x₁,y₁)最优，舍弃点(x₂,y₂)并不会造成局部最优的问 题，接下来按着N＝1的步骤展开SW2。当K1逼近0时，说明min2(SAD) 的值接近min1(SAD)，展开SW2时需要同时考虑这两点，此时需要进 一步判定这两个点水平间距和垂直间距：

S1，当两点的水平间距和垂直间距都小于15时，则分别在两个 方向上进行拓展，将范围拓展至16×16。由于前面的步骤中是进行 1/16亚采样，所以当候选样本像素点的水平间距和垂直间距都小于 15时，其间距值只可能是固定值3、7、11，此时按照左边、上边的 拓展范围总比右边、上边多1，并且总范围为16×16的原则进行拓 展。如图4所示，此时两点之间的水平间距和垂直间距都为3，需要 向左边、上边拓展6个像素点，向右边、下边拓展5个像素点，最终 经拓展得到的SW2大小为16×16；

S2，当两点的水平间距和垂直间距，只有一个小于15，另一个 大于等于15时，对小于15的方向进行范围拓展至16，大于等于15 的方向上只需拓展1个像素点即可。如图5所示，两点之间水平间距 为15，垂直间距为3，则需要向左边、右边各拓展1个像素点，上边 拓展4个像素点，下边拓展3个像素点，经拓展后的SW2的大小为 19×16；

S3，当两点的水平间距和垂直间距，皆大于等于15时，在水平、 垂直方向上都只需拓展1个像素点即可。如图6所示，两点之间水平 间距、垂直间距皆为15，则经拓展后的SW2的大小为19×19；

情况三，当N＝3时，得到三个候选样本像素点 (x₁,y₁),(x₂,y₂),(x₃,y₃)，此时首先需要计算(x₁,y₁),(x₂,y₂)间的收敛 系数，步骤同N＝2。若K1逼近1，则直接忽略(x₂,y₂),(x₃,y₃)，只以(x₁,y₁) 为中心展开SW2；若K1逼近0，则根据公式2：

$K2=\frac{\min 3\left(\mathrm{SAD}\right)-\min 1\left(\mathrm{SAD}\right)}{\min 3\left(\mathrm{SAD}\right)}\left(2\right)$

继续计算(x₁,y₁),(x₃,y₃)间的收敛系数K2。同理，若K2逼近1， 则舍弃点(x₃,y₃)，以(x₁,y₁),(x₂,y₂)为中心展开SW2，步骤同N＝2时 SW2展开情况；若K2逼近0，此时需要进一步判定这三个点之间的最 大水平间距和最大垂直间距：

S1，当三点之间的最大水平间距和垂直间距都小于15时，则分 别在两个方向上进行拓展，将范围拓展至16×16。由于前面的步骤 中是进行1/16亚采样，所以当候选样本像素点的最大水平间距或最 大垂直间距都小于15时，其间距值只可能是3、7、11，此时按照左 边、上边的拓展范围总比右边、上边多1，并且总范围为16×16的 原则进行拓展。如图7所示，三点之间最大的水平间距为7，垂直间 距为7，则分别需要向左边、上边拓展4个像素点，右边、下边拓展 3个像素点，经拓展得到的SW2范围为16×16；

S2，当三点之间的最大水平间距和最大垂直间距，只有一个小于 15，另一个大于等于15时，对小于15的方向进行范围拓展至16， 大于等于15的方向上只需拓展1个像素点即可。如图8所示，三点 之间的最大水平间距为15，最大垂直间距为7，则需要向左边、右边 各拓展1个像素点，上边拓展4个像素点，下边拓展3个像素点，经 拓展后的SW2的大小为19×16；

S3，当三点之间的最大水平间距和最大垂直间距，皆大于等于 15时，在水平、垂直方向上都只需拓展1个像素点即可。如图9所 示，三点之间最大的水平间距为19，最大垂直间距皆为15，则经拓 展后的SW2的大小为23×19；

至此，完成SW2的展开，根据粗略搜索部分得到的N个候选样本 像素点，展开SW2的详细判断过程，如图10所示。

步骤五，对于SW2内所有的像素点，直接计算SAD值。由于H.264 中，对于一个16x16的宏块，有16x16、16x8、8x16、8x8、8x4、4x8、 4x4七种分割方式，需要对每种分割方式分别计算出对应的SAD值， 所以共有41个整数运动矢量IMV，此时完成此次搜索。

相比全搜索方法，本发明提出的一种用于H.264编码的整数运动 估计快速搜索方法，能有效减少搜索点数，进而减少计算量。计算量 减少率G的计算公式如下：

$G=\frac{S_{\mathrm{FS}}/16+S_{\mathrm{SW}2}}{S_{\mathrm{FS}}}---\left(3\right)$

其中S_FS表示全搜索方法需要搜索的点数，由外部设定的 Searchrange_x*Searchrange_y决定；S_FS/16表示经过第一步1/16亚 采样之后需要的点数，S_SW2表示第二步进行SW2展开后需要搜索的点 数。如当外部设定的SW1搜索范围 Searchrange_x*Searchrange_y＝64*32，候选样本像素点N＝2且收敛 系数K1逼近0时，此时SW2的范围为16x16，则减少率：

$G=\frac{64*32/16+16*16}{64*32}---18.75\%$

相比全搜索方法减少了81.25％的计算量。虽然相比全搜索方法， 编码图像的质量会有一定的下降，但是由于在SW1内经过了粗略搜 索、判断筛选之后再精细搜索SW2，编码图像的质量损失被控制在很 小的范围内，图像质量得到了保证。

由于视频图像中当前编码宏块与周围宏块有很强的空间相关性， 当候选样本像素点SAD最小时，最佳匹配块在其周围出现的可能性很 大。与现有技术相比，本发明充分利用了这种空间相关性，自适应的 调整整数运动估计的搜索范围，同时可以根据用户的选择自行调整图 像的编码质量和运算复杂度，在牺牲一定编码质量且质量损失控制在 很小范围内时，大大提高搜索准确度，降低运算复杂度。