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