Sem vložte zadání Vaší práce.
České vysoké učení technické v Praze
Fakulta informačních technologií
Katedra teoretické informatiky
Magisterská práce
Metody pro identifikaci vzorků
z hutní výroby
Bc. Juraj Leškanič
Vedoucí práce: Ing. Pavel Kordík, PhD.
9. mája 2012
Poďakovanie
V prvom rade si dovoľujem poďakovať svojim rodičom za neustálu podporu
a čas, ktoré mi venovali počas celého štúdia. Veľká vďaka patrí aj vedúcemu
tejto diplomovej práce Ing. Pavlovi Kordíkovi, PhD. za odborné vedenie a jeho
cenné pripomienky a rady pri vzniku tejto práce.
Prehlásenie
Prehlasujem, že som túto prácu vytvoril samostatne a použil som len podklady
uvedené v priloženom zozname.
V zmysle §60 Zákona č. 121/2000 Sb., o autorskom práve, o právach súvisiacich
s právom autorským a o zmene niektorých zákonov (autorský zákon), nemám
závažný dôvod proti použitiu tohto školského diela a k použitiu udeľujem
zvolenie.
V Prahe dňa 9. mája 2012
.....................
7
České vysoké učení technické v Praze
Fakulta informačních technologií
c 2012 Juraj Leškanič. Všechna práva vyhrazena.
Tato práce vznikla jako školní dílo na Českém vysokém učení technickém
v Praze, Fakultě informačních technologií. Práce je chráněna právními předpisy a mezinárodními úmluvami o právu autorském a právech souvisejících
s právem autorským. K jejímu užití, s výjimkou bezúplatných zákonných licencí, je nezbytný souhlas autora.
Odkaz na túto prácu
Juraj Leškanič. Metody pro identifikaci vzorků z hutní výroby: Magisterská
práce. Praha: ČVUT v Praze, Fakulta informačních technologií, 2012.
Abstract
The purpose of this master thesis is to test different methods of feature extraction from image data, which serves for identification of metallurgical samples.
Another goal is to try to increase the quality of this data before the identification using pre-processing perhaps even post-processing. To suggest and
compare different consecutions of editing and to recommend the best one and
consequently test different approaches of pattern matching.
Keywords: digital image processing, spatial filtering, feature extraction,pattern
matching, moment invariants, Zernike moments, k-nearest neighbor, neural
network, decision tree, naive-bayes classifier.
Abstrakt
Cieľom tejto diplomovej práce je otestovať rôzne metódy extrakcie príznakov z obrazových dát, ktoré slúžia na identifikáciu metalurgických vzoriek,
pokúsiť sa zlepšiť kvalitu týchto dát, pred samotnou identifikáciou pomocou
metód pre-processingu, prípadne post-procesingu, navrhnúť a porovnať rôzne
postupy úprav a doporučiť ten najvhodnejší a následne otestovať rôzne prístupy klasifikácie vzorov (pattern matching).
Kľúčové slová: spracovanie digitálneho obrazu, priestorová filtrácia, extrakcia príznakov, rozpoznávanie vzorov, invarianty, Zernikeho momenty, klasifikátor najbližšieho suseda, neurónová sieť, rozhodovací strom, Bayesov klasifikátor.
9
Obsah
Úvod
17
1 Spracovanie obrazu
19
2 Predspracovanie obrazových dát
2.1 Priestorové filtre - Spatial filtering . . . . .
2.2 Zvýšenie kvality obrazových dát . . . . . . .
2.2.1 Lineárne filtre . . . . . . . . . . . . .
2.2.1.1 Smoothing Linear Filters .
2.2.1.2 Sharpening Spatial Filters
2.2.2 Nelineárna filtrácia . . . . . . . . . .
2.2.2.1 Mediánový filter . . . . . .
2.2.2.2 Max a min filter . . . . . .
2.2.2.3 Bilaterálny filter . . . . . .
2.3 Segmentácia obrazu . . . . . . . . . . . . .
2.3.1 Detekcia bodov, línií a hrán . . . . .
2.3.1.1 Houghova transformácia . .
2.3.2 Thresholding . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Rozpoznávanie vzorov - pattern matching
3.1 Reprezentácia a deskripcia vzorov . . . . . . . . . . .
3.1.1 Jednoduché priestorové deskriptory . . . . . .
3.1.2 Momenty . . . . . . . . . . . . . . . . . . . .
3.1.2.1 Momentové invarianty voči posunu,
zmene mierky . . . . . . . . . . . .
3.1.3 Zernikeho momenty . . . . . . . . . . . . . .
3.2 Klasifikácia vzorov . . . . . . . . . . . . . . . . . . .
3.2.1 Metriky a klasifikátor najbližšieho suseda . .
3.2.2 Bayesovská teória a Bayesovský klasifikátor .
3.2.2.1 Naive-Bayes klasifikátor . . . . . . .
3.2.3 Neurónové siete . . . . . . . . . . . . . . . . .
3.2.4 Rozhodovacie stromy . . . . . . . . . . . . . .
4 Experimentálna časť
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . .
. . . .
. . . .
rotácii
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
. .
. .
a
. .
. .
. .
. .
. .
. .
. .
. .
21
21
23
25
25
26
31
32
32
34
36
37
42
45
47
48
48
49
50
52
54
55
56
57
58
60
63
11
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
Spracovanie a identifikácia vzoriek s razenou identifikačnou známkou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Porozumenie problému a dátam . . . . . . . . . . . . . .
4.1.2 Predspracovanie . . . . . . . . . . . . . . . . . . . . . .
4.1.2.1 Lokalizácia identifikátora . . . . . . . . . . . .
4.1.2.2 Separácia jednotlivých častí identifikátora . . .
Extrakcia príznakov . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Grid features . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Angles features . . . . . . . . . . . . . . . . . . . . . . .
4.2.3 Centrálne momenty . . . . . . . . . . . . . . . . . . . .
4.2.4 Zernike moments . . . . . . . . . . . . . . . . . . . . . .
Experiment I . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Experiment II . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Experiment III . . . . . . . . . . . . . . . . . . . . . . . . . . .
Experiment IV . . . . . . . . . . . . . . . . . . . . . . . . . . .
Automatická lokalizácia, separácia a klasifikácia identifikátora .
Spracovanie a identifikácia vzoriek s farebným náterom . . . . .
4.8.1 Porozumenie problému a dátam . . . . . . . . . . . . . .
4.8.2 Predspracovanie . . . . . . . . . . . . . . . . . . . . . .
64
64
65
68
68
69
70
71
71
72
73
74
75
80
81
84
85
86
Záver
89
Literatúra
91
A Zoznam použitých skratiek a symbolov
93
B Obrazové prílohy a vzniknuté materiály
95
C Obsah priloženého CD
101
12
Zoznam obrázkov
1.1
Projekcia dvojrozmerného digitálneho obrázku do trojrozmerného
systému . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13
2.14
2.15
2.16
2.17
2.18
2.19
Ukážka základného princípu aplikácie priestorovej filtrácie . .
Mechanizmus lineárnej priestorovej filtrácie . . . . . . . . . .
Vybrané typy šumu . . . . . . . . . . . . . . . . . . . . . . . .
Ukážka vyhladzovacích filtrov . . . . . . . . . . . . . . . . . .
Ukážka filtrov na výpočet derivácie funckie jednej premennej
Ilustrácia výpočtu a vlastností derivácií . . . . . . . . . . . .
Dvojrozmerné aproximácie Laplaciánu dvoch premenných . .
Ukážka použitia Laplaciánu . . . . . . . . . . . . . . . . . . .
Ukážka použitia unsharp masking-u a highboost filtering-u .
Ukážky použitia priemerovania a mediánového filtra . . . . .
Schématické zobrazenie použitia bilaterálneho filtra . . . . . .
Porovnanie Gaussovského a bilaterálneho filtra . . . . . . . .
Filtračné masky určené na detekciu línií . . . . . . . . . . . .
Filtre na výpočet gradientných zložiek . . . . . . . . . . . . .
Ukážky filtrov používaných na detekciu hrán v obraze . . . .
Ukážky použitia filtrov na detekciu hrán v obraze . . . . . . .
Ilustrácia vytvorenia Houghovho parametrického priestoru . .
Aplikácia Houghovej transformácie na reálny obrázok . . . .
Ukážka použitia thresholdingu . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22
24
24
25
27
28
29
30
31
33
35
36
38
39
40
41
43
44
45
3.1
3.2
3.3
3.4
Ukážka princípu extrakcie príznakov . .
Ilustrácia separácie objektov dvoch tried
Schématická ukážka neurónovej siete . .
Ukážka rozhodovacieho stromu . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
49
51
59
60
4.1
4.2
4.3
4.4
4.5
4.6
4.7
Ukážka vzorky s razeným identifikátorom . . . . . . . . . . . . . .
Ukážka použitia rôznych predspracovacích techník . . . . . . . . .
Ukážka lokalizovaného identifikátoru . . . . . . . . . . . . . . . . .
Separácia číslic . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Separované číslice upravené pred extrakciou grid features . . . . .
Separované číslice upravené pred extrakciou centrálnych momentov
Separované číslice upravené pred extrakciou ZM . . . . . . . . . .
65
66
68
69
71
72
73
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13
Graf zobrazujúci závislosť úspešnosti k-NN na parametri k . . . .
Ukážka rozloženia tried a ich odchýlky pre CM . . . . . . . . . . .
Ukážka rozloženia tried a ich odchýlky pre ZM . . . . . . . . . . .
Zobrazenie zhlukov jednotlivých objektov prostredníctvom scatterplotu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ukážka invariancie príznakov voči rotácii v spojení s k-NN . . . .
Ukážka invariancie príznakov voči rotácii v spojení s NB . . . . . .
Ukážka lokalizovaného identifikátora na snímke vzorky s razeným
identifikátorom . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ukážka použitia Houghovej tranformácie na reálnych dátach . . .
Ukážky nesprávnej separácie číslic . . . . . . . . . . . . . . . . . .
Ukážka vzorky s farbeným identifikátorom . . . . . . . . . . . . . .
Rôzne postupy predspracovania vzoriek s farebným identifikátorom
Ukážka porovnania výsledkov predspracovania u razeného a farbeného identifikátoru . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
77
78
B.1 Ukážka nepresnej lokalizácie . . . . . . . . . . . . . . . . . . . . .
B.2 Ukážka nesprávne klasifikovaných číslic . . . . . . . . . . . . . . .
B.3 Ukážka fontu ID8400 . . . . . . . . . . . . . . . . . . . . . . . . . .
95
96
97
4.8
4.9
4.10
4.11
4.12
4.13
4.14
4.15
4.16
4.17
4.18
4.19
14
79
80
81
82
83
84
85
86
87
Zoznam tabuliek
4.1
4.2
Počty jednotlivých číslic v dostupných dátach . . . . . . . . . . . .
Tabuľka zobrazujúca použitie rôznych klasifikátorov v kombinácii
s rôznymi typmi príznakov (zachované všetky atribúty). . . . . . .
Feature selection 1 . . . . . . . . . . . . . . . . . . . . . . . . . . .
Feature selection 2 . . . . . . . . . . . . . . . . . . . . . . . . . . .
Korelačná matica pôvodných CM . . . . . . . . . . . . . . . . . . .
Korelačná matica redukovaných CM . . . . . . . . . . . . . . . . .
Počty jednotlivých číslic v trénovacej a testovacej množine . . . . .
73
75
75
76
76
83
B.1 Tabuľka zobrazujúca úspešnosť klasifikácie pri rôznych uhloch otočenia generovaných dát . . . . . . . . . . . . . . . . . . . . . . . . .
B.2 Korelačná matica redukovaných príznakov ZM8 . . . . . . . . . . .
96
98
4.3
4.4
4.5
4.6
4.7
64
15
Úvod
Automatizácia spojená so spracovaním digitálneho obrazu sa veľmi rýchlo rozvíja, rozširuje sa sféra jej aplikácie a preniká hlboko do oblasti vedy a techniky.
V tejto dobe takmer neexistuje oblasť, ktorá by nebola aspoň okrajovo dotknutá spracovaním obrazu. Na prvý pohľad to možno nie je také zrejmé, ale
je nutné si uvedomiť, že sa so spracovaním obrazu stretávame v sférach od
medicínskej cez priemyselnú, až po astronomickú. V každej oblasti sú samozrejme ciele spracovania rôzne a tak toto spracovanie digitálneho obrazu zahŕňa obrovské množstvo techník a metód používaných na dosiahnutie týchto
cieľov. Zautomatizovanie týchto procesov má za dôsledok zrýchlenie výroby,
presnejšie merania, zvýšenie bezpečnosti (v oblastiach, kde existuje nejaké
nebezpečenstvo ohrozenia), . . .
V tejto práci pojednávame zväčša o automatickom spracovaní obrazu, konkrétne o procesoch automatickej idenfitikácie metalurgických vzoriek z hutného priemyslu. V tomto odvetví je potrebné takéto vzorky identifikovať pomerne presne, pretože tie môžu byť ďalej použité na rôzne účely a pri zlej
identifikácii by mohlo dôjsť dokonca k zastaveniu výroby a podobne, práve
kvôli dodaniu zlého materiálu. Pohľad z druhej strany je však taký, že získanie
digitálneho obrazu v takejto sfére je často ovplyvnené prostredím v akom sa
s danými vzorkami pracuje (zvýšená teplota, prašné prostredie, nedostatočné
svetelné podmienky a pod.). Je teda možné, že kvalita snímkov použitých na
identifikáciu by nebola dostatočná a preto bude nevyhnutné použiť metódy
schopné sa s takýmto problémom vysporiadať. Ďalšou komplikáciou môže byť
to, že robustné spracovávanie obrazu, ktoré by dokázalo spracovať aj menej
kvalitné snímky môže trvať nejakú dobu, čo je samozrejme nežiadúcim faktorom (spracovanie a vyhodnotenie by malo byť takmer real-time). V práci sa
teda zameráme na rôzne metódy spracovania, od najjednoduchších až po zložité a hodnotiacim kritériom bude samozrejme kvalita rozpoznávania. Metódy,
ktoré budeme testovať, by mali byť schopné vysporiadať sa aj s neočakávanými udalosťami, napríklad zmena farby náteru a pod. Výsledkom tejto práce
by malo byť doporučenie postupu aplikácie metód spracovania obrazu a rozpoznávania vzorov, ktoré dosiahne požadované výsledky, čo sa týka presnosti
a rýchlosti a aj doporučenie spôsobu značenia týchto vzoriek, aby nemohlo
dochádzať k omylom pri takomto spracovaní.
17
KAPITOLA
Spracovanie obrazu
Pojem obrazu prichádza z reálneho sveta ako zobrazenie nejakej skutočnosti
zachytenej na určitú formu média. Teoreticky môžme digitálny obrázok definovať ako spojitú funkciu dvoch premenných I(x, y) : R2 ⇒ Rn . V praxi však
obrázok definujeme ako maticu pixelov I[x, y] : N2 ⇒ Rn , kde x a y sú súradnice jednotlivých bodov obrázku, a hodnotu funkcie I každej dvojice súradníc
nazývame intenzitou stupňa šedi. Ak n = 1 ide teda o obrázok v stupňoch
šedi alebo ak n = 3 ide o farebný obrázok so složkami RGB. Na obrázku 1.1
môžme vidieť názornú reprezentáciu obrázku v stupňoch šedi.
Obr. 1.1: Projekcia dvojrozmerného digitálneho obrázku do trojrozmerného
systému
Pojem spracovanie digitálneho obrazu úzko súvisí s použitím prostriedkov digitálneho počítača. Digitálny obrázok je zložený z elementov, z ktorých
každý má svoju presnú polohu a hodnotu a tieto elementy najčastejšie nazývame pixely.
Prácu s digitálnym obrazom môžme rozdeliť na dve veľké skupiny a to
spracovanie obrazu a tzv. computer vision. Patria sem rôzne metódy a tech19
1
1. Spracovanie obrazu
niky, ktoré využívajú prvky z oboch skupín a existuje určitá paradigma ako
tieto techniky rozdeľovať: nízky, stredný a vysoký stupeň [11, 4]:
1. najnižší stupeň zahŕňa primitívne techniky, ktoré sú späté s pre-processingom,
teda so zvyšovaním kvality obrazu, redukciou šumu, zaostrovaním, vylepšovaním kontrastu a pod. Základnou vlastnosťou týchto metód je, že
ich vstupom aj výstupom je obrázok ako taký (väčšinou značne upravený).
2. stredný stupeň zahŕňa už určitú časť abstrakcie. To znamená, že vstupom pre tieto techniky je samozrejme obrázok, ale výstupom sú len atribúty získané z tohto obrázka (napr. hrany, objekty a pod.). Metódami
tohto stupňa sú úlohy ako segmentácia, identifikácia (objektov, hrán,
. . . ), analýza tvaru, detekcia a podobne.
3. do najvyššieho stupňa patria procesy spojené so sledovaním objektov a
s prvkami počítačového videnia ako aj stabilizácia obrazu a podobne.
V tejto práci budeme pojednávať hlavne o prvých dvoch kategóriách, ku
ktorým pridružíme techniky a metódy extrakcie príznakov a klasifikácie vzorov.
20
KAPITOLA
Predspracovanie obrazových
dát
V tejto kapitole predstavíme pár jednoduchých metód používaných na predspracovanie dát. Pod pojmom predspracovanie si môžme predstaviť zvýšenie kvality nie príliš kvalitného obrazu, prípadne zameranie sa na časti dát,
ktoré nás zaujímajú viac ako ostatné (napr. hrany, oválne útvary, rohy, . . . ).
Zvýšením kvality obrázku chápeme najmä úpravu farebnosti, jasu, kontrastu,
prípadne odstraňovanie šumu, ktorý samozrejme v značnej miere ovplyvňuje
následné spracovanie.
2.1
Priestorové filtre - Spatial filtering
V tejto časti zavedieme základné koncepty používania priestorovej filtrácie pre
spracovanie obrazu.
Termín priestorová filtrácia odkazuje na plochu samotného obrázku, ktorá
spolu s tretím rozmerom, hodnotami intenzít, vytvárajú akýsi priestor obrázku. Spracovanie obrazu týmito metódami je založené na priamej manipulácii s pixelmi v obrázku. Proces priestorovej filtrácie môžeme vyjadriť vzťahom
g(x, y) = T [f (x, y)],
(2.1)
kde f (x, y) je vstupný obrázok, g(x, y) je výstupný obrázok a T je operátor na f definovaný nad okolím bodu (x, y). Operátor môže byť použitý na
samostatný obrázok alebo aj na množinu obrázkov.
21
2
2. Predspracovanie obrazových dát
Počiatok obrázku
y
(x, y)
Okolie 3 × 3 bodu (x, y)
Obrázok
x
Obr. 2.1: Okolie 3 × 3 okolo bodu (x, y) v obrázku. Výstupný obrázok je výsledkom posúvania okolia z pixelu na pixel cez celý vstupný obrázok (upravené
podľa [4]).
Obrázok 2.1 demonštruje základnú myšlienku implementácie rovnice 2.1
na samostatnom obrázku. Okolie bodu (x, y) zobrazené na tomto obrázku
je dôležitým faktorom spracovania. Väčšinou je obĺžnikového (štvorcového)
tvaru, centrovaného na bod (x, y) a podstatne menšej veľkosti ako obrázok f .
Názov filter je zapožičaný z časti spracovania obrazu, ktorá pracuje vo
frekvenčnej oblasti, kde „filter“ odkazuje na prijímanie (passing) alebo potlačenie určitých frekvenčných komponentov. Napríklad filter, ktorý ponecháva
nízke frekvencie je nazývaný lowpass filter. Vytvorený efekt tohto filtra je vyhladenie (rozmazanie) obrázku. Takýto efekt dokážeme vytvoriť aj priamo na
obrázku ako takom, použitím priestorových filtrov (tiež nazývaných spatial
masks(masky), kernels(jadrá), windows(okná)). Oproti filtrom, ktoré pracujú
len vo frekvenčnej oblasti, majú priestorové filtre väčšie uplatnenie, pretože
ich dokážeme použiť aj na nelineárnu filtráciu, čo nedokážeme dosiahnuť vo
frekvenčnej oblasti [4].
Na obrázku 2.1 sme ukázali, že priestorový filter pozostáva z okolia (typicky malý štvorec), a určeného operátora, ktorý vykonáva požadovanú operáciu na daných pixeloch obrázku zahrňujúc toto okolie. Operácia filtra vytvorí
nový pixel so súradnicami odpovedajúcimi súradniciam centra okolia a jeho
hodnota je výsledkom tejto operácie.
Obrázok 2.4 popisuje mechanizmus lineárneho priestorového filtrovania použitím okolia 3 × 3. V každom bode (x, y), účinok g(x, y) filtra je suma členov
22
2.2. Zvýšenie kvality obrazových dát
koeficientov a jednotlivých pixelov obsiahnutých filtrom:
g(x, y) = w(−1, −1)f (x − 1, y − 1) + w(−1, 0)f (x − 1, y) + . . .
+ w(0, 0)f (x, y) + . . . + w(1, 1)f (x + 1, y + 1)
(2.2)
Centrum koeficientov filtra, w(0, 0), prislúcha pixelu na pozícii (x, y). Pre
masku veľkosti m × n, nadobúdajú parametre m a n hodnoty m = 2a + 1 a
n = 2b + 1, kde a a b sú kladné prirodzené čísla. To znamená, že väčšina filtrov
má veľkosť nepárnych dĺžok strán počínajúc filtrom 3 × 3 (vo väčšine prípadov
sú strany rovnakej dĺžky). Filtrovanie obrázku s veľkosťou M × N , filtrom s
veľkosťou m × n môžeme teda všeobecne popísať vzťahom:
g(x, y) =
a
b
X
X
w(s, t)f (x + s, y + t),
(2.3)
s=−a t=−b
kde x a y nadobúdajú hodnoty tak, aby každý pixel z w priľahol na každý
pixel v f .
2.2
Zvýšenie kvality obrazových dát
Veľkým problémom, s ktorým sa stretávame úplne bežne pri digitálnych obrazových dátach, je šum. Ten sa vyskytuje takmer u všetkých digitálnych obrázkov vytvorených aparátmi ako sú kamery a fotoaparáty, pretože ich optika
samozrejme nie je dokonalá, ako aj režim fotenia, statika a podobne. Ľubovoľný obrázok teda môžeme charakterizovať ako:
G = F + N,
(2.4)
kde G je reálny obrázok, F je ideálny obrázok, ktorý je narušený šumom N.
Odstraňovanie tohto šumu nie je banálnou vecou, pretože automaticky rozpoznať, ktorý pixel je porušený šumom, ako aj typ šumu je veľmi obtiažne.
Rozoznávame totiž niekoľko typov šumu, napríklad rozostrenie (pohybom),
impulzívny šum (obr. 2.3b), ktorý môže vzniknúť zväčša nedokonalosťou softvéru fotoaparátov - chýbajúce pixely (Salt&Pepper), . . .
23
2. Predspracovanie obrazových dát
Počiatok obrázku
y
Filter
w(−1,−1) w(−1,0)
w(−1,1)
Pixely
w(0,−1)
w(0,0)
w(0,1)
w(1,−1)
w(1,0)
w(1,1)
Obrázok
f (x−1,y−1) f (x−1,y) f (x−1,y+1)
Koeficienty filtra
x
f (x,y−1)
f (x,y)
f (x,y+1)
f (x+1,y−1) f (x+1,y) f (x+1,y+1)
Pixely obrázku
(oblasť pod filtrom)
Obr. 2.2: Mechanizmus lineárnej filtrácie s použitím 3 × 3 filtračnej masky
(upravené podľa [4])
(a) Gaussovský šum
(b) Impulzívny šum
Obr. 2.3: Vybrané typy šumu
24
2.2. Zvýšenie kvality obrazových dát
V súčasnosti sa využíva mnoho metód na potlačenie šumu a celkové zvýšenie kvality obrazu. V ďalších kapitolách rozoberieme jednotlivé prístupy počínajúc priestorovou filtráciou za pomoci lineárnych a nelineárnych priestorových filtrov, ale aj metódy využívané vo fotografickom priemysle.
2.2.1
Lineárne filtre
Lineárna filtrácia je základným prostriedkom spracovania obrazu a teda operátorom premeny vstupného signálu (obrazu) na signál výstupný pri dodržaní
obmedzení linearity. Filtre používané na dané operácie sú pomerne jednoduché na implementáciu a sú používané aj kvôli rýchlosti spracovania. Ako už
bolo spomenuté v kapitole 2.1, filter pozostáva z nadefinovanej operácie a okolia. Na základne tejto špecifickej operácie rozlišujeme niekoľko typov filtrov.
Lineárnou filtráciou dokážeme vylepšiť obraz z viacerých hľadísk: zaostrenie
hrán objektov v obraze, vyhladenie obrazu, redukovanie náhodného šumu,
oprava nerovnakého osvetlenia, oprava obrazu z dôvodu rozmazania pohybom
a podobne.
2.2.1.1
Smoothing Linear Filters
Tieto filtre sú využívané v predspracovaní obrazu najmä na vyhladenie a
redukciu šumu. Ich hlavnou úlohou je odstraňovanie irelevantných detailov
(šumu) z obrazu. Irelevantný detail je taká skupina pixelov, ktoré sú malé
v porovnaní s maskou filtra. Výstupom aplikácie týchto filtrov je priemerná
hodnota intenzít pixelov obsiahnutých okolím filtra (úprava susedných pixelov
tak, aby vyzerali podobne). Tieto filtre sa niekedy nazývajú aj priemerovacie,
averaging filtre. Procesom vyhladenia obrazu však môže byť aj strata ostrosti,
čo sa týka hodnôt inteznít jednotlivých pixelov. Keďže náhodný šum vlastne
pozostáva z vysokých rozdielov intenzít náhodného pixelu, väčšina aplikácií
týchto filtrov je za účelom redukcie šumu. Na druhú stranu sa v obraze väčšinou nachádzajú aj hrany, ktoré sú vlastne tiež tvorené vysokými rozdielmi
intenzít a teda vedľajším účinkom aplikácie týchto filtrov je rozmazanie hrán
v obraze [4].
1
9
×
1
1
1
1
1
1
1
1
1
1
16
×
1
2
1
2
4
2
1
2
1
Obr. 2.4: Dva (3 × 3) lineárne filtre používané na vyhladenie obrazu
25
2. Predspracovanie obrazových dát
Na obrázku 2.4 vidíme dva filtre, z ktorých prvý je používaný na tzv. štandardné priemerovanie pixelov pod filtrovacou maskou. Matematické vyjadrenie
si môžeme predstaviť asi takto:
R=
9
1X
zi ,
9 i=1
(2.5)
kde R je priemer intenzít pixelov v okolí 3 × 3 definovanom maskou. Na konci
procesu filtrovania sa hodnoty intenzít všetkých pixelov vydelia číslom 9 a tak
dostaneme správne hodnoty. Použitie koeficientov hodnoty 1 namiesto 19 je z
dôvodu výpočtovej a časovej zložitosti. Filter, ktorého koeficienty sú rovnaké,
sa nazýva aj box filter. Použitie takéhoto filtra je zobrazené na obrázku 2.10b
na porovnanie výsledku filtrácie s nelineárnym mediánovým filtrom.
Druhý filter na obrázku 2.4 je o niečo zaujímavejší ako ten prvý. Takúto
masku nazývame aj váženou priemerovacou maskou (weighted average mask),
čo znamená, že intenzity pixelov sú násobené rozdielnymi koeficientami, podľa
ktorých majú tieto pixely určitú významnosť. V tejto maske má najvyššiu významnosť centrálny pixel a so zvyšujúcou sa vzdialenosťou tento význam klesá.
Diagonálne členy majú dokonca nižší význam ako√pixely priamo susediace s
centrálnym, pretože vzdialenosť týchto pixelov je 2 na rozdiel od 1. Cieľom
takéhoto váženia je redukcia rozmazávania počas vyhladzovacieho procesu [4].
Všeobecne môžeme vážený filter s veľkosťou m × n, kde m, n sú nepárne, charakterizovať ako:
a
X
g(x, y) =
b
X
w(s, t)f (x + s, y + t)
s=−a t=−b
a
X
b
X
,
(2.6)
w(s, t)
s=−a t=−b
kde g(x, y) je výstupný obrázok po aplikácii filtra, w(s, t) je filter veľkosti
m × n, f (x, y) je spracovávaný obrázok. Táto rovnica je aplikovaná na všetky
hodnoty pozícií premenných x a y tak, že všetky elementy filtra w navštívia
každý pixel v obrázku f . Hodnoty a a b nadobúdajú hodnoty podľa veľkosti
n−1
masky filtra a = m−1
2 a b= 2 .
2.2.1.2
Sharpening Spatial Filters
Odtraňovanie šumu nie je jedinou technikou zvyšovania kvality obrazu. Vylepšovanie obrazu je proces, ktorý transformuje numerické dáta (obrázok), aby
sme získali nový obrázok s niektorými informáciami zoslabenými, inými naopak, čo najviac zosilnenými. Medzi takéto procesy patrí aj zaostrovanie, teda
zvýrazňovanie rozdielov inteznít v obraze. Týmto procesom dosiahneme zvýraznenie malých detailov, čo má úplne opačný efekt ako vyhladzovanie obrazu.
26
2.2. Zvýšenie kvality obrazových dát
Keďže vyhladzovanie obrazu sa javí ako opačná operácia k zaostrovaniu
a vyhladzovanie je integrácia pixelov v okolí (priemerovanie), je logické, že
zaostrovanie bude uskutočnené diferencovaním.
Princíp derivácie použitej v obraze je znázornený na obrázku 2.6. Pre prvú
deriváciu digitálnej funkcie platí:
1. derivácia je nulová pre oblasti s konštantnou intenzitou,
2. derivácia je nenulová na začiatku intenzitného sklonu alebo skoku,
3. derivácia je nenulová pozdĺž sklonu.
Pre druhú deriváciu platí:
1. podobne ako prvá derivácia, musí vykazovať nulové hodnoty v oblastiach
s konštantnou intenzitou,
2. musí byť nenulová na začiatku a na konci sklonu alebo skoku,
3. musí byť nulová pozdĺž sklonu s konštantným stúpaním alebo klesaním.
Základnou matematickou definícou pre prvú deriváciu digitálnej funkcie
jednej premennej f (x) je rozdiel
∂f
= f (x + 1) − f (x)
(2.7)
∂x
Takáto funkcia je veľmi ľahko transformovateľná na jednoduchý filter,
ktorý by teoreticky pracoval v jednorozmernom priestore na vytvorenie prvej
derivácie postupnosti intenzít pixelov. Takýto filter je zobrazený na obrázku
2.5a. Druhú deriváciu funkcie f (x) môžeme ďalej definovať ako rozdiel
∂2f
= f (x + 1) + f (x − 1) − 2f (x).
(2.8)
∂x2
Na obrázku 2.5b je podobne vytvorený filter, ktorý by realizoval druhú
deriváciu intenzít pixelov.
−1
1
(a)
1
−2
1
(b)
Obr. 2.5: Dva jednorozmerné filtre na výpočet prvej a druhej derivácie digitálnej funkcie s jednou premennou
Na obrázku 2.6 môžeme vidieť názorné zobrazenie derivácií jednorozmerného obrazu a môžeme si všimnúť, že ako prvá, tak aj druhá derivácia značne
27
2. Predspracovanie obrazových dát
reagujú na ostré zmeny intenzít susedných pixelov, zatiaľčo pri nemenných intenzitách majú vždy nulovú hodnotu. Druhá derivácia odhaľuje takéto zmeny
intenzity oveľa viac, keďže pri značnom rozdiele intenzít dochádza dokonca
k tzv. prechodu nulou. Tento prechod spája dva extrémy, ktoré sú v dátach
jednoducho identifikovateľné. Práve tieto prechody sú veľmi užitočné pri lokalizácii hrán, pretože práve hrany majú charakter takýchto skokov v intenzitách
susedných pixelov. Z toho vyplýva, že druhá derivácia nachádza lepšie uplatnenie pri identifikácii hrán a vylepšovaní detailov, pretože prvá derivácia má
nenulové hodnoty aj pozdĺž sklonov. Pri druhej derivácii však okolo detailu
(hrany), vznikne dvojitá hrana oddelená nulou a z toho vyvodíme dôsledok,
že druhá derivácia je preto vhodnejšia na vylepšovanie detailov [4, 8].
Intenzita
Zmena intenzity
6
5
4
3
2
1
0
Postupnosť
pixelov
Sklon
Skok
x
6
Prvá derivácia
6
6
1
1
1
1
1
1
6
6
6
6
0
0 -1 -1 -1 -1 -1 0
0
0
0
0
5
0
0
0
0
0 -1 0
0
0
0
0
5 -5
0
0
0
Druhá derivácia 0
6
5
4
0
3
0
2
0
1
6
x
5
4
3
Intenzita
2
1
x
0
-1
Prechod nulou
-2
-3
-4
Prvá derivácia
Druhá derivácia
-5
Obr. 2.6: Ilustrácia prvej a druhej derivácie jednorozmernej funkcie reprezentujúcej profil intenzít pixelov jednorozmerného obrazu (upravené podľa [4])
V predchádzajúcom príklade sme sa venovali jednorozmernému obrazu. Pri
použití druhej derivácie v obraze (funkcia dvoch premenných) však musíme
brať do úvahy ako os x tak aj os y. Jednotlivé druhé derivácie pre funkciu
f (x, y) potom sú
28
2.2. Zvýšenie kvality obrazových dát
∂2f
= f (x + 1, y) + f (x − 1, y) − 2f (x, y)
∂x2
∂2f
= f (x, y + 1) + f (x, y − 1) − 2f (x, y)
∂y 2
(2.9)
(2.10)
Keďže musíme uvažovať súčasne oba členy, tak celkový výsledok bude ich
súčtom. Takýto súčet nazývame Laplacián. Tento operátor je definovaný ako
∂2f
∂2f
+ 2
2
∂x
∂y
= f (x + 1, y) + f (x − 1, y) + f (x, y + 1) + f (x, y − 1)
∇2 f =
(2.11)
− 4f (x, y)
Táto rovnica môže byť implementovaná ako filter zobrazený na obrázku
2.7a. Tento filter dokáže odhaliť hrany len v smeroch osí x a y, čiže len v
kolmých smeroch. Ak by sme chceli pridať aj možnosť zvýraznenia detailov v
diagonálnych smeroch, filter by sme upravili tak, ako je zobrazené na obrázku
2.7b. Pridanie diagonálnych smerov k filtru má za následok pridanie ďalších
dvoch členov k výslednému Laplaciánu. Oba nové členy vyzerajú podobne
ako členy 2.9 s rozdielom súradníc tak, aby charakterizovali diagonálny smer.
V oboch pridaných členoch sa bude vyskytovať −2f (x, y) a tak pri použití
diagonálneho filtra bude vo výslednej rovnici člen −8f (x, y).
0
1
0
1
1
1
1
−4
1
1
−8
1
0
1
0
1
1
1
(a)
(b)
Obr. 2.7: Dve jadrá používané na aproximáciu Laplaciánu dvoch premenných,
obr. (b) - s rozšírením o diagonálne členy
Výsledkom aplikácie Laplaciánu je zvýraznenie alebo dokonca extrakcia
detailov z obrazu. Ak následne chceme pôvodný obraz zaostriť, čiže tieto extrahované detaily zvýrazniť, potrebujeme previesť ešte jednu operáciu. Operátor Laplaciánu totiž v obrázku eliminuje jednoliate plochy, plochy s rovnakým
stupňom intenzity. Aby sme dostali pôvodný obrázok, čiže so zachovaným
29
2. Predspracovanie obrazových dát
pozadím, musíme jednoducho spojiť pôvodný obrázok s obrazom zosilnených
detailov. Takúto operáciu prevedieme nasledovne
g(x, y) = f (x, y) + c[∇2 f (x, y)],
(2.12)
kde f (x, y) je vstupný obrázok, na ktorý chceme aplikovať operátor Laplaciánu, g(x, y) je výsledný obrázok po aplikácii tohto operátora a konštanta c
je normalizačná konštanta, ktorou volíme typ tohto operátora. Definícia typu
spočíva v tom, že operátor môže byť definovaný opačne ako na obrázku 2.7.
To znamená, že všetky hodnoty by mali opačné znamienko. Pre filtre uvedené
na obrázku 2.7 je hodnota konštanty c = −1.
Obr. 2.8: Ukážka použitia Laplaciánu. (a) - pôvodný (rozmazaný) obrázok,
(b) - zaostrený obrázok použitím Laplaciánu bez diagonálnych členov, (c) zaostrený obrázok použitím Laplaciánu s diagonálnymi členmi
Ďalším spôsobom využívajúcim podobný princíp ako sme popísali vyššie
je tzv. highboost filtering. Princíp tejto metódy spočíva v odčítaní vyhladeného obrázku od originálu, čím dostaneme tzv. masku. Túto masku následne pričítame k originálu. Vytvorenie masky teda zahŕňa vyhladenie obrázku, ktorý chceme zaostriť a odčítanie od originálu. Masku získame ako:
gmaska (x, y) = f (x, y) − f¯(x, y),
(2.13)
kde f¯(x, y) je pôvodný obrázok rozmazaný napríklad Gaussovským filtrom.
Následne pridáme masku váženú konštantou k originálu:
g(x, y) = f (x, y) + k.gmaska (x, y),
(2.14)
kde k ≥ 0. Ak k = 1 hovoríme o tzv. unsharp masking. Ak k > 1 tak
hovoríme o spomínanom highboost filteringu. Pre hodnoty nižšie ako 1 sa
príspevok takéhoto maskovania znehodnocuje [4]. Na obrázku 2.9 je ukážka
použitia highboost filteringu a unsharp maskingu.
30
2.2. Zvýšenie kvality obrazových dát
Obr. 2.9: Ukážka použitia highboost filteringu. (a) - pôvodný obrázok, (b) obrázok rozmazaný Gaussovským filtrom (7×7, σ = 3), (c) - unsharp masking,
(d) - highboost filtering (k = 3.5).
2.2.2
Nelineárna filtrácia
V posledných rokoch nelineárne metódy a techniky zaznamenali veľký rast a
rozvoj v oblasti spracovania obrazu a signálov. Dôvody rastu záujmu práve o
tieto metódy v sfére spracovania obrazu pramenia z pricípu ľudského vizuálneho systému, ktorý tiež zahŕňa nelineárne efekty a to je jednou z podstatných
vecí, ktoré musíme chápať pri vytváraní efektívnych algoritmov spracovania
obrazu.
V porovnaní s lineárnymi filtrami je známe, že lineárne filtre nedokážu odstrániť impulzívny šum, ktorý postihuje obrazové dáta, bez zničenia(rozmazania)
hrán a malých detailov. Hoci lineárne filtre stále hrajú významnú rolu pri
spracovaní obrazu, pretože sú jednoduché na implementáciu, výhody dnešných počítačov a procesorov, v zmysle rýchlosti, veľkosti a ceny, umožňujú
implementovať omnoho sofistikovanejšie algoritmy prakticky a efektívne [6].
Dnešné aplikácie nelineárnych filtrov zahŕňajú najmä vyhladzovanie so zachovávaním hrán, vylepšenie hrán, redukciu šumu, segmentáciu obrazu a extrakciu príznakov. Základnými triedami nelineárnych operátorov sú [6]:
• jednotvaré filtre, spoliehajúce sa na priníp superpozície,
31
2. Predspracovanie obrazových dát
• nelineárne priemerovacie filtre, používajúce nelineárne definície priemeru,
• morfologické filtre, založené na geometrických, nie štatistických vlastnostiach,
• polynomiálne filtre, používajúce polynomiálne vyjadrenie vstupných a
výstupných vzoriek,
• filtre založené na fuzzy logikách, uplatňujúce fuzzy rozhodovanie, ktoré
je typické pre niektoré typy výsledkov spracovania obrazu.
2.2.2.1
Mediánový filter
Filtre používajúce túto štatistiku sú veľmi efektívne v redukcii impulzívneho
šumu, pričom dokážu zachovať hrany signálu (obrazu). Zachovávanie hrán v
obrazových dátach je základnou esenciou v spracovaní obrazu, kvôli prirodzenému ľudskému vizuálnemu vnímaniu. Výsledok filtrovania takýmto filtrom je
založený na zoradení pixelov nachádzajúcich sa v obrázku a nahradení hodnoty
centrálneho pixelu hodnotou určenou ako výsledok zoradenia. U mediánového
filtra je táto hodnota určená ako medián
hodnôt
intenzít v okolí tohto pixelu,
kde medián je charakterizovaný ako N 2+1 −tá hodnota v zoradenej postupnosti hodnôt (hodnoty pod maskou filtra) [6]. Hodnota centrálneho pixelu je
teda:
g(x, y) = median {f (s, t)}
(2.15)
(s,t)∈Sxy
Na obrázku 2.10 je zobrazené porovnanie aplikácie lineárneho (priemerovacieho) a nelineárneho (medián) filtra na obrázok 2.10a, ktorý je narušený
impulzívnym šumom s pravdepodobnosťou Pw = Pb = 0, 2. Už voľným okom
dokážeme usúdiť, že filter používajúci mediánovú štatistiku oveľa lepšie odstránil impulzívny šum z obrázku, pričom hrany ostali takmer neporušené. U
priemerovacieho filtra vidíme značné ovplyvňovanie okolitých hodnôt napríklad hodnotou 17, ktorá je v rámci susedov omnoho nižšia, a tak všetkých
okolitých susedov ovplyvní znížením ich intenzity. Pri mediánovom filtri je
táto hodnota nahradená hodnotou 170, ktorá tam očividne podľa okolia patrí.
Mediánový filter je schopný odstrániť izolované zhluky pixelov, ktoré sú podstatne svetlejšie alebo tmavšie ako ich blízke okolie. Ak je plocha tohto zhluku
2
menšia ako m2 (polovica plochy filtračnej masky), tak je tento zhluk filtrom s
veľkosťou m × m odstránený. Odstránený znamená, že intenzita týchto pixelov
je potlačená v prospech mediánovej intenzity okolia [4].
2.2.2.2
Max a min filter
Mediánový filter je najbežnejšie používaný filter používajúci tzv. order-statistic.
Medián vyjadruje 50-ty percentil ohodnotených (zoradených) čísel. Filtre s
32
2.2. Zvýšenie kvality obrazových dát
(a)
(b)
(c)
170 204 170 187 170
170 204 170 187 170
170 204 170 187 170
187 9 170 147 153
187 9 170 147 153
187 9 170 147 153
170 170 170 187 170
170 170 140 187 170
170 170 170 187 170
153 17 170 221 153
153 151 170 221 153
153 170 170 221 153
170 170 170 170 204
170 170 170 170 204
170 170 170 170 204
(d)
(e)
(f)
Obr. 2.10: Odpovedajúce výstupy a ukážky matice intenzít pri použití priemerovania a mediánového filtra. (a) a (d) - pôvodný obrázok, (b) a (e) - výstup
po aplikácii priemerovania (filter 3×3), (c) a (f) - výstup po aplikácii mediánu
(filter 3 × 3)
názvom min alebo max sú tiež filtre založené na order-statistic, ale na rozdiel od mediánu využívaju 0-tý a 100-tý percentil. 0-tý percentil môžeme teda
chápať ako:
g(x, y) =
min {f (s, t)}
(2.16)
(s,t)∈Sxy
Tento filter sa používa na hľadanie najtmavšieho bodu v obrázku a tiež
redukuje salt šum (zložka impulzívneho šumu - salt & pepper). Na druhú
stranu 100-tý percentil môžeme vyjadriť nasledujúcim vzťahom:
g(x, y) = max {f (s, t)},
(2.17)
(s,t)∈Sxy
ktorého funkcia je opačná k funkcii min. Týmto filtrom dokážeme vyhľadať
najsvetlejší bod v obraze a keďže druhá zložka impulzívneho šumu pepper má
veľmi nízke hodnoty, operácia max je dobrá na jeho redukovanie v podobrázku
Sxy . Mediánový filter je vlastne akousi kombináciou týchto dvoch filtrov, pretože filtruje práve tieto odľahlé hodnoty, maximálnu a minimálnu (obe zložky
impulzívneho šumu).
33
2. Predspracovanie obrazových dát
2.2.2.3
Bilaterálny filter
Impulzívny šum nie je jediný, ktorý postihuje kvalitu digitálneho obrazu. Práve
ten je ľahko odstrániteľný spomínaným mediánovým filtrom, pretože hodnoty
jednotlivých zložiek tohto šumu sú extrémne voči blízkemu okoliu. Na druhú
stranu, tzv. Gaussovský šum (obr. 2.3a) má práve naopak tieto hodnoty pomerne podobné okoliu, ale pre ľudské oko alebo počítačové videnie má stále
rušivý efekt. Takýto šum je dobre odstrániteľný filtrom na rozmazávanie, ale
ako vieme, ten narúša aj hrany objektov a detaily, ktoré sú pre nás väčšinou
dôležité.
Nelienárnou filtráciou, ktorá vyjadruje to, že sa k podobrázku správa podľa
jeho obsahu, môžeme dosiahnuť odstránenie šumu bez narušenia hrán a významných detailov. Túto abilitu dokážeme zabezpečiť tzv. bilaterálnym filtrom, ktorý je sofistikovaným, nelineárnym rozšírením obyčajného Gaussovského filtru [7].
Keďže Gaussovský filter je nemenný voči okoliu, môžeme ho v bode p[px , py ]
definovať ako:
gG(px ,py ) =
a
b
X
X
Gσ (||(px , py ) − (qs , qt )||) f (qs , qt ),
(2.18)
s=−a t=−b
kde Gσ je dvojrozmerné Gaussovské jadro.
1
x2
Gσ (x) =
exp
−
2πσ 2
2σ 2
!
(2.19)
vyjadruje príspevok intenzity pixelu q na základe jeho priestorovej vzdialenosti ||(px , py ) − (qs , qt )|| od pixelu p. Parameter σ určuje rozsah okolia.
Podobne ako základný Gaussovský filter je aj bilaterálny definovaný ako
vážený priemer pixelov okolia okolo daného centrálenho pixelu. Hlavným rozdielom je, že bilaterálny filter berie do úvahy aj rozdiely intenzít jednotlivých
pixelov, aby bolo možné zachovať hrany v tomto okolí. Princíp vlastne spočíva
v tom, že dva pixely sú si navzájom podobné nielen na základe priestorovej
vzdialenosti, ale aj na základe určitej podobnosti v hodnote intenzity - v rozsahu. Bilaterálny filter teda môžeme definovať ako:
gBF (px ,py ) =
=
(2.20)
a
b
X
1 X
Gσs (||(px , py ) − (qs , qt )||) Gσr (|f (px , py ) − f (qs , qt )|) f (qs , qt ),
Wp s=−a t=−b
(2.21)
34
2.2. Zvýšenie kvality obrazových dát
kde Wp je normalizačný faktor:
Wp =
a
b
X
X
Gσs (||(px , py ) − (qs , qt )||) Gσr (|f (px , py ) − f (qs , qt )|) (2.22)
s=−a t=−b
Parametre σs a σr určujú množstvo filtrácie v obrázku f . Parameter Gσ s je
vážený priemer priestorového Gaussovského jadra, ktoré znižuje vplyv vzdialených pixelov a Gσ r je rozsahová zložka Gaussovského jadra, ktorá znižuje
vplyv pixelov s odlišnou hodnotou intenzity [7].
Na obrázku 2.11 môžeme názorne vidieť aplikáciu bilaterálneho filtra na
vstupný obrázok. Filter vyhladzuje obrázok zatiaľčo zachováva neporušené
hrany. Každý pixel je nahradený váženým priemerom svojich susedov. Kombinácia oboch komponentov, priestorovej a rozsahovej, zabezpečí prispievanie
len podobných pixelov z tohto okolia.
(d)
(e)
osť
alen
vzdi ázku
r
v ob
rozdiel
intenzít
p
q
(a)
(c)
(b)
Obr. 2.11: Schématické zobrazenie použitia bilaterálneho filtra, (a) - pôvodný
zašumený obrázok, (b) - dvojzložkový bilaterálny filter pre pozíciu pixelu p
získaný vynásobením zložiek (d) a (e), (c) - výsledný, upravený obrázok, (d) rozsahová zložka, (e) - priestorová zložka (upravené podľa [7])
Na obrázku 2.12 sú zobrazené ukážky obrázkov po aplikácii bilaterálneho
a obyčajného Gaussovského filtra. Vidno, že obyčajný Gaussovský filter absolútne neuvažuje hrany a detaily a jeho efekt je v celom obrázku rozmazávací.
Na druhú stranu na obrázku 2.12c môžeme badať redukciu šumu, pričom sú
hrany objektov takmer naporušené.
35
2. Predspracovanie obrazových dát
(a)
(b)
(c)
Obr. 2.12: Porovnanie obyčajného a bilaterálneho Gaussovského filtra. (a) - obrázok postihnutý Gaussovským šumom (var = 0.04), (b) - obrázok po aplikácii
Gaussovského filtra (15 × 15, σ = 10), (c) - obrázok po aplikácii bilaterálneho
filtra (9 × 9, σs = 5, σr = 0.45)
Bilaterálny filter dosahuje kvalitné výsledky v oblasti štýlovania a korekcie
fotografií, používa sa pri mapovaní tónov (tone mapping; kde je potrebné
zobraziť napríklad farby v rozsahu h0, 65535i do rozsahu h0, 255i), vytvorenie
tzv. cartoon efektu a mnoho ďalších. Jeho najväčšou nevýhodou je však jeho
výpočtový čas, pretože je potrebné prepočítať príspevky každého zo susedných
pixelov.
2.3
Segmentácia obrazu
Segmentácia obrazu je dôležitým prvkom v spracovaní obrazu. Keďže patrí
do druhého stupňa techník spracovania, jej vstupom je samotný obrázok a
výstupom by mali byť atribúty získané samotnou operáciou segmentácie. V
rámci segmentácie tieto atribúty vzniknú rozdelením obrazu na objekty alebo
oblasti nachádzajúce sa v obraze. Presnosť segmentácie (úroveň detailov) je
problémovo závislá a preto je segmentácia jednou z najťažších úloh v spracovaní obrazu. Väčšine segmentácií predchádzajú rôzne úpravy obrazu, ktoré
zosilnia objekty záujmu a naopak, zoslabia časti obrazu, ktoré nie sú potrebné
pri následnom riešení problému.
Základným problémom segmentácie je teda rozdeliť obrázok na oblasti,
ktoré spĺňajú požadované podmienky. Algoritmy vykonávajúce proces segmentácie sú všeobecne založené na dvoch základných myšlienkach ako sa vysporiadať s vlastnosťami hodnôt intenzít: nespojitosť a podobnosť. Algoritmy
prvej kategórie predpokladajú, že hranice objektov sú rozdielne medzi sebou
a hlavne, že sú rozdielne od pozadia. To umožňuje detekovať hranice na základe lokálnej diskontinuity, čo sa týka intenzity. Základným prístupom v tejto
kategórii je teda hranovo založená segmentácia. Algoritmy založené na rozdeľovaní obrazu na plochy a oblasti, ktoré sú podobné podľa preddefinovaných
vlastností spadajú do druhej skupiny, regionálne založenej segmentácie [4].
36
2.3. Segmentácia obrazu
2.3.1
Detekcia bodov, línií a hrán
V tejto podkapitole sa sústredíme na detekciu výrazných lokálnych zmien intenzity. Takéto zmeny predstavujú tri základné rysy v obrazových dátach,
izolované body, línie a hrany. Identifikácia práve týchto rysov napomáha v
identifikácii objektov a regiónov v obraze a teda k celkovej segmentácii. Hranové pixely sú pixely, v ktorých sa intenzita obrazovej funkcie náhle mení a
hrany sú teda pospájané hranové pixely. Detektory hrán sú lokálne spracovacie metódy navrhnuté na detekciu práve hranových pixelov. Línie môžu byť
následne definované ako hrany v ktorých je intenzita pozadia na oboch stranách väčšia alebo menšia ako intenzita pixelov na tejto línii. Izolované body
môžeme popísať ako línie s dĺžkou a šírkou rovnajúcou sa jednému pixelu [4].
Ako sme popísali v kapitole 2.2.1.2, na odhaľovanie detailov, medzi ktoré
izolované body určite patria, je výborným prostriedkom druhá derivácia a
operátor Laplacián. Na obrázku 2.7b môžeme vidieť tento operátor rozšírený
o diagonálne členy. Použitím tohto filtra dokážeme detekovať izolované body
tak, že po aplikácii Laplaciánu vyhľadáme vo výstupnom obraze body s najväčšou hodnotou intenzity a tie, ktoré prekročia nami uvedenú hranicu, môžeme prehlásiť za izolované body, pretože koeficienty filtra spôsobia, že práve
v izolovanom bode bude reakcia filtra vysoká, ale pre plochy s konštantnou
intenzitou, hodnoty koeficientov spôsobia nulovú odozvu, kvôli ich sume rovnej nule. Tento typ detekcie je značne závislý na tom, že izolovaný pixel musí
byť obklopený homogénnym pozadím.
V úvode tejto kapitoly sme izolované body popísali ako línie s dĺžkou a
šírkou s veľkosťou jedného pixelu. Z princípu teda vyplýva, že aj na detekciu
línií nám poslúži Laplaceovský operátor ∇2 . Pri detekcii línií ale prichádzame
k problému prechodu nulou, ktorý vytvára samotná druhá derivácia, a to má
za následok vytvorenie akejsi dvojitej línie. Riešením tohto problému môže byť
napríklad použitie absolútnej hodnoty Laplaciánu, ktorý však spôsobí, že línie
budú dvojnásobne hrubšie ako v skutočnosti, alebo že použijeme len kladné
hodnoty Laplaciánu, a tým odstránime aj tento efekt.
Operátor Laplacián je všeobecný operátor na vyhľadávanie línií vo všetkých smeroch, no niekedy je centrom záujmu práve vyhľadávanie línií v definovaných smeroch. Na to je možné použiť špeciálne filtre, ktorých tvar a hodnoty
koeficientov vychádzajú priamo z druhej derivácie funkcie obrazového signálu.
Z rovnice 2.8 pre vertikálny smer a pre f (y) pre horizontálny smer vieme odvodiť dvojrozmerné jadro filtra na detekciu línií práve v týchto smeroch. Takéto
filtre sú zobrazené na obrázkoch 2.13a a 2.13b, prípadne odvodené filtre na
detekciu línií pod uhlom ±45◦ na obrázkoch 2.13c a 2.13d.
37
2. Predspracovanie obrazových dát
−1
−1
−1
−1
2
−1
2
2
2
−1
2
−1
−1
−1
−1
−1
2
−1
(a)
(b)
2
−1
−1
−1
−1
2
−1
2
−1
−1
2
−1
−1
−1
2
2
−1
−1
(c)
(d)
Obr. 2.13: Filtrovacie masky pre detekciu línií v smere (a) - horizontálnom,
(b) - vertikálnom (c) - +45◦ , (d) - −45◦
Posledný prístup k detekcii rysov je detekcia hrán. Tento prístup sa pri
segmentácii používa najčastejšie, pretože objekty v obraze sú väčšinou súvislé
regióny a nie len línie a body. Pri detekcii hrán musíme brať do úvahy, že
existuje niekoľko typov hrán objektov. Pre jednoduchosť rozoberieme len dva
typy objektových hrán a to: ideálnu a sklonovú. Ideálnu hranu môžeme charakterizovať ako prechod medzi dvomi oblasťami rôznych intenzít šírky, ideálne
jeden pixel. Názorná ukážka takejto hrany je na obrázku 2.6 označená ako
„skok“. Druhý typ hrany je tiež zobrazený na tomto obrázku a je označený ako
„sklon“. U takýchto hrán je obtiažne použiť klasický Laplaceovský operátor,
pretože prechod sa rozprestiera pozdĺž malého počtu pixelov. V skutočnosti je
väčšina hrán v reálnych obrazových dátach práve takéhoto typu. Ideálne hrany
sú vytvorené väčšinou prostredníctvom počítača, ale takéto hrany nevyzerajú
reálne [4].
Na detekciu hrán sa využíva obdoba Laplaceovského operátora avšak s
využitím prvej derivácie. Tento operátor sa nazýva gradient a umožňuje určiť
intenzitu hrany a jej smer na pozícii (x, y) v obrázku f . Je definovaný ako:


∇f ≡ grad(f ) ≡ 
gx



=

gy

∂f
∂x
∂f
∂y






(2.23)
Vektor gradientu je veľmi dôležitý, pretože je od bodu (x, y) orientovaný
v smere najväčšej zmeny intenzity. Z poznatku tejto vlastnosti vyplýva, že
38
2.3. Segmentácia obrazu
v každom bode dokážeme rozhodnúť, či je daný bod na hrane. Výpočtom
gradientných vektorov vo všetkých možných pozíciách x a y získame tzv. gradientný obrázok. Podobne ako pri operátore Laplaciánu dokážeme aj gradient
aproximovať v diskrétnych hodnotách:
gx =
∂f (x, y)
= f (x + 1, y) − f (x, y)
∂x
(2.24)
gy =
∂f (x, y)
= f (x, y + 1) − f (x, y)
∂y
(2.25)
Podobne ako pri zaostrovacích filtroch dokážeme z týchto rovníc vytvoriť
jednoduché filtre v smere x a y. Tie sú zobrazené na obrázku 2.14.
−1
1
(a)
−1
1
(b)
Obr. 2.14: Jednorozmerné masky na výpočet gradientných zložiek v smere (a)
- horizontálnom, (b) - vertikálnom
Pri prechode do viacrozmerného priestoru, obrazu, musíme tiež samozrejme rozšíriť aj tieto masky na viacrozmerné, v našom prípade dvojrozmerné.
Najjednoduchším rozšírením sú masky zobrazené na obrázku 2.15a. Nevýhodou tohto gradientného filtra je to, že jeho rozmery sú 2 × 2 a z toho vyplýva,
že maska nie je symetricky posadená na centrálny pixel, v ktorom vlastne
gradient určujeme. Preto sa väčšinou využívajú operátory, ktoré umožňujú
túto symetriu zachovať. Najmenšie možné, ktoré túto podmienku spĺňajú sú
veľkosti 3 × 3. Na obrázkoch 2.15b, 2.15c a 2.15d môžeme vidieť takéto filtre.
Hlavným rozdielom medzi nimi je to, že koeficienty 1, 2, 1 v maske Sobelovského operátora (prípadne 3, 10, 3 v Scharrovského operátore) zabezpečujú
naviac oproti Prewittovskému aj rozmazávanie a teda malú redukciu šumu,
ktorý má na detekciu hrán obrovský vplyv.
39
2. Predspracovanie obrazových dát
−1
−2
−1
−1
0
1
−1
0
0
−1
0
0
0
−2
0
2
0
1
1
0
1
2
1
−1
0
1
3
0
−3
(a)
(b)
−1
−1
−1
−1
0
1
0
0
0
−1
0
1
0
0
0
10
0
−10
1
1
1
−1
0
1
3
10
3
3
0
−3
(c)
−3 −10 −3
(d)
Obr. 2.15: Ukážky filtrov používaných na detekciu hrán v obraze: (a) - Robertsov operátor, (b) - Sobelov operátor, (c) - Prewittov operátor, (d) - Scharrov
operátor
Na obrázku 2.16 sú ukážky gradientného obrázku vytvoreného Sobelovským operátorom a následne ukážky gradientných obrázkov spojených s thresholdingom pre vyššie spomenuté hranové operátory.
40
2.3. Segmentácia obrazu
(a)
(b)
(c)
(d)
(e)
(f)
Obr. 2.16: Ukážky použitia filtrov na detekciu hrán v obraze: (a) - pôvodný
obrázok, (b) - gradientný obrázok; obrázok po aplikácii (c) - Robertsovho, (d)
- Sobelovho, (e) - Prewittovho, (f) - Scharrovho operátoru
41
2. Predspracovanie obrazových dát
2.3.1.1
Houghova transformácia
V tejto podkapitole osobitne predstavíme robustnú metódu používanú na
extrakciu geometrických primitív z obrazu. Geometrickými primitívami rozumieme krivky alebo plochy, ktoré dokážeme popísať parametrickými rovnicami, napríklad priamky, kružnice, elipsy a podobne.
Práve parametrický popis je základom princípu použitého v tejto metóde.
Houghova tranformácia mení klasický xy-súradnicový systém na tzv. Houghov
parametrický priestor. Jeho vytvorenie vychádza zo všeobecnej parametrickej
rovnice priamky:
y = ax + b
(2.26)
a jej následnej úpravy na tvar:
cosθ
ρ
y= −
x+
sinθ
sinθ
=⇒ ρ = x cosθ + y sinθ
=⇒
(2.27)
Geometrická interpretácia tohto priestoru je ilustrovaná na obrázku 2.17.
Na obrázku 2.17a je zobrazená priamka prechádzajúca bodmi (xi , yi ) a (xj , yj ).
Týmto bodom odpovedajú na obrázku 2.17b sínusové krivky. Bod, ktorý vznikol ako ich priesečník, korešponduje s priamkou prechádzajúcou týmito bodmi
v xy-súradnicovom systéme. Vo všeobecnosti všetky body obsiahnuté na tejto
priamke majú rovnaký priesečník v ρθ priestore. Táto vlastnosť sa principiálne
využíva na detekciu línií pomocou tejto metódy. Ďalšou dôležitou súčasťou
tejto metódy sú tzv. akumulátorové bunky, ktore rozdeľujú ρθ parametrickú rovinu na časti zobrazené
√ na obrázku
√ 2.17c. Rozsahy (ρmin , ρmax ) a (θmin , θmax )
dosahujú hodnoty: − 2D ≤ ρ ≤ 2D a −90◦ ≤ θ ≤ 90◦ , kde D je dĺžka diagonály obrázku. Bunka so súradnicami (i, j) má teda hodnotou akumulátora
A(i, j). V prvom kroku hodnoty všetkých akumulátorov pre každú hodnotu i
a j nastavíme na nulu. Následne pre každý bod z popredia obrázku (xk , yk ) z
xy-roviny vypočítame prislúchajúce hodnoty ρ pre všetky dovolené hodnoty
θ podľa rovnice ρ = xk cosθ + yk sinθ. Výsledné hodnoty ρ sú zaokrúhlené k
najbližšej povolenej hodnote niektorej z buniek. Ak pre hodnotu θp dostaneme
výslednú hodnotu ρp , potom A(p, q) = A(p, q) + 1. Po ukončení výpočtu pre
všetky body z popredia nám hodnota P z A(i, j) určuje, že práve P bodov z
xy-roviny leží na priamke x cosθj + y sinθj = ρi [4, 9].
Popísaným spôsobom možno v obraze detekovať aj iné primitívy ako priamky.
Rozdiel spočíva v parametrickom vyjadrení daného tvaru (kružnica, elipsa) a
v počte voľných parametrov (napríklad prítomnosť troch parametrov vedie k
trojrozmernému parametrickému priestoru).
Najväčšou aplikačnou oblasťou použitia tejto metódy je detekcia najvýraznejších a najdlhších hrán v obraze. Tie je možné detekovať v parametrickom
42
2.3. Segmentácia obrazu
θ’
y
θ
ρ
θmin
θ
0
ρmin
θmax
θ
xj cosθ + yj sinθ = ρ
(xj , yj )
0
(xi , yi )
ρ’
xi cosθ + yi sinθ = ρ
ρ
x
(a)
ρmax
ρ
(b)
(c)
Obr. 2.17: Obrázok ilustrujúci vytvorenie Houghovho ρθ-parametrického priestoru. (a) - ρθ parametrizácia priamky v xy-súradnicovom systéme, (b) - sínusové krivky v ρθ-rovine; bod (ρ’, θ’) korešponduje s priamkou prechádzajúcou
bodmi (xi , yi ) a (xj , yj ) v xy-súradnicovom systéme, (c) - rozdelenie ρθ-roviny
na akumulátorové bunky (upravené podľa [4].
priestore ako najvyššie akumulátorové hodnoty. Na obrázku 2.18 je znázornené
použitie Houghovej transformácie práve na tento účel. Na obrázku 2.18c je znázornený ρθ-parametrický priestor a v ňom vyznačené tri najvyššie hodnoty,
ktoré korešpondujú s tromi najvýraznejšími líniami vyznačenými v obrázku
2.18d.
Oblasť aplikácie tejto metódy je veľmi rozšírená v počítačovom videní a
robotike, kvôli automatickému navádzaniu, sledovaniu určitej cesty a podobne.
Ďalšou prednosťou tejto metódy je stabilita pri práci so šumom.
43
2. Predspracovanie obrazových dát
(a)
(b)
(c)
(d)
Obr. 2.18: Aplikácia Houghovej transformácie na reálny obrázok: (a) - pôvodný
obrázok, (b) - detekcia hrán Cannyho algoritmom, (c) - Houghov parametrický
priestor, (d) - vyznačenie najvýraznejších hrán v pôvodnom obrázku
44
2.3. Segmentácia obrazu
2.3.2
Thresholding
Thresholding má jednu s najvýznamnejších pozícií v aplikáciách obrazovej
segmentácie. Jeho základnou koncepciou je rozdeľovanie obrazu priamo na
oblasti pixelov na základe ich intenzít.
Majme obrázok f (x, y) (obr. 2.18a) a jeho histogram intenzít na obrázku
2.19a. Z pôvodného obrázku jasne vidno, že na tmavšom pozadí sa nachádzajú
svetlé objekty, ktoré v histograme odpovedajú pravej časti histogramu. Veľká
skupina uprostred predstavuje tmavšie pozadie tohto obrázku. Jedným z riešení ako tieto dva rozličné oblasti separovať je zvoliť threshold, hodnotu, ktorá
tieto skupiny oddelí. Všetky body (x, y) budú patriť k pozadiu, ak f (x, y) ≤ T ,
a k poprediu (objektu), ak f (x, y) > T . Vo všeobecnosti teda segmentovaný
obrázok g(x, y) bude
g(x, y) =

1
ak f (x, y) > T
0
ak f (x, y) ≤ T
(2.28)
Ak je T konštantné pre celý obrázok, proces thresholdingu má prívlastok
globálny. V inom prípade je možno hodnotu T meniť v závislosti na pozícii v
obraze a túto hodnotu počítať z určitého okolia bodu (x, y). Takýto prípad
označujeme ako lokálny alebo adaptívny thresholding [4].
Na obrázku 2.19b vidieť ukážku obrázku po aplikácii globálneho tresholdingu.
(a)
(b)
Obr. 2.19: Ukážka použitia thresholdingu. (a) - histogram obrázku 2.18a, (b)
- obrázok po aplikácii thresholdingu
Aplikácii thresholdingu predchádza mnoho obrazových úprav, pretože jeho
úspešnosť silne závisí od viacerých faktorov ako je prítomnosť šumu, pomer
relatívnych veľkostí pozadia a popredia, rovnomernosť osvetlenia a podobne.
45
2. Predspracovanie obrazových dát
Vo väčšine prípadov sa používa práve jediný globálny threshold. Jeho výpočet musí byť dostatočne presný a spoľahlivý. Nasledujúci iteratívny algoritmus
možno použiť na výpočet hodnoty thresholdu [4]:
1. Odhadom zvolíme prvotný globálny threshold T .
2. Na obrázok aplikujeme rovnicu 2.28. Výsledkom budú dve skupiny pixelov, G1 a G2 .
3. Vypočítame priemernú hodnotu intenzít m1 , m2 pre skupiny G1 a G2 .
4. Vypočítame novú hodnotu thresholdu:
1
T = (m1 + m2 )
2
(2.29)
5. Opakujeme kroky 2-4, kým rozdiel hodnôt T nie je menší ako preddefinovaný parameter ∆T .
Tento algoritmus je dostatočne spoľahlivý vo výpočte hodnoty T , ale nie
je veľmi efektívny, pretože v každom kroku musíme znovu počítať priemer. Na
výpočet hodnoty thresholdu sa využívajú rôzne metódy, z ktorých je najznámejšia Otsuova metóda.
46
KAPITOLA
Rozpoznávanie vzorov pattern matching
V dnešnej dobe je prirodzené, že sa snažíme navrhovať a vytvárať prostriedky
na rozpoznávanie vzorov. Cez automatické rozpoznávanie reči, identifikáciu
odtlačkov prstov, rozpoznávanie znakov, identifikáciu DNA reťazcov a mnoho
ďalších je samozrejmé, že spoľahlivý a presný nástroj na rozpoznávanie by bol
okamžite žiadaný a užitočný [2].
V tejto kapitole komplexne predstavíme systémy na rozpoznávanie vzorov
so zameraním priamo na obrazové dáta.
Obrazové dáta sú veľmi silným informačným médiom a komunikačným
nástrojom kvôli možnosti reprezentovať komplexné objekty a procesy v kompaktnej a efektívnej forme. Všeobecný digitálny obrázok obsahuje enormné
množstvo informácií, dokonca toľko, že jeden obrázok v sebe zahŕňa toľko informácií ako niekoľko sto stránok textu. Kvôli tejto skutočnosti je nevyhnutne
potrebné zamerať sa na automatické a robustné metódy analýzy obrazových
dát [3].
Analýza a interpretácia obrazu získaného reálnymi obrazovými systémami
je hlavným problémom vo väčšine aplikačných oblastí ako napríklad počítačové
videnie, bezdotykové snímanie, astronómia, medicína a mnoho ďalších.
Analýzou obrazu zvyčajne rozumieme proces zložený z troch hlavných fáz.
Prvou fázou je predspracovanie obrazu a segmentácia, ktoré boli popísané v
kapitole 2. V druhej fáze je potrebné extrahované objekty matematicky popísať, aby ich bolo možné rozpoznať na základe nejakých vlastností. Túto
fázu nazývame aj feature extraction, čiže doslovne extrakcia príznakov, vlastností. Poslednou treťou fázou je tzv. klasifikačná fáza, v ktorej odhaľujeme
príslušnosť jednotlivých vzorov do určitých tried, prípadne podobnosti medzi
jednotlivými vzormi. Práve tieto dve fázy, čiže extrakciu príznakov a klasifi47
3
3. Rozpoznávanie vzorov - pattern matching
káciu, spracujeme v tejto kapitole a popíšeme vybrané metódy na deskripciu,
reprezentáciu a klasifikáciu týchto objektov.
3.1
Reprezentácia a deskripcia vzorov
Deskripcia vzorov je veľmi významným faktorom pri klasifikácii objektov.
Práve na tejto deskripcii závisí následná úspešnosť klasifikátora a ideálnym
prípadom môžeme nazvať stav, ak extraktor príznakov objekty daných tried
popíše tak, že pre klasifikátor by bola klasifikácia len triviálnym problémom
spracovať tieto príznaky. To je samozrejme idealizovaný prípad a v skutočnosti
väčšinou takéto príznaky neexistujú. Náročnosť extrakcie vhodných príznakov
je teda jednou z najťažších úloh pri klasifikácii vzorov, pretože komplexicita
tejto úlohy sa zvyšuje s počtom tried a počtom záznamov. Úlohou extraktora
príznakov je charakterizovať objekt tak, aby bolo možné tento objekt rozpoznať na základe meraní, ktorého hodnoty sú veľmi podobné pre objekty z jednej
kategórie a naopak, odlišné pre objekty z rozdielnych kategórií.
Po aplikácii segmentácie a extrakcii požadovaných objektov z dát, je nutné
tieto objekty popísať vo forme vhodnej na ďalšie spracovanie.
V zásade môžeme extrahované objekty alebo oblasti reprezentovať na základe jeho externých (hranice objektu) alebo interných charakteristík (pixely,
z ktorých objekt pozostáva). Voľba externej reprezentácie súvisí najmä so zameraním na tvarové charakteristiky. Interná reprezentácia sa používa väčšinou
na popis vlastností ako je farba alebo textúra. Ďalším krokom je zvolenú reprezentáciu popísať príznakmi, ako napríklad dĺžka hranice, orientácia, počet
zakrivení a podobne.
V ďalších podkapitolách popíšeme niektoré prístupy extrakcie príznakov
priamo pre rozpoznávanie v obrazových dátach. Pre jednoduchosť sme uviedli
len typy príznakov, s ktorými sme následne pracovali na experimentoch v
ďalšej časti tejto práce.
3.1.1
Jednoduché priestorové deskriptory
Na základe článkov [12, 13] sme vytvorili dva typy príznakov popisujúcich
segmentovaný objekt. Pre názornú ukážku je demonštrácia extrakcie týchto
príznakov zobrazená na obrázku 3.1.
48
3.1. Reprezentácia a deskripcia vzorov
2
00011
(a)
(b)
Obr. 3.1: Ukážka princípu extrakcie príznakov. (a) - príznakový vektor je
vytvorený tak, že jeho veľkosť zodpovedá veľkosti mriežky; hodnoty jednotlivých príznakov určujú, či sa v danom lokálnom okne nachádza časť objektu
(1) alebo nie (0) - v tomto prípade je výsledný vektor veľkosti 35 × 1, (b) veľkosť príznakového vektora v tomto prípade zodpovedá počtu línií vedených
zo stredu objektu; jednotlivé hodnoty príznakov určujú koľkokrát línia pod
daným uhlom pretne nejakú časť objektu (inšpirované projekčnými líniami z
[13]).
Oba tieto typy príznakov, sú pomerne jednoduché a predpokladáme, že
budú dosť citlivé na zmenu rotácie a iné deformácie obrazu, ako aj na šum a
podobne.
3.1.2
Momenty
Momenty sú skalárne veličiny používané na charakteristiku funkcií a na zachytenie ich signifikantných vlastností. Z matematického pohľadu sú momenty
projekcie funkcie na polynomiálny základ [3]. Najdôležitejším polynomiálnym
základom, ktorý následne vedie ku geometrickým momentom, je pkj (x, y) =
xk y j a z neho vyplýva definícia momentu:
Z∞ Z∞
mpq =
xp y q f (x, y)dxdy
(3.1)
−∞ −∞
Predchádzajúci vzťah platí všeobecne pre spojité funkcie, ale ako už bolo
viackrát v tejto práci spomenuté, obrázok je funkciou diskrétnych hodnôt,
preto je potrebné vzťah 3.1 upraviť pre dvojrozmerný obrázok f (x, y) veľkosti
M × N:
mpq =
M
−1 N
−1
X
X
xp y q f (x, y)
(3.2)
x=0 y=0
49
3. Rozpoznávanie vzorov - pattern matching
Suma parametrov p, q ∈ N určuje rád daného momentu. Momenty môžu
byť nižšieho a vyššieho rádu a každý z nich vyjadruje určitú vlastnosť funkcie.
So zvyšujúcim sa rádom momentu sa zvyšuje aj jeho komplexicita a zložitosť
vlastnosti, ktorú vyjadruje. Moment rádu 0, m00 (p = 0, q = 0) vyjadruje
m01
10
akúsi „hustotu“ alebo „kapacitu“ daného obrázku, m
m00 a m00 definujú tzv.
centroid obrazu. Momenty druhého stupňa, m20 a m02 vyjadrujú rozloženie
hustoty v obrázku s ohľadom na osi x a y.
3.1.2.1
Momentové invarianty voči posunu, rotácii a zmene
mierky
Tradičnou úlohou extraktora príznakov je charakterizovať objekt tak, aby bolo
v ďalšej fáze možné tento objekt presne rozpoznať. Príznaky, ktoré extraktor
získa, musia byť dostatočne diskriminatívne, aby sa od objektov iných tried
dostatočne odlišoval a zároveň aby príznaky v rámci jednej triedy boli čo najpodobnejšie. Problémom však je, že reálne dáta sú často zašumené a sú postihnuté rôznymi deformáciami. Základnými deformáciami, ktoré môžu v obraze
nastať, sú translácia, rotácia a škálovanie (zmena mierky). Obraz postihnutý
týmito deformáciami, môže byť všeobecne popísaný nasledovne:
x
¯ = sR.x + t,
(3.3)
kde x je obrázok bez akejkoľvek deformácie, s je kladný škálovací parameter,
t je translačný vektor a R je rotačná matica.
Existujú tri základné prístupy na riešenie problému s deformáciami: hrubá
sila, normalizácia obrazu a invariantné príznaky. Hrubá sila je všeobecne
známa metóda riešenia problémov. Jej výpočtová zložitosť je však pre väčšie inštancie problémov neúnosná. V tomto prípade eliminácie deformácií by
to znamenalo, že trénovacia množina klasifikátora by musela obsahovať všetky
možné kombinácie posunov, rotácií a zmien mierky. Normalizačný prístup je
založený na úprave obrazu na jeho pôvodnú formu, čiže spätná úprava rotácie, posunu, vyhladenia obrazu, . . . Tretím prístupom je extrakcia príznakov,
ktoré sú priamo odolné voči týmto transformáciám. Takéto príznaky nazývame invarianty alebo momentové invarianty [3]. Schopnosť takto reagovať na
zmeny je zakotvená v tom, že invarianty popisujú vlastnosti objektu ako sú
tvar, farba, textúra a podobne. Aby sme boli schopní dosiahnuť vysokú diskriminatívnu schopnosť, vo väčšine prípadov musíme použiť viac invariantov. Na
obrázku 3.2 môžeme vidieť ukážku separácie dvoch tried na základne dvoch
invariantných príznakov F1 a F2 .
50
3.1. Reprezentácia a deskripcia vzorov
F2
A
A
A AAA
B
B
B
BB
B
B
A
F1
Obr. 3.2: Ukážka separácie objektov dvoch tried na základe príznakov F1 a F2 .
Triedy takmer ideálne vytvárajú dva zhluky (príznaky sú invariantné). Zhluky
sú dobre separovateľné (príznaky sú dostatočne diskriminatívne) [3]
.
Na základe rovnice 3.2 môžeme následne odvodiť tzv. centrálne momenty
rádu (p + q):
µpq =
−1
M
−1 N
X
X
(x − x
¯)p (y − y¯)q f (x, y),
(3.4)
x=0 y=0
kde p, q ∈ N a
x
¯=
m10
m01
a y¯ =
m00
m00
(3.5)
Následne môžeme ešte centrálny moment µpq normalizovať na
µpq
,
µγ00
(3.6)
p+q
+1
2
(3.7)
ηpq =
kde
γ=
pre p + q = 2, 3, . . .
Následne sme na základe týchto rovníc schopní odvodiť sedem invariantných normalizovaných momentov.
51
3. Rozpoznávanie vzorov - pattern matching
φ1 =η20 + η02
(3.8)
2
φ2 =(η20 − η02 )2 + 4η11
(3.9)
φ3 =(η30 − 3η12 )2 + (3η21 − η03 )2
(3.10)
φ4 =(η30 + η12 )2 + (η21 + η03 )2
(3.11)
φ5 =(η30 − 3η12 )(η30 + η12 )[(η30 + η12 )2
− 3(η21 + η03 )2 ] + (3η21 − η03 )(η21 + η03 )
[3(η30 + η12 )2 − (η21 + η03 )2 ]
(3.12)
φ6 =(η20 − η02 )[(η30 + η12 )2 − (η21 + η03 )2 ]
+ 4η11 (η30 + η12 )(η21 + η03 )
(3.13)
φ7 =(3η21 − η03 )(η30 + η12 )[(η30 + η12 )2
− 3(η21 + η03 )2 ] + (3η12 − η30 )(η21 + η03 )
[3(η30 + η12 )2 − (η21 + η03 )2 ]
(3.14)
Táto množina momentov je invariantná voči posunu, zmene mierky, zrkadleniu a rotácii.
Niekedy sa používajú ešte ďalšie p
veličiny derivované
z momentov nižších
p
rádov, napríklad polomer otočenia q
( m20 /m00q
, m02 /m00 ), skosenie (skewness) a vydutosť (kurtosis) (m30 / m320 , m03 / m302 ) [3].
3.1.3
Zernikeho momenty
Zernikeho momenty (ZM) sú jednými z najznámejších momentových invariantov. Ich sila spočíva najmä v invariancii voči rotácii, ktorá bazíruje na práci s
polárnymi súradnicami (rotácia je transformovaná na posun). ZM sa radia do
skupiny momentov, ktorých bázy sú ortogonálne, čo má v konečnom dôsledku
priaznivé numerické vlastnosti. Motiváciou použitia nie len ZM, ale ortogonálnych momentov všeobecne, je hlavne rýchla implementácia (momenty môžme
vyhodnotiť na základe rekurentných vzťahov) a vysoká robustnosť a odolnosť voči šumu. Významnou aplikáciou momentov je aj rekonštrukcia obrazu
z dôvodu minimálnej informačnej redundancie preto, že minimalizujú MSE
(mean-square error).
Všeobecne môžeme ortogonálne momenty (oblasť ortogonality je jednotková kružnica) definovať ako:
Z2πZ1
vpq = npq
0 0
52
Rpq (r)e−iqϕ f (r, ϕ)r dr ϕ,
(3.15)
3.1. Reprezentácia a deskripcia vzorov
kde p = 0, 1, 2, . . . , q a q = −p, . . . , p, npq je normalizujúci faktor, r a ϕ sú
polárne súradnice, Rpq je radiálna a eiqϕ uhlová časť patričného polynómu.
Oblasť ortogonality je jednotková kružnica Ω = (x, y)|x2 + y 2 ≤ 1 . Na výpočet momentu musí byť obrázok f naškálovaný tak, aby bol plne obsiahnutý
v Ω [3, 10].
Z celej skupiny kruhovo ortogonálnych momentov môžeme ZM charakterizovať ako najsilnejšie. Poskytujú výpočet momentov vysokých stupňov, čo
vedie k možnosti disponovať veľkým množstvom príznakov. ZM sú príznaky
extrahované projekciou vstupného obrazu či funkcie na množinu Zernikeho
polynómov. Magnitúdy týchto momentov sú použité na rozpoznávanie vzorov
kvôli ich invariancii voči rotácii. Zernikeho radiálne polynómy sú definované
ako
Vn` (r, ϕ) = Rn` (r)ei`ϕ ,
(3.16)
(n − s)!
rn−2s
s![(n + |`|)/2 − s]![(n − |`|)/2 − s]!
(3.17)
kde radiálna časť
(n−|`|)/2
Rn` (r) =
X
(−1)s
s=0
Z predchádzajúcich rovníc môžeme teda odvodiť ZM n-tého stupňa s opakovaním ` ako
An`
n+1
=
π
Z2πZ1
∗
Vn`
(r, ϕ)f (r, ϕ)r dr dϕ,
(3.18)
0 0
pre n = 0, 1, 2, . . . a ` = −n, −n + 2, . . . , n, pričom rozdiel n − |`| je vždy
párny (tzv. pseudo-Zernikeho momenty od tejto podmienky upúšťajú) a ∗
značí komplexné združenie.
Ako sme už spomínali, Zernikeho bazálne funkcie sú definované len v priestore jednotkovej kružnice, takže pixely mimo tejto kružnice nebudú vo výpočtoch obsiahnuté. Diskrétna forma ZM obrázku veľkosti M × N je potom
An` =
−1 N
−1
X
n + 1 MX
V ∗ (r, ϕ)f (r, ϕ),
π x=0 y=0 n`
(3.19)
kde n = 0, 1, 2, . . . a ` = −n, −n + 2, . . . , n. Keďže v tomto prípade ide už o
diskrétny obrázok, treba kartézske súradnice x, y previesť na polárne súradnice
r, ϕ. Jedným z najbežnejších spôsobov je použitie centra rotácie, čiže centroid
(xc , yc ) obrázku:
p
r=
(x − xc )2 + (y − yc )2
,
rmax
(3.20)
53
3. Rozpoznávanie vzorov - pattern matching
kde rmax =
q
√
m00
M
2
N
+
N
M
a
y − yc
ϕ = arctan
x − xc
(3.21)
Na základe štúdií ZM bolo zistené, že ZM vyššieho rádu sú viac náchylné
na šum a numerickú nestabilitu. Ako sme už uviedli v predchádzajúcom texte,
existuje ďalšia variácia ZM, tzv. pseudo-Zernikeho momenty. Výhodou tejto
variácie je vyššia robustnosť voči aditívnemu šumu v obraze [10].
ZM sú vo všeobecnosti používané najmä v počítačovom videní, pri rozpoznávaní vzorov, identifikácii tvárí a podobne.
3.2
Klasifikácia vzorov
Úlohou klasifikátora je použiť vektor príznakov vytvorený extraktorom príznakov na priradenie objektu k určitej triede. Pretože je takmer nemožné vytvoriť
klasifikátor schopný dokonalej separácie, úlohu klasifikátora predefinujeme na
priradenie pravdepodobnosti príslušnosti pre každú z možných tried pre daný
objekt. Rozmanitosť reprezentácie príznakov vedie podobne k rozmanitosti
designu klasifikátorov. Stupeň obtiažnosti klasifikačného problému závisí od
premenlivosti hodnôt príznakov pre objekty v jednej kategórii, relatívne k rozdielu hodnôt pre objekty v odlišných triedach. Voľba typu príznakov je jedným
z kritických krokov a je problémovo závislá. Objekty teda môžeme popísať rôznymi príznakmi a tak isto je možné vytvárať rôzne modely na ich klasifikáciu.
Voľba klasifikačnej metódy je problémovo závislá a každý typ príznakov implikuje použitie iného klasifikátora. Klasifikačné modely majú však niekoľko
vlastností spoločných. Väčšina klasifikátorov pracuje v dvoch nadväzujúcich
fázach, v trénovacej a evaluačnej fáze. V trénovacej fáze sú klasifikačnému
modelu odovzdané trénovacie dáta (príslušnosť ku kategóriám je známa), na
ktorých je schopný adaptovať si svoje voľné parametre tak, aby chyba medzi
vstupným a výstupným vektorom kategórií týchto dát bola čo najmenšia. V
následnej evaluačnej fáze sú klasifikátoru odovzdané neznáme dáta, obsahujúce rovnaké atribúty ako pri testovacej fáze s rozdielom toho, že nepoznáme
príslušnosť týchto objektov k možným kategóriám. Klasifikátor dáta spracuje
podľa nastavených vnútorných parametrov a následne ohodnotí každý objekt
najpravdepodobnejšou triedou. Pri klasifikácii sa stretávame s troma základnými typmi trénovania:
Supervised learning - pri tomto type učenia disponujeme dátami, v ktorých
každý záznam obsahuje pár, pozostávajúci zo vstupného vektora (popis
objektu) a požadovanej výstupnej hodnoty (príslušnosť k triede). Výstupom je teda klasifikátor alebo regresná funkcia, ktorá dokáže predikovať
správnu výstupnú hodnotu pre akýkoľvek validný vstupný objekt.
54
3.2. Klasifikácia vzorov
Unsupervised learning - na rozdiel od predchádzajúceho typu u nesupervizovaného učenia nepoznáme požadovaný výstupný signál. Pri tomto
type učenia sa klasifikátor snaží odhaliť skrytú štruktúru v neoznačených dátach, formovať akési zhluky na základe prirodzenej podobnosti
objektov. Jednou z najvýznamnejších metód patracich do tejto skupiny
je clustering (zhlukovanie) alebo SOM (self-organizing map).
Reinforcement learning - najtypickejšou cestou trénovania klasifikátora je
prevziať vstupný vektor, pokusne vypočítať kategóriu a následne použiť
známu hodnotu kategórie na vylepšenie klasfikátora. V reinforcement
learning-u nie je predložená známa kategória, klasifikátor obdrží spätnú
väzbu obsahujúcu správu, že zvolená kategória je buď správna alebo
naopak. Klasifikátor je následne „odmenený“ za správnu klasifkáciu a
„penalizovaný“ za klasifikáciu nesprávnu [2].
3.2.1
Metriky a klasifikátor najbližšieho suseda
Algoritmus najbližšieho suseda je metóda klasifikovania objektov založená na
vzdialenosti k najbližšiemu prvku z trénovacích dát. Tento klasifikačný model
je jeden z najjednoduchších z dôvodu absencie trénovacej fázy. Na jeho funkciu
sú postačujúce uložené trénovacie dáta. Pri klasifikačnej fáze a teda hľadaní
najbližšieho prvku z množiny trénovacích dát sa na výpočet podobnosti vzorov
(vzdialenosti) používajú rôzne metriky, na ktorých následne závisí klasifikačná
úspešnosť tohto modelu.
Všetky metriky musia spĺňať štyri podmienky. Pre všetky vektory a, b a
c tieto podmienky sú:
1. nezápornosť d(a, b) ≥ 0,
2. reflexivita d(a, b) = 0 ⇔ a = b,
3. symetria d(a, b) = d(b, a),
4. trojuholníková nerovnosť d(a, b) + d(b, c) ≥ d(a, c).
Najpoužívanejšími metrikami spojenými s klasifikátorom najbližšieho suseda sú:
Euklidovská vzdialenosť , ktorá je pre body P = (p1 , p2 , . . . , pn ) a Q =
(q1 , q2 , . . . , qn ) v n-rozmernom priestore definovaná ako:
q
dE (P, Q) = (p1 − q1 )2 + (p2 − q2 )2 + . . . + (pn − qn )2
v
u n
uX
=t (pi − qi )2
(3.22)
i=1
55
3. Rozpoznávanie vzorov - pattern matching
Minkowského metrika Lk normy v n-rozmernom priestore:
v
u n
uX
k
Lk (P, Q) = t
|pi − qi |k ,
(3.23)
i=1
kde k ≥ 1. Euklidovská vzdialenosť je vlastne Minkowského metrika L2
normy. Podobne aj ďalšia metrika je derivovaná z Minkowského metriky
[2].
Manhattanská vzdialenosť je pre body P = (p1 , p2 , . . . , pn ) a Q = (q1 , q2 , . . . , qn )
v n-rozmernom priestore definovaná ako:
dM (P, Q) = |p1 − q1 | + |p2 − q2 | + . . . + |pn − qn |
(3.24)
V úvode sme spomenuli, že u tohto klasifikačného modelu chýba trénovacia fáza. Väčšinou však uložené dáta a jednotlivé atribúty majú rozdielne
rozsahy hodnôt (napríklad F1 ∈ h0, 10i a F2 ∈ h100, 1000i) a s týmto faktom
vzniká problém toho, že atribút F2 je 100x významnejší ako atribút F1 , čo
pri použití spomenutých metrík bude mať závažny následok a to, že atribút
F1 bude mať veľmi malú váhu pri rozhodovaní. Takéto dáta je potrebné pred
klasifikáciou upraviť normalizáciou, aby všetky atribúty spadali do rovnakého
rozsahu hodnôt.
V praxi sa často používa aj rozšírenie klasického klasifiátora najbližšieho
suseda, ktorý uvažuje len jedného (najbližšieho) suseda. Toto rozšírenie zahŕňa
výpočet najpravdepodobnejšej triedy z príslušnosti k najbližších susedov. Výsledná trieda daného vzoru je určená majoritou z tohto počtu. Všeobecným
problémom je voľba parametra k. Väčšinou je hodnota k nepárnym číslom z
dôvodu výpočtu majority.
Tento model je pomerne populárny, pretože jeho implementácia je značne
jednoduchá, ale na druhú stranu si prístup tohto modelu vyžaduje vyššie nároky na čas, kvôli tomu, že pri klasifikácii každého nového vzoru musí prehľadať celú množinu trénovacích dát. Klasifikátor najbližieho suseda sa používa
najmä v rozpoznávaní vzorov, štatistickej klasifikácii, internetovom nakupovaní a doporučovaní, detekcia plagiátorských diel a podobne.
3.2.2
Bayesovská teória a Bayesovský klasifikátor
Bayesovská rozhodovacia teória je významným štatistickým prístupom k problému klasifikácie vzorov. Tento prístup je založený na porovnávaní medzi
rôznymi klasifikačnými rozhodnutiami na základe pravdepodobnosti. Predpokladá, že rozhodovací problém je formovaný na základe pravdepodobnostných
podmienok a že všetky relevantné hodnoty pravdepodobnosi sú známe [2].
Ak by sme klasifikačný problém zredukovali na problém dvoch tried, tak
podľa rozhodovacej teórie je každý prvok v jednej alebo v druhej z možných
56
3.2. Klasifikácia vzorov
tried. Tieto triedy označme ω1 a ω2 . Keďže nevieme vopred predpovedať, do
akej triedy bude daný prvok patriť, popíšeme tieto hodnoty pravdepodobnostne. Ak triedy ω1 a ω2 obsahujú rovnaký počet prvkov, môžeme vo všeobecnosti tvrdiť, že nasledujúci prvok bude s rovnakou pravdepodobnosťou patriť
ako do triedy ω1 , tak aj do triedy ω2 . Ak neexistuje žiadna ďalšia trieda, do
ktorej by objekt mohol patriť, potom pravdepodobnosť P (ω1 ) + P (ω1 ) = 1.
Ak sme teda nútení rozhodnúť sa, na základe dostupných informácií je logické použiť rozhodovacie pravidlo tvaru: objekt priradíme do triedy ω1 ak
P (ω1 ) > P (ω2 ), inak do triedy ω2 . Úspešnosť tohto pravidla silne závisí na
pravdepodobnostiach P (ω1 ) a P (ω2 ). Vo väčšine prípadov klasifikácie však
disponujeme ďaleko väčším množstvom informácií (príznakov), na základe ktorých môžeme uplatniť toto pravidlo. S väčším množstvom informácií prichádza
samozrejme aj väčšia variabilita príznakových vektorov, keďže obsahujú vyšší
počet charakteristík. Nech teda x značí spojitú náhodnú veličinu, ktorej rozloženie vyjadríme ako p(x|ω). Toto označuje podmienenú hustotu pravdepodobnosti tejto náhodnej veličiny. Potom rozdiel medzi p(x|ω1 ) a p(x|ω2 ) popisuje
rozdiel vo vlastnosti charakterizovanej veličinou x. Poznamenajme, že hustota
pravdepodobnosti získania objektu, ktorý patrí do kategórie ωj a jeho príznakový vektor je x, môžme zapísať ako p(ωj , x) = P (ωj |x)p(x) = p(x|ωj )P (ωj )
[2]. Preusporiadaním tejto rovnice získame tzv. Bayesova teoréma:
P (ωj |x) =
p(x|ωj )P (ωj )
,
p(x)
(3.25)
p(x|ωj )P (ωj )
(3.26)
kde v prípade c kategórií
p(x) =
c
X
j=1
Bayesova teoréma popisuje, že sledovaním hodnoty x môžeme zmeniť apriórne pravdepodobnosti P (ωj ) na podmienené pravdepodobnosti P (ωj |x).
Využitím tejto formuly dokážeme navrhnúť jednoduchý, ale používaný klasifikátor využívajúci práve podmienené pravdepodobnosti.
3.2.2.1
Naive-Bayes klasifikátor
Naive-Bayes (NB) je klasifikátor, o ktorý je v posledných rokoch veľký záujem
prameniaci z prekvapujúcej úspešnosti pri klasifikácii s použitím príznakov,
nezávislých premenných [5].
Zvážme teda priradenie objektu x = (x1 , . . . , xc ) k jednej z c kategórií.
Kvôli garancii minimálnej klasifikačnej chyby vyberieme kategóriu s maximálnou podmienenou pravdepodobnosťou [5]. Podmienenú pravdepodobnosť
každej z týchto kategórií môžeme vypočítať pomocou Bayesovej formuly
p(x|ωj )P (ωj )
P (ωj , x) = Pc
,
i=1 p(x|ωi )P (ωi )
(3.27)
57
3. Rozpoznávanie vzorov - pattern matching
pre j = 1, . . . , c a kde P (ωi ) je apriórna pravdepodobnosť triedy ωi a p(x|ωi )
je hustota pravdepodobnosti tejto triedy. Naive časť NB hovorí o predpoklade
nezávislosti príznakov. V tomto prípade je združená hustota pravdepodobnosti
určená ako produkt čiastočných hustôt p(xi |ωj ):
p(x|ωj ) =
n
Y
p(xi |ωj ),
(3.28)
i=1
pre j = 1, . . . , c. NB substituuje 3.28 do rovnice 3.27 a preto je optimálny pre
podmienenú nezávislosť tried.
3.2.3
Neurónové siete
Neurónové siete (NN) známe aj pod názvom paralelné distribuované spracovanie alebo neurónové počítanie je výpočtový model, ktorý smeruje k spôsobu
počítania a spracovania informácií podobne ako v ľudskom mozgu. Jednou z
definícií môže byť aj: Predmetom štúdia neurónového počítania sú siete adaptívnych uzlov, ktoré skrz učiaci proces na základe ukážkových vzorov dokážu
získať a zachovať experimentálnu znalosť a sprístupniť ju k využitiu [Aleksander, Morton]. NN je procesorom informácií skladajúca sa z jednoduchých
procesných jednotiek spojených medzi sebou. Každá táto elementárna jednotka je jednoduchým modelom mozgového neurónu. Tento výpočtový model
sa v najväčšej miere snaží napodobniť schopnosť mozgu pracovať s neúplnou
informáciou a byť dostatočne robustným modelom na počítanie reálnych klasifikačných problémov [1].
Keďže sa umelé NN snažia napodobniť (prevažne) ľudský mozog, je zrejmé,
že elementárnych jednotiek bude veľké množstvo a že paralelizovaná implementácia NN má svoje opodstatnenie. Vo všeobecnosti sú všetky NN zložené
z umelých neurónov, ktoré sa delia na vstupné, výstupné a skryté, a spojení
medzi nimi. Každý neurón má určité vstupy a výstup. Odozvu neurónu môžme
popísať ako:
d(x) =
n
X
wi x i ,
(3.29)
i=1
kde koeficienty wi , i = 1, 2, . . . , n nazývame váhy korešpondujúce so zložkami vektora x, x1 , x2 , . . . , xn . Váhy wi teda modifikujú vstupné hodnoty ešte
pred operáciou sumácie. Funkciu, ktorá mapuje výstup tejto váženej sumácie
na finálny výstup je nazývame aktivačná funkcia. Používajú sa viaceré typy
nelineárnych funkcií ako: Heaviside-ova, thresholdová, sigmoidná, logistická,
hyperbolická tangentoida a iné funkcie [4, 2].
Na základe štruktúry, usporiadania, topológie a spojenia medzi neurónmi
delíme NN na viacero architektonických typov:
Single layer feedforward - obsahuje 2 vrstvy neurónov, vstupnú, na ktorej neuróny sú privedené vstupy vektora x a výstupnú, ktorej neuróny
58
3.2. Klasifikácia vzorov
vykazujú výstup (je schopná klasifikovať len lineárne separovateľné problémy).
Multi layer feedforward - podobne ako predchádzajúca sieť, obsahuje vstupnú
a výstupnú vrstvu, ale na rozdiel od nej obsahuje ešte jednu alebo viacero skrytých vrstiev. Skrytými vrstvami zvýšime počet neurónov a tým
pádom je možné vytvoriť akúkoľvek vstupno-výstupnú funkciu. Schématické zobrazenie takejto siete môžeme vidieť na obrázku 3.3. Tento typ
NN je zrejme najpoužívanejší a existujú rôzne modifikácie tejto siete
vzhľadom na prepojovaciu sieť medzi neurónami (fully connected, partially connected).
Simple recurrent network - NN v ktorej existuje spätná väzba vedúca od
skrytej vrstvy opätovne k vstupnej alebo jednoducho k predchádzajúcej
vrstve (spätná väzba simuluje dynamický systém).
Fully recurrent network - v tejto NN existujú viacnásobné spätné väzby
medzi prepojenými neurónmi (obojstranné spojenia).
vstupná vrstva
(vektor x)
skryté vrstvy
výstupná vrstva
xF1
ω1
xF2
···
xF3
...
...
ω2
...
···
...
ωW
xFN
Obr. 3.3: Schématická ukážka neurónovej siete (multilayer, feed-forward)
NN patria do skupiny klasifikátorov, v ktorej sa väčšinou stretávame so
supervizovaným učením, to znamená, že ich iniciačnou fázou je učenie na dátach, ktoré sú kompletné a každý vzor z trénovacích dát obsahuje atribút label,
ktorý určuje príslušnosť k danej triede. V trénovacej fáze dochádza k iteratívnej adaptácii jednotlivých váh (poznáme aj učenie rozšírené o adaptáciu
štruktúry vnútorných, skrytých vrstiev NN) a tým k minimalizácii rozdielu
medzi vstupným a výstupným vektorom. Po učebnej fáze je neurónová sieť
59
3. Rozpoznávanie vzorov - pattern matching
schopná reagovať na akýkoľvek vstupný vektor odpoveďou príslušnosti daného
vzoru k určitej triede.
Použitie NN v rozličných aplikačných oblastiach je priamo implikované ich
vlastnosťami. Tieto vlastnosti zahŕňajú schopnosť učiť, adaptovať sa, zobecňovať problémy, ich štruktúra pamäte zaručuje, že zlyhanie jedného neurónu
nemá za následok fatálne zlyhanie celej NN a hlavne možný paralelný prístup
[1]. Spomenuté vlastnosti vedú k použitiu najmä v rozpoznávaní rukopisov,
rozpoznávaní vzorov, regresii, spracovaní signálov, robotike, predpovediach a
modelovaní.
3.2.4
Rozhodovacie stromy
Ak sa rozhodneme použiť rozhodovacie stromy (DT), je to väčšinou z dôvodu
ich jednoduchosti a transparentnosti. Je jednoduché pochopiť ich štruktúru
a interpretovať vzťahy extrahované z dát, pretože využíva stromovo orientovaný graf. V porovnaní s ostatnými metódami, napríklad s NN, sa DT javia
ako pomerne primitívne, ale aj tento model je dostatočne silný a v niektorých
prípadoch dosahuje výborné výsledky. Základným problémom je konštrukcia správneho modelu, stromu [14]. Základnou myšlienkou DT je klasifikovať
vzory na základe zodpovedania postupnosti dobre zvolených otázok, v ktorej nasledujúca otázka závisí od odpovede na aktuálnu otázku. Tieto otázky
charakterizujú uzly daného stromu a odpovede na nich sú charakterizované
hranami vedúcimi k potomkom aktuálneho uzlu. Na obrázku 3.4 je ukážka
DT. Notácia DT je zväčša z hora nadol alebo sprava doľava.
xF1 < 0.7
<
>
xF2 < 0.5
xF5 < 0.2
>
<
<
xF4 < 0.3
C1
<
C3
>
xF4 < 0.7
>
<
C2
C6
>
C4
C5
Obr. 3.4: Ukážka rozhodovacieho stromu
Učenie DT spočíva v použití trénovacích dát na vytvorenie (rast) DT.
Základnou myšlienkou je v každej vetve rozhodnúť podľa istého kritéria ako
trénovaciu množinu dát rozdeliť tak, aby každá z nich obsahovala len prvky
ideálne jednej triedy. V takomto prípade je nutné v každom uzle rozhodnúť,
či je daná množina akceptovateľná alebo je nutné uskutočniť ďalšie rozhodnutie na rozdelenie danej množiny. To zreteľne implikuje rekurzívny proces, čo
môže viesť k vytvoreniu obrovského stromu, ktorý bude preučený na trénovacie dáta. Veľmi významným parametrom je teda ukončovacie kritérium, ktoré
60
3.2. Klasifikácia vzorov
príjme napríklad aj nie úplne homogénnu podmnožinu, čo sa týka príslušnosti
k triede. Konštruktívna metodológia DT známa ako CART (classification and
regression trees) vytvára obecný framework, ktorý je možné aplikovať viacerými spôsobmi na vytvorenie rozdielnych DT. Uvádza niekoľko významných
vlastností, ktoré je nutné poznať a určiť k vytvoreniu DT [14].
1. Podľa ktorého atribútu sa budeme rozhodovať v danom uzle?
2. Koľko rôznych odpovedí (potomkov) máme na výber?
3. Hodnota ukončovacieho kritéria - kedy rozhodneme, že daný uzol sa
stane listom DT.
4. Ak je strom príliš veľký, ako ho možno ho zredukovať na jednoduchšiu
verziu so zachovaním klasifikačnej úspešnosti.
5. Ak list DT obsahuje nehomogénnu podmnožinu, ako bude tejto množine
priradená triedna príslušnosť.
Najdôležitejším faktorom je zrejme voľba deliaceho kritéria, atribútu (atribútov), podľa ktorého dané dáta v aktuálnom uzle rozdelíme. Ako bolo spomenuté, chceme vytvoriť postupnosť rozhodnutí, ktoré vedú k jednoduchému,
kompaktnému stromu s niekoľkými uzlami. Hľadáme teda atribút, ktorý dokáže separovať dáta tak, že následné uzly budú čo možno najhomogénnejšie.
Pri formalizácii tejto myšlienky by bolo vhodné definovať skôr nehomogenitu
ako homogenitu. Nech teda i(N ) je nehomogenita ulza N . Chceme aby i(N )
bola rovná 0 ak všetky vzory v danej podmnožine prislúchajú k jedinej triede
a naopak, aby mala najvyššiu možnú hodnotu pre triedy zastúpené rovnakým
počtom vzorov. Používanou metrikou nehomogenity je tzv. entropy impurity:
i(N ) = −
X
Pˆ (x ∈ ωj |N ) log2 Pˆ (x ∈ ωj |N ),
(3.30)
j
kde Pˆ (x ∈ ωj |N ), je podiel vzorov kategórie ωj v uzle N . Ak všetky vzory
budú reprezentovať jedinú triedu, podiel vzorov v uzle N bude 1 a tým pádom
výsledná hodnota i(N ) sa bude rovnať 0 a je teda splnená podmienka, ktorú
sme si zvolili. V opačnom prípade bude určite kladná [2].
Druhou vlastnosťou je počet možných následníkov k danému uzlu. Tento
problém sa často rieši binárnymi DT, kvôli rýchlosti a jednoduchosti vytvárania stromu.
Ako sme už spomínali, ak necháme DT konštruovať do jeho maximálnej
výšky, model sa na tieto dáta značne preučí. V extrémnom prípade by všetky
listy takého stromu obsahovali len jeden vzor. Ukončovacie kritérium teda musí
byť zvolené dostatočne správne. Jednoduchým riešením môže byť voľba thresholdu pre hodnotu nehomogenity tak, že delenie sa zastaví, ak najlepšie možné
61
3. Rozpoznávanie vzorov - pattern matching
delenie v uzle N redukuje nehomogenitu o menej než tento stanovený threshold: ∆i(N ) ≤ Ti . Tento prístup, napríklad na rozdiel od cross-validation,
na učenie používa celú trénovaciu množinu, čo môže zlepšiť konečný výsledok. Druhou výhodou je to, že listy stromu môžu ležať v rozdielnych výškach
stromu, čo je žiadané, ak sa zložitosť dát mení po celom rozsahu vstupu [2].
Najpopulárnejšími používanými stromovými algoritmami sú dnes ID3 a
C4.5 prípadne C5.0. Klasifikácia pomocou DT sa využíva najmä v rozhodovacej analýze, medicínskej diagnostike a podobne.
62
KAPITOLA
Experimentálna časť
V tejto časti práce sa venujeme niekoľkým experimentom použitia jednotlivých
metód predstavených v kapitole 1. Snažili sme sa navrhnúť postup aplikácie
rôznych metód predspracovania obrazu na fotografie identifikačných známok
(razených a farebných) na zvýšenie kvality týchto obrázkov a tým na zvýraznenie identifikačných znakov obsiahnutých v týchto dátach. Následne ukážeme
niekoľko experimentov a dosiahnutých výsledkov zvolených metód predstavených v časti 3, ako extrakcie príznakov, tak aj rôznych klasifikačných prístupov, a doporučíme ten najlepší postup vedúci k automatizácii procesu v tomto
odvetví priemyslu.
Keďže výsledkom tejto práce nemá byť samotná implementácia nástroja na
identifikáciu daných metalurgických vzoriek, rozhodli sme sa experimenty vytvoriť v nástrojoch, ktoré už obsahujú a podporujú niektoré funkcie a metódy,
ktoré sme popísali či už pre predspracovanie dát alebo pre samotnú extrakciu
príznakov a rozpoznávanie. Z týchto dôvodov sme sa rozhodli použiť programovacie prostredie na vývoj algoritmov, analýzu a vizualizáciu dát, nástroj
Matlab. Pri práci sme využívali Matlab R2011b (7.13.0.564) pre 32-bitový
operačný systém a z jeho predpripravených nástrojov využívali najmä Image
Processing Toolbox a samozrejme základné funkcie tohto jazyka. Nástroje obsiahnuté v tomto balíčku podporujú prácu s rozličnými typmi obrazových dát
a dovoľujú skúmať obrázky, vylepšovať kontrast a iné vlastnosti obrazu, balancovanie farieb, automaticky aplikovať predpripravené priestorové filtre, napríklad na detekciu hrán, zaostrovanie, vyhladzovanie, analyzovať textúry a tvary
v obraze, detekovať a merať rôzne atribúty obrazu a podobne. Po extrakcii
príznakov z dát sme sa rozhodli na ich úpravu, klasifikáciu a vizualizáciu použiť data-miningový open-source nástroj RapidMiner, ktorý ponúka rozsiahle
možnosti v analýze, integrácii a transformácii dát. Ďalej ponúka značné množstvo modelovacích algorimov a metód na analýzu príznakov, ich klasifikáciu a
vizualizáciu. Experimenty sme uskutočňovali v nástroji verzie RapidMiner
63
4
4. Experimentálna časť
5.1.003. V ďalšej časti práce sa zameriame už na spomínané experimenty a
výsledky, ako číselné tak aj vizuálne a ukážky prípadov zlyhania a zaujímavostí a úskalia, s ktorými sme sa stretli počas práce s týmito dátami. Kapitola je rozdelená na niekoľko nadväzujúcich častí popisujúcich celý postup
práce, od porozumenia dátam, cez predspracovanie, modelovanie až k vyhodnoteniu výsledkov ich spracovania a celkovému zhodnoteniu. Pre testovanie a
experimenty sme samozrejme využili oba druhy dát, poskytnutých spoločnosťou KMC GROUP s.r.o., vzorky označené razeným identifikátorom a vzorky
označené farebným náterom.
4.1
Spracovanie a identifikácia vzoriek s razenou
identifikačnou známkou
Tieto dáta sú značené automatickým raziacim systémom pre teplé alebo chladné
značenie zväčša v strojárenskom priemysle. Značenie je permanentné dokonca
aj na surových neopracovaných zväčša kovových materiáloch. Jednotlivé znaky
sú vsadené do matríc rôznych veľkostí (5 × 7, 7 × 9, 11 × 16). Ukážka používaného fontu sa nachádza v prílohe B, obrázok B.3.
4.1.1
Porozumenie problému a dátam
Našou úlohou je z fotografických snímkov vzoriek materiálov označených identifkátorom tento identifikátor rozpoznať a určiť jednotlivé znaky, z ktorých sa
identifikátor skladá. Dáta ktorými disponujeme obsahujú identifikátor zložený
len z číslic, neobsahuje žiadne ďalšie znaky ani interpunkčné znamienka. Na
obrázku 4.1 môžeme vidieť fotografickú ukážku vzorky, ktorá je takto označená (znaky sú razené v matrici veľkosti 5 × 7). Takýchto snímkov máme k
dispozícii 42, z ktorých každý je označený rovnakým typom identifikátora a
každý z nich je zložený z 7-8 číslic (počet identifikátorov o veľkosti 7: 10 a o
veľkosti 8: 32). V konečnom dôsledku teda disponujeme 326 číslicami ktorých
popis je v tabuľke 4.1.
číslica
1
2
3
4
5
6
7
8
9
0
# vzoriek
83
38
48
9
67
10
35
3
27
6
Tabuľka 4.1: Počty jednotlivých číslic v dostupných dátach
Takéto dáta nie sú veľmi vhodné pre klasifikačné úlohy, pretože počet vzoriek pre jednotlivé triedy je rôzny. Najnepriaznivejšie sú na tom dáta číslice
„4“, „8“ a „0“, pretože počet ich výskytov je veľmi nízky. Takéto dáta nazývame nevybalancované a riešenie tohto problému popíšeme v nasledujúcej
kapitole 4.2.
64
4.1. Spracovanie a identifikácia vzoriek s razenou identifikačnou známkou
Obr. 4.1: Ukážka vzorky s razeným identifikátorom
4.1.2
Predspracovanie
Po obhliadnutí dát môžeme konštatovať niekoľko skutočností:
1. obrázok nie je postihnutý vysokým stupňom šumu,
2. identifikátor je jasne viditeľný,
3. v obraze sa nenachádzajú žiadne podobné objekty ako identifikátor,
4. číslice sú výrazné, rovnako orientované a navzájom sa neprekrývajú.
Pri predspracovaní dát sme vyskúšali rôzne metódy a snažili sa spomedzi
nich vybrať tú najlepšiu pre dané dáta. Jednotlivé metódy sme hodnotili na
vizuálnom základe a ako merateľnú veličinu sme použili jednoduché sčítavanie objektov v obraze, keďže vieme koľko a akých číslic sa v týchto dátach
nachádza. Optimálny počet objektov (vyrazených dier) je 4 533. Pri meraní
tejto hodnoty pri predspracovacích metódach sme počítali s istým šumom,
65
4. Experimentálna časť
ktorý sa v dátach určite vyskytuje a ktorý môže byť charakterizovaný ako
vyrazená diera. Ukážky po aplikácii niektorých vybraných metód sú zobrazené na obrázku 4.2. Väčšinou sme sa zamerali na metódy, ktoré vyhladzujú
obraz a následne na segmentáciu identifikátoru oproti pozadiu. Keďže dáta
nepostihuje impulzívny šum, použili sme väčšinou Gaussovský filter.
(a)
(b)
(c)
(d)
Obr. 4.2: Ukážka predspracovaných snímkov vzorky s identifikačnou známkou
s použitím rôznych predspracovacích techník
(a) - v tomto prvotnom postupe sme sa snažili využiť jednoduché základné
operácie s obrazom. V prvom kroku sme použili Gaussovský filter na
vyhladenie a prípadnú redukciu šumu. Následne sme obrázok previedli
na obraz v stupňoch šedi a aplikovali Sobelovský detektor hrán. Ten zabezpečil identifikáciu detailov a teda častí identifikátora. Následne sme
aplikovali morfologickú operáciu zvanú dilatácia. Po jej aplikácii sa z
hrán stali hrubšie čiary, ktoré sa uzavreli do akýchsi kružníc, ak sa jednalo o hrany častí identifikátora. Ďalšou úpravou bolo vyplnenie týchto
kružníc, aby sa javili ako kruhy, podobne ako sa javia v pôvodnom obraze. Následne sme aplikovali 2x operáciu erózia, ktorá spôsobila kolaps
66
4.1. Spracovanie a identifikácia vzoriek s razenou identifikačnou známkou
objektov na menšie oblasti, pričom časti identifikátora ešte ostali viditeľné ako body. Zmysel použitia takejto operácie je redukcia nežiadúcich
objektov (šumu). Ako poslednú sme previedli opäť operáciu dilatácie
aby sa časti identifkátoru stali viditeľnejšie. Výsledná hodnota jednotlivých častí však bola len 2 815, čo je oproti skutočnosti veľmi málo. To
je spôsobené akýmsi pospojovaním častí identifikátora, ktoré teda vytvoria namiesto niekoľkých objektov len jeden. Na zobrazenej ukážke sa
predspracovanie javí ako relatívne dobré.
(b) - pri tomto type predspracovania sme ako prvý použili jednoduchý Gaussovský filter o veľkosti 3×3, σ = 3 na vyhladenie obrazu. Po jeho aplikácii
sme sa zamerali na časti identifikátora. Keďže jednotlivé body vyrazených číslic sú pomerne malé, je vhodné použiť niektorú zo zaostrovacích
techník na vylepšenie detailov na hranách jednotlivých vyrazených dier.
Po niekoľkých testoch rôznych metód sme sa rozhodli pre aplikáciu highboost filteringu, ktorý sme popísali v kapitole 2.2.1.2. Gaussovský filter
použitý na vytvorenie masky mal parametre: 11 × 11, σ = 3 a parameter
k pri použití highboost filteringu má hodnotu k = 3. Následne sme sa
už mohli zamerať na segmentáciu, pretože identifikátor bol dostatočne
zvýraznený oproti pozadiu. Použili sme automatickú funkciu globálneho
thresholdingu použitím Otsuovej metódy. Počet jednotlivých častí identifikátora dosiahol hodnotu 5 861, čo je podstatne viac ako reálny počet
vyrazených dier.
(c) - po predchádzajúcom zistení, že takýto postup je relatívne správny sme
sa ho rozhodli rozhodli len málo zmeniť. Namiesto použitia Gaussovského filtra v prvom kroku sme sa rozhodli použiť filter bilaterálny. Ten
bude mať rovnaký efekt ako gaussovský s rozdielom lepšieho zachovania
hrán. Použité parametre bilaterálneho filtru boli: veľkosť 5 × 5, σ1 = 3,
σ2 = 0.09. Vizuálnym zhodnotením, sa identifikátor javí trošku ostrejšie
a šumové zložky sú redukované viac ako v predchádzajúcom prípade.
Avšak počet identifikovaných dier vo všetkých dátach je len 4 149, čo
je menej ako reálny počet a tým pádom sme prišli o niektoré z nich.
Ďalšou nevýhodou tohto postupu je aplikácia bilaterálneho filtra, ktorá
je výpočtovo extrémne náročná.
(d) - tento typ predspracovania je úplne zhodný z postupom b až na hodnotu
parametra k, ktorého hodnotu sme sa následne snažili empiricky zistiť.
Z vizuálnej stránky a podľa počtu častí sme tento parameter ponechali
na hodnote k = 1, 5. Súčet jednotlivých častí pri tomto postupe je 4 606,
čo pomerne dobre odpovedá skutočnosti. Túto predspracovaciu metódu
sme ďalej použili pri experimentoch.
V ďalšom kroku predspracovania je potrebné tento identifikátor čo najpresnejšie lokalizovať, čo bolo realizované automaticky v prostredí Matlab.
67
4. Experimentálna časť
4.1.2.1
Lokalizácia identifikátora
V predspracovanom obraze je jasne vyznačený identifikátor pomerne jednoduché lokalizovať. Problémom je, ako je viditeľné na obrázkoch 4.2, prítomnosť
objektov podobných samotným častiam identifikátora. S týmto problémom sa
potýka samotná lokalizácia, ale aj následná automatická separácia.
Pred samotným ohraničením identifikátora bolo potrebné čo možno najviac týchto šumových zložiek z obrazu odstrániť, na čo sme navrhli jednoduchý
spôsob detekcie a eliminácie akýchsi outlierov. Outlier je všeobecne odľahlá
hodnota, ktorej parametre sa od ostatných podstatne líši. Túto skutošnosť
sme využili na ich detekciu. Z obrazu je možné zistiť, že jednotlivé vyrazené
diery sú pri sebe relatívne blízko. Ak sa zameriame na časti, ktoré nie sú súčasťou identifikátora, môžme usúdiť že vzdialenosť k najbližšiemu bodu je o dosť
väčšia. Na základe merania vzdialenosti, práve k najbližšiemu susedovi sme
boli schopní tieto šumové zložky lokalizovať a odstrániť. Hodnotu, s ktorou
sme jednotlivé vzdialenosti porovnávali, sme vypočítali ako priemernú veľkosť
jednotlivých častí v tomto predspracovanom obraze.
Ukážku takto lokalizovaného identifikátora z obrázku 4.2d môžme vidieť
na obrázku 4.3.
Obr. 4.3: Ukážka lokalizovaného identifikátoru
4.1.2.2
Separácia jednotlivých častí identifikátora
V takto predspracovanom obraze môžeme pristúpiť k samotnej separácii číslic.
Tým, že v jednotlivých obrazoch sú číslice orientované prirodzene vertikálne,
je možné použiť veľmi jednoduchú techniku na ich separáciu. Využijeme znalosť toho, že sa jednotlivé číslice neprekrývajú a tak medzi nimi vzniká akési
prázdne miesto, ktoré môžeme detekovať napríklad sumáciou hodnôt v jednotlivých stĺpcoch. Podobne je možné lokalizovať jednotlivé riadky, v ktorých
sa číslice nachádzajú, sumáciou hodnôt po riadkoch.
68
4.2. Extrakcia príznakov
Pred aplikáciou tejto metódy však musíme zabezpečiť to, aby nám automatická separácia číslicu „nerozrezala“, ak by sa vytvorilo prázdne miesto medzi
vyrazenými dierami. Preto pred separáciou riadkov, čiže „rezom“ v horizontálnom smere, aplikujeme už spomínanú operáciu dilatácie, no tentokrát len
vo vertikálnom smere. Analogicky, pri reze vo vertikálnom smere aplikujeme
dilatáciu v smere horizontálnom.
Oddeľovacie rezy boli prevedené 2x striedavo, v horizontálnom smere a následne v smere vertikálnom a znova. Vzniknuté separáty boli ešte analyzované
na základe počtu objektov (vyrazených dier) a tie, ktoré obsahovali menej
objektov ako 4 boli odstránené. Ďalšia analýza spočívala v rozbore veľkosti
daných častí. Použili sme apriórnu znalosť, že číslice sú na výšku zložené zo 7
segmentov (značenie v matrici 5×7). Zistili sme priemerný rozmer jednotlivých
malých objektov na výšku a separáty, ktoré nesplnili podmienku, aby tento
rozmer bol vyšší ako 5x priemerná hodnota malých častí, bol tiež odstránený.
Analýzou rozmerov vo vertikálnom smere sme sa nezaoberali pretože pri tejto
veľkosti závisí od danej číslice (napríklad číslica „1“ je zobrazená v matrici
3 × 7 - viď ukážku použitého fontu v obrazových prílohách). Touto analýzou
sme opäť redukovali šum, ktorý sa mohol v obrazoch vyskytovať. Po separácii
boli vo všetkých oddelených častiach orezané zbytočné okraje. Výsledok po
takejto separácii je zobrazený na obrázku 4.4
Obr. 4.4: Separované číslice z obrázku 4.3
4.2
Extrakcia príznakov
V tejto časti už disponujeme dátami, z ktorých je možné extrahovať zvolené
príznaky. Ako sme však uviedli v predchádzajúcej časti, dáta nie sú dobre
balancované a tento problém je potrebné vyriešiť. Balancovanie dát sme uskutočnili dogenerovaním umelých dát náhodnou rotáciou: α ∈ h−45, 45i (pri
vyšších povolených uhloch dochádzalo k zámene číslic „6“ a „9“ ) a škálovaním reálnych dát tak, aby počet zástupcov jednotlivých tried bol rovnaký.
Výsledné dáta majú veľkosť 850 záznamov a každá z tried má 85 zástupcov.
Pre všetky typy príznakov, chceme vytvoriť univerzálny formát ich zápisu
a ten je zobrazený na nasledujúcej schéme:
att1 att2
...
attn
label
ID
69
4. Experimentálna časť
Veľkosti príznakových vektorov budú pre jednotlivé typy príznakov premenlivé. Vektor príznakov CM bude mať veľkosť 7 atribútov (použité všetky
centrálne momenty), ZM7 36 a ZM8 45 atribútov a u grid features alebo angles
features sme zvolili počty atribútov na 36 a 49 pre grid features a na 36 a 48
pre angles features.
Extrakcia príznakov je významnou časťou v celom procese klasifikácie vzorov a je nutné dané príznaky extrahovať s čo najlepšími vlastnosťami. Rôzne
metódy extrakcie príznakov si však väčšinou vyžadujú aj špecifické podmienky,
pri ktorých sa dané príznaky z dát získavajú. V nasledujúcich podkapitolách
poukážeme na potrebu špecifických predspracovacích metód pred samotnou
extrakciou daných príznakov.
4.2.1
Grid features
Použitie dát, ktorými disponujeme nemajú vlastnosti, ktoré by boli vhodné
pre extrakciu týchto príznakov, pretože v separovaných obrázkoch sú číslice
zložené z jednotlivých častí. Princíp extrakcie týchto príznakov je založený na
rozdelení obrazu do mriežky a pri takomto spôsobe zobrazenia číslic by bola
extrakcia príliš náchýlná na šum, keďže by mohlo dôjsť k presunu vyrazenej
diery do iného políčka tejto mriežky. Preto sme zvolili dodatočné predspracovanie pripravených vzoriek, ktorým chceme dosiahnuť stav, zobrazený na
obrázku 3.1a.
Takúto úpravu môžme docieliť použitím základných predspracovacích techník. Úprava spočívala v aplikácii priemerovacieho filtra s veľkosťou 3 × 3 z dôvodu vyhladenia hrán vyrazených dier. Následne bol použitý ešte nelineárny
max-filter s veľkosťou 7 × 7, ktorý v obraze vyhľadáva body s najvyššou intenzitou a teda bodom, ktoré sa nachádzajú v blízkosti tohto bodu upraví ich
intezitu práve na hodnotu najsilnejšieho bodu. To ma za následok vytvorenie
spojitého objektu premostením jednotlivých značiek. Ako posledný bol ešte
aplikovaný mediánový filter (3 × 3) na vyhladenie hraníc objektu. V tomto
momente už boli objekty výborne viditeľné a spojité a ďalšou úpravou bolo
použitie morfologickej operácie thin, ktorá spôsobí kolaps objektu na líniu,
takže z čislice sa stala len kostra objektu šírky 1px. Aplikácia tejto operácie
bola takmer nevyhnutná, pretože pôvodný spojitý objekt zasahoval takmer
do všetkých políčok mriežky, čo by viedlo k vysokej podobnosti príznakových
vektorov. Následne sme ešte eliminovali zbytočný okraj na všetkých stranách,
aby okraje číslice boli tesne na okraji obrázku. Podľa počtu zvolených atribútov, ktoré má výsledný vektor obsahovať bolo
p nutnépzmeniť veľkosť obrázku,
tak aby ho bolo možné presne rozdeliť na |x| × |x| polí, kde |x| je veľkosť príznakového vektoru. Jednotlivé príznaky sme extrahovali na základe
princípu popísaného v časti 3.1.1 a ukážka takto predpripravených dát je na
obrázku 4.5.
70
4.2. Extrakcia príznakov
Obr. 4.5: Separované číslice upravené pred extrakciou grid features
4.2.2
Angles features
Pri použití týchto príznakov nebolo nutné rapídne pretvárať charakter objektov a preto sme použili len filtráciu pomocou max-filtru s veľkosťou 3×3, ktorý
bol použitý za účelom zvýraznenia a zväčšenia jednotlivých značiek, aby sme
zvýšili pravdepodobnosť pretnutia priamkou. Výpočet jednotlivých príznakov
je popísaný v časti 3.1.1.
4.2.3
Centrálne momenty
Z teoretickej znalosti vlastností príznakov sme sa rozhodli použiť pred extrakciou CM podobný postup ako pri extrakcii grid features. Rozdiel oproti tomuto
postupu je vo vynechaní morfologickej operácie vytvorenia kostry objektu, pretože problémom u týchto príznakov je normalizácia momentom nultého rádu
m00 , ktorý popisuje hustotu obrázku. Pri línii širokej 1px by hodnota tohto
normalizačného prvku bola veľmi nízka a výsledné príznaky by dosahovali
vysoké hodnoty.
Rozdiely v hodnotách bez a s použitím operácie vytvorenia kostry sú zobrazené v nasledujúcej ukážke:
no thin
0.508
0.218
1.078
0.430
0.289
0.197
0.051
thin
4.606
20.622
90.474
51.275
3424.77
209.16
-683.979
Na základe týchto hodnôt sme sa rozhodli definitívne nepoužiť operáciu
vytvorenia kostry, keďže sa hodnoty pri použití tejto operácie líšia rádovo až
o 103 .
Ukážka výsledkov metódy predspracovania pred extrakciou centrálnych
momentov je na obrázku 4.6.
71
4. Experimentálna časť
Obr. 4.6: Separované číslice upravené pred extrakciou centrálnych momentov
4.2.4
Zernike moments
Extrakcii ZM predchádzala špecifická predspracovacia metóda, ktorá vyplýva
z ich definície. ZM vyžadujú aby objekt, ktorý popisujú, bol úplne obsiahnutý
v kružnici. Body, ktoré sa nachádzajú mimo tejto kružnice by neboli pri výpočtoch uvažované, čo by značne ovplyvnilo silu týchto príznakov.
Opäť ako v predchádzajúcom prípade sme aplikovali priestorové filtre s
rovnakým efektom ako v prípade centrálnych momentov. Podobne zachováme
objekt číslice výrazný a dostatočne hrubý. Následne obrázok pretransformujeme tak, aby bolo možné splniť podmienku obsiahnutia v kružnici. Prvým
krokom bolo orezanie okrajov, aby obrázok mal minimálne rozmery a zároveň
obsahoval celú, teraz už spojitú číslicu. Následne bolo potrebné prenastaviť
veľkosť obrázku, aby sa z neho vytvoril presný štvorec (na skúšobných dátach
na veľkosť 100 × 100px). Následne sme k obrázku opäť pridali okraje, aby
sa objekt číslice presunul do stredu, aby bolo možné opísať tomuto objektu
kružnicu. Šírku okrajov je možné vypočítať použitím Pytagorovej vety:
a
2
+
2
a
2
−
a
2
x
+
2
a
x=
r 2
a
2
x
a
kde a je veľkosť strany štvorca upraveného obrázku a x je šírka okraju, ktorý
musí byť k tomuto obrázku pridaný, aby sa celá kružnica obsahujúca obraz s
číslicou zmestila do výsledného obrázku.
Ukážka separovaných číslic pripravených na extrakciu ZM použitím popísaného postupu je na obrázku 4.7.
72
4.3. Experiment I
Obr. 4.7: Separované číslice upravené pred extrakciou ZM
4.3
Experiment I
Klasifikácia vzorov na základe extrahovaných príznakov
V prvom experimente sme sa rozhodli klasifikovať objekty za pomoci štyroch rôznych typov príznakov a štyroch základných klasifikátorov a na základe
výsledkov ďalej analyzovať tieto príznaky. Dáta boli importované do nástroja
RapidMiner ako „.csv“ súbory. Následne bola klasifikácia prevedená za pomoci cross-validácie (10x validácia), ktorá zaručuje, aby trénovacie dáta neboli
použité ako testovacie, a naviac všetky podmnožiny použité na testovanie sa
objavia aj v testovacích dátach. Výsledky tejto klasifikácie sú v tabuľke 4.2.
k-NN (best)
Bayes
DT
NN
grid (6 × 6)
96,71% (1)
66,71%
10,24%
92,35%
grid (7 × 7)
97,88% (1)
81,76%
9,41%
93,41%
angles (36)
92,94% (1)
77,29%
22,94%
84,71%
angles (48)
93,76% (1)
78,35%
21,41%
88,12%
CM (7)
87,06% (1)
80,35%
82,82%
82,59%
ZM7 (36)
99,29% (2)
95,41%
90,59%
97,06%
ZM8 (45)
99,53% (2)
94,71%
89,65%
97,76%
Tabuľka 4.2: Tabuľka zobrazujúca použitie rôznych klasifikátorov v kombinácii
s rôznymi typmi príznakov (zachované všetky atribúty).
Keďže sme použili klasifikátor k-NN, bolo potrebné zistiť hodnotu tohto
parametru tak, aby výsledok klasifikácie bol čo najlepší. Túto hodnotu sme
zisťovali automaticky za pomoci operátora Loop v spomínanom nástroji. Testovali sme hodnoty k = (1, . . . , 30). Na obrázku 4.8 je zobrazený graf závislostí
na tomto parametri pre príznaky grid(49), angles(48), CM(7) a ZM8 (45).
73
4. Experimentálna časť
Závislosť úspešnosti k-NN na parametri k
100
Úspešnosť [%]
95
90
85
80
grid(49)
angles(48)
CM(7)
ZM8 (45)
75
70
0
5
10
15
k
20
25
30
Obr. 4.8: Graf zobrazujúci závislosť úspešnosti k-NN na parametri k
V tabuľke 4.2 je vidieť, že všetky typy príznakov dosahujú najlepšie výsledky v spojení s klasifikátorom najbližšieho suseda. To je zrejme spôsobené
tým, že tento klasifikátor sa rozhoduje len podľa niekoľkých najbližších susedov, pričom ostatné klasifikátory sa snažia nastaviť si určité vnútorné parametre na základe všetkých dát (separačnú hranicu určujú na základe prvkov celej triedy). Tento poznatok vypovedá aj o sile jednotlivých príznakov.
Môžme si všimnúť, že grid a angles features v spojení s inými klasifikátormi
dosahujú pomerne odlišné výsledky pričom CM a ZM sú pomerne stabilné i
pri zmene klasifikačnej metódy. V ďalšom experimente sa zameriame práve na
významnosť jednotlivých atribútov z príznakových vektorov.
4.4
Experiment II
Výber najvýznamnejších príznakov
V tomto experimente chceme porovnať význam jednotlivých príznakov
medzi sebou na základe niektorej z dostupných metód feature selection.
V prvom kroku vytvoríme príznakové vektory združujúce všetky dostupné
príznaky: grid f.(49) + angles f.(48) + CM(7) + ZM8 (45). Výsledný formát
tohto príznakového vektoru bude mať teda tvar:
74
4.5. Experiment III
1, . . . , 49
50, . . . , 97
98, . . . , 104 105, . . . , 149
grid(49) angles(48)
CM (7)
150
151
ZM (45) label ID
V nástroji RapidMiner sme namodelovali knowledge-flow pozostávajúci
z načítania dát a operátora wrapper feature selection Forward Selection. Ako
modelovací operátor sme zvolili pre porovnanie k-NN a NB. Následne sme feature selection operátor nahradili operátorom Wrapper-X-Validation a použili
váženie príznakov pomocou operátora Weight by Information Gain. Výsledky
týchto experimentov sú zobrazené v tabuľke 4.3 a 4.4.
atr.
váha
99
103
21
101
98
16
18
35
1
14
CM
CM
G
CM
CM
G
G
G
G
G
1
0, 742
0
0, 960
0, 832
0
0
0
0
0
Tabuľka 4.3: Selekcia 10 najvýznamnejších atribútov s odpovedajúcou hodnotou information gain pre modelovanie klasifikátorom k-NN
atr.
váha
99
113
100
117
63
101
110
105
128
74
CM
ZM
CM
ZM
A
CM
ZM
ZM
ZM
A
1
0, 613
0, 876
0, 509
0, 150
0, 960
0, 550
0, 475
0, 421
0, 176
Tabuľka 4.4: Selekcia 10 najvýznamnejších atribútov s odpovedajúcimi hodnotami information gain pre modelovanie NB
Na základe analýzy výsledkov tohto experimentu môžme uviesť, že klasifikátorom k-NN boli vybrané skôr jednoduchšie príznaky, dokonca aj tie, ktoré
majú nulovú hodnotu informačného zisku. To vypovedá o skutočnosti, že kNN neskúma v dátach ich skutočnú štruktúru a nevyhľadáva vzory v nich
obsiahnuté, ale riadi sa len podobnosťou na základe jedného alebo niekoľkých
podobných objektov. Na druhú stranu NB spojený s feature selection vyselektoval práve tie sofistikovanejšie príznaky ako sú CM a ZM, ktorých informačný
zisk je podstatne vyšší ako u grid a angles features.
Úspešnosť klasifikácie pomocou k-NN v spojení s vyselektovanými príznakmi sa oproti použitiu jednotlivých príznakov osobitne znížila na hodnotu
93,88%. Pri použití NB a vybraných príznakov sa úspešnosť oproti hodnotám v tabuľke 4.2 dokonca zvýšila na 96,82% čo svedčí o výbornej schopnosti
separácie tried pomocou príznakov CM a ZM.
4.5
Experiment III
Na základe poznatkov získaných z experimentu I a II sa v ďalších experimentoch zameriame hlavne na príznaky CM a ZM, ktoré vykazujú dobrú schopnosť
75
4. Experimentálna časť
sepáracie tried a kvôli faktu, že výsledná presnosť klasifikácie je s použitím
týchto príznakov pomerne stabilná pre ľubovoľný klasifikátor, čo predikuje ich
vysokú diskriminatívnu silu.
Diskriminatívna schopnosť CM
Základnou charakteristikou, ktorá sa využíva na analýzu atribútov je korelačná matica. Táto matica obsahuje hodnoty korelačného koeficientu ρX,Y pre
všetky kombinácie atribútov. Na základe týchto hodnôt je možné určiť relevanciu prípadne redundanciu atribútov. Korelačný koeficient nadobúda hodnoty
z intervalu h−1, 1i. Hodnota koeficientu je: 1 v prípade úplnej korelácie medzi
dvoma atribútmi (atribúty sú rovnaké), −1 v prípade tzv. antikorelácie a 0 v
prípade absolútnej nekorelácie (nezávislosť atribútov).
Na základe hodnôt v tabuľke 4.5 môžme vyvodiť, že nie všetky atribúty sú
potrebné ku klasifikácii, pretože sú len lineárnou kombináciou jedného alebo
viacerých atribútov. To charakterizujú hodnoty koeficientu ρ blížiace sa k
hodnote 1. Pridaním operátoru forward-selection budú z príznakového vektoru
vybrané len tie, ktoré sú najviac diskriminatívne.
atr.
att1
att2
att3
att4
att5
att6
att7
att1
1,0
0,868
0,425
0,416
0,328
0,401
-0,326
att2
0,868
1,0
0,197
0,204
0,165
0,226
-0,142
att3
0,425
0,197
1,0
0,957
0,865
0,922
-0,872
att4
0,416
0,204
0,957
1,0
0,950
0,982
-0,885
att5
0,328
0,165
0,865
0,950
1,0
0,959
-0,899
att6
0,401
0,226
0,922
0,982
0,959
1,0
-0,853
att7
-0,326
-0,142
-0,872
-0,885
-0,899
-0,853
1,0
Tabuľka 4.5: Korelačná matica pôvodných CM
V tabuľke vidíme atribúty po aplikácii tohto operátora a môžme si všimnúť, že počet atribútov sa zredukoval zo 7 na 5 (tieto výsledky boli dosiahnuté
použitím CM a NB).
atr.
att2
att6
att3
att1
att4
att2
1,0
0,226
0,197
0,868
0,204
att6
0,260
1,0
0,922
0,401
0,982
att3
0,197
0,922
1,0
0,425
0,957
att1
0,868
0,401
0,425
1,0
0,416
att4
0,204
0,982
0,957
0,416
1,0
Tabuľka 4.6: Korelačná matica redukovaných CM
76
4.5. Experiment III
Úspešnosť klasifikácie s pôvodnými príznakmi bol 80, 35% a s redukovanými dokonca 86, 12%. To znamená, že eliminované atribúty boli dokonca pri
klasifikácii zavádzajúce. Výsledky pri klasifikácii ukazujú ešte jednu podstatnú
vec. Tým, že sú príznaky invariantné voči rotácii, nastáva tu problém s číslicami „6“ a „9“, ktoré sú identické po otočení o 180◦ . Pri klasifikácii NB bolo
totiž takmer 45% záznamov číslice „9“ klasifikovaných ako čislica „6“. Práve
podobnosť týchto dvoch tried zhoršovala celkovú úspešnosť tohto klasifikátora.
Na obrázku 4.9 je zobrazené rozloženie jednotlivých tried s odchýlkami od
strednej hodnoty podľa vyselektovaných atribútov. Môžme si všimnúť napríklad triedu číslice „1“ (modrá farba), ktorá je pomerne dobre separovateľná
od ostatných tried a to najmä atribútmi att2 a att1.
Obr. 4.9: Ukážka rozloženia tried a ich odchýlky pre CM
Podľa výsledkov prevedených experimentov môžme CM charakterizovať
ako príznaky s dobrou separačnou schopnosťou. Najväčším problémom boli už
spomínané triedy číslic „6“ a „9“. Aj napriek tomu sú tieto príznaky pomerne
stabilné, pretože so zmenou klasifikátora sa úspešnosť výrazne nemení. Veľkou
výhodou týchto príznakov je to, že je dostačujúce použiť len 5 atribútov k
dosiahnutiu úspešnosti presahujúcej hodnotu 85%. Možným a používaným
riešením prekryvu už spomínaných problémových tried je napríklad úprava
fontu tak, aby aj po otočení boli tieto číslice dostatočne odlišné.
Diskriminatívna schopnosť ZM
V tejto časti sme sa rozhodli popísať diskriminatívnu schopnosť ZM, keďže
výsledky prvotnej klasifikácie boli najlepšie práve v spojení s týmito príznakmi. Testovali sme ZM až rádu 8, takže príznakový vektor mal veľkosť
45 atribútov. Postupovali sme podobne ako pri skúmaní CM.
77
4. Experimentálna časť
V prvom rade sme použili operátor Forward Selection s modelom NB.
Podobne ako pri CM sa počet atribútov výrazne redukoval a táto redukcia
taktiež priniesla zlepšenie oproti použitiu kompletného príznakového vektora.
Počet atribútov bol redukovaný z pôvodných 45 na 14 a korelačná matica
redukovaných príznakov sa nachádza v prílohe, pod označením B.2. Pôvodná
úspešnosť s plným príznakovým vektorom bola 94, 71% a po redukcii ako v
predchádzajúcom prípade sa tiež zvýšila na 96, 00%.
Na obrázku 4.10 vidíme podobne ako pri CM zobrazené rozloženie tried.
Aj keď boli atribúty redukované, ich množstvo je ešte pomerne veľké a takéto
zobrazenie nie je veľmi prehľadné. Z tohto dôvodu sme sa rozhodli pre lepšiu vizualizáciu. Na redukované atribúty sme aplikovali ďalší operátor a to operátor
PCA. Ten zredukuje ich dimenzionalitu, pričom zachová varianciu atribútov.
Následne sme dáta zobrazili pomocou 3D-scatter plotu, ktorý môžeme vidieť
na obrázku 4.11. V ňom sú viditeľné jednotlivé zhluky objektov daných tried,
aj keď s istým prekryvom. Ak by bolo možné zobrazenie viacerých dimenzií
súčasne, zhluky by mali byť oddelené podstatne lepšie.
Obr. 4.10: Ukážka rozloženia tried a ich odchýlky pre ZM
V obrazových prílohách na obrázku B.2 sú zobrazené niektoré číslice, ktoré
boli klasifikáciou priradené do inej triedy ako je ich skutočná. Tieto chyby
vznikli za použitia NB.
78
4.5. Experiment III
Obr. 4.11: Zobrazenie zhlukov jednotlivých objektov prostredníctvom scatterplotu
79
4. Experimentálna časť
4.6
Experiment IV
Závislosť úspešnosti klasifikácie na uhle otočenia
V tomto experimente sme chceli poukázať na invarianciu CM a ZM voči
rotácii. V prvom kroku sme vytvorili viacero dátových setov, ktoré sme generovali otočením originálnych dát o rôzne uhly. Použili sme pôvodné separované
dáta a pre každý interval uhlov z nich vytvorili 850 nových, s 85 zástupcami pre každú z tried. Uhly otočení sa pohybovali v rozsahoch: h−30◦ , 30◦ i,
h−45◦ , 45◦ i, h−60◦ , 60◦ i, h−75◦ , 75◦ i, h−90◦ , 90◦ i, h−135◦ , 135◦ i a h−180◦ , 180◦ i.
Invarianciu sme testovali s klasifikátormi k-NN a NB.
Závislosť úspešnosti klasifikátora k-NN na uhle otočenia generovaných dát
100
Úspešnosť[%]
95
90
85
80
75
70
grid(49)
angles(48)
CM(7)
ZM8 (45)
0i
5i
0i
5i
0i
0, 3 45, 4 60, 6 75, 7 90, 9
3
−
h−
h−
h−
h−
h
h−
Uhly otočenia[◦ ]
i
35
5, 1
3
1
0
18
h−
0i
, 18
Obr. 4.12: Ukážka invariancie príznakov voči rotácii v spojení s k-NN
V grafe 4.12 môžeme sledovať citlivosť klasifikácie na zvyšujúci sa uhol otočenia jednotlivých číslic pri použití k-NN. Najcitlivejšie sa javia príznaky grid
a angles features, ako sme očakávali. Najvyššiu stabilitu vykazujú príznaky
CM, ktoré na zmenu uhlu takmer nereagujú. Podobný stav sme očakávali aj
od ZM, ale mierna citlivosť na zmenu uhla otočenia je spôsobená zámenou
číslic „6“ a „9“ pri vyšších uhloch.
Pri použití klasifikácie pomocou NB je citlivosť jednoduchých príznakov
ešte signifikantnejšia. CM a ZM vykazujú rovnako dobrú stabilitu ako pri
použití klasifikátora k-NN. To opäť svedčí o ich nezávislosti na použitom klasifikátore a o ich vhodnosti na použitie v takýchto prípadoch.
80
4.7. Automatická lokalizácia, separácia a klasifikácia identifikátora
Z testovaných príznakov charakterizujeme CM ako najlepšie príznaky schopné
invariancie voči rotácii, čo implikuje použitie v oblastiach, kde objekty s identifikátorom môžu byť ľubovoľne natočené voči snímacej technike. Ďalšou obrovskou výhodou CM je, že daný objekt je popísaný len 7 alebo 5 (v prípade
redukcie) príznakmi.
Závislosť úspešnosti Bayesovho klasifikátora na uhle otočenia generovaných dát
100
90
Úspešnosť[%]
80
70
60
50
40
30
grid(49)
angles(48)
CM(7)
ZM8 (45)
0i
5i
5i
0i
0i
0, 3 45, 4 60, 6 75, 7 90, 9
3
−
h−
h−
h−
h−
h
h−
i
35
5, 1
3
1
Uhly otočenia[◦ ]
h−
i
80
0, 1
8
1
Obr. 4.13: Ukážka invariancie príznakov voči rotácii v spojení s NB
4.7
Automatická lokalizácia, separácia a
klasifikácia identifikátora
Ako sme spomenuli v úvode tejto kapitoly, pokúsili sme sa dokonca aj o automatickú lokalizáciu, separáciu číslic s následnou extrakciou príznakov a rozpoznávaním. V tejto podkapitole uvedieme dosiahnuté výsledky a porovnanie
s tými predchádzajúcimi a hlavne poukážeme na úskalia takejto automatizácie.
Na obrázku 4.14 je ukážka lokalizácie identifikátora na pôvodnom obrázku.
Na jeho lokalizáciu sme využili postup popísaný v 4.1.2.1.
81
4. Experimentálna časť
Obr. 4.14: Ukážka lokalizovaného identifikátora na snímke vzorky s razeným
identifikátorom
V obrazovej prílohe (obr. B.1) je ukážka nesprávnej lokalizácie identifkátora. Lokalizáciu ovplyvnil šum, ktorý sa nachádza nad identifikátorom a
pretože má podobné vlastnosti ako samotný identifikátor, zvolené predspracovanie ho nedokázalo eliminovať.
Následnej separácii jednotlivých číslic z lokalizovaného identifikátora, ktorú
sme popísali v 4.1.2.2, predchádzala ešte úprava pomocou Houghovej tranformácie na korekciu uhla z dôvodu, že niektoré z obrázkov boli mierne pootočené. Zachovaním tohto otočenia by separácia pomocou navrhnutej metódy
nemusela pracovať správne.
Na obrázku 4.15a môžeme vidieť obrázok lokalizovaného identifikátora,
ktorý bol značne upravený. Podstata úpravy spočívala v tom, aby sa lokalizovaný identifikátor akoby „zlial“ do jedného celku a tak vytvoril akúsi oblasť
(použitie priemerovacieho filtra s veľkosťou 11 × 11 a následnej morfologickej operácie remove, ktorá zachová z objektu len jeho hranice). Horizontálne
hranice tohto objektu teda určujú uhol, ktorým je obrázok pootočený od horizontálnej osi. Pomocou Houghovej transformácie sme schopní túto líniu získať
82
4.7. Automatická lokalizácia, separácia a klasifikácia identifikátora
a zistiť uhol pootočenia. Po zistení tohto uhla pomocou operácie imrotate
otočíme pôvodný obrázok a opäť obraz predspracujeme a identifikátor znovu
lokalizujeme.
(a)
(b)
Obr. 4.15: Ukážka výpočtu dominantnej línie pomocou Houghovej transformácie (a) a následná oprava pootočenia obrazu (b)
Ďalším krokom je už samotná separácia a možnosť výpočtu príznakov.
Pre samotnú klasifikáciu sme sa rozhodli použiť ZM8 ako príznaky a k-NN
klasifikátor, keďže spoločne dosahovali najlepšie výsledky v predchádzjúcich
experimentoch. Predpokladáme, že najväčším rozdielom v celkovej klasifikácii
oproti predvedeným experimentom bude hlavne chybná separácia jednotlivých
číslic a rozdiel trénovacej množiny. Tú musíme zvoliť len z reálnych dát a keďže
niektorých číslic je v poskytnutých dátach veľmi nízky počet, i trénovacia
množina bude podstatne menšia ako pri experimentoch s umelými dátami.
Trénovaciu množiu sme vytvorili z 10 obrázkov, takže na klasifikáciu ostalo
zvyšných 32, v ktorých sa nachádza 249 číslic:
číslica
1
2
3
4
5
6
7
8
9
0
train.
20
8
12
2
14
3
8
1
7
2
test.
63
30
36
7
53
7
27
2
20
4
Tabuľka 4.7: Počty jednotlivých číslic v trénovacej a testovacej množine
V prostredí nástroja Matlab sme zo separovaných číslic trénovacej množiny extrahovali zvolené príznaky a uložili ich v osobitnom súbore. Následne
sme mohli pristúpiť ku klasifikácii. V tomto nástroji je dostupná implementácia klasifikátora k-NN takže bolo potrebné už len extrahovať príznaky zo
separovaných číslic z obrázkov testovacej množiny. Tie sme extrahovali rovnakým spôsobom ako pri trénovacej množine a implementovanému klasifikátoru
83
4. Experimentálna časť
poskytli trénovacie dáta z osobitného súboru a získané príznaky z aktuálneho
obrázku. Ten sa na základe jedného najbližšieho suseda rozhodol, do ktorej
triedy priradí danú číslicu. Výsledok klasifikácie bol pre každý obrázok vypísaný v príkazovom riadku tohto nástroja. Ako sme predpokladali, stretli
sme sa s problémom zlej separácie číslic. Ukážky nesprávnej separácie sú na
obrázku 4.16.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
Obr. 4.16: Ukážky nesprávnej separácie číslic, (a),(c),(d) - neoddelenie čislic,
(b) - ponechanie šumu, (e),(f) - rozdelenie číslice, (g) - ovplyvnenie šumom
Aj napriek tomuto problému klasifikácia dopadla pomerne úspešne. Ako
sme spomenuli, jednotlivých číslic v testovacej množine bolo 249. Separáciou
sme získali 251 obrázkov, z ktorých 16 sme klasifikovali ako nesprávne separované (napríklad rozdelenie číslice na viac dielov, ponechanie šumu ako relevantnej číslice a podobne). Zo zvyšných 235 bolo 229 klasifikovaných správne
a len 6 obrázkov, ktoré boli správne odseparované, bolo klasifikovaných zle.
Kvôli nesprávnosti separácie nevieme teda určiť presnú úspešnosť, keďže sme
priradili do tried aj objekty, ktoré neboli číslicami, alebo sme niektoré separáty označili za nerelevantné, aj keď obsahovali číslicu. Významným faktorom
pri takejto klasifikácii bola aj veľkosť trénovacej množiny, ktorá by v reálnych
podmienkach bola omnoho väčšia.
Týmto experimentom sme potvrdili možnosť automatizácie procesu identifikácie metalurgických vzoriek a správnosť zvolených predspracovacích techník
a metód extrakcie príznakov či klasifikácie.
4.8
Spracovanie a identifikácia vzoriek s farebným
náterom
V tejto časti sa len okrajovo zameriame na vzorky značené farebným náterom
a ukážeme na možnosti predspracovania so snahou dosiahnuť stav ako pri
vzorkách značených razeným identifikátorom.
84
4.8. Spracovanie a identifikácia vzoriek s farebným náterom
V prípade tohto značenia disponujeme veľmi nízkym množstvom dát, takže
následná klasifikácia nebude popísaná, keďže by väčšina dát bola umelo vygenerovaná. Výsledkom tejto kapitoly bude teda len konštatovanie toho, či je
možné takto značené dáta pripraviť k extrakcii príznakov s podobným výsledkom ako pri vzorkách značených razeným identifikátorom. Následná klasifikácia by sa v takomto prípade nelíšila od tej použitej v predchádzajúcej
kapitole.
4.8.1
Porozumenie problému a dátam
Podobne ako pri vzorkách značených razeným identifkátorom je našou úlohou navrhnúť postup metód predspracovania, ktorého výsledkom budú obrazy jednotlivých znakov vo forme podobnej ako v predchádzajúcich častiach.
Identifikátor je tiež zložený len z číslic, neobsahuje teda žiadne iné znaky ani
interpunkciu. Použitý font sa líši od fontu použitého pri razených identifikátoroch. Na obrázku 4.17 je zobrazená ukážka takého identifikátora. Je vidieť, že
časti identifikátora nie sú označené veľmi precízne a že predspracovanie bude
musieť byť dostatočne robustné.
Obr. 4.17: Ukážka vzorky s farbeným identifikátorom
85
4. Experimentálna časť
4.8.2
Predspracovanie
Ako sme uviedli v úvode tejto kapitoly, značenie dát nie je veľmi kvalitné.
Jednotlivé číslice sú pomerne slabo viditeľné a obsahujú určité defekty ako sú
nespojitosť celého objektu a podobne (viď obrázok 4.17 a napríklad číslice „2“
a „3“). Hlavne z dôvodu malého rozdielu medzi pozadím a identifikátorom sme
sa rozhodli použiť techniky na vyrovnanie kontrastu obrazu. Použili sme dve
techniky podporované nástrojom Matlab a to funkcie imadjust a histeq. Prvá
z uvedených vyrovnáva hodnoty intenzít v obraze tak, aby pokryli celú šírku
intenzitného histogramu v rozsahu h0, 255i. Druhá technika je založená na
ekvalizácii histogramu, čo má za následok opäť vylepšenie kontrastu v obraze.
U všetkých pokusov o čo najlepšie predspracovanie, bolo prvým krokom práve
vylepšenie kontrastu. Kvalitu predspracovania sme hodnotili len z vizuálnej
stránky a snažili sa dosiahnuť stav, ako pri razenom identifikátore. Na obrázku
4.18 sú zobrazené ukážky predspracovaní.
Obr. 4.18: Rôzne postupy predspracovania vzoriek s farebným identifikátorom
Ako najlepší postup predspracovania u takto značených vzoriek sme vy86
4.8. Spracovanie a identifikácia vzoriek s farebným náterom
brali posledný z uvedených na obrázku 4.18. Tento postup je veľmi jednoduchý
a je realizovaný v 5 krokoch.
1. Vylepšenie kontrastu funkciou imadjust.
2. Aplikácia pomerne veľkého Gaussovského filtra (15 × 15, σ = 3).
3. Použitie automatického thresholdingu.
4. Následné použitie mediánového filtra (11 × 11), ktorého použitie zabezpečilo vyhladenie hraníc objektov.
5. Odstránenie objektov, ktoré obsahovali menej ako 30px.
Na obrázku 4.19 je ukážka použitia operácie thin na vytvorenie kostry
objektov zo zvoleného predspracovaného obrázku. Na tomto obrázku môžeme
ďalej vidieť ukážky kostier číslic, ktoré boli vytvorené zo vzoriek značených
razeným identifikátorom. Na základe vizuálneho porovnania môžeme skonštatovať, že takto pripravené dáta značené farebným náterom by bolo možné
následne použiť na dodatočné predspracovanie, extrakciu príznakov a klasifikáciu podobne ako v experimentoch I,II,III,IV.
Obr. 4.19: Ukážka porovnania výsledkov predspracovania u razeného a farbeného identifikátoru
Z dôvodu absencie použiteľného množstva dát sme nepristúpili k samotnej klasifikácii, ale na základe experimentov s predspracovacími technikami
môžme konštatovať, že takto značené vzorky je možné automaticky identifikovať na základe úpravy identifikátora značeného farbou podobne ako razeného.
87
Záver
V tejto diplomovej práci som zvolenými postupmi dokázal overiť a potvrdiť
skutočnosť, že rozpoznávanie razených a farbených identifikátorov je možné
uskutočniť v reálnych podmienkach. Navrhnuté postupy som implementoval
a následne overil ich funkčnosť na sade reálnych dát poskytnutých spoločnosťou KMC GROUP s.r.o. Z výsledkov experimentov na reálnych alebo
pomocných, vygenerovaných dátach môžem povedať, že razený identifikátor
je omnoho kvalitnejší, čo sa týka viditeľnosti a presnosti označenia a tento
spôsob značenia vzoriek by som doporučil ako primárny. Značenie vzoriek farebným náterom je menej precízne a prípadný problém môže vzniknúť pri
zámene farby náteru, ktorá môže mať značný vplyv na pripravený postup aplikácie predspracovacích metód. Tento spôsob značenia je určite tiež menej
odolný voči obtretiu alebo poškodeniu náteru, čo pri razenom identifikátore
nehrozí v takej miere.
V práci bol dôraz kladený najmä na predspracovacie techniky a extrakciu
a analýzu príznakov, pretože správne zvolené príznaky extrahované z kvalitne
prispôsobených dát by mali zaručiť úspech bez nutnosti použitia konkrétnej
klasifikačnej metódy. O tejto skutočnosti som sa presvedčil aj v experimentoch.
Na ich základe odporúčam použiť príznaky CM alebo ZM, ktoré dosahovali
úspešnosť pohybujúcu sa okolo 99%. Výborné výsledky by mala dosahovať aj
kombinácia týchto dvoch typov príznakov. Výhodou použitia práve príznakov
CM a ZM je ich invariancia, ktorá umožňuje rozpoznávať aj číslice otočené
v rozsahu uhlov h0◦ , 360◦ i s viac ako 90% úspešnosťou. Prednosťou príznakov ZM bola schopnosť rozpoznať číslice „6“ a „9“ a príznaky CM výborne
reagovali na otáčanie číslic. Po úprave separácie tak, aby bola schopná odseparovať i pootočené číslice, by tak bolo možné snímať identifikačné známky pod
ľubovoľným uhlom. Spojenie týchto dvoch typov by teda zaručovalo vysokú
úspešnosť klasifikácie i schopnosť jednoduchého odoberania snímkov vzoriek,
keďže vieme, že metalurgické vzorky môžu byť rôznej veľkosti a hlavne hmotnosti, ktorá bráni jednoduchej manipulácii s nimi.
Pri experimentoch sme boli značne limitovaný počtom dostupných dát.
Hlavne pri automatickom rozpoznávaní bola trénovacia množina veľmi malá.
Pri vytvorení dostatočne veľkej trénovacej množiny a natrénovaní zvoleného
klasifikátora na extrahované príznaky by sa celková úspešnosť mohla ešte zvýšiť. Samozrejme vo výslednej aplikácii by bolo nutné upraviť automatickú
89
Záver
lokalizáciu a separáciu identifikátora, ktoré tiež spôsobovali určitú chybu následnej klasifikácie.
V konečnom dôsledku môžem skonštatovať, že postupy popísané v experimentálnej časti tejto práce je možné s úpravami použiť na reálne automatické
rozpoznávanie vzoriek v metalurgickom priemysle.
90
Literatúra
[1]
Bishop, J. M.; Mitchell, R. J.: Neural networks - an introduction. 1991,
s. 1–3.
[2]
Duda, R. O.; Hart, P. E.; Stork, D. G.: Pattern Classification. John Wiley
& Sons, Inc., druhé vydanie, 2001, ISBN 0-471-05669-3.
[3]
Flusser, J.; Suk, T.; Zitová, B.: Moments and Moments Invariants in
Pattern Recognition. John Wiley & Sons Ltd, prvé vydanie, 2009, ISBN
978-0-470-69987-4.
[4]
Gonzalez, R. C.; Woods, R. E.: Digital Image Processing. Pearson Education, Inc., tretie vydanie, 2008, ISBN 978-0-13-168728-8.
[5]
Hoare, Z.: Naive Bayes classifier: True and estimated errors for 2-class,
2-features case. Published in 3rd IEEE Conference Intelligent Systems,
2006: s. 566–570.
[6]
Mitra, S. K.; Sicuranza, G. L.: Nonlinear Image Processing. Academic
Press, prvé vydanie, 2001, ISBN 0-12-500451-6.
[7]
Paris, S.; Kornprobst, P.; Tumblin, J.; a i.: A Gentle Introduction to
Bilateral Filtering and its Applications.
[8]
Pattanasethanon, P.; Attachoo, B.: A Unified Histogram and Laplacian
Based for Image Sharpening. IEEE, 2009: s. 1125–1130.
[9]
Ralević, N. M.; Dražić, S.; Obradović, R.: The Hough Transformation of
Rectangle. Published by the IEEE, 2008.
[10] Singh, C.; Walia, E.; Mittal, N.: Rotation invariant complex Zernike moments features and their applications to human face and character recognition. Published in IET Computer Vision, ročník 5, 2010: s. 255–266.
[11] Vajda, F.: Techniques and trends in digital image processing and computer vision (summary). Printed and published by the IEE, Savoy Place,
London, UK, 1994.
91
Literatúra
[12] Wang, W.: License Plate Recognition Algorithm Based on Radial Basis
Function Neural Networks. 2009, s. 1–3.
[13] Wijetunge, A.; Ratnaweera, D.: Real-Time Recognition of License Plates
of Moving Vehicles in Sri Lanka. 2011.
[14] Šprogar, M.; Kokol, P.; Zorman, M.; a i.: Evolving Groups of Basic Decision Trees. Published by the IEEE, 2001: s. 183–188.
92
DODATOK
Zoznam použitých skratiek a
symbolov
a
skalárna veličina
a
vektorová veličina
A
množina
f (x, y)
vstupný obrázok
g(x, y)
výstupný obrázok
NB
klasifikátor Naive-Bayes
MSE
mean-square error
CM
centrálne momenty
ZM
Zernikeho momenty
k-NN
k - nearest neighbor - klasifikátor k najbližších susedov
DT
decision tree(s) - rozhodovací/rozhodovacie strom/stromy
NN
neural network - neurónová sieť
93
A
DODATOK
Obrazové prílohy a vzniknuté
materiály
Obr. B.1: Ukážka nepresne lokalizovaného identifikátora s posunom kvôli šumu
95
B
B. Obrazové prílohy a vzniknuté materiály
grid(49)
angles(48)
CM(7)
ZM8 (45)
1-NN
Bayes
1-NN
Bayes
1-NN
Bayes
1-NN
Bayes
±30◦
99,29%
73,41%
95,18%
79,65%
87,76%
77,29%
99,65%
96,35%
◦
97,29%
76,00%
93,88%
71,41%
85,18%
80,82%
98,82%
94,12%
◦
±60
97,41%
63,29%
90,94%
60,12%
87,88%
78,71%
99,06%
94,47%
±75◦
96,94%
64,59%
88,24%
55,65%
87,29%
76,12%
99,18%
91,53%
◦
96,00%
50,47%
86,12%
51,65%
92,82%
82,24%
98,59%
90,59%
±135
◦
90,24%
49,88%
78,00%
39,76%
88,24%
86,82%
94,71%
87,06%
±180
◦
88,12%
41,53%
74,00%
31,76%
87,65%
80,47%
91,65%
82,12%
±45
±90
Tabuľka B.1: Tabuľka zobrazujúca úspešnosť klasifikácie pri rôznych uhloch
otočenia generovaných dát
1-4
2-6
3-7
3-7
4-7
5-4
5-4
6-4
6-7
9-3
9-4
9-2
Obr. B.2: Ukážka nesprávne klasifikovaných číslic (popis: label-prediction)
ZM7 + NB
96
Obr. B.3: Ukážka fontu ID8400
97
att9
1,0
-0,253
0,162
-0,046
-0,046
0,178
0,051
-0,336
0,032
0,176
0,275
-0,896
-0,171
0,184
atr.
att9
98
att5
att2
att1
att14
att7
att38
att33
att24
att42
att36
att3
att44
att28
-0,210
0,192
0,177
-0,247
-0,270
-0,164
0,097
-0,109
-0,254
0,015
-0,510
-0,415
1,0
-0,253
att5
-0,051
-0,042
0,059
0,117
-0,193
0,081
0,102
0,059
-0,006
0,121
1,0
0,235
-0,510
-0,046
att1
0,302
-0,403
-0,026
0,044
-0,006
-0,131
-0,055
0,177
0,045
1,0
0,121
0,170
0,015
-0,046
att14
0,110
-0,096
-0,146
0,163
0,115
-0,071
-0,187
0,337
1,0
0,045
-0,006
0,693
-0,254
0,178
att7
-0,025
-0,005
-0,031
0,275
-0,008
-0,214
-0,250
1,0
0,337
0,177
0,059
0,379
-0,109
0,051
att38
-0,031
-0,004
0,255
-0,382
-0,163
0,041
1,0
-0,250
-0,187
-0,055
0,102
-0,103
0,097
-0,336
att33
0,005
-0,013
-0,006
0,049
0,194
1,0
0,041
-0,214
-0,071
-0,131
0,081
0,102
-0,164
0,032
att24
0,199
-0,071
-0,125
0,248
1,0
0,194
-0,163
-0,008
0,115
-0,006
-0,193
0,080
-0,270
0,176
att42
Tabuľka B.2: Korelačná matica redukovaných príznakov ZM8
-0,023
-0,009
-0,128
0,188
0,080
0,102
-0,103
0,379
0,693
0,170
0,235
1,0
-0,415
0,162
att2
0,097
-0,082
0,021
1,0
0,248
0,049
-0,382
0,275
0,163
0,044
0,117
0,188
-0,247
0,275
att36
-0,136
0,144
1,0
0,021
-0,125
-0,006
0,255
-0,031
-0,146
-0,026
0,059
-0,128
0,177
-0,896
att3
-0,952
1,0
0,144
-0,082
-0,071
-0,013
-0,004
-0,005
-0,096
-0,403
-0,042
-0,009
0,192
-0,171
att44
1,0
-0,952
-0,136
0,097
0,199
0,005
-0,031
-0,025
0,110
0,302
-0,051
-0,023
-0,210
0,184
att28
B. Obrazové prílohy a vzniknuté materiály
Vzniknuté materiály
Matlab
• angle_adaptation - funkcia na opravu rotácie obrazu
• automatic_classification - skript uskutočňujúci automatické rozpoznávanie
• border_deleting - automatické orezanie prázdnych okrajov
• central_moment - funkcia na výpočet CM
• color1 - predspracovací postup farebne značených vzoriek č.1
• color2 - predspracovací postup farebne značených vzoriek č.2
• color3 - predspracovací postup farebne značených vzoriek č.3
• color4 - predspracovací postup farebne značených vzoriek č.4
• count_distance - funkcia na výpočet vzdialeností z x-ových súradníc
bodov
• create_feature_matrix - skript vytvárajúci .csv súbor s požadovanými
príznakmi
• distance_outliers - funkcia na vyhľadanie a vymazanie outlierov na
základe vzdialenosti
• feature_extraction_angles - funkcia na predpripravenie a extrakciu
príznakov angles features
• feature_extraction_CM - funkcia na predpripravenie a extrakciu CM
• feature_extraction_grid - funkcia na predpripravenie a extrakciu
grid features
• feature_extraction_ZM - funkcia na predpripravenie a extrakciu ZM
• gen_data - skript na generovanie umelých dát
• localization - automatická lokalizácia identifikátora
• moment - výpočet jednoduchého momentu
• ni - výpočet normalizovaného momentu
• number_separation - automatická separácia častí identifikátora
99
B. Obrazové prílohy a vzniknuté materiály
• outlier_detection - vyhľadanie outlierov v obrazových dátach na základe vzdialeností
• plot_lines - funkcia vizualizácie miesta lokalizovaného identifikátora
• preprocess - predspracovanie pôvodného obrazu
• Bilateral Filtering - bilaterálny filter; autor: Douglas Lanman
• Max-Min Filter - max a min filter; autor: Frederico D’Almeida
• Zernike - výpočet ZM (The MathWorks)
RapidMiner
• performance - proces klasifikácie pre rôzne príznaky a klasifikátory (pre
zmenu príznakov je nutné upraviť načítanie .csv súboru; prípadne v Xvalidation zmeniť klasifikačný model)
• kNN_loop - proces na zistenie najlepšieho k
• attribute_selection - proces selekcie významných atribútov
• correlation_matrices - proces na vytvorenie korelačných matíc pôvodných a redukovaných príznakov
• information_gain - proces hodnotenia významnosti atribútov
100
DODATOK
Obsah priloženého CD
cd
documents ... Táto zložka obsahuje patričné dokumenty
(elektronická verzia DP).
Mthesis_source_codes ... Táto zložka obsahuje zdrojové súbory DP
(šablóna, zdrojový kód použitej literatúry,
časti DP a použité obrázky).
latex_source_codes
tikz_source_codes
pictures
matlab_source_codes ... Táto zložka obsahuje skripty a funkcie vytvorené v nástroji Matlab.
rapidMiner_processes ... Táto zložka obsahuje procesy vytvorené v
nástroji RapidMiner.
raw_data ... Táto zložka obsahuje pôvodné dáta poskytnuté spoločnosťou KMC GROUP
s.r.o.
pin_marked
color_marked
preprocessed_data ... Táto zložka obsahuje predspracované dáta
(generované, pootočené a pod.).
pin_marked
color_marked
features ... Táto zložka obsahuje súbory s extrahovanými príznakmi použitými v experimentoch práce.
101
C
Download

článok