Scribble matching

• US 6,018,591 A
• Filed: 11/19/1997
• Issued: 01/25/2000
• Est. Priority Date: 07/04/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Gupta, Dipankar, Reynolds, David, Hull, Richard
• Primary Examiner(s): Lee, Thomas D
• Assistant Examiner(s): Chen, Wenpeng
• Application Number:
  US08/974,704
• Time in Patent Office: 797 Days
• Field of Search: 382/122, 382/120, 382/186, 382/187, 382/188, 382/138, 382/175, 382/192
• US Class Current: 382/186
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

The present invention relates to scribble matching methods, ie. methods for searching samples of electronic ink without having first to translate the ink into ASCII text. The methods of the present invention find application in pen-based computer devices. The invention entails the identification and encoding of velocity minima in the input scribble. Three scribble matching algorithms are described--a syntactic matcher, a word matcher and an elastic matcher. The syntactic matcher encodes the input scribble according to the shape of the scribble in the region of the velocity minima. The word matcher encodes the input scribble according to the heights of the velocity minima from a reference line, using a continuous height encoding scheme. The elastic matcher encodes the input scribble according to a classification of the velocity minima and intermediate points. The use of velocity minima in the encoding of scribble input provides a stable set of points and leads to improved performance in comparison with known scribble matching methods.

Claims

1. A method of matching samples of electronically stored freehand input with other stored samples of freehand input, the method comprising:

locating velocity minima in each said freehand input sample;

coding each said freehand input sample by a sequence of symbols each representing a feature of the freehand input sample at a velocity minimum which is one of said velocity minimum; and

matching each said sequence of symbols against codes of said other stored samples of freehand input using a string edit distance metric;

wherein at least one of said freehand input samples is a figure exceeding a single text character, and said matching is completed for each said freehand input sample without identification of said freehand input sample as a sequence of individual text characters.

2. A method according to claim 1 wherein the feature encoded is a shape of the freehand input in a region of the velocity minimum and the symbols represent a set of shape characteristics, and wherein edit costs, used to calculate the string edit distance, are dependent on the shape characteristics.

3. A method according to claim 2 wherein the set of shape characteristics comprises;

cusp, open curve, closed curve and line end.

4. A method according to claim 3 wherein substitution costs are used in calculating the string edit distances, and substitution costs between line ends and other shape characteristics are lower than substitution costs between shape characteristics which are not line ends.

5. A method according to claim 3 wherein the set of shape characteristics further comprises miscellaneous smooth curves and diacritical marks, and insertion and deletion costs for these shape characteristics are lower than insertion and deletion costs for shape characteristics which are not miscellaneous smooth curves or diacritical marks.

6. A method according to claim 2 wherein the edit costs are also dependent on a probability of occurrence of corresponding edit operations.

7. A method according to claim 1 comprising encoding a normalized height of the freehand input at the velocity minima relative to a reference line, wherein the height is encoded on a continuous scale and edit costs, used to calculate the string edit distance, are dependent on the encoded heights.

8. A method according to claim 7 wherein edit costs for deletions and insertions correspond to a magnitude of encoded heights of relevant velocity minima and edit costs for substitutions correspond to a difference in height of relevant velocity minima.

9. A method according to claim 1 comprising:

coding the freehand input by a sequence of symbols which also represent features of points intermediate the velocity minima, wherein the intermediate points are generated by a resampling of the freehand input between velocity minima;

providing a point classification of the velocity minima and the intermediate points, said classification being either a break in electronic ink, a velocity minimum or an intermediate point;

encoding points including the velocity minima and the intermediate points by a triple containing a normalised height of the point, an angle to a tangent of the freehand input at the point, and said point classification; and

calculating the string edit distance using edit costs dependent on differences in height, angle and point classification.

10. A method according to claim 9 wherein the resampling comprises polygonal resampling.

11. A method according to claim 2, further comprising the steps of:

encoding normalized height of the freehand input at the velocity minima relative to a reference line, wherein the normalized height is encoded on a continuous scale and the edit costs are dependent on the encoded heights; and

calculating a weighted sum of match scores obtained from matching said sequence of symbols where said symbols represent a set of shape characteristics and from matching said sequence of symbols where said symbols represent a normalized height of the freehand input at the velocity minima relative to a reference line, to obtain an overall match score.

12. A method according to claim 11, wherein the step of matching the sequence of symbols against codes of other samples of freehand input includes a step of reducing match candidates of said electronically stored freehand input by implementation of a pruning algorithm and a linear matching algorithm.

13. A method according to claim 2, further comprising the steps of:

coding the freehand input by a sequence of symbols which also represent features of points intermediate the velocity minima, wherein the intermediate points are generated by a resampling of the freehand input between velocity minima;

providing a point classification of the velocity minima and the intermediate points, said classification being either a break in electronic ink, a velocity minimum or an intermediate point;

encoding points including the velocity minima and the intermediate points by a triple containing a normalised height of the point, an angle to a tangent of the freehand input at the point, and said point classification;

using edit costs dependent on differences in height, angle and point classification; and

calculating a weighted sum of match scores obtained from matching said sequence of symbols where said symbols represent a set of shape characteristics and from matching said sequence of symbols where said symbols represent said triple, to obtain an overall match score.

14. A method according to claim 13, wherein the step of matching the sequence of symbols against codes of other samples of freehand input includes a step of reducing match candidates of said freehand input sample by implementation of a pruning algorithm and a linear matching algorithm.

15. A method according to claim 9, further comprising the steps of:

encoding normalized height of the freehand input at the velocity minima relative to a reference line, wherein the normalized height is encoded on a continuous scale and the edit costs are dependent on the encoded heights; and

calculating a weighted sum of match scores obtained from matching said sequence of symbols where said symbols represent the normalized height of the freehand input at the velocity minima relative to a reference line, and from matching said sequence of symbols where said symbols represent said triple, to obtain an overall match score.

16. A method according to claim 15, wherein the step of matching the sequence of symbols against codes of other samples of freehand input includes a step of reducing match candidates of said electronically stored freehand input by implementation of a pruning algorithm and a linear matching algorithm.

17. A method according to claim 2, further comprising the steps of:

encoding normalized height of the freehand input at the velocity minima relative to a reference line, wherein the normalized height is encoded on a continuous scale and the edit costs are dependent on the encoded heights;

coding the freehand input by a sequence of symbols which also represent features of points intermediate the velocity minima, wherein the intermediate points are generated by a resampling of the freehand input between velocity minima;

providing a point classification of the velocity minima and the intermediate points, said classification being either a break in electronic ink, a velocity minimum or an intermediate point;

encoding points including the velocity minima and the intermediate points by a triple containing a normalised height of the point, an angle to a tangent of the freehand input at the point, and said point classification;

using edit costs dependent on differences in height, angle and point classification; and

calculating a weighted sum of match scores obtained from matching said sequence of symbols where said symbols represent a set of shape characteristics, from matching said sequence of symbols where said symbols represent the normalized height of the freehand input at the velocity minima relative to a reference line, and from matching said sequence of symbols where said symbols represent said triple, to obtain an overall match score.

18. A method according to claim 17, wherein the step of matching the sequence against codes of other samples of freehand input includes the step of reducing match candidates of said electronically stored freehand input by implementation of a pruning algorithm and a linear matching algorithm.

20. A method according to claim 1, wherein matching the sequence of symbols against codes of other samples of freehand input includes the step of reducing match candidates of said electronically stored freehand input by implementation of a pruning algorithm and a linear matching algorithm.

19. An apparatus for matching samples of electronically stored freehand input with other stored samples of freehand input, said apparatus comprising:

a velmin locator for locating velocity minima in each said freehand input sample;

a freehand input encoder responsive to velocity minima received from said velmin locator, said freehand input encoder coding each said freehand input sample by a sequence of symbols, each symbol representing a feature of the freehand input at a velocity minimum which is one of said velocity minima; and

a matcher responsive to said sequence of symbols received from said encoder, said matcher matching the sequence of symbols against codes of other samples of freehand input by using a string edit distance metric;

wherein at least one of said freehand input samples is a figure exceeding a single text character, and said matcher matches each said freehand input sample without identifying it as a sequence of individual text characters.

25. An apparatus as claimed in claim 19, further comprising storage for selected samples of freehand input coded by said freehand input encoder, wherein the matcher is adapted to match the output of the freehand input encoder against codes of the selected samples of freehand input stored in the storage.

21. A method of matching samples of electronically stored freehand input, said method comprising:

locating velocity minima in a first freehand input sample;

coding the first freehand input sample by a sequence of symbols each representing a feature of the first freehand input sample at a velocity minimum which is one of said velocity minima;

storing said coded first freehand input sample;

repeating said steps of locating velocity minima, coding and storing for each of a plurality of further first freehand input samples to obtain a stored set of coded first freehand input samples;

locating velocity minima in a second freehand input sample;

coding the second freehand input sample by a sequence of symbols each representing a feature of the second freehand input sample at a velocity minimum; and

matching the sequence of symbols from the second freehand input sample against the stored set of coded first freehand input samples using a string edit distance metric;

wherein at least one of said first freehand input samples is a figure exceeding a single character, and said matching is completed without identification of said at least one of said first freehand input samples sequence of individual text characters.

22. A method as claimed in claim 21, wherein said steps of coding the first freehand input samples and of coding the second freehand input sample comprise coding a shape of the freehand input in a region of the velocity minimum and the symbols represent a set of shape characteristics and wherein edit costs, used in calculating the sting edit distance metric, are dependent on the shape characteristics.

23. A method as claimed in claim 21, wherein said steps of coding the first freehand input samples and of coding the second freehand input sample comprise encoding normalized height of the freehand input at the velocity minima relative to a reference line, wherein the normalized height is encoded on a continuous scale and edit costs, used in calculating the string edit distance metric, are dependent on the encoded heights.

24. A method as claimed in claim 21, wherein said steps of coding the first freehand input samples and of coding the second freehand input sample comprise:

coding each said freehand input sample by a sequence of symbols which also represent features of points intermediate the velocity minima, wherein the intermediate points are generated by a resampling of the freehand input between velocity minima;

providing a point classification of the velocity minima and the intermediate points, said classification being either a break in the electronic ink, a velocity minimum or an intermediate point;

encoding points including the velocity minima and the intermediate points by a triple containing a normalised height of the point, an angle to a tangent of the freehand input at the point, and said point classification.

26. A method of matching a test sample of electronically stored freehand input with other stored samples of freehand input, said method comprising:

locating velocity minima in the test sample of freehand input;

coding the test sample of freehand input according to a plurality of coding steps, wherein each coding step comprises coding the test sample of freehand input by a sequence of symbols each representing a feature of the test sample of freehand input at a velocity minimum which is one of said velocity minima;

for each sequence of symbols generated by one of said plurality of coding steps, matching the sequence of symbols against codes of other samples of freehand input using a string edit distance metric to provide a match score; and

calculating a weighted sum of the match scores to obtain an overall match score for each of the other samples of freehand input;

wherein the method of matching is performed on a plurality of test samples at least one of which is a figure exceeding a single text character, and matching does not include identification of any of said plurality of test samples as a string of individual text characters.

27. A method as claimed in claim 26, wherein one of the plurality of coding steps consists of coding a shape of the freehand input in a region about the velocity minimum and the symbols represent a set of shape characteristics and wherein edit costs, used it calculating the string edit distance in the matching step, are dependent on the shape characteristics.

28. A method as claimed in claim 26, wherein one of the plurality of coding steps consists of encoding normalized heights of the freehand input at the velocity minima relative to a reference line, wherein the normalized heights are encoded on a continuous scale, and wherein edit costs, used in calculating the string edit distance in the matching step, are dependent on the encoded heights.

29. A method as claimed in claim 26, wherein one of the plurality of coding steps consists of:

coding the freehand input by a sequence of symbols which also represent features of points intermediate the velocity minima, wherein the intermediate points are generated by a resampling of the freehand input between velocity minima;

providing a point classification of the velocity minima and the intermediate points, said classification being either a break in the electronic ink, a velocity minimum or an intermediate point;

encoding points including the velocity minima and the intermediate points by a triple containing a normalised height of the point, an angle to a tangent of the freehand input at the point, and said point classification.