SYSTEM AND METHOD FOR INPUTTING TEXT

• US 20140359515A1
• Filed: 11/30/2012
• Published: 12/04/2014
• Est. Priority Date: 01/16/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Touchtype Limited (Microsoft Corporation)
• Inventors: Medlock, Benjamin, Aley, James, Orr, Douglas Alexander Harper
• Granted Patent: US 9,563,348 B2
• Time in Patent Office: Days
• US Class Current: 715/773
• CPC Class Codes: G06F 2203/04803 Split screen, i.e. subdividing the display area or the window area into separate subareas
• CPC Class Codes: G06F 3/017 Gesture based interaction, e.g. based on a set of recognized hand gestures interaction based on gestures traced on a digitiser G06F3/04883
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 3/0488 using a touch-screen or digitiser, e.g. input of commands through traced gestures
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06F 3/04886 by partitioning the display area of the touch-screen or the surface of the digitising tablet into independently controllable areas, e.g. virtual keyboards or menus
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A system and method for inputting text A system (10) comprising a feature identification means (2) configured to generate one or more features (12) from a plurality of samples (11), wherein each of the plurality of samples (11) are sampled at a different time and correspond to a location of a single continuous gesture on a gesture-sensitive keyboard as the gesture is being performed and, wherein each of the one or more features (12) relates to one of a plurality of targets of the gesture sensitive keyboard that a user may have intended to input when performing the gesture. The system comprises a prediction means configured to predict one or more terms (15) from the one or more features (12), the prediction means (5) comprising a prefix tree generating means (3) configured to generate a prefix tree of terms (13) which includes the one or more features (12), a path finding means (4) configured to find one or more paths (14) through the prefix tree of terms (13) given the one or more features (12), and a predictor (5). A corresponding method is also provided.

Claims

1. A method for predicting one or more terms from a single continuous gesture across a gesture-sensitive keyboard comprising:

sampling at a plurality of times the location of the gesture on the gesture-sensitive keyboard as the gesture is performed; and

predicting one or more terms from the plurality of samples by;

generating one or more features from the plurality of samples, wherein each of the one or more features relates to a target on the gesture-sensitive keyboard that a user may have intended to input when performing the gesture;

generating a prefix tree of terms which includes the one or more features;

finding one or more paths through the prefix tree of terms given the one or more features.

2. The method of claim 1, wherein the prefix tree of terms is represented by a graph, and including generating the graph using graph theory.

3. The method of claim 1 or 2, wherein generating one or more features from the plurality of samples comprises identifying a location of the gesture on the gesture-sensitive keyboard where the user may have intended to pass through a target of the gesture-sensitive keyboard.

4. The method of claim 3, wherein the location of the feature is the location of the gesture where the gesture passes closest to the target.

5. The method of any preceding claim, wherein the target is a point target or a line target.

6. The method of any preceding claim, wherein a feature is identified for each target on the gesture-sensitive keyboard.

7. The method of claim 6, wherein a feature is only retained if the minimum distance between the feature and the target is below a threshold distance.

8. The method of any preceding claim, wherein each feature comprises a distance metric which corresponds to the minimum distance between the gesture and the target.

9. The method of any preceding claim, wherein the prefix tree of terms is generated by retaining the terms of a dictionary prefix tree which are allowed given the one or more features.

10. The method according to claim 9, wherein a term of the dictionary prefix tree may be retained even if a feature does not correspond to that term.

11. The method of any preceding claim, wherein the targets of the gesture-sensitive keyboard may correspond to the letters of the alphabet, and optionally word boundary delimiters, such as a space, and/or punctuation symbols.

12. The method of claim 11 when dependent on claim 8, wherein the prefix tree of terms comprises one or more nodes representing the last letter of a completed word, wherein generating the prefix tree of terms further comprises inserting a node corresponding to a space character into the prefix tree where there is a node corresponding to the last letter in a word.

13. The method of claim 12, wherein the probability associated with the node corresponding to the space character is reduced if a feature associated with that space character has not been identified.

14. The method of claim 12 or 13, wherein generating the prefix tree of terms further comprises generating at the node corresponding to the space character, a new prefix tree of terms generated by retaining the terms of a dictionary prefix tree which are allowed given the remaining features in a sequence of one or more features.

15. The method of any preceding claim, further comprising pruning the prefix tree of terms to remove all paths through the prefix tree of terms for which the ratio of the probability of a given path over the probability of the most likely path is below a predetermined threshold.

16. The method of claim 14 or claim 15 when dependent on 14, wherein the node representing a space character comprises meta-data to prune the new prefix tree of terms on the basis of context data.

17. The method of claim 11 when dependent on claim 9 or 10, wherein generating the prefix tree of terms further comprises allowing a given feature to represent a repeated instance of the character it relates to, by retaining the terms of a dictionary prefix tree which include character repetition if there is a valid path given the one or more features through the prefix tree for this repeated character.

18. The method of any preceding claim, wherein finding one or more paths through the prefix tree of terms comprises using a path-finding algorithm.

19. The method of claim 18 when dependent on claim 8, wherein the path-finding algorithm uses the distance metrics to generate a probability estimate associated with each path through the prefix tree of terms.

20. The method of claim 18 or 19, wherein the path-finding algorithm is configured to return as the one or more terms, terms for which the corresponding route has a probability estimate above a threshold value.

21. The method of any one of claims 1 to 17, wherein finding one or more paths through the prefix tree of terms comprises:

identifying one or more features which correspond to the end location of the gesture; and

assigning an indication of the cumulative probability for a given path to any node representing the one or more features that correspond to the location of the end of the gesture, only if that node corresponds to a leaf of the prefix tree of terms.

22. The method of claim 21, wherein the one or more paths are identified by ordering the cumulative probabilities and returning the path(s) for which the cumulative probability is above a threshold value, wherein the returned one or more paths correspond to the one or more terms.

23. The method of any preceding claims, wherein the one or more terms is predicted on the basis of all the currently available samples.

24. The method of claim 23, wherein the method comprises periodically updating the prediction of the one or more terms as the single continuous stroke is being performed and more samples are generated.

25. The method of any preceding claim, wherein predicting the one or more terms comprises predicting one or more words.

26. The method of claim 25, wherein, the one or more words are predicted on the basis of a single continuous gesture which corresponds to the user gesturing over one or more characters on a gesture-sensitive keyboard intended to indicate the prefix for that word.

27. The method of claim 25, wherein predicting the one or more words comprises predicting a phrase comprising a sequence of two or more words on the basis of a single continuous gesture which corresponds to the user gesturing over characters for multiple words on a gesture-sensitive keyboard.

28. The method of claim 26 or 27, wherein the method comprises using context information to tailor the prediction of one or more terms.

29. The method of any preceding claim, wherein sampling is performed at a predetermined frequency

30. The method of claim 29, wherein the sampling frequency is about 60 Hz.

31. The method of any preceding claim, wherein the prediction of the one or more terms is based on the topography of the gesture-sensitive keyboard in combination with gesture velocity and/or gesture curve direction.

32. The method of claim 31, wherein the probability of a path through the prefix tree is dependent on the topography of the gesture between two features and the targets of the keyboard associated with those two features.

33. The method of claim 32, wherein the probability of the path is based on a monotonically decreasing function of the difference between a straight-line distance between the two targets and the curved length of the gesture between the two targets.

34. The method of claim 32, wherein the probability of the path is based on a monotonically decreasing function of the difference between the direction of a straight-line between the two targets and the gesture direction at each point between the two targets.

35. The method of any preceding claim, wherein the gesture is a stroke and the gesture-sensitive keyboard is a touch-sensitive keyboard.

36. The method of claim 35, wherein the method comprises detecting pressure from a user stroking the keyboard to form the single continuous stroke and the step of sampling comprises sampling the location at which pressure is present.

37. The method of claim 36, wherein the sampling comprises detecting a pressure value and a location at a given time.

38. A computer program product comprising a computer readable medium having stored thereon computer program means for causing a processor to carry out the method of any of claims 1-37.

51. The system of any preceding claim, wherein the plurality of targets correspond to the letters of the alphabet, and optionally word boundary delimiters, such a space bar, and/or punctuation symbols.

39. A system comprising:

a feature identification means configured to generate one or more features from a plurality of samples, wherein each of the plurality of samples is sampled at a different time and corresponds to a location of a single continuous gesture on a gesture-sensitive keyboard as the gesture is being performed and, wherein each of the one or more features relates to one of a plurality of targets of the gesture sensitive keyboard that a user may have intended to input when performing the gesture; and

a prediction means configured to predict one or more terms from the one or more features, the prediction means comprising;

a prefix tree generating means configured to generate a prefix tree of terms which includes the one or more features;

a path finding means configured to find one or more paths through the prefix tree of terms given the one or more features; and

a predictor.

40. The system of claim 39, further comprising a gesture-sensitive keyboard comprising a plurality of targets and configured to receive a single continuous gesture as input.

41. The system of claim 39 or 40, further comprising a sampling means for sampling at a plurality of times the location of the gesture on the gesture-sensitive keyboard as the gesture is performed.

42. The system of any one of claim 39-41, wherein the prefix tree generating means is configured to generate a graph by graph theory, wherein the graph represents the prefix tree of terms.

43. The system of any one of claim 39-42, wherein the feature identification means is configured to generate one or more features from the plurality of samples by identifying a location of the gesture on the gesture-sensitive keyboard where the user may have intended to pass through a target of the gesture-sensitive keyboard.

44. The system of claim 43, wherein the location of the feature is the location of the gesture where the gesture passes closest to the target.

45. The system of any one of claims 39-44, wherein the target is a point target or a line target.

46. The system of claim 43 or 44 wherein the feature identification means is configured to identify a feature for each of the plurality of targets.

47. The system of claim 46, wherein the feature identification means is configured to retain a feature only if the minimum distance between the feature and the target is below a threshold distance.

48. The system of any one of claims 39-47, wherein each feature comprises a distance metric which corresponds to the minimum distance between the gesture and the target.

49. The system of any one of claims 39-48, wherein the prefix tree generating means is configured to generate the prefix tree of terms by retaining the terms of a dictionary prefix tree which are allowed given the one or more features.

50. The system according to claim 49, wherein a term of the dictionary prefix tree may be retained even if a feature does not correspond to that term.

52. The system of claim 51 when dependent on claim 49 or 50, wherein the prefix tree of terms comprises one or more nodes representing the last letter of a completed word, wherein the prefix tree generating means is configured to insert a node corresponding to a space character into the prefix tree where there is a node corresponding to the last letter in a word

53. The system of claim 52, wherein the prefix tree generating means is configured to reduce the probability associated with the node corresponding to the space character, if the feature identification means has not identified a feature associated with that space character.

54. The system of claim 53, wherein the prefix tree generating means is configured to generate at the node corresponding to the space character, a new prefix tree of terms generated by retaining the terms of a dictionary prefix tree which are allowed given the remaining features in a sequence of one or more features.

55. The system of any one of claims 39 to 51, wherein the prefix tree generating means is configured to prune the prefix tree of terms to remove all paths through the graph for which the probability of the path is below a predetermined threshold.

56. The system of claim 54 or claim 55 when dependent on 54, wherein the prefix tree generating means is configured to associate meta-data with the node representing a space character to prune the new prefix tree of terms on the basis of context data.

57. The system of claim 51 when dependent on claim 49 or 50, wherein the prefix tree generating means is configured to allow a given feature to represent a repeated instance of the character is relates to, by retaining the terms of a dictionary prefix tree which include character repetition if there is a valid path given the one or more features through the prefix tree for this repeated character.

58. The system of any one of claims 39 to 57, wherein the path finding means is a path-finding algorithm.

59. The system of claim 58 when dependent on claim 48, wherein the path-finding algorithm is configured to use the distance metrics to generate a probability estimate associated with each path through the prefix tree of terms.

60. The system of claim 58 or 59, wherein the path-finding algorithm is configured to return as the one or more terms, terms for which the corresponding route has a probability estimate above a threshold value.

61. The system of any one of claims 39 to 57, wherein the feature identification means is configured to determine one or more features which correspond to the end location of the gesture, and the prefix tree generating means is configured to assign an indication of the cumulative probability for a given path to any node representing the one or more features that correspond to the location of the end of the gesture, only if that node corresponds to a leaf of the prefix tree of terms.

62. The system of claim 61, wherein the path finding means is configured to order the cumulative probabilities and to return as the one or more terms, terms for which the corresponding route has a cumulative probability estimate above a threshold value.

63. The system of any one of claims 39 to 62, wherein the predictor is configured to predict the one or more terms on the basis of all the currently available samples.

64. The system of claim 63, wherein the predictor is configured to periodically update the prediction for the one or more terms as the single continuous stroke is being performed and the sampling means generates more samples.

65. The system of any one of claims 39 to 64, wherein the predictor is configured to predict one or more words.

66. The system of claim 65, wherein the predictor is configured to predict the one or more words on the basis of a single continuous gesture which corresponds to the user gesturing over one or more characters on a gesture-sensitive keyboard intended to indicate the prefix for that word.

67. The system of claim 66, wherein the predictor is configured to predict a phrase comprising a sequence of two or more words on the basis of a single continuous gesture which corresponds to the user gesturing over characters for multiple words on a gesture-sensitive keyboard.

68. The system of claim 66 or 67, wherein the predictor is configured to use context information to tailor the prediction of one or more terms.

69. The system of any one of claims 39 to 68, wherein the sampling means is configured to sample at a predetermined frequency

70. The system of claim 69, wherein the sampling means samples at a frequency of about 60 Hz.

71. The system of any one of claims 39 to 70, wherein the predictor is configured to predict the one or more terms on the basis of the topography of the gesture-sensitive keyboard in combination with gesture velocity and/or gesture curve direction.

72. The system of claim 71, wherein the predictor is configured to predict a path through the prefix tree dependent on the topography of the gesture between two features and the targets of the keyboard associated with those two features.

73. The system of claim 72, wherein the probability of the path is based on a monotonically decreasing function of the difference between a straight-line distance between the two targets and the curved length of the gesture between the two targets.

74. The system of claim 73, wherein the probability of the path is based on a monotonically decreasing function of the difference between the direction of a straight-line between the two targets and the gesture direction at each point between the two targets.

75. The system of any one of claims 39 to 71, wherein the gesture-sensitive keyboard is a touch-sensitive keyboard and the single continuous gesture is a stroke across the touch-sensitive keyboard.

76. The system of claim 75, wherein the touch-sensitive keyboard is configured to detect pressure from a user stroking the touch-sensitive keyboard and the sampling means is configured to sample the location of the stroke at which pressure is present.

77. The method of claim 76, wherein the sampling means is configured to detect a pressure value and a location at a given time.

78. A system substantially as hereinbefore described with reference to and as shown in the accompanying drawings.

79. A method substantially as hereinbefore described with reference to and as shown in the accompanying drawings.