Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 街道特徵與地標位置識別之研究
Content-based map localization using street map with landmarks
作者 李澤毅
Li, Ze Yi
貢獻者 何瑁鎧
Hor, Maw Kae
李澤毅
Li, Ze Yi
關鍵詞 地理資訊系統
地理資訊檢索
極座標表示法
街道圖
地標
GIS
Geographical Information Retrieval
Polar coordinate representation
Street map
Landmark
日期 2009
上傳時間 8-Dec-2010 02:00:32 (UTC+8)
摘要 隨著GIS的發展,地圖定位成為空間查詢中極為普遍的行為。一般地圖定位大多透過地址來進行,但是在缺乏地址的情況之下,進行地圖上之定位變成極為困難之事。
     本論文嘗試對手繪地圖在真實地圖上進行定位,我們提出了一套機制,使用者可以隨意地以手繪方式繪製街道圖與地標,透過我們提出的方法,即可自動地在真實的地圖上進行定位。
     論文中,我們使用相鄰街廓中之地標配置與相鄰之交叉路口之地標配置等變數組成的表示法來描述地圖。我們將手繪地圖與真實地圖轉換成這些表示法,並透過字串編輯距離、圖同構等關係來比較手繪地圖與真實地圖之相似度,從而對手繪地圖進行定位。
     實作中,我們挑選了幾處真實場景在台北市地圖中進行比對並觀察其結果。系統採用之地標包括政府機構(如派出所、消防隊、區公所等)、學校、醫院等資料。在實驗中,應用這套表示法可成功的定位出使用者所輸入之各場景所在位置。另外,透過控制相似度門檻值,我們可以調整辨識之精確度,不至於錯失可能之定位結果。
As the widely spread of the GIS applications, map localization becomes one of the most important features in the spatial information retrieval. Normally, map localization is done through street addresses. Without this information, map localization becomes very difficult.
     In this research, we are trying to do map localization using hand drawing maps. We proposed a mechanism that can localize the user`s drawing map in the reference map automatically.
     Our approaches use the landmark configurations of the adjacent street blocks as well as the landmark configurations of the adjacent street intersections as the descriptors in representing a map. The user`s hand drawn maps and the reference maps are converted into these representations. The string editing distances and graph isomorphism are used in determining the similarities between the hand drawn map and the reference map. The map localization can be done by comparing these similarities.
     We used various real scenes in Taipei City to verify our systems. The landmarks we used including police offices, fire stations, county offices, schools and hospitals, etc. The experimental results shown that our system can localize the user`s input successfully. Moreover, by controlling thresholds in similarity analysis, we can adjust the system`s accuracy that reduces possibility of miss localizations.
參考文獻 [1] J. D. Nystuen, A. Frank, and L. Frank, "Assessing topological similarity of spatial networks," in Proceedings of the International Conference and Workshop on Interoperating Geographic Information Systems, Santa Barbara, 1997.
[2] S. K. Chang and A. Hsu, "Image information systems: where do we go from here?," Knowledge and Data Engineering, IEEE Transactions on, vol. 4, pp. 431-442, 1992.
[3] A. K. Majumdar, I. Bhattacharya, and A. K. Saha, "An object-oriented fuzzy data model for similarity detection in image databases," Knowledge and Data Engineering, IEEE Transactions on, vol. 14, pp. 1186-1189, 2002.
[4] E. G. M. Petrakis, C. Faloutsos, and K. I. Lin, "ImageMap: an image indexing method based on spatial similarity," Knowledge and Data Engineering, IEEE Transactions on, vol. 14, pp. 979-987, 2002.
[5] E. El-Qawasmeh, "A quadtree-based representation technique for indexing and retrieval of image databases," Journal of Visual Communication and Image Representation, vol. 14, pp. 340-357, 2003.
[6] S.-K. Chang, Q.-Y. Shi, and C.-W. Yan, "Iconic Indexing by 2-D Strings," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. PAMI-9, pp. 413-428, 1987.
[7] S. K. Chang, E. Jungert, and Y. Li, "Representation and Retrieval of Symbolic Pictures Using Generalized 2D Strings," University of Pittsburg 1988.
[8] J. Erland, "Extended Symbolic Projections as a Knowledge Structure for Spatial Reasoning," in Proceedings of the 4th International Conference on Pattern Recognition: Springer-Verlag, 1988.
[9] E. Jungert and S. K. Chang, "An algebra for Symbolic Image Manipulation and Transformation," in Visual Database Systems North-Holland: Elsevier Science Publishers B.V.,, 1989.
[10] S.-Y. Lee and F.-J. Hsu, "2D C-string: A new spatial knowledge representation for image database systems," Pattern Recognition, vol. 23, pp. 1077-1087, 1990.
[11] A. J. T. Lee, H.-P. Chiu, and P. Yu, "3D C-string: a new spatio-temporal knowledge representation for video database systems," Pattern Recognition, vol. 35, pp. 2521-2537, 2002.
[12] P. W. Huang and Y. R. Jean, "Using 2D C+-strings as spatial knowledge representation for image database systems," Pattern Recognition, vol. 27, pp. 1249-1257, 1994.
[13] J. T. L. Anthony and C. Han-Pang, "2D Z-string: a new spatial knowledge representation for image databases," Pattern Recogn. Lett., vol. 24, pp. 3015-3026, 2003.
[14] J. T. L. Anthony, Y. Ping, C. Han-Pang, and H. Ruey-Wen, "3D Z-string: A new knowledge structure to represent spatio-temporal relations between objects in a video," Pattern Recogn. Lett., vol. 26, pp. 2500-2508, 2005.
[15] C.-C. Chang and C.-F. Lee, "A spatial match retrieval mechanism for symbolic pictures," Journal of Systems and Software, vol. 44, pp. 73-83, 1998.
[16] P.-W. Huang and C.-H. Lee, "Image Database Design Based on 9D-SPA Representation for Spatial Relations," IEEE Trans. on Knowl. and Data Eng., vol. 16, pp. 1486-1496, 2004.
[17] P. W. Huang and Y. R. Jean, "Spatial reasoning and similarity retrieval for image database systems based on RS-strings," Pattern Recognition, vol. 29, pp. 2103-2114, 1996.
[18] D. S. Guru and P. Punitha, "An invariant scheme for exact match retrieval of symbolic images based upon principal component analysis," Pattern Recognition Letters, vol. 25, pp. 73-86, 2004.
[19] C.-C. Chen, A. K. Craig, S. Cyrus, C. Yao-Yi, and T. Snehal, "Automatically and accurately conflating orthoimagery and street maps," in Proceedings of the 12th annual ACM international workshop on Geographic information systems Washington DC, USA: ACM, 2004.
[20] D. Sneha, A. K. Craig, C. Yao-Yi, D. Kandarp, and C. Ching-Chien, "Automatically identifying and georeferencing street maps on the web," in Proceedings of the 2005 workshop on Geographic information retrieval Bremen, Germany: ACM, 2005.
[21] S. Ranade and A. Rosenfeld, "Point pattern matching by relaxation," Pattern Recognition, vol. 12, pp. 269-275, 1980.
[22] S.-H. Chang, F.-H. Cheng, W.-H. Hsu, and G.-Z. Wu, "Fast algorithm for point pattern matching: Invariant to translations, rotations and scale changes," Pattern Recognition, vol. 30, pp. 311-320, 1997.
[23] R. C. Read and D. G. Corneil, "The graph isomorphism disease," Journal of Graph Theory, vol. 1, pp. 339-363, 1977.
[24] J. R. Ullmann, "An Algorithm for Subgraph Isomorphism," J. ACM, vol. 23, pp. 31-42, 1976.
[25] L. A. Zager and G. C. Verghese, "Graph similarity scoring and matching," Applied Mathematics Letters, vol. 21, pp. 86-94, 2008.
[26] H. Bunke, "On a relation between graph edit distance and maximum common subgraph," Pattern Recognition Letters, vol. 18, pp. 689-694, 1997.
[27] S. Gerard, A. Wong, and C. S. Yang, "A Vector Space Model for Automatic Indexing," Cornell University 1974.
[28] E. S. Ristad and P. N. Yianilos, "Learning string-edit distance," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 20, pp. 522-532, 1998.
[29] V. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals," 10, 1966.
[30] S. B. Needleman and C. D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins," Journal of Molecular Biology, vol. 48, pp. 443-453, 1970.
[31] N. Gonzalo, "A guided tour to approximate string matching," ACM Comput. Surv., vol. 33, pp. 31-88, 2001.
描述 碩士
國立政治大學
資訊科學學系
94753012
98
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0947530121
資料類型 thesis
dc.contributor.advisor 何瑁鎧zh_TW
dc.contributor.advisor Hor, Maw Kaeen_US
dc.contributor.author (Authors) 李澤毅zh_TW
dc.contributor.author (Authors) Li, Ze Yien_US
dc.creator (作者) 李澤毅zh_TW
dc.creator (作者) Li, Ze Yien_US
dc.date (日期) 2009en_US
dc.date.accessioned 8-Dec-2010 02:00:32 (UTC+8)-
dc.date.available 8-Dec-2010 02:00:32 (UTC+8)-
dc.date.issued (上傳時間) 8-Dec-2010 02:00:32 (UTC+8)-
dc.identifier (Other Identifiers) G0947530121en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/49167-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 94753012zh_TW
dc.description (描述) 98zh_TW
dc.description.abstract (摘要) 隨著GIS的發展,地圖定位成為空間查詢中極為普遍的行為。一般地圖定位大多透過地址來進行,但是在缺乏地址的情況之下,進行地圖上之定位變成極為困難之事。
     本論文嘗試對手繪地圖在真實地圖上進行定位,我們提出了一套機制,使用者可以隨意地以手繪方式繪製街道圖與地標,透過我們提出的方法,即可自動地在真實的地圖上進行定位。
     論文中,我們使用相鄰街廓中之地標配置與相鄰之交叉路口之地標配置等變數組成的表示法來描述地圖。我們將手繪地圖與真實地圖轉換成這些表示法,並透過字串編輯距離、圖同構等關係來比較手繪地圖與真實地圖之相似度,從而對手繪地圖進行定位。
     實作中,我們挑選了幾處真實場景在台北市地圖中進行比對並觀察其結果。系統採用之地標包括政府機構(如派出所、消防隊、區公所等)、學校、醫院等資料。在實驗中,應用這套表示法可成功的定位出使用者所輸入之各場景所在位置。另外,透過控制相似度門檻值,我們可以調整辨識之精確度,不至於錯失可能之定位結果。
zh_TW
dc.description.abstract (摘要) As the widely spread of the GIS applications, map localization becomes one of the most important features in the spatial information retrieval. Normally, map localization is done through street addresses. Without this information, map localization becomes very difficult.
     In this research, we are trying to do map localization using hand drawing maps. We proposed a mechanism that can localize the user`s drawing map in the reference map automatically.
     Our approaches use the landmark configurations of the adjacent street blocks as well as the landmark configurations of the adjacent street intersections as the descriptors in representing a map. The user`s hand drawn maps and the reference maps are converted into these representations. The string editing distances and graph isomorphism are used in determining the similarities between the hand drawn map and the reference map. The map localization can be done by comparing these similarities.
     We used various real scenes in Taipei City to verify our systems. The landmarks we used including police offices, fire stations, county offices, schools and hospitals, etc. The experimental results shown that our system can localize the user`s input successfully. Moreover, by controlling thresholds in similarity analysis, we can adjust the system`s accuracy that reduces possibility of miss localizations.
en_US
dc.description.tableofcontents 第 1 章 緒論........................ 1
      1.1 簡介........................ 1
      1.2 問題描述.................... 2
      1.3 研究動機.................... 3
      1.4 研究目的.................... 4
      1.5 章節架構.................... 5
     第 2 章 相關研究.................... 6
      2.1 關係特徵.................... 6
      2.2 圖層疊合.................... 10
      2.3 其他相關研究................ 14
     第 3 章 系統資料前處理與描述子建立.. 15
      3.1 問題說明與系統架構簡介...... 17
      3.2 前處理系統架構.............. 22
      3.3 地標向量.................... 27
      3.4 地標配置.................... 28
      3.5 相鄰配置.................... 30
      3.6 特徵點組成.................. 32
      3.7 樣式表...................... 34
     第 4 章 檢索與比對方法.............. 38
      4.1 概論與架構.................. 39
      4.2 範例地圖特徵點與檢索前處理.. 42
      4.3 地標向量比對................ 43
      4.4 地標配置比對................ 47
      4.5 相鄰配置比對................ 57
      4.6 特徵點組成比對.............. 64
      4.7 檢索系統架構................ 69
     第 5 章 系統架構、實驗與結果........ 74
      5.1 手動前處理.................. 74
      5.2 參數設計.................... 78
      5.3 實驗設計.................... 82
      5.4 實驗結果與評估.............. 84
      5.5 實驗總結.................... 96
     第 6 章 討論與未來研究.............. 98
      引用文獻與參考資料..........100
zh_TW
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0947530121en_US
dc.subject (關鍵詞) 地理資訊系統zh_TW
dc.subject (關鍵詞) 地理資訊檢索zh_TW
dc.subject (關鍵詞) 極座標表示法zh_TW
dc.subject (關鍵詞) 街道圖zh_TW
dc.subject (關鍵詞) 地標zh_TW
dc.subject (關鍵詞) GISen_US
dc.subject (關鍵詞) Geographical Information Retrievalen_US
dc.subject (關鍵詞) Polar coordinate representationen_US
dc.subject (關鍵詞) Street mapen_US
dc.subject (關鍵詞) Landmarken_US
dc.title (題名) 街道特徵與地標位置識別之研究zh_TW
dc.title (題名) Content-based map localization using street map with landmarksen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] J. D. Nystuen, A. Frank, and L. Frank, "Assessing topological similarity of spatial networks," in Proceedings of the International Conference and Workshop on Interoperating Geographic Information Systems, Santa Barbara, 1997.zh_TW
dc.relation.reference (參考文獻) [2] S. K. Chang and A. Hsu, "Image information systems: where do we go from here?," Knowledge and Data Engineering, IEEE Transactions on, vol. 4, pp. 431-442, 1992.zh_TW
dc.relation.reference (參考文獻) [3] A. K. Majumdar, I. Bhattacharya, and A. K. Saha, "An object-oriented fuzzy data model for similarity detection in image databases," Knowledge and Data Engineering, IEEE Transactions on, vol. 14, pp. 1186-1189, 2002.zh_TW
dc.relation.reference (參考文獻) [4] E. G. M. Petrakis, C. Faloutsos, and K. I. Lin, "ImageMap: an image indexing method based on spatial similarity," Knowledge and Data Engineering, IEEE Transactions on, vol. 14, pp. 979-987, 2002.zh_TW
dc.relation.reference (參考文獻) [5] E. El-Qawasmeh, "A quadtree-based representation technique for indexing and retrieval of image databases," Journal of Visual Communication and Image Representation, vol. 14, pp. 340-357, 2003.zh_TW
dc.relation.reference (參考文獻) [6] S.-K. Chang, Q.-Y. Shi, and C.-W. Yan, "Iconic Indexing by 2-D Strings," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. PAMI-9, pp. 413-428, 1987.zh_TW
dc.relation.reference (參考文獻) [7] S. K. Chang, E. Jungert, and Y. Li, "Representation and Retrieval of Symbolic Pictures Using Generalized 2D Strings," University of Pittsburg 1988.zh_TW
dc.relation.reference (參考文獻) [8] J. Erland, "Extended Symbolic Projections as a Knowledge Structure for Spatial Reasoning," in Proceedings of the 4th International Conference on Pattern Recognition: Springer-Verlag, 1988.zh_TW
dc.relation.reference (參考文獻) [9] E. Jungert and S. K. Chang, "An algebra for Symbolic Image Manipulation and Transformation," in Visual Database Systems North-Holland: Elsevier Science Publishers B.V.,, 1989.zh_TW
dc.relation.reference (參考文獻) [10] S.-Y. Lee and F.-J. Hsu, "2D C-string: A new spatial knowledge representation for image database systems," Pattern Recognition, vol. 23, pp. 1077-1087, 1990.zh_TW
dc.relation.reference (參考文獻) [11] A. J. T. Lee, H.-P. Chiu, and P. Yu, "3D C-string: a new spatio-temporal knowledge representation for video database systems," Pattern Recognition, vol. 35, pp. 2521-2537, 2002.zh_TW
dc.relation.reference (參考文獻) [12] P. W. Huang and Y. R. Jean, "Using 2D C+-strings as spatial knowledge representation for image database systems," Pattern Recognition, vol. 27, pp. 1249-1257, 1994.zh_TW
dc.relation.reference (參考文獻) [13] J. T. L. Anthony and C. Han-Pang, "2D Z-string: a new spatial knowledge representation for image databases," Pattern Recogn. Lett., vol. 24, pp. 3015-3026, 2003.zh_TW
dc.relation.reference (參考文獻) [14] J. T. L. Anthony, Y. Ping, C. Han-Pang, and H. Ruey-Wen, "3D Z-string: A new knowledge structure to represent spatio-temporal relations between objects in a video," Pattern Recogn. Lett., vol. 26, pp. 2500-2508, 2005.zh_TW
dc.relation.reference (參考文獻) [15] C.-C. Chang and C.-F. Lee, "A spatial match retrieval mechanism for symbolic pictures," Journal of Systems and Software, vol. 44, pp. 73-83, 1998.zh_TW
dc.relation.reference (參考文獻) [16] P.-W. Huang and C.-H. Lee, "Image Database Design Based on 9D-SPA Representation for Spatial Relations," IEEE Trans. on Knowl. and Data Eng., vol. 16, pp. 1486-1496, 2004.zh_TW
dc.relation.reference (參考文獻) [17] P. W. Huang and Y. R. Jean, "Spatial reasoning and similarity retrieval for image database systems based on RS-strings," Pattern Recognition, vol. 29, pp. 2103-2114, 1996.zh_TW
dc.relation.reference (參考文獻) [18] D. S. Guru and P. Punitha, "An invariant scheme for exact match retrieval of symbolic images based upon principal component analysis," Pattern Recognition Letters, vol. 25, pp. 73-86, 2004.zh_TW
dc.relation.reference (參考文獻) [19] C.-C. Chen, A. K. Craig, S. Cyrus, C. Yao-Yi, and T. Snehal, "Automatically and accurately conflating orthoimagery and street maps," in Proceedings of the 12th annual ACM international workshop on Geographic information systems Washington DC, USA: ACM, 2004.zh_TW
dc.relation.reference (參考文獻) [20] D. Sneha, A. K. Craig, C. Yao-Yi, D. Kandarp, and C. Ching-Chien, "Automatically identifying and georeferencing street maps on the web," in Proceedings of the 2005 workshop on Geographic information retrieval Bremen, Germany: ACM, 2005.zh_TW
dc.relation.reference (參考文獻) [21] S. Ranade and A. Rosenfeld, "Point pattern matching by relaxation," Pattern Recognition, vol. 12, pp. 269-275, 1980.zh_TW
dc.relation.reference (參考文獻) [22] S.-H. Chang, F.-H. Cheng, W.-H. Hsu, and G.-Z. Wu, "Fast algorithm for point pattern matching: Invariant to translations, rotations and scale changes," Pattern Recognition, vol. 30, pp. 311-320, 1997.zh_TW
dc.relation.reference (參考文獻) [23] R. C. Read and D. G. Corneil, "The graph isomorphism disease," Journal of Graph Theory, vol. 1, pp. 339-363, 1977.zh_TW
dc.relation.reference (參考文獻) [24] J. R. Ullmann, "An Algorithm for Subgraph Isomorphism," J. ACM, vol. 23, pp. 31-42, 1976.zh_TW
dc.relation.reference (參考文獻) [25] L. A. Zager and G. C. Verghese, "Graph similarity scoring and matching," Applied Mathematics Letters, vol. 21, pp. 86-94, 2008.zh_TW
dc.relation.reference (參考文獻) [26] H. Bunke, "On a relation between graph edit distance and maximum common subgraph," Pattern Recognition Letters, vol. 18, pp. 689-694, 1997.zh_TW
dc.relation.reference (參考文獻) [27] S. Gerard, A. Wong, and C. S. Yang, "A Vector Space Model for Automatic Indexing," Cornell University 1974.zh_TW
dc.relation.reference (參考文獻) [28] E. S. Ristad and P. N. Yianilos, "Learning string-edit distance," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 20, pp. 522-532, 1998.zh_TW
dc.relation.reference (參考文獻) [29] V. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals," 10, 1966.zh_TW
dc.relation.reference (參考文獻) [30] S. B. Needleman and C. D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins," Journal of Molecular Biology, vol. 48, pp. 443-453, 1970.zh_TW
dc.relation.reference (參考文獻) [31] N. Gonzalo, "A guided tour to approximate string matching," ACM Comput. Surv., vol. 33, pp. 31-88, 2001.zh_TW