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)

Sparse image approximation with application to flexible image coding

Figueras i Ventura, Rosa Maria ; Vandergheynst, Pierre (Dir.)

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

Ajouter à la liste personnelle
    Summary
    Natural images are often modeled through piecewise-smooth regions. Region edges, which correspond to the contours of the objects, become, in this model, the main information of the signal. Contours have the property of being smooth functions along the direction of the edge, and irregularities on the perpendicular direction. Modeling edges with the minimum possible number of terms is of key importance for numerous applications, such as image coding, segmentation or denoising. Standard separable basis fail to provide sparse enough representation of contours, due to the fact that this kind of basis do not see the regularity of edges. In order to be able to detect this regularity, a new method based on (possibly redundant) sets of basis functions able to capture the geometry of images is needed. This thesis presents, in a first stage, a study about the features that basis functions should have in order to provide sparse representations of a piecewise-smooth image. This study emphasizes the need for edge-adapted basis functions, capable to accurately capture local orientation and anisotropic scaling of image structures. The need of different anisotropy degrees and orientations in the basis function set leads to the use of redundant dictionaries. However, redundant dictionaries have the inconvenience of giving no unique sparse image decompositions, and from all the possible decompositions of a signal in a redundant dictionary, just the sparsest is needed. There are several algorithms that allow to find sparse decompositions over redundant dictionaries, but most of these algorithms do not always guarantee that the optimal approximation has been recovered. To cope with this problem, a mathematical study about the properties of sparse approximations is performed. From this, a test to check whether a given sparse approximation is the sparsest is provided. The second part of this thesis presents a novel image approximation scheme, based on the use of a redundant dictionary. This scheme allows to have a good approximation of an image with a number of terms much smaller than the dimension of the signal. This novel approximation scheme is based on a dictionary formed by a combination of anisotropically refined and rotated wavelet-like mother functions and Gaussians. An efficient Full Search Matching Pursuit algorithm to perform the image decomposition in such a dictionary is designed. Finally, a geometric image coding scheme based on the image approximated over the anisotropic and rotated dictionary of basis functions is designed. The coding performances of this dictionary are studied. Coefficient quantization appears to be of crucial importance in the design of a Matching Pursuit based coding scheme. Thus, a quantization scheme for the MP coefficients has been designed, based on the theoretical energy upper bound of the MP algorithm and the empirical observations of the coefficient distribution and evolution. Thanks to this quantization, our image coder provides low to medium bit-rate image approximations, while it allows for on the fly resolution switching and several other affine image transformations to be performed directly in the transformed domain.
    Résumé
    Les images naturelles sont souvent modélisées par des régions lisses par morceaux. Dans ce modèle, les bords de ces régions, correspondants aux contours des objets, constituent l'information principale du signal. Ces contours possèdent la propriété d'être des fonctions lisses le long de la direction des bords et irrégulières dans la direction orthogonale. La modélisation des bords avec un nombre minimal de termes est d'une importance capitale pour de nombreuses applications, telles que le codage d'image, la segmentation ou le débruitage. Les bases séparables standards ne peuvent pas fournir des représentations assez parcimonieuses des contours, dû au fait que ce type de base ne "voit" pas la régularité des bords. Par conséquent, une nouvelle méthode, basée sur les ensembles redondants de fonctions de base, est nécessaire pour capturer la géométrie des images. Cette thèse présente, dans une première étape, une étude sur les caractéristiques que les fonctions de base devraient posséder pour fournir des représentations parcimonieuses d'une image lisse par morceaux. Cette étude souligne le besoin de fonctions de base adaptées aux bords qui soient capables de capturer précisément l'orientation locale et la dilatation anisotrope des structures de l'image. Des orientations et des degrés d'anisotropie différents dans un ensemble de fonctions de base conduisent à l'utilisation de dictionnaires redondants. Cependant, l'inconvénient des dictionnaires redondants est de fournir des décompositions d'image non uniques, alors que, de toutes les décompositions possibles d'un signal dans un dictionnaire redondant, seule la plus parcimonieuse est nécessaire. Plusieurs algorithmes permettent de trouver des décompositions parcimonieuses sur des dictionnaires redondants, mais la plupart de ces algorithmes ne garantissent pas de trouver l'approximation optimale. Afin de résoudre ce problème, nous avons mené une étude sur les propriétés des approximations parcimonieuses. Cette étude établit un test pour vérifier si une approximation parcimonieuse donnée est la plus parcimonieux possible. La seconde partie de cette thèse présente un nouveau schéma d'approximation d'image, basé sur l'utilisation d'un dictionnaire redondant. Ce schéma permet d'avoir une bonne approximation d'une image avec un nombre de termes beaucoup plus petit que la dimension du signal. Ce nouveau schéma d'approximation est basé sur un dictionnaire formé par la combinaison de Gaussiennes et de fonctions mères, similaires à des ondelettes anisotropement dilatées et tournées. Nous avons défini un algorithme "Matching Pursuit" (MP) efficace de recherche complète de pour accomplir la décomposition d'image dans un tel dictionnaire. Finalement, nous construisons un schéma de codage géométrique d'images basé sur l'image approximée dans le dictionnaire anisotrope et tourné de fonctions de base. Nous présentons également une étude détaillée sur le codage des indices de fonctions de base dans l'approximation d'image parcimonieuse. Dans cette étude, la quantification des coefficients apparaît être d'une importance cruciale dans la conception d'un schéma de codage basé sur MP. Par conséquent, nous avons étudié un schéma de quantification des coefficients de MP, basé sur la borne supérieure théorique d'énergie de l'algorithme et les observations empiriques de la distribution et de l'évolution des coefficients. Grâce à cette quantification, notre codeur d'image produit des approximations d'image à bas et moyens débits, compétitifs avec l'état de l'art, tout en permettant de changer de résolution en un clin d'oeil et d'exécuter plusieurs autres transformations géométriques directement dans le domaine transformé.
    Summary
    Natural images are often modeled through piecewise-smooth regions. Region edges, which correspond to the contours of the objects, become, in this model, the main information of the signal. Contours have the property of being smooth functions along the direction of the edge, and irregularities on the perpendicular direction. Modeling edges with the minimum possible number of terms is of key importance for numerous applications, such as image coding, segmentation or denoising. Standard separable basis fail to provide sparse enough representation of contours, due to the fact that this kind of basis do not see the regularity of edges. In order to be able to detect this regularity, a new method based on (possibly redundant) sets of basis functions able to capture the geometry of images is needed. This thesis presents, in a first stage, a study about the features that basis functions should have in order to provide sparse representations of a piecewise-smooth image. This study emphasizes the need for edge-adapted basis functions, capable to accurately capture local orientation and anisotropic scaling of image structures. The need of different anisotropy degrees and orientations in the basis function set leads to the use of redundant dictionaries. However, redundant dictionaries have the inconvenience of giving no unique sparse image decompositions, and from all the possible decompositions of a signal in a redundant dictionary, just the sparsest is needed. There are several algorithms that allow to find sparse decompositions over redundant dictionaries, but most of these algorithms do not always guarantee that the optimal approximation has been recovered. To cope with this problem, a mathematical study about the properties of sparse approximations is performed. From this, a test to check whether a given sparse approximation is the sparsest is provided. The second part of this thesis presents a novel image approximation scheme, based on the use of a redundant dictionary. This scheme allows to have a good approximation of an image with a number of terms much smaller than the dimension of the signal. This novel approximation scheme is based on a dictionary formed by a combination of anisotropically refined and rotated wavelet-like mother functions and Gaussians. An efficient Full Search Matching Pursuit algorithm to perform the image decomposition in such a dictionary is designed. Finally, a geometric image coding scheme based on the image approximated over the anisotropic and rotated dictionary of basis functions is designed. The coding performances of this dictionary are studied. Coefficient quantization appears to be of crucial importance in the design of a Matching Pursuit based coding scheme. Thus, a quantization scheme for the MP coefficients has been designed, based on the theoretical energy upper bound of the MP algorithm and the empirical observations of the coefficient distribution and evolution. Thanks to this quantization, our image coder provides low to medium bit-rate image approximations, while it allows for on the fly resolution switching and several other affine image transformations to be performed directly in the transformed domain.