四川大學(xué)計(jì)算機(jī)學(xué)院 多媒體技術(shù) 4

語(yǔ)義依賴（semantic-dependent）的DC方法應(yīng)用背景： 對(duì)于“局部冗余”的特殊類型。 主要應(yīng)用于圖象表達(dá)、處理。原因：數(shù)字化的image有大量的“局部冗余”占空間大 （一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的象素都具有相同的顏色值。）語(yǔ)義依賴（semantic-dependent）的DC方法典型：行程編碼（run-lengthencoding:RLE）差異映射(differencemapping)詞典編碼(DictionaryEncoding)語(yǔ)義依賴（semantic-dependent）的DC方法差異映射：算法思想：圖象表示為相鄰像素在亮度/顏色上的差異陣列，而不是像素本身的亮度/顏色值例[Laeseretal.1986]8bits/pixel(256brightness)

3bits/pixel語(yǔ)義依賴（semantic-dependent）的DC方法詞典編碼詞典：全部詞語(yǔ)（words）常用詞語(yǔ)+詞語(yǔ)結(jié)束符號(hào)編碼方法：指向詞典的指針表指向詞典的指針表（常用詞語(yǔ)）+編碼（不常用詞語(yǔ)）語(yǔ)義依賴（semantic-dependent）的數(shù)據(jù)壓縮方法缺點(diǎn)：實(shí)用性有限可以用其他更一般的編碼方法獲得相同效果如huffman編碼、Lempel-Ziv編碼RLE編碼行程編碼(RLE）算法:x1,x2,……

xn

---->(

c1,l1),(

c2,l2),……

(

ck,lk

)

ci:亮度/顏色li:第i行程（相同亮度/顏色的像素的序列）的長(zhǎng)度不需要存儲(chǔ)每一個(gè)象素的顏色值，而僅僅存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色的象素?cái)?shù)目就可以；或者存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色值的行數(shù)。具有相同顏色并且是連續(xù)的象素?cái)?shù)目稱為行程長(zhǎng)度。RLE編碼例：代碼字為：（0，8),（1，3),（8，50),（1，4),(0，8）RLE編碼RLE所能獲得的壓縮比——主要是取決于圖像本身的特點(diǎn)。如果圖像中具有相同顏色的圖像塊越大，圖像塊數(shù)目越少，獲得的壓縮比就越高。反之，壓縮比就越小。RLE是無損壓縮技術(shù)。RLE編碼應(yīng)用：尤其適用于計(jì)算機(jī)生成的圖像，對(duì)減少圖像文件的存儲(chǔ)空間非常有效。（對(duì)顏色豐富的自然圖像不能單純使用RLE一種編碼方法，需要和其他的壓縮編碼技術(shù)聯(lián)合應(yīng)用。）商業(yè)數(shù)據(jù)處理（如連續(xù)多個(gè)0，空格）分解與編碼源信息代碼（長(zhǎng)度）：block->blockblock->variablevariable->blockvariable->variable例：“aa

bbb

cccc

ddddd

eeeeee

fffffffgggggggg”

block->block(120)Sourcemassage codeworda 000b 001c 010d 011e 100f 101g 110space 111例：“aa

bbb

cccc

ddddd

eeeeee

fffffffgggggggg”

variable->variable(30)

Sourcemassage codewordaa 0bbb 1ccccc 10ddddd 11eeeeeee 100fffffff 101gggggggg 110space 111分解與編碼“定義字”與“自由分解”方法定義字（defined-word）方式源信息分解的長(zhǎng)度在編碼調(diào)用之前已確定自由分解（free-parse）方式編碼算法本身決定源信息分解的長(zhǎng)度（變長(zhǎng)）分解與編碼典型算法定義字方式的：Shannon-FanocodingHuffmancodingUniversalcodes(通用碼)Arithmeticcoding(算術(shù)編碼)自由分解方式的：Lempel-ZivcodesAlgorithmBSTWLempel-Ziv編碼variable->block自由分解算法：一規(guī)則：從一個(gè)有限字母表分解出不超過規(guī)定長(zhǎng)度的子串或詞；一編碼方法：將子串順序地映射成固定長(zhǎng)度、可辨認(rèn)的代碼字。Lempel-Ziv編碼策略：選出幾乎必定出現(xiàn)的字串。使得概率大的字符，組成較長(zhǎng)串；概率小的字符，組成較短串。

對(duì)有效利用冗余，因?yàn)榉?hào)的頻繁出現(xiàn)字母重復(fù)高使用模式Lempel-Ziv編碼不斷增長(zhǎng)長(zhǎng)度的語(yǔ)法分析策略：在編碼的每一步，分解出剩余源信息集合中與現(xiàn)有表的某項(xiàng)∞匹配的最長(zhǎng)前綴，追加上源信息集合中該前綴的后一字符c,將∞c加入編碼表中，編為（i,c):i——現(xiàn)有表項(xiàng)的代碼字；c——追加的字符Lempel-Ziv編碼例：“010100010”分解：{0，1，01，00，010}編碼：{(0,0),(0,1),(1,1),(1,0),(3,0)}例：“aa

bbb

cccc

ddddd

eeeeee

fffffffgggggggg”

（3-bits:a~g,

,5-bits:tableindexes,碼長(zhǎng)=173）a 1 e 121

2 12e 13b 3 13e 143b 4 5f 15

5 f 16c 6 16f 17 6c 7 17f 186

8 g 19d 9 19g 209d 10 20g 2110

11 20 22Lempel-Ziv編碼評(píng)價(jià)：簡(jiǎn)單，且貪心（每步找最長(zhǎng)識(shí)別串）漸近最優(yōu)Hash查找實(shí)際應(yīng)用：UNIX資源壓縮，50~60%的壓縮率

LZ78算法

例：輸入為“ABBCBCABA”步驟位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)

LZW算法

例：輸入為“ABBABABAC”步驟位置(序號(hào))詞典輸出(1)A(2)B(3)C11(4)AB122(5)BB233(6)BA244(7)ABA456(8)ABAC763

LZ77算法

例：輸入為“AABCBBABC”步驟位置匹配串字符輸出11A(0,0)A22AB(1,1)