Character recognition method using optimally weighted correlation

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
18Forward
Citations 
0
Petitions 
5
Assignments
First 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.
5 Assignments
0 Petitions
Accused Products
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.
22 Citations
View as Search Results
Method and apparatus for forming variant search strings  
Patent #
US 6,459,810 B1
Filed 09/03/1999

Current Assignee
LinkedIn Corporation

Sponsoring Entity
International Business Machines Corporation

Portable authentication device and method of authenticating products or product packaging  
Patent #
US 7,079,230 B1
Filed 04/24/2000

Current Assignee
Sun Chemical NV

Sponsoring Entity
Sun Chemical NV

Method and apparatus for modular hearing aid  
Patent #
US 20050232453A1
Filed 04/15/2004

Current Assignee
Starkey Laboratories Incorporated

Sponsoring Entity
Starkey Laboratories Incorporated

System and method of signal processing for use in reading data  
Patent #
US 6,956,962 B1
Filed 05/07/2002

Current Assignee
Digital Check Corp

Sponsoring Entity
Unisys Corporation

Authentication mark for a product or product package  
Patent #
US 20040000787A1
Filed 01/31/2003

Current Assignee
Sun Chemical NV

Sponsoring Entity
Sun Chemical NV

Tamperresistant authentication mark for use in product or product packaging authentication  
Patent #
US 20040023397A1
Filed 08/05/2002

Current Assignee
VERIFICATION TECHNOLOGIES INC.

Sponsoring Entity
VERIFICATION TECHNOLOGIES INC.

Method and apparatus for extracting text information from moving image  
Patent #
US 20030113015A1
Filed 12/18/2001

Current Assignee
Toshiba Tec Corporation, Toshiba Corporation

Sponsoring Entity
Toshiba Tec Corporation

Online verification of an authentication mark applied to products or product packaging  
Patent #
US 20030112423A1
Filed 10/18/2002

Current Assignee
VERIFICATION TECHNOLOGIES INC.

Sponsoring Entity


Optical object recognition method and system  
Patent #
US 6,473,524 B1
Filed 04/14/1999

Current Assignee
Videk Inc.

Sponsoring Entity
Videk Inc.

Device and method for handwriting recognition with adaptive weighting of recognition data  
Patent #
US 5,917,942 A
Filed 12/28/1995

Current Assignee
Google Technology Holdings LLC

Sponsoring Entity


Neural network optical character recognition system and method for classifying characters in a moving web  
Patent #
US 5,712,922 A
Filed 11/15/1994

Current Assignee
Eastman Kodak Company

Sponsoring Entity
Eastman Kodak Company

Method for training an adaptive statistical classifier to discriminate against inproper patterns  
Patent #
US 5,768,422 A
Filed 08/08/1995

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Computer Incorporated

Method and apparatus for storing corrected words with previous usercorrected recognition results to improve recognition  
Patent #
US 5,787,455 A
Filed 12/28/1995

Current Assignee
Google Technology Holdings LLC

Sponsoring Entity
Motorola Inc.

Adaptive statistical classifier which provides reliable estimates or output classes having low probabilities  
Patent #
US 5,805,731 A
Filed 08/08/1995

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Computer Incorporated

Method for training an adaptive statistical classifier with improved learning of difficult samples  
Patent #
US 5,805,730 A
Filed 08/08/1995

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Computer Incorporated

Method of multifont template enhancement by pixel weighting  
Patent #
US 5,530,775 A
Filed 08/19/1994

Current Assignee
Canon Ayutthaya Limited

Sponsoring Entity
Canon Inc.

Method of OCR template enhancement by pixel weighting  
Patent #
US 5,379,349 A
Filed 09/01/1992

Current Assignee
Canon Inc.

Sponsoring Entity
Canon Inc.

Method and device for detecting connected pixels in image  
Patent #
US 10,019,807 B1
Filed 12/05/2017

Current Assignee
MVTech Co. Ltd.

Sponsoring Entity
MVTech Co. Ltd.

Method of optical character recognition  
Patent #
US 4,731,861 A
Filed 08/26/1983

Current Assignee
Texas Instruments Inc.

Sponsoring Entity
Texas Instruments Inc.

IMAGE CLASSIFYING BY ELEMENTAL GROUPING,READING AND COMPARING  
Patent #
US 3,588,821 A
Filed 11/28/1967

Current Assignee
LASALLE MICHEL MARIE JOSEPH, JOURDAN GERARD CHARLES MAURICE

Sponsoring Entity
LASALLE MICHEL MARIE JOSEPH, JOURDAN GERARD CHARLES MAURICE

Pattern recognition systems using digital logic  
Patent #
US 3,275,985 A
Filed 06/14/1962

Current Assignee
Mcdermid William L., Lanal Laveen N., Curt F. Fey, Dunn William H., Smith Donald F.

Sponsoring Entity
Mcdermid William L., Lanal Laveen N., Curt F. Fey, Dunn William H., Smith Donald F.

Adaptive computing system capable of being trained to recognize patterns  
Patent #
US 3,267,431 A
Filed 04/29/1963

Current Assignee
Herbert J. Greenberg, Konheim Alan G.

Sponsoring Entity
Herbert J. Greenberg, Konheim Alan G.

7 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.  View Dependent Claims (2, 3, 4, 5, 6, 7)
 1) creating a font of trained characters by;
1 Specification
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 INVENTIONCorrelation 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
y=[y.sub.1, y.sub.2, . . . , y.sub.N ].sup.T ( 1)
where y.sub.i denotes the light value of the ith 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.
x=[x.sub.1, x.sub.2, . . . , x.sub.N ].sup.T ( 2)
where x.sub.i denotes the light value of the ith 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 INVENTIONThis 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
Z=W.sup.2 ( 5)
where ##EQU2## Note that although Z.sub.x is an N.times.N matrix, there are only N nonzero 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
x.sub.w =W.multidot.x=[x.sub.1 w.sub.1, x.sub.2 w.sub.2, . . . , x.sub.N w.sub.N ].sup.T ( 12)
and
y.sub.w =W.multidot.y=[y.sub.1 w.sub.1, y.sub.2 w.sub.2, . . . , y.sub.N w.sub.N ].sup.T ( 13).
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
.gradient..sub.Z R.sub.xy =.differential.R.sub.xy /.differential.Z.sub.x( 14)
where .gradient..sub.Z is the gradient operator and is defined as .differential.``/.differential.Z.sub.x.
The ith component of the gradient is easily shown (from equation (8)) to be
(.gradient..sub.Z R.sub.xy).sub.i =.differential.R.sub.xy /.differential.z.sub.x,i =x.sub.i y.sub.i ( 15)
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.
Z.sub.x (k+1)=Z.sub.x (k).alpha..gradient..sub.Z R.sub.xy ( 16)
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 offdiagonal 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 meancorrected correlation.
The weighted normalized meancorrected correlation (squared) R.sup.2.sub.xy is defined as ##EQU9## where
x.sub.c =xm.sub.x ( 17a)
y.sub.c =ym.sub.y ( 17b)
are the meancorrected characters where
x.sub.c.sup.T =[x.sub.c,1 x.sub.c,2 . . . x.sub.c,N ].sup.T( 17c)
y.sub.c.sup.T =[y.sub.c,1 y.sub.c,2 . . . y.sub.c,N ].sup.T( 17d)
and the ith components of the mean vectors are given by
(m.sub.x).sub.i =.SIGMA.x.sub.i /N, i=1,2, . . . ,N (17e)
(m.sub.y).sub.i =.SIGMA.y.sub.i /N, i=1,2, . . . ,N (17f)
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 meancorrected correlation (squared) with respect to the weights (squared) is defined as
.gradient..sub.Z R.sup.2.sub.xy =.differential.R.sup.2.sub.xy /.differential.Z.sub.x =(2R.sub.xy)(.gradient..sub.Z R.sub.xy)(18)
The ith component of the gradient is defined as:
(.gradient..sub.Z R.sup.2.sub.xy).sub.i =.differential.R.sup.2.sub.xy /.differential.z.sub.x,i
By partial differentiation of (18), it can be shown that the ith component of the gradient of the weighted normalized meancorrected 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.
Z.sub.x (k+1)=Z.sub.x (k).alpha..gradient..sub.Z R.sup.2.sub.xy( 20)
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 DRAWINGSFIG. 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 EMBODIMENTReferring 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 electrooptic sensor 30. Upon detection of the part, the electrooptic 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 fiberoptic 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 meancorrected 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 ith 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 offdiagonal 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 offdiagonal terms of this matrix indicates significant correlations. The goal is to reduce the value of these offdiagonal 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 offdiagonal 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##