Abstract

The problem of reconstructing a binary image from undersampled Fourier amplitude data is considered. This problem maps to an image reconstruction problem in x-ray crystallography. The binary constraint is sufficient to overcome the undersampling and enforce uniqueness, but is insufficient in the case of the additional loss of data that can occur in practice. An iterative projection algorithm is developed that uses binary, connectivity, and compactness constraints to solve the image reconstruction problem. Simulations show the utility of the reconstruction algorithm.

© 2008 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. R. P. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A 7, 394-411 (1990).
    [CrossRef]
  2. J. C. Dainty and J. R. Fienup, “Phase retrieval and image reconstruction for astronomy,” in Image Recovery: Theory and Application, H.Stark, ed. (Academic, 1987), pp. 231-275.
  3. M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature (London) 442, 63-66 (2006).
    [CrossRef]
  4. H. N. Chapman, A. Barty, S. Marchesini, A. Noy, S. R. Hau-Riege, C. Cui, M. R. Howells, R. Rosen, H. He, J. C. H. Spence, U. Weierstall, T. Beetz, C. Jacobsen, and D. Shapiro, “High-resolution ab initio three-dimensional x-ray diffraction microscopy,” J. Opt. Soc. Am. A 23, 1179-1200 (2006).
    [CrossRef]
  5. P. Thibault, V. Elser, C. Jacobsen, D. Shapiro, and D. Sayre, “Reconstruction of a yeast cell from X-ray diffraction data,” Acta Crystallogr. 62, 248-261 (2006).
    [CrossRef]
  6. R. H. T. Bates, “Uniqueness of solutions of two-dimensional Fourier phase problems for localized and positive images,” Comput. Vis. Graph. Image Process. 2, 205-217 (1984).
    [CrossRef]
  7. R. W. Gerchberg and W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237-246 (1972).
  8. J. R. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. 21, 2758-2769 (1982).
    [CrossRef] [PubMed]
  9. A. Levi and H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A 1, 932-943 (1984).
    [CrossRef]
  10. V. Elser, “Phase retrieval by iterated projections,” J. Opt. Soc. Am. A 20, 40-55 (2003).
    [CrossRef]
  11. R. P. Millane, “Iterative projection algorithms for solving inverse problems,” in Proc. Oceans 2003 (IEEE, 2003), CD-ROM, pp. 2714-2719.
  12. D. R. Luke, “Relaxed averaged alternating reflections for diffraction imaging,” Inverse Probl. 21, 37-50 (2005).
    [CrossRef]
  13. J. Drenth, Principles of X-ray Crystallography (Springer-Verlag, 1994).
  14. C. W. Carter, K. V. Crumley, D. E. Coleman, F. Hage, and G. Bricogne, “Direct phase determination for the molecular envelope of tryptophanyl-tRNA synthetase from Bacillus stearothermophilus by x-ray contrast variation,” Acta Crystallogr. 46, 57-68 (1990).
    [CrossRef]
  15. R. Fourme, W. Shepard, R. Kahn, G. l'Hermite, and I. L. de La Sierra, “The multiwavelength anomalous solvent contrast (MASC) method in macromolecular crystallography,” J. Synchrotron Radiat. 2, 36-48 (1995).
    [CrossRef] [PubMed]
  16. R. P. Millane and W. J. Stroud, “Reconstructing symmetric images from their undersampled Fourier intensities,” J. Opt. Soc. Am. A 14, 568-579 (1997).
    [CrossRef]
  17. V. Elser, I. Rankenburg, and P. Thibault, “Searching with iterated maps,” Proc. Natl. Acad. Sci. U.S.A. 104, 418-423 (2007).
    [CrossRef] [PubMed]
  18. V. Elser and R. P. Millane, “Reconstruction of an object from its symmetry-averaged diffraction pattern,” Acta Crystallogr. 64, 273-279 (2008).
    [CrossRef]

2008 (1)

V. Elser and R. P. Millane, “Reconstruction of an object from its symmetry-averaged diffraction pattern,” Acta Crystallogr. 64, 273-279 (2008).
[CrossRef]

2007 (1)

V. Elser, I. Rankenburg, and P. Thibault, “Searching with iterated maps,” Proc. Natl. Acad. Sci. U.S.A. 104, 418-423 (2007).
[CrossRef] [PubMed]

2006 (3)

M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature (London) 442, 63-66 (2006).
[CrossRef]

H. N. Chapman, A. Barty, S. Marchesini, A. Noy, S. R. Hau-Riege, C. Cui, M. R. Howells, R. Rosen, H. He, J. C. H. Spence, U. Weierstall, T. Beetz, C. Jacobsen, and D. Shapiro, “High-resolution ab initio three-dimensional x-ray diffraction microscopy,” J. Opt. Soc. Am. A 23, 1179-1200 (2006).
[CrossRef]

P. Thibault, V. Elser, C. Jacobsen, D. Shapiro, and D. Sayre, “Reconstruction of a yeast cell from X-ray diffraction data,” Acta Crystallogr. 62, 248-261 (2006).
[CrossRef]

2005 (1)

D. R. Luke, “Relaxed averaged alternating reflections for diffraction imaging,” Inverse Probl. 21, 37-50 (2005).
[CrossRef]

2003 (1)

1997 (1)

1995 (1)

R. Fourme, W. Shepard, R. Kahn, G. l'Hermite, and I. L. de La Sierra, “The multiwavelength anomalous solvent contrast (MASC) method in macromolecular crystallography,” J. Synchrotron Radiat. 2, 36-48 (1995).
[CrossRef] [PubMed]

1990 (2)

C. W. Carter, K. V. Crumley, D. E. Coleman, F. Hage, and G. Bricogne, “Direct phase determination for the molecular envelope of tryptophanyl-tRNA synthetase from Bacillus stearothermophilus by x-ray contrast variation,” Acta Crystallogr. 46, 57-68 (1990).
[CrossRef]

R. P. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A 7, 394-411 (1990).
[CrossRef]

1984 (2)

A. Levi and H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A 1, 932-943 (1984).
[CrossRef]

R. H. T. Bates, “Uniqueness of solutions of two-dimensional Fourier phase problems for localized and positive images,” Comput. Vis. Graph. Image Process. 2, 205-217 (1984).
[CrossRef]

1982 (1)

1972 (1)

R. W. Gerchberg and W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237-246 (1972).

Barty, A.

Bates, R. H. T.

R. H. T. Bates, “Uniqueness of solutions of two-dimensional Fourier phase problems for localized and positive images,” Comput. Vis. Graph. Image Process. 2, 205-217 (1984).
[CrossRef]

Beetz, T.

Bricogne, G.

C. W. Carter, K. V. Crumley, D. E. Coleman, F. Hage, and G. Bricogne, “Direct phase determination for the molecular envelope of tryptophanyl-tRNA synthetase from Bacillus stearothermophilus by x-ray contrast variation,” Acta Crystallogr. 46, 57-68 (1990).
[CrossRef]

Carter, C. W.

C. W. Carter, K. V. Crumley, D. E. Coleman, F. Hage, and G. Bricogne, “Direct phase determination for the molecular envelope of tryptophanyl-tRNA synthetase from Bacillus stearothermophilus by x-ray contrast variation,” Acta Crystallogr. 46, 57-68 (1990).
[CrossRef]

Chapman, H. N.

Coleman, D. E.

C. W. Carter, K. V. Crumley, D. E. Coleman, F. Hage, and G. Bricogne, “Direct phase determination for the molecular envelope of tryptophanyl-tRNA synthetase from Bacillus stearothermophilus by x-ray contrast variation,” Acta Crystallogr. 46, 57-68 (1990).
[CrossRef]

Crumley, K. V.

C. W. Carter, K. V. Crumley, D. E. Coleman, F. Hage, and G. Bricogne, “Direct phase determination for the molecular envelope of tryptophanyl-tRNA synthetase from Bacillus stearothermophilus by x-ray contrast variation,” Acta Crystallogr. 46, 57-68 (1990).
[CrossRef]

Cui, C.

Dainty, J. C.

J. C. Dainty and J. R. Fienup, “Phase retrieval and image reconstruction for astronomy,” in Image Recovery: Theory and Application, H.Stark, ed. (Academic, 1987), pp. 231-275.

de La Sierra, I. L.

R. Fourme, W. Shepard, R. Kahn, G. l'Hermite, and I. L. de La Sierra, “The multiwavelength anomalous solvent contrast (MASC) method in macromolecular crystallography,” J. Synchrotron Radiat. 2, 36-48 (1995).
[CrossRef] [PubMed]

Drenth, J.

J. Drenth, Principles of X-ray Crystallography (Springer-Verlag, 1994).

Elser, V.

V. Elser and R. P. Millane, “Reconstruction of an object from its symmetry-averaged diffraction pattern,” Acta Crystallogr. 64, 273-279 (2008).
[CrossRef]

V. Elser, I. Rankenburg, and P. Thibault, “Searching with iterated maps,” Proc. Natl. Acad. Sci. U.S.A. 104, 418-423 (2007).
[CrossRef] [PubMed]

P. Thibault, V. Elser, C. Jacobsen, D. Shapiro, and D. Sayre, “Reconstruction of a yeast cell from X-ray diffraction data,” Acta Crystallogr. 62, 248-261 (2006).
[CrossRef]

V. Elser, “Phase retrieval by iterated projections,” J. Opt. Soc. Am. A 20, 40-55 (2003).
[CrossRef]

Fienup, J. R.

J. R. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. 21, 2758-2769 (1982).
[CrossRef] [PubMed]

J. C. Dainty and J. R. Fienup, “Phase retrieval and image reconstruction for astronomy,” in Image Recovery: Theory and Application, H.Stark, ed. (Academic, 1987), pp. 231-275.

Fourme, R.

R. Fourme, W. Shepard, R. Kahn, G. l'Hermite, and I. L. de La Sierra, “The multiwavelength anomalous solvent contrast (MASC) method in macromolecular crystallography,” J. Synchrotron Radiat. 2, 36-48 (1995).
[CrossRef] [PubMed]

Gerchberg, R. W.

R. W. Gerchberg and W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237-246 (1972).

Hage, F.

C. W. Carter, K. V. Crumley, D. E. Coleman, F. Hage, and G. Bricogne, “Direct phase determination for the molecular envelope of tryptophanyl-tRNA synthetase from Bacillus stearothermophilus by x-ray contrast variation,” Acta Crystallogr. 46, 57-68 (1990).
[CrossRef]

Harder, R.

M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature (London) 442, 63-66 (2006).
[CrossRef]

Hau-Riege, S. R.

He, H.

Howells, M. R.

Jacobsen, C.

Kahn, R.

R. Fourme, W. Shepard, R. Kahn, G. l'Hermite, and I. L. de La Sierra, “The multiwavelength anomalous solvent contrast (MASC) method in macromolecular crystallography,” J. Synchrotron Radiat. 2, 36-48 (1995).
[CrossRef] [PubMed]

Levi, A.

l'Hermite, G.

R. Fourme, W. Shepard, R. Kahn, G. l'Hermite, and I. L. de La Sierra, “The multiwavelength anomalous solvent contrast (MASC) method in macromolecular crystallography,” J. Synchrotron Radiat. 2, 36-48 (1995).
[CrossRef] [PubMed]

Luke, D. R.

D. R. Luke, “Relaxed averaged alternating reflections for diffraction imaging,” Inverse Probl. 21, 37-50 (2005).
[CrossRef]

Marchesini, S.

Millane, R. P.

V. Elser and R. P. Millane, “Reconstruction of an object from its symmetry-averaged diffraction pattern,” Acta Crystallogr. 64, 273-279 (2008).
[CrossRef]

R. P. Millane and W. J. Stroud, “Reconstructing symmetric images from their undersampled Fourier intensities,” J. Opt. Soc. Am. A 14, 568-579 (1997).
[CrossRef]

R. P. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A 7, 394-411 (1990).
[CrossRef]

R. P. Millane, “Iterative projection algorithms for solving inverse problems,” in Proc. Oceans 2003 (IEEE, 2003), CD-ROM, pp. 2714-2719.

Noy, A.

Pfeifer, M. A.

M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature (London) 442, 63-66 (2006).
[CrossRef]

Rankenburg, I.

V. Elser, I. Rankenburg, and P. Thibault, “Searching with iterated maps,” Proc. Natl. Acad. Sci. U.S.A. 104, 418-423 (2007).
[CrossRef] [PubMed]

Robinson, I. K.

M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature (London) 442, 63-66 (2006).
[CrossRef]

Rosen, R.

Saxton, W. O.

R. W. Gerchberg and W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237-246 (1972).

Sayre, D.

P. Thibault, V. Elser, C. Jacobsen, D. Shapiro, and D. Sayre, “Reconstruction of a yeast cell from X-ray diffraction data,” Acta Crystallogr. 62, 248-261 (2006).
[CrossRef]

Shapiro, D.

Shepard, W.

R. Fourme, W. Shepard, R. Kahn, G. l'Hermite, and I. L. de La Sierra, “The multiwavelength anomalous solvent contrast (MASC) method in macromolecular crystallography,” J. Synchrotron Radiat. 2, 36-48 (1995).
[CrossRef] [PubMed]

Spence, J. C. H.

Stark, H.

Stroud, W. J.

Thibault, P.

V. Elser, I. Rankenburg, and P. Thibault, “Searching with iterated maps,” Proc. Natl. Acad. Sci. U.S.A. 104, 418-423 (2007).
[CrossRef] [PubMed]

P. Thibault, V. Elser, C. Jacobsen, D. Shapiro, and D. Sayre, “Reconstruction of a yeast cell from X-ray diffraction data,” Acta Crystallogr. 62, 248-261 (2006).
[CrossRef]

Vartanyants, I. A.

M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature (London) 442, 63-66 (2006).
[CrossRef]

Weierstall, U.

Williams, G. J.

M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature (London) 442, 63-66 (2006).
[CrossRef]

Acta Crystallogr. (3)

P. Thibault, V. Elser, C. Jacobsen, D. Shapiro, and D. Sayre, “Reconstruction of a yeast cell from X-ray diffraction data,” Acta Crystallogr. 62, 248-261 (2006).
[CrossRef]

C. W. Carter, K. V. Crumley, D. E. Coleman, F. Hage, and G. Bricogne, “Direct phase determination for the molecular envelope of tryptophanyl-tRNA synthetase from Bacillus stearothermophilus by x-ray contrast variation,” Acta Crystallogr. 46, 57-68 (1990).
[CrossRef]

V. Elser and R. P. Millane, “Reconstruction of an object from its symmetry-averaged diffraction pattern,” Acta Crystallogr. 64, 273-279 (2008).
[CrossRef]

Appl. Opt. (1)

Comput. Vis. Graph. Image Process. (1)

R. H. T. Bates, “Uniqueness of solutions of two-dimensional Fourier phase problems for localized and positive images,” Comput. Vis. Graph. Image Process. 2, 205-217 (1984).
[CrossRef]

Inverse Probl. (1)

D. R. Luke, “Relaxed averaged alternating reflections for diffraction imaging,” Inverse Probl. 21, 37-50 (2005).
[CrossRef]

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

J. Synchrotron Radiat. (1)

R. Fourme, W. Shepard, R. Kahn, G. l'Hermite, and I. L. de La Sierra, “The multiwavelength anomalous solvent contrast (MASC) method in macromolecular crystallography,” J. Synchrotron Radiat. 2, 36-48 (1995).
[CrossRef] [PubMed]

Nature (London) (1)

M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature (London) 442, 63-66 (2006).
[CrossRef]

Optik (Stuttgart) (1)

R. W. Gerchberg and W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237-246 (1972).

Proc. Natl. Acad. Sci. U.S.A. (1)

V. Elser, I. Rankenburg, and P. Thibault, “Searching with iterated maps,” Proc. Natl. Acad. Sci. U.S.A. 104, 418-423 (2007).
[CrossRef] [PubMed]

Other (3)

J. Drenth, Principles of X-ray Crystallography (Springer-Verlag, 1994).

J. C. Dainty and J. R. Fienup, “Phase retrieval and image reconstruction for astronomy,” in Image Recovery: Theory and Application, H.Stark, ed. (Academic, 1987), pp. 231-275.

R. P. Millane, “Iterative projection algorithms for solving inverse problems,” in Proc. Oceans 2003 (IEEE, 2003), CD-ROM, pp. 2714-2719.

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

(a) Connected image, and (b) an image connected between unit cells.

Fig. 2
Fig. 2

(a) Binary image and (b) the result of applying a rigorous connectivity projection.

Fig. 3
Fig. 3

Illustration of application of the image space constraints. (a) x, (b) P B F x , (c) P C P B F x , and (d) P I x .

Fig. 4
Fig. 4

Original images are shown in the top row: Image A (left), Image B (center), and Image C (right). Reconstructions with limited, noise-free data are shown in the middle row, and with limited, noisy data in the bottom row.

Fig. 5
Fig. 5

Error metrics E n and Δ n versus iteration n for image B with f = 0.4 , for (a) limited, noise-free Fourier amplitude data, and (b) limited noisy Fourier amplitude data.

Fig. 6
Fig. 6

Fourier amplitude error versus iteration showing the effect of inverting the image as described in the text.

Equations (22)

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

y = K x ,
B = { x : y = K x } .
P A x = argmin x A x x .
x n + 1 = P B P A x n .
T A x = λ P A x + ( 1 λ ) x ,
x n + 1 = x n + β [ P A T B x P B T A x ] ,
X = F [ x ] ,
M = { x : X j = M j , j Q } .
B = { x : x j ( 0 , 1 ) , j = 1 , 2 , , N } ,
F = { x B : j = 1 N x j = f N } .
P M x = F 1 [ P ̃ M F [ x ] ] ,
P ̃ M X j = { M j exp ( i ϕ ( X j ) ) if j Q X j if Q } ,
P B x j = { 0 if x j < 1 2 1 if x j > 1 2 } ,
P B F x j = { 0 if x j S ( f ) 1 if x j S ( f ) } ,
P C x j = { 1 if j L ( l ) 0 if j L ( l ) } ,
P S C x = 1 P C ( 1 x ) .
P I x = P S C P C P B F x .
E n = j Q ( X j M j ) 2 j Q M j 2
Δ n = x n x n 1 x n
e = x s x t x t ,
g = 1 x .
G j = { X j if j 1 ( 1 f f ) X 1 if j = 1 } ,

Metrics