El poder de las matemáticas y la computación

Autor: Wilfredo Orozco (*)

Breve nota en la que el autor nos cuenta su experiencia al aplicar un poderoso algoritmo computacional para el cálculo de la Transformada de Fourier.

Luego de pasar varias semanas en casa debido a distintas circunstancias, me animé y después de más de diez años volví a un viejo amor: la programación. Estuve desempolvando viejos (en realidad muy viejos) programas, e instalando compiladores. Hace tiempo había visto en la web cómo eliminar patrones repetitivos en una imagen a través de una herramienta matemática conocida como la «Transformada Discreta de Fourier» (TDF). Los resultados obtenidos al aplicar esta técnica me parecieron simplemente alucinantes. Pero, ¿eran verdaderas las imágenes que aparecían en algunos informes sobre los usos de la TDF, o eran en realidad imágenes convenientemente retocadas? Por eso, para no tener dudas, decidí apuntar ahí. Volver a programar después de tanto tiempo me resultó bastante complicado, porque el cerebro se acostumbra a no complicarse con problemas matemáticos y/o lógicos. Por suerte de a poco pude resucitar viejas habilidades (que creía definitivamente perdidas…), y comenzaron a surgir ideas.

El punto débil del cálculo directo de la Transformada Discreta de Fourier a través de la fórmula que la define, es el tiempo que tarda una computadora en realizar todos los cálculos necesarios (en realidad operaciones con números complejos). Para una imagen pequeña, por ejemplo, de tamaño 256 x 256 píxeles, una computadora moderna corriendo a 3 GHz puede demorar unos 6 minutos en calcular la TDF. Para imágenes de mayor tamaño, el cálculo de la TDF simplemente se vuelve muy penoso, ya que el número de multiplicaciones complejas que es necesario realizar es igual al cuadrado del número de datos.

Por suerte existe un algoritmo para el cálculo eficiente y veloz de la TDF, denominado justamente Transformada Rápida de Fourier o en inglés «Fast Fourier Transform» (FFT), propuesto por James Cooley y John Tukey en 1965. Este famoso y bien conocido algoritmo es en realidad una reinvención independiente de la metodología empleada por el astrónomo alemán Carl Friedrich Gauss a principios del Siglo XIX, para sus cálculos de las órbitas de asteroides y cometas a partir de un número reducido de observaciones. 

La implementación de la FFT que realicé, se basa en el algoritmo estándar de Cooley-Tukey de base-2. El programa fue codificado en el lenguaje C++, y pude incorporar algunos trucos de programación para que el algoritmo pudiera correr lo más rápido posible. No vale la pena describir el algoritmo, ya que en la web hay una muy abundante literatura al respecto. Lo que sí deseo destacar es el rendimiento alcanzado en la implementación de este algoritmo. Durante las pruebas, el cálculo de la FFT de una imagen de dimensiones 256 x 256 píxeles fue realizada en 30 milisegundos (!). Como mencioné con anterioridad, una computadora podría tardar unos 6 minutos en realizar la misma tarea, pero de modo directo. Y este dramático cambio en la velocidad de procesamiento datos al aplicar la FFT es, en verdad, asombroso.

(*) Editor del sitio Espacial.org

Izquierda: Imagen original
Centro: Imagen procesada
Derecha: Módulo de la Transformada de Fourier.
Las regiones en rojo corresponden a aquellas
frecuencias que han sido eliminadas o atenuadas.

buscadores: digital image processing, patterns, FFT, IFFT, inverse, Shroud of Turin, Sudario, tramas periódicas