System and method for inputting text

• US 10,613,746 B2
• Filed: 12/22/2016
• Issued: 04/07/2020
• 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, Pei Yong
• Application Number:
  US15/389,294
• Publication Number:
  US 20170102869A1
• Time in Patent Office: 1,202 Days
• 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 comprising a feature identification means configured to generate one or more features from a plurality of samples, wherein each of the plurality of samples 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 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 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. A corresponding method is also provided.

Claims

1. A system comprising:

a processor;

memory storing instructions that, when executed by the processor, cause the system to perform operations comprising;

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 the one or more features relates to one of a plurality of targets of the gesture sensitive keyboard indicative of a user intended input based on the gesture;

generate a prefix tree of terms which includes the one or more features based on the single continuous gesture;

select one or more paths through the prefix tree of terms given the one or more features based on a distance between the one or more features and the one of the plurality of targets; and

predict one or more terms corresponding to the single continuous gesture from the one or more features.

2. The system of claim 1, wherein the instructions further cause the system 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 further cause the system to generate said one or more features from the plurality of samples by identifying a location of the gesture on the gesture-sensitive keyboard indicative of a gesture intended to pass through a target of the gesture-sensitive keyboard.

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

5. The system of claim 1, wherein the instructions further cause the system to identify a feature for plurality of targets.

6. The system of claim 1, wherein the instructions further cause the system to retain a feature only if the minimum distance between the feature and the one of the plurality of targets 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 is retained when a feature does not correspond to the term.

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

the prefix tree of terms comprises one or more nodes representing a last latter of a completed word; and

the instructions further cause the system to insert a node corresponding to a word boundary delimiter into the prefix tree where there is a node corresponding to the last letter in the completed word.

10. The system of claim 9, wherein the instructions further cause the system to reduce a probability associated with a 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 10, 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 further cause the system to associate metadata 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 letters of the alphabet or word boundary delimiters, wherein the instructions further cause the system 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 the repeated character.

14. The system of claim 1, wherein the instructions further cause the system to prune the prefix tree of terms to remove paths through a graph for which a 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 one of the plurality of targets and wherein the instructions further cause the system 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 further cause the system to return as the one or more terms, terms for which a corresponding route has a probability estimate above a threshold value.

17. The system of claim 1, wherein the instructions further cause the system to:

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

assign an indication of a cumulative probability for a given path to any node representing the one or more features that correspond to the location of an 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 currently available samples.

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

20. The system of claim 1, wherein the instructions further cause the system 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 further cause the system to predict a phrase comprising a sequence of two or more words on the basis of a single continuous gesture which corresponds to gesturing over characters for multiple words on a gesture-sensitive keyboard.

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

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

24. The system of claim 1, wherein the instructions further cause the system to predict a path through the prefix tree dependent on a topography of the gesture between two features and targets of the keyboard associated with those two features.

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

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

27. 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 a 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 the one or more features relates to a target on the gesture-sensitive keyboard indicative of an input based on the gesture;

generating a prefix tree of terms which includes the one or more features based on the single continuous gesture; and

selecting one or more paths through the prefix tree of terms given the one or more features based on a distance between the one or more features and the target to predict one or more terms corresponding to the single continuous gesture.