运动估计综述

运动估计综述第一页，共三十三页，2022年，8月28日图像的冗余

视频序列图像在时间上存在很强的相关性，采用运动估计和运动补偿技术可以消除时间冗余以提高编码效率，这种技术广泛用于视频压缩的一些国际标准中，如H.261/263/264、MPEG-1/2/4。第二页，共三十三页，2022年，8月28日运动估计的分类全局运动估计基于块的运动估计基于象素点的运动估计基于区域的运动估计基于网格的运动估计时域运动估计频域运动估计（DFT、DCT、DWT）第三页，共三十三页，2022年，8月28日运动估计的分类a全局运动估计c基于块的运动估计b基于象素点的运动估计d基于区域的运动估计第四页，共三十三页，2022年，8月28日运动估计的分类a基于块的运动估计b基于网格的运动估计块匹配运动估计因算法简单、便于硬件实现得到广泛应用，本文将对其进行重点讨论，下面简称其为“运动估计”。第五页，共三十三页，2022年，8月28日运动估计的定义基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。第六页，共三十三页，2022年，8月28日匹配准则

常见的运动估计匹配准则有三种：MAD、MSE和NCCF，由于MAD没有乘除操作，不需做乘法运算，实现简单方便，所以使用较多。通常使用求和绝对误差（SAD）代替MAD。第七页，共三十三页，2022年，8月28日全搜索法对搜索区域的所有位置进行穷尽搜索。精度最高计算复杂，难以实时处理必须研究相应的运动估计快速算法第八页，共三十三页，2022年，8月28日运动估计快速算法分类分层的和多分辨率的快速块匹配方法固定搜索模式的快速块匹配方法基于时空相关性和视觉特性的快速块匹配方法基于连续消除的快速块匹配方法基于象素子抽样的快速块匹配方法第九页，共三十三页，2022年，8月28日分层的或多分辨率法

在较粗糙的分辨率下预测一个接近的大尺寸的运动矢量，然后在较高的分辨率下进一步修正。称为分层的或多分辨率的运动估计快速算法。缺点：计算过程复杂，内存需求较大。第十页，共三十三页，2022年，8月28日连续消除法第十一页，共三十三页，2022年，8月28日象素子抽样法通常的匹配准则是把块里所有的象素点进行计算和比较，事实上一个块里相邻象素的差别很小，使得它们之间也存在冗余。子采样运动估计算法就利用了这一事实，只取其中的一部分象素进行计算，可大大减少计算量，但同时降低了准确性。第十二页，共三十三页，2022年，8月28日固定模式法

该方法假设匹配误差随着离全局误差最小点的距离增加而单调增加。一般从原点开始，采用固定的搜索模板和搜索策略得到最佳匹配块。著名的算法有：三步法、梯度下降法、四步法、菱形法、六边形法等，下边将分别予以介绍。第十三页，共三十三页，2022年，8月28日三步法搜索模板半径依次减半对小运动检测效果不好搜索范围大于7时，搜索步骤不止三步第十四页，共三十三页，2022年，8月28日梯度下降法反复使用3×3模板进行搜索。模板中心处SAD值最小时结束。对大运动检测效果不好第十五页，共三十三页，2022年，8月28日四步法反复使用5×5方形模板进行搜索。模板中心处SAD值最小时再用3×3模板搜索一次确定最佳匹配位置。第十六页，共三十三页，2022年，8月28日菱形法搜索方式与四步法类似，只是搜索模板换为两个菱形模板。第十七页，共三十三页，2022年，8月28日六边形法搜索方式与菱形法类似，只是大搜索模板换为一个六边形模板。第十八页，共三十三页，2022年，8月28日固定模式搜索法的缺点

没有利用图像本身的相关信息，不能根据物体运动的剧烈程度自适应的改变搜索起点和搜索半径。以菱形法为例，对背景图像，也要经历从大模板到小模板的转换过程，至少需要13个搜索点，搜索速度还有待改进。对于运动剧烈的图像，从原点开始搜索时，要经过多次搜索才能找到匹配点，搜索点过多，且容易陷入局部最优点。第十九页，共三十三页，2022年，8月28日序列相关性和视觉特性

针对固定模式法的不足，近几年来，人们针对序列图像的时空相关性和人眼视觉特性，提出了许多改进算法，主要可分类下面几类：预测搜索起点扁平搜索模板背景图像快速检测多预测点搜索第二十页，共三十三页，2022年，8月28日预测搜索起点利用相邻块之间的运动相关性选择一个反映当前块运动趋势的预测点作为初始搜索点，这个预测点一般比原点更靠近全局最小点。从预测点开始搜索可以在一定程度上提高搜索速度和搜索精度。可参考预测搜索法（PSA）、自适应运动跟踪法（AMTS）。

第二十一页，共三十三页，2022年，8月28日扁平搜索模板在序列图像中，大多数的运动矢量都位于水平或垂直方向，因此有些论文设计了扁平搜索模板（非对称搜索模板）来加快搜索速度。可参考十字菱形搜索法（CDS）。第二十二页，共三十三页，2022年，8月28日背景图像的快速检测由于一般序列中背景图像占有相当的比例，对背景图像的快速检测对搜索算法的性能提高很大。一般有两种方法：中止判别条件（门限一般设置512左右）从中心点开始用小模板检测，可参考CDHS算法第二十三页，共三十三页，2022年，8月28日多预测点搜索这种方法是根据邻块运动矢量预测多个搜索点，在搜索过程中选择预测性能最好的预测点，通常于小模板搜索方法想结合。可参考自适应十字模式搜索（ARPS）及其改进算法。预测方法至关重要。第二十四页，共三十三页，2022年，8月28日H.264标准中运功估计的新特点多帧参考¼象素预测精度多块尺寸第二十五页，共三十三页，2022年，8月28日多帧参考第二十六页，共三十三页，2022年，8月28日帧间运动矢量复用第二十七页，共三十三页，2022年，8月28日¼预测精度第二十八页，共三十三页，2022年，8月28日亚象素全搜索法第二十九页，共三十三页，2022年，8月28日亚象素快速搜索（一）第三十页，共三十三页，2022年，8月28日亚象素快速搜索（二）第三十一页，共三十三页，2022年，8月28日多块尺寸第三十二页，共三十三页，2022年，8月28日H.264的性能优势和计算复杂度

在相同的图像质量下，H.264所需码率约为MPEG-2的36%、H.263的51%、MPEG-4的61%，在很大程度上应归功于运动估计的这三个新特性。但是，H.264的高性能是以计算复杂度为代价的。以运动估计为例，1/4象