2D-foldning i billedbehandling

Denne artikel giver et indblik i todimensional foldning og nul-padding i forbindelse med digital billedbehandling.

I min tidligere artikel “Bedre indsigt i DSP: Lær om foldning”, diskuterede jeg foldning og dens to vigtige anvendelser inden for signalbehandling. Der blev signalerne formentlig anset for at være endimensionelle i det rumlige domæne. Processen med konvolution kan imidlertid også udføres på flerdimensionale signaler.

I denne artikel vil vi forsøge at forstå processen og konsekvenserne af todimensional konvolution, der anvendes i vid udstrækning inden for billedbehandling, bedre.

Definitionen af 2D-konvolution

Konvolution, der involverer endimensionale signaler, kaldes 1D-konvolution eller blot konvolution. Hvis konvolutionen derimod udføres mellem to signaler, der spænder over to gensidigt vinkelrette dimensioner (dvs. hvis signalerne er todimensionelle af natur), vil den blive omtalt som 2D-konvolution. Dette begreb kan udvides til at omfatte flerdimensionale signaler, hvorved vi kan få flerdimensional konvolution.

I det digitale domæne udføres konvolution ved at multiplicere og akkumulere de øjeblikkelige værdier af de overlappende prøver svarende til to indgangssignaler, hvoraf det ene er vendt. Denne definition af 1D-foldning gælder også for 2D-foldning, bortset fra at i sidstnævnte tilfælde er et af indgangssignalerne vendt to gange.

Denne type operation anvendes i vid udstrækning inden for digital billedbehandling, hvor den 2D-matrix, der repræsenterer billedet, vil blive foldet med en forholdsvis mindre matrix kaldet 2D-kernen.

Eksempel på 2D-konvolution

Lad os prøve at beregne pixelværdien af det udgangsbillede, der er resultatet af konvolutionen af en billedmatrix x på størrelse 5×5 med kernen h på størrelse 3×3, som er vist nedenfor i figur 1.

Figur 1: Indgangsmatricer, hvor x repræsenterer det oprindelige billede, og h repræsenterer kernen. Billedet er skabt af Sneha H.L.

For at opnå dette er den trinvise procedure, der skal følges, skitseret nedenfor.

Strin 1: Matrixinversion

Dette trin indebærer en vending af kernen langs f.eks. rækker efterfulgt af en vending langs dens kolonner, som vist i Figur 2.

Figur 2: Billedlig fremstilling af matrixinversion. Billede oprettet af Sneha H.L.

Som følge heraf bliver hvert (i,j)-te element i den oprindelige kerne til det (j,i)-te element i den nye matrix.

Stræk 2: Skub kernen hen over billedet, og udfør MAC-operationen i hvert øjeblik

Overlap den inverterede kerne hen over billedet og gå frem pixel for pixel.

For hvert tilfælde beregnes produktet af de gensidigt overlappende pixels, og deres sum beregnes. Resultatet vil være værdien af udgangspixelen på det pågældende sted. I dette eksempel antages det, at ikke-overlappende pixels har værdien “0”. Vi vil diskutere dette mere detaljeret i det næste afsnit om “Zero Padding”.

I det nuværende eksempel begynder vi først at skubbe kernen kolonnevis og går derefter videre langs rækkerne.

Pixels række for række

Først skal vi dække den første række fuldstændigt og derefter gå videre til den anden, osv. osv.

I løbet af denne proces vil det første overlap mellem kernen og billedpixlerne opstå, når pixlen nederst til højre i kernen falder på den første pixelværdi øverst til venstre i billedmatrixen. Begge disse pixelværdier er fremhævet og vist med mørkerød farve i figur 3a. Så den første pixelværdi i udgangsbilledet vil være 25 × 1 = 25.

Næste trin: Lad os rykke kernen frem langs den samme række med en enkelt pixel. På dette tidspunkt overlapper to værdier i kernematrixen (0, 1 – vist med mørkerød skrifttype) med to pixels i billedet (25 og 100 vist med mørkerød skrifttype), som vist i figur 3b. Så den resulterende outputpixelværdi vil være 25 × 0 + 100 × 1 = 100.

Figur 3a, 3b. Konvolutionsresultater for udgangspixelerne på placeringerne (1,1) og (1,2). Billedet er skabt af Sneha H.L.

Figur 3c, 3d: Konvolutionsresultater opnået for udgangspixelerne på placering (1,4) og (1,7). Billedet er skabt af Sneha H.L.

Der kan på samme måde beregnes alle pixelværdierne i den første række i udgangsbilledet. To sådanne eksempler svarende til fjerde og syvende udgangspixel i udgangsmatricen er vist i henholdsvis figur 3c og 3d.

Hvis vi yderligere lader kernen glide langs den samme række, overlapper ingen af kernens pixels med dem i billedet. Dette indikerer, at vi er færdige langs den nuværende række.

Flyt vertikalt nedad, gå horisontalt fremad

Det næste skridt ville være at gå vertikalt nedad med en enkelt pixel, før vi igen begynder at bevæge os horisontalt. Det første overlap, der så opstår, er som vist i figur 4a, og ved at udføre MAC-operationen over dem, får vi resultatet 25 × 0 + 50 × 1 = 50.

Derpå kan vi skubbe kernen i vandret retning, indtil der ikke er flere værdier, der overlapper mellem kernen og billedmatricerne. Et sådant tilfælde svarende til den sjette pixelværdi i udgangsmatricen (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) er vist i figur 4b.

Figur 4a, 4b. Resultater af konvolutionen for udgangspixelerne ved placering (2,1) og (2,6). Billede oprettet af Sneha H.L.

Denne proces med at bevæge sig et trin nedad efterfulgt af horisontal scanning skal fortsættes indtil den sidste række i billedmatrixen. Tre tilfældige eksempler, der vedrører pixeludgange på placeringerne (4,3), (6,5) og (8,6), er vist i figur 5a-c.

Figur 5a. Konvolutioneringsresultater for udgangspixelerne ved (4,3). Billede oprettet af Sneha H.L.

Figur 5b. Konvolutioneringsresultater for udgangspixelerne ved (6,5). Billede oprettet af Sneha H.L.

Figur 5c. Konvolutioneringsresultater for udgangspixelerne ved (8,6). Billedet er skabt af Sneha H.L.

Stræk

Den resulterende udgangsmatrix vil derfor være:

Figur 6. Vores eksempels resulterende udgangsmatrix. Billede oprettet af Sneha H.L.

Zero Padding

Den matematiske formulering af 2-D-foldning er givet ved

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

hvor, x repræsenterer indgangsbilledmatrixen, der skal konvolveres med kernematrixen h for at resultere i en ny matrix y, der repræsenterer udgangsbilledet. Her vedrører indeksene i og j billedmatricerne, mens indeksene m og n vedrører kernen. Hvis størrelsen af den kerne, der er involveret i konvolutionen, er 3 × 3, ligger indeksene m og n mellem -1 og 1. I dette tilfælde, resulterer en udvidelse af den præsenterede formel 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 + h\left \cdot x\left \cdot x\left $$$

Dette indikerer, at for at opnå hver udgangspixel, skal der udføres 9 multiplikationer, hvis faktorer er de overlappende pixelelementer i billedet og kernen. Men mens vi beregnede værdien for vores første udgangspixel, foretog vi kun en enkelt multiplikation (figur 3a replikeret som figur 7a). Hvad betyder dette? Indebærer det en uoverensstemmelse med ligningsformen for 2-D-foldning?

Nej, egentlig ikke. Fordi det resultat, der opnås ved summering af ni produkttermer, kan være lig med produktet af et enkelt term, hvis den samlede virkning af de andre otte produkttermer udlignes til nul. En sådan måde er det tilfælde, hvor hvert produkt af de andre otte termer evaluerer sig selv til nul. I forbindelse med vores eksempel betyder det, at alle de produkttermer, der svarer til de pixels, der ikke overlapper hinanden (mellem billedet og kernen), skal blive nul for at gøre resultaterne af formelberegningen lig med resultaterne af den grafiske beregning.

Fra vores elementære viden om matematik ved vi, at hvis mindst en af de faktorer, der indgår i multiplikationen, er nul, så er det resulterende produkt også nul. Ved hjælp af denne analogi kan vi konstatere, at vi i vores eksempel skal have en billedpixel med nulværdi svarende til hver enkelt ikke-overlappende pixel i kernematrixen. En billedlig fremstilling af dette ville være den, der er vist i figur 7b. En vigtig ting, der skal bemærkes her, er, at en sådan tilføjelse af nuller til billedet ikke ændrer billedet på nogen måde, bortset fra dets størrelse.

Figur 7: Nul-padding vist for den første pixel i billedet (Tegnet af mig)

Denne proces med at tilføje ekstra nuller er kendt som nul-padding og skal foretages i hvert tilfælde, hvor der ikke er nogen billedpixels, der overlapper kernepixlerne. I vores eksempel skal nulpolstring foretages for hver enkelt pixel, der ligger langs de to første rækker og kolonner, samt for de pixels, der ligger langs de to sidste rækker og kolonner (disse pixels er vist med blå skrifttype i figur 8). Generelt er antallet af rækker eller kolonner, der skal nul-padding på hver side af indgangsbilledet, givet ved (antal rækker eller kolonner i kernen – 1).

Figur 8

En vigtig ting, der skal nævnes, er det faktum, at nul-padding ikke er den eneste måde at håndtere de kanteffekter, der opstår ved konvolution. Andre padding-teknikker omfatter replicate padding, periodisk forlængelse, spejling osv. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Summary

Denne artikel har til formål at forklare den grafiske metode til 2-D-foldning og begrebet nul-padding med hensyn til digital billedbehandling.