360
11 Compression d’images par fonctions it´ er´ ees
D ln r = ln 1/m = − ln m.
D’o` u le r´ esultat.
Pour la premi` ere partie de la preuve, nous serons plus intuitifs. Soient A notre
attracteur et N () le nombre minimum de carr´ es de cˆ ot´ e n´ ecessaires pour le couvrir.
Puisque A est la r´ eunion disjointe de T 1 (A), . . ., T m (A), N () est ` a peu pr` es ´ egal `
a
N 1 () + · · · + N m () o` u N i () est le nombre de carr´ es de cˆ ot´ e n´ ecessaires pour couvrir
T i (A). Cette approximation est d’autant meilleure que est petit. Maintenant T i (A)
est obtenu de A par application d’une contraction de facteur de contraction exact r i
(c’est-` a-dire que T i est la composition d’une homoth´ etie de rapport r i et d’une isom´ etrie
pr´ eservant les distances et les angles). Donc, si on a besoin de N i () carr´ es de cˆ ot´ e
pour recouvrir T i (A), l’application de T
−1
i
` a ces carr´ es nous donne N i () carr´ es de cˆ ot´ e
/r i qui recouvrent A. Donc,
N (/r i ) ≈ N i ().
On a donc
N () ≈ N (/r 1 ) + · · · + N (/r m ).
(11.15)
Sous cette forme, il est difficile de calculer la limite lim →0 N (). Nous allons donc
supposer que N () ≈ CC
−D o` u D est la dimension cherch´ ee (ici nous sommes seulement
intuitifs !) ; ceci serait le cas pour les segments, carr´ es et cubes consid´ er´ es dans nos
exemples simples. Selon cette hypoth` ese, l’´ equation (11.15) nous donne
CC
−D = C
r 1
−D
+ · · · + C
r m
−D
.
On peut simplifier CC
−D , ce qui nous laisse
1 =
1
r
−D
1
+ · · · +
1
r
−D
m
= r
D
1 + · · · + r
D
m .
Exemple 11.24 Pour le triangle de Sierpi´ nski, on a r = 1/2 et m = 3. En vertu du
th´ eor` eme, sa dimension est
ln 3
ln 2 ≈ 1,58496, ce qui correspond au r´ esultat obtenu par
comptage de carr´ es ` a l’exemple 11.22.
Calcul de la dimension D(A) ` a l’aide de (11.13) quand les r i ne sont pas tous
´ egaux et sous la condition (11.12). Mˆ eme si ce n’est pas facile de donner une preuve
rigoureuse, on peut se convaincre en analysant les exemples que la condition (11.12)
se v´ erifie souvent dans les syst` emes de fonctions it´ er´ ees totalement d´ econnect´ es. On ne
peut trouver la solution exacte, mais on peut chercher une solution num´ erique. En effet,
on sait que la dimension D(A) ∈ [0, 2]. La fonction
f (D) = r
D
1 + · · · + r
D
m − 1
11 Compression d’images par fonctions it´ er´ ees
D ln r = ln 1/m = − ln m.
D’o` u le r´ esultat.
Pour la premi` ere partie de la preuve, nous serons plus intuitifs. Soient A notre
attracteur et N () le nombre minimum de carr´ es de cˆ ot´ e n´ ecessaires pour le couvrir.
Puisque A est la r´ eunion disjointe de T 1 (A), . . ., T m (A), N () est ` a peu pr` es ´ egal `
a
N 1 () + · · · + N m () o` u N i () est le nombre de carr´ es de cˆ ot´ e n´ ecessaires pour couvrir
T i (A). Cette approximation est d’autant meilleure que est petit. Maintenant T i (A)
est obtenu de A par application d’une contraction de facteur de contraction exact r i
(c’est-` a-dire que T i est la composition d’une homoth´ etie de rapport r i et d’une isom´ etrie
pr´ eservant les distances et les angles). Donc, si on a besoin de N i () carr´ es de cˆ ot´ e
pour recouvrir T i (A), l’application de T
−1
i
` a ces carr´ es nous donne N i () carr´ es de cˆ ot´ e
/r i qui recouvrent A. Donc,
N (/r i ) ≈ N i ().
On a donc
N () ≈ N (/r 1 ) + · · · + N (/r m ).
(11.15)
Sous cette forme, il est difficile de calculer la limite lim →0 N (). Nous allons donc
supposer que N () ≈ CC
−D o` u D est la dimension cherch´ ee (ici nous sommes seulement
intuitifs !) ; ceci serait le cas pour les segments, carr´ es et cubes consid´ er´ es dans nos
exemples simples. Selon cette hypoth` ese, l’´ equation (11.15) nous donne
CC
−D = C
r 1
−D
+ · · · + C
r m
−D
.
On peut simplifier CC
−D , ce qui nous laisse
1 =
1
r
−D
1
+ · · · +
1
r
−D
m
= r
D
1 + · · · + r
D
m .
Exemple 11.24 Pour le triangle de Sierpi´ nski, on a r = 1/2 et m = 3. En vertu du
th´ eor` eme, sa dimension est
ln 3
ln 2 ≈ 1,58496, ce qui correspond au r´ esultat obtenu par
comptage de carr´ es ` a l’exemple 11.22.
Calcul de la dimension D(A) ` a l’aide de (11.13) quand les r i ne sont pas tous
´ egaux et sous la condition (11.12). Mˆ eme si ce n’est pas facile de donner une preuve
rigoureuse, on peut se convaincre en analysant les exemples que la condition (11.12)
se v´ erifie souvent dans les syst` emes de fonctions it´ er´ ees totalement d´ econnect´ es. On ne
peut trouver la solution exacte, mais on peut chercher une solution num´ erique. En effet,
on sait que la dimension D(A) ∈ [0, 2]. La fonction
f (D) = r
D
1 + · · · + r
D
m − 1