Variable step search algorithm for motion estimation

Motion estimation (ME) is a key technique in interframe coding. It is the basis of most compression algorithms for video compression, such as the CCITT standard H. 261, and MPEG 2. The performance of ME is decided by two factors: (1) the estimation exactitude; and (2) the computational load. The full search algorithm is the optimal one for the first factor, but it requires extensive computations. To reduce the computational complexity, many efficient search algorithms have been proposed. The one step at a time search (OSATS) is the second most efficient algorithm, but it becomes inefficient when the search window is greater than 4 pels/frame. The aim of this paper is to overcome this disadvantage