Image analysis – Pattern recognition – Classification
Reexamination Certificate
2002-01-04
2004-08-17
Mehta, Bhavesh M. (Department: 2721)
Image analysis
Pattern recognition
Classification
C382S159000, C382S209000, C382S197000, C706S020000, C706S025000, C706S026000
Reexamination Certificate
active
06778704
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to pattern recognition and in particular relates to a pattern recognition method and apparatus that uses partitioned categories to provide an improved recognition accuracy.
BACKGROUND OF THE INVENTION
Pattern recognition is the process by which a hand written or printed pattern is converted to a pattern signal representing the pattern, a determination is made of what pattern the pattern signal represents, and a code indicating the determined pattern is generated. For example, pattern representing an unknown character, such as the letter “A,” may be scanned by an electronic scanner. The scanner generates a pattern signal composed of array of a few thousand bytes that represent the unknown character. The signal representing the bit map is then analyzed to determine the identity of the unknown character represented by the pattern and to generate a code identifying the character. For example, the ASCII code 65 representing the letter A may be generated.
Most pattern recognition devices can only recognize pattern signals representing patterns that are members of a predetermined pattern set. For example, a simple pattern recognition device may only be capable of recognizing pattern signals representing the numerals 0 through 9. A more complex pattern recognition device may be capable recognizing pattern signals representing the letters and numerals that are members of a pattern set corresponding to the ASCII character set. Pattern recognition devices typically include a recognition dictionary divided into categories, one for each of the patterns in the pattern set that the device is capable of recognizing. The recognition dictionary stores a typical pattern signal for each category. For example, the above-mentioned simple pattern recognition device may include a recognition dictionary divided into ten categories, one for each of the numerals 0 through 9. The recognition dictionary stores a typical pattern signal for the numeral corresponding to each category. To recognize the pattern represented by an unknown pattern signal, the pattern recognition device performs a matching operation between the unknown pattern signal and the pattern signals stored in the recognition dictionary. The matching operation determines which of the pattern signals stored in the recognition dictionary is closest to the unknown pattern signal. The unknown pattern signal is then deemed to represent the pattern corresponding to the category whose typical pattern signal is closest to the unknown pattern signal.
Many pattern recognition devices reduce the complexity of the matching operation by expressing the unknown pattern signal and the typical pattern signals stored in the recognition dictionary as vectors. To prevent confusion, a vector extracted from an unknown pattern signal will be called a feature vector, and a vector representing a pattern signal stored in the recognition dictionary will be called a reference vector.
In many pattern recognition devices, the matching operation involves determining the distance between the unknown pattern signal and the typical pattern signal of each of the categories by matching the feature vector extracted from the unknown pattern signal with the reference vector of each category stored in the recognition dictionary. The unknown pattern signal is deemed to belong to the category for which the distance is the smallest. Known functions for representing the distance between two vectors include the Euclidean distance, the weighted Euclidean distance, and the Mahalanobis distance.
To improve the accuracy of the pattern recognition operation performed by a pattern recognition device, the pattern recognition device may be trained using known patterns of the same style as the unknown pattern. For example, a pattern recognition device for handwriting recognition may require the writer to write a set of known patterns or characters for training purposes. Alternatively, training may be performed using handwritten training pattern sets written by many writers.
One way of training the distance function is called Learning by Discriminant Analysis (LDA), and is described by the inventor in
Handprinted Numeral Recognition by Learning Distance Function
, IEICE TRANS. D-II, vol. J76-D-11, 9, 1851-59 (1993) (in Japanese). LDA trains such parameters of the distance function as the reference vector, weighting vector, and the constant term by using a weighted Euclidean distance or a quadratic discriminant function as an original distance function and by superposing a discriminant function onto the original distance function. The discriminant function is determined by applying linear discriminant analysis between the pattern set of each category and a rival pattern set for the category. The rival pattern set for each category is composed of patterns that are mis-recognized as belonging to the category when the original distance function is used.
LDA features using not only the linear term of the feature vector, but also using the quadratic term as the linear terms in a linear discriminant. Test results show that this type of training provides a marked improvement in recognition accuracy. Using the weighted Euclidean distance, a recognition accuracy comparable to those obtained using the Mahalanobis distance function or using a quadratic discriminant function was achieved. The Mahalanobis distance function and the quadratic discriminant function both require a great deal of processing and memory to implement, whereas the Euclidian distance requires little memory and has a short processing time.
Satisfactory as present results are, the recognition accuracy of pattern recognition devices using LDA is not perfect. Improving the recognition accuracy of pattern recognition devices that use LDA involves increasing the discrimination ability of the discriminant function to separate a given category pattern set from its rival pattern set. The discriminant function is expressed by a quadratic equation of each component of the feature vector in which the products between the components are omitted. Consequently, the boundary between the given category pattern set and its rival pattern set, that is, the locus where the value of the discriminant function is 0, lies parallel to the feature axis and lies in a quadratic plane symmetric with respect to the center, as shown in FIG.
1
.
It can be seen from
FIG. 1
that, although the category pattern set
1
of the category lies safely within the boundary
2
defined by the quadratic function, the spacing between the boundary and the perimeter of the category pattern set is such that the boundary encompasses small parts of the rival pattern sets
3
of the category. The discriminant function has a positive value outside the boundary, a negative value inside the boundary, and a value of zero at the boundary. The polarity of the discriminant function inside and outside the boundary
2
is indicated by the circled − and the circled +, respectively, in
FIG. 1. A
pattern belonging to the part of the rival pattern set encompassed by the boundary will have a smaller distance from the category after the discriminant function is superposed onto the original function than the distance obtained using the original function. The pattern may therefore be incorrectly recognized as belonging to the category.
In pattern recognition, the category pattern set of each category often has an asymmetric distribution in feature space. Moreover, since the patterns that belong to the rival pattern set of a category usually belong to many categories, the rival patterns are considered to enclose an asymmetric pattern set of the given category in feature space. When the category pattern set and the rival pattern set of a given category have the distribution described above, completely separating these sets by a symmetric quadratic plane is difficult, and the unknown patterns located near the periphery of the pattern pattern set are easily mis-recognized.
Accordingly, an inability to adequately handle the asymmetry of th
Deame Gregory
Mehta Bhavesh M.
LandOfFree
Method and apparatus for pattern recognition using a... 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 apparatus for pattern recognition using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for pattern recognition using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3351786