Clustering of spatial data with implicit polygonal structure based on topological approaches

Clustering is one of the fundamental approaches for data mining, which in the field of geoinformatics and image processing is used to search for knowledge and hidden patterns of spatial information. During automatic vectorization of objects on satellite images due to imperfections of these technologies, missing elements appear on linear and polygonal objects, which prevent full-fledged data analysis and visualization. The paper considers the problem of clustering geometric primitives with implicit polygonal structure with the possibility of eliminating incomplete data in vector models. The proposed method is based on the iterative formation of spatial structures by stretching the original linear objects. Unlike many clustering approaches, elements are grouped into clusters not by the principle of nearest Euclidean distance, but by determining the nearest intersection between segments. This approach allows us correctly dividing adjacent objects into different clusters. For the spatial structures formed at each iteration, their topological features are calculated depending on the stretching coefficient, which makes it possible to detect and filter implicit polygonal structures. The developed method is tested for clustering of linear geometric primitives on vector models of urban infrastructure. The performance of the method is compared with its competitors: k-means, DBSCAN, and agglomerative clustering. The research has shown that using the clustering quality assessment metric in the form of inertia and Jaccard indices, the proposed method has an advantage due to the correct separation of closely located clusters.

1. Vorobev A.V., Vorobeva G.R. Geoinformation system for dynamic spatial clustering of distributed data sources. Tomsk State University Journal of Control and Computer Science, 2023, no. 64, pp. 61–73. (in Russian). https://doi.org/10.17223/19988605/64/7

2. Eremeev S.V., Abakumov A.V., Andrianov D.E., Bogoyavlensky I.V., Nikonov R.A. Detection of perennial heaving mounds in digital elevation model images using decomposition by topological features. Sovremennye problemy distantsionnogo zondirovaniya Zemli iz kosmosa, 2023, vol. 20, no. 6, pp. 129–143. (in Russian). https://doi.org/10.21046/2070-7401-2023-20-6-129-143

3. Eremeev S.V., Abakumov A.V., Andrianov D.E., Shirabakina T.A. Vectorization method of satellite images based on their decomposition by topological features. Informatics and Automation, 2023, vol. 22, no. 1, pp. 110–145. (in Russian). https://doi.org/10.15622/ia.22.1.5

4. Lin X., Zhou Y., Liu Y., Zhu C. A comprehensive review of image line segment detection and description: taxonomies, comparisons, and challenges. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024, vol. 46, no. 12, pp. 8074–8093. https://doi.org/10.1109/tpami.2024.3400881

5. Zhang C., He Y., Fraser C.S. Spectral clustering of straight-line segments for roof plane extraction from airborne LiDAR point clouds. IEEE Geoscience and Remote Sensing Letters, 2018, vol. 15, no. 2, pp. 267–271. https://doi.org/10.1109/LGRS.2017.2785380

6. Zang D., Wang J., Zhang X., Yu J. Semantic extraction of roof contour lines from airborne lidar building point clouds based on multidirectional equal-width banding. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2024, vol. 17, pp. 16316–16328. https://doi.org/10.1109/jstars.2024.3422973

7. Xin X., Huang W., Zhong S., Zhang M., Liu Z. Xie Z. Accurate and complete line segment extraction for large-scale point clouds. International Journal of Applied Earth Observation and Geoinformation, 2024, vol. 128, pp. 103728. https://doi.org/10.1016/j.jag.2024.103728

8. Miroshnichenko S.Yu., Titov V.S., Dremov E.N., Mosin S.A. Hough transform application to digitize rectangular spatial objects on aerospace imagery. SPIIRAS Proceedings, 2018, no. 5 (60), pp. 189–215. https://doi.org/10.15622/sp.60.7

9. Teplyakov L., Erlygin L., Shvets E. LSDNet: Trainable modification of LSD algorithm for real-time line segment detection. IEEE Access, 2022, vol. 10, pp. 45256–45265. https://doi.org/10.1109/ACCESS.2022.3169177

10. Shili H. Clustering in big data analytics: a systematic review and comparative analysis (review article). Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2023, vol. 23, no. 5, pp. 967–979. https://doi.org/10.17586/2226-1494-2023-23-5-967-979

11. Ikotun A.M., Ezugwu A.E., Abualigah L., Abuhaija B., Heming J. K-means clustering algorithms: a comprehensive review, variants analysis, and advances in the era of big data. Information Sciences, 2023, vol. 622, pp. 178–210. https://doi.org/10.1016/j.ins.2022.11.139

12. Ester M., Kriegel H.-P., Sander J., Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise. Proc. of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96), 1996, pp. 226–231.

13. Jang J.H., Hong K.S. Fast line segment grouping method for finding globally more favorable line segments. Pattern Recognition, 2002, vol. 35, no. 10, pp. 2235–2247. https://doi.org/10.1016/S0031-3203(01)00175-3

14. Gao J., Langberg M., Schulman L.J. Clustering lines in highdimensional space: Classification of incomplete data. ACM Transactions on Algorithms, 2010, vol. 7, no. 1, pp. 8. https://doi.org/10.1145/1868237.1868246

15. Aidagulov R.R., Glavatsky S.T., Mikhalev A.V. Clustering models. Journal of Mathematical Sciences, 2022, vol. 262, no. 5. pp. 603–616. (in Russian). https://doi.org/10.1007/s10958-022-05841-9

16. Kang Y., Wu K., Gao S., Ng I., Rao J., Ye S., Zhang F., Fei T. STICC: a multivariate spatial clustering method for repeated geographic pattern discovery with consideration of spatial contiguity. International Journal of Geographical Information Science, 2022, vol. 36, no. 8, pp. 1518–1549. https://doi.org/10.1080/13658816.2022.2053980

17. Alomari H.W., Al-Badarneh A.F., Al-Alaj A., Khamaiseh S.Y. Enhanced approach for agglomerative clustering using topological relations. IEEE Access, 2023, vol. 11, pp. 21945–21967. https://doi.org/10.1109/access.2023.3252374

18. Edelsbrunner H., Letscher H., Zomorodian A. Topological persistence and simplification. Discrete & Computational Geometry, 2002, vol. 28, no. 4, pp. 511–533. https://doi.org/10.1007/s00454-002-2885-2

19. Abakumov A.V., Eremeev S.V. Assessing the possibility of using the method of image decomposition based on topological features to reduce entropy during their compression. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2023, vol. 23, no. 6, pp. 1152–1161. (in Russian). https://doi.org/10.17586/2226-1494-2023-23-6-1152-1161

20. Xu F., Beard K. A unifying framework for analysis of spatial-temporal event sequence similarity and its applications. ISPRS International Journal of Geo-Information, 2021, vol. 10, no. 9, pp. 594. https://doi.org/10.3390/ijgi10090594

21. Rykov A., De Amorim R.C., Makarenkov V., Mirkin B. Inertia-based indices to determine the number of clusters in K-Means: an experimental evaluation. IEEE Access, 2024, vol. 12, pp. 11761–11773. https://doi.org/10.1109/ACCESS.2024.3350791