Faculté des sciences et techniques de l'ingénieur STI, Section de génie électrique et électronique, Institut de traitement des signaux ITS (Laboratoire de traitement des signaux 2 LTS2)

Toward sparse and geometry adapted video approximations

Divorra Escoda, Òscar ; Vandergheynst, Pierre (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3299.

Ajouter à la liste personnelle
    Summary
    Video signals are sequences of natural images, where images are often modeled as piecewise-smooth signals. Hence, video can be seen as a 3D piecewise-smooth signal made of piecewise-smooth regions that move through time. Based on the piecewise-smooth model and on related theoretical work on rate-distortion performance of wavelet and oracle based coding schemes, one can better analyze the appropriate coding strategies that adaptive video codecs need to implement in order to be efficient. Efficient video representations for coding purposes require the use of adaptive signal decompositions able to capture appropriately the structure and redundancy appearing in video signals. Adaptivity needs to be such that it allows for proper modeling of signals in order to represent these with the lowest possible coding cost. Video is a very structured signal with high geometric content. This includes temporal geometry (normally represented by motion information) as well as spatial geometry. Clearly, most of past and present strategies used to represent video signals do not exploit properly its spatial geometry. Similarly to the case of images, a very interesting approach seems to be the decomposition of video using large over-complete libraries of basis functions able to represent salient geometric features of the signal. In the framework of video, these features should model 2D geometric video components as well as their temporal evolution, forming spatio-temporal 3D geometric primitives. Through this PhD dissertation, different aspects on the use of adaptivity in video representation are studied looking toward exploiting both aspects of video: its piecewise nature and the geometry. The first part of this work studies the use of localized temporal adaptivity in subband video coding. This is done considering two transformation schemes used for video coding: 3D wavelet representations and motion compensated temporal filtering. A theoretical R-D analysis as well as empirical results demonstrate how temporal adaptivity improves coding performance of moving edges in 3D transform (without motion compensation) based video coding. Adaptivity allows, at the same time, to equally exploit redundancy in non-moving video areas. The analogy between motion compensated video and 1D piecewise-smooth signals is studied as well. This motivates the introduction of local length adaptivity within frame-adaptive motion compensated lifted wavelet decompositions. This allows an optimal rate-distortion performance when video motion trajectories are shorter than the transformation "Group Of Pictures", or when efficient motion compensation can not be ensured. After studying temporal adaptivity, the second part of this thesis is dedicated to understand the fundamentals of how can temporal and spatial geometry be jointly exploited. This work builds on some previous results that considered the representation of spatial geometry in video (but not temporal, i.e, without motion). In order to obtain flexible and efficient (sparse) signal representations, using redundant dictionaries, the use of highly non-linear decomposition algorithms, like Matching Pursuit, is required. General signal representation using these techniques is still quite unexplored. For this reason, previous to the study of video representation, some aspects of non-linear decomposition algorithms and the efficient decomposition of images using Matching Pursuits and a geometric dictionary are investigated. A part of this investigation concerns the study on the influence of using a priori models within approximation non-linear algorithms. Dictionaries with a high internal coherence have some problems to obtain optimally sparse signal representations when used with Matching Pursuits. It is proved, theoretically and empirically, that inserting in this algorithm a priori models allows to improve the capacity to obtain sparse signal approximations, mainly when coherent dictionaries are used. Another point discussed in this preliminary study, on the use of Matching Pursuits, concerns the approach used in this work for the decompositions of video frames and images. The technique proposed in this thesis improves a previous work, where authors had to recur to sub-optimal Matching Pursuit strategies (using Genetic Algorithms), given the size of the functions library. In this work the use of full search strategies is made possible, at the same time that approximation efficiency is significantly improved and computational complexity is reduced. Finally, a priori based Matching Pursuit geometric decompositions are investigated for geometric video representations. Regularity constraints are taken into account to recover the temporal evolution of spatial geometric signal components. The results obtained for coding and multi-modal (audio-visual) signal analysis, clarify many unknowns and show to be promising, encouraging to prosecute research on the subject.
    Summary
    Video signals are sequences of natural images, where images are often modeled as piecewise-smooth signals. Hence, video can be seen as a 3D piecewise-smooth signal made of piecewise-smooth regions that move through time. Based on the piecewise-smooth model and on related theoretical work on rate-distortion performance of wavelet and oracle based coding schemes, one can better analyze the appropriate coding strategies that adaptive video codecs need to implement in order to be efficient. Efficient video representations for coding purposes require the use of adaptive signal decompositions able to capture appropriately the structure and redundancy appearing in video signals. Adaptivity needs to be such that it allows for proper modeling of signals in order to represent these with the lowest possible coding cost. Video is a very structured signal with high geometric content. This includes temporal geometry (normally represented by motion information) as well as spatial geometry. Clearly, most of past and present strategies used to represent video signals do not exploit properly its spatial geometry. Similarly to the case of images, a very interesting approach seems to be the decomposition of video using large over-complete libraries of basis functions able to represent salient geometric features of the signal. In the framework of video, these features should model 2D geometric video components as well as their temporal evolution, forming spatio-temporal 3D geometric primitives. Through this PhD dissertation, different aspects on the use of adaptivity in video representation are studied looking toward exploiting both aspects of video: its piecewise nature and the geometry. The first part of this work studies the use of localized temporal adaptivity in subband video coding. This is done considering two transformation schemes used for video coding: 3D wavelet representations and motion compensated temporal filtering. A theoretical R-D analysis as well as empirical results demonstrate how temporal adaptivity improves coding performance of moving edges in 3D transform (without motion compensation) based video coding. Adaptivity allows, at the same time, to equally exploit redundancy in non-moving video areas. The analogy between motion compensated video and 1D piecewise-smooth signals is studied as well. This motivates the introduction of local length adaptivity within frame-adaptive motion compensated lifted wavelet decompositions. This allows an optimal rate-distortion performance when video motion trajectories are shorter than the transformation "Group Of Pictures", or when efficient motion compensation can not be ensured. After studying temporal adaptivity, the second part of this thesis is dedicated to understand the fundamentals of how can temporal and spatial geometry be jointly exploited. This work builds on some previous results that considered the representation of spatial geometry in video (but not temporal, i.e, without motion). In order to obtain flexible and efficient (sparse) signal representations, using redundant dictionaries, the use of highly non-linear decomposition algorithms, like Matching Pursuit, is required. General signal representation using these techniques is still quite unexplored. For this reason, previous to the study of video representation, some aspects of non-linear decomposition algorithms and the efficient decomposition of images using Matching Pursuits and a geometric dictionary are investigated. A part of this investigation concerns the study on the influence of using a priori models within approximation non-linear algorithms. Dictionaries with a high internal coherence have some problems to obtain optimally sparse signal representations when used with Matching Pursuits. It is proved, theoretically and empirically, that inserting in this algorithm a priori models allows to improve the capacity to obtain sparse signal approximations, mainly when coherent dictionaries are used. Another point discussed in this preliminary study, on the use of Matching Pursuits, concerns the approach used in this work for the decompositions of video frames and images. The technique proposed in this thesis improves a previous work, where authors had to recur to sub-optimal Matching Pursuit strategies (using Genetic Algorithms), given the size of the functions library. In this work the use of full search strategies is made possible, at the same time that approximation efficiency is significantly improved and computational complexity is reduced. Finally, a priori based Matching Pursuit geometric decompositions are investigated for geometric video representations. Regularity constraints are taken into account to recover the temporal evolution of spatial geometric signal components. The results obtained for coding and multi-modal (audio-visual) signal analysis, clarify many unknowns and show to be promising, encouraging to prosecute research on the subject.
    Résumé
    Le signal vidéo est une séquence d'images en mouvement, dont les images sont souvent modelées comme des signaux réguliers par morceaux. Ainsi, le signal vidéo peut être considéré comme un signal 3D régulier par morceaux, et composé de régions qui suivent un certain mouvement a travers le temps. La modélisation du signal vidéo par morceaux permet d'analyser en détail le comportement de différentes stratégies de codage, et ainsi de déterminer quelles sont les approches les plus appropriées pour maximiser le taux de compression. Afin de permettre un codage efficace de la vidéo, il est nécessaire d'utiliser des méthodes adaptatives de décomposition du signal. Cette adaptabilité doit être optimisée pour garantir une modélisation du signal avec un coût de codage minimum. La nature du signal vidéo est fortement liée à sa structure, avec une forte composante géométrique. Celle-ci inclut tant la géométrie temporelle (normalement représentée par l'information du mouvement) que la géométrie spatiale. La plupart des méthodes utilisées pour la représentation du signal vidéo ne tient pas compte de sa géométrie spatiale. De même que dans le cas des images, une stratégie prometteuse pour exploiter conjointement la structure géométrique spatio-temporelle est celle qui utilise des dictionnaires redondants avec une forte composante géométrique. Dans le contexte de la vidéo, les primitives géométriques 2D doivent suivre une évolution temporelle en formant des complexes primitives 3D qui ont la fonction de représenter, en même temps, les composantes géométriques spatiales et temporelles du signal. Dans cette thèse de doctorat, plusieurs aspects concernant l'utilisation de méthodes adaptatives pour la modélisation du signal vidéo sont traités. Cette thèse traite particulièrement des aspects structurels de la vidéo ainsi que de sa nature géométrique. La première partie du présent travail porte sur l'étude de l'utilisation de décompositions temporelles adaptatives dans des approches basées sur la décomposition de la vidéo en sous-bandes. L'influence de l'adaptabilité est notamment discutée pour deux stratégies de codage: les transformées en ondelettes 3D et le filtrage temporel avec compensation de mouvement. Les avantages de l'utilisation d'adaptabilité dans des représentations basées sur la transformée en ondelettes 3D sont démontrés à l'aide d'une étude théorique R-D ainsi que par des résultats expérimentaux. L'utilisation de l'adaptabilité dans le cadre du filtrage temporel avec compensation du mouvement est aussi étudiée en faisant une analogie entre le signal vidéo, avec le mouvement compensé, et les signaux réguliers par morceaux 1D. Cette analogie suggère l'introduction des transformées de longitude localement variable dans des schémas de décomposition par ondelettes bases sur des lifting steps. Cette modification permet une plus forte compression du signal grâce à une meilleure adaptation de la représentation des trajectoires de mouvement avec une longueur inférieure à celle du Groupe d'Images (GOP - en anglais -) ou quand l'erreur due à la compensation de mouvement est trop élevé. Après l'étude d'adaptabilité temporelle, une deuxième partie de cette thèse se concentre également sur l'étude et la compréhension des concepts de base pour exploiter, conjointement, la structure géométrique spatio-temporelle du signal. Cette recherche se base sur des études précédentes qui tenaient compte de la géométrie spatiale de la vidéo, sans considérer son évolution temporelle (mouvement). Afin d'obtenir des représentations flexibles et efficaces (parcimonieuses), avec des dictionnaires redondants, il faut utiliser des algorithmes de décomposition hautement non linéaires, tels que les algorithmes gloutons (Greedy algorithms et Matching Pursuits en anglais). L'utilisation de ces techniques est encore peu explorée. Pour cette raison, avant d'étudier de telles représentations, certains aspects liés à l'utilisation de ces algorithmes conjointement avec des dictionnaires cohérents pour l'approximation des images et de la vidéo sont étudiés. Une partie de cette étude présente l'utilisation des modèles à priori dans des algorithmes non-linéaires comme les Matching Pursuits. En fonction du dictionnaire utilisé, et du signal, les Matching Pursuits peuvent avoir des grandes difficultés pour arriver à obtenir des expansions parcimonieuses optimales. Basé sur ce résultat, il peut être démontré, de manière théorique et expérimentale, que l'utilisation des modèles à priori (comme par exemple des modèles probabilistes) peut contribuer très significativement à l'amélioration des performances de ces algorithmes. Une autre partie de l'étude préliminaire, pour l'utilisation des Matching Pursuits, concerne l'approche utilisée dans cette thèse pour la décomposition du signal vidéo et des images. L'approche proposé dans cette thèse améliore une méthode existante de Matching Pursuits utilisée dans le passé dans un but similaire. Cette méthode était basée, pour des raisons de complexité calculatoire, sur l'utilisation d'algorithmes génétiques. La méthode proposée dans cette thèse rend possible, d'une manière plus rapide et efficace, la substitution de l'algorithme génétique par une recherche exhaustive. Finalement, l'utilisation des Matching Pursuits avec des modèles à priori pour la décomposition du signal vidéo est étudiée. Des critères de régularité ont étés imposés afin de capturer l'évolution temporelle des composantes géométriques 2D. Les résultats obtenus pour le codage de ces représentations, ainsi que les résultats issus des analyses multimodales (audio/vidéo) d'une séquence, permettent d'éclaircir une grand partie des points incompris jusqu'alors sur l'utilisation des dictionnaires redondants avec des Matching Pursuits pour les représentations géométriques adaptatives en espace et en temps du signal vidéo.