Virtual keyboard system with automatic correction

• US 20050169527A1
• Filed: 12/20/2004
• Published: 08/04/2005
• Est. Priority Date: 05/26/2000
• Status: Active Grant

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AOL LLC (Apollo Global Management, Inc.)
• Inventors: Longe, Michael R., van Meurs, Pim
• Granted Patent: US 7,030,863 B2
• Time in Patent Office: Days
• US Class Current: 382/177
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/0238 Programmable keyboards key guide holders G06F3/0224
• 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/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 3/0489 using dedicated keyboard keys or combinations thereof
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

There is disclosed an enhanced text entry system which uses word-level analysis to correct inaccuracies automatically in user keystroke entries on reduced-size or virtual keyboards. A method and system are defined which determine one or more alternate textual interpretations of each sequence of inputs detected within a designated auto-correcting region. The actual interaction locations for the keystrokes may occur outside the boundaries of the specific keyboard key regions associated with the actual characters of the word interpretations proposed or offered for selection, where the distance from each interaction location to each corresponding intended character may in general increase with the expected frequency of the intended word in the language or in a particular context. Likewise, in a virtual keyboard system, the keys actuated may differ from the keys actually associated with the letters of the word interpretations. Each such sequence corresponds to a complete word, and the user can easily select the intended word from among the generated interpretations. Additionally, when the system cannot identify a sufficient number of likely word interpretation candidates of the same length as the input sequence, candidates are identified whose initial letters correspond to a likely interpretation of the input sequence.

Claims

1. A text entry system comprising:

a user input device comprising a virtual keyboard including an auto-correcting region comprising a plurality of the characters of an alphabet, wherein one or more of the plurality of characters corresponds to a location with known coordinates in the auto-correcting region, wherein a location associated with the user interaction is determined when a user interacts with the user input device within the auto-correcting region, and the determined interaction location is added to a current input sequence of interaction locations;

a memory containing a plurality of objects, wherein one or more objects comprise a string of one or a plurality of characters forming a word or a part of a word;

an output device; and

a processor coupled to the user input device, memory, and output device, said processor comprising;

a distance value calculation component which, for a determined interaction location in the input sequence of interactions, calculates a set of distance values between the interaction locations and the known coordinate locations corresponding to one or a plurality of characters within the auto-correcting region;

a word evaluation component which, for a generated input sequence, identifies one or a plurality of candidate objects in memory, and for one or more identified candidate objects, evaluates identified candidate objects by calculating a matching metric based on the calculated distance and ranks the evaluated candidate objects based on the calculated matching metric values; and

a selection component for identifying one or a plurality of candidate objects according to their evaluated ranking, presenting the identified objects to the user, and enabling the user to select one of the presented objects for output to the output device.

2. The system of claim 1, wherein:

one or more of the plurality of objects in memory is further associated with one or a plurality of predefined groupings of objects; and

the word evaluation component, for a generated input sequence, limits the number of objects for which a matching metric is calculated by identifying one or a plurality of candidate groupings of the objects in memory, and for one or a plurality of objects associated with one or more of identified candidate groupings of objects, calculates a matching metric based on the calculated distance values and ranks the evaluated candidate objects based on the calculated matching metric values.

3. The system of claim 1, wherein the characters of the alphabet are arranged on the auto-correcting region in approximately a standard QWERTY layout.

4. The system of claim 1, wherein said auto-correcting region comprises one or a plurality of known locations associated with one or a plurality of punctuation characters and/or diacritic marks, wherein said memory includes one or a plurality of objects in memory which include one or a plurality of the punctuation characters and/or diacritic marks associated with locations in said auto-correcting region.

5. The system of claim 1, wherein objects in memory are further associated with one or a plurality of modules, wherein each module comprises or generates a set of objects with one or a plurality of common characteristics.

6. The system of claim 1, wherein the word evaluation component calculates the matching metric for each candidate object by summing the distance values calculated from each interaction location in the input sequence to the location assigned to the character in the corresponding position of the candidate object.

7. The system of claim 1, further comprising the step of:

applying a weighting function according to a frequency of use associated with the object.

8. The system of claim 6, wherein one or more locations on the auto-correcting region is defined by a horizontal and a vertical coordinate, and wherein the distance value between an interaction location and the known coordinate location corresponding to a character comprises a horizontal and a vertical component, wherein at least one of said horizontal and vertical components is adjusted by a weighting factor in calculating the distance of the interaction location from the character.

9. The system of claim 7, wherein the frequency of use associated with a candidate object in memory comprises an ordinal ranking of the object with respect to other objects in memory.

10. The system of claim 6, wherein the word evaluation component adds an increment value to a sum of the distance values prior to applying a weighting function according to the frequency of use associated with the candidate object.

11. The system of claim 2, wherein objects in memory are stored such that objects are classified into groupings comprising objects of the same length.

12. The system of claim 11, wherein the word evaluation component limits a number of objects for which a matching metric is calculated by identifying candidate groupings of objects of the same length as the number of inputs in the input sequence.

13. The system of claim 6, wherein for a calculated distance value between an interaction location in the input sequence and a known coordinate location corresponding to a character within the auto-correcting region, in which said calculated distance exceeds a threshold distance value, for one or more objects in memory in which said character occurs at a position in the sequence of the characters of said object that corresponds to the position of said interaction location in said input sequence, said object is ranked by the word evaluation component as an object that is excluded from presentation to the user for selection.

14. The system of claim 2, wherein one or a plurality of the identified candidate groupings of the objects in memory comprise objects that are excluded from presentation to the user for selection, wherein at least one of the calculated distance values included in a calculated sum of distance values for each object in said one or identified candidate groupings of objects exceeds a threshold distance value.

15. The system of claim 1, wherein for a character corresponding to a known location in the auto-correcting region, a region is predefined around one or a plurality of said known locations, wherein the distance between an input interaction location falling within said predefined region and the known character location within said predefined region is calculated as a distance of zero.

16. The system of claim 1, wherein at least one of the locations with known coordinates in the auto-correcting region corresponds to a plurality of characters, one or a plurality of which comprise various diacritic marks, wherein the plurality of characters comprise variant forms of a single base character, and wherein objects in memory are stored with their correct accented characters.

17. The system of claim 1, wherein the selection component presents an identified one or a plurality of candidate objects for selection by a user in a candidate object list.

18. The system of claim 17, wherein the selection component identifies a highest ranked candidate object and presents the identified object in the first position of the candidate object list.

19. The system of claim 1, wherein a user selection of a character that is associated with an interaction outside of the auto-correcting region accepts and outputs a determined object prior to outputting said character.

20. The system of claim 1, wherein user selection of an object for output terminates a current input sequence such that a next interaction within the auto-correcting region starts a new input sequence.

21. The system of claim 1, wherein selection of a candidate may be through an alternate input modality.

22. The system of claim 1, wherein user inputs for the current input sequence may be through a combination of different modalities.

23. The system of claim 1, wherein correction of user entry errors employs an alternate input modality.

24. The system of claim 1, wherein the selection component detects a distinctive manner of selection that is used to select a candidate object, and wherein upon detecting that an object has been selected through said distinctive manner, the system replaces a current input sequence of actual interaction locations with an input sequence of interaction locations corresponding to the coordinate locations of the characters comprising the selected object, and wherein a next interaction in the auto-correcting region is appended to the current input sequence.

25. The system of claim 24, wherein said distinctive manner of selection eliminates all candidates except those candidates that incorporate said selected object.

26. The system of claim 1, wherein a distinctive manner of selection effects selection and/or editing of a word in a predicted/accepted phrase or sentence.

27. The system of claim 1, wherein the word evaluation component determines, for a determined interaction location in an input sequence of interaction locations, a closest known location corresponding to a character, and constructs an exact typing object composed of said determined corresponding characters in an order corresponding to the input sequence of interaction locations.

28. The system of claim 27, further comprising:

means for providing visual feedback of the exact typing object'"'"'s letter tracking.

29. The system of claim 28, further comprising:

means for providing proportional scaling to improve accuracy.

30. The system of claim 1, wherein the selection component identifies a highest ranked candidate object and presents the identified object on the output device.

31. The system of claim 30, wherein the text entry system comprises a region that is associated with an object selection function, wherein interaction with said region replaces the object presented on the output device with a next highest ranked object of the identified one or a plurality of candidate objects.

32. The system of claim 1, wherein the text entry system comprises a delete key region associated with a delete function, wherein when a current input sequence includes at least one interaction and said delete key region is interacted with, a last input interaction from the current input sequence of interactions is deleted.

33. The system of claim 1, wherein the text entry system includes a region associated with an Edit Word function, wherein:

when no current input sequence exists and said region is interacted with, and when the text insertion point on the output device is contained within a previously output word, the system establishes a new current input sequence comprising a sequence of interaction locations corresponding to coordinate locations associated with the characters of said word; and

when a text insertion point in the text display area on the output device is located between two previously output words, the system establishes a new current input sequence comprising a sequence of interaction locations corresponding to coordinate locations associated with the characters of the word adjacent to the text insertion point;

wherein the text entry system processes said new current input sequence and determines a corresponding ranking of new candidate objects; and

wherein selection of one of the new candidate objects replaces the previously output word used to establish said new current input sequence.

34. The system of claim 33, wherein when the text insertion point is within or adjacent to a word, and/or the word is selected/highlighted, and the user initiates a new input sequence, the system can establish a current input sequence using the adjacent/selected word with the user-entered interaction locations appended to the sequence.

35. The system of claim 1, wherein for each input interaction location, the distance value calculation component computes a running average of the horizontal and vertical components of an offset of the coordinate location corresponding to one or more characters of a selected word with respect to the coordinates of a corresponding input interaction location;

and wherein in performing distance calculations for the word evaluation component, the distance value calculation component adjusts the horizontal and vertical coordinates of each input interaction location by amounts that are functions of the computed average signed horizontal and vertical offsets.

36. The system of claim 1, said processor further comprising:

a stroke recognition component that determines for one or more user interaction actions within the auto-correcting region whether a point of interaction is moved less than a threshold distance from an initial interaction location prior to being lifted from the virtual keyboard;

wherein when the start and end points of interaction are less than a threshold distance, the stroke recognition component determines the nature of the user interaction to be a single point, and the location determined to be associated with the user interaction is added to the current input sequence of interaction locations to be processed by the distance value calculation component, the word evaluation component, and the selection component; and

wherein when the start and end points of interaction are greater than a threshold distance, the stroke recognition component determines that the user interaction is one of a plurality of stroke interactions that are associated with known system functions or recognizable characters, and classifies the stroke interaction as one of the plurality of predefined types of stroke interactions.

37. The system of claim 1, wherein when a threshold number of interaction locations in the input sequence are further than a threshold maximum distance from the corresponding character in the sequence of characters comprising a given candidate object, said object is identified as no longer being a candidate object for the selection component.

38. The system of claim 1, wherein the processor further comprises:

a frequency promotion component for adjusting a frequency of use value associated with each object in memory as a function of the number of times the object is selected by the user for output on the output device.

39. The system of claim 38, wherein the frequency promotion component analyzes additional information files that are accessible to the text entry system to identify new objects contained in said files that are not included among the objects already in said memory of said text entry system;

and wherein said newly identified objects are added to the objects in memory as objects that are associated with a low frequency of use.

40. The system of claim 1, wherein information regarding capitalization of one or a plurality of objects is stored along with the objects in memory;

and wherein the selection component presents each identified object in a preferred form of capitalization according to the stored capitalization information.

41. The system of claim 1, wherein one or a plurality of objects in memory are associated with a secondary object in memory comprising a sequence of one or a plurality of letters or symbols, and wherein when the selection component identifies one of said objects for presentation to the user based on the matching metric calculated by the word evaluation component, the selection component presents the associated secondary object for selection.

42. The system of claim 1, wherein said virtual keyboard comprises:

any of a laser-projection keyboard, a muscle sensing keyboard, a fabric keyboard, a gesture detection device, a device for tracking eye movement and a device for detecting brain waves.

43. The system of claim 1, further comprising:

a linguistic model comprising any of;

frequency of occurrence of a linguistic object in formal or conversational written text;

frequency of occurrence of a linguistic object when following a preceding linguistic object or linguistic objects;

proper or common grammar of the surrounding sentence;

application context of current linguistic object entry; and

frequency of use or repeated use of the linguistic object by the user or within an application program.

44. The system of claim 1, wherein user interaction comprises:

a scrolling gesture across or adjacent to the auto-correcting keyboard region that causes a list to scroll and changes a candidate word that is selected for output.

45. The system of claim 1, wherein user interaction comprises any of:

a gesture and other movement expressive of user intent, comprising any of a finger tap, any distiguishable eye movement, muscle activity, and a brain wave pattern.

46. A text entry system comprising:

a user input device comprising a virtual keyboard comprising an auto-correcting region having a plurality of interaction locations representing defined keys at known coordinates, which locations correspond to one or more characters of an alphabet, wherein user selection of a determined location corresponds to a key activation event that is appended to a current input sequence;

a memory containing a plurality of objects each comprising a string of one or a plurality of characters forming a word or a part of a word;

an output device; and

a processor coupled to the user input device, memory, and output device, said processor comprising;

a distance value calculation component which, for a generated key activation event location, calculates a set of distance values between the key activation event location and the known coordinate locations corresponding to one or a plurality of keys within the auto-correcting region;

a word evaluation component which, for a generated input sequence, identifies one or a plurality of candidate objects in memory, and for one or a plurality of identified candidate objects evaluates each identified candidate object by calculating a matching metric based on the calculated distance values and the frequency of use associated with the object, and ranks the evaluated candidate objects based on the calculated matching metric values; and

a selection component for identifying one or a plurality of candidate objects according to their evaluated ranking, presenting the identified objects to a user, and enabling the user to select one of the presented objects for output to the output device.

47. The text entry system of claim 46, wherein:

the plurality of objects in memory is further associated with one or a plurality of predefined groupings of objects; and

the word evaluation component, for a generated input sequence, limits the number of objects for which a matching metric is calculated by identifying one or a plurality of candidate groupings of the objects in memory, and for one or a plurality of objects associated with each of the one or a plurality of identified candidate groupings of objects, calculates a matching metric based on the calculated distance values, and ranks the evaluated candidate objects based on the calculated matching metric values.

48. The system of claim 46, wherein the characters of the alphabet are arranged on the auto-correcting region in approximately a standard telephone keypad layout.

49. The system of claim 46, wherein when a key activation event is detected comprising substantially simultaneous activation of a plurality of adjacent keys in the auto-correcting region, a location corresponding to said key activation event is determined as a function of the locations of the simultaneously activated keys, and said determined location is appended to the current input sequence of the locations of the key activation events.

50. The system of claim 46, wherein said auto-correcting region comprises one or a plurality of interaction locations associated with one or a plurality of punctuation characters and/or diacritic marks, wherein said memory comprises one or a plurality of objects in memory which comprise one or a plurality of the punctuation characters and/or characters accented by diacritic marks associated with keys in said auto-correcting region.

51. The system of claim 46, wherein the word evaluation component calculates a matching metric for candidate objects by summing distance values calculated from a determined location in the input sequence to a known location of the interaction location corresponding to the character in the corresponding position of the candidate object.

52. The system of claim 46, further comprising the step of:

applying a weighting function according to the frequency of use associated with the object.

53. The system of claim 46, wherein at least one of the interaction locations in the auto-correcting region corresponds to a plurality of characters, one or a plurality of which include various diacritic marks, wherein the plurality of characters comprise variant forms of a single base character, and wherein objects in memory are stored with their correct accented characters.

54. The system of claim 46, wherein the selection component presents the identified one or a plurality of candidate objects for selection by the user in a candidate object list.

55. The system of claim 54, wherein the selection component identifies a highest ranked candidate object and presents the identified object in the candidate object list in a position nearest to the auto-correcting region.

56. The system of claim 46, wherein activation of an interaction location that is associated with a character, where said interaction location is not included within the auto-correcting region, accepts and outputs a determined highest ranked candidate object prior to outputting the selected character.

57. The system of claim 46, wherein user selection of an object for output area terminates a current input sequence, wherein a next key activation event within the auto-correcting region starts a new input sequence.

58. The system of claim 46, wherein said virtual keyboard comprises:

any of a laser-projection keyboard, a muscle sensing keyboard, a fabric keyboard, a gesture detection device, a device for tracking eye movement, and a device for detecting brain waves.