Abstract:
A method for recognizing previously localized characters present in digital gray tone images, particularly for recognizing characters struck in metal surfaces, whereby, for training a trainable character recognition routine, steps are provided to generate reference characters presented line-like and to deposit these reference characters in a working memory of the trainable character recognition routine, whereby the number and nature of the reference characters correspond to the character set from which characters are to be recognized. For recognizing characters, steps are provided: to read the digitized character of the localized character to be recognized into a character recognition routine and an appertaining gray tone image is provided, to pre-process the character to be recognized so that a classification of the appertaining character can be implemented; to compare the preprocessed character to all reference characters previously learned by the character recognition routine, to implement a majority decision for identifying that reference character that has the greatest plurality of sub-features coinciding with the character to be recognized, and to produce a result signal from the character recognition routine for further processing thereof.

Description:
BACKGROUND OF THE INVENTION 
     Manufactured products are frequently provided with legends that serve to identify the product. Such identifications, for example, are directed to particulars such as article number, manufacturer and type of execution. 
     Legends applied with color stamps are often too temporary since they become easily illegible due to scratches, rust or foreign colored materials, such as lacquer. Coined legends prove more durable and, for example, are frequently employed in the field of automobile manufacture. A distinction is made in coined characters between imaged or struck legends and raised legends. 
     Although a bar code can be automatically read more easily than such characters, it is seldom used since the identifications could also be easily read by other persons. There is therefore a great need for a method that recognizes coined characters in automated production processes. 
     Optical character recognition (OCR) is well known in the prior art for pattern recognition of digital image processing. For example, optical reader equipment are already used in banks and in post offices, see, for example, Ullmann, J.R., Picture Analysis in Character Recognition in Digital Picture Analysis, Edited by A. Rosenfeld, Springer 1976, pages 295-343. They have different requirements concerning the print image to be read and of the text layout. However, what they all have in common is that they expect characters that noticeably differ from the picture background in terms of color or brightness. 
     This pre-requisite is generally not met for characters coined in workpieces. Depending on the type of coining, on the illumination, on the material of the surface and any possible contamination of the workpiece, the labelling thereon does not uniformally contrast with the background. Consequently, a binary image is not available, only a digital gray tone image is available and therefore known methods for optical character recognition cannot be employed. 
     FIG. 1 shows portions of gray tone images of punched characters that were recorded under different illumination conditions. 
     Two sub-tasks form the foundation for the process of optical character recognition in gray tone images, namely, first segmenting for identifying at which locations characters are present in the image, and second classifying or recognition. For example, let a rectangle in which a character is assumed to reside be extracted from the image. A determination must then be made as to which character is present or, as warranted, whether a missegmenting was carried out. 
     Complete systems for character segmenting and recognition in gray tone images are disclosed in the publications of Hongo, Y., Komuro, A., &#34;Stamped Character Apparatus Based on the Bit Matrix Method&#34;, Proc. 6th ICPR, Muenchen 1982, pages 448-450; German published application 3 203 897; and Langer, W., &#34;Segmentierung von Schriftzeichen in Grauwertbildern&#34;, Degree Thesis, Technical University of Braunschweig Inst. fuer Elektrotechnik, 1988. All three systems employ methods that first convert the gray tone image into a black-and-white picture and then execute the segmenting and recognition. 
     In the references of Hongo and Komuro the original image is converted into a binary representation by establishing a gray tone threshold and then by assuming the characters have a planar structure with small disrupting areas. The latter are then eliminated by evaluating their size. The method is not suitable for recognizing coined characters without an additional application of color. However this method can be used, for example, for automobile identifications and labelled keyboards. The same is true of the method disclosed by German published application 3 203 897. 
     In the reference of Langer the disclosed method also segments the characters in the binary image, whereby, however, it is proposed to use alternative segments in the case of an unclear classification. The binary segmented characters are pre-processed in order to produce planar patterns. A method of CGK (Computer Gesellschaft Konstanz) is used for classification that recognizes planar binary characters. The main drawback of the Langer method is the selection of parameters dependent on the original image and the selection of the sub-steps for image pre-processing. Moreover, the classification by the CGK method requires an exact segmenting of the binary characters in a rectangle. Given the presence of disrupting areas, this cannot be guaranteed in every case. 
     European Patent 0 217 118 A2 discloses a method for segmenting wafer numbers from gray tone images. According to this method, the original image is first &#34;smoothed&#34; and is then converted into a black-and-white image with reference to a global threshold. Using a single-pass method, the components of the image are coded into simple polygon trains (&#34;descriptors&#34;). Maximum expanses are calculated for every polygon train and small noise elements are eliminated on the basis of the resulting values. An individual character segmenting and a classification are not disclosed. The extremely narrow coining of the wafer numbers facilitates the segmenting significantly since the characters themselves are not subject to any brightness fluctuations (no reflections). Without such specific, prior knowledge about the image, an image smoothing is generally not recommended since features important for the classification can also be lost in addition to any disruptions of the image. 
     A method for the classification of characters from &#34;DMA sequences&#34; is disclosed in the publication by Holder, S., Dengler, J., &#34;Font and Size-Invariant Character Recognition with Gray Value Image Features&#34;, Proc. 9th ICPR, Rom, 1988, these sequences are composed of the leters &#34;A&#34;, &#34;C&#34;, &#34;G&#34; and &#34;T&#34; and are usually printed in an extremely small type face with poor printing quality and a variable character set in trade publications. The method employs the gradient image of the digitized gray tone image for acquiring the features since a good binarization can generally not be achieved by establishing a gray tone threshold due to the poor quality of the original image. The gradient directions and their directional changes in the course of the contour of the letters presented are entered into a histogram. The histogram is compared to reference histograms of the four letters that were previously produced on the basis of sample letters from various character sets. The method works in size-invariant fashion and nearly independently of the character set of the original. A method for segmenting is not disclosed. The algorithm used is not suitable for punched characters since the important information about th original changes of the gradients in the course of the contours of the characters is not reliably present for these characters. For example, an &#34;L&#34; could thus not be discriminated from a &#34;T&#34; merely with reference to the gradient histogram. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to provide a method for the classification of previously localized characters present in gray tone images that is suitable for reliably recognizing characters punched o struck in workpieces or fashioned as raised characters on workpieces recognizing these under arbitrary illumination conditions. 
     For achieving this object, the method of the present invention for recognizing previously localized characters present in digital gray tone images, particularly for recognizing characters struck into metal surfaces, is as follows. For training a trainable character recognition means the following steps are performed: generate reference characters (ideals) portrayed line-like and deposit these reference characters in a working memory of the trainable character recognition means, whereby the number and nature of the reference characters correspond to the character set from which characters are to be recognized; assign a direction to every pixel of every reference character; determine a scatter function for anticipated values; determine an angular comparison function for comparing reference directions with gray tone edge directions identified from the gray tone image; produce evaluation matrices on the basis of the scatter function and the angular comparison function. For recognizing characters, the following steps are performed: read the digitized character to be recognized into a character recognition means, as a result whereof the appertaining gray tone image is obtained; preprocess the character to be recognized so that a classification of the appertaining character ca be implemented; compare the pre-processed character to all reference characters previously learned by the character recognition means; implement a majority decision for determining which reference character coincides with the greatest plurality of sub-features of the character to be recognized; and generate a result signal from the character recognition means for further processing. 
     The generated result signal is subjected to a plausibility check and a signal that represents a rejection criteria is generated when a positive check result is not obtained. 
     The rejection criterion is established when at least one of the following two conditions is met: 
     1) a value Vg1(B)/AV is smaller than a threshold Rs1, whereby B is the result character of a classification and AV is the number of foreground points of the appertaining, binarized gradient image; 
     2) the minimum distance of the obtained evaluation of the result character B to other characters is lower than a threshold Rs2. 
     The distance function for the condition &#34;2&#34; is established by the following relationship: ##EQU1## 
     The character to be recognized is further-processed in a rectangle segmented from the gray tone image. The intensity and direction of a potential gray value edge in the rectangle is first calculated for every point of this rectangle with a gradient filter. The orientation of the gray value edges (&#34;from bright to dark&#34; or &#34;from dark to bright&#34;) is not discriminated, since which of the coined edges in the gray tone image appear bright and which appear dark cannot be predicted for an unknown illumination direction. 
     In one embodiment of the present invention a compass gradient filter is used as a gradient filter. The gradient image present after the gradient filtering is transformed into a binary image and pixels having weak gradient values are erased. The binarized gradient image is transformed to a format &#34;RefBreite*RefHohe&#34; of the reference characters. Specific steps of the comparison procedure can be executed either sequentially or in parallel. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The features of the present invention which are believed to be novel, are set forth with particularity in the appended claims. The invention, together with further objects and advantages, may best be understood by reference to the following description taken in conjunction with the accompanying drawings, in the several Figures in which like reference numerals identify like elements, and in which: 
     FIG. 1 depicts portions of gray tone images of punched characters that were registered under different illumination conditions, showing these as a laser printout; 
     FIG. 2 shows examples of reference characters for the numeral &#34;9&#34;; 
     FIG. 3 shows a set of 35 reference characters that are transformed into a prescribed reference format; 
     FIGS. 4a-4c are illustrations of various classes of black point arrangement in reference characters; 
     FIGS. 5a-5c show possibilities of assigning directions to line points of a reference character; 
     FIG. 6 shows the eight possible directions of the points of a reference character based on the directional definition of FIG. 5; 
     FIG. 7 shows the reference character for the numeral &#34;9&#34;; 
     FIG. 8 shows the evaluation matrices produced for the reference character shown in FIG. 7; 
     FIG. 9 shows a segmented gray tone image of the numeral &#34;5&#34;; 
     FIG. 10 shows the character of FIG. 9 filtered with what is referred to as a Robinson mask; 
     FIG. 11 shows the binarized gradient image of the character filtered out and acquired according to FIG. 10; 
     FIG. 12 shows the character image of FIG. 11 demagnified to 24*40 pixels; and 
     FIGS. 13, 14, and 15 each respectively show exemplary results of the character r®cognition, whereby the characters shown in FIG. 3 were used as reference characters. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Before the character recognition means can be used for recognition, it must be trained in a learning phase. In this learning phase, the character set to be learned is presented to the system. The typical scope of such a character set lies between five and 35 different characters. The characters are frequently composed only of numbers (i.e. a maximum of 10 characters). &#34;Evaluation matrices&#34; are automatically generated for every character, these being stored and used subsequently in a recognition phase. 
     Line-like images of the stamping punch are used as reference characters for the &#34;training&#34; of the character recognition means. The coining edge of the punch should thereby be portrayed. FIG. 2 shows examples of reference characters of the numeral &#34;9&#34;. A reference character for an extremely narrow stamping punch is shown in the middle and that for a broader stamping punch is shown at the right. 
     The reference characters must be produced by the user of the character recognition means. This can be accomplished using a simple CAD system, a light pen or using parametric input. However, it is also possible to prepare a drawing and to then digitize the drawing. The line-like references of FIG. 2 were acquired, for example, from the binary image shown at the left in the FIG. 2. All reference characters are transformed by the character recognition means to the same format of a predetermined width and to a predetermined height, hereinafter referred to as &#34;RefBreite*RefHohe&#34;. FIG. 3 shows a set of 35 reference characters in the format of 24*40 pixels. 
     The reference characters are present in binary images (only composed of black and white points). A thinning method is applied in order to thin the lines of the reference characters to a minimum width (&#34;One-Pixel-Width&#34;). A definition of the term &#34;thin&#34; and a few thinning methods may be found in the book, Pavlidis, Th., Algorithms for Graphics and Image Processing, Springer 1982, Pages 195-214 (hereby incorporated by reference). The thinned reference characters are then stored. The black points (P), see FIG. 4, of the references can now be categorized into three classes: 
     a) end points (a black neighboring point in a 3×3-environment), 
     b) line points (exactly two black neighboring points), and 
     c) branching points (more than two black neighboring points), see FIG. 4. 
     An edge direction is assigned to the points of the reference character. Various methods can be employed for this purpose. 
     One possibility of assigning a direction to the line points of a reference character is shown in FIG. 5. From left to right, FIG. 5 shows: 
     a) the direction of the connecting straight line of the neighboring points being the direction assigned to P; 
     b) the connecting straight lines therewith possible in 3×3 window; 
     c) the eight possible directions with numbering and specification of the angle. 
     The directional straight lines here contain no running sense, that is, the directions &#34;north&#34; and &#34;south&#34; are identical. End points and branching points receive no assigned direction. 
     Let R Ref  reference the resolution of the direction detection in the reference character (in the example of FIG. 5, R Ref  =8). 
     Since the edge direction measured in the reference character need not also appear at the same location in the gray tone image presented later for recognition, a scatter function is employed. It distributes the anticipation of specific edge directions to an environment of the point at which this direction was measured in the reference. 
     Let the function be referenced d(P, Q), whereby P is a point in the reference character and Q is a location in a matrix (Evaluation matrix). The function d(P, Q) should not be equal to 0 only for Q in a small environment of P, and the values of d(P, Q) should drop monotonously when Q moves away from P. 
     The following is a simple example of a scatter function: What are depicted are the values in a 9*9 environment of a point P. The value d(P, Q)=3 is reached for Q=P. The values that are not shown are defined as zero. 
     
         ______________________________________1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 11 1 2 2 2 2 2 1 11 1 2 2 2 2 2 1 11 1 2 2 3 2 2 1 11 1 2 2 2 2 2 1 11 1 2 2 2 2 2 1 11 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1______________________________________ 
    
     (for use of the scatter function, see below.) 
     An angular comparison function h(r Ref ,R Vor ) is used to compare an edge direction r Ref  measured in a reference character to a defined direction r Vor  in the gray tone image. It should output high positive values for a slight angular difference between directions and should output zero for a great angular difference. 
     FIG. 6 shows the eight possible directions of the points of a reference character according to the directional definition of FIG. 5. The forward directions that can be defined by a compass gradient operator in the gray tone image are shown at the outside. 
     A simple angular comparison function for this specific case can then be defined, for example, by: ##EQU2## 
     An evaluation matrix is produced for every character to be learned and for every possible edge direction in the gray tone image. When, for example, the directional resolution in the gray tone image is R Vor  =4, then four matrices are produced for each character to be learned. These matrices are the actual result of the overall learning step. The line-like reference characters ar only required for producing these matrices. 
     How a defined, presented edge direction is to be evaluated with reference to a learned character is entered into the evaluation matrices. The evaluation matrix for vertical edge directions in the middle of the rectangle for the character &#34;1&#34; contains, for example, a high positive value, but contains a negative value for the character &#34;8&#34;. 
     The evaluation matrices are referenced Bew(Z, r Vor ), whereby Z is a character to be learned. The evaluation matrices have the same format as the learned character, &#34;RefBreite x RefHohe&#34;. Let W Ref  indicate the value range for points of a rectangle having this size and let C reference a positive constant that serves the purpose of defining a maximum value for the evaluation. 
     The evaluation matrices for the character Z are now produced in the following way: 
     Set Bew(Z,r Vor ,P):=0 for all directions r Vor  and all points P; 
     Add the value d(P,Q)*h(r Ref ,R Vor ) to Bew(Z,r Vor ), for all foreground points P of the thin ideal of Z, for all possible r Vor  and every point Q from W Ref , whereby r Ref  is the direction belonging to P (for the definition of the functions d and h, see above); 
     Set Bew(Z,r Vor ):=MIN (C, Bew (Z, r Vor )) for all possible r Vor  and every point Q from W Ref  (MIN=selection of the minimum); 
     Calculate the mean value over all elements of the evaluation matrices of Z: ##EQU3## for norming, subtract this mean value from all elements of the evaluation matrices of Z. 
     FIG. 8 shows the evaluation matrices for the reference shown in FIG. 7 for a &#34;9&#34;. The reference matrices for the directions &#34;horizontal&#34;, &#34;ascending diagonal&#34;, &#34;vertical&#34; and &#34;descending diagonal&#34; are shown from left to right. Dark gray tones correspond to high evaluations. The respectively upper matrix shows the positive elements cf the evaluation matrix, that is, negative elements are left light in the upper matrix and are entered in the lower matrix. 
     The evaluation matrices were calculated with the above-described, exemplary examples, i.e., in particular with RefBreite=24, RefHohe=4, R Ref  =8, R Vor  =4. 
     The character to be recognized is presented in a rectangle segmented from the gray tone image. The intensity and direction of a gray tone edge potentially occurring here is first calculated for every point of this rectangle with a gradient filter. Since, given an unknown illumination direction, it cannot be predicted which coined edges will appear bright in the image and which will appear dark in the image, no discrimination is made regarding the orientation of the gray value edges (&#34;from bright to dark&#34; or from &#34;dark to bright&#34;). 
     For example, the compass gradient filters can be used as disclosed in the publication of Wirtz, B. &#34;Untersuchung von Algorithmen zur Kantenerkennung in industriellen Szenen&#34;, Degree Thesis in Computer Science at the RWTH Aachen, 1987, i.e., for example, the Kirsch, Prewitt or Robinson Masks as well as the non-orthogonal masks presented by Wirtz. Filter makes that are known in the prior art and, other than that disclosed in the thesis by Wirtz, that can be used as equally well in the method of the present invention are disclosed in the following publications: 
     J.M.S. Prewitt, 1972, &#34;Parametric and Non-Parametric Recognition by Computer: An Application to Leucocyte Image Processing&#34;, Adv. in Computers, Vol. 12, pgs. 285-414; 
     G. Robinson, 1977, &#34;Edge-Detection by Compass Gradient Masks&#34;, Computer Vision Graphics and Image Proc., Vol. 6, No. 5, pgs. 492-501; and 
     R. Kirsch, 1971, &#34;Computer Determination of the Constituent Structure of Biological Images&#34;, Biomed. Res., Vol. 4, No. 3, pgs. 315-328. 
     A resolution of four edge directions is obtained by use of these methods: &#34;vertical&#34;, &#34;ascending diagonal&#34;, &#34;horizontal&#34; and &#34;descending diagonal&#34;. 
     The character of FIG. 9 filtered with the Robinson mask is shown in FIG. 10. Pronounced gray valued transitions in the original image are thereby marked with bright gray values. The allocated edge directions are not shown. The edge directions are numbered beginning with one and the resolution is referenced R Vor . Use of gradient filters having a resolution differing from 4 is possible. 
     The gradient image is subsequently transformed into a binary image and points having weak gradient values are erased. Various methods can be employed in the binarization. FIG. 11 shows the binarized gradient image of the FIG. 10 character using a binarization according to the publication of Chen, D., Siy, P., Forward/Backward Contour Tracing With Feedback, IEEE PAMI-9, May 1987, Pages 438-446 (hereby incorporated by reference). The binary image generally has relatively poor quality and, in particular, it does not appear &#34;planar&#34; but rather it is composed of small strokes and points. It is therefore not suitable for submission to a standard character recognition method (for font and paper originals). 
     Finally, the binarized gradient image is also transformed onto the format, &#34;RefBreite*RefHohe&#34;, of the reference characters. FIG. 12 shows the image of FIG. reduced to 24*40 pixels. 
     The foreground points thereby continue to carry the information about their appertaining edge direction. Now, let V(r,P) be equal to 1, when the point P is a foreground point in the binarized gradient image and has the direction r; otherwise, let V(r,P) be equal to 0. 
     For comparing the original to a learned character Z, all the evaluations that correspond to foreground points in the binarized gradient image are summed: ##EQU4## 
     For classification, the original is compared to all learned characters. That reference character that yields the highest comparison value is a result character of the classification (majority decision). 
     The critical advantage of this comparison method is that it operates without multiplication since the factor V(r,P) can only assume the values &#34;0&#34; and &#34;1&#34;. Moreover, steps in the procedure can be performed in parallel in a simple way on corresponding hardware, that is, the steps can be chronologically executed in parallel. 
     In case of a mis-segmenting, i.e. when none of the learned characters was present, or when the quality of the original image is too poor, a criterion for rejecting the character is formed (plausibility check). 
     An original is rejected when at least one of the following two conditions is met: 
     1. The value Vg1(B)/AV is smaller than a threshold RS1, whereby B is the result character of the classification and AV is the number of foreground points of the appertaining, binarized gradient image. (The evaluation per pixel of the original that is achieved on average is too low with respect to the most similar, learned character.) 
     2. The minimum difference of the achieved evaluation of B from the other characters is lower than a threshold RS2. A possible distance function for condition 2 is established by: ##EQU5## 
     FIGS. 13, 14 and 15 show exemplary results of the recognition. The characters shown in FIG. 3 were used as reference characters. The characters in the gray tone image were automatically segmented and rectangles, presented for recognition, are framed. 
     The results show the independence of the recognition from the illumination that clearly differs in the three images. Extremely similar characters such as &#34;6&#34; and &#34;G&#34; were also correctly recognized. 
     In conclusion, one skilled in the art would recognize that the method is also suitable for the recognition of characters on paper originals since edge directions can be identified with gradient filters for binary images as well as for gray tone images. 
     The attached program printout contains instructions for training reference characters as well as instructions for classification in gray tone images of segmented characters. The implementation was executed on a VAX 8700 and the software was written in the &#34;PASCAL&#34; programming language. 
     The invention is not limited to the particular details of the apparatus depicted and other modifications and applications are contemplated. Certain other changes may be made in the above described apparatus without departing from the true spirit and scope of the invention herein involved. It is intended, therefore, that the subject matter in the above depiction shall be interpreted as illustrative and not in a limiting sense. ##SPC1##