Boundary analyzer

Details Boundary analyzer Boundary analyzer

1999-02-05

2004-03-30

Mehta, Bhavesh M. (Department: 2625)

Image analysis

Pattern recognition

Feature extraction

C345S442000, C345S443000, C382S103000, C382S151000, C382S153000, C382S202000, C382S203000, C382S294000

Reexamination Certificate

active

06714679

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to machine vision, and particularly to methods and apparatuses for analyzing a boundary of an object in an image.
BACKGROUND
The problem of quantitatively describing the shape of an object in an image is central to the field of image processing. Although shape description techniques have been developed for such diverse purposes as character recognition, classification of tactical targets, and assembly line inspection, typically, greater accuracy for inspection of the shape is desired.
In machine-vision systems, operation is broken into two phases: training and inspection. Training, in the case of shape analysis, involves constructing a model of the shape and storing it in memory. Thereafter, during inspection, also known in the industry as runtime, a machine-vision system acquires an image of the object and analyzes the object using the model of the object generated during training. The machine-vision system performs further operations on the image, such as searching for features or deviation analysis.
The accuracy of the results depends upon the model. Noise is common in models that are templates of a good image. When the model contains noise, the results reflect the error in the model caused by the noise.
One result, deviation analysis, typically cannot detect sub-pixel errors, particularly when the analysis uses a subtraction procedure. A subtraction procedure aligns the model and the image, and then combines the two images by subtracting one from another yielding a difference image. The pixel values of the difference image represent differences between the model and the image, such as noise. The difference image is very sensitive to noise, and the noise can be erroneously mistaken for defects, making the procedure identify false errors. To decrease false errors, the effect of noise is minimized somewhat by filtering or morphing the difference image, techniques known in the art. The techniques remove noise or enlarge defects. However, when the goal is to measure the area of the defect as opposed to its presence, these techniques frustrate measurement and make it difficult, if not impossible, to produce accurate sub-pixel error measurement.
There is a clear need for building a more precise model and using the information in inspection, such as sub-pixel error detection.
SUMMARY
The invention provides methods and apparatuses for analyzing a boundary of an object within an image. To analyze the boundary, the method “matches” a representation of the boundary with a representation of a model boundary. In particular, the method “matches” the vertices of the boundary with the vertices of the model boundary. Thereafter, the method measures deviations in the runtime segments whose vertices were “matched” to traintime vertices. The measurement is made using a training class associated with the runtime segments, where the training class becomes associated with the runtime segment during the “matching.” Alternatively, the method computes a correlation score indicative of the number of “matches” of runtime vertices to traintime vertices.
Before measuring deviations or computing a correlation score, first the method provides two sets of segments: a first set of traintime segments and a second set of runtime segments. The first set represents the model boundary of the object, such as a boundary during training, and the second set represents the boundary of the object later, such as a boundary during inspection. Each traintime segment and runtime segment has traintime vertices or runtime vertices, respectively, where at least portions of the vertices are approximately the endpoints of the segments. Further, each traintime segment has a training class, such as a line or an arc, for example.
In one embodiment, the accuracy and reliability of the segments and the vertices are enhanced before being “matched.” One enhancement is to merge, into a single segment, neighboring segments that are similar, where, in a preferred embodiment, similarity is measured and established using statistical analysis. Another enhancement is to reassign data points of the boundary to neighboring segments whenever a data point “fits better” with its neighboring segment than its initial segment. In one embodiment, “fits better” constitutes minimizing any error between fitting a data point to the initial segment or the neighboring segment. The error is minimized by minimizing a residual error of the fit to the data point between the initial segment and the neighboring segment.
Once the segments and the vertices are provided, the method substantially “matches” at least some of the runtime vertices to at least some of the traintime vertices. In a preferred embodiment, a runtime vertex matches a traintime vertex when the runtime vertex is within a predetermined distance of a traintime vertex. The invention recognizes, among other things, that this process will allow the segmentation of the runtime boundary to be compared usefully to the traintime boundary.
Once matched, a runtime segment becomes associated with the training class of the traintime segment whose traintime vertices most closely matched the runtime vertices of that runtime segment.
The training class is used to measure deviations in the matched runtime segments, where a training class is a line or an arc, for example. An equation of that class is generated of that class that “best fits” the data points of the runtime segment. In one embodiment, the deviation of the data points in the runtime segment from the equation is compared against defect tolerances provided by a user, where a defect can have a height tolerance, duration tolerance, or an area tolerance, for example. The invention recognizes that a parse (which can also be called a segmentation) of a boundary can be trained and used for inspection by exploiting the matching of its vertices.
In further aspects, preferably, the set of runtime segments is refined and rematched a second time to improve the utility of the invention for a variety of boundaries. More particularly, the segmentation of the runtime boundary is altered to allow more runtime segments to match traintime segments.
During the refinement, for each traintime vertex that remained unmatched after the first pass, an additional runtime vertex is provided on the runtime boundary at a position as close as possible to the unmatched traintime vertex. Any runtime vertices that remained unmatched after the first pass are effectively removed, and the segments sharing the unmatched runtime vertex are merged. The refined segmentation of the runtime boundary is then rematched against the initial traintime vertices, as described earlier. Refining the segmentation greatly increases the number of matched vertices. Therefore, more runtime segments can be analyzed for defects. Thus, the performance and repeatability of the method is enhanced.
In further aspects, the representation of the model boundary can be used for other vision processes outside of boundary analysis, both alone or in combination with the matching and refinement of the segmentation steps of a preferred embodiment.
In further aspects, the invention provides an apparatus in accord with the methods described above. The aforementioned and other aspects of the invention are evident in the drawings and in the description that follows.
One advantage of the invention is the invention saves computational time by analyzing a subset of pixels of the image, i.e. that is vertices, for many computational steps.
One of the additional advantages of the invention is the invention can accommodate objects having different lengths or scales.
A further advantage is that the invention can analyze objects at any rotation and it is rotation invariant.
A still further advantage is that the invention can be fully automated, and once an image of a training object is obtained, the invention can automatically provide the results.
In addition to the other advantages, the invention solves some of the deficiencies in the prior art. The model is less influenced by noise, th

Affiliated with

Also associated with

Rating

Boundary analyzer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Boundary analyzer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boundary analyzer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3258195