A multi-stage multi-candidate algorithm for motion estimation

Motion compensation using the optimal full search algorithm is often too computationally heavy for real-time implementation. Many suboptimal fast search algorithms have been proposed. In particular, Liu and Zaccarin (1993) proposed the alternating subsampling search algorithm (ASSA). The ASSA reduces the computation by subsampling the pixels instead of limiting the search locations. It was shown that ASSA has nearly the same MSE performance as the full search but its complexity is only 1/4 of the full search. We generalize the idea to the multi-stage case. Simulation results show that the proposed algorithm has a comparable performance to the ASSA but it has a much lower computational cost