Method and apparatus for similarity matching of handwritten data objects

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).

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.

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.

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.

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.