perjantai 25. huhtikuuta 2014

Oppivat järjestelmät

Tänään jatkettiin hahmontunnistusjärjestelmien opiskelua.

Aluksi muisteltiin edellisen viikon asioita lyhyesti, ja vilkaistiin mm. Matlab-demoa, jolla voidaan piirtää hiirellä projektiosuora kaksiulotteisen datan koordinaatistoon. Kun kaksi pistettä suoralta on merkitty, Matlab-skripti projisoi datan tälle suoralle ja piirtää tuloksena saatavien yksiulotteisten näytteiden jakauman sekä luokitteluprosentin. Hyvillä projektiosuorilla data oli täydellisesti luokiteltavissa, mutta huonoilla joukot menivät päällekkäin projisoinnin jälkeen. Fisherin lineaarinen erottelija laskee tämän suoran automaattisesti niin että erottelu on optimaalinen.

Seuraavaksi tutustuttiin tukivektorikoneeseen, ja tarkasteltiin lähemmin kernelitemppua. Kernelitemppu kuvaa näytteet korkeampiulotteiseen avaruuteen, jossa ne toivottavasti ovat paremmin eroteltavissa. Itse kuvausta ei kuitenkaan tarvitse käytännössä tehdä, vaan riittää korvata menetelmässä jokainen vektorien välinen sisätulo <x,y> jollain muulla funktiolla k(x,y). Tiettyjen reunaehtojen vallitessa voidaan osoittaa tämän olevan sama asia kuin kuvaus tiettyyn korkeampiulotteiseen avaruuteen ennen luokittelua. Periaatteessa tämä kyseinen kuvaus voidaan laskeakin, mutta yleensä se ei sinänsä ole kovin kiinnostavaa. Sen sijaan voidaan kokeilla erilaisia kerneleitä, ja katsoa millä niistä luokittelutulos on paras. Yleisesti käytettyjä kerneleitä ovat mm. polynomikernelit k(x,y) = (<x,y>)^n ja k(x,y) = (1 + <x,y>)^n sekä ns. RBF-kerneli k(x,y) = exp(-||x-y||).


Tämän jälkeen paneuduttiin hermoverkkojen opetukseen, ja mainittiin  lyhyesti opetusalgoritmin perustuvan derivaattaan ja ketjusääntöön. Näiden avulla voidaan päätellä suunta, jossa luokitteluvirhe pienenee jyrkimmin, ja kyseiset kaavat löytyvät esim. täältä. Perus- backpropagationin lisäksi on olemassa kehittyneempiä ja nopeampia opetusalgoritmeja, ja esim. Matlabissa niitä on lähes parikymmentä. Olennaisin ero algoritmien välillä on niiden nopeudessa ja muistin tarpeessa.

keskiviikko 16. huhtikuuta 2014

Sovelluksia: Kuvankäsittely ja hahmontunnistus

Tänään paneuduttiin kappaleeseen 11 (ks. kurssimonisteen liite), joka tarkastelee kuvankäsittelyä. Alkuosa koostuu enimmäkseen yksiulotteisten lineaaristen järjestelmien yleistyksestä kahteen ulottuvuuteen. Fourier-muunnoksen yhteydessä todettiin, että kaksiulotteinen tapaus voidaan toteuttaa kahden yksiulotteisen FFT:n avulla, mikä mahdollistaa nopean laskennan.
Tämän jälkeen tarkasteltiin dekonvoluutiota, eli konvoluution käänteistä operaatiota. Monisteen esimerkin lisäksi esimerkkinä mainittiin Hubble-avaruusteleskoopin varhainen ongelma, joka aiheutti kuvaan jonkin verran epätarkkuutta. Ennen kuin kiertoradalle päästiin korjaamaan linssi kuntoon, täytyi linssin virhe mallintaa konvoluution avulla. Varhaisia kuvia myös korjattiin dekonvoloimalla virheelliset kuvat. Linssi kuitenkin lopulta vaihdettiin, koska dekonvoluutio ei voi tuottaa yhtä täydellistä tulosta kuin fyysinen korjaus. Tämä johtuu siitä, että PSF ei koskaan ole täysin oikea, vaan siinä on numeerista epätarkkuutta. Lisäksi informaatiota saattaa kadota konvoluution yhteydessä, jos taajuustason funktiossa H(n,m) on nollia kertoimina.

Kappaleessa 6 on myös esimerkki liike-epätarkkuuden korjauksesta. Tästä aiheesta on myös esimerkiksi taannoin ollut hieno julkaisu hieno julkaisu SIGGRAPH-konferenssissa.

Toisen tunnin loppupuolella aloitettiin kappaletta 12, joka käsittelee hahmontunnistusta. Hahmontunnistusjärjestelmän ideana on esittää järjestelmälle näytteitä ja opettaa se tuottamaan oikea ulostulo kun sille esitetään opetusjoukkoon kuulumaton uusi näyte. Yksi oppivien järjestelmien osajoukko ovat luokittelijat, jossa ulostulo kertoo luokan johon esitetty näyte kuuluu.

Suosittuja luokittelualgoritmeja ovat ainakin seuraavat (kasvavan monimutkaisuuden järjestyksessä):
Näistä kolme ensimmäistä käsiteltiin luennolla. KNN on ideana yksinkertaisin: kaikki opetusdata pidetään muistissa ja uuden näytteen tullessa etsitään k samanlaisinta näytettä, ja valitaan näistä yleisin luokka. Tyypillisesti k on vajaan kymmenen luokkaa, mutta voi olla suurempikin; esim. 30. Mitä suurempi k on, sitä sileämpi luokkarajasta tulee. Vaikka KNN:n luokittelutulos onkin melko hyvä, on sen ongelmana suuri muistin tarve sekä laskennallinen kompleksisuus. Koko opetusjoukko täytyy nimittäin säilyttää muistissa, josta etsitään k lähintä naapuria jokaisen luokittelun yhteydessä. Sekä tilantarve että etsinnän vaatima aika voivat olla ongelmallisia jos opetusjoukossa on esim. 100000 alkiota.

Luentomonisteen seuraava menetelmä on Fisherin diskriminantti eli LDA. Tässä vilkaistiin mm. Matlab-demoa, jolla voidaan piirtää hiirellä projektiosuora kaksiulotteisen datan koordinaatistoon. Kun kaksi pistettä suoralta on merkitty, Matlab-skripti projisoi datan tälle suoralle ja piirtää tuloksena saatavien yksiulotteisten näytteiden jakauman sekä luokitteluprosentin. Hyvillä projektiosuorilla data oli täydellisesti luokiteltavissa, mutta huonoilla joukot menivät päällekkäin projisoinnin jälkeen. Fisherin lineaarinen erottelija laskee tämän suoran automaattisesti niin että erottelu on optimaalinen.

keskiviikko 9. huhtikuuta 2014

Signaaliprosessorit ja GPU

Tämänpäiväisellä luennolla käsiteltiin kappale signaaliprosessoreista. Tärkeimmät syyt niiden käyttöön ovat yksinkertaisuus, halvempi hinta sekä pienempi virrankulutus. Kuitenkin niistä saa riittävästi tehoa signaalinkäsittelyn tarpeisiin, koska alan tarvitsemat operaatiot ovat nopeita (kertolasku, yhteenlasku). Esimerkiksi FIR-suodatuksen tai kompressiossa käytettävän kaksiulotteisen DCT:n tarvitsemat kertolaskut ja yhteenlaskut voidaan pistetuloina laskea rinnakkain ns. MAC-operaation avulla. Vastaavia operaatioita on nykyisin myös tavallisissa prosessoreissa, ja ensimmäinen tällainen laajennus oli Intelin MMX-käskykanta vuodelta 1997.

Ensi viikon viikkoharjoituksissa koodataan FIR-suodin luokan TC303 signaaliprosessoreille. Olennaisimmat vaiheet olivat:
  1. Suodin suunniteltiin Matlabin fir1-rutiinilla.
  2. Kertoimet kopioitiin C-koodiin.
  3. C-kieliseen pohjaan kirjoitettiin for-silmukka, jossa kertoimet käydään läpi.
  4. Ulostulonäyte kirjoitetaan D/A-muuntimelle.
Vaiheessa 3 on kiinnitettävä huomiota circular buffering-tekniikkaan, jotta viitataan oikeisiin aiemmin sisään tulleisiin alkioihin.
Toisen tunnin loppupuolella luotiin katsaus GPU-laskentaan ja sen sovelluksiin koneoppimisessa. Esimerkkinä oli 1.2 miljoonan kuvan luokittelu tuhanteen luokkaan ns. konvoluutioverkolla. Tämä voidaan toteuttaa omalla koneellakin käyttäen pylearn2-pakettia.

keskiviikko 2. huhtikuuta 2014

Näytteenottotaajuuden muuntelu D/A-muunnoksessa

Tänään käytiin kappale 8 loppuun, tarkasteltiin interpoloinnin sovelluksia D/A-muunnoksen apuna. Aloitimme menetelmällä, jota käytettiin jo ensimmäisissä CD-soittimissa 1980-luvun alussa. Menetelmän ideana on tehostaa nollannen asteen pitopiirin toimintaa nostamalla näytteenottotaajuus korkeammaksi ennen pitopiiriä. Tämä näkyy aikatasossa porraskuvion hienontumisena ja tätä kautta pitopiirin virheen pienenemisenä jä siirtymisenä korkeammille taajuuksille. Taajuustasossa yli 22,05 hertsin taajuuksille tulee vastaavia heijastuksia kuin interpoloinnin yhteydessäkin. Erona on, että nyt heijastumat vaimenevat sitä enemmän mitä korkeammalle mennään. Digitaalinen interpolointi helpottaa näiden heijastusten poistamista: ilman digitaalista interpolointia tarvittavan analogisen suotimen siirtymäkaistan leveys olisi 2,05 kHz (20kHz...22.05kHz), kun esim. nelinkertaisella interpoloinnilla se saadaan yli 130 kHz:n levyiseksi (väli 20kHz...154,35 kHz).

Toinen, nykyisin yleisempi ratkaisu yksinkertaistaa analogiapuolta edelleen kvantisoimalla D/A-muunnettavan signaalin 1-bittiseksi. Ratkaisusta käytetään nimeä kohinanmuokkaus, englanniksi noise shaping tai sigma delta modulation. Kvantisointi onnistuu äänenlaatua heikentämättä, kun nostetaan näytteenottotaajuus ensin riittävän suureksi. Tällöin näytteiden suuri määrä kompensoi niiden heikkoa tarkkuutta. Pelkkä ylinäytteistys ei kuitenkaan vielä riitä: ilman muita temppuja näytteenottotaajuus pitäisi nostaa jopa miljardikertaiseksi, mikä ei käytännössä ole mahdollista. Siksi täytyy ottaa käyttöön alla olevan lohkokaavion mukainen takaisinkytkentä, joka aiheuttaa kvantisointivirheen siirtymisen korkeammille taajuuksille.


Korkeilla taajuuksilla kohina ei haittaa, koska se voidaan erottaa hyötysignaalista analogisella alipäästösuodatuksella D/A-muunnoksen jälkeen. Jäljelle jäävän kvantisointikohinan määrä voidaan laskea, ja havaitaan että suuruusluokassa 1500 oleva muunnoskerroin riittää (miljardien sijaan). Ratkaisua voidaan edelleen tehostaa tarkastelemalla korkeampiasteisia kohinanmuokkaimia, jotka siirtävät vieläkin tehokkaammin kvantisointikohinaa korkeammalle.

Jotkin audioformaatit kuten Super Audio CD tallentavat äänen suoraan yksibittisenä. Tästä on etuna se, että kohinanmuokkaus täytyy tehdä vain kerran äänitysstudiossa eikä jokaisessa kuluttajalaitteessa erikseen.

keskiviikko 26. maaliskuuta 2014

Näytteenottotaajuuden muuntelu

Tänään luennon aluksi vilkaistiin välikoetta sekä sen tuloksia.

Tämän jälkeen käsiteltiin alku kappaleesta "näytteenottotaajuuden muuntelu". Kappale tarkastelee menetelmiä, joilla voidaan muuntaa näytteenottotaajuus näytteistämisen jälkeen toiseksi. Perusoperaatiot ovat desimointi ja interpolointi, jotka toimivat kokonaislukukertoimilla. Näitä yhdistelemällä saadaan kaikki rationaalikertoimet. Molemmat operaatiot tarvitsevat alipäästösuodattimen, joka on yleensä FIR, ja suunnitellaan normaaleilla menetelmillä. Suotimen siirtymäkaistasta todettiin, että se laitetaan aina rajataajuuden alapuolelle. Näin signaaliin tulee vähemmän virhettä kuin jos laskostumista pääsisi tapahtumaan.

Desimoinnissa tapahtuva näytteenottotaajuuden pieneminen toteutetaan yksinkertaisesti jättämällä näytteitä pois tasaisin väliajoin. Esimerkiksi kertoimella kolme jätetään vain joka kolmas näyte jäljelle. Tämä kuitenkin aiheuttaa laskostumista, koska signaalin sisältämät taajuudet pysyvät samoina mutta näytteenottotaajuus pienenee. Tämä saadaan luonnollisesti estettyä suodattamalla signaali ennen alinäytteistämistä sopivalla alipäästösuotimella.

Interpolointi puolestaan koostuu nollien lisäämisestä sekä tämän operaation tuottamien roskien poistamisesta. Nollien lisääminenhän tuottaa kopioita ja peilikuvia alkuperäisestä spektristä, jotka voidaan myös poistaa kätevästi alipäästösuodatuksella.

Kappaleessa luodaan myös katsaus interpoloinnin ja desimoinnin yhdistämiseen, jolloin päästään yksinkertaisempaan rakenteeseen huomaamalla kokonaisuudessa olevan kaksi suodatinta peräkkäin, jotka molemmat poistavat tietyn kaistan ylätaajuuksilta. Näin ollen vain toinen niistä on tarpeellinen. Piirtämällä kuva näiden suodinten amplitudivasteista voidaan päätellä kumpi on tarpeeton (aina se, jota vastaava muunnoskerroin on isompi).

keskiviikko 19. maaliskuuta 2014

Äärellinen sanapituus

Tänään luento aloitettiin pikaisella ekskursiolla erääseen kuvankäsittelyongelmaan. Esimerkki perustui muutama vuosi sitten toteutettuun tutkimushankkeeseen, jossa tavoitteena oli löytää pienhiukkasia SEM-mikroskoopin kuvista. Demottu menetelmä korosti ensin mielenkiintoiset hiukkaset muotoon perustuvalla morfologisella tophat-muunnoksella, jonka jälkeen hiukkaset etsittiin Otsun kynnystyksellä. Löydetyistä kohteista karsittiin liian pienet pois Matlabin bwareaopen-funktiolla, ja lopuksi laskettiin jäljelle jääneiden kohteiden kokojakauma labeling-algoritmilla.

Kuva-analyysidemon jälkeen palattiin prujun aiheeseen. Muistelimme äärellisen sananpituuden vaikutusta A/D-muunnoksessa, ja osoitettiin että kvantisointikohinan odotusarvo on nolla ja varianssin yhtä kuin 2^(-2b) / 12.

Yllä olevaa kaavaa voidaan edelleen jalostaa signaali-kohinasuhteen käsitteeksi (SNR), joka kertoo signaalin tehon suhteessa kohinan tehoon. Kun kaavaa pyöriteltiin, havaittiin jokaisen ylimääräisen bitin (per näyte) nostavan SNR:ää kuudella bitillä.

Lopuksi johdettiin kaava varianssille suodatuksen jälkeen ja sekä tutkittiin suotimen kertoimien pyöristämisen vaikutusta. Tämähän täytyy tehdä aina kun suodin toteutetaan huonomman tarkkuuden alustalla kuin Matlab (esim. tällä 17-bitin DSP:llä).

Toisen tunnin lopuksi käsiteltiin alku kappaleesta "näytteenottotaajuuden muuntelu". Kappale tarkastelee menetelmiä, joilla voidaan muuntaa näytteenottotaajuus näytteistämisen jälkeen toiseksi. Perusoperaatiot ovat desimointi ja interpolointi, jotka toimivat kokonaislukukertoimilla. Näitä yhdistelemällä saadaan kaikki rationaalikertoimet. Molemmat operaatiot tarvitsevat alipäästösuodattimen, joka on yleensä FIR, ja suunnitellaan normaaleilla menetelmillä.

keskiviikko 12. maaliskuuta 2014

IIR-suodinten suunnittelu ja kvantisointi

Tänään luennon ensimmäisellä tunnilla tutkittiin Matlabin valmiita IIR-suodattimen suunnittelumenetelmiä.

Tässä yhteydessä muisteltiin ns. pole-zero-placement -suunnittelumenetelmää, jossa hiirellä sijoiteltiin napoja ja nollia yksikköympyrälle ja laskettiin näitä vastaava suodin. Alla olevassa kuvassa on eräs näin saatu napanollakuvio, jossa tavoitellaan alipäästösuodinta. Tätä vastaava amplitudivaste on seuraavassa kuvassa, jossa selvästi erottuu hyppäys ylös- tai alaspäin jokaisen lähellä kehää olevan navan tai nollan kohdalla. Alimmassa kuvassa on vielä esitetty siirtofunktion itseisarvo |H(z)|, josta saadaan keskimmäinen amplitudivasteen |H(exp(iw))| kuvaaja sijoittamalla exp(iw) lausekkeessa z:n tilalle. Edellä kuvattu menetelmä ei luonnollisestikaan ole kovin tarkka. 

Toisen tunnin aihe olikin täsmällisempi IIR-suodinten suunnittelu, joka käytiin melko yleisellä Matlab-komentojen osaamisen tasolla. Kappaleen ydin on koottu monisteen taulukkoon, jossa suodintyyppejä vertaillaan amplitudivasteen ominaisuuksien ja kertoimien määrän suhteen. Kertoimia tarvitaan eri menetelmillä 29+28, 13+12 ja 8+7 kappaletta. Suurin määrä tulee Butterworth-suotimella ja pienin elliptisellä suotimella. Kahden Chebyshev-suotimen kerroinmäärä on näiden kahden ääripään välissä. Vertailun vuoksi FIR-suotimen kertoimien määrä vastaavilla vaatimuksilla olisi N = [5.5/0.035] = 159 käytettäessä Blackman-ikkunaa.
 
Muita luennolla esiin tulleita seikkoja olivat mm.
  • Matlabin kerroinvektorit a ja b eivät ole suoraan käytettävissä ulostulon y(n) laskennassa, vaan takaisinkytkentäkertoimien (siis esim. termin y(n-1) kertoimen) merkki täytyy vaihtaa vastakkaiseksi.
  • Elliptisellä suotimella on aina vähemmän kertoimia kuin muilla. Lisäksi tasavärähtely-ominaisuus on yleensä hyvä asia.
IIR-suotimen etuna on siis pienempi kertoimien tarve. Haittapuolina mahdollinen epästabiilisuus sekä numeeriset ongelmat toteutuksessa. Tästä esimerkkinä mainittiin kurssin SGN-16006 signaaliprosessorityö, jossa täytyy toteuttaa IIR-suodin. Käytännössä yli toisen asteen IIR-suodinta ei voi toteuttaa numeeristen ongelmien vuoksi. Sen sijaan suodin täytyy jakaa peräkkäisiin toisen asteen lohkoihin esim. Matlabin TF2SOS-funktiolla.

Toisella tunnilla käsiteltiin äärellisen sananpituuden vaikutuksia. Meidän tarkastelussamme nämä ilmenevät A/D-muunnoksen yhteydessä sekä suodatettaessa äärellisellä laskentatarkkuudella. Pääpaino on ensimmäisessä tyypissä. Luennolla käsiteltiin näytteistyksessä käytettävät kvantisointitasot: esimerkiksi (1+7) bitin esityksessä käytettävissä ovat seuraavat 256 tasoa: -128/128, -127/128, ..., 0, ..., 126/128, 127/128. 
 
Pyöristettäessä lähimpään lukuun syntyvä kvantisointivirhe on aina välillä -1/256...1/256. Yleisesti pyöristys (1+b) bittiin aiheuttaa enintään virheen 2^(-b) / 2 suuntaan tai toiseen. Vasemmalla olevassa kuvassa on esimerkkitapaus jossa "seiska" kvantisoidaan 1+9 bittiin.

 
Seuraavaksi tätä yksinkertaista virhemallia käytettiin johdettaessa arvio virheen varianssille, joka on suoraan verrannollinen syntyvän kvantisointivirheen tehoon. Tätä kautta määritellään SNR, eli signaali-kohinasuhde, eli häiriöetäisyys. Tämä suure kertoo jotain äänenlaadusta, ja saatavia tuloksia tullaan tarvitsemaan kappaleessa 6, kun päätellään montako bittiä signaalista uskalletaan poistaa kompressiossa ilman äänenlaadun havaittavaa heikkenemistä.

Jos ehtojen oletetaan olevan voimassa, voidaan osoittaa kohinan odotusarvon olevan nolla ja varianssin yhtä kuin 2^(-2b) / 12.