2D konvolúció a képfeldolgozásban

Ez a cikk betekintést nyújt a kétdimenziós konvolúcióba és a nullapadozásba a digitális képfeldolgozás szempontjából.

Az előző, “Jobb betekintés a DSP-be: a konvolúció megismerése” című cikkemben a konvolúciót és annak két fontos alkalmazását tárgyaltam a jelfeldolgozás területén. Ott a jeleket feltehetően egydimenziósnak tekintettük a térbeli tartományban. A konvolúció folyamata azonban többdimenziós jeleken is végrehajtható.

Ebben a cikkben megpróbáljuk jobban megérteni a kétdimenziós konvolúció folyamatát és következményeit, amelyet széles körben használnak a képfeldolgozás területén.

A 2D konvolúció definíciója

Az egydimenziós jeleket érintő konvolúciót 1D konvolúciónak vagy egyszerűen konvolúciónak nevezzük. Ellenkező esetben, ha a konvolúciót két, egymásra merőleges két dimenzió mentén terjedő jel között végezzük (azaz ha a jelek kétdimenziósak), akkor 2D konvolúciónak nevezzük. Ez a fogalom kiterjeszthető többdimenziós jelek bevonására, aminek köszönhetően többdimenziós konvolúcióról beszélhetünk.

A digitális tartományban a konvolúciót a két bemeneti jelnek megfelelő, egymást átfedő minták pillanatnyi értékeinek szorzásával és felhalmozásával végezzük, amelyek közül az egyiket megfordítjuk. Az 1D konvolúciónak ez a definíciója a 2D konvolúcióra is alkalmazható, kivéve, hogy az utóbbi esetben az egyik bemeneti jelet kétszer megfordítjuk.

Ezt a fajta műveletet széles körben használják a digitális képfeldolgozás területén, ahol a képet reprezentáló 2D mátrixot egy viszonylag kisebb, 2D kernelnek nevezett mátrixszal konvolválják.

Egy példa a 2D konvolúcióra

Kíséreljük meg kiszámítani a kimeneti kép pixelértékét, amely az 5×5 méretű x képmátrix 3×3 méretű h kernellel való konvolúciójából származik, az alábbi 1. ábrán látható módon.

1. ábra: Bemeneti mátrixok, ahol x az eredeti képet, h pedig a kernelt jelöli. A képet Sneha H.L.

Az alábbiakban vázoljuk fel a lépésről lépésre követendő eljárást.

1. lépés: Mátrix inverzió

Ez a lépés a kernel felfordítását jelenti, mondjuk a sorok mentén, amit az oszlopok mentén történő felfordítás követ, amint az a 2. ábrán látható.

2. ábra: A mátrixinverzió képi ábrázolása. A képet Sneha H.L.

Az eredeti mátrix minden (i,j)-edik eleme az új mátrix (j,i)-edik elemévé válik.

2. lépés: Csúsztassuk a kernelt a képen, és minden pillanatban végezzük el a MAC műveletet

Az invertált kernelt csúsztassuk át a képen, pixelről pixelre haladva.

Minden esetben számítsuk ki az egymást átfedő pixelek szorzatát, és számítsuk ki az összegüket. Az eredmény lesz a kimeneti pixel értéke az adott helyen. Ebben a példában a nem átfedő pixelekről feltételezzük, hogy értéke “0”. Ezt részletesebben a következő, “Nulla kitöltés” című fejezetben tárgyaljuk.

A jelen példában először oszloponként kezdjük a kernel csúsztatását, majd a sorok mentén haladunk előre.

Pixelek soronként

Először az első sort fedjük fel teljesen, majd haladjunk a második sor felé, és így tovább és így tovább.

A folyamat során az első átfedés a kernel és a kép pixelei között akkor keletkezne, amikor a kernel jobb alsó szélén lévő pixel a képmátrix bal felső szélén lévő első pixel értékére esik. A 3a. ábrán mindkét pixelérték ki van emelve és sötétvörös színnel látható. A kimeneti kép első pixelértéke tehát 25 × 1 = 25 lesz.

A következőkben lépjünk előre a kernelben ugyanazon sor mentén egyetlen pixellel. Ebben a szakaszban a kernelmátrix két értéke (0, 1 – sötétpiros betűtípussal ábrázolva) átfedésben van a kép két pixelével (25 és 100 sötétpiros betűtípussal ábrázolva), amint az a 3b. ábrán látható. Így az eredményül kapott kimeneti pixelérték 25 × 0 + 100 × 1 = 100 lesz.

3a, 3b ábra. Az (1,1) és (1,2) helyen lévő kimeneti pixelekre kapott konvolúciós eredmények. A képet Sneha H.L. készítette

3c., 3d. ábra: Az (1,4) és (1,7) helyen lévő kimeneti képpontokra kapott konvolúciós eredmények. A Sneha H.L.

Hasonlóan haladva a kimeneti kép első sorának összes pixelértéke kiszámítható. A kimeneti mátrix negyedik és hetedik kimeneti pixelének megfelelő két ilyen példa a 3c. és 3d. ábrán látható.

Ha tovább csúsztatjuk a kernelt ugyanazon sor mentén, a kernelben lévő pixelek egyike sem fedésben van a képen lévő pixelekkel. Ez azt jelzi, hogy a jelenlegi sor mentén végeztünk.

Függőlegesen lefelé mozogni, vízszintesen előrehaladni

A következő lépés az lenne, hogy függőlegesen lefelé haladunk egyetlen pixellel, mielőtt újra elkezdenénk a vízszintes mozgást. Az első átfedés, amely ekkor bekövetkezne, a 4a. ábrán látható, és a MAC műveletet végrehajtva rajtuk; az eredmény a következő: 25 × 0 + 50 × 1 = 50.

Ezt követően vízszintes irányban csúsztathatjuk a magot, amíg nincs több átfedés a kernel és a képmátrixok között. Egy ilyen eset, amely a kimeneti mátrix hatodik pixelértékének (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) felel meg, a 4b. ábrán látható.

4a., 4b. ábra. A (2,1) és (2,6) helyen lévő kimeneti pixelekre kapott konvolúciós eredmények. Sneha H.L.

Az egy lépéssel lejjebb lépés, majd a vízszintes pásztázás folyamatát a képmátrix utolsó soráig kell folytatni. Az 5a-c. ábrákon három véletlenszerű példa látható, amelyek a (4,3), (6,5) és (8,6) helyeken lévő pixelkimenetekre vonatkoznak.

5a. ábra. A (4,3)-nál lévő kimeneti képpontokra kapott konvolúciós eredmények. A képet Sneha H.L. készítette.

5b. ábra. A (6,5)-nél lévő kimeneti pixelekre kapott konvolúciós eredmények. Sneha H.L.

5c. ábra. A (8,6)-nál lévő kimeneti pixelekre kapott konvolúciós eredmények. A Sneha H.L. által létrehozott kép

Lépés

Az eredményül kapott kimeneti mátrix tehát:

6. ábra. Példánk eredő kimeneti mátrixa. A képet Sneha H.L. készítette.

Nulla kitöltés

A 2-D konvolúció matematikai megfogalmazása a következő

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

hol, x a bemeneti képmátrixot jelöli, amelyet a h kernelmátrixszal kell konvolválni, hogy egy új y mátrixot kapjunk, amely a kimeneti képet képviseli. Itt az i és j indexek a képmátrixokkal, míg az m és n indexek a kernel mátrixaival foglalkoznak. Ha a konvolúcióban részt vevő kernel mérete 3 × 3, akkor az m és n indexek -1-től 1-ig terjednek. Ebben az esetben, a bemutatott képlet kiterjesztése a

$$ 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 $$

Ez azt jelenti, hogy minden kimeneti pixelhez, 9 szorzást kell elvégezni, amelyek faktorai a kép és a kernel átfedő pixelelelemei. Miközben azonban kiszámítottuk az első kimeneti képpontunk értékét, csak egyetlen szorzást végeztünk (3a. ábra a 7a. ábra replikációjaként). Mit jelent ez? Jelent-e ez ellentmondást a 2D konvolúció egyenletformájával?

Nem, nem igazán. Ugyanis a kilenc terméktétel összegzésével kapott eredmény akkor lehet egyenlő egyetlen terméktétel szorzatával, ha a másik nyolc terméktétel együttes hatása kiegyenlítődik nullával. Ilyen például az az eset, amikor a másik nyolc terminus minden egyes szorzata önmagát nullának értékeli. Példánk kapcsán ez azt jelenti, hogy a nem átfedő (a kép és a kernel közötti) pixeleknek megfelelő összes terméktételnek nullává kell válnia ahhoz, hogy a képlet-számítás eredménye megegyezzen a grafikus számítás eredményével.

Elemi matematikai ismereteinkből tudjuk, hogy ha a szorzásban részt vevő tényezők közül legalább egy nulla, akkor a kapott termék is nulla. Ezzel az analógiával megállapíthatjuk, hogy példánkban a kernelmátrix minden nem átfedő pixelének megfelelő nulla értékű képpixelre van szükségünk. Ennek képi ábrázolása a 7b. ábrán látható módon történne. Egy fontos dolog, amit itt észre kell venni, hogy a képhez hozzáadott nullák semmilyen értelemben nem változtatják meg a képet, kivéve a méretét.

7. ábra: A kép első képpontjának nullás kitöltése (saját rajz)

Az extra nullák hozzáadásának ezt a folyamatát nullás kitöltésnek nevezik, és minden olyan esetben el kell végezni, amikor nincsenek a kernel képpontjaival átfedő képpontok. A mi példánkban a zérófeltöltést minden egyes olyan pixel esetében el kell végezni, amely az első két sor és oszlop mentén helyezkedik el, valamint azoknál, amelyek az utolsó két sor és oszlop mentén jelennek meg (ezek a pixelek a 8. ábrán kék betűtípussal vannak jelölve). Általánosságban a bemeneti kép mindkét oldalán nullázandó sorok vagy oszlopok számát a (sorok vagy oszlopok száma a kernelben – 1) adja meg.

8. ábra

Egy fontos dolog, amit meg kell említeni, az az, hogy a nullázás nem az egyetlen módja a konvolúció által kiváltott élhatások kezelésének. Egyéb kitöltési technikák közé tartozik a replikációs kitöltés, a periodikus kiterjesztés, a tükrözés stb. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Összefoglaló

Ez a cikk a 2D konvolúció grafikus módszerét és a nulladik kitöltés fogalmát kívánja ismertetni a digitális képfeldolgozással kapcsolatban.