340
11 Compression d’images par fonctions it´ er´ ees
x 2 − x 1 y 2 − y 1
x 3 − x 1 y 3 − y 1
= (x 2 − x 1 )(y 3 − y 1 ) − (x 3 − x 1 )(y 2 − y 1 ).
D’autre part, le d´ eterminant d’une matrice ne change pas quand on ajoute ` a une ligne
un multiple d’une autre. Soustrayons donc la premi` ere ligne de A de la deuxi` eme ligne
et de la troisi` eme. On a
det A =
x 1
y 1
1
x 2 − x 1 y 2 − y 1 0
x 3 − x 1 y 3 − y 1 0
= (x 2 − x 1 )(y 3 − y 1 ) − (x 3 − x 1 )(y 2 − y 1 ).
On voit que det A = 0 pr´ ecis´ ement quand les trois points sont align´ es. Par contre, si
det A = 0, chacun des syst` emes (11.2) et (11.3) a une solution unique.
Remarque Dans la foug` ere, on doit utiliser la m´ ethode de la preuve du th´ eor` eme 11.2
pour trouver les quatre transformations affines. Pour cela, on doit se donner un syst` eme
d’axes dans lequel on mesure les coordonn´ ees des points P i et Q i . Dans beaucoup
d’exemples, on peut cependant deviner la formule de l’application affine sans avoir besoin de mesurer les coordonn´ ees des points P i et Q i et de r´ esoudre les syst` emes (11.2) et
(11.3). Pour cela, on utilise des compositions des applications affines simples suivantes.
Exemples d’applications affines simples
• Homoth´ etie de rapport r : T (x, y) = (rx, ry).
• Sym´ etrie par rapport `
a l’axe des x : T (x, y) = (x, −y).
• Sym´ etrie par rapport `
a l’axe des y : T (x, y) = (−x, y).
• Sym´ etrie par rapport `
a l’origine : T (x, y) = (−x, −y).
• Rotation d’angle θ : T (x, y) = (x cos θ − y sin θ, x sin θ + y cos θ). Pour trouver
cette formule, on utilise le fait qu’une rotation est une transformation lin´ eaire.
Les colonnes de sa matrice sont les coordonn´ ees des images des vecteurs de la base
e 1 = (1, 0) et e 2 = (0, 1) (figure 11.3). La matrice de la transformation est alors
cos θ − sin θ
sin θ
cos θ
.
• Projection sur l’axe des x : T (x, y) = (x, 0).
• Projection sur l’axe des y : T (x, y) = (0, y).
• Translation par un vecteur (e, f ) : T (x, y) = (x + e, y + f ).
11.3 Les syst` emes de fonctions it´ er´ ees
Les fractales que nous construisons ` a l’aide de la m´ ethode d´ ecrite sont des attracteurs
de syst` emes de fonctions it´ er´ ees. Nous allons d´ efinir ces termes.
11 Compression d’images par fonctions it´ er´ ees
x 2 − x 1 y 2 − y 1
x 3 − x 1 y 3 − y 1
= (x 2 − x 1 )(y 3 − y 1 ) − (x 3 − x 1 )(y 2 − y 1 ).
D’autre part, le d´ eterminant d’une matrice ne change pas quand on ajoute ` a une ligne
un multiple d’une autre. Soustrayons donc la premi` ere ligne de A de la deuxi` eme ligne
et de la troisi` eme. On a
det A =
x 1
y 1
1
x 2 − x 1 y 2 − y 1 0
x 3 − x 1 y 3 − y 1 0
= (x 2 − x 1 )(y 3 − y 1 ) − (x 3 − x 1 )(y 2 − y 1 ).
On voit que det A = 0 pr´ ecis´ ement quand les trois points sont align´ es. Par contre, si
det A = 0, chacun des syst` emes (11.2) et (11.3) a une solution unique.
Remarque Dans la foug` ere, on doit utiliser la m´ ethode de la preuve du th´ eor` eme 11.2
pour trouver les quatre transformations affines. Pour cela, on doit se donner un syst` eme
d’axes dans lequel on mesure les coordonn´ ees des points P i et Q i . Dans beaucoup
d’exemples, on peut cependant deviner la formule de l’application affine sans avoir besoin de mesurer les coordonn´ ees des points P i et Q i et de r´ esoudre les syst` emes (11.2) et
(11.3). Pour cela, on utilise des compositions des applications affines simples suivantes.
Exemples d’applications affines simples
• Homoth´ etie de rapport r : T (x, y) = (rx, ry).
• Sym´ etrie par rapport `
a l’axe des x : T (x, y) = (x, −y).
• Sym´ etrie par rapport `
a l’axe des y : T (x, y) = (−x, y).
• Sym´ etrie par rapport `
a l’origine : T (x, y) = (−x, −y).
• Rotation d’angle θ : T (x, y) = (x cos θ − y sin θ, x sin θ + y cos θ). Pour trouver
cette formule, on utilise le fait qu’une rotation est une transformation lin´ eaire.
Les colonnes de sa matrice sont les coordonn´ ees des images des vecteurs de la base
e 1 = (1, 0) et e 2 = (0, 1) (figure 11.3). La matrice de la transformation est alors
cos θ − sin θ
sin θ
cos θ
.
• Projection sur l’axe des x : T (x, y) = (x, 0).
• Projection sur l’axe des y : T (x, y) = (0, y).
• Translation par un vecteur (e, f ) : T (x, y) = (x + e, y + f ).
11.3 Les syst` emes de fonctions it´ er´ ees
Les fractales que nous construisons ` a l’aide de la m´ ethode d´ ecrite sont des attracteurs
de syst` emes de fonctions it´ er´ ees. Nous allons d´ efinir ces termes.