Améliorations de la méthode triviale

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 $L_2$ par une norme moins coûteuse en temps de calculs. Chaudhuri et al. [CCW92] ont proposés la norme $L_\alpha$ en tant qu'approximation de la distance euclidienne définie par $L_2$. La norme $L_\alpha$ d'une couleur $\col$ étant définie par:

$$\begin{array}{lll} \Vert\col\Vert _\alpha&=&(1-\alpha)\Vert\... ...\vert+\alpha\max_{i\in\{1,2,3\}}\vert\col^j\vert\\ \end{array}$$

D'après les expériences menées par Verevka [VB95] la norme $L_{\frac{1}{2}}$ accélère la recherche de façon significative sans introduire une perte notable de la qualité de l'image résultat.

La recherche peut être encore réduite en utilisant les considérations suivantes [Hod88] :

• Somme partielle :

  Si nous utilisons le carré de la norme $L_2$, ou les normes $L_1$ ou $L_{\frac{1}{2}}$ 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.

• Tri sur une coordonnée (voir exercices sections 6.5.2 et 6.6.2):

  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.

• Distance du plus proche voisin : Donné une couleur représentative $\col_j$ avec $j\in\{1,\dots,K\}$ sa plus proche couleur représentative $\col_{q(j)}$ est définie par :
  $$q(j)=\arg \min_{k\in\{1,\dots,K\},k\neq j} d(\col_j,\col_k)$$

  Supposons que la couleur représentative courante $\col_i$ parcourue par l'algorithme soit la plus proche de la couleur d'entrée $\col$. Supposons de plus que la distance minimale courante $\Sigma_{min}=d(\col,\col_i)$ soit plus petite que la moitié de $d(\col_i,\col_{q(i)})$. On a donc:

  $$\left\{\begin{array}{lll} \Sigma_{min}&=& d(\col,\col_i)\\ \Sigma_{min}&\leq& \frac{1}{2}d(\col_i,\col_{q(i)})\\ \end{array}\right.$$
  Donné n'importe quelle autre couleur représentative $\col_k$:
  $$\begin{array}{lllll} &2\Sigma_{min}&\leq& d(\col_i,\col_{q(i... ... \Rightarrow& \Sigma_{min}&\leq& d(\col,\col_k)\\ \end{array}$$
  L'algorithme d'inversion de table de couleur peut donc retourner directement $\col_i$ puisque aucune autre couleur représentative n peut être plus proche de $\col$ que $\col_i$.