Image analysis – Pattern recognition – Classification
Reexamination Certificate
1998-12-08
2001-03-20
Boudreau, Leo H. (Department: 2721)
Image analysis
Pattern recognition
Classification
C382S156000, C382S159000, C382S224000, C382S227000
Reexamination Certificate
active
06205247
ABSTRACT:
BACKGROUND OF THE INVENTION
Pattern recognition is becoming increasingly significant in the era of electronic data processing. Its range of use extends from automation technology to machine-based image and text processing, where it is used for automatic letter distribution (address reading) or to evaluate formulas or documents. The objective of pattern recognition is to allocate to a piece of electronically pre-processed image information an identification that reliably coincides with the true meaning of the pattern. Statistics-based pattern-recognition methods assess a digitized piece of image information with estimates from which the degree of association of the pattern with a class of patterns can be read. With K given target classes, the class whose estimation result corresponds to the maximum of all K estimates is generally awarded this assessment. A recognition system is more reliable the more frequently the target class estimated as the maximum class matches the true target class (meaning). A network classifier used to this point, which comprises a complete ensemble of two-class classifiers and has the task of discriminating the K target classes, is based on the fact that a two-class classifier is calculated for all possible K*(K−1)/2 class pairs. During a reading operation, for the present pattern, each of the two-class classifiers supplies an estimate of the association of the pattern with one of the two fundamental target classes. The result is K*(K−1)/2 estimates, which are not independent among themselves. From these K*(K−1)/2 estimates, K estimates are to be formed, one for each target class. The theory provides a mathematical rule for this relationship, which is described in Wojciech W. Siedlecki, A formula for multiclass distributed classifiers, Pattern Recognition Letters 15 (1994). The practice of classifiers demonstrates that the applicability of this rule is unsatisfactory, because the two-class classifiers supply no statistical conclusion probabilities as soon as they estimate a foreign pattern that is not part of their adapted class range. In practice, this means that shutoff mechanisms must deactivate those classifiers that are not responsible for the pattern as early as possible. The shutoff rules used to this point in practice are largely of a heuristic nature. Consequently, an element of arbitrariness that is not statistically controlled is factored into the processing of network classifiers. This rule-based iteration of variables that experience a measurable statistic behavior significantly worsens the recognition results. Rule-based iteration of network classifiers additionally prevents the possibility of effectively re-training the classifier system when the samples are changed. With 30 or more classes to be discriminated, the use of network classifiers also meets with fundamental problems:
1. The number of components (pair classifiers) to be stored increases quadratically with the number of classes (K* (K−1)/2).
2. An assessment and combination of the component-related estimates into a reliable total estimate becomes increasingly less reliable with a growing number of classes.
3. Adaptations of a network classifier to country-specific writing styles incur considerable costs in the adaptation phase.
OBJECTS AND SUMMARY OF THE INVENTION
The object of the invention is to create a statistics-based pattern-recognition method and an arrangement for executing the method, with which the outlined problems of the state of the technology are avoided, with a large class number and for justifiable costs, and which is capable of performing general recognition tasks in real time, avoiding a rule-based iteration of network classifiers.
A particular advantage attained with the invention is a significant increase in recognition reliability through the avoidance of heuristic shutoff rules. Following the selection of the two- or multi-class classifiers and the generation of the assessment classifier, the entire set of statistics of the application is represented in the moment matrix used as the basis of the assessment classifier. Because only the reduced sequence of the two- or multi-class classifiers need be stored together with the assessment classifier, the memory load is very economical. Because polynomial classifiers manage all operations following the image-feature preparation by means of addition, multiplication and arrangement of natural numbers, more complex calculations for example floating-point simulation on the target hardware, are completely omitted. Memory-hogging table-creating mechanisms can also be omitted. These circumstances permit the focus of the target hardware design to be optimizing the transit time. In one embodiment of the invention, the sum of the error squares in the discrimination space is selected as a scalar separation measure (classification measure). The advantage of this is that a ranking by contribution to the minimizing of the residual error is explicitly formed among the components over the course of the linear regression accompanying the calculation of the linear classifier. This ranking is utilized in selecting from the available two- or multi-class classifiers, which selection forms the reduced set of pair classifiers as a result. The method of minimizing the residual error is described in detail in Schurmann, Statistischer Polynomklassifikator [Statistical Polynomial Classifier], R. Oldenburg Verlag [Publisher], 1977.
Another embodiment uses the entropy in the distribution space of the estimation vectors as a scalar separation measure. To evaluate the entropy, the frequency of appearance of each state of all pair-classifier estimates over the quantity of all states must be determined. Then, the partial system that produces the least entropy is determined. In the embodiment, a large quantity of target classes is divided into numerous quantities of target classes, for which a selection of the two- or multi-class classifiers is made, and from this, the assessment classifier is generated. A resulting total estimate is then determined from the results of the assessment classifiers. The resulting total estimate can be calculated in various ways:
In one embodiment a Cartesian-expanded product vector is formed from the result vectors of the assessment classifiers, from which a resulting quadratic assessment classifier is formed which determines the total estimate.
2. A Cartesian product vector is also formed in a second embodiment. By means of a subspace transformation U, this vector is converted into a shortened vector, of which only the most crucial components corresponding to the eigenvalue distribution of the transformation matrix U are used to adapt a quadratic classifier. This quadratic classifier then maps the transformed and reduced vector for an estimation vector onto the target class.
3. Fundamentally, in another embodiment a meta-class classifier, which is trained over groups of class quantities, generates estimates for the groups prior to activation of the respective selection of the two- or multi-class classifiers. Afterward, the two- or multi-class classifiers for the characters of the groups whose estimated value lies above an established threshold are activated. To determine the total estimate, the group estimates are linked to the estimates of the respective, associated character-assessment classifiers for the character target classes according to a unified rule such that the sum of all character estimates obtained in this manner yields a number that can be normalized to 1. The first variation yields the most precise results with the most computational effort, while the second and third variations contribute to the reduction in the computational effort.
BRIEF DESCRIPTION OF THE DRAWINGS
The realization of the invention can be divided into five phases. Each phase of the invention is described in detail in the following section, with reference to a respective drawing. Shown are in:
FIG. 1
the procedure in the generation of a complete set of pair classifiers of a network clas
Breuer Thomas
Franke Jurgen
Hanisch Wilfried
Boudreau Leo H.
Kinberg Robert
Mariam Daniel G.
Siemens Aktiengesellschaft
Spencer George H.
LandOfFree
Method and arrangement for pattern recognition on the basis... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and arrangement for pattern recognition on the basis..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and arrangement for pattern recognition on the basis... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2536353