# US 12,761,045 B2 · Systems and methods for generating lane line maps for a vehicle

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,761,045 B2
- Document ID: US12761045B2
- Status: Granted
- Kind: B2
- Application number: 18/753,953
- Filed: 2024-06-25
- Published: 2025-12-25
- Granted: 2026-10-13
- Earliest claimed: 2024-06-25
- Assignees: GM Global Technology Operations LLC
- Applicants: GM Global Technology Operations LLC
- Inventors: Bo Yu; Kamran Ali; Gui Chen; Joon Hwang; Thaer Arafat
- Web page: https://patentgrep.com/patent/US12761045B2

## CPC

- G01C 21/3841: {Data obtained from two or more sources, e.g. probe vehicles}
- G01C 21/3822: {Road feature data, e.g. slope data}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)

## Abstract

Systems and methods are provided for crowd-sourcing lane line map data for a vehicle. The systems include a server communication system, a map database, a server controller that is programmed to: receive observations using the server communication system, generate a point cloud alignment vector based at least in part on the observations, determine confidence scores for the observations based at least in part on the point cloud alignment vector, designate a subset of the observations having confidence scores in excess of a confidence score threshold as anchor points, generate an optimized aligned point cloud based at least in part on the point cloud alignment vector and the anchor points, determine a lane line map based at least in part on the optimized aligned point cloud, and update the map database based at least in part on the lane line map.

## Claims

### Claim 1

A method for crowd-sourcing lane line map data for a vehicle, the method comprising:
receiving a plurality of observations, wherein the plurality of observations includes at least a first observation and a second observation, wherein receiving the plurality of observations includes receiving the plurality of observations from one or more vehicles, wherein each of the plurality of observations includes a vehicle location trajectory and a plurality of points positioned relative to the vehicle location trajectory, wherein each point of the plurality of points includes a plurality of point characteristics, wherein one of the plurality of point characteristics is a location of each point relative to the vehicle location trajectory, and wherein each of the plurality of points corresponds to an object in an environment surrounding the one or more vehicles;
generating a point cloud alignment vector using a point cloud registration algorithm based at least in part on the plurality of observations, wherein using the point cloud registration algorithm includes determining the point cloud alignment vector such that shifting the vehicle location trajectory of the second observation by the point cloud alignment vector aligns the vehicle location trajectory of the second observation with the vehicle location trajectory of the first observation;
determining confidence scores for the plurality of observations based at least in part on the point cloud alignment vector;
designating a subset of the plurality of observations having confidence scores in excess of a confidence score threshold as anchor points;
generating an optimized aligned point cloud based at least in part on the point cloud alignment vector and the anchor points, wherein generating the optimized aligned point cloud includes:
determining a plurality of correction vectors, wherein each of the plurality of correction vectors corresponds to one of the plurality of points of the second observation, wherein determining the plurality of correction vectors includes minimizing an objective function to determine the plurality of correction vectors, wherein the objective function includes at least a plurality of cost functions, wherein each of the plurality of cost functions depends at least in part on the plurality of correction vectors, wherein each of the plurality of cost functions corresponds to one of a plurality of optimization constraints, and wherein the plurality of optimization constraints includes at least: a trajectory pose constraint, a location vicinity constraint, and optionally an anchor point constraint, wherein the trajectory pose constraint limits a change in shape of the trajectory of the plurality of points of the second observation resulting from applying the plurality of correction vectors to the plurality of points of the second observation, wherein the location vicinity constraint limits movement of the second observation from an original location thereof resulting from applying the plurality of correction vectors to the plurality of points of the second observation, wherein the anchor point constraint limits movement of the second observation towards the first observation resulting from applying the plurality of correction vectors to the plurality of points of the second observation; and
shifting each of the plurality of points of the second observation to generate the optimized aligned point cloud, wherein each of the plurality of points of the second observation is shifted based at least in part on one of the plurality of correction vectors;
determining a lane line map based at least in part on the optimized aligned point cloud; and
updating a map database based at least in part on the lane line map.

### Claim 2 (depends on 1)

The method of claim 1, wherein the plurality of cost functions includes:
an anchor point constraint cost function, wherein the anchor point constraint cost function is:
Cost
o
⁢
b
(
c
i
)
=
c
i
-
C
i
σ
ob
2
(
i
)
wherein Costob(ci) is the anchor point constraint cost function for one of the plurality of correction vectors corresponding to an ith point of the plurality of points of the second observation, ci is one of the plurality of correction vectors corresponding to an ith point of the plurality of points of the second observation, Ci is the point cloud alignment vector for the ith point of the plurality of points of the second observation, and
σ
o
⁢
b
2
(
i
)
is an alignment variance of the ith point of the plurality of points of the second observation;
a trajectory pose constraint cost function, wherein the trajectory pose constraint cost function is:
Cost
pose
(
c
i
)
=
f
pose
(
c
i
,
c
i
+
1
)
-
f
pose
(
c
.
i
,
c
.
i
+
1
)
σ
pose
2
(
i
)
wherein Costpose(ci) is the trajectory pose constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ci is one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ċi is an initial correction vector corresponding to the ith point of the plurality of points of the second observation, fpose(ci, ci+1) is a heading between the ith point of the plurality of points of the second observation and an i+1th point of the plurality of points of the second observation after application of one of the plurality of correction vectors, fpose(ċi, ċi+1) is a heading between the ith point of the plurality of points of the second observation and the i+1th point of the plurality of points of the second observation after application of the initial correction vector, and
σ
pose
2
(
i
)
is a pose variance of the ith point of the plurality of points of the second observation; and
a location vicinity constraint cost function, wherein the location vicinity constraint cost function is:
Cost
loc
(
c
i
)
=
e
⁢
u
⁢
clidian
⁡
(
c
i
,
c
.
i
)
σ
loc
2
(
i
)
wherein Costloc(ci) is the location vicinity constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ci is one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ċi is the initial correction vector corresponding to the ith point of the plurality of points of the second observation, euclidian (ci, ċi), is a Euclidian distance between a location of the ith point after application of one of the plurality of correction vectors and a location of the ith point after application of the initial correction vector, and
σ
loc
2
(
i
)
is an location variance of the ith point of the plurality of points of the second observation.

### Claim 3 (depends on 2)

The method of claim 2,
wherein the objective function further includes:
F
⁡
(
c
1
,
c
2
,
⋯
,
c
n
)
=
∑
c
i
(
Cost
ob
(
c
i
)
2
+
Cost
pose
(
c
i
)
2
+
Cost
loc
(
c
i
)
2
)
wherein F(c1, c2, . . . , cn) is the objective function, c1, c2, . . . , cn are the plurality of correction vectors, ci is one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, Costob(ci) is the anchor point constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, Costpose(ci) is the trajectory pose constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, and Costloc(ci) is the location vicinity constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation.

### Claim 4 (depends on 1)

The method of claim 1, wherein minimizing the objective function to determine the plurality of correction vectors includes using an iterative optimization algorithm.

### Claim 5 (depends on 4)

The method of claim 4, wherein the iterative optimization algorithm is a factor graph optimization algorithm, and wherein the method includes:
generating a factor graph, wherein the factor graph includes a plurality of variable nodes, a plurality of factor nodes, and a plurality of edges linking variable nodes and factor nodes, wherein each of the plurality of variable nodes represents one of the plurality of correction vectors, wherein each of the plurality of factor nodes represents one of the plurality of optimization constraints, and wherein each of the plurality of edges represents one of the plurality of cost functions; and
updating one or more of the plurality of variable nodes using an iterative process until a convergence condition is satisfied.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
adjusting an operation of the vehicle at least in part based on the lane line map.

### Claim 7

A system for crowd-sourcing lane line map data for a vehicle, the system comprising:
a server communication system;
a map database;
a server controller in electrical communication with the server communication system and the map database, wherein the server controller is programmed to:
receive a plurality of observations using the server communication system, wherein the plurality of observations includes at least a first observation and a second observation, wherein receiving the plurality of observations includes receiving the plurality of observations from one or more vehicles, wherein each of the plurality of observations includes a vehicle location trajectory and a plurality of points positioned relative to the vehicle location trajectory, wherein each point of the plurality of points includes a plurality of point characteristics, wherein one of the plurality of point characteristics is a location of each point relative to the vehicle location trajectory, and wherein each of the plurality of points corresponds to an object in an environment surrounding the one or more vehicles;
generate a point cloud alignment vector using a point cloud registration algorithm based at least in part on the plurality of observations, wherein using the point cloud registration algorithm includes determining the point cloud alignment vector such that shifting the vehicle location trajectory of the second observation by the point cloud alignment vector aligns the vehicle location trajectory of the second observation with the vehicle location trajectory of the first observation;
determine confidence scores for the plurality of observations based at least in part on the point cloud alignment vector;
designate a subset of the plurality of observations having confidence scores in excess of a confidence score threshold as anchor points;
generate an optimized aligned point cloud based at least in part on the point cloud alignment vector and the anchor points, wherein generating the optimized aligned point cloud includes:
determining a plurality of correction vectors, wherein each of the plurality of correction vectors corresponds to one of the plurality of points of the second observation, wherein determining the plurality of correction vectors includes minimizing an objective function to determine the plurality of correction vectors, wherein the objective function includes at least a plurality of cost functions, wherein each of the plurality of cost functions depends at least in part on the plurality of correction vectors, wherein each of the plurality of cost functions corresponds to one of a plurality of optimization constraints, and wherein the plurality of optimization constraints includes at least: a trajectory pose constraint, a location vicinity constraint, and optionally an anchor point constraint, wherein the trajectory pose constraint limits a change in shape of the trajectory of the plurality of points of the second observation resulting from applying the plurality of correction vectors to the plurality of points of the second observation, wherein the location vicinity constraint limits movement of the second observation from an original location thereof resulting from applying the plurality of correction vectors to the plurality of points of the second observation, wherein the anchor point constraint limits movement of the second observation towards the first observation resulting from applying the plurality of correction vectors to the plurality of points of the second observation; and
shifting each of the plurality of points of the second observation to generate the optimized aligned point cloud, wherein each of the plurality of points of the second observation is shifted based at least in part on one of the plurality of correction vectors;
determine a lane line map based at least in part on the optimized aligned point cloud; and
update the map database based at least in part on the lane line map.

### Claim 8 (depends on 7)

The system of claim 7, wherein the plurality of cost functions includes:
an anchor point constraint cost function, wherein the anchor point constraint cost function is:
Cost
o
⁢
b
(
c
i
)
=
c
i
-
C
i
σ
ob
2
(
i
)
wherein Costob(ci) is the anchor point constraint cost function for one of the plurality of correction vectors corresponding to an ith point of the plurality of points of the second observation, ci is one of the plurality of correction vectors corresponding to an ith point of the plurality of points of the second observation, Ci is the point cloud alignment vector for the ith point of the plurality of points of the second observation, and
σ
o
⁢
b
2
(
i
)
is an alignment variance of the ith point of the plurality of points of the second observation;
a trajectory pose constraint cost function, wherein the trajectory pose constraint cost function is:
Cost
pose
(
c
i
)
=
f
pose
(
c
i
,
c
i
+
1
)
-
f
pose
(
c
.
i
,
c
.
i
+
1
)
σ
pose
2
(
i
)
wherein Costpose(ci) is the trajectory pose constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ci is one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ċi is an initial correction vector corresponding to the ith point of the plurality of points of the second observation, fpose(ci, ci+1) is a heading between the ith point of the plurality of points of the second observation and an i+1th point of the plurality of points of the second observation after application of one of the plurality of correction vectors, fpose(ċi, ċi+1) is a heading between the ith point of the plurality of points of the second observation and the i+1th point of the plurality of points of the second observation after application of the initial correction vector, and
σ
pose
2
(
i
)
is a pose valiance of the ith point of the plurality of points of the second observation; and
a location vicinity constraint cost function, wherein the location vicinity constraint cost function is:
Cost
loc
(
c
i
)
=
e
⁢
u
⁢
clidian
⁡
(
c
i
,
c
.
i
)
σ
loc
2
(
i
)
wherein Costloc(ci) is the location vicinity constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ci is one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ċi is the initial correction vector corresponding to the ith point of the plurality of points of the second observation, euclidian (ci, ċi), is a Euclidian distance between a location of the ith point after application of one of the plurality of correction vectors and a location of the ith point after application of the initial correction vector, and
σ
loc
2
(
i
)
is an location variance of the ith point of the plurality of points of the second observation.

### Claim 9 (depends on 8)

The system of claim 8,
wherein the objective function includes:
F
⁡
(
c
1
,
c
2
,
⋯
,
c
n
)
=
∑
c
i
(
Cost
ob
(
c
i
)
2
+
Cost
pose
(
c
i
)
2
+
Cost
loc
(
c
i
)
2
)
wherein F(c1, c2, . . . , cn) is the objective function, c1, c2, . . . , cn are the plurality of correction vectors, ci is one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, Costob(ci) is the anchor point constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, Costpose(ci) is the trajectory pose constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, and Costloc(ci) is the location vicinity constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation.

### Claim 10 (depends on 7)

The system of claim 7, wherein the server controller is programmed to minimize the objective function to determine the plurality of correction vectors includes using an iterative optimization algorithm.

### Claim 11 (depends on 10)

The system of claim 10, wherein the iterative optimization algorithm is a factor graph optimization algorithm, and wherein the server controller is further programmed to:
generate a factor graph, wherein the factor graph includes a plurality of variable nodes, a plurality of factor nodes, and a plurality of edges linking variable nodes and factor nodes, wherein each of the plurality of variable nodes represents one of the plurality of correction vectors, wherein each of the plurality of factor nodes represents one of the plurality of optimization constraints, and wherein each of the plurality of edges represents one of the plurality of cost functions; and
update one or more of the plurality of variable nodes to determine the plurality of correction vectors using an iterative process until a convergence condition is satisfied.

### Claim 12 (depends on 7)

The system of claim 7, wherein the server controller is programmed to transmit the lane line map to the one or more vehicles, wherein the lane line map is configured to be used by the one or more vehicles to adjust an operation thereof at least in part based on the lane line map.

### Claim 13 (depends on 12)

The system of claim 12, wherein the lane line map is configured to be used by the one or more vehicles to adjust operation of an advanced driver assistance system.

### Claim 14 (depends on 7)

The system of claim 7, wherein the plurality of point characteristics further includes a lane line color, a lane line type, and a lane line location relative to traffic direction.

### Claim 15

A system for crowd-sourcing lane line map data for a vehicle, the system comprising:
a server communication system;
a map database;
a server controller in electrical communication with the server communication system and the map database, wherein the server controller is programmed to:
receive a plurality of observations from one or more vehicles using the server communication system, wherein the plurality of observations includes at least a first observation and a second observation, wherein each of the plurality of observations includes a vehicle location trajectory and a plurality of points positioned relative to the vehicle location trajectory, wherein each point of the plurality of points includes a plurality of point characteristics, wherein one of the plurality of point characteristics is a location of each point relative to the vehicle location trajectory, and wherein each of the plurality of points corresponds to an object in an environment surrounding the one or more vehicles;
generate a point cloud alignment vector using a point cloud registration algorithm based at least in part on the plurality of observations, wherein using the point cloud registration algorithm includes determining the point cloud alignment vector such that shifting the vehicle location trajectory of the second observation by the point cloud alignment vector aligns the vehicle location trajectory of the second observation with the vehicle location trajectory of the first observation;
determine confidence scores for the plurality of observations based at least in part on the point cloud alignment vector;
designate a subset of the plurality of observations having confidence scores in excess of a confidence score threshold as anchor points;
generate an optimized aligned point cloud based at least in part on the point cloud alignment vector and the anchor points, wherein generating the optimized aligned point cloud includes:
determining a plurality of correction vectors, wherein each of the plurality of correction vectors corresponds to one of the plurality of points of the second observation, wherein determining the plurality of correction vectors includes minimizing an objective function to determine the plurality of correction vectors, wherein the objective function includes at least a plurality of cost functions, wherein each of the plurality of cost functions depends at least in part on the plurality of correction vectors, wherein each of the plurality of cost functions corresponds to one of a plurality of optimization constraints, and wherein the plurality of optimization constraints includes at least: a trajectory pose constraint, a location vicinity constraint, and optionally an anchor point constraint, wherein the trajectory pose constraint limits a change in shape of the trajectory of the plurality of points of the second observation resulting from applying the plurality of correction vectors to the plurality of points of the second observation, wherein the location vicinity constraint limits movement of the second observation from an original location thereof resulting from applying the plurality of correction vectors to the plurality of points of the second observation, wherein the anchor point constraint limits movement of the second observation towards the first observation resulting from applying the plurality of correction vectors to the plurality of points of the second observation; and
shifting each of the plurality of points of the second observation to generate the optimized aligned point cloud, wherein each of the plurality of points of the second observation is shifted based at least in part on one of the plurality of correction vectors;
determine a lane line map based at least in part on the optimized aligned point cloud;
update the map database based at least in part on the lane line map; and
transmit the lane line map to the one or more vehicles, wherein the one or more vehicles are configured to adjust an operation thereof at least in part based on the lane line map.

### Claim 16 (depends on 15)

The system of claim 15, wherein the plurality of cost functions includes:
an anchor point constraint cost function, wherein the anchor point constraint cost function is:
Cost
o
⁢
b
(
c
i
)
=
c
i
-
C
i
σ
o
⁢
b
2
(
i
)
wherein Costob(ci) is the anchor point constraint cost function for one of the plurality of correction vectors corresponding to an ith point of the plurality of points of the second observation, ci is one of the plurality of correction vectors corresponding to an ith point of the plurality of points of the second observation, Ci is the point cloud alignment vector for the ith point of the plurality of points of the second observation, and Is an alignment variance of the ith point of the plurality of points of the
σ
o
⁢
b
2
(
i
)
second observation;
a trajectory pose constraint cost function, wherein the trajectory pose constraint cost function is:
Cost
p
⁢
o
⁢
s
⁢
e
(
c
i
)
=
f
p
⁢
o
⁢
s
⁢
e
(
c
i
,
c
i
+
1
)
-
f
p
⁢
o
⁢
s
⁢
e
(
c
.
i
,
c
.
i
+
1
)
σ
p
⁢
o
⁢
s
⁢
e
2
(
i
)
wherein Costpose(ci) is the trajectory pose constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ci is one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ċi is an initial correction vector corresponding to the ith point of the plurality of points of the second observation, fpose(ci, ci+1) is a heading between the ith point of the plurality of points of the second observation and an i+1th point of the plurality of points of the second observation after application of one of the plurality of correction vectors, fpose(ċi, ċi+1) is a heading between the ith point of the plurality of points of the second observation and the i+1th point of the plurality of points of the second observation after application of the initial correction vector, and
σ
p
⁢
o
⁢
s
⁢
e
2
(
i
)
is a pose variance of the ith point of the plurality of points of the second observation; and
a location vicinity constraint cost function, wherein the location vicinity constraint cost function is:
Cost
loc
(
c
i
)
=
euclidian
⁡
(
c
i
,
c
.
i
)
σ
loc
2
(
i
)
wherein Costloc(ci) is the location vicinity constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ci is one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, ċi is the initial correction vector corresponding to the ith point of the plurality of points of the second observation, euclidian (ci, ċi), is a Euclidian distance between a location of the ith point after application of one of the plurality of correction vectors and a location of the ith point after application of the initial correction vector, and
σ
l
⁢
o
⁢
c
2
(
i
)
is an location variance of the ith point of the plurality of points of the second observation.

### Claim 17 (depends on 16)

The system of claim 16, wherein the objective function includes:
F
⁡
(
c
1
,
c
2
,
…
,
c
n
)
=
∑
c
i
(
Cost
o
⁢
b
(
c
i
)
2
+
Cost
p
⁢
o
⁢
s
⁢
e
(
c
i
)
2
+
Cost
loc
(
c
i
)
2
)
wherein F(c1, c2, . . . , cn) is the objective function, c1, c2, . . . , cn are the plurality of correction vectors, ci is one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, Costob(ci) is the anchor point constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, Costpose(ci) is the trajectory pose constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation, and Costloc(ci) is the location vicinity constraint cost function for one of the plurality of correction vectors corresponding to the ith point of the plurality of points of the second observation.

### Claim 18 (depends on 15)

The system of claim 15, wherein the server controller is programmed to minimize the objective function to determine the plurality of correction vectors using an iterative optimization algorithm.

### Claim 19 (depends on 18)

The system of claim 18, wherein the iterative optimization algorithm is a factor graph optimization algorithm, and wherein the server controller is programmed to:
generate a factor graph, wherein the factor graph includes a plurality of variable nodes, a plurality of factor nodes, and a plurality of edges linking variable nodes and factor nodes, wherein each of the plurality of variable nodes represents one of the plurality of correction vectors, wherein each of the plurality of factor nodes represents one of the plurality of optimization constraints, and wherein each of the plurality of edges represents one of the plurality of cost functions; and
update one or more of the plurality of variable nodes to determine the plurality of correction vectors using an iterative process until a convergence condition is satisfied.

### Claim 20 (depends on 19)

The system of claim 19, wherein the convergence condition is satisfied when further modification of the plurality of variable nodes results in an increase of the objective function, when the objective function is less than or equal to a predetermined objective function threshold value, or after completion of a predetermined quantity of iterations.