10

我正在尝试将两个用(SciPy's FFTPACK RFFT)转换的二维数组相乘fftpack_rfft2d(),结果与我从scipy_rfft2d()(SciPy's FFT RFFT)得到的结果不兼容。

下图共享脚本的输出,其中显示:

  • 两个输入数组的初始化值;
  • 两个数组在使用 SciPy 对 RFFT 的 FFT 实现进行转换后,使用 ;scipy_rfft2d()进行反向转换后的乘法输出scipy_irfft2d()
  • 使用 SciPy 对 RFFT 的 FFTPACK 实现与fftpack_rfft2d()和相同的事情fftpack_irfft2d()
  • 一个测试的结果np.allclose()是检查两个乘法的结果在它们被转换回它们各自的 IRFFT 实现后是否相同。

需要说明的是,红色矩形显示的是逆变换IRFFT后的乘法结果:左边的矩形使用了SciPy的FFT IRFFT;右边的矩形,SciPy 的 FFTPACK IRFFT。当与 FFTPACK 版本的乘法固定时,它们应该呈现相同的数据。

我认为 FFTPACK 版本的乘法结果不正确,因为scipy.fftpack返回结果 RFFT 数组中的实部和虚部与 scipy.fft 的 RFFT不同

  • 我相信来自scipy.fftpack 的RFFT返回一个数组,其中一个元素包含实部,下一个元素包含其虚部;
  • 在来自 scipy.fft 的RFFT中,每个元素都是一个复数,因此能够同时保存实部和虚部;

如果我错了,请纠正我!我还想指出,由于scipy.fftpack不提供用于转换 2D 数组的函数,例如rfft2()and irfft2(),我在下面的代码中提供了我自己的实现:

import numpy as np
from scipy import fftpack as scipy_fftpack
from scipy import fft as scipy_fft

# SCIPY RFFT 2D
def scipy_rfft2d(matrix):
    fftRows = [scipy_fft.rfft(row) for row in matrix]
    return np.transpose([scipy_fft.fft(row) for row in np.transpose(fftRows)])

# SCIPY IRFFT 2D
def scipy_irfft2d(matrix, s):
    fftRows = [scipy_fft.irfft(row) for row in matrix]
    return np.transpose([scipy_fft.ifft(row) for row in np.transpose(fftRows)])

# FFTPACK RFFT 2D
def fftpack_rfft2d(matrix):
    fftRows = [scipy_fftpack.rfft(row) for row in matrix]
    return np.transpose([scipy_fftpack.rfft(row) for row in np.transpose(fftRows)])

# FFTPACK IRFFT 2D
def fftpack_irfft2d(matrix):
    fftRows = [scipy_fftpack.irfft(row) for row in matrix]
    return np.transpose([scipy_fftpack.irfft(row) for row in np.transpose(fftRows)])


print('\n####################     INPUT DATA     ###################\n')

# initialize two 2D arrays with random data for testing
in1 = np.array([[0,   0,   0,   0], \
                [0, 255, 255,   0], \
                [0,   0, 255, 255], \
                [0,   0,   0,   0]])

print('\nin1 shape=', in1.shape, '\n', in1)

in2 = np.array([[0,   0,   0,   0], \
                [0,   0, 255,   0], \
                [0, 255, 255,   0], \
                [0, 255,   0,   0]])

print('\nin2 shape=', in2.shape, '\n', in2)

print('\n###############    SCIPY: 2D RFFT (MULT)    ###############\n')

# transform both inputs with SciPy RFFT for 2D
scipy_rfft1 = scipy_fft.rfftn(in1)
scipy_rfft2 = scipy_fft.rfftn(in2)

print('* Output from scipy_fft.rfftn():')
print('scipy_fft1 shape=', scipy_rfft1.shape, '\n', scipy_rfft1.real)
print('\nscipy_fft2 shape=', scipy_rfft2.shape, '\n', scipy_rfft2.real)

# perform multiplication between two 2D arrays from SciPy RFFT
scipy_rfft_mult = scipy_rfft1 * scipy_rfft2

# perform inverse RFFT for 2D arrays using SciPy
scipy_data = scipy_fft.irfftn(scipy_rfft_mult, in1.shape) # passing shape guarantees the output will have the original data size
print('\n* Output from scipy_fft.irfftn():')
print('scipy_data shape=', scipy_data.shape, '\n', scipy_data)

print('\n###############   FFTPACK: 2D RFFT (MULT)   ###############\n')

# transform both inputs with FFTPACK RFFT for 2D
fftpack_rfft1 = fftpack_rfft2d(in1)
fftpack_rfft2 = fftpack_rfft2d(in2)
print('* Output from fftpack_rfft2d():')
print('fftpack_rfft1 shape=', fftpack_rfft1.shape, '\n', fftpack_rfft1)
print('\nfftpack_rfft2 shape=', fftpack_rfft2.shape, '\n', fftpack_rfft2)

# TODO: perform multiplication between two 2D arrays from FFTPACK RFFT
fftpack_rfft_mult = fftpack_rfft1 * fftpack_rfft2 # this doesn't work

# perform inverse RFFT for 2D arrays using FFTPACK
fftpack_data = fftpack_irfft2d(fftpack_rfft_mult)
print('\n* Output from fftpack_irfft2d():')
print('fftpack_data shape=', fftpack_data.shape, '\n', fftpack_data)

print('\n#####################      RESULT     #####################\n')

# compare FFTPACK result with SCIPY
print('\nIs fftpack_data equivalent to scipy_data?', np.allclose(fftpack_data, scipy_data), '\n')

假设我的猜测是正确的,那么将生成的两个二维数组相乘的函数的正确实现是fftpack_rfft2d()什么?请记住:生成的数组必须能够用fftpack_irfft2d().

仅邀请解决二维问题的答案。那些对如何乘以一维 FFTPACK 数组感兴趣的人可以查看这个线程

4

5 回答 5

4

正确的功能:

import numpy as np
from scipy import fftpack as scipy_fftpack
from scipy import fft as scipy

# FFTPACK RFFT 2D
def fftpack_rfft2d(matrix):
    fftRows = scipy_fftpack.fft(matrix, axis=1)
    fftCols = scipy_fftpack.fft(fftRows, axis=0)

    return fftCols

# FFTPACK IRFFT 2D
def fftpack_irfft2d(matrix):
    ifftRows = scipy_fftpack.ifft(matrix, axis=1)
    ifftCols = scipy_fftpack.ifft(ifftRows, axis=0)

    return ifftCols.real

您以错误的方式计算了 2D FFT。是的,可以使用rfft() 计算第一个 FFT(在您的情况下按列) ,但是必须在第一个 FFT(按列)的复数输出上提供第二个 FFT 计算,因此rfft()的输出必须被转换成真正的 复谱。此外,这意味着您必须使用fft()而不是rfft()进行第二次 FFT 逐行。因此,在两种计算中使用fft()会更方便。

此外,您将输入数据作为numpy 2D 数组,为什么要使用列表推导?直接使用fftpack.fft()这样会快很多

  • 如果您已经只有由错误函数计算的 2D 数组并且需要将它们相乘:那么,我认为,尝试使用相同的“错误”方式从错误的 2D FFT 重建输入数据,然后计算正确的 2D FFT

==================================================== ===============

具有新功能版本的完整测试代码:

import numpy as np
from scipy import fftpack as scipy_fftpack
from scipy import fft as scipy_fft


# FFTPACK RFFT 2D
def fftpack_rfft2d(matrix):
    fftRows = scipy_fftpack.fft(matrix, axis=1)
    fftCols = scipy_fftpack.fft(fftRows, axis=0)

    return fftCols

# FFTPACK IRFFT 2D
def fftpack_irfft2d(matrix):
    ifftRows = scipy_fftpack.ifft(matrix, axis=1)
    ifftCols = scipy_fftpack.ifft(ifftRows, axis=0)

    return ifftCols.real

print('\n####################     INPUT DATA     ###################\n')

# initialize two 2D arrays with random data for testing
in1 = np.array([[0,   0,   0,   0], \
                [0, 255, 255,   0], \
                [0,   0, 255, 255], \
                [0,   0,   0,   0]])

print('\nin1 shape=', in1.shape, '\n', in1)

in2 = np.array([[0,   0,   0,   0], \
                [0,   0, 255,   0], \
                [0, 255, 255,   0], \
                [0, 255,   0,   0]])

print('\nin2 shape=', in2.shape, '\n', in2)

print('\n###############    SCIPY: 2D RFFT (MULT)    ###############\n')

# transform both inputs with SciPy RFFT for 2D
scipy_rfft1 = scipy_fft.fftn(in1)
scipy_rfft2 = scipy_fft.fftn(in2)

print('* Output from scipy_fft.rfftn():')
print('scipy_fft1 shape=', scipy_rfft1.shape, '\n', scipy_rfft1)
print('\nscipy_fft2 shape=', scipy_rfft2.shape, '\n', scipy_rfft2)

# perform multiplication between two 2D arrays from SciPy RFFT
scipy_rfft_mult = scipy_rfft1 * scipy_rfft2

# perform inverse RFFT for 2D arrays using SciPy
scipy_data = scipy_fft.irfftn(scipy_rfft_mult, in1.shape) # passing shape guarantees the output will
                                                          # have the original data size
print('\n* Output from scipy_fft.irfftn():')
print('scipy_data shape=', scipy_data.shape, '\n', scipy_data)

print('\n###############   FFTPACK: 2D RFFT (MULT)   ###############\n')

# transform both inputs with FFTPACK RFFT for 2D
fftpack_rfft1 = fftpack_rfft2d(in1)
fftpack_rfft2 = fftpack_rfft2d(in2)
print('* Output from fftpack_rfft2d():')
print('fftpack_rfft1 shape=', fftpack_rfft1.shape, '\n', fftpack_rfft1)
print('\nfftpack_rfft2 shape=', fftpack_rfft2.shape, '\n', fftpack_rfft2)

# TODO: perform multiplication between two 2D arrays from FFTPACK RFFT
fftpack_rfft_mult = fftpack_rfft1 * fftpack_rfft2 # this doesn't work

# perform inverse RFFT for 2D arrays using FFTPACK
fftpack_data = fftpack_irfft2d(fftpack_rfft_mult)
print('\n* Output from fftpack_irfft2d():')
print('fftpack_data shape=', fftpack_data.shape, '\n', fftpack_data)

print('\n#####################      RESULT     #####################\n')

# compare FFTPACK result with SCIPY
print('\nIs fftpack_data equivalent to scipy_data?', np.allclose(fftpack_data, scipy_data), '\n')

输出是:

####################     INPUT DATA     ###################


in1 shape= (4, 4) 
 [[  0   0   0   0]
 [  0 255 255   0]
 [  0   0 255 255]
 [  0   0   0   0]]

in2 shape= (4, 4) 
 [[  0   0   0   0]
 [  0   0 255   0]
 [  0 255 255   0]
 [  0 255   0   0]]

###############    SCIPY: 2D RFFT (MULT)    ###############

* Output from scipy_fft.rfftn():
scipy_fft1 shape= (4, 4) 
 [[1020.  -0.j -510.  +0.j    0.  -0.j -510.  -0.j]
 [-510.-510.j    0.  +0.j    0.  +0.j  510.+510.j]
 [   0.  -0.j    0.+510.j    0.  -0.j    0.-510.j]
 [-510.+510.j  510.-510.j    0.  -0.j    0.  -0.j]]

scipy_fft2 shape= (4, 4) 
 [[1020.  -0.j -510.-510.j    0.  -0.j -510.+510.j]
 [-510.  +0.j  510.+510.j    0.-510.j    0.  -0.j]
 [   0.  -0.j    0.  +0.j    0.  -0.j    0.  -0.j]
 [-510.  -0.j    0.  +0.j    0.+510.j  510.-510.j]]

* Output from scipy_fft.irfftn():
scipy_data shape= (4, 4) 
 [[130050.  65025.  65025. 130050.]
 [ 65025.      0.      0.  65025.]
 [ 65025.      0.      0.  65025.]
 [130050.  65025.  65025. 130050.]]

###############   FFTPACK: 2D RFFT (MULT)   ###############

* Output from fftpack_rfft2d():
fftpack_rfft1 shape= (4, 4) 
 [[1020.  -0.j -510.  +0.j    0.  -0.j -510.  +0.j]
 [-510.-510.j    0.  +0.j    0.  +0.j  510.+510.j]
 [   0.  +0.j    0.+510.j    0.  +0.j    0.-510.j]
 [-510.+510.j  510.-510.j    0.  +0.j    0.  +0.j]]

fftpack_rfft2 shape= (4, 4) 
 [[1020.  -0.j -510.-510.j    0.  -0.j -510.+510.j]
 [-510.  +0.j  510.+510.j    0.-510.j    0.  +0.j]
 [   0.  +0.j    0.  +0.j    0.  +0.j    0.  +0.j]
 [-510.  +0.j    0.  +0.j    0.+510.j  510.-510.j]]

* Output from fftpack_irfft2d():
fftpack_data shape= (4, 4) 
 [[130050.+0.j  65025.+0.j  65025.+0.j 130050.+0.j]
 [ 65025.+0.j      0.+0.j      0.+0.j  65025.+0.j]
 [ 65025.+0.j      0.+0.j      0.+0.j  65025.+0.j]
 [130050.+0.j  65025.+0.j  65025.-0.j 130050.+0.j]]

#####################      RESULT     #####################


Is fftpack_data equivalent to scipy_data? True 
于 2020-05-18T08:35:33.983 回答
3

你的假设是正确的。FFTPACK 以格式返回单个实向量中的所有系数

[y(0),Re(y(1)),Im(y(1)),...,Re(y(n/2))]              if n is even
[y(0),Re(y(1)),Im(y(1)),...,Re(y(n/2)),Im(y(n/2))]   if n is odd

其中 scipy.rfft 返回一个复数向量

[y(0),Re(y(1)) + 1.0j*Im(y(1)),...,Re(y(n/2) + 1.0j*Im(y(n/2)))]

所以你需要使用适当的步幅形成一个向量,如下所示:

y_fft = np.cat([y_fftpack[0], y_fftpack[1:2:] + 1.0j*y_fftpack[2:2:]])
于 2020-05-11T03:59:29.197 回答
2

@Andrei是对的:仅使用复值 FFT 会简单得多(尽管他的实现不必要地复杂,只需使用scipy.fftpack.fft2)。正如我在评论中所说,最好的选择是切换到scipy.fft更易于使用的;fftpack不赞成使用它。

但是,如果您确实需要使用fftpack,并且确实想通过使用该rfft函数来节省一些计算时间,那么这是正确的方法。它需要在计算另一个维度之前将函数的实值输出转换为rfft复值数组。fft使用此解决方案,fftpack_rfft2d下方输出其输入的一半 2D FFT,另一半是冗余的。

import numpy as np
from scipy import fftpack

# FFTPACK RFFT 2D
def fftpack_rfft1d(matrix):
    assert not (matrix.shape[1] & 0x1)
    tmp = fftpack.rfft(matrix, axis=1)
    assert  tmp.dtype == np.dtype('float64')
    return np.hstack((tmp[:, [0]], np.ascontiguousarray(tmp[:, 1:-1]).view(np.complex128), tmp[:, [-1]]))

def fftpack_rfft2d(matrix):
    return fftpack.fft(fftpack_rfft1d(matrix), axis=0)

# FFTPACK IRFFT 2D
def fftpack_irfft1d(matrix):
    assert  matrix.dtype == np.dtype('complex128')
    tmp = np.hstack((matrix[:, [0]].real, np.ascontiguousarray(matrix[:, 1:-1]).view(np.float64), matrix[:, [-1]].real))
    return fftpack.irfft(tmp, axis=1)

def fftpack_irfft2d(matrix):
    return fftpack_irfft1d(fftpack.ifft(matrix, axis=0))

######

# test data
in1 = np.random.randn(256,256)
in2 = np.random.randn(256,256)

# fftpack.fft2
gt_result = fftpack.ifft2(fftpack.fft2(in1) * fftpack.fft2(in2)).real

# fftpack_rfft2d
our_result = fftpack_irfft2d(fftpack_rfft2d(in1) * fftpack_rfft2d(in2) )

# compare
print('\nIs our result equivalent to the ground truth?', np.allclose(gt_result, our_result), '\n')

[此代码仅适用于大小均匀的图像,我没有费心将其设为通用,请参阅此处了解如何操作)。

尽管如此,由于该解决方案需要数据副本,因此它实际上比仅使用普通的复数值 FFT ( fftpack.fft2) 慢,即使它执行的计算量更少:

import time

tic = time.perf_counter()
for i in range(100):
   fftpack.fft(in1)
toc = time.perf_counter()
print(f"fftpack.fft() takes {toc - tic:0.4f} seconds")

tic = time.perf_counter()
for i in range(100):
   fftpack_rfft2d(in1)
toc = time.perf_counter()
print(f"fftpack_rfft2d() takes {toc - tic:0.4f} seconds")

输出:

fftpack.fft() takes 0.0442 seconds
fftpack_rfft2d() takes 0.0664 seconds

所以,确实,坚持fftpack.fft(或者更确切地说scipy.fft.fft,如果可以的话)。

于 2020-05-18T15:53:07.120 回答
1

要乘以 2 个复数系数数组,您必须进行复数乘法。

请参阅https://en.m.wikipedia.org/wiki/Complex_number的运算部分中的乘法

您不能只将实数分量相乘,然后将虚数分量分开或拆分元素,这可能就是您的 fftpack 矩阵 mul 产生垃圾的原因。

于 2020-05-18T00:42:13.987 回答
1

除了@CrisLuengo 答案(https://stackoverflow.com/a/61873672/501852)。

性能测试

测试fftpack.FFTfftpack.RFFT - 1D

# test data
sz =50000
sz = fftpack.next_fast_len(sz)
in1 = np.random.randn(sz)

print(f"Input (len = {len(in1)}):", sep='\n')

rep = 1000

tic = time.perf_counter()
for i in range(rep):
    spec1 = fftpack.fft(in1,axis=0)
toc = time.perf_counter()
print("", f"Spectrum FFT (len = {len(spec1)}):",
      f"spec1 takes {10**6*((toc - tic)/rep):0.4f} us", sep="\n")

sz2 = sz//2 + 1
spec2 = np.empty(sz2, dtype=np.complex128)

tic = time.perf_counter()
for i in range(rep):
    tmp = fftpack.rfft(in1)

    assert  tmp.dtype == np.dtype('float64')

    if not sz & 0x1:
        end = -1 
        spec2[end] = tmp[end]
    else:
        end = None

    spec2[0] = tmp[0]
    spec2[1:end] = tmp[1:end].view(np.complex128)

toc = time.perf_counter()
print("", f"Spectrum RFFT (len = {len(spec2)}):",
      f"spec2 takes {10**6*((toc - tic)/rep):0.4f} us", sep="\n")

结果是

Input (len = 50000):

Spectrum FFT (len = 50000):
spec1 takes 583.5880 us

Spectrum RFFT (len = 25001):
spec2 takes 476.0843 us
  • 因此,与大型阵列相比,使用fftpack.rfft()进一步将其输出投射到complex视野中要快约 15-20%fftpack.fft()

测试fftpack.FFTfftpack.FFT2 - 2D

2D 案例的类似测试:

# test data
sz = 5000
in1 = np.random.randn(sz, sz)

print(f"Input (len = {len(in1)}):", sep='\n')

rep = 1

tic = time.perf_counter()
for i in range(rep):
    spec1 = np.apply_along_axis(fftpack.fft, 0, in1)
    spec1 = np.apply_along_axis(fftpack.fft, 1, spec1)
toc = time.perf_counter()
print("", f"2D Spectrum FFT with np.apply_along_axis (len = {len(spec1)}):",
      f"spec1 takes {10**0*((toc - tic)/rep):0.4f} s", sep="\n")


tic = time.perf_counter()
for i in range(rep):
    spec2 = fftpack.fft(in1,axis=0)
    spec2 = fftpack.fft(spec2,axis=1)
toc = time.perf_counter()
print("", f"2D Spectrum 2xFFT (len = {len(spec2)}):",
      f"spec2 takes {10**0*((toc - tic)/rep):0.4f} s", sep="\n")

tic = time.perf_counter()
for i in range(rep):
    spec3 = fftpack.fft2(in1)
toc = time.perf_counter()
print("", f"2D Spectrum FFT2 (len = {len(spec3)}):",
      f"spec3 takes {10**0*((toc - tic)/rep):0.4f} s", sep="\n")

# compare
print('\nIs spec1 equivalent to the spec2?', np.allclose(spec1, spec2))
print('\nIs spec2 equivalent to the spec3?', np.allclose(spec2, spec3), '\n')

大小矩阵的结果 = 5x5

Input (len = 5):

2D Spectrum FFT with np.apply_along_axis (len = 5):
spec1 takes 0.000183 s

2D Spectrum 2xFFT (len = 5):
spec2 takes 0.000010 s

2D Spectrum FFT2 (len = 5):
spec3 takes 0.000012 s

Is spec1 equivalent to the spec2? True

Is spec2 equivalent to the spec3? True

大小矩阵的结果 = 500x500

Input (len = 500):

2D Spectrum FFT with np.apply_along_axis (len = 500):
spec1 takes 0.017626 s

2D Spectrum 2xFFT (len = 500):
spec2 takes 0.005324 s

2D Spectrum FFT2 (len = 500):
spec3 takes 0.003528 s

Is spec1 equivalent to the spec2? True

Is spec2 equivalent to the spec3? True 

大小矩阵的结果 = 5000x5000

Input (len = 5000):

2D Spectrum FFT with np.apply_along_axis (len = 5000):
spec1 takes 2.538471 s

2D Spectrum 2xFFT (len = 5000):
spec2 takes 0.846661 s

2D Spectrum FFT2 (len = 5000):
spec3 takes 0.574397 s

Is spec1 equivalent to the spec2? True

Is spec2 equivalent to the spec3? True

结论

从上面的测试来看,似乎fftpack.fft2()对于更大的矩阵使用更有效。

使用ofnp.apply_along_axis()是最慢的方法。

于 2020-05-18T21:40:40.940 回答