Learning Asymmetric and Local Features in Multi-Dimensional Data Through Wavelets With Recursive Partitioning

Meng Li, Li Ma

TL;DR

The authors introduce WARP (Wavelets with Adaptive Recursive Partitioning), a Bayesian framework that allows wavelet transforms to "twist and turn" to match the geometric structure of 2D and 3D data. By treating the data permutation as a learnable parameter, WARP achieves state-of-the-art denoising accuracy with a lightning-fast linear computational complexity ($O(n)$).

What Problem Does This Paper Address?

Wavelet transforms are a staple of signal processing because of "energy concentration"—the ability to squash a complex signal into just a few large coefficients, making it easy to separate "signal" from "noise." However, traditional wavelet analysis uses a fixed, predetermined transform (like a standard 2D Haar wavelet).

This "one-size-fits-all" approach fails for multidimensional data like images or 3D medical scans. A fixed transform doesn't know where the edges or textures are, so it fails to concentrate energy effectively. While researchers have tried "adaptive" methods before, they are often computationally expensive, specific to a single dimension (e.g., only working for 2D), or lack a solid statistical foundation. The challenge is: how do we make wavelets adapt to the data's local structure without losing the speed that makes wavelets useful in the first place?

Methods

The core innovation is a framework called WARP. The authors realize that "warping" a 1D wavelet transform to fit a multidimensional space is mathematically equivalent to permuting (shuffling) the pixels before applying a standard 1D transform.

  1. Recursive Dyadic Partitioning (RDP): Since the space of all possible permutations is too massive to search, the authors use RDP to define a "smoothness-preserving" subclass of permutations. This creates a tree-like structure that guides how the data is organized.
  2. Bayesian Hierarchical Modeling: They place a prior distribution on these RDP trees. This allows the model to "learn" which permutation best concentrates the signal's energy based on the observed noisy data.
  3. Exact Message Passing: For the Haar wavelet basis, the authors derived a recursive algorithm that allows for exact analytical inference. This means they don't need slow simulations (like MCMC); they can calculate the best reconstruction directly.
  4. Local Block Shrinkage: The model can "prune" the wavelet tree in homogeneous areas (like a flat background), further improving efficiency and reducing noise.

Datasets

The authors evaluated WARP using several benchmarks:

  • ImageNet: 100 randomly selected images to test general performance across various structures.
  • Classic Benchmarks: The famous "Lena" image and the "Phantom" test image.
  • 3D Simulations: Artificial 3D intensity functions ($f_1$ and $f_2$) to test scalability and performance in higher dimensions.
  • Medical Imaging: The abstract mentions retinal optical coherence tomography (OCT) data.

Key Insights and Ideas

  • Permutation is Adaptivity: The "Aha!" moment is that adaptivity doesn't require a new, complex multidimensional basis. You can use simple 1D wavelets if you find the right way to "thread" them through your multidimensional data.
  • Node-Autonomy: The Haar basis is "node-autonomous," meaning the coefficients at one level of the partition don't depend on what's happening in other branches. This property is what unlocks the $O(n)$ speed.
  • Dimension Agnostic: Unlike many image processing tools that are hard-coded for 2D, the WARP math is identical for 2D, 3D, or even higher-dimensional data.
  • Energy Concentration as a Metric: The authors show that WARP needs significantly fewer coefficients to represent 90% of an image's energy compared to standard 2D wavelets, proving that the "warping" actually works.

Key Results

  • Accuracy: WARP consistently outperformed or matched state-of-the-art methods (like BPFA and SHAH) across various noise levels. It was particularly dominant in high-noise scenarios.
  • Speed: The computational gains are massive. For the "Lena" image, WARP took 7.2 seconds, while a competing Bayesian method (BPFA) took 2,100 seconds (35 minutes).
  • Scalability: The authors empirically confirmed that the running time scales linearly with the number of pixels or voxels. It can process a 17-million-pixel image in about 2 minutes.
  • Visual Quality: Qualitatively, WARP was better at recovering sharp edges (like the nose and mouth in the Lena image) while smoothing out noise in flat areas compared to standard 2D Haar transforms.

Limitations and Future Work

  • Haar Basis Reliance: While the framework works for other wavelet bases (like Daubechies D4), it loses the "exact" analytical solution and requires a Sequential Monte Carlo (SMC) approach, which is slightly more complex and slower.
  • Boundary Conditions: The current implementation uses periodic padding, which can sometimes cause artifacts at the very edges of an image.
  • Future Applications: The authors suggest that the posterior distribution of permutations found by WARP could be used for highly efficient data compression, as it identifies the most "information-dense" way to represent a signal.

Summary updated

Abstract

Effective learning of asymmetric and local features in images and other data observed on multi-dimensional grids is a challenging objective critical for a wide range of image processing applications involving biomedical and natural images. It requires methods that are sensitive to local details while fast enough to handle massive numbers of images of ever increasing sizes. We introduce a probabilistic model-based framework that achieves these objectives by incorporating adaptivity into discrete wavelet transforms (DWT) through Bayesian hierarchical modeling, thereby allowing wavelet bases to adapt to the geometric structure of the data while maintaining the high computational scalability of wavelet methods-linear in the sample size (e.g., the resolution of an image). We derive a recursive representation of the Bayesian posterior model which leads to an exact message passing algorithm to complete learning and inference. While our framework is applicable to a range of problems including multi-dimensional signal processing, compression, and structural learning, we illustrate its work and evaluate its performance in the context of image reconstruction using real images from the ImageNet database, two widely used benchmark datasets, and a dataset from retinal optical coherence tomography and compare its performance to state-of-the-art methods based on basis transforms and deep learning.
BibTeX
@article{li2021learning,
  author = {Meng Li and Li Ma},
  title = {{Learning Asymmetric and Local Features in Multi-Dimensional Data Through Wavelets With Recursive Partitioning}},
  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  year = {2021},
  doi = {10.1109/tpami.2021.3110403},
}

Loading related content...

Figure