Abstract

The block-matching motion estimation (BME) is one of the most commonly used techniques for digital video compression in low to moderate bit rate environments. The full search for block-matching motion estimation, as compared to a partial search, provides a higher motion estimation accuracy, yet its computational cost is generally high. Hence, developing new techniques for an efficient implementation of full-search algorithms is of practical significance for the BME. In this thesis, a new full search algorithm is proposed, wherein the mean squared error (MSE) is used as the matching criterion to provide a higher motion estimation accuracy for the BME than that by any algorithm based on the most commonly-used mean absolute difference. It is shown that the computation of the MSE in the Haar wavelet domain results in a computational complexity that is much lower than or of the same order as that of the best-performing full search algorithms available in the literature. A new approach has been developed for the multi-reference-frame block-matching motion estimation, wherein a full search is performed in the spatial domain of the multi-reference-frame memory, and an early termination is imposed in the temporal domain using a novel strategy. It is shown that the computational complexity of the proposed full search method is significantly lower than that of any existing full search technique, and yet has a motion estimation accuracy which is about the same as that of the latter. A new pseudo-spiral-scan data input scheme has been proposed, which can be used in any existing hardware architecture for the implementation of the successive-elimination-based block-matching motion estimation. This scheme results in significant power savings compared to the conventional raster-scan data input scheme. Several designs to implement the successive elimination algorithm have been given, some of which are shown to provide additional power savings.