next up previous contents index
Next: owave2 Up: Reference Previous: iowave2   Contents   Index


$ \bigcirc$Name

owave1 Computes the orthogonal wavelet transform of an 1D signal

$ \bigcirc$Command Synopsis

owave1 [-r RecursNum] [-h HaarLevel] [-e EdgeMode] [-p PrecondMode] [-i] [-n FilterNorm] Signal WavTrans ImpulseResponse [EdgeIR ]

-r RecursNum : Number of levels (default 1)

-h HaarLevel : Continue decomposition with Haar until HaarLevel

-e EdgeMode : Edge processing mode (0/1/2/3, default 3)

-p PrecondMode : Edge preconditionning mode (0/1/2, default 0)

-i : Invertible transform

-n FilterNorm : Filter taps normalization. 0: no normalization, 1: sum equal to 1.0, 2: squares sum equal to 1.0 (default)

Signal : Input signal

WavTrans : Wavelet transform of Signal

ImpulseResponse : Impulse response of inner filters

EdgeIR : Impulse reponses of edge and preconditionning filters

$ \bigcirc$Function Summary

void owave1 (NumRec , Haar , Edge , Precond , Inverse , FilterNorm , Signal , Output , Ri , Edge_Ri )

int *NumRec ;

int *Haar ;

int *Edge ;

int *Precond ;

int *Inverse ;

int *FilterNorm ;

Fsignal Signal ;

Wtrans1d Output ;

Fsignal Ri ;

Fimage Edge_Ri ;

$ \bigcirc$Description

owave1 computes the J level discrete wavelet transform of the univariate digitized signal whose sample values are in the file Signal, according to the pyramidal algorithm of S. Mallat [Mal89]. The reader is assumed to be familiar with the wavelet theory (if not, you may read [Mal97]).

Let {Vj}j $\scriptstyle \in$ Z be a multiresolution analysis of L2(IR). {Vj} is a non-increasing sequence of closed subspaces of L2(IR), and there exists a function $ \varphi$, called the scaling function, such that {$ \varphi_{{j,k}}^{}$ = 2-j/2$ \varphi$(2-j. - k)}k $\scriptstyle \in$ Z is an orthonormal basis of Vj. If f is a continuous-time signal then the orthogonal projection PVjf of f on Vj is an approximation of f at the scale 2j. One has

PVjf = $\displaystyle \sum_{{k}}^{}$ < f,$\displaystyle \varphi_{{j,k}}^{}$ > $\displaystyle \varphi_{{j,k}}^{}$

where < .,. > is the scalar product of L2(IR). The coefficients < f,$ \varphi_{{j,k}}^{}$ > are now denoted Aj[k] (A is for approximation or average).

Aj[k] = < f,$\displaystyle \varphi_{{j,k}}^{}$ >

Let Wj be the orthonormal complement of Vj in Vj-1, and $ \psi$ the mother wavelet associated to {Vj}. Then {$ \psi_{{j,k}}^{}$ = 2-j/2$ \psi$(2-j. - k)}k $\scriptstyle \in$ Z is an orthonormal basis of Wj. The orthonormal projection PWjf of f on Wj represents the difference of information between scales 2j-1 and 2j that is, the detail at the scale 2j. One has

PWjf = $\displaystyle \sum_{{k}}^{}$ < f,$\displaystyle \psi_{{j,k}}^{}$ > $\displaystyle \psi_{{j,k}}^{}$

The coefficients < f,$ \psi_{{j,k}}^{}$ > are denoted Dj[k] (D is for detail).

Dj[k] = < f,$\displaystyle \psi_{{j,k}}^{}$ >

Consider now the function f in V0 defined by

f = $\displaystyle \sum_{{k}}^{}$A0[k$\displaystyle \varphi_{{0,k}}^{}$

where A0[k] are the sample values stored in the file Signal.

Since V0 = W1 $ \oplus$ W2 $ \oplus$ ... $ \oplus$ WJ $ \oplus$ VJ for any positive integer J, one also has

f = $\displaystyle \sum_{{k}}^{}$AJ[k]$\displaystyle \varphi_{{J,k}}^{}$ + $\displaystyle \sum_{{j=1}}^{{J}}$$\displaystyle \sum_{{k}}^{}$Dj[k]$\displaystyle \psi_{{j,k}}^{}$

owave1 performs the wavelet decomposition of f up to the level J, i.e. computes the coefficients of the detail sub-signals (Dj[k])k $\scriptstyle \in$ Z, 1 $ \leq$ j $ \leq$ J and of the average sub-signal (AJ[k])k $\scriptstyle \in$ Z. This is done recursively : the sequence A1[k] and D1[k] are computed from the sequence A0[k] , the sequences A2[k] and D2[k] are computed from A1[k] , a.s.o.. The same algorithm is applied at each step. This algorithm is very simple due to the two-scales relationships :

$\displaystyle \varphi$(t) = $\displaystyle \sqrt{{2}}$$\displaystyle \sum_{{k}}^{}$hk$\displaystyle \varphi$(2t - k)      
$\displaystyle \psi$(t) = $\displaystyle \sqrt{{2}}$$\displaystyle \sum_{{k}}^{}$gk$\displaystyle \varphi$(2t - k)      

where gk = (- 1)kh1-k. And thus
Aj+1[n] = $\displaystyle \sum_{{k}}^{}$hk-2nAj[k]      
Dj+1[n] = $\displaystyle \sum_{{k}}^{}$gk-2nAj[k]      

If the filter (hk) is a low-pas filter, regardless of its definition by the two-scales relationships, then Aj+1[k] is effectively an average of Aj[k]. From this point of view owave1 performs a subband coding of the signal. (hk) is said to have the exact reconstruction property if one can reconstruct exactly Aj[k] from Aj+1[k] and Dj+1[k] by interpolating and filtering this two sub-signals and adding the results. If moreover the same filter bank is used for the reconstruction, then (hk) is called conjugate quadrature filter (CQF) (see [SB86]). Filters associated to orthogonal wavelet bases, i.e. that stems from the two-scales relationships above are always CQF and are indeed low-pass filters (see iowave1 for the description of the reconstruction algorithm).

Notice that the filters that are associated to compactly supported wavelets are of finite length : hk = 0, if | k| > K where K is a positive integer. See [Dau88] for the construction and properties of these filters.

The fact that the discrete signal is of finite size raises some problems near edges, i.e. when computing the first and last coefficients of the average and detail sub-signals. There are several ways of dealing with these problems.

Because of the down-sampling, the size of the average and detail signals is divided by two at each step (omitting edge problems). As a consequence the size of the wavelet decomposition (obtained by adding the sizes of each sub-signal in it) is equal to the size of the original signal, and the scale parameter J is upper bounded since obviously one should have n $ \geq$ 2J where n is the size of the signal. Moreover, when edge processing is performed via periodization or application of special filters, the size of the signal should be a multiple of 2J.

If one chooses the 0-extension or the reflexion for edge processing, and one wants to get the exact reconstruction property, then one has to keep extra coefficients near edges. Thus the size of the wavelet decomposition is in fact slightly larger than the size of the original signal. To overcome this problem one can use one of the two other methods of edge processing.

When the edge processing is done with special filters, then one has the possibility to do a preconditionning of the coefficients near edges before applying the wavelet decomposition. Then one recovers the cancellation property (any polynomial signal of degree less than the cancellation degree of the mother wavelet is decomposed in a zero valued detail sub-signal and a polynomial average sub-signal). This is an inversible linear (but not orthogonal in general) transform.

If the impulse response has size N then the complexity of the algorithm is roughly (2 - 2-(J-1))nN multiplications and additions.

The resulting sub-signals A1, A2,..., AJ and D1, D2,..., DJ are stored in files having all the same prefix Wavtrans. The name of the file is prefix_j_A.wtrans1d for Aj and prefix_j_D.wtrans1d for Dj.

The coefficients hk of the filter's impulse response are stored in the file ImpulseResponse. The coefficients of the filter's impulse response for computing the edge coefficients are stored in the file EdgeIR. Notice that the underlying Daubechies wavelet basis must be the same for edge and inner filter.

$ \bigcirc$See Also

precond1d, sconvolve.


$ \bigcirc$Version 1.2

Last Modification date : Thu Jan 31 15:11:32 2002

$ \bigcirc$Author

Jean-Pierre D'Ales

next up previous contents index
Next: owave2 Up: Reference Previous: iowave2   Contents   Index
mw 2004-05-05