La méthode de Friedman

Il est également possible d'approcher le calcul de la fonction $\Q{}$ en affectant à chaque couleur $c$ le barycentre $c_i$ de son ensemble englobant $C_i$. Cette méthode proposée par Friedman et al. [BFF77] est utilisée par la majorité des algorithmes de quantification. L'approximation des cellules de Voronoi $\{V_1,\dots,V_K\}$ par les ensembles $\{C_1,\dots,\C_K\}$ utilise le fait que la partition de l'espace de couleur en cellules de Voronoi est celle qui minimise l'erreur quadratique pour un ensemble de couleurs représentatives donné. La partition produite par les algorithmes de quantification étant proche de celle qui minimise l'erreur de partition, chaque ensemble $C_i$ est proche de la cellule de Voronoi $V_i$ de centre $c_i$ où $c_i$ est le barycentre de $C_i$. Les algorithmes utilisant ce type de méthode utilisent généralement la structure de données utilisée pour stocker la partition de l'ensemble des couleurs de l'image. Par exemple, les méthodes de quantification descendantes stockent généralement l'ensemble des ensembles formant la partition à l'aide d'un arbre binaire. L'utilisation de cet arbre permet alors de retrouver l'ensemble contenant une couleur donnée en _2(K) tests. Toutefois, ce type de méthode ne peut s'appliquer que lorsque l'étape d'inversion de la table de couleur suit immédiatement l'étape de quantification. Dans le cas contraire, reproduire les structures intermédiaires utilisées par les algorithmes de quantification est souvent plus coûteux que la méthode d'Heckbert [Hec82] ou la recherche exhaustive.