Wiem więc, że splot za pomocą FFT ma mniejszą złożoność obliczeniową niż splot w przestrzeni rzeczywistej. Ale jakie są wady splotu FFT?Jakie są wady splotu przez FFT w porównaniu do splotu w przestrzeni rzeczywistej?
Czy rozmiar jądra zawsze musi odpowiadać rozmiarowi obrazu, czy istnieją funkcje, które się tym zajmują, na przykład w pakietach pythons numpy i scipy? A co z efektami antyaliasingu?
FFT zwoje są oparte na convolution theorem, który stanowi, że givem dwie funkcje f i g, jeśli Fd() i Fi() oznaczają bezpośrednie i odwrotnej transformaty Fouriera i * i . splot i mnożenia, a następnie:
f*g = Fi(Fd(d).Fd(g))
Aby zastosować to do sygnału f i jądra g, istnieje kilka rzeczy, którymi należy się zająć:
f i g muszą być tego samego rozmiaru, aby krok mnożenia był możliwy, więc konieczne jest zerowanie jądra.Jeśli sygnał i jądra rozmiary są f_l i g_l, robiąc prosty splot w dziedzinie czasu wymaga g_l * (f_l - g_l + 1) mnożenia i (g_l - 1) * (f_l - g_l + 1) uzupełnień.
W przypadku podejścia FFT należy wykonać 3 transformaty FFT o rozmiarze co najmniej f_l + g_l, a także zmultiplikacje f_l + g_l.
Dla dużych rozmiarów zarówno f, jak i g, FFT jest wyraźnie lepszy ze złożonością n*log(n). W przypadku małych jąder bezpośrednie podejście może być szybsze.
scipy.signal ma zarówno metody, które można odtwarzać w trybie convolve i . I fftconvolve obsługuje wszystkie wyściółki opisane powyżej dla Ciebie.
"Większość (wszystkich?) Pakietów FFT działa tylko w przypadku rozmiarów, które nie mają dużych czynników pierwszeństwa." : dokładne, że mówisz tylko o prędkości, samo obliczenie nie stanowi problemu (przynajmniej w przypadku numpy i scipy). –
Tak, rzeczywiście, dodałem notatkę w mojej odpowiedzi. Typowy algorytm FFT rozkłada DFT o rozmiarze "N = a * b" na "a" FFT o rozmiarze rekurencyjnie "b". Jeśli 'N' jest liczbą pierwszą, potrzebujesz [bardziej wyrafinowanych algorytmów] (http://en.wikipedia.org/wiki/Rader%27s_FFT_algorithm), aby przyspieszyć działanie. Na moim komputerze: '% timeit numpy.fft.fft (np.random.rand (1024)); 10000 pętli, najlepiej 3: 36,2 na pętlę; % timeit numpy.fft.fft (np.random.rand (1021)); 100 pętli, najlepiej 3: 2,15 ms na pętlę', spowolnienie x100, co wydaje się wskazywać, że DFT o rozmiarze pierwotnym jest obliczany bezpośrednio, bez przyspieszenia. – Jaime
Wygląda na to, że FFTW ma przyspieszenie: "Rozmiary z małymi współczynnikami pierwszymi są najlepsze, ale FFTW używa algorytmów O (N log N), nawet w przypadku wielkości początkowych.". Obsługuje także proces wieloprocesowy. Jest użyteczny z python z pyfftw. –
Podczas gdy szybkie splatanie ma lepszą złożoność "wielkiej litery" niż splot z postaci bezpośredniej; jest kilka wad lub zastrzeżeń. Zrobiłem trochę myślenia o tym temacie dla an article napisałem jakiś czas temu.
Lepsza złożoność "wielkiej litery" nie zawsze jest lepsza. Bezpośrednia forma splotu może być szybsza niż użycie FFT dla filtrów mniejszych niż pewien rozmiar. Dokładny rozmiar zależy od używanej platformy i implementacji. Punkt podziału jest zwykle w zakresie 10-40.
Opóźnienie. Szybkie splatanie jest z natury algorytmem blokowym.Kolejkowanie setek lub tysięcy próbek naraz przed ich transformacją może być niedopuszczalne w przypadku niektórych aplikacji działających w czasie rzeczywistym.
Złożoność realizacji. Forma bezpośrednia jest prostsza pod względem pamięci, przestrzeni kodu i teoretycznego tła pisarza/opiekuna.
Na platformie DSP o stałym punkcie (nie jest to procesor ogólnego przeznaczenia): ograniczone rozważania dotyczące rozmiaru słowa FFT o ustalonej długości powodują, że duże FFT o stałej długości są prawie bezużyteczne. Na drugim końcu spektrum wielkości, chipy te mają wyspecjalizowane struktury MAC, które są dobrze zaprojektowane do wykonywania bezpośrednich obliczeń FIR, zwiększając zakres, w którym te O (N^2) bezpośrednia forma jest szybsza niż O (NlogN). Czynniki te mają tendencję do tworzenia ograniczonej "słodkiej plamy", w której FFT o ustalonej długości są przydatne do Szybkiej Konwolucji.
Należy zauważyć, że splot w dziedzinie częstotliwości jest bardziej skuteczny, gdy jądro przekroczy pewien rozmiar. W przypadku stosunkowo małych ziaren bezpośrednie splatanie jest bardziej wydajne. –