1. Quantification d'images en niveaux de gris
1.1 Qu'est ce que la quantification?
1.2 Erreur de quantification
1.3 Algorithme de Lloyd-Max

2. Quantification d'images en couleur
2.1 Utilisation d'une palette fixe
2.2 Création d'une palette adaptée à l'image

1. Quantification d'images en niveaux de gris


1.1 QU'EST CE QUE LA QUANTIFICATION?

La quantification est un procédé de traitement du signal, qui permet d'approximer un signal analogique par un signal discret. Cette opération permet de passer d'un signal continu à un signal discret dans un espace de petite taille. Les applications les plus courantes sont la numérisation d'un signal analogique et des applications de compression du signal (Algorithme de compression JPEG p.e.). Il existe plusieurs méthodes de quantification. La plus simple est appelée Quantification Scalaire ; cette technique consiste à faire correspondre une et une seule valeur discrète sur intervalle borné.

Mathématiquement cela correspond à l'application



où D est un ensemble discret fini, de taille n.

Les intervalles de quantification sont définis par , où les sont appelés niveaux de décision.
La quantité est appelée quantum, ou pas de quantification.
Si on parle de quantification scalaire uniforme.

Il existe d'autres méthodes de quantification, le quantificateur à zone morte qui permet de quantifier à zéro des valeurs considérées comme « petites » et le quantificateur optimal donné par l'algorithme de Llyod-Max (1).

Voici un exemple de quantification d'une sinusoïdale :
Quantification d'un sinus avec 8 niveaux
Avec un quantificateur scalaire uniforme défini pour
.

1.2 ERREUR DE QUANTIFICATION.

L'erreur de quantification est due à la perte d'information engendrée par la quantification du signal. On mesure cette erreur par la distance suivante :
,
où est le signal quantifié.

Si nous utilisons cette distance, nous pouvons introduire l'erreur quadratique moyenne (EQM) définie par :


où F est le signal original, Q le signal quantifié, le ième échantillon et N le nombre d'échantillons.

Notons que cette erreur est souvent appelée distortion.
Par exemple, nous avons une EQM ; D = 0.0153605 pour notre sinus quantifié.
Voici la représentation graphique de l'erreur commise (différence entre les 2 signaux) : Erreur de quantification d'un sinus avec 8 niveaux

1.3 ALGORITHME DE LLOYD-MAX

Voici l'algorithme de Lloyd-Max, un algorithme qui permet de construire le quantifieur scalaire optimal.
Le quantifieur optimal est celui qui minimise la distorsion.

Le quantifieur scalaire uniforme est optimal si l'amplitude de la source suit une distribution uniforme. Les signaux audio ou image ne peuvent cependant être considérés comme des sources uniformes, ce qui a conduit à la recherche d'algorithmes permettant de générer un quantifieur optimal, pour tous types de sources.
Ce quantifieur est donné par l'algorithme de Lloyd-Max, basé sur les conditions d'optimalités définies par Lloyd en 1957.

Algorithme de Lloy-Max:

function d = LM(img, N)
q = max(img)/N;
d = [0:q:N*q];
r = zeros(d);

maxiter = 100;
eps = 1E-6;
img_prec = quantification(img, N);
img_cur = zeros(img);
for iter = 1 : maxiter

//calcul de r
for i = 1:N
indices = find( img >= d(i) & img <= d(i+1) );
r(i) = mean( img(indices) );
end;

//calcul de d
d(2:N) = (r(1:N-1) + r(2:N))/2;
img_cur = apply(img, d);
if eqm(img_prec, img_cur) < eps then

//printf("arret a l'iteration %d\n", iter);
break;
end;
img_prec = img_cur;
end;
endfunction;

function imgQ = apply(img, d)
imgQ = zeros(img);
for i = 1:(length(d)-1)
indices = find( img >= d(i) & img <= d(i+1) );
imgQ(indices) = (d(i)+d(i+1))/2;
end;
endfunction;

2. Quantification d'images en couleur

Alors que la quantification optimale d'une image en N&B, qui est expliquée au dessus, s'apparente à la quantification d'un signal temporel (une dimension), une image en couleurs est un signal en 3 dimensions (3 composantes : rouge, vert, bleu), qu'on ne peut donc pas traiter avec les mêmes méthodes.

2.1 Utilisation d'une palette fixe

Le cas le plus simple est de fixer une palette de couleurs régulièrement espacées dans l'espace que l'on utilisera pour toutes les images indifféremment. Cette solution est loin d'être optimale car elle ne sera (presque) jamais adaptée à l'image encodée ; et on tombera rarement exactement sur le nombre de couleurs désiré sachant qu'on ne peut avoir que des puissances de 3.

Exemple :
On cherche à réduire l'espace colorimétrique “ normal ” de 16 millions de couleurs à 256 couleurs. On veut distribuer les niveaux disponibles équitablement aux 3 couleurs, le nombre de couleurs créées sera le nombre de niveaux choisis puissance 3 (pour les 3 canaux).

La solution qui s'approche le plus de 256 couleurs sans les dépasser est d'avoir 6 niveaux par canal, ce qui nous donne 6^3=216 couleurs (à 7 niveaux par canal, on a 7^3=343 couleurs). On voit que 40 couleurs sont inutilisées.


Palette déséquilibrée

Une solution envisagée pour éviter de perdre des couleurs en équilibrant le nombre de niveaux par canal, tout en gardant une palette fixe, est d'utiliser la façon dont les couleurs sont perçues par l'œil humain pour sacrifier des couleurs au profit d'autres : On perçoit mieux les nuances de vert que de rouge, et mieux les nuances de rouge que de bleu.

Un bon compromis qui est parfois utilisé est la palette comportant 6, 8 et 5 niveaux respectivement pour les couleurs rouge, vert et bleu. Cet arrangement donne 240 couleurs : on voit que l'on est toujours pas à 256 couleurs. Cependant, un désavantage dans le déséquilibrage du nombre de niveaux par canal est qu'on a pas de “ vrai gris ” (les 3 canaux au même niveau). Les 16 couleurs restantes peuvent donc être utilisées pour compenser ce défaut et contenir 16 niveaux de gris.

2.2 Création d'une palette adaptée à l'image

Application d'un traitement N&B à chaque canal

La première solution à laquelle on pourrait penser pour quantifier une image en couleurs, serait de reprendre une des palettes décrites précédemment et d'appliquer un traitement indépendant sur chaque canal pour en optimiser les niveaux utilisés, comme l'algorithme de Lloyd-Max par exemple, mais cette solution est sous-optimale et assez simple à améliorer.

Clustering 3D

En fait, le problème de réduction du nombre de couleurs dans un espace 2D est équivalent à un problème de clustering 3D : il s'agit de regrouper les points dispersés dans un cube 3D en groupes de points “ similaires ”, et de trouver les limites entre ces groupes de façon à limiter la dispersion des points dans un groupe.

Les couleurs du set réduit sont ensuite les moyennes des couleurs des pixels contenus dans chaque cluster.

Il existe de nombreux algorithmes réalisant cette tâche, dont celui de Lloyd-Max, que nous connaissons déjà appliqué aux images en noir et blanc. Le principe est simplement généralisé à 3 dimensions (ou plus) :

  • • On place des centres arbitrairement dans l'espace
  • • Chaque point est rattaché au centre le plus proche
  • • Les centres sont déplacés vers le barycentre des points qui lui sont rattachés
  • • Recommencer

À la fin de l'algorithme, on donne la couleur du centre à tous les points effectivement rattachés à ce centre, avec éventuellement l'application d'un tramage pour améliorer le résultat visuel.

Clustering avec un Octree

Le problème de la méthode itérative de Lloyd-Max est qu'elle prend assez longtemps. Une méthode plus rapide a été développée autour de la partition de l'espace dans un octree.

Un octree est un arbre (au sens de la théorie des graphes) dont chaque nœud possède 8 fils, il sert à découper un espace cubique 3D en sous-cubes : la racine de l'arbre est le cube englobant tout l'espace (ici, tout l'espace colorimétrique), et ses huit fils sont les huit cubes qu'il contient, et ainsi de suite, suivant la profondeur de l'arbre. Son pendant 2D est un quadtree.

L'implémentation consiste à découper l'espace en petits cubes, avec un octree de profondeur 4 ou 5 par exemple, et à se fixer un seuil du nombre de pixels contenus à partir duquel une couleur sera attribuée à un cube. On part alors du dernier niveau, et on remonte l'arbre en additionnant les pixels non attribués dans le père à chaque fois. Quand un cube dépasse le seuil critique, on attribue une couleur (le centre du cube) à tous les pixels contenus, et de même pour les cubes des niveaux supérieurs (le père, le grand-père, etc...), pour lesquels on ignore bien sur les pixels déjà fixés.

Il existe cependant quelques tricks à effectuer pendant l'implémentation de cet algorithme, dont l'implémentation a été décrite plus précisement par Dan Bloomberg dans un papier .

Le défaut de cet algorithme est qu'on a pas de controle direct sur le nombre de couleurs utilisé, que l'on peut seulement approximer. On a donc typiquement quelques couleurs perdues à chaque fois.