Method of Generating Dictionary for Pattern Recognition and Pattern Recognition Method Using the Same

The present invention relates to a pattern recognition method or scheme using a dictionary in various types of pattern recognition, including character reading and, more particularly, to a method of composing a dictionary for use in the case of employing a distance function as a discriminant function and a pattern recognition method using the dictionary.

A brief description will be given of the most commonly used procedure for handprinted or handwritten character recognition which is a typical example of pattern recognition. For each of characters of all classes (referred to also as categories) which are likely to be used (0 through 9 when the characters to be recognized are numerals, for example), a number of handprinted characters are gathered or collected as learning character patterns (also called training patterns or learning samples) and features of respective training patterns in each class are extracted and each expressed as an M-dimensional vector x=(x.sub.1, . . . , x.sub.M). Next, calculations are made of, for example, means .mu..sub.1 =x.sub.1, .mu..sub.2 =x.sub.2, . . . , .mu..sub.M =x.sub.M of corresponding components of the feature vectors of all training patterns in each class, and the average vectors .mu.=.mu..sub.1, . . . , .mu..sub.M) thus obtained are used as reference pattern vectors. In this way, such a reference pattern vector is predetermined for every class of characters.

To recognize an arbitrary handwritten character pattern, its feature vector x=(x.sub.1, . . . , x.sub.M) is obtained first, then the distance between the feature vector x and the reference pattern vector .mu. of every class to be recognized is calculated using a distance function as a discriminant function, and a character of the class closest to the feature vector x is selected and output as a recognition result for the input pattern. A variety of parameters have been proposed to express features of character patterns, but as long as they are represented by vectors, the principles of the present invention have nothing to do with the kinds of feature parameters used and the way of determining them. The present invention rather concerns how the distance function which defines the distance between the feature vector of the input pattern and the reference pattern vector should be modified to increase the character recognition accuracy.

The character recognition utilizes the distance function as the discriminant function in many cases. There are known, as distance functions, a Euclidean distance, a weighted Euclidean distance, a quadratic discriminant function (or Bayesian discriminant function), and a modified quadratic discriminant function and a projected distance, for instance. To provide increased recognition accuracy in the case of using the distance function, it is customary to faithfully represent the distribution of features (x.sub.1, . . . , x.sub.M) in each class of the characters to be read. In contrast to the Euclidean distance, the weighted Euclidean distance utilizes, as the weight, the inverse of the variance of corresponding feature components of the respective classes, i.e., the corresponding components of the feature vectors. The weighted Euclidean distance provides higher recognition accuracy than does the Euclidean distance. The quadratic discriminant function, the modified quadratic discriminant function and the projected distance utilize a covariance matrix of features in each class and its eigenvector and eigenvalue for discrimination, and hence provide high accuracy even if the features are correlated. However, these methods have technical limitations and cannot be expected to achieve higher accuracy.

Another important viewpoint to increase the accuracy of character recognition is to emphasize differences of each class from the others. One possible method that has been proposed to implement it is to modify the distance between the input pattern and each class, which is obtained when the discrimination of the input pattern is made using the distance function, so that the distance between the input pattern and the class to which the input pattern belongs is short, whereas the distance between the input pattern and the class to which it does not belong is long.

To make such a modification to the distance between the input pattern and each class, it is necessary to employ a function which produces negative values for patterns belonging to the class concerned and positive values for patterns not belonging to the class. To this end, it is possible to use such a method as disclosed in a literature [Kawatani, et al., "Improvement of Discriminant Function by Superposition of Distance Function and Linear Discriminant Function," '89 Autumn National Conference of the Institute of Electronics, Information and Communication Engineers of Japan, D-166, pp. 6-166 (1989)].

According to this method, the weighted Euclidean distance, the quadratic discriminant function or the like is used as the distance function,and a pattern set of each noticed class and a misread or nearly-misread pattern set (a rival pattern set) for the noticed class which are obtained by the discrimination of training patterns with the original distance function, are subjected to a discriminant analysis using either the difference between each component of the feature vector of the training pattern and the corresponding component of the reference pattern vector or the square of the difference as a variable, whereby an intended function (called a discriminant function) is obtained. In the actual discrimination, the distance value of each class obtained with the original distance function is added to a value obtained with the discriminant function for each class, and the resulting added value is used to determine the class of the input pattern. A method for obtaining the rival patterns will be described later.

In this conventional method, the value obtained with the discriminant function for each class is added to each distance obtained with the original distance function to thereby produce the same effect as that by the modification or correction of the weight vector of the original distance function or the reference pattern vector. That is, when the difference between each component of the feature vector of the training pattern and the corresponding component of the reference pattern vector is used as a variable in the discriminant analysis, the reference pattern vector is corrected, and when the square of the difference is used, the weight vector is corrected.

With this method, however, the weight vector and the reference pattern vector are corrected independently of each other; therefore, they cannot be corrected in the optimum combination--this imposes limitations on improvement of the recognition capability.

It is therefore an object of the present invention to provide a method of generating or composing a dictionary for pattern recognition which obviates the above-mentioned defect of the prior art and permits improvement of the recognition accuracy by simultaneous and optimum correction of reference pattern vectors, weight vectors or constant terms appearing in the original distance function.

Another object of the present invention is to provide a pattern recognition method using the above-mentioned dictionary.

According to the present invention, a training pattern set of each noticed class and a misread or nearly-misread pattern set (hereinafter referred to as a rival pattern set) for the noticed class obtained as the result of the recognition of training patterns with the original distance function, are subjected to a discriminant analysis using both of the difference between each component of the feature vector of the training pattern and the corresponding component of the feature vector of the reference pattern and the square of the difference as variables, or using, as a variable, each component of a vector which is provided by projecting in a subspace a vector obtained by subtracting the feature vector of the reference pattern stored in the dictionary from the feature vector of the training pattern, and the square of the said each component. By this, an intended discriminant function is obtained.

By using the sum of the value obtained with the original distance function for each class and the value obtained with the discriminant function for each class in the actual recognition, the reference pattern vectors, weight vectors and constant terms appearing in the original distance function can be corrected simultaneously and optimally--this would substantially increase the recognition accuracy.

FIG. 1 is a block diagram illustrating an embodiment of the present invention for generating a dictionary for pattern recognition and for pattern recognition using it;

FIG. 2 is a schematic diagram showing the relationship between a training pattern set and a rival pattern set;

FIG. 3 is a flow chart showing the procedure for generating the dictionary for pattern recognition use;

FIG. 4 is a graph showing the relationship between a coupling coefficient .gamma. and the recognition rate;

FIG. 5 is a block diagram illustrating another embodiment of the present invention for generating the dictionary for pattern recognition use and for pattern recognition;

FIG. 6 is a flow chart showing the procedure for generating the dictionary for repetitive or iterative learning;

FIG. 7 is a flow chart showing the procedure for determining .gamma..sub.A in step S5 in FIG. 6;

FIG. 8 is a flow chart showing the procedure for generating another dictionary for repetitive learning;

FIG. 9 is a flow chart showing the procedure for determining .gamma..sub.B in step S7 in FIG. 8; and

FIG. 10 is a flow chart illustrating a modified form of the FIG. 6 or 8 embodiment.

FIG. 1 is a block diagram for explaining the operation of an embodiment of the present invention. Reference numeral 11 denotes a preprocessing part, 12 a feature extracting part, 13 a distance calculating part, 14 an original dictionary, 15 a discriminant value calculating part, 16 a discriminant dictionary, 17 a class deciding part, 18 a rival pattern holding part and 19 a feature vector holding part.

The recognition of an input pattern begins with preprocessing by the preprocessing part 11 to normalize the position and magnitude of the pattern and remove therefrom noise, after which the features for use in recognition are extracted as a feature vector x=(x.sub.1, . . . , x.sub.M).sup.t by the feature extracting part 12, t indicating transposition. In the distance calculating part 13, a predetermined desired original distance function D(x) is used to obtain the distance between the feature vector of the input pattern to be recognized and each reference pattern vector of all classes read out of the original dictionary 14. In the discriminant value calculating part 15, the value of a discriminant function F(x), which is provided when a learned distance function G(x) is represented by the following equation, is calculated for each class.

The discriminant function F(x) of each class is prestored in the discriminant dictionary 16 and is designed to have a negative or positive value, depending on whether the input pattern belongs to the class or not. Hence, the discriminant function F(x) of each class reflects the difference between the class and the others.

In the class determining part 17, the value of the learned distance function G(x) of Eq. (1) is calculated for each class and the class that provides the smallest value is selected and determined as the class to which the input pattern belongs. Incidentally, the coupling coefficient .gamma. is a predetermined constant. Here, what kind of function can be used as the original distance function D(x) and how the discriminant function F(x) is determined are problems to be solved.

Now, let it be assumed that when patterns were discriminated using a proper distance function, a pattern P belonging to a class n is misread or misclassified as belonging to another class k and a pattern Q belonging to the class k as belonging to the class n as shown in FIG. 2. In this instance, letting the reference pattern vectors of the classes k and n be represented by .mu..sub.k and .mu..sub.n, the distances between the feature vector of the pattern P and the reference pattern vectors .mu..sub.k and .mu..sub.n by D.sub.Pk and D.sub.Pn and the distances between the feature vector of the pattern Q and the reference vectors .mu..sub.k and .mu..sub.n by D.sub.Qk and D.sub.Qn, the distances D.sub.Pk and D.sub.Qn are smaller than those D.sub.Pn and D.sub.Qk, respectively; hence, the patterns P and Q are misclassified. To relieve the misread patterns P and Q, it is necessary to correct or modify the distances so that D.sub.Pk and D.sub.Qn become larger and D.sub.Pn and D.sub.Qk smaller. To this end, functions F.sub.k and F.sub.n, which have values negative for patterns belonging to the noticed class and positive for patterns not belonging to the noticed class, are calculated for the classes k and n as shown in FIG. 2 and such functions are added to the respective distances.

According to the present invention, the discriminant function is obtained by making a discriminant analysis between a set of patterns of each class and a set of patterns either misclassified or nearly misclassified as belonging to the class (which will hereinafter be referred to as a rival pattern set and the nearly misclassified patterns as near-miss patterns). A concrete description will be given of the case where the weighted Euclidean distance, polynomial discriminant function (Bayesian discriminant function), modified quadratic discriminant function (and the projected distance) or the like is used as the original distance function D(x). In the following description, x=(x.sub.1, . . . , x.sub.M).sup.t represents the feature vector of each pattern, .mu.=(.mu..sub.1, . . . , .mu..sub.M).sup.t represents the reference pattern vector of each class, and .omega.=(.omega..sub.1, . . . , .omega..sub.M).sup.t is the inverse of the variance of the feature vector of a training pattern in each class and represents a weight vector. The feature vectors of given training patterns are held in the feature vector holding part 19 for each class. t indicates a transposition and M the number of dimensions (or the number of components) of the feature vectors. Let D(x), F(x) and G(x) represent the original distance function, the discriminant function and the learning distance function, respectively. Furthermore, let the pattern set of the notice class be represented by .OMEGA. and the rival pattern set when discriminated with the original distance function D(x) be represented by .OMEGA.', and let it be assumed that the discriminant analysis is made between the pattern set .OMEGA. and the rival pattern set .OMEGA.'. In the following description, the reference pattern vector, the weight vector, coefficients and a constant term, except the variable x, will be generically called parameters.

(1) Weighted Euclidean distance

The weighted Euclidean distance is expressed by the following expression.

where

.SIGMA. represents ##EQU1## If all the weights .omega..sub.1, . . . , .omega..sub.M are 1's, D(x) is the Euclidean distance. In the original dictionary 14 there are stored the reference pattern vector .mu. and weight vector .omega. of each class. According to the present invention, the discriminant function F(x) is obtained, with two variables y.sub.m and y.sub.m+M defined as follows:

That is, both the difference between each component x.sub.m of the feature vector of the training pattern and the corresponding component .mu..sub.m of the reference pattern vector and the square of the difference are used as variables. Hence, the discriminant function F(x) is defined as follows: ##EQU2## where .SIGMA. represents ##EQU3## In this instance, the signs of the coefficient parameters {a.sub.m }, {b.sub.m } and c are determined so that the value of the discriminant function F(x) is negative or positive depending on whether x belongs to the noticed class or the rival pattern set. In the discriminant dictionary 16, the coefficient parameters {a.sub.m }, {b.sub.m } and c are stored for each class. A concrete method for obtaining these coefficients will be described later on.

(2) Polynomial discriminant function (Bayesian discriminant function)

Letting S represent a covariance matrix of feature vectors in the noticed class and .phi..sub.m and .lambda..sub.m represent the m-th eigenvector and eigenvalue of the covariance matrix S, the Bayesian discriminant function D(x) can be expressed as follows: ##EQU4## where .SIGMA. represents ##EQU5## In this case, .mu., (.phi..sub.1, . . . , .phi..sub.M), (.lambda..sub.1, . . . , .lambda..sub.M) and 1n.vertline.S.vertline. are stored in the original dictionary 14 for each class. If the constant term 1n.vertline.S.vertline. is neglected, then a Mahalanobis distance will be provided. The discriminant function F(x) is calculated, with the two variables y.sub.m and y.sub.M+m defined as follows:

That is, each component of a vector, which is obtained by projecting a vector of the difference between the feature vector of the training pattern and the reference pattern vector into a subspace using the vector (.phi..sub.1, . . . , .phi..sub.M), and the square of the above-said component are used as variables. The function F(x) is given by the following equation.

where

.SIGMA. represents ##EQU6## In the discriminant dictionary 16, the parameters {a.sub.m }, {b.sub.m } and c are stored for each class.

(3) Modified quadratic discriminant function and projected distance In this instance, D(x) is expressed as follows:

where

.SIGMA. represents ##EQU7##

In the case of the modified quadratic discriminant function, T is the order at which the rate of cumulative contribution of eigenvalue exceeds a predetermined constant .delta. for the first time, and the eigenvalue above the (T+1)-th order is expressed by .lambda..sub.T+1. Moreover,

where the first II in the brackets is the product of .lambda. from u=1 to u=T and the second II is the product of .lambda. from u=T+1 to u=M. In the original dictionary 14, the value of T, the parameters .mu., (.phi..sub.1, . . . , .phi..sub.T), (.lambda..sub.1, . . . , .lambda..sub.T+1) and d are stored for each class. In the case where T is a predetermined constant and .alpha.=1, .omega..sub.u =1 and d=0, the distance is called "projected distance".

In the case of the modified quadratic discriminant function and the projected distance, the discriminant function F(x) is calculated after defining two variables y.sub.u and y.sub.T+u as follows:

where:

u.ltoreq.T

The discriminant function F(x) is given as follows:

wherein

.SIGMA. represents ##EQU8## In the discriminant dictionary 16, the parameters {a.sub.u }, {b.sub.u } and c are stored for each class.

The above description has been given of the weighted Euclidean distance, the quadratic discriminant function, the Mahalanobis distance, the modified quadratic discriminant function and the projected distance, and the concept of the present invention is similarly applicable to other distance functions, for instance, a city block distance.

FIG. 3 shows the procedure for obtaining the learned distance function G(x) by determining the coefficient parameters {a.sub.m }, {b.sub.m } and c of respective variables in the discriminant function F(x) for each class and determining the coupling coefficient .gamma. of the discriminant function F(x) for the original distance function D(x). This procedure is common to the aforementioned weighted Euclidean distance, the quadratic discriminant function and the modified quadratic discriminant function.

The procedure begins with step S1 wherein a number of training patterns are prepared for every class and their feature vectors are extracted and then stored in the feature vector holding part 19 for each class. In step S2 the mean of the feature vectors of the training patterns of each class is extracted as the reference pattern vector and the training patterns of all the classes are each recognized or classified using the original distance function D(x). That is, the distance between the feature vector of each training pattern and the reference pattern vector of each class is calculated using the original distance function D(x) and the class closest to the feature vector is regarded as a class to which the training pattern belongs. In step S3 rival patterns for each class are compiled on the basis of the classified results of all the training patterns. The rival patterns are obtained by selecting for each noticed class, patterns misclassified and nearly misclassified as belonging to the noticed class although they belong to the other classes. The near-miss patterns can be obtained by selecting those patterns belonging to classes other than the noticed one and correctly classified as belonging to their classes for which the differences between the distance from the reference pattern vector of the noticed class and the distance from the reference pattern vectors of the classes to which the patterns belong are within a predetermined value, or by selecting a predetermined number of patterns in increasing order of the difference between the distance from the reference pattern vector of the noticed class and the distance from the reference pattern vector of each class to which the patterns belong. That is, the near-miss pattern is a pattern which is correctly classified but is very likely to be misclassified as belonging to the currently notice class in the event of a slight change in the distance between the noticed class and the class to which the pattern belongs, because there is substantially no difference between the distance from the former and the distance from the latter. The number of near-miss patterns for each class is chosen to be, for instance, about three times larger than the number of misread patterns for the class. The rival pattern set thus obtained for each class is stored in the rival pattern holding part 18.

Next, in step S4 a discriminant analysis is made between all training patterns of each class and the rival patterns of the corresponding set to thereby determine the coefficient parameters {a.sub.m }, {b.sub.m } and c of the discriminant function F(x). This function is determined following the procedure described below. Now, let S.sub.s represent a covariance matrix concerning a vector y=(y.sub.1, . . . , y.sub.M, y.sub.M+1, . . . , y.sub.2M) which uses, as its components, the aforementioned two coefficients y.sub.m and y.sub.M=m of a pattern set (letting the number of patterns which form the set be represented by n.sub.s) belonging to each class, and let S.sub.R represent a covariance matrix of the feature vectors of the rival pattern set (letting the number of patterns forming the set be represented by n.sub.R) corresponding to the said each class. A matrix S is calculated by the following equation.

The number of misread patterns that are obtained as rival patterns for each class is originally small and the accuracy of the covariance matrix cannot be increased sufficiently high with the misread patterns alone. In this embodiment, the number of rival patterns is increased by using the near-miss or nearly-misread patterns as well, but according to the principles of the present invention, the nearly-misread patterns need not always be used. q.sub.S and q.sub.R may both be set to 0.5. Next, a vector e=(a.sub.1, . . . , a.sub.M, b.sub.1, . . . , b.sub.M).sup.t is defined which uses the two coefficients a.sub.m and b.sub.m as its components and e and c are calculated by the following equation, using means y.sub.S and y.sub.R of a vector y which uses the coefficients y.sub.m and y.sub.M+m of the pattern set and rival pattern set of each class.

In this way, the discriminant function F(x) in the learned distance function G(x) is determined.

Next, an optimum value of the coupling coefficient .gamma. is determined in step S5. As shown in FIG. 4, according to experiments by the inventors of this application, the recognition rate based on Eq. (1) rapidly increases with an increase in the coupling coefficient .gamma. and reaches the maximum at a certain value of the coefficient .gamma., thereafter gradually decreasing. Based on this fact, the value of the coupling coefficient .gamma. is increased step by step from its initial value 0 by a fixed width and, for each value of the coefficient .gamma., all training patterns of all classes are discriminated on the basis of the learned distance function G(x) of Eq. (1) and the recognition rate for the entire training patterns by the coupling coefficient .gamma. is calculated. In this way, the recognition rate varies with the change in the coupling coefficient .gamma. and the value of the coefficient .gamma. is determined which provides the maximum recognition rate.

In the above-described fashion, the discriminant function F(x) and the coupling coefficient .gamma. are determined, and consequently Eq. (1) is determined which defines the learned distance function G(x). The coefficient parameters {a.sub.m }, {b.sub.m } and c thus determined for each class are written as dictionary data into the discriminant dictionary 16 in correspondence to the class. The value of the coupling coefficient .gamma. is also held in the discriminant dictionary 16. Since the parameters .mu. and .omega. stored in the original dictionary 14 and the parameters .gamma., {a.sub.m }, {b.sub.m } and c in the discriminant dictionary 16 for each class are dictionary data which define the learned distance function G(x) for the class, the dictionaries 14 and 16 which holds these parameters will hereinafter be called, in combination, a dictionary G(x) as well.

To discriminate or recognize an arbitrary input pattern, the input pattern is preprocessed by the preprocessing part 11 to normalize the pattern size, for instance, then the feature vector of the normalized input pattern is extracted in the feature pattern extracting part 12, and in the distance calculating part 13 the weighted Euclidean distance D(x) is calculated by Eq. (2), for instance, using the reference pattern vector .mu. and weight vector .omega. of each class read out of the original dictionary 14. Next, in the discriminant value calculating part 15, the value of the discriminant function F(x) is calculated by Eqs. (3) and (4), using the coupling coefficient .gamma. and the coefficient parameters {a.sub.m }, {b.sub.m } and c of each class read out of the discriminant dictionary 16, and the value of the learned distance function G(x) is calculated using the above-mentioned original distance function D(x) and Eq. (1). After this, in the class determining part 17 that one of the classes which provide the smallest one of the distance values G(x) of all classes thus obtained is selected and the selected class is output as the discriminated result. In the recognition of an arbitrary input pattern, the rival pattern holding parts 18 in FIGS. 1 and 5 are not necessary.

Incidentally, in the case of the weighted Euclidean distance, the learned distance function G(x) of Eq. (1) can be expressed by the following equation, using Eqs. (2) and (4).

where

where

.SIGMA. represents ##EQU9## As is evident from Eqs. (13a), (13b) and (13c), parameters .omega..sub.m ', .mu..sub.m ' and d are constants, which can be precalculated using the function F(x) and the coupling coefficient .gamma. determined for each class as described above. Consequently, the original dictionary 14 and the discriminant dictionary 16 provided separately in FIG. 1 may be replaced by with a learned dictionary 24 as depicted in FIG. 5. In this instance, the parameters .mu.'=(.mu..sub.1 ', . . . , .mu..sub.M ').sup.t, .omega.'=(.omega..sub.1, . . . , .omega..sub.M ').sup.t and d, which define the function G(x) for each class, are prestored as dictionary data in the dictionary 24, and the parameters .mu.', .omega.' and d are read out therefrom for the input pattern to calculate Eq. (13) in a distance calculating part 23. The dictionary 24 will hereinafter be referred to also as G(x).

Similarly, in the case of the quadratic discriminant function (or the Bayesian discriminant function), too, the learned distance function G(x) of Eq. (1) can be expressed by the following equation, using Eqs. (5) and (7) ##EQU10## where:

A: matrix using .phi..sub.m as row elements

where

.SIGMA. represents ##EQU11## Also in this case, the system configuration shown in FIG. 5 can be employed, and the learned dictionary 24 needs only to prestore parameters (.phi..sub.1, . . . , .phi..sub.M), .mu.'=(.mu..sub.1 ', . . . , .mu..sub.M ').sup.t, .omega.'=(.omega..sub.1 ', . . . , .omega..sub.M ').sup.t and d for each class.

In the case of the modified quadratic discriminant function and the projected distance, the learned distance function G(x) of Eq. (1) can be expressed by the following equation on the basis of Eqs. (8) and (10). ##EQU12## where:

otherwise

where

.SIGMA. represents ##EQU13## In this instance, the learned dictionary 24 in FIG. 5 needs only to prestore the parameters .alpha., (.phi..sub.1, . . . , .phi..sub.T), .mu.'=(.mu..sub.1 ', . . . , .mu..sub.M ').sup.t, .omega.'=(.omega..sub.1 ', . . . , .omega..sub.T ').sup.t and d' for each class.

For example, in the case of the weighted Euclidean distance, as is evident from comparison with Eq. (2), Eq. (13) is identical in shape with Eq. (2) except that the constant term d is added and the weight vector .omega..sub.m and the reference pattern vector .mu..sub.m are modified as shown in Eqs. (13a) and (13b), respectively. This means that Eq. (2) is modified to Eq. (13) as the result of learning on the boundary between the training pattern set and the corresponding rival pattern set for each class by a discriminant analysis (the F(x) determining process) between the two pattern sets. Turning back to FIG. 2, this will be described conceptually. In the pattern recognition based on the Eq. (2), the class boundary between training pattern groups .OMEGA..sub.k and .OMEGA..sub.n of two classes, for example, is drawn as indicated by the broken line B1, and consequently, the patterns P and Q in the shaded areas are each misclassified as belonging to the other class. According to the present invention, however, the discriminant function F(x) is determined by a discriminant analysis for each class and is added to the distance function D(x), in consequence of which such a modification or correction as mentioned above is made and the class boundary is corrected accordingly as indicated by the broken line B2, enabling the patterns P and Q to be correctly recognized.

Eq. (13) indicates that further modification could be made by adding a new pattern to the training pattern set and/or rival pattern set of each class and making a discriminant analysis with the function F(x) (i.e. by learning). The same goes for Eq. (14) in the case of the quadratic discriminant function and Eq. (15) in the case of the modified quadratic discriminant function. FIG. 6 shows a flowchart for processing to provide increased recognition rate by correcting the learned distance function G(x) of Eqs. (13), (14) and (15) through learning.

In FIG. 6, steps S1 through S5 are the same as steps S1 through S5 in the FIG. 3 embodiment. In step S2 all training patterns are discriminated with the discriminant function D(x), using the feature vectors of all the training patterns prepared for each class in step S1 and the recognition rate R(0) calculated and is then held. Furthermore, rival patterns are compiled for each class and held in the rival pattern holding part 18. In step S3 the learning repetition count n is set to 1 and in step S4 a discriminant analysis is made between the training pattern set and the rival pattern set for each class, thereby determining the discriminant function F(x) for each class. In the following description, the indication of the variable x of each function will be omitted but instead the repetition count n, which indicates the session count or round number of learning, will be put in parentheses of the function. In step S5 the coupling coefficient .gamma. is determined so that the recognition rate R(n) becomes maximum for all training patterns with the learning distance function G(n)=D+.gamma.F(n), and the value of this coupling coefficient is represented by .gamma..sub.A (n). The procedure for determining this value will be described in detail later on.

In step S6 all the training patterns are recognized with the learned distance function G(n) using the above-noted value .gamma..sub.A (n) determined in step S5 and the recognition rate R(n) based on the discriminated results is held, after which the rival patterns are detected on the basis of the discriminated results and is held. In step S8, in the case of the FIG. 1 system configuration, the coefficient parameters {a.sub.m }, {b.sub.m } and c of the discriminant function F(n) of, for example, Eq. (4) determined in step S4 are stored as dictionary data in the discriminant dictionary 16 in correspondence to each class. In the case of the FIG. 5 system configuration, for example, the parameter vectors .mu.'(n), .omega.'(n) and d, expressed by Eqs. (13a), (13b) and (13c), are calculated for each class, using the coefficient of the discriminant function F(x) determined in step S4 and the value .gamma..sub.A (n) determined in step S5, and the thus calculated parameter vectors are written as dictionary data into the learned dictionary 24 to update its contents.

In step S9 a check is made to see if the recognition rate R(n) obtained in step S6 is higher than the previous recognition rate R(n-1). If so, it means that the learning effect was produced, and it can be expected to further enhance the recognition rate by further learning. Then, the process proceeds to step S10, in which new rival patterns contained in the rival pattern set obtained for each class by the discrimination with the function G(n) in step S7, for instance, are added to the rival pattern (held in the rival pattern holding part 18) obtained for each class by the discrimination with the functions D, G(1), . . . , G(n-1) in step S2. Next, in step S11 the learning repetition count n is incremented by one and the process goes back to step S4, in which the updated rival pattern set is used to make the discriminant analysis again to update the function F(n), after which the same processing is repeated. If it is found in step S9 that the recognition rate R(n) is not higher than that of the previous recognition, no further improvement of the recognition rate can be expected, and consequently, the process proceeds to step S12, in which the parameters defining the previous learned distance function G(n-1) for each class are written into the dictionary 16 in FIG. 1 or dictionary 24 in FIG. 5 and then this session of learning ends. Thus, the value .gamma..sub.A (n-1) in the previous recognition in which the recognition rate was the maximum is stored as an eventual value of the coupling coefficient .gamma..

FIG. 7 shows in detail the procedure for determining the coupling coefficient .gamma..sub.A (hereinafter identified simply as .gamma.) in step S5 in the FIG. 6 flowchart. The number of repetitions of this coupling coefficient determination processing is represented by m. In step S1 the step width .DELTA. of the coupling coefficient .gamma. is set to a predetermined value C1 (C1=100, for instance), and the initial value R'(0) of a temporary recognition rate R'(m) is set to the recognition rate obtained when recognition was made with the original distance function D, and the initial value .gamma.(0) of the coupling coefficient is set to 0. In step S2 the repetition count m is set to m=1; in step S3 the loop count L is set to L=1; and in step S4 the value of the coefficient .gamma.(m) of the current session (m=1) is set to .gamma.(m)=.DELTA..multidot.L. Next, in step S5 it is made sure that the coefficient .gamma.(m) does not reach its upper limit value C3 (10.sup.8, for instance), after which the process proceeds to step S6, in which all patterns are discriminated with the learning distance function G using the coefficient .gamma.(m) and the recognition rate R'(m) is calculated. In step S7 a check is made to see if the recognition rate R'(m) is larger than the previous one R'(m-1). If so, there is the possibility of the maximum recognition rate having not been reached yet. Therefore, in step S8 the loop count L is incremented by 1; in step S9 the repetition count m is also incremented by 1; and in step S10 a check is made to see if the loop count L is smaller than a predetermined count C2 (C2=100, for instance). If it is smaller than C2, then the process returns to step S4. If it is found in step S10 that the loop count L has reached the predetermined count C2, the process goes to step S11, in which the step width .DELTA. is made C2 times larger than that set so far (i.e. .DELTA..rarw..DELTA..multidot.C2). After this, the process returns to step S3, in which the loop count L is reset to 1 and the same processing as described above takes place. When it is found in step S7 that the recognition rate R'(m) is not larger than the previous one, it is judged that the recognition rate will no longer increase, and in step S12 the coupling coefficient .gamma.(m-1) in the previous session is determined as the value of the coupling coefficient .gamma..sub.A and this session ends.

In the FIG. 6 embodiment, when learning is repeated, the coupling coefficient .gamma..sub.A is set which maximizes the recognition rate and the new rival patterns obtained as the result of recognition are added to the previous rival patterns and then the discriminant analysis is made again. It has been found experimentally, however, that the effect of improving the ultimate recognition rate by learning of G(x) would increase when the value of the temporary coupling coefficient .gamma. in step S5 in the course of learning of G(x) is selected to be a little larger than the value .gamma..sub.A which maximizes the recognition rate (hence, the recognition rate in this case would be smaller than the maximum value). This is considered to be for the reasons given below. When the value .gamma..sub.A is determined in step S5 so that the recognition rate become maximum, the number of new rival patterns which are generated in the pattern recognition using the value .gamma..sub.A in step S6 abruptly decreases, and consequently, the number of rival patterns obtained for each class at the end of learning of G(x) is not sufficiently large and the covariance matrix of the rival pattern set cannot be obtained with high accuracy.

By temporarily selecting in step S5 the coupling coefficient .gamma. to be a value .gamma..sub.B larger than that which maximizes the recognition rate so as to heighten the learning effect, it is possible to intentionally increase the number of new rival patterns which are generated in the discrimination processing in step S6. This increases the number of new rival patterns which are added to the rival pattern set in step S10, making it possible to obtain a highly accurate covariance matrix. In FIG. 8 there is shown a flow chart for the procedure of generating a dictionary through learning based on such a concept as mentioned above.

The contents of steps S1 through S6 are the same as those in the FIG. 6 embodiment. Also in this embodiment, the coupling coefficient .gamma..sub.A (n) which maximizes the recognition rate R(n) is determined in step S5 following the procedure depicted in FIG. 7, and in step S6 the recognition rate R(n) with the function G(n) using the coupling coefficient .gamma..sub.A is calculated and is then held. In the next step S7, however, the coupling coefficient .gamma. is selected to be a value larger than that .gamma..sub.A which maximizes the recognition rate, determined in step S5. The criterion for selecting the value of the coupling coefficient .gamma. is such as described below. That is, the coupling coefficient .gamma. is set to the value .gamma..sub.B such that the number of rival patterns of any one of the class exceeds a predetermined value when new rival patterns, which result from the pattern recognition of all patterns on the basis of the function G(n) using the selected coupling coefficient .gamma., are added to the rival pattern set previously obtained with the original distance function D and held in the rival pattern holding part 18.

Next, in step S8 the rival patterns based on the results of the pattern recognition with the coupling coefficient .gamma..sub.B determined in step S7 are held in the rival pattern holding part 18, and in step S9 it is determined if the recognition rate R(n) by the pattern recognition in step S7 is larger than the previous one. If so, the process proceeds to step S10, in which dictionary data based on the function G(n) using the coupling coefficient .gamma..sub.B, that is, the parameters {a.sub.m }, {b.sub.m }, c and .gamma. in the case of the FIG. 1 embodiment, or the parameters .mu.', .omega.' and d' in the case of the FIG. 5 embodiment, are written into the dictionary 16 or 24 (to generate the dictionary G(x)). Then, in step S11 the newly generated rival patterns are added to the corresponding rival pattern set and in step S12 the learning repetition count n is incremented by 1, after which the process returns to step S4. When it is found in step S9 that the current recognition rate R(n) is not larger than the previous rate R(n-1), the process proceeds to step S13, in which dictionary data based on the learned distance function G(n-1) using the value .gamma..sub.A (n-1) Of the coupling coefficient .gamma. which maximizes the previous recognition rate is written into the dictionary 16 or 24 and this session of learning ends.

To sum up, in the FIG. 8 embodiment, flow repeats determining the value .gamma..sub.A of the coupling coefficient .gamma. which maximizes the recognition rate, selecting, as the temporary value .gamma..sub.B for learning the dictionary G, a value larger than that .gamma..sub.A and updating (i.e. learning) the dictionary, and when the recognition rate no longer exceeds the previous value, the repetition of learning ends, followed by the generation of a dictionary based on the learned distance function G(n-1) using the previous value .gamma..sub.A which maximizes the recognition rate, and then flow ends. In the procedure of FIG. 8, the decision step S9 may be shifted to between steps S6 and S7.

FIG. 9 shows an example of the procedure for determining the value .gamma..sub.B larger than that .gamma..sub.A in step S7. In step S1 the initial value of the coupling coefficient .gamma..sub.B is set to .gamma..sub.A, then in step S2 it is made sure that the value .gamma..sub.B is smaller than a predetermined limit value C3, and in step S3 a pattern recognition based on G(n) using the value .gamma..sub.B is performed to obtain rival patterns for each class and the number of new rival patterns is counted. In step S4 a check is made to see if the number of new rival patterns for the class concerned is larger than a predetermined value C4 (400, for instance). When such a class is not found, flow proceeds to step S5, in which the loop count L is incremented by one, and then goes to step S6, in which a check is made to see if the loop count L has reached a predetermined value C2. If the loop count L is smaller than C2, flow goes to step S7, in which the value .gamma..sub.B is set to .DELTA..multidot.L+.gamma..sub.A, and then goes back to step S2, repeating the same processing as mentioned above. Consequently, as long as the loop count L checked in step S6 is smaller than the value C2, the value .gamma..sub.B increases from the value .gamma..sub.A by a fixed width .DELTA. in step S7 upon each iteration of the loop. When it is found in step S6 that the loop count L has reached the value C2, flow proceeds to step S8, in which the value of the width .DELTA. is set to be C2 times larger than the previous value, that is, a value C2.multidot..DELTA. is set as a new step width .DELTA., and goes to step S9, in which the loop count L is reset to L=1. Then, in step S7, the value .gamma..sub.B is set to .gamma..sub.A +.DELTA..multidot.L, after which processing of step S2 and the subsequent steps is repeated. When it is found in step S4 that the number of rival patterns is larger than the value C4 in any class, the value .gamma..sub.B used for the pattern recognition in step S3 is determined as the value .gamma..sub.A that is to be determined in step S7 in FIG. 8.

In the embodiments of FIGS. 6 and 8, the entire training patterns are only initial ones and all the training patterns are subjected to the pattern recognition to obtain the rival pattern set which is used to determine the discriminant function F(x) for each class. In this instance, if the number of rival patterns for each class is not sufficiently large, the accuracy of the covariance matrix of the rival pattern set is low as referred to previously and it is likely to fail to increase the ultimate recognition rate even if learning of the dictionary G(x) is repeated. To avoid this, it is possible to employ such a method as described below. That is, some or all of the rival patterns of each class, obtained in step S3 of FIG. 3 or step S2 of FIG. 6 or 8, are variously modified into various new patterns by making their lines thick or thin if the rival patterns are character patterns, for instance, and these new patterns are discriminated using the original distance function D(x) for each class. Of the discriminated patterns, those judged as rival patterns of each class (hereinafter referred to as pseudo-rival patterns) are added to the rival pattern set of the class, after which the discriminant analysis in step S4 of FIG. 3, 6 or 8 is performed. Strictly speaking, in this case, the addition of the modified patterns to each class causes a change in the reference pattern vector of the class; hence, the accuracy of the discriminant analysis of step S4 in FIG. 3, 6 or 8 could be increased by performing the analysis after obtaining a new reference pattern vector for each class. It is also possible, however, to determine the discriminant function F(x) and the coupling coefficient .gamma. by performing the analysis of step S4 in FIG. 3, 6 or 8 through utilization of the reference pattern vector prior to the addition of the new rival patterns to the rival pattern set of each class.

In the embodiments of FIGS. 6 and 8, learning is repeated for n=1, 2, . . . , the repetition of learning is finished when it is determined in step S9 that the recognition rate R(n) for all patterns of all classes will no longer increase, and the ultimate dictionary is determined on the basis of the dictionary G(n-1) using the ultimately determined optimum coupling coefficient .gamma..sub.A. In practice, however, even if the recognition rate for the patterns of all classes is maximum, the recognition rates for the individual classes usually differ and do not always become maximum when the recognition rate for the patterns of all classes reaches its maximum value. That is, the recognition rate for a certain class may sometimes become maximum during the repetition of learning. It is considered possible to further increase the recognition rate as a whole by holding a temporary dictionary generated upon each repetition of learning, selecting one of the temporary dictionaries which maximizes the recognition rate for a corresponding one of the classes, and extracting and registering the function F(n) held in the selected dictionary for the class.

FIG. 10 shows an example of the procedure based on the above-noted idea. This procedure will be described as being applied to the FIG. 6 embodiment. Assume that in FIG. 6, the value of the coupling coefficient .gamma..sub.A (n), determined in step S5 upon each repetition of learning, is held and the dictionary G(n) set up in step S8 is held as a temporary dictionary. Let it be assumed that when the condition for making the recognition rate R(n) higher than the previous one is no longer satisfied in step S9, N+1 temporary dictionaries, including the case of n=0, are obtained. In this case, the procedure shown in FIG. 10 is performed in place of the processing of step S12 in FIG. 6.

Let q=1, 2, 3, . . . , Q represent the numbers of all classes and n=0, 1, . . . , N the numbers of temporary dictionaries. In step S1, the dictionary number n and the class number q are initialized to 0 and 1, respectively. Then, in step S2, the recognition rate R.sub.1 (0) is first obtained for patterns of the class q=1, using the corresponding coupling coefficient .gamma..sub.A (0) based on the n=0th one G(0) of the N+1 dictionaries, that is, the original dictionary D, where .gamma..sub.A (0) is zero. When it is found in step S3 that the dictionary number n is not the last one N, it is incremented by one in step S4. Then, flow returns to step S2 to obtain the recognition rate R.sub.1 (1) for the same class q=1, using the coupling coefficient .gamma..sub.A (1) based on the next dictionary G(1). Thereafter, the sequence of steps S2, S3 and S4 are similarly repeated, and when it is found in step S3 that the dictionary number n has reached the last one N, flow proceeds to step S5. At this time, there are provided, by the process of step S2, recognition rates R.sub.1 (0), . . . , R.sub.1 (N) for the class q=1 by the N+1 sets of dictionary G and coupling coefficient .gamma..sub.A. In step S5, a set of parameters, for example, .mu., .omega., {a.sub.m }, {b.sub.m }, c and .gamma..sub.A, for the class q=1 in the dictionary G(n) which provide the maximum one of the N+1 recognition rates, are registered as ultimate dictionary data for the class q=1. Next, in step S6, if it is found that the class number q has not reached the last number Q, the class number q is incremented by one in step S7. Then, flow returns to step S2 and repeats the sequence of steps S2, S3 and S4 to perform the same processing as mentioned above, obtaining the recognition rate R.sub.2 (n) for the class q=2 by each of the N+1 sets of dictionary and the coupling coefficient .gamma..sub.A. In step S5, dictionary data for the class q=2 in the dictionary which provides the maximum recognition rate for the class q=2 are registered as a dictionary G.sub.2 (n) together with the corresponding coupling coefficient .gamma..sub.A (n). thereafter, steps S2 through S6 are repeated, by which dictionaries, which maximize the recognition rates for the respective Q classes, are ultimately selected and the dictionary data corresponding to each class is registered together with the corresponding coupling coefficient .gamma..sub.A.

The method shown in FIG. 10 is applicable to step S13 in the FIG. 8 embodiment as well. In such an instance, the coupling coefficient .gamma..sub.A (n) is determined in step S6 in FIG. 8 and the dictionary G(n) is generated using the coupling coefficient .gamma..sub.A (n).

Incidentally, in the case of discriminating input patterns by use of the dictionary set up as described above, the learned distance function G(x) represented by Eq. (1) is used to select that one of the input patterns which is minimum in the distance between its feature vector and the reference pattern vector of each class. In this case, the equation which expresses the learned distance function G(x) contains the parameter .gamma. which is the coupling coefficient for coupling the original distance function D(x) and the discriminant function F(x). By experimentation, it has been found that the parameter .gamma. may have very large values of four through six digits according to the learning repetition count, the number of rival patterns and so forth. Consequently, floating-point operations are needed to calculate the learned distance function G(x)--this increases the computational quantity and decreases the processing speed. However, since learning samples (i.e. training patterns) are recognized using the original distance function D(x) and the discriminant function F(x) is defined so that misread or nearly-misread patterns, that is, rival patterns are correctly classified, it will be understood that the pattern recognition can be performed as briefly described below with reference to FIG. 1.

That is, in the distance calculating part 13, the distance D(x) between the feature vector of an arbitrary input pattern and each reference pattern vector is calculated by Eq. (2), (5), or (8), referring to the original dictionary 14 and a predetermined number of class candidates or those in a predetermined distance range are selected in increasing order of the distance. Then, in the discriminant value calculating part 15, the reference pattern vector of each class candidate and the feature vector of the input pattern are substituted in F(x) in Eq. (4), (7), or (10) and the discriminant dictionary 16 is referred to, to thereby obtain the value of the discriminant function F(x). The class which minimizes the discriminant function F(x) is used as the result of recognition of the input pattern. This method does not call for calculating the coupling coefficient .gamma., and hence does not involve floating-point operations and permits processing with simple integer operations.

As described above, according to the present invention, a discriminant analysis is made between the pattern set of each class and the corresponding rival pattern set, using the difference between the corresponding components of the feature vector and the reference vector and the square of the difference as variables. By this, the difference between these pattern sets can be emphasized, and consequently, the use of the dictionary thus generated increases the pattern recognition accuracy without significantly increasing the memory capacity used and the amount of data to be processed.

It will be apparent that many modifications and variations may be effected without departing from the scope of the novel concepts of the present invention.