搜索
运动估计基础陈虎视频图像的冗余t空间冗余时间冗余视频图像的冗余视频序列图像在时间上存在很强的相关性，采用运动估计和运动补偿技术可以消除时间冗余以提高编码效率，这种技术广泛用于视频压缩的一些国际标准中，如H.261/263/264、MPEG-1/2/4。视频编码框架消除时间冗余当前图像块与参考图像对应块求差值相似图像块才能有效消除时间冗余图像块越相似，消除时间冗余效果越好采用运动搜索的方法寻找最相似的块运动估计与补偿运动以及运动搜索时间上目标的空间位移运动矢量通过搜索比较，确定相似块以及运动矢量的过程运动估计的分类全局运动估计基于块的运动估计基于象素点的运动估计基于区域的运动估计基于网格的运动估计时域运动估计频域运动估计（DFT、DCT、DWT）运动估计的分类a全局运动估计c基于块的运动估计b基于象素点的运动估计d基于区域的运动估计运动估计的分类a基于块的运动估计b基于网格的运动估计块匹配运动估计因算法简单、便于硬件实现得到广泛应用，本文将对其进行重点讨论，下面简称其为“运动估计”。基于块的运动估计基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。基于块的运动估计基于块的运动估计基于块的运动估计基于块的运动估计块匹配法基本流程搜索范围最佳匹配块运动矢量参考帧当前块当前帧NN分成互不重叠N×N大小的块，块遵循物体刚性平动的假设模型根据一定的匹配准则和搜索算法，在参考帧中给定的搜索范围内，寻找到当前块的最佳匹配块当前块和最佳匹配块之间的相对位移就是当前块的运动矢量匹配准则21111(,)(,)(,)MNiikkiimnMSExyfmnfmxnyMN均方误差：平均绝对误差：111(,)(,)(,)MNiikkiimnSADxyfmnfmxny绝对误差：1111(,)(,)(,)MNiikkiimnMADxyfmnfmxnyMN举例运动估计快速算法分类分层的和多分辨率的快速块匹配方法固定搜索模式的快速块匹配方法基于时空相关性和视觉特性的快速块匹配方法基于连续消除的快速块匹配方法基于象素子抽样的快速块匹配方法分层的或多分辨率法在较粗糙的分辨率下预测一个接近的大尺寸的运动矢量，然后在较高的分辨率下进一步修正。称为分层的或多分辨率的运动估计快速算法。缺点：计算过程复杂，内存需求较大。分层的或多分辨率法象素子抽样法通常的匹配准则是把块里所有的象素点进行计算和比较，事实上一个块里相邻象素的差别很小，使得它们之间也存在冗余。子采样运动估计算法就利用了这一事实，只取其中的一部分象素进行计算，可大大减少计算量，但同时降低了准确性。全搜索法对搜索区域的所有位置进行穷尽搜索。精度最高计算复杂，难以实时处理必须研究相应的运动估计快速算法三步法搜索模板半径依次减半对小运动检测效果不好搜索范围大于7时，搜索步骤不止三步梯度下降法反复使用3×3模板进行搜索。模板中心处SAD值最小时结束。对大运动检测效果不好四步法反复使用5×5方形模板进行搜索。模板中心处SAD值最小时再用3×3模板搜索一次确定最佳匹配位置。菱形法搜索方式与四步法类似，只是搜索模板换为两个菱形模板。六边形法搜索方式与菱形法类似，只是大搜索模板换为一个六边形模板。2D对数法反复使用3×3模板进行搜索。模板中心处边界时结束。比较2D对数法与全搜索法的比较水平、垂直方向最大位移为6固定模式搜索法的缺点没有利用图像本身的相关信息，不能根据物体运动的剧烈程度自适应的改变搜索起点和搜索半径。对于运动剧烈的图像，从原点开始搜索时，要经过多次搜索才能找到匹配点，搜索点过多，且容易陷入局部最优点。粒子群优化算法粒子群优化(ParticleSwarmOptimization,PSO)是由Kennedy和Eberhart在1995年共同提出的，源于对鸟群迁徙和鱼群聚集行为的启发。粒子群优化算法(1)()()()()()1122()()kkkkkkididdididddidvvcrandpbestxcrandgbestx(1)()(1)kkkidididxxv群体中的每个个体视为没有质量和体积的“粒子”，可以理解为是搜索空间中的点或者优化问题中的解。每个粒子都有自己的速度和空间位置，还有一个由目标函数决定的适应度值。在进化迭代过程中，每个粒子根据自身最优解和群体最优解更新自己的飞行速度大小和前进的方向。最终所有粒子向群体的最优解聚集，寻找到搜索空间的全局最优解。速度位置自身最优解群体最优解粒子群优化算法粒子群的搜索空间N粒子群优化运动估计运动估计的搜索空间D=2“粒子”粒子的位置粒子的速度“搜索点”搜索点的水平和垂直坐标搜索点的水平和垂直速度生物地理分布优化算法2008年，DanSimon提出了一种新型的智能优化算法，称为生物地理分布优化算法(Biogeography-basedOptimization-BBO)，该算法源于对生物地理分布情况的启发。生物地理分布优化算法BBO的搜索空间N生物地理分布优化运动估计运动估计的搜索空间D=2“岛屿”岛屿适合指数变量“搜索点”搜索点的水平和垂直坐标常用搜索算法总结全搜索法特点：效果最好、复杂度很高三步法、对数搜索法特点：效果一般、复杂度低、适应差钻石搜索法、十字搜索法特点：效果较好、复杂度低、适应较好群智能搜索法（遗传、粒子群、生物地理分布）特点：效果很好、复杂度较高、适应较好序列相关性和视觉特性人们针对序列图像的时空相关性和人眼视觉特性，提出了许多改进算法，主要可分类下面几类：预测搜索起点扁平搜索模板背景图像快速检测多预测点搜索预测搜索起点利用相邻块之间的运动相关性选择一个反映当前块运动趋势的预测点作为初始搜索点，这个预测点一般比原点更靠近全局最小点。从预测点开始搜索可以在一定程度上提高搜索速度和搜索精度。扁平搜索模板在序列图像中，大多数的运动矢量都位于水平或垂直方向，因此有些论文设计了扁平搜索模板（非对称搜索模板）来加快搜索速度。可参考十字菱形搜索法（CDS）。背景图像的快速检测由于一般序列中背景图像占有相当的比例，对背景图像的快速检测对搜索算法的性能提高很大。一般有两种方法：中止判别条件（门限一般设置512左右）从中心点开始用小模板检测多预测点搜索这种方法是根据邻块运动矢量预测多个搜索点，在搜索过程中选择预测性能最好的预测点，通常于小模板搜索方法想结合。预测方法至关重要。图像1图像2残差图像运动残差图像举例举例结果分析结果分析结果分析