Method and apparatus for DP matching using multiple templates

• US 5,067,166 A
• Filed: 03/23/1990
• Issued: 11/19/1991
• Est. Priority Date: 03/24/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ito, Nobuyasu
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US07/498,310
• Time in Patent Office: 606 Days
• Field of Search: 381/41, 381/42, 381/43, 382/30, 382/34, 382/37, 382/38, 364/513.5
• US Class Current: 382/215
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

A pattern recognition method and apparatus using dynamic programming in which an input sequence of labels is matched to a set of candidate templates (candidate reference label sequences). The set of candidate reference label sequences is grouped into subsets, where each reference label sequence in a subset has a common root reference label subsequence. Using this set organization, a depth-first search is performed to identify a local optimum template and its local optimum match score with the input sequence of labels. Using the local optimum match score as a threshold, the input sequence of labels is matched to root reference label subsequences, eliminating those root reference label subsequences having match scores above the threshold. Surviving root reference label subsequences having match scores below the threshold remain recognition candidates, and are further investigated.

Claims

1. A method for DP matching multiple label-sequences which form templates comprising the steps of:

(a) generating from said multiple label-sequences a tree-structured dictionary having a root node, a plurality of intermediate nodes, a plurality of end nodes, and a plurality of paths from the root node through intermediate nodes to end nodes, each intermediate and each end node having only one incoming path segment from the root node to the intermediate node, each intermediate node having one ancestor node adjacent to the intermediate node along the incoming path segment into the intermediate node, each intermediate node having at least one outgoing path segment from the intermediate node to an end node, each intermediate node having one or more descendent nodes adjacent to the intermediate node along the outgoing path segments from the intermediate node, where each node corresponds to one label, and storing it in a storage device,

(b) providing such label node in said tree-structured dictionary with a buffer area in said storage device,

(b1) selecting an ancestor node in said tree-structured dictionary, said selected ancestor node having at least two descendent nodes,

(c) selecting one descendent node of the two or more descendent nodes of the selected ancestor node, performing a stage calculation between the label corresponding to the selected descendent node and an input label sequence and storing the result in the buffer provided for the selected descendent node, the step (c) comprising the sub-steps of;

(c1) referring to the stage calculation result stored in the buffer for the selected ancestor node,

(c2) determining a label in the input label sequence providing the minimum value of the stage calculation result obtained in said sub-step (c1) and

(c3) selecting a descendent node of the selected ancestor node, which descendent node corresponds to a label having the minimum distance from a label immediately after the label determined in the sub-step (c2) in the input label sequence, and

(d1) if the selected descendent node is not an end node, then replacing the selected ancestor node with the selected descendent node, and repeating step (c), and

(d2) after performing the stage calculation for the node which corresponds to the end of one template, storing the stage calculation result obtained for the end node with the identification data of the template as solution candidate information into said storage device.

2. A method according to claim 1 wherein the step (c) further comprises the steps of predicting the minimum value obtainable as a distance between a template which includes the label corresponding to the selected node and the input label sequence based on the minimum value of the calculation result obtained by performing the sub-step (c1),

comparing the predicted value with the distance stored as solution candidate information and judging whether the sub-steps (c2) and (c3) should be performed or not from the comparison result.

3. A method according to claim 2 wherein the step (d) further comprises the steps of comparing a distance D'"'"' obtained for the template including the end node with a distance D stored as the solution candidate information each time the stage calculation is performed for the node which corresponds to the end of one template and judging whether the solution candidate information should be updated or not from the comparison result.

4. A method for DP matching for using multiple label-sequences which form templates comprising the steps of:

(a) generating from said multiple label-sequences a tree-structured dictionary having a root node, a plurality of intermediate nodes, a plurality of end nodes, and a plurality of paths from the root node through intermediate nodes to end nodes, each intermediate and each end node having only one incoming path segment from the root node to the intermediate node, each intermediate node having one ancestor node adjacent to the intermediate node along the incoming path segment into the intermediate node, each intermediate node having at least one outgoing path segment from the intermediate node to an end node, each intermediate node having one or more descendent nodes adjacent to the intermediate node along the outgoing path segments from the intermediate node, where each node corresponds to one label and storing it in a storage device,

(b) providing each label node in said tree-structured dictionary with a buffer area in said storage device,

(b1) selecting an ancestor node in said tree-structured dictionary, said selected ancestor node having at least two descendent nodes,

(c) selecting one descendent node of the two or more descendent nodes of the selected ancestor node, performing a stage calculation between the label corresponding to the selected descendent node and an input label sequence and storing the result in the buffer provided for the selected descendent node, the step (c) comprising the sub-steps of;

(c1) referring to the stage calculation result stored in the buffer for the selected ancestor node,

(c2) determining an optimum node to be selected for the next stage calculation from a predetermined range of descendent nodes of the selected ancestor node by referring to the stage calculation result stored in the buffer of a predetermined range of nodes which include said selected node at least and selecting the determined node as a node for the next stage calculation and

(d1) if the selected descendent node is not an end node, then replacing the selected ancestor node with the selected descendent node, and repeating step (c), and

(d2) after performing the stage calculation for the node which corresponds to the end of one template, storing the stage calculation result obtained for the end node with the identification data of the template as solution candidate information into said storage device.

5. A method according to claim 4 wherein the step (c) further comprises the steps of predicting the minimum value obtainable as a distance between a template which includes the label corresponding to the selected node and the input label sequence based on the minimum value of the calculation result obtained by performing the sub-step (c1), comparing the predicted value with the distance stored as the solution candidate information, and judging whether the sub-step (c2) should be performed or not from the comparison result.

6. A method according to claim 5 wherein the step (d) further comprises the steps of comparing a distance D'"'"' obtained for the template including the end node with a distance D stored as the solution candidate information each time the stage calculation is performed for the node which corresponds to the end of one template and judging whether the solution candidate information should be updated or not from the comparison result.

7. An apparatus for DP matching between an input label sequence and multiple label-sequences which form templates comprising:

(a) a storage device,

(b) means for receiving the multiple label-sequences, forming a tree-structured dictionary having a root node, a plurality of intermediate nodes, a plurality of end nodes, and a plurality of paths from the root node through intermediate nodes to end nodes, each intermediate and each end node having only one incoming path segment from the root node to the intermediate node, each intermediate node having one ancestor node adjacent to the intermediate node along the incoming path segment into the intermediate node, each intermediate node having at least one outgoing path segment from the intermediate node to an end node, each intermediate node having one or more descendent nodes adjacent to the intermediate node along the outgoing path segments from the intermediate node, where each node corresponds to one label, storing it in said storage device and providing each label node in the tree-structure dictionary with a buffer area in said storage device,

(b1) means for selecting an ancestor node in said tree-structured dictionary, said selected ancestor node having at least two descendent nodes,

(c) means for selecting one descendent node of the two or more descendent nodes of the selected ancestor node, performing a stage calculation between the label corresponding to the selected descendent node and an input label sequence and storing the result in the buffer provided for the selected descendent node, said operations including;

(c1) referring to the stage calculation result stored in the buffer for the selected ancestor node,

(c2) determination of a label in the input label sequence providing the minimum value of the stage calculation result obtained by said operation (c1), and

(c3) selection of a descendent node of the selected ancestor node, which descendent node corresponds to a label having the minimum distance from the label immediately after the label determined in the step (c2) in the input label sequence, and

(d1) means for replacing, if the selected descendent node is not an end node, the selected ancestor node with the selected descendent node, and repeating step (c), and

(d2) means for storing, after the performance of the stage calculation for the node which corresponds to the end of one template, the stage calculation result obtained for the end node with the identification data of the template as solution candidate information into said storage device.

8. An apparatus according to claim 7 wherein said means (c) predicts a minimum value obtainable as a distance between a template which includes the label corresponding to the selected node and the input label sequence based on the minimum value of the calculation result obtained by performing the operation (c1), compares said predicted value with the distance stored as the solution candidate information and judges whether the operations (c2) and (c3) should be performed or not from the comparison result.

9. An apparatus according to claim 8 wherein said means (d) compares a distance D'"'"' obtained for the template including the end node with a distance D stored as solution candidate information each time the stage calculation is performed for the node which corresponds to the end of one template and judges whether the solution candidate information should be updated or not from the comparison result.

10. An apparatus for DP matching between an input label sequence and multiple label-sequences which form templates comprising:

(a) a storage device,

(b) means for receiving the multiple label-sequences, forming a tree-structured dictionary having a root node, a plurality of intermediate nodes, a plurality of end nodes, and a plurality of paths from the root node through intermediate nodes to end nodes, each intermediate and each end node having only one incoming path segment from the root node to the intermediate node, each intermediate node having one ancestor node adjacent to the intermediate node along the incoming path segment into the intermediate node, each intermediate node having at least one outgoing path segment from the intermediate node to an end node, each intermediate node having one or more descendent nodes adjacent to the intermediate node along the outgoing path segments from the intermediate node, where each node corresponds to one label, storing it in said storage device and providing each label node in the tree-structured dictionary with a buffer area in said storage device,

(b1) means for selecting an ancestor node in said tree-structured dictionary, said selected ancestor node having at least two descendent nodes,

(c) means for selecting one descendent node of the two or more descendent nodes of the selected ancestor node, performing a stage calculation between the label corresponding to the selected descendent node and an input label sequence, storing the result in a buffer provided for the selected descendent node, said operations including;

(c1) referring to the stage calculation result stored in the buffer for the selected ancestor node,

(c2) determination of an optimum node to be selected for a next stage calculation from labels of a predetermined range of descendant nodes of the selected ancestor node by referring to the stage calculation result stored in the buffer of a predetermined range of nodes which include the selected node at least and selection of the determined node as a node for the next stage calculation and

(d1) means for replacing, if the selected descendent node is not an end node, the selected ancestor node with the selected descendent node, and repeating step (c), and

(d2) means for storing, after the performance of the stage calculation for the node which corresponds to the end of one template, the stage calculation result obtained for the end node with the identification data of the template as solution candidate information into said storage device.

11. An apparatus according to claim 10 wherein said means (c) predicts a minimum value obtainable as a distance between a template which includes the label corresponding to the selected node and the input label sequence based on the minimum value of the calculation result obtained by the operation (c1), compares the predicted value with the distance stored as the solution candidate information and judges whether the operation (c2) should be performed or not from the comparison result.

12. An apparatus according to claim 11 wherein said means (d) compares a distance D'"'"' obtained for the template including the end node with a distance D stored as the solution candidate information each time the stage calculation is performed for the node which corresponds to the end of one template and judges whether the solution candidate information should be updated or not from the comparison result.

13. A pattern recognition method comprising the steps of:

generating a sequence of feature label signals, each feature label signal having a value representing the value of at least one feature of an observed information signal;

storing a candidate set of template signals, each template signal having a value representing a template sequence of reference labels, each reference label having a value;

partitioning the candidate set of template signals into at least first and second subsets of one or more template signals, each template signal in the first subset having a value representing a sequence of reference labels beginning with a first subsequence of one or more reference labels, each template signal in the second subset having a value representing a sequence of reference labels beginning with a second subsequence of one or more reference labels different from the first subsequence of reference labels;

matching the values of the sequence of feature labels against the values of the reference labels in the first subsequence to produce a first match score signal having a match score value representing the similarity of the sequence of feature labels to the reference labels in the first subsequence;

matching the values of the sequence of feature labels against the values of the reference labels in the second subsequence to produce a second match score signal having a match score value representing the similarity of the sequence of feature labels to the reference labels in the second subsequence;

selecting as a local optimum subset of template signals the first subset of template signals if the first match score is better than the second match score, or the second subset of template signals if the second match score is better than the first match score;

finding, from the template signals in the local optimum subset, the local optimum template signal whose value is best matched to the values of the sequence of feature labels to produce a local optimum match score signal having a local optimum match score value representing the similarity of the sequence of feature labels to reference labels represented by the local optimum template;

defining a remainder set of template signals containing template signals which are not in the local optimum subset of templates;

partitioning the remainder set of template signals into at least first and second remainder subsets of one or more template signals, each template signal in the first remainder subset having a value representing a sequence of reference labels beginning with a first remainder subsequence of one or more reference labels, each template signal in the second remainder subset having a value representing a sequence of reference labels beginning with a second remainder subsequence of one or more reference labels different from the first remainder subsequence of reference labels;

matching the values of the sequence of feature labels against the values of the reference labels in the first remainder subsequence to produce a first remainder match score signal having a remainder match score value representing the similarity of the sequence of feature labels to the reference labels in the first remainder subsequence; and

removing the first remainder subset of template signals from the candidate set of template signals if the local optimum match score value is better than the remainder match score value.

14. A pattern recognition apparatus comprising:

means for generating a sequence of feature label signals, each feature label signal having a value representing the value of at least one feature of an observed information signal;

means for storing a candidate set of template signals, each template signal having a value representing a template sequence of reference labels, each reference label having a value;

means for partitioning the candidate set of template signals into at least first and second subsets of one or more template signals, each template signal in the first subset having a value representing a sequence of reference labels beginning with a first subsequence of one or more reference labels, each template signal in the second subset having a value representing a sequence of reference labels beginning with a second subsequence of one or more reference labels different from the first subsequence of reference labels;

means for matching the values of the sequence of feature labels against the values of the reference labels in the first subsequence to produce a first match score signal having a match score value representing the similarity of the sequence of feature labels to the reference labels in the first subsequence;

means for matching the values of the sequence of feature labels against the values of the reference labels in the second subsequence to produce a second match score signal having a match score value representing the similarity of the sequence of feature labels to the reference labels in the second subsequence;

means for selecting as a local optimum subset of template signals the first subset of template signals if the first match score is better than the second match score, or the second subset of template signals if the second match score is better than the first match score;

means for finding, from the template signals in the local optimum subset, the local optimum template signal whose value is best matched to the values of the sequence of feature labels to produce a local optimum match score signal having a local optimum match score value representing the similarity of the sequence of feature labels to reference labels represented by the local optimum template;

means for defining a remainder set of template signals containing template signals which are not in the local optimum subset of templates;

means for partitioning the remainder set of template signals into at least first and second remainder subsets of one or more template signals, each template signal in the first remainder subset having a value representing a sequence of reference labels beginning with a first remainder subsequence of one or more reference labels, each template signal in the second remainder subset having a value representing a sequence of reference labels beginning with a second remainder subsequence of one or more reference labels different from the first remainder subsequence of reference labels;

means for matching the values of the sequence of feature labels against the values of the reference labels in the first remainder subsequence to produce a first remainder match score signal having a remainder match score value representing the similarity of the sequence of feature labels to the reference labels in the first remainder subsequence; and

means for removing the first remainder subset of template signals from the candidate set of template signals if the local optimum match score value is better than the remainder match score value.