Methods and apparatuses for handwriting recognition

• US 6,956,969 B2
• Filed: 04/07/2003
• Issued: 10/18/2005
• Est. Priority Date: 05/23/1996
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.), National University Of Singapore Institute Of Systems Science
• Inventors: Wu, Yi-Min, Pittman, James A., Loudon, Gareth H.
• Primary Examiner(s): LAROSE, COLIN M
• Application Number:
  US10/408,895
• Publication Number:
  US 20030190074A1
• Time in Patent Office: 925 Days
• Field of Search: 382/187, 382/189, 382/217, 382/218, 382/185, 382/186
• US Class Current: 382/185
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 30/287 of Kanji, Hiragana or Katakana characters

Abstract

Method and apparatus for handwriting recognition system for ideographic characters and other characters based on subcharacter hidden Markov models. The ideographic characters are modeled using a sequence of subcharacter models and by using two-dimensional geometric layout models of the subcharacters. The subcharacter hidden Markov models are created according to one embodiment by following a set of design rules. The combination of the sequence and geometric layout of the subcharacter models is used to recognize the handwriting character.

Claims

1. A method of recognizing a handwritten character comprising:

comparing a handwritten input to a first model of a first portion of said character;

comparing said handwritten input to a second model of a second portion of said character, said second portion of said character having been defined to follow in time said first portion, wherein said first portion is a first radical and said second portion is a second radical, and wherein said first model is a first hidden Markov model and said second model is a second hidden Markov model, and wherein said second model is defined to follow said first model in time.

2. A method as in claim 1, wherein said handwritten character is a cursively written character and wherein said method is on an on-line method of recognizing a handwritten character.

3. A method as in claim 1, wherein said handwritten character is a printed character.

4. A method as in claim 3 wherein said handwritten character is preprocessed to provide a cursively written representation and said handwritten input is said cursively written representation.

5. A method as in claim 1, further comprising:

comparing a first geometric feature of said first portion to a first geometric model of said first portion;

comparing a second geometric feature of said second portion to said first geometric model.

6. A method as in claim 5 further comprising:

comparing said first geometric feature of said first portion to a second geometric model of said second portion;

comparing said second geometric feature of said second portion to said second geometric model.

7. A method as in claim 6 wherein said first geometric feature comprises a mean for a center of said first portion of said handwritten character and wherein said first geometric model comprises a mean for a plurality of centers of a plurality of examples of said first portion.

8. A method as in claim 1 wherein said first portion comprises a first portion of a recognized radical and said second portion comprises a second portion of said recognized radical, wherein said first portion is normally written first and then at least another portion of another recognized radical is written and then said second portion is written.

9. A method as in claim 1 wherein said character comprises a first recognized radical and a second recognized radical and wherein said method recognizes said character by using said first model for both said first recognized radical and said second recognized radical and wherein said first portion comprises said first recognized radical and said second recognized radical, and wherein said second recognized radical is normally written either before or after said first recognized radical.

10. A method for recognizing a handwritten character comprising:

comparing a first geometric feature of a first portion of a character to a first geometric model of said first portion;

comparing a second geometric feature of a second portion of said character to said first geometric model of said first portion, wherein said first portion and said second portion are first and second radicals of said character, and wherein said first geometric feature comprises a mean for a center of said first portion of said handwritten character and wherein said first geometric model comprises a mean for a plurality of centers of a plurality of examples of said first portion.

11. A method for recognizing a handwritten character comprising:

comparing a first geometric feature of a first portion of a handwritten character to a first geometric model of said first portion;

comparing a second geometric feature of a second portion of said handwritten character to said first geometric model of said first portion, wherein said first portion and said second portion are first and second radicals of said handwritten character; and

segmenting said handwritten character by using a Viterbi search through a lexical tree of hidden Markov models, comprising first and second models of said first and second radicals.

12. A method as in claim 11, wherein said first and second models have been defined to follow in a specific time sequence.

13. A method of creating a database of radicals for use in handwriting recognition of a handwritten character, said method comprising:

storing a first model in a computer readable storage medium for a first portion of said character;

storing a second model in said computer readable storage medium for a second portion of said character, wherein said first portion comprises a first portion of a recognized radical and said second portion comprises a second portion of said recognized radical, wherein said first portion is normally written first and then at least another portion of another recognized radical is written and then said second portion is written, wherein said first model is a first hidden Markov model for said first portion and said second model is a second hidden Markov model for said second portion and wherein said first model is defined to follow in time said second model.

14. A method of creating a database of radicals for use in handwriting recognition, said method comprising:

storing a first model in a computer readable storage medium for a first recognized radical;

storing a second model in said computer readable storage medium for said first recognized radical, said first recognized radical having different shapes depending on the use of said first recognized radical in a character, wherein said first model is a first hidden Markov model and said second model is a second hidden Markov model.

15. A method of creating a database of radicals for use in handwriting recognition of a handwritten character, said method comprising:

storing a first hidden Markov model in a computer readable storage medium for a first portion of said character;

storing a second hidden Markov model in said computer readable storage medium for a second portion of said character, wherein said second hidden Markov model having been defined as following in time said first hidden Markov model, wherein said character comprises a first recognized radical and a second recognized radical and wherein said method recognizes said character by using said first model for both said first recognized radical and said second recognized radical and wherein said first portion comprises said first recognized radical and said second recognized radical, and wherein said second recognized radical is normally written either before or after said first recognized radical.

16. A method as in claim 15 further comprising:

storing a first geometric model of said first portion;

storing a second geometric model of said second portion.

17. A method as in claim 15 wherein said first portion comprises a first portion of a recognized radical and said second portion comprises a second portion of said recognized radical, wherein said first portion is normally written first and at least another portion of another recognized radical is written and then said second portion is written.

18. A digital processing system comprising:

an input table for inputting handwritten characters;

a bus coupled to said input tablet;

a processor coupled to said bus;

a memory coupled to said bus, said memory storing a first model of a first portion of a character desired to be recognized, and storing a second model of a second portion of said character, said memory storing said second model such that said second model is defined to follow in time said first model, wherein said first portion is a first radical and said second portion is a second radical, and wherein said first model is a first hidden Markov model and said second model is a second hidden Markov model.

19. A system as in claim 18 wherein said processor recognizes an inputted handwritten character by comparing a representation of said inputted handwritten character to said first model and then to said second model.

20. A system as in claim 19 wherein said representation is a preprocessed representation such that if said inputted handwritten character is a printed character, said preprocessed representation provides a one-stroke written representation of said printed characters.

21. A system as in claim 19 wherein said system comprises a printed circuit housing which is adapted to connect to a computer system through an expansion connection of said computer system.

22. A system as in claim 21 wherein said bus and said processor are positioned on said printed circuit housing.

23. A system as in claim 19 wherein said system is part of a computer system and said bus is a system bus and said processor is a central processing unit of said computer system.

24. A system as in claim 19 wherein said memory further stores a first geometric model of said first portion and stores a second geometric model of said second portion.

25. A system as in claim 24 wherein said processor further recognizes said inputted handwritten character by comparing a first geometric feature of said first portion to said first geometric model and by comparing a second geometric feature of said second portion to said first geometric model.

26. A system as in claim 25 wherein said processor performs a Viterbi search through a lexical tree of plurality of hidden Markov models stored in said memory, said plurality of hidden Markov models comprising said first hidden Markov model and said second hidden Markov model.

27. A digital processing system as in claim 18 wherein said first portion comprises a first portion of a recognized radical and said second portion comprises a second portion of said recognized radical, wherein said first portion is normally written first in time and then at least another portion of another recognized radical is written and then said second portion is written.

29. A digital processing system as in claim 18 wherein said memory stores preclassification data and instructions for selecting n best characters from a larger number of characters.

30. A digital processing system as in claim 25 wherein said memory stores preclassification data and instructions for selecting n best characters from a larger number of characters.

28. A digital processing system comprising:

an input for inputting handwritten characters;

a bus coupled to said input;

a processor coupled to said bus;

a memory coupled to said bus, said memory storing a first model for a first recognized radical and storing a second model for said first recognized radical, said first recognized radical having different shapes depending on the use of said first recognized radical in a character, wherein said first model is a first hidden Markov model and said second model is a second hidden Markov model.

31. A computer readable storage medium containing executable computer program instructions which when executed by a digital processing system cause the system to perform the steps of:

comparing a first geometric feature of a first portion of a character to a first geometric model of said first portion;

comparing a second geometric feature of a second portion of said character to said first geometric model of said first portion, wherein said first portion and said second portion are first and second radicals of said character and wherein said medium contains executable instructions which when executed cause the system to perform the step of segmenting said character by using a search through a group of hidden Markov models comprising first and second models of said first and second radicals.

32. A computer readable storage medium as in claim 31, wherein said second model has been defined to follow said first model in time.

33. A computer readable storage medium as in claim 31 wherein said medium contains executable instructions which when executed cause the system to perform the step of preclassifying n best characters by selecting the n best characters from a larger number of characters.

34. A computer readable storage medium containing executable computer program instructions which when executed by a digital processing system cause the system to perform the steps of:

comparing a handwritten input to a first model of a first portion of a character;

comparing said handwritten input to a second model of a second portion of said character, said second portion of said character having been defined to follow in time said first portion, wherein said first portion is a first radical and said second portion is a second radical, said first model is first hidden Markov model and said second model is a second hidden Markov model, and wherein said second model is defined to follow said first model in time.

35. A computer readable storage medium as in claim 34 wherein said medium contains instructions which when executed cause the system to perform the steps of:

comparing a first geometric feature of said first portion to a first geometric model of said first portion;

comparing a second geometric feature of said second portion to said first geometric model.

36. A computer readable storage medium as in claim 34 wherein said character comprises a first recognized radical and a second recognized radical and wherein said character is recognized by using said first model for both said first recognized radical and second recognized radical and wherein said first portion comprises said first recognized radical and said second recognized radical, and wherein said second recognized radical is normally written either before or after said first recognized radical.

37. A computer readable storage medium as in claim 34 wherein said medium contains instructions which when executed cause the system to perform the step of preclassifying n best characters by selecting the n best characters from a larger number of characters.

38. An apparatus for recognizing a handwritten character comprising:

means for comparing a handwritten input to a first model of a first portion of said character; and

means for comparing said handwritten input to a second model of a second portion of said character said second portion of said character having been defined to follow in time said first portion, wherein said first portion is a first radical and said second portion is a second radical, and wherein said first model is a first hidden Markov model and said second model is a second hidden Markov model, and wherein said second model is defined to follow said first model in time.

39. An apparatus as in claim 38 comprising:

means for comparing a first geometric feature of said first portion to a first geometric model of said first portion;

means for comparing a second geometric feature of said second portion to said first geometric model.