臺灣博碩士論文加值系統

近年來因為PDA (Personal Digital Assistant)等行動裝置(mobile device)使用趨於普及，相關的應用隨之而起，電子地圖因為可以結合旅遊與生活資訊而成為一種普遍的應用。向量格式圖形(vector image) ，因為以點座標的方式儲存，所需空間比一般光柵圖 (raster image) 以儲存像素值方式還來得省空間。但當地圖資料量大之時，還是需要對向量圖壓縮才能符合行動裝置的限制。FHM (Fibonacci, Huffman, and Markov)壓縮法是一個字典基礎(dictionary-based)的改良式多環鍊碼 (modified multi-ring chain code)，是一個針對線條壓縮的方法，但其為一個失真 (lossy) 壓縮法，而其失真程度主要在字典 (dictionary) 的設計，後來有研究者以k-means分群法改進其字典的設計方式，降低失真。本研究主要提出兩個方面的改良技巧。一、在將道路向量化後，把每一向量的起點置於二維座標平面的原點，可以得到一個分佈圖。運用部分逆序取向量法調整道路儲存的順序，可以使得此向量分佈更為緊密，增進分群後每一群內的相似程度，進而提高字典的品質。二、如果道路向量化的程序是採用每一點減去前一點座標的方式，則原有k-means分群法中k-means誤差的計算方式將無法代表整個地圖實際的失真值，透過調整k-means分群法的誤差計算公式，可以確保分群法最小化的是實際的地圖失真。此兩種方法都可在不增加地圖儲存空間大小的前提下，進一步減少原有壓縮法所造成的失真。

Using mobile devices like PDA (Personal Digital Assistant) is more popular now, so many related applications arise. Digital street maps have become a common application for PDAs to help people when they travel. Images store as vector point coordinates need less storage space than raster images. As maps become larger, they need to be compressed in order to meet the limited storage of mobile devices. The FHM (Fibonacci, Huffman, and Markov) compression method, which is designed for compressing digital signatures, is a dictionary-based modified multi-ring chain code. It’s a lossy compression method, and the degree of distortion depends on the design of the dictionary. Some researchers improve the dictionary design by using k-means clustering to reduce the distortion. This thesis improves the dictionary design in two ways: (1) if roads are vectorized with an arbitrary starting point, and we make a polar scatter plot of the direction and length of all vectors that makeup the whole map. It is possible to reduce the extent of this distribution if we optimize the stored directions (start vs. end points) of individual roads. This has the advantage of reducing the error of the clusters, which, in turn, reduces the error of the dictionary generated from the clusters. (2) when roads are vectorized relative to previous points, the original k-means error can not stand for the real distortion of a map. So, adjusting the object function of the k-means clustering algorithm can ensure that the k-means error we minimize represents the real distortion. These two improvements can reduce the distortion without increasing the required storage.

第一章、緒論 1
第一節 研究背景 1
第二節 研究動機與目的 1
第三節 研究範圍 2
第四節 論文架構 2
第二章、文獻探討 3
第一節 FHM壓縮演算法沿革 3
第二節 k-means分群法 7
第三章、改良方法 9
第一節 部分逆序取向量法 10
第二節 調整k-means分群法 13
第四章、實驗與討論 22
第一節 名詞介紹 22
第二節 實作工具 22
第三節 座標系統 24
第四節、實驗數據 26
第五章、結論與未來發展 48
第六章、參考文獻 49
附錄、地圖資料 51

[1] ESRI Shapefile Technical Description, July 1998
[2] Ｈ. Freeman, “On the encoding of arbitrary geometric configurations”, Institute of Radio Engineers, Transactions on Electronic Computers, 1961
[3] H. Freeman, A. Saaghri, “Generalized Chain Codes for Planar Curves”, International Conference on Pattern Recognition, 1978
[4] J. D. Gibson, T. Berger, T. Lookabaugh, D. LindBergh, R. L. Baker, Digital Compression for Multimedia Principles & Standards, Morgan Kaufmann; 1st edition, 1998
[5] J. A. Hartigan, M. A. Wong, "A k-means clustering algorithm", Applied Statistics, No.28, pp.100-108, 1979.
[6] A.K. Jain, Dubes R.C., Algorithms for clustering data, Prentice Hall, 1988
[7] B. Johannessen, J. H. Bons, N. B. J. Weyland, R. Prasad. “Multiring Differential Chain Codes for Line Drawings.” Electronics Letters, Vol. 26, No.10, 1990.
[8] T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, A. Y. Wu. “An Efficient k-Means Clustering Algorithm: Analysis and Implementation.” IEEE Transactions on Patterns Analysis and Machine Intelligence, Vol. 24, No. 7, 2002.
[9] D. Salomon, Data Compression: the Complete Reference, Springer-Verlag, 2nd, 2000.
[10] M. Satyanarayanan, “Fundamental Challenges in Mobile Computing”, Fifteenth ACM Symposium on Principles of Distributed Computing, 1996
[11] S. Shekhar, Y. Huang, and J. Djugash, “Dictionary Design Algorithms for Vector Map Compression(Abstract).” In Proceedings of Data Compression Conference, 2002.
[12] S. Shekhar, Y. Huang, J. Djugash, C. Zhou, “Vector Map Compression: A Clustering Approach”, ACMGIS 2002, 2002
[13] 周天穎，地理資訊系統理論與實務，台北：儒林圖書，民92年
[14] Annotated Computer Vision Bibliography http://iris.usc.edu/Vision-Notes/bibliography/contents.html
[15] Arc/Info. http://www.esri.com/software/index.html
[16] Maction Mobile Tecnologies 研勤科技 http://www.mactiontech.com/index.htm
[17] MobileMap http://www.gismosoft.com/
[18] National Atlas of the United State of America - Map Layers Warehouse http://nationalatlas.gov/atlasftp.html
[19] ShowMap生活地圖網http://www.showmap.com.tw
[20] TaiwanMap台灣電子地圖服務網 http://www.map.com.tw
[21] TeleMap http://www.telemap.com
[22] UrMap 你的地圖http://www.urmap.com
[23] Yam蕃薯藤地圖 http://maps.yam.com/yam/travel/travel.asp