Wenchuan Wu^{1}, Peter J Koopmans^{1}, and Karla L Miller^{1}

For joint k-q reconstruction, it’s beneficial to incoherently under-sampling k-space for different q-space points to utilize the complimentary k-space information. As nearby q-space points in general share more similarities than distant points, it is hypothesized that locally-incoherent k-space sampling can further improve the joint k-q reconstruction. In this work, we propose a method to design locally-incoherent k-space sampling patterns based on a graph colouring algorithm. Results show the proposed method achieves better reconstruction than existing sampling schemes.

Recently, several
diffusion MRI studies have demonstrated improved reconstruction of
under-sampled k-space data by exploring the data redundancy in q-space using a
joint k-q reconstruction^{1-5}. A common finding is that by acquiring
k-space incoherently for different q-space points, the missed k-space lines can
be better recovered using the complimentary k-space information from all
q-space points. Different k-space under-sampling strategies have been proposed,
including random sampling^{3} and circulant sampling^{1,2,4,5}.

These methods increase the global incoherence of k-space under-sampling, but do not specifically aim to achieve local incoherence. Nearby q-space points generally share more common features (i.e. the images are more similar) than distant points. We therefore hypothesize we can improve joint k-q reconstruction by incoherently under-sampling k-space within local q-space neighborhoods. In this work, we propose a graph model approach to design locally incoherent k-space under-sampling and evaluate its efficacy using a newly proposed k-q reconstruction algorithm based on Gaussian processes (presented in another abstracted by our group).

For EPI with an under-sampling factor of R, there exist R unique sampling patterns (produced by shifting the under-sampled trajectory along the phase-encoding direction) that can be applied at different q-space points. Random sampling of k-space as widely used for compressed sensing is not compatible with EPI; instead, we randomize the distribution of under-sampled EPI across different q-space locations to achieve (global) incoherence.

Achieving local incoherence requires a more sophisticated design approach than either randomized or circulant sampling. For each q-space point, a neighborhood is defined including itself and its R-1 nearest neighbors (measured by angular distance). To maximize the local incoherence of k-space under-sampling patterns, it is desirable to assign circulant k-space sampling patterns within each q-space neighborhood (Fig.1). This can be equivalently described as a graph-coloring problem, where each q-space point corresponds to a vertex and an edge between two vertices exists if the corresponding two q-space points are within the same neighborhood. If the constructed graph can be colored using R different colors while obeying that no connected vertexes share the same color, the resultant coloring scheme provides locally-incoherent k-space sampling.

Graph coloring is an
“NP-complete” problem, which means no efficient algorithms are available that provide the exact optimal solution. We applied a greedy algorithm^{6}
to approximate the solution. However, for high reduction factors (highly-connected graph), the greedy algorithm fails to find a solution. To alleviate
the problem, the size of neighborhood was slightly reduced when constructing
the graph.

A joint k-q reconstruction algorithm utilizing
sharable information in q-space based on Gaussian processes was used to evaluate the proposed sampling scheme. This approach builds a
statistical model for the joint distribution of different
data points and predicts the missing k-space data in a given q-space point from
adjacent locations. A simulated 8-channel diffusion data set (normally wouldn’t
support parallel imaging with R>4) with 128 directions and b=1000 s/mm^{2} were
used in the reconstruction. Randomly generated linear phase maps were
added to different diffusion directions to simulate motion-induced phase errors. In-plane
reduction factor of 6 was tested. For comparison, three other sampling schemes
were also evaluated, including using the fixed sampling pattern (a conventional
diffusion acquisition); randomized sampling; and circulant sampling pattern
along a ‘smooth’ q-space trajectory^{5}.

Results

To measure the performance of the sampling scheme, a local incoherence metric Ns is defined as the number of different k-space sampling patterns within each R-neighborhood in q-space. Using smooth circulant sampling (Fig.2b) or randomized sampling scheme (Fig.2c), the global incoherence of k-space sampling is improved, but suffers at some q-space points with low Ns of 2 or 3. With the proposed method, the local incoherence of k-space sampling is improved with no q-space points having Ns<4.

Fig.3 compares the RMSE of reconstructions from different sampling schemes. Using the fixed sampling pattern leads to the highest reconstruction errors, which is expected as no complementary k-space information can be used. With smooth-circulant or randomized sampling, the reconstructions are improved for some directions but fail for many others. Using the optimized sampling scheme, the reconstructions for all directions are improved. Fig.4 shows the reconstructions of the first 6 diffusion directions, clearly demonstrating image artefacts.

Discussion and conclusion

We present a method to improve joint k-q reconstruction by incoherently under-sampling k-space data within local q-space neighborhoods using a graph-coloring algorithm. Reconstructions based on a newly developed algorithm demonstrate superior performance over other sampling designs. The proposed sampling scheme hasn’t been evaluated using alternate joint k-q reconstruction methods, which will be investigated in the future.

1. Madore B, Chiou JYG, Chu R, Chao TC, Maier SE. Accelerated multi-shot diffusion imaging. Magnetic Resonance in Medicine 2014;72:324-336.

2. Gao H, Li L, Zhang K, Zhou W, Hu X. PCLR: Phase-constrained low-rank model for compressive diffusion-weighted MRI. Magnetic Resonance in Medicine 2014;72:1330-1341.

3. Mani M, Jacob M, Guidon A, Magnotta V, Zhong J. Acceleration of high angular and spatial resolution diffusion imaging using compressed sensing with multichannel spiral data. Magnetic Resonance in Medicine 2015;73:126-138.

4. Shi X, Ma X, Wu W, Huang F, Yuan C, Guo H. Parallel imaging and compressed sensing combined framework for accelerating high-resolution diffusion tensor imaging using inter-image correlation. Magnetic Resonance in Medicine 2015;73:1775-1785.

5. Chao T-C, Chiou J-yG, Maier SE, Madore B. Fast diffusion imaging with high angular resolution. Magnetic Resonance in Medicine 2016; doi: 10.1002/mrm.26163.

6. D. J. A. Welsh and M. B. Powell An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J. 10 (1967), 85–86.

Fig.1. Optimized k-space sampling scheme for single-shot EPI. The q-space sampling
is shown on the left, where each colour corresponds to a different under-sampling
pattern in k-space as shown on the right. The local neighborhood of q-space
point 1 (red) is defined as the area delineated by dash lines. In this case,
the under-sampling pattern is unique for each q-space sample, corresponding a
local incoherence of Ns=6. The solid lines illustrate the edges for vertex 1 in the
graph, including two reaching vertices p1 and p2 (vertex 1 is within the
neighborhood of p1 and p2, but not vice versa).

Fig.2. Number
of different sampling patterns in q-space neighborhoods (Ns). (a). Fixed sampling pattern for all
q-space samples. (b). Smooth circulant sampling. (c). Randomised sampling. (d). Proposed optimized sampling
scheme. The mean (standard deviation) of Ns for the four
schemes are 1(0), 4.19(0.82), 3.83(0.79), 4.82(0.57), respectively. The proposed
method produces overall higher Ns, enabling higher local incoherence of k-space
under-sampling.

Fig.3. RMSEs
of reconstructions for all diffusion directions using different sampling strategies.
The proposed method outperforms other methods.

Fig.4. Reconstructed images for diffusion 1 to 6 from different sampling schemes.