2 차원 이산 푸리에 변환의 복잡도

Question

2D 푸리에 변환에 관한 질문이 있습니다. 나는 현재 이것의 뒤에있는 수학을 이해하는 과정에 있으며, 내가 알지 못하는 것이있다. 내가 아는 한, DFT는 O(N*N)의 복잡성을 가지고 있습니다. 나는 다음과 같은 알고리즘을 보면 :

나는 그것이 어떻게 작동하는지 이해하지 않습니다. 우리는 변환 된 모든 픽셀에 대해이 계산을 할 것인가 이미지?

예를

1. 우리는 2 * 2의 이미지를 가지고있다. 우리는 DFT F를 할거야이 이미지 (X, Y)의 각 픽셀에 대한
3. 나는 새로운 이미지를 만들 수 있습니다, 각각의 픽셀이 corrosponding 복잡한 값의 크기입니다

이것이 작동하는 방식입니까, 아니면 뭔가 빠졌는가요? 왜냐하면 지금 내가 본 방식이므로 복잡성이 있습니다. O(N^4)

Answer 1

방정식은 "픽셀 (u, v)에서 F 값을 얻고, (오른쪽에서 수식)"을 의미합니다. 따라서 전체 변환 이미지를 얻으려면 변환 된 이미지의 모든 픽셀에 대해 평가됩니다.

수식을 사용하여 DFT를 계산하려면 모든 출력 값에 대한 모든 입력 값에 대해 O (1) 계산을 수행해야합니다. 2D DFT의 경우, 알고리즘은 입력 픽셀의 수가 M * N이고 (* (N * N)^2), 복잡도 O 출력 픽셀도 M * N입니다.

편집 : 2D 행렬 DFT는 행과 열을 별도의 단계로 변환하여 O (NM^2 + MN^2)에서 계산할 수 있습니다. 알고리즘은 다음과 같습니다. http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node6.html