Cristian Grava Vasile Buzuloiu

ELEMENTE DE PRELUCRAREA

I ANALIZA IMAGINILOR

2007

2

EDITURA UNIVERSITII DIN ORADEA

Descrierea CIP a Bibliotecii Naionale a Romniei

GRAVA, CRISTIAN Elemente de prelucrarea i analiza imaginilor /

Cristian Grava, Vasile Buzuloiu. Oradea : Editura Universitii din Oradea, 2007 ISBN 978-973-759-377-1

I. Buzuloiu, Vasile 621.397.3 (075.8)

EDITURA UNIVERSITII DIN ORADEA ESTE ACREDITAT DE CNCSIS, COD 149.

3

Cuprins:

Prefa 7 1. Introducere . 9 2. Reprezentarea imaginilor ... 12

2.1. Digitizarea imaginilor . 12 2.2. Eantionarea imaginilor .. 15 2.3. Reprezentarea spaial a imaginilor 20 2.4. Proprieti ale imaginilor digitale ... 25

2.4.1. Proprieti metrice ale imaginilor digitale . 26 2.4.2. Proprieti topologice ale imaginilor digitale 27 2.4.3. Relaii de vecintate ntre pixeli 28 2.4.4. Paradoxuri de conexitate ... 31 2.4.5. Alte proprieti topologice i geometrice ... 33

2.5. Reprezentarea spectral a imaginilor ... 34 2.5.1. Transformata Fourier (TF) bidimensional ... 36 2.5.2. Proprietile transformatei Fourier bidimensionale ... 36 2.5.3. Proprieti specifice TF bidimensionale 43

3. mbuntirea imaginilor 52 3.1. Calitatea unei imagini . . 52 3.2. Tehnici de mbuntire a imaginilor 55 3.3. Operatori punctuali de mbuntire a imaginilor 57

3.3.1. Operatori punctuali de modificare a contrastului 58 3.3.2. Decuparea intervalelor de niveluri de gri 62 3.3.3. Modificarea histogramei . 64

3.4. Operatori liniari de vecintate pentru mbuntirea imaginilor. Filtrarea liniar a imaginilor . 68

3.5. Efectul n frecven al operatorilor liniari de vecintate .. 73 3.6. Filtrarea neliniar a imaginilor . 76

3.6.1. Filtre neliniare de ordine . 77 3.6.2. Filtre de ordine multi-etaj 79 3.6.3. Proprieti ale filtrelor de ordine . 81

4

3.6.4. Filtre de ordine de domeniu 83 3.6.5. L-filtre 85

4. Transformri integrale ale imaginilor . 87 4.1. Transformri integrale unitare . 87 4.2. Matrici unitare . 93 4.3. Transformri unitare ale unor semnale unidimensionale 98 4.4. Transformri unitare ale unor semnale bidimensionale .. 100 4.5. Transformata Fourier discret unidimensional (DFT-1D) . 104 4.6. Proprieti ale transformatei DFT-1D .. 105 4.7. Transformata Fourier discret bidimensional (DFT-2D) .... 108 4.8. Proprieti ale transformatei DFT-2D .. 111 4.9. Transformata Cosinus discret unidimensional . 113 4.10. Transformata Cosinus discret bidimensional 115 4.11. Transformata Sinus discret unidimensional .. 120 4.12. Transformata Sinus discret bidimensional . 121

5. Restaurarea imaginilor 122 5.1. Filtrarea invers 123 5.2. Filtrul invers cu constrngeri ... 125

6. Morfologie matematic ... ... 130 6.1. Transformarea Hit or Miss .. 130 6.2. Erodarea . 132 6.3. Dilatarea .. 134 6.4. Proprietile operaiilor morfologice ... 136 6.5. Transformri morfologice derivate . 138

6.5.1. Operatori de extragere a conturului .. 138 6.5.2. Deschiderea i nchiderea .. 140

6.6. Trierea dimensional a obiectelor 142 6.7. Caracterizarea morfologic a formelor 143

6.7.1. Reconstrucia dup marker 144 6.7.2. Distana Haussdorf 145 6.7.3. Extragerea skeletonului morfologic .. 145 6.7.4. Skeletonul generalizat 149

6.8. Extinderea morfologiei matematice la imagini cu niveluri de gri.. 151

5

6.8.1. Trecerea de la mulime la funcie 152 6.8.2. Trecerea de la funcie la mulime 153 6.8.3. Operaii cu funcii .. 154

7. Segmentarea imaginilor .. 157 7.1. Segmentarea orientat pe regiuni .. 157

7.1.1. Etichetarea componentelor . 158 7.1.2. Metoda arborelui cuaternar (quad-tree) . 159

7.2. Segmentarea imaginilor cu niveluri de gri 161 7.2.1. Segmentarea bazat pe histogram . 161 7.2.2. Segmentarea bazat pe creterea i fuziunea regiunilor .. 165

7.3. Segmentarea orientat pe contururi . 168 7.3.1. Operatori de tip gradient 169 7.3.2. Operatori de tip compas 173

8. Compresia imaginilor . 176 8.1. Compresia imaginilor binare 177

8.1.1. Codarea de nivel nalt . 177 8.1.1.1. Aproximri poligonale . 177 8.1.1.2. Codul Freeman . 178 8.1.1.3. Descriptori Fourier 181

8.1.2. Codarea la nivel de bloc . 183 8.1.2.1. Metoda arborelui cuaternar (Quad-tree) 183 8.1.2.2. Metoda WBS (White Block Skipping) . 184

8.1.3. Codarea la nivel de bit 185 8.1.3.1. Codarea RLE (Run Length Encoding) .. 185 8.1.3.2. Codarea entropic (Huffman) 186

8.2. Compresia imaginilor cu niveluri de gri 188 8.2.1. Codarea pe plane . 188 8.2.2. Metode predictive de compresie . 190 8.2.3. Compresia cu transformate . 194

Bibliografie .. 204

6

7

Prefa Prelucrarea i analiza imaginilor ajunge pe zi ce trece, tot mai mult, n categoria bunurilor de larg consum ca urmare a aceleiai mutaii suferit de calculatoarele electronice care reprezint suportul hard i soft al acestui domeniu relativ nou dar devenit indispensabil, al existenei sociale contemporane. Numai c, fr ndoial, nu se rezum la suport: analiza i prelucrarea imaginilor i prin extensie, a secvenelor video, a semnalelor multimedia i, mai general, a semnalelor multidimensionale nseamn n primul rnd algoritmi; algoritmi de prelucrri i algoritmi de analiz. i, ajungnd aici, ne dm seama c, n fapt, avem de-a face cu modelare matematic. Cndva, pe vremea bunicilor bunicilor notri, adic n zorii epocii moderne din istoria omenirii, cu arta aceasta se ocupau doar genii de prim rang un Galilei, Newton, Leibnitz dar numrul celor ocupai cu modelarea matematic a crescut vertiginos n secolul XIX i apoi al XX-lea astfel nct astzi, cum nvmntul universitar a ajuns nvmnt de mas, modelarea matematic a ajuns i ea n nvmntul de mas; adic s-ar vrea un bun de larg consum. Numai c n matematic nu exist cale regal adic pe care s naintezi fr efort (asta o tim nc din antichitate: i-a spus-o mentorul su mpratului Alexandru cel Mare!). Cele de mai sus se vor o justificare a faptului c aceast carte, care este i un suport de curs pentru studenii ingineri ai Universitii din Oradea dar poate fi i o lectur util pentru toi cei interesai de subiect, conine pagini ntregi de matematic, constituind subiecte alese din nevoile disciplinei. n mod ideal, o carte de prelucrarea i analiza imaginilor de sine stttoare ar trebui s aib un material imagistic ilustrativ, mult mai bogat. Rabatul pe care l facem de la acest deziderat este justificat prin faptul c materia unui astfel de curs nu se rezum la teorie ci are drept component principal i partea de aplicaii, n faa ecranului: n felul acesta studentul testeaz pe viu ce influen au asupra rezultatelor modificrile n algoritmi i vede cum se modific imaginea. De asemenea, ne-am decis s folosim n titlu un partitiv Elemente de fiindc de fapt cartea este doar o uoar introducere ntr-un domeniu astzi deja vast, care conine printre multe altele, tehnicile de restaurare a

8

imaginilor (din care fac parte cele de reconstrucie a imaginilor din proiecii care stau la baza imagisticii medicale, a defectoscopiei nedistructive i a teledeteciei satelitare), ustensilele software pentru fotografia digital (ne mrginim la un singur exemplu: corecia n timp real a ochilor roii) i tot felul de sisteme de supraveghere a cror component principal trebuie s fie una capabil de recunoatere a formelor (maini, fee etc). n pofida faptului c prelucrarea i analiza imaginilor este, cum se zice azi, un domeniu de vrf, noi am fost activi n el de mai bine de 30 de ani datorit cercetrilor de televiziune digital i prelucrare n timp real a semnalului digital n colectivul de cercetare al Catedrei de Electronic Aplicat de la Politehnica din Bucureti; primul sistem digital de analiz a imaginilor a fost terminat n 1981 iar n urmtorii ani a fost reprodus n cteva exemplare la Fabrica de Calculatoare Electronice. Perioada anilor 80 n-a fost, din pcate, propice dezvoltrilor tehnologice la noi i astfel ntietatea i avantajul pe care apucaserm s l avem n lagrul socialist, n-a dat roade. Dup 1990 ne-am trezit ntr-o lume care ntre timp progresase mult n acest domeniu. Totui, experiena pe care o avem ne-a permis s relum ideile iar astzi, Laboratorul de Analiza i Prelucrarea Imaginilor LAPI al Politehnicii din Bucureti este destul de bine cunoscut i peste hotare; mai mult, transplantul cunotinelor l-am fcut i spre alte universiti Braov, Oradea i aa se face c astzi, n Catedra de Electronic a Universitii din Oradea exist un colectiv important de cadre tinere implicate n acest domeniu, cu stagii n strintate i colaborri internaionale. Avem toate condiiile preliminare pentru un nvmnt responsabil. Cartea de fa, scris aproape n totalitate de Cristian Grava, adun elementele eseniale ale unui curs introductiv dar presupune c studentul cititorul a fost expus nainte unor cursuri pregtitoare printre care cel de teoria statistic a semnalelor, cel de sisteme liniare i cursurile fundamentale de matematic pentru ingineri. Ar mai fi de remarcat c, pentru compactizarea materialului s-a preferat o niruire neliniar a subiectelor, care de exemplu n capitolul 2 trimite la capitolul 4 dar, fiind vorba de subiecte reluate de la cursuri anterioare, suntem convini c cititorul va putea parcurge textul fr dificulti, cel mult eventual cu reluri.

Prof. Vasile Buzuloiu

9

1. Introducere

Dezvoltarea spectaculoas din ultimii ani a tehnologiei informaiei

i a componentelor electronice a condus la impunerea de soluii inimaginabile pn nu demult pentru numeroase probleme tehnice, ca de exemplu n industrie la conducerea proceselor de producie sau la controlul de calitate. Tehnicile de exploatare a informaiei vizuale ocup o poziie important i de extrem actualitate. Domeniul prelucrrii i analizei imaginilor grupeaz tehnicile de achiziie, transformare i utilizare a informaiei vizuale din imaginile reprezentate, transmise i exploatate n form digital, n sisteme de calcul de uz general sau calculatoare specializate.

Printre aplicaiile importante ale prelucrrii i analizei imaginilor se pot aminti aplicaiile n medicin (investigarea de organe ale corpului uman), aplicaii n industrie i n tehnic (cartografierea solului, prospeciuni geologice, controlul tehnic automat al diverselor produse, robotic etc.) precum i aplicaii dedicate unor domenii ca arta, aplicaiile militare etc.

Principalele probleme ale prelucrrii i analizei de imagini sunt: 1. Reprezentarea i modelarea imaginilor:

Eantionarea i cuantizarea imaginilor Reprezentarea spaial a imaginilor Reprezentarea spectral a imaginilor. Transformata Fourier

TransformareImagine discretizat

Imagine transformat

Prelucrarea se face asupra

acestei imagini

Figura 1.1. Transformarea unei imagini.

10

Modelele imaginilor pot fi: stohastice; deterministe.

2. mbuntirea imaginilor. Se face prin:

prelucrri punctuale. Exemple: modificarea contrastului i luminanei; modificarea histogramei.

prelucrri pe vecinti. Exemple: accentuarea contururilor; reducerea zgomotului imaginilor; pseudo-colorarea.

prelucrri geometrice. prelucrri integrale.

3. Restaurarea imaginilor. Presupunem c f(x,y) este imaginea original

care datorit procesului de captare a suferit o transformare (degradare), liniar sau neliniar, obinndu-se imaginea degradat fd(x,y).

f(x,y) fd(x,y)

transformare

transformare-1 Figura 1.2. Transformarea invers a unei imagini.

Imaginea original se poate obine din imaginea degradat prin aplicarea unei transformri inverse celei suferite n procesul de captare. Apar probleme cnd n procesul de captare intervine i zgomot, caz n care se impune i o etap de restaurare a imaginii, pentru a se obine o

aproximare a imaginii originale (x,y)f :

11

Transformare + Restaurare

f(x,y)

zg=zgomot

f (x,y) fd(x,y)+zg

Figura 1.3. Restaurarea imaginilor.

Reconstrucia imaginilor din proiecii.

4. Analiza imaginilor, care implic:

msurtori automate pe imagini; segmentarea imaginilor (extragerea obiectelor).

5. Compresia imaginilor, care implic reducerea cantitii de informaie. Exemplu: Pentru o imagine de 512512 pixeli (2929), n care fiecare pixel este reprezentat pe 8 bii, adic cu 28=256 niveluri de gri, cantitatea de informaie este: (2929)pixeli23bii/pixel=221 2 Mb Prin compresia imaginilor se urmrete reducerea acestei cantiti de informaie.

Schema bloc a unui lan de analiza i prelucrarea imaginilor este

prezentat n figura 1.4.

senzor CAD

Compresie

Memorie

mbuntire+ Restaurare

Msurtori date

Segmentare

List de obiecte

Msurtori pe obiecte

Clasificare Descrierea scenei

Scen

CAD = convertor analog-digital

Display Display

Figura 1.4. Schema bloc a unui lan de analiza i prelucrarea imaginilor.

12

2. Reprezentarea imaginilor Sistemele vizuale ale organismelor vii percep mediul nconjurtor 3-dimensional, prin intermediul unor latici de senzori de lumin bidimensionale (de exemplu, retina din ochii mamiferelor) i refac spaiul 3D prin integrare temporal i/sau vedere binocular. n pofida faptului c senzaia este de cmp continuu al imaginilor percepute, laticea senzorilor este discret. n sistemele tehnice imaginate de om, aceste proprieti se pstreaz: informaia imagistic din mediul nconjurtor se proiecteaz pe latici bidimensionale de senzori de lumin i astfel se discretizeaz spaial, iar semnalele de la fiecare senzor se discretizeaz n timp i n valoare astfel nct imaginile ajung n sistemele de calcul sub form digital, pentru prelucrare i analiz.

2.1. Digitizarea imaginilor Imaginile pot fi descrise de distribuia spaial a intensitii luminoase ntr-un plan. Din punct de vedere matematic, distribuia spaial a intensitii luminoase (I) poate fi descris printr-o funcie continu de dou variabile spaiale continue (x,y)=p:

I(x,y)=I(p)

Calculatoarele existente nu pot trata imaginile ca funcii definite pe un domeniu continuu ci doar ca matrici discrete de numere. Din acest motiv este necesar transformarea i reprezentarea imaginilor continue ca matrici bi-dimensionale de puncte, prin discretizare. Un punct al unei astfel de matrice se numete pixel (din englez = picture element). Un pixel reprezint intensitatea luminoas sau culoarea corespunztoare unui anumit punct din matrice. Prin urmare, un pixel este caracterizat prin poziia i prin valoarea sa.

13

Pentru tratri teoretice, imaginea bidimensional poate fi reprezentat ca o funcie continu (analogic) bidimensional I(x,y)=f(x,y), unde x i y sunt coordonatele spaiale. Valoarea funciei ntr-un punct oarecare (x,y) va reprezenta: luminana din punctul respectiv, n cazul n care funcia f(x,y) este o

funcie real. n acest caz avem o imagine cu niveluri de gri, numit impropriu i imagine alb-negru;

culoarea din punctul respectiv, n cazul n care funcia f este o funcie vectorial, (f1(x,y),f2(x,y),f3(x,y)) = (R,G,B). n acest caz avem o imagine color, cu componentele fundamentale (R, G, B).

Trecerea de la o imagine color la o imagine cu niveluri de gri se face prin adunarea componentelor fundamentale ponderate cu anumii coeficieni, adic printr-o combinaie liniar a acestor componente.

Pentru prelucrarea digital a imaginilor analogice (de exemplu cu ajutorul unui calculator) este nevoie de discretizarea imaginilor, proces n urma cruia imaginea este transformat ntr-o matrice care conine elementele de imagine (pixel). n practic, camera video de tip CCD (Charge Coupled Device) realizeaz discretizarea imaginilor chiar n procesul de captare. Pentru afiare, imaginile se pot converti din nou n form analogic.

Discretizarea imaginilor analogice se realizeaz n doi pai: discretizarea spaial (eantionarea), cu ajutorul unei reele discrete

f(lx,ky), l,kZ. n urma acestei operaii rezult o imagine (matrice) cu L linii i K coloane: lL, kK. Prin urmare, se obine LK pixeli, iar imaginea obinut se va scrie printr-o expresie de forma:

A={a(l,k), 1lL, 1kK}, l,k,L,KZ;

a11 a12 a1,K a21 a22 a2,K aL,1 aL,2 aL,K

14

discretizarea n valoare (cuantizarea): fq(lx,ky) l,kZ, lL, kK, cu: fq(lx,ky){f1,,fn}, unde n este numrul nivelurilor de cuantizare a imaginii (numrul nivelurilor de gri). De exemplu, pentru n=2 avem o imagine binar.

n acest caz, fiecare eantion obinut n pasul anterior (la eantionare) este cuantizat folosind un numr finit de bii. Astfel, fiecare pixel va avea un anumit nivel de gri (pentru imagini alb-negru) sau o anumit culoare (pentru imagini color), codificat printr-un numr constant de bii.

n reprezentare binar, un pixel oarecare al,k este codat: (al,k)binar=bn-1bn-2b1b0 cruia i corespunde o valoare zecimal:

(al,k)zecimal=bn-12n-1+bn-22n-2++b121+b020=q (2.1)

care reprezint nivelul q din scara de 2n nivele de gri considerate. n mod uzual, negrul este considerat ca avnd nivelul logic 0 (n binar 00 00), iar albul ca avnd nivelul logic 1 (n binar 1111). De exemplu, n cazul unei imagini reprezentate pe 8 bii avem un numr de 28 =256 niveluri de gri, n care negrul este codat cu nivelul q=0, iar albul este codat cu nivelul q=255. Pixelul a34 avnd valoarea codat binar cu octetul 00101001 este pixelul al 4-lea de pe rndul 3 i are nivelul q=41 n scara de niveluri de gri amintit. n continuare, cnd se va vorbi despre imagini digitale sau simplu despre imagini, se va face referire la imagini eantionate i cuantizate, iar cnd se va vorbi despre discretizarea imaginilor se va face referire la discretizarea spaial (eantionarea) i n valoare (cuantizarea) imaginilor.

15

2.2. Eantionarea imaginilor Se consider o matrice de eantionare, cu pasul (x,y) care

transform imaginea dintr-o funcie (continu) ntr-un ir:

( )( ) Zl,kantionaree yx,klff(x,y) s (2.2)

x

y

x

y

Figura 2.1. Matricea de eantionare a unei imagini.

Transformarea invers (din ir n imagine) este posibil n condiiile teoremei eantionrii. Modelul matematic al semnalului eantionat este:

===

n restykyxlxyxf

yxfnot

e

,0,),,(

),(.

(2.3)

==m n

pe yxyxfynyxmxyxfyxf ),(),(),(),(),( , unde:

periodicl k

p ykyxlxyx == ),(),( (2.4) este impulsul Dirac periodic:

==

rest ,00 pt. ,1

)(n

xx (2.5)

16

Transformata Fourier a semnalului eantionat este: { } { }),(),(),(),( yxyxfyxfvuF pee == (2.6) Se tie c dac funcia f(t) este periodic (cu perioada T), seria sa Fourier este:

=k

tkT

jk eCtf

2)( , unde coeficienii: (2.7)

=T

tkT

jk dtetfT

C2

)(1 (2.8)

Din acest motiv, deoarece funcia p(x,y) este periodic cu perioada x pe x, respectiv y pe y:

+=

k l

yly

xkx

j

klp eCyx

22

),( , unde: (2.9)

+= )( )(

22exp),(1

x ypkl dxdyyly

xkx

jyxyx

C (2.10)

Deoarece se integreaz pe un interval x =

2

,2

xx , respectiv

y =

2

,2

yy i dac se presupune c ntr-un dreptunghi cu laturile x,

y cade un singur impuls p i numai unul (cel din origine):

17

lx

ky

y

z

x

Figura 2.2. Eantionarea imaginilor.

+= dxdyylyxkxjyxyxC pkl

22exp),(1 (2.11)

Deoarece: )0()()( fdttft =

, iar n cazul de fa: f(0)=1

yx

C lk =1

, (2.12)

+= k l

yly

xkx

j

p eyxyx

221),( (2.13)

=

+

k l

yly

xkx

j

e eyxfyxvuF

22),(1),( (2.14)

Pe baza proprietii de liniaritate a transformatei Fourier:

=

+

k l

yly

xkx

j

e eyxfyxvuF

22),(1),( (2.15)

18

( ) =

= k lk levlvuku

yxl

yvk

xu

yxvuF ,12,21),(

unde: x

unot

=2. ,

yv

not

=2. (2.16)

Spectrul semnalului eantionat F(u,v) se obine prin periodizarea (repetarea) spectrului su Fe(u,v):

v

F(u,v)

u

v

u

FTJ

v

u

Figura 2.3. Spectrul semnalului eantionat. Recuperarea semnalului original din semnalul eantionat se poate face cu un filtru trece-jos (FTJ) cu parametri adecvai (figura 2.4).

umaxv

u

vmax

u

vv-vmax

u-umax

Figura 2.4. Parametrii FTJ.

19

Parametrii umax, respectiv vmax reprezint frecvenele spaiale maxime din spectrul funciei f, n direcia u, respectiv v (ce corespund coordonatelor spaiale x, respectiv y). Pentru ca semnalul original s fie corect recuperat cu ajutorul unui FTJ, trebuie ca parametrii acestuia s satisfac condiiile:

maxmax

maxmaxvvvuuu

max

maxvvuu

22

(2.17)

Prin urmare, frecvenele de tiere (, ) a FTJ de recuperare a semnalului original n cele dou direcii (u,v), trebuie s ndeplineasc condiiile:

maxmax

maxmaxvvvuuu

(2.18)

Astfel, n acest caz, teorema eantionrii se poate enuna astfel:

dac x

u =2 ,

yv =

2 adic frecvenele de eantionare pe x, respectiv pe y, sunt mai mari sau cel puin egale cu dublul frecvenelor maxime din spectrul lui f pe direcia u, respectiv v, atunci recuperarea semnalului original de imagine f(x,y) se poate face exact, din eantioane, cu un filtru ideal trece-jos cu funcia de transfer:

H(u,v)

fe(x,y) f(x,y)

Figura 2.5. FTJ necesar pentru extragerea semnalului original.

=

restn 0, si pentru,1

),(vu

vuH (2.19)

unde frecvenele de tiere (, ) sunt alese n mod corespunztor, adic astfel nct:

20

maxmax

maxmaxvvvuuu

(2.20)

Observaie:

Condiia de recuperare enunat de teorema eantionrii este suficient dar nu i necesar. Acest lucru este ilustrat de exemplul urmtor:

u

v

u

v

vmax

umax

F(u,v)

H(u,v)

v-vmax

u-umax

Figura 2.6. Caz particular de extragere a semnalului original.

Se observ c dei condiia de recuperare nu este ndeplinit, recuperarea se poate face cu un FTJ ideal corespunztor, care s extrag doar zona corespunztoare spectrului funciei.

2.3. Reprezentarea spaial a imaginilor

Odat digitizate (eantionate i cuantizate), imaginile pot fi prelucrate i analizate cu sisteme de calcul uzuale sau dedicate. Reprezentarea imaginilor se poate face sub diverse forme (spaial, spectral etc.), adecvate diverselor aplicaii.

n cazul cel mai simplu, pixelii sunt localizai pe o reea rectangular. Poziia unui pixel este dat n mod analog notaiei utilizate

21

pentru elementele unei matrice. Primul indice (l) exprim poziia pe linie, iar cel de-al doilea indice (k) exprim poziia pe coloan (figura 2.1).

Cl,k

0 0 1

1

k

l

K-1

L-1

x

y

coloane

linii

Figura 2.7. Reprezentarea imaginilor digitale ca matrici de pixeli dispui

ntr-o reea rectangular bi-dimensional.

Dac imaginea conine LK pixeli, aceasta poate fi reprezentat printr-o matrice de dimensiune LK, unde indicele l=0L-1, iar k=0K-1. L reprezint numrul de linii, iar K numrul de coloane. Ca i n cazul matricilor, sensul pozitiv al axei verticale (y) este de sus n jos i nu de jos n sus, cum este cazul reprezentrilor grafice bidimensionale uzuale. Sensul pozitiv al axei orizontale (x) este cel uzual, de la stnga la dreapta (figura 2.1).

Rezoluia spaial de reprezentare a unei imagini poate fi definit ca reprezentnd numrul total de pixeli (de exemplu LK) sau poate fi definit ca fiind egal cu numrul de pixeli pe unitatea de suprafa (n pixeli/cm2 sau n pixeli/inch2). Rezoluia spaial a unui sistem de achiziie de imagini se poate defini ca fiind egal cu numrul de pixeli pe unitatea de lungime (pixeli/mm sau pixeli/cm). Pe baza acestor noiuni, se mai poate defini i sensibilitatea unui sistem de vedere sau a unui sistem de

22

achiziie de imagini, ca fiind unitatea minim de lungime care poate fi observat ntr-o imagine achiziionat.

Fiecare pixel reprezint nu numai un punct al unei imagini, ci o regiune rectangular a acesteia, care definete o celul elementar a imaginii. Valoarea asociat unui pixel reprezint n mod adecvat media intensitii luminoase din celula corespunztoare. n figura 2.8 este ilustrat una i aceeai imagine, reprezentat printr-un numr diferit de pixeli.

(a) (b)

(c) (d)

Figura 2.8. Imagine digital cu diferite rezoluii: (a) - 1616 pixeli; (b) - 3232 pixeli; (c) - 6464 pixeli; (d) - 256256

pixeli. n cazul unor pixeli de dimensiune mare (figura 2.8.a i 2.8.b), nu

numai c rezoluia spaial este mic, dar apar nite artefacte (zgomote)

23

deranjante datorate discontinuitilor de niveluri de gri de la marginile pixelilor, care distrag atenia privitorului de la coninutul propriu-zis al imaginii. Atunci cnd dimensiunea pixelilor devine mai mic, adic atunci cnd crete rezoluia spaial (figura 2.8.c i 2.8.d), efectele descrise mai sus devin mai puin pronunate, putndu-se ajunge pn la impresia de continuitate spaial a imaginii. Acest lucru de ntmpl cnd rezoluia spaial a imaginii devine mai mare dect rezoluia sistemului uman de vedere, adic atunci cnd dimensiunea unui pixel al imaginii devine mai mic dect dimensiunea minim pe care o poate percepe ochiul uman.

Nu exist un rspuns general valabil legat de numrul optim de pixeli necesar pentru a crea senzaia de continuitate spaial a unei imagini. n cazul observrii vizuale a unei imagini, trebuie ca dimensiunea unui pixel s fie mai mic dect dimensiunea corespunztoare rezoluiei spaiale a sistemului vizual, la o distan nominal a observatorului. n cazul unei aplicaii concrete, dimensiunea unui pixel trebuie s fie obligatoriu mai mic dect dimensiunea celui mai mic obiect pe care dorim s l vizualizm. n general, ntr-o aplicaie dat, cel care impune o limit a numrului de pixeli este sistemul de achiziie a imaginilor. De exemplu, chiar dac se utilizeaz sisteme de achiziie cu o rezoluie ridicat, de 10001000 = 1 milion de elemente, rezoluia spaial relativ este de 10-3. Aceasta poate fi considerat o rezoluie slab, deoarece n cazul msurrii unei lungimi, a unei tensiuni electrice sau a unei frecvene, o rezoluie sau o precizie satisfctoare ncepe de la 10-6. ns, n cazul msurrii unor astfel de mrimi uni-dimensionale, se efectueaz msurtori relativ la un singur punct, n timp ce o imagine de 10001000 conine un milion de puncte. Prin urmare, o imagine poate oferi informaii referitoare la variaia spaial a unui semnal. n plus, dac se achiziioneaz secvene temporale de imagini, se pot obine informaii care nu sunt accesibile dintr-o imagine static. Astfel se pot obine informaii legate de variaiile temporale ale unui semnal i prin urmare se poate studia cinematica i dinamica temporal a acestuia.

24

O reea rectangular reprezint cea mai simpl, dar i cea mai rspndit geometrie a unei imagini digitale. Pe lng aceasta, mai exist i alte aranjamente geometrice ale pixelilor sau alte forme ale celulelor elementare. Aceste forme i dispuneri geometrice sunt similare configuraiilor cristaline posibile n cazul corpurilor solide 3D n fizic, chimie sau mineralogie. Dac se iau n considerare doar poligoane regulate, exist doar trei forme de reele regulate posibile: triunghiulare, ptrate sau hexagonale (figura 2.9).

Figura 2.9. Forme de reele regulate posibile n 2D:

(a) - reea triunghiular; (b) - reea ptrat; (c) reea hexagonal. n cazul imaginilor 3D, pixelul se transform n voxel (din englez = volume element). ntr-o reea rectangular, fiecare pixel reprezint valoarea medie a nivelului de gri (sau de culoare) dintr-un cub elementar. Poziia unui voxel este indicat prin trei indici: un indice de linie (l), un indice de coloan (k) i un indice (m) pentru adncime (figura 2.10).

25

y

x

z

l

k

m

Figura 2.10. Reprezentarea imaginilor digitale ca matrici de voxeli

dispui ntr-o reea rectangular tri-dimensional.

2.4. Proprieti ale imaginilor digitale Imaginile digitale au unele proprieti, metrice sau topologice, diferite de proprietile funciilor bidimensionale continue. Pe baza celor prezentate pn n acest punct, se pot trage urmtoarele concluzii: o imagine digital este format din elemente de imagine (pixeli) de

dimensiune finit; n mod uzual, pixelii sunt aranjai sub forma unei reele rectangulare; o imagine digital reprezint o matrice bidimensional a crui

elemente sunt numere ntregi care corespund nivelurilor de cuantizare a gamei de niveluri de gri.

unele proprieti ale imaginilor continue nu au o analogie direct n domeniul imaginilor digitale.

26

2.4.1. Proprieti metrice ale imaginilor digitale

Distana dintre doi pixeli dintr-o imagine digital reprezint o

mrime cantitativ. Distana dintre punctele de coordonate (i,j) i (k,l) poate fi definit n diferite moduri: distana euclidian:

[ ] ( ) ( )22),(),,( ljkilkjid E += (2.21)

Avantajul distanei euclidiene este faptul c este intuitiv, dar are dezavantajul unui cost mare de calcul datorit radicalului din formul i datorit valorii nentregi care rezult i deci a interpolrii necesare.

Distana dintre dou puncte poate fi exprimat i prin numrul minim de pai elementari de pe reeaua discret, dintre punctul de start i punctul final.

Dac sunt permise doar deplasri orizontale i verticale, se poate defini distana d4 sau distana interbloc:

[ ] ljkilkjid +=),(),,(4 (2.22)

Aceast distan este similar distanei dintre dou locaii dintr-un ora cu o reea rectangular de strzi i blocuri nchise de cldiri.

Dac sunt permise i deplasri diagonale, se poate defini distana d8 sau distana de tip ah:

[ ] { }ljkilkjid = ,max),(),,(8 (2.23)

27

2.4.2. Proprieti topologice ale imaginilor digitale Adiacena pixelilor este un concept important n prelucrarea imaginilor digitale. Oricare doi pixeli sunt vecini n sensul distanei d4 dac exist o distan d4 =1 ntre cei doi pixeli. n mod analog, doi pixeli sunt vecini n sensul distanei d8 dac exist o distan d8=1 ntre cei doi pixeli. Cele dou tipuri de vecinti sunt ilustrate n figura de mai jos:

V4 V8

Figura 2.11. Vecintatea V4 i V8. Pe baza adiacenei pixelilor se pot defini regiunile, ca mulimi conexe de pixeli adiaceni. O cale dintre un pixel P i Q este o secven de puncte A1, A2, , An, unde A1=P i An=Q, iar Ai+1 este vecin cu Ai, i=1, ,n. O regiune reprezint o mulime de pixeli n care exist o cale ntre oricare pereche de pixeli ai si, iar pixelii acelei ci sunt inclui i ei n mulimea respectiv. Dac exist o cale ntre doi pixeli ai unei imagini, aceti pixeli sunt coneci. Relaia de conexitate este reflexiv, simetric i tranzitiv i definete o descompunere a mulimii (n cazul de fa imaginea) n clase echivalente (regiuni). S presupunem c Ri sunt regiuni disjuncte din imagine i c aceste regiuni nu ating marginile imaginii (pentru a evita cazurile speciale). Fie R reuniunea tuturor regiunilor Ri. Fie RC complementara mulimii R n raport cu imaginea.

28

Submulimea lui RC care este conex n raport cu marginile imaginii se numete fundal, iar restul mulimii RC se numesc guri. Dac nu avem guri ntr-o regiune, aceasta se numete regiune simplu conex. O regiune cu guri se numete regiune multi-conex.

Trebuie observat faptul c noiunea de regiune implic doar proprietatea de conexitate. Regiunilor li se pot atribui proprieti secundare care i au originea n interpretarea imaginilor. Astfel, unele regiuni din imagine se numesc obiecte. Procesul prin care se determin care regiuni dintr-o imagine corespund fiecrui obiect se numete segmentarea imaginilor. De exemplu, nivelul de gri al unui pixel reprezint o proprietate simpl care poate fi utilizat pentru a defini obiectele dintr-o imagine. Dac un pixel are un nivel de gri mai mare dect anumite praguri predefinite, el aparine unui anumit obiect. Toate punctele care satisfac aceast proprietate i care sunt conexe, constituie un obiect. O gaur const din punctele care nu aparin unui obiect i sunt nconjurate de obiecte. Toate celelalte obiecte constituie fundalul. Un exemplu l constituie un text negru pe o pagin alb, n care literele reprezint obiectele. Regiunile albe nconjurate de litere reprezint guri (de exemplu n interiorul literei O). Toate celelalte regiuni ale hrtiei reprezint fundal.

2.4.3. Relaii de vecintate ntre pixeli Una din proprietile importante ale imaginilor discrete este reprezentat de relaiile de vecintate dintre pixeli, deoarece pe baza acestora se pot defini regiunile conexe i obiectele. ntr-o reea rectangular bidimensional se pot defini dou tipuri de vecinti ale pixelilor (figura 2.12.a i 2.12.b ).

29

l-1, k

l, k l, k+1

l+1, k

l, k-1

l-1, k

l, k l, k+1

l+1, k

l, k-1

l-1, k+1l-1, k-1

l+1, k+1l+1, k-1

Figura 2.12. Vecinti definite pe o reea rectangular:

(a) - vecintatea V4; (b) - vecintatea V8.

Definirea acestor vecinti se poate face i pe baza unor relaii matematice, dar pentru moment vor fi definite ntr-un mod simplu, pentru o mai bun nelegere. Astfel, se poate spune despre doi pixeli c sunt vecini dac au cel puin o latur comun. n acest caz un pixel va avea 4 vecini, obinndu-se vecintatea V4 (figura 2.12.a). Se poate defini i o alt vecintate, n cadrul creia doi pixeli sunt vecini dac au cel puin un col comun. n acest caz, un pixel va avea 8 vecini, obinndu-se vecintatea V8 (figura 2.12.b). Ambele tipuri de vecintate sunt necesare pentru a defini obiectele i regiunile conexe. Se spune despre o regiune (sau un obiect) c este conex atunci cnd se poate ajunge de la un pixel la oricare alt pixel al regiunii, trecnd doar de la un pixel vecin la altul. De exemplu, obiectul gri din figura 2.13 reprezint un obiect n sensul unei vecinti V8, dar este constituit din dou obiecte n sensul unei vecinti V4.

Figura 2.13. Regiunea gri reprezint un obiect (sau regiune conex) dac

se utilizeaz o vecintate V8 i dou obiecte dac se utilizeaz o vecintate V4.

30

Acelai lucru se poate afirma i despre fundalul alb din figura 2.13. Pentru a se putea face o distincie clar ntre fundal i obiectele din figur se poate defini o vecintate V4 n cazul obiectelor i o vecintate V8 n cazul fundalului sau invers. Aceste complicaii nu apar numai n cazul reelelor rectangulare. n cazul unei reele triunghiulare se poate defini o vecintate V3 pentru pixelii care au n comun cte o latur i o vecintate V12 pentru pixelii care au n comun cte un col (figura 2.9). n cazul unei reele hexagonale se poate defini numai o vecintate V6 deoarece toi pixelii care au n comun un col, au n comun i o latur, iar pixelii care au n comun o latur, au n comun i dou coluri. n ciuda acestor dezavantaje, reelele hexagonale sunt utilizate n mod curent n prelucrarea imaginilor dei sistemele de achiziie a imaginilor genereaz, de regul, imagini ai cror pixeli sunt dispui ntr-o reea rectangular. Motivul l reprezint dispunerea sub form hexagonal a senzorilor din retina ochiului uman. n cazul tri-dimensional, relaiile de vecintate sunt mai complexe. n acest caz exist trei moduri de definire a vecintilor: voxeli cu fee comune, cu laturi comune sau cu coluri comune. n cazul unei reele rectangulare, aceste enunuri permit definirea unei vecinti V6, V18, respectiv V26 (figura 2.14).

l l l

k

l+1

l-1 k

m-1 k+1 k-1

m

Figura 2.14. Cele trei tipuri de vecinti posibile ntr-o reea cubic 3D:

(a) - V6: voxeli cu fee comune; (b) - V18: voxeli cu laturi comune; (c) - V26: voxeli cu coluri comune.

31

i n acest caz trebuie definite dou tipuri de vecinti pentru obiecte i pentru fundal, pentru a putea defini n mod corect regiunile conexe. Astfel, n cazul obiectelor se poate utiliza o vecintate V6, iar n cazul fundalului se poate utiliza o vecintate V26 sau invers.

2.4.4. Paradoxuri de conexitate Definiia vecintii i conexitii pe o reea rectangular creeaz unele paradoxuri. Exemplul 1. n figura urmtoare sunt reprezentate trei linii digitale cu pante de 45o, respectiv -45o.

Figura 2.15. Exemplu de paradox de conexitate a liniilor.

Dac se utilizeaz vecintatea V4, liniile nu sunt conexe n fiecare punct al lor. Mai mult, apar i conflicte n raport cu nelegerea intuitiv a proprietilor liniilor. Astfel, dou linii perpendiculare se intersecteaz ntr-un caz (stnga-jos), dar nu se intersecteaz n alt caz (dreapta-sus), deoarece nu au un punct comun.

32

Exemplul 2. n figura urmtoare este prezentat un alt paradox. A

BC

D

Figura 2.15. Exemplu de paradox de conexitate a curbelor sau regiunilor.

Acest paradox este cunoscut n geometria euclidian, unde fiecare curb (sau regiune) nchis divide planul n dou regiuni neconexe. Dac imaginea este digitizat ntr-o reea ptrat, utiliznd vecintatea V8, se poate trasa o linie din partea intern a unei curbe nchise pn n partea extern, care nu intersecteaz curba. Aceasta implic faptul c prile interne i externe ale curbei constituie o singur regiune conex.

Exemplul 3 (paradoxul conectivitii). Dac se presupune vecintatea (conexitatea) V4, figura de mai sus conine patru regiuni separate conexe A, B, C i D. A B sunt neconexe, la fel ca i C D, ceea ce reprezint o contradicie topologic deoarece, n mod intuitiv, dac A B sunt neconexe, ar trebui ca C D s fie conexe. Dac se presupune vecintatea V8, exist dou regiuni A B i C D. Cele dou mulimi conin n ntregime cile AB i CD, dar acestea se intersecteaz! O soluie de eliminare a paradoxului conexitii este de a trata obiectele utiliznd vecintatea V4 iar fundalul utiliznd vecintatea V8 sau invers.

Problemele prezentate sunt tipice reelelor rectangulare. Reelele hexagonale rezolv o mare parte a acestor probleme dar au, la rndul lor, numeroase dezavantaje. Astfel, din motive de simplitate, majoritatea

33

dispozitivelor de digitizare utilizeaz o reea rectangular, n ciuda dezavantajelor i paradoxurilor prezentate. O alternativ pentru eliminarea problemelor de vecintate sau conexitate este de a utiliza topologia discret, considernd familii de mulimi de diferite dimensiuni. De exemplu, punctele (0-dimensionale) pot fi atribuite unor mulimi care s conin structuri de dimensiuni mai mari (ca de exemplu, mulimi de pixeli), care permit eliminarea paradoxurilor expuse. Liniile (1-dimensionale) permit o definiie precis a muchiilor i contururilor etc.

2.4.5. Alte proprieti topologice i geometrice Frontiera unei regiuni R este o mulime de pixeli din regiune, care au unul sau mai muli vecini n exteriorul regiunii. Aceast definiie se refer la frontiera intern, pentru a o distinge de frontiera extern, care reprezint frontiera fundalului (complementarei) regiunii. Muchia este o proprietate a unui pixel i a vecintii sale imediate, caracterizat de o amplitudine i o direcie. Direcia unei muchii este perpendicular pe direcia gradientului care indic direcia de variaie a nivelului de gri din imagine. Frontiera este un concept global relativ la o regiune, n timp ce muchia exprim o proprietate local a funciei de variaie a nivelului de gri dintr-o imagine. Cu toate acestea, ntre muchii i frontiere exist o legtur. Astfel, o posibilitate de a determina frontierele este de a concatena muchiile semnificative (punctele caracterizate de un gradient mare al funciei de variaie a nivelului de gri). Proprietatea de a aparine unei muchii este caracteristic unui pixel i vecinilor si. Uneori este avantajos s se utilizeze proprieti ale unor perechi de pixeli vecini. Astfel se poate introduce noiunea de muchie compus, ataat fiecrui pixel, care exprim relaia sa cu cei 4 vecini. Direcia muchiilor compuse este cea de cretere a nivelului de gri i este

34

un multiplu de 90o, n timp ce amplitudinea sa reprezint diferena absolut dintre nivelurile de gri ale perechilor relevante de pixeli. Pentru descrierea proprietilor geometrice ale obiectelor se utilizeaz contururi convexe. Un contur convex este cea mai mic regiune care conine un obiect, astfel nct oricare dou puncte ale regiunii pot fi unite printr-o linie dreapt, toate punctele liniei aparinnd regiunii.

Un obiect poate fi reprezentat printr-o colecie a componentelor sale topologice. Mulimile de puncte din interiorul contururilor convexe, care nu aparin unui obiect, sunt numite deficit de convexitate.

2.5. Reprezentarea spectral a imaginilor Reprezentarea spectral a imaginilor este util n analiza spectral a acestora. Analiza spectral ofer informaii despre modul de variaie a unui semnal. De exemplu, un semnal unidimensional (1D) lent variabil are un spectru concentrat n jurul originii, n timp ce un semnal rapid variabil, are un spectru mai larg.

t

f(t) |F()|

t

f(t) |F()|

Figura 2.16. Ilustrarea spectrului unui semnal lent i a unuia rapid variabil.

35

n cazul imaginilor (2D) se poate determina dac are sau nu contururi multe, prin inspecia spectrului su, pornind de la constatarea c variaiile rapide (frecvenele mari) corespund contururilor. Spectrul unui semnal (sau al unei imagini) se obine prin transformata Fourier a acestuia.

Transformata Fourier unidimensional se definete astfel:

{ }

== )()()( . Fdtetftf tjdef , CR :f (2.24)

Transformata Fourier { } )()( . Ftf not= se definete pentru funciile f(t)L2, unde L2 este clasa semnalelor (funciilor) de energie finit, pentru care exist transformat Fourier direct i invers, adic:

36

2.5.1. Transformata Fourier bidimensional

Definiie: Se consider funcia bidimensional f(x,y), f: RC, unde:

37

)(00 00

22),(),(),(),( yvxuj

FFevuFyyxxfvuFyxf

DD + (2.31) Demonstraie:

{ } ( ) +=2

),(),( 0000R

dxdyeyyxxfyyxxf yvxuj (2.32)

Fcnd schimbrile de variabile: x-x0=x, respectiv y-y0=y, iacobianul corespunztor este:

1

''

''det =

=yy

xy

yy

xx

I (2.33)

{ } ( )[ ] =+++=

2'')'()'(exp)','(),( 0000

RdydxIyyvxxujyxfyyxxf

( )[ ] ( )[ ] =++= 2

''''exp)','(exp 00R

dydxyvxujyxfyvxuj

( )[ ]00exp),( yvxujvuF += q.e.d.

2. Deplasarea spectrului: Dac funciei unidimensionale 1D f(t) i corespunde spectrul

(transformata Fourier) F(), atunci funciei tjetf 0)( i corespunde spectrul deplasat:

)()()()( 01

01 mFetfFtf DD FtjF (2.34)

n cazul bidimensional:

),(),(),(),( 00)( 200

2vvuuFeyxfvuFyxf

DD FyvxujF

mm + (2.35) Demonstraia este lsat ca exerciiu, aceasta fiind similar demonstraiei proprietii 1, de deplasare a semnalului.

38

3. Scalarea semnalului:

Dac funciei f(x,y) i corespunde transformata Fourier F(u,v), atunci funciei scalate ),( byaxf i corespunde transformata Fourier:

bv

auF

baybxafvuFyxf

DD FF,1),(),(),(

22 (2.36)

n cazul unidimensional, acest lucru poate fi ilustrat grafic astfel:

f(t)

t

f(at)

t

Pt. a

39

{ }

=

+=2

,1''''exp)','(),(R b

vauF

badydxI

byv

axujyxfybxaf q.e.d.

4. Liniaritatea:

Dac funciilor f, respectiv g le corespunde transformatele Fourier F, respectiv G, atunci funciei compuse gf + i corespunde transformata Fourier compus:

C++ ,,,, 22 GFgfGFgf DD FF (2.39) Demonstraia este trivial i se face similar proprietii de deplasare a semnalului.

5. Proprietatea de simetrie: Dac funciei f(x,y) i corespunde transformata Fourier F(u,v), atunci funciei simetrice fa de origine ),( yxf , i corespunde un spectru (transformata Fourier) simetric fa de origine:

),(),(),(),(22

vuFyxfvuFyxfDD FF (2.40)

Similar, dac funciei f(x,y) i corespunde transformata Fourier F(u,v), atunci conjugatei funciei simetrice fa de origine ),( yxf , i corespunde un spectru (transformata Fourier) simetric fa de origine, dar rotit cu 1800:

),(),(),(),( **22

vuFyxfvuFyxfDD FF (2.41)

Dac funcia f este real (fR2): ),(),(),(),( ** vuFvuFyxfyxf == (2.42)

40

6. Teorema convoluiei:

Fie funciile bidimensionale CR 2:, gf . Produsul de convoluie al funciilor f i g se definete astfel:

=2

),(),(),(),(.

R ddyxgfyxgyxf def = (2.43)

==2

),(),(),(),(.

Ryxfyxgddgyxf

def (2.44)

Enunul teoremei convoluiei: Dac funciei f(x,y) i corespunde transformata Fourier F(u,v), iar funciei g(x,y) i corespunde transformata Fourier G(u,v), atunci produsului de convoluie a celor dou funcii i corespunde produsul transformatelor Fourier ale celor dou funcii, iar produsului simplu a celor dou funcii i corespunde produsul de convoluie a transformatelor Fourier ale celor dou funcii:

),(),(),(),(2

vuGvuFyxgyxfDF (2.45)

),(),(4

1),(),( 22

vuGvuFyxgyxfDF (2.46)

Demonstraie:

{ } +=2

)(.

),(),(),(),(R

dxdyeyxgyxfyxgyxf yvxujdef

=

+

=

2 2

)(),(),(R R

dxdyeddyxgf yvxuj =

dddxdyeyxgf

vujevuG

yvxuj+

+

=

2

)(

2

),(

)(),(),(R R 4444444 34444444 21

=

41

),(),(),(),(2

)( vuGvuFddefvuG vuj == + R

q.e.d.

7. Teorema lui Parceval:

Fie funciile bidimensionale CR 2:, gf . Dac funciei f(x,y) i corespunde transformata Fourier F(u,v), iar funciei g(x,y) i corespunde transformata Fourier G(u,v), atunci produsului scalar a celor dou funcii i corespunde produsul scalar al transformatelor

Fourier a celor dou funcii, multiplicat cu o constant 241 .

Deci, dac:

),(),(2

vuFyxfDF i ),(),( 2 vuGyxg D

F , (2.47)

atunci:

GFgf ,4

1, 2= (2.48) adic:

GFdudvvuGvuFdxdyyxgyxfgfdef

,4

1),(),(4

1),(),(,2

*2

*

22 === RR

Demonstraie:

+=2

)(2 ),(4

1),(R

dudvevuGyxg yvxuj

+=2

)(*2

* ),(4

1),(R

dudvevuGyxg yvxuj

dxdydudvevuGyxfgf yvxujdef

= +

2 2

)(*2 ),(4

1),(,R R

=

42

dudvdxdyeyxfvuG

vuF

yvxuj

= +

2 2

),(

)(2

* ),(4

1),(R R 44444 344444 21

=

GFdudvvuGvuF ,4

1),(),(4

12

*2 2 == R

q.e.d.

Dac definim energia funciei f ca fiind:

=2

2. ),(R

dxdyyxfEdef

f (2.49)

Teorema energiei (consecin a teoremei lui Parceval): Energia calculat n spaiul original (primar) este egal cu

energia calculat n domeniul spectral, multiplicat cu o constant

241 .

Aceast teorem rezult ca un caz particular din teorema lui Parceval, pentru g=f:

(2.50)

F

Ff

f EdudvvuFvuFdxdyyxfyxfE === 2*

2*

41),(),(

41),(),(

2 22 2 RR44 344 2144 344 21

8. Teorema simetriei:

Dac funciei unidimensionale f(t) i corespunde transformata Fourier F(), atunci transformatei Fourier privit ca funcie de timp F(t) i corespunde transformata Fourier simetric multiplicat cu constanta 2: )(2)()()(

11 ftFFtf DD FF (2.51) Un exemplu este prezentat n figura urmtoare:

43

f(t)

t

f()

F1D F()

F(t)

t

F1D

Figura 2.18. Exemple ilustrative ale teoremei simetriei.

n cazul bidimensional, dac funciei bidimensionale f(x,y) i corespunde transformata Fourier F(u,v), atunci transformatei Fourier privit ca funcie de spaiu F(x,y) i corespunde transformata Fourier simetric multiplicat cu constanta 42: ),(4),(),(),( 2

22vufyxFvuFyxf

DD FF (2.52)

2.5.3. Proprieti specifice transformatei Fourier bidimensionale

9. Separabilitatea: Transformata Fourier bidimensional este separabil:

( )[ ]

+= dxdyyvxujyxfvuF exp),(),( =

( ) dyyvjdxxujyxfyuFx

)exp(exp),(

),(

=

4444 34444 21 =

44

),(),()exp(),( vuFvuFdyyvjyuF xyx ===

(2.53)

Din aceast proprietate rezult c se poate face calculul

transformatei Fourier bidimensionale aplicnd pe rnd (pe cele dou direcii x i y) transformata Fourier unidimensional. Cu alte cuvinte, se aplic transformata Fourier unidimensional pe direcia x, iar asupra rezultatului se aplic transformata Fourier unidimensional pe direcia y:

),(),(),(),( pepe 11 vuFvuFyuFyxf xyyF

xxF DD = sau:

),(),(),(),( pepe 11 vuFvuFvxFyxf yxxF

yyF DD = (2.54)

Proprietatea de separabilitate are urmtoarele consecine:

- Dac se dispune de un algoritm rapid de calcul pentru cazul unidimensional (iar pentru transformata Fourier exist un astfel de algoritm), atunci i pentru transformata Fourier bidimensional exist un algoritm rapid de calcul.

- Dac funcia original se poate scrie ca produsul a dou funcii, transformata sa Fourier este egal cu produsul transformatelor Fourier a celor dou funcii, adic:

Dac: )()(),( 21 yfxfyxf = { }{ }

===

)()(

:unde),()(),(22

1121 yf(v)F

xf(u)FvFuFvuF (2.55)

10. Derivarea spaial:

Dac funciei bidimensionale f(x,y) i corespunde transformata Fourier F(u,v), atunci derivatei funciei f n raport cu cele dou variabile, i corespunde urmtoarele transformate Fourier:

45

),(

),(),(),(

2

2

2

vuFvjyf

vuFujxf

vuFyxfD

D

D

F

F

F (2.56)

Demonstraie:

( )[ ] +=2

exp),(4

1),( 2.

RdudvyvxujvuFyxf

def

(2.57)

( )[ ] ),(exp),(4

122

vuFujdudvyvxujujvuFxf =+=

R

q.e.d.

Aceast proprietate are aplicaii n calculul diferenial, de exemplu la calculul laplaceanului:

22

2

2.),(

yf

xfyxf

def

+

= (2.58)

Deoarece:

FuvuFujx

fvuFujxf DD FF =

22

2

2),()(),( 22

n mod similar: Fvy

f DF = 22

22

),()(),( 222 vuFvuyxf DF += (2.59)

11. Integrarea spaial: Dac funciei bidimensionale f(x,y) i corespunde transformata Fourier F(u,v), atunci integralei funciei f n raport cu cele dou variabile, i corespunde urmtoarele transformate Fourier:

46

)0,(),(

),0(),(),(),( 2

uFdyyxf

vFdxyxfvuFyxf DF (2.60)

Demonstraie:

( )[ ]

+= dxdyyvxujyxfvuF def exp),(),( .

( ) ( )444444 3444444 21

4434421

y

y

dyyvjdxyxfdxdyyvjyxfvF

de functiei aFourier tatransforma

de functie o

exp),(exp),(),0(

==

=

dxyxfvF ),(),0( (2.61)

12. Teorema rotaiei: Dac funciei unidimensionale f i corespunde transformata Fourier F, atunci funciei rotite cu un unghi , f, i corespunde o transformat Fourier rotit n acelai sens i cu acelai unghi .

n cazul bidimensional (deci n cazul unei imagini 2D), dac funciei bidimensionale f(x,y) i corespunde transformata Fourier F(u,v), atunci funciei rotite cu un unghi , f(x,y), i corespunde un spectru rotit n acelai sens i cu acelai unghi .

Rotaia (Rot) conserv liniaritatea i simetriile.

47

x

y

x'

y'

y

x Figura 2.19. Rotaia unui segment de dreapt.

Rotaia 22: RR Rot se poate scrie:

=

yx

yx

cossinsincos

''

(2.62)

Prin urmare, rotaia se mai poate scrie:

+=+=

cossin'sincos'

yxyyxx

(2.63)

)cossin,sincos()','(),( ++== yxyxfyxfyxf

Demonstraie:

{ } + ++=2

)()cossin,sincos(),(R

dxdyeyxyxfyxf yvxuj

Se face schimbarea de variabile:

+=+=

cossin'sincos'

yxyyxx

48

=

=

''

cossinsincos

''

)cos()sin()sin()cos(

yx

yx

yx

+==

cos'sin''sin'cos'

yxyyxx

(2.64)

nlocuind:

{ } ( )[ ] ++= 2

''cos'sin'sin'cos'exp)','(),(R

dydxyvxvyuxujyxfyxf

Iacobianul este:

1cossinsincos

det

''

''det =

=

yy

xy

yx

xx

{ }

+++=

2''')cossin(')sincos(exp)','(),(

''Rdydxyvuxvujyxfyxf

vu444 3444 21444 3444 21

{ } ),()','(),( vuFvuFyxf == , unde:

=

vu

vu

cossinsincos

''

(2.65)

Prin urmare, dac funcia f(x,y) este cu simetrie circular, atunci i

transformata sa Fourier F(u,v) este cu simetrie circular. Demonstraie: Presupunem c f(x,y) este o funcie cu simetrie circular. n

coordonate polare (fp), aceast proprietate se scrie: ),()sin,cos(),( pffyxf == , (2.66)

49

unde:

==

sincos

yx

Deoarece funcia f este cu simetrie circular:

)(),(),(simetrie

circular

coordonaten

polare== pp ffyxf (2.67)

Pornim de la relaia de definiie:

( )[ ]

+= dxdyyvxujyxfvuF def exp),(),( . (2.68)

Se face schimbarea de variabile carteziene n coordonate polare:

==

sincos

yx

=+=

xyarctg

yx

22

(2.69)

Prin aceast schimbare de variabile, planul real se transform n coordonate polare ntr-o semiband de nlime 2 (pentru a se acoperi tot planul trebuie s ia valori ntre 02, iar trebuie s ia valori ntre 0):

n coordonate polare

y

x

R2

=0

=02

2

Figura 2.20. Domeniile de valori n diferite sisteme de coordonate.

50

Iacobianul este:

=

=

cossinsincos

detdet yy

xx

(2.70)

( )[ ]

+= ddvujfvuF p sincosexp),(),(

Se fac notaiile:

==

sincos

rvru

)sin,cos(),(. = rrFrF notp (2.71)

( )[ ] +=0

2

0

.sinsincoscosexp),(),( ddrjfrF p

notp

Dac funcia f este cu simetrie circular: )(),( pp ff = (2.72)

[ ]

==

=

0

2

)(

2

0

02

0

cos

)cos(exp)(),(

ddrjfrF

da cu perioa , dic dup este perioegrandul deoarece

rJde

pp

rj

444444 3444444 21

int

)()(),(0

2

0

cos rFddefrF prj

pp =

= (2.73)

Prin urmare, dac funcia f este cu simetrie circular, atunci i transformata sa Fourier F este cu simetrie circular (q.e.d).

51

n plus, se tie c:

= 20

0 )cosexp()( dxjxJ = funcia Bessel de ordinul 0

=0

0 )()()( drJfrF pp = transformata Henkel

{ } )()()()(0

0.

rFdrJffH pdef

== = transformata

Henkel a unei funcii de o singur variabil f().

52

3. mbuntirea imaginilor

La concepia algoritmilor sau a dispozitivelor de prelucrare i mbuntire a imaginilor trebuie luat n considerare principiul percepiei vizuale umane. Printre parametrii psiho-fizici ai percepiei vizuale umane pot fi amintii: contrastul, contururile, forma, textura, culoarea etc. Percepia uman a unei imagini poate provoca multe iluzii, nelegerea lor furniznd explicaii referitoare la mecanismele vederii umane i artificiale.

3.1. Calitatea unei imagini

O imagine poate fi degradat pe parcursul achiziiei, transmisiei sau prelucrrii sale. Pentru a estima aceast degradare se pot utiliza msuri de calitate a imaginii. Calitatea necesar pentru o imagine depinde de scopul n care este utilizat imaginea. Metodele de apreciere a calitii imaginii pot fi mprite n dou categorii: subiective i obiective.

Calitatea imaginii f(x,y) este estimat prin compararea cu o imagine de referin g(x,y). Imaginea de referin utilizat n acest scop este, de regul, o imagine de sintez. Una din clasele de metode cele mai utilizate se bazeaz pe diferena medie ptratic MSE:

( ) yx

yxfyxg,

2),(),( (3.1)

Problema acestei msuri este c nu este posibil distincia ntre cteva diferene mari i multe diferene mici. n locul diferenei medii ptratice se poate utiliza eroarea medie absolut. O alt alternativ este corelaia dintre imaginile f i g.

O msur a degradrii imaginii este reprezentat de raportul semnal-zgomot SNR. Fie f(x,y) imaginea original i f'(x,y)= f(x,y)+z(x,y)

53

imaginea degradat. Msura degradrii este estimat prin raportul dintre energia semnalului i energia zgomotului, care este estimat prin relaia:

( )

=

yx

yx

yxfyxf

yxfffSNR

,222

,2

10),('),(

),(log10),'( (dB) (3.2)

Se poate defini i valoarea de vrf a raportului semnal-zgomot PSNR:

( ) =

yx

yx

yxfyxf

yxfNffPSNR

,222

2,

10),('),(

),(maxlog10)',( (dB) (3.3)

unde N este numrul de pixeli. Un raport PSNR mai mare de 32 dB corespunde unei degradri invizibile.

Zgomotul care poate s apar la achiziia, transmiterea sau prelucrarea imaginilor, poate fi dependent sau independent de coninutul imaginii. Zgomotul este descris, n general, de caracteristicile sale probabilistice.

Zgomotul alb are un spectru de putere constant, iar intensitatea sa nu se modific odat cu frecvena. Acest tip de zgomot se utilizeaz n majoritatea cazurilor ca aproximare brut a zgomotului dintr-o imagine. Funcia sa de auto-corelaie este funcia delta. Prin urmare, valorile zgomotului n doi pixeli diferii sunt necorelate. Avantajul acestui model de zgomot este c permite simplificarea calculelor.

Un caz special de zgomot l reprezint zgomotul Gaussian. Zgomotul Gaussian reprezint o aproximare foarte bun a zgomotului care intervine n majoritatea cazurilor. Probabilitatea de densitate a variabilei aleatoare ce descrie zgomotul Gaussian este dat de funcia lui Gauss. Zgomotul Gaussian unidimensional 1D este caracterizat de media sa i de deviaia standard a variabilei aleatoare:

22

2)(

22

1)(

=

x

exp (3.4)

54

Zgomotul poate fi: zgomot aditiv, n cazul n care zgomotul i semnalul de imagine f

sunt independente: f(x,y) = f(x,y) + (x,y) (3.5)

n timpul transmisiei zgomotul este, n general, independent de semnalul de imagine. Prin urmare, degradarea sa poate fi modelat ca un zgomot aditiv.

zgomotul multiplicativ este o funcie descris de relaia: f'(x,y) f(x,y) (x,y) (3.6)

zgomotul impulsiv (de tip impuls) corespunde unei degradri a imaginii cu pixeli zgomotoi a cror valoare difer semnificativ de cea a pixelilor din vecintatea lor.

zgomotul de tip sare i piper este utilizat pentru a descrie zgomotul impulsiv saturat, care corespunde unei imagini degradate cu pixeli albi i/sau negri, de exemplu.

Un parametru important n aprecierea calitii unei imagini l constituie contrastul. Contrastul reprezint variaia local a nivelului de gri i se definete ca raport ntre nivelul mediu de gri al unui obiect i cel al fundalului. Ochiul uman este logaritmic sensibil la iluminare i la variaii ale nivelurilor de gri. Acesta este motivul pentru care majoritatea monitoarelor au implementat o corecie de tip gamma. Nivelul de gri aparent depinde foarte mult de nivelul local de gri al fundalului. Acest efect este numit contrast condiional. Datorit acestui efect, percepia vizual a unor obiecte cu acelai nivel de gri poate fi diferit dac acestea sunt plasate pe un fundal de culoare nchis sau deschis.

55

3.2. Tehnici de mbuntire a imaginilor mbuntirea imaginilor const dintr-un ansamblu de tehnici de

prelucrare care au ca scop scoaterea n eviden a anumitor caracteristici a imaginilor (de exemplu muchii sau contururi) sau eliminarea zgomotului, scopul final fiind obinerea unei vizibiliti superioare a componentelor imaginii. n general, termenul de mbuntire este strns legat de percepia vizual subiectiv a unui expert uman, considerat utilizatorul final al imaginii. ntruct nu se pot defini standarde de calitate a imaginilor, calitatea imaginii este un criteriu subiectiv. Cei care pot face afirmaii cu privire la calitatea unor imagini sunt experii din domeniile din care provin imaginile. n plus, se poate afirma c mbuntirea imaginilor este bine s fie interactiv i iterativ deoarece utilizatorul poate interveni n permanen asupra calitii imaginii i fiecare utilizator o va face ntr-un mod caracteristic. Tehnicile de mbuntire a imaginilor nu genereaz informaie suplimentar despre imaginea original, ci doar o pune pe cea existent sub o alt form, mai uor de interpretat de ctre utilizator. Chiar i o imagine original, nedegradat, poate fi mbuntit, obinnd o imagine modificat, dar subiectiv preferabil. De exemplu, ntr-o imagine subexpus sau supraexpus, utilizatorul (uman sau dispozitivul tehnic) poate s nu disting ntre dou niveluri de luminan care difer cu o cuant; acestea sunt valori diferite n semnalul din calculator i prin tehnici de mbuntire a imaginii pot fi fcute s difere mult mai mult, astfel nct s fie depit pragul de sesizare a diferenei.

56

Operatorii de mbuntire a imaginilor pot fi mprii n trei mari

categorii: operatori punctuali, prin care se realizeaz o relaie de coresponden

punctual ntre valoarea original a fiecrui pixel i valoarea sa dup transformare;

operatori spaiali (locali sau de vecintate), la care noua valoare a nivelului de gri a unui pixel se obine din valoarea original a pixelului respectiv i din valorile originale ale unor pixeli din vecintatea acestuia;

operatori integrali, n cazul crora valoarea nou a unui pixel depinde de valorile tuturor pixelilor din imaginea original, obinndu-se printr-o transformare integral a acestora.

Pentru a exemplifica operaiile de mbuntire a imaginilor, se vor considera imagini de dimensiuni LK (cu L linii i K coloane) i se va nota cu U imaginea iniial i cu V imaginea mbuntit, rezultat n urma aplicrii unei operaii sau transformri de mbuntire (T) asupra imaginii iniiale:

{ }KkLlklUU = 1,1|),( , (3.7)

{ }KkLlklVV = 1,1|),( (3.8) n figura 3.1 se observ c imaginea mbuntit are aceleai dimensiuni ca i imaginea original.

57

U V

V=T(U)

L

K

L

K

Figura 3.1. Operaia de mbuntire a unei imagini.

3.3. Operatori punctuali de mbuntire a imaginilor

Operatorii punctuali de mbuntire a imaginilor sunt transformri aplicate asupra nivelurilor de gri, a cror rezultat depinde doar de valoarea din pixelul considerat. Operatorii punctuali sunt definii prin relaii prin care se realizeaz asocieri ntre valoarea original a fiecrui pixel i valoarea sa dup transformare.

u(l,k)

v (l,k)=T(u(l,k))

L

K

V L

v(l,k)

U

K

Figura 3.2. Operaia de mbuntire a unei imagini, cu operatori punctuali. Operatorii punctuali de mbuntire a imaginilor pot fi mprii n: 1) operatori de modificare a contrastului (engl. contrast streching); 2) transformri de decupare (engl. clipping, slicing, thresholding); 3) operatori de modificare a histogramei.

58

3.3.1. Operatori punctuali de modificare a contrastului Operaiile de modificare a contrastului urmresc mrirea sau

micorarea intervalului de niveluri de gri ocupat de anumite componente ale imaginii, pstrnd acelai numr total de niveluri de gri (N).

Negativarea imaginii Cea mai simpl operaie de modificare a contrastului este

negativarea imaginii, definit de ecuaia:

),(),(.

kluNklvdef

= , (3.9)

unde N este numrul de niveluri de cuantizare (de gri).

Contrastul relativ perceput de un observator uman este modificat, ca urmare a diferenei de sensibilitate ntre percepia nuanelor ntunecate i luminoase. Exemplul cel mai simplu de aplicare este percepia unei radiografii de ctre un observator nespecialist: contrastul va fi apreciat ca mult mai bun pentru imaginea negativat, n care avem obiecte de interes negre pe fond alb.

Diferena ntre imagini Aceast operaie poate fi definit prin relaia:

),(),(),( 12.

klukluklvdef = (3.10)

59

Pentru obinerea unui rezultat ct mai util, ar trebui ca imaginile U1 i U2 s reprezinte aproximativ acelai lucru, dar n alte ipostaze (de exemplu un obiect n micare).

Printre domeniile de aplicaii se poate meniona angiografia (grafia vaselor de snge). n acest scop se achiziioneaz o radiografie a pacientului n stare normal, dup care se injecteaz n vasele sanguine o substan contrastant n raze X i se achiziioneaz o nou radiografie. Prin compararea i diferena celor dou radiografii se scot n eviden zonele de interes, potenial afectate de anumite boli.

Aceast operaie poate fi utilizat i pentru detecia micrii n secvene de imagini. Modificarea liniar a contrastului Cea mai rspndit tehnic de modificare a contrastului (engl. contrast streching) este transformarea liniar pe poriuni. Expresia analitic a acesteia este:

( )( )

+

+

==

1,11

,

0,

)(

222

22

21112

121

11

1

NuuuuuNvN

v

uuuuuuuvv

v

uuuuv

ufv

(3.11)

unde pantele 1

1uv= ,

12

12uuvv

= i

2

211

uNvN

= , vor determina

variaiile relative de contrast (figura 3.3).

60

O

uu1 u2 N-1

v

N-1

v1

v2

Figura 3.3. Modificarea contrastului.

Astfel se vor obine niveluri de gri cuprinse ntre v1 i v2 pentru

valori iniiale cuprinse ntre u1 i u2. Dac u2-u1 < v2-v1, se va obine o imagine cu un contrast mai mare, iar dac u2-u1 > v2-v1 se va obine o imagine cu un contrast mai slab pentru intervalul central al gamei de niveluri de gri.

Trebuie avut n vedere faptul c prin modificarea contrastului dintr-o regiune se modific contrastul i n celelalte regiuni. De exemplu, prin mrirea contrastului n regiunea central (u1, u2), contrastul scade n celelalte regiuni (0u1, u2(N-1)). Se poate realiza i operaia invers, adic dintr-o imagine cu contrast puternic s se obin o imagine cu contrast mai slab.

Din cazul general al modificrii de contrast se pot obine cteva cazuri particulare de interes. Unul dintre acestea este determinat de particularizarea v1=0 i v2=N-1, i const n eliminarea extremelor i extinderea maxim a intervalului de niveluri de gri de interes (figura 3.4).

61

u1 O u2 N-1 u

N-1

v

Figura 3.4. Extinderea nivelurilor de gri.

Expresia analitic corespunztoare este:

( )

==1,1

,10,0

)(

2

21112

1

NuuN

uuuuuuu

Nuu

ufv

(3.12)

Tot din cazul general al modificrii de contrast se mai pot obine i alte cazuri particulare, cum ar fi transformrile de decupare. De exemplu, dac intervalul central de niveluri de gri este eliminat (u1 =u2), din cazul prezentat anterior se obine transformarea de binarizare a imaginilor sau segmentarea cu prag ("tresholding", figura 3.5) .

uO

u

N-1

N-1u1= u2=T

Figura 3.5. Binarizarea imaginilor.

62

Variantele neliniare de modificare a contrastului sunt compresia (sau compandarea) i inversa acesteia, expandarea. Prin compresie se obine o variaie maxim a contrastului n zona nivelurilor de gri apropiate de 0, iar prin expandare, variaia maxim a contrastului se obine n zona nivelurilor de gri apropiate de N-1. Compresia logaritmic (figura 3.6) este descris de ecuaia:

( ) ]10[,1lglg

1 ,N-u,vuN

Nv += (3.13)

Expandarea este descris de ecuaia:

( ) ]10[111 ,N-u,vN

eev N

u

= , (3.14)

v

uO N-1

N-1

Figura 3.6. Expandarea i compresia.

3.3.2. Decuparea intervalelor de niveluri de gri

Tehnicile de decupare a intervalelor de niveluri de gri urmresc punerea n eviden numai a unei poriuni din gama total a nivelurilor de gri disponibile (sau ocupate efectiv de pixelii imaginii). Aceast punere n eviden este realizat n principiu prin nlocuirea tuturor celorlalte niveluri de gri cu o valoare constant.

Transformarea de "clipping" pstreaz nemodificat un interval de niveluri de gri de interes (de exemplu u1u2), restul nivelurilor de gri

63

fiind transformate ntr-o valoare unic, numit fundal (F). Expresia analitic a acestui operator este:

==1,

,0,

)(

2

21

1

NuuFuuuuuuF

ufv

(3.15)

uN-1u2u1

N-1

v

v2

v1 F

O

Figura 3.7. Decuparea nivelurilor de gri.

Transformarea de decupare ("slicing") pune n eviden un interval de niveluri de gri prin modificarea valorilor nivelurilor de gri la 0 sau N-1, dup cum acestea se situeaz n afara sau respectiv n interiorul intervalului considerat (figura 3.8).

u2u1

v

uO N-1

N-1

Figura 3.8. Slicing-ul nivelurilor de gri.

64

3.3.3. Modificarea histogramei

Histograma unei imagini este o funcie ce pune n eviden coninutul de niveluri de gri al acesteia. Din punct de vedere matematic, histograma se definete ca frecvena relativ de apariie n imagine a diferitelor niveluri de gri. Dac considerm o imagine f, de dimensiune LK pixeli i notm cu u un nivel de gri i cu impulsul unitar, histograma se exprim ca:

( ) [ ]1,0,),(1)( ,1,0

1

0=

=

=

NuuklfKL

uhL

l

K

k (3.16)

Proprietile imaginii influeneaz forma histogramei sale. O

imagine de tip tabl de ah, format din ptrate luminoase i ntunecate, n proporie relativ egal, va avea o histogram prezentnd dou maxime puternice, localizate n jurul valorilor de 0 i N-1, i valori aproape nule n zona nivelurilor de gri medii. O imagine fotografic subexpus (i deci foarte ntunecat) are o histogram al crei suport (interval ce corespunde valorilor nenule) este concentrat spre valoarea 0. O imagine fotografic supraexpus (i deci foarte luminoas) are o histogram al crei suport este situat n zona valorilor apropiat de N-1. O imagine bine contrastat, ce prezint numeroase nuane, va avea o histogram al crei suport va acoperi aproape ntreaga gam de niveluri de gri posibile i a crei form va fi neregulat.

Reciproc, inspecia formei unei histograme poate oferi informaii despre caracteristicile imaginii, dar nu o poate individualiza, deoarece mai multe imagini pot avea aceeai histogram.

Aceast comportare corespunde faptului c histograma se comport ca o funcie de densitate de probabilitate a unei variabile aleatoare ale crei realizri particulare sunt valorile nivelurilor de gri din imagine.

65

ntr-adevr, h(u)>0, u, i 1)(10

==

N

nnh . Orice funcie de densitate de

probabilitate are asociat o funcie de repartiie. n cazul histogramei imaginilor, aceast funcie de repartiie este histograma cumulativ:

[ ]1;0,)()( = =

NunhuHu

on (3.17)

Imaginea ideal ar trebui s prezinte o distribuie uniform a

nivelurilor de gri i un contrast repartizat regulat n ntreaga gam dinamic. Pentru a obine o asemenea imagine, operatorul de mbuntire trebuie s transforme histograma original a imaginii ntr-o histogram uniform, n care toate nivelurile de gri sunt egal probabile. Din punct de vedere matematic, problema se reduce la a transforma o funcie de densitate de probabilitate oarecare ntr-o funcie de densitate de probabilitate uniform (constant pe intervalul de definiie [0,N-1]). innd cont de teoria variabilelor aleatoare (funcie de o variabil aleatoare) i de faptul c variabila aleatoare nivel de gri este discret, formula de transformare a nivelului de gri u pentru egalizarea de histogram este:

( )

+= 5,01

)0(1)0()(int N

HHuHv (3.18)

unde int[ ] este operatorul parte ntreag, iar H este histograma cumulativ definit anterior.

Exemplu: Considernd o imagine de 6464 pixeli, reprezentat cu 8 niveluri de gri (07), a crei histogram este dat n tabelul urmtor (cruia i corespunde figura 3.9), s se realizeze egalizarea de histogram.

66

Nivelul de gri

Nr. de pixeli avnd acest nivel de gri

0 796 1 1023 2 850 3 650 4 329 5 245 6 122 7 81

0200400600800

10001200

1 2 3 4 5 6 7 8nivelul de gri

Nr.

de p

ixeli

Figura 3.9. Histograma unei imagini.

Rezultatele obinute n urma egalizrii, pe baza relaiilor de

definiie sunt cumulate n urmtorul tabel: Tabelul 3.1.

Imaginea iniial Imaginea transformat Nivel

de gri

Nr. de pixeli cu nivelul de gri i

h(i) Histograma cumulativ pt. nivelul

de gri i

Nivelul de gri

transformatconform

egalizrii de histogram

Numrul de pixeli

corespunztornivelului de

gri transformat

Transformarea nivelului de

gri

0 796 0,194 0,194 0 796 0-0 1 1023 0,249 0,443 2 0 1-2 2 850 0,208 0,651 4 1023 2-4 3 650 0,159 0,81 5 0 3-5 4 329 0,08 0,89 6 850 4-6 5 245 0,06 0,95 7 650 5-7 6 122 0,031 0,981 7 329 6-7 7 81 0,019 1 7 448 7-7

67

Histograma "egalizat" este deci (figura 3.10):

0

200

400

600

800

1000

1200

1 2 3 4 5 6 7 8

nr

de p

ixel

i

0 1 2 3 4 5 6 7 Figura 3.10. Histograma egalizat.

Din graficul prezentat se observ c histograma obinut nu este

"uniform" i prezint numeroase niveluri de gri lips ("guri"). Aceste efecte sunt datorate n general cuantizrii nivelurilor de gri i limitrii prin trunchiere a domeniului de variaie a valorilor (formula de transformare este dedus pentru variabile aleatoare cu variaie continu). Pentru corectare au fost propuse mai multe abordri: limitarea maximelor histogramei, mutarea aleatoare a valorilor pixelilor situate pe niveluri de gri mai bine reprezentate n histogram pe niveluri de gri absente, etc. Trebuie de asemenea remarcat faptul c egalizarea de histogram nu asigur n toate cazurile cea mai bun calitate vizual a imaginii transformate.

Egalizarea de histogram i tehnicile nrudite de specificare a histogramei asigur mrirea contrastului imaginii prin redistribuirea nivelurilor de gri n cadrul gamei dinamice fixate, [0,N-1]. Sensibilitatea sistemului vizual uman este ns mult mai mare n gama color dect n cea a nivelurilor de gri. De aceea una dintre tehnicile cele mai populare de realizare a unei vizibiliti maxime a anumitor componente dintr-o imagine este colorarea lor cu culori puternic contrastante, adic prin pseudocolorare.

n cazul aplicrii tehnicii de pseudocolorare, imaginea va fi afiat (vizualizat) cu o tabel de culoare diferit de paleta original de niveluri

68

de gri. Aceast nou palet de culoare poate fi construit dup orice fel de reguli care s corespund problemei de rezolvat: de exemplu, toi pixelii al cror nivel de gri este 250 vor fi afiai cu rou i toi pixelii al cror nivel de gri este cuprins ntre 100 i 120 vor fi afiai cu verde. Se pot introduce i condiii relative la poziia spaial a pixelilor sau la alte caracteristici locale ale acestora.

Schema general a unei operaii de pseudocolorare este detaliat n figura 3.10.

index R G B

Palet de culori Display

Imagineiniial

Bloc de extragere

caracteristici

Figura 3.10. Schema unui sistem de pseudocolorare.

3.4. Operatori liniari de vecintate pentru mbuntirea imaginilor. Filtrarea liniar a imaginilor

Spre deosebire de operatorii punctuali, operatorii de vecintate

(numii i operatori spaiali locali) determin valoarea nou a unui pixel ca o funcie de valorile pixelilor dintr-o vecintate a sa. Dac aceast funcie (de mai multe variabile) este liniar, atunci operatorul se numete liniar.

Se va nota cu u(l,k) imaginea iniial (de intrare), cu l=1,,L, k=1,,K, cu v(l,k) imaginea rezultat (de ieire) i cu a(i,j), funcia pondere a sistemului, i=1,L, j=1,,K.

Operatorii liniari de vecintate se implementeaz, n general, prin convoluia imaginii iniiale cu funcia pondere a unui filtru cu rspuns finit, numit masc spaial, adic prin aplicarea unui asemenea operator se realizeaz practic o filtrare bidimensional. Aceast filtrare este obinut

69

prin tehnica "ferestrei glisante" (moving-window), iar fereastra ce culiseaz peste imagine se mai numete i masc spaial sau filtru bidimensional i are rolul de a selecta vecintatea pixelului curent asupra cruia opereaz filtrul respectiv.

Expresia analitic a acestei operaii este:

=Wji

kkilujiaklv),(

),(),(),( (3.19)

unde u i v sunt imaginile de intrare, respectiv de ieire, iar a sunt

coeficienii ferestrei (mtii) de filtrare W, care are dimensiuni mai mici dect imaginile asupra crora acioneaz.

Dup cum se observ, aceasta este de fapt o convoluie: v=a*u, ntre funcia pondere a unui filtru cu rspuns finit (a) i imaginea de intrare, iniial (u). Aceasta se poate exprima ca un produs punct cu punct ntre coeficienii mtii i o poriune din imagine, de aceeai dimensiune.

Tehnica ferestrei glisante const n efectuarea urmtoarelor operaii: Se definete fereastra de filtrare adic:

forma (relativ la o origine); coeficienii din fiecare punct;

Fereastra gliseaz peste imaginea iniial, adic se pune originea ferestrei n fiecare punct al imaginii. Astfel va fi selectat de ctre fereastr pixelul curent i pixelii din vecintatea acestuia.

Se face produsul punct cu punct ntre valoarea pixelilor din imagine selectai de fereastr i coeficienii ferestrei.

Se nlocuiete pixelul curent cu noua valoare obinut, ca sum a produselor obinute la punctul anterior.

De regul, filtrele folosite sunt de ordin impar, rectangulare i au

originea (0,0) n centrul suportului:

70

a-1-1 a-10 a-11

a0-1 a00 a01 a1-1 a10 a11

Problemele care se ridic la aplicarea acestor operatori se refer la:

Marginile imaginii, aici avnd 2 posibiliti: obinerea unei imagini de dimensiuni mai mici, atunci

cnd glisarea ncepe din interiorul imaginii bordarea imaginii de intrare pentru a pstra aceleai

dimensiuni pentru imaginea prelucrat Numrul de operaii necesare pentru fiecare punct. Pentru o fereastr

ptrat cu latura n sunt necesare: n2 nmuliri i n2-1 adunri. n concluzie, din punct de vedere al volumului de calcule, este mai bine s se lucreze cu ferestre ct mai mici.

Filtrele bidimensionale folosite uzual n prelucrarea imaginilor sunt nuclee cu suporturi de dimensiuni mici: 33, 55. Filtrele de dimensiuni mai mari se pot reduce adesea la aplicarea repetat asupra unei imagini a unor nuclee de dimensiuni mai mici.

Nucleele ptrate de dimensiuni 33 sunt cele mai utilizate. Exemple de astfel de nuclee sunt:

111111111

91

010141010

81 (3.20)

(a) (b)

Filtrul (a) realizeaz media ntre pixelul central i vecinii si, iar filtrul (b) realizeaz media ponderat ntre pixelul central i vecinii si verticali i orizontali.

71

Forma i coeficienii ferestrei se aleg astfel nct s corespund aplicaiei concrete. Singura constrngere n ceea ce privete coeficienii ferestrei, pentru filtrele de mediere (al cror efect este de FTJ) este:

=wji

jia),(

1),( , pentru a nu modifica regiunile uniforme. (3.21)

n cazul n care coeficienii ferestrei ndeplinesc condiia din relaia (3.21) efectul filtrului (ferestrei de filtrare) este un efect de netezire. n cazul n care coeficienii ferestrei ndeplinesc relaia:

=wji

jia),(

0),( (3.22)

efectul filtrului (ferestrei de filtrare) este un efect de reliefare (accentuare sau contrastare), respectiv de filtru trece-sus. Exemple de filtre de reliefare sunt:

[ ]

010141

010 [ ]

111181111

[ ]

121242

121 (3.23)

Medierea efectuat cu ajutorul operatorilor liniari de vecintate

poate fi util la reducerea zgomotului aditiv gaussian i mai puin a zgomotului impulsiv, de tip salt and pepper (engl.= "sare i piper"). Aplicarea unui filtru de mediere asupra unei imagini afectat de zgomot impulsiv sau gaussian are ca rezultat extinderea punctelor cu zgomot (formarea de pete), respectiv apariia efectului de bluring sau mnjeal (neclar, ceos), ca efect special dorit sau ca o consecin nedorit a reducerii zgomotului. Aceste efecte au ca rezultat nedorit reducerea claritii imaginii filtrate, ceea ce poate produce dificulti suplimentare n

72

etapele ulterioare de prelucrare a imaginii (segmentare, detecie de contur, recunoatere de forme etc.).

O prim modalitate de reducere a efectului de bluring este ponderarea pixelilor mediai n funcie de distana fa de centrul ferestrei:

=

W(i,j)j)i,ku(lc(i,j)v(l,k) (3.24)

unde c(i,j) sunt coeficienii cu care se face ponderarea pixelilor din

fereastra W. Valorile acestor coeficieni c respect n general o anumit distribuie spaial, cel mai adesea fiind utilizat distribuia gaussian. Filtrul este cunoscut n acest caz, sub denumirea de filtru gaussian.

O variant mbuntit pentru reducerea efectului de bluring o constituie filtrul de netezire cu prag, care nu mai este liniar. Particularitatea sa const n faptul c nlocuirea valorii pixelului curent cu media ponderat a vecinilor si se face doar dac este satisfcut condiia:

Tkluklv

73

3.5. Efectul n frecven al operatorilor liniari de vecintate

Dup cum s-a artat mai sus, aplicarea unui filtru de mediere se face prin convoluia ntre imaginea iniial u i funcia pondere a filtrului h:

v = h*u (3.26)

Coeficienii ferestrei sunt egali i se tie c transformata Fourier a unei constante este un sinc (figura 3.11):

y

x

Figura 3.11. Transformata Fourier a unei constante.

Dac se noteaz cu U, V i H transformatele Fourier ale imaginilor de intrare, respectiv de ieire i a filtrului, din relaia anterioar i din teorema convoluiei rezult c: V=HU (3.27)

iar caracterizarea n frecven a aciunii filtrului se poate face pe baza lui H. Transformata Fourier a unui filtru de mediere cu coeficieni constani (figura 3.12.a) este un sinc bidimensional (figura 3.12.b):

74

F

z

y x

z

yx

(a) (b)

Figura 3.12. Transformata Fourier a unui filtru de mediere cu coeficieni constani.

Prin urmare, medierea spaial este echivalent cu o filtrare

trece-jos (figura 3.13):

Mediere spaial

u vFTJ

u v

Figura 3.13. Medierea spaial.

Celelalte tipuri de filtre (n frecven) se pot obine cu un FTJ. Astfel, dac hTJ(m,n) este funcia de transfer a unui FTJ atunci un filtru trece-sus FTS va avea o funcie de transfer hTS(m,n):

),(),(),( klhklklh TJTS = (3.28)

unde este impulsul Dirac. Deci, un FTS se poate implementa prin scderea din imaginea

iniial a imaginii obinute printr-un FTJ (figura 3.14):

75

FTS u v

FTJ

u v +

-

Figura 3.14. Obinerea unui FTS cu ajutorul unui FTJ.

La fel, un filtru trece-band FTB poate fi caracterizat prin relaia:

),(),(),( 21 klhklhklh TJTJTB = (3.29)

unde hTJ1 i hTJ2 sunt funcii de transfer a dou FTJ. Deci un FTB se poate obine din 2 FTJ astfel (figura 3.15):

u FTB v FTJ hTJ1(l,k)

FTJ hTJ2(l,k)

u v

+-

Figura 3.15. Obinerea unui FTB cu ajutorul a dou FTJ.

Filtrarea trece-jos se utilizeaz pentru atenuarea zgomotului,

filtrarea trece-band se folosete pentru extragerea sau accentuarea contururilor, iar filtrarea trece-sus este util pentru mbuntirea contururilor sau a altor caracteristici de tip trece-sus ale unei imagini, n prezena zgomotului.

Pe baza acestor considerente, pentru mbuntirea imaginilor se pot defini i operatori integrali (numii si transformri integrale) n cazul crora noua valoare ntr-un punct depinde de valoarea ntregii imagini

76

iniiale. Folosirea transformrilor integrale mut problema ntr-un plan dual planului imaginii i anume planul frecvenelor spaiale.

Repartiia spaial a spectrului difer de la o transformare la alta:

FTJ FTJ

FTB FTB

FTS

FTB FTB

Figura 3.16. Exemplu de repartiie spaial a spectrului unei imagini.

Exemple de transformri (Fourier, Cosinus) vor fi prezentate n

capitolul referitor la transformri integrale ale imaginilor.

3.6. Filtrarea neliniar a imaginilor

Filtrele liniare (de netezire sau contrastare) produc la ieire, n fiecare punct al imaginii, o combinaie liniar ponderat a setului de valori selectate de fereastra de filtrare plasat cu originea n acel punct. Filtrele liniare pot elimina zgomote care corespund acestui model de mediere, deci zgomote aditive i cu distribuie normal (gaussian). Din aceast comportare de tip filtru trece-jos rezult efecte secundare care se manifest prin reducerea sau eliminarea din imagine a componentelor de frecven nalt (detalii, contururi). Imaginea i pierde claritatea i devine mai ceoas (efect de blur). n acelai timp, filtrarea liniar a unor zgomote ne-aditive (de exemplu zgomotul impulsiv) produce rezultate deranjante din punct de vedere al calitii imaginii (n particular lirea i mprtierea impulsurilor de zgomot).

77

3.6.1. Filtre neliniare de ordine

Pentru eliminarea dezavantajelor filtrelor liniare apare evident

necesitatea de a modifica structura de filtrare liniar, n care valoarea unui pixel nu este luat n considerare, tocmai printr-o triere a valorilor extrase de fereastra de filtrare, n funcie de rangul sau importana lor. Evident, operaia devine neliniar, ntruct se va baza pe compararea i ordonarea valorilor. Acesta este modelul de filtrare de ordonare (rank-order filter), fr a fi ns singurul tip de filtrare neliniar. Dac se noteaz cu: X={x1,x2,, xN}, cele N valori extrase de o fereastr de filtrare pentru o poziie dat, setul de valori ordonate este: X()={x(1),x(2),,x(N)}, cu x(1) x(2)x(N). Scalarul x(k) se numete statistica de ordine de ordinul k (sau pe scurt, statistica de ordin k) a secvenei X. Evident, statistica de ordinul 1 este minimul, iar statistica de ordinul N este maximul: x(1) = min X() = min X (echivalentul unei erodri morfologice) (3.30) x(N)= max X()= max X (echivalentul unei dilatri morfologice) Considernd ca exemplu setul de 5 valori: X={1, 10, 100, 10, 200}, rezult: x1=1, x2=10, x3=100, x4=10, x5=200. Setul ordonat este: X()={1,10,10,100,200}, iar statisticile de ordine sunt: x(1)=1, x(2)=10, x(3)=10, x(4)=100, x(5)=200. Ieirea de ordinul k a filtrului de ordine este statistica de ordin k a setului de valori selectate de fereastra de filtrare, k putnd lua orice valoare ntre 1 i N: rankk(X)=x(k) (3.31)

78

Cel mai utilizat filtru de ordine este filtrul median, caracterizat de:

+=2

1Nk , (unde [x]= part