Pracuję z korelacją 2d dla technik przetwarzania obrazu (rozpoznawanie wzorów itp.). Zastanawiałem się, czy istnieje teoretyczne podejście do tego, jak powiedzieć, kiedy stosować mnożenie w przestrzeni częstotliwości zamiast korelacji w przestrzeni czasu. Dla rozmiarów 2 x częstotliwość jest oczywiście szybsza, ale co powiesz na małe, podstawowe rozmiary, takie jak np. 11?
Zakładam, że odbywa się to na konwencjonalnym procesorze, jednym rdzeniu, wykonującym jeden prosty wątek, bez wymyślnego sprzętu. Jeśli dzieje się coś więcej, prawdopodobnie można to wyjaśnić, dostosowując rozumowanie prostszego systemu. Niewiele więcej można powiedzieć bez konkretnego systemu do dyskusji lub całego podręcznika lub artykułu badawczego obejmującego szereg możliwości.
Nie martwiłbym się o moc dwóch rozmiarów. To nie ma znaczenia Algorytmy FFT z jednostkami motylkowymi i wszystkimi innymi, które istnieją dla współczynników 3 lub dowolnej małej liczby, nie tylko 2. Istnieją również sprytne algorytmy dla serii danych w podstawowej wielkości. Nie lubię cytować Wikipedii na ten temat ze względu na jego nietrwałość, ale zresztą:
istnieją FFT o złożoności O (N log N) dla wszystkich N, nawet dla pierwszej N
Implementacje FFT dla dowolnego N można znaleźć w bibliotece FFTW GPL .
Jedynym wiarygodnym sposobem w zakresie poważnej inżynierii jest budowanie i mierzenie, ale z pewnością możemy uzyskać pomysł z teorii, aby zobaczyć relacje między zmiennymi. Potrzebujemy oszacowań, ile operacji arytmetycznych jest zaangażowanych dla każdej metody.
Mnożenie jest nadal wolniejsze niż dodawanie na większości procesorów, nawet jeśli różnica znacznie się skurczyła przez lata, więc policzmy mnożenia. Księgowość również w przypadku dodawania wymaga nieco więcej myślenia i śledzenia rzeczy.
Prosty splot, faktycznie mnożenie i dodawanie za pomocą jądra splotu, powtarzanie dla każdego piksela wyjściowego, wymaga mnożenia W² · K², gdzie W jest liczbą pikseli wzdłuż jednej strony obrazu (zakładając kwadrat dla uproszczenia), a K jest rozmiarem jądra splotu, jako piksele wzdłuż jednej strony. Potrzeba mnożenia K², aby obliczyć jeden piksel wyjściowy przy użyciu jądra i tej samej wielkości obrazu wejściowego. Powtórz dla wszystkich pikseli wyjściowych, których liczba jest taka sama jak na obrazie wejściowym.
(N mults ) bezpośrednie = W² · K²
Aby wykonać zadanie w przestrzeni Fouriera, musimy przekształcić obraz Fouriera. Odbywa się to poprzez zastosowanie FFT do każdej kolumny osobno, a następnie do każdego wiersza. FFT dla N punktów danych zajmuje około 2N · log (N) mnożeń; chcemy, aby N było W, długością jednej kolumny lub wiersza. Wszystkie logarytmy tutaj są podstawą drugą.
Istnieją W wiersze i W kolumny, więc po wykonaniu wszystkich FFT, wykonaliśmy mnożenia 2W · (2W · log (W)). Podwój to, ponieważ po pomnożeniu przez transformację Fouriera jądra, musimy odwrócić Fouriera danych, aby wrócić do rozsądnego obrazu. To 8W² · log (W). Oczywiście należy wykonać mnożenie przez transformację Fouriera jądra, kolejne multiplikacje W². (Wykonane raz, nie raz na piksel wyjściowy, wiersz lub cokolwiek innego.) Są to złożone multiplikacje, więc to prawdziwe multiplikacje 4W².
Tak więc, chyba że goofed w górę (i prawdopodobnie zrobiłem) mamy
(N mults ) Fourier = 4W² · (2 · log (W) + 1)
Kiedy chcemy robić rzeczy bezpośrednio? Gdy K jest wystarczająco małe, aby W² · K² był mniejszy niż 4W² · (2 · log (W) + 1). Wspólny czynnik W² można łatwo wyliczyć. Prawdopodobnie możemy upuścić „+1”, ponieważ mamy do czynienia z wyidealizowanymi szacunkami. +1 najprawdopodobniej gubi się w błędach w stosunku do rzeczywistych implementacji, z powodu nie liczenia dodatków, narzutów pętli i tak dalej. To pozostawia:
K² < 8·log(W)
Jest to przybliżony warunek wyboru podejścia bezpośredniego zamiast podejścia do przestrzeni częstotliwości.
Zauważ, że korelacja dwóch obrazów tej samej wielkości jest jak splot z jądrem o rozmiarze K = W. Przestrzeń Fouriera jest zawsze na to sposobem.
Można to udoskonalić i argumentować, aby uwzględnić koszty ogólne, potokowanie opcodów, zmiennoprzecinkowe vs. stały punkt i wyrzucenie przez okno za pomocą GPGPU i specjalistycznego sprzętu.