Clustering system for optical character reader

• US 5,187,751 A
• Filed: 07/22/1991
• Issued: 02/16/1993
• Est. Priority Date: 07/24/1990
• Status: Expired due to Fees

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Tanaka, Hideaki
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/733,041
• Time in Patent Office: 575 Days
• Field of Search: 382/14, 382/15, 382/36, 382/34, 382/30, 382/21, 382/48, 345/20, 345/21
• US Class Current: 382/225
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering

Abstract

In a clustering system for an optical character reader, feature vectors of character image data to be classified are stored in a first memory. The number of classes, and representative vectors for the respective classes which are previously provided are stored in a second memory. Values of the cosine of each of the feature vectors stored in the first memory and each of the representative vectors stored in the second memory are calculated by a cosine calculating unit. Then, each of the feature vectors is assigned to one of the classes from which the largest cosine value is calculated, and the largest cosine value is stored into a third memory. For each of the thus processed classes, a total sum vector calculating unit calculates a total sum vector from the feature vectors which belong to the respective class, using the largest cosine values for the respective feature vectors stored in the third memory as weights. The resulting weighted total sum vector is stored into the second memory as a new representative vector for the class so as to update the contents of the second memory. The cosine calculating unit, and total sum vector calculating unit are controlled to operate repeatedly, until a convergence judging unit judges that any feature vectors are not exchanged between the classes during the classification.

Claims

1. A clustering system for classifying data into a predetermined number of classes, comprising:

first memory means for storing feature vectors of said data;

second memory means for storing said predetermined number and representative vectors of said classes, said representative vectors being previously provided;

cosine calculating means for calculating the cosine of each of said feature vectors stored in said first memory means and each of said representative vectors stored in said second memory means;

classification means for assigning each of said feature vectors into one of said classes which indicates the largest cosine value;

third memory means for storing said largest cosine value for each of said feature vectors;

total sum vector calculating means for calculating, for each of said classes, a total sum vector from feature vectors of one of said classes, using a weight which is the largest cosine value for each of said feature vectors stored in said third memory means, and for storing said weighted total sum vector into said second means, thereby updating the contents of said second memory means; and

convergence judging means for controlling said cosine calculating means, classification means and total sum vector calculating means to operate repeatedly, until no feature vectors are exchanged between the classes as a result of the classification by said classification means.

2. An optical character reader comprising a clustering system for classifying character image data into a predetermined number of font classes, said clustering system comprising:

first memory means for storing feature vectors of said character image data;

second memory means for storing said predetermined number and representative vectors of said font classes, said representative vectors being previously provided;

cosine calculating means for calculating the cosine of each of said feature vectors stored in said first memory means and each of said representative vectors stored in said second memory means;

classification means for assigning each of said feature vectors into one of said classes which indicates the largest cosine value;

third memory means for storing said largest cosine value for each of said feature vectors;

total sum vector calculating means for calculating, for each of said classes, a total sum vector from feature vectors of one of said classes, using a weight which is the largest cosine value for each of said feature vectors stored in said third memory means, and for storing said weighted total sum vector into said second means, thereby updating the contents of said second memory means; and

convergence judging means for controlling said cosine calculating means, classification means and total sum vector calculating means to operate repeatedly, until no feature vectors are exchanged between the classes as a result of the classification by said classification means.

3. An optical character reader according to claim 2, wherein each of said representative vectors of said font classes is indicative of the feature of the font corresponding to the respective one of said font classes.

4. An optical character reader according to claim 2, wherein said font classes are used in a dictionary for character recognition.