近年來，因無人船相關技術發展成熟，在多個領域中均被廣泛地運用，已儼然
成為未來的發展趨勢之一，順應該趨勢，如何產生一避碰路徑亦成為當今火熱的議
題。在過往的研究中，路徑規劃的演算法大多採用A*與Finite Angle A*，然而這
兩類均為事先規劃的演算法，航行路徑為出船前事先由岸上電腦計算完畢，無人船
則依該路徑行駛，然而該路徑規劃方法無法在航行中偵測到障礙物時即時重新規
劃路徑。有鑑於該缺陷，本文結合了船上相機並嘗試規劃可以在無人船航行中即時
修正航行路線的演算法。
於影像部分中，障礙物偵測演算法可透過結合水平集與核密度估計實現，這兩
種方法均為既有方法，而本文則致力於提升演算法計算速度以符合無人船路徑須
不斷更新的即時性，其中在水平集方面本文提出了初始值與停止條件的選取方法，
在核密度估計中則提出了一個新的核，透過上述改善方向可改善計算量過大的問
題；於路徑規劃中，一開始先採用出船前產生的路徑，於航行中再開啟障礙物偵測
演算法，當偵測到障礙物則自動重新規畫一個避碰路線。透過上述步驟無人船的即
時避碰路線規劃得以實現。

In recent years, unmanned surface vehicles (USVs) have drawn attention around the world since the USVs have various applications in several fields. In line with the trend of the times, how to plan a collision-free path is one of the most well-discussed things in the recent study. In the previous study, A* and finite angle A* are widely applied in path planning. However, both of them belong to offline path planning, i.e. the path is generated before setting sail and the path is not able to be revised when an obstacle is detected. Thus, this thesis tries to give the online collision-free path by combining the camera on the USVs.
In the image part, the obstacle detection algorithm is realized by combing the level set method and kernel density estimation. Both two methods have been proposed in the previous study. But a new way to determine the initial conditions and stop conditions for the level set method, and a new kernel for kernel density estimation are proposed to increase the computation efficiency. In the path planning part, an offline collision-free path is generated at first. Whenever an obstacle is detected by the obstacle detection algorithm, the path is revised automatically. These processes ensure that an online collision-free path can be realized.

[1] E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische mathematik, vol. 1, no. 1, pp. 269-271, 1959.
[2] P. E. Hart, N. J. Nilsson, and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths," IEEE transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968.
[3] S. Russell and P. Norvig, "Artificial intelligence: a modern approach," 2002.
[4] J. Yao, C. Lin, X. Xie, A. J. Wang, and C.-C. Hung, "Path planning for virtual human motion using improved A* star algorithm," in 2010 Seventh international conference on information technology: new generations, 2010: IEEE, pp. 1154-1158.
[5] E. A. Hansen and R. Zhou, "Anytime heuristic search," Journal of Artificial Intelligence Research, vol. 28, pp. 267-297, 2007.
[6] A. Botea, M. Müller, and J. Schaeffer, "Near optimal hierarchical path-finding," J. Game Dev., vol. 1, no. 1, pp. 1-30, 2004.
[7] Y. H. Chen, Y. Y. Chen, and J. M. Yang, "Path Planning for Unmanned Surface Vessels with Multisensor Fusion Design," Sensors and Materials, vol. 31, no. 3, pp. 889-903, 2019.
[8] A. Elgammal, D. Harwood, and L. Davis, "Non-parametric model for background subtraction," in European conference on computer vision, 2000: Springer, pp. 751-767.
[9] A. Elgammal, R. Duraiswami, D. Harwood, and L. S. Davis, "Background and foreground modeling using nonparametric kernel density estimation for visual surveillance," Proceedings of the IEEE, vol. 90, no. 7, pp. 1151-1163, 2002.
[10] D. A. Reynolds, "Gaussian Mixture Models," Encyclopedia of biometrics, vol. 741, pp. 659-663, 2009.
[11] C. E. Rasmussen, "The infinite Gaussian mixture model," in NIPS, 1999, vol. 12, pp. 554-560.
[12] Z. Zivkovic, "Improved adaptive Gaussian mixture model for background subtraction," in Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004., 2004, vol. 2: IEEE, pp. 28-31.
[13] C. Li, C. Xu, C. Gui, and M. D. Fox, "Distance regularized level set evolution and its application to image segmentation," IEEE transactions on image processing, vol. 19, no. 12, pp. 3243-3254, 2010.
[14] X.-F. Wang, D.-S. Huang, and H. Xu, "An efficient local Chan–Vese model for image segmentation," Pattern Recognition, vol. 43, no. 3, pp. 603-618, 2010.
[15] D. N. Thanh, N. N. Hien, V. S. Prasath, and N. H. Hai, "Automatic initial boundary generation methods based on edge detectors for the level set function of the Chan-Vese segmentation model and applications in biomedical image processing," in Frontiers in Intelligent Computing: Theory and Applications: Springer, 2020, pp. 171-181.
[16] P. Getreuer, "Chan-vese segmentation," Image Processing On Line, vol. 2, pp. 214-224, 2012.
[17] J. Yonghong, "Digital image processing (The Second Edition)," ed: Wu Han China: Wu Han university press, 2010.
[18] S. Wang and K. Yang, "An image scaling algorithm based on bilinear interpolation with VC++," Techniques of Automation and Applications, vol. 27, no. 7, pp. 44-45, 2008.
[19] R. Keys, "Cubic convolution interpolation for digital image processing," IEEE transactions on acoustics, speech, and signal processing, vol. 29, no. 6, pp. 1153-1160, 1981.
[20] N. Otsu, "A threshold selection method from gray-level histograms," IEEE transactions on systems, man, and cybernetics, vol. 9, no. 1, pp. 62-66, 1979.
[21] D. Marr and E. Hildreth, "Theory of edge detection," Proceedings of the Royal Society of London. Series B. Biological Sciences, vol. 207, no. 1167, pp. 187-217, 1980.
[22] I. Sobel and G. Feldman, "A 3x3 isotropic gradient operator for image processing," a talk at the Stanford Artificial Project in, pp. 271-272, 1968.