基于EPZS的运动估计算法的改进

引 言

目前，H.264 标准的视频编解码受到了广泛地应用，它的编码效率很高，但是运动估计作为编码的核心，其计算量也相当复杂，这就增加了时间损耗，严重降低了视频编解码的效率。近年来，运动估计一直被作为研究热点。

在各种视频编码标准中，块匹配运动估计算法是应用最广泛的。全局算法（FS）能得到最佳的运动矢量，但是计算量很大，严重降低了编码的实时性。为了减少算法的复杂度，很多算法被提出来，其中包括三步法[1]、四步法[2]、MVFAST[3] 等经典算法。而 EPZS（预测区域的搜索算法）是一种被 JM 模型采用的整像素运动搜索算法，它由局部逐渐向最佳点靠近，对于搜索范围较大的、运动很激烈的对象的搜索容易过早陷入局部最优[4]。

在充分分析 EPZS 算法的基础上，针对基于六边形改进的EPZS 算法搜索精度不高，搜索点数多的特点[5]，提出了对EPZS 终止搜索的条件以及搜索模板进行改进，改进优化后的算法搜索方向细化，精度更高，减少了搜索点数，降低了算法的复杂度，有效节省了运动估计的时间，增强了编码的实时性。

1 EPZS算法的介绍以及存在的不足

EPZS 搜索算法利用视频运动的空间和时间相关项，对当前编码的运动矢量进行预测，提出一种相邻块失真的提前终止准则来提前终止搜索 [6]，进一步来提高搜索速度，减少编码的复杂度。对于那些不能提前进行终止搜索的，利用搜索模板来进行相关运动矢量地完善。

1.1 计算提前终止搜索条件的不足

EPZS 根据相邻块的失真具有很高的相似度，而提出了一种基于相邻块失真的提前终止准则。通过提前终止准则，减少了算法的计算复杂度。在 EPZS 算法中，通过当前块 A 的左 侧块 B、正上方块 C、右上方块 D 三个相邻块的最小 SAD 值 来计算终止条件的标准 [7]（分别记为 SADB、SADC、SADD）。 由此可知，EPZS 计算终止搜索的条件过于简单，对于大多数 情况计算出来的搜索终止条件是满足的，但没有考虑到运动较 小或者静止情况下，这三个 SAD 的值非常接近 [8]，由此可知， 这样计算出来的 SAD 不一定是准确的。

1.2 EPZS的搜索模板的不足

改进后的EPZS 算法，搜索点数过多，对于运动较为复杂的运动场合，容易陷入局部最优而提前进入终止搜索，这样就会产生更大的误差。

2 改进后的 EPZS算法

对EPZS 算法的优化主要是针对其在计算终止搜索条件和搜索模板方面地优化，通过终止搜索阈值 T0 地设定和不同的搜索模板方法来对当前块在不同的范围内进行搜索，直至搜索到最佳点，得到最佳运动矢量。

2.1 搜索终止条件的优化

我们将起始搜索点的SAD 值记为SADM，由于起始预测搜索点最接近于最佳点，SAD 的值和SADM 的值相关性越大， 我们可以更快地利用终止搜索的条件来得到最佳的 SAD 值， 我们设定终止搜索的阈值为 T0，如下公式所示：

T0=min（SADM，SADB，SADC，SADD）

2.2 精细搜索模板的改进

通过研究各种搜索模板，我们可以发现搜索模板越是接近圆形，其搜索性能越好 [9]，因为圆形的方向覆盖全，搜索范围更精确，更容易让我们找到最佳点，从而得到最佳运动矢量，而这里十二边形无限接近于圆形，它共有 13 个点分别为（0，0）、（1，4）、（3，3）、（4，1）、（4，－ 1）、（3，－ 3）、（1，－ 4）、（－1，－ 4）、（－3，－ 3）、（－4，-1）、（－4，1）、（－3，3）、（－1，4），搜索中心点和外围的 12 个不同方向的点，求得最佳点，判断搜索到的点是不是最佳点，如不是以此点为中心进行非对称十字形搜索，判断是否为最佳点，直到最佳点为中心点，此时的向量为最佳运动矢量MV。利用十二边形进行最佳点方向的判断搜索，方向覆盖更全面，减少了搜索点数，能够很快很好地得到最佳点，从而得到最佳运动矢量。

这里采用小菱形搜索模板[10]、非对称十字形搜索模板和（类圆形）十二边形的搜索模板。模板如图 1 所示：

（a）小钻石形（b）非对称十字形（c）十二边形

图1 搜索模板

在初始化搜索点后，对块类型进行判别来选择相应的模板进行搜索最佳点，然后进行阈值判断来判别是否终止搜索。算法的搜索步骤和流程如图 2 所示。

算法的搜索步骤如下： 

（1）判断当前块是否是静止块，若是静止块直接跳入步 骤（5），否则进入步骤（2）。 

（2）判断当前块是小运动块还是大运动块，如果当前块 为小运动块，即运动平缓，则进入步骤（3），否则进入步骤（4）。 

（3）当前块为小运动块，对其进行小钻石形模板搜索， 直到 SAD 小于阈值 T0，得到最佳运动矢量。 

（4）当前块为大运动块，即运动比较激烈，此时应该先 进行初始搜索点预测，然后对其进行十二边形模板搜索，对 得到的 SAD 进行分析，是否为最佳点，若为最佳点，则对其 进行小钻石形模板搜索，直到得到最佳运动矢量 ；若不是最 佳点则对其进行非对称十字形搜索，然后再次判断是否为最 佳点，若不是则一直进行非对称十字形搜索，直到得到 SAD 最佳点，然后再对其最佳点进行小钻石型搜索，直到 SAD 小 于阈值 T0，得到最佳运动矢量。 

（5）搜索结束。 本文是以 H.264 官方的标准测试模型 JM 10.1 为平台， 在此基础上对改进算法进行测试的实验。优化后的算法和基 于六边形改进的 EPZS 算法相比较，在不影响图像质量的前提 下，运动估计的时间明显减少，搜索效率明显提高。

结 语

本文基于EPZS（预测区域的搜索算法）来展开分析和讨论，充分利用图像运动的空间域和时间域的相关特性，利用初始预测矢量和阈值终止标准来进行相关运动矢量地求解。改进后的算法在搜索中使用小钻石形、非对称十字形以及十二边形等搜索模板，在保证图像恢复质量不变的情况下，运动估计时间明显减少，特别是对运动对象较为剧烈的场合有显著的效果，编码效率有了显著地提高，提高了视频运动序列编码的实时性，具有一定的实用价值。