LA TRANSFORMADA RAPIDA DE FOURIER SUS USOS Y SU APLICACIN

ResumenEl presente documento comprende la investigacin sobre los fundamentos matemticos, algoritmos y aplicacin prctica en el procesamiento de imgenes de la Transformada de Fourier, y la difusin a travs de la elaboracin de un texto orientado a los estudiantes de Informtica, Sistemas o ramas afines, ya que la implementacin de la Transformada Rpida de Fourier (ms conocida como FFT por sus siglas en ingls).IntroduccinLa Transformada de Fourier es una herramienta matemtica que tiene un uso muy amplio en lo referente al tratamiento digital de seales, se encuentra implementada bajo la forma de dispositivos electrnicos de reconocimiento de voz e imagen; puede ser aplicada a varios campos como anlisis espectral, ecuaciones diferenciales, resolucin de problemas elsticos estacionarios y dinmicos, etc.Este documento, enlaza los aspectos tericos con la aplicacin prctica de la Transformada de Fourier en el procesamiento digital de imgenes mediante el desarrollo de aplicaciones que implementan los algoritmos de la Transformada Rpida de Fourier, los mismos que son explicados y analizados de una manera clara y didctica. ImportanciaEl desarrollo matemtico de la transformada de Fourier fue explicado por Jean Baptiste Joseph Fourier, en su libro la Teora Analtica del Calor, publicado en 1822; posteriormente, en 1965 Cooley y Tukey publicaron su artculo Un algoritmo para calcular las Series de Fourier Complejas, el cual es conocido como algoritmo FFT (Fast Fourier Transform) y que con el desarrollo acelerado de las computadoras digitales ha permitido la aplicacin de la FFT a diferentes campos.Su aplicacin al procesamiento de imgenes se encuentra documentado en los libros especficos sobre la materia a un nivel terico, en los que no se expone directamente, la forma de implementacin de los diferentes algoritmos, y en el mejor de los casos presentan una descripcin narrativa del algoritmo, como ejemplo se puede revisar el libro Digital Image Processing de Gonzlez y Woods. Por otra parte, los libros especficos sobre la Transformada Rpida de Fourier, se centran su aplicacin mayormente a la fundamentacin matemtica y explicacin de los algoritmos, presentando aplicaciones ms orientadas al Procesamiento Digital de Seales, que corresponde al campo de la Electrnica.Objetivo del estudioCon las consideraciones anteriores, el presente documento, rene en una serie de fundamentos matemtica, los algoritmos de la transformada Rpida de Fourier, y la aplicacin de los mismos al procesamiento de imgenes mediante el desarrollo de software que muestra como se implementan dichos algoritmos.Diseo de InvestigacinPara el desarrollo de la investigacin se aplic el mtodo lgico deductivo, el cual permiti desarrollar y explicar los fundamentos matemticos de la FFT, tambin se utiliz el mtodo do experimental, para comprobar los resultados arrojados por los algoritmos implementados al aplicarlos en las imgenes digitales.Para la realizacin del proyecto fue necesario identificar la bibliografa especializada en dos reas: transformada Rpida de Fourier y Procesamiento Digital de Imgenes, la misma que se anexa.

Algoritmos de la Transformada Rpida de FourierLa transformada discreta de Fourier en una dimensin est dada por:

Donde x(n) es el conjunto de datos original X(u) es la transformada de x(n)N es el nmero de elementosu representa la variable en el dominio de la frecuencia Y su extensin a dos dimensiones est definida por

Partiendo de estas definiciones se analizaron los algoritmos en diferentes fuentes bibliogrficas y se implementaron en Visual Basic.Net los siguientes: Para una dimensin Mtodo directo: el cual implementa directamente la definicin de la transformada discreta en una dimensin. Mtodo recursivo: el cual est basado en el algoritmo FFT propuesto por Cooley y Tukey. Mtodo iterativo, tambin basado en el algoritmo anterior, y que presenta una mayor complejidad, puesto que requiere de la implementacin del algoritmo de reversin de bits de un arreglo.

Un prototipo de esta implementacin se muestra a continuacin.

Implementacin de las aplicaciones de la FFT

Usos y aplicaciones: Tratamiento de imagen (JPEG) y audio (MP3) Reduccin de ruido en seales, como elruido blanco Anlisis en frecuencia de cualquier seal discreta Anlisis de materiales yestadstica

Ejemplo:function []=fftej7(N,D) [ref.4]

% fftej7(N,d)% x(t)=exp(-2*t)*sin(2*pi*3*t)%

ts=D/N;d=ts/10;t=0:ts:D-d;x=exp(-2*t).*sin(2*pi*3*t);

X=fft(x);

% ReordenarM=N/2;Xaux=X;X(M+1:N)=Xaux(1:M);X(1:M)=Xaux(M+1:N);

% Separar Modulo y Fase de los coeficientes X(k)Xm=abs(X)*ts;Xf=unwrap(angle(X))*180/pi; %En grados

% Transformar Indices k en frecuenciasfaux(M+1:N)=0:M-1;faux(1:M)=-M:-1;f=faux/D;

% Reconstruir los muestreos originales a partir de los X(k)xr=zeros(1,N);for i=1:Nfor k=1:Nxr(i)=xr(i)+X(k)*exp(j*2*pi*f(k)*ts*(i-1));endendxr=xr/N;

%Plotsfigure;lines(t,x,'oc5','-c5');hold on;lines(t,xr,'xc3','-c3');zoom;title('Puntos de muestreo (o) y Reconstruccin a partir de X[k] (x)');xlabel('Tiempo (s)');ylabel('x(t)');

figure;lines(f,Xm,'oc5','-c5');zoom;title('Mdulo de los coeficientes espectrales de x(t)');xlabel('Frecuencia (Hz)');ylabel('|X[k]|'); figure;lines(f,Xf,'oc3','-c3');zoom;title('Fase de los coeficientes espectrales X[k]');xlabel('Frecuencia (Hz)');ylabel('Fase X[k]');

%Reconstruccion de la seal original a partir de los X(k)%Utilizamos un mayor nmero de puntos ts=ts/10ts=1/64;d=ts/2;t=0:ts:2*D-d;x=exp(-2*t).*sin(2*pi*3*t);Ns=length(x);

xr=zeros(1,Ns);for i=1:Nsfor k=1:Nxr(i)=xr(i)+X(k)*exp(j*2*pi*f(k)*ts*(i-1))/N;endend

%plots

figure;plot(t,x,'g-');hold on;plot(t,xr,'r--');zoom;title('Comparacin entre x(t) y su reconstruccin a partir de X[k]');xlabel('Tiempo (t)');ylabel('x(t)');

FILTROS DIGITALES

Un filtro digital es un sistema que, dependiendo de las variaciones de las seales de entrada en el tiempo y amplitud, se realiza un procesamiento matemtico sobre dicha seal; generalmente mediante el uso de la Transformada rpida de Fourier; obtenindose en la salida el resultado del procesamiento matemtico o la seal de salidaEl filtrado digital consiste en la realizacin interna de un procesado de datos de entrada. El valor de la muestra de la entrada actual y algunas muestras anteriores (que previamente haban sido almacenadas) son multiplicadas por unos coeficientes definidos. Tambin podra tomar valores de la salida en instantes pasados y multiplicarlos por otros coeficientes. Finalmente todos los resultados de todas estas multiplicaciones son sumados, dando una salida para el instante actual. Esto implica que internamente tanto la salida como la entrada del filtro sern digitales, por lo que puede ser necesaria una conversin analgicodigital o digitalanalgico para uso de filtros digitales en seales analgicas.Los objetivos comunes del proceso de filtrado son mejorar la calidad de la seal, comnmente se usa para atenuar o amplificar algunas frecuencias, por ejemplo se puede implementar un sistema para controlar los tonos graves y agudos del audio del estreo del auto, removiendo o atenuando el nivel de ruido, extrayendoInformacin de dos o ms seales previamente combinadas para hacer uso eficiente de un canal de comunicacin, etc.El procesamiento interno y la entrada del filtro sern digitales, por lo que puede ser necesario una conversin analgica-digital o digital-analgica para uso de filtros digitales con seales analgicas.

Podemos darnos cuenta que la tendencia actual es la migracin de la tecnologa analgica a la digital, en este caso el filtrado digital ofrece varias ventajas con respecto a los filtrados analgicos: El ancho de banda de un filtro digital esta limitado por la frecuencia de muestreo, mientras que en un filtro analgico, este parmetro depende de las caractersticas de los componentes fsicos. Se pueden implementar tanto en software como en hardware.La gran ventaja de los filtros digitales sobre los analgicos es que presentan una gran estabilidad de funcionamiento en el tiempo.

TIPOS DE FILTROSHay varios tipos de filtros as como distintas clasificaciones para estos filtros:

De acuerdo con la parte del espectro que dejan pasar y que atenan hay: Filtros pasa alto. Filtros pasa bajo. Filtros pasa banda.

De acuerdo con el tipo de respuesta ante entrada unitaria: FIR (Finite Impulse Response) IIR (Infinite Impulse Response) TIIR (Truncated Infinite Impulse Response)

De acuerdo con la estructura con que se implementa: Directa Transpuesta Cascada Fase Lineal Laticce

FILTROS IIR (Filtros con respuesta al Impulso de longitud infinita)

La forma de obtener en general la salida en este tipo de filtros es mediante formulas recursivas, una de las particularidades de estos filtros respecto a los tipo FIR es el hecho de que su comportamiento respecto a la fase es peor. Esta respuesta impulsiva h[n], n = 0, 1, 2, . . . caracteriza completamente el filtro, a punto tal que las seales de entrada y salida estn relacionadas por la suma de convolucin, que para filtros IIR toma la forma:

Al observar esta ecuacin podemos evidenciar que la suma convolucin no es adecuada para esta clase de filtros debido a que la respuesta impulsiva es muy larga (en teora, infinitamente larga). Por ello, los filtros IIR se implementan con ecuaciones a diferencia que permiten calcular las muestras de salida en forma recursiva:

El nmero N es el orden del filtro, y fija la cantidad de modos de la respuesta impulsiva. En la ecuacin podemos ver que la salida y[n] es funcin de los valores actuales y pasados de la entrada, y de valores pasados de la salida (de ah el nombre recursivo), por lo tanto el filtro IIR es sistema realimentado.Aplicando la transformada Z a la respuesta impulso:

Diseo de filtros IIRLas formas habituales de disear este tipo de filtros son:Indirecta (a partir de prototipos analgicos) Impulso invariante Aproximacin de derivadas Transformacin bilineal

Directa Aproximacin de Pad Aproximacin de mnimos cuadrados

FILTROS FIR (Filtros con respuesta al Impulso de longitud finita)Se trata de un tipo de filtros digitales en el que, como su nombre indica, si la entrada es una seal impulso la salida tendr un nmero finito de trminos no nulos. Su expresin en el dominio n es:

En la expresin anterior (N) es el orden del filtro, que tambin coincide con el nmero de trminos no nulos y con el nmero de coeficientes del filtro. Los coeficientes son ( ). La seal a la salida y[n] slo depende de los valores pasados de la entrada x(n).Aplicando laTransformada Z a la respuesta impulso.

Diseo de filtros FIRPara resumir hay tres mtodos bsicos para disear este tipo de filtros:Mtodo de las ventanas. Las ms habituales son: Ventana rectangular Ventana de Barlett Ventana de Hanning Ventana de Hamming Ventana de Blackman Ventana de Kaiser

Muestreo en frecuencia. Rizado constante (Aproximacin de Chebyshev y algoritmo de intercambio de Remez).

La decisin difcil es optar entre FIR o IIR. En aquellos casos en que las propiedades de los FIR (respuesta de fase estrictamente lineal, estabilidad inherente) son imprescindibles, la mejor eleccin puede ser el diseo por mtodos ptimos, o usando ventanas (generalmente la de Kaiser). Si, en cambio, son deseables las caractersticas de los IIR (menor cantidad de coeficientes para especificaciones similares) el mtodo de la transformada bilineal es apropiado para la mayora de los casos.

VENTAJAS Y DESVENTAJAS DE FILTROS IIR Y FIR. Los filtros FIR pueden tienen una respuesta lineal en fase (no se introduce distorsin por fase en la seal), los filtros IIR tienen respuesta no lineal. Los filtros FIR que son realizados sin recursividad son siempre estables porque no tienen polos. En los IIR esto no siempre se puede garantizar. Cuando se disean filtros IIR con polos cerca del crculo unitario se debe hacer con cuidado porque no es raro que al implementar el filtro, resulte que el polo caiga fuera del crculo hacindolo inestable. Los efectos de la longitud de palabra finita son menos en los filtros FIR que en los filtros FIR. Los filtros IIR requieren menos coeficientes, menos clculos y son ms eficientes, Los FIR requieren ms procesamiento y memoria.

Los filtros analgicos pueden ser transformados en su equivalente IIR, los FIR no tienen equivalente analgico.

Los filtros FIR son ms difciles de sintetizar, en los IIR se logra ms fcil la respuesta arbitraria en frecuencia.Las caractersticas principales de los filtros FIR es que no cuentan con retroalimentacin, por lo cual cuenta con mayor localidades de memoria pero la salida del filtro es siempre estable, por lo general llegan hacer de fase lineal y es ms fcil de implementar que in filtro IIR. Este tipo de filtros tiene especial inters en aplicaciones de audio.

El procesamiento digital de seales se ha utilizado para diversas aplicaciones, como lo son el sonido, imgenes, videos y datos, siendo el enfoque del presente document el procesamiento digital de un sonido. El procesamiento digital de sonidos se puede realizar por medio de un ecualizador digital, efectos de sonido, etc., a partir de esto nos enfocaremos en el ecualizador, que comprende la modificacin de las frecuencias a partir de filtros digitales. Un filtro digital es un tipo de filtro que trabaja con seales discretas de entrada, este sistema depende de las variaciones en la seal en tiempo y en amplitud, realizando un proceso matemtico mediante el uso generalmente de la Transformada Rpida de Fourier; y obteniendo as una seal de salida resultado del procesamiento matemtico realizado por dicho sistema. En una seal de sonido al pasar por el sistema de filtros o ecualizador se modifican las frecuencias siendo este capaz de atenuar la seal o amplificarla.

Seal de Audio y sus Caractersticas. Una seal de audio es una seal analgica, conocida como un sonido audible para los seres humanos, normalmente una seal de audio tiene un rango de frecuencias entre los 20 y los 20,000 Hz aproximadamente. Para describir un sonido musical (de frecuencias entre 20 y 20,000 Hz, por lo cual, slo se pueden escuchar aprox. 10 octavas, con doce notas cada una) se utilizan los trminos de altura, timbre e intensidad.Para describir la voz (de frecuencias entre 80 y 1100 Hz), se utilizan principalmente la intensidad y el timbre. La altura est relacionada con la frecuencia de oscilacin, para que un sonido tenga una altura clara o no debe haber una periodicidad en la seal. Mientras ms alta sea la frecuencia de una seal, es ms agudo el sonido. La intensidad depende de la diferencia de las presiones mximas y mnimas de la onda, se asocia al volumen del sonido, y se puede decir que mientras haya ms amplitud de onda, hay mayor volumen.

El timbre ayuda a distinguir entre distintos tipos de voz, o instrumentos, ya que dos seales pueden tener la misma frecuencia (altura) pero diferente forma (timbre). Las ondas de los sonidos son complejas, ya que vibran con varias frecuencias al mismo tiempo; para esto, la frecuencia de vibracin menor (la ms grave) define el perodo y la altura, sta es la frecuencia base y las dems son consideradas armnicas. El sonido es la vibracin de un medio elstico, bien sea gaseoso, lquido o slido. Las ondas generadas por la fuente sonora producen ciertas variaciones de presin en el medio (por ejemplo, el aire o el agua), y esto es lo que permite que sean percibidas por el ser humano (si bien no percibe cualquier variacin; si es demasiado rpida o demasiado lenta no la escuchar). Es por ello que en el espacio csmico no hay sonidos, ya que falta el medio por el que deben discurrir, en el espacio slo hay vaco y por ello no puede haber variaciones de presin audibles.

Analgica que recibe mediante el muestreo. En el proceso contrario, al reproducir el sonido almacenado, la tarjeta lee las secuencias de ceros y unos y reproduce el sonido de cada muestra, tan rpido como cuando se tom. Cuando digitalizamos el sonido se debe elegir el formato que se utilizar para almacenarlo en la computadora. Describiendo brevemente los formatos ms utilizados tenemos: WAV: El formato estndar de Windows, stos almacenan todos los bits obtenidos de la digitalizacin, ocupan mucho espacio en disco pero conservan la calidad obtenida inicialmente. MP3: Utiliza tcnicas de compresin para lograr archivos varias veces ms pequeos que sus correspondientes WAV, la diferencia de calidad es casi imperceptible (ambos MP3 y WAV consideran solo sonido dado por la suma de sonidos individuales). MIDI: define diversos tipos de datos como nmeros que corresponden a notas particulares, ocupan menos espacio que los WAV,Una de sus desventajas es que nunca logra reproducir de manera fiel la interpretacin original, ya que la computadora la interpreta segn su capacidad.

Tarjeta de Sonido. Realiza el proceso de interpretar y convertir el sonido en datos y viceversa, para esto cuenta con dos dispositivos conversores: El convertidor analgico a digital (ADC) y el convertidor digital a anlogo (DAC), stos trabajan por separado y a la vez, para que la conversin del sonido en datos sea inmediata.

Conclusiones. Al ecualizar y definir ciertas frecuencias que sean capaces de ser escuchadas con plenitud y claridad por el humano, se debe de tener en claro que es lo que se desea resaltar y que se desea atenuar segn el espacio o medio en el que se propagaran las ondas sonoras segn el alcance de las frecuencias. La ecualizacin es en esenciaQue el odo humano puede identificar y definir lo que mejor se pueda cada instrumento, y no simplemente basarse en tablas o normas para ecualizar. Para el gnero clsico la ecualizacin debe de ser altamente detallada y la mejor alternativa encontrada es tratar de modificar lo menos posible los anchos de banda tanto en agudos como en graves y as obtener una fidelidad y calidad de sonido mayor.

Pg. 12