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

Humaira Nisar; Tae-Sun Choi

doi:10.1117/12.383021

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

Humaira Nisar, Tae-Sun Choi

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

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available