Methods and apparatuses for handwriting recognition

• US 20030190074A1
• Filed: 04/07/2003
• Published: 10/09/2003
• Est. Priority Date: 05/23/1996
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Gareth H. Loudon, James A. Pittman, Yi-Min Wu
• Inventors: Wu, Yi-Min, Pittman, James A., Loudon, Gareth H.
• Granted Patent: US 6,956,969 B2
• Time in Patent Office: Days
• US Class Current: 382/187
• 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.

2. A method as in claim 1 wherein said first portion is a first radical and said second portion is a second radical.

3. A method as in claim 2 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.

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

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

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

7. A method as in claim 3 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.

8. A method as in claim 7 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.

9. A method as in claim 8 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.

10. 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.

11. 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.

12. 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.

13. A method as in claim 12 wherein said first portion and said second portion are first and second radicals of said character.

14. A method as in claim 13 further comprising 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.

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

16. A method as in claim 13 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.

17. A method of recognizing a handwritten character comprising:

receiving an input of said handwritten character, wherein said handwritten character is written with multiple strokes;

preprocessing said input to provide a one-stroke written representation of said handwritten character.

18. A method as in claim 17 wherein said preprocessing step comprises at least one of interpolating points in said input, smoothing said points, scaling said points and resampling said points.

19. 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.

20. A method as in claim 19 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.

21. 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.

22. A method as in claim 21 wherein said first model is a first hidden Markov model and said second model is a second hidden Markov model.

23. 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.

24. A method as in claim 23 further comprising:

storing a first geometric model of said first portion;

storing a second geometric model of said second portion.

25. A method as in claim 23 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.

26. A method as in claim 23 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.

27. A digital processing system comprising:

an input tablet 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.

28. A system as in claim 27 wherein said first portion is a first radical and said second portion is a second radical.

29. A system as in claim 28 wherein said first model is a first hidden Markov model and said second model is a second hidden Markov model.

30. A system as in claim 27 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.

31. A system as in claim 30 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.

32. A system as in claim 30 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.

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

34. A system as in claim 30 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.

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

36. A system as in claim 35 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.

37. A system as in claim 36 wherein said processor performs a Viterbi search through a lexical tree of a 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.

38. A digital processing system as in claim 27 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.

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

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

39. 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.

42. 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.

43. A computer readable storage medium as in claim 42 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.

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

45. A computer readable storage medium as in claim 42 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.

46. 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.

47. A computer readable storage medium as in claim 46 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.

48. A computer readable storage medium as in claim 46 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.

49. A computer readable storage medium as in claim 46 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.

50. A computer readable storage medium as in claim 46 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.

51. 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.

52. An apparatus as in claim 51 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.

53. An apparatus as in claim 52 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.