本論文旨在使用傳統的資料處理方式，發展出針對某堆疊工件在場景中點雲的匹配演算法，以判別工件在場景中之位置與姿態。本論文對三維點雲資料進行分析與處理，在數位訊號處理及數據統計的基礎上，先對工件模型的部分點雲進行降採樣、隱藏點去除法(Hidden Point Removal, HPR)及RANSAC (RANdom SAmple Consensus)的平面以及弧面模型擬合，以產生點雲匹配之面特徵。在場景的部分，吾人利用開源軟體Blender將工件模型檔案隨意堆疊至平面上，輸出可模擬實際工件堆疊之點雲資料。並用軟體內部的功能，將視野中由上而下所會看到的點雲資料萃取出來，並對其摻加雜訊，進而模擬實際深度相機所會拍攝到的畫面。在實作上，吾人利用第三方函式庫Point Cloud Library (PCL)與C++，對場景進行區域增長法(region growing)，將破碎平面萃取出來，並利用模型資料之多個面模型，進行法向量對齊、最近點迭代(Iterative Closest Point, ICP)、旋轉、最近點搜尋與距離評分，再佐以最近點資料分布相似度以及個數，進行加權評分，以判斷出能夠最佳吻合於場景平面的面模型，最後計算出該工件位於場景的姿態與位置。經多次實驗，本論文所發展之演算法對該工件之匹配成功率可達100%，且還能夠運用在外型簡單的物件如柱狀體或是圓柱體，萃取出物件之平面或弧面的特徵並進行匹配，其匹配成功率亦可達100%。

The main objective of this thesis is to develop a point cloud registration algorithm that determines the position and orientation of the objects which are piled up in the scene using traditional data processing methods. The analysis and processing of the object’s point cloud data is based on digital signal processing and statistics, which includes methods such as down sampling, Hidden Point Removal and surface feature extraction of plane and arc using RANSAC (RANdom SAmple Consensus). The scene part is composed of multiple objects which is generated by the open-source software, Blender, and output as point cloud data for registration. The point cloud data of the scene is aimed to simulate the situation in real-time stereo camera shooting from the top. The scene data contains noise, and the objects are placed in an arbitrary way. The solution to extracting the surface parts of the objects in the scene is by applying region growing method supported by Point Cloud Library. The surface data from the scene is then registered with model’s plane data using the methods of surface normal alignment, Iterative Closest Point, and adding rotation to the object’s point cloud. Furthermore developed a grading system to determine the optimal orientation of the object in the scene. The accuracy of the algorithm is 100% tested multiple times. The algorithm can be applied to other objects which are composed of simple geometric surfaces, and the result accuracy is 100% as well.

[1] Blender網站https://www.blender.org/ (accessed on Jul. 7, 2024).
[2] S. L. Brunton, Data Driven Science & Engineering Machine Learning, Dynamical Systems, and Control, Cambridge University Press, New York, 2019.
[3] PCL網站https://pointclouds.org/ (accessed on Jul. 7, 2024).
[4] N. Pal and S. K. Pal, “A Review on Image Segmentation Techniques,” Pattern Recognition,” Vol. 26, No. 9, pp. 1277-1278, Sep. 1993.
[5] X. Huang, G. Mei, J. Zhang, and R. Abbas, “A Comprehensive Survey on Point Cloud Registration,” arXiv e-prints, Vol. 2, No. 2103.02690, Mar. 2021. https://arxiv.org/pdf/2103.02690 (accessed on Jul. 7, 2024).
[6] P. J. Besl and N. D. McKay, “A Method for Registration of 3-D Shapes,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, No. 2, pp. 239-256, Feb. 1992.
[7] R. B. Rusu, Semantic 3D Object Maps for Everyday Manipulation in Human Living Environments, Ph.D. Dissertation, The University of Rochester, 2009.
[8] I. Sipiran and B. Bustos, “Harris 3D: A Robust Extension of the Harris Operator for Interest Point Detection on 3D Meshes,” The Visual Computer, Vol. 27, No. 1, pp. 963-976, Nov. 2011.
[9] Y. Zhong, “Intrinsic Shape Signatures: A Shape Descriptor for 3D Object Recognition,” Proceeding of 2009 IEEE 12th International Conference on Computer Vision Workshops, pp. 689-696, Sep.-Oct. 2009.
[10] B. Drost, M. Ulrich, N. Navab, and S. Ilic, “Model Globally, Match Locally: Efficient and Robust 3D Object Recognition,” Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 998-1005, Jun. 2010.
[11] A. E. Johnson and M. Hebert, “Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 21, No. 5, pp. 433-449, May 1999.
[12] F. Tombari, S. Salti, and L. D. Stefano, “Unique Signatures of Histograms for Local Surface Description,” Proceedings of Computer Vision – ECCV 2010, Vol. 6313, pp. 356-369, Sep. 2010.
[13] F. Tombari and L. Di Stefano, “Object Recognition in 3D Scenes with Occlusions and Clutter by Hough Voting,” Proceedings of 4th Pacific-Rim Symposium on Image and Video Technology, pp. 349-355, Nov. 2010.
[14] A. Zeng, S. Song, M. Nießner, M. Fisher, J. Xiao, and T. Funkhouser, “3dmatch: Learning Local Geometric Descriptors from RGB-D Reconstructions,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1802-1811, Jul. 2017.
[15] D. Haowen, T. Birdal, and S. Ilic, “Ppfnet: Global Context Aware Local Features for Robust 3d Point Matching,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 195-205, Jun. 2018.
[16] M. A. Fischler and R. C. Bolles, “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography,” Readings in Computer Vision, Vol. 24, No. 6, pp. 726-740, Nov. 1987.
[17] Z. Yang, J. Z. Pan, L. Luo, X. Zhou, K. Grauman, and Q. Huang, “Extreme Relative Pose Estimation for RGBD Scans via Scene Completion,” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4526-4535, Jun. 2019.
[18] L. Wang, “Non-Rigid Point Set Registration Networks,” ArXiv, Vol. abs/1904.01428, Apr. 2019.
https://arxiv.org/pdf/1904.01428 (accessed on Jul. 7, 2024).
[19] G. Elbaz, T. Avraham, and A. Fischer, “3d Point Cloud Registration for Localization Using a Deep Neural Network Auto-Encoder,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4631-4640, Jul. 2017.
[20] M. Weinmann, Reconstruction and Analysis of 3D Scenes, Springer Cham, London, 2018.
[21] R. Szeliski, Computer Vision: Algorithms and Applications. Springer, London, Sep. 2011.
[22] D. Scharstein and R. Szeliski, “A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms,” Proceedings IEEE Workshop on Stereo and Multi-Baseline Vision, Vol. 47, pp. 131-140, Dec. 2001.
[23] G. Bradski and A. Kaehler, Learing OpenCV, O'Reilly Media, Inc., California, 2008.
[24] Y. Furukawa and C. Hernández, Multi-View Stereo: A Tutorial, Now Foundations and Trends, Norwell, 2015.
[25] D. G. Lowe, “Object Recognition from Local Scale-Invariant Features,” Proceedings of the Seventh IEEE International Conference on Computer Vision, Vol. 2, pp. 1150-1157, Sep. 1999.
[26] S. M. Seitz, B. Curless, J. Diebel, D. Scharstein, and R. Szeliski, “A Comparison and Evaluation of Multi-View Stereo Reconstruction Algorithms,” Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 1, pp. 519-528, Jun. 2006.
[27] 劉治中，周錫珉,「結構光三維成像及其編碼技術」，科儀新知219期, 25-37頁, 民國一〇八年六月。
[28] B. Steder, B. Rusu, K. Konolige, and W. Burgard, “NARF: 3D Range Image Features for Object Recognition,” Proceedings of International Conference on Intelligent Robots and Systems, Vol. 44, pp. 2-3, Oct. 2010.
[29] J. L. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Association for Computing Machinery, Vol. 18, No. 9, pp. 509-517, Sep. 1975.
[30] 胡昭民，「圖解資料結構 × 演算法：運用C++」，博碩文化，民國一一〇年。
[31] D. Meagher, Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer, Rensselaer Polytechnic Institute, New York, 1980.
[32] Z. C. Marton, R. B. Rusu, and M. Beetz, “On Fast Surface Reconstruction Methods for Large and Noisy Datasets,” Proceedings of the IEEE International Conference on Robotics and Automation, pp. 3218-3223, May 2009.
[33] J. Wang and X. Li, “Calibration Method for Line-Structured Light Three-Dimensional Measurements Based on a Single Circular Target,” Photonics, Vol. 9, No. 4, Mar. 2022.
[34] Eigen網站
https://eigen.tuxfamily.org/index.php?title=Main_Page (accessed on Jul. 7, 2024).
[35] VTK網站https://vtk.org/ (accessed on Jul. 7, 2024).
[36] BSD網站 https://www.bsd.org/ (accessed on Jul. 7, 2024).
[37] J. Demmel and W. Kahan, Computing Small Singular Values of Bidiagonal Matrices With Guaranteed High Relative Accuracy, Nabu Press, Illnois, 2010.
[38] T. Roughgarden and G. Valiant, The Modern Algorithmic Toolbox Lecture #9: The Singular Value Decomposition (SVD) and Low-Rank Matrix Approximations, Standford University, 2024.
https://web.stanford.edu/class/cs168/l/l9.pdf (accessed on Jul. 7, 2024).
[39] Walter Gander, The Singular Value Decomposition, ETH Zurich, 2008. https://www2.math.ethz.ch/education/bachelor/lectures/hs2014/other/linalg_INFK/svdneu.pdf (accessed on Jul. 7, 2024).
[40] IDS網站
https://en.ids-imaging.com/ensenso-3d-camera-s-series.html (accessed on Jul. 7, 2024).
[41] Gocator網站
https://lmi3d.com/series/gocator-3500-series/ (accessed on Jul. 7, 2024).
[42] M. Pauly, M. Gross, and L. Kobbelt, “Efficient Simplification of Point-Sampled Surfaces,” Proceedings of IEEE Visualization, pp. 163-170, Nov. 2002.
[43] J. Shi and C. Tomasi, “Good Features to Track,” Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 593-600, Jun. 1994.
[44] 羅德里格旋轉矩陣之角度差異求解
https://www.cs.cornell.edu/courses/cs6670/2017fa/lec3-rotation.pdf (accessed on Jul. 7, 2024).
[45] H. Cheng and K. C. Gupta, “An Historical Note on Finite Rotations,” Journal of Applied Mechanics, Vol. 56, No. 1, pp. 139-145, Mar. 1989.
[46] C. B. Barber, “The Quickhull Algorithm for Convex Hulls,” ACM Transactions on Mathematical Software, Vol. 22, No. 4, pp. 469-483, Dec. 1996.
[47] S. Katz, A. Tal, and R. Basri, “Direct Visibility of Point Sets,” Association for Computing Machinery, Vol. 26, No. 3, pp. 24-25, Jul. 2007.
[48] M. M. S. J. Preetha, L. P. Suresh and M. J. Bosco, “Image Segmentation Using Seeded Region Growing," Proceedings of 2012 International Conference on Computing, Electronics and Electrical Technologies, pp. 576-583, Mar. 2012.
[49] T. Rabbani, F.V. Heuvel, and G. Vosselman, “Segmentation of Point Clouds Using Smoothness Constraint,” International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. 36, No. 5, pp. 248-253, Jan. 2006.
[50] Open3D網站
https://www.open3d.org/docs/0.9.0/tutorial/Basic/index.html (accessed on Jul. 7, 2024).
[51] V. Hai, L. Van-Hung, N. Thuy, L. Thi, and T. Thanh-Hai, “Fitting Cylindrical Objects in 3-D Point Cloud Using the Context and Geometrical Constraints,” Journal of Information Science and Engineering, Vol. 35, No. 1, pp. 41-60, Jan. 2018.