翻译 新三步搜索算法

新三步搜索算法块运动估计摘要三步搜索（TSS）算法由于其简单性和有效性，在一些低比特率视频压缩应用中被广泛用作运动估计技术。然而，TSS在其第一步中使用统一分配的检查点模式，对于小运动的估计而言效率低下。本文提出了一种新的三步搜索（NTSS）算法。NTSS的特点是在第一步中采用了一种中心偏差检查点模式，这是通过使搜索适应运动矢量分布而获得的，并且使用中途停止技术来降低计算成本。仿真结果表明，与TSS相比，NTSS更加稳健，运动补偿误差更小，计算复杂度更高。一·介绍运动估计在运动补偿的图像序列编码中起着重要的作用。由于全搜索方法的巨大计算需求，近十年来对快速运动估计算法的研究一直是研究的热点。在20世纪80年代初，提出了一些传统的快速算法，如三步搜索（TSS），二维对数搜索，共轭定向搜索等算法，由于其简单性和有效性，TSS成为低比特率视频应用（包括可视电话和视频会议）中最流行的一种。然而，TSS在其第一步中使用统一分配的搜索模式，对于捕捉出现在静止或静止块中的小运动效率不高。为了解决这个问题，已经提出了几种自适应技术来使搜索更适应运动规模和不确定性。文献[6]提出了一种动态搜索窗口方案，根据运动尺度的不确定性来调整搜索窗口尺寸。不确定性通过检查点之间的块失真度量（BDM）的差异来估计。较小的差异表示较大的不确定性，因此下一步搜索范围将会增加。否则，执行正常的TSS搜索或仅仅8邻近搜索。在[7]中，引入了一个多级方案。在每个阶段，将最小BDM与预定阈值进行比较，如果BDM值小于阈值，则停止搜索。否则，就进入下一个阶段。很显然，这两种算法采用多个阈值来控制搜索，这些阈值对算法的性能起着重要的作用。另一方面，随着处理过程中图像序列的变化，最佳阈值集合可能会发生变化，从而使其难以在实际应用中使用。本文提出了一种新的快速运动估计三步搜索算法（NTSS）。每一步的搜索模式是固定的，没有稿件于1994年4月3日收到。本文由香港电讯信息技术研究所（HKTHT）的研究资助，由孙明廷博士推荐。阈值操作涉及到这个算法。尽管如此，在低比特率视频应用中更好地利用现实世界图像序列的运动分布，并且在算法可能在第二或第三步停止的意义上是自适应的。结果表明，NTSS算法保留了原始TSS方法的简单性和规律性，在运动补偿误差和鲁棒性方面优于TSS，在计算复杂度方面与TSS相当。二·快速观测光栅的一个框架给定尺寸为N×N的块，块运动估计搜索在邻近区域内产生最小BDM的运动矢量（在先前帧中）。假设垂直和水平方向的最大运动是±W。然后，如果使用全搜索方法，则总共有（2W+1）²个运动矢量被检查，每个运动矢量对应于搜索窗口中的一个点。搜索窗口中所有点上的BDM值形成一个误差曲面（假设绝对误差为失真度量），其中（u,v）是候选运动向量，并且ft-r(.,.）和ft（.,.）指的是前一帧中的块和将要比较的当前帧。这个误差面的复杂性对算法的性能有显着的影响。所有传统的快速算法[1]-[7]明确或隐含地基于以下假设[3]：当检查点离开全局最小值时，BDM单调递增。显然，这个假设本质上要求误差曲面在搜索窗口上是单峰的。不幸的是，由于诸如孔径问题，纹理化（周期性）的局部图像内容，运动的物体和背景的不一致的块分割，帧之间的亮度变化等诸多原因，这通常是不正确的。结果，搜索很容易被困在当地的最低限度。在诸如TSS等多阶段搜索方案中，第一步的检查点在搜索窗口中统一分配。这样的结构对于观察到小运动的一些模块可能不是很合适，因此如何最优地设计该步骤的检查点模式成为主要关心的问题。尽管大空间尺度上的不确定性，我们可以合理地假设误差曲面在全局最小值附近的一个小邻域内是单调的。因此，如果其中一个检查点接近全局最小值，那么找到全局最小值的机会就会很高。在数学上，这可以被定义为具有定义为的目标函数的优化其中S由搜索区域中的所有点组成，c是最接近Xt的检查点，||·||代表欧几里德距离运动矢量分布从完全搜索导出100帧的（a）推销员序列和（b）美国小姐序列（块尺寸：16×16）。度量，P（Xi）是在X上出现全局最小值的概率。注意检查点数Ct的数量小于S的基数，否则就不需要设计，因为全面搜索是占上风的。要解决上述优化问题时，必须考虑全局最小值分布的一些基本特征。例如，以下属性是众所周知的：现实世界图像序列的块运动通常是平缓的，平滑的，变化缓慢，在低比特率视频应用中尤其如此。因此，全局最小分布是中心偏向的，而不是均匀分布的，正如图1所示的典型例子所证明的。对于推销员序列，有近80％的区块可以被认为是稳定的或者是平稳的固定块而且大部分的运动矢量被封闭在中央的5×5区域。对于美国小姐序列，与推销员相比，它的运动矢量分布更加多样化。但是，它仍然是高度偏中心的。利用这种特定形式的分布，检查点图案也应该是中心偏置的，以使平均距离d最小化。三·NTSS算法根据上节的讨论，我们现在提出一个可行的解决方案来优化问题，也称为一种新的三步搜索（NTSS）算法。NTSS与TSS的不同之处在于：（1）在第一步中假设一个中心偏差的检验点模式;（2）为平稳或者平稳的模块采用中途停止技术。详情如下：1）在第一步中，除了TSS中使用的原始检查点之外，还增加了八个额外的点，它们是搜索窗口中心的八个相邻点，如图2（a）所示。（因此，检查点模式是高度偏中心的。）2）为了快速识别和估计这些块的运动，对于平稳和平稳块使用中途停止技术：a）如果第一步中的最小BDM发生在搜索窗口中心，停止搜索。（这叫做第一步停止。）b）如果第一步中的最小BDM点是窗口中心的八个相邻点中的一个，则第二步中的搜索将仅对最小的八个相邻点执行，然后停止搜索。（这叫做第二步停止。）NTSS的框图如图2（b）所示。显然，它保留了TSS的简单性和规律性。可以看出，唯一需要执行完整的三步搜索的情况是，第一步的最小BDM点不是窗口中心，也不是其八个相邻点中的任何一个。由于在第一步中使用了这种新的中心偏置检查点模式，引入第一步停止技术似乎相当合理。对于这种情况，运动非常平缓，因此窗口中心认为代表了真实的运动矢量。对于发生第二步停止的情况，也很容易理解：（1）运动进一步变小;（2）第二步的执行使得估计更准确（因而是值得的）;（3）第二步之后发现真实动作的可能性非常高（从而证明第二步停止的合适性）。在低比特率视频应用中，搜索通常在15×15的区域进行，因此W=7。对于这样的选择，全搜索将检查225个点，而TSS检查25个点，从而导致加速比为9.尽管NTSS与TSS共同使用更多的检查点，但第一步停止和第二步停止可显着减少计算量。例如，一旦发生第一步停止，将会保存八个块匹配。取决于窗口中心的8个邻近的最小BDM点的位置（第一步），一旦发生二级停止，将会保存五个或三个块匹配：（1）如果最小值是沿着水平或垂直方向的四个相邻位置之一，则保存五个块匹配;（2）如果最小值是沿两个对角线方向的四个邻居中的一个，则将保存三个块匹配。实际上，用于估计块运动矢量的NTSS中所需的块匹配的数量可以通过17P1+20P2+22P’2+33（1-PI-P2-P’2）来估计，其中PI是发生第一步停止的概率，而P2和P’2分别是在上述两种情况下发生第二步停止的概率。这些概率取决于视频帧包含多少个平稳块。在诸如可视电话和视频会议的低比特率视频应用中，由于块运动是平缓的，并且背景通常是静止的，因此节省相当大。在最坏的情况下（即，没有单个静止块），与TSS所需的25个匹配相比，NTSS算法需要33个块匹配。'请注意，这八点中的一部分已经在第一步检查了。NTSS相对于全面搜索的实际加速比是总结在表一。与TSS的结果相比，我们看到NTSS和TSS基本上拥有相当可比的复杂计算能力。另一方面，基于测试图像序列，我们可以计算出如果出现第一步停止，全局最小BDM点（即真实运动矢量）位于搜索窗口的中心的概率以及如果第二步停止发生在这样的相邻点，则真实运动是窗口中心的八个相邻点之一的概率。对于推销员和美国小姐测试序列，观察到这样的概率接近于1，从而证明了NTSS算法的有效性。基于测试序列，我们也可以计算使用NTSS或TSS发现真实运动的总概率。这两个序列的概率也在表1中给出，从中可以看出，NTSS比TSS提供更高的概率。最后，为了进一步比较NTSS和TSS的有效性，计算它们的平均距离从（2）使用从全搜索中获得的运动矢量作为全局最小值。从表1我们可以看出，NTSS中使用的中心偏差模式的平均距离比TSS中的均匀分布模式要小得多。五·模拟在我们的模拟中，BDM被定义为平均绝对差（MAD）。块大小固定为16x16，行列最大运动假设为±7。我们使用了100帧推销员和美国小姐序列（以CIF格式）来测试NTSS算法，并将其与TSS和全面搜索进行比较。结果（均方误差测量）如图3所示。由此可见，NTSS几乎总是提供与全搜索相同的性能，而在许多帧中，TSS的性能劣化严重。此外，我们还测试了两个运动场子采样方案，以验证NTSS和TSS的稳健性：第一个是子块采样，第二个是2：1子块采样[8]。它们分别提供了4倍和2倍的额外加速比。图4给出了子块采样方案的仿真结果。一个有趣的现象是，推销员序列的运动补偿误差远低于图3中使用16×16块的情况。图5给出了2：1子块采样方案的结果。从这些仿真结果中可以清楚地看出，NTSS总是比TSS更好地工作，特别是当对运动场进行二次采样时，它比TSS更加稳健。五·结论在本文中，块运动估计（针对低比特率视频压缩）被制定为最优化问题，其中目标函数由平均距离度量来定义并且已经考虑了中心偏差约束。作为一种可行的解决方案，我们提出了一种新的快速运动估计三步搜索算法。我们在第一步中通过添加8个额外的检查点（它们是窗口中心的相邻点）来构建一个中心偏向的搜索点模式。这显著降低了平均距离。同时，我们引入了使用中途停止技术来保持NTSS算法在计算复杂度方面与TSS兼容。实验结果表明，与TSS相比，NTSS总是提供更小的运动补偿误差，特别是更好的稳健性，无论是单独使用还是结合运动场子采样技术。