Learning Asymmetric and Local Features in Multi-Dimensional Data through Wavelets with Recursive Partitioning

Meng Li, Li Ma

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.

Introduction

Traditional Discrete Wavelet Transforms (DWT) have long been a cornerstone of signal processing due to their exceptional computational efficiency, scaling linearly ($O(n)$) with the number of pixels. However, these transforms typically rely on fixed, symmetric basis functions. This rigidity becomes a significant drawback when dealing with real-world data, such as medical imaging or natural scenes, where features are often highly asymmetric and locally varied. For instance, in Retinal Optical Coherence Tomography (OCT), the critical diagnostic information lies in thin, horizontal tissue layers that a standard symmetric wavelet struggles to represent efficiently, often resulting in blurring or a lack of sparsity.

While deep learning models like Convolutional Neural Networks (CNNs) offer high adaptivity, they often function as "black boxes" requiring massive datasets for pre-training and substantial computational resources. This research introduces WARP (WAvelets with Recursive Partitioning), a Bayesian framework designed to bridge the gap between the speed of wavelets and the adaptivity of modern machine learning.

The WARP Framework

The fundamental innovation of WARP is treating the data's permutation as a latent variable to be learned. Instead of applying a fixed transform to a static grid, the algorithm identifies an optimal "path" through the multi-dimensional data that best captures its underlying geometry.

The WARP framework: Recursive Dyadic Partitioning (RDP) induces a permutation of the data, allowing a 1D wavelet transform to capture complex multi-dimensional structures.

As shown in the figure above, the process utilizes Recursive Dyadic Partitioning (RDP) to split the index space into smaller rectangles, creating a tree structure. Any specific path through this tree induces a unique ordering (permutation) of the pixels. By applying a simple 1D wavelet transform to this custom-ordered sequence, the model effectively implements a highly complex, adaptive multi-dimensional transform on the original image. To manage the vast space of possible partitions, the authors employ a Bayesian hierarchical model with a "spike-and-slab" prior on wavelet coefficients to enforce sparsity.

Computational Efficiency and Inference

One of the most significant breakthroughs of this work is the derivation of an exact message passing algorithm. By leveraging the "node-autonomy" property of Haar wavelets—where coefficients depend only on data within their specific partition—the authors avoided the need for slow Markov Chain Monte Carlo (MCMC) simulations. This allows the entire Bayesian inference process to be completed in $O(n)$ time, matching the complexity of a standard DWT. In practical terms, this means the model can process an image with 17 million pixels in approximately two minutes on a standard laptop.

Experimental Results and Energy Concentration

The performance of WARP was evaluated against diverse datasets, including ImageNet, standard benchmarks like BSD68, and clinical retinal OCT images. A key metric for success in this domain is "energy concentration"—the ability to represent the majority of an image's information with as few coefficients as possible.

As illustrated in the comparative analysis, WARP achieves a much higher percentage of coefficient savings than traditional 1D-DWT. This high sparsity translates directly to better denoising performance. In head-to-head tests, WARP consistently outperformed state-of-the-art methods such as SHAH and Wedgelets. Notably, when compared to the deep learning-based denoiser DnCNN, WARP showed superior performance in high-noise scenarios and comparable results in low-noise settings, all without the need for a GPU or extensive pre-training.

Clinical and Practical Utility

In the context of medical imaging, WARP demonstrated a unique ability to preserve sharp boundaries between retinal layers, which is vital for accurate diagnosis. Unlike other methods that tend to blur these fine horizontal features, WARP's adaptive partitioning aligns itself with the tissue structure.

While the current implementation primarily utilizes the Haar basis—which can occasionally produce blocky artifacts—the authors mitigate this through "cycle spinning" (averaging over shifts). Future work aims to extend this recursive framework to smoother wavelet bases like Daubechies and explore applications in high-ratio data compression and structural learning.

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},
}
Figure