Compression fractale

• La compression fractale consiste tout d'abord à réaliser deux segmentations (appelées 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.

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).

• 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.
• 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.

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é.

• Une image en noir et blanc peut être représentée par un vecteur dans un espace vectoriel de dimension n : la i-ième composante du vecteur représente le niveau de gris du i-ième pixel. Le niveau de gris d'un pixel peut aller de 0 à 255. C'est sur ce modèle mathématique d'une image que pourront s'appliquer la compression et la décompression. On peut considérer une image en couleur comme étant la superposition de 3 calques primaires rouge vert bleu.
• Pour la compression, la garantie de pouvoir trouver les couples (figure source, figure destination) ainsi que les transformations adaptées repose sur le Théorème du collage.
• Pour la décompression, la garantie de convergence vers l'image compressée est assurée par le Théorème du point fixe. C'est ce théorème qui impose que le pavage destination doit être plus petit que le pavage source.