L'algorithme Median-cut et une variante

Algorithme Median Cut

Dans cet algorithme, implémenté par Heckbert en 1982, l'espace RGB des couleurs est subdivisé de manière récursive en boîtes rectangulaires de plus en plus petites, separées par des plans parallèles aux axes, et contenant un nombre égal de couleurs.

On distingue deux phases:

Classification :
La boîte initiale est une boîte rectangulaire dans l'espace R,G,B contenant toutes les couleurs de l'image initiale.
A chaque étape :
- On cherche pour chaque boîte sa dimension la plus grande selon R, G ou B.
- On prend la boîte ayant la plus grande dimension. On la coupe en deux par un plan perpendiculaire à l'axe choisi, au point médian, c'est à dire de facon à ce que chaque nouvelle boîte contienne le même nombre de couleurs.
- On recommence jusqu'à ce que le nombre de boîtes soit egal au nombre de couleurs desiré pour la nouvelle palette.

Affectation :
On affecte à chaque pixel de l'image initiale la couleur représentant la boîte dans laquelle se trouve la couleur initiale. La couleur représentant une boîte a pour composantes RGB les moyennes des composantes de toutes les couleurs contenues dans la boîte.

Variante basée sur la variance (Variance based)

Pour une meilleure optimisation, Heckbert propose une méthode basée sur la variance pour découper les boîtes en deux. Celle-ci a ete implémentée par Wu en 1990.
Le schéma de l'algorithme est similaire. Mais le point par lequel on fait passer le plan coupant la boîte en deux est tel que la somme des variances projetées sur l'axe soit minimale.

Comparez Médian-Cut et :

sa variante à minimisation de variance : Bill le Déjanté.
sa variante, Octree et les K-Moyennes locales avec Klimt.
Octree avec Lena.
un réseau neuronal avec un billard comme support.

Pour plus d'infos...

Color Image Quantization for Frame Buffer Display de Paul S. Heckbert.
Voir l'article "Color Quantization by Dynamic Programming and Principal Analysis" de Xiaolin Wu, ACM Transactions on Graphics, Vol. 11, No. 4, Octobre 1992, 348-372.
Un exemple d'implémentation de Médian-cut en C.
L'implémentation de la variante de Xiaolin Wu, quantizer.c, qui minimise la variance.

Revenir à l'index.