В настоящее время я реализую двухмерный БПФ для реальных входных данных с использованием opencl (точнее, быструю двумерную свертку с использованием БПФ, поэтому мне нужно только то, что ведет себя аналогично, чтобы применить свертку). 2D FFT реализуется с использованием 1D FFT на строках, а затем 1D FFT на столбцах.Эффективный 2D БПФ на реальных входных данных?
Чтобы сделать это более эффективным, я пытаюсь использовать симметрии БПФ с реальным входом, чтобы иметь возможность вычислять меньшие БПФ. Я обнаружил, что я могу объединить две строки в одну, используя первый как реальный компонент, второй как мнимый компонент, сделать первый 1D FFT в результирующей строке, а затем использовать свойства симметрии для построения результатов 1D БПФ индивидуума строки из этого. Так что я делаю в основном следующее:
Позвольте f и g быть строками из матрицы.
- Построить
x = f + i * g - Transform, чтобы получить
F(x) = F(f) + i * F(g) - Использование симметрий для извлечения
F(f)иF(g)изF(x)
я не могу, однако только входные результаты непосредственно в 2-1D FFT, потому что в этом случае я бы не преобразовал всю матрицу, а вместо нее - две подматрицы. Однако извлечение данных между преобразованиями означает либо хранение большего количества данных (n/2+1 записей, необходимых для выражения результата 1D БПФ на реальном вводе), либо объединение элементов по индексу 0 и индекс n/2 в один элемент (объединение с использованием того же трюка, поскольку оба номера гарантированно являются реальными) и используют один и тот же объем хранилища, но должны сделать spcial case для этого в моей свертке.
Поскольку я стараюсь как можно больше использовать буферы (из-за ограниченного объема оперативной памяти, доступного на gpu), использование большего количества хранилища не является хорошим решением. Кроме того, мои алгоритмы не оборудованы для работы с матрицами, которые не имеют мощности 2/кратных 16 (варьируется от ядра к ядру). Я бы предпочел не вводить специальные случаи, так как это сделало бы мои ядра более сложными, ухудшая эффективность (у меня уже есть проблемы с минимизацией количества регистров, используемого каждым ядром).
Итак, мой вопрос в том, есть ли элегантный подход к этой проблеме, то есть тот, который будет работать без использования большего количества памяти или особых случаев для определенных элементов?
В идеале, я хотел бы иметь возможность делать весь БПФ без разделения моих комбинированных данных в середине БПФ, но я не уверен, что это возможно.
Будет ли это в мягкой обложке в ближайшее время? –
Вам действительно нужно сделать сложный БПФ? Возможно нет. – phkahler
Хороший вопрос, у меня была почти такая же проблема, делая fft для обнаружения стеганографии. но я не понял тогда ... что stackoverflow существует;/ – dfens