Method and system for detecting a flaw in a sample image

[0002] This invention relates to methods and systems for detecting a flaw in a sample image and, in particular, to interactive methods and systems for detecting a flaw in a sample image.

[0003] Relative geometric distortion is typically caused by differential stretching and twisting of screens of a screen printer being used to print an image. For purposes of this application, a flaw consists of an area of the image consisting of the wrong grey level, which cannot be accounted for by means of the relative geometrical distortion. A much exaggerated demonstration of such a distortion is shown in the image of FIG. 1.

[0004] Referring now to FIG. 2, the type of flaws that need to be detected include a pigment splash 10, a pigment bridge 12, a pinhole 13, a pigment overrun 14, and a missing pigment.

[0005] Techniques which are able to detect flaws such as those described above have been known for a considerable period of time. However, these techniques, such as those described in U.S. Pat. No. 5,640,200 entitled “Golden Template Comparison Using Efficient Image Registration” are only capable of working where there is an effectively constant geometric relationship existing between the template image and the sample image.

[0006] Referring now to FIG. 3, one technique of the above-noted patent initially creates a composite template image by statistically combining multiple instances of a “perfect” image. The resulting template consists of a mean image, together with a standard deviation image (i.e. σ image). Naturally, the areas of most “rapid” rate of change within the template components (i.e. edges and regions of color change) provide most of the contribution to the standard deviation image, which can be used to form a mask of regions which, even on a good sample, are subject to the greatest variation, and, on hunting for flaws, can be given much less weight than areas that are subject to little change.

[0007] Once the template image has been fully trained, sample images taken from the production line can be compared with it. However, there is very little chance of the template and sample image exactly overlaying. In order to remove this misalignment some form of registration must be undertaken. This process invariably uses some form of correlation between either known landmarks or fiducial marks on both template and sample images, else using the complete image itself. Done properly, this process can provide a sub-pixel accurate measurement of the relative positioning of the template and the sample. This information can be used to either digitally re-register the images, or else can be used to re-position the sample image relative to the camera to ensure that the two images are optimally aligned. Flaws between the template image and the sample image can then be detected by the simple process of undertaking an absolute subtraction of the two. Thus, any difference, irrespective of whether the greyscale is brighter or darker than the other, results in a positive difference.

[0008] The value of this difference can either be thresholded, or else compared to the standard deviation image. Comparing with the σ image allows one to determine if the difference in that region of the image is greater than that expected from the distribution derived from the template samples. If so, the pixel is marked as a flaw, or else it is considered as part of the natural statistical variation between acceptable samples. The resulting flaw flag can be directly used to provide an error image, which, after further analysis using morphological tools such as blob analysis, high-lights the position of any artifacts.

[0009] The system of the above-noted patent works well in many applications, and is used extensively within the machine vision industry. However, there are some very important applications where the assumption of optimum alignment between the template image and the sample image being satisfied by a single correlation process is not valid.

[0010] For example, there are many cases within the screen printing industry, where the printing screen can become warped during use and thus change the relative alignment between the template and sample images across the image. In the case where this alignment drift can itself be categorized as a flaw, the previously described methodology can still be used. However, in the case where the results of the geometric warp are considered unimportant, the flaws maintain their criticality. In this situation, the current prior art systems produce far too many rejects, which often increase as the production batches progress.

[0011] The U.S. Pat. No. 5,412,577 to Sainio et al. entitled “Color Registration System for a Printing Press” discloses a control system for controlling misregistration between the colors of an image printed on a web. The system includes an imaging device such as a camera, a processor and image conversion circuits coupled to the processor. In the preferred embodiment, four printing units each print one color of the image upon the web. This kind of printing is commonly referred to as web offset printing. Colors on the units are cyan (C), magenta (M), yellow (Y) and black (K) The system further includes a print controller, a computer, a camera positioning unit, a camera assembly, and a printing plate scanner. The controller converts the signals from the computer into signals having suitable quality. The assembly is configured to scan a web for red (R), green (G), blue (B) and infrared (I). The U.S. Pat. No. 4,887,530 also to Sainio describes a web registration control system.

[0012] An object of the present invention is to provide a method and system for detecting a flaw in a sample image of an object which cope with geometric warpage or distortion while at the same time maintain their sensitivity to the flaw.

[0013] In carrying out the above object and other objects of the present invention, a method is provided for detecting a flaw in a sample image of an object in a machine vision system including a camera and a computer. The method includes the steps of: a) creating a template image of the object; b) registering the template image and the sample image; and c) subtracting the template image from the sample image to provide an error image after performing step b). The method also includes the steps of: d) analyzing the error image to identify a region of error; e) creating a final image of both the template image and the sample image in the region of error; and f) repeating steps b) through d) using the final sub-images to obtain a final region of error. The method finally includes the step of: g) identifying the final region of error as the flaw.

[0014] The flaw is typically an area of the sample image which has an incorrect greyscale level.

[0015] The above object and other objects, features, and advantages of the present invention are readily apparent from the following detailed description of the best mode for carrying out the invention when taken in connection with the accompanying drawings.

[0016] FIG. 1 is a view of a template image and a corresponding sample image illustrating exaggerated relative geometric distortions;

[0017] FIG. 2 is a view of an image which illustrates a number of flaws that need to be detected;

[0018] FIG. 3 is a schematic block diagram flow chart illustrating a prior art system for detecting flaws in sample images;

[0019] FIG. 4 is a schematic diagram illustrating a machine vision system and station at which the method and system of the present invention can automatically detect a flaw in a sample image;

[0020] FIG. 5 is a schematic block diagram flow chart illustrating the method and system of the present invention;

[0021] FIG. 6 is a graph illustrating a scalar product of a template image's position vector with that of a sub-image under the template of the image;

[0022] FIG. 7 is a graph illustrating various vector relationships of a template image in vector form and a sample image in vector form; and

[0023] FIG. 8 is a block diagram flow chart illustrating the method of the present invention.

[0024] The method and system of the present invention are primarily used as an aid for the screen printing industry. However, the method and system of the present invention can also be used in other industries wherein a template image and a sample image suffer from a relative geometrical distortion.

[0025] Referring again to the drawings Figures, there is illustrated schematically in FIG. 4 a machine vision system and station, generally indicated at 20, by which the method and system of the present invention can automatically detect flaws in a sample image of an object. In general, a flaw is an area of the sample image having an incorrect greyscale level.

[0026] The machine vision system 20 typically includes an image digitizer/frame grabber 22. The image digitizer/frame grabber 22 samples and digitizes input images from an image source such as a camera 24 and places each input image into a frame buffer having picture elements. Each of the picture elements may consist of an 8-bit number representing the brightness of that spot in the image. A digital camera 25 may be provided to eliminate the need for the image digitizer/frame grabber 22.

[0027] The system 20 also includes input/output circuits 30 to allow the system 20 to communicate with external devices such as a controller 27 for controlling a screen printing machine 31.

[0028] The camera 24 may be an image source such as an analog, digital, or line scan camera such as RS-170, CCIR, NTSC and PAL.

[0029] A system bus 26 may be either a PCI, an EISA, ISA or VL system bus or any other standard bus to allow inter-system communication such as at a monitor 29 of the system 20.

[0030] The image digitizer/frame grabber 22 may be a conventional frame grabber board such as that manufactured by Matrox, Cognex, Data Translation or other frame grabbers. Alternatively, the image digitizer/frame grabber 22 may comprise a vision processor board such as made by Cognex.

[0031] The machine vision system 20 may be programmed at a mass storage unit 32 to include custom controls for image processing and image analysis. Examples of image processing may include linear and non-linear enhancement, morphology, color and image arithmetic. Also, image analysis may include search, edge, caliper, blob, template, color, 2-D and 3-D measurements.

[0032] A computer 28 of the system 20 may be a Pentium-based IBM compatible PC or other PC having a sufficient amount of RAM and hard disk space for performing the algorithms associated with the present invention.

[0033] Referring now to FIG. 5, there is illustrated a template image 34 in the form of a 4 letter sequence “IVFC”. A sample image 36 has the same sequence except that the “V” and the “F” is slightly out of position due to screen distortion, and “F” has a real flaw in the form of a small “mouse nibble” near the top of the left hand side of the vertical.

[0034] These images 34 and 36 are fed into the Alignment and Error Image processing stage 38. This undertakes the correlation between the complete template image 34 and the sample image 36, and, based upon this, their relative positions are adjusted and an absolute value substraction is undertaken between the repositioned sample and template images. The resulting error image 40 consists of part of the “V” and “F” corresponding to the regions where they are still out of alignment. This error would be incorrectly classified as a flaw by the prior art systems.

[0035] This error image 40 is passed into a identify sub-images process 42, which identifies the respective regions that are still out of register. It then forms independent sub-images 44 of these regions (i.e. the “F” and the “V” from both the template and sample images).

[0036] These sub-images 44 are now passed through an alignment and error image generator 46 which now re-registers the template “V” with the sample “V” which, because it contains no flaws, returns a completely blank error image 50. The process is repeated in a second alignment and error image generator 48 with the “F” which produces an error image 52 which clearly shows the “mouse nibble” but very little else.

[0037] Referring now to FIG. 8, there is illustrated in block diagram form the method of the present invention.

[0038] At block 54, a template image of an object is created.

[0039] At block 56, a sample image of the object is created.

[0040] At block 58, the images are registered if this is the first pass through the methodology of FIG. 8. If this is a second or subsequent pass through the methodology of FIG. 8, then the resulting sub-images are registered as will be described in greater detail hereinbelow.

[0041] At block 60, a subtraction process is performed with the images created at blocks 54 and 56.

[0042] At block 62, all regions of image difference are identified.

[0043] At block 64, if no differences are found or if differences are identified as flaws, block 66 is entered and the methodology is stopped.

[0044] If at block 64 the differences are not identified as flaws, the method enters block 68 wherein sub-images are created for each image in each region of detected error.

[0045] At this point, block 58 is re-entered and the sub-images created at block 68 are registered and the steps of the remaining blocks 60, 62 and 64 are performed with the sub-images.

[0046] If at block 64 the differences are still not identified as flaws, block 68 is re-entered and sub-images of each sub-image in each region of detected error are created and block 58 is then re-entered wherein the sub-images of the sub-images are registered and thereafter blocks 60, 62 and 64 are re-entered.

[0047] Correlation Considerations

[0048] It can be readily appreciated that during each step through the above iterative process, the size of the sub-images gets smaller but their number can increase substantially. Consequently, the actual correlation process will represent a critical component to the throughput of the system. It is therefore important that the efficiency of this computation is kept as high as is possible.

[0049] It is well known that in general signal processing applications, pattern matching can be achieved using the well known techniques of correlation. In its simplest form this involves calculating the correlation integral for all relative displacements of the template inside the image to be searched. Assuming that the means of the template and the sub-image under the template are zero, the correlation integral can be expressed as:

[0050] Z(x,y)=∫∫I_x+a,y+bT_a,bdadb

[0051] where x and y specify the position of the template T inside the image to be searched. I, a and b are variables of integration and have a range which covers the complete area of the template. To see what the correlation integral is doing, one considers the n-pixel template image to be a point in n-dimensional space.

[0052] For example, 65536 dimensional space is capable of representing all possible 256×256 greyscale images. The correlation integral can then be seen to be nothing more than the scalar product of the template image's position vector with that of the sub-image under the template of the image to be searched. This is illustrated for a two-dimensional case in FIG. 6.

[0053] The basic correlation theory states that the position of the optimum match occurs when Z(x,y) takes its maximum value.

[0054] In practice, this simple theory is not adequate. It is possible for a very bright patch of the image to be searched to have a higher scalar product with the template image than the correct area. To get around this, the correlation theory is modified, to use “normalized correlation”. In effect, normalized correlation reduces each of the position vectors in n-dimensional space to unit length. In this form, one can see that the “normalized correlation coefficient” is nothing more than the cosine of the angle between the position vectors of the images.

[0055] From basic vector algebra:

[0056] OS.OT=|OS∥OT|cos (θ)

[0057] where: $\mathrm{OS}.\mathrm{OT}=\int \int {\mathrm{OS}}_{x+a,y+b}{\mathrm{OT}}_{a,b}dadb,{\left|\mathrm{OS}\right|}^2=\int \int {\mathrm{OS}}_{x+a,y+b}^{2}dadb,{\left|\mathrm{OT}\right|}^2=\int \int {\mathrm{OT}}_{a,b}^{2}dadb,\zeta \left(x,y\right)=\frac{\int \int {\mathrm{OS}}_{x+a,y+b}{\mathrm{OT}}_{a,b}dadb}{\sqrt{\int \int {\mathrm{OS}}_{x+a,y+b}^{2}dadb\int \int {\mathrm{OT}}_{a,b}^{2}dadb}}=\mathrm{Cos}\left(\theta \right)$

[0058] This relationship fully explains the +1→−1 range of the normalized correlation coefficient.

[0059] The correlation approach to pattern matching has many drawbacks when one implements it in software. Perhaps the most serious of which is the dynamic range of the variables which one has to use to store intermediate results. The above equation contains a large number of products of pixel values, this increases the required dynamic range very rapidly. Multiplying two 8-bit pixels immediately takes one to a 16-bit result, summing over many such results requires, minimally, 32 bits of storage. The square root and division, to yield a result between −1 and 1 necessitates the use of floating point arithmetic, together with the corresponding performance penalty. The technique works and works well. However, in the iterative environment one is working in, the time taken to apply this implementation would render the system unusable.

[0060] However, staying with the simplified two-dimensional case, one can see the following vector relationships in FIG. 7. Here, OT represents the template image in vector form (for a realistic image this would exist in “N” dimensional space, where N is the number of pixels in the image). Similarly, OS represents the sample image in vector form. The line D_tsrepresents the physical distance between the template and sample image and can be seen to be equal to:

[0061] D_ts=(Sx−Tx)²+(Sy−Ty)²

[0062] One can also obtain its value directly from the Cosine rule viz:

[0063] D_ts²=OT²+OS²−2*OT*OS*Cos(θ)

[0064] One also knows the following:

[0065] OT−TX²+Ty²OS=Sx²+Sy²

[0066] From this analysis, one can see that computing the overall distance from the generalized equation:

[0067] D_ts=Σ_pixels(S_i−T_i)²

[0068] provides exactly the same information but in a different format to that of computing the normalized correlation integral, but in a substantially simpler form.

[0069] The validity of this analysis can be demonstrated in diagrams where a distance based pattern match is compared to a correlation based pattern match. One would not expect the two to produce identical results as the relationship between the distance and correlation image contain functions depending on the magnitude of the image vector length.

[0070] Both methods clearly and unambiguously indicate the position where the sample image most closely matches the template, where the images are darkest—or where the distance is smallest.

[0071] The formulation for distance is well known in the art and is called the Euclidean distance. However, it is rarely used where maximum performance is required due to the need to incorporate floating point arithmetic to compute the square root function. This operation is often replaced by a similar well known function called CityBlock distance. This is defined as:

[0072] D_ts=Σ_pixels|Si−Ti|

[0073] A comparison of the two algorithms for all practical purposes produce identical results without the need to apply floating point arithmetic.

[0074] This algorithm is well known in the art, and has merely been included to show that CityBlock distance is simply an approximation to the Euclidean distance measure which, in turn, is merely a very efficient way of undertaking text book normalized correlation.

[0075] Error Image Considerations

[0076] The error image is generated by forming the absolute subtraction of the template image and the sample image. Although the spatial resolution is limited to the pixel level of the camera 24, in general the alignment between the two images will not be constrained to be an integer number of pixels. Consequently, the error image will always contain the outline of the target made up from the fractional part of the misregistration. Although correlation is capable of determining alignment to sub-pixel accuracy, it requires some mechanism such as interpolation or curve fitting to be applied to the pixel quantized shifting operations undertaken to compute the cross correlation relationship.

[0077] Sub-image Identification Considerations

[0078] The resulting error image obtained after the re-registration phase requires the area's showing errors to be locally re-registered, and the process being repeated. Three methods of identifying these sub-images are possible, these are:

[0079] 1. Manual pre-selection of sub-images;

[0080] 2. Automatic pre-selection of sub-images;

[0081] 3. Blind allocation of sub-images.

[0082] The first option allows the user to select “obvious” regions for use as sub-images. For example, in the first example image of the word “SAMPLE” in FIG. 1, each letter would be the natural choice for the sub-image selection.

[0083] As this decision could be made during train time, the setting up of these images wouldn't have direct impact on the performance of the system during system run time.

[0084] The second option is available when there is just too much data to make manual selection a practical option. There are many possible options for undertaking the automatic selection of the sub-images. For example, both Hough and frequency domain transform techniques make excellent choices when the pattern is on a regular grid. Cepstrum analysis has been used to identify the x and y positioning of the letters in the example text.

[0085] Finally, the automatic blind selection of the sub-image would be used where the shape of the regions were sufficiently complex to render either of the first two options inappropriate. In this mode of operation, the sub-image would be selected from the original error image. Regions of error image would be processed with a morphological “blob” tool which essentially collects adjacent flawed pixels into an amorphous region. An analysis would be made using the physical size of each blob as to whether it could be categorized directly into a small flaw such as a pigment splash, or a much larger blob which would probably be caused by an area of the two images not being in register, due to relative template/sample warpage.

[0086] A rectangular region would be generated that generously enclosed the offending blob and the coordinates of the corners of the region would be used as the coordinates of the sub-image to extract from the template and sample image. These two sub-images would then be re-registered, and the resulting error image used to determine whether another iteration is required.

[0087] While the best mode for carrying out the invention has been described in detail, those familiar with the art to which this invention relates will recognize various alternative designs and embodiments for practicing the invention as defined by the following claims.