Algorithme de Floyd-Steinberg
L'algorithme de Floyd-Steinberg est un algorithme de réduction du nombre de couleurs utilisé en traitement d'images. Cet algorithme, publié pour la première fois en 1976 par Robert W. Floyd et Louis Steinberg, effectue une diffusion de l'erreur de quantification d'un pixel à ses voisins.
Description
Lors de la réduction du nombre de couleurs d'une image (par exemple pour la conversion en GIF, limité à 256 couleurs), cet algorithme permet de conserver l'information qui devrait être perdue par la quantification en la poussant sur les pixels qui seront traités plus tard.
Plus précisément, 7/16 de son erreur est ajoutée au pixel à sa droite, 3/16 au pixel situé en bas à gauche, 5/16 au pixel situé en dessous et 1/16 au pixel en bas à droite.
Exemple
Par exemple, considérons la matrice des valeurs des pixels ci-dessous :
Si la valeur du centre est quantifiée à zéro et que l'erreur est diffusée par l'algorithme de Floyd-Steinberg, la matrice résultat sera celle ci-dessous :
Pseudo-code
Les opérations ci-dessous portent sur les différentes composantes de couleur en même temps: par exemple, ancien_pixel - nouveau_pixel signifie que l'on soustrait chaque composante.
La fonction couleur_la_plus_proche effectue la simplification de couleur voulue: par exemple, elle convertit la couleur d'un pixel en un Ă©quivalent en niveau de gris.
pour chaque y de haut en bas
pour chaque x de gauche Ă droite
ancien_pixel := pixel[x][y]
nouveau_pixel := couleur_la_plus_proche(ancien_pixel)
pixel[x][y] := nouveau_pixel
erreur_quantification := ancien_pixel - nouveau_pixel
pixel[x+1][y ] := pixel[x+1][y ] + 7/16 * erreur_quantification
pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * erreur_quantification
pixel[x ][y+1] := pixel[x ][y+1] + 5/16 * erreur_quantification
pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * erreur_quantification