El tramado de Floyd-Steinberg es un algoritmo de tramado de imágenes publicado por primera vez en 1976 por Robert W. Floyd y Louis Steinberg. Se utiliza habitualmente en el software de manipulación de imágenes, por ejemplo, cuando una imagen se convierte al formato GIF , que está restringido a un máximo de 256 colores.
El algoritmo logra el difuminado mediante 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 tratarlo más adelante. Distribuye la deuda según la distribución (que se muestra como un mapa de los píxeles vecinos):
El píxel indicado 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 y 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 han sido cuantificados. Por lo tanto, si un número de píxeles se ha redondeado hacia abajo, es más probable que el siguiente píxel se redondee hacia arriba, de modo que, en promedio, el error de cuantificación sea cercano a cero.
Los coeficientes de difusión tienen la propiedad de que si los valores de píxeles originales están exactamente a medio camino entre los colores disponibles más cercanos, el resultado difuminado es un patrón de tablero de ajedrez. Por ejemplo, los datos con un 50 % de 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 al resultado.
En algunas implementaciones, la dirección horizontal de escaneo alterna entre líneas; esto se llama "escaneo serpentino" o tramado por transformada de boustrophedon .
El algoritmo descrito anteriormente se encuentra en el siguiente pseudocódigo . Esto funciona para cualquier codificación aproximadamente lineal de valores de píxeles, como enteros de 8 bits, enteros de 16 bits o números reales en el rango [0, 1].
para cada y de arriba a abajo haga para cada x de izquierda a derecha haga oldpixel := píxeles[ x ][ y ] nuevopíxel:= find_closest_palette_color(viejopíxel) píxeles[ x ][ y ] := nuevo píxel quant_error := 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] + error_cuantitativo × 1/16
Al convertir valores de píxeles en escala de grises de una profundidad de bits alta a una baja (por ejemplo, escala de grises de 8 bits a blanco y negro de 1 bit), find_closest_palette_color()puede realizar simplemente un redondeo simple, por ejemplo:
find_closest_palette_color(oldpixel) = round(oldpixel / 255)
El pseudocódigo puede provocar que los valores de píxeles superen los valores válidos (por ejemplo, más de 255 en imágenes en escala de grises de 8 bits). Idealmente, la función debería recortar dichos valores find_closest_palette_color(), en lugar de recortar los valores intermedios, ya que un error posterior puede hacer que el valor vuelva al rango. Sin embargo, si se utilizan números enteros de ancho fijo, ajustar los valores intermedios provocaría la inversión del blanco y negro, por lo que se debe evitar.
Esto find_closest_palette_colorno es trivial para una paleta que no está distribuida uniformemente. En tal caso, se requiere una búsqueda del vecino más cercano en 3D.
