Median cut
Median cut est un algorithme de tri permettant de sélectionner récursivement un ensemble de représentants d'une palette de couleurs donnée[1]. C'est une méthode de quantification de couleur (en). À chaque itération, on sélectionne la dimension de l'espace colorimétrique avec la plus grande amplitude et on utilise sa valeur médiane pour séparer les données en deux paquets[2]. Cette méthode permet de déterminer une palette de couleurs représentative des données initiales en se basant sur la distribution des couleurs et non sur une subdivision uniforme du spectre[1].
Exemple illustratif[modifier | modifier le code]
Soit une image avec un nombre arbitraire de pixels, que l'on souhaite représenter avec une palette de 16 couleurs. On commence par placer tous les pixels (leurs coordonnées RVB) dans un unique paquet, puis on détermine la dimension selon laquelle la partition sera faite. Le critère usuel consiste à calculer l'amplitude des valeurs selon chacun des canaux (rouge, vert, bleu) et à choisir avec l'amplitude maximale[2]. Une autre possibilité consiste à choisir celui présentant la variance maximale[2]. On trie ensuite les pixels du paquet selon ce canal. Par exemple, si le canal sélectionné est le canal rouge, un pixel de coordonnées RVB (16, 125, 125) sera supérieur à un pixel de coordonnées (8, 255, 255), car 16 > 8. Une fois le paquet trié, on calcule la médiane pour ce canal et on place les pixels ayant une valeur supérieure dans un nouveau paquet. L'algorithme tire son nom de l'utilisation de la médiane pour diviser chaque paquet en deux[1].
Ce processus est appliqué récursivement sur chacun des nouveaux paquets jusqu'à obtenir le nombre de paquets désiré[2].
Une fois qu'on a obtenu le nombre de paquets désiré, on détermine la palette finale en choisissant comme représentant pour chaque paquet la moyenne des couleurs des pixels[2].
Notes et références[modifier | modifier le code]
- (en) « Median Cut Algorithm », dans Encyclopedia of Multimedia, Springer US, (ISBN 978-0-387-74724-8, DOI 10.1007/978-0-387-78414-4_36, lire en ligne), p. 417–418
- (en) Paul Heckbert, « Color image quantization for frame buffer display », ACM SIGGRAPH Computer Graphics, vol. 16, no 3, , p. 297–307 (ISSN 0097-8930, DOI 10.1145/965145.801294, lire en ligne, consulté le )
