# US 2010/0166294 A1 · System and method for three-dimensional alignment of objects using machine vision > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2010/0166294 A1 - Document ID: US20100166294A1 - Status: Published application - Kind: A1 - Application number: 12/345,130 - Filed: 2008-12-29 - Published: 2010-07-01 - Earliest claimed: 2008-12-29 - Assignees: Cognex Corporation - Inventors: Cyril C. Marrion; Nigel J. Foster; Lifeng Liu; David Y. Li; Guruprasad Shivaram; Aaron S. Wallack; Xiangyun Ye - Web page: https://patentgrep.com/patent/US20100166294A1 ## CPC - G06V 20/653: {by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces} - G06V 10/757: {Matching configurations of points or features} - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract This invention provides a system and method for determining the three-dimensional alignment of a modeledobject or scene. After calibration, a 3D (stereo) sensor system views the object to derive a runtime 3D representation of the scene containing the object. Rectified images from each stereo head are preprocessed to enhance their edge features. A stereo matching process is then performed on at least two (a pair) of the rectified preprocessed images at a time by locating a predetermined feature on a first image and then locating the same feature in the other image. 3D points are computed for each pair of cameras to derive a 3D point cloud. The 3D point cloud is generated by transforming the 3D points of each camera pair into the world 3D space from the world calibration. The amount of 3D data from the point cloud is reduced by extracting higher-level geometric shapes (HLGS), such as line segments. Found HLGS from runtime are corresponded to HLGS on the model to produce candidate 3D poses. A coarse scoring process prunes the number of poses. The remaining candidate poses are then subjected to a further more-refined scoring process. These surviving candidate poses are then verified by, for example, fitting found 3D or 2D points of the candidate poses to a larger set of corresponding three-dimensional or two-dimensional model points, whereby the closest match is the best refined three-dimensional pose. ## Claims ### Claim 1 A system for determining alignment of an object in three dimensional space (3D) comprising: one or more 3D sensors and one or more processing elements constructed and arranged to generate a 3D representation of a scene; a feature extraction process that generates found 3D higher level geometric shapes (HLGS) of the scene from the 3D representation; and a correspondence process that compares the found 3D HLGS to a model 3D HLGS to generate one or more candidate 3D poses of one or more objects in the scene, the correspondence process being constructed and arranged to score the plurality of candidate 3D poses and select at least one high-scoring pose based upon a sufficiently high score. ### Claim 2 (depends on 1) The system as set forth in claim 1 wherein the one or more 3D sensors each comprise an arrangement of a plurality of 2D cameras. ### Claim 3 (depends on 2) The system as set forth in claim 2 wherein the one or more 3D sensors each comprise a stereo camera head. ### Claim 4 (depends on 1) The system as set forth in claim 1 wherein the 3D representation is defined by 3D coordinates and at least one other geometric or non-geometric parameter. ### Claim 5 (depends on 4) The system as set forth in claim 4 wherein the at least one other geometric or non-geometric parameter includes at least one of edge direction, color and intensity. ### Claim 6 (depends on 1) The system as set forth in claim 1 wherein the scene includes a cluttered or confusing background of elements, and the 3D sensors are positioned, and the feature extraction process is constructed and arranged, to distinguish HLGS from the cluttered or confusing background of elements. ### Claim 7 (depends on 1) The system as set forth in claim 1 wherein the scene includes a plurality of the objects therein, and the feature extraction process is constructed and arranged to distinguish HLGS of one or more of the plurality of the objects. ### Claim 8 (depends on 1) The system as set forth in claim 1 wherein the scene includes no resolvable objects therein, and each of the feature extraction process and the correspondence process is constructed and arranged to identify an absence of the resolvable objects in the scene. ### Claim 9 (depends on 1) The system as set forth in claim 1 wherein the correspondence process is constructed and arranged to score the one or more candidate 3D poses using (a) a coarse scoring process that generates a plurality of coarse scored candidate 3D poses, and (b) a fine scoring process that generates one or more fine scored candidate 3D poses from the one or more coarse scored candidate 3D poses. ### Claim 10 (depends on 1) The system as set forth in claim 1 further comprising a verification process that is constructed and arranged to compare at least one of found 2D and found 3D points of the one or more objects with respect to at least one of model 2D and model 3D points, and thereby derive the at least one high-scoring pose. ### Claim 11 (depends on 1) The system as set forth in claim 1 wherein the scoring process is constructed and arranged to (a) compute a model coverage score for the one or more candidate 3D poses, (b) provide one or more high scoring candidate 3D poses each having a high model coverage score, (c) refine respective poses of the high-scoring candidate 3D poses based upon a comparison of found 3D points to model 3D points, and (d) select the at least one high-scoring pose from a combination of the high-scoring candidate 3D poses and the refined candidate 3D poses. ### Claim 12 (depends on 1) The system as set forth in claim 1 wherein the scoring process is constructed and arranged to define predetermined geometric regions that surround each of the model 3D HLGS and remove at least one candidate 3D pose whose found 3D HLGS include portions thereof outside of the predetermined geometric regions respectively. ### Claim 13 (depends on 12) The system as set forth in claim 12 wherein a refined set of candidate 3D poses are generated based upon a fit of portions of the found 3D HLGS within the geometric regions. ### Claim 14 (depends on 13) The system as set forth in claim 13 wherein each of the found 3D HLGS and model 3D HLGS are line segments, the predetermined geometric regions are pipes having a cross sectional shape that is at least one of circular, ovular, polygonal, or an irregular enclosed shape, and wherein the portions are line segment endpoints. ### Claim 15 (depends on 13) The system as set forth in claim 13 wherein the portions comprise all or a predetermined proportion of found 3D points with respect to the found 3D HLGS. ### Claim 16 (depends on 1) The system as set forth in claim 1 wherein the found 3D HLGS and the model 3D HLGS are based upon at least one of a line segment, an edgelet, a spline and a curve. ### Claim 17 (depends on 1) The system as set forth in claim 1 wherein the one or more 3D sensors include at least one trinocular camera head. ### Claim 18 A method for determining alignment of an object in three dimensional (3D) space comprising: generating, with one or more 3D sensors and one or more processing elements, a 3D representation of a scene; extracting features so as to generate found 3D higher level geometric shapes (HLGS) of the scene from the 3D representation; and corresponding the found 3D HLGS to a model 3D HLGS to generate one or more candidate 3D poses of one or more objects in the scene, including scoring the one or more candidate 3D poses and selecting at least one high-scoring pose based upon a sufficiently high score. ### Claim 19 (depends on 18) The method as set forth in claim 18 wherein the 3D sensors comprise each of a plurality of stereo camera heads, and further comprising arranging each of the plurality of stereo camera heads at respective vantage points with respect to the scene so as to provide a less occluded and less obstructed view of the one or more objects in the scene. ### Claim 20 (depends on 18) The method as set forth in claim 18 wherein the step of corresponding includes scoring the one or more candidate 3D poses by (a) coarse scoring that generates one or more coarse scored candidate 3D poses, and (b) fine scoring that generates one or more fine scored candidate 3D poses from the one or more coarse scored candidate 3D poses. ### Claim 21 (depends on 20) The method as set forth in claim 20 further comprising comparing at least one of found 2D and found 3D points of the one or more objects with respect to at least one of model 2D and model 3D points to thereby derive the at least one high-scoring pose. ### Claim 22 (depends on 18) The method as set forth in claim 18 wherein the scoring step includes (a) computing a model coverage score for the one or more of the candidate 3D poses, (b) providing one or more high-scoring candidate 3D poses each having a high model coverage score, (c) refining respective poses of the high-scoring candidate 3D poses based upon a comparison of found 3D points to model 3D points, and (d) selecting the at least one high-scoring pose from a combination of the high-scoring candidate 3D poses and the refined candidate 3D poses. ### Claim 23 (depends on 18) The method as set forth in claim 18 wherein the scoring step includes defining predetermined geometric regions that surround each of the model 3D HLGS and removing at least one candidate 3D pose whose found 3D HLGS include portions thereof outside of the predetermined geometric regions respectively. ### Claim 24 (depends on 23) The method as set forth in claim 23 further comprising generating the a refined set of candidate 3D poses from the one or more candidate 3D poses based upon a fit of portions of the found 3D HLGS within the geometric regions. ### Claim 25 (depends on 24) The method as set forth in claim 24 wherein each of the found 3D HLGS and model 3D HLGS are line segments, the predetermined geometric regions are pipes having a cross sectional shape that is at least one of circular, ovular, polygonal, or an irregular enclosed shape, and wherein the portions are line segment endpoints. ### Claim 26 (depends on 24) The method as set forth in claim 24 wherein the portions comprise all or a predetermined proportion of found 3D points with respect to the found 3D HLGS. ### Claim 27 (depends on 18) The method as set forth in claim 18 wherein the found 3D HLGS and the model 3D HLGS are based upon at least one of a line segment, an edgelet, a spline or a curve. ### Claim 28 A method for determining alignment of an object in three dimensional (3D) space comprising: generating, with one or more 3D sensors and one or more processing elements, a 3D representation of a scene; extracting features so as to generate found 3D higher level geometric shapes (HLGS) of the scene from the 3D representation; and corresponding the found 3D HLGS to a model 3D HLGS to generate one or more candidate 3D poses of one or more objects in the scene, including scoring the one or more candidate 3D poses and selecting at least one high-scoring pose based upon a sufficiently high score.