Problématique

Nous avons vu dans la section 6.3.1 que l'objectif d'un algorithme de quantification est de partitionner le multi-ensemble contenant l'ensemble des couleurs de l'image en un ensemble de multi-ensembles $\{\multip{1},\dots,\multip{K}\}$. Une fois cette partition déterminée, il convient d'afficher l'image avec le nouvel ensemble de couleurs et ce avec une distorsion visuelle minimale. Partant de cette partition, l'on construit un ensemble de couleurs représentatives $\{c_1,\dots,c_K\}$ défini par :

$$\forall i \in \{1,\dots,K\}~~c_i = \mu(C_i).$$

La fonction définie dans la section 6.3.1 associe à chaque couleur de l'image sa couleur représentative la plus proche. On a donc :

$$\Q(c) = Arg Min_{z\in \{c_1,\dots,c_K\}} \Vert z-c\Vert$$ (6.13)

où $Arg~Min f(t)$ représente la valeur d'un paramètre $t$ réalisant le minimum, et $\Vert z-c\Vert$ la norme du vecteur $z-c$ définie dans un espace métrique donné (par exemple la norme euclidienne dans l'espace ).

Cette étape est usuellement appelée l'inversion de table de couleurs. Elle consiste à affecter à chaque couleur de l'image sa couleur la plus proche dans l'ensemble $\{c_1,\dots,c_K\}$. Le calcul de l'ensemble des couleurs plus proche d'une couleur représentative donnée peut s'interpréter comme le calcul du diagramme de Voronoï 3D [Ber94,Aur91,CP95] de germes $\{c_1,\dots,c_K\}$. Les méthodes utilisant explicitement le calcul du diagramme de Voronoï permettent d'obtenir très rapidement la plus proche couleur représentative d'une couleur donnée. Cependant, cette efficacité est compensée par le pré-calcul du diagramme de Voronoi qui induit un sur-coût de calcul important.