Method and apparatus for deriving spatial properties of bus stops and traffic controls

• US 9,489,637 B2
• Filed: 04/29/2013
• Issued: 11/08/2016
• Est. Priority Date: 04/29/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Modica, Leo, Stenneth, Leon
• Primary Examiner(s): SITIRICHE, LUIS A
• Application Number:
  US13/872,439
• Publication Number:
  US 20140324748A1
• Time in Patent Office: 1,289 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/08 Learning methods
• 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
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles

Abstract

A method, apparatus and computer program products are provided for automatically detecting specific locations, i.e. bus stops, stop lights, and/or traffic signals, based on received GPS reports. The method can also be adopted to detect the utilization of the specific locations along the route. One example method includes receiving GPS data from a plurality of buses from along a transit route, and utilizes a machine learning classification strategy that captures the mobility patterns of the GPS equipped buses, at specific locations. The method may then generate mini-clusters, each comprised of a first location point from a first route and one or more subsequent location points located within a predetermined distance of the first location point. The mobility patterns of the mini-clusters within larger clusters are represented as a normalized histogram where the bin values become classification features. A machine learning model is then utilized to determine a location of the specific locations.

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 mini-clusters, each mini-cluster comprised of a first location point from a first set and one or more subsequent location points, wherein each subsequent location point is located within a predetermined distance of the first location point, wherein the first location point representing a center of the mini-cluster shifts as one or more additional location points are added to the mini-cluster;

generating a histogram for each of a plurality of clusters, each cluster of a predetermined distance and comprising one or more mini-clusters within the distance, wherein each bin of the histogram represents a fraction of a maximum cluster size;

generating a feature vector for each cluster, the feature vector comprising normalized values representing each of the bins of the histogram; and

distinguishing whether one or more clusters represent a specified object based on the feature vector.

2. The method of claim 1 wherein the determining step further comprises:

determining a location of the specified object by identifying one or more spatial or temporal patterns of the mini-clusters matching particular classification features of the specified object.

3. The method of claim 1 further comprising:

receiving training data from location reporting devices;

capturing classification features of training data;

training a detection model to detect a bus stop based on the captured classification features; and

wherein the distinguishing step applies the detection model to the feature vector to distinguish whether the feature vector represents the specified object.

4. The method of claim 1 further comprising calculating a speed between consecutive location points from a same set, and wherein the one or more classification features comprises a value representing a number of location points where the calculated speed is less than a predetermined threshold.

5. The method of claim 1 further comprising calculating an average speed across a cluster, wherein the one or more classification features comprises a value representing the average speed across the cluster.

6. The method of claim 1 further comprising calculating a confidence rating for each location indicative of whether the location is being utilized as the specified object at a given time.

7. The method of claim 1 further comprising presenting a map comprising one or more bus stops along a route.

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:

receive 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 mini-clusters, each mini-cluster comprised of a first location point from a first set and one or more subsequent location points, wherein each subsequent location point is located within a predetermined distance of the first location point, wherein the first location point representing a center of the mini-cluster shifts as one or more additional location points are added to the mini-cluster;

generate a histogram for each of a plurality of clusters, each cluster of a predetermined distance and comprising one or more mini-clusters within the distance, wherein each bin of the histogram represents a fraction of a maximum cluster size;

generate a feature vector for each cluster, the feature vector comprising normalized values representing each of the bins of the histogram; and

distinguish whether one or more clusters represent a specified object based on the feature vector.

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:

determine a location of the specified object by identifying one or more spatial or temporal patterns of the mini-clusters matching particular classification features of the specified object.

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:

receive training data from location reporting devices;

capture classification features of training data;

train a detection model to detect a bus stop based on the captured classification features; and

wherein the distinguishing step applies the detection model to the feature vector to distinguish whether the feature vector represents the specified object.

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 calculate a speed between consecutive location points from a same set, and wherein the one or more classification features comprises a value representing a number of location points where the calculated speed is less than a predetermined threshold.

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 an average speed across a cluster, wherein the one or more classification features comprises a value representing the average speed across the cluster.

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 calculate a confidence rating for each location indicative of whether the location is being utilized as the specified object at a given time.

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 present a map comprising one or more bus stops along a route.

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 mini-clusters, each mini-cluster comprised of a first location point from a first set and one or more subsequent location points, wherein each subsequent location point is located within a predetermined distance of the first location point, wherein the first location point representing a center of the mini-cluster shifts as one or more additional location points are added to the mini-cluster;

generating a histogram for each of a plurality of clusters, each cluster of a predetermined distance and comprising one or more mini-clusters within the distance, wherein each bin of the histogram represents a fraction of a maximum cluster size;

generating a feature vector for each cluster, the feature vector comprising normalized values representing each of the bins of the histogram; and

distinguishing whether one or more clusters represent a specified object based on the feature vector.

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

determining a location of the specified object by identifying one or more spatial or

temporal patterns of the mini-clusters matching particular classification features of the specified object.

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

receiving training data from location reporting devices;

capturing classification features of training data;

training a detection model to detect a bus stop based on the captured classification features; and

wherein the distinguishing step applies the detection model to the feature vector to distinguish whether the feature vector represents the specified object.

18. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for calculating a speed between consecutive location points from a same set, and wherein the one or more classification features comprises a value representing a number of location points where the calculated speed is less than a predetermined threshold.

19. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for calculating an average speed across a cluster, wherein the one or more classification features comprises a value representing the average speed across the cluster.

20. A computer program product according to claim 15, wherein the computer-executable program code portions further comprise program code instructions for calculating a confidence rating for each location indicative of whether the location is being utilized as the specified object at a given time.

21. A computer program product according to claim 15, wherein the computer executable program code portions further comprise program code instructions for presenting a map comprising one or more bus stops along a route.