El tramado ordenado es un algoritmo de tramado de imágenes. Se usa comúnmente para mostrar una imagen continua en una pantalla de menor profundidad de color . Por ejemplo, Microsoft Windows lo usa en modos de gráficos de 16 colores. El algoritmo se caracteriza por patrones de sombreado marcados en el resultado.
Mapa de umbrales
El algoritmo reduce el número de colores aplicando un mapa de umbral M a los píxeles mostrados, lo que hace que algunos píxeles cambien de color, dependiendo de la distancia del color original a las entradas de color disponibles en la paleta reducida.
Los mapas de umbral vienen en varios tamaños, que normalmente es una potencia de dos:
El mapa puede rotarse o reflejarse sin afectar la eficacia del algoritmo. Este mapa de umbrales (para lados con longitud como potencia de dos ) también se conoce como matriz de índice o matriz de Bayer . [1]
Los mapas de umbral de tamaño arbitrario se pueden diseñar con una regla simple: Primero llene cada espacio con números enteros sucesivos. Luego, reordenarlos de manera que la distancia promedio entre dos números sucesivos en el mapa sea lo más grande posible, asegurándose de que la tabla se "envuelva" en los bordes. [ cita requerida ] Para mapas de umbral cuyas dimensiones son una potencia de dos, el mapa se puede generar de forma recursiva a través de:
La expresión recursiva se puede calcular explícitamente utilizando solo aritmética de bits: [2]
M (i, j) = bit_reverse (bit_interleave (bit a bit_xor (i, j), i)) / n ^ 2
Mapas de umbrales precalculados
En lugar de almacenar el mapa de umbral como una matriz de × enteros de 0 a , dependiendo del hardware exacto utilizado para realizar el tramado, puede ser beneficioso calcular previamente los umbrales del mapa en un formato de punto flotante, en lugar del formato tradicional de matriz de enteros que se muestra arriba.
Para ello, se puede utilizar la siguiente fórmula:
Mpre (i, j) = (Menta (i, j) +1) / n ^ 2
Esto genera una matriz de umbral estándar.
para el mapa 2 × 2:
esto crea el mapa precalculado:
Además, la normalización de los valores para promediar su suma a 0 (como se hace en el algoritmo de difuminado que se muestra a continuación) se puede realizar durante el preprocesamiento y restando de cada valor:
Mpre (i, j) = (Menta (i, j) +1) / n ^ 2 - 0.5
creando el mapa precalculado:
Algoritmo
El algoritmo de tramado ordenado representa la imagen normalmente, pero para cada píxel, compensa su valor de color con un valor correspondiente del mapa de umbral de acuerdo con su ubicación, lo que hace que el valor del píxel se cuantifique a un color diferente si excede el umbral.
Para la mayoría de los propósitos de difuminado, es suficiente simplemente agregar el valor de umbral a cada píxel (sin realizar la normalización restando ), o de manera equivalente, para comparar el valor del píxel con el umbral: si el valor de brillo de un píxel es menor que el número en la celda correspondiente de la matriz, trazar ese píxel en negro; de lo contrario, trazarlo en blanco.
Esto aumenta ligeramente el brillo medio de la imagen y hace que los píxeles casi blancos no se difuminen. Esto no es un problema cuando se usa una paleta de escala de grises (o cualquier paleta donde las distancias de color relativas son (casi) constantes), y a menudo incluso se desea, ya que el ojo humano percibe las diferencias en los colores más oscuros con mayor precisión que en los más claros. , produce resultados incorrectos, especialmente cuando se usa una paleta pequeña o arbitraria, por lo que se debe preferir una normalización adecuada.
El algoritmo realiza la siguiente transformación en cada color c de cada píxel:
donde M ( i , j ) es el mapa de umbral en la i -ésima fila y la j -ésima columna, c ′ es el color transformado y r es la cantidad de dispersión en el espacio de color. Suponiendo una paleta RGB con 2 3 N colores uniformemente distanciados donde cada color (un triple de los valores rojo, verde y azul) está representado por un octeto de 0 a 255, normalmente se elegiría:
Los valores leídos del mapa de umbrales deben escalar preferiblemente en el mismo rango que la diferencia mínima entre los distintos colores en la paleta de destino.
Debido a que el algoritmo opera en píxeles individuales y no tiene declaraciones condicionales, es muy rápido y adecuado para transformaciones en tiempo real. Además, debido a que la ubicación de los patrones de difuminado siempre permanece igual en relación con el marco de visualización, es menos propenso a la fluctuación que los métodos de difusión de errores, lo que lo hace adecuado para animaciones. Debido a que los patrones son más repetitivos que el método de difusión de errores, una imagen con tramado ordenado se comprime mejor. El tramado ordenado es más adecuado para gráficos de arte lineal, ya que dará como resultado líneas más rectas y menos anomalías.
El tamaño del mapa seleccionado debe ser igual o mayor que la relación entre los colores de origen y los colores de destino. Por ejemplo, al cuantificar una imagen de 24 bpp a 15 bpp (256 colores por canal a 32 colores por canal), el mapa más pequeño que se elegiría sería 4 × 2, para la proporción de 8 (256: 32). Esto permite expresar cada tono distinto de la entrada con diferentes patrones de difuminado. [ cita requerida ]
Notas
- ^ Bayer, Bryce (11 al 13 de junio de 1973). "Un método óptimo para la reproducción de dos niveles de imágenes de tonos continuos" (PDF) . Conferencia Internacional de Comunicaciones de IEEE . 1 : 11-15. Archivado desde el original (PDF) el 12 de mayo de 2013 . Consultado el 19 de julio de 2012 .
- ^ Joel Yliluoma. " Algoritmo de tramado posicional de paleta arbitraria "
Referencias
- Tramado ordenado (proyecto del curso de gráficos, laboratorio de Visgraf, Brasil)
- Algoritmos de difuminado (Lee Daniel Crocker, Paul Boulay y Mike Morra)