2D-konvolution i bildbehandling

Denna artikel ger en inblick i tvådimensionell konvolution och nollpaddning med avseende på digital bildbehandling.

I min tidigare artikel ”Bättre inblick i DSP: Lär dig mer om konvolution” diskuterade jag konvolutionen och dess två viktiga tillämpningar inom signalbehandlingsområdet. Där ansågs signalerna förmodligen vara endimensionella i den spatiala domänen. Processen med konvolution kan dock utföras även på flerdimensionella signaler.

I den här artikeln ska vi försöka förstå processen och konsekvenserna av den tvådimensionella konvolutionen, som används flitigt inom bildbehandlingsområdet, bättre.

Definitionen av 2D-konvolution

Konvolution som involverar endimensionella signaler kallas för 1D-konvolution eller bara konvolution. Om konvolutionen däremot utförs mellan två signaler som sträcker sig längs två sinsemellan vinkelräta dimensioner (dvs. om signalerna är tvådimensionella till sin natur), kallas den för 2D-konvolution. Detta begrepp kan utvidgas till att omfatta flerdimensionella signaler, vilket gör att vi kan få en flerdimensionell konvolution.

I den digitala domänen utförs konvolutionen genom att multiplicera och ackumulera de ögonblickliga värdena för de överlappande samplingar som motsvarar två insignaler, av vilka den ena är vänd. Denna definition av 1D-konvolution är tillämplig även för 2D-konvolution utom att i det senare fallet vänds en av ingångarna två gånger.

Denna typ av operation används i stor utsträckning inom området digital bildbehandling där 2D-matrisen som representerar bilden kommer att konvolveras med en jämförelsevis mindre matris som kallas 2D-kärna.

Ett exempel på 2D-konvolution

Låt oss försöka beräkna pixelvärdet i utdatabilden som är resultatet av konvolutionen av en bildmatris x i storleken 5×5 med kärnan h i storleken 3×3, som visas nedan i figur 1.

Figur 1: Ingångsmatriser, där x representerar originalbilden och h representerar kärnan. Bild skapad av Sneha H.L.

För att åstadkomma detta beskrivs den stegvisa procedur som ska följas nedan.

Steg 1: Matrisinversion

Detta steg innebär att kärnan vänds längs t.ex. rader följt av en vändning längs kolumnerna, vilket visas i figur 2.

Figur 2: Bildlig representation av matrisinversion. Bild skapad av Sneha H.L.

Som ett resultat blir varje (i,j)e element i den ursprungliga kärnan det (j,i)e elementet i den nya matrisen.

Steg 2: Glid kärnan över bilden och utför MAC-operationen vid varje ögonblick

Följ den inverterade kärnan över bilden och gå framåt pixel för pixel.

För varje fall, beräkna produkten av de pixlar som ömsesidigt överlappar varandra och beräkna deras summa. Resultatet blir värdet för utgångspixeln på den aktuella platsen. I det här exemplet antas de pixlar som inte överlappar varandra ha värdet ”0”. Vi kommer att diskutera detta mer i detalj i nästa avsnitt om ”Zero Padding”.

I det här exemplet börjar vi med att skjuta kärnan kolumnvis först och avancerar sedan längs raderna.

Pixlar rad för rad

Först spänner vi över den första raden helt och hållet och avancerar sedan till den andra, och så vidare och så vidare.

Under denna process skulle den första överlappningen mellan kärnan och bildpixlarna uppstå när pixeln längst ner till höger i kärnan faller på det första pixelvärdet längst upp till vänster i bildmatrisen. Båda dessa pixelvärden är markerade och visas i mörkröd färg i figur 3a. Så det första pixelvärdet i utgångsbilden blir 25 × 1 = 25.

Nästan, låt oss flytta fram kärnan längs samma rad med en enda pixel. I detta skede överlappar två värden i kärnmatrisen (0, 1 – visas i mörkrött typsnitt) två pixlar i bilden (25 och 100 visas i mörkrött typsnitt), vilket visas i figur 3b. Det resulterande pixelvärdet blir alltså 25 × 0 + 100 × 1 = 100.

Figur 3a, 3b. Resultat av konvolutionen för utgångspixlarna på platserna (1,1) och (1,2). Bild skapad av Sneha H.L.

Figur 3c, 3d: Resultat av konvolutionen för utgångspixlarna på platserna (1,4) och (1,7). Bild skapad av Sneha H.L.

Med samma tillvägagångssätt kan alla pixelvärden i den första raden i utdatabilden beräknas. Två sådana exempel som motsvarar fjärde och sjunde utgångspixeln i utgångsmatrisen visas i figurerna 3c respektive 3d.

Om vi ytterligare förflyttar kärnan längs samma rad överlappar ingen av pixlarna i kärnan med pixlarna i bilden. Detta indikerar att vi är klara längs den aktuella raden.

Föra ner vertikalt, avancera horisontellt

Nästa steg skulle vara att avancera vertikalt ner med en enda pixel innan vi återupptar förflyttningen horisontellt. Den första överlappningen som då skulle uppstå är den som visas i figur 4a och genom att utföra MAC-operationen över dem får vi resultatet 25 × 0 + 50 × 1 = 50.

Därefter kan vi skjuta kärnan i horisontell riktning tills det inte finns några fler värden som överlappar mellan kärnan och bildmatriserna. Ett sådant fall som motsvarar det sjätte pixelvärdet i utgångsmatrisen (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) visas i figur 4b.

Figur 4a, 4b. Resultat av konvolutionen för utgångspixlarna på platserna (2,1) och (2,6). Bild skapad av Sneha H.L.

Denna process med ett steg nedåt följt av horisontell skanning måste fortsätta till den sista raden i bildmatrisen. Tre slumpmässiga exempel som rör pixelutgångarna på platserna (4,3), (6,5) och (8,6) visas i figurerna 5a-c.

Figur 5a. Resultat av konvolutionen för utgångspixlarna vid (4,3). Bild skapad av Sneha H.L.

Figur 5b. Resultat av konvolutionen för utgångspixlarna vid (6,5). Bild skapad av Sneha H.L.

Figur 5c. Resultat av konvolutionen för utgångspixlarna vid (8,6). Bild skapad av Sneha H.L.

Steg

Därmed blir den resulterande utmatrisen:

Figur 6. Vårt exempels resulterande utmatris. Bild skapad av Sneha H.L.

Zero Padding

Den matematiska formuleringen av 2-D konvolution ges av

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

var, x representerar matrisen för inmatningsbilden som ska konvolveras med kärnmatrisen h för att resultera i en ny matris y, som representerar utmatningsbilden. Här gäller indexen i och j bildmatriserna medan indexen m och n gäller kärnmatriserna. Om storleken på den kärna som är inblandad i konvolutionen är 3 × 3, varierar indexen m och n mellan -1 och 1. För detta fall, en expansion av den presenterade formeln resulterar i

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

Detta indikerar att för att erhålla varje utgångspixel, måste 9 multiplikationer utföras vars faktorer är de överlappande pixelelementen i bilden och kärnan. När vi beräknade värdet för vår första utgångspixel utförde vi dock bara en enda multiplikation (figur 3a replikerad som figur 7a). Vad betyder detta? Innebär det en inkonsekvens med ekvationsformen för 2-D konvolution?

Nej, egentligen inte. Därför att det resultat som erhålls genom summering av nio produkttermer kan vara lika med produkten av en enda term om den kollektiva effekten av de andra åtta produkttermerna utjämnas till noll. Ett sådant sätt är det fall där varje produkt av de övriga åtta termerna utvärderar sig själva till noll. I samband med vårt exempel innebär detta att alla produkttermer som motsvarar de pixlar som inte överlappar varandra (mellan bilden och kärnan) måste bli noll för att resultatet av formelberäkningen ska bli lika med resultatet av den grafiska beräkningen.

Från våra elementära kunskaper i matematik vet vi att om minst en av faktorerna som är inblandade i en multiplikation är noll, så är den resulterande produkten också noll. Genom denna analogi kan vi konstatera att vi i vårt exempel måste ha en nollvärdig bildpixel som motsvarar varje icke överlappande pixel i kärnmatrisen. En bildlig representation av detta skulle vara den som visas i figur 7b. En viktig sak att lägga märke till här är att ett sådant tillägg av nollor till bilden inte ändrar bilden i någon mening förutom dess storlek.

Figur 7: Nollpaddning visas för bildens första pixel (ritad av mig)

Den här processen med att lägga till extra nollor kallas nollpaddning och måste göras i varje fall där det inte finns några bildpixlar som överlappar kärnpixlarna. I vårt exempel måste nollutfyllnad göras för varje pixel som ligger längs de två första raderna och kolumnerna samt för de pixlar som ligger längs de två sista raderna och kolumnerna (dessa pixlar visas med blått typsnitt i figur 8). I allmänhet ges antalet rader eller kolumner som skall nollpaddas på varje sida av inmatningsbilden av (antal rader eller kolumner i kärnan – 1).

Figur 8

En viktig sak som bör nämnas är det faktum att nollpaddning inte är det enda sättet att hantera de kanteffekter som uppstår vid konvolution. Andra utfyllnadstekniker är replikatutfyllnad, periodisk förlängning, spegling etc. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Sammanfattning

Denna artikel syftar till att förklara den grafiska metoden för tvådimensionell konvolution och begreppet nollutfyllnad med avseende på digital bildbehandling.