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

• US 10,429,189 B2
• Filed: 09/18/2018
• Issued: 10/01/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:
  US16/134,034
• Publication Number:
  US 20190017825A1
• Time in Patent Office: 378 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 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.

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;

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

11. 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 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;

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.

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

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

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

15. The device of claim 12, 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.

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

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.