US 5,768,423 AGranted

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

AssigneePanasonic Technologies, Inc.

InventorsWalid Aref, Daniel Barbara

Life of this patent

Estimating the term…

Loading patent…

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.

Claims13

Dependent claims

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.

8 more elements

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

11 more elements

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

11 more elements

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.

11 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/545,242Filed 19 Oct 1995 · continuation in part
Priority: 2 Sep 1994
Granted: 16 Jun 1998
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 16/322
Indexing structures: trees
G06F 18/24323
Relating to the number of classes: tree-organised classifiers
G06F 18/295
Graphical models, e.g. Bayesian networks: markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding…
G06V 30/2276
Using stroke segmentation: with probabilistic networks, e.g. hidden Markov models