Abstract

We address the potential performance of the successive overrelaxation technique (SOR) in image deconvolution, focusing our attention on the restoration of astronomical images distorted by atmospheric turbulence. SOR is the classical Gauss-Seidel iteration, supplemented with relaxation. As indicated by earlier work, the convergence properties of SOR, and its ultimate performance in the deconvolution of blurred and noisy images, can be made competitive to other iterative techniques, including conjugate gradients, by a proper choice of the relaxation parameter. The question of how to choose the relaxation parameter, however, remained open, and in the practical work one had to rely on experimentation. In this paper, using constructive (rather than exact) arguments, we suggest a simple strategy for choosing the relaxation parameter and for updating its value in consecutive iterations to optimize the performance of the SOR algorithm (and its positivity-constrained version, +SOR) at finite iteration counts. We suggest an extension of the algorithm to the notoriously difficult problem of “blind” deconvolution, where both the true object and the point-spread function have to be recovered from the blurred image. We report the results of numerical inversions with artificial and real data, where the algorithm is compared with techniques based on conjugate gradients. In all of our experiments +SOR provides the highest quality results. In addition +SOR is found to be able to detect moderately small changes in the true object between separate data frames: an important quality for multi-frame blind deconvolution where stationarity of the object is a necesessity.

© 2011 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. V. N. Strakhov and S. V. Vorontsov, “Digital image deblurring with SOR,” Inverse Probl. 24, 025024 (2008) (Paper I).
    [CrossRef]
  2. K. Sauer and C. Bouman, “A local update strategy for iterative reconstruction from projections,” IEEE Trans. Signal Process. 41, 534–548 (1993).
    [CrossRef]
  3. J. A. Fessler, “Penalized weighted least-squares image reconstruction for positron emission tomography,” IEEE Trans. Med. Imaging 13, 290–300 (1994).
    [CrossRef] [PubMed]
  4. A. Björck, Numerical Methods for Least Squares Problems (SIAM, 1996).
    [CrossRef]
  5. C. W. Cryer, “The solution of a quadratic programming problem using systematic overrelaxation,” SIAM J. Control 9, 385–392 (1971).
    [CrossRef]
  6. R. G. Lane and R. H. T. Bates, “Automatic multidimensional deconvolution,” J. Opt. Soc. Am. 4, 180–188 (1987).
    [CrossRef]
  7. R. T. H. Bates, B. K. Quek, and C. R. Parker, “Some implications of zero sheets for blind deconvolution and phase retrieval,” J. Opt. Soc. Am. 7, 468–479 (1990).
    [CrossRef]
  8. R. C. Puetter, T. R. Gosnell, and A. Yahil, “Digital image reconstruction: deblurring and denoising,” Ann. Rev. Astron. Astrophys. 43, 139–194 (2005).
    [CrossRef]
  9. D. Calvetti, G. Landi, L. Reichel, and F. Sgallari, “Non-negativity and iterative methods for ill-posed problems,” Inverse Probl. 20, 1747–1758 (2004).
    [CrossRef]
  10. P. C. Hansen, “Analysis of discrete ill-posed problems by means of the L-curve,” SIAM Rev. 34, 561–580 (1992).
    [CrossRef]
  11. C. R. Vogel, Computational Methods for Inverse Problems (SIAM, 2002).
    [CrossRef]
  12. C. L. Matson, K. Borelli, S. M. Jefferies, E. K. Hege, C. C. Beckner, and M. Lloyd-Hart, “A fast and optimal multiframe blind deconvolution algorithm for high-resolution, ground-based imaging of space objects,” Appl. Opt. 48, A75–A92 (2009).
    [CrossRef]

2009 (1)

2008 (1)

V. N. Strakhov and S. V. Vorontsov, “Digital image deblurring with SOR,” Inverse Probl. 24, 025024 (2008) (Paper I).
[CrossRef]

2005 (1)

R. C. Puetter, T. R. Gosnell, and A. Yahil, “Digital image reconstruction: deblurring and denoising,” Ann. Rev. Astron. Astrophys. 43, 139–194 (2005).
[CrossRef]

2004 (1)

D. Calvetti, G. Landi, L. Reichel, and F. Sgallari, “Non-negativity and iterative methods for ill-posed problems,” Inverse Probl. 20, 1747–1758 (2004).
[CrossRef]

1994 (1)

J. A. Fessler, “Penalized weighted least-squares image reconstruction for positron emission tomography,” IEEE Trans. Med. Imaging 13, 290–300 (1994).
[CrossRef] [PubMed]

1993 (1)

K. Sauer and C. Bouman, “A local update strategy for iterative reconstruction from projections,” IEEE Trans. Signal Process. 41, 534–548 (1993).
[CrossRef]

1992 (1)

P. C. Hansen, “Analysis of discrete ill-posed problems by means of the L-curve,” SIAM Rev. 34, 561–580 (1992).
[CrossRef]

1990 (1)

R. T. H. Bates, B. K. Quek, and C. R. Parker, “Some implications of zero sheets for blind deconvolution and phase retrieval,” J. Opt. Soc. Am. 7, 468–479 (1990).
[CrossRef]

1987 (1)

R. G. Lane and R. H. T. Bates, “Automatic multidimensional deconvolution,” J. Opt. Soc. Am. 4, 180–188 (1987).
[CrossRef]

1971 (1)

C. W. Cryer, “The solution of a quadratic programming problem using systematic overrelaxation,” SIAM J. Control 9, 385–392 (1971).
[CrossRef]

Bates, R. H. T.

R. G. Lane and R. H. T. Bates, “Automatic multidimensional deconvolution,” J. Opt. Soc. Am. 4, 180–188 (1987).
[CrossRef]

Bates, R. T. H.

R. T. H. Bates, B. K. Quek, and C. R. Parker, “Some implications of zero sheets for blind deconvolution and phase retrieval,” J. Opt. Soc. Am. 7, 468–479 (1990).
[CrossRef]

Beckner, C. C.

Björck, A.

A. Björck, Numerical Methods for Least Squares Problems (SIAM, 1996).
[CrossRef]

Borelli, K.

Bouman, C.

K. Sauer and C. Bouman, “A local update strategy for iterative reconstruction from projections,” IEEE Trans. Signal Process. 41, 534–548 (1993).
[CrossRef]

Calvetti, D.

D. Calvetti, G. Landi, L. Reichel, and F. Sgallari, “Non-negativity and iterative methods for ill-posed problems,” Inverse Probl. 20, 1747–1758 (2004).
[CrossRef]

Cryer, C. W.

C. W. Cryer, “The solution of a quadratic programming problem using systematic overrelaxation,” SIAM J. Control 9, 385–392 (1971).
[CrossRef]

Fessler, J. A.

J. A. Fessler, “Penalized weighted least-squares image reconstruction for positron emission tomography,” IEEE Trans. Med. Imaging 13, 290–300 (1994).
[CrossRef] [PubMed]

Gosnell, T. R.

R. C. Puetter, T. R. Gosnell, and A. Yahil, “Digital image reconstruction: deblurring and denoising,” Ann. Rev. Astron. Astrophys. 43, 139–194 (2005).
[CrossRef]

Hansen, P. C.

P. C. Hansen, “Analysis of discrete ill-posed problems by means of the L-curve,” SIAM Rev. 34, 561–580 (1992).
[CrossRef]

Hege, E. K.

Jefferies, S. M.

Landi, G.

D. Calvetti, G. Landi, L. Reichel, and F. Sgallari, “Non-negativity and iterative methods for ill-posed problems,” Inverse Probl. 20, 1747–1758 (2004).
[CrossRef]

Lane, R. G.

R. G. Lane and R. H. T. Bates, “Automatic multidimensional deconvolution,” J. Opt. Soc. Am. 4, 180–188 (1987).
[CrossRef]

Lloyd-Hart, M.

Matson, C. L.

Parker, C. R.

R. T. H. Bates, B. K. Quek, and C. R. Parker, “Some implications of zero sheets for blind deconvolution and phase retrieval,” J. Opt. Soc. Am. 7, 468–479 (1990).
[CrossRef]

Puetter, R. C.

R. C. Puetter, T. R. Gosnell, and A. Yahil, “Digital image reconstruction: deblurring and denoising,” Ann. Rev. Astron. Astrophys. 43, 139–194 (2005).
[CrossRef]

Quek, B. K.

R. T. H. Bates, B. K. Quek, and C. R. Parker, “Some implications of zero sheets for blind deconvolution and phase retrieval,” J. Opt. Soc. Am. 7, 468–479 (1990).
[CrossRef]

Reichel, L.

D. Calvetti, G. Landi, L. Reichel, and F. Sgallari, “Non-negativity and iterative methods for ill-posed problems,” Inverse Probl. 20, 1747–1758 (2004).
[CrossRef]

Sauer, K.

K. Sauer and C. Bouman, “A local update strategy for iterative reconstruction from projections,” IEEE Trans. Signal Process. 41, 534–548 (1993).
[CrossRef]

Sgallari, F.

D. Calvetti, G. Landi, L. Reichel, and F. Sgallari, “Non-negativity and iterative methods for ill-posed problems,” Inverse Probl. 20, 1747–1758 (2004).
[CrossRef]

Strakhov, V. N.

V. N. Strakhov and S. V. Vorontsov, “Digital image deblurring with SOR,” Inverse Probl. 24, 025024 (2008) (Paper I).
[CrossRef]

Vogel, C. R.

C. R. Vogel, Computational Methods for Inverse Problems (SIAM, 2002).
[CrossRef]

Vorontsov, S. V.

V. N. Strakhov and S. V. Vorontsov, “Digital image deblurring with SOR,” Inverse Probl. 24, 025024 (2008) (Paper I).
[CrossRef]

Yahil, A.

R. C. Puetter, T. R. Gosnell, and A. Yahil, “Digital image reconstruction: deblurring and denoising,” Ann. Rev. Astron. Astrophys. 43, 139–194 (2005).
[CrossRef]

Ann. Rev. Astron. Astrophys. (1)

R. C. Puetter, T. R. Gosnell, and A. Yahil, “Digital image reconstruction: deblurring and denoising,” Ann. Rev. Astron. Astrophys. 43, 139–194 (2005).
[CrossRef]

Appl. Opt. (1)

IEEE Trans. Med. Imaging (1)

J. A. Fessler, “Penalized weighted least-squares image reconstruction for positron emission tomography,” IEEE Trans. Med. Imaging 13, 290–300 (1994).
[CrossRef] [PubMed]

IEEE Trans. Signal Process. (1)

K. Sauer and C. Bouman, “A local update strategy for iterative reconstruction from projections,” IEEE Trans. Signal Process. 41, 534–548 (1993).
[CrossRef]

Inverse Probl. (2)

V. N. Strakhov and S. V. Vorontsov, “Digital image deblurring with SOR,” Inverse Probl. 24, 025024 (2008) (Paper I).
[CrossRef]

D. Calvetti, G. Landi, L. Reichel, and F. Sgallari, “Non-negativity and iterative methods for ill-posed problems,” Inverse Probl. 20, 1747–1758 (2004).
[CrossRef]

J. Opt. Soc. Am. (2)

R. G. Lane and R. H. T. Bates, “Automatic multidimensional deconvolution,” J. Opt. Soc. Am. 4, 180–188 (1987).
[CrossRef]

R. T. H. Bates, B. K. Quek, and C. R. Parker, “Some implications of zero sheets for blind deconvolution and phase retrieval,” J. Opt. Soc. Am. 7, 468–479 (1990).
[CrossRef]

SIAM J. Control (1)

C. W. Cryer, “The solution of a quadratic programming problem using systematic overrelaxation,” SIAM J. Control 9, 385–392 (1971).
[CrossRef]

SIAM Rev. (1)

P. C. Hansen, “Analysis of discrete ill-posed problems by means of the L-curve,” SIAM Rev. 34, 561–580 (1992).
[CrossRef]

Other (2)

C. R. Vogel, Computational Methods for Inverse Problems (SIAM, 2002).
[CrossRef]

A. Björck, Numerical Methods for Least Squares Problems (SIAM, 1996).
[CrossRef]

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (11)

Fig. 1
Fig. 1

The true object (a), blurred image with noise (b), and the minimum-error restoration obtained with adaptive +SOR (c).

Fig. 2
Fig. 2

Restoration errors versus the iteration count k. The thick gray line marked with circles is the result obtained with the adaptive +SOR; figures along the line indicate current value of the relaxation parameter τk . The dashed line shows the result obtained with a conjugate-gradient technique, modified to incorporate the non-negativity constraint (+CG).

Fig. 3
Fig. 3

Modulus of DFT of the approximation residuals r (k) in the adaptive +SOR iterative descent, at k = 0 (a), k=15 (b), and k=30 (c). The gray scale is taken such that the maximum signal (white) saturates at a level which is 1/1000 of its maximum value at k = 0 (panel a).

Fig. 4
Fig. 4

Artificial noise-free blind-deconvolution experiment. First row: the true object (a); PSF of the first frame (b); and the first data frame generated from the convolution of the true object and the PSF (c). Second row: the results of deconvolution obtained with adaptive +SOR in 1000 iterations, in a single-frame experiment (d) and with using two (e) and ten (f) frames of data. Third row: the inferred PSF of the first frame.

Fig. 5
Fig. 5

The artificial noise-free experiment. Relative norm of the approximation residuals in the iterative blind deconvolution with using the adaptive +SOR (solid lines) and with using the PCID algorithm based on conjugate gradients [12] (dashed lines).

Fig. 6
Fig. 6

Blind deconvolution of the Seasat images. First row: the first data frame (a), and the results of deconvolution obtained with adaptive +SOR in a single-frame experiment (b) and with using ten (c) frames of data. Second row: the results obtained with using the PCID algorithm based on conjugate gradients [12].

Fig. 7
Fig. 7

As Fig. 5, but for the blind deconvolution of the Seasat data.

Fig. 8
Fig. 8

As Fig. 6, but for the deconvolution of the HST images. Because of the high dynamic range of the +SOR results, the pixel values were rescaled by taking a cubic root (in all the frames displayed in this figure).

Fig. 9
Fig. 9

As Fig. 5, but for the deconvolution of the HST data.

Fig. 10
Fig. 10

Deconvolution of HST images with adaptive +SOR. Left: relaxation parameter of the descents in object parameter space. Right: number of descents required for the object refresh.

Fig. 11
Fig. 11

Deconvolution of the HST data in separate frames. First row: input data. Second row: object restoration from an individual frame. In the second row, the color scale saturates at 50 percent of maximum pixel value (red) to make the entire satellite visible.

Equations (20)

Equations on this page are rendered with MathJax. Learn more.

A x = f δ , f δ = f + δ f .
M = | | A x f δ | | 2 ;
A T A x = A T f δ ,
A T A = L + D + L T ,
( 1 τ k D + L ) x ( k ) = [ ( 1 τ k 1 ) D L T ] x ( k 1 ) + A T f δ , k = 1 , 2 , ,
r ( k ) = f δ A x ( k ) .
( 1 τ k D + L ) Δ x = A T r ( k 1 ) ,
Δ x = x ( k ) x ( k 1 )
r ( k ) = r ( k 1 ) A Δ x ;
| | r ( k ) | | 2 = | | r ( k 1 ) | | 2 ( 2 τ k 1 ) ( Δ x ) T D Δ x ,
A T r ( k ) = A T r ( k 1 ) A T A Δ x ,
| | A T r ( k ) | | 2 = | | A T r ( k 1 ) | | 2 ( 2 τ k 1 ) ( Δ x ) T D A T A Δ x + ( Δ x ) T ( L L T L T L ) Δ x .
| | A T r ( k ) | | 2 = | | A T r ( k 1 ) | | 2 ( 2 τ k 1 ) d | | A Δ x | | 2 ,
| | A T r ( k ) | | 2 = | | A T r ( k 1 ) | | 2 ( 2 τ k 1 ) d | | r ( k ) r ( k 1 ) | | 2 ,
( 2 τ k 1 ) d = | | A T r ( k 1 ) | | 2 | | r ( k 1 ) | | 2 .
( 2 τ k 1 ) d = ω | ( A T r ( k 1 ) ) | 2 ω | ( r ( k 1 ) ) | 2 = ω | a * ( r ( k 1 ) ) | 2 ω | ( r ( k 1 ) ) | 2 = ω ( l + d + l * ) | ( r ( k 1 ) ) | 2 ω | ( r ( k 1 ) ) | 2 ,
r ( k ) = r ( k 1 ) A ( 1 τ k D + L ) 1 A T r ( k 1 ) .
( r ( k ) ) = W ( τ k ) ( r ( k 1 ) ) ,
W ( τ k ) = 1 l + d + l * d / τ k + l = ( 1 / τ k 1 ) d l * d / τ k + l ,
| ( r ( k ) ) | 2 | ( r ( k 1 ) ) | 2 = | W ( τ k ) | 2 = [ ( 2 / τ k 1 ) d ( l + d + l * ) ] 2 + 4 Im 2 ( l ) [ ( 2 / τ k 1 ) d + ( l + d + l * ) ] 2 + 4 Im 2 ( l ) ,

Metrics