SMART PICKING IN 3D POINT CLOUDS

• US 20090103773A1
• Filed: 10/22/2008
• Published: 04/23/2009
• Est. Priority Date: 10/23/2007
• Status: Active Grant

• Current Assignee: Leica Geosystems AG (Hexagon AB)
• Original Assignee: Leica Geosystems Holdings AG (Hexagon AB)
• Inventors: Kazhiyur-Mannar, Ramakrishnan, Li, Zhiyun, Wheeler, Mark Damon, Wallace, William Edward
• Granted Patent: US 8,396,284 B2
• Time in Patent Office: Days
• US Class Current: 382/100
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 7/4802 using analysis of echo signal for target characterisation; Target signature; Target cross-section
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

An embodiment of the invention includes a method for identifying a point representing a feature in a 3D dataset. The method includes performing a pick, which includes filtering the dataset to extract a subset of points based on certain criteria including a seed point and evaluating a metric for each point in the subset of points. The metric is a non-normalized probability that the point being evaluated represents the feature. The point or points with the highest metric is identified as representing the feature. Another embodiment of the invention includes a computer-readable medium comprising computer-executable instructions for identifying a point representing a feature in a 3D dataset. Another embodiment of the invention includes a method for displaying a view of a feature in a 3D dataset.

Claims

1. A method for identifying a point representing a feature in a 3D dataset comprising:

performing a pick, wherein the pick includes;

filtering the dataset including extracting a subset of points based on certain criteria, wherein the criteria include a seed point; and

evaluating a metric for each point in the subset of points, wherein the metric is a non-normalized probability that the point being evaluated represents the feature; and

identifying a point or points with the highest metric as representing the feature.

2. A method according to claim 1, wherein the 3D dataset includes a point cloud.

3. A method according to claim 1, wherein the step of filtering includes at least one of the set consisting of:

filtering based on spatial position;

filtering based on color;

filtering based on intensity; and

filtering based on a normal angle.

4. A method according to claim 1, wherein filtering the dataset further includes using a filter that is conical in shape, wherein the conical filter includes:

an apex of the cone that is at a camera point;

an axis of the cone including a line through the apex and through the seed point; and

selecting all points within the cone as the subset of points.

5. A method according to claim 1, wherein filtering the dataset further includes using a filter that is cylindrical in shape, wherein the cylindrical filter includes:

an axis of the cylinder including a line through the seed point and substantially parallel to the z-axis; and

selecting all points within the cylinder as the subset of points.

6. A method according to claim 1, wherein the pick is a closest pick, wherein the closest pick identifies a non-occluded point rendered at a given screen coordinate.

7. A method according to claim 6, wherein the closest pick includes:

selecting a point provided by a user as the seed point;

filtering with a filter that is conical in shape and selecting all points within the cone as the subset of points; and

evaluating the metric for each point in the subset of points as the negative of the distance between the point being evaluated and a camera point.

8. A method according to claim 6, wherein the closest pick includes:

selecting a point provided by a user as the seed point;

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points; and

evaluating the metric for each point in the subset of points as the negative of the distance between the point being evaluated and a camera point.

9. A method according to claim 1, wherein the pick is a highest pick, wherein the highest pick identifies a point that is vertically highest in the vicinity of a user'"'"'s pick location.

10. A method according to claim 9, wherein the highest pick includes:

selecting a closest pick as the seed point;

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points; and

evaluating the metric for each point in the subset of points as the z-coordinate of the point being evaluated.

11. A method according to claim 1, wherein the pick is a lowest pick, wherein the lowest pick identifies a point that is vertically lowest in the vicinity of a user'"'"'s pick location.

12. A method according to claim 11, wherein the lowest pick includes:

selecting a closest pick as the seed point;

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points; and

evaluating the metric for each point in the subset of points as the negative of the z-coordinate of the point being evaluated.

13. A method according to claim 1, wherein the pick is a lowest planar surface pick, wherein the lowest planar surface pick identifies a point on the lowest elevation plane.

14. A method according to claim 13, wherein the lowest planar surface pick is a ground pick.

15. A method according to claim 13, wherein the lowest planar surface pick includes:

selecting a closest pick as the seed point; and

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points.

16. A method according to claim 14, wherein evaluating the metric for each point in the subset of points includes:

dividing the subset of points into one or more horizontal slices, wherein the horizontal slices include points within the subset of points that have z-coordinates within a predetermined range;

projecting all points within each horizontal slice onto a bitmap;

counting the number of bits containing one or more points as a footprint size of each horizontal slice;

comparing the footprint size of each horizontal slice to the footprint size of neighboring slices; and

assigning high confidence to the lowest horizontal slice and to any horizontal slice which has a footprint size significantly different than neighboring slices and low confidence to all other slices.

17. A method according to claim 16, wherein evaluating the metric for each point in the subset of points further includes:

checking each high confidence slice for a group of points forming a plane using a RANSAC algorithm;

assigning the highest metric to the intersection of the fitted plane within the high confidence slice with the lowest elevation which can be fit to a plane and an axis of the cylindrical filter;

checking each low confidence slice for a group of points forming a plane using a RANSAC algorithm when no high confidence slice fits a plane;

assigning the highest metric to the intersection of the fitted plane within the low confidence slice with the lowest elevation which can be fit to a plane and an axis of the cylindrical filter when no high confidence slice fits a plane; and

assigning the highest metric to the intersection of the best fitting plane within any slice and an axis of the cylindrical filter when neither the high confidence nor low confidence slices fit to a plane.

18. A method according to claim 16, wherein the horizontal slices are adjacent to and share boundaries with neighboring slices.

19. A method according to claim 16, wherein the horizontal slices overlap neighboring slices.

20. A method according to claim 16, wherein the horizontal slices are not adjacent to and do not overlap neighboring slices.

21. A method according to claim 1, wherein the pick is a line stripe pick, wherein the line stripe pick identifies a point which:

is on the endpoint of the line stripe if the subset of points contains a line stripe with an endpoint;

is on the medial axis of the line stripe if the subset of points contains a line stripe with no endpoint;

or

is the intersection of the medial axes of the line stripes when the subset of points contains an intersection of multiple line stripes.

22. A method according to claim 21, wherein the line stripe pick includes:

selecting a ground pick as the seed point; and

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points.

23. A method according to claim 22, wherein evaluating the metric for each point in the subset of points includes:

separating the subset of points into a group of points having high intensities and a group of points having low intensities;

extracting line stripes from the points having high intensities using a RANSAC algorithm;

improving the fit of the lines using an optimization algorithm; and

assigning the highest metric to the point which;

is on the endpoint of the line stripe if the subset of points contains a line stripe with an endpoint;

is on the medial axis of the line stripe if the subset of points contains a line stripe with no endpoint;

or

is the intersection of the medial axes of the line stripes when the subset of points contains an intersection of multiple line stripes.

24. A method according to claim 23, wherein the optimization algorithm includes a Hooke-Jeeves algorithm.

25. A method according to claim 1, wherein the pick is a plane edge pick, wherein the plane edge pick identifies a point on the edge of a plane.

26. A method according to claim 25, wherein the plane edge pick includes:

selecting a closest pick as the seed point; and

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points.

27. A method according to claim 26, wherein evaluating the metric for each point P in the subset of points includes:

performing for each point P′

within a small distance of P;

selecting each point P″

within the subset of points;

adding a first negative score to the metric of the point P, wherein the first negative score is inversely scaled by the distance from the point P″

to the horizontal plane containing the line PP′

; and

adding a second negative score to the metric of the point P, wherein the second negative score is inversely scaled by the distance from the point P″

to the vertical plane containing the line PP′

.

28. A method according to claim 1, wherein the pick is a trough detection pick, wherein the trough detection pick identifies a lowest and flattest point in an immediate area.

29. A method according to claim 28, wherein the trough detection pick includes:

selecting a ground pick as the seed point;

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points; and

evaluating the metric for each point in the subset of points as the absolute value of the dot-product of the normal of a plane and the z-axis, wherein the plane is found by fitting a plane through the points within a sphere centered on the point being evaluated.

30. A method according to claim 28, wherein the trough detection pick further comprises:

selecting a ground pick as the seed point;

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points; and

performing the steps of;

a first step including starting at the seed point and lowering the point;

a second step including fitting a plane through the points within a sphere centered on the lowered point;

a third step including projecting the lowered point to the plane as a new seed point; and

repeating the first, second and third steps until the new seed point is the same point as the previous seed point.

31. A method according to claim 1, wherein the pick is a ridge detection pick, wherein the ridge detection pick identifies a highest and flattest point in an immediate area.

32. A method according to claim 31, wherein the ridge detection pick includes:

selecting a ground pick as the seed point;

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points; and

evaluating the metric for each point in the subset of points as the absolute value of the dot-product of the normal of a plane and the z-axis, wherein the plane is found by fitting a plane through the points within a sphere centered on the point being evaluated.

33. A method according to claim 31, wherein the ridge detection pick further includes:

selecting a ground pick as the seed point;

filtering with a filter that is cylindrical in shape and selecting all points within the cylinder as the subset of points; and

performing the steps of;

a first step including starting at the seed point and raising the point;

a second step including fitting a plane through the points within a sphere centered on the raised point;

a third step including projecting the raised point to the plane as a new seed point; and

repeating the first, second and third steps until the new seed point is the same point as the previous seed point.

34. A computer-readable medium comprising computer-executable instructions for performing the steps of claim 1.

35. A method for displaying a view of a feature in a 3D dataset comprising:

defining the feature to be detected;

picking a point representing the feature;

determining a view direction based on the feature and configured to highlight the feature; and

displaying a slice of data, with dimensions that highlight the feature, along the view direction in the immediate neighborhood of the picked point.

36. A method according to claim 35, wherein the view direction is different than an original view direction.

37. A method according to claim 35, wherein multiple view directions can be defined for a single feature.

38. A method according to claim 35, wherein the view direction is of a curb edge pick and is a side view showing the silhouette of the curb edge.

39. A method according to claim 35, wherein the view direction of a curb edge pick is a top-down view.

40. A method according to claim 35, wherein the view direction of a highest pick is a side view showing a vertical cylinder of points.

41. A method according to claim 35 further comprising selecting the view direction based on an attribute of the feature.

42. A method according to claim 41, wherein the attribute is one of:

a curvature of the feature, length of the feature, shape of the feature, or size of the feature.