Method and apparatus of data classification for routes in a digitized map

Patent metadata

Field	Value
Publication number	US-10429189-B2
Application number	US-201816134034-A
Country	US
Kind code	B2
Filing date	Sep 18, 2018
Priority date	Aug 4, 2016
Publication date	Oct 1, 2019
Grant date	Oct 1, 2019

Abstract

A method and system obtaining positioning data from an object traveling on a plurality of routes; mapping the data into a plurality of points on a digital map; identifying points that are unmatched to the stored route trajectory; obtaining candidate transition points from the unmatched points; aggregating the candidate transition points by applying a clustering algorithm; selecting a first cluster of points and a plurality of second clusters of points, determining a confidence level that the first cluster of points are transition points indicating a transition between the routes, classifying the first cluster of points as a first plurality of traveling points having a first direction in response to the confidence being below a threshold confidence and automatically adjusting the stored route trajectory to indicate that the first cluster of points are on the route trajectory.

First claim

What is claimed is:

1. A computer-implemented method for tracking the route trajectory of a traveling object comprising:
obtaining positioning data from a positioning device carried on each of a respective at least one traveling object traveling on a plurality of routes;
mapping the positioning data into a plurality of points on a digital map, the digital map including a stored route trajectory along at least two of the plurality of routes, the at least two plurality of routes having different route directions, each point of the plurality of points having a traveling direction indicated by the positioning data;
identifying points of the plurality of points on the digital map that are unmatched to the stored route trajectory along the at least two of the plurality of routes, the unmatched points being points separated from the routes by distances exceeding a first threshold distance, points located between the routes but inconsistent with the route directions, and points located on one of the routes but have directions inconsistent with the respective route directions;
obtaining candidate transition points from the plurality of unmatched points on the digital map;
aggregating the plurality of candidate transition points by applying a clustering algorithm;
selecting a first cluster of points and a plurality of second clusters of points from the aggregated clusters of points;
determining a confidence level of whether the first cluster of points are transition points indicating a transition between the at least two plurality of routes;
classifying the first cluster of points based on the confidence level; wherein
in response to the confidence level being below a threshold confidence, classifying the first cluster of points as a plurality of traveling points having a first direction; and
in response to the confidence level being above the threshold confidence, classifying the first cluster of points as the transition points; and

automatically adjusting the stored route trajectory based on the classification of the first cluster of points.

2. The method of claim 1 , wherein the first cluster of points are generated from positioning data obtained from a plurality of the traveling objects traveling on the plurality of routes and the plurality of second clusters of points are generated from positioning data obtained from a single object traveling on the plurality of routes multiple times.

3. The method of claim 1 , wherein determining a confidence level comprises selecting, from among the plurality of second clusters of points, clusters of points such that a distance between each of the selected clusters of points and the first cluster of points is below a second threshold distance, and wherein in response to the number of the selected clusters of points being below a threshold number, determining that the confidence is below the threshold confidence.

4. The method of claim 1 , wherein the at least two plurality of routes at least include a first route and a second route having opposite directions, and wherein determining a confidence level comprises:
determining a first travel distance from a first cluster of points to a predetermined reference transition along the first route, the predetermined reference transition representing a transition between the first and second routes;
determining a second travel distance from the predetermined reference transition to the first cluster of points along the second route; and
determining a difference between the first and second travel distances; and
wherein, in response to the difference being below a threshold difference, determining that the confidence level exceeds the threshold confidence.

5. The method of claim 1 , wherein the classifying comprises:
determining the first direction for the first plurality of traveling points by:
determining a dominant direction of a second plurality of traveling points with respect to the first cluster of points, a distance between each of the second plurality of traveling points and the first cluster of points being below a third threshold distance, the second plurality of traveling points representing movements along the plurality of routes; and
determining the first direction at least in part based on the dominant direction of the second plurality of traveling points.

6. The method of claim 5 , further comprising:
selecting, from among the second plurality of traveling points, a traveling point having a second direction other than the dominant direction; and
adjusting the second direction of the selected traveling point based on the dominant direction.

7. The method of claim 6 , further comprising:
in response to determining that one of the unmatched points is located on one of the at least two plurality of routes, classifying the unmatched point as a traveling point having the route direction of the located route.

8. A device for tracking the route trajectory of a traveling object comprising:
a processing unit;
a memory coupled to the processing unit and storing instructions thereon, the instructions, when executed by the processing unit, causing the device to perform:
obtaining positioning data from a positioning device carried on each of a respective at least one traveling object traveling on a plurality of routes;
mapping the positioning data into a plurality of points on a digital map, the digital map including a stored route trajectory along at least two of the plurality of routes, the at least two plurality of routes having different route directions, each point of the plurality of points having a traveling direction indicated by the positioning data;
identifying points of the plurality of points on the digital map that are unmatched to the stored route trajectory along the at least two of the plurality of routes, the unmatched points being points separated from the routes by distances exceeding a first threshold distance, points located between the routes but inconsistent with the route directions, and points located on one of the routes but have directions inconsistent with the respective route directions;
obtaining candidate transition points from the plurality of unmatched points on the digital map;
aggregating the plurality of candidate transition points by applying a clustering algorithm;
selecting a first cluster of points and a plurality of second clusters of points from the aggregated clusters of points;
determining a confidence level of whether the first cluster of points are transition points indicating a transition between the at least two plurality of routes;
classifying the first cluster of points based on the confidence level; wherein
in response to the confidence level being below a threshold confidence, classifying the first cluster of points as a plurality of traveling points having a first direction; and
in response to the confidence level being above the threshold confidence, classifying the first cluster of points as the transition points; and

automatically adjusting the stored route trajectory based on the classification of the first cluster of points.

9. The method of claim 8 , wherein the first cluster of points are generated from positioning data obtained from a plurality of the traveling objects traveling on the plurality of routes and the plurality of second clusters of points are generated from positioning data obtained from a single object traveling on the plurality of routes multiple times.

10. The device of claim 8 , wherein determining a confidence level comprises:
selecting, from among the plurality of second clusters of points, clusters of points such that a distance between each of the selected clusters of points and the first cluster of points is below a seco

Assignees

• IBM

Inventors

• Dong Wei Shan
• Duan Ning
• Gao Peng
• Wang zhi hu
• Yan jun chi

Classifications

• G06F16/29 Primary

  Geographical information databases · CPC title

• G01C21/30

  Map- or contour-matching · CPC title

• G06F16/9537

  Spatial or temporal dependent retrieval, e.g. spatiotemporal queries · CPC title

• G06F21/30

  Authentication, i.e. establishing the identity or authorisation of security principals · CPC title

• G01C21/005 Primary

  with correlation of navigation data from several sources, e.g. map or contour matching (G01C21/30 takes precedence) · CPC title