Algorithme de Floyd-Steinberg
# 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 :

    ${\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

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.

