11.5 La distance de Hausdorff
355
d H (W
n (B), W
n+1 (B)) ≤ rd H (W
n−1 (B), W
n (B)) ≤ · · · ≤ r
n d H (B, W (B)),
o` u r ∈ (0, 1). Il ne permet cependant pas de borner la distance entre B et l’attracteur
A. C’est ce que fait le prochain th´ eor` eme, appel´ e th´ eor` eme du collage par Barnsley.
Th´ eor` eme 11.17 (th´ eor` eme du collage de Barnsley [1]) Soit le syst` eme de fonctions it´ er´ ees {T 1 , . . . , T m } de facteur de contraction r ∈ (0, 1) et d’attracteur A. Soient
B et > 0 tels que
d H (B, T 1 (B) ∪ · · · ∪ T m (B)) ≤ .
Alors,
d H (B, A) ≤
1 − r
.
(11.11)
Preuve Nous copions un argument de la preuve du th´ eor` eme 11.6 pour borner la
distance d H (B, W
n (B)). Puisqu’une distance satisfait `
a l’in´ egalit´ e du triangle (propri´ et´ e
(iv)), on a
d H (B, W
n (B)) ≤ d H (B, W (B)) + d H (W (B), W
2 (B)) + · · · + d H (W
n−1 (B), W
n (B))
≤ (1 + r
1 + . . . r
n−1 )d H (B, W (B))
≤
1−r
n
1−r d H (B, W (B))
≤
1
1−r d H (B, W (B)) ≤
1−r .
Prenons η > 0 arbitraire. Il existe N tel que, si n > N, alors d H (W
n (B), A) < η. Alors,
si n > N, on a
d H (B, A) ≤ d H (B, W
n (B)) + d H (W
n (B), A) <
1 − r
+ η.
Comme cette in´ egalit´ e vaut pour tout η > 0, on en conclut que d H (B, A) ≤
1−r .
Le th´ eor` eme du collage est extrˆ emement important pour les applications pratiques.
En effet, supposons qu’au lieu de la foug` ere « math´ ematique » de la figure 11.2, on
ait la photographie d’une vraie foug` ere que nous appellerons B ; il est possible que
les transformations affines T 1 , . . . , T 4 telles que B = T 1 (B) ∪ T 2 (B) ∪ T 3 (B) ∪ T 4 (B)
n’existent pas et que B ne soit qu’approximativement ´ egal `
a
C = T 1 (B) ∪ T 2 (B) ∪ T 3 (B) ∪ T 4 (B)
pour des transformations affines T 1 , . . . , T 4 . Si on fait construire par l’ordinateur l’attracteur A du syst` eme de fonctions it´ er´ ees {T 1 , . . . , T 4 } et si d H (B, C) ≤ , le th´ eor` eme
du collage assure que d H (A, B) ≤
1−r , c’est-` a-dire que A ressemble ` a B. Notre m´ ethode
est donc « robuste » : elle r´ esiste aux approximations des images.
355
d H (W
n (B), W
n+1 (B)) ≤ rd H (W
n−1 (B), W
n (B)) ≤ · · · ≤ r
n d H (B, W (B)),
o` u r ∈ (0, 1). Il ne permet cependant pas de borner la distance entre B et l’attracteur
A. C’est ce que fait le prochain th´ eor` eme, appel´ e th´ eor` eme du collage par Barnsley.
Th´ eor` eme 11.17 (th´ eor` eme du collage de Barnsley [1]) Soit le syst` eme de fonctions it´ er´ ees {T 1 , . . . , T m } de facteur de contraction r ∈ (0, 1) et d’attracteur A. Soient
B et > 0 tels que
d H (B, T 1 (B) ∪ · · · ∪ T m (B)) ≤ .
Alors,
d H (B, A) ≤
1 − r
.
(11.11)
Preuve Nous copions un argument de la preuve du th´ eor` eme 11.6 pour borner la
distance d H (B, W
n (B)). Puisqu’une distance satisfait `
a l’in´ egalit´ e du triangle (propri´ et´ e
(iv)), on a
d H (B, W
n (B)) ≤ d H (B, W (B)) + d H (W (B), W
2 (B)) + · · · + d H (W
n−1 (B), W
n (B))
≤ (1 + r
1 + . . . r
n−1 )d H (B, W (B))
≤
1−r
n
1−r d H (B, W (B))
≤
1
1−r d H (B, W (B)) ≤
1−r .
Prenons η > 0 arbitraire. Il existe N tel que, si n > N, alors d H (W
n (B), A) < η. Alors,
si n > N, on a
d H (B, A) ≤ d H (B, W
n (B)) + d H (W
n (B), A) <
1 − r
+ η.
Comme cette in´ egalit´ e vaut pour tout η > 0, on en conclut que d H (B, A) ≤
1−r .
Le th´ eor` eme du collage est extrˆ emement important pour les applications pratiques.
En effet, supposons qu’au lieu de la foug` ere « math´ ematique » de la figure 11.2, on
ait la photographie d’une vraie foug` ere que nous appellerons B ; il est possible que
les transformations affines T 1 , . . . , T 4 telles que B = T 1 (B) ∪ T 2 (B) ∪ T 3 (B) ∪ T 4 (B)
n’existent pas et que B ne soit qu’approximativement ´ egal `
a
C = T 1 (B) ∪ T 2 (B) ∪ T 3 (B) ∪ T 4 (B)
pour des transformations affines T 1 , . . . , T 4 . Si on fait construire par l’ordinateur l’attracteur A du syst` eme de fonctions it´ er´ ees {T 1 , . . . , T 4 } et si d H (B, C) ≤ , le th´ eor` eme
du collage assure que d H (A, B) ≤
1−r , c’est-` a-dire que A ressemble ` a B. Notre m´ ethode
est donc « robuste » : elle r´ esiste aux approximations des images.