Curvature-Based Change Detection in Road Segmentation: Ascending Hierarchical Clustering vs. K-Means - David Jaurès Fotsa-Mbogne; Addie Bernice Nguensie-Wakponou; Jean Michel Nlong; Marcellin Atemkeng; Maurice Tchuente (Mathematics)
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 <semantics>14.28</semantics> and a p-value of <semantics>9.77×10−7</semantics>. 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 <semantics>85.52%</semantics> and <semantics>87.48%</semantics>, true negative rate of <semantics>93.6%</semantics> and <semantics>93.73%</semantics>, accuracy of <semantics>84.18%</semantics> and <semantics>82.59%</semantics>, <semantics>κ</semantics>-coefficient of <semantics>84.18%</semantics> and <semantics>82.56%</semantics>, and Rand index of <semantics>86.33%</semantics> and <semantics>82.84%</semantics>. The average computational time for K-means is <semantics>333.1</semantics> s, compared to <semantics>0.312</semantics> 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.