Tramado ordenado

El tramado ordenado es un algoritmo de tramado de imágenes que utiliza un mapa de umbral preestablecido aplicado a la imagen. Se usa comúnmente para mostrar una imagen continua en pantallas con poca profundidad de color . Por ejemplo, Microsoft Windows lo usa en los modos gráficos de 16 colores. Con el mapa de umbral "Bayer", el algoritmo se caracteriza por patrones de trama cruzada perceptibles en el resultado.

El algoritmo reduce el número de colores aplicando un mapa de umbral M a los píxeles mostrados, lo que provoca que algunos píxeles cambien de color, dependiendo de la distancia del color original con respecto a las entradas de color disponibles en la paleta reducida.

Los primeros mapas de umbral se diseñaron a mano para minimizar la diferencia perceptual 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 posible cuantización del color, presenta la mínima textura posible, de modo que la impresión más nítida de la característica subyacente proviene de la imagen que se está cuantizando. Se puede demostrar que para matrices cuyos lados tienen una longitud que es potencia de dos, existe una matriz de umbral óptima. ^{[ 2 ]} El mapa puede rotarse o reflejarse sin afectar la eficacia del algoritmo.

Este mapa de umbral (para lados con longitud que es potencia de dos ) también se conoce como matriz de Bayer o, cuando no está escalado, como matriz de índices . Para mapas de umbral cuyas dimensiones son potencia de dos, el mapa se puede generar recursivamente mediante:

${\displaystyle \mathbf {M} _{2n}={\frac {1}{(2n)^{2}}}{\begin{bmatrix}4\mathbf {M} _{n}&4\mathbf {M} _{n}+2\mathbf {J} _{n}\\4\mathbf {M} _{n}+3\mathbf {J} _{n}&4\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},}$

dónde${\displaystyle \mathbf {J} _ {n}}$son${\displaystyle n\times n}$matrices de unos y${\displaystyle \otimes }$es el producto Kronecker .

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

Esta función también puede expresarse utilizando únicamente aritmética de bits: ^{[ 3 ]}

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${\displaystyle n}$×${\displaystyle n}$números enteros del 0 al${\displaystyle n^{2}}$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 entera tradicional que se muestra arriba.

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 de 2×2:

Esto crea el mapa precalculado:

Además, la normalización de los valores para que su suma sea promedio de 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 * maxValue

Creando el mapa precalculado:

El algoritmo de tramado ordenado renderiza la imagen normalmente, pero para cada píxel, ajusta su valor de color con un valor correspondiente del mapa de umbrales según su ubicación, lo que provoca que el valor del píxel se cuantifique a un color diferente si supera el umbral.

Para la mayoría de los propósitos de tramado, basta con sumar el valor umbral a cada píxel (sin realizar la normalización restando 1/2 ) , o , de forma 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, se dibuja ese píxel en negro; de lo contrario, se dibuja 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 tramen. Esto no es un problema cuando se utiliza una paleta de escala de grises (o cualquier paleta donde las distancias de color relativas sean (casi) constantes), e incluso suele ser 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 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: $${\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)}$$ donde M ( i , j ) es el mapa de umbral en la i -ésima fila y 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 igualmente espaciados donde cada color (una tripleta de valores rojo, verde y azul) está representado por un octeto de 0 a 255, normalmente se elegiría${\textstyle r\approx {\frac {255}{N}}}$( 1/2 es de nuevo el término de normalización) .

Debido a que el algoritmo opera sobre píxeles individuales y no tiene condiciones, es muy rápido e idóneo para transformaciones en tiempo real. Además, como la posición de los patrones de tramado se mantiene constante con respecto al fotograma de visualización, es menos propenso a la inestabilidad que los métodos de difusión de errores, lo que lo hace adecuado para animaciones. Dado que los patrones son más repetitivos que en 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 produce líneas más rectas y menos anomalías.

Los valores leídos del mapa de umbral deberían, preferiblemente, estar dentro del mismo rango que la diferencia mínima entre los distintos colores de la paleta objetivo. De forma equivalente, el tamaño del mapa seleccionado debería ser igual o mayor que la relación entre los colores de origen y los de destino. Por ejemplo, al cuantificar una imagen de 24 bpp a 15 bpp (de 256 colores por canal a 32 colores por canal), el mapa más pequeño que se elegiría sería de 4×2, para una relación de 8 (256:32). Esto permite expresar cada tono distinto de la entrada con diferentes patrones de tramado.

El método de matriz de umbralización descrito anteriormente describe la familia Bayer de algoritmos de tramado ordenado. Existen otros algoritmos conocidos que, por lo general, implican cambios en la matriz de umbralización, lo que modifica la distribución del "ruido" introducido por todos los tipos de tramado (la diferencia entre la imagen original y la imagen tramada).

• Tramado ordenado (proyecto del curso de gráficos, laboratorio Visgraf, Brasil)
• Algoritmos de tramado (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).