El dithering de Floyd-Steinberg es un algoritmo de dithering de imágenes publicado por primera vez en 1976 por Robert W. Floyd y Louis Steinberg. Se utiliza habitualmente en software de manipulación de imágenes. Por ejemplo, al convertir una imagen de un formato PNG de 24 bits con color verdadero a un formato GIF , que está restringido a un máximo de 256 colores.
El algoritmo logra el dithering mediante la difusión de errores , lo que significa que empuja (agrega) el error de cuantificación residual de un píxel a sus píxeles vecinos, para ser tratado más tarde. Distribuye la deuda de acuerdo con la distribución (mostrada como un mapa de los píxeles vecinos):
El píxel marcado con una estrella (*) indica el píxel que se está escaneando actualmente y los píxeles en blanco son los píxeles escaneados anteriormente. El algoritmo escanea la imagen de izquierda a derecha, de arriba a abajo, cuantificando los valores de los píxeles uno por uno. Cada vez, el error de cuantificación se transfiere a los píxeles vecinos, sin afectar a los píxeles que ya se han cuantificado. Por lo tanto, si se han redondeado hacia abajo una cantidad de píxeles, es más probable que el siguiente píxel se redondee hacia arriba, de modo que, en promedio, el error de cuantificación es cercano a cero.
Los coeficientes de difusión tienen la propiedad de que si los valores de los píxeles originales están exactamente a la mitad de los colores disponibles más cercanos, el resultado difuminado es un patrón de tablero de ajedrez. Por ejemplo, un 50 % de datos grises se podrían difuminar como un patrón de tablero de ajedrez en blanco y negro. Para un difuminado óptimo, el recuento de errores de cuantificación debe tener la precisión suficiente para evitar que los errores de redondeo afecten el resultado.
Para obtener resultados correctos, todos los valores deben linealizarse primero, en lugar de operar directamente sobre los valores sRGB como es común con las imágenes almacenadas en computadoras.
En algunas implementaciones, la dirección horizontal del escaneo alterna entre líneas; esto se denomina "escaneo serpenteante" o tramado de transformada de bustrofedón .
El algoritmo descrito anteriormente se encuentra en el siguiente pseudocódigo . Funciona para cualquier codificación aproximadamente lineal de valores de píxeles, como números enteros de 8 bits, números enteros de 16 bits o números reales en el rango [0, 1].
para cada y de arriba a abajo haz para cada x de izquierda a derecha haz oldpixel := pixels[ x ][ y ] newpixel := buscar el color de paleta más cercano (oldpixel) píxeles[ x ][ y ] := nuevopíxel error_cuantitativo := píxel_antiguo - píxel_nuevo píxeles[ x + 1][ y ] := píxeles[ x + 1][ y ] + quant_error × 7 / 16 píxeles[ x - 1][ y + 1] := píxeles[ x - 1][ y + 1] + quant_error × 3 / 16 píxeles[ x ][ y + 1] := píxeles[ x ][ y + 1] + quant_error × 5 / 16 píxeles[ x + 1][ y + 1] := píxeles[ x + 1][ y + 1] + quant_error × 1 / 16
Al convertir valores de píxeles en escala de grises de una profundidad de bits alta a una baja (por ejemplo, una escala de grises de 8 bits a un blanco y negro de 1 bit), find_closest_palette_color()se puede realizar simplemente un redondeo simple, por ejemplo:
buscar_color_de_paleta_más_cercano(pixel_antiguo) = redondo(pixel_antiguo / 255)
El pseudocódigo puede dar como resultado valores de píxeles que superen los valores válidos (por ejemplo, más de 255 en imágenes en escala de grises de 8 bits). Lo ideal sería que la find_closest_palette_color()función manejara dichos valores, en lugar de recortar los valores intermedios, ya que un error posterior podría hacer que el valor volviera a estar dentro del rango. Sin embargo, si se utilizan números enteros de ancho fijo, la superposición de valores intermedios provocaría la inversión del blanco y negro, por lo que debería evitarse.
La find_closest_palette_color()implementación no es trivial para una paleta que no está distribuida uniformemente; sin embargo, las pequeñas imprecisiones en la selección del color correcto de la paleta tienen un impacto visual mínimo debido a que el error se propaga a los píxeles futuros. Con frecuencia se utiliza una búsqueda del vecino más cercano en 3D.
