双十字搜索算法的快速块匹配运动估计

Fast Block-Matching Motion Estimation Based on a Dual-Cross Search Algorithm

在块运动估计中,不同形状、不同大小的搜索模型对搜索速度和搜索质量有很大的影响.通过运动矢量概率分布分析,发现了运动矢量概率分布具有除中心十字偏置特性以外的方向性特性,提出了一种快速的双十字搜索(DCS)运动估计算法.该算法首先根据运动矢量概率分布的中心十字偏置性,采用小十字搜索模型(SCSP)和大十字搜索模型(LCSP)对小运动矢量进行搜索,从而减少搜索点数.然后,根据运动矢量概率分布的方向性,使用非完全对称十字搜索模型(NFSCSP)对大运动矢量进行搜索,进一步提高了搜索速度.在保持相当搜索质量的前提下,双十字搜索算法与菱形搜索算法(DS)和十字菱形搜索(CDS)算法相比,搜索速度分别可提高70%和40%.实验结果证明双十字搜索算法是非常有效的,且具有较强的鲁棒性.

In block motion estimation, search patterns with different shapes and/or sizes have a large impact on the searching speed and quality of performance. By statistical analysis of motion vector probabilities distribution, directional characteristic is found besides cross center-biased characteristic. A novel dual-cross search algorithm （DCS） is proposed. The proposed algorithm first employs the small cross search pattern （SCSP） and large cross search pattern （LCSP） to find small motion vectors with fewer search points based on cross-center-biased property. In addition, the algorithm uses no-full-symmetrical cross search pattern （NFSCSP） in the subsequent steps based on direction characteristic of motion vector probabilities distribution for large motion vectors. The improvement of DCS over DS and CDS can be a 70% and 40% gain on speedup, respectively, while maintaining comparable search quality. Experimental results show that the DCS is much more effective and robust.