FFT ja sen sovelluksia

Tänään tarkasteltiin Fourier muunnoksen ominaisuuksia, sovelluksia sekä nopeaa toteutusta.

Luennon aluksi esiteltiin alkeellinen menetelmä puheen tunnistukseen. Kirjan Elements of statistical learning kappaleessa 5.2.3 opetetaan tietokone erottelemaan kaksi vokaalia niiden Fourier-muunnosten perusteella. Menetelmä on nimeltään logistinen regressio, joka monimutkaisista kaavoista huolimatta on varsin yksinkertainen toteuttaa: menetelmä etsii kertoimet kullekin Fourier-muunnoksen taajuudelle, ja laskee tulokset yhteen. Jos luku on positiivinen, tulkitaan äänne ä-kirjaimeksi, muutoin a-kirjaimeksi. 

Esimerkki kuvaa hyvin tämän päivän signaalinkäsittelyalgoritmia: perusmenetelmiä (Fourier-muunnos, konvoluutio, jne.) käytetään piirregeneraattoreina, jotka tuottavat hieman parempaa raakadataa kuin suora mittaussignaali (esim. taajuustietoa eikä raakaa mittausdataa). Laskettujen piirteiden perusteella sitten nostetaan tiedon abstraktiotasoa edelleen. Esimerkiksi äänteen tunnistuksessa hierarkia on esimerkiksi seuraava:

48000 aikatason näytettä -> 256 taajuustason kerrointa -> 1 bitti, joka kertoo kumpi äänne on kyseessä

Toisena esimerkkinä mainitsin tamperelaisen Visy Oy:n, jossa olen työskennellyt kymmenisen vuotta sitten automaattisen rekisterikilven tunnistuksen parissa. Tässäkin suuresta määrästä matalan tason pikselitietoa päätellään pieni määrä sovellukselle olennaista tietoa (merkkijono ABC-123).

Tämän jälkeen siirryttiin tarkastelemaan Fourier-muunnoksen ominaisuuksia. Ominaisuuksista tutustuttiin lähemmin siirtoon ajassa (esim. laske signaalin x(n+20) muunnos, kun tiedetään x(n):n muunnos) sekä konvoluution muunnokseen (DFT muuntaa konvoluution kertolaskuksi, eli x(n)*y(n) -> X(n)Y(n)). Tämä on perustana mm. dekonvoluutiolle joka on konvoluutiolle käänteinen operaatio. Menetelmää käytettiin mm. Hubble-teleskoopin alkuaikoina, jolloin yhdessä peilissä olleen hiontavirheen vuoksikuvat olivat sumuisia. Kuvantamisprosessia voidaan nimittäin mallintaa (kaksilulotteisella) konvoluutiolla

y(n,m) = h(n,m) * x(n,m),

missä x on todellinen näkymä, y on havaittu sumuinen kuva, ja h on linssin impulssivaste (nk. point spread function; PSF). Yhtälössä y ja h ovat tunnettuja, ja tehtävänä on ratkaista x. Ratkaisu löytyy taajuustasossa, koska

Y(n,m) = H(n,m) X(n,m),

joten (Matlabin syntaksilla ilmaistuna):

x(n,m) = ifft (Y(n,m) ./ H(n,m)).

Toisena esimerkkinä mainittiin kappaleen 6 esimerkki kameran liikkeen aiheuttamasta epäterävyydestä, ja havaittiin terävyyden paranevan yksinkertaisellakin dekonvoluutiolla (arvaamalla).

Dekonvoluutiosta on hyötyä yleisemminkin lineaarisen kanavan aiheuttaman häiriön poistossa. Jos tiedetään signaalin x kulkeneen kanavan h läpi, voidaan vastaanotetusta mittaustuloksesta ypäätellä x, jos meillä on joku käsitys kanavasta h. Esimerkkinä tästä mainittiin langattoman tiedonsiirtokanavan estimointi ja sen aiheuttaman vääristymän kompensointi.

Toinen menetelmän tuottama etu on että Fourier-muunnoksen (käytännössä FFT:n) avulla voidaan laskea konvoluutio kaavasta (Matlabin syntaksilla ilmaistuna):

conv(x,y) = ifft(fft(x) .* fft(y))

Luennon lopuksi käsiteltiin nopeaa Fourier-muunnosta eli FFT:tä, joka on vain nopeampi tapa toteuttaa diskreetti Fourier-muunnos (DFT). FFT perustuu signaalin jakamiseen lyhyempiin pätkiin, jotka muunnetaan jakamalla ne edelleen rekursiivisesti kahtia. Rekursio päättyy, kun muunnoksen pituus on 1, jolloin muunnosta ei tarvitse enää tehdä. 1-ulotteisen vektorin tapauksessa muunnosmatriisi on yksinkertaisesti F = [1], joka tarkoittaa pelkkää ykkösellä kertomista eikä sitä tarvitse tehdä. Lyhyemmistä vektoreista saadaan koostettua pidemmät vektorit kaavoilla (3.3) ja (3.4).