Searching and Matching unrecognized handwriting

• US 5,687,254 A
• Filed: 06/06/1994
• Issued: 11/11/1997
• Est. Priority Date: 06/06/1994
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Weber, Karon Anne, Poon, Alex D., Cass, Todd A.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Davis, Monica S.
• Application Number:
  US08/254,382
• Time in Patent Office: 1,254 Days
• Field of Search: 382/241, 382/313, 382/229, 382/178, 382/186, 382/226, 382/230, 382/187, 395/800, 364/231.9, 364/229.2, 364/259, 364/259.2
• US Class Current: 382/229
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet
• CPC Class Codes: G06V 40/20 Movements or behaviour, e.g. gesture recognition recognition of facial expressions G06V40/16

Abstract

A method and system provide for searching and matching gesture-based data such as handwriting without performing a recognition process on the handwritten gesture data to convert it to a standard computer-coded form. Target data collected as sample data points of spatial coordinates over time are concatenated into a single target gesture sequence of sample data points. The sample data points comprising the gesture-based data structure to be searched (the corpus) are grouped into corpus gesture sequences for matching against the target gesture sequence. Matching may be done by any suitable method, and a novel signal comparison technique based on dynamic time warping concepts is illustrated. The result of the matching is a list of the locations of the matching corpus gesture sequences in the corpus, which in turn may be used for further processing, such as the display of an image of the matching corpus gestures for a system user. The ability to determine the existence and location of a gesture in the corpus that matches a target gesture is the basis for performing a variety of additional functions, such as a "find and replace" function and the ability to use gestures as keywords to index a gesture-based data structure without performing recognition on either the keyword gestures or the gesture-based data structure. The technique is suitable for inclusion in any system that accepts gesture-based data, such as a personal digital assistant (PDA) or other pen-based computing device.

Claims

1. A method of operating a machine including a signal source for providing data based on gestures, memory for storing data based on gestures, and a processor connected for receiving signals;

the method comprising;

receiving target gesture-based data from the signal source;

the target gesture-based data including a plurality of target sample data points ordered in time indicating a first path of motion over a first interval of time of a target gesture;

accessing a gesture-based data structure, referred to hereafter as a corpus data structure, stored in the machine memory;

the corpus data structure including a plurality of corpus gestures;

each respective corpus gesture including a plurality of sample corpus data points ordered in time indicating a respective path of motion over a respective interval of time of the respective corpus gesture;

performing a grouping operation using the corpus sample data points included in the corpus data structure to produce a plurality of corpus gesture sequences of sample data points;

each corpus gesture sequence including at least two time-ordered consecutive sample data points included in a respective one of the corpus gestures in the corpus data structure;

a first one of the corpus gesture sequences sharing time-ordered consecutive sample data points in common with a second one of the corpus gesture sequences such that when a single corpus gesture included in the corpus data structure indicates a sequence of handwritten symbols, overlapping first and second corpus gesture sequences indicate first and second overlapping subsequences of handwritten symbols;

comparing the target gesture-based data to each of the corpus gesture sequences to determine whether the target gesture-based data matches at least one of the corpus gesture sequences; and

producing a matching list of matching corpus gesture sequences that match the target gesture-based data without assigning a semantic label to any respective one of the matching corpus gesture sequences identifying the respective matching corpus gesture sequence;

the list including, for each matching corpus gesture sequence, a location in the corpus data structure of the matching corpus gesture sequence.

2. The method of claim 1 wherein the target gesture-based data includes first and second strokes that are consecutive in time;

and wherein the method further includes, prior to comparing the target gesture-based data to each of the corpus gesture sequences, concatenating together the last sample data point of the first stroke with the first sample data point of the second stroke into a target gesture sequence of the first plurality of sample data points;

each corpus gesture sequence being compared to the target gesture sequence.

3. The method of claim 1 wherein the signal source is a stylus providing data based on gestures of a machine user.

4. The method of claim 3 wherein the machine further includes a display device including a display area for presenting images therein;

wherein an image including display features representing at least a portion of the corpus data structure is presented in the display area; and

wherein the target gesture-based data received from the machine user is selected by the user from the corpus data structure using the stylus device to interact with the image of the portion of the corpus data structure to select the target gesture-based data.

5. The method of claim 1 further including

producing an image using the matching list;

the image including display features indicating at least one matching corpus gesture sequence included in the matching list; and

presenting the image to a machine user on a display device included in the machine.

6. The method of claim 1 wherein, when the target gesture-based data does not match any one of the corpus gesture sequences, the matching list is empty.

7. The method of claim 1 wherein the signal source is an image scanning device providing image definition data defining an image including a plurality of display features;

and wherein the method further includes a converting step for converting the image definition data defining the image including a plurality of display features to the target gesture-based data including the first plurality of sample data points ordered in time.

8. The method of claim 7 wherein the display features included in the image represent gestures.

9. The method of claim 1 wherein the corpus data structure stored in the system memory was converted from image definition data defining an image including a plurality of display features;

the image definition data being converted to a plurality of corpus gestures each including a plurality of sample corpus data points ordered in time.

10. The method of claim 9 wherein the display features included in the image represent gestures.

13. The method of claim 1 wherein each corpus gesture included in the corpus data structure includes at least one stroke, referred to as a corpus stroke;

and wherein, when the grouping operation produces a corpus gesture sequence that includes a sequence of time-ordered consecutive sample data points fewer in number than a sequence of time-ordered consecutive sample data points included in a respective corpus stroke in the corpus data structure, the corpus gesture sequence indicates a portion of a stroke;

the target gesture-based data being compared to the portion of the stroke to determine whether the target gesture-based data matches the corpus gesture sequence.

14. The method of claim 1 wherein each corpus gesture included in the corpus data structure includes at least one stroke, referred to as a corpus stroke;

and wherein performing the grouping operation to produce a plurality of corpus gesture sequences of sample data points includes grouping sample data points by stroke such that each corpus gesture sequence is referred to as a corpus stroke sequence and includes at least one stroke;

first and second overlapping corpus gesture sequences including at least one identical stroke.

15. The method of claim 14 wherein performing the grouping operation to produce a plurality of corpus stroke sequences includes

(a) initializing a corpus stroke counter n to 1;

(b) initializing a grouping counter m to 1;

(c) grouping corpus strokes n to n+m-1 into a corpus stroke sequence until grouping counter m reaches a maximum value; and

(d) incrementing corpus stroke counter n and repeating steps (b) and (c) for each value of n to a maximum number of strokes in the corpus data structure.

16. The method of claim 1 wherein the plurality of corpus gestures included in the corpus data structure indicates strings of handwritten characters;

the overlapping first and second corpus gesture sequences indicating first and second substrings of handwritten characters such that comparing the target gesture-based data to the corpus gesture sequences produces a match of the target gesture-based data to substrings of handwritten characters indicated by the corpus gestures included in the corpus data structure.

17. The method of claim 1 wherein the plurality of corpus gestures included in the corpus data structure indicates groups of handwritten graphical symbols;

the overlapping first and second corpus gesture sequences indicating first and second subgroups of handwritten graphical symbols such that comparing the target gesture-based data to the corpus gesture sequences produces a match of the target gesture-based data to subgroups of handwritten graphical symbols indicated by the corpus gestures included in the corpus data structure.

18. The method of claim 1 wherein comparing the target gesture-based data to each of the corpus gesture sequences to determine whether the target gesture-based data matches at least one of the corpus gesture sequences includes using a dynamic programming technique.

19. The method of claim 1 wherein comparing the target gesture-based data to each of the corpus gesture sequences to determine whether the target gesture-based data matches at least one of the corpus gesture sequences includes using a dynamic time warping technique to compare a target stroke function of sample data points of the target gesture-based data to a corpus stroke function of sample data points of each corpus gesture sequence;

the target stroke function being mapped to a corpus stroke function of sample data points on a sample data point by sample data point basis by warping a time axis of each of the target and corpus stroke functions.

11. A processor-controlled machine comprising:

a signal source for providing target gesture-based data including a plurality of target sample data points ordered in time indicating a first path of motion over a first interval of time of a target gesture;

a processor connected for receiving the target gesture-based data from the signal source; and

memory for storing data;

the data stored in the memory including instruction data indicating instructions the processor can execute, and a gesture-based data structure, referred to hereafter as a corpus data structure;

the corpus data structure including a plurality of corpus gestures;

each respective corpus gesture including a plurality of sample corpus data points ordered in time indicating a respective path of motion over a respective interval of time of the respective corpus gesture;

the processor being further connected for accessing the data stored in the memory;

the processor, in executing the instructions in response to receiving the target gesture-based data from the signal source,

performing a grouping operation using the corpus sample data points included in the corpus data structure to produce a plurality of corpus gesture sequences of corpus sample data points;

each corpus gesture sequence including at least two time-ordered consecutive corpus sample data points included in a respective one of the corpus gestures in the corpus data structure;

a first one of the corpus gesture sequences sharing time-ordered consecutive sample data points in common with a second one of the corpus gesture sequences such that when a single corpus gesture included in the corpus data structure indicates a sequence of handwritten symbols, overlapping first and second corpus gesture sequences indicate first and second overlapping subsequences of handwritten symbols;

comparing the target gesture-based data to each of the corpus gesture sequences to determine whether the target gesture-based data matches one of the corpus gesture sequences; and

producing a list of matching corpus gesture sequences that match the target gesture-based data without assigning a semantic label to any respective one of the matching corpus gesture sequences identifying the respective matching corpus gesture sequence;

the list including, for each corpus gesture sequence, the location in the corpus data structure of the matching corpus gesture sequence.

20. The machine of claim 11 wherein the machine further includes a display device including a display area for presenting images therein;

wherein an image including display features representing at least a portion of the corpus data structure is presented in the display area;

wherein the signal source is a stylus device for providing data based on gestures of a machine user; and

wherein the target gesture-based data received from the machine user is selected by the machine user from the corpus data structure using the stylus device to interact with the image of the portion of the corpus data structure to select the target gesture-based data.

21. The machine of claim 11 wherein the plurality of corpus gestures included in the corpus data structure indicates strings of handwritten characters;

the overlapping first and second corpus gesture sequences indicating first and second substrings of handwritten characters;

the processor, in executing the instructions to compare the target gesture-based data to the corpus gesture sequences, producing a match of the target gesture-based data to substrings of handwritten characters indicated by the corpus gestures included in the corpus data structure.

12. An article of manufacture for use in a processor-controlled machine that includes a user input device for receiving signals indicating actions and requests of a machine user;

memory for storing data;

a storage medium access device for accessing a medium that stores data; and

a processor connected for receiving data from the user input device and for accessing the data stored in the memory;

the processor further being connected for receiving data from the storage medium access device;

the article comprising;

a data storage medium that can be accessed by the storage medium access device when the article is used in the machine; and

data stored in the data storage medium so that the storage medium access device can provide the stored data to the processor when the article is used in the machine;

the stored data including target gesture receiving instruction data indicating input instructions the processor can execute to receive target gesture-based data from the user input device;

the target gesture-based data including a plurality of target sample data points ordered in time indicating a first path of motion over a first interval of time of a target gesture;

the stored data further including operation performing instruction data indicating response instructions the processor can execute to perform operations for searching for the target gesture-based data in a gesture-based data structure stored in the memory, in response to the target gesture-based data;

the gesture-based data structure being hereafter referred to as a corpus data structure;

the corpus data structure including a plurality of corpus gestures;

each respective corpus gesture including a plurality of sample corpus data points ordered in time indicating a respective path of motion over a respective interval of time of the respective corpus gesture;

when the target gesture-based data is received, execution of the response instructions causing the processor to perform a grouping operation using the corpus sample data points included in the corpus data structure to produce a plurality of corpus gesture sequences of sample data points;

each corpus gesture sequence including at least two time-ordered consecutive sample data points included in a respective one of the corpus gestures in the corpus data structure;

a first one of the corpus gesture sequences sharing time-ordered consecutive sample data points in common with a second one of the corpus gesture sequences such that when a single corpus gesture included in the corpus data structure indicates a sequence of handwritten symbols, overlapping first and second corpus gesture sequences indicate first and second overlapping subsequences of handwritten symbols;

execution of the response instructions further causing the processor to compare the target gesture-based data to each of the corpus gesture sequences to determine whether the target gesture-based data matches at least one of the corpus gesture sequences;

when a corpus gesture sequence is matched to the target gesture-based data, execution of the response instructions causing the processor to produce a list of matching corpus gesture sequences without assigning a semantic label to any respective one of the matching corpus gesture sequences identifying the respective matching corpus gesture sequence;

the list of matching corpus gesture sequences including the location in the corpus data structure of each matching corpus gesture sequence.

22. The article of manufacture of claim 12 wherein the processor-controlled machine further includes a display device including a display area for presenting images therein;

wherein an image including display features representing at least a portion of the corpus data structure is presented in the display area;

wherein the user input device is a stylus device for providing data based on gestures of the machine user;

wherein the target gesture-based data is selected by the machine user from the corpus data structure using the stylus device to interact with the image of the portion of the corpus data structure to select the target gesture-based data; and

wherein the input instructions the processor executes to receive the target gesture-based data from the user input device causes the processor to obtain the target gesture-based data from the corpus data structure using position data indicated by the stylus device.

23. The article of manufacture of claim 12 wherein the plurality of corpus gestures included in the corpus data structure indicates strings of handwritten characters;

the overlapping first and second corpus gesture sequences indicating first and second substrings of handwritten characters;

execution of the response instructions to compare the target gesture-based data to the corpus gesture sequences causing the processor to produce a match of the target gesture-based data to substrings of handwritten characters indicated by the corpus gestures included in the corpus data structure.