S-114.240 Laskennallisen tekniikan seminaari

Rinnakkaislaskenta kuvankäsittelyssä

Saku Vainio 20.4.1999


1 Esipuhe

Tässä esityksessä käydään läpi joukko kuvankäsittelyn perusoperaatioita kuten kynnystys, histogrammi, erillaiset tavat suodattaa kuvaa, hough muunnos ja FFT/IFFT muunnokset. Pääpaino on näiden operaatioiden rinnakkaistamisessa ja helpohkon rinnakkaistumisen syiden tarkastelussa.

2 Perusasetelmat rinnakkaistamiselle

Kuvankäsittelyssä pyritään korostamaan, vahvistamaan ja suodattamaan kullekin ongelmatyypille tärkeitä piirteitä ja ominaisuuksia. Operoitavat kuvat ovat yleensä matriiseja vaikka muunlaisiakin kuvarakenteita on olemassa. Kuvankäsittelyn vaiheita esittää käytännönläheisesti kaavio konenäkö järjestelmästä (kuva 1). Ensimmäisessä vaiheessa on näytteiden kerääminen, joka tehdään kameralla. Seuraavaksi tehdään joukko matalan tason operaatioita joita voidaan toistaa iteroimalla jotta sopivat parametrit löydetään. Vaiheiden tarkoituksena on muokata raaka dataa ja jalostaa se korkeamman tason toiminnoille. Kuva 1. Konenäköjärjestelmän rakenne. Alun matalan tason operaatiot ovat hyvin yksinkertaisia esim: suodatusta, reunan etsintää ja valmiiseen malliin vertailemista. Näitä tehdään koko kuva alueelle niin, että tutkittava alue kerrallaan on hyvin pieni ja operaatiot ovat toisistaan riippumattomia. Kun matalantason esiprosessoinnit on tehty, voidaan datasta ruveta kaivamaan viivoja, ympyröitä ym. pirteitä ongelman vaatimuksista riippuen. Näihin tehtäviin käytetään Hough muunnosta joka on edelleen hyvin rinnakkaistuva. Joskus voi olla tarpeellista käsitellä dataa spatiaali tason (normaali kuva) sijasta taajuustasossa. Varsinkin suodatuksessa tähän voi tulla tarvetta. Operaatio toteutetaan normaaleilla 2-D FFT ja IFFT muunnoksilla, jotka rinnakkaistuvat hyvin. Kuvaavaa on, että prosessissa matalalla tasolla dataa on paljon ja operaatiot hyvin yksinkertaisia ja jopa naurettavan helposti rinnakkaistettavia. Kun lähestytään korkeamman tason operaatiota data jalostuu ja sen määrä vähenee samalla, kun dataa käsittelevät operaatiot muuttuvat monimutkaisemmiksi. Käsiteltävät näyttematriisit voivat olla esim: satelliiteilla hankittua korkearesoluutioisia kuvia kooltaan luokkaa 10 000 x 10 000 pixeliä joita on voitu koota pidemmältä aikaväliltä tarkasteltavaksi jolloin dataa voi olla suunnattomasti ja suoritukset ajetaan batch tyylisesti. Kuvat voivat olla myös realiaika toteutuksesta esim: liukuhihnalla tapahtuvaa ladunvalvonnasta jossa kuvan koko voi olla luokkaa 512x512 pixeliä ja kuvien ottonopeus 60-85 kuvaa/sekunnissa. Kummassakin tapauksessa vaaditaan suuria laskentatehoja vaikkakin hieman eri tyyppisiä. Tämän vuoksi kuvankäsittelyssä voidaan ja käytetään erikoislaitteistoja matalan tason operaatioiden toteuttamiseen. Erikoislaitteistot eivät kuitenkaan ole yhtä mukautuvia kuin rinnakkastietokoneet.

3 Matalan tason prosessit

Matalan tason prosessointi voidaan jakaa kolmeen eri luokkaan: * Piste (point processing) Käytetään vain yhtä pistettä uuden pisteen muodostamiseen. Naurettavan helppo rinnakkaistaa. * Paikalliset (local operations) Käytetään pistettä ja sen naapurustoa uuden pisteen muodostamiseen. Hyvin helppo rinnakkaistaa. * Globaalit (global operations) Käytettään koko kuva aluetta uuden pisteen muodostamiseen. Helppo rinnakkaistaa. Kuva 2. Esimerkki kuva lenna jota käytetään esimerkeissä.

3.1 Piste prosessointi

3.1.1 Kynnystys (thresholding)

Hyvin yksinkertainen tekniikka jolla voidaan helposti segmentoida alueita ainoastaan tutkimalla kuuluuko piste johonkin värialueeseen. Rinnakkaistaminen onnistuu vaikka antamalla jokaiselle pikselille oma prosessori. Esim: Kuvan segmentointi kahteen alueeseen. Kuva 3. Koodi kynnystystä varten. Kuva 4. Kynnystetty lenna.

3.1.2 Kontrastin venytys

Jos tutkittava data on jakaantunut hyvin pienelle värialueelle sen kontrasti on pieni ja siitä on vaikea nähdä mitään. Tällöin voidaan levittää kontrastia. Esim. Jos käytetty harmaa värialue on [0, 31] voidaan se levittää alueelle [0, 255] jolloin eri sävyjen väliset erot ovat suurempia. (Samalla tavalla voidaan tietysti myös kaventaa kontrastia.)

3.1.3 Histogrammi

Histogrammi kertoo kuinka värit ovat jakaantuneet kuvassa. Tekemiseen tarvitaan kaikki kuvan pisteet, mutta vain yksi piste kerrallaan. Histogrammi on hyvin hyödyllinen ja sitä voidaan käyttää hyväksi kynnystyksessä, kontrastin parantamisessa, etc. Rinnakkaistaminen onnistuu helposti kuten edellisissäkin tapauksissa. Lukolla ym. on kuitenkin pidettävä huoli, että eri prosessit eivät kirjoita histogrammitaulukkoon saman aikaisesti. Kuva 5. Koodi histogrammia varten. Kuva 6. lenna kuvan histogrammi [0,...,255].

3.2 Paikalliset operaatiot

Paikallisia operaatioita jotka tarvitsevat tiedon käsiteltävän pisteen naapureistaan ovat tasoitus (smoothing) jossa poistetaan korkeita taajuuksia, terävöittäminen (sharpening) jossa korostetaan korkeita taajuuksia ja häiriön poistaminen (noise reduction) jossa häiritseviä signaaleita vaimennetaan.

3.2.1 Keskiarvoistava suodatin

Yksinkertainen tapa tasoittaa kuva on laskea naapuruston keskiarvo pisteelle. Kuva 7. Pisteiden valinta 3x3 alueelta. Jos kuvassa esiintyy häiriöitä niitä ei saa hävitettyä pois keskiarvoistavalla suodattimella. Häiriöt ainoastaan leviävät ympäristöönsä. Rinnakkais SIMD (Single Instruction Multiple Data) toteutus keskiarvoistavasta suodatuksesta saadaan suoritettua neljässä vaiheessa: Kuva 8. Mean suodatuksen vaiheet. Vaihe 1 Lasketaan summa vasemman puoleisen pisteen kanssa. (x3+x4) Vaihe 2 Lasketaan summa oikean puoleisen pisteen kanssa. (x3+x4+x5) Vaihe 3 Lasketaan summa yläpuolen summan kanssa. (x3+x4+x5) + (x0+x1+x2) Vaihe 4 Lasketaan summa alapuolen summan kanssa. (x3+x4+x5) + (x0+x1+x2) + (x6+x7+x8)

3.2.2 Mediaani suodatin

Suodatin jolla yksittäiset suuret muutokset spatiaalitasosta saadaan poistettua. Idea on järjestää piste ja sen paikalliset naapurit jonoon suuruus järjestyksessä ja valita uusi x4 piste jonon keskeltä. Näin suurimmat ja pienimmät arvot jotka voivat olla häiriöitä eivät vaikuta muodostettavaan kuvaan. Jos häiriötä ei esiinny järjestetyn jonon keskimmäinen alkio on lähellä oikeaa arvoa. Yksinkertaisin toteutus on käyttää "buble sort" järjestämistä. Toteutus voidaan taas tehdä rinnakkaisesti useammalla prosessorilla 6:ssa vaiheessa: Kuva 9. Mediani suodatuksen vaiheet. (tarkastellaan yhtä naapurustoa) Vaihe 1 Vertaillaan vasemman sarakkeen alkioita keskimmäisen sarakkeen alkiohin ja muutetaan järjestystä jolleivat ole jo järjestyksessä. Vaihe 2 Vertaillaan keskimmäisen sarakkeen ja oikeanpuolen sarakkeen alkiota ja muutetaan järjestystä jolleivat ole jo järjestyksessä. Vaihe 3 Vertaillaan vasemman sarakkeen alkioita keskimmäisen sarakkeen alkiohin ja muutetaan järjestystä jolleivat ole jo järjestyksessä. Vaihe 4 Vertaillaan alimman rivin alkioita keskimmäisen rivin alkiohin ja muutetaan järjestystä jolleivat ole jo järjestyksessä. Vaihe 5 Vertaillaan keskimmäisen rivin alkioita ylimmän rivin alkiohin ja muutetaan järjestystä jolleivat ole jo järjestyksessä. Vaihe 6 Vertaillaan alimman rivin alkioita keskimmäisen rivin alkiohin ja muutetaan järjestystä jolleivat ole jo järjestyksessä. Tämä toteutus on hieman epätarkka, mutta kuitenkin riittävän tarkka vaikkakin kaikissa tilanteessa pisteeseen x4 ei aina päädy juuri keskimmäiseksi suurin arvo. Kuva 10. lenna suodatettuna 7x7 median suodattimella.

3.2.3 Painotetut maskit

Kun keskiarvoistavassa suodatuksessa suodattimen arvot olivat ykkösiä nyt nämä arvot ovat vaihdettavia. Laskenta suoritetaan liu'uttamalla maskia kuvan yli. Operaatioita on nimitetty spatiaali konvoluutioksi. Kuva 11. Laskenta 3x3 maskilla. Maskit voivat olla gaussisia maskeja melun poistoon: tai "meksikolais hattuja" kuvan tarkentamiseen. Rinnakkaistaminen on helppoa jakamalla kuva vaikka 4:lle prosessorille etc...

3.2.4 Reunan tunnistus

Moni hahmontunnistus tehtävä perustuu reunojen havaitsemiseen kun väritason muutokset ovat suuria. Gradientin suuruudella ja suunnalla seurataan väritaon intensitetin vaihteluja. Kuva 12. Gradientin suuruus ja suunta. Reunojen hakemiseen käytetään painotettuja maskeja. Maskin arvot aproksimoidaan gradientti lausekkeista ja tapoja toteutukseen on monia. Prewitt: Kuva 13a. Prewitt suodatin. Kuva 13b. Prewitt suodatin. Sobel: Kuva 14a. Sobel suodatin. Kuva 14b. Sobel suodatin. Kuva 15. Lenna suodatettuna sobel maskilla. Rinnakkaistaminen on taas helppoa toteuttaa kuten edellä ja koska maskit ovat riippumattomia toisistaan voidaan niitä ajaa saman aikaisesti. Laskennan tehokkuutta voi parantaa jättämällä "0" kertolaskut pois ja käyttämällä 4 vaiheen (kohta 3.2.1) laskutapaa painojen kera. Kolmas tapa valita maskille painot on laplace operaatio. Kuva 16. Laplace suodatin. Kun reunasuodattimet on ajettu käsitellään kuvaa tavallisesti vielä kynnystämällä kuva 0 ja 1 etc. arvoiksi. Tällöin päästään eroon mahdollisista heikoista/virheellistä reunoista ja kuvioiden tunnistus on selkeämpää.

3.3 Globaalit operaatiot

3.3.1 Hough muunnos

Kun kuva on esikäsitelty siitä voidaan ruveta etsimään kuvioita kuten viivoja, ympyröitä, ellisejä etc. Reunan etsintä suodattimien jäljiltä reunat eivät ole yhtenäisiä ääriviivoja vaan niissä on aukkoja. Muotojen löytämiseen tarvitaan robusti tapa. Hough muunnoksella etsitään kuviolle parametrit joilla kuvion sovittuminen kuvassa on todennäköisimmillään. Esimerkiksi viivan kuvaamiseen tarvitaan parametrit a ja b. Tällöin viivan kaava olisi muotoa: y=ax+b Tämä muoto ei ole kuitenkaan järkevä käyttää, koska kun viiva lähestyy pystysyoraa kasvaa a äärettömäksi. Siksi viivaa kuvataan kaavalla: r=x*cos(ang)+y*sin(ang) Kuva 17. Kuvautuminen parametripintaan. Yksittäisen pisteen kautta voi kulkea ääretön määrä suoria. Siksi parametrit r ja ang ovat diskreetejä vektoreita. Todennäköisimmän suoran etsimistä varten rakennetaan matriisi jossa on alkio jokaista r:n ja ang:n yhdistelmää varten. Kun kuvaa käydään läpi ja löydetään mahdollinen suora kasvatetaan sitä vastaavien parametrien alkiota matriisissa. Lopuksi todennäköisimpien suorien parametrit löytyvät matriisin suurimpien alkioden kohdista. Kuva 18. Rinnakkaistamaton pseudo koodi. Jaetun muistin järjestelmissä Hough muunnoksen rinnakkaistaminen on suoraviivaista. Näytteiden haut kuvasta ovat toisistaan riippumattomia jolloin tarvitaan ainoastaan lukuoperaatioita. Yhtäaikaiset haut kuvasta hidastavat kuitenkin prosessia jaetun muistin koneissa.

3.3.2 Muunnokset taajuusalueessa

Kuvat ovat signaaleja ja signaalien käsittely on kätevää taajuusalueessa. Erillaisia taajuusalueen operaatioita on lukemattomia, algoritmeja riittää. 2-D muunnos spatiaalitasosta taajuustasoon on kaksi-osainen muunnos. Ensiksi datalle lasketaan FFT (Fast Fourier Transform) rivi kerrallaan jonka jälkeen tuloksesta lasketaan jokaiselle sarakkeelle FFT joidenka jälkeen muunnos on valmis. Kuva 19. 2-D spatiaali -> taajuus tasoon muunnos geometrisesti. 2-D Muunnos on helposti rinnakkaistettavissa, mutta rinnakkaistus on jo käsitelty huolellisesti moduulisen ohjelmoinnin kohdalla. Vastaavassa muunnoksessa taajuustasosta spatiaalitasoon IFFT muunnoksessa vaihtuu vain kaavan potenssin etumerkki. Koska DFT (Discrete Fourier Transform) on hidas laskea kehitettiin FFT joka on huomattavasti nopeampi kuin DFT ja siksi FFT:tä käytetään laskentaan. FFT on myöskin hyvin rinnakkaistuva. FFT perustuu siihen, että 1-D muunnos voidaan hajottaa (N/2) parilliseen ja (N/2) parittomaan osaan: Kuva 20. Fourier muunnos kaava. Lasketaan 16 pisteen muunnos Binary Exchange algoritmilla. Yhteydet on järjestelty tavalla jota kutsutaa nimellä "butterfly." Kuva 21. Butterfly FFT. Butterfly kuvio kuvautuu hyperkuutioon ja laskettaessa datan/prosessorien hallinta on helppoa, koska prosessorien osoiteet on laskettavissa nykyisten prosessorien osoitteiden biteistä kunhan prosessorien ja muunnettavan datan määrät ovat 2:n potensseja. Toinen tapa laskea FFT jos prosessorit ovat 2-D ruudukossa voidaan algoritmi rakentaa niin, että kommunikointia tapahtuu vain vähän sarakkeiden kesken. Tätä nimitetään transpose algoritmiksi: Laskettaan 16 pisteen muunnos algoritmilla: Kuva 22a. Aluksi liikennettä on vain sarakkeen sisällä. Kuva 22b. Sarakkeiden kesken tapahtuu transponointi. Kuva 22c. Lopuksi liikennettä on vain sarakkeen sisällä.

4 Yhteenveto

Perustason kuvankäsittely rutiinit ovat hyvin rinnakkaistuvia. Syynä on, että operaatiot eivät ole keskenään toisistaan riippuvaisia vaan tarvitsevat ainoastaan dataa kuvasta. Operaatioiden tuloksen tallentamisia voidaan kuitenkin joutua kontrolloimaan lukoilla ja semaphoreilla, mutta nämä tilanteet ovat erittäin yksinkertaisia ja helposti hallittavia.
Lähteenä on käytetty: Barry Wilkinson, Michael Allen, Parallel Programming : Techniques and Applications Using Networked Workstations and Parallel Computers, Prentice Hall, 1998.