Automatic region-growing system for the segmentation of large point clouds

3D point cloud; RANSAC; Region-growing; Segmentation; Unsupervised clustering; Multilevels; Planar region; Point-clouds; Potential variations; Region growing; Scale-up; Control and Systems Engineering; Civil and Structural Engineering; Building and Construction

Abstract :

[en] This article describes a complete unsupervised system for the segmentation of massive 3D point clouds. Our system bridges the missing components that permit to go from 99% automation to 100% automation for the construction industry. It scales up to billions of 3D points and targets a generic low-level grouping of planar regions usable by a wide range of applications. Furthermore, we introduce a hierarchical multi-level segment definition to cope with potential variations in high-level object definitions. The approach first leverages planar predominance in scenes through a normal-based region growing. Then, for usability and simplicity, we designed an automatic heuristic to determine without user supervision three RANSAC-inspired parameters. These are the distance threshold for the region growing, the threshold for the minimum number of points needed to form a valid planar region, and the decision criterion for adding points to a region. Our experiments are conducted on 3D scans of complex buildings to test the robustness of the “one-click” method in varying scenarios. Labelled and instantiated point clouds from different sensors and platforms (depth sensor, terrestrial laser scanner, hand-held laser scanner, mobile mapping system), in different environments (indoor, outdoor, buildings) and with different objects of interests (AEC-related, BIM-related, navigation-related) are provided as a new extensive test-bench. The current implementation processes ten million points per minutes on a single thread CPU configuration. Moreover, the resulting segments are tested for the high-level task of semantic segmentation over 14 classes, to achieve an F1-score of 90+ averaged over all datasets while reducing the training phase to a fraction of state of the art point-based deep learning methods. We provide this baseline along with six new open-access datasets with 300+ million hand-labelled and instantiated 3D points at: https://www.graphics.rwth-aachen.de/project/45/.

Disciplines :

Computer science

Author, co-author :

Poux, Florent ; Université de Liège - ULiège > Département de géographie > Unité de Géomatique - Topographie et géométrologie

Mattes, C.; Visual Computing Institute, RWTH Aachen University, Germany

Selman, Z.; Visual Computing Institute, RWTH Aachen University, Germany

Kobbelt, L.; Visual Computing Institute, RWTH Aachen University, Germany

Language :

English

Title :

Automatic region-growing system for the segmentation of large point clouds

Alternative titles :

[fr] Système automatique de croissance de région pour la segmentation de larges nuages de points

Publication date :

04 June 2022

Journal title :

Automation in Construction

ISSN :

0926-5805

eISSN :

1872-7891

Publisher :

Elsevier B.V.

Volume :

138

Pages :

104250

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://api.elsevier.com/content/article/PII:S0926580522001236?httpAccept=text/xml

Name of the research project :

Terra Mosana

Funders :

ERDF - European Regional Development Fund
Interreg Europe

Funding text :

This work was funded by the European Regional Development Fund within the “Terra Mosana” project under the funding code EMR10 .

Data Set :

Large point cloud datasets

Large point cloud datasets for instance segmentation

Available on ORBi :

since 07 June 2022

Statistics

Number of views

126 (5 by ULiège)

Number of downloads

6 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Wang, Q., Kim, M.K., Applications of 3D point cloud data in the construction industry: A fifteen-year review from 2004 to 2018. Adv. Eng. Inform. 39 (2019), 306–319, 10.1016/j.aei.2019.02.007.
Xiong, X., Adan, A., Akinci, B., Huber, D., Automatic creation of semantically rich 3D building models from laser scanner data. Autom. Constr. 31 (2013), 325–337, 10.1016/j.autcon.2012.10.006.
Vanlande, R., Nicolle, C., Cruz, C., IFC and building lifecycle management. Autom. Constr. 18 (2008), 70–78, 10.1016/j.autcon.2008.05.001.
Liu, R., Asari, V.K., 3D indoor scene reconstruction and change detection for robotic sensing and navigation. Agaian, S.S., Jassim, S.A., (eds.) SPIE - the International Society for Optical Engineering, 2017, International Society for Optics and Photonics, 102210D, 10.1117/12.2262831.
Poux, F., Billen, R., Voxel-based 3D point cloud semantic segmentation: unsupervised geometric and relationship featuring vs deep learning methods. ISPRS Int. J. Geo Inf., 8, 2019, 213, 10.3390/ijgi8050213.
Schnabel, R., Wahl, R., Klein, R., Efficient RANSAC for point cloud shape detection. Computer Graphics Forum. 26 (2007), 214–226, 10.1111/j.1467-8659.2007.01016.x.
Qi, C.R., Yi, L., Su, H., Guibas, L.J., PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space, in: Conference on Neural Information Processing Systems (NIPS). 2017, Long Beach, United States http://arxiv.org/abs/1706.02413 (accessed March 13, 2018).
Landrieu, L., Simonovsky, M., Large-Scale Point Cloud Semantic Segmentation with Superpoint Graphs, in: Conference on Computer Vision and Pattern Recognition (CVPR), Salt Lake City, United States. 2018, 4558–4567, 10.1109/CVPR.2018.00479.
Thomas, H., Qi, C.R., Deschaud, J.E., Marcotegui, B., Goulette, F., Guibas, L., KPConv: Flexible and deformable convolution for point clouds. Proceedings of the IEEE International Conference on Computer Vision. 2019-Octob, 2019, 6410–6419, 10.1109/ICCV.2019.00651.
Choy, C., Gwak, J., Savarese, S., 4D spatio-temporal convnets: Minkowski convolutional neural networks. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2019, 3070–3079, 10.1109/CVPR.2019.00319.
Hu, Q., Yang, B., Xie, L., Rosa, S., Guo, Y., Wang, Z., Trigoni, N., Markham, A., RandLA-Net: Efficient semantic segmentation of large-scale point clouds. ArXiv, 2019, 11105–11114, 10.1109/CVPR42600.2020.01112.
Matrone, F., Lingua, A., Pierdicca, R., Malinverni, E.S., Paolanti, M., Grilli, E., Remondino, F., Murtiyoso, A., Landes, T., A Benchmark for Large-scale Heritage Point Cloud Semantic Segmentation. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences - ISPRS Archives, International Society for Photogrammetry and Remote Sensing, 2020, 1419–1426, 10.5194/isprs-archives-XLIII-B2-2020-1419-2020.
Obrist, A.F., Flisch, A., Hofmann, J., Point cloud reconstruction with sub-pixel accuracy by slice-adaptive thresholding of X-ray computed tomography images. NDT and E International. 37 (2004), 373–380, 10.1016/j.ndteint.2003.11.002.
Zhang, K., Bi, W., Zhang, X., Fu, X., Zhou, K., Zhu, L., A new Kmeans clustering algorithm for point cloud, international journal of hybrid information. Technology. 8 (2015), 157–170, 10.14257/ijhit.2015.8.9.16.
Biosca, J.M., Lerma, J.L., Unsupervised robust planar segmentation of terrestrial laser scanner point clouds based on fuzzy clustering methods. ISPRS J. Photogramm. Remote Sens. 63 (2008), 84–98, 10.1016/j.isprsjprs.2007.07.010.
Melzer, T., Non-parametric segmentation of ALS point clouds using mean shift. Journal of Applied Geodesy. 1 (2008), 159–170, 10.1515/jag.2007.018.
Strom, J., Richardson, A., Olson, E., Graph-based segmentation for colored 3D laser point clouds. IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 - Conference Proceedings, 2010, 2131–2136, 10.1109/IROS.2010.5650459.
Douillard, B., Underwood, J., Kuntz, N., Vlaskine, V., Quadros, A., Morton, P., Frenkel, A., On the Segmentation of 3D LIDAR Point Clouds, in: 2011 IEEE International Conference on Robotics and Automation. 2011, IEEE, Shangai, 1–8, 10.1109/ICRA.2011.5979818.
Grilli, E., Menna, F., Remondino, F., A review of point clouds segmentation and classification algorithms. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences - ISPRS Archives, 2017, 339–344, 10.5194/isprs-archives-XLII-2-W3–339-2017.
Rostami, R., Bashiri, F.S., Rostami, B., Yu, Z., A survey on data-driven 3D shape descriptors. Computer Graphics Forum. 00 (2018), 1–38, 10.1111/cgf.13536.
Xie, Y., Tian, J., Zhu, X.X., A Review of Point Cloud Semantic Segmentation. 2019, ArXiv.Org. http://arxiv.org/abs/1908.08854.
Kaiser, A., Ybanez Zepeda, J.A., Boubekeur, T., A survey of simple geometric primitives detection methods for captured 3D data. Computer Graphics Forum. 38 (2019), 167–196, 10.1111/cgf.13451.
Deschaud, J., A fast and accurate plane detection algorithm for large noisy point clouds using filtered normals and voxel growing. Symposium A Quarterly Journal In Modern Foreign Literatures, 2010 http://campwww.informatik.tu-muenchen.de/3DPVT2010/data/media/e-proceeding/papers/paper111.pdf.
Xiao, J., Zhang, J., Adler, B., Zhang, H., Zhang, J., Three-dimensional point cloud plane segmentation in both structured and unstructured environments. Robot. Auton. Syst. 61 (2013), 1641–1652, 10.1016/j.robot.2013.07.001.
Vo, A.V., Truong-Hong, L., Laefer, D.F., Bertolotto, M., Octree-based region growing for point cloud segmentation. ISPRS J. Photogramm. Remote Sens. 104 (2015), 88–100, 10.1016/j.isprsjprs.2015.01.011.
Dong, Z., Yang, B., Hu, P., Scherer, S., An efficient global energy optimization approach for robust 3D plane segmentation of point clouds. ISPRS International Journal of Photogrammetry and Remote Sensing. 137 (2018), 112–133, 10.1016/j.isprsjprs.2018.01.013.
Rabbani, T., Van den Heuvel, F.A., Vosselman, G., Segmentation of Point Clouds Using Smoothness Constraint, in: International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences - ISPRS Archives, Dresden. 2006, 248–253 http://www.isprs.org/proceedings/XXXVI/part5/paper/RABB_639.pdf (accessed May 28, 2013).
Nurunnabi, A., Belton, D., West, G., Robust Segmentation in Laser Scanning 3D Point Cloud Data, in: International Conference on Digital Image Computing Techniques and Applications. 2012, IEEE, Fremantle, WA, 1–8, 10.1109/DICTA.2012.6411672.
Tóvári, D., Pfeifer, N., Segmentation based robust interpolation - a new approach to laser data filtering. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences - ISPRS Archives, 36, 2005, 79–84.
Poux, F., Neuville, R., Nys, G.-A., Billen, R., 3D point cloud semantic modelling: integrated framework for indoor spaces and furniture. Remote Sens., 10, 2018, 1412, 10.3390/rs10091412.
Hough, P., METHOD AND MEANS FOR RECOGNIZING COMPLEX PATTERNS, US3069654A. http://www.google.com/patents/US3069654?printsec=description#v=onepage&q&f=false, 1960 (accessed April 19, 2021).
Ballard, D.H., Generalizing the Hough transform to detect arbitrary shapes. Pattern Recogn. 13 (1981), 111–122, 10.1016/0031-3203(81)90009-1.
Limberger, F.A., Oliveira, M.M., Real-time detection of planar regions in unorganized point clouds. Pattern Recogn. 48 (2015), 2043–2053, 10.1016/j.patcog.2014.12.020.
Borrmann, D., Elseberg, J., Lingemann, K., Nüchter, A., The 3D Hough Transform for Plane Detection in Point Clouds: A Review and a New Accumulator Design, 3D Research. vol. 02, 2011, 1–13, 10.1007/3DRes.02(2011)3.
Camurri, M., Vezzani, R., Cucchiara, R., 3D Hough transform for sphere recognition on point clouds: a systematic study and a new method proposal. Mach. Vis. Appl. 25 (2014), 1877–1891, 10.1007/s00138-014-0640-3.
Fischler, M.A., Bolles, R.C., Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24 (1981), 381–395, 10.1145/358669.358692.
Choi, S., Kim, T., Yu, W., Performance evaluation of RANSAC family, British Machine Vision Conference, BMVC 2009 - Proceedings. 24, 2009, 271–300, 10.5244/C.23.81.
Nguyen, H.L., Belton, D., Helmholz, P., Planar surface detection for sparse and heterogeneous mobile laser scanning point clouds. ISPRS J. Photogramm. Remote Sens. 151 (2019), 141–161, 10.1016/j.isprsjprs.2019.03.006.
Xu, B., Jiang, W., Shan, J., Zhang, J., Li, L., Investigation on the weighted RANSAC approaches for building roof plane segmentation from LiDAR point clouds. Remote Sens., 8, 2016, 5, 10.3390/rs8010005.
Sanchez, V., Zakhor, A., Planar 3D modeling of building interiors from point cloud data. International Conference on Image Processing (ICIP), 2012, IEEE, 1777–1780, 10.1109/ICIP.2012.6467225.
Li, L., Yang, F., Zhu, H., Li, D., Li, Y., Tang, L., An improved RANSAC for 3D point cloud plane segmentation based on normal distribution transformation cells. Remote Sens., 9, 2017, 433, 10.3390/rs9050433.
Boulch, A., Marlet, R., Fast and robust normal estimation for point clouds with sharp features. Eurographics Symposium on Geometry Processing. 31 (2012), 1765–1774, 10.1111/j.1467-8659.2012.03181. x.
Armeni, I., Sener, O., Zamir, A.R., Jiang, H., Brilakis, I., Fischer, M., Savarese, S., 3D Semantic Parsing of Large-Scale Indoor Spaces, in: Conference on Computer Vision and Pattern Recognition (CVPR), Las Vegas, United States. 2016, 1534–1543, 10.1109/CVPR.2016.170.
Lehtola, V., Kaartinen, H., Nüchter, A., Kaijaluoto, R., Kukko, A., Litkey, P., Honkavaara, E., Rosnell, T., Vaaja, M., Virtanen, J.-P., Kurkela, M., El Issaoui, A., Zhu, L., Jaakkola, A., Hyyppä, J., Comparison of the selected state-of-the-art 3D indoor scanning and point cloud generation methods. Remote Sens., 9, 2017, 796, 10.3390/rs9080796.
Kharroubi, A., Hajji, R., Billen, R., Poux, F., Classification and integration of massive 3d points clouds in a virtual reality (VR) environment, international archives of the photogrammetry, remote sensing and spatial. Inf. Sci. 42 (2019), 165–171, 10.5194/isprs-archives-XLII-2-W17-165-2019.
Bassier, M., Vergauwen, M., Poux, F., Point cloud vs. mesh features for building interior classification. Remote Sensing, 12, 2020, 2224, 10.3390/rs12142224.
Grilli, E., Poux, F., Remondino, F., Unsupervised object-based clustering in support of supervised point-based 3d point cloud classification. Int. Arch. Photogramm. Remote. Sens. Spat. Inf. Sci. XLIII-B2-2 (2021), 471–478, 10.5194/isprs-archives-xliii-b2-2021-471-2021.
Bengio, Y., Lecun, Y., Hinton, G., Deep learning for AI. Commun. ACM 64 (2021), 58–65, 10.1145/3448250.
Poux, F., Ponciano, J.J., Self-learning ontology for instance segmentation of 3d indoor point cloud. ISPRS, (eds.) International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2020, Copernicus Publications, Nice, 309–316, 10.5194/isprs-archives-XLIII-B2-2020-309-2020.