Road segmentation, clustering and abnormality detection

LAMBDA Road segmentation, clustering & abnormality detection Workshop on Un/Semi-supervised learning and Data Mining, 15/10/2019 [Ioannis Chamodrakas, NKUA] This project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 734242 LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Presentation Outline •Data Analysis Pipeline •Data Gathering •Road Segmentation Techniques & Analysis •Segment Clustering LSH for curves kMeans Curve Alignment •Driving Behaviour Abnormality Detection Velocity & Acceleration analysis The 3 sigma rule Analysis of abnormalities LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Data Analysis Pipeline GATHER DATA •ROAD SEGMENT + CONTEXT •DRIVING BEHAVIOUR DISCOVER ROAD SEGMENT CLUSTERS DRIVING BEHAVIOUR ABNORMALITY DETECTION •Open Street Map Network •Open GPX trajectories (Open Street Map) •Simulated GPX trajectories •k-Means •Discrete Fréchet •LSH for curves •Buckets as clusters •Alignment •c-RMSD •Fréchet minimization •Map matching •BMW Barefoot tool to connect GPX to segments and classes •Calculation of speed and acceleration stats •Statistical techniques •3 sigma rule •Segment-based detection •Cluster-based detection •Other techniques •Machine learning models •One class SVM •Subspace Outlier Detection Red fonts denote future work and experiments City Class 1 Highway Class 2 Class 3 Class 4 Class 5 ROAD SEGMENTATION •BY CURVATURE CHANGE •BY INTERSECTION •ACCORDING TO ROAD TYPE •Curvature •Radius of circumcircle •Rules •Lower bound to segment length •Lower bound to number of nodes •Consecutive intersections LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Data Gathering •Use of osm2pgsql tool 3.063.066 nodes (Paris network OSM file) 392.650 roads (A road is an ordered list of nodes) •Use of Google Maps Elevation API Elevation retrieval •Speed and Acceleration time series data From OSM public GPS traces Creation of simulated GPS traces Road Segmentation LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Road segmentation •Conversion from Geodesic to ECEF coordinates ECEF: Earth Centered-Earth Fixed coordinates right-handed Cartesian coordinate system •Standard algorithm for the conversion LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Road segmentation (cont.) •Road types High performance (motorway, trunk, primary, secondary, tertiary and link roads) Low performance (residential, unspecified) •Segmentation by curvature change •Curvature: Each set of three points forms a triangle with a circumcircle whose radius corresponds to the radius of the curve for that set. •Each straight line segment is part of two separate triangles: the smaller, larger, or average of the radii maybe selected. Average radius was selected in our research. •Segments are created when the change of curvature exceeds a certain threshold. •Used in motorway link, trunk link, primary link, secondary link and service road types. LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Road segmentation (cont.) •Segmentation by intersection •Produces road segments by checking the existence of intersections among the roads. •Disregard consecutive intersections •used in motorway, trunk, primary, secondary, tertiary and residential road types. •Upper bound for the number of nodes of a segment and its length. —𝑷 < 𝑯 𝑯 𝝆+𝟏 AND 𝝀 < 𝝁 P: the set of nodes of the segment. |P| denotes cardinality 𝜆: the length of the under construction segment. H: the set of nodes of the road which is divided to the segments. 𝜇: the mean length of all the roads that belong to the same category. 𝜌: a small positive number. LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Segmentation analysis •The plot shows the distribution of the road type on the map that it’s been used •Most of the roads are residential or service roads 2357 479 4821 411 350 208 5945 21944 14172 127 518 6375 LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Clustering segments – kMeans LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Clustering segments – kMeans (cont.) LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Clustering segments (cont.) •Alignment: translation and rotation of curves so as to: 1. Minimize c-RMSD (coordinate Root Mean Square Deviation). Given two sets of n points v and w, the cRMSD is defined as follows: 2. Minimize Discrete Fréchet Distance c- LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Clustering segments (cont.) •Find optimal number of clusters k by obtaining best Silhouette coefficients LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Clustering segments (cont.) LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Clustering segments results •Athens road network: Abnormality Detection LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Abnormality detection •Map matching •Barefoot tool to connect GPX to segments and classes •Calculation of speed and acceleration stats •Acceleration and velocity analysis per segment •The blue line shows the average speed (km/h) per segment. •The orange line shows the average acceleration (km/h) per segment. •We see that some segments have higher deviation than others. •The acceleration can also have negative values if the user is slowing down the speed. LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Abnormality detection (cont.) •Detailed velocity analysis •Average velocity (blue) vs. standard deviation (orange) plot •For sigma plot we used the following formula: 𝜎 = 𝐸 𝑋2− 𝐸 𝑋 2 •Only few roads (i.e. < 10) have high standard deviation (greater than 20 km/h) •The average velocity is 52 km/h, which is depicted on the plot. Some roads have high average velocity (might be highways) and others have smaller (within the city center) LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Abnormality detection (cont.) •Detailed acceleration analysis •The blue line shows the average acceleration values versus the standard deviation of the acceleration values. •The average standard deviation of the acceleration is higher for the acceleration attribute, which is also depicted on the acceleration values. •The acceleration can be also negative, if the person is slowing down. LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Future work (cont.) •The PRADO project aims at the creation of an integrated intelligent system for the evaluation of driving behavior in passenger transport and business fleets promoting security and efficiency. •The system will output a set of features characterizing and evaluating the driving behavior of each driver (driver profile). •An innovative telematics device for the measurement of speed, deceleration, acceleration and sharp turns in real time will be developed. •Driving behavior monitoring and evaluation will be visualized appropriately through an integrated visual environment. •The system will be piloted in the road assistance vehicle fleet of Interamerican which consists of more than 600 vehicles as well as in the privately owned buses of Ellinogermaniki Agogi for the transport of students, whose number currently exceeds 140 buses. LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 References •Research work has been performed in the context of the following undergraduate theses which were supervised by Professor Ioannis Emiris and Dr. Ioannis Chamodrakas: 1. D. Konstantakis, Geometrical Road Segmentation and Clustering, 2018 2. I. Troullinos, Abnormality Detection in Driving Behaviour, 2019. LAMBDA Workshop on Un/Semi-supervised learning and Data Mining, Paris, 14-15 October 2019 Discussion