search

odlgroup / odl

Operator Discretization Library https://odlgroup.github.io/odl/
Mozilla Public License 2.0
374 stars 105 forks source link

Non-uniform FFT #1437

Open ozanoktem opened 6 years ago

ozanoktem commented 6 years ago

In some imaging modalities, like MRI and phase contrast tomography, the forward problem involves taking the Fourier transform of a function in 2D/3D that is not sampled on a grid. The current Fourier transform in ODL lacks support for this case, thereby forcing the user to interpolate in Fourier space. An alternative would be to integer a backend for the DFT that can directly handle this situation, and there are several non-uniform FFT (NUFFT) routines out there.

One implementation of NUFFT that has python wrappers and includes routines for computing the adjoint is Flatiron Institute Nonuniform Fast Fourier Transform (FINUFFT) which is available at https://github.com/flatironinstitute/finufft, see also https://finufft.readthedocs.io/en/latest for the documentation. This git repo shows it is an actively developed software package. The library is currently supported for unix/linux and also tested on Mac OSX.

Bearing in mind the above, it would be a nice feature if one could integrate FINUFFT with ODL.

kohr-h commented 6 years ago

Flatiron Institute Nonuniform Fast Fourier Transform (FINUFFT)

Is there any particular reason for suggesting that particular library? I still find NFFT more convincing. More contributors, more releases, more functionality, and above all, no limitation to dimensions 1 to 3 as in FINUFFT.

Other than that, agreed, would be a nice addition.

ozanoktem commented 6 years ago

Backed by a large institution, active git repo, bindings to various languages are all good features.

kohr-h commented 6 years ago

All good, but limitation to dimensions 1, 2, 3 is an anti-feature. Also benchmarks would be nice to have.

ozanoktem commented 6 years ago

Agree that NFFT has its advantages, but in NFFT most wrappers are for MATLAB rather than python. At least, it seems like that.

kohr-h commented 6 years ago

I had a closer look at their docs (FINUFFT, that is). They claim that they're faster than NFFT if the points are not close to uniform, and that they use less RAM. Could be interesting in any case. The API is a bit crude, but it's small and shouldn't be too hard to wrap as an ODL operator.

I wouldn't be entirely sure how to package it up (new operator or existing operator?), but there's no reason why we shouldn't have (potentially) multiple NUFFT backends.

If anybody wants to go ahead with this, great.

As an aside, what should definitely part of an effort to wrap this library is to make a conda package, ideally on conda-forge. Having a wrapper for a library that can't be easily installed is a non-starter.

kohr-h commented 6 years ago

They claim that they're faster

The Python interface is hard-wired to double precision, so I'm not sure how much that claim is worth for us, e.g. when comparing against single precision NFFT.

adler-j commented 6 years ago

I guess @ozanoktem has some pseduo-inside connections over there, perhaps we could ask for e.g. single precision and a condo library. Until then I'd use NFFT.

kohr-h commented 6 years ago

The library itself supports single precision, and it can in fact be compiled for different precisions and uses separate names for the shared libs, so that part is good. It's only the Python bindings that lack support for float32. I don't think it's too hard to add that support in the Python code, only the loading of the correct shared library needs to be handled depending on dtype, or both should be loaded.

zaccharieramzi commented 5 years ago

Hi !

I wanted to know what was the status of this. Indeed, following a discussion I had via mail with @adler-j , I would like to implement an ODL operator for the non-uniform FFT in order to integrate it in an NN (similar to the work done for learned primal-dual reconstruction).

If there is already someone working on this we could sync up (I didn't see any open or closed PRs related to this matter at first sight), otherwise I will fork and do my thing. I am open to discussing the implementation details like the backend, or anything that comes on the table.

kohr-h commented 5 years ago

That would be awesome @zaccharieramzi. I think of the core team I would be the most likely person to have started this, and I haven't. But I'd roughly know how to do it. If you want to discuss anything, just post here. I'll have an eye on the thread.