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

Patent metadata

Field	Value
Publication number	US-11860911-B2
Application number	US-201916545232-A
Country	US
Kind code	B2
Filing date	Aug 20, 2019
Priority date	Aug 20, 2019
Publication date	Jan 2, 2024
Grant date	Jan 2, 2024

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 a traveling object traveling on an overall route including a first route segment in a first direction, a second route segment in a second direction, the second route segment being different from the first route segment;
mapping the positioning data into a plurality of points on a digital map, the digital map including a stored route trajectory of the overall route along the first route segment and the second route segment;
identifying points of the plurality of points on the digital map that are unmatched to the stored route trajectory of the overall route along the first route segment and the second route segment;
obtaining candidate transition points corresponding to the traveling object travelling on a third route segment transitioning between the first route segment and the second route segment from the plurality of unmatched points on the digital map, the candidate transition points being between the first and second route segments and in directions different from the first and second directions;
aggregating the plurality of candidate transition points by applying a clustering algorithm;
classifying a first cluster of points from the aggregated cluster of points as being transition points corresponding to the traveling object travelling on the third route segment transitioning between the first route segment and the second route segment based on a confidence level being above a first threshold; and
automatically adjusting the stored route trajectory of the overall route based on the classification of the first cluster of points as transition points corresponding to the traveling object travelling on the third route segment transitioning between the first route segment and the second route segment.

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

3. The method of claim 2 , further comprising selecting, from among the plurality of second clusters of points, proximate clusters of points in which a distance between each of the selected plurality of second clusters of points and the first cluster of points is below a second threshold distance, and wherein in response to a number of the selected proximate clusters of points being above a threshold number, verifying that the first cluster of points are transition points.

4. The method of claim 1 , further comprising determining a first travel distance from the first cluster of points to a predetermined reference transition along the first route, the predetermined reference transition representing a transition between the first route and the second route;
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, verifying that the first cluster of points are transition points.

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

6. The method of claim 5 , further comprising:
selecting, from among the 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 5 , further comprising:
in response to determining that one of the unmatched points is located on one of the first route and the second route, classifying the unmatched point as a traveling point having the route direction of the located route.

8. The method of claim 1 , wherein the unmatched points are points separated from the first route or the second route by distances exceeding a first threshold distance, points located between the first route or the second route but inconsistent with the route directions, and points located on one of the first route or the second route but have directions inconsistent with the respective route directions.

9. 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 a traveling object traveling on an overall route including a first route segment in a first direction, a second route segment in a second direction, the second route segment being different from the first route segment;
mapping the positioning data into a plurality of points on a digital map, the digital map including a stored route trajectory of the overall route along the first route segment and the second route segment;
identifying points of the plurality of points on the digital map that are unmatched to the stored route trajectory of the overall route along the first route segment and the second route segment;
obtaining candidate transition points corresponding to the traveling object travelling on a third route segment transitioning between the first route segment and the second route segment from the plurality of unmatched points on the digital map, the candidate transition points being between the first and second route segments and in directions different from the first and second directions;
aggregating the plurality of candidate transition points by applying a clustering algorithm;
classifying a first cluster of points from the aggregated cluster of points as being transition points corresponding to the traveling object travelling on the third route segment transitioning between the first route segment and the second route segment based on a confidence level being above a first threshold; and
automatically adjusting the stored route trajectory of the overall route based on the classification of the first cluster of points as transition points corresponding to the traveling object travelling on the third route segment transitioning between the first route segment and the second route segment.

10. The device of claim 9 , further comprising selecting a plurality of second clusters of points from the aggregated cluster of points, and wherein the first cluster of points are generated from positioning data obtained from a plurality of the traveling objects traveling on the first route and the second route and the plurality of second clusters are generated from positioning data obtained from a singl

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/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/3484

  Personalized, e.g. from learned user behaviour or user-defined profiles · CPC title

• G06F18/24137

  Distances to cluster centroïds · CPC title

• G06F18/23

  Clustering techniques · CPC title