Virtual keyboard system with automatic correction

• US 7,920,132 B2
• Filed: 04/22/2010
• Issued: 04/05/2011
• Est. Priority Date: 05/27/1999
• Status: Expired due to Fees

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Tegic Communications, Inc. (Microsoft Corporation)
• Inventors: Longe, Michael R., Meurs, Pim Van
• Primary Examiner(s): Mengistu; Amare
• Assistant Examiner(s): Xavier; Antonio
• Application Number:
  US12/765,687
• Publication Number:
  US 20100257478A1
• Time in Patent Office: 348 Days
• Field of Search: None
• US Class Current: 345/173
• 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 determines one or more alternate textual interpretations of each sequence of inputs detected within a designated auto-correcting keyboard region. The actual contact 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 contact 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.

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 a character set, where the characters occupy different character locations with different known coordinates in the auto-correcting region, wherein an interaction location associated with a user interaction is determined when a user interacts with the user input device within the auto-correcting region, the interaction location including coordinates of a contact point on the auto-correcting region, and the determined interaction location is added to a current input sequence of interaction locations;

a machine readable vocabulary containing a plurality of objects, wherein one or more of the objects comprise a string of one or a plurality of characters forming all or part of a word or phrase;

an output device having an output text region and an object choice list region; and

a processor coupled to the user input device, the vocabulary, and the output device, said processor programmed to perform operations comprising;

responsive to each new user interaction, conducting object-level analysis of various candidate objects from the vocabulary, comprising operations of;

associating each user interaction with a different character of the given object, and scoring the given object according to factors including distances from the interaction locations in the current input sequence and the known coordinates of the associated characters of the given object;

additionally responsive to each new user interaction, causing the object choice list region to display multiple objects according to scores produced by the object-level analysis;

operating the output text region to display text entered by the user and to serve as a buffer for text input and editing;

responsive to the user selecting one of the objects displayed in the object choice list, entering the selected object in the output text region.

2. The system of claim 1, wherein one or more of the plurality of objects in said vocabulary is further associated with one or a plurality of predefined groupings of objects.

3. The system of claim 1, wherein one or more of the plurality of objects in said vocabulary are further associated with one or a plurality of modules, wherein each module comprises or generates a set of objects having one or a plurality of common characteristics.

4. The system of claim 1, wherein one or more of the plurality of objects in said vocabulary is further associated with a promotion value.

5. The system of claim 4 said processor programmed such that the scoring operation further applies a weighting function according to the promotion value.

6. The system of claim 1, wherein the character set members are arranged on the auto-correcting keyboard region in approximately alphabetic order for a language.

7. The system of claim 1, wherein the character set members are arranged on the auto-correcting keyboard region in approximately any standard keyboard layout.

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

9. The system of claim 1, further comprising:

means for providing feedback to the user identifying the character set members near a current interaction location.

10. The system of claim 9, wherein the feedback is presented visually on the output device and only character set members occupying known locations closest to the current interaction location are indicated by one or more of:

size, color, background shading, and font attribute.

11. The system of claim 1, wherein the user input device further comprises means for changing some or all of the auto-correcting keyboard region to a determined key state, wherein a character set member is determined when a user interacts with one of the keys or with a known location in the changed region and a representation of the determined character set member is added to the current input sequence.

12. The system of claim 1, wherein the processor is further programmed to perform operations including determining, for an interaction location in an input sequence, a closest known location corresponding to a character set member, and constructing an exact typing object composed of said corresponding character set members in an order corresponding to the input sequence.

13. The system of claim 1, where the processor is programmed such that the operation of displaying multiple objects according to scores produced by the object-level analysis includes displaying a highest ranked object.

14. The system of claim 13, wherein the display of the highest ranked object occurs at a current text entry location.

15. The system of claim 13, further comprising a user input region or device that is associated with an object selection function, wherein an interaction with said device replaces the object presented on the output device with a next highest ranked object of the said one or a plurality of candidate objects.

16. The system of claim 1, wherein for a character set member corresponding to a known coordinate location in the auto-correcting region, a region is predefined around one or a plurality of said known coordinate locations, wherein any user interaction location within said predefined region is determined as occurring at a known coordinate location.

17. 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 of a character set, one or a plurality of which comprise at least one diacritic mark, wherein the plurality of character set members comprise variant forms of another character set member and wherein objects in the vocabulary contain said variant forms.

18. The system of claim 1, where the processor is programmed such that the user selection of one of the displayed multiple objects occurs via an alternate input modality.

19. The system of claim 1, wherein user inputs for the current input sequence are provided through a combination of different modalities.

20. The system of claim 1, where the processor is programmed to perform operations as follows:

detecting a distinctive manner of selection that is used to select a candidate object;

upon detecting that an object has been selected through said distinctive manner, replacing a current input sequence of actual interaction locations with an input sequence of interaction locations corresponding to the coordinate locations of the character set members comprising the selected object; and

appending a next interaction in the auto-correcting region to the current input sequence.

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

22. The system of claim 1, wherein the processor is further programmed to adjust a promotion value associated with each object in the vocabulary as a function of how many times the object is selected by the user for output on the output device.

23. The system of claim 22, wherein the processor is further programmed to perform operations comprising:

analyzing 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 vocabulary of said text entry system; and

adding said newly identified objects to the objects in the vocabulary.

24. The system of claim 1, wherein the user input device comprises any of:

a mouse, a trackball, a trackpad, a joystick, and a device for decoding brainwaves.

25. The system of claim 1, further comprising:

means for providing visual feedback of the user'"'"'s interaction with said user input device.

26. The system of claim 25, the processor being programmed to perform further operations comprising:

providing the user with visual feedback as to which character is being selected by magnifying whichever character corresponds to the interaction location and continually updating said magnification as the interaction location changes across the auto-correcting region.

27. The system of claim 1, wherein one or more objects in the vocabulary are associated with a secondary object in the vocabulary comprising a designated function and wherein, when the user selects one of the presented objects associated with a secondary object, the designated function is executed.

28. The system of claim 1, wherein said plurality of objects comprises correctly spelled words and said processor is programmed to identify and rank one or more said correctly spelled words corresponding to said input sequence of interactions.

29. The system of claim 1, wherein said auto-correcting keyboard region is displayed or printed on the surface of the user input device without defined boundaries between the entire set of characters.

30. The system of claim 1, where the processor is programmed such that the scoring operation comprises:

for each interaction location in the entry sequence, computing a square of a distance from the interaction location to the location occupied by the associated character in the given object;

summing all the computed squares;

multiplying the sum of the computed squares by a frequency adjustment factor.

31. The system of claim 30, where the processor is programmed such that the frequency adjustment factor is a base 2 logarithm of an ordinal position of the given object with respect to other candidate objects, where objects associated with higher relative frequencies of use correspond to lower ordinal positions, with a most frequently used object having position one.

32. The system of claim 30, where the processor is programmed to perform an additional operation comprising, prior to multiplying the sum of the computed squares by the frequency adjustment factor, adding a fixed increment to the sum.

33. The system of claim 32, where the fixed increment equals twice an average distance between adjacent characters locations upon the virtual keyboard.

34. The system of claim 1, where objects in the vocabulary are organized into groups of same length words and the processor is programmed such that the scoring operation comprises:

identifying all objects from the vocabulary having a length equal to the current input sequence and scoring only the identified objects;

determining whether there are more than a prescribed minimum number of scored and identified objects;

if so, outputting the scored and identified objects for use in the object choice list;

if not, iteratively identifying all objects from the vocabulary having a length equal to the current input sequence plus incrementally greater numbers starting with one, and only in response to occurrence of the prescribed minimum number of scored and identified objects, outputting the scored and found objects for use in the object choice list.

35. The system of claim 1, where the processor is further programmed such that the scoring operation comprises:

counting how many interaction locations of the current input sequence exceed a prescribed distance from the known coordinates of the associated characters of the given object;

if the count exceeds a prescribed threshold, scoring the given object as zero or null.

36. The system of claim 1, where the processor is further programmed to perform operations comprising:

following a given interaction, which occurs upon a given character, delaying processing of the user interaction for a prescribed period or until receiving a user interaction upon on a character non-adjacent to the given character;

responsive to one or more user interactions upon the given character or one or more characters adjacent to the given character during the prescribed period, regarding said one or more user interactions as a single user interaction located at a computed center or average of the user interactions.

37. The system of claim 1, where:

instead of multiple objects, where the processor is programmed to cause the object choice list to display only a single object for which the object-level analysis yielded a highest score; and

responsive to repeated user activation of a designated selection input, successively replacing the displayed single object with other scored objects of iteratively lesser scores.

38. The system of claim 1, where the processor is programmed to perform operations comprising:

for each input sequence of interaction locations, constructing a word by identifying the character whose known coordinate is nearest each interaction location and composing a word consisting of the identified characters in order of user entry;

presenting the constructed word in the object choice list region for user review and selection.

39. The system of claim 1, the processor further programmed to perform operations comprising:

detecting when a site of user interaction moves before user contact is lifted from the surface, and in response, resolving ambiguity as to the location of user interaction by computationally predicting a point of contact predicted intended by the user.

40. The system of claim 39, further comprising:

recording a path traced out by the moving user interaction as a set of interaction points of a predetermined number, the points including endpoints of the path and zero or more points equally spaced along the path;

designating that an nth point of each set of recorded points be used as the interaction location for conducting the scoring operation;

responsive to the user selecting an object from the object choice list, repeating the scoring operation for the chosen object based each remaining point of each set of recorded points, and then performing one of the following;

designating than whichever set of points results in a minimum calculated distance be used as the interaction location for conducting future scoring operations; and

computing a running average based on distances calculated from each point set, and designating the point set for which the running average is lowest to be used for conducting future scoring operations.