System and method for continuous stroke word-based text input

US 7,453,439 B1
Filed: 07/21/2004
Issued: 11/18/2008
Est. Priority Date: 01/16/2003
Status: Expired due to Fees

- Alert
- Pin

Associated Cases

Associated Defendants

First Claim

Patent Images

1. An apparatus comprising:

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

an input device which detects a trace of an input path on said displayed keyboard, said input path comprising a sequence of input path locations on or near said displayed keyboard;

an output device;

a database for storing words; and

a processor coupled to the input device, the output device, and the database, the processor comprising;

a first component for recording input path data corresponding to a trace of an input path on said displayed keyboard, wherein said input path data include an initial path location, a sequence of one or more locations along which said input path continues, and a final path location at which said input path terminates;

a second component for identifying one or more words of a set of words stored in a database, one or more of said set of words associated with an indication of frequency of use, wherein one or more letters of each identified word are each associated with keys that are within a determined threshold distance of one or more determined points on said input path; and

a third component for comparing said input path with one or more of said identified words, wherein comparing includes comparing a sequence of locations of the keys associated with the letters comprising the spelling of a word with said input path;

a fourth component for determining a numerical score for one or more of the compared one or more words to establish a relative ranking of the words according to the comparison and the frequency associated with the word.

View all claims

9 Assignments

Timeline View

Assignment View

Litigations

0 Petitions

Accused Products

Abstract

The disclosed System enables a small virtual keyboard on a touch-screen to be used to enter a word by contacting the keyboard on or near the key of the first letter, tracing through or near the key of each letter in sequence, and lifting the stylus from the keyboard in the vicinity of the key of the last letter. The input pattern is matched by scoring it against words in a database which includes an indication of relative frequency. A correctly spelled word is matched even when the input pattern corresponds to an incorrect spelling of a word. Words are ranked according to a score calculated from the weighted distances from each associated key to determined input path points, further weighted by the frequency of use and by other characteristics of the input path. Alternate word choices are presented to the user in a manner to minimize distraction.

501 Citations

63 Claims

1. An apparatus comprising:
- a device for presenting a displayed keyboard, said displayed keyboard includes a set of keys wherein each letter of the alphabet is associated with at least one key;
  
  an input device which detects a trace of an input path on said displayed keyboard, said input path comprising a sequence of input path locations on or near said displayed keyboard;
  
  an output device;
  
  a database for storing words; and
  
  a processor coupled to the input device, the output device, and the database, the processor comprising;
  
  a first component for recording input path data corresponding to a trace of an input path on said displayed keyboard, wherein said input path data include an initial path location, a sequence of one or more locations along which said input path continues, and a final path location at which said input path terminates;
  
  a second component for identifying one or more words of a set of words stored in a database, one or more of said set of words associated with an indication of frequency of use, wherein one or more letters of each identified word are each associated with keys that are within a determined threshold distance of one or more determined points on said input path; and
  
  a third component for comparing said input path with one or more of said identified words, wherein comparing includes comparing a sequence of locations of the keys associated with the letters comprising the spelling of a word with said input path;
  
  a fourth component for determining a numerical score for one or more of the compared one or more words to establish a relative ranking of the words according to the comparison and the frequency associated with the word.
- View Dependent Claims (2, 3)
- - 2. The apparatus of claim 1, further comprising:
    - a fifth component for presenting one or more of the ranked words on the output device.
  - 3. The apparatus of claim 1, further comprising:
    - a fifth component for comparing the numerical scores determined for the highest ranked word and the second-highest ranked word; and
      
      a sixth component for selecting the highest ranked word as text to be generated for input when the comparison between the numerical scores exceeds a determined threshold.

4. A method of inputting alphabetic text to an electronic device having a displayed keyboard, said displayed keyboard includes a set of keys wherein each letter of the alphabet is associated with at least one key, the method comprising:
- recording input path data corresponding to a trace of an input path on said displayed keyboard, wherein said input path data include an initial path location, a sequence of one or more locations along which said input path continues, and a final path location at which said input path terminates,identifying one or more words of a set of words stored in a database, one or more of said set of words associated with an indication of frequency of use, wherein one or more letters of each identified word are each associated with keys that are within a determined threshold distance of one or more determined points on said input path; and
  
  comparing said input path with one or more of said identified words, wherein comparing includes comparing a sequence of locations of the keys associated with the letters comprising the spelling of a word with said input path;
  
  determining a first numerical score for each of the compared one or more words to establish a relative ranking of the words according to the comparison and the frequency associated with the word.
- View Dependent Claims (5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63)
- - 5. The method of claim 4, further comprising generating one of the identified one or more words as text to be input.
  - 6. The method of claim 5, further comprising offering one or more of the highest ranked words of said determined relative ranking to the user for selection of the word to be generated as text to be input.
  - 7. The method of claim 5, further comprising an editing environment wherein one or more words that are generated as text to be input are displayed in an output text area.
  - 8. The method of claim 7, further comprising:
    - creating and maintaining a database comprising a list of one or more words previously generated as text to be input, wherein each of said words in said list is associated with one or more of the highest ranking alternate candidate words identified during the processing of the input path to which said stored word was compared;
      
      detecting a distinctive control action performed on a displayed word in said output text area;
      
      identifying said displayed word one of said stored words in said database list; and
      
      offering one or more of said highest ranking alternate candidate words associated with said displayed word in said database for selection of the word to be generated as text to replace said displayed word in said output text area.
  - 9. The method of claim 8, wherein said distinctive control action is a double-tap with a stylus on a word displayed on a touch sensitive display screen.
  - 10. The method of claim 8, wherein said distinctive control action is a double-click on a mouse with the mouse cursor on a word displayed on a display screen.
  - 11. The method of claim 8, wherein said distinctive control action is a distinctive movement of the mouse cursor that begins with the mouse cursor positioned on a word displayed on a display screen.
  - 12. The method of claim 7, further comprising:
    - detecting and recording changes in the position of the text insertion location in said editing environment;
      
      identifying one or more characters preceding the position of the text insertion location in said editing environment each time the position of the text insertion location is changed to a new position;
      
      determining whether a space is automatically generated prior to generating a next word as text to be input at said new position of the text insertion location;
      
      automatically generating or not generating a space prior to generating a next word as text to be input at said new position of the text insertion location according to the determination.
  - 13. The method of claim 5, further comprising comparing said numerical scores determined for the highest ranked word and the second-highest ranked word, and when the comparison between the numerical scores exceeds a determined threshold automatically selecting the highest ranked word to be generated as text for input without offering any of the ranked words to the user for selection.
  - 14. The method of claim 6, wherein said determining said numerical score for said word includes:
    - determining two or more points along said input path, including at least one point at or near said initial path location and one point at or near said final path location, that are designated as points of inflection;
      
      for each of one or more of said keys associated with the letters comprising the spelling of said word, determining a corresponding matching point on said input path;
      
      calculating said numerical score from a function of one or more of the distances from each determined matching point on said input path to the location of the corresponding matched key associated with a letter of the compared word; and
      
      determining one or more penalty amounts that are included in the calculation of said function for each instance in which the order of the sequence along the input path of matching points does not correspond with the sequence of said associated letters in the spelling of the compared word.
  - 15. The method of claim 14, wherein the location of each said determined point of inflection along the path is described by a first set of coordinates including a horizontal and a vertical coordinate, and wherein each said key is at a location described by a second set of said coordinates, and wherein said each said distance is calculated as a function of the difference between said first and second horizontal coordinates and of the difference between said first and second vertical coordinates, and wherein said difference between said first and second vertical coordinates is modified by multiplying said vertical coordinate difference by a determined factor in calculating said distance.
  - 16. The method of claim 14, further comprising:
    - identifying a key associated with a letter in the spelling of the compared word that is no more than a maximum threshold distance from a determined point along a segment of said input path that lies between two successive determined points of inflection along said input path;
      
      matching said key with said determined point along said segment of said input path; and
      
      including the distance from said matched key to said matched determined point in said function of said distances in calculating said numerical score of said word.
  - 17. The method of claim 16, wherein the distance from said matched key to said matched determined point is weighted according to one or more characteristics determined for said matched determined point before being included in said function of said distances.
  - 18. The method of claim 17, wherein each point of inflection is of one of two or more types of points of inflection, and wherein recording the input path data as a sequence of locations further comprises:
    - recording each location as a point on a two-dimensional coordinate plane;
      
      detecting when the sum of the absolute values of the rates of change of the rates of change of the two-dimensional coordinates in the recorded sequence of locations exceeds a determined threshold;
      
      determining a path location point where said rate of change of the rate of change reaches a local maximum; and
      
      identifying a point of inflection of said first type at or near said determined path location point.
  - 19. The method of claim 18, wherein one of said characteristics is the magnitude of the sum of the absolute values of the rates of change of the rates of change of the two-dimensional coordinates in the recorded sequence of locations at the point with which the key associated with a letter in a candidate word is matched.
  - 20. The method of claim 17, wherein, in calculating said function of said distances, an adjustment is made to the magnitude of the distance from a first key associated with a letter in a candidate word to a first matched point in the input path with which said first key is matched, wherein said adjustment is calculated based on one or more parameters determined with respect to a second key associated with an adjacent letter in the candidate word and a second matched point in the input path with which said second key is matched.
  - 21. The method of claim 20, wherein the magnitude of the adjustment made to said distance is further adjusted according to the distance between said first key and said second key.
  - 22. The method of claim 20, wherein the magnitude of the adjustment made to said distance is further adjusted according to the distance between said first matched input path point and said second matched input path point.
  - 23. The method of claim 20, wherein one of said parameters is determined as a function of a comparison of the slope of a line between said first key and said second key to the slope of a line between said first matched input path point and said second matched input path point.
  - 24. The method of claim 20, wherein one of said parameters is determined as a function of a comparison of the distance along a straight line between said first matched input path point and said second matched input path point to the distance along the actual input path between said first matched input path point and said second matched input path point.
  - 25. The method of claim 16, wherein when the distance from the key associated with a letter in a candidate word to any potentially matching point on said input path exceeds a determined maximum threshold distance, the word is eliminated as a candidate to match the input path data.
  - 26. The method of claim 16, further comprising:
    - determining one or more penalty amounts that are included in the calculation of said function when one or more of said designated points of inflection is not determined as a matching point for any key associated with a letter of the compared word; and
      
      determining one or more penalty amounts that are included in the calculation of said function for each instance in which no corresponding matching point is determined for one or more keys associated with letters of the compared word.
  - 27. The method of claim 16, wherein when the distance from the key associated with a letter in a candidate word to any potentially matching point on said input path exceeds a determined maximum threshold distance, a determined penalty amount is included in the calculation of said function of said distances from which the numerical score of said word is calculated.
  - 28. The method of claim 14, wherein when a determined point of inflection along said input path is not matched with any key associated with a letter in a candidate word, a determined penalty amount is included in the calculation of said function of said distances from which the numerical score of said word is calculated.
  - 29. The method of claim 26, wherein said determined maximum threshold distance is adjusted with respect to the measured speed of the motion in tracing said input path.
  - 30. The method of claim 26, wherein a secondary numerical score is calculated for one or more of said identified one or more words, and wherein the calculation of said secondary numerical score of said identified one or more words does not include one or more of said determined penalty amounts that are included in the calculation of said first numerical score, and wherein the indication of frequency of use associated with said identified one or more words is not included in the calculation of said secondary numerical score.
  - 31. The method of claim 30, wherein the difference is calculated between said secondary numerical score for the word ranked highest according to said first numerical score and said secondary numerical score for a second word, and wherein when said calculated difference in secondary numerical scores falls below a determined threshold, an adjustment is made to the ranking established according to said first numerical score.
  - 32. The method of claim 6, further comprising comparing the numerical scores determined for the highest ranked word and the second-highest ranked word, and offering two or more of the highest ranked words of said determined relative ranking in a distinctive visual manner to the user for selection of the word to be input as text when the comparison between said numerical scores falls below a determined threshold.
  - 33. The method of claim 7, further comprising comparing the numerical scores determined for the highest ranked word and the second-highest ranked word, and generating the highest ranked word as text to be input in a distinctive visual manner when the comparison between said numerical scores falls below a determined threshold.
  - 34. The method of claim 5, further comprising comparing the numerical scores determined for the highest ranked word and the second-highest ranked word, and generating a distinctive auditory signal to the user when the comparison between the numerical scores falls below a determined threshold.
  - 35. The method of claim 5, further comprising comparing the numerical scores determined for the highest ranked word and the second-highest ranked word, and generating a distinctive visual signal to the user when the comparison between the numerical scores falls below a determined threshold.
  - 36. The method of claim 4, wherein each letter of the alphabet is associated with at least one key of said displayed keyboard, and wherein said set of keys is arranged according to the standard “
    - QWERTY”
      
      layout, and wherein one or more pairs of adjacent keys are separated by inactive areas not associated with any letter.
  - 37. The method of claim 5, wherein when a word is generated as text to be input immediately following a word previously generated as text to be input, a space is automatically generated between said previously generated word and said immediately following generated word.
  - 38. The method of claim 37, wherein one or more of the one or more words stored in the database comprise words that comprise only non-alphabetic characters.
  - 39. The method of claim 4, wherein when said first numerical score determined for the highest ranked word is no better than a determined first numerical score threshold, said determined threshold distance is increased and said comparing and identifying is repeated using the increased threshold distance.
  - 40. The method of claim 4, wherein the magnitude of the effect that the indication of frequency stored in said database with said word has on the calculation of the numerical score of said word is modified according to the measured speed of the motion in tracing said input path.
  - 41. The method of claim 26, wherein said determined maximum threshold distance is adjusted with respect to the number of points of inflection determined along said input path.
  - 42. The method of claim 30, wherein the initial indication of frequency associated with one or more words of the set of words stored in said database is proportional to the relative frequency with which the word is generally used in the language from which said words are taken.
  - 43. The method of claim 42, wherein the indication of frequency associated with one or more words of the set of words stored in said database is set to a value that is lower than the relative frequency with which the word is generally used in the language from which said words are taken.
  - 44. The method of claim 42, wherein the indication of frequency associated with one or more words of the set of words stored in said database is modified when a word other than the highest ranked word is selected as text to be generated for input by the user.
  - 45. The method of claim 44, wherein the indication of frequency associated with one or more words of the set of words stored in said database is modified when a numerical score determined for the word selected to be generated as text to be input by the user is within a determined threshold margin of a numerical score determined for the highest ranked word when the respective indications of frequency of use associated with said words are not included in the calculation of said numerical scores.
  - 46. The method of claim 26, wherein the indication of frequency associated with one or more words of the set of words stored in said database is modified when a word other than the highest ranked word is selected to be input as text by the user and the sum of the determined penalty amounts included in the calculation of the numerical score determined for said selected word is less than a determined maximum threshold.
  - 47. The method of claim 26, wherein when a sum of the penalty amounts included in calculating the numerical score determined for a candidate word exceeds a determined maximum threshold, the word is eliminated as a candidate to match the input path data.
  - 48. The method of claim 4, in which one or more words of a set of words are stored in a database represented as strings of letters composed of an initial root string component and a final suffix string component.
  - 49. The method of claim 48, in which one or more initial root string components are stored as an initial prefix string component followed by a string of zero or more letters comprising the remaining portion of said initial root string component.
  - 50. The method of claim 49, in which each initial prefix string component comprises two letters.
  - 51. The method of claim 48 wherein the comparing said input path with one or more words of a set of words stored in a database includes comparing the initial portion of said input path with one or more root string components and identifying one or more root string components stored in the database wherein one or more letters of the identified root string component are each associated with keys that are within a determined threshold distance of the initial portion of said input path and comparing said input path with one or more words in the database whose composition includes one of said identified root string components.
  - 52. The method of claim 49, wherein the comparing said input path with one or more words of a set of words stored in a database includes comparing the initial portion of said input path with one or more prefix string components and identifying one or more prefix string components stored in the database wherein one or more letters of the identified prefix string component are each associated with keys that are within a determined threshold distance of the initial portion of said input path and comparing said input path with one or more words in the database whose composition includes one of said identified prefix string components.
  - 53. The method of claim 48, wherein the comparing said input path with one or more words of a set of words stored in a database includes comparing the final portion of said input path with one or more suffix string components and identifying one or more suffix string components stored in the database wherein one or more letters of the identified suffix string component are each associated with keys that are within a determined threshold distance of the final portion of said input path and comparing said input path with one or more words in the database whose composition includes one of said identified suffix string components.
  - 54. The method of claim 48, wherein two or more of said suffix string components are grouped in at least one defined set of suffix string components, wherein every suffix string component that is a member of said defined set can be combined with one or more root string components to create one or more sets of distinct words, wherein each word in each said set of distinct created words is composed from a single shared root string component, and wherein each such said set of distinct words is stored within the database as a single indication of said shared root string component combined with a single indication of said defined set of suffix string components.
  - 55. The method of claim 54, wherein said defined set of suffix string components includes an indication of the average relative frequencies of each word in a set of words created by combining said defined set of suffix string components with a single root string component, and wherein each set of distinct words that is stored within the database as a single indication of a shared root string component combined with a single indication of said defined set of suffix string components includes an indication of the frequency of at least one of the words included in said set of distinct words.
  - 56. The method of claim 14, wherein when the distance from an inflection point to the key with which it is matched is greater than the distance to the matched key from the closest point to the matched key on the path segment immediately preceding the matched inflection point, the distance from the matched inflection point to the matched key is calculated as a weighted average of the actual distance of the matched key from the matched inflection point and of the distance of the matched key from the closest point to the matched key on the preceding path segment.
  - 57. The method of claim 56, wherein said weighted average is not used as the calculated distance from the matched inflection point to the matched key when the slope of a line from the path point with which the preceding key was matched to said matched inflection point differs by more than a determined threshold amount from the slope of a line from the preceding matched key to the matched key.
  - 58. The method of claim 5, wherein said comparing said input path includes detecting a determined pattern of movement in said input path that is in a region associated with a determined neighborhood of a key that is associated with a letter of an identified word, and wherein said letter of said identified word that is associated with said key is shifted to upper case in the text of said identified word that is included in said established relative ranking.
  - 59. The method of claim 58, wherein said determined pattern of movement in said input path comprises a movement of said trace of said input path upward past the top boundary of said displayed keyboard.
  - 60. The method of claim 58, wherein when said determined pattern of movement in said input path is detected in a region associated with a determined neighborhood of a key associated with a letter of a candidate word such that the associated letter is accordingly shifted to upper case in the text of the candidate word to be included in the established relative ranking, and wherein when the resulting pattern of upper-case and lower-case characters in said candidate word comprises a pattern that is infrequently found in general usage, the numerical score determined for said candidate word is adjusted by a penalty factor corresponding to the infrequency of said pattern of upper-case and lower-case characters.
  - 61. The method of claim 5, wherein said comparing said input path includes detecting a determined pattern of movement in said input path, and wherein each letter of each identified word is shifted to upper case in the text of each word included in said established relative ranking.
  - 62. The method of claim 61, wherein said determined pattern of movement in said input path comprises a movement of said trace of said input path upward past the top boundary of said displayed keyboard, and performing a distinctive pattern of movement above the top boundary of said displayed keyboard.
  - 63. The method of claim 62, wherein said distinctive pattern of movement above the top boundary of said displayed keyboard comprises forming a more or less circular loop in said trace of said input path.

Specification

Resources

Litigation Campaign Assessment

Litigation Data

Current Assignee
Cerence Operating Company (Cerence Inc.)
Original Assignee
Forward Input Incorporated
Inventors
Kushler, Clifford A., Marsden, Randal J.
Primary Examiner(s)
Shankar; Vijay

Application Number

US10/710,575
Time in Patent Office

1,581 Days
Field of Search

345156-179, 178 1801- 1809
US Class Current

345/168
CPC Class Codes

G06F 3/0237   using prediction or retriev...

G06F 3/04883   for inputting data by handw...

G06F 3/04886   by partitioning the display...

System and method for continuous stroke word-based text input

First Claim

9 Assignments

Litigations

0 Petitions

Accused Products

Abstract

501 Citations

63 Claims

Specification

Solutions

Use Cases

Quick Links

System and method for continuous stroke word-based text input

First Claim

9 Assignments

Subscription Required

Subscription Required

Litigations

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

501 Citations

63 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links