How to create 2D DFT matrix to transform a vectorized 2D image

Say I have an image I of size mxn and I want to find the pxq 2D fourier transform of this image where p&q are larger than m&n.

However, I want my transform to be in the form IF = FT*I(:). Where I(:) is the vectorized version of my image of size m*nx1.

And I don't know how to get FT to represent the 2D fourioer transform correctly.

I want this to be able to use it in a recursive optimization algorithm.

I used the kronecker of the 1D DFT matrix but MATLAB keeps telling me I have singularities in my matrix.

The code I have written so far,

% Creating the 1D fft matrix to be used in the kron function
filt_size = 25;
n_pts = 10*filt_size;

fft_mtx = zeros(n_pts,filt_size);
test_vec = zeros(25,1);

for k = 1:25

      test_vec(k,1) = 1;
      fft_mtx(:,k) = fft(test_vec,n_pts);
      test_vec(k,1) = 0;

end

% The fft applied using the kron function

F = kron(fft_mtx,fft_mtx);

Answer 1

[xadu]

I know this is an old quesiton, but posting here in case someone finds it useful. Here are three different ways of getting the 2D DFT of an image. What is asked for is shown in method 2, by the matrix called Fvec, which can be applied to a vectorized form of the input image.

%2d dft transforms
%gen image
m = 10; n = 20;
x = rand(m,n);

%2d dft, method 1: apply to cols at a time, and then to rows
F1D_m = dftmtx(m);
F1D_n = dftmtx(n);
X1 = F1D_m * x * F1D_n;

%2d dft, method 2: vectorize input, gen matrix by linear transformation ideas
%refer to sec 2.6 of Linear Algebra, Gilbert Strang
x = reshape(x,[],1);
Fvec = zeros(m*n,m*n);
for i=1:m*n
    inpvec = zeros(m*n,1);
    inpvec(i) = 1;
    inpvec = reshape(inpvec,m,n);
    %finding out one col of the transformation. since i/p and o/p basis are
    %canonical, nothing further is required
    opvec = fft2(inpvec); 
    opvec = reshape(opvec,[],1);
    Fvec(:,i) = opvec;
end
X2 = Fvec * x; %input,output are vectors
X2 = reshape(X2,m,n); %convert back to image
x = reshape(x,m,n); %convert back to image

%2d dft, method 3: directly use the 2d fft
X3 = fft2(x);

Answer 2

[kerry zhang]

I think I had the same question as you did. I spent sometime to figure it out. Hope my answer can help someone later.

Say you have a 2D image with size of img_x * img_y. Then you acquire the signal in a 2D fourier domain, here is called K space with size of kx * ky.

First you need to vectorize the 2D image matrix coordinate in to a (img_x*img_y) * 2 vector by

img_r = zeros(img_x * img_y, 2);
img_r(:,1) = repmat([1:img_x],[1 img_y]);
img_r(:,2) = reshape(repmat([1:img_y], [img_x, 1]), img_x*img_y, 1);

Then the coordinates of the K-space signal is stored in the same fashion with the size of (kx * ky) * 2

One important step here is to normalize the K-space coordinates. The rule is the highest frequency modulation should give a linear phase step of 2pi in both directions. Otherwise you'll have useless repetitions. This may also scale up the sampling interval causing aliasing in the reconstructed images.

K_vec_normed(:,1) = K_vec(:,1)/kx*2*pi;
K_vec_normed(:,2) = K_vec(:,2)/ky*2*pi;

Then the Fourier encoding matrix can be obtained as

F = exp(-i.* (K_vec_normed * img_r'));

If the image is more than 2D, the idea is the same. The vector will have N columns for a ND image.

[Jaweria Amjad]

what is K_vec here?

Answer 3

[Image Analyst]

I don't understand. You say you want "FT*I(:)". First of all, what is FT? And why are you multiplying a spectral domain image by a spatial domain column vector? It doesn't make sense. Or did you mean to take the FT of I(:), like FT{I(:)}? Even that doesn't make sense to me. What is that supposed to represent? I mean, you're going to have lower frequencies in the Ft of a 1D column vector than you'd have in the 2D version of it, so you're making up stuff that isn't really there. Then you go into a loop where you're taking the FT of delta functions as they move along in space, which just gives a constant, though the phase changes. It has nothing to do with I, some image which you never even read in or created. Then we're on to doing kron() - what's the purpose of that? Finally I don't see anything recursive about this or why it would even be desired. So I don't understand the explanation/theory and I don't see how the code does anything like what the theory describes. I'm totally lost.

[Abdullah]

I am transforming my image to a 1D vector so that taking the DFT of this image would be utilized through a liner transformation as follows,

IF = F*I_v

where I_v is a 1D vector representing the 2D image by reshaping it. So, if I is an m by n matrix then I_v is an mn by 1 vector.

F is 2d DFT matrix.

And IF is the 1D vector of size pq by 1 of the 2D spectrum of the image (pq > mn)

. .

This matrix multiplication form is highly used in convex optimization problems.