Determination of object heading based on point cloud

• US 9,014,903 B1
• Filed: 05/22/2012
• Issued: 04/21/2015
• Est. Priority Date: 05/22/2012
• Status: Active Grant

• Current Assignee: Waymo LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhu, Jiajun, Dolgov, Dmitri A., Fairfield, Nathaniel
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): NGUYEN, ROBERT T
• Application Number:
  US13/477,871
• Time in Patent Office: 1,064 Days
• Field of Search: 701/1, 701/2, 701/23, 701/27, 701/28, 701/200, 701/223, 701/300, 701/301, 701/400, 701/423, 701/514, 701/519, 382/100, 382/103, 382/104, 382/106, 382/107, 345/418, 345/419, 356/3, 356/508, 356/614
• US Class Current: 701/28
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01S 13/865 Combination of radar systems with lidar systems
• CPC Class Codes: G01S 13/867 Combination of radar systems with cameras
• CPC Class Codes: G01S 13/931 of land vehicles
• CPC Class Codes: G01S 17/875 for determining attitude
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 17/931 of land vehicles
• CPC Class Codes: G01S 2013/9318 Controlling the steering
• CPC Class Codes: G01S 2013/93185 Controlling the brakes
• CPC Class Codes: G01S 2013/9321 Velocity regulation, e.g. cruise control
• CPC Class Codes: G05D 1/0238 using obstacle or wall sensors G05D1/0246 and G05D1/0289 take precedence; lidar systems designed for anti-collision purposes G01S17/93

Abstract

An autonomous vehicle configured to determine the heading of an object-of-interest based on a point cloud. An example computer-implemented method involves: (a) receiving spatial-point data indicating a set of spatial points, each spatial point representing a point in three dimensions, where the set of spatial points corresponds to an object-of-interest; (b) determining, for each spatial point, an associated projected point, each projected point representing a point in two dimensions; (c) determining a set of line segments based on the determined projected points, where each respective line segment connects at least two determined projected points; (d) determining an orientation of at least one determined line segment from the set of line segments; and (e) determining a heading of the object-of-interest based on at least the determined orientation.

Claims

1. A computer-implemented method comprising:

receiving, by a computer system from a LIDAR unit, spatial-point data indicating a set of spatial points, each spatial point representing a point in three dimensions, wherein the set of spatial points corresponds to an object-of-interest;

determining, for each spatial point, an associated projected point, each projected point representing a point in two dimensions;

determining a set of line segments based on the determined projected points, wherein each respective line segment connects at least two determined projected points;

determining an orientation of at least one determined line segment from the set of line segments;

determining a heading of the object-of-interest based on at least the determined orientation; and

controlling a vehicle, by the computer system, based on the determined heading of the object-of-interest.

2. The method of claim 1, wherein each spatial point is associated with (i) a respective laser from a set of lasers and (ii) a respective timestamp.

3. The method of claim 1, wherein each projected point representing a point in two dimensions represents a point in a ground plane.

4. The method of claim 3, further comprising:

before determining, for each spatial point, an associated projected point, sorting the set of spatial points based on at least (i) the respective laser and (ii) the respective timestamp associated with each spatial point.

5. The method of claim 3, wherein the set of spatial points comprises at least two subsets of spatial points, wherein (i) no two subsets of spatial points comprise spatial points associated with the same respective laser and (ii) the spatial points within each subset of spatial points are associated with the same respective laser, and wherein determining the set of line segments comprises:

for each given subset of spatial points, determining a respective two-dimensional curve based on projected points associated with the spatial points within the given subset of spatial points; and

determining a subset of line segments based on each respective two-dimensional curve.

6. The method of claim 5, wherein determining the set of line segments further comprises:

before determining the subset of line segments, determining an approximated-two-dimensional curve for each respective two-dimensional curve, wherein the approximated-two-dimensional curve contains fewer spatial points than the respective two-dimensional curve.

7. The method of claim 1, wherein determining the orientation of at least one line segment comprises determining the orientation of at least one line segment relative to a predetermined direction.

8. The method of claim 1, wherein determining the heading of the object-of-interest comprises:

creating a histogram of line segments, wherein the line segments are grouped into histogram intervals based on at least the respective determined orientation of each line segment; and

selecting, as the heading of the object-of-interest, a peak of the histogram.

9. The method of claim 1, wherein the histogram intervals are one-half degree.

10. The method of claim 1, wherein determining the heading of the object-of-interest comprises:

determining a curve, wherein the curve is an approximate fit of the determined orientation of the at least one line segment; and

selecting, as the heading of the object-of-interest, a peak of the curve.

11. A non-transitory computer-readable medium having program instructions stored thereon that are executable by at least one processor, the program instructions comprising:

instructions for receiving, from a LIDAR unit, spatial-point data indicating a set of spatial points, each spatial point representing a point in three dimensions, wherein the set of spatial points corresponds to an object-of-interest;

instructions for determining, for each spatial point, an associated projected point, each projected point representing a point in two dimensions;

instructions for determining a set of line segments based on the determined projected points, wherein each respective line segment connects at least two determined projected points;

instructions for determining an orientation of at least one determined line segment from the set of line segments;

instructions for determining a heading of the object-of-interest based on at least the determined orientation; and

instructions for controlling a vehicle based on the determined heading of the object-of-interest.

12. The non-transitory computer-readable medium of claim 11, wherein each spatial point is associated with (i) a respective laser from a set of lasers and (ii) a respective timestamp.

13. The non-transitory computer-readable medium of claim 11, wherein each projected point representing a point in two dimensions represents a point in a ground plane.

14. The non-transitory computer-readable medium of claim 13, the program instructions further comprising:

instructions for, before determining, for each spatial point, an associated projected point, sorting the set of spatial points based on at least (i) the respective laser and (ii) the respective timestamp associated with each spatial point.

15. The non-transitory computer-readable medium of claim 13, wherein the set of spatial points comprises at least two subsets of spatial points, wherein (i) no two subsets of spatial points comprise spatial points associated with the same respective laser and (ii) the spatial points within each subset of spatial points are associated with the same respective laser, and wherein the instructions for determining the set of line segments comprise:

instructions for, for each given subset of spatial points, determining a respective two-dimensional curve based on projected points associated with the spatial points within the given subset of spatial points; and

instructions for determining a subset of line segments based on each respective two-dimensional curve.

16. The non-transitory computer-readable medium of claim 15, wherein the instructions for determining the set of line segments further comprise:

instructions for, before determining the subset of line segments, determining an approximated-two-dimensional curve for each respective two-dimensional curve, wherein the approximated-two-dimensional curve contains fewer spatial points than the respective two-dimensional curve.

17. The non-transitory computer-readable medium of claim 11, wherein determining the orientation of at least one line segment comprises determining the orientation of at least one line segment relative to a predetermined direction.

18. The non-transitory computer-readable medium of claim 11, wherein the instructions for determining the heading of the object-of-interest comprise:

instructions for creating a histogram of line segments, wherein the line segments are grouped into histogram intervals based on at least the respective determined orientation of each line segment; and

instructions for selecting, as the heading of the object-of-interest, a peak of the histogram.

19. The non-transitory computer-readable medium of claim 11, wherein the histogram intervals are one-half degree.

20. The non-transitory computer-readable medium of claim 11, wherein the instructions for determining the heading of the object-of-interest comprise:

instructions for determining a curve, wherein the curve is an approximate fit of the determined orientation of the at least one line segment; and

instructions for selecting, as the heading of the object-of-interest, a peak of the curve.

21. An autonomous-vehicle system comprising:

one or more sensors;

a computer system configured to;

receive spatial-point data indicating a set of spatial points, each spatial point representing a point in three dimensions, wherein the set of spatial points corresponds to an object-of-interest;

determine, for each spatial point, an associated projected point, each projected point representing a point in two dimensions;

determine a set of line segments based on the determined projected points, wherein each respective line segment connects at least two determined projected points;

determine an orientation of at least one determined line segment from the set of line segments; and

determine a heading of the object-of-interest based on at least the determined orientation.

22. The system of claim 21, wherein each spatial point is associated with (i) a respective laser from a set of lasers and (ii) a respective timestamp.

23. The system of claim 21, wherein each projected point representing a point in two dimensions represents a point in a ground plane.

24. The system of claim 23, wherein the computer system is further configured to:

before determining, for each spatial point, an associated projected point, sort the set of spatial points based on at least (i) the respective laser and (ii) the respective timestamp associated with each spatial point.

25. The system of claim 23, wherein the set of spatial points comprises at least two subsets of spatial points, wherein (i) no two subsets of spatial points comprise spatial points associated with the same respective laser and (ii) the spatial points within each subset of spatial points are associated with the same respective laser, and wherein, to determine the set of line segments, the computer system is configured to:

for each given subset of spatial points, determine a respective two-dimensional curve based on projected points associated with the spatial points within the given subset of spatial points; and

determine a subset of line segments based on each respective two-dimensional curve.

26. The system of claim 25, wherein, to determine the set of line segments, the computer system is configured to:

before determining the subset of line segments, determine an approximated-two-dimensional curve for each respective two-dimensional curve, wherein the approximated-two-dimensional curve contains fewer spatial points than the respective two-dimensional curve.

27. The system of claim 21, wherein determining the orientation of at least one line segment comprises determining the orientation of at least one line segment relative to a predetermined direction.

28. The system of claim 21, wherein, to determine the heading of the object-of-interest, the computer system is configured to:

create a histogram of line segments, wherein the line segments are grouped into histogram intervals based on at least the respective determined orientation of each line segment; and

select, as the heading of the object-of-interest, a peak of the histogram.

29. The system of claim 21, wherein the histogram intervals are one-half degree.

30. The system of claim 21, wherein, to determine the heading of the object-of-interest, the computer system is configured to:

determine a curve, wherein the curve is an approximate fit of the determined orientation of the at least one line segment; and

select, as the heading of the object-of-interest, a peak of the curve.