Abstract

We describe a fast and accurate direct Fourier method for reconstructing a function f of three variables from a number of its parallel beam projections. The main application of our method is in single particle analysis, where the goal is to reconstruct the mass density of a biological macromolecule. Typically, the number of projections is extremely large, and each projection is extremely noisy. The projection directions are random and initially unknown. However, it is possible to determine both the directions and f by an iterative procedure; during each stage of the iteration, one has to solve a reconstruction problem of the type considered here. Our reconstruction algorithm is distinguished from other direct Fourier methods by the use of gridding techniques that provide an efficient means to compute a uniformly sampled version of a function g from a nonuniformly sampled version of Fg, the Fourier transform of g, or vice versa. We apply the two-dimensional reverse gridding method to each available projection of f, the function to be reconstructed, in order to obtain Ff on a special spherical grid. Then we use the three-dimensional gridding method to reconstruct f from this sampled version of Ff. This stage requires a proper weighting of the samples of Ff to compensate for their nonuniform distribution. We use a fast method for computing appropriate weights that exploits the special properties of the spherical sampling grid for Ff and involves the computation of a Voronoi diagram on the unit sphere. We demonstrate the excellent speed and accuracy of our method by using simulated data.

© 2004 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. Frank, Three-Dimensional Electron Microscopy of Macromolecular Assemblies (Academic, New York, 1996).
  2. R. H. Wade, “A brief look at imaging and contrast transfer,” Ultramicroscopy 46, 145–156 (1992).
    [CrossRef]
  3. P. A. Penczek, R. A. Grassucci, J. Frank, “The ribosome at improved resolution: new techniques for merging and orientation refinement in 3D cryo-electron microscopy of biological particles,” Ultramicroscopy 53, 251–270 (1994).
    [CrossRef] [PubMed]
  4. P. Penczek, M. Radermacher, J. Frank, “Three-dimensional reconstruction of single particles embedded in ice,” Ultramicroscopy 40, 33–53 (1992).
    [CrossRef] [PubMed]
  5. R. Marabini, G. T. Herman, J. M. Carazo, “3D reconstruction in electron microscopy using ART with smooth spherically symmetric volume elements (blobs),” Ultramicroscopy 72, 53–65 (1998).
    [CrossRef] [PubMed]
  6. M. Radermacher, “Weighted back-projection methods,” in Electron Tomography, J. Frank, ed. (Plenum, New York, 1992), pp. 91–115.
  7. N. Grigorieff, “Three-dimensional structure of bovine NADH: ubiquinone oxidoreductase (complex I) at 22 Å in ice,” J. Mol. Biol. 277, 1033–1046 (1998).
    [CrossRef] [PubMed]
  8. S. Lanzavecchia, P. L. Bellon, V. Scatturin, “SPARK, a kernel software programs for spatial reconstruction in electron microscopy,” J. Microsc. (Oxford) 171, 255–266 (1993).
    [CrossRef]
  9. S. Lanzavecchia, P. L. Bellon, M. Radermacher, “Fast and accurate three-dimensional reconstruction from projections with random orientations via Radon transforms,” J. Struct. Biol. 128, 152–164 (1999).
    [CrossRef] [PubMed]
  10. S. Lanzavecchia, P. L. Bellon, “Electron tomography in conical tilt geometry. The accuracy of a direct Fourier method (DFM) and the suppression of non-tomographic noise,” Ultramicroscopy 63, 247–261 (1996).
    [CrossRef]
  11. J. D. O’Sullivan, “A fast sinc-function gridding algorithm for Fourier inversion in computer tomography,” IEEE Trans. Med. Imaging MI-4, 200–207 (1985).
    [CrossRef]
  12. J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
    [CrossRef]
  13. H. Schomberg, J. Timmer, “The gridding method for im-age reconstruction by Fourier transformation,” IEEE Trans. Med. Imaging 14, 596–607 (1995).
    [CrossRef]
  14. V. Rasche, R. Proksa, R. Sinkus, P. Börnert, H. Eggers, “Resampling of data between arbitrary grids using convolution interpolation,” IEEE Trans. Med. Imaging 18, 385–392 (1999).
    [CrossRef] [PubMed]
  15. R. J. Renka, “Algorithm 772. STRIPACK: Delaunay triangulation and Voronoi diagram on the surface of a sphere,” ACM (Assoc. Comput. Mach.) Trans. Math. Softw. 23, 416–434 (1997).
    [CrossRef]
  16. F. Natterer, F. Wübbeling, Mathematical Methods in Image Reconstruction (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 2001).
  17. W. N. Brouw, “Aperture synthesis,” in Methods in Computational Physics, B. Alder, S. Fernbach, M. Rotenberg, eds. (Academic, New York, 1975), pp. 131–175.
  18. H. Schomberg, “Notes on direct and gridding-based Fourier inversion methods,” in Proceedings of the IEEE International Symposium on Biomedical Imaging, M. Unser, Z. P. Liang, eds. (Institute of Electrical and Electronics Engineers, New York, 2002), pp. 645–648.
  19. A. Okabe, B. Boots, K. Sugihara, S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (Wiley, New York, 2000).
  20. A. Dutt, V. Rokhlin, “Fast Fourier transform for nonequispaced data,” SIAM (Soc. Ind. Appl. Math.) J. Sci. Stat. Comput. 14, 1368–1393 (1993).
    [CrossRef]
  21. G. Beylkin, “On the fast Fourier transform of functions with singularities,” Appl. Comput. Harmon. Anal. 2, 363–381 (1995).
    [CrossRef]
  22. D. Potts, G. Steidl, “New Fourier reconstruction algorithms for computerized tomography,” in Wavelet Applications in Signal and Image Processing VIII, A. Aldroubi, A. F. Laine, M. A. Unser, eds. (SPIE, Bellingham, Wash., 2000), pp. 13–23.
  23. D. Zwillinger, CRC Standard Mathematical Tables and Formulae (CRC Press, Boca Raton, Fla., 2002).
  24. S. S. Orlov, “Theory of three-dimensional reconstruction. 1. Conditions of a complete set of projections,” Sov. Phys. Crystallogr. 20, 312–314 (1976).
  25. J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
    [CrossRef] [PubMed]
  26. I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
    [CrossRef] [PubMed]
  27. M. Radermacher, T. Wagenknecht, A. Verschoor, J. Frank, “A new 3-D reconstruction scheme applied to the 50S ribosomal subunit of E. coli,” J. Microsc. (Oxford) 141, RP1–RP2 (1986).
    [CrossRef]
  28. G. Harauz, M. van Heel, “Exact filters for general geometry three dimensional reconstruction,” Optik (Stuttgart) 73, 146–156 (1986).
  29. R. Chandra, D. Kohr, D. Maydan, L. Dagum, J. McDonald, R. Menom, Parallel Programming in OpenMP (Academic, Boston, 2000).
  30. W. O. Saxton, W. Baumeister, “The correlation averaging of a regularly arranged bacterial envelope protein,” J. Microsc. (Oxford) 127, 127–138 (1982).
    [CrossRef]
  31. P. A. Penczek, “Three-dimensional spectral signal-to-noise ratio for a class of reconstruction algorithms,” J. Struct. Biol. 138, 34–46 (2002).
    [CrossRef] [PubMed]

2002

P. A. Penczek, “Three-dimensional spectral signal-to-noise ratio for a class of reconstruction algorithms,” J. Struct. Biol. 138, 34–46 (2002).
[CrossRef] [PubMed]

2000

I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
[CrossRef] [PubMed]

1999

V. Rasche, R. Proksa, R. Sinkus, P. Börnert, H. Eggers, “Resampling of data between arbitrary grids using convolution interpolation,” IEEE Trans. Med. Imaging 18, 385–392 (1999).
[CrossRef] [PubMed]

S. Lanzavecchia, P. L. Bellon, M. Radermacher, “Fast and accurate three-dimensional reconstruction from projections with random orientations via Radon transforms,” J. Struct. Biol. 128, 152–164 (1999).
[CrossRef] [PubMed]

1998

R. Marabini, G. T. Herman, J. M. Carazo, “3D reconstruction in electron microscopy using ART with smooth spherically symmetric volume elements (blobs),” Ultramicroscopy 72, 53–65 (1998).
[CrossRef] [PubMed]

N. Grigorieff, “Three-dimensional structure of bovine NADH: ubiquinone oxidoreductase (complex I) at 22 Å in ice,” J. Mol. Biol. 277, 1033–1046 (1998).
[CrossRef] [PubMed]

1997

R. J. Renka, “Algorithm 772. STRIPACK: Delaunay triangulation and Voronoi diagram on the surface of a sphere,” ACM (Assoc. Comput. Mach.) Trans. Math. Softw. 23, 416–434 (1997).
[CrossRef]

1996

S. Lanzavecchia, P. L. Bellon, “Electron tomography in conical tilt geometry. The accuracy of a direct Fourier method (DFM) and the suppression of non-tomographic noise,” Ultramicroscopy 63, 247–261 (1996).
[CrossRef]

J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
[CrossRef] [PubMed]

1995

H. Schomberg, J. Timmer, “The gridding method for im-age reconstruction by Fourier transformation,” IEEE Trans. Med. Imaging 14, 596–607 (1995).
[CrossRef]

G. Beylkin, “On the fast Fourier transform of functions with singularities,” Appl. Comput. Harmon. Anal. 2, 363–381 (1995).
[CrossRef]

1994

P. A. Penczek, R. A. Grassucci, J. Frank, “The ribosome at improved resolution: new techniques for merging and orientation refinement in 3D cryo-electron microscopy of biological particles,” Ultramicroscopy 53, 251–270 (1994).
[CrossRef] [PubMed]

1993

S. Lanzavecchia, P. L. Bellon, V. Scatturin, “SPARK, a kernel software programs for spatial reconstruction in electron microscopy,” J. Microsc. (Oxford) 171, 255–266 (1993).
[CrossRef]

A. Dutt, V. Rokhlin, “Fast Fourier transform for nonequispaced data,” SIAM (Soc. Ind. Appl. Math.) J. Sci. Stat. Comput. 14, 1368–1393 (1993).
[CrossRef]

1992

P. Penczek, M. Radermacher, J. Frank, “Three-dimensional reconstruction of single particles embedded in ice,” Ultramicroscopy 40, 33–53 (1992).
[CrossRef] [PubMed]

R. H. Wade, “A brief look at imaging and contrast transfer,” Ultramicroscopy 46, 145–156 (1992).
[CrossRef]

1991

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

1986

M. Radermacher, T. Wagenknecht, A. Verschoor, J. Frank, “A new 3-D reconstruction scheme applied to the 50S ribosomal subunit of E. coli,” J. Microsc. (Oxford) 141, RP1–RP2 (1986).
[CrossRef]

G. Harauz, M. van Heel, “Exact filters for general geometry three dimensional reconstruction,” Optik (Stuttgart) 73, 146–156 (1986).

1985

J. D. O’Sullivan, “A fast sinc-function gridding algorithm for Fourier inversion in computer tomography,” IEEE Trans. Med. Imaging MI-4, 200–207 (1985).
[CrossRef]

1982

W. O. Saxton, W. Baumeister, “The correlation averaging of a regularly arranged bacterial envelope protein,” J. Microsc. (Oxford) 127, 127–138 (1982).
[CrossRef]

1976

S. S. Orlov, “Theory of three-dimensional reconstruction. 1. Conditions of a complete set of projections,” Sov. Phys. Crystallogr. 20, 312–314 (1976).

Agrawal, R. K.

I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
[CrossRef] [PubMed]

Baumeister, W.

W. O. Saxton, W. Baumeister, “The correlation averaging of a regularly arranged bacterial envelope protein,” J. Microsc. (Oxford) 127, 127–138 (1982).
[CrossRef]

Bellon, P. L.

S. Lanzavecchia, P. L. Bellon, M. Radermacher, “Fast and accurate three-dimensional reconstruction from projections with random orientations via Radon transforms,” J. Struct. Biol. 128, 152–164 (1999).
[CrossRef] [PubMed]

S. Lanzavecchia, P. L. Bellon, “Electron tomography in conical tilt geometry. The accuracy of a direct Fourier method (DFM) and the suppression of non-tomographic noise,” Ultramicroscopy 63, 247–261 (1996).
[CrossRef]

S. Lanzavecchia, P. L. Bellon, V. Scatturin, “SPARK, a kernel software programs for spatial reconstruction in electron microscopy,” J. Microsc. (Oxford) 171, 255–266 (1993).
[CrossRef]

Beylkin, G.

G. Beylkin, “On the fast Fourier transform of functions with singularities,” Appl. Comput. Harmon. Anal. 2, 363–381 (1995).
[CrossRef]

Boots, B.

A. Okabe, B. Boots, K. Sugihara, S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (Wiley, New York, 2000).

Börnert, P.

V. Rasche, R. Proksa, R. Sinkus, P. Börnert, H. Eggers, “Resampling of data between arbitrary grids using convolution interpolation,” IEEE Trans. Med. Imaging 18, 385–392 (1999).
[CrossRef] [PubMed]

Brouw, W. N.

W. N. Brouw, “Aperture synthesis,” in Methods in Computational Physics, B. Alder, S. Fernbach, M. Rotenberg, eds. (Academic, New York, 1975), pp. 131–175.

Carazo, J. M.

R. Marabini, G. T. Herman, J. M. Carazo, “3D reconstruction in electron microscopy using ART with smooth spherically symmetric volume elements (blobs),” Ultramicroscopy 72, 53–65 (1998).
[CrossRef] [PubMed]

Chandra, R.

R. Chandra, D. Kohr, D. Maydan, L. Dagum, J. McDonald, R. Menom, Parallel Programming in OpenMP (Academic, Boston, 2000).

Chiu, S. N.

A. Okabe, B. Boots, K. Sugihara, S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (Wiley, New York, 2000).

Dagum, L.

R. Chandra, D. Kohr, D. Maydan, L. Dagum, J. McDonald, R. Menom, Parallel Programming in OpenMP (Academic, Boston, 2000).

Dutt, A.

A. Dutt, V. Rokhlin, “Fast Fourier transform for nonequispaced data,” SIAM (Soc. Ind. Appl. Math.) J. Sci. Stat. Comput. 14, 1368–1393 (1993).
[CrossRef]

Eggers, H.

V. Rasche, R. Proksa, R. Sinkus, P. Börnert, H. Eggers, “Resampling of data between arbitrary grids using convolution interpolation,” IEEE Trans. Med. Imaging 18, 385–392 (1999).
[CrossRef] [PubMed]

Frank, J.

I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
[CrossRef] [PubMed]

J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
[CrossRef] [PubMed]

P. A. Penczek, R. A. Grassucci, J. Frank, “The ribosome at improved resolution: new techniques for merging and orientation refinement in 3D cryo-electron microscopy of biological particles,” Ultramicroscopy 53, 251–270 (1994).
[CrossRef] [PubMed]

P. Penczek, M. Radermacher, J. Frank, “Three-dimensional reconstruction of single particles embedded in ice,” Ultramicroscopy 40, 33–53 (1992).
[CrossRef] [PubMed]

M. Radermacher, T. Wagenknecht, A. Verschoor, J. Frank, “A new 3-D reconstruction scheme applied to the 50S ribosomal subunit of E. coli,” J. Microsc. (Oxford) 141, RP1–RP2 (1986).
[CrossRef]

J. Frank, Three-Dimensional Electron Microscopy of Macromolecular Assemblies (Academic, New York, 1996).

Gabashvili, I. S.

I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
[CrossRef] [PubMed]

Grassucci, R. A.

I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
[CrossRef] [PubMed]

P. A. Penczek, R. A. Grassucci, J. Frank, “The ribosome at improved resolution: new techniques for merging and orientation refinement in 3D cryo-electron microscopy of biological particles,” Ultramicroscopy 53, 251–270 (1994).
[CrossRef] [PubMed]

Grigorieff, N.

N. Grigorieff, “Three-dimensional structure of bovine NADH: ubiquinone oxidoreductase (complex I) at 22 Å in ice,” J. Mol. Biol. 277, 1033–1046 (1998).
[CrossRef] [PubMed]

Harauz, G.

G. Harauz, M. van Heel, “Exact filters for general geometry three dimensional reconstruction,” Optik (Stuttgart) 73, 146–156 (1986).

Herman, G. T.

R. Marabini, G. T. Herman, J. M. Carazo, “3D reconstruction in electron microscopy using ART with smooth spherically symmetric volume elements (blobs),” Ultramicroscopy 72, 53–65 (1998).
[CrossRef] [PubMed]

Jackson, J. I.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

Kohr, D.

R. Chandra, D. Kohr, D. Maydan, L. Dagum, J. McDonald, R. Menom, Parallel Programming in OpenMP (Academic, Boston, 2000).

Ladjadj, M.

J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
[CrossRef] [PubMed]

Lanzavecchia, S.

S. Lanzavecchia, P. L. Bellon, M. Radermacher, “Fast and accurate three-dimensional reconstruction from projections with random orientations via Radon transforms,” J. Struct. Biol. 128, 152–164 (1999).
[CrossRef] [PubMed]

S. Lanzavecchia, P. L. Bellon, “Electron tomography in conical tilt geometry. The accuracy of a direct Fourier method (DFM) and the suppression of non-tomographic noise,” Ultramicroscopy 63, 247–261 (1996).
[CrossRef]

S. Lanzavecchia, P. L. Bellon, V. Scatturin, “SPARK, a kernel software programs for spatial reconstruction in electron microscopy,” J. Microsc. (Oxford) 171, 255–266 (1993).
[CrossRef]

Leith, A.

J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
[CrossRef] [PubMed]

Li, Y.

J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
[CrossRef] [PubMed]

Macovski, A.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

Marabini, R.

R. Marabini, G. T. Herman, J. M. Carazo, “3D reconstruction in electron microscopy using ART with smooth spherically symmetric volume elements (blobs),” Ultramicroscopy 72, 53–65 (1998).
[CrossRef] [PubMed]

Maydan, D.

R. Chandra, D. Kohr, D. Maydan, L. Dagum, J. McDonald, R. Menom, Parallel Programming in OpenMP (Academic, Boston, 2000).

McDonald, J.

R. Chandra, D. Kohr, D. Maydan, L. Dagum, J. McDonald, R. Menom, Parallel Programming in OpenMP (Academic, Boston, 2000).

Menom, R.

R. Chandra, D. Kohr, D. Maydan, L. Dagum, J. McDonald, R. Menom, Parallel Programming in OpenMP (Academic, Boston, 2000).

Meyer, C. H.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

Natterer, F.

F. Natterer, F. Wübbeling, Mathematical Methods in Image Reconstruction (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 2001).

Nishimura, D. G.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

O’Sullivan, J. D.

J. D. O’Sullivan, “A fast sinc-function gridding algorithm for Fourier inversion in computer tomography,” IEEE Trans. Med. Imaging MI-4, 200–207 (1985).
[CrossRef]

Okabe, A.

A. Okabe, B. Boots, K. Sugihara, S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (Wiley, New York, 2000).

Orlov, S. S.

S. S. Orlov, “Theory of three-dimensional reconstruction. 1. Conditions of a complete set of projections,” Sov. Phys. Crystallogr. 20, 312–314 (1976).

Penczek, P.

I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
[CrossRef] [PubMed]

J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
[CrossRef] [PubMed]

P. Penczek, M. Radermacher, J. Frank, “Three-dimensional reconstruction of single particles embedded in ice,” Ultramicroscopy 40, 33–53 (1992).
[CrossRef] [PubMed]

Penczek, P. A.

P. A. Penczek, “Three-dimensional spectral signal-to-noise ratio for a class of reconstruction algorithms,” J. Struct. Biol. 138, 34–46 (2002).
[CrossRef] [PubMed]

P. A. Penczek, R. A. Grassucci, J. Frank, “The ribosome at improved resolution: new techniques for merging and orientation refinement in 3D cryo-electron microscopy of biological particles,” Ultramicroscopy 53, 251–270 (1994).
[CrossRef] [PubMed]

Potts, D.

D. Potts, G. Steidl, “New Fourier reconstruction algorithms for computerized tomography,” in Wavelet Applications in Signal and Image Processing VIII, A. Aldroubi, A. F. Laine, M. A. Unser, eds. (SPIE, Bellingham, Wash., 2000), pp. 13–23.

Proksa, R.

V. Rasche, R. Proksa, R. Sinkus, P. Börnert, H. Eggers, “Resampling of data between arbitrary grids using convolution interpolation,” IEEE Trans. Med. Imaging 18, 385–392 (1999).
[CrossRef] [PubMed]

Radermacher, M.

S. Lanzavecchia, P. L. Bellon, M. Radermacher, “Fast and accurate three-dimensional reconstruction from projections with random orientations via Radon transforms,” J. Struct. Biol. 128, 152–164 (1999).
[CrossRef] [PubMed]

J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
[CrossRef] [PubMed]

P. Penczek, M. Radermacher, J. Frank, “Three-dimensional reconstruction of single particles embedded in ice,” Ultramicroscopy 40, 33–53 (1992).
[CrossRef] [PubMed]

M. Radermacher, T. Wagenknecht, A. Verschoor, J. Frank, “A new 3-D reconstruction scheme applied to the 50S ribosomal subunit of E. coli,” J. Microsc. (Oxford) 141, RP1–RP2 (1986).
[CrossRef]

M. Radermacher, “Weighted back-projection methods,” in Electron Tomography, J. Frank, ed. (Plenum, New York, 1992), pp. 91–115.

Rasche, V.

V. Rasche, R. Proksa, R. Sinkus, P. Börnert, H. Eggers, “Resampling of data between arbitrary grids using convolution interpolation,” IEEE Trans. Med. Imaging 18, 385–392 (1999).
[CrossRef] [PubMed]

Renka, R. J.

R. J. Renka, “Algorithm 772. STRIPACK: Delaunay triangulation and Voronoi diagram on the surface of a sphere,” ACM (Assoc. Comput. Mach.) Trans. Math. Softw. 23, 416–434 (1997).
[CrossRef]

Rokhlin, V.

A. Dutt, V. Rokhlin, “Fast Fourier transform for nonequispaced data,” SIAM (Soc. Ind. Appl. Math.) J. Sci. Stat. Comput. 14, 1368–1393 (1993).
[CrossRef]

Saxton, W. O.

W. O. Saxton, W. Baumeister, “The correlation averaging of a regularly arranged bacterial envelope protein,” J. Microsc. (Oxford) 127, 127–138 (1982).
[CrossRef]

Scatturin, V.

S. Lanzavecchia, P. L. Bellon, V. Scatturin, “SPARK, a kernel software programs for spatial reconstruction in electron microscopy,” J. Microsc. (Oxford) 171, 255–266 (1993).
[CrossRef]

Schomberg, H.

H. Schomberg, J. Timmer, “The gridding method for im-age reconstruction by Fourier transformation,” IEEE Trans. Med. Imaging 14, 596–607 (1995).
[CrossRef]

H. Schomberg, “Notes on direct and gridding-based Fourier inversion methods,” in Proceedings of the IEEE International Symposium on Biomedical Imaging, M. Unser, Z. P. Liang, eds. (Institute of Electrical and Electronics Engineers, New York, 2002), pp. 645–648.

Sinkus, R.

V. Rasche, R. Proksa, R. Sinkus, P. Börnert, H. Eggers, “Resampling of data between arbitrary grids using convolution interpolation,” IEEE Trans. Med. Imaging 18, 385–392 (1999).
[CrossRef] [PubMed]

Spahn, C. M.

I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
[CrossRef] [PubMed]

Steidl, G.

D. Potts, G. Steidl, “New Fourier reconstruction algorithms for computerized tomography,” in Wavelet Applications in Signal and Image Processing VIII, A. Aldroubi, A. F. Laine, M. A. Unser, eds. (SPIE, Bellingham, Wash., 2000), pp. 13–23.

Sugihara, K.

A. Okabe, B. Boots, K. Sugihara, S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (Wiley, New York, 2000).

Svergun, D. I.

I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
[CrossRef] [PubMed]

Timmer, J.

H. Schomberg, J. Timmer, “The gridding method for im-age reconstruction by Fourier transformation,” IEEE Trans. Med. Imaging 14, 596–607 (1995).
[CrossRef]

van Heel, M.

G. Harauz, M. van Heel, “Exact filters for general geometry three dimensional reconstruction,” Optik (Stuttgart) 73, 146–156 (1986).

Verschoor, A.

M. Radermacher, T. Wagenknecht, A. Verschoor, J. Frank, “A new 3-D reconstruction scheme applied to the 50S ribosomal subunit of E. coli,” J. Microsc. (Oxford) 141, RP1–RP2 (1986).
[CrossRef]

Wade, R. H.

R. H. Wade, “A brief look at imaging and contrast transfer,” Ultramicroscopy 46, 145–156 (1992).
[CrossRef]

Wagenknecht, T.

M. Radermacher, T. Wagenknecht, A. Verschoor, J. Frank, “A new 3-D reconstruction scheme applied to the 50S ribosomal subunit of E. coli,” J. Microsc. (Oxford) 141, RP1–RP2 (1986).
[CrossRef]

Wübbeling, F.

F. Natterer, F. Wübbeling, Mathematical Methods in Image Reconstruction (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 2001).

Zhu, J.

J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
[CrossRef] [PubMed]

Zwillinger, D.

D. Zwillinger, CRC Standard Mathematical Tables and Formulae (CRC Press, Boca Raton, Fla., 2002).

ACM (Assoc. Comput. Mach.) Trans. Math. Softw.

R. J. Renka, “Algorithm 772. STRIPACK: Delaunay triangulation and Voronoi diagram on the surface of a sphere,” ACM (Assoc. Comput. Mach.) Trans. Math. Softw. 23, 416–434 (1997).
[CrossRef]

Appl. Comput. Harmon. Anal.

G. Beylkin, “On the fast Fourier transform of functions with singularities,” Appl. Comput. Harmon. Anal. 2, 363–381 (1995).
[CrossRef]

Cell

I. S. Gabashvili, R. K. Agrawal, C. M. Spahn, R. A. Grassucci, D. I. Svergun, J. Frank, P. Penczek, “Solution structure of the E. coli 70S ribosome at 11.5 Å resolution,” Cell 100, 537–549 (2000).
[CrossRef] [PubMed]

IEEE Trans. Med. Imaging

J. D. O’Sullivan, “A fast sinc-function gridding algorithm for Fourier inversion in computer tomography,” IEEE Trans. Med. Imaging MI-4, 200–207 (1985).
[CrossRef]

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

H. Schomberg, J. Timmer, “The gridding method for im-age reconstruction by Fourier transformation,” IEEE Trans. Med. Imaging 14, 596–607 (1995).
[CrossRef]

V. Rasche, R. Proksa, R. Sinkus, P. Börnert, H. Eggers, “Resampling of data between arbitrary grids using convolution interpolation,” IEEE Trans. Med. Imaging 18, 385–392 (1999).
[CrossRef] [PubMed]

J. Microsc. (Oxford)

S. Lanzavecchia, P. L. Bellon, V. Scatturin, “SPARK, a kernel software programs for spatial reconstruction in electron microscopy,” J. Microsc. (Oxford) 171, 255–266 (1993).
[CrossRef]

M. Radermacher, T. Wagenknecht, A. Verschoor, J. Frank, “A new 3-D reconstruction scheme applied to the 50S ribosomal subunit of E. coli,” J. Microsc. (Oxford) 141, RP1–RP2 (1986).
[CrossRef]

W. O. Saxton, W. Baumeister, “The correlation averaging of a regularly arranged bacterial envelope protein,” J. Microsc. (Oxford) 127, 127–138 (1982).
[CrossRef]

J. Mol. Biol.

N. Grigorieff, “Three-dimensional structure of bovine NADH: ubiquinone oxidoreductase (complex I) at 22 Å in ice,” J. Mol. Biol. 277, 1033–1046 (1998).
[CrossRef] [PubMed]

J. Struct. Biol.

S. Lanzavecchia, P. L. Bellon, M. Radermacher, “Fast and accurate three-dimensional reconstruction from projections with random orientations via Radon transforms,” J. Struct. Biol. 128, 152–164 (1999).
[CrossRef] [PubMed]

P. A. Penczek, “Three-dimensional spectral signal-to-noise ratio for a class of reconstruction algorithms,” J. Struct. Biol. 138, 34–46 (2002).
[CrossRef] [PubMed]

J. Frank, M. Radermacher, P. Penczek, J. Zhu, Y. Li, M. Ladjadj, A. Leith, “SPIDER and WEB: processing and visualization of images in 3D electron microscopy and related fields,” J. Struct. Biol. 116, 190–199 (1996).
[CrossRef] [PubMed]

Optik (Stuttgart)

G. Harauz, M. van Heel, “Exact filters for general geometry three dimensional reconstruction,” Optik (Stuttgart) 73, 146–156 (1986).

SIAM (Soc. Ind. Appl. Math.) J. Sci. Stat. Comput.

A. Dutt, V. Rokhlin, “Fast Fourier transform for nonequispaced data,” SIAM (Soc. Ind. Appl. Math.) J. Sci. Stat. Comput. 14, 1368–1393 (1993).
[CrossRef]

Sov. Phys. Crystallogr.

S. S. Orlov, “Theory of three-dimensional reconstruction. 1. Conditions of a complete set of projections,” Sov. Phys. Crystallogr. 20, 312–314 (1976).

Ultramicroscopy

S. Lanzavecchia, P. L. Bellon, “Electron tomography in conical tilt geometry. The accuracy of a direct Fourier method (DFM) and the suppression of non-tomographic noise,” Ultramicroscopy 63, 247–261 (1996).
[CrossRef]

R. H. Wade, “A brief look at imaging and contrast transfer,” Ultramicroscopy 46, 145–156 (1992).
[CrossRef]

P. A. Penczek, R. A. Grassucci, J. Frank, “The ribosome at improved resolution: new techniques for merging and orientation refinement in 3D cryo-electron microscopy of biological particles,” Ultramicroscopy 53, 251–270 (1994).
[CrossRef] [PubMed]

P. Penczek, M. Radermacher, J. Frank, “Three-dimensional reconstruction of single particles embedded in ice,” Ultramicroscopy 40, 33–53 (1992).
[CrossRef] [PubMed]

R. Marabini, G. T. Herman, J. M. Carazo, “3D reconstruction in electron microscopy using ART with smooth spherically symmetric volume elements (blobs),” Ultramicroscopy 72, 53–65 (1998).
[CrossRef] [PubMed]

Other

M. Radermacher, “Weighted back-projection methods,” in Electron Tomography, J. Frank, ed. (Plenum, New York, 1992), pp. 91–115.

J. Frank, Three-Dimensional Electron Microscopy of Macromolecular Assemblies (Academic, New York, 1996).

F. Natterer, F. Wübbeling, Mathematical Methods in Image Reconstruction (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 2001).

W. N. Brouw, “Aperture synthesis,” in Methods in Computational Physics, B. Alder, S. Fernbach, M. Rotenberg, eds. (Academic, New York, 1975), pp. 131–175.

H. Schomberg, “Notes on direct and gridding-based Fourier inversion methods,” in Proceedings of the IEEE International Symposium on Biomedical Imaging, M. Unser, Z. P. Liang, eds. (Institute of Electrical and Electronics Engineers, New York, 2002), pp. 645–648.

A. Okabe, B. Boots, K. Sugihara, S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (Wiley, New York, 2000).

D. Potts, G. Steidl, “New Fourier reconstruction algorithms for computerized tomography,” in Wavelet Applications in Signal and Image Processing VIII, A. Aldroubi, A. F. Laine, M. A. Unser, eds. (SPIE, Bellingham, Wash., 2000), pp. 13–23.

D. Zwillinger, CRC Standard Mathematical Tables and Formulae (CRC Press, Boca Raton, Fla., 2002).

R. Chandra, D. Kohr, D. Maydan, L. Dagum, J. McDonald, R. Menom, Parallel Programming in OpenMP (Academic, Boston, 2000).

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

Fig. 1
Fig. 1

Flow diagram of the reconstruction algorithm. In the preprocessing stage, each of the available, uniformly sampled projections of the object function f is numerically Fourier transformed and evaluated on a 2-D polar grid. The numerical Fourier transformation is realized by the 2-D reverse gridding method. By the projection theorem, the output of the preprocessing stage gives a sampled version of fˆ, the Fourier transform of f, on a 3-D nonuniform grid, where the sampling points are located on centered spheres and on straight lines through the origin. In the main stage, this nonuniformly sampled version of fˆ is numerically inversely Fourier transformed, yielding f on a 3-D uniform grid. The numerical inverse Fourier transformation is realized by the 3-D gridding method. Owing to the special structure of the nonuniform grid, the required gridding weights can be calculated by means of a 2-D spherical Voronoi diagram.

Fig. 2
Fig. 2

(a) Central x3 slice of the test object. (b) Corresponding slice of a reconstructed object, obtained by GDFR from noise-free projections computed in Fourier space. (c) Corresponding slice of a difference between a GDFR-reconstructed object and the test object. The difference map was low-pass filtered by setting to zero the spatial frequencies of the reconstructed objects outside the centered ball with radius 1/(2a). (d) Corresponding slice of a reconstructed object, obtained by the SIRT from noise-free projections computed in object space. (e) Corresponding slice of a difference between an SIRT-reconstructed object and the test object.

Fig. 3
Fig. 3

(a) Fidelity curves for the noise-free projections computed in Fourier space, (b) rescaled version of the low-spatial-frequency range of (a), (c) consistency curves for the noise-free projections computed in Fourier space.

Fig. 4
Fig. 4

(a) Fidelity curves for the noise-free projections computed in object space, (b) consistency curves for the noise-free projections computed in object space.

Fig. 5
Fig. 5

(a) Fidelity curves for the noise-corrupted projections, (b) consistency curves for the noise-corrupted projections.

Tables (2)

Tables Icon

Table 1 Correlation Coefficients between the Test Object and the Objects Reconstructed by the Four Algorithms Tested

Tables Icon

Table 2 Correlation Coefficients between the Test Object and the Low-Pass-Filtered Objects Reconstructed by the Four Algorithms Testeda

Equations (37)

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

(Fh)(y)=Rdh(x)exp(-i2πx·y)dx.
h(x)=(F-1hˆ)(x)=Rdhˆ(y)exp(i2πx·y)dy.
(Ph)(θ, u)=Rh(u+tθ)dt,θSd-1,uθ.
Pθh=(Ph)(θ,·)
(Pθhˆ)(ξ)=hˆ(ξ),ξθ,
b=1/(aN).
wˆKB(y)=ν=1dI0(2πανrνsν[1-(yν/sν)2]1/2)2sν0
y[-s, s],y[-s, s],
wKB(x)=ν=1dsinh(2πανrνsν{1-[xν/(ανrν)]2}1/2)2πανrνsν{1-[xν/(ανrν)]2}1/2.
gˆn=jJcjhˆj(yj)wˆ(nb-yj),-N/2n<N/2.
gk=b1bdn=-N/2N/2gˆn exp[i2πk(n/N)], -K/2k<K/2.
hk=gk/w(ka),-K/2k<K/2.
s(x)=jJcj exp(i2πx·yj),
(s*h)(x)=jJcjhˆ(yj)exp(i2πx·yj).
hS(x)=Shˆ(y)exp(i2πx·y)dy,
cj=vol(Cj).
gk=hk(ka)/w(ka),-K/2k<K/2.
gˆn=a1adk=-N/2N/2gk exp[-i2πk·(n/N)], -N/2k<N/2.
hj=b1bdn=-N/2N/2gˆnwˆ(yj-nb),jJ.
sˆa,K(y)=a1adk=-K/2K/2-1exp[-i2π(ka)y].
V(P, i)={pS2: d(p, pi)d(p, pj),  j=1,,n}.
a=α1++αm-(m-2)π,
αμ=arccos[(qμ×qλ)·(qμ×qν)],
2R=1/a
dr=R/L,
ylm=rlpm,l=0,,L,m=1,,M,
rl=ldr,l=0,,L,
pmS2,m=1,,M.
S=B3(R+dr/2)
fS(x)=Sfˆ(y)exp(i2πx·y)dy
fS(x)c0fˆ(0)+l=1Lm=1Mclmfˆ(ylm)exp(i2πx·ylm)
c0=vol(C0),clm=vol(Clm),
l=1,,L,m=1,,M.
c0=π6dr3.
Clm={rp: rl-dr/2rrl+dr/2, pV(P, m)},
clm=amrl-dr/2rl+dr/2r2 dr=amdr3[3rl2+(dr/2)2].
FSC(f, g;r)=|yn-r|fˆ(yn)gˆ*(yn)|yn-r||fˆ(yn)|2|yn-r||gˆ(yn)|21/2,

Metrics