Image analysis – Pattern recognition – Context analysis or word recognition
Reexamination Certificate
2000-05-16
2002-07-09
Au, Amelia M. (Department: 2623)
Image analysis
Pattern recognition
Context analysis or word recognition
C382S187000
Reexamination Certificate
active
06418239
ABSTRACT:
FIELD OF THE INVENTION
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.
BACKGROUND OF THE INVENTION
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.
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.
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.
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.
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.
OBJECTS AND SUMMARY OF THE INVENTION
Accordingly, it is a general object of the present invention to provide an improved method and mechanism for performing full-context recognition.
Another object is to provide a full context recognition method and mechanism that facilitates rapid visual feedback while having relatively low memory requirements.
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.
Yet another object is to provide a method and mechanism of the above kind that is fast, reliable, cost-efficient, flexible and extensible.
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.
Other objects and advantages will become apparent from the following detailed description when taken in conjunction with the drawings, in which:
REFERENCES:
patent: 4589142 (1986-05-01), Bednar
patent: 4876731 (1989-10-01), Loris et al.
patent: 5067165 (1991-11-01), Nishida
patent: 5151950 (1992-09-01), Hullender
patent: 5289270 (1994-02-01), Hayashi
patent: 5321773 (1994-06-01), Kopec et al.
patent: 5377281 (1994-12-01), Ballard et al.
patent: 5392363 (1995-02-01), Fujisaki et al.
patent: 5526444 (1996-06-01), Kopec et al.
patent: 5615286 (1997-03-01), Patel
patent: 5742705 (1998-04-01), Partasarathy
patent: 6023529 (2000-02-01), Ilan et al.
patent: 6061472 (2000-05-01), Hullender et al.
patent: 6111985 (2000-08-01), Hullender et al.
Burges et al., “Recognition of Handwritten Cursive Postal Words Using Neural Networks,” USPS Advanced Technol Conference, (Nov.-Dec. 2, 1992).
Burges et al., “Shortest Path Segmentation: A Method for Training a Neural Network to Recognize Character Strings,” IJCNN '92 Conference Proceedings, vol. 3, pp. 165-171 (1992).
Rumelhart, David E., “Theory to Practice: A Case Study—Recognizing Cursive Handwriting,”Computational Learning&Cognition,Proceedings of the Third NEC Research Symposium, Chapter 8, pp. 177-196 (1992).
Forney, Jr., G. David, “The Viterbi Algorithm,” Proceedings of the IEEE, vol. 61, No. 3, (Mar. 1973) pp. 268-278.
Haluptzok Patrick M.
Hullender Gregory N.
Au Amelia M.
Law Offices of Albert S. Michalik PLLC
Miller Martin
LandOfFree
Method and mechanism for providing partial results in full... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and mechanism for providing partial results in full..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and mechanism for providing partial results in full... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2857073