台灣位處環太平洋火山帶，地震災害頻傳，若結構物遭受地震襲擊而倒榻，人員將受困於倒塌結構內部，此時若能快速獲得倒塌結構內部空間資訊，便能協助搜救人員進行搜索與救援(search and rescue, SAR)行動，為此本研究依據Bloch所提出之結論，提出一套快速點雲建模演算法，將光達掃描所獲取的點雲資料建模為3D模型，該演算流程包含資料索引建立、點雲下採樣、梁柱元素辨識法、平面元素辨識法、模型建立，其中梁柱元素辨識法運用邊界提取法分割邊界特徵點雲，並運用特徵線追蹤將邊界點雲依法向量分群為邊界線，最後藉由外接圓進行元素識別，用於辨識結構物中矩形及正多邊形柱構件，平面元素辨識法則運用主成分分析搭配區域成長法分割平面點雲並藉由鄰域搜索找尋相鄰且平行之平面合併為元素，用於辨識牆、板等大型平面構件。經由結構物倒塌模型的測試證實，本研究所提出之點雲建模演算法於不同複雜度及不同倒塌程度之模型皆可達到良好的正確辨識率、誤判率、體積還原度及表面積還原度，僅誤判率及體積還原度會受到結構物倒塌程度影響而產生些微變化。

If a structure is collapses by an earthquake, people will be trapped inside the collapsed structure. At this time, if the spatial information inside the collapsed structure can be quickly obtained, it can assist the rescuers in search and rescue. Therefore, this study proposes a fast point cloud Scan-to-BIM algorithm to model the point cloud data as a 3D model. The algorithm process includes data index, voxel downsampling, beam and column element identification method, plane element identification method, and BIM creation. The beam and column element identification method uses the boundary extraction method to segment the boundary feature point cloud, and uses the feature line tracking to group the boundary point cloud into boundary lines according to the rules. Finally, element identification is performed by circumscribed circles, which are used to identify rectangular and regular polygonal column components in the structure. The plane element identification method uses principal component analysis and region growth method to segment plane point cloud, and finds adjacent and parallel through neighborhood search. These planes are grouped into elements that are used to identify large plane components such as walls and floors. The test of the structural collapse model confirms that the point cloud modeling algorithm proposed in this study can achieve good correct recognition rate, false positive rate, volume recovery and surface area recovery in models of different complexity and different degrees of collapse.

[1] Andriasyan, M., Moyano, J., Nieto-Julián, J. E., & Antón, D., From point cloud data to building information modelling: An automatic parametric workflow for heritage. Remote sensing, 12(7), 2020.
[2] Badenko, V., Fedotov, A., Zotov, D., Lytkin, S., Volgin, D., Garg, R. D., & Liu, M., Scan-to-BIM methodology adapted for different application. The International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 42: p. 1-7., 2019.
[3] Barber, C.B., D.P. Dobkin, and H. Huhdanpaa, The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software (TOMS), 22(4): p. 469-483., 1996.
[4] Bassier, M., Vergauwen, M., & Van Genechten, B., Automated semantic labelling of 3D vector models for scan-to-BIM. In Proceedings of the 4th Annual International Conference on Architecture and Civil Engineering (ACE2016) België., p. 93-100., 2016.
[5] Benavides López, J.A., J.A. Barrera Vera, and M. González Ferrer., 3D Laser scanner versus new self-modelling photogrammetry solutions aplications in architecture and archeology. in 1st International conference on construction and building research, p. 1-12., 2009.
[6] Bentley, J.L., Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9): p 509-517., 1975.
[7] Besl, P. J., & Jain, R. C., Segmentation through variable-order surface fitting. IEEE Transactions on pattern analysis and machine intelligence, 10(2): p. 167-192., 1988.
[8] Bloch, T., Sacks, R., & Rabinovitch, O., Interior models of earthquake damaged buildings for search and rescue. Advanced Engineering Informatics, 30(1): p. 65-76., 2016.
[9] Borba, E. Z., Montes, A., de Deus Lopes, R., Zuffo, M. K., & Kopper, R., Itapeva 3D: being Indiana Jones in virtual reality. In 2017 IEEE Virtual Reality (VR), p. 361-362., 2017
[10] Bosché, F., Guillemet, A., Turkan, Y., Haas, C. T., & Haas, R., Tracking the built status of MEP works: Assessing the value of a Scan-vs-BIM system. Journal of computing in civil engineering, 28(4): p. 1-28, 2014.
[11] Chen, H., Chen, W., Wu, R., & Huang, Y., Plane segmentation for a building roof combining deep learning and the RANSAC method from a 3D point cloud. Journal of Electronic Imaging, 30(5), 2021.
[12] Chen, J., Kira, Z., & Cho, Y. K., LRGNet: Learnable region growing for class-agnostic point cloud segmentation. IEEE Robotics and Automation Letters, 6(2): p. 2799-2806., 2021.
[13] Chen, X., Zhao, H., & Zhou, P., Lung Lobe Segmentation Based on Lung Fissure Surface Classification Using a Point Cloud Region Growing Approach. Algorithms, 13(10), 2020.
[14] Cheng, M., Hui, L., Xie, J., & Yang, J., SSPC-Net: Semi-supervised semantic 3D point cloud segmentation network. In Proceedings of the AAAI Conference on Artificial Intelligence, 35(2): p. 1140-1147., 2021.
[15] Choi, S., Kim, T., & Yu, W., Performance evaluation of RANSAC family. Journal of Computer Vision, 24(3): p. 271-300., 1997.
[16]. Duan, Y., Yang, C., Chen, H., Yan, W., & Li, H., Low-complexity point cloud denoising for LiDAR by PCA-based dimension reduction. Optics Communications, 482, 2021.
[17] Ebrahimi, A., & Czarnuch, S., Automatic Super-Surface Removal in Complex 3D Indoor Environments Using Iterative Region-Based RANSAC. Sensors, 21(11), 2021.
[18] Fadakar Alghalandis, Y., Dowd, P. A., & Xu, C, The RANSAC method for generating fracture networks from micro-seismic event data. Mathematical Geosciences, 45(2): p. 207-224., 2013.
[19] Ferworn, A., Herman, S., Tran, J., Ufkes, A., & Mcdonald, R., Disaster scene reconstruction: Modeling and simulating urban building collapse rubble within a game engine. in Proceedings of the 2013 Summer Computer Simulation Conference., p. 1-6., 2013.
[20] Ghahremani, M., Williams, K., Corke, F., Tiddeman, B., Liu, Y., Wang, X., & Doonan, J. H., Direct and accurate feature extraction from 3D point clouds of plants using RANSAC. Computers and Electronics in Agriculture, 187, 2021.
[21] He, J., Wang, S., & Li, J., Tooth point cloud segmentation of dental model based on region growing. in Proceedings of the 2nd International Conference on Artificial Intelligence and Advanced Manufacture., p. 489-492, 2020.
[22] Kamari, M., & Ham, Y., Vision-based volumetric measurements via deep learning-based point cloud segmentation for material management in jobsites. Automation in Construction, 121, 2021.
[23] Khadhraoui, T., Benzarti, F., & Amiri, H., New approach on pca-based 3d face recognition and authentication. in 15th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD), p. 1-5., 2014.
[24] Khaloo, A., & Lattanzi, D., Robust normal estimation and region growing segmentation of infrastructure 3D point cloud models. Advanced Engineering Informatics, 34: p. 1-16., 2017.
[25] Lalonde, J. F., Vandapel, N., Huber, D. F., & Hebert, M., Natural terrain classification using three‐dimensional ladar data for ground robot mobility. Journal of field robotics, 23(10): p. 839-861., 2006.
[26] Li, J., Hu, Q., & Ai, M., Point cloud registration based on one-point ransac and scale-annealing biweight estimation. IEEE Transactions on Geoscience and Remote Sensing, 59(11): p. 9716-9729., 2021.
[27] Li, S., Wang, J., Liang, Z., & Su, L., Tree point clouds registration using an improved ICP algorithm based on kd-tree. in 2016 IEEE International Geoscience and Remote Sensing Symposium (IGARSS), p. 4545-4548, 2016.
[28] Li, Z., & Shan, J., RANSAC-based multi primitive building reconstruction from 3D point clouds. ISPRS Journal of Photogrammetry and Remote Sensing, 185: p. 247-260., 2022.
[29] Lin, W., Fan, W., Liu, H., Xu, Y., & Wu, J., Classification of Handheld Laser Scanning Tree Point Cloud Based on Different KNN Algorithms and Random Forest Algorithm. Forests, 12(3), 2021.
[30] Liu, Y., Zhang, G., Shao, K., Xiao, S., Wang, Q., Zhu, J., Wang, R., Meng, L. & Ma, Y., Segmentation of Individual Leaves of Field Grown Sugar Beet Plant Based on 3D Point Cloud. Agronomy, 12(4), 2022.
[31] Ma, L., Zheng, G., Eitel, J. U., Moskal, L. M., He, W., & Huang, H., Improved salient feature-based approach for automatically separating photosynthetic and nonphotosynthetic components within terrestrial lidar point cloud data of forest canopies. IEEE Transactions on geoscience and remote sensing, 54(2): p. 679-696., 2015.
[32] Macintyre, A. G., Barbera, J. A., & Smith, E. R., Surviving collapsed structure entrapment after earthquakes: a “time-to-rescue” analysis. Prehospital and disaster medicine, 21(1): p. 4-17., 2006.
[33] Mehta, S., Peach, J., & Weinert, A., To expedite roadway identification and damage assessment in LiDAR 3D imagery for disaster relief public assistance. Infrastructures, 7(3), 2022.
[34] Meng, H. Y., Gao, L., Lai, Y. K., & Manocha, D., Vv-net: Voxel vae net with group convolutions for point cloud segmentation. in Proceedings of the IEEE/CVF international conference on computer vision, p. 8500-8508., 2019.
[35] Miao, T., Wen, W., Li, Y., Wu, S., Zhu, C., & Guo, X., Label3DMaize: toolkit for 3D point cloud data annotation of maize shoots. GigaScience, 10(5), 2021.
[36] Muhadi, N. A., Abdullah, A. F., Bejo, S. K., Mahadi, M. R., & Mijic, A., The use of LiDAR-derived DEM in flood applications: A review. Remote Sensing, 12(14), 2020.
[37] Murtiyoso, A., & Grussenmeyer, P., Automatic heritage building point cloud segmentation and classification using geometrical rules. The International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 42: p. 821-827., 2019.
[38] Murtiyoso, A., & Grussenmeyer, P., Virtual disassembling of historical edifices: Experiments and assessments of an automatic approach for classifying multi-scalar point clouds into architectural elements. Sensors, 20(8), 2020.
[39] Ni, H., Lin, X., Ning, X., & Zhang, J., Edge detection and feature line tracing in 3D-point clouds by analyzing geometric properties of neighborhoods. Remote Sensing, 8(9), 2016.
[40] Nurunnabi, A., Belton, D., & West, G., Robust segmentation in laser scanning 3D point cloud data. in 2012 International Conference on Digital Image Computing Techniques and Applications (DICTA), p. 1-8., 2012.
[41] Nurunnabi, A., Belton, D., & West, G., Robust segmentation for multiple planar surface extraction in laser scanning 3D point cloud data. in Proceedings of the 21st International Conference on Pattern Recognition (ICPR2012), p. 1367-1370., 2012.
[42] Oh, S., Lee, D., Kim, M., Kim, T., & Cho, H., Building Component Detection on Unstructured 3D Indoor Point Clouds Using RANSAC-Based Region Growing. Remote Sensing, 13(2), 2021.
[43] Ota, T., Ogawa, M., Mizoue, N., Fukumoto, K., & Yoshida, S., Forest structure estimation from a UAV-based photogrammetric point cloud in managed temperate coniferous forests. Forests, 8(9), 2017.
[44] Peng, K., Tan, J., & Zhang, G., A Method of Curve Reconstruction Based on Point Cloud Clustering and PCA. Symmetry, 14(4), 2022.
[45] Pinkham, R., Zeng, S., & Zhang, Z., Quicknn: Memory and performance optimization of kd tree based nearest neighbor search for 3d point clouds. in 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), 2020.
[46] Poux, F., Neuville, R., Nys, G. A., & Billen, R., 3D Point Cloud semantic modelling: Integrated framework for indoor spaces and furniture. Remote Sensing, 10(9), 2018.
[47] Quintana, B., Prieto, S. A., Adán, A., & Bosché, F., Scan-to-BIM for small building components. in Joint Conference on Computing in Construction, p. 4-7., 2017.
[48] Rebolj, D., Pučko, Z., Babič, N. Č., Bizjak, M., & Mongus, D., Point cloud quality requirements for Scan-vs-BIM based automated construction progress monitoring. Automation in Construction, 84: p. 323-334., 2017.
[49] Sanchez, V., & Zakhor, A., Planar 3D modeling of building interiors from point cloud data. in 2012 19th IEEE International Conference on Image Processing, p. 1777-1780., 2012.
[50] Schnabel, R., Wahl, R., & Klein, R., Efficient RANSAC for point‐cloud shape detection. in Computer graphics forum. 26(2): p. 214-226., 2007.
[51] Shao, J., Zhang, W., Shen, A., Mellado, N., Cai, S., Luo, L., Wang, N., Yan, G., & Zhou, G., Seed point set-based building roof extraction from airborne LiDAR point clouds using a top-down strategy. Automation in Construction, 126, 2021.
[52] Son, H., Kim, C., & Turkan, Y., Scan-to-BIM-an overview of the current state of the art and a look ahead. in ISARC. Proceedings of the International Symposium on Automation and Robotics in Construction, 32, 2015.
[53] Stein, A., Geva, E., & El-Sana, J., CudaHull: Fast parallel 3D convex hull on the GPU. Computers & Graphics, 36(4): p. 265-271., 2012.
[54] Torr, P. H., & Zisserman, A., MLESAC: A new robust estimator with application to estimating image geometry. Computer vision and image understanding, 78(1): p. 138-156., 2000.
[55] Tremeau, A., & Borel, N., A region growing and merging algorithm to color segmentation. Pattern recognition, 30(7): p. 1191-1203., 1997.
[56] Vo, A. V., Truong-Hong, L., Laefer, D. F., & Bertolotto, M., Octree-based region growing for point cloud segmentation. ISPRS Journal of Photogrammetry and Remote Sensing, 104: p. 88-100., 2015.
[57] Wallace, L., Lucieer, A., Watson, C., & Turner, D., Development of a UAV-LiDAR System with Application to Forest Inventory. Remote Sensing, 4(6): p. 1519-1543., 2012.
[58] Wang, B., Lan, J., & Gao, J., LiDAR filtering in 3D object detection based on improved RANSAC. Remote Sensing, 14(9), 2022.
[59] Wang, M., & Tseng, Y. H., Incremental segmentation of lidar point clouds with an octree‐structured voxel space. The Photogrammetric Record, 26(133): p. 32-57., 2011.
[60] Wang, Q., Guo, J., & Kim, M. K., An application oriented scan-to-BIM framework. Remote sensing, 11(3), 2019.
[61] Winiwarter, L., Pena, A. M. E., Weiser, H., Anders, K., Sanchez, J. M., Searle, M., & Höfle, B., Virtual laser scanning with HELIOS++: A novel take on ray tracing-based simulation of topographic full-waveform 3D laser scanning. Remote Sensing of Environment, 269, 2022.
[62] Wu, W., Zhang, Y., Wang, D., & Lei, Y., SK-Net: Deep learning on point cloud via end-to-end discovery of spatial keypoints. in Proceedings of the AAAI Conference on Artificial Intelligence, 34(4): p. 6422-6429., 2020.
[63] Xu, B., Chen, Z., Zhu, Q., Ge, X., Huang, S., Zhang, Y., Liu, T., & Wu, D., Geometrical Segmentation of Multi-Shape Point Clouds Based on Adaptive Shape Prediction and Hybrid Voting RANSAC. Remote Sensing, 14(9), 2022.
[64] 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 Sensing, 8(1), 2015.
[65] Yang, L., Li, Y., Li, X., Meng, Z., & Luo, H., Efficient plane extraction using normal estimation and RANSAC from 3D point cloud. Computer Standards & Interfaces, 82, 2022.
[66] Yew, Z. J., & Lee, G. H., 3dfeat-net: Weakly supervised local 3d features for point cloud registration. in Proceedings of the European Conference on Computer Vision (ECCV), p. 607-623., 2018.
[67] Yonglin, S., Lixin, W., & Zhi, W., Identification of inclined buildings from aerial lidar data for disaster management. in 2010 18th International Conference on Geoinformatics, p. 1-5., 2010.
[68] Zhang, C., & Chen, T., Efficient feature extraction for 2D/3D objects in mesh representation. in Proceedings 2001 International Conference on Image Processing, p. 935-938., 2001.
[69] Zhang, W., Zhou, F., Wang, L., & Sun, P., Region Growing Based on 2-D–3-D Mutual Projections for Visible Point Cloud Segmentation. IEEE Transactions on Instrumentation and Measurement, 70: p. 1-13., 2021.
[70] Zucker, S.W., Region growing: Childhood and adolescence. Computer graphics and image processing, 5(3): p. 382-399., 1976.