Identification of new road segments using a modified version of k-means algorithm

The present work explains how to identify transformation and new road segments in existing electronic maps by using data coming from devices carried on board on different vehicles, by using a modified version of a standard clustering algorithm called k-means. The working dataset appears as sparse clouds of points with their centres over the road segments, including other different data. Because of the spatial distribution of the points and in order to allow the algorithm to converge in a short number of steps, a simple modification has been implemented. With respect to the standard k-means algorithm which works with a fixed number of clusters, the present modified version works with a large initial number of clusters, with sizes defined a priori on the basis of the smallest possible road segment The number of clusters is progressively reduced considering, for each steps, only the clusters including a number of points above a specific thresholds. At the end of the algorithm, all the identified clusters are superimposed over a common map in order to validate if a new road segment is identified. The algorithm has been applied on different datasets acquired on the road network of Turin with good results allowing the identification of new road segments not present in the reference map and one-way roads (change in travel direction).