Compressive Imaging Using Approximate Message Passing and a Markov-Tree Prior.

Subhojit Som, Philip SchniterIEEE TSP 2012 · OpenReview

TL;DR

This paper introduces a novel compressive imaging algorithm that combines the power of Approximate Message Passing (AMP) with a Hidden Markov Tree (HMT) prior for modeling image structure. By employing a "turbo" message-passing schedule, their method achieves state-of-the-art image reconstruction performance with significantly reduced computational complexity compared to existing techniques.

What Problem Does This Paper Address?

Compressive imaging aims to reconstruct a high-resolution image from a limited number of linear measurements. This is an ill-posed problem because the number of measurements ($M$) is much smaller than the number of pixels ($N$). Traditional approaches often rely on the assumption that the image is sparse in some transform domain, like wavelets. However, natural images possess additional structure beyond simple sparsity: persistence across scales (PAS). This means that if a wavelet coefficient at a coarser scale is small, its corresponding coefficients at finer scales are also likely to be small. Exploiting this PAS property can lead to better reconstructions. While previous methods have used models like Hidden Markov Trees (HMTs) to capture PAS, they often suffer from high computational cost (e.g., MCMC) or suboptimal performance. This paper seeks to bridge this gap by developing an efficient and high-performing algorithm that effectively leverages both the HMT structure and the measurement model.

Methods

The core of the proposed method is a "turbo" message-passing schedule that intelligently alternates between two key components:

  1. Exploiting HMT Structure (Soft Support Decoding - SSD): This part uses loopy belief propagation (LBP) on a factor graph representing the HMT. The HMT models the dependencies between wavelet coefficients across different scales, capturing the PAS property.
  2. Exploiting Compressive-Measurement Structure (Soft Support Recovery - SSR): This part leverages the recently proposed Approximate Message Passing (AMP) algorithm. AMP is known for its efficiency and theoretical guarantees in reconstructing sparse signals from linear measurements.

The "turbo" schedule, inspired by turbo decoding, allows these two components to iteratively refine their estimates. Beliefs about the HMT states (which indicate whether coefficients are large or small) are passed from the HMT model to AMP, and AMP's estimates of the coefficients are used to update the HMT model. This iterative exchange helps both parts of the algorithm converge to better solutions. The authors consider two specific coefficient models: Bernoulli-Gaussian (BG) and a two-state Gaussian Mixture (GM). They also detail how to learn the statistical parameters of these models directly from the data using a hierarchical Bayesian approach.

Datasets

The paper evaluates its algorithm on a large image database, specifically mentioning a "Microsoft Research Object Class Recognition database" containing 20 types of images with approximately 30 images of each type. This database was used to measure average performance over a diverse set of natural images. No new benchmarks were introduced; instead, the authors compare their method against existing algorithms on this established dataset.

Key Insights and Ideas

  • Synergy of AMP and HMT: The paper demonstrates that combining the efficient measurement-model inference of AMP with the structural prior modeling of HMTs via a turbo schedule leads to superior performance.
  • "Turbo" Message Passing: The proposed turbo schedule is crucial. It allows for iterative refinement by alternating between exploiting the signal's internal structure (HMT) and the measurement structure (AMP), effectively overcoming limitations of each individual approach.
  • PAS is Key: The results strongly suggest that explicitly modeling the persistence across scales (PAS) using HMTs is critical for achieving state-of-the-art reconstruction quality in compressive imaging, especially for natural images.
  • Complexity Reduction: By integrating AMP, the algorithm achieves significant speedups compared to other HMT-based methods like MCMC, making it more practical for real-world applications.

Key Results

  • State-of-the-Art NMSE: The proposed "Turbo-BG" and "Turbo-GM" algorithms consistently achieved the best Normalized Mean Squared Error (NMSE) across a variety of image types and measurement numbers. For instance, Turbo-GM achieved an average NMSE of -20.74 dB.
  • Significant Complexity Reduction: The Turbo algorithms offered a substantial reduction in computational complexity. For example, they achieved similar or better NMSE than MCMC but were approximately 15 times faster. Compared to VB, they halved the runtime while improving NMSE.
  • Competitive Speed: While not the absolute fastest, the Turbo algorithms were significantly faster than many other high-performing methods (like MCMC and VB) and offered a good balance between speed and accuracy. CoSaMP was faster but yielded worse reconstructions.
  • Robustness to Measurement Count: The Turbo-GM algorithm demonstrated consistently superior NMSE performance across a range of measurement numbers ($M$), outperforming other methods as $M$ increased.

Limitations and Future Work

  • Model Assumptions: The performance relies on the accuracy of the HMT and the chosen coefficient models (BG or GM). If the true image statistics deviate significantly from these models, performance might degrade.
  • Hyperparameter Tuning: While the paper details a method for learning statistical parameters, the choice of hyperpriors can still influence the final results.
  • Future Work: The authors suggest that further exploration of different HMT structures or alternative message-passing schedules could yield even better results. Extending the framework to other signal types or modalities could also be a promising direction.

Summary updated

Abstract

We propose a novel algorithm for compressive imaging that exploits both the sparsity and persistence across scales found in the 2D wavelet transform coefficients of natural images. Like other recent works, we model wavelet structure using a hidden Markov tree (HMT) but, unlike other works, ours is based on loopy belief propagation (LBP). For LBP, we adopt a recently proposed “turbo” message passing schedule that alternates between exploitation of HMT structure and exploitation of compressive-measurement structure. For the latter, we leverage Donoho, Maleki, and Montanari's recently proposed approximate message passing (AMP) algorithm. Experiments with a large image database suggest that, relative to existing schemes, our turbo LBP approach yields state-of-the-art reconstruction performance with substantial reduction in complexity.
BibTeX
@article{som2012compressive,
  author = {Subhojit Som and Philip Schniter},
  title = {{Compressive Imaging Using Approximate Message Passing and a Markov-Tree Prior.}},
  journal = {IEEE Trans. Signal Process.},
  year = {2012},
  url = {https://openreview.net/forum?id=ggbv3UbJ6DLj},
}
Figure