Basic Search / Detailed Display

Author: 侯尊堯
Zun-Yao Hou
Thesis Title: 基於形狀與高度之路徑比對
Path Comparison Based on Shape and Height
Advisor: 楊傳凱
Chuan-Kai Yang
Committee: 楊傳凱
Chuan-Kai Yang
賴源正
Yuan-Cheng Lai
林伯慎
Bor-Shen Lin
Degree: 碩士
Master
Department: 管理學院 - 資訊管理系
Department of Information Management
Thesis Publication Year: 2020
Graduation Academic Year: 108
Language: 中文
Pages: 63
Keywords (in Chinese): 形狀上下文動態時間規劃內插搜尋
Keywords (in other languages): Shape Context, Dynamic Time Warping, Interpolation Search
Reference times: Clicks: 479Downloads: 0
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  • 運動風氣的提升帶動運動相關應用程式的興起,其中許多跑步應用程式能夠設定路線、目標,也可以記錄運動軌跡,但這些應用程式都無法自動為使用者規劃路線,無法滿足那些具有訓練需求,想要特定高低起伏或趣味性形狀路線的使用者。

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


    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.1 研究動機與目的 1.2 論文架構 第二章 文獻探討 2.1 OSMnx 2.2 影像處理 2.2.1 輪廓偵測 2.2.2 特徵提取 2.3 圖像比對 2.4 動態時間規劃 2.5 路徑推薦系統 第三章 演算法設計與系統實作 3.1 系統流程 3.2 影像前處理 3.2.1 路網圖像的生成 3.2.2 邊緣偵測 3.2.3 Harris角點偵測 3.2.4 建立特徵點連線關係 3.3 形狀比對 3.3.1 形狀上下文(Shape Context) 3.3.2 雜訊過濾 3.3.3 相似性度量 3.4 高度比對 3.4.1 內插搜尋篩選路線 3.4.2 動態時間規劃(DTW) 第四章 結果展示與分析 4.1 系統環境 4.2 結果展示與分析 4.2.1 形狀比對結果與分析 4.2.2 高度比對結果 4.3 問卷調查 4.4 研究限制 第五章 結論與未來展望 參考文獻

    [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.

    無法下載圖示 Full text public date 2025/07/24 (Intranet public)
    Full text public date This full text is not authorized to be published. (Internet public)
    Full text public date This full text is not authorized to be published. (National library)
    QR CODE