Быстрое дискретное двумерное преобразование фурье

← →
Norsk © (2005-10-27 13:00) [0]

Необходим алгоритм вычесления БДДПФ с целью получения фазового спектра изображения, а также алгоритм обратного БДДПФ. заранее спасибо

← →
MBo © (2005-10-27 13:31) [1]

Двумерное преобразование Фурье эквивалентно последовательному применению одномерного Фурье по строкам массива, затем по столбцам (или наоборот, без разницы).

← →
Digitman © (2005-10-27 13:47) [2]

см. [1] и начни просто с прямого/обратного БДДПФ для любой секвенции

надеюсь, теория и формулы тебе известны.

← →
Jeer © (2005-10-27 14:06) [3]

Digitman © (27.10.05 13:47) [2]

> надеюсь,

> вычесления

"Это - вряд ли". (С) Сухов.

← →
Digitman © (2005-10-27 15:44) [4]

ну уж это, Серега, "понятно что лошадь, но только с рогами")

← →
Digitman © (2005-10-27 15:48) [5]

> Jeer © (27.10.05 14:06) [3]

про лошадь с рогами, про которую "понятно", копирайт не помню, но тоже имеется) .. засим извиняюсь про отсутствие копирайта)

← →
vrem (2005-10-28 19:52) [6]

>одномерного Фурье по строкам массива, затем по столбцам
вопрос знатокам - кучи реализаций есть, какая быстрее?

← →
Jeer © (2005-10-31 10:44) [7]

vrem (28.10.05 19:52) [6]

http://www.fftw.org - очень даже.
На некоторых типах данных и размерностях превосходит IPP
http://www.fftw.org/speed/p4-2.8GHz/

← →
WondeRu © (2005-10-31 13:37) [8]

Jeer © (31.10.05 10:44) [7]
http://www.fftw.org - очень даже.

у Вас есть примеры на Delphi по использованию сего творения?

← →
Jeer © (2005-10-31 15:09) [9]

Пользовался.
На сайте все есть.

{--------------------------------------------------------------}
{ Delphi interface to the FFTW library -- FFTW Version 3.0.1. }
{ Note that this interface is incomplete. Additional function }
{ interface entries may be added in an anologous manner, see }
{ fftw for more details. }
{ }
{ Last modified 22/DEC/03 }
{ Written by Mark G. Beckett (g.beckett@epcc.ed.ac.uk }
{--------------------------------------------------------------}

unit fftw_interface;

interface
{EPCC (MGB) - Note that the FFTW memory allocation routines can not be used
for data arrays, because the DLL is allocated a separate heap that is not
accessible from the Delphi runtime environment.}
function fftwf_malloc(n : Integer) : Pointer; cdecl;

procedure fftwf_free(p : Pointer); cdecl;

function fftwf_plan_dft_1d(n : Integer; inData : PSingle;
outData : PSingle; sign : Integer; flags : Longword) : Pointer; cdecl;

function fftwf_plan_dft_r2c_1d(n : Integer;
inData : PSingle; outData : PSingle; flags : Longword) : Pointer; cdecl;

function fftwf_plan_dft_r2c_3d(nx : Integer; ny : Integer; nz : Integer;
inData : PSingle; outData : PSingle;
flags : Longword) : Pointer; cdecl;

function fftwf_plan_dft_c2r_3d(nx : Integer; ny : Integer; nz : Integer;
inData : PSingle; outData : PSingle;
flags : Longword) : Pointer; cdecl;

function fftwf_plan_dft_c2r_1d(n : Integer;
inData : PSingle; outData : PSingle; flags : Longword) : Pointer; cdecl;

procedure fftwf_destroy_plan(plan : Pointer); cdecl;

procedure fftwf_execute(plan : Pointer); cdecl;

const
{EPCC (MGB) - FFTW documented constants, taken from "api/fftw3.h". Comments
to the right of the definitions are transcribed from the original header
file.}

FFTW_FORWARD = -1;
FFTW_BACKWARD = 1;

FFTW_MEASURE = 0;
FFTW_DESTROY_INPUT = 1; {1U << 0}
FFTW_UNALIGNED = 2; {1U << 1}
FFTW_CONSERVE_MEMORY = 4; {1U << 2}
FFTW_EXHAUSTIVE = 8; {1U << 3} {NO_EXHAUSTIVE is default }
FFTW_PRESERVE_INPUT = 16; {1U << 4} {cancels FFTW_DESTROY_INPUT}
FFTW_PATIENT = 32; {1U << 5} {IMPATIENT is default }
FFTW_ESTIMATE = 64; {1U << 6}

{FFTW undocumented constants have not been defined in this implementation.
They are not required for typical usage of the library.}

implementation

uses
SysUtils;
function fftwf_malloc(n : Integer): Pointer;
cdecl; external "fftw3.dll";
procedure fftwf_free(p : Pointer);
cdecl; external "fftw3.dll";
{Commented prototypes are taken from FFTW library. }

{fftw_plan fftwf_plan_dft_1d)(int n, C *in, C *out, int sign, unsigned flags)}
function fftwf_plan_dft_1d(n : Integer; inData : PSingle;
outData : PSingle; sign : Integer; flags : Longword) : Pointer;
cdecl; external "fftw3.dll";

{ fftw_plan fftwf_plan_dft_r2c_1d(int n, float *in, \
fftw_complex *out, unsigned flags);}
function fftwf_plan_dft_r2c_1d(n : Integer;
inData : PSingle; outData : PSingle; flags : Longword) : Pointer;
cdecl; external "fftw3.dll";

{fftw_plan fftwf_plan_dft_r2c_3d(int nx, int ny, int nz, R *in, C *out,
unsigned flags)}
function fftwf_plan_dft_r2c_3d(nx : Integer; ny : Integer; nz : Integer;
inData : PSingle; outData : PSingle; flags : Longword) : Pointer;
cdecl; external "fftw3.dll";

{fftw_plan fftwf_plan_dft_c2r_1d(int n, C *in, R *out, unsigned flags)}
function fftwf_plan_dft_c2r_1d(n : Integer;
inData : PSingle; outData : PSingle; flags : Longword) : Pointer;
cdecl; external "fftw3.dll";

{fftw_plan fftwf_plan_dft_c2r_3d(int nx, int ny, int nz,
C *in, R *out, unsigned flags)}
function fftwf_plan_dft_c2r_3d(nx : Integer; ny : Integer; nz : Integer;
inData : PSingle; outData : PSingle; flags : Longword) : Pointer;
cdecl; external "fftw3.dll";

{void fftwf_destroy_plan(fftw_plan p)}
procedure fftwf_destroy_plan(plan : Pointer);
cdecl; external "fftw3.dll";

{void fftwf_execute(const fftw_plan p)}
procedure fftwf_execute(plan : Pointer);
cdecl; external "fftw3.dll";

end.

← →
WondeRu © (2005-10-31 18:06) [10]

видел это, но есть ли реальный пример... что куда запихивать? какие размерности массивов и т.п.?

← →
PAVIA © (2005-10-31 19:08) [11]

Что такое ряд Фурье? Что такое Быстрые преоброзования Фурье?
Насколько я знаю Ряд Фурье это разложение интеграла в ряд косинусов и синусов. То БПФ я понимаю это разложение в ряд и обратно преоброзование,быстрым способом. Я знаю что эти преоброзования применяеться во многих облостях. Так же я узнал, что в ряд фурье можно разложить статистические данные, но как это делыеться я не знаю. Также я узнала, что есть преоброзования X... которые в два раза бычтрее чем ФФТ за счет того, что не используют комплексные числа.
Вопрос:
Как применяют БПФ? Можети привести пример и объеснить как и почему делают так. Для примера используя БПФ для удоления помех с картинки или любой другой.

← →
Jeer © (2005-11-01 12:18) [12]

PAVIA © (31.10.05 19:08) [11]

"преоброзования", "применяеться", "делыеться", "удоления"

Быстро в школу.
Учить русский, для начала.

"Так же я узнал, что в ряд.."
"Также я узнала, что есть преоброзования X..."

И определись с полом, наконец.

← →
vrem (2005-11-01 18:07) [13]

PAVIA ©
Поддерживаю [12] Jeer, читать не очень, но не быстро в школу, а печатать больше - и скорость печати поднимется и ошибок меньше станет.

что касается fft - это очень полезная штука. Суть её, как я понимаю - на входе имеем музыку, шум - любой сигнал, а на выходе - точно знаем какие частоты состовляют исследуемый сигнал. Их можно увеличить или уменьшить и обратно превратить в сигнал = получится эквалайзер хоть сколько полосный, а можно вырезать из сигнала шум - sound forge имеет плагин такой.

← →
Jeer © (2005-11-01 18:50) [14]

vrem (01.11.05 18:07) [13]

Тоже, в школу захотелось ? :))

> какие частоты состовляют

← →
PAVIA © (2005-11-01 20:56) [15]

Извиняюсь из-за ошибок, голова болела после пяти пар. Но вы все-таки не ответили на вопрос. Раз уж поросяти исправляю ошибки.
Что такое ряд Фурье? Что такое Быстрые Преобразования Фурье?
Насколько я знаю Ряд Фурье это разложение интеграла в ряд косинусов и синусов. То БПФ я понимаю это разложение в ряд и обратно преобразование, быстрым способом. Я знаю, что эти преобразования применяется во многих областях. Так же я узнал, что в ряд Фурье можно разложить статистические данные, но как это делается, я не знаю. Также я узнал, что есть преобразования X…, которые в два раза быстрее, чем БПФ за счет того, что не используют комплексные числа.
Вопрос:
Как применяют БПФ? Можете привести пример и объяснить, как и почему делают так. На примере, используя БПФ для удаления помех с картинки или любой другой.

← →
Digitman © (2005-11-02 09:19) [16]

> PAVIA © (01.11.05 20:56) [15]

http://algolist.manual.ru/maths/fft.php

← →
Norsk © (2005-11-02 09:29) [17]

Преобразование Фурье переводит сигнал из временной (или пространственной) в частотную область. В тупую по формулам его обычно не вычисляют а используют матричное представление. Для вычисления ПФ сложность оценивают как N^4 (N - размер квадратной матрицы, и обычно N=8). БПФ - основано на том что элементы матрицы ПФ повторяються, а такдже на том что все вычисления делят на отдельные потоки (и сложность сокращаеться значительно).
Я не нашел Алгоритмм БДДПФ, и пришлось исполььзовать простой алгоритм (матричный, с компл числами). Вроде не особо тормозит (размер матриц у меня 100 на 100, т.к. требуется спектр всего изображения, а не отдельных блоков)

← →
MBo © (2005-11-02 11:35) [18]

>WondeRu © (31.10.05 18:06) [10]
>видел это, но есть ли реальный пример...

procedure TForm1.Button1Click(Sender: TObject); var aIn,aOut: array of Single; N,i:Integer; plan:Pointer; begin N:=256; SetLength(aIn,2*N); SetLength(aOut,2*N); for i:=0 to N -1 do begin aIn[2*i]:=3*sin(i)+cos(i/3); aIn[2*i+1]:=0; Series1.AddXY(i,aIn[2*i]); end; plan := fftwf_plan_dft_1d(N, @aIn[0], @aOut[0], FFTW_FORWARD, FFTW_ESTIMATE); fftwf_execute(plan); fftwf_destroy_plan(plan); for i:=0 to N - 1 do Series2.AddXY(i, Hypot(aOut[2*i],aOut[2*i+1])); end;

← →
WondeRu © (2005-11-02 17:33) [19]

MBo © (02.11.05 11:35) [18]
Спасибо!

>WondeRu
в fftw.pas описаны далеко не все функции, поэтому стоит опираться на документацию. Двумерные я не пробовал - там надо изучить, как упаковываются данные.

MBo © (02.11.05 17:42) [20]
как упаковываются данные.
именно с этим у меня была и непонятка!
Двумерное мне понадобится, поэтому как разберусь сразу дам знать!

Пожалуйста, помогите с двумерным БПФ.
Ничё не выходит: добавил функцию 2D fft в fft_interface, но при запросе функции, почему-то, выдаёт ошибку классов.
Если можно, приведите готовый кусок кода.

Уважаемые.

Что лучше использовать для разложения сигнала со звуковой карты в частотный вид? Поправьте если что не так.

← →
misha_gr (2006-02-06 16:35) [24]

Вопрос к WondeRu.
Извиняюсь, что бросаю сюда, но в анкете мейл не указан. Спрашивал у Анонимщика ссылку на его статью, он отослал к Вам )))

misha_gr (06.02.06 16:35) [24]
ссылки нет, ибо статья не закончена...

← →
Kaban (2006-02-15 11:22) [26]

а саму библиотеку "fftw3.dll" где взять, там можно скачать файлы
libfftw3-3.dll, libfftw3f-3.dll, libfftw3l-3.dll
но названия функций в них отличаются
от используемых в файле fftw_interface
это она и есть?

>а саму библиотеку "fftw3.dll" где взять, там можно скачать файлы

Сейчас там для Windows лежит архив с DLL версии 3.1
Я раньше качал fftw-3.0.1BC.zip - исходники и fftw-3.0.1-w32-pl1.zip - DLL-ки - это там тоже есть в разделе Older Versions
fftw_interface.pas относится к версии 3.01, но он все равно неполный, так что при использовании 3.1, наверно, лучше перевести на паскаль актуальный fftw3.h

Быстрое дискретное двумерное преобразование фурье Найти похожие ветки