El tramado ordenado es un algoritmo de tramado de imágenes . Se utiliza comúnmente para mostrar una imagen continua en una pantalla de menor profundidad de color . Por ejemplo, Microsoft Windows lo utiliza en modos de gráficos de 16 colores. El algoritmo se caracteriza por patrones de sombreado notables en el resultado.
El algoritmo reduce la cantidad 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 umbrales vienen en varios tamaños, que normalmente son una potencia de dos:
El mapa se puede rotar o reflejar sin afectar la efectividad del algoritmo. Este mapa de umbral (para lados con longitud como potencia de dos ) también se conoce como matriz de índice o matriz de Bayer . [1]
Se pueden diseñar mapas de umbrales de tamaño arbitrario con una regla simple: primero llene cada espacio con un número entero sucesivo. Luego, reordenelos 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 "envuelva" los bordes. [ cita necesaria ] Para mapas de umbral cuyas dimensiones son una potencia de dos, el mapa se puede generar de forma recursiva mediante:
Esta función también se puede expresar usando solo aritmética de bits: [2]
M(i, j) = bit_reverse(bit_interleave(bitwise_xor(i, j), i)) / n ^ 2
En lugar de almacenar el mapa de umbral como una matriz de × enteros de 0 a , dependiendo del hardware exacto utilizado para realizar el difuminado, puede resultar beneficioso calcular previamente los umbrales del mapa en un formato de punto flotante, en lugar del formato tradicional. formato de matriz entera que se muestra arriba.
Para ello se puede utilizar la siguiente fórmula:
Mpre(i,j) = Menta(i,j) / n^2
Esto genera una matriz de umbral estándar.
para el mapa 2×2:
esto crea el mapa precalculado:
Además, también se puede normalizar los valores para promediar su suma a 0 (como se hace en el algoritmo de tramado que se muestra a continuación) durante el preprocesamiento restando 1 ⁄ 2 de cada valor:
Mpre(i,j) = Menta(i,j) / n^2 – 0,5
Creando el mapa precalculado:
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 según su ubicación, lo que hace que el valor del píxel se cuantifique en un color diferente si excede el umbral.
Para la mayoría de los propósitos de tramado, es suficiente simplemente sumar el valor umbral a cada píxel (sin realizar la normalización restando 1 ⁄ 2 ), o de manera equivalente, 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, traza ese píxel en negro; de lo contrario, trazalo en blanco. Esta falta de normalización aumenta ligeramente el brillo promedio de la imagen y hace que los píxeles casi blancos no se difuminen. Esto no es un problema cuando se utiliza una paleta de escala de grises (o cualquier paleta donde las distancias relativas de color sean (casi) constantes) y, a menudo, incluso es deseable, 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 utiliza una paleta pequeña o arbitraria, por lo que se debe preferir una normalización adecuada.
En otras palabras, el algoritmo realiza la siguiente transformación en cada color c de cada píxel:
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 cuadro de visualización, es menos propenso a sufrir fluctuaciones 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.
Los valores leídos en el mapa de umbrales deben escalar preferiblemente en el mismo rango que la diferencia mínima entre distintos colores en la paleta de destino. De manera equivalente, el tamaño del mapa seleccionado debe ser igual o mayor que la proporció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 una proporción de 8 (256:32). Esto permite expresar cada tono distinto de la entrada con diferentes patrones de tramado. [ cita necesaria ]
El enfoque de matriz de umbral anterior describe la familia Bayer de algoritmos de tramado ordenados. También se conocen otros algoritmos; generalmente implican cambios en la matriz de umbral, equivalente al "ruido" en las descripciones generales del tramado.
El tramado de medios tonos realiza una forma de tramado agrupado, creando una apariencia similar a los patrones de medios tonos , utilizando una matriz especialmente diseñada.
El algoritmo Void and cluster utiliza un ruido azul pregenerado como matriz para el proceso de tramado. [3] La matriz de ruido azul mantiene el buen contenido de alta frecuencia de Bayer, pero con una cobertura más uniforme de todas las frecuencias involucradas muestra una cantidad mucho menor de patrón. [4]
El método "voids-and-cluster" recibe su nombre del procedimiento de generación de matrices, donde una imagen negra con píxeles blancos inicializados aleatoriamente se desenfoca gaussianamente para encontrar las partes más brillantes y más oscuras, correspondientes a vacíos y clusters. Después de que algunos cambios hayan distribuido uniformemente las partes brillantes y oscuras, los píxeles se numeran según su importancia. Se necesitan importantes recursos computacionales para generar la matriz de ruido azul: en una computadora moderna, una matriz de 64×64 requiere un par de segundos usando el algoritmo original. [5]
Este algoritmo se puede ampliar para crear máscaras de tramado animadas que también consideren el eje del tiempo. Esto se hace ejecutando el algoritmo en tres dimensiones y utilizando un núcleo que es producto de un núcleo gaussiano bidimensional en el plano XY y un núcleo gaussiano unidimensional en el eje Z. [6]
