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

[electroremy]

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.

L'artefact de la "fausse détection" de la couleur orange serait présent

Salut tout le monde,
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) ?

Ces fonctions ne correspondent pas à ce que je cherche, là aussi elles sont orientées traitement "photo" ou "graphique".
Il peut arriver que les fonctions de quantification, de réduction de couleur ou de durcissement des logiciels existants aboutissent au résultat que je cherche, mais c'est aléatoire. Dès que l'image à traiter est un peu "difficile" ça ne fonctionne pas.

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.

Alors justement, le traitement que je cherche à faire est un prérequis pour la conversion au format vectorielle qui arrive ensuite dans mon programme (détection de contour, puis lissage d'un point de vue géométrique).

Ma conversion au format vectorielle fonctionne très bien mais il faut en entrée une image comportant des zones de couleur avec une séparation nette et pas d'anti aliasing.

Après réflexion je pense que l'idée que j'ai émise au message précédent est bonne.
Mon besoin est probablement trop spécifique pour que beaucoup de membres du forum connaissent une solution existante.

[kaitlyn]

L'artefact de la "fausse détection" de la couleur orange serait présent

Ce n’est pas forcément le même orange. D'ailleurs comment sélectionnes-tu tes couleurs à conserver ? Avec une pipette ?

[electroremy]

Ce n’est pas forcément le même orange.

certes mais il faut anticiper la théorie de l'emmerdement maximum

D'ailleurs comment sélectionnes-tu tes couleurs à conserver ? Avec une pipette ?

Alors oui, l'utilisateur pourra choisir les couleurs :
- soit dans la liste des couleurs les plus utilisées (après un "scan" de l'image pour compter les pixels de chaque couleur)
- soit avec une pipette
- soit manuellement si besoin

[tbc92]

Est-ce que l'image que tu as choisie au départ est représentative des images que tu auras à traiter, à savoir des images avec des grandes zones uniformes, qui ne poseraient aucun problème si elles avaient été sauvegardées en format BMP ?
Je suppose que oui.
Est-ce qu'on a l'assurance que l'utilisateur va sélectionner 4 ou 5 couleurs adaptées à l'image à traiter (par exemple, sur l'image présentée, espérons que l'utilisateur ne sélectionne pas bleu, vert, noir et blanc) ?
Je suppose que oui.
Si l'utilisateur choisit comme couleurs jaune, rouge, orange, blanc et bleu, a priori, la seule couleur qui peut être sur-représentée, c'est le orange. (Et peut-être le jaune, voire le rouge ?)
Si on a une zone franchement rouge, et une autre franchement jaune, à la frontière entre les 2, l'anti-aliasing a mis des pixels plus ou moins oranges.
Idem, si on a une zone franchement orange, et une autre franchement blanche, à la frontière entre les 2, l'anti-aliasing peut mettre des pixels plus ou moins jaunes, ou rouges.
Par contre, il n'y a aucune raison que l'anti-aliasing introduise des pixels bleus ni blancs.
Donc il y aurait une première étape, quelles couleurs peuvent être surnuméraires ? Et ensuite, seuls les pixels ayant ces couleurs doivent être vérifiés.

L'idée de regarder les 9 pixels voisins pour chaque pixel me paraît la bonne, sauf que 9, c'est probablement trop petit. Quel seuil mettre avec un aussi petit effectif ?

Dans ton message, tu parles de pixels isolés.
Sauf que dans le cas du cercle jaune sur fond rouge, on risque d'avoir une ligne orange tout autour du cercle. Chaque pixel fautif orange risque d'avoir 2 voisins également fautifs en orange. Voire plus si les couleurs choisies par l'utilisateur ne sont pas parfaitement les mêmes que celles de l'image d'origine, mais seulement ressemblantes.
Si on a un carré noir sur fond blanc, le pixel du coin aura 3 voisins noirs, et 5 voisins blancs, et normalement, il faut le garder en noir.

Je prendrais les 24 voisins (un carré 5x5), quitte à mettre des coefficients un peu plus faible aux pixels les plus loin du pixel traité.

[electroremy]

Est-ce que l'image que tu as choisie au départ est représentative des images que tu auras à traiter, à savoir des images avec des grandes zones uniformes, qui ne poseraient aucun problème si elles avaient été sauvegardées en format BMP ?
Je suppose que oui.
Est-ce qu'on a l'assurance que l'utilisateur va sélectionner 4 ou 5 couleurs adaptées à l'image à traiter (par exemple, sur l'image présentée, espérons que l'utilisateur ne sélectionne pas bleu, vert, noir et blanc) ?
Je suppose que oui.

C'est tout à fait ça

Par contre, il n'y a aucune raison que l'anti-aliasing introduise des pixels bleus ni blancs.

Alors ce sera peut être le cas quand même

Pourquoi ?

Les images peuvent avoir pour source la méthode bourrin, c'est à dire :
- des copies d'écran
- des scan de documents divers et variés, possiblement un peu sales
- une photographie d'une plaque signalétique ou d'une face avant

Les algorithmes de lissage des écrans LCD modernes tiennent compte de l'emplacement physique des pixels R, V et B et du coup dans les copies d'écrans on peut avoir des couleurs inattendues au niveau de l'antialiasing (c'est notamment ce qui est utilisé pour le lissage des polices de caractères)

Du coup l'image aura des aplats de couleurs mais avec d'une part un peu de bruit ou de variation, et de l'autre parts des pixels "intermédiaires" à cause de l'antialiasing.

L'idée de regarder les 9 pixels voisins pour chaque pixel me paraît la bonne, sauf que 9, c'est probablement trop petit. Quel seuil mettre avec un aussi petit effectif ?

Dans ton message, tu parles de pixels isolés.
Sauf que dans le cas du cercle jaune sur fond rouge, on risque d'avoir une ligne orange tout autour du cercle. Chaque pixel fautif orange risque d'avoir 2 voisins également fautifs en orange. Voire plus si les couleurs choisies par l'utilisateur ne sont pas parfaitement les mêmes que celles de l'image d'origine, mais seulement ressemblantes.
Si on a un carré noir sur fond blanc, le pixel du coin aura 3 voisins noirs, et 5 voisins blancs, et normalement, il faut le garder en noir.

Je prendrais les 24 voisins (un carré 5x5), quitte à mettre des coefficients un peu plus faible aux pixels les plus loin du pixel traité.

J'ai eu la même idée cette après midi !

Je vais proposer dans les réglages du traitement d'image le choix de la taille de la zone pour tenir compte des voisins, donc soit 3x3, soit 5x5 (peut être aussi 7x7 mais je pense que 5x5 suffira)
Dans les réglages, on pourra ajuster le nombre mini de pixels voisin de la même couleur.

A bientôt

[Guesset]

Bonjour,

Le problème n'est donc pas tant une réduction de couleurs qu'une quasi détection de contour (seuls les contours sont à régénérer).

La technique des voisinages semble la meilleure mais elle ne peut seulement s'appuyer sur la couleur majoritaire qui entraîne, comme mentionné par tbc92, une abrasion des coins.

Une proposition parmi d'autres :

1. Sur un environnement de n² points (n impair pour que le point testé puisse être central), prendre les ((n + 1) >> 1)² points les plus proches (choix d'une distance à faire).
2. En faire la moyenne et l'affecter au point courant (le point courant étant éventuellement inclus).
3. On peut réitérer la phase précédente pour accentuer la convergence locale.
4. Cela ne va pas faire disparaître complétement le flou de contour mais le rapprocher d'une dominante locale ce qui devrait augmenter les chances que la réduction de couleur qui suit absorbe ces flous résiduels.

Ceci étant, améliorer les contours pour préparer une vectorisation qui les détecte pourrait inciter à utiliser plutôt une détection de contours améliorée au sein même de la vectorisation.

Salutations

[electroremy]

Ceci étant, améliorer les contours pour préparer une vectorisation qui les détecte pourrait inciter à utiliser plutôt une détection de contours améliorée au sein même de la vectorisation.

Mon code de vectorisation, qui fonctionne très bien sur des images en 'n' couleurs, est une version amélioré d'un code initialement conçu pour travailler sur une image en noir et blanc.

Ce code ne peut pas gérer en même temps le problème qui fait l'objet de la discussion (présence "parasite", en plus des 'n' couleurs, d'autres couleurs liés à de l'anti aliasing)

Il est pour moi beaucoup plus facile de procéder à une réduction de couleur en amont du code de vectorisation.

Les fonctions de réduction de couleur des logiciels de traitement d'image arrive presque à faire ce que je souhaite.
Créer ma propre variante de réduction de couleur sera bien plus aisé que de refaire entièrement le code de vectorisation.

A bientôt