The introduction of new, more powerful personal computers and workstations has ushered in a new era of computing. New machines are now capable of supporting full-motion video. The problem of video compression is a difficult and important one, and has inspired a great deal of research and development activity. A number of video compression techniques and standards have been introduced in the past few years, particularly MPEG for interactive multimedia and for digital NTSC and HDTV applications, and H.261/H.263 for video telecommunications. These techniques use motion estimation techniques to reduce the amount of data that is stored and transmitted for each frame of video.
This paper is about these motion estimation techniques, their implementations, their complexity, advantages, and drawbacks. An overview of the MPEG video compression standard is first presented with an emphasis on how it utilizes motion compensation to achieve its high compression gains. Then a survey of current motion estimation techniques is presented, including the exhaustive search and a number of fast block-based search algorithms.