COMPRESSION D’IMAGE PAR LA METHODE FRACTALE

Image numérique

                   Contrairement aux images obtenues à l’aide d’un appareil photo classique, ou dessinées sur du papier, les images manipulées par un ordinateur sont numériques (représentées par une série de bits). L’image numérique est l’image dont la surface est divisée en éléments de tailles fixes appelés cellules ou pixels, ayant chacun comme caractéristique un niveau de gris ou de couleurs prélevé à l’emplacement correspondant dans l’image réelle, ou calculé à partir d’une description interne de la scène à représenter. La numérisation d’une image est la conversion de celle-ci de son état analogique (distribution continue d’intensités lumineuses dans un plan xOy en une image numérique représentée par une matrice bidimensionnelle de valeurs numériques f(x, y) où x, y sont les coordonnées cartésiennes d’un point de l’image, et f(x, y) est le niveau de gris en ce point Pour des raisons de commodité de représentation pour l’affichage et l’adressage, les données images sont généralement rangées sous formes de tableau I de n lignes et p colonnes. Chaque élément I(x ,y) représente un pixel de l’image et à sa valeur est associé un niveau de gris codé sur m bits (2m niveaux de gris ; 0 = noir ; 2m -1 = blanc). La valeur en chaque point exprime la mesure d’intensité lumineuse perçue par le capteur [1] [2] [3].

Décorrélation

                La première étape qui est celle de la décorrélation de l’image a pour objectif de réduire la redondance contenue dans les données, ou encore de dissocier la redondance de l’information pertinente. Les méthodes les plus utilisées mettent en œuvre des transformées afin de représenter les données dans un autre domaine, comme par exemple la DCT (Transformée en Cosinus Discrète) et les ondelettes [4].
Compression par transformation : L’idée consiste à appliquer une transformation au signal de départ, de telle façon que la plupart de son énergie soit projetée dans une région restreinte (un nombre réduit de coefficients) de l’espace transformé. La transformation utilisée sera linéaire afin de disposer d’une solution analytique, qui nous permette la reconstruction ultérieure du signal. Les transformations les plus connues sont la transformation en cosinus discrète (DCT) et les ondelettes [5]. Les méthodes de transformations agissent, non pas dans le domaine spatial sur l’image numérique, mais dans le domaine transformé sur une autre représentation de l’image originale. Après avoir calculé la transformation de l’image d’entrée on obtient les coefficients transformés. Ensuite, il faut quantifier les coefficients pour qu’ils prennent moins de bits et ainsi le flux obtenu aura une taille plus faible que l’image originale. La compression de l’image consiste à négliger les coefficients les moins significatifs (de point de vue amplitude), tout en garantissant une qualité acceptable de l’image reconstruite par transformation inverse [7].
Compression fractale : Contrairement aux autres techniques de compression habituelles, la compression fractale ne tente pas de réduire le nombre de couleurs (format GIF) ou de compresser de manière classique les octets composant l’image. Le principe est de remplacer l’image par des formules mathématiques. La compression fractale a pour principe qu’une image n’est qu’un ensemble de motifs identiques en nombre limité, auxquels on applique des transformations géométriques (rotations, symétries, agrandissements, réductions). Evidemment, plus l’image possède cette propriété, meilleur sera le résultat [7] [19]. L’image est découpée en blocs de pixels de tailles variables. Il faut ensuite détecter les redondances entre ces blocs à diverses résolutions. On parle de transformations fractales basées sur un opérateur contractant. Ces transformations décrivent l’image de plus en plus finement. A la fin de ce processus, on ne stocke pas le contenu d’un bloc autant de fois qu’il a été vu dans l’image mais seulement les équations mathématiques permettant de représenter le contenu de ces blocs [7]. Nous en parlerons plus en détails dans la suite.

Partitionnement rigide : partition Quadtree

                Un partitionnement est qualifié de rigide s’il ne s’adapte pas moindre coût aux formes des objets présents dans l’image [2]. Un quadtree ou arbre quaternaire est une structure utiliser pour représenter les images binaires ou en niveau de gris. La représentation est exacte lorsque le processus récursif de sous division des blocs descend jusqu’à la taille du pixel. Chaque bloc est alors composé de valeurs toutes égales à 1 ou toutes égales à 0 [3].
 Phase de division : On procède de la manière suivante : prenons une image notée ?0 de taille 2? × 2?, on construit le quadtree de haut vers le bas en divisant récursivement tout bloc ??? non homogène selon un parcours donné (critère d’homogénéité) avec ?0 le bloc constituant la région de départ, l le niveau dans la représentation pyramidale du codage en quadtree, et i le numéro du sous bloc avec i∈ {1,2,3,4}. De la division d’un bloc ??? de taille 2?−1 ×2?−1 résultent donc quatre sous-bloc ???+1 avec j∈ {1,2,3,4} de dimension 2?−1−1. A chaque division, quatre nouveaux blocs sont recalculés, et ainsi de suite jusqu’à un bloc homogène [2] [3] [13] [17]. On a dans la figure suivante la représentation schématique de cette phase de  division, avec l’arbre quaternaire (quadtree) correspondante.
 Phase de fusion : Cette étape consiste à regrouper les blocs adjacents égaux selon le prédicat d’homogénéité considéré. Son principal intérêt est que le nombre total de régions s’en trouve réduit, de plus les bords des régions sont aussi beaucoup plus proches des contours réels de l’image. Cette étape de fusion n’est pourtant pas utilisée pour le cas de la compression par fractales à cause de la forme extrêmement complexe des blocs résultants [3]. Ce type de partitionnement est certainement le plus répandu dans les programmes de compression fractale. Il est simple à utiliser et fournit des résultats corrects.

Comparatif entre approches de compression par fractales et par transformée en cosinus discrète

                On a fait un petit comparatif avec une autre technique de compression pour mettre en évidence les capacités de la compression par fractales. Cela reste quand même subjectif car les performances désirées et le temps de compression doivent être choisis selon le besoin de l’utilisateur et dépendent aussi du type d’images à comprimer (images médicales, images satellites, …). Le but ici n’est pas de savoir laquelle de ces techniques est la plus performante, mais de mettre en évidence les points forts et les points faibles de chaque technique pour pouvoir mettre en œuvre les solutions adéquates futures, comme par exemple la compression hybride combinant les fractales et une transformée en ondelettes ou en cosinus discrète. Pour cette comparaison, nous avons choisi l’image du cameraman dans Matlab. On peut constater à l’œil nu des différences notables entre ces deux images restituées après compression. Ce choix dépend aussi des paramètres d’utilisation et d’exploitation de l’image. Il peut s’agir d’une image à transmettre sur tel ou tel réseau de télécommunication, ou bien pour être stockée sur un support en particulier. Enfin, le domaine qui exploite les images constitue aussi un critère de choix de la technique de compression à mettre en œuvre, tout comme le type même des images (images médicales, images satellites, …). Nous exposons dans le tableau suivant les différences entre ces deux approches en termes de performance.
Remarque : Durant cette simulation, nous avons utilisé différents matériels physiques et logiciels qui ont une influence sur les résultats de simulation, aussi il est nécessaire de mettre une précision sur ces outils. Nous avons utilisé entre autres :
 Un (01) ordinateur portable avec un processeur de type Intel Core i3-3120M CPU avec une fréquence de 2.50 GHz et doté d’une mémoire vive de 4096 Mo.
 Le logiciel Matlab version 8.1.0.604 (R2013a).

CONCLUSION GENERALE

                 L’essentiel de ce mémoire s’est consacré à la compression fractale d’images numériques à niveau de gris. La compression fractale d’images, tant fixes que vidéo, constitue une voie de recherche d’actualité et reste encore ouverte aux scientifiques intéressés. La base de cette méthode de compression s’appuie sur la représentation des formes fractales très complexes par des transformations IFS très simples. Cette méthode possède un énorme potentiel lui permettant de figurer parmi les méthodes de compression efficaces proposant un taux de compression très satisfaisant. Toutefois, la lenteur dans la phase de codage constitue le handicap majeur des techniques de compression fractale. Un aspect important à retenir de la compression d’image par fractale est aussi que cette technique, selon les recherches réalisées ces dernières décennies, constitue un compromis entre la compression par transformée en ondelettes et celle par transformée en cosinus discrète. On a étudié cette méthode durant ce mémoire. Le plan suivi a été de mener une campagne d’introduction au domaine de la compression des images numériques au tout début. Bien entendu, nous avons pris la peine de fournir les notions élémentaires indispensables à la compression d’image en entrée en matière. A cela s’est ajouté un second chapitre énonçant les systèmes de fonctions itérées (IFS), qui sont les outils dont on se sert pour générer une fractale. On retrouve nombreuses autres manières de générer ces figures fractales, mais on rencontre le plus souvent les IFS ou les PIFS (IFS partitionnés) pour leur maniabilité mathématique d’où la réduction de leur implémentation et leur programmation. La troisième partie du travail a consisté à parler des détails de la compression d’images par fractales à proprement parler. C’est dans cette section qu’on a cité les divers moyens utilisés dans ce but. Il est vrai qu’on en rencontre un nombre assez important dans la littérature, mais nous avons mis ici ceux qui attirent le plus l’attention de la communauté scientifique internationale. Finalement, on a exposé un cas concret de compression d’image dans le dernier chapitre. Cela constitue le vif de ce travail et propose d’utiliser une méthode assez simple. Les résultats ne permettent pas un système de compression assez fiable pour être commercialisé ou exploité de manière professionnelle, toutefois, on constate que cette technique procure un taux de compression très intéressant. Par la suite, on peut chercher à améliorer les résultats obtenus en réduisant la durée utile à la compression. On propose entre autres d’utiliser une autre technique de partitionnement comme la triangulation de Delaunay mais cela accroitra d’autant plus le temps de calcul. Il est aussi envisageable d’accroitre la vitesse de calcul en réalisant une structure en parallèle pour effectuer la compression. Les algorithmes génétiques constituent aussi un sujet d’étude et d’optimisation intéressant en ce qui concerne cette technique de compression fractale. On a constaté que les fractales, sont encore peu exploitées par les chercheurs en traitement d’image en dépit du fait qu’elles constituent un moyen très universel pour représenter la géométrie de la nature.

Table des matières

INTRODUCTION GENERALE
CHAPITRE 1 GENERALITES SUR LA COMPRESSION D’IMAGE
1.1 Introduction
1.2 L’image numérique
1.2.1 L’image
1.2.2 Image numérique
1.2.3 Caractéristiques d’une image numérique
1.2.4 Images à niveaux de gris
1.2.5 Images couleurs
1.2.6 Images bitmap et images vectorielles
1.2.7 Concept de compression d’image
1.3 Eléments de théorie de l’information
1.3.1 Sources
1.3.2 Entropie d’une source simple
1.4 La compression réversible
1.4.1 Codage entropique
1.4.2 Codage par répétition (RLC ou RLE)
1.4.3 Codage à base de dictionnaires
1.4.4 Codage par prédiction
1.5 La compression irréversible
1.5.1 Décorrélation
1.5.2 Quantification
1.5.3 Le codage
1.6 Compression fractale
1.7 Conclusion
CHAPITRE 2 NOTIONS THEORIQUES SUR LES FRACTALES
2.1 Introduction
2.2 Généralités sur les fractales
2.2.1 Notion de Fractale
2.2.2 Principe d’autosimilarité
2.2.4 Dimension fractale
2.3 Systèmes des fonctions itérées IFS
2.3.1 Principe de la machine à copier
2.3.2 Définition d’un IFS
2.3.3 Attracteur d’un IFS
2.3.6 Théorème du collage
2.3.7 Transformation finalement contractante
2.3.6 Théorème du collage généralisé
2.4 Les PIFS
2.5 Compression des images naturelles par fractales
2.6 Conclusion
CHAPITRE 3 COMPRESSION FRACTALE
3.1 Introduction
3.2 Algorithme de compression
3.3 Méthodes de partitionnement
3.3.1 Partitionnement rigide : partition Quadtree
3.3.2 Partitionnement semi-rigide : partitionnement H-V
3.3.3 Partitionnement souple
3.4 Méthodes de compression
3.4.1 Méthode de Jacquin
3.4.2 Méthode de Fisher
3.4.3 Méthode de Dudbridge
3.5 Avantages et inconvénient de la compression fractale
3.5.1 Avantages
3.5.2 Inconvénients
3.5 Conclusion
CHAPITRE 4 SIMULATION DE LA COMPRESSION FRACTALE D’IMAGE SOUS MATLAB
4.1 Introduction
4.2 Présentation de l’outil de simulation
4.3 Simulation proprement dite
4.3.1 Algorithme
4.3.2 Objectifs
4.3.3 Interface graphique de la simulation
4.3.3 Déroulement
4.3.3 Résultats de simulation
4.3.4 Impact du partitionnement sur la performance
4.4 Comparatif entre approches de compression par fractales et par transformée en cosinus discrète
4.5 Conclusion
CONCLUSION GENERALE
ANNEXE 1 BASES ET OUTILS MATHEMATIQUES SUR LES FRACTALES ET LES IFS
ANNEXE 2 LES ISOMETRIES UTILISEES
ANNEXE 3 CHRONOLOGIE DE L’HISTORIQUE DES FRACTALES
ANNEXE 4 EXTRAIT DU CODE SOURCE
BIBLIOGRAPHIE
RENSEIGNEMENTS
RESUME
ABSTRACT

Télécharger le rapport complet