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
Wavelet transforms are a cornerstone of signal processing, valued for their ability to concentrate signal energy into a few large coefficients. However, traditional multidimensional wavelet transforms often use fixed, predetermined bases that fail to account for the local geometric structures, such as edges and textures, inherent in images or 3D volumes. This lack of adaptivity often results in suboptimal denoising and reconstruction performance. To address this, we present WARP (Wavelets with Adaptive Recursive Partitioning), a Bayesian framework that allows wavelet transforms to adapt to the data's underlying geometry while preserving the linear computational complexity that makes wavelets so efficient.
Methodology
The core innovation of WARP is the realization that adaptivity in multidimensional wavelet transforms can be achieved by finding an optimal permutation of the data before applying a standard 1D transform.
Recursive Dyadic Partitioning (RDP)
To make the search for an optimal permutation computationally feasible, the framework utilizes Recursive Dyadic Partitioning (RDP). As illustrated in Figure 1, RDP recursively divides the multidimensional grid into smaller blocks across different levels. This process induces a tree-structured permutation that guides how the data is organized for the wavelet transform.
Bayesian Inference and Message Passing
We place a prior distribution on the space of RDP trees, allowing the model to learn the partition that best concentrates the signal energy from noisy observations. For the Haar wavelet basis, we derived a recursive representation of the Bayesian posterior, leading to an exact message passing algorithm. This approach avoids the need for computationally expensive simulations like Markov Chain Monte Carlo (MCMC), ensuring that inference remains $O(n)$, where $n$ is the number of pixels or voxels.
Experimental Results
The WARP framework was rigorously tested against state-of-the-art methods, including Bayesian Principal Factor Analysis (BPFA) and SHAH, using diverse datasets such as ImageNet, classic benchmarks like "Lena," and 3D simulations.
- Computational Efficiency: WARP demonstrated significant speed advantages. For instance, processing the "Lena" image took only 7.2 seconds, whereas BPFA required 35 minutes. The linear scaling was empirically verified, with the model processing a 17-million-pixel image in approximately two minutes.
- Denoising Performance: WARP consistently matched or exceeded the accuracy of competing methods, particularly in high-noise scenarios. It effectively recovered sharp edges while smoothing noise in homogeneous regions.
- Dimension Agnosticism: The mathematical framework is inherently multidimensional, performing equally well on 2D images and 3D volumetric data without requiring dimension-specific modifications.
Conclusion
WARP introduces a scalable and adaptive Bayesian framework for multidimensional wavelet regression. By leveraging recursive dyadic partitioning and exact message passing, it achieves state-of-the-art denoising performance with linear computational complexity. This makes it highly suitable for large-scale image processing tasks, including medical imaging and natural image reconstruction. Future research will explore the application of this framework to more complex wavelet bases and its potential in high-efficiency data compression.
Summary updated