Transformada rápida de Fourier y su aplicación en tratamiento de imágenes y audio

1

Transformada rápida de Fourier y su aplicación en tratamiento de imágenes y audio Fast Fourier Transform and its application in image processing and audio Autor: Angie Vanessa Jaramillo Castrillón Facultad de Ingenierías, programa de sistemas y computación Universidad Tecnológica de Pereira Correo: [email protected]

Resumen— la FFT es la forma optimizada de la DFT, logrando así menos complejidad en sus algoritmos pudiéndose aplicar en temas “complejos” para realizar sus procedimientos de un manera más fácil o más analítica. Sus diferentes e innumerables aplicaciones dan a demostrar su gran efectividad en el campo de la ciencia y la ingeniería. Su énfasis en el tratamiento de imágenes y audio permite el análisis de datos retornando patrones que con análisis detallado se pueden desarrollar grandes aplicaciones. Palabras clave— FFT, DFT, minucias, frecuencia de muestreo, patrón. Abstract— the FFT is the optimized form of the DFT, achieving less complexity in their algorithms and can be applied to "complex" issues to make their procedures easier or more analytical way. Its various and innumerable applications give demonstrate its great effectiveness in the field of science and engineering. His emphasis on imaging and audio data analysis allows returning detailed analysis patterns that can develop large applications. Key Word — FFT, DFT, minutiae, sampling frequency, pattern.

I.

INTRODUCCIÓN

Jean Baptiste Joseph Fourier (Auxerre, Francia, 21 de marzo de 1768 – París, 16 de mayo de 1983), matemático y físico francés conocido por sus trabajos sobre la descomposición de funciones periódicas en series trigonométricas convergentes llamadas series de Fourier, método con el cual consiguió resolver la ecuación del calor. La transformada de Fourier recibe su nombre en su honor. FFT es la abreviatura usual del inglés Fast Fourier Transform de un eficiente algoritmo que permite calcular la transformada discreta de Fourier y su inversa.

La transformada rápida de Fourier es la versión más rápida de la transformada discreta de Fourier (DFT). La FFT utiliza algunos algoritmos inteligentes para hacer lo mismo que la DFT pero en mucho menos tiempo. La DFT es extremadamente importante en el área del análisis de la frecuencia debido a que se necesita una señal discreta en el dominio del tiempo y que transforma la señal en su representación de dominio de frecuencia discreta. La FFT es de gran importancia en una amplia variedad de aplicaciones mencionaré algunas como:  Tratamiento de imagen (jpeg) y audio (mp3).  Reducción de ruido en señales, como el ruido blanco.  Análisis en frecuencia de cualquier señal discreta.  Análisis de vibraciones.  Análisis de materiales y estadística.  Síntesis, mediante la transformada inversa.  Procesamiento de imagen lineal.  Técnicas de imagen especial.  Redes neuronales.  Comprensión de datos.  Procesamiento de señales digitales.  Software DSP.  Propagación del calor (fundamentos de la termodinámica).  Algoritmo de encriptación.  Complejidad computacional. En este artículo haré énfasis sobre la aplicación de la FFT en tratamiento de imagen y audio. II.

CONTENIDO

A. Contexto 1. Tratamiento digital de imágenes.

2 El tratamiento digital de imágenes es un campo en constante evolución en su vertiente tecnológica, tanto en capacidad de procesamiento y transmisión con crecimiento exponencial, pero también por el gran avance que han experimentado las técnicas de procesado digital en áreas como el filtrado compresión y análisis de imágenes. Las aplicaciones actuales del Tratamiento Digital de Imágenes son prácticamente innumerables y prometen deparamos grandes sorpresas en un futuro próximo. La televisión digital, los videojuegos, la telefonía móvil, el cine de animación, son solo algunos ejemplos del impacto que tiene actualmente en la sociedad de consumo. En el ámbito industrial y de servicios destacan las aplicaciones de visión artificial en inspección y robótica, así como el desarrollo espectacular que ha producido en la generación y tratamiento de imágenes médicas. Desde una perspectiva histórica, el Tratamiento Digital de Imágenes representa una generalización multidimensional de las técnicas de tratamiento digital de la señal unidimensional. Los orígenes del procesamiento digital de la señal se remontan al siglo XIX, aunque su desarrollo práctico no se produce hasta la década de los años 60, cuando Cooley y Tukey propusieron un algoritmo eficiente para el cálculo de la transformada de Fourier: La FFT (Fast Fourier Transform). Después, con la irrupción de los microprocesadores, se diseñaron procesadores adaptados para el cálculo de FFT’s, los denominados DSP’s. Estas dos circunstancias han sido decisivas para que se produjera el espectacular avance del procesamiento digital de la señal, que hoy día, ha penetrado en todos los sectores de la sociedad y, especialmente, en el tratamiento digital de imágenes. 2. Tratamiento digital de sonido. El almacenamiento y reproducción puede hacerse usando dos criterios: magnetófono y partitura. 2.1 Magnetófono (Sistema de muestreo) El sistema magnetófono digitaliza la onda por el procedimiento de anotar repetidamente su amplitud en intervalos de tiempo muy pequeños; es el denominado sistema de muestreo. En todos los casos la onda es transformada en una serie de valores numéricos que se almacenan en un fichero. Posteriormente el fichero puede ser leído por un programa especial, y sus datos enviados secuencialmente a un dispositivo que es capaz de regenerar una tensión eléctrica proporcional a los valores (numéricos) recibidos, de forma que se asemeja a la forma de onda original. La tensión producida es entregada a su vez a un altavoz que la transforma finalmente en “sonido”. 2.2 Partitura El sistema partitura utiliza un lenguaje especial, parecido al de los músicos, para almacenar información sobre cada nota. Es

un lenguaje adaptado a las necesidades de la representación del sonido. El “fuente” es un partitura electrónica que indica cuando se debe sonar un nota, por cuanto tiempo, con que volumen y cómo debe terminar. Después de un cierto proceso de compilación, en vez de producir un ejecutable normal, producen un sonido binario. Es decir, un fichero .wap, .au, .snd, .mid, .mp3, .aiff entre otros. B. Ejemplo tratamiento de imágenes: Reconocimiento de huellas dactilares. La huella dactilar tiene características únicas llamadas minucias, las cuales son puntos donde los bordes terminan o se dividen. El sistema de reconocimiento consiste de siete pasos: Adquisición, Etapa de Preprocesamiento, Aclaración, Adelgazamiento, Extracción de Minucias, Reconocimiento y algunas veces una etapa de Verificación. 1.

Etapa de Preprocesamiento.

Para evitar posibles errores en el reconocimiento, la información en los extremos será eliminada, para poder asegurar que solamente la información central sea procesada al momento de la extracción de minucias. En caso de que esta distorsión no fuera eliminada, el algoritmo podría detectar falsas minucias. Por lo tanto, la imagen fue recortada en un 10% en cada uno de sus lados tomando en cuenta que esto no elimina información importante de la huella dactilar por lo mencionado anteriormente. 2.

Aclaración.

El objetivo de un algoritmo de aclaración es mejorar la claridad de la estructura de los bordes en las regiones recuperables y marcar las regiones no-recuperables con demasiado ruido para un posterior procesamiento. La mayoría de las técnicas existentes están basadas en el uso de filtros contextuales cuyos parámetros dependen de la frecuencia y orientación de los bordes locales. Los filtros pueden ser definidos en el dominio de Fourier o en el dominio espacial. En este trabajo se utilizó una combinación de filtros en los dos dominios para una mejor aclaración. 2.1 Filtro en el dominio espacial El filtro incrementa el contraste en una dirección perpendicular a los bordes mientras realiza un alisamiento en la dirección de los bordes. Los filtros de Gabor tienen una propiedad importante que consiste en una óptima resolución de frecuencia. La función simétrica de Gabor tiene la forma de la ecuación (1):

3 2.2 Filtro en dominio de Fourier. Cada imagen es convolucionada con filtros precalculados del mismo tamaño que la imagen. Sin embargo, el algoritmo asume que la frecuencia de los bordes es constante a lo largo de la imagen con el fin de evitar tener un gran número de filtros precalculados. Por lo tanto, el algoritmo no utiliza toda la información contextual proporcionada por la imagen de la huella dactilar. Watson propuso otra técnica de aclaración completamente en el dominio de Fourier. En esta técnica la imagen es dividida en bloques los cuales son traslapados, la imagen aclarada es obtenida con las ecuaciones (2) y (3):

posible en el reconocimiento. Así, la información que se almacena de la huella dactilar consiste en una matriz de tamaño 4x500. La matriz se compone de 500 vectores y cada vector de 4 valores que consisten de las dos coordenadas de la primer minucia, la distancia a la siguiente minucia y el ángulo de la primer minucia con respecto al eje Y. Por lo tanto, el tamaño total de nuestra matriz almacenada es de 1000x500 (5 huellas por persona y 50 personas diferentes). 6.

Etapa de verificación

Esta etapa consiste en analizar la dirección y el número de píxeles que fue movida la imagen de entrada. Cuando dos imágenes de la huella dactilar de una misma persona son comparadas y una de estas imágenes está trasladada, todas las minucias de la huella dactilar se mueven en la misma dirección y la misma cantidad de píxeles. C. Ejemplo de reconocimiento de audio: Reconocedor de voz mediante el uso de la FFT.

3.

Adelgazamiento.

Después del proceso de aclaración la imagen es binarizada, es decir, está formada de ceros y unos, donde un “1” significa un píxel blanco y un “0” significa un píxel negro. El algoritmo consiste en encontrar píxeles internos en nuestra imagen y después eliminar los píxeles límite. Este proceso es realizado hasta no encontrar más píxeles internos. 4.

Haciendo uso de un programa implementado en MATLAB: se graban dos segundos de audio con una frecuencia de muestreo de 20KHz. La grabación da como resultado un vector de 40 mil datos, de los que se discriminarán los datos significativos mediante un umbral de 0.1. Con base en el vector de datos obtenidos, se realiza el siguiente procesamiento: 1.

Aplicar el filtro de preénfasis para acentuar las frecuencias altas de la señal de voz, debido a que el modelo de tracto vocal utilizado no filtra adecuadamente las señales de frecuencia alta, no sonoras: las consonante, sonoras: las vocales. El filtro de preénfasis está dado por la ecuación (1).

2.

Segmentar la señal en tramos de 20 a 30ms, puesto que en este período de tiempo se considera a la señal de voz como estacionaria. En este proyecto, se fracciona en tramos de 24ms, por lo tanto, cada vector resultante tiene 480 datos y, se analiza utilizando un overlap de 80 datos. Para ellos usamos la ecuación (2) y podemos visualizar en la figura 1.

Extracción de minucias

El algoritmo consiste en calcular el número de píxeles que cruzan el píxel central (Pc), esto se calcula con la ecuación (4):

Esta es la razón por la cual se ha propuesto combinar dos etapas de aclaración y de esta forma evitar que algunas minucias sean eliminadas durante el proceso. 5.

Etapa de reconocimiento.

El reconocimiento se realizó con tres importantes características: coordenadas, distancia y ángulos. La razón de usar tres características es poder obtener el mínimo error ____________________________

4

3.

Aplicar una ventana Hamming a cada tramo de datos, para así eliminar las discontinuidades provocadas al segmentar, ya que éstas podrían llegar a interpretarse como altas frecuencias. En la ecuación (3) se resume lo antes mencionado.

El contenido debe tener capítulos y subcapítulos enumerados con números arábigos, tipo de letra Times New Roman de 10 puntos en negrita. debe definir su procedencia. III. 

4.

Obtener la FFT de cada tramo ecuación (4), con el objetivo de generar una superficie en la que se pueda observar las frecuencias y su variación en el tiempo (figura 2). Se promedian las FFT de cada tramo, para obtener un patrón de la palabra pronunciada (figura 3).

  

CONCLUSIONES

La FFT presentada bueno resultados analizando las minucias en huella dactilares cerca de las regiones de alta curvatura. La combinación de la FFT y los filtros de Gabor generan un reconocimiento de minucias casi completo. La FFT permite observar las frecuencias y sus variaciones en el tiempo permitiendo decodificar un audio entregado. Un promedio de FFT retorna un patrón de audio.

REFERENCIAS Libros: 

The Scientist and Engineer’s Guide to Digital Signal Processing, second edition, Steven W. Smith.

Artículos: 



Reconocimiento de huellas dactilares usando características locales, Gualberto Aguilar, Gabriel Sánchez, Karina Toscano, Mariko Nakano, Héctor Pérez. Reconocedor de voz mediante el uso de la FFT, Andrés Fuentes Hernández, Álvaro Anzueto Ríos.

5 Links:     

http://www.zator.com/Hardware/H10_2.htm http://cv1.cpd.ua.es/ConsPlanesEstudio/cvFichaAsiE EES.asp?wlengua=C&wcodasi=20024 http://www.phys.nsu.ru/cherk/fft.pdf http://www.phys.nsu.ru/cherk/fft.pdf http://es.wikipedia.org/wiki/Transformada_r%C3%A 1pida_de_Fourier

Anexos:  

Imagen: canes.jpg Txt: aplicativosFFT.txt

____________________________