Les méthodes par popularité

Les méthodes de quantification par popularité sont historiquement parmi les premières à avoir été employées. Ces méthodes sélectionnent les $K$ couleurs de plus grande fréquence de l'image (voir par exemple [Hec82]). Ces méthodes sont rapides et fonctionnent correctement pour un grand nombre d'images. Elles ont toutefois deux inconvénients majeurs:

Tout d'abord le nombre de couleurs affichables est bien plus grand que le nombre de couleurs d'une image (voir Section 5.2.2). De nombreuses cellules de l'histogrammes $3D$ sont donc affectées de valeurs faibles ou nulles. Outre des temps de calculs prohibitifs, cette dernière propriété remet en cause la pertinence des couleurs sélectionnées par l'algorithme. En effet, peut on dire qu'une couleur de fréquence $4$ ou $5$ est réellement représentative de l'ensemble des couleurs de l'image ? Un façon simple de remédier à ce problème est d'effectuer une pré quantification sur l'espace couleur. Si nous utilisons l'espace $RGB$ on peut par exemple ne conserver que les $5$ bits de poids fort de chaque composante.

Le second problème inhérent à ce type de méthode est que les couleurs de fréquence élevées ont tendance à être regroupées dans les même régions de l'espace couleur. Ceci conduit les méthodes par popularité à sur-représenter certaines partie de l'espace.

Braudeway [Bra86] résout partiellement ces deux problèmes en:

1. Effectuant une pré-quantification de l'espace couleur en $L^3$ sous cube de taille $\frac{M}{L}$ où $M$ est la valeur maximale d'une composante correspondant à une couleur affichable. Notons que ce type de méthode fonctionne particulièrement bien pour des espaces cubiques type $RGB$. On obtient donc un multi-ensemble:
   $$(C,f)=\{(c_1,f),\dots,(c_{L^3},f)\}$$
   où chaque élément $c_i$ est le centre d'un sous cube et $f(c_i)$ représente la somme des fréquences des couleurs tombant dans ce sous cube.

2. Sélectionnant les $K$ couleurs représentative par l'itération des deux étapes suivantes:
   1. Sélectionner la couleur $c$ de plus grande fréquence du multi-ensemble.

   2. multiplier la fréquence de chaque couleur $c'$ du multi-ensemble par un facteur $(1-e^{\alpha d(c,c')})$ où $d(c,c')$ est la distance euclidienne entre $c$ et $c'$ et $\alpha$ un facteur de pondération.