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.

[tbc92]

Pour le menton, et pour le front, on a ici du jaune, alors que j'aurais préféré du rose. On retrouve un problème déjà traité ici de 'calcul de ressemblance de couleurs'.

[AbsoluteLogic]

Bonjour, je suis de retour !
Désolé pour l'attente, je ne passe pas tout mon temps sur le projet, et j'ai tout de même fait pas mal de choses.

De tes dominos, je tire la palette de couleurs suivante

J'ai utilisé un capteur RGB finalement pour récupérer les couleurs des dominos, dans la mesure où c'est ce capteur sur la machine en Lego qui enverra les couleurs au programme. Les résultats que je présenterai seront donc avec des couleurs un peu différentes.

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.

Je n'ai pas du tout d'expérience avec Gimp, donc encore moins avec les scripts fu... Donc je préfère tant qu'à faire implémenter directement les algorithmes dans mon programme. Ça revient au même.

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 ... )

Je ne vois pas vraiment quelle corrections je pourrais faire à chaque étape...

Mais je concède que la réduction trop brutale. C'est pourquoi je me contenterai d'appliquer l'algorithme sur des images plus simples (plus faciles à dessiner avec peu de pixels, et sans effet d'ombre qui perturbent facilement les algorithmes). J'utiliserai par la suite comme exemple celle-ci:

Je suis reparti sur l'idée donc j'ai parlé dans l'ancien poste. J'ai d'abord créé un algorithme distinguant les différentes zones de couleurs. Voici le résultat des différentes zones qu'il envoie. Ces zones sont coloriées avec des couleurs aléatoires pour mieux les distinguer:

Il y a de nombreux parasites que je vais essayer d'éliminer à l'étape suivante:
Pour tous les pixels, si un pixel possède au plus un pixel voisin de la même zone et possède deux voisins d'une même zone autre que le pixel, alors ce pixel est affecté à la zone de ces voisins. En répétant cette action jusqu'à ne plus avoir de modifications, j'obtiens ceci:

C'est un peu mieux... Mais je ne sais pas si c'était vraiment nécessaire avec l'étape suivante.

L'étape suivante consiste à la réduction de l'image. On affecte chaque pixel de la petite image la zone qui revient le plus souvent pour les pixels de l'image de départ correspondante.
Les différentes zones, toujours avec des couleurs aléatoires, donnent ceci:

Si on affiche l'image en affectant à chaque zone sa couleur moyenne, on obtient ceci:

L'image est déjà simplifiée mais reste assez ressemblante. Donc si on avait des dominos de bonnes couleurs, c'est ce que l'on obtiendrait.

Maintenant il faut attribuer des couleurs de dominos à chaque zone. Pour cela, je commence par les zones dont les couleurs moyennes sont les plus proches d'une couleur de domino disponible.
A chaque nouvelle zone traitée, je rend non disponible la couleur affectée pour toutes les zones non traitées comportant plus de dominos que le nombre de dominos de la couleur affectée.
Bref, ce n'est peut être pas très clair, mais j'obtient le résultat suivant:

Ça me parait plutôt bien, au détail près que la couleur du visage se confond avec celle du bras. Je voudrais que deux zones qui se touchent aient nécessairement deux couleurs différentes.
Pour empêcher cela, pendant le raisonnement précédent, à chaque nouvelle zone traitée, je rend également non disponible à chaque zone qui la touche la couleur considérée. J'obtiens alors le résultat suivant:

Bof... Je préférais le précédent. Donc je ne sais pas si je garderai cet ajout...

Pour le menton, et pour le front, on a ici du jaune, alors que j'aurais préféré du rose. On retrouve un problème déjà traité ici de 'calcul de ressemblance de couleurs'.

Il n'y avait pas de rose parmi les dominos, mais c'est sûr que le orange aurait toujours été un peu mieux. Pour les distance entre les couleurs, j'utilise la distance euclidienne en considérant l'espace à 3 dimensions RGB. Pour un meilleur résultat, on pourrait peut être s'appuyer sur les valeurs HSV des couleurs, mais je n'ai rien trouvé de concluant sur ça (les nuances de gris peuvent s'écrire de différentes manières...). Avec des recherches sur internet, je suis tombé sur la distance qu'ils appelent "deltaE", mais c'est assez compliqué à mettre en place, et je ne sais pas si ça vaudrait le coup.


Bref, merci de votre participation, mais je crois que je ne vais pas chercher plus loin.
Je reste quand même ouvert à toute suggestion. Je ne marque pas le sujet comme résolu puisqu'il y peut toujours y avoir des améliorations...



EDIT: J'oubliais, voici tout de même le résultat sur deux autres images:
- Une voiture:
>
- et un drapeau (j'ai choisi celui-là pour ces couleurs...):
>

[tbc92]

Pour les distance entre les couleurs, j'utilise la distance euclidienne en considérant l'espace à 3 dimensions RGB.

Pour les distances entre couleurs, tu peux lire cette discussion :

https://www.developpez.net/forums/d1...ur-contrastee/

Il y a énormément de bla-bla, mais il y a quelques références utiles.

Je résume, de mémoire :
J'ai 2 couleurs (R1,G1,B1) et (R2,G2,B2)
Constat n°1 : Pour des petites valeurs de R1, G1, B1, R2, G2 ou B2, les écarts sont quasi indécelables par l'oeil humain. En d'autres mots, l'oeil humain ne sait quasiment pas voir la différence entre (0,G1,B1) et (20,G1,B1), alors qu'il voit nettement la différence entre (235,G1,B1) et (255,G1,B1) ; et idem sur les 2 autres axes.
Constat n°2 : Un écart de 50 sur l'axe Rouge ou sur l'axe Vert, c'est énorme. Alors qu'un écart de 50 sur l'axe Bleu, c'est pas énorme. En d'autres mots, l'axe Bleu doit être pondéré d'un coefficient inférieur à 1 pour mieux représenter la perception de l'oeil humain.

[anapurna]

salut

tu peut chercher le teinte sous-jacente en utilisant un autre format de couleur

actuellement les couleur sont souvent définit sous le format RGB (RED GREEN BLUE)
il faut changer de model et le passer en Teinte Saturation Valeur (TSV ou HSB en anglais)
ce qui te permettra d'extraire la teinte la plus proche de la realité

[AbsoluteLogic]

Je dis ça dans mon post précédent

Pour les distance entre les couleurs, j'utilise la distance euclidienne en considérant l'espace à 3 dimensions RGB. Pour un meilleur résultat, on pourrait peut être s'appuyer sur les valeurs HSV des couleurs, mais je n'ai rien trouvé de concluant sur ça (les nuances de gris peuvent s'écrire de différentes manières...). Avec des recherches sur internet, je suis tombé sur la distance qu'ils appelent "deltaE", mais c'est assez compliqué à mettre en place, et je ne sais pas si ça vaudrait le coup.

Pour les distances entre couleurs, tu peux lire cette discussion :

https://www.developpez.net/forums/d1...ur-contrastee/

Il y a énormément de bla-bla, mais il y a quelques références utiles.

Je résume, de mémoire :
J'ai 2 couleurs (R1,G1,B1) et (R2,G2,B2)
Constat n°1 : Pour des petites valeurs de R1, G1, B1, R2, G2 ou B2, les écarts sont quasi indécelables par l'oeil humain. En d'autres mots, l'oeil humain ne sait quasiment pas voir la différence entre (0,G1,B1) et (20,G1,B1), alors qu'il voit nettement la différence entre (235,G1,B1) et (255,G1,B1) ; et idem sur les 2 autres axes.
Constat n°2 : Un écart de 50 sur l'axe Rouge ou sur l'axe Vert, c'est énorme. Alors qu'un écart de 50 sur l'axe Bleu, c'est pas énorme. En d'autres mots, l'axe Bleu doit être pondéré d'un coefficient inférieur à 1 pour mieux représenter la perception de l'oeil humain.

Toutes ces idées sont justement mises en avant dans la définition de la distance deltaE qui me paraît compliqué à mettre en place. Mais bon, c'est sûr que si j'imagine que je voulais vraiment la solution idéale, il faudrait que je m'y mette.

tu peut chercher le teinte sous-jacente en utilisant un autre format de couleur

actuellement les couleur sont souvent définit sous le format RGB (RED GREEN BLUE)
il faut changer de model et le passer en Teinte Saturation Valeur (TSV ou HSB en anglais)
ce qui te permettra d'extraire la teinte la plus proche de la realité

Le problème, c'est avec le gris, blanc, noir... Deux gris quasiment identiques peuvent s'écrire avec des teintes opposées. C'est pourquoi il est difficile de trouver une distance correcte selon ces valeurs.