Dissimilarity weighting for graph-based point cloud segmentation using local surface gradients

Abstract

Processing of 3D point cloud data is seen as a problem due to the difficulties of processing millions of unstructured points. The point cloud segmentation process is a crucial pre-classification stage such that it reduces the high processing time required to extract meaningful information from raw data and produces some distinctive features for the classification stage. Local surface inclinations of objects are the most effective features of 3D point clouds to provide meaningful information about the objects. Sampling the points into sub-volumes (voxels) is a technique commonly used in the literature to obtain the required neighboring point groups to calculate local surface directions (with normal vectors). The graph-based segmentation approaches are widely used for the surface segmentation using the attributes of the local surface orientations and continuities. In this study, only two geometrical primitives which are normal vectors and barycenters of point groups are used to weight the connections between the adjacent voxels (vertices). The defined 14 possible dissimilarity calculations of three angular values getting from the primitives are experimented and evaluated on five sample datasets that have reference data for segmentation. Finally, the results of the measures are compared in terms of accuracy and F1 score. According to the results, the weight measure W7 (seventh calculation) gives 0.8026 accuracy and 0.7305 F1 score with higher standard deviations, while the original weight measure (W8) of the segmentation method gives 0.7890 accuracy and 0.6774 F1 score with lower standard deviations.

Keywords

• Graph-based segmentation
• Normal vector
• Point cloud segmentation
• Surface gradients
• Weighting

References

1. S. Barnea ve S. Filin, “Segmentation of terrestrial laser scanning data using geometry and image information”, ISPRS Journal of Photogrammetry and Remote Sensing, c. 76, ss. 33–48, 2013, doi: 10.1016/j.isprsjprs.2012.05.001.
2. X. Zhu, H. Zhao, Y. Liu, Y. Zhao, ve H. Zha, “Segmentation and classification of range image from an intelligent vehicle in urban environment”, içinde IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 - Conference Proceedings, 2010, doi: 10.1109/IROS.2010.5652703.
3. M. Weinmann, B. Jutzi, S. Hinz, ve C. Mallet, “Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiers”, ISPRS Journal of Photogrammetry and Remote Sensing, c. 105, ss. 286–304, 2015, doi: 10.1016/j.isprsjprs.2015.01.016.
4. Y. Xu, W. Yao, S. Tuttas, L. Hoegner, ve U. Stilla, “Unsupervised Segmentation of Point Clouds From Buildings Using Hierarchical Clustering Based on Gestalt Principles”, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, c. 11, ss. 4270–4286, 2018, doi: 10.1109/JSTARS.2018.2817227.
5. A. V. Vo, L. Truong-Hong, D. F. Laefer, ve M. Bertolotto, “Octree-based region growing for point cloud segmentation”, ISPRS Journal of Photogrammetry and Remote Sensing, c. 104, ss. 88–100, 2015, doi: 10.1016/j.isprsjprs.2015.01.011.
6. F. Poux ve R. Billen, “Voxel-based 3D Point Cloud Semantic Segmentation: Unsupervised geometric and relationship featuring vs deep learning methods”, ISPRS International Journal of Geo-Information, 2019, doi: 10.3390/ijgi8050213.
7. Y. T. Su, J. Bethel, ve S. Hu, “Octree-based segmentation for terrestrial LiDAR point cloud data in industrial applications”, ISPRS Journal of Photogrammetry and Remote Sensing, c. 113, ss. 59–74, 2016, doi: 10.1016/j.isprsjprs.2016.01.001.
8. H. Samet, Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. 1989.

9. B. Peng, L. Zhang, ve D. Zhang, “A survey of graph theoretical approaches to image segmentation”, Pattern Recognition, c. 46, sayı 3, ss. 1020–1038, 2013.
10. P. F. Felzenszwalb ve D. P. Huttenlocher, “Efficient graph-based image segmentation”, International Journal of Computer Vision, c. 59, sayı 2, ss. 167–181, 2004.
11. A. Saglam ve N. A. Baykan, “Sequential image segmentation based on minimum spanning tree representation”, Pattern Recognition Letters, c. 87, ss. 155–162, Şub. 2017, doi: 10.1016/j.patrec.2016.06.001.
12. J. Strom, A. Richardson, ve E. Olson, “Graph-based segmentation for colored 3D laser point clouds”, içinde IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 - Conference Proceedings, 2010, ss. 2131–2136, doi: 10.1109/IROS.2010.5650459.
13. Y. Xu, S. Tuttas, ve U. Stilla, “Segmentation of 3D outdoor scenes using hierarchical clustering structure and perceptual grouping laws”, içinde 2016 9th IAPR Workshop on Pattern Recognition in Remote Sensing, PRRS 2016, 2017, doi: 10.1109/PRRS.2016.7867013.
14. A. Saglam, H. B. Makineci, N. A. Baykan, ve Ö. K. Baykan, “Boundary constrained voxel segmentation for 3D point clouds using local geometric differences”, Expert Systems with Applications, c. 157, s. 113439, Kas. 2020, doi: 10.1016/j.eswa.2020.113439.
15. T. Rabbani, F. van den Heuvel, ve G. Vosselman, “Segmentation of point clouds using smoothness constraint”, International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences - Commission V Symposium “Image Engineering and Vision Metrology”, c. 36, sayı 5, ss. 248–253, 2006, doi: 10.1111/1750-3841.12802.
16. F. Bergamasco, A. Albarelli, ve A. Torsello, “A graph-based technique for semi-supervised segmentation of 3D surfaces”, Pattern Recognition Letters, c. 33, ss. 2057–2064, 2012, doi: 10.1016/j.patrec.2012.03.015.
17. J. Shi ve J. Malik, “Normalized Cuts and Image Segmentation”, Ieee Transactions on Pattern Analysis and Machine Intelligence, c. 22, sayı 8, ss. 888–905, 2000, doi: 10.1109/34.868688.
18. A. Dutta, J. Engels, ve M. Hahn, “A distance-weighted graph-cut method for the segmentation of laser point clouds”, International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences - ISPRS Archives, c. 40, sayı 3, ss. 81–88, 2014, doi: 10.5194/isprsarchives-XL-3-81-2014.
19. G. Lohmann, Volumetric image analysis. Wiley, 1998.
20. Y. D. Jiang, “Set operations between linear octrees”, Computers and Geosciences, c. 22, sayı 5, ss. 509–516, 1996, doi: 10.1016/0098-3004(95)00118-2.
21. H. Medellín, J. Corney, J. B. C. Davies, T. Lim, ve J. M. Ritchie, “Algorithms for the physical rendering and assembly of octree models”, CAD Computer Aided Design, c. 38, sayı 1, ss. 69–85, 2006, doi: 10.1016/j.cad.2005.07.003.
22. N. J. MITRA, A. NGUYEN, ve L. GUIBAS, “Estimating surface normals in noisy point cloud data”, International Journal of Computational Geometry & Applications, c. 14, sayı 4–5, ss. 261–276, 2004, doi: 10.1142/s0218195904001470.
23. S. C. Stein, M. Schoeler, J. Papon, ve F. Worgotter, “Object partitioning using local convexity”, içinde Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2014, ss. 304–311, doi: 10.1109/CVPR.2014.46.
24. Y.-H. Tseng, K.-P. Tang, ve F.-C. Chou, “Surface Reconstruction from LiDAR Data with Extended Snake Theory”, 2007, ss. 479–492, doi: https://doi.org/10.1007/978-3-540-74198-5_37.
25. Y. Xu, W. Yao, S. Tuttas, L. Hoegner, ve U. Stilla, “Building-Segmentation-Reference-Dataset”, 2018. [Çevrimiçi]. Available at: https://github.com/Yusheng-Xu/Building-Segmentation-Reference-Dataset.
26. M. Awrangjeb ve C. S. Fraser, “An automatic and threshold-free performance evaluation system for building extraction techniques from airborne LIDAR data”, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, c. 7, sayı 10, ss. 4184–4198, 2014, doi: 10.1109/JSTARS.2014.2318694.