Image analysis – Applications – Manufacturing or product inspection
Reexamination Certificate
1998-04-03
2001-11-27
Boudreau, Leo (Department: 2721)
Image analysis
Applications
Manufacturing or product inspection
C382S103000, C382S216000, C382S287000, C382S289000, C382S291000, C348S169000, C358S488000
Reexamination Certificate
active
06324299
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to searching for an image of an object within an image of a region that may contain the object.
BACKGROUND OF THE INVENTION
In the field of searching for an image of an object in an image that may contain the image of the object, it is known to use a model to search for the object image by using Normalized Correlation Search, Generalized Hough Transforms, or PatMax, sold by Cognex Corporation, Natick Mass, for example. A model is defined herein as a set of acceptable spatial arrangements of features of an object. Examples of models include: geometric models, wire frame models, CAD models, an image of a typical object, an image of an ideal object, an image of a sought object, an edge-detected image of an object, and a Generalized Hough Transformed image of an object. However, when the relationship between the image of the object and the model of the object is described by a non-linear transformation, search speed and robustness may be reduced.
When searching for an image of an object, it is known to use sub-models to accommodate non-linear transformations between the image of the object and the model of the object. A sub-model of an object is a model of a portion of the object. For example, it is known in the art to define a plurality of sub-models (also referred to as “parts”) of an object to be found, and then use the plurality of sub-models to find images of portions of the object. In this case, the entire image is searched for images of the portions using each sub-model. Then, the found poses of the sub-models are fit to the corresponding poses of the sub-models in the model of the entire object. (A pose is a generalized position, including location, orientation, scaling, skew, etc.) To accomplish this fit operation, the sub-models must be mutually distinguishable, thereby providing correspondence. Alternatively, the correct correspondence between the sub-models in the image of the entire object and the sub-models in the model must be determined via combinatorial search and verification techniques.
In the above known techniques for searching using sub-models, the specification of the model of the object is made by first defining the individual sub-models of the object, and then defining the model of the object as a spatial arrangement of the sub-models. However, once the model is created in this fashion, changing the model definition or its sub-model definition requires a completely new definition of this spatial arrangement, which can be problematic. Moreover, it is not easy to automatically extract optimized sub-models of the object and to automatically extract the pose of each sub-model within the model. Consequently, the user typically must define the sub-models that are used to locate the image of the object.
SUMMARY OF THE INVENTION
The invention provides a method of locating an object within a client region, where the object has a plurality of portions. The method includes defining a full geometric model of the object; defining a plurality of geometric sub-models of the object; determining coarse candidate poses of the object within the region using an image of the region and the full geometric model of the object; determining the fine pose of each of a plurality of portions of the object using the coarse candidate poses of the object within the region, and at least some of said geometric sub-models, to provide a plurality of object portion fine poses within the region; and then determining the fine poses of the object within the region using said plurality of object portion fine poses.
In a preferred embodiment, defining a plurality of sub-models of the object includes defining the pose of each sub-model within the reference frame of the full model. In a further preferred embodiment, determining the fine pose of each of a plurality of portions of the object includes determining the coarse poses of each of a plurality of portions of the object, and using each coarse pose, determining the fine pose of each of the plurality of portions of the object.
Further, determining the fine pose of each of a plurality of portions of the object occurs locally and independently for each portion of the object.
In another preferred embodiment of the invention, using a full geometric model of the object to determine the coarse candidate poses of the object includes creating an image search model in an image frame of reference. Moreover, creating an image search model in an image frame of reference can include creating a template matching model of the object. In particular, creating an image search model in an image frame of reference can include creating a normalized correlation search model of the object. Also, creating an image search model in an image frame of reference can include creating a generalized Hough transform model of the object.
In a further preferred embodiment, using a geometric sub-model to determine the fine pose of a portion of the object includes creating an image search model in an image frame of reference for that sub-model.
The invention provides a general purpose, user-configurable shape finding method for many machine vision applications where object are to be found using images such as in the inspection of surface mounted devices and fiducial marks.
The invention builds on the strengths of image-based search tools, such as PatMax and PatQuick, sold by Cognex Corporation, by adding the ability to deal with moderate deformations in objects.
The invention allows a client to choose a sub-model strategy that works best for a particular set of object characteristics and imaging conditions.
The invention allows geometric descriptions of objects (such as resistor chips, ball grid array packages, flip chips, etc.) to be specified in an arbitrary coordinate system, such as a physical (real world) coordinate system. This allows the same model to be used when locating the object within the physical world over a wide range of imaging conditions.
The invention provides a powerful method for finding objects in images that is efficient in both memory space and computational time.
The invention avoids the need for users to deal explicitly with lower-level, more complicated vision tools.
The invention provides an automatic method for specifying sub-models, thereby allowing users that are not highly skilled in the art of machine vision to rapidly create effective object inspection systems.
REFERENCES:
patent: 4731860 (1988-03-01), Wahl
patent: 4980971 (1991-01-01), Bartschat et al.
patent: 5060276 (1991-10-01), Morris et al.
patent: 5113565 (1992-05-01), Cipolla et al.
patent: 5226095 (1993-07-01), Okumura et al.
patent: 5268999 (1993-12-01), Yokoyama
patent: 5343028 (1994-08-01), Figarella et al.
patent: 5371690 (1994-12-01), Engel et al.
patent: 5471541 (1995-11-01), Burtnyk et al.
patent: 5495537 (1996-02-01), Bedrosian et al.
patent: 5497451 (1996-03-01), Holmes
patent: 5500906 (1996-03-01), Picard et al.
patent: 5545887 (1996-08-01), Smith et al.
patent: 5602937 (1997-02-01), Bedrosian et al.
patent: 5621807 (1997-04-01), Eibert et al.
patent: 5625715 (1997-04-01), Trew et al.
patent: 5627912 (1997-05-01), Matsumoto
patent: 5627915 (1997-05-01), Rosser et al.
patent: 5663809 (1997-09-01), Miyaza et al.
patent: 5828769 (1998-10-01), Burns
patent: 5845288 (1998-12-01), Syeda-Mahmood
patent: 5850469 (1998-12-01), Martin et al.
patent: 5963664 (1999-10-01), Kumar et al.
patent: 5974169 (1999-10-01), Bachelder
patent: 6037949 (2000-03-01), DeRose
Newmann, et al “3D CAD-Baed Inspection I: Coarse Verification”, IEEE, pp. 49-52, 1992.*
Hoogs, et al “Model-Based Learning of Segmentations”, IEEE, pp. 494-499, 1996.*
Ullman, Shimon, “Aligning pictorial descriptions: An approach to object recognition, I: Approaches to Object Recognition,” reprinted fromCognition, Aug. 1989, pp. 201-214, vol. 32, No. 3, Cambridge, MA, USA.
Cognex Corporation, “Chapter 5 Fiducial Finder,”Cognex 4000/5000 SMD Placement Guidance Package User's Manual, 1996, pp. 179-223, Release 3.2 590-0139, Natick, MA, USA.
Cognex Corporation, “Chapter 7 Rectilinear
Bachelder Ivan A.
Chang Yian Leng
Marrion Cyril C.
Sarachik Karen B.
Boudreau Leo
Cognex Corporation
Mariam Daniel G.
Weinzimmer Russ
LandOfFree
Object image search using sub-models does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Object image search using sub-models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Object image search using sub-models will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2580288