Fast four-step search algorithm using UESA and quadrant selection approach for motion estimation

Humaira Nisar; Tae-Sun Choi

doi:10.1117/12.383021

Translator Disclaimer

19 April 2000 Fast four-step search algorithm using UESA and quadrant selection approach for motion estimation

Humaira Nisar; Tae-Sun Choi

Author Affiliations +

Proceedings Volume 3974, Image and Video Communications and Processing 2000; (2000) https://doi.org/10.1117/12.383021
Event: Electronic Imaging, 2000, San Jose, CA, United States

Abstract

Motion estimation has been widely used by various video coding standards. Full Search is the most straightforward and optimal block matching algorithm but its huge computational complexity is the major drawback. To overcome this problem several fast block matching motion estimation algorithms have been reported. In this paper a fast four step search algorithm based on the strict application of Unimodal Error Surface Assumption has been proposed. Quadrant Selection Approach has been adopted to reduce the computational complexity. The algorithm is adaptive in the sense that it can be stopped at the second or third step depending on the motion content of the block based on the Half Stop Technique. Simulation results show that the number of search points in our algorithm are almost half as compared to the conventional four step search algorithm. The total number of search points varies from 7 to 17 in our proposed algorithm. The worst case computational requirement is only 17 block matches. Our algorithm is robust, as the performance is independent of the motion of the image sequences. It also possesses regularity and simplicity of hardware oriented features.

Citation Download Citation

Humaira Nisar and Tae-Sun Choi "Fast four-step search algorithm using UESA and quadrant selection approach for motion estimation", Proc. SPIE 3974, Image and Video Communications and Processing 2000, (19 April 2000); https://doi.org/10.1117/12.383021

ACCESS THE FULL ARTICLE