Computer Science Colloquium, 2007-2008

Yair Moshe
University of Haifa
April 2, 2008

Title: Fast Block Motion Estimation Using Gray‐Code Kernels

Abstract:

Motion estimation plays an important role in modern video coders. In such coders, motion is estimated using a block matching algorithm that estimates the amount of motion on a block‐by‐block basis. A full search technique for finding the best matching blocks delivers good accuracy but is usually not practical because of its high computational complexity. In this talk, a novel fast block‐based motion estimation algorithm is presented. This algorithm uses an efficient projection framework which bounds the distance between a template block and candidate blocks. Fast projection is performed with a family of highly efficient filter kernels – the Gray‐Code Kernels – using only 2 operations per pixel for each filter kernel. The projection framework is combined with a rejection scheme which allows rapid rejection of candidate blocks that are distant from the template block. The tradeoff between computational complexity and quality of results could be easily controlled in the proposed algorithm, thus it enables adaptivity to image content to further improve the results. Experiments show that the proposed adaptive algorithm significantly outperforms popular fast motion estimation algorithms, such as three‐step search and diamond search.

*MSc. research under the supervision of Dr. Hagit Hel-Or.

 


Benny Pinkas