Indecisión de Floyd-Steinberg

Imagen original

Sin difuminar

Indecisión de Floyd-Steinberg

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. ^{[ 1 ]} Es comúnmente utilizado por software de manipulación de imágenes, por ejemplo, al convertir una imagen de un formato PNG de color verdadero de 24 bits a un formato GIF , que está restringido a un máximo de 256 colores. ^{[ 2 ]}

El algoritmo logra el tramado mediante la difusión de errores , lo que significa que transfiere (suma) el error de cuantificación residual de un píxel a sus píxeles vecinos, que serán cuantificados posteriormente. Distribuye la deuda según la distribución (que se muestra como un mapa de los píxeles vecinos):

$${\displaystyle {\begin{bmatrix}&&*&{\frac {\displaystyle 7}{\displaystyle 16}}&\ldots \\\ldots &{\frac {\displaystyle 3}{\displaystyle 16}}&{\frac {\displaystyle 5}{\displaystyle 16}}&{\frac {\displaystyle 1}{\displaystyle 16}}&\ldots \\\end{bmatriz}}}$$

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 previamente. Los valores específicos (7/16, 3/16, 5/16, 1/16) se encontraron originalmente por ensayo y error, "guiados por el deseo de que una región de densidad deseada de 0,5 apareciera como un patrón de tablero de ajedrez". ^{[ 3 ]} El algoritmo escanea la imagen de izquierda a derecha, de arriba 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 varios píxeles se han 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 originales de los píxeles se encuentran exactamente a medio camino entre los colores disponibles más cercanos, el resultado del tramado es un patrón de tablero de ajedrez. Por ejemplo, los datos en gris al 50 % podrían generar un patrón de tablero de ajedrez en blanco y negro mediante tramado. Para un tramado óptimo, el conteo de errores de cuantificación debe ser lo suficientemente preciso como 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 con los valores sRGB , como suele hacerse con las imágenes almacenadas en ordenadores.

En algunas implementaciones, la dirección horizontal del escaneo alterna entre líneas; esto se denomina "escaneo serpentino" o tramado de transformada bustrofedón .

El algoritmo descrito anteriormente se encuentra en el siguiente pseudocódigo . Este 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 hacer para cada x de izquierda a derecha hacer oldpixel := pixels[ x ][ y ] nuevopixel := encontrar_el_color_de_paleta_más_cercano(oldpixel) píxeles[ x ][ y ] := nuevopixel quant_error := oldpixel - newpixel píxeles[ x + 1][ y ] := píxeles[ x + 1][ y ] + error_cuantificado × 7 / 16 píxeles[ x - 1][ y + 1] := píxeles[ x - 1][ y + 1] + error_cuantificante × 3 / 16 píxeles[ x ][ y + 1] := píxeles[ x ][ y + 1] + error_cuantificación × 5 / 16 píxeles[ x + 1][ y + 1] := píxeles[ x + 1][ y + 1] + error_cuantificación × 1 / 16

Al convertir valores de píxeles en escala de grises de una profundidad de bits alta a una baja (por ejemplo, de escala de grises de 8 bits a blanco y negro de 1 bit), find_closest_palette_color()puede que simplemente se realice un redondeo, por ejemplo:

find_closest_palette_color(oldpixel) = round(oldpixel / 255)

El pseudocódigo puede generar valores de píxeles que excedan los límites válidos (por ejemplo, mayores de 255 en imágenes en escala de grises de 8 bits). Idealmente find_closest_palette_color(), la función debería gestionar estos valores en lugar de recortar los valores intermedios, ya que un error posterior podría devolverlos al rango permitido. Sin embargo, si se utilizan enteros de ancho fijo, el ajuste de los valores intermedios provocaría una inversión de los colores blanco y negro, por lo que debe evitarse.

La find_closest_palette_color()implementación no es trivial para una paleta que no está distribuida uniformemente; sin embargo, pequeñas imprecisiones al seleccionar el color correcto de la paleta tienen un impacto visual mínimo debido a que el error se propaga a los píxeles siguientes. Se suele utilizar una búsqueda del vecino más cercano en 3D.

• El tramado de Atkinson , una variante del tramado de Floyd-Steinberg diseñada por Bill Atkinson.

• Tramado de Floyd-Steinberg (proyecto de curso de gráficos, laboratorio Visgraf, Brasil)
• RW Floyd, L. Steinberg, Un algoritmo adaptativo para la escala de grises espacial . Actas de la Sociedad de Visualización de Información 17 , 75-77 (1976).