臺灣博碩士論文加值系統

在本論文中，我們提出了一個用影像為行動機器人建立階層式地圖以達到快速定位之目標的系統。上層的地圖為一用圖形(graph)來表式的拓樸式地圖，因為此類地圖較適用於大環境。在這個地圖中，每個節點(vertex)由可以快速辨識其在整個環境中的那個地方(Place)的影像資訊所組成，而邊(edge)代表這些地方(Place)的空間關係。在此之後，我們會在每個節點之內建立一個以座標表示的地圖，其建立方式為影像資訊和由其他感應器得到的座標所成的對應。建完此地圖之後，可用即可利用兩個步驟達到快速定位的目標：首先，找出用來搜尋的影像落在那個地方(Place)；再者，比對出此地方(Place)中與用來搜尋的影像最相像的影像，並傳回其所附之座標。

In our thesis, we propose a system to make the mobile robot building a vision-based hierarchical map and then quickly localizing itself by this map. In learning stage, each image The top-level map is a topological map which is represented as the graph because of the fitness of the large-scale environments. In this map, the vertices comprise some visual information for efficiently identifying the places of the robot''s environment and the edges denote the spatial relation between these places. Then, we construct a small metric map attached each node of the topological map. After this two steps, the robot can localize itself by this hierarchical map effectively and robustly.

口試委員審定書 I
誌謝 II
摘要 III
Abstract IV
List of Figures VIII
List of Tables XI
1 Introduction 1
1.1 Motivation 1
1.2 Literature Review 2
1.3 Thesis Organization 4
1.4 Contribution 5
2 Preliminaries 6
2.1 System Overview 6
2.2 Feature Extraction in Computer Vision 7
2.2.1 Feature Detection 8
2.2.2 Feature Description 9
2.3 Scale Invariant Feature Transform (SIFT) 10
2.3.1 Scale Invariant Feature Detection 11
2.3.2 Feature Descriptor 13
3 Visual Information for Place Identification 16
3.1 Diagram of Clustering 18
3.2 Image Segmentation 19
3.3 Segment Encoding 20
3.3.1 Color Space Traslation 24
3.3.2 Expand Color Histogram 24
3.3.3 Measurement of Dissimilarity 25
3.4 Methodology of Clustering 26
4 Database Management and Localization 28
4.1 Diagram of Map Building 29
4.2 Image Representation 31
4.2.1 Scale Invariant Fearure Transform 32
4.2.2 Inverted Index 33
4.3 Databse Management 35
4.3.1 Top-level Database 36
4.3.2 Bottom-level Database 37
4.4 Robust Localization 38
4.4.1 The Diagram of Localization 38
4.4.2 Place Identify 39
4.4.3 Robust Localization 40
5 Experiments 42
5.1 Experimental Settings and Environment 42
5.1.1 Hardware of the Experimental System(Tour Guide Robot) 42
5.1.2 Hardware of the Experimental System(Home Robot) 44
5.1.3 Experimental Environment 45
5.2 Performance Evaluation 46
5.2.1 The Performance of Clustering 46
5.2.2 Performance of Image Recognition 48
5.2.3 Performance of Global Localization 51
6 Conclusion and Future Work 54
6.1 Conclusion 54
6.2 Future Work 55
Bibliography 56

[1] H. Asoh, Y. Motomura, F. Asano, I. Hara, S. Hayamizu, K. Itou, T. Kurita, T. Matsui, N. Vlassis, R. Bunschoten, et al. Jijo-2: An Office Robot That Communicates and Learns. 2001.
[2] R. Siegwart, K.O. Arras, S. Bouabdallah, D. Burnier, G. Froidevaux, X. Greppin, B. Jensen, A. Lorotte, L. Mayor, M. Meisser, et al. Robox at Expo. 02: A large-scale installation of personal robots. Robotics and Autonomous Systems,
42(3-4):203–222, 2003.
[3] L. Armesto, G. Ippoliti, S. Longhi, and J. Tornero. FastSLAM 2.0: Least-Squares Approach. IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5013–5018, 2006.
[4] Chieh-Chih Wang. Simultaneous Localization, Mapping and Moving Object Tracking. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, April 2004.
[5] T. Jost and H. Hugli. A multi-resolution scheme icp algorithm for fast shape registration. In Proceedings First International Symposium on 3D Data Processing
Visualization and Transmission, 2002, pages 540–543, 2002.
[6] P. Newman, D. Cole, and K. Ho. Outdoor slam using visual appearance an laser ranging. In Robotics and Automation, 2006. ICRA 2006. Proceedings 2006 IEEE International Conference on, pages 1180–1187, 2006.
[7] Junqiu Wang, Hongbin Zha, and R. Cipolla. Coarse-to-fine vision-based localization by indexing scale-invariant features. Systems, Man, and Cybernetics, Part B, IEEE Transactions on, 36(2):413–422, April 2006. ISSN 1083-4419.
[8] D. Lowe. Distinctive image features from scale-invariant keypoints. In International Journal of Computer Vision, volume 20, pages 91–110, 2003.
[9] Herbert Bay, Tinne Tuytelaars, and Luc Van Gool. Surf: Speeded-up robust features. In 9th European Conference on Computer Vision, Graz, Austria.
[10] P.J. Besl and H.D. McKay. A method for registration of 3-d shapes. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 14(2):239–256, Feb 1992. ISSN 0162-8828.
[11] Junqiu Wang, Junqiu Wang, R. Cipolla, and Hongbin Zha. Vision-based global localization using a visual vocabulary. In R. Cipolla, editor, Proc. IEEE International Conference on Robotics and Automation ICRA 2005, pages 4230–4235, 2005.
[12] Robert Sim and Gregory Dudek. Learning environmental features for pose estimation. Image Vision Comput., 19(11):733–739, 2001.
[13] Benjamin Kuipers Emilio Remolina. Towards a general theory of topological maps. Artificial Intelligence, 2004.
[14] H. Choset, H. Choset, and K. Nagatani. Topological simultaneous localization and mapping (slam): toward exact localization without explicit localization. 17 (2):125–137, 2001. ISSN 1042-296X.
[15] D. Crisan and A. Doucet. A survey of convergence results on particle filtering for practitioners, 2002.
[16] M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit. Fastslam: A factored solution to the simultaneous localization and mapping problem. In Proceedings of the AAAI National Conference on Artificial Intelligence, Edmonton, Canada, 2002. AAAI.
[17] Hans P. Moravec. Sensor fusion in certainty grids for mobile robots. AI Magazine, 1988.
[18] B. Kuipers, J.Modayil, P. Beeson, M. MacMahon, and F. Savelli. Local metrical and global topological maps in the hybrid spatial semantic hierarchy. Robotics and Automation, 2004. Proceedings. ICRA’04. 2004 IEEE International Conference on, 5.
[19] J. Wolf, J. Wolf, W. Burgard, and H. Burkhardt. Robust vision-based localization for mobile robots using an image retrieval system based on invariant features. In W. Burgard, editor, Proc. IEEE International Conference on Robotics
and Automation ICRA ’02, volume 1, pages 359–365 vol.1, 2002.
[20] T. Starner, T. Starner, B. Schiele, and A. Pentland. Visual contextual awareness in wearable computing. In B. Schiele, editor, Proc. Digest of Papers Wearable Computers Second International Symposium on, pages 50–57, 1998.
[21] Loic Lacheze, Loic Lacheze, and Ryad Benosman. Visual localization using an optimal sampling of bags-of-features with entropy applied to repeatable test methods. In Ryad Benosman, editor, Proc. IEEE/RSJ International Conference
on Intelligent Robots and Systems IROS 2007, pages 1332–1338, 2007.
[22] J. Wang, R. Cipolla, and H. Zha. Vision-based Global Localization Using a Visual Vocabulary. Robotics and Automation, 2005. Proceedings of the 2005 IEEE International Conference on, pages 4230–4235, 2005.
[23] C. Harris and M. Stephens. A combined corner and edge detector. Alvey Vision Conference, 15:50, 1988.
[24] T. Lindeberg. Feature Detection with Automatic Scale Selection. International Journal of Computer Vision, 30(2):79–116, 1998.
[25] K. Mikolajczyk and C. Schmid. Scale & Affine Invariant Interest Point Detectors. International Journal of Computer Vision, 60(1):63–86, 2004.
[26] LMJ Florack, BM Ter Haar Romeny, JJ Koenderink, and MA Viergever. General intensity transformations and differential invariants. Journal of Mathematical Imaging and Vision, 4(2):171–187, 1994.
[27] WT Freeman and EH Adelson. The design and use of steerable filters. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 13(9):891–906, 1991.
[28] P.F. Felzenszwalb and D.P. Huttenlocher. Efficient Graph-Based Image Segmentation. International Journal of Computer Vision, 59(2):167–181, 2004.
[29] A. Torralba, KP Murphy, WT Freeman, and MA Rubin. Context-based vision system for place and object recognition. Computer Vision, 2003. Proceedings.
Ninth IEEE International Conference on, pages 273–280, 2003.
[30] I. Ulrich and I. Nourbakhsh. Appearance-based place recognition for topological localization. PROC IEEE INT CONF ROB AUTOM, 2:1023–1029, 2000.
[31] C. Siagian and L. Itti. Rapid Biologically-Inspired Scene Classification Using Features Shared with Visual Attention. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, pages 300–312, 2007.
[32] H. Greenspan, J. Goldberger, and L. Ridel. A continuous probabilistic framework for image matching. Computer Vision and Image Understanding, 84(3): 384–406, 2001.
[33] J. Sivic and A. Zisserman. Video Google: a text retrieval approach to object matching in videos. Computer Vision, 2003. Proceedings. Ninth IEEE International
Conference on, pages 1470–1477, 2003.
[34] T. Kanungo, D.M. Mount, N.S. Netanyahu, C.D. Piatko, R. Silverman, and A.Y. Wu. An Efficient k-Means Clustering Algorithm: Analysis and Implementation. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, pages 881–892, 2002.