Method and system for map construction

Patent metadata

Field	Value
Publication number	US-11227421-B2
Application number	US-202017032490-A
Country	US
Kind code	B2
Filing date	Sep 25, 2020
Priority date	Feb 26, 2019
Publication date	Jan 18, 2022
Grant date	Jan 18, 2022

Abstract

A method of constructing a map including a plurality of lanes and a system thereof are provided. The method includes: for each of the plurality of lanes, constructing corresponding lane geometry data based on a plurality of polyline segments, including constructing a general outline circumscribing the plurality of lanes and identifying an outline of each of the plurality of lanes based on the plurality of polyline segments and the general outline. Outline polyline segments as boundaries of the general outline are selected from the plurality of polyline segments.

First claim

What is claimed is:

1. A method of constructing a map comprising a plurality of lanes, the method comprising:
constructing, for each of the plurality of lanes, corresponding lane geometry data based on a plurality of polyline segments,
wherein the constructing the corresponding lane geometry data includes:
constructing a general outline circumscribing the plurality of lanes; and
identifying an outline of each of the plurality of lanes based on the plurality of polyline segments and the general outline; and

wherein the constructing the general outline includes:
selecting outline polyline segments as boundaries of the general outline from the plurality of polyline segments; and
merging at least two joined polyline segments into a single polyline segment in response to determining that each of the at least two joined polyline segments merge at only one respective end.

2. The method according to claim 1 , further comprising:
receiving a plurality of polylines; and
converting the plurality of polylines into the plurality of polyline segments, the plurality of polyline segments being constructed on a start point, an end point or a turning point of each of the plurality of polylines.

3. The method according to claim 1 , wherein the general outline forms a closed space circumscribing the plurality of lanes.

4. The method according to claim 3 , wherein constructing the general outline circumscribing the plurality of lanes comprises:
removing at least one invalid polyline segment from the plurality of polyline segments, wherein one end point of the at least one invalid polyline segment is not connected to any other one of the polyline segments.

5. The method according to claim 1 , wherein selecting the outline polyline segments as boundaries of the general outline from the plurality of polyline segments comprises:
selecting a first polyline segment from the plurality of polyline segments as an incident polyline segment, the incident polyline segment being comprised in the general outline and having a first end and a second end opposite to the first end, the general outline comprising indices of the first polyline segment and the first end and the second end of the first polyline segment;
identifying a plurality of candidate polyline segments joined to the second end of the incident polyline segment at respective first ends;
selecting a target polyline segment from the plurality of candidate polyline segments and comprising the target polyline segment into the general outline; and
updating the incident polyline segment with the target polyline segment and updating the general outline by adding indices of the target polyline segment and the first end and the second end of the target polyline segment.

6. The method according to claim 5 , wherein the first polyline segment is selected as that having a smallest coordinate among the plurality of polyline segments.

7. The method according to claim 5 , wherein selecting the target polyline segment comprises:
comparing representative included angles between each of the candidate polyline segments and the incident polyline segment, wherein each of the representative included angles are calculated counterclockwise from the incident polyline segment, and
selecting the target polyline segment that has a maximal included angle.

8. The method according to claim 1 , wherein the lane geometry data is generated according to the outline of each of the plurality of lanes.

9. The method according to claim 1 , further comprising:
generating a lane content for a respective lane based on the lane geometry data.

10. The method according to claim 9 , wherein generating the lane content for the respective lane based on the lane geometry data comprises:
smoothing the plurality of polyline segments as sides of lane segments;
generating a plurality of waypoints for each of the plurality of lanes; and
associating a traffic tag with at least one of lane segments of the plurality of lanes.

11. The method according to claim 9 , further comprising:
retrieving the lane content to extract a map feature.

12. A system for constructing a map comprising a plurality of lanes, the system comprising:
a storage device, arranged to store a programming code; and
a processor, wherein when the programming code is executed by the processor, the processor is configured to perform the following steps:
construct, for each of the plurality of lanes, corresponding lane geometry data based on a plurality of polyline segments, wherein the construct the corresponding lane geometry data includes:
construct a general outline that circumscribes the plurality of lanes; and
identify an outline of each of the plurality of lanes based on the plurality of polyline segments and the general outline;
wherein the construct the general outline includes:
select outline polyline segments as boundaries of the general outline from the plurality of polyline segments;

wherein the lane geometry data of each of the plurality of lanes comprises a first boundary data formed of a first plurality of connected data points in the polyline segments and a second boundary data formed of a second plurality of connected data points in the polyline segments; and

generate a lane content for a respective lane based on the lane geometry data, the lane content is generated by the processor configured to:
generate a plurality of waypoints for each of the plurality of lanes in a space defined by the first boundary data and the second boundary data.

13. The system according to claim 12 , wherein the plurality of waypoints comprises a first waypoint and a second waypoint, and wherein the processor is configured to generate the plurality of waypoints for each of the plurality of lanes by being configured to:
identify a first data point and a first consecutive data point from the first boundary data and a second data point and a second consecutive data point from the second boundary data;
set the first data point and the second data point as an initial data pair and setting a midpoint of the initial data pair as the first waypoint;
calculate a first length of a first data pair between the first data point and the second consecutive data point;
calculate a second length of a second data pair between the second data point and the first consecutive data point; and
select a data pair from one of the first data pair and the second data pair that has a smaller length and setting a midpoint of the selected data pair as the second waypoint.

14. The system according to claim 12 , wherein the processor is configured to generate the lane content for the respective lane by being configured to replace the plurality of waypoints with a plurality of smoothed waypoints by the processor configured to perform up-sampling and data smoothing for the plurality of waypoints.

15. The system according to claim 12 , wherein the generate the lane content for the respective lane further comprises associate a traffic tag with at least one of lane segments of the plurality of lanes.

16. The system according to claim 12 , wherein the processor is further configured to:
generate a lane content for the respective lane based on the lane geometry data; and
partition the map into a grid of slots and generating, for each of the slots, a list of lanes intersecting with the slot based on the lane content.

17. A system for constructing a map comprising a plurality of lanes, the system comprising:
a storage device, arranged to store a programming code; and
a processor, wherein when the programming code is exec

Assignees

• Tusimple Inc

Inventors

• Jiang Minhao
• Lu Hsin
• Shi Genmao
• Liu Ziqi

Classifications

• G06T11/26

  Drawing of charts or graphs · CPC title

• G06T11/23 Primary

  using straight lines or curves · CPC title

• G01C21/3819

  Road shape data, e.g. outline of a route · CPC title

• G06T7/60

  Analysis of geometric attributes · CPC title

• G01C21/26

  specially adapted for navigation in a road network · CPC title