Character recognition method using correlation search

• US 5,150,425 A
• Filed: 08/30/1991
• Issued: 09/22/1992
• 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): Mancuso, Joseph
• Application Number:
  US07/752,801
• Time in Patent Office: 389 Days
• Field of Search: 382/14, 382/15, 382/42, 382/30, 382/34, 395/21, 395/20, 395/23, 395/77
• US Class Current: 382/161
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries

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 correlation coefficients between an unknown character and a trained set of characters (i.e., a font), (4) recognizing the unknown character as the trained character with the highest correlation coefficient above a threshold. The manner in which trained characters are chosen is described herein as a correlation search. Correlation search results in a fast means of correctly classifying an unknown character from a large training set, often on the second or third try, depending on the inner-correlations of the trained characters.

Claims

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

1) font training or 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 pixels 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) repeating steps (a) thru (c) for every image in the training set;

(e) creating a correlation matrix by computing a correlation coefficient for every trained character with every other trained character and storing such matrix in memory;

(f) defining a list of trained character possibilities for every unknown character to be recognized;

(g) setting an upper limit on the number of trained characters that will be tested for each unknown character;

2) recognizing unknown characters by;

(h) acquiring a two dimensional array of pixels;

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

(j) selecting one of the unknown characters found in step (i) and selecting an initial trained character from the list of trained character possibilities for the unknown character;

(k) computing a correlation coefficient between the selected unknown character and the trained character;

(l) performing step (v) and succeeding steps if the correlation coefficient exceeds a threshold;

(m) performing step (n) and succeeding steps if the correlation coefficient does not exceed a threshold;

(n) performing step (p) and succeeding steps if the limit on the number of trained characters to be tested defined in step (g) has been exceeded;

(o) performing step (r) and succeeding steps if the limit on the number of trained characters to be tested defined in step (g) has not been exceeded;

(p) determining that the unknown character is not recognizable;

(q) repeating step (j) and succeeding steps until all unknown characters have been processed;

(r) eliminating the previously selected trained character from the list of trained character possibilities for the unknown character;

(s) searching along the row of the correlation matrix defined in step (e) corresponding to the most recently selected trained character for an entry that most closely matches the correlation coefficient found in step (k) and selecting as the next trained character to be tested the trained character corresponding to the column of this entry with the requirement that this trained character be contained in the list of trained character possibilities for the unknown character;

(t) incrementing the count of the number of trained characters tested for the unknown character;

(u) repeating steps (k) and all succeeding steps;

(v) saving the currently selected trained character as a candidate character for classifying the unknown character;

(w) eliminating the currently selected trained character from the list of trained character possibilities for the unknown character;

(x) performing step (bb) and succeeding steps if there are more entries in the list of trained character possibilities for the unknown character;

(y) performing step (z) and succeeding steps if there are no more entries in the list of trained character possibilities for the unknown character;

(z) classifying the unknown character as the most recently defined candidate character;

(aa) repeating step (j) and succeeding steps until all unknown characters have been processed;

(bb) searching along the row of the correlation matrix defined in step (e) corresponding to the most recently defined candidate character for an entry that exceeds a threshold and selecting as the next trained character to be tested the trained character corresponding to the column of this entry with the requirement that this trained character be contained in the list of trained character possibilities for the unknown character;

(cc) performing step (z) and all succeeding steps if a trained character can not be found in step (bb);

(dd) performing step (ee) and all succeeding steps if a trained character can be found in step (bb);

(ee) computing a correlation coefficient of the most recently selected trained character and the unknown character;

(ff) replacing the candidate character with the most recently selected trained character if the correlation coefficient computed in step (ee) exceeds the correlation coefficient of the candidate character and the unknown character;

(gg) removing the most recently selected trained character from the list of trained character possibilities for the unknown character;

(hh) repeating step (x) and all succeeding steps.

2. The method of claim 1 wherein the initial trained character selection step (j) includes:

(a) randomly selecting the initial trained character from the list of trained character possibilities for the unknown character.

3. The method of claim 1 wherein the initial trained character selection step (j) includes:

(a) selecting the initial trained character from the list of trained character possibilities for the unknown character as the trained character with the highest frequency of occurrence based on previous unknown character classifications.

4. The method of claim 1 wherein:

(a) the trained character identification step (c) of claim 1 includes determining the height and width of each trained character and storing such results to memory;

(b) the unknown character location step (i) of claim 1 includes determining the height and width of each unknown character and storing such results to memory;

(c) the selecting the initial trained character step (j) of claim 1 includes the requirement that the height and width of the initially selected trained character be within a prescribed tolerance of the unknown trained character;

(d) the searching step (s) of claim 1 includes the additional requirement that the height and width of the trained character to be selected next be within a prescribed tolerance of the unknown trained character;

(e) the searching step (bb) of claim 1 includes the additional requirement that the height and width of the trained character to be selected next be within a prescribed tolerance of the unknown character.

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