快速运动估计算法

块匹配运动估计是用于帧间运动预测和减少时间冗余的常用技术。运动估计执行在当前图片中的当前块中进行搜索以找到参考图片中的最佳匹配块。

估计过程一般分为两步：

1. 整数像素级精度的估计。
2. 分数像素级精度的估计。

通常，在最佳整数像素位置周围以半像素和四分之一像素精度完成分数像素级运动搜索，并适当缩放所得到的运动矢量以保持精度。

运动估计是编码框架中最耗时的过程。运动估计的计算过程通常占整个编码过程的60％~90％，具体占比多少取决于配置和算法。因此，运动估计的快速执行对于实时视频应用非常重要。

有很多方法可以用来加速运动估计，例如：

• 可以采用搜索较少位置的方式来找到匹配的块。然而，如何确定待搜索的位置已经成为二十多年来的一个活跃的研究领域，并且产生了很多快速运动估计算法。如果搜索位置不正确，则很容易陷入局部最小值，进而错过搜索空间中的全局最小值，从而导致无法获取理想的运动矢量。 与将块简单地编码为帧内的情况相比，如果利用运动矢量从参考块来预测，则编码效率更高。因此，最终被编码为帧内块的块则无法利用现有的时间冗余。最近的算法通常在运动矢量的最可能候选者附近搜索以找到匹配块。基于相邻宏块的运动矢量，画面间的物体的运动趋势，或运动统计来形成预测的运动矢量。有的搜索算法使用重要性不同的多个搜索区域。例如，算法可以围绕预测的运动矢量开始搜索，并且如果需要，可以继续围绕参考图片中位于同一位置的宏块进行搜索。实验确定的阈值通常用于控制搜索流程。采用H.264和更高标准的相关软件使用了描述这些特征的快速搜索算法。
• 在每次搜索位置的过程中，可以利用部分信息而不是全部信息来匹配块。例如，从当前块中每隔一个像素选择一个像素，然后用选择出的像素与参考块中的对应像素匹配。
• 可以根据某些条件和实验确定的阈值来提前终止搜索。这种提前终止搜索的例子可以在Zhang等人提出的自适应运动估计技术中找到¹。该技术仅检查5个位置，从而将运动中的宏块的速度提高了约25％；即使对于静止的宏块而言，其性能也提高了约3％。并且该技术的平均PSNR损耗微不足道，大约为0.1 dB。
• 无需等到重建图片可用，可以采用源图像作为参考，从而节省了编码器所需要的重建过程。尽管此技术可明显提高性能，但它的缺点是预测误差会从一帧传播到下一帧，从而导致视觉质量的显著下降。
• 运动估计很容易以数据并行方式并行化。因为相同的块匹配操作（例如，SAD）将用于所有的匹配候选者，并且匹配的候选者之间彼此独立，因此可以轻松地使用SIMD并行化运动估计。此外，只要可以从参考图片中获得每个块的合适的搜索窗口，就可以并行执行每个块的运动估计。结合这两种方法，可以对每张图片使用SPMD（single program multiple data）类型的并行化。
• 使用按比例缩放的参考图片的层次结构，可以分别并行处理小数和整数像素部分，然后对结果进行组合。
• 在双向运动估计中，可以并行进行前向和后向估计。

¹. D. Zhang, G. Cao, and X. Gu, Improved Motion Estimation Based on Motion Region Identification. ↩