Curvature-Based Change Detection in Road Segmentation: Ascending Hierarchical Clustering vs. K-Means

This work addresses the challenge of low-cost road quality monitoring in the context of developing countries. Specifically, we focus on utilizing accelerometer data collected from smartphones as drivers traverse roads in their vehicles. Given the high frequency of data collection by accelerometers, the resulting large datasets pose a computational challenge for anomaly detection using supervised classification algorithms. To mitigate scalability issues, it is beneficial to first group the data into homogeneous continuous sections. This approach aligns with the broader problem of change detection in a finite sequence of data indexed by a totally ordered set, which could represent either a time series or a spatial trajectory. Curvature features are extracted and segmented through adapted Ascending Hierarchical Clustering (AHC) and K-means algorithms suited to sequential road data. Our goal is to segment roads into homogeneous sub-sections that can subsequently be labeled based on the level or type of irregularity. Using an analysis of variance (ANOVA) statistical test, we demonstrate that curvature features are effective for classification, with a Fisher value of 14.28 and a p-value of 9.77×10−7. We use two change detection algorithms: (1) Ascending Hierarchical Clustering (AHC) and (2) K-means. Based on the dataset and the number of classes, AHC and K-means achieve the following performance metrics, respectively: specificity of 85.52% and 87.48%, true negative rate of 93.6% and 93.73%, accuracy of 84.18% and 82.59%, κ-coefficient of 84.18% and 82.56%, and Rand index of 86.33% and 82.84%. The average computational time for K-means is 333.1 s, compared to 0.312 s for AHC, resulting in a ratio of 1070. Overall, AHC is significantly faster and achieves a better balance of performance compared to K-means.