Jaggies y Aliasing Los “jaggies” son un nombre informal para los artefactos producto de la representación pobre de una geometria a partir de una grilla 2D de pixeles Los jaggies son una manifestación del error de muestreo y pérdida de información (aliasing) El efecto de los jaggies puede ser reducido por antialiasing, el cual suaviza los pixeles alrededor de los jaggies Tonos de gris en vez de transiciones fuertes de blanco a negro Disminuye la respuesta del SVH a transiciones fuertes (bandas de Mach)
Representando líneas: muestreo de puntos, pixel singular Algoritmo del punto medio: en cada columna, escoger el pixel con el centro más cercano a la línea Una forma de muestreo de puntos: muestrear la línea en cada uno de los valores X entero Escoger un solo pixel para representar la intensidad de la línea, completamente encendido o apagado Doblando la resolución en x y y sólo sirve de paliativo, ¡cuesta 4 veces más memoria, ancho de banda y tiempo de scan conversion! Nota: esto funciona para pendientes entre -1 y 1. Habría que usar filas en vez de columnas para el otro caso, o habrían huecos dentro de la línea. Aproximando la misma línea al doble de resolución Aproximación de línea usando muestreo de puntos
Representando líneas: muestreo de área Representar la línea como un rectángulo de ancho de una unidad, usa múltiples píxeles solapando el rectángulo (pensemos por ahora los píxeles como cuadrados)
En vez de completamente encendido o apagado, calcular cada intensidad del pixel proporcional al área cubierta por el rectángulo. Una forma de muestreo de área no ponderado: Sólo los píxeles cubiertos por la primitiva pueden contribuir La distancia del centro del píxel a la línea no importa Típicamente tienen más de un pixel por columna
“Filtro de caja” representa el muestreo de área no ponderado (Gp:)
“Filtro de cono” para muestreo de área ponderado Muestreo de área, pero la sobreposición entre el filtro y la primitva es ponderada tal que las sub-áreas de dA más cercanas al centro del pixel cuenten más El cono tiene: Caída lineal Simetría circular Ancho de 2 (llamado soporte) Volukmen de 1 (esto hacer que los pixeles completamente cubiertos tengan valor 1) La intensidad del pixel es el “subvolumen” dentro del cono sobre la línea (ver imagen)
Muestro de área ponderado (continuación) (Gp:) (Gp:) W
(Gp:) Soporte circular del filtro de 2 unidades (Gp:) Centro del pixel (+) (Gp:) Área de superposición entre soporte y primitiva (Gp:) Área diferencial dA2 (Gp:) Primitivea (Gp:) Área diferencial dA1
Otra mirada al muestreo de puntos Este algorimo simplista de scan conversion sólo pregunta si un punto matemático está dentro de la primitiva o no Malo para el detalle subpixel el cual es muy común en rendering de alta calidad, ¡donde pueden haber muchos más micro-polígonos que píxeles! Problemas del muestro de puntos. Muestras son señaladas como puntos negros. Objetos A y C son muestreados, pero objetos correspondientes B y D no. A B C D
Otra mirada al muestreo de área no ponderado (filtro de caja) Filtro de caja Soporte: 1 pixel Establece que la intensidad proporiconal al área de superposición Crea “parpadeo” en pixeles adyacentes (Gp:) (b)
Muestreo de área no ponderado. (a) Todas las subáreas del pixel son ponderadas igualmente. (b) Cambios en intensidades computadas a medida que el objeto se mueve entre pixeles.
Otra mirada al muestreo de área ponderado (filtro de pirámide) Filtro de pirámide Soporte: 1 pixel Aproxima un cono circular para enfatizar el área de sobreposición cercano al centro del pixel. Muestro de área ponderado. (a) sub-áreas del pixel son ponderadas diferentemente como función de la distancia al centro del pixel. (b) Cambios en intensidades computadas a medida que el objeto se mueve entre pixeles. (Gp:) (b)
Otra mirada al muestro de área ponderado (Filtro de cono) Filtro de cono Soporte: 2 pixeles Más suavidad en cambios de intensidad Muestreo de área ponderado con superposición. (a) Función tipica de ponderado. (b) Cambios en intensidades computadas a medida que el objeto se mueve entre pixeles.
Pseudocódigo y resultados for each pixel p: place filter centered over p for each pixel q under filter: weight = filter value over q p.intensity += weight * q.intensity (Gp:) Anti-aliased
(Gp:) Aliased
Demostración de crawlies
Ejemplo de anti-aliasing (Gp:) Acercamiento del original, render con alias
(Gp:) Filtro de blur – promedio ponderado de pixeles vecinos
(Gp:) Supersampling – muestrear múltiples puntos dentro de un pixel determinado y promediar resultado
(Gp:) Supersampling y blurring
Tablero de ajedrez con supersampling Antialiasing Techniques:
Muestreo de imágenes La conversión por escaneo (Scan converting) es la digitalización (muestreo) de una serie de functions de intensidad contínua, una por línea de scan. Usaremos líneas de escaneo (scan lines) singulares por simplicidad, pero todo sigue aplicando de igual manera a las imágenes. (Gp:) Scan line de una escena sintética
(Gp:) Scan line de una escena natural
(imagen cortesia de George Wolberg, Columbia University)
El flujo de trabajo de muestreo/reconstrucción/despliegue (imagen cortesia de George Wolberg, Columbia University)
Sístesis de ondas de Fourier La aproximación de un scan line de una imagen mejora con más sinusoides. Una señal puede ser aproximada sumando ondas en forma de seno (y coseno) con diferentes frecuencias, fases y amplitudes. Una señal tiene 2 representaciones. Estamos familiarizados con el dominio espacial, pero cada señal también existe en el dominio de frecuencia.
Frecuencia espectral de una señal Las sinusoides se caracterizan por su amplitud y frecuencia. La frecuencia de una sinusoide es el número de ciclos por segundo para audio, o el número de ciclos por longitud de unidad (ej., distancias entre pixeles) para imágenes. Se puede caracterizar cualquier forma de onda enumerando la amplitud y frecuencia de todas las sinusoidescomponentes (Transformada de Fourier) Esto puede ser graficado como un “espectro de frecuencias”, también conocido como espectro de poder, (generalmente ignoramos las frecuencias negativas, pero son necesarias para ser correctos matemáticamente) Para ver los dominios espaciales y frecuenciales de señales simples: http://www.cs.brown.edu/exploratories/freeSoftware/repository/edu/brown/cs/exploratories/applets/fft1DApp/1d_fast_fourier_transform_guide.html Signal Domain Frequency Domain
Muestreo: el Límite Nyquist Para capturar todas las frecuencias de una señal, debemos muestrear a una velocidad que sea más alta que 2 veces la frecuencia más alta de la señal (el límite Nyquist) Aquí hay una sinusoide aproximada:
La sinusoide muestreada a una velocidad aceptable (4 veces la frecuencia más alta):
Onda reconstruida basada en estas muestras:
Aliasing: conoce a vuestro enemigo El aliasing ocurre cuando muestreamos una señal a menos del doble de la frecuencia máxima. He aquí nuevamente nuestra onda sinusoidal análoga:
Aquí está la onda muestreada a una velocidad muy baja:
Aquí esta la onda reconstruida basada en esas muestras:
¡La reconstrucción ni siquiera se le acerca!
Aliasing en la vida real ¿Has visto alguna vez como giran los cauchos de un carro en una película? ¿Has notado que algunas veces parecieran que ruedan hacia atrás? Esto es porque la velocidad del video es más baja que el doble de la frecuencia en que las ruedas giran. Esto es aliasing temporal. Esto se ve mucho en películasporque el efecto es impactante.Se conoce como el efectostage-coach. Porsche Dyno Test
Muestreando al límite Nyquist Muestrear en el límite Nyquist puede también ser problemático He aquí nuevamente nuestra perfecta sinusoidal análoga:
He aquí la sinusoidal muestreada en el límite Nyquist. En esta ocasión funciona bien:
Aquí esta la onda sinusoidal muestreada en el límite Nyquist, con los puntos de muestra movidos. Ahora no tenemos señal:
Para un applet dedicado a ilustrar el límite Nyquist: http://www.cs.brown.edu/exploratories/freeSoftware/repository/edu/brown/cs/exploratories/applets/nyquist/nyquist_limit_guide.html
El enemigo es reconocido El aliasing se muestra en los últimos diagramas de las láminas previas – señales que son muestreadas a una velocidad muy baja pueden reconstruir las frecuencias altas como frecuencias bajas. Estas frecuencias bajas son “aliases” de las frecuencias altas. Los datos de la baja velocidad de muestreo no pueden representar adecuadamente los componentes de alta frecuencia, así que los representó incorrectamente, como frecuencias bajas. Así que, simplemente muestreamos encima del límite de Nyquist, verdad? Lamentablemente, no siempre podemos hacer esto ¿Qué tal esto?
Intentemos la síntesis de Fourier (Gp:) 5 (Gp:) 25 (Gp:) 125
Número de ondas sinusoidales:
Frecuencias infinitas
Frecuencias infinitas Mientras más frecuencias altas prefiltremos, más baja será la frecuencia de muestreo necesaria pero menor será el parecido de la señal filtrada con la original.
Nota: el prefiltrado suele abreviarse como filtrado, pero el prefijo “pre” nos ayuda a recordar que el post-filtrado (es decir, otra etapa del filtrado despues de la computación o transformación de la imagen) también se aplica. Si se hace en las muestras reconstruidas de la señal original, ¡será difuminada en los aliases presentes en la reconstrucción corrupta!
Aliasing de escalado, o “¿por qué tenemos que pre-filtrar?” Esto no se ve para nada bien. No hay tiras y ahora la imagen tiene un promedio más oscuro. (Gp:) Imagen original
(Gp:) Imagen con puntos de muestra marcados
(Gp:) Imagen escalada usando los puntos de muestra
(Gp:) Imagen original
Mejor, pero no es perfecto Aliasing de escalado II, o “Cerca, pero no hay premio” (Gp:) Imagen prefiltrada con muestras marcadas
(Gp:) Imagen prefiltrada escalada
Aliasing de escalado III, o “¿por qué está mal?” La imagen escalada con prefiltrado se veia un poco mejor, pero aún no podíamos ver las tiras El filtrado hizo que la imagen escalada tuviese el mismo brillo relativo, pero no tiras. El filtro eliminó las “frecuencias altas” de la imagen Las discontinuades que eran tiras Dado el número de puntos para representar la imagen una vez escalada, no habían suficientes puntos para representar las frecuencias altas Nunca podremos ser capaces de representar frecuencias más latas que ½ de nuestra velocidad de muestreo. No podemos tener algo mejor que esta representación difuminada. Recuerda el límite de Nyquist
Filtros de paso bajo(dominio espacial)
Filtro de paso bajo ideal(dominio de frecuencias)
Convolución http://www.cs.brown.edu/exploratories/freeSoftware/repository/edu/brown/cs/exploratories/applets/convolution/convolution_guide.html
Imagen tomada de http://es.wikipedia.org/wiki/Convoluci%C3%B3n
Ejemplo simple de convolución (Gp:) *
1111 ×1111 1111 1111 1111 +1111 1234321
Ejemplo animado de convolución Imagen tomada de http://es.wikipedia.org/wiki/Convoluci%C3%B3n
Ejemplo animado de convolución Imagen tomada de http://es.wikipedia.org/wiki/Convoluci%C3%B3n
Propiedades de la convolución Imagen tomada de http://en.wikipedia.org/wiki/Dirac_delta_function)
Filtros de paso bajo: convolviendo con sinc En teoría, sinc tiene extensión infinita, no importa las contribuciones pequeñas y partes negativas, pero pesa las contribuciones más fuertemente en el centro. En la práctica, sinc se aproxima decentemente con una distribución gaussiana normal, o incluso un triángulo, con extensiones finitas y pesos igual o mayores que cero. Señal original Filtro sinc Señal filtrada Operación del filtro en el origen, mostrado como punto negro
¿Qué hace el filtrado/convolución? Selecciona puntos para muestrear, ej., centro de pixeles Desliza el filtro sobre cada punto de muestra sucesivo y computa integral de la convlución en ese punto (el área bajo la curva) Este es el promedio ponderado del pixel actual y sus vecinos Los filtros gráficos más útiles son simétricos sobre su origen y caen rápidamente desde el centro) El promedio ponderadoes el valor del pixel para la imagen filtrada Nuestras ilustraciones son 2D, pero para pixeles uno debería pensar en sin como un mapa de ponderación trimidensional. Desde luego, no hacemos el cálculo de la integral como tal, sino que simplemente computamos los valores discretos de la función filtro y hacemos una multiplicación discreta y la sumamos al aproximado. El término “filtro” se usa estrictamente en el sentido de procesamiento de señales (el término se pueden emplear para transformaciones arbitrarias de una imagen, como en Photoshop) Sinc en 3D
Resumen de filtrado
Resumen de filtrado Para obtener un filtrado de paso bajo (es decir, filtrar frecuencias altas), solemos convolver con función triángulo en dominio espacial para aproximar al ideal sinc. Propiedades de la función triángulo: Fácil de calcular, a diferencia de sinc, el cual tiene soporte infinito (o incluso una aproximación Gaussiana a sinc) Su dual, sinc2, es una aproximación aceptable a la función caja aunque tiene extensión infinita Causará una representación imprecisa de todas las frecuencias y por lo tanto ocurre un grado de corrupción/aliasing. No es tan malo como usar una caja como filtro con sinc como su dual en la frecuencia de dominio En otras palabras, el muestreo de área con promedio ponderado de cualquier tipo, asumiendo que tenga un parecido con la forma de un cono, es mejor que un muestreo de área sin ponderar con un filtro de caja; que a su vez es mejor que un muestreo de punto.
El pipeline de filtrado