České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačové grafiky a interakce
Diplomová práce
Rozpoznávání druhů dřevin rostoucích v České republice podle tvaru listu Ivana Váňová
Vedoucí práce: Ing. Tomáš Suk, CSc.
Studijní program: Otevřená informatika, Navazující magisterský Obor: Počítačová grafika a interakce 3. ledna 2013
iv
v
Poděkování Chtěla bych poděkovat vedoucímu práce Ing. Tomáši Sukovi, CSc., který byl trpělivý a poskytl mi cenné rady při vypracování mé práce. Dále bych chtěla poděkovat sestře Ireně a švagru Ondrovi za debaty o zpracování obrazu obecně. V neposlední řadě také velice děkuji všem v mém okolí za jejich nekonečnou podporu.
vi
vii
Prohlášení Prohlašuji, že jsem práci vypracovala samostatně a použila jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorském a o změně některých zákonů (autorský zákon).
V Praze dne 1. 1. 2013
.............................................................
viii
Abstract This thesis deals with leaves recognition. The aim is to create a web application; any user can upload image of some leave and the application should recognize species of the tree. Method proposed in the thesis consists of three major steps: segmentation, calculation of shape descriptors, and classification. Thresholding with Otsu’s method for threshold selection has been used for the leave segmentation. Invariant description of the leave shave is based on Zernike moments. Amplitude and phase are normalized by distance functions during the Zernike moments evaluation. The method has been tested on two datasets: Flavia and MEW2012. Species of the tree is successfully recognized on 84.1% of Flavia dataset samples and on 67.7% of MEW2012 dataset. The success rate increases to 86.9% when composition and size of the leave is known.
Abstrakt Cílem této práce je vytvořit webovou aplikace, která rozpozná uživatelem vložený list dřeviny rostoucí v ČR a určí jeho botanický druh. Práce se skládá ze tří částí: segmentace listu, vypočtení deskriptoru a jeho klasifikace. Pro segmentaci listu bylo použito prahování s Otsuovou metodou volby prahu. Popis listu je založen na Zernikových momentech, jejichž amplitudy a fáze jsou v rámci klasifikace porovnávány vzdálenostními funkcemi. Pro testování byly použity dva datasety: Flavia a MEW2012. Pro rozšířený dataset Flavia bylo docíleno úspěšnosti klasifikace 84,13 % pro prvního kandidáta a pro dataset MEW2012 67.65 % bez zadání dodatečné informaci o složení a velikosti listu. Pokud tyto informace bylo zadány, úspěšnost stoupna na 86.90 %.
ix
x
Obsah Obsah
xi
Seznam obrázků
xiv
1 Úvod 1.1 Formulace úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Motivace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Morfologie listu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 1 2 2
2 Vstupní datové množiny 2.1 MEW2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Flavia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 5 6
3 Přehled dostupných řešení 3.1 Klíč pro určování dřevin . . . . . . . . . . . . . . 3.2 Tvarový kontext a křivost . . . . . . . . . . . . . 3.3 Určování podle morfologických znaků . . . . . . . 3.4 Podle příznaků poskytujících úplný popis objektu
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
7 . 7 . 8 . 10 . 11
4 Řešení 4.1 Segmentace . . . . . . . . 4.2 Odstranění řapíku . . . . 4.2.1 Poměr vzdáleností 4.2.2 Otevření . . . . . . 4.3 Popis listu . . . . . . . . . 4.3.1 Předzpracování . . 4.3.2 Výpočet . . . . . . 4.3.3 Normalizace . . . . 4.4 Klasifikace . . . . . . . . . 4.4.1 Amplituda . . . . . 4.4.2 Fáze . . . . . . . . 4.4.3 Velikost . . . . . . 4.4.4 Složení . . . . . . . 4.4.5 Optimalizace . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
13 13 14 14 15 16 16 18 18 19 19 19 20 20 21
5 Implementace 25 5.1 Hlavní algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.1.1 Členění řešení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 xi
xii
OBSAH . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
26 26 28 28 28 28
6 Výsledky 6.1 Dataset MEW2012 . . . . . . 6.1.1 Výsledky optimalizace 6.2 Dataset Flavia . . . . . . . . 6.2.1 Výsledky optimalizace
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
29 30 31 32 32
5.2 5.3
5.1.2 Převod dat Webové rozhraní . Deployment . . . . 5.3.1 Server . . . 5.3.2 Databáze . 5.3.3 Kompilace .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
7 Závěr
33
A Seznam druhů datasetu MEW2012
35
B Obsah příloženého DVD
37
Literatura
39
Seznam obrázků 1.1
Dělení jednoduchého a složeného listu . . . . . . . . . . . . . . . . . . . .
2.1
Rod javor (Acer ): (a) javor babyka (Acer campestre), (b) javor amurský (Acer ginnala), (c) javor jasanolistý (Acer negundo), (d) javor dlanitolistý (Acer palmatum), (e) javor mléč (Acer platanoides), (f) javor klen (Acer pseudoplatanus), (g) javor stříbrný (Acer saccharinum), (h) javor cukrový (Acer saccharum), (i) javor tatarský (Acer tataricum) . . . . . . . . . . . Srovnání listu Břečťanu popínavého (Hedera helix ) z nedospělých (a) a plodících větviček (b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
Ukázka klíče pro určování stromů . . . . . . . . . . . . . . . . . . . . . . .
7
2.2
3.1
Segmentace listu kaštanovníku setého (Castanea sativa) prahováním s více metodami volby prahy: Otsu, Ridler-Calvard (metoda IsoData), ZackRogers-Latt (metoda Triangle) a metoda založená na detekci těžiště . . . 4.2 Obrys listu javor mléč (Acer platanoides) s výsledky detekce řapíku; Graf poměru indexové a prostorové vzdálenosti pro každý okrajový bod; zeleně jsou vyznačeny body lokace řapíku; modře body optimalizovaného řezu řapíku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Ukázka selhání algoritmu pro odřezávání řapíku pomocí poměru vzdáleností 4.4 Ukázka selhání algoritmu pro odřezávání řapíku pomocí otevření . . . . . 4.5 Zobrazení prvních 15 Zernikových polynomů řádu m a opakování l . . . . 4.6 Způsoby normalizace vůči měřítku vstupních listu (a) do jednotkového kruhu o poloměru r, kdy (b): r = k · std(d(T, x)); k = 5.8 nebo (c): r = max(d(T, x)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Graf testování úspěšnosti konstanty k, která určuje poloměr definičního kruhu při normalizaci oproti změně měřítka. . . . . . . . . . . . . . . . . . 4.8 Dvojice druhů, které vyšly jako falešně pozitivní shody, podobné tvarem čepele, ale výrazně odlišné velikostí listu: (a) Katalpa trubacovitá(Catalpa bignonioides), (b) Šeřík obecný(Syringa vulgaris), (c) Javor jasanolistý (Acer negundo) a (d) Ořechovec vejčitý (Carya ovata) . . . . . . . . . . . 4.9 Zástupci druhů, u který došlo po odříznutí řapíku k největšímu zhoršení úspěšnosti: (a) Řešetlák počistivý (Rhamnus cathartica), (b) Kalina vonná (Viburnum farreri), (c) Buk lesní (Fagus sylvatica), (d) Olše zelená (Alnus alnobetula) a (e) Jeřáb muk (Sorbus aria) . . . . . . . . . . . . . . . . . . 4.10 Změna průměrné úspěšnosti popisu všech druhů po zavedení odřezávání řapíku ve srovnání s průměrnou směrodatnou odchylkou vzdáleností prvních třech kandidátů bez řapíku od dotazovaného listu. . . . . . . . . . . . . .
3
5
4.1
xiii
13
14 15 15 16
17 17
20
21
21
xiv
SEZNAM OBRÁZKŮ 4.11 Srovnání výsledků úspěšnosti klasifikace prvního kandidáta dřeviny řešetlák počistivý (Rhamnus cathartica) s řapíkem a bez řapíku se standardní směrodatnou odchylkou vzdálenosti prvních třech kandidátů bez řapíku od dotazovaného listu bez řapíku. . . . . . . . . . . . . . . . . . . . . . . . 22 4.12 Graf úspěšnosti při změně volby prahu pro použití řapíku: vlevo se použijí všechny listy bez řapíku, vpravo všechny s řapíkem. Červeně je vyznačena optimální hodnota prahu s nejvyšší úspěšností. . . . . . . . . . . . . . . . 23 4.13 Graf srovnání úspěšnosti rozpoznávání bez odřezávání řapíku a s odřezáváním v závislosti na normalizační konstantě k, která určuje poloměr definičního kruhu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.1 5.2 5.3
5.4 6.1 6.2 6.3 6.4 6.5 6.6
Jednotlivé části implementace: červeně - http rozhraní; modře - C++ programy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Screenshoty: (a) vložení vstupního listu, (b) zadání dodatečné informace o složení listu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Screenshoty: (a) možnost pro opravu automatické volby prahu a nepovinné zadání rozlišení, resp. reálně velikosti snímku, (b) zobrazení navrhovaných kandidátů a případná verifikace výsledků uživatelem . . . . . . . . . . . Model použité databáze . . . . . . . . . . . . . . . . . . . . . . . . . . . Graf úspěšnosti klasifikace datasetu MEW2012 v závislosti na počtu kandidátů při různých vstupných parametrech. . . . . . . . . . . . . . . . . Graf úspěšnosti rozpoznávání jednotlivých druhů datasetu MEW2012 bez zadání vstupních parametrů . . . . . . . . . . . . . . . . . . . . . . . . . Graf úspěšnosti rozpoznávání jednotlivých druhů datasetu MEW2012 se zadáním vstupních parametrů rozlišení a složení listu . . . . . . . . . . . Porovnání úspěšnosti s podmíněným odřezávání řapíku, s permanentním odřezáváním a bez něj pro dataset MEW2012 . . . . . . . . . . . . . . . Graf úspěšnosti klasifikace datasetu Flavia v závislosti na počtu kandidátů při zadání velikosti a bez něj. . . . . . . . . . . . . . . . . . . . . . . . . Porovnání úspěšnosti s podmíněným odřezávání řapíku, s permanentním odřezáváním a bez něj pro dataset Flavia . . . . . . . . . . . . . . . . .
. 25 . 27
. 27 . 28
. 30 . 30 . 31 . 31 . 32 . 32
Kapitola 1
Úvod Vědní obor zpracování signálu se zabývá zpracováním libovolného signálu obrazového, zvukového nebo jakékoli časově či prostorově proměnného měření. V dnešní době se tento obor dostává do popředí zájmu díky velkému množství dat a tím i praktických aplikací, které je třeba řešit. Mezi základní výzvy zpracování obrazové informace patří rozpoznávání objektů. Takové aplikace ulehčují práci v mnoha oblastech – v zajišťování objektů, policii (detekce postav, obličejů, detekce SPZ), v lékařství (analýza a zpracování dat z ultrazvuku i jiných modalit), v biologii a v mnoha dalších. A právě prakticky motivovaná úloha z biologie, rozpoznávání listů, je předmětem této diplomové práce.
1.1
Formulace úlohy
Cílem této diplomové práce je vytvořit webovou aplikaci, která po vložení snímku listu dřeviny uživatelem určuje podle databáze listů odpovídající botanické druhy dřevin. Uživatelem mohou být volitelně dodány i mimoobrazové informace: informace, zda se jedná o jednoduchý list nebo lístek ze složeného listu, a hustota vzorkování, se kterou byl snímek pořízen. V aplikace také může uživatel poopravit automaticky vypočtený práh použitý pro segmentaci prahováním, pokud automatický výsledek není uspokojivý. Prioritou aplikace je především její plná automatizace, s tím že volitelně dodané vstupní informace však mohou výsledky velmi zpřesnit. Pokud chceme dodávání vstupních mimoobrazových informací uživatelem maximalizovat, musí být tyto možnosti uživateli jednoduše a jasně podány a musí se maximálně zjednodušit jejich zadávání. Informace o hustotě vzorkování v DPI lze např. převést z uživatelsky přívětivější velikosti listu (či snímku) uživatelem zadané v běžných měrných jednotkách. Po vyhodnocení vstupů budou uživateli nabídnuty setříděné tři botanické druhy jako pravděpodobné řešení s ukázkami typických zástupců pro verifikaci. Uživatel bude moci v závěru zvolit, zda je některé z nabízených řešení prokazatelně správné, příp. které. Všechny dotazy na webový server (i s případnou verifikací uživatelem) budou zaznamenávány pro budoucí analýzu. V této práci nejprve krátce v kapitole 2 zmíním datasety listů, které byly použity při vývoji a testování aplikace. Poté představím postupy, které byly k rozpoznávání rostlin a dřevin podle listu dosud použity - viz. kap. 3, a následně představím v kapitole 4 vlastní postup řešení. Dále popisuji implementaci našeho finálního řešení (kap. 5) a výsledky jeho testování (kap. 6), které strhnu v závěrečné kapitole 7. 1
2
1.2
KAPITOLA 1. ÚVOD
Motivace
Dřevnaté porosty jako součást flóry hrají stěžejní roli v ekosystému celé planety. Podílí se fotosyntetickým procesem na čistění ovzduší a stabilizují klima svojí odolností vůči povětrnostním podmínkám, erozi i vysokou absorpcí extrémních srážek. V České republice mají dřeviny navíc také důležitou funkci jako cenný obnovitelný zdroj energie a recyklovatelného materiálu. V České republice, stejně jako v celé střední Evropě, patří mezi původní porosty smíšené opadavé lesy mírného pásu tvořené z velké části druhy dubu a buku. Z ekonomických důvodů přirozené smíšené lesy v dobách minulých byly postupně potlačeny monokulturami jehličnatých lesů. V současné době je druhové složení lesních dřevin v ČR podle plochy takovéto: smrk ztepilý (51,9%), borovice (16,8%), buk (7,3%), dub (6,9%), modřín (3,9%), bříza (2,8%), jedle (1%) atd. Celkový podíl zarostlé plochy jehličnatých dřevin je 73,9%, avšak tato plocha se neustále zmešuje [33] jako výsledek snahy při obnově přirozenějšího lesního porostu. V celkovém měřítku nepatrný, avšak velmi různorodý podíl tvoří dřeviny zavlečené či vyšlechtěné pro účel okrasný, či užitný. Proto lze na území ČR potkat velké množství druhů jehličnatých i listnatých stromů a ostatních dřevin. Ve střední Evropě evidujeme přibližně 200 druhů původních listnatých dřevin. Např. v knize Dřeviny ČR [22] je popsáno 213 původních druhů, poddruhů a ustálených kříženců dřevin, z toho 52 stromovitého vzrůstu, 26 druhů, které jsou keřovité, ale mohou dosáhnout i stromovitého habitu, 85 keřů, 26 polokeřů, 19 keříčků a 5 dřevitých lián. S počty druhů zavlečených dřevin je to složitější, za významné se považuje asi 200 druhů. Samostatnou kapitolou je botanický rod Ostružiník (Rubus), který tvoří jednu z druhově nejbohatších a zároveň taxonomicky nejkritičtějších skupin rostlin (převážně dřevin) ve střední Evropě [16]. V současné době se v ČR rozlišuje více než 120 druhů ostružiníků. Dřevinami obecně nazýváme vytrvalé rostliny se schopností druhotného tloustnutí dřevnatého stonku. Mezi dřeviny řadíme 3 skupiny rostlin: stromy, keře a dřevité liány. Má-li dřevina kmen (zpravidla u země nevětvený dřevnatý stonek), nazýváme ji strom. Další skupiny dřevin jsou keře (jejich stonky se větví hned u země a jsou na rozdíl od polokeřů celé dřevnaté) a některé liány s dřevnatým stonkem. Přechodem mezi dřevinami a bylinami jsou polokeře, jejichž stonky se větví hned od země ale jsou zdřevnatělé pouze ve své dolní části. Listnaté dřeviny mají mnoho druhových rozpoznávacích znaků. Patří mezi ně: list, květ, plod, kůra, tvar koruny atd. Rozpoznání některý druhů listnáčů mezi sebou je kvůli šlechtění i přirozené diverzitě problematické i pro botaniky. My se zaměříme na rozpoznávání dle listu - podle jeho tvaru i vnitřní kresby žilnatiny.
1.3
Morfologie listu
Pro lepší porozumění následujícímu textu uvedeme krátký úvod do morfologie listu [11] a s tím související terminologické minimum. Listy se dělí na jednoduché a složené, viz. obr. 1.1. Každý jednoduchý list se skládá z čepele s žilnatinou a řapíku. Složené listy mají čepel rozdělenou na menší lístky, které jsou buď těsně přisedlé nebo mají vlastní řapíček.
1.3. MORFOLOGIE LISTU
3
Obrázek 1.1: Dělení jednoduchého a složeného listu
Jednoduché listy se dále dělí podle členitosti čepele na celistvé a členěné. Složené listy se dělí podle postavení lístků na dlanitě složené a zpeřené. Složený zpeřený list se od větvičky s jednoduchými listy liší nepřítomností pupenů. Další dělení listů nebude v textu zmiňováno. Obecně je známo, že největší list daného druhu je většinou nejvýše dvakrát tak velký než nejmenší dospělý list.
4
KAPITOLA 1. ÚVOD
Kapitola 2
Vstupní datové množiny Pro, v zadání určené, listnaté dřeviny rostoucí v ČR neexistovala dosud dostatečná datová množina, která by obsáhla všechny požadované rostliny v dostatečné míře. Proto PhDr. Petr Novotný z Pedagogické fakulty UK nasbíral a klasifikoval vzorky a sestavil tak datovou množinu odpovídající zadání. Dataset byl nazván MEW2012 (Middle European Woods 2012).
2.1
MEW2012
Tento dataset obsahuje 151 druhů dřevin s celkem 9745 listy. Do datasetu byly zařazeny jen ty listnaté dřeviny, u nichž se podařilo nasbírat alespoň 50 reprezentativních vzorků. Tento dataset obsahuje většinu listnatých dřevin rostoucích v oblasti České republiky ty běžné i méně obvyklé. V tabulce A.1 a A.2 v příloze A jsou uvedeny všechny obsažené dřeviny se svým latinským a českým rodovým i druhových jménem spolu s četností vzorků, označení typu dřeviny a zda má dřevina jednoduchý čí složený list. Z tabulky je patrné, že nejpočetnější rodová skupina listnáčů je rod Acer - javor. Javory tvoří v oblasti ČR velmi rozmanitý rod dřevin, jehož většina druhů se rozlišuje jen nepatrnými změnami,
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
Obrázek 2.1: Rod javor (Acer ): (a) javor babyka (Acer campestre), (b) javor amurský (Acer ginnala), (c) javor jasanolistý (Acer negundo), (d) javor dlanitolistý (Acer palmatum), (e) javor mléč (Acer platanoides), (f) javor klen (Acer pseudoplatanus), (g) javor stříbrný (Acer saccharinum), (h) javor cukrový (Acer saccharum), (i) javor tatarský (Acer tataricum) 5
6
KAPITOLA 2. VSTUPNÍ DATOVÉ MNOŽINY
které mohou být jednoduše zaměnitelné za přirozenou diverzitu v rámci jednoho druhu. Pouze javor babyka (Acer campestre), javor klen (Acer pseudoplatanus) a javor mléč (Acer platanoides) jsou v ČR druhy původními, ostatní druhy javorů byly zavlečeny. Celkově 151 obsažených druhů odpovídá 93 rodům, přičemž 9 druhů náleží rodu Acer. V datasetu MEW2012 je obsaženo 67 druhů listnatých stromů, 42 druhů keřů, 32 druhů velkých keřů, které se mohou rozrůst v malý strom, a 10 druhů dřevitých lián. 122 druhů dřevin z datasetu má list jednoduchý a 31 druhů list složený - viz. kap. 1.3. Pro dvoudomý keř maklura oranžová (Maclura pomifera) jsou v datasetu zastoupeny listy ze samčího i samičího jedince. Pro dřevitou liánu břečťan popínavý (Hedera helix ) jsou zahrnuty listy z nedospělých (juvenilních) i plodících větévek, které se liší svojí laločnatostí, jak je vidět na obr. 2.2.
(a)
(b)
Obrázek 2.2: Srovnání listu Břečťanu popínavého (Hedera helix ) z nedospělých (a) a plodících větviček (b) Zástupci pro taxonomicky problematický rod ostružiníků (Rubus) v datasetu nejsou přítomni. Všechny obsažené listy obsahují řapík, aby množina mohla být použita pro testování algoritmů rozpoznávající listy bez ohledu na to, zda řapík je nebo není přítomen. Vzorky v datasetu MEW2012 byly snímány skenerem s rozlišením 300 DPI. Dataset je ke stažení zde: http://leaves.utia.cas.cz/dataset.
2.2
Flavia
Flavia je jedna z nejpoužívanějších testovacích množin pro listy roslin, a proto ji uvedeme pro možnost srovnání výkonnosti našeho algoritmu s ostatními projekty. Flavia [31] je dataset, který byl vytvořen pro testování rozpoznávacích algoritmů na principu pravděpodobnostních neuronových sítí [30]. Obsahuje celkem 1907 listů, které přísluší 33 druhům, které odpovídají 30 rodům. Počet zástupců jednoho druhu se pohybuje od 50 do 77 listů. Dataset mapuje listnaté stromy rostoucí v deltě řeky Jang-c’-ťiang v Číně a částečně se s MEW2012 překrývá. Všechny obsažené listy jsou bez řapíku, což práci čistě nad touto množinou částečně zjednodušuje.
Kapitola 3
Přehled dostupných řešení Zkoumání roslin i přírody obecně člověka zajímá odnepaměti, a tudíž si vyvinul jednoduchý způsob, jak rostliny rozpoznávat - za pomocí klíče pro určování rostlin (kap. 3.1). V poslední době vzniká také mnoho výpočetních systémů, které mají určování zrychlit a zpřesnit. Využívá se různých přístupů - identifikace podle tvaru a křivosti hranice listu (kap. 3.2), podle jeho morfologických znaků (kap. 3.3) či podle jeho obecného vyjádření (kap. 3.4).
3.1
Klíč pro určování dřevin
Klíč pro určování rostlin byl jeden z prvních způsobů, jak mohl i laik efektivně určit druh zkoumané rostliny, byť je jeho použití podmíněno alespoň základní znalostí botanické terminologie, především z morfologie rostlin.
Obrázek 3.1: Ukázka klíče pro určování stromů
7
8
KAPITOLA 3. PŘEHLED DOSTUPNÝCH ŘEŠENÍ
Postup určení je založen na rozhodovacím stromu otázek na vnější stavbu zkoumané rostliny. Ukázka z knihy Klíč k určování stromů - 123 nejběžnějších stromů v ČR [7] je vidět na obr. 3.1. I když klíče pro určování rostlin se vyskytují především jako knihy, jsou dostupná i elektronická řešení. Výhodou elektronických klíčů je jejich interaktivita, která napomáhá lepšímu pochopení rozhodovacích kritérií. V češtině jsou dostupné elektronické klíče např. zde [21], i když zahraniční projekty jsou propracovanější, např. [26], [28], [27] nebo [25]. Výhodou klíčů obecně je jejich možná specializace - např. klíč pro určování dřevin podle pupenů a větviček, klíč pro určování lesních rostlin ve vegetativním stavu atd. Nevýhodou je to, že určování pomocí klíče je poměrně zdlouhavý proces a nemusí vést k jednoznačnému výsledku.
3.2
Tvarový kontext a křivost
Automatické nebo poloautomatické rozpoznávání listnatých dřevin se v poslední době stalo oblíbenou úlohou. Nejčastěji se tato úloha řeší jako klasifikace specifického vyjádření binárního vstupu charakterizující tvar listu dané dřeviny (či byliny). Krátce přede mnou se touto úlohou zabýval kolega Tomáš Sixta ve své diplomové práci [24], kde se kromě rozpoznávání listnatých dřevin podle listu zabýval i rozpoznávání jehličnanů podle kůry - přičemž veškeré výpočty probíhají na běžném telefonu s operačním systémem Android. Pro segmentaci vstupních dat byla použita poloautomatická verze algoritmu Watershed - segmentace záplavou, kdy uživatel zadá počáteční body (semínka) náležící popředí a pozadí. Výhodou tohoto postupu je, že lze úspěšně vysegmentovat i listy na texturované pozadí. Z vysegmentovaného popředí se vypočte příznakový prostor Inner Distance Shape Context, kde deskriptor Shape Context (tvarový kontext) používá metriku Inner Distance (vnitřní vzdálenost) rozšiřující Eukleidovskou metriku. Pro klasifikaci byl použit test dobré shody neboli χ2 − test. Testování výkonnosti probíhalo na datasetu Flavia (kap. 2.2) s úspěšností 83,3% pro prvního kandidáta a 94,3%, kdy se správná odpověď vyskytuje mezi prvními 3 navrhovanými. V další práci [14] autoři také vyvinuli mobilní aplikaci. Na rozdíl od výše uvedené práce, se ale výpočty neprovádějí na mobilním zařízení, ale na výkonném serveru. Mobilní zařízení s operačním systémem iOS slouží pro pořízení a odeslání snímku, zobrazení výsledku vyhodnocení, případnou verifikaci výsledku uživatelem a také k lokaci testovaného vzorku. Na serveru se vzorek nejprve převede do binární reprezentace pomocí hodnot sytosti a jasu (v barevném modelu HSV). Pro další zpracování se bere pouze největší spojitá komponenta a tím jsou odstraněny falešně pozitivní oblasti vznikající pří pořizování snímku na pozadí. Poté jsou pomocí morfologické operace otevření (eroze následovaná dilatací) odstraněny oblasti jako kandidáti na řapík listu. Největší odstraněná oblast je prohlášena za řapík a z listu odstraněna. Nyní autoři vyjádří list histogramy křivostí. Hodnoty histogramu jsou dány tak, že pro každý obvodový bod se spočítá, jaká poměrná část kruhu o poloměru r se středem v daném obvodovém bodu leží uvnitř listu. V závislosti na různě velkých r se vytvoří různé histogramy s detekcí různě velkých křivostí. Sestavením histogramů se pro každý list vytvoří škálově normovaný "obrázek křivostí", který se následně může porovnávat s ostatními vzorky. Tato práce využívá jeden z nejrozsáhlejších datasetů čítající 184 druhů stromů ze severovýchodu USA v
3.2. TVAROVÝ KONTEXT A KŘIVOST
9
23915 skenovaných a 5192 mobilem vyfocených vzorcích. Autory uváděná úspěšnost pro prvních pět dobrých je 96,8%, na první dobrý výsledek pak cca. 72%. Další inspirativní článek [3] nepopisuje rozpoznávání listů listnatých dřevin, ale listů plevelnatých bylin pro cílenější používání herbicidů, a podobně jako u předchozí práce je cílem autorů popsat křivost listu. V rámci předzpracování používají autoři Otsuovu metodu [19] pro volbu prahu při segmentaci prahováním šedotónového vstupu a následně z binárního obrázku pomocí Cannyho hranového detektoru extrahují hranice listu. Hraniční uzavřená křivka se převzorkuje na m bodů se stejnou obloukovou vzdáleností, které se následně vyhladí konvolucí s Gaussovským jádrem s fixní šířkou σ = 1. Poté se vypočte Eukleidovská vzdálenost hraničních bodů od těžiště a vzdálenosti se normují odmocninou sumy kvadrátů všech vzdáleností. Z vektoru normovaných vzdáleností se vypočte první derivace, čímž se získá vektor rychlosti, která zde reprezentuje křivost. Vektor rychlostí se vyhladí filtrem nejmenších čtverců s jádrem o velikosti 10%m a všechny hodnoty vektoru se normalizují minimální a maximální hodnotou na < 0; 1 >. Ve fázi porovnávání vzorů se nejprve vypočte vzájemné otočení mezi dotazem a potencionální odpovědí podle nejvýraznějších lokalních extrémů vektorů, a pak se dotazovaný obrázek posune o rozdíl rotací kruhovým posunem v daném vektoru. Výsledná podobnost (korelační koeficient) dvou rotačně normalizovaných vektorů rychlosti je dán jako kvadrát podílu kovariance vektorů normalizovaný standartními odchylkami obou vektorů. Pro dotazovaný list a každý list z trénovací množiny se vypočte korelační koeficient pro 2 navrhované rotační normalizace a větší z nich je prohlášen za platný. Nejvyšší korelační koeficient určuje nejpodobnější list z trénovací množiny pro dotazovaný list. Další publikace [10] také využívá k rozpoznání pouze hranici listu. Z naskenovaného a (blíže neurčeným způsobem) vysegmentovaného listu se extrahuje hranice, která se vyhladí Gaussovským jádrem. Poté se body hranice převzorkují na n bodů s konstantní obvodovou vzdáleností sousedních bodů. Jako optimální autoři uvádějí n = 32. Dále se vypočte těžiště celého listu. Jako deskriptor se pro n bodů vypočte Eukleidovská vzdálenost od těžiště. Následně se vypočte pro porovnávající deskriptory listů matching skóre S; S ∈< −1; 1 >, které určí míru podobnosti dvou vstupních listů. Článek [32] zpracovává vzdálenost okrajových bodů od těžiště dále. Tuto seřazenou posloupnost znormalizuje na hodnoty < 0; 1 > a vypočte z ní normalizovanou diskrétní Fourierovu transformaci - DFT, kterou nakonec porovnává pomocí jednoduchého k-NN klasifikátoru s úspěšností 89.6% na Švédské knihovně čítající 15 druhů o 1125 vzorcích. Další práce [4] se zaměřuje na extrakci zoubkování čepele. Nejprve se vyjádří rozdíl zoubkovité čepele od mediánových filtrem vyhlazené hranice listu. V dalších dvou krocích se používá synchronizační metoda dynamického borcení časové osy (Dynamic Time Warping - DTW ). Nejdřív se pomocí této metody najde místo, kde čepel přechází v řapík, a jeho protilehlá špička listu - a to tak, že se vychází z předpokladu, že list je zpravidla téměř osově symetrický podle spojnice těchto dvou bodů. Proto se kruhovým posunem hledají dvě posloupnosti obvodových bodů s minimální rozdílem. Dále se algoritmus DTW používá i k měření podobnosti vzorků mezi sebou. Protože však nevíme, který z nalezených bodů je přechod řapíku a čepele a který je špička listu, tak jsou všechny 4 možnosti mezi 2 porovnávanými vzorky spočítány. Metoda dosahuje úspěšnosti 91,32% na vlastní množině obsahující 100 druhů rostlin. Titíž autoři později vydali práci [5] o klasifikaci vysoko dimenzionálních funkcí, která využívá optimalizační algoritmus zvaný Maďarská metoda.
10
3.3
KAPITOLA 3. PŘEHLED DOSTUPNÝCH ŘEŠENÍ
Určování podle morfologických znaků
Způsob popisu listu, který je myšlenkově nejbližší původním klíčům pro určování, je popis pomocí morfologických vlastností. Tyto vlastnosti jsou přesně numericky vyčíslitelné a vektor konkrétních vlastností tvoří deskriptor popisující geometrii listu. Použité morfologické vlastnosti se v publikacích opakují, nejčastěji se používá: • poměr stran W/L • kruhovitost (též izoperimetrický faktor, tvarový faktor) 2 4π ∗ SL /OL
• pevnost SL /SH • obdélníkovost W ∗ L/SH • nepravidelnost p max( (xi − xt )2 + (yi − yt )2 ) p min( (xi − xt )2 + (yi − yt )2 ) • excentricita: excentricita elipsy s identickými druhými momenty jako list; ∈< 0; 1 > • prodloužení 1 − max(d(xi , OL ))/DL • konvexita DH /DL Základní znaky listu: W - délka listu L - šířka listu DL - průměr listu SL - obsah listu OL - obvod listu DH - průměr konvexní obálky SH - obsah konvexní obálky OH - obvod konvexní obálky V - obsah žilnatiny listu
• faktor úzkosti DL /L • maximální hloubka vtisku: maximum vzdálenosti obvodového bodu od konvexní obálky normované délkou hranice • spektrum vtisku: Nejnižší frekvence Fourierova spektra z funkce vzdálenosti obvodových bodů od konvexní obálky, která kumuluje alespoň 80% energie spektra • laločnatost: součin kvadrátu maximální hloubky vtisku a spektra vtisku,
kde d je Euklidova vzdálenost a xi je libovolný bod plochy listu. Pro zjištění fyziologické délky a šířky listu se většinou předpokládá spolupráce uživatele, který označí počátek a konec hlavní osy listu. Jinak se uvažuje L = DL . V publikaci [20] se nejprve naskenovaný list vysegmentuje automatickou verzí algoritmu Watershed. Binární data se dále převedou na morfologické vlastnosti. Autoři použili: excentricitu, poměr stran, prodloužení, pevnost, náhodná konvexitu, kruhovost, maximální hloubka vtisku, spektrum vtisku a laločnatost. Poté bylo přidáno 7 Huových momentů. Ze všech těchto vlastností autoři pro zachování diskriminability nakonec po
3.4. PODLE PŘÍZNAKŮ POSKYTUJÍCÍCH ÚPLNÝ POPIS OBJEKTU
11
dlouhém testování použili jen excentricitu, třetí Huův moment a maximální hloubku vtisku. Klasifikátor je založen na vyhledávacím algoritmu k-NN (vyhledávající k nejbližších sousedů) s Eukleidovskou metrikou. Shoda je považována za pozitivní, pokud se rod dotazu nachází mezi rody k odpovědí - druhová shoda není požadována. Tento článek používá vlastní dataset o velikosti 209 listů z 22 rodů listnáčů. Autoři dosáhli správných výsledků v 70% pro první správný (k = 1), 80% pro (k = 3) a 90% (k = 10). Obdobný postup [1], který také využívá k popisu hranice listu jeho základní geometrické vlastnosti, vylepšuje postup klasifikace pomocí Support Vector Machine - SVM. Nejprve z 5 základních geometrických vlastností autoři vypočtou 12 pokročilých morfologických vlastností: poměr stran, kruhovost, obdélníkovost, poměry poloměru a délky a poměru a sumy délky s šířkou, faktor hladkosti (poměr počtu pixelů více a méně rozmazaného listu), faktor úzkosti a 5 faktorů reprezentující žilnatost. Poté pro minimalizaci dimensionality problému použijí analýzu hlavních komponent (Principal Component Analysis - PCA), která najde optimální mapování dat R12 → R5 . Nakonec použijí lineární SVM, který pro každé dvě třídy v R5 najde optimální dělicí nadrovinu z R4 . Autoři uvádějí, že pomocí SVM se podařilo zlepšit výsledky na datasetu Flavia (kap. 2.2) oproti klasifikátoru k-NN z 78% na 94.5% pro náhodně rozdělenou testovací a trénovací množinu.
3.4
Podle příznaků poskytujících úplný popis objektu
List lze vyjádřit také pomocí příznaků poskytujících úplný popis listu - např. pomocí momentů. Již dříve byla publikována řešení rozpoznávání rostlin podle listu využívající Huovi momenty, avšak momenty tvořily většinou jen doplňující roli. Zde uvedeme příklady publikací, kde těžiště řešení problému tkví v pokročilejších momentech. Takového přístupu využívá i publikace [13], která byla vydána krátce před vznikem této práce. V této publikaci se kombinuje popis obecným vyjádřením pomocí momentů s morfologickými znaky. Z morfologických znaků se používá: poměr stran, kruhovost, nepravidelnost, žilnatina, pevnost a konvexita. K tomu se přidají Zernikovy momenty, které jsou založené na ortogonálních Zernikových polynomech. Zernikovy momenty jsou definovány na kruhu, což je výhodné pro řešený problém. List k vyjádření pomocí Zernikových momentů je nejprve normalizován vůči translaci posunem těžiště listu do středu obrázku a vůči škále vydělením odmocninou plochy listu m00 . Poté jsou vypočteny Zernikovy momenty do 12. řádu. Výsledné momenty se následně normalizují plochou m00 . Normalizované Zernikovy momenty 2. až 12. řádu spolu s vypočítanými morfologickými znaky tvoří deskriptor. Následně autoři vyzkoušeli více klasifikátorů a metrik: pravděpodobnostní neuronové sítě a počítání vzdálenosti na základě Eukleidovské a Manhattanské (City-block) metriky. Podle prezentovaných výsledků se jako nejlepší klasifikátor osvědčilo počítání vzdálenosti na základě Eukleidovské metriky a nikoli pravděpodobnostní neuronové sítě, jak se předpokládalo. Autoři dosáhli úspěšnosti 94,69% na datasetu Flavia (kap. 2.2). Tato publikace je nejblíže našemu plánovanému řešení.
12
KAPITOLA 3. PŘEHLED DOSTUPNÝCH ŘEŠENÍ
Kapitola 4
Řešení Řešení zadaného problému lze rozdělit na segmentaci listu z pozadí, odstranění řapíku, vytvoření popisu listu a jeho následnou klasifikaci.
4.1
Segmentace
Jako první krok ve zpracování vstupního obrázku se vysegmentuje tvar listu do binárního obrázku. Po experimentech s Cannyho hranovým detektorem a algoritmem maximálně stabilních oblastí bylo pro segmentaci, vzhledem k ideálním podmínkám (bílé pozadí), zvoleno prahování, které má výhodu ve své výpočetní nenáročnosti. Bylo otestováno více metod volby prahu, jak je vidět na obr. 4.1.
Obrázek 4.1: Segmentace listu kaštanovníku setého (Castanea sativa) prahováním s více metodami volby prahy: Otsu, Ridler-Calvard (metoda IsoData), Zack-Rogers-Latt (metoda Triangle) a metoda založená na detekci těžiště Jako nejúčinnější metodu volby prahu byla vybrána Otsuovu metodu [19], která hledá ideální práh tak, že maximalizuje rozptyl mezi třídami, definovaný jako váženou sumu rozptylu obou tříd:
2
σ =
t X
P (i)σ12 (t)
+
i=1
I X i=t+1
13
P (i)σ22 (t).
(4.1)
14
KAPITOLA 4. ŘEŠENÍ
4.2
Odstranění řapíku
Jako další krok předzpracování bude odstraněn řapík. Tak je možné porovnat výsledky rozpoznávání listu s i bez řapíku a zkoumat tak význam řapíku. Závěr z pozorování výsledků rozpoznávání s i bez řapíku je uveden v kap. 4.4.5. Pro odstranění řapíku byly vyzkoušeny dvě metody. První metoda je založena na podílu obvodové a prostorové (Eukleidovské) vzdálenosti obvodových bodů listu a druhá na morfologické operaci otevření.
4.2.1
Poměr vzdáleností
Základní myšlenkou toho postupu je fakt, že obvodové body označující místo, kde končí řapík a začíná čepel, jsou prostorově blízké, ale jejich vzdálenost po obvodu je vyšší než u většiny prostorově si blízkých bodů. Proto hledáme, pro které dva obvodové body je podíl obvodové a prostorové vzdáleností největší. Takto je nalezeno nejužší místo řapíku, které je použito jako výchozí body pro hledání ideálního místa řezu. Z každého z bodů se postupuje směrem ke špičce listu a hledá se změna směru hranice listu, čímž se získá předpokládané místo řezu řapíku. Ideální výsledek této metody hledání řapíku je vidět na obr. 4.2 v závislosti na grafu poměru vzdáleností.
Obrázek 4.2: Obrys listu javor mléč (Acer platanoides) s výsledky detekce řapíku; Graf poměru indexové a prostorové vzdálenosti pro každý okrajový bod; zeleně jsou vyznačeny body lokace řapíku; modře body optimalizovaného řezu řapíku Bylo nutné nastavit omezující podmínky, které vycházejí s morfologie listů a částečně eliminují falešně pozitivní výsledky. Z pozorování byly vyvozeny a úspěšně aplikovány tyto omezující podmínky: • Minimální indexová vzdálenost lokačních bodů řapíku je 5% z celkového obvodu. • Maximální prostorová vzdálenost lokačních bodů řapíku je 10% z šírky listu. Tento algoritmus selhává, pokud řapík není jednoznačně oddělen a plynule přechází v čepel. Pokud řapík u listu není přítomen (přítomnost řapíku není zaručena), algoritmus často odřízne jinou signifikantní část čepele. Příklady selhání tohoto algoritmu jsou ukázány na obr. 4.3.
4.2. ODSTRANĚNÍ ŘAPÍKU
15
Obrázek 4.3: Ukázka selhání algoritmu pro odřezávání řapíku pomocí poměru vzdáleností
4.2.2
Otevření
Spolehlivější algoritmus pro odstranění řapíku jsem vyvinula pomocí morfologické operace otevření [23], což je eroze následovaná dilatací. Nejprve se otevře obrázek kruhovým jádrem o průměru s. Poté je testován rozdíl mezi původním a otevřeným obrázkem. Největší spojitá komponenta v rozdílu mezi původním a otevřeným obrázkem je prohlášena za řapík a z původního obrázku se vymaže. Po testování se osvědčilo jádro otevření o velikosti s = 0.06w, kde w je šířka, tj. kratší ze stran vstupního obrázku oříznutého o prázdné okraje.
Tento algoritmus se projevil jako robustní. V případě nepřítomnosti řapíku zpravidla odstraní šum nebo nějakou méně signifikantní část listu, většinou jednu špičku z členité čepele. Nejčastější selhání toho algoritmu nastane u listů s krátkým, silným řapíkem, který je obtížně odlišitelný od čepele listu, příp. zaměnitelný s protilehlou špičkou čepele, jak je vidět na obr. 4.4.
Obrázek 4.4: Ukázka selhání algoritmu pro odřezávání řapíku pomocí otevření
16
KAPITOLA 4. ŘEŠENÍ
4.3
Popis listu
Nyní se přistoupí k samotnému vytvoření deskriptoru pro listy dřevin, pro který byly v této práci použity Zernikovy1 momenty. Momenty obecně jsou jako hlavní nástroj pro popis listů roslin používány méně často - na rozdíl od popisu pomocí morfologických znaků nebo pomocí Fourierova deskriptoru hranice listu. Výhodou Zernikových momentů [8] je, že jsou založené na Zernikových polynomech, které jsou ortogonální na kruhu x2 + y 2 <= 1, což je pro aplikaci na popis listu dřevin výhodné. I rozložení nul v Zernikových polynomech při okraji definičního kruhu (jak je vidět na obr. 4.5), které je pro mnohé jiné aplikace nevýhodné, je pro popis listů vhodné. Proto jsem se rozhodla tuto práci založit na nich.
Obrázek 4.5: Zobrazení prvních 15 Zernikových polynomů řádu m a opakování l Pro vytvoření popisu listu je nutné zajištění invariance oproti posunutí, změně měřítka a otočení. Při rozboru úlohy bylo zvažováno, zda je nutné zajištění invariance vůči zrcadlení pro případ, kdy by byl vstupní list skenován z rubu, nikoli z líce. Po prozkoumání datasetu MEW2012 to nebylo shledáno za nutné, protože většina obsažených listů je osově symetrická nebo osové odlišnosti odpovídají diversitě v rámci druhu. Obecně existují 2 způsoby, jak získat invarianci: normováním objektu nebo normováním popisu. Z vlastností Zernikových momentů bylo zvoleno, že invariance vůči posunutí a změně měřítka bude získána normováním objektu v rámci předzpracování a invariance vůči rotaci normováním vypočtených Zernikových momentů.
4.3.1
Předzpracování
V rámci předzpracování je třeba vysegmentovaný binární obrázek normalizovat oproti posunutí a změně měřítka - a to nejen kvůli zajištění invariance, ale také kvůli definičnímu oboru Zernikových polynomů. Všechna signifikantní informace musí tudíž ležet uvnitř jednotkovém kruhu, který určuje tento definiční obor. Normalizace vůči posunutí je zaručena posunutím těžiště listu T = [xt ; yt ] do středu kruhu. Normalizace vůči změně měřítka je o něco složitější. Nejprve byl testován přístup, 1 Frits Zernike (1888 - 1966 ): nizozemský fyzik; získal v roce 1953 Nobelovu cenu za fyziku za konstrukci fázově kontrastního mikroskopu.
4.3. POPIS LISTU
17
kdy každý bod listu leží uvnitř definovaného kruhu. Jeho poloměr r tudíž byl r = max(d(T, x)), kde d(T, x) je Eukleidovská vzdálenost mezi těžištěm T a libovolným bodem listu x. Maximum vzdálenosti se ale po několika testech ukázalo jako nestabilní a citlivé na šum. Proto byla použita varianta, kdy r = k · std(d(T, x)), kde std definuje standardní směrodatnou odchylku a konstanta k určuje násobek odchylky, která optimalizuje množství bodů ležící uvnitř kruhu a body ležící vně, označené jako nesignifikantní. Poloměr založený na směrodatné odchylce je stabilnější (viz. obr. 4.6), a to i v případě, že jsou obsaženy méně signifikantní informace jako např. řapík. Tento přístup je ekvivalentní prvnímu momentu v polárních souřadnicích.
Obrázek 4.6: Způsoby normalizace vůči měřítku vstupních listu (a) do jednotkového kruhu o poloměru r, kdy (b): r = k · std(d(T, x)); k = 5.8 nebo (c): r = max(d(T, x))
Jako výchozí pro testování optimální konstanty k byla zvolena hodnota, která zaručovala, že všechny body všech listů budou ležet uvnitř definovaného kruhu: k = 7. Po mnoha testech úspěšnosti základní klasifikace se jako optimální ukázalo k = 5.8, jak je vidět na grafu 4.7. Části obrázku ležící mimo jednotkový kruh nebyly při výpočtu momentů použity.
Obrázek 4.7: Graf testování úspěšnosti konstanty k, která určuje poloměr definičního kruhu při normalizaci oproti změně měřítka.
18
KAPITOLA 4. ŘEŠENÍ
4.3.2
Výpočet
Nyní lze vypočítat Zernikovy momenty2 Aml z obrazu f (x, y) o velikosti M × N : Aml
M −1 N −1 m+1 X X ∗ Vml (r, ϕ)f (x, y), m = 0, 1, ...., l = −m, −m + 2, ..., m, = π
(4.2)
x=0 y=0
∗ (r, ϕ) je Zernikův polynom řádu m ve polárních souřadnicích (r, ϕ) kde: kde Vml p (x − xt )2 + (y − yt )2 r= rmax
a
ϕ = arctan
y − yt x − xt
(4.3)
.
(4.4)
Po předchozí normalizaci objektu platí: M = N . S přihlédnutím k vypočtení náročnosti a paměťovým nárokům výpočtu Zernikových momentů je jako maximální řád zvolen řád m = 40, přičemž platí: (m, l) = {{p, r} : p, r ∈ Z; 0 ≤ r ≤ p ≤ 40; (p + r)mod 2 = 0}.
4.3.3
Normalizace
Surový popis listu pomocí Zernikových momentů A je potřeba normalizovat oproti otočení pomocí konkrétního řádu momentu Amr lr . Fázi φ normalizačního momentu Amr lr určuje výraz: 1 Im(Amr lr ) φ = arctan , (4.5) lr Re(Amr lr ) kde jako řád normalizačního momentu je použito mr = 3 a opakování lr = 1. Normalizovaný moment Zml řádu m se vypočte Zml = Aml e−ilφ
(4.6)
a je rotačně invariantní. Z normalizovaných momentů Z : Z = {Zml } se jako deskriptor použijí jejich amplitudy aml = |Zml | (4.7) a fáze
ϕml = tan
Im(Zml ) Re(Zml )
,
(4.8)
místo jejich reálné a imaginární složky.
2 Pro testování funkčnosti algoritmu byl použit externí kód pro výpočet Zernikových momentů v Matlabu [29].
4.4. KLASIFIKACE
4.4
19
Klasifikace
Klasifikace je přiřazení dotazovaného listu k třídě z databáze, která je vyhodnocena jako dotazu nejbližší. V této práci je klasifikace dotazu dána podobnostním koeficientem, který určuje míru podobnosti dotazovaného listu se vzory v databázi. Podobnostní koeficient Dλ dvou popisů listů je vážený součet 3 jednotlivých kriterií: • rozdíl amplitud popisů da • rozdíl fází popisů dϕ • porovnání velikosti listů dv (volitelné) Váhy v součtu jednotlivých kritérií Dλ - amplituda da , fáze dϕ a velikost dv :
Dλ (a, b) = w1 da (a, b) + w2 dϕ (a, b) + w3 dv (a, b) ,
(4.9)
byly po důkladném testováním a vyhodnocení zvolena takto w1 = 1, w2 = 6.3 · 105 a w3 = 6.5 · 108 . Při klasifikaci jsou také vyřazeny listy neodpovídajícího složení (jednoduchý vs. složený list - volitelné).
4.4.1
Amplituda
Pro porovnání amplitud popisu je použit jako vzdáleností funkci kvadrát rozdílu amplitud: 40 X da (a, b) = (aml − bml )2 (4.10) m,l=0
(m+l)mod2=0
4.4.2
Fáze
Rozdíl fází popisu je počítán výrazem:
dϕ (α, β) =
40 X m,l=0
min (|αml − βml |, 2π − |αml − βml |) , m
(m+l)mod2 . =0
kde jsou rozdíly fází jednotlivých momentů vážené řádem momentů m
(4.11)
20
4.4.3
KAPITOLA 4. ŘEŠENÍ
Velikost
Velikost listu (resp. rozlišení obrázku) je volitelný vstupní parametr, který má však zásadní význam pro rozpoznávání listů. Přestože listy v rámci jednoho druhu se mohou vyskytovat ve velkém velikostním rozmezí, reálná velikost listu může být nejvýraznějším rozdílem mezi dvěma listy různých druhů s podobnou čepelí. Příkladem dvojic druhů, které jsou podle tvaru čepele zaměnitelné, ale jejich reálná velikost listu je podstatně odlišná jsou např. katalpa trubacovitá (Catalpa bignonioides s listy o šířce 10 až 19,5cm) a šeřík obecný (Syringa vulgaris - šířka: 8,5 až 3cm) nebo javor jasanolistý (Acer negundo - šířka: 2,8 až 7cm) a ořechovec vejčitý (Carya ovata - šířka: 4 až 11,3cm), jak je vidět na obr. 4.8. Právě tyto páry vyšly jako falešně pozitivní shody při testech bez porovnávání velikosti. Koeficient velikosti, který porovnává velikost dotazovaného listu a s listem z databáze b, je vypočítáván na základě Gaussovy funkce s parametry šířky vstupního listu wa a šířky porovnávaného listu wβ a jeho směrodatná odchylka wσβ šířky druhu, ke kterému přísluší list b:
−
dv (a, b) = 1 − e
(wa −wβ )2 2w2 σβ
(4.12)
Při určování koeficientu velikosti je dán prostor přírodní diversitě. Proto není uvažován výpočet velikosti listu zcela přesně a ponechána určitá míra volnosti.
(a)
(b)
(c)
(d)
Obrázek 4.8: Dvojice druhů, které vyšly jako falešně pozitivní shody, podobné tvarem čepele, ale výrazně odlišné velikostí listu: (a) Katalpa trubacovitá(Catalpa bignonioides), (b) Šeřík obecný(Syringa vulgaris), (c) Javor jasanolistý (Acer negundo) a (d) Ořechovec vejčitý (Carya ovata)
4.4.4
Složení
Pokud uživatel na vstupu spolu s obrázkem zadá i dodatečnou informaci, zda je dotazovaný list jednoduchý nebo složený, listy z databáze s nekorespondujícím složením nebudou brány v potaz. Uživatel tudíž bude pro zadání této informace motivován nejen zpřesněním výsledku, ale i urychlením výpočtu.
4.4. KLASIFIKACE
4.4.5
21
Optimalizace
Při testování bylo zjištěno, že úspěšnost klasifikace listů s optimálně uříznutým řapíkem je překvapivě v celkové míře o něco nižší, než klasifikace listů s ponechaným řapíkem. Analýza výsledků testování ukázala, že pro druhy s dostatečně členitou čepelí se odříznutím (často dlouhého a tenkého) řapíku docílilo zlepšení, ale u druhů, které mají čepel méně členitou, je řapík signifikantnější než jsem původně předpokládala. Příklady zástupce druhů, u kterých došlo po odříznutí řapíku k největšímu propadu úspěšnosti, je vidět na obr. 4.9.
(a)
(b)
(c)
(d)
(e)
Obrázek 4.9: Zástupci druhů, u který došlo po odříznutí řapíku k největšímu zhoršení úspěšnosti: (a) Řešetlák počistivý (Rhamnus cathartica), (b) Kalina vonná (Viburnum farreri), (c) Buk lesní (Fagus sylvatica), (d) Olše zelená (Alnus alnobetula) a (e) Jeřáb muk (Sorbus aria) Tyto druhy mají podobnou morfologii čepele, a tudíž zde má řapík vyšší signifikanci, než bylo původně předpokládáno. Z pozorování lze říci, že se obecně jedná hlavně o listy vejčitého tvaru bez výraznějšího pilování čepele, kde řapík (jeho délka a tvar) má větší signifikaci - na rozdíl od členitějších listů s dlouhým a nepředvídatelným řapíkem. Na grafu 4.10 je vidět zlepšení (nebo zhoršení) průměrné úspěšnosti klasifikace prvního kandidáta pro jednotlivé druhy po zavedení odřezávání řapíku.
Obrázek 4.10: Změna průměrné úspěšnosti popisu všech druhů po zavedení odřezávání řapíku ve srovnání s průměrnou směrodatnou odchylkou vzdáleností prvních třech kandidátů bez řapíku od dotazovaného listu. Analýza výsledků rozpoznávání listů s a bez řapíku ukázala, že řešením by mohlo být podmíněné odstraňování řapíku. Uvažuji, že pokud první tři kandidáti na řešení bez řapíku jsou příliš málo odlišní - poté lze prohlásit, že se jedná o podobné druhy
22
KAPITOLA 4. ŘEŠENÍ
a pak přidat signifikantní řapík - viz. algoritmus 1. Podobnost kandidátů je určována směrodatnou odchylkou jejich vzdáleností (součtů da a dϕ ) od dotazu. Algorithm 1 Algoritmus podmíněného odřezávání řapíku 1: [k1 ,k2 ,k3 ] = testBezRapiku(q) 2: d1 = d(k1 , g) 3: d2 = d(k2 , g) 4: d3 = d(k3 , g) 5: if std(d1 ,d2 ,d3 ) < T HRESHOLD then 6: [k1 ,k2 ,k3 ] = testSRapikem(q) 7: end if 8: return k1 ,k2 ,k3 Detailnější srovnání úspěšnosti klasifikace prvního kandidáta s řapíkem a bez řapíku se standardní směrodatnou odchylkou vzdálenosti od dotazu prvních třech kandidátů bez řapíku v rámci druhu řešetlák počistivý (Rhamnus cathartica), který po odříznutí řapíku v průměru zaznamenal největší propad úspěšnosti, je vidět na obr. 4.11. Z grafu je patrné, že pokud se vhodně nastaví práh směrodatné odchylky (kdy pokud listy se směrodatnou odchylkou prvních třech kandidátů bez řapíku budou pod touto hranicí, vezmou se kandidáti s řapíkem), tak úspěšnost na 72 vzorcích tohoto druhu stoupne o 5 úspěšně určených kandidátů na prvním místě.
Obrázek 4.11: Srovnání výsledků úspěšnosti klasifikace prvního kandidáta dřeviny řešetlák počistivý (Rhamnus cathartica) s řapíkem a bez řapíku se standardní směrodatnou odchylkou vzdálenosti prvních třech kandidátů bez řapíku od dotazovaného listu bez řapíku. Optimální volba prahu pro použití či odstranění řapíku byla zjištěna experimentálně. Výsledky experimentu, kdy byla zkoumána úspěšnost při všech přípustných možnostech volby prahu, jsou vidět na grafu 4.12.
4.4. KLASIFIKACE
23
Obrázek 4.12: Graf úspěšnosti při změně volby prahu pro použití řapíku: vlevo se použijí všechny listy bez řapíku, vpravo všechny s řapíkem. Červeně je vyznačena optimální hodnota prahu s nejvyšší úspěšností. Dále bylo testována úspěšnost odřezávání a neodřezávání řapíku v závislosti na normalizační konstantě k, která určuje poloměr definičního kruhu. Výsledky testování jsou vidět na grafu 4.13.
Obrázek 4.13: Graf srovnání úspěšnosti rozpoznávání bez odřezávání řapíku a s odřezáváním v závislosti na normalizační konstantě k, která určuje poloměr definičního kruhu. Za základě těchto testů byly zvoleny optimální hodnoty k pro algoritmus podmíněné odřezávání řapíku: • k = 5.6 pro popis listu bez řapíku • k = 6 pro popis list s řapíkem Přidáním této optimalizace - podmíněného odřezávání řapíku, jsem dosáhla zlepšení celkové úspěšnosti o cca. 2-3%.
24
KAPITOLA 4. ŘEŠENÍ
Kapitola 5
Implementace Implementace uváděného řešení podle zadání se dá rozdělit na dvě hlavní části: implementace hlavního algoritmu uváděného v kapitole 4 a implementace webového rozhraní. Členění implementace a návaznost jednotlivých částí je vidět na diagramu 5.1.
Obrázek 5.1: Jednotlivé části implementace: červeně - http rozhraní; modře - C++ programy
5.1
Hlavní algoritmus
Návrh řešení hlavní úlohy a testování jeho funkčnosti probíhalo ve vývojovém prostředí Matlab [15] ve stejnojmenném programovacím jazyce, který je pro technické výpočty ideální volbou. Bohužel tento jazyk je špatně přenositelný do samostatně stojícího programu potřebného pro vytvoření zadané webové aplikace. Proto bylo uznáno za nezbytně nutné přepsání našeho řešení do jazyku C++ [6]. Toto ulehčí knihovna OpenCV [12] (v. 2.1.0), která je primárně určena nejen pro zpracování obrazu, ale i pro počítačové vidění, robotiku, HCI a další. Výhodou této knihovny je její velká rozšířenost, která dala vzniknout velké spoustě kvalitních studijních materiálů [2]. Pro vývoj aplikace ve C++ bylo použito prostředí Microsoft Visual Studio 2008 Professional.
5.1.1
Členění řešení
Celé řešení je rozděleno na 4 programy, z nichž 2 budou přímou součástí finální aplikace: Test_threshold a Recognize. Zbylé dva programy jsou použity jen při přípravě: jeden vypočítá deskriptory pro celou množinu, druhý program provede základní test, kdy je každý list otestován oproti celé množině a na závěr je vyhodnocena úspěšnost. Zbylé 2 25
26
KAPITOLA 5. IMPLEMENTACE
programy jsou určeny pro koncovou aplikaci. Jedná se o program na segmentaci vstupního listu a hlavní program na klasifikaci binárního obrazu listu - jak je vidět na obr. 5.1. Program Test_threshold pro segmentaci listu má na vstupu jako parametr lokaci obrázku a volitelně jako druhý parametr práh. Tento obrázek program uloží v náhledové velikosti a v této velikosti vysegmentuje pomocí automaticky zvoleného prahu - pokud není zadán práh předem jako parametr. Vysegmentovaný obrázek uloží a na výstup vypíše hodnotu použitého prahu. int Test_threshold(string URL_img, [int threshold]); Další a poslední část řešení je program Recognize na samotné rozpoznání a klasifikaci listu. Vstupem programu je lokace vysegmentovaného obrázku, který uložila předchozí část programu. Volitelně může být vložen i parametr určující rozlišení obrázku, který byl buď zadán přímo uživatelem nebo byl vypočítán z vložené reálné velikosti vloženého obrázku. Dalším volitelným parametrem je složení listu (jednoduchý vs. složený). Listu na tomto obrázku je odstraněn řapík (pokud je vyžadováno - viz. kap. 4.4.5) a list je následně normován, jak je uvedeno v kap. 4.3.1. Poté se přistoupí k samotnému výpočtu popisu pomocí předpočtených koeficientů Zernikových polynomů. Výsledná amplituda a fáze popisu je porovnána s databází jak je uvedeno v kap. 4.4 a na výstupu je vypsáno 5 ID druhů kandidátů. Detaily implementace jsou v dokumentaci ke kódu na přiloženém DVD - viz. příloha B. int[] Recognize(string URL_bin_img, int res = -1, int simple = {-1, 0, 1}); Kompilace zdrojových kódů pro server je popsána v kap. 5.3.3.
5.1.2
Převod dat
Nezbytnou součástí přepsání algoritmu do C++ bylo převedení generovaných dat z Matlabu, který uchovává data ve formátu MAT. Toho bylo docíleno přegenerování dat do formátu YAML1 , který je do OpenCV dobře importovatelný.
5.2
Webové rozhraní
Uživatelské rozhraní webové aplikace je jednoduché obalení zkompilovaných částí hlavního programu a zajišťuje prvotní zpracování dotazů od uživatele. Uživatelem vložený obrázek se nejprve uloží na disk serveru do cache a zároveň se uloží informace do databáze o novém požadavku. Webová aplikace poté začne fungovat i jako obslužná aplikace hlavního programu, když se zavolá automatické prahování vstupního obrázku. Na základě výstupu z programu prahování se uživateli předloží automatický výsledek a čeká se na schválení či opravu prahu. Mezitím je uživatel dotazován na mimoobrazové informace - velikost listu (příp. vzorkování) a složení listu. Obě tyto dodatečné volitelné informace značně zpřesňují výsledek celého hlavního programu, takže jsou tyto dotazy podány uživateli jasně a jednoduše, ale nenásilně. 1
’YAML Ain’t Markup Language’ - dobře čitelný formát pro serializace strukturovaných dat
5.2. WEBOVÉ ROZHRANÍ
(a)
27
(b)
Obrázek 5.2: Screenshoty: (a) vložení vstupního listu, (b) zadání dodatečné informace o složení listu Po zadání (nebo přeskočení) dotazovaných vstupních parametrů je zavolán hlavní program rozpoznávání. Výsledek hlavního programu je pět kandidátů (ID jejich botanických druhů), kteří jsou uživateli předloženi spolu s reprezentativními zástupci - obrázkem jejich listu a odkazem na českou, příp. anglickou, mutaci internetové encyklopedie Wikipedia. Uživatel má následně možnost výsledek klasifikace verifikovat. Výsledek klasifikace i případné verifikace se ukládá do databáze pro budoucí zpracování.
(a)
(b)
Obrázek 5.3: Screenshoty: (a) možnost pro opravu automatické volby prahu a nepovinné zadání rozlišení, resp. reálně velikosti snímku, (b) zobrazení navrhovaných kandidátů a případná verifikace výsledků uživatelem Webová aplikace je vytvořena v jazyku PHP [9] (v.5.3.3) s JS2 rozšířením jQuery (v.1.8.3). Jako databázové úložiště pro logování požadavků, výstupu jejich zpracovaní a jeho případná verifikace byla použita relační databáze MySQL (viz. kap. 5.3.2). Pro vývoj webu bylo použito prostředí Netbeans 7.1. 2
JavaScript
28
5.3 5.3.1
KAPITOLA 5. IMPLEMENTACE
Deployment Server
Server, na kterém běží ukázkové řešení aplikace, mi byl poskytnut díky ÚTIA AV ČR na adrese: http://leavesv.utia.cas.cz/ Server běží na operačním systému CentOS na bázi Linuxu. Použitý softwarový webový server je Apache v.2.2.3.
5.3.2
Databáze
Pro logování požadavků na server byla použita externí MySql databáze. Schéma této jednoduché databáze je vidět na obr. 5.4.
Obrázek 5.4: Model použité databáze
5.3.3
Kompilace
Samostatně řešeným problém byla kompilace zdrojových kódů v C++ pro server, který běží na operačním systému na bázi Linuxu. Nejprve jsem chtěla využít zásuvný modul VisualGDB[17] pro Visual Studio 2008, který zajišťuje cross-kompilaci z Windows systému do Linuxového stroje emulovaného pomocí VirtualBoxu [18]. Tento zásuvný modul funguje dobře, má dobrou možnost debugování při běhu pod Linuxem a velké možnosti konfigurace buildování pro optimální běh aplikace. Při použití tohoto plug-inu je ale problematické připojení knihoven OpenCV. Proto nakonec bylo zvoleno prosté kompilování zdrojových kódů na cílovém serveru pomocí GCC, což je nejjednodušší cesta, ale zároveň to neposkytuje takové možnosti konfigurace buildování jako Visual Studio.
Kapitola 6
Výsledky Výsledky algoritmu popisovaného v kapitole 4 pro dataset MEW2012 a Flavia jsou v tabulce 6.1 a úspěšnost klasifikace reálné implementace se může mírně lišit. A to i z toho důvodu, že finální implementace podléhá požadavkům na rychlost a efektivitu běhu aplikace. Pro MEW2012 jsou zobrazeny výsledky se zadáním vstupních parametrů velikost a složení i bez nich. Pro dataset Flavia je uvažován jen vstupní parametr velikosti, protože informace o složení nejsou známy.
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
% % % % % % % % % %
84.15 92.57 95.24 96.86 97.85 98.51 98.90 99.15 99.27 99.39
% % % % % % % % % %
70.27 82.13 87.08 89.63 91.62 93.21 94.36 95.26 95.98 96.46
% % % % % % % % % %
86.90 94.15 96.55 97.88 98.67 99.05 99.29 99.49 99.55 99.64
% % % % % % % % % %
∅ 84,13 92,33 95,93 97,80 98,27 99,27 99,33 99,40 99,47 99,53
Velikost
Velikost + Složení
Flavia
Složení
∅ 67.65 79.17 84.64 87.54 89.54 91.28 92.41 93.31 94.04 94.78
Velikost
počet kandidátů
MEW2012
% % % % % % % % % %
84,53 92,40 95,93 97,80 98,40 99,20 99,27 99,33 99,40 99,47
% % % % % % % % % %
Tabulka 6.1: Výsledná úspěšnost klasifikace pro datasety MEW2012 a Flavia podle počtu kandidátů a dodatečných vstupních parametrů Detailnější výsledky v grafech pro oba datasety jsou uvedeny v následujících podkapitolách. Z uvedených grafů je patrný vliv zadání vstupních parametrů na celkovou úspěšnost klasifikace a také míra zlepšení úspěšnosti klasifikace po zavedení podmíněného odřezávání řapíku uvedeném v kap. 4.4.5. 29
30
6.1
KAPITOLA 6. VÝSLEDKY
Dataset MEW2012
Obrázek 6.1: Graf úspěšnosti klasifikace datasetu MEW2012 v závislosti na počtu kandidátů při různých vstupných parametrech. Uváděná úspěšnost je celková úspěšnost klasifikace. V grafu 6.2 jsou uvedeny úspěšnosti pro jednotlivé druhy dřevin v rámci datasetu MEW2012 a je z něho patrné, že se úspěšnost klasifikace mezi jednotlivými druhy podstatně liší. Pro druhy javor dlanitolistý (Acer palmatum), javor stříbrný (Acer saccharinum), ambroň západní (Liquidambar styraciflua) a loubinec trojlaločný (Parthenocissus tricuspidata) je úspěšnost rozpoznání na testované množině 100%. Naopak pro druh mišpule obecná (Mespilus germanica) je úspěšnost rozpoznání jen 12%, pro bez černý (Sambucus nigra) jen 16,2% a pro zimolez zákrovnatý (Lonicera involucrata) 18,2%.
Obrázek 6.2: Graf úspěšnosti rozpoznávání jednotlivých druhů datasetu MEW2012 bez zadání vstupních parametrů Fatální selhání u některých druhů se podařilo částečně eliminovat zadáním vstupních parametrů o složení listu a rozlišení snímku (resp. reálná velikost listu) jak je vidět v grafu 6.3.
6.1. DATASET MEW2012
31
Obrázek 6.3: Graf úspěšnosti rozpoznávání jednotlivých druhů datasetu MEW2012 se zadáním vstupních parametrů rozlišení a složení listu
6.1.1
Výsledky optimalizace
Zlepšení po zavedení podmíněného odřezávání řapíku popsaném v kap. 4.4.5 je vidět v grafu 6.4.
Obrázek 6.4: Porovnání úspěšnosti s podmíněným odřezávání řapíku, s permanentním odřezáváním a bez něj pro dataset MEW2012
32
6.2
KAPITOLA 6. VÝSLEDKY
Dataset Flavia
V grafu 6.5 jsou zobrazeny hodnoty úspěšnosti klasifikace v rámci datasetu Flavia při zadání vstupní velikosti a bez něj.
Obrázek 6.5: Graf úspěšnosti klasifikace datasetu Flavia v závislosti na počtu kandidátů při zadání velikosti a bez něj. Z grafu je patrné, že zadání velikosti nemá na zlepšení úspěšnosti klasifikace nijak významný vliv jako tomu je u datasetu MEW2012. Lze předpokládat, že to je dáno tím, že jednotlivé druhy v rámci datasetu Flavia jsou dostatečně rozlišitelné i bez použití reálné velikosti, a tudíž v tomto datasetu jsou minimalizovány falešně pozitivní shody popsané v kap. 4.4.3.
6.2.1
Výsledky optimalizace
Obrázek 6.6: Porovnání úspěšnosti s podmíněným odřezávání řapíku, s permanentním odřezáváním a bez něj pro dataset Flavia
Kapitola 7
Závěr Cílem této práce je vytvořit webovou aplikaci, která by byla laickému uživateli nápomocná při rozpoznávání dřevin rostoucích na území České republiky. Za tímto účelem byl po nastudování dosavadních postupů vyvinut algoritmus na základě Zernikových momentů, které se na aplikace rozpoznávání listů dosud příliš nepoužívaly. Dosud se momenty obecně používali při rozpoznávání listů rostlin hlavně jako jeden z mnoha příznaků. V této práci jsem se založila popis listu dřeviny jen na momentech. Lze prohlásit, že se tento úkol v rámci možností zdařil, i když lze zpětně říci, že v přístupu popsaném v této práci jsou hlediska, která nebyla dostatečně zohledněna a v budoucí práci se lze mnohému poučit a vyvarovat se tak zbytečných chyb a časových prodlení. Během návrhu algoritmu se také potvrdilo, že je nevyhnutelné každou hypotézu či navrhovaný postup podložit průkazným testem. V práci se podařilo dobře zmapovat problematiku míry signifikance řapíku. Budoucí práce by zahrnouvala analýzu příčin, proč u některých konkrétních druhů klesá úspěšnost klasifikace. Také rychlost odezvy koncové aplikace by mohla být předmětem dalšího zlepšování. Při porovnání dosažených výsledků v testování úspěšnosti klasifikace našeho algoritmu s výsledky dosaženými jinými projekty je nutno poukázat na to, že míru efektivity značně ovlivňuje použitý dataset. I z našich výsledků je patrné, že celková úspěšnost klasifikace se může podle použitého datasetu lišit až o 20%. Na datasetu Flavia jsme dosáhli úspěšnosti klasifikace 84,13% pro prvního kandidáta, což je srovnatelný výsledek s projekty srovnatelné s touto prací. Na novém datasetu MEW2012, který výborně mapuje dřeviny dané v zadání, bylo dosaženo bez zadání dodatečných vstupních parametrů úspěšnosti klasifikace 67,65%, což se nemusí na první pohled jevit jako uspokojivý výsledek. Nicméně, je nutno vzít v potaz fakt, že dataset má 151 tříd s celkem 9745 zástupci. Další projekt s minimálně takto rozmanitým datasetem je projekt Leafsnap [14], který na 184 třídách s celkově 23915 skenovanými a 5192 mobilem vyfocenými vzorky dosahuje úspěšnosti klasifikace prvního kandidáta cca. 72%. Nutno podotnout, že Leafsnap je veliký projekt zaštítěný americkými univerzitami Columbia University, University of Maryland a ústavem Smithsonian Institution. U našeho řešení v případě zadání vstupních parametrů jako je rozlišení snímku (resp. jeho reálná velikost) a složení listu (jednoduchý vs. složený) úspěšnost klasifikace prvního kandidáta v našem projektu vzroste na 86.9%, pro první tři kandidáty na 96.55% - což je dobrý výsledek. Vložení těchto dodatečných parametrů není problematické ani pro laika a navíc jejich zadávání bylo maximálně zjednodušeno pomocí webového rozhraní. 33
34
KAPITOLA 7. ZÁVĚR
Všechny požadavky na server jsou zaznamenávány a mohou být použity pro další práci.
Příloha A
Seznam druhů datasetu MEW2012 Rod latinsky
Druh latinsky
Rod česky
Druh česky
Acer
campestre ginnala negundo palmatum platanoides pseudoplatanus saccharinum saccharum tataricum deliciosa glabra hippocastanum octandra pavia altissima alnobetula glutinosa incana fruticosa thunbergii vulgaris nana papyrifera pendula pubescens davidii sempervirens arborescens betulus ovata sativa bignonioides occidentalis japonicum vitalba arborescens alba mas sanguinea avellana colurna maxima coggygria horizontalis integerrimus monogyna mezereum scabra angustifolia europaea verrucosa sylvatica aubertii intermedia alnus excelsior ornus biloba
Javor
babyka amurský jasanolistý dlanitolistý mléč klen stříbrný cukrový tatarský ovocná lysý maďal žlutý pávie žláznatý zelená lepkavá šedá křovitý Thunbergův obecný zakrslá papírovitá bělokorá pýřitá Davidova vždyzelený stromovitý obecný vejčitý setý trubacovitá západní japonský plotní mechýřník bílá obecný krvavá obecná turecká největší vlasatá vodorovný celokrajný jednosemenný jedovatý
Actinidia Aesculus
Ailanthus Alnus
Amorpha Berberis Betula
Buddleja Buxus Caragana Carpinus Carya Castanea Catalpa Celtis Cercidiphyllum Clematis Colutea Cornus
Corylus
Cotoneaster Crataegus Daphne Deutzia Elaeagnus Euonymus Fagus Fallopia Forsythia Frangula Fraxinus Ginkgo
Aktinídie Jírovec
Pajasan Olše
Netvařec Dřišťál Bříza
Komule Zimostráz Čimišník Habr Ořechovec Kaštanovník Katalpa Břestovec Zmarličník Plamének Žanovec Svída Dřín Svída Líska
Ruj Skalník Hloh Lýkovec Hlošina Brslen
úzkolistá evropský bradavičnatý lesní čínská prostřední olšová ztepilý zimnár dvoulaločný
Buk Opletka Zlatice Krušina Jasan Jinan
dřevina
list
počet
strom strom strom strom strom strom strom strom strom liána strom strom strom strom strom strom strom strom keř keř keř strom strom strom strom keř strom / keř strom / keř strom strom strom strom strom strom liána keř strom / keř strom / keř strom / keř keř strom keř strom / keř keř keř strom / keř keř keř strom / keř strom / keř keř strom liána keř strom / keř strom strom / keř strom
J J J J J J J J J J S S S S S J J J S J J J J J J J J S J S J J S J J S J J J J J J J J J J J J J J J J J J J S S J
65 63 63 97 61 61 64 54 70 51 58 63 51 54 62 60 72 62 69 64 62 61 68 62 52 55 65 62 65 56 62 53 64 55 76 68 65 51 65 55 63 63 54 54 59 66 69 62 64 61 64 63 54 72 82 60 60 62
Tabulka A.1: Latinské a české názvy listnatých dřevin z datasetu MEW2012 s typem dřeviny, typem listu (Jednoduchý × Složený) a četností vzorků - část 1
35
36
PŘÍLOHA A. SEZNAM DRUHŮ DATASETU MEW2012
Rod latinsky
Druh latinsky
Rod česky
Druh česky
Gleditsia Gymnocladus Hamamelis Hedera
triacanthos dioicus virginiana helix helix syriacus rhamnoides lupulus japonica aquifolium cinerea nigra regia japonica paniculata amabilis anagyroides angustifolia palustre ovalifolium vulgare styraciflua tulipifera involucrata tatarica xylostea europaeus barbarum pomifera F pomifera M aquifolium germanica alba oleander inserta tricuspidata tomentosa amurens coronarius opulifolius hispanica canescens tremula armeniaca laurocerasus mahaleb padus spinosa pterocarpa coccinea cerris frainetto petraea pubescens robur rubra cathartica hirta alpinum pseudacacia viscosa caprea nigra racemosa japonica sorbifolia aria aucuparia intermedia torminalis japonica salicifolia vanhouttei pinnata albus orbiculatus vulgaris cordata tomentosa glabra laevis minor myrtillus uliginosum vitis-idaea farreri lantana opulus pragense rhytidophyllum minor vinifera florida sinensis serrata
Dřezovec Nahovětvec Vilín Břečťan
trojtrnný dvoudomý viržinský popínavý (plodící) popínavý (neplodící) syrský řešetlákový otáčivý japonský ostrolistá popelavý černý královský japonská latnatý krásná odvislý lékařská bahenní vejcitolistý obecný západní tulipánokvetý zákrovnatý tatarský obecný evropský cizí oranžová (samicí) oranžová (samčí) cesmínolistá obecná bílý obecný popínavý trojlaločný plstnatá amurský vencový kalinolistá javorolistý šedý osika obecná lékařská turecká obecná obecná jasanolistá šarlatová cer balkánský zimní pýřitý letní červený počistivý orobincová alpínský akát lepkavý jíva černý červený japonský jeřábolistý muk ptačí prostřední brek japonský vrbolistý van Houtteuv zpeřený hroznatý červenoplodý obecný srdčitá stříbrná horský vaz habrolistý borůvka bahenní brusinka vonná tušalaj obecná pražská vrásčitolistá barvínek vinná růžová čínská ostrolistá
Hibiscus Hippophae Humulus Chaenomeles Ilex Juglans
Kerria Koelreuteria Kolkwitzia Laburnum Lavandula Ledum Ligustrum Liquidambar Liriodendron Lonicera
Loranthus Lycium Maclura Mahonia Mespilus Morus Nerium Parthenocissus Paulownia Phellodendron Philadelphus Physocarpus Platanus Populus Prunus
Pterocarya Quercus
Rhamnus Rhus Ribes Robinia Salix Sambucus Sophora Sorbaria Sorbus
Spiraea
Staphylea Symphoricarpos Syringa Tilia Ulmus
Vaccinium
Viburnum
Vinca Vitis Weigela Wisteria Zelkova
Ibišek Rakytník Chmel Kdoulovec Cesmína Ořešák
Zákula Svitel Kolkvicie Štedrenec Levandule Rojovník Ptačí zob Ambroň Liliovník Zimolez
Ochmet Kustovnice Maklura Mahónie Mišpule Morušovník Oleandr Loubinec Paulovnie Korkovník Pustoryl Tavola Platan Topol Merunka Bobkovišen Višen Střemcha Trnka Lapina Hlohyně Dub
Rešetlák Škumpa Rybíz Trnovník Vrba Bez Jerlín Tavolníkovec Jeřáb
Tavolník
Klokoč Pámelník Šeřík Lípa Jilm
Brusnice Vlochyně Brusnice Kalina
Brčál Réva Weigelie Vistárie Zelkova
dřevina
list
počet
strom strom strom liána liána keř strom / keř liána keř strom / keř strom strom strom keř strom keř strom / keř keř keř keř keř strom strom keř keř keř keř keř strom / keř strom / keř keř strom / keř strom strom / keř liána liána strom strom keř keř strom strom strom strom strom / keř strom / keř strom / keř strom / keř strom strom strom strom strom strom strom strom strom / keř strom / keř keř strom strom / keř strom / keř strom / keř keř strom / keř keř strom strom strom strom keř keř keř strom / keř keř keř strom / keř strom strom strom strom strom keř keř strom keř strom / keř keř keř strom / keř liána liána keř liána strom
S S J J J J J J J J S S S J S J S J J J J J J J J J J J J J J J J J S J J J J J J J J J J J J J S J J J J J J J J S J S S J S S S S J S J J J J J S J J J J J J J J J J J J J J J J J J J S J
70 66 54 65 62 56 61 63 52 73 60 78 64 70 64 66 69 58 73 63 62 52 66 77 72 60 78 65 52 69 68 50 99 58 54 52 53 70 64 62 52 60 64 61 66 70 53 74 64 63 67 50 63 55 62 73 72 64 83 62 71 62 68 69 65 62 61 60 66 65 69 67 65 75 69 74 62 59 51 53 60 68 60 69 74 65 54 69 58 67 63 62 82 66 67
Tabulka A.2: Latinské a české názvy listnatých dřevin z datasetu MEW2012 s typem dřeviny, typem listu (Jednoduchý × Složený) a četností vzorků - část 2
Příloha B
Obsah příloženého DVD • cpp: C++ kódy – doc: HTML generovaná dokumentace k C++ kódům • mat: MATLAB kódy testovaného algoritmu • text: celý text diplomové práci v PDF – lateX: LATEXzdrojové kódy k textu • www: php a html kódy webového rozhraní – db: SQL záloha databáze • zadani: PDF s oficiálním zadáním práce
37
38
PŘÍLOHA B. OBSAH PŘÍLOŽENÉHO DVD
Literatura [1] C. ArunPriya, T. Balasaravanan, and A. S. Thanamani. An efficient leaf recognition algorithm for plant classification using support vector machine. PRIME 2012 International Conference, pages 428 – 432, 2012. http://arxiv.org/pdf/0707.4289.pdf. [2] G. Bradski and A. Kaehler. Learning OpenCV. O’Reilly Media, 2008. [3] Y. Chen, P. Lin, and Y. He. Velocity representation method for description of contour shape and the classification of weed leaf images. Biosystems Engineering, 109(3):186–195, 2011. [4] J. S. Cope and P. Remagnino. Classifying plant leaves from their margins using dynamic time warping. Advanced Concepts for Intelligent Vision Systems, 7517:258– 267, 2012. [5] J. S. Cope and P. Remagnino. Utilizing the hungarian algorithm for improved classification of high-dimension probability density functions in an image recognition problem. Advanced Concepts for Intelligent Vision Systems, 7517:268–277, 2012. [6] cplusplus.com. C++ Language Tutorial, 1.12.2012. http://www.cplusplus.com/doc/tutorial/. [7] Dominika Dobrylovská. Klíč k určování stromů - 123 nejběžnějších stromů v ČR, 2012. [8] J. Flusser, T. Suk, and B. Zitová. Moments and Moment Invariants in Pattern Recognition. Wiley, 2009. [9] T. P. Group. PHP manual. http://php.net/manual/en/index.php. [10] H. Hajjdiab and lman AI Maskari. Plant species recognition using leaf contours. IEEE International Conference, 2011. [11] Ing. Petra Krejčí, Ph.D. Multimediální učební text Obecná botanika, 1.2.2011. http://web2.mendelu.cz/af_211_multitext/obecna_botanika/. [12] Intel Corporation, Willow Garage. OpenCV, 1.12.2012. http://docs.opencv.org/. [13] A. Kadir, L. E. Nugroho, A. Susanto, and P. I. Santosa. Experiments of zernike moments for leaf identification. Journal of Theoretical and Applied Information Technology, 41(1):82–93, 2012. 39
40
LITERATURA
[14] N. Kumar, P. N. Belhumeur, A. Biswas, D. W. Jacobs, W. J. Kress, I. Lopez, , and J. V. B. Soares. Leafsnap: A computer vision system for automatic plant species identification. ECCV 2012, pages 502–516, 2012. http://homes.cs.washington.edu/~neeraj/papers/nk_eccv2012_leafsnap. pdf. [15] MathWorks. Matlab Documentation, 1.2.2011. http://www.mathworks.com/help/techdoc/. [16] I. Musil and J. Möllerová. Listnaté dřeviny - Přehled dřevin v rámci systému rosrlin krytosemenných. 2005. http://lesaci.me.cz/borova_siska/materialy/dendrologie/skripta_2.pdf. [17] S. OÜ. Visualgdb - integrate gcc and gdb in visual studio. http://visualgdb.com/. [18] Oracle. Visualbox. https://www.virtualbox.org/. [19] N. Otsu. A threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man, and Cybernetics, 9(1):62–66, 1979. [20] E. J. Pauwels, P. M. de Zeeuw, and E. B. Ranguelova. Computer-assisted tree taxonomy by automated image recognition. Engineering Applications of Artificial Intelligence, 22(1):26–31, 2009. http://oai.cwi.nl/oai/asset/13914/13914D.pdf. [21] Přírodou.cz: Atlas rostlin. Klíč k určení, naposledy navštíveno 25.10.2012. http://rostliny.prirodou.cz/klic/. [22] L. Úradníček, P. Maděra, S. Tichá, and J. Koblížek. Dřeviny ČR. Lesnická práce, 2010. [23] F. Y. Shih. Image Processing and Pattern Recognition: Fundamentals and Techniques. Wiley-IEEE Press, 2010. [24] T. Sixta. Image and video-based recognition of natural objects. Master’s thesis, FEL ČVUT, 2011. http://cyber.felk.cvut.cz/research/theses/detail.phtml?id=153. [25] Steve Nix. Tree Identification Using a Tree Leaf Key - A Quick and Easy Way to Identify 50 Common North American Trees, naposledy navštíveno 27.10.2012. http://forestry.about.com/od/treeidentification/tp/tree_key_id_start. htm. [26] The Encyclopedia of House Plants. Plant identification guide, naposledy navštíveno 26.10.2012. http://www.gflora.com/index.php?cmd=def. [27] The Natural History Museum, London. Tree identification key, naposledy navštíveno 26.10.2012. http://www.nhm.ac.uk/nature-online/british-natural-history/ urban-tree-survey/identify-trees/tree-key/index.html.
LITERATURA
41
[28] Weed Science of University of Missouri. Weed ID Guide, naposledy navštíveno 26.10.2012. http://weedid.missouri.edu/index.cfm. [29] C. Wolf. Matlab code for zernike moments. http://liris.cnrs.fr/christian.wolf/software/zernike/. [30] S. G. Wu, F. S. Bao, E. Y. Xu, Y.-X. Wang, Y.-F. Chang, and Q.-L. Xiang. A leaf recognition algorithm for plant classification using probabilistic neural network. IEEE International Symposium, 2007. http://flavia.sf.net/. [31] S. G. Wu, F. S. Bao, E. Y. Xu, Y.-X. Wang, Y.-F. Chang, and Q.-L. Xiang. Dataset flavia, Naposledy navštíveno 7.10.2012. http://flavia.sf.net/. [32] L.-W. Yang and X.-F. Wang. Leaf image recognition using fourier transform based on ordered sequence. ICIC 2012, 7389:393–400, 2012. [33] M. zemědělství ČR. Zpráva o stavu lesa a lesního hospodářství České republiky v roce 2010, Naposledy navštíveno 7.10.2012. http://www.uhul.cz/zelenazprava/2010/zz2010.pdf.
