title: Parallel data resampling and Fourier inversion by the scan-line method.
abstract: Fourier inversion is an efficient method for image reconstruction in a variety of applications, for example, in computed tomography and magnetic resonance imaging. Fourier inversion normally consists of two steps, interpolation of data onto a rectilinear grid, if necessary, and inverse Fourier transformation. Here, the authors present interpolation by the scan-line method, in which the interpolation algorithm is implemented in a form consisting only of row operations and data transposes. The two-dimensional inverse Fourier transformation can also be implemented with only row operations and data transposes. Accordingly, Fourier inversion can easily be implemented on a parallel computer that supports row operations and data transposes on row distributed data. The conditions under which the scan-line implementations are algorithmically equivalent to the original serial computer implementation are described and methods for improving accuracy outside of those conditions are presented. The scan-line algorithm is implemented on the iWarp parallel computer using the Adapt language for parallel image processing. This implementation is applied to magnetic resonance data acquired along radial-lines and spiral trajectories through Fourier transform space.
authors.affiliation: Sch. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA.
authors.forename: D C
authors.initials: DC
authors.lastname: Noll
authors.forename: J A
authors.initials: JA
authors.lastname: Webb
authors.forename: T E
authors.initials: TE
authors.lastname: Warfel