System and process for constructing optimized prototypes for pattern recognition using competitive classification learning

• US 5,802,207 A
• Filed: 06/30/1995
• Issued: 09/01/1998
• Est. Priority Date: 06/30/1995
• Status: Expired due to Term

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Huang, Yea-Shian
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/497,030
• Time in Patent Office: 1,159 Days
• Field of Search: 382/155-161, 382/187, 382/224-229, 395/23-24
• US Class Current: 382/224
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries

Abstract

A system and process for performing character recognition is disclosed wherein inputted characters are compared to prototypes maintained in a predetermined database of the system to determine the best matching character. To generate the prototype database for use in recognition, training character samples are inputted and classified and prototypes, having feature value vectors, are generated for each class. The prototypes are optimized to improve the recognition capabilities of the database. The prototype feature value vectors are updated by only small amounts for abnormal prototypes that are much closer to the nearest class M than to the true class I. In addition, the updating of the prototype feature value vectors is performed so as to minimize an error in the selection of the prototypes. Finally, the distance between a training character sample and a prototype is determined so that features which better distinguish one character from another have a greater weight in determining the distance than those features which do not distinguish one character from another as well.

Claims

1. A method for optimizing prototypes of model characters for character recognition, said prototypes including at least one prototype feature value vector selected for each true class I into which inputted training character samples, of said model characters, are organized, said method comprising the step of:

for each training character sample, iteratively;

using a processor, electronically determining the nearest class M containing the nearest prototype to said training character sample,

using said processor, if said nearest class M is different from said true class I of said training character sample, electronically updating the value of at least some of said prototypes by a value which depends on;

##EQU30## where;

n is the iteration number,

O_M is the distance from said training character sample to said nearest prototype of said nearest class M,

O_I is the distance from said training character sample to the nearest prototype of said true class I, and

A(n) is a monotonically decreasing bandwidth parameter such that 0<

A(n+1)<

A(n) for all n.

2. The method of claim 1 wherein each of said training character samples has a feature value vector x comprising feature values x_i where i is an index that takes on a value from 1 to the maximum feature index N, said step of determining further comprising the step of:

using said processor, electronically determining the distance y^j_k between said training character sample feature value vector x and each j^th prototype feature value vector r^j_k of each k^th class, where k takes on a value from 1 to the maximum class index K, by evaluating;

##EQU31## where θ

_i is a normalization factor associated with said i^th feature.

3. The method of claim 1 wherein said step of updating further comprises the step of:

using said processor, electronically updating each of said normalization factors θ

_i by;

##EQU32## where μ

(n) is a monotnonically decreasing function which depends on A(n).

4. A method for optimizing prototypes of model characters for character recognition, said prototypes including at least one prototype feature value vector selected for each true class I into which inputted training character samples, of said model characters, are organized said method comprising the step of:

for each training character sample, iteratively;

using a processor, electronically determining the nearest class M containing the nearest prototype to said training character sample,

using said processor, if said nearest class M is different from said true class I of said training character sample, electronically updating the value of at least some of said prototypes by a value which depends on;

##EQU33## where;

n is the iteration number,

O_M is the distance from said training character sample to said nearest prototype of said nearest class M,

O_I is the distance from said training character sample to the nearest prototype of said true class I, and

A(n) is a monotonically decreasing bandwidth parameter such that 0<

A(n+1)<

A(n) for all n,

and further wherein each of said training character samples has a feature value vector x comprising feature values x_i, and wherein said step of updating updates each i^th feature value r^qM_Mi of said feature value vector r^qM_M of said q_M^th prototype feature value vector of said class M by the value;

##EQU34## and updates each i^th feature r^qI_Ii value of said feature value vector r^qI_I of said q_I^th nearest feature value vector of said class I by the value ##EQU35## where;

η

(n) is a monotonically decreasing function which depends on A(n),

θ

_i is a normalization factor associated with said i^th feature.

5. A method for optimizing prototypes of model characters for character recognition, said prototypes including at least one prototype feature value vector selected for each true class I into which inputted training character samples, of said model characters, are organized, said method comprising the step of:

for each training character sample, iteratively;

using a processor, electronically determining the nearest class M containing the nearest prototype to said training character sample,

using said processor, if said nearest class M is different from said true class I of said training character sample, electronically updating the value of at least some of said prototypes by a value which depends on;

##EQU36## where;

n is the iteration number,

O_M is the distance from said training character sample to said nearest prototype of said nearest class M,

O_I is the distance from said training character sample to the nearest prototype of said true class I, and

A(n) is a monotonically decreasing bandwidth parameter such that 0<

A(n+1)<

A(n) for all n,

and wherein each of said training character samples has a feature value vector x comprising feature values x_i where i is an index that takes on a value from 1 to the maximum feature index N, said step of determining further comprising the step of;

using said processor, electronically determining the distance y^j_k between said training character sample feature value vector x and each j^th prototype feature value vector r^j_k of each k^th class, where k takes on a value from 1 to the maximum class index K, by evaluating;

##EQU37## where θ

_i is a normalization factor associated with said i^th feature, and further wherein said step of determining the nearest class M further comprises the step of;

using said processor, electronically selecting, for each class k, the smallest distance z_k of said distances y^j_k wherein each class k comprises B_k prototypes, by evaluating;

##EQU38##

6. The method of claim 5 wherein said step of determining the nearest class M further comprises the step of:

using said processor, determining the distance to the nearest prototype of the nearest class M by evaluating;

##EQU39## and determining the distance to the nearest prototype of the true class I as Z_k for k=I.

7. A system for optimizing prototypes of model characters for character recognition, said prototypes including at least one prototype feature value vector selected for each true class I;

said each true class I comprising inputted training character samples, of said model characters, said training character samples, of said model characters being organized into said each true class I;

said system comprising;

a processor for, for each training character sample, iteratively, electronically determining the nearest class M containing the nearest prototype to said training character sample, and, if said nearest class M is different from said true class I of said training character sample, electronically updating the value of at least some of said prototypes by a value which depends on;

##EQU40## where;

n is the iteration number,

O_M is the distance from said training character sample to said nearest prototype of said nearest class M,

O_I is the distance from said training character sample to the nearest prototype of said true class I, and

A(n) is a monotonically decreasing bandwidth parameter such that 0<

A(n+1)<

A(n) for all n.

8. A system for optimizing prototypes of model characters for character recognition, said prototypes including at least one prototype feature value vector selected for each true class I into which inputted training character samples, of said model characters, are organized, which training character samples each comprise a feature value vector, said system comprising:

a neural network processor comprising a plurality of interconnected, hierarchically organized layers of processing nodes for iteratively processing each training character sample, one at a time, said neural network processor comprising;

a first hidden layer, comprising a plurality of processing nodes including one node corresponding to each j^th prototype of a class k for receiving each feature value x_i of an inputted training character sample feature value vector x and determining a distance y^j_k from said training character sample feature value vector x to a corresponding j^th prototype feature value vector r^j_k of a k^th class, having prototype feature values r^j_ki,

wherein each of said distances is determined according to;

##EQU41## where N is the total number of features, 1≦

I≦

N, and θ

_i is a normalization factor associated with said i^th feature, and wherein a change in θ

_i is determined in part by scaling θ

_i by a monotonically decreasing feature normalization factor weighting function.

9. A system for optimizing prototypes of model characters for character recognition, said prototypes including at least one prototype feature value vector selected for each true class I into which inputted training character samples, of said model characters, are organized, which training character samples each comprise a feature value vector, said system comprising:

a neural network processor comprising a plurality of interconnected, hierarchically organized layers of processing nodes for iteratively processing each training character sample, one at a time, said neural network processor comprising;

a first hidden layer, comprising a plurality of processing nodes including one node corresponding to each j^th prototype of a class k for receiving each feature value x_i of an inputted training character sample feature value vector x and determining a distance y^j_k from said training character sample feature value vector x to a corresponding j^th prototype feature value vector r^j_k of a k^th class, having prototype feature values r^j_ki,

wherein each of said distances is determined according to;

##EQU42## where N is the total number of features, 1<

i<

N, and θ

_i is a normalization factor associated with said i^th feature, and wherein said neural network processor further comprises;

a second hidden layer, comprising a second plurality of processing nodes including one node corresponding to each k^th class for receiving only those B_k distances y^j_k to prototypes of the same k^th class as said class to which said k^th node of said second hidden layer corresponds, and determining the minimum one z_k of said B_k distances y^j_k, and

an output layer comprising a third plurality of nodes including a first node corresponding to a nearest class M, for determining a distance O_M from said training character sample to the nearest prototype of said nearest class M by determining the minimum distance of said distances z_k, and a second node for determining a distance O_I from said training character sample to the nearest prototype of said true class I by selecting said distance z_k for k=I, wherein B_k is the total number of prototypes per class K.

10. The system of claim 9 wherein said neural network processor further comprises:

an input layer, comprising a fourth plurality of processing nodes, including one node corresponding to each i^th feature for receiving a corresponding i^th training character sample feature value x_i.