[DCT]

[Compression d'images'] : TIPE : La compression DCT (Jpeg)

 

PLAN:

 


PRINCIPE


 

Décomposition spatiale
(pixels)


Transformée de

Fourrier

Décomposition fréquentielle
(coeffs de Fourrier)

 

 


INTERETS

- Comme la plupart des images sont régulières, les données de l’image transformée sont concentrées dans le domaine des basses fréquences. (gain de place)
- Ces donnes n’ont pas toute la même importance dans l’image. (possiblité d'en négliger certaines)



DECOMPOSITION

L'image est avant tout décomposée en blocs de 8*8 qui sont traités indépendament les uns des autres.
On note A = (aij) un bloc de l'image originale, et B = (bij) le bloc correspondant dans l'image transformée. On a deux matrices de taille 8*8.

La transformée cosinus discrete bidimensionelle s'écrit alors:

avec et .

 

Une forme équivalente pour cette formule est la suivante : B = P-1AP où P est la matrice dont les coefficients sont :

Pour montrer cette formule, il suffit d'effectuer le produit matriciel et on retombe sur la première formule.

De plus, P-1 = Pt, donc P est une matrice orthogonale, ce qui permet de l'inverser rapidement pour obtenir la transformée inverse (on prend juste la transposée)

Cette constatation peut inspirer la remqrque suivante : Si on considère la base (Eij) de l'ensemble des matrice de taille 8*8, alors, comme P est inversible, P-1AP est également une base. C'est la base qui correspond à la décomposition de l'image par la transformée de Fourrier. En effet, l'image est alors combinaison linéaire de ces vecteurs là. Il est représenté ici les vecteurs de cette base :

 

 

 


QUANTIFICATION


Le but est le suivant :pondérer l’importance des différents domaines de fréquences, sachant que la vision humaine est moins sensible aux hautes fréquences de détails.On va donc attribuer à chaque donnée un coefficient de poids qui correspond à son importance dans l'image. Cela revient à diviser les coefficients de Fourrier de l'image par ces coefficients de poids, et ne garder que ceux supérieurs à une certaine valeur. (on ne garde que les fréquences vraiment représentée dans l'image).

La matrice de quantification est empirique. Elle n'est pas unique.Une matrice convenable est la suivante :

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
27
29
21
23
25
27
29
31

Elle est caractérisée par des coefficients croissent en même temps que la fréquence globale du coefficient. Comme chaque coefficient est caractérisé par deux fréquences (une verticale et une horizontale - CF image ci-dessus) on appelle fréquence globale la somme des deux fréquence. On constate que dans la matrice de quantification, à fréquence globale identique on a le même coefficient de poids.

L'utilisation pratique de cette matrice est très simple. On la note Q = (qij). On note également Q' l'image transformée et quantifiée. On a alors :

q'ij = qij / bij

Cela correspond bien à ce que l'on veut faire : on "écrase" les hautes fréquences pour privilégier les basses fréquences auxquelles l'oeil humain est plus sensible.

 


CODAGE ENTROPIQUE

Avant toute chose, la matrice représentant l'image [en deux dimensions] est linéarisée afin de subir un codage réversible (ou entropique). Il est effectuée en diagonale.

 

 

Enuite, un codage RLE est appliqué, puis un codage de Huffman. Le principe de ce codage est le suivant : si on cosidère un fichier, celui-ci est constitué de données qui sont toutes codées avec la même quantité d'information (sur 8 bit ou 16 bit par exemple). Or, si certaines données reviennent beaucoup plus souvent que d'autres, il est plus avantageux de les coder sur un petit nombre de bit, quitte à utiliser plus de bits après pour les données qui reviennent rarement. Huffman a trouvé un algorithme qui permet d'attribuer à chaque valeur possible un code qui répond aux exigences précédentes et qui permet une lecture du fichier codé même lorsque les codes sont mis bout-à-bout (unicité de l'interprétation du fichier codé).

Pour plus de détails sur Huffman, je vous renvoie à ces sites :

http://www.alphabeta-net.com/Huffman.html
http://helium.le-mulot.org/huffman.php

Il existe d'autres algorithmes de codage reversible : Shannon Fano, LZW, codage arithmétique.

 


EXEMPLES

Voici l'image sur laquelle on travaille (le contraste a été accentué) :

139
144
149
153
155
155
155
155
144
151
153
156
159
156
156
156
150
155
160
163
158
156
156
156
159
161
162
160
160
159
159
159
159
160
161
162
162
155
155
155
161
161
161
161
160
154
157
157
162
162
161
163
162
157
157
157
162
162
161
161
163
158
158
158

Image originale

235
-1
-12
-5
2
-2
-3
1
-23
-18
-6
-3
-3
0
0
-1
-11
-9
-2
2
0
-1
-1
0
-7
-2
0
2
1
0
0
0
-1
-1
2
2
0
-1
1
1
2
0
2
0
-1
2
1
-1
-1
0
0
-1
0
2
1
-1
-3
2
-4
-2
2
1
-1
0

Image transforméee

15
0
-1
0
0
0
0
0
-2
-1
0
0
0
0
0
0
-1
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Image transformée et quantifiée

144 146 149 152 154 156 156 156
148 150 152 154 156 156 156 156
155 156 157 158 158 157 156 155
160 161 161 162 161 159 157 155
163 163 164 163 162 160 158 156
163 164 164 164 162 160 158 157
160 161 162 162 162 161 159 158
158 159 161 161 162 161 159 158

Image reconstituée

-5
-2
0
1
1
-1
-1
-1
-4
1
-1
-2
-3
0
0
0
-5
1
3
5
0
-1
0
1
-1
0
1
-2
-1
0
2
4
-4
-3
-3
-1
0
-5
-3
-1
-2
-3
-3
-3
-2
-3
-1
0
2
1
-1
1
0
-4
-2
-1
4
3
0
0
1
-3
-1
0

Ecart entre l'image originale et l'image décoimpressée

Ecart relatif maximal :

2 %

 

Guillem PRATX - Mail : mon nom de famille @stanford.edu

 

[Retour à la page d'accueil]