Compression fractale : reconstruire une image par transformations

Introduction : stocker une règle plutôt que des pixels

Une image numérique ordinaire ressemble à une table immense. Chaque position contient une intensité ou une couleur. La compression tente de représenter cette table avec moins de bits.

JPEG transforme des blocs en fréquences et quantifie leurs coefficients. D'autres codecs utilisent la prédiction, les ondelettes, des transformations plus grandes, des modèles de contexte ou des réseaux neuronaux.

La compression fractale prend une direction étonnamment différente. Elle cherche des régions qui ressemblent à d'autres régions après transformation. Un toit ressemble peut-être à un autre toit plus petit. Une zone de feuillage peut ressembler à une autre après rotation. Une texture peut réapparaître avec un contraste différent.

Au lieu de stocker directement les pixels d'un bloc, on peut stocker une instruction : « Prends cette autre région, réduis-la, tourne-la, ajuste son contraste et sa luminosité, puis place-la ici. » Une image entière peut alors être décrite par une collection de transformations.

Le décodeur ne lit pas simplement une grille de valeurs. Il exécute les transformations de façon répétée. Après plusieurs itérations, l'image se stabilise. La représentation compressée agit comme un petit programme dont l'image est le résultat fixe.

Cette idée paraît paradoxale. Comment reconstruire une image en utilisant des morceaux de l'image qui n'existent pas encore au début du décodage? La réponse vient du théorème du point fixe.

Une image comme point dans un espace

Une image de largeur W et hauteur H peut être vue comme un vecteur contenant WH intensités. Une image couleur possède encore davantage de composantes. Deux images peuvent être comparées par une distance quadratique :

Dans cet espace, une transformation W prend une image complète en entrée et produit une nouvelle image. Le décodeur applique X_(n+1) = W(X_n). La question devient : la suite converge-t-elle vers une image unique? Si oui, cette image X* vérifie W(X*) = X*. Elle est un point fixe.

La contraction et le théorème du point fixe

Une transformation W est contractante s'il existe un nombre s avec 0 ≤ s < 1 tel que, pour toutes les images X et Y :

Le théorème du point fixe de Banach garantit alors l'existence d'un point fixe unique X*, la convergence vers X* depuis n'importe quel état initial, et une vitesse de convergence contrôlée par s. Après n itérations :

Si s = 0,5, après dix itérations l'écart maximal est divisé par environ 1 024. Si s est proche de 1, la convergence est beaucoup plus lente.

IFS : quelques transformations, un attracteur

Un système de fonctions itérées, ou IFS, contient plusieurs transformations contractantes w₁, w₂, …, w_K. Pour un ensemble de points S, l'opérateur de Hutchinson est :

Répéter W produit un attracteur invariant A tel que W(A) = A. La fougère de Barnsley constitue un exemple pédagogique célèbre. Quatre transformations affines suffisent à produire une tige, une grande feuille et deux petites feuilles latérales. Le chaos game applique une transformation choisie probabilistiquement à un point. Après un transitoire, les points dessinent la fougère.

Ce résultat montre qu'une structure visuellement complexe peut être la conséquence d'un petit ensemble de règles. Mais une photographie ordinaire n'est pas une fougère IFS exacte. Pour coder des images naturelles, il faut une version locale et approximative.

Le théorème du collage : résoudre le problème inverse

Générer un attracteur à partir d'un IFS est un problème direct. La compression doit résoudre le problème inverse : étant donné une image cible X, trouver W dont le point fixe X* ressemble à X. Le théorème du collage fournit le principe. Supposons que W soit contractante avec facteur s. Si d(X, W(X)) ≤ ε, alors :

L'expression d(X, W(X)) est l'erreur de collage. Le codeur cherche donc un opérateur qui transforme l'image en une version aussi proche que possible d'elle-même. La borne montre deux choses : une petite erreur de collage est souhaitable, et le facteur de contraction compte. Le théorème du collage ne trouve pas automatiquement le meilleur code. Il transforme le problème inverse en objectif d'approximation.

Pourquoi une photographie n'est pas une fougère parfaite

Une fougère mathématique possède une autosimilarité exacte. Une photographie contient plutôt textures, ombres, perspective, objets uniques, bruit et variations locales. La similarité y est partielle. Une zone peut ressembler à une autre seulement après réduction, rotation, changement de contraste et avec une erreur résiduelle.

Le succès de la compression fractale ne dépend donc pas de l'affirmation « toute photo est fractale ». Il dépend d'une hypothèse plus modeste : de nombreux blocs d'une image peuvent être approximés par des versions transformées d'autres blocs. Jacquin a appelé cette propriété la self-transformability par blocs.

De l'IFS au PIFS

Un IFS classique applique chaque fonction à l'ensemble entier. Pour une image naturelle, on utilise plutôt un partitioned iterated function system, ou PIFS. L'image cible est divisée en blocs non chevauchants appelés blocs cible, ou range blocks. Pour chaque bloc cible R_i, le codeur cherche un bloc domaine D_j, généralement plus grand. Le domaine est réduit à la taille de la cible. Une transformation géométrique g et une transformation photométrique p sont appliquées :

Le code associé au bloc contient typiquement : position du domaine, orientation, facteur de contraste, décalage de luminosité, taille du bloc, information de partition. L'ensemble de ces codes définit l'opérateur global.

Blocs cible et blocs domaine

Supposons une image 512 × 512. On peut utiliser des blocs cible de 8 × 8 et des domaines de 16 × 16, éventuellement chevauchants. Chaque domaine est réduit à 8 × 8, souvent par moyenne. Pourquoi prendre un domaine plus grand? La réduction spatiale contribue à la contractivité et exploite la similarité entre échelles.

Pour chaque bloc cible, le codeur peut devoir tester des milliers de domaines, huit symétries et les paramètres photométriques. C'est là que le coût apparaît. Le décodeur, lui, connaît déjà toutes les correspondances.

Les transformations géométriques

Pour un bloc carré, on utilise souvent huit isométries :

• Identité
• Rotation 90°
• Rotation 180°
• Rotation 270°
• Réflexion horizontale
• Réflexion verticale
• Réflexion diagonale
• Réflexion antidiagonale

La réduction du domaine vers la taille de la cible joue un rôle central dans la contractivité spatiale. Des modèles plus flexibles peuvent utiliser des transformations affines, des domaines rectangulaires ou des partitions irrégulières. Plus le modèle est flexible, plus le code et la recherche deviennent coûteux.

Contraste et luminosité

Après la transformation géométrique, on ajuste les intensités :

où s est le facteur de contraste et o le décalage de luminance. Pour assurer la stabilité photométrique, on limite souvent |s| < 1.

Si s = 1 et o = 0, les intensités sont conservées. Si s = 0, le bloc produit une région uniforme égale à o. Si s est négatif, le contraste est inversé. Les valeurs doivent aussi être quantifiées et limitées.

Ajuster une transformation par moindres carrés

Après réduction et orientation, le domaine fournit dᵢ et la cible rᵢ. On minimise :

Pour n pixels, la solution analytique est :

Si le dénominateur est nul, le domaine est uniforme. Une implémentation robuste peut alors utiliser s = 0 et o égal à la moyenne cible. Après calcul, s est limité à la plage contractante et quantifié. La meilleure correspondance minimise l'erreur après ces opérations.

L'algorithme d'encodage

Un encodeur de base suit cette procédure : diviser l'image en blocs cible, construire un pool de domaines plus grands, puis pour chaque cible tester chaque domaine, réduire le domaine, tester les huit symétries, calculer s et o, calculer l'erreur, conserver le meilleur code. Enfin quantifier les paramètres et stocker les codes et la partition.

Pourquoi l'encodage coûte cher

Soit N_R le nombre de blocs cible, N_D le nombre de domaines, K le nombre de symétries, P les pixels par bloc. La recherche exhaustive coûte grossièrement :

Le coût est asymétrique : encoder exige une recherche, décoder applique les codes. Les méthodes d'accélération incluent : classification par variance, classification par moments, signatures de blocs, réduction du pool domaine, recherche au plus proche voisin, arbres k-d, quantification vectorielle, quadtree, parallélisation, GPU, recherche approximative. Saupe a montré que la recherche domaine–cible peut être reformulée comme un problème de plus proche voisin multidimensionnel.

Quadtree et partition adaptative

Une partition fixe gaspille des bits dans les régions simples et manque de détails dans les régions complexes. Le quadtree commence avec de grands blocs. Pour chaque bloc cible : si l'erreur est sous un seuil, garder le bloc; sinon, le diviser en quatre; répéter jusqu'à une taille minimale.

Un seuil bas produit plus de blocs, plus de bits et une meilleure fidélité. Un seuil élevé donne un fichier plus petit et davantage d'erreur. La structure du quadtree doit elle-même être codée.

L'algorithme de décodage

Le décodeur peut commencer avec une image noire, blanche, du bruit ou une image arbitraire. À chaque itération, il reconstruit chaque bloc cible à partir du domaine désigné dans l'image précédente. Pour chaque code : lire le domaine dans X_n, le réduire, appliquer la symétrie, appliquer s et o, écrire le résultat dans X_(n+1). Après tous les blocs : X_(n+1) = W(X_n).

Deux tampons séparés sont nécessaires pour éviter qu'un bloc déjà écrit modifie les calculs de la même itération.

Pourquoi l'image initiale n'a presque pas d'importance

Si W est contractante, deux images initiales X₀ et Y₀ vérifient :

Leur différence disparaît exponentiellement. Après suffisamment d'itérations, elles deviennent presque identiques. Un décodeur peut partir d'un damier, d'un gradient ou d'un portrait différent. La mémoire de cet état initial s'efface. L'information stable est contenue dans les transformations.

Vitesse de convergence et facteur de contraction

Pour atteindre une tolérance relative τ, le nombre d'itérations nécessaires est :

Exemples : s_max = 0,5 et τ = 10⁻³ donnent environ 10 itérations. s_max = 0,9 exige environ 66 itérations. Le cas non contractant doit être présenté comme une démonstration hors garantie, pas comme un codec valide.

Mesurer l'erreur : MSE, PSNR, SSIM et débit

L'erreur quadratique moyenne est :

Pour une image 8 bits :

Un PSNR élevé indique une faible erreur quadratique, mais pas nécessairement une meilleure apparence. SSIM compare la luminance, le contraste et la structure locale. Le débit est exprimé en bits par pixel : bpp = taille du code en bits / nombre de pixels. Une comparaison honnête utilise une courbe débit–distorsion avec le même jeu d'images et le même protocole.

Les artefacts typiques

• Répétition artificielle de textures
• Contours adoucis
• Détails uniques remplacés par des motifs proches
• Blocs visibles
• Aplats
• Inversion ou compression excessive du contraste
• Erreurs autour des frontières de partition
• Aspect peint ou synthétique

Les textures répétitives sont souvent plus favorables que le texte fin, les visages, les symboles et les détails uniques.

Zoom fractal : promesse et limite

Un code de transformations peut être décodé sur une grille plus fine. Cela évite une simple duplication de pixels et peut produire une interpolation cohérente avec le modèle. Mais le code ne contient pas la vérité perdue. Il contient des relations. À plus haute résolution, il génère des détails compatibles avec ces relations. Ces détails peuvent être plausibles, mais non authentiques.

JPEG contre compression fractale

JPEG divise l'image en blocs, applique une DCT, quantifie les coefficients, code les valeurs, décode directement. La compression fractale cherche des relations entre blocs, stocke des transformations, décode par itération, exploite une redondance intra-image entre positions et échelles.

JPEG possède un encodage rapide et un immense écosystème. La compression fractale possède un décodage génératif et une asymétrie forte. Elle n'est pas automatiquement meilleure à haut taux de compression. Les performances dépendent de l'image, de l'implémentation, du débit, du budget de calcul et de la métrique.

Pourquoi la méthode n'a pas dominé

• Encodage coûteux
• Qualité très dépendante de l'image
• Contrôle du débit difficile
• Concurrence de standards rapides et ouverts
• Historique de brevets et d'implémentations propriétaires
• Promesses commerciales parfois excessives

La technique reste néanmoins scientifiquement précieuse. Elle démontre une compression comme résolution d'un problème inverse.

Ce qu'elle a apporté à l'informatique

La compression fractale illustre :

• Une image comme programme
• Le décodage par point fixe
• La prédiction non locale
• La redondance entre échelles
• La représentation multi-résolution
• L'optimisation nearest neighbor
• La frontière entre compression et modélisation

Relations avec les représentations génératives modernes

Il existe une analogie conceptuelle avec certaines représentations modernes. Dans les deux cas, on stocke des paramètres et on exécute un décodeur. Mais un PIFS classique utilise des transformations explicites, cherche des correspondances dans l'image et garantit la convergence par contractivité. Une représentation neuronale apprend une fonction paramétrique, n'est pas nécessairement contractante et peut utiliser des données externes.

Il faut parler de convergence d'idées, pas d'identité technologique.

Où est la spirale?

La compression fractale ne prouve pas que les images sont des spirales. Son lien le plus important est la convergence vers un point fixe. Une contraction plane avec rotation peut s'écrire :

avec |a| < 1. La distance au point fixe diminue comme |a|ⁿ tandis que l'angle augmente de θ. La trajectoire forme alors une spirale discrète.

Dans l'espace des images, le décodeur suit une trajectoire de dimension immense. Elle n'est pas visible comme une spirale ordinaire. Le sujet illustre donc la thèse du site : une structure mathématique peut réapparaître dans un nouveau domaine sans que tous les objets aient la même forme ni la même origine.

Conclusion

La compression fractale remplace une question de stockage par une question de génération. Au lieu de demander « quels pixels composent l'image? », elle demande : « Quel ensemble de transformations possède une image semblable comme point fixe? »

Le codeur cherche des correspondances entre régions. Le décodeur applique les transformations. La contractivité efface l'état initial. Le point fixe apparaît.

Cette élégance mathématique n'a pas suffi à en faire le codec généraliste dominant. L'encodage est coûteux, la qualité dépend du contenu et les formats concurrents ont bénéficié d'un immense écosystème. Mais la technique conserve une valeur conceptuelle exceptionnelle. Elle montre qu'une image peut être décrite non comme une liste, mais comme un système.