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 & 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. doi: 10.1088/0266-5611/23/5/016. Google Scholar

[2]

M. Agranovsky, P. Kuchment and L. Kunyansky, On reconstruction formulas and algorithms for the thermoacoustic tomography,, in, (2009), 89. doi: 10.1201/9781420059922.ch8. Google Scholar

[3]

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

[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). Google Scholar

[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). doi: 10.1103/PhysRevE.75.046706. Google Scholar

[6]

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

[7]

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

[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. doi: 10.1137/070682137. Google Scholar

[9]

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

[10]

M. Haltmeier, Inversion of circular means and the wave equation on convex planar domains,, , (2012). Google Scholar

[11]

M. Haltmeier, Universal inversion formulas for recovering a function from spherical means,, , (2012). Google Scholar

[12]

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

[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. doi: 10.1109/TMI.2009.2022623. Google Scholar

[14]

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

[15]

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

[16]

F. John, "Plane Waves and Spherical Means Applied to Partial Differential Equations,", Reprint of the 1955 original, (1955). Google Scholar

[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). Google Scholar

[18]

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

[19]

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

[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). Google Scholar

[21]

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

[22]

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

[23]

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

[24]

G. Paltauf, R. Nuster, M. Haltmeier and P. Burgholzer, Photoacoustic tomography with integrating area and line detectors,, in, (2009), 251. Google Scholar

[25]

E. T. Quinto, Helgason's support theorem and spherical Radon transforms,, in, 464 (2008), 249. Google Scholar

[26]

L. V. Wang and H. Wu, "Biomedical Optics - Principles and Imaging,", John Wiley & Sons Inc., (2007). Google Scholar

[27]

G. N. Watson, "A Treatise on the Theory of Bessel Functions,", Second edition, (1966). Google Scholar

[28]

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

[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. doi: 10.1002/mma.1266. Google Scholar

[30]

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

[31]

A. Zygmund, "Trigonometric Series. Vol. I, II,", Third edition, (2002). Google Scholar

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. doi: 10.1088/0266-5611/23/5/016. Google Scholar

[2]

M. Agranovsky, P. Kuchment and L. Kunyansky, On reconstruction formulas and algorithms for the thermoacoustic tomography,, in, (2009), 89. doi: 10.1201/9781420059922.ch8. Google Scholar

[3]

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

[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). Google Scholar

[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). doi: 10.1103/PhysRevE.75.046706. Google Scholar

[6]

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

[7]

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

[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. doi: 10.1137/070682137. Google Scholar

[9]

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

[10]

M. Haltmeier, Inversion of circular means and the wave equation on convex planar domains,, , (2012). Google Scholar

[11]

M. Haltmeier, Universal inversion formulas for recovering a function from spherical means,, , (2012). Google Scholar

[12]

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

[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. doi: 10.1109/TMI.2009.2022623. Google Scholar

[14]

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

[15]

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

[16]

F. John, "Plane Waves and Spherical Means Applied to Partial Differential Equations,", Reprint of the 1955 original, (1955). Google Scholar

[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). Google Scholar

[18]

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

[19]

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

[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). Google Scholar

[21]

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

[22]

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

[23]

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

[24]

G. Paltauf, R. Nuster, M. Haltmeier and P. Burgholzer, Photoacoustic tomography with integrating area and line detectors,, in, (2009), 251. Google Scholar

[25]

E. T. Quinto, Helgason's support theorem and spherical Radon transforms,, in, 464 (2008), 249. Google Scholar

[26]

L. V. Wang and H. Wu, "Biomedical Optics - Principles and Imaging,", John Wiley & Sons Inc., (2007). Google Scholar

[27]

G. N. Watson, "A Treatise on the Theory of Bessel Functions,", Second edition, (1966). Google Scholar

[28]

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

[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. doi: 10.1002/mma.1266. Google Scholar

[30]

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

[31]

A. Zygmund, "Trigonometric Series. Vol. I, II,", Third edition, (2002). Google Scholar

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[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 & 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 & Imaging, 2015, 9 (3) : 749-766. doi: 10.3934/ipi.2015.9.749

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Nam Yul Yu. A Fourier transform approach for improving the Levenshtein's lower bound on aperiodic correlation of binary sequences. Advances in Mathematics of Communications, 2014, 8 (2) : 209-222. doi: 10.3934/amc.2014.8.209

[19]

A. Lehikoinen, S. Finsterle, A Voutilainen, L. M. Heikkinen, M. Vauhkonen, J. P. Kaipio. Approximation errors and truncation of computational domains with application to geophysical tomography. Inverse Problems & Imaging, 2007, 1 (2) : 371-389. doi: 10.3934/ipi.2007.1.371

[20]

Alexander Alekseenko, Jeffrey Limbacher. Evaluating high order discontinuous Galerkin discretization of the Boltzmann collision integral in $ \mathcal{O}(N^2) $ operations using the discrete fourier transform. Kinetic & Related Models, 2019, 12 (4) : 703-726. doi: 10.3934/krm.2019027

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]