Szybkie algorytmy dla sygnałów wielowymiarowych

Podobnie jak w przypadku przetwarzania sygnału 1-D Digital w przypadku przetwarzania sygnału wielowymiarowego mamy Wydajne algorytmy. Wydajność algorytmu można ocenić na podstawie ilości zasobów obliczeniowych potrzebnych do obliczenia wyniku lub ilości będącej przedmiotem zainteresowania. Na tej stronie wyjaśniono dwa bardzo wydajne algorytmy dla sygnałów wielowymiarowych. Dla uproszczenia i opisu wyjaśniono to dla sygnałów 2-D. Jednak ta sama teoria dotyczy sygnałów MD. Wspomniano również o dokładnych oszczędnościach obliczeniowych dla każdego algorytmu.

Motywacja i zastosowania

W przypadku systemów cyfrowych do opisu relacji wejście-wyjście można użyć wyrażeń matematycznych, a do realizacji tej zależności można użyć algorytmu. Podobnie można opracować algorytmy do implementacji różnych transformacji, takich jak filtr cyfrowy , transformata Fouriera , histogram , ulepszenia obrazu itp. Bezpośrednia implementacja tych relacji wejście-wyjście i transformacji niekoniecznie jest najskuteczniejszym sposobem ich implementacji.

Kiedy ludzie zaczęli obliczać takie wyniki na podstawie danych wejściowych poprzez bezpośrednią implementację, zaczęli szukać bardziej wydajnych sposobów. Ta strona wiki ma na celu zaprezentowanie takich wydajnych i szybkich algorytmów dla wielowymiarowych sygnałów i systemów. Sygnał wielowymiarowy (MD) można modelować jako funkcję M zmiennych niezależnych, gdzie M jest większe lub równe 2. Sygnały te można podzielić na ciągłe, dyskretne lub mieszane. Ciągły sygnał można modelować jako funkcję zmiennych niezależnych, które wahają się w kontinuum wartości, na przykład – fala dźwiękowa podróżująca w przestrzeni, trójwymiarowe fale przestrzenne mierzone w różnym czasie. Z drugiej strony sygnał dyskretny można modelować jako funkcję zdefiniowaną tylko na zbiorze punktów, takim jak zbiór liczb całkowitych. Obraz jest najprostszym przykładem dwuwymiarowego sygnału domeny dyskretnej, który ma charakter przestrzenny.

W kontekście szybkich algorytmów rozważ poniższy przykład:

Musimy obliczyć A, które jest podane przez

A = αγ + αδ + βγ + βδ gdzie α,β,γ i δ są zmiennymi zespolonymi.

Aby obliczyć A, potrzebujemy 4 zespolonych mnożeń i 3 zespolonych dodań. Powyższe równanie można zapisać w uproszczonej postaci jako

ZA = (α + β) (γ + δ)

Ta forma wymaga tylko 1 złożonego mnożenia i 2 złożonych dodań.

Zatem drugi sposób obliczania A jest znacznie wydajniejszy i szybszy w porównaniu z pierwszym sposobem obliczania A. To jest motywacja do ewolucji szybkich algorytmów w dziedzinie cyfrowego przetwarzania sygnałów. W rezultacie wiele rzeczywistych aplikacji wykorzystuje te wydajne algorytmy do szybkich obliczeń.

Opis problemu i podstawy

Najprostszą formą reprezentacji systemu Linear Shift Invariant (LSI) jest jego odpowiedź impulsowa. Wyjście takiego systemu domeny dyskretnej LSI jest określone przez splot jego sygnału wejściowego i odpowiedzi impulsowej systemu. Jest to matematycznie przedstawione w następujący sposób:

${\ Displaystyle y \left(n_{1},n_{2}\right)=\sum _{l_{1}=-\infty }^{+\infty }\sum _{l_{2}=\infty }^{+ \infty }x(l_{1},l_{2})h(n_{1}-l_{1},n_{2}-l_{2})}$

gdzie jest odpowiedzią impulsową systemu. ${\ Displaystyle h (n_ {1}, n_ {2})}$

Zgodnie z powyższym równaniem, aby uzyskać wartość wyjściową w określonym punkcie ( powiedzmy ${\ Displaystyle y (0,0)}$ ) musimy pomnożyć kilka wartości wejściowych ${\ displaystyle x (l_ {1}, l_ {2})}$ i odpowiedź impulsowa ${\ Displaystyle h (-l_ {1}, -l_ {2})}$ . Oczywiście zależy to od regionu wsparcia wejścia, jak również odpowiedzi impulsowej. Kluczową kwestią, na którą należy zwrócić uwagę, jest to, że musimy wykonać tak wiele złożonych mnożeń i dodawań, aby uzyskać 1 wartość wyjściową.

Zakładając, że dwuwymiarowy sygnał wejściowy ma długość, a odpowiedź impulsowa systemu ma długość, musimy wykonać $} displaystyle M^{2}N^{2}}$$N$$\ Displaystyle N \ razy$ liczba mnożeń, aby uzyskać wszystkie wartości wyjściowe. Dane wyjściowe można obliczyć wydajnie, jeśli można wykorzystać niektóre cechy systemu.

Z podobnym scenariuszem mamy do czynienia, gdy musimy obliczyć dyskretne transformaty Fouriera interesującego nas sygnału.

Bezpośrednie obliczenie 2-D DFT jest po prostu obliczeniem podwójnej sumy

${\ Displaystyle X\left(k_{1},k_{2}\right)=\suma _{n_{1}=0}^{N_{1}-1}\suma _{n_{2}=0}^{ N_{2}-1}x(n_{1},n_{2})W_{N_{1}}^{n_{1}k_{1}}W_{N_{2}}^{n_{2} k_ {2}}}$${\ Displaystyle {\ tekst {dla}} 0 \ równoważnik k_ {1} \ równoważnik N_ {1} -1 { \text{ i }}0\równik k_{2}\równik N_{2}-1}$

${\ Displaystyle {\ tekst {gdzie}} W_ {N} \ równoważnik {\ tekst {exp}} \ lewo (-j {\ Frac {2 \ pi}} {N }}\Prawidłowy)}$

Całkowita liczba zespolonych mnożeń i zespolonych dodań potrzebnych do oszacowania tego 2-D DFT przez bezpośrednie obliczenie wynosi ${\ Displaystyle N_ {1} ^ {2} N_ {2} ^ {2}}$ . Jest to naiwne podejście, jednak wiemy już, że N-punktową 1-D DFT można obliczyć przy użyciu znacznie mniejszej liczby mnożeń niż $za$ algorytmu szybkiej transformaty Fouriera (FFT) Jak opisano w następnej sekcji, możemy również opracować szybkie transformaty Fouriera do obliczania dwuwymiarowych lub wielowymiarowych DFT

Szybkie algorytmy dla sygnałów wielowymiarowych

Podejście do dekompozycji wierszy i kolumn do oceny DFT

Sumę DFT w poprzednim równaniu można również zapisać w następującej postaci: ${\ Displaystyle X \ lewo (k_ {1}, k_ {2} \ prawej)}$

${ \displaystyle X\left(k_{1},k_{2}\right)=\suma _{n_{1}=0}^{N_{1}-1}\left[\suma _{n_{2} =0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2}}\right]W_{N_{1 }}^{n_{1}k_{1}}}$

Niech ${\ Displaystyle G \ lewo (n_ {1}, k_ {2} \ prawej)}$ oznacza ilość w nawiasach i jest dana przez:

${\ Displaystyle G \ lewo (n_ {1}, k_ {2} \ prawo )=\suma _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2 }}}$

${\ Displaystyle X \ lewo (k_ {1}, k_ {2} \ prawo )=\suma _{n_{1}=0}^{N_{1}-1}G\left(n_{1},k_{2}\right)W_{N_{1}}^{n_{1 }k_{2}}}$

Stosując tę ​​​​metodę, DFT $można$ jako wiele 1-D DFT. Oznacza to $\ displaystyle G}$ że każdą kolumnę $sol$ uznać za 1-D DFT odpowiedniej kolumny = stała $).$ A $każdy$ wiersz $jest$ -DFT odpowiedniego wiersza $.$ stała Dlatego obliczamy 2-D DFT, rozkładając go na wierszowe i kolumnowe DFT.

Ta sama zasada jest stosowana do oceny MD DFT sygnału M-wymiarowego.

Porozmawiajmy teraz o oszczędnościach obliczeniowych, jakie uzyskujemy stosując to podejście. Zaobserwowano $_$ _ Ponadto, jeśli każdy z tych 1-D DFT jest obliczany przy użyciu 1-D FFT, liczbę złożonych mnożeń można dalej zmniejszyć do ${\ Displaystyle N_ {1} N_ { 2}{\frac {\log _{2}N_{1}N_{2}}{2}}}$

Wektorowa podstawowa szybka transformata Fouriera

Podobnie jak w przypadku 1-D FFT, dziesiątkowanie w czasie można osiągnąć w przypadku sygnałów 2-D. 1-D DFT sygnału, którego długość jest potęgą 2, można wyrazić za pomocą dwóch DFT o połowie długości, z których każdy można ponownie wyrazić jako kombinację DFT o długości ćwiartki i tak dalej.

W przypadku sygnałów 2-D możemy wyrazić DFT za pomocą czterech $\ Displaystyle (N_ {1} {\ tekst {x}$${\ Displaystyle {\ Frac {N_ {1}} {2}} {\ tekst {x}} {\ Frac {N_ {2}} {2}}}$ DFT (zakładając ${\ Displaystyle N_ {1 }}$$2$ są ). Dla uproszczenia załóżmy, że ${\ Displaystyle N_ {1} = N_ {2} = N}$ . Podwójną sumę DFT można rozłożyć na cztery oddzielne sumowania, jedno na tych próbkach, dla których zarówno $displaystyle$$n_ {1}},$ jak i $displaystyle n_ {2}}$ jeden, dla którego jest parzysty i $n_ {1}}$$n_ {2}}$ dla którego $n_$${1}} jest$ i $displaystyle$$}$ { \ ${2}$ są nieparzyste.

Jest to napisane jako:

${\ Displaystyle X \ lewo (k_ {1}, k_ {2} \ prawej) = S_ {00} (k_ {1}, k_ {2}) + S_ {01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1 }}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

Gdzie

${\ Displaystyle S_ {00} (k_ {1}, k_ {2}) \ równoważnik \ suma _ {m_ {1} = 0} ^ {N / 2-1} \ suma _ {m_ {2} = 0 }^{N/2-1}x(2m_{1},2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

${\ Displaystyle S_ {01} (k_ {1}, k_ {2}) \ równoważnik \ suma _ {m_ {1} = 0} ^ {N / 2-1} \ suma _ {m_ {2} =0}^{N/2-1}x(2m_{1},2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

${\ Displaystyle S_ {10} (k_ {1}, k_ {2}) \ równoważnik \ suma _ {m_ {1} = 0} ^ {N / 2-1} \ suma _ {m_ {2} =0}^{N/2-1}x(2m_{1}+1,2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

${\ Displaystyle S_ {11} (k_ {1}, k_ {2}) \ równoważnik \ suma _ {m_ {1} = 0} ^ {N / 2-1} \ suma _ {m_ { 2}=0}^{N/2-1}x(2m_{1}+1,2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{ 2}}}$

$(k_ {1}, k_ {2})}$ tablice i ${\ Displaystyle S_$$}$$są$ w z poziomymi i pionowymi kropkami ${\ Displaystyle {\ Frac {N} {2}}}$ . Wykorzystując ten fakt, a także fakt, że możemy uzyskać następujące tożsamości: ${\ Displaystyle W_ {N} ^ {N/2} = -1,}$

${\ Displaystyle X \ lewo (k_ {1}, k_ {2} \ prawej) = S_ {00} (k_ {1}, k_ {2}) + S_ {01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1 }}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\ Displaystyle X \ lewo (k_ {1} + {\ Frac {N} {2}}, k_ {2} \ prawej) = S_ {00 }(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1}, k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\ Displaystyle X \ lewo (k_ {1}, k_ {2} + {\ Frac {N} {2}} \ prawej) = S_ {00 }(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1}, k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\ Displaystyle X \ lewo (k_ {1} + {\ Frac {N} {2}}, k_ {2} + {\ Frac {N}{2}}\right)=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{ 2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N} ^{k_{1}+k_{2}}}$

Powyższe równanie mówi nam, jak obliczyć cztery punkty DFT ${\ Displaystyle X \ lewo (k_ {1}, k_ {2} \ prawej) X \ lewo (k_ {1} + {\ Frac {N} {2}}, k_$ dla określonej wartości ${\ Displaystyle (k_ {1}, k_ {2} })}$ z czterech punktów ${\ Displaystyle S_ {00 }(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{i }}S_ {11}(k_{1},k_{2})}$ . ${\ Displaystyle S_ {00} (k_ {1}, k_ {2})}$ można uzyskać oceniając za ${\ Displaystyle \ lewo ({\ Frac {N} {2}} \ razy {\ frac {N} {2}} \ prawej)}$ -punkt DFT (podobnie można uzyskać inne ${\ displaystyle S_ {ij}} ).$

Widzimy więc, że ${2}}}$ można wyrazić za pomocą czterech ${$${\ Displaystyle {\ Frac {N} {2}} \ razy {\ Frac$ DFT.

Analogicznie do przypadku 1-D, obliczenia przedstawione na poniższym rysunku nazywane są motylem $\ Displaystyle {\ tekst {motyl}}}$ lub dokładniej ${\ displaystyle radix -(2\razy 2){\tekst{motyl}}}$ .

Każdy motyl wymaga trzech zespolonych mnożeń i ośmiu zespolonych dodatków do obliczenia wyników z danych wejściowych. ${\ Displaystyle S_ {00} (k_ {1}, k_ {2}), S_ {01} (k_ {1}, k_ {2}), S_ {10} (k_ {1}, k_ { 2}) {\ tekst {i}} S_ {11} (k_ {1}, k_ {2})}$ próbki z $)$ wymaga obliczeń ${\ Displaystyle {\ Frac {N ^ {2}} {4}} }$ motyle.

Ta procedura dziesiątkowania jest wykonywana ${\ Displaystyle \ log _ {2} N}$ razy, gdy ${\ Displaystyle N}$ jest potęgą 2. Każdy etap dziesiątkowania składa się z ${\ Displaystyle {\ frac { N ^ {2}}{4}}} motyli,$$obliczania$ liczbę złożonych mnożeń, które należy wykonać podczas -podstawa punktu ${\ Displaystyle (2 \ razy 2)}$ FFT jest dana przez

$\ Displaystyle C_ {wektorRadix (2 \ razy 2)} = {\ Frac {3N ^ {2}} {4}}\log _{2}N}$

Zobacz też

• Szybka transformata Fouriera
• Transformacja wielowymiarowa
• Próbkowanie wielowymiarowe
• Wielowymiarowy splot dyskretny
• Projektowanie i implementacja filtrów wielowymiarowych