Convoluția 2D în procesarea imaginilor

Acest articol oferă o perspectivă asupra convoluției bidimensionale și a capitonării zero în ceea ce privește procesarea digitală a imaginilor.

În articolul meu anterior „O mai bună perspectivă asupra DSP: Învățând despre convoluție”, am discutat despre convoluție și cele două aplicații importante ale sale în domeniul procesării semnalelor. Acolo, se presupunea că semnalele erau considerate unidimensionale în domeniul spațial. Cu toate acestea, procesul de convoluție poate fi efectuat și pe semnale multidimensionale.

În acest articol, vom încerca să înțelegem mai bine procesul și consecințele convoluției bidimensionale, utilizate pe scară largă în domeniul prelucrării imaginilor.

Definirea convoluției 2D

Convoluția care implică semnale unidimensionale este denumită convoluție 1D sau pur și simplu convoluție. În caz contrar, dacă convoluția se realizează între două semnale care se întind de-a lungul a două dimensiuni reciproc perpendiculare (adică, dacă semnalele sunt de natură bidimensională), atunci se va numi convoluție 2D. Acest concept poate fi extins pentru a implica semnale multidimensionale datorită cărora putem avea o convoluție multidimensională.

În domeniul digital, convoluția se realizează prin înmulțirea și acumularea valorilor instantanee ale eșantioanelor suprapuse care corespund la două semnale de intrare, dintre care unul este răsturnat. Această definiție a convoluției 1D este aplicabilă chiar și în cazul convoluției 2D, cu excepția faptului că, în acest din urmă caz, una dintre intrări este răsturnată de două ori.

Acest tip de operație este utilizat pe scară largă în domeniul prelucrării digitale a imaginilor, în care matricea 2D care reprezintă imaginea va fi convoluită cu o matrice comparativ mai mică, numită nucleu 2D.

Un exemplu de convoluție 2D

Să încercăm să calculăm valoarea pixelilor din imaginea de ieșire rezultată din convoluția matricei de imagine x de dimensiune 5×5 cu nucleul h de dimensiune 3×3, prezentată mai jos în figura 1.

Figura 1: Matrici de intrare, unde x reprezintă imaginea originală și h reprezintă nucleul. Imagine creată de Sneha H.L.

Pentru a realiza acest lucru, procedura pas cu pas care trebuie urmată este prezentată mai jos.

Pasul 1: Inversia matricei

Acest pas implică răsturnarea nucleului de-a lungul, să zicem, rândurilor, urmată de o răsturnare de-a lungul coloanelor sale, așa cum se arată în figura 2.

Figura 2: Reprezentare picturală a inversiei matricelor. Imagine creată de Sneha H.L.

Ca rezultat, fiecare al (i,j)-lea element al nucleului original devine al (j,i)-lea element în noua matrice.

Etapa 2: Glisați nucleul peste imagine și efectuați operația MAC la fiecare clipă

Suprapuneți nucleul inversat peste imagine, avansând pixel cu pixel.

Pentru fiecare caz, calculați produsul pixelilor care se suprapun reciproc și calculați suma lor. Rezultatul va fi valoarea pixelului de ieșire în acel loc anume. Pentru acest exemplu, se va presupune că pixelii care nu se suprapun vor avea o valoare de „0”. Vom discuta acest lucru mai detaliat în următoarea secțiune despre „Zero Padding”.

În exemplul de față, vom începe să glisăm mai întâi nucleul pe coloane și apoi vom avansa de-a lungul rândurilor.

Pixeli rând cu rând

Primul rând, să acoperim mai întâi primul rând complet și apoi să avansăm la al doilea, și așa mai departe și tot așa.

În timpul acestui proces, prima suprapunere între nucleu și pixelii imaginii ar rezulta atunci când pixelul din dreapta jos al nucleului cade pe prima valoare de pixel din stânga sus a matricei imaginii. Ambele valori ale acestor pixeli sunt evidențiate și prezentate cu roșu închis în figura 3a. Astfel, prima valoare a pixelului din imaginea de ieșire va fi 25 × 1 = 25.

În continuare, să avansăm nucleul de-a lungul aceluiași rând cu un singur pixel. În acest stadiu, două valori ale matricei nucleului (0, 1 – reprezentate cu font de culoare roșu închis) se suprapun cu doi pixeli ai imaginii (25 și 100 reprezentate cu font de culoare roșu închis), așa cum se arată în figura 3b. Astfel, valoarea pixelului de ieșire rezultată va fi 25 × 0 + 100 × 1 = 100.

Figura 3a, 3b. Rezultatele convoluției obținute pentru pixelii de ieșire la locația (1,1) și (1,2). Imagine creată de Sneha H.L.

Figura 3c, 3d: Rezultatele convoluției obținute pentru pixelii de ieșire la locația (1,4) și (1,7). Imagine creată de Sneha H.L.

Avansând în mod similar, pot fi calculate toate valorile pixelilor de pe primul rând din imaginea de ieșire. Două astfel de exemple corespunzătoare pixelilor de ieșire al patrulea și al șaptelea din matricea de ieșire sunt prezentate în figurile 3c și, respectiv, 3d.

Dacă glisăm în continuare nucleul de-a lungul aceluiași rând, niciunul dintre pixelii din nucleu nu se suprapune cu cei din imagine. Acest lucru indică faptul că am terminat de-a lungul rândului actual.

Mutarea în jos pe verticală, avansarea pe orizontală

Postul următor ar fi să avansăm pe verticală în jos cu un singur pixel înainte de a reîncepe să ne deplasăm pe orizontală. Prima suprapunere care ar apărea atunci este așa cum se arată în figura 4a și, efectuând operația MAC peste ele; obținem rezultatul 25 × 0 + 50 × 1 = 50.

După aceasta, putem glisa nucleul în direcția orizontală până când nu mai există valori care să se suprapună între nucleu și matricile imaginii. Un astfel de caz care corespunde celei de-a șasea valori a pixelului din matricea de ieșire (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) este prezentat în figura 4b.

Figura 4a, 4b. Rezultatele convoluției obținute pentru pixelii de ieșire la locația (2,1) și (2,6). Imagine creată de Sneha H.L.

Acest proces de deplasare cu un pas în jos urmat de scanare orizontală trebuie continuat până la ultimul rând al matricei imaginii. Trei exemple aleatorii care se referă la ieșirile de pixeli în locațiile (4,3), (6,5) și (8,6) sunt prezentate în figurile 5a-c.

Figura 5a. Rezultatele convoluției obținute pentru pixelii de ieșire la (4,3). Imagine creată de Sneha H.L.

Figura 5b. Rezultatele convoluției obținute pentru pixelii de ieșire la (6,5). Imagine creată de Sneha H.L.

Figura 5c. Rezultatele convoluției obținute pentru pixelii de ieșire la (8,6). Imagine creată de Sneha H.L.

Etapa

În consecință, matricea de ieșire rezultată va fi:

Figura 6. Matricea de ieșire rezultată a exemplului nostru. Imagine creată de Sneha H.L.

Zero Padding

Formulația matematică a convoluției 2-D este dată de

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

unde, x reprezintă matricea imaginii de intrare care urmează să fie convolvată cu matricea kernel h pentru a obține o nouă matrice y, care reprezintă imaginea de ieșire. Aici, indicii i și j se referă la matricile imaginii, în timp ce indicii m și n se referă la cea a nucleului. În cazul în care dimensiunea nucleului implicat în convoluție este de 3 × 3, atunci indicii m și n variază între -1 și 1. Pentru acest caz, o expansiune a formulei prezentate are ca rezultat

$$$ 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 \cdot x\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \cdot x\left $$

Aceasta indică faptul că pentru a obține fiecare pixel de ieșire, trebuie să se efectueze 9 înmulțiri ai căror factori sunt elementele de pixel suprapuse ale imaginii și ale nucleului. Cu toate acestea, în timp ce am calculat valoarea pentru primul nostru pixel de ieșire, am efectuat doar o singură înmulțire (Figura 3a reprodusă ca Figura 7a). Ce înseamnă acest lucru? Implică o inconsecvență cu forma de ecuație a convoluției 2-D?

Nu, nu chiar. Deoarece, rezultatul obținut prin însumarea a nouă termeni produs poate fi egal cu produsul unui singur termen dacă efectul colectiv al celorlalți opt termeni produs se egalează cu zero. Un astfel de mod este cazul în care fiecare produs al celorlalți opt termeni se evaluează singur la zero. În contextul exemplului nostru, aceasta înseamnă că toți termenii produsului care corespund pixelilor care nu se suprapun (între imagine și nucleu) trebuie să devină zero pentru ca rezultatele calculului prin formule să fie egale cu cele ale calculului grafic.

Din cunoștințele noastre elementare de matematică, știm că dacă cel puțin unul dintre factorii implicați în înmulțire este zero, atunci produsul rezultat este, de asemenea, zero. Prin această analogie, putem afirma că, în exemplul nostru, trebuie să avem un pixel-imagine cu valoare zero care să corespundă fiecărui pixel care nu se suprapune din matricea nucleului. Reprezentarea picturală a acestui lucru ar fi cea prezentată în figura 7b. Un lucru important care trebuie observat aici este că o astfel de adăugare de zerouri la imagine nu modifică imaginea în niciun sens, cu excepția dimensiunii sale.

Figura 7: Adăugarea de zerouri prezentată pentru primul pixel al imaginii (Desenat de mine)

Acest proces de adăugare de zerouri suplimentare este cunoscut sub numele de „zero padding” și este necesar să se facă în fiecare caz în care nu există pixeli de imagine care să se suprapună peste pixelii nucleului. Pentru exemplul nostru, este necesar să se efectueze o umplere cu zero pentru fiecare pixel care se află de-a lungul primelor două rânduri și coloane, precum și pentru cei care apar de-a lungul ultimelor două rânduri și coloane (acești pixeli sunt reprezentați cu font albastru în figura 8). În general, numărul de rânduri sau coloane care trebuie să fie capitonate cu zero pe fiecare parte a imaginii de intrare este dat de (numărul de rânduri sau coloane din kernel – 1).

Figura 8

Un lucru important care trebuie menționat este faptul că capitonarea cu zero nu este singura modalitate de a trata efectele de margine aduse de convoluție. Alte tehnici de umplutură includ umplutura replicată, extensia periodică, oglindirea etc. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Summary

Acest articol își propune să explice metoda grafică a convoluției 2-D și conceptul de umplutură zero în ceea ce privește prelucrarea digitală a imaginilor.