Trie structure based method and apparatus for indexing and searching handwritten databases with dynamic search sequencing

• US 5,768,423 A
• Filed: 10/19/1995
• Issued: 06/16/1998
• Est. Priority Date: 09/02/1994
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Corporation Of America (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Technologies, Inc. (Panasonic Holdings Corporation)
• Inventors: Aref, Walid, Barbara, Daniel
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): Davis, Monica S.
• Application Number:
  US08/545,242
• Time in Patent Office: 971 Days
• Field of Search: 382/186, 382/187, 382/226, 382/178, 382/228, 382/224, 382/227, 382/229
• US Class Current: 382/228
• 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: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models

Abstract

A method of searching for one of a plurality of objects that matches an input sequence of handwritten objects is provided. The objects are modeled by concatenating members of a set of component objects. A Trie structure representing the plurality of objects is generated. Component objects of each object are assigned to the elements of respective nodes of the Trie structure. A respective hidden Markov model (HMM) is associated with each element of each non-leaf node. The HMMs represent the respective component object of the element. A maximum probability of any HMM accepting any of the set of component objects is estimated. The root node of the Trie structure is selected. A plurality of elements of the selected node are selected. A plurality of segments of the input sequence are applied to respective HMMs associated with the selected elements to generate respective acceptance values.

Claims

1. A method of searching for one of a plurality of objects that matches an input sequence of handwritten objects, the objects being modeled by concatenating members of a set of component objects, the method comprising the steps of:

(a) generating a Trie structure representing the plurality of objects, the Trie structure having a plurality of non-leaf nodes, wherein each non-leaf node includes at least one element, each element having a child node associated therewith, including the steps of;

assigning component objects of each of the plurality of objects to the respective elements of respective nodes of the Trie structure; and

associating a respective hidden Markov model (HMM) with each element of each non-leaf node, the HMM representing the respective component object of the element;

(b) estimating a maximum probability of any of the HMMs accepting any of the set of component objects;

(c) selecting a root node of the Trie structure;

(d) selecting a plurality of the elements of the selected node;

(e) applying a plurality of segments of the input sequence to respective HMMs associated with the selected elements to generate respective acceptance values;

(f) calculating, for each one of the selected elements, a respective estimated probability that the input sequence matches any of the plurality of objects represented by respective paths in the Trie structure that pass through the child node associated with the one selected element, as a function of the estimated maximum probability and the respective acceptance value of the one element; and

(g) searching next for said one of the plurality of objects that matches the input sequence within a subtree which has as a root the child node associated with the one of the selected elements for which the respective estimated probability is greatest.

2. A method according to claim 1, wherein step (g) includes the steps of:

(1) selecting each element of the child node associated with the one of the selected elements for which the respective estimated probability is greatest, and

(2) executing steps (d) through (g), recursively for each selected node.

3. A method according to claim 1, further comprising the step of:

establishing a data structure which includes a plurality of entries, each entry being associated with a respectively different element of at least one of the nodes in the Trie structure,

wherein step (d) includes the step of selecting the plurality of elements from among the elements with which the entries in the data structure are associated.

4. A method according to claim 3, wherein the data structure only includes entries associated with elements for which the respective HMMs associated therewith have not yet been executed during the search.

5. A method according to claim 3, wherein step (g) includes the steps of:

(1) selecting each element of said child node associated with the one of the selected elements for which the respective estimated probability determined in step (f) is greatest,

(2) adding a set of entries to the data structure, each added entry being associated with a respectively different element of said child node,

(3) executing the respective HMM associated with each element of said child node, to generate a respective acceptance value for each element of the child node,

(4) deleting from the data structure the entry which is associated with the element with which said child node is associated,

(5) executing steps (d) through (g), recursively.

6. A method according to claim 5, further comprising the step of discontinuing executing steps (d) through (g) when a predetermined number of HMMs have been executed during the search.

7. A method according to claim 1, wherein the Trie structure has N levels, ordinally numbered 0 through N-l, and step (f) includes, for each selected element:

calculating the estimated probability associated with the selected element, according to the equation;

##EQU5## wherein P is the estimated probability, i is an index, L is the level of the node having the selected element, A_i is the acceptance value associated with the element in level i within the respective path through the node having the selected element, and M is the estimated maximum probability of any of the HMMs accepting any of the set of component objects.

8. A method according to claim 1, further comprising:

establishing a data structure which includes a plurality of entries associated with each respective one of a subset of the plurality of elements of at least one of the nodes in the Trie structure, each entry identifying;

(1) a respective type of error condition that could result in the input sequence occurring, and

(2) information identifying an estimated probability that the input sequence matches any of the plurality of objects represented by respective paths in the Trie structure that pass through the child associated with the element with which the entry is associated, if the identified type of error condition is present,

wherein step (d) includes selecting the plurality of elements from among the elements with which the entries in the data structure are associated.

9. A method according to claim 8, wherein the types of error conditions include error free matches, insertion errors, deletion errors and substitution errors.

10. A method of searching for one of a plurality of objects that matches an input sequence of handwritten objects, the objects being modeled by concatenating members of a set of component objects, the method comprising the steps of:

(a) generating a Trie structure representing the plurality of objects, the Trie structure having a plurality of non-leaf nodes, wherein each non-leaf node includes at least one element, each element having a child node associated therewith, including the steps of;

assigning component objects of each of the plurality of objects to the respective elements of respective nodes of the Trie structure; and

associating a respective hidden Markov model (HMM) with each element of each non-leaf node, the HMM representing the respective component object of the element;

(b) estimating a maximum probability of any of the HMMs accepting any of the set of component objects;

(c) selecting a root node of a subtree in the Trie structure that is to be searched;

(d) selecting a plurality of the elements of the selected node;

(e) applying a plurality of segments of the input sequence to respective HMMs associated with the selected elements to generate respective acceptance values;

(f) calculating, for each one of the selected elements, a respective estimated probability that the input sequence matches any of the plurality of objects represented by respective paths in the Trie structure that pass through the child node associated with the one selected element, as a function of the estimated maximum probability and the respective acceptance value of the one element; and

(g) searching next for said one of the plurality of objects that matches the input sequence within a subtree which has as a root the child node associated with the one of the selected elements for which the respective estimated probability is greatest.

11. A method of searching for one of a plurality of objects that matches an input sequence of handwritten objects, the objects being modeled by concatenating members of a set of component objects, the method comprising the steps of:

(a) generating a Trie structure representing the plurality of objects, the Trie structure having a plurality of nodes, wherein each node includes at least one element, each element being associated with a respective child node, including the steps of;

assigning component objects of each of the plurality of objects to respective elements of respective nodes of the Trie structure; and

associating a respective hidden Markov model (HMM) with each element of each node, the HMM representing the respective component object of the element;

(b) establishing a data structure which includes a plurality of entries, each entry identifying a respectively different child of a root node of the Trie structure;

(c) estimating a maximum probability of any of the HMMs accepting any of the set of component objects;

(d) selecting a node which is the root node of the Trie structure;

(e) selecting each element of the selected node;

(f) applying respective segments of the input sequence to the respective HMMs associated with each selected element to generate respective acceptance values;

(g) estimating, for each selected element, a respective value of the estimated probability that the input sequence matches any of the plurality of objects represented by respective paths in the Trie structure that pass through the respective child associated with that element, as a function of the estimated maximum probability and the respective acceptance value of the selected element;

(h) selecting the node having the element for which the respective value of the estimated probability is greatest;

(i) adding a set of entries to the data structure, each added entry in the set identifying a respectively different child of the selected node;

(j) deleting the entry which identifies the selected node;

(k) repeating steps (e) through (j).

12. A method of searching for one of a plurality of objects that matches an input sequence of handwritten objects, the objects being modeled by concatenating members of a set of component objects, the method comprising the steps of:

(a) generating a Trie structure representing the plurality of objects, the Trie structure having a plurality of nodes, wherein each node includes at least one element, including the steps of;

assigning component objects of each of the plurality of objects to respective elements of respective nodes of the Trie structure; and

associating a respective hidden Markov model (HMM) with each element of each node, the HMM representing the respective component object of the element;

(b) establishing a data structure which includes a plurality of entries, each entry identifying a respectively different child of at least one of the nodes in the Trie structure;

(c) estimating a maximum probability of any of the HMMs accepting any of the set of component objects;

(d) selecting a first node of the Trie structure identified in one of the plurality of entries;

(e) selecting a second node of the Trie structure identified in a further one of the plurality of entries, such that the first node does not lie between a root of the Trie structure and the second node, and the second node does not lie between the root of the Trie structure and the first node;

(f) applying first and second segments of the input sequence to respective HMMs associated with elements of the first and second nodes to generate respective first and second acceptance values;

(g) determining, for each respective child of each of the first and second nodes, a respective value of the estimated probability that the input sequence matches any of the plurality of objects represented by respective paths in the Trie structure that pass through the respective child, based on the respective first and second acceptance values and the estimated maximum probability;

(h) selecting the child for which the respective value of the estimated probability is greatest as the first node;

(i) adding a set of entries to the data structure, each added entry in the set identifying a respectively different child of the selected child;

(j) deleting the entry which identifies the selected child;

(k) repeating steps (e) through (j).

13. Apparatus for searching for one of a plurality of objects that matches an input sequence of handwritten objects, the objects being modeled by concatenating members of a set of component objects, comprising:

memory means including a Trie structure representing the plurality of objects, the Trie structure having a plurality of nodes, wherein each node includes at least one element, each element being associated with a respective child node,

a plurality of component objects of each of the plurality of objects being assigned to respective elements of respective nodes of the Trie structure, and

a respective hidden Markov model (HMM) being associated with each element of each node, the HMM representing the respective component object of the element;

said memory means including a data structure which has a plurality of entries, each entry identifying a respectively different child of a root node of the Trie structure;

means for estimating a maximum probability of any of the HMMs accepting any of the set of component objects;

root selecting means for selecting a node which is the root node of the Trie structure;

means for selecting each element of the selected node;

means for applying respective segments of the input sequence to the respective HMMs associated with each selected element to generate respective acceptance values;

means for estimating, for each selected element, a respective value of the estimated probability that the input sequence matches any of the plurality of objects represented by respective paths in the Trie structure that pass through the respective child associated with that element, as a function of the estimated maximum probability and the respective acceptance value of the selected element;

means for selecting the node having the element for which the respective value of the estimated probability is greatest;

means for adding a set of entries to the data structure, each added entry in the set identifying a respectively different child of the selected node; and

means for deleting the entry which identifies the selected node,

wherein the element selecting means, the input sequence applying means, the estimating means, and the node selecting means operate on the node selected by the selecting means.