Operatii spatiale simple - users.utcluj.rousers.utcluj.ro/~simona/apim/apim3.pdf · Aritmetica...

APIM3 - 1

Operatii spatiale simple

APIM3 - 2

In cursul de astazi • gradient, hamiltonian, laplacian

• convolutia discreta

• filtre trece jos

• filtre trece sus

• gradient, hamiltonian, laplacian

• derivare

• detectia muchiilor

• filtrare neliniara simpla

• tratarea marginilor imaginii

• interpolare

• transformari geometrice

APIM3 - 3

Operatii spatiale simple

Redefinirea valorii de gri a unui punct ia in

considerare valorile de gri ale unui grup de

pixeli din vecinatatea punctului

APIM3 - 4

Convolutia discreta (1)

unde

Corelatie (mai intuitiva):

APIM3 - 5


atunci:

Obs.: gf = fg, g*f f*g

APIM3 - 6


• convolutia ne permite sa utilizam o vecinatate a

pixelului (caracteristicile lui spatiale)

• multe procesari de imagini care utilizeaza

informatia spatiala sunt implementate pe baza

convolutiei

• in multe cazuri rezultate bune sunt obtinute

utilizand nuclee (masti) de dimensiuni mici (de

ex. 3x3)

APIM3 - 7


APIM3 - 8

Convolutia

discreta (5)

APIM3 - 9

Exemplu

APIM3 - 10

Exemplu

APIM3 - 11

Netezire (filtru trece jos) (1)

APIM3 - 12

Netezire (2)

1/9 1/9 1/9

1/9 1/9 1/9

1/9 1/9 1/9

1 1 1 1 1 1

1 1 1

1

1

1 1

2 2

2 2 2

22

2 2 2 2 2 2

3 3 3

333

3 3

33

2

APIM3 - 13

Netezire (3)

1/9 1/9 1/9

1/9 1/9 1/9

1/9 1/9 1/9

1 1 1 1 1 1

1 1 1

1

1

1 1

2 2

2 2 2

22

2 2 2 2 2 2

3 3 3

333

3 3

33

1.22 1.67 2.00 2.33

1.44 2.44 2.89

1.89 2.00 2.45 2.77

1.67 1.89 2.22 2.44

2.00

Image Image f g

APIM3 - 14

Netezire (4)

APIM3 - 15

Netezire (5)

Filtru median de dimensiune

3, 5, 9, 15 si 35

APIM3 - 16

Alte filtre de mediere

• efecte similare

• anizotropice –numai aproximari ale cercului

• suma intrarilor este unu – nu modifica zonele

constante din imagine

APIM3 - 17

Accentuarea contururilor

• suma intrarilor este unu – nu actioneaza in

zonele constante din imagine

• diferenta dintre valorile de gri este puternic

accentuata

APIM3 - 18

Exemplu

APIM3 - 19

Exemplu

APIM3 - 20

Filtru trece sus (1) • filtrarea frecventelor inalte se poate calcula:

(imagine)-(imaginea filtrata cu filtru trece jos)

• nucleul poate fi calculat asemanator:

• suma intrarilor e zero, deci ariile de valori constante

dispar

APIM3 - 21

Filtru trece sus (2)

APIM3 - 22

Filtru trece sus (3)

APIM3 - 23

Unsharp masking (1)

= accentuarea frecventelor inalte (pt. imbunatatirea

imaginii) – frecvent utilizat la tiparire

• adaugarea unei imagini filtrate cu filtru trece sus

• scaderea unei imagini filtrate cu filtru trece jos

APIM3 - 24

Unsharp masking (2)

- pt. si masca:

APIM3 - 25

Gradient

• imaginea este o functie:

cu variabilele:

• gradientul sau operatorul nabla:

• gradientul functiei f in punctul a:

APIM3 - 26

Gradient si hamiltonian

• hamiltonian = vectorul perpendicular pe gradient

daca si

atunci vectorul hamiltonian =

• linii de flux

• linii izofote:

APIM3 - 27

Linii izofote

APIM3 - 28

Puncte stationare (1)

• a este punct stationar daca

adica toate derivatele sunt zero

• daca atunci a este punct de maxim

• daca atunci a este punct de minim

APIM3 - 29

Puncte stationare (2)

• pt. cazul bidimensional se util. Hessianul (H)

• minim local daca H(a) > 0 si

• maxim local daca H(a) > 0 si

• punct de inflexiune (saddle point) daca H(a) < 0

APIM3 - 30

Laplacian

• laplacianul (Δ) unei functii

Exemplu: f(x,y) = -2x2-y2

f = (-4x, -2y); Δf = -6

hamiltonianul=(-2y, 4x)

H(0,0) = 8 si fxx=-4 (0,0) este un maxim

APIM3 - 31

Exemplu (1)

APIM3 - 32

Exemplu (2)

APIM3 - 33

Exemplu (3)

APIM3 - 34

Derivate

• punctele interesante ale functiilor matematice

(extreme, puncte de inflexiune, etc.) sunt

determinate pe baza derivatelor

• acelasi lucru este valabil si pentru imagini !

• cum calculam derivata unei imagini digitale?

APIM3 - 35

Aproximarea derivatelor

• aproximarea derivatelor utilizeaza valorile de gri din

vecinatatea unui pixel

• se utilizeaza o combinatie ponderata

• de exemplu utilizand 5 pixeli:

f´a(0)=g-2 f(-2) + g-1 f(-1) + g0 f(0) + g1 f(1) + g2 f(2)=

=

2

2

)(i

i ifg

APIM3 - 36

Aproximarea derivatelor (2)

• determinarea valorilor lui gi: f´a este exacta in cazul in

care f este o functie polinomiala de grad mic (de

exemplu {1, x, x2, x3,…})

•de exemplu, sa se determine o aproximare utilizand trei

pixeli care dau rezultatul corect pentru f = {1, x, x2}

f´a(0)=g-1 f(-1) + g0 f(0) + g1 f(1)

APIM3 - 37

Aproximarea derivatelor (3) f´a(0)=g-1 f(-1) + g0 f(0) + g1 f(1)

sub forma matriciala:

de unde:

gi = {-1/2, 0, 1/2}

APIM3 - 38

Aproximarea derivatelor (4)

• f´a(0)=g-1 f(-1) + g0 f(0) + g1 f(1)

• pentru toti pixeli se poate scrie derivata dupa x ca o

convolutie discreta cu nucleul:

• derivata dupa y ca o convolutie discreta cu nucleul:

-1

0

1 2

1

APIM3 - 39

Aproximarea derivatelor (5) fxx(0)=g-1 f(-1) + g0 f(0) + g1 f(1)

1 -2 1

sub forma matriciala:

de unde:

gi = {1, -2, 1}

0

2

2

0

1

-2

1

APIM3 - 40

Exemplu

original derivata dupa y

utilizand 3 pixeli

APIM3 - 41

Exemplu

original derivata dupa x

utilizand 5 pixeli

APIM3 - 42

Aproximarea derivatelor in doua dim.

• sa se determine o aproximare fxy utilizand un nucleu

de 3x3

• determinarea valorilor lui gi: fxy este exacta in cazul

in care f este o functie polinomiala in x si y de grad

mic {1,x,y,xy,x2,y2,x2y,xy2,x2y2}

APIM3 - 43

Aproximarea derivatelor in doua dim.(2)

Sub forma matriciala:

de unde:

APIM3 - 44

Detectarea muchiilor (1)

• Muchiile sunt strans legate de derivate

• Gradientul este o masura a existentei muchiilor

APIM3 - 45

Detectarea muchiilor (2)

Unde este muchia daca trecerea este lenta? Ce rol are

derivata a doua?

APIM3 - 46

Detectarea muchiilor pe baza derivatelor

Metoda 1:

• Masurarea existentei muchiilor cu ajutorul gradientul

• Accentuarea contrastului imaginii prin thresholding

APIM3 - 47

Detectarea muchiilor pe baza derivatelor

Metoda 2:

• determinarea trecerii prin zero a derivatei a doua

• in 2D se determina trecerea prin zero a Laplacianului

APIM3 - 48

Detectarea muchiilor

• gradientul:

• fx si fy pot fi aproximate utilizand nucleele:

• exista multe nuclee alternative!

APIM3 - 49

Nuclee pentru detectarea muchiilor

APIM3 - 50

Exemplu

orig aprox

Prewitt Sobel

APIM3 - 51

Exemplu

orig aprox

Prewitt Sobel

APIM3 - 52

Orientarea muchiilor

• gradientul este un vector (modul si directie)

• directia gradientului (fx, fy) este caracterizata

de unghiul cu abscisa:

APIM3 - 53

Operatori compas

Alternativa la masurarea gradientului:

• masurarea consistentei muchiei in mai multe

directii si retinerea valorii maxime:

unde:

APIM3 - 54

Operatori compas

Un operator utilizat frecvent <- nucleul Kirsch

APIM3 - 55

Operatorul Frei si Chen

Detectarea muchiilor este uneori gresita din

punct de vedere al opiniei umane. O solutie este

utilizarea unei combinatii de:

• nuclee de detectare a muchiilor ca mai inainte

• nuclee care ar trebui sa aiba un raspuns slab

sau deloc

APIM3 - 56

Operatorul Frei si Chen

APIM3 - 57

Operatorul Marr-Hildreth

• alternativa la derivata a doua/ Laplacian

• mai putin senzitiv la zgomot

unde: gσi = functia Gaussiana, σ2 > σ1

• numita si filtru DoG (difference of Gaussians)

APIM3 - 58

Exemplu

Original Laplacian Marr-Hildreth

APIM3 - 59

Detectarea muchiilor

• Detector perfect de muchii nu exista

• Cea mai buna alegere depinde de

– imaginile utilizate

– aplicatie

– viteza necesara

– etc.

APIM3 - 60

Detectarea liniilor

• liniile – presupuse a avea grosimea de un

pixel- pot fi detectate cu operatorul compas:

,

APIM3 - 61

Exemplu

APIM3 - 62

Exemplu

APIM3 - 63

Detectarea punctelor izolate

• convolutia cu :

• utilizarea op. compas

cu nucleul de baza:

APIM3 - 64

Aproximarea convolutiei 1D (1)

• necesitatea convolutiei discrete in proc. imaginilor

• fie nucleul Gaussian cu

• utilizam aproximarea in 9 puncte {g(-4), g(-3), …, g(4)}

4

2

2

1)(,2x

exg

APIM3 - 65

Aproximarea convolutiei 1D (2)

• aria de sub grafic este 1 !!! nucleul discret trebuie sa aiba

aceeasi proprietate

• daca aproximarea este in 5 puncte {g(-2), g(-1), …, g(2)}

atunci factorul este 0,929

• erori:

- de discretizare

- de trunchiere

APIM3 - 66

Aproximarea convolutiei 2D

• fie nucleul Gaussian

• pentru σ=2 si aproximare in 9x9 puncte

• insumarea valorilor duce la un factor de 1/0,95456

• 0,911 eroare de cca. 9%

2

22

21

2 2

1),(

yx

eyxg

APIM3 - 67

Aproximarea functiilor impare

• fie functia Gaussiana

• aproximarea derivatei in 9 puncte:

• determinarea factorului de normalizare:

adica: si p=1,00007

2

2

21

2

1)(

x

exf

2

2

21

3 2)('

x

exf x

APIM3 - 68

Aritmetica nucleului (1)

Convolutia:

• comutativa: f * g = g * f

• asociativa: (f * g) * h = g * (f * h)

• distributiva: (g + h) * f = g * f + h * f (si pt. corelatie)

dar:

- f *f poate avea valori negative

- f *1 ≠ f in general

APIM3 - 69

Aritmetica nucleului (2) • operatii mai ieftine:

g1 * f + g2 * f = (g1 + g2) * f

• uneori operatii mai ieftine:

g1 * g2 * f = (g1 * g2) * f

in cazul corelatiei: g1 * (g2 * f) = (g1 * g2m)m * f

deoarece gm * f = g * f

APIM3 - 70


Nuclee separabile:

nucleele pot fi descompuse in nuclee de 1D

• Convolutia se poate face utilizand convolutia

unidimensionala

= *

APIM3 - 71


Nuclee sunt in general separabile: g(x,y)=g1(x)g2(y)

nucleele pot fi descompuse in nuclee de 1D

• Convolutia se poate face utilizand convolutia

unidimensionale

APIM3 - 72

Filtrare neliniara simpla (1)

• rezultatul nu poate fi scris ca o medie ponderata a

valorilor pixelilor vecini

• nu poate fi implementata prin convolutie discreta

• de exemplu

- filtru median - valoarea mediana a pixelilor

din vecinatate

- filtre min si max (morfologie)

APIM3 - 73

Filtrare neliniara simpla (2)

• exemplu – filtru median 3x3

APIM3 - 74

Filtrare neliniara simpla (3) - filtru median 3x3 – utilizat pentru eliminarea zgomotului

-aplicat o data -aplicat de 12 ori

- micile detalii dispar, dar muchiile raman; omogenizare

APIM3 - 75

Tratarea marginilor imaginii (1)

Operatiile pe baza pixelilor din vecinatate necesita atentie

deosebita la calculul valorii pixelilor de la marginea imaginii

APIM3 - 76

Tratarea marginilor imaginii (2)

• padding

• extrapolare

• simetrie

APIM3 - 77

Interpolare (1)

Aproximarea valorilor de

gri in locatiile dintre

pixeli pe baza valorilor

pixelilor vecini

• cel mai apropiat vecin

• interpolare liniara

APIM3 - 78

Interpolare (2) • interpolarea cel mai apropiat vecin

APIM3 - 79

Interpolare (3) • interpolarea liniara

APIM3 - 80

Interpolare (4)

• exemplu - interpolare liniara

30x30 256x256

APIM3 - 81

Interpolare modelata prin convolutie (1)

APIM3 - 82


• interpolarea celui mai apropiat pixel

• interpolarea liniara

Relatia dintre cele doua nuclee:

APIM3 - 83


• hk = nuclee de interpolare B-spline cu baza k

• nucleul B-spline cubic (k=4)

• daca k atunci nucleul devine nucleul Gaussian

APIM3 - 84

Nucleul ideal

• functia sinc

• ideal deoarece retine toate frecventele

• trebuie aproximat si trunchiat

APIM3 - 85

Transformari geometrice (1)

• redefinire (mapare): (x, y) (x´, y´)

• utilizate pentru aliniere, vizualizare optima, corectia

distorsiunilor

• exemple: translatie, rotatie, scalare, etc.

APIM3 - 86

Transformari geometrice (2)

• rigide (translatie si rotatie)

• afine (linii paralele devin

linii paralele)

• proiective (liniile raman

linii)

• elastice (linile devin curbe)

APIM3 - 87

Transformari rigide

• translatie:

• rotatie:

• combinarea lor:

APIM3 - 88

Transformari afine

-scalare:

-skewing:

APIM3 - 89

Transformari proiective

• proiectia 3D in 2D

- transformarea perspectivei centrale a doua imagini:

APIM3 - 90

Transformari elastice (1)

• elastice (curbe):

- se utilizeaza functii polinomiale:

- utilizate pentru corectarea distorsiunilor imaginilor

APIM3 - 91

Transformari elastice (2)

• reprezentare sub forma de deplasare a campului vector :

APIM3 - 92

Maparea inversa

• utilizarea matricei A-1 pentru a calcula transformarea:

• necesara fiindca altfel se ‘pierd” valori din imaginea rezultata

• dezavantaj – trebuie calculata A-1

Operatii spatiale simple - users.utcluj.rousers.utcluj.ro/~simona/apim/apim3.pdf · Aritmetica...

Documents

Transcript of Operatii spatiale simple - users.utcluj.rousers.utcluj.ro/~simona/apim/apim3.pdf · Aritmetica...