Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/49167
|
| Title: | 街道特徵與地標位置識別之研究
Content-based map localization using street map with landmarks |
| Authors: | 李澤毅
Li, Ze Yi |
| Contributors: | 何瑁鎧
Hor, Maw Kae
李澤毅
Li, Ze Yi |
| Keywords: | 地理資訊系統
地理資訊檢索
極座標表示法
街道圖
地標
GIS
Geographical Information Retrieval
Polar coordinate representation
Street map
Landmark |
| Date: | 2009 |
| Issue Date: | 2010-12-08 02:00:32 (UTC+8) |
| Abstract: | 隨著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. |
| 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.
[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. |
| Description: | 碩士
國立政治大學
資訊科學學系
94753012
98 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0947530121 |
| Data Type: | thesis |
| Appears in Collections: | [資訊科學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| index.html | 0Kb | HTML2 | 258 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
