Systems and methods for detecting and modeling curb curves in complex urban scenes

Patent metadata

Field	Value
Publication number	US-9870437-B2
Application number	US-201414551502-A
Country	US
Kind code	B2
Filing date	Nov 24, 2014
Priority date	Nov 24, 2014
Publication date	Jan 16, 2018
Grant date	Jan 16, 2018

Abstract

Computer-implemented methods and systems of detecting and modeling curbs include receiving a cloud of three-dimensional (3D) data points acquired along street locations. A plurality of vertical scanlines (e.g., arrays of 3D data points obtained at given horizontal locations) are identified within the cloud of 3D data points. One or more curb points indicating the potential presence of a curb in the plurality of vertical scanlines are identified. A synthesized set of non-overlapping curb curves are generated in order to close gaps between certain curb points while removing certain other outlier curb points. Successive curb curves in the synthesized set of non-overlapping curb curves are then identified as belonging to one or more curb segments. A curb model that fits each of the one or more curb segments to one or more curb model shape representations can then be generated.

First claim

What is claimed is:

1. A computer-implemented method of detecting and modeling curbs, comprising:
receiving, by one or more computing devices, a cloud of three-dimensional data points acquired along one or more street locations;
identifying, by the one or more computing devices, a plurality of vertical scanlines within the cloud of 3D data points, each vertical scanline comprising an array of three-dimensional data points obtained at a given horizontal location along the one or more street locations;
identifying, by the one or more computing devices, one or more curb points in the plurality of vertical scanlines, wherein the one or more curb points are indicative of the potential presence of a curb along the one or more street locations, and wherein identifying one or more curb points in at least one of the plurality of vertical scanlines comprises:
determining, by the one or more computing devices, at least one of a slope and a height difference for each of one or more data points included in the vertical scanline based at least in part on a vector describing a spatial difference between such data point and a next sequential data point; and
identifying, by the one or more computing devices, the one or more curb points by identifying changes in the slope or height difference of the one or more data points included in the vertical scanline;

generating, by the one or more computing devices, a synthesized set of non-overlapping curb curves based at least in part on the one or more curb points identified in nearby vertical scanlines to close gaps between one or more of the curb points;
identifying, by the one or more computing devices, successive curb curves in the synthesized set of non-overlapping curb curves as belonging to one or more curb segments; and
generating, by the one or more computing devices, a curb model that fits each of the one or more curb segments to one or more curb model shape representations.

2. The method of claim 1 , further comprising:
generating, by the one or more computing devices, a three-dimensional model of the one or more street locations based at least in part on the generated curb model; and
responsive to a request, providing for display, by the one or more computing devices, a three-dimensional representation of the street locations generated based at least in part on the three-dimensional model.

3. The method of claim 1 , wherein the cloud of three-dimensional data points is gathered via one or more of a laser scanner and a camera provided at a mobile data acquisition unit traversing the one or more street locations.

4. The method of claim 1 , wherein identifying, by the one or more computing devices, one or more curb points in the plurality of vertical scan lines comprises:
determining, by the one or more computing devices, the slope of three-dimensional data points;
characterizing the three-dimensional data points as one of a predetermined set of classification types based at least in part on the determined slope, wherein the predetermined set of classification types for the three-dimensional data points includes at least horizontal points and vertical points; and
identifying a transition within each vertical scanline from a horizontal point to a vertical point followed by a sequence of vertical points having a vertical distance that is less than a predetermined maximum height for a curb.

5. The method of claim 1 , wherein identifying, by the one or more computing devices, one or more curb points in the plurality of vertical scanlines comprises identifying a spike in the height difference among data points in each vertical scanline, wherein the height difference is calculated as the difference between vertical distance measurements obtained at successive scan points in each vertical scanline.

6. The method of claim 1 , wherein identifying, by the one or more computing devices, one or more curb points within the plurality of vertical scanlines comprises using an optimal sequential cumulative sum algorithm to identify spikes in the height difference among data points in each vertical scanline, wherein the height difference is calculated as the difference between vertical distance measurements obtained at successive scan points in each vertical scanline.

7. The method of claim 1 , wherein generating, by the one or more computing devices, a synthesized set of non-overlapping curb curves comprises connecting a first curb point in a given vertical scanline to a second curb point in another nearby vertical scanline that is within a predetermined distance of the first curb point.

8. The method of claim 1 , wherein identifying, by the one or more computing devices, successive curb curves in the synthesized set of non-overlapping curb curves as belonging to one or more curb segments comprises calculating the distance between endpoints of successive curb curves in the synthesized set of non-overlapping curb curves and comparing the calculated distance between endpoints to a predetermined curb connection parameter.

9. The method of claim 1 , wherein identifying, by the one or more computing devices, successive curb curves in the synthesized set of non-overlapping curb curves as belonging to one or more curb segments comprises:
generating a connecting curve that closes a gap between successive curb curves;
calculating a number of vertical obstacles detected in front of the connecting curve and a number of vertical obstacles detected behind the connecting curve; and
determining whether the successive curb curves should be connected as part of the same curb segment based at least in part on the number of vertical obstacles detected in front of the connecting curve and the number of vertical obstacles detected behind the connecting curve.

10. The method of claim 1 , wherein the one or more curb model shape representations comprises one or more of a three-dimensional linear model, a three-dimensional circular model, and a three-dimensional B-spline model.

11. The method of claim 1 , wherein generating, by the one or more computing devices, a curb model that fits each of the one or more curb segments to one or more curb model shape representations comprises implementing an intersection algorithm between adjacent curb curves within the same curb segment.

12. The method of claim 1 , further comprising, using, by the one or more computing devices, the generated curb model to classify a ground object within the cloud of three-dimensional data points.

13. A computing system, comprising:
one or more processors; and
one or more memory devices, the one or more memory devices storing computer-readable instructions that when executed by the one or more processors, cause the one or more processors to perform operations, the operations comprising:
receiving a cloud of three-dimensional data points acquired along one or more street locations;
identifying a plurality of vertical scanlines within the cloud of three-dimensional data points, each vertical scanline comprising an array of three-dimensional data points obtained at a given horizontal location along the one or more street locations;
identifying one or more curb points in the plurality of vertical scanlines, wherein the one or more curb points are indicative of the potential presence of a curb along the one or more street locations, and wherein identifying one or more curb points in at least one of the plurality of vertical scanlines comprises:
determining at least one of a slope and a height difference for each of one or more data points included in the vertical scanline based at least in part on a vector describing a spatial difference between such data point and a next sequential

Assignees

• Google Inc
• Google Llc

Inventors

• Pope Arthur Robert
• Stamos Ioannis

Classifications

• G06T17/05 Primary

  Geographic models · CPC title

• G06T2210/56

  Particle system, point based geometry or rendering · CPC title

• G06F30/13 Primary

  Architectural design, e.g. computer-aided architectural design [CAAD] related to design of buildings, bridges, landscapes, production plants or roads · CPC title

• G06F17/5004 Primary

  Physics · mapped topic