Incremental feature-based gesture-keyboard decoding

• US 9,552,080 B2
• Filed: 07/14/2014
• Issued: 01/24/2017
• Est. Priority Date: 10/05/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ouyang, Yu, Zhai, Shumin, Chelba, Ciprian Ioan, Bi, Xiaojun, Kataoka, Satoshi, Wakasa, Ken, Kuroyanagi, Keisuke
• Primary Examiner(s): BHARGAVA, ANIL K
• Application Number:
  US14/331,137
• Publication Number:
  US 20140344748A1
• Time in Patent Office: 925 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0236 using selection techniques to select from displayed items
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/0484 for the control of specific functions or operations, e.g. selecting or manipulating an object, an image or a displayed text element, setting a parameter value or selecting a range
• 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/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

In one example, a method includes outputting, at a presence-sensitive display operatively coupled to a computing device, a graphical keyboard comprising a plurality of keys and receiving an indication of a gesture to select a group of keys of the plurality of keys. The method may further include determining, in response to the indication, a candidate word based at least in part on the group of keys. The method may further include determining a group of alignment points traversed by the gesture and respective cost values for each of at least two keys of the plurality of keys. The method may further include comparing the respective cost values for at least each of at least two keys of the plurality of keys to determine a combination of keys having a combined cost value and outputting the candidate word that is based on the respective cost values.

Claims

1. A method comprising:

outputting, by a computing device and for display, a graphical keyboard comprising a plurality of keys;

maintaining, by the computing device, a plurality of letter chains, wherein;

each respective letter chain of the plurality of letter chains is associated with a respective cost value;

each respective letter chain includes a different respective group of one or more characters; and

each respective character of each respective group of one or more characters corresponds to a respective key of the plurality of keys;

receiving an indication of a particular portion of a gesture detected at a presence-sensitive input device, the gesture comprising a plurality of portions;

responsive to receiving the indication of the particular portion of the gesture, updating, by the computing device, based at least in part on the indication of the particular portion of the gesture, the plurality of letter chains;

determining, by the computing device, for the particular portion of the gesture and based at least in part on a cost value associated with at least one of the plurality of letter chains, a candidate word; and

outputting, by the computing device, for display, the candidate word.

2. The method of claim 1, wherein determining the candidate word further comprises:

determining, by the computing device, a group of one or more alignment points traversed by the particular portion of the gesture;

determining, by the computing device, respective cost values for each of at least two keys of the plurality of keys, wherein each of the respective cost values represents a respective probability that a respective alignment point of the group of alignment points indicates a respective key of the plurality of keys;

updating, by the computing device and based at least in part on at least one of the respective cost values for one or more of the at least two keys, the cost value associated with the at least one of the plurality of letter chains; and

comparing, by the computing device, the respective combined cost values respectively associated with the plurality of letter chains to select the candidate word for outputting for display.

3. The method of claim 2, wherein determining the respective cost values for each of the at least two keys of the plurality of keys further comprises:

determining, by the computing device, a first cost value for a first key of the plurality of keys based on a first alignment point of the group of alignment points and a second cost value for a second key of the plurality of keys based on a second alignment point of the group of alignment points.

4. The method of claim 2, wherein determining the respective cost values for each of the at least two keys of the plurality of keys comprises:

determining respective physical cost values for each of the at least two keys of the plurality of keys, wherein each of the respective physical cost values represents a probability that at least one physical feature of an alignment point of the group of alignment points indicates at least one physical feature of a key of the plurality of keys;

determining respective lexical cost values for each of the at least two keys of the plurality of keys, wherein each of the respective lexical cost values represents a probability that a character represented by a key of the plurality of keys is included in the candidate word; and

determining, based at least in part on the respective physical cost values and the respective lexical cost values, the respective cost values for each of the at least two keys of the plurality of keys.

5. The method of claim 4, comprising:

weighting, by the computing device, the respective physical cost values differently than the respective lexical cost values.

6. The method of claim 1, wherein the cost value associated with the at least one of the plurality of letter chains is a combined cost value that is based at least in part on a plurality of cost values.

7. The method of claim 1, wherein the gesture is a continuous gesture, the method further comprising:

determining, by the computing device and based at least in part on a plurality of features associated with the particular portion of the continuous gesture, a group of alignment points traversed by the continuous gesture,

wherein the plurality of features associated with the particular portion of the continuous gesture comprises at least one of;

a length of a segment of the particular portion of the continuous gesture, wherein the segment comprises a path traversed by the particular portion of the continuous gesture at the presence-sensitive input device;

a direction of the segment of the particular portion of the continuous gesture;

a curvature of the segment of the particular portion of the continuous gesture;

a local speed that represents a rate at which the segment of the particular portion of the continuous gesture was detected; and

a global speed that represents a rate at which the particular portion of the continuous gesture was detected.

8. The method of claim 1,

wherein the gesture comprises a plurality of tap gestures;

and

wherein the particular portion of the gesture comprises a tap gesture in the plurality of tap gestures.

9. A computing device comprising:

at least one processor; and

at least one module operable by the at least one processor to;

output, for display, a graphical keyboard comprising a plurality of keys;

maintain a plurality of letter chains, wherein;

each respective letter chain of the plurality of letter chains is associated with a respective cost value;

each respective letter chain includes a different respective group of one or more characters; and

each respective character of each respective group of one or more characters corresponds to a respective key of the plurality of keys;

receive an indication of a particular portion of a gesture detected at a presence-sensitive input device, the gesture comprising a plurality of portions;

responsive to receiving the indication of the particular portion of the gesture, update, based at least in part on the indication of the particular portion of the gesture, the plurality of letter chains;

determine, for the particular portion of the gesture and based at least in part on a cost value associated with at least one of the plurality of letter chains, a candidate word; and

output, for display, the candidate word.

10. The computing device of claim 9, wherein the at least one module is operable by the at least one processor to:

determine a group of one or more alignment points traversed by the particular portion of the gesture;

determine respective cost values for each of at least two keys of the plurality of keys, wherein each of the respective cost values represents a respective probability that a respective alignment point of the group of alignment points indicates a respective key of the plurality of keys;

update, based at least in part on at least one of the respective cost values for one or more of the at least two keys, the cost value associated with the at least one of the plurality of letter chains; and

comparing, by the computing device, the respective combined cost values respectively associated with the plurality of letter chains to select the candidate word for outputting for display.

11. The computing device of claim 9, wherein the at least one module is operable by the at least one processor to:

determine a first cost value for a first key of the plurality of keys based on a first alignment point of the group of alignment points and a second cost value for a second key of the plurality of keys based on a second alignment point of the group of alignment points.

12. The computing device of claim 9, wherein the at least one module is operable by the at least one processor to:

determine respective physical cost values for each of the at least two keys of the plurality of keys, wherein each of the respective physical cost values represents a probability that at least one physical feature of an alignment point of the group of alignment points indicates at least one physical feature of a key of the plurality of keys;

determine respective lexical cost values for each of the at least two keys of the plurality of keys, wherein each of the respective lexical cost values represents a probability that a character represented by a key of the plurality of keys is included in the candidate word; and

determine, based at least in part on the respective physical cost values and the respective lexical cost values, the respective cost values for each of the at least two keys of the plurality of keys.

13. The computing device of claim 12, wherein the at least one module is operable by the at least one processor to:

weight the respective physical cost values differently than the respective lexical cost values.

14. The computing device of claim 9, wherein the cost value associated with the at least one of the plurality of letter chains is a combined cost value that is based at least in part on a plurality of cost values.

15. The computing device of claim 9, wherein the gesture is a continuous gesture, wherein the at least one module is operable by the at least one processor to:

determine, based at least in part on a plurality of features associated with the particular portion of the continuous gesture, a group of alignment points traversed by the continuous gesture,

wherein the plurality of features associated with the particular portion of the continuous gesture comprises at least one of;

a length of a segment of the particular portion of the continuous gesture, wherein the segment comprises a path traversed by the portion of the continuous gesture at the presence-sensitive input device;

a direction of the segment of the particular portion of the continuous gesture;

a curvature of the segment of the particular portion of the continuous gesture;

a local speed that represents a rate at which the segment of the particular portion of the continuous gesture was detected; and

a global speed that represents a rate at which the particular portion of the continuous gesture was detected.

16. The computing device of claim 9,

wherein the gesture comprises a plurality of tap gestures;

and

wherein the particular portion of the gesture comprises a tap gesture in the plurality of tap gestures.

17. A non-transitory computer-readable storage medium encoded with instructions that, when executed, cause at least one processor of a computing device to:

output, for display, a graphical keyboard comprising a plurality of keys;

maintain a plurality of letter chains, wherein;

each respective letter chain of the plurality of letter chains is associated with a respective cost value;

each respective letter chain includes a different respective group of one or more characters; and

each respective character of each respective group of one or more characters corresponds to a respective key of the plurality of keys;

receive an indication of a particular portion of a gesture detected at a presence-sensitive input device, the gesture comprising a plurality of portions;

responsive to receiving the indication of the particular portion of the gesture, update, based at least in part on the indication of the particular portion of the gesture, the plurality of letter chains;

determine, for the particular portion of the gesture and based at least in part on a cost value associated with at least one of the plurality of letter chains, a candidate word; and

output, for display, the candidate word.

18. The non-transitory computer-readable storage medium of claim 17, encoded with instructions that, when executed, cause the at least one processor of the computing device to:

determine a group of one or more alignment points traversed by the particular portion of the gesture;

determine respective cost values for each of at least two keys of the plurality of keys, wherein each of the respective cost values represents a respective probability that a respective alignment point of the group of alignment points indicates a respective key of the plurality of keys;

update, based at least in part on at least one of the respective cost values for one or more of the at least two keys, the cost value associated with the at least one of the plurality of letter chains; and

comparing, by the computing device, the respective combined cost values respectively associated with the plurality of letter chains to select the candidate word for outputting for display.

19. The non-transitory computer-readable storage medium of claim 17, encoded with instructions that, when executed, cause the at least one processor of the computing device to:

determine a first cost value for a first key of the plurality of keys based on a first alignment point of the group of alignment points and a second cost value for a second key of the plurality of keys based on a second alignment point of the group of alignment points.

20. The non-transitory computer-readable storage medium of claim 17, wherein the gesture is a continuous gesture, wherein the non-transitory computer-readable storage medium is encoded with instructions that, when executed, cause the at least one processor of the computing device to:

determine, based at least in part on a plurality of features associated with the particular portion of the continuous gesture, a group of alignment points traversed by the continuous gesture,

wherein the plurality of features associated with the particular portion of the continuous gesture comprises at least one of;

a length of a segment of the particular portion of the continuous gesture, wherein the segment comprises a path traversed by the particular portion of the continuous gesture at the presence-sensitive input device;

a direction of the segment of the particular portion of the continuous gesture;

a curvature of the segment of the particular portion of the continuous gesture;

a local speed that represents a rate at which the segment of the particular portion of the continuous gesture was detected; and

a global speed that represents a rate at which the particular portion of the continuous gesture was detected.

21. The non-transitory computer-readable storage medium of claim 17,

wherein the gesture comprises a plurality of tap gestures;

and

wherein the particular portion of the gesture comprises a tap gesture in the plurality of tap gestures.