Super-resolution using preconditioned conjugate gradient method

Changjiang Yang, Ramani Duraiswami, Larry S. DavisProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2002 · DOI

TL;DR

This paper introduces a faster iterative method for image super-resolution by improving the conjugate gradient algorithm with a novel Wiener filter-based preconditioner. This new approach speeds up convergence and avoids the tricky manual tuning required by previous methods, leading to better image reconstruction quality.

What Problem Does This Paper Address?

Image super-resolution (SR) aims to create a high-resolution (HR) image from a sequence of low-resolution (LR) images. This is crucial for applications where high-quality imagery is essential but sensors are limited by cost or hardware constraints. While single-image SR is notoriously ill-posed, using multiple frames from a video sequence offers a way to reconstruct a sharper image by leveraging the slightly different perspectives and over-sampled information. However, existing iterative SR algorithms, particularly those based on the conjugate gradient (CG) method, can suffer from slow convergence, especially when dealing with ill-conditioned systems common in SR. Preconditioning is a standard technique to accelerate CG, but previous methods, like the inverse filter-based preconditioner, required a difficult-to-determine tolerance parameter, leading to potential artifacts.

Methods

The core of this work is an iterative super-resolution algorithm based on the preconditioned conjugate gradient (PCG) method. The authors propose a new Wiener filter-based preconditioner to address the limitations of existing methods.

Here's a breakdown:

  • Forward Imaging Model: The paper models the imaging process as a sequence of transformations: geometric warping (Fk), blurring (Ck), downsampling (D), and additive noise (nk). This is represented by the equation fk = DCkFk x + nk, where fk is an LR frame and x is the unknown HR image. Stacking these for multiple frames leads to f = Hx + n.
  • Optimization Problem: The goal is to solve the ill-posed system Hx = f. The maximum likelihood estimator leads to minimizing ||Hx - f||^2, which is equivalent to solving the normal equations HT Hx = HTf.
  • Conjugate Gradient (CG): CG is a standard iterative method for solving large linear systems. However, for ill-conditioned systems like those in SR, its convergence can be slow.
  • Preconditioning: To speed up CG, the system is transformed into H̄Hx = H̄f, where H̄ = C⁻¹HC⁻¹, x = Cx, and f = C⁻¹f. The goal is to find a preconditioner M (where M = CᵀC) such that H̄ is well-conditioned.
  • Novel Wiener Filter Preconditioner: Instead of the inverse filter approach that requires a tolerance τ to separate signal and noise subspaces (which is hard to determine and can cause artifacts), this paper proposes a Wiener filter-based preconditioner. The Wiener filter is designed to minimize the mean squared error. Its spectral domain definition is given by: H_wiener = K*(u, v) / (|K(u,v)|² + Sw(u, v)/Sf(u, v)) where K is the system transfer function, Sf is the power spectrum of the ideal image, and Sw is the power spectrum of the noise. This approach automatically handles the eigenvalue clustering without needing an explicit tolerance.

  • Implementation: The PCG algorithm involves two main matrix-vector multiplications: HT Hp (forward and backward imaging) and Mr (preconditioning). The HT Hp operation is implemented iteratively using project and backproject functions for each frame. The Mr operation uses the pre-computed Wiener filter. The circulant-block structure of the preconditioner allows efficient implementation using Fast Fourier Transforms (FFTs).

Datasets

The paper uses simulated image sequences for evaluation. Specifically, they take a single 256x256 image, apply subpixel shifts, blur it with a Gaussian PSF, downsample it, and add Gaussian noise to create LR frames. They evaluate on a "text image sequence" and a "cameraman sequence" under different noise levels (0.002 and 0.02). No new benchmarks are introduced.

Key Insights and Ideas

  • Wiener Filter for Preconditioning: The most significant contribution is the application of a Wiener filter as a preconditioner for CG in SR. This elegantly bypasses the need to manually determine a tolerance parameter, which was a major drawback of previous inverse filter-based preconditioners.
  • Automatic Tolerance Handling: The Wiener filter inherently balances signal and noise based on estimated power spectra, effectively clustering eigenvalues without explicit thresholding. This makes the method more robust and easier to implement.
  • Improved Convergence and Stability: The PCG method, especially with the Wiener filter preconditioner, demonstrates significantly faster convergence and improved stability compared to standard CG and even the inverse filter PCG, particularly in the presence of noise and larger blurs.
  • FFT Efficiency: The circulant-block structure of the preconditioner allows for efficient computation using FFTs, making the overall algorithm practical for large-scale problems.

Key Results

  • Qualitative Improvement: The reconstructed images using the proposed Wiener filter-based PCG method show visibly better detail and sharpness compared to bilinear interpolation, standard CG, and the inverse filter PCG, especially under noisy conditions.
  • Quantitative Improvement: Convergence plots (Figure 3 and 6) show that the PCG methods converge much faster than the standard CG method. The Wiener filter PCG often converges slightly faster or more stably than the inverse filter PCG.
  • Robustness: The paper notes that the CG methods (both standard and preconditioned) are relatively insensitive to noise levels, performing well even at higher noise levels (0.02).
  • Handling Blurring: Experiments with larger blurs indicate that standard CG can fail to converge to the true image, while the PCG methods (including the proposed one) perform much better.

Limitations and Future Work

  • Parameter Estimation: While the Wiener filter avoids the explicit tolerance τ, it still relies on estimating the power spectrum of the ideal image (Sf) and the noise (Sw). The paper mentions Sw can be estimated from degraded images and Sf can be estimated from |G(u,v)|² - σ²w, implying these estimations might introduce their own challenges or approximations.
  • Motion Estimation: The paper assumes that geometric warping operators (Fk) are obtained through motion estimation algorithms. The accuracy of the SR reconstruction is implicitly dependent on the quality of this motion estimation.
  • Future Work: The paper doesn't explicitly detail future work, but the success of the Wiener filter-based preconditioner suggests further exploration of adaptive or data-driven preconditioning techniques for SR and other ill-posed inverse problems. Investigating the impact of different noise models and more complex blurring kernels could also be future directions.

Summary updated

Abstract

In this paper we present a fast iterative image superresolution algorithm using preconditioned conjugate gradient method. To avoid explicitly computing the tolerance in the inverse filter based preconditioner scheme,1 a new Wiener filter based preconditioner for the conjugate gradient method is proposed to speed up the convergence. The circulant-block structure of the preconditioner allows efficient implementation using Fast Fourier Transform. Effectiveness of the preconditioner is demonstrated by superresolution results for simulated image sequences.
BibTeX
@inproceedings{yang2002super,
  author = {Changjiang Yang and Ramani Duraiswami and Larry S. Davis},
  title = {{Super-resolution using preconditioned conjugate gradient method}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2002},
  doi = {10.1117/12.477201},
}
Figure