SE519014C2 - Metod och anordning för igenkänning av ett handskrivet mönster - Google Patents

Description

25 30 35 519 014 gif; canvas o 2 Detta skulle kunna användas för igenkänning av ett ”P” jämfört med ett ”p”.

Det finns idag nägra sätt att använda den informa- tion som ges av tecken som sträcker sig nedanför eller ovanför andra tecken för bättre igenkänning av hand- skriven text. Dessa metoder försöker definiera en bas- linje och en kärnregion för bestämning av var tecknen bör vara positionerade. Baslinjen är den linje pà vilken texten stàr, men tecken som g och p sträcker sig nedanför den. Kärnregionen är den region över baslinjen, som alla* tecken korsar. Tecken som ”a” och "m" är helt inuti kärn- regionen, medan ”l” och ”b” sträcker sig ovanför kärn- regionen. Det kan emellertid vara svàrt att hitta en bas- linje för texten och det är svàrt att definiera kärn- regionen, speciellt om tecknen är lutade. Vidare är denna metod specialiserad för latinska tecken och skulle inte kunna användas för t ex kinesiska tecken.

En annan metod är att ha referensmönster för kombi- nationer av tvà eller flera tecken och känna igen varje mönster som en helhet. Detta innebär emellertid att ett mycket stort antal referensmönster behövs och således blir igenkänningen långsam.

Sammanfattning av uppfinningen Ändamålet med uppfinningen är att tillhandahålla en förbättrad metod för igenkänning av handskrivna mönster.

Ett särskilt ändamål med uppfinningen är att metoden skall kunna särskilja mellan tecken som endast skiljer sig i storlek eller position. Ändamàlen med uppfinningen àstadkommes av en metod för igenkänning av ett handskrivet mönster, vilken metod innefattar stegen att bilda en representation av det handskrivna mönstret, bilda åtminstone tvà underkonfi- gurationer genom uppdelning av representationen av det handskrivna mönstret och behandla underkonfigurationerna.

Steget att behandla innefattar stegen att jämföra varje underkonfiguration med referenskonfigurationer, välja 10 15 20 25 30 35 519 014 "I= 3 åtminstone en underkonfigurationskandidat för varje underkonfiguration bland referenskonfigurationerna, varvid steget att välja baseras på steget att jämföra, och bestämma åtminstone ett kandidatmönster, som består av en vald underkonfigurationskandidat för varje under- konfiguration. Metoden innefattar vidare stegen att jäm- föra representationen av det handskrivna mönstret med kandidatmönstret och beräkna en kostnadsfunktion så att ett bäst överensstämmande kandidatmönster hittas. Kost- nadsfunktionen baseras på jämförelsen av representationen av det handskrivna mönstret med kandidatmönstret och på jämförelsen av underkonfigurationerna med de valda underkonfigurationskandidaterna i kandidatmönstret.

Den uppfinningsenliga metoden känner igen ett hand- skrivet mönster genom igenkänning av underkonfiguration- erna som bildar mönstret och igenkänning av hur dessa är kombinerade. Jämförelsen av representationen av det hand- skrivna mönstret med kandidatmönstret viktas in i kost- nadsfunktionen och skulle således kunna addera informa- tion om de inbördes förhållandena mellan underkonfigura- tionerna till kostnadsfunktionen. Som ett resultat kan de inbördes förhållandena mellan underkonfigurationerna beaktas utan behovet att hitta en baslinje och en kärn- region hos mönstret.

Vidare kan de valda underkonfigurationskandidaterna användas för bildande av vanliga kandidatmönster. Kandi- datmönstren kan då bildas från referenskonfigurationerna under behandlingen av underkonfigurationerna och på detta sätt finns det inget behov för en omfattande databas med kandidatmönster.

I denna ansökans sammanhang definieras termen mönster som ett ord, ett enda tecken eller en del av ett tecken. Om ett tecken är komplicerat skulle det kunna igenkännas genom igenkänning av de delar som bildar tecknet såväl som själva tecknet. Detta resonemang gäller också för ett mönster som är en del av ett tecken. I de senare två fallen skulle det vara fördelaktigt om 10 15 20 25 30 35 519 014 4 mönstret är lagrat i databasen. Termen kostnadsfunktion definieras som en funktion som under beräkningsprocessen bestämmer hur bra en lösning är.

Bildandet av underkonfigurationer kommer inte nöd- vändigtvis att använda alla delar av det handskrivna mönstret. Exempelvis består det handskrivna mönstret, för flytande handskrift, av tecken och ligaturer mellan tecknen. Bildandet av underkonfigurationer skulle då kunna sträva efter att hitta tecknen och beteckna dessa som underkonfigurationer, varefter ligaturerna kan bort- ses fràn. Alternativt används också informationen i liga- turerna, varvid dessa ligaturer då kommer att bilda ytterligare underkonfigurationer.

Jämförelsen av det handskrivna mönstret med kandi- datmönstret skulle kunna utföras genom jämförelse av mönster med varandra som en helhet. Mönstren skulle emellertid också kunna jämföras genom jämförelse av upp- sättningar av tvà eller flera underkonfigurationer av det handskrivna mönstret med uppsättningar av motsvarande underkonfigurationskandidater i kandidatmönstret och upp- repning av dessa jämförelser för olika uppsättningar tills alla underkonfigurationer har inkluderats i åtmin- stone en uppsättning av underkonfigurationer.

I en föredragen utföringsform innefattar steget att bestämma ett kandidatmönster steget att slà ihop en vald underkonfigurationskandidat för varje underkonfiguration till ett kandidatmönster, varvid ihopslagningen görs i enlighet med en fördefinierad regel.

Som ett resultat utförs bestämningen av kandidatmön- stret enkelt. Ihopslagningen av underkonfigurationskandi- dater till ett kandidatmönster är snabb, eftersom en fördefinierad regel styr hur ihopslagningen skall göras.

Steget att jämföra representationen av det hand- skrivna mönstret med kandidatmönstret innefattar före- trädesvis steget att mäta en skillnad hos positioneringen av underkonfigurationerna relativt varandra i det hand- skrivna mönstret jämfört med positioneringen av de valda 10 15 20 25 30 35 5-19 014 5 underkonfigurationskandidaterna relativt varandra i kandidatmönstret. Det bestämda kandidatmönstret bildar en mall för hur vissa underkonfigurationer bör vara positio- nerade relativt varandra. Mätningen av skillnaden hos positioneringen av underkonfigurationerna i det hand- skrivna mönstret mot positioneringen av underkonfigura- tionskandidaterna i kandidatmönstret kommer således att ge ett mått pà hur bra det handskrivna mönstret följer mallen.

I en föredragen utföringsform innefattar steget att mäta skillnaden i positionering stegen att omvandla representationen av det handskrivna mönstret så att det liknar kandidatmönstret så mycket som möjligt och beräkna en geometrisk närhet mellan representationen av det hand- skrivna mönstret och den omvandlade representationen av det handskrivna mönstret.

Detta innebär att representationen av det hand- skrivna mönstret omvandlas och sedan jämförs med den ursprungliga representationen. Således kommer det inte att bli några problem om representationen av det hand- skrivna mönstret och kandidatmönstret har olika uppsätt- ningar representationer, såsom en representation som innefattar fler punkter än den andra.

I denna ansökans sammanhang definieras termen geo- metrisk närhet som ett mått på likheten hos formen för två mönster. Formerna är invarianta med avseende pà en grupp transformationer av formerna, d v s representa- tionen av formerna ändras inte av gruppen av transforma- tioner. Denna grupp transformationer skulle kunna vara likformighetstransformationer och därmed inkludera skalning, rotation och förflyttning av mönstret eller affina transformationer, vilka vidare inkluderar skjuv- ning av mönstret. Således ger den geometriska närheten samma resultat för likheten av de tvà mönstrenas former, oavsett om ett av mönstrena har transformerats av en transformation som hör till den aktuella transformations- gruppen. 10 15 20 25 30 35 519 014 anu.~n o - 6 I en annan utföringsform innefattar steget att mäta skillnaden i positionering stegen att omvandla kandidat- mönstret sä att det liknar representationen av det hand- skrivna mönstret sä mycket som möjligt och beräkna en geometrisk närhet mellan kandidatmönstret och det omvand- lade kandidatmönstret.

Pà detta sätt omvandlas istället kandidatmönstret sà att det liknar representationen av det handskrivna mönstret. Kandidatmönstret bildas av referenskonfigura- tionerna, vilka är representerade i en form som enkelt kan transformeras.

I ytterligare en annan utföringsform innefattar steget att mäta skillnaden i positionering beräkning av en geometrisk närhet mellan representationen av det handskrivna mönstret och kandidatmönstret. Detta innebär att mätningen av skillnaden utförs direkt mellan det handskrivna mönstret och kandidatmönstret och inget steg att transformera mäste utföras först.

Steget att bilda åtminstone två underkonfigurationer genom uppdelning av representationen av det handskrivna mönstret innefattar företrädesvis steget att bilda olika uppsättningar av underkonfigurationer genom uppdelning av representationen av det handskrivna mönstret på alterna- tiva sätt. Detta är speciellt användbart när man försöker känna igen flytande skrift. Underkonfigurationerna kan dà inte separeras otvetydigt. I mànga fall är flera olika uppdelningar av mönstret möjliga. Därför uppdelas det handskrivna mönstret pà alternativa sätt i olika uppsätt- ningar av underkonfigurationer sà att man skall vara säker på att den korrekta uppsättningen erhålls.

Steget att behandla underkonfigurationerna utförs företrädesvis för varje uppsättning underkonfigurationer.

Pà detta sätt förvärvas màtt för likheterna mellan varje uppsättning av underkonfigurationer och referenskonfigu- rationerna. Således bestäms den korrekta uppsättningen av underkonfigurationer under jämförelserna. 10 15 20 25 30 35 519 014 ansv-p u 1 oouuøo 7 Igenkänningen av det handskrivna mönstret är före- trädesvis oberoende av en grupp transformationer. Gruppen transformationer skulle kunna vara t ex likformighets- Således skulle det handskrivna mönstret kunna skrivas i vilken transformationer eller affina transformationer. som helst storlek, lutning, etc. Ändamàlen med uppfinningen skulle också kunna åstad- kommas genom en anordning för igenkänning av ett hand- skrivet mönster, vilken anordning innefattar organ för detektering av det handskrivna mönstret och bildande av en representation av det handskrivna mönstret och organ för bildande av åtminstone två underkonfigurationer genom uppdelning av representationen av det handskrivna mönstret. Anordningen innefattar vidare en databas, i vilken referenskonfigurationer är lagrade, organ för jämförelse av varje underkonfiguration med referenskon- figurationerna och organ för val av för varje underkon- figuration åtminstone en underkonfigurationskandidat från referenskonfigurationerna i databasen, vilket val baseras på jämförelsen. Anordningen innefattar vidare organ för bestämning av åtminstone ett kandidatmönster, som består av en vald underkonfigurationskandidat för varje under- konfiguration, organ för jämförelse av representationen av det handskrivna mönstret med kandidatmönstret och organ för beräkning av en kostnadsfunktion så att ett bäst överensstämmande kandidatmönster hittas. Kostnads- funktionen är baserad på jämförelsen av representationen av det handskrivna mönstret med kandidatmönstret och på jämförelsen av underkonfigurationerna med de valda under- konfigurationskandidaterna i kandidatmönstret.

Anordningen enligt uppfinningen innefattar organ för jämförelse av underkonfigurationer med referenskonfigura- tioner såväl som organ för jämförelse av representationen av det handskrivna mönstret med kandidatmönstret. Detta innebär att både information om utseendet för underkonfi- gurationer och information om inbördes förhållanden mellan underkonfigurationer kan användas, vilket ger en 10 15 20 25 30 35 519 014 8 god möjlighet att korrekt igenkänna handskrivna mönster.

Endast byggblocken för de handskrivna mönstren behöver lagras i databasen, eftersom organet för bestämmande av ett kandidatmönster skulle kunna skapa mönstren fràn blocken. Dessa block skulle dà kunna hämtas snabbt, eftersom databasen kan vara liten.

Kort beskrivning av ritningarna Föreliggande uppfinning kommer nu i exemplifierande syfte att beskrivas mer i detalj under hänvisning till bifogade ritningar.

Fig l är ett flödesschema över en metod för igen- känning av ett handskrivet mönster enligt uppfinningen.

Fig 2a är en vy av ett exempel pà ett handskrivet mönster.

Fig 2b är en vy av ett exempel pà en uppdelning av det handskrivna mönstret i fig 2a i brytpunkter, i vilka delarna av mönstret blivit horisontellt förflyttade så att brytpunkterna skall framhävas.

Fig 3 är en schematisk vy av en anordning för igen- känning av ett handskrivet mönster enligt uppfinningen.

Detaljerad beskrivning av en föredragen utföringsform av uppfinningen Med hänvisning till fig 1, 2a och 2b kommer nu en metod för igenkänning av ett handskrivet mönster l att beskrivas i detalj. Först matar en användare in ett hand- skrivet mönster 1 pà en tryckkänslig skärm. Det inmatade, handskrivna mönstret 1 detekteras, steg 2, och en digital representation av det handskrivna mönstret l bildas, steg 4. Denna representation innefattar positionerna för flera punkter på det handskrivna mönstret 1. Den skulle alter- nativt kunna innefatta vektorer eller kurvor, som besk- river riktningarna för bàgarna hos det handskrivna mönstret 1. 10 15 20 25 30 35 519 014 9 I en för tillfället föredragen utföringsform retur- nerar detekteringen en representation av det handskrivna mönstret 1 som en sekvens av punkter X=(p1.p2, är koordinaterna för punkten pi.

(Xilyi) Sekvensen av punkter .,pm), där pi=(xi,yi) för i=l,2,...,m. erhålls genom sekventiell detektering av positionen för en penna med vilken det handskrivna mönstret 1 skrivs.

Det är önskvärt att representationen av det handskrivna mönstret 1 är invariant med avseende på t ex likformig- hetstransformationer. En representation som förblir den- samma även om mönstret påverkas av en transformation som tillhör någon grupp sägs vara en invariant med avseende på denna grupp. Rotationer, skalningar och förflyttningar skapar likformighetstransformationer_ I en annan ut- föringsform är representationen invariant med avseende på affina transformationer, där skjuvning också är inklu- derat.

En affin form s(X) skapas från punktkonfigurationen X=(p1,p2,...,pm). avseende på affina transformationer. Den affina formen 'Išm) Den affina formen är en invariant med s(X) är uppsättningen av koefficienter §=(§1,§2,.. som framträder i affina nollmängdskombinationer: s(X) = Éškpk = Ov med Éšk = 0}- Den affina formen skulle också kunna representeras av en matris SX, vars kolumnrum är lika med s(X).

Sedan bildas åtminstone två underkonfigurationer genom uppdelning av representationen av det handskrivna mönstret, steg 6. Det finns varierande svårigheter att korrekt bilda underkonfigurationer. Om det handskrivna mönstret 1 är i flytande skrift är bildandet av underkon- figurationer mycket svårt och skulle kunna utföras på olika sätt, inte är kopplade är bildandet av underkonfigurationer men om tecknen i det handskrivna mönstret 1 ganska enkelt. Bildandet av underkonfigurationer innebär 10 15 20 25 30 35 519 014 10 att representationen av det handskrivna mönstret l upp- delas i sekventiella punktkonfigurationer X. Representa- tionen av det handskrivna mönstret 1 uppdelas således i vissa brytpunkter 7, där punkterna på olika sidor om brytpunkterna 7 anvisas till olika punktkonfigurationer.

Brytpunkterna 7 är relativt enkla att hitta när det hand- skrivna mönstret 1 inte är i flytande skrift. Då hänför sig en båge, d v s en linje som dragits utan att lyfta endast till ett tecken. Ett tecken skulle emellertid kunna innefatta en eller flera bågar, varför pennan, identifiering måste göras om två på varandra följande bågar hör till olika tecken eller till samma tecken. Om det handskrivna mönstret 1 är i flytande skrift måste brytpunkterna 7 hittas inom bågar. Detta är mycket svårare och skulle kunna åstadkommas på flera olika sätt.

I denna utföringsform hittas brytpunkterna 7 genom försök att känna igen ligaturer, d v s delar av bågen som binder samman två tecken. Denna metod använder antagandet att ligaturer sträcker sig från vänster till höger och också sträcker sig i positiv vertikal riktning. Detta är sant för nästan alla ligaturer. Efter ett ”o” eller ett ”v” sträcker sig emellertid ligaturer ofta rakt åt höger eller t o m något nedåt. Brytpunkterna 7 placeras runt varje del av bågen som sträcker sig åt höger och i posi- tiv vertikal riktning. En brytpunkt 7 skulle då kunna placeras inuti ett tecken, som innefattar en del som sträcker sig som en ligatur, och följaktligen måste upp- sättningar av underkonfigurationer som bildar det hand- skrivna mönstret l skapas på olika sätt. Den enklast erhållna uppsättningen skapas genom beaktande av varje bågdel, riktning, som sträcker sig åt höger och i positiv vertikal som en ligatur och således beaktande av varje del mellan ligaturerna som en underkonfiguration. Andra uppsättningar erhålls genom beaktande av några delar, som sträcker sig åt höger och i positiv vertikal riktning, som delar av ett tecken och genom att således slå ihop bågdelar till en underkonfiguration. Flera uppsättningar 10 15 20 25 30 35 519 014 ll skapas pà detta sätt och används sedan för igenkänningen av det handskrivna mönstret 1.

Den ovan beskrivna metoden för bildande av underkon- figurationer kräver att texten inmatas horisontellt för att ligaturerna skall detekteras korrekt. Om så inte är fallet måste emellertid en orientering för texten hittas och därefter kan det handskrivna mönstret 1 roteras eller skulle den definierade riktningen för ligaturerna kunna sättas i enlighet med textens orientering.

Därefter igenkänns underkonfigurationerna som har fastställts genom segmenteringen. Detta görs genom jäm- förelse av underkonfigurationerna med referenskonfigura- tioner som har lagrats i en databas, steg 8. Jämförelsen av underkonfigurationerna med en referenskonfiguration ger ett mätt pà hur stor likheten mellan konfiguration- erna är. Referenskonfigurationerna som har stora likheter med underkonfigurationerna behålls och identifieras som underkonfigurationskandidater, steg 10. En underkonfi- guration skulle således kunna igenkännas av flera refe- renskonfigurationer och den vidare behandlingen av under- konfigurationerna kommer då att ge svar pà vilken av dessa referenskonfigurationer som är den korrekta tolk- ningen av underkonfigurationen. De enskilda jämförelserna av underkonfigurationerna med referenskonfigurationerna använder närhetsmàttet som sammanfattas i WO OO/13131 av R. Närhetsmàttet definieras Sparr, G. och Berthilsson, SOITI flCX»Y)=*P(SwS2)=Iw'"Pg)%,W (1) där S1,S2 är de affina formmatriserna för de två punktkonfigurationerna X, vilken är en underkonfiguration av det handskrivna mönstret, och Y, vilken är en refe- renskonfiguration, och P&, Rà är projektionsmatriserna för det rum som uppspänns av kolumnerna för S1 respektive S2. S1 och S2 skulle kunnas ersättas i (1) av X=( X l ) respektive Y&( Y l ) med samma resultat, d v s lO 15 20 25 30 35 519 014 12 P(S1.IS2) =P(Xf I respektive Y. Detta närhetsmått returnerar ett litet eftersom S1 och S2 är ortogonala mot X värde om punktkonfigurationerna är mycket lika. Om när- hetsmåttet returnerar ett värde under ett tröskelvärde utpekas således referenskonfigurationen som en underkon- figurationskandidat för den aktuella underkonfiguration- en.

Sedan bestäms kandidatmönster på basis av de behållna referenskonfigurationerna, steg 12. Några kandidatmönster skulle kunna vara lagrade i databasen, men majoriteten av kandidatmönster skapas genom ihop- slagning av underkonfigurationskandidaterna. Exempel på kandidatmönster som skulle kunna vara lagrade i databasen är tecken som består av mer än en båge, såsom ett ”i”, ett ”j” eller ett "t". kunna lagras som kandidatmönster. Kandidatmönstren Mycket vanliga ord skulle också bestäms för alla uppsättningar av underkonfigurationer och för varje uppsättning skulle flera kandidatmönster kunna bestämmas. Detta förekommer när en underkonfigura- tion inte tolkas otvetydigt som en referenskonfiguration.

Alla möjliga kombinationer av kandidatunderkonfigura- tioner till underkonfigurationerna hos det handskrivna mönstret 1 bildar ett eget kandidatmönster. I detta sammanhang behålls sekvensen av underkonfigurationskandi- dater som samma som sekvensen av underkonfigurationer hos det handskrivna mönstret 1. Ihopslagningen av underkonfi- gurationskandidater utförs enligt en fördefinierad regel.

Denna regel bestäms i enlighet med hur tecken normalt placeras i förhållande till varandra. Således placeras en underkonfigurationskandidat på ett visst avstånd till höger om en föregående underkonfigurationskandidat_ Den vertikala placeringen av underkonfigurationskandidaten är fixerad så att kandidaterna står på samma baslinje.

När alla kandidatmönster har bestämts jämförs repre- sentationen av det handskrivna mönstret 1 med varje kan- didatmönster, steg 14. Denna jämförelse ger ett mått på likheten för hela det handskrivna mönstret 1 med kandi- l0 15 20 25 30 35 519 014 13 datmönstret. Sàledes bestäms det kandidatmönster som har bäst individuell likhet med varje underkonfiguration tillsammans med likheten för hela mönstret.

Màttet pà likheten för ett handskrivet mönster 1 med ett kandidatmönster erhålls genom ett relativt närhets- mått. gurationskandidaterna i par av intilliggande underkon- I en föredragen utföringsform jämförs underkonfi- figurationskandidater med underkonfigurationerna hos det handskrivna mönstret l, oberoende av de andra underkonfi- gurationerna i mönstren. Alla par i ett kandidatmönster jämförs då med motsvarande par av underkonfigurationer i det handskrivna mönstret 1. En underkonfigurations- kandidat paras dä ihop med underkonfigurationskandidaten som ligger före den och i ett annat par med underkonfi- gurationen som följer den. Fler underkonfigurationer skulle emellertid kunna jämföras i gängen. Detta skulle då resultera i det faktum att betydelsen för ett enskilt tecken minskar och en större risk för feltolkning inträffar. Å andra sidan innebär jämförelse av flera underkonfigurationer i gängen att mer information om inbördes förhållanden hos tecknen används.

En relativ form s(X1,X2) beskriver hur de tvà punkt- konfigurationerna Xloch X2, vilka var och en representer- ar en underkonfiguration hos det handskrivna mönstret, bör sättas samman. Den relativa formen s(X1,X2) är ett linjärt underrum till s(X1°X2) med egenskapen S(X1°X2)=S(X1)® S(X2)® S(X1,Xz) - måttet ger ett mått på hur bra en relativ form av två Det relativa närhets- punktkonfigurationer s(X1,X2) överensstämmer med en relativ form av tvà andra punktkonfigurationer s(Y1,Yfi, där Y1 och Y2 representerar valda underkonfigurations- kandidater, vilka bildar en mall för hur punktkonfigura- I syfte att hitta det relativa närhetsmàttet mäste vi bilda tionerna bör vara positionerade med varandra. s(X)=s(X1)EB s(X2)® s(Y1,Y2) . Detta representerar en sammansatt konfiguration X, där de två konfigurationerna X1 och X2 separat affint transformerats för bildande av 10 15 20 25 30 519 014 14 den relativa formen s(Y1,Y2). Då ger ett närhetsmått, som beräknats för de tvà kombinerade konfigurationerna X och X0= X1°X2ett mått pà hur mycket den ursprungliga samman- satta konfigurationen Xoöverensstämmer med den konfigu- ration som transformerats att ha den relativa formen från mallen s(Y1,Y2). Sàledes behöver vi hitta den transforma- tion av Xo som ger bäst approximation av Y°= Y1°Y2 med begränsningen att de individuella affina formerna för X1 och X2 skall förbli konstanta under transformationen. Den transformerade versionen av X0 kallas X. Det relativa närhetsmàttet skulle då kunna erhållas genom jämförelse av X0 och X.

Detta skulle kunna göras genom bildande av en ny matris ägg, X_X, o_x,1o o 12-0 X2"o oxzl' där l innebär en kolumn av ettor och 0 innebär en eller flera kolumner av nollor, beroende pá sammanhanget. Sedan görs denna matris ortogonal, X12_L=Orth (X12) .

Ag=( X0 1 ) är då en linjärkombination av dessa kolumner. *¥°=*¥nl*A En annan linjärkombination, X, av kolumnerna Xn¿, kommer att ge oss en lösning pà vàrt problem, d v s sammansättningen av de tvà delarna X1 och X2 som bäst approximerar Yo. För att hitta denna linjärkombination vill vi minimera normen "Iz/'Youf :IIXIZL *B-nuf' 10 15 20 25 30 35 519 014 15 där &g=( Yo 1 ). Det B som minimerar denna norm kan hittas från normalekvationer XlTzlXxzlß = X1TzlYo <3 B = XêlYo Sedan jämför vi X med X¿næd hjälp av närhetsmàttet (Xo/X) - det relativa närhetsmàttet. som definierats ovan, Detta refereras till som En observation som är användbar när detta skall implementeras är att P(X0>l)=P(X1Tz1A>X121B)=P(AvB) Alla uträkningar som måste göras för beräkning av det relativa närhetsmàttet är således att ortogonalisera xn till xm, beräkna A=X,TZLXO, beräkna B=XIQLYO och jämföra A och B, d v s beräkna P(A,B).

Varje kandidatmönster har nu ett närhetsmàtt för var och en av dess individuella underkonfigurationskandidater och ett relativt närhetsmàtt för hela kandidatmönstret.

Dessa mått bör viktas på ett lämpligt sätt så att det handskrivna mönstret 1 tolkas korrekt. Således utformas en kostnadsfunktion så att den ger lägst kostnad till det bästa kandidatmönstret. Sedan beräknas kostnadsfunktion- en, steg 16, för identifiering av det bäst överens- stämmande kandidatmönstret, vilket kommer att vara resul- tatet av igenkänningen. Kostnadsfunktionen summerar inte bara närhetsmåtten för kandidatmönstren utan dessa viktas i enlighet med hur komplex kandidaten är. Den slutliga kostnadsfunktionen är således en funktion av de viktade närhetsmåtten. Ett enkelt förslag är att bara addera alla viktade närhetsmàtt. Ett annat eventuellt bättre till- vägagàngssätt är att addera alla faktorer och dividera med antalet faktorer så att man får någon form av ”kostnad per faktor”. Annars kan segmenteringar med färre underkonfigurationer få en felaktig fördel. Enligt den 519 014 16 för tillfället föredragna utföringsformen är kostnads- funktionen summan m: ms' Q (0 0) 0) 0) 0 Zdgfl Wii) E/'Ågf ßgflvci' *(3111) _ja #1 c0st(S¿) - + ng Ini-1 5 där S1,S2,...,Sn, S¿=(C¿,Gi) är de sekvenser som består av underkonfigurationskandidaterna Ci=(d°,c?,...,c$) och de motsvarande underkonfiguration- erna Gi=(gf),gf),...,gfi?) för det handskrivna mönstret l, varvid sekvensen består av mi underkonfigurationer, där 10 funktionen F(gY),4Ü), som definieras nedan, ger ett mått (I) pà hur bra kandidat underkonfigurationskandidaten çf är för underkonfigurationen gy) oberoende av hur komplex kandidaten är, och där pr(gY),gf¿,cf),cfl,) ger det rela- tiva närhetsmàttet för paret (gf),gæ1) jämfört med paret 15 (QÜ,c¶1). F-funktionen används för att inkludera det faktum att olika underkonfigurationer/tecken får olika typiska värden av närhet när de jämförs med sin databas- ekvivalent. Således tar F-funktionen hänsyn till både närhetsmàttet p(g,c) och vad närhetsmàttet vanligtvis är 20 för den kandidaten när den anses vara den bästa kandidaten. Funktionen skulle exempelvis kunna vara _ Mgß) “w- me) där p(c) är medelnärhetsmàttet för kandidaten, c, 25 när den anses vara bäst. I den för tillfället föredragna utföringsformen används emellertid följande definition: faflrafij-šgfïí-š där fl(g) är antalet segment av vilka underkonfigura- 30 tionen är uppbyggd. Detta främjar tecken med flera l0 15 20 25 30 35 519 014 17 segment och ger möjligheten att jämföra dessa tecken med enklare tecken pà förhoppningsvis lika villkor.

Denna kostnadsfunktion skulle kunna finjusteras så att den passar de mönster som man eftersträvar att tolka och skulle således kunna vara olika utformad för olika alfabet.

Kandidatmönstret som får det lägsta resultatet av kostnadsfunktionen kommer att anses som tolkningen av det handskrivna mönstret 1.

Det är inte säkert att alla punkter i ett tecken inmatas i följd. Vissa punkter skulle kunna inmatas före ett följande tecken, medan andra punkter skulle kunna inmatas efter det tecknet. Exempel på detta är prickar i ett ”i” eller ett ”j” Dessa särdrag kallas sekundära bågar och eller tvärstrecken över ett ”t” eller ett ”q” skrivs ofta sist i ett ord. Informationen i dessa sekundära bågar skulle kunna vara användbar för korrekt tolkning av tecken och särskiljning mellan exempelvis ett ”m” och tre på varandra följande ”i”:n.

Om ett tecken med en sekundär bàge föreslås som en kandidat för en underkonfiguration görs därför en kontroll om en sekundär bàge förekommer och i så fall om denna sekundära båge är korrekt placerad jämfört med tecknets primära bàge. Om det inte finns någon sekundär båge, eller om den är felplacerad, adderas en bestraff- ning till kandidaten som tolkning av underkonfiguration- en, medan å andra sidan om en sekundär bàge är korrekt placerad adderas en bonus till kandidaten som tolkning av underkonfigurationen. Ett mått på placeringen av den sekundära bàgen med avseende på den primära bàgen erhålls med det relativa närhetsmàttet som beskrivits ovan. Den relativa formen, d v s tecknet med en primär och en sekundär bàge, lagras företrädesvis i databasen, eftersom det sätt att slå ihop en sekundär båge till en primär båge inte följer ett system som är lika för alla tecken.

Med hänvisning till fig 3 kommer en anordning 20 för igenkänning av ett handskrivet mönster enligt uppfinning- 10 15 20 25 30 35 519 014 18 en att beskrivas. Anordningen 20 för igenkänning av ett handskrivet mönster skulle kunna vara införlivad i en datahanteringsanordning, sàsom en dator, en PDA, en mobiltelefon, en skanner eller liknande, vilken inne- fattar en textinmatningsenhet för inmatning av text genom manuell skrift. Anordningen 20 för igenkänning av det handskrivna mönstret innefattar organ för detektering 22 av ett handskrivet mönster, som inmatats pà textin- matningsenheten. Organet för detektering 22 tar före- trädesvis upprepade gånger upp positionen för en penna 24 i ett tryckkänsligt område 26, pà vilket en användare skriver ett mönster. Organet för detektering 22 skapar en digital representation av det handskrivna mönstret.

Anordningen 20 för igenkänning av ett handskrivet mönster innefattar vidare organ för uppdelning 28 av representa- tionen av det handskrivna mönstret. Organet för upp- delning 28 delar upp det handskrivna mönstret i underkon- figurationer. Om det handskrivna mönstret inte kan delas upp otvetydigt skapar organet för uppdelning 28 flera uppsättningar av underkonfigurationer som tar hänsyn till olika uppdelningar av det handskrivna mönstret.

Anordningen 20 för igenkänning av ett handskrivet mönster innefattar vidare en databas 30, i vilken refe- renskonfigurationer är lagrade. Ett första organ för jäm- förelse 32 är anordnat att jämföra underkonfigurationerna hos det handskrivna mönstret med referenskonfiguration- erna i databasen 30 och skapar ett màtt pà likheten mellan underkonfigurationerna och referenskonfiguration- erna. Det första organet för jämförelse 32 väljer de referenskonfigurationer som har ett mätt på likhet under en tröskel som kandidater för den underkonfigurationen.

Ett organ för hopslagning 34 slår ihop en kandidat för varje underkonfiguration till ett kandidatmönster. För varje uppsättning av underkonfigurationer slås alla kombinationer av valda kandidater för underkonfigura- tionerna ihop till kandidatmönster. Således skapas i de flesta fall flera olika kandidatmönster. 10 l5 20 25 30 35 519 014 19 Ett andra organ för jämförelse 36 jämför sedan kandidatmönstren med det handskrivna mönstret för att ge ett mått på likheten för de fullständiga mönstren med varandra. Ett organ för val av en bästa motsvarighet 38 viktar måtten på likheterna för de individuella under- konfigurationerna och de hela mönstren så att det kandi- datmönster som har den lägsta kostnaden hittas. En pre- sentationsanordning 40 presenterar sedan detta kandidat- mönster, med typografiska bokstäver, som igenkänningen av det handskrivna mönstret.

I det ovanstående har beskrivningen gjorts väsent- ligen på basen av att tecknen skrivs på en tryckkänslig skärm och detekteras samtidigt som de skrivs. Igen- känningsmetoden skulle emellertid också kunna tillämpas på mönster som detekteras, exempelvis inskannas, efter att de har skrivits på ett papper. Således innefattar detekteringen, istället för åtgärden att avkänna skriften på den tryckkänsliga skärmen, åtgärden att läsa (skanna) tecknen från pappret. Representationer av de lästa, hand- skrivna mönstren detekteras och skapas således och igen- känning kan sedan utföras såsom beskrivits ovan.

Det bör understrykas att den föredragna utförings- formen som beskrivits häri inte är på något sätt begrän- sande och att många alternativa utföringsformer är möjliga inom skyddsomfånget som definieras av bifogade krav. Exempelvis har den ovanstående utföringsformen beskrivits med hänvisning till igenkänning av latinska tecken och ord. Uppfinningen skulle emellertid kunna tillämpas på igenkänning av andra alfabet eller andra symboler.

I en alternativ utföringsform skulle det handskrivna mönstret kunna vara ett tecken eller en del av ett tecken. Uppdelningen av det handskrivna mönstret kommer då att åstadkommas på ett annat sätt. Om exempelvis kinesiska tecken skall igenkännas skulle uppdelningen kunna returnera varje båge som en underkonfiguration. 10 15 20 519 014 20 Steget att bilda underkonfigurationerna skulle kunna utföras pà flera olika sätt. Exempelvis skulle brytpunkt- erna 7 pä var sida om en underkonfiguration kunna identi- fieras genom att punkter med maximal krökning i det hand- skrivna mönstret hittas. Ett annat sätt att hitta bryt- punkterna 7 är att hitta lokala extrempunkter i det hand- skrivna mönstrets vertikala riktning. Dessa och andra sätt att hitta brytpunkterna 7 skulle också kunna kombi- neras, eftersom de funna brytpunkterna 7 inte är iden- tiska för dessa metoder.

De tvà konfigurationerna Y1 och Y2, som representerar de valda underkonfigurationskandidaterna transformeras affint i en alternativ utföringsform för beräkning av det relativt närhetsmàttet pà hur bra den relativa formen för tvà underkonfigurationer hos det handskrivna mönstret s(X1,X2) överensstämmer med den relativa formen s(Y1,Y2).

Sàledes bildas s(y)=s(Y1NE s(Y¿)® s(X1,X2) och beräknas ett närhetsmàtt för de två kombinerade konfigurationerna y och YO= Y1°Y2för erhållande av det relativa närhetsmàttet.

I en annan alternativ utföringsform beräknas det relativa närhetsmàttet direkt mellan de kombinerade konfigurationerna X°= X1°X2 och Y0= Y1°Y2.

Claims (10)

lO 15 20 25 30 35 519 014 21 PATENTKRAV

1. Metod för igenkänning av ett handskrivet mönster, vilken metod innefattar stegen att: bilda (4) mönstret, en representation av det handskrivna bilda (6) åtminstone tvà underkonfigurationer genom uppdelning av representationen av det handskrivna mönstret, behandla underkonfigurationerna, varvid steget att behandla innefattar stegen att: jämföra (8) varje underkonfiguration med referenskonfigurationer, välja (10) åtminstone en underkonfigurations- kandidat för varje underkonfiguration bland refe- renskonfigurationerna, varvid steget att välja är baserat pà steget att jämföra, och bestämma (12) åtminstone ett kandidatmönster, som består av en vald underkonfigurationskandidat för varje underkonfiguration, jämföra (14) representationen av det handskrivna mönstret med kandidatmönstret och beräkna (16) en kostnadsfunktion, som är baserad pà jämförelsen av representationen av det handskrivna mönstret med kandidatmönstret och på jämförelsen av underkonfigurationerna med de valda underkonfigurations- kandidaterna i kandidatmönstret så att ett bäst över- ensstämmande kandidatmönster hittas.

2. Metod enligt krav 1, vid vilken steget att bestämma (12) ett kandidatmönster innefattar steget att slå ihop en vald underkonfigurationskandidat för varje underkonfiguration till ett kandidatmönster, varvid ihop- slagningen görs i enlighet med en fördefinierad regel.

3. Metod enligt krav 1 eller 2, vid vilken steget att jämföra (14) representationen av det handskrivna mönstret med kandidatmönstret innefattar steget att mäta en skillnad för positioneringen av underkonfigurationerna lO 15 20 25 30 35 519 014 22 relativt varandra jämfört med positioneringen av de valda underkonfigurationskandidaterna relativt varandra i kandidatmönstret.

4. Metod enligt krav 3, vid vilken steget att mäta skillnaden för positioneringen innefattar stegen att transformera representationen av det handskrivna mönstret så att den liknar kandidatmönstret så mycket som möjligt och beräkna en geometrisk närhet mellan representationen av det handskrivna mönstret och den transformerade repre- sentationen av det handskrivna mönstret.

5. Metod enligt krav 3, vid vilken steget att mäta skillnaden för positioneringen innefattar stegen att transformera kandidatmönstret så att det liknar repre- sentationen av det handskrivna mönstret så mycket som möjligt och beräkna en geometrisk närhet mellan kandi- datmönstret och det transformerade kandidatmönstret.

6. Metod enligt krav 3, vid vilken steget att mäta skillnaden för positioneringen innefattar beräkning av en geometrisk närhet mellan representationen av det hand- skrivna mönstret och kandidatmönstret.

7. Metod enligt något av föregående krav, vid vilken steget att bilda (6) åtminstone två underkonfigurationer genom uppdelning av representationen av det handskrivna mönstret innefattar steget att bilda olika uppsättningar av underkonfigurationer genom uppdelning av representa- tionen av det handskrivna mönstret på alternativa sätt.

8. Metod enligt krav 7, vid vilken steget att behandla underkonfigurationerna utförs för varje uppsätt- ning av underkonfigurationer.

9. Metod enligt något av föregående krav, vid vilken igenkänningen av det handskrivna mönstret är oberoende av en grupp transformationer.

10. Anordning för igenkänning av ett handskrivet mönster, vilken innefattar: organ för detektering (22) av det handskrivna mönstret och bildande av en representation av det hand- skrivna mönstret, 10 15 20 519 014 23 (28) av åtminstone tvà under- konfigurationer genom uppdelning av representationen av organ för bildande det handskrivna mönstret, en databas (30), i vilken referenskonfigurationer är lagrade, organ för jämförelse (32) av varje underkonfigura- tion med referenskonfigurationerna, organ för val av för varje underkonfiguration åtmin- stone en underkonfigurationskandidat från referenskon- figurationerna i databasen, vilket val är baserat pà jämförelsen, organ för bestämning av åtminstone ett kandidat- mönster, som består av en vald underkonfigurations- kandidat för varje underkonfiguration, (36) handskrivna mönstret med kandidatmönstret och organ för jämförelse av representationen av det organ för beräkning av en kostnadsfunktion, som är baserad på jämförelsen av representationen av det hands- krivna mönstret med kandidatmönstret och pà jämförelsen av underkonfigurationerna med de valda underkonfigura- tionskandidaterna i kandidatmönstret så att ett bäst överensstämmande kandidatmönster hittas.