運動風氣的提升帶動運動相關應用程式的興起，其中許多跑步應用程式能夠設定路線、目標，也可以記錄運動軌跡，但這些應用程式都無法自動為使用者規劃路線，無法滿足那些具有訓練需求，想要特定高低起伏或趣味性形狀路線的使用者。

鑒於先前鮮少有針對路網形狀或高度的路徑比對研究，本論文提出一套能針對特定區域自動尋找符合使用者要求路線之演算法。本文分為兩部分，第一部分是在平面二維空間中，使用者給定一張物件圖像，接著分別對物件和背景進行特徵點提取，再使用遮罩過濾雜訊後的形狀上下文進行特徵點比對，在比對區域內找出一段封閉路線近似於物件圖像輪廓；第二部分是對三維空間中的高度，根據使用者期望的路線總長度及路線高度的變化，對背景進行內插搜尋篩選路線，之後使用動態時間規劃對兩個標準化後的二維高度序列進行比對，在比對區域內找出一段最符合條件的路線。最後會將比對出來的路線呈現在網頁的互動式地圖上，方便使用者瀏覽。

The craze for sports has caused the booming of sports-related applications. Many of these running applications can set routes, goals, and record sports tracks. However, these applications can’t automatically plan routes for users who want specific elevation routes or routes with interesting shapes.

In view of the fact that there have been few previous researches on path comparison according to shape or height of the corresponding routes, this paper proposes an algorithm that can automatically find a route that meets the user’s requirements within a specific area. This paper consists of two parts. Dealing with the 2D case, the first part is to extract the feature points of a desired shape given by a user and the background, and use the shape context by removing the noise to perform the feature point matching. Then, we can get a closed route in a given area that approximates the outline of the desired shape. The second part is focusing on the height of routes in the 3D space. According to a user’s desired route containing distance and height, we do interpolation searches on the background to select candidate routes. After that, we use dynamic time warping to compare normalized 2D height sequences to find a route that best meets the conditions in a given area. Finally, the result will be presented on an interactive webmap, which is convenient for users to browse.

[1] Geoff Boeing. OSMnx: New methods for acquiring, constructing, analyzing,
and visualizing complex street networks. Computers, Environment and Urban
Systems, 65:126–139, 2017.
[2] John Canny. A computational approach to edge detection. IEEE Transactions
on Pattern Analysis and Machine Intelligence, PAMI-8(6):679–698, 1986.
[3] Satoshi Suzuki and Keiichi Abe. Topological structural analysis of digitized
binary images by border following. Computer Vision, Graphics and Image
Processing, 30(1):32–46, 1985.
[4] Chris Harris and Mike Stephens. A combined corner and edge detector. In In
Proc. of Fourth Alvey Vision Conference, pages 147–151, 1988.
[5] D. G. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91–110, 2004.
[6] Herbert Bay, Tinne Tuytelaars, and Luc Van Gool. SURF: Speeded up robust
features. Computer Vision and Image Understanding, 110(3):346–359, 2008.
[7] Zhang Zhijia, Huang Shabai, and Shi Zelin. A fast strategy for image matching
using hausdorff distance. In Proceedings of the 2003 IEEE Intemational Conference on Robotics,Intelligent Systems and Signal Processing, pages 915–919,
2003.
[8] Gang Xu and Wenxian Yang. Fast shape matching using a hybrid model.
International Conference on Computer Engineering and Technology, 1(4):247–
251, 2009.
[9] Serge Belongie, Jitenfra Malik, and Jan Puzicha. Shape matching and object
recognition using shape contexts. IEEE Transactions on Pattern Analysis and
Machine Intelligence, 24(24):509–522, 2002.
49
[10] Chien-Chou Lin and Chun-Ting Chang. A fast shape context matching using indexing. In Proceedings of 5th International Conference on Genetic and
Evolutionary Computing, volume 1, pages 17–20. IEEE, 2011.
[11] Jong-Chul Yoon, In-Kwon Lee, and Henry Kang. A hidden-picture puzzles
generator. Computer Graphics Forum, 27(7):1869–1877, 2008.
[12] Qiang Tong, Song-Hai Zhang, Shi-Min Hu, and Ralph R. Martin. Hidden
images. In Symposium on Non-Photorealistic Animation and Rendering, pages
27–34. ACM, 2011.
[13] Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization
for spoken word recognition. IEEE Transactions on Acoustics, Speech, and
Signal Processing, 26(1):43–49, 1978.
[14] Stan Salvador and Philip Chan. FastDTW: Toward accurate dynamic time
warping in linear time and space. Intelligent Data Analysis, 11(5):561–580,
2007.
[15] Rodica Neamtu, Ramoza Ahsan, Elke A. Rundensteiner, Gabor Sarkozy, Eamonn Keogh, Hoang Anh Dau, Cuong Nguyen, and Charles Lovering. Generalized dynamic time warping: Unleashing the warping power hidden in point-wise
distances. In Proceedings of 34th International Conference on Data Engineering, pages 521–532. IEEE, 2018.
[16] Wataru Sasaki and Yasufumi Takama. Walking route recommender system
considering SAW criteria. In Proceedings of 2013 Conference on Technologies
and Applications of Artificial Intelligence, pages 246–251. IEEE, 2013.
[17] Daniele Quercia, Rossano Schifanella, and Luca Maria Aiello. The shortest
path to happiness: Recommending beautiful, quiet, and happy routes in the
city. Proceedings of the 25th ACM Conference on Hypertext and Social Media,
pages 116–125, 2014.
[18] Jiayu Long, Jia Jia, and Han Xu. SenseRun: Real-time running routes recommendation toward providing pleasant running experiences. 31st AAAI Conference on Artificial Intelligence, pages 5101–5102, 2017.
50
[19] SRTM elevation data. https://www2.jpl.nasa.gov/srtm/.
[20] SRTM Github. https://github.com/tkrajina/srtm.py.
[21] OpenCV documentation. https://opencv-python-tutroals.readthedocs.
io/en/latest/index.html.
[22] OSMnx documentation. https://osmnx.readthedocs.io/.
[23] OSMnx Github example. https://github.com/gboeing/osmnx-examples.