JP3019911B2 - Pattern recognition method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a pattern recognition method for a pattern recognition device such as a character reading device, and more particularly to a pattern recognition method for improving recognition accuracy.

[0002]

2. Description of the Related Art Character recognition will be described as an example. In character recognition, a distance function is often used as an identification function. Examples of the distance function include a Euclidean distance function, a weighted Euclidean distance function, and a secondary discriminant distance function. Also,
A distance function is often used as a correction function, and there is a discriminant function obtained by performing a discriminant analysis.

Since most of the distance function and the correction function are symmetric functions, the maximum effect is obtained when the feature vector extracted from the input pattern has a symmetric distribution. However, the feature vectors extracted from the input pattern are not necessarily symmetric. Therefore, the distribution of the feature vector cannot be accurately described, and the recognition accuracy is limited.

[0004]

SUMMARY OF THE INVENTION The present invention solves the above problems, spatially transforms a feature vector and approximates the distribution of the feature vector to a symmetric distribution, thereby increasing the accuracy with which the distance function describes the distribution. An object is to improve recognition accuracy.

It is another object of the present invention to reduce the amount of calculation without reducing the recognition accuracy by compressing a feature dimension having a large distribution of feature vectors after spatial transformation and having a small contribution to identification accuracy.

[0006]

According to the present invention, a linear combination of features is performed by principal component analysis of a feature vector of an input pattern .
It intends line the space conversion that. As a result, the distance value is determined after the distribution of the feature vectors is approximated to the symmetric distribution.

Further, the amount of calculation is reduced by performing principal component analysis and using only feature dimensions having a small distribution of feature vectors after spatial transformation and having a large contribution to the accuracy of discrimination for recognition.

[0008]

When the distance value is obtained by using the distance function, the distance function can accurately describe the distribution of the feature vector, so that a remarkable improvement in recognition accuracy can be expected. In addition, by using only feature dimensions that have a large contribution to recognition accuracy for recognition, and not using feature dimensions that have a small contribution for recognition, it is possible to reduce the identification dimension, the discrimination dictionary, and the feature dimension for comparing feature vectors with the discrimination dictionary. Therefore, the amount of calculation can be reduced.

[0009]

FIG. 1 is a diagram showing an embodiment of the present invention. In the figure, 1 is a pre-process, 2 is a feature extraction process, 3 is a space conversion process, 4 is a space conversion parameter storage unit, 5 is a distance calculation process, 6 is an identification dictionary, 7 is a discriminant value calculation process, and 8 is a discrimination dictionary. , 9 represent a class determination process.

For the input pattern, first, preprocessing 1
Then, the center of gravity of the pattern is moved so as to come to the center of the predetermined pattern size, and then the size is normalized by the moment of the pattern. Further, the noise on the pattern is removed by applying a noise filter.

Next, a feature vector used for identification in feature extraction processing 2 is extracted. Examples of feature vectors are described in the literature (IEEE Vol.J 76-D-II No.9 PP.1851-1859, Kawatani;
"Handwritten digit recognition by learning distance functions").

In the spatial transformation process 3, spatial transformation of the value of the feature vector extracted in the feature extraction process 2 is performed based on the following equation. x _m “= φ _m (x′−MX) / {sqrt (λ _m )} where the eigenvalues and eigenvectors are the eigenvalues and eigenvectors of the covariance matrix of the feature vector of the training pattern, and these are the spatial transformation parameter storages. The ij component of the covariance matrix of the feature vector of the training pattern is obtained as follows.

Σ _ij = Σ (x _i −MX _i ) (x _j −MX _j ) / (N−1) where x ′; input pattern feature vector x; training pattern feature vector MX; average vector of x x _m "; m component of spatially transformed feature vector N; number of training patterns σ _ij ; ij component of x covariance matrix λ _m ; m-th eigenvalue of x covariance matrix φ _m ; covariance of x In the distance calculation process 5, the distance value d between the feature vector of the input pattern and the feature vector of the reference pattern is obtained for each class to be read, using the distance function D (x ″).

In the discriminant value calculation process 7, the discriminant function F
The discriminant value f is obtained for each class using (x "). The discriminant function F (x") of each class is a negative value if the input pattern belongs to the class, and a positive value if the input pattern does not belong to the class. Designed to have That is, F (x ″) is a function that reflects the difference between each class and other classes.

In a class determination process 9, g = d + γ · f is determined for each class, the class giving the smallest value of g is selected, and the class to which the input pattern belongs is determined. Here, γ is a predetermined constant. Here, what kind of function is used as the distance function D (x ″) and how to determine the discriminant function F (x ″) are issues.

In the present invention, a linear discriminant analysis is performed between a rival pattern set obtained when identification is performed using D (x ″) and a pattern set of each class, and
(X ") is determined. Hereinafter, an example in which a weighted Euclidean distance is used as D (x") will be described.

The weighted Euclidean distance can be written as: D (x ″) = Σω _m (x ″ _m −μ _m ) ² where x ″ = (x ″ ₁ ,..., X ″ _M ) ^t is an input feature vector, and μ = (μ ₁ ,..., Μ _M ) ^t is a reference pattern vector, ω = (ω ₁ ,..., ω _M ) ^t is a weight vector, M is the number of dimensions of a feature, t is transpose, and Σ is m = 1.
To M. Here, if ω _{1 to} ω _M is 1, D (x ″) is the Euclidean distance.
Stores a reference pattern vector and a weight vector of each class. The discriminant function F (x ″) includes variables y _m , y _{M + m}
Is defined as follows.

Y _m = (x ″ _m −μ _m ) ² y _{M + m} = (x ″ _m −μ _m ) That is, each element of the reference pattern vector is subtracted from each element of the training pattern feature vector as a variable. Both the object and its square are used as variables.

[0019] F (x ") is defined as follows. F (x") = Σa m y m + Σb m y M + m + c = Σa m (x "m -μ m) 2 + Σb m (x _"m -μ _m)
+ C (sigma is the sum of the m = 1 to M), however, x "is negative when belonging to the target class, as will be positive when belonging to rival pattern set _{{a m}, {b m} }, the c The codes are determined, and {a _m }, {b _m }, c are stored for each class in the discrimination dictionary 8. A specific method of obtaining {a _m }, {b _m }, c will be described later. .

Although the weighted Euclidean distance has been described above, the same concept can be applied to other distance functions, such as a city block distance. FIG. 2 shows that {a _m },
It shows details of how to find {b _m }, c.

First, in step 11, a training pattern is prepared, and in step 12, the preprocessing described in preprocessing 1 of FIG. 1 is performed. Next, at step 13, the feature extraction described in the feature extraction process 2 of FIG. 1 is performed. At step 14, the space conversion process 3 of FIG.
The range correction and the space conversion described in the above are performed. Step 15
In step 16, recognition is performed using the original distance function D (x ″). In step 16, a rival pattern is edited based on the recognition result. Each rival pattern belongs to a class other than the class of interest for each class. A pattern that is erroneously recognized as the target class and a pattern that is likely to be erroneously recognized are selected from the patterns. They can be obtained by arranging them in order and selecting a certain number of them.

Next, linear discriminant analysis is performed in step 17, and this procedure is as follows. First, the vector y
If the covariance matrix of the class of _{interest for ==} (y ₁ ,..., Y _M , y _{M + 1} ,..., Y _2M ) is S _S and the covariance matrix of the rival pattern is S _R , the matrix S is S = q obtained by _{S S S + q R S R} . q _S and q _R are both set to 0.5 and a ratio of the number of patterns [q _S = number of patterns in the class of interest / (number of patterns in the class of interest + number of rivals), q _R = 1− q _S ] is known and can be calculated using either of them.

Next, a = (a ₁ ,..., A _M , b ₁ ,.
and b _M) ^t, the mean vector y _S of given class, and rival pattern, with y _R, a and ^{c, a = S -1 (y} R -y S) c = (1/2) a t determined by (y _R + y _S).

Next, in steps 18 and 19, the optimum γ is determined. This uses all training patterns, and the value d of the distance function D (x ″) and the value f of the discriminant function F (x ″) are used for each class.
From the above, g = d + γ · f is obtained, and when the class of the input pattern is determined by selecting the class that gives the smallest value of g, the value is obtained by selecting γ with the highest recognition rate for the training pattern. be able to. When the processing as described above is repeatedly performed, the difference from the previous recognition rate is compared in step 20, and if the difference is small, the process is terminated. If the difference is large, in step 20 ', a pattern which has been correctly read up to the previous time and which has been misread for the first time is newly added to the rival pattern set, and the processing from linear discriminant analysis is repeated.

FIG. 3 is a diagram showing a second embodiment of the present invention. 21 is a pre-processing, 22 is a feature extraction process, 23 is a space conversion process, 24 is a space conversion parameter storage unit, 25 is a distance calculation process, 26 is an identification discrimination dictionary, and 27 is a class determination process.

In this embodiment, an identification discrimination dictionary 26 having information obtained by superimposing the contents of the identification dictionary 6 and the contents of the discrimination dictionary 8 shown in FIG. 1 is used. The processing up to the space conversion processing 23 is the same as the example in FIG. In the distance calculation processing 25, a value G (x ″) obtained by adding the value of the distance function D (x ″) and the value of the discriminant function F (x ″) is obtained for each class. , G (x ″) is determined based on the value of the input pattern. As an example of a method of creating the contents of the identification discrimination dictionary 26 in this case, there is a method described in Japanese Patent Application No. 4-343686.

For example, in the case of a weighted Euclidean distance, G (x ″) = D (x ″) + γ · F (x ″) = Σω _m ′ (x ″ _m −μ _m ′) ² + d where ω _m ′ _{= ω m + γa m μ m} '= μ m - (1/2) γb m / ω m' d = γc- (1/4) is ^{_{Σ (γb m) 2 / ω}} m ', the identification determination dictionary 26 Is μ ′ = (μ
_{1 ', ..., μ M'} ) t, ω '= (ω 1', ..., ω M ')
^t and d are stored. Note that Σ is the sum of m = 1 to M.

FIG. 4 is a diagram showing a third embodiment of the present invention. 31 is a pre-process, 32 is a feature extraction process, 33 is a space conversion process, 34 is a space conversion parameter storage unit, 35 is a dimension compression parameter storage unit, 36 is a distance calculation process, 37 is an identification discrimination dictionary, and 38 is a class determination process. Represents

In this embodiment, an identification discrimination dictionary 37 having information obtained by superimposing the contents of the identification dictionary 6 and the contents of the discrimination dictionary 8 shown in FIG. 1 is used. The process up to the feature extraction process 32 is the same as the example of FIG. After the feature extraction processing, the spatial conversion of the feature vector is performed only for the dimensions stored in the dimension compression parameter storage unit 35.

The dimension compression parameter storage unit 35 stores in advance
A dimension number in which the eigenvalue of the covariance matrix of the feature vector after the range correction of the training pattern is a value equal to or less than a certain value is stored. This constant value is determined within a range where the recognition accuracy of the training pattern can be maintained.

The processing after the distance calculation processing 36 is the same as in the example of FIG.

[0032]

As described above, according to the present invention,
Since the distribution of each feature vector can be accurately estimated, the recognition accuracy can be significantly improved.

Further, by performing dimension compression of the feature vector, it is possible to reduce the amount of calculation without impairing the recognition accuracy.

[Brief description of the drawings]

FIG. 1 is a diagram showing an embodiment of the present invention.

FIG. 2 is a diagram showing a procedure for obtaining a discriminant function.

FIG. 3 is a diagram showing a second embodiment of the present invention.

FIG. 4 is a diagram showing a third embodiment of the present invention.

[Explanation of symbols]

 Reference Signs List 1 preprocessing 2 feature extraction processing 3 space conversion processing 4 space conversion parameter storage unit 5 distance calculation processing 6 identification dictionary 7 discrimination value calculation processing 8 discrimination dictionary 9 class determination processing 21 preprocessing 22 feature extraction processing 23 space conversion processing 24 space conversion Parameter storage unit 25 Distance calculation processing 26 Identification discrimination dictionary 27 Class determination processing 31 Preprocessing 32 Feature extraction processing 33 Spatial conversion processing 34 Space conversion parameter storage unit 35 Dimensional compression parameter storage unit 36 Distance calculation processing 37 Identification discrimination dictionary 38 Class determination processing

Continuation of front page (56) References JP-A-6-195517 (JP, A) JP-A-5-324910 (JP, A) JP-A-4-69780 (JP, A) (58) Fields investigated (Int) .Cl. ⁷ , DB name) G06K 9/62 640

Claims (4)

(57) [Claims] 1. An identification distance obtained by collating a feature vector extracted from an input pattern with an identification dictionary including information on feature vectors of one or more reference patterns for each class based on an identification function. And a step of recognizing a training pattern in advance using the identification dictionary to obtain an erroneous or erroneous error pattern set, and obtaining the error pattern set or a pattern set belonging to a class of interest, or A step of obtaining a correction distance obtained by comparing a correction dictionary having information on one or more sets of correct reading pattern sets with a feature vector extracted from the input pattern based on a correction function; Determining the class of the input pattern based on a value obtained using one or both of the identification distance and the correction distance In the pattern recognition method having, in the above case one or both of said correction function and identification function is a symmetric function, the distribution of feature vectors extracted from the input pattern is characterized to be symmetrical linear
A spatial transformation step of performing a spatial transformation by coupling; using a transformed feature vector generated by the spatial transformation step instead of a feature vector extracted from the input pattern; A pattern recognition method comprising: determining a class to which the input pattern belongs by comparing the input pattern with a feature vector. 2. An identification distance obtained by comparing a feature vector extracted from an input pattern with an identification dictionary including information on feature vectors of one or more reference patterns for each class, and an identification distance of the input pattern. Recognize the feature vector and the training pattern in advance using the identification dictionary,
Alternatively, an error pattern set that is likely to be erroneous is obtained, and the error pattern set is obtained by collating with a modified dictionary having information on one or more of the error pattern set, the pattern set belonging to the class of interest, or the correct reading pattern set. A correction identification distance corresponding to a value obtained by using one or both of the correction distances obtained by the correction pattern is obtained by correcting the feature vector of the input pattern, the identification dictionary, and the correction identification dictionary obtained by superimposing the correction dictionary. In a pattern recognition method having a step of determining the class of the input pattern based on the modified identification distance, the pattern is obtained by matching based on a distance function. spatial distribution of feature vectors extracted from the pattern performs spatial transformation by linear combination of features to be symmetrical variant Using the transformed feature vector generated by the spatial transformation process in place of the feature vector extracted from the input pattern, collating the modified identification dictionary after the spatial transformation process with the transformed feature vector. A pattern recognition method, wherein a class to which the input pattern belongs is determined. 3. The pattern recognition method according to claim 1 or 2, wherein for each class, a new pattern that is erroneous to the class or that is likely to be erroneous does not belong to the class is added to the error pattern set. A pattern recognition method characterized by repeatedly creating or updating a correction dictionary or a correction identification dictionary. 4. The pattern recognition method according to claim 1, wherein feature dimension compression is performed by principal component analysis.