362
11 Compression d’images par fonctions it´ er´ ees
parties de la photographie appartiendront `
a un tel patron fractal ? Il est fort probable
que non ! Mˆ eme si un humain r´ eussit ` a rapprocher chaque partie d’une photographie
donn´ ee d’un mod` ele fractal, et, ainsi, ` a reconstruire une image ressemblant ` a la photographie initiale (il y a de jolis exemples dans [1]), ceci n’est pas la mˆ eme chose que de
programmer un ordinateur pour le faire de mani` ere syst´ ematique sur des centaines de
photographies. Il faut transformer et g´ en´ eraliser les id´ ees que nous venons d’introduire
pour obtenir un algorithme de compression photographique efficace.
Les id´ ees expos´ ees ci-dessus seront donc appliqu´ ees un peu diff´ eremment. Le point
commun est l’existence d’un syst` eme de fonctions it´ er´ ees, qu’on appellera syst` eme de
fonctions it´ er´ ees partitionn´ e, dont l’attracteur approximera l’image que l’on veut reproduire. La pr´ esentation qui suit a ´ et´ e inspir´ ee de [2]. La recherche se poursuit sur d’autres
m´ ethodes.
Repr´ esentation d’une image comme le graphe d’une fonction On discr´ etise
une photographie en la traitant comme un ensemble fini de minuscules carr´ es lumineux
appel´ es pixels (pour picture elements). `
A chacun de ces pixels, on associe un nombre
qui repr´ esente sa couleur. Pour simplifier, on va se limiter aux tons de gris. `
A chaque
point (x, y) du rectangle, on associe un nombre z qui repr´ esente son niveau de gris. Un
choix usuel en photographie num´ erique consiste ` a donner `
a z une valeur enti` ere dans
l’ensemble {0, . . . , 255} ; 0 repr´ esente le noir et 255 le blanc. Ainsi, de fa¸ con formelle, une
photographie est une fonction ! Si elle contient h pixels horizontalement et v verticalement et que nous notons par S N l’ensemble {0, 1, 2, . . . , N − 1}, alors une photographie
est une fonction
f : S h × S v −→ S 255 ,
c’est-` a-dire une r` egle qui associe ` a chaque pixel (x, y), 0 ≤ x ≤ h − 1, 0 ≤ y ≤ v − 1, un
ton de gris
z = f (x, y) ∈ {0, 1, 2, . . . , 255}.
Les fonctions ` a it´ erer que nous allons introduire ` a l’instant pourront transformer une
photographie f en une autre f
dont les valeurs ne sont pas des entiers entre 0 et 255.
Il sera donc plus facile de travailler sur les fonctions
f : S h × S v −→ R.
Construction du syst` eme de fonctions it´ er´ ees partitionn´ e C’est sur l’ensemble
F = {f : S h × S v → R} de toutes les photographies qu’agira le syst` eme de fonctions it´ er´ ees partitionn´ e. Voici comment ce syst` eme est construit pour une photographie
donn´ ee. On divise l’image en une r´ eunion de carr´ es de quatre pixels par quatre pixels :
un tel carr´ e, appel´ e petit carr´ e, est not´ e C i , et I d´ esigne l’ensemble des petits carr´ es.
Pour chaque petit carr´ e on choisit dans l’image le carr´ e de huit pixels par huit pixels
qui lui « ressemble le plus », que l’on appelle grand carr´ e associ´ e (figure 11.9) et qu’on
note G i . (Nous donnerons bientˆ ot une d´ efinition pr´ ecise de l’expression « ressemble le
plus ».)
11 Compression d’images par fonctions it´ er´ ees
parties de la photographie appartiendront `
a un tel patron fractal ? Il est fort probable
que non ! Mˆ eme si un humain r´ eussit ` a rapprocher chaque partie d’une photographie
donn´ ee d’un mod` ele fractal, et, ainsi, ` a reconstruire une image ressemblant ` a la photographie initiale (il y a de jolis exemples dans [1]), ceci n’est pas la mˆ eme chose que de
programmer un ordinateur pour le faire de mani` ere syst´ ematique sur des centaines de
photographies. Il faut transformer et g´ en´ eraliser les id´ ees que nous venons d’introduire
pour obtenir un algorithme de compression photographique efficace.
Les id´ ees expos´ ees ci-dessus seront donc appliqu´ ees un peu diff´ eremment. Le point
commun est l’existence d’un syst` eme de fonctions it´ er´ ees, qu’on appellera syst` eme de
fonctions it´ er´ ees partitionn´ e, dont l’attracteur approximera l’image que l’on veut reproduire. La pr´ esentation qui suit a ´ et´ e inspir´ ee de [2]. La recherche se poursuit sur d’autres
m´ ethodes.
Repr´ esentation d’une image comme le graphe d’une fonction On discr´ etise
une photographie en la traitant comme un ensemble fini de minuscules carr´ es lumineux
appel´ es pixels (pour picture elements). `
A chacun de ces pixels, on associe un nombre
qui repr´ esente sa couleur. Pour simplifier, on va se limiter aux tons de gris. `
A chaque
point (x, y) du rectangle, on associe un nombre z qui repr´ esente son niveau de gris. Un
choix usuel en photographie num´ erique consiste ` a donner `
a z une valeur enti` ere dans
l’ensemble {0, . . . , 255} ; 0 repr´ esente le noir et 255 le blanc. Ainsi, de fa¸ con formelle, une
photographie est une fonction ! Si elle contient h pixels horizontalement et v verticalement et que nous notons par S N l’ensemble {0, 1, 2, . . . , N − 1}, alors une photographie
est une fonction
f : S h × S v −→ S 255 ,
c’est-` a-dire une r` egle qui associe ` a chaque pixel (x, y), 0 ≤ x ≤ h − 1, 0 ≤ y ≤ v − 1, un
ton de gris
z = f (x, y) ∈ {0, 1, 2, . . . , 255}.
Les fonctions ` a it´ erer que nous allons introduire ` a l’instant pourront transformer une
photographie f en une autre f
dont les valeurs ne sont pas des entiers entre 0 et 255.
Il sera donc plus facile de travailler sur les fonctions
f : S h × S v −→ R.
Construction du syst` eme de fonctions it´ er´ ees partitionn´ e C’est sur l’ensemble
F = {f : S h × S v → R} de toutes les photographies qu’agira le syst` eme de fonctions it´ er´ ees partitionn´ e. Voici comment ce syst` eme est construit pour une photographie
donn´ ee. On divise l’image en une r´ eunion de carr´ es de quatre pixels par quatre pixels :
un tel carr´ e, appel´ e petit carr´ e, est not´ e C i , et I d´ esigne l’ensemble des petits carr´ es.
Pour chaque petit carr´ e on choisit dans l’image le carr´ e de huit pixels par huit pixels
qui lui « ressemble le plus », que l’on appelle grand carr´ e associ´ e (figure 11.9) et qu’on
note G i . (Nous donnerons bientˆ ot une d´ efinition pr´ ecise de l’expression « ressemble le
plus ».)