Method and apparatus for similarity matching of handwritten data objects

• US 5,710,916 A
• Filed: 06/16/1995
• Issued: 01/20/1998
• Est. Priority Date: 05/24/1994
• Status: Expired due to Term

• Current Assignee: Panasonic Corporation Of North America (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Technologies, Inc. (Panasonic Holdings Corporation)
• Inventors: Kamel, Ibrahim, Barbara, Daniel
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/491,506
• Time in Patent Office: 949 Days
• Field of Search: 395/600, 395/603, 395/605, 395/606, 395/609, 382/13, 345/575, 345/600, 345/700
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• 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/2276 with probabilistic networks, e.g. hidden Markov models
• CPC Class Codes: G06V 30/333 Preprocessing; Feature extraction
• CPC Class Codes: G06V 30/36 Matching; Classification
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

Apparatus for determining a distance between two handwritten strings in a database. A processor extracts global features from each string. The processor divides the string into strokes, and identifies a plurality of bounding boxes. Each box contains a different stroke. The processor extracts global features from the suing, including: (1) a number of points; (2) a maximum angle between a first point in the string and a corner of the tallest bounding box; (3) a number of positive inversions; and (4) a number of negative inversions. The apparatus calculates the distance between the strings based on all of the numbers of points, maximum angles, numbers of positive inversions and numbers of negative inversions. A fixed query tree index may be formed. The tree has leaves and internal nodes belonging to multiple levels. A different key is associated with each level. Each key is a handwritten string. Each string is associated with one of the leaves, such that each child of each internal node in any of the levels between the one leaf and the root node is a root of a respective subtree. Each string associated with any leaf in the subtree which includes the one leaf is equally distant from the key associated with the one level, based on the global features. The tree is queried to search for a subset of the strings, such that each string in the subset is within a threshold distance of an input string, according to the distance function.

Claims

1. In a database having a plurality of handwritten strings, apparatus for determining a distance between two of the plurality of strings, comprising:

(a) a processor for extracting a plurality of global features from each one of the plurality of handwritten strings in the database, comprising;

(1) means for dividing the handwritten string into a plurality of strokes;

(2) means for identifying a plurality of bounding boxes, each bounding box containing a respectively different one of the plurality of strokes;

(3) means for extracting from the string;

(A) a number of points in the string,

(B) a maximum angle between a first one of the points in the string and a corner of a tallest one of the plurality of bounding boxes,

(C) a number of positive inversions in the string, and

(D) a number of negative inversions in the string;

(b) means for storing the extracted global features in a storage medium; and

(c) means for calculating the distance between the two handwritten strings based on all of the numbers of points, maximum angles, numbers of positive inversions and numbers of negative inversions extracted by the extracting means.

2. Apparatus according to claim 1, wherein the calculating means include:

(1) means for computing a Levenshtein distance between the two handwritten strings, and

(2) means for multiplying the Levenshtein distance by an adjustment factor that is based on all of the extracted global features to form the distance between the two handwritten strings.

3. Apparatus according to claim 2, wherein the multiplying means include:

(A) means for calculating four values by which the two handwritten strings differ from one another in number of points, maximum angle, number of positive inversions and number of negative inversions, respectively,

(B) means for normalizing the four calculated values, based on all of the numbers of points, maximum angles, numbers of positive inversions and numbers of negative inversions extracted by the extracting means, to form four factors, and

(C) means for multiplying the four factors together to form the adjustment factor.

4. Apparatus according to claim 1, wherein the calculating means include:

means for identifying a maximum number of points among the number of points of each one of the plurality of handwritten strings,

means for identifying a minimum number of points among the number of points of each one of the plurality of handwritten strings,

means for subtracting the minimum number of points from the maximum number of points to form a first point difference value,

means for subtracting the number of points in a first one of the two handwritten strings from the number of points in a second one of the two handwritten strings to form a second point difference value, and

means for dividing the second point difference value by the first point difference value to form a point factor that is used to calculate the distance.

5. Apparatus according to claim 1, wherein the calculating means include:

means for identifying a maximum value of the maximum angle among the maximum angles of each one of the plurality of handwritten strings,

means for identifying a minimum value of the maximum angle among the maximum angles of each one of the plurality of handwritten strings,

means for subtracting the minimum value of the maximum angle from the maximum value of the maximum angle to form a first angle difference value,

means for subtracting the maximum angle in a first one of the two handwritten strings from the maximum angle in a second one of the two handwritten strings to form a second angle difference value, and

means for dividing the second angle difference value by the first angle difference value to form an angle factor that is used to calculate the distance.

6. Apparatus according to claim 1, wherein the calculating means include:

means for identifying a maximum number of positive inversions among the numbers of positive inversions of each one of the plurality of handwritten strings,

means for identifying a minimum number of positive inversions among the numbers of positive inversions of each one of the plurality of handwritten strings,

means for subtracting the minimum number of positive inversions from the maximum number of positive inversions to form a first positive inversion difference value,

means for subtracting the number of positive inversions in a first one of the two handwritten strings from the number of positive inversions in a second one of the two handwritten strings to form a second positive inversion difference value, and

means for dividing the second positive inversion difference value by the first positive inversion difference value to form a positive inversion factor that is used to calculate the distance.

7. Apparatus according to claim 1, wherein the calculating means include:

means for identifying a maximum number of negative inversions among the numbers of negative inversions of each one of the plurality of handwritten strings,

means for identifying a minimum number of negative inversions among the numbers of negative inversions of each one of the plurality of handwritten strings,

means for subtracting the minimum number of negative inversions from the maximum number of negative inversions to form a first negative inversion difference value,

means for subtracting the number of negative inversions in a first one of the two handwritten strings from the number of negative inversions in a second one of the two handwritten strings to form a second negative inversion difference value, and

means for dividing the second negative inversion difference value by the first negative inversion difference value to form a negative inversion factor that is used to calculate the distance.

8. A method for indexing and querying a database having a plurality of electronic handwritten strings, comprising the steps of:

(a) extracting a plurality of global features from each one of the plurality of electronic handwritten strings;

(b) forming a fixed query tree index having a plurality of leaves and a plurality of internal nodes which belong to a plurality of levels, including the steps of;

(1) associating a respectively different single key with each one of the plurality of levels, each key being a handwritten string,

(2) associating each string with one of the plurality of leaves, such that;

(A) each child of each internal node in any one of the plurality of levels between the one leaf and a root node of the index is a root of a respective subtree, and

(B) each string associated with any leaf in the subtree which includes the one leaf is equally distant from the single key associated with the one level, using a distance function based on the global features; and

(c) querying the fixed query tree to search for a first subset of the strings, such that each string in the first subset is within a threshold distance of an input string, according to the distance function used in step (b) (2) (B).

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

(d) applying a plurality of matching criteria to the strings in the first subset to identify one or more strings in the first subset that most closely match the input string.

10. A method according to claim 9, wherein step (d) comprises:

(1) determining a respective global distance between the input string and each of the strings in the first subset, individually, and

(2) forming a second subset of the plurality of strings, the second subset including each of the strings in the first subset for which the global distance is less than a threshold value.

11. A method according to claim 10, wherein step (1) includes, for each one of the input string and the plurality of strings, the steps of:

(A) dividing the one string into a plurality of strokes,

(B) constructing a respective minimum bounding rectangle which completely encloses each one of the strokes, individually,

(C) selecting a tallest one of the minimum bounding rectangles,

(D) calculating an angle alpha for the one string, according to the following equation;

##EQU9## where x₀ is a location of a corner of a first one of the minimum bounding rectangles, h_m is a height of the tallest minimum bounding rectangle, x_m is a location of a corner of the tallest minimum bounding rectangle, and w_m is a width of the tallest minimum bounding rectangle, and

step (2) includes determining the global distance between the input string and each one of the plurality of strings, individually, based on a difference between the angle alpha of the one string and the angle alpha of the input string.

12. A method according to claim 10, wherein step (d) further comprises:

(3) determining a respective first edit distance between the input string and each of the strings in the second subset, individually, and

(4) forming a third subset of the plurality of strings, the third subset including each of the strings in the second subset for which the first edit distance is less than a second threshold value.

13. A method according to claim 12, wherein the first edit distance is determined by a number of insertion and/or deletion operations which transform one of the second subset of the plurality of strings into the input string, and step (d) further comprises:

(5) determining a respective second edit distance between the input string and each of the strings in the third subset, individually, said second edit distance being determined by a number of insertion, deletion, substitution, split and/or merge operations which transform one of the third subset of the plurality of strings into the input string, and

(6) forming a fourth subset of the plurality of strings, the fourth subset including each of the strings in the third subset for which the second edit distance is less than a third threshold value, wherein the strings in the fourth subset are identified as being closest to the input string.

14. A method for indexing a database having a plurality of electronic handwritten strings, comprising the steps of:

(a) performing, for each one of the plurality of electronic handwritten strings, the steps of;

(1) dividing the handwritten string into a plurality of strokes;

(2) identifying a plurality of bounding boxes, each bounding box containing a respectively different one of the plurality of strokes;

(3) extracting a plurality of global features from the string, the plurality of global features including;

(A) a number of points in the string,

(B) a maximum angle between a first one of the points in the string and a corner of a tallest one of the plurality of bounding boxes,

(C) a number of positive inversions in the string, and

(D) a number of negative inversions in the string;

(b) forming a fixed query tree index having a plurality of leaves and a plurality of internal nodes which belong to a plurality of levels, including the steps of;

(1) associating a respectively different key with each one of the plurality of levels, each key being a handwritten string,

(2) calculating a respective distance between one of the plurality of strings and one or more of the keys, based on all of the numbers of points, maximum angles, numbers of positive inversions and numbers of negative inversions extracted in step (a) (3),

(3) associating the one string with one of the plurality of leaves, such that;

(A) each child of each internal node in any one of the plurality of levels between the one leaf and a root node of the index is a root of a respective subtree, and

(B) each string associated with any leaf in the subtree which includes the one leaf is equally distant from the key associated with the one level, using the distances calculated in step (b) (2); and

(4) repeating steps (b) (2) and (b) (3) each time a respectively different one of the plurality of electronic handwritten strings is added to the database.

15. A method according to claim 14, wherein step (b) (2) includes:

(A) computing a Levenshtein distance between the one handwritten string and the one key, and

(B) multiplying the Levenshtein distance by an adjustment factor that is based on all of the global features extracted in step (a) (3), to form the distance between the one handwritten string and the one key.

16. A method according to claim 15, wherein step (b) (2) (B) includes:

(i) calculating four values by which the one handwritten string differ from the key in number of points, maximum angle, number of positive inversions and number of negative inversions, respectively,

(ii) normalizing the four values calculated in step (b) (2) (B) (i), based on all of the numbers of points, maximum angles, numbers of positive inversions and numbers of negative inversions extracted in step (a), to form four factors, and

(iii) multiplying the four factors together to form the adjustment factor.

17. A method according to claim 14, wherein step (b) (3) includes:

(i) selecting the root node of the index,

(ii) identifying the key associated with the selected node,

(iii) computing a distance between the one handwritten string and the identified key,

(iv) selecting the one of the children of the selected node which is the root of a subtree, in which subtree each leaf is associated with a respective one of the plurality of strings that is equal to the one handwritten string in distance from the identified key,

(v) repeating steps (b) (3) (ii) through (b) (3) (iv) until a leaf is selected, and

(vi) associating the one handwritten string with the selected leaf, if a number of handwritten strings associated with the selected leaf is less than a predetermined bucket size.

18. A method according to claim 17, wherein step (b) (3) further includes:

(vi) performing the following steps (I) through (II) if the number of handwritten strings associated with the selected leaf equals the bucket size;

(I) replacing the selected leaf with a new internal node,

(II) establishing at least two new leaves as children of the new internal node,

(III) associating the one handwritten string and each of the plurality of handwritten strings associated with the selected leaf with respective ones of the new leaves.

19. A method according to claim 18, wherein step (b) (3) (vi) further includes:

(IV) associating a new key with a level of the new internal node when step (b) (3) (vi) (I) is executed, if the new internal node is the first internal node in the level of the new internal node.

20. A method according to claim 14, wherein step (b) (2) includes using a measure of distance in accordance with the following inequality:

space="preserve" listing-type="equation">d(K,S2)≦

d(K,S1)+d(S1,S2)

where K is a key, S1 is a first string, S2 is a second string, d(K,S1) is a distance between the key and the first string, d(S1,S2) is a distance between the first string and the second string, and d(K,S2) is a distance between the key and the second string.

21. A method according to claim 20, further comprising the steps of:

(c) providing an input string and a desired maximum distance, D;

(d) selecting the root node of the index;

(e) identifying the key associated with the level of the selected node;

(f) computing a distance, d_i, between the input string and the identified key;

(g) selecting each child of the selected node that is a root of a subtree which complies with the following inequality;

space="preserve" listing-type="equation">d.sub.i -D≦

d≦

d.sub.i +D,

wherein d is the distance between any of the leaves of the subtree and the identified key;

(h) repeating steps (e) through (g), recursively, for each selected node that is an internal node.

22. A method for indexing a database having a plurality of electronic handwritten strings, comprising the steps of:

(a) performing, for each one of the plurality of electronic handwritten strings, the steps of;

(1) dividing the handwritten string into a plurality of strokes;

(2) extracting a plurality of features from each stroke of the string;

(b) forming an R-tree index having a plurality of leaves and a plurality of internal nodes, each one of the plurality of internal nodes having at least one child node, including the steps of;

(1) providing, for each respective one of the child nodes, a pointer to the child node and an identification of a minimum bounding contour associated with the child node, the minimum bounding contour containing a plurality of further minimum bounding contours pointed to by respective ones of a corresponding plurality of entries in the child, if the child node is an internal node, each minimum bounding contour defining a respective range of values within which the value of one of the features of one of the plurality of strokes lies;

(2) storing a plurality of entries in each leaf node, each entry comprising;

(A) a feature vector representing a respective one of the plurality of strokes, and

(B) a pointer which points to the one of the plurality of electronic handwritten strings containing the one stroke, the one electronic handwritten string being a member of the subset,

wherein all the feature vectors stored in any one leaf node differ from one another by less than a threshold distance.

23. A method according to claim 22, further comprising the steps of:

(c) providing an input string which comprises a plurality of input strokes;

(d) forming a range query defined by a plurality of contours, each of the plurality of contours defining a range of values containing a respective one of the input strokes;

(e) identifying one of the plurality of electronic handwritten strings as being found by the range query, such that the one string includes a highest number of strokes for which the respective feature vectors fall within any of the plurality of contours of the range query.

24. A method for indexing a database having a plurality of electronic handwritten strings, comprising the steps of:

(a) performing, for each one of the plurality of electronic handwritten strings, the steps of;

(1) dividing the handwritten string into a plurality of strokes;

(2) extracting a plurality of features from each stroke of the string;

(b) forming an R-tree index having a plurality of leaves and a plurality of internal nodes, each one of the plurality of internal node having at least one child node, including the steps of;

(1) providing, for each respective one of the child nodes, a pointer to the child node and an identification of a minimum bounding contour associated with the child node, the minimum bounding contour containing a plurality of further minimum bounding contours pointed to by respective ones of a corresponding plurality of entries in the child node, if the child node is an internal node,

(2) storing a plurality of entries in each leaf node,

(A) each entry comprising an additional minimum bounding contour which is associated with a respective range of values for each one of the plurality of features,

(B) the additional minimum bounding contour being associated with a plurality of pointers, each pointer pointing to a respective one of the plurality of electronic handwritten strings for which the features of at least one stroke thereof are within the respective range of values of the additional minimum bounding contour,

(C) wherein all the additional minimum bounding contours stored in any one leaf node differ from one another by less than a threshold distance.

25. A method according to claim 24, further comprising the steps of:

(c) providing an input string which comprises a plurality of input strokes;

(d) forming a range query defined by a plurality of contours, each of the plurality of contours defining a range of values containing a respective one of the strokes in the input string;

(e) identifying one of the plurality of electronic handwritten strings as being found by the range query, such that the identified string has a highest number of additional minimum bounding contours which overlap any of the plurality of contours of the range query.

26. A method according to claim 25, wherein step (e) includes:

selecting each of the plurality of electronic handwritten strings which have at least one additional minimum bounding contour overlapping at least one of the plurality of contours of the range query,

determining whether each one of the strokes in each selected string lies within any of the plurality of contours of the range query,

identifying the string that has the highest number of additional minimum bounding contours which overlap any of the plurality of contours of the range query, based only on those strokes which lie within the plurality of contours of the range query.

27. A method for indexing a database having a plurality of electronic handwritten strings, comprising the steps of:

(a) performing, for each one of the plurality of electronic handwritten strings, the steps of;

(1) dividing the handwritten string into a plurality of strokes;

(2) identifying a plurality of bounding boxes, each bounding box containing a respectively different one of the plurality of strokes;

(3) extracting a plurality of global features from the string, the plurality of global features including;

(A) a number of points in the string,

(B) a maximum angle between a first one of the points in the string and a corner of a tallest one of the plurality of bounding boxes,

(C) a number of positive inversions in the string, and

(D) a number of negative inversions in the string;

(b) forming an R-tree index having a plurality of leaves and a plurality of internal nodes,

(1) each internal node having at least one child node, and having, for each respective child node, a pointer to the child node and an identification of a minimum bounding contour associated with the child node, the minimum bounding contour containing a plurality of further minimum bounding contours pointed to by respective ones of a plurality of entries in the child node, if the child node is an internal node,

(2) each one of the leaf nodes having a plurality of pointers, each pointer of a given one of the leaf nodes pointing to a respective one of a subset of the plurality of handwritten strings, for which subset the global features extracted in step (a) (3) differ from one another by less than a threshold value.

28. A method according to claim 27, wherein step (b) includes storing a plurality of entries in each leaf node, each entry comprising:

a global feature vector, and

one of the plurality of pointers, the one pointer pointing to one of the plurality of electronic handwritten strings to which the global feature vector belongs.

29. A method according to claim 28, further comprising the steps of:

(c) providing an input string which has a set of input global feature values;

(d) forming a range query comprising ranges of values containing the input global feature values; and

(e) identifying each string having global features which lie within the ranges of the range query.

30. A method according to claim 29, further comprising the steps of:

(f) computing a respective distance value between each one of the identified strings and the input string; and

(g) determining which of the identified strings most closely matches the input string based on the distance function.