FFTW - 计算实数二维FFT，特殊需求

Question

我正在使用FFTW3在C++中计算2D实数FFT。我已经阅读了手册，但还有一些问题。从手册上看：http://www.fftw.org/fftw3_doc/One_002dDimensional-DFTs-of-Real-Data.html#One_002dDimensional-DFTs-of-Real-Data

作为交换，用户牺牲了FFTW的复杂变换的一部分简单性，以获得速度和空间优势。首先，输入和输出数组的大小和类型不同：输入是n个实数，而输出是n/2+1个复数（非冗余输出）；这也需要对输入数组进行轻微的“填充”以进行原位变换。其次，逆变换（复数到实数）默认情况下会覆盖其输入数组。这些不便之处都不应该对用户构成严重问题，但重要的是要意识到它们。

1. 我知道我需要将输入的2D矩阵转换为行顺序的1D向量。但输出长什么样？n/2 + 1个数字代表什么？换句话说，如何重新排序输出以获取2D矩阵？

2. 具体来说，我需要做什么才能创建这个“填充”？

- tir38

---

哼。在我使用过的其他FFT库中，由于Nyquist值和直流分量（DC offset）都是实数，因此Nyquist值只是打包到“X_0”的虚部中，那么就不需要填充了。显然FFTW并没有这样做。 - nneonneo

仅供参考，这种打包方式[..]在多维转换中不具有普适性。请参阅此FFTW文档的倒数第二段了解详情。 - Sveltely

Answer 1

1. If your input is already in a normal C++ 2D array, all you should need to do is typecast it:

   double twoDarray[10][10];
   double *oneDarrayPointer = (double *)twoDarray;
   

   If your input is 100 (like it is in the above example), your output array is going to be 51 complex numbers. The format of those numbers should be described by your library, but probably is an array of 102 doubles - 51 entries times 2 (real/imaginary parts).

   Edit: Confirmed - fftw_complex is defined as:

   typedef double fftw_complex[2];
   

   So they're just consecutive pairs of doubles representing the real and imaginary parts of a complex number.

2. If you don't want to do it in place, you don't have to pad anything - just allocate an appropriately sized output array. If you do need to do it in place, your input buffer has to have space for the 2 extra doubles vs the input size. Assuming the declarations above, you'd want something like:

   double *inPlaceFFTPointer = malloc(sizeof twoDarray + 2*sizeof(double));
   memcpy(inPlaceFFTPointer, oneDarrayPointer, sizeof twoDarray);
   

   I'm not sure if you'd need to make sure to have 0.0 in the last two entries or not, but that's easy enough to add.

- Carl Norum

---

你可以使用C++标准库中的std::complex，也可以使用C语言风格或上述typedef与FFTW。 - pyCthon

@pyCthon，是的。我认为它们在内存中基本上都是相同的。 - Carl Norum

所以它们只是表示复数的实部和虚部的连续双精度对。没错，但为什么只有51个？为什么不是100个？难道2D FFT的输出矩阵不与输入矩阵大小相同吗？ - tir38

从您发布的链接中可以看到：“在许多实际应用中，输入数据in[i]是纯实数，此时DFT输出满足“Hermitian”冗余：out[i]是out[n-i]的共轭。” 因此，如果需要的话，您只需要一半的输出就可以生成所有的输出。 - Carl Norum

我有点理解了。这篇文章帮助我理解了视觉对称性：“你可能会开始注意到有很多对称性。对于所有的实数（相对于虚数或复数），傅里叶变换关于原点是对称的，因此第一象限和第三象限相同，第二象限和第四象限相同。如果图像关于x轴对称（如余弦图像），则会出现4倍对称性。” http://www.cs.unm.edu/~brayer/vision/fourier.html - tir38

Answer 2

您可以查看FFTW3中的实际到实际变换，这正是您所要求的。 这些不需要填充，并且考虑到波数0和代表Nyquist频率的波数只有一个实部。 请在此处查看： FFTW3实际到实际变换

并查看内存中的布局： FFTW3实际到实际变换种类

- Chiel