Method, apparatus, and computer program product for detecting changes in road traffic condition

Patent metadata

Field	Value
Publication number	US-10943474-B2
Application number	US-202016849688-A
Country	US
Kind code	B2
Filing date	Apr 15, 2020
Priority date	May 3, 2019
Publication date	Mar 9, 2021
Grant date	Mar 9, 2021

Abstract

A method, apparatus, and computer program product are provided for detecting changes in road traffic conditions based on vehicle probe data. Methods may include: receiving a plurality of probe data points; map-matching probe data points of the plurality of probe apparatuses to road segments of a candidate road of a road networks; for a plurality of time epochs, cluster probe speeds map-matched to road segments of the candidate road according to a clustering algorithm; establishing centroid speeds corresponding to clusters of probe speeds; spatially grouping said road segments according to probe-to-cluster mapping; and providing a road traffic condition change message in response to a difference between centroid speeds along the candidate road exceeding a predefined threshold, where the road traffic condition change message includes at least information about said road segment groups that correspond to said clusters.

First claim

That which is claimed:

1. A method for detecting changes in road traffic condition comprising:
receiving a plurality of probe data points, each probe data point received from a probe apparatus of a plurality of probe apparatuses;
map-matching probe data points of the plurality of probe apparatuses to road segments of a candidate road of a road network;
clustering probe speeds of probe data points map-matched to road segments of the candidate road to form probe data point clusters;
establishing centroid speeds corresponding to the probe data point clusters;
spatially grouping said road segments according to the probe data point clusters; and
providing a road traffic condition change message in response to a difference between centroid speeds along the candidate road satisfying a predefined threshold.

2. The method of claim 1 , wherein clustering probe speeds of probe data points map-matched to road segments of the candidate road to form probe data point clusters comprises:
calculating cluster variances using a set of pre-calculated binary tables;
minimizing a sum of at least two cluster variances in the set of pre-calculated binary tables; and
identifying clusters based on the minimized sum of at least two cluster variances.

3. The method of claim 2 , wherein the set of pre-calculated binary tables comprises a main binary table and a complementary binary table.

4. The method of claim 3 , wherein a predefined number of probe data points are identified for each cluster, wherein a dimension of said binary tables is established as 2{circumflex over ( )}(N−1), where N is the predefined number of probe data points.

5. The method of claim 1 , further comprising grouping consecutive road segments according to centroid speed correspondence.

6. The method of claim 5 , wherein the road traffic condition change message comprises centroid speeds of each group of consecutive road segments.

7. The method of claim 1 , wherein the method further comprises:
failing to establish a centroid speed corresponding to a cluster of probe speeds for a respective road segment in response to a number of probe data points corresponding to the road segment failing to satisfy a predetermined number.

8. The method of claim 1 , wherein the road traffic condition change message includes at least information about said road segment groups that correspond to said clusters.

9. An apparatus comprising processing circuitry and at least one memory including computer program code, the at least one memory and computer program code configured to, with the processing circuitry, cause the apparatus to at least:
receive a plurality of probe data points, each probe data point received from a probe apparatus of a plurality of probe apparatuses;
map-match probe data points of the plurality of probe apparatuses to road segments of a candidate road of a road network;
cluster probe speeds of probe data points map-matched to road segments of the candidate road to form probe data point clusters;
establish centroid speeds corresponding to the probe data point clusters;
spatially group said road segments according to the probe data point clusters; and
provide a road traffic condition change message in response to a difference between centroid speeds along the candidate road satisfying a predefined threshold.

10. The apparatus of claim 9 , wherein causing the apparatus to cluster probe speeds of probe data points map-matched to road segments of the candidate road to form probe data point clusters comprises causing the apparatus to:
calculate cluster variances using a set of pre-calculated binary tables;
minimize a sum of at least two cluster variances in the set of pre-calculated binary tables; and
identify clusters based on the minimized sum of at least two cluster variances.

11. The apparatus of claim 10 , wherein the set of pre-calculated binary tables comprises a main binary table and a complementary binary table.

12. The apparatus of claim 11 , wherein a predefined number of probe data points are identified for each cluster, wherein a dimension of said binary tables is established as 2{circumflex over ( )}(N−1), where N is the predefined number of probe data points.

13. The apparatus of claim 9 , wherein the apparatus is further caused to group consecutive road segments according to centroid speed correspondence.

14. The apparatus of claim 13 , wherein the road traffic condition change message comprises centroid speeds of each group of consecutive road segments.

15. The apparatus of claim 9 , wherein the apparatus is further caused to:
fail to establish a centroid speed corresponding to a cluster of probe speeds for a respective road segment in response to a number of probe data points corresponding to the road segment failing to satisfy a predetermined number.

16. The apparatus of claim 9 , wherein the road traffic condition change message includes at least information about said road segment groups that correspond to said clusters.

17. 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 configured to:
receive a plurality of probe data points, each probe data point received from a probe apparatus of a plurality of probe apparatuses;
map-match probe data points of the plurality of probe apparatuses to road segments of a candidate road of a road network;
cluster probe speeds of probe data points map-matched to road segments of the candidate road to form probe data point clusters;
establish centroid speeds corresponding to the probe data point clusters;
spatially group said road segments according to the probe data point clusters; and
provide a road traffic condition change message in response to a difference between centroid speeds along the candidate road satisfying a predefined threshold.

18. The computer program product of claim 17 , wherein the program code instructions to cluster probe speeds of probe data points map-matched to road segments of the candidate road to form probe data point clusters comprise program code instructions to:
calculate cluster variances using a set of pre-calculated binary tables;
minimize a sum of at least two cluster variances in the set of pre-calculated binary tables; and
identify clusters based on the minimized sum of at least two cluster variances.

19. The computer program product of claim 17 , wherein the set of pre-calculated binary tables comprises a main binary table and a complementary binary table.

20. The computer program product of claim 17 , wherein a predefined number of probe data points are identified for each cluster, wherein a dimension of said binary tables is established as 2{circumflex over ( )}(N−1), where N is the predefined number of probe data points.

Assignees

• Here Global Bv

Inventors

• Sheynman Arnold
• Radakovic Daniela
• Jackson Kyle

Classifications

• G08G1/0112

  from the vehicle, e.g. floating car data [FCD] · CPC title

• G08G1/0141 Primary

  for traffic information dissemination · CPC title

• G08G1/0133

  for classifying traffic situation · CPC title