Hilbert scanning search algorithm for motion estimation

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