Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » The filtered transform

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • NSF Partnership display tagshide tags

    This module is included inLens: NSF Partnership in Signal Processing
    By: Sidney BurrusAs a part of collection: "Multiresolution Analysis, Filterbank Implementation, and Function Approximation using Wavelets"

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This module is included inLens: UniqU's lens
    By: UniqU, LLCAs a part of collection: "Multiresolution Analysis, Filterbank Implementation, and Function Approximation using Wavelets"

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module is included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

The filtered transform

Module by: Veronique Delouille. E-mail the author

Introduction

We saw in a previous section an example of a scaling function ϕ,ϕ, and we outlined how to construct ψψ(also called the mother wavelet) starting from ϕϕ(the father wavelet). Suppose now we have at our disposal {ϕj,k}{ϕj,k} and {ψj,k}.{ψj,k}. In fact, it is sufficient for our purpose to know the value of these functions at dyadic points 2-jk,jZZ,kZZ.2-jk,jZZ,kZZ. We would like to compute in an efficient way the wavelet representation described in Homogeneous and inhomogeneous representation of f, that is, we would like to have a fast algorithm to compute the wavelet coefficients.

Filter algorithm-Fast wavelet transform

We will still use the relationship between the functions spaces VjVj and WjWj to find a fast wavelet transform (FWT). We start by recalling that, since both the scaling function ϕV0ϕV0 and the wavelet ψW0ψW0 are in V1,V1, and since V1V1 is generated by ϕ1,k=2ϕ(2x-k),kZZ,ϕ1,k=2ϕ(2x-k),kZZ, there exist two sequences {hk}{hk} and {gk}l2{gk}l2 such that

ϕ ( x ) = 2 k h k ϕ ( 2 x - k ) ϕ ( x ) = 2 k h k ϕ ( 2 x - k )
(1)
ψ ( x ) = 2 k g k ϕ ( 2 x - k ) ψ ( x ) = 2 k g k ϕ ( 2 x - k )
(2)

for all xIR.xIR. On the other hand, we know that V1=V0W0V1=V0W0 and as we consider the orthogonal case, it follows immediately that :

2 ϕ ( 2 x ) = k [ h - 2 k ϕ ( x - k ) + g - 2 k ψ ( x - k ) ] 2 ϕ ( 2 x ) = k [ h - 2 k ϕ ( x - k ) + g - 2 k ψ ( x - k ) ]
(3)
2 ϕ ( 2 x - 1 ) = k [ h 1 - 2 k ϕ ( x - k ) + g 1 - 2 k ψ ( x - k ) ] . 2 ϕ ( 2 x - 1 ) = k [ h 1 - 2 k ϕ ( x - k ) + g 1 - 2 k ψ ( x - k ) ] .
(4)

These two equations Equation 3 and Equation 4 can be combined into a single formula:

2 ϕ ( 2 x - l ) = k [ h l - 2 k ϕ ( x - k ) + g l - 2 k ψ ( x - k ) ] , l Z Z , 2 ϕ ( 2 x - l ) = k [ h l - 2 k ϕ ( x - k ) + g l - 2 k ψ ( x - k ) ] , l Z Z ,
(5)

which is called the “decomposition relation” of ϕϕ and ψ.ψ.

Note that, in the bi-orthogonal case there are four sequences in l2l2 instead of two (denoted here by {hk}{hk} and {gk}{gk}): we have two sequences for the 2-scales relations Equation 1, Equation 2, and two others for the decomposition relations Equation 3, Equation 4. In the following algorithm, we drop the normalisation constant. Suppose that we want to decompose ff as a sum of wavelets and that we have computed, or are given, the inner products of ff with ϕJ,k,ϕJ,k, where JJ is the finest scale we can work on. We denote these inner products by cJ.cJ. Now, our task is to compute ckjckj and dkj,j<J,dkj,j<J, where

P j f = k c k j ϕ ( 2 j x - k ) ; c k j = < f j , ϕ j , k > P j f = k c k j ϕ ( 2 j x - k ) ; c k j = < f j , ϕ j , k >
(6)
Q j f = k d k j ψ ( 2 j x - k ) ; d k j = < f j , ψ j , k > Q j f = k d k j ψ ( 2 j x - k ) ; d k j = < f j , ψ j , k >
(7)

Decomposition algorithm

By combining Equation 5, Equation 6 and Equation 7, we get (see [1]):

c k j - 1 = l h l - 2 k c l j d k j - 1 = l g l - 2 k c l j . c k j - 1 = l h l - 2 k c l j d k j - 1 = l g l - 2 k c l j .
(8)

Observe that both cj-1cj-1 and dj-1dj-1 are obtained from cjcj by “moving average” schemes, using the decomposition sequence as “weights”, with the exception that these moving averages are sampled only at the even integers. This is called downsampling.

Reconstruction algorithm

In the orthogonal case, the reconstruction algorithm follows easily from the relationships:

c n j + 1 = < f j + 1 , ϕ j + 1 , n > f j + 1 = P j + 1 f = P j f + Q j f = k c k j ϕ j , k + k d k j ψ j , k , c n j + 1 = < f j + 1 , ϕ j + 1 , n > f j + 1 = P j + 1 f = P j f + Q j f = k c k j ϕ j , k + k d k j ψ j , k ,
(9)

which gives:

c n j + 1 = k c k j < ϕ j , k , ϕ j + 1 , n > + k d k j < ψ j , k , ϕ j + 1 , n > = k [ c k j h n - 2 k + d k j g n - 2 k ] . c n j + 1 = k c k j < ϕ j , k , ϕ j + 1 , n > + k d k j < ψ j , k , ϕ j + 1 , n > = k [ c k j h n - 2 k + d k j g n - 2 k ] .
(10)

Hence cj+1cj+1 is obtained from cjcj and djdj by two moving average.

Mallat's algorithm

In the previous section, we assumed that we knew the coefficients

c k J = < f , ϕ J , k > , k Z Z . c k J = < f , ϕ J , k > , k Z Z .
(11)

The question to ask is: how to compute these coefficients ? In Mallat's algorithm (see [4]), we consider that the finest scale is constituted by the observations{Yk}k=1n{Yk}k=1n themselves. To use the MRA presented above, these observations must be taken at equispaced points, i.e. we can write that

{ Y k } k = 1 n = { f ( k n ) } k = 1 n . { Y k } k = 1 n = { f ( k n ) } k = 1 n .
(12)

Moreover, we assume that nn (the number of observations) is a power of 2 : n=2J,n=2J, with JJ denoting the finest level.

Mallat's algorithm is based on the fact that, as jj tends to infinity, the support of ϕj,kϕj,k tends to become smaller and smaller. We have:

lim j ϕ j , k ( x ) δ ( x - k n ) = 1 if x = k / n = 0 otherwise. lim j ϕ j , k ( x ) δ ( x - k n ) = 1 if x = k / n = 0 otherwise.
(13)

Hence Mallat considered that we can compute ckJckJ as:

c k J f ( x ) δ ( x - k / n ) = f ( k / n ) = Y k . c k J f ( x ) δ ( x - k / n ) = f ( k / n ) = Y k .
(14)

The starting point of this algorithm is thus extremely simple: we just take as value for ckJckJ the whole set of observations. Thereafter, having constructed the filters {hk}and{gk}{hk}and{gk} (or, equivalently, having constructed ϕϕ and ψψ), we can compute a fast wavelet transform using the algorithm presented in the previous section.

References

  1. C.K. Chui. (1992). An Introduction to Wavelets. San Diego, CA: American Press.
  2. I. Daubechies. (1992). Ten Lectures on wavelets. Philadelphia: Society for Industrial and Applied Mathematics.
  3. W. Härdle, G. Kerkyacharian, D. Picard, and A. Tsybekov. (1998). Wavelets, Approximation, and Statistical Applications. Lectures notes in Statistics.
  4. S. Mallat. (1989). A theory for multiresolution signal decomposition: the wavelet representation. I.E.E.E Trans. on pattern analysis and machine intelligence, 11(7), 674-693.
  5. Y. Meyer. (1990). Ondelettes et Opérateurs, I: Ondelettes, II:. Operateurs de Calderón-Zygmund.

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks