11.7 Une photographie comme attracteur
371
Le degr´ e de compression r´ ealis´ e En 2007, plusieurs appareils num´ eriques populaires
offraient des capteurs d’environ huit millions de pixels et les appareils professionnels
allaient jusqu’` a 50 millions de pixels. ´
Etudions donc le degr´ e de compression obtenu
pour une photographie de 3000 pixels par 2000 pixels avec 2
8 = 256 tons de gris.
Chaque ton de gris est donn´ e par huit bits, soit un octet (un octet ´ egale huit bits). Le
fichier non comprim´ e donnant le ton de gris de chaque pixel a 6 × 8 × 10
6 bits, soit
six m´ egaoctets (6Mo). Voyons maintenant de combien de bits nous avons besoin pour
mettre en m´ emoire le fichier comprim´ e selon la m´ ethode d´ ecrite.
Pour chaque petit carr´ e C i 4 × 4, on met en m´ emoire une transformation T i choisie
pour ce carr´ e. Comptons le nombre de bits n´ ecessaires.
(i) Nombre de bits pour repr´ esenter une transformation T i de la forme (11.16) :
• trois bits pour repr´ esenter la partie lin´ eaire L de T i , car on a 2
3 = 8 possibilit´ es ;
• huit bits pour le facteur s i permettant d’ajuster l’amplitude des tons de gris ;
• neuf bits pour g i puisqu’on doit permettre des translations n´ egatives de couleur.
(ii) Nombre de bits pour pr´ eciser le grand bloc associ´ e : il suffit de donner les coordonn´ ees (e i , f i ) du coin sup´ erieur gauche du grand carr´ e. Si nous acceptons tous les
carr´ es 8 × 8, alors e i ∈ {0, . . . , 2992}, f i ∈ {0, . . . , 1992}, et il y a trop de possibilit´ es
pour obtenir une bonne compression. Si nous nous limitons aux grands carr´ es pour
lesquels e i et f i sont des multiples de 8 (comme nous l’avons fait pour comprimer
la photographie de la chatte), alors il reste
3000
8 ×
2000
8
= 93 750 choix. Comme
2
16 = 65 536 < 93 750 < 2
17 = 131 072, il faudra 17 bits pour fixer la position du
grand carr´ e.
(iii) Nombre de petits carr´ es n´ ecessaires pour recouvrir la photographie :
3000
4 ×
2000
4 =
375 000.
Au total, on a besoin de 3+8+9+17 = 37 bits pour d´ efinir la transformation T i associ´ ee
` a chacun des 375 000 petits carr´ es, ce qui donne un total de 37×375 000 bits ou 1,73 Mo.
La compression est de l’ordre de 3,46. Dans cette m´ ethode, on voit qu’on peut jouer
beaucoup sur le nombre de grands carr´ es qu’on compare au petit carr´ e. Si, au lieu de
la solution retenue, on explore seulement le quart des grands carr´ es, par exemple, ceux
qui sont au voisinage du petit carr´ e choisi, le nombre de bits n´ ecessaires pour rep´ erer la
position du grand carr´ e associ´ e diminue de deux (de 37 `
a 35) et le degr´ e de compression
devient
37
35 × 1,73 ≈ 3,66.
Un gain plus substantiel est r´ ealis´ e si la taille des petits carr´ es est fix´ ee ` a 8 × 8 pixels
et celle des grands ` a 16 × 16 ; c’est alors un facteur 4 qui est gagn´ e, mais on perd plus
en qualit´ e. Finalement, la taille des petits carr´ es et des grands carr´ es n’a pas besoin
d’ˆ etre fixe. On pourrait augmenter la taille des carr´ es dans des r´ egions de l’image o` u il
y a peu de d´ etails. Le degr´ e de compression peut donc ˆ etre am´ elior´ e selon les capacit´ es
du stockage et la fid´ elit´ e de la reproduction d´ esir´ ee.
Les syst` emes de fonctions it´ er´ ees partitionn´ es et JPEG La m´ ethode d´ ecrite
ici est tr` es diff´ erente du format JPEG. Quelle m´ ethode de compression d’images est
la meilleure ? Cela d´ epend du type d’image, du taux de compression d´ esir´ e et de la
371
Le degr´ e de compression r´ ealis´ e En 2007, plusieurs appareils num´ eriques populaires
offraient des capteurs d’environ huit millions de pixels et les appareils professionnels
allaient jusqu’` a 50 millions de pixels. ´
Etudions donc le degr´ e de compression obtenu
pour une photographie de 3000 pixels par 2000 pixels avec 2
8 = 256 tons de gris.
Chaque ton de gris est donn´ e par huit bits, soit un octet (un octet ´ egale huit bits). Le
fichier non comprim´ e donnant le ton de gris de chaque pixel a 6 × 8 × 10
6 bits, soit
six m´ egaoctets (6Mo). Voyons maintenant de combien de bits nous avons besoin pour
mettre en m´ emoire le fichier comprim´ e selon la m´ ethode d´ ecrite.
Pour chaque petit carr´ e C i 4 × 4, on met en m´ emoire une transformation T i choisie
pour ce carr´ e. Comptons le nombre de bits n´ ecessaires.
(i) Nombre de bits pour repr´ esenter une transformation T i de la forme (11.16) :
• trois bits pour repr´ esenter la partie lin´ eaire L de T i , car on a 2
3 = 8 possibilit´ es ;
• huit bits pour le facteur s i permettant d’ajuster l’amplitude des tons de gris ;
• neuf bits pour g i puisqu’on doit permettre des translations n´ egatives de couleur.
(ii) Nombre de bits pour pr´ eciser le grand bloc associ´ e : il suffit de donner les coordonn´ ees (e i , f i ) du coin sup´ erieur gauche du grand carr´ e. Si nous acceptons tous les
carr´ es 8 × 8, alors e i ∈ {0, . . . , 2992}, f i ∈ {0, . . . , 1992}, et il y a trop de possibilit´ es
pour obtenir une bonne compression. Si nous nous limitons aux grands carr´ es pour
lesquels e i et f i sont des multiples de 8 (comme nous l’avons fait pour comprimer
la photographie de la chatte), alors il reste
3000
8 ×
2000
8
= 93 750 choix. Comme
2
16 = 65 536 < 93 750 < 2
17 = 131 072, il faudra 17 bits pour fixer la position du
grand carr´ e.
(iii) Nombre de petits carr´ es n´ ecessaires pour recouvrir la photographie :
3000
4 ×
2000
4 =
375 000.
Au total, on a besoin de 3+8+9+17 = 37 bits pour d´ efinir la transformation T i associ´ ee
` a chacun des 375 000 petits carr´ es, ce qui donne un total de 37×375 000 bits ou 1,73 Mo.
La compression est de l’ordre de 3,46. Dans cette m´ ethode, on voit qu’on peut jouer
beaucoup sur le nombre de grands carr´ es qu’on compare au petit carr´ e. Si, au lieu de
la solution retenue, on explore seulement le quart des grands carr´ es, par exemple, ceux
qui sont au voisinage du petit carr´ e choisi, le nombre de bits n´ ecessaires pour rep´ erer la
position du grand carr´ e associ´ e diminue de deux (de 37 `
a 35) et le degr´ e de compression
devient
37
35 × 1,73 ≈ 3,66.
Un gain plus substantiel est r´ ealis´ e si la taille des petits carr´ es est fix´ ee ` a 8 × 8 pixels
et celle des grands ` a 16 × 16 ; c’est alors un facteur 4 qui est gagn´ e, mais on perd plus
en qualit´ e. Finalement, la taille des petits carr´ es et des grands carr´ es n’a pas besoin
d’ˆ etre fixe. On pourrait augmenter la taille des carr´ es dans des r´ egions de l’image o` u il
y a peu de d´ etails. Le degr´ e de compression peut donc ˆ etre am´ elior´ e selon les capacit´ es
du stockage et la fid´ elit´ e de la reproduction d´ esir´ ee.
Les syst` emes de fonctions it´ er´ ees partitionn´ es et JPEG La m´ ethode d´ ecrite
ici est tr` es diff´ erente du format JPEG. Quelle m´ ethode de compression d’images est
la meilleure ? Cela d´ epend du type d’image, du taux de compression d´ esir´ e et de la