淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0806200821220000
中文論文名稱 改善用於嵌入式系統的LZW無失真壓縮方法
英文論文名稱 Improving LZW Lossless Compression for Embedded Systems
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士在職專班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 96
學期 2
出版年 97
研究生中文姓名 王櫳賢
研究生英文姓名 Lung-Hsien Wang
電子信箱 jouse.wang@yahoo.com.tw
學號 795410116
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2008-06-06
論文頁數 77頁
口試委員 指導教授-許輝煌
委員-洪啟舜
委員-黃仁俊
中文關鍵字 無失真壓縮  資料壓縮  嵌入式系統  LZW 
英文關鍵字 Lossless compression  Lempel-Ziv Welch (LZW)  embedded system  Run-Length Encoding (RLE)  data compression 
學科別分類 學科別應用科學資訊工程
中文摘要 本論文是基於LZW壓縮原理,設計應用於小型嵌入式系統的無失真壓縮/解壓縮程式,由LZW方法中延伸出兩個新的變形壓縮方法,一個是利用PNG相鄰兩點色差值壓縮原理,用在LZW相鄰字元差值,並以縮減位元編碼,用在灰階圖形上有不錯的效果,另一個是改善LZW重建字典時,字串取代的順序,在壓縮率上可比原本的LZW演算法更好,而且字典需求空間更小,對於小型靜態無失真圖形檔上,壓縮效果比其他格式好,而且也能用於壓縮非圖形的檔案。另外本論文亦實作整合了RLE的方法於應用程式中,提供了小型嵌入式系統多重的選擇,使用者可自由選擇壓縮方法,及調整本論文所提供壓縮方法的參數,以符合各式不同嵌入式系統記憶體及速度上不同的需求。
英文摘要 This research is based on the LZW compression principle. It extends the principle to two new methods. One of the methods exploits different values with bytes, then compresses as reducing code-bit. Another uses reference values to reserve common use strings when the LZW dictionary need to be rebuilt. For some small images, the new method is better than the PNG image format. And the new method can compress non-imaged files. This research also integrated RLE into the application program that supporting multi-method selection for embedded systems. The user can adjust different parameters for various embedded systems with different demands on speed and memory.
論文目次 目 錄
第1章 緒論 1
1.1 研究動機與目的 1
1.2 論文組織架構 1
第2章 相關研究探討 2
2.1 壓縮方法相關研究 2
2.2 RLE(RUN-LENGTH ENCODING) 5
2.2.1 基本原理 5
2.2.2 Microsoft-RLE 6
2.3 LZW(LEMPEL-ZIV-WELCH) 8
2.3.1 基本原理 8
2.3.2 LZW壓縮 9
2.3.3 LZW解壓縮 12
2.3.4 LZW縮減位元編碼 14
2.3.5 PNG像素色差值編碼 17
2.4 LZW+RLE 20
2.4.1 原理分析 20
2.4.2 LZW模式 21
2.4.3 RLE 模式 23
2.4.4 與原LZW與RLE比較 24
第3章 改良的壓縮方法 27
3.1 LZWD色差值縮減位元編碼 27
3.1.1 PNG檔可改進方向 27
3.1.2 實作原理 28
3.1.3 與原PNG檔及LZW方法比較 30
3.2 LZWR 常用字串參考法 34
3.2.1 LZW字典限制分析 34
3.2.2 LZWR關鍵想法 37
3.2.3 LZWR使用的資料結構 39
3.2.4 LZWR字串代換原則 44
3.2.5 與原LZW方法比較 47
第4章 應用程式實作 49
4.1 主畫面介紹 49
4.2 ANALYSIS功能 50
4.3 OPTION選項功能 51
4.4 COMPRESS/DECOMPRESS功能 55
第5章 實驗結果比較 56
5.1 實驗條件及檔案 56
5.2 實驗結果 58
5.3 與其他方法比較與分析 60
第6章 結論及未來研究方向 62
6.1 結論 62
6.2 壓縮方法未來研究方向 63
6.3 應用程式未來改進方向 64
參考文獻 65
附錄-英文論文 67




圖片目錄
圖 1 XPHOTO.BMP用於醫療照片的無失真影像壓縮 1
圖 2 現在頗流行的多功能手機 2
圖 3 數位電視OSD選單 3
圖 4 壓縮編碼的分類 2
圖 5 完整資料壓縮程序 3
圖 6 (A) 德國國旗 (B) 日本國旗 5
圖 7 LZW壓縮演算法 9
圖 8  LZW解壓縮演算法 12
圖 9 適用PNG格式之範例圖像檔 17
圖 10  CARTOONS.BMP (303X239X8BPP, 73734 BYTES) 24
圖 11  LOGO.BMP (240X72X4BPP, 8758 BYTES) 25
圖 12  AFRICA.BMP (384X256X8BPP, 99382 BYTES) 25
圖 13 LENNAGRAY.BMP為256灰階照片 31
圖 14 LENNA256.BMP為256色彩色照片 31
圖 15 LENNAGRAY.BMP(左)與LENNA256.BMP(右)的調色盤資料 33
圖 16 壓縮文字檔時LZW字典大小與壓縮比關係圖 35
圖 17 LENNA256.BMP字典大小與壓縮比關係圖 36
圖 18 以TREE-ARRAY LINK方式建立字典 39
圖 19  TREE-LINK LIST資料結構 41
圖 20 以TREE-LINK LIST方式建立字典 42
圖 21 (A)為編碼索引陣列  (B)為字串被參考數次記錄 44
圖 22 字典建立及字串取代流程關係圖 45
圖 23 LZW與LZWR壓縮比與字典大小關係比較圖 48
圖 24 實作應用程式之主畫面 49
圖 25 實作應用程式之分析結果報告 50
圖 26 實作應用程式之選項頁面 51
圖 27 壓縮字典與解壓縮字典的內容比較 52
圖 28 編碼(左)及解碼(右)過程記錄檔內容 53
圖 29 壓縮/解壓縮進度表及結果報告 54
圖 30 TV-BOX嵌入式系統硬體照片 56
圖 31 TV-BOX使用的一系列ICON小圖組 57
圖 32 TV-BOX嵌入式系統實際運作的情況 58
圖 33 切換不同子選單後近拍照片 59
圖 34 切換到圖示少的選單速度更快 59


表格目錄
表格 1  RLE 4-BITS 編碼與對應解壓縮資料 7
表格 2  LZW壓縮之編碼過程 10
表格 3  LZW解壓縮之解碼過程 13
表格 4 (A)重對應字元陣列 (B)縮減位元編碼範例 15
表格 5  LZW+RLE CASE1 21
表格 6  LZW+RLE CASE2 22
表格 7  LZW+RLE與原LZW及RLE壓縮結果比較表 25
表格 8  LZWD與原LZW及PNG檔之比較 32
表格 9 範例8編碼過程範例 38
表格 10  LZWR與原LZW方法的比較 47
表格 11 LRM與其他壓縮方法的比較 60

參考文獻 [1] D. A. Huffman, “A method for the construction of minimum redundancy codes,” hoc. IRE, Volume 40, Page(s): 1098 - 1101, Sept. 1952.
[2] I. H. Witten, R. M. Neal, and J. G. Cleary, “Arithmetic coding for data compression,” Comm. ACM, Volume 30, Issue 6, Page(s):520 - 540, 1987.
[3] Tao Tao and Amar Mukherjee, “Pattern matching in LZW compressed files,” IEEE Transactions on Computers, Volume 54, Issue 8, Page(s):929 - 938, Aug. 2005.
[4] Lih-Jen Kau and Yuan-Pei Lin, “Least-squares-based switching structure for lossless image coding,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, Volume 54, Issue 7, Page(s):1529 - 1541, July 2007.
[5] Ming Yang and Bourbakis Nikolaos, “An overview of lossless digital image compression techniques,” 48th Midwest Symposium on Circuits and Systems, Volume 2, Page(s):1099 - 1102, Aug. 2005.
[6] J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Transactions Information Theory, Volume 23, Issue 3, Page(s):337-343, May 1977.
[7] J. Ziv and A. Lempel, "Compression of individual sequences via variable-rate coding," IEEE Transactions on Information Theory, Volume 24, Issue 5, Page(s):530 - 536, Sept. 1978.
[8] T. A. Welch, “A technique for high-performance data compression,” IEEE Computer, Volume 17, Issue 6, Page(s):8 - 19, June 1984.
[9] LZW, http://en.wikipedia.org/wiki/LZW
[10] PNG, http://en.wikipedia.org/wiki/Portable_Network_Graphics
[11] LZMA, http://en.wikipedia.org/wiki/LZMA
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2008-06-23公開。
  • 同意授權瀏覽/列印電子全文服務,於2008-06-23起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信