
-
Previous Article
Recovering the boundary corrosion from electrical potential distribution using partial boundary data
- IPI Home
- This Issue
-
Next Article
Ambient noise correlation-based imaging with moving sensors
Time-invariant radon transform by generalized Fourier slice theorem
1. | Institute of Geophysics, University of Tehran, Tehran, Iran |
2. | Department of Physics, University of Alberta, Edmonton, AB, Canada |
Time-invariant Radon transforms play an important role in many fields of imaging sciences, whereby a function is transformed linearly by integrating it along specific paths, e.g. straight lines, parabolas, etc. In the case of linear Radon transform, the Fourier slice theorem establishes a simple analytic relationship between the 2-D Fourier representation of the function and the 1-D Fourier representation of its Radon transform. However, the theorem can not be utilized for computing the Radon integral along paths other than straight lines. We generalize the Fourier slice theorem to make it applicable to general time-invariant Radon transforms. Specifically, we derive an analytic expression that connects the 1-D Fourier coefficients of the function to the 2-D Fourier coefficients of its general Radon transform. For discrete data, the model coefficients are defined over the data coefficients on non-Cartesian points. It is shown numerically that a simple linear interpolation provide satisfactory results and in this case implementations of both the inverse operator and its adjoint are fast in the sense that they run in $O(N \;\text{log}\; N)$ flops, where $N$ is the maximum number of samples in the data space or model space. These two canonical operators are utilized for efficient implementation of the sparse Radon transform via the split Bregman iterative method. We provide numerical examples showing high-performance of this method for noise attenuation and wavefield separation in seismic data.
References:
[1] |
A. Averbuch, R. Coifman, D. L. Donoho, M. Israeli and Y. Shkonisky,
A framework for discrete integral transformation Ⅰ- the pseudo-polar Fourier transform, SIAM J. of Scientific Computing, 30 (2008), 764-784.
doi: 10.1137/060650283. |
[2] |
A. Averbuch, R. Coifman, D. L. Donoho, M. Israeli, Y. Shkonisky and I. Sedelnikov,
A framework for discrete integral transformation Ⅱ-the 2D discrete Radon transform, SIAM J. of Scientific Computing, 30 (2008), 785-803.
doi: 10.1137/060650301. |
[3] |
S. Basu and Y. Bresler,
$O(N^3 \log N)$ backprojection algorithm for the 3D Radon transform, IEEE Trans. Medical Imaging, 21 (2002), 76-88.
|
[4] |
A. Beck and M. Teboulle,
A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sciences, 2 (2009), 183-202.
doi: 10.1137/080716542. |
[5] |
G. Beylkin,
Discrete Radon transform, IEEE Transactions on Acoustics, Speech and Signal Processing, 35 (1987), 162-172.
doi: 10.1109/TASSP.1987.1165108. |
[6] |
P. W. Cary,
The simplest discrete Radon transform, 68th Annual International Meeting, SEG, Expanded Abstracts, (1998), 1999-2002.
doi: 10.1190/1.1820335. |
[7] |
R. H. Chan and M. K. Ng,
Conjugate gradient methods for Toeplitz systems, SIAM Review, 38 (1996), 427-482.
doi: 10.1137/S0036144594276474. |
[8] |
S. Chen, D. L. Donoho and M. Saunders,
Atomic decomposition by basis pursuit, SIAM J. of Scientific Computation, 20 (1998), 33-61.
doi: 10.1137/S1064827596304010. |
[9] |
A. Gholami,
Nonconvex compressed sensing with frequency mask for seismic data reconstruction and denoising, Geophysical Prospecting, 62 (2014), 1389-1405.
|
[10] |
A. Gholami,
Deconvolutive Radon transform, Geophysics, 82 (2017), V117-V125.
doi: 10.1190/geo2016-0377.1. |
[11] |
T. Goldstein and S. Osher,
The split Bregman method for l1 regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343.
doi: 10.1137/080725891. |
[12] |
D. Hampson,
Inverse velocity stacking for multiple elimination, 56th Annual International Meeting, SEG, Expanded Abstracts, (1986), 422-424.
doi: 10.1190/1.1893060. |
[13] |
P. E. Hart,
How the Hough transform was invented, IEEE Signal Processing Magazine, 26 (2008), 18-22.
|
[14] |
P. Herrmann, T. Mojesky, M. Magesan and P. Hugonnet,
De-aliased, high-resolution Radon transforms, 70th Annual International Meeting, SEG, Expanded Abstracts, 19 (2000), 1953-1956.
doi: 10.1190/1.1815818. |
[15] |
K. Hokstad and R. Sollie,
3D surface-related multiple elimination using parabolic sparse inversion, Geophysics, 71 (2006), V145-V152.
doi: 10.1190/1.2345050. |
[16] |
J. Hsieh,
Computed Tomography Principles, Design, Artifacts, and Recent Advances, 2nd Edition, 2nd revised ed. , SPIE Publications, Bellingham, WA, 2015.
doi: 10.1117/3.2197756. |
[17] |
J. Hu, S. Fomel, L. Demanet and L. Ying,
A fast butterfly algorithm for generalized Radon transforms, Geophysics, 78 (2013), U41-U51.
doi: 10.1190/geo2012-0240.1. |
[18] |
C. Kostov,
Toeplitz structure in slant-stack inversion, SEG Technical Program Expanded Abstracts, (1990), 1618-1621.
doi: 10.1190/1.1890075. |
[19] |
W. Lu,
An accelerated sparse time-invariant Radon transform in the mixed frequency-time domain based on iterative 2D model shrinkage, Geophysics, 78 (2013), V147-V155.
doi: 10.1190/geo2012-0439.1. |
[20] |
R. M. Mersereau,
Recovering multidimensional signals from their projections, Computer Graphics and Image Processing, 2 (1973), 179-195.
doi: 10.1016/0146-664X(73)90026-9. |
[21] |
V. Nikitin, F. Andersson, M. Carlsson and A. Duchkov,
Fast hyperbolic Radon transform by log-polar convolutions, SEG Technical Program Expanded Abstracts, (2016), 4534-4539.
doi: 10.1190/segam2016-13943010.1. |
[22] |
M. D. Sacchi and M. Porsani,
Fast high resolution parabolic Radon transform, SEG Technical
Program Expanded Abstracts, (1999), 1477-1480.
doi: 10.1190/1.1820798. |
[23] |
M. Sacchi and T. Ulrych,
High-resolution velocity gathers and offset space reconstruction, Geophysics, 60 (1995), 1169-1177.
doi: 10.1190/1.1443845. |
[24] |
M. Sacchi and T. Ulrych,
Improving resolution of Radon operators using a model re-weighted least squares procedure, Journal of Seismic Exploration, 4 (1995), 315-328.
|
[25] |
M. Schonewille and A. Duijndam,
Parabolic Radon transform, sampling and efficiency, Geophysics, 66 (2001), 667-678.
doi: 10.1190/1.1444957. |
[26] |
J. R. Thorson and J. F. Claerbout,
Velocity-stack and slant-stack stochastic inversion, Geophysics, 50 (1985), 2727-2741.
doi: 10.1190/1.1441893. |
[27] |
D. Trad, T. Ulrych and M. Sacchi,
Latest views of the sparse Radon transform, Geophysics, 68 (2003), 386-399.
doi: 10.1190/1.1543224. |
[28] |
S. Treitel, P. Gutowski and D. Wagner,
Plane-wave decomposition of seismograms, Geophysics, 47 (1982), 1375-1401.
doi: 10.1190/1.1441287. |
[29] |
O. Yilmaz,
Velocity stack processing, SEG Technical Program Expanded Abstracts, (1988), 1013-1016.
doi: 10.1190/1.1892186. |
[30] |
O. Yilmaz,
Seismic Data Analysis: Processing, Inversion, and Interpretation of Seismic Data, 2nd edition, Investigations in geophysics, Society of Exploration Geophysicists, Tulsa, OK, 2001.
doi: 10.1190/1.9781560801580. |
show all references
References:
[1] |
A. Averbuch, R. Coifman, D. L. Donoho, M. Israeli and Y. Shkonisky,
A framework for discrete integral transformation Ⅰ- the pseudo-polar Fourier transform, SIAM J. of Scientific Computing, 30 (2008), 764-784.
doi: 10.1137/060650283. |
[2] |
A. Averbuch, R. Coifman, D. L. Donoho, M. Israeli, Y. Shkonisky and I. Sedelnikov,
A framework for discrete integral transformation Ⅱ-the 2D discrete Radon transform, SIAM J. of Scientific Computing, 30 (2008), 785-803.
doi: 10.1137/060650301. |
[3] |
S. Basu and Y. Bresler,
$O(N^3 \log N)$ backprojection algorithm for the 3D Radon transform, IEEE Trans. Medical Imaging, 21 (2002), 76-88.
|
[4] |
A. Beck and M. Teboulle,
A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sciences, 2 (2009), 183-202.
doi: 10.1137/080716542. |
[5] |
G. Beylkin,
Discrete Radon transform, IEEE Transactions on Acoustics, Speech and Signal Processing, 35 (1987), 162-172.
doi: 10.1109/TASSP.1987.1165108. |
[6] |
P. W. Cary,
The simplest discrete Radon transform, 68th Annual International Meeting, SEG, Expanded Abstracts, (1998), 1999-2002.
doi: 10.1190/1.1820335. |
[7] |
R. H. Chan and M. K. Ng,
Conjugate gradient methods for Toeplitz systems, SIAM Review, 38 (1996), 427-482.
doi: 10.1137/S0036144594276474. |
[8] |
S. Chen, D. L. Donoho and M. Saunders,
Atomic decomposition by basis pursuit, SIAM J. of Scientific Computation, 20 (1998), 33-61.
doi: 10.1137/S1064827596304010. |
[9] |
A. Gholami,
Nonconvex compressed sensing with frequency mask for seismic data reconstruction and denoising, Geophysical Prospecting, 62 (2014), 1389-1405.
|
[10] |
A. Gholami,
Deconvolutive Radon transform, Geophysics, 82 (2017), V117-V125.
doi: 10.1190/geo2016-0377.1. |
[11] |
T. Goldstein and S. Osher,
The split Bregman method for l1 regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343.
doi: 10.1137/080725891. |
[12] |
D. Hampson,
Inverse velocity stacking for multiple elimination, 56th Annual International Meeting, SEG, Expanded Abstracts, (1986), 422-424.
doi: 10.1190/1.1893060. |
[13] |
P. E. Hart,
How the Hough transform was invented, IEEE Signal Processing Magazine, 26 (2008), 18-22.
|
[14] |
P. Herrmann, T. Mojesky, M. Magesan and P. Hugonnet,
De-aliased, high-resolution Radon transforms, 70th Annual International Meeting, SEG, Expanded Abstracts, 19 (2000), 1953-1956.
doi: 10.1190/1.1815818. |
[15] |
K. Hokstad and R. Sollie,
3D surface-related multiple elimination using parabolic sparse inversion, Geophysics, 71 (2006), V145-V152.
doi: 10.1190/1.2345050. |
[16] |
J. Hsieh,
Computed Tomography Principles, Design, Artifacts, and Recent Advances, 2nd Edition, 2nd revised ed. , SPIE Publications, Bellingham, WA, 2015.
doi: 10.1117/3.2197756. |
[17] |
J. Hu, S. Fomel, L. Demanet and L. Ying,
A fast butterfly algorithm for generalized Radon transforms, Geophysics, 78 (2013), U41-U51.
doi: 10.1190/geo2012-0240.1. |
[18] |
C. Kostov,
Toeplitz structure in slant-stack inversion, SEG Technical Program Expanded Abstracts, (1990), 1618-1621.
doi: 10.1190/1.1890075. |
[19] |
W. Lu,
An accelerated sparse time-invariant Radon transform in the mixed frequency-time domain based on iterative 2D model shrinkage, Geophysics, 78 (2013), V147-V155.
doi: 10.1190/geo2012-0439.1. |
[20] |
R. M. Mersereau,
Recovering multidimensional signals from their projections, Computer Graphics and Image Processing, 2 (1973), 179-195.
doi: 10.1016/0146-664X(73)90026-9. |
[21] |
V. Nikitin, F. Andersson, M. Carlsson and A. Duchkov,
Fast hyperbolic Radon transform by log-polar convolutions, SEG Technical Program Expanded Abstracts, (2016), 4534-4539.
doi: 10.1190/segam2016-13943010.1. |
[22] |
M. D. Sacchi and M. Porsani,
Fast high resolution parabolic Radon transform, SEG Technical
Program Expanded Abstracts, (1999), 1477-1480.
doi: 10.1190/1.1820798. |
[23] |
M. Sacchi and T. Ulrych,
High-resolution velocity gathers and offset space reconstruction, Geophysics, 60 (1995), 1169-1177.
doi: 10.1190/1.1443845. |
[24] |
M. Sacchi and T. Ulrych,
Improving resolution of Radon operators using a model re-weighted least squares procedure, Journal of Seismic Exploration, 4 (1995), 315-328.
|
[25] |
M. Schonewille and A. Duijndam,
Parabolic Radon transform, sampling and efficiency, Geophysics, 66 (2001), 667-678.
doi: 10.1190/1.1444957. |
[26] |
J. R. Thorson and J. F. Claerbout,
Velocity-stack and slant-stack stochastic inversion, Geophysics, 50 (1985), 2727-2741.
doi: 10.1190/1.1441893. |
[27] |
D. Trad, T. Ulrych and M. Sacchi,
Latest views of the sparse Radon transform, Geophysics, 68 (2003), 386-399.
doi: 10.1190/1.1543224. |
[28] |
S. Treitel, P. Gutowski and D. Wagner,
Plane-wave decomposition of seismograms, Geophysics, 47 (1982), 1375-1401.
doi: 10.1190/1.1441287. |
[29] |
O. Yilmaz,
Velocity stack processing, SEG Technical Program Expanded Abstracts, (1988), 1013-1016.
doi: 10.1190/1.1892186. |
[30] |
O. Yilmaz,
Seismic Data Analysis: Processing, Inversion, and Interpretation of Seismic Data, 2nd edition, Investigations in geophysics, Society of Exploration Geophysicists, Tulsa, OK, 2001.
doi: 10.1190/1.9781560801580. |









Backslash | Levinson | PCG-Chan | GFST | |||||
Time | Time | Time | Time | speed-up | Error | |||
Backslash | Levinson | PCG-Chan | ||||||
4.6480 | 6.3021 | 1.2668 | 0.0181 | 256 | 348 | 69 | 43e-7 | |
49.485 | 32.273 | 8.3074 | 0.0615 | 804 | 524 | 135 | 24e-7 | |
595.83 | 179.41 | 33.672 | 0.2447 | 2434 | 733 | 137 | 11e-7 | |
7707.0 | 1384.2 | 290.30 | 1.0561 | 7297 | 1310 | 274 | 60e-8 |
Backslash | Levinson | PCG-Chan | GFST | |||||
Time | Time | Time | Time | speed-up | Error | |||
Backslash | Levinson | PCG-Chan | ||||||
4.6480 | 6.3021 | 1.2668 | 0.0181 | 256 | 348 | 69 | 43e-7 | |
49.485 | 32.273 | 8.3074 | 0.0615 | 804 | 524 | 135 | 24e-7 | |
595.83 | 179.41 | 33.672 | 0.2447 | 2434 | 733 | 137 | 11e-7 | |
7707.0 | 1384.2 | 290.30 | 1.0561 | 7297 | 1310 | 274 | 60e-8 |
Number of iterations | Average time per iteration | Total time | |
83 | 0.0332 | 2.7516 | |
70 | 0.1589 | 11.122 | |
65 | 0.6638 | 43.150 | |
58 | 2.4840 | 144.07 |
Number of iterations | Average time per iteration | Total time | |
83 | 0.0332 | 2.7516 | |
70 | 0.1589 | 11.122 | |
65 | 0.6638 | 43.150 | |
58 | 2.4840 | 144.07 |
$N_t$ | Time | Speed-up | Error | |
Direct sums | GFST | |||
0.2844 | 0.0112 | 25 | 12e-5 | |
2.5050 | 0.0497 | 50 | 11e-6 | |
17.926 | 0.2139 | 84 | 33e-7 | |
137.45 | 0.8475 | 162 | 34e-7 |
$N_t$ | Time | Speed-up | Error | |
Direct sums | GFST | |||
0.2844 | 0.0112 | 25 | 12e-5 | |
2.5050 | 0.0497 | 50 | 11e-6 | |
17.926 | 0.2139 | 84 | 33e-7 | |
137.45 | 0.8475 | 162 | 34e-7 |
[1] |
Simon Gindikin. A remark on the weighted Radon transform on the plane. Inverse Problems and Imaging, 2010, 4 (4) : 649-653. doi: 10.3934/ipi.2010.4.649 |
[2] |
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 |
[3] |
Michael Krause, Jan Marcel Hausherr, Walter Krenkel. Computing the fibre orientation from Radon data using local Radon transform. Inverse Problems and Imaging, 2011, 5 (4) : 879-891. doi: 10.3934/ipi.2011.5.879 |
[4] |
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 |
[5] |
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 |
[6] |
C E Yarman, B Yazıcı. A new exact inversion method for exponential Radon transform using the harmonic analysis of the Euclidean motion group. Inverse Problems and Imaging, 2007, 1 (3) : 457-479. doi: 10.3934/ipi.2007.1.457 |
[7] |
Jean-François Crouzet. 3D coded aperture imaging, ill-posedness and link with incomplete data radon transform. Inverse Problems and Imaging, 2011, 5 (2) : 341-353. doi: 10.3934/ipi.2011.5.341 |
[8] |
Jan Boman. A local uniqueness theorem for weighted Radon transforms. Inverse Problems and Imaging, 2010, 4 (4) : 631-637. doi: 10.3934/ipi.2010.4.631 |
[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] |
Fahd Jarad, Thabet Abdeljawad. Generalized fractional derivatives and Laplace transform. Discrete and Continuous Dynamical Systems - S, 2020, 13 (3) : 709-722. doi: 10.3934/dcdss.2020039 |
[12] |
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 |
[13] |
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 |
[14] |
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 |
[15] |
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 |
[16] |
Siamak RabieniaHaratbar. Support theorem for the Light-Ray transform of vector fields on Minkowski spaces. Inverse Problems and Imaging, 2018, 12 (2) : 293-314. doi: 10.3934/ipi.2018013 |
[17] |
Venkateswaran P. Krishnan, Plamen Stefanov. A support theorem for the geodesic ray transform of symmetric tensor fields. Inverse Problems and Imaging, 2009, 3 (3) : 453-464. doi: 10.3934/ipi.2009.3.453 |
[18] |
William Guo. The Laplace transform as an alternative general method for solving linear ordinary differential equations. STEM Education, 2021, 1 (4) : 309-329. doi: 10.3934/steme.2021020 |
[19] |
Jae Gil Choi, David Skoug. Algebraic structure of the $ L_2 $ analytic Fourier–Feynman transform associated with Gaussian paths on Wiener space. Communications on Pure and Applied Analysis, 2020, 19 (7) : 3829-3842. doi: 10.3934/cpaa.2020169 |
[20] |
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 |
2020 Impact Factor: 1.639
Tools
Metrics
Other articles
by authors
[Back to Top]