Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1994-03-11
2001-01-23
Couso, Jose L. (Department: 2721)
Image analysis
Pattern recognition
Feature extraction
Reexamination Certificate
active
06178262
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
This invention relates to machine vision, and more particularly, to methods and apparatus for accurately locating circular or curvilinear patterns in a digitized image.
B. Background
Many production machines require automated alignment of objects such as printed circuit boards before processing operations, such as the insertion of integrated circuits can take place. In such applications, machine vision systems can be used to capture and digitize an image of the object to be aligned and analyze that image for a match to a pre-trained “model” of a fiducial or locator target on the object. Typically, search techniques such as correlation search, contour finding or edge detection are used to locate x,y coordinates in the digitized image for a possible match to the pre-trained model. Those results are then sent to the production machine equipment, where the information can be used to move the printed circuit board for proper alignment.
One technique used to improve accuracy in such searching is to decompose the features of the fiducial or target pattern into subfeatures, such as corners or arcs that can be independently located more accurately and whose locations can then be combined to give the location of the whole. The creation of subfeatures is usually done in a separate training step, while searches are conducted at runtime, during production.
Subfeature models of angular fiducial symbols, such as squares, rectangles, crosses and triangles, can be generated using a number of techniques that are simple, fast and accurate. Models of circular or curvilinear fiducials can also be created using existing techniques. However, for reasons of computational efficiency in existing systems and because fiducials are frequently uniform in grey level, the model for a circle or curvilinear symbol is typically a binary model generated from a synthetic image. Calculating grey level values for the boundary locations of a curvilinear object is a more complex task than it is for angular objects.
Previous circle location schemes train four subfeature models at 0, 90, 180, and 270 degrees. Prior techniques can vary in accuracy. If multiple images are taken of the same fiducial (without moving it under the camera), the resulting location reported by the fiducial finder can vary from image to image by as much as 0.25 to 0.5 pixels or pels. Even though this variation is not very severe, it is too great for applications that demand highly accurate position information.
One cause of inaccuracy stems from the binary nature of the typical circular or curvilinear fiducial model. Since curvilinear fiducials cannot be exactly represented by an integral number of binary pels, inaccuracies are built into the model. Computations necessary to determine the fill of a synthetic grey scale circle model are also not trivial. One such method involves the use of integration.
Furthermore, the presence of confusing artifacts near or around the object of interest, non-uniform lighting variations, scale variations, video noise generated in the imaging system, and smearing or obscuration of parts of the symbol all contribute to the difficulty of locating a symbol accurately.
Another significant problem in using subfeature models for curvilinear objects stems from the fact that the x and y axis coordinate positions returned for a particular subfeature model may not be equally likely to indicate a good match. For example, a subfeature model centered at the zero degrees location on the circle's periphery provides quite accurate information about the x axis location of the symbol, but the y axis information is not definitive for that point on the circumference, due to the slow curvature of the circle perimeter. For each subfeature model around the circumference, the x, and y coordinates may vary in their respective information value in a search.
Similarly, in existing search techniques using templates or models, it may happen that the results that match the subfeature model most closely may in fact be positions found as a result of spurious artifacts in the image. For example, a circular fiducial may be represented by four subfeature models. If these four subfeature models are used to search for the fiducial, three of the resulting positions found in the image may actually be part of the fiducial. However, an artifact which is not part of the fiducial may be located by the search technique as a best match for the fourth subfeature. This artifact may be positioned so far away from the other three it could not possibly be part of the fiducial.
SUMMARY OF THE INVENTION
The present invention provides an apparatus and method for locating curvilinear symbols in digitized images. The invention generates a grey scale synthetic model of a symmetrically located segment of a curvilinear symbol or object, assigns foreground pixel values to those pixels located entirely within the segment; assigns background pixel values to those pixels located entirely outside the segment; and approximates pel values for boundary pixels of the segment by interpolation. The invention creates a full size grey scale full resolution model of the symbol by reflecting the segment about the axes of symmetry of the symbol. Full resolution subfeature models are created from the full size image.
Next, x and y axes coordinate weighting factors are computed for each subfeature model. These values are applied to assign a confidence level to each x and each y axis in each subfeature model. When locations corresponding to the subfeature models are found by the machine vision system, location of the symbol is computed by combining the weighted x,y coordinates in the digitized image which correspond to each subfeature model. Another aspect of the invention also assigns a weighting based on the search scores returned by the search function of the vision system used and incorporates this in the computation of the position of the object. A preferred embodiment combines both weighting methods.
The invention further provides for setting tolerance thresholds for deviation in distance from an ideal or expected or anticipated subfeature model location, based upon the position returned by a full model coarse search. The invention computes the location of the symbol using the x,y coordinates returned by the machine vision system for each weighted subfeature model after discarding distances for shapes outside the tolerance threshold.
In a preferred embodiment of the invention, the machine vision search function is asked to return a specified multiple of possible matches for each subfeature model. A weighted best fit computation is first done for the set of points found that have the best scores. Least squares error regression techniques can be used to compute a best fit for circles and other curvilinear shapes to which such best fit techniques apply. If a fit is found, the present invention next checks the positions for conformance to the tolerance thresholds. If all positions found are within tolerance, the location of the object is computed and passed to the host controller. If a position is not within tolerance, the next result for that subfeature model is selected, weighted, and subjected to best fit analysis, until a sufficient number of positions have been found within tolerance.
It is an object of this invention to use grey level synthetic models or pre-trained images to represent pixels or pels on the edge of an imaged object, rather than simply rounding up or down to an appropriate binary level to represent the edge pixels. Generating a grey level subfeature model of edge pels or selecting pre-trained grey level subfeature models enables the present invention to achieve more reliable symbol and object location.
It is a further object of this invention to reduce the time and steps needed in the generation or training of models for use in searching for circles or other curvilinear objects.
It is an aspect of the invention that using rectangles and triangles to interpolate the area of boundary pixel values is simpler a
Levine Neil S.
Picard Len L.
Cognex Corporation
Couso Jose L.
Stretch Maureen
Weinzimmer Russ
LandOfFree
Circle location does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circle location, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circle location will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2502748