Ventanas deslizantes por bloques para la implementación online de la transformada wavelet discreta Antonio Cedeño Pozo1 y Rafael Trujillo Codorniú2 1 Universidad

2 Instituto

de las Ciencias Informáticas, Centro de Informática Industrial, Cuba

Superior Minero Metalúrgico de Moa, Departamento de Matemática, Cuba [email protected], [email protected]

Resumen. En este trabajo se propone un esquema para la implementación online de la Transformada Wavelet Discreta. Se introducen mejoras en cuanto a tiempo de ejecución respecto al método de ventanas deslizantes tradicional. En la propuesta se realiza una modificación a la definición de la ventana de datos propuesta en el esquema original. Las pruebas realizadas muestran que el algoritmo propuesto es más rápido que el de ventanas deslizantes tradicionales. Palabras clave. Wavelet, online, ventanas deslizantes, programación dinámica.

Sliding Windows by Blocks for Online Wavelet Discrete Transform Implementation Abstract. In this paper we propose an online Wavelet Discrete Transform implementation scheme. Our proposal improves the execution time compared to the traditional sliding window method. Also, we modify the definition of the data window concept given in the original scheme. The experiments we performed show that the runtime cost of the proposed algorithm is better than that of the traditional sliding window method. Keywords. Wavelet, online, sliding window, dynamic programming.

1. Introducción La Transformada Wavelet Discreta (WDT) es una herramienta matemática relativamente reciente, entre sus múltiples utilidades sobresale en áreas como la reducción de ruido, la compresión de datos y el reconocimiento de

patrones. El concepto clave de la WDT es la adaptación del análisis en tiempo y frecuencia de forma simultánea, ésta característica la hace más factible para el tratamiento de señales no estacionarias que otras transformadas, como la Transformada de Fourier [1]. De forma natural esta transformada se utiliza para el tratamiento de señales una vez que han sido almacenadas, en ese sentido se han publicado un número importante de trabajos que ponen de manifiesto la eficacia de la WDT en este tipo de tratamiento [2, 3, 4], que en este material denominaremos offline. Estos buenos resultados para el tratamiento offline de señales han motivado a que algunos investigadores utilicen la WDT para el tratamiento online. Entiéndase por online el tratamiento sobre la señal a medida que se van adquiriendo las muestras. La utilización de la WDT presupone el aprovechamiento de un conjunto de propiedades que caracterizan a las señales en el espacio de la transformada, que en este caso muchos autores llaman coeficientes wavelets, por tanto los esquemas de aplicación constan de tres pasos fundamentales: 1. Descomposición de la señal en coeficientes wavelets mediante la WDT. 2. Tratamiento de los coeficientes según el área específica de aplicación. 3. Reconstrucción de la señal mediante la WDT inversa. En el caso online las muestras se deben tratar por separado a medida que van siendo adquiridas, para evitar retardos en la salida los pasos mencionados anteriormente se deben

Computación y Sistemas, Vol. 18, No. 4, 2014, pp. 767–772 ISSN 1405-5546 doi: 10.13053/CyS-18-4-1426

768 Antonio Cedeño Pozo y Rafael Trujillo Codorniú

realizar sobre un histórico de datos que incluye a la muestra más reciente o muestra actual. En [5] se propone un esquema de este tipo, el mismo está basado en un mecanismo de ventanas deslizantes, esta propuesta ha sido aplicada con buenos resultados en [5, 6, 7] para la reducción de ruido en diferentes tipos de señales. El principal inconveniente que tiene este enfoque es el tiempo de ejecución de los algoritmos, pues para cada muestra se deben recalcular los coeficientes wavelets, elevando los tiempos de respuesta y comprometiendo la utilización de esta técnica en algunas áreas de aplicación con restricciones de tiempo importantes. En ese sentido en este material se realizan modificaciones al esquema de ventanas deslizantes (MW), y se propone un esquema que mejora el costo computacional, la nueva propuesta se denomina ventana deslizante por bloques (MWB).

2. Desarrollo 2.1. Implementación de la WDT: esquema lifting Una de las principales dificultades que enfrentan los ingenieros a la hora de trabajar con transformadas es la complejidad que esto implica, algunas implementaciones de la WDT presuponen un amplio conocimiento matemático, por ejemplo en [8,9] se emplea la teoría de Fourier como instrumento para las construcciones wavelet. El esquema lifting permite implementar la WDT de una forma sencilla y eficiente, es un esquema natural, con todas las ventajas de los métodos tradicionales y con menor costo computacional. En el caso más simple consta de tres fases: división, predicción y actualización. El esquema parte de un conjunto de datos muestreados dado por X0 = {x0 , x1 , ..., xN −1 }, en la primera fase este conjunto se divide en dos subconjuntos C-1(coeficientes wavelets) y A1(aproximaciones), formados por los elementos de subíndice impar y par de X0 respectivamente. En la fase de predicción se trata de predecir los elementos de C-1 a partir de A-1 usando algún tipo de correlación presente en los datos originales.

Computación y Sistemas, Vol. 18, No. 4, 2014, pp. 767–772 ISSN 1405-5546 doi: 10.13053/CyS-18-4-1426

Fig. 1. Esquema lifting

Si se pudiera encontrar un operador de predicción P, que garantice que C-1 = P(A-1), entonces se pudiera reemplazar el conjunto X0 por A-1 pues se podría predecir la parte faltante para reconstruir X0. En la práctica es imposible encontrar una predicción exacta que sea independiente de los datos iniciales, pero si P(A-1) es bastante cercano a C-1, entonces se podría reemplazar cada elemento de C-1 por la diferencia entre su valor y la predicción, es decir C-1 = C-1 - P(A-1). Es de suponer que si la predicción es razonable entonces esta diferencia contiene mucha menos información que el conjunto original. En la fase de actualización se tratan de conservar en A-1 algunas propiedades globales de los datos del conjunto original mediante un operador U de la siguiente forma: A-1 = A-1 + U (C-1) (ver Figura 1). El esquema puede ser iterado, se divide A-1 en dos subconjuntos A-2 y C-2 , y se aplican nuevamente los operadores P y U. Luego de n pasos el conjunto original puede ser reemplazado por su representación wavelet: {𝐴−𝑛 ,C−𝑛 ,C−n+1 … ,C−1 }

(1)

Si el modelo de predicción es exitoso entonces la energía del vector obtenido se concentra en A-n y los coeficientes deben ser pequeños. La transformada inversa se obtiene invirtiendo las operaciones del esquema. 2.2. Ventanas deslizantes Se ha demostrado estadísticamente en muchas investigaciones que las técnicas de

Ventanas deslizantes por bloques para la implementación online de la Transformada Wavelet Discreta 769

La cantidad de elementos de la prolongación p aumenta el tamaño de la ventana a l + p, y ésta

Fig. 2. Ventana de datos en MW

procesamiento de señales offline basadas en WDT pueden ser muy eficientes, sin embargo, dichas técnicas no pueden ser aplicadas tal cual para realizar procesamiento online, necesario para aplicaciones con requerimientos de algún tipo de tiempo real. Debido a esa razón se han propuesto algunos esquemas para adaptar las técnicas offline para el realizar procesamiento online, aprovechando el rendimiento de las primeras. Para lograr ese objetivo uno de los puntos críticos es la utilización de la WDT de forma efectiva para minimizar los retardos en las salidas. Una de las técnicas utilizadas es MV [5, 6, 7], que propone la utilización de una ventana de datos sobre la que se realiza de manera online la WDT y se actualiza (desplazando o deslizando) ante el arribo de una nueva muestra (ver Figura 2). La ventana alrededor de la muestra actual x(i) se puede definir como: {Vacío}, i pmin], permitiendo reutilizar una parte importante de los coeficientes en cada bloque. El esquema MWB está originalmente diseñado para el funcionamiento con la wavelet Haar (ver Figura 5), que por definición es la más sencilla y de menor complejidad computacional en su implementación lifting, cuyos operadores P y U se definen a partir de un término adyacente. Para el correcto funcionamiento de MWB los parámetros deben seleccionarse teniendo en cuenta las consideraciones que se listan a continuación: -

2.3 Ventanas deslizantes por bloques La idea de la propuesta de este material, esquema que denominamos MWB, se basa en principios de la programación dinámica, siguiendo el patrón de MW se tratan de reutilizar los coeficientes wavelets tanto como sea posible, evitar que todo el tiempo se tenga que recalcular la WDT ante la llegada de cada una de las muestras de la señal. En MW se utiliza una prolongación de tamaño fijo, en el esquema que se propone la prolongación p varía desde pmax hasta pmin, que son variables que representan la máxima y mínima longitud respectivamente, que puede tomar la prolongación. De esa forma la nueva ventana W queda definida por: {Vacío}, 𝑝 ⏞

-

i