Motion estimation in video coding

Summary form only given. 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 MPEG-2 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 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 with a computational complexity similar to other less adequate fast algorithms like the three step search