Pattern recognition system with improved recognition rate using nonlinear transformation

• US 5,555,320 A
• Filed: 11/29/1993
• Issued: 09/10/1996
• Est. Priority Date: 11/27/1992
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Irie, Bunpei, Kurosawa, Yoshiaki
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): ANDERSON, DAVID
• Application Number:
  US08/158,857
• Time in Patent Office: 1,016 Days
• Field of Search: 382/14, 382/15, 382/16, 382/3, 382/41, 382/155, 382/156, 382/157, 382/159, 382/119, 382/276, 382/286, 382/225, 381/42, 381/43, 395/2.4, 395/2.41, 395/2.47, 395/2.52, 395/2.54
• US Class Current: 382/225
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods

Abstract

A pattern recognition system capable of handling the non-Gaussian feature vector distribution in the feature vector space such that the recognition rate can be improved while using the pattern matching based on the assumption of the Gaussian feature vector distribution. In the system, a nonlinear transformation for each recognizable category is applied to the feature vector extracted from the input pattern to be recognized, to obtain a transformed feature data for the input pattern, where the nonlinear transformation maps linearly inseparable distributions in a vector space containing the feature vector onto linearly separable distributions. Then, the transformed feature data for the input pattern is compared with reference feature model for each recognizable category indicating a feature vector distribution for each category, to find a category of the input pattern as that of the reference feature model closest to the transformed feature data for the input pattern.

Claims

1. A pattern recognition system for identifying an input pattern with one of a plurality of prescribed recognizable categories for patterns, comprising:

pattern input means for inputting the input pattern to be recognized;

feature extraction means for extracting a feature vector from the input pattern inputted by the pattern input means;

nonlinear transformation means for applying a nonlinear transformation for each of said prescribed recognizable categories to the feature vector extracted by the feature extraction means to obtain a transformed feature data for the input pattern for each of said prescribed recognizable categories, where the nonlinear transformation for each of said prescribed recognizable categories maps linearly inseparable distributions in a vector space containing the feature vector onto separable distributions; and

matching means for comparing the transformed feature data for the input pattern for each of said prescribed recognizable categories with a corresponding reference feature model for each of said prescribed recognizable categories indicating a feature vector distribution for each of said prescribed recognizable categories, for finding a category of the input pattern as that of the reference feature model for one of said prescribed recognizable categories that is closest to the transformed feature data for the input pattern for said one of said prescribed recognizable categories.

2. The system of claim 1, wherein the nonlinear transformation maps a nonlinear subset representing a distribution in the vector space onto a linear space.

3. The system of claim 2, further comprising means for determining the nonlinear transformation for each of said prescribed recognizable categories applied by the nonlinear transformation means, by approximating the feature vector distribution for each of said prescribed recognizable categories obtained by using learning patterns of said each of said prescribed recognizable categories by a nonlinear subset of the feature vector distribution, and choosing a transformation which maps the nonlinear subset onto a linear space as the nonlinear transformation for each of said prescribed recognizable categories.

4. The system of claim 1, further comprising dictionary means for registering the reference feature model for each of said prescribed recognizable categories in advance.

5. The system of claim 4, further comprising means for determining the reference feature model for each of said prescribed recognizable categories registered into the dictionary means as data indicating a distribution obtained by applying the nonlinear transformation for each of said prescribed recognizable categories to the feature vector distribution for each of said prescribed recognizable categories obtained by using learning patterns of said each of said prescribed recognizable categories.

6. The system of claim 1, wherein the matching means compares the transformed feature data for the input pattern with the reference feature model for each of said prescribed recognizable categories, by calculating a similarity of the transformed feature data for the input pattern and the reference feature model for each of said prescribed recognizable categories, such that the reference feature model closest to the transformed feature data for the input pattern is found as that for which the calculated similarity is maximum among all the reference feature model for all of said prescribed recognizable categories.

7. The system of claim 1, wherein the nonlinear transformation subdivides the feature vector distribution into a number of small regions, and maps each of the subdivided small regions separately onto a linear space.

8. The system of claim 1, wherein when the feature vector distribution for a certain one of said prescribed recognizable categories contains a plurality of spatially separated distribution blocks in the vector space, the nonlinear transformation superposes said plurality of spatially separated distribution blocks with each other in the vector space.

9. The system of claim 1, further comprising presentation means for presenting information related to the feature vector distribution for each of said prescribed recognizable categories obtained by using learning patterns of said each of said prescribed recognizable categories for an inspection by an operator.

10. The system of claim 9, wherein the presentation means presents the information in at least one of:

(1) a mode for displaying a projection of the feature vector distribution onto a subspace of the vector space;

(2) a mode for displaying a cross section of the feature vector distribution;

(3) a mode for displaying a plurality of cross sections of the feature vector distribution in an ordered sequence;

(4) a mode for displaying the feature vector distributions for more than one of said prescribed recognizable categories together, with different brightnesses or colors assigned for different ones of said prescribed recognizable categories;

(5) a mode for displaying at least one of the input pattern and the feature vector corresponding to a plurality of points in the feature vector distribution, in identical positional relationships as said plurality of points have in the feature vector distribution; and

(6) a mode for presenting at least one of the input pattern and the feature vector for a point in the feature vector distribution specified by an operator.

11. The system of claim 1, wherein the feature extraction means comprises a KxK Gaussian Function Filter, K is an integer, and wherein a KxK-dimensional feature vector is extracted as a result thereof.

12. A method of pattern recognition for identifying an input pattern with one of a plurality of prescribed recognizable categories for patterns, comprising the steps of:

(a) inputting the input pattern to be recognized;

(b) extracting a feature vector from the input pattern inputted at the step (a);

(c) applying a nonlinear transformation for each of said prescribed recognizable categories to the feature vector extracted at the step (b) to obtain a transformed feature data for the input pattern for each of said prescribed recognizable categories, where the nonlinear transformation for each of said prescribed recognizable categories maps linearly inseparable distributions in a vector space containing the feature vector onto linearly separable distributions; and

(d) comparing the transformed feature data for the input pattern for each said prescribed recognizable categories with a corresponding reference feature model for each of said prescribed recognizable categories indicating a feature vector distribution for each of said prescribed recognizable categories, for finding a category of the input pattern as that of the reference feature model for one of said prescribed recognizable categories that is closest to the transformed feature data for the input pattern for said one of said prescribed recognizable categories.

13. The method of claim 12, wherein the nonlinear transformation maps a nonlinear subset representing a distribution in the vector space onto a linear space.

14. The method of claim 13, further comprising the step of determining the nonlinear transformation for each of said prescribed recognizable categories applied at the step (c), by approximating the feature vector distribution for each of said prescribed recognizable categories obtained by using learning patterns of said each of said prescribed recognizable categories by a nonlinear subset of the feature vector distribution, and choosing a transformation which maps the nonlinear subset onto a linear space as the nonlinear transformation for each of said prescribed recognizable categories.

15. The method of claim 12, further comprising the step of registering the reference feature model for each of said prescribed recognizable categories in a form of a dictionary in advance.

16. The method of claim 15, further comprising the step of determining the reference feature model for each of said prescribed recognizable categories registered into the dictionary as data indicating a distribution obtained by applying the nonlinear transformation for each of said prescribed recognizable categories to the feature vector distribution for each of said prescribed recognizable categories obtained by using learning patterns of said each of said prescribed recognizable categories.

17. The method of claim 12, wherein the step (d) compares the transformed feature data for the input pattern with the reference feature model for each of said prescribed recognizable categories, by calculating a similarity of the transformed feature data for the input pattern and the reference feature model for each of said prescribed recognizable categories, such that the reference feature model closest to the transformed feature data for the input pattern is found as that for which the calculated similarity is maximum among all the reference feature models for all of said prescribed recognizable categories.

18. The method of claim 12, wherein the nonlinear transformation subdivides the feature vector distribution into a number of small regions, and maps each of the subdivided small regions separately onto a linear space.

19. The method of claim 12, wherein when the feature vector distribution for a certain one of said prescribed recognizable categories contains a plurality of spatially separated distribution blocks in the vector space, the nonlinear transformation superposes said plurality of spatially separated distribution blocks with each other in the vector space.

20. The method of claim 12, further comprising the step of presenting information related to the feature vector distribution for each of said prescribed recognizable categories obtained by using learning patterns of said each of said prescribed recognizable categories for an inspection by an operator.

21. The method of claim 20, wherein the presenting step presents the information in at least one of:

(1) a mode for displaying a projection of the feature vector distribution onto a subspace of the vector space;

(2) a mode for displaying a cross section of the feature vector distribution;

(3) a mode for displaying a plurality of cross sections of the feature vector distribution in an ordered sequence;

(4) a mode for displaying the feature vector distributions for more than one of said prescribed recognizable categories together, with different brightnesses or colors assigned for different ones of said prescribed recognizable categories;

(5) a mode for displaying at least one of the input pattern and the feature vector corresponding to a plurality of points in the feature vector distribution, in identical positional relationship as said plurality of points have in the feature vector distribution; and

(6) a mode for presenting at least one of the input pattern and the feature vector for a point in the feature vector distribution specified by an operator.

22. The method of claim 12, wherein the feature vector is extracted in the step (b) by using a KxK Gaussian Function Filter, K is an integer, and wherein a KxK-dimensional feature vector is extracted as a result thereof.