Les techniques de compression: les fractales
Qui n'a jamais croisé cette fameuse fougère, exemple de choix lorsque l'on souhaite évoquer la construction d'une image fractale ?
Si compresser les données n'est pas un besoin récent, l'utilisation des méthodes de compression a changé. Il y a quelques années de cela, il était encore courant de compresser à tout va, afin de gagner quelques précieux kilos-octets sur sa disquette 1.44 Mo. C'était l'époque ou le dernier disque dur affichait fièrement ses 80 Mo de capacité de stockage.
Aujourd'hui, même si notre besoin en stockage augmente (utilisation d'appareils photos numériques, de fichiers musicaux, etc.), les disques durs suivent le rythme et offrent un coût au giga abordable. Peu importe à ce moment là qu'une image issue de vos dernières vacances occupe sur le disque 30 Ko ou 2 Mo... du moment qu'elle rappelle de bons souvenirs.
Il en va tout autrement sur les réseaux, là où la transmission d'informations n'est pas aussi rapide qu'entre un lecteur de CD-ROM vers un disque dur, où d'un port USB vers ce même disque. Les sites web ont besoin d'afficher un maximum d'informations, tout en nécessitant pour l'internaute le moins de téléchargement possible. Ici, ce ne sont pas pas les textes des pages web qui sont incriminés, mais bien les images, qui représentent souvent la partie la plus "lourde" d'un site.
Avant d'approfondir les principes mêmes de la compression fractale, remontons à l'origine de cette technique, vers la fin des années 70.
L'origine de cette technique
Benoît Mandelbrot est considéré (Escher Maurits est aussi cité) comme étant à l'origine des fractales. Mandelbrot porta cette technique au rang d'une discipline mathématique : "la géométrie fractale". Du latin "fractus" (brisé), "fractale" est un terme inventé par ce mathématicien français ("The Fractal Geometry of Nature", 1977) pour désigner des objets dit "irréguliers" se distinguant des figures classiques telles que la droite, le cercle...
Plus tard, en 1988, un autre mathématicien, Michael F. Barnsley montra qu'on pouvait stocker des images avec peu de données grâce à une approximation de photographies numérisées à l'aide de fractales. Il évoque les fractales IFS ("Iterated Function Systems" ) dans un livre qui fit sensation cette année là : "Fractals Everywhere". Selon lui, toute image peut être représentée par un ensemble de ces "IFS". Il aboutit au "Collage Theorem" qui stipule à quoi doit ressembler un "IFS" afin de représenter une image.
Si le système "IFS" est capable de générer des images, peut-être est-il aussi capable de les compresser ? Barnsley décide de poursuivre dans cette voie et fonde la société "Iterated Systems Incorporated", qui détient aujourd'hui les brevets des fichiers ".FIF", le format des images compressées par la technologie fractale. Malheureusement pour Barnsley qui pensait avoir résolu le problème de la compression, sa solution était très lente et non automatisée. En 1992, un de ses élèves, Arnaud Jacquin, automatise la procédure. Son algorithme est encore utilisé aujourd'hui pour la compression fractale.
Le principe de l'algorithme de compression
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 ici 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 !
Comme pour le format JPEG, l'image est découpée en blocs de pixel, mais ils sont ici 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 carrés.
Au final on obtient une structure présentant des caractéristiques similaires à des échelles différentes. Pour retrouver l'image il suffira de décrire les transformations qui ont été appliquées aux blocs initiaux. Ce processus rend la compression indépendante de la taille de l'image. De plus, l'image produite est vectorisée et ne subit pas les effets de la pixelisation, contrairement au JPEG. Ce phénomène est surtout visible lors d'un zoom par exemple, l'image fractale peut devenir floue mais ne pixelise pas. Ceci est dû au fait que lors de l'agrandissement, ce ne sont pas les pixels qui sont élargis, mais toute l'image qui est recalculée mathématiquement.
Le problème lié à cette technique est la lenteur du procédé de compression, de l'ordre de 50 fois plus lent que pour une image JPEG. La décompression quant à elle est aussi rapide que pour les autres formats.
Un peu de détente : galeries, liens et exemples d'images
Voyons un peu à quoi ces images ressemblent. Le format ".FIF" n'est pas reconnu par vos navigateurs : il existe un certain flou au niveau de sa standardisation. Il faut donc télécharger un "viewer" adapté. Une fois installé, profitez de ces magnifiques paysages.
Moins puissante que les ondelettes (fichiers ".wi" ) mais supérieure au JPEG (à partir de 40:1), la compression par fractale constitue une solution intermédiaire, comme le montre cette comparaison, en images, de ces trois formats.
Pour beaucoup, les fractales ne sont pas seulement un moyen de compresser des images, mais aussi un moyen d'expression, un art capable de générer des paysages improbables ou de magnifiques tableaux.
Si vous souhaitez en savoir plus, vous pouvez consulter cette bonne introduction, en anglais, sur cette technique de compression.
Enfin, pour réveiller la fibre artistique qui sommeille peut-être en vous, voici un dernier lien qui recense plusieurs outils qui vous permettront de créer vos propres fractales.
