Adaptive motion search with elastic diamond for MPEG-4 video coding

Video coding is a complex process, comprising a combination of spatial, temporal and statistical data reduction techniques. Of these techniques, motion estimation taking advantage of inter-frame information redundancy plays the most vital role. The overwhelming complexity of motion estimation using a brute-force search has prompted researchers to propose myriad of algorithms, yet finding the "most efficient" algorithm remains an open research problem. Recently, the MPEG-4 committee, after a rigorous evaluation, have recommended a motion estimation algorithm that performs very well in terms of speed and picture quality. In this paper, we propose a motion estimation algorithm that is a combination of a number of novel ideas for finding more accurate motion vectors and with a faster speed. The proposed algorithm, named as adaptive motion search with elastic diamond (AMSED) algorithm, takes advantages of the correlation between motion vectors in both spatial and temporal domains, and uses special diamond shape search patterns to accelerate motion search. The new algorithm achieves very close quality compared to full search but with several hundred times speedup. In term of speed, compared with the motion estimation technique recommended by the MPEG-4 committee, AMSED can achieve more than 200% speedup