Discussion :

[Electroniktor]

Bonjour tout le monde !

Je suis à la recherche d'un petit algorithme.

Je dois convertir une image bitmap 24 bits en une image bitmap 4 bits (16 couleurs).
Pour cela, sur toute l'image source, je dois prendre un pixel, chercher quelle est la couleur de la palette 16 couleurs qui s'en rapproche le plus, puis injecter cette couleur dans l'image de destination aux mêmes coordonnées.

Mais je bloque un peu sur la manière de trouver la couleur la plus proche ...

Merci d'avance !

[pseudocode]

Les 16 couleurs sont imposées ou il faut également les determiner ?

[Electroniktor]

Salut ! Merci de me répondre !

Ben c'est les 16 couleurs qui sont affichables dans une console !
C'est celles que l'on obtient quand avec Paint, on enregistre une image au format bmp 16 couleurs !

[pseudocode]

OK. Dans ce cas pour mesurer l'écart entre 2 couleurs il faut choisir un espace de couleur et une distance. Tu as plusieurs choix:

- Espace RGB et distance euclidienne
- Espace HSL et distance de carron (voir ici)
- Espace YUV/LAB et distance euclidienne pondérée (voir ici)

[Electroniktor]

OK merci beaucoup pour ces explications.

La méthode avec l'espace HSL me semble adaptée avec le type d'image que j'aurai à convertir, et en plus j'ai l'impression que c'est la plus simple !

En pièce jointe le genre d'image que je vais traiter.

[Frifron]

Pour convertir une image en 16 couleurs simplement, utiliser juste la couleur la plus proche risque de ne pas donner un résultat très satisfaisant (surtout en cas de dégradé). Une technique qui va te permette de plus approximer l'image originale est d'utiliser un tramage (également appelé diffusion). Un de ses algo de tramage s'appelle le tramage de floyd steinberg mais il en existe d'autres.

[Electroniktor]

Re-bonjour tout le monde !

Désolé de mon retard mais je n'ai pas pu accéder à internet ces derniers temps !

Oui j'ai remarqué que les résultats n'étaient pas très bon (voir décevants ) donc je vais essayé cet algo. J'ai bien compris son principe de fonctionnement, seulement je n'ai trouvé nul part quelle valeur donner à l'erreur et si elle doit évoluer pendant le traitement.

Merci d'avance !

[Frifron]

Salut l'erreur est en fait la distance entre la couleur choisie (une de tes couleurs de ta palette) et la couleur réelle. Elle n'évolu pas en fonction du temps mais est différente pour chaque pixel. Dans l'espace RGB, tu calculer l'erreur pour chaque canal avec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

erreur = valeur_réelle - valeur_choisie

Tu diffuse ensuite l'erreur pour les 3 canaux séparemment aux pixels contigues suivant la matrice de diffusion de floyd & steinberg http://fr.wikipedia.org/wiki/Algorithme_de_Floyd-Steinberg

Tu fais ca pour tout les pixels en parcourant dans le bon sens (la diffusion met a jour les pixel dont la couleur n'a pas encore été choisie evidemment).

En gros l'ago :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
pour i allant de 0 a hauteur
    pour j allant de 0 a largeur
         choix de la couleur pour le pixel(i,j)
         calcul et diffusion de l'erreur R
         calcul et diffusion de l'erreur G
         calcul et diffusion de l'erreur B

Après tu peux testé la diffusion dans un autre espace que RGB (YUV, HSL...) et comparer les résultat voir ce que ca donne.

[Electroniktor]

Salut, merci de ta réponse !

J'ai implémenté l'algo et cela me donne une image toute grise (avec le même gris partout).

Je pense donc que la manière de calculer la distance entre les deux couleurs et importante. Est-ce qu'il y a un algo spécial pour ce type de tramage ?

Pour l'instant je fais ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
long distance(RGB e1, RGB e2)
{
    int r = e1.r - e2.r;
    int g = e1.g - e2.g;
    int b = e1.b - e2.b;
    int rmean = (e1.r + e2.r) / 2;
 
    return (((512 + rmean) * r *r) >> 8) + 4 * g * g + (((767 - rmean) * b * b >> 8);
}

[pseudocode]

Je pense donc que la manière de calculer la distance entre les deux couleurs et importante. Est-ce qu'il y a un algo spécial pour ce type de tramage ?

il faut travailler sur les 3 canaux RGB séparément. L'erreur est alors la simple difference (en valeur absolue)

[Frifron]

il faut travailler sur les 3 canaux RGB séparément. L'erreur est alors la simple difference (en valeur absolue)

Pour la distance c'est en valeur absolue mais pour l'erreur non, il faut conserver l'information de signe pour savoir dans quelle sens on la réduit.

Si tu as que du gris partout il y a en effet un probleme dans l'algo... Si tu enleves la diffusion de l'erreur est ce que le choix des couleurs te parait juste ? Si oui, tu as mal implémenté l'algo de diffusion et je te propose de le poster ici.

[souviron34]

il faut travailler sur les 3 canaux RGB séparément. L'erreur est alors la simple difference (en valeur absolue)

en gros, ce que veut dire pseudocode, c'est que ce n'est pas la distance par rapport au total des 3 canaux, mais le point ou la distanc en R, la distance en G, et la distance en B est minimale... C'est plus clair ?

[Frifron]

J'ai fait un petit prog en java vite fait qui implémente la diffusion de Floyd Steinberg.

C'était vraiment pour mettre l'algo en application et que tu vois ou est ton erreur. Pour la distance j'ai simplement pris l'addition des distances des 3 canaux R G et B ce qui est loin d'etre la meileur facon d'approximer une couleur pour l'oeil humain mais qui suffit dans le principe. En ulisant uniquement 5 couleurs (noir,blanc, rouge,vert et bleu) on arrive deja a un résultat honnete qui sera grandement amélioré avec un autre calcul de distance (d ou sors celui que tu utilises ?) et 16 couleurs au lieu de 5, voire même en changeant d'algo de diffusion

[pseudocode]

en gros, ce que veut dire pseudocode, c'est que ce n'est pas la distance par rapport au total des 3 canaux, mais le point ou la distanc en R, la distance en G, et la distance en B est minimale... C'est plus clair ?

heu... c'est effectivement plus clair mais ce n'ai pas ce que je voulais dire.

Je voulairs dire qu'il faut calculer l'erreur sur chaque canal (donc 3 valeurs) et diffuser cette erreur sur les canaux correspondants de chaque pixel. Le code source de Frifron explique cela bien mieux que ma phrase.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
for (int i = 0; i < image.getHeight(); ++i)
	for (int j = 0; j < image.getWidth(); ++j) {
		int real = image.getRGB(j,i);
		int chosen = chooseColor(real);
		image.setRGB(j,i,chosen);
 
		int errorR = getError(getR(real),getR(chosen));
		int errorG = getError(getG(real),getG(chosen));
		int errorB = getError(getB(real),getB(chosen));
 
		diffuseError(image,j - 1,i + 1,errorR,errorG,errorB,3.0f / 16.0f);
		diffuseError(image,j,i + 1,errorR,errorG,errorB,5.0f / 16.0f);
		diffuseError(image,j + 1,i + 1,errorR,errorG,errorB,1.0f / 16.0f);
		diffuseError(image,j + 1,i,errorR,errorG,errorB,7.0f / 16.0f);
	}
}

Sinon, la formule utilisée par Electroniktor est expliquée dans un des liens de mon post #4.