Map-centric map matching method and apparatus

Patent metadata

Field	Value
Publication number	US-10677598-B2
Application number	US-201815989798-A
Country	US
Kind code	B2
Filing date	May 25, 2018
Priority date	May 25, 2018
Publication date	Jun 9, 2020
Grant date	Jun 9, 2020

Abstract

A method, apparatus and computer program product are provided to process probe data in accordance with a map-centric map matching technique. Methods may include obtaining a road link from a database of a plurality of road links; calculating a boundary separation distance for spacing vertices along a length of the road link; determining a sequence of vertices along the road link according to the boundary separation distance; generating, for each vertex, a spatial boundary where an overlap between spatial boundaries of adjacent vertices extends a first distance from the road link, where the first distance is a minimum distance from the road link; and providing for storage of a spatial boundary structure for the road link including the plurality of spatial boundaries associated with the road link.

First claim

That which is claimed:

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 from a database of a plurality of road links;
calculate a boundary separation distance for spacing vertices along a length of the road link;
determine a sequence of vertices along the road link according to the boundary separation distance;
for each vertex, generate a spatial boundary, wherein an overlap between spatial boundaries of adjacent vertices extends a first distance from the road link, wherein the first distance is a minimum distance from the road link;
provide for storage of a spatial boundary structure for the road link comprising the plurality of spatial boundaries associated with the road link;
receive a probe data point including a location;
determine a spatial boundary within which the probe data point location falls; and
map-match the probe data point to the road link.

2. The apparatus of claim 1 , wherein the spatial boundary generated for each vertex comprises a circle having a radius less than the spatial boundary distance, and wherein an intersection between adjacent spatial boundaries along the road link is disposed at least a predefined tolerance distance from the road link.

3. The apparatus of claim 1 , wherein the apparatus is further caused to map match the received probe data point to a sub-segment of the road link based on the determined spatial boundary within the spatial boundary structure and a sub-segment of the road link corresponding to the vertex of the determined spatial boundary.

4. The apparatus of claim 1 , wherein the road link is a first road link, and wherein the apparatus is further caused to:
obtain a second road link from the database of a plurality of road links;
determine a sequence of vertices along the second road link according to the boundary separation distance;
for each vertex of the second road link, generate a spatial boundary, wherein an overlap between spatial boundaries of adjacent vertices extends a first distance from the second road link, wherein the first distance is a minimum distance from the second road link;
wherein causing the apparatus to determine a spatial boundary within which the probe data point location falls comprises causing the apparatus to determine a first spatial boundary of the first road link within which the probe data point location falls and a second spatial boundary of the second road link within which the probe data point falls, the apparatus further caused to:
compute the probability of the probe data point belonging to the first road link;
compute the probability of the probe data point belonging to the second road link; and
map match the probe data point to the one of the first road link or second road link with the higher probability.

5. The apparatus of claim 1 , wherein causing the apparatus to provide for storage of the spatial boundary structure for the road link comprises causing the apparatus to:
identify a map tile associated with the road link based on an anchor node of the road link; and
provide for storage of the spatial boundary structure for the road link in association with the identified map tile.

6. The apparatus of claim 1 , wherein causing the apparatus to determine a sequence of vertices along the road link according to the boundary separation distance comprises causing the apparatus to:
identify a latitude and longitude of a first vertex of the sequence of vertices;
determine a directional angle of a next vertex of the sequence of vertices; and
calculate a latitude and longitude of the next vertex based on the latitude and longitude of the first vertex, the boundary separation distance, and the directional angle of the next vertex.

7. The apparatus of claim 1 , wherein the apparatus is further caused to:
provide for at least one of navigation assistance or at least semi-autonomous vehicle control of a vehicle associated with the probe data point along the road link in response to the probe data point being map matched to the road link.

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 from a database of a plurality of road links;
calculate a boundary separation distance for spacing vertices along a length of the road link;
determine a sequence of vertices along the road link according to the boundary separation distance;
for each vertex, generate a spatial boundary, wherein an overlap between spatial boundaries of adjacent vertices extends a first distance from the road link, wherein the first distance is a minimum distance from the road link;
provide for storage of a spatial boundary structure for the road link comprising the plurality of spatial boundaries associated with the road link;
receive a probe data point including a location;
determine a spatial boundary within which the probe data point location falls; and
map match the probe data point to the road link.

9. The computer program product of claim 8 , wherein the spatial boundary generated for each vertex comprises a circle having a radius less than the spatial boundary distance, and wherein an intersection between adjacent spatial boundaries along the road link is disposed at least a predefined tolerance distance from the road link.

10. The computer program product of claim 8 , further comprising program code instructions configured to map match the received probe data point to a sub-segment of the road link based on the determined spatial boundary within the spatial boundary structure and a sub-segment of the road link corresponding to the vertex of the determined spatial boundary.

11. The computer program product of claim 8 , wherein the road link is a first road link, the computer program product further comprising program code instructions configured to:
obtain a second road link from the database of a plurality of road links;
determine a sequence of vertices along the second road link according to the boundary separation distance;
for each vertex of the second road link, generate a spatial boundary, wherein an overlap between spatial boundaries of adjacent vertices extends a first distance from the second road link, wherein the first distance is a minimum distance from the second road link;
wherein the program code instructions to determine a spatial boundary within which the probe data point location falls comprises program code instructions to determine a first spatial boundary of the first road link within which the probe data point location falls and a second spatial boundary of the second road link within which the probe data point falls, the computer program product further including program code instructions to:
compute the probability of the probe data point belonging to the first road link;
compute the probability of the probe data point belonging to the second road link; and
map match the probe data point to the one of the first road link or second road link with the higher probability.

12. The computer program product of claim 8 , wherein the program code instructions to provide for storage of the spatial boundary structure for the road link comprises program code instructions to:
identify a map tile associated with the road link based on an anchor node of the road link; and
provide for storage

Assignees

• Here Global Bv

Inventors

• Linder Eric
• Jang Dongwook
• Averbuch Alex

Classifications

• G06F16/29 Primary

  Geographical information databases · CPC title

• G01C21/32 Primary

  Structuring or formatting of map data · CPC title

• G01C21/3867

  Geometry of map features, e.g. shape points, polygons or for simplified maps · CPC title

• G01C21/3852

  Data derived from aerial or satellite images · CPC title

• G01C21/3881

  Tile-based structures · CPC title