使用苹果加速框架选择真实与复杂的二维FFT

Question

有谁能建议正确的FFT（实数或复数）？我在这里查看了此处，但仍有疑问。

我想做图像相关来确定主图像中子图像的位置。我理解FFT和iFFTs的基础知识。

计划如下：

1. 对主图像进行FFT。512x512
2. 取子图像的共轭。
3. 对子图像执行FFT。30x30但用零填充到512x512
4. 将两个结果矩阵进行复合乘法
5. 在结果上执行iFFT
6. 即使结果应该是（大部分）实数，也要取得结果矩阵的幅值
7. 寻找最大值，应该对应最大相关性。

我无法获得我预期的结果。

如果使用实2d fft（vDSP_fft2dzrip），则结果以打包格式呈现，这使得难以使用vDSP_zvmul将两个结果矩阵相乘。

如果使用复杂fft（vDSP_fft2dzip），我根本没有获得任何相关性。

苹果示例和大多数音频示例除了执行反演之外，不对正向FFT的结果进行任何操作。

有人能帮助我开始进行图像相关吗？第一个问题...我能使用复杂FFT并避免打包格式吗？

- Bill Johnson

Answer 1

唯一的区别在于真实和复杂FFT之间，即通过使用巧妙的打包方案将2 ^ n实际FFT转换为2 ^（n-1）复杂FFT，实际FFT可以略微更有效率。结果在两种情况下应该是相同的。因此，如果我是你，我会选择复杂FFT以简化操作，至少在你确保所有工作正常之前这样做。

你有没有看过vImageConvolve_ARGB8888？它似乎可以用更少的精力做你想做的事情 :)

- Tark

---

我正在尝试在不确定的环境中识别街道标志，当我尝试使用vImageConvolve时，图像的白色区域会使目标图像过载。我不确定如何规范化卷积，因此决定尝试频域方法。 - Bill Johnson

vImageConvolve函数肯定会使用频域实现，这是实现非平凡图像算法的唯一实用方式。也许您可以尝试使用浮点变量或先对图像进行缩放？ - Tark

vImageConvolve的文档说明它执行Kernel(x,y) * Pixel(x,y) / M x N的求和。我相信它是在空间模式下进行卷积的。它将目标滑动到大图像上，并为每个位置计算平均值。白色区域覆盖了细节区域。我尝试在两个图像上使用Sobel边缘检测，但树木有太多的边缘，也无法正常工作。 - Bill Johnson

无论算法是在空间域还是频率域执行，结果几乎完全相同。唯一的区别是到达目的地所需的时间长度。 - Tark

原问题已经得到解答。如果您不担心速度，使用“真实”FFT没有优势。 - Bill Johnson

@BillJohnson 我尝试了vImageConvolve。但是对于大图像来说速度太慢了，而且运行时间为O(n^2)。基于FFT的实现可能更快，时间复杂度为O(nlogn)。 - kiranpradeep