Tehtävä 3 - Kuva

Ruotsinkielinen tehtävänanto saatavilla osoitteessa: http://www.niksula.cs.hut.fi/~alipiain/tehtavat/kierros3/tehtava3sve.html

Huom! Viimeksi päivitetty 22-10-2013 16.37

Muutettu RoundTo-metodi Osatehtävään 1selkeyden vuoksi ClampTo-metodiksi. Kuvausta tehtävänannossa selkeytetty toteutuksen osalta.
Tarkennettu ylikuormituksen kuvausta.
ti 22.10.: Päivitetty FourierFilter-luokkaa. Muutos on tehty FFT-metodiin, jossa muutoksen kohteena ollut osio on kommentoitu pois. Jos siis olet edennyt tehtävässä jo tämän vaiheen yli ja saanut halutun toiminnallisuuden aikaiseksi, ei sinun tarvitse muuttaa ratkaisuasi.

Tässä ohjelmointitehtävässä lähestytään kuvan manipulaatiota kahdesta näkökulmasta. Aluksi kuvaa operoidaan paikka-avaruudessa, minkä jälkeen kuvalla operointia harjoitellaan myös taajuusavaruudessa.

Taustaa
Tehtävänanto

Osatehtävä - Abstrakti luokka Filter

Osatehtävä - Metodien kuormittaminen

Osatehtävä - Toimiiko oikein?

Osatehtävä - PixelFilter-luokka

Osatehtävä - FourierFilter-luokka

Osatehtävä - operateFilter-metodi taajuusavaruudessa

Osatehtävä - Lopuksi

Palautus
Arvostelu
Lähteet

Taustaa

Kuva on valon intensiteetin ja värin eri aallonpituuksien spatiaalinen (paikallinen) jakauma. Kuvasignaali on jatkuva-arvoinen funktio (analoginen kuva) tai koodattu merkkijono (digitaalinen kuva), joka taltioi kuvan intensiteetin ja värin paikan funktiona. [1] Kuvien käsittely tietokoneella vaatii digitoinnin, missä kuva muutetaan numeeriseen, tietokoneelle sopivaan, muotoon. Jokainen kuva-alkio, pikseli, kuvastaa alkuperäisen kuvan intensiteettiä ja väriä.

Paikka-avaruudessa kuvan operointi on melko yksinkertaista. Scalassa kuvien lukeminen ja luominen onnistuu helposti esimerkiksi Javan java.awt.image.BufferedImage-luokan avulla. Luokka tarjoaa metodit, joiden avulla päästään käsiksi yksittäisten pikselien väriarvoihin. Tämän luokan lisäksi tehtävässä käytetään apuna java.awt.Color-luokkaa, joka tarjoaa näppärän säiliön RGB-värille.

Fourier-muunnos

Fourier-muunnoksen avulla signaali voidaan esittää sini-funktioiden sarjana. Lähde: http://en.wikipedia.org/wiki/ File:Fourier_transform_time_and_frequency_domains_(small).gif

Taajuusavaruudessa kuvan käsittely aloitetaan muuttamalla kuva taajuusavaruuteen tekemällä Fourier-muunnos. Fourier-muunnoksen avulla kuva voidaan esittää sini- ja/tai cosini-muotoisten taajuuksien avulla. Fourier-muunnos ei varsinaisesti kuulu tämän kurssin sisältöön ja tarkemmin siihen päästään tutustumaan vasta myöhemmillä matematiikan kursseilla.

Fourier-muunnos (tässä 1-dimensioinen) on jatkuva funktio:

F(u) = ∫ ^∞ _-∞ f(x)e^-2πiux dx, missä

f(x) on signaali paikka-avaruudessa
F(u) on signaali taajuusavaruudessa

Kuvaa voidaan käsitellä taajuusavaruudessa ja se voidaan muuttaa takaisin paikka-avaruuteen käänteisellä Fourier-muunnoksella:

f(x) = ∫ ^∞ _-∞ F(u)e^+2πiuxdu

Koska tässä tehtävässä operoidaan rasterikuvilla (ja kuvan funktio ei siis ole jatkuva), on käytettävä Fourier-muunnoksen diskreettiä muotoa, jolla operoidaan yksittäisiä kuvapisteitä seuraavasti:

X_u = Σ ^M-1 _m=0 x_m ∙ e^-2πium/M

ja käänteisenä:

x_m = ¹—_MΣ ^M-1 _u=0 X_u ∙ e^2πium/M

Käänteisessä versiossa eksponentin etumerkin kääntymisen lisäksi kerrotaan lopputulos vielä 1/M:llä (kuvan tapauksessa leveyden käänteisluvulla. Kerroin voidaan myös yhtä hyvin sijoittaa käänteisen DFT:n sijaan normaaliversioon ilman, että lopputulos muuttuu.

Koska me operoimme kuvilla, jotka ovat kaksiulotteisia myös kaksiulotteiseen DFT:hen tutustuminen on aiheellista. Alla vastaavat versiot DFT:stä kaksiulotteisessa tapauksessa.

X_{(u, v)} = Σ Σ ^M-1 ^N-1 _m=0_n=0 x_{(m, n)} ∙ e^{-2πi(um/M + vn/N)}

ja käänteisenä:

x_{(m, n)} = ^1 1——_{M N}Σ Σ ^M-1 ^N-1 _u=0_v=0 X_{(u, v)} ∙ e^{2πi(um/M + vn/N)}

Koska käänteislukukerrointa voi siirtää käänteisen ja normaalin version välillä kunhan kokonaisuutena kertoimen arvo on sama, tämän tehtävän ratkaisussa jaamme kertoimen tasan kummallekin versiolle. Käänteisenä ratkaisua kerrotaan korkeuden käänteisluvulla ja normaaliversiossa kuvan leveyden käänteisluvulla.

Fourier-muunnoksen lisäksi tässä vaiheessa on aiheellista mainita myös Eulerin lause, joka huomattavasti helpottaa yllä olevien laskujen ratkaisua.

e^ix = cos x + i ∙ sin x

Muuttamalla DFT Eulerin yhtälön avulla helpompaan muotoon, ei tarvitse välittää Neperin luvusta tai sen eksponenttien laskemisesta.

Suurilla kuvilla tavallinen DFT (Discrete Fourier Transform) on kuitenkin hidas verrattuna rekursiiviseen FFT:hen (Fast Fourier Transform). FFT:ssä diskreetti Fourier-muunnos jaetaan jokaisella rekursion kierroksella kahteen (parilliseen ja parittomaan) DFT:hen. Jolloin esimerkiksi n:n arvolla 1024, DFT tarvitsee 1 048 476 laskuoperaatiota tuloksen laskemiseen, kun FFT ainoastaan 10 240.

Tässä harjoitustehtävässä laadittava ratkaisu perustuu Cooley-Tukey algoritmiin, josta sinun toteutettavaksi jää joitakin osia. Algoritmi toimii esimerkiksi ainoastaan kuvilla, joiden korkeus ja leveys ovat kahden potensseja — vastuullasi on varmistaa, että muunlaisia kuvia ei yritetä käyttää. Yksinkertaistettuna algoritmi toimii seuraavasti:

    jos kuvan korkeus ja leveys ovat kahden potensseja
      täytetään tulosmatriisi lähtömatriisin arvoilla bittikäännetyssä järjestyksessä (kts. Bit-reversal)
      suoritetaan sarakkeiden FFT
      suoritetaan rivien FFT
      jos FFT on käänteinen
        kerrotaan tulos leveyden käänteisluvulla
      muussa tapauksessa
        kerrotaan tulos korkeuden käänteisluvulla

Digitaalisen kuvan suotimet

Suotimella (engl. filter) tarkoitetaan laitetta tai prosessia, jonka avulla signaalista voidaan poistaa ei-toivottu komponentti tai ominaisuus. [2] Tässä tehtävässä paikka-avaruudessa operoitaessa suotimet toteutetaan matriiseina, joita operoidaan kuvaan pikseli kerrallaan. Taajuusavaruudessa operoitaessa suotimet voidaan rakentaa esimerkiksi niin, että taajuuksista suodatetaan tietyn korkuiset signaalit pois.

Paikka-avaruuden suotimet

Suotimet, jotka muodostetaan paikka-avaruutta varten voisivat näyttää esimerkiksi tältä:

	0.0 0.2 0.0
	0.2 0.2 0.2
	0.0 0.2 0.0

Matriisilla, joka voidaan Scalassa toteuttaa kaksiulotteisen taulukon avulla, kerrotaan jokaista pikseliä siten, että suotimen keskikohta tasataan pikselin kanssa. Tällöin kertomisen jälkeen pikselin uudeksi arvoksi tulee alkuperäisen arvon ja suotimen keskimmäisen alkion tulo summattuna ympäröivien pikselien tuloon vastaavien suotimen alkioiden kanssa. Jotta kuvan valoisuus ei muuttuisi, tulisi suotimen alkioiden yhteenlaskettu summa olla 1.

1) Alkuperäinen kuva.

2) Suodin. Kertoimena käytetty 1/13.

3) Tuloskuva suotimen jälkeen. Hiukan sumennettu (blurred) lopputulos.

Yllä olevassa esimerkissä ensimmäisessä kuvassa alkuperäinen kuva, johon käytetään keskellä olevaa suodinta ja lopputulokseksi saadaan oikealla oleva kuva. Huomaa, että tässä suotimessa alkioiden yhteenlaskettu summa on 13, jolloin lopputulos pitäisi jakaa vielä kolmellatoista tai vastaavasti muuttaa suodinta niin, että jokainen 1 muutettaisiin 1/13:ksi. Jos tuloskuvaa skaalaa riittävän suureksi, voi huomata, että reunoilla oleva muutaman pikselin levyinen kaistale on hiukan eri värinen viereisiin pikseleihin nähden. Tämä johtuu siitä, että tehtävässä suotimella operointia on helpotettu sen verran, että kuvan pikselien käsittely aloitetaan suotimen säteen päästä reunasta.

Taajuusavaruuden suotimet

Alla ensimmäisessä kuvassa on muokkaamaton kuva, jota käytämme tässä esimerkkinä. Kun ensimmäiselle kuvalle tehdään Fourier-muunnos, saadaan aikaiseksi toisen kuvan mukainen tuotos. (Todellinen tuloskuva näyttää oikeasti erilaiselta, tässä kulmat on siirretty keskelle luettavuuden parantamiseksi.) Toisessa kuvassa reunoilta keskelle siirryttäessä taajuudet ovat korkeasta matalampaan. Jolloin kun Fourier-muunnoksen jälkeen käytetään kolmannen kuvan mukaista suodinta, kaikki korkeat taajuudet, jotka ovat suotimessa mustalla alueella poistetaan kuvasta (kerrotaan nollalla) kun taas valkoisen alueen taajuudet jäävät koskematta (tai kerrotaan yhdellä). Lopputuloksena käänteisen FFT:n jälkeinen tuloskuva näkyy neljäntenä.

1) Alkuperäinen kuva.

2) Kuva FFT:n jälkeen.

3) Suodin, jolla kuvaa operoidaan.

4) Tuloskuva suotimen jälkeen.

Tehtävänanto

Tehtävässä tarvittavat luokat voit ladata kerralla zip-pakettina tästä: luokat.zip.

1. Osatehtävä - Abstrakti luokka `Filter`

Aluksi luomme abstraktin luokan Filter, joka tarjoaa myöhemmin tehtäville varsinaisille suodinluokille muutamia apumetodeja. Myöhemmin luotavia PixelFilter sekä FourierFilter luokkia varten luomme metodin applyFilter, joka ottaa parametreikseen BufferedImage tyyppisen kuvan sekä suotimen nimen palauttaen muokatun BufferedImage:n. Tässä jätämme metodin toteutuksen kuitenkin tyhjäksi ja huolehdimme varsinaisesta toteutuksesta Filter-luokan aliluokissa.

Aloitamme luomalla yksinkertaiset metodit getComponent ja clampTo, joista ensimmäinen palauttaa Color-luokan instanssista pyydetyn värikomponentin arvon ja jälkimmäinen pyöristää parametrina välitettävän luvun kahden muun parametrin määrittämälle välille. Metodit näyttävät siis seuraavalta:

   /**
   * Returns the specified RGB color component specified by component in color.
   * If component is not between [0, 2] zero is returned. 
   */
   protected def getComponent(color: Color, component: Int) : Float = {
     // ... your code here ...
   }
  
   /**
    * Assures that value is at the lowest lower and at the highest upper
    */
   protected def clampTo(lower: Float, upper: Float, value: Float) : Float = {
     // ... your code here ...
   }

getComponent-metodissa haluttu komponentti määritellään kokonaisluvulla välillä [0, 2], missä jokainen luku vastaa RGB-väriavaruuden komponenttia. Tarkista, että pyydetty komponentti on sallitulta väliltä. clampTo-metodin toteutuksessa kannattaa tutustua scala.Int-luokan tarjoamiin metodeihin.

2. Osatehtävä - Metodien kuormittaminen

Metodien kuormittaminen tarkoittaa useamman samannimisen, mutta parametreiltaan ja paluuarvoiltaan tai ainoastaan parametreiltaan eroavan metodin luomista yhden objektin/luokan käyttöön. Metodien allekirjoitusten (engl. method signature) on oltava toisistaan poikkeavat.

Tässä tehtävänä on luoda Filter-luokalle metodit imageToPixels sekä pixelsToImage kahdella eri allekirjoituksella. Jolloin toisia näistä käytetään PixelFilter-luokasta, joka käsittelee kuvapisteitä luokan Color avulla ja toiset jäävät FourierFilter-luokan käyttöön, jossa kuvapisteet on mallinnettu liukulukuja sisältävällä taulukolla. Tällainen rakenne sallii sen, että jos myöhemmin esimerkiksi PixelFilter-luokassa päädytään käyttämään kuvapisteiden esittämiseen liukulukutaulukkoa, siihen siirtyminen ei vaadi muutoksia kuin PixelFilter-luokassa.

Metodeja käytetään siihen, että tiedostosta luettu kuva saadaan helpommin käsiteltävämpään muotoon kaksiulotteisena taulukkona sekä palautettua takaisin taulukosta BufferedImage-olioksi, joka voidaan helposti esittää ruudulla tai tallentaa.

Luo siis seuraavanlaiset metodit:


   /**
    * Fills the target array with color information in image.
    */
   protected def imageToPixels(image: BufferedImage, target: Array[Array[Color]]) : Unit = { 
     // ... your code here ...
   }
   
   /**
    * Fills the target array with color information in image.
    */
   protected def imageToPixels(image: BufferedImage, target: Array[Array[Array[Float]]]) : Unit = { 
     // ... your code here ...
   }
   
   /**
    * Writes the contents of the pixels array to the BufferedImage in image returning the result.
    */
   protected def pixelsToImage(image: BufferedImage, pixels: Array[Array[Color]]) : BufferedImage = {
     // ... your code here ...
   }
   
   /**
    * Writes the contents of the pixels array to the BufferedImage in image returning the result.
    */
    protected def pixelsToImage(image: BufferedImage, pixels: Array[Array[Array[Float]]]) : BufferedImage = {
     // ... your code here ...
   }

Joudut tekemään kussakin metodissa silmukkarakenteen, joka käy läpi jokaisen rivin ja sarakkeen. FourierFilter-luokan imageToPixels-metodissa kannattaa hyödyntää juuri luotua getComponent-metodia sekä pixelsToImage-metodissa vastaavasti clampTo-metodia. Miksi metodien määrittelyn edessä on sana protected? Lue lisää näkyvyysmääreistä http://www.tutorialspoint.com/scala/scala_access_modifiers.htm

3. Osatehtävä - Toimiiko oikein?

Oman ratkaisun toimivuuden varmistamiseksi on suositeltava käytettävän aikaa vähintään jokaisen suuremman kokonaisuuden valmistuttua. Lähestymistapoja testaamiseen on monia aina testivetoisesta kehityksestä (kts. http://en.wikipedia.org/wiki/Test-driven_development), jolloin testit kirjoitetaan ennen varsinaista toteutusta, virheiden välttämiseen (kts. http://en.wikipedia.org/wiki/Cleanroom_software_engineering). Tällä kurssilla kannustetaan valitsemaan itselle sopivin tapa, ei välttämättä yllä jäljempänä mainittu, ja todella testaamaan omia ratkaisuja kunnolla ennen palautusta.

Tässä vaiheessa varmistamme, että juuri luotu Filter-luokka toimii kutakuinkin oikein. Luo Filter-luokan perivä FilterTest-luokka, johon kirjoitat testisi, sekä lataa itsellesi TestView-luokka. Riittää, että toteutat FilterTest-luokkaan ainoastaan yliluokassa esitellyn metodin applyFilter.

Kannattaa testata sekä Color-luokan että Array[Float]:n kanssa toimivia ratkaisuja. Tarvitset tähän kaksiulotteista (tai jälkimmäisessä tapauksessa oikeasti kolmiulotteista) taulukkoa, joiden käyttöön voit tutustua esimerkiksi täältä: http://www.tutorialspoint.com/scala/scala_arrays.htm. Kaksi- tai useampiulotteisen taulukon voi luoda ofDim-metodilla, jolle on määriteltävä säilöttävien alkioiden tietotyyppi sekä taulukon koko. 3x3x3-kokoinen kokonaislukuja sisältävä kolmiulotteinen taulukko voitaisiin tehdä siis seuraavasti:

   var cube = ofDim[Int](3, 3, 3)

Saat tarvitsemasi kokoiset taulukot selvittämällä kuvan koon BufferedImage-luokan tarjoamien metodien avulla.

Nyt pystyt testaamaan, että aikaisemmin tekemäsi Filter-luokan metodit toimivat oikein. Varmista, että silmukkasi käyvät kuvan jokaisen pikselin läpi, ja komponentin palautus sekä pyöristys toimivat oikein.

4. Osatehtävä - `PixelFilter`-luokka

Seuraavaksi tehdään ensimmäinen varsinainen suodinluokka, joka perii aikaisemmin rakennetun Filter-luokan. Luotava PixelFilter-luokka on tarkoitettu kuvien muokkaamiseen paikka-avaruudessa. Luokan tärkein ja ainoa ulospäin näkyvä metodi on Filter-luokassa jo mainittu toteutus applyFilter-metodista.

PixelFilter-luokka laaditaan niin, että luokan instanssin kautta voidaan kutsua applyFilter-metodia, jolla annetaan parametreina kuva, jota halutaan muokata sekä suotimen nimi (merkkijono), jolla kuvaa halutaan muokata. operateFilter-metodi huolehtii suodinten toteutuksesta ja applyFilter-metodi käyttää suodinta kuvaan.

Metodit `applyFilter` ja `operateFilter`

Toteuta applyFilter-luokan metodi PixelFilter-luokassasi. Aluksi metodissa on luotava rakenne kuvan tietojen säilömiseen kuten testiluokassakin. Tässä käytämme kaksiulotteista Color-olioita sisältävää taulukkoa. Tämän jälkeen tarvitsee ainoastaan muuttaa kuva käsiteltävän muotoon täyttämällä taulukko, kutsua kohta kirjoittamaamme operateFilter-metodia ja muuttaa taulukko takaisin kuvan muotoon.

Kuvien manipulaatiota varten luodaan operateFilter-metodi, joka ottaa parametreikseen ainakin kuvan tiedot sisältävän taulukon ja suotimen nimen. Metodin ei tarvitse palauttaa mitään.

operateFilter-metodin toiminta perustuu siihen, että parametrina välitetyn suotimen nimeen saadaan yhdistettyä oikea suotimena toimiva matriisi. Helpoiten tämä onnistuu match-rakenteen avulla. Kun oikea suodin on valmisteltu, käydään kuva läpi operoiden suodinta jokaiseen pikseliin.

match-rakenne on vain pieni osa Scalan tarjoamista hahmonsovitus- (engl. pattern matching) ominaisuuksista. Meille riittää merkkijonojen tunnistaminen ja toiminnan ohjaaminen sen mukaan. Perusrakenteeltaan siis tässä tehtävässä toteutetut match-rakenteet ovat seuraavanalaisia:

filterName match {
case "filter1" => // do something
case "filter2" => // do something else
}

Kussakin tapauksessa tehtäviä toimenpiteitä voi olla useita eikä niitä tarvitse sijoittaa samalle riville case kanssa. Voit tutustua tarkemmin erilaisiin hahmonsovitusominaisuuksiin täältä: http://www.tutorialspoint.com/scala/scala_pattern_matching.htm

Se, minkä nimisiä suotimet ovat, määritellään erillisessä tekstitiedostossa pixelfilter.txt, jonka lukemisesta huolehtii View-luokka, jonka voit ladata itsellesi tästä: View.scala . Voit laatia pixelfilter.txt tiedostosi itse ja sijoittaa sen itsellesi sopivaan paikkaan. Tiedostossa kukin suotimen nimi sijoitetaan omalle rivilleen — tämä nimi näkyy kuvaa muokkaavissa painikkeissa ja tämä nimi välitetään PixelFilter-luokalle sinun vertailtavaksi. Muista tarvittaessa muokata View-luokasta tiedostopolkuja. Voit tässä vaiheessa luoda myös fourierfilter.txt tiedoston, jotta sinun ei tarvitsisi muokata View-luokkaa muuten. Yksinkertaistettuna ohjelmarakenne on alla olevan kuvan mukainen.

Kuten jo aikaisemmin tuli mainittua, operateFilter-metodin toiminta tullaan rakentamaan match-rakenteen avulla. Ainoa ehdottoman pakollinen case on verrata original merkkijonoa vastaan. Tästä tapauksesta on hyvä aloittaa koko metodin tekeminen ja siirtyä eteenpäin vasta kun se toimii. Lisää tämä suotimen nimi pixelfilter.txt-tiedostoosi, jotta napin painallus saadaan yhdistettyä oikeaan toimintaan. Tapauksessa luotava suodin on 1x1-taulukko, jonka ainoassa solussa on arvo 1 (yksi). Suodinta varten on sopivinta käyttää liukulukuja (Float) sisältävää kaksiulotteista taulukkoa.

Suotimen määrittelyn jälkeen operateFilter-metodi, käy läpi parametrina annetun kuvataulukon jokaisen alkion kertoen jokaisen värikomponentin suotimella. Jotta saat tallennettua uudet arvot kuvataulukkoon Color-olioina, sinun tulee pyöristää kunkin komponentin arvo oikealle välille.

Suodinten laatiminen

Laaditaan aluksi kuvan valoisuutta muuttavat suotimet "darken" ja "lighten". Kuten "original", nämä suotimet ovat vain 1x1-taulukoita.

Oikealla olevasta kuvasta näet kuinka punaisen, vihreän ja sinisen väri muuttuu eri arvoilla. Jotta kuva vaalenisi, taulukossa olevan alkion arvon on oltava suurempi kuin 1 ja vastaavasti tummenemisen aiheuttaa arvo, joka on yhtä pienempi. Voit hakea sopivan tasapainon tässä itse kokeilemalla eri arvoja.

Seuraavaksi siirrytään hiukan hankalempiin ja monimutkaisempiin suotimiin. Kuvan valoisuuden muuttaminen on hyödyllistä, mutta joissain tapauksissa kuvan tarkkuuden muuttaminen voi lisätä suuresti kuvan arvoa.

Aloitetaan yksinkertaisemmasta, sumentavasta (engl. blur) suotimesta. Sumentaminen poistaa pieniä yksityiskohtia ja tasoittaa kuvaa. Yksinkertaisimmillaan sumentava suodin laskee pikselin uudeksi arvoksi ympäröivien pikselien keskiarvon. Tällöin kuvan siirtymät tasoittuvat ja kuvan terävyys vähenee. Sumentava suodin poistaa kuvasta kohinaa, mutta samalla menetetään myös eri värialueiden rajojen terävyys.

Tee sumentavasta suotimestasi itsellesi mieluisan tarkka. Muista alustuksessa esitellyt periaatteet; suotimet ovat leveydeltään parittomia, eli (3, 5, 7, jne.), symmetrisiä (leveys == korkeus) ja alkioiden summa on 1 (yksi). Mieti, millaisella matriisilla kertominen tuottaa pikselin uudeksi arvoksi ympäristön keskiarvon.

Sumennukselle vastakkaisena suotimena voidaan ajatella tarkentavaa suodinta, joka korostaa kuvan pieniä yksityiskohtia. Keskiarvoistamista vastaava operaatio on integraatio, mistä voidaan päätellä, että tarkennus voidaan saavuttaa derivoinnin avulla. Tässä tehtävä suodin perustuu toisen asteen derivaatalle, joka määritetään Laplacen yhtälön avulla. Matriisimuotoisena suotimena esitettynä pikselin uudeksi arvoksi tulee ympäröivien pikselien keskiarvo, kuten edellä, mutta pikselin alkuperäinen arvo korostuu. Käytettävä suodin on lisäksi edellisestä poiketen käänteinen ja perusmuodossaan seuraavanlainen.

   -1 -1 -1
   -1  8 -1
   -1 -1 -1

Huomaa, että alkioiden summa on nyt 0 (nolla). Kasvattamalla suotimen keskimmäisen kertoimen arvoa (pitäen samalla kokonaissumman 1:ssä) voit etsiä sopivasti tarkentavan suotimen.

Yllä laaditut suotimet ovat kaikki operoineet kuvalla RGB-avaruudessa, mutta esimerkiksi mustavalkoiseksi muuttavan suotimen rakentaminen näin on ongelmallista. OLO-tapauksessa esitelty HSB-avaruus (Hue, Saturation, Lightness) tarjoaa erilaisen värinmuodostusperiaatteen, jolla ongelma voidaan ratkaista. Tee nyt oma kuvan harmaasävyiseksi muuttava suodin.

Lisäksi (ei vaadita täysiin pisteisiin!) voit kokeilla rakentaa vielä tiettyyn suuntaan sumentavaa (motion blur), reunoja korostavaa (edges), tai tietyn värikomponentin poistavaa suodinta.

Sinulla pitäisi olla nyt toteutettuna vähintään 5 kuvaa manipuloivaa suodinta ja yksi kuvan alkuperäiseksi palauttava suodin. Tässä vaiheessa kannattaa katsoa toteutustasi ja pohtia onko se rakenteeltaan järkevä. Jos olet kirjoittanut kaiken toiminnallisuuden yhteen operateFilter-metodiin, saattaa olla viisasta miettiä selkeästi yhtä tehtävää tekevien tai toistuvien toimintojen erottamista omiksi metodeikseen.

5. Osatehtävä - `FourierFilter`-luokka

FourierFilter kuten PixelFilter on Filter-luokan aliluokka. Luokan rakenne vastaa myös spatiaaliavaruudessa operoivaa suodinluokkaa — luokan ainoa julkinen metodi on applyFilter, jonka toiminta on samankaltainen kuin PixelFilter-luokassa. Koska FourierFilter-luokka operoi kuvilla taajuusavaruudessa on kuitenkin käytettävä aikaisemman yhden taulukon sijaan, kahta taulukkoa kuvan tietojen säilömiseen. Toinen taulukoista on kuvan reaalisille komponenteille ja toinen imaginäärisille, jotka tulevat seurauksena Fourier-muunnoksesta. Lisäksi tarvitaan vielä toinen pari samanlaisia taulukkoja tulosten tallentamiseen.

applyFilter metodin toiminta etenee niin, että (1) ensin luodaan tarvittavat taulukot ja (2) täytetään kuvataulukon reaalisosaan alkuperäisen kuvan tiedot. Kuva (3) muutetaan sitten taajuusavaruuteen suorittamalla kaksiulotteinen FFT, (4) muutetaan tämän tulostaulukon indeksointia niin, että kulmat siirtyvät keskelle ja (5) operoidaan kuvaa suotimella. Lopuksi sama tehdään käänteisenä (6) siirtämällä reunat uudestaan keskelle ja (7) tekemällä käänteinen kaksiulotteinen FFT lopuksi (8) palauttaen saatu tuloskuva. Metodin toteutuksessa on oltava tarkkana mitä taulukkoa kulloinkin käytät.

Koska Fourier-muunnoksen toteuttamisen opettelu ei ole yksi tämän kierroksen tavoitteista, toteutat vain muutamia apumetodeja koko prosessista. Lataa itsellesi FourierFilter-luokka täältä: FourierFilter.scala.

Sinun tehtäväsi on toteuttaa seuraavat metodit(, mieluiten tässä järjestyksessä):

applyFilter

Toiminta, kuten kuvattu yllä. Muista käyttää apunasi Filter-luokan metodeja.

FFT2D

Algoritmin toiminta kuvailtu tehtävänannon alussa.

moveCornersToCenter

Siirtää parametrina annetun taulukon arvoja siten, että nurkissa olevat arvot asettuvat kuvan keskiosaan.
Tällöin esimerkiksi saavutetaan seuraava toiminta

saadaan seuraavaan muotoon →
Mieti siis, millaisella algoritmilla saat laskettua kuvapisteiden uudet sijainnit.

isPowerOfTwo

Apumetodi, joka palauttaa totuusarvon sen mukaan onko parametrina annettu kokonaisluku kahden potenssi. (kts. esim. avuksi: http://fi.wikipedia.org/wiki/Kahden_potenssit)
Tätä metodia tarvitset FFT2D metodin toteutuksessa.

bitReverseArray

Apumetodi, joka kääntää taulukon indeksit bittikäännettyyn järjestykseen.
Tätä metodia tarvitset FFT2D metodin toteutuksessa.

bitReverse

bitReverseArray-metodin apumetodi, jonka avulla lasketaan uudet indeksien arvot.

operateFilter

Metodi, joka operoi kuvalle suodinta taajuusavaruudessa.

Ennen kuin toteutat metodin operateFilter, kannattaa testata muun toteutuksen toimintaa luomalla suodin "none", joka esittää kuvan yksittäisen Fourier-muunnoksen jälkeen, eli kuten tehtävänannon alussa kuvassa 2. Yksinkertaisin tapa toteuttaa tämä toiminnallisuus on ohittaa applyFilter metodissa vaiheet 5-7 yksinkertaisella ehtolauseella. Kokeile toimintaa erikokoisilla kuvilla. Vasta kun tähän mennessä toteutettu toiminnallisuus toimii halutulla tavalla, kannattaa siirtyä eteenpäin.

6. Osatehtävä - `operateFilter`-metodi taajuusavaruudessa

Taajuusavaruuden käytön suurin etu on, että siinä operoidessa usein muuten monimutkainen operaatio (spatiaaliavaruudessa) muuttuu helpoksi. Huomaat pian, että tässä tehtävät suotimet ovat paljon yksinkertaisempia kuin aikaisemmin paikka-avaruutta varten tekemäsi.

Kuten aikaisemmin operateFilter-metodin toiminta perustuu match-rakenteeseen. Tässä tapauksessa ei kuitenkaan ole järkevää tallentaa suotimia omaan taulukkoon — huomaat pian miksi.

Fourier-muunnoksen jälkeen kuvassa matalin taajuus on kuvan keskellä (origossa). Ensimmäinen suotimemme, kolosuodin "notch", muuttaa ainoastaan kuvan matalimman taajuuden nollaksi. Muista tehdä muutos sekä reaali- että imaginääriosaan. Huomannet, että jo yhden pisteen muutos muuttaa koko kuvan valoisuutta.

Fourier-muunnettu testikuva.

Keinotekoinen testikuva.

Tarkastellaan seuraavaksi erästä erikoistapausta kolosuotimesta. Voit kokeilla näitä suotimia oikealla olevaan esimerkkikuvaan tai mihin tahansa säännöllisiä pysty- ja/tai vaakaelementtejä sisältävään kuvaan. Huomaa, kun kyseiselle kuvalle tehdään Fourier-muunnos, siitä on selkeästi havaittavissa säännöllisiä elementtejä kuten alkuperäisessäkin kuvassa on.

Kokeile nyt tehdä erikseen kolosuotimet "horizontal" ja "vertical", joissa nollaksi asetetaan vastaavasti taajuudet pysty- ja vaakasuunnassa kuvan keskikohdasta. (Jätä kuitenkin origo koskematta.) Mitä keinotekoiselle testikuvallemme tapahtuu kussakin tapauksessa? Onko tuloksissa jotain yllättävää?

Tosi kivoja suotimia, mutta mitä hyötyä tästä on? Kuvittele vaikkapa tilanne, jossa kuvassa on esimerkiksi skannauksen seurauksena aiheutunut koko matkalta järjestelmällinen raidoitus. Tällaisen kuvan korjaaminen on vastaavanlaisen suotimen avulla yksinkertaista. Kokeile esimerkiksi korjata keinotekoisesti vaurioitettua testikuvaa (alla oikealla). Et luultavasti saa virhettä täysin korjattua, sillä diagonaaliset viivat ovat niin leveitä, mutta saat parannettua lopputulosta ja jatkossa osaat ratkaista tilanteen.

Keinotekoisesti vaurioitettu testikuva.

Seuraavaksi tehdään alipäästö- (lowpass) ja ylipäästö- (highpass) suotimet, joista ensimmäinen poistaa kuvasta häiriöitä leikaten korkeat taajuudet pois ja jälkimmäinen säilyttäessään korkeat taajuudet säilyttää vain äärirajat. Esimerkin alipäästösuotimesta näit jo tehtävänannon alussa. Viimeistään tässä vaiheessa kannattaa muistella miten ympyrän yhtälö määritellään, jotta pystyt määrittämään haluamasi kokoisen alueen suodinten päästettäväksi. Kokeile erilaisilla arvoilla kumpaakin suodinta.

Huomaat, että lowpass-suotimen säteen kasvaessa tuloskuva muuttuu tarkemmaksi, jolloin toki suotimen vaikutus on myös pienempi. Huomaat myös, että kuvan tasaisille alueille muodostuu renkaita. Voit kokeilla päästä tästä efektistä eroon pehmentämällä suotimen rajaa, jolloin kerroin vaihtelee 0 ja 1 välillä origosta etäisyyden funktiona.

Highpass-suotimen kohdalla taas säteen kasvaessa näet yhä ohuempia reunoja. Huomaat, että myös highpass-suotimen kohdalla tietyssä vaiheessa muodostuu renkaita. Tämän voi korjata vastaavalla tavalla kuin aikaisemmin.

Tee vielä lopuksi suodin, joka yhdistelee kahta aikaisempaa — rengassuodin, joka ympyrämuotoisen alueen sijaan päästää läpi rengasmaisen alueen. Nollaksi asetetaan siis taajuudet kuvan reunoilta keskelle renkaan reunaan asti sekä origosta reunoille renkaan sisäkaareen asti. Kokeile eri levyisiä ja säteisiä renkaita saavuttaaksesi parhaan tuloksen.

Sinulla pitäisi olla nyt ainakin seuraavat suotimet; "notch", "vertical", "horizontal", "low", "high" ja "ring".

7. Osatehtävä - Lopuksi

Testaa vielä lopuksi kaikkien tekemiesi luokkien toiminta ja varmista, että kaikki toimii toivomallasi tavalla. Viimeistään tässä vaiheessa kommentoi koodisi ne pätkät, jotka saattavat olla vaikeaselkoisia. Jos jokin suodin toimii erityisen hyvin tietyn kuvan kanssa, kannattaa siitä mainita koodissa kommentein. Pakkaa koko ratkaisusi niin, että tarkistavan assistentin ei tarvitse ladata mitään muuta lisäksi ohjelman toimimiseksi. Laita siis palautettavaan pakettiin ainakin seuraavat tiedostot: Filter.scala, FourierFilter.scala, PixelFilter.scala, View.scala, fourierfilter.txt, pixelfilter.txt sekä kuvatiedostosi, jo(i)lla olet ohjelmasi toimintaa kokeillut. Nimeä palautettava pakettisi muotoon opnro_kierros3.zip.

Palautuksen jälkeen käy vielä vastaamassa palautteeseen osoitteessa: http://www.cs.hut.fi/cgi-bin/teekysely.pl?action=showform&id=studio1-scala3-2013&lang=FIN

Palautus

Tehtävän palautus tehdään aikarajaan lauantaihin 26.10. klo 18.00 mennessä Rubyric-järjestelmään. Myöhästyneestä palautuksesta seuraa 2 pisteen vähennys alkavaa vuorokautta kohden – eli esimerkiksi sunnuntaina klo 18.01 palautetun työn pisteistä vähennetään 4 pistettä.

Arvostelu

Ohjelmointitehtävät arvostellaan erillisten kriteerien mukaisesti. Tehtävän maksimipistemäärä on 60 pistettä ja hyväksytty suoritus on vähintään 30 pistettä.

Jos tehtäväpalautus on selvästi hyvin keskeneräinen ja se saa alle vaaditun hyväksytyn pistemäärän, se voidaan palauttaa tekijälle korjattavaksi (ns. bumerangi). Tehtävä on hyväksytty vasta, kun se on palautettu riittävän laajuisena ja syvällisenä. Bumerangina palautetusta tehtävästä voidaan antaa korjattunakin enintään minimipistemäärä 30.

Kannattaa kiinnittää huomiota koodin ja sisennyksen selkeyteen; jos assistentti näkee koodista selkeästi ajatuksenkulkusi, helpottaa se koodin toimivuuden ja vikatilanteiden vakavuuden arviointia. Kannattaa myös varmistaa, että palautettava koodi kääntyy ja että kyseessä on viimeisin versio harjoituksestasi.

Tehtävänannon täyttyminen - 25 pistettä

Jos tehtävänannossa kuvattua toiminnallisuutta puuttuu, ei suorituksesta voi antaa täysiä pisteitä. Karkeasti voisi arvioida, että puoleen osion pisteistä vaaditaan vähintään 50-prosenttisesti toteutettu tehtävänanto, ja 90-prosenttisesti oikein tehty tehtävä on suunnilleen 21-23 pisteen arvoinen.
Tehtävänantoa ei kuitenkaan ole pakko noudattaa orjallisesti – ohjeista poikkeaminen on sallittua, kunhan sen tekee hyvin perusteluin.

Toimivuus - 15 pistettä

Tämän kohdan arvosteluun vaikuttavat toteutettujen ratkaisujen oikeellisuus. Mikäli tehtävänannossa kuvattu toiminnallisuus on toteutettu puutteellisesti (esimerkiksi olennaisiin ongelmatilanteisiin ei ole varauduttu), seuraa pistevähennyksiä.

Järkevyys ja selkeys - 10 pistettä

Usein, saman asian voi toteuttaa monella tapaa, eikä yksi tapa välttämättä ole toisia parempi. Käyttäkää vapaasti luovuuttanne, mutta koettakaa pyrkiä myös eleganssiin – tehkää loppuun asti mietittyjä, helposti ymmärrettäviä ratkaisuja, välttäkää turhia koodirivejä elleivät ne selkiytä koodia.

Tyyli - 5 pistettä

Tähän kuuluvat muun muassa systemaattinen, oikeaoppinen sisennys, omien muuttujien ja metodien tarkoituksenmukainen nimeäminen sekä kommentointi siellä, missä se parantaa koodin ymmärrettävyyttä.

Yleisvaikutelma - 5 pistettä

Edellisten kohtien lisäksi työstä voi saada korkeintaan viisi lisäpistettä. Täydet pisteet saa moitteettomasta tai lähes moitteettomasta suorituksesta, neljästä kolmeen pistettä saa mikäli työssä on joitakin puutteita ("ihan ok"), 2-1 pisteen saaminen tarkoittaa jo merkittäviä erehdyksiä ja nolla pistettä tarkoittaa jo hyvin suuria puutteita työn sisällössä tai muodossa.

Lisäksi ohjelmointitehtävissä on mahdollista saada lisäpisteitä tehtävänannon ylittävästä suorituksesta

Lähteet

[1] Saarelma, Hannu. Kuvatekniikan perusteet. Otatieto. Oy Yliopistokustannus University Press Finland Ltd., Helsinki, 2003.
[2] Wikipedia. Filter (signal processing), 6.7.2013. Saatavilla: http://en.wikipedia.org/wiki/Filter_(signal_processing), viitattu 24.7.2013