System and method for inputting text

• US 9,563,348 B2
• Filed: 11/30/2012
• Issued: 02/07/2017
• 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
• Primary Examiner(s): Weng, Peiyong
• Application Number:
  US14/372,445
• Publication Number:
  US 20140359515A1
• Time in Patent Office: 1,530 Days
• US Class Current: 1/1
• 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 system comprising:

a processor;

memory storing instructions that, when executed by the processor, configure the processor to;

sample at a plurality of times a location of a single continuous gesture on a gesture-sensitive keyboard as the gesture is being performed;

generate one or more features from the plurality of samples, 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;

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

find one or more paths through the prefix tree of terms given the one or more features;

predict one or more terms from the one or more features; and

insert a node corresponding to a word boundary delimiter into the prefix tree where there is a node corresponding to the last letter in a word.

2. The system of claim 1, wherein the instructions configure the processor to generate a graph by graph theory, wherein the graph represents the prefix tree of terms.

3. The system of claim 1, wherein the instructions configure the processor to generate said 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.

4. The system of claim 1, wherein the target is a point target or a line target.

5. The system of claim 1, wherein the instructions configure the processor to identify a feature for each of the plurality of targets.

6. The system of claim 1, wherein the instructions configure the processor to retain a feature only if the minimum distance between the feature and the target is below a threshold distance.

7. The system of claim 1, 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.

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

9. The system of claim 8, wherein the plurality of targets correspond to the letters of the alphabet, and.

10. The system of claim 9, wherein the instructions configure the processor to reduce the probability associated with the node corresponding to the word boundary delimiter, if a feature associated with that word boundary delimiter has not been identified.

11. The system of claim 9, wherein a new prefix tree of terms is generated at the node corresponding to the word boundary delimiter by retaining the terms of a dictionary prefix tree which are allowed given the remaining features in a sequence of one or more features.

12. The system of claim 11, wherein the instructions configure the processor to associate meta-data with the node representing a word boundary delimiter to prune the new prefix tree of terms on the basis of context data.

13. The system of claim 12, 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 and wherein instructions configure the processor to allow 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.

14. The system of claim 1, wherein the instructions configure the processor 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.

15. The system of claim 1, wherein each feature comprises a distance metric which corresponds to the minimum distance between the gesture and the target and wherein the instructions configure the processor to use the distance metrics to generate a probability estimate associated with each path through the prefix tree of terms.

16. The system of claim 15, wherein the instructions configure the processor to return as the one or more terms, terms for which the corresponding route has a probability estimate above a threshold value.

17. The system of claim 1, wherein the instructions configure the processor to determine one or more features which correspond to the end location of the gesture, and 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.

18. The system of claim 1, wherein the one or more terms is predicted on the basis of all the currently available samples.

19. The system of claim 1, wherein the instructions configure the processor to periodically update the prediction for the one or more terms as the single continuous stroke is being performed and more samples are generated.

20. The system of claim 1, wherein the instructions configure the processor to predict 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 one or more word.

21. The system of claim 1, wherein the instructions configure the processor 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.

22. The system of claim 1, wherein the instructions configure the processor to use context information to tailor the prediction of one or more terms.

23. The system of claim 1, wherein the instructions configure the processor to predict the one or more terms on the basis of the topography of the gesture-sensitive keyboard in combination with at least one of the group comprising gesture velocity and gesture curve direction.

24. The system of claim 1, wherein the instructions configure the processor 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.

25. The system of claim 24, 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.

26. The system of claim 24, 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.

27. The system of claim 1, wherein the gesture-sensitive keyboard is a touch-sensitive keyboard, the single continuous gesture is a stroke across the touch-sensitive keyboard, and wherein the touch-sensitive keyboard is configured to detect pressure from a user stroking the touch-sensitive keyboard and the instructions configure the processor to sample a pressure value and the location of the stroke at a given time.

28. 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; and

inserting a node corresponding to a word boundary delimiter into the prefix tree when there is a node corresponding to the last letter in a word.

29. The method of claim 28, 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 and a term of the dictionary prefix tree may be retained even if a feature does not correspond to that term.

30. The method of claim 28, wherein the targets of the gesture-sensitive keyboard correspond to letters of the alphabet, and the word boundary delimiters comprise a space or punctuation symbols.

31. The method of claim 30, wherein generating the prefix tree of terms further comprises generating at the node corresponding to the word boundary delimiter, 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.

32. The method of claim 28, wherein, predicting the one or more terms comprises predicting 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.

33. The method of claim 28, wherein predicting the one or more terms 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.

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

35. The method of claim 28, wherein the prediction of the one or more terms is based on the topography of the gesture between two features and the targets of the keyboard associated with those two features.

36. A non-transient computer readable medium containing program instructions which, when executed by a processor, configure the processor to:

sample at a plurality of times a location of a single continuous gesture on a gesture-sensitive keyboard as the gesture is being performed;

generate one or more features from the plurality of samples, 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;

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

find one or more paths through the prefix tree of terms given the one or more features;

predict one or more terms from the one or more features; and

insert a node corresponding to a word boundary delimiter into the prefix tree when a node corresponding to the last letter in a word is identified.