380
12 Compression d’images : le standard JPEG
une certaine d´ egradation du contenu (dits avec perte) et ceux qui permettent la restitution parfaite du contenu original (dits sans perte). Deux observations simples s’imposent.
La premi` ere est qu’il est impossible de comprimer sans perte tous les fichiers d’une
taille donn´ ee. Supposons qu’une telle m´ ethode existe pour tous les fichiers ayant pr´ ecis´ ement N bits. Chacun des bits peut prendre deux valeurs (0 et 1), et il existe donc
au total 2
N fichiers ayant pr´ ecis´ ement N bits. Si l’algorithme comprime v´ eritablement
tous les fichiers, alors chacun de ces 2
N fichiers sera repr´ esent´ e par au plus N − 1 bits.
Or, il existe 2
N −1 fichiers de longueur N − 1, il en existe 2
N −2 de longueur N − 2, . . . ,
et il en existe 2
1 de longueur 1 et un seul de longueur nulle. Le nombre de fichiers de
moins de N bits est ainsi :
1 + 2
1 + 2
2 + · · · + 2
N −2 + 2
N −1 =
N −1
n=0
2
i =
2
N
− 1
2 − 1
= 2
N
− 1.
Il existe donc au moins deux fichiers de N bits qui seront comprim´ es en un mˆ eme fichier
plus court. Et ces deux fichiers deviendront donc indistinguables apr` es compression. `
A
nouveau : il est impossible de comprimer sans perte tous les fichiers d’une taille donn´ ee.
La seconde observation est une cons´ equence de la premi` ere : en d´ eveloppant un algorithme de compression, la personne charg´ ee de cette tˆ ache doit d´ ecider s’il est important
de transmettre l’information sans absolument aucune perte ou si une l´ eg` ere perte (ou
transformation) de l’information peut ˆ etre tol´ er´ ee. Deux exemples peuvent aider ` a comprendre la nature de ce choix et certaines des m´ ethodes qui seront utilis´ ees une fois
celui-ci fait.
Le Petit Robert (´ edition de 1972) contient environ 1950 pages, deux colonnes par
page, 90 lignes par colonnes, une soixantaine de caract` eres par ligne, pour un total
d’environ 21 millions de caract` eres. Ces caract` eres peuvent ˆ etre repr´ esent´ es dans un
alphabet de 256 caract` eres o` u chacun est cod´ e par huit bits, soit un octet (voir la section
12.2). Il faut donc environ 21 Mo pour emmagasiner ce dictionnaire. (Notons qu’un
disque compact peut contenir pr` es de 750 Mo. La totalit´ e du Petit Robert pourrait donc
ˆ etre log´ ee, sans compression, plus de 35 fois sur un disque compact.) Aucun auteur d’un
dictionnaire, d’une encyclop´ edie ou d’un trait´ e n’acceptera de voir une lettre de son texte
chang´ ee par un algorithme de compression permettant des pertes ou transformations
de l’information. Il faudra alors choisir un algorithme de compression permettant de
reproduire fid` element le document original.
Une id´ ee assez r´ epandue pour un tel algorithme est d’accorder un code de longueur
variable `
a chacune des lettres de l’alphabet. Sachant qu’un texte en fran¸ cais contient
en grande majorit´ e des espaces « » entre les mots et la lettre « e », il est naturel de
leur accorder un code plus court (un ou deux bits) que les lettres « k » et « w » qui
n’apparaissent pratiquement jamais. (Voir la table 12.1.) De cette fa¸ con, les caract` eres
obtiennent des repr´ esentations de longueur variable (plutˆ ot que d’une longueur uniforme
de un octet), les lettres plus probables ayant les repr´ esentations les plus courtes. Cet
algorithme ne viole-t-il pas notre premi` ere observation ? Non, certains textes pourront
ˆ etre repr´ esent´ es par des fichiers plus longs que les fichiers originaux o` u toutes les lettres
12 Compression d’images : le standard JPEG
une certaine d´ egradation du contenu (dits avec perte) et ceux qui permettent la restitution parfaite du contenu original (dits sans perte). Deux observations simples s’imposent.
La premi` ere est qu’il est impossible de comprimer sans perte tous les fichiers d’une
taille donn´ ee. Supposons qu’une telle m´ ethode existe pour tous les fichiers ayant pr´ ecis´ ement N bits. Chacun des bits peut prendre deux valeurs (0 et 1), et il existe donc
au total 2
N fichiers ayant pr´ ecis´ ement N bits. Si l’algorithme comprime v´ eritablement
tous les fichiers, alors chacun de ces 2
N fichiers sera repr´ esent´ e par au plus N − 1 bits.
Or, il existe 2
N −1 fichiers de longueur N − 1, il en existe 2
N −2 de longueur N − 2, . . . ,
et il en existe 2
1 de longueur 1 et un seul de longueur nulle. Le nombre de fichiers de
moins de N bits est ainsi :
1 + 2
1 + 2
2 + · · · + 2
N −2 + 2
N −1 =
N −1
n=0
2
i =
2
N
− 1
2 − 1
= 2
N
− 1.
Il existe donc au moins deux fichiers de N bits qui seront comprim´ es en un mˆ eme fichier
plus court. Et ces deux fichiers deviendront donc indistinguables apr` es compression. `
A
nouveau : il est impossible de comprimer sans perte tous les fichiers d’une taille donn´ ee.
La seconde observation est une cons´ equence de la premi` ere : en d´ eveloppant un algorithme de compression, la personne charg´ ee de cette tˆ ache doit d´ ecider s’il est important
de transmettre l’information sans absolument aucune perte ou si une l´ eg` ere perte (ou
transformation) de l’information peut ˆ etre tol´ er´ ee. Deux exemples peuvent aider ` a comprendre la nature de ce choix et certaines des m´ ethodes qui seront utilis´ ees une fois
celui-ci fait.
Le Petit Robert (´ edition de 1972) contient environ 1950 pages, deux colonnes par
page, 90 lignes par colonnes, une soixantaine de caract` eres par ligne, pour un total
d’environ 21 millions de caract` eres. Ces caract` eres peuvent ˆ etre repr´ esent´ es dans un
alphabet de 256 caract` eres o` u chacun est cod´ e par huit bits, soit un octet (voir la section
12.2). Il faut donc environ 21 Mo pour emmagasiner ce dictionnaire. (Notons qu’un
disque compact peut contenir pr` es de 750 Mo. La totalit´ e du Petit Robert pourrait donc
ˆ etre log´ ee, sans compression, plus de 35 fois sur un disque compact.) Aucun auteur d’un
dictionnaire, d’une encyclop´ edie ou d’un trait´ e n’acceptera de voir une lettre de son texte
chang´ ee par un algorithme de compression permettant des pertes ou transformations
de l’information. Il faudra alors choisir un algorithme de compression permettant de
reproduire fid` element le document original.
Une id´ ee assez r´ epandue pour un tel algorithme est d’accorder un code de longueur
variable `
a chacune des lettres de l’alphabet. Sachant qu’un texte en fran¸ cais contient
en grande majorit´ e des espaces « » entre les mots et la lettre « e », il est naturel de
leur accorder un code plus court (un ou deux bits) que les lettres « k » et « w » qui
n’apparaissent pratiquement jamais. (Voir la table 12.1.) De cette fa¸ con, les caract` eres
obtiennent des repr´ esentations de longueur variable (plutˆ ot que d’une longueur uniforme
de un octet), les lettres plus probables ayant les repr´ esentations les plus courtes. Cet
algorithme ne viole-t-il pas notre premi` ere observation ? Non, certains textes pourront
ˆ etre repr´ esent´ es par des fichiers plus longs que les fichiers originaux o` u toutes les lettres