# US 10,371,535 B1 · Automatic map generation

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

- Number: US 10,371,535 B1
- Document ID: US10371535B1
- Status: Granted
- Kind: B1
- Application number: 15/975,464
- Filed: 2018-05-09
- Granted: 2019-08-06
- Earliest claimed: 2018-05-09
- Assignees: Ford Global Technologies, LLC
- Applicants: Ford Global Technologies, LLC
- Inventors: Homayoun Jamshidi Nekou; Thomas Pilutti
- Web page: https://patentgrep.com/patent/US10371535B1

## CPC

- G01C 21/3811: {Point data, e.g. Point of Interest [POI]}
- G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence)
- G01C 21/3844: {Data obtained from position sensors only, e.g. from inertial navigation}
- G01C 21/3859: {Differential updating map data}
- G08G 1/20: {Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles}
- G09B 29/004: {Map manufacture or repair; Tear or ink or water resistant maps; Long-life maps (printing processes for maps B41M3/02; by permanently attaching map sections to sheets B42B7/00)}
- G09B 29/106: {using electronic means}
- 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)
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})
- G09B: EDUCATIONAL OR DEMONSTRATION APPLIANCES; APPLIANCES FOR TEACHING, OR COMMUNICATING WITH, THE BLIND, DEAF OR MUTE; MODELS; PLANETARIA; GLOBES; MAPS; DIAGRAMS (devices for psychotechnics or for testing reaction times A61B5/16; games, sports, amusements A63; projectors, projector screens G03B)

## Abstract

Map data is augmented using GPS traces captured by navigation systems of vehicles. A GPS trace is reduced to key points identified based on magnitude of bearing changes and to maintain a maximum separation between key points. The locations and bearings of each key point are compared to locations and bearings along map traces in the map data. Where the location and bearing meet threshold conditions, the key point is merged with the map trace, such as by computing an average or weighted average. The manner in which the key point is merged is modified based on proximity of the key point to points in the map trace connected by segments of the map trace.

## Claims

### Claim 1

A method comprising:
receiving, by a computer system, a map trace comprising a plurality of first points and defining a plurality of lines connecting adjacent first points of the plurality of first points;
receiving, by the computer system, a second trace comprising a plurality of second points from a navigation system; and
for each second point of a first portion of the plurality of second points, calculating, by the computer system, a new point for the plurality of first points as an average of a location of the each second point and a location on the map trace, the location on the map trace being one of:
a point of the plurality of first points closest to the each second point and
a point on a line of the plurality of lines that is closest to the each second point;
wherein the method further comprises:
identifying the first portion of the plurality of second points as being within a distance threshold from the map trace and as having a heading within a first threshold heading change from the location on the map trace that is closest to each second point of the portion of the plurality of second points.

### Claim 2 (depends on 1)

The method of claim 1, wherein the location on the map trace is a location on the map trace that is closest to the each second point.

### Claim 3 (depends on 2)

The method of claim 2, wherein the new point is a weighted average of a location of the each second point and the location of the closest location lying on the map trace weighted by a weight associated with the map trace.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
identifying a plurality of key points among the plurality of second points, the portion of the plurality of second points being at least a portion of the plurality of key points;
wherein the plurality of key points are identified as at least one of:
bearing points of the second points that meet a second threshold heading change within the second trace; and
span points of the second points that are within a span of the second trace between bearing points that is greater than a maximum separation threshold.

### Claim 5 (depends on 1)

The method of claim 1, further comprising adding the new point to the plurality of first points in the map trace.

### Claim 6 (depends on 1)

The method of claim 1, further comprising, when adding the new point to the plurality of first points would result in a heading change in the map trace that exceeds a third threshold heading change:
changing the new point to an average of the each second point and a first point of the plurality of first points that is closest to the each second point; and
adding the new point to the plurality of first points in the map trace.

### Claim 7 (depends on 1)

The method of claim 1, further comprising, when the each second point is within a threshold proximity to a particular first point of the plurality of first points, setting the new point to be an average of the each second point and the particular first point.

### Claim 8 (depends on 1)

The method of claim 1, further comprising, when a perpendicular line from the map trace to the each second point is not defined, setting the new point to be an average of the each second point and a first point of the plurality of first point that is closest to the each second point.

### Claim 9 (depends on 1)

The method of claim 1, further comprising, for each second point of a second portion of the plurality of second points:
defining a first line from the each second point and perpendicularly intersecting the map trace;
defining a second line from a first point of the plurality of first points closest to the each second point and perpendicularly intersecting the second trace; and
when a first midpoint of the first line is within a threshold proximity to a second midpoint of the second line, setting the new point to be a third midpoint between the first midpoint and the second midpoint.

### Claim 10 (depends on 1)

The method of claim 1, further comprising, following adding the new points for the portion of the plurality of second points to the plurality of first points:
removing those first points of the plurality of first points that both of:
do not meet the second threshold heading change within the map trace; and
are not required such that a span of the map trace between first points of the plurality of points is not greater than a maximum separation threshold.

### Claim 11

A system comprising one or more processing devices and one or more memory devices operably coupled to the one or more processing devices, the one or more memory devices storing executable code effective to cause the one or more processing devices to:
receive a map trace comprising a plurality of first points and defining a plurality of first lines connecting adjacent points of the plurality of first points;
receive a second trace comprising a plurality of second points from a navigation system;
identify a portion of the plurality of second points as being within a distance threshold from the map trace and as having a heading within a first threshold heading change from a location on the map trace that is closest to each second point of the portion of the plurality of second points; and
for each second point of the portion of the plurality of second points, calculate a new point for the plurality of first points that is a weighted average of the location on the map trace that is closest to the each second point weighted by a weight associated with the map trace and the second point, the location on the map trace being one of a first point of the plurality of first points that is closest to the each second point and a point on a line of the plurality of lines that is closest to the each second point.

### Claim 12 (depends on 11)

The system of claim 11, wherein the executable code is further effective to cause the one or more processing devices to:
identify a plurality of key points among the plurality of second points, the portion of the plurality of second points being selected exclusively from the plurality of key points, wherein the plurality of key points are identified as at least one of:
bearing points of the second points that meet a second threshold heading change within the second trace; and
span points of the second points that are within a span of the second trace between bearing points that is greater than a maximum separation threshold.

### Claim 13 (depends on 12)

The system of claim 12, wherein the executable code is further effective to cause the one or more processing devices to, when adding the new point to the plurality of first points would result in a heading change in the map trace that exceeds a third threshold heading change:
change the new point to an average of the each second point and a first point of the plurality of first points that is closest to the each second point; and
add the new point to the plurality of first points in the map trace.

### Claim 14 (depends on 12)

The system of claim 12, wherein the executable code is further effective to cause the one or more processing devices to, when the each second point is within a threshold proximity to a particular first point of the plurality of first points, set the new point to be an average of the each second point and the particular first point.

### Claim 15 (depends on 12)

The system of claim 12, wherein the executable code is further effective to cause the one or more processing devices to, when a perpendicular line from the map trace to the each second point is not defined, set the new point to be an average of the each second point and a first point of the plurality of first point that is closest to the each second point.

### Claim 16 (depends on 12)

The system of claim 12, wherein the executable code is further effective to cause the one or more processing devices to:
define a first line from the each second point and perpendicularly intersecting the map trace;
define a second line from a first point of the plurality of first points closest to the each second point and perpendicularly intersecting the second trace;
when a first midpoint of the first line is within a threshold proximity to a second midpoint of the second line, set the new point to be a third midpoint between the first midpoint and the second midpoint; and
add the new point to the plurality of first points of the map trace.

### Claim 17 (depends on 12)

The system of claim 12, wherein the executable code is further effective to cause the one or more processing devices to, following adding the new points for the portion of the plurality of second points to the plurality of first points:
remove those first points of the plurality of first points that both of:
do not meet the second threshold heading change within the map trace; and
are not required such that a span of the map trace between first points of the plurality of points is not greater than a maximum separation threshold.

### Claim 18 (depends on 11)

The system of claim 11, wherein the executable code is further effective to cause the one or more processing devices to:
add the new point to the plurality of first points in the map trace.