Mean square optimal NUFFT approximation for efficient non-Cartesian MRI reconstruction

Abstract

The fast evaluation of the discrete Fourier transform of an image at non-uniform sampling locations is key to efficient iterative non-Cartesian MRI reconstruction algorithms. Current non-uniform fast Fourier transform (NUFFT) approximations rely on the interpolation of oversampled uniform Fourier samples. The main challenge is high memory demand due to oversampling, especially when multidimensional datasets are involved. The main focus of this work is to design an NUFFT algorithm with minimal memory demands. Specifically, we introduce an analytical expression for the expected mean square error in the NUFFT approximation based on our earlier work. We then introduce an iterative algorithm to design the interpolator and scale factors. Experimental comparisons show that the proposed optimized NUFFT scheme provides considerably lower approximation errors than the previous designs [1] that rely on worst case error metrics. The improved approximations are also seen to considerably reduce the errors and artifacts in non-Cartesian MRI reconstruction.

Keywords: Histogram; Interpolators; Non-Cartesian MRI; Non-uniform fast Fourier transform.

Figure 1

Effect of scale factors on NUFFT approximation: the solid lines correspond to least square methods introduced in [20, 15, 14] with KB, Gaussian, and cosine scale factors. Note that all of these methods results in considerably higher error kernels than the proposed MOLS-U interpolator, shown in black dotted lines. To demonstrate the improvement offered by mean-square optimal scale factors specified by (13), we re-compute the scale factors of the LS schemes [20, 15, 14]; the corresponding methods are termed as LS-KB*, LS-Cosine*, and LS-Gaussian*, which are denoted by dotted lines. We observe that the error kernels of these methods are considerably lower and more comparable to the proposed scheme than the original LS methods. These results demonstrate the role played by the scale factor in NUFFT approximation.

Figure 2

Comparison of different NUFFT approximation schemes:the optimized interpolators, scale factors, and the corresponding error kernels specified by (10) are shown in the top three rows. Here, we assume the energy distribution to be a Gaussian shown in (j). The columns correspond to the interpolators with different lengths (J = 4, 6&8), computed assuming K = 68, N = 64 and O = 101. We observe that the error kernels associated with the LS-KB scheme is much higher than the proposed one, mainly due to the sub-optimality of the scale factors as shown in Fig. 1. The decay of the NUFFT approximation error for a random k-space sampling pattern are shown in (k) and (l). We observe from (k) that the MOLS schemes provide the lowest mean-square errors. However, their worst case performance is much worse than the WOLS scheme as see from (l), since they result in higher errors at the image boundaries.

Figure 3

Recovery of the 64×64 Shepp-Logan phantom from under sampled radial acquisition (30 lines) using total variation reconstruction scheme, specified by (25). We set K=66 and J=4 to obtain a memory and computationally efficient iterative reconstruction algorithm. The comparison of the reconstructions using different NUFFT approximations with the the ones obtained using the exact DTFT are shown in bottom row. These error images are scaled by a factor of 6.67 compared to the original images for better visualization. Note that the MOLS and MOLS-U interpolators provide low errors at most image regions. In contrast, the WOLS scheme results in higher errors at the image center, while the errors associated with the LS-KB scheme are considerably higher.

Figure 4

Reconstructed images and error images using different interpolators, when K=130 and J=6. It is observed from the top row that LS-KB kernel results in large errors close to the image boundaries, indicated by the red arrows. It also results in subtle differences in the texture in the central regions. As in the case of the Shepp-Logan example, the WOLS scheme is able to reduce these structured artifacts at the expense of increased in the image center. By contrast, the MOLS and MOLS-U schemes result in lower and un-structured artifacts. The behavior can be better appreciated from the error images shown in the bottom row, obtained by comparing the reconstructions against ones obtained using the exact DTFT. For better visualization, the error images are scaled by a factor of 10 compared to the original images.

Figure 5

Reconstructed images and error images using different interpolators, when K=194 and J=4. The MOLS-U scheme provides considerably less reconstruction errors compared to WOLS and LS-KB reconstructions. All the error images are scaled by the factor of 12. We observe that the LS-KB scheme results in higher errors. Specfically, we observe the systematic reduction in intensity indicated by the black arrows, as well as oscillatory artifacts indicated by red arrows. We also observe that the errors in the LS-KB case are more unstructured and hence not as visually disturbing as the WOLS scheme. This can be explained in terms of the smoothness of LS-KB error kernel (see Fig. 2). Specifically, the variance of the errors is spatially modulated by the error kernel and the intensity of the image. While this behavior may be acceptable in anatomical imaging, it may be undesirable in functional imaging.