Les améliorations de la méthode triviale sont nombreuses:
Poskanzer [Pos91] à proposé d'améliorer la
recherche en utilisant une table de hachage de façon à ne pas
recalculer la couleur représentative d'une couleur déjà
rencontrée. Toutefois cette amélioration reste inefficace pour des
images comportant un nombre important de couleurs différentes. Une
autre approche consiste à approximer la norme par une norme
moins coûteuse en temps de calculs. Chaudhuri et
al. [CCW92] ont proposés la norme
en tant
qu'approximation de la distance euclidienne définie par
. La
norme
d'une couleur
étant définie par:
La recherche peut être encore réduite en utilisant les considérations suivantes [Hod88] :
Si nous utilisons le carré de la norme , ou les normes
ou
la distance entre la couleur d'entrée et une couleur
représentative est définie comme la somme de trois termes. La somme
partielle doit être comparée à la distance minimale avant chaque
addition. Le calcul de distance n'a en effet aucune raison de
continuer si une somme partielle est plus grande que la distance
minimale.
Supposons que les couleurs représentatives sont triés suivant un des axes de coordonné (par ex. le premier) Alors la recherche débute sur la couleur représentative dont la première coordonnée est la plus proche de celle de la couleur d''entrée et continue ensuite dans l'ordre croissant des distances sur la première coordonnée. La recherche se termine quand la distance sur la première coordonnée entre la couleur représentative courante et la couleur d'entrée est plus grande que la distance minimale. Notons que le temps moyen de recherche sera d'autant plus court que la variance sur l'axe des coordonnée choisis sera grand.
Supposons que la couleur représentative courante parcourue
par l'algorithme soit la plus proche de la couleur d'entrée
. Supposons de plus que la distance minimale courante
soit plus petite que la moitié de
. On a donc: