Utilisateur:Hydroxypropyl/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. À 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. 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
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. On détermine quel canal (rouge, vert ou bleu) a la plus grande amplitude et on trie 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.
Ce processus est répété itérativement jusqu'à obtenir le nombre de paquets désiré. Le choix du paquet à diviser peut se faire en calculant pour chacun des paquets l'amplitude maximale, puis en comparant celles-ci afin de sélectionner le paquet avec la valeur maximale. Par exemple, si le premier paquet présente une amplitude maximale sur le canal rouge, d'une valeur de 50, et que le second paquet présente une amplitude maximale sur le canal vert, d'une valeur de 100, alors on choisit le deuxième paquet pour cette itération.
Une fois qu'on a obtenu le nombre de paquets désirés, on détermine la palette finale en choisissant comme représentant pour chaque paquet la moyenne des couleurs des pixels.
Notes et références modifier
- (en) « Median Cut Algorithm », dans Encyclopedia of Multimedia, Springer US, (ISBN 978-0-387-78414-4, DOI 10.1007/978-0-387-78414-4_36, lire en ligne), p. 417–418
