|
DOI: 10.14489/vkit.2025.08.pp.013-026
Глумова Е. С., Судаков О. В., Филинских А. Д., Дмитриев Д. В.
АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ ДЛЯ РАЗРЕЖИВАНИЯ ОБЛАКА ТОЧЕК С СОХРАНЕНИЕМ ГЕОМЕТРИИ ОБЪЕКТА
(с. 13-26)
Аннотация. Рассмотрено применение алгоритмов кластеризации для разреживания облаков точек для уменьшения объема данных при сохранении ключевой геометрической информации. В рамках исследования анализируются алгоритмы DBSCAN, OPTICS и k-means. Основное внимание уделено оценке эффективности алгоритмов сжатия облаков точек, содержащих миллионы элементов, с точки зрения сохранения структуры объекта и оптимизации вычислительных ресурсов. Результаты показывают, что несмотря на высокую точность некоторых алгоритмов (например, OPTICS и DBSCAN), их производительность ограничена по времени обработки и потреблению памяти, что делает их менее подходящими для работы с крупными наборами данных. Напротив, алгоритм G-Means продемонстрировал высокую эффективность в разреживании облаков точек, сохраняя при этом значимые геометрические особенности и обеспечивая приемлемую скорость обработки. Предложенный подход позволяет значительно уменьшить объем данных и сохранить достаточную точность для последующего моделирования и анализа. Актуальность проблемы обработки трехмерных неструктурированных данных для создания цифровых двойников обусловлена повышенным спросом на эффективные методы проектирования и моделирования объектов в различных отраслях промышленности, таких как строительство, проектирование, медицинская диагностика и др.
Ключевые слова: облако точек; кластеризация; прореживание облака точек; трехмерное моделирование; алгоритм G-Means.
Glumova E. S., Sudakov O. V., Filinskikh A. D., Dmitriev D. V.
CLUSTERING ALGORITHMS FOR POINT CLOUD RESAMPLING WITH OBJECT GEOMETRY RETENTION
(pp. 13-26)
Abstract. The application of clustering algorithms for resolving point clouds to reduce data size while retaining key geometric information is discussed. The algorithms such as DBSCAN, OPTICS, and k-means are analyzed. The focus is on evaluating the performance of algorithms for compressing point clouds containing millions of elements in terms of retaining object structure and optimizing computational resources. The results show that, despite the high accuracy of some algorithms such as OPTICS and DBSCAN, their performance is limited in terms of processing time and memory consumption, making them less suitable for large datasets. On the contrary, the G-Means algorithm has demonstrated high efficiency in resolving point clouds while retaining meaningful geometric features and providing acceptable processing speed. The proposed approach can significantly reduce the amount of data and maintain sufficient accuracy for subsequent modeling and analysis.The study was conducted using two examples: a power line support and an abandoned building. The G-Means algorithm reduced the point cloud file size by reducing the number of elements for both objects. The power line support point cloud originally had a more uniform structure, which allowed the rarefaction algorithm to remove more points with Object Geometry Retentions.The relevance of the problem of processing three dimensional unstructured data to create digital twins is due to the increased demand for efficient methods of designing and modeling of objects in various industries, such as construction, engineering, medical diagnostics, etc.
Keywords: Point cloud; Clustering; Point cloud resampling; 3D modeling; G-Means algorithm.
Е. С. Глумова, О. В. Судаков, А. Д. Филинских, Д. В. Дмитриев (Нижегородский государственный технический университет им. Р. Е. Алексеева, Нижний Новгород, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
E. S. Glumova, O. V. Sudakov, A. D. Filinskikh, D. V. Dmitriev (Nizhny Novgorod State Technical University named after R. E. Alekseev, Nizhny Novgorod, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Аксенов А. Ю. Модели и методы обработки и представления сложных пространственных объектов: дис. ... канд. техн. наук. Санкт-Петербург, 2015. 110 с.
2. Li G., Gao W, Gao W. Point Cloud Compression: Technologies and Standardization. Singapore: Springer Nature, 2024. 156 p.
3. Kalaiah A., Varshney A. Differential Point Rendering // Rendering Techniques 2001: Proceedings of the Eurographics Workshop. Vienna: Springer, 2001. P. 139–150.
4. Beliaevskii K. O. Generating Octrees from the Point Cloud in Conditions of Limited Random Access Memory Volume // St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunications and Control Systems. 2019. V. 12(4). P. 97–110. DOI: 10.18721/JCSTCS.12408
5. Ковеня А. С., Босяков С. М. Применение функциональных возможностей конечно-элементных программных комплексов для моделирования и расчета сетчатых оболочек // Вестник ГГТУ им. П. О. Сухого. 2007. № 3(30). С. 10–17.
6. Шаповалов Р. В. Методы структурного обучения в задачах совместной разметки: дис. ... канд. физ.-мат. наук. Москва, 2014. 119 с.
7. Pauly M., Gross M., Kobbelt L. P. Efficient Simplification of Point-sampled Surfaces // IEEE Visualization, 2002. VIS 2002. P. 163–170.
8. A Local Tangent Plane Distance-based Approach to 3D Point Cloud Segmentation via Clustering / H. Chen, T. Xie, M. Liang et al. // Pattern Recognition. 2023. V. 137. P. 12. DOI: 10.1016/j.patcog.2023.109307
9. Deep Learning-based 3D Point Cloud Classification: A Systematic Survey and Outlook / H. Zhang, C. Wang, S. Tian et al. // Displays. 2023. V. 79. P. 14. DOI: 10.1016/j.displa.2023.102456
10. Sheng H., Liu X., Zhang S. Saliency Analysis Based on Depth Contrast Increased // 2016 IEEE International Conference on Acoustics, Speech and Signal Processing. IEEE, 2016. P. 1347–1351.
11. SIEV-Net: A Structure-Information Enhanced Voxel Network for 3D Object Detection From LiDAR Point Clouds / C. Yu, J. Lei, B. Peng et al. // IEEE Transactions on Geoscience and Remote Sensing. 2022. V. 60. 5703711. P. 1–11. DOI: 10.1109/TGRS.2022.3174483
12. SVGA-Net: Sparse Voxel-Graph Attention Network for 3D Object Detection from Point Clouds / Q. He, Z. Wang, H. Zeng et al. // Proceedings of the AAAI Conference on Artificial Intelligence. 2022. V. 36(1). P. 870–878. DOI: 10.1609/aaai.v36i1.19969
13. Gelfand N., Ikemoto L., Rusinkiewicz S., Levoy M. Geometrically Stable Sampling for the ICP Algorithm // Fourth International Conference on 3D Digital Imaging and Modeling, 3DIM 2003. Banff, AB, Canada, 2003. P. 260–267. DOI: 10.1109/IM.2003.1240258
14. Dynamic Downsampling Algorithm for 3D Point Cloud Map Based on Voxel Filtering / W. Lyu, W. Ke, H. Sheng et al. // Applied Sciences. 2024. V. 14. DOI: 10.3390/app14083160
15. Xiao Z., Gao J., Wu D., Zhang L. Voxel Grid Downsampling for 3D Point Cloud Recognition // Modular Machine Tool & Automatic Manufacturing Technique. 2021. № 11. P. 43–47. DOI: 10.13462/j.cnki.mmtamt.2021.11.011
16. Daszykowski M., Walczak B., Massart D. L. Density-based Clustering for Exploration of Analytical Data //Analytical and Bioanalytical Chemistry. 2004. V. 380. P. 370–372.
17. OPTICS: Ordering Points to Identify the Clustering Structure / Ankerst M., Breunig M. M., Kriegel H. P., et al. // ACM SIGMOD Record. 1999. V. 28. P. 49–60.
18. Na S., Xumin L., Yong G. Research on K-Means Clustering Algorithm: An Improved k-Means Clustering Algorithm // 2010 Third International Symposium on Intelligent Information Technology and Security Informatics. IEEE, 2010. P. 63–67.
19. Javaheri A., Brites C., Pereira F., Ascenso J. A Generalized Hausdorff Distance Based Quality Metric for Point Cloud Geometry // 2020 Twelfth International Conference on Quality of Multimedia Experience. IEEE, 2020. P. 1–6.
20. Sudakov O. V., Dmitriev D. V. Comparison of G-Means Algorithms and Kohonen Network in Solving Clustering Problems // Graphicon – Conference on Computer Graphics and Vision. 2022. V. 32. P. 1147–1156.
21. Лемешко Б. Ю., Блинов П. Ю. Критерии проверки отклонения распределения от равномерного закона. Руководство по применению. Москва: ИНФРА-М, 2015. 183 С.
1. Aksenov, A. Yu. (2015). Models and methods for processing and representation of complex spatial objects [Candidate of Technical Sciences dissertation, Saint Petersburg]. [in Russian language]
2. Li, G., Gao, W., & Gao, W. (2024). Point cloud compression: Technologies and standardization. Springer Nature.
3. Kalaiah, A., & Varshney, A. (2001). Differential point rendering. In Rendering techniques 2001: Proceedings of the Eurographics Workshop (pp. 139–150). Springer.
4. Beliaevskii, K. O. (2019). Generating octrees from the point cloud in conditions of limited random access memory volume. St. Petersburg State Polytechnical University journal. Computer science. Telecommunications and control systems, 12(4), 97–110. https://doi.org/10.18721/JCSTCS.12408
5. Kovenya, A. S., & Bosyakov, S. M. (2007). Application of functional capabilities of finite-element software systems for modeling and calculation of lattice shells. Vestnik GGTU im. P. O. Sukhogo, (3), 10–17. [in Russian language]
6. Shapovalov, R. V. (2014). Methods of structural learning in joint labeling tasks [Candidate of Physical and Mathematical Sciences dissertation, Moscow]. [in Russian language]
7. Pauly, M., Gross, M., & Kobbelt, L. P. (2002). Efficient simplification of point-sampled surfaces. IEEE Visualization, 2002, 163–170.
8. Chen, H., Xie, T., Liang, M., et al. (2023). A local tangent plane distance-based approach to 3D point cloud segmentation via clustering. Pattern Recognition, 137, 109307. https://doi.org/10.1016/j.patcog.2023.109307
9. Zhang, H., Wang, C., Tian, S., et al. (2023). Deep learning-based 3D point cloud classification: A systematic survey and outlook. Displays, 79, 102456. https://doi.org/10.1016/j.displa.2023.102456
10. Sheng, H., Liu, X., & Zhang, S. (2016). Saliency analysis based on depth contrast increased. 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (pp. 1347–1351). IEEE.
11. Yu, C., Lei, J., Peng, B., et al. (2022). SIEV-Net: A structure-information enhanced voxel network for 3D object detection from LiDAR point clouds. IEEE Transactions on Geoscience and Remote Sensing, 60, 5703711. https://doi.org/10.1109/TGRS.2022.3174483
12. He, Q., Wang, Z., Zeng, H., et al. (2022). SVGA-Net: Sparse voxel-graph attention network for 3D object detection from point clouds. Proceedings of the AAAI Conference on Artificial Intelligence, 36(1), 870–878. https://doi.org/10.1609/aaai.v36i1.19969
13. Gelfand, N., Ikemoto, L., Rusinkiewicz, S., & Levoy, M. (2003). Geometrically stable sampling for the ICP algorithm. Fourth International Conference on 3D Digital Imaging and Modeling (pp. 260–267). https://doi.org/10.1109/IM.2003.1240258
14. Lyu, W., Ke, W., Sheng, H., et al. (2024). Dynamic downsampling algorithm for 3D point cloud map based on voxel filtering. Applied sciences, 14(8), 3160. https://doi.org/10.3390/app14083160
15. Xiao, Z., Gao, J., Wu, D., & Zhang, L. (2021). Voxel grid downsampling for 3D point cloud recognition. Modular machine tool & automatic manufacturing technique, (11), 43–47. https://doi.org/10.13462/j.cnki.mmtamt.2021.11.011
16. Daszykowski, M., Walczak, B., & Massart, D. L. (2004). Density-based clustering for exploration of analytical data. Analytical and Bioanalytical Chemistry, 380, 370–372.
17. Ankerst, M., Breunig, M. M., Kriegel, H. P., et al. (1999). OPTICS: Ordering points to identify the clustering structure. ACM SIGMOD Record, 28, 49–60.
18. Na, S., Xumin, L., & Yong, G. (2010). Research on K-means clustering algorithm: An improved k-means clustering algorithm. 2010 Third International Symposium on Intelligent Information Technology and Security Informatics (pp. 63–67). IEEE.
19. Javaheri, A., Brites, C., Pereira, F., & Ascenso, J. (2020). A generalized Hausdorff distance based quality metric for point cloud geometry. 2020 Twelfth International Conference on Quality of Multimedia Experience (pp. 1–6). IEEE.
20. Sudakov, O. V., & Dmitriev, D. V. (2022). Comparison of G-means algorithms and Kohonen network in solving clustering problems. Graphicon – Conference on Computer Graphics and Vision, 32, 1147–1156.
21. Lemeshko, B. Yu., & Blinov, P. Yu. (2015). Criteria for checking deviation of distribution from uniform law: Application guide. INFRA-M. [in Russian language]
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 700 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2025.08.pp.013-026
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 700 rubles. (including VAT 20%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2025.08.pp.013-026
and fill out the form
.
|
Current Issue
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»