Efficient Approximation of Jacobian Matrices Involving a Non-Uniform Fast Fourier Transform (NUFFT).

There is growing interest in learning Fourier domain sampling strategies (particularly for magnetic resonance imaging, MRI) using optimization approaches. For non-Cartesian sampling, the system models typically involve non-uniform fast Fourier transform (NUFFT) operations. Commonly used NUFFT algorithms contain frequency domain interpolation, which is not differentiable with respect to the sampling pattern, complicating the use of gradient methods. This paper describes an efficient and accurate approach for computing approximate gradients involving NUFFTs. Multiple numerical experiments validate the improved accuracy and efficiency of the proposed approximation. As an application to computational imaging, the NUFFT Jacobians were used to optimize non-Cartesian MRI sampling trajectories via data-driven stochastic optimization. Specifically, the sampling patterns were learned with respect to various model-based image reconstruction (MBIR) algorithms. The proposed approach enables sampling optimization for image sizes that are infeasible with standard auto-differentiation methods due to memory limits. The synergistic acquisition and reconstruction design leads to remarkably improved image quality. In fact, we show that model-based image reconstruction methods with suitably optimized imaging parameters can perform nearly as well as CNN-based methods.

Optimization in the space domain for density compensation with the nonuniform FFT.

The non-uniform Discrete Fourier Transform algorithm has shown great utility for reconstructing images from non-uniformly spaced Fourier samples in several imaging modalities. Due to the non-uniform spacing, some correction for the variable density of the samples must be made. Common methods for generating density compensation values are either sub-optimal or only consider a finite set of points in the optimization. This manuscript presents an algorithm for generating density compensation values from a set of Fourier samples that takes into account the point spread function over an entire rectangular region in the image domain. We show that the reconstructed images using the density compensation values of this method are of superior quality when compared to other standard methods. Results are shown with a numerical phantom and with magnetic resonance images of the abdomen and the knee.

Real-time, single breath-hold, multi-slice, 2D cine radial MR image reconstruction using sc-GROG k-t ESPIRiT.

Background:Multi-slice, multiple breath-hold ECG-gated 2D cine MRI is a standard technique for evaluating heart function and restricted to one or two images per breath-hold. Therefore, the standard cine MRI requires long scan time and can result in slice-misalignments because of various breath-hold locations in the multiple acquisitions.Methods:This work proposes the sc-GROG based k-t ESPIRiT with Total Variation (TV) constraint (sc-GROG k-t ESPIRiT) to reconstruct unaliased cardiac real-time cine MR images from highly accelerated whole heart multi-slice, single breath-hold, real-time 2D cine radial data acquired using the balanced steady-state free precession (trueFISP) sequence in 8 patients. The proposed method quality is assessed via Artifact Power (AP), Root-Mean Square Error (RMSE), Structure Similarity Index (SSIM), Peak Signal-to-Noise Ratio (PSNR), blood-pool to myocardial Contrast-to-Noise-Ratio (CNR), Signal-to-Noise-Ratio (SNR) and spatial-temporal intensity plots through the blood-myocardium boundary. The proposed method quantitative results are compared with the NUFFT based k-t ESPIRiT with Total Variation (TV) constraint (NUFFT k-t ESPIRiT) approach. Furthermore, clinical analysis and function quantification are assessed by Bland-Altman (BA) analyses.Results:As supported by the visual assessment and evaluation parameters, the reconstruction results of the sc-GROG k-t ESPIRiT approach provide an average 21%, 12%, 1% and 47% improvement in AP, RMSE, SSIM and PSNR, respectively in comparison to the NUFFT k-t ESPIRiT approach. Furthermore, the proposed method gives on average 45% and 58% improved blood-pool to myocardial CNR and SNR than the NUFFT k-t ESPIRiT approach. Also, from the BA plot, the proposed method gives better left ventricular and right ventricular function measurements as compared to the NUFFT k-t ESPIRiT scheme.Conclusions:The sc-GROG k-t ESPIRiT (Proposed Method) improves the spatio-temporal quality of the whole heart multi-slice, single breath-hold, real-time 2D cine radial MR and semi-automated analysis using standard clinical software, as compared to the NUFFT k-t ESPIRiT approach.

Improved Image Quality for Static BLADE Magnetic Resonance Imaging Using the Total-Variation Regularized Least Absolute Deviation Solver.

In order to improve the image quality of BLADE magnetic resonance imaging (MRI) using the index tensor solvers and to evaluate MRI image quality in a clinical setting, we implemented BLADE MRI reconstructions using two tensor solvers (the least-squares solver and the L1 total-variation regularized least absolute deviation (L1TV-LAD) solver) on a graphics processing unit (GPU). The BLADE raw data were prospectively acquired and presented in random order before being assessed by two independent radiologists. Evaluation scores were examined for consistency and then by repeated measures analysis of variance (ANOVA) to identify the superior algorithm. The simulation showed the structural similarity index (SSIM) of various tensor solvers ranged between 0.995 and 0.999. Inter-reader reliability was high (Intraclass correlation coefficient (ICC) = 0.845, 95% confidence interval: 0.817, 0.87). The image score of L1TV-LAD was significantly higher than that of vendor-provided image and the least-squares method. The image score of the least-squares method was significantly lower than that of the vendor-provided image. No significance was identified in L1TV-LAD with a regularization strength of λ= 0.4-1.0. The L1TV-LAD with a regularization strength of λ= 0.4-0.7 was found consistently better than least-squares and vendor-provided reconstruction in BLADE MRI with a SENSitivity Encoding (SENSE) factor of 2. This warrants further development of the integrated computing system with the scanner.

CG-SENSE revisited: Results from the first ISMRM reproducibility challenge.

PURPOSE: The aim of this work is to shed light on the issue of reproducibility in MR image reconstruction in the context of a challenge. Participants had to recreate the results of "Advances in sensitivity encoding with arbitrary k-space trajectories" by Pruessmann et al. METHODS: The task of the challenge was to reconstruct radially acquired multicoil k-space data (brain/heart) following the method in the original paper, reproducing its key figures. Results were compared to consolidated reference implementations created after the challenge, accounting for the two most common programming languages used in the submissions (Matlab/Python). RESULTS: Visually, differences between submissions were small. Pixel-wise differences originated from image orientation, assumed field-of-view, or resolution. The reference implementations were in good agreement, both visually and in terms of image similarity metrics. DISCUSSION AND CONCLUSION: While the description level of the published algorithm enabled participants to reproduce CG-SENSE in general, details of the implementation varied, for example, density compensation or Tikhonov regularization. Implicit assumptions about the data lead to further differences, emphasizing the importance of sufficient metadata accompanying open datasets. Defining reproducibility quantitatively turned out to be nontrivial for this image reconstruction challenge, in the absence of ground-truth results. Typical similarity measures like NMSE of SSIM were misled by image intensity scaling and outlier pixels. Thus, to facilitate reproducibility, researchers are encouraged to publish code and data alongside the original paper. Future methodological papers on MR image reconstruction might benefit from the consolidated reference implementations of CG-SENSE presented here, as a benchmark for methods comparison.

A GRAPPA algorithm for arbitrary 2D/3D non-Cartesian sampling trajectories with rapid calibration.

PURPOSE: GRAPPA is a popular reconstruction method for Cartesian parallel imaging, but is not easily extended to non-Cartesian sampling. We introduce a general and practical GRAPPA algorithm for arbitrary non-Cartesian imaging. METHODS: We formulate a general GRAPPA reconstruction by associating a unique kernel with each unsampled k-space location with a distinct constellation, that is, local sampling pattern. We calibrate these generalized kernels using the Fourier transform phase shift property applied to fully gridded or separately acquired Cartesian Autocalibration signal (ACS) data. To handle the resulting large number of different kernels, we introduce a fast calibration algorithm based on nonuniform FFT (NUFFT) and adoption of circulant ACS boundary conditions. We applied our method to retrospectively under-sampled rotated stack-of-stars/spirals in vivo datasets, and to a prospectively under-sampled rotated stack-of-spirals functional MRI acquisition with a finger-tapping task. RESULTS: We reconstructed all datasets without performing any trajectory-specific manual adaptation of the method. For the retrospectively under-sampled experiments, our method achieved image quality (i.e., error and g-factor maps) comparable to conjugate gradient SENSE (cg-SENSE) and SPIRiT. Functional activation maps obtained from our method were in good agreement with those obtained using cg-SENSE, but required a shorter total reconstruction time (for the whole time-series): 3 minutes (proposed) vs 15 minutes (cg-SENSE). CONCLUSIONS: This paper introduces a general 3D non-Cartesian GRAPPA that is fast enough for practical use on today's computers. It is a direct generalization of original GRAPPA to non-Cartesian scenarios. The method should be particularly useful in dynamic imaging where a large number of frames are reconstructed from a single set of ACS data.

Quadratic Frequency Modulation Signals Parameter Estimation Based on Two-Dimensional Product Modified Parameterized Chirp Rate-Quadratic Chirp Rate Distribution.

In an inverse synthetic aperture radar (ISAR) imaging system for targets with complex motion, the azimuth echo signals of the target are always modeled as multicomponent quadratic frequency modulation (QFM) signals. The chirp rate (CR) and quadratic chirp rate (QCR) estimation of QFM signals is very important to solve the ISAR image defocus problem. For multicomponent QFM (multi-QFM) signals, the conventional QR and QCR estimation algorithms suffer from the cross-term and poor anti-noise ability. This paper proposes a novel estimation algorithm called a two-dimensional product modified parameterized chirp rate-quadratic chirp rate distribution (2D-PMPCRD) for QFM signals parameter estimation. The 2D-PMPCRD employs a multi-scale parametric symmetric self-correlation function and modified nonuniform fast Fourier transform-Fast Fourier transform to transform the signals into the chirp rate-quadratic chirp rate (CR-QCR) domains. It can greatly suppress the cross-terms while strengthening the auto-terms by multiplying different CR-QCR domains with different scale factors. Compared with high order ambiguity function-integrated cubic phase function and modified Lv's distribution, the simulation results verify that the 2D-PMPCRD acquires higher anti-noise performance and obtains better cross-terms suppression performance for multi-QFM signals with reasonable computation cost.

Rapid compressed sensing reconstruction of 3D non-Cartesian MRI.

PURPOSE: Conventional non-Cartesian compressed sensing requires multiple nonuniform Fourier transforms every iteration, which is computationally expensive. Accordingly, time-consuming reconstructions have slowed the adoption of undersampled 3D non-Cartesian acquisitions into clinical protocols. In this work we investigate several approaches to minimize reconstruction times without sacrificing accuracy. METHODS: The reconstruction problem can be reformatted to exploit the Toeplitz structure of matrices that are evaluated every iteration, but it requires larger oversampling than what is strictly required by nonuniform Fourier transforms. Accordingly, we investigate relative speeds of the two approaches for various nonuniform Fourier transform kernel sizes and oversampling for both GPU and CPU implementations. Second, we introduce a method to minimize matrix sizes by estimating the image support. Finally, density compensation weights have been used as a preconditioning matrix to improve convergence, but this increases noise. We propose a more general approach to preconditioning that allows a trade-off between accuracy and convergence speed. RESULTS: When using a GPU, the Toeplitz approach was faster for all practical parameters. Second, it was found that properly accounting for image support can prevent aliasing errors with minimal impact on reconstruction time. Third, the proposed preconditioning scheme improved convergence rates by an order of magnitude with negligible impact on noise. CONCLUSION: With the proposed methods, 3D non-Cartesian compressed sensing with clinically relevant reconstruction times (<2 min) is feasible using practical computer resources. Magn Reson Med 79:2685-2692, 2018. © 2017 International Society for Magnetic Resonance in Medicine.

Fast computation of far-field pulse-echo PSF of arbitrary arrays for large sparse 2-D ultrasound array design.

Large wideband two-dimensional (2-D) arrays are essential for high-resolution three-dimensional (3-D) ultrasound imaging. Since the tremendous element number of a full sampled large 2-D array is not affordable in any practical 3-D ultrasound imaging system, it is necessary to reduce the element number through sparse 2-D array design. Sparse array design requires that both the positions and weights of the array elements should be arbitrarily alterable. Hence a proper evaluation tool that can deal with arbitrary array is integral to optimizing the array structure and apodization function. It is known that pulse-echo point spread function (PSF) has been a common tool used to evaluate the performance of wideband arrays in ultrasound imaging all along, which also plays an important role in wideband ultrasound simulations. However, so far the conventional ultrasound simulation tools can only calculate pulse-echo PSF of arbitrary wideband arrays in the time domain because of the existence of nonuniform nodes in the spatial impulse response expressions, which obstructs their application of FFT to do fast computation of the time-domain convolutions. As a result, ultra-high time consumption of pulse-echo PSF computation of a large arbitrary wideband array hampers it to be taken as the evaluation tool by any stochastic optimization methods which need massive iterations in designing large sparse 2-D arrays. This paper aims to make available the pulse-echo PSF tool in designing large sparse 2-D arrays by proposing a fast computation method of far-field pulse-echo PSFs of arbitrary wideband arrays. In the paper, fast computation of wideband spatial impulse responses of a 2-D array is first realized in frequency domain by employing the nonuniform fast Fourier transform (NUFFT), under the point source assumption in far-field. On the basis of that, fast computation of time-domain convolutions is made possible by using FFT. In addition, a short inverse FFT (IFFT) is applied in recovering the time-domain envelopes rather than the detailed waveforms of beam pulses to extract the pulse-echo PSF, which further accelerates the computation. Compared with the computation speed of the time domain method, i.e. Field II, the proposed method achieves an improvement of three orders of magnitude with comparable accuracy for a 100×100 wideband 2-D array. The proposed method makes it possible for applying stochastic optimization methods to design arbitrary large wideband 2-D arrays using pulse-echo PSF as the evaluation tool.

ICON-MIC: Implementing a CPU/MIC Collaboration Parallel Framework for ICON on Tianhe-2 Supercomputer.

Electron tomography (ET) is an important technique for studying the three-dimensional structures of the biological ultrastructure. Recently, ET has reached sub-nanometer resolution for investigating the native and conformational dynamics of macromolecular complexes by combining with the sub-tomogram averaging approach. Due to the limited sampling angles, ET reconstruction typically suffers from the "missing wedge" problem. Using a validation procedure, iterative compressed-sensing optimized nonuniform fast Fourier transform (NUFFT) reconstruction (ICON) demonstrates its power in restoring validated missing information for a low-signal-to-noise ratio biological ET dataset. However, the huge computational demand has become a bottleneck for the application of ICON. In this work, we implemented a parallel acceleration technology ICON-many integrated core (MIC) on Xeon Phi cards to address the huge computational demand of ICON. During this step, we parallelize the element-wise matrix operations and use the efficient summation of a matrix to reduce the cost of matrix computation. We also developed parallel versions of NUFFT on MIC to achieve a high acceleration of ICON by using more efficient fast Fourier transform (FFT) calculation. We then proposed a hybrid task allocation strategy (two-level load balancing) to improve the overall performance of ICON-MIC by making full use of the idle resources on Tianhe-2 supercomputer. Experimental results using two different datasets show that ICON-MIC has high accuracy in biological specimens under different noise levels and a significant acceleration, up to 13.3 × , compared with the CPU version. Further, ICON-MIC has good scalability efficiency and overall performance on Tianhe-2 supercomputer.

Technical Note: Evaluation of pre-reconstruction interpolation methods for iterative reconstruction of radial k-space data.

PURPOSE: To evaluate the use of three different pre-reconstruction interpolation methods to convert non-Cartesian k-space data to Cartesian samples such that iterative reconstructions can be performed more simply and more rapidly. METHODS: Phantom as well as cardiac perfusion radial datasets were reconstructed by four different methods. Three of the methods used pre-reconstruction interpolation once followed by a fast Fourier transform (FFT) at each iteration. The methods were: bilinear interpolation of nearest-neighbor points (BINN), 3-point interpolation, and a multi-coil interpolator called GRAPPA Operator Gridding (GROG). The fourth method performed a full non-Uniform FFT (NUFFT) at each iteration. An iterative reconstruction with spatiotemporal total variation constraints was used with each method. Differences in the images were quantified and compared. RESULTS: The GROG multicoil interpolation, the 3-point interpolation, and the NUFFT-at-each-iteration approaches produced high quality images compared to BINN, with the GROG-derived images having the fewest streaks among the three preinterpolation approaches. However, all reconstruction methods produced approximately equal results when applied to perfusion quantitation tasks. Pre-reconstruction interpolation gave approximately an 83% reduction in reconstruction time. CONCLUSION: Image quality suffers little from using a pre-reconstruction interpolation approach compared to the more accurate NUFFT-based approach. GROG-based pre-reconstruction interpolation appears to offer the best compromise by using multicoil information to perform the interpolation to Cartesian sample points prior to image reconstruction. Speed gains depend on the implementation and relatively standard optimizations on a MATLAB platform result in preinterpolation speedups of ~ 6 compared to using NUFFT at every iteration, reducing the reconstruction time from around 42 min to 7 min.

FGG-NUFFT-Based Method for Near-Field 3-D Imaging Using Millimeter Waves.

In this paper, to deal with the concealed target detection problem, an accurate and efficient algorithm for near-field millimeter wave three-dimensional (3-D) imaging is proposed that uses a two-dimensional (2-D) plane antenna array. First, a two-dimensional fast Fourier transform (FFT) is performed on the scattered data along the antenna array plane. Then, a phase shift is performed to compensate for the spherical wave effect. Finally, fast Gaussian gridding based nonuniform FFT (FGG-NUFFT) combined with 2-D inverse FFT (IFFT) is performed on the nonuniform 3-D spatial spectrum in the frequency wavenumber domain to achieve 3-D imaging. The conventional method for near-field 3-D imaging uses Stolt interpolation to obtain uniform spatial spectrum samples and performs 3-D IFFT to reconstruct a 3-D image. Compared with the conventional method, our FGG-NUFFT based method is comparable in both efficiency and accuracy in the full sampled case and can obtain more accurate images with less clutter and fewer noisy artifacts in the down-sampled case, which are good properties for practical applications. Both simulation and experimental results demonstrate that the FGG-NUFFT-based near-field 3-D imaging algorithm can have better imaging performance than the conventional method for down-sampled measurements.

ICON: 3D reconstruction with 'missing-information' restoration in biological electron tomography.

Electron tomography (ET) plays an important role in revealing biological structures, ranging from macromolecular to subcellular scale. Due to limited tilt angles, ET reconstruction always suffers from the 'missing wedge' artifacts, thus severely weakens the further biological interpretation. In this work, we developed an algorithm called Iterative Compressed-sensing Optimized Non-uniform fast Fourier transform reconstruction (ICON) based on the theory of compressed-sensing and the assumption of sparsity of biological specimens. ICON can significantly restore the missing information in comparison with other reconstruction algorithms. More importantly, we used the leave-one-out method to verify the validity of restored information for both simulated and experimental data. The significant improvement in sub-tomogram averaging by ICON indicates its great potential in the future application of high-resolution structural determination of macromolecules in situ.