2D Convolutie in Beeldverwerking

Dit artikel geeft inzicht in tweedimensionale convolutie en zero-padding met betrekking tot digitale beeldverwerking.

In mijn vorige artikel “Beter inzicht in DSP: Leren over Convolutie”, besprak ik convolutie en de twee belangrijke toepassingen ervan op het gebied van signaalverwerking. Daar werden de signalen vermoedelijk beschouwd als eendimensionaal in het ruimtelijk domein. Het proces van convolutie kan echter ook worden uitgevoerd op meerdimensionale signalen.

In dit artikel zullen we proberen het proces en de gevolgen van tweedimensionale convolutie, die veel wordt gebruikt op het gebied van beeldverwerking, beter te begrijpen.

De definitie van 2D Convolutie

Convolutie waarbij eendimensionale signalen worden gebruikt, wordt 1D convolutie genoemd of gewoon convolutie. Indien de convolutie wordt uitgevoerd tussen twee signalen die zich over twee onderling loodrechte dimensies uitstrekken (d.w.z. indien de signalen tweedimensionaal van aard zijn), dan wordt deze aangeduid als 2D-convolutie. Dit concept kan worden uitgebreid tot multidimensionale signalen, waardoor er sprake kan zijn van multidimensionale convolutie.

In het digitale domein wordt convolutie uitgevoerd door vermenigvuldiging en accumulatie van de momentane waarden van de overlappende monsters die corresponderen met twee ingangssignalen, waarvan er één wordt omgedraaid. Deze definitie van 1D convolutie is zelfs van toepassing op 2D convolutie, behalve dat in het laatste geval een van de ingangssignalen tweemaal wordt omgedraaid.

Dit soort bewerking wordt op grote schaal gebruikt op het gebied van digitale beeldverwerking, waarbij de 2D matrix die het beeld vertegenwoordigt zal worden geconvolveerd met een relatief kleinere matrix die 2D kernel wordt genoemd.

Een voorbeeld van 2D Convolutie

Laten we eens proberen de pixelwaarde te berekenen van het uitgangsbeeld dat het resultaat is van de convolutie van een 5×5-afbeeldingsmatrix x met de kernel h van 3×3, zoals hieronder in figuur 1 wordt getoond.

Figuur 1: Ingangsmatrices, waarbij x de originele afbeelding voorstelt en h de kernel. Afbeelding gemaakt door Sneha H.L.

Om dit te bereiken, wordt de te volgen stapsgewijze procedure hieronder geschetst.

Stap 1: Matrixinversie

Bij deze stap wordt de kernel omgedraaid, bijvoorbeeld langs de rijen, gevolgd door een omdraaiing langs de kolommen, zoals te zien is in figuur 2.

Figuur 2: Illustratieve weergave van matrixinversie. Afbeelding gemaakt door Sneha H.L.

Als resultaat wordt elk (i,j)e element van de oorspronkelijke kern het (j,i)e element in de nieuwe matrix.

Stap 2: Schuif de kernel over de afbeelding en voer de MAC-bewerking op elk moment uit

Overlap de geïnverteerde kernel over de afbeelding, waarbij pixel voor pixel wordt opgeschoven.

Voor elk geval berekent u het product van de elkaar overlappende pixels en berekent u de som ervan. Het resultaat is de waarde van de uitvoerpixel op die bepaalde plaats. In dit voorbeeld wordt ervan uitgegaan dat niet-overlappende pixels een waarde “0” hebben. We zullen dit in meer detail bespreken in de volgende paragraaf over “Zero Padding”.

In het huidige voorbeeld beginnen we eerst de kernel kolomgewijs te schuiven en gaan dan verder langs de rijen.

Pixels rij per rij

Laten we eerst de eerste rij volledig overspannen en gaan we dan verder met de tweede, enzovoort enzovoort.

Tijdens dit proces zou de eerste overlap tussen de kernel en de beeldpixels ontstaan wanneer de pixel rechtsonder in de kernel valt op de eerste pixelwaarde linksboven in de beeldmatrix. Deze beide pixelwaarden zijn gemarkeerd en in donkerrode kleur weergegeven in figuur 3a. De eerste pixelwaarde van het uitgangsbeeld is dus 25 × 1 = 25.

Laten we de kernel nu één pixel verder op dezelfde rij zetten. In dit stadium overlappen twee waarden van de kernelmatrix (0, 1 – afgebeeld in donkerrood lettertype) met twee pixels van het beeld (25 en 100 afgebeeld in donkerrood lettertype), zoals afgebeeld in figuur 3b. De resulterende waarde van de uitvoerpixel is dus 25 × 0 + 100 × 1 = 100.

Figuur 3a, 3b. Convolutieresultaten voor de uitvoerpixels op locatie (1,1) en (1,2). Afbeelding gemaakt door Sneha H.L.

Figuur 3c, 3d: Convolutieresultaten voor de uitvoerpixels op plaats (1,4) en (1,7). Afbeelding gemaakt door Sneha H.L.

Op dezelfde manier kunnen alle pixelwaarden van de eerste rij in de uitvoerafbeelding worden berekend. Twee van dergelijke voorbeelden, die overeenkomen met de vierde en zevende uitvoerpixels van de uitvoermatrix, zijn respectievelijk te zien in de figuren 3c en 3d.

Als we de kernel verder langs dezelfde rij schuiven, overlapt geen van de pixels in de kernel met die in de afbeelding. Dit geeft aan dat we klaar zijn langs de huidige rij.

Verticaal naar beneden schuiven, horizontaal naar voren

De volgende stap zou zijn om verticaal naar beneden te schuiven met één pixel voordat we opnieuw beginnen met horizontaal schuiven. De eerste overlapping die dan optreedt, is te zien in figuur 4a en door de MAC-bewerking erover uit te voeren, krijgen we als resultaat 25 × 0 + 50 × 1 = 50.

Vervolgens kunnen we de kernel in horizontale richting schuiven tot er geen waarden meer zijn die de kernel en de beeldmatrices overlappen. Eén zo’n geval, dat overeenkomt met de zesde pixelwaarde van de uitgangsmatrix (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200), wordt getoond in figuur 4b.

Figuur 4a, 4b. Convolutieresultaten verkregen voor de uitvoerpixels op locatie (2,1) en (2,6). Afbeelding gemaakt door Sneha H.L.

Dit proces van één stap naar beneden gevolgd door horizontaal scannen moet worden voortgezet tot de laatste rij van de beeldmatrix. Drie willekeurige voorbeelden met betrekking tot de pixeluitgangen op de plaatsen (4,3), (6,5) en (8,6) worden getoond in Figuren 5a-c.

Figuur 5a. Convolutieresultaten verkregen voor de uitvoerpixels op (4,3). Afbeelding gemaakt door Sneha H.L.

Figuur 5b. Convolutieresultaten voor de uitvoerpixels op (6,5). Afbeelding gemaakt door Sneha H.L.

Figuur 5c. Convolutieresultaten voor de uitvoerpixels op (8,6). Afbeelding gemaakt door Sneha H.L.

Stap

De resulterende uitgangsmatrix wordt dan:

Figuur 6. De resulterende uitgangsmatrix van ons voorbeeld. Afbeelding gemaakt door Sneha H.L.

Zero Padding

De wiskundige formulering van 2-D convolutie wordt gegeven door

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

waar, x de beeldinvoermatrix voorstelt die moet worden geconvolveerd met de kernelmatrix h om een nieuwe matrix y te verkrijgen, die het uitgangsbeeld voorstelt. Hier hebben de indices i en j betrekking op de beeldmatrices, terwijl die van m en n betrekking hebben op die van de kernel. Indien de grootte van de kernel die bij de convolutie betrokken is 3 × 3 is, dan lopen de indexen m en n van -1 tot 1. Voor dit geval, resulteert een uitbreiding van de gepresenteerde formule in

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

$ y\left= h\left \left \left x\left + h\left \left \left x\left + h\left \left \left \Dit geeft aan dat om elke output pixel te verkrijgen, er 9 vermenigvuldigingen moeten worden uitgevoerd waarvan de factoren de overlappende pixelelementen van het beeld en de kernel zijn. Terwijl wij echter de waarde voor onze eerste uitvoerpixel berekenden, voerden wij slechts één vermenigvuldiging uit (Figuur 3a gerepliceerd als Figuur 7a). Wat betekent dit? Impliceert het een inconsistentie met de vergelijkingsvorm van 2-D convolutie?

Nee, niet echt. Want het resultaat verkregen door de sommatie van negen producttermen kan gelijk zijn aan het product van een enkele term als het gezamenlijke effect van de andere acht producttermen gelijk is aan nul. Eén zo’n manier is het geval waarin elk product van de andere acht termen zichzelf gelijkstelt aan nul. In de context van ons voorbeeld betekent dit, dat alle producttermen die corresponderen met de niet-overlappende (tussen beeld en kernel) pixels nul moeten worden om de resultaten van formule-berekening gelijk te maken aan die van grafische-berekening.

Vanuit onze elementaire kennis van de wiskunde weten we dat als tenminste één van de factoren die betrokken zijn bij vermenigvuldiging nul is, het resulterende product ook nul is. Op grond van deze analogie kunnen we stellen dat we in ons voorbeeld een beeldpixel met nul moeten hebben die overeenkomt met elke niet-overlappende pixel van de kernelmatrix. Een grafische voorstelling hiervan zou die zijn zoals in figuur 7b. Een belangrijk punt is dat een dergelijke toevoeging van nullen aan de afbeelding de afbeelding op geen enkele wijze verandert, behalve wat betreft de grootte.

Figuur 7: Nulvulling voor de eerste pixel van de afbeelding (door mij getekend)

Dit proces van het toevoegen van extra nullen staat bekend als nulvulling en moet worden uitgevoerd in elk geval waarin er geen beeldpixels zijn die de kernelpixels overlappen. In ons voorbeeld moet de nulopvulling worden uitgevoerd voor elke pixel die in de eerste twee rijen en kolommen ligt en voor elke pixel die in de laatste twee rijen en kolommen ligt (deze pixels zijn in figuur 8 in het blauwe lettertype aangegeven). In het algemeen wordt het aantal rijen of kolommen aan elke kant van het invoerbeeld dat met “zero padding” moet worden opgevuld, gegeven door (het aantal rijen of kolommen in de kernel – 1).

Figuur 8

Een belangrijk punt dat moet worden vermeld, is het feit dat “zero padding” niet de enige manier is om de door convolutie veroorzaakte randeffecten aan te pakken. Andere opvullingstechnieken zijn replicate padding, periodic extension, mirroring, etc. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Samenvatting

Dit artikel heeft tot doel de grafische methode van 2-D convolutie en het concept van zero padding uit te leggen met betrekking tot digitale beeldverwerking.