Pattern recognition device using tree structure data
First Claim
1. A pattern recognition device comprising:
- a catalog of a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data;
a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;
parent distance calculating means for calculating respective parent node distances of similarity for each of a plurality of recognition elements included in inputted recognition data;
parent node selecting means for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity;
subordinate distance calculating means for calculating respective subordinate node distances of similarity for each of said recognition elements only for ones of said subordinate nodes linked to said selected parent nodes;
distance storage means for storing only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; and
means for determining a recognition result based on said stored distances.
4 Assignments
0 Petitions
Accused Products
Abstract
The pattern recognition device utilizes a tree structure wherein the phoneme data is organized in a particular fashion. Specifically, the phonemes of the subordinate nodes are categorized into groups made up of similar phonemes. A phoneme that corresponds on average to the groups of subordinate nodes is established as the parent node of that group. Distances of similarity of the plurality of standard elements with respect to each of the plurality of consecutive recognition elements are calculated and stored. Parent nodes for which these distances are small are selected, and the distances with respect to recognition elements are calculated for only the subordinate nodes of the selected parent nodes. Distances stored in this way are accumulated in correspondence with tree structure data and standard data. The item of standard data for which the accumulated distance is the smallest is outputted as the recognition result.
-
Citations
30 Claims
-
1. A pattern recognition device comprising:
-
a catalog of a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;parent distance calculating means for calculating respective parent node distances of similarity for each of a plurality of recognition elements included in inputted recognition data; parent node selecting means for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; subordinate distance calculating means for calculating respective subordinate node distances of similarity for each of said recognition elements only for ones of said subordinate nodes linked to said selected parent nodes; distance storage means for storing only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; and means for determining a recognition result based on said stored distances. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13)
-
-
11. A pattern recognition device comprising:
-
data input means for receiving various inputted recognition data comprising a plurality of consecutive recognition elements; data storing means for storing a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; element storing means for storing a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;data dividing means for generating said plurality of consecutive recognition elements from said inputted recognition data; parent distance calculating means for calculating respective parent node distances of similarity for each of said recognition elements; parent node selecting means for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; subordinate distance calculating means for calculating respective subordinate node distances of similarity for each of said recognition elements only for ones of said subordinate nodes linked to said selected parent nodes; distance storing means for storing only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; distance accumulating means for calculating respective standard data item distances for consecutive ones of said recognition elements, based on only said distances stored in said distance storing means; and result outputting means for selectively outputting standard data, for which said distances accumulated by said distance accumulating means are smallest, as the recognition result.
-
-
14. A pattern recognition device comprising:
-
data input means for receiving various inputted recognition data comprising a plurality of consecutive recognition elements; data storing means for storing a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; element storing means for storing a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;data dividing means for generating said plurality of consecutive recognition elements from said inputted recognition data; parent distance calculating means for calculating respective parent node distances of similarity for each of said recognition elements; parent node selecting means for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; subordinate distance calculating means for calculating respective subordinate node distances of similarity for each of said recognition elements only for ones of said subordinate nodes linked to said selected parent nodes; distance storing means for storing only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; distance accumulating means for calculating respective standard data item distances for consecutive ones of said recognition elements by reading and accumulating said subordinate node distances of subordinate nodes that correspond with standard elements that form standard data from said distance storing means, and reading and accumulating said parent node distances of parent nodes in place of missing subordinate node distances when said subordinate node distances are not stored in said distance storing means; and result outputting means for selectively outputting standard data, for which said distances accumulated by said distance accumulating means are smallest, as the recognition result.
-
-
15. A pattern recognition device comprising:
-
data input means for receiving various inputted recognition data comprising a plurality of consecutive recognition elements; data storing means for storing a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; element storing means for storing a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;data dividing means for generating said plurality of consecutive recognition elements from said inputted recognition data; parent distance calculating means for calculating respective parent node distances of similarity for each of said recognition elements; parent node selecting means for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; subordinate distance calculating means for calculating respective subordinate node distances of similarity for each of said recognition elements only for ones of said subordinate nodes linked to said selected parent nodes; distance storing means for storing only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes;
identifier storing means for storing, for each of said parent nodes, for each of said recognition elements, an identifier indicating the presence or absence of subordinate node distances;position storing means for storing, as position data, the storage positions of said subordinate node distances in said distance storing means for each said identifier indicating said presence of said subordinate node distances; distance reading means for reading said identifiers from said identifier storing means according to identification data of said parent nodes and for reading said subordinate node distances from said distance storing means corresponding to said position data when one of said identifiers indicates that said subordinate node distances are present, and for reading said parent node distances from said predetermined positions when one of said identifiers indicates that said subordinate node distances are not present; distance accumulating means for calculating respective standard data item distances for consecutive ones of said recognition elements, based on distances read by said distance reading means; and result outputting means for selectively outputting standard data, for which said distances accumulated by said distance accumulating means are smallest, as the recognition result. - View Dependent Claims (16, 17)
-
-
18. A pattern recognition device comprising:
-
data input means for receiving various inputted recognition data comprising a plurality of consecutive recognition elements; data storing means for storing a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; element storing means for storing a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;data dividing means for generating said plurality of consecutive recognition elements from said inputted recognition data; parent distance calculating means for calculating respective parent node distances of similarity for each of said recognition elements; parent node selecting means for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; subordinate distance calculating means for calculating respective subordinate node distances of similarity for each of said recognition elements only for ones of said subordinate nodes linked to said selected parent nodes; distance storing means for storing only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; identifier storing means for storing, for each of said parent nodes, for each of said recognition elements, an identifier indicating the presence or absence of subordinate node distances; distance reading means for reading said identifiers from said identifier storing means according to identification data of sa parent nodes, reading said subordinate node distances from said distance storing means when a corresponding one of said identifiers indicates that said subordinate node distances are present, and reading said parent node distances when a corresponding one of said identifiers indicates that distances are not present; distance accumulating means for calculating respective standard data item distances for consecutive ones of said recognition elements, based on distances read by said distance reading means; and result outputting means for selectively outputting standard data, for which said distances accumulated by said distance accumulating means are smallest, as the recognition result. - View Dependent Claims (19, 20)
-
-
21. A pattern recognition device comprising:
-
data input means for receiving various inputted recognition data comprising a plurality of consecutive recognition elements; data storing means for storing a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; element storing means for storing a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;data dividing means for generating said plurality of consecutive recognition elements from said inputted recognition data; parent distance calculating means for calculating respective parent node distances of similarity for each of said recognition elements; parent node selecting means for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; subordinate distance calculating means for calculating respective subordinate node distances of similarity for each of said recognition elements only for ones of said subordinate nodes linked to said selected parent nodes; distance storing means for storing only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; identifier storing means for storing, for each of said parent nodes, for each of said recognition elements, an identifier indicating the presence or absence of subordinate node distances; distance reading means for reading said identifiers from said identifier storing means according to identification data of said parent nodes, reading said parent node distances from said distance storing means when a corresponding one of said identifiers indicates that said subordinate node distances are not present, and calculating a respective storage positions of said subordinate node distances according to tree structure data and reading therefrom said subordinate node distances when a corresponding one of said identifiers indicates that said subordinate node distances are present; distance accumulating means for calculating respective standard data item distances for consecutive ones of said recognition elements, based on distances read by said distance reading means; and result outputting means for selectively outputting standard data, for which said distances accumulated by said distance accumulating means are smallest, as the recognition result.
-
-
22. A pattern recognition device comprising:
-
data input means for receiving various inputted recognition data comprising a plurality of consecutive recognition elements; data storing means for storing a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; element storing means for storing a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;data dividing means for generating said plurality of consecutive recognition elements from said inputted recognition data; parent distance calculating means for calculating respective parent node distances of similarity for each of said recognition elements; parent node selecting means for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; subordinate distance calculating means for calculating respective subordinate node distances of similarity for each of said recognition elements for only ones of said subordinate nodes linked to said selected parent nodes; distance storing means for storing, only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; position storing means for storing, as position data, the storage positions of said distances read from said distance storing means for each item of parent node identification data; distance reading means for reading said position data according to the identification data of said parent nodes and, then, reading said distances; distance accumulating means for calculating respective standard data item distances for consecutive ones of said recognition elements by accumulating said read distances; and result outputting means for outputting standard data, for which said accumulated distances are smallest, as the recognition result. - View Dependent Claims (23, 24)
-
-
25. A pattern recognition device comprising:
-
data input means for receiving various inputted recognition data comprising a plurality of consecutive recognition elements; data storing means for storing a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; element storing means for storing a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;data dividing means for generating said plurality of consecutive recognition elements from said inputted recognition data; parent distance calculating means for calculating respective parent node distances of similarity for each of said recognition elements; parent node selecting means for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; subordinate distance calculating means for calculating respective subordinate node distances of similarity for each of said recognition elements for only ones of said subordinate nodes linked to said selected parent nodes; distance storing means for storing, only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; position storing means for storing, for identification data of one of said parent nodes for which the subordinate node distances have been calculated, position data indicating a position of said subordinate node distances, and storing, for identification data of one of said parent nodes for which the subordinate node distances have not been calculated, position data indicating a position of said parent node distance, and storing, as position data, the storage positions of all said distances read from said distance storing means; distance reading means for reading said position data according to the identification data of said parent nodes and, then, reading said distances; distance accumulating means for calculating respective standard data item distances for consecutive ones of said recognition elements by accumulating said read distances; and result outputting means for outputting standard data, for which said accumulated distances are smallest, as the recognition result.
-
-
26. A pattern recognition method, comprising:
-
a step for storing a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; a step for storing a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;a step for receiving various inputted recognition data comprising a plurality of consecutive recognition elements; a step for generating said plurality of consecutive recognition elements from said inputted recognition data; a step for calculating respective parent node distances of similarity for each of said recognition elements; a step for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; a step for calculating respective subordinate node distances of similarity for each of said recognition elements only for ones of said subordinate nodes linked to said selected parent nodes; a step for storing only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; a step for calculating respective standard data item distances for consecutive ones of said recognition elements, based on only said distances stored in said distance storing means; and a step for selectively outputting standard data, for which said distances accumulated by said distance accumulating means are smallest, as the recognition result.
-
-
27. A pattern recognition method, comprising:
-
a step for storing a plurality of items of standard data each made up of a plurality of consecutive standard elements, said plurality of items of standard data having a predetermined correspondence to prescribed recognition data; a step for storing a predetermined tree structure of data, said tree structure having a root node and a plurality of subordinate nodes, each said subordinate node corresponding to one of said standard elements;
said plurality of subordinate nodes being linked by a number of parent nodes, said number of parent nodes being smaller than a number of said subordinate nodes, said parent nodes each corresponding, on average, to a plurality of mutually similar ones of said standard elements;a step for receiving various inputted recognition data comprising a plurality of consecutive recognition elements; a step for generating said plurality of consecutive recognition elements from said inputted recognition data; a step for calculating respective parent node distances of similarity for each of said recognition elements; a step for selecting ones of said parent nodes based on a magnitude of said respective parent node distances of similarity; a step for calculating respective subordinate node distances of similarity for each of said recognition elements only for ones of said subordinate nodes linked to said selected parent nodes; a step for storing only once, in order, at predetermined positions, said respective parent node distances of similarity, and for storing, in order, at other predetermined positions, only said respective subordinate node distances of similarity for said subordinate nodes of said selected parent nodes; a step for storing, for each of said parent nodes, for each of said recognition elements, an identifier indicating the presence or absence of subordinate node distances; a step for storing, as position data, the storage positions of said subordinate node distances in said distance storing means for each said identifier indicating said presence of said subordinate node distances; a step for reading said identifiers from said identifier storing means according to identification data of said parent nodes; a step for reading said subordinate node distances from said distance storing means corresponding to said position data when one of said identifiers indicates that said subordinate node distances are present; a step for reading said parent node distances from said predetermined positions when one of said identifiers indicates that said subordinate node distances are not present; a step for calculating respective standard data item distances for consecutive ones of said recognition elements, based on distances read by said distance reading means; and a step for selectively outputting standard data, for which said distances accumulated by said distance accumulating means are smallest, as the recognition result.
-
-
28. An information storage medium:
-
on which a plurality of items of standard data are catalogued in advance that are made up from a plurality of consecutive standard elements and that individually correspond to prescribed recognition data; on which tree structure data are catalogued in advance wherein one root node and a large number of subordinate nodes that individually correspond to all standard elements are linked by means of a small number of parent nodes that individually correspond on average to a plurality of mutually similar standard elements; and on which is stored a program that allows a computer to; accept input of various recognition data constituted by a plurality of consecutive recognition elements; divide inputted recognition data into prescribed frames and generate a plurality of consecutive recognition elements; individually calculate distances of similarity of a plurality of parent nodes of tree structure data with respect to generated recognition elements; select parent nodes having small calculated distances; individually calculate distances of a plurality of subordinate nodes of selected parent nodes with respect to recognition elements; temporarily store, only once, at predetermined positions, calculated distances of parent nodes and store, in other predetermined positions, only distances of said subordinate nodes for which said distances are calculated; individually calculate distances of a plurality of standard data with respect to one item of recognition data by accumulating stored distances as distances of standard elements corresponding to standard data; and selectively output the item of standard data for which the accumulated distance is smallest as the recognition result.
-
-
29. An information storage medium:
-
on which a plurality of items of standard data are catalogued in advance that are made up from a plurality of consecutive standard elements and that individually correspond to prescribed recognition data; on which tree structure data are catalogued in advance wherein one root node and a large number of subordinate nodes that individually correspond to all standard elements are linked by means of a small number of parent nodes that individually correspond on average to a plurality of mutually similar standard elements; and on which is stored a program that allows a computer to; accept input of various recognition data constituted by a plurality of consecutive recognition elements; divide inputted recognition data into prescribed frames and generate a plurality of consecutive recognition elements; individually calculate distances of similarity of a plurality of parent nodes of tree structure data with respect to generated recognition elements; select parent nodes having small calculated distances; individually calculate distances of a plurality of subordinate nodes of selected parent nodes with respect to recognition elements; temporarily store, only once, at predetermined positions, calculated distances of parent nodes and store, in other predetermined positions, only distances of said subordinate nodes for which said distances are calculated; individually store identifiers indicating the presence or absence of subordinate node distances for each item of identification data of a parent node; individually store storage positions of subordinate node distances as position data for every item of identification data of a parent node in which an identifier indicating the presence of distances is set; read identifiers according to identification data of parent nodes of tree structure data; read distances of subordinate nodes corresponding to position data when an identifier indicates the presence of distances; read distances of a parent node from a prescribed position when an identifier indicates that distances are not present; individually calculate distances of a plurality of standard data with respect to one item of recognition data by accumulating read distances as distances of standard elements corresponding to standard data; and selectively output the item of standard data for which the accumulated distance is smallest as the recognition result.
-
-
30. An information storage medium on which is stored a program that allows a computer to:
-
accept input of various recognition data constituted by a plurality of consecutive recognition elements; divide inputted recognition data into prescribed frames and generate a plurality of consecutive recognition elements; individually calculate distances of similarity of a plurality of parent nodes of tree structure data with respect to generated recognition elements;
select parent nodes having small calculated distances;individually calculate distances of a plurality of subordinate nodes of selected parent nodes with respect to recognition elements; temporarily store only once, at predetermined positions, calculated distances of parent nodes and store, in other predetermined positions, only distances of said subordinate nodes for which said distances are calculated; individually store identifiers indicating the presence or absence of subordinate node distances for each item of identification data of a parent node; individually store storage positions of subordinate node distances as position data for every item of identification data of a parent node in which an identifier indicating the presence of distances is set; read identifiers according to identification data of parent nodes of tree structure data; read the distance of a subordinate node according to position data when an identifier indicates the presence of distance; read the distance of a parent node from a prescribed position when an identifier indicates that distance is not present; individually calculate distances of a plurality of standard data with respect to one item of recognition data by accumulating read distances as distances of standard elements corresponding to standard data; and selectively output the item of standard data for which the accumulated distance is smallest as the recognition result.
-
Specification