NAIL072 ROZPOZNÁVÁNÍ VZORŮ

NAIL072 – ROZPOZNÁVÁNÍ VZORŮ RNDr. Jana Štanclová, Ph.D. [email protected] www.cuni.cz/~stancloj LS Zk 2/0

OSNOVA 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

Úvod do rozpoznávání vzorů Bayesovská teorie rozpoznávání Diskriminační funkce Odhady parametrů Lineární klasifikátory Nelineární klasifikátory Rozpoznávání v řetězcích Template matching Strukturální rozpoznávání Rozhodovací stromy Klastrování

Jana Štanclová, [email protected]

2/44

LITERATURA

•

Richard O. Duda, Peter E. Hart, David G. Stork – Pattern Classification – Second Edition, A Wiley-Interscience Publication, 2000

•

Sergios Theodoridis, Konstantinos Koutroumbas – Pattern Recognition – Second Edition, Elsevier Academic Press, 2003 – Third Edition, Academic Press, 2006

•

Evangelia Micheli-Tzanakou – Supervised and Unsupervised Pattern Recognition, Feature Extraction and Computational Intellingence, – CRC Press, 2000


3/44

ROZPOZNÁVÁNÍ VZORŮ


4/44


•

rozpoznávání vzorů – ekvivalent anglického pattern recognition – dříve (60. a 70. léta) zazníval pojem rozpoznávání obrazců • zřejmě: pattern recognition = распознавание образцов


5/44


•

člověk umí – – – –

rozpoznat obličeje rozumět mluveným slovům číst ručně psaný text dotykem rozpoznat klíč v kapse

→

proces rozpoznávání

•

rozpoznávání (pattern recognition) → klasifikace objektů do tříd

•

objekty = obrázky, signály, ... podle aplikace → obecně vzory (patterns)


6/44

TROŠKA HISTORIE 1

•

západní svět – Platón • základy rozpoznávání

– rozšířeny Aristotelem • esenciální (základní) a druhotné vlastnosti • rozpoznávání vzorů → nalezení esenciální vlastnosti

•

východní svět – filozofická epistemologie → nauka o přirozenosti vědění • patriarcha Bodhidharma ze Zenu → konfrontace procesů v mysli, identifikace objektů a klasifikace


7/44

TROŠKA HISTORIE 2

•

novověk – před rokem 1960 • rozpoznání → výstup teoretického výzkumu v oblasti statistiky

– rozvoj počítačů • potřeba aplikací na rozpoznávání vzorů

→ požadavek na další teoretický rozvoj

– rozpoznávání vzorů → součást systémů strojového vnímání (machine intelligence) • rozhodovací systémy


8/44

APLIKACE


9/44

APLIKACE ROZPOZNÁVÁNÍ VZORŮ 1 •

„machine vision“ – snímání obrázků kamerou – analýza → popis scény

•

počítačová diagnóza – pomáhá doktorům dělat rozhodnutí – nevýhoda • medicínská data nejsou vždy dobře interpretovatelná

– příklad: rentgenová mamografie • rozpoznávací systém → rozpoznání rakoviny prsu (suplování dalšího doktora)


10/44

APLIKACE ROZPOZNÁVÁNÍ VZORŮ 2 •

rozpoznávání řeči – dlouho neřešitelné – rozpoznání textu a převod do ASCI znaků

•

rozpoznávání znaků ... OCR (optical character recognition) – tiskací písmena: komerčně dostupné – 1. detektor citlivý na světlo • převod intenzity světla do čísel → obraz

– 2. čárová a znaková segmentace obrazu – 3. klasifikace znaku do třídy (číslo/písmeno/punkce) – 4. uložení „rozpoznané třídy“ → zahození naskenovaného obrazu – výhody • snadné další zpracování • efektivní uložení Jana Štanclová, [email protected]

11/44

APLIKACE ROZPOZNÁVÁNÍ VZORŮ 3

•

rozpoznávání ručně psaných textů

•

online rozpoznávání ručně psaných textů


12/44

APLIKACE ROZPOZNÁVÁNÍ VZORŮ 3

•

rozpoznávání ručně psaných textů – čtení bankovních šeků • strojové rozpoznávání částky • ověření podpisu → praxe: strojově rozpoznána zhruba polovina šeků (zbytek ručně)

– automatické třídící stroje na poštách • třídění dopisů podle PSČ

•

online rozpoznávání ručně psaných textů – tužkové počítače • vstup → psaní textu na displej


13/44

VYTVOŘENÍ KLASIFIKÁTORU


14/44

POJMY Z TEORIE SYSTÉMŮ

•

objekt – zkoumání složitého jevu → omezení se jen na část, která nás zajímá

•

pozadí – vše, co nás z daného jevu nezajímá

•

rozlišovací úroveň – objekty složité → typicky se nezkoumají celé – výběr zajímavých vlastností → ty se měří a zkoumají – různá rozlišovací úroveň → různý popis a chápání objektů


15/44

JAK POPSAT OBJEKTY? 1

•

popis objektů – snaha o exaktní popis objektů pomocí nástrojů matematiky

•

1. matematické modelování – objekt popsán pomocí matematických rovnic – hledání relace mezi vstupem a výstupem – problém • vytvořit matematický model (např. model fungování mozku)


16/44

JAK POPSAT OBJEKTY? 2

•

2. rozpoznávání – alternativa k matematickému modelování – menší porozumění objektu – rozhodovací pravidlo → zařazování objektů do předem známých tříd • třídy ekvivalence (reflexivita, symetrie, tranzitivita)

– objekty podobnější uvnitř tříd než mezi třídami navzájem – výhoda • při vytváření klasifikátoru není nutné rozumět složité podstatě objektů, které se budou klasifikovat • rozhodovací pravidlo lze naučit empiricky z naměřených dat – trénovací vzory


17/44

UČENÍ KLASIFIKÁTORU •

učení s učitelem – učitel → informace o správné kategorii či chybě klasifikace pro každý trénovací vzor

•

učení bez učitele (klastrování) – není známa správná kategorie či chyba klasifikace – vytváření „přirozených shluků“ vstupních vzorů


18/44

ILUSTRAČNÍ PŘÍKLAD •

třídění ulovených ryb: losos × mořský okoun Získání formálního popisu 1. snímání dat (např. kamerou) 2. předzpracování dat • • •

3.

nastavení průměných intenzit světla odstranění pozadí izolace obrazu jediné ryby

extrakce vybraných příznaků

Klasifikace • rozhodnutí, co to je za rybu


19/44

JAK UDĚLAT KLASIFIKÁTOR? 1 •

externí informace „okouni jsou větší než lososi“ – klasifikace → délka ryby – hledání kritické délky l* na základě trénovacích vzorů

•

histogram délek

→ ??


20/44


externí informace „okouni jsou větší než lososi“ – klasifikace → délka ryby – hledání kritické délky l* na základě trénovacích vzorů

•

histogram délek

→ průměrně „losos kratší“ → jako samostatné kritérium to nestačí


21/44


jiný příznak – barva šupin ryby – problém při předzpracování – změna osvětlení může změnit barvu šupin – hledání kritické světlosti x* na základě trénovacích vzorů


22/44


jiný příznak – barva šupin ryby – problém při předzpracování – změna osvětlení může změnit barvu šupin – hledání kritické světlosti x* na základě trénovacích vzorů

•

histogram světlosti šupin ryb

→ lepší klasifikátor → třídy lépe oddělené


23/44

CENA ŠPATNÉHO ROZHODNUTÍ •

špatné rozhodnutí při klasifikaci – kousek lososa v konzervě okouna → „může být“ – kousek okouna v konzervě lososa → „špatné“ → redukce počtu špatně klasifikovaných okounů – řešení: ??


24/44


špatné rozhodnutí při klasifikaci – kousek lososa v konzervě okouna → „může být“ – kousek okouna v konzervě lososa → „špatné“ → redukce počtu špatně klasifikovaných okounů – řešení: posunutí rozhodovací hranice do světlejších barev


25/44


špatné rozhodnutí při klasifikaci – kousek lososa v konzervě okouna → „může být“ – kousek okouna v konzervě lososa → „špatné“ → redukce počtu špatně klasifikovaných okounů – řešení: posunutí rozhodovací hranice do světlejších barev

•

teorie rozhodování – celková cena spojená s rozhodnutím – cíl: najít rozhodovací pravidlo minimalizující cenu klasifikace


26/44

VÝBĚR VÍCE PŘÍZNAKŮ •

•

více příznaků – x1 ... barva šupin – x2 ... šířka ryby

příznaky → 2D-prostor příznaků – rozdělení prostoru na dvě oblasti (oblast lososa a oblast okouna)


27/44

VÝBĚR VÍCE PŘÍZNAKŮ •

•

více příznaků – x1 ... barva šupin – x2 ... šířka ryby

příznaky → 2D-prostor příznaků – rozdělení prostoru na dvě oblasti (oblast lososa a oblast okouna)

→ celková cena klasifikátoru menší než u jednoho příznaku


28/44

DALŠÍ VÝVOJ KLASIFIKÁTORU 1.

další příznaky - poloha očí, úhel hřbetní ploutve, ...

2.

komplexnější rozhodovací kritérium - ne přímka → složitější křivka


29/44



2.



30/44



2.


→ správná klasifikace „známých“ ryb → špatná klasifikace „neznámých“ ryb


→ problém generalizace klasifikátoru

31/44

LEPŠÍ GENERALIZACE KLASIFIKÁTORU •

více trénovacích vzorů (pokud jsou k dispozici) –

•

lepší oddělení tříd

nepožadovat příliš složitá rozhodovací kritéria – –

trénovací data → slabší výkon celková generalizace → lepší


32/44

LEPŠÍ GENERALIZACE KLASIFIKÁTORU •

více trénovacích vzorů (pokud jsou k dispozici) –

•

lepší oddělení tříd

nepožadovat příliš složitá rozhodovací kritéria – –

trénovací data → slabší výkon celková generalizace → lepší

→ statistické rozpoznávání vzorů → problém odhadnout, zda bude dobře generalizovat Jana Štanclová, [email protected]

33/44

REPREZANTACE DAT •

typické reprezentace – vektory reálných čísel – uspořádaný seznam atributů, – ...

•

dobrá reprezentace dat – „blízké“ vzory → vedou ke stejné akci – „vzdálené“ vzory → vedou k různé akci

•

praxe – malé množství příznaků • jednodušší rozhodovací oblasti • snadné naučení klasifikátoru

– nedostatečná data • další znalost problematiky


34/44

REPREZANTACE DAT •

typické reprezentace – vektory reálných čísel – uspořádaný seznam atributů, – ...

•

dobrá reprezentace dat – „blízké“ vzory → vedou ke stejné akci – „vzdálené“ vzory → vedou k různé akci

•

praxe – malé množství příznaků • jednodušší rozhodovací oblasti • snadné naučení klasifikátoru

– nedostatečná data • další znalost problematiky


35/44

ILUSTRAČNÍ PŘÍKLAD 2 •

požadované vlastnosti příznaků – invariance, odlišitelnost, nezávislost, úplnost, .....

•

protipříklad – příznaky • auto? • barva • logo

– třída: Ferrari • „auto?“ ... ANO • barva ... červená • logo ... kůň


36/44

ILUSTRAČNÍ PŘÍKLAD 2 •

požadované vlastnosti příznaků – invariance, odlišitelnost, nezávislost, úplnost, .....

•

protipříklad – příznaky • auto? • barva • logo

– třída: Ferrari • „auto?“ ... ANO • barva ... červená • logo ... kůň


37/44

METODY ROZPOZNÁVÁNÍ


38/44

METODY ROZPOZNÁVÁNÍ •

1. statistické (příznakové) rozpoznávání – objekt → n-tice čísel • n vybraných příznaků → objekt = bod v n-rozměrném příznakovém prostoru

– volba reprezentace objektů • body z jedné třídy → kompaktní a dobře oddělitelné shluky v příznakovém prostoru

•

2. strukturální (syntaktické) rozpoznávání – popis struktury mezi objekty – častá reprezentace struktury → gramatiky • třída ... gramatika • vzor/objekt ... slovo • rozpoznávání ... syntaktická analýza

– problém: zašuměná data Jana Štanclová, [email protected]

39/44

METODY ROZPOZNÁVÁNÍ •

1. statistické (příznakové) rozpoznávání – objekt → n-tice čísel • n vybraných příznaků → objekt = bod v n-rozměrném příznakovém prostoru

– volba reprezentace objektů • body z jedné třídy → kompaktní a dobře oddělitelné shluky v příznakovém prostoru

•

2. strukturální (syntaktické) rozpoznávání – popis struktury mezi objekty – častá reprezentace struktury → gramatiky • třída ... gramatika • vzor/objekt ... slovo • rozpoznávání ... syntaktická analýza

– problém: zašuměná data Jana Štanclová, [email protected]

40/44

SYSTÉMY NA ROZPOZNÁVÁNÍ VZORŮ 1. 2.

snímání segmentace a shlukování –

3.

izolování nasnímaných objektů od pozadí a jiných objektů

extrakce příznaků – –

závislá na úloze měření vlastností/příznaků objektů pro klasifikaci • •

4.

podobné pro objekty stejné třídy invariantní vůči tranformacím a škálování (tvar, barva, druh „textury“, ...)

klasifikace – –

ohodnocení vstupních příznaků → určení třídy složitost klasifikátoru podle různorodosti příznaků ve stejné třídě • •

–

5.

vliv šumu = vlastnost nasnímaných objektů bez vztahu ke skutečnému modelu náhodnost ve světě, na senzorech, ...

praxe: ne vždy lze zjistit hodnoty všech příznaků pro daný objekt

post-processing – –

podle rozhodnutí klasifikátoru → příslušné akce účinnost klasifikátoru = poměr chyby/ztráty → minimalizace chyby


41/44

SYSTÉMY NA ROZPOZNÁVÁNÍ VZORŮ 1. 2.

snímání segmentace a shlukování –

3.

izolování nasnímaných objektů od pozadí a jiných objektů

extrakce příznaků – –

závislá na úloze měření vlastností/příznaků objektů pro klasifikaci • •

4.

podobné pro objekty stejné třídy invariantní vůči tranformacím a škálování (tvar, barva, druh „textury“, ...)

klasifikace – –

ohodnocení vstupních příznaků → určení třídy složitost klasifikátoru podle různorodosti příznaků ve stejné třídě • •

–

5.

vliv šumu = vlastnost nasnímaných objektů bez vztahu ke skutečnému modelu náhodnost ve světě, na senzorech, ...

praxe: ne vždy lze zjistit hodnoty všech příznaků pro daný objekt

post-processing – –

podle rozhodnutí klasifikátoru → příslušné akce účinnost klasifikátoru = poměr chyby/ztráty → minimalizace chyby


42/44

NÁVRH KLASIFIKÁTORU 1.

sběr dat –

2.

trénovací/testovací data

výběr příznaků – –

3.

závisí zcela na daném problému využití apriorní informace

výběr modelu –

4.

dány příznaky → nalezení dobrého modelu

učení klasifikátoru –

5.

parametry klasifikátoru (pomocí dat)

ohodnocení klasifikátoru –

nutnost zopakovat některé kroky • •

–

klasifikátor málo naučen, špatná volba příznaků, ...

pozor na přeučení systému


43/44

PŘÍBUZNÉ OBORY •

testování hypotéz – hypotézu zamítnout či ne?

•

image processing – rotace obrázku, zvýšení kontrastu, ....

•

extrakce příznaků – objekt/vzor → hodnoty příznaků – ztráta informace → typicky nemožnost zpětné rekonstrukce • klasifikace ještě radikálnější ztráta informace

•

regrese/interpolace – funkční popis s cílem predikovat hodnoty pro nové vstupy – příklady • známa změna délky lososa v závislosti na věku lososa pro první dva týdny života → odvození závislosti od věku 2 týdnů do 2 let • domněnka: délka lososa lineárně závislá na hmotnosti → naměření hodnot a nalezení koeficientů regrese


44/44

NAIL072 ROZPOZNÁVÁNÍ VZORŮ

Recommend Documents