Wavelet-Analysis-Image-Compression-Using-Discrete-Haar-Wavelet-Transform.

Function Descriptions

DWT (General):

use: wname = 'haar' for Haar Wavelet. = 'sym1' for Symlets. = 'db1' for Daubechies wavelet.

1. DWT performs a single-level 1-D wavelet decomposition with respect to either a particular wavelet ('wname') D = DWT(C,'wname') computes the 1-D wavelet decomposition (D) of vector C. length of C must have form 2^j where j is positive integer.

2. IDWT performs an inverse single-level 1-D wavelet decomposition with respect to either a particular wavelet ('wname') C = IDWT(D,'wname') computes the inverse 1-D wavelet decomposition (C) of vector D. length of D must have form 2^j where j is positive integer.

3. DWT2 performs a single-level 2-D wavelet decomposition with respect to either a particular wavelet ('wname') D = DWT2(C,'wname') computes the 2-D wavelet decomposition (D) of matrix C. size of C must have form 2^j*2^j where j is positive integer.

4. IDWT2 performs an Inverse single-level 2-D wavelet decomposition with respect to either a particular wavelet ('wname') C = IDWT2(D,'wname') computes the inverse 2-D wavelet decomposition (C) of matrix D. size of D must have form 2^j*2^j where j is positive integer.

5. DWT3 performs a single-level layerwise 2-D wavelet decomposition with respect to either a particular wavelet ('wname') of an image. imgD = DWT3(imgC,'wname') computes the layerwise 2-D wavelet decomposition (imgD) of image imgC. size of imgC must have form 2^j*2^j where j is positive integer.

6. IDWT3 performs an Inverse layerwise single-level 2-D wavelet decomposition with respect to either a particular wavelet ('wname') of an image. imgC = IDWT3(imgD,'wname') computes the inverse layerwize 2-D wavelet decomposition (imgC) of image imgD. size of imgD must have form 2^j*2^j where j is positive integer.

dht (Discrete Haar Transform)

1. dht performs a single-level 1-D Discrete Haar Transform D = dht(C) computes the 1-D Discrete Haar Transform (D) of vector C. the function pads C to nearest power of two.

2. idht performs an inverse 1-D Discrete Haar Transform C = idht(D) computes the inverse 1-D Discrete Haar Transform (C) of vector D. the function pads D to nearest power of two.

3. dht2 performs a 2-D Discrete Haar Transform D = dht2(C) computes the 2-D discrete Haar Transform (D) of matrix C. the matrix C will be padded to nearest power of two.

4. idht2 performs an Inverse 2-D Discrete Haar Transform C = idht2(D) computes the inverse 2-D Discrete Haar Transform (C) of matrix D. the matrix D will be padded to nearest power of two.

5. dht3 performs a single-level layerwise 2-D Discrete Haar Transform of an image. imgD = dht3(imgC) computes the layerwise 2-D discrete Haar Transform. size of imgC must will be padded to nearest power of two.

6. idht3 performs an Inverse layerwise single-level 2-D Discrete Haar Transform of an image. imgC = idht3(imgD) computes the inverse layerwize 2-D discrete Haar Transform (imgC) of image imgD. size of imgD must will be padded to nearest power of two.

--Y. Phalak 4-Dec-2019.

Introduction

Signal-Processing is faster and simpler in a sparse representation where few Fourier coefficients reveal the information. Such representations can be constructed by decomposing signals over elementary waveforms chosen in the orthonormal basis domain explained in general Fourier analysis. But results are shown by such methods sometimes introduces errors due to certain conditions. Such conditions can be taken care of by wavelet transforms.

The discovery of wavelet orthogonal bases and local time-frequency basis has opened the door to huge ways of new transforms. Adapting sparse representations to signal properties, and deriving efficient processing operators, is, therefore, a necessary survival strategy. An orthogonal basis is a dictionary of the minimum size that can yield a sparse representation if designed to concentrate the signal energy over a set of few vectors. This set gives a geometric signal description.

In this report, we will present an example of an orthonormal system on [0, 1) known as the Haar system. The Haar basis is the simplest and historically the first example of an orthonormal wavelet basis. Many of its properties stand in sharp contrast to the corresponding properties of the trigonometric basis (Fourier Basis). For example, (1) The Haar basis functions are supported on small subintervals of [0, 1), whereas the Fourier basis functions are nonzero on all of [0,1), (2) The Haar basis functions are step functions with jump discontinuities, whereas the Fourier basis functions are C^∞ on [0, 1), (3) The Haar basis replaces the notion of frequency (represented by the index n in the Fourier basis) with the dual notions of scale and location (separately indexed by j and k), (4) the Haar basis provides a very efficient representation of functions that consist of smooth, slowly varying segments punctuated by sharp peaks and discontinuities, whereas the Fourier basis best represents functions that exhibit long term oscillatory behavior.

Fourier Analysis And Its Limitations.

When processing signals, such as audio, radio waves, light waves, seismic waves, and even images, Fourier analysis can isolate narrowband components of a compound waveform, concentrating them for easier detection or removal. A large family of signal processing techniques consist of Fourier-transforming a signal, manipulating the Fourier-transformed data in a simple way, and reversing the transformation

General Advantages And Disadvantages.

Advantages.

• Fourier series and the Fourier transform hold a unique place in the analysis of many linear operators, essentially because the complex exponentials are the eigenvectors/eigenfunctions of linear, shift-invariant operators. In signal processing, this is illustrated via the convolution theorem, though the theory goes much deeper (see: Pseudo-differential operators). Related to this is the role of the Fourier transform in the mathematical foundations of quantum mechanics - Fourier analysis is directly related to "momentum", since the eigenfunctions of the momentum operator − i∂_x are the complex exponentials.

• In this same vein, Fourier analysis leads to an extremely powerful theory of smoothness, because of the correspondence between differentiability and decay of the Fourier coefficients. See Sobolev spaces.

• Fourier analysis is very powerful in the study of generalized functions.

• From a numerical analysis and signal processing point of view, the accuracy of Fourier based methods has the advantage of being limited only by the smoothness of the underlying function. This means several things: Fourier methods are very good at approximating very smooth things, but perhaps not so good at approximating less smooth things.

• The general techniques we learn from Fourier, like expanding functions in an orthonormal basis, are extremely powerful. See spectral theory.

Disadvantages.

• First off, from a numerical standpoint, issues of convergence play a massive role. See Gibbs Phenomenon. This leads to a secondary issue that Fourier series are not "efficient" at resolving discontinuous or multi-scale functions. This is illustrated, for example, by the vast difference between original JPEG image compression, which is based on Fourier series, and modern image compression techniques like JPEG2000, which are based on more multi-scale techniques like Wavelets.

• Related to the above fact is that the Fourier series give no information on the spatial/temporal localization of features. A Fourier series or transform can tell you that there is a discontinuity, but it can’t tell you where it is. Think of a musical score: having just the Fourier transform is like knowing which notes you need to play, but not when to play them. Not very useful if you want to hear music! This is partially what inspired the study of phase-space/time-frequency/wavelet representations (which incidentally are playing an increasing role in quantum theory).

• Classical Fourier analysis is less generally applicable for nonlinear and nonstationary/transient phenomenon (although it is still hugely powerful in some cases!)

The Gibbs phenomenon.

The Gibbs phenomenon involves both the fact that Fourier sums overshoot at a jump discontinuity, and that this overshoot does not die out as more terms are added to the sum.

The three figures below demonstrate the phenomenon for a square wave of height π/4 whose Fourier expansion is given by:

As can be seen, as the number of terms rises, the error of the approximation is reduced in width and energy, but converges to a fixed height. A calculation for the square wave gives an explicit formula for the limit of the height of the error. It turns out that the Fourier series exceeds the height π/4 of the square wave by:

The Gibbs phenomenon reflects the difficulty inherent in approximating a discontinuous function by a finite series of continuous sine and cosine waves. It is important to put emphasis on the word finite because even though every partial sum of the Fourier series overshoots the function it is approximating, the limit of the partial sums does not. The value of x where the maximum overshoot is achieved moves closer and closer to the discontinuity as the number of terms summed increases so, again informally, once the overshoot has passed by a particular x, convergence at that value of x is possible.

The Haar System.

In mathematics, the Haar wavelet is a sequence of rescaled "square-shaped" functions which together form a wavelet family or basis. Wavelet analysis is similar to Fourier analysis in that it allows a target function over an interval to be represented in terms of an orthonormal basis. The Haar sequence is now recognized as the first known wavelet basis

The Haar Scaling Functions and the Haar Functions.

Definition: Let p(x) = X_[0.1)(x), and for each j.k ∈ Z, define p_j.k(x) = 2^j/2p(2^j,r−k) = D₂, T_kp(x).

The collection {p_j, k(x)}_{t. k ∈ Z} is referred to as the system of Haar scaling function. For each j ∈ Z. the collection {p_1, k(x)}_k ∈ Z is referred to as the system of scale j Haar scaling functions. Let h(x) = χ_[0, 1/2)(x) − χ_[1/2, 1](x), and for each j, k ∈ Z, define

h_j, k(x) = 2^J/2h(2^jx−k) = D_2^jT_kh(x) The collection {h_j, k(x)}_{j, k ∈ Z} is referred to as the Haar system on R. For each j ∈ Z, the collection {h_J, k(x)}_k ∈ Z is referred to as the system of scale j Haar functions.

Properties:

• For each j.k ∈ Z, p_j.k(x) = 2^j/2l_{*I j.k}(x). so that p_j.k(x) is supported on the interval I_j.k and does not vanish on that interval. Therefore, we refer to the scaling function p_j.k(.r) as being associated with the interval I_j, k.

• For each j, k ∈ Z

and

The Haar Bases on [0,1].

For any integer J ≥ 0, the scale J Haar system on [0, 1] is the collection

When J = 0, this collection will be referred to simply as the Haar system on [0, 1].

(a) The Haar system on [0, 1] consists of precisely those Haar functions h_j, k(x) corresponding to dyadic intervals I_j, k that are sub- sets of [0, 1], together with the single scaling function p_0, 0(x)

(b) For J > 0, the scale J Haar system on [0, 1] consists of precisely those Haar functions h_j, k(x) corresponding to dyadic intervals I_j.k for which j≥ J and that are subsets of [0, 1], together with those scale J Haar scaling functions that are supported in [0, 1].

Approximate and Detailed Operators.

Definition: For each j ∈ Z, define the approximation operator P_j on functions f(x), L² on R, by

(a) For each j ∈ Z, define the approximation space V_j by

since {p_ȷ, k(x):k∈Z} is an orthonormal system on R ∈ Z. that P_jf(x) is the function in V_j best approximating f(x) in the L² sense.

(b) since p_j, k(x) = 2^j/2χ_Ij, k(x)

In other words, on the interval I_j, k, P_jf(x) is the average value of f(x) on I_J, k

Definition: For each j ∈ Z, define the detail operator Q_j on functions f(x), L² on R, by

(a) Approximate Operator of Second Degree Hat function, (b) Approximate Operator of Second Degree Hat function, (c) Detailed Operator of Second Degree Hat function, (d)Approximation of Second Degree Hat function Using Haar Basis.

(a) For each j ∈ Z, we define the wavelet space W_j by

since {h_j, k(x)}_k ∈ Z is an orthonormal system on R and in light of ( 5.12) Lemma 2.51 implies that Q_jf(x) is the function in W_j best approximating f(x) in the L² sense.

(b) In light of the interpretation of P_jf(x) as the blurred version of f(x) at scale 2^− j, we can interpret Q_jf(x) as containing those features of f(x) that are of size smaller than 2^− J but larger than 2^{− ȷ − 1}. That is, Q_jf(x) has those details invisible to the approximation P_jf(x) but visible to the approximation P_J + 1f(x).

The Discrete Haar Transform in 1 Dimension.

Motivation.

A function f(x) (defined on [ 0.1] his an expansion in terms of Haar functions as follows. Give that any integer J ≥ 0.

in L² on [0.1]

Thus. the Haar coefficients of f(x) can be approximated by the Haar coefficients of P_Nf(x). That is.

Derivation.

Suppose that we are given a finite sequence of data of length 2^N for some N ∈ N.{c₀(k)}_k = 0² − 1. We assume that for some underlying function f(x) c₀(k) = ⟨f⋅p_N, k⟩. Fix J ∈ N.J < N. and for each 1 ≤ j ≤ J, define,

c_j(k) = ⟨f,p_{N − j, k}⟩   and d_j(k) = ⟨f.h_{N − j..⟩}⟩

It turns out that there is a convenient recursive algorithm that can be used to compute the coefficients c_j(k) and d_j(k) from c_j − 1(k)..

By writing in Matrix form,

As with the DFT, the DHT can be thought of as a linear transformation on a finite-dimensional space and as such can be written as multiplication by a matrix. Given L ∈ N even, define the (L/2) × L matrices H_L and G_L by:

Define the L × L matrix 𝒲_L by

The matrix H_L is referred to as the approximation matrix, the matrix G_L as the detail matrix, and the matrix 𝒲_L as the wavelet matrix.

Algorithms for DHT and IDHT

Discrete Haar Transform: Given J, N ∈ N with J < N and a vector

of length 2^N, the DHT of c₀ is the vector

where,

Tree Diagram for The DHT.

Comparison of Discrete Haar Wavelet Transform with Discrete Cosine Transform.

As shown in the figure,the lossy compression is performed on the given discrete signal by using discrete Haar transform (DHT) and by using discrete cosine transform (DCT).

(a) Original Discrete Signal, (b) DHT of the Signal, (c) DCT of the Signal,(d) IDHT of Compressed Signal, (e) IDCT of Compressed Signal.

As we can see, the information at the discontinuity in the original signal is sustained by the DHT method whereas, it is smoothed out in the case of DCT method.

Image Compression Using Discrete Haar Wavelet Transform.

As shown in the figure below, the Discrete Haar Wavelet Transform and The Discrete Cosine Transforms are taken. As most of the pixel values are near to the zero (i.e. black), image can be compressed by setting those values to zero.

(a) Original Image, (b) DHT of the Image, (c) DCT of the Image.

Hence, by applying lossy compression on the Discrete Cosine Transform of the image, The Inverse Discrete Cosine Transform of the compressed images are given by:

(a) 97% compressed using DCT, (b) 99% compressed using DCT, (c) 99.99% compressed using DCT.

Similarly, applying lossy compression on the Discrete Haar Transform of the image, The Inverse Discrete Haar Transform of the compressed images are given by:

(a) 97% compressed using DHT, (b) 99% compressed using DHT, (c) 99.99% compressed using DHT.

Conclusions.

The normalized version of the Haar wavelet offers greater compression, and yields better-looking results compared to the standard one. This is due to the properties of orthogonal matrices. The variant that implements loops to perform the normalization in the Haar wavelet transformation process is better in terms of algorithm complexity compared to the variant that generates the required Haar matrices and performs matrix multiplication. Throughout this project, we focused on the Haar wavelet transform as a window to better understanding the different compression processes since they boil down to the same essence. Thus, this research and implementation have been useful in terms of gaining a lot of insight into the field of image compression and its application of mathematical concepts

REFERENCES

1. ] Walnut, David F. An introduction to wavelet analysis / David F. Walnut p. cm. (Applied and numerical harmonic analysis) Includes bibliographical references and index. ISBN 0 − 8176 − 3962 − 4 (alk. paper).

2. ] Stéphane Mallat, a Wavelet tour of signal processing,The Sparse Way,ISBN 13 : 9780 − 12 − 374370 − 1.

3. ] A. Haar. Zur theorie der orthogonalen funktionensysteme. Math. Annal., 69:331–371, 1910.