sisteme de vedere artificial ărovislab.com/courses/sva/curs_02_sva_2016.pdf · 2018-11-19 · 1...

1

Sisteme de Vedere Artificială

Filtrarea imaginilor

Sorin M. Grigorescu

Universitatea Transilvania din BraşovLaboratorul de Vedere Artificială Robustă şi Control

2

Cuprins

�Reprezentarea imaginilor

�Distribuţia Gaussiană

�Filtrarea imaginilor

�Template matching

3

Lanţ de procesare a imaginilor�Recunoaşterea caracterelor

SegmentarePre

procesareAchiziţia

imaginilor

Procesarea imaginilor

Clasificare şirecunoaştere

Înţelegerea imaginilor

Extragerecaracteristici

Nivel inferior Nivel superior

CaracteristicileObiectelor

(caracterelor)

Nivel mijlociu

4

Reprezentarea imaginilor

Coloane

PIXEL

Eşantionarea imaginilor

5

Reprezentarea imaginilor

Valorile pixelilor

133154157165165154138124113978167656791105

10815718919818918116511689971008158485081

13317918919619617991402642818367241656

1461961981981989726505650348973341024

1081791891891733465402458424873321016

4012417118917356482682632264824816

1034891491496724241016161816181618

10162456653416161016241818181626

1081624242418161618182418263440

50241824422616263232345648505050

6765588111365247375757367736573157

5897891161301167310510510591918191173189

50738910812413011311612111310081113179189181

6

Reprezentarea imaginilor

Coloane x(0,0)

M

N

y

f (N-2,6)

6

−−−−−−−−−−−−−−−−

−−−−

−−−−

====

),(),(),(

),(),(),(

),(),(),(

),(

111101

111101

101000

NMfMfMf

Nfff

Nfff

yxf

K

MMM

K

K

7

Tipuri de imagini digitale

Lena, imagine binară (2 nivele de gri: negru şi alb)

Lena, imagine gri (8 nivele de gri)

Lena, imagine color

Lena, imagine gri (256 nivele de gri)

8

Tipuri de imagini digitale

Lena, imagine gri

(256 nivele de gri – 8 Biţi) Lena, imagine color

Matrice M x N cu elemente aparţinând

intervalului ]255,0[∈

3 matrici M x N (o matrice pentru fiecare

canal RGB) cu elemente aparţinând intervalului ]255,0[∈

„Lena în verderoşu şi albastru“

9

Imaginea ca şi funcţie

�(�, �)�

0, 0 �

133154157165165154138124113978167656791105

10815718919818918116511689971008158485081

13317918919619617991402642818367241656

1461961981981989726505650348973341024

1081791891891733465402458424873321016

4012417118917356482682632264824816

1034891491496724241016161816181618

10162456653416161016241818181626

1081624242418161618182418263440

50241824422616263232345648505050

6765588111365247375757367736573157

5897891161301167310510510591918191173189

50738910812413011311612111310081113179189181

10

Imaginea ca şi funcţie

�

0, 0 �

�

�

Pixel value

(intensity)

11

Imaginea ca şi funcţie�O imagine (gri) poate fi considerată o funcţie f sau I, din spaţiul ℝ

în ℝ� � �, � defineşte intensitatea sau valoarea la poziţia �, �

133154157165165154138124113978167656791105

10815718919818918116511689971008158485081

13317918919619617991402642818367241656

1461961981981989726505650348973341024

1081791891891733465402458424873321016

4012417118917356482682632264824816

1034891491496724241016161816181618

10162456653416161016241818181626

1081624242418161618182418263440

50241824422616263232345648505050

6765588111365247375757367736573157

5897891161301167310510510591918191173189

50738910812413011311612111310081113179189181

�

�

0, 0�:ℝ → ℝ

12

Imaginea ca şi funcţie

�

0, 0 �� �, � ∈ ℝ

� ∈ ℝ

� ∈ ℝ

���

13

Imaginea color ca şi funcţie

�:ℝ → ℝ�

�O imagine color este

reprezentată pe 3 canale (Red,

Green, Blue

14

Operaţii pe puncte

�Considerăm o singură imagine de intrare

)],([),( yxpGyxq =

G(.)

(x,y) (x,y)

Imaginea intrare p(x,y) Imaginea ieşire q(x,y)

(0,0) (0,0)

(M-1,N-1) (M-1,N-1)

ayxpyxq += ),(),(Adunare cu un scalar a:

15

Zgomotul în imagini

�Zgomotul este un semnal perturbator ce se combina cu imaginea

originală

�� �, � = � �, � + �(�, �)�Tipuri de zgomote:

� ”Salt and Pepper”: apariţii aleatoare de pixeli albi şi negrii

�Zgomot impuls: apariţii aleatoare de pixeli albi

�Zgomot Gaussian: variaţii ale intensităţii pixelilor generate

dintr-o distribuţie Gaussiană

16

Distribuţia Gaussiană

�Distribuţia Gauss �(�, �), sau Normală, este o funcţie continuă de

probabilitate

�Funcţia de densitate de probabilitate (cazul 1-dimensional):

� � �, � = 12�� exp −

(� − �)2�

� ∈ ℝ– media

� ∈ ℝ– deviaţia standard

� ∈ ℝ– varianţa

17

Distribuţia Gaussiană

18

Distribuţia Gaussiană multivariată�Cazul n-dimensional �(�, Σ):

� � �, " = 1(2�)#/|Σ|&/ exp −

12 (� − �)'Σ(&(� − �)

� ∈ ℝ# – vector medie

Σ ∈ ℝ#×# – matricea de covarianţă

|Σ| – determinantul matricei Σ

19

Ex: 2-dimensiuni

� = 00Σ = * = 1 00 1

� = 00Σ = 0.6 00 0.6

� = 00Σ = 2 00 2

Distribuţia normală standard

- – matricea identitate

20

Ex: 2-dimensiuni

Σ = 1 00 1 Σ = 1 0.50.5 1 Σ = 1 0.80.8 1

21

Ex: 2-dimensiuni

Σ = 1 −0.5−0.5 1Σ = 1 −0.8−0.8 1

Σ = 3 0.80.8 1

22

Ex: 2-dimensiuni

� = 10Σ = *

� = −0.50Σ = *

� = −1−1.5Σ = *

23

Generarea de zgomot gaussian

Cazul 1-dimensional

Cazul 2-dimensional

24

Generarea de zgomot gaussian�Efectul covarianţei Σ în zgomotul Gaussian

� = 2 � = 8

� = 32 � = 64

25

Zgomotul Gaussian

�� �, � =� �, � + �(�, �)

26

Filtrarea unui semnal 1-dimensional

�

�2

�Semnalul filtrat �2 este o medie ponderată a semnalului original �

27

Filtrarea unui semnal 1-dimensional

�2(3) = � 3 − 2 + � 3 − 1 + � 3 + � 3 + 1 + � 3 + 25

�

�2

28

�2(3) = 124 + 1 5 �(3 + 6)

7

89(7

�

�2

29

�

�2

�2(3) = 124 + 1 5 �(3 + 6)

7

89(7

30

�

�2

�2(3) = 124 + 1 5 �(3 + 6)

7

89(7

31

Filtrarea unui semnal 1-dimensional

32

Filtrarea imaginilorSemnal 2-dimensional

�Filtrarea unei imagini: calculul unei funcţii de vecinătăţi la fiecare

poziţie a imaginii

�Utilizări:

� Îmbunătăţirea imaginilor:

� Reducerea zgomotului, mărire/micşorare, îmbunătăţirea contrastului, etc.

�Extragerea informaţiei din imagini:

� Textură, cante, puncte distince (colţuri)

�Detecţia de obiecte

� Template matching

7 7 7 7

7 6 6 7

7 7 7 7

7 7 7 7

7 0 7 7

7 7 7 7

1/9 1/9 1/9

1/9 1/9 1/9

1/9 1/9 1/9

Imaginea de intrare Imaginea de ieşire

Filtru (mască)

(1,1): 6222.69

56

9

178

9

17

9

17

9

17

9

17

9

10

9

17

9

17

9

17

9

17 ≈==⋅⋅=⋅+⋅+⋅+⋅+⋅+⋅+⋅+⋅+⋅

(1,2): 6222.69

56

9

178

9

17

9

17

9

17

9

17

9

17

9

10

9

17

9

17

9

17 ≈==⋅⋅=⋅+⋅+⋅+⋅+⋅+⋅+⋅+⋅+⋅

Filtre de netezire: Filtrul median

],[ lkg],[ nmh],[ nmf

33

111

111

111

],[ ⋅⋅g

Filtrarea spaţială

- imaginea de intrare (originală)

- filtrul (masca = kernel =

template)

- imaginea de ieşire (filtrată)

],[ lkg

],[ nmh

],[ nmf

3=l

3=k

�Filtrarea spaţială se obţine prin operaţia de convoluţie a filtrului

(măştii = kernel = template) :;<, => cu imaginea de intrare �;?, @>

Box filter

34

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

Credit: S. Seitz

],[],[],[,

lnkmflkgnmhlk

++=∑

[.,.]h[.,.]f111

111

111

],[g ⋅⋅Convoluţia 2D

35

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 10

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

[.,.]h[.,.]f

Credit: S. Seitz

],[],[],[,

lnkmflkgnmhlk

++=∑

111

111

111

],[g ⋅⋅Convoluţia 2D

36

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 10 20

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

[.,.]h[.,.]f

Credit: S. Seitz

],[],[],[,

lnkmflkgnmhlk

++=∑

111

111

111

],[g ⋅⋅Convoluţia 2D

37

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 10 20 30

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

[.,.]h[.,.]f

Credit: S. Seitz

],[],[],[,

lnkmflkgnmhlk

++=∑

111

111

111

],[g ⋅⋅Convoluţia 2D

38

0 10 20 30 30

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

[.,.]h[.,.]f

Credit: S. Seitz

],[],[],[,

lnkmflkgnmhlk

++=∑

111

111

111

],[g ⋅⋅Convoluţia 2D

39

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

[.,.]h[.,.]f

Credit: S. Seitz

],[],[],[,

lnkmflkgnmhlk

++=∑

111

111

111

],[g ⋅⋅

0 10 20 30 30

50

Convoluţia 2D

40

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 90 0 90 90 90 0 0

0 0 0 90 90 90 90 90 0 0

0 0 0 0 0 0 0 0 0 0

0 0 90 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 10 20 30 30 30 20 10

0 20 40 60 60 60 40 20

0 30 60 90 90 90 60 30

0 30 50 80 80 90 60 30

0 30 50 80 80 90 60 30

0 20 30 50 50 60 40 20

10 20 30 30 30 30 20 10

10 10 10 0 0 0 0 0

[.,.]h[.,.]f

Credit: S. Seitz

],[],[],[,

lnkmflkgnmhlk

++=∑

111

111

111

],[g ⋅⋅Convoluţia 2D

41

000010000

Original

?

Source: D. Lowe

Exemple filtrare

42

000010000

Original Filtrare(nicio schimbare)

Source: D. Lowe

Exemple filtrare

43

000100000

Original

?

Source: D. Lowe

Exemple filtrare

44

000100000

Original Shiftare cu 1 pixel către stânga

Source: D. Lowe

Exemple filtrare

45

Original

111111111

000020000 - ?

(Suma filtrelor este 1)

Source: D. Lowe

Exemple filtrare

46

Original

111111111

000020000 -

Filtru de accentuare a contururilor- accentuează diferenţele dintre

pixeli utilizând media locală

Source: D. Lowe

Exemple filtrare

47

Source: D. Lowe

Accentuarea contururilor (sharpening)

Înainte După

48

-101

-202

-101

Cantă verticală(valoare absolută)

Sobel

Filtrul Sobel: direcţia verticală (axa y)

49

-1-2-1

000

121

Cantă orizontală(valoare absolută)

Sobel

Filtrul Sobel: direcţia orizontală (axa x)

50

51

Convoluţia 2D

�Fie : <, = → ℝ un kernel (template = mască) şi � ?, @ → ℝ o

imagine, operaţia de convoluţie � ∗ : este definită ca şi:

� �, � ∗ : �, � = B B � � − C, � − D : C, D ECEDFG

� �, � ∗ : �, � =55�;� − 3, � − H>:;3, H>IJ

52

Proprietăţiile convoluţiei

�Comutativitate: � ∗ : = : ∗ ��Asociativitate: � ∗ : ∗ ℎ = � ∗ (: ∗ ℎ)�Distributivitate: � + : ∗ ℎ = � ∗ ℎ + : ∗ ℎ�Liniaritate: L� + M: ∗ ℎ = L� ∗ ℎ + M: ∗ ℎ� Invarianţă la translaţie: � � + N ∗ ℎ = (� ∗ ℎ)(� + N)�Regula de derivare: O

O� � ∗ : = O�O� ∗ :

Imagine coruptă de zgomot gaussian

Imagine prelucrată cu un filtru median 3x3

∗

111

111

111

9

1

),(),( yxgyxf ∗

Exemplu: Filtrul median

53

),(),( yxgyxf ∗

∗

11111

11111

11111

11111

11111

25

1

Imagine coruptă de zgomot gaussian

Imagine prelucrată cu un filtru median 5x5

Exemplu: Filtrul median

54

Exemplu : Segmentarea prin partiţionare

: �, � = P255, � �, � > R0, � �, � ≤ RT:: R = 100

55

Filtrul Gaussian

0.003 0.013 0.022 0.013 0.003

0.013 0.059 0.097 0.059 0.013

0.022 0.097 0.159 0.097 0.022

0.013 0.059 0.097 0.059 0.013

0.003 0.013 0.022 0.013 0.003

5 x 5, σ = 1

�Ponderile kernelului gaussian sunt cu atât mai mari cu cât sunt

mai apropiate de centrul măştii

:(C, D) = 12�� exp −

C + D2�

56

Exemplu: Filtrul gaussian

57

Exemplu: Filtrul median

58

59

Proprietăţiile filtrului Gaussian

� Înlătură ”frecvenţele înalte” din imagine (filtru trece jos):

� Imaginea devine mai netedă

�Convoluţia fitrului Gaussian cu el însuşi rezultă într-un alt filtru

Gaussian:

�Filtrarea de două ori cu un kernel de mărime mică (ex. 3 × 3)

este acelaşi lucru cu o singură filtrare cu kernel mare (ex. 5 × 5)

�Convoluţia de două ori cu un kernel de dimensiune � × � este

acelaşi lucru cu convoluţia cu un kernel de dimensiune � × ��Kernel separabil:

�Se factorizează în produsul a două funcţii Gaussiene 1D

60

Separabilitatea kernelului Gaussian

�Kernelul 2D Gaussian poate fi exprimat ca produsul a două funcţii,

una dependentă de �, iar cealaltă dependentă de �� În acest caz, cele două funcţii sunt (identic) 1D Gaussian

:(�, �) = 12�� exp −

� + �2�

:(�, �) = 12�� exp −

�2�

12�� exp −

�2�

61

Varianţa kernelului Gaussian

�Varianţa (�) sau deviaţia standard (�) determină gradul de netezire

� = 0.6(kernel 30 × 30)

� = 2(kernel 30 × 30)

62

Varianţa kernelului GaussianZgomot Gaussian

Dimensiune kernel Gaussian

63

Template matching

64

Template matching�Obiectiv: gasirea poziţiei în imagine

�Mărimi de similaritate (sau distanţă)

dintre două regiuni:

�Corelaţie

�Corelaţie zero-mean

�Suma Diferenţelor Pătratice -

Sum of Squared Difference

(SSD)

�Cross-Corelaţie Normalizată

Input Imagine filtrată

],[],[],[,

lnkmflkgnmhlk

++=∑f = imaginea

g = filtrul (kernel)

Problema: Raspunsul

este puternic pentru

intensităţi mari ale

pixelilor

Template matching�Obiectiv: gasirea poziţiei în imagine

�Metoda 0: convoluţia imaginii cu regiunea ochiului

65

Input Imagine filtrată (scalată) Imagine binarizată

)],[()],[(],[,

lnkmgflkfnmhlk

++−=∑

Detecţii pozitive

Detecţiifalse

Media lui �

Template matching�Obiectiv: gasirea poziţiei în imagine

�Metoda 1: filtrarea imaginii cu un ochi centrat pe media zero

66

Input Imagine binarizată

2

,

)],[],[(],[ lnkmflkgnmhlk

++−=∑

Detecţii pozitive

Template matching�Obiectiv: gasirea poziţiei în imagine

�Metoda 2: SSD

U − VVW 67

Input 1- sqrt(SSD)

2

,

)],[],[(],[ lnkmflkgnmhlk

++−=∑

Dezavantaj: SSD are sensibilitate la

intensitatea medie. Daca imaginea are intensitate mare, atunci vom avea

multe detecţii false.

Template matching�Obiectiv: gasirea poziţiei în imagine

�Metoda 2: SSD

68

∑ ∑

∑

−−−−

−−−−

=

lk

nm

lk

nm

lk

flnkmfglkg

flnkmfglkg

nmh

,

2,

,

2

,,

)],[()],[(

)],[)(],[(

],[

media regiunii din imaginemedia kernelului

Template matching�Obiectiv: gasirea poziţiei în imagine

�Metoda 3: Cross-Corelaţie Normalizată

69

Input Cross-Corelaţie Normalizată Imagine binarizată

Detecţii pozitive

Template matching�Obiectiv: gasirea poziţiei în imagine

�Metoda 3: Cross-Corelaţie Normalizată

70

Input

Template matching�Obiectiv: gasirea poziţiei în imagine

�Metoda 3: Cross-Corelaţie Normalizată

Cross-Corelaţie Normalizată Imagine binarizată

Detecţii pozitive

71

Template matching

�Care este cea mai bună metodă pentru stabilirea corelaţiei?

�SSD: mai rapidă, sensibilă la intensitatea pixelilor

�Cross-Corelaţie Normalizată: mai înceată, invariantă la

intensitatea medie a regiunilor din imagine şi contrast

� În realitate, niciunul din criterii nu este reprezentativ pentru

sistemele moderne de recunoaştere de obiecte

72

Dorim să gasim ochi de dimensiuni mai mici sau mai mari!

Piramidele de imagini

Imagine filtrată ”trece-jos”

Imagine

FiltruGaussian Sample

Imagine micşorată

73

Source: Forsyth

Piramidă Gaussiană

74

Template matching prin piramidele de imagini

� Input: imagine; template (kernel)

1. Template matching la scala curentă

2. Micşorare (downsample) imagine

3. Repetă operaţiile 1-2 până când imaginea este foarte mică

4. Consideră pozitive răspunsurile peste un anumit Threshold

(luând în considerare şi supresia non-maximă)

75

este operatorul Laplace:

Laplace de Gaussian

Gaussian Derivata funcţiei Gaussian

Filtre de detecţie a cantelor

76

GaussianImpuls unitar

Laplacian of Gaussian

Source: Lazebnik

Filtrul Laplace

77

http://sepwww.stanford.edu/~morgan/texturematch/paper_html/node3.html

Calculul piramidei Gaussian/Laplace

78

Source: Forsyth

Piramidă Laplace

79

80