# US 2019/0376795 A1 · Map matching method and apparatus

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

- Number: US 2019/0376795 A1
- Document ID: US20190376795A1
- Status: Published application
- Kind: A1
- Application number: 16/004,833
- Filed: 2018-06-11
- Published: 2019-12-12
- Earliest claimed: 2018-06-11
- Assignees: HERE Global B.V.
- Applicants: HERE Global B.V.
- Inventors: Eric Linder
- Web page: https://patentgrep.com/patent/US20190376795A1

## CPC

- G01C 21/30: Map- or contour-matching
- G06F 16/29: Geographical information databases
- H04W 4/021: Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
- H04W 4/024: Guidance services
- H04W 4/40: for vehicles, e.g. vehicle-to-pedestrians [V2P]
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

A method, apparatus and computer program product are provided to process probe data in accordance with an efficient map matching technique. Methods may include obtaining a road link within a geographic area from a database of a plurality of road links; calculating a plurality of areas of interest and a centroid for each; receiving a probe data point from a probe apparatus including one or more sensors and being onboard a vehicle, where the probe data point includes location information associated with the probe apparatus; determining that the probe data point location information corresponds to the geographic area; determining that the probe data point location corresponds to an area of interest disposed along the road link within the geographic area; and map matching the probe data point to a centroid of the area of interest determined to correspond to the probe data point location.

## Claims

### Claim 1

An apparatus to map match probe data points to a road segment including at least one processor and at least one non-transitory memory including computer program code instructions, the computer program code instructions configured to, when executed, cause the apparatus to at least:
obtain a road link within a geographic area from a database of a plurality of road links;
calculate a plurality of areas of interest along a length of the road link;
calculate a centroid of each of the plurality of areas of interest along the length of the road link;
receive a probe data point from a probe apparatus comprising one or more sensors and being onboard a vehicle, wherein the probe data point comprises location information associated with the probe apparatus;
determine that the probe data point location information corresponds to the geographic area;
determine that the probe data point location corresponds to an area of interest disposed along the road link within the geographic area;
map match the probe data point to the centroid of the area of interest determined to correspond to the probe data point location; and
provide for at least one of navigational assistance or at least semi-autonomous vehicle control in response to map matching the probe data point to the centroid of the area of interest.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein causing the apparatus to calculate a plurality of areas of interest comprises causing the apparatus to:
determine a maximum map match distance within which a probe data point must be of a road segment to be map matched to that road segment; and
determine an acceptable error threshold defining a maximum acceptable distance error for map matching a probe data point along a road segment;
wherein each of the plurality of areas of interest is a rectangle having a first dimension based upon the maximum map match distance and a second dimension based upon the acceptable error threshold.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the first dimension for an area of interest extends in a longitudinal direction and the second dimension extends in a latitudinal direction in response to a heading of the road link being between northeast and southeast or between northwest and southwest;
wherein the first dimension for an area of interest extends in a latitudinal direction and the second dimension extends in a longitudinal direction in response to the heading of the road link being between northwest and northeast or between southwest and southeast.

### Claim 4 (depends on 3)

The apparatus of claim 3, wherein each area of interest is defined by at least two points, each point including a latitude and a longitude, and each of the at least two points defining a corner of the rectangle of the area of interest.

### Claim 5 (depends on 4)

The apparatus of claim 4, wherein map matching the probe data point to an area of interest comprises causing the apparatus to:
compare a latitude of the probe data point against a minimum latitude of the at least two points of a respective area;
compare the latitude of the probe data point against a maximum latitude of the at least two points of the respective area;
compare a longitude of the probe data point against a minimum longitude of the at least two points of the respective area; and
compare the longitude of the probe data point against a maximum longitude of the at least two points of the respective area;
wherein the probe data point is map matched to the area of interest in response to the latitude of the probe data point being above the minimum latitude of the at least two points of the area of interest and below the maximum latitude of the at least two points of the area of interest, and the longitude of the probe data point being above the minimum longitude of the at least two points of the area of interest and below the maximum longitude of the at least two points of the area of interest.

### Claim 6 (depends on 1)

The apparatus of claim 1, wherein causing the apparatus to determine that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprises causing the apparatus to:
determine that the probe data point location corresponds to at least two areas of interest within the geographic area;
determine a heading of the probe data point; and
determine a heading of each of the at least two areas of interest corresponding to a portion of the road link to which each of the at least two areas of interest correspond;
wherein causing the apparatus to determine that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprises causing the apparatus to determine that the probe data point location corresponds to an area of interest of the at least two areas of interest having a heading closest to the heading of the probe data point.

### Claim 7 (depends on 1)

The apparatus of claim 1, wherein causing the apparatus to determine that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprises causing the apparatus to:
determine that the probe data point location corresponds to at least two areas of interest within the geographic area; and
calculate a distance from the probe data point location to a centroid of each of the at least two areas of interest;
wherein causing the apparatus to determine that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprises causing the apparatus to determine that the probe data point location corresponds to an area of interest of the at least two areas of interest having a centroid closest to the location of the probe data point.

### Claim 8

A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions configured to:
obtain a road link within a geographic area from a database of a plurality of road links;
calculate a plurality of areas of interest along a length of the road link;
calculate a centroid of each of the plurality of areas of interest along the length of the road link;
receive a probe data point from a probe apparatus comprising one or more sensors and being onboard a vehicle, wherein the probe data point comprises location information associated with the probe apparatus;
determine that the probe data point location information corresponds to the geographic area;
determine that the probe data point location corresponds to an area of interest disposed along the road link within the geographic area;
map match the probe data point to a centroid of the area of interest determined to correspond to the probe data point location; and
provide for at least one of navigational assistance or at least semi-autonomous vehicle control in response to map matching the probe data point to the centroid of the area of interest.

### Claim 9 (depends on 8)

The computer program product of claim 8, wherein the program code instructions to calculate a plurality of areas of interest comprise program code instructions to:
determine a maximum map match distance within which a probe data point must be of a road segment to be map matched to that road segment; and
determine an acceptable error threshold defining a maximum acceptable distance error for map matching a probe data point along a road segment;
wherein each of the plurality of areas of interest is a rectangle having a first dimension based upon the maximum map match distance and a second dimension based upon acceptable error threshold.

### Claim 10 (depends on 9)

The computer program product of claim 9, wherein the first dimension for an area of interest extends in a longitudinal direction and the second dimension extends in a latitudinal direction in response to a heading of the road link being between northeast and southeast or between northwest and southwest;
wherein the first dimension for an area of interest extends in a latitudinal direction and the second dimension extends in a longitudinal direction in response to the heading of the road link being between northwest and northeast or between southwest and southeast.

### Claim 11 (depends on 10)

The computer program product of claim 10, wherein each area of interest is defined by at least two points, each point including a latitude and a longitude, and each of the at least two points defining a corner of the rectangle of the area of interest.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein the program code instructions to map match the probe data point to an area of interest comprise program code instructions to:
compare a latitude of the probe data point against a minimum latitude of the at least two points of a respective area;
compare the latitude of the probe data point against a maximum latitude of the at least two points of the respective area;
compare a longitude of the probe data point against a minimum longitude of the at least two points of the respective area; and
compare the longitude of the probe data point against a maximum longitude of the at least two points of the respective area;
wherein the probe data point is map matched to the area of interest in response to the latitude of the probe data point being above the minimum latitude of the at least two points of the area of interest and below the maximum latitude of the at least two points of the area of interest, and the longitude of the probe data point being above the minimum longitude of the at least two points of the area of interest and below the maximum longitude of the at least two points of the area of interest.

### Claim 13 (depends on 8)

The computer program product of claim 8, wherein the program code instructions to determine that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprise program code instructions to:
determine that the probe data point location corresponds to at least two areas of interest within the geographic area;
determine a heading of the probe data point; and
determine a heading of each of the at least two areas of interest corresponding to a portion of the road link to which each of the at least two areas of interest correspond;
wherein the program code instructions to determine that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprises program code instructions to determine that the probe data point location corresponds to an area of interest of the at least two areas of interest having a heading closest to the heading of the probe data point.

### Claim 14 (depends on 8)

The computer program product of claim 8, wherein the program code instructions to determine that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprise program code instructions to:
determine that the probe data point location corresponds to at least two areas of interest within the geographic area; and
calculate a distance from the probe data point location to a centroid of each of the at least two areas of interest;
wherein the program code instructions to determine that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprises program code instructions to determine that the probe data point location corresponds to an area of interest of the at least two areas of interest having a centroid closest to the location of the probe data point.

### Claim 15

A method comprising:
obtaining a road link within a geographic area from a database of a plurality of road links;
calculating a plurality of areas of interest along a length of the road link;
calculating a centroid of each of the plurality of areas of interest along the length of the road link;
receiving a probe data point from a probe apparatus comprising one or more sensors and being onboard a vehicle, wherein the probe data point comprises location information associated with the probe apparatus;
determining that the probe data point location information corresponds to the geographic area;
determining that the probe data point location corresponds to an area of interest disposed along the road link within the geographic area;
map matching the probe data point to a centroid of the area of interest determined to correspond to the probe data point location; and
providing for at least one of navigational assistance or at least semi-autonomous vehicle control in response to map matching the probe data point to the centroid of the area of interest.

### Claim 16 (depends on 15)

The method of claim 15, wherein calculating a plurality of areas of interest comprises:
determining a maximum map match distance within which a probe data point must be of a road segment to be map matched to that road segment; and
determining an acceptable error threshold defining a maximum acceptable distance error for map matching a probe data point along a road segment;
wherein each of the plurality of areas of interest is a rectangle having a first dimension based upon the maximum map match distance and a second dimension based upon the acceptable error threshold.

### Claim 17 (depends on 16)

The method of claim 16, wherein the first dimension for an area of interest extends in a longitudinal direction and the second dimension extends in a latitudinal direction in response to a heading of the road link being between northeast and southeast or between northwest and southwest;
wherein the first dimension for an area of interest extends in a latitudinal direction and the second dimension extends in a longitudinal direction in response to the heading of the road link being between northwest and northeast or between southwest and southeast.

### Claim 18 (depends on 17)

The method of claim 17, wherein each area of interest is defined by at least two points, each point including a latitude and a longitude, and each of the at least two points defining a corner of the rectangle of the area of interest.

### Claim 19 (depends on 18)

The method of claim 18, wherein map matching the probe data point to an area of interest comprises:
comparing the latitude of the probe data point against a minimum latitude of the at least two points of a respective area;
comparing the latitude of the probe data point against a maximum latitude of the at least two points of the respective area;
comparing the longitude of the probe data point against a minimum longitude of the at least two points of the respective area; and
comparing the longitude of the probe data point against a maximum longitude of the at least two points of the respective area;
wherein the probe data point is map matched to the area of interest in response to the latitude of the probe data point being above the minimum latitude of the at least two points of the area of interest and below the maximum latitude of the at least two points of the area of interest, and the longitude of the probe data point being above the minimum longitude of the at least two points of the area of interest and below the maximum longitude of the at least two points of the area of interest.

### Claim 20 (depends on 15)

The method of claim 15, wherein determining that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprises:
determining that the probe data point location corresponds to at least two areas of interest within the geographic area;
determining a heading of the probe data point; and
determining a heading of each of the at least two areas of interest corresponding to a portion of the road link to which each of the at least two areas of interest correspond;
wherein determining that the probe data point location corresponds to an area of interest within the geographic area disposed along the road link comprises determining that the probe data point location corresponds to an area of interest of the at least two areas of interest having a heading closest to the heading of the probe data point.
