Hilbert scanning search algorithm for motion estimation
Hilbert scanning search algorithm for motion estimation
复制标题
用于运动估计的希尔伯特扫描搜索算法
DOI：
10.1109/76.780357
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
H. Kuroda
中科院分区：
文献类型：
--
作者：
Yankang Wang;H. Kuroda
块匹配算法，如TSS和dwa /IS，被广泛用于低比特率视频编码中的运动估计。这些算法背后的假设是，当匹配块远离最优块时，它们之间的差异单调增加。不幸的是，这种假设往往是无效的，因此导致结果很有可能陷入局部最小值。在本研究中，我们提出了一种新的多候选搜索方案——希尔伯特扫描搜索算法（Hilbert scanning search algorithm， HSSA），该算法不需要全局单调性假设，可以通过对每个候选点的二叉搜索来有效地探索局部单调性。在HSSA中，可以调整初始候选者的数量和从一个阶段到下一个阶段控制候选者选择的阈值，以满足所需的搜索精度和/或速度。与传统的块匹配算法相比，在适当选择参数的情况下，HSSA收敛到最优结果的速度更快，精度更高。
Block-matching algorithms, such as TSS and DSWA/IS, are widely used for motion estimation in low-bit-rate video coding. The assumption behind these algorithms is that when the matching block moves away from the optimal block, the difference between them increases monotonically. Unfortunately, this assumption is often invalid, and therefore leads to a high possibility for the result to be trapped to local minima. In this research, we propose a new multiple-candidate search scheme, Hilbert scanning search algorithm (HSSA), in which the assumption of global monotonicity is not necessary and the local monotonicity can be effectively explored with binary search around each candidate. In HSSA, the number of initial candidates and a threshold to control the selection of candidates from one stage to the next can be adjusted to meet the required search accuracy and/or speed. With properly chosen parameters, the HSSA converges to their optimal results faster and with better accuracy than the conventional block-matching algorithms.