翻译 新三步搜索算法.doc

《翻译 新三步搜索算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、新三步搜索算法块运动估计摘要三步搜索（TSS）算法由于其简单性和有效性，在一些低比特率视频压缩应用中被广泛用作运动估计技术。然而，TSS在其第一步中使用统一分配的检查点模式，对于小运动的估计而言效率低下。本文提出了一种新的三步搜索（NTSS）算法。NTSS的特点是在第一步中采用了一种中心偏差检查点模式，这是通过使搜索适应运动矢量分布而获得的，并且使用中途停止技术来降低计算成本。仿真结果表明，与TSS相比，NTSS更加稳健，运动补偿误差更小，计算复杂度更高。一·介绍运动估计在运动补偿的图像序列编码中起着重要的作用。由于全搜索方法的巨大计算

2、需求，近十年来对快速运动估计算法的研究一直是研究的热点。在20世纪80年代初，提出了一些传统的快速算法，如三步搜索（TSS），二维对数搜索，共轭定向搜索等算法，由于其简单性和有效性，TSS成为低比特率视频应用（包括可视电话和视频会议）中最流行的一种。然而，TSS在其第一步中使用统一分配的搜索模式，对于捕捉出现在静止或静止块中的小运动效率不高。为了解决这个问题，已经提出了几种自适应技术来使搜索更适应运动规模和不确定性。文献[6]提出了一种动态搜索窗口方案，根据运动尺度的不确定性来调整搜索窗口尺寸。不确定性通过检查点之间的块失真度量（BDM

3、）的差异来估计。较小的差异表示较大的不确定性，因此下一步搜索范围将会增加。否则，执行正常的TSS搜索或仅仅8邻近搜索。在[7]中，引入了一个多级方案。在每个阶段，将最小BDM与预定阈值进行比较，如果BDM值小于阈值，则停止搜索。否则，就进入下一个阶段。很显然，这两种算法采用多个阈值来控制搜索，这些阈值对算法的性能起着重要的作用。另一方面，随着处理过程中图像序列的变化，最佳阈值集合可能会发生变化，从而使其难以在实际应用中使用。本文提出了一种新的快速运动估计三步搜索算法（NTSS）。每一步的搜索模式是固定的，没有稿件于1994年4月3日收到

4、。本文由香港电讯信息技术研究所（HKTHT）的研究资助，由孙明廷博士推荐。阈值操作涉及到这个算法。尽管如此，在低比特率视频应用中更好地利用现实世界图像序列的运动分布，并且在算法可能在第二或第三步停止的意义上是自适应的。结果表明，NTSS算法保留了原始TSS方法的简单性和规律性，在运动补偿误差和鲁棒性方面优于TSS，在计算复杂度方面与TSS相当。二·快速观测光栅的一个框架给定尺寸为N×N的块，块运动估计搜索在邻近区域内产生最小BDM的运动矢量（在先前帧中）。假设垂直和水平方向的最大运动是±W。然后，如果使用全搜索方法，则总共有（2W+1）

5、²个运动矢量被检查，每个运动矢量对应于搜索窗口中的一个点。搜索窗口中所有点上的BDM值形成一个误差曲面（假设绝对误差为失真度量），其中（u,v）是候选运动向量，并且ft-r(.,.）和ft（.,.）指的是前一帧中的块和将要比较的当前帧。这个误差面的复杂性对算法的性能有显着的影响。所有传统的快速算法[1]-[7]明确或隐含地基于以下假设[3]：当检查点离开全局最小值时，BDM单调递增。显然，这个假设本质上要求误差曲面在搜索窗口上是单峰的。不幸的是，由于诸如孔径问题，纹理化（周期性）的局部图像内容，运动的物体和背景的不一致的块分割，帧之间的

6、亮度变化等诸多原因，这通常是不正确的。结果，搜索很容易被困在当地的最低限度。在诸如TSS等多阶段搜索方案中，第一步的检查点在搜索窗口中统一分配。这样的结构对于观察到小运动的一些模块可能不是很合适，因此如何最优地设计该步骤的检查点模式成为主要关心的问题。尽管大空间尺度上的不确定性，我们可以合理地假设误差曲面在全局最小值附近的一个小邻域内是单调的。因此，如果其中一个检查点接近全局最小值，那么找到全局最小值的机会就会很高。在数学上，这可以被定义为具有定义为的目标函数的优化其中S由搜索区域中的所有点组成，c是最接近Xt的检查点，

7、

8、·

9、

10、代表欧

11、几里德距离运动矢量分布从完全搜索导出100帧的（a）推销员序列和（b）美国小姐序列（块尺寸：16×16）。度量，P（Xi）是在X上出现全局最小值的概率。注意检查点数Ct的数量小于S的基数，否则就不需要设计，因为全面搜索是占上风的。要解决上述优化问题时，必须考虑全局最小值分布的一些基本特征。例如，以下属性是众所周知的：现实世界图像序列的块运动通常是平缓的，平滑的，变化缓慢，在低比特率视频应用中尤其如此。因此，全局最小分布是中心偏向的，而不是均匀分布的，正如图1所示的典型例子所证明的。对于推销员序列，有近80％的区块可以被认为是稳定的或者是

12、平稳的固定块而且大部分的运动矢量被封闭在中央的5×5区域。对于美国小姐序列，与推销员相比，它的运动矢量分布更加多样化。但是，它仍然是高度偏中心的。利用这种特定形式的分布，检查点图案也应该是中心偏置的，以使平