Annexe 2 — Compression fractale — Une application des points fixes

Objectifs d'apprentissage

À la fin de cette annexe, vous serez en mesure de :

• Expliquer comment générer une image fractale par itération de transformations
• Comprendre le rôle des transformations affines contractantes dans la convergence
• Décrire le concept d'attracteur et son lien avec le théorème du point fixe
• Identifier les principes de la compression fractale d'images
• Situer cette technique dans le paysage des méthodes modernes de traitement d'images

Introduction

Dans ce cours, nous avons étudié les méthodes itératives pour résoudre des équations. Nous avons vu qu'une suite peut converger vers un point fixe si certaines conditions sont respectées, notamment .

Une question naturelle se pose : que se passe-t-il si, au lieu d'itérer sur des nombres, on itère sur des images ? Cette question a conduit Michael Barnsley, dans les années 1980, à développer la théorie des systèmes de fonctions itérées (IFS) et son application à la compression d'images.

Cette annexe présente d'abord une approche intuitive de ces concepts, puis les fondements mathématiques rigoureux, et enfin l'évolution de ces idées jusqu'aux techniques modernes.

Le photocopieur spécial : une expérience de pensée

L'idée

Imaginons un photocopieur très particulier. Au lieu de produire une copie identique, ce photocopieur effectue les opérations suivantes :

1. Réduit l'image d'entrée (par exemple à 50% de sa taille)
2. Duplique cette image réduite plusieurs fois
3. Positionne chaque copie à un endroit précis de la feuille
4. Assemble le tout pour produire l'image de sortie

Comportement asymptotique

Considérons trois images de départ très différentes : un visage souriant, un triangle vide, et un triangle partiellement rempli. Faisons passer chacune dans notre photocopieur spécial, puis repassons le résultat dans le photocopieur, et ainsi de suite.

Après quelques itérations, un phénomène remarquable se produit : toutes les images convergent vers la même image finale — dans notre exemple, le triangle de Sierpiński.

Ce comportement est analogue à celui que nous avons étudié avec les méthodes itératives : quelle que soit la valeur initiale , la suite converge vers le même point fixe .

Le concept d'attracteur

L'image finale vers laquelle toutes les entrées convergent s'appelle l'attracteur du système. C'est l'analogue du point fixe pour les transformations d'images : si on passe l'attracteur dans le photocopieur, on obtient exactement la même image en sortie.

Transformations affines : le formalisme mathématique

Définition

Notre « photocopieur spécial » peut être décrit mathématiquement par un ensemble de transformations affines. Une transformation affine agit sur un point du plan selon :

Cette transformation se décompose en deux parties :

• La partie linéaire encode les opérations de rotation, mise à l'échelle et cisaillement
• La partie translation encode le déplacement

On peut écrire de façon compacte : .

Cas particuliers

Selon les valeurs des paramètres, on obtient différents types de transformations :

Transformations contractantes : la clé de la convergence

Définition

Une transformation est dite contractante s'il existe une constante telle que pour tous points et :

où désigne la distance euclidienne. Le nombre est appelé facteur de contraction.

Interprétation géométrique

Une transformation contractante rapproche les points. Si deux points sont distants de 10 unités et que , leurs images seront distantes d'au plus 5 unités. À chaque application de la transformation, les distances sont réduites.

Lien avec le cours

Cette condition est l'analogue de la condition que nous avons étudiée pour la convergence de la méthode du point fixe. Dans les deux cas, la « contraction » garantit que les itérations successives se rapprochent d'une limite unique.

Pour une transformation affine , la contraction est assurée si toutes les valeurs propres de la matrice sont de module strictement inférieur à 1. En pratique, une condition suffisante simple est que pour une norme matricielle appropriée.

Systèmes de fonctions itérées

Définition

Un système de fonctions itérées (IFS, pour Iterated Function System) est un ensemble fini de transformations contractantes :

L'opérateur de Hutchinson associé à cet IFS est défini par :

Cet opérateur prend un ensemble (par exemple, une image) et renvoie l'union des images de par chacune des transformations.

Le triangle de Sierpiński comme exemple

Le triangle de Sierpiński est l'attracteur d'un IFS composé de trois homothéties de facteur :

Chaque transformation :

• Réduit l'image de moitié ()
• La positionne dans un des trois coins (inférieur gauche, inférieur droit, supérieur)

L'attracteur est l'unique ensemble tel que .

Pourquoi la convergence est-elle garantie ?

Le théorème du point fixe de Banach (que nous avons vu pour la méthode du point fixe) s'étend aux espaces de compacts munis de la distance de Hausdorff. Puisque chaque est contractante, l'opérateur est également contractant, ce qui garantit :

1. L'existence d'un unique attracteur
2. La convergence de la suite vers pour tout ensemble initial

C'est pourquoi notre photocopieur spécial produit toujours la même image finale, quelle que soit l'image de départ.

De la génération à la compression

Le problème direct et le problème inverse

Jusqu'ici, nous avons étudié le problème direct : étant donné un IFS, calculer son attracteur par itération.

Le problème inverse est plus subtil : étant donné une image cible, trouver un IFS dont l'attracteur approche cette image. C'est le fondement de la compression fractale.

Le théorème du collage

Michael Barnsley a établi le théorème du collage (Collage Theorem) qui fournit un critère pratique. En termes simplifiés :

Si une image est « bien approchée » par l'union des images , alors est proche de l'attracteur de l'IFS .

Ce théorème transforme le problème de compression en un problème d'optimisation : trouver les transformations qui « collent » au mieux l'image sur elle-même.

L'autosimilarité des images naturelles

Une observation clé sous-tend la compression fractale : les images naturelles présentent une autosimilarité approximative. Dans une photo de visage, par exemple :

• Certaines régions de la joue ressemblent à d'autres régions après réduction et translation
• Les textures de peau se répètent à différentes échelles
• Les motifs des cheveux présentent des similarités internes

Cette propriété permet de représenter une image non pas par ses pixels, mais par les transformations qui relient ses différentes parties entre elles.

Principe de la compression

Encodage : Au lieu de stocker les valeurs de millions de pixels, on stocke les paramètres d'un petit nombre de transformations affines (6 paramètres par transformation).

Décodage : On part d'une image arbitraire (même du bruit) et on applique itérativement les transformations. Après quelques itérations, l'image converge vers l'approximation de l'image originale.

Cette approche inverse le paradigme habituel : on ne stocke pas « ce que l'image est », mais « comment la reconstruire ».

Un exemple de décompression

Considérons le processus de décompression d'une image (par exemple, le portrait classique « Lena » utilisé en traitement d'images).

Le point fondamental est que l'image de départ n'influence pas le résultat final. Seules les transformations stockées déterminent l'attracteur. Cette propriété découle directement du théorème du point fixe.

Avantages et limitations de l'approche fractale

Avantages théoriques

Résolution indépendante : Puisque l'image est définie par des transformations mathématiques plutôt que par une grille de pixels, on peut théoriquement l'agrandir sans pixelisation. Le système génère des détails cohérents avec sa structure autosimilaire.

Compression asymétrique : La décompression est très rapide (simple application itérative), tandis que la compression est lente (recherche des meilleures transformations). Ce profil peut être avantageux pour des contenus encodés une fois et décodés de nombreuses fois.

Limitations pratiques

Ces limitations expliquent pourquoi la technique est restée principalement académique, malgré quelques applications commerciales dans les années 1990 (Microsoft Encarta, certains jeux vidéo).

Fondements mathématiques des fractales

Les sections qui suivent établissent les fondements rigoureux des concepts introduits intuitivement ci-dessus.

La notion de fractale et la dimension de Hausdorff

Origine du terme

Benoît Mandelbrot (1924-2010) a introduit le terme « fractale » en 1975 dans Les objets fractals : forme, hasard et dimension, puis développé cette théorie dans The Fractal Geometry of Nature (1982). L'étymologie provient du latin fractus (irrégulier, brisé).

Définition formelle

Définition (Mandelbrot, 1982) : Un ensemble est une fractale si sa dimension de Hausdorff est strictement supérieure à sa dimension topologique :

La dimension topologique est toujours entière, tandis que la dimension de Hausdorff peut être non-entière, d'où l'appellation « dimension fractionnaire ».

La mesure de Hausdorff

Felix Hausdorff (1868-1942) a introduit cette mesure dans Dimension und äußeres Maß (Mathematische Annalen, 1918).

Pour un espace métrique et , la mesure de Hausdorff α-dimensionnelle est définie par :

La dimension de Hausdorff est alors :

Calcul pour les ensembles auto-similaires

Pour les ensembles auto-similaires générés par similitudes de facteurs de contraction satisfaisant la condition de l'ensemble ouvert (théorème de Moran, 1946 ; Hutchinson, 1981), la dimension est l'unique solution positive de :

Pour des similitudes de même facteur : .

Exemples classiques

Le théorème du point fixe de Banach

Contexte historique

Stefan Banach (1892-1945) a présenté ce résultat fondamental dans sa thèse (24 juin 1920), publiée en 1922 : « Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales », Fundamenta Mathematicae 3, 133-181.

Définitions préliminaires

Définition (Espace métrique complet) : Un espace métrique est complet si toute suite de Cauchy dans converge vers un élément de .

Définition (Contraction) : Une application est une contraction s'il existe tel que :

Le nombre est le facteur de contraction (ou constante de Lipschitz).

Énoncé du théorème

Ce théorème est la pierre angulaire de la compression fractale : il garantit que l'application itérée des transformations contractantes converge vers une image unique, indépendamment du point de départ.

Systèmes de fonctions itérées : la formulation de Hutchinson

L'article fondateur

John E. Hutchinson a formalisé les IFS dans l'article « Fractals and Self-Similarity », Indiana University Mathematics Journal 30 (1981), 713-747.

Définitions formelles

Définition (IFS) : Un système de fonctions itérées est un ensemble fini de contractions sur un espace métrique complet :

où chaque satisfait avec .

Définition (Opérateur de Hutchinson) : L'opérateur est défini sur l'ensemble des parties compactes non-vides de par :

La distance de Hausdorff

La distance de Hausdorff entre compacts est définie par :

Lemme de Hutchinson (1981) : L'opérateur est une contraction sur avec constante .

Théorème d'existence de l'attracteur

Le théorème du collage de Barnsley

Contexte

Michael F. Barnsley a énoncé ce résultat dans Fractals Everywhere (Academic Press, 1988, 2ᵉ édition 1993).

Énoncé

Interprétation

Si un ensemble est « proche » de son image par l'opérateur de Hutchinson (son « collage »), alors est proche de l'attracteur . C'est le fondement du problème inverse : trouver un IFS dont l'attracteur approche une image cible.

Construction du triangle de Sierpiński

Contexte historique

Wacław Sierpiński (1882-1969) a décrit cette construction en 1915 : « Sur une courbe cantorienne dont tout point est un point de ramification », Comptes Rendus Acad. Sci. 160, 302-305.

Construction géométrique

À partir d'un triangle équilatéral :

1. Diviser en 4 triangles en reliant les milieux des côtés
2. Retirer le triangle central
3. Répéter sur chaque triangle restant

IFS associé

Avec sommets , , :

Propriétés

• Chaque transformation est une homothétie de rapport
• Dimension de Hausdorff :
• Aire nulle mais « périmètre » infini

L'article fondateur de Jacquin (1992)

Contexte et contribution

L'article d'Arnaud E. Jacquin « Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations », publié dans IEEE Transactions on Image Processing, Vol. 1, No. 1, pp. 18-30 (janvier 1992), constitue le tournant décisif de la compression fractale.

Issu de sa thèse dirigée par Michael Barnsley à Georgia Tech (1989), cet article résout le problème majeur des IFS classiques : l'automatisation. Les travaux antérieurs de Barnsley et Demko nécessitaient une intervention humaine intensive — environ 100 heures par image. L'innovation de Jacquin est le Système de Fonctions Itérées Partitionnées (PIFS), qui permet un encodage entièrement automatique.

Le PIFS : exploiter l'autosimilarité locale

La différence fondamentale entre IFS et PIFS réside dans la nature de l'autosimilarité exploitée :

Une image en niveaux de gris est modélisée comme le graphe d'une fonction , où est le support et l'intensité.

L'algorithme de partitionnement

Range blocks (blocs de destination)

Partition non-chevauchante de l'image en blocs carrés, typiquement 4×4, 8×8 ou 16×16 pixels. Pour une image 512×512 avec blocs 8×8 : 4 096 range blocks.

Domain blocks (blocs source)

Blocs plus grands (typiquement 2× la taille des range blocks), avec chevauchement possible. Le sous-échantillonnage 2:1 réduit chaque domain block à la taille du range block par moyenne des 4 pixels voisins.

Transformations affines contractantes

Chaque transformation combine une transformation géométrique et un ajustement photométrique :

où :

• : similitude géométrique de facteur 0.5
• : facteur de contraste (scaling), contraint à
• : décalage de luminosité (offset)

Les 8 isométries du groupe diédral multiplient le codebook : identité, rotations (90°, 180°, 270°), et 4 réflexions.

Algorithme d'encodage

Pour chaque range block , l'algorithme recherche le meilleur domain block par minimisation aux moindres carrés.

Contraste optimal :

Luminosité optimale :

Complexité algorithmique : Avec range blocks et domain blocks, la recherche exhaustive nécessite comparaisons.

Résultats expérimentaux

Pour l'image Lena (512×512, 8 bits/pixel) :

Évolution et état actuel

L'autosimilarité dans les codecs vidéo modernes

Intra Block Copy (IBC)

L'Intra Block Copy est l'héritier direct de la compression fractale. Il prédit un bloc à partir d'un bloc similaire dans la zone déjà reconstruite de la même frame.

HEVC Screen Content Coding (2015-2016) a introduit l'IBC standardisé, avec jusqu'à 50% de réduction BD-rate pour le contenu écran.

VVC/H.266 (2020) intègre l'IBC nativement avec des améliorations comme le Flipping and Rotation IBC (FR-IBC).

AV1 (Alliance for Open Media, 2018) implémente IntraBC avec recherche par tables de hachage, permettant 27.1% d'économie de bitrate pour le contenu écran.

Super-résolution par autosimilarité interne

L'article de Glasner, Bagon et Irani « Super-Resolution from a Single Image » (ICCV 2009, Weizmann Institute) a démontré que les patches d'une image naturelle se répètent de manière redondante tant au sein de la même échelle qu'à travers différentes échelles.

Cette observation a permis la super-résolution à partir d'une seule image, sans base de données externe, en exploitant l'autosimilarité interne.

Non-Local Means et BM3D

Non-Local Means (Buades, Coll, Morel, 2005) calcule une moyenne pondérée de tous les pixels, les poids étant fonction de la similarité des patches environnants.

BM3D (Dabov, Foi et al., 2007) — Block-Matching and 3D Filtering — groupe les patches similaires en cylindres 3D et applique un seuillage collaboratif. Cette méthode est restée l'état de l'art en débruitage pendant plus de 15 ans.

Les raisons du déclin de la compression fractale pure

La compression fractale a été supplantée pour plusieurs raisons :

• Asymétrie encodage/décodage extrême : ratio temps typique de 1000:1 à 10000:1
• Complexité d'encodage prohibitive : recherche exhaustive
• Arrivée des wavelets : JPEG2000 (2000) offre une performance comparable avec complexité maîtrisée

Toutefois, les principes d'autosimilarité perdurent sous des formes évoluées dans les codecs modernes et les algorithmes de restauration d'images.

Connexions avec l'apprentissage profond

Parallèles conceptuels

Les liens entre compression fractale et réseaux de neurones sont à la fois structurels et fonctionnels :

FractalNet : architecture explicitement autosimilaire

Larsson, Maire et Shakhnarovich (2016, ICLR 2017) ont proposé FractalNet, une architecture CNN construite sur le principe de la géométrie fractale. Une règle d'expansion récursive génère des réseaux profonds dont la structure est une fractale tronquée, sans connexions résiduelles.

Le réseau égale ResNet sur CIFAR-10/100 et ImageNet, démontrant que les représentations résiduelles ne sont pas fondamentales pour la performance.

Modèles de diffusion et processus itératifs

Les DDPM (Denoising Diffusion Probabilistic Models) de Ho, Jain et Abbeel (NeurIPS 2020) présentent un parallèle conceptuel avec la reconstruction fractale :

Super-résolution neuronale et autosimilarité

L'évolution de SRCNN (2014) à ESRGAN (2018) puis SSGAN (Wang et al., 2023) illustre le retour explicite à l'autosimilarité. SSGAN intègre un Downscale Attention Block et un Upscale Attention Block exploitant les similarités cross-scale.

Dimension fractale comme feature

La dimension fractale reste utile en deep learning. Roberto et al. (2020) ont développé le Fractal Neural Network (FNN) combinant features fractales et CNN, atteignant jusqu'à 99.62% de précision sur des datasets histologiques.

El Zini et Awad (arXiv:2401.04141, 2024) ont montré que les CNN profonds ne parviennent pas à encoder directement la dimension fractale, suggérant que ces features géométriques restent complémentaires aux représentations apprises.

Conclusion

La compression fractale illustre une convergence entre théorie mathématique pure et applications pratiques. Les fondements — théorème de Banach, opérateur de Hutchinson, théorème du collage — fournissent un cadre rigoureux pour exploiter l'autosimilarité inhérente aux images naturelles.

L'algorithme PIFS de Jacquin (1992) a démontré la faisabilité de cette approche, malgré sa complexité d'encodage. Bien que supplantée par les wavelets puis les méthodes neuronales, la compression fractale a profondément influencé le traitement d'images moderne :

• L'Intra Block Copy des codecs VVC et AV1 incarne directement ses principes
• La super-résolution par autosimilarité interne prolonge ses intuitions
• Les modèles de diffusion partagent sa structure de convergence itérative vers un attracteur

L'héritage le plus durable est peut-être conceptuel : l'idée que l'information visuelle possède une structure auto-référentielle exploitable pour la compression, la restauration et la génération.

Pour aller plus loin

Expérimentations suggérées

• Implémenter le triangle de Sierpiński avec le « jeu du chaos » (algorithme stochastique)
• Visualiser la convergence vers l'attracteur avec différentes images de départ
• Comparer visuellement les artefacts de JPEG et de la compression fractale

Références

Fondements mathématiques

• Banach, S. (1922). Sur les opérations dans les ensembles abstraits. Fundamenta Mathematicae, 3, 133-181.
• Hausdorff, F. (1918). Dimension und äußeres Maß. Mathematische Annalen, 79, 157-179.
• Hutchinson, J.E. (1981). Fractals and Self-Similarity. Indiana University Mathematics Journal, 30, 713-747.
• Barnsley, M.F. (1988). Fractals Everywhere. Academic Press.
• Mandelbrot, B.B. (1982). The Fractal Geometry of Nature. W.H. Freeman.
• Falconer, K. (2003). Fractal Geometry: Mathematical Foundations and Applications, 2nd ed. Wiley.

Compression fractale

• Jacquin, A.E. (1992). Image coding based on a fractal theory of iterated contractive image transformations. IEEE Trans. Image Processing, 1(1), 18-30.
• Fisher, Y. (1995). Fractal Image Compression: Theory and Application. Springer-Verlag.
• Davis, G.M. (1998). A wavelet-based analysis of fractal image compression. IEEE Trans. Image Processing, 7(2), 141-154.

Applications modernes

• Glasner, D., Bagon, S., & Irani, M. (2009). Super-resolution from a single image. ICCV.
• Dabov, K., Foi, A., et al. (2007). Image denoising by sparse 3-D transform-domain collaborative filtering. IEEE Trans. Image Processing, 16(8), 2080-2095.
• Xu, X., et al. (2016). Intra Block Copy in HEVC Screen Content Coding. IEEE JETCAS, 6(4), 409-419.

Deep learning

• Larsson, G., Maire, M., & Shakhnarovich, G. (2016). FractalNet: Ultra-Deep Neural Networks without Residuals. arXiv:1605.07648.
• Ballé, J., Laparra, V., & Simoncelli, E.P. (2017). End-to-end Optimized Image Compression. ICLR.
• Ho, J., Jain, A., & Abbeel, P. (2020). Denoising Diffusion Probabilistic Models. NeurIPS.

Ressources en ligne

• Triangle de Sierpiński — Wikipédia