Description de l'algorithme

Description de l'algorithme • Mesure de l'erreur de réduction des couleurs

Ce document décrit comment ImageMagick effectue la réduction des couleurs d'une image. Pour bien comprendre ce qui suit, vous devez connaître les techniques d'imagerie de base ainsi que la structure de données en arbre (tree) et sa terminologie.

Description de l'algorithme

Pour les besoins de l'allocation des couleurs, une image est un ensemble de n pixels, où chaque pixel est un point dans l'espace RGB. L'espace RGB est un espace vectoriel à 3 dimensions, et chaque pixel, p(i), est défini par un triplet ordonné de coordonnées rouge, vert et bleu, (r(i), g(i), b(i)).

Chaque composante de couleur primaire (rouge, vert ou bleu) représente une intensité qui varie linéairement de 0 jusqu'à une valeur maximale, Cmax, qui correspond à la saturation complète de cette couleur. L'allocation des couleurs est définie sur un domaine constitué du cube dans l'espace RGB dont les sommets opposés sont en (0, 0, 0) et (Cmax, Cmax, Cmax). ImageMagick exige Cmax= 255.

L'algorithme fait correspondre ce domaine à un arbre dans lequel chaque nœud représente un cube à l'intérieur de ce domaine. Dans la discussion qui suit, ces cubes sont définis par les coordonnées de deux sommets opposés : le sommet le plus proche de l'origine dans l'espace RGB et le sommet le plus éloigné de l'origine.

Le nœud racine de l'arbre représente le domaine entier, de (0,0,0) à (Cmax, Cmax, Cmax). Chaque niveau inférieur de l'arbre est généré en subdivisant le cube d'un nœud en huit cubes plus petits de taille égale. Cela correspond à couper le cube parent en deux par des plans passant par les milieux de chaque arête.

L'algorithme de base fonctionne en trois phases :

1. Classification
2. Réduction
3. Affectation

Classification

La classification construit un arbre de description des couleurs pour l'image. La réduction réduit l'arbre jusqu'à ce que le nombre qu'il représente soit, au plus, le nombre de couleurs souhaité dans l'image de sortie. L'affectation définit la table des couleurs de l'image de sortie et fixe la couleur de chaque pixel par reclassification dans l'arbre réduit. Notre but est de minimiser les écarts numériques entre les couleurs d'origine et les couleurs quantifiées. Pour en savoir plus sur l'erreur de quantification, voir Mesure de l'erreur de réduction des couleurs.

La classification commence par initialiser un arbre de description des couleurs d'une profondeur suffisante pour représenter chaque couleur d'entrée possible dans une feuille. Cependant, il est irréaliste de générer un arbre de description des couleurs entièrement formé lors de la phase de classification pour des valeurs réalistes de Cmax. Si les composantes de couleur de l'image d'entrée sont quantifiées avec une précision de k bits, de sorte que Cmax = 2^k-1, l'arbre aurait besoin de k niveaux sous le nœud racine pour permettre de représenter chaque couleur d'entrée possible dans une feuille. Cela devient prohibitif car le nombre total de nœuds de l'arbre :

total nodes = 1+Sum(8^i), i=1,k

For k=8,
nodes = 1 + (8^1+8^2+....+8^8)
      = 1 + 8(8^8 - 1)/(8 - 1)
      = 19,173,961

Par conséquent, pour éviter de construire un arbre entièrement peuplé, ImageMagick :

1. n'initialise les structures de données des nœuds qu'au fur et à mesure des besoins ;

2. choisit une profondeur maximale pour l'arbre en fonction du nombre de couleurs souhaité dans l'image de sortie (actuellement le logarithme en base deux de Cmax).

   For Cmax=255, maximum tree depth = log2(256) = 8

Un arbre de cette profondeur permet généralement la meilleure représentation de l'image source avec la vitesse de calcul la plus rapide et la moindre quantité de mémoire. Cependant, la profondeur par défaut est inadaptée à certaines images. C'est pourquoi l'appelant peut demander une profondeur d'arbre spécifique.

Pour chaque pixel de l'image d'entrée, la classification parcourt l'arbre de description des couleurs vers le bas depuis la racine. À chaque niveau de l'arbre, elle identifie le nœud unique qui représente un cube dans l'espace RGB contenant la couleur du pixel. Elle met à jour les données suivantes pour chacun de ces nœuds :

n1

nombre de pixels dont la couleur est contenue dans le cube RGB que ce nœud représente ;

n2

nombre de pixels dont la couleur n'est représentée dans aucun nœud à une profondeur inférieure dans l'arbre ; initialement, n2=0 pour tous les nœuds sauf les feuilles de l'arbre.

Sr,Sg,Sb

sommes des valeurs des composantes rouge, vert et bleu pour tous les pixels non classés à une profondeur inférieure. La combinaison de ces sommes et de n2 caractérisera finalement la couleur moyenne d'un ensemble de pixels représenté par ce nœud.

E

le carré de la distance dans l'espace RGB entre chaque pixel contenu dans un nœud et le centre du nœud. Cela représente l'erreur de quantification d'un nœud.

Réduction

La réduction élague l'arbre de façon répétée jusqu'à ce que le nombre de nœuds avec n2 > 0 soit inférieur ou égal au nombre maximal de couleurs autorisé dans l'image de sortie. À chaque itération sur l'arbre, elle sélectionne pour l'élagage les nœuds dont la valeur E est minimale et fusionne leurs statistiques de couleur vers le haut. Elle utilise un seuil d'élagage, Ep, pour régir la sélection des nœuds comme suit :

Ep = 0
while number of nodes with (n2 > 0) > required maximum number of colors
   prune all nodes such that E <= Ep
   Set Ep  to minimum E in remaining nodes

Cela a pour effet de minimiser toute erreur de quantification lors de la fusion de deux nœuds.

Lorsqu'un nœud à élaguer possède une descendance, la procédure d'élagage s'invoque récursivement afin d'élaguer l'arbre des feuilles vers le haut. Les valeurs de n2, Sr, Sg et Sb dans un nœud en cours d'élagage sont toujours ajoutées aux données correspondantes du nœud parent. Cela conserve les caractéristiques de couleur du nœud élagué pour un calcul de moyenne ultérieur.

Pour chaque nœud, il existe n2 pixels pour lesquels ce nœud représente le plus petit volume dans l'espace RGB contenant les couleurs de ces pixels. Lorsque n2 > 0, le nœud définira de manière unique une couleur dans l'image de sortie. Au début de la réduction, n2 = 0 pour tous les nœuds sauf les feuilles de l'arbre qui représentent les couleurs présentes dans l'image d'entrée.

L'autre comptage de pixels, n1, indique le nombre total de couleurs dans le volume cubique que le nœud représente. Cela inclut n1 - n2 pixels dont les couleurs devraient être définies par des nœuds à un niveau inférieur de l'arbre.

Affectation

L'affectation génère l'image de sortie à partir de l'arbre élagué. L'image de sortie se compose de deux parties :

1. Une table des couleurs, qui est un tableau de descriptions de couleurs (triplets RGB) pour chaque couleur présente dans l'image de sortie.
2. Un tableau de pixels, qui représente chaque pixel comme un indice dans le tableau de la table des couleurs.

Tout d'abord, la phase d'affectation effectue un passage sur l'arbre de description des couleurs élagué pour établir la table des couleurs de l'image. Pour chaque nœud avec n2 > 0, elle divise Sr, Sg et Sb par n2. Cela produit la couleur moyenne de tous les pixels qui ne se classent pas plus bas que ce nœud. Chacune de ces couleurs devient une entrée dans la table des couleurs.

Enfin, la phase d'affectation reclassifie chaque pixel dans l'arbre élagué pour identifier le nœud le plus profond contenant la couleur du pixel. La valeur du pixel dans le tableau de pixels devient l'indice de la couleur moyenne de ce nœud dans la table des couleurs.

Les preuves empiriques suggèrent que les distances dans des espaces colorimétriques tels que YUV ou YIQ correspondent plus étroitement aux différences de couleur perceptuelles que les distances dans l'espace RGB. Ces espaces colorimétriques peuvent donner de meilleurs résultats lors de la réduction des couleurs d'une image. Ici, l'algorithme est tel que décrit, sauf que chaque pixel est un point dans l'espace colorimétrique alternatif. Par commodité, les composantes de couleur sont normalisées dans la plage de 0 à une valeur maximale, Cmax. La réduction des couleurs peut alors se dérouler comme décrit.

Mesure de l'erreur de réduction des couleurs

Selon l'image, l'erreur de réduction des couleurs peut être évidente ou invisible. Les images à hautes fréquences spatiales (telles que les cheveux ou l'herbe) montreront beaucoup moins l'erreur que les images comportant de grandes zones ombrées en douceur (telles que les visages). Cela s'explique par le fait que les bords de contour à haute fréquence introduits par le processus de réduction des couleurs sont masqués par les hautes fréquences présentes dans l'image.

Pour mesurer la différence entre l'image d'origine et l'image à couleurs réduites (l'erreur totale de réduction des couleurs), ImageMagick somme, sur tous les pixels d'une image, le carré de la distance dans l'espace RGB entre chaque valeur de pixel d'origine et sa valeur à couleurs réduites. ImageMagick affiche plusieurs mesures d'erreur, notamment l'erreur moyenne par pixel, l'erreur moyenne normalisée et l'erreur maximale normalisée.

La mesure d'erreur normalisée peut être utilisée pour comparer des images. En général, plus l'erreur moyenne est proche de zéro, plus l'image quantifiée ressemble à l'image source. Idéalement, l'erreur devrait être de nature perceptuelle, puisque l'œil humain est le juge final de la qualité de la quantification.

Ces erreurs sont mesurées et affichées lorsque les options -colors et -verbose sont spécifiées sur la ligne de commande magick :