November  2012, 6(4): 645-661. doi: 10.3934/ipi.2012.6.645

Efficient and accurate computation of spherical mean values at scattered center points

1. 

University Osnabrück, Institute of Mathematics, 49069 Osnabrück, Germany

2. 

University Chemnitz, Department of Mathematics, 09107 Chemnitz, Germany

3. 

University Osnabrück, Institute of Mathematics, 49069 Osnabrück, and, Helmholtz Zentrum München, Institute for Biomathematics and Biometry, 85764 Neuherberg, Germany

Received  December 2011 Revised  September 2012 Published  November 2012

Spherical means are a widespread model in modern imaging modalities like photoacoustic tomography. Besides direct inversion methods for specific geometries, iterative methods are often used as reconstruction scheme such that each iteration asks for the efficient and accurate computation of spherical means. We consider a spectral discretization via trigonometric polynomials such that the computation can be done via nonequispaced fast Fourier transforms. Moreover, a recently developed sparse fast Fourier transform is used in the three dimensional case and gives optimal arithmetic complexity. All theoretical results are illustrated by numerical experiments.
Citation: Torsten Görner, Ralf Hielscher, Stefan Kunis. Efficient and accurate computation of spherical mean values at scattered center points. Inverse Problems and Imaging, 2012, 6 (4) : 645-661. doi: 10.3934/ipi.2012.6.645
References:
[1]

M. Agranovsky and P. Kuchment, Uniqueness of reconstruction and an inversion procedure for thermoacoustic and photoacoustic tomography with variable sound speed, Inverse Problems, 23 (2007), 2089-2102. doi: 10.1088/0266-5611/23/5/016.

[2]

M. Agranovsky, P. Kuchment and L. Kunyansky, On reconstruction formulas and algorithms for the thermoacoustic tomography, in "Photoacoustic Imaging and Spectroscopy" (ed. L. V. Wang), chapter 8, CRC Press, Boca Raton, FL, (2009), 89-101. doi: 10.1201/9781420059922.ch8.

[3]

M. Agranovsky, P. Kuchment and E. T. Quinto, Range descriptions for the spherical mean Radon transform, J. Funct. Anal., 248 (2007), 344-386. doi: 10.1016/j.jfa.2007.03.022.

[4]

A. Buehler, A. Rosenthal, T. Jetzfellner, A. Dima, D. Razansky and V. Ntziachristos, Model-based optoacoustic inversions with incomplete projection data, Med. Phys., 38 (1694), 2011.

[5]

P. Burgholzer, G. J. Matt, M. Haltmeier and G. Paltauf, Exact and approximate imaging methods for photoacoustic tomography using an arbitrary detection surface, Phys. Rev. E, 75 (2007), 046706. doi: 10.1103/PhysRevE.75.046706.

[6]

Y. Dong, T. Görner and S. Kunis, An iterative reconstruction scheme for photoacoustic imaging, preprint, 2011.

[7]

F. Filbir, R. Hielscher and W. R. Madych, Reconstruction from circular and spherical mean data, Appl. Comput. Harmon. Anal., 29 (2010), 111-120. doi: 10.1016/j.acha.2009.10.001.

[8]

D. Finch, M. Haltmeier and Rakesh, Inversion of spherical means and the wave equation in even dimensions, SIAM J. Appl. Math., 68 (2007), 392-412. doi: 10.1137/070682137.

[9]

M. Haltmeier, A mollification approach for inverting the spherical mean Radon transform, SIAM J. Appl. Math., 71 (2011), 1637-1652. doi: 10.1137/110821561.

[10]

M. Haltmeier, Inversion of circular means and the wave equation on convex planar domains, arXiv:1206.1246, 2012.

[11]

M. Haltmeier, Universal inversion formulas for recovering a function from spherical means, arXiv:1206.3424, 2012.

[12]

M. Haltmeier, O. Scherzer, P. Burgholzer and G. Paltauf, Thermoacoustic computed tomography with large planar receivers, Inverse Problems, 20 (2004), 1663-1673. doi: 10.1088/0266-5611/20/5/021.

[13]

M. Haltmeier, O. Scherzer and G. Zangerl, A reconstruction algorithm for photoacoustic imaging based on the nonuniform FFT, IEEE Trans. Med. Imag., 28 (2009), 1727-1735. doi: 10.1109/TMI.2009.2022623.

[14]

M. Haltmeier, T. Schuster and O. Scherzer, Filtered backprojection for thermoacoustic computed tomography in spherical geometry, Math. Methods Appl. Sci., 28 (2005), 1919-1937. doi: 10.1002/mma.648.

[15]

M. Haltmeier and G. Zangerl, Spatial resolution in photoacoustic tomography: Effects of detector size and detector bandwidth, Inverse Problems, 26 (2010), 125002, 14 pp.

[16]

F. John, "Plane Waves and Spherical Means Applied to Partial Differential Equations," Reprint of the 1955 original, Dover Publications, Inc., Mineola, NY, 2004.

[17]

J. Keiner, S. Kunis and D. Potts, Using {NFFT 3-a software library for various nonequispaced fast Fourier transforms}, ACM Trans. Math. Software, 36 (2009), Art. 19, 30 pp.

[18]

P. Kuchment and L. Kunyansky, Mathematics of thermoacoustic tomography, European J. Appl. Math., 19 (2008), 191-224.

[19]

S. Kunis and I. Melzer, A stable and accurate butterfly sparse Fourier transform, SIAM J. Numer. Anal., 50 (2012), 1777-1800. doi: 10.1137/110839825.

[20]

L. Kunyansky, Reconstruction of a function from its spherical (circular) means with the centers lying on the surface of certain polygons and polyhedra, Inverse Problems, 27 (2011), 025012, 22 pp.

[21]

L. A. Kunyansky, Explicit inversion formulae for the spherical mean Radon transform, Inverse Problems, 23 (2007), 373-383.

[22]

L. A. Kunyansky, A series solution and a fast algorithm for the inversion of the spherical mean Radon transform, Inverse Problems, 23 (2007), S11-S20. doi: 10.1088/0266-5611/23/6/S02.

[23]

F. Natterer, Photo-acoustic inversion in convex domains, Inverse Probl. Imaging, 6 (2012), 1-6. doi: 10.3934/ipi.2012.6.315.

[24]

G. Paltauf, R. Nuster, M. Haltmeier and P. Burgholzer, Photoacoustic tomography with integrating area and line detectors, in "Photoacoustic Imaging and Spectroscopy" (ed. L. V. Wang), Optical Science and Engineering, chapter 20, CRC Press, Boca Raton, FL, (2009), 251-263.

[25]

E. T. Quinto, Helgason's support theorem and spherical Radon transforms, in "Radon Transforms, Geometry, and Wavelets," Contemp. Math., 464, Amer. Math. Soc., Providence, RI, (2008), 249-264.

[26]

L. V. Wang and H. Wu, "Biomedical Optics - Principles and Imaging," John Wiley & Sons Inc., Hoboken, NJ, 2007.

[27]

G. N. Watson, "A Treatise on the Theory of Bessel Functions," Second edition, Cambridge University Press, Cambridge, 1966.

[28]

L. Ying, Sparse Fourier transform via butterfly algorithm, SIAM J. Sci. Comput., 31 (2009), 1678-1694. doi: 10.1137/08071291X.

[29]

G. Zangerl and O. Scherzer, Exact reconstruction in photoacoustic tomography with circular integrating detectors II: Spherical geometry, Math. Methods Appl. Sci., 33 (2010), 1771-1782. doi: 10.1002/mma.1266.

[30]

G. Zangerl, O. Scherzer and M. Haltmeier, Exact series reconstruction in photoacoustic tomography with circular integrating detectors, Commun. Math. Sci., 7 (2009), 665-678.

[31]

A. Zygmund, "Trigonometric Series. Vol. I, II," Third edition, With a foreword by Robert A. Fefferman, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2002.

show all references

References:
[1]

M. Agranovsky and P. Kuchment, Uniqueness of reconstruction and an inversion procedure for thermoacoustic and photoacoustic tomography with variable sound speed, Inverse Problems, 23 (2007), 2089-2102. doi: 10.1088/0266-5611/23/5/016.

[2]

M. Agranovsky, P. Kuchment and L. Kunyansky, On reconstruction formulas and algorithms for the thermoacoustic tomography, in "Photoacoustic Imaging and Spectroscopy" (ed. L. V. Wang), chapter 8, CRC Press, Boca Raton, FL, (2009), 89-101. doi: 10.1201/9781420059922.ch8.

[3]

M. Agranovsky, P. Kuchment and E. T. Quinto, Range descriptions for the spherical mean Radon transform, J. Funct. Anal., 248 (2007), 344-386. doi: 10.1016/j.jfa.2007.03.022.

[4]

A. Buehler, A. Rosenthal, T. Jetzfellner, A. Dima, D. Razansky and V. Ntziachristos, Model-based optoacoustic inversions with incomplete projection data, Med. Phys., 38 (1694), 2011.

[5]

P. Burgholzer, G. J. Matt, M. Haltmeier and G. Paltauf, Exact and approximate imaging methods for photoacoustic tomography using an arbitrary detection surface, Phys. Rev. E, 75 (2007), 046706. doi: 10.1103/PhysRevE.75.046706.

[6]

Y. Dong, T. Görner and S. Kunis, An iterative reconstruction scheme for photoacoustic imaging, preprint, 2011.

[7]

F. Filbir, R. Hielscher and W. R. Madych, Reconstruction from circular and spherical mean data, Appl. Comput. Harmon. Anal., 29 (2010), 111-120. doi: 10.1016/j.acha.2009.10.001.

[8]

D. Finch, M. Haltmeier and Rakesh, Inversion of spherical means and the wave equation in even dimensions, SIAM J. Appl. Math., 68 (2007), 392-412. doi: 10.1137/070682137.

[9]

M. Haltmeier, A mollification approach for inverting the spherical mean Radon transform, SIAM J. Appl. Math., 71 (2011), 1637-1652. doi: 10.1137/110821561.

[10]

M. Haltmeier, Inversion of circular means and the wave equation on convex planar domains, arXiv:1206.1246, 2012.

[11]

M. Haltmeier, Universal inversion formulas for recovering a function from spherical means, arXiv:1206.3424, 2012.

[12]

M. Haltmeier, O. Scherzer, P. Burgholzer and G. Paltauf, Thermoacoustic computed tomography with large planar receivers, Inverse Problems, 20 (2004), 1663-1673. doi: 10.1088/0266-5611/20/5/021.

[13]

M. Haltmeier, O. Scherzer and G. Zangerl, A reconstruction algorithm for photoacoustic imaging based on the nonuniform FFT, IEEE Trans. Med. Imag., 28 (2009), 1727-1735. doi: 10.1109/TMI.2009.2022623.

[14]

M. Haltmeier, T. Schuster and O. Scherzer, Filtered backprojection for thermoacoustic computed tomography in spherical geometry, Math. Methods Appl. Sci., 28 (2005), 1919-1937. doi: 10.1002/mma.648.

[15]

M. Haltmeier and G. Zangerl, Spatial resolution in photoacoustic tomography: Effects of detector size and detector bandwidth, Inverse Problems, 26 (2010), 125002, 14 pp.

[16]

F. John, "Plane Waves and Spherical Means Applied to Partial Differential Equations," Reprint of the 1955 original, Dover Publications, Inc., Mineola, NY, 2004.

[17]

J. Keiner, S. Kunis and D. Potts, Using {NFFT 3-a software library for various nonequispaced fast Fourier transforms}, ACM Trans. Math. Software, 36 (2009), Art. 19, 30 pp.

[18]

P. Kuchment and L. Kunyansky, Mathematics of thermoacoustic tomography, European J. Appl. Math., 19 (2008), 191-224.

[19]

S. Kunis and I. Melzer, A stable and accurate butterfly sparse Fourier transform, SIAM J. Numer. Anal., 50 (2012), 1777-1800. doi: 10.1137/110839825.

[20]

L. Kunyansky, Reconstruction of a function from its spherical (circular) means with the centers lying on the surface of certain polygons and polyhedra, Inverse Problems, 27 (2011), 025012, 22 pp.

[21]

L. A. Kunyansky, Explicit inversion formulae for the spherical mean Radon transform, Inverse Problems, 23 (2007), 373-383.

[22]

L. A. Kunyansky, A series solution and a fast algorithm for the inversion of the spherical mean Radon transform, Inverse Problems, 23 (2007), S11-S20. doi: 10.1088/0266-5611/23/6/S02.

[23]

F. Natterer, Photo-acoustic inversion in convex domains, Inverse Probl. Imaging, 6 (2012), 1-6. doi: 10.3934/ipi.2012.6.315.

[24]

G. Paltauf, R. Nuster, M. Haltmeier and P. Burgholzer, Photoacoustic tomography with integrating area and line detectors, in "Photoacoustic Imaging and Spectroscopy" (ed. L. V. Wang), Optical Science and Engineering, chapter 20, CRC Press, Boca Raton, FL, (2009), 251-263.

[25]

E. T. Quinto, Helgason's support theorem and spherical Radon transforms, in "Radon Transforms, Geometry, and Wavelets," Contemp. Math., 464, Amer. Math. Soc., Providence, RI, (2008), 249-264.

[26]

L. V. Wang and H. Wu, "Biomedical Optics - Principles and Imaging," John Wiley & Sons Inc., Hoboken, NJ, 2007.

[27]

G. N. Watson, "A Treatise on the Theory of Bessel Functions," Second edition, Cambridge University Press, Cambridge, 1966.

[28]

L. Ying, Sparse Fourier transform via butterfly algorithm, SIAM J. Sci. Comput., 31 (2009), 1678-1694. doi: 10.1137/08071291X.

[29]

G. Zangerl and O. Scherzer, Exact reconstruction in photoacoustic tomography with circular integrating detectors II: Spherical geometry, Math. Methods Appl. Sci., 33 (2010), 1771-1782. doi: 10.1002/mma.1266.

[30]

G. Zangerl, O. Scherzer and M. Haltmeier, Exact series reconstruction in photoacoustic tomography with circular integrating detectors, Commun. Math. Sci., 7 (2009), 665-678.

[31]

A. Zygmund, "Trigonometric Series. Vol. I, II," Third edition, With a foreword by Robert A. Fefferman, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2002.

[1]

Leonid Kunyansky. Fast reconstruction algorithms for the thermoacoustic tomography in certain domains with cylindrical or spherical symmetries. Inverse Problems and Imaging, 2012, 6 (1) : 111-131. doi: 10.3934/ipi.2012.6.111

[2]

Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $-means problem with penalty. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021067

[3]

Linh V. Nguyen. Spherical mean transform: A PDE approach. Inverse Problems and Imaging, 2013, 7 (1) : 243-252. doi: 10.3934/ipi.2013.7.243

[4]

Mark Agranovsky, David Finch, Peter Kuchment. Range conditions for a spherical mean transform. Inverse Problems and Imaging, 2009, 3 (3) : 373-382. doi: 10.3934/ipi.2009.3.373

[5]

Susanna V. Haziot. On the spherical geopotential approximation for Saturn. Communications on Pure and Applied Analysis, 2022, 21 (7) : 2327-2336. doi: 10.3934/cpaa.2022035

[6]

Alberto Ibort, Alberto López-Yela. Quantum tomography and the quantum Radon transform. Inverse Problems and Imaging, 2021, 15 (5) : 893-928. doi: 10.3934/ipi.2021021

[7]

Daniela Calvetti, Paul J. Hadwin, Janne M. J. Huttunen, Jari P. Kaipio, Erkki Somersalo. Artificial boundary conditions and domain truncation in electrical impedance tomography. Part II: Stochastic extension of the boundary map. Inverse Problems and Imaging, 2015, 9 (3) : 767-789. doi: 10.3934/ipi.2015.9.767

[8]

Daniela Calvetti, Paul J. Hadwin, Janne M. J. Huttunen, David Isaacson, Jari P. Kaipio, Debra McGivney, Erkki Somersalo, Joseph Volzer. Artificial boundary conditions and domain truncation in electrical impedance tomography. Part I: Theory and preliminary results. Inverse Problems and Imaging, 2015, 9 (3) : 749-766. doi: 10.3934/ipi.2015.9.749

[9]

Juan H. Arredondo, Francisco J. Mendoza, Alfredo Reyes. On the norm continuity of the hk-fourier transform. Electronic Research Announcements, 2018, 25: 36-47. doi: 10.3934/era.2018.25.005

[10]

Georgi Grahovski, Rossen Ivanov. Generalised Fourier transform and perturbations to soliton equations. Discrete and Continuous Dynamical Systems - B, 2009, 12 (3) : 579-595. doi: 10.3934/dcdsb.2009.12.579

[11]

Victor Palamodov. Remarks on the general Funk transform and thermoacoustic tomography. Inverse Problems and Imaging, 2010, 4 (4) : 693-702. doi: 10.3934/ipi.2010.4.693

[12]

Gaik Ambartsoumian, Leonid Kunyansky. Exterior/interior problem for the circular means transform with applications to intravascular imaging. Inverse Problems and Imaging, 2014, 8 (2) : 339-359. doi: 10.3934/ipi.2014.8.339

[13]

Hans Rullgård, Eric Todd Quinto. Local Sobolev estimates of a function by means of its Radon transform. Inverse Problems and Imaging, 2010, 4 (4) : 721-734. doi: 10.3934/ipi.2010.4.721

[14]

Sunghwan Moon. Inversion of the spherical Radon transform on spheres through the origin using the regular Radon transform. Communications on Pure and Applied Analysis, 2016, 15 (3) : 1029-1039. doi: 10.3934/cpaa.2016.15.1029

[15]

Ali Gholami, Mauricio D. Sacchi. Time-invariant radon transform by generalized Fourier slice theorem. Inverse Problems and Imaging, 2017, 11 (3) : 501-519. doi: 10.3934/ipi.2017023

[16]

Michael Music. The nonlinear Fourier transform for two-dimensional subcritical potentials. Inverse Problems and Imaging, 2014, 8 (4) : 1151-1167. doi: 10.3934/ipi.2014.8.1151

[17]

Jan-Cornelius Molnar. On two-sided estimates for the nonlinear Fourier transform of KdV. Discrete and Continuous Dynamical Systems, 2016, 36 (6) : 3339-3356. doi: 10.3934/dcds.2016.36.3339

[18]

Matti Viikinkoski, Mikko Kaasalainen. Shape reconstruction from images: Pixel fields and Fourier transform. Inverse Problems and Imaging, 2014, 8 (3) : 885-900. doi: 10.3934/ipi.2014.8.885

[19]

Barbara Brandolini, Francesco Chiacchio, Jeffrey J. Langford. Estimates for sums of eigenvalues of the free plate via the fourier transform. Communications on Pure and Applied Analysis, 2020, 19 (1) : 113-122. doi: 10.3934/cpaa.2020007

[20]

Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427

2020 Impact Factor: 1.639

Metrics

  • PDF downloads (81)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]