Algorithme de Floyd-Steinberg

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Michelangelo's David - Floyd-Steinberg.png

L'algorithme de Floyd-Steinberg est utilisé en traitement d'images. Cet algorithme, publié pour la première fois en 1976 par Robert W. Floyd et Louis Steinberg, effectue un tramage par la diffusion de l'erreur de quantification d'un pixel à ses voisins.

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.

Par exemple, considérons la matrice des valeurs des pixels ci-dessous :


\begin{bmatrix}
0.00 & 0.00 & 0.00 \\
0.00 & 1.00 & 0.00 \\
0.00 & 0.00 & 0.00
\end{bmatrix}

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 :


\begin{bmatrix}
0.0000 & 0.0000 & 0.0000 \\
0.0000 & 0 & 0.4375 \\
0.1875 & 0.3125 & 0.0625
\end{bmatrix}


En pseudo-code :

pour chaque y de bas en haut
   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

Lien interne[modifier | modifier le code]