WARP: Wavelets with adaptive recursive partitioning for multi-dimensional data

Meng Li, Li Ma

Abstract

Traditional Discrete Wavelet Transforms (DWT) are constrained by fixed, symmetric basis functions that often fail to capture the local, asymmetric features prevalent in multi-dimensional data like biomedical images. We present WARP (WAvelets with Recursive Partitioning), a probabilistic framework that introduces data-adaptivity into DWT by modeling the transform itself as a latent Bayesian structure. By leveraging recursive dyadic partitioning (RDP), WARP adapts to the geometric structure of the data while maintaining $O(n)$ linear computational complexity. Our evaluation on natural and biomedical datasets demonstrates that WARP outperforms traditional wavelets and deep learning models, particularly in high-noise environments.

Introduction

Discrete Wavelet Transforms are fundamental to signal processing due to their speed and multi-resolution capabilities. However, their "stiffness"—the reliance on fixed, symmetric basis functions—limits their efficiency when representing asymmetric features. For instance, in Optical Coherence Tomography (OCT) scans, horizontal tissue layers exhibit sharp vertical contrasts. A standard DWT requires a large number of coefficients to represent such features accurately. While deep learning approaches like CNNs can learn these patterns, they often require massive training datasets and significant computational resources. WARP bridges this gap by providing a generative probabilistic model that is as fast as a wavelet transform but as adaptive as a learning-based approach.

Methodology: Adaptive Recursive Partitioning

The core innovation of the WARP framework is treating the wavelet transform as an unknown to be inferred.

The WARP framework uses Recursive Dyadic Partitioning (RDP) to adaptively permute grid points, allowing the wavelet transform to follow the data's geometric structure.
  1. Recursive Dyadic Partitioning (RDP): WARP uses RDP to "warp" or permute the grid points of an image. This allows a 1D wavelet transform to effectively "twist and turn" through multi-dimensional space, following the actual contours and layers of the data.
  2. Bayesian Hierarchical Modeling: A prior distribution is placed on the space of all possible recursive partitions. The model "learns" the optimal partitioning strategy based on the observed data.
  3. Node-Autonomy and Efficiency: By utilizing the Haar wavelet basis, the framework exploits "node-autonomy," where inference for one part of the partition tree is independent of distant branches. This enables an exact Recursive Message Passing algorithm with $O(n)$ complexity, making it suitable for high-resolution 3D datasets.

Experimental Evaluation

WARP was evaluated across several benchmarks:

  • ImageNet & BSD68: 100 random natural images and the Berkeley segmentation dataset were used for general denoising performance.
  • Retinal OCT Dataset: 3D biomedical volumes were used to test the preservation of delicate, asymmetric tissue layers.
  • Comparison Models: WARP was compared against state-of-the-art methods including TI-2D-Haar, Shape-Adaptive Wavelets (SHAH), and deep learning models like DnCNN.

Results and Discussion

WARP demonstrated significant improvements in both reconstruction quality and computational efficiency.

Comparison of Mean Squared Error (MSE) across different noise levels (sigma). WARP consistently achieves lower error compared to state-of-the-art methods.

Superior Denoising and Energy Concentration

As shown in the performance metrics, WARP consistently achieves lower Mean Squared Error (MSE) than competing methods across various noise levels. This is attributed to its superior "energy concentration"—it captures the signal's essence using significantly fewer coefficients than standard DWT.

Performance in High-Noise Scenarios

Notably, WARP outperformed the DnCNN neural network in high-noise settings ($\sigma = 0.6$). While CNNs excel with sufficient data and low noise, WARP’s probabilistic structure provides more robust regularization when the signal-to-noise ratio is low.

Computational Speed

WARP is the fastest adaptive method tested. A $512 \times 512$ image is processed in approximately 7 seconds, compared to 77 seconds for SHAH and over 2,000 seconds for dictionary learning (BPFA).

Conclusion

The WARP framework successfully addresses the rigidity of traditional wavelets by incorporating adaptive recursive partitioning. By modeling the transform itself, WARP achieves high energy concentration and superior denoising performance with linear scalability. While currently reliant on the Haar basis—which can introduce blocky artifacts—future work aims to extend this framework to smoother wavelet families and explore its applications in high-efficiency data compression.

Summary updated

Abstract

Effective identification of asymmetric and local features in images and other data observed on multi-dimensional grids plays a critical role in a wide range of applications including biomedical and natural image processing. Moreover, the ever increasing amount of image data, in terms of both the resolution per image and the number of images processed per application, requires algorithms and methods for such applications to be computationally efficient. We develop a new probabilistic framework for multi-dimensional data to overcome these challenges through incorporating data adaptivity into discrete wavelet transforms, thereby allowing them to adapt to the geometric structure of the data while maintaining the linear computational scalability. By exploiting a connection between the local directionality of wavelet transforms and recursive dyadic partitioning on the grid points of the observation, we obtain the desired adaptivity through adding to the traditional Bayesian wavelet regression framework an additional layer of Bayesian modeling on the space of recursive partitions over the grid points. We derive the corresponding inference recipe in the form of a recursive representation of the exact posterior, and develop a class of efficient recursive message passing algorithms for achieving exact Bayesian inference with a computational complexity linear in the resolution and sample size of the images. 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 2D and 3D image reconstruction using real images from the ImageNet database. We also apply the framework to analyze a data set from retinal optical coherence tomography.
BibTeX
@article{li2021warp,
  author = {Meng Li and Li Ma},
  title = {{WARP: Wavelets with adaptive recursive partitioning for multi-dimensional data}},
  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  year = {2021},
  doi = {10.1109/tpami.2021.3110403},
}

Loading related content...

Figure