(3.237.20.246) 您好!臺灣時間:2021/04/15 19:23
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳克奇
研究生(外文):ke chi Chen
論文名稱:以分群法為基礎的多環鍊碼應用於向量地圖壓縮之研究
論文名稱(外文):The Study of Clustering-Based Multi-Ring Chain Code on Vector Map Compression
指導教授:林順喜林順喜引用關係
指導教授(外文):Shun-Shii Lin
學位類別:碩士
校院名稱:國立臺灣師範大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:55
中文關鍵詞:向量地圖壓縮多環鍊碼
外文關鍵詞:vector map compressionmulti-ring chain codek-means clusteringFHM
相關次數:
  • 被引用被引用:3
  • 點閱點閱:107
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:15
  • 收藏至我的研究室書目清單書目收藏:0
近年來因為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] H. 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
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 鐘樹椽(1999)。教學科技應用於小班教學之探討。教師之友,40,5-11。
2. 劉世雄(2000)。國小教師運用資訊科技融入教學策略之探討。資訊與教育,78,8。
3. 潘貴美(2001)。檔案評量初探。敦煌英語教學雜誌,30,32-34。
4. 廖伯仁(2001)。高中生活科技合作學習之觀察研究。生活科技教育,34卷11期,頁9-15。
5. 張秉中(2000)。藏私文化已過時知識管理重分享。統領雜誌,72-74。
6. 楊叔卿(2000)。迎接二十一世紀的「艾麗絲」:網際網路輔助教育的理念。教學科技與媒體,50,2-11。
7. 溫明正(2000)。教室電腦教學環境的應用。資訊與教育,77,8-14。
8. 張政亮(2002)。多媒體網路教學的發展趨勢─以模組式網頁教材的設計為例。資訊與教育雜誌2001特刊,45-55。
9. 陳年興、李旻俐(1999)。A捷計畫:高中、國中跨英文遠距教學。教育部電子計算機中心簡訊,8809,24-37。
10. 陳立元(1997)。工欲善其事,必先利其器:華語教學與媒體運用。教學科技與媒體,36,50-54。
11. 張美玉(2001)。從多元智能的觀點談歷程檔案評量在教育上的應用。教育研究資訊,2001.2,9(1),32-54.
12. 曹世亮(2002)。永續學習的e-Learning架構:以學習型組織為基礎的探討。資訊與教育雜誌2001特刊,163-179。
13. 孫春在(1995)。超媒體網路與遠距合作式電腦輔助學習。教學科技與媒體,21,29-37。
14. 徐元瑛、史永健、曾建超(2002)。無線網路學習環境的面面觀。資訊與教育雜誌,90,3-13。
15. 吳明隆(1999)。教室電腦網路應用於「小班教學精神內涵」的探究。資訊與教育,71,33-39。
 
系統版面圖檔 系統版面圖檔