Autonomous vehicle localization based on walsh kernel projection technique

• US 10,380,890 B2
• Filed: 02/08/2017
• Issued: 08/13/2019
• Est. Priority Date: 02/08/2017
• Status: Active Grant

• Current Assignee: Baidu USA LLC (Baidu Incorporated)
• Original Assignee: Baidu USA LLC (Baidu Incorporated)
• Inventors: Wang, Quan
• Primary Examiner(s): Sample, Jonathan L
• Application Number:
  US15/427,973
• Publication Number:
  US 20180225968A1
• Time in Patent Office: 916 Days
• Field of Search: 701400-541, 701 23- 28
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01S 17/06 Systems determining position data of a target
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 19/45 by combining measurements of signals from the satellite radio beacon positioning system with a supplementary measurement
• CPC Class Codes: G01S 5/16 using electromagnetic waves other than radio waves
• CPC Class Codes: G01S 7/4808 Evaluating distance, position or velocity data
• CPC Class Codes: G08G 1/13 the indicator being in the form of a map

Abstract

Location of an autonomous driving vehicle (ADV) is determined with respect to a high definition map. On-boards sensors of the ADV obtain a 3D point cloud of objects surrounding the ADV. The 3D point cloud is organized into an ADV feature space of cells. Each cell has a median intensity value and a variance in elevation. A set of candidate cells that surround the ADV is determined. For each candidate, a set of cells of the ADV feature space that surround the candidate cell is projected onto the map feature space using kernel projection, for one or more dimensions. Kernels can be Walsh-Hadamard vectors. Candidates having insufficient similarity are rejected. When a threshold number of non-rejected candidates remain, candidate similarity can be determined using a similarity metric. The coordinates of the most similar candidate cell are used to determine the position of the vehicle with respect to the map.

Claims

1. A computer-implemented method of determining a location of an autonomous driving vehicle (ADV) with respect to a high definition (HD) map and navigating the ADV, the method comprising:

determining a first sub-set of a plurality of candidate cells of an ADV feature space of cells surrounding the ADV, the ADV feature space derived from a three-dimensional (3D) point cloud of sensor data obtained by sensors of the ADV;

for each candidate cell in the first sub-set of the plurality of candidate cells;

determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell and an HD map feature space, by projecting the subset of the ADV feature space onto the map feature space using a first dimension projection kernel;

in response to determining that the similarity score is less than a threshold amount, marking the candidate cell as rejected, otherwise storing the similarity score in association with the candidate cell;

determining a location of the ADV with respect to the HD map feature space based at least in part on a candidate cell in the plurality of candidate cells having a highest similarity score among the plurality of candidate cells; and

navigating the ADV along a planned route, the navigating based at least in part on the determined location of the ADV with respect to the HD map.

2. The method of claim 1, wherein determining the location of the ADV with respect to the map feature space comprises:

determining the coordinates of the candidate cell having the highest similarity score among the plurality of candidate cells that are not rejected.

3. The method of claim 1, wherein the first sub-set of the plurality of candidate cells comprises all of the plurality of candidate cells.

4. The method of claim 1, further comprising:

in response to the candidate cell not being marked as rejected, determining a second similarity score between the candidate cell and the map feature space by projecting the subset of the ADV feature space onto the map feature space using a second dimension projection kernel, wherein the first dimension projection kernel captures a larger portion of the similarity of the ADV feature space surrounding the candidate cell to the HD map feature space than the second dimension projection kernel captures; and

determining an updated similarity score by using the stored similarity score for the candidate cell and the second similarity score; and

in response to determining that the updated similarity score is less than the threshold amount, marking the candidate cell as rejected, otherwise storing the updated similarity score in association with the candidate cell.

5. The method of claim 4, wherein the first and second dimension projection kernels comprise an ordered sequence of Gray-Code kernels.

6. The method claim 1, further comprising:

determining a second sub-set of the plurality of candidate cells comprising, each candidate cell in the second subset of the plurality of candidate cells not having been rejected and not having had a similarity score stored in association with the candidate cell, and each candidate cell in the second sub-set having a median intensity and a variance in elevation;

for each candidate cell in the second sub-set;

determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and the map feature space, using the median intensity and variance in elevation.

7. The method of claim 6, wherein determining the second sub-set is performed in response to one of:

determining that a count of candidate cells in the plurality of candidate cells, each candidate cell in the count not having been rejected and not having had a similarity score stored in association with the candidate cell, is less than a threshold number of candidate cells;

or

determining that a maximum number of dimensions of projection kernels has been reached.

8. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for determining a location of an autonomous driving vehicle (ADV) with respect to a high definition (HD) map, the operations comprising:

determining a first sub-set of a plurality of candidate cells of an ADV feature space of cells surrounding the ADV, the ADV feature space derived from a three-dimensional (3D) point cloud of sensor data obtained by sensors of the ADV;

for each candidate cell in the first sub-set of the plurality of candidate cells;

determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and an HD map feature space, by projecting the subset of the ADV feature space onto the map feature space using a first dimension projection kernel; and

in response to determining that the similarity score is less than a threshold amount, marking the candidate cell as rejected, otherwise storing the similarity score in association with the candidate cell;

determining a location of the ADV with respect to the HD map feature space based at least in part on a candidate cell in the plurality of candidate cells having a highest similarity score among the plurality of candidate cells; and

navigating the ADV along a planned route, the navigating based at least in part on the determined location of the ADV with respect to the HD map.

9. The medium of claim 8, wherein determining the location of the ADV with respect to the map feature space comprises:

determining the coordinates of the candidate cell having the highest similarity score among the plurality of candidate cells that are not rejected.

10. The medium of claim 8, wherein the first sub-set of the plurality of candidate cells comprises all of the plurality of candidate cells.

11. The medium of claim 8, further comprising:

in response to the candidate cell not being marked as rejected, determining a second similarity score between the candidate cell and the map feature space by projecting the subset of the ADV feature space onto the map feature space using a second dimension projection kernel, wherein the first dimension projection kernel captures a larger portion of the similarity of the ADV feature space surrounding the candidate cell to the HD map feature space than the second dimension projection kernel captures; and

determining an updated similarity score by using the stored similarity score for the candidate cell and the second similarity score; and

in response to determining that the updated similarity score is less than the threshold amount, marking the candidate cell as rejected, otherwise storing the updated similarity score in association with the candidate cell.

12. The medium of claim 11, wherein the first and second dimension projection kernels comprise an ordered sequence of Gray-Code kernels.

13. The medium claim 8, the operations further comprising:

determining a second sub-set of the plurality of candidate cells comprising, each candidate cell in the second subset of the plurality of candidate cells not having been rejected and not having had a similarity score stored in association with the candidate cell, and each candidate cell in the second sub-set having a median intensity and a variance in elevation;

for each candidate cell in the second sub-set;

determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and the map feature space, using the median intensity and variance in elevation.

14. The medium of claim 13, wherein determining the second sub-set is performed in response to one of:

determining that a count of candidate cells in the plurality of candidate cells, each candidate cell in the count not having been rejected and not having had a similarity score stored in association with the candidate cell, is less than a threshold number of candidate cells;

or

determining that a maximum number of dimensions of projection kernels has been reached.

15. A data processing system, comprising:

a processor; and

a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations for determining a location of an autonomous driving vehicle (ADV) with respect to a high definition (HD) map and navigating the ADV, the operations including;

determining a first sub-set of a plurality of candidate cells of an ADV feature space of cells surrounding the ADV, the ADV feature space derived from a three-dimensional (3D) point cloud of sensor data obtained by sensors of the ADV;

for each candidate cell in the first sub-set of the plurality of candidate cells;

determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and an HD map feature space, by projecting the subset of the ADV feature space onto the map feature space using a first dimension projection kernel; and

in response to determining that the similarity score is less than a threshold amount, marking the candidate cell as rejected, otherwise storing the similarity score in association with the candidate cell;

determining a location of the ADV with respect to the HD map feature space based at least in part on a candidate cell in the plurality of candidate cells having a highest similarity score among the plurality of candidate cells; and

navigating the ADV along a planned route, the navigating based at least in part on the determined location of the ADV with respect to the HD map.

16. The system of claim 15, wherein determining the location of the ADV with respect to the map feature space comprises:

determining the coordinates of the candidate cell having the highest similarity score among the plurality of candidate cells that are not rejected.

17. The system of claim 15, wherein the first sub-set of the plurality of candidate cells comprises all of the plurality of candidate cells.

18. The system of claim 15, further comprising:

in response to the candidate cell not being marked as rejected, determining a second similarity score between the candidate cell and the map feature space by projecting the subset of the ADV feature space onto the map feature space using a second dimension projection kernel, wherein the first dimension projection kernel captures a larger portion of the similarity of the ADV feature space surrounding the candidate cell to the HD map feature space than the second dimension projection kernel captures; and

determining an updated similarity score by using the stored similarity score for the candidate cell and the second similarity score; and

in response to determining that the updated similarity score is less than the threshold amount, marking the candidate cell as rejected, otherwise storing the updated similarity score in association with the candidate cell.

19. The system of claim 18, wherein the first and second dimension projection kernels comprise an ordered sequence of Gray-Code kernels.

20. The system claim 15, the operations further comprising:

determining a second sub-set of the plurality of candidate cells comprising, each candidate cell in the second subset of the plurality of candidate cells not having been rejected and not having had a similarity score stored in association with the candidate cell, and each candidate cell in the second sub-set having a median intensity and a variance in elevation;

for each candidate cell in the second sub-set;

determining a similarity score between a subset of the ADV feature space that surrounds the candidate cell, and the map feature space, using the median intensity and variance in elevation.

21. The system of claim 20, wherein determining the second sub-set is performed in response to one of:

determining that a count of candidate cells in the plurality of candidate cells, each candidate cell in the count not having been rejected and not having had a similarity score stored in association with the candidate cell, is less than a threshold number of candidate cells;

or

determining that a maximum number of dimensions of projection kernels has been reached.