Historique
L'histoire commence à la fin des années 80, lorsque deux
importants groupes de normalisation, le CCITT (Consultative Committe
for International Telegraph and Telephone ) et l'ISO (Organisation Internationale
de Standardisation) décidèrent de créer, appuyés
par divers groupes industriels et universitaires, une norme internationale
pour la compression d'images fixes. La mise en place d'un standard international
était devenue nécessaire pour archiver ou pour faciliter
l'échange des images dans des domaines aussi variés que
les photos satellites, l'imagerie médicale, la télécopie
couleur, ou la cartographie. C'est ainsi que fut créé
le groupe JPEG (Joint Photgraphic Experts Group) à l'origine
de la norme qui porte son nom. Cette norme comprend des spécifications
pour les codages conservateurs (l'image est restituée identique
à elle-même à la suite du codage) et non conservateurs
(l'image est légèrement modifiée pendant le cycle
de compression mais cette modification reste imperceptible pour l'œil)
de l'image. Le JPEG est aujourd'hui largement utilisé dans les
secteurs de l'informatique et de la communication (appareils photo numériques,
scanners, imprimantes, télécopieurs…).
Le principe général
Le
principe de l'algorithme JPEG pour une image à niveaux de gris
(étant donné qu'une image couleur est la somme de 3 images
de ce même type, dans la suite du TIPE nous ne considérerons
plus que ce genre d'images) est le suivant. La matrice des pixels de
l'image numérique est décomposée en blocs de 8x8
pixels qui vont tous subir le même traitement. Une transformation
linéaire, le plus souvent du type FFT (Fast Fourier Transform)
ou DCT (Discret consine Transform) est réalisée sur chaque
bloc. Ces transformations complexes concentrent l'information sur l'image
en haut et à gauche de la matrice. Les coefficients de la transformée
sont ensuite quantifiés à l 'aide d'une table de 64 éléments
définissant les pas de quantification. Cette table permet de
choisir un pas de quantification important pour certaines composantes
jugées peu significatives visuellement. On introduit ainsi un
critère perceptif qui peut être rendu dépendant
des caractéristiques de l'image et de l'application (taille du
document). Des codages (prédictif, entropique, l'algorithme de
Huffmann ou arithmétique), sans distorsion, sont ensuite réalisés
en utilisant les propriétés statistiques des images. Ces
compressions seront suivis d'une transformation inverse de la transformation
initiale, conduisant à la restitution de l'image.
Approfondissons un peu....
Soit un bloc de 8 x 8 pixels à 256 niveaux de gris:
Remarque: Si l'on avait pris une image 24 bits
on aurait eut trois matrices différentes; l'une codant pour le
rouge, l'une codant pour le vert et l'une codant pour le bleu. On peut
aussi ajouter une matrice pour la chrominance ou pour la luminance.
Mais alors l'image sera codée sur 32 bits...
Matrice de pixels d'entrée
| 140 |
144 |
147 |
140
|
140
|
155
|
179
|
175
|
|
144
|
152
|
140
|
147
|
140
|
148
|
167
|
179
|
|
152
|
155
|
136
|
167
|
163
|
162
|
152
|
172 |
|
168
|
145
|
156
|
160
|
152
|
155
|
136
|
160
|
|
162
|
148
|
156
|
148
|
140
|
136
|
147
|
162
|
|
147
|
167
|
140
|
155
|
155
|
140
|
136
|
162
|
|
136
|
156
|
123
|
167
|
162
|
144
|
140
|
147
|
|
148
|
155
|
136
|
155
|
152
|
147
|
147
|
136
|
La DCT
L'image est découpé en bloc de 8 x 8 pixel. Ensuite la
Transformée en Cosinus Discète (DCT) est appliqué sur les pixels de
chaque bloc. Cette transformation numérique est une variété de la transformée
de Fourier. Elle permet de décrire chaque bloc en un graphique de fréquences
(correspondant à l'importance et à la rapidité d'un changement de couleur)
et en amplitudes (qui est l'écart associé à chaque changement de couleur)
plutôt qu'en pixels et qu'en couleurs comme c'est le cas normalement.
La DCT étant un procédé très complexe nous
ne pouvons aller plus loin dans notre développement et une longue
formule que l'on ne comprend pas n'apporterait rien..A ce niveau -ci
il n'y a pas encore de pertes de données
Matrice DCT
| 1210 |
-18 |
15 |
-9
|
23
|
-9
|
-14
|
-19
|
|
21
|
-34
|
26
|
-9
|
-11
|
11
|
14
|
7
|
|
-10
|
-24
|
-2
|
6
|
-18
|
3
|
-20
|
-1
|
|
-8
|
-5
|
14
|
-15
|
-8
|
-3
|
-3
|
8
|
|
-3
|
10
|
8
|
1
|
-11
|
18
|
18
|
15
|
|
4
|
-2
|
-18
|
8
|
8
|
-4
|
1
|
-7
|
|
9
|
1
|
-3
|
4
|
-1
|
-7
|
-1
|
-2
|
|
0
|
-8
|
-2
|
2
|
1
|
4
|
-6
|
0
|
Les valeurs de la matrice DCT ont été arrondies à l'entier le plus proche.
Le coefficient continu 1210 sur la composante (0,0) représente "la moyenne"
de la grandeur d'ensemble de la matrice d'entrée. Cette moyenne n'est
pas une moyenne statique mais un nombre proportionnel à la somme de
toutes les valeurs du signal. Les autres valeurs de la DCT sont les
"écarts" par rapport à cette moyenne. Lorsque l'on monte dans les hautes
fréquences, les valeurs de la matrice ont tendance à s'approcher de
0 quand on s'eloigne du coin supérieur gauche de la matrice.
L'étape de la quantification de chaques blocs regroupent les ensembles
de valeurs proches.
Ensuite, chaque amplitude originale sera remplacée par la valeur moyenne
de l'intervale, c'est à dire l'étape de quantification est de diminuer
la précision du stockage des entiers de la matrice DCT pour diminuer
le nombre de bits occupés par chaque entier. C'est la partie non conservative
de la méthode. Les basses fréquences sont conservées, la précision des
hautes fréquences sont diminuées. La perte de précision est plus grande
lorsqu'on s'éloigne de la position(0,0). Les valeurs de la matrice DCT
sera divisée par la matrice de quantification.
La quantification
Réglage du pas de
quantification
Exemple
Supposons qu'une variable puisse prendre
les valeurs 1, 2, 3, 4, 5.........Si l'on prend un pas de quantification
de 4 on garde le quotient de la division euclidienne de la valeur par
le pas de quantification. Pour cela on utilise d'abord les congruences
pour trouver le reste de la division euclidienne, cette division est
de la forme a = bq + r avec 0 < r < b donc q = (a-r)/b. Donc pour
trouver le reste il faut d'abord le calculer avec une congruences de
la forme a congru à r modulo b.
|
a
|
r
|
q
|
|
0
|
0
|
0
|
|
1
|
1
|
0
|
|
2
|
2
|
0
|
|
3
|
3
|
0
|
|
4
|
0
|
1
|
|
5
|
1
|
1
|
|
6
|
2
|
1
|
|
7
|
3
|
1
|
|
8
|
0
|
2
|
|
9
|
1
|
2
|
|
10
|
2
|
2
|
|
11
|
3
|
2
|
|
12
|
0
|
3
|
|
13
|
1
|
3
|
|
14
|
2
|
3
|
|
15
|
3
|
3
|
Donc si on prend un pas de quantification de 4 on va remplacer
:
0, 1, 2, 3 par 0
4, 5, 6, 7 par 1
8, 9, 10, 11 par 2
12, 13, 14, 15 par 3
C'est à cette étape que nous allons
perdre de l'information et nous allons la perdre d'une manière
"astucieuse" parce que le pas de quantification dont dépend
la précision de l'image restitué va dépendre de
la position de la valeur dans la matrice. Nous allons prendre un pas
relativement petit pour les valeurs importantes ( en haut à gauche
) et prendre un pas de plus en plus grand au fur et à mesure
qu'on descend vers le bas et la droite de la matrice. l'ensemble des
pas qui vont être utilisés constituent ce que l'on appelle
une matrice de quantification. Une matrice peut être fabriquer
grâce une petite formule
Q( i , j ) = 1 + ( 1 + i + j ) x Fq
Fq est le facteur de qualité
Si l'on prend ici un facteur de qualité de 5 nous obtenons après
calcul la matrice suivante. Le calcul est très simple, on prend
la position de chaque pixel dans la matrice DCT, la valeur du pixel
n'intervient pas dans le calcul, puis on met le résultat dans
la matrice de quantification au même coordonnées que dans
la matrice DCT. Simple non ?
Matrice de quantification
|
3
|
5
|
7
|
9
|
11
|
13
|
15
|
17
|
|
5
|
7
|
9
|
11
|
13
|
15
|
17
|
19
|
|
7
|
9
|
11
|
13
|
15
|
17
|
19
|
21
|
|
9
|
11
|
13
|
15
|
17
|
19
|
21
|
23
|
|
11
|
13
|
15
|
17
|
19
|
21
|
23
|
25
|
|
13
|
15
|
17
|
19
|
21
|
23
|
25
|
27
|
|
15
|
17
|
19
|
21
|
23
|
25
|
27
|
29
|
|
17
|
19
|
21
|
23
|
25
|
27
|
29
|
31
|
Matrice DCT quantifiée
Pour cela on divise juste comme expliqué
ci-dessus la matrice DCT par la matrice de quantification. Et cela nous
donne :
|
403
|
-4
|
2
|
-1
|
2
|
-1
|
-1
|
1
|
|
4
|
-5
|
3
|
-1
|
-1
|
1
|
1
|
0
|
|
-1
|
-3
|
0
|
0
|
-1
|
0
|
-1
|
0
|
|
-1
|
0
|
1
|
-1
|
0
|
0
|
0
|
1
|
|
0
|
1
|
1
|
0
|
-1
|
1
|
1
|
0
|
|
0
|
0
|
-1
|
0
|
0
|
0
|
0
|
0
|
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
Lors de la décompression, il suffira de multiplier la
valeur de la matrice DCT quantifiée par l'élément correspondant de la
matrice de quantification pour obtenir une approximation de la DCT.
La matrice obtenue est appelée matrice DCT déquantifiée.
L'encodage
Le codage de la matrice DCT quantifiée se fait en
parcourant les éléments dans l'ordre imposé par une séquence appelée
Séquence zigzag. Les éléments sont parcourus en commençant par les basses
fréquences puis ensuite en traitant les fréquences de plus en plus élevées.
Etant donné qu'il y a beaucoup de composantes de hautes fréquences qui
sont nulles dans la matrice DCT, la séquence zigzag engendre de longues
suites de 0 consécutifs. D'une part, les suites de valeurs nulles sont
simplement codées en donnant le nombre de 0 successifs. D'autre part,
les valeurs non nulles seront codées en utilisant une méthode statitisque
de type Huffman.
Remarque: Les fréquences les plus hautes
se situent en bas à droite et les fréquences les plus
basses se situent en haut à gauche.
