Computationally Efficient Lossy and Lossless Motion Estimation Algorithms.

Motion estimation is a key component of existing video compression systems, where motion estimation allows for significant compression by exploiting the temporal redundancy existing in successive frames of a video sequence. The exhaustive full search method is a block-based motion estimation approach that can provide optimal solutions to the motion estimation problem. However, the exceedingly high computational complexity of the full search method limits its practical applications. Therefore, it is desirable to design computationally efficient motion estimation algorithms that are lossless in terms of motion estimation accuracy as compared to the full search method. On the other hand, some very fast block-based motion estimation algorithms have been proposed in the literature, albeit at the expense of significant loss in the motion estimation accuracy as compared to the full search method. Therefore, it is desirable to improve the accuracies of these lossy motion estimation algorithms while achieving high computational efficiencies. To this end, several major contributions have been made by the work in this dissertation. First, we introduce an improved particle swarm optimization (PSO) technique to the problem of lossy block-based motion estimation and demonstrate that the new PSO-based method achieves significant improvements over the existing fast motion estimation methods in terms of motion estimation accuracy and computational cost. Second, we improve an existing projection-based block matching method for fast motion estimation in the literature, based on an in-depth analysis of the correlations between the matching metrics at different projection levels. While the original method is based on thresholds that are selected on an ad hoc basis, we introduce a new motion estimation method that allows thresholds to be chosen adaptively, thereby offering more scalable tradeoffs between motion estimation accuracy and computational complexity than the original method. Third, we improve the computational efficiency of the multi-level successive elimination algorithm, on which a family of lossless motion estimation methods represents the state of the art in fast block matching algorithms is based. We propose a multiple-pass approach to prioritize the block searching process. Simulation results demonstrate that the proposed multiple-pass method achieves significant speedups over the multi-level successive elimination algorithm, with especially remarkable improvements observed in video sequences with large motion.