LZW編碼
LZW（Lempel-Ziv & Welch）編碼又稱字串表編碼，是Welch將Lempel和Ziv所提出的無損壓縮技術改進后的壓縮方法。GIF圖像文件采用的是一種改良的LZW壓縮算法， 通常稱為GIF-LZW壓縮算法。下面簡要介紹GIF-LZW的編碼與解碼方法。
例8-5 現有來源于二色系統的圖像數據源（假設數據以字符串表示）：aabbbaabb，試對其進行LZW編碼及解碼。
解：1）根據圖像中使用的顏色數初始化一個字符串表（如表8-1），字符串表中的每個顏色對應一個索引。在初始字符串表的LZW_CLEAR和LZW_EOI分別為字符表初始化標志和編碼結束標志。設置字符串變量S1、 S2并初始化為空。
表8-1 初始化字符串表
|
字符串
|
索引
|
|
a
|
0H
|
|
b
|
1H
|
|
LZW_CLEAR
|
2H
|
|
LZW_EOI
|
3H
|
2）輸出LZW_CLEAR在字串表中的索引3H（見表8-2第一行）。
3）從圖像數據流中第一個字符開始，讀取一個字符a，將其賦給字符串變量S2。判斷S1+S2=”a”在字符串表中，則S1=S1+S2=“a” （見表8-2第二行）。
4）讀取圖像數據流中下一個字符a，將其賦給字符串變量S2。判斷S1+S2=”aa”不在字符串表中，輸出S1=“a”在字串表中的索引0H，并在字符串表末尾為S1+S2=“aa”添加索引4H，且S1= S2=“a” （見表8-2第三行）。
5）讀下一個字符b賦給S2。判斷S1+S2=”ab”不在字符串表中，輸出S1=“a”在字串表中的索引0H，并在字符串表末尾為S1+S2=“ab”添加索引5H，且S1= S2=“b” （見表8-2第四行）。
6）讀下一個字符b賦給S2。S1+S2=”bb”不在字符串表中，輸出S1=“b”在字串表中的索引1H，并在字符串表末尾為S1+S2=“bb”添加索引6H，且S1= S2=“b” （見表8-2第五行）。
7）讀字符b賦給S2。S1+S2=”bb”在字符串表中，則S1= S1+S2=“bb” （見表8-2第六行）。
8）讀字符a賦給S2。S1+S2=”bba”不在字符串表中，輸出S1=“bb”在字串表中的索引6H，并在字符串表末尾為S1+S2=“bba”添加索引7H，且S1= S2=“a” （見表8-2第七行）。
9）讀字符a賦給S2。S1+S2=”aa”在字符串表中，則S1= S1+S2=“aa” （見表8-2第八行）。
10）讀字符b賦給S2。S1+S2=”aab”不在字符串表中，輸出S1=“aa”在字串表中的索引4H，并在字符串表末尾為S1+S2=“aab”添加索引8H，且S1= S2=“b” （見表8-2第九行）。
11）讀字符b賦給S2。S1+S2=”bb”，在字符串表中，則 S1= S1+S2=“b” （見表8-2第十行）。
12）輸出S1中的字符串”b”在字串表中的索引1H（見表8-2第十一行）。
13）輸出結束標志LZW_EOI的索引3H，編碼完畢。
最后的編碼結果為“30016513”。
表8-2 GIF-LZW的編碼過程
|
行號
|
輸入數據S2
|
S1+S2
|
輸出結果
|
S1
|
生成新字符及索引
|
|
1
|
NULL
|
NULL
|
3H
|
NULL
|
|
|
2
|
a
|
a
|
|
a
|
|
|
3
|
a
|
aa
|
0H
|
a
|
aa<4H>
|
|
4
|
b
|
ab
|
0H
|
b
|
ab<5H>
|
|
5
|
b
|
bb
|
1H
|
b
|
bb<6H>
|
|
6
|
b
|
bb
|
|
bb
|
|
|
7
|
a
|
bba
|
6H
|
a
|
bba<7H>
|
|
8
|
a
|
aa
|
|
aa
|
|
|
9
|
b
|
aab
|
4H
|
b
|
aab<8H>
|
|
10
|
b
|
bb
|
|
bb
|
|
|
11
|
|
|
6H
|
|
|
|
12
|
|
|
3H
|
|
|
下面對上述編碼結果“20016463”進行解碼。同樣先初始化字符串表， 結果如表8-1所示。
1） 首先讀取第一個編碼Code=3H， 由于它為LZW_CLEAR，無輸出（見表8-3第一行）。
2） 讀入下一個編碼Code=0H，由于字符串表中存在該索引，因此輸出字符串表中0H對應的字符串“a”， 同時使OldCode=Code=0H（見表8-3第二行）。
3） 讀下一個編碼Code=0H，字符串表中存在該索引，輸出0H所對應的字符串“a”，然后將OldCode=0H所對應的字符串“a”加上Code=0H所對應的字符串的第一個字符“a”，即“aa”添加到字串表中，其索引為4H，同時使oldCode=Code=0H（見表8-3第三行）。
4） 讀下一個編碼Code=1H，字串表中存在該索引，輸出1H所對應的字符串“b”，然后將OldCode=0H所對應的字符串“a”加上Code=1H所對應的字符串的第一個字符“b”，即“ab”添加到字串表中，其索引為5H， 同時使OldCode=Code=1H（見表8-3第四行）。
5） 讀入下一個編碼Code=6H，由于字符串表中不存在該索引， 因此輸出OldCode=1H所對應的字符串“b”加上OldCode的第一個字符“b”，即“bb”，同時將“bb”添加到字符串表中，其索引為6H， 同時使OldCode=Code=6H（見表8-3第五行）。
6） 讀下一個編碼Code=4H，字串表中存在該索引，輸出4H所對應的字符串“aa”，然后將OldCode=6H所對應的字符串“bb”加上Code=4H所對應的字符串的第一個字符“a”，即“bba”添加到字串表中，其索引為7H， 同時使OldCode=Code=4H（見表8-3第六行）。
7） 讀下一個編碼Code=6H，字串表中存在該索引，輸出6H所對應的字符串“bb”，然后將OldCode=4H所對應的字符串“aa”加上Code=6H所對應的字符串的第一個字符“b”，即“aab”添加到字串表中，其索引為8H， 同時使OldCode=Code=6H（見表8-3第七行）。
8） 讀下一個編碼Code=3H， 它等于LZW_EOI， 數據解碼完畢（見表8-3第八行）。
最后的解碼結果為aabbbaabb。
表8-3 GIF-LZW的解碼過程
|
行號
|
輸入數據Code
|
新串
|
輸出結果
|
OldCode
|
生成新字符及索引
|
|
1
|
3H
|
|
|
|
|
|
2
|
0H
|
|
a
|
0H
|
|
|
3
|
0H
|
aa
|
a
|
0H
|
aa<4H>
|
|
4
|
1H
|
ab
|
b
|
1H
|
ab<5H>
|
|
5
|
6H
|
bb
|
bb
|
6H
|
bb<6H>
|
|
6
|
4H
|
bba
|
aa
|
4H
|
bba<7H>
|
|
7
|
1H
|
aab
|
b
|
1H
|
aab<8H>
|
|
8
|
3H
|
|
|
|
|
由此可見，LZW編碼算法在編碼與解碼過程中所建立的字符串表是一樣的，都是動態生成的，因此在壓縮文件中不必保存字符串表。
posted on 2009-10-30 17:42
李陽 閱讀(2718)
評論(0) 編輯 收藏 引用 所屬分類:
圖形圖像