How to use nufft or nufftn to compute NonUniformFFT of an image with missing (not sampled) pixels?

Given an image x for which I have non sampled values i.e. some pixels are randomly (or given a pattern but lets say randomly) sampled, i.e. I have a nonuniformly sampled 2D signal. I would like to compute its NUFFT.

In the Matlab doc I see this example:

t = [1:10 11:2:29]';
x = t;
y = t';
z = reshape(t,[1 1 20]);
X = cos(2*pi*0.01*x) + sin(2*pi*0.02*y) + cos(2*pi*0.03*z);
Y = nufftn(X,{t,t,t});

Unfortunately this does not help me. The X is a 3D matrix of size 20x20x20 with just the nonuniformly sampled values however I would like to keep the dimenstions of my image e.g. 256x256. The idea I had was to put zeros in the non-sampled pixels and the greyscale value otherwise and give in t the coordinates of the sampled pixels but this does not work. I could just take the nonuniformly sampled pixels of my image and form a new matrix but its shape would be arbitrary, I could even just concatenate all the pixels in a long vector... I have no idea how to do it and how nufftn understands this.

So my question is: how to obtain the NUFFT (2D) of an undersampled 2D image? I would like to understand what happends with the reshaping/what shapes are understood/used by NUFFT... all this seems very obscure to me.

Answer 1

[Chris Turnes]

I'm not sure what format your data is in; however, for the purposes of showing how you might do this, suppose you had a list of pixel locations (stored as linear indices) called sampledLocations for which you have corresponding values. Then to compute the 2-D non-uniform FFT of your non-uniform image samples onto a uniform 2-D grid you would do:

% Just to get some data.
X = randn(256, 256);
% Suppose you pick 100 random pixels to sample.
sampledLocations = randperm(256*256, 100)';
% Convert these to x-y locations.
[i, j] = ind2sub([256 256], sampledLocations);
% Specify the uniformly spaced output frequencies you want.
funiform = (0:255) / 256;
% Non-uniform input points specified as M x 2 vector.
% Uniform output grid specified via cells.
Y = nufftn(X(sampledLocations), [i, j], {funiform, funiform});
% Reshape to your grid size.
Y = reshape(Y, [256 256]);

[Michael Thompson]

IMHO, the more "powerful"/complicated a function is the more important it is to verify its function before use. My attempts to verify the behavior of the nufftn function haven't gone swimmingly so I wanted to ask:

Has the nufftn been tested with fully sampled data sets, and shown to be equivalent to the fft functions?

Is there a location where Matlab provides access to verification code or results?

There is some sample code here and on the nufftn help page, but it's limited to pretty artificial scenarios; my opinion.