Method of generating dictionary for pattern recognition and pattern recognition method using the same

• US 5,602,938 A
• Filed: 05/20/1994
• Issued: 02/11/1997
• Est. Priority Date: 05/20/1994
• Status: Expired due to Term

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Akiyama, Teruo, Sawaki, Minako, Kawatani, Takahiko
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/246,520
• Time in Patent Office: 998 Days
• Field of Search: 382/155-161, 382/178-179, 382/185-187, 382/200, 382/224, 382/225, 382/228, 382/197, 382/198
• US Class Current: 382/155
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier

Abstract

A reference pattern vector is obtained from training patterns belonging to each class and is held as a parameter of an original distance function in a distance dictionary. A discriminant function is defined which has, as variables, the difference between respective corresponding components of a feature vector of each training pattern and the corresponding reference pattern vector and the square of the difference. Training patterns of all classes are discriminated with the original distance function and a rival pattern set, which includes patterns misclassified as belonging to a respective class, is derived from the results of discrimination of the training patterns. A discriminant analysis is made between the training pattern set of each class and the corresponding rival pattern set to thereby determine parameters of the discriminant function, which are held in a discriminant dictionary. The original distance function and the discriminant function are additively coupled together by a predetermined coupling coefficient to define a learned distance function, which is used to discriminate the training patterns to update the learned distance function.

Claims

1. A method of generating a dictionary for pattern recognition in which a feature vector of an input pattern is compared with a reference pattern vector of each class, read out of a pattern recognition dictionary, and a class of the reference pattern vector closest to said input pattern is output as the recognized result of said input pattern, said method comprising the steps of:

a) extracting features of each of a plurality of training patterns each belonging to one of a plurality of predetermined classes and expressing said features of each training pattern as a vector;

b) obtaining, as said reference pattern vector, the mean of said feature vectors of said training patterns of each class;

c) discriminating each of said training patterns of all classes through use of an original distance function using said reference pattern vectors corresponding to each class to obtain for each class, a rival pattern set containing patterns misclassified as belonging to said each class;

d) defining a discriminant function which contains, as first and second variables, the difference between respectively corresponding components of a feature vector of a training pattern and a reference pattern vector and the square of said difference and determining, for each class, parameters of said discriminant function so that a discrimination is made between patterns forming a training pattern set of said each class and patterns forming said rival pattern set for said each class; and

e) writing, for each class, parameter information into dictionary means, said parameter information corresponding to the parameters of said original distance function containing said reference pattern vector of said each class and parameters of said discriminant function determined for said each class.

3. The method of claim 1 or 2, wherein said dictionary means comprises an original dictionary and a discriminant dictionary and said step of writing said parameter information into said dictionary means comprises a step of writing said parameters of said original distance function of each class into said original dictionary and writing said parameters of said discriminant function into said discriminant dictionary.

4. The method of claim 1 or 2, wherein said step of writing said parameter information into said dictionary means comprises a step of writing parameters obtained by modifying said parameter of said original distance function with said parameter of said discriminant function.

5. The method of claim 1 or 2, which further includes a step of defining a learned distance function obtained by additively coupling said original distance function and said discriminant function with a coupling coefficient, discriminating all training patterns of all of said classes by referring to said dictionary means through use of said learned distance function, and determining said coupling coefficient so that the recognition rate resulting from said discrimination becomes maximum, and holding said coupling coefficient.

6. The method of claim 5, which further comprises steps of:

discriminating said all training patterns by referring to said dictionary means through use of said learned distance function using said determined coupling coefficient and adding new rival patterns, obtained on the basis of the results of said discrimination, to said rival pattern set of the corresponding class to update said rival pattern set; and

making a discrimination based on discriminant analysis between said training pattern set of each class and said updated rival pattern set to update said discriminant function, thereby updating said parameter information of said dictionary means which defines said learned distance function.

7. The method of claim 6, which further comprises a step of obtaining the recognition rate for said all training patterns upon each repetition of said rival pattern set updating step and said parameter information updating step, and ending said repetitive learning of said updating steps when said recognition rate is below the previous one.

8. The method of claim 7, which further comprises a step of obtaining a plurality of dictionaries by holding an updated dictionary upon each updating of said dictionary means, obtaining the recognition rate for said training patterns of each class through utilization of the corresponding parameter information of said plurality of dictionaries, selecting parameter information of one of said dictionaries for each class which maximizes said recognition rate, and reconstructing said dictionary to use said selected parameter as ultimate parameter information for said class.

9. The method of claim 5, which further comprises steps of:

determining a temporary coupling coefficient larger than said determined coupling coefficient by a predetermined width, discriminating said all training patterns by referring to said dictionary means through use of said learned distance function using said temporary coupling coefficient, and adding new rival patterns, obtained on the basis of the results of said discrimination, to said rival pattern set of the corresponding class to update said rival pattern set; and

making a discrimination based on discriminant analysis between said training pattern set of each class and said updated rival pattern set to update said discriminant function, thereby updating said parameter information of said dictionary means which defines said learned distance function.

10. The method of claim 9, which further comprises a step of obtaining the recognition rate for said all training patterns upon each repetition of said rival pattern set updating step and said parameter information updating step, and ending said repetitive learning of said updating steps when said recognition rate is below the previous one.

11. The method of claim 10, which further comprises a step of obtaining a plurality of dictionaries by holding an updated dictionary upon each updating of said dictionary means, obtaining the recognition rate for said training patterns of each class through utilization of the corresponding parameter information of said plurality of dictionaries, selecting parameter information of one of said dictionaries for each class which maximizes said recognition rate, and reconstructing said dictionary to use said selected parameter information as ultimate parameter information for said class.

12. The method of claim 9, wherein said temporary coupling coefficient is chosen such that when new rival patterns obtained by discriminating all patterns with said learned distance function using said temporary coupling coefficient are added to the corresponding rival pattern set, the number of new rival patterns of said rival patterns set for at least one class is larger than a predetermined value.

13. The method of claim 1 or 2, wherein said rival pattern set for each class contains, as rival patterns, patterns belonging to classes other than the currently noticed one and correctly classified as belonging to said other classes for each of which the difference between the distance from the reference pattern vector of said notice class and the distance from the reference pattern vector of each of said other classes is within a predetermined range.

14. The method of claim 1 or 2, which further comprises a step of generating modified patterns by modifying a plurality of misclassified patterns in said rival pattern for at least one class, discriminating said modified patterns with said original distance function, and adding those modified patterns recognized as rival patterns for said at least one class, as pseudo-rival patterns, to said rival pattern set, and wherein said discriminant analysis is made between said rival pattern set added with said pseudo-rival patterns and the training pattern set of the corresponding class.

2. A method of generating a dictionary for pattern recognition in which a feature vector of an input pattern is compared with a reference pattern vector of each class, read out of a pattern recognition dictionary, and a class of the reference vector pattern closest to said input pattern is output as the recognized result of said input pattern, said method comprising the steps of:

a) extracting features of each of a plurality of training patterns each belonging to one of a plurality of predetermined classes and expressing said features of each training pattern as a vector;

b) obtaining, as said reference pattern vector, the mean of said feature vectors of said training patterns of each class;

c) discriminating each of said training patterns of all classes through use of an original distance function using said reference pattern vectors corresponding to each class to obtain, for said each class, a rival pattern set containing patterns misclassified as belonging to said each class;

d) defining a discriminant function which contains, as first and second variables, a vector component obtained by projecting the difference between respectively corresponding components of a feature vector of a training pattern and a reference pattern vector into a subspace defined by the eigenvector of a covariance matrix of said class and the square of said vector component, and determining, for each class, parameters of said discriminant function so that a discrimination is made between patterns forming a training pattern set of said each class and patterns forming said rival pattern set for said each class; and

e) writing, for said each class, parameter information into dictionary means, said parameter information corresponding to the parameters of said original distance function containing said reference pattern vector of said each class and parameters of said discriminant function determined for said each class.

15. A pattern recognition method which discriminates an input pattern by referring to dictionary means, and in which a discriminant function is predefined which includes, as first and second variables, the difference between respective corresponding components of a feature vector of each input pattern and the corresponding reference pattern vector and the square of said difference, and said dictionary means has stored therein, for each class, parameter information corresponding to parameters of said discriminant function and parameters of an original distance function, said parameters of said discriminant function being determined so that a discrimination is made by said discriminant function between a set of training patterns of each class and a set of rival patterns of said each class, said rival patterns set including patterns misclassified for each class when all training patterns of all classes are discriminated with said original distance function, and said parameters of said original distance function including said reference pattern vector of each class, said method comprising the steps of:

a) extracting a feature vector of said input pattern;

b) calculating, for each class, the distance between said feature vector of said input pattern and said reference pattern vector by applying said parameter information of each class, read out of said dictionary means, to a learned distance function formed by said original distance function and said discriminant function additively coupled by a predetermined coupling coefficient; and

c) determining, as the class to which said input pattern belongs, the class in which to minimize said distance.

17. The method of claim 15 or 16, wherein said dictionary means comprises an original dictionary and a discriminant dictionary, said parameters of said original distance function being written in said original dictionary and said parameters of said discriminant function being written in said discriminant dictionary.

18. The method of claim 15 or 16, wherein said parameter information is parameters obtained by modifying said parameters of said original distance functions by parameters of said discriminant function.

16. A pattern recognition method which discriminates an input pattern by referring to dictionary means, and in which a discriminant function is predefined which includes, as first and second variables, a component of a vector and the square of said component, said component of said vector being obtained by projecting the difference between respective corresponding components of a feature vector of each input pattern and the corresponding reference pattern vector into a subspace defined by an eigenvector of a covariance matrix of each class, and said dictionary means has stored therein, for each class, parameter information corresponding to parameters of said discriminant function and parameters of an original distance function, said parameters of said discriminant function being determined so that a discrimination is made by said discriminant function between a set of training patterns of each class and a set of rival patterns of said each class, said rival pattern set including patterns misclassified for each class when all training patterns of all classes are discriminated with said original distance function, and said parameters of said original function including said reference pattern vector of each class, said method comprising the steps of:

a) extracting a feature vector of said input pattern;

b) calculating, for each class, the distance between said feature vector of said input pattern and said reference pattern vector by applying said parameter information of each class, read out of said dictionary means, to a learned distance function formed by said original distance function and said discriminant function additively coupled by a predetermined coupling coefficient; and

c) determining, as the class to which said input pattern belongs, the class in which to minimize said distance.

19. A pattern recognition method which discriminates an input pattern by referring to an original dictionary and a discriminant dictionary and in which a discriminant function is predefined which includes, as first and second variables, a component of a vector and the square of said component, said component of said vector being obtained by projecting the difference between respective corresponding components of a feature vector of each pattern and the corresponding reference pattern vector into a subspace defined by an eigenvector of a covariance matrix of each class, said original dictionary has stored therein, for each class, parameters of an original distance function, and said discriminant dictionary has stored therein parameters of said discriminant function, said parameters of said discriminant function being determined so that a discrimination is made by said discriminant function between a set of training patterns of each class and a set of rival patterns of said each class, said rival pattern set including patterns misclassified for each class when all training patterns of all classes are discriminated with said learned distance function, and said parameters of said original distance function including the reference pattern vector of each class, said method comprising the steps of:

a) extracting a feature vector of said input pattern;

b) calculating, for each class, the distance between said feature vector and said reference pattern vector of said input pattern by applying said parameters of each class, read out of said original dictionary, to said original distance function;

c) selecting a plurality of said calculated distances in increasing order of distance and selecting, as class candidates, a plurality of classes corresponding to said plurality of selected distances; and

d) calculating the value of said discriminant function by applying thereto said parameters read out of said discriminant dictionary for each of said class candidates and determining, as the class to which said input pattern belongs, the class candidate which provides the minimum value of said discriminant function.

20. A pattern recognition method which discriminates an input pattern by referring to an original dictionary and a discriminant dictionary and in which a discriminant function is predefined which includes, as first and second variables, the difference between respective corresponding components of a feature vector or each pattern and the corresponding reference pattern vector and the square of said difference, said original dictionary has stored therein, for each class, parameters of an original distance function, and said discriminant dictionary has stored therein parameters of said discriminant function, said parameters of said discriminant function being determined so that a discrimination is made by said discriminant function between a set of training patterns of each class and a set of rival patterns of training patterns of each class and a set of rival patterns of said each class, said rival pattern set including patterns misclassified for each class when all training patterns of all classes are discriminated with said learned distance function, and said parameters of said original distance function including the reference pattern vector of each class, said method comprising the steps of:

a) extracting a feature vector of said input pattern;

b) calculating, for each class, the distance between said feature vector and said reference pattern vector of said input pattern by applying said parameters of each class, read out of said distance dictionary, to said original distance function;

c) selecting a plurality of said calculated distances in increasing order of distance and selecting, as class candidates, a plurality of selected distances; and

d) calculating the value of said discriminant function by applying thereto said parameters read out of said discriminant dictionary for each of said class candidate and determining, as the class to which said input pattern belongs, the class candidate which provides the minimum value of said discriminant function.