Aliasing

Esta entrada voy a dedicarla a explicar, espero que de manera sencilla, a ese gran desconocido del mundo digital: el aliasing.

Puede que a muchos de vosotros no os suene este término, pero de lo que si estoy convencido con total seguridad es que alguna vez habeis visto o sufrido algo parecido a esto

Este efecto se denomina aliasing y en líneas generales se produce en la digitalización de señales analógicas, consecuencia de realizar un muestreo deficiente de la misma.

No me entero, ¿qué es lo está pasando en el vídeo? 

Aquí va el intento de explicación. Las cámaras de vídeo ven el mundo como una secuencia de imágenes, a diferencia de como lo percibimos nosotros a través de nuestro ojo. En el caso de las digitales, esta secuencia se graba en su memoria a razón de unos 30 fps (imágenes por segundo), es decir, aproximadamente una imagen cada 0,034 segundos. Como consecuencia de esto, aquellos movimientos que sufren variaciones en lapsos de tiempo menores que 0,034 segundos, como puede ser el caso del vídeo anterior, no pueden ser captados correctamente por la cámara.

Esto puede resumirse de la siguiente manera

El número de fps limita las variaciones u oscilaciones que una cámara puede percibir.

Veamos estas limitaciones con un sencillo ejemplo. Supongamos que nos encontramos en una situación similar a la del vídeo. En este supuesto, estimamos que la frecuencia de giro de la hélice es de 29 Hz, esto es, 29 vueltas por segundo. Si nuestra cámara de vídeo es capaz de grabar 30 fps, ¿qué secuencia de imágenes obtendremos? Para responder a esta pregunta nos serviremos de un toy model, una aproximación matemática que nos permita simplificar el problema.

El giro de una hélice (en sentido antihorario) de frecuencia de giro \omega_0 puede modelizarse mediante la curva

\displaystyle h(t)=(\cos\,2\pi\omega_0 t,\sin\,2\pi\omega_0 t)  para \displaystyle t\geq 0

En nuestro caso, \omega_0 = 29 Hz. Sabemos además que la cámara no sigue el movimiento continuo de la hélice, sólo la sigue en un conjunto discreto de imágenes, de manera específica en los instantes t = 0, 1/30, 2/30\ldots Por tanto, realmente vemos la secuencia de puntos

\displaystyle h(n)=\left(\cos\left(2\pi\cdot 29\cdot\frac{n}{30}\right),\sin\left(2\pi\cdot 29\cdot\frac{n}{30}\right)\right)  para \displaystyle n\geq 0

Para cada una de las componentes del movimiento puede escribirse

\displaystyle\cos\left(2\pi\cdot 29\cdot\frac{n}{30}\right) = \cos\left(2\pi n-2\pi\frac{n}{30}\right) = \cos \left(\frac{2\pi n}{30}\right)

\displaystyle\sin\left(2\pi\cdot 29\cdot\frac{n}{30}\right) = \sin\left(2\pi n-2\pi\frac{n}{30}\right) = -\sin \left(\frac{2\pi n}{30}\right)

De aquí se tiene que

\displaystyle h(n) = \left(\cos \left(\frac{2\pi n}{30}\right),-\sin \left(\frac{2\pi n}{30}\right)\right)

Este cálculo nos revela algo sorprendente, ¡la cámara nos muestra la hélice moviéndose a una frecuencia de -1 Hz, es decir, una vuelta por segundo en sentido horario!

Este truco que hemos hecho escribiendo 29 = 30 -1, y unas cuantas propiedades trignométricas, puede hacerse de manera general y obtener las siguientes conclusiones acerca de la grabación de la cámara:

  • Para frecuencias con 30>|\omega_0| >15 el giro de la hélice se invierte.
  • Para frecuencias |\omega_0 |<15 el movimiento se representa correctamente.
  • Para rotaciones por encima de 30 Hz la frecuencia se reduce módulo 30 y cae en alguno de los casos anteriores.
  • Las frecuencias múltiplos de 15 Hz son casos degenerados del movimiento en los que la hélice permanece inmóvil o casi.
Movimiento circular de frecuencia variable. A la derecha, la segunda componente del movimiento, un seno.

En el vídeo anterior tenemos un pequeño experimento numérico en el que observamos distintas formas de aliasing, consecuencia del aumento progresivo de la frecuencia del movimiento circular. Al llegar a 29 Hz no observamos 29 vueltas por segundo, sino una por segundo y en sentido horario.

Las conclusiones anteriores nos animan a formular la siguiente conjetura

Una cámara, de velocidad de grabación \omega_r fps, graba correctamente si esta velocidad es mayor que el doble de la máxima frecuencia \omega_0 de los movimientos que haya en escena.

Esto es, si se cumple

2|\omega_0| < \omega_r

¿Qué consecuencias traería esta conjetura? Básicamente, que si nos propusieramos grabar el batir de alas de un colibrí (los más rápidos lo hacen unas 80 veces por segundo) deberíamos asegurarnos de hacerlo con una cámara que pudiera grabar a unos 170 fps para evitar el aliasing.

Pues bien, la anterior conjetura tiene nombre, apellidos y padres

Teorema de Muestreo de Whittaker-Shannon

Probado primero en 1935 por el matemático inglés Edmund T. Whittakerredescubierto años después, en 1949, por el matemático estadounidense Claude E. Shannon.

Dicho resultado establece bajo qué condiciones un muestro de una señal f(t), por ejemplo señales analógicas de audio y vídeo, puede usarse para recuperar toda la señal. Concretamente el teorema afirma que si el soporte de la transformada de Fourier de la señal f(t) cumple

\displaystyle\text{sop } \hat{f}(\xi) \subset [-\pi/T, \pi/T],

donde \omega_s = T^{-1} es la frecuencia de muestreo (la velocidad a la que graba la cámara), entonces

\displaystyle f(t)=\sum_{n=1}^\infty f(nT)\text{ sinc}\left(t - nT\right)  donde  \displaystyle \text{sinc }t=\frac{\sin (\pi t/T)}{\pi t/T}

Observamos que la condición sobre el soporte de \hat{f}(\xi) es equivalente la condición 2|\omega_0| < \omega_r. Basta escribir 2\pi\omega=\hat{f}(\xi), donde podríamos decir que \omega viene dado en vueltas por segundo mientras que \hat{f}(\xi) viene en radianes por segundo. Con esto obtenemos la condición

\displaystyle \text{sop }\omega \subset [-\omega_r/2,\omega_r/2]

análoga a la obtenida en nuestra ejemplo. El valor |\omega_r|/2 se denomina frecuencia de Nyquist, debida al matemático sueco Henry Nyquist.

 Una demostración de este resultado puede encontrarse en el libro de Stéphane MallatA Wavelet Tour of Signal Processing.

Para terminar, un pequeño apunte.

Hasta ahora hemos visto aliasing temporal, efecto que se produce por la discretización temporal del movimiento. Pero como era de esperar, existe aliasing espacial. Este efecto se produce al realizar una discretización espacial deficiente y salvo el nombre, no hay ninguna diferencia matemática entre los dos.

La imagen anterior presenta la función f(x,y) = \cos\left(30\pi (x^2 + y^2)\right) en el dominio [-1,1]\times[-1,1] para dos discretizaciones espaciales distintas. La imagen derecha se muestra sobre una discretización 20 veces mas fina que la imagen de la izquierda.

El alias que se ve en la imagen izquierda, y tal vez un poco en la derecha (aunque en el tamaño original no se ve), se debe a que nuestra onda f(x,y) tiene una frecuencia variable \omega_0 = 15 \sqrt{x^2+y^2}. Crece a medida que nos alejamos del origen.

Una vez pasamos la frecuencia de Nyquist, la frecuencia máxima que podemos representar en esa discretización sin la formación de aliasing, vemos las frecuencias superiores reducidas módulo la frecuencia de Nyquist. Se empieza a presentar cierta periocidad.

En alguna entrada posterior espero poder hablar un poco acerca de formas de reducción del aliasing: los métodos de anti-aliasing.

Esta entrada participa en El Carnaval de las Matemáticas de Febrero de 2012, que tiene por anfitriones a Scientia potentia est.

Anuncios
Esta entrada fue publicada en Uncategorized. Guarda el enlace permanente.

3 Responses to Aliasing

  1. Pingback: Resumen del Carnaval de Matemáticas Edición 3.1 (actualizándose) | Scientia potentia est

  2. Pingback: ¡A votar! (Carnaval de Matemáticas 3.1) | Scientia potentia est

  3. Pingback: Gotas vibrantes y aliasing. | Scientia potentia est

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s