Кластеризация пространственных данных с неявно выраженной полигональной структурой на основе топологических подходов

Введение. Кластеризация является одним из фундаментальных подходов для интеллектуального анализа данных, который в сфере геоинформатики и обработки изображений используется для поиска знаний и скрытых закономерностей пространственной информации. При автоматической векторизации объектов на спутниковых снимках из-за несовершенства этих технологий на линейных и полигональных объектах появляются пропущенные элементы, что препятствует полноценному анализу и визуализации данных. Представлен новый метод кластеризации геометрических примитивов с неявно выраженной полигональной структурой с возможностью устранения неполных данных в векторных моделях.

Метод. Предлагаемый метод основан на итерационном формировании пространственных структур при растяжении исходных объектов линейного типа. В отличие от многих подходов кластеризации элементы группируются в кластеры не по принципу ближайшего евклидова расстояния, а за счет определения ближайшего пересечения между отрезками. Такой подход позволяет корректно разделить рядом стоящие линейные объекты в разные кластеры. Для формирующихся пространственных структур на каждой итерации в зависимости от коэффициента растяжения вычисляются их топологические особенности, что обеспечивает возможность обнаруживать и проводить фильтрацию неявно выраженных полигональных структур.

Основные результаты. Разработанный метод апробирован для кластеризации линейных геометрических примитивов на векторных моделях городской инфраструктуры. Проведено сравнение работы метода с аналогами: k-средних, Density-Based Spatial Clastering of Application with Noise (DBSCAN) и агломеративной кластеризацией. Исследования показали, что с использованием метрики оценки качества кластеризации в виде индексов инерции и Жаккара предложенный метод имеет преимущество в случаях корректного разделения близко расположенных кластеров.

Обсуждение. Полученные результаты могут быть использованы в геоинформационных системах для актуализации векторных данных после применения технологий автоматической векторизации объектов на спутниковых снимках.

1. Воробьев А.В., Воробьева Г.Р. Геоинформационная система динамической пространственной кластеризации распределенных источников данных // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2023. № 64. С. 61–73. https://doi.org/10.17223/19988605/64/7

2. Еремеев С.В., Абакумов А.В., Андрианов Д.Е., Богоявленский И.В., Никонов Р.А. Обнаружение многолетних бугров пучения с использованием декомпозиции цифровых моделей рельефа по топологическим признакам // Современные проблемы дистанционного зондирования Земли из космоса. 2023. Т. 20. № 6. С. 129–143. https://doi.org/10.21046/2070-7401-2023-20-6-129-143

3. Еремеев С.В., Абакумов А.В., Андрианов Д.Е., Ширабакина Т.А. Метод векторизации спутниковых снимков на основе их разложения по топологическим особенностям // Информатика и автоматизация. 2023. Т. 22. № 1. С. 110–145. 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. V. 46. N 12. P. 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. V. 15. N 2. P. 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. V. 17. P. 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. V. 128. P. 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. N 5 (60). P. 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. V. 10. P. 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. V. 23. N 5. P. 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. V. 622. P. 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. P. 226–231.

13. Jang J.H., Hong K.S. Fast line segment grouping method for finding globally more favorable line segments // Pattern Recognition. 2002. V. 35. N 10. P. 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. V. 7. N 1. P. 8. https://doi.org/10.1145/1868237.1868246

15. Айдагулов Р.Р., Главацкий С.Т., Михалёв А.В. Модели кластеризации // Фундаментальная и прикладная математика. 2020. Т. 23. № 2. С. 17–36.

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. V. 36. N 8. P. 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. V. 11. P. 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. V. 28. N 4. P. 511–533. https://doi.org/10.1007/s00454-002-2885-2

19. Абакумов А.В., Еремеев С.В. Оценка возможности применения метода декомпозиции изображений по топологическим признакам для уменьшения энтропии при их сжатии // Научно-технический вестник информационных технологий, механики и оптики. 2023. Т. 23. № 6. С. 1152–1161. https://doi: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. V. 10. N 9. P. 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. V. 12. P. 11761–11773. https://doi.org/10.1109/ACCESS.2024.3350791