Accueil🇫🇷Chercher

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.

Image à 1 bit de la Statue de David, tramée avec l'algorithme Floyd–Steinberg

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

Notes et références

    Articles connexes

    Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.