A Novel Progressive Image Scanning and Reconstruction Scheme Based on Compressed Sensing and Linear Prediction

Giulio Coluccia, Enrico Magli

TL;DR

This paper proposes a computationally efficient way to apply Compressed Sensing (CS) to line-by-line image acquisition (like flatbed scanners or satellite imagers). By iteratively predicting rows from their neighbors and only reconstructing the "prediction error," the authors achieve high-quality images with far fewer samples and lower complexity than traditional multidimensional CS.

What Problem Does This Paper Address?

Compressed Sensing is a powerful tool that allows us to reconstruct signals from far fewer samples than the Nyquist rate requires, provided the signal is "sparse." However, applying CS to high-resolution 2D images faces a massive hurdle: computational complexity.

Standard reconstruction algorithms scale cubically ($O(N^3)$) with the number of samples. For a modern image with millions of pixels, reconstructing the whole thing at once is mathematically "intractable"—it would take far too much time and memory.

Engineers often solve this by scanning line-by-line and reconstructing each row independently. While fast, this approach is wasteful because it ignores the "vertical" correlation between adjacent rows. This paper tackles the gap: how do we exploit the 2D structure of an image to improve quality without hitting the $O(N^3)$ complexity wall?

Methods

The authors introduce a two-part framework:

  1. Progressive Acquisition (Algorithm 1): The image is acquired row-by-row. For each row, a small number of random linear projections (Gaussian measurements) are taken. Crucially, a different random sensing matrix is used for each row to ensure diversity in the data.
  2. Iterative Reconstruction (Algorithm 2): This is the core innovation. Instead of just reconstructing rows in isolation, the algorithm uses an iterative "predict-and-correct" loop:
  3. Initialization: Perform a basic row-by-row reconstruction.
  4. Prediction: Use a linear predictor (the authors tested three versions) to estimate the current row based on the rows above and below it from the previous iteration.
  5. Error Reconstruction: Instead of reconstructing the whole row, the algorithm calculates the "prediction error" in the measurement domain. Because adjacent rows are highly correlated, this error is much sparser than the original signal.
  6. Update: Reconstruct this sparse error and add it back to the prediction to refine the estimate.

The authors found that a weighted average of six neighboring pixels (Predictor "P3") provided the best performance.

Datasets

The algorithm was evaluated on three types of data:

  • Standard Benchmarks: The classic 512x512 "Lena" grayscale image.
  • Synthetic Graphics: Four images representing typical flatbed scanner content: a QPSK constellation, a trellis diagram, a block diagram, and sample text.
  • Remote Sensing Data: A spectral band (the 600th band) from the AIRS hyperspectral sensor ("granule 9"), representing a real-world satellite imaging scenario.

Key Insights and Ideas

  • Sparsity is the "Secret Sauce": CS works better when a signal is sparser. By predicting a row from its neighbors, the remaining "error" is significantly sparser than the raw pixel data. This makes the CS reconstruction much more accurate for the same number of measurements.
  • Complexity Decoupling: By processing rows but linking them through an iterative predictor, the authors achieve the benefits of 2D correlation while keeping the complexity tied to the size of a single row ($N_{COL}$) rather than the whole image ($N_{ROW} \times N_{COL}$).
  • Kronecker Integration: The paper shows that this method can be further improved by using "Kronecker Compressed Sensing" (KCS) for initialization, which uses 2D transform properties to get a better starting point for the iterations.

Key Results

  • Significant Quality Gains: On the "Lena" image with $M=64$ measurements per row, the iterative approach improved the Mean Squared Error (MSE) by 10.2 dB compared to separate row reconstruction.
  • Efficiency: For the AIRS satellite data, the algorithm reached convergence in just 4 to 10 iterations.
  • Superiority over OMP: The proposed method outperformed Orthogonal Matching Pursuit (OMP), a common low-complexity CS algorithm. At $M=64$, the proposed algorithm showed an 8 dB gain over OMP for the same total amount of data.
  • Visual Sparsity: For very sparse images (like simple black-and-white graphics), the algorithm could reduce MSE by an entire order of magnitude.

Limitations and Future Work

  • Convergence Speed: While the algorithm is efficient, convergence can be slow when the number of measurements ($M$) is very low.
  • Predictor Sensitivity: The performance relies heavily on the linear predictor. While the weighted 6-neighbor average worked well, more sophisticated or adaptive predictors (perhaps using machine learning) could potentially yield even better results.
  • Hardware Implementation: The paper focuses on the mathematical framework; the authors note that the next step would be implementing this in low-power hardware for actual remote sensing or portable scanning devices.

Summary updated

Abstract

Compressed sensing (CS) is an innovative technique allowing to represent signals through a small number of their linear projections. In this paper we address the application of CS to the scenario of progressive acquisition of 2D visual signals in a line-by-line fashion. This is an important setting which encompasses diverse systems such as flatbed scanners and remote sensing imagers. The use of CS in such setting raises the problem of reconstructing a very high number of samples, as are contained in an image, from their linear projections. Conventional reconstruction algorithms, whose complexity is cubic in the number of samples, are computationally intractable. In this paper we develop an iterative reconstruction algorithm that reconstructs an image by iteratively estimating a row, and correlating adjacent rows by means of linear prediction. We develop suitable predictors and test the proposed algorithm in the context of flatbed scanners and remote sensing imaging systems. We show that this approach can significantly improve the results of separate reconstruction of each row, providing very good reconstruction quality with reasonable complexity.
BibTeX
@inproceedings{coluccia2012novel,
  author = {Giulio Coluccia and Enrico Magli},
  title = {{A Novel Progressive Image Scanning and Reconstruction Scheme Based on Compressed Sensing and Linear Prediction}},
  booktitle = {ICME},
  year = {2012},
  url = {https://openreview.net/forum?id=jtmUkcDuqd},
}

Loading related content...

Figure