JPH04256087A - Pattern recognition device - Google Patents

Abstract

PURPOSE:To recognize a pattern with the high identification capacity of a similar class and with less recognition errors. CONSTITUTION:Pattern data observed in a pattern input part 1 is converted into a feature vector in a feature extraction part 2. A main component dictionary part 3 generated by the analysis of the main component of learning data and a discrimination dictionary part 4 generated by discriminating and analyzing learning data are given. An unknown input pattern is distance-calculated with the main component dictionary in a projection distance calculation part 7 and with the discrimination dictionary in a discrimination dictionary calculation part 11. A synthetic judgement part 13 rejects a pattern whose distance value is large based on a projection distance value and adopts a judgement result based on a discrimination distance value as to the pattern whose distance value is approximated to the other different class. Thus, erroneous recognition for the pattern which is not considered at the time of learning by a main component analysis method effective for catching the whole image of the pattern is prevented, a discrimination analysis method whose identification capacity of the similar class is high is shared and high recognition precision can be recognized.

Description

[Detailed description of the invention]

0001

[Industrial Application Field] The present invention is applicable to handwritten characters, printed characters,
Regarding pattern recognition methods for automatically recognizing speech, etc.
In particular, it relates to a pattern recognition method for automatically recognizing similar classes of character shapes, sounds, etc.

0002

[Background Art] A general pattern recognition method uses observed feature vectors.

[Math 1]

0003

[0004] This is for efficiently associating [0004] with a category set without error. However, in order to recognize characters, sounds, etc. without errors, the observed feature vector x needs to be a high-dimensional vector, but it also contains redundancy that is unrelated to recognition, and performing recognition processing without information compression requires a huge amount of calculation. becomes. Therefore, for efficient recognition, it is necessary to further extract features effective for classification and identification based on the statistical structure of the feature vector x, and to construct an efficient feature space Fd with fewer dimensions. . Conventionally, methods using principal component analysis and discriminant analysis, which are statistical methods, have been reported as methods for constructing the feature space Fd. [Reference: Otsu: “Mathematical research on feature extraction in pattern recognition,” Research Report of the Institute of Electronics Technology, No. 818 (1981)”].

[0005]

[Problems to be Solved by the Invention] The conventional pattern recognition methods using principal component analysis and discriminant analysis described above have advantages and disadvantages.

[0006] The principal component analysis method expresses a high-dimensional pattern set belonging to a certain class using low-dimensional mutually orthogonal principal component axes, and the hyperplane obtained by principal component analysis optimizes the pattern set using the standard of square error. Approximate. Although it is an excellent method in the sense that it describes the overall picture of a pattern with a small number of features, it does not take into account the distribution of patterns in other classes at all, so its ability to discriminate when similar classes exist is low. There are drawbacks.

Discriminant analysis extracts discriminant axes with high ability to separate classes from a set of high-dimensional patterns of multiple classes and converts them into a low-dimensional discriminant space. , there is a high possibility that the features emphasized for class identification will be partial features, and if a pattern that has not been considered during learning is input, there is a drawback that the class will often be determined incorrectly.

[0008] The purpose of the present invention is to focus on the fact that principal component analysis and discriminant analysis have different features, and to utilize the strengths of each method to achieve high-accuracy recognition performance by combining both methods. An object of the present invention is to provide a pattern recognition device having the following features.

[0009]

[Means for Solving the Problems] The present invention provides a pattern in which pattern data observed in a pattern input unit is converted into a feature vector in a feature extraction unit, and a pattern is determined based on the distance value between the feature vector and the recognition dictionary vector. In the recognition device,
a principal component dictionary section created based on principal component analysis of the learning pattern; a projection distance calculation section that calculates the distance between the feature vector and the principal component dictionary; a discriminant dictionary section created based on the discriminant analysis of the learning pattern; a discriminant distance calculation section that calculates the distance between the feature vector and the discriminant dictionary; and a comprehensive judgment section that performs comprehensive judgment based on the projection distance value obtained by the projection distance calculation section and the discriminant distance value obtained by the discriminant distance calculation section. It is characterized by having the following.

As described above, the present invention has a principal component dictionary part obtained by principal component analysis method and a discriminant dictionary part obtained by discriminant analysis method. A principal component dictionary with excellent descriptive ability and stability is used, and a discriminant dictionary with high discrimination ability for similar classes is used in the identification stage to determine categories belonging to one class from a plurality of candidates.

[0011]

Embodiments Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 shows the configuration and processing flow of one embodiment. This pattern recognition device includes a pattern input section 1, a feature extraction section 2 that converts pattern data observed by the pattern input section 1 into feature vectors, and a principal component dictionary section 3 that is created based on principal component analysis of learning patterns. , a projection distance calculation section 7 that calculates the distance between the feature vector and the principal component dictionary, a discriminant dictionary section 4 that is created based on the discriminant analysis of the learning pattern, and a discriminant distance calculation section that calculates the distance between the feature vector and the discriminant dictionary. unit 11, and a comprehensive determination unit 13 that performs comprehensive determination based on the projection distance value determined by the projection distance calculation unit 7 and the discrimination distance value determined by the discrimination distance calculation unit 11.

The pattern input section 1 is composed of a CCD sensor and a microphone, and performs A/D conversion on character signals and audio signals inputted through these, and converts observed data into time-series discrete data.

The feature extractor 2 converts time-series discrete data into a feature vector x. An example of the processing of the feature extraction unit 2 will be explained using FIGS. 2 to 4. Character observation data obtained by the pattern input section 1 is shown in FIG. 15 is a black dot part of the character, and 16 is a background part of the character, and these correspond to time-series discrete data. The feature extraction unit 2 performs character contour tracing processing. Assuming that the points on the character contour shown in FIG. 3 are the external contact points 17 in the four directions as P4 and the external contact points 18 in the eight directions as P8, samples are sampled at equal intervals between P4 and P8, and the characteristics shown in 19, 20, and 21 are obtained. Points f1, f2,
..., obtain fn/2. Similarly, samples are taken at equal intervals between P8 and P4, and feature points f(n
/2) Obtain +1,..., fn-1, fn.

For each of the obtained feature points f1, . . . , fn, the coordinate, direction, and angle features are extracted as features. FIG. 4 shows the extracted feature amounts. For example, for the feature point fi shown in 25, the x coordinate pi (1) shown in 26, the y coordinate pi (2) shown in 27, the x component in the tangential direction of fi shown in 30, pi (3) in 28, y The component 29 pi (
4), fi-1 adjacent to the feature point fi shown in 31,
Find the angle pi(5) shown in 34 between fi+1 and find the feature vector of the feature point fi.

[Math 2]

[0016]

[0017] is generated. The feature vector x for one character as a whole is

[Math 3]

[0018]

It is generated by

The principal component dictionary section 3 in FIG. 1 is obtained as follows. A collection of feature vectors of learning patterns belonging to class ck

[Math 4]

[0021]

Regarding [0022]

[Math 5]

[0023]

0024

[Math 6]

[0025]

[0026]

[Math 7]

[0027]

It is determined by: Principal component analysis solves the eigenvalue problem of number 8.

[Math. 8]

[0029]

[0030] Rearrange the corresponding eigenvectors U so that the eigenvalues λ1≧λ2≧…≧λM

[Math. 9]

[0031]

[0032] is selected as the principal component axis. The principal component dictionary unit 3 calculates the average vector μk and principal component axis vectors uk1, uk2, ..., u for all classes c={ck}.
kN. A subspace formed by principal component axis vectors uk1, .

Next, the projection distance calculating section 7 in FIG. 1 performs the following processing. The unknown pattern feature vector for the unknown pattern is calculated using the feature vector shown in Equation 3.

[Math. 10]

[0034]

Then, the projection distance dk(z) for the principal component dictionary of class ck is

[Math. 11]

[0036]

It is determined by: The projection distance of each class {ck} to the principal component dictionary is calculated, and the unknown pattern feature vector z is determined to be ck', which minimizes the distance shown in Equation 12.

[0038]

[Math. 12]

[0039]

FIG. 5 shows the projection distance dα(z) when k=α.
I will explain. Set of learning patterns of class cα {xα
}, find the average vector μα shown in 36, perform principal component analysis centering on μα, and calculate 38 from the orthogonal complementary space of the first principal component axis uα1 and uα1 with the largest variance of the data shown in 37.
A second principal component axis uα2 shown in is obtained. The projection distance 41 of the unknown pattern feature vector z to the principal component dictionary plane of the class cα is

[Math. 13]

[0041]

It is determined by: The first term on the right side of Equation 13 is the Euclidean distance between the unknown pattern feature vector z shown in 39 and the average vector μα of class cα, and the second term on the right side is the Euclidean distance between the perpendicular to the plane of z shown in 41 and the distance of class cα shown in 35. The intersection point 42 with the principal component dictionary plane and the average vector μα
, and dα(z) is the distance from the perpendicular line drawn from z to the principal component dictionary plane 35 shown in 41.

Similarly, for class cβ, the average vector 44 is μβ, the first principal component axis 45 is uβ1, and the second principal component axis 46 is uβ2. unknown pattern feature vector z
The projection distance of class cβ to the principal component dictionary plane is 47
teeth

[Math. 14]

[0044]

It is determined by:

The discriminant dictionary section 4 in FIG. 1 is obtained as follows. A set of feature vectors of learning patterns belonging to class cα

[Math. 15]

[0047]

and a set of feature vectors of learning patterns belonging to class cβ

[Math. 16]

[0049]

For [0050], let the average vector of the feature vectors of class cα be μα, and the average vector of the feature vectors of class cβ be μβ, then the covariance matrix Σ of each class
α, Σβ are

[Math. 17]

[0051]

[0052]

[Math. 18]

[0053]

Then, the intra-class covariance matrix ΣW is

[Number 1
9]

[0055]

Here, ωα and ωβ are the probabilities of appearance of patterns of classes cα and cβ.

Next, the average vector μt of the entire two classes
teeth

[Math. 20]

[0058]

The inter-class covariance matrix ΣB is determined by

[
Number 21]

[0060]

[0061]

Transformation matrix A that has the highest ability to linearly separate data sets of M-dimensional feature vectors of both classes
αβ is obtained by solving the eigenvalue problem of Equation 22.

[0063]

[Math. 22]

[0064]

Therefore, in the case of a two-class problem as shown in FIG. 6, since N=1, only aαβ1 can be obtained as the discriminant axis.

In FIG. 6, the feature vectors belonging to class cα

[Math. 23]

[0067]

Let the distribution of 48 be the feature vector belonging to class cβ.

[Math. 24]

[0069]

The distribution of [0070] is shown in 49. Based on Equation 22, the discriminant feature axis aαβ1 having the highest ability to linearly separate the classes cα and cβ is 50.

Next, when the set 48 of feature vectors belonging to the class cα is projected onto the discriminant feature axis aαβ1, the minimum value of the projected values shown at 51 is Vαmin, the maximum value of the projected values shown at 52 is Vαmax, and it belongs to the class cβ. When the set of feature vectors 49 is projected onto the discriminant feature axis aαβ1, 53
Let the minimum value of the projection values shown in 54 be Vβmin, and the maximum value of the projection values shown in 54 be Vβmax. Also, the projection value 55 of the unknown input pattern vector is

[Math. 25]

[0072]

[0073] The distance Dα to the discriminant dictionary of class cα and the distance Dβ to the discriminant dictionary of class cβ are as follows.

[0074]

[Math. 26]

[0075]

[0076]

[Math. 27]

[0077]

The class to which the unknown input pattern vector z belongs is determined as cl' based on Equation 28.

[0079]

[Math. 28]

[0080]

In the example of FIG. 6, Dα (Vz
) and Dβ(Vz) shown in 57 are compared.

[Math. 29]

[0082]

##EQU1## Therefore, the class is determined to be cβ.

The comprehensive determination section 13 in FIG. 1 is controlled based on the results of the projection distance calculation section 7. In the projection distance calculation unit 7, the class with the smallest distance value is cα, and the class with the second largest distance value is cα.
When β, aα(z) and aβ(z
)about

[Math. 30]

[0085]

When the following is satisfied, the class cα is determined. Further, when aβ(z)-aα(z)<δ1, the calculation result of the discriminant distance calculation unit is referred to and the class cl' is determined based on Equation 28 (l'=β in the example of FIG. 6). When all the distance values of the discriminant distance calculation unit are equal, for example, Dα(Vz)=Dβ(V
z), reject processing is performed.

Furthermore, the minimum distance value dα(
z) is

[Math. 31]

[0088]

Reject processing is also performed in the case of [0089].

The judgment logic of the comprehensive judgment section described above is shown in FIG.
Shown below.

The effectiveness of the present invention will be explained with reference to FIG.

Unknown pattern vector z1 as shown in 58
On the other hand, the method based on principal component analysis does not take other classes into consideration, so its ability to identify similar classes is low, and z1
With the projection distance method, it is difficult to identify a pattern such as dα (z1) shown in 59 and dβ (z1) shown in 60, which have almost the same value. However, since the method based on discriminant analysis has a high ability to identify similar classes, a difference occurs between the values of Dα (Vz1) shown in 61 and Dα (Vz2) shown in 62, and it is possible to identify it as belonging to class cα. .

In addition, for a pattern like z2 shown in 63, Dα (Vz) = 0 in the method based on discriminant analysis, and Dβ (Vz) > 0 shown in 64, so cα
In some cases, even a pattern that is far from the distribution of
It is possible to reject if dα(z2)>δ2 as shown in FIG.

[0094]

[Effects of the Invention] As explained above, in the pattern recognition method of the present invention, patterns for which similar classes exist are judged using the discriminant analysis method, which has excellent ability to identify similar patterns, and is not taken into consideration during learning. For such patterns, we have made it possible to check the distance values and reject them using a method based on principal component analysis, which is excellent in describing the overall image of the pattern. Therefore, we have achieved a pattern recognition method with fewer recognition errors and high ability to identify similar classes. In addition, this time we will explain using an example of character recognition, but it can also be easily applied to voice recognition etc. by making the feature pattern into a frequency component or the like.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing a configuration diagram and a process flow of the present invention.

FIG. 2 is a diagram showing samples of feature points.

FIG. 3 is a diagram showing eight directions.

FIG. 4 is a diagram showing feature amounts at a feature point fi.

FIG. 5 is a diagram showing a projection distance of an unknown pattern feature vector z to a principal component dictionary.

FIG. 6 is a diagram showing the distance of an unknown pattern vector z to a discriminant dictionary.

FIG. 7 is a diagram showing determination logic of a comprehensive determination section.

FIG. 8 is an explanatory diagram of the effectiveness of the present invention.

[Explanation of symbols]

1 Pattern input section 2 Feature extraction part 3 Principal component dictionary section 4 Discrimination dictionary section 7 Projection distance calculation section 11 Discrimination distance calculation unit 13　Comprehensive Judgment Department

Claims (1)

[Claims] Claim 1: A pattern recognition device that converts pattern data observed in a pattern input unit into a feature vector in a feature extraction unit, and makes a determination based on a distance value between the feature vector and a recognition dictionary vector. A principal component dictionary section created based on component analysis, a projection distance calculation section that calculates the distance between a feature vector and a principal component dictionary, a discriminant dictionary section created based on discriminant analysis of learning patterns, and a feature vector and discrimination section. A discriminant distance calculation unit that calculates a distance between dictionaries, and a comprehensive judgment unit that performs a comprehensive judgment based on the projection distance value obtained by the projection distance calculation unit and the discriminant distance value obtained by the discriminant distance calculation unit. Characteristic pattern recognition device.