2e année Informatique
TP-_Compression.d’images
La compression d’image est un type de compression de données appli-
qué aux images numériques en dégradant peu la qualité de l’image. La
réduction de la taille du fichier permet de stocker davantage d’images
sur un espace mémoire limité. Cela réduit également le temps nécessaire
pour que les images soient envoyées sur Internet ou téléchargées à partir
de pages Web.
Les algorithmes de compression d’image tirent parti de la perception
visuelle et des propriétés statistiques des données d’image pour fournir
des résultats de qualité. Il existe deux types de méthodes de compression
d’image sans perte ou avec perte.
Compression sans perte Il s’agit d’une méthode utilisée pour réduire la taille d’un fichier tout en
conservant la même qualité qu’avant sa compression. La compression sans perte ne compromet pas
la qualité des données et le fichier peut être restauré dans sa forme d’origine. La taille du fichier ne
change pas trop dans ce type de compression. Les algorithmes utilisés pour la compression sans perte
sont le codage de Huffman, le codage arithmétique...
Compression avec perte La compression avec perte est la méthode de compression qui élimine
les données qui ne sont pas perceptibles par l’humain. Pour donner à la photo une taille encore plus
petite, la compression avec perte supprime certaines parties d’une photo qui sont moins importantes. Le
fichier compressé ne peut pas être restauré dans sa forme originale exacte. Dans ce type de compression,
la qualité des données est compromise et la taille des données change. La compression avec perte est
principalement utilisée pour la compression des images, de l’audio et de la vidéo. Il existe de nombreux
algorithmes de compression avec perte : Transformée discrète en cosinus, Compression fractale...
Nous allons utiliser la technique des K-Moyennes (K-Means Clustering) pour la compression
d’image en modifiant la quantification des couleurs présentes dans l’image, ce qui permettra de dimi-
nuer la taille de l’image.
I Rappel sur les images
Une image matricielle est constituée d’un ensemble de pixels (nom provenant de l’anglais picture
elements). Le pixel (qui correspond à un point ou petit carré) est le plus petit élément que l’on peut
trouver dans une image. Il possède ses caractéristiques propres telles que sa couleur, sa luminosité ou
sa brillance.
Les pixels sont stockés la plupart du temps dans des tableaux à deux dimensions et sont espacés
régulièrement.
La résolution est la discrétisation des coordonnées spatiales qui détermine la précision de l’image.
C’est le nombre de pixels par unité de longueur dans l’image. La résolution d’une image se mesure en
"pixels par pouce" (ppp) ou "dots per inch" (dpi).
Taper les instructions suivantes :
import imageio
from numpy import *
# mettre le chemin absolu de l ’ image ou import os , os . chdir ()
im = imageio . imread ( " tour_eiffel . bmp " )
[h ,l , p ]= im . shape
TP–Compressiond’images_1/3
2e année Informatique
Q1. Aller voir les informations sur l’image données dans windows (taille, dimensions, type) obtenues en
survolant l’image avec la souris ou en faisant un clic droit puis Propriétés. Indiquer à quoi correspondent
les deux premiers nombres renvoyés par shape (h et l).
La définition (dimensions) d’une image est le nombre fixe de pixels utilisés pour représenter
l’image dans ses deux dimensions. Cette information détermine directement la taille des informations
à stocker.
Taper ensuite les instructions suivantes
r = zeros ([ h ,l ,3])
r [: ,: ,0]= im [: ,: ,0]
g = zeros ([ h ,l ,3])
g [: ,: ,1]= im [: ,: ,1]
b = zeros ([ h ,l ,3])
b [: ,: ,2]= im [: ,: ,2]
# mettre le chemin absolu pour sauvegarde
imageio . imsave ( " tour_r . bmp " , uint8 ( r ) )
imageio . imsave ( " tour_g . bmp " , uint8 ( g ) )
imageio . imsave ( " tour_b . bmp " , uint8 ( b ) )
Q2. Aller voir dans le dossier les images créées (en cliquant dessus). A quoi correspond la troisième
dimension p de im ? Quelles sont les valeurs prises par cette troisième dimension ?
La quantification détermine la qualité de l’image au niveau des couleurs. Cette quantification
se mesure en donnant un nombre de bits par pixel de l’image. En codant sur 8 bits, 256 valeurs sont
possibles pour chaque pixel. Si on code chaque couleur primaire (rouge, bleu, vert) sur 8 bits = 1
octet, on obtient 24 bits disponibles par pixel ce qui correspond à 16 millions de couleurs différentes
possibles.
Q3. Taper im pour vérifier le type des données pour chaque pixel. Calculer la taille en Ko de l’image
en couleur initiale et la vérifier sous Windows/Mac/Linux pour le fichier correspondant.
Pratiquement, nous ne pouvons visualiser que quelques couleurs dans une image très inférieure au
nombre de couleurs disponibles. Ainsi, l’algorithme des K-moyennes tire parti de la perception visuelle
limitée de l’œil humain et utilise peu de couleurs pour représenter l’image.
Q4. Tapez les commandes suivantes et aller à l’adresse suivante (https ://[Link]/colors/colors_rgb.as
pour indiquer à quelles couleurs correspondent les triplets obtenus. Où sont situés les pixels sélection-
nés ? Que peut-on dire des couleurs de x et z ?
x = im [0 ,0 ,:]
y = im [ -1 , -1 ,:]
z = im [20 ,20 ,:]
Nous allons utiliser l’algorithme des k-Moyennes pour trouver k couleurs qui seront représenta-
tives de couleurs similaires dans l’image. Ces k-couleurs seront des points centroïdes de l’algorithme.
Ensuite, nous remplacerons chaque valeur de pixel dans l’image par l’indice des points centroïdes. La
combinaison de couleurs formée en utilisant uniquement les valeurs k est très inférieure à la combinai-
son de couleurs totale.
Q5. S’il n’y a que 8 combinaisons de couleurs retenues, quelle est la taille de l’image en bits en fonction
de h, l ?
II Implémentation de l’algorithme k-moyennes
Dans un premier temps, l’image va être redimensionnée pour obtenir une liste de points (de dimen-
sions 3 correspondant aux 3 couleurs). On peut le faire simplement à l’aide de la commande numpy
suivante : data=[Link](h∗l,3).
La première étape de l’algorithme de k-moyennes consiste à initialiser les centroïdes. Pour cela,
on choisit de déterminer k centroïdes (chaque centroïde est un vecteur de dimension 3) dont les
coordonnées entières sont choisis aléatoirement entre 0 et 255 : c=[Link](0,255,3).
TP–Compressiond’images_2/3
2e année Informatique
Q6. Écrire une fonction initialise_centroides (k: int )−>[] qui renvoie une liste contenant les k centroïdes
choisis aléatoirement.
Chaque itération de l’algorithme k-moyennes est constituée de 2 étapes : assignation des centroïdes
pour chaque point et mise à jour des centroïdes.
L’assignation des centroïdes consiste à assigner à chaque point de data un entier entre 0 et k − 1
(correspondant à l’indice du centroïde dans la liste des centroïdes initialisée précédemment). Pour cela,
on calcule la distance euclidienne entre un point x (3 coordonnées entières) et un centroïde. On assigne
alors le centroïde le plus proche du point x.
Q7. Écrire une fonction calc_d(x :[], c :[]) −>float qui calcule et renvoie la distance euclidienne entre les
points x et c.
Q8. Écrire une fonction assign_centroides(data :[], centroides :[]) −>([],[]) qui renvoie une liste contenant l’indice
des centroides assignés à chaque point de data ainsi que la liste des distances de chaque point de data
et le centroïde auquel il est assigné. Il faudra utiliser la fonction calc_d.
La mise à jour des centroïdes se fait en calculant le barycentre des points assignés à un même
centroïde.
Q9. Écrire une fonction update_centroids(k:int, data :[], assignations :[]) −>[] qui renvoie une liste contenant les
nouveaux centroïdes à partir de data, de la liste des assignations assignations et du nombre de centroïdes
k.
On peut maintenant écrire la fonction itérative kmeans(data,k,err) qui après initialisation des centroïdes
va affecter les points de data à chaque centroïde puis mettre à jour les centroïdes. Le critère d’arrêt
sera basé sur le calcul d’une erreur correspondant à la somme de toutes les distances calculées à
l’assignation des centroïdes. L’algorithme s’arrêtera lorsque l’erreur successive entre 2 itérations est
inférieure à une valeur err .
Q10. Écrire une fonction kmeans(data:[],k: int , err : float ) −>([],[]) qui prend en argument la liste des points
data, le nombre de centroïdes souhaité k et une valeur d’erreur err et qui renvoie la liste des assignations
(indices dans la liste des centroïdes) ainsi que la liste des centroïdes
Q11.
Éxécuter les commandes suivantes pour extraire les k couleurs les plus représentatives puis créer
une nouvelle image new_img de la même taille que l’image d’origine qui utilise la liste assignations et les
centroides pour obtenir une image compressée. Visualiser cette image avec le module plt .imshow(new_img)
a s s i g n a t i o n s , d i s t a n c e s , c e n t r o i d e s=kmeans ( data , 8 , 1 0 0 )
c e n t r o i d e s=numpy . c e i l ( c e n t r o i d e s ) . a s t y p e ( i n t )
new_img=z e r o s ( ( h , l , 3 ) , dtype=u i n t 8 )
Q12. Observer les différences de qualité obtenues en augmentant le nombre de centroïdes.
L’algorithme proposé ne permet pas de traiter une image de grande taille car les boucles ne sont pas
optimisées. On pourrait obtenir un résultat beaucoup plus rapidement en écrivant toutes les fonctions
précédentes à l’aide de la vectorisation de Numpy. Il existe cependant un module déjà codé qui propose
l’algorithme kmeans optimisé et permet de traiter de grosses images. Si vous avez installe le module
sklearn en quelques lignes on réalise la compression.
from s k l e a r n . c l u s t e r i mp ort KMeans
kmeans = KMeans ( n _ c l u s t e r s =8)
kmeans . f i t ( data )
compressed_image = kmeans . c l u s t e r _ c e n t e r s _ [ kmeans . l a b e l s _ ]
compressed_image = numpy . c l i p ( compressed_image . a s t y p e ( ’ u i n t 8 ’ ) , 0 , 2 5 5 )
compressed_image = compressed_image . r e s h a p e ( h , l , 3 )
p l t . imshow ( compressed_image )
p l t . show ( )
TP–Compressiond’images_3/3