354
11 Compression d’images par fonctions it´ er´ ees
On montrera seulement (i), (ii) ´ etant analogue. Comme v ∈ T (B 1 ), on a v = T (v
) pour
un certain v
∈ B 1 . Soit w ∈ T (B 2 ). On a d(v, T (B 2 )) ≤ d(v, w). Soit w
∈ B 2 tel que
w = T (w
). Alors,
d(v, T (B 2 )) ≤ d(v, w) = d(T (v
), T (w
)) ≤ rd(v
, w
).
Puisque ceci est v´ erifi´ e pour tout w
∈ B 2 , on en tire
d(v, T (B 2 )) ≤ rd(v
, B 2 ) ≤ rd H (B 1 , B 2 ).
Preuve du th´ eor` eme 11.14. La preuve se fait par induction sur le nombre m de
transformations d´ efinissant l’op´ erateur W : nous montrerons que si T i est une contraction de facteur de contraction r i , i = 1, . . . , m, alors W est une contraction de facteur
de contraction r = max(r 1 , . . . , r m ). Le cas m = 1 est l’objet du lemme 11.16. Quoiqu’il
ne soit pas n´ ecessaire de traiter le cas m = 2, nous le faisons pour bien illustrer les
id´ ees avant le cas g´ en´ eral et pour mettre en ´ evidence le facteur de contraction de W . Si
m = 2, W (B) = T 1 (B) ∪ T 2 (B).
d H (W (B), W (C)) = d H (T 1 (B) ∪ T 2 (B), T 1 (C) ∪ T 2 (C))
≤ max(d H (T 1 (B), T 1 (C)), d H (T 2 (B), T 2 (C)))
≤ max(r 1 d H (B, C), r 2 d H (B, C))
= max(r 1 , r 2 )d H (B, C),
par application successive du lemme 11.15 et du lemme 11.16.
Supposons que le th´ eor` eme est d´ emontr´ e pour un syst` eme de m fonctions it´ er´ ees
et d´ emontrons-le pour un syst` eme de m + 1 fonctions it´ er´ ees : on a W (B) = T 1 (B) ∪
. . . T m+1 (B). Alors,
d H (W (B), W (C)) = d H (T 1 (B) ∪ · · · ∪ T m+1 (B), T 1 (C) ∪ · · · ∪ T m+1 (C))
= d H
m
i=1
T i (B)
∪ T m+1 (B),
m
i=1
T i (C)
∪ T m+1 (C)
≤ max
d H
m
i=1
T i (B),
m
i=1
T i (C)
, d H (T m+1 (B), T m+1 (C))
≤ max(max(r 1 , . . . , r m )d H (B, C), r m+1 d H (B, C))
≤ max(r 1 , . . . , r m+1 )d H (B, C),
en vertu des lemmes 11.15 et 11.16 et de l’hypoth` ese d’induction.
Le th´ eor` eme 11.14 nous assure que, quel que soit B ⊂ R
2 , la distance de Hausdorff
entre deux de ses it´ er´ ees cons´ ecutives W
n (B) et W
n+1 (B) d´ ecroˆ ıt `
a mesure que n
augmente puisque
11 Compression d’images par fonctions it´ er´ ees
On montrera seulement (i), (ii) ´ etant analogue. Comme v ∈ T (B 1 ), on a v = T (v
) pour
un certain v
∈ B 1 . Soit w ∈ T (B 2 ). On a d(v, T (B 2 )) ≤ d(v, w). Soit w
∈ B 2 tel que
w = T (w
). Alors,
d(v, T (B 2 )) ≤ d(v, w) = d(T (v
), T (w
)) ≤ rd(v
, w
).
Puisque ceci est v´ erifi´ e pour tout w
∈ B 2 , on en tire
d(v, T (B 2 )) ≤ rd(v
, B 2 ) ≤ rd H (B 1 , B 2 ).
Preuve du th´ eor` eme 11.14. La preuve se fait par induction sur le nombre m de
transformations d´ efinissant l’op´ erateur W : nous montrerons que si T i est une contraction de facteur de contraction r i , i = 1, . . . , m, alors W est une contraction de facteur
de contraction r = max(r 1 , . . . , r m ). Le cas m = 1 est l’objet du lemme 11.16. Quoiqu’il
ne soit pas n´ ecessaire de traiter le cas m = 2, nous le faisons pour bien illustrer les
id´ ees avant le cas g´ en´ eral et pour mettre en ´ evidence le facteur de contraction de W . Si
m = 2, W (B) = T 1 (B) ∪ T 2 (B).
d H (W (B), W (C)) = d H (T 1 (B) ∪ T 2 (B), T 1 (C) ∪ T 2 (C))
≤ max(d H (T 1 (B), T 1 (C)), d H (T 2 (B), T 2 (C)))
≤ max(r 1 d H (B, C), r 2 d H (B, C))
= max(r 1 , r 2 )d H (B, C),
par application successive du lemme 11.15 et du lemme 11.16.
Supposons que le th´ eor` eme est d´ emontr´ e pour un syst` eme de m fonctions it´ er´ ees
et d´ emontrons-le pour un syst` eme de m + 1 fonctions it´ er´ ees : on a W (B) = T 1 (B) ∪
. . . T m+1 (B). Alors,
d H (W (B), W (C)) = d H (T 1 (B) ∪ · · · ∪ T m+1 (B), T 1 (C) ∪ · · · ∪ T m+1 (C))
= d H
m
i=1
T i (B)
∪ T m+1 (B),
m
i=1
T i (C)
∪ T m+1 (C)
≤ max
d H
m
i=1
T i (B),
m
i=1
T i (C)
, d H (T m+1 (B), T m+1 (C))
≤ max(max(r 1 , . . . , r m )d H (B, C), r m+1 d H (B, C))
≤ max(r 1 , . . . , r m+1 )d H (B, C),
en vertu des lemmes 11.15 et 11.16 et de l’hypoth` ese d’induction.
Le th´ eor` eme 11.14 nous assure que, quel que soit B ⊂ R
2 , la distance de Hausdorff
entre deux de ses it´ er´ ees cons´ ecutives W
n (B) et W
n+1 (B) d´ ecroˆ ıt `
a mesure que n
augmente puisque