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 $X_{n+1} = g(X_n)$ peut converger vers un point fixe $r$ si certaines conditions sont respectées, notamment $|g'(r)| < 1$ .

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 :

Réduit l'image d'entrée (par exemple à 50% de sa taille)
Duplique cette image réduite plusieurs fois
Positionne chaque copie à un endroit précis de la feuille
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 $X_0$ , la suite $X_{n+1} = g(X_n)$ converge vers le même point fixe $r$ .

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 $w$ agit sur un point $(x, y)$ du plan selon :

w \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} + \begin{pmatrix} e \\ f \end{pmatrix}

Cette transformation se décompose en deux parties :

La partie linéaire $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ encode les opérations de rotation, mise à l'échelle et cisaillement
La partie translation $\mathbf{t} = \begin{pmatrix} e \\ f \end{pmatrix}$ encode le déplacement

On peut écrire de façon compacte : $w(\mathbf{x}) = A\mathbf{x} + \mathbf{t}$ .

Cas particuliers

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

Type	Matrice A	Effet
Homothétie (facteur r)	$\begin{pmatrix} r & 0 \\ 0 & r \end{pmatrix}$	Agrandissement ou réduction uniforme
Rotation (angle θ)	$\begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$	Rotation autour de l'origine
Réflexion (axe x)	$\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$	Symétrie horizontale

Transformations contractantes : la clé de la convergence

Définition

Une transformation $w$ est dite contractante s'il existe une constante $0 \leq s < 1$ telle que pour tous points $P$ et $Q$ :

d(w(P), w(Q)) \leq s \cdot d(P, Q)

où $d$ désigne la distance euclidienne. Le nombre $s$ 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 $s = 0.5$ , 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 $|g'(r)| < 1$ 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 $w(\mathbf{x}) = A\mathbf{x} + \mathbf{t}$ , la translation disparaît dans la différence : $d(w(P), w(Q)) = \|A(P - Q)\|$ . La contraction au sens de la distance euclidienne est donc assurée si et seulement si la plus grande valeur singulière de $A$ est strictement inférieure à 1, c'est-à-dire $\|A\|_2 < 1$ . Une condition portant sur les seules valeurs propres ne suffit pas : la matrice de cisaillement $A = \begin{pmatrix} 0.5 & 10 \\ 0 & 0.5 \end{pmatrix}$ n'a que $0.5$ comme valeur propre, mais elle envoie les points $(0, 0)$ et $(0, 1)$ , distants de 1, sur deux points distants de $\sqrt{100.25} \approx 10.01$ .

💡

Condition de contraction

Pour une homothétie de facteur $r$ , la transformation est contractante si et seulement si $|r| < 1$ . C'est pourquoi notre photocopieur spécial réduit les images avant de les dupliquer.

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 :

\mathcal{F} = \{w_1, w_2, \ldots, w_N\}

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

W(A) = \bigcup_{i=1}^{N} w_i(A) = w_1(A) \cup w_2(A) \cup \cdots \cup w_N(A)

Cet opérateur prend un ensemble $A$ (par exemple, une image) et renvoie l'union des images de $A$ 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 $\frac{1}{2}$ :

w_1(\mathbf{x}) = \frac{1}{2}\mathbf{x}, \quad w_2(\mathbf{x}) = \frac{1}{2}\mathbf{x} + \begin{pmatrix} 1/2 \\ 0 \end{pmatrix}, \quad w_3(\mathbf{x}) = \frac{1}{2}\mathbf{x} + \begin{pmatrix} 1/4 \\ \sqrt{3}/4 \end{pmatrix}

Chaque transformation :

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

L'attracteur est l'unique ensemble $K$ tel que $K = W(K) = w_1(K) \cup w_2(K) \cup w_3(K)$ .

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 $w_i$ est contractante, l'opérateur $W$ est également contractant, ce qui garantit :

L'existence d'un unique attracteur $K$
La convergence de la suite $W^n(A_0)$ vers $K$ pour tout ensemble initial $A_0$

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 $L$ est « bien approchée » par l'union des images $w_1(L) \cup w_2(L) \cup \cdots \cup w_N(L)$ , alors $L$ est proche de l'attracteur de l'IFS $\{w_1, \ldots, w_N\}$ .

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

Itération	État de l'image
0	Image de départ quelconque (grille, bruit, noir...)
1	Structures grossières commencent à apparaître
2	Formes principales reconnaissables
10	Image nette, proche de l'originale

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

⚠️

Limitations

La compression fractale n'a pas remplacé les méthodes classiques pour plusieurs raisons :

Temps de compression prohibitif (recherche exhaustive des correspondances)
Ratio de compression pas systématiquement supérieur à JPEG
Complexité d'implémentation et de mise au point

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 $F \subset \mathbb{R}^n$ est une fractale si sa dimension de Hausdorff $D_H$ est strictement supérieure à sa dimension topologique $D_T$ :

D_H(F) > D_T(F)

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 $(X, d)$ et $E \subset X$ , la mesure de Hausdorff α-dimensionnelle est définie par :

\mathcal{H}^{\alpha}_{\delta}(E) := \inf \left\{ \sum_{i=1}^{\infty} (\text{diam } E_i)^{\alpha} : E \subset \bigcup_{i=1}^{\infty} E_i, \quad \text{diam}(E_i) < \delta \right\}

\mathcal{H}^{\alpha}(E) := \lim_{\delta \to 0} \mathcal{H}^{\alpha}_{\delta}(E)

La dimension de Hausdorff est alors :

\dim_H(E) := \inf\{s \geq 0 : \mathcal{H}^s(E) = 0\} = \sup\{s \geq 0 : \mathcal{H}^s(E) = \infty\}

Calcul pour les ensembles auto-similaires

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

\sum_{i=1}^{N} r_i^D = 1

Pour des similitudes de même facteur $r$ : $D = \frac{\log(N)}{\log(1/r)}$ .

Exemples classiques

Fractale	N	r	Dimension D
Ensemble de Cantor (1883)	2	1/3	$\frac{\log 2}{\log 3} \approx 0.631$
Triangle de Sierpiński (1915)	3	1/2	$\frac{\log 3}{\log 2} \approx 1.585$
Courbe de Koch (1904)	4	1/3	$\frac{\log 4}{\log 3} \approx 1.262$
Tapis de Sierpiński	8	1/3	$\frac{\log 8}{\log 3} \approx 1.893$

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 $(X, d)$ est complet si toute suite de Cauchy dans $X$ converge vers un élément de $X$ .

Définition (Contraction) : Une application $T : X \to X$ est une contraction s'il existe $q \in [0, 1)$ tel que :

d(T(x), T(y)) \leq q \cdot d(x, y), \quad \forall x, y \in X

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

Énoncé du théorème

🚨

Théorème du point fixe de Banach (1922)

Soit $(X, d)$ un espace métrique complet non vide et $T : X \to X$ une contraction de constante $q \in [0, 1)$ . Alors :

$T$ possède un unique point fixe $x^* \in X$ tel que $T(x^*) = x^*$ .
Pour tout $x_0 \in X$ , la suite $x_{n+1} = T(x_n)$ converge vers $x^*$ .
Estimations de convergence :
- $d(x^*, x_n) \leq q^n \cdot d(x^*, x_0)$
- $d(x^*, x_n) \leq \frac{q^n}{1-q} \cdot d(x_1, x_0)$

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 :

\mathcal{F} = \{f_1, f_2, \ldots, f_N\}, \quad f_i : X \to X

où chaque $f_i$ satisfait $d(f_i(x), f_i(y)) \leq r_i \cdot d(x, y)$ avec $r_i \in [0, 1)$ .

Définition (Opérateur de Hutchinson) : L'opérateur $F : \mathcal{H}(X) \to \mathcal{H}(X)$ est défini sur l'ensemble $\mathcal{H}(X)$ des parties compactes non-vides de $X$ par :

F(A) = \bigcup_{i=1}^{N} f_i(A) = f_1(A) \cup f_2(A) \cup \cdots \cup f_N(A)

La distance de Hausdorff

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

h(A, B) = \max\left\{ \sup_{a \in A} d(a, B), \sup_{b \in B} d(b, A) \right\}

Lemme de Hutchinson (1981) : L'opérateur $F$ est une contraction sur $(\mathcal{H}(X), h)$ avec constante $r = \max\{r_1, \ldots, r_N\} < 1$ .

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

🚨

Théorème d'existence de l'attracteur (Hutchinson, 1981)

Soit $(X, d)$ un espace métrique complet et $\mathcal{S} = \{S_1, \ldots, S_N\}$ un IFS de contractions. Alors il existe un unique compact non-vide $K$ tel que :

K = F(K) = \bigcup_{i=1}^{N} S_i(K)

L'ensemble $K$ est l'attracteur de l'IFS. Pour tout compact initial $K_0$ , la suite $F^n(K_0)$ converge vers $K$ dans la métrique de Hausdorff.

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é

🚨

Théorème du collage (Barnsley, 1988)

Soit $(X, d)$ un espace métrique complet et $\{w_1, \ldots, w_N\}$ un IFS avec facteur de contraction $s \in [0, 1)$ . Soit $A$ l'attracteur. Pour tout compact non-vide $L \subset X$ :

h(L, A) \leq \frac{1}{1-s} \cdot h\left(L, \bigcup_{n=1}^{N} w_n(L)\right)

Interprétation

Si un ensemble $L$ est « proche » de son image par l'opérateur de Hutchinson (son « collage »), alors $L$ est proche de l'attracteur $A$ . 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 :

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

IFS associé

Avec sommets $A = (0, 0)$ , $B = (1, 0)$ , $C = (1/2, \sqrt{3}/2)$ :

f_1(\mathbf{x}) = \frac{1}{2}\mathbf{x}, \quad f_2(\mathbf{x}) = \frac{1}{2}\mathbf{x} + \begin{pmatrix} 1/2 \\ 0 \end{pmatrix}, \quad f_3(\mathbf{x}) = \frac{1}{2}\mathbf{x} + \begin{pmatrix} 1/4 \\ \sqrt{3}/4 \end{pmatrix}

Propriétés

Chaque transformation est une homothétie de rapport $r = 1/2$
Dimension de Hausdorff : $D = \frac{\log 3}{\log 2} \approx 1.585$
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 :

IFS Classique	PIFS (Jacquin)
Transformations globales	Transformations locales
L'image = copies réduites d'elle-même	Portions similaires à d'autres portions
Limité aux fractales « pures »	Applicable à toute image naturelle

Une image en niveaux de gris est modélisée comme le graphe $G \subset \mathbb{R}^3$ d'une fonction $f : S \to \mathbb{R}$ , où $S \subset \mathbb{R}^2$ est le support et $f(x,y)$ 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 $w_i$ combine une transformation géométrique et un ajustement photométrique :

w_i(x, y, z) = (A_i(x, y), s \cdot z + o)

où :

$A_i$ : similitude géométrique de facteur 0.5
$s$ : facteur de contraste (scaling), contraint à $|s| < 1$
$o$ : décalage de luminosité (offset)

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

Algorithme d'encodage

Pour chaque range block $R_{k,l}$ , l'algorithme recherche le meilleur domain block $D_{i,j}$ par minimisation aux moindres carrés.

Contraste optimal :

\alpha = \frac{N_s \cdot \sum(D_{mn} \cdot R_{mn}) - \sum D_{mn} \cdot \sum R_{mn}}{N_s \cdot \sum D_{mn}^2 - (\sum D_{mn})^2}

Luminosité optimale :

\beta = \frac{\sum R_{mn} - \alpha \cdot \sum D_{mn}}{N_s}

Complexité algorithmique : Avec $n_r$ range blocks et $n_d$ domain blocks, la recherche exhaustive nécessite $O(n_r \times n_d \times 8)$ comparaisons.

Résultats expérimentaux

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

Configuration	Ratio	PSNR
Range 4×4	~10:1	33-35 dB
Range 8×8	~18-22:1	30-32 dB
Range 16×16	~85-97:1	26-27 dB

É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 $O(n^2)$
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 :

Concept Fractal	Équivalent Deep Learning
Représentation compacte par IFS	Espace latent des autoencodeurs
Transformations itératives	Couches récurrentes, modèles de diffusion
Autosimilarité spatiale	Weight sharing, convolutions
Recherche de patches similaires	Mécanismes d'attention (key-query matching)
Convergence vers attracteur	Convergence vers distribution apprise

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 :

Compression Fractale	Modèles de Diffusion
Décodage itératif via IFS	Débruitage itératif (reverse diffusion)
Convergence vers attracteur	Convergence vers distribution des données
Image initiale arbitraire → attracteur	Bruit pur → échantillon
Théorème de Banach garantit convergence	Schedule de variance garantit convergence

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