Abstract

A new technique for the acceleration of iterative image restoration algorithms is proposed. The method is based on the principles of vector extrapolation and does not require the minimization of a cost function. The algorithm is derived and its performance illustrated with Richardson–Lucy (R–L) and maximum entropy (ME) deconvolution algorithms and the Gerchberg–Saxton magnitude and phase retrieval algorithms. Considerable reduction in restoration times is achieved with little image distortion or computational overhead per iteration. The speedup achieved is shown to increase with the number of iterations performed and is easily adapted to suit different algorithms. An example R–L restoration achieves an average speedup of 40 times after 250 iterations and an ME method 20 times after only 50 iterations. An expression for estimating the acceleration factor is derived and confirmed experimentally. Comparisons with other acceleration techniques in the literature reveal significant improvements in speed and stability.

© 1997 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. T. J. Cornwell, “Where have we been, where are we now, where are we going?” in The Restoration of HST Images and Spectra II, R. J. Hanisch, R. L. White, eds. (Space Telescope Science Institute, Baltimore, Md., 1994).
  2. W. H. Richardson, “Bayesian-based iterative method of image restoration,” J. Opt. Soc. Am. 62, 55–59 (1972).
    [CrossRef]
  3. L. B. Lucy, “An iterative technique for the rectification of observed images,” Astron. J. 79, 745–754 (1974).
    [CrossRef]
  4. V. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Assoc. 80, 8–37 (1985).
    [CrossRef]
  5. R. L. White, “Image restoration using the damped Richardson—Lucy method,” in The Restoration of HST Images and Spectra II, R. J. Hanisch, R. L. White, eds. (Space Telescope Science Institute, Baltimore, Md., 1994).
  6. E. S. Meinel, “Origins of linear and non-linear recursive restoration algorithms,” J. Opt. Soc. Am. A 3, 787–799 (1986).
    [CrossRef]
  7. H. M. Adorf, R. N. Hook, L. B. Lucy, F. D. Murtagh, “Accelerating the Richardson–Lucy Restoration Algorithm,” in Fourth ESO/ST-ECF Data Analysis Workshop, (European Southern Observatory, Garching, Germany, 1992), pp. 99–103.
  8. T. J. Holmes, Y.-H. Liu, “Acceleration of maximum-likelihood image restoration for fluorescence microscopy and other noncoherent imagery,” J. Opt. Soc. Am. A 8, 893–907 (1991).
    [CrossRef]
  9. L. Kaufman, “Implementing and accelerating the EM algorithm for positron emission tomography,” IEEE Trans. Med. Imaging 6, 37–51 (1987).
    [CrossRef] [PubMed]
  10. D. S. C. Biggs, M. Andrews, “Conjugate gradient acceleration of maximum-likelihood image restoration,” Electron. Lett. 31, 1985–1986 (1995).
    [CrossRef]
  11. R. G. Lane, “Methods for maximum likelihood deconvolution,” J. Opt. Soc. Am. A 13, 1992–1998 (1996).
    [CrossRef]
  12. W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipies in C, 2nd ed. (Cambridge U. Press, Cambridge, 1992).
  13. J. R. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. 21, 2758–2769 (1982).
    [CrossRef]
  14. P. E. Gill, W. Murray, M. H. Wright, Practical Optimization (Academic, New York, 1981).
  15. J. E. Dorband, N. L. Bonavito, T. Busse, “Maximum entropy restoration of blurred and oversaturated Hubble Space Telescope imagery,” Appl. Opt. 32, 5768–5774 (1993).
    [CrossRef] [PubMed]
  16. The image of the binary stellar system R Aquarii was observed with the faint object camera and made available through the Science Assessment and Early Release Observations programme of the Space Telescope Science Institute.

1996 (1)

1995 (1)

D. S. C. Biggs, M. Andrews, “Conjugate gradient acceleration of maximum-likelihood image restoration,” Electron. Lett. 31, 1985–1986 (1995).
[CrossRef]

1993 (1)

1991 (1)

1987 (1)

L. Kaufman, “Implementing and accelerating the EM algorithm for positron emission tomography,” IEEE Trans. Med. Imaging 6, 37–51 (1987).
[CrossRef] [PubMed]

1986 (1)

1985 (1)

V. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Assoc. 80, 8–37 (1985).
[CrossRef]

1982 (1)

1974 (1)

L. B. Lucy, “An iterative technique for the rectification of observed images,” Astron. J. 79, 745–754 (1974).
[CrossRef]

1972 (1)

Adorf, H. M.

H. M. Adorf, R. N. Hook, L. B. Lucy, F. D. Murtagh, “Accelerating the Richardson–Lucy Restoration Algorithm,” in Fourth ESO/ST-ECF Data Analysis Workshop, (European Southern Observatory, Garching, Germany, 1992), pp. 99–103.

Andrews, M.

D. S. C. Biggs, M. Andrews, “Conjugate gradient acceleration of maximum-likelihood image restoration,” Electron. Lett. 31, 1985–1986 (1995).
[CrossRef]

Biggs, D. S. C.

D. S. C. Biggs, M. Andrews, “Conjugate gradient acceleration of maximum-likelihood image restoration,” Electron. Lett. 31, 1985–1986 (1995).
[CrossRef]

Bonavito, N. L.

Busse, T.

Cornwell, T. J.

T. J. Cornwell, “Where have we been, where are we now, where are we going?” in The Restoration of HST Images and Spectra II, R. J. Hanisch, R. L. White, eds. (Space Telescope Science Institute, Baltimore, Md., 1994).

Dorband, J. E.

Fienup, J. R.

Flannery, B. P.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipies in C, 2nd ed. (Cambridge U. Press, Cambridge, 1992).

Gill, P. E.

P. E. Gill, W. Murray, M. H. Wright, Practical Optimization (Academic, New York, 1981).

Holmes, T. J.

Hook, R. N.

H. M. Adorf, R. N. Hook, L. B. Lucy, F. D. Murtagh, “Accelerating the Richardson–Lucy Restoration Algorithm,” in Fourth ESO/ST-ECF Data Analysis Workshop, (European Southern Observatory, Garching, Germany, 1992), pp. 99–103.

Kaufman, L.

L. Kaufman, “Implementing and accelerating the EM algorithm for positron emission tomography,” IEEE Trans. Med. Imaging 6, 37–51 (1987).
[CrossRef] [PubMed]

V. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Assoc. 80, 8–37 (1985).
[CrossRef]

Lane, R. G.

Liu, Y.-H.

Lucy, L. B.

L. B. Lucy, “An iterative technique for the rectification of observed images,” Astron. J. 79, 745–754 (1974).
[CrossRef]

H. M. Adorf, R. N. Hook, L. B. Lucy, F. D. Murtagh, “Accelerating the Richardson–Lucy Restoration Algorithm,” in Fourth ESO/ST-ECF Data Analysis Workshop, (European Southern Observatory, Garching, Germany, 1992), pp. 99–103.

Meinel, E. S.

Murray, W.

P. E. Gill, W. Murray, M. H. Wright, Practical Optimization (Academic, New York, 1981).

Murtagh, F. D.

H. M. Adorf, R. N. Hook, L. B. Lucy, F. D. Murtagh, “Accelerating the Richardson–Lucy Restoration Algorithm,” in Fourth ESO/ST-ECF Data Analysis Workshop, (European Southern Observatory, Garching, Germany, 1992), pp. 99–103.

Press, W. H.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipies in C, 2nd ed. (Cambridge U. Press, Cambridge, 1992).

Richardson, W. H.

Shepp, L. A.

V. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Assoc. 80, 8–37 (1985).
[CrossRef]

Teukolsky, S. A.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipies in C, 2nd ed. (Cambridge U. Press, Cambridge, 1992).

Vardi, V.

V. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Assoc. 80, 8–37 (1985).
[CrossRef]

Vetterling, W. T.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipies in C, 2nd ed. (Cambridge U. Press, Cambridge, 1992).

White, R. L.

R. L. White, “Image restoration using the damped Richardson—Lucy method,” in The Restoration of HST Images and Spectra II, R. J. Hanisch, R. L. White, eds. (Space Telescope Science Institute, Baltimore, Md., 1994).

Wright, M. H.

P. E. Gill, W. Murray, M. H. Wright, Practical Optimization (Academic, New York, 1981).

Appl. Opt. (2)

Astron. J. (1)

L. B. Lucy, “An iterative technique for the rectification of observed images,” Astron. J. 79, 745–754 (1974).
[CrossRef]

Electron. Lett. (1)

D. S. C. Biggs, M. Andrews, “Conjugate gradient acceleration of maximum-likelihood image restoration,” Electron. Lett. 31, 1985–1986 (1995).
[CrossRef]

IEEE Trans. Med. Imaging (1)

L. Kaufman, “Implementing and accelerating the EM algorithm for positron emission tomography,” IEEE Trans. Med. Imaging 6, 37–51 (1987).
[CrossRef] [PubMed]

J. Am. Stat. Assoc. (1)

V. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Assoc. 80, 8–37 (1985).
[CrossRef]

J. Opt. Soc. Am. (1)

J. Opt. Soc. Am. A (3)

Other (6)

R. L. White, “Image restoration using the damped Richardson—Lucy method,” in The Restoration of HST Images and Spectra II, R. J. Hanisch, R. L. White, eds. (Space Telescope Science Institute, Baltimore, Md., 1994).

T. J. Cornwell, “Where have we been, where are we now, where are we going?” in The Restoration of HST Images and Spectra II, R. J. Hanisch, R. L. White, eds. (Space Telescope Science Institute, Baltimore, Md., 1994).

H. M. Adorf, R. N. Hook, L. B. Lucy, F. D. Murtagh, “Accelerating the Richardson–Lucy Restoration Algorithm,” in Fourth ESO/ST-ECF Data Analysis Workshop, (European Southern Observatory, Garching, Germany, 1992), pp. 99–103.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipies in C, 2nd ed. (Cambridge U. Press, Cambridge, 1992).

P. E. Gill, W. Murray, M. H. Wright, Practical Optimization (Academic, New York, 1981).

The image of the binary stellar system R Aquarii was observed with the faint object camera and made available through the Science Assessment and Early Release Observations programme of the Space Telescope Science Institute.

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 (12)

Fig. 1
Fig. 1

Path of an individual pixel over 10,000 R–L iterations; (a) linear, (b) logarithmic scales.

Fig. 2
Fig. 2

(a) Conceptual difference between the unaccelerated and new accelerated method for five iterations. (b) Vector diagram illustrating the acceleration method in geometric terms.

Fig. 3
Fig. 3

Original F16 image from which the selected region of the tail is used, measuring 128 × 128 pixels.

Fig. 4
Fig. 4

Blurred and restored images using R–L; (a) blurred, (b) unaccelerated RL0(250), (c) accelerated RL1(250), (d) unaccelerated RL0(10,000).

Fig. 5
Fig. 5

(a) Acceleration parameter (αk) for RL1(250), (b) instantaneous and average acceleration factor for RL1(250).

Fig. 6
Fig. 6

(a) MSE between original and restored image (no noise) and (b) plotted with effective iterations, which shows the curves match. Unaccelerated RL0(10,000), solid curve; accelerated RL1(250), dashed curve.

Fig. 7
Fig. 7

R–L restoration of image corrupted with Poisson noise (Image mean = 1000); (a) unaccelerated RL0(32), (b) accelerated RL1(11).

Fig. 8
Fig. 8

MSE curves of restoration for Fig. 7. Image mean, 1000. Results are averaged over 100 different Poisson noise processes; average MSE (solid curve) with maximum and minimum MSE (dashed curves) at each iteration. Minimum unaccelerated MSE, dotted curve.

Fig. 9
Fig. 9

R–L restoration of image corrupted with Poisson noise (Image mean, 10,000); (a) unaccelerated RL0(151), (b) accelerated RL1(26).

Fig. 10
Fig. 10

MSE curves of restoration for Fig. 9; image mean, 10,000. Results are averaged over 100 different Poisson noise processes. Curves have the same definitions as in Fig. 8.

Fig. 11
Fig. 11

Restoration of R Aquarii using ME: (a) raw HST data, (b) mask applied to invalid data, (c) unaccelerated (1000 iterations), (d) accelerated (50 iterations).

Fig. 12
Fig. 12

Magnitude retrieval using the Gerchberg–Saxton algorithm; (a) unaccelerated (1000 iterations), (b) accelerated (70 iterations).

Tables (1)

Tables Icon

Table 1 Results of Restoration with Poisson Noise

Equations (33)

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

g=hf+n,
fˆk+1=fˆkh*ghfˆkψfˆk,
fˆk+1=fˆkh*ghfˆkκ,  where κ>1.
fˆk+λ=fˆk+λgk,
gkψfˆk-fˆk.
yk=xk+αkhk,
hkxk-xk-1,
xk+1=yk+gk,
gkψyk-yk.
αk= gk-1·gk-2 gk-2·gk-2, 0<αk<1.
βk= gk-1·gk-2 gk-1·gk-1=αk gk-2·gk-2 gk-1·gk-1.
ηk=1+j=1k m=k-j+1kγm,
γk=αkβk2.
fk+α=fk+αΔfk+12!α2Δ2fk+13!α3Δ3fk++1n!αnΔnfk+,
Δ2fk=Δfk-Δfk-1
=fk-fk-1-fk-1-fk-2
=fk-2fk-1 +fk-2;
αk= gk-1·gk-1 gk-2·gk-21/2, 0<αk<1.
RL0n=Unaccelerated R-L for n iterations, RL1n=Accelerated R-L for n iterations,
fk=c exph*λk,
xk+1=ψxk=xk+gk,
mx=-x-xsAx-xs, mx=-2Ax-xs,
gk=mxk=-2Axk-xs, A=SΛAS-1, B=I-2A, ΛB=I-2ΛA, xk=SΛBkS-1x0-xs+xs, <12 maxΛA;
xk=SΛBkS-1x0-xs+xs, gk-1=SΛBkI-ΛB-1S-1x0-xs, xk-δ=SΛBk-δS-1x0-xs+xs, gk-δ-1 =SΛBk-δI-ΛB-1S-1x0-xs.
hk,-δ=xk-xk-δ=SΛBkI-ΛB-δS-1x0-xs.
xk+δ=SΛBk+δS-1x0-xs+xs, gk+δ-1=SΛBk+δI-ΛB-1S-1x0-xs, hk,δ=xk+δ-xk=SΛBk+δI-ΛB-δS-1x0-xs.
hˆk,δ=αkhk,-δ, 0=hk,δ-αkhk,-δhk,-δ, αk=hk,δhk,-δhk,-δhk,-δ.
hk,δ=xk+δ-xk=SΛBk+δI-ΛB-δS-1x0-xs, I-ΛB-δδI-ΛB-1, hk,δδSΛBkI-ΛB-1S-1x0-xs=δgk-1 hk,-δδgk-δ-1, αkgk-1gk-δ-1gk-δ-1gk-δ-1.
yk=xk+αkxk-xk-1, xk+1=ψyk=yk+gk, αk+1=gkgk-1gk-1gk-1, yk+1=xk+1+αk+1xk+1-xk.
hˆk,δ=αkhk,-δk, hk, γkδk=αkhk,-δk,
δk=1+j=1k-1m=k-jk-1 γm.
ηk=1+j=1km=k-j+1k γm.
γˆk=αkgk-2gk-1gk-1gk-2gk-1gk-2M.

Metrics