Method and apparatus for providing a machine learning approach for a point-based map matcher

Patent metadata

Field	Value
Publication number	US-10060751-B1
Application number	US-201715597999-A
Country	US
Kind code	B1
Filing date	May 17, 2017
Priority date	May 17, 2017
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

An approach is provided for point-based map matchers using machine learning. The approach involves retrieving points collected within proximity to a map feature represented by a link of a geographic database. The probe points are collected from sensors of devices traveling near the map feature. The approach also involves determining a probe feature set for each probe point comprising probe attribute values, and determining a link feature set for the link comprising link attribute values. The apparatus further involves classifying, using a machine learning classifier, each probe point to determine a matching probability based on the probe feature set and the link feature to indicate a probability that each probe point is classified as map-matched to the link. The machine learning classifier is trained using ground truth data comprising reference probe points with known map-matches to respective reference links, and comprising known probe attribute values and known link attribute values.

First claim

What is claimed is:

1. A computer-implemented method for map-matching probe data using a machine learning classifier, comprising:
retrieving one or more probe points collected within a proximity to a map feature represented by a link of a geographic database, wherein the one or more probe points are collected from one or more sensors of a plurality of devices traveling within the proximity to the map feature;
determining a probe feature set for each of the one or more probe points, wherein the probe feature set comprises respective values for one or more probe attributes of said each probe point;
determining a link feature set for the link, wherein the link feature set comprises respective values for one or more link attributes of the link;
classifying, using the machine learning classifier, said each probe point to determine a matching probability based on the probe feature set, the link feature, and one or more combined link and probe attributes,
wherein the one or more combined link and probe attribute include a perpendicular distance between said each probe point and the link, an angle difference between a heading of said each probe point and a bearing of the link, a ratio of a speed of said each probe point and a median speed of the link, or a combination thereof,
wherein the matching probability indicates a probability that said each probe point is classified as map-matched to the link; and
wherein the machine learning classifier is trained using ground truth data comprising reference probe points with known map-matches to respective reference links, and comprising known values of the one or more probe attributes for the reference probe points, known values of the one or more link attributes for the reference links, and known values of the one or more combined link and probe attributes for the reference probe points and the reference links.

2. The method of claim 1 , further comprising:
dividing the one or more probe points into a map-matched set and an unmatched set by applying a threshold value on the matching probability for said each probe point.

3. The method of claim 1 , further comprising:
processing the unmatched set of the one or more probe points to identify a new geometry, a map attribute, or a combination thereof of a transportation network represented in the geographic database.

4. The method of claim 1 , further comprising:
calibrating the matching probability based a classifier type of the machine learning classifier.

5. The method of claim 1 , further comprising:
extracting the probe feature set from location sensor data of said each probe point.

6. The method of claim 1 , further comprising:
extracting the link feature set from the geographic database.

7. The method of claim 1 , wherein the proximity to the map feature is determined by an area delimited by a radius extending from a vertex of the link.

8. The method of claim 1 , further comprising:
creating a hash map that associates each pair of said each probe point and the link respectively with a corresponding one of the probe feature set and the link feature set; and
maintaining the hash map in a memory of the machine learning classifier during the classifying of the one or more probe points.

9. An apparatus for map-matching probe data using a machine learning classifier, comprising:
at least one processor; and
at least one memory including computer program code for one or more programs,
the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,
retrieve one or more probe points collected within a proximity to a map feature represented by a link of a geographic database, wherein the one or more probe points are collected from one or more sensors of a plurality of devices traveling within the proximity to the map feature;
determine a probe feature set for each of the one or more probe points, wherein the probe feature set comprises respective values for one or more probe attributes of said each probe point;
determine a link feature set for the link, wherein the link feature set comprises respective values for one or more link attributes of the link;
classify, using the machine learning classifier, said each probe point to determine a matching probability based on the probe feature set the link feature, and one or more combined link and probe attributes,
wherein the one or more combined link and probe attribute include a perpendicular distance between said each probe point and the link, an angle difference between a heading of said each probe point and a bearing of the link, a ratio of a speed of said each probe point and a median speed of the link, or a combination thereof,
wherein the matching probability indicates a probability that said each probe point is classified as map-matched to the link; and
wherein the machine learning classifier is trained using ground truth data comprising reference probe points with known map-matches to respective reference links, and comprising known values of the one or more probe attributes for the reference probe points, known values of the one or more link attributes for the reference links, and known values of the one or more combined link and probe attributes for the reference probe points and the reference links.

10. The apparatus of claim 9 , wherein the apparatus is further caused to:
divide the one or more probe points into a map-matched set and an unmatched set by applying a threshold value on the matching probability for said each probe point.

11. The apparatus of claim 9 , wherein the apparatus is further caused to:
process the unmatched set of the one or more probe points to identify a new geometry, a map attribute, or a combination thereof of a transportation network represented in the geographic database.

12. The apparatus of claim 9 , wherein the proximity to the map feature is determined by an area delimited by a radius extending from a vertex of the link.

13. The apparatus of claim 9 , wherein the apparatus is further caused to:
create a hash map that associates each pair of said each probe point and the link respectively with a corresponding one of the probe feature set and the link feature set; and
maintain the hash map in a memory of the machine learning classifier during the classifying of the one or more probe points.

14. A non-transitory computer-readable storage medium for map-matching probe data using a machine learning classifier, carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:
retrieving one or more probe points collected within a proximity to a map feature represented by a link of a geographic database, wherein the one or more probe points are collected from one or more sensors of a plurality of devices traveling within the proximity to the map feature;
determining a probe feature set for each of the one or more probe points, wherein the probe feature set comprises respective values for one or more probe attributes of said each probe point;
determining a link feature set for the link, wherein the link feature set comprises respective values for one or more link attributes of the link;
classifying, using the machine learning classifier, said each probe point to determine a matching probability based on the probe feature set, the link feature, and one or more combined link and probe attributes,
wherein the one or more combined link and probe attribute include a perpendicular distance between said each probe point and the link, an angle difference

Assignees

• Here Global Bv

Inventors

• Chen Qin
• Ballesteros Jaime

Classifications

• G06F16/29

  Geographical information databases · CPC title

• G06N20/00

  Machine learning · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06N99/005

  Physics · mapped topic