Algoritmin kehityskaari

Ryhmästämme valikoitui sovelluksen tarvittavien algoritmien kehittäjiksi Ville ja Niko. Valinta sujui melko luonnollisesti, kun Ville oli jo omatoimisesti aloittanut kuvanvakautuksen kehittämistä ja Niko on ryhmän ainut matematiikan opiskelija. Lähdimme siitä, että kaikki algoritmit kehitetään itse, jolloin oppiminen maksimoituu, koska tilannetta pitää tarkastella huomattavasti tarkemmin kuin, jos olisimme kopioineet valmiita algoritmeja. Kehityksessä lähdimme liikkeelle ohjaajamme Tuomas Auran kuvanvakautukseen liittyvästä vinkistä – rivi- ja sarakesummien hyödyntäminen.  

Jotta sovelluksemme avulla pystyttäisiin lähettämään ja vastaanottamaan viestejä kännykän salamavalolla ja kameralla, täytyi meidän etsiä ratkaisut seuraaviin kysymyksiin:

•  miten yksittäisestä kuvasta voidaan löytää kaikki valonlähteet (erityisesti kännykän salamavalo),

• miten pystytään yhdistämään havaitut valonlähteet aiemmin havaittuihin, ja

• miten viestit tulisi koodata, jotta vastaanottaja pystyisi dekoodaamaan sen oikein?

Ensiksi näistä kysymyksistä lähdettiin etsimään vastausta ensimmäiseen kysymykseen, sillä se on helpoiten lähestyttävissä – videon käsittelyn sijasta voidaan käsitellä yksittäisiä kuvia.

Valoja metsästämässä

Ville aloitti kehityksen C++:lla Computer Graphics –kurssilta valmiina olevaan frameworkiin ja Niko aloitti koodaukset MATLABilla. Ensimmäisenä ideana oli tunnistaa valot kuvasta laskemalla x- ja y-suunnan histogrammit ja tunnistaa niistä lokaalit maksimit. Näin saatiin aikaan nopea, mutta jokseenkin epätarkka valojen tunnistus kuvasta. Ongelmia tässä toteutuksessa olivat virheelliset tunnistukset ja suuret valonlähteet, jotka saattoivat hukuttaa etsimämme kännykän salamavalon. Tätä toteutusta onnistuttiin parantamaan etsimällä valonlähteitä vain sinisestä värikanavasta ja varjojen leikkaamisella, jolla hävitetään kaikki keskisävyjen vaikutukset kuvasta. Tämä versio toimi hyvin erityisesti pimeässä, mutta päivänvalossa etäällä olevan salamavalon tunnistus osoittautui mahdottomaksi valonlähteen pienen koon takia.

Varjojen leikkaaminen yksinkertaistaa kuvaa.

Valoiksi tunnistetut kohdat kuvassa.

Intohimoisena tavoitteenamme oli saada toimiva sovellus ympäristöstä riippumatta, jolloin ensimmäinen algoritmi valojen löytämiseksi ei ollut tarpeeksi tarkka. Koska aiemmin oli jo analysoitu, että kännykän salamavalon avulla ei pystytä lähettämään viestejä kovinkaan nopeasti, päätimme keskittyä algoritmien nopeuden sijasta niiden tarkkuuteen. Ville keksi, että voisimme laskea kuvasta niin kutsutun summataulukon, jolloin voisimme nopeasti laskea jonkin kuvan alueen keskimääräisen valoisuuden. Tämä antoi kohtuullisen tehokkaan tavan tarkastella jokaisen yksittäisen kuvan pikselin kohdalla, onko sen ympäristössä valonlähde, vaiko ei. Yllätyimme, että tämä algoritmi oli edelleen melko nopea ja samalla jokainen valonlähde löytyi todella luotettavasti.  

To be continued…