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