:: Yves Jacolin :: Ludovic Granjon :: Softlibre :: OSGeo-fr ::
"Quand on veut reprendre avec utilité, et montrer à un autre qu'il se trompe, il faut observer par quel côté il envisage la chose, car elle est vraie ordinairement de ce côté-là, et lui avouer cette vérité, mais lui découvrir le côté où elle est fausse." Pascal, Pensées Br. 9, Lafuma 5.

Retour vers le sommaire

Chapitre 21 Quantification

Cette section décrit de quelle manière ImageMagick réduit les couleurs d'une image. Pour pleinement comprendre cette section, vous devez avoir une connaissance de base des techniques d'images et de la structure des données en arborescence et leur terminologie.

21.1 Description de l'algorithme

Afin d'attribution de couleur, 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éfinie par des triples coordonnées de rouge, vert et bleu (r(i), g(i), b(i)).

Chaque composant de couleur primaire (rouge, vert ou bleu) représente une intensité qui varie linéairement de 0 à la valeur maximale, Cmax, qui correspond à la pleine saturation de cette couleur. Les allocations de couleur sont définie sur un domaine comprenant le cube dans l'espace RGB avec des sommets opposés à (0, 0, 0) et (Cmax, Cmax, Cmax). ImageMagick nécessite Cmax=255.

L'algorithme relie ce domaine dans une arborescence dans laquelle chaque noeud représente un cube dans ce domaine. Dans les paragraphes suivants, ces cubes sont définie 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 loin de l'origine.

Le noeud racine de l'arborescence représente le domaine entier, (0,0,0) à (Cmax, Cmax, Cmax). Chaque niveau inférieur dans l'arborescence est généré en divisant un noeud du cube en huit cubes plus petits de taille égale. Cela correspond à couper en deux le cube parent avec des plans passant à travers le milieu de chaque bord.

L'algorithme de base opère en trois phases :

  1. Classification
  2. Réduction
  3. Tâche

21.1.1 Classification

La Classification construit une arborescence de la description des couleurs pour l'image. La réduction détruit l'arborescence jusqu'à ce que le nombre qu'il représente, au plus, soit le nombre de couleurs désirées dans l'image de sortie. La Tâche définie la carte de couleur de l'image de sortie et définie chaque couleur du pixel en le reclassant dans l'arbre réduit. Le but est de minimiser les anomalies numériques entre les couleurs originales et les couleurs réduites. Pour en apprendre plus sur les erreurs de réduction, voyez le chapitre T.II Mesurer l'erreur de réduction de couleurs.

La classification commence par l'initialisation de l'arborescence de la description des couleurs de profondeur suffisante pour représenter chaque couleur possible en entrée dans une “feuille” de l'arbre. Cependant, il est impossible de générer un arbre de description de couleur complètement formé dans la phase de classification pour des valeurs réaliste de Cmax. Si les composants de couleur dans l'image en entrée sont quantifiée à une précision de k-bite(s), de sorte que Cmax = 2k-1, l'arbre aura besoin de k niveau(x) en dessous du noeud racine pour permettre la représentation de chaque couleur possible en entrée dans la « feuille » de l'arbre. Cela devient prohibitif à cause du nombre total de noeud de l'arbre :

formule 1

Donc, pour éviter de construire un arbre pleinement peuplé, ImageMagick :

  1. initialise les structures de données pour les noeuds seulement quand c'est nécessaire ;
  2. choisit une profondeur maximal pour l'arbre comme une fonction du nombre désiré des couleurs dans l'image en sortie (un algorithme de base deux de Cmax).

formule 2

Un arbre de cette profondeur permet en général la meilleur représentation de l'image source avec le meilleur taux de vitesse de calcul et la plus basse utilisation mémoire. Cependant, la profondeur par défaut est inappropriée pour certaine image. Donc, vous pouvez demander une profondeur d'arbre spécifique.

Pour chaque pixel dans l'image en entrée, la classification scanne vers le bas à partir de la racine de l'arbre de description de couleur. À chaque niveau de l'arbre, il identifit le noeud simple qui représente un cube dans l'espace RGB contenant la couleur du pixel. Il met à jour les données qui suivent pour chaque noeud :

noeud : n1 : nombre de pixels dont la couleur est contenu dans le cube RGB dont le noeud représente ; n2 : nombre de pixels dont la couleur n'est pas représentée dans le noeud à une profondeur plus basse dans l'arbre ; initialement, n2=0 pour tous les noeuds sauf les feuilles de l'arbre. Sr,Sg,Sb somme des valeurs de composition de rouge (red), vert (green) et bleu (blue) pour tous les pixels non classifiés à une profondeur plus basse. La combinaison de ces sommes et de n2 permettra de caractériser la couleur moyenne de l'ensemble des pixels représenté par ce noeud. E : distance au carré dans l'espace RGB entre chaque pixel contenu dans le noeud et le centre du noeud. Cela représente l'erreur de quantification pour un noeud.

21.1.2 Réduction

La réduction diminue à plusieurs reprises l'arbre jusqu'à ce que le nombre de noeuds avec n2 > 0 soit inférieure ou égal au nombre maximal de couleurs autorisées dans l'image en sortie. Dans une itération donnée sur l'arbre, il sélectionne ces noeuds dont la valeur E est minimale pour la taille et fusionne leurs statistiques de couleur vers le haut. Il emploit un seuil de taille, Ep, pour régir le choix de noeud comme suit :

  1. Ep = 0
  2. while number of nodes with (n2 > 0) > required maximum number of colors
  3. prune all nodes such that E ⇐ Ep
  4. Set Ep to minimum E in remaining nodes

Cela a pour effet de minimiser les erreurs de quantification lors de la fusion de deux noeud ensemble.

Quand un noeud à tailler possède des enfants, la procédure pour la taille s'invoque récursivement dans le but de tailler l'arbre de la feuille vers le haut. Les valeurs de n2, Sr, Sg et Sb dans un noeud qui doit être taillé a toujours été ajouté aux données correspondantes dans ce noeud parent. Cela garde les caractéristiques de la couleur du noeud taillé pour en faire une moyenne plus tard.

Pour chaque noeud, n2 pixels existe pour lequel ce noeud représente le volume le plus petit dans l'espace RGB contenant ces couleurs de pixels. Quand n2 > 0 le noeud définira uniquement une couleur dans l'image en sortie. Au début de la réduction, n2 = 0 pour tous les noeuds sauf les feuilles de l'arbre qui représente une couleur présente dans l'image en entrée.

Le compte des autres pixels, n1, indique le nombre total de couleur dans le volume du cube que le noeud représente. Cela inclut n1 - n2 pixels dont la couleur doit être définie par les noeuds à un plus bas niveau dans l'arbre.

21.1.3 Affectation

L'affectation génère l'image en sortie à partir de l'arbre taillé. L'image en sortie consiste à deux parties :

  1. Une carte des couleurs, qui est un tableau de descriptions de couleurs (Triple RGB) pour chaque couleur présenté dans l'image en sortie.
  2. Un tableau de pixel, qui représente chaque pixel comme un index dans le tableau de la carte des couleurs.

D'abord, la phase d'affectation passe une première fois sur l'arbre de description des couleurs enlevées pour établir la carte de couleurs de l'image. Pour chaque noeud avec n2 > 0, elle divise Sr, Sg et Sb par n2. Cela produit la couleur moyenne de tous les pixels qui ne sont pas classé plus bas que ce noeud. Chacun de ces noeuds devient une entrée dans la carte de couleurs.

Enfin, la phase d'affectation classifie chaque pixel dans l'arbre taillé pour identifier le noeud le plus éloigné contenant la couleur du pixel. La valeur du pixel dans le tableau de pixels devient l'index de la couleur moyenne du noeud dans la carte de couleur.

L'évidence empirique suggère que les distances dans des espace de couleurs tels que YUV, ou YIQ correspondent aux différences perceptibles de couleur plus étroitement que des distances dans un espace RVB. Ces espaces de couleurs peuvent donner de meilleur résultats lors d'une réduction de couleurs.

Ici l'algorithme est comme il a été décris sauf que chaque pixel est un point dans l'espace de couleurs alternatif. Pour plus de confort, les composants de couleur sont normalisés de 0 à la valeur maximale, Cmax. La réduction de couleur peut alors être procédé comme décrit.

21.2 Mesurer l'erreur de réduction de couleurs

En fonction de l'image, l'erreur de réduction de couleurs peut être évidente ou invisible. Les images avec des fréquences spatiale élevé (tels que les cheveux ou l'herbe) affichera beaucoup moins d'erreur que les images avec de larges zones légèrement ombrées (tel que les visages). Cela est dû au fait que les contours des bords en haute fréquence introduit par le processus de réduction de couleurs sont maqués par les hautes fréquences de l'image.

Pour mesurer la différence entre l'originale et l'image de couleurs réduites (l'erreur de réduction de couleurs), ImageMagick ajoute pour tous les pixels dans une image la distance au carré dans l'espace RGB entre la valeur du pixel original et sa valeur de couleur réduite. ImageMagick affiche plusieurs mesures d'erreur incluant l'erreur moyenne par pixel, l'erreur moyenne normalisée et l'erreur maximal normalisée.

La mesure de l'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 à la source de l'image. Idéalement, l'erreur doit être basé sur la perception, puisque l'oeil humain est le juge final de la qualité de la quantification.

Ces erreurs sont mesurées et affichées quand les options -colors et -verbose sont spécifiées dans la commande convert :

L'erreur moyenne par pixel [mean error per pixel] est l'erreur moyenne pour n'importe quel pixel simple dans l'image.

L'erreur du carré moyen normalisée [normalized mean square error] est l'erreur de quantification du carré moyen normalisé pour chaque pixel dans l'image. Cette distance est normalisé dans un domaine de 0 à 1. Il est indépendant du domaine de valeur du rouge, vert et bleu dans l'image.

L'erreur du carré maximale normalisée [normalized maximum square error]est la plus grande erreur de quantification du carré normalisé pour un pixel simple dans l'image. Cette distance est normalisé dans un domaine de valeur de rouge, vert et bleu dans l'image.

Contact - Information et copyright - Statistique

Recent changes RSS feed Creative Commons License Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki