Least Squares Optimal Density Compensation for the Gridding Non-uniform Discrete Fourier Transform

Nicholas Dwork, Daniel O’Connor, Ethan Johnson, Corey A. Baron, Jeremy W. Gordon, John M. Pauly, Peder E. Z. LarsonarXiv 2021 · DOI · arXiv

Abstract

The Gridding algorithm has shown great utility for reconstructing images from non-uniformly spaced samples in the Fourier domain in several imaging modalities. Due to the non-uniform spacing, some correction for the variable density of the samples must be made. Existing methods for generating density compensation values are either sub-optimal or only consider a finite set of points (a set of measure 0) in the optimization. This manuscript presents the first density compensation algorithm for a general trajectory that takes into account the point spread function over a set of non-zero measure. We show that the images reconstructed with Gridding using the density compensation values of this method are of superior quality when compared to density compensation weights determined in other ways. Results are shown with a numerical phantom and with magnetic resonance images of the abdomen and the knee.

Introduction

In medical imaging modalities like Magnetic Resonance Imaging (MRI) and Computed Tomography (CT), data is frequently acquired along non-Cartesian trajectories, such as radial lines or spiral paths. To reconstruct a viewable image, this non-uniformly sampled data must be mapped onto a standard rectangular grid, a process known as "Gridding."

A critical challenge in Gridding is the non-uniform sampling density in k-space (the Fourier domain). Typically, the center of k-space is over-sampled while the periphery is under-sampled. Without proper correction using density compensation weights (DCW), the resulting images suffer from significant blurring and artifacts. Current methods, such as Voronoi-based calculations or iterative fixed-point algorithms, often fall short because they either ignore image quality optimization or only consider discrete points, neglecting the continuous nature of the image space.

Methodology

This paper proposes a novel approach by framing density compensation as a constrained weighted least squares optimization problem. The goal is to find a set of weights $w$ such that the resulting Point Spread Function (PSF) $s_w$ approximates a Dirac delta function as closely as possible across the entire Field of View (FOV).

The optimization minimizes the energy of the PSF over a continuous region (a set of non-zero measure), rather than just at discrete pixel locations. This ensures that "leakage" or side-lobes of the PSF are minimized throughout the image. The problem is constrained to ensure the PSF peak is normalized and the weights remain non-negative ($w \geq 0$) to maintain numerical stability and prevent noise amplification. The authors utilize the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA), a gradient-projection method, to solve this optimization efficiently.

Experimental Setup

The proposed method was evaluated against three distinct datasets, each utilizing a different non-Cartesian sampling trajectory:

  1. Numerical Phantom: A synthetic geometric image used with a radial trajectory.
  2. Abdominal MRI: Multi-coil data from the ISMRM Reconstruction Challenge, sampled via a spiral trajectory.
  3. Knee MRI: Clinical data from mridata.org, acquired using a PROPELLER (rotating blade) trajectory.
Non-Cartesian sampling trajectories: a) Radial, b) Spiral, and c) PROPELLER.

Results and Discussion

The proposed Gradient Projection (GP) method consistently outperformed traditional Voronoi and Fixed-Point (FP) methods in both quantitative metrics and qualitative visual quality.

Quantitative Performance

In the abdominal MRI test case, the GP method achieved a Mean Square Error (MSE) of $1.0 \times 10^{-4}$, significantly lower than the $3.2 \times 10^{-4}$ produced by the Voronoi method. Similar improvements were noted in the Structural Similarity Index (SSIM), indicating higher fidelity to the ground truth.

Visual Fidelity

Qualitatively, the GP method effectively suppressed high-frequency artifacts. For instance, the "block patterns" often seen in Voronoi reconstructions of the kidney were eliminated. The GP reconstructions also demonstrated superior contrast and brightness fidelity compared to Fixed-Point methods, which often struggle with global intensity scaling.

Reconstruction targets: a) Numerical phantom, b) Abdominal MRI, and c) Knee MRI.

Conclusion and Future Work

While the GP method offers superior image quality, it comes with a higher computational cost. Calculating weights for the abdominal scan took approximately 5 hours, compared to less than a minute for the Voronoi method. However, since sampling trajectories are often fixed for specific clinical protocols, these weights can be pre-computed and stored, allowing for near-instantaneous reconstruction during live exams.

Future research will focus on extending this framework to 3D imaging and optimizing the algorithm for the massive datasets typical of volumetric scans. Additionally, the authors suggest adapting this approach for Type III non-uniform transforms, where both input and output grids are non-Cartesian.

Summary updated

Abstract

The Gridding algorithm has shown great utility for reconstructing images from non-uniformly spaced samples in the Fourier domain in several imaging modalities. Due to the non-uniform spacing, some correction for the variable density of the samples must be made. Existing methods for generating density compensation values are either sub-optimal or only consider a finite set of points (a set of measure 0) in the optimization. This manuscript presents the first density compensation algorithm for a general trajectory that takes into account the point spread function over a set of non-zero measure. We show that the images reconstructed with Gridding using the density compensation values of this method are of superior quality when compared to density compensation weights determined in other ways. Results are shown with a numerical phantom and with magnetic resonance images of the abdomen and the knee.
BibTeX
@misc{dwork2021least,
  author = {Nicholas Dwork and Daniel O’Connor and Ethan Johnson and Corey A. Baron and Jeremy W. Gordon and John M. Pauly and Peder E. Z. Larson},
  title = {{Least Squares Optimal Density Compensation for the Gridding Non-uniform Discrete Fourier Transform}},
  year = {2021},
  eprint = {2106.06660},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.06660},
}

Loading related content...

Figure