2D konvoluce ve zpracování obrazu

Tento článek poskytuje vhled do dvourozměrné konvoluce a nulování s ohledem na digitální zpracování obrazu.

V mém předchozím článku „Better Insight into DSP: Learning about Convolution“ jsem se zabýval konvolucí a jejími dvěma důležitými aplikacemi v oblasti zpracování signálu. Tam byly signály pravděpodobně považovány za jednorozměrné v prostorové oblasti. Proces konvoluce však může probíhat i na vícerozměrných signálech.

V tomto článku se pokusíme lépe pochopit proces a důsledky dvourozměrné konvoluce, která se hojně využívá v oblasti zpracování obrazu.

Definice 2D konvoluce

Konvoluce zahrnující jednorozměrné signály se označuje jako 1D konvoluce nebo jen konvoluce. V opačném případě, pokud se konvoluce provádí mezi dvěma signály rozprostírajícími se podél dvou na sebe kolmých rozměrů (tj. pokud jsou signály dvourozměrné povahy), pak se bude označovat jako 2D konvoluce. Tento pojem lze rozšířit tak, aby zahrnoval vícerozměrné signály, díky čemuž můžeme mít vícerozměrnou konvoluci.

V digitální oblasti se konvoluce provádí násobením a akumulací okamžitých hodnot překrývajících se vzorků odpovídajících dvěma vstupním signálům, z nichž jeden je převrácený. Tato definice 1D konvoluce je použitelná i pro 2D konvoluci s tím rozdílem, že v druhém případě je jeden ze vstupů převrácen dvakrát.

Tento druh operace se hojně využívá v oblasti digitálního zpracování obrazu, kdy se 2D matice reprezentující obraz konvolvuje s relativně menší maticí zvanou 2D jádro.

Příklad 2D konvoluce

Pokusíme se vypočítat hodnotu pixelu výstupního obrazu, který je výsledkem konvoluce obrazové matice x o velikosti 5×5 s jádrem h o velikosti 3×3, znázorněné na obrázku 1 níže.

Obrázek 1: Vstupní matice, kde x představuje původní obraz a h představuje jádro. Obrázek vytvořil Sneha H.L.

Pro dosažení tohoto cíle je níže uveden postup krok za krokem, který je třeba dodržet.

Krok 1: Inverze matice

Tento krok zahrnuje převrácení jádra například podél řádků, po kterém následuje převrácení podél jeho sloupců, jak je znázorněno na obrázku 2.

Obrázek 2: Obrázkové znázornění inverze matice. Obrázek vytvořil Sneha H.L.

V důsledku toho se každý (i,j)-tý prvek původního jádra stane (j,i)-tým prvkem v nové matici.

Krok 2: Posuňte jádro po obrázku a v každém okamžiku proveďte operaci MAC

Překryjte invertované jádro po obrázku a postupujte pixel po pixelu.

Pro každý případ vypočítejte součin vzájemně se překrývajících pixelů a vypočítejte jejich součet. Výsledkem bude hodnota výstupního pixelu v daném místě. Pro tento příklad se bude předpokládat, že nepřekrývající se pixely mají hodnotu „0“. Podrobněji o tom pojednáme v následující části „Nulový padding“.

V tomto příkladu začneme jádro posouvat nejprve po sloupcích a pak budeme postupovat po řádcích.

Pixely po řádcích

Nejprve zcela překleneme první řádek a pak postoupíme na druhý a tak dále a tak dále.

Při tomto postupu by první překrytí mezi jádrem a pixely obrazu vzniklo, když pixel v pravém dolním rohu jádra padne na hodnotu prvního pixelu v levém horním rohu matice obrazu. Obě tyto hodnoty pixelů jsou na obrázku 3a zvýrazněny a zobrazeny tmavě červenou barvou. Hodnota prvního pixelu výstupního obrazu tedy bude 25 × 1 = 25.

Napříště posuňme jádro po stejném řádku o jeden pixel. V této fázi se dvě hodnoty matice jádra (0, 1 – znázorněné tmavě červeným písmem) překrývají se dvěma pixely obrazu (25 a 100 znázorněné tmavě červeným písmem), jak ukazuje obrázek 3b. Výsledná hodnota výstupního pixelu tedy bude 25 × 0 + 100 × 1 = 100.

Obrázek 3a, 3b. Výsledky konvoluce získané pro výstupní pixely v místě (1,1) a (1,2). Obrázek vytvořila Sneha H.L.

Obrázek 3c, 3d: Výsledky konvoluce získané pro výstupní pixely v místě (1,4) a (1,7). Obrázek vytvořený Sneha H.L.

Postupem podobným způsobem lze vypočítat všechny hodnoty pixelů prvního řádku ve výstupním obrázku. Dva takové příklady odpovídající čtvrtému a sedmému výstupnímu pixelu výstupní matice jsou zobrazeny na obrázcích 3c a 3d.

Pokud jádro dále posouváme podél stejného řádku, žádný z pixelů v jádře se nepřekrývá s pixely v obraze. To znamená, že jsme skončili podél stávajícího řádku.

Přesun vertikálně dolů, postup horizontálně

Dalším krokem by bylo postoupit vertikálně dolů o jeden pixel a poté znovu začít postupovat horizontálně. První překrytí, které by pak nastalo, je znázorněno na obrázku 4a a provedením operace MAC nad nimi; dostaneme výsledek jako 25 × 0 + 50 × 1 = 50.

Poté můžeme jádro posouvat v horizontálním směru, dokud nebudou existovat další hodnoty, které se překrývají mezi jádrem a maticemi obrazu. Jeden takový případ odpovídající šesté hodnotě pixelu výstupní matice (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) je zobrazen na obrázku 4b.

Obrázek 4a, 4b. Výsledky konvoluce získané pro výstupní pixely v místě (2,1) a (2,6). Obrázek vytvořil Sneha H.L.

Tento proces posunu o jeden krok dolů a následného horizontálního skenování musí pokračovat až do posledního řádku matice obrazu. Tři náhodné příklady týkající se výstupů pixelů v místech (4,3), (6,5) a (8,6) jsou zobrazeny na obrázcích 5a-c.

Obrázek 5a. Výsledky konvoluce získané pro výstupní pixely v místě (4,3). Obrázek vytvořil Sneha H.L.

Obrázek 5b. Výsledky konvoluce získané pro výstupní pixely v bodě (6,5). Obrázek vytvořený Sneha H.L.

Obrázek 5c. Výsledky konvoluce získané pro výstupní pixely v bodě (8,6). Obrázek vytvořený Snehou H.L.

Krok

Takže výsledná výstupní matice bude:

Obrázek 6. Výsledná výstupní matice našeho příkladu. Obrázek vytvořil Sneha H.L.

Nulový padding

Matematická formulace 2-D konvoluce je dána vztahem

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

kde, x představuje matici vstupního obrazu, která se má konvolvovat s maticí jádra h, aby vznikla nová matice y, která představuje výstupní obraz. Zde se indexy i a j týkají matic obrazu, zatímco indexy m a n se týkají matic jádra. Je-li velikost jádra zapojeného do konvoluce 3 × 3, pak se indexy m a n pohybují od -1 do 1. Pro tento případ rozklad předloženého vzorce vede k

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

To znamená, že pro získání každého výstupního pixelu, je třeba provést 9 násobení, jejichž činiteli jsou překrývající se pixelové prvky obrazu a jádra. Zatímco jsme však počítali hodnotu pro náš první výstupní pixel, provedli jsme pouze jediné násobení (obrázek 3a replikovaný jako obrázek 7a). Co to znamená? Znamená to nesoulad s formou rovnice 2-D konvoluce?“

Ne, ve skutečnosti ne. Protože výsledek získaný součtem devíti součinových členů může být roven součinu jediného členu, pokud se společný účinek ostatních osmi součinových členů vyrovná na nulu. Jedním z takových způsobů je případ, kdy se každý součin ostatních osmi členů vyhodnotí jako nulový. V kontextu našeho příkladu to znamená, že všechny součinové členy odpovídající nepřekrývajícím se (mezi obrazem a jádrem) pixelům se musí stát nulovými, aby se výsledek vzorcového výpočtu rovnal výsledku grafického výpočtu.

Z našich elementárních znalostí matematiky víme, že pokud je alespoň jeden z činitelů zapojených do násobení nulový, pak je nulový i výsledný součin. Na základě této analogie můžeme konstatovat, že v našem příkladu potřebujeme mít nulový obrazový pixel odpovídající každému nepřekrývajícímu se pixelu matice jádra. Obrázkové znázornění by bylo takové, jak je uvedeno na obrázku 7b. Zde je třeba si všimnout jedné důležité věci, takovéto přidání nul do obrazu nemění obraz v žádném smyslu kromě jeho velikosti.

Obrázek 7: Nulová výplň zobrazená pro první pixel obrazu (nakresleno mnou)

Tento proces přidání dalších nul je známý jako nulová výplň a je třeba jej provést v každém případě, kdy neexistují žádné pixely obrazu, které by překrývaly pixely jádra. V našem příkladu je třeba provést doplnění nul pro každý pixel, který leží podél prvních dvou řádků a sloupců, a také pro ty, které se objevují podél posledních dvou řádků a sloupců (tyto pixely jsou na obrázku 8 znázorněny modrým písmem). Obecně je počet řádků nebo sloupců, které je třeba doplnit nulou na každé straně vstupního obrazu, dán vztahem (počet řádků nebo sloupců v jádře – 1).

Obrázek 8

Jedinou důležitou věcí, kterou je třeba zmínit, je skutečnost, že doplnění nulou není jediným způsobem, jak se vypořádat s okrajovými efekty způsobenými konvolucí. Mezi další techniky vycpávek patří replikační vycpávka, periodické rozšíření, zrcadlení atd. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Shrnutí

Tento článek si klade za cíl vysvětlit grafickou metodu 2-D konvoluce a koncept nulové vycpávky s ohledem na digitální zpracování obrazu.

.