Image analysis – Pattern recognition – Classification
Reexamination Certificate
1998-08-03
2001-10-16
Mehta, Bhavesh (Department: 2621)
Image analysis
Pattern recognition
Classification
C382S103000, C382S159000, C382S181000, C382S228000, C704S232000, C704S256000, C706S020000
Reexamination Certificate
active
06304674
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a system and method for recognizing user specified pen-based gestures. More particularly, the method utilizes Hidden Markov Models (HMMs) that are applied to an incremental training procedure and a recognition procedure that incorporates a fast pruning approach.
While the invention is particularly directed to the art of gesture recognition and training therefor, and thus will be described with specific reference thereto, it will be appreciated that the invention may have applicability to other areas, such as speech recognition and word matching for pen-based systems.
By way of background, an active and rapidly growing area of personal computing today, both in the academic and commercial arenas, involves computers using pen-based user interfaces. Examples of such devices incorporating pen-based user interfaces include Personal Digital Assistants (PDAs) which are useful for maintaining personal information such as notes, calenders, etc. Recognition of pen gestures—which form the basis of command and data input—is a very important factor in the success of PDAs and other pen-based systems.
More specifically, single stroke gestures provide an intuitive user interface and are useful for editing text and graphics in much the same way as a teacher would use special correlation characters when grading students' homework. Furthermore, use of recognizable gestures is necessary for devices which lack keyboards and rely entirely on pen-based input.
Presently, there are a number of applications in which gestures form a part of the user interface. However, there are numerous problems with creating a reliable recognition scheme. The main problem is the large variety of gesture types and wide variability in the manners in which different users may draw the ago same gesture.
The variety of gestures presents a problem in selecting the characteristic which best distinguishes between gestures. For instance, that which distinguishes a square from a circle is the corners. However, this is not a valid distinction if one desires to distinguish a square from a rectangle. Accordingly, it is difficult to choose a distinguishing feature even if the gestures to be recognized are known, let alone if the gesture is not known in advance.
On the other hand, choosing characteristics that are too particular also limits the range of gestures that can be successfully distinguished. For instance, if a feature set for a square includes four corners and specific dimensional data, then only squares satisfying that criteria will be recognized, not all squares.
Known gesture recognizers require improvements. First, in some cases, the accuracy of these gesture recognizers is not acceptable for use in real world applications. When too many errors are made during gesture recognition, the user will usually revert to clumsier but more accurate input devices such as the keyboard or pull down menus.
Second, the recognizers that are known are specifically designed around a fixed set of gestures—the application is restricted to gestures in this predefined set. In some applications, this is an undesirable restriction. In addition, the user must often draw the gestures in the way prescribed by the system in order for them to be correctly recognized.
Third, in traditional approaches to recognition, a gesture is run through, or processed by, a recognizer and a likelihood that the subject gesture belongs to each of a variety of classes in the recognizer is determined, and nothing else. Accordingly, the class having the best likelihood is determined but that class is not necessarily the correct class. It is only the class with the best likelihood. Thus, the results are unreliable and not reached efficiently.
It would, therefore, be desirable to include in the process a normalization (or a ground level or threshold) to determine that the best class is, at the very least, above a certain level. This feature is not present in known gesture recognition systems.
The present invention contemplates a new and improved gesture recognition method which resolves the shortcomings of the prior schemes.
SUMMARY OF THE INVENTION
A method for use in a system for recognizing user specified gestures is provided. The method and system are reliable, utilize incremental training to adapt to user needs and efficiently handle recognition.
In one aspect of the invention, Hidden Markov Models (HMMs) are used to incrementally train a system on particular gestures.
In another aspect of the invention, a procedure for recognition of input gestures that includes a fast pruning method is used. The fast pruning procedure includes comparing HMMs to HMMs, as opposed to comparing gestures to HMMs, to eliminate HMMs that do not satisfy predetermined threshold criteria relative to the gesture. Comparing HMMs to HMMs is convenient relative to comparing a gesture to HMMs because HMMs can be compared based on a limited number states (e.g. twelve (12) in the preferred embodiment) whereas comparing a gesture to an HMM requires alignment of forty (40) to fifty (50) features with the states of the HMM. For pruning purposes according to the present invention, comparisons involving twelve states is sufficient.
Further scope of the applicability of the present invention will become apparent from the detailed description provided below. It should be understood, however, that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art.
REFERENCES:
patent: 5502774 (1996-03-01), Bellegarda et al.
patent: 5644652 (1997-07-01), Bellegarda et al.
patent: 5649023 (1997-07-01), Barbara et al.
patent: 5687254 (1997-11-01), Poon et al.
patent: 5768423 (1998-06-01), Aref et al.
patent: 5781663 (1998-06-01), Sakaguchi et al.
patent: 5806030 (1998-09-01), Junqua
patent: 5842165 (1998-11-01), Raman et al.
patent: 5875256 (1999-02-01), Brown et al.
patent: 0 464 467 A2 (1992-01-01), None
x “Similarity Measure of Hidden Markov Models”, IBM Technical Disclosure Bulletin, Dec. 1991, pp. 326-329.*
Yang, et al. “Gesture Interface: Modeling and learning”, IEEE, 1994, pp. 1747-1752.*
Young “Competitive Training in Hidden Markov Models”, IEEE, 1990, pp. 681-684.*
L. R. Rabiner, “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”,IEEE—Stochastic Approaches, pp. 267-296 (1989).
George M. Miller, “On-Line Recognition of Hand-Generated Symbols”,University of California—Fall Joint Computer Conference, 1969, pp. 399-412.
Joonki Kim, “On-Line GestureRecognition By Feature Analysis”,Vision Interface '88, Edmonton Convention Centre, pp. 51-55 (Jun. 6-10, 1988).
Dean Rubine, “Specifying Gestures by Example”,Computer Graphics, vol. 25, No. 4, pp. 329-337, (Siggraph '91, Las Vegas) (Jul. 1991).
Kyoji Hirata et al., “Rough Sketch-Based Image Information Retrieval”,NEC Research&Development, vol. 34, No. 2, pp. 263-273, Japan (Apr. 1993).
Thierry Paquet et al., “Recognition of Handwritten Sentences Using a Restricted Lexicon”,Pattern Recognition, vol. 26, No. 3, pp. 391-407 (1993).
Walid Aref et al., “The Handwritten Trie: Indexing Electronic Ink”,Matsushita Information Technology Laboratory, Princeton, NJ, pp. 1-25 (Oct. 1994).
Daniel Lopresti et al., “On the Searchability of Electronic ink”,The Fourth International Workshop on Frontiers in Handwritting Recognition, Grand Hotel, Taiwan, pp. 156-165 (Dec. 1994).
Cass Todd A.
Tenev Tichomir G.
Wilcox Lynn D.
Fay Sharpe Fagan Minnich & McKee LLP
Mariam Daniel G.
Mehta Bhavesh
Xerox Corporation
LandOfFree
System and method for recognizing user-specified pen-based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for recognizing user-specified pen-based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for recognizing user-specified pen-based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2599054