Nadpis
Výběr příznaků a návrh klasifikátoru

Výběru příznaků je třeba věnovat zvláštní pozornost, neboť jejich nevhodná volba může znatelně snížit úspěšnost klasifikace. Navrhli jsme následující příznakový popis segmentových číslic:

Vektor příznaků má sedm složek odpovídajících sedmi segmentům číslice. Každý příznak vyjadřuje míru určitosti, s jakou je segment číslice aktivní, a nabývá hodnot v intervalu (0, 3). Segment ve třech místech přetneme úsečkou obsahující tři obrazové body. Pro každou z úseček zjišťujeme, zda alespoň jeden její bod je aktivní (tedy černý) . Pokud ano, inkrementujeme příznak o 1. Stejně postupujeme i u dalších dvou úseček. Pokud je celý segment aktivní, nabývá příznak hodnoty 3. V případě, že celý segment neobsahuje ani jeden aktivní bod, nabude hodnoty 0.


Podívejme se na obrázek. Horní segment nabude hodnoty 1, neboť pouze první úsečka obsahuje alespoň jeden aktivní bod. Naproti tomu dolní segment nabude hodnoty 2, protože alespoň jeden aktivní bod obsahuje první a třetí úsečka (dvě úsečky s alespoň jedním aktivním bodem a proto má příznak hodnotu 2). Příznak popisující prostřední segment bude mít maximální hodnotu - tedy 3, protože všechny tři úsečky, které segment přetínají, obsahují alespoň jeden aktivní bod.

Nyní sestavíme vektor příznaků číslice na obrázku. Víme, že příznakový vektor bude obsahovat sedm položek. Definujeme-li pořadí příznaků takto:

  1. -   horní segment
  2. -   pravý horní segment
  3. -   pravý dolní segment
  4. -   dolní segment
  5. -   levý dolní segment
  6. -   levý horní segment
  7. -   prostřední segment

bude vektor příznaků číslice na obrázku vypadat takto: [1, 3, 0, 2, 3, 0, 3].

Pro každou třídu existuje etalon - typický (ideální) zástupce třídy. Etalony jsou zobrazeny na následujícím obrázku. Ve fázi trénování vyčíslíme příznaky všech etalonů a uložíme je do paměti - tím natrénujeme klasifikátor.


Již víme, jakým způsobem získáme příznaky popisující klasifikovanou číslici. Pro klasifikaci podle kritéria minimální chyby je nutné vyčíslit vzdálenost klasifikované číslice od jednotlivých etalonů. Jako vzdálenost budeme uvažovat prostý součet rozdílů stejnolehlých složek vektorů. Potom vzdálenost klasifikované číslice z prvního obrázku od etalonu pro číslici "dvě", která má příznakový vektor [3, 3, 0, 3, 3, 0, 3], je:


[|3-1|+|3-3|+|0-0|+|3-2|+|3-3|+|0-0|+|3-3|] = 3

Vlastní zařazení do třídy je poměrně jednoduché. Vypočítáme vzdálenosti vektoru klasifikované číslice od vektorů příznaků všech etalonů a zařadíme číslici do třídy, pro kterou bude tato vzdálenost minimální.



Implementace

Nyní se zaměříme na programovou realizaci metody rozpoznávání metodou minimální vzdálenosti. Jak jsme se již zmínili příklad jsme naprogramovali jako applet v jazyce Java. Většinu programátorské práce jsme strávili nad vytvářením příjemného uživatelského prostředí s intuitivním ovládáním - viz obrázek.



Základní použité knihovny a techniky

Pro realizaci grafického uživatelského rozhraní (GUI) jsme použili tzv. Abstract Window Toolkit (AWT), což je (zjednodušeně řečeno) knihovna tříd Javy pro práci se vstupy a výstupy v graficky orientovaných operačních systémech (Windows95/NT/98, X Window).

Při programování jsme se nespokojili pouze s třídami, které nabízí AWT, ale vytvořili jsme i třídy vlastní. Zejména proto, že některé standardní objekty nevypadají příliš dobře. Například se nám nelíbilo použití standardních tlačítek (z třídy java.awt.Button). Naprogramovali jsme tedy vlastní třídu ImageButton, která implementuje všechny funkce tlačítka a navíc umožňuje kreslit na tlačítka obrázky.

Java umožňuje tzv. multithreading neboli paralelní běh dvou či více částí programu (tzv. vláken). Této vlastnosti jsme při programování mnohokrát využili. Např. při inicializaci appletu spouštíme samostatné vlákno, které nahrává ze sítě obrázky a zvukové klipy. Jiným příkladem může být obsluha události "stisk tlačítka", kterou spouštíme jako samostatné vlákno, takže i když probíhá časově náročná operace (např. extrakce příznaků), může applet reagovat na další události.


Použitý vývojový prostředek

Programovali jsme ve vývojovém prostředí Java WorkShop 2.0 od firmy Sun Microsystems. Projekt jsme nazvali Digits a hlavní soubor projektu Digits.prj. Pro překlad jsme používali kompilátor Java Development Kit (JDK), verze 1.1.3.


Modulární stavba programu

Vytvořili jsme osm tříd, každá je definována v samostatném souboru. Zde je jejich výčet s krátkým popisem významu třídy.

Digits.java
- hlavní třída appletu, zodpovídá za zobrazování všech grafických komponent (tlačítka, kreslicí plocha, tabule pro výpis informací) a přehrávání zvuků
Platno.java
- implementuje plochu, na které se kreslí číslice, zpracovává události od myši a rozsvěcuje a zhasíná příslušné body
ImageButton.java
- předefinovává standardní třídy Button, abychom mohli používat tlačítka s obrázky (vypadají mnohem lépe)
Tracker.java
- vlákno, které se spouští při startu appletu a zodpovídá za nahrávání obrázků ze sítě
Zalozky.java
- implementace přepínače mezi rychlou a pomalou animací. Pomalá varianta je vhodná pro několik prvních spuštění programu - je dobře vidět postup, jakým klasifikace probíhá.
Extrakce.java
- vlákno, které zodpovídá za extrakci příznaků. Spouští se při obsluze události stisk tlačítka "Extrakce příznaků" a volá funkci getPriznaky().
Vzdalenosti.java
- vlákno, spouštěné při stisku tlačítka "Výpočet vzdáleností" a volající funkci getVzdalenosti()
Klasifikace.java
- vlákno, které spouští funkci klasifikuj(), je spuštěné po stisku tlačítka "Klasifikace"

Všechny zdrojové texty programu si jsou umístěny v adresáři Digits. Spolu s nimi jsou v tomto adresáři i přeložené třídy (soubory s příponou .class) a podadresáře imgsound s obrázky a zvukovými klipy.


Klíčové algoritmy

Při programování jsme od sebe důsledně oddělili tři fáze klasifikace:

  1. extrakce příznaků
  2. výpočet vzdáleností od etalonů
  3. klasifikace (výběr minima)

Každá fáze je realizována jako samostatná funkce a spouští se jako obsluha události - stisk příslušného tlačítka. Studenti tak mohou spouštět jednotlivé fáze samostatně a sledovat jejich průběh.


Zhodnocení algoritmu

Program byl již od počátku zamýšlen jako co nejjednodušší, a proto si nedělá nárok na nejlepší možnou klasifikaci. Myslíme si však, že je ideální pro demonstraci kritéria minimálních vzdáleností a že s jeho pomocí studenti bez problémů proniknou k jádru metody.

Algoritmus by se dal významně vylepšit. Uveďme alespoň některá možná zlepšení:

Pro rozpoznávání normálních (ne segmentových) číslic se v praxi používají jiné metody, které dávají mnohem lepší výsledky. Zejména metoda masek má vysokou úspěšnost a používá se v praxi pro rozpoznávání poštovních směrovacích čísel.


Ovládání programu

Program se spouští automaticky po zobrazení HTML stránky, na které je umístěn. K řízení běhu programu slouží především pětice tlačítek, která jsou umístěna ve střední části panelu (viz obr.).


Zobrazit etalony
- kreslí etalony na plátno v levé části plochy appletu (začíná etalonem číslice 0)
Smazat plátno
- smaže kreslicí plochu
Extrakce příznaků
- spustí demo, které uživateli ukáže, jakým způsobem se příznaky počítají
Výpočet vzdáleností
- zahájí ukázku výpočtu vzdáleností vektoru příznaků klasifikované číslice od vektorů příznaků všech deseti etalonů
Klasifikace
- předvede, jakým způsobem se klasifikovaná číslice zařadí do třídy

Pod tlačítky se nachází přepínač mezi pomalou a zrychlenou variantou výpočtu. Pomalá varianta je vhodná při prvním spuštění, kdy uživatel může sledovat postup klasifikace krok za krokem. Pokud uživatele detaily klasifikace nezajímají, lze přepnout rychlost klasifikace na "rychle". Tím se ignorují čekací smyčky používané při zobrazování informací o průběhu výpočtu v pravé části plochy appletu a uživatel nemusí dlouho čekat.

Nakonec se ještě zmíníme o ploše na kreslení číslic, umístěné v levé části appletu. Plocha je rozdělena na 9 x 15 čtverců, každý z nich představuje jeden obrazový bod. Číslice se kreslí myší při stisknutém levém tlačítku. Pravým tlačítkem myši můžeme mazat již nakreslené.


Instalace

Applet není třeba instalovat, pokud jej spouštíme z výukového programu. Chceme-li applet spustit samostatně, otevřeme soubor Digits.html v adresáři Digits Java-kompatibilním WWW prohlížečem.

V současnosti (květen 1999) je applet spustitelný prohlížeči Microsoft Internet Explorer 4.0, Netscape Navigator 4.5 a HotJava 1.0. Applet lze spustit i pomocí programu Java Applet Viewer, který je součástí instalace Java Development Kit, ovšem tento program neobsahuje podporu češtiny, takže akcentované znaky se nezobrazují zcela korektně.