System and method for continuous stroke word-based text input

• US 7,098,896 B2
• Filed: 01/16/2003
• Issued: 08/29/2006
• Est. Priority Date: 01/16/2003
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Swype, Inc. (Microsoft Corporation)
• Inventors: Marsden, Randal J., Kushler, Clifford A.
• Primary Examiner(s): Nguyen, Jimmy H.
• Application Number:
  US10/346,366
• Publication Number:
  US 20040140956A1
• Time in Patent Office: 1,321 Days
• Field of Search: 345/168, 345/169, 345/173, 715/773, 715/863, 715/864
• US Class Current: 345/168
• CPC Class Codes: G06F 2203/04805 Virtual magnifying lens, i.e. window or frame movable on top of displayed information to enlarge it for better reading or selection
• CPC Class Codes: G06F 2203/04806 Zoom, i.e. interaction techniques or interactors for controlling the zooming operation
• CPC Class Codes: G06F 3/0236 using selection techniques to select from displayed items
• 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

Abstract

A method and system of inputting alphabetic text having a virtual keyboard on a touch sensitive screen. The virtual keyboard includes a set of keys where an each letter of alphabet is associated with at least one key. The present invention allows someone to use the virtual keyboard with continuous contact of the touch sensitive screen. The user traces an input pattern for word by starting at or near the first letter in a decided word and then tracing through or near each letter in sequence. The present invention then generates a list of possible words associated with the entered part and presents it to user for selection.

Claims

1. A method of inputting alphabetic text to an electronic device having a virtual keyboard on a touch-sensitive screen, said virtual keyboard comprising a set of keys wherein each letter of the alphabet is associated with at least one key, the method comprising:

recording a contact action on the virtual keyboard, wherein the contact action includes an initial contact location, a path along which contact with the touch-sensitive screen continues, and a final contact location at which contact with the touch-sensitive screen is removed,

forming an input stroke pattern according to said recorded contact action;

comparing said input stroke pattern with a set of words stored in a database;

identifying one or more words stored in the database wherein the first letter of the identified word is associated with a key that is at or near the recorded initial contact location, and wherein the last letter of the identified word is associated with a key that is at or near the recorded final contact location, and wherein any remaining letters of the word are each associated with keys that are on or near the recorded path of the contact location;

determining relative ranking of the identified one or more words according to the comparison; and

offering one or more words of said determined relative ranking to the user for selection of the word to be input as text.

2. The method of claim 1, wherein said contact action includes moving said location of contact along the path of said contact action, and wherein said moving includes distinctly moving the location of contact when a desired word includes a letter that is repeated twice in succession.

3. The method of claim 2, wherein said distinctly moving includes moving in a circular motion on or near the key associated with the repeated letter.

4. The method of claim 2, further comprising repeating the distinctly moving for each additional repetition of the repeated letter when the desired word includes a letter that is repeated more than twice in succession.

5. The method of claim 2, wherein said distinctly moving includes moving one or more times in succession.

6. The method of claim 1, further comprising creating a tap input stroke pattern, when the point of contact is removed from the screen without being moved more than a threshold distance from the initial location of contact and without remaining in contact with the screen for more than a threshold time period.

7. The method of claim 6, further comprising:

comparing the tap input stroke pattern to a set of one-letter words stored in the database;

identifying one or more one-letter words that are acceptable based on the comparison;

determining relative ranking of the one or more one-letter words of said identified words according to the comparison; and

offering one or more words of said determined relative ranked words to a user.

8. The method of claim 7, wherein when none of said determined ranked words are associated with keys that are less than a minimum threshold distance from said tap input stroke pattern, then none of said identified words are offered to the user.

9. The method of claim 7, wherein each detected tap input stroke pattern is associated with the letter displayed on the key within which the tap input pattern is detected.

10. The method of claim 9, further comprising creating a text string that is composed of the sequence of letters associated with the sequence of detected tap input stroke patterns when a sequence of two or more consecutive tap input stroke patterns are detected, and offering the created text string to the user.

11. The method of claim 10, further comprising displaying a list that includes one or more regions within each of which one of the letters associated with the key within whose boundaries the initial location of contact is located, when the point of contact is not moved more than a threshold distance from the initial location of contact and remains in contact with the screen for more than a threshold time period, and making the input stroke pattern a tap input stroke pattern that is associated with the letter associated with region from which the point of contact is removed when the user moves the point of contact to one of said regions in said list and removes the point of contact.

12. The method of claim 10, wherein when said text string is selected by the user as the word to be input as test, and when said word is not yet present in said database of words, said word is automatically added to said database.

13. The method of claim 1, wherein while the user is contacting the screen to enter a word and the user determines that the entered path of the point of contact does not correspond to the user'"'"'s desired word, moving the point of contact in a distinctive manner to indicate that the current input stroke pattern is to be canceled, and wherein when the system identifies said distinctive manner of movement of the point of contact, no matching words are identified for said input stroke pattern including said distinctive manner of movement of the point of contact and no words are offered to the user for selection.

14. The method of claim 13, wherein the distinctive manner in which the point of contact is moved comprises a back and forth movement of the point of contact a threshold number of times, where the point of contact is moved faster than a threshold speed.

15. The method of claim 14, wherein the threshold speed is determined to be a threshold percentage faster than the fastest speed of movement of the point of contact measured within an input pattern for which an offered matching word is accepted for output by the user.

16. The method of claim 13, wherein when the system recognizes said distinctive manner of movement of the point of contact, providing a signal to the user indicating that said distinctive manner of movement has been detected and that no words will be offered to the user for selection in response to the current input stroke pattern.

17. The method of claim 1, wherein the arrangement of keys in said virtual keyboard is that of the traditional “

QWERTY”

layout.

18. The method of claim 17, wherein the width of certain keys in said virtual keyboard is increased relative to other keys.

19. The method of claim 1, wherein said comparing includes comparing said input stroke pattern with a sequence of locations of the keys associated with the sequence of letters comprising one of the words stored in the database.

20. The method of claim 19, further comprising determining a sequence of points of inflection along the path of said input stroke pattern, wherein each point of inflection is matched with a key that is associated with at least one letter of the compared word, wherein the points in the path occur in the same sequence as the associated letters occur in the sequence of letters comprising said compared word.

21. The method of claim 20, wherein an average value of distances from each determined point of inflection along the path to each corresponding matched key is used in calculating a matching metric to determine if the compared word is acceptable based on how closely the input stroke pattern matches the sequence of locations of the keys associated with the sequence of letters of said word.

22. The method of claim 21, further comprising calculating the matching metric from an average value of squared distances from each determined point along the path to each corresponding matched key.

23. The method of claim 21, wherein the distance to the key associated with any letter in the sequence of letters of the compared word that is not matched with a point of inflection is measured from the nearest point along the input stroke pattern that lies between the points from which the distances are measured to the keys associated with the letters immediately preceding and following the unmatched letter in the sequence of letters comprising the compared word, and wherein said distance is included in calculating the average value used in calculating said matching metric.

24. The method of claim 21 or claim 23, wherein when the distance from the key associated with the letter in the compared word to each matched point in an input stroke pattern exceeds a maximum threshold distance, the compared word is eliminated as a candidate to match the input stroke pattern.

25. The method of claim 21, wherein a plurality of types of points of inflection are identified.

26. The method of claim 25, wherein one of the plurality of types of points of inflection corresponds to a point determined at or near the initial contact location.

27. The method of claim 25, wherein one of the plurality of types of points of inflection corresponds to a point determined at or near the final contact location.

28. The method of claim 25, wherein said contact action includes moving said location of contact along the path of said contact action, and wherein said moving includes distinctly moving the location of contact when a desired word includes a letter that is repeated twice in succession, and wherein one of the plurality of types of points of inflection corresponds to a point determined at or near a location where the location of contact is distinctly moved.

29. The method of claim 25, wherein one of the plurality of types of points of inflection corresponds to a point, wherein the point is determined by recording the input stroke pattern as a sequence of points of contact, each of the points of contact being identified as a location on a two-dimensional coordinate plane, and identifying said point of inflection wherever the absolute value of a second order difference of one or both of the two-dimensional coordinates in the sequence of points of contact exceeds a determined threshold, and wherein said point of inflection is identified at or near a point where said absolute value of the second order difference of one or both of the two-dimensional coordinates reaches a local maximum.

30. The method of claim 25, wherein one of the plurality of types of points of inflection corresponds to a point, the point being along the segment of the input stroke pattern lying within a second horizontal row of keys at or near a point where the path of the input stroke pattern attains its maximum vertical distance from a first horizontal row of keys.

31. The method of claim 25, wherein said plurality of types of points of inflection are associated with weighting factors such that the distance of a key associated with a letter of said compared word that is matched with a point of inflection of a type associated with a relatively larger weighting factor has a correspondingly larger influence on a value calculated for said matching metric than the distance of a key associated with a letter of said compared word that is matched with a point of inflection of a type associated with a relatively smaller weighting factor.

32. The method of claim 25, wherein when a word is selected for output corresponding to an input stroke pattern, a difference is calculated between the location of each detected point of inflection and the location of the key associated with the letter in the output word with which the point of inflection was matched, wherein said difference is used to calculate a running average of said differences, and wherein said average difference is added to the location of each subsequently detected point of inflection to adjust the detected inflection point location, wherein the distance from an inflection point to the location of a key associated with a letter of a compared word is measured from said adjusted inflection point locations.

33. The method of claim 32, wherein said running average of said differences is calculated and added separately for the x-coordinate and the y-coordinate of each of said plurality of types of inflection point.

34. The method of claim 33, wherein said running average of said differences is calculated and added separately for positive and negative values of the second difference of the x-coordinate and the y-coordinate for one or more types of inflection point.

35. The method of claim 20, wherein the forming includes recording the input stroke pattern as a sequence of points of contact, each of the points of contact being identified as a location on a two-dimensional coordinate plane, and identifying a point of inflection wherever an absolute value of a second order difference of one or both of the two-dimensional coordinates in the sequence of points of contact exceeds a determined threshold, wherein said point of inflection is identified at or near a point where said absolute value of the second order difference of one or both of the two-dimensional coordinates reaches a local maximum, and wherein each said identified point of inflection is used as one of said determined sequence of points that is matched with a key that is associated with at least one letter of the compared word.

36. The method of claim 35, wherein the forming includes applying a smoothing algorithm to the sequence of points of contact before identifying the point of inflection.

37. The method of claim 35, wherein the first and second order differences of the two-dimensional coordinates calculated at each point along the input path are calculated with respect to two points at a fixed distance preceding and following the given point along the input path.

38. The method of claim 35, wherein wherever the input stroke pattern transitions from being within a first horizontal row of keys to being within a second horizontal row of keys and then returns to again lie within the first horizontal row of keys, and wherein no said point of inflection is identified according to the method of claim 31 along the segment of the input stroke pattern lying within said second horizontal row of keys, at least one additional point of inflection is identified along said segment of the input stroke pattern lying within said second horizontal row of keys at or near a point where the path of the input stroke pattern attains its maximum vertical distance from said first horizontal row of keys.

39. The method of claim 38, wherein said additional identified point of inflection is not matched with a key that is associated with a letter of said compared word when matching said sequence of determined points in the input stroke pattern with the keys associated with each letter of said compared word.

40. The method of claim 38, wherein horizontal and vertical components of the distance of a key associated with a letter of said compared word that is matched with a point of inflection are differentially weighted in computing the distance used in calculating the value for said matching metric.

41. The method of claim 35, wherein one or more of the words in the database are stored with an indication of the minimum number of points of inflection expected to be detected in an input stroke pattern corresponding to the word.

42. The method of claim 1, wherein the words in said database are stored in groups, wherein for each group of words, the first letters of all words in said group are associated with a single key of said virtual keyboard, and the last letters of all words in said group are associated with a single key of said virtual keyboard, said keys determining an ordered pair of keys uniquely associated with said group.

43. The method of claim 1, wherein one or more of the words in the database are stored with an indication of the frequency of use associated with the word, and wherein said frequency of use is used in determining which of the set of one or more words determined to most closely match the input stroke pattern is most likely to be the word intended to be input by the user, and wherein said determined set of words is presented to the user in order of decreasing likelihood.

44. The method of claim 1, wherein one or more of the words in the database are stored with an indication of the path length expected for an input stroke pattern corresponding to the word.

45. The method of claim 44, wherein the path length expected for an input stroke pattern corresponding to a word is calculated as the sum of the distances between the centers of the keys associated with the letters of the word in sequence.

46. The method of claim 1, wherein the word determined to most closely match the input stroke pattern is presented to the user as a default word choice selection.

47. The method of claim 46, wherein the word presented to the user as a default word choice selection is automatically accepted for output unless the user performs an explicit action to select an alternate word choice.

48. The method of claim 1, wherein each time a word is accepted for input as text immediately following a previously input word, a space is automatically generated between said previously input word and said immediately following word accepted for input.

49. The method of claim 1, wherein the forming said input stroke pattern includes creating a path comprised of contact point locations which connect in sequence the locations of the keys associated with the sequence of letters of a previously output word, wherein the identifying a set of one or more words includes excluding said previously output word that most closely matches said input stroke pattern, and the offering includes presenting one or more highest ranked words to the user for selection of the word to replace said previously output word in the output text.

50. The method of claim 49, wherein a smoothing process is first applied to said created input stroke pattern prior to comparing it with the set of words stored in the database.

51. An apparatus comprising:

a touch-sensitive screen for presenting a keyboard device, said virtual keyboard includes a set of keys wherein each letter of the alphabet is associated with at least one key;

an output device;

a database for storing words; and

a processor coupled to the touch-sensitive screen, the output device, and the database, the processor comprising;

a first component for recording a contact action on said virtual keyboard, wherein the contact action includes an initial contact location, a path along which contact with the touch-sensitive screen continues, and a final contact location at which contact with the touch-sensitive screen is removed;

a second component for forming an input stroke pattern according to said recorded contact action;

a third component for comparing said input stroke pattern with the words stored in the database;

a fourth component for identifying one or more words stored in the database wherein the first letter of the identified word is associated with a key that is at or near the recorded initial contact location, and wherein the last letter of the identified word is associated with a key that is at or near the recorded final contact location, and wherein any remaining letters of the word are each associated with keys that are on or near the recorded path of the contact location;

a fifth component for determining relative ranking of the identified one or more words according to the comparison; and

a sixth component for presenting one or more of the ranked words on the output device.