Compression Fractale

Compression Fractale

Compression fractale

La compression fractale est une méthode de compression d'image encore peu utilisée aujourd’hui. Elle repose sur la détection de la récurrence des motifs, et tend à éliminer la redondance d’informations dans l'image.

C'est une méthode destructive puisque l'ensemble des données de départ ne se retrouve pas dans l'image finale. Il existe plusieurs méthodes (subdivision de triangles, Delaunay etc.) mais la compression par la méthode Jacquin est la plus connue.

Sommaire

Illustration par la Méthode Jacquin

Méthode Jacquin

(L'image utilisée pour cette compression est, selon la tradition, la photo de Lenna.)

  • La compression fractale consiste tout d'abord à réaliser deux segmentations (appelés aussi pavages, ou partitionnements) sur une image : une segmentation de figures Sources et une segmentation de figures Destinations.
  • Il s'agit alors de trouver pour chaque figure Source, quel est le meilleur couple (figure source, figure destination) minimisant une erreur. Cette erreur est généralement calculée en soustrayant les deux figures. Pour réaliser l'opération de soustraction, il est nécessaire d'opérer une transformation de la figure source aux dimensions (et à la géométrie) de la figure destination.

De plus, des règles comme la rotation et les retournements sont possibles.

  • Une fois que tous les couples ont été trouvés, le fichier de sortie contient alors les différents couples, ainsi que les différentes transformations effectuées (rotation, réduction de la moyenne etc.).
  • Lors de la décompression, l'image est recréée à partir de ces transformations. La convergence est alors garantie par le fait que d'une part il y a une minimisation d'erreur (différence) et une modification des pixels, et d'autre part, que les figures sources sont plus grandes que les figures destinations. La compression fractale utilise la même propriété pour reconstruire l'image.

Partitionnements

Le partitionnement est l’opération qui consiste à segmenter une image en régions. Dans la compression par la méthode Jacquin, nous avons besoin de 2 partitionnements : Source et Destination. La méthode Jacquin utilise par exemple des figures carrées, mais d'autres formes sont possibles (nids d'abeilles, triangles etc).

Pavages carrés Source et Destination
  • Un point essentiel dans les partitionnements Source et Destination est que le pavage destination

doit être plus petit que le pavage source. En effet, dans le cas contraire, nous serions amenés à faire un agrandissement (et non une réduction) lors de la transposition des figures sources vers les figures destinations. Une fractale possède un motif se répétant à l’infini, en se rétrécissant. Aussi, nous perdons cette propriété si le partitionnement destination est plus grand que le partitionnement source, l’image ne pourra alors pas converger.

Pavages triangulaires Source et Destination
  • Le partitionnement par la méthode Jacquin est un partitionnement statique. L'utilisation d'un partitionnement adaptatif (qui dépend de l'image à traiter) améliore considérablement le facteur de compression.

Décompression

La décompression consiste en la lecture du fichier contenant les correspondances figure source-figure destination. Il suffit ensuite d'appliquer les transformations plusieurs fois. Ce procédé de reconstruction itéré, aussi connu sous le nom de système de fonctions itérées, garantit une convergence, relative, vers l'image de départ. La qualité du résultat dépend fortement de la taille des figures de segmentation, plus les figures seront nombreuses, et plus l'image résultante sera de qualité.

Partitionnements carrés - Itérations 1,2,3 et 4
  • Voici quelques images résultantes de la compression Jacquin, sur quatre itérations :
Partitionnements triangulaires - Itérations 1,2,3 et 4
  • Avec un partitionnement adaptatif triangulaire :

Voir aussi

Liens internes

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Compression fractale ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Compression Fractale de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Compression fractale — La compression fractale est une méthode de compression d image encore peu utilisée aujourd’hui. Elle repose sur la détection de la récurrence des motifs, et tend à éliminer la redondance d’informations dans l image. C est une méthode destructive… …   Wikipédia en Français

  • Compression De Données — La compression de données est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contient les mêmes informations, en utilisant un algorithme particulier. La décompression est l… …   Wikipédia en Français

  • Compression de donnees — Compression de données La compression de données est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contient les mêmes informations, en utilisant un algorithme particulier. La… …   Wikipédia en Français

  • Compression informatique — Compression de données La compression de données est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contient les mêmes informations, en utilisant un algorithme particulier. La… …   Wikipédia en Français

  • Compression D'image — La compression d image est une application de la compression de données sur des images numériques. Cette compression a pour utilité de réduire la redondance des données d une image afin de pouvoir l emmagasiner sans occuper beaucoup d espace ou… …   Wikipédia en Français

  • Compression d'images — Compression d image La compression d image est une application de la compression de données sur des images numériques. Cette compression a pour utilité de réduire la redondance des données d une image afin de pouvoir l emmagasiner sans occuper… …   Wikipédia en Français

  • Compression de données — La compression de données ou codage de source est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, contenant les mêmes informations, en utilisant un algorithme particulier. Il s agit d… …   Wikipédia en Français

  • Fractale — On nomme figure fractale ou fractale par substantivation de l adjectif (ou encore en anglais fractal), une courbe ou surface de forme irrégulière ou morcelée qui se crée en suivant des règles déterministes ou stochastiques impliquant une… …   Wikipédia en Français

  • Compression par ondelettes — La Compression par ondelettes est une technique de compression de données, bien adaptée à la compression d images. Sommaire 1 Introduction aux ondelettes 2 Algorithme ondelettes 3 Transformée ondelettes …   Wikipédia en Français

  • Compression d'image — La compression d image est une application de la compression de données sur des images numériques. Cette compression a pour utilité de réduire la redondance des données d une image afin de pouvoir l emmagasiner sans occuper beaucoup d espace ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”