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.
Introduction
Compressed Sensing (CS) offers a paradigm shift in signal acquisition, allowing for the reconstruction of sparse signals from measurements captured well below the Nyquist rate. However, applying CS to high-resolution 2D images faces a significant hurdle: computational complexity. Standard reconstruction algorithms scale cubically ($O(N^3)$) with the number of samples, making the holistic reconstruction of megapixel-scale images mathematically intractable for many real-time systems.
To address this, many practical systems employ a line-by-line scanning approach, reconstructing each row independently. While computationally efficient, this method fails to exploit the strong vertical correlations present in natural and synthetic images. This paper proposes a novel framework that bridges this gap, utilizing linear prediction to incorporate 2D structural information into a progressive, row-based reconstruction process.
Methodology
The proposed scheme consists of two main components: progressive acquisition and iterative reconstruction.
Progressive Acquisition
The image is acquired row-by-row. For each row, a small number of random linear projections (Gaussian measurements) are captured. To ensure data diversity and improve reconstruction robustness, a different random sensing matrix is employed for each row.
Iterative Reconstruction
The core innovation is a "predict-and-correct" iterative loop. Instead of treating rows as isolated entities, the algorithm leverages inter-row dependencies:
- Initialization: A baseline reconstruction is performed row-by-row.
- Prediction: A linear predictor estimates the current row based on its neighbors (above and below) from the previous iteration. The authors evaluated three predictors (P1, P2, and P3), with P3—a weighted average of six neighboring pixels—demonstrating the highest efficacy.
- Error Reconstruction: The algorithm computes the "prediction error" in the measurement domain. Because adjacent rows are highly correlated, this error signal is significantly sparser than the raw pixel data.
- Refinement: This sparse error is reconstructed and added back to the prediction, iteratively refining the image estimate.
Performance Evaluation
The algorithm was tested across diverse datasets, including the standard "Lena" benchmark, synthetic graphics (Figure 3), and hyperspectral remote sensing data from the AIRS sensor.
Key Results
The iterative approach yielded substantial improvements in image quality. On the "Lena" image with $M=64$ measurements per row, the scheme achieved a 10.2 dB gain in Mean Squared Error (MSE) over independent row reconstruction. Furthermore, it outperformed standard low-complexity algorithms like Orthogonal Matching Pursuit (OMP) by 8 dB at the same measurement rate.
As shown in Figure 1, the algorithm demonstrates rapid convergence, typically within 4 to 10 iterations. The use of Predictor P3 consistently results in the lowest MSE across various measurement densities, validating the benefit of using a more sophisticated local neighborhood for prediction.
Conclusion
By decoupling the complexity of 2D reconstruction into a series of 1D problems linked by linear prediction, this scheme achieves high-quality results with manageable computational costs. The increased sparsity of the prediction error is the primary driver of this performance gain. Future work will explore adaptive predictors and hardware-level implementations for low-power remote sensing devices.
Summary updated