Au début de l'histoire, le truc qui m'a fait rêver c'est l'outil in the mod de Dr Woohoo qui permet de récupérer une palette de couleurs à partir d'une image.
Alors moi tout naïf je me dis "ouai c'est facile, c'est tout comme réduire le nombre de couleurs de l'image" et je repense à nicoptère qui a fait un truc qui y ressemble.
Sauf qu'en fait ce que je veux (va savoir pourquoi) c'est récupérer un nombre précis de couleurs. Alors j'en parle avec Nicoptère et là il me dit "ah mais ça a rien à voir (pov' nul), toi c'est une posterisation que tu veux faire! ". Ce à quoi google me répond "la posterisation c'est ça". Ah bein oui, c'est un beau chien, mais là c'est le contraire de ce que je veux.
C'est quand même un bon début parcequ'en fouinant dans cette direction je découvre le median cut filter et même comment améliorer l'algorithme. Bien sûr tout celà n'est pas à confondre avec avec l'autrement plus compliqué mean shift filter.
Bon, trop bien! Cette fois c'est le bon.
Là je fais une pause dans l'histoire, juste pour dire que si tu veux obtenir des belles couleurs d'une belle image, tu peux tout de suite aller chez soulwire voir ces articles:
couleurs moyennes et extraire une palette de couleurs, c'est plus simple et ça marche mieux.
Par contre tu vas rater la partie intéressante de l'histoire.
Pour en revenir au median cut filter, si tu te disais "Chouette, un filtre! on va sortir PixelBender" tu te trompes, ça marchera pas. C'est pas comme le BlurFilter ou ColorMatrixFilter, qui traitent chaque pixel pour les redéfinir en fonction de leurs voisins ou de paramètres quelconques. Là c'est l'espace colorimétrique de l'image qu'on va tripoter.
L'espace colorimétrique est un cube dans lequel chaque point est une couleur déterminée par sa position sur les axes R, G, B.
Maurice de Vlaminck a peint Les arbres rouges en 1906. C'est une huile sur toile de 65 x 81 cm et tu peux le voir au Centre Pompidou à Paris. Ici il est légèrement recadré.
Ici c'est toujours le Vlaminck mais représenté dans l'espace colorimétrique. Cette fois il n'est pas recadré. Les résultats sont très différents selon les images.
On commence par mettre le tableau dans une boite. En vrai une boite ce sera juste une liste de pixels.
Ensuite on regarde quel est le côté le plus long. Pour ça il suffit de prendre les valeurs extrèmes de rouge, vert et bleu dans la liste de pixels. On va alors trier la liste selon leur valeur de rouge si par exemple c'est dans le vert qu'on a le plus d'amplitude. Il n'y a plus qu'à diviser notre liste en deux parts égales de façon à obtenir deux boites contenant le même nombre de pixels.
On recommence la dernière étape avec la boite qui a le plus long côté jusqu'à avoir autant de boites qu'on veut de couleurs. On obtient la palette en récupérant la couleur moyenne de chaque boite. Après pour reconstituer l'image il faudrait faire une posterisation. Moi je me contente d'attribuer aux pixels la couleur de la boite où ils sont, ça revient presque au même.
Et voilà des images reconstituées avec 2, 4, 8 et 32 couleurs et les palettes correspondantes :
À moins de 20 couleurs les palettes sont loin de ce qu'on pourrait attendre.
On a vu que l'algorithme nécessite que les pixels d'une boite soient triés lors de la division de celle-ci.
Trier un Vector c'est simple avec la methode sort(). Ça prend en paramètre une fonction de notre choix c qui est top pour trier des éléments comme on veux. L'inconvénient c'est que c'est lent. Trop lent pour trier tous les pixels d'une image.
Voilà le test de base avec un Vector.
//nombre de valeurs à trier
var n:int = 20000;
//Vector contenant les valeurs à trier
var values:Vector.<int> = new Vector.<int>(n, true);
//valeur maximale contenue dans le Vector (minimum 0)
var valMax:int = 0xFF;
//remplissage du Vector avec des valeurs aléatoires
for(var i:int = 0; i< n; i++)values[i] = Math.random() * valMax;
var t:int = getTimer();
//tri
values.sort(function(v1:int, v2:int){return v1 - v2;});
trace(getTimer() - t);
chez moi j'ai :
72 ms pour 10 000 éléments
3 900 ms pour 100 000 éléments
14 500 ms pour 200 000 éléments
après on dépasse les 15 secondes et ça plante.
Une image de 500x500 fait déjà 250 000 pixels.
Heureusement les algorithmes de tri sont très nombreux et le counting sort m'a paru sympa.
Si on reprend le test de tout à l'heure
function countingSort(a:Vector.<int>, k:int):Vector.<int>{
var n:int = a.length;
var b:Vector.<int> = new Vector.<int>(n, true);
var c:Vector.<int> = new Vector.<int>(k, true);
for(var i:int = 0; i< n; i++){ c[a[i]] = c[a[i]] + 1; }
for(i = 1; i < k; i++){ c[i] = c[i] + c[i - 1]; }
for(i = n - 1; i >= 0; i--){
b[c[a[i]]-1] = a[i];
c[a[i]] = c[a[i]] - 1;
}
return b;
}
var n:int = 100000;
var values:Vector.<int> = new Vector.<int>(n, true);
var valMax:int = 0xFF;
for(var i:int = 0; i< n; i++){
values[i] = Math.random() * valMax;
}
var t:int = getTimer();
values = countingSort(values, valMax + 1);
trace(getTimer() - t);
2ms pour 10 000 éléments
17ms pour 100 000 éléments
1600ms pour 10 000 000 éléments
Bon, en gros pour 50 fois plus d'éléments ça met à peu près 10 fois moins de temps. Pas mal non?
Bien sûr comme tu ne crois pas à la magie, tu sais qu'il y a des inconvénients.
En fait là ça marche bien parceque les valeurs à trier sont des entiers compris entre 0 et 255
Avec des nombre décimaux ça ne marcherai pas. Et avec des nombres négatifs il faudrait adapter un peu.
Avec des valeurs issues d'un large interval c'est la mémoire qui prendrait un coup.
Et puis il faut réécrire la fonction pour chaque type de Vector
Le quickSort est plus pratique pour ces cas là, mais peut-être un peu moins rapide dans le cas des canaux rgb.
La leçon c'est que le median cut filter ça sert peut-être à rien mais au moins maintenant je sais mieux trier mes objets