2017, 11(3): 501-519. doi: 10.3934/ipi.2017023

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

* Corresponding author: Ali Gholami

Received  April 2015 Revised  January 2017 Published  April 2017

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.
Citation: 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
References:
[1]

A. Averbuch, R. Coifman, D. L. Donoho, M. Israeli, Y. Shkonisky, A framework for discrete integral transformation Ⅰ- the pseudo-polar Fourier transform, SIAM J. of Scientific Computing, 30 (2008), 764-784.

[2]

A. Averbuch, R. Coifman, D. L. Donoho, M. Israeli, Y. Shkonisky, I. Sedelnikov, A framework for discrete integral transformation Ⅱ-the 2D discrete Radon transform, SIAM J. of Scientific Computing, 30 (2008), 785-803.

[3]

S. Basu, 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, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sciences, 2 (2009), 183-202.

[5]

G. Beylkin, Discrete Radon transform, IEEE Transactions on Acoustics, Speech and Signal Processing, 35 (1987), 162-172.

[6]

P. W. Cary, The simplest discrete Radon transform, 68th Annual International Meeting, SEG, Expanded Abstracts, (1998), 1999-2002.

[7]

R. H. Chan, M. K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Review, 38 (1996), 427-482.

[8]

S. Chen, D. L. Donoho, M. Saunders, Atomic decomposition by basis pursuit, SIAM J. of Scientific Computation, 20 (1998), 33-61.

[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.

[11]

T. Goldstein, S. Osher, The split Bregman method for l1 regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343.

[12]

D. Hampson, Inverse velocity stacking for multiple elimination, 56th Annual International Meeting, SEG, Expanded Abstracts, (1986), 422-424.

[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, P. Hugonnet, De-aliased, high-resolution Radon transforms, 70th Annual International Meeting, SEG, Expanded Abstracts, 19 (2000), 1953-1956.

[15]

K. Hokstad, R. Sollie, 3D surface-related multiple elimination using parabolic sparse inversion, Geophysics, 71 (2006), V145-V152.

[16]

J. Hsieh, Computed Tomography Principles, Design, Artifacts, and Recent Advances 2nd Edition, 2nd revised ed. , SPIE Publications, Bellingham, WA, 2015.

[17]

J. Hu, S. Fomel, L. Demanet, L. Ying, A fast butterfly algorithm for generalized Radon transforms, Geophysics, 78 (2013), U41-U51.

[18]

C. Kostov, Toeplitz structure in slant-stack inversion, SEG Technical Program Expanded Abstracts, (1990), 1618-1621.

[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.

[20]

R. M. Mersereau, Recovering multidimensional signals from their projections, Computer Graphics and Image Processing, 2 (1973), 179-195.

[21]

V. Nikitin, F. Andersson, M. Carlsson, A. Duchkov, Fast hyperbolic Radon transform by log-polar convolutions, SEG Technical Program Expanded Abstracts, (2016), 4534-4539.

[22]

M. D. Sacchi, M. Porsani, Fast high resolution parabolic Radon transform, SEG Technical Program Expanded Abstracts, (1999), 1477-1480.

[23]

M. Sacchi, T. Ulrych, High-resolution velocity gathers and offset space reconstruction, Geophysics, 60 (1995), 1169-1177.

[24]

M. Sacchi, 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, A. Duijndam, Parabolic Radon transform, sampling and efficiency, Geophysics, 66 (2001), 667-678.

[26]

J. R. Thorson, J. F. Claerbout, Velocity-stack and slant-stack stochastic inversion, Geophysics, 50 (1985), 2727-2741.

[27]

D. Trad, T. Ulrych, M. Sacchi, Latest views of the sparse Radon transform, Geophysics, 68 (2003), 386-399.

[28]

S. Treitel, P. Gutowski, D. Wagner, Plane-wave decomposition of seismograms, Geophysics, 47 (1982), 1375-1401.

[29]

O. Yilmaz, Velocity stack processing, SEG Technical Program Expanded Abstracts, (1988), 1013-1016.

[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.

show all references

References:
[1]

A. Averbuch, R. Coifman, D. L. Donoho, M. Israeli, Y. Shkonisky, A framework for discrete integral transformation Ⅰ- the pseudo-polar Fourier transform, SIAM J. of Scientific Computing, 30 (2008), 764-784.

[2]

A. Averbuch, R. Coifman, D. L. Donoho, M. Israeli, Y. Shkonisky, I. Sedelnikov, A framework for discrete integral transformation Ⅱ-the 2D discrete Radon transform, SIAM J. of Scientific Computing, 30 (2008), 785-803.

[3]

S. Basu, 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, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sciences, 2 (2009), 183-202.

[5]

G. Beylkin, Discrete Radon transform, IEEE Transactions on Acoustics, Speech and Signal Processing, 35 (1987), 162-172.

[6]

P. W. Cary, The simplest discrete Radon transform, 68th Annual International Meeting, SEG, Expanded Abstracts, (1998), 1999-2002.

[7]

R. H. Chan, M. K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Review, 38 (1996), 427-482.

[8]

S. Chen, D. L. Donoho, M. Saunders, Atomic decomposition by basis pursuit, SIAM J. of Scientific Computation, 20 (1998), 33-61.

[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.

[11]

T. Goldstein, S. Osher, The split Bregman method for l1 regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343.

[12]

D. Hampson, Inverse velocity stacking for multiple elimination, 56th Annual International Meeting, SEG, Expanded Abstracts, (1986), 422-424.

[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, P. Hugonnet, De-aliased, high-resolution Radon transforms, 70th Annual International Meeting, SEG, Expanded Abstracts, 19 (2000), 1953-1956.

[15]

K. Hokstad, R. Sollie, 3D surface-related multiple elimination using parabolic sparse inversion, Geophysics, 71 (2006), V145-V152.

[16]

J. Hsieh, Computed Tomography Principles, Design, Artifacts, and Recent Advances 2nd Edition, 2nd revised ed. , SPIE Publications, Bellingham, WA, 2015.

[17]

J. Hu, S. Fomel, L. Demanet, L. Ying, A fast butterfly algorithm for generalized Radon transforms, Geophysics, 78 (2013), U41-U51.

[18]

C. Kostov, Toeplitz structure in slant-stack inversion, SEG Technical Program Expanded Abstracts, (1990), 1618-1621.

[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.

[20]

R. M. Mersereau, Recovering multidimensional signals from their projections, Computer Graphics and Image Processing, 2 (1973), 179-195.

[21]

V. Nikitin, F. Andersson, M. Carlsson, A. Duchkov, Fast hyperbolic Radon transform by log-polar convolutions, SEG Technical Program Expanded Abstracts, (2016), 4534-4539.

[22]

M. D. Sacchi, M. Porsani, Fast high resolution parabolic Radon transform, SEG Technical Program Expanded Abstracts, (1999), 1477-1480.

[23]

M. Sacchi, T. Ulrych, High-resolution velocity gathers and offset space reconstruction, Geophysics, 60 (1995), 1169-1177.

[24]

M. Sacchi, 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, A. Duijndam, Parabolic Radon transform, sampling and efficiency, Geophysics, 66 (2001), 667-678.

[26]

J. R. Thorson, J. F. Claerbout, Velocity-stack and slant-stack stochastic inversion, Geophysics, 50 (1985), 2727-2741.

[27]

D. Trad, T. Ulrych, M. Sacchi, Latest views of the sparse Radon transform, Geophysics, 68 (2003), 386-399.

[28]

S. Treitel, P. Gutowski, D. Wagner, Plane-wave decomposition of seismograms, Geophysics, 47 (1982), 1375-1401.

[29]

O. Yilmaz, Velocity stack processing, SEG Technical Program Expanded Abstracts, (1988), 1013-1016.

[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.

Figure 1.  Graphical representation of the Fourier slice theorem. The seismogram $v$ includes a linear event. The projection of $v$ along the slope of the event is the red line shown in $u$ which is the IFT of the radial slice taken from $\hat{v}$ using relation $k_x=fp$
Figure 2.  Graphical representation of the generalized Fourier slice theorem. The seismogram $v$ includes a linear event. The Fourier transform of a trace at offset $x$ is the same as the radical slice taken through the 2-D Fourier transform of its linear Radon transform $u$ using the relation $k_p=f x$
Figure 3.  Relation between the grid points of the Radon plane $\hat{u}(f,k_p)$ (in green) and those of the data $\hat{v}(f,x)$ (in black) corresponding to the forward linear (a) and parabolic (c) Radon transforms. (b) and (d) show the grid points for the inverse transformations
Figure 4.  Simulated 2-D data sets including linear (a) and parabolic (b) events. For both data sets $N_t=N_x=1024$. (c) and (d) are the $f-x$ representation of the data (absolute value). The green paths show constant wavenumber of the corresponding Radon panel. The proposed non-sparse and sparse Radon transforms have been applied to these data and the results are shown in Figures 5 and 6
Figure 5.  Non-sparse (a) and sparse (b) linear Radon transform of the data shown in Figure 4(a). (c) and (d) show the predicted data. The sparse solution has been obtained via 20 Bregman iterations with computational time = 1.2 seconds
Figure 6.  Non-sparse (a) and sparse (b) parabolic Radon transforms of the data shown in Figure 4(b). (c) and (d) show the predicted data. The sparse solution has been obtained by 20 Bregman iterations with computational time = 1.2 seconds
Figure 7.  (a) and (b) show wiggle plot of the noise contaminated seismic data shown in Figure 4 (SNR=-5 dB). (c) and (d) show denoised data by the proposed sparse Radon transform
Figure 8.  (a) and (b) show decimated seismic data shown in Figure 4, generated by randomly removing 98 percent of the traces (1000 out of 1024). (c) and (d) show reconstructed data by the proposed sparse Radon transforms
Figure 9.  A field CMP gather, NMO corrected using the velocity of primaries. Note that the primary waves are flatted (with $p$ values clustered around zero) but multiples show parabolic moveouts
Figure 10.  (a) Sparse parabolic Radon transform of the field data (Figure 7), obtained by generalized Fourier slice theorem, and (b) the corresponding predicted data. (c) Separated multiples, corresponding to the coefficients enclosed by the rectangle in (a). (d) Separated primaries, obtained by subtraction of (c) from the original wavefield
Figure 11.  (a) Sparse parabolic Radon transform of the field data (Figure 7), obtained by direct method and FISTA, and (b) the corresponding predicted data. (c) Separated multiples, corresponding to the coefficients enclosed by the rectangle in (a). (d) Separated primaries, obtained by subtraction of (c) from the original wavefield
Table 1.  Computational time (in sec) for the (non-sparse or least squares) forward parabolic Radon transform via the generalized Fourier slice theorem (GFST) and three linear solvers: Backslash, Levinson, and preconditioned conjugate gradient method with the Chan preconditioner, the speed-up gained over these solvers, and the mean-squared-error compared to the Backslash method.$N_t$ refers to the time length of the square data matrices for the experiments
Backslash Levinson PCG-Chan GFST
$N_t$ Time Time Time Time speed-up Error
Backslash Levinson PCG-Chan
$2^9$ 4.6480 6.3021 1.2668 0.0181 256 348 69 43e-7
$2^{10}$ 49.485 32.273 8.3074 0.0615 804 524 135 24e-7
$2^{11}$ 595.83 179.41 33.672 0.2447 2434 733 137 11e-7
$2^{12}$ 7707.0 1384.2 290.30 1.0561 7297 1310 274 60e-8
Backslash Levinson PCG-Chan GFST
$N_t$ Time Time Time Time speed-up Error
Backslash Levinson PCG-Chan
$2^9$ 4.6480 6.3021 1.2668 0.0181 256 348 69 43e-7
$2^{10}$ 49.485 32.273 8.3074 0.0615 804 524 135 24e-7
$2^{11}$ 595.83 179.41 33.672 0.2447 2434 733 137 11e-7
$2^{12}$ 7707.0 1384.2 290.30 1.0561 7297 1310 274 60e-8
Table 2.  Number of iterations, average time per iteration, and total computational time (in sec) for the sparse parabolic Radon transform via Algorithm 1.$N_t$ refers to the time length of the square data matrices for the experiments
$N_t$ Number of iterations Average time per iteration Total time
$2^9$ 83 0.0332 2.7516
$2^{10}$ 70 0.1589 11.122
$2^{11}$ 65 0.6638 43.150
$2^{12}$ 58 2.4840 144.07
$N_t$ Number of iterations Average time per iteration Total time
$2^9$ 83 0.0332 2.7516
$2^{10}$ 70 0.1589 11.122
$2^{11}$ 65 0.6638 43.150
$2^{12}$ 58 2.4840 144.07
Table 3.  Computational time (in sec) for the inverse parabolic Radon transform via direct sums and the generalized Fourier slice theorem (GFST), speed-up, and mean-squared-error compared to the direct method.$N_t$ refers to the time length of the square data matrices for the experiments
$N_t$ Time Speed-up Error
Direct sums GFST
$2^9$ 0.2844 0.0112 25 12e-5
$2^{10}$ 2.5050 0.0497 50 11e-6
$2^{11}$ 17.926 0.2139 84 33e-7
$2^{12}$ 137.45 0.8475 162 34e-7
$N_t$ Time Speed-up Error
Direct sums GFST
$2^9$ 0.2844 0.0112 25 12e-5
$2^{10}$ 2.5050 0.0497 50 11e-6
$2^{11}$ 17.926 0.2139 84 33e-7
$2^{12}$ 137.45 0.8475 162 34e-7
[1]

Simon Gindikin. A remark on the weighted Radon transform on the plane. Inverse Problems & Imaging, 2010, 4 (4) : 649-653. doi: 10.3934/ipi.2010.4.649

[2]

Michael Krause, Jan Marcel Hausherr, Walter Krenkel. Computing the fibre orientation from Radon data using local Radon transform. Inverse Problems & Imaging, 2011, 5 (4) : 879-891. doi: 10.3934/ipi.2011.5.879

[3]

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

[4]

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

[5]

Jean-François Crouzet. 3D coded aperture imaging, ill-posedness and link with incomplete data radon transform. Inverse Problems & Imaging, 2011, 5 (2) : 341-353. doi: 10.3934/ipi.2011.5.341

[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 & Imaging, 2007, 1 (3) : 457-479. doi: 10.3934/ipi.2007.1.457

[7]

Jan Boman. A local uniqueness theorem for weighted Radon transforms. Inverse Problems & Imaging, 2010, 4 (4) : 631-637. doi: 10.3934/ipi.2010.4.631

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Venkateswaran P. Krishnan, Plamen Stefanov. A support theorem for the geodesic ray transform of symmetric tensor fields. Inverse Problems & Imaging, 2009, 3 (3) : 453-464. doi: 10.3934/ipi.2009.3.453

[13]

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

[14]

Daniel Fusca. The Madelung transform as a momentum map. Journal of Geometric Mechanics, 2017, 9 (2) : 157-165. doi: 10.3934/jgm.2017006

[15]

Doǧan Çömez. The modulated ergodic Hilbert transform. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 325-336. doi: 10.3934/dcdss.2009.2.325

[16]

Sean Holman, Plamen Stefanov. The weighted Doppler transform. Inverse Problems & Imaging, 2010, 4 (1) : 111-130. doi: 10.3934/ipi.2010.4.111

[17]

Sebastian Reich, Seoleun Shin. On the consistency of ensemble transform filter formulations. Journal of Computational Dynamics, 2014, 1 (1) : 177-189. doi: 10.3934/jcd.2014.1.177

[18]

Gareth Ainsworth. The attenuated magnetic ray transform on surfaces. Inverse Problems & Imaging, 2013, 7 (1) : 27-46. doi: 10.3934/ipi.2013.7.27

[19]

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

[20]

Gareth Ainsworth. The magnetic ray transform on Anosov surfaces. Discrete & Continuous Dynamical Systems - A, 2015, 35 (5) : 1801-1816. doi: 10.3934/dcds.2015.35.1801

2016 Impact Factor: 1.094

Metrics

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

Other articles
by authors

[Back to Top]