二维离散傅里叶变换的复杂性
我有一个关于二维傅里叶变换的问题。我目前正在理解这背后的数学，但有些东西我不明白。就我而言，DFT 的复杂度为 O(N*N)。如果我查看以下算法：
我不明白它是如何工作的。我们要对转换后的图像中的每个像素进行这种计算吗？
示例
- 我们有一张 2*2 的图像。
- 对于该图像中的每个像素，我们将进行 DFT F(x,y)
- 我将创建一个新图像，每个像素是对应复数值的大小
是这样的吗有效还是我错过了什么？因为以我现在的方式来看，它的复杂度为O(N^4)
I have a question regarding a 2D Fourier transformation. I'm currently in the progress of understandig the maths behind this, and there's something I dont onderstand. As far as I'm concerned, the DFT has a complexity of O(N*N). If I look at the following algorithm:
I don't understand how it works. Are we going to do this caluculation for every pixel in the tranformed image?
example
- We have an image of 2*2.
- For each pixel in this image we're going to do the DFT F(x,y)
- I'll create a new image, and each pixel is the magnitude of the corrosponding complex value
Is this how it works or am I missing something? Because the way I see it now, it has a complexity of O(N^4)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
该方程的意思是“要获得像素 (u, v) 处的 F 值，请评估（右侧的公式）”。因此，为了获得整个变换图像，需要对变换图像中的每个像素进行评估。
要使用公式计算 DFT，您需要对每个输出值的每个输入值进行 O(1) 计算。 （对于某些类型的数据，还有其他更快的算法。）在 2D DFT 情况下，该算法的复杂度为 O((M*N)^2)，因为输入像素的数量为 M*N 并且输出像素也是M*N。
编辑：通过在单独的步骤中变换行和列，可以在 O(NM^2 + MN^2) 中计算 2D 矩阵 DFT。该算法在这里：http://fourier.eng.hmc.edu/ e101/lectures/Image_Processing/node6.html
The equation means "to get the value of F at pixel (u, v), evaluate (the formula on the right-hand-side)." So, to get the entire transformed image, it's evaluated for every pixel in the transformed image.
To compute a DFT, using the formula, you need to do an O(1) calculation for every input value for every output value. (There are other, faster algorithms for some kinds of data.) In your 2D DFT case, the algorithm has complexity O((M*N)^2), because the number of input pixels is M*N and and the number of output pixels is also M*N.
edit: A 2D matrix DFT can be calculated in O(NM^2 + MN^2) by transforming the rows and columns in separate steps. The algorithm is here: http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node6.html