US 5,204,914 AGrant
Character Recognition Method Using Optimally Weighted Correlation
Issue Date:1993-04-20
•7 Claims
•16 Drawing Sheets
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.
Metadata
Assignee
- Eastman Kodak Company
Inventors
- James A. Mason
- Gregory J. Martin
- Robert Y. Chen
- John F. Cook
Application Information
Application Number:US 7531508
Filing Date:1991-08-30
Priority Date:1991-08-30
Art Unit:266
Classifications
IPC:
G06K 968
Field of Search:
38214;15;30;39;9;26;36
Patent Drawings (16 sheets)
Description
Field of the Invention
This invention relates to weighted correlation methods for performing character recognition whereby the best match (i.e. highest correlation score) is used to select and classify an unknown character as a member of a trained set of characters. The correlations are computed from the two dimensional array of pixels for the unknown character and the training set of characters. In this specification, the term font training denotes the process of creating and storing all of the trained characters in a font. The term inspect denotes the process of recognizing each unknown character as one of the trained characters of a font. In this invention, the light value of each pixel is weighted to place more or less emphasis on its contribution to the overall correlation score. The weights are adjusted so as to provide optimal discrimination (decorrelation) among the characters in the training set. The method for automatically adjusting these weights is described herein.
Background of the Invention
Correlation is a technique well known to those skilled in the art of developing character recognition methods. The process of recognizing an unknown character using correlation is comprised of the following steps: (1) acquiring a two dimensional array of pixels, (2) locating an unknown character in the two dimensional array, (3) computing the correlations between the unknown character and every member of a trained set of characters (otherwise known as a font), (4) recognizing the unknown character as the trained character with the highest associated correlation coefficient above a threshold.
The correlation between an unknown character and a trained character can be conveniently described mathematically using vector notation. That is, let the vector y denote the light values (relative scene reflectance, intensities, etc.) of the pixels of the unknown character to be recognized. That is, let
where y.sub.i denotes the light value of the i-th pixel of the unknown character and .sup.T denotes the transpose operator. In this representation there are N pixels in the unknown character y. That is, the two dimensional array of pixels for the unknown character is represented as a one dimensional array by concatenating rows (or columns) into one vector.
In a similar manner, let x denote the vector of light values of a trained character from a font, i.e.
where x.sub.i denotes the light value of the i-th pixel of the trained character x. For simplicity, it is assumed that both the unknown character and the trained characters have the same number of pixels, N. If this were not true, the two vectors can be made the same size by appropriately increasing/decreasing the size of the unknown character y to that of the trained character x by utilizing the surrounding pixels in the image.
With these definitions, the correlation R.sub.xy between the unknown character y and the trained character x can be written as ##EQU1## where the sum is over all N pixels.
According to the above description, R.sub.xy is computed for all M trained characters of the font {x.sub.0, x.sub.1, . . . , x.sub.M } and unknown character y is recognized as being equivalent to that trained character x.sub.i that results in the highest correlation score among all the scores calculated.
An additional condition for a match is that the highest correlation score (R.sub.xy).sub.max exceed some predetermined threshold (R.sub.xy).sub.thresh. Otherwise, the unknown character does not match any trained characters from the font.
The above describes the standard method of performing character recognition using correlation of the light value of pixels of an unknown character and trained characters from a font. The above method may not work well when trained characters from a font are highly correlated among themselves and measurement noise is significant. For example, consider the letters O and Q of a particular font. These two characters can be quite similar (highly correlated) to each other. Depending on the font type and magnification selected in capturing the image, the O may only be distinguished from the Q by the light value of one or two pixels. This implies that the correlation score, R.sub.OQ, will be high and that discriminating an O from a Q can be difficult. In the presence of high levels of noise associated with capturing the image (i.e. video noise, sampling artifacts, lighting and printing variations), it is possible that an incorrect decision will be made and an O will be mistaken for a Q. For example, this can occur when the unknown character is a Q and R.sub.OQ exceeds R.sub.QQ. In this case, the Q is incorrectly classified (recognized) as an O.
There are several obvious approaches to reducing these types of errors. These approaches include: (1) choosing a font such that the trained characters are as dissimilar as possible; (2) increasing the magnification to generate more pixels that aid in better discriminating among the trained characters of the font; (3) reducing the system level of noise. Unfortunately, it is not always possible to alter these conditions. That is: (1) the font type may be dictated by the application; (2) magnification may be fixed by other constraints; (3) the system noise level may not be easily lowered.
Summary of the Invention
This invention describes another approach to minimizing classification errors in character recognition. In this invention, a method is developed that places more emphasis (higher weight) on those pixels that distinguish a trained character in a font from other highly correlated trained characters of the font. For the example cited above, more emphasis (increased weight) is placed on the pixels in the tail region of the Q for both the O and the Q.
In this invention, there are two separate processes in performing character recognition: font training and inspect. During font training, the trained characters are created and stored to memory for later use during inspect. Also, the weights for each trained character are optimally adjusted during font training using the method described herein. These weights are used during the inspect step to recognize all unknown characters.
The procedure for altering the weights of the pixels of a trained character is accomplished by introducing a weight (squared) matrix Z.sub.x for each trained character x in the font. Thus, Z.sub.x is an N.times.N matrix defined by
where ##EQU2## Note that although Z.sub.x is an N.times.N matrix, there are only N non-zero terms along the diagonal. These terms correspond to the individual weights (squared) for each pixel in the trained character x. Hence, the actual values that need to be stored for each trained character are the contents of the weight vector w=[w.sub.1, w.sub.2, . . . , w.sub.N ].sup.T.
Thus, each trained character x of a font has two associated vectors: an observation vector x and an associated weight vector w.sub.x.
The correlation R.sub.xy given above in equation (3) is modified to include the pixel weighting terms as follows: ##EQU3## where
and
In the above expressions, the weights w and weight (squared) z terms are associated with the trained character x. Equations (7) thru (13) show explicitly several different ways for computing the weighted correlation coefficient. That is, it can be computed in terms of the unknown character y and the trained character x and its associated weight (squared) matrix Z.sub.x or it can be computed in terms of a weighted trained character x.sub.w and a weighted unknown character y.sub.w. The two expressions are equivalent and provide insight into different approaches in implementing a weighted correlation algorithm.
Equations (7) thru (13) above show how a weighted correlation coefficient can be computed. The goal is to develop a method to adjust the weights w.sub.x for each trained character x.sub.i of a font such that the correlations of x.sub.i with every other trained character of the font {x.sub.j, j=1,2, . . . , M, j.sub.i i} are minimized. This is a constrained optimization problem and methods for solving these problems are well known to those skilled in the art. The approach to solving an optimization problem can be generally classified as either as a First Order Method or a Second Order Method. First Order Methods require the calculation of the first derivative of the function to be optimized. Typical First Order methods are the Gradient Method and the Steepest Ascent Methods. Second Order Methods require the calculation of the first and second derivatives of the function to be optimized. The Steepest Ascent Method is the simplest to implement and is described in this invention. The Gradient Method and the Second Order Methods can also be used and results in a reduction in the number of iterations to reach the optimum.
In order to compute the maximum/minimum of a function with respect to a set of variables, the gradient of the function with respect to those variables is computed using an initial guess (starting estimates) of those values. Next, the gradient is multiplied by a scaling constant and is added/subtracted to the initial estimates of the variables. The function is recomputed using the new estimates of the variables and tested to see if its value has increased/decreased sufficiently enough to stop the process. If not, the gradient is recomputed using the new estimates of the variables, scaled, and added to the previous estimates of the variables. The process is repeated until either: the maximum/minimum of the function is reached, no additional improvement is observed, or a maximum count of the number of iterations is exceeded.
The gradient of the correlation coefficient R.sub.xy, as defined in equation (7), with respect to the weights (squared) Z.sub.x is defined as
where .gradient..sub.Z is the gradient operator and is defined as .differential.``/.differential.Z.sub.x.
The i-th component of the gradient is easily shown (from equation (8)) to be
As stated above, in order to minimize R.sub.xy, the weights (squared) for the trained character x are adjusted recursively by subtracting a scaled version of the gradient, i.e.
where k is the time index, .alpha. is a scaling constant and the correction is understood to apply to the diagonal elements of the weight (squared) matrix (since the off-diagonal terms are always zero). This procedure is repeated until: the optimum is reached, no additional improvement is observed, or a maximum iteration count is exceeded.
For a single pair of trained characters, equation (15) shows that the gradient is a constant, independent of the weights. Thus, the optimum can be computed directly.
As a simple example, consider a font consisting of two trained characters x and y. Let x=[1 0].sup.T, y=[1 1].sup.T and ##EQU4## Then from equation (7), ##EQU5## From equation (15), the gradient is .gradient..sub.Z R.sub.xy =[1 0].sup.T. Since the initial weights are unity, then Z.sub.x (0)=W.sub.x (0) and application of equation (16) with .alpha.=1 results in ##EQU6## The new correlation is computed using equation (7) with the updated weight (squared) matrix as ##EQU7##
Thus, the trained character x has been decorrelated with the trained character y by adjusting x's weights.
In a similar manner the weights for trained character y are adjusted resulting in ##EQU8## and thus R.sub.xy =0, i.e. trained character y is no longer correlated with trained character x.
The above example, though contrived, illustrates the basic ideas in adjusting the trained characters weights. However, the weighted correlation as defined in equation (7) has some undesirable properties. Namely, the correlation R.sub.xy in equation (7) is sensitive to variations in illumination level and character contrast. (This is also true for the unweighted correlation as given in equation (3) above.) For the example cited above, doubling the intensity of character y to [2 2].sup.T results in an increase in the initial correlation from 1 to 2. Hence the correlation computation must be modified to render it insensitive to contrast and illumination level variations. This is accomplished by computing a weighted normalized mean-corrected correlation.
The weighted normalized mean-corrected correlation (squared) R.sup.2.sub.xy is defined as ##EQU9## where
are the mean-corrected characters where
and the i-th components of the mean vectors are given by
and Z.sub.x is the weight (squared) matrix as defined previously in equations (5) and (6).
Equation (17a) shows that the correlation (squared) R.sup.2.sub.xy is computed rather than the correlation R.sub.xy as a mathematical convenience to avoid having to compute the square root. Note that R.sup.2.sub.xy as given by equation (17a) is bounded in the range of zero to one and is insensitive to lighting or contrast variations. This can be easily proved (by those skilled in the art).
The gradient of the weighted normalized mean-corrected correlation (squared) with respect to the weights (squared) is defined as
The i-th component of the gradient is defined as:
By partial differentiation of (18), it can be shown that the i-th component of the gradient of the weighted normalized mean-corrected correlation (squared) is given by ##EQU10##
In a manner similar to that of equation (16), the weights are adjusted recursively to minimize R.sup.2.sub.xy by subtracting a scaled version of the gradient, i.e.
where k is the time index, and .alpha. is a scaling constant.
The object of this invention is to significantly reduce the possibility of incorrectly classifying an unknown character with respect to a trained character set (font). This is accomplished by placing more emphasis, i.e. increasing the weight, on those pixels that distinguish a trained character from every other trained character in the font and repeating this for every trained character in the font until the correlations among the trained characters in the font are reduced to an acceptable level or until it is determined that the correlations can not be reduced any further. More particularly, in accordance with this invention, a method of character recognition, comprises 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) 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) thru (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) thru (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.
Description of the Drawings
FIG. 1 is an illustration of an embodiment of the character recognition method in accordance with the present invention;
FIG. 2 is a schematic of the logic and control unit 40 of FIG. 1;
FIG. 3A thru 3D are flow charts illustrating an embodiment of the control logic followed by the logic and control unit 40 of FIG. 2. FIG. 3A shows the flow chart illustrating the decision logic to choose inspect or training. FIG. 3B shows the flow diagram for the inspect control logic. FIG. 3C shows the flow diagram for the Font Training logic. FIG. 3D shows the flow diagram illustrating the weight optimization portion of the Font Training logic;
FIGS. 4' and 4" shows an example of applying the weight adjustment procedure to a three character font; and FIGS. 5A', 5A", 5B', 5B", 5C, 5D, 5E' and 5E" shows an example of applying the weight adjustment procedure to a sixteen character font.
Attached is APPENDIX A which is a C Program for performing the weight adjustment. The various modules (C callable functions) of this program will be referred to with reference to the various items of FIG. 3C and FIG. 3D.
Detailed Description of the Preferred Embodiment
Referring to FIG. 1, there is shown the components of the preferred embodiment. There is a part 10 with printed characters 15 that are to be recognized. The part is moving on a conveyance unit 20 and is detected by an electro-optic sensor 30. Upon detection of the part, the electro-optic position sensor sends a signal to the sensor transducer unit 35. The transducer signals the logic and control unit 40 that the part is present in the field of view of the video camera 50 via the part detect cable 37.
Upon receipt of the part detect signal, the logic and control unit commands a stroboscopic light source 60 via the light source trigger cable 62 to generate a pulse of light given that the video camera is ready to capture the next video frame. The logic and control unit knows when the camera is ready to capture the next video frame since it controls the timing of the camera via the video synch cable 53.
The pulsed light from the stroboscopic light source illuminates the moving part via the fiber-optic bundle 65. The pulsed light essentially "freezes" the moving part and renders a sharp image of it when captured by the video camera 50.
Upon the capture of an image, the analog video signal is transferred from the camera to the logic and control unit 40 via the video cable 52. The logic and control unit displays the processed video image along with superimposed text on a video monitor 70 via the monitor cable 72. The type of information displayed on the monitor depends on whether the logic and control unit is in the training mode or the inspect mode, the details of which are described below with reference to FIGS. 3B and FIG. 3C. The example monitor display of FIG. 1 shows the results of an sample inspection. The captured image is displayed and boxes 73, 74 and 75 are drawn around the three characters that the logic and control unit has located in this example. Also shown on the monitor is textual information 76 indicating what classification the logic and control unit has assigned to the three located characters (in this example they are shown correctly classified as the letters `1`, `2`, and `3`) as the result of an inspection.
A keyboard 80 and a pointing device (mouse) 90 are also shown to provide a means for user input to the logic and control unit. The keyboard is interfaced to the logic and control unit via the keyboard cable 82. The pointing device is interfaced to the logic and control unit via the pointing device cable 92.
An interface to a host computer 100 provides a means for communicating the results of the inspection to another processing unit for defect sorting and/or statistical analyses.
FIG. 2 shows in block diagram form the components of the logic and control unit 40, the details of which are described below. A microprocessor 105 acts as the main controller of the logic and control unit and receives input and provides output to the other components of FIG. 2 via the address, data, and control bus 110. The microprocessor receives its' instructions from program code stored in nonvolatile memory (ROM) 120.
A part detect interface 130 receives the part detect signal from the sensor transducer unit 35 via the part detect cable 37. The part detect interface signals the microprocessor when a part is in the field of view of the video camera. The microprocessor triggers the light source 60 via the light source interface 140 at the precise instant in time when the camera 50 is capable of capturing a video frame. The camera control module 150 provides the timing signals to the camera via the video sync cable 53 and alerts the microprocessor when the camera is ready to capture the next video frame.
The analog video output from the camera is digitized and stored upon command from the microprocessor by the digitizer and frame store module 160. The digitized video is accessible by the microprocessor for locating characters and computing correlation coefficients in a manner described below with reference to FIGS. 3B thru 3D.
The data associated with the trained characters of a font are stored in a block of memory, preferably nonvolatile, labeled font memory 170. Font memory contains all the pixel data associated with each trained character including the mean vectors and the weight vectors that are used to compute weighted correlation coefficients. The trained character data are addressed by the microprocessor via a list of pointer references stored in the general purpose memory 180. The general purpose memory provides a means for storing additional data as described below with reference to FIGS. 3A thru 3D.
The video data from the digitizer and frame store 160 are displayed on a monitor by means of the video display module 190 and the monitor cable 72. The microprocessor has the capability of overlaying graphics and textual information on top of the video to provide the user a means of viewing the results of an inspection and to prompt the user during font training.
The keyboard interface module 200 and the pointing device interface module 210 provide the interface from the keyboard and pointing device units and alerts the microprocessor when a key is pressed.
The host communications module 220 provides the interface from the microprocessor to a host computer and provides the gateway for sending the results of an inspection for subsequent sorting or statistical analysis.
FIG. 3A shows a flow diagram illustrating a portion of the logic followed by the logic and control unit 40. Control begins with the main label 300. This is the beginning of the control loop. The user is then queried as to whether the unit is to inspect or a font is to be trained 310. This question appears on the video monitor 70. The user responds via the keyboard 80 or pointing device 90 and control is directed either to font training 320 or inspect 330.
FIG. 3B shows a flow diagram illustrating the inspect portion of the logic followed by the logic and control unit 40. Inspect begins with the inspect label 340 and is followed by the capture and digitization of an image 350 step upon the receipt of a part detect signal as discussed previously with reference to FIG. 1 and FIG. 2.
Next, all of the unknown characters are located in a predefined region of interest in the image 360. This is accomplished by selectively scanning columns or rows of the predefined area of the image and comparing the light value of each pixel with a reference value to determine the first pixel of each unknown 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 same reference level and thus determining and recording the upper left and lower right coordinates of a box bounding each character. Once all of the unknown characters have been located, each unknown character y.sub.i is then recognized by computing the weighted normalized mean-corrected correlation (squared) R.sup.2.sub.xy according to equation (17) with every trained character of the font x.sub.j j=1,2, . . . , M where M is the number of trained characters in the font 370.
Next, the trained character (x.sub.j).sub.max corresponding to the highest correlation (R.sup.2.sub.xy).sub.max is determined by sorting the correlation scores 380. A comparison is made of the highest correlation score (R.sup.2.sub.xy).sub.max with a predetermined threshold R.sub.thresh 390. If the threshold is exceeded, then the unknown character y.sub.i is identified as (x.sub.j).sub.max 400 and is reported to the user via the video monitor 70 and to the host computer via the host computer interface 100. Otherwise, the unknown character is judged as not recognizable 410 and is reported to the user and the host computer as such. A test is made to check for additional unknown characters 420 and if true then steps 370 thru 410 are repeated. The logic and control unit will loop back to capture another image if in a continuous inspect mode 430, otherwise it will branch back to main 440.
FIG. 3C shows a flow diagram illustrating the font training portion of the logic followed by the logic and control unit 40. Training begins with the font training label 450 and is followed by the capture and digitization of an image 460 step upon the receipt of a part detect signal as discussed previously with reference to FIG. 1 and FIG. 2.
Next, all of the characters are located in a predefined region of interest in the image 470. This is accomplished in exactly the same manner as the procedure described for locating characters in the inspect process of FIG. 3B. The located characters are displayed on the video monitor with a box bounding each character and the user is prompted for a label for each character. The pixel data for each character are then extracted from the image and saved as a trained character in the Font Memory 170 portion of the logic and control unit 480. In this manner, the font is built of trained characters for every image of the training set 490. Once the font has been defined, the weights can be adjusted for each trained character. For every trained character in the font, the weights are initialized to a constant value500. The module init.sub.-- pattern of the program in Appendix A performs this task.
Next, a correlation matrix R.sub.MxM of size MxM is computed 510. The correlation matrix contains the correlation score of every trained character with every other trained character in the font. The individual correlation scores are computed according to equation (17). The C program module get .sub.-- R.sub.-- matrix of Appendix A performs these computations.
Prior to adjusting the weights, several parameters must be initialized 520. These parameters include: max.sub.-- count sets the total number of iterations; max.sub.-- count.sub.-- per.sub.-- char sets the number of iterations allowed for each of the M trained characters in the font; alpha defines the scaling factor that is applied to the gradient when added to the old weights according to equation (20); R.sub.-- min is the desired correlation score for each trained character after weight adjustment; R.sub.-- max is the maximum value of the correlation matrix R.sub.M.times.M ; char.sub.-- count[M] and elim.sub.-- char[M] are arrays that are initialized to zero and are used to determine if a trained character has exceeded the parameter max.sub.-- count.sub.-- per.sub.-- char. The modules main and optimize.sub.-- R of the computer program in Appendix A show the initialization of these parameters. The next step is to optimize the weights as indicated by the label 530.
FIG. 3D shows a flow diagram that illustrates how the weights are adjusted for each trained character by the logic and control unit 40. The label optimize weights 540 indicates the start of this process. The process begins by testing whether the iteration count has exceed the parameter max.sub.-- count or whether the maximum value of the correlation matrix R.sub.-- max is less than the minimum desired correlation R.sub.-- min 550. If either of these tests are true then the weight adjustment process is done and control returns to main 560. Otherwise, the most highly correlated pair of trained characters (x.sub.1,X.sub.j).sub.max is determined by finding the largest entry of the font correlation matrix R.sub.M.times.M 570. The main diagonal terms (correlation score=100) are eliminated during this search. Also eliminated are any trained characters whose count has previously exceeded the parameter max.sub.-- count.sub.-- per.sub.-- char. The trained character (x.sub.i).sub.max corresponding to row i of the correlation matrix containing the maximum entry is thus selected as the trained character for weight adjustment. A test is performed first to check that the trained character (x.sub.i).sub.max has been called too many times 580. If it has, then it is eliminated from any further weight adjustment 590. Otherwise processing continues. For the program in Appendix A, the above three steps are handled by the module optimize.sub.-- R.
The next step is the adjustment of the weights of the trained character (x.sub.i).sub.max using the trained character pair (x.sub.i,x.sub.j).sub.max and the parameter alpha 600 by evaluating equations (19) and (20). The module adjust.sub.-- weight of the program in Appendix A adjusts the weights by computing the gradient (equation (19)) and adjusting the weight vector (equation (20)). The module adjust.sub.-- weight maintains the weights in the range of zero to 255, i.e. negative weights are not permitted, nor are weights above a maximum value (255). This is done to permit storing the weights in finite word length (8 bit) Font Memory 170.
The i-th row of the correlation (squared) matrix, corresponding to trained character (x.sub.i).sub.max, is recomputed next 610. The program module redo.sub.-- R.sub.-- matrix of Appendix A performs this task. Finally the iteration counters count and char.sub.-- count[i.sub.-- max] are incremented 620 and the logic and control unit branches back to the test 550 for another possible iteration.
FIG. 4 shows an example of applying the weight adjustment procedure to a three character font. The font is composed of the trained characters `O`, `Q`, and `D`. The mean patterns for three characters 630, 640, and 650 are seven pixels high by five pixels wide. The light value (intensity) of each pixel is digitized to 8 bits, i.e. 256 levels of gray. Note that the Q is distinguished from the O by only two pixels, the D is distinguished from the O by only two pixels and the D is distinguished from the Q by four pixels.
The initial weights of the O 660, Q 670, and D 680, are shown initialized to a constant value of 128 (i.e. half of full scale). The initial correlation (squared) matrix R.sub.3.times.3 690 shows high correlations among all three trained characters, especially the O and the Q.
The weights are adjusted as described above with regards to FIG. 3C and FIG. 3D and the computer program of Appendix A. The parameters are initialized as follows: max.sub.-- count=200, R.sub.-- min=1, and alpha=0.001. The final correlation matrix 700 shows that the three trained characters are essentially completely decorrelated since all off-diagonal terms are essentially zero. The final weight pattern for the O 710 shows that more emphasis is placed on the four pixels that distinguish the O from the Q and the D. In a similar manner, more emphasis is placed on the two pixels that sufficiently distinguish the Q 720 from the O and the D. Also there are only two pixels that distinguish the D 730 from the O and the Q.
FIG.'s 5A thru 5E show an example of applying the weight adjustment procedure for a sixteen character font. The mean patterns for the sixteen trained characters are shown in FIG. 5A. The characters are: 0 740, 1 741, 8 742, 9 743, B 744, C 745, D 746, E 747, F 748, G 749, I 750, O 751, P 752, Q 753, R 754, and T 755. Each character is seven pixels high by five pixels wide. The light value (intensity) of each pixel is digitized to 8 bits (256 gray levels).
The initial weight patterns for the sixteen trained characters are shown in FIG. 5B (760 thru 775). All sixteen weight patterns are initialized to a constant value of 128. The weights are stored as unsigned bytes (8 bit words) and thus the permissible range of the weights is from 0 to 255. The initial value of 128 is half of the full scale value and provides for maximum adjustment in either the positive or negative direction.
The initial correlation (squared) matrix R.sub.16.times.16 780, shown in FIG. 5C, was computed using equation (17) using the computer program of Appendix A. The high off-diagonal terms of this matrix indicates significant correlations. The goal is to reduce the value of these off-diagonal terms by placing more emphasis (increasing the weights) on those pixels that distinguish one trained character from another. The weight adjustment procedure illustrated in FIG. 3C and FIG. 3D was applied with the following parameters: R.sub.-- min=1, max.sub.-- count=6400, max.sub.-- count.sub.-- per.sub.-- char=400, alpha=0.001. With these parameters, after 3900 iterations, the weight adjustment process stopped.
The final correlation (squared) matrix R.sub.16.times.16 790, is shown in FIG. 5D. The off-diagonal terms for all of the trained characters in the font are reduced compared to the initial correlation (squared) matrix 780. However, some of the terms are not reduced to the desired level of R.sub.-- min=1. In particular, the correlation scores along a row corresponding to the characters: 0 791, 8 792, B 793, D 794, E 795, I 796, P 797, Q 798, and R 799 are higher than desired. These scores are not reduced any further since the the number of iterations for each trained character exceeded the parameter max.sub.-- count.sub.-- per.sub.-- char, and hence each of these trained characters were eliminated from further weight adjustment. Close examination of the weight adjustment process shows that contradictory weight adjustments occur for various combinations of trained character pairs which leads to oscillations. Hence, no further improvement in reducing the correlation scores can be obtained without eliminating the trained character pairs causing the oscillations from the optimization set.
The final weight patterns are shown in FIG. 5E for the sixteen trained characters 800 thru 815. Inspection of these weights shows which pixels provide the most discrimination of each trained character from every other trained character in the font. For example, the weight pattern for the O 811 has seven pixels with significant weight. It is clear from inspection of the patterns and the initial correlation matrix these pixels were selected to reduce the high correlations with the O, C, D, and Q. The weight patterns for the other trained characters can be analyzed in a similar manner.
In the above examples, some of the weights were reduced to zero value. In actual practice, this would be prevented since each pixel provides some information in recognizing a trained character and the redundancy helps reduce the influence of noise. The amount of weight adjustment can be controlled by properly setting the R.sub.-- min parameter.
The invention has been described in detail with particular reference to a preferred embodiment thereof, but it will be understood that variations and modifications can be effected within the spirit and scope of the invention. Such variations could include, but are not limited to, document scanners which scan the document with a linear, one dimensional, scanner one line at a time and build the image sequentially in a digital frame store. For example, the documents could contain text composed of multiple fonts with various styles such as bold, or italic. ##SPC1##
Claims
We claim:
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).
Patent Citations (4)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3267431 | 1960-08-01 | Greenberg et al. | |
| US3275985 | 1966-09-01 | Dunn et al. | |
| US3588821 | 1971-06-01 | LaSalle et al. | |
| US4731861 | 1988-03-01 | Blanton et al. |