This paper presents a multi-step motion estimation (MSME) algorithm, a new method for motion estimation in video sequences. Motion estimation methods are very important for interframe block matching, a key component used in most video codecs. The authors also describe many other motion estimation algorithms--full search (FS), “the optimal algorithm”; three-step search (TSS); four-step search (FSS); and diamond search (DS)--that they use in experimental comparisons.

The proposed MSME algorithm is:

a probabilistic approach to determine the initial candidate predictor that is the most probable search point for [the] first iteration [based on a central diamond point and outer points,] and it is followed by [a] refinement stage, which allows us to extract [the] true motion vector so that picture quality is as good as FS.

The MSME algorithm uses an early termination technique based on a fixed threshold. Note that FS is the best algorithm for solving this problem, but, as it does a full search, it is not as efficient as the other algorithms that are based on some heuristic techniques to reduce and accelerate the search. According to the authors, the MSME algorithm achieves better estimate accuracy than the other previously mentioned algorithms. MSME, FS, TSS, FSS, and DS were tested on several different video sequence fragments, to compare the peak signal-to-noise ratio (PSNR), the average number of search points per block (ASP), and the different bit rates.