Method and apparatus for indexing a plurality of handwritten objects
First Claim
1. A method for indexing a plurality of handwritten objects in a database, the method comprising the steps of:
- (a) generating a B-tree data structure of order m, where m is an integer, the B-tree having a plurality of nodes divided into a plurality of levels ordinally numbered 0th through nth, each node in the 0th level being a leaf, each node in the 1th level having at least m/2 leaves as children;
(b) assigning each one of the handwritten objects to a respective leaf;
(c) associating a respectively different hidden Markov model (HMM) with each respective child of each of the nodes in the 1th to nth levels, each one of the nodes in the 1th to nth levels containing the respective HMMs associated with the children of the one node;
(d) training each HMM in each one of the nodes in the 1th level to accept the handwritten object assigned to the leaf that is the child with which the HMM is associated; and
(e) training the respective HMMs in each node in a path from a root node of the B-tree to one of the nodes in the 1th level, so that each HMM associated with any of nodes in the path accepts all of the handwritten objects in the leaves of a subtree that has as a root the respective child with which the HMM is associated, wherein step (e) is executed each time an object is added to the database.
3 Assignments
0 Petitions
Accused Products
Abstract
A method for indexing a plurality of handwritten objects is provided. A B-tree data structure of order m is generated, where m is an integer. The B-tree has a plurality of nodes divided into a plurality of levels ordinally numbered 0th through nth. Each node in the 0th level is a leaf. Each node in the 1th level has at least m/2 leaves as children. Each one of the handwritten objects is assigned to a respective leaf. A respectively different hidden Markov model (HMM) is associated with each respective child of each of the nodes in the 1th to nth levels. Each one of the nodes in the 1th to nth levels contains the respective HMM associated with the child of the one node. Each HMM in each one of the nodes in the 1th level is trained to accept the handwritten object of the respective leaf that is a child of the one node. Each HMM associated with any of the nodes in the 2th through nth levels is trained to accept all of the handwritten objects in the leaves of a subtree that has as a root the respective child with which the HMM is associated.
-
Citations
12 Claims
-
1. A method for indexing a plurality of handwritten objects in a database, the method comprising the steps of:
-
(a) generating a B-tree data structure of order m, where m is an integer, the B-tree having a plurality of nodes divided into a plurality of levels ordinally numbered 0th through nth, each node in the 0th level being a leaf, each node in the 1th level having at least m/2 leaves as children; (b) assigning each one of the handwritten objects to a respective leaf; (c) associating a respectively different hidden Markov model (HMM) with each respective child of each of the nodes in the 1th to nth levels, each one of the nodes in the 1th to nth levels containing the respective HMMs associated with the children of the one node; (d) training each HMM in each one of the nodes in the 1th level to accept the handwritten object assigned to the leaf that is the child with which the HMM is associated; and (e) training the respective HMMs in each node in a path from a root node of the B-tree to one of the nodes in the 1th level, so that each HMM associated with any of nodes in the path accepts all of the handwritten objects in the leaves of a subtree that has as a root the respective child with which the HMM is associated, wherein step (e) is executed each time an object is added to the database. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for matching a sequence of input data to one of a plurality of handwritten objects, the method comprising the steps of:
-
(a) generating a B-tree data structure of order m, having a plurality of nodes divided into a plurality of levels ordinally numbered 0th through nth, each node in the 0th level being a leaf, each node in the 1th level having at least m/2 leaves as children; (b) assigning each one of the handwritten objects to a respective leaf; (c) associating a respectively different hidden Markov model (HMM) with each child of each one of the nodes in the 1th to nth levels, each one of the nodes in the 1th to nth levels containing the respective HMMs associated with the children of the one node; (d) training the HMMs contained in each one of the nodes in the 1th level to accept the handwritten objects of the respective leaves that are children of the one node; (e) training each HMM contained in any of nodes in the 2th through nth levels to accept all of the handwritten objects in the leaves of a subtree that has as a root the respective child with which the HMM is associated; (f) selecting the node in the nth level; (g) executing, for each kth level, for values of k from n to 1, the steps of; (1) running the respective HMM of each selected node in kth level against the sequence of input data, (2) selecting each one of the nodes in the k-1th level for which the associated HMM has an output probability greater than a threshold value, and (h) identifying the handwritten object in at least one of the leaves as matching the sequence of input data if the leaf is selected.
-
-
11. A method for indexing a plurality of handwritten objects, comprising the steps of:
-
(a) generating a B-tree data structure of order m, having a plurality of nodes divided into a plurality of levels ordinally numbered 0th through nth, each node in the 0th level being a leaf, each node in the 1th level having a respective leaf as a child; (b) assigning one of the handwritten objects to a first one of the leaves; (c) associating a hidden Markov model (HMM) in the 1th level with the first leaf; (d) training the HMMs in the 1th and 2th levels to accept the handwritten object of the first leaf; (e) adding a further handwritten object to the B-tree, including the steps of; (1) training a further HMM to accept the further handwritten object; (2) selecting the node in the nth level; (3) executing, for each level from the nth level to the 2th level, the steps of; (a) running each HMM in the selected node against the further handwritten object, (b) identifying the HMM that outputs a highest probability value during execution of step (3)a, (c) selecting the node that is a child of the identified HMM; and (4) inserting the further HMM in the selected node in the 1th level, if the selected node in the 1th level has fewer than m children; (5) adding a further node in the 1th level if the selected node in the 1th level has m children, comprising the steps of; (a) inserting a node in the 1th level, (b) associating half of the HMMs in the selected node in the 1th level with the inserted node, and (c) making a parent node of the selected node in the 1th level a parent of the inserted node.
-
-
12. Apparatus for indexing a plurality of handwritten objects in a database, comprising:
-
means for monitoring movement of a stylus that forms a handwritten pattern, and for generating therefrom a plurality of symbols which form the handwritten objects; means for storing a B-tree data structure of order m, where m is an integer, the B-tree having a plurality of nodes divided into a plurality of levels ordinally numbered 0th through nth, each node in the 0th level being a leaf, each node in the 1th level having at least m/2 leaves as children; means for assigning each one of the handwritten objects to a respective leaf; means for associating a respectively different hidden Markov model (HMM) with each respective child of each of the nodes in the 1th to nth levels, each one of the nodes in the 1th to nth levels containing the respective HMMs associated with the children of the one node; means for training each HMM in each one of the nodes in the 1th level to accept the handwritten object assigned to the leaf that is the child with which the HMM is associated; and means for training each HMM associated with any of the nodes in the 2th through nth levels to accept all of the handwritten objects in the leaves of a subtree that has as a root the respective child with which the HMM is associated.
-
Specification