迭代最近點演算法是一種用來將兩群點集合對齊的方法，常使用於 2D 和 3D 幾何圖形的對齊。本論文使用機器人搭載雷射測距儀收集雷射資料，透過其掃描資訊作為點集合資訊，再使用迭代最近點演算法疊合，完成一個未知環境地圖的建立。但原始 ICP 演算法容易因為雜訊和離散點的關係，使得對齊效果不準確，尤其是在連續掃描的狀況下，對齊誤差越大，導致疊合精確度低和運算時間龐大。故本論文提出基於增強型ICP演算法實現於雲端運算架構，將原本序列進行所有雷射資料的過程，提出一分散式計算架構，使得所有雷射資料可以透過平行化的過程進行增強型ICP演算法，此演算法可大幅降低計算負擔並提升對齊的精確度，獲得更準確的環境地圖。接著將單機器人延伸至多機器人系統，將增強型ICP演算法結合加速強健特徵法，主要利用影像資訊判斷多機器人是否於相同的環境，在未滿足影像特徵門檻值前，單機器人將於各自的環境建立區域地圖，一旦滿足特徵匹配後，將多機器人的區域地圖資訊再以增強型ICP演算法疊合，進而增加建圖的效率。

The Iterative Closest Point algorithm (ICP) is to align the two point set, which is widely used in 2D and 3D geometric figure alignments. By using a Laser Range Finder (LRF) to collect data, it is capable of building a map in uncertain environments through a mobile robot. However, the original ICP algorithm can be easily affected by noise and discrete points, thus, increasing the error of alignment. In a row scanning by the laser date, the more data points are accumulated, the larger the errors of alignment become, which leads to an unpreferable map, and the process would be time consuming. This thesis proposes a cloud computing architecture based on Enhanced ICP, which parallelizes the original procedure. By doing so, it can significantly reduce the computational burden, improve the accuracy of alignment, and provide a more accurate environmental map. Furthermore, this thesis improves the use of a single robot to multi-robot system which combines the ICP alignment and Speeded Up Robust Features (SURF), resulting in increasing the efficiency of map building.

[1] P. Besl and N. McKay, “A method for registration of 3-D shapes,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 14, no. 2, pp. 239-256, 1992.
[2] J. Minguez, F. Lamiraux, and L. Montesano, “Metric-based scan matching algorithms for mobile robot displacement estimation,” Proc. IEEE Int. Conf. on Robotics and Automation, Spain, 2005, pp. 3557-3563.
[3] L. Zhang, S.-I. Choi, and S.-Y. Park, “Robust ICP registration using biunique correspondence,” Proc. IEEE Int. Conf. on 3D Imaging, Modeling, Processing, Visualization and Transmission, South Korea, 2011, pp. 80-85.
[4] D. Chetverikov, D. Svirko, D. Stepanov, and P. Krsek, “The trimmed iterative closest point algorithm,” Proc. IEEE Int. Conf. Pattern Recognition, Quebec City, 2002, pp. 545-548.
[5] M. Tomono, “Robust robot localization and map building using a global scan matching method,” Proc. IEEE Int. Conf. on Intelligent Robots and Systems, Japan, 2004, pp. 1059-1064.
[6] F. Lu and E. Milios, “Globally consistent range scan alignment for environment mapping,” Autonomous Robots, vol. 4, no. 4, pp. 333-349, Oct. 1997.
[7] K. S. Arun, T. S. Huang, and S. D. Bostein, “Least-square fitting of two 3-D point sets,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 9, no. 5, pp. 698-700, Sept. 1987.
[8] B. K. P. Horn, “Closed-form solution of absolute orientation using unit quaternion,” Journal of the Optical Society of America A, vol. 4, no. 4, pp. 629-642, April 1987.
[9] B. K. P. Horn, H. M. Hilden, and S. Negahdaripour, “Closed-form solution of absolute orientation using orthonormal matrices,” Journal of the Optical Society of America A, vol. 5, no.7, pp. 1127-1136, July 1988.
[10] M. Walker, L. Shao, and R. Volz, “Estimating 3-D location parameters using dual number quaternions,” CVGIP: Image Understanding, vol. 54, no. 3, pp. 358-367, Nov. 1991.
[11] 林映辰，大型三維重建之模型對齊-使用Velodyne雷射掃描儀，碩士論文，高雄大學資訊工程學系，民國100年。
[12] Z. Zhang, “Iterative point matching for registration of free-form curves and surfaces,” International Journal of Computer Vision, vol. 13, no. 2, pp. 119-152, 1994.
[13] A. Segal, D. Haehnel, and S. Thrun, “Generalized-icp,” Proc. of Robotics: Science and Systems, USA, 2009, pp. 26-27.
[14] C.-C. Hsu, H.-E. Chang, and Y.-Y Lu, “Map building of unknown environment using PSO-tuned enhanced iterative closest point algorithm,” Proc. IEEE Int. Conf. on System Science and Engineering, Budapest, Hungary, 2013, pp. 279-284.
[15] J. Dean and S. Ghemawat, “MapReduce: simplified data processing on large clusters,” Symposium on Operating System Design and Implementation, San Francisco, CA, Dec. 2004.
[16] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The google file system,” 19th ACM Symposium on Operating Systems Principles, Lake George, NY, Oct. 2003.
[17] F. Chang, J. Dean, S. Ghemawat, W. Hsieh, D. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber, “Bigtable: a distributed storage system for structured data,” Symposium on Operating System Design and Implementation, Seattle, WA, Nov. 2006.
[18] HDFS, https://hadoop.apache.org/docs/r1.2.1/hdfs_design.html
[19] S. Liu and X. Xie, “Research on algorithm of point cloud MapReduce registration,” Proc. IEEE Int. Conf. on Cloud Computing and Intelligence Systems, Beijing, 2011, pp. 338-341.
[20] L. Parker, “Current state of the art in distributed autonomous mobile robots,” Proc. Distributed Autonomous Robotic Systems 4, Tokyo, 2000, pp. 3-12.
[21] A. Birk and S. Carpin, “Merging occupancy grid maps from multiple robots,” Proceedings of the IEEE, vol. 94, no. 7, pp. 1384-1397, July 2006.
[22] S. Carpin, “Fast and accurate map merging for multi-robot systems” Autonomous Robots, vol. 25, no. 3, pp. 305-316, 2008.
[23] S. Thrun, “Learning occupancy grids maps with forward sensor models,” Autonomous Robots, vol. 15, no. 2, pp. 111-127, 2003.
[24] M. Dissanayake, P. Newman, S. Clark, H. Whyte, and M. Csorba, “A solution to the simultaneous localization and map building (SLAM) problem,” IEEE Trans. on Robotics and Automation, vol. 17, no. 3, pp. 229-241, 2001.
[25] H. Whyte and T. Bailey, “Simultaneous localization and mapping: Part I,” IEEE Robotics and Automation Magazine, vol. 13, no. 2, pp. 99-110, 2006.
[26] A. Howard, “Multi-robot simultaneous localization and mapping using particle filters,” International Journal of Robotics Research, vol. 25, no. 12, pp. 1243-1256, 2006.
[27] D. Fox, J. Ko, K. Konolige, B. Limketkai, D. Schulz, and B. Stewart, “Distributed multirobot exploration and mapping,” Proceedings of the IEEE, vol. 94, no. 7, pp. 1325-1339, July 2006.
[28] W. Xu, R. Jiang, and Y. Chen, “Map alignment based on PLICP algorithm for multi-robot SLAM,” Proc. IEEE International Symposium on Industrial Electronics, Hangzhou, May 2012, pp. 926-930.
[29] R. Kaushik, J. Xiao, W. Morris, and Z. Zhu, “3D laser scan registration of dual-Robot system using vision,” Proc. IEEE Int.Con.on Intelligent Robots and Systems, USA, Oct. 2009, pp. 4148-4153.
[30] M. Elliott, W. Morris, A. Calle, and J. Xiao, “City-climbers at work,” Proc. IEEE Int. Con. on Robotics and Automation, Roma, Italy, April 2007, pp. 2764-2765.
[31] R. Haralick, C.-N. Lee, K. Ottenberg, and M. Nolle, “Analysis and solutions of the three point perspective pose estimation problem,” Proc. of Computer Vision and Pattern Recognition, Maui, HI, Jun. 1991, pp. 592-598.
[32] Z. Li, S. Jafri, and R. Chellali, “Visual place recognition for multi-robots maps merging,” Proc. IEEE Int. Symposium on Safety, Security, and Rescue Robotics, College Station, TX, Nov. 2012, pp. 1-6.
[33] M. Ozuysal, M. Calonder, V. Lepetit, and P. Fua, “Fast keypoint recognition using random ferns,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 32, no. 3, pp. 448-461, March 2010.
[34] V. Lepetit and P. Fua, “Keypoint recognition using randomized trees,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 28, no. 9, pp. 1465-1479, Sept. 2006.
[35] K. Wang, S. Jia, Y. Li, X. Li, and B. Guo, “Research on map merging for multi-robotic system based on RTM,” Proc. IEEE Int. Con. on Information and Automation, Shenyang, China, June 2012, pp. 156-161.
[36] S. Jia, T. Murakami, D. Chugo, and K. Takase, “Interactive robot system for supporting object acquisition based on robot technology middleware,” Proc. IEEE Int. Con. on Information and Automation, China, June 2008, pp. 966-971.
[37] S. S. Ge, Q. Zhang, A. T. Abraham, and B. Rebsamen, “Simultaneous path planning and topological mapping for environment exploration and goal oriented navigation,” Robotics and Autonomous Systems, vol. 59, no.3-4, pp. 228-242, March 2011.
[38] A. T. Abraham, S. S. Ge, and P. Y. Tao, “A topological approach of path planning for autonomous robot navigation in dynamic environments,” Proc. IEEE Int. Con. on Intelligent Robots and Systems, Louis, USA, Oct. 2009, pp.4907-4912.
[39] H. Bay, A. Ess, T. Tuytelaars, and L. V. Gool, “Speeded-up robust features,” Computer Vision and Image Understanding, vol. 110, no. 3, pp. 346-359, June 2008.
[40] D. G. Lowe, “Object recognition from local scale-invariant features,” Proc. IEEE Int. Conf. on Computer Vision, Corfu, Sept. 1999, pp. 1150-1157.
[41] SIFT和SURF比較，http://blog.csdn.net/jwh_bupt/article/details/6567452
[42] R. Lienhart and J. Maydt, “An extended set of haar-like features for rapid object detection,” Proc. IEEE Int. Conf. on Image Processing, USA, 2002, pp. 900-903.
[43] HBase architecture, http://wuce7758.iteye.com/blog/1747214
[44] HBase,http://www.cyanny.com/2014/03/13/hbase-architecture-analysis-part1-logical-architecture/
[45] N. Dimiduk and A. Khurana, HBase in Action. Shelter Island, 2013.
[46] Webots, https://www.cyberbotics.com/
[47] Mobile Robot, http://www.mobilerobots.com/Mobile_Robots.aspx
[48] SICK, http://www.sick.com.tw/index.asp