Method for representing objects with concentric ring signature descriptors for detecting 3D objects in range images

• US 8,274,508 B2
• Filed: 02/14/2011
• Issued: 09/25/2012
• Est. Priority Date: 02/14/2011
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Porikli, Fatih, Nguyen, Hien
• Primary Examiner(s): Nguyen, Kimbinh T
• Application Number:
  US13/026,382
• Publication Number:
  US 20120206438A1
• Time in Patent Office: 589 Days
• Field of Search: 345/419, 382/199, 382/170, 382/224, 707/999.102, 707/955, 702/150, 711/200, 711/208
• US Class Current: 345/419
• CPC Class Codes: G06V 10/76 based on eigen-space representations, e.g. from pose or different illumination conditions; Shape manifolds
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces

Abstract

A 3D object is represented by a descriptor, wherein a model of the 3D object is a 3D point cloud. A local support for each point p in the 3D point cloud is located, and reference x, y, and z axes are generated for the local support. A polar grid is applied according to the references x, y, and z axes a along an azimuth and a radial directions on an xy plane centered on the point p such that each patch on the grid is a bin for a 2D histogram, wherein the 2D histogram is a 2D matrix F on the grid and each coefficient of the 2D matrix F corresponds to the patch on the grid. For each grid location (k, l), an elevation value F(k, l) is estimated by interpolating the elevation values of the 3D points within the patches to produce the descriptor for the point p.

Claims

1. A method for representing a 3D object with a descriptor, wherein a model of the 3D object is a 3D point cloud, comprising the steps of:

locating a local support for each point p in the 3D point cloud, wherein the local support is a spherical volume S of points p_i, centered on the point p and within a radius r of the point p according to

S={p_i;

∥

p_i−

p∥

≦

r},

generating reference x, y, and z axes for the local support;

applying, according to the references x, y, and z axes, a polar grid along an azimuth and a radial directions on an xy plane centered on the point p such that each patch on the grid is a bin for a 2D histogram, wherein the 2D histogram is a 2D matrix F on the grid and each coefficient of the 2D matrix F corresponds to the patch on the grid; and

estimating, for each grid location (k, l), an elevation value F(k, l) by interpolating the elevation values of the 3D points within the patches to produce the descriptor for the point p, wherein the steps are performed in a processor.

2. The method of claim 1, further comprising:

fitting a tangent plane P to the local support by least squares so that the tangent plane P is orthogonal to the z-axis; and

defining a local reference coordinates for the tangent plane to generate the reference x, y, and z axes for the local support so that the descriptor for the local support is invariant of a viewing angle.

3. The method of claim 2, further comprising:

translating the origin of the plane P at the point p along a normal direction before defining the local reference coordinates.

4. The method of claim 2, further comprising:

selecting a subset of points along a perimeter of the local support to fit the tangent plane.

5. The method of claim 1, wherein the z-axis is a normal of the local support.

6. The method of claim 1, further comprising:

matching a first descriptor of a known object with a second descriptor of an unknown object using a matrix distance.

7. The method of claim 6, wherein matrix distance is a Euclidian distance.

8. The method of claim 6, wherein matrix distance is a Mahalanobis Euclidian distance.

9. The method of claim 6, wherein matrix distance is a Minkowsky distance.

10. The method of claim 6, wherein matrix distance is a Chebychev distance.

11. The method of claim 1, where the elevation value F(k, l) is a weighted average of elevation of points surrounding the grid location (k, l).

12. The method of claim 1, where the elevation value F(k, l) is a number of points surrounding the grid location (k, l).

13. The method of claim 1, where the elevation value F(k, l) is a weighted average of the gradient values of points surrounding the grid location (k, l).

14. The method of claim 6, wherein the matching further comprises:

embedding the first and second descriptors in a manifold, and a matching score is a geodesic distance connecting the first and second descriptors.

15. The method of claim 14, wherein the manifold is flattened.

16. The method of claim 1, further comprising:

matching the set of descriptors of a query object with the set of descriptors of another object using a discriminant ratio.

17. The method of claim 16, further comprising:

determining distances between a first descriptor and a second descriptor, wherein the first descriptor is from a query set and the second one is from a database set;

finding the smallest and the second smallest distance for each descriptor in the query set;

determining the discriminant ratio for each descriptor in the query set; and

removing the descriptors from the query set with the discriminant ratios smaller than a reliability threshold;

using the remaining descriptors to determine the distance between the descriptors of the query set and the database set.

18. The method of claim 1, wherein the descriptor is used for object registration.

19. The method of claim 1, wherein the descriptor is used to locate and determine a pose of an unknown object.

20. A method for representing an object with a descriptor, comprising the steps of:

locating a local support for each point in a point cloud representing the object;

generating reference axes for the local support;

applying, according to the references axes, a polar grid along an azimuth and a radial directions on a plane centered on the point such that each patch on the grid is a bin for a histogram, wherein the histogram is a matrix on the grid, and each coefficient of the matrix corresponds to the patch on the grid; and

estimating, for each grid location, an elevation value by interpolating the elevation values of the points within the patches to produce the descriptor for the point, wherein the steps are performed in a processor.