Interaktywny wstęp do transformaty Fouriera

Jez Swanson

Przekład: Jakub Górczyński

Transformata Fouriera jest narzędziem, które znajduje zastosowanie w wielu rzeczach. Znajdziesz tu wyjaśnienie, co robi transformata Fouriera i kiedy bywa użyteczna. Dowiesz się też, jak za jej pomocą możesz tworzyć ciekawie wyglądające rzeczy, np. tą wizualizację:

Zamierzam wytłumaczyć, jak działa ta animacja i o co chodzi w transformacie Fouriera!

Po przeczytaniu tego interaktywnego artykułu powinieneś/powinnaś mieć dobre rozeznanie w temacie. Poznasz następujące zagadnienia:

Na razie nie będę zagłębiać się w równania i matematyczne szczegóły, które skrywa w sobie transformata Fouriera. Na dobry początek warto zacząć od tego, co to narzędzie faktycznie robi i dlaczego ktoś chciałby go użyć. Jeśli chcesz poznać matematyczne oblicze transformaty Fouriera, poniżej znajdziesz linki do interesujących Cię artykułów.

Co to właściwie jest?

Mówiąc krótko, transformata Fouriera jest metodą rozbijania czegoś (np. sygnału dźwiękowego) na kilka sinusoid. Jak zwykle nazwa pochodzi od gościa, który żył dawno temu i nazywał się Fourier.

Zacznijmy od prostego przykładu. Na pierwszy rzut oka weźmy fale - wzory i schematy powtarzające się w czasie.

Poniżej przykładowa fala:

Ten falisty wykres może być rozbity na zwykłe sinusoidy. To oznacza, że po zsumowaniu tych dwóch sinusoid otrzymamy oryginalną, wyjściową falę.

Transformata Fouriera jest sposobem na rozbicie złożonej fali na regularne sinusoidy składające się na ten wykres. W tym przykładzie można przeanalizować i rozbić sygnał w głowie, po prostu patrząc na falę.

Ale po co? Okazuje się, że wiele rzeczy wokół nas oddziałuje na siebie w oparciu o te niewinnie wyglądające sinusoidy, a ściślej mówiąc - w oparciu o częstotliwości tych fal.

Najbardziej oczywistym przykładem jest dźwięk. Gdy go słyszymy, ucho nie odbiera pojedynczej, pokręconej linii, ale różne częstotliwości sinusoid, które tworzą słyszany dźwięk.

Dzięki temu, że można taką analizę przeprowadzić na komputerze, jesteśmy w stanie określić, co faktycznie słyszymy, jak niski lub jak wysoki jest dźwięk albo wskazać, jaka to nuta.

Transformata Fouriera działa również w przypadku fal, które nie wyglądają jak złożenie sinusoid.

Rzućmy okiem na przykład poniżej. Jest to tzw. fala kwadratowa.

Być może nie wydaje się to wykonalne, ale ta fala też może być rozdzielona na sinusoidy.

Tym razem potrzebujemy ich znacznie więcej. Praktycznie rzecz biorąc - nieskończonej ilości pośrednich sinusoid, aby jak najdokładniej przedstawić wyjściową falę. W miarę dodawania kolejnych fal otrzymywany wzór coraz bardziej przypomina kwadratową falę, od której rozpoczął się proces.

Przemieszczaj suwak powyżej, aby zobaczyć, ile sinusoid tworzy złożoną falę

Gdy się przyjrzysz, zauważysz, że właściwie tylko kilka pierwszych sinusoid ma największy wpływ na układ fali. Gdy suwak znajduje się w połowie zakresu, fala jest już mniej więcej ukształtowana, ale na jej powierzchni wciąż widnieją "wężyki". Fale znajdujące się w drugiej połowie zakresu suwaka są potrzebne, aby spłaszczyć "wężyki" i uzyskać gładką linię.

Gdy posłuchasz fali, usłyszysz, że dźwięk się obniża, bo pozbyliśmy się wyższych częstotliwości.

Ten proces zadziała dla każdej powtarzającej się linii. Daj się ponieść - narysuj swoją własną!

Rysuj tutaj!

Przemieszczaj suwak aby zobaczyć, że w miarę dodawania kolejnych fal wykres coraz bardziej przypomina twój rysunek

I znów - poza dodatkowymi "wężykami", fala jest dość podobna jedynie w oparciu o połowę sinusoid.

Możemy skorzystać z faktu wspomnianego powyżej. Dzięki transformacie Fouriera jesteśmy w stanie "wyciągnąć" interesujące nas fragmenty sygnału dźwiękowego i otrzymać ścieżkę, która różni się w niewielkim stopniu od oryginału.

Zazwyczaj fala przechowywana jest na komputerze w formie zbioru punktów.

Zamiast tego można przedstawić falę jako grupę sinusoid, a następnie skompresować dźwięk poprzez eliminację niższych częstotliwości. Końcowy wynik nie będzie identyczny, ale różnicę ciężko będzie wysłyszeć.

W zasadzie jest to sposób, w jaki działa format MP3, z tą różnicą, że tam eliminacja częstotliwości przebiega trochę bardziej inteligentnie.

W tym przypadku można było wykorzystać transformatę Fouriera do zrozumienia falowej natury dźwięku i metody jego kompresji.

Ok, teraz pora zagłębić się bardziej w transformatę Fouriera. Kolejna część wygląda naprawdę super, ale też pozwala lepiej zrozumieć, co ten proces robi. W dużej mierze jednak po prostu wygląda super.

Epicykle

Na początku powiedziałem, że transformata rozbija różne rzeczy na sinusoidy. Rzecz w tym, że fale powstałe w tym procesie nie są zwykłymi sinusoidami. Są trójwymiarowe (3D). Możesz określić je jako "złożone sinusoidy" lub po prostu "spirale".

Gdy patrzymy na spiralę z boku, wygląda jak zwykła sinusoida. Patrząc od frontu - porusza się po okręgu.

Do tej pory wszystko, o czym do tej pory mówiliśmy wymagało sinusoid 2D (dwuwymiarowych). Gdy przeprowadzamy transformatę Fouriera na falach 2D, nie mamy do czynienia ze złożonymi fragmentami i otrzymujemy jedynie sinusoidy.

Możemy jednak użyć sinusoid 3D, aby otrzymać coś, co wygląda całkiem interesująco. Na przykład to:

Co tu się właściwie dzieje?

Cóż, możemy myśleć o tym rysunku jak o trójwymiarowym kształcie ze względu na sposób, w jaki się porusza w miarę upływu czasu. Gdy wyobrazisz sobie dłoń rysowaną przez kogoś, trzy wymiary określają pozycję czubka ołówka w danym momencie. Osie x i y wyznaczają pozycję, natomiast oś z - czas.

Ponieważ teraz mamy do czynienia z trójwymiarowym wzorem, nie możemy użyć dwuwymiarowych sinusoid, aby przeprowadzić analizę. Nieważne jak dużo fal 2D zostanie dodanych - wynik nigdy nie będzie przypominać czegoś trójwymiarowego. Potrzeba innego rozwiązania.

Możemy posłużyć się spiralami przedstawionymi przed chwilą. Jeśli dodamy ich wystarczająco dużo, możemy otrzymać coś całkiem podobnego do wyjściowego wzoru 3D.

Pamiętaj, że spirale przypominają okręgi, gdy patrzy się na nie z przodu. Wzór okręgu poruszającego się wokół innego okręgu nosi nazwę epicyklu.

Użyj suwaka powyżej, aby zmienić ilość okręgów

Tak jak poprzednio, otrzymujemy całkiem niezłe przybliżenie naszego wzoru jedynie przy użyciu kilku okręgów. Ponieważ jest to dość prosty kształt, kolejne okręgi delikatnie wyostrzają krawędzie.

Wszystko to można wykorzystać w jakimkolwiek rysunku. Naprawdę! Teraz masz okazję, żeby się tym pobawić.

Rysuj tutaj!

Użyj suwaka, aby zmieniać ilość okręgów użytych do twojego rysunku

Po raz kolejny możesz zobaczyć, że dla większości kształtów można je całkiem przyzwoicie przybliżyć za pomocą niewielkiej ilości okręgów, bez potrzeby przechowywania wszystkich punktów.

Czy można użyć tego procesu dla prawdziwych danych? W sumie… można! W praktyce mamy do dyspozycji inny format, który z pewnością sprawdzi się lepiej w przypadku kształtów, które tworzymy - SVG. Na tą chwilę więc przyda się to jedynie do tworzenia fajnych GIFów.

Istnieje jednak jeszcze jeden rodzaj wizualnych danych, który korzysta z transformaty Fouriera.

JPEG

Czy wiedziałeś/aś, że transformata Fouriera może być wykorzystana w obrazkach? Powiem więcej - dzieje się to za każdym razem, gdy korzystasz z formatu JPEG, ponieważ to na transformacie opiera się zasada jego działania. W przypadku plików graficznych proces wygląda tak samo - rozbijamy jakiś obiekt na kilka sinusoid i przechowujemy jedynie te najbardziej istotne.

Tym razem mamy do czynienia z obrazkiem, zatem potrzebujemy innego rodzaju fali. Niezależnie od tego, jaki to będzie obraz, potrzebujemy takiego obiektu, który po dodaniu kilku fal pozwoli powrócić do oryginalnego obrazu.

Żeby to zrobić, każda z sinusoid także będzie obrazem. W tym przypadku fali nie będzie reprezentować linia, ale obrazki z białymi i czarnymi fragmentami. Aby przedstawić rozmiar fali, każdy obrazek będzie miał większy lub mniejszy kontrast.

Można skorzystać z tej samej metody do tworzenia koloru, ale póki co skupimy się na czarno-białych obrazach. Jeśli chcemy przedstawić bezbarwne obrazy, potrzebujemy zarówno obrazy fal poziomych…

… jak i fal pionowych.

Same obrazki fal nie wystarczą do wizualizacji obrazów, które chcemy otrzymać. Potrzeba dodatkowych obrazków, otrzymanych w wyniku "przemnożenia" przez siebie poziomego i pionowego obrazka.

×
=

Poniżej lista obrazków, których potrzebujemy do obrazu o wymiarach 8x8.

Gdy weźmiemy te obrazki, skalibrujemy kontrast i nałożymy na siebie, możemy stworzyć każdy obraz.

Zacznijmy od litery 'A'. Jest dość mała, jednak jest to konieczne. Inaczej w trakcie procesu moglibyśmy otrzymać inne, zbędne obrazy.

W miarę dodawania i nakładania na siebie obrazków, otrzymywany rezultat coraz bardziej przypomina faktyczny, wyjściowy obraz. Myślę, że jesteś w stanie zauważyć schemat, ponieważ dostajemy rozsądne przybliżenie przy użyciu zaledwie kilku obrazków.

W przypadku prawdziwych JPEGów istnieje kilka drobnych, wartych uwagi szczegółów.

Wyjściowy obraz o wymiarach 8x8 zostaje rozłożony na fragmenty (siatka 8x8). Każdy fragment osobno również zostaje rozbity. Używamy pewnego zbioru częstotliwości, aby określić, jak ciemny lub jasny jest piksel, a następnie dwóch zbiorów barw - jednego zbioru dla czerwonej i zielonej, a kolejnego zbioru dla niebieskiej i żółtej. Liczba częstotliwości, która zostanie użyta do każdego fragmentu determinuje jakość obrazu.

Poniżej prawdziwy obraz typu JPEG, powiększony, żeby zobaczyć detale. Przewiń stronę w dół, aby zobaczyć przebieg procesu.

Wnioski

Podsumowując:

Tytuł tego samouczka mówi sam za siebie - jest to jedynie wstęp i wierzchołek góry lodowej. Transformata Fouriera jest niezwykle potężnym narzędziem, którego podstawą działania i fundamentem jest podział na grupę częstotliwości. Można je spotkać w wielu dziedzinach i zagadnieniach. Z transformaty korzysta się chociażby przy projektowaniu obwodów elektrycznych, w telekomunikacji, rezonansie magnetycznym, a nawet w fizyce kwantowej!

Pytania dla dociekliwych

Pominąłem zdecydowaną większość matematycznych zagadnień, ale jeśli interesują cię podwaliny działania transformaty Fouriera, poniżej znajduje się kilka pytań, o które możesz się oprzeć w trakcie poszukiwania informacji:

Dalsza 'czytanka'

Jeśli chcesz wiedzieć więcej, poniżej umieszczam linki do bardzo dobrych źródeł, które możesz sprawdzić (źródła umieszczone przez autora są w języku angielskim):

An Interactive Guide To The Fourier Transform
Świetny artykuł zgłębiający matematyczne oblicze transformaty Fouriera.

But what is the Fourier Transform? A visual introduction.
Bardzo dobry film autorstwa 3Blue1Brown objaśniający matematykę stojącą za tym procesem z perspektywy dźwięku i jego falowej natury.

A Tale of Math & Art: Creating the Fourier Series Harmonic Circles Visualization
Kolejny artykuł, który przybliży ci zastosowania epicykli do rysowania ścieżek od tej algebraicznej strony.

Fourier transform (Wikipedia)
Artykuł z Wikipedii również nie ma się czego wstydzić.

O autorze

Jestem Jez! Pracuję na pełen etat w pewnej dużej firmie w rejonie zatoki San Francisco. W wolnym czasie lubię tworzyć gry i interaktywne, programowalne rzeczy jak animację powyżej.

Ta strona ma otwarte źródło, możesz podejrzeć jej kod na GitHubie! Jeśli chcesz podzielić się swoimi wrażeniami lub po prostu zadać pytanie, śmiało napisz do mnie maila na fourier [at] jezzamon [dot] com lub na Twitterze.

Jeśli chcesz zobaczyć, co jeszcze robię, zajrzyj na moją stronę główną, a jeśli chcesz być na bieżąco - możesz zaobserwować moje konto na Twitterze, @jezzamonn!