La recherche par tri local d'Heckbert

La méthode d'Heckbert [Hec82], basée sur une découpe uniforme de l'espace de couleurs, permet de rejeter a priori des couleurs représentatives qui ne peuvent réaliser le minimum de l'équation (6.14). Heckbert effectue une découpe du cube $\RGB{}$ en $N$ sous cubes. Chaque cube contient une liste de couleurs représentatives pouvant être la couleurs représentative d'une couleur du cube. Chaque liste est définie en calculant la distance $r$ entre la couleur représentative la plus proche du centre du cube et le coin du cube le plus éloigné de la couleur représentative(Figure 6.8). Cette distance donne une limite supérieure de la distance entre une couleur du cube et sa couleur représentative. Donc toute couleur représentative dont la distance au cube est plus grande que $r$ est rejetée de la liste.

Les tests effectués par Heckbert [Hec82] montrent que le nombre de tests nécessaires pour calculer l'image $\Q(c)$ d'une couleur $c$ est d'environ K23, où $K$ est le nombre de couleurs représentatives. Cette méthode permet donc de diminuer la complexité du calcul de la fonction $\Q{}$ sans toutefois changer l'ordre de grandeur du temps de calcul de cette fonction.

Figure 6.8: La recherche par tri local d'Heckbert. La couleur représentative $A$ est la plus proche du centre de la boite courante. La distance entre $A$ et le coin de la boite le plus éloigné défini $r$. La couleur représentative $D$ appartient à la liste du cube alors que $C$ situé à une distance supérieure à $r$ du centre du cube est rejeté de la liste