System and method for recognizing user-specified pen-based gestures using hidden markov models

• US 6,304,674 B1
• Filed: 08/03/1998
• Issued: 10/16/2001
• Est. Priority Date: 08/03/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Cass, Todd A., Wilcox, Lynn D., Tenev, Tichomir G.
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/128,255
• Time in Patent Office: 1,170 Days
• Field of Search: 382/181, 382/186, 382/187, 382/224, 382/155, 382/159, 382/228, 382/103, 704/243, 704/245, 704/256, 704/202, 704/232, 706/20
• US Class Current: 382/224
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

A method for recognizing user specified pen-based gestures uses Hidden Markov Models. A gesture recognizer is implemented which includes a fast pruning procedure. In addition, an incremental training method is utilized.

Claims

1. A method adapted for use in a system for recognizing user specified gestures, the method comprising steps of:

a) initiating a training mode of the system;

b) specifying a gesture class to which a first single gesture belongs, a gesture class comprising at least one subclass of gestures;

c) inputting the first gesture to the system;

d) training a first sample Hidden Markov Model (HMM) on the first gesture, the first sample HMM being classified in the at least one subclass that belongs to the specified gesture class;

e) inputting a subsequent gesture to the system, the subsequent gesture belonging to the specified gesture class;

f) training a subsequent sample HMM on the subsequent gesture;

g) comparing the subsequent sample HMM to a threshold HMM to determine therebetween a first distance;

h) comparing the subsequent sample HMM to one of an HMM and HMMs of the at least one subclass belonging to the specified gesture class to determine therebetween one of a second distance and second distances;

i) selecting a single HMM of the one of HMM and HMMs of the at least one subclass corresponding to a shortest second distance;

j) merging the subsequent sample HMM with the selected single HMM if the first distance is greater than the second distance whereby the selected single HMM is modified;

k) creating a new subclass, comprising the subsequent sample HMM, if the first distance is less than the shortest second distance; and

,

l) performing steps e) through k) for subsequent gestures belonging to the specified gesture class that are input to the system.

2. The method as set forth in claim 1 further comprising presetting a standard deviation threshold level.

3. A method adapted for use in a system for recognizing user specified gestures wherein a specified gesture class has been initialized to include at least one single input gesture, the method comprising steps of:

a) inputting a subsequent gesture to the system, the subsequent gesture belonging to the specified gesture class;

b) training a subsequent sample HMM on the subsequent gesture;

c) comparing the subsequent sample HMM to a threshold HMM to determine therebetween a first distance;

d) comparing the subsequent sample HMM to an HMM or HMMs of at least one subclass belonging to the specified gesture class to determine therebetween a second distance or distances;

e) selecting a single HMM of the HMMs of the at least one subclass corresponding to a shortest second distance;

f) merging the subsequent sample HMM with the selected single HMM if the first distance is greater than the second distance whereby the selected single HMM is modified; and

,

g) creating a new subclass, comprising the subsequent sample HMM, if the first distance is less than the shortest second distance.

4. The method according to claim 3 further comprising performing steps a) through g) for additional subsequent gestures belonging to the specified gesture class that are input to the system.

5. The method as set forth in claim 3 wherein a standard deviation is set to a preselected threshold level.

6. A method adapted for use in a system for recognizing user specified gestures, the method comprising steps of:

inputting a single gesture;

training a sample Hidden Markov Model (HMM) on the single gesture;

comparing the sample HMM to a threshold HMM to determine therebetween a first distance;

sequentially comparing the sample HMM to a plurality of HMMs to determine respective second distances between the sample HMM and each of the plurality, each of the plurality representing a subclass of gestures;

selecting HMMs of the plurality that correspond to second distances that are less than the first distance;

computing the probability of the gesture relative to the selected HMMs of the plurality; and

,

determining a subclass to which the gesture most likely belongs based on the computing.

7. A method adapted for use in a system for recognizing user specified gestures, the method comprising steps of:

inputting a single gesture;

training a sample Hidden Markov Model (HMM) on the single gesture;

comparing the sample HMM to a threshold HMM to obtain first data;

sequentially comparing the sample HMM to a plurality of HMMs to determine second data;

selecting HMMs of the plurality based on the first and second data;

computing the probability of the gesture relative to the selected HMMs of the plurality; and

,

determining a subclass to which the gesture most likely belongs based on the computing.

8. A system for recognizing user specified gestures, the system comprising:

means for initiating a training mode of the system;

means for specifying a gesture class to which a first single gesture belongs, a gesture class comprising at least one subclass of gestures;

means for inputting the first gesture to the system;

means for training a first sample Hidden Markov Model (HMM) on the first gesture, the first sample HMM being classified in the at least one subclass that belongs to the specified gesture class;

means for inputting a subsequent gesture to the system, the subsequent gesture belonging to the specified gesture class;

means for training a subsequent sample HMM on the subsequent gesture;

means for comparing the subsequent sample HMM to a threshold HMM to determine therebetween a first distance;

means for comparing the subsequent sample HMM to an HMM or HMMs of the at least one subclass belonging to the specified gesture class to determine therebetween a second distance or distances;

means for selecting a single HMM of the HMM of the at least one subclass corresponding to a shortest second distance;

means for merging the subsequent sample HMM with the selected single HMM if the first distance is greater than the second distance whereby the selected single HMM is modified; and

means for creating a new subclass, comprising the subsequent sample HMM, if the first distance is less than the shortest second distance.

9. A system for recognizing user specified gestures wherein a specified gesture class has been initialized to include at least one single input gesture, the system comprising:

means for inputting a subsequent gesture to the system, the subsequent gesture belonging to the specified gesture class;

means for training a subsequent sample HMM on the subsequent gesture;

means for comparing the subsequent sample HMM to a threshold HMM to determine therebetween a first distance;

means for comparing the subsequent sample HMM to an HMM or HMMs of at least one subclass belonging to the specified gesture class to determine therebetween a second distance or distances;

means for selecting a single HMM of the HMM of the at least one subclass corresponding to a shortest second distance;

means for merging the subsequent sample HMM with the selected single HMM if the first distance is greater than the second distance whereby the selected single HMM is modified; and

,

means for creating a new subclass, comprising the subsequent sample HMM, if the first distance is less than the shortest second distance.

10. A system for recognizing user specified gestures, the system comprising:

means for inputting a single gesture;

means for training a sample Hidden Markov Model (HMM) on the single gesture;

means for comparing the sample HMM to a threshold HMM to determine therebetween a first distance;

means for sequentially comparing the sample HMM to a plurality of HMMs to determine respective second distances between the sample HMM and each of the plurality, each of the plurality representing a subclass of gestures;

means for selecting HMMs of the plurality that correspond to second distances that are less than the first distance;

means for computing the probability of the gesture relative to the selected HMMs of the plurality; and

,

means for determining a subclass to which the gesture most likely belongs based on the computing.

11. A system for recognizing user specified gestures, the system comprising:

means for inputting a single gesture;

means for training a sample Hidden Markov Model (HMM) on the single gesture;

means for comparing the sample HMM to a threshold HMM to obtain first data;

means for sequentially comparing the sample HMM to a plurality of HMMs to determine second data;

means for selecting HMMs of the plurality based on the first and second data;

means for computing the probability of the gesture relative to the selected HMMs of the plurality; and

,

means for determining a subclass to which the gesture most likely belongs based on the computing.