Current Science

Open Access Open Access  Restricted Access Subscription Access

Three-Dimensional Point Cloud Segmentation Using a Combination of RANSAC and Clustering Methods


Affiliations
1 North Eastern Space Applications Centre, Department of Space, Government of India, Umiam 793 103, India
2 Department of Computer Science, St Anthony’s College, Shillong 793 001, India
 

There are challenges in performing 3D scene understanding on point clouds derived from drone images as these data are highly unstructured with no neighbouring information, highly redundant making the processing difficult and time-consuming and have variable density making it difficult to group and segment them. For proper scene understanding, these point clouds need to be segmented and classified into different groups representing similar characteristics. The approaches for segmentation differ based on the distinctiveness of each data product. Although newer machine learning-based approaches work well, they need large amounts of standardized labelled data which in turn require extensive resources and human intervention to obtain good results. Considering these, we have proposed a hybrid clustering-based hierarchical model for effective segmentation of dense 3D point cloud. We have applied the model to local data having a mix of man-made and natural vegetation with variable topography. The combination of RANSAC, DBSCAN and Euclidean method of cluster extraction proved to be useful for precise segmentation and classification of point clouds. The performance of the model has been assessed using Davies–Bouldin dbIndex-based intrinsic measures. The hybrid approach is able to segment 91% of the point clouds precisely compared to the conventional one-step clustering approach.

Keywords

Clustering, Drone Images, Hierarchical Model, Three-Dimensional Point Cloud, Segmentation.
User
Notifications
Font Size

  • Jiang, S., Jiang, C. and Jiang, W., Efficient structure from motion for large-scale UAV images: a review and a comparison of SfM tools. ISPRS J. Photogramm. Remote Sensing, 2020, 167, 230–251; ISSN 0924-2716, https://doi.org/10.1016/j.isprsjprs.2020.04.016.

  • Leal-Alves, D. C. et al., Digital elevation model generation using UAV-SfM photogrammetry techniques to map sea-level rise scenarios at Cassino Beach, Brazil. SN Appl. Sci., 2020, 2, 2181; https://doi.org/10.1007/s42452-020-03936-z.

  • Dey, T. K., Li, G. and Sun, J., Normal estimation for point clouds: a comparison study for a Voronoi based method. In Proceedings Eurographics/IEEE VGTC Symposium Point-Based Graphics, Stony Brook, New York, USA, 2005, pp. 39–46; doi:10.1109/PBG.2005.194062.

  • Zhao, R., Pang, M., Liu, C. and Zhang, Y., Robust normal estimation for 3D LiDAR point clouds in urban environments. Sensors, 2019, 19, 1248; https://doi.org/10.3390/s19051248.

  • Tarsha-Kurdi, F., Landes, T. and Grussenmeyer, P., Extended RANSAC algorithm for automatic detection of building roof planes from lidar data. Photogramm. J. Finland, 2008, 21, 97–109.

  • Fischler, M. A. and Bolles, R. C., Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM, 1981, 24, 381–395.

  • Kurban, R., Skuka, F. and Bozpolat, H., Plane segmentation of kinect point clouds using RANSAC. In 7th International Conference on Information Technology, Amman, Jordan, 2015.

  • Schnabel, R., Wahl, R. and Klein, R., Efficient RANSAC for point-cloud shape detection. Comput. Graph. Forum, 2007, 26, 214–226.

  • Ruzgiene, B. and Förstner, W., RANSAC for outlier detection. Geod. Kartogr., 2005, 31(3), 83–87; doi:10.1080/13921541.2005.9636670.

  • Li, L., Yang, F., Zhu, H., Li, D., Li, Y. and Tang, L., An improved RANSAC for 3D point cloud plane segmentation based on normal distribution transformation cells. Remote Sensing, 2017, 9, 433; https://doi.org/10.3390/rs9050433.

  • Wang, P., Gu, T., Sun, B., Huang, D. and Sun, K., Research on 3D point cloud data preprocessing and clustering algorithm of obstacles for intelligent vehicle. World Electr. Veh. J., 2022, 13, 130; https://doi.org/10.3390/wevj13070130.

  • Ahmed, S. M. and Chew, C. M., Density-based clustering for 3D object detection in point clouds. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, Seattle, WA, USA, 2020, pp. 10605–10614; doi:10.1109/CVPR42600.2020.01062.

  • Louhichi, S., Gzara, M. and Ben Abdallah, H., A density based algorithm for discovering clusters with varied density. In World Congress on Computer Applications and Information Systems, Hammamet, Tunisia, 2014, pp. 1–6; doi:10.1109/WCCAIS.2014.6916622.

  • Ester, M., Kriegel, H.-P., Sander, J. and Xu, X., A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, AAAI Press, Portland, Oregon, USA, 1996.

  • Davies, D. L. and Bouldin, D. W., A cluster separation measure. IEEE Trans. Pattern Anal. Mach. Intell., Pattern Analysis and Machine Intelligence-1, 1979, 2, 224–227.

  • Maulik, U. and Bandyopadhyay, S., Performance evaluation of some clustering algorithms and validity indices. IEEE Trans. Pattern Anal. Mach. Intell., 2002, 24(12), 1650–1654; doi:10.1109/TPAMI.2002. 1114856.

  • Wiroonsri, N., Clustering performance analysis using new correlation based cluster validity indices, 2021; arXiv preprint arXiv:2109.11172.


Abstract Views: 123

PDF Views: 70




  • Three-Dimensional Point Cloud Segmentation Using a Combination of RANSAC and Clustering Methods

Abstract Views: 123  |  PDF Views: 70

Authors

Puyam S. Singh
North Eastern Space Applications Centre, Department of Space, Government of India, Umiam 793 103, India
Iainehborlang M. Nongsiej
Department of Computer Science, St Anthony’s College, Shillong 793 001, India
Valarie Marboh
Department of Computer Science, St Anthony’s College, Shillong 793 001, India
Dibyajyoti Chutia
North Eastern Space Applications Centre, Department of Space, Government of India, Umiam 793 103, India
Victor Saikhom
North Eastern Space Applications Centre, Department of Space, Government of India, Umiam 793 103, India
S. P. Aggarwal
North Eastern Space Applications Centre, Department of Space, Government of India, Umiam 793 103, India

Abstract


There are challenges in performing 3D scene understanding on point clouds derived from drone images as these data are highly unstructured with no neighbouring information, highly redundant making the processing difficult and time-consuming and have variable density making it difficult to group and segment them. For proper scene understanding, these point clouds need to be segmented and classified into different groups representing similar characteristics. The approaches for segmentation differ based on the distinctiveness of each data product. Although newer machine learning-based approaches work well, they need large amounts of standardized labelled data which in turn require extensive resources and human intervention to obtain good results. Considering these, we have proposed a hybrid clustering-based hierarchical model for effective segmentation of dense 3D point cloud. We have applied the model to local data having a mix of man-made and natural vegetation with variable topography. The combination of RANSAC, DBSCAN and Euclidean method of cluster extraction proved to be useful for precise segmentation and classification of point clouds. The performance of the model has been assessed using Davies–Bouldin dbIndex-based intrinsic measures. The hybrid approach is able to segment 91% of the point clouds precisely compared to the conventional one-step clustering approach.

Keywords


Clustering, Drone Images, Hierarchical Model, Three-Dimensional Point Cloud, Segmentation.

References





DOI: https://doi.org/10.18520/cs%2Fv124%2Fi4%2F434-441