多媒體信息技術(shù)基礎(chǔ)-無(wú)損壓縮編碼課件

多媒體技術(shù)基礎(chǔ)----無(wú)損壓縮編碼多媒體技術(shù)基礎(chǔ)----無(wú)損壓縮編碼主要內(nèi)容概述統(tǒng)計(jì)編碼RLE編碼（行程編碼）詞典編碼主要內(nèi)容概述主要內(nèi)容概述有損壓縮無(wú)損壓縮統(tǒng)計(jì)編碼RLE編碼（行程編碼）詞典編碼主要內(nèi)容概述主要內(nèi)容概述統(tǒng)計(jì)編碼信息量與熵香農(nóng)范諾編碼霍夫曼編碼算術(shù)編碼RLE編碼（行程編碼）詞典編碼主要內(nèi)容概述主要內(nèi)容概述統(tǒng)計(jì)編碼RLE編碼（行程編碼，游長(zhǎng)編碼）詞典編碼指針型LZ77LZSS詞典型LZ78LZW主要內(nèi)容概述概述無(wú)損壓縮使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)（或者叫做還原，解壓縮），重構(gòu)后數(shù)據(jù)與原來(lái)的數(shù)據(jù)完全相同有損壓縮

使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。概述無(wú)損壓縮統(tǒng)計(jì)編碼

給已知統(tǒng)計(jì)信息的符號(hào)分配代碼的數(shù)據(jù)無(wú)損壓縮方法信息量與熵香農(nóng)范諾編碼霍夫曼編碼算術(shù)編碼不定長(zhǎng)編碼廣泛用在JPEG,MPEG,H.26X等各種信息編碼標(biāo)準(zhǔn)中統(tǒng)計(jì)編碼不定長(zhǎng)編碼廣泛用在JPEG,MPEG統(tǒng)計(jì)編碼—信息量與熵信息量與熵熵的大小表示非冗余的不可壓縮的信息量某個(gè)符號(hào)的信息量與對(duì)該符號(hào)進(jìn)行編碼時(shí)需要的位數(shù)相等。熵是字符集的平均信息量如果對(duì)數(shù)的底數(shù)用2，熵的單位就用“香農(nóng)(Sh)”，也稱“位(bit)”?！拔弧笔?948年Shannon首次使用的術(shù)語(yǔ)。事件概率統(tǒng)計(jì)編碼—信息量與熵信息量與熵事件概率統(tǒng)計(jì)編碼—香農(nóng)范諾編碼香農(nóng)范諾編碼“從上到下”的熵編碼首先按照符號(hào)出現(xiàn)的頻度或概率排序使用遞歸方法分成前后兩個(gè)部分分割規(guī)則：兩個(gè)部分頻度（概率）和值差最小形成二叉樹(shù)，左枝為0，右枝為1問(wèn)題：錯(cuò)誤傳播順序讀取統(tǒng)計(jì)編碼—香農(nóng)范諾編碼香農(nóng)范諾編碼統(tǒng)計(jì)編碼—算術(shù)編碼算術(shù)編碼基本思想是用0和1之間的一個(gè)數(shù)值代表整個(gè)輸入字符流，而不是給輸入流中的每個(gè)字符分別指定一個(gè)碼字首先在0和1之間為每個(gè)字符根據(jù)其概率分配一個(gè)子間隔，使這些字符合集為整個(gè)[0,1]空間，交集為空根據(jù)當(dāng)前輸入字符確定進(jìn)入某子間隔，以這個(gè)子間隔作為分配單元進(jìn)行二次分配所有字符輸入完畢后，從最終間隔區(qū)間選數(shù)統(tǒng)計(jì)編碼—算術(shù)編碼算術(shù)編碼統(tǒng)計(jì)編碼—算術(shù)編碼算術(shù)編碼問(wèn)題精度導(dǎo)致溢出問(wèn)題---比例縮放必須接受到所有位數(shù)之后才可以開(kāi)始譯碼錯(cuò)誤敏感度高應(yīng)用

在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)中（如JPEG、JBIG）中扮演了重要角色統(tǒng)計(jì)編碼—算術(shù)編碼算術(shù)編碼RLE編碼RLE編碼利用重復(fù)的數(shù)據(jù)單元有相同的數(shù)值這一特點(diǎn)對(duì)數(shù)據(jù)進(jìn)行壓縮。思想：對(duì)相同的數(shù)值只編碼一次，同時(shí)計(jì)算出相同值重復(fù)出現(xiàn)的次數(shù)。應(yīng)用：在JPEG，MPEG，H.261和H.263等壓縮方法中，RLE用來(lái)對(duì)圖像數(shù)據(jù)變換和量化后的系數(shù)進(jìn)行編碼RLE編碼RLE編碼RLE編碼RLE編碼RLE編碼RLE編碼詞典編碼

文本中的詞用它在詞典中表示位置的號(hào)碼代替的一種無(wú)損數(shù)據(jù)壓縮方法。指針類LZ77LZSS詞典類LZ78LZW詞典編碼文本中的詞用它在詞典中表示位置的號(hào)碼代替的一種詞典編碼—指針類指針類編碼算法用已經(jīng)出現(xiàn)過(guò)的字符串替代重復(fù)的部分編碼器的輸出僅僅是指向早期出現(xiàn)過(guò)的字符串的“指針”詞典編碼—指針類指針類編碼算法詞典編碼—指針類—LZ77編碼輸出比編碼信息大：對(duì)于綠色行，(Pointer，Length)Characters大于其編碼的信息。額外輸出：未匹配字符被輸出了，但是它們完全可以和后面的字符構(gòu)成新的匹配，例如藍(lán)色行，輸出的B實(shí)際上也可以構(gòu)成匹配，但是卻被直接輸出了窗口前向窗口匹配串字符輸出AABCBBABC--A

(0，0)A

AABCBBABCA

B

(1，1)B

AABCBBABC--C

(0，0)C

AABCBBABCBB(2，1)BAABCBBABCAB

C

$(5，3)$

AABCBBABC詞典編碼—指針類—LZ77編碼輸出比編碼信息大：對(duì)于綠色行，詞典編碼—指針類—LZSS位置1234567891011字符

A

A

B

B

C

B

B

A

A

B

C

窗口前向窗口匹配串輸出AABBCBBAABC--A

AABBCBBAABCA

A

AABBCBBAABC--B

AABBCBBAABCB

B

AABBCBBAABC--C

AABBCBBAABCBB

(3，2)

AABBCBBAABCAAB

(7，3)

AABBCBBAABCC

C

AABBCBBAABC詞典編碼—指針類—LZSS位置1234567詞典編碼—指針類—LZSS文檔壓縮程序都使用了LZSS的思想，例如PKZip，ARJ，LHArc和ZOO等，差別僅僅是指針的長(zhǎng)短、窗口的大小等有所不同LZSS同樣可以和熵編碼聯(lián)合使用ARJ與霍夫曼編碼聯(lián)用PKZip與Shannon-Fano聯(lián)用詞典編碼—指針類—LZSS文檔壓縮程序都使用了LZSS的思想詞典編碼—詞典類詞典類編碼算法從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語(yǔ)詞典”編碼器輸出詞典中的短語(yǔ)“索引號(hào)”，而不是短語(yǔ)詞典編碼—詞典類詞典類編碼算法詞典編碼—詞典類—LZ78位置123456789字符A

B

B

C

B

C

A

B

A步驟（相當(dāng)于碼字）字符流

輸出

詞典1ABBCBCABA(0，A)

A

2BBCBCABA(0，B)

B

3BCBCABA(2，C)

BC

4BCABA(3，A)

BCA

5BA(2，A)

BA

詞典編碼—詞典類—LZ78位置1234567詞典編碼—詞典類—LZ78優(yōu)點(diǎn)：LZ77需要搜索遍歷搜索窗口以尋找最大匹配字符串，而LZ78之需要比較W+C和詞典的字符串是否相同，這是它的最大優(yōu)點(diǎn)問(wèn)題：與LZ77類似詞典編碼—詞典類—LZ78優(yōu)點(diǎn)：LZ77需要搜索遍歷搜索窗口詞典編碼—詞典類—LZW位置123456789字符A

B

B

A

B

A

B

A

C

步驟字符流

輸出

詞典11(1)

(4)AB

22(2)

(5)BB

33(2)

(6)BA

44(4)

(7)ABA

56(7)

(8)ABAC