Multigrid block matching motion estimation for generic video coding

Motion estimation and compensation techniques have shown their efficiency to reduce temporal redundancies in video coding applications. Motion estimation analyzes the movement of objects in the scene. The resulting motion information allows to improve interframe predictive coding. This work deals with the study of motion estimation algorithms in the framework of image sequence coding. The desired features of a motion estimation algorithm in order to achieve high performances are the following. First, the algorithm provides an accurate motion compensated prediction. Second, it requires a low overhead information. Third, it leads to a smooth motion field close to the true motion in the scene. However, it is straightforward that more precise motion vectors need a higher overhead information, and vice versa. Consequently, a trade-off on the motion estimation complexity has to be found in order to optimally balance these two conflicting features. The motion estimation algorithm developed in this dissertation takes into account the above remarks. Block matching techniques are a promising approach for motion estimation in image sequence coding. In this framework, the classical full-search algorithm is widely used due to its simplicity and ease of hardware implementation. Nevertheless, it suffers serious drawbacks. In particular, it performs poorly on moving edges and introduces block artifacts in the motion compensated frame. Furthermore, it tends to produce noisy motion fields. Finally, it requires a high computational complexity. In this study, we aim at overcoming the above drawbacks in order to fulfill all the above desired features of a motion estimation algorithm. In this dissertation, we propose a locally adaptive multigrid block matching motion estimation technique. The motion vectors are iteratively refined on a set of grids with different resolution. Due to this multigrid structure, the algorithm produces a low energy prediction error and a robust motion field close to the true motion in the scene. Furthermore, the computation complexity is greatly reduced. Introducing a locally varying grid size allows to improve the motion vectors accuracy on moving edges and to reduce the overhead information in uniform areas. Therefore, the locally adaptive multigrid block matching motion estimation outperforms the full-search technique in terms of motion vectors accuracy and smoothness, amount of overhead information, coding performances, visual quality of the reconstructed sequences, and computational complexity. In order to avoid the block artifacts related to the block matching techniques, a VQ-based segmentation of the motion field is proposed. Blocks which contain several objects moving in different directions are segmented by means of VQ and a different motion vector is assigned to each of the resulting regions. The method improves motion compensated prediction along moving edges, resulting in higher coding performances and enhanced visual quality.