Сложность двумерного дискретного преобразования Фурье

Question

У меня вопрос по поводу двумерного преобразования Фурье. В настоящее время я нахожусь в процессе понимания математики за этим, и есть кое-что, что я не понимаю. Насколько я понимаю, DFT имеет сложность O(N*N). Если я смотрю на следующий алгоритм:

Я не понимаю, как это работает. Мы собираемся сделать этот расчет для каждого пикселя в преобразованном изображении ?

пример

1. У нас есть изображение 2 * 2.
2. Для каждого пикселя на этом изображении мы собираемся сделать ДПФ F (x, y)
3. Я создам новое изображение, и каждый пиксель является величиной соответствующего комплексного значения

Это так работает или я что-то упустил? Потому что, как я вижу это сейчас, он имеет сложность O(N^4)

Answer 1

Уравнение означает «чтобы получить значение F в пикселях (u, v), выполнить оценку (формула справа)». Таким образом, чтобы получить все преобразованное изображение, оно оценивается для каждого пикселя в преобразованном изображении.

Чтобы вычислить ДПФ, используя формулу, вам нужно выполнить расчет O (1) для каждого входного значения для каждого выходного значения. (Существуют другие, более быстрые алгоритмы для некоторых видов данных.) В вашем случае 2D DFT алгоритм имеет сложность O ((M * N) ^ 2), потому что количество входных пикселей равно M * N, а также число Выходные пиксели также M * N.

edit : 2D DFT матрицы может быть вычислено в O (NM ^ 2 + MN ^ 2) путем преобразования строк и столбцов в отдельные шаги. Алгоритм здесь: http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node6.html