Algoritmo de Cascada
El algoritmo de cascada es utilizado para reconstruir las funciones wavelet (y
sus funciones de escalamiento correspondientes) a partir de sus coeficientes. Es
un proceso iterativo que aumenta a cada paso la cantidad de información,
haciendo una aproximación cada vez más exacta de los datos de la función
correspondiente; el aumento de datos corresponde a un aumento de la 'resolución'
en la escala. Esto es posible gracias a la autosimilitud a través de la escala
que poseen las funciones wavelet.
. Tenemos una cantidad N de pares de coeficientes
. Tenemos una semilla:
S0 = {0, ... ,0,1,0, ... ,0} para la función de escalamiento
S1 = {0, ... ,0, [(-1)^i]*N ,0, ... ,0} para la función wavelet
Comenzamos con dim(S) = 1, haciendo una convolución normal
S1 = conv(S0,C) dim(S0) = 1 dim(S1) = (2N-1)*2
Si la semilla utilizada es {1}, aún no ha habido iteración. Si la semilla
utilizada es la correspondiente para la función wavelet, se considera haber
hecho una iteración.
La convolución se aplica como sigue (ejemplo con N=2) [contadores comenzando en
cero]
Como N=2, dim(C) = 4, C = {c0,c1,c2,c3}
[Sa Sb Sc Sd] :-- Datos para la convolución (S1)
c0 c1 c2 [c3 0 0 0] Matriz para la convolución
c0 c1 [c2 c3 0 0] creada con los coeficientes
c0 [c1 c2 c3 0] y centrada en los datos
[c0 c1 c2 c3]
[ 0 c0 c1 c2] c3
[ 0 0 c0 c1] c2 c3
[ 0 0 0 c0] c1 c2 c3
'-------' '--------'
|_____________________|______ Datos descartados
Una forma sencilla de 'descartar' los extremos es añadir ceros en los extremos,
específicamente añadimos 2N-1 en cada extremo:
{0 0 0} [Sa Sb Sc Sd] {0 0 0}
Los datos en S1 corresponden a la escala más 'gruesa', menos fina. El aumentar
la resolución de la escala implica encontrar valores intermedios en esta escala;
al momento estos valores no se conocen:
[Sa ? Sb ? Sc ? Sd] ---> [Sa 0 Sb 0 Sc 0 Sd]
Intercalamos ceros entre los valores ya existentes (además de los añadidos a los
extremos); al iterar, esos valores se convierten en aproximaciones de los
valores reales. Con este cambio, la matriz de convolución crece, para abarcar el
nuevo rango de datos:
{0 0 0}[Sa 0 Sb 0 Sc 0 Sd]{ 0 0 0} {ceros} S1 {ceros}
c0 c1 c2 [c3 0 0 0 0 0 0] ...
c0 c1 [c2 c3 0 0 0 0 0] ...
c0 [c1 c2 c3 0 0 0 0] = 0*c0 + Sa*c1 + 0*c2 + Sb*c3
[c0 c1 c2 c3 0 0 0] = Sa*c0 + 0*c1 + Sb*c2 + 0*c3
[ 0 c0 c1 c2 c3 0 0] ...
[ 0 0 c0 c1 c2 c3 0] ...
[ 0 0 0 c0 c1 c2 c3]
[ 0 0 0 0 c0 c1 c2] c3
[ 0 0 0 0 0 c0 c1] c2 c3
[ 0 0 0 0 0 0 c0] c1 c2 c3
'-------' '--------'
|______Datos descartados______|
Al lado de la matriz se ven ejemplos del cálculo de la convolución, que se hace
por cada fila de la matriz. Al poner atención a los cálculos, vemos que en ambos
casos hay coeficientes que son multiplicados por cero:
0*c0 + Sa*c1 + 0*c2 + Sb*c3 = Sa*c1 + Sb*c3 [coeficientes nones]
Sa*c0 + 0*c1 + Sb*c2 + 0*c3 = Sa*c0 + Sb*c2 [coeficientes pares]
Eliminar las multiplicaciones por cero disminuye la cantidad de multiplicaciones
a casi la mitad, lo que representa una ventaja. El cambio será dividir los
coeficientes en pares y nones, y hacer la matriz con este nuevo esquema:
{0}[Sa Sb Sc Sd]{ 0} {ceros} S1 {ceros}
c1 [c3 0 0 0] ... [coeficientes nones]
c0 [c2 c3 0 0] ... [coeficientes pares]
[c1 c3 0 0] = Sa*c1 + Sb*c3
[c0 c2 0 0] = Sa*c0 + Sb*c2
[ 0 c1 c3 0] = Sb*c1 + Sc*c3
[ 0 c0 c2 0] = Sb*c0 + Sc*c2
[ 0 0 c1 c3] ... [coeficientes nones]
[ 0 0 c0 c3] ... [coeficientes pares]
[ 0 0 0 c1] c3
[ 0 0 0 c0] c2
'-' '--'
|________________|________ Datos descartados
Con este arreglo:
. Los ceros al inicio y final son igual a N-1
. Por cada fila, alternamos los coeficientes usados [nones / pares]
Los ceros de los extremos son mantenidos para poder crear un algoritmo
generalizado. Un punto importante de notar es lo siguiente (valores específicos
del ejemplo):
*S2 es el resultado de la convolución
dim(S0) = 1 dim({ceros S0 ceros}) = 3 = 3*(2^0)
dim(S1) = 4 dim({ceros S1 ceros}) = 6 = 3*(2^1)
dim(S2) = 10 dim({ceros S2 ceros}) = 12 = 3*(2^2)
A partir de estos números notamos que es sencillo calcular la cantidad de datos
de cada nivel de iteración tomando en cuenta los ceros de los extremos; el ritmo
de crecimiento de datos es:
Ndatos = (2N-1)(2^iteración)
Programación (en lenguaje C).
Al llevar a cabo las iteraciones, necesitamos un lugar dónde almacenar el
resultado de la convolución, y los valores que la originaron. La solución
práctica y rápida es asignar dos bloques de memoria, uno para el resultado
actual y otro para el resultado anterior (generador del resultado actual).
double *actual, *anterior; /* Punteros a tipo doble */
...
actual = calloc((2N-1)(2^iteracion),sizeof(double));
anterior = calloc(2N-1)(2^iteracion),sizeof(double));
/* Bloques de memoria
* . actual . anterior
* | |
* [______________]...[_____________]
*/
Para el primer paso:
/* *anterior contiene la semilla */
actual = convolucion (anterior,coeficientes);
pero en el siguiente paso:
/* *actual contiene los datos útiles */
anterior = convolucion (actual,coeficientes);
Debemos intercambiar la 'posición' entre *actual y *anterior para usar una
versión generalizada del paso. Ya que dentro del lenguaje C los punteros indican
el comienzo de un bloque de memoria, podemos intercambiar estos valores, como
sigue:
double *temporal; /* Para hacer una copia momentánea */
...
actual = convolución (anterior,coeficientes);
temporal = actual;
actual = anterior;
anterior = actual;
Porque:
temporal = actual;
/* . temporal
* . actual . anterior
* | |
* [______________]...[_____________]
*/
actual = anterior;
/* . actual
* . temporal . anterior
* | |
* [______________]...[_____________]
*/
anterior = temporal;
/* . anterior
* . temporal . actual
* | |
* [______________]...[_____________]
*/
Después de eso, la referencia de los bloques de memoria ha quedado invertida. Ya
que la inversión sucede después de haber obtenido el resultado deseado, al final
de las iteraciones el resultado del último paso estará en *anterior, por lo que
podremos liberar 'actual'.
double *anterior, *actual, *temporal;
...
actual = calloc((2N-1)(2^iteracion),sizeof(double));
anterior = calloc(2N-1)(2^iteracion),sizeof(double));
...
for (i=0;i ( geocities.com/mx)