Introduction Générale

    La société actuelle produit un nombre croissant de données qui doivent être traitées, transmises et / ou stockées. Celles-ci sont principalement des sons, des images ou des textes et proviennent de différents secteurs tels que par exemple la physique, la médecine, la biologie, l’industrie, la culture, le tourisme ou la finance.

La représentation de ces informations sous forme numérique fiabilise leur transmission à travers des réseaux informatiques et facilite leur manipulation. La numérisation présente cependant un inconvénient : elle requiert que les dispositifs de stockage ainsi que les largeurs des bandes passantes des lignes de transmission soient suffisamment importantes. Ceci n’est pas possible toujours et il faut dans ce cas faire appel à des algorithmes de compression des données.

L’idée de base de la compression des images est de réduire le nombre moyen de bits par pixel nécessaire à sa représentation. Il est possible dans une certaine limite de réduire ce nombre sans perte d’information. Au-delà, il est nécessaire d’élaborer des algorithmes de compression (irréversibles) induisant une distorsion pas ou peu visible dans les conditions normales d’observation des images.

Nous nous intéressons dans le cadre de cette thèse à la compression des images numériques fixes en niveaux de gris et présentons une méthode selon une approche fractale.

Cette méthode opère sur une partition de l’image et cherche à exploiter les redondances entre des blocs de pixels à diverses résolutions. On parle dans ce cas de transformation (géométrique) fractale, basée sur un opérateur finalement contractant.

L'histoire de la compression par fractales a commencé lorsque Barnsley, Demko et d’autres chercheurs d’Atlanta ont démontré dans une série d’articles entre 1985 et 1988 l’intérêt d’utiliser la théorie des fractales pour coder les images numériques. La méthode, basée sur le théorème de collage, montre qu’il est possible d’approximer un objet fractal binaire défini dans le plan à l’aide de quelques transformations contractantes définissant un système de fonctions itérées (IFS). L’objet est dit aussi auto-similaire dans le sens où il est composé de l’union de transformations contractantes de lui-même. L’approximation d’un objet donné constitue un problème inverse difficile à résoudre de manière automatique et Barnsley proposait à cette époque une solution " manuelle ". L’idée fut ensuite généralisée aux objets en niveaux de gris en les approximant, toujours de façon manuelle, à l’aide de mesures invariantes normalisées définies sur un support fractal du plan. L’approximation des images naturelles peut être faite de la même manière en les considérant comme étant formées de l’union d’objets auto-similaire, chacun étant approximé indépendamment par une mesure invariante. Les images initialement présentées par M.Barnsley étaient obtenues de cette manière, mais constituaient des approximations très grossières des images réelles.

Sur la base de ces travaux, Jacquin a proposé en 1989 une approche fractale ne nécessitant pas d’intervention humaine et permettant de coder une image naturelle. La méthode est basée sur une série de transformations affines contractantes et " locales " définissant un opérateur contractant. Elle a l’avantage d’être automatique mais ne résoud cependant pas directement le problème inverse décrit par Barnsley puisque l’image n’est pas considérée comme une union de transformations d’elle-même. Dès 1989, de nombreuses autres recherches ont débuté visant toutes à accélérer la phase de calcul des transformations locales, et / ou à répondre au compromis taux de compression-distorsion. Une formulation algébrique de l’opérateur contractant a permis de définir d’autres types de transformations locales plus optimales tout en contrôlant sa propriété de contraction. Fisher a proposé de réduire le nombre de transformations en adaptant le partitionnement à l’image. Il a pour cela utilisé un partitionnement en quadtree puis un partitionnement rectangulaire. En parallèle à ces travaux visant à définir un opérateur optimal agissant dans l’espace des niveaux de gris, des chercheurs utilisent actuellement la théorie des IFS

ainsi que l’extension proposée par Jacquin dans des schémas hybrides basés sur la transformée en ondelettes ou en cosinus discrète.

Notre étude vise à montrer l’intérêt d’utiliser un modèle de partitionnement géométrique beaucoup plus souple que ceux proposés jusqu’à présent (des partitionnements rigides ou semi-rigide ne s'adaptant pas au contenu de l'image) et à apporter différentes améliorations au schéma de compression développé. C’est le modèle de partitionnement triangulaire.

Afin d'aborder tous les aspects ayant trait à la compression d'images, la méthode développée et aux résultats, le mémoire est organisé comme suit:

Le chapitre I: présente différentes définitions sur le traitement d’image en général.

Le chapitre II: est consacré à la présentation des principales méthodes de codage entropique et de compression réversibles et irréversibles des images fixes en niveaux de gris.

Le chapitre III: introduit les notions nécessaires à la compréhension de la théorie des systèmes de fonctions itérés (IFS) et présente les principaux algorithmes de compression des images naturelles selon l'approche fractale sur des blocs de pixels.

Il présente aussi les différents partitionnements déjà utilisés en compression d’images par fractales.

Le chapitre IV est consacré à notre approche fondée sur le modèle de partitionnement de Delaunay. La souplesse de ce partitionnement nous permet de proposer trois triangulations adaptées au contenu de l’image à compresser. La première est implantée dans un contexte algorithmique de type division-fusion en considérant la variance des niveaux de gris à l’intérieur de chacun des triangles. La deuxième partition est implantée dans un contexte de type division seule à partir d’un ensemble dense de points disposés sur le support de l’image. La troisième partition est contrainte par les contours de l’image et permet de se rapprocher des méthodes basées régions-contours mentionnées auparavant.

Dans le chapitre V, nous montrons comment calculer la transformation fractale d’une image naturelle à l’aide des triangulations décrites dans le chapitre III et détaillons l’algorithme de codage-décodage. Nous présenterons les améliorations apportées au schéma de compression / décompression, qui visent à réduire les temps et l’espace de stockage en diminuant le nombre de comparaisons inter-blocs. Elles sont fondées sur la quantification des vecteurs histogrammes du contenu des triangles et l’orthogonalisation de l’espace de collage.

Le chapitre VI présente notre logiciel ainsi que les différents résultats obtenus lors de son application sur différentes images, tout en dégageant ses points forts, ses limites, et en discutant les perspectives de recherche sur la compression des images fixes par fractales.