视频运动估计.

视频运动估计1基本概念2方法分类3快速算法4H264运动估计视频图像序列在时间上存在很强的相关性，采用运动估计和运动补偿技术可以消除时间冗余以提高编码效率，这种技术广泛用于视频压缩标准，如H.261/263/264、MPEG-1/2/4。1基本概念2方法分类全局运动估计基于块的运动估计基于象素点的运动估计基于区域的运动估计基于网格的运动估计时域运动估计频域运动估计（DFT、DCT、DWT）运动估计的分类a全局运动估计c基于块的运动估计b基于象素点的运动估计d基于区域的运动估计运动估计的分类a基于块的运动估计b基于网格的运动估计块匹配运动估计因算法简单、便于硬件实现得到广泛应用。基于块的运动估计首先将图像序列帧分成许多互不重叠的宏块，假设宏块内所有象素的位移量都相同；然后对每个宏块在特定搜索范围内，根据匹配准则找出与当前块最相似的匹配块；最后计算相对位移（运动矢量）。视频压缩的时候，只需保存运动矢量和残差数据。匹配准则常见运动估计匹配准则有三种：MAD、MSE和NCCF；MAD没有乘除运算，实现简便，使用较多。通常使用求和绝对误差（SAD）代替MAD。全搜索法对搜索区域的所有位置进行穷尽搜索，精度最高计算复杂，难以实时处理必须研究相应的运动估计快速算法分层或多分辨率的快速块匹配方法固定搜索模式的快速块匹配方法基于时空相关性和视觉特性的快速块匹配方法基于连续消除的快速块匹配方法基于象素子抽样的快速块匹配方法3快速算法分层或多分辨率法包含两步：先粗测，再修正。在较粗糙的分辨率下预测一个接近的大尺寸的运动矢量，然后在较高的分辨率下进一步修正。称为分层的或多分辨率的运动估计快速算法。缺点：计算过程复杂，内存需求较大。连续消除法象素子抽样法通常的匹配准则是把块里所有的象素点进行计算和比较，事实上一个块里相邻象素的差别很小，使得它们之间也存在冗余。子采样运动估计算法就利用了这一事实，只取其中的一部分象素进行计算，可大大减少计算量，但同时降低了准确性。固定搜索模式法该方法假设匹配误差随着离全局误差最小点的距离增加而单调增加。一般从原点开始，采用固定的搜索模板和搜索策略得到最佳匹配块。著名算法有：三步法、梯度下降法、四步法、菱形法、六边形法等。三步法搜索模板半径依次减半对小运动检测效果不好搜索范围大于7时，搜索步骤不止三步第一步，以窗口中心为中心，步长为4，进行周围8个点搜索；第二步，以上步最佳匹配点为中心，步长为2继续搜索；第三步，步长为1继续搜索，最后得到最佳匹配点。共搜索25个点，FS需15×15点搜索。梯度下降法反复使用3×3模板进行搜索，模板中心处SAD值最小时结束。对大运动检测效果不好四步法反复使用5×5方形模板进行搜索。模板中心处SAD值最小时再用3×3模板搜索一次，确定最佳匹配位置。菱形法搜索方式与四步法类似，只是搜索模板换为两个菱形模板。六边形法搜索方式与菱形法类似，只是大搜索模板换为一个六边形模板。固定模式搜索法的缺点没有利用图像本身的相关信息，不能根据物体运动的剧烈程度自适应地改变搜索起点和搜索半径。以菱形法为例，对背景图像，也要经历从大模板到小模板的转换过程，至少需要13个搜索点，搜索速度还有待改进。对于运动剧烈的图像，从原点开始搜索时，要经过多次搜索才能找到匹配点，搜索点过多，容易陷入局部最优点。序列相关性和视觉特性针对固定模式法的不足，近几年来，人们针对序列图像的时空相关性和人眼视觉特性，提出了许多改进算法，主要可分为下面几类：预测搜索起点扁平搜索模板背景图像快速检测多预测点搜索预测搜索起点利用相邻块之间的运动相关性选择一个反映当前块运动趋势的预测点作为初始搜索点，这个预测点一般比原点更靠近全局最小点。从预测点开始搜索可以在一定程度上提高搜索速度和搜索精度。如预测搜索法（PSA）、自适应运动跟踪法（AMTS）。扁平搜索模板在序列图像中，大多数运动矢量都位于水平或垂直方向，因此扁平搜索模板（非对称搜索模板）可以加快搜索速度。如十字菱形搜索法（CDS）。背景图像的快速检测由于一般序列中背景图像占有相当的比例，对背景图像的快速检测对搜索算法的性能提高很大。一般有两种作用：中止判别条件（门限一般设置512左右）从中心点开始用小模板检测多预测点搜索这种方法是根据相邻块运动矢量预测多个搜索点，在搜索过程中选择预测性能最好的预测点，通常与小模板搜索方法相结合。如自适应十字模式搜索（ARPS）及其改进算法。预测路径选择和并行计算平台至关重要。多帧参考¼象素预测精度多块尺寸4H264的运动估计多帧参考帧间运动矢量复用¼预测精度亚象素全搜索法亚象素快速搜索多块尺寸H.264的优势和计算复杂度在相同的图像质量下，H.264所需码率约为MPEG-2的36%、H.263的51%、MPEG-4的61%，在很大程度上应归功于运动估计的这三个新特性。但是H.264的高性能是以计算复杂度为代价的。以运动估计为例，1/4象素预测需要大量的象素插值和匹配点运算，运动估计的计算复杂度还随参考帧和分块方式呈线性增加。而H.264中参考帧最多支持16个，分块模式共有7种，极大地增加了处理器的运行负担。因此，研究基于H.264的运动估计快速算法，是H.264标准走向实时应用的关键。