11.7 Une photographie comme attracteur
367
sur l’ensemble des photographies. Cette m´ ethode de compression a remplac´ e l’alphabet
d’objets g´ eom´ etriques que nous avions utilis´ e dans l’´ etude des fractales par un alphabet
de patrons de tons de gris, plus sp´ ecifiquement les patrons des grands carr´ es 8 × 8 de la
photographie `
a comprimer.
La reconstruction de l’image La photographie peut ˆ etre reconstitu´ ee de la mani` ere
suivante.
• On choisit arbitrairement une fonction f
0
∈ F. Un choix naturel est la fonction
f
0 (x, y) = 128 pour tout x et y, c’est-` a-dire la fonction « ton de gris uniforme »
qui associe ` a chaque pixel le mˆ eme gris.
• On calcule les it´ er´ ees f
j = W (f
j−1 ), c’est-` a-dire qu’ on remplace la fonction f
j−1
sur chaque petit carr´ e C i par la transformation par T i de l’image de f
j−1 sur
le grand carr´ e G i associ´ e. (Si on veut mesurer la qualit´ e de la pr´ ecision obtenue
apr` es le calcul de chaque f
j , on calcule la distance globale d h×v (f
j , f
j−1 ). Si cette
distance est inf´ erieure ` a un certain seuil, on arrˆ ete le processus d’it´ eration.)
• Pour la derni` ere it´ er´ ee obtenue, on arrondit le ton de gris de chacun des pixels ` a
l’entier le plus proche. Si l’entier est n´ egatif, on le remplace par 0 ; s’il est sup´ erieur
` a 255, on le remplace par 255.
Comme nous le verrons dans l’exemple qui suit, les it´ er´ ees f
1 et f
2 donnent d´ ej` a de
bonnes approximations de la photographie `
a reproduire, et la distance entre f
5 et f
6
est tr` es petite ou, en d’autres mots, f
5 est visuellement une excellente approximation
de l’attracteur (et, on l’esp` ere, de la photographie initiale).
Remarque Les T i , transformations affines sur R
3 , ne sont pas toutes des contractions ;
en fait, T i n’est jamais une contraction si s i > 1 ! Mais la plupart des T i sont des
contractions parce qu’il est naturel d’avoir plus de contraste sur les grands carr´ es que
sur les petits. `
A notre connaissance, il n’y a pas de th´ eor` eme garantissant la convergence
de l’algorithme pour toutes les images. Cependant, en pratique, on observe g´ en´ eralement
la convergence, comme si le syst` eme {T i } i∈I ´ etait une application contractante. Benoˆ ıt
Mandelbrot a ´ elabor´ e une nouvelle g´ eom´ etrie, la g´ eom´ etrie fractale, pour d´ ecrire les
formes de la nature, la g´ eom´ etrie traditionnelle n’´ etant pas assez riche pour cela. Outre
les formes des v´ eg´ etaux comme la foug` ere, on peut penser au contour des cˆ otes rocheuses,
` a certains types de montagnes, aux r´ eseaux hydrographiques, au r´ eseau de capillaires
du corps humain, etc. La m´ ethode de compression d’images par syst` eme de fonctions
it´ er´ ees partitionn´ e est adapt´ ee ` a des photographies ayant un caract` ere fractal, c’est-` adire poss´ edant des patrons tr` es similaires ` a diverses ´ echelles ; pour de telles photos, on
peut s’attendre non seulement `
a la convergence de l’algorithme, mais `
a une reproduction
fid` ele. Mais voyons enfin un exemple !
Exemple 11.26 Apr` es avoir lu la mise en garde ci-dessus, on peut se demander si
cette m´ ethode de compression a une chance de reproduire correctement une photographie.
L’exemple qui suit rassurera les lecteurs. Nous utiliserons la mˆ eme photographie qu’au
chapitre 12 consacr´ e au standard de compression JPEG, celle de la figure 12.1 de la
367
sur l’ensemble des photographies. Cette m´ ethode de compression a remplac´ e l’alphabet
d’objets g´ eom´ etriques que nous avions utilis´ e dans l’´ etude des fractales par un alphabet
de patrons de tons de gris, plus sp´ ecifiquement les patrons des grands carr´ es 8 × 8 de la
photographie `
a comprimer.
La reconstruction de l’image La photographie peut ˆ etre reconstitu´ ee de la mani` ere
suivante.
• On choisit arbitrairement une fonction f
0
∈ F. Un choix naturel est la fonction
f
0 (x, y) = 128 pour tout x et y, c’est-` a-dire la fonction « ton de gris uniforme »
qui associe ` a chaque pixel le mˆ eme gris.
• On calcule les it´ er´ ees f
j = W (f
j−1 ), c’est-` a-dire qu’ on remplace la fonction f
j−1
sur chaque petit carr´ e C i par la transformation par T i de l’image de f
j−1 sur
le grand carr´ e G i associ´ e. (Si on veut mesurer la qualit´ e de la pr´ ecision obtenue
apr` es le calcul de chaque f
j , on calcule la distance globale d h×v (f
j , f
j−1 ). Si cette
distance est inf´ erieure ` a un certain seuil, on arrˆ ete le processus d’it´ eration.)
• Pour la derni` ere it´ er´ ee obtenue, on arrondit le ton de gris de chacun des pixels ` a
l’entier le plus proche. Si l’entier est n´ egatif, on le remplace par 0 ; s’il est sup´ erieur
` a 255, on le remplace par 255.
Comme nous le verrons dans l’exemple qui suit, les it´ er´ ees f
1 et f
2 donnent d´ ej` a de
bonnes approximations de la photographie `
a reproduire, et la distance entre f
5 et f
6
est tr` es petite ou, en d’autres mots, f
5 est visuellement une excellente approximation
de l’attracteur (et, on l’esp` ere, de la photographie initiale).
Remarque Les T i , transformations affines sur R
3 , ne sont pas toutes des contractions ;
en fait, T i n’est jamais une contraction si s i > 1 ! Mais la plupart des T i sont des
contractions parce qu’il est naturel d’avoir plus de contraste sur les grands carr´ es que
sur les petits. `
A notre connaissance, il n’y a pas de th´ eor` eme garantissant la convergence
de l’algorithme pour toutes les images. Cependant, en pratique, on observe g´ en´ eralement
la convergence, comme si le syst` eme {T i } i∈I ´ etait une application contractante. Benoˆ ıt
Mandelbrot a ´ elabor´ e une nouvelle g´ eom´ etrie, la g´ eom´ etrie fractale, pour d´ ecrire les
formes de la nature, la g´ eom´ etrie traditionnelle n’´ etant pas assez riche pour cela. Outre
les formes des v´ eg´ etaux comme la foug` ere, on peut penser au contour des cˆ otes rocheuses,
` a certains types de montagnes, aux r´ eseaux hydrographiques, au r´ eseau de capillaires
du corps humain, etc. La m´ ethode de compression d’images par syst` eme de fonctions
it´ er´ ees partitionn´ e est adapt´ ee ` a des photographies ayant un caract` ere fractal, c’est-` adire poss´ edant des patrons tr` es similaires ` a diverses ´ echelles ; pour de telles photos, on
peut s’attendre non seulement `
a la convergence de l’algorithme, mais `
a une reproduction
fid` ele. Mais voyons enfin un exemple !
Exemple 11.26 Apr` es avoir lu la mise en garde ci-dessus, on peut se demander si
cette m´ ethode de compression a une chance de reproduire correctement une photographie.
L’exemple qui suit rassurera les lecteurs. Nous utiliserons la mˆ eme photographie qu’au
chapitre 12 consacr´ e au standard de compression JPEG, celle de la figure 12.1 de la