2D-konvoluutio kuvankäsittelyssä

Tämässä artikkelissa kerrotaan kaksiulotteisesta konvoluutiosta ja nollatäytteestä digitaalisen kuvankäsittelyn kannalta.

Edellisessä artikkelissani ”Parempi näkemys DSP:stä: konvoluutiosta oppiminen” käsittelin konvoluutiota ja sen kahta tärkeätä sovelluskohtaa signaalinkäsittelyn alalla. Siinä signaaleja pidettiin oletettavasti yksiulotteisina spatiaalialueella. Konvoluutioprosessi voidaan kuitenkin toteuttaa myös moniulotteisilla signaaleilla.

Tässä artikkelissa yritämme ymmärtää paremmin kaksiulotteisen konvoluution prosessia ja seurauksia, joita käytetään laajasti kuvankäsittelyn alalla.

Kaksiulotteisen konvoluution määritelmä

Konvoluutiota, jossa on mukana yksiulotteisia signaaleja, kutsutaan 1D-konvoluutioksi (1D-konvoluutioksi) tai vain konvoluutioksi. Jos taas konvoluutio suoritetaan kahden signaalin välillä, jotka ulottuvat kahta toisiaan vastaan kohtisuorassa olevaa ulottuvuutta pitkin (eli jos signaalit ovat luonteeltaan kaksiulotteisia), siitä käytetään nimitystä 2D-konvoluutio. Tätä käsitettä voidaan laajentaa koskemaan moniulotteisia signaaleja, minkä ansiosta voimme käyttää moniulotteista konvoluutiota.

Digitaalisella alueella konvoluutio suoritetaan kertomalla ja kumuloimalla päällekkäisten näytteiden hetkelliset arvot, jotka vastaavat kahta tulosignaalia, joista toinen on käännetty. Tämä 1D-konvoluution määritelmä pätee myös 2D-konvoluutioon, paitsi että jälkimmäisessä tapauksessa toinen tulosignaaleista käännetään kahdesti.

Tällaista operaatiota käytetään laajalti digitaalisen kuvankäsittelyn alalla, jossa kuvaa edustava 2D-matriisi konvolvoidaan verrattain pienemmällä matriisilla, jota kutsutaan 2D-ytimeksi.

Esimerkki 2D-konvoluutiosta

Kokeillaan laskea kuvassa 1 esitetyn 5×5-kokoisen kuvamatriisin x konvoluutiosta 3×3-kokoisella ytimellä h saadun lähtökuvan pikseliarvo.

Kuva 1: Tulomatriisit, joissa x edustaa alkuperäistä kuvaa ja h ydintä. Kuvan on luonut Sneha H.L.

Vaiheittainen menettely, jota noudatetaan, on esitetty seuraavassa.

Vaihe 1: Matriisien käänteistäminen

Tässä vaiheessa ydintä käännetään vaikkapa rivejä pitkin ja sen jälkeen sarakkeita pitkin, kuten kuvassa 2 on esitetty.

Kuva 2: Kuvallinen esitys matriisin inversiosta. Kuvan on luonut Sneha H.L.

Tuloksena alkuperäisen ytimen jokaisesta (i,j)-osasta tulee uuden matriisin (j,i)-osa.

Vaihe 2: Liu’uta ydintä kuvan yli ja suorita MAC-operaatio kullakin hetkellä

Liikuta invertoitua ydintä kuvan yli etenemällä pikseli kerrallaan.

Laskekaa kullakin kerralla toistensa kanssa päällekkäisten pikseleiden tulo ja laskekaa niiden summa. Tulos on lähtöpikselin arvo kyseisessä kohdassa. Tässä esimerkissä muiden kuin päällekkäisten pikselien arvoksi oletetaan ’0’. Keskustelemme tästä tarkemmin seuraavassa luvussa ”Nollatäytteistäminen”.

Tässä esimerkissä aloitamme ytimen liu’uttamisen ensin sarakkeittain ja etenemme sitten rivejä pitkin.

Pikselit rivi kerrallaan

Kattaamme ensin ensimmäisen rivin kokonaan ja etenemme sitten toiselle riville, ja niin edelleen ja niin edelleen.

Tässä prosessissa ensimmäinen päällekkäisyys ytimen ja kuvan pikseleiden välillä syntyisi, kun ytimen oikeassa alakulmassa oleva pikseli osuu kuvamatriisin vasemmassa yläkulmassa olevan ensimmäisen pikselin arvoon. Molemmat pikseliarvot on korostettu ja esitetty tummanpunaisella värillä kuvassa 3a. Lähtökuvan ensimmäinen pikseliarvo on siis 25 × 1 = 25.

Seuraavaksi siirretään ydintä samalla rivillä yhden pikselin verran eteenpäin. Tässä vaiheessa ytimen matriisin kaksi arvoa (0, 1 – esitetty tummanpunaisella fontilla) ovat päällekkäin kuvan kahden pikselin kanssa (25 ja 100 kuvattu tummanpunaisella fontilla), kuten kuvassa 3b on esitetty. Tuloksena oleva pikselin lähtöarvo on siis 25 × 0 + 100 × 1 = 100.

Kuva 3a, 3b. Konvoluutiotulokset, jotka on saatu lähtöpikseleille sijainnissa (1,1) ja (1,2). Kuvan on luonut Sneha H.L.

Kuvat 3c, 3d: Konvoluutiotulokset, jotka on saatu lähtöpikseleille sijainnissa (1,4) ja (1,7). Sneha H.L:n luoma kuva

Etenemällä samalla tavalla voidaan laskea kaikki lähtökuvan ensimmäisen rivin pikseliarvot. Kaksi tällaista esimerkkiä, jotka vastaavat lähtömatriisin neljättä ja seitsemättä tulostuspikseliä, on esitetty kuvissa 3c ja 3d.

Jos liu’utamme ydintä edelleen samaa riviä pitkin, yksikään ytimen pikseleistä ei ole päällekkäinen kuvan pikseleiden kanssa. Tämä osoittaa, että olemme valmiit nykyistä riviä pitkin.

Liikkuminen pystysuunnassa alaspäin, eteneminen vaakasuunnassa

Seuraavaksi etenemme pystysuunnassa alaspäin yhden pikselin verran ennen kuin aloitamme uudelleen liikkumisen vaakasuunnassa. Ensimmäinen päällekkäisyys, joka tällöin tapahtuisi, on kuvassa 4a esitetty, ja suorittamalla MAC-operaatio niiden päälle saamme tulokseksi 25 × 0 + 50 × 1 = 50.

Tämän jälkeen voimme liu’uttaa ydintä vaakasuunnassa, kunnes ytimen ja kuvamatriisien välillä ei ole enää päällekkäisiä arvoja. Yksi tällainen tapaus, joka vastaa lähtömatriisin kuudetta pikseliarvoa (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200), on esitetty kuvassa 4b.

Kuvat 4a, 4b. Konvoluutiotulokset, jotka on saatu ulostulopikseleille paikoissa (2,1) ja (2,6). Kuvan on luonut Sneha H.L.

Tätä yhden askeleen alaspäin siirtymistä, jota seuraa vaakasuora skannaus, on jatkettava kuvamatriisin viimeiseen riviin asti. Kuvissa 5a-c on esitetty kolme satunnaista esimerkkiä, jotka koskevat pikselilähtöjä paikoissa (4,3), (6,5) ja (8,6).

Kuva 5a. Lähtöpikseleille (4,3) saadut konvoluutiotulokset. Kuvan on luonut Sneha H.L.

Kuva 5b. Konvoluutiotulokset, jotka on saatu lähtöpikseleille kohdassa (6,5). Sneha H.L.

Kuva 5c. Konvoluutiotulokset, jotka on saatu lähtöpikseleille kohdassa (8,6). Sneha H.L.

Vaihe

Luotu kuva

Vaihe

Siten tuloksena saatava lähtömatriisi on:

Kuva 6. Esimerkkimme tuloksena syntyvä ulostulomatriisi. Kuvan on luonut Sneha H.L.

Nollatäytteistäminen

Kaksiulotteisen konvoluution matemaattinen muotoilu saadaan

$$$ y\left=\sum_{m=-\infty}^\infty\sum_{n=-\infty}^\infty h\left \cdot x\left $$$

jossa, x edustaa tulokuvamatriisia, joka konvolvoidaan ytimen matriisin h kanssa, jotta saadaan uusi matriisi y, joka edustaa lähtökuvaa. Tässä indeksit i ja j koskevat kuvamatriiseja, kun taas indeksit m ja n koskevat ytimen matriiseja. Jos konvoluutiossa käytettävän ytimen koko on 3 × 3, indeksit m ja n ovat välillä -1-1. Tässä tapauksessa, esitetyn kaavan laajennuksen tuloksena saadaan

$$$ y\left=\sum_{m=-\infty}^\infty h\left \cdot x\left + h\left \cdot x\left \\\ + h\left \cdot x\left $$

$$ y\left= h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \\\ + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \\\ + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \cdot x\left $$

Tämä osoittaa, että jokaisen ulostulopikselin saamiseksi, on suoritettava 9 kertolaskua, joiden tekijät ovat kuvan ja ytimen päällekkäisiä pikselielementtejä. Kun kuitenkin laskimme arvon ensimmäiselle tulostuspikselillemme, suoritimme vain yhden kertolaskun (kuva 3a jäljennettynä kuvaan 7a). Mitä tämä tarkoittaa? Tarkoittaako se epäjohdonmukaisuutta 2D-konvoluution yhtälömuodon kanssa?

Ei oikeastaan. Koska yhdeksän tuotostermin yhteenlaskulla saatu tulos voi olla yhtä suuri kuin yhden termin tulo, jos kahdeksan muun tuotostermin yhteisvaikutus tasoittuu nollaan. Yksi tällainen tapa on tapaus, jossa kukin kahdeksan muun termin tulo arvioi itsensä nollaksi. Esimerkkimme yhteydessä tämä tarkoittaa, että kaikkien ei-ylittävästi (kuvan ja ytimen välillä) olevia pikseleitä vastaavien tuotostermien on muututtava nollaksi, jotta kaava-laskennan tulokset olisivat yhtä suuret kuin graafisen laskennan tulokset.

Matematiikan alkeistietämyksestämme tiedämme, että jos vähintään yksi kertolaskuun osallistuvista tekijöistä on nolla, myös tuloksena oleva tuote on nolla. Tämän analogian avulla voimme todeta, että esimerkissämme tarvitsemme nolla-arvoisen kuvapikselin, joka vastaa jokaista ydinmatriisin ei-ylittyvää pikseliä. Kuvallinen esitys tästä olisi kuvan 7b mukainen. Yksi tärkeä huomioitava asia on, että tällainen nollien lisääminen kuvaan ei muuta kuvaa missään muussa mielessä kuin sen koon osalta.

Kuva 7: Nollatäytteen lisääminen kuvan ensimmäiselle pikselille (minun piirtämäni)

Tämä ylimääräisten nollien lisääminen tunnetaan nimellä nollatäytteen lisääminen (zero padding, nollatäytteinen lisäys), ja se on tehtävä jokaisessa sellaisessa tapauksessa, jossa ei ole yhtään sellaista kuvapikseliä, joka olisi päällekkäin ytimessä olevien pikselien kanssa. Esimerkissämme nollatäytettä on lisättävä jokaiselle pikselille, joka sijaitsee kahdella ensimmäisellä rivillä ja sarakkeella sekä kahdella viimeisellä rivillä ja sarakkeella (nämä pikselit on merkitty sinisellä fontilla kuvassa 8). Yleisesti ottaen nollatäytteistettävien rivien tai sarakkeiden lukumäärä tulokuvan kummallakin puolella on (rivien tai sarakkeiden lukumäärä ytimessä – 1).

Kuva 8

Yksi tärkeä asia on mainittava, että nollatäytteistäminen ei ole ainoa tapa käsitellä konvoluution tuomia reunavaikutuksia. Muita pehmustustekniikoita ovat esimerkiksi replicate padding, periodic extension, mirroring jne. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Yhteenveto

Tämän artikkelin tarkoituksena on selittää 2D-konvoluution graafista menetelmää ja nollapehmustuksen käsitettä digitaalisen kuvankäsittelyn kannalta.

Hyväksyttävää.