Pattern recognition methods and apparatus to reduce processing time by groupnise comparison of features and coordinated dynamic elimination of candidates
First Claim
1. A neighbor detection method, in a feature space comprised of a plurality of dimensions, wherein each dimension represents one of a plurality of features of pattern attributes, for calculating distance values between an input point and a plurality of prototypes that are distributed across a feature space, and for detecting a neighbor prototype that has a small distance value, comprising the steps of:
- (a) sorting said plurality of features to a plurality of groups, with each of said plurality of groups comprising at least one of said plurality of features;
(b) determining a first threshold value for said plurality of groups, wherein said first threshold value is based on a quantity of information related to said plurality of features of each of said plurality of groups, and wherein said first threshold value is assigned to at least two groups of said plurality of groups as different values;
(c) calculating an accumulated distance value for said plurality of groups to add distance values of said input point and said plurality of prototypes, according to a predetermined order and calculating a minimum accumulated distance value for each of said groups;
(d) excluding, from a target for a following distance calculation, a prototype for which said accumulated distance value to a first specific group in said feature space is provided that exceeds said first threshold value assigned to said first specific group; and
(e) excluding, from the target for a following distance calculation, a sample point for which said minimum accumulated distance value to a second specific group in said feature space is provided that exceeds a second threshold value assigned to said second specific group wherein said second threshold is determined of said minimum accumulated distance value of said second specific group, wherein said second specific group is the target for calculation of step (d).
1 Assignment
0 Petitions
Accused Products
Abstract
The detection of a nearest neighbor is calculated at high speed and with high accuracy. Feature space grouping is performed, with one, or two or more features being assigned to each group. A check is performed to determine whether or not a calculated distance value that is acquired before the limits for a group is reached has exceeded the threshold value THR-- MIX for each group. The threshold value that is set for THR-- MIX is the average of the threshold value that is determined based on the cumulative quantity of the features that is acquired and the threshold value that is based on the number of dimensions. When the distance value for each group is greater than the threshold value THR-- MIX, first phase screening is performed to exclude, from the succeeding distance calculations, the prototype that provides that distance value. Then, for a group for which the first phase screening is performed, the threshold value THR-- RATE is calculated by using the minimum distance value to that group, and the second phase screening is performed.
-
Citations
17 Claims
-
1. A neighbor detection method, in a feature space comprised of a plurality of dimensions, wherein each dimension represents one of a plurality of features of pattern attributes, for calculating distance values between an input point and a plurality of prototypes that are distributed across a feature space, and for detecting a neighbor prototype that has a small distance value, comprising the steps of:
-
(a) sorting said plurality of features to a plurality of groups, with each of said plurality of groups comprising at least one of said plurality of features; (b) determining a first threshold value for said plurality of groups, wherein said first threshold value is based on a quantity of information related to said plurality of features of each of said plurality of groups, and wherein said first threshold value is assigned to at least two groups of said plurality of groups as different values; (c) calculating an accumulated distance value for said plurality of groups to add distance values of said input point and said plurality of prototypes, according to a predetermined order and calculating a minimum accumulated distance value for each of said groups; (d) excluding, from a target for a following distance calculation, a prototype for which said accumulated distance value to a first specific group in said feature space is provided that exceeds said first threshold value assigned to said first specific group; and (e) excluding, from the target for a following distance calculation, a sample point for which said minimum accumulated distance value to a second specific group in said feature space is provided that exceeds a second threshold value assigned to said second specific group wherein said second threshold is determined of said minimum accumulated distance value of said second specific group, wherein said second specific group is the target for calculation of step (d). - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A neighbor detection system, in a feature space comprised of a plurality of dimensions, wherein each dimension represents one of a plurality of features of pattern attributes, for calculating distance values between an input point and a plurality of prototypes that are distributed across a feature space, and for detecting a neighbor prototype that has a small distance value, comprising:
-
(a) means for sorting said plurality of features to a plurality of groups, with each of said plurality of groups comprising at least one of said plurality of features; (b) means for determining a first threshold value for said plurality of groups, wherein said first threshold value is based on a quantity of information related to said plurality of features of each of said plurality of groups, and wherein said first threshold value is assigned to a least two groups of said plurality of groups as different values; (c) means for calculating an accumulated distance value for said plurality of groups to add distance values of said input point and said plurality of prototypes, according to a predetermined order and calculating a minimum accumulated distance value for each of said groups; (d) means for excluding, from a target for a following distance calculation, a prototype for which said accumulated distance value to a first specific group in said feature space is provided that exceeds said first threshold value assigned to said first specific group; and (e) means for excluding, from the target for a following distance calculation, a sample point for which said minimum accumulated distance value to a second specific group in said feature space is provided that exceeds a second threshold value assigned to said second specific group wherein said second threshold is determined on said minimum accumulated distance value of said second specific group, wherein said second specific group is the target for calculation of said means for excluding a prototype. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A computer program product recorded on computer readable media for a neighbor detection system, in a feature space comprised of a plurality of dimensions, wherein each dimension represents one of a plurality of features of pattern attributes, for calculating distance values between an input point and a plurality of prototypes that are distributed across a feature space, and for detecting a neighbor prototype that has a small distance value, said product comprising:
-
(a) computer readable means for sorting said plurality of features to a plurality of groups, with each of said plurality of groups comprising at least one of said plurality of features; (b) computer readable means for determining a first threshold value for said plurality of groups, wherein said first threshold value is based on a quantity of information related to said plurality of features of each of said plurality of groups, and wherein said first threshold value is assigned to a least two groups of said plurality of groups as different values; (c) computer readable means for calculating an accumulated distance value for said plurality of groups to add distance values of said input point and said plurality of prototypes, according to a predetermined order and calculating a minimum accumulated distance value for each of said groups; (d) computer readable means for excluding, from a target for a following distance calculation, a prototype for which said accumulated distance value to a first specific group in said feature space is provided that exceeds said first threshold value assigned to said first specific group; and (e) computer readable means for excluding, from the target for a following distance calculation, a sample point for which said minimum accumulated distance value to a second specific group in said feature space is provided that exceeds a second threshold value assigned to said second specific group wherein said second threshold is determined on said minimum accumulated distance value of said second specific group, wherein said second specific group is the target for calculation of said computer readable means for excluding a prototype. - View Dependent Claims (14, 15, 16, 17)
-
Specification