Operatori liniari 2D. Convolutia 2D discreta

Operatori liniari 2D. Convolutia 2D discreta

Operatorii liniari joaca un rol important in prelucrarea numerica a imaginilor, avand la baza un suport teoretic ce a fost in mare parte dezvoltat anterior dezvoltarii preocuparilor din domeniul prelucrarii numerice  a semnalelor.

1. Operatorul liniar bidimensional generalizat

In forma serie cea mai generala, un operator liniar 2D (o transformare liniara) este definit prin ecuatia:

(3.1)

Ecuatia (3.1) arata ca un element oarecare al imaginii de iesire, g_m,n, se obtine ca o suma ponderata a elementelor imaginii de intrare, de dimensiuni M N. Ponderile sunt specificate de nucleul operatorului liniar, O(j,k;m,n). In cazul general, toate elementele imaginii de intrare participa la calculul fiecarui element al imaginii de iesire. Mai remarcam faptul ca definitia nu precizeaza dimensiunile  imaginii de iesire. Acest aspect urmeaza a fi clarificat pentru formele particulare importante ale operatorului liniar. Ecuatia (3.1) poate fi scrisa mai concis in reprezentare vectoriala

g = Of. (3.2)

Din punct de vedere practic, suntem adesea interesati in operatori liniari separabili, de forma

O(m,n; j,k) = O_C(j;m) O_R(k;n). (3.3)

Pentru operatorul liniar separabil, relatia (3.1) devine

. (3.4)

Se observa ca numarul maxim de operatii pe pixel scade drastic, de la M N la M+N. Operatorul O_R(k;n) efectueaza prelucrarea unidimensionala a tuturor liniilor (randurilor) imaginii f si are ca rezultat intermediar o imagine prelucrata pe linii:

(3.5)

unde j = 0, 1, , M-1 si n = 0,1, , Q-1.

Aceasta imagine este apoi prelucrata unidimensional de-a lungul coloanelor

(3.6)

unde m = 0,1, , P-1 si n = 0,1, , Q-1. Evident, era posibila si alta factorizare, care conducea la ordinea de prelucrare inversata. Examinand ultimele doua ecuatii, se observa ca operatorul liniar separabil poate fi scris si in forma

(3.7)

Si din aceasta ecuatie se observa ca ordinea de prelucrare este arbitrara, tinand cont de proprietatea de asociativitate a produsului matricilor.

2. Convolutia bidimensionala discreta

Definitie

Un caz particular important este operatorul liniar spatial-invariant 2D numit operator de convolutie bidimensionala discreta, caracterizat prin proprietatea:

h(j,k;m,n) = h_m-j,n-k. (3.8)

Convolutia bidimensionala discreta se poate exprima in forma serie prin ecuatia:

(3.9)

Convolutia bidimensionala discreta poate fi interpretata ca o discretizare a unei convolutii bidimensionale continue. Limitele de sumare din ecuatia (3.9) cer cateva precizari, existand in literatura mai multe moduri echivalente de a defini convolutia bidimensionala discreta. Elementele operatorului de convolutie pot fi aranjate in forma unei matrici, H cu elementul general h_p,q. Denumita sugestiv si masca de convolutie, matricea operatorului de convolutie nu trebuie confundata cu matricea operatorului liniar generalizat. Uzual, dimensiunile mastii operatorului de convolutie sunt mult mai mici decat cele ale imaginii. Fara pierderea generalitatii, vom presupune o masca de forma patrata, cu dimensiunile L L

(3.10)

Matricea H reprezinta raspunsul sistemului liniar la (o imagine) impuls unitar 2D, , avand un pixel cu nivelul de luminanta unitar in origine si fiind nula in restul domeniului real.

Cu aceste notatii, putem acum preciza ca, in ecuatia (3.9), h_p,q = 0 daca: p < 0 sau q < 0 sau p > L-1 sau q > L-1. Asemanator convolutiei imaginilor continuale, ecuatia (3.9) se scrie concis:

G = F H (3.11)

Convolutia 2D are toate proprietatile cunoscute ale operatorilor liniari discreti 1D:

comutativitate

asociativitate

distributivitate in raport cu adunarea imaginilor

Interpretare grafica a procesului de convolutie

Convolutia reprezinta o operatie locala, pentru ca un element al imaginii de iesire se obtine prin combinarea unor elemente ale imaginii de intrare localizate intr-un subdomeniu al imaginii, de regula de dimensiuni mici in comparatie cu dimensiunile imaginii. Este util sa dam o interpretaregrafica intuitiva procesului de convolutie (Fig. 3.1.). Imaginea este explorata, de exemplu in ordine lexicografica, cu ajutorul mastii de convolutie, rotita cu 180 . Pentru fiecare pixel de iesire, de coordonate (m,n) se calculeaza suma ponderata a pixelilor din imaginea de intrare, aflati sub masca de convolutie deplasata cu originea la coordonatele (m,n). Ponderea fiecarui pixel este specificata de coeficientul care i se suprapune din masca. Rotirea cu 180 a mastii este consecinta (neesentiala a) semnului minus din ecuatia de definitie a convolutiei, fiind introdus in definitie pentru conveniente teoretice.

Se observa ca imaginea de iesire are dimensiunile extinse cu L-1 elemente pe ambele directii. Nu toate elementele suplimentare sunt utile in general. Un exemplu clarifica mai usor motivul.

Fig. 3.1. Geometria procesului de convolutie

De exemplu, sa presupunem ca operatorul 3 3 din Fig. 3.1 este

(3.12)

Operatorul este denumit operator de mediere aritmetica sau filtru uniform in varianta cauzala (originea este marcata). Fiecare element al imaginii de iesire este media aritmetica a pixelilor dintr-o regiune de 3 3 pixeli. Primul element din imaginea de iesire este g_0,0=(1/9)f_0,0 si provine din medierea pixelului f_0,0 cu opt zerouri din fundal. Este, evident, un pixel afectat de eroare. Toti pixelii de iesire pentru care masca de convolutie nu este integral suprapusa pe imaginea de intrare vor avea valori mai mici decat media aritmetica a 9 pixeli de intrare. In principiu, calculul acestor elemente ale imaginii de iesire poate fi omis. Totusi, din punct de vedere practic, este adesea inconvenabil sa restringem imaginea de iesire, G, la dimensiunile N L-1)/2] N L-1)/2]. Ar fi preferabil sa pastram formatul de imagine, N N al imaginii de intrare, F. In acest caz, avem de rezolvat problema erorilor de margine reprezentate umbrit in Fig.4.1. Solutia consta in extinderea imaginii de intrare prin continuitate (exemplu repetarea sau oglindirea liniilor sau coloanelor).