A CUDA-based reverse gridding algorithm for MR reconstruction

MR raw data collected using non-Cartesian method can be transformed on Cartesian grids by traditional gridding algorithm (GA) and reconstructed by Fourier transform. However, its runtime complexity is O(K× N²), where resolution of raw data is N× N and size of convolution window (CW) is K. And it involves a large number of matrix calculation including modulus, addition, multiplication and convolution. Therefore, a Compute Unified Device Architecture (CUDA)-based algorithm is proposed to improve the reconstruction efficiency of PROPELLER (a globally recognized non-Cartesian sampling method). Experiment shows a write–write conflict among multiple CUDA threads. This induces an inconsistent result when synchronously convoluting multiple k-space data onto the same grid. To overcome this problem, a reverse gridding algorithm (RGA) was developed. Different from the method of generating a grid window for each trajectory as in traditional GA, RGA calculates a trajectory window for each grid. This is what “reverse” means. For each k-space point in the CW, contribution is cumulated to this grid. Although this algorithm can be easily extended to reconstruct other non-Cartesian sampled raw data, we only implement it based on PROPELLER. Experiment illustrates that this CUDA-based RGA has successfully solved the write–write conflict and its reconstruction speed is 7.5 times higher than that of traditional GA.     

An improved gridding method for spiral MRI using nonuniform fast Fourier transform

The algorithm of Liu and Nguyen [IEEE Microw. Guided Wave Lett. 8 (1) (1998) 18; SIAM J. Sci. Comput. 21 (1) (1999) 283] for nonuniform fast Fourier transform (NUFFT) has been extended to two dimensions to reconstruct images using spiral MRI. The new gridding method, called LS_NUFFT, minimizes the reconstruction approximation error in the Least Square sense by generated convolution kernels that fit for the spiral k-space trajectories. For analytical comparison, the LS_NUFFT has been fitted into a consistent framework with the conventional gridding methods using Kaiser-Bessel gridding and a recently proposed generalized FFT (GFFT) approach. Experimental comparison was made by assessing the performance of the LS_NUFFT with that of the standard direct summation method and the Kaiser-Bessel gridding method, using both digital phantom data and in vivo experimental data. Because of the explicitly optimized convolution kernel in LS_NUFFT, reconstruction results showed that the LS_NUFFT yields smaller reconstruction approximation error than the Kaiser-Bessel gridding method, but with the same computation complexity.     

A new theoretical derivation of NFFT and its implementation on GPU

An efficient calculation of NFFT (nonequispaced fast Fourier transforms) is always a challenging task in a variety of application areas, from medical imaging to radio astronomy to chemical simulation. In this article, a new theoretical derivation is proposed for NFFT based on gridding algorithm and new strategies are proposed for the implementation of both forward NFFT and its inverse on both CPU and GPU. The GPU-based version, namely CUNFFT, adopts CUDA (Compute Unified Device Architecture) technology, which supports a fine-grained parallel computing scheme. The approximation errors introduced in the algorithm are discussed with respect to different window functions. Finally, benchmark calculations are executed to illustrate the accuracy and performance of NFFT and CUNFFT. The results show that CUNFFT is not only with high accuracy, but also substantially faster than conventional NFFT on CPU.     

Evaluation of optimal density weighting for regridding

Density weighting is a necessary component of the regridding algorithm for interpolating nonuniformly sampled data points onto a regular grid. Differing concepts of optimality for the density weighting have been proposed previously. The present study reviews some of these concepts and evaluates the accuracy of different techniques by comparison with the image obtained by a computationally intensive least squares minimization. A variant on one of the techniques is proposed that yields the highest accuracy of those studied.