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 un algorithme 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.

Description[modifier | modifier le code]

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[modifier | modifier le code]

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}

Pseudo-code[modifier | modifier le code]

En pseudo-code :


 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

Notes et références[modifier | modifier le code]


Articles connexes[modifier | modifier le code]