运动估计基础 陈虎

视频图像的冗余 空间冗余 时间冗余

视频图像的冗余 视频序列图像在时间上存在很强的相关性，采用运动估计和运动补偿技术可以消除时间冗余以提高编码效率，这种技术广泛用于视频压缩的一些国际标准中，如H.261/263/264、MPEG-1/2/4。

视频编码框架

消除时间冗余 当前图像块与参考图像对应块求差值 相似图像块才能有效消除时间冗余 图像块越相似，消除时间冗余效果越好 采用运动搜索的方法寻找最相似的块 运动估计 与补偿

运动以及运动搜索 时间上目标的空间位移 运动矢量 通过搜索比较，确定相似块以及运动矢量的过程

运动估计的分类 全局运动估计 基于象素点的运动估计 基于块的运动估计 基于区域的运动估计 基于网格的运动估计 时域运动估计 频域运动估计（DFT、DCT、DWT）

运动估计的分类 a 全局运动估计 b 基于象素点的运动估计 c 基于块的运动估计 d 基于区域的运动估计

运动估计的分类 a 基于块的运动估计 b 基于网格的运动估计 块匹配运动估计因算法简单、便于硬件实现得到广泛应用，本文将对其进行重点讨论，下面简称其为“运动估计”。

基于块的运动估计 基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。

基于块的运动估计

基于块的运动估计

基于块的运动估计

基于块的运动估计

块匹配法基本流程 分成互不重叠N×N大小的块，块遵循物体刚性平动的假设模型 根据一定的匹配准则和搜索算法，在参考帧中给定的搜索范围内，寻找到当前块的最佳匹配块 当前块和最佳匹配块之间的相对位移就是当前块的运动矢量

匹配准则 绝对误差： 均方误差： 平均绝对误差：

举例

运动估计快速算法分类 分层的和多分辨率的快速块匹配方法 基于连续消除的快速块匹配方法 基于象素子抽样的快速块匹配方法 固定搜索模式的快速块匹配方法 基于时空相关性和视觉特性的快速块匹配方法 基于连续消除的快速块匹配方法 基于象素子抽样的快速块匹配方法

分层的或多分辨率法 在较粗糙的分辨率下预测一个接近的大尺寸的运动矢量，然后在较高的分辨率下进一步修正。称为分层的或多分辨率的运动估计快速算法。 缺点：计算过程复杂，内存需求较大。

分层的或多分辨率法

象素子抽样法 通常的匹配准则是把块里所有的象素点进行计算和比较，事实上一个块里相邻象素的差别很小，使得它们之间也存在冗余。子采样运动估计算法就利用了这一事实，只取其中的一部分象素进行计算，可大大减少计算量，但同时降低了准确性。

全搜索法 对搜索区域的所有 位置进行穷尽搜索。 精度最高 计算复杂，难以实时 处理 必须研究相应的运动 估计快速算法

三步法 搜索模板半径依次减半 对小运动检测效果不好 搜索范围大于7时，搜索步骤不止三步

梯度下降法 反复使用3×3模板进行搜索。模板中心处SAD值最小时结束。 对大运动检测效果不好

四步法 反复使用5×5方形模板进行搜索。模板中心处SAD值最小时再用3×3模板搜索一次确定最佳匹配位置。

菱形法 搜索方式与四步法类似，只是搜索模板换为两个菱形模板。

六边形法 搜索方式与菱形法类似，只是大搜索模板换为一个六边形模板。

2D 对数法 反复使用3×3模板进行搜索。模板中心处边界时结束。

比较 2D对数法与全搜索法的比较 水平、垂直方向最大位移为6

固定模式搜索法的缺点 对于运动剧烈的图像，从原点开始搜索时，要经过多次搜索才能找到匹配点，搜索点过多，且容易陷入局部最优点。 没有利用图像本身的相关信息，不能根据物体运动的剧烈程度自适应的改变搜索起点和搜索半径。 对于运动剧烈的图像，从原点开始搜索时，要经过多次搜索才能找到匹配点，搜索点过多，且容易陷入局部最优点。

粒子群优化算法 粒子群优化 (Particle Swarm Optimization, PSO)是由Kennedy和Eberhart在1995年共同提出的，源于对鸟群迁徙和鱼群聚集行为的启发。

粒子群优化算法 群体中的每个个体视为没有质量和体积的“粒子”，可以理解为是搜索空间中的点或者优化问题中的解。 每个粒子都有自己的速度和空间位置，还有一个由目标函数决定的适应度值。在进化迭代过程中，每个粒子根据自身最优解和群体最优解更新自己的飞行速度大小和前进的方向。最终所有粒子向群体的最优解聚集，寻找到搜索空间的全局最优解。 速度 位置 群体最优解 自身最优解

粒子群优化算法 粒子群优化 运动估计 粒子群的搜索空间N 运动估计的搜索空间 D=2 “粒子” “搜索点” 粒子的位置 粒子群优化 运动估计 粒子群的搜索空间N 运动估计的搜索空间 D=2 “粒子” “搜索点” 粒子的位置 搜索点的水平和垂直坐标 粒子的速度 搜索点的水平和垂直速度

生物地理分布优化算法 2008年，Dan Simon提出了一种新型的智能优化算法，称为生物地理分布优化算法(Biogeography-based Optimization-BBO)，该算法源于对生物地理分布情况的启发。

生物地理分布优化算法 生物地理分布优化 运动估计 BBO的搜索空间N 运动估计的搜索空间 D=2 “岛屿” “搜索点” 岛屿适合指数变量 生物地理分布优化 运动估计 BBO的搜索空间N 运动估计的搜索空间 D=2 “岛屿” “搜索点” 岛屿适合指数变量 搜索点的水平和垂直坐标

常用搜索算法总结 全搜索法 特点：效果最好、复杂度很高 三步法、对数搜索法 特点：效果一般、复杂度低、适应差 钻石搜索法、十字搜索法 特点：效果较好、复杂度低、适应较好 群智能搜索法（遗传、粒子群、生物地理分布） 特点：效果很好、复杂度较高、适应较好

序列相关性和视觉特性 预测搜索起点 扁平搜索模板 背景图像快速检测 多预测点搜索 人们针对序列图像的时空相关性和人眼视觉特性，提出了许多改进算法，主要可分类下面几类： 预测搜索起点 扁平搜索模板 背景图像快速检测 多预测点搜索

预测搜索起点 利用相邻块之间的运动相关性选择一个反映当前块运动趋势的预测点作为初始搜索点，这个预测点一般比原点更靠近全局最小点。从预测点开始搜索可以在一定程度上提高搜索速度和搜索精度。

扁平搜索模板 在序列图像中，大多数的运动矢量都位于水平或垂直方向，因此有些论文设计了扁平搜索模板（非对称搜索模板）来加快搜索速度。可参考十字菱形搜索法（CDS）。

背景图像的快速检测 由于一般序列中背景图像占有相当的比例，对背景图像的快速检测对搜索算法的性能提高很大。一般有两种方法： 中止判别条件（门限一般设置512左右） 从中心点开始用小模板检测

多预测点搜索 这种方法是根据邻块运动矢量预测多个搜索点，在搜索过程中选择预测性能最好的预测点，通常于小模板搜索方法想结合。 预测方法至关重要。

图像1

图像2

残差图像

运动残差图像

举例

举例

结果分析

结果分析

结果分析

Thank You !