Method for detecting bridges using lidar point cloud data

• US 8,798,372 B1
• Filed: 03/07/2012
• Issued: 08/05/2014
• Est. Priority Date: 03/07/2012
• Status: Active Grant

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Korchev, Dmitriy, Medasani, Swarup, Owechko, Yuri
• Primary Examiner(s): Koziol, Stephen R
• Assistant Examiner(s): GILLIARD, DELOMIA L
• Application Number:
  US13/414,391
• Time in Patent Office: 881 Days
• Field of Search: None
• US Class Current: 382/195
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 20/176 Urban or other man-made structures
• CPC Class Codes: G06V 20/182 Network patterns, e.g. roads or rivers

Abstract

Described is a system and method for detecting elevated structures, such as bridges and overpasses, in point cloud data. A set of data from a three-dimensional point cloud of a landscape is received by the system. The set of data points comprises inlier data points and outlier data points. The inlier data points in the three-dimensional point cloud data are identified and combined into at least one segment. The segment is converted into an image comprising at least one image level. Each image level is processed with an edge detection algorithm to detect elevated edges. The elevated edges are vectorized to identify an elevated structure of interest in the landscape. The present invention is useful in applications that require three-dimensional sensing systems, such as autonomous navigation and surveillance applications.

Claims

1. A system for detecting elevated structures using three-dimensional point cloud data, the system comprising:

one or more processors and a memory having instructions such that when the instructions are executed, the one or more processors perform operations of;

receiving a set of data from a three-dimensional point cloud of a landscape, wherein the set of data points comprises inlier data points and outlier data points;

identifying the inlier data points in the three-dimensional point cloud data;

combining the inlier data points into a plurality of segments, wherein each segment in the plurality of segments represents a planar, horizontal or near-horizontal extent in the three-dimensional cloud data;

filtering the plurality of segments to generate a plurality of filtered segments, the plurality of filtered segments having overlapping parts;

converting each of the filtered segments into an image comprising one or more horizontal image levels, wherein the number of image levels depends on a maximum number of overlapping parts of the filtered segments;

processing each image level with an edge detection algorithm to detect elevated edges in the filtered segments; and

vectorizing the elevated edges to identify a multi-level elevated structure of interest in the landscape wherein, the multi-level elevated structure of interest is selected from the group consisting of bridges, overpasses, and ramps.

2. The system for detecting elevated structures as set forth in claim 1, wherein the system further performs an operation of:

dividing the three-dimensional point cloud into a plurality of small point clouds using a sliding window that shifts along the three-dimensional point cloud to produce a new sliding window position;

wherein each of the small point clouds overlaps with at least one adjacent small point cloud;

wherein the three-dimensional point cloud comprises an x coordinate and a y coordinate, and Ox and Oy represent overlaps between adjacent small point clouds along the x coordinate and the y coordinate, respectively;

wherein each new sliding window position is shifted along the x coordinate by Ox; and

wherein each new sliding window position is shifted along the y coordinate by Oy until the entire three-dimensional point cloud is processed.

3. The system for detecting, elevated structures as set forth in claim 2, wherein the system further performs operations of:

determining a density of data points D in each new sliding window position of a small point cloud;

comparing the density of data points D to a predetermined threshold, such that when the density of data points D exceeds the predetermined threshold, the small point cloud is decimated;

processing the data points in each new sliding window position with a random sample consensus (RANSAC) algorithm to detect at least one plane comprising current inlier data points; and

determining whether an overlap exists between the current inlier data points and the inlier data points of a segment in the plurality of segments, producing overlapping inlier data points.

4. The system for detecting elevated structures as set forth in claim 3, wherein the system further performs an operation of adding the current inlier data points to a segment in the plurality of segments when the number of overlapping inlier data points is greater than a predetermined threshold.

5. The system for detecting elevated structures as set forth in claim 3, wherein the system further performs an operation of creating a new segment from the current inlier data points when the number of overlapping inlier data points is less than a predetermined threshold.

6. The system for detecting elevated structures as set forth in claim 1, wherein the system further performs an operation of filtering a segment in the plurality of segments when the segment is smaller than a predetermined threshold. Or discontinuous, wherein segments that are smaller than the predetermined threshold or discontinuous do not represent elevated structures of interest in the landscape.

7. A computer-implemented method for detecting elevated structures, comprising an act of causing a data processor to execute instructions stored on a memory such that upon execution, the data processor performs operations of:

receiving a set of data from a three-dimensional point cloud of a landscape, wherein the set of data points comprises inlier data points and outlier data points;

identifying the inlier data points in the three-dimensional point cloud data;

combining the inlier data points into a plurality of segments, wherein each segment in the plurality of segments represents a planar, horizontal or near-horizontal extent in the three-dimensional cloud data;

filtering the plurality of segments to generate a plurality of filtered segments, the plurality of filtered segments having overlapping parts;

converting each of the filtered segments into an image comprising one or more horizontal image levels, wherein the number of image levels depends on a maximum number of overlapping parts of the filtered segments;

processing each image level with an edge detection algorithm to detect elevated edges in the filtered segments; and

vectorizing the elevated edges to identify a multi-level elevated structure of interest in the landscape, wherein the multi-level elevated structure of interest is selected from the group consisting of bridges, overpasses, and ramps.

8. The method for detecting elevated structures as set forth in claim 7, further comprising an act of causing a data processor to perform an operation of:

dividing the three-dimensional point cloud into a plurality of small point clouds using a sliding window that shifts along the three-dimensional point cloud to produce a new sliding window position;

wherein each of the small point clouds overlaps with at least one adjacent small point cloud;

wherein the three-dimensional point cloud comprises an x coordinate and a y coordinate, and Ox and Oy represent overlaps between adjacent small point clouds along the x coordinate and the y coordinate, respectively;

wherein each new sliding window position is shifted along the x coordinate by Ox; and

wherein each new sliding window position is shifted along the y coordinate by Oy until the entire three-dimensional point cloud is processed.

9. The method for detecting elevated structures as set forth in claim 8, further comprising an act of causing a data processor to perform operations of:

determining a density of data points D in each new sliding window position of a small point cloud;

comparing the density of data points D to a predetermined threshold, such that when the density of data points D exceeds the predetermined threshold, the small point cloud is decimated;

processing the data points in each new sliding window position with a random sample consensus (RANSAC) algorithm to detect at least one plane comprising current inlier data points; and

determining whether an overlap exists between the current inlier data points and the inlier data points of a segment in the plurality of segments, producing overlapping inlier data points.

10. The method for detecting elevated structures as set forth in claim 9, further comprising an act of causing a data processor to perform an operation of adding the current inlier data points to a segment in the plurality of segments when the number of overlapping inlier data points is greater than a predetermined threshold.

11. The method for detecting elevated structures as set forth in claim 9, further comprising an act of causing a data processor to perform an operation of creating a new segment from the current inlier data points when the number of overlapping inlier data points is less than a predetermined threshold.

12. The method for detecting elevated structures as set forth in claim 7, further comprising an act of causing a data processor to perform an operation of filtering a segment in the plurality of segments when the segment is smaller than a predetermined threshold or discontinuous, wherein segments that are smaller than the predetermined threshold or discontinuous do not represent elevated structures of interest in the landscape.

13. A computer program product for detecting elevated structures, the computer program product comprising:

computer-readable instruction means stored on a non-transitory computer-readable medium that are executable by a computer having a processor for causing the processor to perform operations of;

receiving a set of data from a three-dimensional point cloud of a landscape, wherein the set of data points comprises inlier data points and outlier data points;

identifying the inlier data points in the three-dimensional point cloud data;

combining the inlier data points into a plurality of segments, wherein each segment in the plurality of segments represents a planar, horizontal or near-horizontal extent in the three-dimensional cloud data;

filtering the plurality of segments to generate a plurality of filtered segments, the plurality of filtered segments having overlapping parts;

converting each of the filtered segments into an image comprising one or more horizontal image levels, wherein the number of image levels depends on a maximum number of overlapping pans of the filtered segments;

processing each image level with an edge detection algorithm to detect elevated edges in the filtered segments; and

vectorizing the elevated edges to identify a multi-level elevated structure of interest in the landscape, wherein the multi-level elevated structure of interest is selected from the group consisting of bridges, overpasses, and ramps.

14. The computer program product for detecting elevated structures as set in claim 13, further comprising instruction means for causing a processor to perform an operation of:

dividing the three-dimensional point cloud into a plurality of small point clouds using a sliding window that shifts along the three-dimensional point cloud to produce a new sliding window position;

wherein each of the small point clouds overlaps with at least one adjacent small point cloud;

wherein the three-dimensional point cloud comprises an x coordinate and a y coordinate, and Ox and Ox represent overlaps between adjacent small point clouds along the x coordinate and the y coordinate, respectively;

wherein each new sliding window position is shifted along the x coordinate by Ox; and

wherein each new sliding window position is shifted along the y coordinate by Oy until the entire three-dimensional point cloud is processed.

15. The computer program product for detecting elevated structures as set forth in claim 14, further comprising instruction means for causing a processor to perform operations of:

determining a density of data points D in each new sliding window position of a small point cloud;

comparing the density of data points D to a predetermined threshold, such that when the density of data points D exceeds the predetermined threshold, the small point cloud is decimated;

processing the data points in each new sliding window position with a random sample consensus (RANSAC) algorithm to detect at least one plane comprising current inlier data points; and

determining whether an overlap exists between the current inner data points and the inlier data points of a segment in the plurality of segments, producing overlapping inner data points.

16. The computer program product for detecting elevated structures as set forth in claim 15, further comprising instruction means for causing a processor to perform an operation of adding the current inlier data points to a segment in the plurality of segments when the number of overlapping inlier data points is greater than a predetermined threshold.

17. The computer program product for detecting elevated, structures as set forth in claim 15, further comprising instruction means for causing a processor to perform an operation of creating a new segment from the current inlier data points when the number of overlapping inlier data points is less than a predetermined threshold.

18. The computer program product for detecting elevated structures as set forth in claim 13, filtering a segment in the plurality of segments when the segment is smaller than a predetermined threshold or discontinuous, wherein segments that are smaller than the predetermined threshold or discontinuous do not represent elevated structures of interest in the landscape.