Trie based method for indexing handwritten databases

• US 5,528,701 A
• Filed: 09/02/1994
• Issued: 06/18/1996
• Est. Priority Date: 09/02/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 G.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US08/300,795
• Time in Patent Office: 655 Days
• Field of Search: 382/186, 382/187, 382/226, 382/227, 382/228, 382/229, 382/173, 382/177, 382/179, 395/600, 395/2.52, 395/2.63, 395/2.65, 364/274.3, 364/274.4, 364/283.2, 364/926.8, 364/974.1, 364/974.3, 381/43
• US Class Current: 382/178
• 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 is disclosed for matching input data representing a continuous combination of input objects to a plurality of objects in a trie database structure. This data structure has a plurality of nodes partitioned into a plurality of levels. Each node in the Trie includes a plurality of elements where each element corresponds to a respective one of the component objects. In addition, a hidden Markov model corresponding to the component object is associated with the element in the database. According to the method, the input object is applied to each of the hidden Markov models associated with the respective plurality of elements of a node to generate a respective plurality of acceptance values. The element which generates the largest acceptance value is identified with a segment of the input data. The component object for this element is recorded and the identified segment is deleted from the input data string. These steps are repeated at successive levels of the Trie data structure until each segment of the input data has been identified with an element of a node of the Trie data structure. The input data is matched with the objects stored in the database by concatenating the component objects associated with the respective identified elements.

Claims

1. A method for matching an input sequence of continuously connected handwritten objects to one of a plurality of objects which are modeled by concatenating members of a set of component objects, the method comprising the steps of:

(a) generating a Trie data structure representing the plurality of objects, the Trie data structure having a plurality of nodes divided into a plurality of levels, wherein each node includes a plurality of elements, including the steps of;

assigning component objects of each of the plurality of objects to respective elements of respective nodes of the Trie data structure,

associating identifying characteristics of the respective component objects with each element in each node of the Trie data structure, wherein the identifying characteristics are numbers of local minima, local maxima and inflection points in each of the component objects, and

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

(b) selecting a node of the Trie data structure;

(c) applying the input sequence of continuously connected handwritten objects to each of the hidden Markov models associated with the respective plurality of elements of the selected node to generate a respective plurality of acceptance values;

(d) identifying a segment of the input sequence with the element of the selected node that generates the acceptance value which is larger than any other one of the acceptance values, based on the identifying characteristics associated with the element, without interference from a portion of the input sequence that does not correspond to the component object assigned to the element; and

(e) deleting the identified segment from the input sequence of continuously connected handwritten objects.

2. A method according to claim 1, further including the steps of:

(f) repeating steps (b) through (e) at successive levels of the Trie data structure until each segment of the input sequence has been identified with an element of a node of the Trie data structure; and

(g) concatenating the component objects that are associated with the respective identified elements to identify one of the objects in the Trie data structure which matches the input sequence.

3. A method according to claim 1, wherein the step of associating a respective hidden Markov model with each element of each node includes the step of generating the hidden Markov model for the respective component object, the generated hidden Markov model being a left to right structure having a final state and the final state has a probability of one associated with remaining in the final state.

4. A method according to claim 1, wherein the component objects are handwritten letters.

5. A method for matching an input sequence of continuously connected handwritten objects representing a plurality of handwritten letters to one of a plurality of words which are modeled by concatenating letters, the method comprising the steps of:

(a) generating a Trie data structure representing the plurality of words, the Trie data structure having a plurality of nodes divided into a plurality of levels, wherein each node includes a plurality of elements, including the steps of;

assigning respective letters of each of the words to each of the respective elements of respective nodes of the Trie data structure,

associating identifying characteristics of the respective letters with each element in each node of the Trie data structure, wherein the identifying characteristics are numbers of local minima, local maxima and inflection points in each of the letters, and

associating a respective hidden Markov model with each element of each node, the hidden Markov model representing the respective letter of the element;

(b) selecting a node of the Trie data structure;

(c) applying the input sequence of continuously connected handwritten objects to each of the hidden Markov models associated with the respective plurality of elements of the selected node to generate a respective plurality of acceptance values;

(d) identifying a segment of the input sequence with the element of the selected node that generates the acceptance value which is larger than any other one of the acceptance values, based on the identifying characteristics associated with the element, without interference from a portion of the input sequence adjacent to the segment, wherein the segment of the input sequence forms a single letter or a portion of a single letter and said portion represents a connecting stroke adjacent to the letters; and

(e) deleting the identified segment from the input sequence.

6. A method according to claim 5, further including the steps of:

(f) repeating steps (b) through (e) at successive levels of the Trie data structure until each segment of the input sequence has been identified with an element of a node of the Trie data structure; and

(g) concatenating the letters that are associated with the respective identified elements to identify one of the words in the Trie data structure which matches the input sequence.

7. A method of segmenting a continuous data stream representing a first object and a second object, where the first object and second object are modeled by respective first and second hidden Markov models, each having a plurality of states, the method comprising the steps of:

concatenating the first and second hidden Markov models to generate a combined hidden Markov model of the continuous data stream;

identifying a first transition state of the combined hidden Markov model as representing a last state of the first hidden Markov model;

identifying a second transition state of the combined hidden Markov model as representing a first state of the second hidden Markov model;

applying the continuous data stream to the combined hidden Markov model to generate a state transition matrix;

identifying, from the state transition matrix, a most probable state sequence which represents the continuous data stream, including the steps of;

comparing each target state in the most probable state sequence with the second transition state to determine equality;

if the target state equals the second transition state, comparing the state preceding the target state in the most probable state sequence to the first transition state;

if the state preceding the target state is found to be equal to the first transition state, identifying a portion of the continuous data stream which corresponds to the target state as a segment boundary in the continuous data stream.

8. A method according to claim 7, wherein the first object and the second object are handwritten letters.

9. A method according to claim 7, wherein the method further comprises, before the step of concatenating, the step of:

generating a Trie data structure representing a plurality of object sequences, the Trie data structure having a plurality of nodes divided into a plurality of levels, wherein each node includes a plurality of elements, including the steps of;

assigning objects within each of the plurality of object sequences to respective elements of respective nodes of the Trie data structure; and

associating a respective hidden Markov model with each element of each node, the hidden Markov model representing the respective object of the element,

wherein the first and second hidden Markov models are associated with elements of respective first and second nodes within the Trie data structure, said second node being a child of the first node.