Transformacija
Skok od periodičnih k splošnim signalom — prizma, ki razstavi zvok, svetlobo in vse vmes.
Predpogoji: 2. stopnja ali osnove integracije.
Na 2. stopnji smo spoznali Fourierjevo vrsto — za signale, ki se ponavljajo v neskončnost. A svet ni ponavljajoč. Zvok vašega glasu ni večni sinus; je kratka, enkratna stvar. Eksplozija, ki jo je seizmograf zaznal včeraj, se ne bo ponovila. Fotografija, ki jo pošljete prijatelju, obstaja le enkrat. Za takšne signale Fourierjeva vrsta odpove — in točno tu vstopi Fourierjeva transformacija.
Ideja je elegantno drzen hack: kaj če predpostavimo, da je naš enkraten signal del neskončno dolge periodične funkcije — katere perioda je neskončna? Ko pustimo periodo, da gre v neskončnost, se vsota sinusov iz Fourierjeve vrste preoblikuje v integral. Diskretne "barve" frekvenc se zlijejo v zvezni spekter. Dobimo orodje, ki deluje za vse.
Od vrste k transformaciji: intuicija
Na 2. stopnji ste videli, da Fourierjeva vrsta za periodični signal z periodo T da koeficiente pri frekvencah 1/T, 2/T, 3/T, ... — diskretna zbirka "barv". Ko T → ∞, se te barve gostijo in gostijo, dokler ne nastane zvezna mavrica. Vsota postane integral:
// f(t) ... signal v časovnem prostoru (kar slišimo/merimo)
// F(ξ) ... transformirani signal (spekter frekvenc, ξ = xi)
// e⁻²πiξt ... "detektor" za frekvenco ξ — vrtljivo kolo
Vidite e−2πiξt? To je samo sinus in kosinus skupaj — Eulerjeva formula pravi eiθ = cos θ + i·sin θ. Torej integral pomeni: "Vzemi signal, ga zamotaj okoli kroga pri frekvenci ξ, in poglej, kje se nabere težišče." Tisto, kar pride ven, je amplituda in faza frekvence ξ v originalnem signalu.
Ko je frekvenca namotavanja enaka frekvenci signala, se spirala ne razprši — ampak zbere v eno smer. Težišče (bela pika) se odmakne od centra. To je spekter.
Ta vizualizacija — zamotavanje signala okoli kroga — je srce Fourierjeve transformacije. Za vsako možno frekvenco ξ vprašamo: "Koliko te frekvence je v signalu?" Odgovor je razdalja težišča od izhodišča. Ko to naredimo za vsako frekvenco, dobimo spekter.
Euler je leta 1748 pokazal, da velja eiθ = cos θ + i·sin θ. Ko vstavimo θ = −2πξt, dobimo cos(2πξt) − i·sin(2πξt) — torej enotski vektor, ki s časom kroži po kompleksni ravnini s frekvenco ξ.
Integrirati signal pomnožen s tem vektorjem pomeni seštevati vse točke signala, ki so "obrnjene" na posebno frekvenco. Če signal vsebuje tisto frekvenco, vektorji niso naključno razmetani — kažejo v isto smer in se seštejejo v velik rezultat. Če je ni, se razpršijo enakomerno in vsota gre k nič. Natanko to počne tisto zamotavanje v vizualizaciji zgoraj.
Kompleksna vrednost F(ξ) nosi dve informaciji hkrati: |F(ξ)| je amplituda (moč) frekvence, arg F(ξ) pa je faza (zamik). Skupaj opisujeta vse, kar moramo vedeti o prisotnosti te frekvence v signalu.
Spekter: signal v frekvenčnem prostoru
Rezultat Fourierjeve transformacije — F(ξ) za vsak ξ — imenujemo spekter. Namesto da vidimo signal kot vrednosti skozi čas, ga vidimo kot recepturo: koliko vsake frekvence je v njem.
To ni le drugačen pogled — je drugačen prostor. Časovni prostor in frekvenčni prostor sta dve enako veljavni "govorici" za opis istega signala. Prehod med njima je reverzibilen — z inverzno transformacijo pridemo nazaj:
// Inverzna Fourierjeva transformacija — iz spektra nazaj v signal
// Edina razlika: predznak v eksponentu (+ namesto −)
Opazite: čisti sinus ima v spektru eno samo konico. Dva sinusa dasta dve konici. Pravokotni val ima konice pri lihih večkratnikih — točno to, kar smo spoznali na 2. stopnji. Hrup nima preferiranih frekvenc — spekter je enakomerno razporejen po vsem. Vsak signal ima svojo "frekvenčno osebnost".
Eden lepših rezultatov v matematiki: skupna energija signala je enaka v obeh prostorih. Če seštejemo kvadrate vrednosti v časovnem prostoru, dobimo enako kot kvadrate v frekvenčnem spektru:
∫|f(t)|² dt = ∫|F(ξ)|² dξ
To ni naključje — je posledica dejstva, da je Fourierjeva transformacija unitarni operator (dolžine ohranja). V praksi to pomeni: ko stiskamo zvok (npr. MP3), točno vemo, koliko energije smo izgubili, ko smo zavrgli visoke frekvence. Brez tega izreka bi bila kompresija slepa ugibanja.
Kaj nam spekter pove?
Recimo, da slišite ton klavirja. V ušesu se membrana odzove na cel snop frekvenc hkrati. Fourierjeva transformacija tega zvoka pokaže:
Vse to — spektralna analiza — je osnova glasbenega produciranja, diagnostike strojev, geofizike in medicinskih naprav. Šele ko signal vidimo v frekvenčnem prostoru, ga razumemo.
Fourierjeva transformacija kot filter
Ker je transformacija reverzibilna, jo lahko uporabimo za manipulacijo signalov: spremenimo spekter in se vrnemo nazaj v časovni prostor. To je filtriranje.
Nižajni filter (nizkoprehodnik) prepušča le nizke frekvence in zaduši visoke — rezultat je "zamegljen" ali "topel" zvok. Višajni filter naredi obratno — ostanejo le visoke frekvence, signal je "oster" in "piskav". Pasovni filter prepušča le pas frekvenc vmes — ravno to naredi radijska postaja, ki "spusti" le signal na vaši frekvenci.
Filtriranje v časovnem prostoru zahteva konvolucijo — za vsako točko signala moramo sešteti prispevke vseh sosedov. Za signal z N točkami in filter dolžine M je to O(N·M) operacij — počasno.
Konvolucijski izrek pravi: konvolucija v časovnem prostoru = množenje v frekvenčnem prostoru. Torej: transformiramo signal (O(N log N)), pomnožimo spektra (O(N)), transformiramo nazaj (O(N log N)). Skupaj O(N log N) — bistveno hitreje.
To je razlog, da vaš telefon v realnem času procesira zvok, slike pa stisnete v delčku sekunde. Brez tega izreka bi bila digitalna obdelava signalov praktično neizvedljiva na potrošniški strojni opremi.
Izrek o negotovosti: čas proti frekvenci
Tu pride najlepši — in najgloblji — rezultat te stopnje. Obstaja fundamentalna meja, kako natančno hkrati poznamo signal v časovnem in frekvenčnem prostoru.
Čim bolj natančno je signal lokaliziran v času, tem bolj razpotegnjen je v frekvenčnem prostoru — in obratno.
Kratek impulz (npr. klik) je v času zelo oster — a v frekvenci vsebuje vse frekvence enakovredno (ravna spektralna linija). Čisti sinus traja večno — in ima v spektru eno samo konico.
Ko je impulz ozek v času (σ majhen), je spekter širok v frekvenci — in obratno. Produkt σčas·σfrekvenca ≥ 1/(4π) je vedno konstantno omejen od spodaj.
To ni omejitev naše merilne opreme — je matematično dejstvo. In to je točno Heisenbergov princip nedoločenosti iz kvantne mehanike. Niti naključje: de Broglieva valovna funkcija delca je Fourierjev transform njegove gibalne količine. Fizika valovanja je matematika Fourierja.
Med vsemi signali ima Gaussova krivulja (zvonec) posebno lastnost: njen Fourierjev transform je spet Gaussova krivulja. Je edina oblika, ki je "lastni vektor" Fourierjeve transformacije.
Posledica: Gaussov impulz ima optimalno razmerje med časovno in frekvenčno lokalizacijo — doseže mejo σ·σ_f = 1/(4π). Vsak drug signal je "slabši" v smislu tega produkta.
Zato Gaussove funkcije vladajo povsod: v statistiki (normalna porazdelitev), v fiziki (valovna paketa v kvantni mehaniki), v strojnem učenju (jedra v SVM), v obdelavi slik (Gaussovo zamegljevanje). Niso tam zgolj ker so "lepe" — so tam, ker so Fourierjevo optimalne.
Dvodimenzionalna Fourierjeva transformacija
Vse do zdaj smo govorili o enodimenzionalnih signalih — vrednost v odvisnosti od časa. A Fourierjevo transformacijo lahko razširimo na dve dimenziji: namesto časa imamo koordinate (x, y) slike.
Spekter slike pokaže, kakšne prostorske vzorce v njej prevladuje. Horizontalne črte v spektru pomenijo horizontalne proge v sliki; diagonalne frekvence pomenijo diagonalne vzorce. Vsaka frekvenca v prostoru ustreza ponavljajočemu se vzorcu v sliki.
JPEG stiskanje točno to izkorišča: slike razstavi na 2D Fourierjeve komponente in zavrže visoke prostorske frekvence (fino podrobnosti), ki jih oko le težko zazna. Ko stiskate fotografijo na 20 %, ste pravzaprav rekli: "Ohrani le nizke frekvence spektra." Rezultat je manjša datoteka — in rahlo zamegljena slika.
1. Razdeli na bloke 8×8 pikslov. Vsak blok obdelamo ločeno — to poenostavi računanje in lokalizira napake.
2. DCT (diskretna kosinusna transformacija). Varianta Fourierjeve transformacije, prilagojena realnim vrednostim. Vsak blok 8×8 se preslika v 64 koeficientov, urejenih od nizkih frekvenc (levo zgoraj) do visokih (desno spodaj).
3. Kvantizacija. Koeficiente visokofrekvenčnih komponent zaokrožimo bolj agresivno (ali jih povsem zavrže). To je edini korak z izgubo — tukaj se "izgubijo" podatki.
4. Huffmanovo kodiranje. Rezultat (večinoma nič-e za visoke frekvence) učinkovito stisnemo z brezizgubnim kodiranjem. Dolga zaporedja ničel se kodirajo s kratko kodo.
Kakovost JPEG (1–100) nadzira agresivnost kvantizacije. Na 100 % praktično ni kvantizacije — na 1 % ostanejo le najnižje frekvence. Tipično 80 % dá vizualno neopazno razliko pri 5× manjši datoteki.
Kar zdaj veste
Fourierjeva transformacija razširi Fourierjevo vrsto na neperiodične signale z integracijo po vseh frekvencah. Signal in spekter sta dve govorici istega: prehod med njima je brezizgubno reverzibilen. Izrek o negotovosti poveže frekvenčno in časovno resolucijo — in razloži Heisenbergov princip. Filtriranje v frekvenčnem prostoru je enakovredno konvoluciji v časovnem prostoru, a hitrejše. Na naslednji stopnji bomo videli, kako vse to narediti v računalniku z O(N log N) namesto O(N²) — algoritem, ki je dobesedno spremenil civilizacijo.