How to implement a 2D RFFT algorithm based on 1D RFFT?

Question

I'm trying to implement NumPy's rfft2(), the RFFT function that supports arrays with 2-dimensions, by performing 1D RFFT on each row and then performing 1D RFFT again on each column of the previous result.

This approach works well to implement a 2D FFT function, as discussed previously on this post, but it doesn't seem to work for 2D RFFT.

Here's a script that implements a custom 2D FFT function that this follows this idea using the 1D version of NumPy's FFT as basis and later compares its result to the actual 2D version from NumPy:

import cmath
import numpy as np
import math

def my_fft2d(matrix):
    fft_rows = [np.fft.fft(row) for row in matrix]
    return np.transpose([np.fft.fft(row) for row in np.transpose(fft_rows)])


# initialize test data
img = np.array([[0,0,0,0], [0,1,0,0], [0,0,0,0], [0,0,0,0]])
print('img shape=', img.shape)

# perform custom FFT2D and print result
custom_result = my_fft2d(img)
print('\ncustom_result shape=', custom_result.shape)
for row in custom_result:
   print(', '.join(['%.3f + %.3fi' % (x.real, x.imag) for x in row]))

# perform numpy FFT2D and print result
numpy_result = np.fft.fft2(img)
print('\nnumpy_result shape=', numpy_result.shape)
for row in numpy_result:
   print(', '.join(['%.3f + %.3fi' % (x.real, x.imag) for x in row]))

# compare results
print('\nAre the results equivalent to NumPy?', np.allclose(custom_result, custom_result))
print('ASSERT(assert_array_almost_equal):', np.testing.assert_array_almost_equal(custom_result, custom_result))

Output:

img shape= (4, 4)

custom_result shape= (4, 4)
1.000 + 0.000i, 0.000 + -1.000i, -1.000 + 0.000i, 0.000 + 1.000i
0.000 + -1.000i, -1.000 + 0.000i, 0.000 + 1.000i, 1.000 + 0.000i
-1.000 + 0.000i, 0.000 + 1.000i, 1.000 + 0.000i, 0.000 + -1.000i
0.000 + 1.000i, 1.000 + 0.000i, 0.000 + -1.000i, -1.000 + 0.000i

numpy_result shape= (4, 4)
1.000 + 0.000i, 0.000 + -1.000i, -1.000 + 0.000i, 0.000 + 1.000i
0.000 + -1.000i, -1.000 + 0.000i, 0.000 + 1.000i, 1.000 + 0.000i
-1.000 + 0.000i, 0.000 + 1.000i, 1.000 + 0.000i, 0.000 + -1.000i
0.000 + 1.000i, 1.000 + 0.000i, 0.000 + -1.000i, -1.000 + 0.000i

Are the results equivalent to NumPy? True
ASSERT(assert_array_almost_equal): None

The output of the script shows that my_fft2d() implementation is compatible with np.fft.fft2().

However, when the same logic is applied to implement the RFFT version of the transform, the resulting array has a different shape, as the script below demonstrates:

def my_rfft2d(matrix):
    fft_rows = [np.fft.rfft(row) for row in matrix]
    return np.transpose([np.fft.rfft(row) for row in np.transpose(fft_rows)])


# initialize test data
img = np.array([[0,0,0,0], [0,1,0,0], [0,0,0,0], [0,0,0,0]])
print('img shape=', img.shape)

# perform custom FFT2D and print result
custom_result = my_rfft2d(img)
print('\ncustom_result shape=', custom_result.shape)
for row in custom_result:
   print(', '.join(['%.3f + %.3fi' % (x.real, x.imag) for x in row]))

# perform numpy FFT2D and print results
numpy_result = np.fft.rfft2(img)
print('\nnumpy_result shape=', numpy_result.shape)
for row in numpy_result:
   print(', '.join(['%.3f + %.3fi' % (x.real, x.imag) for x in row]))

Output:

img shape= (4, 4)
C:\Users\username\AppData\Roaming\Python\Python37\site-packages\numpy\fft\_pocketfft.py:77: ComplexWarning: Casting complex values to real discards the imaginary part
  r = pfi.execute(a, is_real, is_forward, fct)

custom_result shape= (3, 3)
1.000 + 0.000i, 0.000 + 0.000i, -1.000 + 0.000i
0.000 + -1.000i, 0.000 + 0.000i, 0.000 + 1.000i
-1.000 + 0.000i, 0.000 + 0.000i, 1.000 + 0.000i

numpy_result shape= (4, 3)
1.000 + 0.000i, 0.000 + -1.000i, -1.000 + 0.000i
0.000 + -1.000i, -1.000 + 0.000i, 0.000 + 1.000i
-1.000 + 0.000i, 0.000 + 1.000i, 1.000 + 0.000i
0.000 + 1.000i, 1.000 + 0.000i, 0.000 + -1.000i

As you can see, there are two problems in the output:

• a warning from numpy complains about something I'm not totally sure how to fix;
• the custom implementation of 2D RFFT returns a result that has less rows than the one returned by np.fft.rfft2();

How can I fix this problem and make my_rfft2d() compatible with np.fft.rfft2()?

Answer 1

Like the commenter said. You should take the fft the second time. This is because the output from the rfft of the rows is complex. This solves the complex to real error, as well as the shape problem.

import numpy as np

def my_rfft2d(matrix):
    fft_rows = [np.fft.rfft(row) for row in matrix]
    return np.transpose([np.fft.fft(row) for row in np.transpose(fft_rows)])


# initialize test data
img = np.array([[0,0,0,0], [0,1,0,0], [0,0,0,0], [0,0,0,0]])
print('img shape=', img.shape)

# perform custom FFT2D and print result
custom_result = my_rfft2d(img)
print('\ncustom_result shape=', custom_result.shape)
for row in custom_result:
   print(', '.join(['%.3f + %.3fi' % (x.real, x.imag) for x in row]))

# perform numpy FFT2D and print results
numpy_result = np.fft.rfft2(img)
print('\nnumpy_result shape=', numpy_result.shape)
for row in numpy_result:
   print(', '.join(['%.3f + %.3fi' % (x.real, x.imag) for x in row]))

Output:

custom_result shape= (4, 3)
1.000 + 0.000i, 0.000 + -1.000i, -1.000 + 0.000i
0.000 + -1.000i, -1.000 + 0.000i, 0.000 + 1.000i
-1.000 + 0.000i, 0.000 + 1.000i, 1.000 + 0.000i
0.000 + 1.000i, 1.000 + 0.000i, 0.000 + -1.000i

numpy_result shape= (4, 3)
1.000 + 0.000i, 0.000 + -1.000i, -1.000 + 0.000i
0.000 + -1.000i, -1.000 + 0.000i, 0.000 + 1.000i
-1.000 + 0.000i, 0.000 + 1.000i, 1.000 + 0.000i
0.000 + 1.000i, 1.000 + 0.000i, 0.000 + -1.000i

Answer 2

As I said in my comment, after taking the rfft of the rows, you should take the fft instead of rfft because rfft result is complex in general.

I don't know why you are trying to go real, but if you really want to go all real, you should use DCT (Discrete Cosine Transform) instead of FFT, because DCT output is real. You can take the same approach as what you are doing to calculate the 2D FFT above, because you can decompose 2D DCT in a similar way.