OSA's Digital Library

Journal of the Optical Society of America A

Journal of the Optical Society of America A


  • Vol. 21, Iss. 4 — Apr. 1, 2004
  • pp: 499–509

Gridding-based direct Fourier inversion of the three-dimensional ray transform

Pawel A. Penczek, Robert Renka, and Hermann Schomberg  »View Author Affiliations

JOSA A, Vol. 21, Issue 4, pp. 499-509 (2004)

View Full Text Article

Enhanced HTML    Acrobat PDF (306 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



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

OCIS Codes
(100.3010) Image processing : Image reconstruction techniques
(100.3190) Image processing : Inverse problems
(100.6890) Image processing : Three-dimensional image processing
(100.6950) Image processing : Tomographic image processing

Original Manuscript: June 4, 2003
Revised Manuscript: November 18, 2003
Manuscript Accepted: November 20, 2003
Published: April 1, 2004

Pawel A. Penczek, Robert Renka, and Hermann Schomberg, "Gridding-based direct Fourier inversion of the three-dimensional ray transform," J. Opt. Soc. Am. A 21, 499-509 (2004)

Sort:  Author  |  Year  |  Journal  |  Reset  


  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]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


Fig. 1 Fig. 2 Fig. 3
Fig. 4 Fig. 5

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited