Wavelets: Software and Applications

This Ph.D. thesis was presented to obtain the degree of Doctor in de Toegepaste Wetenschappen [Doctor in Engineering] from the Faculty of Applied Sciences of the Katholieke Universiteit Leuven. It was defended in the Arenbergkasteel in Heverlee on Wednesday April 28, 1999.

Members of the Jury

Prof. Dr. ir. R. Govaerts, chairman
Prof. Dr. ir. D. Roose, supervisor
Prof. Dr. A. Bultheel, supervisor
Prof. Dr. ir. B. De Moor
Prof. Dr. ir. R. Cools
Prof. Dr. J.-P. Antoine (Université catholique de Louvain)

English Abstract

During the last decade, the wavelet transform has proven to be a valuable tool in many application fields. In this thesis we focus on two applications: image processing and compression to create low-dimensional models for dynamical systems.

We worked out the details of integer wavelet transforms, based on the lifting scheme, for a class of biorthogonal wavelets (Cohen-Daubechies-Feauveau). Based on this we designed and implemented a software library called WAILI (Wavelets with Integer Lifting) that provides wavelet transforms and wavelet-based image processing operations on two-dimensional images. Later we added support for very large images and block-based processing.

We created a new kind of second-generation wavelets on a rectangular grid, based on a red-black blocking scheme. These Red-Black wavelets are less anisotropic than tensor product wavelets.

We reduced the complexity of the Proper Orthogonal Decomposition (POD) by biorthogonal wavelet packet compression and evaluated the resulting Approximate POD by analyzing a large-scale dynamical system, described by partial differential equations.

Dutch Abstract

Tijdens de voorbije jaren heeft de wavelet-transformatie haar belang bewezen als een hulpmiddel in allerlei toepassingsgebieden. In deze thesis concentreerden we ons op twee toepassingsgebieden: beeldverwerking en compressie voor het creëren van laagdimensionale modellen voor dynamische systemen.

We werkten de details uit van gehele-getallen-wavelet-transformaties, op basis van het liftingschema, voor een klasse van biorthogonale wavelets (Cohen-Daubechies-Feauveau). Dit gebruikten we om de programmabibliotheek PIEFPAK (WAILI -- Wavelets with Integer Lifting) te ontwikkelen. Deze bibliotheek implementeert wavelet-transformaties en wavelet-gebaseerde beeldverwerkingsoperaties op tweedimensionale beelden. Later voegden we ondersteuning toe voor zeer grote beelden en blokgebaseerde verwerking.

We construeerden een nieuw soort tweede-generatie-wavelets op een rechthoekig rooster, gebaseerd op een rood-zwart blokschema. Deze rood-zwart-wavelets zijn minder anisotroop dan tensorproduct-wavelets.

We reduceerden de complexiteit van de orthogonale eigenontbinding (POD) m.b.v. biorthogonale wavelet-packet-compressie en evalueerden de resulterende benaderende POD door de analyse van een grootschalig dynamisc systeem, beschreven door partiële differentiaalvergelijkingen.

Preface
Nederlandse Samenvatting
Contents
Notations and Abbreviations
List of Figures
List of Tables
Chapter 1: Introduction
- Overview of Wavelet Research
- Overview of the Thesis
- Situation of the Research
Chapter 2: Wavelets
- What are Wavelets?
- Why wavelets?
- Wavelets and Multi-Resolution Analysis
  - Multi-Resolution Analysis
  - Wavelet Functions
  - The Fast Wavelet Transform (FWT)
  - Orthogonal Wavelets
  - Biorthogonal Wavelets
  - The Wavelet Decomposition Tree
  - Higher Dimensions
- The Wavelet Transform and Translation Invariance
- The Redundant Wavelet Transform
- Wavelet Packets
Chapter 3: The Lifting Scheme
- Introduction
- Predict and Update
  - The Inverse Transform
  - Example: Linear Prediction
  - Flexibility
- Unifying the Two Paradigms
  - The Filter Bank Algorithm
  - Polyphase Representations
  - Primal and Dual Lifting
  - Decomposition into Lifting Steps
  - Advantages of the Lifting Scheme
- The Integer Wavelet Transform
  - Integer Transforms
  - Rational Lifting Coefficients
  - Normalization
- Boundary Treatment
  - Classical Extension Methods
  - Signal Extension with Lifting
- Conclusions
Chapter 4: Wavelet-Based Image Processing
- Digital Images
  - Discretization
  - Quantization
  - Color images
  - Generalization
  - L^*a^*b^*
- Wavelet Denoising
  - Thresholding
  - Threshold selection
  - Integer Minimization Problem
- Image Scaling
- Crop and Merge
- Image Compression
  - Why Compression?
  - Compression Techniques
  - Features of Image Compression using Wavelets
  - Zerotree Encoding
- Conclusions
Chapter 5: Design of the Software Library WAILI
- Design Criteria
- WAILI: Wavelets with Integer Lifting
  - The Lifting Scheme
  - Cohen-Daubechies-Feauveau Biorthogonal Wavelets
  - Image Size Constraints
  - Images and Wavelet Transforms
- Wavelet-Based Operations
  - Crop and Merge on Wavelet-Transformed Images
  - Scaling of Images
  - Noise Reduction
- Implementation Issues
  - In-Place Transform
  - The Two-Dimensional Wavelet Transform: Mallat Ordering
  - Transform Order
  - Normalization of the Wavelet Coefficients
- Summary of the Functionality of WAILI
- Evaluation of the Compression Potential
  - Description of the Compression Method
  - Measure of the Compression Rate
  - Measure of the Image Quality
  - Results
- Comparison with Other Wavelet Software
Chapter 6: Large-Scale Image Processing
- Introduction
- Very Large Images and Tiling
  - Tiling
  - Block Management
  - Implementation in WAILI
- Image Processing on Tiled Images
  - Block-Based Denoising
  - Image Compression
  - Crop and Merge
  - A GIS Application
- Transform Results
- Conclusions
Chapter 7: The Red-Black Wavelet Transform
- Introduction
- The Red-Black Wavelet Transform
  - A Two-Step Method
  - Borders
  - Reordering
  - Integer Wavelet Transform
  - Basis Functions
  - Other Members of the Family
- Properties of the Red-Black Wavelet Transform
- The Redundant Wavelet Transform
- Comparison with the CDF (2, 2) Tensor Product Wavelets
  - Test case 1
  - Test case 2
- Conclusions
Chapter 8: Experiments with a Wavelet-Based APOD
- Introduction
- The Proper Orthogonal Decomposition
- The Approximate Proper Orthogonal Decomposition
  - Theory of Operation
  - Decorrelating Transforms
  - Decomposition into the Basis of Approximate Eigenmodes
- Wavelet Transforms
- Results
  - Wavelets
  - The Dynamical System
  - Snapshots
  - ``Strange'' Snapshots
  - Eigenvalue Distribution
  - Eigenmodes
  - Reconstruction of the Snapshots
  - Coefficients of the Snapshots in the APOD Basis
  - Timings
- Conclusions
Chapter 9: Conclusions and Suggestions for Future Research
- Wavelet Transforms
- A Software Library for Wavelet-Based Image Processing
- Approximate POD using Wavelet Packets
- Suggestions for Future Research
Bibliography
Appendix A: Lifting Decompositions
Appendix B: A Simple Image Compression Example using WAILI
Index

Download

You can download gzipped PostScript files of the thesis text:

The whole text (195 pages, 2.1 MB)
Separate chapters:
- Coverpage, Abstract, and Preface (8 pages, 22 KB)
- Nederlandse Samenvatting (32 pages, 62 KB)
- Table of Contents, Notations and Abbreviations, Lists of Figures and Tables (12 pages, 17 KB)
- Chapter 1: Introduction (4 pages, 12 KB)
- Chapter 2: Wavelets (14 pages, 42 KB)
- Chapter 3: The Lifting Scheme (20 pages, 56 KB)
- Chapter 4: Wavelet-Based Image Processing (14 pages, 369 KB)
- Chapter 5: Design of the Software Library WAILI (16 pages, 42 KB)
- Chapter 6: Large-Scale Image Processing (10 pages, 33 KB)
- Chapter 7: The Red-Black Wavelet Transform (14 pages, 1.4 MB)
- Chapter 8: Experiments with a Wavelet-Based APOD (26 pages, 129 KB)
- Chapter 9: Conclusions and Suggestions for Future Research (4 pages, 19 KB)
- Bibliography (6 pages, 14 KB)
- Appendix A: Lifting Decompositions (8 pages, 20 KB)
- Appendix B: A Simple Image Compression Example using WAILI (4 pages, 8 KB)
- Index (3 pages, 10 KB)