SYSTEM AND METHOD FOR 3D OBJECT RECOGNITION

• US 20090096790A1
• Filed: 02/20/2008
• Published: 04/16/2009
• Est. Priority Date: 10/11/2007
• Status: Active Grant

• Current Assignee: MvTec Software GmbH (MvTec LLC)
• Original Assignee: MvTec Software GmbH (MvTec LLC)
• Inventors: Ulrich, Markus, Wiedemann, Christian, Steger, Carsten
• Granted Patent: US 8,379,014 B2
• Time in Patent Office: Days
• US Class Current: 345/427
• CPC Class Codes: B25J 9/1692 Calibration of manipulator
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: G06V 30/1914 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries, e.g. user dictionaries
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

The present invention provides a system and method for recognizing a 3D object in a single camera image and for determining the 3D pose of the object with respect to the camera coordinate system. In one typical application, the 3D pose is used to make a robot pick up the object. A view-based approach is presented that does not show the drawbacks of previous methods because it is robust to image noise, object occlusions, clutter, and contrast changes. Furthermore, the 3D pose is determined with a high accuracy. Finally, the presented method allows the recognition of the 3D object as well as the determination of its 3D pose in a very short computation time, making it also suitable for real-time applications. These improvements are achieved by the methods disclosed herein.

Claims

1. A method for constructing a 3D model for 3D object recognition comprising the following steps:

(a) providing the interior parameters of the camera;

(b) providing a geometric representation of a 3D object;

(c) providing a range of poses in which the 3D object may appear with respect to the camera;

(d) creating virtual views of the 3D object by sampling the range of poses for different image resolutions;

(e) representing all views by a tree structure where views that correspond to the same image resolution reside at the same hierarchy level in the tree; and

(f) for each view creating a 2D model that can be used to find the 2D view in an image by using an appropriate 2D matching approach.

2. The method of claim 1, where the interior parameters of the camera of step (a) are obtained by performing a geometric camera calibration.

3. The method of claim 1, wherein the geometric representation of step (b) is a 3D Computer Aided Design model.

4. The method of claim 3, wherein the 3D CAD model is represented by a DXF file.

5. The method of claim 1, wherein providing the range of poses of step (c) is providing the range of poses of the camera in a fixed object coordinate system comprising the steps of:

(c1) transforming the 3D object representation into a reference object coordinate system;

(c2) providing a camera position by providing intervals for spherical coordinates longitude, latitude, and distance in the reference object coordinate system;

(c3) rotating the camera such that a Z axis of the camera coordinate system passes through the origin of the reference object coordinate system and an X axis of the camera coordinate system is parallel to a predefined plane; and

(c4) providing the camera orientation by providing an interval for a camera roll angle.

6. The method of claim 5, wherein in step (c3) the predefined plane is the equatorial plane of the reference object coordinate system.

7. The method of claim 1, wherein providing the range of poses of step (c) is providing the range of poses of the camera in the fixed object coordinate system comprising the steps of:

(c1) transforming the 3D object representation into a reference object coordinate system;

(c2) providing the camera position by providing intervals for X, Y, and Z coordinates in the reference object coordinate system;

(c3) rotating the camera such that a Z axis of the camera coordinate system passes through the origin of the reference object coordinate system and an X axis of the camera coordinate system is parallel to a predefined plane; and

(c4) providing the camera orientation by providing an interval for a camera roll angle.

8. The method of claim 7, wherein in step (c3) the predefined plane is the plane that is spanned by the X and Z axis of the reference object coordinate system.

9. The method of claims 5 or 7, wherein in step (c4) the camera roll angle is the rotation of the camera around its Z axis.

10. The method of claim 1, wherein providing the range of poses of step (c) is providing the range of poses of the object within a fixed camera coordinate system.

11. The method of claims 5 or 7, wherein the reference object coordinate system in step (c1) is identical to the object coordinate system that is defined by the geometric representation.

12. The method of claims 5 or 7, wherein the reference object coordinate system in step (c1) is the object coordinate system that is defined by the geometric representation translated to the center of the 3D object and rotated into a provided reference orientation.

13. The method of claim 1, wherein creating virtual views of the 3D object by sampling the range of poses for different image resolutions is creating virtual views of the 3D object by sampling the range of poses for different levels of an image pyramid.

14. The method of claim 1, wherein step (d) comprises the steps of:

(d1) computing an over-sampling of the views on the highest image resolution, or on a lowest pyramid level;

(d2) thinning out the views by successively merging neighboring views that have a similarity that exceeds a predefined threshold;

(d3) repeating step (d2) until no more two neighboring views have a similarity that exceeds the threshold of step (d2);

(d4) copying the merged views into the 3D model; and

(d5) repeating steps (d2)-(d4) for all image resolutions after relaxing the similarity threshold of (d2).

15. The method of claim 14, wherein the similarity in step (d2) is computed by projecting the object into the image plane of both views and computing the similarity between both projections based on the similarity measure that is used in the 2D matching approach mentioned in step (f) of claim 1.

16. The method of claim 14, wherein the similarity in step (d2) is computed by only projecting a 3D bounding box of the object into the image plane of both views and computing the similarity between both projections based on the similarity measure that is used in the 2D matching approach mentioned in step (f) of claim 1.

17. The method of claims 15 or 16, wherein the similarity measure is replaced by an analytic approximation that can be computed faster than the original similarity measure.

18. The method of claim 14, wherein the steps (d2) and (d3) are iterated by starting with a fastest approximation of the similarity measure and refining the similarity measure until the original similarity measure is used.

19. The method of claim 14, wherein relaxing of the similarity threshold in step (d5) is performed by smoothing and sub-sampling the image to get a next higher pyramid level and computing the similarity measure on the sub-sampled images.

20. The method of claim 14, wherein relaxing of the similarity threshold in step (d5) is performed by multiplying a position tolerance during an analytic approximation of the similarity measure in accordance with the pyramid level.

21. The method of claim 1, wherein step (e) comprises the steps of:

(e1) for each view storing the 3D pose of the view in the 3D model;

(e2) for each view storing a reference to all child views in the 3D model; and

(e3) for each view storing a reference to its parent view in the 3D model.

22. The method of claim 1, wherein step (f) comprises the steps of:

(f1) projecting the 3D object into the image plane of each view yielding 3-channel images, where the three channels represent the three elements of the normal vector of the faces of the 3D object; and

(f2) creating 2D models consisting of the image edges, which are obtained by thresholding the gradient amplitudes of the 3-channel images.

23. The method of claim 22, wherein creating the 2D model in step (f2) comprises creating a 2D model that can be used for a matching approach that is based on the generalized Hough transform, on the Hausdorff distance, or on the dot product of the edge gradient directions.

24. The method of claim 22, where the threshold in step (f2) is computed from a provided minimum face angle.

25. The method of claim 22, where in step (f1) a constant value is added to each image channel to ensure that the silhouette of the projected object is not suppressed by the thresholding in step (f2).

26. The method of claim 22, wherein the image edges obtained by the thresholding in step (f2) are automatically validated and the 2D model is discarded if the validation fails.

27. The method of claim 1, wherein the following additional steps are included:

(g) computing a spherical mapping of the image plane that reduces the effect of projective distortions and storing the spherical mapping in the 3D model;

(h) mapping the 2D models that are created in step (f) using the spherical mapping and storing the spherically mapped 2D models in addition to the original 2D models in the 3D model.

28. The method of claim 1, wherein the following additional step is included:

(i) computing a mapping of the image plane that eliminates the effect of lense distortions and storing the mapping in the 3D model.

29. A method for recognizing a 3D object and for determining its 3D pose from one image of the object comprising the following steps:

(a) providing a 3D model of the 3D object;

(b) providing an electronic search image of the 3D object;

(c) creating a representation of the search image containing different resolutions of the search image;

(d) matching the 2D models that do not have a parent view in a hierarchical tree structure to the image of the respective level of an image pyramid;

(e) verifying and refining the 2D matches of a top pyramid level by tracking them down to a lowest pyramid;

(f) determining the initial 3D object pose from the 2D matching pose and the respective 3D view pose; and

(g) refining the initial 3D object poses.

30. The method of claim 29, wherein step (e) comprises the following steps:

(e1) projectively transforming the 2D models of a child views in accordance with the position of the match candidate; and

(e2) matching the transformed 2D models of the child views in a restricted parameter space to the image of the respective level of the image pyramid.

31. The method of claims 29 or 30, wherein the matching in step (d) or step (e2), respectively, is based on a generalized Hough transform, on a Hausdorff distance, or on a dot product of an edge gradient direction.

32. The method of claims 29 or 30, wherein the matching in step (d) or step (e2), respectively, is based on a dot product of an edge gradient direction ignoring the local polarity of the gradients.

33. The method of claim 29, wherein in step (d) the respective pyramid level on which the matching is performed is mapped by using the spherical mapping that is stored in the 3D model to reduce projective distortions before applying the matching and wherein in step (d) the spherically mapped 2D models are used for the matching instead of the original 2D models.

34. The method of claims 29 or 30, wherein in step (d) or step (e2), respectively, the respective pyramid level on which the matching is performed is mapped by using the mapping that is stored in the 3D model to eliminate lens distortions before applying the matching.

35. The method of claim 29, wherein the refining of the initial 3D object poses in step (g) is performed by minimizing the distance between subpixel precise image edge points and a corresponding projected 3D object edge.

36. The method of claim 35 comprising the following steps:

(g1) projecting 3D model edges into the search image by using the initial 3D object pose while suppressing hidden object edges by using a hidden-line-algorithm and while suppressing object edges at which the angle between the two adjacent faces is below a provided minimum face angle;

(g2) sampling projected edges to discrete points in accordance with the pixel grid

(g3) finding for each sampled edge point the corresponding subpixel-precise image edge point in the neighborhood of the sampled edge point; and

(g4) determining the 6 parameters of the refined 3D object pose by minimizing the sum of squared distances between point correspondences by using an iterative non-linear optimization algorithm.

37. The method of claim 36, wherein in step (g3) finding the corresponding subpixel-precise image edge point is restricted to a direction that is perpendicular to the projected model edge.

38. The method of claim 36, wherein in step (g3) only correspondences with an angle difference below a threshold are accepted as valid correspondences, where the angle difference is computed between the perpendicular to the projected model edge and the image gradient.

39. The method of claim 36, wherein in step (g4) the squared distances are weighted according to the angle difference during the optimization, where the angle difference is computed between the perpendicular to the projected model edge and the image gradient.

40. The method of claim 36, wherein the steps (g1) to (g4) are iterated until the refined 3D object pose does not change significantly between the last two iterations.

41. The method of claim 36, wherein the steps (g1) to (g4) are iterated for a provided fixed number of iterations.

42. The method of claims 40 or 41, wherein in step (g1) the hidden-line-algorithm is only applied in the first iteration, whereas in higher iterations only the parts of the 3D model edges that have been visible in the first iteration are projected without performing the hidden-line-algorithm anew.

43. The method of claims 29 or 30, wherein a gradient direction in the image is expanded before performing the matching by applying a maximum filter to the gradients where at each filter position the gradient vector at the center of the filter is replaced by the gradient vector with the largest amplitude within the filter.

44. A method for augmenting a 3D model with texture information:

(a) providing two or more example images of the 3D object;

(b) determining the 3D pose of the 3D object in each of the example images by using the steps that are described in claim 31;

(c) for each example image projecting each face of the 3D model into the example image using the 3D pose determined in step (b);

(d) for each object face rectifying the part in the example image that is covered by the projected face using the 3D pose of the face; and

(e) augmenting the 2D models with the derived texture information of the rectified textured object faces, resulting in 2D models containing both geometric information as well as texture information.

45. The method of claim 44, wherein step (e) is replaced by the following step:

(e) regenerating the 2D models by using only the derived texture information of the rectified textured object faces and omitting the geometry information.