Discussion :

[electroremy]

Bonjour,

Je cherche un algorithme de réduction du nombre de couleurs dans une image pour un besoin particulier.

Il faut que l'image obtenue comporte des formes bien nettes, sans couleurs intermédiaires.

Je vais prendre un exemple, ce sera plus parlant :



Cette image est en 24 bits, donc du fait de l'anti aliasing, il y a pas mal de pixels de couleurs intermédiaires entre les formes.

L'objectif est d'obtenir une image "pixelisée" en cinq couleurs, comme si l'image avait été dessinée sans anti-aliasing avec une ancienne version de Paint.

Précision importante : dans mon application, c'est l'utilisateur qui va choisir les couleurs à conserver.
Dans l'exemple donné, l'utilisateur choisira de conserver le blanc, le rouge, le jaune, l'orange et le bleu.

L'algorithme n'a donc pas à déterminer par le calcul le nombre de couleur à obtenir, ni la valeur de ces couleurs.
L'algorithme devra faire avec les couleurs imposées.

Un traitement sur la palette posera un problème au niveau de la frontière entre le cercle jaune et le rectangle rouge, car des pixels intermédiaires seront inévitablement reconnus comme orange qui est une couleur utilisée par une autre forme de l'image.

J'ai pu trouver toutes sortes d'algorithmes de réduction de couleurs (k-moyennes, k-moyennes++, Floyd-Steinberg, ...) mais ces algorithmes ont été élaborés pour du traitement d'image "classique" destiné à réduire le nombre de couleurs d'une photo en conservant le mieux possible son aspect esthétique pour l'œil humain.

Ca ne correspond pas à ce que je souhaite faire.

Auriez vous connaissance d'un type d'algorithme adapté à mon besoin ?

Je pensais procéder par "passes successives", c'est à dire :
- En faisant d'abord une conversion noir et blanc pour chaque couleur imposée, avec un seuil assez sévère pour que seuls les pixels très proches de la couleur voulue soient blancs et tous les autres noirs;
- Ensuite, j'effectue un filtrage pour éliminer les éventuels pixels blancs "isolés";
- On obtient une série d'images en noir et blanc pour chaque couleur (un peu comme des calques).
- Enfin, on peut ensuite recombiner ces "calques" pour obtenir l'image finale, en peignant successivement de la bonne couleur les zones blanches de chaque image en noir et blanc.

Mais je crains de me retrouver avec des "artefacts" dans l'image finale, car les "calques" risquent de ne pas bien se recouvrir

Ou alors il faut procéder par "couches", chaque couleur de l'image finale étant classée dans un certain ordre, et ensuite :
- le premier "calque" détecte tous les pixels de la couleur n°1
- le 2e "calque" détecte tous les pixels de la couleur n°1 ou de la couleur n°2
- le 3e "calque" détecte tous les pixels de la couleur n°1 ou de la couleur n°2 ou n°3
- le 4e "calque" détecte tous les pixels de la couleur n°1 ou de la couleur n°2 ou n°3 ou n°4

En quelque sorte, on élimine chaque couleur au fur et à mesure
Il faudra du filtrage là aussi

Ensuite, on peint sans anti aliasing l'image finale dans l'ordre inverse :
- d'abord la couleur n°5 en couleur de fond
- puis la couleur n°4 avec le calque n°4
- puis la couleur n°3 avec le calque n°3
- puis la couleur n°2 avec le calque n°2
- puis la couleur n°1 avec le calque n°1

A bientôt

[Guesset]

Bonjour,

Sauf erreur de compréhension, le problème est plus simple que les algorithmes cités puisque c'est l'utilisateur qui fixe les couleurs.
Le travail qui reste à faire consiste pour chaque point lui affecter la couleur la plus proche. Cela se résume donc à des calculs de distance (beaucoup).

Quelle distance utiliser ? Bien sûr cela dépend de l'objectif visé. J'utilise fréquemment une distance euclidienne pondérée (enfin sa forme quadratique car la racine carré ne change rien aux relations d'ordre et consomme du temps) mais les espaces perceptuels peuvent être intéressants même s'ils demandent plus de calculs (donc sont plus longs).

Il y a deux approches de calcul : pixel par pixel (w*h*nbrCouleur calculs de distances) ou création de clusters à partir de la palette (nbrCouleur² calculs de distances + w*h affectations de cluster). Le choix dépend des tailles en jeu sachant que la deuxième approche est souvent plus rapide mais plus difficile à mettre en œuvre.

Il y a aussi à décider ce qu'on fait des erreurs. L'affectation des couleurs de la palette laisse des résidus. Soit on ne les conserve pas soit on propage l'erreur (comme Floyd-Steinberg). Ne pas s'en occuper est plus simple mais les créneaux sont bien visibles et propager les erreurs est mieux visuellement mais fait apparaître des moustiques de points parasites (dont la moyenne se rapproche de la valeur moyenne d'origine). Là encore l'objectif incitera à un choix ou l'autre

Salutations

[electroremy]

Bonjour,

Sauf erreur de compréhension, le problème est plus simple que les algorithmes cités puisque c'est l'utilisateur qui fixe les couleurs.
Le travail qui reste à faire consiste pour chaque point lui affecter la couleur la plus proche. Cela se résume donc à des calculs de distance (beaucoup).

Quelle distance utiliser ? Bien sûr cela dépend de l'objectif visé. J'utilise fréquemment une distance euclidienne pondérée (enfin sa forme quadratique car la racine carré ne change rien aux relations d'ordre et consomme du temps) mais les espaces perceptuels peuvent être intéressants même s'ils demandent plus de calculs (donc sont plus longs).

Il y a deux approches de calcul : pixel par pixel (w*h*nbrCouleur calculs de distances) ou création de clusters à partir de la palette (nbrCouleur² calculs de distances + w*h affectations de cluster). Le choix dépend des tailles en jeu sachant que la deuxième approche est souvent plus rapide mais plus difficile à mettre en œuvre.

Il y a aussi à décider ce qu'on fait des erreurs. L'affectation des couleurs de la palette laisse des résidus. Soit on ne les conserve pas soit on propage l'erreur (comme Floyd-Steinberg). Ne pas s'en occuper est plus simple mais les créneaux sont bien visibles et propager les erreurs est mieux visuellement mais fait apparaître des moustiques de points parasites (dont la moyenne se rapproche de la valeur moyenne d'origine). Là encore l'objectif incitera à un choix ou l'autre

Salutations

Bonjour,

Merci pour ta réponse

Mais l'approche que tu décris est toujours celle du traitement d'images "photo", qui ne correspond pas à mon besoin.

En particulier, cela ne résoud pas le problème que j'ai soulevé dans l'exemple de mon message initial au niveau de la frontière entre le cercle jaune et le rectangle rouge, car des pixels intermédiaires seront inévitablement reconnus comme orange qui est une couleur utilisée par une autre forme de l'image.

Ce que je cherches à faire c'est, en quelque sorte, "annuler" l'antialiasing pour retrouver une image avec des formes pixelisées "nettes" sans pixel intermédiaire

Voici une autre illustration du problème, avec un "zoom" pour mieux comprendre :

image de départ avec anti aliasing :



L'utilisateur choisi de conserver les couleurs jaune, vert, bleu, orange et violet

image désirée en sortie :



A bientôt

[electroremy]

Bonjour

je vais reprendre l'exemple de départ avec un zoom, ce sera plus explicite

image de départ :



L'utilisateur sélectionne les couleurs ROUGE, JAUNE, ORANGE et BLEU

Image finale :



Un logiciel comme Paint.NET arrive presque à le faire via sa fonction "Quantize" du menu "Effet" -> "Couleurs" en mettant le niveau de tramage à zéro
En réalité ça ne fonctionne pas, il faut mettre le nombre de couleurs à 3, puis peindre manuellement le cercle en haut à droite en orange manuellement.

A bientôt !

[electroremy]

Bonsoir

il me vient une autre idée :

Puisque mon besoin consiste en fait à "annuler" l'antialiasing, le traitement des pixels pourrait se faire en plusieurs étapes :
- les pixels identiques (ou vraiement très proches) d'une couleur sélectionnés sont identifiés comme étant de cette couleur sélectionnée
- un filtrage détecte les pixels "isolés" c'est à dire avec trop de différences avec leurs 8 voisins, et les reclasse comme étant "non identifiés" (le fameux problème de la zone frontière entre le cercle rouge et le cercle jaune dans mon exemple)
- les pixels non identifiés sont affectés à la couleur des pixels "identifiés" les plus proches et majoritaires géographiquement

la pixelisation serait probablement un peu plus "sèche" mais on évite ainsi les artefacts

A bientôt

[kaitlyn]

Salut tout le monde,

Quand tu parcours ton image horizontalement (ou verticalement, peu importe) tu tombes sur des pixels qui se suivent sur un dégradé de couleurs (color gradient), disons du rouge au jaune. En quantifiant les couleurs des pixels de transition, tu sais s'ils tiennent plus du rouge ou du jaune et tu modifies leurs couleurs en conséquence.

Je me demande aussi si une conversion au format vectoriel (détection de contours, vectorisation) puis à nouveau au format matriciel (rastérisation) (mais sans anticrénelage (antialiasing)) permettrait d'obtenir ce que tu souhaites.

Enfin, as-tu regardé si GIMP ou Imagemagick ont une fonction ou un filtre qui fait le job, ou quelque chose qui s'en rapprocherait, la netteté par exemple (Sharpen) ?