Lue ensin tällä sivulla olevat yleisohjeet. Tarkemmat tiedot löytyvät tehtäväkohtaisista ohjeista. Jokaiseen tehtävään on saatavilla oma zip-tiedosto, josta löytyvää koodia voit käyttää ratkaisujesi pohjana.

Yleiset ohjeet

Etsi paras tapa jakaa annettu kuva kahteen osaan: monokromaattiseen suorakulmioon ja monokromaattiseen taustaan. Tavoitteena on minimoida virheiden neliöiden summa.

Rajapinta

Tulosten tallentamista varten on määritetty seuraava tyyppi:

struct Result {
    int y0;
    int x0;
    int y1;
    int x1;
    float outer[3];
    float inner[3];
};

Toteuta seuraava funktio:

Result segment(int ny, int nx, const float* data)

Tässä data on värikuva, jossa on ny*nx pikseliä. Jokainen pikseli muodostuu punaisesta, vihreästä ja sinisestä värikanavasta. Taulukossa nimeltä data on yhteensä ny*nx*3 liukulukua.

Värikanavat on numeroitu 0 <= c < 3, x-koordinaatit 0 <= x < nx ja y-koordinaatit 0 <= y < ny. Väriarvo tallennetaan taulukkoon data[c + 3 * x + 3 * nx * y].

Haluttu tuloste

Result-tietueen ensimmäiset neljä kenttää ilmaisevat suorakulmion sijainnin. Suorakulmion vasen yläkulma on koordinaateissa (x0, y0), ja oikea alakulma koordinaateissa (x1-1, y1-1). Eli suorakulmion leveys on x1-x0 pikseliä ja korkeus y1-y0 pikseliä. Koordinaattien tulee täyttää ehdot 0 <= y0 < y1 <= ny ja 0 <= x0 < x1 <= nx.

Viimeiset kaksi kenttää ilmaisevat taustan ja suorakulmion värin. outer-kenttä sisältää taustan kolme värikanavaa ja inner-kenttä sisältää suorakulmion kolme värikanavaa.

Kohdefunktio

Kullekin pikselille (x,y) ja värikanavalle c määritetään virhe error(y,x,c) seuraavasti:

• Olkoon color(y,x,c) = data[c + 3 * x + 3 * nx * y].
• Jos (x,y) on suorakulmion ulkopuolella: error(y,x,c) = outer[c] - color(y,x,c).
• Jos (x,y) on suorakulmion sisäpuolella: error(y,x,c) = inner[c] - color(y,x,c).

Segmentoinnin kokonaiskustannus on virheiden neliöiden summa, eli summa luvuista error(y,x,c) * error(y,x,c) yli kaikkien 0 <= c < 3, 0 <= x < nx ja 0 <= y < ny.

Tehtävänä on löytää segmentointi, joka minimoi kokonaiskustannuksen.

Algoritmi

Tehtävissä IS2, IS4, IS6a ja IS6b käytetään algoritmia, joka kokeilee suorakulmion kaikki mahdolliset sijainnit 0 ≤ y0 < y1 ≤ ny ja 0 ≤ x0 < x1 ≤ nx ja valitsee niistä parhaan. Kutakin sijainnin arviointia varten suoritetaan kuitenkin vain O(1)-operaatioita. Siksi tarvitaan esikäsittelyä.

Tehtävässä IS9a kehitetään tehokkaampi algoritmi, jonka ei ainakaan tyypillisissä tapauksissa tarvitse kokeilla kaikkia mahdollisia suorakulmion sijainteja. Tehtävän IS9a ratkaisu arvioidaan rakenteellisen syötekuvan perusteella. Se saattaa muistuttaa esimerkiksi oikeaa valokuvaa, jossa jotkut sijainnit ovat toisia huomattavasti parempia.

Esimerkkejä

Näistä esimerkeistä näet, miltä oikeanlaisella toteutuksella segmentoidut (oikealla) näytekuvat (vasemmalla) näyttävät. Vie hiiri tuloskuvien päälle, jolloin näet segmentoinnin paremmin.

Yleisiä vinkkejä

Hahmottele ratkaisua ensin paperilla, jotta matematiikka varmasti täsmää. Ratkaisuun tarvitaan erittäin tehokas tapa selvittää parhaat sijainnit. On olemassa melko yksinkertainen ratkaisu, jossa kunkin mahdollisen sijainnin kohdalla tarvitsee tehdä vain muutama haku etukäteen lasketusta taulukosta ja muutama laskutoimitus, joiden perusteella sijainnin laatu selviää.

Muista, että keskiarvo minimoi neliösummavirheen.

Käytä inkluusio-ekskluusioperiaatetta arvojen summan nopeaan laskemiseen suorakulmion sisällä — jos esilasketusta taulukosta voi hakea oranssin ja sinisen summan, myös harmaan alueen summan voi laskea:

Saattaa olla hyödyllistä järjestää silmukat siten, että ulompi silmukka kokeilee eri suorakulmion kokoja, ja sisempi silmukka kokeilee suorakulmion kaikkia mahdollisia sijainteja. Siten sisimmässä silmukassa pitää vain pystyä vertaamaan mahdollisia sijainteja samankokoisille suorakulmioille. Kannattaa esilaskea kaikki mahdollinen sisimpien silmukoiden ulkopuolella.

Vinkkejä tehtävään IS9a