Genetic algorithm approach to motion estimation for video compression

With the advance in VLSI technology as well as the increasing demand in multimedia applications, video compression has been a major research topic in both industrial and academic domain. Within the existing video coding standards, motion estimation is an important component in any coding system. It usually consumes most of the chip area and computational power. Thus, an efficient and effective algorithm for estimating motion information is defmitely a need in video technology. In this thesis, we have investigated the problem of block-based motion estimation. We have given a survey on the existing motion estimation algorithms, their merits and demerits. We also proposed parallel extensions to the conventional fast algorithms. Experimental results showed that the parallel approaches significantly improved the performance of the original algorithms. Furthermore, we have also proposed an innovative algorithm, namely Genetic Motion Search (GMS) algorithm. It employed an natural signal processing concept called Genetic Algorithm (GA). In contrast to the existing fast algorithms, which rely on the assumption that the matching error decreases monotonically as the searched point moves closer to the global optimum, GMS algorithm is not fundamentally limited by this assumption. The results from a full MPEG-1 simulation demonstrated that GMS is more robust and has a performance very close to that of full search algorithm but with a great reduction in complexity. Because of its regularity and highly parallelism in architecture, GMS algorithm is also suitable for VLSI implementation