<title>Construction of shift-orthogonal wavelets using splines</title>

Michaël Unser, P. Thévenaz, Akram AldroubiProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 1996 · DOI

TL;DR

This paper introduces a novel class of "shift-orthogonal" wavelets constructed using splines. These wavelets offer a compelling trade-off: they maintain orthogonality within each scale (crucial for quantization in compression) while relaxing orthogonality across scales. This design, particularly with faster-decaying synthesis filters, promises improved performance for image coding and data compression compared to existing orthogonal wavelet transforms.

What Problem Does This Paper Address?

The field of wavelet theory has explored various types of wavelet bases, primarily orthogonal, semi-orthogonal, and biorthogonal. Orthogonal wavelets (like Daubechies or Battle-Lemarié) offer desirable properties for signal processing, especially for quantization in compression, as the quantization error in the transformed domain directly relates to the error in the reconstructed image. However, these often come with limitations like asymmetry or slow filter decay, leading to artifacts. Semi-orthogonal wavelets offer more flexibility in shape and localization but sacrifice shift-orthogonality. Biorthogonal wavelets allow for shorter, linear-phase filters but introduce asymmetry.

This paper addresses the desire for wavelets that combine the benefits of orthogonality (specifically, shift-orthogonality for quantization) with desirable characteristics like symmetry and faster filter decay for better compression performance. They aim to achieve this by constructing wavelets that are orthogonal to their translates within the same scale but not necessarily across different scales.

Methods

The core of the paper lies in constructing "shift-orthogonal" wavelet bases using spline functions. They leverage two multiresolution analyses of $L^2$, one for analysis (using splines of degree $n_1$, typically 0 or 1) and another for synthesis (using splines of higher degree $n_2$).

Key methodological aspects include:

  • Spline Multiresolution Analysis: They define spline spaces $V^n$ based on Schoenberg's causal B-splines.
  • Shift-Orthogonality: The crucial property is that the wavelets are orthogonal to their translates within the same scale, i.e., $(\psi(x/2), \psi(x/2 - k)) = \delta[k]$.
  • Biorthogonality Constraint: They define dual analysis and synthesis wavelets ($\tilde{\psi}$ and $\psi$) that satisfy a biorthogonality constraint: $(\tilde{\psi}(x/2), \phi^n_2(x/2 - k)) = \delta[k]$.
  • Oblique Projection: Instead of orthogonal projection, they use an oblique projection from the synthesis space $V^n_2$ onto the analysis space $V^n_1$ (or vice-versa), perpendicular to the other space. This allows for flexibility in choosing analysis and synthesis spaces.
  • Filter Design: The construction leads to specific filter coefficients for the analysis and synthesis filters, which are derived from spline properties and cross-correlation sequences. The paper emphasizes that these filters decay exponentially fast.

Datasets

Not discussed in the paper. The paper focuses on the theoretical construction and properties of the wavelet bases, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • "Shift-Orthogonality" as a Sweet Spot: The paper introduces a new category of wavelets that are orthogonal within a scale but not across scales. This is a clever compromise, retaining the benefits of shift-orthogonality for quantization while allowing for more flexible filter design.
  • Splines as Building Blocks: Using splines, particularly higher-order splines for synthesis, allows for wavelets with excellent approximation properties. This means that for smooth signals, finer scale coefficients will be close to zero, which is highly beneficial for compression techniques like zero-tree coding.
  • Faster Filter Decay: A significant advantage highlighted is the much faster decay of the synthesis wavelet filters compared to their orthogonal Battle-Lemarié counterparts. This is crucial for reducing ringing artifacts in image coding and for better localization in time-frequency.
  • Symmetry/Anti-symmetry: The construction naturally leads to symmetric or anti-symmetric basis functions, which simplifies boundary handling in signal processing (e.g., using mirror extensions).
  • Angle Between Spaces as a Measure of Orthogonality Loss: The paper quantifies the loss of orthogonality across scales by calculating the "angle" between the spline spaces. This provides a theoretical basis for understanding the trade-offs.

Key Results

  • Construction of Shift-Orthogonal Wavelets: The paper successfully derives the mathematical framework and explicit formulas for constructing these new shift-orthogonal spline wavelets.
  • Symmetric/Anti-symmetric Properties: The resulting wavelets are either symmetric or anti-symmetric, a desirable property for signal processing.
  • Faster Filter Decay: The synthesis filters exhibit significantly faster decay than comparable orthogonal filters, which is a key advantage for image compression.
  • Good Approximation Power: The use of higher-order splines for synthesis ensures good approximation properties, leading to sparse representations for smooth signals.
  • Theoretical Justification: The paper provides a rigorous theoretical foundation for the construction, including conditions for well-definedness and stability.

Limitations and Future Work

  • Limited Empirical Evaluation: While the paper discusses potential benefits for image coding and data compression, it does not present extensive empirical results or comparisons with state-of-the-art compression algorithms.
  • Focus on Splines: The construction is specific to spline bases. Future work could explore applying similar principles to other types of basis functions.
  • Trade-off in Orthogonality: The relaxation of orthogonality across scales, while beneficial for filter design, might still introduce some residual correlations that could impact certain applications. The paper acknowledges this by noting that the "residual correlations across scales should not be too significant."
  • Further Optimization: While the filters decay faster, further optimization for specific compression tasks could be explored.

The authors suggest that the faster decay and near-orthogonality properties make these wavelets promising for image coding and data compression, implying that future work would likely involve detailed performance evaluations in these areas.

Summary updated

Abstract

We present examples of a new type of wavelet basis functions that are orthogonal across shifts, but not across scales. The analysis functions are low order splines while the synthesis functions are polynomial splines of higher degree n<SUB>2</SUB>. The approximation power of these representations is essentially as good as that of the corresponding Battle- Lemarie orthogonal wavelet transform, with the difference that the present wavelet synthesis filters have a much faster decay. This last property, together with the fact that these transformation s are almost orthogonal, may be useful for image coding and data compression.
BibTeX
@inproceedings{unser1996lt,
  author = {Michaël Unser and P. Thévenaz and Akram Aldroubi},
  title = {{\&lt;title\&gt;Construction of shift-orthogonal wavelets using splines\&lt;/title\&gt;}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {1996},
  doi = {10.1117/12.255257},
}
Figure