La méthode de Thomas

On peut aussi diminuer l'ordre de complexité de la fonction en utilisant un diagramme de Voronoi 3D [Tho91]. Chaque cellule de Voronoi $V_i$ est alors définie comme l'ensemble des points de l'espace de couleurs plus proches de la couleur $c_i$ que de toute autre couleur représentative. Ce type de méthode permet de pré-calculer de façon incrémentale l'ensemble des valeurs de la fonction $\Q{}$ pour tout point discret $c$ de l'espace de couleurs. L'inconvénient majeur de cette méthode est que l'on effectue bien plus de calculs que nécessaire. En effet, si l'on travaille dans l'espace de couleurs , le pré-calcul de la fonction $\Q{}$ impose d'initialiser $256^3 \approx 16.000.000$ valeurs. Si l'image à quantifier a une taille de $256\star256$, nous aurons besoin de tester la valeur de la fonction $\Q{}$ pour au plus $256^2 \approx 65.000$ valeurs différentes. Cette méthode peut donc nécessiter de nombreux calculs inutiles. De plus, le stockage de l'ensemble des valeurs de la fonction $\Q{}$ requiert, si l'on utilise 256 couleurs représentatives, $16$ méga octets de mémoire. Afin de diminuer la place mémoire requise par l'algorithme on effectue généralement une pré-quantifiquation en ne prenant en compte que les 5 bits de poids fort de chaque composante $(R,G,B)$. Cette méthode diminue la place mémoire requise par l'algorithme et le nombre de valeurs à calculer. Toutefois, malgré cette simplification, le pré-calcul de la fonction nécessite environ $24$ secondes sur une station de travail SUN 3/60 [Tho91]. Sachant que l'obtention d'une partition de l'espace de couleur s'effectue généralement en moins d'une minute, le sur-coût de calcul qu'implique le pré-calcul de la fonction est important.