本論文是基於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