2D影像之物體偵測已廣泛使用於許多應用。然而，某些條件會限制2D影像之物體偵測能力。例如相同物體卻由不同角度拍攝所得之二張影像，便難以有效地確認此二張影像為同一物體。3D 攝影機/掃描器 提供了有效的方法去取得3D物體之點雲(point cloud)資料，此資料能描繪出與拍攝角度無關之物體表面特徵。
在3D場景(scene)中尋找目標物(template)需要非常龐大的運算量，而處於高遮蔽率場景之目標物，其偵測率通常不高，本文提出一種多階段架構之3D物體偵測演算法，用以解決龐大的運算量以及低偵測率之問題。此演算法以對點特徵(point-pair feature)作為表面特徵描述子(descriptor)，利用散列法(hashing technique)加速描述子的匹配，並且使用一種創新的隨機成對航點特徵(randomized waypoint-pair feature)以及連續航點檢查(consecutive waypoint checking)之策略，有效的濾除錯誤目標。最後，計算出待偵測物體映射至場景中物體的表面擬合估計值(surface fitting estimation)，以判斷所偵測的物體是否為正確之目標。此外，本文利用等方格結構(uniform cubic structure)加速連續航點檢查及表面擬合估計值之計算。
為展現本文所提多階段架構之3D物體偵測演算法之能力，本實驗之點雲資料由二種不同類型之3D取像裝置取得，分別為3D雷射場景掃描器(3D laser range scanner)及顏色深度攝影機(RGB-D camera, Microsoft Kinect V1)。

2D object detection has been widely used in many applications. Since a 2D image can only describe the information of an object by one angle of view, it is a difficult problem to identify an object effectively from 2D images. The 3D scanning technology provides an efficient way to obtain 3D data (point cloud) of an object. The 3D point cloud model is angle-invariant and can describe the surface of a 3D object.
Searching a template object in a scene will encounter two drawbacks: the low detection rate in cases with high occlusion, and the heavy computation. In this thesis, an algorithm based on a multi-step structure is proposed for solving the problems of the low detection rate and the heavy computation. The basic descriptor of the proposed algorithm is with the point-pair feature format. The hashing technique is utilized to speed up the descriptor matching process. A novel 3D descriptor, the randomized waypoint-pair feature, is utilized to describe the descriptors in the scene model. A strategy of consecutive waypoint checking is utilized to sift the spurious detected candidates. Lastly, a verification method of surface fitting estimation is utilized to determine if a detected candidate is correct or not. Moreover, we also propose a uniform cubic structure for speeding up the processes of the consecutive waypoint checking and the surface fitting estimation.
The sample datasets of our experiments are from two types of device, the 3D laser range scanner and the RGB-D camera. We analyze the influence of the different parameters of the proposed algorithm, and compare the detection rates with the previous methods. From experimental results, the proposed algorithm not only gets a high detection rate, but also reduces the computation efficiently.

[1]H. Schneiderman and T. Kanade, "A statistical method for 3D object detection applied to faces and cars," in Computer Vision and Pattern Recognition, 2000. Proceedings. IEEE Conference on, 2000, pp. 746-751 vol.1.
[2]P. Viola and M. Jones, "Rapid object detection using a boosted cascade of simple features," in Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on, 2001, pp. I-511-I-518 vol.1.
[3]R. Lienhart and J. Maydt, "An extended set of Haar-like features for rapid object detection," in Image Processing. 2002. Proceedings. 2002 International Conference on, 2002, pp. I-900-I-903 vol.1.
[4]C. P. Papageorgiou, M. Oren, and T. Poggio, "A general framework for object detection," in Computer Vision, 1998. Sixth International Conference on, 1998, pp. 555-562.
[5]A. Torralba, K. P. Murphy, and W. T. Freeman, "Sharing features: efficient boosting procedures for multiclass object detection," in Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, 2004, pp. II-762-II-769 Vol.2.
[6]A. Torralba, K. P. Murphy, and W. T. Freeman, "Sharing Visual Features for Multiclass and Multiview Object Detection," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, pp. 854-869, 2007.
[7]P. F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan, "Object Detection with Discriminatively Trained Part-Based Models," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 32, pp. 1627-1645, 2010.
[8]J. Gall and V. Lempitsky, "Class-Specific Hough Forests for Object Detection," in Decision Forests for Computer Vision and Medical Image Analysis, A. Criminisi and J. Shotton, Eds., ed London: Springer London, 2013, pp. 143-157.
[9]T. Dean, M. A. Ruzon, M. Segal, J. Shlens, S. Vijayanarasimhan, and J. Yagnik, "Fast, Accurate Detection of 100,000 Object Classes on a Single Machine," presented at the Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition, 2013.
[10]J. J. Lim, C. L. Zitnick, P. Doll, and x00E, "Sketch Tokens: A Learned Mid-level Representation for Contour and Object Detection," in Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on, 2013, pp. 3158-3165.
[11]P. Dollar, R. Appel, S. Belongie, and P. Perona, "Fast Feature Pyramids for Object Detection," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 36, pp. 1532-1545, 2014.
[12]C. L. Zitnick and P. Dollár, "Edge Boxes: Locating Object Proposals from Edges," in Computer Vision – ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V, D. Fleet, T. Pajdla, B. Schiele, and T. Tuytelaars, Eds., ed Cham: Springer International Publishing, 2014, pp. 391-405.
[13]A. Borji, D. N. Sihite, and L. Itti, "Salient Object Detection: A Benchmark," in Computer Vision – ECCV 2012: 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012, Proceedings, Part II, A. Fitzgibbon, S. Lazebnik, P. Perona, Y. Sato, and C. Schmid, Eds., ed Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 414-429.
[14]P. J. Besl and R. C. Jain, "Three-dimensional object recognition," ACM Computing Surveys, vol. 17, pp. 75-145, 1985.
[15]F. Stein and G. Medioni, "Structural indexing: efficient 3-D object recognition," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 14, pp. 125-145, 1992.
[16]C. Chua and R. Jarvis, "Point Signatures: A New Representation for 3D Object Recognition," International Journal of Computer Vision, vol. 25, pp. 63-85, 1997.
[17]A. E. Johnson and M. Hebert, "Using spin images for efficient object recognition in cluttered 3D scenes," IEEE Trans., Pattern Anal. Mach. Intell., vol. 21, pp. 433-449, 1999.
[18]M. T. Suzuki, T. Kato, and N. Otsu, "A similarity retrieval of 3D polygonal models using rotation invariant shape descriptors," presented at the Systems, Man, and Cybernetics, 2000 IEEE International Conference on, 2000.
[19]G. Mamic and M. Bennamoun, "Representation and Recognition of 3D Free-Form Objects," Digital Signal Processing, vol. 12, pp. 47-76, 2002.
[20]D. Katsoulas, "Robust extraction of vertices in range images by constraining the Hough transform," in Pattern Recognition and Image Analysis, Proceedings. vol. 2652, F. J. Perales, Ed., ed Berlin: Springer-Verlag Berlin, 2003, pp. 360-369.
[21]E. Wahl, U. Hillenbrand, and G. Hirzinger, "Surflet-pair-relation histograms: a statistical 3D-shape representation for rapid classification," presented at the Proc. Fourth International Conf. 3-D Digital Imaging and Modeling, 2003.
[22]S. Yiyong, P. Joonki, A. Koschan, D. L. Page, and M. A. Abidi, "Point fingerprint: a new 3-D object representation scheme," in Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on vol. 33, ed, 2003, pp. 712-717.
[23]A. S. Mian, M. Bennamoun, and R. Owens, "Three-Dimensional Model-Based Object Recognition and Segmentation in Cluttered Scenes," IEEE Trans., Pattern Anal. Mach. Intell., vol. 28, pp. 1584-1601, 2006.
[24]A. S. Mian, M. Bennamoun, and R. A. Owens, "A Novel Representation and Feature Matching Algorithm for Automatic Pairwise Registration of Range Images," International Journal of Computer Vision, vol. 66, pp. 19-40, 2006.
[25]H. Chen and B. Bhanu, "3D free-form object recognition in range images using local surface patches," Pattern Recogn. Lett., vol. 28, pp. 1252-1262, 2007.
[26]R. B. Rusu, N. Blodow, Z. C. Marton, and M. Beetz, "Aligning point cloud views using persistent feature histograms," presented at the Intelligent Robots and Systems, 2008. IROS 2008. IEEE/RSJ International Conference on, 2008.
[27]P. Bariya and K. Nishino, "Scale-hierarchical 3D object recognition in cluttered scenes," in Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, 2010, pp. 1657-1664.
[28]A. Mian, M. Bennamoun, and R. Owens, "On the repeatability and quality of keypoints for local feature-based 3D object retrieval from cluttered scenes," International Journal of Computer Vision, vol. 89, pp. 348-361, 2010.
[29]K. Eunyoung and G. Medioni, "3D object recognition in range images using visibility context," presented at the Proc. International Conf. Intelligent Robots and Systems, 2011.
[30]H. V. Nguyen and F. Porikli, "Concentric ring signature descriptor for 3D objects," presented at the Proc. 18th IEEE International Conf. Image Processing, 2011.
[31]P. Heider, A. Pierre-Pierre, R. Li, R. Mueller, and C. Grimm, "Comparing local shape descriptors," The Visual Computer, vol. 28, pp. 919-929, 2012/09/01 2012.
[32]P. Guan and U. Neumann, "Training-Based Object Recognition in Cluttered 3D Point Clouds," in 3DV-Conference, 2013 International Conference on, 2013, pp. 87-94.
[33]S. Salti, F. Tombari, and L. Di Stefano, "SHOT: Unique signatures of histograms for surface and texture description," Computer Vision and Image Understanding, vol. 125, pp. 251-264, 2014.
[34]D. H. Ballard, "Generalizing the Hough transform to detect arbitrary shapes," Pattern Recognition, vol. 13, pp. 111-122, 1981.
[35]T. Zaharia and F. J. Preteux, "Hough transform-based 3D mesh retrieval," 2001.
[36]V. Bevilacqua, P. Casorio, and G. Mastronardi, "Extending Hough Transform to a Points’ Cloud for 3D-Face Nose-Tip Detection," presented at the Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence Lecture Notes in Computer Science, 2008.
[37]Y. T. Su and J. Bethel, "Detection and robust estimation of cylinder features in point clouds," San Diego, CA, 2010.
[38]B. Drost, M. Ulrich, N. Navab, and S. Ilic, "Model globally, match locally: Efficient and robust 3D object recognition," presented at the Proc. IEEE Conf. Computer Vision and Pattern Recognition, 2010.
[39]B. Drost and S. Ilic, "3D Object Detection and Localization Using Multimodal Point Pair Features," presented at the Proc. Second International Conf. 3D Imaging, Modeling, Processing, Visualization and Transmission, 2012.
[40]S. H. Chiu, C. Y. Wen, J. H. Lee, K. H. Lin, and H. M. Chen, "A Fast Randomized Generalized Hough Transform for Arbitrary Shape Detection," International Journal of Innovative Computing, Information and Control, vol. 8, pp. 1103-1116, 2012.
[41]B. E. Boser, I. M. Guyon, and V. N. Vapnik, "A training algorithm for optimal margin classifiers," presented at the Proceedings of the fifth annual workshop on Computational learning theory, Pittsburgh, Pennsylvania, USA, 1992.
[42]C. Cortes and V. Vapnik, "Support-Vector Networks," Mach. Learn., vol. 20, pp. 273-297, 1995.
[43]C. C. Chang and C. J. Lin, "LIBSVM: A library for support vector machines," ACM Trans. Intell. Syst. Technol., vol. 2, pp. 1-27, 2001.
[44]C. W. Hsu, C. C. Chang, and C. J. Lin, A practical guide to support vector classification, 2003.
[45]S. J. Dickinson, A. P. Pentland, and A. Rosenfeld, "From volumes to views: An approach to 3-D object recognition," CVGIP: Image Understanding, vol. 55, pp. 130-154, 1992.
[46]U. Uenohara and T. Kanade, "Geometric invariants for verification in 3-D object tracking," in Intelligent Robots and Systems '96, IROS 96, Proceedings of the 1996 IEEE/RSJ International Conference on, 1996, pp. 785-790 vol.2.
[47]M. Pontil and A. Verri, "Support vector machines for 3D object recognition," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, pp. 637-646, 1998.
[48]H. Byun and S. W. Lee, "Applications of Support Vector Machines for Pattern Recognition: A Survey," in Pattern Recognition with Support Vector Machines: First International Workshop, SVM 2002 Niagara Falls, Canada, August 10, 2002 Proceedings, S. W. Lee and A. Verri, Eds., ed Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 213-236.
[49]A. Smirnoff, E. Boisvert, and S. J. Paradis, "Support vector machine for 3D modelling from sparse geological information of various origins," Computers & Geosciences, vol. 34, pp. 127-143, 2008.
[50]Z.-C. Marton, L. Goron, R. B. Rusu, and M. Beetz, "Reconstruction and Verification of 3D Object Models for Grasping," in Robotics Research: The 14th International Symposium ISRR, C. Pradalier, R. Siegwart, and G. Hirzinger, Eds., ed Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 315-328.
[51]A. Aldoma, F. Tombari, L. Stefano, and M. Vincze, "A Global Hypotheses Verification Method for 3D Object Recognition," in Computer Vision – ECCV 2012: 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012, Proceedings, Part III, A. Fitzgibbon, S. Lazebnik, P. Perona, Y. Sato, and C. Schmid, Eds., ed Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 511-524.
[52]M. Zhang, G. Jiang, C. Wu, and L. Quan, "Horizontal plane detection from 3D point clouds of buildings," Electronics Letters, vol. 48, pp. 764-765, 2012.
[53]K. S. Choi and D. H. Kim, "Angular-partitioned spin image descriptor for robust 3D facial landmark detection," Electronics Letters, vol. 49, pp. 1454-1455, 2013.
[54]A. W. Vieira, P. L. J. Drews, and M. F. M. Campos, "Spatial Density Patterns for Efficient Change Detection in 3D Environment for Autonomous Surveillance Robots," IEEE Transactions on Automation Science and Engineering, vol. 11, pp. 766-774, 2014.
[55]S. Smith and I. Williams, "A Statistical Method for Improved 3D Surface Detection," IEEE Signal Processing Letters, vol. 22, pp. 1045-1049, 2015.
[56]D. Blow, "To fit a plane to a set of points by least squares," Acta Crystallographica, vol. 13, p. 168, 1960.
[57]P. J. Besl and N. D. McKay, "A method for registration of 3-D shapes," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 14, pp. 239-256, 1992.
[58]C. J. C. Burges, "A Tutorial on Support Vector Machines for Pattern Recognition," Data Min. Knowl. Discov., vol. 2, pp. 121-167, 1998.
[59]R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin, "Shape distributions," ACM Trans. Graph., vol. 21, pp. 807-832, 2002.
[60]H. Samet and A. Kochut, "Octree approximation and compression methods," presented at the 3D Data Processing Visualization and Transmission, 2002. Proceedings. First International Symposium on, 2002.
[61]N. Gelfand, N. J. Mitra, L. J. Guibas, and H. Pottmann, "Robust global registration," presented at the Proceedings of the third Eurographics symposium on Geometry processing, Vienna, Austria, 2005.
[62]P. Gao, A. Li, Y. Lu, J. Wang, N. Li, and W. Yu, "Adaptive Mesh Simplification Using Vertex Clustering with Topology Preserving," presented at the Computer Science and Software Engineering, 2008 International Conference on, 2008.
[63]C. Papazov and D. Burschka, "An Efficient RANSAC for 3D Object Recognition in Noisy and Occluded Scenes," in Computer Vision – ACCV 2010. vol. 6492, R. Kimmel, R. Klette, and A. Sugimoto, Eds., ed: Springer Berlin Heidelberg, 2011, pp. 135-148.