Multiresolution analysis

Not to be confused with Multiple-scale analysis.

A multiresolution analysis (MRA) or multiscale approximation (MSA) is the design method of most of the practically relevant discrete wavelet transforms (DWT) and the justification for the algorithm of the fast wavelet transform (FWT). It was introduced in this context in 1988/89 by Stephane Mallat and Yves Meyer and has predecessors in the microlocal analysis in the theory of differential equations (the ironing method) and the pyramid methods of image processing as introduced in 1981/83 by Peter J. Burt, Edward H. Adelson and James L. Crowley.

Definition

A multiresolution analysis of the Lebesgue space ${\displaystyle L^{2}(\mathbb {R} )}$ consists of a sequence of nested subspaces

${\displaystyle \{0\}\subset \dots \subset V_{1}\subset V_{0}\subset V_{-1}\subset \dots \subset V_{-n}\subset V_{-(n+1)}\subset \dots \subset L^{2}(\mathbb {R} )}$

that satisfies certain self-similarity relations in time-space and scale-frequency, as well as completeness and regularity relations.

• Self-similarity in time demands that each subspace V_k is invariant under shifts by integer multiples of 2^k. That is, for each ${\displaystyle f\in V_{k},\;m\in \mathbb {Z} }$ the function g defined as ${\displaystyle g(x)=f(x-m2^{k})}$ also contained in ${\displaystyle V_{k}}$.
• Self-similarity in scale demands that all subspaces ${\displaystyle V_{k}\subset V_{l},\;k>l,}$ are time-scaled versions of each other, with scaling respectively dilation factor 2^k-l. I.e., for each ${\displaystyle f\in V_{k}}$ there is a ${\displaystyle g\in V_{l}}$ with ${\displaystyle \forall x\in \mathbb {R} :\;g(x)=f(2^{k-l}x)}$.
• In the sequence of subspaces, for k>l the space resolution 2^l of the l-th subspace is higher than the resolution 2^k of the k-th subspace.
• Regularity demands that the model subspace V₀ be generated as the linear hull (algebraically or even topologically closed) of the integer shifts of one or a finite number of generating functions ${\displaystyle \phi }$ or ${\displaystyle \phi _{1},\dots ,\phi _{r}}$. Those integer shifts should at least form a frame for the subspace ${\displaystyle V_{0}\subset L^{2}(\mathbb {R} )}$, which imposes certain conditions on the decay at infinity. The generating functions are also known as scaling functions or father wavelets. In most cases one demands of those functions to be piecewise continuous with compact support.
• Completeness demands that those nested subspaces fill the whole space, i.e., their union should be dense in ${\displaystyle L^{2}(\mathbb {R} )}$, and that they are not too redundant, i.e., their intersection should only contain the zero element.

Algorithms

This section explores the core algorithms that form the foundation of multiresolution analysis, enabling its wide range of applications.

Subdivision Schemes

Subdivision schemes are iterative algorithms used to generate smooth curves and surfaces from an initial set of control points. These schemes progressively refine the control polygon or mesh to produce increasingly detailed representations.^[1][2]

Key characteristics of subdivision schemes include:

• Masks: Define the rules for generating new points at each refinement step.
• Flexibility: Enable local modifications at varying resolution levels, making them ideal for multiresolution editing.

A notable example is the Lane-Riesenfeld algorithm, which constructs smooth B-spline curves by iteratively averaging control points. Subdivision schemes are widely applied in geometric modeling, particularly for creating and editing shapes with varying levels of detail.

Discrete Wavelet Transform (DWT)

The Discrete Wavelet Transform (DWT) is a pivotal algorithm in multiresolution analysis, offering a multiscale representation of signals through decomposition into different frequency sub-bands.

Key features of DWT:

• Decomposition: The signal is passed through high-pass and low-pass filters, yielding detail coefficients (high frequencies) and approximation coefficients (low frequencies).
• Reconstruction: The original signal is reconstructed using inverse filters.
• Efficiency: With a computational complexity of ${\displaystyle O(N)}$, DWT is well-suited for large-scale data processing tasks like image compression and feature extraction.

Pyramidal Algorithms

Pyramidal algorithms leverage a hierarchical structure, akin to a pyramid, where each level represents the signal at a progressively coarser resolution.^[1]

Core steps include:

• Decomposition: Downsampling and smoothing the signal at each level to create a hierarchy of representations.
• Reconstruction: Upsampling and combining information from different levels to restore the original signal.

These algorithms are computationally efficient and extensively used in image processing, computer vision, and pattern recognition.

Fast Decomposition and Reconstruction Algorithms

The Mallat algorithm is a fast, hierarchical method for wavelet decomposition and reconstruction. It processes data at multiple scales, enabling efficient computation of wavelet coefficients and their reconstruction.^[2]

Applications

Image Fusion in Remote Sensing

MRA is instrumental in merging images from sensors with varying resolutions and spectral bands ^[3] . For instance, a high-resolution panchromatic image can be fused with a low-resolution multispectral image, producing a single output with enhanced spatial and spectral resolution. Techniques like the "à trous" wavelet algorithm and Laplacian pyramids preserve spatial connectivity and minimize artifacts.

Multiresolution Editing in Geometric Modeling

MRA enhances geometric modeling by enabling efficient representation and manipulation of complex shapes^[4]:

• Hierarchical B-splines: Allow local and global modifications, simplifying both coarse adjustments and detailed refinements.
• Flexible design: Provides a multiresolution framework for iterative editing, streamlining the creative process in computer-aided design (CAD).

Shape Compression Using Semi-Regular Remeshing

MRA contributes to efficient 3D model compression through semi-regular remeshing^[4]:

• Simplification: Reduces unnecessary connectivity and parameterization data.
• Parameterization: Maps the input mesh onto base triangular domains, resulting in a compact representation.

This approach facilitates the efficient storage, transmission, and rendering of 3D models in applications like gaming, virtual reality, and scientific visualization.

Emerging Fields

• Machine Learning: MRA aids in multiscale feature extraction for tasks like image recognition and natural language processing.
• Quantum Wavelet Transforms: Leveraging quantum computing principles, MRA is being explored for high-dimensional datasets.
• Seismic Analysis: MRA enhances the interpretation of seismic data, identifying subsurface structures with high precision.

Practical Examples

Case Study: Image Compression

JPEG 2000, a widely used image compression standard, relies on MRA through the DWT. By retaining critical wavelet coefficients, it achieves high compression ratios with minimal loss of image quality.

Additional Case Studies

• Climate Data Analysis: Detects patterns in multiscale climate datasets.
• Financial Market Trends: Analyzes stock market data for trend detection and anomaly identification.
• Medical Imaging: Enhances feature detection and clarity in MRI and CT scans.

Important conclusions

In the case of one continuous (or at least with bounded variation) compactly supported scaling function with orthogonal shifts, one may make a number of deductions. The proof of existence of this class of functions is due to Ingrid Daubechies.

Assuming the scaling function has compact support, then ${\displaystyle V_{0}\subset V_{-1}}$ implies that there is a finite sequence of coefficients ${\displaystyle a_{k}=2\langle \phi (x),\phi (2x-k)\rangle }$ for ${\displaystyle |k|\leq N}$, and ${\displaystyle a_{k}=0}$ for ${\displaystyle |k|>N}$, such that

${\displaystyle \phi (x)=\sum _{k=-N}^{N}a_{k}\phi (2x-k).}$

Defining another function, known as mother wavelet or just the wavelet

${\displaystyle \psi (x):=\sum _{k=-N}^{N}(-1)^{k}a_{1-k}\phi (2x-k),}$

one can show that the space ${\displaystyle W_{0}\subset V_{-1}}$, which is defined as the (closed) linear hull of the mother wavelet's integer shifts, is the orthogonal complement to ${\displaystyle V_{0}}$ inside ${\displaystyle V_{-1}}$.^[5] Or put differently, ${\displaystyle V_{-1}}$ is the orthogonal sum (denoted by ${\displaystyle \oplus }$) of ${\displaystyle W_{0}}$ and ${\displaystyle V_{0}}$. By self-similarity, there are scaled versions ${\displaystyle W_{k}}$ of ${\displaystyle W_{0}}$ and by completeness one has

${\displaystyle L^{2}(\mathbb {R} )={\mbox{closure of }}\bigoplus _{k\in \mathbb {Z} }W_{k},}$

thus the set

${\displaystyle \{\psi _{k,n}(x)={\sqrt {2}}^{-k}\psi (2^{-k}x-n):\;k,n\in \mathbb {Z} \}}$

is a countable complete orthonormal wavelet basis in ${\displaystyle L^{2}(\mathbb {R} )}$.

See also

• Multigrid method
• Multiscale modeling
• Scale space
• Time–frequency analysis
• Wavelet

References

1. Albert Cohen (2003). Albert Cohen (ed.). Chapter 2 - Multiresolution approximation. Vol. 32. Elsevier. pp. 43–153.
2. Bruce W. Suter (1998). Bruce W. Suter (ed.). Chapter 5 - Wavelet Signal Processing. Wavelet Analysis and Its Applications. Vol. 8. Academic Press. pp. 167–190.
3. Bruno Aiazzi, Stefano Baronti, Massimo Selva (2008). Tania Stathaki (ed.). 2 - Image fusion through multiresolution oversampled decompositions. Oxford: Academic Press. pp. 27–66. ISBN 978-0-12-372529-5.
4. Georges-Pierre Bonneau, Gershon Elber, Stefanie Hahmann, Basile Sauvage (2008). Leila De Floriani, Michela Spagnuolo (ed.). Multiresolution Analysis. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 83–114. ISBN 978-3-540-33265-7.
5. Mallat, S.G. "A Wavelet Tour of Signal Processing". www.di.ens.fr. Retrieved 2019-12-30.

• Chui, Charles K. (1992). An Introduction to Wavelets. San Diego: Academic Press. ISBN 0-585-47090-1.
• Akansu, A.N.; Haddad, R.A. (1992). Multiresolution signal decomposition: transforms, subbands, and wavelets. Academic Press. ISBN 978-0-12-047141-6.
• Crowley, J. L., (1982). A Representations for Visual Information, Doctoral Thesis, Carnegie-Mellon University, 1982.
• Burrus, C.S.; Gopinath, R.A.; Guo, H. (1997). Introduction to Wavelets and Wavelet Transforms: A Primer. Prentice-Hall. ISBN 0-13-489600-9.
• Mallat, S.G. (1999). A Wavelet Tour of Signal Processing. Academic Press. ISBN 0-12-466606-X.