Application of pattern recognition methods in classification of different types of rocks

Akademia Gorniczo-Hutnicza
im. Stanisawa Staszica
Wydzia Geologii, Geofizyki
i Ochrony rodowiska
Al. Mickiewicza 30
30-059 Krakow


PRACA MAGISTERSKA

IMI I NAZWISKO DYPLOMANTA: Andrzej Gorszczyk
NR ALBUMU: 212170
KIERUNEK I SPECJALNO: Informatyka Stosowana,
Modelowanie i Systemy Informatyczne w Geofizyce
JEDNOSTKA DYPLOMUJCA: Katedra Geoinformatyki i Informatyki Stosowanej
TYTUL PRACY (wersja polska): Zastosowanie metod rozpoznawania obrazow
do klasyfikacji wybranych typow ska.
TYTUL PRACY (wersja angielska): Application of pattern recognition methods
in classification of different types of rocks.
PROMOTOR: dr hab. in. Mariusz Mynarczuk, prof. AGH
RECENZENT: dr in. Adam Piorkowski
LICZBA: stron pracy: 61 figur: 52
tabel: 3
pozycji literatury: 10
ZALCZNIKI: -
Ocena punktowa pracy magisterskiej
Recenzenta: .....................................
Promotora: ......................................
Lczna ocena punktowa recenzenta i promotora: .....................................
Lczna ocena liczbowa i sowna: ............................................................
Skala ocen (wg regulaminu studiow AGH, par.13, p.1)
Liczba punktow Ocena liczbowa i sowna
91 - 100.....................5.0 (bardzo dobry)
81 - 90......................4.5 (plus dobry)
71 - 80......................4.0 (dobry)
61 - 70......................3.5 (plus dostateczny)
50 - 60......................3.0 (dostateczny)
<50......................2.0 (niedostateczny) ............................................................
Przewodniczcy Komisji Egzaminacyjnej

Krakow 25.06.2012

---

STRESZCZENIE PRACY
Dynamiczny rozwoj sztucznej inteligencji znajduje odzwierciedlenie w coraz szerszym
wykorzystywaniu jej technik. Badania i projekty prowadzone w dziedzinach takich jak
medycyna, robotyka, biometryka, wojskowo, systemy diagnostyczne i wizyjne oraz wiele
innych w znacznej czci opieraj si dzisiaj na zautomatyzowanych procesach, ktore
bazuj na komputerowym rozpoznawaniu obrazow. Tendencja ta potwierdza si take dla
bada powizanych z szeroko pojt geologi, gdzie w poczeniu z algorytmami
przetwarzania i analizy obrazu, rozpoznawanie obrazow stanowi przydatne narzdzie
klasyfikacji oraz opisu struktur skalnych. Niniejsza praca prezentuje sposob w jaki
wspomniane techniki mog zosta wykorzystane do rozpoznawania wybranych typow ska
na podstawie ich zdj mikroskopowych. Autor zestawi w pracy porownanie skutecznoci
dziaania piciu metod rozpoznawania obrazow w zalenoci od kadej z dziewiciu
wybranych ska, ktorych zdjcia przetwarzane byy w czterech przestrzeniach barw.
Najlepsze zestawienie metody NN i przestrzeni barw CIELab dao wynik prawidowych
klasyfikacji rowny 99,81% co dowodzi skutecznoci dziaania rozpoznawania obrazow dla
postawionego problemu i moe prowadzi do prac nad bardziej skomplikowanymi
problemami z podobnego zakresu.
Sowa kluczowe
rozpoznawanie obrazow, analiza obrazow, przestrzenie barw, klasyfikacja ska,


ABSTRACT
The dynamic development of artificial intelligence is reflected by the increased use of its
techniques. Research and projects in areas such as medicine, robotics, biometrics, military,
diagnostic systems and many others for the most part now rely on automated processes,
which are based on computer pattern recognition. This trend is also confirmed for studies
related to the wider geology, where in conjunction with image processing algorithms and
image analysis, pattern recognition is a useful tool for classification and description of rock
structures. This paper shows how these techniques can be used to identify some types of
rocks based on their microscopic images. The author compiled the work to compare the
effectiveness of five methods of pattern recognition based on each of the nine selected
rocks, whose images were processed in four color spaces. The best summary of the method
of NN and CIELab color space gave a result equal to the correct classification of 99.81%
which demonstrates the effectiveness of pattern recognition to the shown issue and can
lead to work on more complex problems of a similar scope.
Key words
pattern recognition, image analysis, color spaces, rocks classification

2

---

Miejsce odbywania praktyki dyplomowej:
Instytut Mechaniki Gorotworu PAN, Krakowie,
Katedra Geoinformatyki i Informatyki Stosowanej, Wydzia Geologii
Geofizyki i Ochrony rodowiska, AGH , Krakow
Program praktyki dyplomowej:
1. Wybor i przygotowanie materiau do bada.
2. Wykonanie zdj mikroskopowych.
3. Przegld literatury wykorzystanej do realizacji projektu.
4. Opracowanie i implementacja algorytmow przetwarzania i rozpoznawania.

OWIADCZENIE AUTORA PRACY

Owiadczam, wiadomy odpowiedzialnoci karnej za powiadczenie nieprawdy,
e niniejsz prace dyplomow wykonaem osobicie i samodzielnie, i nie korzystaem
ze rode innych ni wymienione w pracy.
Owiadczam rownie, e przedstawiona praca nie bya wczeniej przedmiotem
procedur zwizanych z uzyskaniem tytuu zawodowego w wyszej uczelni i jest identyczna z
zaczon wersj elektroniczn. Ponadto przyjmuj do wiadomoci, e praca dyplomowa lub
jej cz moe by opublikowana jedynie po uzyskaniu pisemnej zgody promotora.


........................... ......................................................
Data Podpis Autora





JEDNOSTKA DYPLOMUJCA



........................................................................

3

---

FORMULARZ OCENY PUNKTOWEJ PRACY MAGISTERSKIEJ
Oceniany element pracy
Ocena
Ocena
Suma ocen
recenzenta promotora
I. ZAWARTO MERYTORYCZNA [0 - 40 pkt]
1. Zgodno treci pracy z jej tytuem.



[0 - 3 pkt]
2. Literatura (poprawno opracowania wykazu literatury,
kompletno danych bibliograficznych, poprawno cytowa)



[0 - 3 pkt]
3. Umiejtno sformuowania problemu badawczego i sposobu
jego rozwizania (samodzielno i inicjatywa badawcza,


umiejtno opisu materiaow podstawowych i historii bada)
[0 - 8 pkt]
4. Metodyka bada (dobor waciwych metod badawczych i
umiejtno ich zastosowania)



[0 - 8 pkt]
5. Dyskusja wynikow bada i wnioski (logiczno wywodow,
poprawno i krytyczna analiza wynikow bada, znaczenie
naukowe i praktyczne, w jakim stopniu uzyskane wyniki s


wasnoci intelektualn magistranta)
[0 - 15 pkt]
6. Czy po dostosowaniu do wymogow redakcyjnych do publikacji
nadaje si: caa praca [3 pkt], wybrane rozdziay [2 pkt],
wybrane elementy pracy w formie komunikatu naukowego


[1 pkt], brak moliwoci [0 pkt]
[0 - 3 pkt]
Zawarto merytoryczna cznie



II. STRONA EDYTORSKA [0 - 10 pkt]
1. Poprawno skadniowa, gramatyczna i ortograficzna pracy,
staranno korekty tekstu.



[0 - 5 pkt]
2. Kompletno i poprawno rysunkow, tabel i zacznikow



[0 - 3 pkt]
3. Estetyka pracy


[0 - 2 pkt]

Strona edytorska cznie







LCZNA OCENA PUNKTOWA PRACY

........................... ......................................................
Data Podpis Recenzenta


........................... ......................................................
Data Podpis Promotora


4

---

OCENA OPISOWA PRACY
RECENZENT
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
......................................................
Podpis Recenzenta

PROMOTOR
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
......................................................
Podpis Promotora




5

---

Spis treci
1. Wprowadzenie ............................................................................. 8
1.1. Zadanie rozpoznawania .............................................................................. 8
1.2. Przetwarzanie i analiza obrazow .............................................................. 10
1.3. Cel projektu .............................................................................................. 11
2. Rozpoznawanie obrazow ........................................................... 13
2.1. Elementy skadowe rozpoznawania obrazow............................................ 13
2.1.1. Recepcja i przestrze cech ..................................................................... 14
2.1.2. Cig uczcy .......................................................................................... 15
2.1.3. Funkcje przynalenoci .......................................................................... 16
2.1.4. Podejmowanie decyzji ............................................................................ 18
2.2. Metody rozpoznawania obrazow .............................................................. 18
2.2.1. Metody minimalnoodlegociowe.............................................................. 19
2.2.1.1. Metoda najbliszego ssiada ................................................................... 20
2.2.1.2. Metoda alfa najbliszych ssiadow. .......................................................... 21
2.2.2. Metody wzorcow ................................................................................... 23
2.2.2.1. Metoda jednakowych i optymalnych otocze kulistych ................................ 23
2.2.2.2. Metoda najbliszej mody ........................................................................ 25
3. Analiza obrazu. .......................................................................... 27
3.1. Obraz i jego akwizycja. ............................................................................ 27
3.2. Barwa i model barwy ................................................................................ 28
3.2.1. Model RGB ........................................................................................... 29
3.2.2. Model YIQ ............................................................................................ 29
3.2.3. Model HSV ........................................................................................... 30
3.2.4. Model CIELab ........................................................................................ 31
3.3. Przeksztacenia obrazu - przeksztacenia morfologiczne ......................... 32
3.3.1. Element strukturalny ............................................................................. 33
3.3.2. Erozja i dylatacja .................................................................................. 34
3.3.3. Gradient morfologiczny .......................................................................... 34
3.4. Pomiary automatyczne ............................................................................. 34
4. Przebieg bada .......................................................................... 36
4.1. Proces przygotowania materiau badawczego .......................................... 36
4.2. Wybrane skay .......................................................................................... 36
4.3. Akwizycja zdj ........................................................................................ 39
4.4. Oprogramowanie problemu ...................................................................... 40
5. Prezentacja wynikow ................................................................. 42
5.1. Analiza rozkadu cech w przestrzeni jako jeden ze sposobow optymalizacji
metod rozpoznawania ....................................................................................... 42

6

---

5.2. Analiza skutecznoci metod rozpoznawania w zalenoci od przestrzeni
barw......................................................................................................................46
5.2.1. Prawidowe klasyfikacje .......................................................................... 46
5.2.2. Bdne klasyfikacje ................................................................................ 47
5.2.3. Braki klasyfikacji. .................................................................................. 48
5.2.4. Podsumowanie prawidowych rozwiza ................................................... 49
5.3. Analiza
skutecznoci
metod
rozpoznawania
w
zalenoci
od
rozpoznawanego materiau ............................................................................... 50
5.3.1. Prawidowe klasyfikacje .......................................................................... 50
5.3.2. Bdne klasyfikacje ................................................................................ 51
5.3.3. Braki klasyfikacji ................................................................................... 52
5.3.4. Wraliwo na zmiany cigu uczcego...................................................... 53
5.3.5. Podsumowanie prawidowych rozwiza ................................................... 55
5.3.6. Wpyw parametru na ilo prawidowych klasyfikacji metody NN ............. 56
5.4. Analiza bdnych klasyfikacji w zalenoci od metody rozpoznawania ..... 56
6. Podsumowanie i wnioski ........................................................... 59
7. Bibliografia ................................................................................ 61




7

---

1. Wprowadzenie
1.1. Zadanie rozpoznawania
Badania prowadzone nad rozwojem rozpoznawania obrazow znajduj swoje
odzwierciedlenie w szerokim zastosowaniu jakie do tej pory zyskaa i nadal zyskuje ta ga
sztucznej inteligencji. Coraz wicej zada pojawiajcych si podczas prac nad ronego
rodzaju projektami, ktore do niedawna wizay si bezwarunkowo z podejmowaniem decyzji
przez czowieka, zostaje zautomatyzowanych dziki rozwizaniom dostarczanym przez
szeroko pojte systemy informatyczne, a w szczegolnoci m.in. dziki rozpoznawaniu
obrazow. Tendencja do automatyzowania zada wynika niejako z zaoe stojcych
u podstaw tej dziedziny. Zasadnicz ide sztucznej inteligencji jest uzyskanie dziaania
maszyny podobnego do tego jakie realizuje czowiek, w szczegolnoci za zaoeniem teorii
rozpoznawania obrazow jest nauczenie maszyny umiejtnoci klasyfikowania obiektow
do pewnych wydzielonych klas, czyli rozpoznawania ich. Nie sposob nie zgodzi si zatem
ze stwierdzeniem, e zagadnienia rozpoznawania s kluczowymi dla rozwoju sztucznej
inteligencji.
Nazwa rozpoznawanie obrazow odruchowo nasuwa nam na myl jedynie analizowanie
ronego rodzaju obrazow - zdj. Mimo, i w kontekcie niniejszego projektu, gdzie analizie
poddajemy pewne zdjcia ska, jest ona trafna, naley j doprecyzowa jeli chodzi
o caociowe ujcie zakresu tematycznego dziedziny rozpoznawania. Trzeba zatem w tym
miejscu zaznaczy, e mowic o rozpoznawanym obrazie odnosimy si do niemal dowolnego
typu obiektu. Dla lepszego zobrazowania zagadnienia warto przytoczy cytat z ksiki
Tadeusiewicza i Flasiskiego [6]:
(...)opis dziaanie hydrauliki podwozia moe by traktowany jako obiekt w zadaniu,
w ktorym obrazami s decyzje o dopuszczeniu samolotu do kolejnego startu
lub skierowaniu go do remontu. Stan powierzchni chwytanego detalu moe by obrazem
dla systemu sensorycznego robota sortujcego elementy na tamie montaowej. Zbior
parametrow
ekonomicznych
opisujcych
gospodark
przedsibiorstwa
moe
by rozpoznawany jako opis pewnego obiektu, co pozwala na automatyczne zaliczenie
go do obrazu zakadow rozwojowych, wartych inwestowania lub stojcych na progu
bankructwa."
W anglojzycznej literaturze dotyczcej rozpoznawania stosowany jest trafniejszy termin:
pattern recognition, w dosownym tumaczeniu oznaczajcy rozpoznawanie wzorcow.
Skoro wiadomo ju, e obiekty podlegajce rozpoznawaniu mog mie rozmaity
charakter, naturalnym wydaje si by, e zbior cech opisujcych te obiekty bdzie od nich
uzaleniony. Co wicej ten sam zbior obiektow mona klasyfikowa pod ronym wzgldem.
Oznacza to, e wydobywane cechy charakterystyczne, bd take zalene od konkretnego

8

---

zadania, a ich wybor bdzie dokonywany pod wzgldem celu jaki mamy osign.
Wyznaczenie przestrzeni cech jest zatem wstpnym i kluczowym etapem rozpoznawania.
Pomimo istnienia ronorodnych metod klasyfikacji obiektow, teoria rozpoznawania nie
dostarcza jak na razie algorytmu automatycznego wyboru samych cech. Co wicej, wybrana
ju przestrze cech moe jeszcze by poddana wartociowaniu oraz optymalizacji z punktu
widzenia przydatnoci wybranych cech w procesie rozpoznawania. Weryfikacja taka jednak
moe zosta przeprowadzona dopiero po uzyskaniu wynikow rozpoznawania, a sposob
konstrukcji przestrzeni cech szczegoowo opisuje rozdzia 2.1.1.
Jak ju wczeniej zaznaczono ogolnym zadaniem rozpoznawania obrazow
jest wskazanie przynalenoci ronego rodzaju obiektow do pewnych klas. Aby klasyfikacja
taka moga by przeprowadzona konieczne jest przekazanie algorytmowi rozpoznajcemu
informacji na ten temat. Poniewa w odronieniu od czowieka algorytm taki nie posiada
apriorycznej wiedzy o sposobie klasyfikacji obiektow do waciwych klas, musi ona by
wprowadzona do pamici za pomoc cigu uczcego zawierajcego przykadowe obiekty,
dla ktorych znana jest prawidowa klasyfikacja. W ten sposob przeprowadza si proces
uczenia algorytmu bazujcy na cigu uczcym, ktory jest pewnym uogolnieniem
i reprezentacj wszystkich rozpoznawanych obiektow. Z racji tego, e podczas uczenia
wprowadzamy do algorytmu jedynie cz obiektow, natomiast rozpoznawaniu poddawane
s wszystkie pozostae (nienalece do cigu uczcego), dobor przykadowych obiektow
ma kluczowe znaczenie dla wynikow rozpoznawania. Problem ten bdzie przedmiotem
rozwaa w rozdziale 2.1.2.
Bez wzgldu na to czy cechy wykorzystywane w procesie rozpoznawania poddano
wstpnej selekcji bd przetworzeniu, na ich podstawie nastpuje proces podejmowania
decyzji o przynalenoci zadanego obiektu do jednej z ustalonych klas. Warto tutaj zatem
w skrocie zaprezentowa dwa podejcia do tego procesu.
Podejcie caociowe charakteryzuje si tym, e podjcie decyzji nastpuje w jednym
etapie przy uwzgldnieniu wszystkich cech rozpoznawanego obiektu. Istniej rone metody
dziaajce na podstawie tzw. jednego aktu decyzyjnego. S to m.in. metody zwizane
z pojciem odlegoci oraz geometrii (opisane w dalszej czci tej pracy), metody oparte
o aproksymacj funkcji przynalenoci bd bazujce na statystyce itd. [6].
Podejcie strukturalne bazuje na okreleniu w rozpoznawanym obiekcie pewnych
elementow oraz wyznaczeniu wzajemnych relacji midzy nimi. Wyznaczanie to odbywa si,
podobnie jak w przypadku wczeniej opisanych metod, na podstawie wybranych cech. Jest
to jednak etap wstpny, po ktorym nastpuje waciwe rozpoznawanie uwzgldniajce
strukturalny opis zawierajcy wykryte elementy i ustalone relacje. Podejcie to wydaje si
by bardziej skomplikowane, a jego uycie moe by uzasadnione gdy mamy do czynienia
z problemami zbyt zoonymi dla podejcia caociowego dlatego nie bdzie ono
przedmiotem dalszych rozwaa w tej pracy [6].

9

---

1.2. Przetwarzanie i analiza obrazow1
Wspomniana we wczeniejszym rozdziale automatyzacja stanowisk oraz procesow
decyzyjnych wie si bardzo czsto z zaprojektowaniem automatycznych systemow
wizyjnych, za pomoc ktorych bylibymy w stanie przetworzy, przeanalizowa
oraz przekaza urzdzeniom niezbdne informacje o analizowanym obiekcie lub otoczeniu
mogcym wpyn na przebieg zautomatyzowanego procesu. Systemy te zyskay
w ostatnich latach wielk popularno i znajduj zastosowanie w coraz wikszej iloci
dziedzin. Poczwszy od procesow przemysowych poprzez medycyn, robotyk, mineralogi,
metalurgi, astronomi, komunikacj oraz wszdzie tam gdzie wystpuje konieczno
interpretacji, bd wydobycia informacji z szeroko pojtego obrazu, coraz czciej siga
si po gotowe, lub probuje konstruowa nowe algorytmy bazujce na przetwarzaniu
i analizie obrazu. Opracowywanie nowych algorytmow i prezentowanie nowych, ambitnych
podej do problematycznych zagadnie uatwia cigy rozwoj nie tylko szeroko pojtych
systemow wizyjnych, ale take powizanych z nimi dziedzin.
Nie ulega wtpliwoci, e zadania realizowane przez wspomniane wyej systemy
wizyjne mog by niejednokrotnie wyjtkowo skomplikowane i zoone. W odronieniu
od czowieka, ktory uczy si czynnoci przetwarzania i analizowania obrazow od okresu
niemowlcego, doskonalc j przez cae ycie a stanie si ona dla niego zupenie naturalna
i oczywista, maszyna wymaga zaprogramowania tego procesu co jest bardzo trudne, jednak
czsto przynosi wymierne korzyci w postaci:
szybszej i taszej analizy,
powtarzalnoci wynikow,
automatycznego rejestrowania wynikow,
eliminacji czynnikow ludzkich takich jak zmczenie czy stres,
atwoci w powielaniu rozwiza,
moliwoci przetwarzania obrazow rejestrowanych w ronych zakresach
promieniowania.
Zoono i strukturalny charakter zautomatyzowanego procesu widzenia przejawia
si w etapach, ktore przej musi obraz zanim zostanie zinterpretowany. Etapy te mona
zdefiniowa jako nastpujce operacje:
akwizycja obrazu,
przetwarzanie obrazu,
analiza obrazu,
rozpoznanie i interpretacja obrazu,

1 Rozdzia zosta opracowany w oparciu o ksik Tadeusiewicza [7].
2 Rozdzia zosta opracowany w oparciu o ksik Tadeusiewicza i Flasiskiego [6].

10

---