Algorithme de Floyd-Steinberg

Un article de Wikipédia, l'encyclopédie libre.

L'algorithme de Floyd-Steinberg est utilisé en traitement d'images. Cet algorithme effectue un tramage par la diffusion de l'erreur de quantification d'un pixel à ses voisins. Plus précisement, 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.00 & 0.00 & 0.00 \\ 0.00 & 0 & 0.44 \\ 0.19 & 0.31 & 0.06 \end{bmatrix}

Cet algorithme peut servir à une résolution naïve du problème du plus court chemin en théorie de graphes

[modifier] Liens