Département d'électricité, Institut de génie électrique et électronique IEL (Laboratoire de traitement des signaux 1 LTS1)

Multigrid block matching motion estimation for generic video coding

Dufaux, Frédéric ; Kunt, Murat (Dir.)

Thèse Ecole polytechnique fédérale de Lausanne EPFL : 1994 ; no 1221.

Ajouter à la liste personnelle
    Summary
    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. In a further stage, an entropy criterion is introduced to control the motion estimation procedure. By evaluating the transmission cost of both the prediction error and the overhead motion information, it achieves an optimization of the motion estimation and compensation. More precisely, it leads to the optimal trade-off on the motion estimation complexity given an allotted bandwidth. This method is applied in both the locally adaptive multigrid block matching technique and the VQ-based segmentation of the motion field. Finally, a generic video coding system is presented. It supports a wide range of applications and is suitable for multimedia services. Simulation results show good coding performances and high visual quality.
    Résumé
    Les techniques d'estimation et de compensation de mouvement ont montré leur efficacité afin de réduire la redondance temporelle dans le cadre du codage de séquences d'images. L'estimation de mouvement consiste analyser le déplacement des objets composants la scène. L'information de mouvement résultante permet d'améliorer le codage prédictif inter-image. Ce travail porte sur l'étude d'algorithmes d'estimation de mouvement pour les applications de codage de séquences d'images. Les propriétés désirées d'un algorithme d'estimation de mouvement afin d'obtenir de bonnes performances se résument comme suit. Premièrement, l'algorithme produit une prédiction compensée en mouvement précise. De plus, il ne nécessite que peu d'information complémentaire pour représenter le mouvement. Finalement, il engendre un champs de mouvement lisse, représentatif du mouvement dans la scène. Cependant, il est clair que des vecteurs de mouvement plus précis demandent plus d'information complémentaire, et vice versa. Par conséquent, un compromis sur la complexité de l'estimation de mouvement doit être trouvé afin de balancer de manière optimale ces deux propriétés en contradiction. L'algorithme d'estimation de mouvement développé dans cette dissertation prend en compte ces remarques. Les techniques d'appariement de blocs constituent une approche prometteuse pour l'estimation de mouvement dans le cadre du codage de séquences d'images. Dans ce contexte, l'algorithme classique de recherche exhaustive est largement utilisé, grâce à sa simplicité et sa facilité d'implantation en hardware. Néanmoins, il est caractérisé par certaines limitations. En particulier, son efficacité est faible sur le contour des objets en mouvement. D'autre part, il introduit des artefacts de blocs dans l'image compensée en mouvement. De plus, il tend à produire des champs de mouvement bruités. Finalement, il nécessite une grande complexité de calculs. Cette étude a pour but de résoudre ces limitations afin de satisfaire les propriétés désirées d'un algorithme d'estimation de mouvement telles que décrites ci-dessus. Dans cette dissertation, une technique d'estimation de mouvement multi-grille et localement adaptative par appariement de blocs est proposée. Les vecteurs de mouvement sont itérativement affinés sur une structure de grilles de résolutions différentes. Grâce à cette structure multi-grille, l'algorithme engendre simultanément une faible énergie de l'erreur de prédiction et un champs de mouvement robuste et proche du mouvement effectif dans la scène. De plus, la complexité de calculs est grandement réduite. En introduisant une taille de grille variant localement, d'une part une précision accrue des vecteurs de mouvement est obtenue sur le contour des objets en déplacement, et d'autre part la quantité d'information complémentaire est réduite dans les régions uniformes. Pour ces raisons, l'estimation de mouvement multi-grille et localement adaptative par appariement de blocs mène à des performances plus élevées lorsqu'elle est comparée à la technique de recherche exhaustive. Cette amélioration apparaît en termes de précision et robustesse des vecteurs de mouvement, quantité d'information complémentaire nécessaire, performances de codage, qualité visuelle de la séquence reconstruite, et complexité de calculs. Dans le but d'éviter les artefacts de blocs liés aux techniques d'appariement de blocs, une segmentation du champs de mouvement basée sur la quantification vectorielle est proposée. Les blocs contenant plusieurs objets se déplaçant dans des directions différentes sont segmentés par quantification vectorielle. A chacune des régions résultantes est assignée un vecteur de mouvement différent. La méthode améliore la compensation de mouvement le long des contours des objets en mouvement. Il en résulte des performances de codage plus élevées ainsi qu'une qualité visuelle augmentée. Dans une étape suivante, un critère entropique est introduit afin de contrôler la procédure d'estimation de mouvement. En évaluant les coûts de transmission relatifs à l'erreur de prédiction et à l'information complémentaire de mouvement, ce critère optimise la procédure d'estimation et de compensation de mouvement. Plus précisément, il permet d'obtenir le compromis optimal sur la complexité de l'estimation de mouvement, pour une largeur de bande donnée. Cette méthode est appliquée avec succès à la technique multigrille localement adaptative par appariement de blocs et à la segmentation du champs de mouvement basée sur la quantification vectorielle. Finalement, un système de codage générique des signaux vidéo est présenté. Ce système supporte une large variété d'applications et de ce fait est approprié pour les services multimédia. Les résultats de simulations montrent de bonnes performances en termes de codage ainsi qu'une haute qualité visuelle.