Accelerated handwritten symbol recognition in a pen based tablet computer

• US 20020118879A1
• Filed: 05/03/2001
• Published: 08/29/2002
• Est. Priority Date: 05/03/2000
• Status: Active Grant

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Hickerson, Kevin, Eden, Uri
• Granted Patent: US 7,266,236 B2
• Time in Patent Office: Days
• US Class Current: 382/187
• CPC Class Codes: G06V 10/94 Hardware or software architectures specially adapted for image or video understanding
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

The present invention provides a method and apparatus for accelerated handwritten symbol recognition in a pen based tablet computer. In one embodiment, handwritten symbols are translated into machine readable characters using special purpose hardware. In one embodiment, the special purpose hardware is a recognition processing unit (RPU) which performs feature extraction and recognition. A user inputs the handwritten symbols and software recognition engine preprocesses the input to a reduced form. The data from the preprocessor is sent to the RPU which performs feature extraction and recognition. In one embodiment, the RPU has memory and the RPU operates on data in its memory. In one embodiment, the RPU uses a hidden Markov model (HMM) as a finite state machine that assigns probabilities to a symbol state based on the preprocessed data from the handwritten symbol. In another embodiment, the RPU recognizes collections of symbols, termed “wordlets,” in addition to individual symbols.

Claims

1. A method of translating handwritten input to machine readable characters comprising:

obtaining a data item; and

performing one or more recognition processing operations upon said data item by a special purpose hardware unit to produce a second data item.

2. The method of claim 1 wherein said data item is a handwritten symbol.

3. The method of claim 1 further comprising:

altering said first data item by a preprocessor to a reduced form.

4. The method of claim 3 wherein said step of altering is fully information preserving.

5. The method of claim 1 further comprising:

selecting one or more machine readable characters by a postprocessor.

6. The method of claim 1 wherein said special purpose hardware unit is configured to perform a first recognition processing operation and a second recognition processing operation in parallel.

7. The method of claim 1 wherein said special purpose hardware unit is configured to perform hidden Markov model computations.

8. The method of claim 1 wherein said special purpose hardware unit comprises:

a memory unit.

9. The method of claim 5 further comprising:

presenting said machine readable characters to a user.

10. The method of claim 9 further comprising:

obtaining an indication from said user of whether said machine readable characters are a correct translation of said data item.

11. The method of claim 1 wherein said data item is a combination of a plurality of handwritten symbols.

12. The method of claim 1 further comprising:

adjusting the operation of said special purpose hardware unit in accordance with a set of training data.

13. The method of claim 3 further comprising:

adjusting the operation of said preprocessor in accordance with a set of training data.

14. The method of claim 5 further comprising:

adjusting the operation of said postprocessor in accordance with a set of training data.

15. The method of claim 5 wherein said step of selecting comprises:

determining a context of said data item.

16. The method of claim 15 wherein said step of selecting further comprises:

determining a correctly spelled word wherein said machine readable characters appear in said correctly spelled word and said correctly spelled word is appropriate for said context.

17. The method of claim 15 wherein said step of selecting further comprises:

determining whether machine readable characters are grammatically incorrect for said context.

18. The method of claim 15 wherein said step of selecting further comprises:

determining a word in which said machine readable characters appear in said word and said word appeared previously in said context.

19. The method of claim 15 wherein said step of selecting further comprises:

examining a set of user information.

20. A method of translating handwritten input to machine readable characters comprising:

obtaining a data item; and

performing one or more hidden Markov model operations upon said data item.

21. The method of claim 20 wherein said hidden Markov model operations are forward probability calculations.

22. The method of claim 20 wherein said hidden Markov model operations are backward probability calculations.

23. The method of claim 20 wherein one or more wordlets are part of a symbol alphabet.

25. The handwritten input to machine readable characters translator of claim 24 wherein said data item is a handwritten symbol.

26. The handwritten input to machine readable characters translator of claim 24 further comprising:

a preprocessor configured to alter said first data item to a reduced form.

27. The handwritten input to machine readable characters translator of claim 26 wherein said preprocessor alters said first data item in a fully information preserving manner.

28. The handwritten input to machine readable characters translator of claim 24 further comprising:

a postprocessor configured to select one or more machine readable characters.

29. The handwritten input to machine readable characters translator of claim 24 wherein said special purpose hardware unit is configured to perform a first recognition processing operation and a second recognition processing operation in parallel.

30. The handwritten input to machine readable characters translator of claim 24 wherein said special purpose hardware unit is configured to perform hidden Markov model computations.

31. The handwritten input to machine readable characters translator of claim 24 wherein said special purpose hardware unit comprises:

a memory unit.

32. The handwritten input to machine readable characters translator of claim 28 further comprising:

a means for presenting said machine readable characters to a user.

33. The handwritten input to machine readable characters translator of claim 32 further comprising:

a means for obtaining an indication from said user of whether said machine readable characters are a correct translation of said data item.

34. The handwritten input to machine readable characters translator of claim 24 wherein said data item is a combination of a plurality of handwritten symbols.

35. The handwritten input to machine readable characters translator of claim 24 further comprising:

a means for adjusting the operation of said special purpose hardware unit in accordance with a set of training data.

36. The handwritten input to machine readable characters translator of claim 26 further comprising:

a means for adjusting the operation of said preprocessor in accordance with a set of training data.

37. The handwritten input to machine readable characters translator of claim 28 further comprising:

a means for adjusting the operation of said postprocessor in accordance with a set of training data.

38. The handwritten input to machine readable characters translator of claim 28 wherein said postprocessor comprises:

a determiner configured to determine a context of said data item.

39. The handwritten input to machine readable characters translator of claim 38 wherein said postprocessor further comprises:

a second determiner configured to determine a correctly spelled word wherein said machine readable characters appear in said correctly spelled word and said correctly spelled word is appropriate for said context.

40. The handwritten input to machine readable characters translator of claim 38 wherein said postprocessor further comprises:

a second determiner configured to determine whether machine readable characters are grammatically incorrect for said context.

41. The handwritten input to machine readable characters translator of claim 38 wherein said postprocessor further comprises:

a second determiner configured to determine a word in which said machine readable characters appear in said word and said word appeared previously in said context.

42. The handwritten input to machine readable characters translator of claim 38 wherein said postprocessor further comprises:

an examiner configured to examine a set of user information.

24. A handwritten input to machine readable characters translator comprising:

a means for obtaining a data item; and

a special purpose hardware unit configured to perform one or more recognition processing operations upon said data item to produce a second data item.

43. A handwritten input to machine readable characters translator comprising:

a means for obtaining a data item; and

a computation unit configured to perform one or more hidden Markov model operations upon said data item.

44. The handwritten input to machine readable characters translator of claim 43 wherein said hidden Markov model operations are forward probability calculations.

45. The handwritten input to machine readable characters translator of claim 43 wherein said hidden Markov model operations are backward probability calculations.

46. The handwritten input to machine readable characters translator of claim 43 wherein one or more wordlets are part of a symbol alphabet.

48. The computer program product of claim 47 wherein said data item is a handwritten symbol.

49. The computer program product of claim 47 further comprising:

computer readable code configured to cause a computer to alter said first data item to a reduced form.

50. The computer program product of claim 49 wherein said computer readable code configured to cause a computer to alter is fully information preserving.

51. The computer program product of claim 47 further comprising:

computer readable code configured to cause a computer to select one or more machine readable characters.

52. The computer program product of claim 47 wherein said computer readable code configured to cause a computer to perform is further configured to perform a first recognition processing operation and a second recognition processing operation in parallel.

53. The computer program product of claim 47 wherein said computer readable code configured to cause a computer to perform is further configured to perform hidden Markov model computations.

54. The computer program product of claim 47 wherein said computer readable code configured to cause a computer to perform comprises:

computer readable code configured to cause a computer to store a plurality of data items.

55. The computer program product of claim 51 further comprising:

computer readable code configured to cause a computer to present said machine readable characters to a user.

56. The computer program product of claim 55 further comprising:

computer readable code configured to cause a computer to obtain an indication from said user of whether said machine readable characters are a correct translation of said data item.

57. The computer program product of claim 47 wherein said data item is a combination of a plurality of handwritten symbols.

58. The computer program product of claim 47 further comprising:

computer readable code configured to cause a computer to adjust the operation of said special purpose hardware unit in accordance with a set of training data.

59. The computer program product of claim 49 further comprising:

computer readable code configured to cause a computer to adjust the operation of said preprocessor in accordance with a set of training data.

60. The computer program product of claim 51 further comprising:

computer readable code configured to cause a computer to adjust the operation of said postprocessor in accordance with a set of training data.

61. The computer program product of claim 51 wherein said computer readable code configured to cause a computer to select comprises:

computer readable code configured to cause a computer to determine a context of said data item.

62. The computer program product of claim 61 wherein said computer readable code configured to cause a computer to select further comprises:

computer readable code configured to cause a computer to determine a correctly spelled word wherein said machine readable characters appear in said correctly spelled word and said correctly spelled word is appropriate for said context.

63. The computer program product of claim 61 wherein said computer readable code configured to cause a computer to select further comprises:

computer readable code configured to cause a computer to determine whether machine readable characters are grammatically incorrect for said context.

64. The computer program product of claim 61 wherein said computer readable code configured to cause a computer to select further comprises:

computer readable code configured to cause a computer to determine a word in which said machine readable characters appear in said word and said word appeared previously in said context.

65. The computer program product of claim 61 wherein said computer readable code configured to cause a computer to select further comprises:

computer readable code configured to cause a computer to examine a set of user information.

47. A computer program product comprising:

a computer usable medium having computer readable program code embodied therein configured to translate handwritten input to machine readable characters, said computer program product comprising;

computer readable code configured to cause a computer to obtain a data item; and

computer readable code configured to cause a computer to perform one or more recognition processing operations upon said data item to produce a second data item.

66. A computer program product comprising:

a computer usable medium having computer readable program code embodied therein configured to translate handwritten input to machine readable characters, said computer program product comprising;

computer readable code configured to cause a computer to obtain a data item; and

computer readable code configured to cause a computer to perform one or more hidden Markov model operations upon said data item.

67. The computer program product of claim 66 wherein said hidden Markov model operations are forward probability calculations.

68. The computer program product of claim 66 wherein said hidden Markov model operations are backward probability calculations.

69. The computer program product of claim 66 wherein one or more wordlets are part of a symbol alphabet.