Reconstruction of a signal from a given set of nonuniformly spaced samples of its representation in the frequency domain is a problem encountered in a vast range of scientific fields: radio astronomy, seismic and geophysical imaging such as geophysical diffraction tomography (GDT) and ground penetrating radar (GPR), SAR imaging and medical imaging systems including magnetic resonance imaging (MRI), computerized tomography (CT) and diffraction ultrasound tomography.

In the last decades nonuniform sampling patterns have become increasingly popular amongst MRI practitioners. In particular, radial and spiral trajectories allow faster and more efficient coverage of k-space, thereby reducing scan time and giving rise to other desirable properties such as lower motion sensitivity. Other notable non-Cartesian sampling patterns in MRI are stochastic and rosette trajectories which benefit from less systematic shifting or blurring artifacts. A popular approach for recovering the original image is to resample the signal on a Cartesian grid in k-space and then use the inverse fast Fourier transform (IFFT) in order to transform back into the image domain. It has been shown that this approach is advantageous in terms of computational complexity.

In recent years the concepts of sampling and reconstruction have been generalized within the mathematical framework of function spaces. Methods were developed for reconstructing a desired signal, or an approximation of this signal, beyond the restrictions of the classic Shannon-Nyquist sampling theorem.

We apply these concepts to the reconstruction of a function from non-uniformly spaced samples in the spatial frequency domain. Resampling is performed onto a Cartesian grid in a computationally efficient manner while maintaining a low reconstruction error. First, the given non-Cartesian samples are projected onto an intermediate subspace, spanned by integer translations of a compactly supported kernel function. A sparse system of equations is produced which describes the relation between the nonuniformly spaced samples and a vector of coefficients representing the projection of the signal onto the auxiliary subspace. This sparse system of equations is then solved efficiently using available sparse equation solvers. The result is next projected onto the subspace in which the sampled signal is known to reside. The second projection is implemented efficiently using a digital linear shift invariant (LSI) filter to produce uniformly spaced values of the signal on a Cartesian grid in k-space. Finally, the uniform samples are inverse Fourier transformed to obtain the reconstructed image.

Our algorithm, termed SParse Uniform ReSampling (SPURS) allows handling large scale problems while maintaining a small approximation error at a low computational cost. We demonstrate that the reconstruction error can be traded off for computational complexity by controlling the kernel function spanning the auxiliary subspace and by oversampling the reconstruction grid.

We apply SPURS to the problem of MR image reconstruction from nonuniformly spaced measurements in k-space. The SPURS algorithm is tested using numerical simulations and compared with other prevalent reconstruction methods in terms of its accuracy, its computational burden and its behavior in the presence of noise. The results demonstrate that a single iteration of SPURS outperforms other reconstruction methods while maintaining a similar computational complexity over a range of sampling densities and trajectories as well as various input SNR levels. Iterating SPURS yields further improvement of the reconstruction result and allows for faster trajectories employing less sampling points.

• A. Kiperwas, D. Rosenfeld and Y. C. Eldar, "GSURS: Generalized sparse uniform resampling with application to MRI", Sampling Theory and Applications (SampTA), 2015 International Conference, 538-542. IEEE, 2015.
• A. Kiperwas, D. Rosenfeld and Y. C. Eldar, "The SPURS Algorithm for Resampling an Irregularly Sampled Signal onto a Cartesian Grid", IEEE Transactions on Medical Imaging, vol. 36, issue 2, pp. 628-640, February 2017.

• Download the SPURS package, MATLAB version.

• SPURS package repository, C++ version.

Installation:
1. Download.
2. Follow the instructions in the README.md .

back to index

Software & Hardware:   SoftwareHardwareDemo movies