Example - Haar Wavelets - IIT Delhi

1 Example - Haar Wavelets Suppose we are given a 1D "image" with a resolution of 4 pixels: [9 7 3 5]. The Haar wavelet transform is the following: L0 D1 D2 D3. Example - Haar Wavelets (cont d). Start by averaging the pixels together (pairwise) to get a new lower resolution image: To recover the original four pixels from the two averaged pixels, store some detail coefficients. Example - Haar Wavelets (cont d). Repeating this process on the averages gives the full decomposition: Example - Haar Wavelets (cont d). The Harr decomposition of the original four-pixel image is: We can reconstruct the original image to a resolution by adding or subtracting the detail coefficients from the lower-resolution versions. 2 1 -1. Example - Haar Wavelets (cont d). Note small magnitude detail coefficients!

2 Dj Dj-1 How to compute Di ? D1. L0. How to compute Di ? (cont d). If f(t) Vj+1, then f(t) can be represented using basis functions (t) fromVj+1: f (t ) = ck (2 j +1 t k ). Vj+1 k Alternatively, f(t) can be represented using two basis functions, (t) from Vj and (t) from Wj: Vj+1 = Vj + Wj f (t ) = ck (2 j t k ) + d jk (2 j t k ). k k How to compute Di ? (cont d). Think of Wj as a means to represent the parts of a function in Vj+1 that cannot be represented in Vj f (t ) = ck (2 j +1 t k ). k f (t ) = ck (2 j t k ) + d j ,k (2 j t k ) differences k k between Vj and Vj+1. Vj, Wj How to compute Di ? (cont d). Vj+1 = Vj + W. using recursion on Vj: j Vj+1 = Vj-1+Wj-1+Wj = = V0 + W0 + W1 + W2 + + Wj if f(t) Vj+1 , then: f (t ) = ck (t k ) + d j ,k (2 j t k ). k k j V0 W0, W1, W2, . basis functions basis functions wavelet expansion (cont d).

3 F(t) is written as a linear combination of (t-k) and . (2jt-k) : j f (t ) = ck (t k ) + d jk (2 t k ). k k j scaling function wavelet function Note: in Fourier analysis, there are only two possible values of k ( , 0 and /. 2); the values j correspond to different scales ( , frequencies). 1D Haar Wavelets (cont d). 1D Haar Wavelets (cont d). Mother wavelet function: 1. -1 0 1/2 1. Note that (x) . (x) = 0 ( , orthogonal). 1. 1 =0. 0 1 . -1 0 1/2 1. 1D Haar Wavelets (cont d). basis for V 1 : Note basis W 1 : that inner product j=1 is zero! 1D Haar Wavelets (cont d). Basis functions ji of W j form a basis in V j+1. Basis functions ji of V j 1D Haar Wavelets (cont d). (t). (t). Example - Haar basis (revisited). Decomposition of f(x). f(x)=. 0,2(x). V2 1,2(x). 2,2(x). 3,2(x). Decomposition of f(x) (cont d).

4 0,1(x). V1and W1 1,1(x). V2=V1+W1. 0,1(x). 1,1(x). Example - Haar basis (revisited). Decomposition of f(x) (cont d). 0,0(x). V0 ,W0 and W1 0,0(x). V2=V1+W1=V0+W0+W1. 0,1(x). 1,1(x). Example - Haar basis (revisited). Example Example (cont d). Convention for illustrating 1D Haar wavelet decomposition (cont d). average x x x x x x x x detail . 2D Haar wavelet Transform The 2D Haar wavelet decomposition can be computed using 1D Haar wavelet decompositions ( , 2D Haar wavelet basis is separable). Two decompositions Standard decomposition Non-standard decomposition Each decomposition corresponds to a different set of 2D basis functions. Standard Haar wavelet decomposition Steps (1) Compute 1D Haar wavelet decomposition of each row of the original pixel values. (2) Compute 1D Haar wavelet decomposition of each column of the row-transformed pixels.

5 Standard Haar wavelet decomposition (cont d). average (1) row-wise Haar decomposition: detail re-arrange terms xxx x . xxx x .. xxx .. x . Standard Haar wavelet decomposition (cont d). average (1) row-wise Haar decomposition: detail from previous slide: row-transformed result .. Standard Haar wavelet decomposition (cont d). average detail (2) column-wise Haar decomposition: row-transformed result column-transformed result .. Example row-transformed result . re-arrange terms .. Example (cont d). column-transformed result .. Non-standard Haar wavelet decomposition Alternates between operations on rows and columns. (1) Perform one level decomposition in each row ( , one step of horizontal pairwise averaging and differencing). (2) Perform one level decomposition in each column from step 1 ( , one step of vertical pairwise averaging and differencing).

6 (3) Repeat the process on the quadrant containing averages only ( , in both directions). Non-standard Haar wavelet decomposition (cont d). one level, horizontal one level, vertical Haar decomposition: Haar decomposition: xxx x . xxx x .. xxx .. x .. Note: averaging/differencing of detail coefficients shown Non-standard Haar wavelet decomposition (cont d). re-arrange terms . one level, vertical one level, horizontal . Haar decomposition Haar decomposition on green quadrant on green quadrant .. Example re-arrange terms .. Example (cont d).