Motion estimation in video coding

Abstract

Motion Estimation (ME) is one of the most computational intensive operations in video compression. It can easily account for over 80% of the computation in an MPEG2 video encoder. Most ME algorithms can be formulated as an optimization problem and the challenge is to avoid being trapped at local minima without the expense of a full search in the optimization space. In this talk, we shall provide a comprehensive survey of existing ME algorithms in the literature, and present two new algorithms that we have developed. The first algorithm, the 'Edge-Pattern Search' (EPS) algorithm makes use of the visual patterns information in the video signal to provide clues for motion vector search. The second algorithm, the 'Adaptive Search Centre' (ASC) algorithm exploits the inter/intra frame information and a non-uniform distribution of the search points to guide the search process. Both algorithms give accurate ME similar to Full Search (FS) with a computational complexity similar to other less adequate fast algorithms like the Three Step Search (TSS).