Dithering ordenado

El tramado ordenado es cualquier algoritmo de tramado de imágenes que utiliza un mapa de umbral preestablecido distribuido en mosaico sobre una imagen. Se utiliza habitualmente para mostrar una imagen continua en una pantalla con una profundidad de color menor . Por ejemplo, Microsoft Windows lo utiliza en modos gráficos de 16 colores. El algoritmo se caracteriza por patrones de trama cruzada 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 según la distancia del color original respecto de las entradas de color disponibles en la paleta reducida.

Los primeros mapas de umbral se diseñaron a mano para minimizar la diferencia perceptiva entre una imagen en escala de grises y su cuantificación de dos bits para una matriz de hasta 4x4. ^[1]

Una matriz de umbral óptima es aquella que, para cualquier cuantificación posible del color, tiene la textura mínima posible, de modo que la mayor impresión de la característica subyacente proviene de la imagen que se cuantifica. Se puede demostrar que para matrices cuya longitud de lado es una potencia de dos existe una matriz de umbral óptima. ^[2] 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 Bayer o, cuando no está escalado, matriz de índice . Para los mapas de umbral cuyas dimensiones son una potencia de dos, el mapa se puede generar de forma recursiva mediante:

${\displaystyle \mathbf {M} _{2n}={\frac {1}{(2n)^{2}}}{\begin{bmatrix}(2n)^{2}\mathbf {M} _{n }&(2n)^{2}\mathbf {M} _{n}+2\mathbf {J} _{n}\\(2n)^{2}\mathbf {M} _{n}+3\ mathbf {J} _{n}&(2n)^{2}\mathbf {M} _{n}+\mathbf {J} _{n}\end{bmatrix}}=\mathbf {J} _{2 }\otimes \mathbf {M} _{n}+{\frac {1}{n^{2}}}\mathbf {M} _{2}\otimes \mathbf {J} _{n},}$

donde son matrices de unos y es el producto de Kronecker .${\displaystyle \mathbf {J} _ {n}}$${\displaystyle n\veces n}$ ${\displaystyle \otimes}$

Si bien la métrica de textura que propuso Bayer podría usarse para encontrar matrices óptimas para tamaños que no sean una potencia de dos, dichas matrices son poco comunes ya que no existe una fórmula simple para encontrarlas, y los tamaños de matriz relativamente pequeños con frecuencia dan excelentes resultados prácticos (especialmente cuando se combinan con otras modificaciones al algoritmo de tramado).

Esta función también se puede expresar utilizando sólo aritmética de bits: ^[3]

M(i, j) = bit_inverso(intercalado_bit(xor_bit a bit(i, j), i)) / n ^ 2

En lugar de almacenar el mapa de umbrales como una matriz de × números enteros de 0 a , dependiendo del hardware exacto utilizado para realizar el tramado, puede ser beneficioso precalcular los umbrales del mapa en un formato de punto flotante, en lugar del formato de matriz de números enteros tradicional que se muestra arriba.${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización n^{2}}$

Para ello se puede utilizar la siguiente fórmula:

Mpre(i,j) = Mint(i,j) / 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 tramado que se muestra a continuación) también se puede realizar durante el preprocesamiento restando 1 ⁄ 2 del valor más grande de cada valor:

Mpre(i,j) = Mint(i,j) / n^2 – 0,5 * valormáximo

Creando el mapa precalculado:

El algoritmo de tramado ordenado renderiza 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 a un color diferente si excede el umbral.

Para la mayoría de los propósitos de tramado, es suficiente simplemente sumar el valor del umbral a cada píxel (sin realizar la normalización restando 1 ⁄ 2 ), o equivalentemente, 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, trace ese píxel en negro, de lo contrario, tracelo 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 usa una paleta de escala de grises (o cualquier paleta donde las distancias relativas de color sean (casi) constantes), e incluso a menudo 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, sin embargo, produce resultados incorrectos, especialmente cuando se usa una paleta pequeña o arbitraria, por lo que se debe preferir la normalización adecuada.

En otras palabras, 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 fila i y la columna j , 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 espaciados uniformemente donde cada color (un triple de valores rojo, verde y azul) está representado por un octeto de 0 a 255, uno elegiría típicamente . ( 1 ⁄ 2 es nuevamente el término normalizador).$${\displaystyle c'=\mathrm {color\_de\_paleta\_más\_cercano} {\mathopen {}}\left(c+r\times \left(M(x{\bmod {n}},y{\bmod {n}})-1/2\right){\mathclose {}}\right)}$$${\textstyle r\approx {\frac {255}{N}}}$

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 tramado siempre permanece igual en relación con el marco de visualización, es menos propenso a la vibració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.

Los valores leídos del mapa de umbral deberían escalarse preferiblemente en el mismo rango que la diferencia mínima entre los distintos colores en la paleta de destino. De manera equivalente, el tamaño del mapa seleccionado debería 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 relación de 8 (256:32). Esto permite expresar cada tono distinto de la entrada con diferentes patrones de tramado. ^{[ cita requerida ]}

Esta sección está vacía. Puedes ayudarnos agregándole algo. ( Julio 2021 )

El enfoque de matriz de umbralización anterior describe la familia Bayer de algoritmos de dithering ordenados. También se conocen otros algoritmos que generalmente implican cambios en la matriz de umbral, equivalentes al "ruido" en las descripciones generales del dithering.

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 de vacío y clúster utiliza un ruido azul generado previamente como matriz para el proceso de tramado. ^[4] La matriz de ruido azul conserva 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 patrones. ^[5]

El método de "vacíos y cúmulos" recibe su nombre del procedimiento de generación de matrices, en el que una imagen negra con píxeles blancos inicializados aleatoriamente se difumina mediante un método gaussiano para encontrar las partes más brillantes y más oscuras, correspondientes a los vacíos y los cúmulos. Después de que unos pocos intercambios hayan distribuido de manera uniforme las partes brillantes y oscuras, los píxeles se numeran por importancia. Se necesitan recursos computacionales significativos para generar la matriz de ruido azul: en una computadora moderna, una matriz de 64 × 64 requiere un par de segundos utilizando el algoritmo original. ^[6]

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 un producto de un núcleo gaussiano bidimensional en el plano XY y un núcleo gaussiano unidimensional en el eje Z. ^[7]

• Dithering ordenado (Proyecto del curso de Gráficos, laboratorio Visgraf, Brasil)
• Algoritmos de dithering (Lee Daniel Crocker, Paul Boulay y Mike Morra)

• Implementación en Matlab de varios métodos de tramado
• anim8gdx, implementación en Java de varios métodos de tramado (en su mayoría ordenados)