Adaptive Clustering for Point Cloud
<p>The workflow of large-scale scene segmentation based on the adaptive clustering method. Sample 42 provided by ISPRS is used as an example.</p> "> Figure 2
<p>Flowchart of normal vector calculation.</p> "> Figure 3
<p>Flowchart of computation bound.</p> "> Figure 4
<p>Flowchart of cluster merging.</p> "> Figure 5
<p>Study data distribution. White points are the original large scene study area, blue points are the medium scene study area, and red points are the small scene study area.</p> "> Figure 6
<p>The normal vector pointing of the whole study data. A normal vector is drawn at an interval of 6 points.</p> "> Figure 7
<p>The normal vector pointing distribution of each block. The purple area is the border area, the blue area is the forest area, and the red area is the regular area.</p> "> Figure 8
<p>High-density point distribution. The red points comprise more than 30 adjacent points within 4 times the average density, and the blue points comprise the other points in the scene, except for the high-density points.</p> "> Figure 9
<p>Initial clustering results. Different colors represent different clusters.</p> "> Figure 10
<p>Classification results of point clouds. Panel (<b>a</b>) is the initial classification results of a certain number of point clouds, and different colors represent different clusters; panel (<b>b</b>) is the three-dimensional boundary of preliminary clusters, and the red bounding box indicates the same cluster class; panel (<b>c</b>) is the classification results with scatter points; panel (<b>d</b>) is the boundary distribution of clusters.</p> "> Figure 11
<p>The result of low-density clustering points and merged clustering points. Panel (<b>a</b>) shows the distribution of elimination points; the blue points are scattered points, and the red points are points with a certain density. Panel (<b>b</b>) shows the distribution of segmentation results; the black points are elimination points.</p> "> Figure 12
<p>The clustering results after removing the low-density clustering point cloud blocks. Panel (<b>a</b>) shows the distribution of the clustering points after removing the low-density clustering point cloud blocks; panel (<b>b</b>) shows the boundary after removing the low-density clustering point cloud.</p> "> Figure 13
<p>Low-density clustering results. Panel (<b>a</b>) shows the low-density point cloud clustering results; panel (<b>b</b>) shows the low-density point cloud clustering boundary.</p> "> Figure 14
<p>The merged clustering point cloud and its boundary. Panel (<b>a</b>) shows the distribution of clustering points, and panel (<b>b</b>) shows the boundary of the clustering points.</p> "> Figure 15
<p>The remaining scatter distribution. The black points are the completed cluster segmentation points, and the red points are the cluster scatter points.</p> "> Figure 16
<p>The final segmentation result.</p> "> Figure 17
<p>Euclidean clustering segmentation results for the small scene. Panels (<b>a</b>,<b>c</b>,<b>e</b>) show scatter distribution maps using 2 m, 2.5 m, and 3 m clustering thresholds, respectively; panels (<b>b</b>,<b>d</b>,<b>f</b>) show the cluster top views using 2 m, 2.5 m, and 3 m clustering thresholds. The black line shows the outer contour of the clustering result, and the red line box shows the area with a poor classification result.</p> "> Figure 18
<p>Region growth segmentation results for the small scene. The red box shows the area with a poor classification result. Panel (<b>a</b>) shows the distribution of clustering points, and panel (<b>b</b>) shows the boundary of the clustering points.</p> "> Figure 19
<p>Segmentation result map of the proposed method for the small scene. The red box shows the area with a poor classification result, the blue box shows the eliminated discrete points, and the black line is the outer contour of the clustering result. Panel (<b>a</b>) shows the distribution of clustering points, and panel (<b>b</b>) shows the boundary of the clustering points.</p> "> Figure 20
<p>Segmentation side view of the proposed method for the small scene. The red box shows the disputed area.</p> "> Figure 21
<p>Euclidean clustering segmentation results for the medium scene. Panels (<b>a</b>,<b>c</b>,<b>e</b>) show the scatter distribution maps using 1.5 m, 2 m, and 3 m clustering thresholds, respectively; panels (<b>b</b>,<b>d</b>,<b>f</b>) show the cluster top views using 1.5 m, 2 m, and 3 m clustering thresholds. The black line is the outer contour of the clustering result, and the red line box shows the area with a poor classification result.</p> "> Figure 22
<p>Region-growing method segmentation results for the medium scene. Panel (<b>a</b>) shows a scatter plot, and panel (<b>b</b>) shows a cluster top view. The black line is the boundary of the clustering result, and the red box indicates the area with a poor classification result.</p> "> Figure 23
<p>Euclidean clustering segmentation results for the large scene. Panels (<b>a</b>,<b>c</b>,<b>e</b>) show the scatter distribution maps using 1.5 m, 2 m, and 2.5 m clustering thresholds, respectively; panels (<b>b</b>,<b>d</b>,<b>f</b>) show the cluster top views using 1.5 m, 2 m, and 2.5 m clustering thresholds. The black line is the outer contour of the clustering result, and the red line box shows the area with a poor classification result.</p> "> Figure 24
<p>Region-growing segmentation results for the large scene. Panel (<b>a</b>) shows a scatter plot, and panel (<b>b</b>) shows a cluster top view. The black line is the boundary of the clustering result, and the red box indicates the area with a poor classification result.</p> "> Figure 25
<p>Segmentation result map of the proposed method for the large scene. Panel (<b>a</b>) shows the clustering plots, and panel (<b>b</b>) shows a cluster top view. The black line is the boundary of the clustering result. Panel (<b>c</b>) is the boundary of the clustering result.</p> "> Figure 26
<p>Distributions of samples 1, 2, 3, and 4.</p> "> Figure 27
<p>Distributions of samples 5 and 6.</p> "> Figure 28
<p>Segmentation error of each sample area using the Euclidean clustering method. The black point is the correct segmented point cloud, the red point is the under-segmented point cloud, and the blue point is the over-segmented point cloud.</p> "> Figure 29
<p>Segmentation error of each sample area using the region-growing method. The black point is the correct segmented point cloud, the red point is the under-segmented point cloud, and the blue point is the over-segmented point cloud.</p> "> Figure 30
<p>Segmentation error of each sample area using our method. The black point is the correct segmented point cloud, the red point is the under-segmented point cloud, and the blue point is the over-segmented point cloud.</p> "> Figure 31
<p>Comparison of error ratios. Panel (<b>a</b>) shows a comparison chart of Euclidean clustering and the regional-growing method, panel (<b>b</b>) shows a comparison chart of Euclidean clustering and our method, and panel (<b>c</b>) shows a comparison chart of the region-growing method and our method.</p> "> Figure 32
<p>Small-scene segmentation results with different constant coefficients. Panels (<b>a</b>,<b>c</b>,<b>e</b>) show the split scatter plots with constant coefficients of 2, 3, and 4, respectively; panels (<b>b</b>,<b>d</b>,<b>f</b>) show the segmented top view with constant coefficients of 2, 3, and 4. The black lines are the outer contours of different cluster points.</p> "> Figure 33
<p>Medium-scene segmentation results with different constant coefficients. Panels (<b>a</b>,<b>c</b>,<b>e</b>) show split scatter plots with constant coefficients of 2, 3, and 4, respectively; panels (<b>b</b>,<b>d</b>,<b>f</b>) show the segmented top view with constant coefficients of 2, 3, and 4. The black lines show the outer contours of different cluster points.</p> "> Figure 34
<p>Clustering segmentation results of ground points of different samples. The black points are the correct segmented ground points, the red points are the under-segmented ground points, and the blue points are the over-segmented ground points.</p> ">
Abstract
:1. Introduction
2. Materials and Methods
2.1. Normal Vector Calculations
2.2. Adaptive Clustering Method
2.3. Boundary Construction
Algorithm 1 Pseudo-code of boundary construction. |
1. Initialize P = {P1,P2,...Pn} as target cluster set |
2. project all points onto a two-dimensional coordinate system |
3. find the x coordinate extreme point in the projection two-dimensional coordinate system: xmin = min{xi},xmax = max{xi}, and find the y coordinate extreme point: ymin = min{yi},ymax = max{yi}, get four points: Pta(xmin,ya), Ptb(xb,ymax), Ptc(xmax,yc), Ptd(xd,ymin); these four points are convex hull vertices. |
4. Let Pt1 and Pta, Pt2 and Ptb, Pt3 and Ptc, Pt4 and Ptd exchange coordinates, connect four points counterclockwise, and construct the initial convex hull P1,P2,P3,P4. |
5. if the points are in the initial convex hull then |
6. remove the points from the point set of the outer contour to be judged |
7. end if |
8. divide the remaining point set into multiple subsets in order |
9. obtain the convex hull vertices of each subset by Graham algorithm |
10. use Graham algorithm to judge the outer contour of the subset to generate the final convex hull |
11. Return OP-the outermost point of each cluster point |
2.4. Cluster Merging
3. Experimentation
3.1. Study Data
3.2. Experimental Process
3.3. Analysis of Our Method
4. Discussion
- (1)
- How can adaptive clustering segmentation be realized?
- (2)
- Where can the proposed method be used?
- (3)
- What are the shortcomings?
5. Conclusions
- (1)
- Although the overall segmentation effect of the method proposed in this paper is good, the normal vector of the point cloud is calculated using the adjacent point in the calculation process; therefore, the normal vector of the boundary part of the scene object has a large deflection, and it is easy to eliminate the boundary points from the clustering in the calculation process of the clustering threshold.
- (2)
- In the adaptive clustering method proposed in this paper, only a simple formula for computing positive and negative ratios is used. We plan to fit and verify parameters from multiple test areas and use ablation studies to evaluate the impact of key components and then compute the relation.
Author Contributions
Funding
Data Availability Statement
Acknowledgments
Conflicts of Interest
References
- Chen, X.; Jia, D.; Zhang, W. Integrating UAV photogrammetry and terrestrial laser scanning for three-dimensional geometrical modeling of post-earthquake county of Beichuan. In Proceedings of the 18th International Conference on Computing in Civil and Building Engineering: ICCCBE 2020, São Paulo, Brazil, 18–20 August 2021; Springer International Publishing: Cham, Switzerland, 2021; pp. 1086–1098. [Google Scholar]
- Kang, C.; Lin, Z.; Wu, S.; Yang, J.; Zhang, S.; Zhang, S.; Li, X. Method to Solve Underwater Laser Weak Waves and Superimposed Waves. Sensors 2023, 23, 6058. [Google Scholar] [CrossRef]
- Wang, H.; Zhang, Y.; Liu, W.; Gu, X.; Jing, X.; Liu, Z. A novel GCN-based point cloud classification model robust to pose variances. Pattern Recognit. 2022, 121, 108251. [Google Scholar] [CrossRef]
- Wang, X.; Yang, J.; Kang, Z.; Du, J.; Tao, Z.; Qiao, D. A category-contrastive guided-graph convolutional network approach for the semantic segmentation of point clouds. IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens. 2023, 16, 3715–3729. [Google Scholar] [CrossRef]
- Xu, Y.; Tong, X.; Stilla, U. Voxel-based representation of 3D point clouds: Methods, applications, and its potential use in the construction industry. Autom. Constr. 2021, 126, 103675. [Google Scholar] [CrossRef]
- Ruan, X.; Liu, B. Review of 3d point cloud data segmentation methods. Int. J. Adv. Netw. Monit. Control. 2020, 5, 66–71. [Google Scholar] [CrossRef]
- Grilli, E.; Menna, F.; Remondino, F. A review of point clouds segmentation and classification algorithms. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2017, 42, 339–344. [Google Scholar] [CrossRef]
- Luo, N.; Jiang, Y.; Wang, Q. Supervoxel-based region growing segmentation for point cloud data. Int. J. Pattern Recognit. Artif. Intell. 2021, 35, 2154007. [Google Scholar] [CrossRef]
- Zhao, B.; Hua, X.; Yu, K.; Xuan, W.; Chen, X.; Tao, W. Indoor point cloud segmentation using iterative gaussian mapping and improved model fitting. IEEE Trans. Geosci. Remote Sens. 2020, 58, 7890–7907. [Google Scholar] [CrossRef]
- Dong, C.; Chen, N.; Li, Y.; Bao, J. Point Cloud Segmentation Algorithm Based on Deep Learning and 3D Reconstruction. In Proceedings of the 2022 IEEE 5th Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC), Chongqing, China, 16–18 December 2022; Volume 5, pp. 476–480. [Google Scholar]
- Zhu, X.; Liu, X.; Zhang, Y.; Wan, Y.; Duan, Y. Robust 3-D plane segmentation from airborne point clouds based on quasi-a-contrario theory. IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens. 2021, 14, 7133–7147. [Google Scholar] [CrossRef]
- Andoni, A.; Indyk, P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 2008, 51, 117–122. [Google Scholar] [CrossRef]
- Chen, H.; Liang, M.; Liu, W.; Wang, W.; Liu, P.X. An approach to boundary detection for 3D point clouds based on DBSCAN clustering. Pattern Recognit. 2022, 124, 108431. [Google Scholar] [CrossRef]
- Miao, T.; Zhu, C.; Xu, T.; Yang, T.; Li, N.; Zhou, Y.; Deng, H. Automatic stem-leaf segmentation of maize shoots using three-dimensional point cloud. Comput. Electron. Agric. 2021, 187, 106310. [Google Scholar] [CrossRef]
- Sun, L.; Liu, R.; Xu, J.; Zhang, S. An adaptive density peaks clustering method with Fisher linear discriminant. IEEE Access 2019, 7, 72936–72955. [Google Scholar] [CrossRef]
- Zhu, Z.; Liu, N. Early warning of financial risk based on K-means clustering algorithm. Complexity 2021, 2021, 5571683. [Google Scholar] [CrossRef]
- Chen, Y.; Zhong, H.; Chen, C.; Shen, C.; Huang, J.; Wang, T.; Liang, Y.; Sun, Q. On mitigating hard clusters for face clustering. In Proceedings of the European Conference on Computer Vision, Tel Aviv, Israel, 23–27 October 2022; Springer Nature: Cham, Switzerland, 2022; pp. 529–544. [Google Scholar]
- Kang, C.; Lin, Z.; Wu, S.; Lan, Y.; Geng, C.; Zhang, S. A Triangular Grid Filter Method Based on the Slope Filter. Remote Sens. 2023, 15, 2930. [Google Scholar] [CrossRef]
- Zhang, J.; Cao, J.J.; Zhu, H.R.; Yan, D.M.; Liu, X.P. Geometry guided deep surface normal estimation. Comput. -Aided Des. 2022, 142, 103119. [Google Scholar] [CrossRef]
- Hu, G.; Xiong, L.; Lu, S.; Chen, J.; Li, S.; Tang, G.; Strobl, J. Mathematical vector framework for gravity-specific land surface curvatures calculation from triangulated irregular networks. GIScience Remote Sens. 2022, 59, 590–608. [Google Scholar] [CrossRef]
- Yazdanpanah, M.; Xu, C.; Sharifzadeh, M. A new statistical method to segment photogrammetry data in order to obtain geological information. Int. J. Rock Mech. Min. Sci. 2022, 150, 105008. [Google Scholar] [CrossRef]
- Zhou, B.; Huang, R. Segmentation algorithm for 3D LiDAR point cloud based on region clustering. In Proceedings of the 2020 7th International Conference on Information, Cybernetics, and Computational Social Systems (ICCSS), Guangzhou, China, 13–15 November 2020; pp. 52–57. [Google Scholar]
- Tan, K.; Ke, T.; Tao, P.; Liu, K.; Duan, Y.; Zhang, W.; Wu, S. Discriminating forest leaf and wood components in TLS point clouds at single-scan level using derived geometric quantities. IEEE Trans. Geosci. Remote Sens. 2021, 60, 1–17. [Google Scholar] [CrossRef]
- Thukral, A.K.; Bhardwaj, R.; Kumar, V.; Sharma, A. New indices regarding the dominance and diversity of communities, derived from sample variance and standard deviation. Heliyon 2019, 5, e02606. [Google Scholar] [CrossRef]
- Furlan, L.; Sterr, A. The applicability of standard error of measurement and minimal detectable change to motor learning research—A behavioral study. Front. Hum. Neurosci. 2018, 12, 95. [Google Scholar] [CrossRef] [PubMed]
- Yuan, H.; Sun, W.; Xiang, T. Line laser point cloud segmentation based on the combination of RANSAC and region growing. In Proceedings of the 2020 39th Chinese Control Conference (CCC), Shenyang, China, 27–29 July 2020; pp. 6324–6328. [Google Scholar] [CrossRef]
Sample | Number of Under-Segmented Points (Red Points) | Number of over-Segmented Points (Blue Points) | Manual Segmentation | Total Error Rate | ||||||
---|---|---|---|---|---|---|---|---|---|---|
European Clustering | Region-Growing Method | Our Method | Euclidean Clustering | Region-Growing Method | Our Method | Euclidean Clustering | Region-Growing Method | Our Method | ||
Sample1 | 1753 | 7 | 326 | 179 | 2943 | 365 | 14,410 | 13.4074 | 20.4719 | 4.7953 |
Sample2 | 450 | 0 | 22 | 0 | 981 | 7 | 5183 | 8.6822 | 18.9273 | 0.5595 |
Sample3 | 28 | 4 | 21 | 0 | 300 | 1 | 2169 | 1.2909 | 14.0157 | 1.0143 |
Sample4 | 5 | 0 | 0 | 0 | 188 | 6 | 996 | 0.5020 | 18.8755 | 0.6024 |
Sample5 | 47 | 0 | 27 | 14 | 218 | 12 | 1450 | 4.2069 | 15.0345 | 2.6897 |
Sample6 | 299 | 1 | 15 | 0 | 97 | 0 | 653 | 45.7887 | 15.0077 | 2.2971 |
Average | 12.3130 | 17.0554 | 1.9931 |
Sample | Real Ground Point | Segmentation Point | Accurate Segmentation | Correct Ratio | Under-Segmented Points | Over-Segmented Points |
---|---|---|---|---|---|---|
Sample 12 | 26,691 | 18,218 | 16,644 | 91.36 | 1569 | 10,036 |
Sample 21 | 10,085 | 1764 | 1643 | 93.14 | 121 | 8436 |
Sample 22 | 22,504 | 3088 | 3014 | 97.60 | 74 | 19,484 |
Sample 23 | 13,223 | 839 | 835 | 99.52 | 3 | 12,384 |
Sample 24 | 5434 | 960 | 922 | 96.04 | 38 | 4507 |
Sample 31 | 15,556 | 13,899 | 12,617 | 90.78 | 1276 | 2933 |
Sample | Real Ground Point | Segmentation Point | Accurate Segmentation | Correct Ratio | Under-Segmented Points | Over-Segmented Points |
---|---|---|---|---|---|---|
Sample 12 | 26,691 | 29,825 | 24,795 | 83.13 | 5020 | 1885 |
Sample 21 | 10,085 | 11,924 | 10,027 | 84.09 | 1891 | 52 |
Sample 22 | 22,504 | 24,784 | 20,890 | 84.29 | 3888 | 1608 |
Sample 23 | 13,223 | 11,367 | 9991 | 87.89 | 1372 | 3228 |
Sample 24 | 5434 | 6357 | 5377 | 84.58 | 975 | 52 |
Sample 31 | 15,556 | 15,602 | 13,591 | 87.11 | 2005 | 1959 |
Sample | Real Ground Point | Segmentation Point | Accurate Segmentation | Correct Ratio | Under-Segmented Points | Over-Segmented Points |
---|---|---|---|---|---|---|
Sample 12 | 26,691 | 35,628 | 26,453 | 74.25 | 9162 | 227 |
Sample 21 | 10,085 | 12,292 | 10,079 | 82.00 | 2207 | 0 |
Sample 22 | 22,504 | 25,504 | 21,352 | 83.72 | 4146 | 1146 |
Sample 23 | 13,223 | 17,985 | 12,423 | 69.07 | 5556 | 796 |
Sample 24 | 5434 | 6611 | 5408 | 81.80 | 1198 | 21 |
Sample 31 | 15,556 | 22,120 | 15,496 | 70.05 | 6615 | 54 |
Sample | Real Ground Point | Segmentation Point | Accurate Segmentation | Correct Ratio | Under-Segmented Points | Over-Segmented Points |
---|---|---|---|---|---|---|
Sample 12 | 26,691 | 29,528 | 20,632 | 69.87 | 8884 | 6048 |
Sample 21 | 10,085 | 9584 | 8585 | 89.58 | 993 | 1494 |
Sample 22 | 22,504 | 26,353 | 19,631 | 74.49 | 6715 | 2967 |
Sample 23 | 13,223 | 18,886 | 11,038 | 58.45 | 7844 | 2181 |
Sample 24 | 5434 | 5091 | 4249 | 83.46 | 837 | 1180 |
Sample 31 | 15,556 | 19,066 | 12,952 | 67.93 | 6103 | 2698 |
Sample | Real Ground Point | Segmentation Point | Accurate Segmentation | Correct Ratio | Under-Segmented Points | Over-Segmented Points |
---|---|---|---|---|---|---|
Sample 12 | 26,691 | 20,384 | 18,467 | 90.60 | 1909 | 8213 |
Sample 21 | 10,085 | 9444 | 9082 | 96.17 | 356 | 997 |
Sample 22 | 22,504 | 12,198 | 11,645 | 95.47 | 549 | 10,853 |
Sample 23 | 13,223 | 7224 | 6313 | 87.39 | 908 | 6906 |
Sample 24 | 5434 | 3067 | 2877 | 93.81 | 186 | 2552 |
Sample 31 | 15,556 | 13,275 | 12,218 | 92.04 | 1051 | 3332 |
Sample | Real Ground Point | Segmentation Point | Accurate Segmentation | Correct Ratio | Under-Segmented Points | Over-Segmented Points |
---|---|---|---|---|---|---|
Sample 12 | 26,691 | 25,001 | 21,695 | 86.78 | 3299 | 4985 |
Sample 21 | 10,085 | 10,272 | 9015 | 87.76 | 1252 | 1064 |
Sample 22 | 22,504 | 21,989 | 19,914 | 90.56 | 2840 | 3354 |
Sample 23 | 13,223 | 9816 | 8799 | 89.64 | 1015 | 4420 |
Sample 24 | 5434 | 5508 | 4924 | 89.40 | 580 | 505 |
Sample 31 | 15,556 | 13,900 | 12,438 | 89.48 | 1456 | 3112 |
Sample | Over-Segmented Points | Over-Segmented Points Remove Non-Continuous Ground |
---|---|---|
Sample 12 | 4985 | 2613 |
Sample 21 | 1064 | 1064 |
Sample 22 | 3354 | 1817 |
Sample 23 | 4420 | 1650 |
Sample 24 | 505 | 505 |
Sample 31 | 3112 | 1253 |
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. |
© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Lin, Z.; Kang, C.; Wu, S.; Li, X.; Cai, L.; Zhang, D.; Wang, S. Adaptive Clustering for Point Cloud. Sensors 2024, 24, 848. https://doi.org/10.3390/s24030848
Lin Z, Kang C, Wu S, Li X, Cai L, Zhang D, Wang S. Adaptive Clustering for Point Cloud. Sensors. 2024; 24(3):848. https://doi.org/10.3390/s24030848
Chicago/Turabian StyleLin, Zitao, Chuanli Kang, Siyi Wu, Xuanhao Li, Lei Cai, Dan Zhang, and Shiwei Wang. 2024. "Adaptive Clustering for Point Cloud" Sensors 24, no. 3: 848. https://doi.org/10.3390/s24030848