3877

OEDIPUS: Towards optimal deterministic k-space sampling for sparsity-constrained MRI

Justin P. Haldar¹ and Daeun Kim¹

¹Electrical Engineering, University of Southern California, Los Angeles, CA, United States

Synopsis

We propose a novel approach to designing optimal k-space sampling patterns for sparsity-constrained MRI. The new approach, called OEDIPUS (Oracle-based Experiment Design for Imaging Parsimoniously Under Sparsity constraints), is inspired by insights and methods from estimation theory and the statistical design of experiments. Specifically, OEDIPUS combines the oracle-based Cramér-Rao bound for sparsity-constrained reconstruction with sequential greedy algorithms for observation selection. We demonstrate that OEDIPUS can be used to deterministically and automatically generate k-space sampling patterns that are tailored to specific hardware and application contexts, and which lead to better reconstruction performance relative to conventional sampling approaches for sparse MRI.

Purpose

Many fast MRI approaches use sparsity constraints to enable image reconstruction from undersampled k-space data. While sparse MRI has been quite successful, the optimal choice of sampling patterns remains a longstanding open problem. While early work used sparsity constraints to allow super-resolution of Nyquist-sampled low-resolution data¹, insights from more recent compressed sensing theory have led to the emergence and popularity of random Fourier sampling schemes². However, completely random Fourier sampling is suboptimal both in theory and in practice^3,4, and most modern approaches rely on heuristic variations of random sampling that are adapted for each new application context based on extensive empirical trial-and-error testing^5-7. In this work, we describe a principled method called OEDIPUS (Oracle-based Experiment Design for Imaging Parsimoniously Under Sparsity constraints) for deterministically designing sampling patterns for sparse MRI.

Methods

OEDIPUS is based on choosing k-space samples that optimize the Cramér-Rao bound (CRB) for estimating a sparse image. The CRB is a theoretical limit on how accurately an unknown parameter vector can be estimated using an unbiased estimator⁸, and is frequently used as an optimality criterion in the statistical design of experiments⁹. While the CRB has been used to optimize k-space sampling in previous work^10-12, we believe that OEDIPUS is the first method to use the CRB to optimize MRI k-space sampling under sparsity constraints.

Theoretical results have shown that the CRB under sparsity constraints is equal to the oracle estimator¹³. The oracle estimator is the simple least squares estimator that is obtained when the positions of the non-zero coefficients of the sparse representation are known, and all other coefficients are forced to zero. While the exact locations of the non-zero coefficients are not generally known in advance, prior images acquired with the same contrast on the same scanner will generally have similar sparsity patterns, and can be used as surrogates for the true sparsity pattern during k-space sampling design.

OEDIPUS proceeds as follows. First, we form the matrix $$$\mathbf{E}$$$ representing the mapping between the image and a fully-sampled k-space dataset. In addition to Fourier encoding, this matrix can also incorporate any other forms of image encoding, including coil sensitivities in parallel imaging or RF encoding. While coil calibration and other similar information is not generally available a priori, OEDIPUS can use the calibration information from past similar scans as a good approximate surrogate for the true values. Second, we form the matrix $$$\mathbf{S}$$$ that synthesizes an image from its coefficients in an appropriately-chosen sparsifying transform domain. Third, we discard the columns from $$$\mathbf{S}$$$ corresponding to transform coefficients that had negligible amplitude in a surrogate reference image acquired with the same sequence, resulting in a truncated matrix $$$\tilde{\mathbf{S}}$$$. Finally, we use observation selection algorithms^14-15 to select the rows of the $$$\mathbf{E}$$$ matrix that, when discarded to form the subsampled matrix $$$\tilde{\mathbf{E}}$$$, lead to the smallest degradation of the CRB. The trace measure ("A-optimality"⁹) of the oracle CRB in this case is $$$\mathrm{Trace}( (\tilde{\mathbf{S}}^H\tilde{\mathbf{E}}^H\tilde{\mathbf{E}}\tilde{\mathbf{S}})^{-1})$$$. For our results, we use the greedy sequential backward selection algorithm¹⁴ to find a local minimum of this difficult (NP-hard) optimization problem, although many other choices are available that may lead to even better performance.

The final result of this procedure is a deterministically-generated undersampled k-space sampling mask that has been specifically tailored to have small CRB for a specific application context and a specific coil configuration, and which can be used whenever acquiring similar data on the same hardware in the future.

Results and Discussion

OEDIPUS was used to design sampling patterns for two different applications (2D T2-weighted imaging and 3D T1-weighted imaging) for two different coil configurations (single-channel and 12-channel) and three different acceleration factors ($$$R=2,3,4$$$). The sampling patterns were tested using retrospective undersampling of fully sampled datasets, and reconstructed using $$$\ell_1$$$-regularization² of Daubechies-4 wavelet coefficients. Comparisons were made against uniform^16,17 and Poisson disc random¹⁸ undersampling. Results are shown in Figs. 1-5.

Results show that, for these images, OEDIPUS generates variable density sampling patterns. However, unlike standard variable density heuristics, OEDIPUS automatically tailors the sampling pattern to the specific imaging context, without the need for manual interaction. For example, OEDIPUS automatically produces different sampling densities variations for single-channel and multichannel data. While all three sampling schemes (uniform, random, OEDIPUS) work similarly well at low acceleration factors, OEDIPUS consistently yields the best reconstruction performance for highly accelerated scans.

Conclusions

We proposed and evaluated OEDIPUS, a novel theory-guided approach to designing k-space sampling patterns for sparsity-constrained MRI. Empirical results confirmed the potential of this new approach, and we anticipate that OEDIPUS will become an powerful tool for designing sampling patterns.

Acknowledgements

This work was supported in part by NSF CAREER award CCF-1350563, and NIH research grants R21-EB022951 and R01-NS089212. Computation for some of the work described in this paper was supported by the University of Southern California’s Center for High-Performance Computing (http://hpcc.usc.edu).

References

1. Liang Z-P, Haacke EM, Thomas CW. “High-resolution inversion of finite Fourier transform data through a localized polynomial approximation.” Inverse Problems 5:831-847, 1989.

2. Lustig M, Donoho D, Pauly JM. “Sparse MRI: The application of compressed sensing for rapid MR imaging.” Magnetic Resonance in Medicine 58:1182-1195, 2007.

3. Haldar JP, Hernando D, Liang Z-P. “Compressed-Sensing MRI with Random Encoding.” IEEE Transactions on Medical Imaging 30:893-903, 2011.

4. Adcock B, Hansen AC, Poon C, Roman B. “Breaking the coherence barrier: a new theory for compressed sensing.” Preprint, 2013. arXiv:1302.0561

5. Wang Z, Arce GR. “Variable density compressed image sampling.” IEEE Transactions on Image Processing 19:264-270, 2010.

6. Puy G, Vandergheynst P, Wiaux Y. “On variable density compressive sampling.” IEEE Signal Processing Letters 18:595-598, 2011.

7. Zijlstra F, Viergever MA, Seevinck PR. “Evaluation of variable density and data-driven k-space undersampling for compressed sensing magnetic resonance imaging.” Investigative Radiology 51:410-419, 2016.

8. Kay SM. Fundamentals of Statistical Signal Processing, Volume I: Estimation Theory. Upper Saddle River: Prentice Hall, 1993.

9. Pukelsheim F. Optimal Design of Experiments. New York: John Wiley & Sons, 1993.

10. Marseille GJ, Fuderer M, de Beer R, Mehlkopf AF, van Ormondt D. “Reduction of MRI scan time through nonuniform sampling and edge-distribution modeling.” Journal of Magnetic Resonance, Series B 103:292-295, 1994.

11. Xu D, Jacob M, Liang Z-P. “Optimal Sampling of k-Space with Cartesian Grids for Parallel MR Imaging.” Proc. ISMRM 2005, p. 2450.

12. Haldar JP, Hernando D, Liang Z-P. “Super-resolution reconstruction of MR image sequences with contrast modeling.” Proc. IEEE International Symposium of Biomedical Imaging 2009, pp. 266-269.

13. Ben-Haim Z, Eldar Y. “The Cramér–Rao bound for estimating a sparse parameter vector.” IEEE Transactions on Signal Processing 58:3384-3389, 2010.

14. Reeves SJ, Zhe Z. “Sequential algorithms for observation selection.” IEEE Transactions on Signal Processing 47:123-132, 1999.

15. Broughton R, Coope I, Renaud P, Tappenden R. “Determinant and exchange algorithms for observation subset selection.” IEEE Transactions on Image Processing 19:2437-2443, 2010.

16. Pruessmann KP, Weiger M, Scheidegger MB, Boesiger P. “SENSE: Sensitvity encoding for fast MRI.” Magnetic Resonance in Medicine 42:952-962, 1999.

17. Breuer FA, Blaimer M, Mueller MF, Seiberlich N, Heidemann RM, Griswold MA, Jakob PM. “Controlled aliasing in volumetric parallel imaging (2D CAIPIRINHA).” Magnetic Resonance in Medicine 55:549-556, 2006.

18. Nayak KS, Nishimura DG. “Randomized trajectories for reduced aliasing artifact.” Proc. ISMRM 1998, p. 670.

Figures

Figure 1. Example k-space sampling patterns ($$$R=2$$$) generated by OEDIPUS for (top) 3D Fourier encoding of a T1-weighted image, and (bottom) 2D Fourier encoding of a T2-weighted image. Note that OEDIPUS has generated variable density sampling patterns, and that the sampling density is automatically selected to be different for (left) single channel acquisition than it is for (right) multichannel acquisition.

Figure 2. Sparsity-constrained images obtained from single channel data with $$$R=2$$$ for (top) T1-weighted and (bottom) T2-weighted images. The OEDIPUS sampling patterns were shown in Fig. 1, while the uniform and random sampling patterns are the same as shown for the multichannel case in Figs. 3 and 4. The normalized root-mean-squared error metric is shown as an inset, and the best performing sampling pattern for a given acceleration factor is color coded with blue text.

Figure 3. (Left) Two-dimensional Fourier sampling patterns generated for multichannel reconstruction of a T2-weighted image. (Right) Reconstructed multichannel images using $$$\ell_1$$$ regularization. The normalized root-mean-squared error metric is shown as an inset, and the best performing sampling pattern for a given acceleration factor is color coded with blue text.

Figure 4. Three-dimensional Fourier sampling patterns generated for multi-channel reconstruction of a T1-weighted image. Corresponding reconstruction results are shown in Fig. 5.

Figure 5. Reconstructed multichannel T1-weighted images using $$$\ell_1$$$ regularization and the sampling patterns shown in Fig. 4. The normalized root-mean-squared error metric is shown as an inset, and the best performing sampling pattern for a given acceleration factor is color coded with blue text.

Proc. Intl. Soc. Mag. Reson. Med. 25 (2017)

3877