Abstract

We present a unified approach for constructing iterative restorations of positively constrained objects. Specifically, a set of nonlinear algorithms, one of which is the Richardson–Lucy algorithm, is described for estimating positively constrained objects from data modeled by either Poisson or Gaussian processes. Exponential and monomial functions are used to remap the estimation space and to positively constrain the restorations. This technique also provides a method to accelerate the rate of convergence of known algorithms. Both one- and two-dimensional examples are presented.

© 1996 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. W. H. Richardson, “Bayesian-based iterative method of image restoration,” J. Opt. Soc. Am. 62, 55–59 (1972).
    [Crossref]
  2. L. B. Lucy, “An iterative technique for the rectification of observed distributions,” Astron. J. 79, 745–754 (1974).
    [Crossref]
  3. L. A. Shepp, Y. Vardi, “Maximum likelihood reconstruction for emission tomography,” IEEE Trans. Med. Imaging 1, 113–122 (1982).
    [Crossref] [PubMed]
  4. Y. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Soc. 80, 8–35 (1985).
    [Crossref]
  5. A. P. Dempster, N. M. Laird, D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. R. Stat. Soc. 39, 1–38 (1977).
  6. D. L. Snyder, T. J. Schulz, J. A. O’Sullivan, “Deblurring subject to nonnegativity constraints,” IEEE Trans. Sig. Process. 40, 1143–1150 (1992).
    [Crossref]
  7. J. Nunez, J. Llacer, “A fast Bayesian reconstruction algorithm for emission tomography with entropy prior converging to feasible images,” IEEE Trans. Med. Imaging 9, 159–171 (1990).
    [Crossref] [PubMed]
  8. D. L. Snyder, A. M. Hammoud, R. L. White, “Image recovery from data acquired with a charge-coupled-device camera,” J. Opt. Soc. Am. A 10, 1014–1023 (1993).
    [Crossref] [PubMed]
  9. C. L. Byrne, “Iterative image reconstruction algorithms based on cross-entropy minimization,” IEEE Trans. Image Process. 2, 96–103 (1993).
    [Crossref] [PubMed]
  10. L. Kaufman, “Implementing and accelerating the EM algorithm for positron emission tomography,” IEEE Trans. Med. Imaging 6, 37–51 (1987).
    [Crossref] [PubMed]
  11. M. E. Daube-Witherspoon, G. Muehllehner, “An iterative image space reconstruction algorithm suitable for volume ECT,” IEEE Trans. Med. Imaging 5, 61–66 (1986).
    [Crossref]
  12. A. R. De Pierro, “On the convergence of the iterative image space reconstruction algorithm for volume ECT,” IEEE Trans. Med. Imaging 6, 174–175 (1987).
    [Crossref]
  13. A. R. De Pierro, “On the relation between the ISRA and the EM algorithm for positron emission tomography,” IEEE Trans. Med. Imaging 12, 328–333 (1993).
    [Crossref] [PubMed]
  14. R. A. Gonsalves, “Phase retrieval and diversity in adaptive optics,” Opt. Eng. 21, 829–832 (1982).
    [Crossref]
  15. B. R. Hunt, “Bayesian methods in nonlinear digital image restoration,” IEEE Trans. Comput. 26, 219–229 (1977).
    [Crossref]
  16. H. J. Trussell, B. R. Hunt, “Improved methods of maximum a posteriorirestoration,” IEEE Trans. Comput., 27, 57–62 (1979).
    [Crossref]
  17. H. J. Trussell, “The relationship between image restoration by the maximum a posteriorimethod and maximum entropy method,” IEEE Trans. Acoust. Speech Signal Process. 28, 114–117 (1980).
    [Crossref]
  18. T. S. Zaccheo, R. A. Gonsalves, P. Nisenson, S. M. Ebstein, “Estimating the Cramér–Rao bound for astronomical observations: application to the Richardson–Lucy algorithm,” Astrophys. J. 458, 742–745 (1996).
    [Crossref]
  19. T. S. Zaccheo, “Digital image restorations: algorithms and accuracy with applications to astronomical observations,” Ph.D. dissertation (Tufts University, Medford, Mass., 1995).

1996 (1)

T. S. Zaccheo, R. A. Gonsalves, P. Nisenson, S. M. Ebstein, “Estimating the Cramér–Rao bound for astronomical observations: application to the Richardson–Lucy algorithm,” Astrophys. J. 458, 742–745 (1996).
[Crossref]

1993 (3)

D. L. Snyder, A. M. Hammoud, R. L. White, “Image recovery from data acquired with a charge-coupled-device camera,” J. Opt. Soc. Am. A 10, 1014–1023 (1993).
[Crossref] [PubMed]

C. L. Byrne, “Iterative image reconstruction algorithms based on cross-entropy minimization,” IEEE Trans. Image Process. 2, 96–103 (1993).
[Crossref] [PubMed]

A. R. De Pierro, “On the relation between the ISRA and the EM algorithm for positron emission tomography,” IEEE Trans. Med. Imaging 12, 328–333 (1993).
[Crossref] [PubMed]

1992 (1)

D. L. Snyder, T. J. Schulz, J. A. O’Sullivan, “Deblurring subject to nonnegativity constraints,” IEEE Trans. Sig. Process. 40, 1143–1150 (1992).
[Crossref]

1990 (1)

J. Nunez, J. Llacer, “A fast Bayesian reconstruction algorithm for emission tomography with entropy prior converging to feasible images,” IEEE Trans. Med. Imaging 9, 159–171 (1990).
[Crossref] [PubMed]

1987 (2)

A. R. De Pierro, “On the convergence of the iterative image space reconstruction algorithm for volume ECT,” IEEE Trans. Med. Imaging 6, 174–175 (1987).
[Crossref]

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

1986 (1)

M. E. Daube-Witherspoon, G. Muehllehner, “An iterative image space reconstruction algorithm suitable for volume ECT,” IEEE Trans. Med. Imaging 5, 61–66 (1986).
[Crossref]

1985 (1)

Y. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Soc. 80, 8–35 (1985).
[Crossref]

1982 (2)

L. A. Shepp, Y. Vardi, “Maximum likelihood reconstruction for emission tomography,” IEEE Trans. Med. Imaging 1, 113–122 (1982).
[Crossref] [PubMed]

R. A. Gonsalves, “Phase retrieval and diversity in adaptive optics,” Opt. Eng. 21, 829–832 (1982).
[Crossref]

1980 (1)

H. J. Trussell, “The relationship between image restoration by the maximum a posteriorimethod and maximum entropy method,” IEEE Trans. Acoust. Speech Signal Process. 28, 114–117 (1980).
[Crossref]

1979 (1)

H. J. Trussell, B. R. Hunt, “Improved methods of maximum a posteriorirestoration,” IEEE Trans. Comput., 27, 57–62 (1979).
[Crossref]

1977 (2)

B. R. Hunt, “Bayesian methods in nonlinear digital image restoration,” IEEE Trans. Comput. 26, 219–229 (1977).
[Crossref]

A. P. Dempster, N. M. Laird, D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. R. Stat. Soc. 39, 1–38 (1977).

1974 (1)

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

1972 (1)

Byrne, C. L.

C. L. Byrne, “Iterative image reconstruction algorithms based on cross-entropy minimization,” IEEE Trans. Image Process. 2, 96–103 (1993).
[Crossref] [PubMed]

Daube-Witherspoon, M. E.

M. E. Daube-Witherspoon, G. Muehllehner, “An iterative image space reconstruction algorithm suitable for volume ECT,” IEEE Trans. Med. Imaging 5, 61–66 (1986).
[Crossref]

De Pierro, A. R.

A. R. De Pierro, “On the relation between the ISRA and the EM algorithm for positron emission tomography,” IEEE Trans. Med. Imaging 12, 328–333 (1993).
[Crossref] [PubMed]

A. R. De Pierro, “On the convergence of the iterative image space reconstruction algorithm for volume ECT,” IEEE Trans. Med. Imaging 6, 174–175 (1987).
[Crossref]

Dempster, A. P.

A. P. Dempster, N. M. Laird, D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. R. Stat. Soc. 39, 1–38 (1977).

Ebstein, S. M.

T. S. Zaccheo, R. A. Gonsalves, P. Nisenson, S. M. Ebstein, “Estimating the Cramér–Rao bound for astronomical observations: application to the Richardson–Lucy algorithm,” Astrophys. J. 458, 742–745 (1996).
[Crossref]

Gonsalves, R. A.

T. S. Zaccheo, R. A. Gonsalves, P. Nisenson, S. M. Ebstein, “Estimating the Cramér–Rao bound for astronomical observations: application to the Richardson–Lucy algorithm,” Astrophys. J. 458, 742–745 (1996).
[Crossref]

R. A. Gonsalves, “Phase retrieval and diversity in adaptive optics,” Opt. Eng. 21, 829–832 (1982).
[Crossref]

Hammoud, A. M.

Hunt, B. R.

H. J. Trussell, B. R. Hunt, “Improved methods of maximum a posteriorirestoration,” IEEE Trans. Comput., 27, 57–62 (1979).
[Crossref]

B. R. Hunt, “Bayesian methods in nonlinear digital image restoration,” IEEE Trans. Comput. 26, 219–229 (1977).
[Crossref]

Kaufman, L.

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

Y. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Soc. 80, 8–35 (1985).
[Crossref]

Laird, N. M.

A. P. Dempster, N. M. Laird, D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. R. Stat. Soc. 39, 1–38 (1977).

Llacer, J.

J. Nunez, J. Llacer, “A fast Bayesian reconstruction algorithm for emission tomography with entropy prior converging to feasible images,” IEEE Trans. Med. Imaging 9, 159–171 (1990).
[Crossref] [PubMed]

Lucy, L. B.

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

Muehllehner, G.

M. E. Daube-Witherspoon, G. Muehllehner, “An iterative image space reconstruction algorithm suitable for volume ECT,” IEEE Trans. Med. Imaging 5, 61–66 (1986).
[Crossref]

Nisenson, P.

T. S. Zaccheo, R. A. Gonsalves, P. Nisenson, S. M. Ebstein, “Estimating the Cramér–Rao bound for astronomical observations: application to the Richardson–Lucy algorithm,” Astrophys. J. 458, 742–745 (1996).
[Crossref]

Nunez, J.

J. Nunez, J. Llacer, “A fast Bayesian reconstruction algorithm for emission tomography with entropy prior converging to feasible images,” IEEE Trans. Med. Imaging 9, 159–171 (1990).
[Crossref] [PubMed]

O’Sullivan, J. A.

D. L. Snyder, T. J. Schulz, J. A. O’Sullivan, “Deblurring subject to nonnegativity constraints,” IEEE Trans. Sig. Process. 40, 1143–1150 (1992).
[Crossref]

Richardson, W. H.

Rubin, D. B.

A. P. Dempster, N. M. Laird, D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. R. Stat. Soc. 39, 1–38 (1977).

Schulz, T. J.

D. L. Snyder, T. J. Schulz, J. A. O’Sullivan, “Deblurring subject to nonnegativity constraints,” IEEE Trans. Sig. Process. 40, 1143–1150 (1992).
[Crossref]

Shepp, L. A.

Y. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Soc. 80, 8–35 (1985).
[Crossref]

L. A. Shepp, Y. Vardi, “Maximum likelihood reconstruction for emission tomography,” IEEE Trans. Med. Imaging 1, 113–122 (1982).
[Crossref] [PubMed]

Snyder, D. L.

D. L. Snyder, A. M. Hammoud, R. L. White, “Image recovery from data acquired with a charge-coupled-device camera,” J. Opt. Soc. Am. A 10, 1014–1023 (1993).
[Crossref] [PubMed]

D. L. Snyder, T. J. Schulz, J. A. O’Sullivan, “Deblurring subject to nonnegativity constraints,” IEEE Trans. Sig. Process. 40, 1143–1150 (1992).
[Crossref]

Trussell, H. J.

H. J. Trussell, “The relationship between image restoration by the maximum a posteriorimethod and maximum entropy method,” IEEE Trans. Acoust. Speech Signal Process. 28, 114–117 (1980).
[Crossref]

H. J. Trussell, B. R. Hunt, “Improved methods of maximum a posteriorirestoration,” IEEE Trans. Comput., 27, 57–62 (1979).
[Crossref]

Vardi, Y.

Y. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Soc. 80, 8–35 (1985).
[Crossref]

L. A. Shepp, Y. Vardi, “Maximum likelihood reconstruction for emission tomography,” IEEE Trans. Med. Imaging 1, 113–122 (1982).
[Crossref] [PubMed]

White, R. L.

Zaccheo, T. S.

T. S. Zaccheo, R. A. Gonsalves, P. Nisenson, S. M. Ebstein, “Estimating the Cramér–Rao bound for astronomical observations: application to the Richardson–Lucy algorithm,” Astrophys. J. 458, 742–745 (1996).
[Crossref]

T. S. Zaccheo, “Digital image restorations: algorithms and accuracy with applications to astronomical observations,” Ph.D. dissertation (Tufts University, Medford, Mass., 1995).

Astron. J. (1)

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

Astrophys. J. (1)

T. S. Zaccheo, R. A. Gonsalves, P. Nisenson, S. M. Ebstein, “Estimating the Cramér–Rao bound for astronomical observations: application to the Richardson–Lucy algorithm,” Astrophys. J. 458, 742–745 (1996).
[Crossref]

IEEE Trans. Acoust. Speech Signal Process. (1)

H. J. Trussell, “The relationship between image restoration by the maximum a posteriorimethod and maximum entropy method,” IEEE Trans. Acoust. Speech Signal Process. 28, 114–117 (1980).
[Crossref]

IEEE Trans. Comput. (2)

B. R. Hunt, “Bayesian methods in nonlinear digital image restoration,” IEEE Trans. Comput. 26, 219–229 (1977).
[Crossref]

H. J. Trussell, B. R. Hunt, “Improved methods of maximum a posteriorirestoration,” IEEE Trans. Comput., 27, 57–62 (1979).
[Crossref]

IEEE Trans. Image Process. (1)

C. L. Byrne, “Iterative image reconstruction algorithms based on cross-entropy minimization,” IEEE Trans. Image Process. 2, 96–103 (1993).
[Crossref] [PubMed]

IEEE Trans. Med. Imaging (6)

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

M. E. Daube-Witherspoon, G. Muehllehner, “An iterative image space reconstruction algorithm suitable for volume ECT,” IEEE Trans. Med. Imaging 5, 61–66 (1986).
[Crossref]

A. R. De Pierro, “On the convergence of the iterative image space reconstruction algorithm for volume ECT,” IEEE Trans. Med. Imaging 6, 174–175 (1987).
[Crossref]

A. R. De Pierro, “On the relation between the ISRA and the EM algorithm for positron emission tomography,” IEEE Trans. Med. Imaging 12, 328–333 (1993).
[Crossref] [PubMed]

L. A. Shepp, Y. Vardi, “Maximum likelihood reconstruction for emission tomography,” IEEE Trans. Med. Imaging 1, 113–122 (1982).
[Crossref] [PubMed]

J. Nunez, J. Llacer, “A fast Bayesian reconstruction algorithm for emission tomography with entropy prior converging to feasible images,” IEEE Trans. Med. Imaging 9, 159–171 (1990).
[Crossref] [PubMed]

IEEE Trans. Sig. Process. (1)

D. L. Snyder, T. J. Schulz, J. A. O’Sullivan, “Deblurring subject to nonnegativity constraints,” IEEE Trans. Sig. Process. 40, 1143–1150 (1992).
[Crossref]

J. Am. Stat. Soc. (1)

Y. Vardi, L. A. Shepp, L. Kaufman, “A statistical model for positron emission tomography,” J. Am. Stat. Soc. 80, 8–35 (1985).
[Crossref]

J. Opt. Soc. Am. (1)

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

J. R. Stat. Soc. (1)

A. P. Dempster, N. M. Laird, D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. R. Stat. Soc. 39, 1–38 (1977).

Opt. Eng. (1)

R. A. Gonsalves, “Phase retrieval and diversity in adaptive optics,” Opt. Eng. 21, 829–832 (1982).
[Crossref]

Other (1)

T. S. Zaccheo, “Digital image restorations: algorithms and accuracy with applications to astronomical observations,” Ph.D. dissertation (Tufts University, Medford, Mass., 1995).

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

Fig. 1
Fig. 1

RL and iterative Gaussian algorithms. A, Flow diagram representing the accelerated RL process; B, block diagram of the iterative Gaussian algorithm. In both cases it is assumed that the quantity Pj = 1. Note that B requires only one matrix operation (PTP)ân per iteration, whereas A requires two separate matrix operations ( and PT[d/ĝ]).

Fig. 2
Fig. 2

One-dimensional Poisson example. A, Original object containing two simulated stars and an extended object; B, one-dimensional blurring function obtained by integration of a synthetic Hubble Space Telescope psf; C, observable data described by the convolution of A with B and corrupted by Poisson noise; D, Wiener filter estimate for the above data; E, typical RL estimate constructed with 100 iterations, with C as the initial estimate and β = 1; F, accelerated RL estimate obtained with 50 iterations and β = 2. In this case each new estimate was normalized at the end of each pass.

Fig. 3
Fig. 3

One-dimensional Gaussian example. A, Typical observable data synthesized by convolution of Fig. 1A with Fig. 1B and addition of Gaussian noise with σ2 equaling 5% of the maximum of g. B, Typical Wiener filter estimate for the above data. C, typical estimated results from 100 iterations of the RL-like algorithm for Gaussian data. Its initial estimate was set to A and β = 1. D, Accelerated estimate obtained with 50 iterations and β = 2. In this case each estimate was normalized to conserve the total input data area.

Fig. 4
Fig. 4

Log likelihood versus iteration for one-dimensional estimates obtained with both the RL and the iterative Gaussian algorithms. Dotted curves, data obtained for β = 1; solid curves, the values for β = 2. A, Log likelihood [Eq. (3)] at each iteration for the estimates shown in Figs. 1E and 1F; B, the negative of the total squared error [Eq. (12)] for the estimates described by Figs. 2C and 2D.

Fig. 5
Fig. 5

Comparison of the log likelihood values produced by the iterative Gaussian (solid curves) and RL (dashed curves) algorithms for both Gaussian and Poisson data. A, the log likelihood [Eq. (12)] versus iteration for Poisson data; B, the log likelihood −(dĝ)2 versus iteration for Gaussian data.

Fig. 6
Fig. 6

Two-dimensional Gaussian example. A, Original object, a cameraman; B, typical observable data synthesized by convolution of A with a two-dimensional Gaussian blurring function, σw2 = 3, and addition of Gaussian noise, with σn2 equaling 5% of the maximum of g; C, typical Wiener filter estimate; D, typical RL-like estimate based on 50 iterations. In this case B was used as the initial estimate, and β = 1. The Wiener and the RL-like estimates have similar total squared errors.

Equations (23)

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

g = Pa ,
p ( d g ) = k = 0 N exp ( - g k ) g k d k d k ! ,
L ( d g ) = - k = 0 N p k j [ g k - d k ln ( g k ) ] + C ,
P T [ d / g ] - P T u = 0 ,
[ d / g ] = u             or             d = Pa .
a ^ = P - 1 d ,
[ f ( s j ) s j ] n + 1 = 1 P j k = 0 N p k j d k g ^ k n [ f ( s j ) s j ] n ,
a ^ j n + 1 = a ^ j n P j k = 0 N p k j d k g ^ k n .
a ^ j n + 1 = a ^ j n ( 1 P j k = 0 N p k j d k g ^ k n ) α α - 1 .
s ^ j n + 1 = s ^ j n + β ln ( 1 P j k = 0 N p k j d k g ^ k n ) .
p ( d a ) = 1 2 π σ 2 k = 0 N exp [ - ( d k - g k ) 2 / 2 σ 2 ] .
L ( d g ) = - 1 2 σ 2 k = 0 N ( d k - g k ) 2 + C ,
a ^ j n + 1 = a ^ j n ( k = 0 N p k j d k k = 0 N p k j g ^ k n ) β .
g k = P k a ,             k = 1 , 2 , , N ,
P T = [ P 1 , , P N ]
D T = [ d 1 , , d N ] .
A ^ n + 1 = A ^ n P T ( D P G ^ ) ,
G ^ T = [ g ^ 1 , , g ^ N ] = [ P 1 a ^ 1 , , P N a ^ N ] .
A ^ n + 1 = A ^ n ( P T D P T P A ^ ) .
A ^ n + 1 = A ^ n [ P 1 T ( d 1 P 1 g ^ 1 ) P N T ( d N P N g ^ N ) ] .
A ^ n + 1 = A ^ n [ P 1 T d 1 + + P N T d N ( P 1 T P 1 + + P N T P N ) A ^ n ] .
p ( a d ) = p ( d a ) p ( a ) p ( d ) .
[ L ( d a ) a j + L ( a ) a j ] a j s j = 0 ,

Metrics