11.7 Une photographie comme attracteur
365
C’est en choisissant soigneusement s i et g i qu’on aura de tr` es grandes chances d’obtenir un syst` eme de fonctions it´ er´ ees partitionn´ e contractant par rapport `
a cette distance.
Soit C i un petit carr´ e. Voici comment sont choisis le grand carr´ e G i et la transformation
T i associ´ es ` a C i . Pour un C i fix´ e, nous r´ ep´ etons les ´ etapes suivantes pour chacun des
grands carr´ es G j et chacune des transformations lin´ eaires L ci-dessus :
• transformation de la restriction f Gj de f au grand carr´ e G j en une fonction ˆ
f Gj
obtenue en faisant la moyenne des tons de gris sur les petits blocs 2 × 2 de G j ;
• application d’une transformation affine T ` a cette fonction (l’image obtenue est celle
qui est associ´ ee ` a T (G j ) d´ efini plus haut) : nous l’appellerons f Ci . Lors de cette
transformation, la transformation du point (x, y) est compl` etement d´ etermin´ ee,
mais la transformation affine du ton de gris d´ etermin´ ee par la paire (s i , g i ) demeure
` a fixer ;
• choix des s i et g i qui minimisent la distance d 4 d´ efinie en (11.18) ;
• calcul de la distance pour ces s i et g i optimaux.
Une fois ces op´ erations effectu´ ees pour tous les grands carr´ es G j et les huit transformations lin´ eaires L ci-dessus, nous choisissons le grand carr´ e G i et la transformation affine
T i qui produisent la plus petite distance parmi celles qui ont calcul´ ees ` a la derni` ere
´ etape. Cette transformation fera partie du syst` eme de fonctions it´ er´ ees partitionn´ e. Il
faut effectuer les ´ etapes ci-dessus pour tous les autres petits carr´ es C i . Si la photographie
contient h × v pixels, il y a h × v/16 petits carr´ es. Pour chacun, le nombre de grands
carr´ es ` a consid´ erer est ´ enorme ! Pour sp´ ecifier un grand carr´ e, il suffit de sp´ ecifier son
pixel sup´ erieur gauche. Il y a (h − 7) × (v − 7) grands carr´ es possibles si on accepte
n’importe quel pixel sup´ erieur gauche. Comme ce nombre est trop grand, nous nous
limitons aux grands carr´ es dont le pixel sup´ erieur gauche a comme coordonn´ ees des
multiples de 8 ; ces grands carr´ es forment une partition de la photographie et sont au
nombre de h × v/64. C’est dans cet alphabet de carr´ es munis de patrons de tons de gris
que nous devons choisir pour approximer le mieux possible chacun des h × v/16 petits
carr´ es C i . Si h × v = 640 × 640, il faut calculer (
1
64 h × v) × 8 × (
1
16 h × v) ≈ 1,3 × 10
9
paires (s i , g i ). C’est beaucoup ! Il y a certes des fa¸ cons de r´ eduire le nombre de paires `
a
consid´ erer, mais malgr´ e ces am´ eliorations, c’est `
a la compression que cette m´ ethode est
coˆ uteuse.
M´ ethode des moindres carr´ es C’est la m´ ethode employ´ ee dans l’avant-derni` ere
´ etape ci-dessus, soit la recherche des s i et g i optimaux. Il est probable que vous l’ayez
vue dans un cours de calcul `
a plusieurs variables, d’alg` ebre lin´ eaire ou de statistique.
On doit minimiser
d 4 (f Ci , f Ci ) =
x∈Hi
y∈Vi
f Ci (x, y) − f Ci (x, y)
2 .
(11.19)
Minimiser d 4 ´ equivaut ` a minimiser son carr´ e d
2
4 , ce qui nous d´ ebarrasse de la racine
carr´ ee. Pour cela, on doit donner la formule de f Ci en fonction de s i et g i . Voyons
comment nous obtenons f Ci :
365
C’est en choisissant soigneusement s i et g i qu’on aura de tr` es grandes chances d’obtenir un syst` eme de fonctions it´ er´ ees partitionn´ e contractant par rapport `
a cette distance.
Soit C i un petit carr´ e. Voici comment sont choisis le grand carr´ e G i et la transformation
T i associ´ es ` a C i . Pour un C i fix´ e, nous r´ ep´ etons les ´ etapes suivantes pour chacun des
grands carr´ es G j et chacune des transformations lin´ eaires L ci-dessus :
• transformation de la restriction f Gj de f au grand carr´ e G j en une fonction ˆ
f Gj
obtenue en faisant la moyenne des tons de gris sur les petits blocs 2 × 2 de G j ;
• application d’une transformation affine T ` a cette fonction (l’image obtenue est celle
qui est associ´ ee ` a T (G j ) d´ efini plus haut) : nous l’appellerons f Ci . Lors de cette
transformation, la transformation du point (x, y) est compl` etement d´ etermin´ ee,
mais la transformation affine du ton de gris d´ etermin´ ee par la paire (s i , g i ) demeure
` a fixer ;
• choix des s i et g i qui minimisent la distance d 4 d´ efinie en (11.18) ;
• calcul de la distance pour ces s i et g i optimaux.
Une fois ces op´ erations effectu´ ees pour tous les grands carr´ es G j et les huit transformations lin´ eaires L ci-dessus, nous choisissons le grand carr´ e G i et la transformation affine
T i qui produisent la plus petite distance parmi celles qui ont calcul´ ees ` a la derni` ere
´ etape. Cette transformation fera partie du syst` eme de fonctions it´ er´ ees partitionn´ e. Il
faut effectuer les ´ etapes ci-dessus pour tous les autres petits carr´ es C i . Si la photographie
contient h × v pixels, il y a h × v/16 petits carr´ es. Pour chacun, le nombre de grands
carr´ es ` a consid´ erer est ´ enorme ! Pour sp´ ecifier un grand carr´ e, il suffit de sp´ ecifier son
pixel sup´ erieur gauche. Il y a (h − 7) × (v − 7) grands carr´ es possibles si on accepte
n’importe quel pixel sup´ erieur gauche. Comme ce nombre est trop grand, nous nous
limitons aux grands carr´ es dont le pixel sup´ erieur gauche a comme coordonn´ ees des
multiples de 8 ; ces grands carr´ es forment une partition de la photographie et sont au
nombre de h × v/64. C’est dans cet alphabet de carr´ es munis de patrons de tons de gris
que nous devons choisir pour approximer le mieux possible chacun des h × v/16 petits
carr´ es C i . Si h × v = 640 × 640, il faut calculer (
1
64 h × v) × 8 × (
1
16 h × v) ≈ 1,3 × 10
9
paires (s i , g i ). C’est beaucoup ! Il y a certes des fa¸ cons de r´ eduire le nombre de paires `
a
consid´ erer, mais malgr´ e ces am´ eliorations, c’est `
a la compression que cette m´ ethode est
coˆ uteuse.
M´ ethode des moindres carr´ es C’est la m´ ethode employ´ ee dans l’avant-derni` ere
´ etape ci-dessus, soit la recherche des s i et g i optimaux. Il est probable que vous l’ayez
vue dans un cours de calcul `
a plusieurs variables, d’alg` ebre lin´ eaire ou de statistique.
On doit minimiser
d 4 (f Ci , f Ci ) =
x∈Hi
y∈Vi
f Ci (x, y) − f Ci (x, y)
2 .
(11.19)
Minimiser d 4 ´ equivaut ` a minimiser son carr´ e d
2
4 , ce qui nous d´ ebarrasse de la racine
carr´ ee. Pour cela, on doit donner la formule de f Ci en fonction de s i et g i . Voyons
comment nous obtenons f Ci :