This paper proposes a fast motion estimation algorithm for MPEG-4 shape coding. Motion estimation (ME) is essential to the improvement of the videl coding efficiency. However, most of the computational complexity for shape coding as well as texture coding is due to ME. Therefore, ME is a heavy burden for a real-time MPEG-4 coder. For several years, many researchers have focused on fast ME algorithms for texture coding. In this paper, we address a fast ME algorithm for shape coding. The proposed algorithm is based on inherent properties of shape coding as well as shape information, i.e., context-based motion estimation feature, motion vector(MV) correlation between neighbor binary alpha blocks (BAB's), and binary feature of shape information. By using these properties, the proposed algorithm can achieve a high processing speed. Simulation results show that our algorithm can reduce the computational complexity of ME for shape coding to 10% at least even in the worst case. And by combining the BBGDS algorithm with the proposed algorithm, we can reduce the computational complexity to 0.6% in the worst case. Therefore, the algorithm is suitable for real=time software applications of MPEG-4 shape encoding.
