Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
1999-07-12
2002-10-15
Starks, Jr., Wilbert L. (Department: 2122)
Data processing: artificial intelligence
Neural network
Learning task
C705S028000
Reexamination Certificate
active
06466926
ABSTRACT:
TECHNICAL FIELD
The invention relates to pattern recognition methods, such as character recognition. In particular, the invention relates to a method that optimizes a recognition dictionary used in pattern recognition to enable the recognition dictionary to be able to better distinguish between patterns that are difficult to distinguish.
BACKGROUND OF THE INVENTION
Character recognition is typically implemented in the three stages that include preprocessing, feature extraction, and discrimination. During the preprocessing stage, size normalization of the input pattern and noise removal are performed. During the feature extraction stage, feature values that represent the shape of the character are extracted from each character pattern in the input pattern, and a feature vector representing the feature values is generated. Each feature represents a portion of the structure of the character pattern. Typical features include the length of stroke, the angle of stroke, and the number of loops. For example, when the feature is the number of loops, the feature may have one of the following values:
0: when the character pattern belongs to numeral “1”, “2” or “3,”
1: when the character pattern belongs to numeral “0”, “6” or “9,” and
2: when the character pattern belongs to numeral “8.”
Typically, many hundreds of feature values are extracted for each character pattern in the input pattern. The feature values are represented by a feature vector whose elements each represent the feature value of one of the features of the character pattern. A feature vector has a large number of dimensions, with 500 dimensions being typical.
During the discrimination stage, the feature vector of each character pattern in the input pattern is compared with a reference vector for each category. The character pattern is determined to belong to the category whose reference vector is closest to the feature vector of the character pattern. In character recognition, each category represents one character. For example, in numeral recognition, a category exists for each of the characters “0,” “1,”. . . , “9.”
The reference vectors are stored in a recognition dictionary. The recognition dictionary is statistically created from character patterns obtained from the handwriting of many people. Such character patterns are called “training patterns.” Before the character recognition system can be used for handwriting recognition, the recognition dictionary is created by a number of unspecified writers, where each writer provides a handwriting sample that includes a predetermined set of character patterns. The category to which each. of the character patterns in the set belongs is known. The feature vectors extracted from the character patterns in each category are averaged and each average vector is stored in the recognition dictionary as the reference vector for the category.
The effectiveness of a character recognition system is characterized by its recognition ratio. When character recognition is performed, one of the following results is obtained for each character pattern in the input pattern: (1) the category to which the character pattern belongs is correctly recognized; (2) the character pattern is successfully recognized as belonging to a category, but the character pattern is mis-read so that the category is incorrect; or (3) the character pattern is not recognized as belonging to any category. For example, when the character pattern is the numeral “1,” result (1) occurs when the character pattern is recognized as belonging to the category “1,” result (2) occurs when the character pattern is incorrectly recognized as belonging to the category “7,” for example, and result (3) occurs when the category to which the character pattern belongs cannot be recognized. The recognition ratio is the number of character recognition events that generate result (1) divided by the total number of character patterns in the input pattern. A successful character recognition system is one that has a recognition ratio close to unity (or 100%).
Two basic approaches may be used to increase the recognition ratio of a character recognition system. These approaches are:
(1) to describe the distribution of the features of each category as precisely as possible; and
(2) to emphasize the distribution differences between the categories.
Many known approaches to increasing the recognition ratio of character recognition systems concentrate on the first approach. These approaches have been successful, but only to a limited extent.
In
Handprinted Numerals Recognition by Learning Distance Function
, IEICE Trans. D-11, vol. J76-D-II, no. 9, pp. 1851-59 (September 1993), the inventor described Learning by Discriminant Analysis (LDA), a way of increasing the recognition ratio of character recognition systems based on the second approach. In particular, LDA increases the recognition ratio by reducing the number of incorrectly-recognized character patterns (result (2) above). In the LDA character recognition method, a discriminant function obtained by applying Fisher's linear discriminant analysis is superposed onto the original distance function between the feature vector of each character pattern in the input pattern and the reference vector of each category. The original distance function may be the weighted Euclidean distance or the quadratic discriminant function between the feature vector and the reference vectors.
Fisher's linear discriminant analysis is applied between the reference vector of each category and the feature vector of a rival pattern for the category. A rival pattern for category A, for example, is defined as a character pattern that belongs to a different category, e.g., category B, but is incorrectly recognized as belonging to category A. In this example, the rival pattern is incorrectly recognized as belonging to category A when the Euclidian distance between the feature vector of the rival pattern and the reference vector of category A is less than that between the feature vector of the rival pattern and the reference vector of category B, the category to which the rival pattern actually belongs.
In LDA, the linear discriminant analysis uses both the linear terms and the quadratic terms of the feature vector as linear terms. By applying the LDA pattern recognition method, multiple parameters in the distance function, such as the reference vector, the weighting vector and the constant term, can be determined at the same time. The use of the weighted Euclidean distance as the original distance function will be described in greater detail below.
The weighted Euclidean distance D(x) between the feature vector of a character pattern and the reference vector of a category can be described as follows:
D
(
x
)
=
∑
m
=
1
M
ω
m
(
x
m
-
μ
m
)
2
(
1
)
where x=(x
1
, . . . , x
M
)
t
represents the feature vector of the character pattern
&mgr;=(&mgr;
1
, . . . , &mgr;
M
)
t
represents the reference vector of the category, and
&ohgr;=(&ohgr;
1
, . . . , &ohgr;
M
)
t
represents the weighting vector, and
t denotes a transposition factor.
Subscripts denoting the index of the category have been omitted from equation (1) to simplify it.
To obtain the discriminant function F(x), LDA first performs a character recognition operation on an input pattern composed of a large set of training patterns. Each training pattern is determined to belong to the category for which the value of D(x) is lowest. The results of the character recognition operation are analyzed to identify, for each category, the training patterns that are incorrectly recognized as belonging to the category. The training patterns that are incorrectly recognized as belonging to a category constitute the rival pattern set for the category. The training patterns that are defined as belonging to each category constitute the in-category pattern set for the category. For example, training pattern x is defined as belonging to category A because the writer who wrote training pattern x did so in response to a reque
LandOfFree
Method for optimizing a recognition dictionary to... 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 for optimizing a recognition dictionary to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimizing a recognition dictionary to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2957832