Image analysis – Histogram processing
Reexamination Certificate
1998-05-28
2001-06-19
Couso, Yon J. (Department: 2623)
Image analysis
Histogram processing
C382S142000
Reexamination Certificate
active
06249602
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to machine vision, and particularly to determining a reference point, such as the center, of an object profile of unknown size but known shape using a machine vision system.
BACKGROUND
It is known in the machine vision industry how to search for an object of a known size and shape in an image. Such techniques are used to align a template of the object with the image of the object so that further processes can inspect portions of the object, such as printing on the surface of the object, roundness of the object, or the presence/absence of a pill contained in the object.
Here, an image is a rectangular, two-dimensional array of grey values, where each element in the array is called a pixel. A template is similar to an image, except that it need not be rectangular, or even simply connected, i.e. it may consist of a collection of disjoint regions. A template is similar to an image also in that each element of the template is assigned a grey value.
In general, the methodology for searching for an object of known size and shape in an image is to first construct the template of the object; then search a likely area of the image of the object for the portion of the image to which the template is most similar. Various methods, such as that taught in U.S. Pat. No. 5,548,326 Efficient Image Registration, have been developed to improve the efficiency of such searches.
Once the object is found, it can be said to be aligned with respect to the template. Alignment shall be defined as orienting the object with respect to the template to make at least one alignment parameter of the object, such as the planar position, substantially equal to the corresponding alignment parameter of the template. After alignment, commonly, the machine vision system returns a metric representative of the goodness of fit, a measure of the aggregate deviations of the actual object from the template.
However, when the size of the object to be found is unknown, the known search techniques have had to be modified to include multiple templates of various sizes. Multiple templates are needed because typically such techniques search for objects that are the same size as the template. The techniques typically compare pixels of the image to elements of the template for a match. Thus, the pixel values of the image and the elements of the template will not correspond unless an appropriately scaled template with appropriate number and arrangement of elements is used. However, it is not always possible to know which sizes of the template are required for effective searching.
The possibility of flaws in the object further diminishes the usefulness of current search techniques for objects of an unknown size. Under such circumstances, known techniques take an unacceptably long time. Further, even when given a longer time to search, known techniques have difficulty distinguishing between a perfect but differently sized object, and a flawed but correctly sized object.
SUMMARY
An efficient and accurate alignment method and apparatus provides the position of a reference point, such as the center, of an “object profile”, even when an exact size of the object, and thus the size of the profile of the object, is unknown. The method generates a synthetic labeled-projection model based upon the “object profile” to be found, acquires an image of the object, and defines a window to enclose at least a portion of the image. The image is evaluated by performing a normalized labeled projection of the image of the object using the model of the object at each location in the image within the window, which generates a histogram of the image for each location. The histogram is a representation of all pixels in the image that are similarly labeled in the labeled-projection model. Next, the histogram is differentiated and the maximum absolute value is noted for each location. Thereafter, a comparison can be made between the maximum absolute values of the first derivative of each of the locations. Ultimately, the peak of the maximum absolute values of the first derivative is determined. The position of the labeled-projection model associated with the peak provides the position of the reference point of the “object profile.” More particularly, the position of the center of the labeled-projection model associated with the peak is the position of the center of the “object profile.”
The first derivative of the histogram is greatest when a feature of the image, such as the “object profile”, is aligned with a feature denoted by a specific label of the labeled-projection model, such as the shape of the “object profile.” Therefore, the method uses the peak of the all the histogram's first derivatives to find the reference point of the “object profile”. Since flaws in the object will rarely align with labels of the labeled-projection model, the flaws will not significantly effect finding the reference point of the “object profile”. Moreover, the labeled-projection model is labeled such that “object profiles” of varying sizes can be found.
Not only can the “object profile” be found despite flaws and unknown size, but the reference point of the “object profile” can also be found efficiently. In one embodiment, more than one window is defined to reduce the area of the image at which the normalized labeled projection must be performed for each position of the labeled-projection model, thereby, enhancing efficiency. The multiple windows of this embodiment enclose a smaller area of the image than the single window of the previous embodiment. Although a smaller area is searched for each normalized labeled projection, the “object profile” is identified because the smaller windows are defined to enclose enough of the “object profile” within the windows. Thus, use of more than one small window enhances the efficiency of the method and apparatus by decreasing the number of computations required without substantially decreasing reliability.
In a preferred embodiment, the number of times the labeled-projection model is moved with respect to the image is decreased to enhance efficiency. Two or more one-dimensional searches are used to increment the labeled-projection model's position as opposed to an area search of an alternative embodiment.
In particular, when there is greater uncertainty about the size of objects to be inspected, the invention obtains more accurate and faster results than known methods, which is advantageous in many inspection applications.
REFERENCES:
patent: 5204911 (1993-04-01), Schwartz et al.
patent: 5278983 (1994-01-01), Kawabe et al.
patent: 5548326 (1996-08-01), Michael
patent: 5550763 (1996-08-01), Michael et al.
patent: 5581632 (1996-12-01), Koljonen et al.
patent: 5818443 (1998-10-01), Schott
patent: 5848181 (1998-12-01), Ogata
patent: 5901241 (1999-05-01), Koljonen et al.
Cognex 3000/4000/5000, Image Processing, “Labeled Projection Tool”, Chapter 7, pp. 354-366 (1996).
Dutta-Choudhury Paul
Koljonen Juha
Michael David J.
Calabresi Tracy M.
Cognex Corporation
Couso Yon J.
Weinzimmer Russ
LandOfFree
Method and apparatus for determining a reference point of an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining a reference point of an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining a reference point of an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443096