Interpolacja

Transformacja Fouriera (ang. Fourier Transformation) jest narzędziem analitycznym, które pozwala rozłożyć skomplikowane "obiekty" na proste elementy składowe. Jako przykład, wyobraź sobie, że w kuchni w naczyniu znajduje się pyszny sok. Gdy poddasz go analizie, to otrzymasz informację z czego ten sok się składa oraz w jakiej ilości zawiera swoje składniki: np. 25% borówek, 40% bananów i 35% mleka. Coś podobnego robi transformacja Fouriera z sygnałami: bierze skomplikowany sygnał, np. dźwięk z mikrofonu, i rozbija go na pojedyncze fale sinusoidalne, z których ten dźwięk jest złożony:

Mówiąc językiem fizyki i matematyki: TF to narzędzie, które bierze skomplikowany, „poszarpany” sygnał (np. dźwięk) i rozbija go na pojedyncze fale sinusoidalne, z których ten sygnał został złożony. Przenosi nas z domeny czasu \(t\) (gdzie widzimy tylko sumaryczny hałas) do domeny częstotliwości \(f\) (gdzie widzimy konkretne nuty/składniki):

W domenie czasu \(t\) (na zwykłym wykresie fali dźwiękowej) sygnały są nieczytelne. Jeśli w tym samym momencie gra gitara, perkusja i ktoś krzyczy, mikrofon rejestruje jedną, chaotyczną, falującą linię.

TF rozwiązuje problem izolacji i analizy danych:

• Separacja: Pozwala komputerowi „usłyszeć” poszczególne instrumenty osobno z jednego nagrania.
• Kompresja: Zamiast zapisywać miliard punktów skomplikowanej fali, TF pozwala zapisać tylko informację typu: „gra dźwięk A przez 5 sekund i dźwięk B przez 3 sekundy”. To drastycznie zmniejsza wagę plików.
• Filtracja: Rozwiązuje problem szumu. Jeśli w nagraniu piszczy stary telewizor (wysoka częstotliwość), TF pokazuje ten pisk jako pojedynczy, wyraźny słupek na wykresie w dziedzinie częstotliwości \(f\). Wystarczy go „skasować” i cofnąć transformację, aby uzyskać czysty dźwięk.

Transformacja Fouriera zyskała na znaczeniu po opracowaniu szybkiego algorytmu dokonującego tej transformacji, tzw. FFT (ang. Fast Fourier Transformation). Tym zajmiemy się w dalszej części rozdziału. Transformację Fouriera będziemy oznaczać skrótem FT.

1805 rok – Carl Friedrich Gauss (Pierwszy, ukryty algorytm FFT)

Wielu uważa, że szybki algorytm obliczania transformacji Fouriera (FFT) powstał w latach 60. XX wieku. W rzeczywistości Carl Friedrich Gauss obliczył go jako pierwszy w 1805 roku, próbując wyznaczyć orbity asteroid Pallas i Juno.

• Co zrobił: Opracował matematyczny trik pozwalający drastycznie skrócić liczbę mnożeń potrzebnych do analizy okresowych orbit.
• Dlaczego świat o tym zapomniał: Gauss nigdy nie opublikował tej pracy za życia. Została ona wydana dopiero pośmiertnie w 1866 roku w jego Dziełach zebranych, napisana po łacinie, przez co świat nauki kompletnie ją przeoczył na kolejne sto lat.

1807 rok – Jean Baptiste Joseph Fourier (Narodziny idei)

Francuski matematyk Joseph Fourier przedstawia przed Instytutem Francuskim swoją przełomową pracę dotyczącą rozchodzenia się ciepła w ciałach stałych.

• Co zrobił: Sformułował twierdzenie, że każdą funkcję okresową można przedstawić jako sumę nieskończonego szeregu sinusów i cosinusów.
• Odrzucenie przez elity: Najwięksi matematycy epoki (Lagrange, Laplace, Legendre) odrzucają jego pracę. Lagrange kategorycznie twierdził, że zaokrąglonymi sinusami nie da się opisać funkcji o ostrych, "kwadratowych" załamaniach (tzw. efekt Gibbsa).

1822 rok – Publikacja „Analitycznej teorii ciepła”

Po 15 latach walki z recenzentami i dopracowywania teorii, Fourier publikuje swoje opus magnum: Théorie analytique de la chaleur.

• Co to zmienia: W tej książce formalnie definiuje to, co dziś nazywamy Szeregiem Fouriera (dla sygnałów okresowych) oraz Transformacją Fouriera (dla sygnałów nieokresowych, rozciągniętych od \(-\infty \) do \(\infty \)). Świat matematyki zaczyna rozumieć potęgę tego narzędzia.

1829 rok – Peter Gustav Lejeune Dirichlet (Rygor matematyczny)

Fourier działał intuicyjnie, co dawało pole do krytyki. Niemiecki matematyk Dirichlet jako pierwszy podaje ścisły dowód matematyczny zbieżności szeregów Fouriera.

• Co zrobił: Sformułował tzw. warunki Dirichleta. Określił dokładnie, jakie kryteria musi spełniać funkcja (np. skończona liczba minimów, maksimów i punktów nieciągłości), aby transformacja Fouriera była dla niej w 100% poprawna matematycznie.

1965 rok – James Cooley i John Tukey (Ponowne odkrycie FFT i cyfrowa rewolucja)

Wraz z pojawieniem się pierwszych komputerów, klasyczna Dyskretna Transformacja Fouriera (DFT) okazała się zbyt ciężka obliczeniowo – dla \(N\) próbek wymagała \(N^{2}\) operacji.

• Co zrobili: Cooley i Tukey publikują niezależnie algorytm FFT (ang. Fast Fourier Transformation – Szybka Transformacja Fouriera), redukujący liczbę obliczeń do \(N \log_2 N\).
• Efekt: To najważniejszy moment dla współczesnej technologii. Bez tego algorytmu komputery nie byłyby w stanie przetwarzać dźwięku i obrazu w czasie rzeczywistym.

Dopiero po publikacji odkryto, że powtórzyli oni schemat Gaussa z 1805 roku.

Przełom XX/XXI wieku – Powstanie wersji okienkowej (STFT) i falkowej

Klasyczna TF ma jedną wadę: pokazuje jakie częstotliwości są w sygnale, ale nie pokazuje, kiedy wystąpiły. W odpowiedzi na to ograniczenie matematycy rozwinęli transformację:

• STFT (ang. Short-Time Fourier Transform – Krótkookresowa Transformacja Fouriera): Dzieli sygnał na małe "okienka" czasowe i analizuje je po kolei.
• Transformacja falkowa (ang. Continuous wavelet transform): Zastępuje sinusy tzw. falkami, co pozwala na jednoczesną, precyzyjną analizę czasu i częstotliwości. Stała się podstawą formatów takich jak JPEG 2000.

xxx

xxx

xxx

xxx

xxx

xxx