Short introduction to Haar Wavelets:

Haar basis was developed by Alfred Haar in 1909. It is the simplest yet the most widely adopted wavelet basis. For clarity, we first start from one dimensional Haar basis. Given a 1D discrete signal, we can represent it by a combination of *average* and *difference (or detail)*, like the following example:

The functions in the right hand side can be expressed as

,

are called mother scale function and mother wavelet function, respectively. Other basis functions could be derived by scaling and translating them. Here are some examples:

For a 1-D discrete signal with length N (N>2), we can repeat this average & difference process to obtain 1 scale coefficient and N-1 detail coefficients.

The following is an example of transforming a 1-D discrete signal [ 9 7 3 5 ]

Thus the wavelet transform of [ 9 7 3 5 ] is given by [ 6 2 1 -1].

Less significant detail coefficients could be discarded for data compression purposes, like the following image shows:

To perform 2D Haar wavelet transform, we can simply do full 1D transform along one dimension and then do another full 1D transform along the other dimension. This is called standard decomposition.

Or, we can perform 1D Haar transform alternatively along different dimensions, in each level. This is called nonstandard decomposition.

Non-standard decomposition has some desired properties, such fewer assignments are required than in standard decomposition, and square local supports for every basis functions.

One application of 2D Haar wavelet is image compression. Here is an image reconstruction example using different numbers of coefficients:

It’s an example produced by my own implementation, and the coefficient pickup scheme is naive (just pick those with large magnitude), so it does not yield best compression quality.

References:

1. Eric J. Stollnitz Tony D. DeRose David H. Salesin, Wavelets for Computer Graphics: A Primer.

### Like this:

Like Loading...

Pingback: Real-time wavelet decomposition using compute shader | Cheng's Programming Blog