PatentDe  


Dokumentenidentifikation EP0960381 13.06.2002
EP-Veröffentlichungsnummer 0960381
Titel GERÄT UND VERFAHREN ZUR MUSTERERKENNUNG.
Anmelder Hewlett-Packard Co. (n.d.Ges.d.Staates Delaware), Palo Alto, Calif., US
Erfinder KAWATANI, Takahiko, Kanagawa, JP;
SHIMIZU, Hiroyuki, Kanagawa, JP
Vertreter derzeit kein Vertreter bestellt
DE-Aktenzeichen 69805280
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 13.02.1998
EP-Aktenzeichen 989063326
WO-Anmeldetag 13.02.1998
PCT-Aktenzeichen PCT/US98/02660
WO-Veröffentlichungsnummer 0009836372
WO-Veröffentlichungsdatum 20.08.1998
EP-Offenlegungsdatum 01.12.1999
EP date of grant 08.05.2002
Veröffentlichungstag im Patentblatt 13.06.2002
IPC-Hauptklasse G06K 9/62

Beschreibung[en]

The invention relates to a pattern recognition apparatus and a pattern recognition method and in particular to a pattern recognition method that combines different recognition modules to improve the recognition accuracy.

The demand for information processing involving pattern recognition is currently large and is rapidly increasing. Pattern recognition is used in such applications as image processing, text processing, and sound processing performed by computers. Consequently, improvements in pattern recognition technology are strongly desirable.

Pattern recognition is the process by which a physical phenomenon, such as an image, hand written or printed character or a sound, is converted to an electronic signal representing the phenomenon, a determination is made of which one of a number of possible categories in a category set the phenomenon belongs to, and a code indicating the determined category is generated. For example, in character recognition, an unknown printed character, such as the letter "A," may be scanned by an electronic scanner. The scanner generates an electronic pattern signal that represents a pattern composed of an array of a few thousand bytes that represent the unknown character. The pattern signal is then analyzed to determine to which of the categories in the category set corresponding to the letters A-Z the unknown character belongs. A code identifying this category as the category of the unknown character is then generated. For example, the ASCII code 33 representing the letter A may be generated.

Pattern recognition processing is preferably performed using features of the pattern extracted from the pattern signal instead of using the raw pattern signal. Processing the features extracted from the pattern signal is preferable because these features can often be processed faster, more accurately and cheaper than the raw pattern signal. If pattern signals containing extremely large quantities of information are processed, features are sometimes extracted, and the features must be processed. One objective of pattern recognition is to compress the information by representing the patterns using the features extracted from the pattern signal. Of course, the features must be extracted from the pattern signal in a way that does not impair the ability of the pattern recognition processing to recognize the pattern.

The feature f of a pattern p is usually defined by a set {x(p;m); m= 1,2,3,...,M} of a finite number M of feature components x(p;m). The feature f tangibly and quantitatively represents the characteristic qualities of the pattern. Consequently, since the feature f is represented by an M-dimensional vector whose m-th component is the feature component x(p;m), the vector representation of the feature f is the feature vector X(p) = (x(p;1), x(p;2),...., x(p;m))t. The argument p indicates the feature vector X(p) is the feature vector of the pattern p. The superscript t denotes vector transposition.

Even though the feature components are qualitative, they can be quantified and used.

If the pattern p undergoes various deformations, the value of the feature component x(p;m) changes. Consequently, the feature vector X(p) changes. However, as long as the deformed pattern belongs to its original category, the pattern recognition process must recognize it as belonging to that category.

A particular pattern that specified as being representative of the patterns belonging to a particular category or as being representative of a feature of the category is called the reference pattern of the category. The feature vector of the specified pattern is called the reference vector of the category. As an alternative to using a particular pattern as the reference pattern for the category, a hypothetical pattern obtained by averaging the patterns belonging to the category can be used as the reference pattern, and the feature vector of such hypothetical pattern can be used as the reference vector of the category.

In pattern recognition, an unknown pattern p is received and a pattern recognition process is performed. The pattern may determine whether the unknown pattern is similar to a known pattern q, or to determine which category the unknown pattern belongs to. Pattern recognition is essential in recognizing diagrams, characters, symbols, images, and sounds. General information about pattern recognition and the problems of pattern recognition can be found in Reference 1, Kazuo Nakada, Ed.: PATTERN RECOGNITION AND ITS APPLICATION, Corona Co. (1978) (in Japanese) and Reference 2, Hidemitsu Ogawa, Ed.: New Developments in Pattern Recognition and Understanding - The Challenges -DENSHI JYOHO TSUSHIN GAKKAI (1992) (in Japanese).

Examples of pattern recognition in which the unknown patterns are character patterns will described below on the understanding that the principles set forth in the description can easily be applied to other forms of pattern recognition, such as image recognition and sound recognition. Character patterns are patterns representing letters, numbers, Kanji characters and the like. A pattern representing a character will from now on be referred to as a character pattern. Examples of possible feature components of character patterns include:

  • the length-to-width ratio of the character,
  • the number of horizontal lines,
  • the number of loops,
  • whether each square of a grid overlaid on the character is black or white,
  • the number of crossing points with a straight line in a specific direction, and
  • the transform coefficients of a Fourier transform of the character pattern.

A set of feature components such as that listed above is used to construct the feature vector so that the resulting feature vector can optimally represent the characters in the character set. The dynamic range of each feature component is selected to improve the accuracy of the pattern recognition to be described later. The feature component may be normalized using the standard deviation when this is needed.

Pattern recognition generates a category name for each character pattern subject to pattern recognition. The category code represents the reading, meaning, or code of the character pattern. For example, the category name of the category to which the character "A" belongs may be "category A." As noted above, a specific character pattern belonging to the category is selected as the reference pattern for the category. Alternatively, a hypothetical pattern obtained by averaging a number of character patterns belonging to a category may be used as the reference pattern. The feature vector of the reference pattern is adopted as the reference vector of the category.

At the heart of pattern recognition is a recognition processor that has the objective of determining that all unknown character patterns that represent the character "A," belong to category A, irrespective of whether the character pattern is deformed, and, further, that such character patterns do not belong to categories other than category A.

The processing performed by a character recognition apparatus after character pattern observation and reading is usually divided into a series of process modules that perform character pattern preprocessing, feature extraction, and recognition. Each process module can primarily be implemented using a computer and is realized by the computer performing a specific set of operations. All of the process modules, including observation of the character pattern, affect the result generated by the recognition module.

The strategy for increasing the accuracy of character recognition is to maximize the recognition ratio and to reduce the misrecognition ratio to zero. The recognition ratio is the fraction of character patterns that should belong to each category that are correctly recognized as belonging to that category. The misrecognition ratio is the fraction of characters patterns that do not belong to each category that are misrecognized as belonging to that category. In particular, many applications strongly demand that misrecognition does not occur, i.e., character patterns that do not belong to category A, for example, must not be allocated to category A.

Each input pattern can be regarded as a warping or a modification of a corresponding ideal pattern. Such modification can be regarded as an inverse form of pre-processing in the sense that the modification degrades the ability of the pattern recognition apparatus to recognize the pattern. This negative pre-processing must be one of the target factors taken into consideration when attempting to improve the performance of a pattern recognition apparatus for character patterns.

Known approaches to improving the recognition accuracy of a pattern recognition apparatus have added feedback control functions, such as adjusting the processing performed by each process module based on the recognition result, and have made various changes to the processing performed by the recognition module.

The character pattern pre-processing referred to above includes normalizing the size, tilt, position, and line density of an input character pattern, and removal of noise such as spots and scratches.

Feature extraction referred to above analyzes an input character pattern to determine the values of the feature components that represent the shape and other characteristics of the character represented by the character pattern. The feature vector of the character pattern is constructed from the feature components. The number of feature components is typically of the order of several hundred, for example, 380 or 500, but may be as large as several thousand. One way of generating the feature vector of a character pattern is to hypothetically overlay the character pattern with a 64 × 64 grid and then determine whether each square of the grid is filled by a stroke of the character pattern. If the square is filled, the value 1 is allocated to the square. Otherwise, the value 0 is allocated. Each square of the grid may be regarded as a feature component, and a 4,096-dimensional feature vector whose elements are 0 and 1 is generated as the feature vector of the character pattern.

In another example, another effective feature in character recognition is a combination of, for example, the number of end points in the strokes (2 in the letter A), the number of loops ( 1 in the letter A), the number of bending points ( 1 in the letter A), the number of branch points (2 in the letter A), the number of crossing points (0 in the letter A), and their positions. Then, the smallest possible number of feature components consistent with a required recognition accuracy is selected, and a feature vector with the corresponding number of dimensions is constructed. Although increasing the number of dimensions of the feature vector tends to increase the recognition accuracy, increasing the number of dimensions increases the processing time and the memory capacity required.

In the recognition module referred to above, the feature vector extracted from each input character pattern is matched to the reference vector of each category in the category set to determine the category to which the input character pattern belongs. The reference vectors are determined before the character recognition processing starts and are stored in a recognition dictionary. The reference vectors are specific to the character set to which the unknown character belongs and to the particular way in which the character recognition is performed. The recognition dictionary includes a set of reference vectors, at least one reference vector for each category in the category set. Recognition modules often use a similarity function or a distance function as a recognition function to determine the category to which the unknown character pattern belongs. The distance between the character pattern and the reference pattern can be regarded as the distance between the character pattern and the category, as represented by the reference pattern. In particular, the distance between the feature vector of the character pattern and the reference vector of the reference pattern can be regarded as the distance between the character pattern and the category.

When the recognition module uses a distance function, a way of measuring the distance between character patterns is defined, and the distance between the input character pattern and each category is measured. Generally, the shorter the distance, the more similar are the character patterns. An input character pattern whose feature vector is within a fixed distance of the reference vector of a certain category can be said to belong to that category. Alternatively, a character pattern can be said to belong to the category to which the closest reference feature vector belongs.

When the feature vector of the input character is defined as in the example described above, the recognition module computes the Hamming distance (number of mutually different elements) in the 4,096-dimensional feature vector whose elements are 1 and 0. An input character is said to belong to the category whose reference vector is within a Hamming distance of 100 from the extracted feature vector of the input character.

Hamming distances are calculated between the feature vector extracted from the input character pattern and the reference vectors of all the categories in the category set. The category for which the Hamming distance is shortest is determined to be the category to which the input character pattern belongs.

Additional conditions may be imposed before an input character pattern is said to belong to the category whose reference vector is the shortest distance from the feature vector of the input character pattern. Examples of such additional conditions are that the shortest Hamming distance must be less than a first threshold value, and that the increment between the shortest Hamming distance and the second-shortest Hamming distance must be greater than a second threshold value.

In other examples of a highly accurate character recognition process, the recognition module may use as its recognition function a distance function that determines a Euclidean distance, a distance function that determines a weighted Euclidean distance, or a quadratic discriminant function. It is known that the recognition accuracy of such recognition functions can be increased by using a training process to improve the discriminant function and the character recognition dictionary. The Learning by Discriminant Analysis (LDA) method described by the inventor in Handprinted Numerals Recognition by Learning Distance Function, TRANS. OF THE IEICE, Vol. J-76-D-11, No. 9, pp. 1851-59 (Reference 3). takes into account the deformation of character patterns by training the discriminant process. This reference additionally describes conventional character recognition processes in some detail, so a review of this reference provides a good basis for better understanding the invention disclosed below.

Learning by Discriminant Analysis uses Fisher's linear discriminant analysis. Part of the LDA method will now be described using symbolic representations that differ from the symbolic representations used in Reference 3 to be discussed below. In Learning by Discriminant Analysis, a distance function that gives a weighted Euclidean distance is trained and stored in the recognition dictionary. Specifically, the weighting vectors and constant terms of the distance function and the reference vectors are learned.

A known input character pattern p is input to the recognition apparatus as a training pattern and is first subject to conventional preprocessing and feature extraction to obtain the feature vector X(p) = (x(p;1), x(p;2),..., x(p;m),..., x(p;m))t.

The reference vector R(K) = (r(K;1), r(K;2),..., r(K;m),..., r(K;M))t of each category K in the category set {K} is given, and the weighted Euclidean distance D(p,K) between the input character pattern X(p) and the reference vector R(K) of each category in the category set is calculated. The weighted Euclidian distance is calculated using:

To be precise, D(p,K) gives the square of the distance, but it will simply be called the distance here.

In this, ω(K;m) is the m-th weighting factor and is one element of the weighting vector W(K) = (ω(K;1), ω(K;2),..., ω(K;m),..., ω(K;M))t. The character recognition dictionary L({K}) stores the parameters needed to perform the recognition operation. Typical parameters include the reference feature vectors R(K) and the weighting vectors W(K). {K} indicates the entire set of categories of which the category K is a member and to which the input character can belong. During the matching operation, the reference dictionary provides a reference vector for each category in the category set. Consequently, the recognition dictionary related to the category set {K} is designated as L({K}).

Although the above format of the distance function is used to determine the weighted Euclidian distance for all of the categories in the category set, the parameters used in the distance function are set to specific values for each category. The distance function after learning by LDA differs from a conventional distance function based on the usual definition satisfying the distance formula. The LDA-based recognition function increases the differences between patterns.

In the following description, the category to which the input character pattern p actually belongs will be designated by K(p). In the LDA-based pattern recognition operation, the learning operation is performed using training patterns, i.e., character patterns whose categories are known. The modified Euclidian distance D(p,K) between each input character pattern and each category is determined for each category K in the category set. The recognition module determines that the input character pattern p belongs to the category K1(p) for which the determined modified Euclidian distance D(p,K) is smallest. However, in some circumstances, the determined category K1(p) will differ from the category K(p) to which the input character pattern p actually belongs. In this case, the input character pattern is misrecognized. In other circumstances, the increment between the distances D(p,K1) and D(p,K2) between the input character pattern on one hand and the category K1 and the category K2 on the other hand is small. The category K2 differs from the category K1. For such character patterns, the recognition result K(p) cannot be said to be accurate with a high degree of confidence. A character pattern that is either incorrectly allocated to a category, or that cannot be said with a high degree of confidence to belong to a category, can be characterized in one of the following ways:

  • (1) A character pattern that actually belongs to a category different from category K but that the recognition module misrecognizes as belonging to the category K will be called an error pattern poe belonging to the category K.
  • (2) A character pattern that actually belongs to a category different from category K but that the recognition module nearly misrecognizes as belonging to the category K will be called a near-miss pattern pon belonging to the category K.

The terms poe and pon are the terms used in by the inventor Reference 3, referred to above and describe two types of rival patterns por that constitute the rival pattern set of the category K. In LDA, the weighting vectors and constant terms and the reference vectors are learned so that all rival patterns por are kept at least a minimum distance from the category K. The learning process can be performed for all of the categories or only for those categories for which misrecognition most easily takes place.

The rival pattern set of the category K is designated by Ωr(K) and the in-category pattern set of the category K be designated by Ωo(K). The in-category pattern set of the category K is composed of the training patterns defined as belonging to the category K. The learning process determines the coefficients {a(m); m = 1 to M}, {b(m); m = 1 to M}, and c so that these coefficients make the discriminant function F(X(p),R(K)) given by the equation below negative when the training pattern is a member of the in-category set Ωo(K) and positive when the training pattern is a member of the rival pattern set ΩrR(K). During this processing, the average of the feature vectors of the training patterns that belong to the in-category pattern set of the category K is used in the reference vector R(K) of the category K. The discriminant function is calculated using:

Since the discriminant function F(X(p), R(K)) is negative for the in-category pattern set Ωo(K), F(R(K),R(K)) = c < 0.

The discriminant function F(X(p),R(K)) is then weighted by the factor γ and the result is added to the original distance defined above in equation (1). Thus, the distance D(X(p),R(K)) becomes the new distance G(X(p),R(K)) defined as follows:

The weighting factor y in equation (3) is a positive number and is determined experimentally. The value of the weighting factor is selected to maximize the recognition accuracy over all of the categories in the category set {K}. The tests use publicly-available character databases or independently-compiled character databases. Often, the learning operation is performed using a portion of the character patterns in the character database and the remainder of the character patterns are used to verify the result of the learning operation.

As a result of performing the learning operation, the weighting vector, reference vector, and constant term are learned in the format with the added constant term d(K). The new reference vector and weighting vector are designated as: T(K) = (r(K;1) + Δr(K;1),..., r(K;M) + Δr(K;M))+, and U(K) = (ω(K;1) + Δω(K;1),..., ω(K;M) + Δω(K;M))+, respectively.

The constant term d(K), weighting vector U(K), and reference vector T(K) are stored in the recognition dictionary. Next, discrimination using G(X(p),R(K)), which includes the constant term, is performed, and newly-generated rival patterns which result from this discrimination are added to the rival pattern set of each category and the learning process is repeated

In the examples described above, since the feature vectors and discriminant functions are unchanged in type from the original feature vectors, the scope of the learning process is restricted to a portion of the recognition process. This portion includes the contents of the recognition dictionary.

Pattern recognition methods that combine multiple different recognition processes to improve the character recognition accuracy are known. Specifically, combinations of recognition processes that use different features extracted from the pattern are known. The features may differ in their type and the number of feature components in them. Moreover, combinations of recognition processes that use different discriminant functions have been tried. Either of these possible combinations of recognition processes is effective at improving the recognition accuracy. However, conventional ways of using multiple recognition processes simply combine at least two independently-developed recognition processes. There is no Indication that more effect measures have been taken such as designing one recognition process to recognize with high accuracy the characters that are not recognized by the other recognition process. As a result, the improvement in the recognition accuracy resulting from using a combination of two conventional recognition processes is limited.

Schwerdtmann W. describes in his article "Reduktion des Klassifikationsfehler durch angepasste Musterentwicklung" in Nachrichtentechnische Zeitschrift, June 1974, Volume 27, No. 6, pages 233 to 238, the reduction of errors in classification processes by using adapted pattern developments. It is described that prior to classification of a pattern, features are extracted. The aim of the extraction of the features is to determine on the basis of the features those features which are relevant for classification. By means of the extraction of features, the features to be used for classification are reduced to only the essential features.

JP-A-8106295 describes a method and device for recognizing patterns in which the pattern is classified into classes among prescribed plural classes. The input pattern is transformed into vectors of plural features spaces corresponding to respective classes. A pattern recognition is executed by selecting a class to which the input pattern belongs.

Jin Wang et al. describes in "Resolving multifont character confusion with neural networks" in Pattern Recognition, Volume 6, No. 1, January 1, 1993, pages 175 to 187, the resolving of character confusion by using a set of feedforward neural networks and a rule invocation procedure added to a conventional character recognition system.

It is the object underlying the present invention to provide an improved pattern recognition apparatus and an improved recognition method having improved accuracy in recognizing patterns.

This object is achieved by an apparatus according to claim 1 and by a method according to claim 11.

The present invention provides a pattern recognition apparatus and method in which the recognition accuracy is improved by integrating two recognition processes that have characteristics designed so that those patterns that cannot be recognized with high reliability by one of the recognition processes are recognized with the highest possible accuracy by the other recognition process.

According to a preferred embodiment, the two recognition processes are integrated in a way that minimizes the percentage of patterns that are correctly recognized by the one of the recognition processes operating alone but are misrecognized by the recognition processes operating together.

It is an advantage of the present invention that a pattern recognition apparatus and method in which two recognition processes are integrated is provided in which learning by the integrated recognition processes is easily implemented.

The invention provides a pattern recognition apparatus that comprises an input section, a feature extraction module, a feature transform module, a recognition section that includes a recognition dictionary and a categorizer. The input section receives input patterns that include a pattern belonging to one of plural categories constituting a category set. The feature extraction module expresses features of the pattern as a feature vector. The feature transform module uses transform vector matrices to transform at least part of the feature vector to generate an at least partially transformed feature vector corresponding to each of the categories. The recognition dictionary stores both matching information and first transformed matching information for each of the categories. The first transformed matching information has been transformed using the transform vector matrices. The recognition section generates at least one difference value for each of the categories by performing a matching operation between at least one matching vector derived at least from the at least partially transformed feature vector corresponding to each of the categories on one hand, and the matching information and the first transformed matching information on the other hand. The categorizer identifies the category to which the pattern belongs in response to the at least one difference value.

One embodiment additionally comprises a reliability determination module, the feature transform module transforms all of the feature vector to generate a transformed feature vector corresponding to each of the categories, and the recognition section includes first recognition module and a second recognition module. The first recognition module generates a first difference value for each of the categories by performing a matching operation between the matching information and a first matching vector derived from the feature vector. The second recognition module generates a second difference value for each of the categories by performing a matching operation between the first transformed matching information and a second matching vector derived from the first transformed feature vector corresponding to each of the categories. The reliability determination module receives the first difference value for each of the categories and indicates when pattern recognition based on the first difference value for each of the categories would be reliable. The categorizer identifies the category to which the pattern belongs in response either to the first difference value for each of the categories alone for each of the categories or to the first difference value and the second difference value for each of the categories. The categorizer identifies in response to the first difference values alone when the reliability determination module indicates that pattern recognition based on the first difference values would be reliable.

The invention also provides a method for recognizing patterns in which input patterns are received and features of the pattern are expressed as a feature vector. The input patterns include a pattern belonging to one of plural categories constituting a category set. A least part of the feature vector is transformed using transform vector matrices to generate an at least partially transformed feature vector corresponding to each of the categories. A matching operation is performed between a matching vector derived from the at least partially transformed feature vector corresponding to each of the categories on one hand, and matching information and transformed matching information for each of the categories on the other hand. The matching operation generates at least one difference value for each of the categories. The transformed matching information is matching information that has been transformed using the transform vector matrices. Finally, the category to which the pattern belongs is identified in response to the at least one difference value.

The transform vector matrices include a transform vector matrix for either (a) a category belonging to the category set, or (b) a category subset composed of plural categories belonging to the category set. The transform vector matrix may be generated by receiving training patterns whose respective categories are defined and expressing features of the training patterns as feature vectors. The categories to which the training patterns respectively belong are identified by performing a matching operation between first matching vectors derived from the feature vectors and the matching information. The categories to which the training patterns are identified as belonging are compared with the respective defined categories to define a rival pattern set for either (a) the category, or (b) the category subset, respectively. An average vector is determined from the feature vectors of all of the training patterns defined as belonging to either (a) the category, or (b) the category subset, respectively. A difference vector is calculated for each of the training patterns belonging to the rival pattern set using the average vector. An autocorrelation matrix of the difference vectors is calculated. Finally, eigenvectors of the autocorrelation matrix are adopted as transform vectors constituting the transform vector matrix either (a) the category, or (b) the category subset, respectively.

The transformed recognition information for a category belonging to the category set may be generated by receiving training patterns whose respective categories are defined and expressing features of the training patterns as feature vectors. The categories to which the training patterns respectively belong are identified by performing a matching operation between a first matching vector derived from the feature vector and the matching information. The categories to which the training patterns are identified as belonging are compared with the respective defined categories to define a rival pattern set for the category. The feature vectors of the training patterns are transformed to generate respective transformed feature vectors using the transform vector matrix for either (a) the category, or (b) a category subset to which the category belongs. The category subset is composed of plural categories belonging to the category set. A discriminant analysis is performed using the transformed feature vectors to generate a discriminant function. A modified difference value is calculated between the training patterns and each of the categories using the discriminant function. The categories to which the training patterns respectively belong are re-identified in response to the modified difference value for each of the categories. The categories to which the training patterns are identified as belonging in response to the modified difference values are re-compared with the respective defined categories to determine whether additional patterns are misrecognized as belonging to the category. The transformed recognition information is generated using the discriminant function when no additional patterns are misrecognized. Otherwise, the additional patterns are included in the rival pattern set of the category, and the discriminant analysis performing, modified difference value calculating, category re-identifying and re-comparing operations are repeated until no additional patterns are misrecognized.

Figure 1 is a block diagram of a first embodiment a pattern recognition apparatus according to the invention.

Figure 2 is a flow diagram showing how the transform vector matrices used by the pattern recognition apparatus are generated.

Figure 3 is a flow diagram showing how the recognition dictionary used to perform pattern recognition on the transformed feature vectors is generated.

Figure 4 is a block diagram of a second embodiment of the pattern recognition apparatus according to the invention.

Figure 5 is a block diagram of a third embodiment of the pattern recognition apparatus according to the invention.

Figure 6 is a block diagram of a fourth embodiment of the pattern recognition apparatus according to the invention.

Figure 7 is a block diagram of a pattern recognition device incorporating one embodiment the pattern recognition apparatus according to the invention.

In the following description, the term difference value will be understood to encompass the following parameters, and any other parameter or parameters that quantify a similarity or dissimilarity between two vectors: the distance value of a distance function, the value of a similarity function, the value of a quadratic discriminant function, the value of a discriminant function, the value of another discriminant function, or the value of a combination of such functions. The value of the squared distance in LDA is another example of a difference value.

In the pattern recognition apparatus and method according to the invention, two different recognition modules determine a difference value between a matching vector characterizing the input character pattern and the reference vector of each category in the category set stored in the recognition dictionary. Since feature vectors are not necessarily extracted unchanged from the input pattern but may undergo a feature transformation and additionally or alternatively may have their number of dimensions reduced, the vectors characterizing the input patterns are called matching vectors in this disclosure.

Practical embodiments of the pattern recognition apparatus according to the invention are not used to perform the learning process using training patterns. Instead, a model of such a practical embodiment is simulated and the learning process is performed using the model. At the end of the learning process, the results generated by the learning process are transferred to the practical embodiment of the apparatus for use in actual pattern recognition. In the following description of the invention, unless it would otherwise be confusing, the practical embodiment of the pattern recognition apparatus and the model of this apparatus are not distinguished.

The pattern recognition apparatus according to the invention includes first and second recognition modules respectively equipped with first and second recognition dictionaries. The pattern recognition apparatus can perform either a character recognition operation or a learning operation in which the recognition dictionaries are optimized. In performing the learning operation, the pattern recognition apparatus first extracts a feature vector from a training pattern belonging to a given category and obtains a first difference value by matching the first recognition dictionary to a first matching vector related to the feature vector. The second recognition module then generates a second difference value by matching to the second recognition dictionary to a second matching vector related to the feature vector. The second matching vector includes a transformed feature vector obtained by transforming at least a portion of the feature vector using transform vector matrices. Finally, the category of the training pattern is determined from the first and second difference values.

The pattern recognition apparatus uses the above processing to perform a pattern recognition operation. In this, an unknown input pattern is processed instead of the training pattern.

In the learning operation, the pattern recognition apparatus additionally determines the eigenvector from (1) the rival patterns determined from the first difference values of at least one of the categories and (2) the training patterns belonging to the category. In addition, the pattern recognition apparatus performs the above-mentioned processing until the category of all of the training patterns in the training pattern set, composed of training patterns belonging to all of the categories in the category set, has been determined. Next, the pattern recognition apparatus determines the recognition accuracy of the pattern recognition performed on the training pattern set. This is determined by comparing the categories to which the training patterns actually belong with the categories determined from the first and second difference values. Finally, the second recognition dictionary is modified in a manner designed to increase the recognition accuracy, and the categories of all the training patterns in the training pattern set are re-determined and the recognition accuracy is re-determined.

In one embodiment of the invention, the first matching vector includes all of the feature components of the feature vector extracted from each training pattern, and the second matching vector includes a transformed feature vector obtained by transforming a vector that includes all of the feature components of the feature vector extracted from the training pattern.

In another embodiment of the invention, the first matching vector is composed of the first group of the feature components of the feature vector extracted from the training pattern. The second matching vector can include a transformed feature vector obtained by transforming a vector composed of a second group, different from the first group, of the feature components of the feature vector extracted from the training pattern.

When needed to conserve the computational resources required to provide the pattern recognition apparatus, the first matching vector can have a reduced number of dimensions and can be composed of a first group of the feature components of the feature vector extracted from the training pattern.

One example of a pattern recognition system embodying the pattern recognition apparatus according to the invention and capable of performing the pattern recognition method according to the invention is composed of a learning center in communication with a terminal. The terminal stores the recognition dictionaries and the transform vector matrices and performs the function of determining the category of the input character pattern. The terminal makes this determination on the recognition dictionaries and the transform vector matrices. In response to a notification of a rival pattern generated at the terminal, the pattern recognition apparatus is designed so that the learning center updates the recognition dictionary and the terminal updates the transform vector matrices.

The recognition system can be embodied in a computer or digital signal processor with functions capable of easily relearning in response to changes in the training patterns and increases in the misrecognition rate, and automatically learning based on changes in the recognition accuracy.

A variation of the pattern recognition apparatus according to the invention can have multiple recognition units in a serial arrangement. Each recognition unit is composed of a recognition dictionary and a recognition module. At least one recognition unit accepts the input pattern. At least one recognition unit receives the output of another recognition unit and generates an output which it forwards to another recognition unit. At least one recognition unit receives the matching vector related to the feature vector of the input pattern and transforms the features represented by the feature vector using the transform vector matrices. At least one recognition unit forwards its output to the recognition module. The recognition module determines the category of each input pattern. Each transform vector matrix is determined based on the rival pattern determined by the recognition unit connected to the input side for the transform vector matrix. In this structure, each recognition unit reliably recognizes a pattern that the recognition units previous to the recognition unit have had difficulty recognizing. This way, the recognition accuracy of the multiple recognition unit pattern recognition apparatus can be further improved.

Figure 1 is a block diagram of a first embodiment 100 of a pattern recognition apparatus according to the invention. The pattern recognition apparatus includes the pattern input section 102 composed of the pattern input module 104 and the pre-processing module 106; the feature extraction module 108; the first recognition module 110; the reliability determining module 112; the feature transform module 114; the second recognition module 116 and the categorizer 118. The processing performed by each of these modules will be described in detail next.

Each input pattern p is received by the pattern input module 104 that forms part of the pattern input section 102. The pattern input module passes the pattern to the pre-processing module 106 which normalizes the size, position, rotation etc., of the pattern. The preprocessing module passes the normalized pattern to the feature extraction module 108 which extracts from the pattern the features that will be used for recognizing the pattern. The feature extraction module expresses the features extracted from the pattern p as the feature vector X(p).

The first recognition module 110 adopts the feature vector X(p) as the matching vector for the pattern p. The first recognition module performs a first matching operation between the matching vector of the pattern p and the reference vector R(K) and the weighting vector W(K) of each category K constituting the category set {K}. The reference vectors and weighting vectors are stored in the first recognition dictionary 120. The matching operation performed by the first recognition module generates a first difference value between the matching vector of the input pattern and the reference vector for each category. Each first difference value quantifies the difference between the input pattern and the respective category.

The first recognition module 110 forwards the first difference value for each category in the category set {K} to the reliability determining module 112 and to the categorizer 118. Based on the first difference values for the categories in the category set, the reliability determining module generates an output signal whose state indicates whether or not pattern recognition based on the first difference values would be reliable. The reliability determining module can determine, for example, the increment between the smallest of the first difference values and the next-smallest of the first difference values. The reliability determining module can then compare the reliability value with a predetermined threshold value to determine the state of its output signal.

If the reliability value is greater than, or not less than, the predetermined threshold value, the reliability determining module 112 determines that pattern recognition based on the first difference values generated by the first recognition module 110 would be reliable. In this case, the reliability determining module generates its output signal in a HIGH RELIABILITY (HIGH) state. The reliability determining module passes the output signal to the categorizer 118, the feature transform module 103 and the second recognition module 116. In response to the reliability module output signal in the HIGH state, the categorizer identifies the category in the category set {K} for which the first difference value is smallest and outputs a code indicating this category as the category of the input pattern. Moreover, the HIGH state of the output signal inhibits operation of the feature transform module 103 and the second recognition module 116.

If the reliability result is less than the predetermined threshold value, the reliability determining module 112 determines that pattern recognition based on the first difference values generated by the first recognition module 110 would not be reliable. In this case, the reliability determination module generates its output signal in the LOW RELIABILITY (LOW) state. In response to the reliability module output signal in the LOW state, the feature transform module 114 and the second recognition module 116 perform additional processing to generate a second difference value, and the categorizer determines the category of the input pattern in response to both the first and second difference values. This increases the reliability of the recognition result generated by the categorizer.

The feature transform module 114 receives the feature vector of the input pattern from the feature extraction module 108 and temporarily stores it. When the reliability determining module 112 generates its output signal in the LOW state, the feature transform module applies a transform to the feature vector X(p) of the input pattern p. The transform is performed using the transform vector matrix &phis;(K) for each category K in the category set {K}. Generation of the transform vector matrix &phis;(K) will be described below with reference to Figure 2. Transforming the feature vector X(p) using the transform vector matrix &phis;(K) of each category K in the category set generates the transformed feature vector Y(p;K) for each category in the category set.

The m-th feature component y(p;K;m) of the transformed feature vector Y(p;K) is given by: y(p;K;m) = X(p)&phis;(K;m) where &phis;(K;m) is the m-th transform vector of the transform vector matrix &phis;(K) of category K. The transform module forwards the transformed feature vector Y(p;K) for each category to the second recognition module 116.

The second recognition module 116 adopts the transformed feature vector Y(p;K) of the input pattern p and the category K received from the transform module 114 as the matching vector of the pattern p for the category K. The second recognition module performs a second matching operation between each transformed feature vector, which is the matching vector in this recognition process, and the page L({K};&phis;(K)) of the transformed recognition dictionary L({K}) 122 corresponding to the transform vector matrix &phis;(K). The transformed recognition dictionary is generated using LDA, for example. The page L({K};&phis;(K)) stores the transformed reference vector R(&phis;(K)), the transformed weighting vector T(&phis;(K)), and, when needed, the constant term d(&phis;(K)) of each category K in the category set {K} corresponding to transformation by the transform vector matrix &phis;(K) for the category. For the input pattern p matching for the category K is performed between the transformed feature vector Y(p;K) of the pattern p for the category K and the transformed reference vector R(&phis;(K)), the transformed weighting vector T(&phis;(K)), and, when needed, the constant term d(&phis;(K)) of the category K stored in the page L({K};&phis;(K)) of the reference dictionary.

Using the transformed reference vectors and transformed weighting vectors for each category stored in the page L({K};&phis;(K)) of the transformed recognition dictionary L({K}) 122 corresponding to the transform vector matrix &phis;(K) of each category K, the second recognition module 116 generates a second difference value between the transformed feature vector Y(p;K) of the input pattern p for the category K as the matching vector and the transformed reference vector R(&phis;(K)) of each category in the category set {K}. The second recognition module forwards the second difference value for each category in the category set to the categorizer 118. The structure of the transformed recognition dictionary L({K};&phis;(K)) page will be described below.

When the output signal of the reliability determining module 112 is in its LOW state, indicating that pattern recognition based solely on the first difference values generated by the first recognition module 110 would not be reliable, the categorizer 118 modifies the first difference value for each category prior to determining the category of the input pattern. For each category, the categorizer multiplies the second difference value determined for each category by the second recognition module 116 by a constant multiplier, and adds the result to the first difference value received for the category from the first recognition module to generate a modified difference value. The categorizer then identifies the category in the category set {K} for which the modified difference value is smallest and provides a code indicating this category as the category of the input pattern.

The multiplier used in the categorizer 118 to multiply the second difference values is selected experimentally to increase the recognition accuracy over all of the categories. A publicly-available pattern database such as a character pattern database is used to train and to test the pattern recognition apparatus according to the invention. Some of the character patterns in the database are used as training patterns and the remainder is used as test patterns. For example, four-fifths of the character patterns in the data base can be used as training patterns, and the remainder can be used as test patterns. The multiplier that maximizes the overall recognition accuracy is selected. Moreover, an independently-compiled character database can be used in addition to the publicly-available character database to increase the accuracy of the character recognition in a specific region of the character set where higher-than-average recognition accuracy is desired. Furthermore, the complete set of recorded character patterns can be used as training patterns. However, if a portion of the recorded character patterns is used as training patterns and the remainder as test patterns, the stability and robustness of the recognition performance of the pattern recognition apparatus can be evaluated more reliably. It is also effective to interchange the recorded character patterns used as training patterns and those used as test patterns.

Although the feature transform module 114 and the second recognition module 116 are shown as operating in response to the output signal of the reliability determination module 112, this is not critical. The feature transform module and the second recognition module can generate second difference values for each input pattern. In this case, the HIGH state of the output signal of the reliability determination module causes the categorizer 118 to ignore the second difference values, and to determine the category of the input pattern in response to the first difference values alone.

Figure 2 is a flow chart illustrating the processing performed to generate the transform vector matrix &phis;(K) for each category K in the character set {K}. This processing may be performed in the embodiments of the pattern recognition apparatus described in this disclosure, or may be performed independently. In the latter case, the results of the processing are loaded into the pattern recognition apparatus. First, in step 10, a set of training patterns is input. The category to which each training pattern is defined. In step 12, a preliminary pattern recognition operation is performed on the training patterns. This operation may be performed using the input module 102, feature extraction module 108, first recognition module 110, the reliability determination module 112 and the categorizer 118 of the embodiment of the pattern recognition apparatus shown in Figure 1. For each training pattern q, the preliminary pattern recognition operation generates a difference value between the training pattern and the reference feature vector for each category K in the category set {K}, a determination of the category of the training pattern and a determination of the reliability of the category determination.

In step 14, the recognition results generated by the preliminary pattern recognition operation performed in the step 12 are evaluated to generate a rival pattern set for each category. Two types of patterns are allocated to the rival pattern set of each category. Evaluation of the recognition results with respect to the category K will now be described.

The first type of pattern allocated to the rival pattern set of the category K is a pattern whose defined category is not category K, but which the preliminary pattern recognition operation performed in step 12 misrecognized as belonging to category K. This type of rival pattern will be called an error pattern pe(K) in the rival pattern set of category K.

The second type of pattern allocated to the rival pattern set of the category K is a pattern whose defined category is not category K, but which the preliminary pattern recognition operation performed in step 12 nearly misrecognized as belonging to category K. A pattern is nearly misrecognized as belonging to category K if category K is the category with the second-smallest difference value, and the increment between the smallest difference value and the second-smallest difference value is small. This type of rival pattern will be called a near-miss pattern pn(K) in the rival patter set of category K. The near-miss patterns are identified by the reliability determination module 112.

The error patterns pe(K) are identified by comparing each training pattern that the preliminary pattern recognition operation allocates to category K with the defined category of the training pattern. A training pattern allocated to category K and whose defined category is not category K is identified as an error pattern.

The near-miss patterns pn(K) are identified in the following way. For the training patterns whose defined category is not category K, the increment is determined between the difference value between the training pattern and category K and the difference value between the training pattern and the category to which the preliminary pattern recognition operation allocated the training pattern. Next, a fixed number of training patterns is selected from among the training patterns whose increment is smaller than a threshold value. In performing this selection, the training patterns are selected in order of their increments, starting with the smallest.

Preferably, both error patterns and near-miss patterns constitute the rival pattern set Λ(K) of the category K. Alternatively, the near-miss patterns can be omitted so that the rival pattern set consists exclusively of error patterns. However, tests have shown that including near-miss patterns in the rival pattern set produces better results. In particular, when there are few error patterns the effect of including the near-miss patterns produces a significant improvement.

In step 16, the feature vectors of all the training patterns defined as belonging to the category K are averaged to generate the average vector Rm(K) of the category K.

In step 18, the feature vector of each rival pattern in the rival pattern set is subtracted from the average vector Rm(K) of the category K to generate a difference vector for the rival pattern.

In step 20, the autocorrelation matrix of the difference vectors generated in step 18 is determined. This is done as follows:

The feature vector of the n-th rival pattern pr,n in the rival pattern set of the category K is X(K;r;n). The difference vector determined in step 18 for the rival pattern is ≡(K;r;n), where: ≡(K;r;n) = X(K;r;n) - Rm(K). The autocorrelation matrix Q(K;r) of the difference vector ≡(K;r;n) is given by:

where N(K;r) is the total number of rival patterns in the rival pattern set, and the summation from 1 to N is a summation over the rival pattern set, and t denotes the transposition of the difference vector.

In step 22, the eigenvectors &phis;(K;m) of the autocorrelation matrix Q(K;r) are determined and adopted to form the transform vector matrix &phis;(K) for the category K. The maximum number of transform vectors constituting the transform vector matrix for the category K is equal to the number of dimensions M of the feature vectors. The m-th transform vector of the transform vector matrix is the eigenvector of the autocorrelation matrix with the m-th largest eigenvalue.

The difference vector calculated in step 18 represents the difference between each rival pattern in the rival pattern set and the average vector of the category K. The eigenvectors of the autocorrelation matrix Q(K;r) are regarded as an orthogonal expansion of the difference between the category K and the rival patterns. Consequently, the eigenvectors of the autocorrelation matrix Q(K;r) accurately reflect the main components of the difference between the category K and the rival patterns. Projections of the input feature vector on the eigenvectors of the autocorrelation matrix Q(K;r) were found to be extremely effective in separating the in-category pattern set of the category K from the rival pattern set.

At step 24, a test is performed to determine whether a transform vector matrix has been generated for each category K in the category set {K}. If the result is YES, execution ends. If the result is NO, execution returns to step 14 so that the transform vector matrix for anther category in the category set can be generated.

In an alternative way of determining the transform vector matrix of the category K, the covariance matrix S(K) of the in-category pattern set of the category K is determined in addition to the average vector for the category. The in-category pattern set is composed of the training patterns whose defined category is category K. Then, after the autocorrelation matrix Q(K;r) of the rival pattern set of the category K has been calculated in step 20, it is multiplied by inverse of the covariance matrix of the in-category pattern set to generate the matrix S(K)-1Q(K;r), Finally, in step 22, the eigenvectors of the matrix S(K)-1Q(K;r) are determined and adopted to form the transform vector matrix &phis;(K) for the category K.

An eigenvector of the autocorrelation matrix Q(K;r) defines an axis along which the squared average, taken over all of the rival patterns, of a projection of the difference vector of each rival pattern onto the axis is a maximum. In contrast, an eigenvector of the matrix S(K)-1Q(K;r) defines an axis along which the squared mean, taken over all of the rival patterns, of a projection of the difference vector of each rival pattern onto the axis increases, and along which scattering is relatively small when the in-category pattern set of the category is projected. This is also considered to be extremely effective in separating the in-category pattern set of the category K from the rival pattern set.

In the adoption process performed in step 22, the eigenvector with the largest eigenvalue is adopted as one transform vector of the transform vector matrix. In addition, a number of the eigenvectors having progressively smaller eigenvalues is additionally selected. The number of eigenvectors selected determines the complexity of the transform vector matrix and the complexity of the processing performed using the transform vector matrix. Thus, it is desirable to select only those eigenvectors whose eigenvalues are significant. The number of eigenvalues selected is the number of eigenvectors between the eigenvector with largest eigenvalue and the eigenvector of a desired eigenvalue where the summation of eigenvalues from the largest eigenvalue to the desired eigenvalue is greater than a predetermined fraction, for example, 0.9, of the sum of all of the eigenvalues. Alternatively, the number of eigenvectors selected can be determined experimentally.

In the above description, the eigenvectors determined for each category are adopted as the transform vectors constituting the respective transform vector matrix used to transform the feature vectors of the input patterns. Alternatively, the feature vector transformation can use transform vector matrices generated from a super set of the rival pattern sets of a desired number of categories constituting the category subset {K}'. The transformation effected such transform vector matrices takes multiple categories into consideration.

The category subset {K}' is composed of a desired number of categories. Categories are selected for inclusion in the category subset {K}' by ranking all of the categories in the category set {K} in the order of their number of error patterns and the size of their rival pattern sets, with priority being given to the number of error patterns. The desired number of the categories is then taken from the large number of error patterns/large rival pattern set end of the ranking to constitute the category subset {K}'. Optionally, the category subset {K}' can be made co-extensive with the category set {K}.

Then, in a step analogous to step 20, the autocorrelation matrix Q({K}';r) of the difference vectors of the category subset {K}' is calculated using equation (8), which is based on equation (7) that gives the autocorrelation matrix Q(K;r) of the difference vector ≡(K;r;n) of the category K in category subset {K}':

In this, the summation from 1 to {K} denotes that the terms are added across those categories in the category set {K} that constitute the category subset {K}'.

In a step analogous to step 22, the m-th eigenvector &phis;({K}';m) of the autocorrelation matrix Q({K}';r) of the difference vectors of the category subset {K}' is determined and adopted as the m-th transform vector of the transform vector matrix &phis;({K}') for the category subset {K}'.

In an alternative similar to that described above, the average covariance matrix S({K}) of the training patterns belonging to the category subset {K}' is found and the transform vector &phis;({K}';m) is replaced by the eigenvector of S({K})-1Q({K}';r). This provides the same effect as that provided by replacing the eigenvector &phis;(K;m) by the eigenvector of S(K)-1Q(K;r), as described above.

Figure 3 shows a flow diagram of the process for generating the transformed recognition dictionary L({K}:&phis;(K)). The same processing in which &phis;(K) is replaced by &phis;({K}') can be used to generate the transformed recognition dictionary L({K};&phis;({K}')). This processing may be performed in the embodiments of the pattern recognition apparatus described in this disclosure, or may be performed independently. In the latter case, a suitable storage or transmission medium is used to load the results generated by the processing into the pattern recognition apparatus.

In the transformed recognition dictionary generation processing shown in Figure 3, steps 10-14 are identical to steps 10-14 in the transform vector matrix generating process described above with reference to Figure 2 and will not be described in detail. The training patterns that were misrecognized or nearly misrecognized as belonging to each category in the preliminary pattern recognition step 12 are identified as the rival pattern set Λ(K) of the category in step 14.

In step 30, the feature vectors of all of the training patterns defined as belonging to each category are transformed using the transform vector matrix &phis;(K) of the category.

In step 32, a discriminant analysis is performed between the in-category pattern set and the rival pattern set of each category. The variables used in the discriminant analysis are the feature vectors transformed using the transform vector matrix &phis;(K) of the category. The discriminant analysis derives a discriminant function that optimally separates the rival pattern set and the in-category pattern set of the category. The discriminant analysis may be performed using the procedure set forth by the inventor in Reference 3.

In step 34, the value of the discriminant function determined for each category in step 32 is multiplied by a constant and the result is added to the difference value for each category determined for each training pattern in step 12 to generated a modified distance value.

In step 36, the category of each of the training patterns is then determined using the modified distance values generated in step 34.

In step 38, the pattern recognition result generated in step 36 for each training pattern is evaluated, and a test is performed to determine whether the processing performed in steps 32, 34 and 36 has resulted in new misrecognized patterns. New misrecognized patterns are error patterns that are not already members of the rival pattern set of the category. If the result of the test is NO, execution advances to step 40. If the result of the test is YES, and new misrecognized patterns have been generated, execution passes to step 42, where the new misrecognized patterns of each category are added to the rival pattern set of the category. Execution then returns to step 32, and the loop composed of steps 32, 34, 36, 38 and 42 repeats until the test result in step 38 is NO.

In step 40, the transformed recognition dictionary is generated using the discriminant function generated in the last iteration of step 32.

When the m-th component of the average vector Rm(&phis;(K)) of the transformed feature vector Y(K;p) of category K is designated by rm(&phis;(K);m), the discriminant function F(Y(K;p), Rm(&phis;(K))) of the category K is given by:

The weighting vectors of which a(m) is the m-th component, the reference vector of which rm(&phis;(K);m) - b(m)/(2a(m)) is the m-th component, and the constant terms having the value of

are stored as the category K recognition dictionary in the transformed recognition dictionary. According to this procedure, when combined with the discriminant functions used in step 12, a discriminant function can be determined to maximize the recognition accuracy.

The inventor has discovered that in iterations of the learning process, the recognition accuracy initially increases, but the learning effect gradually decreases and the recognition accuracy may actually decrease. This fact is used to stop the learning process automatically when either of the following conditions are met:

  • (1) the recognition accuracy reaches a specific value; or
  • (2) an additional iteration of the learning process does not improve the recognition accuracy.

When the second criterion is adopted, the contents of the recognition dictionary before the iteration of the learning process is begun and the transform vector matrix for each category is stored in memory for use. The pattern recognition apparatus according to the invention can include a display that notifies the user that the learning iteration has stopped and that displays the achieved recognition rate and the number of iterations of the learning process performed.

In the above processing, the rival patterns can be automatically compiled. The categories and the character patterns are obtained as training patterns and test patterns. The error patterns and near-miss patterns are extracted. At this time, the error patterns are automatically determined as described above. If the maximum number of near-miss patterns is specified, the near-miss patterns are automatically determined. Alternatively, a predetermined number of near-miss patterns is selected only when the number of error patterns is less than the predetermined number.

The training patterns, including the test patterns when necessary, are given to the recognition system according to the invention implemented on a computer as described above and are automatically learned. Consequently, the recognition system according to the invention has a simple implementation and can be easily adapted to a given application by providing it with training patterns corresponding to the application.

Figure 4 is a block diagram of a second embodiment 130 of a pattern recognition apparatus according to the invention. In this, elements corresponding to elements of the first embodiment described above with reference to Figure 1 are indicated by the same reference numerals and will not be described in detail. In this embodiment, the input section 102 feeds pre-processed input patterns to the feature extraction module 108, which is a first feature extraction module, and also to the second feature extraction module 132. The first feature extraction module extracts a first feature vector from each input pattern. The first feature vector is subject to the operations performed by the first recognition module 110 and the reliability determination module 112. The second feature extraction module is similar to the first feature extraction module, but extracts different feature components from each pre-processed input pattern to generate a second feature vector.

The feature transform module 134 operates similarly to the feature transform module 114 described above to transform each second feature vector generated by the second feature extraction module 132 using the transform vector matrix &phis;(K) for each category in the category set {K}. The second recognition module 136 operates similarly to the second recognition module 116 to perform a recognition process on the transformed second feature vectors using the transformed recognition dictionary 138. For each input pattern, the second recognition module generates a difference value between the input pattern and each category in the category set {K}.

The categorizer 118 determines the category of each input pattern solely using the first difference values generated by the first recognition module 110 when the reliability determination module output signal is in its HIGH state, and using both the first difference values generated by the first recognition module 110 and the second difference values generated by the second recognition module 116 when the reliability determination module output signal is in its LOW state.

The second feature extraction module 132, the feature transform module 134 and the second recognition module 136 are shown as operating in response to the output signal of the reliability determination module 112 so that they collectively generate second difference values only for those input patterns that the reliability determination module determines that pattern recognition based on the first difference values generated by the first recognition module 110 would not be reliable. Alternatively, these modules may generate second difference values for every input pattern. In this case, when the state of the output signal of the reliability determination module is in its HIGH state, the categorizer ignores the second difference values generated by the second recognition module and determines the category of the input pattern solely in response to the first difference values generated by the first recognition module.

The second embodiment differs from the first embodiment in that the feature transform module 134 operates on the second feature vectors generated by the second feature extraction module 132 instead of on the feature vectors generated by the feature extraction module 108, and that the first and second feature extraction modules extract different sets of features from the pre-processed input pattern. The second recognition module 136 can be simplified by enabling it to operate on a smaller set of features. Based on tests that determine the recognition accuracy using test patterns whose categories are known, as described above, the second embodiment or the first embodiment can be selected, depending on which gives the better recognition accuracy.

Normally, the first feature vector and the second feature vector do not have common feature components. However, they may have common feature components when this would clearly improve the recognition accuracy. In the first and second embodiments described above, the first recognition module 110 is described as operating using a recognition function based on Learning by Discriminant Analysis. However, this is not critical, and other recognition functions can alternatively be used.

In the embodiment of the pattern recognition apparatus described above with reference to Figure 1, the transform vector matrix &phis;(K) that transforms the feature vectors in the feature transform module 114 may be replaced by the transform vector matrix &phis;({K}') described above with reference to Figure 2. If this is done, the transformed recognition dictionary L({K};&phis;(K)) 122 used in the second recognition module 116 is also replaced by the transformed recognition dictionary L({K};&phis;({K}')). Corresponding changes can be made to the feature transform module 134 and to the transformed recognition dictionary 138 used in the second recognition module 136 of the second embodiment shown in Figure 4. In both of these cases, the transform vector matrix &phis;({K}') is determined as described above using the rival pattern set of the category subset {K}'. The rival pattern set of the category subset {K}' is composed of the rival pattern sets of all of the categories constituting the category subset {K}'. In the transformed recognition dictionary L({K};&phis;({K}')), the reference vector of each category K in the category set {K} is transformed using the transform vector matrix &phis;({K}') to generate the transformed reference vector for the category. When the category subset {K}' is composed of only one category, {K}' becomes K.

When there is only one category in the category set {K} or in the category subset {K}', {K} and {K}' can be set to K in the above explanation. The category subset {K}' can include as many as all of the categories in the category set {K}.

The feature transform module 114,134 can be operated so that it generates a transformed feature vector for each of the categories belonging to the category subset {K}' by transforming the feature vector of the input pattern using the transform vector matrix &phis;({K}'). In this case, the feature transform module additionally generates the transformed feature vectors for the remaining categories belonging to the category set {K} by transforming the feature vector of the input pattern using the transform vector matrix &phis;{K} of each of the remaining categories. Alternatively, the transform module 114,134 can be operated so that it generates a transformed feature vector for each of the categories belonging to the category set {K} using the transform vector matrix &phis;({K}') to transform the feature vector of the input pattern. The former mode of operation easily improves the recognition accuracy, but tends to have a greater demand for operational speed and memory capacity than the latter.

In a variation on the first embodiment of the pattern recognition apparatus according to the invention, the first recognition module 110 and the reliability determination module 112 are omitted. Each extracted feature vector X(p) extracted by the feature extraction module 108 is input unchanged to the feature transform module 114, and the categorizer determines the category of the input pattern solely on the basis of the difference values generated by the second recognition module 116.

In a variation on the second embodiment of the pattern recognition apparatus according to the invention described above with reference to Figure 4, the reliability determination module 112 is omitted, the second feature extraction module 132, the feature transform module 134 and the second recognition module 136 operate on every input pattern, and the categorizer 118 determines the category of every input pattern using both the first difference value generated by the first recognition module 110 and the second difference value generated by the second recognition module 136.

Figure 5 shows a third embodiment of the pattern recognition apparatus according to the invention. Elements of this embodiment that correspond to the first embodiment described above with reference to Figure 1 are indicated using the same reference numerals and will not be described in detail. In this embodiment, the feature extraction module 142 extracts a first feature vector and a second feature vector from each pre-processed input pattern. The two feature vectors are independently processed before being combined by the feature vector combining module 146. The recognition module 148 adopts the combined feature vector as the matching vector when it performs the matching operation with the recognition dictionary.

The feature extraction module 142 extracts two sets of features from each pre-processed input pattern and expresses each set of features as a feature vector. The feature extraction module sends the first feature vector X1(p) to the dimension reduction module 144 and sends the second feature vector X2(p) to the feature transform module 114.

The dimension reduction module 144 reduces the number of dimensions of the first feature vector X1(p) using, for example, the known Karhunen-Loeve expansion, and sends the dimension-reduced feature vector Z1(p) to the feature vector combining module 148. The dimension reduction module may be omitted, in which case, Z1(p) = X1(p).

When the number of dimensions of the first feature vector X1(p) is reduced, the m-th component z1(p;m) of the resulting dimension-reduced feature vector Z1(p) is given by: z1(p;m) = X1(p) ψ($;m) in which Ψ($,m) is an m-th degree dimension-reduced vector that can use the eigenvectors of the covariance matrix of all of the training patterns used in the learning processing performed by this embodiment. Other known dimension reduction techniques may alternatively be used. The $ symbol in the vector ψ($;m) indicates that all of the training patterns are used.

The feature transform module 114 transforms the features of the second feature vector X2(p) using the transform vector matrix &phis;(Z1;{K}'). The transform vector matrix &phis;(Z1;{K}') indicates a transform vector matrix that is generated by performing pattern recognition using the dimension-reduced feature vector Z1(p) extracted from the training patterns and is based on the rival pattern set of the category subset {K}'.

The result of transforming the second feature vector X2(p) using the transform vector matrix &phis;(Z1;{K}') is the transformed feature vector Y1(p;Z1;{K}').

The m-th feature component y1(p;Z1;{K}';m) of the transformed feature vector Y1(Z1;{K}') is given by: y1(p;Z1;{K}';m) = X2(p)&phis;(Z1;{K}';m) in which &phis;(Z1;{K}';m) is the m-th transform vector of the transform vector matrix &phis;(Z1;{K}').

The feature vector combining module 146 extracts all of the components of the dimension-reduced feature vector Z1(p) and the transformed feature vector Y1(Z1;{K}') to generate the combined feature vector C(Z1;Y1). Alternatively, this module may generate the combined feature vector by extracting only specific components from the vectors received from the dimension reduction module 144 and the feature transform module 114. The feature vector combining module feeds the combined feature vector C(Z1;Y1) to the recognition module 148,

The recognition module 148 adopts the combined feature vector C(Z1;Y1) as its matching vector and performs a matching operation between the matching vector and the combined recognition dictionary 150. The processing performed by the recognition module 148 is similar to that performed by the first recognition module 110 described above with reference to Figure 1 and generates a difference value for each category. The recognition module 148 forwards the difference values to the categorizer 152. The categorizer then determines the category of the input pattern by identifying the category corresponding to the smallest of the difference values received from the recognition module.

The combined recognition dictionary 150 used in this embodiment can be created by applying LDA using a combined feature vector C(Z1;Y1) derived from each training pattern. Moreover, although dimension reduction is applied to reduce the number of dimensions of the first feature vector, the transform vector matrix &phis;(Z1;{K}') is determined by first performing a recognition process using a recognition dictionary optimized for the dimension-reduced feature vector Z1(p). Based on the recognition result using this dictionary, rival pattern sets are compiled, and the transform vector matrix &phis;(Z1;{K}') is found in the same way as the above-mentioned transform vector matrix &phis;({K}').

This embodiment has an improved recognition accuracy and a rapid recognition processing time, but does not require that the combined recognition dictionary be large.

In this embodiment, the first feature vector can be the same as the second feature vector.

Figure 6 shows a fourth embodiment 160 of the pattern recognition apparatus according to the invention. Elements of this embodiment that correspond to the first and second embodiments described above with reference to Figures 1 and 4 are indicated using the same reference numerals and will not be described again here.

In the pattern recognition apparatus shown in Figure 6, the pattern recognition apparatus 100 shown in Figure 1 is modified by the addition of the second reliability determination module 160; and the feature extraction module 132, the feature transform module 134 and the recognition module 138 of the second embodiment shown in Figure 4. In the fourth embodiment, these elements are called the second feature extraction module 132, the second feature transform module 134 and the third recognition module 136. The third recognition module includes the second transformed recognition dictionary 138.

The second reliability determination module 162 operates together with the first feature transform module 114 and the second recognition module 116 in response to the LOW state of the output signal of the first reliability determination module 112. The LOW state of this output signal indicates that pattern recognition based on the first difference values generated by the first recognition module 110 would not be reliable.

The second reliability determination module 162 receives the difference values generated by the first recognition module 112 and the second recognition module 116. The second reliability determination module operates similarly to the first reliability determination module 112 to determine the reliability of pattern recognition based on the difference values generated by the first and second recognition modules and generates an output signal whose state indicates the reliability of such pattern recognition operation. The output signal of the second reliability determination module is fed as a control signal to the second feature extraction module 132, the second feature transform module 134, the third recognition module 136 and the categorizer 164.

The second feature extraction module 132 receives the pre-processed patterns from the pattern input section 102, extracts a set of features from the input pattern and expresses the extracted features as a second feature vector. The features extracted by the second feature extraction module differ from the features extracted from the input pattern by the first feature extraction module 108. The second feature extraction module passes each second feature vector to the second feature transform module, which transforms the second feature vector, and passes the resulting transformed second feature vector to the third recognition module 136.

The third recognition module 136 adopts the transformed second feature vector as a matching vector, and performs a matching operation between the matching vector and the second transformed recognition dictionary 138. The matching operation generates a third difference value for each category. The third recognition module feeds the third difference values to the categorizer 164.

The categorizer 164 operates in response to the first and second output signals of the first reliability determination module 112 and the second reliability determination module 162, respectively, to determine the category of the input pattern using the difference values received from the first recognition module 110, the second recognition module 116 and the third recognition module 136. When the first reliability determination module output signal is in its HIGH state, the categorizer determines the category of the input pattern from the first difference values generated by the first recognition module alone. When the first reliability determination module output signal is in its LOW state and the second reliability determination module output signal is in its HIGH state, the categorizer determines the category of the input pattern from the first difference values generated by the first recognition module and from the second difference values generated by the second recognition module. When both the first and second reliability determination module output signals are in their LOW state, the categorizer determines the category of the input pattern from the first difference values generated by the first recognition module, the second difference values generated by the second recognition module and the third difference values generated by the third recognition module.

The transform vector matrices used in the feature vector transformations described above and the recognition dictionaries can be created by using the methods described above for creating such transform vector matrices and recognition dictionaries. For example, the transform vector matrices used in the feature transform modules 114 and 134 can be determined from rival pattern sets generated by performing a pattern recognition operation on training patterns using the first recognition module 110. The recognition dictionaries 120, 122 and 138 can be determined so that the recognition rate is maximum for preferably all of the training patterns up to the outputs of the first recognition module 110, the second recognition module 116 and the third recognition module 136 in which the recognition dictionaries are respectively located. Determining the transform vector matrix is subject to more variables than determining the recognition dictionary. For example, the transform vector matrices used in the feature transform modules 114 and 134 can be determined from the rival pattern sets generated by performing a pattern recognition operation on training patterns using the first recognition module 110. Alternatively, the transform vector matrices used in the second feature transform module 134 can be determined from the rival pattern set generated by performing a pattern recognition operation on training patterns using the first recognition module 110 and the second recognition module 116.

In a first variation on the embodiment just described, the second feature extraction module 132 is omitted, and the feature vectors generated by the first feature extraction module 108 are input to the second feature transform module 134. In a second variation, the second feature extraction module and the second feature transform module are omitted, and the transformed feature vectors generated by the first feature transform module 114 are directly input to the third recognition module 136.

The serial arrangement of a recognition module preceded by a feature extraction module, a feature transform module, or a feature extraction module and a feature transform module can be regarded as a recognition unit. In the embodiment shown in Figure 6, three recognition units including a recognition unit that includes the third recognition module 136 are cascaded. Variations on this embodiment can have additional recognition units located upstream near the pattern input section 102 and additionally or alternatively downstream near the categorizer. The pre-processed pattern derived from the input pattern can be input to multiple recognition units, depending on the recognition result of one or more of the recognition units.

In the variations just described, the input patterns and the vectors derived by linearly transforming the feature vector representing each input pattern are input to the recognition unit, the recognition unit generates a recognition result, which may be an indication of the category of the input pattern or a set of difference values for the input pattern, and the categorizer finally determines the category of the input pattern from the outputs of the recognition units. Therefore, the transform vector matrix used by the recognition unit is determined based on the rival pattern set obtained from an upstream recognition unit. The recognition dictionary of each recognition unit is set to maximize, or at least to increase significantly, the recognition accuracy of pattern recognition performed on training patterns by the part of the pattern recognition apparatus up to, and including, the recognition unit.

Figure 7 is a block diagram of a typical pattern recognition system 200. The system is composed of the learning center 202 and one or more terminals, a typical one of which is shown at 204, linked by the communication link or transferrable storage medium 206.

The learning center 202 uses built-in or externally-connected resources to run the control/training software 210 that processes the set 212 of training patterns to create the set 214 of transform vector matrices and the recognition dictionary 216. After the transform vector matrices and the recognition dictionary have been created by the learning center 202, they are stored using a suitable storage medium that can then be sent to the terminal 204. The terminal may be an optical character recognition (OCR) device that actually performs pattern recognition on unknown patterns temporarily stored in a storage medium. Alternatively, the transform vector matrices and recognition dictionary may be sent to the terminal 204 using the communication link 206. If the communication link used is bidirectional, the learning center can receive error patterns provided by the terminal, and can use the error patterns to update the transform vector matrices and the recognition dictionary. The learning center 202 may include a display (not shown) that can display messages such as the recognition accuracy. The system may include an input device (not shown) through which commands and data can be input.

The terminal 204 runs the control/recognition software 220 using built-in or externally-connected resources. Each pattern input using the pattern input module 222 is transformed by the transform vector matrices 224 and is matched to the recognition dictionary 226 to determine the category of the pattern.

Since substantial computer resources may be required to create the transform vector matrices 214 and the recognition dictionary 216, considerable scope exists for choosing an optimum balance between performance and cost of the computer on one hand with the sizes of the transform vector matrices and the recognition dictionary on the other. Either apparatus can perform both training and recognition.

According to the invention described above, when a first recognition module and a second recognition module are effectively combined, first vectors that effectively separate the in-category pattern set of each category from the rival pattern set of the category in the first recognition module are found. The second recognition module builds a recognition dictionary that enables as many as possible of the patterns misrecognized by the first recognition module to be correctly recognized. The second recognition module uses values of the feature vectors projected on the first vectors as feature vectors. By effectively combining two recognition modules, the invention markedly improves the recognition accuracy.

Moreover, pattern recognition apparatus and method according to the invention can be easily adapted to perform pattern recognition on different types of patterns simply by performing the learning process using the appropriate type of training patterns.

The embodiments of the pattern recognition apparatus disclosed herein can be constructed using dedicated hardware such as adders and multipliers. In a preferred embodiment, the pattern recognition apparatus is embodied in a computer program executed by a microprocessor (not shown) or digital signal processor. It should also be noted that, in computer-based and DSP-based embodiments, the various modules of the pattern recognition apparatus may be ephemeral, and may come into and out of existence as the various pattern recognition and learning operations are performed. Not all of the modules need exist simultaneously in the computer or DSP.

In the preferred embodiment, a computer including a pattern recognition program implements all of the processes described above. This disclosure provides sufficient information for a person of ordinary skill in the art to write a suitable pattern recognition program using a high-level (e.g., C or C++) or low-level programming language. Accordingly, the program listing itself is omitted. The pattern recognition program could be conveyed to the computer on which it is to run by embodying the program in a suitable tangible medium of expression, such as a set of floppy disks, a CD-ROM, a DVD-ROM, or could be transmitted to such computer by a suitable data link.

Although this disclosure describes illustrative embodiments of the invention in detail, it is to be understood that the invention is not limited to the precise embodiments described, and that various modifications may be practiced within the scope of the invention defined by the appended claims.


Anspruch[de]
  1. Eine Mustererkennungsvorrichtung, die folgende Merkmale aufweist:
    • einen Eingabeabschnitt (102), der Eingangsmuster empfängt, die ein Musters einschließen, das einer von mehreren Kategorien angehört, die einen Kategoriesatz bilden;
    • ein erstes Merkmalsextraktionsmodul (108), das Merkmale des Musters als einen ersten Merkmalsvektor ausdrückt;
    • ein erstes Merkmalstransformationsmodul (114), das Transformationsmatrizen verwendet, um zumindest einen Teil des ersten Merkmalsvektors zu transformieren, um einen zumindest teilweise transformierten ersten Merkmalsvektor entsprechend jeder der Kategorien zu erzeugen, wobei die Transformationsmatrizen eine Transformationsmatrix für jede Kategorie des Kategoriesatzes umfassen, wobei eine Transformationsmatrix für eine Kategorie in Reaktion auf einen rivalisierenden Mustersatz für die Kategorie erzeugt wird, wobei der rivalisierende Mustersatz rivalisierende Muster aufweist, die als zu der Kategorie gehörend fehlerkannt wurden, wobei die Transformationsmatrix auf der Basis der Differenz zwischen den Merkmalsvektoren in dem rivalisierenden Mustersatz und dem Referenzmerkmalsvektor für die Kategorie erhalten wird;
    • einen Erkennungsabschnitt, der ein Erkennungswörterbuch (120, 122) umfaßt, das Anpassungsinformationen und erste transformierte Anpassungsinformationen für jede der Kategorien speichert, wobei die ersten transformierten Anpassungsinformationen unter Verwendung der Transformationsmatrizen transformiert worden sind, und das für jede der Kategorien zumindest einen Differenzwert erzeugt durch Ausführen einer Anpassungsoperation zwischen:
      • den Anpassungsinformationen und den zuerst transformierten Anpassungsoperationen, und
      • zumindest einem Anpassungsvektor, der zumindest aus dem zumindest teilweise transformierten ersten Merkmalsvektor abgeleitet wurde, der jeder der Kategorien entspricht; und
    • einem Kategorisierer (118), der die eine der Kategorien, zu der das Muster gehört, in Reaktion auf den zumindest einen Differenzwert identifiziert.
  2. Die Mustererkennungsvorrichtung gemäß Anspruch 1, bei der:
    • das erste Merkmalstransformationsmodul den gesamten ersten Merkmalsvektor transformiert, um einen ersten transformierten Merkmalsvektor zu erzeugen, der jeder der Kategorien entspricht;
    • wobei der Erkennungsabschnitt folgende Merkmale aufweist:
      • ein erstes Erkennungsmodul (110), das einen ersten Differenzwert für jede der Kategorien durch Ausführen einer Anpassungsoperation zwischen den Anpassungsinformationen und einem ersten Anpassungsvektor erzeugt, der aus dem ersten Merkmalsvektor abgeleitet wurde, und
      • ein zweites Erkennungsmodul (116), das einen zweiten Differenzwert für jede der Kategorien durch Ausführen einer Anpassungsoperation zwischen den ersten transformierten Anpassungsinformationen und einem zweiten Anpassungsvektor erzeugt, der aus dem ersten transformierten Merkmalsvektor abgeleitet wurde, der jeder der Kategorien entspricht;
    • wobei die Vorrichtung zusätzlich ein Zuverlässigkeitsbestimmungsmodul (112) aufweist, das den ersten Differenzwert für jede der Kategorien empfängt und anzeigt, wann die Mustererkennung basierend auf dem ersten Differenzwert für jede der Kategorien zuverlässig sein könnte; und
    • der Kategorisierer die eine der Kategorien, zu der das Muster gehört, identifiziert in Reaktion auf:
      • den ersten Differenzwert alleine für jede der Kategorien, wenn das Zuverlässigkeitsbestimmungsmodul anzeigt, daß die Mustererkennung basierend auf dem ersten Differenzwert für jede der Kategorien zuverlässig sein könnte, und
      • den ersten Differenzwert und den zweiten Differenzwert für jede der Kategorien sonst.
  3. Die Mustererkennungsvorrichtung gemäß Anspruch 2, bei der:
    • die Mustererkennungsvorrichtung zusätzlich ein zweites Merkmalsextraktionsmodul (132) aufweist, das die Merkmale des Musters als einen zweiten Merkmalsvektor ausdrückt, wobei das zweite Merkmalsextraktionsmodul zwischen dem Eingabeabschnitt (102) und dem ersten Merkmalstransformationsmodul (134) angeordnet ist; und
    • das erste Merkmalstransformationsmodul den zweiten Merkmalsvektor transformiert, um die transformierten Merkmalsvektoren zu erzeugen.
  4. Die Mustererkennungsvorrichtung gemäß Anspruch 2, bei der:
    • die Vorrichtung zusätzlich folgende Merkmale aufweist:
      • ein zweites Zuverlässigkeitsbestimmungsmodul (162), das den ersten und den zweiten Differenzwert für jede der Kategorien empfängt und anzeigt, wann die Mustererkennung basierend auf dem ersten und dem zweiten Differenzwert für jede der Kategorien zuverlässig wäre,
      • ein zweites Merkmalsextraktionsmodul (132), das Merkmale des Musters als einen zweiten Merkmalsvektor ausdrückt, und
      • ein zweites Merkmalstransformationsmodul (134), das zweite Transformationsmatrizen verwendet, um den zweiten Merkmalsvektor zu transformieren, um einen zweiten transformierten Merkmalsvektor zu erzeugen, der jeder der Kategorien entspricht;
    • wobei das Erkennungswörterbuch (120, 122, 138) zusätzlich zweite transformierte Anpassungsinformationen für jede der Kategorien speichert, wobei die zweiten transformierten Anpassungsinformationen unter Verwendung der zweiten Transformationsmatrizen transformiert worden sind;
    • wobei der Erkennungsabschnitt ein drittes Erkennungsmodul (136) aufweist, das einen dritten Differenzwert für jede der Kategorien durch Ausführen einer Anpassungsoperation zwischen den zweiten transformierten Anpassungsinformationen und einem dritten Anpassungsvektor erzeugt, der aus dem zweiten transformierten Merkmalsvektor abgeleitet wurde, der jeder der Kategorien entspricht; und
    • wobei der Kategorisierer (164) die eine der Kategorien, zu der das Muster gehört, identifiziert in Reaktion auf:
      • den ersten Differenzwert für jede der Kategorien alleine, wenn das erste Zuverlässigkeitsbestimmungsmodul (112) anzeigt, daß die Mustererkennung basierend auf dem ersten Differenzwert für jede der Kategorien zuverlässig wäre,
      • den ersten und den zweiten Differenzwert für jede der Kategorien alleine, wenn das zweite Zuverlässigkeitsbestimmungsmodul (162) anzeigt, daß die Mustererkennung basierend auf dem ersten und dem zweiten Differenzwert für jede der Kategorien zuverlässig wäre, und
      • den ersten, zweiten und dritten Differenzwert für jede der Kategorien sonst.
  5. Die Mustererkennungsvorrichtung gemäß Anspruch 2, bei der

    eine serielle Anordnung des ersten Merkmalsextraktionsmoduls (108) und des ersten Erkennungsmoduls (110) eine erste Erkennungseinheit darstellen;

    eine serielle Anordnung des ersten Merkmalstransformationsmoduls (114) und des zweiten Erkennungsmoduls (116) zusammen eine zweite Erkennungseinheit darstellen; und

    die Mustererkennungsvorrichtung zusätzlich eine zusätzliche Erkennungseinheit (132, 134, 136) aufweist, die eine serielle Anordnung aufweist von:
    • zumindest einem Merkmalsextraktionsmodul (132) und einem Merkmalstransformationsmodul (134), und
    • einem Erkennungsmodul (136), das ein transformiertes Erkennungswörterbuch (138) umfaßt, das optimiert ist, um Muster zu erkennen, die nicht zuverlässig durch die erste und die zweite Erkennungseinheit erkannt werden.
  6. Die Mustererkennungsvorrichtung gemäß Anspruch 3 oder 4, bei der:
    • der erste Merkmalsvektor, der durch das erste Merkmalsextraktionsmodul erzeugt wurde, einen ersten Satz der Merkmale des Musters ausdrückt; und
    • der zweite Merkmalsvektor, der durch das zweite Merkmalsextraktionsmodul erzeugt wurde, einen zweiten Satz der Merkmale des Musters ausdrückt.
  7. Die Mustererkennungsvorrichtung gemäß Anspruch 6, bei der der erste Satz von Merkmalen und der zweite Satz von Merkmalen teilweise überlappen.
  8. Die Mustererkennungsvorrichtung gemäß Anspruch 1, bei der:
    • das erste Merkmalsextraktionsmodul (142) einen ersten Satz der Merkmale des Musters als den ersten Merkmalsvektor ausdrückt und
    • zusätzlich einen zweiten Satz der Merkmale des Musters als einen zweiten Merkmalsvektor ausdrückt;
    • das erste Merkmalstransformationsmodul (114) den gesamten Merkmalsvektor transformiert, um einen ersten transformierten Merkmalsvektor zu erzeugen, der jeder der Kategorien entspricht; und
    • die Vorrichtung zusätzlich ein Merkmalsvektor-Kombinierungsmodul (146) aufweist, das den zweiten Merkmalsvektor und den ersten transformierten Merkmalsvektor kombiniert, der jeder der Kategorien entspricht, um den zumindest teilweise transformierten ersten Merkmalsvektor zu erzeugen, der jeder der Kategorien entspricht, wobei das Merkmalsvektor-Kombinierungsmodul zwischen dem ersten Merkmalsextraktionsmodul und dem Erkennungsabschnitt (148) angeordnet ist.
  9. Die Mustererkennungsvorrichtung gemäß Anspruch 8, bei der:
    • der zweite Merkmalsvektor eine Anzahl von Dimensionen aufweist;
    • die Vorrichtung zusätzlich ein Dimensionsreduktionsmodul (144) aufweist, das die Anzahl von Dimensionen des zweiten Merkmalsvektors reduziert, um einen dimensionsreduzierten zweiten Merkmalsvektor zu erzeugen, wobei das Dimensionsreduktionsmodul zwischen dem ersten Merkmalsextraktionsmodul und dem Merkmalsvektor-Kombinierungsmodul angeordnet ist; und
    • das Merkmalsvektor-Kombinierungsmodul (146) den dimensionsreduzierten zweiten Merkmalsvektor und den ersten transformierten Merkmalsvektor, der jeder der Kategorien entspricht, kombiniert, um den zumindest teilweise transformierten Merkmalsvektor, der jeder der Kategorien entspricht, zu erzeugen.
  10. Die Mustererkennungsvorrichtung gemäß Anspruch 9, bei der das Merkmalsvektor-Kombinierungsmodul den kombinierten Merkmalsvektor durch Extrahieren eines Teilsatzes von zumindest:
    • dem dimensionsreduzierten zweiten Merkmalsvektor und dem ersten transformierten Merkmalsvektor, der jeder der Kategorien entspricht,
    erzeugt.
  11. Ein Verfahren zum Erkennen von Mustern, wobei das Verfahren folgende Schritte aufweist:
    • Empfangen (102) von Eingangsmustern, die ein Muster umfassen, das einer von mehreren Kategorien angehört, die einen Kategoriesatz bilden, wobei die Transformationsmatrizen eine Transformationsmatrix für jede Kategorie des Kategoriesatzes umfassen, wobei eine Transformationsmatrix für eine Kategorie in Reaktion auf einen rivalisierenden Mustersatz für jede Kategorie erzeugt wird, wobei der rivalisierende Mustersatz rivalisierende Muster umfaßt, die als zu der Kategorie gehörend fehlerkannt wurden, wobei die Transformationsmatrix auf der Basis der Differenz zwischen Merkmalsvektoren im rivalisierenden Mustersatz und dem Referenzmerkmalsvektor für die Kategorie erhalten wird;
    • Ausdrücken (108) von Merkmalen des Musters als ein Merkmalsvektor;
    • Transformieren (114) von zumindest einem Teil des Merkmalsvektors unter Verwendung von Transformationsmatrizen, um einen zumindest teilweise transformierten Merkmalsvektor zu erzeugen, der jeder der Kategorien entspricht;

         Ausführen (116) einer Anpassungsoperation zwischen:
      • Anpassungsinformationen und transformierten Anpassungsinformationen für jede der Kategorien, wobei die transformierten Anpassungsinformationen Anpassungsinformationen sind, die unter Verwendung der Transformationsmatrizen transformiert werden, und
      • einem Anpassungsvektor, der von dem zumindest teilweise transformierten Merkmalsvektor, der jeder der Kategorien entspricht, abgeleitet wurde, um zumindest einen Differenzwert für jede der Kategorien zu erzeugen; und
    • Identifizieren (118) der einen der Kategorien, zu der das Muster gehört, in Reaktion auf den zumindest einen Differenzwert.
  12. Das Verfahren gemäß Anspruch 11, bei dem die Transformationsmatrizen eine Transformationsmatrix für (a) eine Kategorie, die dem Kategoriesatz angehört, und (b) einen Kategorie-Teilsatz, der aus mehreren der Kategorien besteht, die zum Kategoriesatz gehören, umfassen, wobei die Transformationsmatrix erzeugt wird durch:
    • Empfangen (10) von Trainingsmustern, deren jeweilige Kategorien definiert sind, und Ausdrücken von Merkmalen der Trainingsmuster als erste Merkmalsvektoren;
    • Identifizieren (12) der Kategorien, zu der die Trainingsmuster jeweils gehören, durch Ausführen einer Anpassungsoperation zwischen ersten Anpassungsvektoren, die von den ersten Merkmalsvektoren abgeleitet wurden, und den Anpassungsinformationen;
    • Vergleichen (14) der Kategorien, zu denen die Trainingsmuster als zugehörig identifiziert werden, mit den jeweiligen definierten Kategorien, um einen rivalisierenden Mustersatz für jeweils (a) die Kategorie und (b) den Kategorie-Teilsatz zu definieren;
    • Bestimmen (16) eines Durchschnittsvektors ausvon den Merkmalsvektoren von allen Trainingsmustern, die als zu jeweils (a) die Kategorie und (b) dem Kategorie-Teilsatz gehörend definiert sind;
    • Berechnen (18) eines Differenzvektors für jedes der Trainingsmuster, die dem rivalisierenden Mustersatz angehören, unter Verwendung des Durchschnittsvektors;
    • Berechnen (20) einer Autokorrelationsmatrix der Differenzvektoren; und
    • Annehmen (22) von Eigenvektoren der Autokorrelationsmatrix als Transformationsvektoren, die die Transformationsmatrix für jeweils (a) die Kategorie und (b) den Kategorie-Teilsatz bilden.
  13. Das Verfahren gemäß Anspruch 12, bei dem:
    • die Eigenvektoren der Autokorrelationsmatrix jeweilige Eigenwerte aufweisen; und
    • das Annehmen von Eigenvektor folgende Schritte umfaßt:
      • Summieren der Eigenwerte von allen Eigenvektoren der Autokorrelationsmatrix, um einen ersten Summenwert zu erzeugen, und
      • Annehmen der Eigenvektoren in der Reihenfolge der absteigenden Eigenwerte als angenommene Eigenwerte und Summieren der Eigenwerte der angenommenen Eigenvektoren, um einen zweiten Summenwert zu erzeugen, bis der zweite Summenwert einen vorbestimmten Bruchteil des ersten Summenwerts übersteigt.
  14. Das Verfahren gemäß Anspruch 13, bei dem:
    • das Verfahren zusätzlich folgende Schritte aufweist:
      • Berechnen einer Kovarianzmatrix aus den Merkmalsvektoren von allen Trainingsmustern, die als zu der Kategorie gehörend definiert sind, und
      • Multiplizieren der Kovarianzmatrix mit der Autokorrelationsmatrix, um eine Produktmatrix zu erzeugen; und
      • beim Annehmen von Eigenvektoren, werden Eigenvektoren der Produktmatrix anstelle von Eigenvektoren der Autokorrelationsmatrix als die Transformationsvektoren der Transformationsmatrix angenommen.
  15. Das Verfahren gemäß einem der Ansprüche 12 bis 14, bei denen die transformierten Erkennungsinformationen für eine Kategorie, die dem Kategorie-Teilsatz angehört, erzeugt wird durch:
    • Empfangen (10) von Trainingsmustern, deren jeweilige Kategorien definiert sind, und Ausdrücken von Merkmalen der Trainingsmuster als Merkmalsvektoren;
    • Identifizieren (12) der Kategorien, zu denen die Träiningsmuster jeweils gehören, durch Ausführen einer Anpassungsoperation zwischen einem ersten Anpassungsvektor, der vom ersten Merkmalsvektor abgeleitet wurde, und den Anpassungsinformationen;
    • Vergleichen (14) der Kategorien, zu denen die Trainingsmuster als zugehörig identifiziert werden, mit den jeweiligen definierten Kategorien, um einen rivalisierenden Mustersatz für die Kategorie zu definieren;
    • Transformieren (30) der Merkmalsvektoren der Trainingsmuster unter Verwendung der Transformationsmatrix für (a) die Kategorie und (b) einen Kategorie-Teilsatz, zu dem die Kategorie gehört, wobei der Kategorie-Teilsatz aus mehreren der Kategorien, die dem Kategoriesatz angehören, besteht, um jeweilige transformierte Merkmalsvektoren zu erzeugen;
    • Durchführen (32) einer Diskriminanzanalyse unter Verwendung der transformierten Merkmalsvektoren, um eine Diskriminanzfunktion zu erzeugen;
    • Berechnen (34) eines modifizierten Differenzwerts für jede der Kategorien unter Verwendung der Diskriminanzfunktion;
    • erneutes Identifizieren (36) der Kategorien, zu denen die Trainingsmuster jeweils gehören, in Reaktion auf den modifizierten Differenzwert für jede der Kategorien;
    • erneutes Vergleichen (38) der Kategorien, zu denen die Trainingsmuster als zugehörig identifiziert sind, mit den jeweiligen definierten Kategorien in Reaktion auf die neuen Differenzwerte, um zu bestimmen, ob zusätzliche Muster als zu der Kategorie gehörend fehlerkannt werden; und
    • Erzeugen (40) der transformierten Erkennungsinformationen unter Verwendung der Diskriminanzfunktion, wenn keine zusätzlichen Muster fehlerkannt werden, und ansonsten Umfassen (42) der zusätzlichen Muster in den rivalisierenden Mustersatz der Kategorie und Wiederholen des Ausführens der Diskriminanzanalyse, des Berechnens des modifizierten Differenzwerts, des erneuten Identifizierens der Kategorie und des erneuten Vergleichens von Operationen, bis keine zusätzlichen Muster mehr fehlerkannt werden.
  16. Das Verfahren gemäß einem der Ansprüche 12 bis 15, bei dem:
    • das Verfahren zusätzlich folgende Schritte aufweist:
      • Ausführen einer Anpassungsoperation (110) zwischen den Anpassungsinformationen (120) für jede der Kategorien und einem ersten Anpassungsvektor, der aus dem Merkmalsvektor abgeleitet wurde, um einen ersten Differenzwert für jede der Kategorien zu erzeugen;
      • in Reaktion auf die ersten Differenzwerte, Erzeugen eines Zuverlässigkeitshinweises (112), der anzeigt, wann die Mustererkennung basierend auf den ersten Differenzwerten zuverlässig wäre;
      • wobei die eine der Kategorien, zu der das Muster gehört, in Reaktion auf eine Summe des ersten Differenzwertes für jede der Kategorien und eines Vielfachen des zweiten Differenzwertes für jede der Kategorien identifiziert (118) wird, wenn der Zuverlässigkeitshinweis anzeigt, daß die Mustererkennung basierend auf dem ersten Differenzwert nicht zuverlässig wäre; und
      • das Vielfache bestimmt wird durch:
        • Einstellen des Multiplikators auf einen anfänglichen Wert,
        • Empfangen von Trainingsmustern, deren jeweilige Kategorien definiert sind, und
        • Durchführen des Ausdrücken der ersten Anpassungsoperationsausführung der Zuverlässigkeitshinweis-Erzeugungsoperationen bezüglcih der Trainingsmuster, um die Trainingsmuster, für die der Zuverlässigkeitshinweis anzeigt,
        daß die Mustererkennung basierend auf den ersten Differenzwerten als identifizierte Trainingsmuster nicht zuverlässig wäre, als identifizierte Trainingsmuster zu identifizieren,
    • Ausführen der Transformationsoperation bezüglich der Merkmalsvektoren der identifizierten Trainingsmuster, und
    • Ausführen der nachfolgenden Sequenz auf den identifizierten Trainingsmustern, bis der Multiplikator einen Wert aufweist, der einer maximalen Erkennungsgenauigkeit entspricht;
    • Ausführen der zweiten Anpassungs- und Identifizierungsoperationen;
    • Vergleichen der Kategorien, zu denen die identifizierten Trainingsmuster als zugehörig identifiziert werden, mit den entsprechenden definierten Kategorien, um eine Erkennungsgenauigkeit zu bestimmen; und
    • Verändern des Multiplikators.
Anspruch[en]
  1. A pattern recognition apparatus, comprising:
    • an input section (102) that receives input patterns including a pattern belonging to one of plural categories constituting a category set;
    • a first feature extraction module (108) that expresses features of the pattern as a first feature vector;
    • a first feature transform module (114) that uses transform matrices to transform at least part of the first feature vector to generate an at least partially transformed first feature vector corresponding to each of the categories, wherein the transform matrices include a transform matrix for each category of said category set, wherein a transform matrix for a category is generated in response to a rival pattern set for said category, said rival pattern set comprising rival patterns misrecongnized as belonging to said category, wherein said transform matrix is obtained on the basis of the difference between feature vectors in the rival pattern set and the reference feature vector for said category;
    • a recognition section including a recognition dictionary (120, 122) that stores matching information and first transformed matching information for each of the categories, the first transformed matching information having been transformed using the transform matrices, and that generates at least one difference value for each of the categories by performing a matching operation between:
      • the matching information and the first transformed matching information, and
      • at least one matching vector derived at least from the at least partially transformed first feature vector corresponding to each of the categories; and
    • a categorizer (118) that identifies the one of the categories to which the pattern belongs in response to the at least one difference value.
  2. The pattern recognition apparatus of claim 1, in which:
    • the first feature transform module transforms all of the first feature vector to generate a first transformed feature vector corresponding to each of the categories;
    • the recognition section includes:
      • a first recognition module (110) that generates a first difference value for each of the categories by performing a matching operation between the matching information and a first matching vector derived from the first feature vector, and
      • a second recognition module (116) that generates a second difference value for each of the categories by performing a matching operation between the first transformed matching information and a second matching vector derived from the first transformed feature vector corresponding to each of the categories;
    • the apparatus additionally comprises a reliability determination module (11 2) that receives the first difference value for each of the categories and indicates when pattern recognition based on the first difference value for each of the categories would be reliable; and
    • the categorizer identifies the one of the categories to which the pattern belongs in response to:
      • the first difference value alone for each of the categories when the reliability determination module indicates that pattern recognition based on the first difference value for each of the categories would be reliable, and
      • the first difference value and the second difference value for each of the categories otherwise.
  3. The pattern recognition apparatus of claim 2, in which:
    • the pattern recognition apparatus additionally comprises a second feature extraction module (132) that expresses features of the pattern as a second feature vector, the second feature extraction module being interposed between the input section (102) and the first feature transform module (134); and
    • the first feature transform module transforms the second feature vector to generate the transformed feature vectors.
  4. The pattern recognition apparatus of claim 2, in which:
    • the apparatus additionally comprises:
      • a second reliability determination module (162) that receives the first and second difference values for each of the categories and indicates when pattern recognition based on the first and second difference values for each of the categories would be reliable,
      • a second feature extraction module (132) that expresses features of the pattern as a second feature vector, and
      • a second feature transform module (134) that uses second transform matrices to transform the second feature vector to generate a second transformed feature vector corresponding to each of the categories;
    • the recognition dictionary (120, 122, 138) additionally stores second transformed matching information for each of the categories, the second transformed matching information having been transformed using the second transform matrices;
    • the recognition section includes a third recognition module (136) that generates a third difference value for each of the categories by performing a matching operation between the second transformed matching information and a third matching vector derived from the second transformed feature vector corresponding to each of the categories; and
    • the categorizer (164) identifies the one of the categories to which the pattern belongs in response to:
      • the first difference value for each of the categories alone when the first reliability determination module (112) indicates that pattern recognition based on the first difference value for each of the categories would be reliable,
      • the first and second difference values for each of the categories alone when the second reliability determination module (162) indicates that pattern recognition based on the first and second difference values for each of the categories would be reliable, and
      • the first, second and third difference values for each of the categories otherwise.
  5. The pattern recognition apparatus of claim 2, in which:
    • a serial arrangement of the first feature extraction module (108) and the first recognition module (110) constitutes a first recognition unit;
    • a serial arrangement of the first feature transform module (114) and the second recognition module (116) collectively constitute a second recognition unit; and
    • the pattern recognition apparatus additionally comprises an additional recognition unit (132, 134, 136) including a serial arrangement of:
      • at least one of a feature extraction module (132) and a feature transform module (134), and
      • a recognition module (136) including a transformed recognition dictionary (138) optimized to recognize patterns not reliably recognized by the first and second recognition units.
  6. The pattern recognition apparatus of claim 3 or 4 in which:
    • the first feature vector generated by the first feature extraction module expresses a first set of the features of the pattern; and
    • the second feature vector generated by the second feature extraction module expresses a second set of the features of the pattern.
  7. The pattern recognition apparatus of claim 6, in which the first set of features and the second set of features partially overlap.
  8. The pattern recognition apparatus of claim 1, in which:
    • the first feature extraction module (142) expresses a first set of the features of the pattern as the first feature vector and
    • additionally expresses a second set of the features of the pattern as a second feature vector;
    • the first feature transform module (114) transforms all of the first feature vector to generate a first transformed feature vector corresponding to each of the categories; and
    • the apparatus additionally comprises a feature vector combining module (146) that combines the second feature vector and the first transformed feature vector corresponding to each of the categories to generate the at least partially transformed first feature vector corresponding to each of the categories, the feature vector combining module being interposed between the first feature extraction module and the recognition section (148).
  9. The pattern recognition apparatus of claim 8, in which:
    • the second feature vector has a number of dimensions;
    • the apparatus additionally comprises a dimension reduction module (144) that reduces the number of dimensions of the second feature vector to generate a dimension-reduced second feature vector, the dimension reduction module being interposed between the first feature extraction module and the feature vector combining module; and
    • the feature vector combining module (146) combines the dimension-reduced second feature vector and the first transformed feature vector corresponding to each of the categories to generate the at least partially transformed feature vector corresponding to each of the categories.
  10. The pattern recognition apparatus of claim 9, in which the feature vector combining module generates the combined feature vector by extracting a subset of at least one of:
    • the dimension-reduced second feature vector, and the first transformed feature vector corresponding to each of the categories.
  11. A method for recognizing patterns, the method comprising:
    • receiving (102) input patterns including a pattern belonging to one of plural categories constituting a category set, wherein the transform matrices include a transform matrix for each category of said category set, wherein a transform matrix for a category is generated in response to a rival pattern set for said category, said rival pattern set comprising rival patterns misrecongnized as belonging to said category, wherein said transform matrix is obtained on the basis of the difference between feature vectors in the rival pattern set and the reference feature vector for said category;
    • expressing (108) features of the pattern as a feature vector;
    • transforming (114) at least part of the feature vector using transform matrices to generate an at least partially transformed feature vector corresponding to each of the categories;
    • performing (116) a matching operation between:
      • matching information and transformed matching information for each of the categories, the transformed matching information being matching information transformed using the transform matrices, and
      • a matching vector derived from the at least partially transformed feature vector corresponding to each of the categories, to generate at least one difference value for each of the categories; and identifying (118) the one of the categories to which the pattern belongs in response to the at least one difference value.
  12. The method of claim 11, in which the transform matrices include a transform matrix for one of (a) a category belonging to the category set, and (b) a category subset composed of plural ones of the categories belonging to the category set, the transform matrix being generated by:
    • receiving (10) training patterns whose respective categories are defined and expressing features of the training patterns as first feature vectors;
    • identifying (12) the categories to which the training patterns respectively belong by performing a matching operation between first matching vectors derived from the first feature vectors and the matching information;
    • comparing (14) the categories to which the training patterns are identified as belonging with the respective defined categories to define a rival pattern set for a respective one of (a) the category, and (b) the category subset;
    • determining (16) an average vector from the feature vectors of all of the training patterns defined as belonging to the respective one of (a) the category, and (b) the category subset;
    • calculating (18) a difference vector for each of the training patterns belonging to the rival pattern set using the average vector;
    • calculating (20) an autocorrelation matrix of the difference vectors; and
    • adopting (22) eigenvectors of the autocorrelation matrix as transform vectors constituting the transform matrix for the respective one of (a) the category, and (b) the category subset.
  13. The method of claim 12, in which:
    • the eigenvectors of the autocorrelation matrix have respective eigenvalues; and
    • adopting eigenvectors includes:
      • summing the eigenvalues of all of the eigenvectors of the autocorrelation matrix to generate a first sum value, and
      • adopting the eigenvectors in order of descending eigenvalues as adopted eigenvectors and summing the eigenvalues of the adopted eigenvectors to generate a second sum value until the second sum value exceeds a predetermined fraction of the first sum value.
  14. The method of claim 13, in which:
    • the method additionally comprises:
      • calculating a covariance matrix from the feature vectors of all of the training patterns defined as belonging to the category, and
      • multiplying the covariance matrix by the autocorrelation matrix to generate a product matrix; and
      • in adopting eigenvectors, eigenvectors of the product matrix are adopted instead of eigenvectors of the autocorrelation matrix as the transform vectors of the transform matrix.
  15. The method of any one of claims 12-14, in which the transformed recognition information for a category belonging to the category set is generated by:
    • receiving (10) training patterns whose respective categories are defined and expressing features of the training patterns as feature vectors;
    • identifying (12) the categories to which the training patterns respectively belong by performing a matching operation between a first matching vector derived from the first feature vector and the matching information;
    • comparing (14) the categories to which the training patterns are identified as belonging with the respective defined categories to define a rival pattern set for the category;
    • transforming (30) the feature vectors of the training patterns using the transform matrix for one of (a) the category and (b) a category subset to which the category belongs, the category subset being composed of plural ones of the categories belonging to the category set, to generate respective transformed feature vectors;
    • performing (32) a discriminant analysis using the transformed feature vectors to generate a discriminant function;
    • calculating (34) a modified difference value for each of the categories using the discriminant function;
    • re-identifying (36) the categories to which the training patterns respectively belong in response to the modified difference value for each of the categories;
    • re-comparing (38) the categories to which the training patterns are identified as belonging in response to the new difference values with the respective defined categories to determine whether additional patterns are misrecognized as belonging to the category; and
    • generating (40) the transformed recognition information using the discriminant function when no additional patterns are misrecognized, and otherwise including (42) the additional patterns in the rival pattern set of the category, and repeating the discriminant analysis performing, modified difference value calculating, category re-identifying and re-comparing operations until no additional patterns are misrecognized.
  16. The method of any one of claims 12-15, in which:
    • the method additionally comprises:
      • performing a matching operation (110) between the matching information (120) for each of the categories and a first matching vector derived from the feature vector to generate a first difference value for each of the categories;
      • in response to the first difference values, generating a reliability indication (112) indicating when pattern recognition based on the first difference values would be reliable;
    • the one of the categories to which the pattern belongs is identified (118) in response to a sum of the first difference value for each of the categories, and a multiple of the second difference value for each of the categories when the reliability indication indicates that pattern recognition based on the first difference values would not be reliable; and the multiple is determined by:
      • setting the multiplier to an initial value,
      • receiving training patterns whose respective categories are defined,
      • performing the expressing, first matching operation performing, reliability indication generating operations on the training patterns to identify as identified training patterns the training patterns for which the reliability indication indicates that pattern recognition based on the first difference values would not be reliable as identified training patterns,
      • performing the transforming operation on the feature vectors of the identified training patterns, and
      • performing the following sequence on the identified training patterns until the multiplier has a value corresponding to a maximum recognition accuracy:
        • performing the second matching and identifying operations;
        • comparing the categories to which the identified training patterns are identified as
        • belonging with the respective defined categories
        • to determine a recognition accuracy; and
        • changing the multiplier.
Anspruch[fr]
  1. Dispositif de reconnaissance de forme comprenant :
    • une section d'entrée (102) qui reçoit des formes entrées incluant une forme appartenant à l'une de plusieurs catégories constituant un jeu de catégories,
    • un premier module d'extraction de caractéristiques (108) qui exprime les caractéristiques de la forme comme un premier vecteur de caractéristiques ;
    • un premier module de transformée de caractéristiques (114) qui utilise des matrices de transformées pour transformer au moins une partie du premier vecteur de caractéristiques pour générer un premier vecteur de caractéristiques au moins partiellement transformé correspondant à chacune des catégories, dans lequel les matrices de transformées incluent une matrice de transformées pour chaque catégorie dudit jeu de catégorie, dans lequel une matrice de transformées pour une catégorie est générée en réponse à un jeu de formes rivales pour ladite catégorie, ledit jeu de formes rivales comprenant des formes rivales faussement reconnues comme appartenant à ladite catégorie, dans laquelle ladite matrice de transformée est obtenue sur la base de la différence entre les vecteurs de caractéristiques dans le jeu de formes rivales et le vecteur de caractéristiques de référence pour ladite catégorie ;
    • une section de reconnaissance incluant un dictionnaire de reconnaissance (120, 122) qui stocke des informations de mise en concordance et les premières informations de mise en concordance transformées pour chacune des catégories, les premières informations de mise en concordance transformées ayant été transformées en utilisant les matrices de transformées et qui génèrent au moins une valeur do différence pour chacune des catégories en effectuant une opération de mise en concordance entre :
      • les informations de mise en concordance et les premières informations de mise en concordance transforméess, et
      • au moins un vecteur de mise en concordance dérivé au moins du premier vecteur de caractéristiques au moins partiellement transformé correspondant à chacune des catégories ; et
      • un formateur de catégorie (118) qui identifie celle des catégories à laquelle la forme appartient en réponse à au moins une valeur de différence.
  2. Dispositif de reconnaissance de forme selon la revendication 1, dans lequel :
    • le premier module de transformée de caractéristiques transforme l'intégralité du premier vecteur de caractéristiques pour générer un premier vecteur de caractéristiques transformé correspondant à chacune des catégories ;
    • la section de reconnaissance comprend :
      • un premier module de reconnaissance (110) qui génère une première valeur de différence pour chacune des catégories en effectuant une opération de mise en concordance entre les informations de mise en concordance et un premier vecteur de mise en concordance dérivé du premier vecteur de caractéristiques, et
      • un second module de reconnaissance (116) qui génère une seconde valeur de différence pour chacune des catégories en effectuant une opération de mise en concordance entre la première information de mise en concordance transformées et un second vecteur de mise en concordance dérivé du premier vecteur de caractéristiques transformé correspondant à chacune des catégories ;
      • le dispositif comprend additionnellement un module de détermination de fiabilité (11 2) qui reçoit la première valeur de différence pour chacune des catégories et qui indique quand la reconnaissance de forme basée sur la première valeur de différence pour chacune des catégories devrait être fiable ; et
      • le formateur de catégorie identifie celle des catégories à laquelle la forme appartient en réponse à :
        • la première valeur de différence seule pour chacune des catégories lorsque le module de détermination de fiabilité indique que la reconnaissance de forme basée sur la première valeur de différence pour chacune des catégories devrait être fiable, et
        • la première valeur de différence et la seconde valeur de différence pour chacune des catégories autres.
  3. Dispositif de reconnaissance de forme selon la revendication 2, dans lequel :
    • le dispositif de reconnaissance de forme comprend additionnellement un second module d'extraction de caractéristiques (132) qui exprime les caractéristiques de la forme comme un second vecteur de caractéristiques, le second module d'extraction de caractéristiques étant interposé entre la section d'entrée (102) et le premier module de transformée de caractéristiques (134) ; et
    • le premier module de transformée de caractéristiques transforme le second vecteur de caractéristiques pour générer les vecteurs de caractéristiques transformés.
  4. Dispositif de reconnaissance de forme selon la revendication 2, dans lequel :
    • le dispositif comprend additionnellement :
      • un second module de détermination de fiabilité (162) qui reçoit les première et seconde valeurs de différence pour chacune des catégories et indique quand la reconnaissance de forme basée sur les première et seconde valeurs de différence pour chacune des catégories devrait être fiable,
      • un second module d'extraction de caractéristiques (132) qui exprime les caractéristiques de la forme comme un second vecteur de caractéristiques et,
      • un second module de transformée de caractéristiques (134) qui utilise des secondes matrices de transformées pour transformer le second vecteur de caractéristiques afin de générer un second vecteur de caractéristiques transformé correspondant à chacune des catégories ;
      • le dictionnaire de reconnaissance (120, 122, 138) stocke additionnellement des secondes informations de mise en concordance transformées pour chacune des catégories, les secondes informations de mise en concordance transformées ayant été transformées en utilisant les secondes matrices de transformées ;
      • la section de reconnaissance inclut un troisième module de reconnaissance (136) qui génère une troisième valeur de différence pour chacune des catégories en effectuant une opération de mise en concordance entre les secondes informations de mise en concordance transformées et un troisième vecteur de mise en concordance dérivé du second vecteur de caractéristiques transformé correspondant à chacune des catégories ; et
      • le formateur de catégorie (164) identifie celles des catégories à laquelle le modèle appartient en réponse :
        • à la première valeur de différence pour chacune des catégories seule lorsque le premier module de détermination de fiabilité (112) indique que la reconnaissance de forme basée sur la première valeur de différence pour chacune des catégories devrait être fiable,
        • aux première et seconde valeurs de différence pour chacune des catégories seule lorsque le second module de détermination de fiabilité (162) indique que la reconnaissance de forme basée sur les première et seconde valeurs de différence pour chacune des catégories devrait être fiable, et
        • aux première, seconde et troisième valeur de différence pour chacune des catégories autres.
  5. Dispositif de reconnaissance de forme selon la revendication 2, dans lequel :
    • un agencement sériel du premier module d'extraction de caractéristiques (108) et du premier module de reconnaissance (110) constitue une première unité de reconnaissance ;
    • un agencement sériel du premier module de transformée de caractéristiques (114) et du second module de reconnaissance (116) constitue collectivement une seconde unité de reconnaissance ; et
    • le dispositif de reconnaissance de forme comprend additionnellement une unité de reconnaissance additionnelle (132, 134, 136) incluant un agencement sériel :
      • d'au moins l'un d'un module d'extraction de caractéristiques (132) et d'un module de transformée de caractéristiques (134), et
      • d'un module de reconnaissance (136) incluant un dictionnaire de reconnaissance transformée (138) optimisé pour reconnaître des formes non reconnues fiablement par les première et seconde unités do reconnaissance.
  6. Dispositif de reconnaissance de forme selon la revendication 3 ou 4 dans lequel :
    • le premier vecteur de caractéristiques généré par le premier module d'extraction de caractéristiques exprime un premier jeu de caractéristiques de la forme ; et
    • le second vecteur de caractéristiques généré par le second module d'extraction de caractéristiques exprime un second jeu de caractéristiques de la forme.
  7. Dispositif de reconnaissance de forme selon la revendication 6, dans lequel le premier jeu de caractéristiques et le second jeu de caractéristiques se chevauchent partiellement.
  8. Dispositif de reconnaissance de forme selon la revendication 1, dans lequel :
    • le premier module d'extraction de caractéristiques (142) exprime un premier jeu des caractéristiques de la forme comme premier vecteur de caractéristiques et
    • exprime additionnellement un second jeu des caractéristiques de la forme comme second vecteur de caractéristiques ;
    • le premier module de transformée de caractéristiques (114) transforme l'intégralité du premier vecteur de caractéristiques pour générer un premier vecteur de caractéristiques transformé correspondant à chacune des catégories ; et
    • le dispositif comprend additionnellement un module de combinaison de vecteurs de caractéristiques (146) qui combine le second vecteur de caractéristiques et le premicr vecteur de caractéristiques transformé correspondant à chacune des catégories pour générer le premier vecteur de caractéristiques au moins partiellement transformé correspondant à chacune des catégories, le module de combinaison de vecteurs de caractéristiques étant interposé entre le premier module d'extraction de caractéristiques et la section de reconnaissance (148).
  9. Dispositif de reconnaissance de forme selon la revendication 8, dans lequel :
    • le second vecteur de caractéristiques possède un certain nombre de dimensions ;
    • le dispositif comprend additionnellement un module de réduction de dimension (144) qui réduit le nombre de dimensions du second vecteur de caractéristiques pour générer un second vecteur de caractéristiques de dimensions réduites, le module de réduction de dimension étant interposé entre le premier module d'extraction de caractéristiques et le module de combinaison de vecteur de caractéristiques ; et
    • le module de combinaison de vecteur de caractéristiques (146) combine le second vecteur de caractéristiques de dimensions réduites et le premier vecteur de caractéristiques transformé correspondant à chacune des catégories pour générer le vecteur de caractéristiques au moins partiellement transformé correspondant à chacune des catégories.
  10. Dispositif de reconnaissance de forme selon la revendication 9, dans lequel le module de combinaison de vecteurs de caractéristiques génère le vecteur de caractéristiques combiné par extraction d'un sous-jeu d'au moins l'un :
    • du second vecteur de caractéristiques de dimensions réduites et du premier vecteur de caractéristiques transformé correspondant à chacune des catégories.
  11. Procédé de reconnaissance de forme, le procédé comprenant :
    • la réception (102) de formes entrées incluant une forme appartenant à l'une de plusieurs catégories constituant un jeu de catégorie, dans lequel les matrices de transformées incluent une matrice de transformée pour chaque catégorie dudit jeu de catégories, dans lequel une matrice de transformée pour une catégorie est générée en réponse à un jeu de formes rivales correspondant à ladite catégorie, ledit jeu de formes rivales comprenant des formes rivales faussement reconnues comme appartenant à ladite catégorie, dans lequel ladite matrice de transformée est obtenue sur la base de la différence entre les vecteurs de caractéristiques du jeu de formes rivales et du vecteur de caractéristiques de référence pour ladite catégorie ;
    • l'expression (108) de caractéristiques de la forme comme vecteur de caractéristiques ;
    • la transformation (114) d'au moins une partie du vecteur de caractéristiques en utilisant des matrices de transformées pour générer un vecteur de caractéristiques au moins partiellement transformé correspondant à chacune des catégories ;
    • la conduite (116) d'une opération de mise en concordance entre :
      • des informations de mise en concordance et des informations de mise en concordance Lransformées pour chacune des catégories, les informations de mise en concordance transformées étant des informations de mise en concordance transformées en utilisant les matrices de transformées, et
      • un vecteur de mise en concordance dérivé du vecteur de caractéristiques au moins partiellement transformé correspondant à chacune des catégories, pour générer au moins une valeur de différence pour chacune des catégories ; et l'identification (118) de celle des catégories à laquelle la forme appartient en réponsc à la au moins une valeur de différence.
  12. Procédé selon la revendication 11, dans lequel les matrices de transformées incluent une matrice de transformée pour l'une (a) d'une catégorie appartenant au jeu de catégorie, et (b) d'un sous-ensemble de catégories composé d'une pluralité de celles des catégories appartenant au jeu de catégorie, la matrice de transformée étant générée en :
    • recevant (10) des formes d'apprentissage dont les catégories respectives sont définies et en exprimant les caractéristiques des formes d'apprentissage comme premier vecteur de caractéristiques ;
    • identifiant (12) les catégories auxquelles les formes d'apprentissage appartiennent respectivement en effectuant une opération de mise en concordance entre des premiers vecteurs de mise en concordance dérivés des premiers vecteurs de caractéristiques et les informations de mise en concordance ;
    • comparant (14) les catégories auxquelles les formes d'apprentissage sont identifiées comme appartenant aux catégories définies respectives pour définir un jeu de formes rivales correspondant à l'un respectif (a) de la catégorie et (b) du sous-jeu de catégories ;
    • déterminant (16) un vecteur moyen à partir des vecteurs de caractéristiques de toutes les formes d'apprentissage définies comme appartenant à l'un respectif (a) de la catégorie et (b) du sous-ensemble de catégories ;
    • calculant (18) un vecteur de différence pour chacune des formes d'apprentissage appartenant au jeu de formes rivales en utilisant le vecteur moyen ;
    • calculant (20) une matrice d'autocorrélation des vecteurs de différences ; et
    • adoptant (22) les vecteurs propres de la matrice d'autocorrélation comme vecteurs de transformée constituant la matrice de transformée correspondant à l'un respectif (a) de la catégorie et (b) du sous-jeu de catégories.
  13. Procédé selon la revendication 12, dans lequel :
    • les vecteurs propres de la matrice d'autocorrélation ont des valeurs propres respectives ; et
    • l'adoption de vecteurs propres inclut :
      • la sommation des valeurs propres de tous les vecteurs propres de la matrice d'autocorrélation pour générer une première valeur de somme, et
      • l'adoption des vecteurs propres dans l'ordre des valeurs propres descendantes comme vecteurs propres adoptés et la sommation des valeurs propres des vecteurs propres adoptés pour générer une seconde valeur de somme jusqu'à ce que la seconde valeur de somme excède une fraction prédéterminée de la première valeur de somme.
  14. Procédé selon la revendication 13, dans lequel :
    • le procédé comprend additionnellement
    • le calcul d'une matrice de co-variance à partir des vecteurs de caractéristiques de toutes les formes d' upprentissage definies comme appartenant à la catégorie, et
    • la multiplication de la matrice de co-variance par la matrice d'autocorrélation pour générer une matrice de produit ; et
    • dans l'adoption des vecteurs propres, les vecteurs propres de la matrice de produit sont adoptés au lieu des vecteurs propres de la matrice d'autocorrélation comme les vecteurs de transformées de la matrice de transformée.
  15. Procédé selon l'une quelconque des revendications 12 à 14, dans lequel les informations de reconnaissance transformées pour une catégorie appartenant au jeu de catégorie sont générées par :
    • la réception (10) des formes d'apprentissage dont les catégories respectives sont définies et l'expression de caractéristiques des formes d'apprentissage comme vecteurs de caractéristiques ;
    • l'identification (12) des catégories auxquelles les formes d'apprentissage appartiennent respectivement en effectuant une opération de mise en concordance entre un premier vecteur de mise en concordance dérivé du premier vecteur de caractéristiques et les informations de mise en concordance ;
    • la comparaison (14) des catégories auxquelles les formes d'apprentissage sont identifiées comme appartenant aux catégories définies respectives pour définir un jeu de formes rivales pour la catégorie ;
    • la transformation (30) des vecteurs de caractéristiques des formes d'apprentissage en utilisant la matrice de transformée pour l'un (a) de la catégorie et (b) d'un sous-ensemble de catégories auquel la catégorie appartient, le sous-ensemble de catégories étant composé d'une pluralité de celles des catégories apparLenanL au jeu de catégorie, pour générer des vecteurs de caractéristiques transformés respectifs ;
    • la conduite (32) d'une analyse discriminatoire utilisant les vecteurs de caractéristiques transformées pour générer une fonction discriminante ;
    • le calcul (34) d'une valeur de différence modifiée pour chacune des catégories en utilisant la fonction discriminante ;
    • la ré-identification (36) des catégories auxquelles les formes d'apprentissage appartiennent respectivement en réponse à la valeur de différence modifiée pour chacune des catégories ;
    • une re-comparaison (38) des catégories auxquelles les formes d'apprentissage sont identifiées comme appartenant en réponse aux nouvelles valeurs de différences aux catégories respectives pour déterminer si des formes additionnelles sont ou non faussement reconnues comme appartenant à la catégorie ; et
    • la génération (40) des informations de reconnaissance transformée en utilisant la fonction discriminante lorsque aucune forme additionnelle n'est faussement reconnue et, sinon, en incluant (42) les formes additionnelles dans le jeu de formes rivales de la catégorie puis en répétant l'analyse discriminante, en effectuant le calcul des valeurs de différences modifiées, en ré-identifiant les catégories puis en re-comparant les opérations jusqu'aucune forme additionnelle ne soit faussement reconnue.
  16. Procédé selon l'une quelconque des revendications 12 à 15, dans lequel :
    • le procédé comprend additionnellement :
      • l'exécution d'une opération (110) de concordance entre les informations de concordance (120) pour chacune des catégories et un premier vecteur de concordance dérivé du vecteur de caractéristiques pour générer une première valeur de différence pour chacune des catégories ;
      • en réponse aux premières valeurs de différences, la génération d'une indication (112) de fiabilité indiquant quand la reconnaissance de forme basée sur les premières valeurs de différence devrait être fiable ;
      • celle des catégories à laquelle la forme appartient est identifiée (118) en réponse à une somme de la première valeur de différence pour chacune des catégories, et à un multiple de la seconde valeur de différence pour chacune des catégories lorsque l'indication de fiabilité indique que la reconnaissance de forme basée sur les premières valeurs de différences ne devrait pas être fiable ; et le multiple est déterminé par :
        • l'établissement du multiplicateur à une valeur initiale,
        • la réception des formes d'apprentissage dont les catégories respectives sont définies,
        • l'exécution de l'expression, exécuter la première opération de mise en concordance, l'implémentation des opérations génératrices d'indications de fiabilité sur les formes d'apprentissage pour identifier comme formes d'apprentissage identifiées les formes d'apprentissage pour lesquelles l'indication de fiabilité indique que la reconnaissance de forme basée sur les premières valeurs de différence ne devrait pas être fiable comme formes d'apprentissage identifiées,
        • l'implémentation de l'opération de transformation sur les vecteurs de caractéristiques des formes d'apprentissage identifiées, et
        • l'exécution de la séquence suivante sur les formes d'apprentissage identifiées jusqu'à ce que le multiplicateur ait une valeur correspondant à une précision de reconnaissance maximale :
          • l'implémentation des secondes opérations de mise en concordance et d'identification ;
          • la comparaison des catégories auxquelles les formes d'apprentissage identifiées sont identifiées comme appartenant aux catégories définies respectives pour déterminer une précision de reconnaissance ; et
          • la modification du l'exécution de multiplicateur.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com