Discrete Fourier Analysis and Wavelets

S. Allen Broughton, PhD, is Professor Emeritus of Mathematics at Rose-Hulman Institute of Technology. Dr. Broughton is a member of the American Mathematical Society (AMS) and the Society for the Industrial Applications of Mathematics (SIAM), and his research interests include the mathematics of image and signal processing, and wavelets. Kurt Bryan, PhD, is Professor of Mathematics at Rose-Hulman Institute of Technology. Dr. Bryan is a member of MAA and SIAM and has authored over twenty peer-reviewed journal articles.

• Preface xviiAcknowledgments xxi1 Vector Spaces, Signals, and Images 11.1 Overview 11.2 Some Common Image Processing Problems 11.2.1 Applications 21.2.1.1 Compression 21.2.1.2 Restoration 21.2.1.3 Edge Detection 31.2.1.4 Registration 31.2.2 Transform-Based Methods 31.3 Signals and Images 31.3.1 Signals 41.3.2 Sampling, Quantization Error, and Noise 51.3.3 Grayscale Images 61.3.4 Sampling Images 81.3.5 Color 91.3.6 Quantization and Noise for Images 91.4 Vector Space Models for Signals and Images 101.4.1 Examples—Discrete Spaces 111.4.2 Examples—Function Spaces 141.5 Basic Waveforms—The Analog Case 161.5.1 The One-Dimensional Waveforms 161.5.2 2D Basic Waveforms 191.6 Sampling and Aliasing 201.6.1 Introduction 201.6.2 Aliasing for Complex Exponential Waveforms 221.6.3 Aliasing for Sines and Cosines 231.6.4 The Nyquist Sampling Rate 241.6.5 Aliasing in Images 241.7 Basic Waveforms—The Discrete Case 251.7.1 Discrete Basic Waveforms for Finite Signals 251.7.2 Discrete Basic Waveforms for Images 271.8 Inner Product Spaces and Orthogonality 281.8.1 Inner Products and Norms 281.8.1.1 Inner Products 281.8.1.2 Norms 291.8.2 Examples 301.8.3 Orthogonality 331.8.4 The Cauchy–Schwarz Inequality 341.8.5 Bases and Orthogonal Decomposition 351.8.5.1 Bases 351.8.5.2 Orthogonal and Orthonormal Bases 371.8.5.3 Parseval’s Identity 391.9 Signal and Image Digitization 391.9.1 Quantization and Dequantization 401.9.1.1 The General Quantization Scheme 411.9.1.2 Dequantization 421.9.1.3 Measuring Error 421.9.2 Quantifying Signal and Image Distortion More Generally 431.10 Infinite-Dimensional Inner Product Spaces 451.10.1 Example: An Infinite-Dimensional Space 451.10.2 Orthogonal Bases in Inner Product Spaces 461.10.3 The Cauchy–Schwarz Inequality and Orthogonal Expansions 481.10.4 The Basic Waveforms and Fourier Series 491.10.4.1 Complex Exponential Fourier Series 491.10.4.2 Sines and Cosines 521.10.4.3 Fourier Series on Rectangles 531.10.5 Hilbert Spaces and L2(a, b ) 531.10.5.1 Expanding the Space of Functions 531.10.5.2 Complications 541.10.5.3 A Converse to Parseval 551.11 Matlab Project 55Exercises 602 The Discrete Fourier Transform 712.1 Overview 712.2 The Time Domain and Frequency Domain 712.3 A Motivational Example 732.3.1 A Simple Signal 732.3.2 Decomposition into BasicWaveforms 742.3.3 Energy at Each Frequency 742.3.4 Graphing the Results 752.3.5 Removing Noise 772.4 The One-Dimensional DFT 782.4.1 Definition of the DFT 782.4.2 Sample Signal and DFT Pairs 802.4.2.1 An Aliasing Example 802.4.2.2 Square Pulses 812.4.2.3 Noise 822.4.3 Suggestions on Plotting DFTs 842.4.4 An Audio Example 842.5 Properties of the DFT 852.5.1 Matrix Formulation and Linearity 852.5.1.1 The DFT as a Matrix 852.5.1.2 The Inverse DFT as a Matrix 872.5.2 Symmetries for Real Signals 882.6 The Fast Fourier transform 902.6.1 DFT Operation Count 902.6.2 The FFT 912.6.3 The Operation Count 922.7 The Two-Dimensional DFT 932.7.1 Interpretation and Examples of the 2-D DFT 962.8 Matlab Project 972.8.1 Audio Explorations 972.8.2 Images 99Exercises 1013 The Discrete Cosine Transform 1053.1 Motivation for the DCT—Compression 1053.2 Other Compression Issues 1063.3 Initial Examples—Thresholding 1073.3.1 Compression Example 1: A Smooth Function 1083.3.2 Compression Example 2: A Discontinuity 1093.3.3 Compression Example 3 1103.3.4 Observations 1123.4 The Discrete Cosine Transform 1123.4.1 DFT Compression Drawbacks 1123.4.2 The Discrete Cosine Transform 1133.4.2.1 Symmetric Reflection 1133.4.2.2 DFT of the Extension 1133.4.2.3 DCT/IDCT Derivation 1143.4.2.4 Definition of the DCT and IDCT 1153.4.3 Matrix Formulation of the DCT 1163.5 Properties of the DCT 1163.5.1 BasicWaveforms for the DCT 1163.5.2 The Frequency Domain for the DCT 1173.5.3 DCT and Compression Examples 1173.6 The Two-Dimensional DCT 1203.7 Block Transforms 1213.8 JPEG Compression 1233.8.1 Overall Outline 1233.8.2 DCT and Quantization Details 1243.8.3 The JPEG Dog 1283.8.4 Sequential versus Progressive Encoding 1283.9 Matlab Project 131Exercises 1344 Convolution and Filtering 1394.1 Overview 1394.2 One-Dimensional Convolution 1394.2.1 Example: Low-Pass Filtering and Noise Removal 1394.2.2 Convolution 1424.2.2.1 Convolution Definition 1424.2.2.2 Convolution Properties 1434.3 Convolution Theorem and Filtering 1464.3.1 The Convolution Theorem 1464.3.2 Filtering and Frequency Response 1474.3.2.1 Filtering Effect on BasicWaveforms 1474.3.3 Filter Design 1504.4 2D Convolution—Filtering Images 1524.4.1 Two-Dimensional Filtering and Frequency Response 1524.4.2 Applications of 2D Convolution and Filtering 1534.4.2.1 Noise Removal and Blurring 1534.4.2.2 Edge Detection 1544.5 Infinite and Bi-Infinite Signal Models 1564.5.1 L2(ℕ) and L2(ℤ) 1584.5.1.1 The Inner Product Space L2(ℕ) 1584.5.1.2 The Inner Product Space L2(ℤ) 1594.5.2 Fourier Analysis in L2(ℤ) and L2(ℕ) 1604.5.2.1 The Discrete Time Fourier Transform in L2(ℤ) 1604.5.2.2 Aliasing and the Nyquist Frequency in L2(ℤ) 1614.5.2.3 The Fourier Transform on L2(ℕ)) 1634.5.3 Convolution and Filtering in L2(ℤ) and L2(ℕ) 1634.5.3.1 The Convolution Theorem 1644.5.4 The z-Transform 1664.5.4.1 Two Points of View 1664.5.4.2 Algebra of z-Transforms; Convolution 1674.5.5 Convolution in ℂN versus L2(ℤ) 1684.5.5.1 Some Notation 1684.5.5.2 Circular Convolution and z-Transforms 1694.5.5.3 Convolution in ℂN from Convolution in L2(ℤ) 1704.5.6 Some Filter Terminology 1714.5.7 The Space L2(ℤ × ℤ) 1724.6 Matlab Project 1724.6.1 Basic Convolution and Filtering 1724.6.2 Audio Signals and Noise Removal 1744.6.3 Filtering Images 175Exercises 1765 Windowing and Localization 1855.1 Overview: Nonlocality of the DFT 1855.2 Localization via Windowing 1875.2.1 Windowing 1875.2.2 Analysis of Windowing 1885.2.2.1 Step 1: Relation of X and Y 1895.2.2.2 Step 2: Effect of Index Shift 1905.2.2.3 Step 3: N-Point versus M-Point DFT 1915.2.3 Spectrograms 1925.2.4 Other Types of Windows 1965.3 Matlab Project 1985.3.1 Windows 1985.3.2 Spectrograms 199Exercises 2006 Frames 2056.1 Introduction 2056.2 Packet Loss 2056.3 Frames—Using more Dot Products 2086.4 Analysis and Synthesis with Frames 2116.4.1 Analysis and Synthesis 2116.4.2 Dual Frame and Perfect Reconstruction 2136.4.3 Partial Reconstruction 2146.4.4 Other Dual Frames 2156.4.5 Numerical Concerns 2166.4.5.1 Condition Number of a Matrix 2176.5 Initial Examples of Frames 2186.5.1 Circular Frames in ℝ2 2186.5.2 Extended DFT Frames and Harmonic Frames 2196.5.3 Canonical Tight Frame 2216.5.4 Frames for Images 2226.6 More on the Frame Operator 2226.7 Group-Based Frames 2256.7.1 Unitary Matrix Groups and Frames 2256.7.2 Initial Examples of Group Frames 2286.7.2.1 Platonic Frames 2286.7.2.2 Symmetric Group Frames 2306.7.2.3 Harmonic Frames 2326.7.3 Gabor Frames 2326.7.3.1 Flipped Gabor Frame 2376.8 Frame Applications 2376.8.1 Packet Loss 2396.8.2 Redundancy and other duals 2406.8.3 Spectrogram 2416.9 Matlab Project 2426.9.1 Frames and Frame Operator 2436.9.2 Analysis and Synthesis 2456.9.3 Condition Number 2466.9.4 Packet Loss 2466.9.5 Gabor Frames 246Exercises 2477 Filter Banks 2517.1 Overview 2517.2 The Haar Filter Bank 2527.2.1 The One-Stage Two-Channel Filter Bank 2527.2.2 Inverting the One-stage Transform 2567.2.3 Summary of Filter Bank Operation 2577.3 The General One-stage Two-channel Filter Bank 2607.3.1 Formulation for Arbitrary FIR Filters 2607.3.2 Perfect Reconstruction 2617.3.3 Orthogonal Filter Banks 2637.4 Multistage Filter Banks 2647.5 Filter Banks for Finite Length Signals 2677.5.1 Extension Strategy 2677.5.2 Analysis of Periodic Extension 2697.5.2.1 Adapting the Analysis Transform to Finite Length 2707.5.2.2 Adapting the Synthesis Transform to Finite Length 2727.5.2.3 Other Extensions 2747.5.3 Matrix Formulation of the Periodic Case 2747.5.4 Multistage Transforms 2757.5.4.1 Iterating the One-stage Transform 2757.5.4.2 Matrix Formulation of Multistage Transform 2777.5.4.3 Reconstruction from Approximation Coefficients 2787.5.5 Matlab Implementation of Discrete Wavelet Transforms 2817.6 The 2D Discrete Wavelet Transform and JPEG 2000 2817.6.1 Two-dimensional Transforms 2817.6.2 Multistage Transforms for Two-dimensional Images 2827.6.3 Approximations and Details for Images 2867.6.4 JPEG 2000 2887.7 Filter Design 2897.7.1 Filter Banks in the z-domain 2907.7.1.1 Downsampling and Upsampling in the z-domain 2907.7.1.2 Filtering in the Frequency Domain 2907.7.2 Perfect Reconstruction in the z-frequency Domain 2907.7.3 Filter Design I: Synthesis from Analysis 2927.7.4 Filter Design II: Product Filters 2957.7.5 Filter Design III: More Product Filters 2977.7.6 Orthogonal Filter Banks 2997.7.6.1 Design Equations for an Orthogonal Bank 2997.7.6.2 The Product Filter in the Orthogonal Case 3007.7.6.3 Restrictions on P(z); Spectral Factorization 3017.7.6.4 Daubechies Filters 3017.8 Matlab Project 3037.8.1 Basics 3037.8.2 Audio Signals 3047.8.3 Images 3057.9 Alternate Matlab Project 3067.9.1 Basics 3067.9.2 Audio Signals 3077.9.3 Images 307Exercises 3098 Lifting for Filter Banks and Wavelets 3198.1 Overview 3198.2 Lifting for the Haar Filter Bank 3198.2.1 The Polyphase Analysis 3208.2.2 Inverting the Polyphase Haar Transform 3218.2.3 Lifting Decomposition for the Haar Transform 3228.2.4 Inverting the Lifted Haar Transform 3248.3 The Lifting Theorem 3248.3.1 A Few Facts About Laurent Polynomials 3258.3.1.1 The Width of a Laurent Polynomial 3258.3.1.2 The Division Algorithm 3258.3.2 The Lifting Theorem 3268.4 Polyphase Analysis for Filter Banks 3308.4.1 The Polyphase Decomposition and Convolution 3318.4.2 The Polyphase Analysis Matrix 3338.4.3 Inverting the Transform 3348.4.4 Orthogonal Filters 3388.5 Lifting 3398.5.1 Relation Between the Polyphase Matrices 3398.5.2 Factoring the Le Gall 5/3 Polyphase Matrix 3418.5.3 Factoring the Haar Polyphase Matrix 3438.5.4 Efficiency 3458.5.5 Lifting to Design Transforms 3468.6 Matlab Project 3518.6.1 Laurent Polynomials 3518.6.2 Lifting for CDF(2,2) 3548.6.3 Lifting the D4 Filter Bank 356Exercises 3569 Wavelets 3619.1 Overview 3619.1.1 Chapter Outline 3619.1.2 Continuous from Discrete 3619.2 The Haar Basis 3639.2.1 Haar Functions as a Basis for L2(0, 1) 3649.2.1.1 Haar Function Definition and Graphs 3649.2.1.2 Orthogonality 3679.2.1.3 Completeness in L2(0, 1) 3689.2.2 Haar Functions as an Orthonormal Basis for L2(ℝ) 3729.2.3 Projections and Approximations 3749.3 Haar Wavelets Versus the Haar Filter Bank 3769.3.1 Single-stage Case 3779.3.1.1 Functions from Sequences 3779.3.1.2 Filter Bank Analysis/Synthesis 3779.3.1.3 Haar Expansion and Filter Bank Parallels 3789.3.2 Multistage Haar Filter Bank and Multiresolution 3809.3.2.1 Some Subspaces and Bases 3819.3.2.2 Multiresolution and Orthogonal Decomposition 3819.3.2.3 Direct Sums 3829.3.2.4 Connection to Multistage Haar Filter Banks 3849.4 Orthogonal Wavelets 3869.4.1 Essential Ingredients 3869.4.2 Constructing a Multiresolution Analysis: The Dilation Equation 3879.4.3 Connection to Orthogonal Filters 3899.4.4 Computing the Scaling Function 3909.4.5 Scaling Function Existence and Properties 3949.4.5.1 Fixed Point Iteration and the Cascade Algorithm 3949.4.5.2 Existence of the Scaling Function 3959.4.5.3 The Support of the Scaling Function 3979.4.5.4 Back to Multiresolution 3999.4.6 Wavelets 3999.4.7 Wavelets and the Multiresolution Analysis 4049.4.7.1 Final Remarks on Orthogonal Wavelets 4069.5 Biorthogonal Wavelets 4079.5.1 Biorthogonal Scaling Functions 4089.5.2 Biorthogonal Wavelets 4099.5.3 Decomposition of L2(ℝ) 4099.6 Matlab Project 4119.6.1 Orthogonal Wavelets 4119.6.2 Biorthogonal Wavelets 414Exercises 414Bibliography 421Appendix: Solutions to Exercises 423Index 439