HK1091023B - System and method for continuous stroke word-based text input - Google Patents

Description

Continuous stroke word-based text input system and method

Technical Field

The present invention relates to text input systems, and more particularly to touch screen text input systems.

Background

The origin of modern keyboards, which are the primary method of inputting text from humans to machines, dates back to early printers in the 19 th century. With the advent of computers, the use of typewriter keyboards as the primary method of entering text has evolved naturally. For skilled typists, it remains the fastest possible way to enter text into a computer.

With ongoing efforts to make computers smaller and more portable, physical keyboards have become one of the most important limiting factors in how small a device can be: computer designers cannot change the physical size of a person's finger. Thus, computers without physical keyboards have been designed for certain portable applications, such computers using touch screen-based input methods as the primary form of human-machine interface (as is the case for some applications where a human cannot use a keyboard for physical reasons (e.g., people with disabilities)).

There are two basic requirements for touch screen input methods that often conflict with each other. The input method must be as fast as possible and at the same time, the input method must occupy as small a display screen as possible. Unfortunately, as the space on the display screen occupied for input is reduced, it is difficult to increase speed without adversely affecting accuracy.

Despite the recent surge in demand for pen-type computing devices, many people who must generate text still utilize standard keyboards to generate text. In fact, a whole industry has emerged that provides portable keyboards for pen computers that are designed without keyboards. To date, pen computing devices have not replaced conventional portable laptops as originally predicted, for the simple reason that text entry on pen computers is too slow. Even the recently proposed "Tablet PC", mainly due to the lack of a sufficiently accurate handwriting recognition engine, is used mainly as a way to save and retrieve "digital ink" -the actual graphical image of the user's handwriting depicted on the touch screen-as opposed to recognizing what was written and converting it into computerized text.

Similar to one-finger typing, the prior art using a virtual keyboard for input is known as "point and tap". The pen tip is moved between the letters and pressed down on the desired key, thereby selecting the key. This results in the stylus always needing to be lifted and lowered, slowing down the input. Cursive handwriting has been invented to allow better (and faster) movement between letters, reducing the number of times a pen (or goose brush) is lifted. In a similar manner, the current invention utilizes an on-screen keyboard to reduce the number of taps required when entering text, thereby speeding up text entry.

A natural way for humans to produce text on anything other than a machine is to "write" the text in hand. Therefore, with the advent of touch screen computers, handwriting recognition software was developed that allowed users to input text by writing on the screen of the computer without making them surprising. But naturally handwriting is slower. Each letter requires several pens of the stylus, making it very inefficient. Furthermore, the accuracy of the software remains below user acceptable levels due to the changing hand-writing stylus (see MacKenzie, I.S., & Chang, L. (1999), Aperformance compliance of two hand-writing recognizers. interactions with Computers, 11, 283- & 297). As described above, even with the "strongest recent" computer touch screen technology, the reliance of Tablet Pc on the use of "digital ink" clearly indicates that handwriting recognition is still not as good as satisfactory for most users. Furthermore, even if a completely accurate handwriting recognition method exists, handwriting itself is too slow and tiring (especially on touch screens) to provide a satisfactory input method.

Some methods make this work easier for the software by requiring the user to write letters in a simplified manner (see Goldberg, US patent application 20020009227, Unistroke; or as popular with Palm Computing in their commercial product named "Graffiti"). The advantage of this approach is that each character is sufficiently unique to be easily recognized by software, each character is depicted as a single stroke, and no virtual keyboard is required on the screen. The disadvantage of this method is that it requires the user to learn a new writing method, still requiring the stylus to be lowered and lifted once for each individual character (thereby slowing text entry).

Likewise, the idea of bringing a keyboard into the virtual world of a computer display is a natural development. Auer et al, in U.S. patent #4725694, describe a system in which one or more images of a simulated keyboard are displayed on a touch-sensitive screen of a computer and appropriate control signals are generated in response to the touching of simulated keys. In a recent improvement of this principle, the image of the keyboard is floating displayed on top of other applications running on the computer, rather than occupying a dedicated portion of the screen. The user interacts with the "on-screen keyboard" or "virtual keyboard" by directing a cursor pointer over it, or by directly touching keys through a touch screen with a finger or stylus. On-screen keyboards have been used primarily for devices that lack a standard keyboard, such as certain public kiosks and Personal Digital Assistants (PDAs), handheld computers that are too small to accommodate a physical keyboard. They are also often used by individuals who have disabilities such that a physical keyboard cannot be used.

Screen keyboards have two major drawbacks: firstly, they take up valuable screen space on the computer required for any task requiring text entry, and secondly, and more importantly, they are slow because the user has to tap one letter at a time-in effect forcing the user to enter text in a manner similar to a single hand tap on a conventional physical keyboard.

In an effort to address the slow speed of typing using an on-screen keyboard, predictive software was developed that attempts to predict what word is being typed based on previous words, as well as based on the starting letter typed for the current word, and provides the user with a list of alternative words or phrases that they may select as a faster alternative to completing the word or phrase letter by letter. This "word prediction" scheme only slightly increases the speed of text entry, if any (depending on the user), since attention needs to be diverted from the task (typing) at hand in order to scan the prediction list and determine if the intended word is provided as an alternative.

As the size of the on-screen keyboard is reduced beyond a certain level, the speed of text entry is dramatically reduced. This is due to the need to improve the accuracy and dexterity of hitting smaller targets. Various methods have been proposed to minimize the size of the keyboard while still maintaining accuracy without unduly sacrificing input speed.

Grover et al in us patent #5818437 describe a system that reduces the number of different keys required by assigning multiple letters to each key. For a given size keyboard, this allows the individual keys to be relatively larger, thus making it easier to hit the individual keys accurately, allowing the user to type faster. The input in such a system is word-based, whereby disambiguation software uses a database of words to analyze each sequence of keystrokes and determine the most likely word corresponding to that sequence, thereby determining which letter each ambiguous keystroke actually expects. While the system of Grover et al makes it easy to hit the intended key by reducing the total number of keys and enlarging individual keys, it still requires the user to lift and drop a stylus for each letter entered, significantly slowing text entry when implemented on a touch screen device. Furthermore, this approach requires the user to adapt to a very unfamiliar keyboard layout in which totally unrelated letters are centered on a single keyboard. Even when arranged in an "alphabetical" layout (the same as on the keypad of a mobile phone), this arrangement is unfamiliar to most individuals and reduces the progress of text entry compared to a standard keypad.

Lee in us patent #6292179 describes another system that reduces the number of different keys required on a touch screen keyboard by assigning multiple letters to each key and determining which letter associated with the touched key is desired by determining the direction of movement of the stylus after touching the key. Each letter associated with a key is further associated with a column of directions in which the point of contact may move. The Lee approach also allows each key of a given keyboard to be relatively large and thus easy to make initial contact, requires a smaller number of keys due to multiple letters being combined on one key, and requires the point of contact to be moved in a particular direction before the stylus is lifted and contact with the screen is completed.

Kaehler, in U.S. patent #5128672, describes a system that reduces the number of different keys required for a touch screen keyboard by displaying only a subset of the total set of characters that can be entered at a given time. The attempt determines a character combination including the next character to be input based on the position of the previous character input or the text insertion point. When the character is not present, the user must manually switch to a different keyboard to locate and enter the desired character. A large number of different (and often changing) incomplete keyboards will tend to make most users perceive this to be a slow and frustrating input method.

Vargas in us patent #5748512 attempts to reduce the required precision (and thus speed) on touch screen keys by treating two adjacent keys as possible candidates when the key is not activated in its central region. Based on the location of contact with respect to the three keypad, in conjunction with statistical analysis of the top characters (if any) in the word being entered, and optionally also using information from the word prediction engine, the system determines the most likely three possible candidate characters and displays them as the characters to be entered in response to activation. However, since each character forms the basis for predicting the next character once entered, when the character prediction is incorrect, it must be corrected before the user can type the next character. In the system described, the contact point is slid in the direction of the actual intended letter, by maintaining contact with the keyboard during activation, observing whether the predicted character is correct, and if necessary. As mentioned, an advantage of this invention is that it can enable a user to use a blunt object (such as a fingertip rather than a pen tip) to activate a keyboard key that is actually smaller than the activation tool. However, the nature of the feedback provided to the user, and the subsequent need to observe the results of each keystroke and correct it before moving on to the next keystroke, causes the resulting system to typically significantly reduce the rate of text entry.

Robinson et al in International patent application WO 00/74240A 1 describe a text input system for a touch screen device that includes a keyboard having an auto-correction zone that includes a set of keys associated with letters. The advantage of this system is that for words included in the system database, the user does not need to touch the area within the key associated with the intended letter, but only needs to hit the adjacent area of the key. The user taps the keyboard once for each letter in the word being entered, and the system records the location of each touch. The sequence of contacts is compared to the locations of the keys in the database associated with the words and one or more of the most likely matching words are provided to the user for selection. This system is a significant improvement over the previous approach in that it no longer requires precise contact in the area of each intended key so that the user can type faster on the keypad. However, for each key activation, the user still needs to target the intended key on the screen with the control, then lift the stylus from the screen and move the alignment to the next key. The extra movement of raising and lowering the stylus for each letter, and the extra effort required to control its repositioning when the stylus is not in contact with the screen, results in a significantly reduced progress of input compared to the system of the present invention.

Another factor in the slowness of text entry on a touch screen keyboard is the time it takes to lift the stylus from the screen and put it back in between each key selection ("tap"). Us patent 5574482(Niemeier) discloses a method for entering data on a touch sensitive screen. The Niemeier patent describes computer-generated "temporary" adjacent keys that may be made to appear on top of a standard keyboard layout. When the user touches a key, the first letter is selected, and one or more temporary keys are displayed adjacent to the touched key as long as the initial contact is maintained. A second letter (or group of letters) is displayed on the adjacent key by sliding a finger or stylus from the first selected key to the adjacent momentary key in a wiping motion. Can be selected by performing a motion called "wiping" in which one finger or stylus slides from a first selection key to an adjacent "temporary" key. This method allows two (or more) adjacent letters to be entered without lifting the stylus from the screen, suitably reducing the number of times the stylus needs to be lifted from the screen by half. The "temporary" contiguous keys generate a manual grouping of the most likely letters to provide more opportunities for "wiping" the input.

However, the method described by Niemeier has several significant drawbacks. One is that the user either needs to remember 26 new "temporary" sub-keyboards that appear when each 26 letters is touched (to generate an important learning curve for efficient use of the system), or the user needs to pause to see if and where the next expected letter appears on the temporary key, which may negate any speed advantage provided by the "tap and slide" method. To increase the likelihood of the expected letter occurrence, the method becomes even worse when the temporary key displayed for each key is changed using a dictionary or other database based on the context of the last letter selected prior to activation of the key. Furthermore, as described above, the system is limited to sliding to at most one additional key in addition to the initially selected key, unless subsequent letters also happen to appear on keys adjacent to the selected transient key. Furthermore, the number of keys that can be displayed (and thus selected) is limited to the number of keys that can be displayed around a single key (6, up to 8 for a standard key arrangement according to the Niemeier recommendation). Moreover, because the temporary keys are only displayed when the stylus (or finger) is actually touching the screen, a large number of keys that may be displayed may be partially or fully obscured by the stylus or the user's finger. The system proposed by Niemeier also includes a large amount of space between the active keys (for capitalization and spacing), reducing the size of the actual key targets that must be contacted inside the determined key area in order to affect activation of each key target.

A similar system is described by Van kleeckza in us patent #6008799, where the "temporary key" is never actually displayed, but in which the four vowel letters "o", "e", "i", "a" are implicitly associated with each letter key and can be added by tapping the character button and dragging the pen in the north, south, west or east direction. This method, however, is easier to learn than the Niemeier method (since only four vowel letters and their associated directions must be learned) and is not affected by the potential visual obstruction of the user's hand (since there are virtually no temporary keys to be displayed), is limited to adding only one of the four specific letters following a key selection, and therefore does not provide a very significant improvement over the standard keyboard.

Perlin, in us patent #6031525, describes a method in which the stylus is never lifted from the touch screen, but is directed from a critical point in the middle ("stop band" in the Perlin technique) to one of a plurality of surrounding areas, each of which includes a plurality of letters. The user needs to touch the screen at the rest area and then perform a continuous sliding action, which for each letter to be entered, passes from the rest area into the adjacent area containing the intended character, and then indicates which character contained in that area is intended, either by returning directly to the rest area or by first passing to a different area before returning to the rest area. Thus, in combination with the area from which the rest area is rejoined again, the intended character is indicated by the union of the areas input from the rest areas for the first time. As a result, the user needs a minimum of 2 strokes, typically 3 strokes, of the stylus to indicate each intended letter. This approach allows for a smaller keyboard, but requires multiple strokes per letter, which significantly slows the speed of text entry.

Another common method in accelerating text entry is to modify the layout of characters on the keys of an on-screen keyboard (see www.fitaly.com). The usual letters are located near the center of the on-screen keyboard and the usual pairs of letters are located adjacent. In this way, the movement of the stylus between letters is reduced, thus speeding up text entry. The disadvantage of this approach is that it requires the user to learn a new keyboard layout and also requires the user to lift the stylus between each key activation, essentially turning the user into a finger typist.

Each of the above methods has the potential to speed up text entry to some extent and/or reduce the amount of screen real estate required for input. However, the speed of text entry via existing on-screen keyboards and handwriting recognition techniques is still slower than with physical keyboards. The writing itself is only too slow and the accuracy of the recognition still does not meet acceptable standards. All of the keyboard-based approaches described above require one or more separate and distinct actions to enter a single letter. Most of the proposed keyboard systems are based on hitting some type of key, so that generating a single character requires properly positioning the stylus, touching the screen keyboard, and lifting the stylus again from the screen before entering the next character.

The fundamental problem is that the extra act of lifting the stylus and bringing it back into contact with the screen in a controlled manner, especially for devices that have to use a touch screen keyboard of reduced size, greatly reduces the input process. Other proposed methods for reducing the number of times the stylus must be lifted from the screen (such as Niemeier and Perlin) still fail to provide a method that can significantly increase the speed of text entry. The system proposed by Niemeier adds much complexity by requiring the user to react to a constantly changing keyboard layout and limits the number of characters that can be selected after initial character selection. The reason why Perlin's method is not useful is that it requires the user to perform too many different stylus movements to enter each character.

Disclosure of Invention

The method of the invention is characterized by the fact that the use of continuous motion in the touch screen significantly reduces the number of controlled movements that must be performed to input each word. This significantly increases the speed of text entry. The present invention uses word-level analysis to match the input pattern depicted on the keyboard to the most likely words in the system database. The user is provided with a list of recognized matching words and can either accept a default selection (the system identifies the word as the most likely match) or select one of the alternative words or request that the system display a more potentially matching word if the intended word does not appear in the list. When a word is selected for output immediately after a previously output word, the system automatically outputs a space before the selected word is output, eliminating the need to perform additional actions on a large number of typed space characters. The system also includes a simple and straightforward alternative method to enter new words that have not yet appeared in the system database and automatically add them to the database for future input using the continuous stroke method.

The method of the present invention has significant advantages over previous systems, such as those disclosed by Niemeier and Perlin. One point is that the keyboard displayed by the system remains unchanged and the same words always appear in the same location. This is in contrast to the system suggested by Niemeier, where a different set of temporary keys appears each time the screen is touched, allowing the user to observe and dynamically change the layout accordingly. Furthermore, this allows the method of the present invention to be used with static keyboards that are embossed on less costly touch sensitive films rather than touch sensitive dynamic displays. A second advantage is that it saves considerable motion. It is only necessary to bring the stylus into contact at the beginning of each word and lift the stylus at the end of each word. As will be described below, in most cases, no additional action is required to correctly generate a space between each generated word. Also, in contrast to the system of Perlin, it is only necessary to move the stylus directly from letter to letter of the word being input, rather than having to perform two to three different strokes per letter. A fourth advantage is that, like the Robinson system, the individual letters of a word do not need to be in precise contact with the stylus. The stylus need only be brought into proximity with each word in sequence, and need not necessarily pass directly through the area defined by the keys associated with the word. When words are entered with a relatively high frequency of use, the system allows the user to move the stylus relatively less accurately (and thus more quickly) accordingly. This greatly increases the overall input speed as it allows the user to input the words that tend to be the most commonly used words most quickly.

The present invention provides a keyboard text entry system for a device having a touch-sensitive input panel or touch-sensitive display screen. More particularly, the present invention provides a system and method that enables a user to input text word by word using a keyboard displayed or printed on a touch-sensitive display screen, wherein contact with the display generates an input signal to the system corresponding to the location of the contact. The user enters a word by making contact with the screen, tracing a continuous graphic that passes through or near each letter of the word in sequence, and breaking contact with the screen when the last letter of the word is reached. In another aspect, the keyboard is displayed on a touch-sensitive display screen (hereinafter referred to as a touch screen) and the user contacts the display with a stylus. However, it should be understood that the system may be applied to any system in which a user may trace a continuous path on a display keyboard, such as a touch screen in contact with the user's finger, or even a standard computer monitor (not a touch screen) in which the point of "contact" in the computer monitor is the position of a cursor on the screen, in which the position of the cursor on the display is controlled by a mouse (or similar control device), and in which the actions of "contacting" and "breaking contact" with the screen are indicated by closing and opening a switch (or performing some other control action, such as "dwelling" near a location without moving the mouse for a period of time longer than a selected threshold). The operation of the system will refer to aspects including a touch screen contacted by a stylus, but should not be taken as limiting the scope of the invention, but merely as a means of providing a description of some of the current aspects of the method.

The system of the present invention allows the user to enter text words without having to place the stylus on the screen to touch the intended letter and then lift the stylus again from the screen before touching the next letter-i.e., without having to tap each letter. Maintaining contact between the stylus and the screen allows for more precise control over the location of the contact to be maintained in general, which allows the user to enter text more quickly, since no extraneous actions of raising and lowering the stylus need be performed, and since by helping to stabilize the relationship between the stylus and the screen. Moreover, it generally allows the displayed keyboard to be reduced in size significantly overall, since the path traced by the user does not need to touch exactly every letter of the intended word. In the range where the keyboard size is not greatly reduced, the input speed can contribute to a corresponding increase.

The path traced by the user on the touch screen and recorded by the system for analysis is referred to as the input pattern. When the user traces the input pattern on the touch screen, the system records the sequence of contact points detected by the touch screen control hardware. When the input pattern is recorded, it is processed by the input pattern analysis component. The input graph analysis component body extracts the data needed by the graph matching component, which compares the extracted data to words in a database to identify a list of one or more candidate words determined to be the most likely matches. One or more of these identified words are provided to the user for selection, and the selected words are added to the text being entered by the user.

In another aspect, the text input system includes: a keyboard disposed on the touch-sensitive display screen, wherein the location of each displayed text character key is determined by screen coordinates of the center of the key, which is the location used when determining the distance of the letter associated with the key from any point on the keyboard; a record of an input pattern consisting of the coordinate positions of a series of contact points, said contact being detected from a first position of contact by the position of the stylus lifted from the screen; analyzing the input pattern to determine locations associated with one or more of the one or more inflection points and calculating a distance between each determined location and a location associated with a text character key; a database of words, which words may be entered using the system; determining those words that best match the determined location of the inflection point; and means for allowing the user to select the intended word from the set of candidate words determined to be the best match. In another aspect, the distance from a point on the input graphic to a letter associated with a key is determined to be 0 when the point is located within the boundary of the key and otherwise determined to be the distance from the point on the input graphic to the closest point on the defined boundary of the key.

The term "letter" in the context of the present invention is understood to include any character that appears in one or more words of the spell database. Thus, for example, if the word "can't" is in the system's database, it may be entered by tracing a path that starts near the letter "c", passes through or near "a" and "n", then passes through or near the key associated with the apostrophe, and ends near the letter "t". Similarly, words concatenated with hyphens, words mixed alphabetic and numeric, and other words that include special characters may all be included in the database and entered as text using the system of the present invention, so long as each character used in the database is associated with at least one key on the keyboard.

In another aspect, the input pattern analysis component first applies a smoothing process to the sequence of recorded contact points to reduce the amount of "waving", which may be introduced by any back-and-forth inconsistency in the touch screen digitizer reporting the coordinate position of each recorded contact point. Algorithms for smoothing the sequence of data points are well known in the art, and any of a number of such algorithms may be used for this purpose. The input pattern analysis component then analyzes the path to identify "turning points" at which the path changes direction in a greater manner. Such turning points can be detected and extracted by a variety of analytical methods as described below. In an alternative aspect, the method of detecting multiple turning points is associated with different confidence levels that are actually associated with the location of the key associated with the letter of the word being entered, and in turn with different methods of weighting the distance from the keys of the input path, where, for example, the horizontal and vertical distances of the keys in the path may be weighted differently. Thus, when the input pattern analysis determines that the inflection point is of a type whose location can be accurately determined and there is a high likelihood that the inflection point actually corresponds to the letter of the word being input, the location of the potentially matching word in the database that is considered to be the more closely corresponding letter of the more likely matching word will be determined. When a turning point is determined to be a less reliable type, the likelihood of determining a potentially matching word will be less affected by the distance from the corresponding letter of the turning point.

In another aspect, the input pattern analysis component determines a sequence of first and second order (order) differences (equivalent to rates of change) in the sequential x-and y-coordinates of points in the input pattern. The ratio of the x and y first order differences corresponds to the "slope" of the input pattern for each point, such that the second order difference corresponds to the rate of change in slope. A second order difference staying around 0 corresponds to a segment of the input pattern, which is a relative straight line. A small, relatively constant second order difference represents a constant ratio of change in slope corresponding to a segment of the input pattern having a slight constant curvature. The fixed point or sharp change in the second order difference corresponds to a relatively sharp change in the direction of the input pattern. In another aspect, since the first and second order differences are also a function of frequency and velocity at which the operating system samples and collects contact location data points, the user moves the contact point at that velocity and calculates the first and second order differences for two points along the input path for a fixed distance from a given point before and after the input path. In another aspect, to simplify the computational requirements, a fixed distance is estimated by a fixed summation of the absolute amounts of the x-and y-first order differences. In yet another embodiment, when the system detects that the input path has traversed itself within a circle (the input of a small circle within the DOUBLE _ LETTER stylus command input as defined below), the amount of fixed distance used is reduced to approximately the radius of the circle, and the amount of second order difference calculated is scaled by the ratio of the standard fixed distance to the reduced fixed distance used.

In another embodiment, the input pattern analysis component identifies 5 different types of turning points in the input pattern: PEN _ DOWN, the position at which the stylus first makes contact with the touch screen; PEN _ UP, recording the position of the PEN disconnected from the touch screen; ANGLE _ THRESHOLD, the location where the sum of the absolute amounts of the X and y second order differences reaches a local maximum, exceeding a predetermined minimum THRESHOLD; ROW CHANGE, a location between two consecutive turning points of another type, where the y coordinate reaches a maximum (or minimum) value, occurs in a ROW of the keyboard, where the keyboard is located above (or below) the ROW where the two consecutive turning points are located; and a TAP for raising the position of the stylus more or less quickly after touching the screen, according to the words of a letter or selecting a single function key.

In another aspect, the input graph analysis component identifies more than one category of ANGLE THRESHOLD inflection points according to a set of predetermined ranges within which a maximum value obtained by the second order difference summation falls. Alternatively, the maximum obtained by the sum of the second order differences is used in a function that applies differential weights to the distances associated with the different turning points. In another aspect, the ANGLE _ THRESHOLD inflection points for two or more categories (or subcategories) are determined according to the length of the input graphics path between the point at which the second order difference first exceeds a predetermined minimum THRESHOLD and the point at which it again falls below the minimum THRESHOLD level. In general, the shorter length of the segment corresponds to a "sharper" angle and the longer length of the segment corresponds to a "rounder" angle.

On the other hand, another type of turning point is determined, which corresponds to a predetermined type of stylus movement that the user needs to perform in order to be a DOUBLE-LETTER (DOUBLE _ LETTER) only input. To illustrate this, consider the possible inputs of the words "feel" and "fell". To input any word, the user contacts the touch screen at or near the key associated with the letter "f", passes or approaches the key associated with the letter "e", moves the stylus to or near the key associated with the letter "l", and lifts the stylus from the screen. For a properly entered graphic, without such a type of DOUBLE _ LETTER break point, it is not possible to separate them from each other, since only one can be displayed as a default value (automatically accepted), so that the user always explicitly selects one of the two word forms. When the type of DOUBLE _ LETTER inflection point is included, a distinguishable motion will be performed at or near the key associated with the LETTER "e" for the case of the word "fell" and at or near the key associated with the LETTER "l" for the case of the word "fell", so that the system can distinguish the input patterns of the two words. On the other hand, the motion associated with the type of DOUBLE _ LETTER inflection point is that of a small circle of the stylus at or near the location of the key associated with the word to be repeated. The position of the DOUBLE _ separator turning point is determined as the center of the small circle depicted by the user. On the other hand, each successive additional repetition of the motion associated with the DOUBLE _ LETTER transition point represents an additional occurrence of the LETTER in the word being input. For example, by entering the word "AAA" by touching the screen at or near the key associated with the letter "a", two small circles are performed with the stylus and the stylus is lifted from the touch screen.

It is difficult for the user to determine how many "small circle stylus commands" have actually been executed, based on the relationship between the direction of the double-letter key input and the direction in which the input path continues when the key is left. In another aspect, the system handles additional repetitions of motion in the same manner as motion is performed separately. In this regard, one or more repetitions of the movement are matched to an arbitrary sequence comprising two or more consecutive occurrences of the same letter, or alternative forms of the same letter, in a word. In yet another aspect, when a small circle (loop) is detected in the input pattern that does not complete a complete 360 ° change in the slope of the input path, the selectable categories of the DOUBLE _ left 2 inflection points that are matched by the system are identified as the ANGLE _ THRESHOLD inflection point and the DOUBLE _ left inflection point, and an appropriate interpretation is selected for each evaluated candidate word that best matches that word. Examples of such turning points may be found in the input paths of the input words "fed" and "feed", where there may be uncertainty in whether the traced path tends to contain a two-letter light pen command. The reroute may begin within the "f" key, continue up to the "e" key, and in continuing down to the "d" key, the route may inadvertently loop to the right and back down through itself, depending on the user's habits in tracing the input route. Assuming that the path passes through the center of each key (for a correctly identified ideal path), the slope of the path between entering "e" and exiting the "e" key changes by only about 220 °. Meanwhile, since a small closed circle has been depicted on the "e" button, the path may appear to be perfect to correctly execute the DOUBLE _ LETTER light pen command (GESTure) to a user who wants to input the word "feed". On the other hand, when matching multiple LETTERs to a single LETTER, a separate additional adjustment factor is considered for use in the manner of the point of inflection of the DOUBLE _ LETTER 2. When the DOUBLE _ LETTER2 inflection point matches a single LETTER, or when it matches a DOUBLE LETTER, the identification determines whether the adjustment factor is added to the Matching _ Metric considered for the candidate word. When the small circle traced by the user does not complete a full 360 change in slope, and the word selection list includes words that match the single letter and the double letter, the system determines which of the two selectable words is selected by the user for output. When the user's option appears lower in the selection list than the corresponding alternative word, an incremental change is made in the adjustment factor (the associated identification value, when necessary) for the point of inflection of the DOUBLE _ LETTER 2. This allows the system to better accommodate users who are accustomed to generating small circles at turning points where the path "reverses" the direction of the x-and y-components, as in the present example. In another aspect, separate values for the markers and adjustment factors are calculated for different ranges of degrees, and the slope is varied in accordance with the degrees in completing the circle light pen command.

In another aspect, the input pattern analysis component analyzes the input pattern as it is being entered so that once the stylus is lifted from the screen, the pattern matching component can identify potential matching candidate words with little or no delay. The location at which the screen was first touched is recorded within the system as the inflection point first detected and identified as a PEN _ DOWN type of inflection point. In case the stylus is lifted from the screen again without moving more than a threshold distance or remaining in contact with the screen for more than a threshold period of time, the first turning point is recorded as a separate turning point of the TAP type. In another aspect, when the contact location data is accepted from the touch screen controller, it is immediately processed by a smoothing algorithm to eliminate any jitter caused by the touch screen digitizer. The smoothed data is then used to calculate first and second differences in the data stream in x-and y-coordinates. The data stream of second difference data is then passed through a filter to determine when the sum of the absolute values of the x-and y-second differences exceeds any of one or more THRESHOLDs determined to be ANGLE THRESHOLD type inflection points. Whenever any such THRESHOLD is exceeded, the ANGLE THRESHOLD type inflection point is identified at the contact location determined by the data point at which the sum of the absolute values of the second differences takes its maximum value before it falls below the exceeded THRESHOLD again. When the stylus is finally lifted from the touch screen, the last touched position of the screen is recorded in the system as the last detected inflection point and identified as a PEN _ UP type inflection point.

In another aspect, after identifying the first PEN _ DOWN inflection point, each time an additional inflection point is identified, the data from the previously identified inflection point to the most recently identified inflection point is analyzed to determine whether additional inflection points of the ROW _ CHANGE type can be identified. When a recorded input path segment between a previously identified turn point and a most recently identified turn point crosses into a keyboard row that is higher (or lower) than the row containing the two identified turn points, there is a reasonable likelihood that the path segment will enter a row containing one or more letters of the word being input, even if there is no identified ANGLE THRESHOLD turn point. The system identifies the maximum (or minimum) height obtained by the path segment and identifies the turning point of the ROW CHANGE type at the corresponding location. On the other hand, since the environment provides additional evidence: one or more turning points may occur along the path segment, with the path segment first being re-analyzed to identify whether one or more turning points of the ANGLE _ THRESHOLD type can be identified with a THRESHOLD of a lower criterion for the second difference. If the lower THRESHOLD is not exceeded and no ANGLE _ THRESHOLD inflection point is identified, then an inflection point of ROW _ CHANGE type is identified as described above. An important difference between the ANGLE _ THRESHOLD inflection point and the ROW _ CHANGE inflection point is that: in performing pattern matching analysis, the ROW _ CHANGE inflection point is not required to match the letters of the candidate word. In order for a user to enter text at the fastest rate possible with the system, it is desirable to impose as many restrictions as possible on how the input path is drawn. The present invention makes this easy by allowing the user to deviate from the direct path without being penalized in the correct recognition operation. By following a reasonably straight path between letters falling on the same row of the keyboard, and by being able to bend upwards through the keys of adjacent rows without having to cause unusual and artificial "sharp" changes in direction, both the speed of entry and the accuracy of recognition of the input pattern can be improved.

After the input pattern analysis component identifies the inflection points associated with the input pattern, the pattern matching component examines the words stored in the system database to determine which word is the most likely matching candidate word. The aspects described herein are simple and computationally efficient methods to identify which word in the database best matches the input pattern, it being understood that other alternative methods may achieve such goals and should not be considered as beyond the scope of the present invention.

In another aspect, the words in the database are organized in a manner that is easily and efficiently searched by the pattern matching component. Since each input pattern has two easily and reliably identified inflection points, first (PEN _ DOWN) and last (PEN _ UP), which both always match unambiguously the first and last word of the word being input, the words in the database are organized in groups according to pairs of keys, which are associated with letters comprising the prefix and the last letter of each word. The pattern matching component simply identifies the set of keys that are within a threshold distance from the PEN _ DOWN transition point and the set of keys that are within a threshold distance from the PEN _ UP transition point and only examines those word groups that have the initial and last letters associated with the identified set of keys. In this way, the number of words in the database that must be evaluated is greatly reduced, allowing the system to function efficiently enough, even in devices with relatively low-powered processors.

An additional feature of the input pattern that can be easily and reliably recognized by the input pattern analysis component is the total length of the path of the input pattern. Since words may have a small number of letters that are spaced more apart (e.g., "ape") or a larger number of letters that are spaced more closely together (e.g., "determined"), the length of the input path cannot be reliably related to the length of the word in terms of the number of letters in the word. However, for any given keyboard layout and screen structure, the average expected length of each word is easily calculated. In another aspect, the expected length of a word is calculated as the sum of the distances between the centers of the keys associated with the sequential letters of the word. In the example of the word "ape", this would be the sum of the distances from the "a" key to the "p" key, plus the distance from the "p" key to the "e" key. Since the expected path length is only an expected approximation of the actual input pattern for a given word, on the other hand, the range of expected path lengths associated with words of the database is divided into a relatively small number of ranges, each such range being associated with a word class whose expected path length falls within that range. The expected input path length category associated with each word may be stored with the word without significantly increasing the size of the database, or alternatively, the words in the database may be stored in groups according to the expected input path length category. In another case, because the pattern matching component utilizes the actual length of the input pattern as measured by the input pattern analysis component, just ignoring words that belong to significantly different classes of expected input paths, the number of words that need to be examined in detail by the pattern matching component is greatly reduced. In another aspect, the word selection component calculates a moving average of the ratio of the actual measured length of the input pattern to the expected input path length class of words selected for output, which the pattern matching component uses to determine which expected input path length class will be examined for a given measured input pattern path length.

In another aspect, based on the expected input path length category to be examined and determining candidate pairs of the first and last letters for the current input pattern, the system determines which words in the database qualify as potential matching candidates, which must be evaluated by the pattern matching component. In another aspect, the number of candidate words is further limited by determining the total number of inflection points identified as any of the categories PEN _ DOWN, PEN _ UP, or ANGLE _ THRESHOLD. The total number of inflection points corresponds to the minimum number of letters that the candidate word must contain (since the ROW _ CHANGE inflection point does not need to dematch letters). Candidate words may also contain more than this minimum number of letters, since the input path may pass through or near the letters of the word without the need to generate a turning point.

Another feature for limiting the number of words in the database that need to be evaluated is the expected minimum number of inflection points in the input pattern. As described above, words having the same expected input pattern path length may vary greatly in the number of letters of the word. The number of letters and the continuous set relationship between them on the keyboard can be used to determine the minimum number of turning points required. In another aspect, for each word in the database, the graph of oriented line segments connecting each successive pair of keys associated with a letter in the word is analyzed to determine the number of instances where the angle between the input and output line segments on the keyboard exceeds a predetermined threshold. This number is recorded with the word as the minimum number of ANGLE _ THRESHOLD inflection points that must appear in the input pattern to qualify the word as a potential matching candidate. The pattern matching component evaluates each determined candidate word in the database by computing a matching metric that reflects the degree to which the input pattern corresponds to the word. The match metric is a function of the alphabetical distance of a word from a series of points along the input pattern from which the distance is calculated, where the points of the input pattern must appear in the same sequence as the letters of the word. In one aspect, the inflection point of the PEN _ DOWN, PEN _ UP, or ANGLE _ THRESHOLD type must match the letters of the candidate word, such that the distance from the key with which the letter is associated to the inflection point is included in the calculation of the match metric function. If a ROW CHANGE inflection point is also identified and there are one or more unmatched letters between inflection points on the ROW CHANGE inflection point on each side, one of these unmatched letters must be matched to the ROW CHANGE inflection point so that the distance from the key with which the letter is associated to the ROW CHANGE inflection point is included in the calculation of the matching metric function. The distance to any additional unmatched letter is measured from the closest point along the input pattern between the points at which the distance to the letter is measured immediately before and immediately after the unmatched word and is also included in the calculation of the matching metric function.

In another aspect, the distance from the input pattern to any potentially matching letter is compared to a maximum threshold distance, such that whenever a letter is found to be farther than the threshold distance from any possible matching point in the input pattern, that word is deleted as a possible candidate. Since this is sufficient to speed up the evaluation process as long as the pattern matching algorithm identifies the letters of words that exceed the threshold distance from any possible match point on the input pattern, the algorithm immediately continues to evaluate the next candidate word.

In one aspect, the matching metric function is calculated as the sum of the distances from the identified inflection points to the keys associated with the letters with which the inflection points match, adding that distance to any unmatched letters, where each letter is measured from the closest point along the input pattern as described above. In another aspect, the matching metric function is computed as the sum of the squares of the distances. In another aspect, a weight function is applied to each distance (or squared distance) prior to calculating the sum, wherein the weight applied to each distance is determined according to the type of turning point from which the distance is measured. To normalize the results so that the metric can be used to purposefully compare results between words to different numbers of letters, the weighted sum is segmented by the sum of the weighting factors used in calculating the sum. In one aspect, the weighting function multiplies each distance by the following factors: for PEN _ DOWN, PEN _ UP, or DOUBLE _ LETTER type is 3; type 2 for ANGLE _ THRESHOLD; type 1 for ROW _ CHANGE; the distance measured from a point on the input pattern different from the turning point is 0.5. Different expected confidence levels are reflected with different weighting factors at different turning points, the confidence level being that a turning point of a given type is precisely located and that in fact the detected turning point reflects the fact that the letters of the word being input will be located nearby.

In another aspect, the x-and y-components of the distance are weighted differently, depending on the type of turning point from which the distance is measured. In particular, in the case of the ROW CHANGE inflection point, it is reasonable to expect a relatively accurate reflection that the vertical y-coordinate of the location of the inflection point is the vertical location of the expected letter, but the x-coordinate location may differ significantly from the expected letter for sufficient reasons. In this case, the y-component of the distance is weighted more heavily than the x-component of the distance. Significantly reducing the weight applied to the x-component of the distance avoids placing inappropriate weight on the horizontal position of the turning point when the horizontal position cannot be reliably determined.

The problem of identifying the best match between the M letters of the candidate word and the N identified turning points and the input pattern path segments is a variation of the "shortest path" problem, which is well known in the field of dynamic programming. Different algorithms, such as the Floyd-Warshall algorithm, have been designed to solve the problem of finding the shortest path through an edge-weighted graph (edge-weighted graph) from a specified starting vertex to a specified ending vertex. A typical problem is to simulate in some way the problem of identifying the best match between the turning point and the insertion path segment of the input pattern and the position of the key associated with the letter of the potential matching candidate word. Such algorithms are relatively complex and time intensive (belonging to the class of N3 for graphics with N vertices). However, the current problem is made easier to handle due to several important additional limitations:

1. the first and last letters of the candidate word must match the PEN _ DOWN and PEN _ UP inflection points, respectively, and the order of the letters in the spelled word must match the order in which the inflection points occur.

2. Each turning point must match a letter.

3. The number of letters that can potentially match a given turning point or path segment is limited to the letters that occur in the MAX _ DISTANCE of the point or segment, greatly limiting the number of possible methods that will be evaluated.

4. Once a inflection point matches a letter, each remaining unmatched word must match a path segment connecting inflection points matching the nearest previous and next matching letters.

In combination with the above limitations, the fact that the nature of the input method generally produces an input pattern of N turning points of M-letter words makes it possible to design a matching algorithm based on a heuristic that exhibits a minimum number of recursions in operation and therefore operates efficiently even on devices with limited processing power, where M is not very large compared to N. The first thing among these is that for (N-2) turning points that need to be matched with letters, there are at most (M-N) letters to be considered.

In one aspect, the pattern matching component utilizes the following algorithm to match the letters of the M-letter candidate words with the N inflection points determined as the input pattern. The first (PEN _ DOWN) inflection point always matches the first letter of a word, and the last (PEN _ UP) inflection point always matches the last letter. The variable Match _ Lim is initialized to (M-N) and tracks how many letters after the next unmatched letter need to be considered as possible Match candidates for each successive inflection point as the algorithm continues. The arrays MATCH [ ], RECURSE [ ], and BACK _ TRACK [ ] [ ] and the variable RECURSION _ LEVEL are all initialized to 0, and the system is tracked as being required to retrace there when multiple possible methods are found. For each subsequent inflection point, the system determines how many letters after Match _ Lim that have not yet matched can be matched with it. If not, and RECURSION _ LEVEL is set to 0, then the current word is not a candidate and the algorithm returns a failure code. If there is only one, it matches the turning point and the system determines if all letters that have not previously matched can match the previous path segment. If any previously unmatched letter cannot be matched with the previous path segment and RECURSION _ LEVEL is set to 0, then the current word is not a candidate and the algorithm returns a failure code. Otherwise, each letter that has not previously matched matches a previous path segment, and Match _ Lim is reduced by the number of such letters. For each matching inflection point, the entry of the corresponding MATCH [ ] is set to the index of the letter, which matches the index. If a break point J can Match more than one of the following Match _ Lim unmatched letters and in all cases any of the previous unmatched letters can Match the previous path segments, the best matching letter is temporarily matched to the break point, BACK _ TRACK [ J ] [0] is set to a value less than the number of letters K, the remaining potential matching letters are stored in BACK _ TRACK [ J ] [1.. K ] in ascending order of best Match, RECURSE [ RECURSION _ LEVEL ] is set to J, RECURSION _ LEVEL is incremented, and the algorithm continues to attempt to Match the next break point. If the system determines that there is no likely match of letters to subsequent inflection points and RECURSION _ LEVEL is not set to 0, the system temporarily returns to matching the inflection point J ═ RECURSE [ RECURSION _ LEVEL-1] with the letters stored in BACK _ TRACK [ J ] [ BACK _ TRACK [ J ] [0] ]. The system decrements BACK _ TRACK [ J ] [0], and if BACK _ TRACK [ J ] [0] is decremented to 0, RECURSION _ LEVEL is also decremented. If the system determines a possible match for each turning point, the algorithm stops even if RECURSION _ LEVEL is greater than 0. Since the algorithm first selects the best match for each turning point with the possible matches, the first valid match identified may be the best match, and in any event, the constraints placed on the matches make it unlikely that multiple methods, even if they exist, have significantly different match metric values. FIG. 3D shows a flow chart of a preferred matching algorithm, which will be described in detail in the description of the preferred embodiment.

In another aspect, the pattern matching component employs another algorithm that performs a recursive process to match the letters of the candidate word with the inflection points determined as the input pattern. The first letter of a word always matches the first (PEN _ DOWN) inflection point, and the last letter always matches the last (PEN _ UP) inflection point. For each subsequent letter, the system determines whether it can match the current (next unmatched) inflection point. If it cannot, or alternatively, if the following letter is actually a better (i.e., closer) match to the current turning point, it is determined whether the current letter can match the current path segment at a point between the previous (already matched) turning point and the next unmatched turning point (if it also matches the current path segment, or the previous letter matches the point). If not, the current word is not a candidate, but if so, the current path segment is matched to the current letter at the determined point and advanced to the next letter to determine if it can be matched to a turning point that has not yet been matched. If, however, the current letter can be matched to the current (next unmatched) inflection point, then it is determined whether the next letter can be matched to either the next inflection point or the path segment, but if not, it is determined whether the current letter can be matched to the current path segment at a point between the previous (already matched) inflection points (if it also matches the current path segment, or the previous letter matched point), and if so, the current segment is matched to the current letter and advanced to the next letter to determine whether it can be matched to an inflection point that has not yet been matched.

In another aspect, the words in the database also include an indication of the frequency of use associated with the words. In calculating the match metric, the frequency of use associated with a word is combined with a weighted sum of distances, and the value of the match metric is used to determine the relative ranking of potentially matching candidate words. In one aspect, the matching metric is calculated as:

(Weighted_Sum_of_Distances)^＊(log(MAX_FREQ/Word_Frequency)+1)

where Weighted _ Sum _ of _ Distances is the value calculated by the graph matching component for the candidate Word, Word _ Frequency is the Frequency of use associated with the candidate Word, and MAX _ FREQ is the maximum value of the Frequency of use in the words of the database. In this formula, the smaller the match metric, the more likely the candidate word is to be considered as an expected match of the input pattern.

In another aspect, one or more words identified by the pattern matching component as the most likely candidate are provided to the user for selection by the word selection component. In one aspect, a predetermined number of the most likely candidates, e.g., 4, are displayed in a word selection list from which the user may select a desired word to insert the text being typed. In another aspect, if the user does not explicitly select a candidate word from the word selection list, when a subsequent input action is performed (e.g., the user begins to draw the next input graphic or selects certain characters for output), the default word choice (the word deemed to be the most likely candidate) is automatically accepted for insertion into the text being typographically. On the other hand, when the user takes no action for a threshold time after, for example, a word selection list, the default word choice is automatically accepted for insertion into the text being typed.

On the other hand, when a word is to be output immediately after a previously output word and inserted into the text being typographically, a single space is automatically inserted into the output text before outputting the word. This speeds up the entry of prose text significantly, since the user no longer has to explicitly activate the space key between each output word, and words can be input in succession as a continuous input pattern, with the appropriate spaces between words being automatically generated. Since no space is automatically output after each grade, when the user wishes to input a punctuation mark such as a comma or a period, there is no need to automatically delete the output space before inputting the punctuation mark.

In another aspect, the system records the length of time that the stylus is in contact with the touch screen while the input graphics are being traced. This allows the system to estimate the speed at which the user moves the stylus in the rendered input pattern. Given that it is reasonable that users will be faster in the input pattern that depicts words as a function of practice and proficiency, users can take advantage of the effect of applying higher weights to word frequency in calculating a match metric value for words in a database because more commonly used words will tend to input words that are less familiar to the user sooner.

On the other hand, additional time information is recorded with the input pattern, such as a sequence of time stamps of contact locations of the arctic road at fixed intervals (e.g. every 10msec.) so that the speed of stylus movement can be estimated along each point of the input pattern.

There are situations when the user realizes that he or she made an error in entering the current word, such as ignoring a letter, the stylus moved to an unintended position, or some other similar error. Since the system is always trying to find the best match and identify at least one default word choice, the user will have to lift the stylus from the touch screen, move to the button that cancels the current word choice list and activate the button. In another aspect, the input graphic analysis component identifies a "cancel" light pen command (gettrue), which can be made at any point in the rendered input graphic. In another aspect, the light pen command includes moving the stylus a threshold number of times back and forth, wherein the stylus moves faster than a threshold speed. In one aspect, the default number of movements is 3 times (e.g., right-left-right), and a minimum threshold speed of movement is automatically set (e.g., 5% faster than the fastest speed) based on the fastest stylus movement speed measured during entry of a user accepted word. High speed execution is easy since the "cancel" light pen command does not need to be precisely controlled or executed. The cancellation of the light pen command described in the present invention is simple and intuitive because it involves the feeling of simply "cluttering" the previously depicted input graphics. In another aspect, the system provides visual and/or audible feedback (e.g., a distinctive beep) whenever the input graphical analysis component identifies a Cancel cursor command. The user may simply lift the pen from the touch screen and begin inputting the desired word again. This feature is also useful when it is more appropriate for the user to determine different words midway through the input profile.

As described above, the pattern matching component compares the location of the inflection point extracted by the input pattern analysis component with the idealized location of the inflection point of a word in the database (corresponding to the center of the key for each associated letter) to rank potential word matches. On the other hand, in accordance with these detected customary input patterns, the algorithm further increases the interpretation of the pattern detected for a given user (e.g., a trend that is consistently hit in the target word but a certain percentage) by adjusting the location of the inflection points extracted from the input pattern. Whenever the user selects a word for output from the word selection component, the position of each inflection point is compared with the central position of the key associated with the letter in the output word, the inflection point being associated with the output word. In another aspect, an x-coordinate difference and a y-coordinate difference between two locations are calculated. The moving average of these differences is calculated for each type of inflection point (PEN _ DOWN, PEN _ UP, ANGLE _ THRESHOLD, ROW _ CHANGE, TAP, and DOUBLETTER). For the PEN _ DOWN and PEN _ UP transition points, separate moving averages are calculated based on whether the vector of the path of the input pattern (starting at PEN _ DOWN, or ending at PEN _ UP position) is positive or negative. For the ANGLE _ THRESHOLD inflection point, a separate moving average is calculated based on whether the corresponding second difference is positive or negative. Then, as each new input pattern is input, the x-and y-coordinates of each turning point extracted by the input pattern analysis component are adjusted by adding the average difference calculated for that type of turning point (or a predetermined fraction thereof). The pattern matching component then utilizes the adjusted locations of the inflection points to identify the intended word. The method allows the system to identify coherent trends in the user input pattern. For example, if the user exceeded the expected letters only when the user moved to the right to touch keys on the right side of the keyboard, and the user did not reach the expected letters only when the user moved to the left to touch keys on the left side of the keyboard, the pattern would be detected because the moving average (resulting in a negative second difference in the X-coordinate) is calculated separately for the ANGLE _ THRESHOLD inflection points appearing at the end of the movement of the stylus to the right and the moving average (resulting in a positive second difference in the X-coordinate) is calculated separately for those inflection points appearing at the end of the movement of the stylus to the left. When there is no continuous relationship between the type of inflection point and the expected key position, the moving average of the type of inflection point will be close to 0 and the adjustment will have a negative impact.

In another aspect, the input pattern analysis component identifies a single TAP on the keyboard as a TAP type inflection point. The pattern matching component processes the TAP type inflection point by first determining whether one or more one-letter words are present within a threshold distance from the inflection point, and if so, generating a word selection list containing the one or more one-letter words, with the one letter having the best match metric score displayed as the default word selection. Furthermore, after an alphabetical word, the letter associated with the key within the boundary of which the tap contact ("tap position word") occurred is also added to the word selection list (unless the letter has been displayed as an alphabetical word). If the user continues to trace the input pattern after the TAP contact, the default word option (typically a single letter word, but possibly the TAP position letter if none of the letter words are determined to be candidates) is inserted as a single letter word into the output text, just as the multi-letter default word option. If, however, the user continues to tap on the keyboard, the sequence of taps generates a word object that is composed of tap position letters connected in the order in which the corresponding key was tapped ("tap position words"). After the second tap, the word consisting of the tap position letters appears in the word selection list as the default word. The user selects the word (either by explicitly selecting from a word selection list or by continuing to depict the input graphic to enter the next word, so that the word selected for tapping is the word choice according to which it is the default), and inserts that word into the output text. On the other hand, whenever a word consisting of tap position letters is accepted for output into the text being generated, if the word does not appear in the database, it is automatically added to the user word list of words added by the user to the words that originally appear in the system's word database.

In many languages, it is common to use some letters in many alternative forms, typically consisting of letters with different distinguishable indicia. For example, other forms commonly used for the letter "e" include "ex", "e", and(other versions are possible-this is just one described example). Most on-screen keyboards require the user to select a particular alternate form to display one or more alternate keyboards from which the desired alternate alphabetic form must be selected. In the present invention, such alternate letter forms are handled in two distinct and advantageous ways. First, each alternative form of the letter used in the language of the words in the database is associated with the same key to which the basic form of the letter (in the present example, "e") is associated. Because the information specifying which alternate form of the letters is used in the spelling of the word is included in the database, the user can enter words having the alternate letter form as if they were a word not having the alternate letter form-i.e., just trace an output graphic that passes through or near a series of keys associated with the basic form of all letters in the word. Two words appearing in the database corresponds to just underWhere it is good for the same order of keys (i.e., the words are the same except for the presence of one or more alternate alphabetic shapes), the words will generally all be added to the word selection list, with the words having a higher frequency of use appearing higher up in the word selection list.

A second way of handling the alternative letter forms in an advantageous manner is to enter a new word consisting of a series of stroke position letters. In the present invention, the user need not select a replacement keyboard in order to explicitly select a replacement letter format to spell out a new word that does not exist in the database. In another aspect, the alternate letter form may be selected by contacting a key associated with the basic form of the letter and maintaining contact with the key (without sliding off of it) for a time exceeding a predetermined threshold length of time. Once the threshold period of time has been exceeded, a "pop-up list" of alternate letter forms associated with the key is displayed, at which point the user can slide the point of contact to the intended alternate form of letters in the list, lifting the stylus to select the alternate form as the tap position letter. The alternate letter forms are then added to the tap position words as usual so that the user can easily generate letters in any desired order without having to change the mode of the keyboard when spelling a new word that includes the alternate letter forms.

In another aspect of the invention, the keyboard layout is modified to enhance the ability to distinguish between input graphics that may be more difficult to distinguish. Since most users are familiar with it, a standard "QWERTY" keyboard is set up that most users prefer. The disadvantage of this arrangement is the approximation of the vowel letters "u", "i" and "o". Since the system is designed to allow the user to be inaccurate in tracing the graphics, and since these vowels are often interchanged among otherwise identical words (e.g., "hut," "hit," and "hot"), the approximation of these vowels in a standard "QWERTY" keyboard setting causes a large percentage of occurrences where the intended words cannot be provided to the user as default options. On the other hand, the increased width of the "i" key effectively increases the spacing between the centers of the three adjacent reason letters, resulting in easier and quicker positioning of the stylus relatively close to the three intended letters by the user. Since confusion between "u" and "o" and other adjacent letters is not a problem, it is not necessary to also enlarge the width of these keys. Also, the adjacent nasal consonant letters "n" and "m" are often replaceable, on the other hand, slightly increasing the width of the keys associated with "n" and "m" to increase the spacing between the centers of the keys.

On the other hand, by lengthening the keyboard in the vertical direction, the keyboard layout is further modified to improve the ability of the system to correctly analyze the input pattern. By increasing the distance between adjacent rows of the keyboard, the user can more easily and quickly trace out the input pattern that is defining the bitline segment and the inflection point within the actual row of the keyboard that contains the intended letter. This improves the performance of the pattern matching component since it greatly reduces confusion between candidate words that differ only in letters in adjacent rows (e.g., "hot" and "not"). The match metric calculated by the graph matching component can then be modified to apply an increased weight to the vertical component of the distance between the key of the letter of the candidate word and the location of the inflection point.

When the system provides the user with the intended word as the default word choice, no additional action by the user is required since continuing to depict the input graphic to the next intended word causes the default word choice to automatically output the text inserted into the line. When the system identifies the user's intended words with high accuracy, there may be a tendency for the word selection list to be less noticeable in order to quickly move from one word to the next, speeding up text entry. As a result, there may occasionally be situations where the default word does not correspond to the user's intended word, such that the unintended word is input to the output text, which the user must then edit to change to the intended word. In another aspect, the system allows the user to select a word to be edited anew in the output text, for example by double-clicking on the word to be edited or by highlighting the word and activating a designated edit function key. When a word is selected for re-editing, the system generates a simulated input pattern by generating a path that connects in sequence the centers of the keys associated with the order of the letters that make up the word. To avoid generating "artificial" turning points that are not likely to be present in the original input pattern, a smoothing process is first applied to the generated input pattern to avoid generating ANGLE _ THRESHOLD turning points at keys where the path of the input pattern changes direction only slightly. The smoothed input graphics are then processed by the system in the same manner as the user renders the input graphics. In another aspect, a longer word selection list is generated to increase the likelihood that the word that the user originally intended will appear somewhere in the selection list. Since the word being re-edited is very close to the original input pattern that will be selected as the default word choice, it is highly likely that the original intended word is very close to the generated input pattern that appears in the word selection list that was generated by the pattern matching component in processing the generated input pattern. A word is selected from the word selection list and the highlighted word is automatically replaced with the selected word for re-editing.

While the above description contains many specificities, these should not be construed as limitations on the scope of the invention, but as merely providing illustrations of some of the presently contemplated aspects of the process. For example, the input pattern may be analyzed in other ways, the word database may be organized in other ways, and the pattern matching component may use other algorithms to identify the most likely candidate word. For example, on a device with sufficient processing power, the order in which the letters of each word in the database are formed may be compared only to the input pattern, with the distance of each letter of a word being measured sequentially from the closest point on the input pattern that occurs later than the point at which the previous measurement was made. The basic understanding of the present invention is that text entry by using a touch screen keyboard is faster and more efficient when a familiar and constant keyboard layout can be utilized, but without having to lift the stylus from the touch screen in entering each word, and without having to pause or perform any other action other than tracing a path through or near each letter in sequence. The present system may use any type of touch screen and the input device may be a stylus, a finger or any tool that acts as an input device on a touch sensitive screen. The touch sensitive screen may be used by any type of computer or handheld computer capable of performing the required processing. The scope of the method should, therefore, be determined by the appended claims and their legal equivalents, rather than by the specific aspects described above.

Drawings

Preferred and alternative embodiments of the present invention are described in detail below with reference to the attached drawing figures:

FIG. 1 is a hardware block diagram representing exemplary hardware components of a system embodying the method of the present invention as shown in FIGS. 2A and 2B;

FIG. 2A is a schematic diagram of a preferred embodiment of a portable computer having a touch screen display on which the keyboard system of the present invention is displayed;

FIG. 2B is the same schematic diagram showing one embodiment of a word selection list displayed after the user has finished tracing out the input pattern and lifted the stylus from the touch screen;

FIG. 2C illustrates an embodiment of a Pop-up selection list of alternate fonts displayed after a user has touched a stylus on the "e" key and has remained in contact with the key for more than a predetermined time threshold;

FIG. 2D is the same diagram showing the first stage in one embodiment of the "Re-Edit" function which assists the user in correcting a previously output word when the user fails to select the intended word from the word selection list;

FIG. 2E is the same schematic diagram illustrating a second stage in the operation of the "Re-Edit" function;

FIG. 2F is yet another identical diagram showing an example of a ROW _ CHANGE inflection point identified in an input pattern corresponding to the word "Atlantic";

figures 3A-3J illustrate a preferred embodiment of a software algorithm implementing the method of the present invention to determine the most likely word or words in the database that match the input pattern traced by the user.

Detailed Description

FIG. 1 shows a simplified block diagram of the hardware components of a typical device 100 in which systems and methods for continuous stroke word-based text input are implemented. The device 100 includes a touch screen 120, the touch screen 120 providing input to the CPU (processor) 110 that when touching the screen informs the CPU (processor) 110 of the contact event when the screen is touched, typically mediated by a hardware controller that interprets the raw signals received from the touch screen and propagates the information to the CPU110 through the available data ports using a known communication protocol. Also for display 130, CPU110 communicates with a hardware controller to draw on the display. Optionally, a speaker 140 is also connected to the processor so that any suitable audible signal can be passed to the user as a guide (mainly for error signals). The processor 110 may use memory 150, which memory 150 may include a combination of temporary and/or permanent memory, as well as read-only and writeable memory (random access memory or RAM), read-only memory (ROM), writeable permanent memory (such as flash memory, hard disk, floppy disk, etc.). The memory 150 includes a program memory 160, the memory 160 containing all programs and software such as an operating system 161, continuous stroke word based text input software 162, and other application programs 163. The memory 150 also includes a data storage 170, the data storage 170 including a database 171 required by the continuous stroke word based text input software 162, memory for maintaining a record of user options and preferences, and any other data 173 required by any of the devices of the apparatus 100.

FIG. 2A is a schematic diagram showing a typical hand-held portable computer 2100 (commonly referred to as a "personal digital assistant" or PDA) with a keyboard 2104 system designed and used in accordance with the present invention displayed on the touch screen 2102. When used in the present invention, the keyboard 2104 generates text that is output to a text insertion point 2108 of a text display area 2106. The term "keyboard" in this application refers to any keyboard implemented on a touch-sensitive surface, including keyboards presented on touch-sensitive displays as shown in FIG. 2A, as well as keyboards imprinted on a touch-sensitive surface. The keyboard 2104 unambiguously represents the 26 letters of the english alphabet on 26 keys arranged roughly in the standard "QWERTY" arrangement on most keyboards. According to a preferred embodiment, some keys, such as the "i" key shown on the keyboard 2104, are significantly wider than the normal keys, so as to have greater separation between other adjacent keys, such as the commonly ambiguous "u", "i" and "o" keys (in the context of the present invention "ambiguous" is because there are common instances of a collection of words that are identical except that one of these vowels is replaced by another). Also, the "n" and "m" keys 2112 are displayed slightly larger than the average width for the same reason.

Text is generated by contacting the keypad 2104 at or near the key associated with the first letter of the word being entered, tracing a continuous pattern through or near each letter of the word in sequence, and breaking contact with the touch screen when the last letter of the word is completed. FIG. 2B shows the same schematic of a computer 2100 in which a representative input graphic 2200 is additionally displayed on the displayed keyboard 2104. In a preferred embodiment, the user may select whether the path of the input graphic is actually drawn on the display word by word and delete the input graphic when selecting a word from the selection list 2208 displayed in the display area 2106 or when deselecting the list 2208. In the example shown in fig. 2B, this option is opened for descriptive purposes. In this embodiment, the user attempts to enter the word "text," and the system successfully matches the word "as the most likely candidate word, causing it to be displayed at default word selection location 2210 in selection list 2208. The path of the input pattern entered by the user with a touch device, such as a stylus, begins at an initial contact point 2212, the location of which is received by the processor and recorded by an input pattern analysis component executed by the processor as the PEN _ DOWN inflection point of the input pattern. The user moves the stylus so that the path first moves to the key associated with the letter "e" and then abruptly moves to the key associated with the letter "x," generating an ANGLE _ THRESHOLD transition point that is identified by the input pattern analysis component at location 2214. Then, in the vicinity of (although not above) the key associated with the letter "x", the path abruptly falls back to the key associated with the letter "t", generating an ANGLE _ THRESHOLD transition point, which is identified by the input graphical analysis component at location 2216. Finally, the stylus is lifted from the touch screen at position 2218 and the input pattern analysis component records it as the PEN _ UP inflection point of the input pattern. In another preferred embodiment, selection list 2208 also displays three additional candidate words that have the next highest match metric values, which in the example shown in FIG. 2B are "test", "rest", and "great". In the preferred embodiment, when the letters of a word are more or less along a vertical path between the preceding and succeeding letters (as is the case with the letter "r" in "great"), nothing is necessary except for the path of the continued entry of the graphic through or near the intended letter. Thus, in accordance with another preferred embodiment, in the example of FIG. 2B, the processor identifies the word "great" having more than four letters, although only four turning points are identified by the input pattern analysis component.

In another preferred embodiment, the selection list 2208 also includes a "(more)" function 2220, the selection of which causes the processor to identify and display the next four additional candidate words that have the metric values of the matches for the remaining words in the database. In the example of FIG. 2B, although not shown, the next 4 such candidate words are "ear", "year", and "feat", and are displayed in selection list 2208 in response to selection of "(more)" function 2220. If, for any reason, the user chooses not to select any word in the displayed selection list 2208, the selection list display can be closed by selecting the "Cancel" function 2222.

In another preferred embodiment, when the user enters the input graphic with sufficient precision and finds that the default value has in fact been the intended word, the user may choose to close the selection list display so that only the default word is displayed at the insertion point. In order to display the selection list in alternate word options, the Re-Edit function key 2224 appearing in the keyboard 2104 must be activated prior to progression. Alternatively, in another preferred embodiment, the user may simply choose to reduce the number of word choices displayed in the selection list 2208.

In accordance with another preferred embodiment, although not normally explicitly displayed on the keys of the keyboard 2104, a different alternate letter form (such as a letter with a distinguishable identification) is associated with each key, each key being associated with and displaying the basic form of the letter with the alternate form. In accordance with another preferred embodiment, FIG. 2C shows a "Pop-up" menu 2300 of alternate letter forms of the letter "e", which is displayed after the user touches the stylus on the "e" key and remains in contact with the key for more than a predetermined time threshold. In the example shown in FIG. 2C, the user slides the stylus's point of contact 2302 down to a list line 2304 containing the alternate letter form "e" which is correspondingly highlighted so that when the user lifts the stylus from the screen, the letter "e" will be explicitly added to the word currently being spelled by a conventional "tap". This embodiment allows the user to explicitly enter alternate forms of letters to spell out words that do not already appear in the system's database without transitioning to an alternate keyboard layout display. In the example shown in FIG. 2C, the user is in the process of spelling out the word "Caf," and has "tapped" the Shift key, followed by the "C," "a," and "f" keys, to generate the TAP location word object "Caf," which appears in the word selection list 2306 at the text insertion point as the default (and unique) word object in the list. When the user lifts the stylus from the screen at location 2302, the letter "e" will be appended to the TAP location word to form the word "cafe", which, according to another preferred embodiment of the invention, can be selected either explicitly by tapping the selection list 2306 at arrow 2308, or implicitly by continuing to enter the stroke input graphic of the next word in succession. Alternatively, the user may Cancel the current selection by selecting arrow 2310 associated with the Cancel function.

In another preferred embodiment, as shown in FIG. 2D, when the user inadvertently accepts a default word for output to the text field 2106 that does not correspond to the intended word, the Re-Edit function activated by the Re-Edit function key 2224 can be used to correct the previously output word. The unintentionally output word is selected either by double-clicking the word to highlight it, or by any of a number of known techniques. Once the target word ("great" in FIG. 2D) is selected, the user activates the RE-Edit function key 2224 by double-clicking on the word. The processor then generates a simulated input pattern 2402 by generating a path that connects in sequence the centers of the keys associated with the alphabetical order that includes the target word. FIG. 2D shows a simulated input pattern of the target word "great" 2400 generated by the processor. To avoid generating "artificial" turning points where they cannot exist in the original input pattern, a smoothing process is first applied to the generated input pattern 2402 to avoid generating false ANGLE _ THRESHOLD turning points at keys where the path of the input pattern is actually only slightly changed in direction. FIG. 2E shows a smoothed input pattern 2500 generated by applying a smoothing process to the initial simulated input pattern 2402 of FIG. 2D. The system then processes the smoothed input pattern 2500 in the same manner as the input pattern is traced by the user, resulting in the identification of the PEN _ DOWN inflection point at location 2502; ROW _ CHANGE inflection point at location 2504; ANGLE _ THRESHOLD transition point at location 2506 and PEN _ UP transition point at location 2508. The pattern is matched to the components executed by the processor and the smoothed input pattern 2500 is processed, generating a selection list as shown in fig. 2E. In this example, the original intended word "heat" appears as the second word in the selection list 2510. Selecting a word in the selection list 2510 automatically replaces the highlighted target word "great" with the original intended word "heat" in the output text field 2106.

FIG. 2F depicts an example of the ROW _ CHANGE inflection point. The figure shows an input pattern depicted on the keyboard to input the word "Atlantic". Given the relatively large distance between the "a" key and the "l" key, and the relatively small deviation required to move up the keyboard to pass the "t" key in moving from the "a" to the "l" key, it is not surprising that there is no rapid change in direction near the "t" key, which can be identified as an ANGLE _ THRESHOLD transition point. In a preferred embodiment, since each new turning point is identified by the input pattern analysis component, the portion connecting the aforementioned turning point to the newly identified turning point is examined again. When the input pattern analysis component determines that the current and previous inflection points are in the same ROW (in the example of FIG. 2F, inflection points 2602 and 2604 in the ROW containing the "a" key and the "l" key) and that the inserted input path deviates from the ROW to pass through a higher or lower ROW of keys (which contains the "t" in the current example), then the ROW _ CHANGE inflection point is identified at a further point that deviates from the ROW containing the surrounding inflection points. In FIG. 2F, the ROW _ CHANGE inflection point is identified by the input pattern analysis component at position 2606. The resulting set of inflection points determined for the input graph of FIG. 2E is a close match to the expected target word "Atlantic". In another preferred embodiment, as depicted in the selection list 2608 in FIG. 2F, when the difference between the metric value of the match computed for one candidate word and the match metric value computed for the next best matching candidate word exceeds a predetermined threshold, the display of potential matching candidate words in the selection list is truncated to exclude the next best matching candidate word and all other words having lower matching score metric values. This minimizes the size of the displayed selection list by executing words that are unlikely to be the intended word, so that the restricted text output region is generally barely observable through the selection list. Any candidate words that are cut from the display are displayed as usual in response to the initiation of the "(more)" function.

Fig. 3A through 3J show a flow diagram of a preferred embodiment of software 162 to implement a method of continuous stroke word-based text input that generates and manages a word selection list in response to a user touching a screen and entering a continuous stroke input graphic or tap touch. FIG. 3A illustrates a flow diagram of a preferred embodiment of a main processing routine 3100 based on the continuous stroke word text input software 162. At block 3105, when the process is first started, various system variables are initialized. At block 3110, the process waits to be notified that contact has occurred in the area of the keyboard 2104.

When the operating system detects a touch in the keyboard region 2104, control returns to the main processing routine 3100 at block 3115, where the input graph analysis routine 3200 of fig. 3B is invoked to analyze and classify the nature of the user's touch operation. Once the contact operation is analyzed, the graph matching routine 3300 of FIG. 3C is invoked at block 3120 to determine what word candidates will appear, what text will be generated, or what functions will be invoked in response to the analyzed contact operation. At block 3125, the display selection list routine 31000 of FIG. 3J is invoked to generate a word selection list display, if necessary, to enable the user to select a desired word. Upon returning from the display selection list routine 31000, control returns to block 3110 where the process awaits notification of the occurrence of a next touch operation within the area of the keyboard 2104.

FIG. 3B illustrates a flow diagram of a preferred embodiment of an input graph analysis routine. At block 3205, the variables of the request are initialized, the array for storing smoothly input graphics data and the corresponding index are cleared along with a list of turning points (IPTs) in which the determined information about each identified turning point, such as its type, location and time of occurrence, is stored. In a preferred embodiment, to reduce the number of computations performed by the graph matching routine 3300, each inflection point entry in the IPT also includes an array IP _ Distance [ ], which is populated with the Distance from the inflection point to each key of the keyboard associated with the letter. In another preferred embodiment, when the Distance from a turning point to a key of the keyboard exceeds a predetermined maximum threshold, the corresponding entry in the IP _ Distance [ ] array is set to a unique MAX _ DISTANCE flag value. In another preferred embodiment to further reduce the number of computations performed by the graph matching routine 3300, each valid Distance entry in the array IP _ Distance [ ] array for each inflection point is stored in the array as a Distance multiplied by the weight factor of the inflection point type. Similarly, each inflection point entry in IPT (except the first PEN _ DOWN) includes an array Path _ Distance [2] populated with the Distance from each key of the keyboard associated with the letter to the closest point on the previous input Path segment (between the previous inflection point and the current inflection point), where it is again multiplied by a weighting factor PATH WEIGHT determined from the Distance measured in the Path segment (if the Distance is greater than the corresponding maximum threshold Distance of the Path segment or to the MAX _ Distance flag value). In addition, for each entry in Path-Distance [ ] [0] for which an effective Distance value is set, Path-Distance [ ] [1] sets an ordinal value representing the ordinal position of the input Path segment along the point of the measured Distance, relative to the points at which the distances of other active keys along the measured Path segment are measured. In order for two adjacent letters in a candidate word to match the unified path segment, the ordinal value of the second letter must be greater than the ordinal value of the preceding letter. This requirement prevents two adjacent letters of a word from matching a path segment when the position of the associated key is opposite to the direction of movement of the stylus along the input path. In this manner, at block 3210, the received first contact location is recorded as a first (PEN _ DOWN) inflection point in the IPT.

Next, at block 3215, the process waits to determine whether the contact location exits from the area associated with the key at which the first contact location is located, or whether the stylus is lifted, and the touch screen ends before exiting the key, wherein case statement execution continues to block 3220, where a single inflection point of the type TAP is added to IPT, and the routine ends. Furthermore, in another preferred embodiment, although not shown in FIG. 3B, when the process detects at block 3214 that the point of contact has not exited from the key at which contact first occurred, AND that the contacted key is associated with one or more alternate fonts, AND that a predetermined threshold of time has elapsed since the contact was initiated, only a single inflection point of the type TAP _ AND _ HOLD is added to the IPT, control returns from the input graph analysis routine without waiting for the contact to be lifted from the touch screen. When the pattern matching routine receives AND processes the TAP _ AND _ HOLD inflection point, a "push-up list" of alternate fonts associated with the key press is displayed, AND the process waits until the user slides the point of contact to the ideal alternate font for the letters in the list, lifting the stylus to select the alternate font for the letter at the TAP location. The flag is then set so that the alternate font is then added to the TAP position Word (as shown in FIG. 3F), and if the current TAP _ Word _ Len is set to 0, the selected alternate font also becomes the default one-letter Word in the Word selection list. This allows the user to easily generate any desired sequence of letters in the spelling of a new word comprising alternating fonts, without changing the graphics of the keyboard.

If the point of contact is exited from the first contacted key (or a DOUBLE _ LETTER gesture is detected) at block 3215, then if there is a pending selection list currently displayed by the previous input graphic, a word output routine 3900 (shown in FIG. 31) is invoked to output a default word selection at block 3230. Then at block 3233, all unprocessed data points are collected up to the time of the touch screen, the sequence of which is processed by a suitable smoothing algorithm to form a smoothed sequence of data points that is appended to the input pattern data buffer, and at block 3235, first and second order differences are calculated, in particular the sum of the absolute values of the x and y second order differences is appended to a single input pattern data buffer. The process then determines whether a DOUBLE _ LETTER gesture was detected in the just processed data sequence at block 3240. If detected, at block 3245 the approximate center of the gesture is determined and added to the IPT as the DOUBLE _ LETTER transition point, at blocks 3250 and 3255 as described above. In addition, each time an inflection point is added to the IPT, the WEIGHT factors for that inflection point type are summed into a different IP-WEIGHT that is used to calculate a match metric value for each candidate word, block 3250.

Then, at block 3260, the process determines whether the ROW CHANGE inflection point can be identified along the previous input path segment and, if so, adds 1 to IPT in the manner previously described. In this case, the predetermined path segment is divided into two segments, one before the newly identified ROW CHANGE inflection point and one after the newly identified ROW CHANGE inflection point. The predetermined Path _ Distance [ ] [ ] entry is reassigned to the new Path _ Distance [ ] [ ] array of entries after the ROW _ CHANGE inflection point.

At block 3265 the process determines whether all input path data has been processed UP to the point where the stylus is lifted from the touch screen, and if so, at block 3295 the last PEN UP inflection point is added to the IPT in the manner previously described, and at block 3298 a final check is made to determine whether a ROW _ CHANGE inflection point can be identified along the last input path segment.

If no DOUBLE _ LETTER is detected in the data sequence at block 3240, then the process determines whether the sum of the absolute values of the x and y second differences exceeds a predetermined threshold at some point in the analyzed data sequence at block 3270. If so, then at block 3275, the process determines the point at which the sum of the absolute values of the second differences reaches its maximum value before falling back to the minimum THRESHOLD, and this point is then added to IPT in the manner described above as the ANGLE _ THRESHOLD transition point. Since the CANCLE gesture may represent the meaning of three or more consecutive ANGLE _ THRESHOLD transition points defined to be entered at an accelerated speed, following detection of each ANGLE _ THRESHOLD transition point, the process checks at block 3280 whether the CANCLE gesture has been entered. If so, at block 3285, a CANCEL signal is generated to notify the user that a CANCEL gesture has been recognized, the process waits for the stylus to be lifted from the touch screen, and then the IPT and input graphics data buffers are cleared before returning to the main routine 3100. If a CANCEL gesture is not detected at block 3280, the process continues to complete adding the ANGLE _ THRESHOLD transition point at block 3250, continuing before the DOUBLE _ LETTER transition point.

After returning from the call to the input graph analysis routine 3200, at block 3120 in the main processing routine 3100, the graph matching routine is called to process the results of the analysis of the input graph. As shown in FIG. 3C, the word candidate list is cleared at block 3305 by setting the number of Candidates (Num Candidates) to 0, and the maximum metric Value (MaxMetrix Value) is initialized to the FLAG Value MAX _ FLAG, indicating that the word candidate list is still empty. Then, at block 3307, the process checks whether a CANCEL gesture was entered, and if so, returns to block 3320 where the word candidate list is still empty. If a CANCEL gesture has not been entered, then at block 3310 the process checks whether the breakpoint list contains a single TAP breakpoint, and if so, at block 3315 the process TAP breakpoint transition routine 3600 is invoked to process the detected TAP. Otherwise, the process identifies each uniquely ordered pair of keys at block 3325 such that the first key of each pair is within the predetermined threshold MAX _ DISTANCE from the PEN _ DOWN transition point and the second key of each pair is within MAX _ DISTANCE from the PEN _ DOWN transition point. The process then identifies a range of input path length classifications associated with the words in the database that may be considered potential matches with input patterns of actual length detected by the input pattern analysis routine and stored in the IPT, block 3330. At block 3335, various MIN _ LETTERS are set to the number of inflection points that must match a LETTER, adjusted to account for the DOUBLE _ LETTER inflection points that must match two LETTERS. Similarly, N _ packet is set to the number of packet _ receiver transition points. The loop from block 3340 to block 3350 is then performed for each sequential pair of keys identified at block 3325, the set of words in the database at block 3345 corresponding to the current sequential pair of keys being identified. The loop from block 3360 through block 3390 is then performed for each word of the set of words identified at block 3345. At blocks 3365, 3370, and 3373, the process checks whether the word qualifies as a candidate for sorting based on its input path length, the number of letters in the word, and the double-letter in the word. If any of these qualifying conditions are not met, then the word is skipped and the next word is considered. In another preferred embodiment (not shown in FIG. 3C), each word in the database is stored with a desired number of inflection points based on the geometric relationship between the keys associated with the sequence letters forming the spelling of the word. If the number of inflection points identified in the current input pattern is less than the desired number of inflection points, the candidate word is not qualified. If the WORD meets all of these preliminary conditions, then at block 3375 the WORD is copied to the array WORD [ ], WORD _ Len is set to its length. At block 3380, a match metric calculation routine 3400 (shown in FIG. 3D) is invoked to calculate a match metric for the current word. An update candidate Word list routine 3700 (shown in FIG. 3G) is then invoked at block 3385 to determine whether the calculated match metric value is good enough to qualify the current Word for temporary addition to the Word _ Candidates [ ] list of the top matching Word Candidates identified in the database, and if the match metric value is good, add it to the list. Once all identified qualified candidate words have been calculated, the routine returns to main processing routine 3100 at return block 3355, where at block 3125 the display selection list routine 31000 (shown in FIG. 3J) is invoked to display the identified word candidates in the selection list at or near the text insertion point on text display 2106.

Figure 3D illustrates a flow diagram of a preferred embodiment of the matching metric value calculation routine 3400 invoked at block 3380 of the pattern matching routine 3300. The process described in FIG. 3D determines whether a valid match between the inflection point (path segment if necessary) of the input pattern and the key associated with the letter of the candidate word can be identified. If such a match is possible, the routine of FIG. 3D identifies the best or near-best match so that the set match metric value routine 3700, invoked at block 3475, can quickly and simply calculate the actual value of the match metric value from the identified match configuration.

This is a preferred embodiment of geometric matching of letters of a candidate WORD that has the length of the WORD-Len letters (stored in WORD [ ] of the Number _ of _ IP inflection points determined by the input pattern. At block 3405, since the first (PEN _ DOWN) inflection point always matches the first letter of the word and the Last (PEN _ UP) inflection point always matches the Last letter, various different IP _ Index (for each inflection point passed through matching) are initialized to 1 and Last _ IP (for defining the Number of processed inflection points) is initialized to (Number _ of _ IPs-1). Similarly, the letters of WORD [ ] are indexed, the LTR index is initialized to 1, and the Last LTR is set to (WORD _ Len-1). Various Match-Lim are initialized (WORDLen-Number _ of _ IP), how many subsequent letters need to be considered as a trajectory of potential Match candidates for each turning point of the algorithm. The arrays MATCH [ ], RECURSE [ ] and BACK _ TRACK [ ] [ ] and the various RECURSION _ LEVELs are initialized to 0 and the trajectory where the process must roll BACK when the result is doubled is found.

At block 3410, for each subsequent inflection point, the process determines how many of the next Match _ Lim still unmatched letters are potential matches and sets N _ Match to this number. For a potentially matching letter, the key associated with that letter must be within MAX _ DISTANCE of the inflection point, and any previous letter that has not yet matched must be able to match the previous path segment in its proper sequence. At block 3415, no MATCH is possible, but at block 3417 it is determined that the current inflection point is the ROW _ CHANGE inflection point (and therefore does not need to MATCH a letter), and then at block 3463MATCH [ IP _ Index ] is set to the flag value ROW _ CHANGE _ SKIP, which indicates that the ROW _ CHANGE inflection point is left unmatched, and LTR _ Index is decremented so that subsequent increments made at block 3465 restore it to its native value (since the current letter has not yet matched an inflection point). If, however, at block 3415 there is no potential match, it is determined at block 3417 that the current inflection point is not a ROWCHANGE inflection point, and if RECURSION _ LEVEL is set to 0 at block 3420, then the current word is not a candidate, and the algorithm returns an error code at block 3440. If it is determined at block 3450 that there is a potential Match, then at block 3460, Best-Match is set to the Index of the matching letter and a Match to the inflection point is recorded by setting MATCH [ IP _ Index ] to Best-Match, and all LTR _ Index are set to Best-Match since all letters up to Best-Match have now been provisionally matched. At block 3465, LTR _ Index is updated to the Index of the next letter to match the previous inflection point, and IP _ Index is incremented by 1, continuing to identify a match for the next inflection point. At block 3470, the value of Match _ Lim is updated in view of any letters that have been matched to a path segment, since each letter that has been matched to a path segment reduces the number of letters that can be matched to each subsequent turning point. At block 3473 the process checks whether all inflection points and letters that need to be matched have been matched, and if so, at block 3475 a set MATCH metric value routine 3700 is called to calculate the value of the MATCH metric value from the inflection point-letter pairs established in MATCH [ ], and the routine eventually returns at block 3480.

If at block 3450 the process determines that the inflection point index can successfully Match more than one letter of the next Match-Lim that still does not Match, then the Best matching letter (with index Best Match) is temporarily matched to the inflection point. At block 3455, BACKTRACK [ IP _ Index ] [0] is set to (N _ Match-1), one less than the number of potential matching letters not yet tried, and the remaining potential matching letters are stored in BACKTRACK [ IP _ Index ] [ l.. N _ Match ] with the increasing order of the best Match, RECURSE [ RECURSION _ LEVEL ] is set to IP _ Index, RECURSION _ LEVEL incremented. The remaining potential matches are stored in BACKREACK [ ] so that if the algorithm reaches a dead point based on a temporary Match of the current inflection point with Best _ Match, it can fall back to that point by matching the inflection point with one of the other potential matches and try again. Thus, at block 3415, if no potential matches are found for the subsequent inflection points, and RECURSION LEVEL is not set to 0 at block 3420, then at block 3425 the process retrieves (and removes) the next best match from RECURSE [ ] and BACKTRACK [ ] for the pre-identified most recently identified inflection points with multiple matches, restores the IP _ Index and LTR _ Index to their proper values, and again works forward from that point, attempting to find a valid, complete match solution. At block 3430, the process determines whether the last stored potential match has been removed from the current active stage of the BACKTRACK [ ] array, and if so, decrements at block 3435RECURSION _ LEVEL so that the algorithm will move forward (since all potential matches have been tried at the current stage). If the process determines a potential match for each turning point, even if RECURSION _ LEVEL is greater than 0 (indicating that there may in fact be other better solutions possible), the algorithm moves to termination at block 3473. Since the algorithm 3400 first selects the best match for each turning point with multiple potential matches, the first valid match identified may be the best match, in either case, the range of constraints set based on the matches makes it impossible for multiple solutions, if any, to have significantly different match metric values. In another preferred embodiment, the algorithm of fig. 3D is changed so that it alternates between matching the next turning point moving forward from the first PEN DOWN turning point and matching the next turning point moving backward from the last PEN UP turning point. In another preferred embodiment, any identified DOUBLE LETTER inflection point (or points) is first matched with the necessary occurrence (or multiple occurrences) of a DOUBLE LETTER in the candidate word, and the algorithm of FIG. 3D moves alternately forward and backward from each of the previously matched PEN _ DOWN, PEN _ UP, and DOUBLE LETTER inflection points.

Once the matching metric value matching _ metric calculation routine 3400 identifies a valid pair between the identified inflection point and the letter of the candidate word, the actual metric value of the matching metric value in the set matching metric value routine 3500 shown in fig. 3E is determined directly forward (called from block 3475 in the matching metric value calculation routine 3400). At block 3505, the matching metric value is initialized to the weighted distance between the initial PENDOWN inflection point and the first letter of the word. When each inflection point is initially identified, the total weight is initialized to the sum of the inflection point distances calculated by the input graph analysis routine 3200, the NEXT LTR is initialized to 1, and the index of the NEXT letter of the word will be matched. The loop from blocks 3510 through 3540 then continues at each remaining inflection point. At block 3515, if the current inflection point has already matched the inflection point to be matched, then the weighted distance of the current letter from the current inflection point is added to the sum accumulated in the Matching Metric value (Matching _ Metric) at block 3530. If the current inflection point has not yet matched the next letter to be matched, then at block 3517, if the current inflection point is found to be a ROW CHANGE inflection point that has been skipped (not matched with any letters), then at block 3527 the overall weight is adjusted so that the ROW CHANGE inflection point has been skipped during the matching of the current word, continuing the process at the end of loop 3540, moving up to the next inflection point i. If the current inflection point is found to not be a skipped ROW CHANGE inflection point 3517, then the current letter must have been matched with the previous path segment, so that the weighted distance of the current letter derived from the previous path segment at block 3520 is added to the sum accumulated in the Matching _ Metric, and the Total _ Weight is adjusted to calculate the Weight applied to that distance. Next _ LTR is incremented at block 3525 since the current letter has already been calculated, and the Next letters are examined at block 3515 to determine if they have already matched the current inflection point. Once all the inflection points have been processed, the loop ends at block 3540, and the final value of Matching _ Metric is calculated at block 3545 by multiplying the sum of the weighted distance calculations by a Frequency adjustment factor, which in a preferred embodiment is calculated as (1+ log (MAX _ FREQ/WORD _ FREQUENCY)), where MAX _ FREQ is the maximum possible Frequency of usage values that can be associated with a WORD in the database, and WORD _ FREQUENCY is the particular current value of usage Frequency associated with the current WORD. Finally at block 3545, the final value of Matching _ Metric is normalized by dividing by the sum of all the weighting factors used in calculating the summed distance sum such that the final value is the average frequency weight distance of the letters of the word derived from the inflection point (possibly a path segment) of the current input pattern.

FIG. 3F illustrates an embodiment of a process TAP break point routine 3600, which routine 3600 is called from the graph matching routine 3300 at block 3315. At block 3603, the process determines whether the TAP location appears within the boundaries of the key associated with letter generation. If so, at block 3605 the process checks whether the tapped Word has already started, or whether this is the first TAP of a potential new TAP sequence (i.e., TAP _ Word _ Len is currently set to 0). If TAP _ Word _ Len is 0, then at block 3610 the process identifies all one-letter words in the database that are associated with the key in MAX _ DISTANCE of the identified TAP location. Then in a loop from blocks 3615 through 3630, a Matching _ Metric value is calculated for each identified single-letter WORD, which is stored in WORD [ ] and WORD _ Len, and at block 3625, an update WORD candidate list routine 3700 is invoked to add each identified one letter WORD to the WORD _ Candidates [ ] list at the appropriate location so that a selection list with the proper priority can be displayed.

If at block 3605 it is found that TAP _ Word _ Len is not set to 0 (and thus this is the second or later TAP event in the letter-to-key TAP sequence), again at block 3630 following the other of the letter words, at block 3635 the process identifies the default letter associated with the key in which the TAP location occurred.

This default letter is added to the current TAP-WORD [ ] being formed at block 3640, which is added to the current Word Candidates [ ] list as the designated TAP WORD at blocks 3645 and 3650.

If the TAP location is not within a key associated with letter generation at block 3603, then at block 3660 the process determines if the TAP location is present within the boundaries of the displayed word selection list and, if so, at block 3663 word selection routine 3800 is invoked to process the selection of a word or word selection list function. If the TAP location is not in the Word selection list at block 3603, the process determines at block 3670 whether the TAP location appears within the boundaries of the BackSpace key, and if so, if TAP Word Len is also found at block 3673 to be greater than 0, then at block 3675, TAP Word Len is decremented. If at block 3677 it is found that TAP _ Word _ Len is still greater than 0, the process continues as before at block 3645, adding the current TAP _ WORD [ ] to the Word _ Candidates [ ] list. If at block 3690 it is found that TAP _ Word _ Len is not greater than 0, then the BackSpace function is invoked for its standard Word processing function (i.e., deleting characters up to the left of the text cursor, or deleting a highlighted text fragment if present, etc.). Thereafter, at block 3693, Word _ Output is set to FALSE, since it is assumed that the user no longer wants automatic Output for a period of time before the next selected Word.

If the TAP location is not on the BackSpace key at block 3670, the process determines at block 3680 whether the TAP location is present within the boundaries of the key associated with the function that caused the output of the default word for the selection list, and if so, the word selection is set to the default value of 0 at block 3685, and the word output routine 3900 is invoked at block 3687 to output the default word selection to the insertion point in the text output region. If the function found at block 3680 does not cause output of the default word, then the function associated with the tapped key is invoked at block 3690 to perform its standard word processing function. Depending on the nature of the function invoked, if the flag word output is automatically output for a period of time (e.g., after the BackSpace function) just before the next selected word at block 3693, the flag word output is set to FALSE.

FIG. 3G shows a preferred embodiment of an update Word Candidates [ ] list routine 3700 that is called in block 3385 of the graph matching routine 3300 and in blocks 3626 and 3650 of the handle TAP break point routine 3600. At block 3705, the Matching _ Metric value is checked to determine if the value has been set to the flag value indicating that the current word may not match the input pattern, and if set to the flag value, the routine returns without adding a candidate word. If the flag Value is not set, Num-Candidates is checked to determine if the candidate word list has been filled with the maximum number of valid Candidates, and if not, the current word is automatically added to the word candidate list at block 3740, and the match Metric Value is checked at block 3745 to determine if the current Value of Max _ Metric _ Value needs to be updated. If the Word _ Candidates [ ] list has been populated with a valid set of entries at block 3710, then the match Metric Value for the current Word is compared to the Max _ Metric _ Value at block 3715 to determine if the current Word is a better match than the Word(s) currently present in the database. If it is a better match, then the WORD with the highest Matching _ Metric value is removed from the WORD candidate list at block 3720, the current WORD [ ] is added to WORD-Candidates at block 3725, and stored in descending order according to the Matching _ Metric value for each entry. At 3730, Max _ Metric _ Value is updated to represent the highest Value of Matching _ Metric in the Word _ Candidates [ ] list. At block 3755, control returns to the callee.

Fig. 3H shows a preferred embodiment of a word selection routine 3800, the word selection routine 3800 being invoked at block 3663 of the process TAP inflection point routine 3600. At block 3805, a word selection list region is displayed in which TAP contacts that occurred were identified and candidate words or list functions associated with the region were determined. If the region is associated with a Word at block 3810, then at block 3815 the index variable, Word _ Choice, is set to (First _ Display + index to select region), where First _ Display contains the index value of the Word Candidates array for the entry displayed in the top (default) row of the Word _ Choice list, so that Word _ Choice is set to the index of the Word Candidates array for the selected Word. At block 3820, word output routine 3900 is invoked to output the selected word to text display area 2106 at insertion point 2108. At block 3825 the process determines whether the selected word is a constructed TAP-location word, if a TAP-location word, which is added to the database as a user-defined word at block 3827 if the selected word is not already in the database, or if a discriminatory exploit has been formed. The routine then terminates at block 3829.

If the selected LIST region is not associated with a Word selection at block 3810, then if it is determined at block 3830 that the region is associated with a "(more)" function, then at block 3835 the index variable First _ Display is incremented by the value LIST _ MAX, which is a predetermined maximum number of words displayed in the fully populated Word _ Choice LIST. If the value of the First Display increase exceeds the total number of candidate words identified in the Word _ Candidates [ ] array at block 3840, then First Display is set to 0 at block 3845, generating a signal (such as a distinctive alarm sound) to inform the user that the Word Choice list has looped through all possible Candidates, and has returned to the beginning of the list. The display selection list routine 31000 is then called at block 3850 to display the new set of Word candidates in the updated Word Choice list display. The routine then terminates at block 3855.

If the selection list region is not associated with the "(more)" function at block 3830, and then it is determined at block 3860 that the region is associated with the "CANCEL" function, then at block 3835 the Word _ Candidates [ ] list is cleared at block 3865, Num-Candidates is set to 0, Max _ MetricFlag is set to the MAX _ FLAG value, so that the Word _ Candidates [ ] list is ready to have a new set of determined Candidates added to it. Similarly, at block 3870TAP _ Word _ Len is set to 0 so that new TAP words can begin to be built, at block 3875 the Word Choice list Display is dismissed, the Display screen is refreshed, the Word Choice list Display is removed from the screen, and the First _ Display is reinitialized to 0. The routine then terminates at block 3880.

FIG. 3I shows a preferred embodiment of a word output routine 3900 that is invoked from block 3230 of the input graph analysis routine 3200, block 3687 of the handle TAP milestone routine 3600, and block 3820 of the word selection routine 3800. At block 3905, if the current Word _ Candidates [ ] list contains at least one candidate, then at block 3910 the process considers the index Word Choice point as a valid candidate, and if not, at block 3915 the Word _ Choice is reset to the default candidate index 0. At block 3917, if the auto period flag Word _ Output is set to TRUE, then a period of time is Output to the text insertion point at block 3919 before the selected Word _ Candidates [ ] list entry (determined by the value of Word _ Choice) is Output at block 3920. Further, adjusting the frequency of use stored in the database according to one of the algorithms known in the art for tracking Word frequency of use, Word _ Output is set to TRUE so that if the next Word is subsequently Output, a time period will be automatically generated before the next Word. Then at block 3925, if at block 3905 it is found that the current Word _ Candidates [ ] list is clear, the execution may also be restarted, the Word _ Candidates [ ] list is cleared, Num-Candidates is set to 0, maxmtric _ Flag is set to the MAXFLAG value, so that the Word _ Candidates [ ] list is ready to have a new set of determined Candidates added to it. The TAP _ Word _ Len is then set to 0 at block 3930 so that new TAP words can begin to be built, the Word Choice list Display is cancelled, the Display screen is refreshed, the Word Choice list Display is removed from the screen, and the First _ Display is reinitialized to 0 at block 3935. The routine 3900 is then terminated at block 3940.

FIG. 3J illustrates a preferred embodiment of the display selection list routine 31000, which is invoked from block 3125 of the main processing routine 3100 and from block 3850 of the word selection routine 3800. At block 31005, Num-Display is initialized to LIST _ MAX, which is a predetermined maximum number of words displayed in the fully populated Word _ Choice LIST. If there are no candidates available to display at block 31010, the routine does nothing and returns from block 31040. If there is at least one candidate, then at block 31015 the index variable First _ Display, which contains the index value of the Word _ Candidates [ ] array for the entry displayed in the top (default) row of the Word Choice list, is checked to determine that it is a valid value. If not, First _ Display is set to 0, i.e., the index of the default candidate, at block 31020. At block 31025 the process determines if there are enough Word candidates outside of First _ Display to form a full Word Choice list, and if there are not enough Word candidates, then at block 31030Num _ Display is reset to the number of available candidates. Finally, at block 31025 a Word Choice list is generated and displayed at the text insertion point, representing Num _ Display Word _ Candidates [ ] starting at the index First _ Display, followed by the standard Word Choice list function "(more)" and "CANCEL".

While the preferred embodiments of the invention have been illustrated and described, as noted above, many changes can be made without departing from the spirit and scope of the invention. Accordingly, the scope of the invention is not limited by the disclosure of the preferred embodiments.

Claims (51)

1. A method of inputting alphabetic text into 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 is continued, and a final contact location at which contact with the touch-sensitive screen is removed,

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

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

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

determining a relative ranking of the identified one or more words in accordance with the comparison; and

the one or more words for which the relative rankings are determined are provided to the user for selection of the word to be entered as text.

2. The method of claim 1, wherein the recorded contact action comprises moving a position of a contact along a path of the contact action, and wherein the movement comprises an unambiguous movement of the contact action when the intended word comprises a letter repeated twice in succession.

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

4. The method of claim 2, further comprising, when the intended word comprises a letter repeated more than twice in succession, repeating the explicitly moving for each additional repetition of the repeated letter.

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

6. The method of claim 1, further comprising generating a tapping input stroke graphic when the point of contact moves away from the screen without moving more than a threshold distance from the initial contact location and without maintaining contact with the screen for more than a threshold period of time.

7. The method of claim 6, further comprising:

comparing the stroke input stroke pattern to a word group of a letter stored in a database;

identifying acceptable words of one or more letters based on the comparison;

determining a relative ranking of one or more alphabetic words of the recognized words in accordance with the comparison; and

one or more of the words for which the relative ranking is determined are provided to the user.

8. The method of claim 7, wherein none of said recognized words are provided to the user when none of said rated words are associated with a key less than a minimum threshold distance from said stroke input stroke pattern.

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

10. The method of claim 9, further comprising generating a text string when a series of two or more consecutive tap input stroke patterns are detected, the text string being composed of a sequence of letters associated with the detected sequence of tap input stroke patterns, and providing the generated text string to the user.

11. The method of claim 10, when the point of contact has not moved more than a threshold distance from the initial contact location and remains in contact with the screen for more than a threshold period of time, displaying a list comprising one or more regions, within each region, where one letter is associated with a key, the initial contact location being located within a boundary of the key; and when the user moves the point of contact to one of the regions in the list and moves the point of contact away, making the input stroke graphic a tap input stroke graphic associated with the letter associated with the region from which the point of contact was moved.

12. The method of claim 10, wherein said text string is automatically added to said database when a user selects said text string as a word to be entered as text, and when said word has not yet appeared in said database.

13. The method of claim 1, wherein when a user touches the screen to input a word and when the user determines that the path of input of the contact point does not correspond to the user's intended word, moving the contact point in a distinctive manner to indicate that the current input stroke graphic will be cancelled, and wherein when the system identifies the distinctive manner of movement of the contact point, no matching words are identified for the input stroke graphic that includes the distinctive manner of movement of the contact point, and no words are provided to the user for selection.

14. The method of claim 13, wherein the distinct manner of moving the point of contact includes moving the point of contact back and forth a threshold number of times, wherein the point of contact moves faster than a threshold speed.

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

16. The method of claim 13, wherein when the system identifies the distinctive manner of movement of the point of contact, a signal is provided to the user in response to the current input tick pattern indicating that the distinctive manner of movement has been detected and that no words are to be provided to the user for selection.

17. The method of claim 1, wherein the layout of the keys in said virtual keyboard is a conventional "QWERTY" layout.

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

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

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

21. The method of claim 20 wherein the average of the distance from each determined turning point along the path to each corresponding matched key is used in the calculation of a match metric value to determine whether the compared word is acceptable based on the degree of match of the input stroke pattern and the series of positions associated with the alphabetic sequence of the word.

22. The method of claim 21, further comprising calculating a match metric based on an average of squares of distances from each determined turning point along the path to each corresponding matched key.

23. The method of claim 20, wherein said forming comprises recording the input stroke pattern as a series of contact points, each contact point being identified as a position on a two-dimensional coordinate plane, and identifying a turning point when the absolute value of the second order difference of one or both of the two-dimensional coordinates in the sequence of contact points exceeds a determined threshold, wherein said turning point is identified at or near a point where the absolute value of the second order difference of one or both of the two-dimensional coordinates reaches a local maximum, and wherein each of said identified turning points serves as one of said determined series of points, i.e. a point matching a key associated with at least one letter of the compared word.

24. The method of claim 23, wherein said forming comprises applying a smoothing algorithm to the series of contact points prior to identifying the turning point.

25. A method according to claim 23, wherein the first and second order differences of the two dimensional coordinates calculated at each point along the input path are calculated in respect of two points along the input path a fixed distance before and after a given point.

26. The method of claim 21, measuring the distance from the closest point along the input stroke pattern to the key associated with any letter in the letter sequence of the compared word that does not match the turning point, and wherein this distance is included in the calculation for calculating the average of the matching measures; wherein said closest point is located between: the distance of this point to the key associated with the previous and next letter to the unmatched letter in the letter sequence containing the word being compared is measured.

27. The method of claim 21 or 26, wherein when the distance from the key associated with the letter in the compared word to each matching point in the input stroke pattern exceeds a maximum threshold distance, the compared word is deleted as a candidate to match the input stroke pattern.

28. The method of claim 23 wherein when the input stroke pattern transitions from within the first horizontal row of keys to within the second horizontal row of keys and then returns again to within the first horizontal row of keys and no such turning point is determined along a segment of the input stroke pattern within the second horizontal row of keys, at or near the point at which the path of the input stroke pattern obtains its greatest vertical distance from the first horizontal row of keys, at least one additional turning point is identified along the segment of the input stroke pattern within the second horizontal row of keys.

29. The method of claim 28, wherein said additional identified inflection point does not match a key associated with a letter of said compared word when the key associated with each letter of said compared word matches said determined series of points in the input stroke pattern.

30. The method of claim 28 wherein the horizontal and vertical components of the distance of the key associated with the letter of said compared word that matches a turning point are weighted differently when calculating the distance used in calculating the value of said match metric.

31. The method of claim 21, wherein multiple types of turning points are identified.

32. A method according to claim 31, wherein one type of turning point corresponds to a point determined at or near the initial positional contact.

33. A method according to claim 31, wherein one type of turning point corresponds to a point determined at or near the location of the last contact.

34. The method of claim 31, wherein the contact action comprises moving the location of contact along a path of the contact action, and wherein the moving comprises explicitly moving the contact location when the intended word comprises a letter repeated twice in succession, and wherein a type of inflection point corresponds to explicitly moving a determined point at or near the contact location.

35. The method of claim 31, wherein a type of inflection point corresponds to a point determined by recording an input stroke pattern as a series of contact points, each contact point being identified as a position on a two-dimensional coordinate plane and the inflection point being identified when an absolute value of a second order difference of one or two-dimensional coordinates in the series of contact points exceeds a determined threshold, and wherein the inflection point is identified at or near a point where the absolute value of the second order difference of one or two-dimensional coordinates reaches a local maximum.

36. The method of claim 31, wherein a type of turning point corresponds to a point along a segment of the input stroke pattern located within a second horizontal row of keys at or near a vertical distance where the path of the input stroke pattern is taken to be at its greatest from the first horizontal row of keys.

37. The method of claim 31, wherein the inflection points of the plurality of types are associated with weight factors such that a distance of a key associated with a letter of the compared word that matches an inflection point of a type associated with a relatively smaller weight factor has a correspondingly greater effect on the value calculated by the match metric value than a distance of a key associated with a letter of the compared word that matches an inflection point of a type associated with a relatively smaller weight factor.

38. The method of claim 31, wherein when selecting an output word corresponding to the input stroke pattern, a difference is calculated between the position of each detected turning point and the position of the key associated with the letter in the output word that matches the turning point, wherein the difference is used to calculate a running average of the differences, and wherein the running average of the differences is added to each sequentially detected turning point position to adjust the detected turning point position, wherein the distance from the turning point to the key position associated with the letter of the compared word is measured from the adjusted turning point position.

39. The method of claim 38, wherein the running average of the difference values is calculated and separately adding the running average of the difference values to an x-coordinate and a y-coordinate of each of the plurality of types of turning points, the x-coordinate being a horizontal dimension of the virtual keyboard and the y-coordinate being a vertical dimension of the virtual keyboard.

40. The method of claim 39, wherein said running average of said differences is calculated and positive and negative values of second differences in x-and y-coordinates of one or more types of inflection points, individually, are increased by said running average of said differences.

41. The method of claim 1, wherein the words in the database are stored in groups, wherein for each group of words, the first letter of all words in the group is associated with a single key of the virtual keyboard and the last letter of all words in the group is associated with a single key of the virtual keyboard, the key identifying a sequential key pair uniquely associated with the group.

42. The method of claim 1, wherein the one or more words in the database are stored with an indication of a frequency of use associated with the word, and wherein the frequency of use is used to determine which set of one or more words determined to best match the input stroke pattern is most likely the word the user intended to input, wherein the determined set of words is provided to the user in order of decreasing likelihood.

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

44. The method of claim 43, wherein the expected path length 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 sequentially arranged words.

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

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

47. The method of claim 46 in which the word presented to the user as the default word selection is automatically accepted for output unless the user makes an explicit action to select another word selection.

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

49. The method of claim 1, wherein said forming an input stroke pattern comprises generating a path including contact point locations that sequentially connect key locations associated with a sequence of letters of a previous output word, wherein identifying a set of one or more words comprises excluding the previous output word that most closely matches the input stroke pattern, and said providing comprises providing one or more highest-ranking words to the user for selection of the word to replace the previous output word in the output text.

50. The method of claim 49, wherein a smoothing process is first applied to the generated input stroke pattern before comparing the generated input stroke pattern to the set of words stored in the database.

51. An apparatus, comprising:

a touch sensitive screen for presenting a virtual keyboard, the virtual keyboard comprising 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 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 last contact location at which contact with the touch sensitive screen is removed;

a second component for forming an input stroke pattern according to the recorded contact operation;

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

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

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

a sixth component for causing the one or more ranked words to be presented on an output device.