The Cascade Algorithm - Recursion, Wavelets

I'm trying to implement something called the "Cascade Algorithm" which is
based upon the Dilation Equation, used when needed to approximate a
Wavelet Scaling function or mother function.

Everything is well apart from a small snag, I've been studying for a while
now and still have no idea how to implement it?!!

it goes something like this;

f(t) = c(0)f(2t) + c(1)f(2t - 1) + c(2)f(2t - 2) + c(3)f(2t - 3)

where 
c(0) = 0.6830127
c(1) = 1.1830127
c(2) = 0.3169873
c(3) = -0.1830127 (daubechie co-efficents, 4-tap)

I've tried many times on google for something that can explain this to me,
without glossing over the initial stages of "how to prime" the algorithm,
but with little luck.  I think the recursion is confusing me a tad, it
seems to say that to produce a low scale rendering of a wavelet, you need
to know what the high scale version looks like first, which is odd
considering what I've already researched seems to suggest that the low
scale rendering is the start point for the high scale rendering!?!?!


Could somebody explain it to me please, in a "cascade algorithm for
dummies" type way? I'd be very greatful (once again!)

moosedude wrote:

> 
> I'm trying to implement something called the "Cascade Algorithm" which is
> based upon the Dilation Equation, used when needed to approximate a
> Wavelet Scaling function or mother function.
> 
> Everything is well apart from a small snag, I've been studying for a while
> now and still have no idea how to implement it?!!
> 
> it goes something like this;
> 
> f(t) = c(0)f(2t) + c(1)f(2t - 1) + c(2)f(2t - 2) + c(3)f(2t - 3)
> 
> where
> c(0) = 0.6830127
> c(1) = 1.1830127
> c(2) = 0.3169873
> c(3) = -0.1830127 (daubechie co-efficents, 4-tap)
> 

This functions is the dilation equation. IIRC, cascade algorithm employs
similar filter structure as the fast wavelet transform. However, one runs
the algorithm sort of backwards. Feed a unit impulse as the lowpass band
(i.e., the approximation part) and zeros for other bands and run the
reconstruction to N levels. When the N approaches infinity the discrete
approximation should approach the actual scaling function.

> I've tried many times on google for something that can explain this to me,
> without glossing over the initial stages of "how to prime" the algorithm,
> but with little luck.  I think the recursion is confusing me a tad, it
> seems to say that to produce a low scale rendering of a wavelet, you need
> to know what the high scale version looks like first, which is odd
> considering what I've already researched seems to suggest that the low
> scale rendering is the start point for the high scale rendering!?!?!
> 
> 
> Could somebody explain it to me please, in a "cascade algorithm for
> dummies" type way? I'd be very greatful (once again!)

You are familiar with the filter bank implementation? If not the above
explanation might not make any sense. 

-- 
Jani Huhtanen
Tampere University of Technology, Pori

>moosedude wrote:
>
>> 
>> I'm trying to implement something called the "Cascade Algorithm" which
is
>> based upon the Dilation Equation, used when needed to approximate a
>> Wavelet Scaling function or mother function.
>> 
>> Everything is well apart from a small snag, I've been studying for a
while
>> now and still have no idea how to implement it?!!
>> 
>> it goes something like this;
>> 
>> f(t) = c(0)f(2t) + c(1)f(2t - 1) + c(2)f(2t - 2) + c(3)f(2t - 3)
>> 
>> where
>> c(0) = 0.6830127
>> c(1) = 1.1830127
>> c(2) = 0.3169873
>> c(3) = -0.1830127 (daubechie co-efficents, 4-tap)
>> 
>
>This functions is the dilation equation. IIRC, cascade algorithm employs
>similar filter structure as the fast wavelet transform. However, one
runs
>the algorithm sort of backwards. Feed a unit impulse as the lowpass band
>(i.e., the approximation part) and zeros for other bands and run the
>reconstruction to N levels. When the N approaches infinity the discrete
>approximation should approach the actual scaling function.
>
>> I've tried many times on google for something that can explain this to
me,
>> without glossing over the initial stages of "how to prime" the
algorithm,
>> but with little luck.  I think the recursion is confusing me a tad, it
>> seems to say that to produce a low scale rendering of a wavelet, you
need
>> to know what the high scale version looks like first, which is odd
>> considering what I've already researched seems to suggest that the low
>> scale rendering is the start point for the high scale rendering!?!?!
>> 
>> 
>> Could somebody explain it to me please, in a "cascade algorithm for
>> dummies" type way? I'd be very greatful (once again!)
>
>You are familiar with the filter bank implementation? If not the above
>explanation might not make any sense. 
>
>-- 
>Jani Huhtanen
>Tampere University of Technology, Pori
>


Thanks Jani for your reply, I am familiar with filter banks, but my
interpretation of a filter bank is that the decomposition for a filter
bank occurs with low & high pass filters, the further down the chain you
go, the more refined the information on the original input, for each chain
downsampling of 2 takes place until you can divide no further. Presumably a
simular division takes place for each cascade of the algorithm? for a finer
resolution you double your number of data points from the previous scale. 
But I don't understand how the (2t - n) bit could obtain the right values
for refinement from the previous coarse scale?

Unless the algorithm assumes you start with a fine resolution scale and
starts the processes to get to the coarse resolution?!?!?!?

I've done a bit more reading and have come across this java applet;

http://cm.bell-labs.com/who/wim/cascade/

which implies that the starting input is a triangle structure, i.e.

t0 = 0.0, t1 = 0.0, t2 = 1.0, t3 = 0.0

I've been tinkering with some C++ code with this as input but aren't
getting the output I would expect at certain iterations.

Is there any worked examples for a daub4 cascade at iteration 1, on the
internet somewhere I can have a look at that would help me clarify a few
points?

moosedude wrote:

>>moosedude wrote:
>>
>>> 
>>> I'm trying to implement something called the "Cascade Algorithm" which
> is
>>> based upon the Dilation Equation, used when needed to approximate a
>>> Wavelet Scaling function or mother function.
>>> 
>>> Everything is well apart from a small snag, I've been studying for a
> while
>>> now and still have no idea how to implement it?!!
>>> 
>>> it goes something like this;
>>> 
>>> f(t) = c(0)f(2t) + c(1)f(2t - 1) + c(2)f(2t - 2) + c(3)f(2t - 3)
>>> 
>>> where
>>> c(0) = 0.6830127
>>> c(1) = 1.1830127
>>> c(2) = 0.3169873
>>> c(3) = -0.1830127 (daubechie co-efficents, 4-tap)
>>> 
>>
>>This functions is the dilation equation. IIRC, cascade algorithm employs
>>similar filter structure as the fast wavelet transform. However, one
> runs
>>the algorithm sort of backwards. Feed a unit impulse as the lowpass band
>>(i.e., the approximation part) and zeros for other bands and run the
>>reconstruction to N levels. When the N approaches infinity the discrete
>>approximation should approach the actual scaling function.
>>
>>> I've tried many times on google for something that can explain this to
> me,
>>> without glossing over the initial stages of "how to prime" the
> algorithm,
>>> but with little luck.  I think the recursion is confusing me a tad, it
>>> seems to say that to produce a low scale rendering of a wavelet, you
> need
>>> to know what the high scale version looks like first, which is odd
>>> considering what I've already researched seems to suggest that the low
>>> scale rendering is the start point for the high scale rendering!?!?!
>>> 
>>> 
>>> Could somebody explain it to me please, in a "cascade algorithm for
>>> dummies" type way? I'd be very greatful (once again!)
>>
>>You are familiar with the filter bank implementation? If not the above
>>explanation might not make any sense.
>>
>>--
>>Jani Huhtanen
>>Tampere University of Technology, Pori
>>
> 
> 
> Thanks Jani for your reply, I am familiar with filter banks, but my
> interpretation of a filter bank is that the decomposition for a filter
> bank occurs with low & high pass filters, the further down the chain you
> go, the more refined the information on the original input, for each chain
> downsampling of 2 takes place until you can divide no further.

In cascade algorithm you run the reconstruction band (not the decomposition
band) and for scaling function you only run the lowpass branch of the
dyadic tree. In order to retrieve the wavelet function, at the last branch,
instead of filtering with the lowpass filter (i.e. scaling filter) you
filter with the wavelet filter.

> Is there any worked examples for a daub4 cascade at iteration 1, on the
> internet somewhere I can have a look at that would help me clarify a few
> points?

Below is a simple matlab / octave function for cascade algorithm I did. I'm
sure you can translate it to C++ easily
------------------------------------------------------
function [s,w] = cascade(n,cs,cw)

  s = cs;
  w = cw;
  x2(1:2:length(w)*2) = w;
  x2(2:2:end)=0;
  x(1:2:length(s)*2) = s;
  x(2:2:end)=0;

  for i = 1:n

    s = conv(x,cs);
    w = conv(x2,cs);

    x2(1:2:length(w)*2) = w;
    x2(2:2:end)=0;
    x(1:2:length(s)*2) = s;
    x(2:2:end)=0;

  end

end
-----------------------------------------------------------

If you have octave or matlab you can try it like this:

%Filter coefficients for daub4 (h<->scaling, g<->wavelet)
h = [1+sqrt(3) 3+sqrt(3) 3-sqrt(3) 1-sqrt(3)]/(4*sqrt(2));
g = [h(4) -h(3) h(2) -h(1)];

%Calculate 5 iterations of the cascade algorithm
[s,w]=cascade(5,h,g);

plot(s); %Plot scaling function
plot(w); %Plot wavelet function


NB. The code probably has some flaws, so be aware!

-- 
Jani Huhtanen
Tampere University of Technology, Pori

>moosedude wrote:
>
>>>moosedude wrote:
>>>
>>>> 
>>>> I'm trying to implement something called the "Cascade Algorithm"
which
>> is
>>>> based upon the Dilation Equation, used when needed to approximate a
>>>> Wavelet Scaling function or mother function.
>>>> 
>>>> Everything is well apart from a small snag, I've been studying for a
>> while
>>>> now and still have no idea how to implement it?!!
>>>> 
>>>> it goes something like this;
>>>> 
>>>> f(t) = c(0)f(2t) + c(1)f(2t - 1) + c(2)f(2t - 2) + c(3)f(2t - 3)
>>>> 
>>>> where
>>>> c(0) = 0.6830127
>>>> c(1) = 1.1830127
>>>> c(2) = 0.3169873
>>>> c(3) = -0.1830127 (daubechie co-efficents, 4-tap)
>>>> 
>>>
>>>This functions is the dilation equation. IIRC, cascade algorithm
employs
>>>similar filter structure as the fast wavelet transform. However, one
>> runs
>>>the algorithm sort of backwards. Feed a unit impulse as the lowpass
band
>>>(i.e., the approximation part) and zeros for other bands and run the
>>>reconstruction to N levels. When the N approaches infinity the
discrete
>>>approximation should approach the actual scaling function.
>>>
>>>> I've tried many times on google for something that can explain this
to
>> me,
>>>> without glossing over the initial stages of "how to prime" the
>> algorithm,
>>>> but with little luck.  I think the recursion is confusing me a tad,
it
>>>> seems to say that to produce a low scale rendering of a wavelet, you
>> need
>>>> to know what the high scale version looks like first, which is odd
>>>> considering what I've already researched seems to suggest that the
low
>>>> scale rendering is the start point for the high scale rendering!?!?!
>>>> 
>>>> 
>>>> Could somebody explain it to me please, in a "cascade algorithm for
>>>> dummies" type way? I'd be very greatful (once again!)
>>>
>>>You are familiar with the filter bank implementation? If not the above
>>>explanation might not make any sense.
>>>
>>>--
>>>Jani Huhtanen
>>>Tampere University of Technology, Pori
>>>
>> 
>> 
>> Thanks Jani for your reply, I am familiar with filter banks, but my
>> interpretation of a filter bank is that the decomposition for a filter
>> bank occurs with low & high pass filters, the further down the chain
you
>> go, the more refined the information on the original input, for each
chain
>> downsampling of 2 takes place until you can divide no further.
>
>In cascade algorithm you run the reconstruction band (not the
decomposition
>band) and for scaling function you only run the lowpass branch of the
>dyadic tree. In order to retrieve the wavelet function, at the last
branch,
>instead of filtering with the lowpass filter (i.e. scaling filter) you
>filter with the wavelet filter.
>
>> Is there any worked examples for a daub4 cascade at iteration 1, on
the
>> internet somewhere I can have a look at that would help me clarify a
few
>> points?
>
>Below is a simple matlab / octave function for cascade algorithm I did.
I'm
>sure you can translate it to C++ easily
>------------------------------------------------------
>function [s,w] = cascade(n,cs,cw)
>
>  s = cs;
>  w = cw;
>  x2(1:2:length(w)*2) = w;
>  x2(2:2:end)=0;
>  x(1:2:length(s)*2) = s;
>  x(2:2:end)=0;
>
>  for i = 1:n
>
>    s = conv(x,cs);
>    w = conv(x2,cs);
>
>    x2(1:2:length(w)*2) = w;
>    x2(2:2:end)=0;
>    x(1:2:length(s)*2) = s;
>    x(2:2:end)=0;
>
>  end
>
>end
>-----------------------------------------------------------
>
>If you have octave or matlab you can try it like this:
>
>%Filter coefficients for daub4 (h<->scaling, g<->wavelet)
>h = [1+sqrt(3) 3+sqrt(3) 3-sqrt(3) 1-sqrt(3)]/(4*sqrt(2));
>g = [h(4) -h(3) h(2) -h(1)];
>
>%Calculate 5 iterations of the cascade algorithm
>[s,w]=cascade(5,h,g);
>
>plot(s); %Plot scaling function
>plot(w); %Plot wavelet function
>
>
>NB. The code probably has some flaws, so be aware!
>
>-- 
>Jani Huhtanen
>Tampere University of Technology, Pori
>


Thanks Jani for that code, it worked in octave without any bugs in it!!

Your help has been very much appreciated and I just wanted to say a quick
thankyou.