Как выполнить FFT2D (быстрое преобразование Фурье 2D) R, G, B цветовой компонент

Question

Я новичок в области быстрого преобразования Фурье (БПФ) и не имею большого представления о том, как он рассчитывается в языке программирования, таком как C++. Вот метод FFT2D

void FFT2D(Complex<double> *f, Complex<double> *F, int width, int height);
It takes an input image f of size width * height and output the transformed 
coefficients into F.

Подсказки: пиксели изображения хранятся в виде трех отдельных цветовых плоскостей изображения (R, G, B), каждая из которых представлена ​​одномерным массивом комплексных чисел. Предположим, что изображение имеет размер W ширины и высоты H, тогда значения цветовой составляющей (R, G и B) пикселей в местоположении изображения (m, n) можно найти как R[m + n * W], G(m + n * W) и B[m + n * W], где R, G, B - три массива комплексных чисел. 1D-массив для преобразованных коэффициентов также представлен таким же образом.

Что мне нужно для реализации обработки только для одного компонента цвета, и шаблон программирования будет обрабатывать R, G, B отдельно на основе реализованных функций. Шаблон также заполнит изображение нулями, чтобы каждое входное изображение имело размер 2 м * 2n.

If I called from another class, I have to pass R, G, B separately
Suppose: 
Complex<double> *R = new Complex<double>[width * height];
Let, width = 4096 and height 4096
FFT2D(R, output F, width, height) for compute “R” color component;
FFT2D(G, output F, width, height) for compute “G” color component;
FFT2D(B, output F, width, height) for compute “B” color component;

We have template of calculated FFT1D function:
void FFT1D(Complex<double> *fx, Complex<double> *Fu, int twoK, int stride)
Hint: it outputs the frequency coefficients in the array Fu.

FFT1D вызывает изнутри функцию FFT2D. Я нашел несколько различных типов кода в C, C++, Java и C # FFT2D. Большинство из них реализованы с использованием 2D-структуры массива; они приписывают вещественную и мнимую части структуре двумерного массива в цикле строк и столбцов. Тем не менее, в моем случае это 1D структура массива компонента цвета.

Давайте сделаем некоторый код, и это внутри функции FFT2D:

Complex<double> *outPutMap = new Complex<double>[width * height];
 for (int i = 0; i < height; i++){
 #  for(int j = 0; j < width; j++){
 #     outPutMap[i + j * width] = f[i + j * width];
 #      I don’t understand how to implement in here for color component and how 
 #      it assign a value for real and imaginary part
 #   }
  }

Перед вызовом FFTID также требовалось вычислить значение twoK, как в книге, M = 2K

Если у вас есть идеи или рекомендации, пожалуйста, дайте мне знать.

Спасибо

С уважением Ичиро

Answer 1

Я бы посоветовал вам приобрести такую ​​книгу, как "Численные рецепты" [1].

http://www.amazon.com/Numerical-Recipes-Art-Scientific-Computing/dp/0521750334

БПФ, правило Симпсонов, алгоритм Фурье должны быть там. Я читал от автора по имени Раджарам.. это было в C.