Réduction de couleur complexe - Page 1

Bonjour tout le monde ^^

J'aimerais faire une réduction de couleurs un peu plus compliquée que d'habitude.
J'ai une image en couleurs vraies (32 bits) et je dois la découper en morceaux d'une certaine taille (8x8 par défaut). Chacun de ces morceaux de 8x8 référencie une image 4 bits (c'est-à-dire 16 couleurs, dont une est transparente), et chacun de ces morceaux peut choisir l'une des palettes système (il y en a 16 par défaut, mais on pourra régler).
Ainsi, on a 256 couleurs, sauf que seulement 16 ne peuvent être affichées simultanément dans un bloc de 8x8.
Le but est de générer les 16 meilleures palettes de 16 couleurs pour l'image, et de les associer aux différents blocs pour avoir la meilleure qualité d'image possible.
Cela peut sembler simple au premier abord, mais ça ne l'est pas tant que ça, car chaque bloc ne peut utiliser QUE les couleurs de la palette à laquelle il est associé. Donc si un morceau d'image est rouge, on sera tenté d'y coller une palette rouge, mais si cet objet est une flèche par exemple, il faudra tenir compte que dans les bords il y a une autre couleur (l'objet n'est pas forcément rectangulaire et ne fait pas forcément 8x8). Et il y a beaucoup plus de blocs que de palettes, donc il faut créer des palettes réutilisables et adaptées à tout.

J'ai déjà réfléchi et essayé quelques algos, mais le résultat est plutôt mauvais. Je ne les posterai pas ici car mon post est déjà assez gros mais si vous voulez je le ferai.

Donc voilà, si vous avez des idées à me faire partager, ce serait très sympa et utile. Merci d'avance ^^

PS: pour ceux qui n'auraient pas reconnu, le but est de générer des maps optimisées (avec tilesets 4 bits & palettes) pour des consoles de type SNES, GBA, Mega Drive, Game Gear, DS, etc.

Brunni :
PS: pour ceux qui n'auraient pas reconnu, le but est de générer des maps optimisées (avec tilesets 4 bits & palettes) pour des consoles de type SNES, GBA, Mega Drive, Game Gear, DS, etc.

Juste un truc, au moins la moitié des consoles cité font bcp mieux

Wé mais tu bourres la mémoire vidéo avec des tilesets / bitmaps 8 bits (ou plus), d'où l'intérêt du 4 bits.

./1 > regarde le blog d'Orion_, il me semble qu'il a fait des trucs de ce genre

Je ne connais pas l'adresse de son blog, mais si tu parles de son site alors je ne vois rien à ce propos.

blogs/blog.php?id=18&i=256 et blogs/blog.php?id=18&i=278

Merci beaucoup, ça a l'air d'être exactement ça, mais pas de lien pour télécharger et l'image est down.
Je serais curieux de voir le résultat et de savoir quelle méthode il a utilisée...
Je vais reposter dans un moment avec la méthode que j'ai testée jusqu'à maintenant, et pourquoi elle est pas bien, peut-être que vous pourrez me donner des idées d'amélioration
Merci en tous cas

Comme promis, voici une description de la méthode que j'ai utilisée:

A la base j'ai une routine, qui s'occupe de créer une palette optimisée (16 couleurs) pour un morceau d'image (tile). Elle me renvoie aussi un score pour cette image, qui est l'addition des défauts de l'image (différence entre deux couleurs: racine(rdiff^2+vdiff^2+bdiff^2) où rvbdiff est la différence entre le pixel utilisant la palette et la vraie couleur, et y'a sûrement mieux comme formule d'ailleurs, je serais intéressé).
La première étape consiste à générer des palettes. D'abord, je crée une première palette en prenant une tile "au hasard" (en réalité, celle qui a le plus de couleurs différentes) dans l'image et en la passant à la fonction de création de palette optimisée.
Ensuite, j'essaie de caser toutes les tiles du dessin dans cette palette. Celle qui passe le moins bien (plus mauvais score) reçoit une palette pour elle. Ensuite, j'essaie de caser toutes les tiles dans ces deux palettes, et celle qui rentre le moins bien reçoit elle-aussi une palette, etc.
Deuxième étape, donner la meilleure palette à chacune des tiles. Pour ça, très simple, pour chaque tile, j'essaie de la caser dans une des palette et je regarde dans laquelle elle passe le mieux (meilleur score) et je la lui assigne.

Le résultat est globalement moyen, et pour cause, voici un exemple:
Prenons une image utilisant des nuances de vert, avec un cercle utilisant des nuances de bleu (comme un lac dans un pré par exemple). En premier, une palette verte sera créée. On essayera ensuite d'y caser nos tiles, et forcément le bleu ne passera pas. Problème: la partie la plus éloignée (celle qui méritera le plus selon les stats de recevoir une palette pour elle) est forcément celle qui ne contient pas de vert, donc le centre du cercle (tous les pixels sont faux à ce moment là). Résultat on se retrouve avec une palette complètement bleue générée à partir de cette tile, et dans les bords du lac, il ne va pas savoir laquelle des deux palettes (verte ou bleue) choisir, car aucune des deux ne contient un mélange de bleu et de vert... le résultat est donc dans le style JPEG 0%

Voilà, si vous avez des suggestions pour améliorer tout ça, c'est avec plaisir

donc en gros le but c'est de chercher une partition des blocs en 16 groupes différents, les blocs dans un même groupe ayant une palette identique ?
ben par exemple solution bourrin : tu prends une partition au hasard, puis pour chacun des blocs tu regardes si tu peux améliorer le "score" (i.e. qualité de l'image) en le déplaçant de groupe (si oui tu le déplaces dans le groupe qui donne le meilleur score), puis tu réitères jusqu'à que tu ne puisses plus améliorer le score ; ça te donne une image potentiellement pas trop mal, mais tu peux répéter plein de fois tout le processus avec une partition de départ différente, en prenant le résultat qui a le meilleur score...


EDIT : évidemment ça exige que ta fonction de création de palette puisse travailler sur plusieurs tiles, mais sans ça tu ne risques pas d'aller très loin...

Tu peut aussi commencer par creer autant de palette que tu veux (en utilisant le meme algo bien sur) et apres tenter de reduire le nombre de palettes

oui par exemple en mettant chaque bloc dans son propre groupe (ce qui donne forcément un score maximal), puis faire le regroupement de deux groupes qui réduirait le moins le score, et ainsi de suite jusqu'à avoir 16 groupes... (enfin c'est peut-être pas très optimal, dans le sens où les 10-20 dernières fusions feront forcément très très bobo aux deux groupes concernés, alors que ceux qui ont échappé de près à la fusion n'auront pas une égratignure : peut-être que ça serait une bonne idée de faire les dernières fusions avec un algo un peu plus coûteux mais un peu plus subtil)

Elle a l'air excellente ta méthode Pollux, malheureusement si on imagine qu'on a 2'000 tiles, ça reviendrait à faire plus de 2'000'000 de tests par groupe qu'on veut éliminer (et il y aura autant de groupes que de tiles)! Et on aura effectivement entre 1'000 et 10'000 tiles en général. A moins qu'il y ait un moyen plus efficace?
Enfin bon je peux toujours essayer de regarder avant de commencer les différences entre eux pour ne tester qu'avec ceux qui sont les plus proches, mais ce sera pas réellement valable dans la mesure où comparer des couleurs réelles avec des couleurs générées par octree est faux, mais ce sera déjà mieux que rien
Ou alors une autre idée?
PS: Benchmark pour le moment: 13 secondes pour 200'000 tiles dont on sort une palette optimisée + score. Donc même un premier test pour trouver celles qui se ressemblent le plus serait impossible, car si on a 10'000 tiles, ça donne 50'000'000 de tests...

Brunni :
Elle a l'air excellente ta méthode Pollux, malheureusement si on imagine qu'on a 2'000 tiles, ça reviendrait à faire plus de 2'000'000 de tests par groupe qu'on veut éliminer (et il y aura autant de groupes que de tiles)! Et on aura effectivement entre 1'000 et 10'000 tiles en général. A moins qu'il y ait un moyen plus efficace?

Ben si tu gardes en mémoire les Score(x,y), et que quand tu fais une fusion des groupes x et y tu ne recalcules que les Score(Fusion(x,y),z) et pas le reste, ça te fait effectivement "seulement" O(ntiles^2) tests au total... (ce qui ne serait pas énorme si les fusions ne dépendaient pas du nb de tiles concernés, cf plus bas)

13 secondes pour 200'000 tiles dont on sort une palette optimisée + score

Arf ^^ Tu peux essayer de voir comment se comporte ton algo asymptotiquement par rapport au nb de tiles ? O(n^2) ?


Alors si effectivement l'algo de calcul de score est très sensible au nb de tiles concernés, ça peut être efficace de ne pas tjs tout mettre à jour... Par exemple si le groupe A a déjà 100'000 tiles et qu'on le fusionne avec un groupe de 100 tiles, ce serait profondément stupide de re-tester si A colle avec 10'000 groupes différents de 3 tiles, parce que les 100 tiles n'ont probablement pas changé grand-chose au score... Une solution à ce problème serait simplement de considérer que le score relatif de deux groupes avec des tailles très différentes est très mauvais : s'il y a plus d'un facteur, disons, 5 entre la taille de deux groupes, on ne calcule pas leur score relatif, sauf vers la fin (par exemple quand il ne reste plus que 50 groupes on se met à calculer tous les scores). Ca assure que les groupes ne seront comparés qu'avec des groupes de mêmes tailles (donc si on met à jour un groupe de 10,000 tiles alors il ne sera pas comparé 500 fois -- alors que vers la fin on n'a plus vraiment besoin de cette garantie puisqu'il n'y a de toute façon plus 500 groupes, et surtout on ne veut pas allouer une couleur spéciale au jaune pâle parce qu'il n'y a que 10 tiles jaune pâle alors qu'il y a 10000 tiles jaunes)

Hm je crois comprendre plus ou moins, merci. Je suis assez nul en algo, faut pas m'en vouloir si je réponds à côté
Ce que je me disais c'est qu'au début si on a 10'000 tiles, on commence avec 10'000 palettes, c'est-à-dire 10'000 groupes.
Pour comparer ces 10'000 groupes entre eux (déjà rien que la première fois, où on n'a encore rien éliminé), il y a 50 millions de tests à faire! C'est déjà là qu'il faudrait pouvoir retirer des possibilités en fait, et là que je coince d'ailleurs

si tu as vraiment 10'000 groupes, alors ça devient intéressant de couper le problème en morceaux : dans chaque morceau tu réduis par exemple 100 tiles en 50 groupes, puis tu fusionnes deux morceaux, en réduisant les 100 groupes en 50, et ainsi de suite ^^ (évidemment si tu prends des valeurs de "50" trop faibles, ça va influer sur la qualité de l'image... l'idée étant qu'il faut que "50" soit un peu plus grand que 16)

du coup ça passe de O(n^2) à O(100^2 n/50) ^^ (bon ok ça fait "juste" un facteur 50 avec n = 10'000, mais c'est déjà pas mal...)

Ok merci. Voici comment j'ai fait pour finir:
Comme la méthode que j'ai posté au-dessus, on retrouve toujours l'étape de base qui consiste à extraire les palettes extrêmes. On aura donc par exemple une palette bleue, une violette, une verte, etc. en tous cas bien éloignées et représentatives des différentes parties de l'image.
Après, une fois que j'ai mes 16 palettes, je leur crée une liste de tiles, et chacune reçoit pour tile celle qui l'a créée. Ensuite, pour chacune des tiles, j'essaie de la lier à chacune des palettes, en relançant ainsi la conversion qui crée une palette résultante de toutes les tiles liées (donc pas seulement une tile casée comme avant). La tile est finalement placée dans la palette pour laquelle la liaison réduit le moins le score.
Au final, on a des palettes bien représentatives, et une dernière étape détermine avec quelle palette chaque tile va le mieux et la lui donne. Il ne reste plus qu'à génèrer une map, une palette et un tileset à partir de ça et c'est bon.

Mais voilà, le problème, c'est que les palettes ont toutes tendance à être identiques! L'avantage est que l'image n'a pas cet effet "patchwork", mais la qualité est inférieure. Voici un exemple, en haut l'image de base, puis avec ma première méthode (3 minutes 40 pour 1'200 tiles) et en bas avec la deuxième (30 secondes pour 1'200 tiles):

http://gbagraphics.palib.info/Temp/convdiffs.png

D'où mes quelques questions:
1) comment pourrait-on faire pour améliorer la distance entre les palettes? J'ai essayé de donner des priorités aux tiles de base (colorées) mais c'est pire. Il me faudrait si possible avoir les couleurs les plus vives possibles pour un éventuel dithering.
2) comment peut-on calculer la similitude entre deux images? (par exemple, un pixel de noir à côté d'un blanc est plus proche du gris que deux pixels rouges par exemple, pourtant avec un calcul simple ça ne marche pas...).
3) Quelle méthode serait-elle plus adaptée pour la réduction de couleurs? Octree est rapide mais les couleurs sont plutôt fades...
Merci d'avance

Personnellement j'aurait commencé par reduire le nombre de couleur de l'image, en applicant ou non un dithering, et apres je ferais la conversion tel que tu la fait now. mais bon ^^

Remarque : pour éviter de trop perdre en qualité de couleur, je te conseille de passer du codage RGB au codage YUV, de réduire le nombre de couleurs en sachant qu'il vaut mieux arrondir grossièrement sur les composantes U et V plutôt que sur Y (l'oeil y est plus sensible), avant de repasser en RGB pour les palettes (cf. ce topic pour le passage RGB <-> YUV).

Sympa merci elle a l'air pas mal ta méthode