Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2000-10-30
2004-11-02
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S419000, C382S199000, C382S203000
Reexamination Certificate
active
06812933
ABSTRACT:
COPYRIGHT NOTICE
The disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the United States Patent and Trademark Office patent file or records, once a patent is issued on this application, but otherwise reserves all copyright rights whatsoever.
FIELD OF THE INVENTION
This invention relates to methods for rendering shapes, and particularly to such methods that are automated.
BACKGROUND OF THE INVENTION
The ability to determine the position and/or attitude of an object is of considerable practical importance in many applications, including industrial manufacturing, robot guidance, intelligent transportation systems, mail and parcel handling, and many others. Position might include up to three degrees of freedom (e.g., up-down, in-out, and side-ways), and the three degrees of freedom of attitude (e.g., pitch, yaw, and roll). Together, these six degrees of freedom can be used to describe what can be referred to as the “location” or “pose” of an object. Note that here, “location” or “pose” can mean more than just position in three spatial dimensions—it can also include information as to the other non-translational degrees of freedom, such as skew, perspective, aspect-ratio, and many other more exotic non-translational degrees of freedom. In a two-dimensional plane, position includes two translation degrees of freedom (e.g., up-down and side-ways), and at least one non-translation degree of freedom, such as “orientation” (a rotation degree of freedom), and possibly skew, aspect ratio, size, and others.
It is well-known to use machine vision to locate objects at a distance. A digital image of a scene containing an object to be located is formed by any suitable apparatus, for example consisting of visible light illumination, a CCD camera, and a video digitizer. The digital image is then analyzed by a suitable image analysis device, for example consisting of a digital signal processor or personal computer running software that implements a suitable method for identifying and locating image patterns that correspond to the object of interest. The analysis results in certain parameters that describe the pattern in the image that corresponds to the object, or a suitable portion of the object, in the scene. These parameters might include position, attitude, and size of the pattern in the image. These parameters are then used to compute the location (pose) of the object using well-known mathematical formulas.
There are many methods known in the art for analyzing digital images to determine one or more of the pattern parameters, including blob analysis, normalized correlation, Hough transforms, and geometric pattern matching. Numerous other methods have been used or proposed in commercial practice or in academic literature.
The process of determining object location (pose) by machine vision can be referred to in various ways, including “alignment”, “registration”, “pattern recognition”, and “pattern matching”. For present purposes herein, those terms are equivalent, and so herein the term “alignment” shall be used to refer to any such process. Any object, or portion of an object, that gives rise to the pattern in the image to be analyzed shall be called an “alignment target”, or simply a “target”.
Most machine vision alignment applications require locating targets having a shape determined by engineering considerations that are largely independent of the needs of automated visual alignment. In these cases, the objects contain no special markings or components specially adapted to aid the alignment method. Consequently, the alignment method must work with whatever object shape is given. There are many applications, however, where the alignment target can be engineered specifically for that purpose. Examples include fiducial marks on printed circuit boards, registration marks etched on silicon wafers, and “bull's eye” targets used by the United Parcel Service on package labels. A target that has been engineered to aid machine vision alignment can be called a “cooperative target.” In contexts where it is clear that a target has been engineered for alignment, the modifier “cooperative” is sometimes omitted, but “cooperative” is understood.
Although alignment methods have an extensive literature and commercial history, relatively little work has been done on understanding the effect of target shape on alignment performance. The work is almost entirely restricted to shapes composed of circles and polygons, to the effect of such shapes on binary image analysis methods, to translation-only (i.e., horizontal and vertical) alignment, and to accuracy criteria only.
Rotationally symmetric targets, primarily circles and “bull's-eye” patterns, have long been a favorite in the academic literature. In a 1974 paper, for example, W. Makous “Optimal Patterns for Alignment”, in Applied Optics, Vol. 13, No. 3, states that “a bull's-eye pattern of regularly alternating black and white rings would be optimal for visual alignment in two dimensions.” Twenty four years later, in a 1998 paper entitled “Design of Shapes for Precise Image Registration”, in IEEE Trans. on Information Theory, Vol. 44, No. 7, Bruckstein, O'Gorman, and Orlitsky state that “Experimental tests and . . . theoretical developments . . . led to the conclusion that the ‘bull's-eye’ fiducial is indeed a very good, robust and practical location mark.”
Rotationally symmetric targets suffer from a number of limitations, however, that have not been anticipated in the prior art. First, such targets contain no information for measuring orientation. This has been considered an advantage, based on the assumption that alignment methods would fail under orientation misalignment unless the target is rotationally symmetric, but the recent advent of practical methods for orientation alignment have created a need for targets that convey substantial orientation information.
A second limitation of rotationally symmetric targets, such as the “bull's eye” pattern, is that circles and arcs of circles are extremely common in manufactured items, and one cannot guarantee that such shapes will not appear in the field of view containing the target. The appearance of such a shape in the same field of view as a target composed of circles or arcs of circles results in potential confusion for the alignment method, and this confusion usually leads to higher recognition error rates under variations in image quality typically encountered in an industrial environment.
A third limitation of rotationally symmetric targets is that they are often not good choices for measuring size, what might be called “size alignment”. While such a target does contain plenty of information for conveying size, the concentric circular boundaries match each other perfectly at many different sizes. At the correct size the overall target match will be higher than at any of the wrong sizes, but the matches at the wrong sizes are sometimes good enough to create confusion under realistic conditions of image degradation. This “self-confusion” can lead to higher recognition error rates. Furthermore, this self-confusion generally requires that any practical alignment method must examine the “size” degree of freedom more carefully to avoid error, which increases recognition time.
The academic literature has also considered using as alignment targets simple polygons such as squares and diamonds, as well as complex sequences of stripes that are optimal for 1D or 2D alignment in some theoretical sense, but are almost impossible to manufacture.
Known targets in commercial use include simple geometric shapes such as circles, bull's-eyes, squares, crosses, two squares touching at a corner, and patterns consisting of a cross embedded in a circle.
In the semiconductor industry, significant attention has been given to the engineering of targets used to achieve the extreme accuracy needed to register the
Bella Matthew C.
Blackman A
Cognex Technology and Investment
Weinzimmer Russ
LandOfFree
Method for rendering algebraically defined two-dimensional... 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 for rendering algebraically defined two-dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for rendering algebraically defined two-dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3363160