Konwolucja | mysimulator.uk

Operacja sama w sobie

Konwolucja bierze dwa funkcje i generuje trzecią. W przypadku dyskretnych sygnałów – takich, jakie faktycznie przechowują komputery – jest to przesuwające się ważone sumowanie: odwróć jedną sekwencję, przesuń ją po drugiej próbka po próbce i w każdym położeniu pomnóż nakładające się wartości i zsumuj. Wynik na każdym przesunięciu stanowi jeden próbkowany wynik. Zapisywane to wygląda następująco: konwolucja sygnału x z jądrem h wynosi:

y[n] = Σ x[k] * h[n - k] // suma po wszystkich k // jądro jest odwrócone i przesuwa się na przemian przez x Może to wydawać się abstrakcyjne, ale konkretny przykład sprawia, że wszystko staje się jasne. Niech h będzie jądrem o trzech elementach [1/3, 1/3, 1/3]. Konwolucja dowolnego sygnału z nim zastępuje każdy próbkowany wynik średnią z jego wartości oraz dwóch sąsiednich - ruchome uśrednianie, najprostszy możliwy filtr dolnoprzepustowy, który wygładza szybkie wahania, pozostawiając trend wolno zmieniający się.

y[n] = Σ  x[k] * h[n - k]     // sum over all k
                              // h is flipped and slid across x

demo na żywo · powiązana symulacja● LIVE

Dlaczego każdy system LTI jest konwolucją

Konwolucja to nie tylko jeden przydatny trik wśród wielu – to twierdzenie ukryte w środku. Każdy liniowy, staczyznyczny (LTI) system – taki, w którym podwojenie wejścia podwaja wyjście, a opóźnienie wejścia o dowolną ilość powoduje opóźnienie wyjścia dokładnie o tę samą wartość, bez zmiany kształtu – jest całkowicie zdefiniowany przez jedną funkcję: jego odpowiedź na pojedynczy, natychmiastowy impuls, czyli odpowiedź na impuls. Poznając tę jedną odpowiedź, wyjście systemu dla dowolnego wejścia to po prostu konwolucja wejścia z odpowiedzią na impuls. Każdy stały filtr liniowy, niezależnie od tego, czy jest to wygładzanie fali dźwiękowej, rozmycie obrazu, czy modelowanie wpływu akustyki pomieszczenia na dźwięk, strukturalnie jest dokładnie tą samą operacją.

Znane jądra

Zmiana jądra wpływa na to, co robi filtr, bez zmiany podrzędnej mechaniki. Jądro, które odejmuje przesuniętą, wygładzoną kopię sygnału od niego samego, generuje detekcję krawędzi lub pogłębianie – podkreślając szybkie zmiany zamiast je usuwać. Jądro o kształcie Gaussa produkuje naturalnie wyglądający rozmywacz, używany w całym przetwarzaniu obrazów, ponieważ nie posiada ostrych rogów, które mogłyby wprowadzać artefakty zaszumienia. W dwóch wymiarach ta sama operacja przesunięcia i sumowania, stosowana z małym jądrem nad każdym obszarem sąsiedztwa pikseli, jest dokładnie warstwą konwolucyjną, będącą sercem sieci neuronowej konwolucyjnej – każde nabyte jądro wykrywa specyficzny wzór lokalny, gdziekolwiek pojawia się na obrazie.

Teoria konwolucji: mnożenie pod spodem

Konwolucja w dziedzinie czasu (lub przestrzeni) odpowiada dokładnie zwykłemu mnożeniu punktowemu w dziedzinie częstotliwości, i odwrotnie. Ta teoria konwolucji jest jednym z najbardziej przydatnych faktów w przetwarzaniu sygnałów: oznacza to, że filtrowanie – przekształcanie sygnału poprzez jego konwolucję z jądrem – można rozumieć jako równoważnie przekształcanie jego spektrum przez pomnożenie go przez odpowiedź częstotliwościową jądra. Odpowiedź częstotliwościowa jądra o charakterze filtrów dolnoprzepustowych jest duża w pobliżu zerowej częstotliwości i mała przy wysokich częstotliwościach; mnożenie spektrum sygnału przez tę odpowiedź dokładnie usuwa szybkie drgania, widoczne z drugiej domeny.

convolve(x, h)   in time domain
  ⇔  multiply(X(f), H(f))   in frequency domain, where X, H are Fourier transforms

Szybka konwolucja: dlaczego FFT ma tu również znaczenie

Bezpośrednia konwolucja dwóch sekwencji o długości n kosztuje rzędu n² mnożeń — każdy element wyjściowy sumuje się z każdym pikselem jądra. Dla długiego jądra lub długiego sygnału jest to bardzo kosztowne. Twierdzenie konwolucji oferuje drogę ucieczki: przekształć oba sygnały do domeny częstotliwości za pomocą Szybkiej Transformacji Fouriera w czasie O(n log n), pomnóż je punkt po punkcie w czasie O(n) i przetransformuj produkt ponownie w czasie O(n log n) — znacznie tańsze niż bezpośrednia konwolucja, gdy długość jądra jest wystarczająco duża, aby uczynić przełączenie strategii wartym uwagi, co dokładnie wyjaśnia, dlaczego biblioteki audio i obrazu zmieniają strategie w oparciu o rozmiar jądra.

Frequently asked questions

Co oznacza, że system jest liniowy i niezmiennym w czasie?

Liniowość oznacza, że skalowanie lub dodawanie wejść skaluje lub sumuje wyjścia w taki sam sposób, bez dodatkowych składników krzyżowych. Niezmienność w czasie oznacza, że system zachowuje się tak samo niezależnie od momentu przyjścia wejścia – opóźnienie wejścia powoduje opóźnienie wyjścia o dokładnie tę samą wartość, bez zmiany kształtu. Tylko systemy posiadające obie te właściwości są gwarantowane pełne opisanie za pomocą konwolucji z pojedynczą odpowiedzią na impuls.

Dlaczego jądro jest odwrócone w formule konwolucji?

Odwrócenie jądra uwzględnia przyczynowość i kolejność: konwolucja sumuje wejście, ważone przez to, jak system reaguje na coś, co wydarzyło się w pewnym czasie, a odwrócenie jądra przed przesuwaniem go sprawia, że ten moment kolejności pojawia się prawidłowo, zamiast obliczać korelacje, która nie odwraca i mierzy podobieństwo zamiast odpowiedzi.

Dlaczego mnożenie w dziedzinie częstotliwości sprawia, że konwolucja jest znacznie szybsza?

Bezpośrednia konwolucja dwóch sekwencji o długości n kosztuje rzędu n kwadrat mnożeń. Twierdzenie o konwolucji mówi, że konwolucja w czasie równa się zwykłemu mnożeniu w dziedzinie częstotliwości, a szybka transformata fourierowska oblicza każdą stronę w około n log n operacji, więc transformacja obu sygnałów, mnożenie punktowe i transformacja z powrotem jest znacznie tańsze niż bezpośrednia konwolucja, gdy n jest duże.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Convolution i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację Convolution

Konwolucja: Jak Filtry Przekształcają Sygnały