Student World

Rozpoznávání ručně psaných znaků a textů (Hand Written Character Recognition – HWCR) je jednou z rychle se rozvíjejících disciplín v informatice. S nárůstem informačních systémů ve všech odvětvích lidské činnosti je stále více cítit potřeba nahrazovat staré papírové kartotéky elektronickými systémy využívajícími sílu moderních výkonných počítačů.

Fakt, že se nejedná o elementární problém, dokazuje množství různých stylů písma. V úvahu musíme brát různý sklon písma (např. leváci a praváci mají naprosto opačný sklon písma), dále uvažujeme psací a tiskací písmo, různou velikost (nejen výšku, ale i šířku) jednotlivých znaků. Je zřejmé, že vyhodnocovací algoritmy jsou složité a výpočetně náročné, navíc by ideální algoritmus měl mít schopnost se neustále učit.

Ukázalo se, že velkým pomocníkem jsou neuronové sítě, nicméně potřeba superrychlého zpracování vede ke stále komplexnějším architekturám. I zde však platí pravidlo o správném účelu systému, jelikož jednodušší systémy se nedají, co do výkonu, srovnávat s těmi nejnovějšími a nejmohutnějšími, na druhou stranu jsou vhodné pro prostředí, kde rychlost nehraje roli. Rozpoznávání ručně psaných znaků se dělí do dvou hlavních odvětví. Prvním z nich je tzv. rozpoznávání ON-LINE, které se v současné době nejvíce používá v bankovním sektoru, při kontrolách podpisového vzoru. Druhým z nich je OFF-LINE způsob rozpoznávání, který našel uplatnění např. v poštovních službách, kde je třeba rozdělovat zásilky podle PSČ.

Získávání vstupních dat

Při rozpoznávání znaků uvažujeme dvě formy dat, a to na základě způsobu jejich získání. Data se obecně dělí na on-line a off-line data. On-line data se získávají přímo při psaní textu uživatelem, k tomu je určeno speciální pero a digitalizační tableta. Na druhé straně off-line data se získávají až po jejich napsání. Znamená to, že text je nejdříve napsán obyčejným perem na obyčejný papír a následně je digitalizován pomocí skeneru. Tento způsob vede k dvourozměrné matici, kde každý prvek je výsledkem intenzity odraženého světla.

On-line data

Tablet zachycuje v daném rozlišení pohyby špičky pera po povrchu. Data jsou snímána od okamžiku, kdy se pero dotkne povrchu, do chvíle, kdy povrch opustí. Znát pozici pera ve vzduchu může být užitečné ve chvíli, kdy pero slouží také jako myš a umožňuje uživateli pohybovat kurzorem, aniž by zanechával stopu.

Ukládáním dat do databáze můžeme získat až několikatisícový svazek tréninkových dat. Je dobré používat data od různých uživatelů (leváků, praváků atd.). Čím více různých stylů získáme, tím účinnější pak bude náš rozpoznávací mechanismus.

Takto získaná data mají však své slabiny. Lidé mají tendenci psát na tabletu písmena o několik centimetrů větší než při běžném psaní, velký vliv na kvalitu získaných dat má použitý materiál (tablet, plochý displej — projevuje se jiným stylem písma, bodový snímač a snímač zachycující celý tah).

Off-line data

Dnešní technologie již nabízejí mnoho druhů skenerů, které se dají použít na šeky, fotografie či diapozitivy. Skenery přiřazují každému pixelu jednu binární hodnotu (0,1 — černá, bílá), tedy černobílé provedení až po několik úrovní (odstínů) šedi či barevné hloubky. Výsledkem je obrázek, který uchováváme ve formě binárního kódu.

Zpracování dat

V současné době se rozpoznávání ručně psaných znaků potýká s řadou problémů, které snižují potenciální popularitu OCR (Optical Character Recognition), resp. HWCR. Tyto problémy se týkají zejména odstraňování pozadí, korekce sklonu a velikosti písma, ambiguace jednotlivých znaků či slov, digitálního "způsobu přemýšlení", který se liší od lidského. Některé z těchto problémů se podařilo do jisté míry odstranit tzv. preprocesními a postprocesními úpravami (preprocessing and postprocessing), které se vykonávají před nebo po samotném OCR. Je rozumné oddělovat fáze preprocesní a postprocesní od samotných algoritmů OCR, a to z důvodu, že většina známých algoritmů OCR umí pracovat jen s černými znaky na bílém pozadí.

Preprocesní zpracování dat

Typickým příkladem preprocesních algoritmů (provádějí se u OFF-LINE získaných dat) je odstraňování vzorů na pozadí, vypreparování textu, srovnání šikmo psaného textu, korekce velikosti a sklonu znaků. Text je vlastně často psán na vzorovaném pozadí (papíře), například při posílání dopisů lidé často používají pěkně graficky zpracované obálky, proto by dobrý systém měl umět rozeznat text od okrasné grafiky. Lidé toto samozřejmě zvládnou díky přirozené intuici, ale podíváme-li se na tento problém z hlediska počítače, je to nelehký oříšek. Není výjimkou, že se celý blok textu rozpozná jako grafika, a je tak vyloučen ze znakové rozpoznávací procedury. Jednou z možných metod je tzv. thresholding, jedná se o algoritmus na získání prahové úrovně šedi, kdy každému pixelu na pozadí se přiřadí "0" a pixelu na popředí hodnota "1". Takto připravená data mohou přistoupit k dalšímu kroku v preprocesní fázi, kterým je segmentace a následně skeletonizace (provádí se i u ON-LINE dat).

Algoritmus segmentace hledá na obrázku sloupcovité skrumáže bílých pixelů (upozorňuji, že jsme dříve provedli thresholding, takže máme "černobílý" obrázek), které znamenají oddělení jednotlivých znaků. Pokud uvažujeme PSČ, pak jsou evidentně úspěšné ty případy, u kterých segmentace odhalila pět shluků (tzv. blobs — nepopsatelné objekty shluku informací), a tedy pětimístné číslo.

Vypreparování textu (znaků), tzv. skeletonizace, je akcí velice důležitou, jelikož takto získaná informace o tvaru znaků je základní vstupní informací pro algoritmus OCR. Skeletonizace může pomoci odstranit nepravidelnosti ve znacích, a tím zjednodušit celý rozpoznávací algoritmus, který pak uvažuje jen znakové úhozy, jež jsou pouhý pixel široké. Rapidně se taktéž sníží paměťové nároky na uchovávané informace o vstupních znacích. Toto je jedna z hojně užívaných metod protože mimo jiné, zkracuje čas samotného rozpoznávání. Kostry (skeletony) se získávají tzv. ztenčovacími metodami nebo transformacemi vzdáleností.

Zjednodušení algoritmu OCR můžeme dosáhnout také tím, že algoritmus bude považovat všechna vstupní data za normalizovaná na standardní rozložení (míněno, že text není "do kopce" ani "z kopce"), velikost a sklon. Existuje řada úspěšných algoritmů, které umožňují vytvořit horizontální rozložení, otáčet znaky a vytvářet konzistentní velikost. Algoritmy OCR pak mohou dostávat normalizované tvary znaků. Jiným příkladem normalizace je případ, kdy může být znak psán více způsoby. Například písmeno "a" jsme schopni napsat alespoň dvěma způsoby. Dobrý algoritmus by si měl být schopen poradit i s takovými nesváry.

OCR algoritmy

Nejběžněji používané techniky OCR jsou založeny na Markovových modelech, neuronových sítích, srovnávacích metodách tvarů a vzorů (stromové struktury vzorů jsou úspěšné při rozpoznávání netradičních fontů), polygonálních odhadech (vstupní data jsou převedena na polygonální reprezentaci), filtrech na extrakci tahů a bodů (on-line rozpoznávání). Markovovy modely zaznamenaly velký úspěch v rozpoznávání řeči, jsou to vlastně stavové stroje, které využívají kontextové informace. Počítače obecně nemají problémy s rozpoznáváním dobře napsaných znaků, které se moc neliší od daných vzorů, ale psané znaky jsou mnohdy víceznačné a nečitelné i pro člověka. Lidé jsou schopni číst slova s nečitelnými znaky, a tak by tomu mělo být i u počítačů. Algoritmy založené na principu rozpoznávání znaku po znaku by na takovém slově neuspěly, ukazuje se, že kontextová informace je nejen užitečná, ale často i nutná.

Postprocesní zpravování dat

Postprocesní zpracování je velice důležité, protože slouží k napravování chyb, kterých se případně dopustí algoritmus OCR. Nejtypičtějším případem postprocesního zpracování je kontrola pravopisu (spell checking), která automaticky opraví drobné chybičky a u větších chyb se zeptá uživatele na správný tvar. V mnoha případech se raději přímo přistupovalo k přepisování dokumentů než k použití OCR a následné manuální opravě, protože množství chyb, jichž se OCR systémy dopouštěly, bylo příliš velké. Cena vynaložená za opravu výstupu procesu OCR může úplně zmařit záměr, za jakým jsme OCR prováděli. Musíme si uvědomit, že postprocesní systémy by neměly znehodnotit původně správně rozpoznaná data.

Mnoho vědců upozorňuje na fakt, že chyb, které algoritmy OCR dělají, by se lidé nedopouštěli. Zaměnit "S" za "5" může i člověk, protože oba znaky jsou si svou strukturou podobné. Ale zaměnit "S" za "M", to by se asi člověku jen tak nepodařilo, avšak počítačový algoritmus takové chyby dělá. Je to dáno tím, že počítačové výpočty se liší od výpočtů lidského mozku. Lidé se většinou podívají na úhozy (tahy) daného znaku a na jejich vzájemné vztahy, zatímco algoritmus měří cokoliv od transformace kruhové projekce znaku, po Fourierovy transformace horizontálních a vertikálních projekcí. Někteří lidé tvrdí, že takové algoritmy jsou příliš složité a že je lepší využívat jednodušších intuitivních algoritmů. Jiní zase zdůrazňují, že chyby typické pro lidi mohou být lehčeji opraveny zase lidmi. Například je jednodušší opravit "5ave" na "Save", než by tomu bylo u "Mave". Pro správné rozpoznání je často potřeba znalost kontextu – rozlišit "0" a "O" bez kontextu nelze. Při rozpoznávání celých slov se jednoznačně neobejdeme bez kontextuální informace.

Praktické využití

Nejeno teorií živ je člověk, a proto se v následujících odstavcích můžete seznámit s praktickými možnostmi využití těchto teoretických poznatků.

V zásadě existují dva velcí uživatelé systémů na rozpoznávání ručně psaných znaků. Jedná se o sektory bankovních a poštovních služeb. Finanční instituce využívají těchto systémů zejména v souvislosti se šeky, jelikož šek obsahuje značné množství položek, které je třeba řádně ověřit, aby byla zajištěna bezpečnost bankovních operací. Systém by například mohl kontrolovat, zdali souhlasí částka uvedená číslicemi a částka uvedená slovy, dále by mohl kontrolovat, jestli jméno plátce souhlasí s účtem, ze kterého má být částka odečtena, avšak první věcí, která by nás v souvislosti s šeky napadla, by bylo ověřování podpisu. Když vezmeme v úvahu množství šeků, které projde každý den bankovním systémem, a i kdyby takový systém rozpoznával pouze polovinu z nich, znamenal by značnou úsporu mravenčí práce. Francouzská pošta zavedla počátkem devadesátých let podobný systém, který měl mít 0,01% chybovost a umožňoval, aby až 50% šeků prošlo bez nutnosti předání k ručnímu zpracování.

Již mnoho poštovních úřadů zavedlo systémy OCR (Optical Character Recognition), které rozeznávají samostatné číslice, tím napomáhají k automatickému třídění zásilek na základě poštovních směrovacích čísel. Mnoho výzkumů potvrdilo obrovskou výhodu používání výlučně číslic v poštovních směrovacích číslech (USA, Česká republika atd.), jelikož číslice lze relativně nejsnadněji automatizovaně rozpoznávat. Systémy na poštách však mohou jít mnohem dál. Bylo by je možné používat k rozpoznávání celých adres a třídění obálek jen na jejich základě, tedy bez PSČ.

Vidíme, že poštovní systémy jsou asi nejlepší ukázkou aplikace systémů na rozpoznávání ručně psaných znaků, a to i z toho důvodu, že nabízejí širokou škálu obtížnosti. Nejjednodušším případem je rozpoznávání číslicových PSČ v předtištěných rámečcích, na druhém konci pak stojí rozpoznávání adres bez PSČ. S poštovními systémy se dá velice dobře experimentovat, jelikož dochází v současné době k značným ztrátám poštovních zásilek (lépe řečeno k jejich směrování na špatné místo), a proto je možné tolerovat počáteční chyby počítačového systému.

Jinou oblastí, kde se využívá ručně psaného vstupu dat, je vyplňování formulářů, psaní si poznámek, korektura dokumentů a udržování záznamů. Celkem pěknou aplikací by se mohl stát systém, jež by přijímal data z digitálního pera, např. při přejímaní dodávek zboží, kde by se pak data přenášela do centrálního počítače. To by ale vyžadovalo, aby se ve větší míře rozšířily elektronické podpisy. Když bychom se přenesly ze skladu do kanceláří, pak by nás určitě potěšil systém, ježn by automaticky četl faxové zprávy. S tím souvisí i podpora pro nevidomé, která jednoznačně ukazuje, že rozpoznávání ručně psaných znaků se nevyužívá výhradně pro komerční nebo humanitární aplikace, ale obě úrovně se navzájem překrývají.

autor Jan Vlček