Pattern recognition methods and apparatus to reduce processing time by groupnise comparison of features and coordinated dynamic elimination of candidates

• US 5,937,093 A
• Filed: 07/17/1996
• Issued: 08/10/1999
• Est. Priority Date: 07/26/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Takahashi, Hiroyasu
• Primary Examiner(s): Vu, Kim Yen
• Assistant Examiner(s): ROSENBLUM, DAVID J
• Application Number:
  US08/682,347
• Time in Patent Office: 1,119 Days
• Field of Search: 382/226, 382/253, 382/190, 382/192, 382/225, 382/217, 382/218, 382/195, 382/224, 382/228, 382/229, 382/227
• US Class Current: 382/226
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification

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.

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).

2. The neighbor detection method according to claim 1, wherein said first threshold value is determined by a cumulative quantity of features, which is obtained by adding together, in said predetermined order, quantities of features for said input point for each of said groups.

3. The neighbor detection method according to claim 1, wherein said first threshold value is determined by a cumulative number of features, which is acquired by adding together, in said predetermined order, the number of said features for said groups.

4. The neighbor detection method according to claim 1, wherein said first threshold value is determined by a cumulative quantity of features, which is obtained by adding together, in said predetermined order, quantities of features for said input point until limits for said groups are reached, and a cumulative number of features, which is obtained by adding together, in said predetermined order, the number of said features for said groups.

5. The neighbor detection method according to claim 4, wherein said first threshold value is determined by an average value for said cumulative quantity of features and said cumulative number of features.

6. The neighbor detection method according to claim 5, wherein said predetermined order is in consonance with a degree of dispersion for the quantity of features that is found in each of said groups.

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.

8. The neighbor detection system of claim 7, wherein said first threshold value is determined by a cumulative quantity of features, which is obtained by adding together, in said predetermined order, quantities of features for said input point for each of said groups.

9. The system of claim 7, wherein said first threshold value is determined by a cumulative number of features, which is acquired by adding together, in said predetermined order, the number of said features for said groups.

10. The system of claim 7, wherein said first threshold value is determined by a cumulative quantity of features, which is obtained by adding together, in said predetermined order, quantities of features for said input point until limits for said groups are reached, and a cumulative number of features, which is obtained by adding together, in said predetermined order, the number of said features for said groups.

11. The system of claim 10, wherein said first threshold value is determined by an average value for said cumulative quantity of features and said cumulative number of features.

12. The system of claim 11, wherein said predetermined order is in consonance with a degree of dispersion for the quantity of features that is found in each of said groups.

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.

14. The computer program product of claim 13, wherein said first threshold value is determined by a cumulative quantity of features, which is obtained by adding together, in said predetermined order, quantities of features for said input point for each of said groups.

15. The computer program product of claim 13, wherein said first threshold value is determined by a cumulative number of features, which is acquired by adding together, in said predetermined order, the number of said features for said groups.

16. The computer program product of claim 13, wherein said first threshold value is determined by a cumulative quantity of features, which is obtained by adding together, in said predetermined order, quantities of features for said input point until limits for said groups are reached, and a cumulative number of features, which is obtained by adding together, in said predetermined order, the number of said features for said groups.

17. The computer program product of claim 16, wherein said first threshold value is determined by an average value for said cumulative quantity of features and said cumulative number of features.