Method and mechanism for providing partial results in full context handwriting recognition

[0002] This application is a continuation of copending U.S. patent application Ser. No. 08/870,558 filed Jun. 6, 1997, now U.S. Pat. No. 6,111,985 issued Aug. 29, 2000.

[0003] The invention relates generally to the input of user information into computer systems, and more particularly to the recognition of handwritten characters input by a user.

[0004] Many handwritten characters resemble others, for example, a handwritten lowercase letter “o” resembles a “0” (zero) as well as an uppercase “O.” Moreover, the shape of any handwritten character typically varies from user to user, and often varies from instance to instance when written by a single user. Consequently, in addition to shape matching, the accuracy of handwritten character recognition is improved when the character is also analyzed with respect to its context. Indeed, some Japanese symbols are virtually indistinguishable from one another absent surrounding context.

[0005] Context-based recognition is done in one of two ways, i.e., a backward context approach or a full context approach. Backward context recognition analyzes previous characters, if any, to determine the best translation of the current character. A benefit of backward context recognition is that each entered character is recognized and immediately displayed for user verification. In contrast, a full context approach looks at the characters both before and after each character in a string to help in the recognition thereof.

[0006] Backward context recognition is less accurate than full context recognition because by only looking backwards, only half of the available context is used. By way of example, a handwritten string such as “|O0” may be intended to be “one-zero-zero” or the first three letters of a word such as “loops.” As can be appreciated, both are reasonably probable. If the next character was available for analysis, the chance of correctly recognizing the string may be greatly improved. For example, a “5” would strongly indicate that the first three characters were part of a number (“1005”) while a “p” would strongly indicate the first three characters were part of a word (“loop”). However, the backwards context recognition has to make its initial decision based solely on the first character, which may be incorrect, particularly if the character shape is one which closely resembles the shape of one or more other characters. Thereafter, subsequent characters are analyzed relative to this initial guess, e.g., a letter more likely follows a letter than a number. As can be appreciated, if the initial guess is incorrect, with backwards context recognition, some or all subsequent characters may be also incorrect, further compounding the error.

[0007] Full (forwards and backwards) context recognition is thus more accurate than backwards recognition because of the ability to use all rather than half of the available context information. A first approach to full context recognition is to wait for the user to complete all characters in a given string (with the user indicating completion) and then analyze the full string. Full context thus provides a relatively high level of recognition accuracy, but also has a number of drawbacks associated therewith. First, the user receives no feedback while entering the characters until the user indicates that the string is complete. Second, there is a noticeably long delay between receipt of the string and the completion of the recognition operation. Lastly, and possibly most important, the memory requirements for keeping a potentially unlimited amount of electronic ink in the memory for a potentially unlimited amount of characters would overwhelm many systems, particularly hand-held (palmtop) computing devices in which handwriting recognition is commonplace.

[0008] A compromise solution has been attempted in which backwards context recognition is initially performed to provide instantaneous feedback using only small amounts of memory, while full context recognition is later performed on those backwards-recognized characters to increase recognition accuracy. However, this solution has the effect of changing characters that have already been displayed, and possibly verified as correct by the user, to character values that may be incorrect. Indeed, in most cases, unilaterally changing a character after display and verification of the correctness thereof has been found so annoying to users that this is an unacceptable solution, even though overall recognition accuracy may be increased.

[0009] Accordingly, it is a general object of the present invention to provide an improved method and mechanism for performing full-context recognition.

[0010] Another object is to provide a full context recognition method and mechanism that facilitates rapid visual feedback while having relatively low memory requirements.

[0011] In accomplishing those objects, it is a related object to provide a method and mechanism as characterized above that functions with existing recognition components such as shape matching components and language model context components.

[0012] Yet another object is to provide a method and mechanism of the above kind that is fast, reliable, cost-efficient, flexible and extensible.

[0013] Briefly, the present invention provides a method and mechanism for recognizing handwritten characters previously entered into the system from the context of subsequent handwritten characters presently being entered into the system. Using a shape matcher, each handwritten character entered is associated with a plurality of alternate code points therefor, with each alternate code point having probability information associated therewith. As each character is received, the alternate code points therefor are placed at the end of a queue, and a cost is determined from each alternate code point to any immediately preceding alternate in the queue. The cost is based on the probability information of the alternates and a transition cost therebetween. Then, the lowest cost path back from each of the alternates at the end of the queue to an alternate at the beginning of the queue is determined. If each lowest cost path back converges at (traverses) a common alternate in the queue, the common alternate and any alternates previous thereto on the path back are recognized as the code points for each of the handwritten characters associated therewith. The alternates corresponding to recognized code points are removed from the queue, and the code points appropriately displayed on a screen as recognized characters, to allow editing thereof or the like.

[0014] Other objects and advantages will become apparent from the following detailed description when taken in conjunction with the drawings, in which:

[0015] FIG. 1 is a block diagram representing a computer system into which the present invention may be incorporated;

[0016] FIG. 2 is a representation of an exemplary touch-sensitive screen for inputting user information to the system and for outputting system information to the user;

[0017] FIG. 3 is a block diagram representing functional components for recognizing handwritten characters according to the present invention;

[0018] FIGS. 4A-4C represent an exemplary sequence of handwritten user characters with corresponding character alternatives returned by a shape matcher and buffered and analyzed for context recognition thereof;

[0019] FIGS. 5A-5F represent an alternate exemplary sequence of handwritten user characters with corresponding character alternatives returned by a shape matcher and buffered and analyzed for context recognition;

[0020] FIG. 6 is a representation of a simplified state machine used to perform context recognition on the characters of FIGS. 5A-5F;

[0021] FIG. 7 is a representation of a lattice of alternative paths and showing cost information of some of the paths for the buffered alternative characters of FIG. 5C;

[0022] FIGS. 8A-8B comprise a flow diagram representing the general steps taken to perform full context recognition while displaying partial results in accordance with one aspect of the present invention;

[0023] FIG. 9 is a representation of a dictionary state machine used to perform context recognition;

[0024] FIG. 10 is a representation of a bigram state machine used to perform context recognition; and

[0025] FIG. 11 is a representation of a lattice of alternative paths resulting from the state machines of FIGS. 9 and 10.

[0026] Turning to the drawings and referring first to FIG. 1, there is shown a computer system generally designated 20 into which the present invention may be incorporated. The computer system 20 includes a processor 22 operatively connected to storage 24, the storage including read only memory (ROM), random access memory (RAM) and non-volatile storage such as a hard disk-drive, optical drive or the like. As can be appreciated, the non-volatile storage can be used in conjunction with the RAM to provide a relatively large amount of virtual memory via well-known swapping techniques.

[0027] The processor 22 also connects through I/O circuitry 28 to one or more input devices 30₁-30₃, such as a keyboard and/or a pointing device such as a mouse. The system 20 includes means for inputting pen-based information, including handwritten characters, such as a pen and/or pen-sensitive (e.g., touch-sensitive) input device 30₃. The system 20 also includes at least one local output device 34 connected to the I/O circuitry 28 for communicating information, such as via a graphical user interface, to the user of the system 20. The output device 34 may include a liquid crystal display screen or the like integrated with the pen-input device 30₃, which, taken together, can be considered a pen-sensitive screen 36 (FIG. 2).

[0028] A preferred system 20 is a hand-held personal computing device running on the Windows CE operating system loaded in the storage 24. At least one application program such as a word processing program may also be loaded into the storage 24.

[0029] As shown in FIG. 2, the pen-sensitive screen 36 includes a visible manifestation of a text buffer 38 for displaying and allowing edit control of the text characters that have been input into and recognized by the system 20. As described in detail below, if the character is a handwritten character, the system 20 recognizes the character in part by its shape, from among a set of possible computer characters, (e.g., ASCII or Unicode code points). The system 20 also recognizes the character in part from its full context, i.e., its surrounding characters both forward and backward. In accordance with one aspect of the invention and as described in detail below, the code point is transferred to the text buffer 38, i.e., recognized character buffer 38, and displayed therein in an appropriate font and font size, when it is established that the additional context cannot change the code point regardless of further character input.

[0030] The touch screen 36 preferably includes one or more button input areas 40₁-40₃(FIG. 2), which may provide a virtual keyboard through which the user may directly input characters, character-based editing commands and so on. For example, the buttons may represent characters, such that when contacted by a pen, the character is input into the system as if it was typed by the user on a conventional keyboard. In addition, the user may use such buttons to enter editing commands, such as Backspace or Enter commands, by touching the screen 36 at an appropriately displayed button in the one of the areas 40₁-40₃.

[0031] As shown in FIG. 2, for inputting handwritten characters, the display/touch-sensitive screen 36 typically includes two or more pen input display areas 42-44. In general, the pen input display areas 42-44 are used to receive handwritten characters from the user in the form of strokes. The user typically alternates character input between the boxes 42-44. For example, a user will write in the first box 42, with the system echoing the pen movement on the screen by darkening or coloring the contacted areas, giving the user the impression that the pen has ink therein. When the user begins writing in the second box 43, it is assumed that the character in the first box 42 is complete. The stroke information from the first box 42 is thus sent to a recognition process 48, and the displayed strokes (ink) in the first box 42 are erased. Note that the recognizer runs on a separate thread whereby it can recognize a character while the user is writing the next character. Similarly, the same actions occur in the second box 43, i.e., the strokes are sent for character recognition thereof and the second box 43 erased upon a detection that the user is now writing in the third box 44 (or has returned to write in the first box 42). A time-out when no pen activity is detected is also treated as a completed character, as will a direct command from the user, entered via one of the button input areas 40₁-40₃or the like, indicating that the user is finished with a character.

[0032] In accordance with one aspect of the invention and as best shown in FIG. 3, when the user inputs a character, the recognition process 48 receives the character and sends the character data (e.g., the stroke or bitmap information) to a shape matcher 50. The shape matcher 50 compares the character data against shape data 52 maintained in the storage 24. The shape data 52 may be organized in one or more databases containing character shape information accumulated from samples taken from thousands or even millions of users.

[0033] In keeping with the invention, the shape matcher 50 returns a list of possible alternates 54 (i.e., possible code points) for the character, each alternate having a probability (or some other weighted value) associated therewith indicative of the likelihood of the user-entered character's match with the sample data. For example, the leftmost part of FIG. 4A shows one such (hypothetical) ranked list 54₁of five alternates for the handwritten character (intended by the user to be a capital “P”) input via one of the boxes 42-44. Based upon the actual shape versus the sample shape data 52, as determined by the shape matcher 50, the lowercase “p” may have fifty percent chance (likelihood) of being what the user intended, the uppercase “P” a forty-eight percent chance, the “D” a one percent chance, and so on totaling (or closely approaching) one hundred percent. Note that in the actual system, the shape matcher 50 may return in the list 54 any number of alternative characters, or a fixed number of alternates such as the most-probable twenty. Moreover, instead of a percentage, the preferred shape matcher 50 returns a cost proportional to how unlikely each alternative is. The cost equals the negative of the natural log of the percentage probability, to determine the lowest cost path as described below. Negative natural logs are used since some of the probabilities can be very small percentages, and since summing the costs (performed by a known algorithm) corresponds to multiplying the percentages.

[0034] Once the shape matcher 50 has returned the ranked list of character alternatives 54, the recognition process 48 appends the list 54 to a context recognition buffer 56 or the like containing similar ranked lists for any preceding characters, if any, which have not yet been recognized. In accordance with another aspect of the invention, each of the alternates of the preceding character has a cost associated with transitioning to each of the alternates of the most recent character. As can be appreciated, this forms a lattice of possible paths (e.g., FIG. 7) between the most recent character's alternates and the previous character's alternates. A state machine 58, statistically derived from a language model or some other source and kept in the storage 24, maintains information needed to determine the costs of transitioning from each alternative of the last-written character to each of the alternatives of the preceding character.

[0035] The recognition process 48 then uses a context computation process 60 to compute the total cost to reach each of the character alternatives of the last written character. A preferred context computation process uses an algorithm described in the paper entitled “The Viterbi Algorithm,”G. David Forney Jr., Proceedings of the IEEE, VOL 61, No. 3, (1973). The Viterbi algorithm is known in the character recognition art and is thus not described in detail herein, except to summarize that the algorithm finds the lowest cost path from among a lattice of possible paths between nodes, wherein each node has a cost associated therewith and each branch between any two nodes has a cost associated therewith.

[0036] Thus, as shown in FIGS. 4A-4C, as each character is written, the cost of each path, including the cost of the alternates and the transition cost, are computed for each path. The lowest cost path to get to each of the last-written character's alternates are saved along with the cost. More particularly, a backpointer from each of the last-written alternates pointing on the lowest cost backpath to a predecessor alternate is saved, along with the cost, in a pointer-cost data table 62 or the like for use by the recognition process 48 as described below.

[0037] By way of example, FIG. 4A shows five alternates in a list 54₂within the context recognition buffer 56 for the second box, intended by the user to be a lowercase “a” character. Each of the alternates in the list 54₂have a cost to get from the alternates in the list 54₁thereto. The lowest of these costs are saved as a backpointer, shown as an arrow in FIGS. 4A-4C. Note that the various characters and paths shown in this example are only for the purposes of providing a conceptual illustration, and are not necessarily derivable from any real data. Thus, in this example, the lowest cost path to get to the lowercase “o” character in the list 54₂is from the lowercase “p” alternate in box 54₁, the “a” in 54₂to the capital “P” in 54₁, and so on. As shown in FIG. 4A, backpointers are stored for each of these lowest cost paths. As can be appreciated, in a typical case, not all of the previous character's alternates (e.g., the “b” and “f” in the list 54₁, of FIG. 4A) have a backpointer thereto, since they are not on any of the last-written alternates' lowest cost paths. Conversely, those alternates that do have backpointers pointing thereto (shown as shaded in FIGS. 4A-4C) are considered to be active.

[0038] As characters are added, such as shown in FIGS. 4B-4C, the process is repeated. The backpointers are only saved for previous alternates that are active, since only active alternates can be on the lowest cost path back. Thus, as shown in FIG. 4B, the “t”-shaped character's alternates in the list 54₃all point to either the “o” or the “a” alternates in the list 54₂, and thus the backpointers from the “u,” “c” and “n” characters are no longer active. Similarly, as shown in FIG. 4C, all of the alternates in the list 54₄corresponding to the fourth box have backpointers to either the “t” or “E” of the third box's list 54₃.

[0039] In accordance with one aspect of the invention, when the backpointers converge to one active alternate in given list of alternates, that alternate and any of its preceding alternates on the path back therefrom are considered to be recognized. Those alternates are then placed as code points in the recognized character (text) buffer 38 for displaying to the user, and the lists containing those alternates removed from the context recognition buffer 56. This is possible because further context, no matter what characters are entered, will not change this convergence. Thus, in the example shown in FIG. 4C, a “Pa” will be placed in the recognized character buffer 38 and the lists 54₁and 54₂removed from the context recognition buffer 56.

[0040] Turning to an explanation of the invention with particular reference to FIGS. 5A-5F and the flow diagram of FIGS. 8-8B, in the following example, the user intends to input the string “loops_” into the system by writing into the input boxes 42-44 as described above. For purposes of readability, FIGS. 5A-5F show the characters as they are added to the system, (e.g., the user has just begun writing in the next box), and with the underscore character in FIG. 5F representing a space character. Also, for purposes of simplicity, in this example, the simplified state machine 60₁represented in FIG. 6 is used to determine transition costs, with only lowercase letters (including the space character) and numerical digits zero through nine allowed. According to the rules of the simplified state machine 60₁, the set of lowercase letters, represented by an “l.c.” in FIG. 6, have a seventy-five percent chance of being followed by another lowercase letter and a twenty-five percent chance of being followed by a number. The set of numbers, represented by an “N” in FIG. 6, have a seventy-five percent chance of being followed by another number and a twenty-five percent chance of being followed by a letter. Of course, it is understood that more complex state machines based on various language models or the like may be used to determine transition costs in actual systems.

[0041] As described above, the system considers a character to be entered when the user begins writing in another box, stops writing for a sufficiently long period of time (times out), or directly commands the system to enter the character. Thus, the recognition process 48 begins when an input character's data is received at step 800 (FIG. 8), as shown in FIG. 5A (wherein the user has just begun to write in another box). At step 802, the recognition process 48 passes the character information (e.g., coordinates representing the strokes, a bitmap or some other appropriate format) to the shape matcher 50 for recognition thereof. As shown in FIG. 5B, at step 804, the shape matcher 50 returns a ranked list of alternates 54₁, and the ranked list 54₁is appended to the (currently empty) context recognition buffer 56. In the present example, as shown in FIG. 5B, for the vertical stroke entered by the user, the two top alternatives are a one (“1”) and a lowercase letter-L (“l”), each having a forty-nine percent probability, or alternatively, cost=−ln(0.49)=0.7133. Other character alternates, such as an “i” (assumed undotted) and a “t” (uncrossed) may be also returned with much lower probabilities but are not separately shown.

[0042] At step 806, since the user is writing in another box, (e.g., input box 43), the process determines that the user is not done writing, an act which would force the end of the recognition process as described below. For now, the process 48 continues to step 808. At step 808, a set of currently active alternates are established as all of the alternates returned in the list 54₁(by the shape matcher 50) for the last character written, the vertical stroke. (Step 810, described below, is a computation process for determining the lowest cost paths between alternates of adjacent entries, but since this is the first entry, the only cost is the cost of each alternate at this time.) The process thus continues to step 820 (FIG. 8B) to test if the number of active alternates in the current set is one. Since the shape matcher 50 has returned more than one alternate for this first character, all of which are active, the process continues to step 822.

[0043] Step 822 tests to determine if the current set of active alternates belongs to the first character in the context recognition buffer 56. At this time, this is true, so step 822 returns to step 800 (FIG. 8A) to await the next handwritten character.

[0044] As shown in FIG. 5B, sometime later the user begins to write another character in a third box, having completed the circular-shaped character in the second box. Accordingly, the circular-shaped character information is received at step 800, and sent to the shape matcher at step 802. As shown in FIG. 5C, a list of alternates 54₂, including a lowercase “o” and a zero (“0”) are returned and placed in the context recognition buffer 56 at step 804, the zero shown with a slash therethrough in FIG. 5C. Both choices again have forty-nine percent probabilities, or alternatively, cost=−ln(0.49)=0.7133.

[0045] Step 806 again tests to determine if the user is done writing, and since the user is still writing, the process continues to step 808. At step 808, the currently active alternates are the alternates of the last box written, i.e., the “o” and the “0” (plus others, not separately shown). Then, at step 810, the context recognition process 48 uses the state machine 60₁, along with the costs returned by the shape matcher with each alternate, to compute and determine the lowest cost path from the previous to each of the alternates returned for the last written (circular shaped) character. FIG. 7 shows the lattice of paths and the cost information for the paths, shown as percentage probabilities for comparative readability purposes. For additional clarity, the following table sets forth the transition costs for this lattice (with lowercase “l” shown as a capital and the numbers written out to avoid confusion) based on the state machine 60₁, of FIG. 6:

[0046] In keeping with the invention, as described above, the context computation process 60 (Viterbi algorithm) is used at step 810 to determine the lowest cost paths to the alternates of the last written character by summing the costs. As apparent from an analysis of FIG. 7 and as shown in FIG. 5C, backpointers from the zero (“0”) to the one (“1”) and from the “o” to the “l” show the results of the computation. The process 48 then continues to step 820 of FIG. 8B.

[0047] Since there are at least these two alternates, step 820 of FIG. 8B branches to step 822, wherein it is determined that the list 54₂does not represent the first character in the context recognition buffer 56. As a result, step 822 branches to step 824 where the currently active alternates are changed to alternates representing the previous character that are active (have backpointers thereto), i.e., the one (“1”) and the “l” in the list 54₁. Note that in the present example, each of the alternates in the list 54₂that are not separately shown also have to point to either the one (“1”) alternate or the “l” alternate. This is because of the low cost of these top two alternates relative to the possible transition costs under the rules of the state machine 60₁.

[0048] The process then returns to step 820 with the new set of currently active alternates, wherein it is determined that more than one alternate is active in the list 54₁. Accordingly, step 820 branches to step 822 where this time it is determined that the set of currently active alternates belong to the list representing the first character in the context recognition buffer 56. Step 822 thus returns to step 800 of FIG. 8A.

[0049] The next character, another circular-shaped entry, is handled in substantially the same manner as was the previous character. Thus, assuming at step 804 that the shape matcher returns approximately the same probabilities, the “o” alternate in the list 54₃(FIG. 5D) is assigned a backpointer to the “o” alternate in the list 54₂, and the zero (“0”) in the list 54₃a backpointer to the alternate in the list 54₂. As is apparent from FIG. 5D, for each loop through steps 820-824, step 820 again fails to detect any list with only one active alternate therein before the first character is reached at step 822.

[0050] The next entered character, however, the lowercase “p” character, begins to change the context in a way that will ultimately decide the characters in the string. More particularly, the “p” character in the list 54₄receives a high probability, such as ninety-five percent (i.e., low cost, equal to 0.0513), while the other characters such as the “8” receive much lower probability, such as four percent (cost equals 3.2189). However, this time through the recognition process 48, the cost for all of the alternates for the last written character are computed at step 810, with a backpointer assigned to each as shown in FIG. 5E. Thus, although the “8” is unlikely, at this time it is still considered a viable possibility, and thus according the rules of the state machine 60₁, the backpointer from the “8” points to the previous character's zero (“0”) alternate.

[0051] Finally, the user completes the next, s-shaped character and begins another character (by causing a space character to be entered in some manner) as shown in FIG. 5F. At step 802, the s-shaped character is sent to the shape matcher 50. As shown in FIG. 5F, a “5” and an “s” is returned at step 804 with some cost assigned to each, along with other alternates in the list 54₅. Again, in the present example the user is not finished writing at step 806, and thus at step 808 the currently active alternates are the “5” and the “s” (plus others, not separately shown) of the list 54₅.

[0052] At step 810, because of the low cost of the “p,” the cost from the “5” to the “p” is still lower than from the “5” to the “8,” notwithstanding the transition cost differential from the state machine 60₁. In other words, using the numbers stated above, 95 percent times 25 percent is greater than 4 percent times 75 percent, and thus the backpointer from the “5” is to the preceding “p” alternate instead of the preceding “8” alternate. As can be appreciated, this is true of any other alternates not separately shown.

[0053] Once the backpointers have been computed at step 810, the process continues to step 820 of FIG. 8B. At step 820, because there are at least these two alternates, the process branches to step 822. Step 822 determines that this is not the first character in the context recognition buffer 56, and thus continues to step 824 where the currently active alternate set is changed to point to the “p” alternate in the previous list of alternates. Note that only the “p” alternate is placed in the set because only the “p” alternate is active, i.e., has a backpointer thereto.

[0054] As a result, step 820 determines that the number of currently active alternate is now one, and thus branches to step 826. At step 826, the sole currently active alternate, the “p” alternate, is placed along with its preceding alternates on its lowest cost backpath (i.e., “loops”) into the recognized character buffer 38. Then, at step 828, the lists 54₁-54₄corresponding to these now-recognized characters are removed from the context recognition buffer 56 whereby, the list 54₅containing the “5” and the “s” alternates becomes the first entry in the context recognition buffer 56.

[0055] As can be appreciated, the above-described process thus places partial results into the recognized character buffer 38 as soon as available, yet uses a full context recognition process that is as accurate as waiting for an entire string to be completed before analysis thereof. Although the string “loop” was somewhat of an extreme example chosen to show the advantages over backwards-only recognition, in practice it has been found that one to three characters are ordinarily all that are needed by the process of the present invention before the backpointers converge to a common alternate. This provides acceptably rapid visual feedback along with the improved accuracy of full context recognition, while requiring only a small amount of memory for electronic ink. Significantly, once recognized with the above process, characters are not later changed regardless of further characters input into the string.

[0056] Lastly, when the user has finished writing, step 806 will detect that there are no more characters forthcoming from which forward context recognition can be accomplished. At such a time, the process 48 branches to step 812 to find the lowest-cost path back in order to determine the best characters of those remaining. Note that step 812 is just the conventional use of the Viterbi algorithm, used as if the remaining string was the full string entered all-at-once for recognition.

[0057] The above-described simplified state machine has the properties that every state is connected to every other state and any given code point always transitions to the same state regardless of the state in which it started. Any digit always goes to the digit state and any letter always goes to the letter state. In such an instance, the code point always uniquely determines the state, so there is no need to store the state separately. Moreover, all of the states are in a valid state. As can be appreciated, the simplified machine is a bigram state transition machine, which has one state per character in the alphabet, each state is connected to every other state (including itself). A slightly more complex bigram state machine is arranged as a table having transition costs corresponding to the probability of letter bigrams implied by the states, i.e., the cost to transition from “a” to “b” is the probability of seeing an “ab” bigram in normal text. The shape matcher returns a list of code point, score pairs. The set of lists maintained by the context recognition process (engine) is actually a list of triples, i.e., code point, score, state, along with a backpointer.

[0058] However, more complex state machines which implement language models are often desirable, such as a trie-structured dictionary state machine, or a nondeterministic state machine. With a dictionary state machine, the same letter has different states depending on what letters have come before. Moreover, most states only allow transition on a few letters. For example, only a “u” is a valid transition from the “q” state.

[0059] To accomplish context recognition in accordance with the present invention using more complex state machines, as before, for each box of ink the shape matcher returns a list of alternates which is made up character code points with associated probabilities. The context recognition process (i.e., context engine) takes this list of alternatives, and for each alternative, generates a list of all language model states that could be transitioned to with this character from the previous list of language model states. The language model states correspond to different paths through the character alternate arrays that are valid character transitions in the language model. The context recognition process computes the total path score for each of the new language model states by summing the cost of the character alternative assigned by the shape matcher with the cost of the transition from the previous language model state to the current language model state.

[0060] By way of example, the user is inputting the word “cattle” in lowercase as shown in FIG. 11. For purposes of simplicity, in the present example, as shown in FIG. 11, only two character alternatives are returned for each written box, the top choice having a seventy-five percent probability associated therewith, and the bottom choice a twenty-five percent probability. FIG. 9 shows a simplified dictionary state machine 70 having only three words therein which are relevant to the following example, i.e., “cattle”, “oat” and “octant”. Note that the “v” shown in states 13, 7 and 14 indicate a valid end of a word (termination) as described below. FIG. 10 shows a simplified eight-character bigram state machine 72 that will also be used in the present language model example, with the character for transitioning to each state shown as a character in parentheses within the numbered state. The bigram state machine 72 starts with a low probability such as one percent, corresponding to the fact that most words (ninety-nine percent) are expected to be in the dictionary 70. This means that the process selects a dictionary word if one is reasonable, but still can select a non-dictionary word. Note that more than one such state machine is included so that the user is not limited to writing only dictionary words, otherwise as will become apparent below, all paths would be pruned whenever a word was not in the dictionary. Indeed, a bigram state machine, such as 72 with each state being valid to terminate an input string, (and thus which cannot fail), is ordinarily provided for this purpose.

[0061] To integrate other state machines with the dictionary state machine, the context recognition uses the language model state alternative generating process mentioned above, e.g., on the first character box, every code point in the first box's ranked list of codepoint alternatives is used to generate the list of language model states that could be transitioned to.

[0062] For this example each code point alternative generates two language model state alternatives, with the one at the top pointing to the dictionary 70 and the one at the bottom pointing to the bigram state machine 72. Note that since the same character can transition to two different language model states at the same time, this is the same as creating a single nondeterministic state machine from the combination of the various state machines.

[0063] Nondeterministic state machines are described by Knuth, The Art of Computer Programming, Addison-Wesley (1973).

[0064] Note that both state machines 70, 72 share a common initial start state, indicated by the zero state in both FIGS. 9 and 10. Thus, in the present example, four initial language model state alternatives are created from the first box's proposed codepoint alternatives of “c” and “o” that were returned, with a list of quadruples maintained for each language model state alternative generated that includes the code point, state, cost and a backpointer.

[0065] At this time, the quadruples are [c, 1, (0.75* 0.99* 0.5), NUL]; [c, 101, (0.75* 0.01* 0.125), NUL]; [o, 2, (0.25* 0.99* 0.5), NUL]; [o, 104, (0.25* 0.01* 0.125), NUL]. The costs are shown as probabilities and are determined by the probability of the code point (0.75 for “c” and 0.25 for “o”), times the cost of the state machine (0.99 for the dictionary 70, 0.01 for the bigram 72), times the cost of the transition from the initial state (0.5 in the dictionary since two possible branches exist and 0.125 in the bigram since eight possible branches exist). Note that in actual state machines, many more branches would exist and the probabilities assigned to each would sum to one, but not necessarily be equal, e.g., the chance of the first character in a word within a dictionary beginning with an “s” is much greater than a word beginning with an “x.” Dictionary states are generally named after prefixes, and thus the “c” is in the “c” state and the “o” is in the “o” state with respect to the dictionary. Note that in a full dictionary trie, these are 32-bit indexes into a table, and not actually strings. When the code point alternate list for the next ink box is returned, i.e., the “a” (0.75 chance) and the “c” (0.25 chance), the context recognition process generates the language model state alternatives that can be transitioned to from the previous box's four language model state alternates via the two code point alternates returned in the alternate list. The two code point alternatives thus generate as many as eight language model states in this example. However, based on the state machine 70, not all of these eight state machine alternatives are viable. More particularly, as shown in FIG. 9, with respect to the dictionary 70, the previous “c” can transition to the “a”, and the previous “o” to either the “a” or a “c” alternates, but the dictionary state machine 70 does not allow for the previous “c” to transition to another “c”. This eliminates the potential quadruple therefor from the list. Moreover, some of the states in the language model state alternate list for this character box are duplicates. As the Viterbi algorithm is being used to find the lowest cost path through the language model states, it is evident to one familiar with the Viterbi algorithm that only the lowest cost path to a state needs to be kept.

[0066] In each such duplicate instance, the highest cost (lowest probability) duplicates are pruned, whereby the character that made the transition with the lowest cost path to a previous state is kept. The search for duplicates and their removal is preferable done as the list is built, thus dynamically pruning the number of paths.

[0067] In the present example, the quadruples for the second box are [a, 3, (0.75* 0.75* 0.99* 0.5), Πc,1], [a, 100, (0.75* 0.75* 0.01* 0.125* 0.125), Πc,101], [a, 4, (0.25* 0.75* 0.99* 0.5* 0.5), Πo,2], [a, 100, (0.25* 0.75* 0.01* 0.125* 0.125), Πo,104], [c, 101, (0.25* 0.75* 0.01* 0.125* 0.125), Πc,101], [c, 5, (0.25* 0.25* 0.99* 0.5* 0.5), Πo,2], and [c, 101, (0.25* 0.25* 0.01* 0.125* 0.125), Πo,104], where the “Π” represents a backpointer to a previous (code point alternate, state) pair. As is apparent, there are duplicate (a, 100) and (c, 101) states, (it is irrelevant that the character transitions are also identical), and as described above, only the lowest cost (highest probabilities) of these are kept. Thus, the fourth and seventh of the above listed seven quadruples are removed. FIG. 11 shows the remaining code points, states and backpointers, at this time only looking back from Roman numerals II to I. For now, it should be noted that the backpointers from the second alternates are to two distinct characters, “c” and “o”, and thus for now no partial results may be displayed. The display of partial results will be described below at the time in the example that such partial results are capable of being safely displayed.

[0068] The next character entered is either a “t” (75% probability) or an “x” (25% probability). From the dictionary state machine 70, states 3, 4 and 5 can all transition via a “t” to states 6, 7 and 8, respectively, while from the bigram state machine 72, states 100 and 101 can transition to state 105 via a “t”. However, in the dictionary 70, none of the states 3, 4 or 5 can validly transition to another state via the “x” alternate, and thus these dictionary “x” quadruples drop out. The “x” is a valid bigram transition, of course, from state 100 to state 106 and state 101 to state 106. The valid quadruples, this time shown without values for probabilities (which can be determined as described above) for purposes of simplicity, are thus [t, 6, (PROB), Πa,3]; [t, 105, (PROB), Πa,100]; [t, 7, (PROB), Πa,4]; [t, 105, (PROB), Πc,101]; [t, 8, (PROB), Πa,5]; [x, 106, (PROB), Πa,100] and [x, 106, (PROB), Πc,101]. By evaluating the costs, the latter of the two (t, 105) duplicates and the latter of the two (x, 106) duplicates are the lower probability duplicates of each, and thus removed, whereby at this time, the remaining code point alternates, states, and backpointers are as shown in FIG. 11 from Roman numeral III back to Roman numeral I. Again, it should be noted for now that the backpointers from any state on back are to at least two distinct characters, and thus no partial results may be safely displayed at this time.

[0069] Following the above explanation, it should be apparent that the next (fourth) character entered, which also has a “t” and “x” returned as alternates therefor, have only three quadruples after excluding invalid transitions and removing duplicates. These remaining quadruples, shown without values for their probabilities, are [t, 9, (PROB), Πt,6]; [t, 105, (PROB), Π,105]; and [x, 106, (PROB), Πt,105]. Note that this is because there was no valid “t” or “x” transition from state 7 or 8 to another state in the dictionary 70, and no valid “x” transition from state 6. Moreover, the lowest costs duplicates in the bigram state machine 72 were for the t, 105 state that had a backpointer to the t, 105 state and the x, 106 state that had a backpointer to the t, 105 state, and thus the higher cost (i.e., lower probability) duplicates were removed. The code points, states and backpointers thus appear as in FIG. 11 from Roman numeral IV back to Roman numeral I.

[0070] In keeping with the present invention, the algorithm that determines which characters can be displayed safely is modified to search backwards through the queue of language model states for each character box, until all the still active language model states for an ink box have converged to the same proposed alternate character. Note that this does not mean the paths must converge, (since each state machine will have its own path, if any, pointing to its own state), but that any remaining paths represent the same character. At present in the case that the language model is a non-deterministic state machine, the algorithm includes a rule, stating that the requirement that all the paths represent the same character has to hold for all ink boxes back to the first ink box written to safely display the character alternate. For example, if the only two active paths left were for “paternal” and “pottery,” it would appear that at the third letter “t” the paths have merged for the same character. However, the characters are not the same all the way back to the first “p” character, and thus these first three characters in the string are not considered safely recognized.

[0071] In the present example, however, the backpointers from the fourth character alternates (IV) are to a common character, “t”, either via a (t, 6) or a (t, 105). In turn, each of these “t” backpointers are to an “a” character, which in turn are to a “c” character. As a result, even though on different paths, the first three characters, “cat” can be safely written to the recognized character (text) buffer 38 for displaying to the user.

[0072] When the inking process is completed, and completion of the recognition is forced by a time out or the user hitting the recognize button, a final symbol “end” is generated. Only those states that can transition to the end state on “end” are considered valid. For example, if the user hit “recognize” after entering only “catt,” the states for the dictionary path would be discarded since the state numbered 9 is not a valid termination point. States which are valid termination points are marked as such such as by having a specific bit set therein. As can be appreciated, if all dictionary states are discarded, in the present example only bigram states would remain. In this manner, even with the low-probability (one percent) assigned to bigram states, the bigram states may become the ones used for context recognition. Note however, that the “cat” string, which was already written to the text buffer, is not changed by this termination regardless of which path is used.

[0073] As can be appreciated, implementing this search allows a sophisticated language model made up of state machines, of which some of the state machines may be dictionaries organized as state machines (trie state machine in the present implementation). This enables a dictionary search with forward and backward context, while providing partial results that cannot be changed by further input.

[0074] In addition, using this technique, other state machines can be added. For example, a special state machine for numbers can be added, such as one which knows about commas, currency symbols, and decimal points. Another state machine for computer file names, or Internet URLs can be added. Significantly, a user may add a personal supplementary dictionary of private words.

[0075] Moreover, other considerations are handled wherein the context recognition process creates a list of language model state entries from the ranked code point list provided by the shape matcher. A first consideration is when the same character can go to more than one state in the same state machine. For example, this happens with upper and lower case letters, i.e., most words are valid in all lower case (e.g., “word”), with an initial capital, (e.g., “Word”) and in all capitals, (e.g., “WORD”). Other variations are prohibited, e.g., “wOrD”). Second, some words need to be capitalized, (e.g., “Florida” or “FLORIDA”, but not “florida”), and a few are always all capitalized (e.g., “USA”). Of course, in the computer, a capital ‘F’ and a lower-case ‘f’ are different letters, so if the first letter is ‘F’ the context engine needs to match that to both the “f” state and the “F” state. The dictionary state machine itself is slightly augmented to make this work, i.e., it “remembers” whether it has capitalized any letters or not. As can be appreciated by one skilled in the art, this is easily done by adding an appropriate number of bits to the state number, which is equivalent to creating a dictionary state machine with many more states to represent all the states a word can be in.

[0076] A third consideration for which the context recognition process creates multiple language model state entries from a single code point in the shape matchers alternate list is when there is more than one state machine, as described above. This usually happens only at the beginning of input, but it can also happen (for example) when a hyphen, dash, slash, or space is encountered. Because it is important that there be at least one valid state machine for any input, the bigram state machine is used, via which, at the beginning of input, each element in the first ranked list gets a bigram state and a dictionary state. It is also useful to also include state machines for currency amounts, file names, Internet URLs, and so on.

[0077] To this end, the dictionary itself may be nondeterministic, to handle compound forms, e.g., words or terms containing a space, (such as “habeus corpus”), a hyphen (such as “T-shirt”) or a slash (such as “I/O”). Normally, any two dictionary words separated by space, hyphen, or slash are allowed, but it is even more desirable in certain instances to allow a non-dictionary word only when it is part of such a compound. This is accomplished by adding the compound form (including the space, dash, slash and so on) to the dictionary and then letting the context recognition process split each character in the next ranked list, i.e., one going back to the initial dictionary state and the other continuing from the space, dash, or slash. For example, with “I/O”, the “I” is acceptable by itself, but the “O” is probably not, whereby the form “I/O” is added.

[0078] Lastly, although the described embodiment uses characters written in boxes, it will be apparent to one skilled in the art that this algorithm also works for the unconstrained case. It can be readily appreciated that in the unconstrained case, some of the arrows (backpointers) will point back two or more columns rather than always pointing to the immediately previous column of alternates.

[0079] As can be seen from the foregoing detailed description, there is provided an improved method and mechanism for performing full-context recognition. The full context recognition method and mechanism enables rapid visual feedback while having relatively low memory requirements. The method and mechanism function with existing recognition components such as shape matching components and language model context components, and is fast, reliable, cost-efficient, flexible and extensible.

[0080] While the invention is susceptible to various modifications and alternative constructions, certain illustrated embodiments thereof are shown in the drawings and have been described above in detail. It should be understood, however, that there is no intention to limit the invention to the specific forms disclosed, but on the contrary, the intention is to cover all modifications, alternative constructions, and equivalents falling within the spirit and scope of the invention.