VIRTUAL KEYBOARD INPUT FOR INTERNATIONAL LANGUAGES

• US 20160026258A1
• Filed: 03/15/2013
• Published: 01/28/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: ZHANG, Yuanbo, OU, Liangyi, SU, Zhe, PAN, Jie, FU, Song, LI, Zhiheng, CHEN, Ruiyi, JUNG, Robert Stuart
• Granted Patent: US 10,073,536 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2203/04101 2.5D-digitiser, i.e. digitiser detecting the X/Y position of the input means, finger or stylus, also when it does not touch, but is proximate to the digitiser's interaction surface and also measures the distance of the input means within a short range in the Z direction, possibly with a separate measurement setup
• 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 2203/04808 Several contacts: gestures triggering a specific function, e.g. scrolling, zooming, right-click, when the user establishes several contacts with the surface simultaneously; e.g. using several fingers or a combination of fingers and pen
• CPC Class Codes: G06F 3/018 Input/output arrangements for oriental characters
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/044 by capacitive means
• 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

In one example, a computing device includes at least one processor configured to output for display, a graphical keyboard. The at least one processor may also be configured to model, in a first lattice, a plurality of candidate character strings that include symbols of a first alphabet. The first lattice may indicate spatial probabilities of the plurality of candidate character strings. The at least one processor may be configured to determine, using a second lattice that indicates probabilities of one or more words of a second language based at least in part on the spatial probabilities of the plurality of candidate character strings, a probability that the at least one of the plurality of candidate character strings corresponds to at least one word included in the second language. The at least one processor may be configured to output for display, the one or more symbols representing at least one word.

Claims

1. A computing device comprising at least one processor, wherein the at least one processor is configured to:

output for display, a graphical keyboard comprising a plurality of keys, wherein at least one of the plurality of keys is associated with one or more symbols that are included in a first alphabet of a first language;

in response to receiving an indication of at least one gesture detected at a presence-sensitive input device, model, in a first lattice, a plurality of candidate character strings that each include symbols of the first alphabet, wherein the first lattice indicates spatial probabilities of each of the plurality of candidate character strings, where the spatial probabilities are based at least in part on the indication of the at least one gesture;

determine for at least one of the plurality of candidate character strings, using a second lattice that indicates probabilities of one or more words of a second language based at least in part on the spatial probabilities of the plurality of candidate character strings, a probability that the at least one of the plurality of candidate character strings corresponds to at least one word included in the second language, wherein the at least one word is represented by one or more symbols of a second alphabet corresponding to the second language; and

in response to determining that the probability satisfies a threshold, output for display, the one or more symbols representing the at least one word.

2. The computing device of claim 1, wherein the at least one processor is configured to:

determine a group of characters included in a candidate character string of the plurality of candidate character strings;

determine spatial model probabilities of keys corresponding to characters included in the candidate character string;

determine a collective spatial model probability of the candidate character string based at least in part on the spatial model probabilities of keys corresponds to characters included in the candidate character string; and

determine an edge in the first lattice, wherein the candidate character string and the collective spatial model probability of the character string are associated with the edge.

3. The computing device of claim 1, wherein the indication of at least one gesture detected at the presence-sensitive input device further comprises a tap input, wherein the at least one processor is configured to:

determine spatial model probabilities of keys of the graphical keyboard that are proximal to a location of the tap input;

generate edges in a third lattice that each correspond to the keys of the graphical keyboard that are proximal to the location of the tap input;

associate with the edges, characters of the graphical keyboard that are proximal to the location of the tap input and respective spatial model probabilities of the keys the graphical keyboard that are proximal to the location of the tap input;

determine a plurality of edges in the third lattice; and

generate an edge in the first lattice that is associated with a candidate character string, wherein the candidate character string is generated based at least in part on the plurality of edges in the third lattice.

4. The computing device of claim 1, wherein the at least one processor is configured to:

determine that a first spatial model probability of a first candidate character string satisfies a threshold, wherein the first candidate character string corresponds to a first edge of the first lattice, wherein the first edge originates from a first vertex and ends at a second vertex;

determine that a second spatial model probability of a second candidate character string satisfies the threshold, wherein the second candidate character string corresponds to a second edge of the first lattice, wherein the second edge originates from the second vertex and ends at a third vertex; and

generate a third edge in the second lattice that indicates a probability of the at least one word included in the second language, based at least in part on the first spatial model probability and the second spatial model probability.

5. The computing device of claim 4, wherein the at least one processor is configured to:

concatenate the first candidate character string and the second candidate character string to generate a third candidate character string;

associate the third candidate character string with the third edge in the second lattice; and

determine the probability of the third candidate character string given the word in the second language.

6. The computing device of claim 1, wherein the indication of at least one gesture detected at the presence-sensitive input device further comprises a continuous gesture input, wherein the at least one processor is configured to:

determine, in response to receiving the indication of at least one gesture, a candidate character string based at least in part on a group of keys, wherein the determining comprises;

determine a group of alignment points traversed by 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 probability that an alignment point of the group of alignment points indicates a key of the plurality of keys;

in response to determining that the cost value of a combination of keys satisfies a threshold, associate, by the computing device, a candidate character string with an edge of the first lattice, wherein the character string includes characters associated with the combination of keys.

7. The computing device of claim 1, wherein the at least one processor is configured to:

determine a plurality of characters in response to receiving an indication of at least one gesture detected at a presence-sensitive input device;

determine at least one boundary between the plurality of characters, wherein the at least one boundary indicates a first group of characters in the plurality of characters that correspond to a first candidate character string and a second group of characters in the plurality of characters that correspond to a second candidate character string;

generate a first edge in the first lattice that is associated with the first candidate character string, wherein the first edge originates from a first vertex and ends at a second vertex;

generate a second edge in the first lattice that is associated with the second candidate character string, wherein the second edge originates from the second vertex and ends at a third vertex; and

determine the probability of the first candidate character string and the second candidate character string given the word in the second language.

8. A computer-readable storage medium encoded with instructions that, when executed, cause at least one processor to:

output for display, a graphical keyboard comprising a plurality of keys, wherein at least one of the plurality of keys is associated with one or more symbols that are included in a first alphabet of a first language;

in response to receiving an indication of at least one gesture detected at a presence-sensitive input device, model, in a first lattice, a plurality of candidate character strings that each include symbols of the first alphabet, wherein the first lattice indicates spatial probabilities of each of the plurality of candidate character strings, where the spatial probabilities are based at least in part on the indication of the at least one gesture;

determine for at least one of the plurality of candidate character strings, using a second lattice that indicates probabilities of one or more words of a second language based at least in part on the spatial probabilities of the plurality of candidate character strings, a probability that the at least one of the plurality of candidate character strings corresponds to at least one word included in the second language, wherein the at least one word is represented by one or more symbols of a second alphabet corresponding to the second language; and

in response to determining that the probability satisfies a threshold, output for display, the one or more symbols representing the at least one word.

9. The computer-readable storage medium of claim 8, encoded with instructions that, when executed, cause at least one processor to:

determine a group of characters included in a candidate character string of the plurality of candidate character strings;

determine spatial model probabilities of keys corresponding to characters included in the candidate character string;

determine a collective spatial model probability of the candidate character string based at least in part on the spatial model probabilities of keys corresponds to characters included in the candidate character string; and

determine an edge in the first lattice, wherein the candidate character string and the collective spatial model probability of the character string are associated with the edge.

10. The computer-readable storage medium of claim 8, wherein the indication of at least one gesture detected at the presence-sensitive input device further comprises a tap input, wherein the computer-readable storage medium is encoded with instructions that, when executed:

determine spatial model probabilities of keys of the graphical keyboard that are proximal to a location of the tap input;

generate edges in a third lattice that each correspond to the keys of the graphical keyboard that are proximal to the location of the tap input;

associate with the edges, characters of the graphical keyboard that are proximal to the location of the tap input and respective spatial model probabilities of the keys the graphical keyboard that are proximal to the location of the tap input;

determine a plurality of edges in the third lattice; and

generate an edge in the first lattice that is associated with a candidate character string, wherein the candidate character string is generated based at least in part on the plurality of edges in the third lattice.

11. The computer-readable storage medium of claim 8, encoded with instructions that, when executed, cause at least one processor to:

determine that a first spatial model probability of a first candidate character string satisfies a threshold, wherein the first candidate character string corresponds to a first edge of the first lattice, wherein the first edge originates from a first vertex and ends at a second vertex;

determine that a second spatial model probability of a second candidate character string satisfies the threshold, wherein the second candidate character string corresponds to a second edge of the first lattice, wherein the second edge originates from the second vertex and ends at a third vertex; and

generate a third edge in the second lattice that indicates a probability of the at least one word included in the second language, based at least in part on the first spatial model probability and the second spatial model probability.

12. The computer-readable storage medium of claim 11, encoded with instructions that, when executed, cause at least one processor to:

concatenate the first candidate character string and the second candidate character string to generate a third candidate character string;

associate the third candidate character string with the third edge in the second lattice; and

determine the probability of the third candidate character string given the word in the second language.

13. The computer-readable storage medium of claim 8, wherein the indication of at least one gesture detected at the presence-sensitive input device further comprises a continuous gesture input, wherein the computer-readable storage medium is encoded with instructions that, when executed:

determine, in response to receiving the indication of at least one gesture, a candidate character string based at least in part on a group of keys, wherein the determining comprises;

determine a group of alignment points traversed by 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 probability that an alignment point of the group of alignment points indicates a key of the plurality of keys;

in response to determining that the cost value of a combination of keys satisfies a threshold, associate, by the computing device, a candidate character string with an edge of the first lattice, wherein the character string includes characters associated with the combination of keys.

14. The computer-readable storage medium of claim 8, encoded with instructions that, when executed, cause at least one processor to:

determine a plurality of characters in response to receiving an indication of at least one gesture detected at a presence-sensitive input device;

determine at least one boundary between the plurality of characters, wherein the at least one boundary indicates a first group of characters in the plurality of characters that correspond to a first candidate character string and a second group of characters in the plurality of characters that correspond to a second candidate character string;

generate a first edge in the first lattice that is associated with the first candidate character string, wherein the first edge originates from a first vertex and ends at a second vertex;

generate a second edge in the first lattice that is associated with the second candidate character string, wherein the second edge originates from the second vertex and ends at a third vertex; and

determine the probability of the first candidate character string and the second candidate character string given the word in the second language.

15. A method comprising:

outputting, by a computing device and for display, a graphical keyboard comprising a plurality of keys, wherein at least one of the plurality of keys is associated with one or more symbols that are included in a first alphabet of a first language;

in response to receiving an indication of at least one gesture detected at a presence-sensitive input device, modeling, in a first lattice, a plurality of candidate character strings that each include symbols of the first alphabet, wherein the first lattice indicates spatial probabilities of each of the plurality of candidate character strings, where the spatial probabilities are based at least in part on the indication of the at least one gesture;

determining for at least one of the plurality of candidate character strings, using a second lattice that indicates probabilities of one or more words of a second language based at least in part on the spatial probabilities of the plurality of candidate character strings, a probability that the at least one of the plurality of candidate character strings corresponds to at least one word included in the second language, wherein the at least one word is represented by one or more symbols of a second alphabet corresponding to the second language; and

in response to determining that the probability satisfies a threshold, outputting, by the computing device and for display, the one or more symbols representing the at least one word.

16. The method of claim 15, wherein modeling, in the first lattice, the plurality of character strings that each includes symbols of the first alphabet further comprises:

determining, by the computing device, a group of characters included in a candidate character string of the plurality of candidate character strings;

determining, by the computing device, spatial model probabilities of keys corresponding to characters included in the candidate character string;

determining, by the computing device, a collective spatial model probability of the candidate character string based at least in part on the spatial model probabilities of keys corresponds to characters included in the candidate character string; and

generating, by the computing device, an edge in the first lattice, wherein the candidate character string and the collective spatial model probability of the character string are associated with the edge.

17. The method of claim 15, wherein the indication of at least one gesture detected at the presence-sensitive input device further comprises a tap input, the method further comprising:

determining, by the computing device, spatial model probabilities of keys of the graphical keyboard that are proximal to a location of the tap input;

generating, by the computing device, edges in a third lattice that each correspond to the keys of the graphical keyboard that are proximal to the location of the tap input;

associating, by the computing device and with the edges, characters of the graphical keyboard that are proximal to the location of the tap input and respective spatial model probabilities of the keys the graphical keyboard that are proximal to the location of the tap input;

determining, by the computing device, a plurality of edges in the third lattice; and

generating, by the computing device, an edge in the first lattice that is associated with a candidate character string, wherein the candidate character string is generated based at least in part on the plurality of edges in the third lattice.

18. The method of claim 15, further comprising:

determining, by the computing device, that a first spatial model probability of a first candidate character string satisfies a threshold, wherein the first candidate character string corresponds to a first edge of the first lattice, wherein the first edge originates from a first vertex and ends at a second vertex;

determining, by the computing device, that a second spatial model probability of a second candidate character string satisfies the threshold, wherein the second candidate character string corresponds to a second edge of the first lattice, wherein the second edge originates from the second vertex and ends at a third vertex; and

generating, by the computing device a third edge in the second lattice that indicates a probability of the at least one word included in the second language, based at least in part on the first spatial model probability and the second spatial model probability.

19. The method of claim 18, further comprising:

concatenating, by the computing device, the first candidate character string and the second candidate character string to generate a third candidate character string;

associating, by the computing device the third candidate character string with the third edge in the second lattice; and

determining, by the computing device, the probability of the third candidate character string given the word in the second language.

20. The method of claim 15, wherein the indication of at least one gesture detected at the presence-sensitive input device further comprises a continuous gesture input, the method further comprising:

determining, by the computing device and in response to receiving the indication of at least one gesture, a candidate character string based at least in part on a group of keys, wherein the determining comprises;

determining, by the computing device, a group of alignment points traversed by 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 probability that an alignment point of the group of alignment points indicates a key of the plurality of keys;

in response to determining that the cost value of a combination of keys satisfies a threshold, associating, by the computing device, a candidate character string with an edge of the first lattice, wherein the character string includes characters associated with the combination of keys.

21. The method of claim 15, further comprising:

determining, by the computing device, a plurality of characters in response to receiving an indication of at least one gesture detected at a presence-sensitive input device;

determining, by the computing device, at least one boundary between the plurality of characters, wherein the at least one boundary indicates a first group of characters in the plurality of characters that correspond to a first candidate character string and a second group of characters in the plurality of characters that correspond to a second candidate character string;

generating, by the computing device a first edge in the first lattice that is associated with the first candidate character string, wherein the first edge originates from a first vertex and ends at a second vertex;

generating, by the computing device a second edge in the first lattice that is associated with the second candidate character string, wherein the second edge originates from the second vertex and ends at a third vertex; and

determining, by the computing device, the probability of the first candidate character string and the second candidate character string given the word in the second language.