346
11 Compression d’images par fonctions it´ er´ ees
On pourrait prendre comme ensemble B 0 un seul point du carr´ e C 0 . Alors, l’ensemble
B n serait form´ e de 3
n points. Si, pour chaque point de l’ensemble B n , on noircissait le
pixel correspondant, alors B n , pour n assez grand, ressemblerait au triangle de Sierpi´ nski
A.
En fait, les programmes traditionnels exploitent une variante de cette id´ ee, car il
est plus simple de tracer un point `
a la fois que de dessiner 3
n sous-ensembles du plan.
On choisit un point P 0 du rectangle R. `
A chaque ´ etape, on choisit au hasard une des
transformations T 1 , . . . , T m , soit T in , et on calcule P n = T in (P n−1 ). Si le point P 0 est d´ ej` a
dans A, alors on trace l’ensemble des points de la suite {P n } n≥0 : cet ensemble ressemble
fortement `
a A. Si on ne sait pas si P 0 est dans A, alors on rejette les M premiers points
g´ en´ er´ es P 0 , . . . , P M−1 et on trace ensuite les points de la suite {P n } n≥M . La section
suivante montrera qu’il existe toujours un M menant `
a une bonne approximation de A.
En pratique, M peut souvent ˆ etre aussi petit que 10, car la convergence vers l’attracteur
est rapide.
Par exemple, pour tracer le triangle de Sierpi´ nski (figure 11.5), on a choisi al´ eatoirement, ` a chaque ´ etape du dessin, une transformation parmi {T 1 , T 2 , T 3 }. Ceci revient ` a
choisir al´ eatoirement, ` a l’´ etape n, un nombre i n ∈ {1, 2, 3} et ` a appliquer T in . Ainsi,
chaque fois qu’on g´ en` ere 1 (respectivement 2, 3) on applique T 1 (respectivement T 2 , T 3 ).
Pour la foug` ere, cette m´ ethode ne serait pas tr` es ´ economique : on tracerait beaucoup trop
de points sur la tige et dans les petites foug` eres et pas assez dans la grande foug` ere. Soit
T 1 (respectivement T 2 , T 3 , T 4 ) la contraction affine qui envoie la foug` ere originale sur la
grande foug` ere (respectivement sur la foug` ere de gauche, la foug` ere de droite, la tige).
On veut que 1 soit choisi avec une probabilit´ e de 85 %, 2 et 3 avec une probabilit´ e de 7 %
et 4 avec une probabilit´ e de 1 %. Pour cela, on g´ en` ere de fa¸ con al´ eatoire des nombres
¯
a n ∈ {1, . . . , 100}. On applique T 1 (c’est-` a-dire i n = 1) si le nombre g´ en´ er´ e ¯
a n appartient
` a {1, . . . , 85}. De mˆ eme, on applique T 2 (c’est-` a-dire i n = 2) si ¯
a n ∈ {86, . . . , 92}, T 3 si
¯
a n ∈ {93, . . . , 99}, T 4 si ¯
a n = 100.
Programme Mathematica utilis´ e pour tracer la foug` ere de la figure 11.2 (Les
coefficients des T i proviennent de [1].)
choixT := (r = RandomInteger[{1, 100}];
If[r <= 85, 1,
If[r <= 92, 2,
If[r <= 99, 3, 4]]])
t = { (* { transformation lineaire, translation } *)
{{{0.85, 0.04}, {-0.04, 0.85}}, {0., 1.6}},
{{{0.2, -0.26}, {0.23, 0.22}}, {0., 1.6}},
{{{-0.15, 0.28}, {0.26, 0.24}}, {0., 0.44}},
{{{0., 0.}, {0., 0.16}}, {0., 0.}}
};
transfoAff[t_, pt_] := t[[1]].pt + t[[2]]
11 Compression d’images par fonctions it´ er´ ees
On pourrait prendre comme ensemble B 0 un seul point du carr´ e C 0 . Alors, l’ensemble
B n serait form´ e de 3
n points. Si, pour chaque point de l’ensemble B n , on noircissait le
pixel correspondant, alors B n , pour n assez grand, ressemblerait au triangle de Sierpi´ nski
A.
En fait, les programmes traditionnels exploitent une variante de cette id´ ee, car il
est plus simple de tracer un point `
a la fois que de dessiner 3
n sous-ensembles du plan.
On choisit un point P 0 du rectangle R. `
A chaque ´ etape, on choisit au hasard une des
transformations T 1 , . . . , T m , soit T in , et on calcule P n = T in (P n−1 ). Si le point P 0 est d´ ej` a
dans A, alors on trace l’ensemble des points de la suite {P n } n≥0 : cet ensemble ressemble
fortement `
a A. Si on ne sait pas si P 0 est dans A, alors on rejette les M premiers points
g´ en´ er´ es P 0 , . . . , P M−1 et on trace ensuite les points de la suite {P n } n≥M . La section
suivante montrera qu’il existe toujours un M menant `
a une bonne approximation de A.
En pratique, M peut souvent ˆ etre aussi petit que 10, car la convergence vers l’attracteur
est rapide.
Par exemple, pour tracer le triangle de Sierpi´ nski (figure 11.5), on a choisi al´ eatoirement, ` a chaque ´ etape du dessin, une transformation parmi {T 1 , T 2 , T 3 }. Ceci revient ` a
choisir al´ eatoirement, ` a l’´ etape n, un nombre i n ∈ {1, 2, 3} et ` a appliquer T in . Ainsi,
chaque fois qu’on g´ en` ere 1 (respectivement 2, 3) on applique T 1 (respectivement T 2 , T 3 ).
Pour la foug` ere, cette m´ ethode ne serait pas tr` es ´ economique : on tracerait beaucoup trop
de points sur la tige et dans les petites foug` eres et pas assez dans la grande foug` ere. Soit
T 1 (respectivement T 2 , T 3 , T 4 ) la contraction affine qui envoie la foug` ere originale sur la
grande foug` ere (respectivement sur la foug` ere de gauche, la foug` ere de droite, la tige).
On veut que 1 soit choisi avec une probabilit´ e de 85 %, 2 et 3 avec une probabilit´ e de 7 %
et 4 avec une probabilit´ e de 1 %. Pour cela, on g´ en` ere de fa¸ con al´ eatoire des nombres
¯
a n ∈ {1, . . . , 100}. On applique T 1 (c’est-` a-dire i n = 1) si le nombre g´ en´ er´ e ¯
a n appartient
` a {1, . . . , 85}. De mˆ eme, on applique T 2 (c’est-` a-dire i n = 2) si ¯
a n ∈ {86, . . . , 92}, T 3 si
¯
a n ∈ {93, . . . , 99}, T 4 si ¯
a n = 100.
Programme Mathematica utilis´ e pour tracer la foug` ere de la figure 11.2 (Les
coefficients des T i proviennent de [1].)
choixT := (r = RandomInteger[{1, 100}];
If[r <= 85, 1,
If[r <= 92, 2,
If[r <= 99, 3, 4]]])
t = { (* { transformation lineaire, translation } *)
{{{0.85, 0.04}, {-0.04, 0.85}}, {0., 1.6}},
{{{0.2, -0.26}, {0.23, 0.22}}, {0., 1.6}},
{{{-0.15, 0.28}, {0.26, 0.24}}, {0., 0.44}},
{{{0., 0.}, {0., 0.16}}, {0., 0.}}
};
transfoAff[t_, pt_] := t[[1]].pt + t[[2]]