Character recognition method using optimally weighted correlation

• US 5,204,914 A
• Filed: 08/30/1991
• Issued: 04/20/1993
• Est. Priority Date: 08/30/1991
• Status: Expired due to Term

• Current Assignee: Videk, Inc. (Ribbon Communications, Inc.)
• Original Assignee: Eastman Kodak Company
• Inventors: Martin, Gregory J., Mason, James A., Cook, John F., Chen, Robert Y.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/753,150
• Time in Patent Office: 599 Days
• Field of Search: 382/14, 382/15, 382/30, 382/39, 382/9, 382/26, 382/36
• US Class Current: 382/161
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

A character recognition method comprising the following steps: (1) acquiring a two dimensional array of pixels, (2) locating an unknown character in the two dimensional array, (3) computing weighted correlation coefficients between the unknown character and a trained set of characters (i.e. a font), (4) recognizing the unknown character as the trained character with the highest weighted correlation coefficient above a threshold. The weights in the correlation calculations are adjusted to place more emphasis on those areas of a trained character that distinguishes it from all other trained characters in the training set. A method for optimally adjusting these weights is described herein.

Claims

1. A method of character recognition, comprising the steps of:

1) creating a font of trained characters by;

(a) acquiring an image composed of a two dimensional array of pixels;

(b) locating all of the characters in the image by selectively scanning columns or rows of a predetermined area of the image and comparing each pixel'"'"'s intensity with a reference level to determine the first pixel of each character and recording the location (column and row coordinates) of such pixel and identifying the other pixels adjacent to the first whose intensity also exceeds the reference level and recording the upper left and lower right coordinates of a box bounding each character;

(c) identifying (labeling) all located characters and entering such identified characters as trained characters in memory;

(d) creating a set of weights, initialized to a constant value, for all trained characters of the training set;

(e) computing a correlation matrix composed of weighted correlation coefficients for all possible pairs of trained characters comprising the trained character set;

(f) searching through the correlation matrix and identifying the character corresponding to the row of the correlation matrix containing the most highly correlated pair of trained characters;

(g) adjusting the weights of the trained character identified in (f);

(h) recomputing the row of the correlation matrix corresponding to the trained character identified in (f) using the adjusted weights computed in (g); and

(i) repeating steps (f) through (h) until the highest correlation in the correlation matrix is reduced to an acceptable level or until a maximum count is exceeded and eliminating those trained characters from this iterative process that have been selected an excessive number of times; and

2) recognizing unknown characters by;

(j) acquiring a two dimensional array of pixels;

(k) locating all unknown characters in a manner described in (b);

(l) computing weighted correlation coefficients using the weights determined in steps (a) through (i) between all unknown characters and the trained character set; and

(m) identifying all unknown characters as those trained characters with the highest weighted correlation coefficients above a threshold.

2. The method of claim 1 wherein the weights adjusting step (g) includes:

(a) computing the gradient of the weighted correlation coefficient with respect to the weights for the pair of characters identified in step (f) of claim 1; and

(b) subtracting a fixed scaled amount of the gradient from the weights of the trained character identified in step (f) of claim 1.

3. The method of claim 1 wherein the weights adjusting step (g) includes:

(a) computing the gradient of the weighted correlation coefficient with respect to the weights for the pair of characters identified in step (f) of claim 1;

(b) initializing a scaling constant;

(c) updating the scaling constant by adding a fixed small number to it;

(d) multiplying the gradient of step (a) by the scaling constant;

(e) subtracting the scaled gradient from a temporary version of the weights for the trained character identified in step (f) of claim 1;

(f) computing a weighted correlation coefficient for the pair of characters identified in step (f) of claim 1;

(g) saving the scaling constant and the weighted correlation coefficient in memory;

(h) repeating steps (c) through (g) to cover a range of scaling constants;

(i) selecting the scaling constant from the range of scaling constants that results in a maximum reduction of the weighted correlation coefficient; and

(j) using the scaling constant found in (i) to subtract a scaled amount of the gradient from the weights of the trained character identified in step (f) of claim 1.

4. The method of claim 1 wherein the weights adjusting step (g) includes:

(a) computing the gradient of the weighted correlation coefficient with respect to the weights for the pair of characters identified in step (f) of claim 1;

(b) initializing a scaling constant;

(c) undating the scaling constant by adding a fixed small number to it;

(d) multiplying the gradient of step (a) by the scaling constant;

(e) subtracting the scaled gradient from a temporary version of the weights for the trained character identified in step (f) of claim 1;

(f) computing a weighted correlation coefficient for the pair of characters identified in step (f) of claim 1;

(g) saving the scaling constant and the weighted correlation coefficient in memory;

(h) repeating steps (c) through (g) to cover a range of scaling constants;

(i) selecting the scaling constant from the range of scaling constants that results in a maximum reduction of the weighted correlation coefficient; and

(j) using a weighted linear combination of the scaling constant found in (i) and a fixed scaling constant to subtract a scaled amount of the gradient from the weights of the trained character identified in step (f) of claim 1.

5. The method of claim 1 wherein the weights adjusting step (g) includes:

(a) computing the gradient of the weighted correlation coefficient with respect to the weights for the pair of characters identified in step (f) of claim 1;

(b) determining the scaling constant for the gradient that results in a maximum reduction of the weighted correlation coefficient using Second Order Methods; and

(c) using the scaling constant found in (b) to subtract a scaled amount of the gradient from the weights of the trained character identified in step (f) of claim 1.

6. The method of claim 1 wherein the character location step (b) is provided by a connectivity algorithm.

7. The method of claim 1 wherein only the weights off the diagonal are adjusted in the weights adjusting step (g).