{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:20:43Z","timestamp":1761402043955,"version":"build-2065373602"},"reference-count":54,"publisher":"MDPI AG","issue":"21","license":[{"start":{"date-parts":[[2019,10,23]],"date-time":"2019-10-23T00:00:00Z","timestamp":1571788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Remote Sensing"],"abstract":"<jats:p>Point cloud segmentation for planar surface detection is a valid problem of automatic laser scans analysis. It is widely exploited for many industrial remote sensing tasks, such as LIDAR city scanning, creating inventories of buildings, or object reconstruction. Many current methods rely on robustly calculated covariance and centroid for plane model estimation or global energy optimization. This is coupled with point cloud division strategies, based on uniform or regular space subdivision. These approaches result in many redundant divisions, plane maladjustments caused by outliers, and excessive number of processing iterations. In this paper, a new robust method of point clouds segmentation, based on histogram-driven hierarchical space division, inspired by kd-tree is presented. The proposed partition method produces results with a smaller oversegmentation rate. Moreover, state-of-the-art partitions often lead to nodes of low cardinality, which results in the rejection of many points. In the proposed method, the point rejection rate was reduced. Point cloud subdivision is followed by resilient plane estimation, using Mahalanobis distance with respect to seven cardinal points. These points were established based on eigenvectors of the covariance matrix of the considered point cluster. The proposed method shows high robustness and yields good quality metrics, much faster than a FAST-MCD approach. The overall results indicate improvements in terms of plane precision, plane recall, under-, and the over- segmentation rate with respect to the reference benchmark methods. Plane precision for the S3DIS dataset increased on average by 2.6pp and plane recall- by 3pp. Both over- and under- segmentation rates fell by 3.2pp and 4.3pp.<\/jats:p>","DOI":"10.3390\/rs11212465","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T03:20:36Z","timestamp":1571973636000},"page":"2465","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Effective Planar Cluster Detection in Point Clouds Using Histogram-Driven Kd-Like Partition and Shifted Mahalanobis Distance Based Regression"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5632-9484","authenticated-orcid":false,"given":"Jakub","family":"Walczak","sequence":"first","affiliation":[{"name":"Institute of Information Technology, Lodz University of Technology, 90-924 \u0141\u00f3d\u017a, Poland"}]},{"given":"Tadeusz","family":"Poreda","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, Lodz University of Technology, 90-924 \u0141\u00f3d\u017a, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3786-7225","authenticated-orcid":false,"given":"Adam","family":"Wojciechowski","sequence":"additional","affiliation":[{"name":"Institute of Information Technology, Lodz University of Technology, 90-924 \u0141\u00f3d\u017a, Poland"}]}],"member":"1968","published-online":{"date-parts":[[2019,10,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Gruen, A., Baltsavias, E.P., and Henricsson, O. (1997). Extracting Artificial Surface Objects from Airborne Laser Scanner Data. Automatic Extraction of Man-Made Objects from Aerial and Space Images (II), Springer.","DOI":"10.1007\/978-3-0348-8906-3"},{"key":"ref_2","first-page":"245","article-title":"Impact of the method of registering Terrestrial Laser Scanning data on the quality of documenting cultural heritage structures","volume":"XL-5\/W7","author":"Kedzierski","year":"2015","journal-title":"ISPRS Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci."},{"key":"ref_3","first-page":"71","article-title":"Segmentation based building detection approach from LiDAR point cloud","volume":"20","author":"Ramiya","year":"2017","journal-title":"Egypt. J. Remote Sens. Space Sci."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Forczma\u0144ski, P., and Kutelski, K. (2018). Driver Drowsiness Estimation by Means of Face Depth Map Analysis. International Multi-Conference on Advanced Computer Systems, Springer.","DOI":"10.1007\/978-3-030-03314-9_34"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Lipinski, P., Lichy, K., and Santorek, J. (2018, January 11\u201314). Empirical research of autonomous robot control system. Proceedings of the IEEE 13th CSIT 2018, Lviv, Ukraine.","DOI":"10.1109\/STC-CSIT.2018.8526721"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ziolkowski, P., Szulwic, J., and Miskiewicz, M. (2018). Deformation Analysis of a Composite Bridge during Proof Loading Using Point Cloud Processing. Sensors, 18.","DOI":"10.3390\/s18124332"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"7032","DOI":"10.1109\/TGRS.2017.2738439","article-title":"Topologically Aware Building Rooftop Reconstruction From Airborne Laser Scanning Point Clouds","volume":"55","author":"Chen","year":"2017","journal-title":"IEEE Trans. Geosci. Remote Sens."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1109\/LGRS.2017.2785380","article-title":"Spectral Clustering of Straight-Line Segments for Roof Plane Extraction From Airborne LiDAR Point Clouds","volume":"15","author":"Zhang","year":"2018","journal-title":"IEEE Geosci. Remote Sens. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1163\/016918610X501291","article-title":"Efficient Representation in Three-Dimensional Environment Modeling for Planetary Robotic Exploration","volume":"24","author":"Vaskevicius","year":"2010","journal-title":"Adv. Robot."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Li, L., Yang, F., Zhu, H., Li, D., Li, Y., and Tang, L. (2017). An Improved RANSAC for 3D Point Cloud Plane Segmentation Based on Normal Distribution Transformation Cells. Remote Sens., 9.","DOI":"10.3390\/rs9050433"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Xu, B., Jiang, W., Shan, J., Zhang, J., and Li, L. (2016). Investigation on the Weighted RANSAC Approaches for Building Roof Plane Segmentation from LiDAR Point Clouds. Remote Sens., 8.","DOI":"10.3390\/rs8010005"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ni, H., Lin, X., Ning, X., and Zhang, J. (2016). Edge detection and feature line tracing in 3d-point clouds by analyzing geometric properties of neighborhoods. Remote Sens., 8.","DOI":"10.3390\/rs8090710"},{"key":"ref_13","unstructured":"Eckart, B., Kim, K., and Kautz, J. (2018). Fast and Accurate Point Cloud Registration using Trees of Gaussian Mixtures. arXiv."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1111\/cgf.13451","article-title":"A survey of simple geometric primitives detection methods for captured 3d data","volume":"Volume 38","author":"Kaiser","year":"2019","journal-title":"Computer Graphics Forum"},{"key":"ref_15","first-page":"99","article-title":"A Review on Point Cloud Semantic Segmentation Methods","volume":"26","author":"Lazarek","year":"2018","journal-title":"J. Appl. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1641","DOI":"10.1016\/j.robot.2013.07.001","article-title":"Three-dimensional Point Cloud Plane Segmentation in Both Structured and Unstructured Environments","volume":"61","author":"Xiao","year":"2013","journal-title":"Robot. Auton. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Douillard, B., Underwood, J., Kuntz, N., Vlaskine, V., Quadros, A., Morton, P., and Frenkel, A. (2011, January 9\u201313). On the segmentation of 3D LIDAR point clouds. Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China.","DOI":"10.1109\/ICRA.2011.5979818"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.isprsjprs.2015.01.011","article-title":"Octree-based region growing for point cloud segmentation","volume":"104","author":"Vo","year":"2015","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.isprsjprs.2016.01.001","article-title":"Octree-based segmentation for terrestrial LiDAR point cloud data in industrial applications","volume":"113","author":"Su","year":"2016","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"407","DOI":"10.14358\/PERS.76.4.407","article-title":"Automatic Segmentation of Lidar Data into Coplanar Point Clusters Using an Octree-Based Split-and-Merge Algorithm","volume":"76","author":"Wang","year":"2010","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0146-664X(82)90104-6","article-title":"Geometric modeling using octree encoding","volume":"19","author":"Meagher","year":"1982","journal-title":"Comput. Graph. Image Process."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.isprsjprs.2018.01.013","article-title":"An efficient global energy optimization approach for robust 3D plane segmentation of point clouds","volume":"137","author":"Dong","year":"2018","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional Binary Search Trees Used for Associative Searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Commun. ACM"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Granger, S., and Pennec, X. (2002, January 28\u201331). Multi-scale EM-ICP: A fast and robust approach for surface registration. Proceedings of the European Conference on Computer Vision, Copenhagen, Denmark.","DOI":"10.1007\/3-540-47979-1_28"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Phillips, J.M., Liu, R., and Tomasi, C. (2007, January 21\u201323). Outlier robust ICP for minimizing fractional RMSD. Proceedings of the Sixth International Conference on 3-D Digital Imaging and Modeling (3DIM 2007), Montreal, QC, Canada.","DOI":"10.1109\/3DIM.2007.39"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1377","DOI":"10.1177\/0278364912460895","article-title":"Fast and accurate scan registration through minimization of the distance between compact 3D NDT representations","volume":"31","author":"Stoyanov","year":"2012","journal-title":"Int. J. Robot. Res."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Liu, X., Zhang, X., Cheng, S., and Nguyen, T.B. (2016, January 19\u201321). A Novel Algorithm for Planar Extracting of 3D Point Clouds. Proceedings of the International Conference on Internet Multimedia Computing and Service, Xi\u2019an, China.","DOI":"10.1145\/3007669.3007746"},{"key":"ref_28","unstructured":"Hough, P.V.C. (1962). Method and Means for Recognizing Complex Patterns. (3,069,654), U.S. Patent."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0031-3203(81)90009-1","article-title":"Generalizing the Hough transform to detect arbitrary shapes","volume":"13","author":"Ballard","year":"1981","journal-title":"Pattern Recognit."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"2043","DOI":"10.1016\/j.patcog.2014.12.020","article-title":"Real-time detection of planar regions in unorganized point clouds","volume":"48","author":"Limberger","year":"2015","journal-title":"Pattern Recognit."},{"key":"ref_31","unstructured":"University of California, Merced (2015). Introduction to Computer Vision Fitting and Alignment, University of California, Merced."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Qian, X., and Ye, C. (2013, January 17\u201321). NCC-RANSAC: A fast plane extraction method for navigating a smart cane for the visually impaired. Proceedings of the 2013 IEEE International Conference on Automation Science and Engineering (CASE), Madison, WI, USA.","DOI":"10.1109\/CoASE.2013.6653929"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1016\/j.patcog.2014.10.014","article-title":"Outlier detection and robust normal-curvature estimation in mobile laser scanning 3D point cloud data","volume":"48","author":"Nurunnabi","year":"2015","journal-title":"Pattern Recognit."},{"key":"ref_34","unstructured":"Bovik, A. (2005). 4.5\u2014Image Noise Models. Handbook of Image and Video Processing, Communications, Networking and Multimedia, Academic Press. [2nd ed.]."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1198\/004017004000000563","article-title":"ROBPCA: A New Approach to Robust Principal Component Analysis","volume":"47","author":"Hubert","year":"2005","journal-title":"Technometrics"},{"key":"ref_36","unstructured":"Stahel, W. (1981). Robust Estimation: Infinitesimal Optimality and Covariance Matrix Estimators. [Ph.D. Thesis, ETH]."},{"key":"ref_37","unstructured":"Donoho, D.L. (1982). Breakdown Properties of Multivariate Location Estimators, Harvard University. Technical Report."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1080\/00401706.1999.10485670","article-title":"A fast algorithm for the minimum covariance determinant estimator","volume":"41","author":"Rousseeuw","year":"1999","journal-title":"Technometrics"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1062","DOI":"10.1080\/2150704X.2017.1349961","article-title":"Segmentation of building roofs from airborne LiDAR point clouds using robust voxel-based region growing","volume":"8","author":"Xu","year":"2017","journal-title":"Remote Sens. Lett."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11263-011-0437-z","article-title":"Fast approximate energy minimization with label costs","volume":"96","author":"Delong","year":"2012","journal-title":"Int. J. Comput. Vis."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Armeni, I., Sener, O., Zamir, A.R., Jiang, H., Brilakis, I., Fischer, M., and Savarese, S. (2016, January 27\u201330). 3D Semantic Parsing of Large-Scale Indoor Spaces. Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, USA.","DOI":"10.1109\/CVPR.2016.170"},{"key":"ref_42","first-page":"315","article-title":"The use of computer vision algorithms for automatic orientation of terrestrial laser scanning data","volume":"XLI-B3","author":"Markiewicz","year":"2016","journal-title":"ISPRS Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Walczak, J., and Wojciechowski, A. (2018, January 14\u201316). Clustering Quality Measures for Point Cloud Segmentation Tasks. Proceedings of the International Conference on Computer Vision and Graphics, Warsaw, Poland.","DOI":"10.1007\/978-3-030-00692-1_16"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1093\/comjnl\/7.4.308","article-title":"A Simplex Method for Function Minimization","volume":"7","author":"Nelder","year":"1965","journal-title":"Comput. J."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"4790","DOI":"10.1109\/TGRS.2016.2551546","article-title":"Robust Segmentation for Large Volumes of Laser Scanning Three-Dimensional Point Cloud Data","volume":"54","author":"Nurunnabi","year":"2016","journal-title":"IEEE Trans. Geosci. Remote Sens."},{"key":"ref_46","first-page":"9","article-title":"Shape distribution features for point cloud analysis &ndash; a geometric histogram approach on multiple scales","volume":"II-3","author":"Blomley","year":"2014","journal-title":"ISPRS Ann."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/j.jesp.2017.09.011","article-title":"Detecting multivariate outliers: Use a robust variant of the Mahalanobis distance","volume":"74","author":"Leys","year":"2018","journal-title":"J. Exp. Soc. Psychol."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1214\/088342307000000087","article-title":"High-breakdown robust multivariate methods","volume":"23","author":"Hubert","year":"2008","journal-title":"Stat. Sci."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.cag.2015.01.006","article-title":"Distinctive 2D and 3D features for automated large-scale scene analysis in urban areas","volume":"49","author":"Weinmann","year":"2015","journal-title":"Comput. Graph."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/j.patcog.2017.06.023","article-title":"Fast density clustering strategies based on the k-means algorithm","volume":"71","author":"Bai","year":"2017","journal-title":"Pattern Recognit."},{"key":"ref_51","unstructured":"Pei, J., Tseng, V.S., Cao, L., Motoda, H., and Xu, G. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. Advances in Knowledge Discovery and Data Mining, Springer."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Landrieu, L., and Martin, S. (2018, January 18\u201322). Large-scale Point Cloud Semantic Segmentation with Superpoint Graphs. Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2018), Salt Lake City, UT, USA.","DOI":"10.1109\/CVPR.2018.00479"},{"key":"ref_53","unstructured":"(2018, March 06). Rooms UZH Irchel Dataset. Available online: http:\/\/www.ifi.uzh.ch\/en\/vmml\/research\/datasets.html."},{"key":"ref_54","unstructured":"Department of Computer Science & Engineering in the University of Washington (1999). Lecture 15: Principal Component Partition, University of Washington College of Engineering."}],"container-title":["Remote Sensing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2072-4292\/11\/21\/2465\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:28:44Z","timestamp":1760189324000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2072-4292\/11\/21\/2465"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,23]]},"references-count":54,"journal-issue":{"issue":"21","published-online":{"date-parts":[[2019,11]]}},"alternative-id":["rs11212465"],"URL":"https:\/\/doi.org\/10.3390\/rs11212465","relation":{},"ISSN":["2072-4292"],"issn-type":[{"type":"electronic","value":"2072-4292"}],"subject":[],"published":{"date-parts":[[2019,10,23]]}}}