Method and apparatus for transit mapping

• US 8,855,921 B2
• Filed: 02/28/2013
• Issued: 10/07/2014
• Est. Priority Date: 02/28/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Modica, Leo, Stenneth, Leon
• Primary Examiner(s): Zanelli, Michael J
• Application Number:
  US13/781,188
• Publication Number:
  US 20140244154A1
• Time in Patent Office: 586 Days
• US Class Current: 701/410
• 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/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G08G 1/123 indicating the position of vehicles, e.g. scheduled vehicles; Managing passenger vehicles circulating according to a fixed timetable, e.g. buses, trains, tramstransmission of navigation instructions to vehicles G08G1/0968

Abstract

A method, apparatus and computer program products are provided for collecting and analyzing route to determine the routes of a transit system. One example method includes receiving GPS data from a plurality of buses or uses from along a transit roué, the discreet GPS reports organized into a set, generating a plurality of clusters, each cluster is comprised of a first GPS point from a first set and one or more subsequent GPS points, each subsequent GPS point from a different set, and wherein each subsequent GPS point is located within a predetermined distance of the first GPS point. The clusters are then connected to form a route polylines. Outliers, inaccuracies, and/or route endpoints may be pruned to improve accuracy and efficiency of the method. The method may also order the aggregated clusters using spatial and temporal data of the GPS reports to improve accuracy.

Claims

1. A method comprising:

causing reception of location data, wherein the location data is organized into a plurality of sets, each set comprised of a plurality of location points;

generating a plurality of clusters, each cluster is comprised of a first location point from a first set and one or more subsequent location points, each subsequent location point from a different set, wherein each subsequent location point is located within a predetermined distance of the first location point; and

aggregating, using a processor, the clusters by connecting two or more clusters to form a route polyline.

2. The method of claim 1 further comprising pruning the plurality of clusters based on a number of location points within the cluster.

3. The method of claim 1 further comprising pruning the two largest clusters.

4. The method of claim 1 further comprising determining a number of points in each of the plurality of clusters and aggregating only those clusters comprising greater than a threshold number of location points from the one or more different sets within a predetermined distance of a first point.

5. The method of claim 1 further comprising calculating a center point of a cluster as a moving average of each of the points included in the cluster, wherein the aggregating step connects the center points of a plurality of cluster to form route polylines.

6. The method of claim 1 further comprising ordering the aggregated data utilizing temporal data and spatial data of at least one location point in each of two or more clusters.

7. The method of claim 1 further comprising comparing the route polylines to map data;

and adjusting the route polylines according to the map data.

8. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the processor, cause the apparatus to at least:

cause reception of location data, wherein the location data is organized into a plurality of sets, each set comprised of a plurality of location points;

generate a plurality of clusters, each cluster is comprised of a first location point from a first set and one or more subsequent location points, each subsequent location point from a different set, wherein each subsequent location point is located within a predetermined distance of the first location point;

cause aggregation of the clusters by connecting two or more clusters to form a route polyline.

9. An apparatus according to claim 8, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to prune the plurality of clusters based on a number of location points within the cluster.

10. An apparatus according to claim 8, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to prune the two largest clusters.

11. An apparatus according to claim 8, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to:

determine a number of points in each of the plurality of clusters; and

cause aggregation of only those clusters comprising greater than a threshold number of location points from the one or more different sets within a predetermined distance of a first point.

12. An apparatus according to claim 8, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to calculate a center point of a cluster as a moving average of each of the points included in the cluster, wherein the aggregating step connects the center points of a plurality of cluster to form route polylines.

13. An apparatus according to claim 8, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to order the aggregated data utilizing temporal data and spatial data of at least one location point in each of two or more clusters.

14. An apparatus according to claim 8, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to compare the route polylines to map data;

and

adjust the route polylines according to the map data.

15. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions for:

causing reception of location data, wherein the location data is organized into a plurality of sets, each set comprised of a plurality of location points;

generating a plurality of clusters, each cluster is comprised of a first location point from a first set and one or more subsequent location points, each subsequent location point from a different set, wherein each subsequent location point is located within a predetermined distance of the first location point; and

aggregating, using a processor, the clusters by connecting two or more clusters to form a route polyline.

16. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for:

pruning the plurality of clusters based on a number of location points within the cluster.

17. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for pruning the two largest clusters.

18. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for determining a number of points in each of the plurality of clusters and aggregating only those clusters comprising greater than a threshold number of location points from the one or more different sets within a predetermined distance of a first point.

19. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for calculating a center point of a cluster as a moving average of each of the points included in the cluster, wherein the aggregating step connects the center points of a plurality of cluster to form route polylines.

20. A computer program product according to claim 15, wherein ordering the aggregated data utilizing temporal data and spatial data of at least one location point in each of two or more clusters.

21. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for comparing the route polylines to map data;

and adjusting the route polylines according to the map data.