Unformatted text preview:

Wavelets • Unlike the Fourier transform, whose basis functions are sinusoids, wavelet transforms are based on small waves of limited duration • Applications – Image compression – Image denoising • Background we need – Multiresolution image pyramids – Subband coding – Multiresolution analysis and scaling functionsMultiresolution • Statistics of images such as histograms can vary significantly from one part of the image to another • Small objects – Analyze at high-resolution • Large objects – Analyze at low-resolution • Need to analyze images at multiple resolutions © 1992–2008 R. C. Gonzalez & R. E. WoodsImage pyramids N=2j j=log2N • Level 0 is of little value • Normally truncated at level P • j=J-P,…,J (P+1 levels) © 1992–2008 R. C. Gonzalez & R. E. Woods • Approximation filter • Gaussian • Mean • No filtering • Interpolation filter • Nearest neighbor • Bilinear interpolation f2↑n( )=f (n / 2) if n is even0 otherwisef2↓n( )= f (2n)Approximation and residual pyramids • Approximation pyramid – 512 x 512 (j=9) to 64 x 64 (j=6) • Residual pyramid – 64 x 64 approximation image at top of pyramid, rest are residuals – Higher compressibility • Fewer bits © 1992–2008 R. C. Gonzalez & R. E. WoodsSubband Coding • Perfect reconstruction filters: – Biorthogonal filters • Two prototyped required – Orthonormal filters • Given a single prototype filter, remaining 3 can be computed to satisfy the orthonormality constraint Approximation of f(n) Detail part of f(n) g0n( )= −1( )nh1n( )g1n( )= −1( )n+1h0n( )ˆf (n) = f (n)© 1992–2008 R. C. Gonzalez & R. E. WoodsTwo-dimensional subband coding • Daubechies orthonormal filters – Prototype: Approximation Horizontal detail Vertical detail Diagonal detail © 1992–2008 R. C. Gonzalez & R. E. WoodsThe Haar basis • Recursively keep replacing approximation image with its decomposition – Stop at some level and keep approximation • Properties: – Histograms of all detail images very similar – Can reconstruct image at various resolutions h0= 1 2 1 2h1= 1 2 −1 2© 1992–2008 R. C. Gonzalez & R. E. Woods Orthonormal Haar basisSeries expansions • Example Fourier series – Expansion set: Sines and cosines – Span: Periodic functions f (x) =αkϕk(x)k∑Function Expansion coefficients Basis functions V = Spankϕkx( ){ }Expansion set: The set of basis functions Span of expansion set: The space of functions expressible with the chosen expansion setExpansion coefficients • Orthonormal basis: – Computation of expansion coefficients: αk=ϕ(x), f (x) =ϕk*(x)∫f (x)dxDual of basis function f (x) =αkϕk(x)k∑ϕj(x),ϕk(x) =ϕj*(x)ϕk(x)∫dx =δjk=0 j ≠ k1 j = kαk=ϕk(x), f (x)Inner product Defn. of inner productScaling functions • Width scaling changes shape • Amplitude scaling makes sure that ϕj,kx( )= 2j /2ϕ2jx − k( )Scaling function: Real, square-integrable prototype function Amplitude scaling Scaling of width Position along x-axis © 1992–2008 R. C. Gonzalez & R. E. Woods ϕj, k,ϕj, k= 1Example::Example: Haar scaling function • Vj is the span achieved by fixing j and varying k • As j increases, the size of Vj increases to include functions with finer detail © 1992–2008 R. C. Gonzalez & R. E. Woods ϕ(x) =1 0 ≤ x < 10 otherwiseShifted j=0,k=1 Shifted & Scaled j=1,k=1 Scaled j=1,k=0 Vj= Spankϕj, kx( ){ }f (x) = 0.25ϕ1,0(x) +ϕ1,1(x) − 0.25ϕ1,4(x)Nested function spaces • All V0 expansion functions are contained in V1 • All Vj expansion functions are contained in Vj+1 • Any function in Vj is also in Vj+1 © 1992–2008 R. C. Gonzalez & R. E. Woods Shifted j=0,k=1 Shifted & Scaled j=1,k=1 Scaled j=1,k=0 ϕ0,k(x) =12ϕ1,2 k(x) +12ϕ1,2 k +1(x)Multiresolution analysis requirements 1. The scaling function is orthogonal to its integer translates 2. The subspaces spanned by the scaling function at low scales are nested within those spanned at higher scales 3. The only function common to all Vj is f(x)=0 4. Any function can be represented with arbitrary precision: • Haar scaling function obeys all these requirements • Under these conditions: V∞= L2R( ){ }ϕj,kx( )=αnϕj +1,n(x)n∑ϕj,kx( )=αnϕj +1,n(x)n∑Substitute ϕj +1,nx( )= 2j +12ϕ2j +1x − n( )and change αn to hϕ(n), thenϕj,kx( )= hϕ(n)n∑2j +12ϕ2j +1x − n( )set j = k = 0,also note that ϕ0,0(x) =ϕ(x)ϕx( )= hϕ(n)n∑2ϕ2x − n( )Refinement equation: Expansion functions can be built from double resolution copies of themselves Scaling function coefficients Refinement equationRefinement equation example • Haar function • Scaling coefficients • Refinement equation ϕ(x) =1 0 ≤ x < 10 otherwisehϕ(0) = hϕ(1) =12ϕx( )= hϕ(n)n∑2ϕ2x − n( )ϕx( )=ϕ2x( )+ϕ2x − 1( )Wavelet functions • Wavelet functions span the difference between adjacent scaling subspaces Vj and Vj+1 – Given a scaling function that meets the requirements discussed, we can design a wavelet function ψj,kx( )= 2j /2ψ2jx − k( )Wavelet function Amplitude scaling Scaling of width Position along x-axis Wj= Spankψj, kx( ){ }Vj +1= Vj⊕ WjUnion of function spaces © 1992–2008 R. C. Gonzalez & R. E. WoodsFunction representation L2R( )= V0⊕ W0⊕ W1⊕ ...L2R( )= V1⊕ W1⊕ W2⊕ ...L2R( )= Vjo⊕ Wjo⊕ Wjo+1⊕ ...© 1992–2008 R. C. Gonzalez & R. E. WoodsGenerating wavelet functions • For the Haar scaling function: • Then: ψ(x) = hψ(n)n∑2ϕ2x − n( )hψ(n) = −1( )nhϕ(1 − n)Wavelet function coefficients hϕ(0) = hϕ(1) =12hψ(0) = −1( )0hϕ(1 − 0) =12hψ(1) = −1( )1hϕ(1 − 1) = −12Haar wavelet function ψ(x) = hψ(n)n∑2ϕ2x − n( )Substitute hψ(0) =12 and hψ(1) = −12ψ(x) =ϕ(2x) −ϕ(2x − 1)ψ(x) =1 0 ≤ x < 0.5−1 0.5 ≤ x < 10 otherwiseHaar wavelet function • f(x) – In space V1 • fa(x) approximation – In space V0 • fd(x) difference – In space W0 ψ(x) =1 0 ≤ x < 0.5−1 0.5 ≤ x < 10 otherwisef (x) = fa(x) + fd(x)V1= V0⊕ W0© 1992–2008 R. C. Gonzalez & R. E. Woods1D Wavelet Transforms Wavelet Series Fourier Series Continuous Wavelet Transform (Continuous) Fourier Transform Discrete


View Full Document

U of U ECE 6532 - Wavelets

Download Wavelets
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Wavelets and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Wavelets 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?