Discussion :

[AbsoluteLogic]

Bonjour,

Je possède une image que je veux recréer de la manière la plus réaliste "visuellement". Mais l'image retournée doit être composée uniquement d'une certaine palette de couleurs données. De plus, chacune de ces couleurs ne peut être utilisé qu'un nombre limité de fois. L'image est également redimensionnée (on redéfinit sa hauteur et on garde la proportion), mais ce n'est qu'un détail...

Données:
- image
- liste des couleurs (palette)
- liste des nombres de pixels maximaux pour chaque couleur
- nouvelle hauteur
Résultat:
- image la plus réaliste selon les contraintes

Concrètement, pour moi, cet algorithme sert à générer une image en dominos à partir d'une image d'un ordinateur
pour passer de ça par exemple...

... à ça:

...d'où une contrainte sur les couleurs et le nombre de dominos (pixels).


Dans un premier temps, j'aborde le problème seulement selon les couleurs (pas de limite sur leurs nombres d'utilisation). Une première approche "naïve" consiste alors à définir une distance entre 2 couleurs, et d'affecter à chaque pixel de l'image finale la couleur qui est la plus "proche". [Algo 1]
Dans la mesure où la résolution d'arrivée sera généralement très faible (de l'ordre de 20-30 pixels de hauteur), on ne peut pas envisager par exemple d'alterner des pixels rouges et bleus pour obtenir du violet.


Dans un second temps, en considérant le problème avec les limites de pixels de couleur, j'ai imaginé deux moyens de le prendre en compte:
Le premier est le suivant [Algo 2]:
1) on affecte à chaque couleur de la palette des poids initialement à 1.
2) on applique l'algorithme précédent (Algo 1), en comptant le nombre de chaque pixel utilisé.
3) si une couleur est utilisée trop de fois, on augmente son poids
4) on recommence à l'étape 2), en retenant prenant en compte les poids pour favoriser les couleurs de poids faible.
A chaque itération le nombre de pixels pour chaque couleurs devrait se rapprocher de leur limite, et finir par tous passer en dessous.
Cependant, on ne peut pas savoir de combien augmenter les poids à chaque fois, et la terminaison n'est pas assurée...

Le second est le suivant [Algo 3]: (plus compliqué...)
1) Pour chaque couleur de la palette, on crée une liste contenant chaque pixel de l'image source (on retient leurs instances, donc leurs couleurs ET position), et on la trie par ordre croissant de la distance à la couleur de la palette.
2) On choisit la liste pour laquelle le premier élément (pixel) est le plus proche de couleur correspondante à la liste (on ne considère que les listes associées à des couleurs pour lesquelles on n'a pas atteint la limite)
3) On place ce pixel (1er élément de la liste) sur notre image finale.
4) On supprime alors ce pixel dans toutes les listes.
5) On recommence à l'étape 2) jusqu'à ce que toutes les listes soient vides.

Voilà ce que j'ai imaginé pour le moment, mais c'est loin d'être parfait, d'autant plus que l'on ne prend à aucun moment l'aspect "spatial" de l'image (aucun idée de voisinage entre les pixels) qui est important pour un bon rendu "visuel".
C'est pourquoi je fais appelle à votre aide pour des suggestions d'améliorations, ou de reprises complètes des algorithmes.

Merci d'avance pour votre aide !

[Flodelarab]

Bonjour

Tu décris un contexte.
Mais quel est le but ? Le vrai but ?
Pourquoi ne traites-tu pas l'image sous gimp en transformant ton image avec une palette fixe de couleurs prédéfinies ?
Puis tu pixélises. Ou l'inverse : Tu pixélises et tu changes les couleurs.

Ton exemple est bon car le reflet du casque fait croire que la majorité du casque est du fond.
Mais ça, seul un humain peut le dire.

[AbsoluteLogic]

Merci pour ton intérêt sur mon problème

Tu décris un contexte.
Mais quel est le but ? Le vrai but ?
Pourquoi ne traites-tu pas l'image sous gimp en transformant ton image avec une palette fixe de couleurs prédéfinies ?

Je cherche à faire tout le processus pour aller d'un point A à un point B.
Le point A est une image brute sur un ordi.
Le point B est un dessin en dominos.
Je travaille déjà parallèlement sur la fin du "processus" en faisant une machine en Lego Mindstorms (J'espère que t'en as déjà entendu parler ^^) capable de placer ces dominos. Je dois donc alors créer un logiciel lui envoyant les couleurs de chaque domino. En partant du point A, je ne compte alors pas utiliser de logiciels tiers, d'autant qu'ils ne pourront jamais prendre en compte la limite du nombre de chaque couleur dont j'ai parlé dans mon problème.

Ton exemple est bon car le reflet du casque fait croire que la majorité du casque est du fond.
Mais ça, seul un humain peut le dire.

Justement, c'est surtout là que j'ai besoin de vous. Les algorithmes que j'ai proposé traitent chaque pixel indépendamment, et cela amène donc des problèmes comme celui que tu as mis en avant. Pour régler ce problème, je ne pense pas qu'il y ait besoin d'être un humain. Il faudrait rajouter un raisonnement prenant en compte l'aspect "spatial" de l'image, ici en mettant en contraste le casque et le fond par le (petit) saut de couleur à la frontière. Une fois ce saut détecté, il faudrait associer deux couleurs différentes aux deux côtés. Mais voilà: c'est plus facile à dire qu'à faire....

Voilà, il y a encore du travail...

[Flodelarab]

Est-ce que tu réalises à quel point l'image finale ne ressemble pas à l'image originale ?

C'est irréalisable.

À part pour "les experts Miami" où ils sont capables de zoomer 400 fois sur une image de 10 pixels de côtés.
Ou pour Chuck Norris.

Tu pourrais faire de la détection de bords.
Mais quand tu auras détecté 5 bords sur 50 pixels sur une image 4000x3000, que cela va-t-il devenir sur un plan de dominos de 40x30 ?

Je voulais te demander une image de palette de couleurs de dominos. Mais je réalise que tu n'en as même pas.

Est-ce un projet perso ? Professionnel ? Scolaire ?

[AbsoluteLogic]

Est-ce un projet perso ? Professionnel ? Scolaire ?

C'est un projet personnel ^^

Est-ce que tu réalises à quel point l'image finale ne ressemble pas à l'image originale ?
C'est irréalisable.

Plus ce sera proche, mieux ce sera. Mais je n'ai pas avant d'abandonner un si beau projet (à mon goût )

Tu pourrais faire de la détection de bords.
Mais quand tu auras détecté 5 bords sur 50 pixels sur une image 4000x3000, que cela va-t-il devenir sur un plan de dominos de 40x30 ?

Après ton message précédent, je me suis lancé sur une nouvelle idée se basant sur ces "bords".
J'ai créé un algorithme partitionnant l'image (déjà pixelisée) en différentes zones de couleur suffisamment uniforme (chaque zone est déterminée en partant d'un pixel et en faisant un parcours en largeur sans saut de couleur au delà d'un seuil). A partir de ces zones, on pourra alors appliquer les algorithmes précédents de manière analogue (les pixels deviennent des ensembles de pixels, et leurs couleurs correspondent aux moyennes).
Pour le moment, le rendu n'est pas très bon puisque comme tu le dit, pour une aussi basse résolution, ça peut difficilement ressembler. Mais je n'abandonne pas, je continuerai d'y travailler demain.

Je voulais te demander une image de palette de couleurs de dominos. Mais je réalise que tu n'en as même pas.

Si, j'utilise mes propres dominos. Voici les différentes couleurs que je possède:


Voilà, à poursuivre... (j'espère)

[Flodelarab]

(Toute la suite est avec Gimp)

De tes dominos, je tire la palette de couleurs suivante :


Je reprends le chevalier du début.



Je le transforme en dominos. (image > Mode > couleur indexées ... choix de la palette ci-dessus)



Donc là, il te faudrait 201x248=49848 dominos.
On réduit (image > Échelle et taille de l'image)



Taille 30x37=1110 dominos
C'est l'ordre de grandeur du résultat présenté au début.
Donc là, tu pourrais le faire chez toi.

C'est moche de prêt mais potable de loin.
C'est le même problème de résolution que les publicités 4 par 3.

De toute façon, la réduction est trop brutale.
Pour un bon résultat, il faudrait réduire par étape et corriger l'inadmissible à chaque étape.
(Ou alors, changer à la fin, à loisir ... )


On peut faire l'inverse. Réduire puis changer en dominos :

> >

C'est un peu moins bon. Mais ce n'est pas flagrant. Amusant

Sous Gimp, tu devrais faire un script fu, et quand tu arriveras à un résultat satisfaisant sur un grand nombre d'images cobayes, tu auras ton algorithme.