Method and apparatus for indexing a plurality of handwritten objects

• US 5,649,023 A
• Filed: 03/27/1995
• Issued: 07/15/1997
• 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: Aref, Walid, Vallabhaneni, Padmavathi, Kamel, Ibrahim, Barbara, Daniel
• Primary Examiner(s): JOHNS, ANDREW W
• Application Number:
  US08/410,812
• Time in Patent Office: 841 Days
• Field of Search: 382/159, 382/160, 382/186, 382/187, 382/226, 382/227, 382/228, 382/229, 395/2.53, 395/2.63, 395/2.65, 395/601, 364/274.3, 364/274.4, 364/283.2, 364/926.8, 364/974.1, 364/974.3
• US Class Current: 382/159
• CPC Class Codes: G06F 16/322 Trees
• 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: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models
• CPC Class Codes: G06V 30/36 Matching; Classification

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 0^th through n^th. Each node in the 0^th level is a leaf. Each node in the 1^th 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 1^th to n^th levels. Each one of the nodes in the 1^th to n^th levels contains the respective HMM associated with the child of the one node. Each HMM in each one of the nodes in the 1^th 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 2^th through n^th 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.

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 0^th through n^th, each node in the 0^th level being a leaf, each node in the 1^th 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 1^th to n^th levels, each one of the nodes in the 1^th to n^th 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 1^th 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 1^th 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.

2. A method according to claim 1, further comprising a step of 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 n^th level

(3) executing, for each level from the n^th level to the 2^th 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 1^th level, if the selected node in the 1^th level has fewer than m children.

3. A method according to claim 2, further comprising the step of retraining the respective HMMs in each node in a path from a root node of the B-tree to the selected node in the 1^th 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.

4. A method according to claim 3, further comprising searching the index, comprising the steps of:

(f) selecting the node in the n^th level;

(g) executing, for each k^th level, for values of k from n to 1, the steps of;

(1) running the respective HMMs of each selected node in k^th level against the sequence of input data,

(2) selecting each one of the nodes in the k-1^th 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.

5. A method according to claim 2, further comprising the step of:

(5) adding a further node in the 1^th level if the selected node in the 1^th level has m children, comprising the steps of;

(a) inserting a node in the 1^th level,

(b) associating half of the HMMs in the selected node in the 1^th level with the inserted node, and

(c) making a parent node of the selected node in the 1^th level a parent of the inserted node, if the parent node has fewer than m children.

6. A method according to claim 5, further comprising the step of retraining the respective HMMs in each node in a path from a root node of the B-tree to the inserted node in the 1^th 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.

7. A method according to claim 6, further comprising the step of retraining the respective HMMs in each node in a further path extending from the root node of the B-tree to the selected node in the 1^th level, so that each HMM associated with any of nodes in the further 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.

8. A method according to claim 5, further comprising the step of:

(6) splitting the parent node of the selected node into two nodes in the 2^th level if the parent node has m children prior to executing step (5)(c),

wherein a first one of the two nodes is the parent of the selected node, and a second one of the two nodes is the parent of the inserted node.

9. A method according to claim 8, further comprising the step of retraining the respective HMMs in each node in a path from a root node of the B-tree to the selected node in the 1^th 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.

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 0^th through n^th, each node in the 0^th level being a leaf, each node in the 1^th 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 1^th to n^th levels, each one of the nodes in the 1^th to n^th 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 1^th 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 2^th through n^th 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 n^th level;

(g) executing, for each k^th level, for values of k from n to 1, the steps of;

(1) running the respective HMM of each selected node in k^th level against the sequence of input data,

(2) selecting each one of the nodes in the k-1^th 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 0^th through n^th, each node in the 0^th level being a leaf, each node in the 1^th 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 1^th level with the first leaf;

(d) training the HMMs in the 1^th and 2^th 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 n^th level;

(3) executing, for each level from the n^th level to the 2^th 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 1^th level, if the selected node in the 1^th level has fewer than m children;

(5) adding a further node in the 1^th level if the selected node in the 1^th level has m children, comprising the steps of;

(a) inserting a node in the 1^th level,

(b) associating half of the HMMs in the selected node in the 1^th level with the inserted node, and

(c) making a parent node of the selected node in the 1^th 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 0^th through n^th, each node in the 0^th level being a leaf, each node in the 1^th 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 1^th to n^th levels, each one of the nodes in the 1^th to n^th 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 1^th 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 2^th through n^th 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.