Compression fractale

Fougère de Barnsley à plusieurs étapes de sa génération. L'une des transformations de la fractale copie, en la réduisant, la zone rouge sur la zone bleue.

La compression fractale est une méthode de compression d'image avec perte qui repose sur la détection de la récurrence des motifs, et tend à éliminer la redondance d'informations dans l'image en décrivant comment reconstituer chaque zone à partir d'une autre, en ajustant à la fois sa forme (position des pixels) et son apparence (contraste et luminance). L'image compressée n'est donc plus une grille de points, mais une « recette » mathématique permettant de la redessiner.

Fondée sur les systèmes de fonctions itérées et la géométrie fractale, la méthode possède deux particularités. Elle est très asymétrique : la compression, qui doit chercher les ressemblances dans l'image, est lente, alors que la décompression est quasi instantanée. Elle est aussi indépendante de la résolution, l'image pouvant être reconstruite à une taille différente de l'originale. Introduite par Michael Barnsley à la fin des années 1980 et rendue automatique par Arnaud Jacquin en 1992, elle a été exploitée commercialement (format FIF, encyclopédie Encarta) mais reste peu utilisée, supplantée par les méthodes par ondelettes.

Historique

La compression fractale naît de l'application à l'image de la théorie des systèmes de fonctions itérées (IFS). À la fin des années 1980, Michael Barnsley et Alan Sloan, chercheurs au Georgia Institute of Technology, en font le principe d'une méthode de compression : ils fondent la société Iterated Systems et déposent un premier brevet en 1987, puis popularisent l'idée dans la revue Byte en 1988, où ils annoncent des taux de compression théoriques pouvant atteindre 10 000:1. Leur procédé d'encodage reste cependant extrêmement lent (de l'ordre de 100 heures pour comprimer une image couleur complexe, contre 30 minutes pour la décompresser) et exige qu'un opérateur identifie lui-même les transformations reproduisant l'image.

L'automatisation du codage est l'œuvre d'Arnaud Jacquin, étudiant de Barnsley, à qui l'on doit le premier algorithme entièrement automatique. Fondé sur un partitionnement de l'image en blocs (partitioned iterated function systems, ou PIFS) et décrit en 1992, il sert de base à la plupart des travaux ultérieurs. Iterated Systems, qui avait déposé dès 1989 un second brevet lié à ce codage, commercialise alors la technologie via le format de fichier FIF (Fractal Image Format), notamment pour l'encyclopédie Encarta, dont les quelque 7 000 photographies sont stockées sous forme fractale.

La méthode continue ensuite d'évoluer : la diversification des méthodes de partitionnement améliore la qualité des images reconstruites, tandis que de nouvelles méthodes d'encodage réduisent le temps de calcul. Elle ne connaît toutefois pas d'adoption large, freinée par les restrictions liées aux brevets et surtout par son coût de calcul à l'encodage, bien supérieur à celui des méthodes par ondelettes ou par DCT. À taux de perte comparable, une image se comprime en moins d'une seconde en JPEG ou par ondelettes, contre plus de 5 heures de calcul par la méthode fractale.

Principe

La méthode repose sur un constat issu de la géométrie fractale, développée notamment par Benoît Mandelbrot pour décrire les formes irrégulières et autosimilaires de la nature : une image naturelle contient souvent des motifs qui se ressemblent à différentes échelles ou en différents endroits. Cette redondance, appelée autosimilarité, peut être exploitée pour décrire l'image de façon compacte.

Pour l'exploiter sur une image classique (ne présentant pas une telle autosimilarité globale), cette dernière est découpée en différents blocs que l'on va transformer afin de les faire correspondre à d'autres parties de l'image. Une fois que l'on peut entièrement recréer l'image à partir d'elle-même, les pixels d'origine peuvent être abandonnés et seules les transformations sont conservées : l'image compressée n'est plus une grille de points, mais un ensemble de règles permettant de la reconstruire. Plus cette liste de transformations sera courte et compacte, plus la compression sera efficace. La décompression consiste alors à appliquer cette liste de transformations de façon répétée à une image de départ quelconque, qui converge vers une image fixe (l'attracteur) approchant l'image d'origine. Cette reconstruction n'étant qu'une approximation, la compression fractale est une méthode avec perte.

Chaque transformation comporte deux volets : une composante géométrique, qui agit sur la position des pixels (réduction, déplacement, rotation ou symétrie), et une composante dite massique, qui ajuste leurs valeurs (le contraste et la luminance) afin de faire correspondre des régions d'éclairement différent. C'est cette double transformation, et non un simple découpage, qui permet à une partie de l'image d'en représenter une autre.

Comme l'image compressée n'est plus une grille de pixels mais un ensemble de transformations, elle ne possède pas de résolution propre : on peut la reconstruire à une taille différente de l'originale en appliquant les transformations sur une grille plus fine. Cette propriété, appelée interpolation fractale, permet d'agrandir l'image en évitant les effets d'escalier des méthodes classiques. Elle ne restitue toutefois pas de détail réellement présent dans l'original : les structures ajoutées aux résolutions supérieures sont synthétisées de façon plausible, et non retrouvées.

Le procédé est donc fortement asymétrique : la compression demande beaucoup de calculs pour explorer l'image, la découper et y rechercher les ressemblances, tandis que la décompression ne nécessite qu'une simple répétition des transformations listées, un nombre fini de fois.

Assises mathématiques

Plusieurs théorèmes permettent de garantir le bon fonctionnement de cette méthode de compression. Les deux théorèmes fondateurs en sont le Théorème du collage et le Théorème du point fixe de Banach.

Le théorème du point fixe énonce que, dans un espace métrique complet, toute transformation contractante (c'est-à-dire qui rapproche les points les uns des autres) possède un unique point fixe. Il garantit que si l'on applique de manière itérée cette transformation à partir de n'importe quel élément initial, la séquence obtenue convergera systématiquement vers ce point fixe unique. Dans le contexte de l'imagerie, ce point fixe est appelé l'attracteur du système et représente l'image finale stable reconstruite par le décodeur. La stricte contractivité de chaque transformation est suffisante, mais non nécessaire, à cette convergence : d'autres transformations peuvent convenir si elles répondent à certains critères.

Illustration du théorème du point fixe : deux images de départ différentes, soumises à la même transformation itérée, convergent vers le même attracteur, ici le triangle de Sierpiński.

Ce théorème peut être illustré par une photocopieuse dotée d'une fonction particulière : elle scanne le document, le réduit de moitié et en imprime trois exemplaires disposés en triangle sur la nouvelle page. Si l'on scanne à nouveau cette page encore et encore, l'image obtenue se rapproche systématiquement d'une même figure (ici le triangle de Sierpiński), quel que soit le document d'origine.

Le théorème du collage énonce que si l'on peut recouvrir presque parfaitement une image avec des petites copies déformées d'elle-même, alors les équations utilisées pour faire ces copies constitueront un bon code compressé pour cette image. Il établit ainsi que la qualité de l'image reconstruite est corrélée à la qualité du collage.

Méthode de Jacquin

Jacquin apporte plusieurs réponses concrètes qui rendent possible un programme autonome de compression et de décompression. Tout d'abord, la segmentation de l'image est simplifiée : il n'est plus nécessaire d'y reconnaître des structures fractales, l'image étant simplement découpée en blocs carrés source et destination (respectivement domain blocks et range blocks), les blocs destination étant deux fois plus petits que les blocs source afin que les transformations soient contractantes, condition suffisante du théorème du point fixe.

Pour chaque bloc destination, on cherche le bloc source qui, après avoir subi différentes transformations, en est le plus proche au sens de l'erreur quadratique moyenne (EQM) sur la luminance. Ces transformations peuvent être géométriques (contraction, translation et huit isométries : les rotations de 90°, 180° et 270°, les symétries verticale, horizontale et selon les deux diagonales, et l'identité) ou massiques, c'est-à-dire modifiant la valeur des pixels (changement de contraste, de luminance, passage à un gris uniforme moyen, ou inversion des couleurs). Si, malgré toutes les combinaisons de transformations possibles, l'EQM reste trop élevée, le bloc destination est subdivisé en quatre et le même algorithme est appliqué à chacun des sous-blocs.

Afin d'optimiser la recherche du bloc source et le choix de la transformation, Jacquin classe les blocs en trois catégories selon leurs caractéristiques (présence de bords, de dégradés) :

• les blocs lisses (shade), de faible variation, sont retirés du réservoir source. Un bloc destination de ce type n'est pas mis en correspondance avec un bloc source mais simplement remplacé par un gris uniforme égal à son niveau de gris moyen.
• les blocs de bord (edge), qui présentent une transition d'intensité marquée, sont mis en correspondance avec d'autres blocs de bord et peuvent recevoir toutes les transformations. La recherche est accélérée en estimant le contraste et la luminance à partir des tons de part et d'autre du bord.
• enfin, les blocs intermédiaires (midrange), de gradient modéré, sont mis en correspondance avec un bloc source de même type à l'aide des seules transformations massiques (contraste et luminance).

Le code fractal ne contient alors, pour chaque bloc destination, que la position du bloc source retenu et les paramètres de sa transformation (isométrie, coefficients de contraste et de luminance), auxquels s'ajoute la description du découpage. C'est cette description compacte, et non les pixels, qui constitue l'image compressée. Sur l'image de test Lena, la méthode atteint un débit de l'ordre de 0,6 bit par pixel, la décompression convergeant en quelques itérations (de l'ordre de huit), pour une qualité jugée bonne dans l'ensemble malgré des effets de bloc liés au découpage carré.

Autres partitionnements

Le découpage en blocs carrés réguliers de Jacquin a l'avantage d'être simple à mettre en œuvre, et il est aussi employé par d'autres méthodes de compression comme JPEG. Il s'adapte toutefois mal au contenu de l'image. De petits blocs découpent une grande zone homogène en de nombreux morceaux, donc en autant de transformations à enregistrer, là où un seul grand bloc aurait suffi. À l'inverse, de gros blocs rendent quasi impossible la restitution des zones riches en détails. Des méthodes de partitionnement adaptatif apparaissent donc pour améliorer la qualité ou le taux de compression en ajustant le découpage au contenu de l'image. Le reste de la méthode de Jacquin, ainsi que les théorèmes sur lesquels elle repose, demeure inchangé. Seul le découpage évolue, parfois accompagné d'optimisations destinées à accélérer la recherche de correspondances.

L'arbre quaternaire (quadtree) est d'abord utilisé. Il divise récursivement une zone en quatre sous-carrés égaux tant qu'elle n'est pas correctement approchée par un bloc source. Simple à manipuler informatiquement, il améliore de deux à trois fois le taux de compression à qualité égale sans alourdir excessivement le codage.

Le partitionnement horizontal-vertical (H-V) divise lui aussi récursivement une zone, mais par une ligne verticale ou horizontale placée librement, séparant le rectangle en deux sous-rectangles. En alignant les divisions sur les structures de l'image, il améliore les résultats du quadtree, au prix d'une complexité de codage plus grande liée au choix de la ligne de division.

La triangulation de Delaunay permet quant à elle de découper l'image en triangles de formes et d'orientations quelconques, capables de suivre les bords et d'englober de grandes zones homogènes. Elle réduit nettement les effets de bloc et d'escalier produits par les découpages carrés, son apport principal étant la qualité visuelle le long des contours. Associée à une quantification vectorielle, elle atteint une bonne qualité à des débits de 0,25 à 0,5 bit par pixel, au prix d'un coût de calcul élevé.

Décompression

Décompression d'une image à différentes itérations. En haut à gauche, l'image d'initialisation, quelconque et aléatoire ; en bas à droite, l'image cible d'origine.

Quel que soit le partitionnement choisi, le principe de la décompression reste le même. Le fichier comprimé, qui contient les correspondances entre blocs source et blocs destination ainsi que leurs transformations, est lu, puis ces transformations sont appliquées de façon répétée à une image de départ quelconque (de l'ordre de huit à douze itérations chez Jacquin). Ce procédé itératif est celui des systèmes de fonctions itérées partitionnés (PIFS). Quelle que soit l'image initiale, la séquence converge vers une image stable, l'attracteur, qui approche l'image d'origine. La qualité du résultat dépend de la finesse du découpage : plus les blocs sont nombreux, plus l'image reconstruite est fidèle, mais moins la compression est élevée.

Voir aussi

Bibliographie

• (en) Yuval Fisher, Fractal Image Compression: Theory and Application, Springer New York, 1995 (ISBN 978-1-4612-7552-7)

Articles connexes

• Fractale
• Compression d'image
• Compression de données
• Triangulation de Delaunay
• Système de fonctions itérées
• Géométrie fractale