## Gridding Based Direct Fourier Inversion Of The Three-PDF Download

• Date:12 Jan 2020
• Views:94
• Downloads:0
• Pages:11
• Size:306.22 KB

Share Pdf : Gridding Based Direct Fourier Inversion Of The Three

Download and Preview : Gridding Based Direct Fourier Inversion Of The Three

Report CopyRight/DMCA Form For : Gridding Based Direct Fourier Inversion Of The Three

Transcription:

500 J Opt Soc Am A Vol 21 No 4 April 2004 Penczek et al. erative method such as the simultaneous iterative recon weighting scheme is to partition the sampled region in. struction technique SIRT 4 or the algebraic reconstruc Fourier space into small sampling cells with one cell. tion technique 5 Methods of this class can be very around each grid point and to choose the weights as the. accurate but are rather slow volumes of these sampling cells 13 The Voronoi diagram. Another general strategy is to evaluate a discrete ver of the grid points provides a good partitioning of the. sion of the expression Qg where Q is the or an approxi sampled region In principle the computation of Voronoi. mate inverse of P The widely used weighted or fil diagrams is feasible but it can be time consuming par. tered backprojection methods6 belong to this class of ticularly in 3 D applications. reconstruction algorithms The random and nonuniform The gridding method has other applications in for ex. distribution of the projection directions is taken into ac ample resampling and interpolation Reversing the. count by a weighting filter function built into these steps of the gridding method yields a method for calculat. methods Weighted backprojection methods are still ing a nonuniformly sampled version of the Fourier trans. relatively slow and as a result of difficulties with con form of some function h from a uniformly sampled version. structing a proper weighting function they do not per of h 14 We call this the reverse gridding method. form well for nonuniformly distributed projections In the case of cryo EM the calculation of the gridding. So called direct Fourier methods are also based on the weights by means of the 3 D Voronoi diagram of the non. second general strategy These methods exploit the pro uniformly spaced grid points for Ff would lead to an accu. jection theorem for the 3 D ray transform which states rate but slow direct Fourier method The reconstruction. that the two dimensional 2 D Fourier transform of a algorithm that we present in the main part of this paper. projection of f equals Ff the 3 D Fourier transform of f on is a variation of this slow direct Fourier method that im. a central plane perpendicular to the projection direction proves the speed and maintains the accuracy Specifi. Thus by numerically 2 D Fourier transforming each pro cally we use the 2 D reverse gridding method rather. jection one obtains a discrete approximation to Ff on than the 2 D FFT to compute the Fourier transform of. some 3 D grid and a subsequent numerical 3 D inverse each projection on a 2 D polar grid rather than a 2 D Car. Fourier transform gives a discrete approximation to f tesian grid In this way we obtain Ff on a 3 D spherical. Typically the projections of f are available on a 2 D Car grid where the grid points are located both on centered. tesian grid and the 2 D fast Fourier transform FFT may spheres and on straight lines through the origin This. be used for the Fourier transformation of the projections makes it possible to partition the sampled region into. making the preprocessing step very fast If the 3 D in suitable sampling cells through the computation of a 2 D. verse Fourier transform could be realized by means of the Voronoi diagram on the unit sphere rather than of a 3 D. 3 D inverse FFT one would indeed have a very fast recon Voronoi diagram in Euclidean space A fast algorithm for. struction algorithm Unfortunately the preprocessing computing Voronoi diagrams on the unit sphere is. step yields Ff on a nonuniform grid and the 3 D inverse available 15. FFT is not immediately applicable There are several The remainder of this paper is organized as follows. possible ways to overcome this obstacle Section 2 contains preparatory material In particular. One possibility is to resample the nonuniformly we provide an overview of gridding techniques and a brief. sampled version of Ff onto a 3 D Cartesian grid by some account of spherical Voronoi diagrams In Section 3 we. form of interpolation and to apply the 3 D inverse FFT to state the reconstruction problem and describe our algo. this resampled version of Ff For example Grigorieff rithm for solving it Test results are provided and dis. used a modified trilinear interpolation scheme 7 Simple cussed in Section 4 Section 5 concludes the paper with. interpolation methods have been found to give inaccurate remarks concerning possible improvements of the method. results although more sophisticated interpolation and its possible impact on single particle analysis. schemes can go a long way to improve the accuracy 8 9. Unfortunately the recommended window size makes,them impractical for most applications 10. Another method for reconstructing f from a nonuni 2 PRELIMINARIES. formly sampled version of Ff is the 3 D gridding A Notation. method 11 13 With this method one first computes an ap The symbols R R Z Z and C denote the sets of real. proximation to the convolution Fw Ff on an appro positive real integer positive integer and complex num. priate Cartesian grid where Fw is a judiciously chosen bers respectively Points in Rd are denoted by boldface. convolution kernel then one uses the 3 D inverse FFT to letters such as a or N The components of a Rd are. compute an approximation to wf F 1 Fw Ff on a denoted by a 1 a d Expressions such as a b a b. Cartesian grid and finally one divides this approxima a 1 or a 1 are understood componentwise The or. tion to wf by w For the convolution step also known as thogonal complement of a Rd is the set a x. gridding the data need to be multiplied with proper Rd a x 0 if a 0 then a is the central hyper. gridding weights designed to compensate for the non plane perpendicular to a The Euclidean norm of a is de. uniform distribution of the grid points Good convolution noted by a The d dimensional d D volume of a region. kernels have a small support so that the gridding method A Rd is denoted by vol A The closed centered ball in. is still fast provided that the computation of the gridding Rd with radius r is denoted by B d r The surface of the. weights is also fast The accuracy of the method is ball B d 1 is the unit sphere in Rd and conventionally de. strongly influenced by the distribution of the sampling noted by S d 1 The terms Cartesian grid and uniform. points and by the choice of the gridding weights A good grid are used interchangeably. Penczek et al Vol 21 No 4 April 2004 J Opt Soc Am A 501. B Fourier Transform b 1 aN 6, The d D Fourier transform of a sufficiently regular func. tion h Rd C is defined by Note that this auxiliary grid fills the interval. bN 2 bN 2 1 2a 1 2a which is indepen,dent of N Third we need a window function w Rd. Fh y h x exp i2 x y dx 1 R with support in an interval of the form. Rd Wb 2 Wb 2 where W Z is small say W 4 or,W 6 The weighting function w F 1 w must be posi. tive in Ka 2 Ka 2 A recommendable window func,We also write h instead of Fh The inverse Fourier.
tion is the d D separable Kaiser Bessel window 11 13 Us. transform is given by,ing the abbreviations r Ka 2 and s Wb 2 we may. write this bell shaped window function as,h x F 1 h x h y exp i2 x y dy 2 d. I 0 2 r s 1 y s 2 1 2,C Ray Transform 0, The d D ray transform of a sufficiently regular function y s s. h Rd C is defined by16 y s s, where I 0 is the zero order modified Bessel function and. Ph u h u t dt S d 1 u R d,is a parameter In the common case W 6 a.
R good choice is 1 25 The weighting function associ. 3 ated with w KB is,The function d,sinh 2 r s 1 x r 2 1 2. 1 2 r s 1 x r 2 1 2, is called a projection of h or more precisely the d The gridding method itself proceeds in three steps In. 1 D parallel beam projection of h with direction the first step also known as gridding one computes the. The ray transform is related to the Fourier transform by numbers. the projection theorem 16 which states that,g n c h y w nb y. j j j j N 2 n N 2, i e each Fourier transformed projection of h yields the. Fourier transform of h on the central hyperplane whose In the second step one uses the d D inverse FFT to com. normal is parallel to the projection direction pute the numbers. D Gridding Method,g k b 1 b d g n exp i2 k n N, The following problem is often encountered in scientific n N 2.
and technical applications We are given a sampled ver. sion h yj j J of the Fourier transform h of some K 2 k K 2 10. function h Rd C where J is some finite index set and. the grid points yj Rd form a possibly nonuniform sam To do this one cyclically shifts the input sequence. pling grid in some region S Rd We wish to recon b 1 b d g n N 2 n N 2 by N 2 applies the d D in. struct h on a Cartesian grid of the form ka k verse FFT cyclically shifts the output sequence. Zd K 2 k K 2 where a R d, is the grid spac g k N 2 k N 2 by N 2 and extracts the interest. ing and K Z The gridding method 11 13 17 outlined ing portion g k K 2 k K 2 In the third step of. below is a potentially efficient and accurate method for the gridding method one simply computes the numbers. solving this kind of problem, The method involves a number of parameters First h k g k w ka K 2 k K 2 11. we need a set of gridding weights c j R j J A, general recipe for the construction of good gridding The sequence h k K 2 k K 2 constitutes the out. weights is given below Second we need an even and put of the gridding method As shown in Ref 18 regard. FFT friendly N Z with N K The ratio N K is less of the choice of the gridding weights if the remaining. called the oversampling factor The oversampling factor parameters are properly chosen for example as indicated. should be greater than 1 but need not be greater than 2 above then the numbers h k provide highly accurate ap. The parameters N and a define an auxiliary Cartesian proximations to the numbers s h ka K 2 k. grid nb n Zd N 2 n N 2 with grid spacing K 2 where. 502 J Opt Soc Am A Vol 21 No 4 April 2004 Penczek et al. In the second step the sequence g k K 2 k K 2 is, j exp i2 x yj 12 symmetrically zero padded to yield the sequence. g k N 2 k N 2 and the d D FFT is used to com,pute the numbers.
s h x c h y exp i2 x y,j j j 13 N 2,g n a 1 a d g k exp i2 k n N. Thus the similarity between s h the function delivered k N 2. by the gridding method and h the function to be recon. N 2 k N 2 17, structed depends on the point spread function s which. depends in turn on the grid points yj and the gridding In the third step one computes the numbers. weights c j The grid points are often imposed or con N 2. strained by the underlying application but the choice of. the gridding weights is under our control A general. h j b 1 b d,g nw yj nb j J 18, mathematical theory that allows one to derive the shape The constant weight b 1 b d in Eq 18 plays the role of. of s from the yj and the cj seems to be missing, the gridding weights c j in Eq 9 The sequence h j j. In Ref 18 it was proposed to choose the gridding,J constitutes the output of the reverse gridding.
weights such that the right hand side of Eq 13 becomes. method An argument similar to the one presented in. a Riemann sum approximating the integral, Ref 18 for the gridding method leads to the conclusion. h y exp i2 x y dy 14, that if the parameters are properly chosen for example. as suggested for the gridding method the numbers h j. provide highly accurate approximations to the numbers. which is in turn an approximation to h x To find such s a K h yj j J where. weights we need to partition the sampled region S into K 2 1. sampling cells C j such that yk C j if and only if k j. and choose c j as the volume of cell C j i e s a K y a 1 a d. exp i2 ka y 19, c j vol C j 15 This point spread function is closely related to the well. 19 known Dirichlet kernel If a is sufficiently small and K. The Voronoi diagram of the sampling points provides a. good partitioning of S Depending on the sampling grid sufficiently large s a K h will resemble h. faster methods for partitioning S may exist Close relatives of the reverse gridding method have. In the recent mathematical literature several numeri also been studied in Refs 20 22. cal methods for the efficient evaluation of trigonometric There is an obvious dual version of the reverse gridding. sums of the form g k j J g j exp i2 ka yj have been method that allows one to compute a function h on a non. investigated 20 22 These methods are closely related to uniform grid from a uniformly sampled version of Fh. the gridding method the numbers g j in the above trigo We obtain a reasonably fast and potentially highly accu. rate method for the nonuniform resampling of a uni. nometric sum corresponding to the numbers c j h yj in. formly sampled function h if we apply the d D FFT to this. Eq 11 The choice of the gridding weights has not been. uniformly sampled version of h before invoking the re. discussed in these references, verse gridding method We obtain a reasonably fast and. There is an obvious dual version of the gridding, potentially highly accurate method for the nonuniform re.
method that allows one to compute the Fourier transform. sampling of a nonuniformly sampled function h if we re. Fh of some function h on a uniform grid from a nonuni. place the FFT by the dual gridding method,formly sampled version of h. If we apply a d D inverse FFT to the output of the dual. F Spherical Voronoi Diagrams, gridding method we obtain a reasonably fast and poten. Gridding based direct Fourier inversion of the three dimensional ray transform Pawel A Penczek Department of Biochemistry and Molecular Biology The University of