Martin Petr. Rozpoznávání rukopisu pomocí

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Martin Petr Rozpoznávání rukopisu pomocí neuronové sítě Katedra teoretické informatiky a matematické logiky Vedoucí bakalářské práce: RNDr. Pavel Surynek, Ph.D. Studijní program: Informatika, Obecná informatika 2010

Děkuji svým rodičům za jejich podporu během celého mého studia. Děkuji RNDr. Pavlu Surynkovi, PhD. za trpělivé vedení mé práce.

Prohlašuji, že jsem svou bakalářskou práci napsal samostatně a výhradně s použitím citovaných pramenů. Souhlasím se zapůjčováním práce a jejím zveřejňováním. V Praze dne 4. sprna 2010

Martin Petr

2

Obsah Úvod Rozpoznávání vzorů . . . . . . . . . . . . . . . . . . . . . . . . . . . . Popis systému pro rozpoznávání vzorů . . . . . . . . . . . . . . . . . . Organizace práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Umělé neuronové sítě 1.1 Neuronová síť . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Formální neuron . . . . . . . . . . . . . . . . . . 1.1.2 Vícevrstevná dopředná neuronová síť . . . . . . . 1.1.3 Průběh výpočtu neuronové sítě . . . . . . . . . . 1.1.4 Adaptace vah a algoritmus zpětného šíření chyby 1.1.5 Akumulované učení vs. inkrementální učení . . . 1.1.6 Role skrytých neuronů . . . . . . . . . . . . . . . 1.2 Přeučení sítě a schopnost generalizace . . . . . . . . . . . 1.2.1 Trénovací, validační a testovací množina . . . . . 1.2.2 Metoda učení použitá v této práci . . . . . . . . . 1.3 Špatná podmíněnost sítě a jak jí zabránit . . . . . . . . . 1.3.1 Špatně podmíněná síť . . . . . . . . . . . . . . . 1.3.2 Normalizace vstupů a výstupů . . . . . . . . . . . 1.3.3 Inicializace vah . . . . . . . . . . . . . . . . . . . 2 Předzpracování vstupních dat 2.1 Binarizace . . . . . . . . . . 2.1.1 Otsuova metoda . . . 2.2 Skeletonizace . . . . . . . . 2.2.1 Hilditchův algoritmus

. . . .

. . . .

3

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

7 7 8 9

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

10 10 11 12 13 14 17 19 20 20 22 23 23 24 24

. . . .

26 27 27 28 29

3 Diskrétní kosinová transformace 3.1 Neformální popis . . . . . . . . . . . . . . . . . . . . . . . 3.2 Formální definice . . . . . . . . . . . . . . . . . . . . . . . 3.3 Získání vektoru příznaků . . . . . . . . . . . . . . . . . . . 3.4 Proč právě DCT . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Omezení dimenzionality prostoru všech vstupů . . . 3.4.2 Potlačení odlišností mezi variantami jednoho znaku 3.4.3 Osvědčenost při rozpoznávání vzorů . . . . . . . . . 4 Výsledky experimentů 4.1 Vstupní data . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Hledání metody pro rozpoznávání znaků . . . . . . . . . 4.2.1 Vliv největšího koeficientu DCT na průběh učení 4.2.2 Test rotační invariance . . . . . . . . . . . . . . . 4.2.3 Normalizace vstupních dat a rychlost učení . . . . 4.2.4 Vliv binarizace a skeletonizace na průběh učení . 4.2.5 Výběr aktivační funkce skrytých neuronů . . . . . 4.2.6 Výběr metody učení . . . . . . . . . . . . . . . . 4.2.7 Navržená metoda . . . . . . . . . . . . . . . . . . 5 Testování navržené metody 5.1 Rukopis použitý při návrhu metody 5.2 Rukopis pro nezávislé otestování . . 5.3 Porovnání se čtením pokusné osoby 5.4 Shrnutí výsledků testů . . . . . . . 5.5 Rychlost rozpoznávání . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . .

. . . . . . . . .

. . . . .

. . . . . . .

. . . . . . . . .

. . . . .

. . . . . . .

. . . . . . . . .

. . . . .

. . . . . . .

32 32 34 35 35 35 36 36

. . . . . . . . .

38 38 38 38 39 40 40 40 41 41

. . . . .

46 46 47 47 48 53

6 Závěr

54

Literatura

56

Dodatek: Obsah CD-ROM

58

4

Název práce: Rozpoznávání rukopisu pomocí neuronové sítě Autor: Martin Petr Katedra (ústav): Katedra teoretické informatiky a matematické logiky Vedoucí bakalářské práce: RNDr. Pavel Surynek, PhD. e-mail vedoucího: [email protected] Abstrakt: Rozpoznávání vzorů nalézá uplatnění v mnoha oborech, do jejichž vývoje zasáhla informatika či výpočetní technika. Výsadní postavení má v tomto ohledu zejména její aplikace na převod tištěného či rukou psaného textu do běžného textu v digitální podobě. V následující práci předkládáme metodu pro rozpoznávání rukou psaných znaků v reálném čase s využitím dopředné neuronové sítě jako základního klasifikačního mechanismu. Vzhledem k tomu, že se jednotlivé rukou psané varianty každého znaku vyznačují vzájemnými odlišnostmi, prozkoumali jsme důkladně možnosti potlačení těchto odlišností při zdůraznění charakteristik, které jsou pro rozpoznání daného znaku důležité. Pro tyto účely byla zvolena diskrétní kosinová transformace, jejíž osvědčenost při zpracování zvukového a obrazového signálu či přímo v oblasti rozpoznávání vzorů byla přesvědčivým argumentem i pro její využití v naší práci. V úvahu jsme vzali rovněž rozdíly mezi odlišnými psacími potřebami, pro jejichž potlačení jsme navrhli předzpracování vstupních dat v podobě binarizace a skeletonizace. Námi navržená metoda předvedla při důkladném otestování na dvou sadách znaků s odlišným rukopisem velmi vysokou úspěšnost a naše práce tak může posloužit jako spolehlivý základ pro případný budoucí návrh kompletního systému převádějícího rukou psaný text do digitální podoby. Klíčová slova: rozpoznávání vzorů, optické rozpoznávání znaků, umělé neuronové sítě, binarizace, skeletonizace, diskrétní kosinová transformace

5

Title: Handwriting recognition using neural network Author: Martin Petr Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: RNDr. Pavel Surynek, PhD. Supervisor’s e-mail address: [email protected] Abstract: Pattern recognition finds its use in many fields whose development has been affected by computer science and computer technology. Among these, the conversion of handwritten or printed text into computer-encoded text has a particularly prominent position. In the presented work we propose a method for recognizing handwritten characters in real-time using feedforward neural network as the basic classification mechanism. Dealing with differences among individual instances of each handwritten character we thoroughly explored the possibility of suppressing these while emphasizing characteristics that are essential for successful recognition. For these purposes we employed discrete cosine transform, whose time-proven application in audio and video signal processing or even directly in the field of pattern recognition provided a convincing argument for us to use it in our work as well. As a means of suppressing variations among various writing instruments we proposed preprocessing of input images using binarization and skeletonization. The designed method was thoroughly tested on two sets of characters with different handwriting and it showed a very high successful recognition rate. Our work can therefore serve as a reliable basis of eventual future system for translation of a whole handwritten text into its digital form. Keywords: pattern recognition, optical character recognition, artificial neural networks, binarization, skeletonization, discrete cosine transform

6

Úvod Rozpoznávání vzorů Pod pojmem rozpoznávání vzorů (angl. pattern recognition) se v dnešní době rozumí široké spektrum technik, úzce spjatých s oborem strojového učení, které ve své základní podstatě spočívají v klasifikaci vstupních dat (vzorů) do tříd či kategorií. Toto rozdělení bývá obvykle založeno na získání a analýze nejdůležitějších charakteristik či příznaků každého vzoru (angl. feature extraction) a porovnání těchto charakteristik se vzory, s nimiž se systém setkal již někdy v minulosti, např. během svého učení. Každý takový systém tedy funguje na principu využívání předchozí zkušenosti. Rozpoznávání vzorů ve výše popsané obecné podobě dnes nalézá uplatnění v mnoha oborech, do jejichž vývoje zasáhla informatika či výpočetní technika. Rozpoznání obličeje [3, 18] na fotografii je již zcela nedílnou součástí výčtu funkcí moderních fotoaparátů, v biometrické identifikaci osob se zase s úspěchem využívá rozpoznávání snímků rohovky [16] či otisků prstů. Do digitální textové podoby je možné převádět nejen naskenovaný tištěný text, ale i ručně psané písmo (funkce zcela běžně využívaná například při automatickém zpracování formulářů), či dokonce záznam hlasu. Nesmírně zajímavá a užitečná je také aplikace rozpoznávání vzorů v diagnostice – zde pomáhá lékařům v analýze obrazových dat získaných např. počítačovou tomografií a v identifikaci podezřelých a potenciálně patologických oblastí na těchto snímcích. Důvodem, proč tento obor byl a stále je cílem velkého zájmu jak teoretického tak aplikovaného výzkumu, je kromě výše uvedené šíře užitečných aplikací i velká výzva, kterou vždy návrh nového systému pro rozpoznávání vzorů představuje. Nejen, že každé nové zadání často klade zcela specifické požadavky na to, co by měl navržený systém zvládat, či že se velmi odlišuje i povaha samotných vstupních dat. Ve většině případů jsou navíc tyto systémy postaveny před problémy, jejichž řešení by bylo velice obtížné, nebo často i zcela nemožné, ně-

7

jakým způsobem přesně algoritmicky popsat. Jako pravděpodobně nejjednodušší a nejzřejmější příklad může sloužit i námi všemi každodenně používaná činnost – čtení. Pro mnoho lidí jde o zcela běžnou věc a je to schopnost, kterou používají podvědomě a samozřejmě, aniž by jim při ní myslí probíhala nějaká přesná posloupnost kroků, která by vždy po dokončení „výpočtuÿ vedla k rozpoznání jednotlivých znaků čteného textu. Při čtení se místo toho řídíme zkušenostmi a znalostmi nabytými v dětství učením, spočívajícím v trpělivém a opakovaném čtení vzorových písmen předkládaných nám naším učitelem. Z počátku sice žák čte s chybami, nicméně již poměrně záhy začne v jednotlivých písmenech (podvědomě) vidět vzory, společné charakteristiky, příznaky. Po nějakém čase se naučí číst i různé typy písmen, dokonce i diametrálně odlišné rukopisy různých autorů, které nejsou – mohlo by se zdát – téměř v ničem podobné rukopisu, který patřil jeho učiteli. Naučí se zobecňovat. Z předchozího odstavce je jasné, že řešení třídy problémů rozpoznávání vzorů, mezi které patří i výše uvedené čtení, vyžaduje zcela jiný přístup, než jaký je používán při řešení jiných úloh v informatice, které si vystačí s klasickým algoritmickým popisem výpočtu. Je více než výhodné použít takový výpočetní model, který by v ideálním případě vykazoval podobnou schopnost učit se, hledat podobnosti v předkládaných vzorech a takové umění zobecňovat, jakou disponuje lidský mozek. Jedním z takových výpočetních prostředků jsou umělé neuronové sítě [12]. Jak už sám název napovídá, jde o matematický model, jehož struktura a způsob výpočtu byly inspirovány principem fungování mozku vyšších organismů. Umělé neuronové sítě různých druhů se díky svým unikátním vlastnostem – své schopnosti zobecňovat a především díky své schopnosti učit se – staly de facto standardem v oboru rozpoznávání vzorů či strojového učení obecně. Umožňují totiž programátorovi soustředit se spíše na analýzu problému a správné předzpracování dat, přičemž samotné těžiště rozhodování a klasifikace je již zcela záležitostí použité umělé neuronové sítě.

Popis systému pro rozpoznávání vzorů Podívejme se nyní na to, z jakých součástí se systém pro rozpoznávání vzorů v té nejobecnější podobě obvykle skládá. Na počátku stojí senzor snímající vstupní data. Může jím být čidlo snímače otisků prstů, mikrofon v případě rozpoznávání hlasu či – jako tomu je v případě naší práce – obyčejný skener. Po získání vstupních dat z okolí může být potřeba je předzpracovat, například z nich odstranit šum nebo je vhodným způsobem normalizovat. Data v takto zpracované podobě převezme mechanismus, který z nich získá nejvýznačnější příznaky a charakteris8

tiky nutné pro správnou klasifikaci do příslušné třídy (angl. feature extractor). Výsledkem tohoto procesu je vektor příznaků, který daný vzor reprezentuje jako bod v mnohorozměrném prostoru vstupů. Fáze získávání příznaků je nesmírně důležitá – je potřeba vybrat kvalitní charakteristiky a je potřeba jich vybrat právě tolik, aby rozpoznávaný vzor v prostoru všech vstupů postačujícím způsobem reprezentovaly. Kdyby vektor příznaků obsahoval příliš málo prvků, nebylo by možné vzor správně klasifikovat, protože by systém neměl dostatek informací, stejně tak v případě, kdy by příznaky byly nekvalitní. Naopak příliš mnoho příznaků by systém zbytečně zatěžovalo, zpomalovalo a hlavně by ztěžovalo jeho učení. Následujícím členem systému je klasifikátor, který vzor, nyní již vlastně pouze vektor ve výše zmíněném prostoru všech vstupů, korektně přiřadí do třídy vzorů, jejichž příslušné vektory příznaků odpovídají (samozřejmě v rámci jistého zobecnění) právě zpracovanému vstupu. Řekněme, že v případě, kdy by se tedy jednalo o systém pro čtení znaků psaného textu, bude například na vstupu systému čekat obrázek písmene a. Tento obrázek projde sérií transformací, jejichž výsledkem bude číselný vektor, který jej bude reprezentovat v prostoru všech písmen abecedy a bude vstupem příslušného klasifikátoru.

Organizace práce Tato práce bude organizována následujícím způsobem: Ve první kapitole položíme nezbytné teoretické základy týkající se umělých neuronových sítí a také zmíníme několik praktických rad, kterými je vhodné se při jejich použití řídit bez ohledu na konkrétní aplikaci. Ve druhé kapitole popíšeme dva algoritmy pro předzpracování obrázků s písmeny – binarizaci a skeletonizaci. Samostatná kapitola bude věnována diskrétní kosinové transformaci, jejím základním vlastnostem a zdůvodnění toho, proč byla právě ona vybrána jako feature extractor pro naši práci. Na začátku čtvrté kapitoly představíme data, se kterými jsme při pokusech s rozpoznáváním rukou psaného textu pracovali, v jejích dalších částech pak postupně všechny provedené experimenty popíšeme. Tato kapitola také bude místem pro experimentální potvrzení, případně vyvrácení, některých tvrzení, která budou v této práci vyslovena. V páté kapitole otestujeme úspěšnost námi navržené metody na dvou sadách znaků s odlišným rukopisem a také se zamyslíme nad případy, ve kterých tato metoda selhala. 9

Kapitola 1 Umělé neuronové sítě V následující kapitole položíme teoretické a praktické základy nezbytné pro práci s umělými neuronovými sítěmi, přičemž se zaměříme pouze na ty algoritmy a metody, které se osvědčily při našem návrhu metody pro rozpoznávání psaného písma. Zmíníme také několik praktických poznatků a rad, které považujeme za důležité při jakékoli aplikaci umělých neuronových sítí.

1.1

Neuronová síť

Termínem umělé neuronové síťě 1 [12] se označují matematické modely napodobující svou strukturou a funkcí principy fungování biologických neuronových sítí. V obecné rovině se neuronová síť sestává z jednoduchých výpočetních jednotek (neuronů [12]) navzájem komunikujících pomocí spojů (tzv. synapsí), jež sice samy o sobě velkou výpočetní silou nedisponují, avšak při organizaci do vyšších struktur jsou schopny vykazovat komplexní chování. V dalším textu se budeme zabývat pouze jednou konkrétní třídou těchto modelů, takzvanými vícevrstevnými dopřednými neuronovými sítěmi [15], které jsou charaketristické tím, že jimi informace proudí pouze jedním směrem, od vstupu k výstupu, a že tedy neobsahují cykly. Tento typ neuronových sítí je sice nejjednodušší a nejsnáze trénovatelný, přesto je ale využíván v drtivé většině aplikací. Ostatní typy sítí, jakými jsou například rekurentní neuronové sítě [13], Kohonenovy sítě [14] či mnohé další, zde rozebírat nebudeme. 1

V dalším textu pro zkrácení již pouze neuronové sítě. O neuronových sítích v původním biologickém smyslu zde hovořit nebudeme, takže při používání tohoto zkráceného termínu nebude docházet ke zmatení.

10

1.1.1

Formální neuron

Základem matematického modelu neuronové sítě je formální neuron 2 [12] (schéma neuronu je vyobrazeno na obr. 1.13 ). Tento neuron přijímá obecně n vstupů, přičemž každý vstup má přídělenu váhu w ∈ R, kterou si lze představit jako míru významu daného vstupu. Kromě vstupů z okolí přijímá každý neuron také formální vstup s konstantní hodnotou 1 a příslušnou vahou (bias). Výstup neuronu je pak dán hodnotou aktivační funkce σ : R → R, jejímž argumentem je vážený součet vstupů neuronu, označovaný jako tzv. vnitřní potenciál ξ. Máme-li tedy neuron i, jeho vstupy xj a jim příslušející váhy wij , j = 0, . . . , n, pak je jeho výstup yi dán rovnicí: n X yi = σ( wij xj ). j=0

Obrázek 1.1: Schéma formálního neuronu.

2

I v tomto případě pro zkrácení již pouze neuron. Převzato a upraveno z http://en.wikibooks.org/wiki/File:ArtificialNeuronModel_english.png. 3

11

(1.1)

Aktivační funkce může mít obecně mnoho podob, nejčastěji se však využívají následující tři: • ostrá nelinearita  σ(ξ) =

0 jestliže ξ < h , 1 jestliže ξ ≥ h

(1.2)

kde h je tzv. aktivační práh neuronu, • standardní logistická sigmoida σ(ξ) =

1 , 1 + e−ξ

(1.3)

σ(ξ) =

1 − e−ξ . 1 + e−ξ

(1.4)

• hyperbolický tangens

1.1.2

Vícevrstevná dopředná neuronová síť

Vícevrstevnou dopřednou neuronovou síť si můžeme pro názornost představit jako orientovaný acyklický graf, jehož uzly jsou tvořeny neurony a orientované spoje mezi nimi jsou ohodnoceny reálnými čísly (vahami). Platí přitom, že můžeme neurony rozdělit do série disjunktních množin (vrstev), kdy se první vrstva, tzv. vstupní vrstva, skládá ze vstupních neuronů, poslední vrstva, tzv. výstupní vrstva, je tvořena výstupními neurony, a mezi těmito dvěma vrstvami může ležet jedna nebo více dalších vrstev, tzv. skrytých vrstev, obsahujících skryté neurony. V takto zadané topologii navíc každý neuron přijímá na svém vstupu výstupy všech neuronů z předchozí vrstvy (dvě po sobě následující vrstvy neuronů tedy, jinými slovy, tvoří úplný bipartitní graf). Schematické znázornění topologie vícevrstevné dopředné neuronové sítě je na obr. 1.24 . 4

Převzato a upraveno z http://www.gamedev.net/reference/programming/features/ vehiclenn/figure1.png.

12

Obrázek 1.2: Schematické znázornění topologie vícevrstevné dopředné neuronové sítě.

1.1.3

Průběh výpočtu neuronové sítě

Znalost funkce formálního neuronu a topologie dopředné neuronové sítě nám dává možnost nahlédnout, jakým způsobem tato síť při svém výpočtu pracuje. Označme tedy nejprve (v souladu s [15], odkud budeme zejména při popisu učícího algoritmu zpětného šíření chyby téměř výhradně čerpat) • vstupní vrstvu jako X a počet vstupních neuronů jako n, • výstupní vrstvu jako Y a počet výstupních neuronů jako m, • vnitřní potenciál neuronu i jako ξi , • výstup neuronu i jako yi , • váhu synapse vedoucí od neuronu i k neuronu j jako wji ,

13

• bias neuronu j, příslušející formálnímu jednotkovému vstupu y0 = 1, jako wj0 , • konfiguraci neuronové sítě (tedy množinu vah v neuronové síti) jako w, • vrstvu neuronů, jež předávají neuronu j své výstupy (včetně jeho formálního jednotkového vstupu), jako j← a • vrstvu neuronů, ke kterým vede synapse od neuronu j, a kterým tedy předává svůj výstup, jako j→ Při svém výpočtu neuronová síť vyhodnocuje funkci f (w) : Rn → Rm . V souladu s topologií dopředné neuronové sítě probíhá tento výpočet induktivně ve „vlnáchÿ odpovídajících jednotlivým vrstvám následujícím způsobem: • V čase t = 0 jsou nastaveny stavy yi , i ∈ X (tedy výstupy neuronů vstupní vrstvy) na příslušné vstupní hodnoty z Rn . Stavy neuronů v následujících vrstvách jsou nedefinovány. • Nechť jsou v čase t > 0 definovány výstupní hodnoty neuronů ve vrstvě R a vrstvách předcházejících. Pak jsou podle rovnice (1.1) na základě těchto výstupů vypočítány stavy yi pro všechny neurony i ∈ S, kde S je vrstva neuronové sítě bezprostředně následující po vrstvě R. Tvrzení 1. Nechť má dopředná neuronová síť konečný počet vrstev L. Pak její výpočet vždy skončí v konečném čase. Důkaz. Plyne triviálně ze záruky acykličnosti dopředné neuronové sítě. V každém z kroků výpočtu jsou vyhodnoceny výstupní stavy neuronů v i-té vrstvě na základě stavů neuronů (i − 1)-ní vrstvy. Jelikož je počet vrstev sítě L konečný, budou po L krocích definovány i stavy neuronů ve výstupní vrstvě a výpočet tedy skončí. Výstupní stavy neuronů v poslední vrstvě sítě určují výslednou hodnotu výše uvedené funkce f (w) : Rn → Rm .

1.1.4

Adaptace vah a algoritmus zpětného šíření chyby

Nyní tedy již víme, jakým způsobem probíhá výpočet dopředné neuronové sítě. Aby byla ale tato síť schopna realizovat námi požadované zobrazení g(w) : Rn → Rm (a tedy měla nějakou pro nás užitečnou funkci), potřebujeme nejprve způsob, jakým adaptovat váhy sítě w. 14

Definujme nejprve tzv. trénovací množinu, popisující námi požadované zobrazení g(w): T = {(xk , dk )|xk = (xk1 , . . . , xkn ) ∈ Rn , dk = (dk1 , . . . , dkm ) ∈ Rm }.

(1.5)

T je tedy množinou p dvojic trénovacích vzorů xk a příslušných požadovaných výstupů dk , přičemž cílem učení je taková adaptace vah sítě w, aby ideálně platilo ∀(xk , dk ) ∈ T :

f (w, xk ) = dk ,

(1.6)

kde f (w) je funkce představovaná samotnou neuronovou sítí. Abychom mohli přistoupit k učení sítě, potřebujeme nějaké kritérium toho, jak je trénovaná neuronová síť vzhledem k výše popsané trénovací množině úspěšná. Definujme tedy chybovou funkci neuronové sítě E(w) jako součet parciálních chybových funkcí sítě Ek (w) vzhledem k jednotlivým p trénovacím vzorům z T : E(w) =

p X

Ek (w).

(1.7)

k=1

Parciální chyba vzhledem ke k-tému trénovacímu vzoru je definována jako suma druhých mocnin rozdílů jednotlivých stavů výstupních neuronů od námi požadovaných výstupů: Ek (w) =

1X (yj (w, xk ) − dkj )2 . 2 j∈Y

(1.8)

Cílem adaptace vah je minimalizace hodnoty chybové funkce E(w) v prostoru všech vah sítě. Jelikož je ale neuronová síť velmi komplikovanou složenou nelineární funkcí a protože navíc dimenizonalita prostoru vah dosahuje často až desetitisíců, tak tato úloha představuje výpočetně velmi náročný optimalizační problém. V praxi se nejčastěji řeší formou gradientní metody (angl. gradient descent), kterou si v následujících odstavcích stručně popíšeme. Na začátku učení v čase t = 0 jsou váhy sítě náhodně nastaveny na hodnoty z intervalu [−r, r], kde r je hodnota nepříliš vzdálená od nuly (podrobnosti k inicializaci vah v podkapitole 1.3.3). Gradientní metoda pak postupuje iterativně v krocích, kdy se vždy v čase t > 0 vypočtou nové hodnoty vah w(t) na základě gradientu chybové funkce E v bodě w(t−1) :

15

(t)

(t−1)

wji = wji

−

∂E (w(t−1) ). ∂wji

(1.9)

Parametr  se nazývá rychlost učení (angl. learning rate) a představuje podíl gradientu chybové funkce, který se v každém kroku učení použije pro skutečný posun v prostoru všech vah sítě. Jeho hodnota se nejčastěji volí z intervalu (0, 1) (obvykle kolem 0.1). Abychom mohli měnit váhy sítě podle rovnice (1.9), potřebujeme znát hodnotu gradientu celkové chyby sítě, jehož výpočet je však vzhledem ke komplikovanosti této složené funkce netriviální. Zderivujme nejprve rovnici (1.7) podle pravidla o derivaci součtu, čímž převedeme gradient celkové chyby sítě na součet gradientů parciálních chyb sítě vzhledem ke všem p trénovacím vzorům: p

X ∂Ek ∂E = ∂wji ∂wji k=1

(1.10)

Pro gradient parciální chyby sítě je pak možné se odvozením (podrobně např. v [15] pro případ logistické sigmoidy jako aktivační funkce) dopracovat k rovnici: ∂Ek ∂Ek 0 = σ (ξj )yi . ∂wji ∂yj

(1.11)

Všimněme si, že aby výše uvedená rovnice platila, musí být aktivační funkce diferencovatelná. Parciální derivace sledujícím způsobem:

∂Ek ∂yj

vypočítáme zvlášť pro výstupní a skryté neurony ná-

• pro výstupní neurony se ke vzorci pro výpočet této parciální derivace dostaneme prostým derivováním parciální chybové funkce popsané rovnicí (1.8): ∂Ek = yj − dkj , ∂yj

(1.12)

• pro skryté neurony derivaci vypočteme takto (odvození opět např. v [15]): X ∂Ek ∂Ek = σ 0 (ξr )wrj . ∂yj ∂yr r∈j →

16

(1.13)

Při výpočtu

∂E ∂wji

pro každou váhu tedy můžeme postupovat iterativně s využi-

tím rovnic (1.12) a (1.13). Nejprve vypočítáme k podle (1.12). Pro určení ∂E podle (1.13) ∂yj k vách pak využíváme pouze ∂E neuronů z ∂yr

∂Ek ∂yj

pro neurony ve výstupní vrstvě

příslušící neuronu j ve skrytých vrst-

j→ (tedy neuronů z následující vrstvy sítě), které byly vypočteny v předcházející iteraci. Tento postup je známý pod vypovídajícím termínem metoda zpětného šíření chyby (angl. backpropagation of errors). Tvrzení 2. Nechť má dopředná neuronová síť konečný počet vrstev L. Pak výpočet ∂E , wji ∈ w metodou zpětného šíření chyby skončí v konečném čase. ∂wji Důkaz. Opět triviální jako v případě Tvrzení 1 o konečnosti výpočtu dopředné neuronové sítě. Znovu využijeme záruku acykličnosti neuronové sítě pouze s tím rozdílem, že se v případě metody zpětného šíření chyby postupuje během výpočtu směrem od výstupní vrstvy ke vstupní vrstvě s využitím rovnic (1.12) a (1.13). Celý učící proces využívající metodu zpětného šíření chyby k adaptaci vah neuronové sítě jsme shrnuli v podobě pseudokódem zapsaného algoritmu ve výpisu na následující straně. K tomuto výpisu dodejme, že kritériem pro ukončení učení sítě může být například dosáhnutí pevného počet trénovacích epoch (počtu průchodů skrz celou trénovací množinu), pokles celkové chyby sítě E(w) (1.7) pod určitou uspokojivou úroveň, případně nějaká jiná a složitější podmínka.

1.1.5

Akumulované učení vs. inkrementální učení

Algoritmus učení popsaný ve výpisu se v literatuře označuje pojmem akumulované (dávkové, z angl. batch) učení. Tento název plyne z faktu, že jsou váhy sítě adaptovány až po průchodu celou trénovací množinou a po akumulaci celkového gradientu chybové funkce Ek (w). Alternativním přístupem je pak tzv. inkrementální (z angl. online) učení. Při tomto druhu učení jsou váhy sítě adaptovány po předložení každého trénovacího vzoru dle gradientu chyby Ek (w) pouze vzhledem k tomuto vzoru. Kroky 6.8., krok 13. a kroky 16.-18. se tedy neprovádí vůbec a váhy jsou v každém cyklu adaptovány přímo podle gradientu vypočítaném v kroku 12 pro aktuální trénovací vzor xk . Před začátkem každé trénovací epochy je také vhodné celou trénovací množinu T promíchat, aby byl vliv jednotlivých trénovacích vzorů na průběh učení rovnoměrně rozložen. Akumulované učení bývá v literatuře často popisováno jako rychlejší a korektnější než učení inkrementální z toho důvodu, že údajně lépe a věrněji kopíruje 17

1: 2: 3: 4: 5: 6: 7:

for all wji ∈ w do wji ← random() end for

while není splněno kritérium pro ukončení učení do for all wji ∈ w do ∂E ←0 ∂wji 8: end for 9: 10: 11: 12: 13: 14: 15: 16: 17:

for all xk ∈ T do Vyhodnoť výstup sítě f (w, xk ). ∂Ek podle rovnice (1.11). Vypočítej ∂w ji ∂E ∂wji

← end for

∂E ∂wji

+

∂Ek ∂wji

for all wji ∈ w do ∂E wji ← wji −  ∂w ji 18: end for 19: end while gradient chybové funkce. Pravdou ovšem je, že je akumulované učení – zejména v případě větších trénovacích množin – téměř vždy pomalejší než inkrementální učení a korektnější je pouze formálně. Vše je velmi podrobně popsáno a experimentálně podloženo v [19]. Metoda akumulovaného učení sice na první pohled opravdu věrně kopíruje povrch chybové funkce výpočtem „pravéhoÿ gradientu vzhledem k celé trénovací množině, není ale schopna odhadnout, jak daleko může ve směru tohoto gradientu (resp. v jeho opačném směru, protože jde při učení o minimalizaci chyby) jít, jelikož je průběh chybové funkce obvykle velmi komplikovaný. Situace se ještě zhoršuje v případě velkých trénovacích množin. Tehdy je totiž gradient naakumulovaný v každé epoše tak velký, že učící algoritmus není schopen sledovat složité křivky povrchu chybové funkce a učení tak často vůbec nedokonverguje. Inkrementální učení na druhou stranu využívá „lokálníchÿ gradientů vůči každému trénovacímu vzoru. Ty jsou sice v porovnání s gradientem naakumulovaným vzhledem k celé trénovací množině poměrně nepřesné a leckdy si vzájemně odporují, ale při jejich zprůměrování dojde vždy k posunu přibližně ve směru pravého gradientu. Navíc inkrementální učení adaptuje váhy po předložení každého 18

trénovacího vzoru zvlášť, což umožňuje lépe následovat jemnější křivky pravého gradientu (v případě dávkového učení máme možnost učinit pouze jeden krok za celou trénovací epochu). Není také potřeba zmenšovat rychlost učení při zvětšení trénovací množiny. Porovnáním výsledků akumulovaného a inkrementálního učení v našem případě se budeme zabývat ve čtvrté kapitole.

1.1.6

Role skrytých neuronů

Jedním z nejtěžších úkolů při aplikaci neuronových sítí je návrh správné architektury, zejména určení počtu skrytých neuronů. Existuje sice několik různých doporučení [11], jejich užitečnost je však přinejmenším diskutabilní, protože mají často pouze podobu velmi hrubých odhadů. To je ale naprosto samozřejmé, protože žádné obecně platné pravidlo stanovující množství skrytých neuronů ani existovat nemůže. „Inteligenceÿ či „paměťÿ neuronové sítě je totiž určena právě počtem skrytých neuronů, resp. počtem vah v síti, a požadovaná míra této inteligence se zákonitě liší v závislosti na konkrétním úkolu, který má daná síť řešit. Při pouhém „memorováníÿ trénovacích dat, například pro účely biometrické identifikace omezeného okruhu osob, bychom si vystačili s menším množstvím skrytých neuronů, protože by byly na síť kladeny menší nároky co se týče generalizace neznámých vstupů. V jiném případě, například v nějakém komplexním systému pro rozpoznávání textu, by tyto nároky byly velké, a tak by bylo nutné použít mnohem větší množství skrytých neuronů. Obecně můžeme říct alespoň to, že ačkoliv vícevrstevná neuronová síť umožňuje použití libovolného počtu skrytých vrstev, díky následujícímu tvrzení (v angličtině známém pod názvem Universal approximation theorem) si vystačíme vždy s jedinou. Tvrzení 3. Nechť f : Rn → Rm reprezentuje dopřednou neuronovou síť s jednou skrytou vrstvou. Pak je f při dostatečném, avšak konečném, množství skrytých neuronů schopna aproximovat jakoukoli funkci g na kompaktní podmnožině Rn . Důkaz. Toto tvrzení dokázal [2] nejprve Cybenko pro případ sogmoidy jako aktivační funkce. Hornik dále ukázal [4], že tato silná vlastnost není dána výběrem konkrétní aktivační funkce, ale samotnou vícevrstevnou dopřednou architekturou neuronové sítě. Dodejme ještě, že v praxi se sice občas experimentuje s použitím více než jedné skryté vrstvy, ale to pouze z důvodů občasného urychlení učení. Použití více 19

vrstev totiž v souladu s výše uvedeným tvrzením nedodá neuronové síti žádnou dodatečnou klasifikační sílu.

1.2

Přeučení sítě a schopnost generalizace

Zřejmě bychom nenašli příliš mnoho užitku ve využití neuronové sítě pro rozpoznávání jedné jediné množiny vzorů. V takových případech by bylo jednodušší a hlavně mnohem efektivnější použít alternativní a přímou metodu, například nějakou formu hashování [5]. O co nám při používání neuronových sítí jde především, je co nejvíce využít jejich unikátní schopnost generalizace. Jak ale za okamžik uvidíme, naučit síť uspokojivým způsobem trénovací množinu a zároveň chtít, aby podávala stejně tak uspokojivé výsledky i na nových a neznámých datech, to jsou často dva zcela protichůdné cíle. Schopnost sítě zobecňovat je do značné míry funkcí délky učení a počtu skrytých neuronů, resp. počtu vah v síti. Velké množství skrytých neuronů, případně příliš dlouhé a důkladné učení, způsobí, že se síť naučí trénovací množinu i s případným šumem tak dokonale, že nebude vůbec schopna uspokojivě zpracovat neznámá data (dojde k tzv. přeučení, angl. overfitting). Naopak, příliš krátké učení nebo příliš malé množství skrytých neuronů bude příčinou toho, že síť nejenomže nedokáže zobecňovat, ale nebude mít ani možnost naučit se samotná vzorová data. Je tedy zřejmé, že je potřeba pečlivě hledat kompromis mezi těmito dvěma extrémy a že je nutné najít takovou metodu učení, abychom zajistili dostatečné naučení trénovacích dat při zachování schopnosti generalizovat neznámá data. V této podkapitole se zamyslíme nad tím, jak při hledání tohoto kompromisu nejlépe postupovat.

1.2.1

Trénovací, validační a testovací množina

Jelikož je naším cílem najít takovou neuronovou síť, která bude nejen co nejlépe zvládat vzory, se kterými se setkala během svého tréninku, ale bude si vést dobře i při vystavení neznámým datům, nabízí se jednoduchá myšlenka rozdělit trénovací data do dvou množin. Do trénovací množiny, vůči které budou během učení pozměňovány váhy sítě, a validační množiny, která bude sloužit pro výběr té nejlepší sítě mezi několika sítěmi s různými architekturami (počty skrytých neuronů), případně různými parametry učení, na základě nejlepšího zobecňování. Po každé tréninkové epoše, kdy dojde ke změně vah sítě, předložíme této síti validační množinu k otestování. Jelikož je validační množina zcela nezávislá na trénovací množině (vůči validační množině nikdy váhy neměníme!), je tento test 20

dobrým měřítkem toho, jak se v právě proběhnuté epoše učení změnila schopnost sítě zobecňovat.

Obrázek 1.3: Schematický průběh chyby sítě vzhledem k trénovací (zelená křivka) a validační (modrá křivka) množině. Dalo by se očekávat, že se na začátku učení bude síť zlepšovat jak vzhledem k trénovací, tak vzhledem k validační množině. Dříve či později ale nastane okamžik, kdy se síť při tréninku přestane učit obecné charakteristiky trénovacích vzorů (které jsou v případě rovnoměrného rozdělení dat mezi trénovací a validační množinu platné pro obě množiny) a začne si zapamatovávat šum, který je specifický pouze pro trénovací data. V tomto bodě se typicky začne úspěšnost sítě vzhledem k validační množině zhoršovat a to je také okamžik t vhodný pro ukončení učení (viz obr. 1.3). V tomto bodě totiž máme nejlepší možnou neuronovou síť vzhledem k oběma výše zmíněným kritériím. Tento jednoduchý postup se v odborné literatuře běžně označuje názvem early-stopping [8]. Při použití této metody je velmi důležité si uvědomit, že jsme sice přímo pro samotné učení validační množinu nikdy přímo nepoužili (nikdy jsme podle ní neměnili váhy sítě) a využívali jsme ji pouze k otestování generalizace sítě, přesto ale nesmíme brát její výkonnost vůči této množině jako směrodatnou, co se týče generalizace vůči všem datům obecně. Je tedy nutné použít ještě množinu třetí – 21

60 40

chyba vzhledem k trénovací množině chyba vzhledem k validační množině úspěšnost vzhledem k validační množině [%]

0

20

Hodnota chybové funkce

80

testovací množinu. Teprve v ní se totiž nacházejí data, která síť neviděla nikdy a úspěšnost sítě na těchto zcela nezávislých datech je tedy nejlepším odhadem toho, jaká je její skutečná schopnost generalizace.

0

20

40

60

80

100

Počet epoch od počátku učení

Obrázek 1.4: Průběh tréninku neuronové sítě při učení se rukou psaných písmen anglické abecedy.

1.2.2

Metoda učení použitá v této práci

Při našich experimentech s učením neuronové sítě rozpoznávat rukou psané písmo jsme již poměrně záhy zjistili, že je pro naše účely učení metoda early-stopping tak, jak bývá popsána v literatuře, nepoužitelná. Pokud se podíváme na graf na obrázku 1.4, který zobrazuje průběh učení sítě při jednom z našich pokusů, okamžitě vidíme, že je průběh procentuální úspěšnost sítě vzhledem k validační množině 22

(která nás zajímá nejvíce) chaotický. Rozhodně se její průběh nepodobá ideálnímu a hladkému průběhu na obrázku 1.3, který slouží v literatuře jako argument pro použití metody early-stopping. Jelikož tedy v našem případě není možné jednoznačně určit výše uvedený bod t, ve kterém by bylo možno učení zastavit s tím, že se dále úspěšnost sítě vzhledem k validační množině bude již pouze zhoršovat, navrhli jsme jinou metodu učení. Spuštěním několika tréninků se pokusíme odhadnout, v jakém rozmezí od počátku učení dochází k podstatným změnám ve výkonnosti sítě, zejména co se týče validační množiny. Síť pak necháme učit jen v tomto rozmezí, přičemž si během učení vždy ukládáme nejlepší konfiguraci sítě (váhy) co se týče procentuální úspěšnosti vzhledem k validační množině. Po změně vah na konci každé epochy konfrontujeme výsledek nové konfigurace s tou dosud nejlepší a na konci učení tak získáme konfiguraci, se kterou daná neuronová síť nejlépe zobecňovala. Na samotném konci učení pak otestujeme nejlepší konfiguraci sítě na nezávislé testovací množině. Je otázkou, jestli je výše uvedený chaotický průběh chyby sítě specifikem naší úlohy, respektive našich trénovacích dat. Domníváme se ale, že je námi použitá metoda učení obecnější než metoda early-stopping a že je použitelná ve větším množství případů. Je totiž snadné si rozmyslet, že kromě toho, že řeší náš případ skokového průběhu chyby, tak i v ideálním případě popsaném na obrázku 1.3 bude dávat zcela stejný výsledek.

1.3

Špatná podmíněnost sítě a jak jí zabránit

Z předchozí části již nyní víme, jak zabránit tomu, aby se síť naučila vzorová data příliš dobře. V praxi je ale mnohem častější opačný problém – síť se nechce učit vůbec nebo se učí velmi špatně a dochází tak ke stavu, který se nazývá špatná podmíněnost sítě (angl. ill-conditioning). To může být způsobeno řadou faktorů: příliš velkými vstupními či výstupními hodnotami trénovacích dat, nevhodnou architekturou sítě či špatně zvolenými počátečními vahami. Na tyto problémy jsme ve své práci narazili i my a v této podkapitole zmíníme možnosti, jak je řešit.

1.3.1

Špatně podmíněná síť

Úspěšnost učení závisí ve velké míře na dobře zvolené hodnotě rychlosti učení (viz kapitola 1.1.4). Pokud zvolíme rychlost učení příliš malou, bude sice algoritmus zpětného šíření chyby věrně kopírovat povrch chybové funkce, ale učení 23

bude postupovat velmi pomalu. Pokud na druhou stranu zvolíme velkou rychlost učení, uspokojivého lokálního minima nikdy nedosáhneme a učení bude divergovat. Nejvhodnější hodnota rychlosti učení se dokonce liší i v závislosti na průběhu chybové funkce – rozsáhlé ploché oblasti vyžadují velkou rychlost učení, strmé oblasti naopak malou rychlost. V ideálním případě by měla mít každá váha vlastní rychlost učení. O neuronové síti řekneme, že je špatné podmíněná, jestliže se ideální rychlosti učení pro jednotlivé váhy liší takovým způsobem, že existence jediné globální rychlosti platné pro všechny váhy zabraňuje síti v tom, aby se byla schopna uspokojivě naučit trénovací data.

1.3.2

Normalizace vstupů a výstupů

Častou překážou úspěšného učení jsou řádové rozdíly ve velikostech mezi vstupy a výstupy neuronů. Transformace velmi velkých vstupů na mnohem menší výstupy totiž vyžaduje změnu počátečních vah na velmi malé hodnoty, což vede k nepřijatelně dlouho trvajícím tréninkům sítě. Analogický problém se vyskytuje i v případě velmi vysokých požadovaných výstupních hodnot sítí a jejich malých vstupů. Vše je podrobně popsáno a vysvětleno v [9]. Řešení tohoto problému je jednoduché – normalizujeme vstupy sítě tak, aby měly nulovou střední hodnotu a standardní odchylku rovnu jedné: Xi =

xi − µ , σ

i = 1, . . . , n.

(1.14)

V případě neuronů, jež své výstupní stavy poskytují jako vstupy neuronům v následující vrstvě, se normalizace výstupů vyplatí také. Přestože se tedy v literatuře (zřejmě z čistě historických důvodů) téměř automaticky předpokládá použití sigmoidy jako aktivační funkce, je výhodnější použít hyperbolický tangens. Jeho hodnoty totiž leží v rozmezí (−1, 1) a jeho symetrie znamená, že se jeho střední hodnota bude blížit k nule. Jaký vliv na rychlost učení má použití hyperbolického tangens oproti sigmoidě si experimentálně ukážeme ve čtvrté kapitole.

1.3.3

Inicializace vah

V kapitole 1.1.4 jsme zmínili náhodnou inicializaci vah sítě na počátku učení. Tyto počáteční hodnoty ale nesmíme nastavovat jen tak bez rozmyslu (interval [−1, 1] zmíněný v [15] při popisu algoritmu backpropagation je například příliš široký). Velmi malé hodnoty by při průchodu sítí zcela utlumily vstupní signál, 24

velké váhy by na druhou stranu saturovaly aktivační funkci. Dostaly by ji blízko asymptotickým hodnotám -1 resp. 1, kde mají sigmoida i hyperbolický tangens téměř nulovou derivaci, což by pro změnu zablokovalo zpětné šíření chyby [9] (důvod je zřejmý z popisu metody zpětného šíření chyby v kapitole 1.1.6). Rádi bychom nastavili váhy vstupů tak, aby byl vnitřní potenciál skrytých neuronů normalizovaný, což by zabránilo výše popsaným problémům. Budeme-li tedy vstupní hodnoty neuronů považovat za nezávislé náhodné veličiny s rovnoměrným rozdělením (což jsme zajistili v předchozí podkapitole), můžeme sčítat jejich rozptyly a pro rozptyl celkového vnitřního potenciálu skrytého neuronu j pak platí [9]: V ar(ξj ) ≈

k X i=1

V ar(wji yi ) =

k X

2 wji V

ar(yi ) ≈

i=1

k X

2 wji ≤ kr2 ,

(1.15)

i=1

leží-li počáteční váhy v intervalu [−r, r] a neuron j přijímá vstupy od k neuronů předcházející vrstvy. Naším cílem je zaručit, aby byl rozptyl vnitřních potenciálů V ar(ξj ) maximálně roven jedné. Toho docílíme inicializací vah v rozmezí [−r, r], kde hraniční hodnota bude 1 r=√ . k

25

(1.16)

Kapitola 2 Předzpracování vstupních dat Žádný systém pro rozpoznávání písma (ať již rukou psaného či tištěného) se neobejde bez metody pro potlačení rozdílů mezi různými druhy psacích potřeb resp. mezi různými fonty. My jsme se pro tento účel rozhodli použít metodu binarizace [7] a skeletonizace [1], která nám umožňuje převést libovolně širokou čáru písmene na jeden pixel širokou linii při zachování veškerých jeho geometrických a topologických vlastností, jakými jsou spojitost tahů, jejich délka a směr, jakým jsou vedeny (obr. 2.1). Převedením písmene na tuto minimální kostru navíc zcela eliminujeme potenciální redundanci v původním obrázku, což by mohlo přispět ke zkvalitnění charakteristik, které ze skeletonizovaného obrázku následně bude získávat diskrétní kosinová transformace (kapitola 3). Ta bude totiž při získávání příznaků brát v úvahu již pouze linie tahů písmene a ne tloušťku čar, různé odstíny šedi způsobené odlišným přítlakem pera na podložku a podobně. Binarizace a skeletonizace nám tedy zaručí, že veškeré příznaky, které budou z obrázku získány, jsou založeny pouze na kostře a tazích písmene, a že tak klasifikační mechanismus nebude zbytečně maten jinými, pro rozpoznávání nepodstatnými, informacemi.

Obrázek 2.1: Vzorový příklad binarizace a skeletonizace. 26

2.1

Binarizace

Vstupem pro náš systém jsou naskenovaná písmena abecedy ve stupních šedi. Jelikož námi použitá skeletonizační metoda pracuje s černobílými daty, je potřeba písmena nejprve binarizovat. Obecně, máme-li obrázek reprezentovaný funkci f (x, y) a globální práh T , pak binarizovaný obrázek odpovídá funkci g(x, y), pro kterou platí  0 pro f (x, y) ≤ T g(x, y) = (2.1) 1 jinak. Pro tyto účely bylo vyvinuto velké množství algoritmů, s různými výhodami a nevýhodami. My jsme využili tzv. Otsuovu metodu [7, 10], která byla součástí grafického software ImageJ1 , jehož skriptovací možnosti a mnoho grafických rozšíření v podobě různých algoritmů pro binarizaci a skeletonizaci jsme pro naše pokusy s předzpracováním písmen použili.

2.1.1

Otsuova metoda

Účelem binarizačního algoritmu je nalézt takový práh (intenzitu pixelů), aby po roztřídění pixelů obrázku do dvou kategorií dle tohoto prahu (v našem případě do pozadí a popředí) zůstal zachován charakter původního obrázku. Celý problém můžeme formulovat tak, že chceme rozdělit histogram intenzit vstupního obrazu do dvou částí, kdy jedna část bude odpovídat intenzitám pixelů pozadí a druhá část intenzitám pixelů popředí. Největší obtíže na celém procesu prahování způsobuje fakt, že i objekty v popředí obrázku mohou obsahovat pixely, jejichž intenzity správně patří do pozadí a naopak. Tyto chyby se můžeme pokusit minimalizovat vybráním takové hodnoty prahové intenzity, aby byl každý pixel svou intenzitou blíže průměrné intenzitě pixelů ze „svéÿ třídy než průměrné intenzitě pixelů druhé třídy. Přesněji řečeno, nechť µB (T ) je střední hodnota intenzit pixelů pod prahem T (pozadí), µF (T ) střední hodnota intenzit pixelů nad prahem T (popředí), p je pixel, i(p) jeho intenzita a f (x, y) je binarizovaný obrázek. Pak tedy chceme najít takovou hodnotu prahu, aby platilo [7]:

1

∀p ∈ f (x, y), i(p) ≥ T : |i(p) − µB (T )| > |i(p) − µF (T )|

(2.2)

∀p ∈ f (x, y), i(p) < T : |i(p) − µB (T )| < |i(p) − µF (T )|.

(2.3)

http://rsbweb.nih.gov/ij/

27

Otsuova metoda se snaží splnit tyto podmínky nastavením prahu T tak, aby minimalizovala celkový rozptyl intenzit pozadí a popředí (tzv. intra-class rozptyl), přičemž tento intra-class rozptyl můžeme definovat jako vážený průměr rozptylů pozadí (σB2 (T )) a popředí (σF2 (T )): 2 σintra (T ) = wB (T ) · σB2 (T ) + wF (T ) · σF2 (T ),

(2.4)

kde pro váhy wB (T ) a wF (T ) platí: nB (T ) , n nF (T ) wF (T ) = . n

wB (T ) =

(2.5) (2.6)

nB (T ) a nF (T ) v rovnicích (2.5) a (2.6) označují počty pixelů zařazených prahováním podle prahu T do pozadí, resp. do popředí, n pak celkový počet pixelů obrázku [7]. Otsu dále ukázal [10], že minimalizace intra-class rozptylu je ekvivalentní maximalizaci tzv. inter-class rozptylu: 2 2 σinter (T ) = σ 2 − σintra (T ) = nB (T )nF (T ) [µB (T ) − µF (T )]2 .

(2.7)

To umožňuje výpočetně méně náročné iterativní řešení celé úlohy, protože si již v každém kroku pro každý z potenciálních prahů Ti (tedy pro každou intenzitu) vystačíme pouze s výpočtem průměru intenzit pozadí a popředí a nemusíme již počítat rozptyly, jako by tomu bylo v případě použití rovnice (2.4). Stačí tedy projít všechny intenzity obsažené v obrázku a pro každou tuto intenzitu Ti spo2 2 čítat σinter (Ti ) podle (2.7). Práh Ti , pro nějž je σinter (Ti ) maximální, je zároveň optimálním prahem T ve smyslu podmínek (2.2) a (2.3) pro binarizaci vstupního obrazu.

2.2

Skeletonizace

Binarizací vstupu získáme dvoubarevný obraz, v němž je černými pixely znázorněn znak abecedy na bílém pozadí. Naším úkolem je nyní obraz skeletonizovat, tedy postupně erodovat pixely z okrajů písmene tak, aby z něj zůstaly pouze jeden pixel široké linie a křivky. Musíme přitom zjistit, aby byly pixely odebírány rovnoměrně

28

a výsledná linie tak vždy ležela ve středu původních tahů a také aby všechny původně spojité linie zůstaly spojité i po provedení skeletonizace. Stejně jako v případě binarizace existuje i pro skeletonizaci mnoho různých algoritmů. My si zde představíme tzv. Hilditchův algoritmus.

2.2.1

Hilditchův algoritmus

Nechť pro každý pixel p ve vstupním obrázku platí, že p ∈ {0, 1}, kde 0 označuje bílou barvu pozadí a 1 černou barvu popředí. Definujme funkci n(p) jako počet nenulových pixelů v bezprostředním okolí pixelu p. Označíme-li pixely sousedící s p v souladu s obrázkem 2.2, pak pro tuto funkci tedy platí: n(p) =

8 X

pi .

(2.8)

i=1

Obrázek 2.2: Okolí pixelu p. Pro případy, kdy p leží na samotném okraji obrazu dodefinujme „chybějícíÿ pixely jeho okolí hodnotou 0, tedy barvou pozadí. Označme dále s(p) jako počet přechodů 0 → 1 v posloupnosti sousedů pixelu p seřazených po směru hodinových ručiček. V případě pixelu p z obr. 2.3 by tedy tato posloupnost počínaje pixelem p1 vypadala takto: (0, 0, 1, 0, 0, 0, 1, 0) a s(p) by tak měla hodnotu 2. S využitím dvou výše definovaných funkcí si již můžeme popsat, jakým způsobem Hilditchovův algoritmus pro skeletonizaci funguje [1]: 29

Obrázek 2.3: Hodnota s(p) pro pixel p je rovna 2. 1. Pro každý nenulový pixel p vypočítej n(p) a s(p). Pokud jsou splněny všechny následující podmínky, označ p příznakem pro vymazání: • 2 ≤ n(p) ≤ 6 Tato podmínka zajišťuje, že nebudou vymazány pixely, pro které platí jeden z následujících případů: – n(p) = 0 a tedy p je osamoceným bodem. – n(p) = 1 a tedy p leží na hrotu nějaké linie. – n(p) = 7, nebo n(p) = 8 a tedy p není hraničním pixelem objektu. • s(p) = 1 Tato podmínka je zárukou zachování spojitosti objektu a zajišťuje, že pixel p nebude odebrán např. v situaci znázorněné na obr. 2.3, kde je s(p) > 1 a odstraněním p by došlo k porušení spojitosti. • p2 · p4 · p8 = 0 nebo s(p2 ) 6= 1 Tato podmínka zajišťuje, že nebudou vymazány 2 pixely široké svislé čáry [1]. • p2 · p4 · p6 = 0 nebo s(p4 ) 6= 1 Tato podmínka zajišťuje, že nebudou vymazány 2 pixely široké vodorovné čáry [1]. 30

2. Vymaž všechny pixely p označené při prvním průchodu obrázkem, tedy polož p = 0. 3. Pokud byly během posledního průchodu vymazány nějaké pixely, vrať se na krok 1. Pokud žádné pixely vymazány nebyly, je skeletonizace dokončena. Výše popsaný Hilditchův algoritmus sice ve většině případů provádí skeletonizaci spolehlivě, v některých případech ovšem selže, protože u nich dojde ke kompletní erozi (příklady jsou na obr. 2.4). I z těchto důvodů jsme se nakonec rozhodli využít mnohem složitější algoritmus popsaný v [6], provádějící skeletonizaci jak dvourozměrných obrázků, tak i třírozměrných objektů, a který byl podobně jako Otsuův binarizační algoritmus opět dostupný jako plugin pro grafický program ImageJ.

Obrázek 2.4: Příklady vzorů, u nichž dojde při použití Hilditchova algoritmu ke kompletní erozi.

31

Kapitola 3 Diskrétní kosinová transformace V úvodu práce jsme při popisu obecného systému pro rozpoznávání vzorů zmínili důležitou úlohu, jakou v celém systému hraje tzv. feature extractor, který ze vstupního vzoru získává vektor nejvýznamnějších charakteristik. Málokdy je totiž užitečné (nebo dokonce možné) předkládat klasifikátoru přímo celý vzor, který se objevil na vstupu systému, a je tedy potřeba jej nejprve nějakým způsobem transformovat. V naší práci byla pro tento účel vybrána diskrétní kosinová transformace [17]. V této kapitole si tedy diskrétní kosinovou transformaci1 představíme, popíšeme její základní vlastnosti a zamyslíme se nad tím, jak nám může pomoci při rozpoznávání rukou psaných znaků.

3.1

Neformální popis

Diskrétní kosinová transformace (dále již jen DCT) patří spolu se známou diskrétní fourierovou transformací či Karhunen-Loéveho transformací „do skupiny metod provádějících takzvané transformační kódování nad diskrétním (vzorkovaným) jednorozměrným či vícerozměrným signálemÿ[17]. V případě zpracování obrazu (dvourozměrného signálu) toto kódování spočívá v nalezení korelací mezi sousedními pixely, což je možno využít pro následné odstranění redundantní informace za účelem datové komprese. K tomu výše zmíněné transformace využívají 1

V celé naší práci budeme, přesněji řečeno, hovořit o druhé z osmi možných druhů diskrétních kosinových transformací označované jako DCT-II. Tato transformace je v praxi nejpoužívanější a bývá tak běžně označována jako „diskrétní kosinová transformaceÿ bez dalších přívlastků. V naší práci se budeme tohoto zvyku držet.

32

převod signálu z prostorové (resp. časové v případě zvukového signálu) domény do frekvenční domény.

Obrázek 3.1: Energie signálu je po provedení diskrétní kosinové transformace soustředěna v několika počátečních koeficientech odpovídajících nejnižším frekvencím. Konkrétně DCT soustřeďuje nejvíce energie původního signálu v nejnižších frekvencích (obr. 3.12 ), což ve spojení s předpokladem, že se většina informace v signálu nachází právě v nižších frekvencích (kupříkladu lidský sluch je schopen vnímat zvuk jen v omezeném rozsahu kmitočtů), přispívá k její vynikající schopnosti datové komprese. V případě obrazové komprese můžeme například převedením do frekvenční domény (matice DCT koeficientů), vynulováním zanedbatelných frekvencí a zpětným převedením do obrázku inverzní transformací snížit počet bitů potřebných pro zachování informačního obsahu původního obrázku. V reálných aplikacích je DCT součástí například ztrátového kompresního for2 Převzato a upraveno z http://upload.wikimedia.org/wikipedia/commons/f/f8/ Dandelion_clock_quarter_dft_dct.png.

33

mátu JPEG, MJPEG, MPEG či DV, její modifikovaná verze3 je zase použita v audio formátech AAC, Vorbis či MP3.

3.2

Formální definice

Formálně je jednorozměrná diskrétní kosinová transformace lineárním, invertovatelným zobrazením F : Rn → Rn . Transformuje tedy vektor reálných čísel (x0 , x1 , ..., xN −1 ) na vektor (X0 , X1 , ..., XN −1 ) a to podle vzorce N −1 X



π Xk = c(k) xn cos N n=0



1 n+ 2

  k

k = 0, ..., N − 1,

(3.1)

kde hodnoty konstant c(k) jsou 1 c(k) = √ pro k = 0, (3.2) N r 2 c(k) = pro 1 ≤ k ≤ N − 1. (3.3) N Hodnota N značí maximální délku signálu (tzv. řád transformace), který je transformace schopna zpracovat. Pokud je vstupní signál delší, je rozdělen na úseky délky maximálně N , které jsou transformovány odděleně [17]. Dvourozměrnou diskrétní transformaci získáme provedením jednorozměrné DCT podél řádků a podél sloupců vstupní matice (obrázku) velikosti N × N a vzorec pro její výpočet je tedy Xk1 ,k2

N −1 N −1 X X



π xm,n cos = c(k1 , k2 ) N n=0 m=0

       1 1 π m+ k1 cos n+ k2 , (3.4) 2 N 2

přičemž pro konstanty tentokrát platí c(k1 , k2 ) = c(k1 ) · c(k2 ),

(3.5)

kde c(k) je definováno stejně jako v případě jednorozměrné DCT. Poznamenejme ještě, že řád dvourozměrné DCT je obecně typu M × N , většinou se však pro zjednodušení výpočtů klade M = N . 3

Založená na DCT-IV.

34

3.3

Získání vektoru příznaků

Po provedení transformace vstupní matice (obrázku) získáme matici DCT koeficientů. V úvodu kapitoly byla zmíněná jedna velmi důležitá vlastnost diskrétní kosinové transformace – nejvíce energie původního signálu shromažďuje v nejnižších frekvencích, což v případě dvourozměrné DCT znamená, že jsou nejvýznamnější koeficienty soustředěny v levém horním rohu transformované matice. Pro získání nejvýznamnějších příznaků z obrázku je tedy vhodné použít takový postup, který by z výsledné matice získal koeficienty právě v pořadí jejich významnosti. V praxi se pro tento účel využívá tzv. „cik-cakÿ průchod maticí (obr. 3.24 ).

Obrázek 3.2: „Cik-cakÿ průchod maticí.

3.4 3.4.1

Proč právě DCT Omezení dimenzionality prostoru všech vstupů

Vstupem našeho systému jsou čtvercové bitmapy velikosti 100 × 100. Po přečtení kapitoly věnované neuronovým sítím je zřejmé, že naučit neuronovou síť s deseti tisíci vstupními neurony jakoukoli netriviálně velkou trénovací množinu by si vyžádalo velké množství času. Navíc by – vzhledem k tomu, jak malý prostor z celého obrázku zaujímá linie každého písmene – měla většina neuronů neustále nulový vstup. Zbytečně bychom tedy v takovém případě plýtvali jak pamětí, tak procesorovým časem. Transformací každého obrázku do, řekněme, vektoru 100 koeficientů dosáhneme stonásobného ušetření paměti a výrazného urychlení učení. 4

Převzato z http://en.wikipedia.org/wiki/File:JPEG_ZigZag.svg.

35

3.4.2

Potlačení odlišností mezi variantami jednoho znaku

Kromě výše zmíněného omezení dimenzionality prostoru všech vstupů má použití DCT i jinou, mnohem důležitější výhodu. Umožňuje nám do značené míry potlačit odlišnosti mezi variantami jednoho znaku. Vezměme si jednoduchý příklad v podobě jednoho písmene a znázorněného na obrázku 3.3 ve dvou různých posunutích a pak v překryvu. Je vidět, že v případě přímého vstupu obrázku do neuronové sítě metodou jeden pixel ↔ jeden vstupní neuron, by měla obě písmena zabírající celkově 59 pixelů „společnýchÿ pouze 12 neuronů z celkových 59. V případě jiných znaků by to mohlo být dokonce ještě méně.

Obrázek 3.3: Vliv posunu písmene na vstupní hodnoty neuronové sítě. Porovnání vektorů DCT koeficientů obou písmen ukázalo, že tyto vektory sice nejsou zcela totožné, nicméně v nich přesto existuje mnoho pozic, kdy příslušný vstupní neuron odpovídající této pozici dostane (v případě stejných znaků abecedy) vždy stejný vstup. To se zdá být nepochybně velkou výhodou oproti prostému „mapováníÿ pixelů obrázku na vstupní neurony, kdy je případná shoda jako v překryvu na obr. 3.3 zcela náhodná. Nakolik je DCT schopna podobné odlišnosti mezi variantami jednoho znaku potlačit, to si ukážeme na jednoduchém experimentu popsaném v kapitole 4.

3.4.3

Osvědčenost při rozpoznávání vzorů

DCT byla úspěšně použita již při předchozích pokusech vytvořit systémy pro rozpoznávání vzorů. V [18] bylo ukázáno, že se výsledky diskrétní kosinové transformace blíží optimální Karhunen-Loéveho transformaci a byla úspěšně použita při rozpoznávání obličejů. Stejně dobrých výsledků bylo dosaženo i v [3] a mnoha dalších pracech. Domnívali jsme se tedy, že přestože mají obrázky písmen jiné 36

charakteristiky než například fotografie obličejů, mohla by DCT stejně tak dobře posloužit při získávání příznaků z těchto písmen. Jak si při tomto úkolu DCT vedla, to uvidíme ve čtvrté a páté kapitole, v nichž výsledky celé naší práce předvedeme.

37

Kapitola 4 Výsledky experimentů 4.1

Vstupní data

Pro naše experimenty byly použity obrázky rukou psaného písmena anglické abecedy, každé z nich zastoupeno dvacetkrát, celkem tedy 520 písmen. Tato písmena byla nejprve napsána na papír, oskenována, rozdělena do 520 jednotlivých obrázků o velikosti 100 × 100 pixelů a následně binarizována a skeletonizována. Skeletonizovaná data pak byla diskrétní kosinovou transformací převedena do vektorů příznaků, jež jsme pro účely tréninku rozdělili v souladu s kapitolou 1.2.1 do trénovací, validační a testovací množiny, a to konkrétně v poměru 6 : 2 : 2.

4.2

Hledání metody pro rozpoznávání znaků

V následujících podkapitolách si popíšeme kroky, které jsme podnikli na cestě k návrhu metody pro rozpoznávání písmen. Rozebereme problémy, jimž jsme museli čelit, a experimentálními výsledky podložíme rozhodnutí, která jsme při jejich řešení učinili.

4.2.1

Vliv největšího koeficientu DCT na průběh učení

První překážkou, se kterou jsme se při naší práci setkali, byla zdánlivě nepochopitelná neschopnost sítě naučit se byť jen podmnožinu vzorových dat. Z průběhu chyby sítě vzhledem k celé trénovací množině (červená křivka v grafu 4.3) je vidět, že učící algoritmus zcela jednoznačně divergoval. Analýzou koeficientů DCT jsme zjistili, že je první koeficient (v literatuře označovaný také jako DC koeficient z angl. direct current) nejen řádově větší než 38

ostatní koeficienty, ale že je také pro všechna písmena téměr totožný. Z tohoto důvodu jsme se domnívali, že pravděpodobně nenese žádnou pro klasifikaci podstatnou informaci a zkusili jsme tedy síť naučit trénovací data znovu, tentokrát však se zanedbáním tohoto největšího koeficientu. Jak znázorňuje zelená křivka na obr. 4.3, tak se tímto opatřením schopnost sítě naučit se vzorová data dramaticky zlepšila.

4.2.2

Test rotační invariance

Pro otestování vhodnosti DCT jako mechanismu pro získávání příznaků v našem systému, zejména co se týče schopnosti potlačovat odlišnosti mezi variantami jednotlivých znaků (kapitola 3.4.2), jsme si připravili jednoduchý pokus. Vytvořili jsme sadu 26 ručně psaných písmen anglické abecedy, kterou jsme následně rozmnožili rotací každého písmene (příklad v podobě rotace písmene h je na obr. 4.1). Na původní sadu písmen jsme natrénovali neuronovou síť a po skončení učení jsme jí předložili k přečtení rozšířenou množinu s rotovanými modifikacemi původních písmen (tedy s obrázky, se kterými při učení nepřišla vůbec do styku).

Obrázek 4.1: Příklad rotace písmene h. Výsledky pokusu byly příznivé, až na několik chyb si DCT vedla dobře (histogram na obr. 4.2). Nejvíce problémů síti způsobilo už výše zmíněné písmeno h. Neuronová síť totiž – zcela správně! stačí se znovu podívat na obr. 4.1 – klasifikovala několik verzí tohoto písmene pootočených proti směru hodinových ručiček jako písmeno b. Obecně se všechny potíže, které měla síť s rozpoznáním některých písmen, týkaly téměř výhradně extrémních rotací. Jelikož DCT evidentně dokáže z obrázku získat informace o liniích, křivkách a jejich úhlech, tak se síť při tréninku učí řídit se i těmito příznaky, což při následném předložení některých rotovaných písmen způsobuje problémy. DCT tedy co se týče rotační invariance sice rozhodně není všemocná, ale obecně si v potlačování geometrických transformací vzorových písmen vedla poměrně dobře. Vlivy rotací v rozumných mezích, jaké by se mohly vyskytnou v 39

reálném nasazení, a které v případě tohoto pokusu tvořily něco přes polovinu vzorů, zvládla omezit na výbornou.

4.2.3

Normalizace vstupních dat a rychlost učení

V kapitole 1.3.2 jsme zmínili význam normalizace vstupů neuronové sítě pro omezení její špatné podmíněnosti a urychlení jejího učení. Zkusili jsme tedy porovnat, jak se bude síť učit normalizovaná data v porovnání s daty nenormalizovanými. Výsledky tohoto pokusu, znázorněné v grafu na obr. 4.4, jasně vypovídají o tom, že se síť nejenom dokázala naučit normalizovaná data s nižší chybou, ale i samotný průběh učení byl hladší a bez fluktuací, k nimž docházelo při použití nenormalizovaných trénovacích dat.

4.2.4

Vliv binarizace a skeletonizace na průběh učení

V úvodu druhé kapitoly jsme popsali význam binarizace a skeletonizace pro potlačení rozdílů mezi psacími potřebami. Vyslovili jsme také předpoklad, že by skeletonizací docílené odstranění redundance ve vstupních obrázcích mohlo mít vliv i na získání kvalitnějších příznaků, což by se zase teoreticky mohlo projevit na snazším učení neuronové sítě. Experiment, jehož výsledky jsou znázorněny v grafu 4.5, ale tuto domněnku přesvědčivě vyvrátil, protože se neuronová síť byla schopna naučit nepředzpracovaná data stejně dobře jako data binarizovaná a skeletonizovaná. To vypovídá o tom, že byly příznaky, získané diskrétní kosinovou transformací z neskeletonizovaných obrázků, evidentně stejně kvalitní jako příznaky, jež byly získány z jejich předzpracovaných variant.

4.2.5

Výběr aktivační funkce skrytých neuronů

V kapitole 1.3.2 jsme navrhli využití hyperbolického tangens jako aktivační funkce skrytých neuronů namísto obvykle používané logistické sigmoidy. Důvodem byla přibližná normalizovanost výstupů těchto neuronů a s tím související omezení špatné podmíněnosti sítě [9]. Na obr. 4.6 je vyobrazen výsledek pokusu, při němž jsme porovnali dvě neuronové sítě s totožnou topologií, ale s odlišnými aktivačními funkcemi skrytých neuronů. V první síti počítaly skryté neurony své výstupy logistickou sigmoidou, v druhé síti pak určovaly své výstupní stavy hyperbolickým tangens. Výsledky pokusu ukázaly, že se – v souladu s argumentací v kapitole 1.3.2 – opravdu vyplatí

40

používat místo klasické sigmoidy hyperbolický tangens. Neuronová síť využívající hyperbolický tangens se totiž dokázala přiblížit k lokálnímu minimu chybové funkce mnohem rychleji než síť, která používala ve skrytých neuronech logistickou sigmoidu.

4.2.6

Výběr metody učení

Kapitola 1.1.5 byla věnována argumentaci ve prospěch inkrementálního způsobu učení. V naší práci jsme zpočátku využívali metodu akumulovaného učení, protože byla v námi využívaných zdrojích považována za korektnější a rychlejší. Např. v [15] se o inkrementálním učení píše, že ”[p]rotože gradient parciální chybové funkce se pro [aktuální] tréninkový vzor počítá pomocí již aktualizovaných vah podle předchozího vzoru, nedochází k minimalizaci celkové chyby sítě vzhledem k tréninkové množině přesně podle gradientní metody [. . .] a podle našich zkušeností tento postup zpomaluje konvergenci.” V našem případě ale inkrementální učení nejen spolehlivě konvergovalo, metoda akumulovaného učení navíc dokonce jasně divergovala (graf na obr. 4.7). Při snížení parametru rychlosti učení o řád se sice neuronová síť již začala trénovací data učit, v rychlosti konvergence ale stále akumulované učení silně zaostávalo za učením inkrementálním. Tyto výsledky jsou tedy zcela v souladu s prací [19], v níž autoři doporučují využívat inkrementální učení namísto učení akumulovaného právě z důvodu rychlejší konvergence a větší stability učení.

4.2.7

Navržená metoda

Jako příznaky znaků a vstupní vektory neuronové sítě jsme využili 300 koeficientů DCT, přičemž jsme zanedbali první, největší, koeficient. Požadované výstupy sítě byly zadány vektory 26 binárních hodnot – v těchto vektorech vždy jediná nenulová hodnota na i-té pozici odpovídala i-tému písmenu anglické abecedy nacházejícímu se na příslušném vstupním obrázku (první pozice ve vektoru tedy odpovídala písmenu a, druhá pozice písmenu b atd.). Pro klasifikaci jsme použili dopřednou neuronovou síť s 300 vstupními neurony, 400 skrytými neurony a 26 výstupními neurony. Aktivační funkcí skrytých neuronů byl zvolen hyperbolický tangens, v případě výstupních neuronů jí pak byla logistická sigmoida. V souladu s podobou trénovací množiny byl výstup neuronové sítě interpretován vždy tak, že nacházela-li se nejvyšší výstupní hodnota na i-tém výstupním neuronu, pak byl předložený vstup klasifikován jako i-té písmeno anglické abecedy. 41

Neuronovou síť jsme trénovali metodou inkrementálního učení při rychlosti učení stanovené na hodnotu 0.01. Její trénink trval vždy maximálně 100 epoch, přičemž nejlepší zobecňující konfigurace sítě byla určena postupem popsaným v kapitole 1.2.2.

42

6 5 4 3 2 1 0

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

r

s

t

u

v

w

x

y

z

100 50

kompletní vektor DCT koeficientů vektor koeficientů bez největší složky

0

Hodnota chybové funkce

150

Obrázek 4.2: Histogram úspěšnosti DCT při testu rotační invariance.

0

50

100

150

200

Počet epoch od počátku učení

Obrázek 4.3: Vliv zanedbání největšího koeficientu DCT na průběh učení.

43

150 100 50 0

Hodnota chybové funkce

nenormalizovaná trénovací data normalizovaná trénovací data

0

50

100

150

200

Počet epoch od počátku učení

120

Obrázek 4.4: Vliv normalizace vstupních dat na rychlost učení.

80 60 40 0

20

Hodnota chybové funkce

100

originální naskenovaná data binarizovaná a skeletonizovaná data

0

50

100

150

200

Počet epoch od počátku učení

Obrázek 4.5: Vliv binarizace a skeletonizace na průběh učení. 44

150 100 50 0

Hodnota chybové funkce

logistická sigmoida hyperbolický tangens

0

50

100

150

200

Počet epoch od počátku učení

150 100

akumulované učení, rychlost učení 0.01 akumulované učení, rychlost učení 0.001 inkrementální učení, rychlost učení 0.01

0

50

Hodnota chybové funkce

200

Obrázek 4.6: Vliv aktivační funkce skrytých neuronů na rychlost učení.

0

50

100

150

200

Počet epoch od počátku učení

Obrázek 4.7: Porovnání rychlostí akumulovaného a inkrementálního učení 45

Kapitola 5 Testování navržené metody Navrženou metodu jsme otestovali na dvou sadách znaků s odlišným rukopisem. První sada byla využita při experimentech, které vedly k návrhu konečné metody, druhá sada pak byla získána až po dokončení naší práce a posloužila tak pro nezávislé otestování našich závěrů.

5.1

Rukopis použitý při návrhu metody

Podívejme se nejprve, jak byla neuronová síť úspěšná vzhledem k datům, která algoritmus zpětného šíření chyby využíval pro adaptaci vah, tedy vzhledem k trénovací množině. Z grafů v předchozí kapitole bylo zřejmé, že se námi navržená neuronová síť dokázala naučit trénovací vzory velmi spolehlivě, alespoň tedy co se týče minimalizace chyby sítě počítané pomocí rovnice (1.7). Tato chyba však nemusí vždy vypovídat o procentuální úspěšnosti, o níž nám jde při rozpoznávání znaků textu především. Histogram na obr. 5.1a ale dokazuje, že neuronová síť v našem případě rozpoznala po skončení svého učení trénovací data se stoprocentní úspěšností. Vysoká úspěšnost vzhledem k trénovací množině je ale pouze nutnou a nikoli postačující podmínkou pro použitelnost jakéhokoli systému pro rozpoznávání vzorů. Téměř vždy nás totiž zajímá zejména schopnost generalizovat neznámá data. Na histogramu 5.1b vidíme, že neuronová síť rozpoznala stoprocentně i většinu validačních dat. Jediné písmeno, které neuronová síť z nám neznámých příčin zcela nezvládla přečíst, bylo písmeno x. Chyby při čtení ostatních písmen byly většinou poměrně opodstatněné a ospravedlnitelné, důvody si rozebereme v celkovém hodnocení na konci kapitoly. Podle vysoké úspěšnosti vzhledem k validační množině by se tedy mohlo zdát, 46

že se nám podařilo nalézt neuronovou síť s velmi dobrou schopností generalizovat neznámé vstupy. Jak jsme ale vysvětlili v kapitole 1.2.1, nesmíme zobecňovací schopnost neuronových sítí posuzovat pouze na základě validační množiny. Pro tyto účely potřebujeme zcela nezávislou množinu testovacích dat. Jak je vidět na histogramu na obr. 5.1c, úspěšnost neuronové sítě vzhledem k testovací množině byla přibližně stejně vysoká jako její úspěšnost vzhledem k validačním datům. Jelikož testovací množina obsahuje data, která neuronová síť neviděla nikdy, znamená to tedy, že jsme nalezli neuronovou síť s velmi spolehlivou schopností zobecňovat vstupy, s nimiž se při svém tréninku nesetkala.

5.2

Rukopis pro nezávislé otestování

Druhá sada znaků byla tvořena menším počtem vzorových písmen než první sada, protože obsahovala písmena ne ze dvaceti, ale pouze ze čtrnácti abeced. Neuronovou síť jsme tímto postavili před těžší úkol – při menším objemu dostupných trénovacích dat jsme na ni kladli stejně vysoké nároky na schopnost zobecňování. Při pohledu na tři histogramy na obr. 5.3 znázorňující úspěšnost neuronové sítě vůči druhé sadě znaků ale vidíme, že si i v případě nezávislého rukopisu vedla síť srovnatelně dobře, jako tomu bylo při rozpoznávání znaků z první sady. Tímto výsledkem tak byla potvrzena nezávislost naší metody na rukopisu či použité psací potřebě.

5.3

Porovnání se čtením pokusné osoby

Na závěr jsme porovnali spolehlivost naší metody s případem, kdy rozpoznávání znaků provedl člověk. Testované osobě jsme předložili k přečtení testovací množiny písmen z první i druhé sady a úspěšnost jejího čtení jsme opět znázornili v podobě histogramů (obr. 5.3a a 5.3b). Srovnáním těchto výsledků s předchozími histogramy 5.1c a 5.2c vidíme, že neuronová síť za testovanou osobou ve čtení znaků nikterak nezaostávala. Pokud bychom tedy lidský mozek považovali za jakýsi referenční model ideálního mechanismu pro rozpoznávání vzorů, pak tento experiment dokázal, že se nám podařilo navrhnout velmi spolehlivou metodu pro rozpoznávání rukou psaných znaků.

47

5.4

Shrnutí výsledků testů

Neuronová síť byla poměrně často zmatena písmeny h a k, případně také l. Je to vcelku pochopitelné, protože mají již na první pohled společné charakteristiky v podobě dlouhých protáhlých linií a křivek a liší se pouze minimálně. Ze stejných důvodů docházelo u některých testovaných sítí také k omylům v případě písmen g a q, případně j a y. Kromě těchto omylů, způsobených vyloženě nesprávnou klasifikací, docházelo i k chybám zapříčiněným těžko čitelným rukopisem (příklady na obr. 5.4 a 5.5), výjimečně i procesem binarizace a skeletonizace. U některých písmen totiž během předzpracování došlo k jejich deformaci a ke ztrátě důležitých příznaků. Nejčastěji se tento problém objevoval u písmene k, jehož komplikovaný charakter často způsoboval vymazání částí, jež ho odlišovaly od písmene l (příklady na obr. 5.6). Tyto deformace jsou ale bohužel určitou daní za možnost potlačení rozdílů mezi různými psacími potřebami a nelze jim zabránit. K úspěšnosti rozpoznávání jednotlivých znaků ještě dodejme, že v praxi tvoří obvykle pouze jádro komplexnějších systémů pro převod tištěného či rukou psaného textu do digitální podoby. Tyto systémy nejprve rozdělí vstupní dokument do jednotlivých řádek, řádky do slov a slova pak do samostatných písmen, která jsou následně rozpoznávána a z nichž je pak celý text zpětně sestaven. Důležité pro nás je, že kontext jednotlivých písmen v daném slově poskytuje možnost kontroly přečteného slova proti slovníku a případně následnou opravu chybně rozpoznaných písmen. Konkrétně v našem případě, kdy docházelo k chybám pouze v omezeném okruhu znaků, by mělo být možné se tímto způsobem přiblížit až ke 100% úspěšnosti při čtení.

48

100 80 60 40 20 0

Procentuální úspěšnost při čtení

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

r

s

t

u

v

w

x

y

z

r

s

t

u

v

w

x

y

z

r

s

t

u

v

w

x

y

z

100 80 60 40 20 0

Procentuální úspěšnost při čtení

(a) trénovací množina

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

100 80 60 40 20 0

Procentuální úspěšnost při čtení

(b) validační množina

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

(c) testovací množina

Obrázek 5.1: Úspěšnost neuronové sítě při čtení první sady písmen. 49

100 80 60 40 20 0

Procentuální úspěšnost při čtení

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

r

s

t

u

v

w

x

y

z

r

s

t

u

v

w

x

y

z

r

s

t

u

v

w

x

y

z

100 80 60 40 20 0

Procentuální úspěšnost při čtení

(a) trénovací množina

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

100 80 60 40 20 0

Procentuální úspěšnost při čtení

(b) validační množina

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

(c) testovací množina

Obrázek 5.2: Úspěšnost neuronové sítě při čtení druhé sady písmen. 50

100 60 20 0

Procentuální úspěšnost při čtení

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

r

s

t

u

v

w

x

y

z

v

w

x

y

z

100 80 60 40 20 0

Procentuální úspěšnost při čtení

(a) testovací množina z první sady znaků

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

r

s

t

u

(b) testovací množina z druhé sady znaků

Obrázek 5.3: Úspěšnost čtení pokusné osoby.

51

Obrázek 5.4: Příklady chybně rozpoznaného písmene u z první sady znaků. První dva znaky byly klasifikovány jako v, třetí jako n. Třetí chyba byla způsobena tím, že trénovací vzory pro písmeno n byly k nerozeznání od písmene u a neuronová síť tak v tomto případě rozhodla v podstatě správně.

Obrázek 5.5: Nečitelné podoby písmene s ze druhé sady znaků. Prvním byla neuronová síť zcela zmatena a přečetla jej jako b, druhé pak klasifikovala jako r.

Obrázek 5.6: Deformace písmene k z první sady znaků(rozpoznáno jako l ) a z druhé sady znaků (rozpoznáno jako h) způsobená skeletonizací. Právě komplikovaný charakter písmene k způsoboval skeletonizačnímu procesu zřejmě největší problémy.

52

5.5

Rychlost rozpoznávání

Pro použitelnost většiny systémů pro rozpoznávání textu v reálném nasazení (např. při automatickém třídění zásilek podle adres) je podstatná schopnost pracovat v reálném čase. Rychlost naší metody jsme otestovali na počítači s procesorem Intel Pentium Dual Core SU4100 1.3 GHz, se 3 GB RAM a 64 bitovým operačním systémem Ubuntu 9.10 Karmic Koala. Námi vytvořený softwarový prototyp pro rozpoznávání rukou psaných znaků (naprogramovaný v jazyce C++ a zkompilovaný překladačem GCC verze 4.4.1 při zapnutí všech dostupných optimalizací) přečetl testovací množinu tvořenou 104 znaky za 96 sekund. Nejpomalejším prvkem celého procesu se ukázala být diskrétní kosinová transformace, jelikož jsme pro jednoduchost naprogramovali pouze její nejprimitivnější verzi pracující v kvadratickém čase. Pouze výpočet koeficientů DCT tak zabral celých 81 sekund. V případě využití naší metody jako součásti komplexnějšího systému pro rozpoznávání textu by byla zcela jistě použita rychlejší implementace DCT (obvykle se využívá implementace pracující v čase O(N log N )) a proces čtení by se tak urychlil na pouhý zlomek námi naměřené hodnoty.

53

Kapitola 6 Závěr Cílem této práce bylo navrhnout metodu pro rozpoznávání rukou psaných znaků s využitím dopředné neuronové sítě jako základního klasifikačního mechanismu. Rozebrali jsme nejen teoretické základy nutné pro použití neuronových sítí, ale zároveň jsme předložili mnoho důležitých návrhů a doporučení platných pro jakoukoli aplikaci tohoto výpočetního modelu v praxi. Naším cílem byl totiž nejen samotný návrh metody pro rozpoznávání rukou psaných písmen, ale také poskytnutí vodítek pro tvorbu obecně jakéhokoli systému pro rozpoznávání vzorů. Pro získání a zdůraznění charakteristik jednotlivých znaků jsme navrhli využít diskrétní kosinovou transformaci, přičemž hlavním důvodem bylo omezení dimenzionality prostoru vstupů neuronové sítě a potlačení odlišností mezi variantami jednoho znaku. Diskrétní kosinová transformace se osvědčila v mnoha předchozích aplikacích rozpoznávání vzorů a předpokládali jsme, že bude dobře sloužit i jako součást námi vypracované metody. Dalé jsme navrhli využití binarizace a skeletonizace jako způsobu předzpracování vstupních dat. Toto předzpracování zajišťuje potlačení rozdílů mezi různými druhy psacích potřeb při zachování veškerých geometrických a topologických vlastností jednotlivých písmen a mělo by tedy být nepostradatelnou součástí jakéhokoli systému pro rozpoznávání rukou psaného textu. Navrženou metodu jsme otestovali na dvou odlišných vzorech rukopisu, přičemž jedna sada znaků byla použita při samotném výzkumu a druhá byla získána až po dokončení naší práce a byla na ní tedy zcela nezávislá. Test na obou sadách písmen dopadl velice dobře, v obou případech se úspěšnost neuronové sítě při rozpoznávání neznámých dat pohybovala kolem 90%, přičemž nezanedbatelný podíl nesprávně přečtených písmen byl v případě některých znaků dán zejména těžko čitelným rukopisem. Jak ukázal test s předložením testovacích znaků po-

54

kusné osobě, tak většinu chyb nelze brát jako nedostatek naší metody, protože se jich při čtení dopustil i člověk. Naše metoda se po důkladném otestování ukázala být velmi vhodným kandidátem pro případný budoucí návrh kompletního systému pro převod rukou psaného textu do digitální podoby, kde by hrála centrální roli v podobě mechanismu, který by v reálném čase rozpoznával jednotlivé znaky získané z celých slov. Možnost kontroly a případné opravy chybně klasifikovaných znaků s pomocí slovníku, kterou by jí dal kontext každého znaku v daném slově, by měl také umožnit přiblížit se až ke 100% úspěšnosti rozpoznávání.

55

Literatura [1] Azar (1997): Hilditch’s Algorithm for Skeletonization. McGill University. http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/azar/ skeleton.html (1. srpna 2010). [2] Cybenko (1989): Approximations by superpositions of sigmoidal functions. Mathematics of Control, Signals, and Systems, Volume 2, Number 4, 303314. [3] Hafed, Levine (2001): Face Recognition Using the Discrete Cosine Transform. International Journal of Computer Vision, Volume 43, Issue 3, 167–188. [4] Hornik (1991): Approximation capabilities of multilayer feedforward networks. Neural Networks, Volume 4, Issue 2, 251–257. [5] Knuth (1998): The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, Reading, Massachusetts, 2. edice, 513–558. [6] Lee, Kashyap a Chu (1994): Building skeleton models via 3-D medial surface/axis thinning algorithms. CVGIP: Graphical Models and Image Processing, Volume 56, Issue 6, 462–478. [7] Morse (2000): Lecture notes on thresholding. Brigham Young University. http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/ MORSE/threshold.pdf (1. srpna 2010). [8] Orr, Schraudolph a Cummins (1999): Neural Networks: Overfitting. Williamette University. http://www.willamette.edu/~gorr/classes/cs449/ overfitting.html (1. srpna 2010). [9] Orr, Schraudolph a Cummins (1999): Neural Networks: Preconditioning the Network. Williamette University. http://www.willamette.edu/~gorr/ classes/cs449/precond.html (1. srpna 2010). 56

[10] Otsu (1979): A Threshold Selection Method from Gray-Level Histograms. IEEE Transactions on Systems, Man and Cybernetics, Volume 9, Number 1, 62–66. [11] Priddy, Keller (2005): Artificial Neural Networks: An Introduction. SPIE Tutorial Texts In Optical Engineering, Vol. TT68, 42–43. [12] Rojas (1996): Neural Networks - A Systematic Introduction. Springer-Verlag, Berlin, New-York, 23. [13] Rojas (1996): Neural Networks - A Systematic Introduction. Springer-Verlag, Berlin, New-York, 42. [14] Rojas (1996): Neural Networks - A Systematic Introduction. Springer-Verlag, Berlin, New-York, 391. [15] Šíma, Neruda (1996): Teoretické otázky neuronových sítí. Matfyzpress, Praha, 52–62. [16] Tisse, Martin, Torres a Robert (2002): Person Identification Technique using Human Iris Recognition. Proceedings of Vision Interface, 294–299. [17] Tišnovský (2007), Programujeme JPEG: diskrétní kosinová transformace (DCT). Root.cz. http://www.root.cz/clanky/ programujeme-jpeg-diskretni-kosinova-transformace-dct/ (1. srpna 2010). [18] Turk, Pentland (1991): Face Recognition Using Eigenfaces. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 586– 591. [19] Wilson, Martinez (2003): The general inefficiency of batch training for gradient descent learning, Neural Networks, Volume 16, Issue 10, 1429–1451.

57

Dodatek: Obsah CD-ROM Abychom umožnili reprodukování výsledků a případné navázání na naši práci, poskytujeme na přiloženém CD-ROM jak veškerá data využitá při návrhu a testování naší metody, tak námi naprogramovaný software. Je důležité poznamenat, že tento software vznikl jen jako platforma pro naše experimenty a je tedy spíše než kompletní aplikací pouze nepříliš zdokumentovaným prototypem. Software byl vytvořen a otestován na počítači s operačním systémem Ubuntu1 9.10 Karmic Koala (distribuce operačního systému GNU/Linux) a je kombinací několika malých konzolových aplikací naprogramovaných v jazyce C++ s využitím skriptovacích možností standardního linuxového shellu Bash (verze 4.0.33). Zdrojové soubory byly zkompilovány překladačem g++ (verze 4.4.1), jež je součástí na internetu volně dostupného souboru překladačů GCC2 (GNU Compiler Colection). Pro binarizaci a skeletonizaci jsme využili rovněž volně dostupný grafický program ImageJ3 (verze 1.43b). Obsah přiloženého CD-ROM je následující: • cogito/ Jednoduchá knihovna pro práci s dopřednými neuronovými sítěmi naprogramovaná v jazyce C++. Pro zkompilování je potřeba vstoupit do adresáře cogito/ a spustit příkaz make. Základní dokumentace ke knihovně je dostupná v doc/html/index.html. • data/ Obrazová vstupní data ve formátu PNG. Adresář obsahuje kromě znaků v původní naskenované podobě i jejich binarizované a skeletonizované verze a v příslušných textových souborech i trénovací, validační a testovací množiny, 1

http://www.ubuntu.com/ http://gcc.gnu.org/ 3 http://rsbweb.nih.gov/ij/ 2

58

které byly použity pro trénink a testování neuronových sítí. Kromě těchto vstupních dat se zde nacházejí i soubory s natrénovanými sítěmi, které jsme využili pro otestování naší metody. • imagej macros/ Makra pro program ImageJ, která jsme využili pro binarizaci a skeletonizací vstupních obrázků. • r scripts/ Skripty pro statistický systém R, které jsme použili pro generování grafů v této práci. • reader/ Sada konzolových aplikací a skriptů sloužících např. pro výpočet diskrétní kosinové transformace, tvorbu trénovacích, validačních a testovacích množin, trénování neuronových sítí a jejich následné využití pro rozpoznávání znaků. Kompilaci je opět nutné spustit příkazem make. Pro pohodlnější použití je vhodné přidat podadresář bin/ se skripty a zkompilovanými programy do proměnné $PATH, případně jeho obsah nakopírovat příkazem make install do adresáře ~/bin (pokud se tento již v $PATH nachází). • Martin Petr-Bakalarska prace.pdf Text této práce ve formátu PDF. • Obsah CD-ROM.txt Text tohoto dodatku. Na závěr tohoto dodatku ještě poznamenejme, že je samozřejmě možné pro reprodukování našich výsledků či případné pokračování v naší práci využít jakékoli aplikace a nástroje, které budou umožňovat výpočet binarizace, skeletonizace a diskrétní kosinové transformace a práci s dopřednými neuronovými sítěmi v takovém rozsahu, jaký byl využit této práci.

59