Motion estimation (ME) plays a key role in the video coding area like H.263 and MPEG-4. To estimate a motion vector (MV), we first find an integer-pixel MV in a wide search area, then estimate a half-pixel MV neighboring the integer-pixel MV. Computation complexity for half-pixel ME is negligible compared with that of integer-pixel full search ME. However, as fast integer-pixel ME algorithms have been developed, they can find an integer MV under 10 search points. Therefore, the development of fast half-pixel ME algorithm becomes important. Hence, in this paper, we aim to develop a novel fast half-pixel ME algorithm.
Most existing fast half-pixel ME algorithms search neighboring 4 points of the integer-pixel MV, and then diagonal points are searched. In the proposed algorithm, however, we first find components of x and y directions MV, respectively, in the directionally reduced image area. Then we can skip diagonal-point searching according to the component values. This algorithm decreases the number of pixels to be interpolated, computation burden of MAD, and the number of search points. The proposed algorithm is about 3 times faster than the full search half-pixel ME algorithm.
