A New Efficient Block-Matching Algorithm for Motion Estimation

This paper presents a new full-search block-matching algorithm: Multi-stage Interval-based Motion Estimation algorithm (MIME). The proposed algorithm is a block based motion estimation algorithm that utilizes successive elimination technique. We define two approximate functions, as the upper and lower boundaries of the interval that includes the Conventional distortion metric SAD. Each stage in the proposed algorithm; except for the last stage; incorporates low resolution pixels for the boundary functions calculations. The final stage is a full resolution block matching stage. MIME has a high probability of finding the optimal motion vector at any stage of the algorithm. The proposed algorithm reduces the computational complexity by successively eliminating non-candidate blocks from the search window at each stage. This computational reduction leads to enhanced performance in terms of low power consumption and fast motion vector estimation. A low power VLSI implementation of the algorithm is also presented in this paper. Simulation results on benchmark video sequences shows that MIME algorithm eliminates almost 88% of the candidate blocks after only two interval based stages. Hanan Ahmed Hosny Mahmoud obtained the B.Sc. of Computer Science from Faculty of Engineering, University of Alexandria in 1986. She obtained her M.Sc. in Computer Science from Faculty of Engineering, University of Alexandria in 1991. She obtained the M.Sc. in Computer Engineering from University of Louisiana at Lafayette in 1999 and the Ph.D. in Computer Engineering from University of Louisiana at Lafayette in 2001. Currently, she is working as an Assistant Professor in the Faculty of Engineering, University of Alexandria. Sumeer Goel received the B. Tech degree in electronics and communications engineering from Punjab Technical University, Punjab, India, in 2001. He received the M.S. degree in computer engineering from University of Louisiana at Lafayette, Lafayette, LA, in 2003 where he is continuing his education towards Ph.D. degree in computer engineering. His research interests are low-power and high noise tolerance VLSI circuit and architecture design for digital signal processing applications. Mohsen Shaaban received his B.S. degree in electrical engineering and communications from the University of Alexandria, Egypt, in 1998. In 2001, he joined the University of Louisiana at Lafayette (ULL) as a teaching and research assistant at the Center For Advanced Computer Studies (CACS), the VLSI Research Lab. He received his M.S. degree in the field computer engineering from ULL in 2003. Currently, he is pursing his Ph.D. degree in the same field. His research interests include Digital VLSI circuit design, CAD tools and Video processing applications. Magdy A. Bayoumi received the B.Sc. and M.Sc. degrees in electrical engineering from Cairo University, Cairo, Egypt, in 1973 and 1977, the M.Sc. degree in computer engineering from Washington University in St. Louis, MO, in 1981, and the Ph.D. degree in electrical engineering from the University of Windsor, Windsor, ON, Canada, in 1984. Currently, he is the Director of the Center for Advanced Computer Studies (CACS), Department Head of the Computer Science Department, the Edmiston Professor of Computer Engineering, and the Lamson Professor of Computer Science at The Center for Advanced Computer Studies, University of Louisiana at Lafayette, where he has been a faculty member since 1985. He has edited and co-edited three books in the area of VLSI Signal Processing. He was an Associate Editor of the Circuits and Devices Magazine and is currently an Associate Editor of Integration, the VLSI Journal, and the Journal of VLSI Signal Processing Systems. He is a Regional Editor for the VLSI Design Journal and on the Advisory Board of the Journal on Microelectronics Systems Integration. He has one patent pending. His research interests include VLSI design methods and architectures, low power circuits and systems, digital signal processing architectures, parallel algorithm design, computer arithmetic, image and video signal processing, neural networks, and wideband network architectures. Dr. Bayoumi received the University of Louisiana at Lafayette 1988 Researcher of the Year Award and the 1993 Distinguished Professor Award. He was an Associate Editor of the IEEE CIRCUITS AND DEVICES MAGAZINE, the IEEE TRANSACTIONS ON VLSI SYSTEMS, the IEEE TRANSACTIONS ON NEURAL NETWORKS, and the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—II: ANALOG AND DIGITAL SIGNAL PROCESSING. From 1991 to 1994, he served on the Distinguished Visitors Program for the IEEE Computer Society, and he is on the Distinguished Lecture Program of the Circuits and Systems Society. He was the Vice President for the technical activities of the IEEE Circuits and Systems Society. He was the Co-chairman of the Workshop on Computer Architecture for Machine Perception in 1993, and is a member of the Steering Committee of this workshop. He was the General Chairman of the 1994 MWSCAS and is a member of the Steering Committee of this symposium. He was the General Chairman for the 8th Great Lake Symposium on VLSI in 1998. He has been on the Technical Program Committee for ISCAS for several years and he was the Publication Chair for ISCAS'99. He was also the General Chairman of the 2000 Workshop on Signal Processing Design and Implementation. He was a founding member of the VLSI Systems and Applications Technical Committee and was its Chairman. He is currently the Chairman of the Technical Committee on Circuits and Systems for Communication and the Technical Committee on Signal Processing Design and Implementation. He is a member of the Neural Network and the Multimedia Technology Technical Committees. Currently, he is the faculty advisor for the IEEE Computer Student Chapter at the University of Louisiana at Lafayette.