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

• US 10,436,589 B2
• Filed: 08/04/2016
• Issued: 10/08/2019
• Est. Priority Date: 08/04/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dong, Wei Shan, Duan, Ning, Gao, Peng, Wang, Zhi Hu, Yan, Jun Chi
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): Greene, Daniel L
• Application Number:
  US15/228,515
• Publication Number:
  US 20180038693A1
• Time in Patent Office: 1,160 Days
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 21/30 Authentication, i.e. establishing the identity or authorisation of security principals

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 matched based on a distance and having a traveling direction consistent with the route directions; obtaining candidate transition points from the plurality of points on the digital map; aggregating the candidate transition points by applying a clustering algorithm to obtain a first cluster of points and a plurality of second clusters of points, verifying a confidence that the first cluster of points are transition points indicating a transition between the routes, and in response to the confidence being below a threshold confidence, classifying the first cluster of points as a first plurality of traveling points having a first direction and automatically adjusting the digital map at least in part based on the first cluster of points.

Claims

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, the traveling direction for each point of the plurality of points being saved as metadata;

identifying points of the plurality of points on the digital map that are matched to the stored route trajectory along the at least two of the plurality of routes based on a distance separating each point from the stored trajectory along the at least two of the plurality of routes being less than a first threshold and having a traveling direction consistent with the route directions of the stored trajectory along the at least two plurality of routes;

obtaining candidate transition points from the plurality of points on the digital map, the candidate transition points being points that are unmatched to the stored route trajectory along the at least two of the plurality of routes;

aggregating a plurality of candidate transition points by applying a clustering algorithm to obtain a first cluster of points and a plurality of second clusters of points, the clusters of points being obtained from one of positioning data obtained from a plurality of the traveling objects traveling on the plurality of routes or positioning data obtained from a single object traveling on the plurality of routes multiple times;

classifying the first cluster of points as transition points between the at least two plurality of routes or travelling points on one of the plurality of routes, based on verifying a confidence level, the confidence level being verified at least in part based on distances between the first cluster of points and the plurality of second clusters of points;

wherein

in response to verifying that the confidence level is below a threshold confidence, classifying the first cluster of points as a first plurality of traveling points having a first direction, and

in response to verifying that the confidence level is above the threshold confidence, classifying the first cluster of points as the transition points; and

automatically adjusting the stored route trajectory at least in part based on the classification of the first cluster of points.

2. The method of claim 1, wherein the verifying 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

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.

3. 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 the verifying 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;

determining a difference between the first and second travel distances; and

in response to the difference being below a threshold difference, determining that the confidence exceeds the threshold confidence.

4. 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.

5. The method of claim 4, 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.

6. The method of claim 1, wherein the unmatched points include at least one of the following:

points that are separated from the at least two of the plurality of routes by distances exceeding the first threshold distance, or

points having directions that are inconsistent with the route directions; and

selecting the candidate transition points from the unmatched points.

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, the traveling direction for each point of the plurality of points being saved as metadata;

identifying points of the plurality of points on the digital map that are matched to the stored route trajectory along the at least two of the plurality of routes based on a distance separating each point from the stored trajectory along the at least two of the plurality of routes being less than a first threshold and having a traveling direction consistent with the route directions of the stored trajectory along the at least two plurality of routes;

obtaining candidate transition points from the plurality of points on the digital map, the candidate transition points

being points that are unmatched to the stored route trajectory along the at least two of the plurality of routes

aggregating a plurality of candidate transition points by applying a clustering algorithm to obtain a first cluster of points and a plurality of second clusters of points, the clusters of points being obtained from one of positioning data obtained from a plurality of the traveling objects traveling on the plurality of routes or positioning data obtained from a single object traveling on the plurality of routes multiple times;

classifying the first cluster of points as transition points between the at least two plurality of routes or travelling points on one of the plurality of routes, based on verifying a confidence level, the confidence level being verified at least in part based on distances between the first cluster of points and the plurality of second clusters of points;

wherein

in response to verifying that the confidence level is below a threshold confidence, classifying the first cluster of points as a first plurality of traveling points having a first direction, and

in response to verifying that the confidence level is above the threshold confidence, classifying the first cluster of points as the transition points; and

automatically adjusting the stored route trajectory at least in part based on the classification of the first cluster of points.

9. The device of claim 8, wherein the verifying 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

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.

10. The device of claim 8, wherein the at least two plurality of routes at least include a first route and a second route having opposite directions, and wherein the verifying 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;

determining a difference between the first and second travel distances; and

in response to the difference being below a threshold difference, determining that the confidence exceeds the threshold confidence.

11. The device of claim 8, wherein the instructions further cause the device to:

adjusting the stored route trajectory on the map at least in part based on the classified first cluster of points.

12. The device of claim 8, further comprising a transition micro-clusters clustering module for aggregating the candidate transition points, a real transition micro-clusters detector module for verifying a confidence in identifying clusters of points as transition points and a label calibration and merge module for classifying the cluster of points.

13. The device of claim 8, 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.

14. The device of claim 13, wherein the instructions further cause the device to:

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.

15. The device of claim 8, wherein the unmatched points including at least one of the following:

points that are separated from the routes by distances exceeding the first threshold distance, or

points having directions that are inconsistent with the route directions; and

selecting the candidate transition points from the unmatched points.

16. The device of claim 15, wherein the instructions further cause the device to:

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.

17. A computer program product for tracking the route trajectory of a traveling object being tangibly stored on a non-transient machine-readable medium and comprising machine-executable instructions, the instructions, when executed on a device, causing the device to:

obtain positioning data from a positioning device carried on each of a respective at least one traveling object traveling on a plurality of routes;

map 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, the traveling direction for each point of the plurality of points being saved as metadata;

identify points of the plurality of points on the digital map that are matched to the stored route trajectory along the at least two of the plurality of routes based on a distance separating each point from the stored route trajectory along at least two of the plurality of routes being less than a first threshold and having a traveling direction consistent with the route directions of the stored trajectory along the at least two plurality of routes;

obtain candidate transition points from the plurality of points on the digital map, the candidate transition points

being points that are unmatched to the stored route trajectory along the at least two of the plurality of routes

aggregate a plurality of candidate transition points by applying a clustering algorithm to obtain a first cluster of points and a plurality of second clusters of points, the clusters of points being obtained from one of positioning data obtained from a plurality of the traveling objects traveling on the plurality of routes or positioning data obtained from a single object traveling on the plurality of routes multiple times;

classifying the first cluster of points as transition points between the at least two plurality of routes or travelling points on one of the plurality of routes, based on verifying a confidence level, the confidence level being verified at least in part based on distances between the first cluster of points and the plurality of second clusters of points;

wherein

in response to verifying that the confidence level is below a threshold confidence, classifying the first cluster of points as a first plurality of traveling points having a first direction, and

in response to verifying that the confidence level is above the threshold confidence, classifying the first cluster of points as the transition points; and

automatically adjusting the stored route trajectory at least in part based on the classification of the first cluster of points.

18. The computer program product of claim 17, wherein the instructions, when executed on the device, cause the device to:

select, 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

in response to the number of the selected clusters of points being below a threshold number, determine that the confidence is below the threshold confidence.