On Computational Complexity of Motion Estimation Algorithms in MPEG-4 Encoder

Abstract: Video Encoding in mobile equipments is a computationally demanding feature that requires a well designed and well developed algorithm. The optimal solution requires a trade off in the encoding process, e.g. motion estimation with tradeoff between low complexity versus high perceptual quality and efficiency. The present thesis works on reducing the complexity of motion estimation algorithms used for MPEG-4 video encoding taking SLIMPEG motion estimation algorithm as reference. The inherent properties of video like spatial and temporal correlation have been exploited to test new techniques of motion estimation. Four motion estimation algorithms have been proposed. The computational complexity and encoding quality have been evaluated. The resulting encoded video quality has been compared against the standard Full Search algorithm. At the same time, reduction in computational complexity of the improved algorithm is compared against SLIMPEG which is already about 99 % more efficient than Full Search in terms of computational complexity. The fourth proposed algorithm, Adaptive SAD Control, offers a mechanism of choosing trade off between computational complexity and encoding quality in a dynamic way.