Key Laboratory of Medical Image Computing of Ministry of Education, Northeastern University, Shenyang, CO 110179, China.
Magn Reson Imaging. 2013 Feb;31(2):313-23. doi: 10.1016/j.mri.2012.06.038. Epub 2012 Aug 13.
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(2)), 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.
使用非笛卡尔方法采集的 MR 原始数据可以通过传统的网格化算法（GA）转换为笛卡尔网格，并通过傅里叶变换进行重建。然而，其运行时复杂度为 O(K×N(2))，其中原始数据的分辨率为 N×N，卷积窗口（CW）的大小为 K。并且它涉及到大量的矩阵计算，包括取模、加法、乘法和卷积。因此，提出了一种基于 Compute Unified Device Architecture（CUDA）的算法来提高 PROPELLER（一种全球认可的非笛卡尔采样方法）的重建效率。实验表明多个 CUDA 线程之间存在写冲突。这会导致在将多个 k 空间数据同步卷积到同一网格上时产生不一致的结果。为了克服这个问题，开发了一种反向网格化算法（RGA）。与传统 GA 为每条轨迹生成网格窗口的方法不同，RGA 为每个网格计算一条轨迹窗口。这就是“反向”的含义。对于 CW 中的每个 k 空间点，都会将其贡献累积到这个网格上。虽然该算法可以很容易地扩展到重建其他非笛卡尔采样的原始数据，但我们仅基于 PROPELLER 实现它。实验表明，这种基于 CUDA 的 RGA 成功地解决了写冲突问题，其重建速度比传统 GA 提高了 7.5 倍。
