Semi-automatic polyline extraction from point cloud

• US 9,406,138 B1
• Filed: 09/17/2013
• Issued: 08/02/2016
• Est. Priority Date: 09/17/2013
• Status: Active Grant

• Current Assignee: Bentley Systems Incorporated
• Original Assignee: Bentley Systems Incorporated
• Inventors: St-Pierre, Mathieu
• Primary Examiner(s): Hajnik, Daniel
• Application Number:
  US14/029,576
• Time in Patent Office: 1,050 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06T 2207/20096 Interactive definition of curve of interest
• CPC Class Codes: G06T 2207/30236 Traffic on road, railway or crossing
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/181 involving edge growing; involving edge linking

Abstract

In one embodiment, a technique is provided for semi-automatically extracting a polyline from a linear feature in a point cloud. The user may provide initial parameters, including a point about the linear feature and a starting direction. A linear feature extraction process may automatically follow the linear feature beginning in the starting direction from about the selected point. The linear feature extraction process may attempt to follow a linear segment of the linear feature. If some points may be followed that constitute a linear segment, a line segment modeling the linear segment is created. The linear feature extraction process then determines whether the end of the linear feature has been reached. If the end has not been reached, the linear feature extraction process may repeat. If the end has been reached, the linear feature extraction process may return the line segments and create a polyline from them.

Claims

1. A method for semi-automatically extracting a polyline from a linear feature in a point cloud, comprising:

receiving, from a user, a selected point in the point cloud about the linear feature in the point cloud;

receiving, from the user, a starting search direction;

returning a plurality of line segments based on the linear feature by a process executing on an electronic device, by;

successively following one or more linear segments of the linear feature, beginning with a current search direction set to the starting search direction and a current search location set about the selected point, and modeling the linear segments with line segments, wherein

when an end of a linear segment is reached, determining whether there is an intersection based on detection of greater than a threshold number of points of the linear feature in multiple directions,

in response to there being an intersection, prompting the user to provide an updated search direction that is used as the current search direction,

in response to there not being an intersection, continuing to successively follow one or more linear segments of the linear feature after the intersection, and modeling the one or more linear segments after the intersection with line segments,

when an end of a linear segment is reached, determining whether there is a jumpable gap,

in response to determining there is a jumpable gap, continuing to successively follow one or more linear segments of the linear feature after the jumpable gap, and modeling the one or more linear segments after the jumpable gap with line segments, and

in response to there not being a jumpable gap, returning the line segments; and

creating a polyline from the returned line segments.

2. The method of claim 1, wherein the following one or more linear segments of the linear feature comprises:

fetching only a limited number of points around the current search location in the point cloud for use in following the one or more linear segments of the linear feature.

3. The method of claim 2, wherein the fetching points further comprises:

creating a query box;

extracting points of the point cloud that fall within the query box;

comparing a number of points extracted to one or more thresholds;

increasing or decreasing a dimension of the query box based on the comparing; and

returning extracted points.

4. The method of claim 1, wherein the following one or more linear segments of the linear feature further comprises:

searching for points around the current search location;

advancing the current search location; and

when a determination is made that point following should stop, returning followed points.

5. The method of claim 4, wherein the following one or more linear segments of the linear feature further comprises:

determining the linear feature has turned; and

updating the current search direction and the current search location based on the turn.

6. The method of claim 1, wherein in response to there being an intersection, further determining there are groups of points having directions that differ by an angle less than a threshold and merging the groups of points having directions that differ by the angle less than the threshold.

7. The method of claim 1, wherein modeling the linear segments with line segments further comprises:

creating a line segment by applying a RAMdom SAmple Consensus (RANSAC) algorithm to points of the linear segment.

8. The method of claim 1, wherein determining there is a jumpable gap further comprises:

searching for a location around which at least a threshold number of points are present within a cone-like search region extending from the current search location;

updating the current search direction based on the location within the cone-like search region; and

continuing to follow one or more linear segments of the linear feature from the location within the cone-like search region.

9. The method of claim 1, wherein the point cloud represents one or more objects in the physical environment.

10. An apparatus to semi-automatically extract a polyline from a linear feature in a point cloud, comprising:

a display screen configured to display a user interface;

a processor; and

a memory coupled to the processor and configured to store instructions for a line extraction software process that when executed by the processor is operable to;

successively follow one or more linear segments of the linear feature in the point cloud, beginning with a current search location set about a selected point and a current search direction set to a starting search direction that are provided by a user in the user interface and model the linear segments with line segments, wherein

when an end of a linear segment is reached, determine whether there is an intersection based on detection of greater than a threshold number of points of the linear feature in multiple directions,

in response to there being an intersection, prompt the user to provide an updated search direction that is used as the current search direction,

in response to there not being an intersection, continue to successively follow one or more linear segments of the linear feature after the intersection, and model the one or more linear segments after the intersection with line segments,

when an end of a linear segment is reached, determine whether there is a jumpable gap,

in response to determining there is a jumpable gap, continue to successively follow one or more linear segments of the linear feature after the jumpable gap, and model the linear segments after the jumpable gap with line segments,

in response to there not being a jumpable gap, return the line segments; and

create a polyline from the returned line segments.

11. The apparatus of claim 10, wherein the line extraction software process when executed by the processor is further operable to:

fetch only a limited number of points around the current location in the point cloud for use in following the one or more linear segments of the linear feature.

12. The apparatus of claim 11, wherein the line extraction software process when executed by the processor is further operable to:

create a query box;

extract points of the point cloud that fall within the query box;

compare a number of points extracted to one or more thresholds;

increase or decrease a dimension of the query box based on the comparing; and

return extracted points.

13. The apparatus of claim 10, wherein the line extraction software process when executed by the processor is further operable to:

search for points around the current search location;

advance the current search location; and

when a determination is made that point following should stop, return followed points.

14. The apparatus of claim 13, wherein the line extraction software process when executed by the processor is further operable to:

determine the linear feature has turned; and

update the current search direction and the current search location based on the turn.

15. The apparatus of claim 10, wherein the line extraction software process when executed by the processor is further operable to:

in response to there being an intersection, further determine there are groups of points having directions that differ by an angle less than a threshold and merge the groups of points having directions that differ by the angle less than the threshold.

16. The apparatus of claim 10, wherein the line extraction software process when executed by the processor is further operable to:

create a line segment by applying a RANdom SAmple Consensus (RANSAC) algorithm to points of a linear segment.

17. The apparatus of claim 10, wherein the line extraction software process when executed by the processor is further operable to:

search for a location around which at least a threshold number of points are present within a cone-like search region extending from the current search location;

update the current search direction based on the location within the cone-like search region; and

continue to follow one or more linear segments of the linear feature from the location within the cone-like search region.

18. A non-transitory computer-readable medium that includes instructions executable on a processor, the instructions, when executed, operable to:

receive a user-provided selected point in a point cloud about a linear feature in a point cloud;

receive a user-provided starting search direction;

follow the linear feature beginning with a current search direction set to be the starting search direction and a current search location set to be about the selected point, by successively;

searching for points associated with the linear feature in a plurality of search spheres disposed about the current search location,

determining whether there is greater than a threshold number of points of the linear feature in multiple search spheres of the plurality of search spheres,

when there is not greater than the threshold number of points of the linear feature in multiple search spheres, extending the linear feature by detecting one or more points that define a linear segment, modeling the linear segment with a line segment, advancing the current search location, and updating the current search direction, and

when there is greater than the threshold number of points of the linear feature in multiple search spheres, determining an intersection is reached;

in response to there being an intersection, prompt a user to provide an updated search direction, and continue to follow the linear feature with the current search direction set to the updated search direction; and

create a polyline from any line segments.

19. The non-transitory computer-readable medium of claim 18, wherein the threshold number of points is based on a percentage of a maximum number of points found in any search sphere.

20. The non-transitory computer-readable medium of claim 18, wherein the instructions to determine an intersection is reached, when executed, are further operable to:

when there is greater than the threshold number of points of the linear feature in multiple search spheres, attempting to follow the linear feature in the multiple search directions for a number of searches;

determine whether the linear feature in two or more of the multiple search directions differs by an angle less than a threshold angle;

when the linear feature in the two or more search directions differs by an angle less than the threshold angle, merging the linear feature in the two or more search directions into a linear feature in one direction; and

when there is still a linear feature in multiple search directions after merging, determine the intersection is reached.

21. The non-transitory computer-readable medium of claim 18, wherein the instructions, when executed, are further operable to:

when an end of a linear segment is reached, determine whether there is a jumpable gap;

in response to determining there is a jumpable gap, continuing extending the linear feature by successively detecting one or more points that define a new linear segment, modeling the new linear segment with a line segment, advancing the current search location, and updating the current search direction; and

in response to there not being a jumpable gap, returning any line segments for creating the polyline.