Abstract

The expectation-maximization (EM) algorithm for maximum-likelihood image recovery is guaranteed to converge, but it converges slowly. Its ordered-subset version (OS-EM) is used widely in tomographic image reconstruction because of its order-of-magnitude acceleration compared with the EM algorithm, but it does not guarantee convergence. Recently the ordered-subset, separable-paraboloidal-surrogate (OS-SPS) algorithm with relaxation has been shown to converge to the optimal point while providing fast convergence. We adapt the relaxed OS-SPS algorithm to the problem of image restoration. Because data acquisition in image restoration is different from that in tomography, we employ a different strategy for choosing subsets, using pixel locations rather than projection angles. Simulation results show that the relaxed OS-SPS algorithm can provide an order-of-magnitude acceleration over the EM algorithm for image restoration. This new algorithm now provides the speed and guaranteed convergence necessary for efficient image restoration.

© 2003 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. R. Richardson, “Bayesian-based iterative method of image restoration,” J. Opt. Soc. Am. 62, 55–59 (1972).
    [CrossRef]
  2. T. J. Holmes, “Maximum-likelihood image restoration adapted for noncoherent optical imaging,” J. Opt. Soc. Am. A 5, 666–673 (1988).
    [CrossRef]
  3. S. Joshi, M. I. Miller, “Maximum a posteriori estimation with Good’s roughness for three-dimensional optical-sectioning microscopy,” J. Opt. Soc. Am. A 10, 1078–1085 (1993).
    [CrossRef] [PubMed]
  4. R. G. Lane, “Methods for maximum-likelihood deconvolution,” J. Opt. Soc. Am. A 13, 1992–1998 (1996).
    [CrossRef]
  5. J. A. Conchello, J. G. McNally, “Fast regularization technique for expectation maximization algorithm for computational optical sectioning microscopy,” in Three-Dimensional and Multidimensional Microscopy: Image Acquisition and Processing, C. J. Cogswell, G. S. Kino, T. Wilson, eds., Proc. SPIE2655, 199–208 (1996).
    [CrossRef]
  6. A. P. Dempster, N. M. Laird, D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. R. Stat. Soc. B 39, 1–38 (1977).
  7. A. R. De Pierro, “A modified expectation maximization algorithm for penalized likelihood estimation in emission tomography,” IEEE Trans. Med. Imaging 14, 132–137 (1995).
    [CrossRef] [PubMed]
  8. H. M. Hudson, R. S. Larkin, “Accelerated image reconstruction using ordered subsets of projection data,” IEEE Trans. Med. Imaging 13, 601–609 (1994).
    [CrossRef] [PubMed]
  9. C. L. Byrne, “Accelerating the EMML algorithm and related iterative algorithms by rescaled block-iterative methods,” IEEE Trans. Image Process. 7, 100–109 (1998).
    [CrossRef]
  10. C. L. Byrne, “Convergent block-iterative algorithms for image reconstruction from inconsistent data,” IEEE Trans. Image Process. 6, 1296–1304 (1997).
    [CrossRef] [PubMed]
  11. J. A. Browne, A. R. D. Pierro, “A row-action alternative to the EM algorithm for maximizing likelihoods in emission tomography,” IEEE Trans. Med. Imaging 15, 687–699 (1996).
    [CrossRef]
  12. A. R. D. Pierro, M. E. B. Yamagishi, “Fast EM-like methods for maximum ‘a posteriori’ estimates in emission tomography,” IEEE Trans. Med. Imaging 20, 280–288 (2001).
    [CrossRef] [PubMed]
  13. J. A. Fessler, H. Erdoğan, “A paraboloidal surrogates algorithm for convergent penalized-likelihood emission image reconstruction,” in Proceedings of the IEEE Nuclear Science Symposium and Medical Imaging Conference (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 1132–1135.
  14. H. Erdoğan, J. A. Fessler, “Monotonic algorithms for transmission tomography,” IEEE Trans. Med. Imaging 18, 801–814 (1999).
    [CrossRef] [PubMed]
  15. S. Ahn, J. A. Fessler, “Globally convergent image reconstruction for emission tomography using relaxed ordered subsets algorithms,” IEEE Trans. Med. Imaging (to be published).
  16. S. Ahn, J. A. Fessler, “Globally convergent ordered subsets algorithms: application to tomography,” in Proceedings of the IEEE Nuclear Science Symposium and Medical Imaging Conference (Institute of Electrical and Electronics Engineers, New York, 2001), pp. 1064–1068.
  17. H. Erdoğan, J. A. Fessler, “Ordered subsets algorithm for transmission tomography,” Phys. Med. Biol. 44, 2835–2851 (1999).
    [CrossRef]
  18. S. Sotthivirat, J. A. Fessler, “Relaxed ordered subsets algorithm for image restoration of confocal microscopy,” in Proceedings of the IEEE International Symposium on Biomedical Imaging (Institute of Electrical and Electronics Engineers, New York, 2002), pp. 1051–1054.
  19. M. Bertero, P. Boccacci, “Application of the OS-EM method to the restoration of LBT images,” Astron. Astrophys. Suppl. Ser. 144, 181–186 (2000).
    [CrossRef]
  20. D. P. Bertsekas, “A new class of incremental gradient methods for least squares problems,” SIAM J. Optim. 7, 913–926 (1997).
    [CrossRef]
  21. 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]
  22. D. L. Snyder, C. W. Helstrom, A. D. Lanterman, M. Faisal, R. L. White, “Compensation for readout noise in CCD images,” J. Opt. Soc. Am. A 12, 272–283 (1995).
    [CrossRef]
  23. P. J. Huber, Robust Statistics (Wiley, New York, 1981).
  24. J. A. Fessler, “Grouped coordinate descent algorithms for robust edge-preserving image restoration,” in Image Reconstruction and Restoration II, T. J. Schulz, ed., Proc. SPIE3170, 184–194 (1997).
    [CrossRef]
  25. S. Sotthivirat, J. A. Fessler, “Image recovery using partitioned-separable paraboloidal surrogate coordinate ascent algorithms,” IEEE Trans. Image Process. 11, 159–173 (2002).
  26. T. J. Holmes, “Blind deconvolution of quantum-limited incoherent imagery: maximum-likelihood approach,” J. Opt. Soc. Am. A 9, 1052–1061 (1992).
    [CrossRef] [PubMed]
  27. E. Thiébaut, J.-M. Conan, “Strict a priori constraints for maximum-likelihood blind deconvolution,” J. Opt. Soc. Am. A 12, 485–492 (1995).
    [CrossRef]
  28. J. Markham, J. A. Conchello, “Parametric blind deconvolution: a robust method for the simultaneous estimation of image and blur,” J. Opt. Soc. Am. A 16, 2377–2391 (1999).
    [CrossRef]
  29. E. Y. Lam, J. W. Goodman, “Iterative statistical approach to blind image deconvolution,” J. Opt. Soc. Am. A 17, 1177–1184 (2000).
    [CrossRef]
  30. J. C. D. de Melo, “Partial FFT Evaluation,” in International Conference on Signal Processing Application and Technology (1996), Vol. 1, pp. 134–141, available at http://www.icspat.com/papers/234amfi.pdf .
  31. S. K. Mitra, Digital Signal Processing: A Computer-Based Approach, 2nd ed. (McGraw-Hill, New York, 2001).
  32. The XCOSM deconvolution package (online). Available at http://3dmicroscopy.wustl.edu/∼xcosm/ .
  33. K. Lange, “Convergence of EM image reconstruction algorithms with Gibbs smoothing,” IEEE Trans. Med. Imaging 9, 439–446 (1990).
    [CrossRef] [PubMed]

2002 (1)

S. Sotthivirat, J. A. Fessler, “Image recovery using partitioned-separable paraboloidal surrogate coordinate ascent algorithms,” IEEE Trans. Image Process. 11, 159–173 (2002).

2001 (1)

A. R. D. Pierro, M. E. B. Yamagishi, “Fast EM-like methods for maximum ‘a posteriori’ estimates in emission tomography,” IEEE Trans. Med. Imaging 20, 280–288 (2001).
[CrossRef] [PubMed]

2000 (2)

M. Bertero, P. Boccacci, “Application of the OS-EM method to the restoration of LBT images,” Astron. Astrophys. Suppl. Ser. 144, 181–186 (2000).
[CrossRef]

E. Y. Lam, J. W. Goodman, “Iterative statistical approach to blind image deconvolution,” J. Opt. Soc. Am. A 17, 1177–1184 (2000).
[CrossRef]

1999 (3)

J. Markham, J. A. Conchello, “Parametric blind deconvolution: a robust method for the simultaneous estimation of image and blur,” J. Opt. Soc. Am. A 16, 2377–2391 (1999).
[CrossRef]

H. Erdoğan, J. A. Fessler, “Monotonic algorithms for transmission tomography,” IEEE Trans. Med. Imaging 18, 801–814 (1999).
[CrossRef] [PubMed]

H. Erdoğan, J. A. Fessler, “Ordered subsets algorithm for transmission tomography,” Phys. Med. Biol. 44, 2835–2851 (1999).
[CrossRef]

1998 (1)

C. L. Byrne, “Accelerating the EMML algorithm and related iterative algorithms by rescaled block-iterative methods,” IEEE Trans. Image Process. 7, 100–109 (1998).
[CrossRef]

1997 (2)

C. L. Byrne, “Convergent block-iterative algorithms for image reconstruction from inconsistent data,” IEEE Trans. Image Process. 6, 1296–1304 (1997).
[CrossRef] [PubMed]

D. P. Bertsekas, “A new class of incremental gradient methods for least squares problems,” SIAM J. Optim. 7, 913–926 (1997).
[CrossRef]

1996 (2)

J. A. Browne, A. R. D. Pierro, “A row-action alternative to the EM algorithm for maximizing likelihoods in emission tomography,” IEEE Trans. Med. Imaging 15, 687–699 (1996).
[CrossRef]

R. G. Lane, “Methods for maximum-likelihood deconvolution,” J. Opt. Soc. Am. A 13, 1992–1998 (1996).
[CrossRef]

1995 (3)

1994 (1)

H. M. Hudson, R. S. Larkin, “Accelerated image reconstruction using ordered subsets of projection data,” IEEE Trans. Med. Imaging 13, 601–609 (1994).
[CrossRef] [PubMed]

1993 (2)

1992 (1)

1990 (1)

K. Lange, “Convergence of EM image reconstruction algorithms with Gibbs smoothing,” IEEE Trans. Med. Imaging 9, 439–446 (1990).
[CrossRef] [PubMed]

1988 (1)

1977 (1)

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

1972 (1)

Ahn, S.

S. Ahn, J. A. Fessler, “Globally convergent image reconstruction for emission tomography using relaxed ordered subsets algorithms,” IEEE Trans. Med. Imaging (to be published).

S. Ahn, J. A. Fessler, “Globally convergent ordered subsets algorithms: application to tomography,” in Proceedings of the IEEE Nuclear Science Symposium and Medical Imaging Conference (Institute of Electrical and Electronics Engineers, New York, 2001), pp. 1064–1068.

Bertero, M.

M. Bertero, P. Boccacci, “Application of the OS-EM method to the restoration of LBT images,” Astron. Astrophys. Suppl. Ser. 144, 181–186 (2000).
[CrossRef]

Bertsekas, D. P.

D. P. Bertsekas, “A new class of incremental gradient methods for least squares problems,” SIAM J. Optim. 7, 913–926 (1997).
[CrossRef]

Boccacci, P.

M. Bertero, P. Boccacci, “Application of the OS-EM method to the restoration of LBT images,” Astron. Astrophys. Suppl. Ser. 144, 181–186 (2000).
[CrossRef]

Browne, J. A.

J. A. Browne, A. R. D. Pierro, “A row-action alternative to the EM algorithm for maximizing likelihoods in emission tomography,” IEEE Trans. Med. Imaging 15, 687–699 (1996).
[CrossRef]

Byrne, C. L.

C. L. Byrne, “Accelerating the EMML algorithm and related iterative algorithms by rescaled block-iterative methods,” IEEE Trans. Image Process. 7, 100–109 (1998).
[CrossRef]

C. L. Byrne, “Convergent block-iterative algorithms for image reconstruction from inconsistent data,” IEEE Trans. Image Process. 6, 1296–1304 (1997).
[CrossRef] [PubMed]

Conan, J.-M.

Conchello, J. A.

J. Markham, J. A. Conchello, “Parametric blind deconvolution: a robust method for the simultaneous estimation of image and blur,” J. Opt. Soc. Am. A 16, 2377–2391 (1999).
[CrossRef]

J. A. Conchello, J. G. McNally, “Fast regularization technique for expectation maximization algorithm for computational optical sectioning microscopy,” in Three-Dimensional and Multidimensional Microscopy: Image Acquisition and Processing, C. J. Cogswell, G. S. Kino, T. Wilson, eds., Proc. SPIE2655, 199–208 (1996).
[CrossRef]

de Melo, J. C. D.

J. C. D. de Melo, “Partial FFT Evaluation,” in International Conference on Signal Processing Application and Technology (1996), Vol. 1, pp. 134–141, available at http://www.icspat.com/papers/234amfi.pdf .

De Pierro, A. R.

A. R. De Pierro, “A modified expectation maximization algorithm for penalized likelihood estimation in emission tomography,” IEEE Trans. Med. Imaging 14, 132–137 (1995).
[CrossRef] [PubMed]

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. B 39, 1–38 (1977).

Erdogan, H.

H. Erdoğan, J. A. Fessler, “Monotonic algorithms for transmission tomography,” IEEE Trans. Med. Imaging 18, 801–814 (1999).
[CrossRef] [PubMed]

H. Erdoğan, J. A. Fessler, “Ordered subsets algorithm for transmission tomography,” Phys. Med. Biol. 44, 2835–2851 (1999).
[CrossRef]

J. A. Fessler, H. Erdoğan, “A paraboloidal surrogates algorithm for convergent penalized-likelihood emission image reconstruction,” in Proceedings of the IEEE Nuclear Science Symposium and Medical Imaging Conference (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 1132–1135.

Faisal, M.

Fessler, J. A.

S. Sotthivirat, J. A. Fessler, “Image recovery using partitioned-separable paraboloidal surrogate coordinate ascent algorithms,” IEEE Trans. Image Process. 11, 159–173 (2002).

H. Erdoğan, J. A. Fessler, “Ordered subsets algorithm for transmission tomography,” Phys. Med. Biol. 44, 2835–2851 (1999).
[CrossRef]

H. Erdoğan, J. A. Fessler, “Monotonic algorithms for transmission tomography,” IEEE Trans. Med. Imaging 18, 801–814 (1999).
[CrossRef] [PubMed]

J. A. Fessler, H. Erdoğan, “A paraboloidal surrogates algorithm for convergent penalized-likelihood emission image reconstruction,” in Proceedings of the IEEE Nuclear Science Symposium and Medical Imaging Conference (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 1132–1135.

S. Ahn, J. A. Fessler, “Globally convergent ordered subsets algorithms: application to tomography,” in Proceedings of the IEEE Nuclear Science Symposium and Medical Imaging Conference (Institute of Electrical and Electronics Engineers, New York, 2001), pp. 1064–1068.

S. Ahn, J. A. Fessler, “Globally convergent image reconstruction for emission tomography using relaxed ordered subsets algorithms,” IEEE Trans. Med. Imaging (to be published).

S. Sotthivirat, J. A. Fessler, “Relaxed ordered subsets algorithm for image restoration of confocal microscopy,” in Proceedings of the IEEE International Symposium on Biomedical Imaging (Institute of Electrical and Electronics Engineers, New York, 2002), pp. 1051–1054.

J. A. Fessler, “Grouped coordinate descent algorithms for robust edge-preserving image restoration,” in Image Reconstruction and Restoration II, T. J. Schulz, ed., Proc. SPIE3170, 184–194 (1997).
[CrossRef]

Goodman, J. W.

Hammoud, A. M.

Helstrom, C. W.

Holmes, T. J.

Huber, P. J.

P. J. Huber, Robust Statistics (Wiley, New York, 1981).

Hudson, H. M.

H. M. Hudson, R. S. Larkin, “Accelerated image reconstruction using ordered subsets of projection data,” IEEE Trans. Med. Imaging 13, 601–609 (1994).
[CrossRef] [PubMed]

Joshi, S.

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. B 39, 1–38 (1977).

Lam, E. Y.

Lane, R. G.

Lange, K.

K. Lange, “Convergence of EM image reconstruction algorithms with Gibbs smoothing,” IEEE Trans. Med. Imaging 9, 439–446 (1990).
[CrossRef] [PubMed]

Lanterman, A. D.

Larkin, R. S.

H. M. Hudson, R. S. Larkin, “Accelerated image reconstruction using ordered subsets of projection data,” IEEE Trans. Med. Imaging 13, 601–609 (1994).
[CrossRef] [PubMed]

Markham, J.

McNally, J. G.

J. A. Conchello, J. G. McNally, “Fast regularization technique for expectation maximization algorithm for computational optical sectioning microscopy,” in Three-Dimensional and Multidimensional Microscopy: Image Acquisition and Processing, C. J. Cogswell, G. S. Kino, T. Wilson, eds., Proc. SPIE2655, 199–208 (1996).
[CrossRef]

Miller, M. I.

Mitra, S. K.

S. K. Mitra, Digital Signal Processing: A Computer-Based Approach, 2nd ed. (McGraw-Hill, New York, 2001).

Pierro, A. R. D.

A. R. D. Pierro, M. E. B. Yamagishi, “Fast EM-like methods for maximum ‘a posteriori’ estimates in emission tomography,” IEEE Trans. Med. Imaging 20, 280–288 (2001).
[CrossRef] [PubMed]

J. A. Browne, A. R. D. Pierro, “A row-action alternative to the EM algorithm for maximizing likelihoods in emission tomography,” IEEE Trans. Med. Imaging 15, 687–699 (1996).
[CrossRef]

Richardson, R.

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. B 39, 1–38 (1977).

Snyder, D. L.

Sotthivirat, S.

S. Sotthivirat, J. A. Fessler, “Image recovery using partitioned-separable paraboloidal surrogate coordinate ascent algorithms,” IEEE Trans. Image Process. 11, 159–173 (2002).

S. Sotthivirat, J. A. Fessler, “Relaxed ordered subsets algorithm for image restoration of confocal microscopy,” in Proceedings of the IEEE International Symposium on Biomedical Imaging (Institute of Electrical and Electronics Engineers, New York, 2002), pp. 1051–1054.

Thiébaut, E.

White, R. L.

Yamagishi, M. E. B.

A. R. D. Pierro, M. E. B. Yamagishi, “Fast EM-like methods for maximum ‘a posteriori’ estimates in emission tomography,” IEEE Trans. Med. Imaging 20, 280–288 (2001).
[CrossRef] [PubMed]

Astron. Astrophys. Suppl. Ser. (1)

M. Bertero, P. Boccacci, “Application of the OS-EM method to the restoration of LBT images,” Astron. Astrophys. Suppl. Ser. 144, 181–186 (2000).
[CrossRef]

IEEE Trans. Image Process. (3)

C. L. Byrne, “Accelerating the EMML algorithm and related iterative algorithms by rescaled block-iterative methods,” IEEE Trans. Image Process. 7, 100–109 (1998).
[CrossRef]

C. L. Byrne, “Convergent block-iterative algorithms for image reconstruction from inconsistent data,” IEEE Trans. Image Process. 6, 1296–1304 (1997).
[CrossRef] [PubMed]

S. Sotthivirat, J. A. Fessler, “Image recovery using partitioned-separable paraboloidal surrogate coordinate ascent algorithms,” IEEE Trans. Image Process. 11, 159–173 (2002).

IEEE Trans. Med. Imaging (6)

K. Lange, “Convergence of EM image reconstruction algorithms with Gibbs smoothing,” IEEE Trans. Med. Imaging 9, 439–446 (1990).
[CrossRef] [PubMed]

J. A. Browne, A. R. D. Pierro, “A row-action alternative to the EM algorithm for maximizing likelihoods in emission tomography,” IEEE Trans. Med. Imaging 15, 687–699 (1996).
[CrossRef]

A. R. D. Pierro, M. E. B. Yamagishi, “Fast EM-like methods for maximum ‘a posteriori’ estimates in emission tomography,” IEEE Trans. Med. Imaging 20, 280–288 (2001).
[CrossRef] [PubMed]

A. R. De Pierro, “A modified expectation maximization algorithm for penalized likelihood estimation in emission tomography,” IEEE Trans. Med. Imaging 14, 132–137 (1995).
[CrossRef] [PubMed]

H. M. Hudson, R. S. Larkin, “Accelerated image reconstruction using ordered subsets of projection data,” IEEE Trans. Med. Imaging 13, 601–609 (1994).
[CrossRef] [PubMed]

H. Erdoğan, J. A. Fessler, “Monotonic algorithms for transmission tomography,” IEEE Trans. Med. Imaging 18, 801–814 (1999).
[CrossRef] [PubMed]

J. Opt. Soc. Am. (1)

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

J. R. Stat. Soc. B (1)

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

Phys. Med. Biol. (1)

H. Erdoğan, J. A. Fessler, “Ordered subsets algorithm for transmission tomography,” Phys. Med. Biol. 44, 2835–2851 (1999).
[CrossRef]

SIAM J. Optim. (1)

D. P. Bertsekas, “A new class of incremental gradient methods for least squares problems,” SIAM J. Optim. 7, 913–926 (1997).
[CrossRef]

Other (10)

P. J. Huber, Robust Statistics (Wiley, New York, 1981).

J. A. Fessler, “Grouped coordinate descent algorithms for robust edge-preserving image restoration,” in Image Reconstruction and Restoration II, T. J. Schulz, ed., Proc. SPIE3170, 184–194 (1997).
[CrossRef]

S. Sotthivirat, J. A. Fessler, “Relaxed ordered subsets algorithm for image restoration of confocal microscopy,” in Proceedings of the IEEE International Symposium on Biomedical Imaging (Institute of Electrical and Electronics Engineers, New York, 2002), pp. 1051–1054.

S. Ahn, J. A. Fessler, “Globally convergent image reconstruction for emission tomography using relaxed ordered subsets algorithms,” IEEE Trans. Med. Imaging (to be published).

S. Ahn, J. A. Fessler, “Globally convergent ordered subsets algorithms: application to tomography,” in Proceedings of the IEEE Nuclear Science Symposium and Medical Imaging Conference (Institute of Electrical and Electronics Engineers, New York, 2001), pp. 1064–1068.

J. A. Conchello, J. G. McNally, “Fast regularization technique for expectation maximization algorithm for computational optical sectioning microscopy,” in Three-Dimensional and Multidimensional Microscopy: Image Acquisition and Processing, C. J. Cogswell, G. S. Kino, T. Wilson, eds., Proc. SPIE2655, 199–208 (1996).
[CrossRef]

J. A. Fessler, H. Erdoğan, “A paraboloidal surrogates algorithm for convergent penalized-likelihood emission image reconstruction,” in Proceedings of the IEEE Nuclear Science Symposium and Medical Imaging Conference (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 1132–1135.

J. C. D. de Melo, “Partial FFT Evaluation,” in International Conference on Signal Processing Application and Technology (1996), Vol. 1, pp. 134–141, available at http://www.icspat.com/papers/234amfi.pdf .

S. K. Mitra, Digital Signal Processing: A Computer-Based Approach, 2nd ed. (McGraw-Hill, New York, 2001).

The XCOSM deconvolution package (online). Available at http://3dmicroscopy.wustl.edu/∼xcosm/ .

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

Fig. 1
Fig. 1

Illustration of how the OS algorithms work. Assume that Φ(x)=f1(x)+f2(x). When x is far from the solution, the subset-gradient-balance conditions hold, and an order-of-magnitude acceleration can be achieved in the early iterations. However, for later iterations or when x is near the optimal solution, those conditions are no longer valid, and a limit-cycle behavior is observed.

Fig. 2
Fig. 2

Possible choices for four subsets with a downsampling approach. These subsets tend to satisfy the subset-gradient-balance conditions. The first number in quotation marks is the number of subsets in each column, and the second number is the number of subsets in each row. The total number of subsets is the product of these two numbers. The pixel label m belongs to the respective set Sm.

Fig. 3
Fig. 3

Investigation of the subset-gradient-balance conditions in the OS-SPS algorithm. Four subsets with a 2×2 configuration were used. The second and third columns show the gradients of the subobjective functions from the downsampling approach with use of subset 1 and subset 4, respectively, and their differences compared with the gradient of the objective function. Similarly, the last two columns are from the subblock approach. The gradients of the subobjective functions in the downsampling approach were multiplied by 4 to compensate for the downsampled data. However, this scaling factor is not needed in the subblock approach, because a block of contiguous pixels is used.

Fig. 4
Fig. 4

Possible choices for four subsets with a subblock approach. These subsets tend to violate the subset-gradient-balance conditions. The first number in quotation marks is the number of subblocks in each column, and the second number is the number of subblocks in each row.

Fig. 5
Fig. 5

Illustration of computing lˆi, iSm (M=2), using all the information of x and h. The asterisk represents convolution. The white blocks denote elements of x belonging to subset m=1, and the striped blocks denote elements of x belonging to subset m=2. The patterns in h indicate the symmetry of the PSF that has the center in the middle.

Fig. 6
Fig. 6

Illustration of computing L˙j, j (M=2), using some information of ψ˙i but all the information of h.

Fig. 7
Fig. 7

Simulated images and restoration using the relaxed OS-SPS algorithm with β=10-6 and δ=100. The PSF in the noisy blurry image was simulated from the 2D PSF of the confocal microscope only in the xz direction, where x is along the horizontal axis and z is along the vertical axis, to show elongation in the z direction. This elongation disappears in the restored image.

Fig. 8
Fig. 8

Comparison of objective function increases of DPEM, SPS, OS-SPS, and relaxed OS-SPS algorithms. OS-SPS-8 stands for the OS-SPS algorithm with eight subsets. Both nonrelaxed and relaxed OS-SPS algorithms have order-of-magnitude acceleration over the DPEM and SPS algorithms.

Fig. 9
Fig. 9

Comparison of objective function increase versus elapsed time of relaxed OS-SPS with different numbers of subsets. The 16-subset relaxed OS-SPS algorithm yielded the fastest convergence rate.

Fig. 10
Fig. 10

Comparison of different choices of subsets with use of the relaxed OS-SPS algorithm. The subset unbalance of relaxed OS-SPS with the subblock approach causes an unpredictable behavior of the objective function increase at the beginning of iterations, but the algorithm eventually converges as a result of relaxation. The relaxed OS-SPS algorithms with the downsampling approach converge at almost the same rate for different choices of subsets.

Tables (2)

Tables Icon

Table 1 Multiplication Complexity Ratio for Computing lˆi (with Use of FFTs) of OS-SPS and non-OS Algorithms with Different Numbers of Subsets

Tables Icon

Table 2 Comparison of Elapsed Times per Iteration and Number of FLOPs for DPEM, SPS, and OS-SPS Algorithms

Equations (42)

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

Φ(x)=L(x)-βR(x),
YiPoission{[Ax]i+bi},i=1,, N,
L(x)=i=1Nψi(li(x)),
R(x)=i=1rψR([Cx]i),
Cx=-110000-11-10100-101x1x2x3x4=x2-x1x4-x3x3-x1x4-x2
xˆarg maxx0Φ(x).
Φ(x)=m=1Mfm(x),
fm(x)iSmψi(li(x))-βMR(x).
f1(x)f2(x)fm(x),
Φ(x)Mfm(x),m=1,,M.
xjn+1=xjn+jΦ(xn)i=1Naijγicin+βpjn+,
jΦ(x)=xjΦ(x)=i=1Naijψ˙i(li(x))-βi=1rcijψ˙R([Cx]i),
cin=2(lin)2[ψi(lin)-ψi(0)-linψ˙i(lin)]+,lin>0[-ψ¨i(0)]+,lin=0,
pjn=i=1rcijνiω([Cxn]i),
xi(n, m)=xj(n, m-1)+Mjfm(x(n,m-1))dj+βpj+,  m=1,, M,
jfm(x)=iSmaijψ˙i(li(x))-βMi=1rcijψ˙R([Cx]i).
dj=i=1Naijγici,
pj=i=1rcijνiω(0).
xj(n,m)=xj(n,m-1)+αnMjfm(x(n,m-1))dj+βpj+,  m=1,, M.
x(n,m)={x(n,m-1)+αnDfm[x(n,m-1)]}+,
dj=-i=1Naijγiψ¨i(yi-bi),
pj=i=1rcijνiω(0),
αn=ξ(ξ-1)+n
lˆi=j=1Paijxj(n,m-1),iSm
ψ˙i=yilˆi+bi-1,iSm
forj=1,, P
L˙j=iSmaijψ˙i
R˙j=i=1rcijψ˙R([Cx(n,m-1)]i)
xj(n,m)=xj(n,m-1)+αnML˙j-βMR˙jdj+βpj+
lˆi=j=1Phi-jxj,iSm,
lˆi=m=1MjSmhi-jxj,iSm.
L˙j=iSmhi-jψ˙i.
lˆ(η)=1Nk=0N-1H(k)X(k)expj2πηkN,ηSm.
lˆ(2η)=1Nk=0N/2-1[H(k)X(k)+H(k+N/2)X(k+N/2)]×expj2πηkN/2.
lˆ(2η+1)=1Nk=0N/2-1[H(k)X(k)-H(k+N/2)X(k+N/2)]expj2πkNexpj2πηkN/2.
MN2log2 N+MN+N(M-1)M+N2log2NM.
L˙(η)=1Nk=0N-1H(k)Ψ(k)expj2πηkN,η.
H(k)=η=0N/2-1h(2η)exp-j2πηkN/2=H(k+N/2),
Ψ(k)=η=0N/2-1ψ˙(2η)exp-j2πηkN/2=Ψ(k+N/2).
H(k)=exp-j2πkNη=0N/2-1h(2η+1)exp-j2πηkN/2=-H(k+N/2),
Ψ(k)=exp-j2πkNη=0N/2-1ψ˙(2η+1)exp-j2πηkN/2=-Ψ(k+N/2).
PSNR=10 log10maxi(yi-bi)21Ni=1N(yi-E[yi])2.

Metrics