在三維物體偵測的研究中，如何有效地擷取特徵是一個重要的課題。利用描述物體的區域性特徵已被視為是一種很有用的方法，然而，冗餘的計算量使得這類區域性的方法無法有效地應用在實際工作上。本論文提出一種快速的「區域樹狀描述子」方法，可用於擷取區域特徵和定義所謂的區域範圍。此方法不但減少了計算特徵時的搜尋時間，並且完整保留了區域的資料。一個區域樹狀描述子包含了兩個不同的樹狀結構資料：用來擷取區域特徵的「網格樹」與用來決定網格樹層級的「點樹」。我們所提出的方法可快速篩選出符合特徵的目標物，之後，再利用我們提出的「立方體疊合 (cube superimposition)」法來確認所選出的目標物。此外，為了精確地定位物體，本論文還提出一個改良自傳統疊代最近點法 (Iterative Closest Point) 的「立方體疊代最近點法 (Cube ICP)」方法，此方法大量減少了計算的時間，並且提高了定位的精確度。最後，從實驗結果中可知本論文的方法比過去的方法能更快速精確地偵測與定位目標物。

Feature extraction plays an important role in 3D object detection. Local feature description has been shown as a kind of useful feature extraction methods. However, the tedious computation of local feature descriptors makes them awkward in practical applications. In this thesis, a fast Local Tree-Structure Description (LTD) method is proposed to extract local features and define a so-called local area. A local tree-structure descriptor includes two tree structures: mesh trees and point trees. Mesh trees are used to extract local features, while point trees are used to decide the levels of mesh trees. With the proposed method, we can quickly sift some candidate targets. Then, we use a novel cube-superimposed method to verify those targets. Furthermore, we also propose an improved Iterative Closest Point (Cube ICP) algorithm for pose alignment. The Cube ICP algorithm can reduce the computation time and increase the accuracy. Experimental results show that our method can detect and register target objects more quickly and accurately than previous works.

[1] Heider, P., Pierre-Pierre, A., Li, R., Mueller, R., and Grimm, C., “Comparing local shape descriptors”, The Visual Computer, Vol.28, No. 9, pp. 919-929 (2012)
[2] Nguyen, H. V. and Porikli, F., “Concentric ring signature descriptor for 3D objects”, Proceedings of 18th IEEE International Conference on Image Processing (ICIP), pp. 2893 - 2896 (2011)
[3] Ong, J. L., Seghouane, A. K., “From point to local neighborhood: Polyp detection in ct colonography using geodesic ring neighborhoods”, IEEE Transactions on Image Processing, Vol.20, No. 4, pp. 1000-1010 (2011)
[4] Drost, B., Ulrich, M., Navab, N., and Ilic, S., “Model globally, match locally: Efficient and robust 3D object recognition”, Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 998 - 1005 (2010)
[5] Su, Y. T. and Bethel, J., “Detection and robust estimation of cylinder features in point clouds”, Proceedings of ASPRS Annual Conference on Opportunities for Emerging Geospatial Technologies (2010)
[6] Mian, A, Bennamoun, M., and Owens, R., “On the repeatability and quality of keypoints for local feature-based 3d object retrieval from cluttered scenes”, International Journal of Computer Vision, Vol. 89, No. 2-3, pp. 348-361 (2010)
[7] Rusu, R. B., Blodow, N., Marton, Z. C., and Beetz, M., “ Aligning point cloud views using persistent feature histograms”, Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3384 – 3391 (2008)
[8] Gao, P., Li, A., Lu, Y., Wang, J., Li, N., and Yu, W., “Adaptive mesh simplification using vertex clustering with topology”, Proceedings of International Conference on Computer Science and Software Engineering, Vol. 2, pp. 971 – 974 (2008)
[9] Hui, C. and Bir, B. “3D free-form object recognition in range images using local surface patches”, Pattern Recognition Letters, Vol.28, No. 10, pp. 1252-1262 (2007)
[10] Mian, A. S, Bennamoun, M., and Owens, R. A., “Three-dimensional model-based object recognition and segmentation in cluttered scenes”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 28, No. 10, pp. 1584-1601 (2006)
[11] Mian, A. S, Bennamoun, M., and Owens, R. A., “A novel representation and feature matching algorithm for automatic pairwise registration of range images”, International Journal of Computer Vision, Vol. 66, No. 1, pp. 19-40 (2006)
[12] Gelfand, N., Mitra, N. J., Leonidas, J. G., and Helmut, P., “Robust global registration”, Proceedings of Eurographics Symposium on Geometry Processing, (2005)
[13] Mian, A. S, Bennamoun, M., and Owens, R. A., “Automatic multiview coarse registration of range images for 3D modeling”, IEEE Conference on Cybernetics and Intelligent Systems, Vol. 1, pp. 158 – 163 (2004)
[14] Andrea, F., Daniel, H., Ravi, K., Thomas, B., and Jitendra, M., “Recognizing objects in range data using regional point descriptors”, Proceedings of 8th European Conference on Computer Vision, Vol. 3023, pp. 224-237 (2004)
[15] Sun, Y., Paik, J., Koschan, A., Page, D. L., and Abidi, M. A., “Point fingerprint: A new 3-d object representation scheme”, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 33, No. 4, pp. 712-717 (2003)
[16] Katsoulas, D., “Robust extraction of vertices in range images by constraining the hough transform”, Pattern Recognition and Image Analysis, Vol. 2652, pp. 360-369 (2003)
[17] Wahl, E., Hillenbrand, U., and Hirzinger, G., “Surflet-pair-relation histograms: a statistical 3D-shape representation for rapid classification” , Proceedings of 4th International Conference on 3-D Digital Imaging and Modeling (3DIM), pp. 474-481 (2003)
[18] Yamany, S. M. and Farag, A. A., “Surface signatures: An orientation independent free-form surface representation scheme for the purpose of objects registration and matching”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, No. 8, pp. 1105-1120 (2002)
[19] Samet, H. and Kochut, A., “Octree approximation and compression methods”, Proceedings of the 1th International Symposium on 3D Data Processing Visualization and Transmission , pp. 460-469 (2002)
[20] Zaharia, T. and Preteux, F. J., “Hough transform-based 3D mesh retrieva”, Proceedings of International Symposium on Optical Science and Technology, pp. 175-185 (2001)
[21] Zhang, C. and Chen, T., “Efficient feature extraction for 2D/3D objects in mesh representation”, Proceedings of International Conference on Image Processing, Vol. 3, pp. 935 - 938 (2001)
[22] Osada, R., Funkhouser, T., Chazelle, B., and Dobkin, D., “ Matching 3D models with shape distributions”, Proceedings of International Conference on Shape Modeling and Applications, pp. 154 - 166 (2001)
[23] Suzuki, M. T., Kato, T., and Otsu, N., “ A similarity retrieval of 3D polygonal models using rotation invariant shape descriptors”, Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, Vol. 4, pp. 2946 - 2952 (2000)
[24] Johnson, A. E. and Hebert, M., “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 (1999)
[25] Chin, C. S. and Ray, J., “Point signatures: A new representation for 3d object recognition”, International Journal of Computer Vision, Vol. 25, No. 1, pp. 63-85 (1997)
[26] Stein, F. and Medioni, G., “Structural indexing: Efficient 3-D object recognition”, IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. 14, No. 2, pp. 125-145 (1992)
[27] Besl, P. J. and McKay, N. D., “Method for registration of 3-D shapes”, Proceedings of SPIE 1611, Sensor Fusion IV: Control Paradigms and Data Structures, Vol. 1611 (1992)