Diseño e Implementación de la Transformada Discreta y Bidimensional de Wavelet sobre un FPGA

Jorge Benavides Aspiazu, Jorge Lucio Tonfat Seclen, Joel Iván Muñoz Quispe Pontificia Universidad Católica del Perú – Grupo de Microelectrónica jbenavidesa@pucp.edu.pe, jtonfat@pucp.edu.pe, ji_munozq@ieee.org

Resumen.­La tr ansformada de Wavelet ha cobrado mucha impor tancia en los últimos años debido a su capacidad de análisis en el tiempo y fr ecuencia a la vez. El procesamiento de señales r equiere además de her ramientas en hardware que permitan un mejor procesamiento de la tr ansformada de Wavelet que en software. Este tr abajo presenta una aproximación a este problema con un diseño en FPGA utilizando filtros para el procesamiento. La aproximación al diseño y el r esultado final permiten una her ramienta capaz de r ealizar un procesamiento a diver sos tipos de señal.

I. INTRODUCCIÓN

El uso de la transformada de Wavelet se da cuando el análisis se desea hacer en señales que no son estacionarias, es decir que sus contenidos de frecuencia cambian en el tiempo. Si bien es cierto un análisis en frecuencia se puede dar utilizando la transformada de Fourier, puede darse el caso en que dos señales totalmente distintas en el dominio del tiempo puedan tener el mismo contenido de frecuencia, en cuyo caso un análisis empleando la transformada de Fourier no es eficaz. Debe notarse sin embargo que si se requiere un análisis en frecuencia para una señal estacionaria, es decir una señal con contenidos de frecuencia que no cambian en el tiempo, la transformada de Fourier resulta siendo la mejor herramienta para este tipo de análisis. Debido a la naturaleza no estacionaria de las señales encontradas esto hace necesaria la utilización de esta herramienta.

El requerimiento de la mayoría de señales de interés para analizar contiene las características mencionadas anteriormente y además de lo requerimientos ya discutidos. Diversas implementaciones de la transformada de Wavelet existen actualmente sin embargo la mayoría de ellas

son diseñadas sobre plataformas de software lo que hace que el procesamiento sea secuencial y no tan eficiente como una implementación en hardware. El presente trabajo pretende mostrar una aproximación que se ha hecho al problema en cuestión: una implementación de la transformada de Wavelet que permita la transformación de señales de manera eficiente, es decir utilizando la menor cantidad de recursos computacionales posibles y a la vez obtener la mejor velocidad posible. El uso de hardware para realizar esta tarea nos permite mejorar enormemente la velocidad de procesamiento y a su vez nos da independencia del uso del computador. En este trabajo hemos usado un FPGA (field programmable gate array) de la empresa Altera Stratix.

El presente trabajo trata sobre el desarrollo de una solución al problema. Este trabajo está dividido como se presenta a continuación: la primera parte consta del fundamento teórico necesario para el desarrollo de la transformada de Wavelet, en la segunda parte se explicará las alternativas al diseño y la alternativa y metodología a utilizar para el desarrollo del proyecto, luego se dará una explicación de la arquitectura utilizada y finalmente se darán las conclusiones y observaciones halladas hasta el momento.

II. LATRANSFORMADADISCRETA DEWAVELET

La implementación de la transformada discreta de wavelet (DWT) se realiza con el uso de filtros para analizar las frecuencias altas y bajas. La resolución de la señal, que es la medida de la cantidad de información presente en la señal, está dada por los filtros; mientras que la escala esta dada por la decimación. Estos dos casos se detallarán a continuación.

En el caso de los filtros se cuenta con dos tipos: un filtro pasa altos y un filtro pasa bajos, que permitirán analizar la parte de frecuencias altas y bajas de la señal respectivamente. Estos filtros además son filtros de media banda, es decir su frecuencia de corte es la mitad de la frecuencia máxima de la señal.

En cuanto a la decimación, esto se refiere a quitar cada 2 muestras, esto disminuye la frecuencia. Para aumentarla se realizaría la operación contraria (upsampling).

Con estas dos operaciones podemos definir la DWT como:

[ ] [ ] [ ]

[ ] [ ] [ ] n k h n x k ylow

n k g n x k yhigh

n

n

− =

− =

∑

∑ 2 *

2 *

Figura 1. Donde yhigh[n] y ylow[n] son las salidas de los filtros pasa altos y pasa bajos r espectivamente, además de g[n] y h[n] los filtros pasa altos y pasa bajos r espectivamente.

Finalmente con esta base teórica se puede desarrollar un algoritmo para la implementación de la transformada de Wavelet.

III. IMPLEMENTACIÓN DE LA TRANSFORMADA DISCRETA DE WAVELET

La implementación de la transformada de Wavelet genera muchas posibilidades, como ya ha sido mencionado la mayor cantidad de implementaciones están hechas sobre una plataforma de software, sin embargo existen implementaciones en hardware también, muchas desarrolladas en grupos de investigación o como tesis. El desarrollo de la herramienta (ya sea en software o hardware) se basa sobre dos posibles aproximaciones: la utilización de un banco de filtros o el desarrollo de la transformada de Wavelet vía Lifting.

La principal diferencia entre estos dos métodos es la utilización de un banco de filtros para el desarrollo de la transformada de Wavelet, mientras en el primer caso si se utilizan estos bancos, la transformada por Lifting no los usa, dependiendo en multiplicaciones y sumas que se realimentan. La selección de este tipo de aproximación se basa en primer en la facilidad de desarrollar la transformada desde el punto de vista matemático, debido a esto hemos seleccionado una implementación con banco de filtros para el diseño.

Por otro lado el desarrollo de este trabajo es un primer paso para un estudio sobre la implementación óptima de la transformada de Wavelet. Finalmente el último factor decisivo para la selección de esta implementación con banco de filtros es el desarrollo de una arquitectura que consume una pequeña cantidad de recursos debido al diseño del filtro en sí.

Con todos estos datos se puede explicar la metodología seleccionada que permite que el proyecto se desarrolle de manera sencilla a pesar de la complejidad del mismo: la implementación y análisis de la transformada en sí se desarrollo primero en el programa Matlab para comprender de mejor manera el algoritmo, con lo que se pudieron observar los resultados que se desean para luego desarrollar el código en VHDL que nos dará el resultado en hardware deseado. Para explicar mejor nuestro trabajo utilizaremos una explicación del algoritmo sin tomar en cuenta la arquitectura, por lo que primero presentaremos la implementación de la transformada de Wavelet en una dimensión, y a partir de esto mostrar como se realiza la transformada de Wavelet para dos dimensiones, aproximaremos todo este análisis a manera de bloques como se explicará a continuación.

A. Transformada Discreta de Wavelet de una Dimensión

La implementación de la Transformada Discreta de Wavelet (DWT) será tratada a modo de bloques básicos con los que se podrá construir descomposiciones a mayores niveles (es decir obtener más detalles, ver figura 2), para poder lograr esto se utilizará el bloque básico mencionado (TA), que consiste en la utilización de filtros circulantes en representación Polifase, esta no es la única forma de realizar la implementación de la DWT sin embargo es una implementación que presenta una buena velocidad de computo. La descomposición en Wavelet también es referida como análisis, este bloque básico está compuesto como se muestra en la figura 3.

Figura 2. Descomposición de wavelet a varios niveles usando varios bloques básicos en su construcción.

1 + j a +

+

j a

j d

( ) 1 2 ↓

0 ~ H

1 ~ H

1 ~ G

0 ~ G

Γ

( ) 0 2 ↓

Γ

) 0 ( 1 + j a

) 1 ( 1 + j a

Figura 3. Bloque básico de análisis para un nivel de descomposición de wavelet.

Como se puede observar en la figura 3, el bloque de análisis comprende varios operadores que describiremos a continuación.

La primera etapa que se debe emplear es un bloque de decimación, la ventaja de decimar primero es que se descartan muestras antes y la operación de convolución que se realiza luego la hace sobre un número menor de muestras lo que, por obvias razones, mejora todo el tiempo de procesamiento que se debe utilizar. Antes de realizar la decimación, sin embargo, se debe separar las muestras en pares e impares con el objetivo de realizar de manera más rápida la transformación.

Una vez realizada la decimación, se debe aplicar una convolución con los coeficientes de los filtros para poder filtrar así la señal, los filtros a utilizar son un filtro pasa­altos y un filtro pasa­bajos. El diseño que hemos hecho permite trabajar con cualquier tipo de coeficientes de filtros, el tipo de convolución que hemos utilizado para nuestro diseño es una convolución circular, el diseño del bloque básico no ha utilizado el mismo tipo de diseño modular que utilizamos para el resto de implementaciones.

Por último debido a los desplazamientos ocurridos por la convolución, se introduce un desplazamiento hacia la derecha de una posición para compensar eso, finalmente procedemos a sumar las señales que son resultado del filtro pasa­altos (g de pares se suma con g de impares) y del filtro pasa­bajos (h de pares se suma con h de impares). Al final tenemos el resultado de una aproximación y un detalle de la señal.

B. Transformada discreta de Wavelet de 2 dimensiones

La transformada discreta de Wavelet bidimensional, tiene un esquema un poco más

complicado que la transformada para una dimensión, sin embargo la esencia de esta implementación sigue siendo la misma que para la transformada en una dimensión, de hecho nuestra implementación se basa en los bloques básicos vistos en una dimensión, de esta forma aprovechamos el diseño ya desarrollado y aplicamos un diseño modular a la vez.

El esquema básico a utilizar para la transformada bidimensional es el que se muestra en la figura 4, los bloques utilizados en este diseño son los vistos anteriormente por lo que el desarrollo sobre este diseño se verá básicamente lo referente a los resultados.

TA

TA

TA

señal a

d

a j3

d j3

dj2

d j1

Figura 4. Implementación del bloque básico de la transformada bidimensional a partir de los bloques básicos de una dimensión.

En la figura 4 podemos ver como el bloque básico de dos dimensiones se construye a partir del bloque básico de una dimensión, podemos observar que la salida del primer bloque de una dimensión nos da una primera aproximación y detalle y que estos son a su vez entradas de las otros dos bloques. Las cuatro salidas finales representan a la aproximación y a los detalles de la señal, dentro de los detalles uno representa todos los detalles horizontales, otro los detalles verticales y finalmente los detalles horizontales. La descomposición que se realice a más niveles será sobre esta nueva aproximación y el resultado generará cuatro señales similares a esta.

IV. ARQUITECTURA DESARROLLADA

El desarrollo de la arquitectura se ha hecho de manera que se puedan optimizar los recursos, esto se debe en parte al tipo de convolución que se planea utilizar. La convolución circular también requiere de un control más fino de las señales, por lo que es necesaria una señal de control, la figura 5. presenta el esquema de la arquitectura a utilizar.

D Q

ena

D Q

ena Clk_data

Shift_register

Decimador

Filtro I_H

Filtro I_L

Filtro P_H

Filtro P_L

Σ

+

+

Σ

+

dj

Σ

+

+

Σ

+

aj

Data

UNIDAD DE CONTROL

UNIDAD DE PROCESOS

Figura 5. Diagrama del sistema de la transformada de Wavelet

Se debe resaltar que esta implementación es la de un bloque básico de análisis y que posibles diseños para transformadas de mayor nivel, solo requieren la interconexión de varios bloques de análisis. Este circuito consta de dos partes importantes, que se detallarán a continuación: el decimador y los filtros.

Decimador: En la figura anterior se observa una etapa de decimación, esta involucra un registro del tamaño de cada de dato a ingresar y procesar. Además se incluye un flip­flop el cual actuará de contador, el cual generará una señal tal que en un primer instante obtenga el primer valor y en un siguiente instante tanto el valor actual como el anterior entran al filtro respectivo a modo de sincronizar también el procesamiento de ambos filtros.

Filtros: Como se menciono anteriormente el proceso de convolución a realizarse es la convolución circular el cual consiste en una rotación de datos para obtener una señal resultante del mismo número de valores que el número de datos ingresados a cada filtro.

Como se observa en la figura 6 se puede observar un bloque que representa un bloque de registros de desplazamiento (Shift Register) el cual almacenará un determinado grupo de valores el cual luego de haber sido ingresada la señal completa estos volverán a ingresar para completar el proceso de convolución Circular. Por otro lado, como se bien se mencionó se buscó optimizar los recursos, por ello como se observa en la figura 6 un grupo de registros que están unidos a 4 multiplexores, el fin de esto fue ocupar menor espacio ya que el numero de Taps requeridos para el diseño los hacía muy saturado y demandaba mayor cantidad de recursos, además se incluyen registros de sincronización para un mejor control del mismo, que

se encuentran tanto a la salida de cada multiplexor, a la salida de cada multiplicador y a la salida del sumador el cual se observa en la figura 6.

Figura 6. Esquema del filtro

V. RESULTADOS DE LA IMPLEMENTACIÓN DE LA DWT EN DOS DIMENSIONES

A continuación se presentarán los resultados de esta implementación, la señal que se utilizó es una imagen que es mostrada en la figura 7, la razón de usar esta señal fue porque la imagen contiene líneas claramente visibles tanto horizontales, verticales como diagonales. El primer resultado a mostrar es justamente la descomposición a un nivel en donde se muestra efectivamente que la separación en los detalles es de la forma explicada.

Figura 7. Señal original, Bárbara.

Figura 8. Salida de la descomposición a un nivel de la transformada bidimensional

Como se aprecia en la figura 8 los detalles solo resaltan aquellos elementos de la imagen que corresponde a las líneas horizontales, verticales y diagonales. Como se mencionó en el caso de una dimensión una vez en el dominio Wavelet es más fácil realizar un análisis de la señal para encontrar detalles que interesen y eliminar lo que no para poder por ejemplo realizar una compresión de la imagen en este caso (como ejemplo se podría usar el estándar JPEG 2000).

Para el caso de más niveles de descomposición ocurre lo que ya se había mencionado, es decir que de la aproximación existente en el nivel anterior aparecen cuatro nuevas salidas, para ilustrar mejor este caso la figura 9 muestra justamente esto.

Figura 9. Resultado de la descomposición a dos niveles.

Como nota aparte cabe señalar que nuestro diseño sigue en progreso y que se espera realizar las pruebas dentro de las próximas semanas para tener resultados más concluyentes, sin embargo todos los resultados obtenidos hasta el momento son muy alentadores y nos muestran que el algoritmo desarrollado es ideal para el tipo de aplicaciones.

VI. CONCLUSIONES

Dentro de todo el análisis desarrollado hemos visto que la implementación en hardware presenta la principal ventaja de un procesamiento más rápido y el aprovechamiento máximo de los recursos computacionales, las desventajas obvias son el costo y el incremento de complejidad en la implementación, sin embargo estos pueden ser pasados por alto si se requiere de una herramienta DSP potente para análisis exhaustivos de las señales.

VII. BIBLIOGRAFÍA

[1] Mallat, Stéphane G., A wavelet tour of signal processing, San Diego : Academic Press, 1999.

[2] Uwe Meyer­Baese, Digital Signal Processing with Field Programmable Gate Arrays, Springer­Verlag, 2001.

[3] Jensen, A., Ripples in Mathematics: The Discrete Wavelet Transform, Springer­Verlag Berlín Heidelberg 2001.

[4] http://www.ieev.uma.es/edutec97/edu97_c3/2­3­10.htm

[5] http://engineering.rowan.edu/~polikar/WAVELETS/ WTtutorial.html ; the Wavelet Tutorial by Robi Polikar.

VII. BIOGRAFÍA

Jorge Benavides Aspiazu: Naciò el 4 de octubre de 1984 en Lima, Perú. Actualmente estudiante del 8vo nivel de ingeniería electrónica en la Pontificia Universidad Católica del Perú. En el 2005 ingresó al grupo de microelectrónica en el área de diseño digital y realizó una

publicación en el XI Workshop Iberchip 2005 en Salvador de Bahía, Brasil, ganando en la categoría de mejor poster con el trabajo "Diseño de un intercalador programable de 8 bits para la decodificación analógica

de turbocódigos". Posteriormente realizó una publicación en el XII congreso internacional INTERCON 2005 con el trabajo “Diseño e Implementación de Sistemas Digitales usando CPLDS”. Actualmente se encarga del desarrollo de la transformada de Wavelet en FPGA.

Joel Iván Muñoz Quispe, nació en Lima, Perú, el 13 de Junio de 1985. Estudiante de 8° ciclo de la Carrera de Ing. Electrónica en la Pontificia Universidad Católica del Perú (PUCP). Ingreso al Grupo de de Microelectrónica (GUE) de la PUCP en el 2005. Y desde entonces se ha dedicado al

Diseño de Arquitectura de Computadoras en VHDL. Los trabajos realizados se han concentrado en la realización de Transformada de Wavelet Discreta para un FPGA.

Jorge Lucio Tonfat Seclen nació en Lima, Perú, el 9 de Julio de 1985. Estudiante de pregrado de la Carrera de Ingeniería Electrónica en la Pontificia Universidad Católica del Perú (PUCP). Miembro del grupo de Microelectrónica de la PUCP. Su área de investigación se centra en el diseño de sistemas digitales basados en FPGA’s. Obtuvo el

diploma al mejor póster en el congreso IBERCHIP 2005 en Salvador de Bahia, Brasil y realizó una ponencia en el XII congreso internacional INTERCON 2005 en Lima, Perú. Actualmente se encarga del desarrollo de la transformada de Wavelet en FPGA.