Method and system for map construction

Patent metadata

Field	Value
Publication number	US-12190609-B2
Application number	US-202318360556-A
Country	US
Kind code	B2
Filing date	Jul 27, 2023
Priority date	Feb 26, 2019
Publication date	Jan 7, 2025
Grant date	Jan 7, 2025

Abstract

A method of retrieving a map includes receiving a grid data of the map comprising lane segments, wherein the grid data includes an array of grids each associated with a list including none or at least one of the lane segments intersecting the respective grid; receiving coordinates of a location; identifying a first grid including the location based on the grid data; identifying a target grid that has an associated list including at least one of the lane segments as first lane segment; and outputting the first lane segment.

First claim

What is claimed is:

1. A method of map construction, comprising:
constructing an outline circumscribing a plurality of lanes on a road based on a plurality of segments that extend along the plurality of lanes or the road; and
identifying an individual outline of each of the plurality of lanes based on the plurality of segments and the outline circumscribing the plurality of lanes,
wherein the plurality of segments is obtained by partitioning polylines describing a shape of the road into segments that are constructed on a start point, an end point, or a turning point of the polylines.

2. The method of claim 1 , wherein each of the plurality of segments is marked using arrows as a bidirectional segment.

3. The method of claim 2 , further comprising:
selecting, from the plurality of segments, a segment having a first end and a second end opposite to the first end;
identifying, from the plurality of segments, a plurality of candidate segments having one end connected to the second end of the segment; and
selecting a candidate segment from the plurality of candidate segments based on a comparison of an angle between the segment and each of the plurality of candidate segments, wherein the candidate segment includes a third end and a fourth end opposite to the third end, wherein the third end of the candidate segment is connected to the second end of the segment.

4. The method of claim 3 ,
wherein a first angle in between the candidate segment and the segment is determined in one direction from the segment to the candidate segment, and
wherein in response to the one direction being a counterclockwise direction, the candidate segment is selected in response to the first angle being greater than a first set of one or more angles determined respectively from the segment to one or more remaining candidate segments in the counterclockwise direction from the segment, and
wherein in response to the one direction being a clockwise direction, the candidate segment is selected in response to the first angle being less than a second set of one or more angles determined respectively from the segment to the one or more remaining candidate segments in the clockwise direction from the segment.

5. The method of claim 3 , further comprising:
removing, from the segment, a first arrow pointing from the first end to the second end of the segment in response to the selecting the candidate segment, wherein the segment includes a second arrow pointing from the second end to the first end of the segment.

6. The method of claim 2 , further comprising:
selecting, from the plurality of segments, a segment having a first end and a second end opposite to the first end;
identifying, from the plurality of segments, a plurality of candidate segments having one end connected to the second end of the segment;
selecting a second candidate segment from the plurality of candidate segments based on another comparison of an angle between the segment and each of the plurality of candidate segments, wherein the second candidate segment includes a fifth end and a sixth end opposite to the fifth end, wherein the fifth end of the second candidate segment is connected to the second end of the segment.

7. The method of claim 6 ,
wherein a second angle in between the second candidate segment and the segment is determined in a counterclockwise direction from the segment to the second candidate segment, and
wherein the second candidate segment is selected in response to the second angle being less than a first set of one or more angles determined respectively from the segment to one or more remaining candidate segments in the counterclockwise direction from the segment.

8. The method of claim 7 , further comprising:
removing, from the second candidate segment, a third arrow pointing from the fifth end to the sixth end of the second candidate segment in response to the selecting the second candidate segment,
wherein the second candidate segment includes a fourth arrow pointing from the sixth end to the fifth end of the second candidate segment,
wherein a lane segment is determined by circumscribing the segment, the second candidate segment, and two additional segments,
wherein each of the two additional segments have one end respectively connected to the segment and the second candidate segment, and
wherein the two additional segments have, opposite to the one end, another end that is connected to each other.

9. A system, comprising:
a processor; and
a memory including processor-executable instructions that, when executed by the processor, cause the system to perform operations comprising:
construct an outline circumscribing a plurality of lanes on a road based on a plurality of segments that extend along the plurality of lanes or the road; and
identify an individual outline of each of the plurality of lanes based on the plurality of segments and the outline circumscribing the plurality of lanes,
wherein the plurality of segments is obtained by partitioning polylines describing a shape of the road into segments that are constructed on a start point, an end point, or a turning point of the polylines.

10. The system of claim 9 , wherein the outline forms a closed space that circumscribe the plurality of lanes.

11. The system of claim 9 , wherein the processor is further configured to:
cause a vehicle to operate along a set of waypoints on a lane from the plurality of lanes, wherein the set of waypoints are calculated in a middle of the lane.

12. The system of claim 9 , wherein the processor is further configured to:
construct, for each of the plurality of lanes, lane geometry data based on the plurality of segments; and
generate, based on the lane geometry data, a lane content that includes a graphical representation of the plurality of lanes and waypoints of the plurality of lanes.

13. The system of claim 9 , wherein any segment from the plurality of segments does not cross any other segment from the plurality of segments.

14. A non-transitory computer readable storage medium comprising executable instructions that, when executed by at least one processor, cause the at least one processor to perform a method, comprising:
constructing an outline circumscribing a plurality of lanes on a road based on a plurality of segments that extend along the plurality of lanes or the road; and identifying an individual outline of each of the plurality of lanes based on the plurality of segments and the outline circumscribing the plurality of lanes,
wherein the plurality of segments is obtained by partitioning polylines describing a shape of the road into segments that are constructed on a start point, an end point, or a turning point of the polylines.

15. The non-transitory computer readable storage medium of claim 14 , wherein the method further comprises:
removing, from the plurality of segments, at least one segment having one end that is not connected to another segment.

16. The non-transitory computer readable storage medium of claim 14 , wherein the method further comprises:
merging, from the plurality of segments, at least two segments in response to determining that the at least two segments merge at only one end with each other.

17. The non-transitory computer readable storage medium of claim 14 , wherein each of the plurality of lanes comprises a plurality of lane segments, wherein each lane segment is circumscribed by a set of segments from the plurality of segments.

18. The non-transitory computer readable storage medium of claim 17 , wherein a first lane segment

Assignees

• Tusimple Inc

Inventors

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

Classifications

• G08G1/167

  Driving aids for lane monitoring, lane changing, e.g. blind spot detection · CPC title

• G01S19/48

  by combining or switching between position solutions derived from the satellite radio beacon positioning system and position solutions derived from a further system · CPC title

• G06T7/11

  Region-based segmentation · CPC title

• G06T7/75

  involving models · CPC title

• G06T2207/30256

  Lane; Road marking · CPC title