TP 17:Compression

Pourquoi compresser ?

Bien que la taille de la mémoire des ordinateurs ait augmenté ces dernières années, bien que la vitesse des processeurs ait augmenté, d'autres outils sont apparus téléphones mobiles, tablettes , utilisant beaucoup d'images, de vidéos et de sons

Pour que ces nouveaux outils puissent utiliser ces informations il est important que ces dernières soient compressées, c'est à dire que leur taille mesurée en Ko, ou Mo soit réduite

Exercice

Calculer la taille d'une vidéo d'une heure non compressée (30 images seconde)

Taille de 3 images

Voici 3 images numériques relever leur taille et les classer du plus petit au plus grand

Télécharger chat.pgm une image au format pgm (binaire)

Télécharger chat.png une image au format png (compression sans perte)

Télécharger chat_jpeg.jpg une image au format jpg (compression avec perte)

Histogramme d'une image

Au lieu de coder l'image uniquement par l'intensité en fonction de (x,y) comme le fait le format pgm, on peut commencer par faire l'histogramme d'une image

On classe les intensités en fonction de leur fréquence d'apparitions, exemple

Un exemple de compression sans pertes: Algorithme de Huffmann

L'idée plus une intensité est fréquente on la code avec un mot court

On va construire un arbre binaire de la manière suivante

Le fils gauche a une fréquence plus petite que le fils droit

Une fois l'arbre construit on parcourt l'arbre de la racine aux extrémités en associant 0 au fils gauche et 1 au fils droit


Début
On trie par ordre croissant les fréquences
Tant que nombre fréquences > 2 faire
	ajouter les deux fréquences les plus basses f1 et f2 
	on a un noeud F de l'arbre dont les fils sont f1 et f2
	classer F dans la suite des fréquences
Fin Tant que

Exercice

Appliquer l'algorithme sur :
Intensité fréquence
a 0,35
b 0,10
c 0,19
d 0,25
e 0,06
f 0,05

Un exemple de compression avec pertes: Quantification

L'idée est de réduire le nombres d'intensité sans que l'on s'en aperçoive

D'un point de vue mathématique on décrit une image (en nuances de gris) par une fonction $f(x,y)$ où $x$ varie de 0 à la largeur de l'image et $y$ varie de 0 à la hauteur de l'image, et $(x,y) \rightarrow f(x,y) \in [0;255]$

On note $T$ la transformation suivante sur l'image $f(x,y) \rightarrow T(f(x,y)) = (f(x,y)/2) \times 2$

Calculons quelques valeurs: $T(2) = 2/2 \times 2 = 2$ mais $T(3) = 3/2 \times 2 = 1 \times 2 = 2$

Autrement dit 0 et 1 ont même image 0, 2 et 3 ont même image 2, plus généralement 2n et 2n + 1 ont pour image 2n

Donc il n'y a que des valeurs paires, on a réduit le nombre d'intensités