Università degli Studi di Napoli “Federico II”
Candidate:
Federico Maria Ariù
matr. M61/000013
CLASSE DELLE LAUREE MAGISTRALI IN INGEGNERIA ELETTRONICA, LM-29
TESI DI LAUREA
Accelerating NMR
via NUFFT algorithms on GPUs
Anno accademico 2012/2013
Supervisors:
Prof. Amedeo Capozzoli
Ing. Claudio Curcio
Ing. Angelo Liseno
MRI
Magnetic Resonance Imaging (MRI) is a medical diagnostic technique based on the physical principle of nuclear magnetic resonance and allows to reconstruct images of the human body.
MRI has become one of the most used medical diagnostic modalities and it is used for many purposes, e.g. brain and orthopedic surveys.
Accelerating NMR via NUFFT algorithms on GPUs
Sampling and processing speed in MRI
Decreasing the required times for the patient immobility
Continuous monitoring of patient’s conditions during surgery
Accelerating NMR via NUFFT algorithms on GPUs
In many recent applications the need for decrease sampling and processing times arises as much as possible.
Monitoring activities and reactions of patients (e.g. functional MRI, fMRI)
1- ACQUISITION METHODS
2- PROCESSING ALGORITHMS
3-PROCESSING HARDWARE
Accelerating NMR via NUFFT algorithms on GPUs
Factors of sampling and processing speed
Thesis statement
The purpose of the thesis was to implement an MRI algorithm based on the
suitable use of parallel computing systems (Graphic Processing Unit, or GPU)
and fast processing algorithms able to handle non-standard acquired data.
Accelerating NMR via NUFFT algorithms on GPUs
MRI reconstruction
MRI system’s data-unknown relation is :
- Cartesian grid discretization m: measured data S: sensitivity map ρ: spin density
Accelerating NMR via NUFFT algorithms on GPUs
t: time parameter - Time discretization
Data are linked to spin density through sensitivity map as a Fourier transform relation. Data are the sampled values of the spectrum on the (Kx(t), Ky(t)) trajectory described by varying time
The relation between ρ and m could be written as a Discrete Fourier Transform (DFT)
Trasformata di Fourier
dxdyeyxyxStktkmytkxtkj
yxyx ])()([2
),(),())(),((
p q
ytkxtkj
qpqpkykxqkypkxeyxyxSyxtktkm
])()([2),(),())(),((
Fast sampling It is possible to use several data sampling method:
Cartesian Radial Spiral
Uniform DFT Non Uniform DFT (NUDFT)
Accelerating NMR via NUFFT algorithms on GPUs
curvetktk yx ))(),((
About cartesian sampling, processing can be attributed to a uniform DFT accelerated by a standard FFT algorithm in order to obtain a time complexity O(NlogN)
elaborate processing
- fast
+ slow
- straightforward processing
+ elaborate processing
- fast
+
Fast data processing
More sophisticated algorithms allowing to use faster sampling methods are required.
From a numerical point of view, Non Uniform Fast Fourier Transform (NUFFT) algorithms restore time complexity of FFT algorithms.
3 algorithms NUFFT types can be characterized: -NUFFT of type 1 – NED (Non-Equispaced Data) -NUFFT of type 2 – NER (Non-Equispaced Results) -NUFFT of type 3 – (Non-Equispaced Data and Results)
Accelerating NMR via NUFFT algorithms on GPUs
Fast data processing
MRI system’s data-unknown relation is :
The relation above can be rewritten as a system of linear equations:
mA mAAA
where
])()([2)( qypx ytkxtkj
i
iemmA
(NER-NUFFT) (NED-NUFFT)
Such system of linear equations has been solved by applying the biconjugate gradient stabilized method (BICGSTAB).
Accelerating NMR via NUFFT algorithms on GPUs
p q
ytkxtkj
qpqpkykx eqkypkxyxyxSyxtktkm
])()([2),(),())(),((
In order to reverse the relation, multiplying the system by the adjoint matrix, depending on the chosen sampling method, matrix-vector multiplications can be more rapidly processed by using NER and NED NUFFT algorithms.
m: measured data S: sensitivity map ρ: spin density t: time parameter
GPU implementation
Matlab C CUDA C
GPU acceleration was executed on Nvidia Tesla Kepler K20c.
Accelerating NMR via NUFFT algorithms on GPUs
The convenience of a GPU-implemented algorithm is the data parallelism, that is the possibility to solve simultaneously arithmetic operations on various data, obtaining better performance in terms of speed and processing.
An MRI algorithm based on a BICGSTAB routine using NER and NED NUFFT was developed both for the GPU and CPU version. Firstly the algorithm was implemented in Matlab language, after in C language and finally in CUDA C for the GPU version.
MRI numerical results
Phantom reconstruction
Accelerating NMR via NUFFT algorithms on GPUs
CPU
196
GPU
3 65
GPU
CPU
Time
Timespeedup
Computation time[sec]
Processing times of MRI application were validated using simulated data from a nonuniform (spyral type) sampling method. The image reconsruction pointed out the same accuracy shown in the literature [“A fast wavelet-based reconstruction method for MRI”, by Guerquin-Kern, IEEE Transaction on Medical Imaging] linked to the simulator.
Sampling grid
Non Uniform Fast Fourier Transform of
type 3 (NUFFT-3)
NUFFT -3 2D steps – Greengard&Lee approach:
1. Projection of the samples on a uniform grid
1
0
2121 ),(),(N
j
jjj yynxxngfynxnfyxyx
2. Precompensation ).(4
1),( 21
)()(
21
22
21 ynxnfeynxnf
yx
yxxyx
yx
nyn
yx
3. FFT t
Xr
Xr
yr
yr
sxyx
yx
yx
yx
ynim
M
Mn
M
Mn
nimeeynxnf
yxtmsmF
22
1 2
11
2
)1(
2
2
)1(
2
2121 ),(2
),(
4. Spectrum reconstruction on irregular frequencies ),(),(2
),( 2
,
121
21
kt
m
mmm
ktkk tmssmgmsmFts
tsFsp
sp
yx
yx
yxyx
5. Postcompensation ),(4
1),(
22
kk
ts
yx
kk tsFeetsFyx
ykxk
Accelerating NMR via NUFFT algorithms on GPUs
NUFFT-3 allows to use a multi resolution approach on the MRI application when the examination with more details of certain areas rather than others is required.
1
0
),(N
j
ytxis
jkkjkjk eeftsF
NUFFT-3 execution times:
CPU vs GPU
2023
GPU
CPUDNUFFT
Time
Timespeedup
Accelerating NMR via NUFFT algorithms on GPUs
Tests on the execution times of the NUFFT-3, for the GPU and CPU version, were carried out by varying the number of samples.
Conclusions
Accelerating NMR via NUFFT algorithms on GPUs
An MRI reconstruction algorithm from simulated data sampled on a spiral grid was implemented.
The convenience of using NER and NED NUFFT algorithms was demonstrated.
A two-dimensional NUFFT-3 for the processing of nonuniform samples for multi resolution imaging applications was implemented.
The performance of the NUFFT-3 implemented algorithm was verified.
MRI processing was entirely developed on GPU.
Thank you for your time
Accelerating NMR via NUFFT algorithms on GPUs
Top Related