Pattern recognition with a tree structure used for reference pattern feature vectors or for HMM

• US 5,912,989 A
• Filed: 06/06/1996
• Issued: 06/15/1999
• Est. Priority Date: 06/03/1993
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Watanabe, Takao
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Prikockis, Larry J.
• Application Number:
  US08/659,557
• Time in Patent Office: 1,104 Days
• Field of Search: 382/224-228, 382/215
• US Class Current: 382/228
• CPC Class Codes: G10L 15/02 Feature extraction for speech recognition; Selection of recognition unit
• CPC Class Codes: G10L 15/08 Speech classification or search
• CPC Class Codes: G10L 15/10 using distance or distortion measures between unknown speech and reference templates
• CPC Class Codes: G10L 15/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]
• CPC Class Codes: G10L 15/142 Hidden Markov Models [HMMs]

Abstract

Preferably using frame vectors, a reference memory (13) keeps feature vectors of a set as a tree comprising a root node, leaf nodes farthest from the root node, and intermediate nodes with the frame vectors assigned respectively to the leaf nodes. A calculator (17) calculates cluster distances between each feature vector of an input pattern and a subset assigned among the set to each daughter node of a mother node which is first the root node. From the intermediate nodes with the mother node successively selected along each branch of the tree, a selector (19) selects at least one daughter node that gives a shortest possible cluster distance. Controlling the calculator and the selector to use the cluster distances starting at each node selected nearest to the root node and proceeding along the branches to one of the leaf nodes that are used as daughter nodes of mother nodes selected nearest to the leaf nodes, a pattern distance calculator (15, 23) calculates pattern distances between the input pattern and reference patterns represented by the set. If the branches do not reach such leaf nodes, the cluster distances are used to the mother node last selected. Frame distributions of HMM may be used instead of the frame vectors.

Claims

1. A pattern recognition device for locating an input pattern among a plurality of reference patterns represented by a set of reference pattern feature vectors, comprising:

an input pattern buffer for receiving a time sequence of input pattern feature vectors representative of said input pattern;

reference pattern memory means for storing said reference pattern feature vectors in a tree structure including a root node which is located on a root stage and which represents said set of reference pattern feature vectors, a plurality of leaf nodes each representing a corresponding one of said reference pattern feature vectors and located on a leaf stage farthest from said root stage, and a plurality of intermediate nodes representing subsets of said set of reference pattern feature vectors and located on at least one intermediate stage between said root stage and said leaf stage, with said subsets of reference pattern feature vectors represented by said intermediate nodes and the reference pattern feature vectors represented by said leaf nodes being denoted as cluster vectors, wherein cluster vectors are associated with each node except said root node and include feature vectors corresponding to all leaf nodes descending from a non-leaf node;

means for specifying a single specified stage, said single specified stage containing daughter nodes of a mother node, said mother node being located on a stage closer to said root stage than said single specified stage;

distance calculating means for calculating vector distances between each input pattern feature vector and said cluster vectors on said single specified stage, said single specified stage corresponding to one of said at least one intermediate stage and said leaf stage;

selecting means for selecting at least one node among said daughter nodes of said mother node, said at least one selected node representing ones of said cluster vectors for which a shortest one of said vector distances is calculated, said daughter nodes being located on a stage next farther from said root stage than a stage on which said mother node is located;

pattern distance calculating means for controlling said distance calculating means and said selecting means to specify another stage consecutively towards said leaf stage from a stage nearest to said root stage in said at least one intermediate stage with said specified nodes given first by said daughter nodes of said root node and subsequently by said daughter nodes of each of said at least one selected node, to select another node from said intermediate nodes, and for calculating pattern distances between said input pattern and said reference patterns with each pattern distance calculated by using said vector distances alone a path from each of said at least one node selected by said selecting means with said root node used as said mother node and along branches branched from said path to ones of said leaf nodes when said ones of said leaf nodes are used as said daughter nodes of said at least one selected node selected ultimately in each branch from said intermediate nodes; and

locating means for locating said input pattern as one of said reference Patterns for which a shortest one of said pattern distances is calculated,

wherein said pattern distance calculating means comprises;

frame distance calculating means for controlling said distance calculating means and said selecting means to specify said specified stage consecutively towards said leaf stage from the stage nearest to said root stage in said at least one intermediate stage with said specified nodes given first by the daughter nodes of said root node and subsequently by the daughter nodes of each of said at least one selected node selected with said root node used as the mother node and to select said selected node from said intermediate nodes and for calculating frame distances between each input pattern feature vector and said cluster vectors with said vector distances used along a path from each of said at least one selected node selected with said root node used as the mother node and along branches branched from said path to ones of said leaf nodes when said ones of said leaf nodes are used as the daughter nodes of said at least one selected node selected ultimately in each branch from said intermediate nodes; and

calculating means for calculating said pattern distances by using said frame distances.

2. A pattern recognition device for locating an input pattern among a plurality of reference patterns represented by a set of reference pattern feature vectors, comprising:

an input pattern buffer for receiving a time sequence of input pattern feature vectors representative of said input pattern;

reference pattern memory means for storing said reference pattern feature vectors in a tree structure including a root node which is located on a root stage and which represents said set of reference pattern feature vectors, a plurality of leaf nodes each representing a corresponding one of said reference pattern feature vectors and located on a leaf stage farthest from said root stage, and a plurality of intermediate nodes representing subsets of said set of reference pattern feature vectors and located on at least one intermediate stage between said root stage and said leaf stage, with said subsets of reference pattern feature vectors represented by said intermediate nodes and the reference pattern feature vectors represented by said leaf nodes being denoted as cluster vectors, wherein cluster vectors are associated with each node except said root node and include feature vectors corresponding to all leaf nodes descending from a non-leaf node;

means for specifying a single specified stage, said single specified stage containing daughter nodes of a mother node, said mother node being located on a stage closer to said root stage than said single specified stage;

distance calculating means for calculating vector distances between each input pattern feature vector and said cluster vectors on said single specified stage, said single specified stage corresponding to one of said at least one intermediate stage and said leaf stage;

selecting means for selecting at least one node among said daughter nodes of said mother node, said at least one selected node representing ones of said cluster vectors for which a shortest one of said vector distances is calculated, said daughter nodes being located on a stage next farther from said root stage than a stage on which said mother node is located;

pattern distance calculating means for controlling said distance calculating means and said selecting means to specify another stage consecutively towards said leaf stage from a stage nearest to said root stage in said at least one intermediate stage with said specified nodes given first by said daughter nodes of said root node and subsequently by said daughter nodes of each of said at least one selected node, to select another node from said intermediate nodes, and for calculating pattern distances between said input pattern and said reference patterns with each pattern distance calculated by using said vector distances along a path from each of said at least one node selected by said selecting means with said root node used as said mother node and along branches branched from said path to ones of said leaf nodes when said ones of said leaf nodes are used as said daughter nodes of said at least one selected node selected ultimately in each branch from said intermediate nodes; and

locating means for locating said input pattern as one of said reference patterns for which a shortest one of said pattern distances is calculated,

wherein said at least one intermediate stage comprises a first plurality of intermediate stages,

wherein said reference pattern memory means comprises;

frame vector tree memory means for storing said tree structure;

clustering vector memory means preliminarily loaded with said set as clustering vectors;

cluster vector calculating means for clustering said clustering vectors into a second plurality of cluster groups with clusters of said cluster groups represented by said cluster vectors, respectively, said second plurality being equal to said first plurality plus one; and

control means for making in said frame vector tree memory means in which the intermediate nodes of said intermediate stages and said leaf nodes represent said cluster vectors with said cluster groups successively assigned to said intermediate stages except for one of said intermediate stages that is nearest to said root stage.

3. A pattern recognition device for locating an input pattern among a plurality of reference patterns represented by a set of element distributions of continuous mixture density hidden Markov models, comprising:

an input pattern buffer for receiving a time sequence of input pattern feature vectors representative of said input pattern;

reference pattern memory means for storing said element distributions in a tree structure including a root node which is located on a root stage and which represents said set of element distribution, a plurality of leaf nodes each representing a corresponding one of said element distributions and located on a leaf stage farthest from said root stage, and a plurality of intermediate nodes representing subsets of said set of element distributions and located on at least one intermediate stage between said root stage and said leaf stage, with said subsets of element distributions and the element distributions represented by said leaf nodes being denoted as cluster distributions, wherein cluster distributions are associated with each node except said root node and include element distributions corresponding to all leaf nodes descending from a non-leaf node;

means for specifying a single specified stage, said single specified stage containing daughter nodes of a mother node, said mother node being located on a stage closer to said root stage than said single specified stage;

likelihood calculating means for calculating likelihoods between each input pattern feature vector and said cluster distributions by nodes specified among said intermediate nodes and said leaf nodes on said single specified stage, said single specified stage being one of said leaf stage and said at least one intermediate stage;

selecting means for selecting at least one node among said daughter nodes of said mother node, said at least one selected node representing ones of said cluster distributions for which a greatest one of said likelihoods is calculated, said daughter nodes being located on a stage next farther from said root stage than a stage on which said mother node is located;

pattern likelihood calculating means for controlling said likelihood calculating means and said selecting means to specify another stage consecutively towards said leaf stage from a stage nearest to said root stage in said at least one intermediate stage with said specified nodes given first by said daughter nodes of said root node and subsequently by said daughter nodes of each of said at least one selected node, and to select another node from said intermediate nodes, and for calculating pattern likelihoods between said input pattern and said reference patterns with each pattern likelihood calculated by using said likelihoods alone a path from each of said at least one selected node selected by said selecting means with said root node used as said mother node and along branches branched from said path of ones of said leaf nodes when said ones of leaf nodes are used as said daughter nodes of said at least one selected node selected ultimately in each branch from said intermediate nodes; and

locating means for locating said input pattern as one of said reference patterns for which a greatest one of said pattern likelihoods is calculated,

wherein said pattern likelihood calculating means comprises;

frame likelihood calculating means for controlling said likelihood calculating means and said selecting means to specify said specified stage consecutively towards said leaf stage from the stage nearest to said root stage in said at least one intermediate stage with said specified nodes given first by said daughter nodes of said root node and subsequently by said daughter nodes of each of said at least one selected node selected with said root node used as said mother node and to select said another selected node from said intermediate nodes and for calculating frame likelihoods between each input pattern feature vector and said cluster distributions with said likelihoods used along a path from each of said at least one selected node selected with said root node used as said mother node and along branches branched from said path to ones of said leaf nodes when said ones of leaf nodes are used as said daughter nodes of said at lest one selected nodes selected ultimately in each branch from said intermediate nodes; and

calculating means for calculating said pattern likelihoods by using said frame likelihoods.

4. A pattern recognition device for locating an input pattern among a plurality of reference patterns represented by a set of element distributions of continuous mixture density hidden Markov models, comprising:

an input pattern buffer for receiving a time sequence of input pattern feature vectors representative of said input pattern;

reference pattern memory means for storing said element distributions in a tree structure including a root node which is located on a root stage and which represents said set of element distribution, a plurality of leaf nodes each representing a corresponding one of said element distributions and located on a leaf stage farthest from said root stage, and a plurality of intermediate nodes representing subsets of said set of element distributions and located on at least one intermediate stage between said root stage and said leaf stage, with said subsets of element distributions and the element distributions represented by said leaf nodes being denoted as cluster distributions, wherein cluster distributions are associated with each node except said root node and include element distributions corresponding to all leaf nodes descending from a non-leaf node;

means for specifying a single specified stage, said single specified stage containing daughter nodes of a mother node, said mother node being located on a stage closer to said root stage than said single specified stage;

likelihood calculating means for calculating likelihoods between each input pattern feature vector and said cluster distributions by nodes specified among said intermediate nodes and said leaf nodes on said single specified stage, said single specified stage being one of said leaf stage and said at least one intermediate stage;

selecting means for selecting at least one node among said daughter nodes of said mother node, said at least one selected node representing ones of said cluster distributions for which a greatest one of said likelihoods is calculated, said daughter nodes being located on a stage next farther from said root stage than a stage on which said mother node is located;

pattern likelihood calculating means for controlling said likelihood calculating means and said selecting means to specify another stage consecutively towards said leaf stage from a stage nearest to said root stage in said at least one intermediate stage with said specified nodes given first by said daughter nodes of said root node and subsequently by said daughter nodes of each of said at least one selected node, and to select another node from said intermediate nodes, and for calculating pattern likelihoods between said input pattern and said reference patterns with each pattern likelihood calculated by using said likelihoods along a path from each of said at least one selected node selected by said selecting means with said root node used as said mother node and along branches branched from said path of ones of said leaf nodes when said ones of leaf nodes are used as said daughter nodes of said at least one selected node selected ultimately in each branch from said intermediate nodes; and

locating means for locating said input pattern as one of said reference patterns for which a greatest one of said pattern likelihoods is calculated,

wherein said at least one intermediate stage comprises a first plurality of intermediate stages,

wherein said reference pattern memory means comprises;

frame distribution tree memory means for storing said tree structure;

clustering distribution memory means preliminarily loaded with said set as clustering distributions;

cluster distribution calculating means for clustering said clustering distributions into a second plurality of cluster groups with clusters of said cluster groups represented by said cluster distributions, respectively, said second plurality being equal to said first plurality less one; and

control means for making in said frame distribution tree memory means in which the intermediate nodes of said intermediate stages and said leaf nodes represent said cluster distributions with said cluster groups successively assigned to said intermediate stages except for one of said intermediate stages that is nearest to said root stage.