CZ6196A3 - Method of segmentation of draws for hand-writing input - Google Patents

Description

Způsob segmentace tahů pro rukopisný vstup

Oblast techniky

LO σ>

rc

Tento vynález se všeobecné týká tóze zná ván-í í— ťukijpi pisu a zejména způsobu segmentace tahů pro rukopisný

7SÍIÍÍ

Dosavadní stav techniky

Stroj ové záležitost a prostředků s úkolem, kterému je různých přístupů k rozdělení rukopisu tahů'

UZltl rozpoznávání lidského rukopisu je velmi složitá se současným prudkým rozšiřováním výpočetních možností vstupu pomocí pera se stalo důležitým třeba se věnovat. Existuje velké množství jeho řešení. Jedním užitečným přístupem je do posloupnosti základních pohybů neboli těchto tahů, které jsou určitým způsobem parametrizovány, jako vstupů znakového rozpoznávače.

Klíčovou podmínkou u rozpoznávače na základě tahů je, že mnohé případy stejné znakové třídy (např. písmeno A napsané v různých časech různými pisateli) by měly být pokaždé rozděleny do podobného souboru .tahů. Toto pomáhá zabezpečit, že rozpoznávání není příliš složité, neboť popis znakových případů se bude jevit znakovému rozpoznávači podobně. Ideálně by všechny případy daného znaku vždy obsahovaly stejný počet tahů, všechny tahy by byly ve stejné relativní poloze a popisy vlastností tahů by byly velmi podobně ve všech případech. Tento ideál není v praxi dosažitelný, ale přesnost rozpoznávání může být zlepšena do té míry, do jaké se mu lze přiblížit.

_______V_j ednom______z—dosud—už-í-vaných—způsobů—jsou—hranice—Jtatiů umístěny v bodech, kde rychlost pera ve vertikálním (nebo y) směru je nulová, tzn. v bodech, kde se písmo začíná pohybovat nahoru či dolů. Vznikající soubory tahů mohou být tedy nazvány tahy nahoru” a tahy dolů. Tento způsob je diskutován v práci Mermelstein & Eden, Experiments on Computer Recognition of Connected Handwritten Vords, v Information and Control, sv.7, Sír.255-270, 1964. Jednou z nevýhod tohoto způsobu je skutečnost, že je příliš citlivý na změny ve vertikálním směru a necitlivý na změny v horizontálním směru. Mnoho znaků je ale složeno z horizontálních částí - např. vodorovná čárka t a tři nožičky E jsou obvykle mnohem vice horizontální než vertikální, dokonce i u nedbalého rukopisu. Segmentovač tahů založený na rychlosti ve směru y rozdělí někdy horizontální část do jednoho tahu, ale často ji rozdělí do dvou, tři či více tahů, jednoduše kvůli drobnému chvění pera ve vertikálním směru. Toto vede k nízké rozpoznávací přesnosti, neboř mnohé případy stejného znaku budou často segmentovány do rozdílně ' vypadajících souborů tahů. Pokusy opravit nepřesnosti tohoto způsobu, zahrnující požadavek minimální změny ve vertikálním směru před vytvořením nového tahu, měly jen omezenou úspěšnost a mnoho stejných základních problémů stále zůstává.

Jiný současný způsob řeší tento problém umístěním hranic tahů do bodů, kde zakřivení je ve svém lokálním ₍ maximu a přesahuje určitou prahovou hodnotu, jež odpovídá ostrým ohybům v rukopise. Jelikož se ostrý ohyb může vyskytnout bez ohledu na směr, kterým se pero pohybuje, není tato metoda citlivá na orientaci různých částí rukopisného vstupu, jako jsou slova nebo znaky. Technika založená na zakřivení má ale též své nedostatky. Předpokládejme např., že někdo píše L · s velmi povlovným zakřivením, spíše než se zakřivením ostrým, takže začne vypadat více jako C”. V tomto případě může způsob selhat při segmentaci L, pokud nebylo dosaženo prahového zakřivení požadovaného pro hranice tahů. Pouhé snížení prahové hodnoty problém neřeší, neboř to by vedlo jen k nepřiměřenému počtu tahů. Příliš velký počet jednotlivých tahů je stejně 'nežádoucí, jako jejich 'příliš malý' počet, neboř to opět znamená, že mnohé případy stejného znaku jsou často segmentovány do různých typů tahů.

Je tedy potřebný způsob segmentace, který je přesnější a nemá nedostatky uvedených způsobů, jako je způsob rychlosti ve směru ý a existující způsob zakřivení.

Podstata vynálezu

V souladu s předloženým vynálezem je realizován způsob segmentace rukopisného vstupu do tahů, jejichž počet je

V konzistentní pro mnoho případů každé jednotlivé znakové třídy.

předložený vynález poskytuje způsob segmentace rukopisného vstupu do tahů, jež jsou si podobné tvarem a umístěním pro mnoho případů každé jednotlivé znakové třídy na vstupu.

Způsob podle předloženého vynálezu obecně zahrnuje krok výpočtu derivace neboli okamžité hodnoty změny zakřivení v bodech rukopisného vstupu. Tento způsob potom vybírá jako body hranice tahu určité body (neboli obrazové prvky) ve vstupu, které leží mezi bodem vysoké derivace zakřivení a následným bodem nízké derivace zakřivení . Takové hraniční body nejsou ovlivněny absolutními hodnotami zakřiveni, ale spíše jen relativními změnami v zakřivení.

_______Přehled obrázků na výkresech _

Obr.l zobrazuje vývojový diagram postupu identifikování hranic tahů v souladu s výhodným provedením předloženého vynálezu.

Obr. 2	zobrazuje segmentaci	rukopisného	vstupu	do	tahů
vytvořenou	předcházejícim způsobem	rychlosti ve	směru y
Obr.3 vytvořenou	zobrazuje segmentaci předcházejícím způsobem	rukopisného zakřivení.	vstupu	do	tahů
Obr. 4	zobrazuje segmentací	rukopisného	vstupu	do	tahů

vytvořenou výhodným provedením předloženého vynálezu.

Obr.5 zobrazuje body vytvářející písmeno L tak, jak jsou přijaty z digitizéru .

Obr.6 zobrazuje body vytvářející písmeno L po převzorkování na konstantní vzdálenosti v souladu s výhodným provedením předloženého vynálezu.

Na obr.7 je rozložený pohled zobrazující výpočet zakřivení ve výhodném provedení předloženého vynálezu.

Obr.8 graficky zobrazuje hodnoty zakřivení vypočítané pro každý bod v obr.7.

Obr.9 graficky zobrazuje derivace hodnot vypočítané pro každý bod z obr.7.

zakřivení

Příklady provedení vynálezu

Rukopisný znakový vstup je obvykle získáván od~užTvatele ve formě oddělených spojitých segmentů. Oddělený spojitý segment se skládá z jednoho či více tahů pera, kde tah pera je stopa, kterou pero zanechává' během'doby svého kontaktu - se vstupním zařízením-, jako je digitalizační tablet nebo papír.

V předloženém vynálezu jsou rcgpoznáv&né jednotky rukopisného vstupu tvořeny jedním či více odělenými spojitými segmenty. Rukopisný vstup je vstup, který je snímán elektronicky, což zahrnuje, ale není omezeno na následující: rukopisný vstup; elektronický vstup; vstup snímaný tlakem, jako je tiskový vstup; vstup přijímaný elektronicky, jako například faxem, přijímačem rádiového vyhledávacího systému, nebo jiným zařízením.

Tah je vyjádřen jako posloupnost bodů vzorkovaných v přibližně pravidelných intervalech vstupním zařízením. Každý bod je určen minimálně souřadnicemi x a y. Tahy mohou být snímány elektronicky za použití digitalizačního tabletu nebo jinak mohou feř ' být odvozeny od skenovaného nebo faxovaného obrazu procesem t řádkové detekce v obrazu; takové metody elektronického snímání jsou v oboru známy. Ve výhodném způsobu je rukopisný vstup přijímán zařízením jako je osobní číslicový pomocník (PDA) nebo jiné zařízení. Další prostředky, které slouží k příjmu rukopisného vstupu, zahrnují, ale nejsou omezeny na následující: počítače, modemy, přijímače rádiového vyhledávacího systému, telefony, číslicové televize, interakční televize, zařízení mající digitalizační tablet, telefaxová zařízení, skanovaci * zařízení a další zařízení schopná snímat rukopisný vstup. Obecně, když jsou tahy snímány elektronicky, je každý bod vyjádřen i- obrazovým prvkem tak, že tah je vyjádřen jako řada obrazových prvků na zařízení.

V souladu s předloženým vynálezem může být rukopisný vstup ve formě alfanumerických znaků, ideografických znaků, nebo j iných forem znaků či symbolů psané komunikace^-.’

Obr .2 a obr. 3 rukopisného vstupu v interpretaci vstupu, rozpoznávače na základě stejného alfanumerického ystupu jako v zobrazují segmentaci tahů alfanumerického s vysokou pravděpodobností nepřesností když segmentace tahů přijde do tahů. Obr.4 zobrazuje segmentaci tahů segmentace tahů prováděna v souladu spředloženým vynálezem a taková segmentace tahů má vysokou pravděpodobnost přesné interpretace při příchodu do rozpoznávače na základě tahů.

Obr.l zobrazuje vývojový diagram výhodného způsobu v souladu s předloženým vynálezem. Rukopisný vstup z digitizéru či jiného zařízení je přijímán ve formě souřadnic x a y 110 (s přidruženými stavy zdviženého nebo spuštěného pera). Typicky jsou tyto body prezentovány obrazovými prvky. Předložená metoda obecně převzorkovává rukopisný vstup za účelem získání bodů, jež jsou rovnoměrně rozmístěny v celé délce rukopisného vstupu 120. Obr. 5 zobrazuje příklad písmena L 500 jako řady bodů nebo obrazových prvků před převzorkováním. Obr.6 zobrazuje totéž písmeno ”L 600 jako řadu bodů nebo obrazových prvků po převzorkování. Převzorkování se děje užitím mezibodové vzdálenosti d 610. která je konstantní v celém rukopisném vstupu. Nejlépe je hodnota d vybrána tak, že střední hodnota vstupní výšky rukopisného vstupu je přibližně v rozmezí 15krát až 30krát d. Například v obr.6 je hodnota d vybrána tak, že střední’ hodnoty výšky písmena ve slově je přibližně v rozmezí 15krát až 30krát d.

Výhodné provedení v obr.l vypočítává zakřivení v každém převzorkovaném bodě 130. Obr.7 ilustruje graficky popis dat pro výpočet zakřivení v bodě R 710. Zakřivení v převzorkovaném bodě

Ί

R 710 je definováno jako vzdálenost k bodu následujícímu po R (bod R+l 730) od bodu P 720. získanému lineární projekcí od bodu préčicházej rčímu— R (R-T; 750)' pres vlast n' í R ; Tato-------vzdálenost je znázorněna na obr.7 jako prvek 740 . Zakřivení v koncových bodech rukopisného vstupu je definováno jako stejné

-v odpovídaj ících- nej bližších- sousedních . bodech--------Zakřivení . ve vnitřních bodech rukopisného vstupu může být též vypočteno projekcí dvou bodů vzdálených od R, spíše než jednoho bodu •fa, použitím bodu, který je dva body ořed R, spíše než bodu F.-l) . aby byl získán odhad odolnější chybám. Obr.8 zobrazuje graficky hodnoty zakřivení získané probody znázorněné na obrT7:

Například výše zmíněný přiklad písmene L s povlovným zahnutím může být segmentován do vertikálního a horizontálního tahu pokud dvě rovné” části L jsou podstatně rovnější než ohyb mezi nimi. Zakřivení by se tedy zvyšovalo směrem k ohybu (tj . derivace zakřivení by byla vysoká) a snižovalo směrem od ohybu (derivace zakřivení by byla nízká), což dovoluje mít hranici tahu v ohybu, nebo blízko něj, jak je požadováno.

Bylo-li ve výhodném provedení předloženého vynálezu již jednou získáno zakřivení pro každý převzorkovaný bod, skupina zakřivení pro převzorkované body může být vyhlazena, aby byly minimalizovány jakékoli známé artefakty zavedené digitalizačním procesem. Typ vyhlazení, které má být provedeno by měl být standardní způsob, který je vybrán na základě konkrétních digitalizačních znaků. Toto může zahrnovat bodu s jeho sousedními body (vážení bodu vyšších bodů) a náhrada hodnoty zakřivení ve zmíněném bodě vypočítaným průměrem. Ideálně by velikost zde použitého vyhlazovacího okna měla být širší v oblastech nízkého zakřivení písma a užší v oblastech velkého zakřivení, aby byly minimalizovány ztráty důležitých informací při vyhlazovacím zprůměrování hodnoty samého a nej bližších procesu. Jelikož je předmětem vyhlazováni zakřivení samo, jeden výhodný způsob vyhlazování je_výpočet počátečních zaTcřivenl,kde vyhlazení je založeno na těchto zakřiveních, a potom znovuvyhlazení založené na nově vypočítaných zakřiveních.

Ve výhodném provedení předloženého vynálezu je pro každý převzorkovaný bod vypočítána absolutní hodnota zakřivení vynásobením každé záporné hodnoty zakřivení hodnotou -1. Absolutní hodnoty 'zakřiveni jsou pro výpočet derivací'zakřivení používány spíše než skutečné hodnoty zakřivení, protože celkově výhodná provedení předloženého vynálezu se zabývají pouze ostrosti ohybů v písmu, a ne kterým směrem se daný ohyb zakřivuje.

Jak je zobrazeno v obr.l, proces dále pokračuje výpočtem derivace zakřivení v každém převzorkovaném bodě 140. Podle obr. 7 je derivace zakřiveni v bodě R definována jako absolutní hodnota zakřivení v bodě R+l mínus absolutní hodnota zakřivení v bodě R-l děleno dvěma (tj.sklon křivky zakreslených hodnot zakřivení). Obr.9 graficky zobrazuje derivaci zakřivení získanou v každém bodě uvedeném v obr.7. Podobně jako při použití více než dvou bodů ke získání přesnější hodnoty zakřivení, jak je popsáno výše, derivace zakřivení by mohla být vypočtena pomocí širšího okna (pět bodů oproti třem) kde existují relevantní body, a užšího okna (dva body oproti třem), tam kde je to nutné. Jelikož derivace zakřivení nemůže být vypočítána v koncových bodech napsaného segmentu, derivace zakřivení v koncových bodech je jednoduše definována jako stejná v odpovídajících sousedních bodech.

Podle obr.l a 9 výhodné provedení způsobu dále zkoumá nově vypočítané pole hodnot derivací zakřivení za účelem určení bodů, kde je derivace ve svém lokálním ipaximu 910 (definovaném tak, že zahrnuje body na konci obratu křivky a začínající klesat) nebo kde je derivace ve svém lokálním minimu 920 (definovaném tak, že zahrnuje body na konci obratu~Tčr~ívRy «“začínající stoupat) . Pro každou oblast vstupu (v čase) po lokálním maximu a před lokálním minimem je určen středový bod sekce (vyjádřený v délce oblouku sekce) '930'. Tento ~středový bod je definován - - jako- M - 9-30 .- -Pokud rozdíl mezi hodnotami lokálního maxima a lokálního minima sekce překročí prahovou hodnotu T 940 a absolutní hodnota zakřivení bcdě M jřekročí určito» prahovou hodnotu T

Í820’;

vybrán jako hranice tahu 150.

Parametry T a T musí být odhadnuty a závisejí na jednotkách, ve kterých jsou měřena zakřiveni a derivace zakřivení. Přesné hodnoty zde nejsou kritické, pokud je používán znakový rozpoznávač tolerující chyby. Při provádění jakéhokoli experimentálního vyladění těchto nebo jakýchkoli jiných parametrů pro /vytvoření specifického provedení vynálezu je požadovaným cílem' dosažení co nejstejnorodější segmentace pro mnoho případů jednotlivých znakových tříd. Toto by mělo být provedeno empiricky, zkoumáním jak procedura segmentuje různé skutečné vzorky písma, jež má být rozpoznáváno.

JKromě již popsaných zvolených hraničních bodů tahů, jsou jako hraniční body tahů zvoleny body, kde se pero zvedá či spouští. Ve výhodném provedení předloženého vynálezu mohou být hraniční body založeny na derivaci zakřivení posunuty až. o dva bodů, kde absolutní hodnoty Posunutím hraničních bodů může být zlepšeno určení body, což zakřivení založených hraničních způsobí, že padnou do jsou maximální 160. na derivaci zakřivení bodů tahů tím, že jak míra zakřivení tak derivace zakřivení poskytnou stejné hranice tahu. Tato výhodná aplikace předloženého vynálezu je ale prováděna pro daný bod pouze tehdy, pokud nebudě vytvořen žádný tah složený z méně než tří bodů.

______Soubor hraničních bodů tahu de f i nu ie „v_ soulad u_-s-_před loženým vynálezem soubor odpovídajících tahů. Tyto tahy mohou být pak postoupeny znakovému rozpoznávací na základě tahů za účelem rozpoznávání rukopisného vstupu.

Předložený vynález a jeho výhodná provedení se týkají nových, přesnějších metod segmentace tahů. V souladu 5 předloženým vynálezem· je v mnoha případech rukopisného vstupu vstup pokaždé opakovaně rozdělen do podobných souborů tahů. Například, pokud je rukopisným vstupem písmeno L, napsané v různých časech různými pisateli, předložený vynález a jeho výhodná provedení by pokaždé přesněji rozděl-ily vstup písmene L do podobných hraničních bodů segmentace tahů bez ohledu na rozdíly různých pisatelů. Taková segmentace tahů by pomohla v zajištění přesnější interpretace rozpoznávačem na základě tahů.

Odborníci v daném oboru zjistí, že je možné použít mnoho provedení současného vynálezu. Jedno zřejmé rozšíření je z případu zde popsaného tisknutého rukopisu na případ spojovaného písma. Předkládaný způsob segmentace tahů je nezávislý na způsobu oddělování znaků, a tudíž techniky spojovaného písma mohou snadno využít segmentace tahů. Jiným provedením by skanovaného nebo nespřaženého písma aplikace předloženého vynálezu na takový problém ztenčení, písma, aby bylo dosaženo konstantní křivky. Hranice tahů by potom mohly být stanoveny dovoluj ící zpracování zde popsaného způsobu mohla být segmentace do tahů. Přímý způsob by spočíval ve šířky napsané jak v bodech založených na derivaci zakřivení, tak v průsečíkových bodech, jelikož chybějící časová informace způsobuje, že průsečíky a dotýkající se ohyby vypadají podobně.

Claims (7)

1. — 1. Způsob rozpoznávání—rukopisného znakufsložea^fe»^ množíny.

   zbarvených obrazových bodů, zahrnující kroky:

   výpočet hodnoty derivace zakřivení pro každý z množiny zbarvených obrazových bodů, kde každá hodnota derivace zakřiveni představuje rychlost změny absolutního zakřivení v odpovídajícím obrazovém bodě,

   - výběr souboru hranic tahů tak, že každá hranice tahu leží mezi zbarveným obrazovým bodem s vysokou hodnotou derivace zakřivení a následným zbarveným obrazovým bodem s nízkou hodnotou derivace zakřivení,

   - určení souboru tahů tak, že každá hranice tahů je umístěna na konci tahu,

   -í,výpočet alespoň jedné hodnoty vlastnosti tahu pro každý tah, za účelem vytvoření sady vlastností znaku,

   - použití sady vlastností znaku k určení identity zmíněného rukopisného znaku.
2. 2. Způsob podle nároku 1, kde zbarvený obrazový bod s vysokou hodnotou derivace zakřivení má lokálně maximální hodnotu derivace zakřivení a následný zbarvený obrazový bod s nízkou hodnotou derivace zakřiveni má lokálně minimální hodnotu derivace zakřivení.
3. 3. Způsob podle nároku 2, kde každá hranice tahu leží v bodě ___poloviční vzdálenosti mezi zbarveným obrazovým bodem s lokálně muximální hodnotou derivace zakřivení a zbarveným obrazovým bodem s lokálně minimální hodnotou derivace zakřivení.
4. 4. Způsob podle nároku 1, kde každá hranice tahu leží v bodě lokálně maximální absolutní hodnoty zakřivení.
5. 5. Způsob rozpoznávání rukopisného znaku složeného z posloupnosti bodů, kde každý bod sestává ž ‘hodnot^- tří prostorových souřadnic, zahrnující kroky:

   výpočet hodnoty derivace zakřivení . pro každý z množiny bodů, kde každá hodnota derivace zakřivení představuje rychlost změny absolutního zakřivení v odpovídajícím bodě,

   - výběr souboru hranic tahů tak, že každá hranice tahu leží mezi bodem s vysokou hodnotou derivace zakřivení a následným bodem s nízkou hodnotou derivace zakřivení,

   - určení souboru tahů tak, že každá hranice tahů je umístěna na konci tahu,

   - výpočet alespoň jedné hodnoty vlastnosti tahu pro každý tah, za účelem vytvoření sady vlastností znaku,

   - použití sady vlastností znaku k určení identity zmíněného rukopisného znaku.
6. 6. Způsob podle nároku 5, kde bod s vysokou hodnotou derivace zakřivení má lokálně maximální hodnotu derivace zakřivení a následný bod s nízkou hodnotou derivace zakřivení má lokálně minimální hodnotu derivace zakřivení.

   - 13 7. Způsob podle nároku 6, kde každá hranice tahu leží v bodě poloviční—vzdálenosťirnnezi bodem s lokálně~iSaxÍmální hodnotou derivace zakřivení a bodem s lokálně minimální hodnotou derivace zakřivení.

   8. Způsob podle nároku 5, kde každá hranice tahu leží v bodě lokálně maximální absolutní hodnoty zakřivení.

   O 03 · í/3

   UD ' <T>

   D0 31CI <>. $

   OSR. . /

   . / \ • --Λ'.

   o -χο

   X \ \

   • \s

   Λ \

   'v ose. . 4

   400 ·

   3/3

   6/0 o

   co

   LO

   C>

   00 ,10 v

   e 'ť

   O3Z

   500

   ... 9 •

   • ~

   OSR . 6 ·· · »* *· ·

   i.
7. 7 7-77

   Popis k obrázku č.l

   110 - příjem vstupu jako posloupnosti (x, y) bodů

   120 - převzorkování tak, že body jsou rozmístěny ve stejných vzdálenostech ,

   130 - výpočet velikosti zakřivení v každém bodě

   X · W » X i -4Q yý^oočet 'derív^c'“ ts-k? / každém bodě Λ

   .. / ..... --y - '7 _................................

   150 - identifikace Hranic tahů jako’ bodů v prostředku mezí v lokálním maximem a minimem derivace zakřiveni

   160 - dostavení hranic táhů za účelem korekce malých chyb měření

   170 - předání detekovaných hranic tahů .pro další použití v rozpoznávacím procesu