Iriksentunnistusta ja z-muunnoksia

Ensimmäisellä tunnilla kuultiin Tapio Mannisen vierailuluento aiheesta "Iiris biometrisena tunnisteena". Esitys pohjautui Tapion kandityöhön, joka valmistui vuosi sitten. Sivumennen sanoen Tapio valmistui tekniikan kandidaatiksi "oivallisesti", mikä tarkoittaa keskiarvoa yli 4 ja kandityön arvosanaa vähintään 4 sekä automaattista 250 euron stipendiä TTY:ltä.

Iiriksentunnistus pohjautuu John Daugmanin kehittämään ja patentoimaan IrisCode-menetelmään. Algoritmi tunnistaa ensin iiriksen ja pupillin reunat sovittamalla niihin ympyrät. Näiden avulla iiriksen alue muunnetaan napakoordinaatistoon, ja saatu matriisi jaetaan edelleen 8x4 = 32 alueeseen. Kukin näistä alueista projisoidaan pistetulon avulla ns. Gabor-kantaan (suodatetaan Gabor-suotimilla). Puhutaan myös Gabor-muunnoksesta, mikä viittaa siihen että kyseessä on hieman viritetty versio Fourier-muunnoksen kaksiulotteisesta yleistyksestä (ks. myös prujun sivut 96-99). Näin jokaisesta alueesta jää jäljelle yksi kompleksiluku kutakin 32:a Gabor-aalloketta kohti. Tämän kompleksiluvun vaihe kvantisoidaan neljään arvoon, jotka voidaan kuvata kahdella bitillä. Kaikkiaan saadaan siis 32 x 32 x 2 = 2048 bittiä pitkä bittijono, joka toimii tunnisteena. Lopuksi pohdittiin kuinka päätellään kuvaavatko kaksi bittijonoa samaa silmää. Tässä oli apuna tilastomatematiikka niin, että arvioitiin jakaumat ns. Hamming-etäisyydelle samoille ja eri silmille. Näin voidaan arvioida virhepäätelmän todennäköisyyttä, mikä on olennainen osa järjestelmän myyntipuheita sekä sen lakiteknistä luotettavuutta (esim.: Loton päävoitto on todennäköisempi kuin että asiaton henkilö pääsee kulunvalvonnastamme sisään ilman lupaa.)

Laitoksella tehtyihin kanditöihin voi tutustua tämän linkin takana. Linkistä latautuu zip-tiedosto, joka on suojattu salasanalla. Tunnus on sgnkandi ja salasana motiivi.

Toisella tunnilla aloitettiin Z-muunnoksen käsittely. Luennoilla ehdittiin käsitellä z-muunnoksen määritelmä, sekä laskea napa-nollakuviot muutamille z-muunnoksille. Itse muunnoksen laskennan osalta ehdittiin tarkastella vain yleisimpien jonojen z-muunnokset, jotka löytyvät sivun 58 alalaidan taulukosta. Useimpien jonojen z-muunnokset voidaan palauttaa näiden tapausten yhdistelmiksi, joten kauhean paljon monimutkaisempia muunnoksia ei tarvitse osatakaan laskea.

Z-muunnos on myös diskreettiaikaisen Fourier-muunnoksen (DTFT; s. 38) yleistys, ja muuntaa signaalin kompleksifunktioksi. Määritelmissä on eroa vain summan sisällä olevassa lausekkeessa, joka Z-muunnoksen tapauksessa on z, ja DTFT:n tapauksessa exp(iw). Jos siis tiedetään signaalin Z-muunnos, saadaan DTFT yksinkertaisesti sijoittamalla z = exp(iw).

Erityisen mielenkiintoinen Z-muunnos on silloin kun muunnettavana on suotimen impulssivaste (joka on signaali siinä kuin mikä tahansa muukin). Tällöin muunnoksen tuloksesta käytetään nimeä siirtofunktio. Siirtofunktio on rationaalifunktio, jonka osoittajassa ja nimittäjässä on polynomi. Kun tämä lauseke tiedetään, saadaan Fourier-muunnos em. sijoituksella. Tulos H(exp(iw)) on nimeltään taajuusvaste, ja siihen menee sisään reaaliluku w (taajuus josta ollaan kiinnostuneita), ja ulos tulee kompleksiluku. Tämän kompleksiluvun itseisarvo kertoo kuinka suuri vahvistus suotimella on kyseisellä taajuudella.

Kirjallisuudessa suotimista puhutaan yleensä niiden z-muunnoksen kautta. Pikainen haku tuottaa esim. tämän artikkelin, jossa esim. kaava (12) tekee juuri näin. Muistan itse ennen signaalinkäsittelyn opintojani saaneeni tehtäväksi toteuttaa suotimen

H(z) = 1 / (1 - z^-1 + 0.5 z^-2).

Ohjaajani näki jakolaskut C-kielisessä koodissa, ja sanoi: ei näin. Ensi viikolla nähdään miten tämä suodin pitäisi toteuttaa. Jakolaskuja toteutuksessa ei kuulu olla.

Kaiken kaikkiaan asia oli tänään varsin matemaattista. Jos tämä ahdistaa sinua, niin ensi viikolla helpottaa.

Välikoe

Kurssin ensimmäinen välikoe oli eilen, ja assareilta kuulin, että sitä oli pidetty haastavana. Välikoejärjestelmä on vielä melko uusi laitoksellamme, ja kysymyksetkin näin ollen melko uusia. Tenttiä vartenhan kysymykset tuppaavat tulemaan prujun loppupuolelta materiaalin kumulatiivisen luonteen vuoksi. Viime vuonnakin välikoetta pidettiin vaikeana, mutta useat saivat silti täydet pisteet.

Kysymykset löytyvät kurssin sivuilta. Tässä muutamia kommentteja niistä.

1. Ykköstehtävän oikea rivi on E, T, E, E, T, E.
2. a) 2 x 10 kHz = 20 kHz. b) Fs on nyt 1/0,00125 Hz = 800 Hz. Prujun sivun 4 alalaidan kuvan perusteella 500 Hz laskostuu nyt taajuudelle 300 Hz. c) Samanlainen kuin harkkatehtävä 2.12.
3. a) Ratkeaa matriisimuunnoksella, ja tulos on [1, -5+2i, 5, -5-2i]. b) Vaikeinta lienee termin y(2-n) muunnoksen laskenta. Tämä saadaan ratkaisemalla ensin y(-n):n muunnos (joka on sama kuin Y, mutta kaikki omegat miinusmerkkisiksi), ja tämän jälkeen lisäämällä kahdella siirron vaikutus (eli lausekkeen y(-n + 2) muunnos). y(2-n):n muunnos on siis exp(2iw) Y(exp(-iw)). x(n-1):n muunnoksen laskenta on helppoa, samoin kuin konvoluution, joka muuttuu Fourier-puolella kertolaskuksi. Päässälaskien sanoisin että kysytty lauseke on exp(2iw) Y(exp(-iw)) exp(-iw) X(exp(iw)), joka vielä vähän sieveneekin. Lauseketta en tällä merkistöllä saa näkyviin. Sivumennen sanoen, x(n) on jono 0.1^n * u(n) ja y(n) = 1, kun n=-5,...,5 ja nolla muulloin (tai lyhyemmin: y(n) = u(n+5) - u(n-6)).
   
4. a) Samanlainen kuin tehtävä 2.17. b) Askelvaste voidaan päätellä kuten harkkatehtävässä 2.18 tehtiin. h(n) saadaan yksinkertaisesti sijoittamalla arvot.
5. a) Impulssivasteen arvot ovat [0.3, -1.2, 1.0, 0.3] välillä n=0,...,3, ja muualla nollia. b) Tässä voidaan käyttää sivun 22 konvoluution ominaisuuksia, joista luennolla piirrettiin kuvatkin. Oikea vastaus on h(n) = h1(n) * h2(n) + h3(n).

Välikokeiden tarkastamisessa menee ehkä parisen viikkoa. Ilmoittautuneita oli reilu 200.

Diskreetti Fourier-muunnos ja FFT

Tänään käsiteltiin Fourier-muunnos (kappale 3) loppuun. Myös ensi viikon välikokeen alue on kappaleen kolme loppuun. Kannattanee vilkaista myös seuraavat viikkoharjoitukset, koska ne käsittelevät samaa asiaa.

Ensimmäisellä tunnilla tarkasteltiin 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ästä mainittiin kaksi sovellusta. Ensimmäinen niistä 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))

Toisena esimerkkinä oli dekonvoluutio, eli kysymys mikä olisi konvoluutiolle käänteinen operaatio. Jos siis tiedetään h ja y yhtälöstä

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

niin kuinka voidaan ratkaista x(n)? Ratkaisu löytyy taajuustasossa, koska

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

joten

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

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

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).

Fourier-muunnos

Tänään luennolla käsiteltiin alkupuoli Fourier-muunnoksesta. Ennen itse asiaa demottiin oskilloskooppia, jossa oli myös spektrianalysaattoritoiminto, ja laite laski taajuusjakaumaa Fourier-muunnoksen avulla reaaliajassa.

Fourier-muunnoksen idea on kysyä paljonko eri taajuuksia annetussa signaalissa on. Taululla oli alla olevan piirroksen kaltainen kuva. Kuvan "yhtälössä" vasemmalla oleva signaalin pätkä jaetaan eri taajuuksiin kysymällä paljonko tarvitaan vakiotaajuutta (0.3 kpl), paljonko kerran värähtävää siniä (0.6 kpl), jne. Sama idea on kaikkien neljän muunnostyypin takana, mutta erona on montako eri taajuutta tarvitaan muodostamaan alkuperäinen signaali. Joissain tapauksissa niitä tarvitaan äärettömän paljon, jolloin kuvan summan sijaan tarvitaan integraali.

Jatkuvat tapaukset perustuvat siis integraalin laskentaan, ja käytännössä tämä täytyy tehdä muunnostaulukoiden avulla. Käsin laskettavien kolmen ensimmäisen muunnostyypin jälkeen tutustuttiin lopuksi diskreettiin Fourier-muunnokseen, joka voidaan esittää matriisimuunnoksena. Muunnosmatriisi muodostetaan lisäämällä rivi kerrallaan ykkösen n:nnen juuren eri potensseja. Ensimmäisellä rivillä potenssit hyppivät nollan askeleen välein, toisella yhden askeleen, kolmannella kahden, jne. Idea käy ehkä ilmi parhaiten sivun 41 alimman matriisin kautta. Matriisissa olevien lukujen päättelyssä auttaa graafinen tulkinta: wN on yksikköympyrällä kulmassa 1/N oleva luku, ja sen potenssit saadaan vaihekulman monikertoina. Alla oleva kuva esittää kuinka tapauksen N = 4 muunnosmatriisi päätellään yksikköympyrältä.