第六章 圖像編碼(2)

1、姓名：石英E_mail：a_l一：概述和分類一：概述和分類l二：基本概念和理論二：基本概念和理論l三：簡(jiǎn)單的編碼方法三：簡(jiǎn)單的編碼方法l四：預(yù)測(cè)編碼四：預(yù)測(cè)編碼l五：變換編碼五：變換編碼l六：國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介六：國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介l一：概述和分類一：概述和分類l二：基本概念和理論二：基本概念和理論l三：簡(jiǎn)單的編碼方法三：簡(jiǎn)單的編碼方法l四：預(yù)測(cè)編碼四：預(yù)測(cè)編碼l五：變換編碼五：變換編碼l六：國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介六：國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介l6.2.1 數(shù)據(jù)冗余數(shù)據(jù)冗余l(xiāng)6.2.2 圖像保真度和質(zhì)量圖像保真度和質(zhì)量l6.2.3 圖像編碼模型圖像編碼模型l6.2.4 信息論簡(jiǎn)介信息論簡(jiǎn)介l6.2.5 基本編碼定理基本編碼定理1

2、. 信息測(cè)量信息測(cè)量概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn))(1log)(log)(EpEpEI隨機(jī)事件隨機(jī)事件E E出現(xiàn)的概率為出現(xiàn)的概率為p(E)p(E)，則它所包含的信息量為：則它所包含的信息量為：概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)要辨識(shí)要辨識(shí)1 1到到3232中選定的某一個(gè)數(shù)，可先提問(wèn)中選定的某一個(gè)數(shù)，可先提問(wèn)：“是否大于是否大于1616？”，得到回答就消去半數(shù)可，得到回答就消去半數(shù)可能事件。每提問(wèn)一次得到回答，可以得到能事件。每提問(wèn)一次得到回答，可以得到1 1bitbit信息量

3、（二進(jìn)制位）。這里共需信息量（二進(jìn)制位）。這里共需5 5次，因此所需次，因此所需的信息量為的信息量為 。532log2概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) kjjjaPaPxH12lognnpxpxpx,2211814813412211,xxxxX 47log12kjjjaPaPxH概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)),(21mxxxXmwwwW,21naaaA,21概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) nNxH2log1dR概述概

4、述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)814813412211,xxxxX1811811411211N 874log147log22nNxH818711dR概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)2N872log247log)(22nNxH818711dR概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)47813813412211N 114747log2nNxH0dR概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)

5、熵與概率的關(guān)系熵與概率的關(guān)系 當(dāng)灰度只有兩級(jí)時(shí)，即當(dāng)灰度只有兩級(jí)時(shí)，即s si i = 0, 1 = 0, 1，且且0 0出現(xiàn)出現(xiàn)概率為概率為p p1 1，1 1出現(xiàn)概率為出現(xiàn)概率為p p2 2=1- p=1- p1 1 ，其熵其熵12112111log)1 (1log)(ppppsH概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) 當(dāng)當(dāng)p p1 1=1/2=1/2， p p2 2=1- p=1- p1 1 =1/2=1/2時(shí)，時(shí)， H(s)=1H(s)=1為為最大值。如圖所示。最大值。如圖所示。概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼

6、變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)l一：概述和分類一：概述和分類l二：基本概念和理論二：基本概念和理論l三：簡(jiǎn)單的編碼方法三：簡(jiǎn)單的編碼方法l四：預(yù)測(cè)編碼四：預(yù)測(cè)編碼l五：變換編碼五：變換編碼l六：國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介六：國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介l6.2.1 數(shù)據(jù)冗余數(shù)據(jù)冗余l(xiāng)6.2.2 圖像保真度和質(zhì)量圖像保真度和質(zhì)量l6.2.3 圖像編碼模型圖像編碼模型l6.2.4 信息論簡(jiǎn)介信息論簡(jiǎn)介l6.2.5 基本編碼定理基本編碼定理l一：概述和分類一：概述和分類l二：基本概念和理論二：基本概念和理論l三：簡(jiǎn)單的編碼方法三：簡(jiǎn)單的編碼方法l四：預(yù)測(cè)編碼四：預(yù)測(cè)編碼l五：變換編碼五：變換編碼l六：國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介六：國(guó)際標(biāo)準(zhǔn)

7、簡(jiǎn)介l6.3.1 變長(zhǎng)編碼（統(tǒng)計(jì)編碼）變長(zhǎng)編碼（統(tǒng)計(jì)編碼）l6.3.2 位平面編碼位平面編碼1. 哈夫曼編碼（哈夫曼編碼（Huffman Encoding）2. 一些亞最優(yōu)變長(zhǎng)碼一些亞最優(yōu)變長(zhǎng)碼3. 算術(shù)編碼（算術(shù)編碼（Arthmetics Encoding）變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼概述概述霍夫曼編碼霍夫曼編碼（1） 基本思想基本思想通過(guò)減少編碼冗余來(lái)達(dá)到壓縮的目的。通過(guò)減少編碼冗余來(lái)達(dá)到壓縮的目的。 基本思想是統(tǒng)計(jì)一下符號(hào)的出現(xiàn)概率；基本思想是統(tǒng)計(jì)一下符號(hào)的出現(xiàn)概率； 建立一個(gè)概率統(tǒng)計(jì)表。建立一個(gè)概率統(tǒng)計(jì)表。將最常出現(xiàn)將最常出

8、現(xiàn)(概率大的概率大的)的符號(hào)用最短的符號(hào)用最短的編碼，的編碼，最少出現(xiàn)的符號(hào)用最長(zhǎng)的編碼。最少出現(xiàn)的符號(hào)用最長(zhǎng)的編碼?；局R(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)霍夫曼編碼霍夫曼編碼（2）例子：建立概率統(tǒng)計(jì)表和編碼樹）例子：建立概率統(tǒng)計(jì)表和編碼樹符號(hào)符號(hào) 概率概率 1 2 3 4 a2 0.4 0.4 0.4 0.4 0.6 a6 0.3 0.3 0.3 0.3 0.4 a1 0.1 0.1 0.2 0.3 a4 0.1 0.1 0.1 a3 0.06 0.1 a5 0.04 概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)

9、準(zhǔn)國(guó)際標(biāo)準(zhǔn)霍夫曼編碼霍夫曼編碼（2）例子：編碼過(guò)程：）例子：編碼過(guò)程：符號(hào)符號(hào) 概率概率 編碼編碼 1 2 3 4a20.4 1 0.4 1 0.4 1 0.4 1 0.6 0a60.3 00 0.3 00 0.3 00 0.3 00 0.4 1a10.1 011 0.1 011 0.2 010 0.3 01a40.1 0100 0.1 0100 0.1 011 a30.06 01010 0.1 0101 a50.04 01011概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)霍夫曼編碼霍夫曼編碼（2）例子：）例子： 解碼過(guò)程：解碼過(guò)程： 01010

10、011 1 1 00概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) a3 a1 a2 a2 a6霍夫曼編碼霍夫曼編碼概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) 變長(zhǎng)碼即非等長(zhǎng)碼，由不同的碼長(zhǎng)的碼字構(gòu)變長(zhǎng)碼即非等長(zhǎng)碼，由不同的碼長(zhǎng)的碼字構(gòu)成。在編碼輸入出現(xiàn)非等概率時(shí)，變長(zhǎng)碼可得到成。在編碼輸入出現(xiàn)非等概率時(shí)，變長(zhǎng)碼可得到較高的編碼效率，使平均碼長(zhǎng)達(dá)到或接近編碼的較高的編碼效率，使平均碼長(zhǎng)達(dá)到或接近編碼的下限。但編碼的限制是碼字要有下限。但編碼的限制是碼字要有單義性單義性（唯一可（唯一可譯）和譯）和非續(xù)長(zhǎng)性

11、非續(xù)長(zhǎng)性（瞬時(shí)可譯）。（瞬時(shí)可譯）。霍夫曼編碼霍夫曼編碼概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)單義性代碼單義性代碼是指任意一個(gè)有限長(zhǎng)的碼字序列，只能被唯是指任意一個(gè)有限長(zhǎng)的碼字序列，只能被唯一地分割成一個(gè)個(gè)碼字，而任何其他分割方法都會(huì)產(chǎn)生一一地分割成一個(gè)個(gè)碼字，而任何其他分割方法都會(huì)產(chǎn)生一些不屬于碼字集合些不屬于碼字集合W W的碼字，符合這個(gè)條件的代碼為單義代的碼字，符合這個(gè)條件的代碼為單義代碼。例如，碼。例如， 對(duì)于一個(gè)有限長(zhǎng)的碼字對(duì)于一個(gè)有限長(zhǎng)的碼字 只只能被分成能被分成 。1230 10 11uuuW100111000213211,u

12、u u u u u霍夫曼編碼霍夫曼編碼概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) 非續(xù)長(zhǎng)代碼非續(xù)長(zhǎng)代碼是指任意一個(gè)碼字都不是其他碼的續(xù)是指任意一個(gè)碼字都不是其他碼的續(xù)長(zhǎng)，即碼字集中任意一個(gè)碼字都不是在其中碼字后面長(zhǎng)，即碼字集中任意一個(gè)碼字都不是在其中碼字后面添加一些碼元所構(gòu)成。如，添加一些碼元所構(gòu)成。如， 就就是續(xù)長(zhǎng)碼，是續(xù)長(zhǎng)碼， 是是 后面加一個(gè)后面加一個(gè)“0”“0”續(xù)長(zhǎng)構(gòu)成，續(xù)長(zhǎng)構(gòu)成，譯碼時(shí)從接受到代碼中，不能立即譯出代表的意思。譯碼時(shí)從接受到代碼中，不能立即譯出代表的意思。12340 10 100 111uuuuW10010霍夫曼編碼霍夫曼

13、編碼（3）算法實(shí)現(xiàn)）算法實(shí)現(xiàn) 第一步：建立一系列的原數(shù)據(jù)縮減量第一步：建立一系列的原數(shù)據(jù)縮減量 通過(guò)對(duì)符號(hào)的概率排序，把最小概率的符號(hào)組成通過(guò)對(duì)符號(hào)的概率排序，把最小概率的符號(hào)組成一個(gè)符號(hào)，以便在下一個(gè)原數(shù)據(jù)縮減量中替換它們。一個(gè)符號(hào)，以便在下一個(gè)原數(shù)據(jù)縮減量中替換它們。 第二步：給每一個(gè)縮減的原始數(shù)據(jù)編碼第二步：給每一個(gè)縮減的原始數(shù)據(jù)編碼從最少的原數(shù)據(jù)開始，向后進(jìn)行到起始原數(shù)據(jù)從最少的原數(shù)據(jù)開始，向后進(jìn)行到起始原數(shù)據(jù)。概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) 霍夫曼編碼已被證明具有最優(yōu)變長(zhǎng)碼性質(zhì)，平均碼長(zhǎng)最霍夫曼編碼已被證明具有最優(yōu)變長(zhǎng)碼性質(zhì)

14、，平均碼長(zhǎng)最短，接近熵值。短，接近熵值。 B碼碼截?cái)喙蚵a截?cái)喙蚵a平移碼平移碼概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) 需要對(duì)大量符號(hào)編碼時(shí)，構(gòu)造最優(yōu)哈夫曼碼需要對(duì)大量符號(hào)編碼時(shí)，構(gòu)造最優(yōu)哈夫曼碼的計(jì)算量很大，此時(shí)常采用一些亞最優(yōu)的變長(zhǎng)編的計(jì)算量很大，此時(shí)常采用一些亞最優(yōu)的變長(zhǎng)編碼方法，通過(guò)犧牲編碼效率來(lái)?yè)Q取編碼計(jì)算的簡(jiǎn)碼方法，通過(guò)犧牲編碼效率來(lái)?yè)Q取編碼計(jì)算的簡(jiǎn)便。便。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)

15、國(guó)際標(biāo)準(zhǔn)B1B2W1C0C00W2C1C01W3C0C0C10W4C0C1C11W5C1C0C00C00W6C1C1C00C01W7C0C0C0C00C10W8C0C0C1C00C11概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)概述概述基本知識(shí)基本知識(shí)簡(jiǎn)單編碼簡(jiǎn)單編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)C1C2C3C400011011 碼字中的碼字中的C1C

16、1、C2C2和和C3C3分別賦予前三個(gè)消息，分別賦予前三個(gè)消息，而后續(xù)的消息則用而后續(xù)的消息則用C4C4和和C1C1、C2C2、C3C3的組合，或的組合，或C4C4的多次重復(fù)與的多次重復(fù)與C1C1、C2C2、C3C3的組合來(lái)表示。的組合來(lái)表示。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) 優(yōu)點(diǎn)：易于實(shí)現(xiàn)，優(yōu)點(diǎn)：易于實(shí)現(xiàn)，且對(duì)于具有單調(diào)減且對(duì)于具有單調(diào)減小概率的輸入信號(hào)小概率的輸入信號(hào)相當(dāng)有效。相當(dāng)有效。符號(hào)符號(hào)出現(xiàn)概率出現(xiàn)概率碼字碼字A10.400A20.301A30.110A40.11100A50.061101A60.041110概述概述基本知識(shí)

17、基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)輸入S1S2S3S4S5S6 rCH(s)概率0.10.060.04L概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)輸入S1S2S3S4S5S6 rCH(s)概率0.10.060.04霍夫曼碼100011010001010010112.20.9750.0251.362.14L概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)輸入S1S2S3S4S5S6 rCH(s)概率0.10.060

18、.04霍夫曼碼100011010001010010112.20.9750.0251.362.14LB1碼C0C1C0C0C0C1C1C0C1C12.60.84概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)輸入S1S2S3S4S5S6 rCH(s)概率0.10.060.04霍夫曼碼100011010001010010112.20.9750.0251.362.14LB1碼C0C1C0C0C0C1C1C0C1C12.60.84S2碼0001101100110111102.40.8950.

19、1151.252.14概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)輸入S1S2S3S4S5S6 rCH(s)概率0.10.060.04霍夫曼碼100011010001010010112.20.9750.0251.362.14LB1碼C0C1C0C0C0C1C1C0C1C12.60.84S2碼0001101100110111102.40.8950.1151.252.14自然碼00000101001110010130.7130.40212.14概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變

20、換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) （一）基本思想（一）基本思想 算術(shù)編碼方法沒(méi)有沿用一般數(shù)據(jù)編碼技術(shù)中用算術(shù)編碼方法沒(méi)有沿用一般數(shù)據(jù)編碼技術(shù)中用一個(gè)特定碼代替一個(gè)輸入符號(hào)的做法，而是，把要一個(gè)特定碼代替一個(gè)輸入符號(hào)的做法，而是，把要壓縮處理的整段數(shù)據(jù)一起映射到一段實(shí)數(shù)半開區(qū)間壓縮處理的整段數(shù)據(jù)一起映射到一段實(shí)數(shù)半開區(qū)間0，1內(nèi)的某一區(qū)段上，構(gòu)造出小于內(nèi)的某一區(qū)段上，構(gòu)造出小于1大于或等于大于或等于0的數(shù)值。這個(gè)數(shù)值是輸入信源數(shù)據(jù)序列的唯一可譯的數(shù)值。這個(gè)數(shù)值是輸入信源數(shù)據(jù)序列的唯一可譯代碼。代碼。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) （二）例子（二

21、）例子 設(shè)輸入信源流為設(shè)輸入信源流為“XY YZ”，其出現(xiàn)的概率和其出現(xiàn)的概率和設(shè)定的取值范圍如下：設(shè)定的取值范圍如下： 字符字符 概率概率 范圍范圍 空格（空格（SPACE） 0.2 0.0, 0.2 X 0.2 0.2, 0.4 Y 0.4 0.4, 0.8 Z 0.2 0.8, 1.0概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) （二）例子（二）例子 注意：注意：區(qū)間是根據(jù)字符出現(xiàn)的概率劃分區(qū)間是根據(jù)字符出現(xiàn)的概率劃分的，字符具體分在哪個(gè)區(qū)間范圍對(duì)編碼本身的，字符具體分在哪個(gè)區(qū)間范圍對(duì)編碼本身沒(méi)有影響，只要編碼器和譯碼器對(duì)字符的概沒(méi)有影響，只

22、要編碼器和譯碼器對(duì)字符的概率空間有相同的定義即可。率空間有相同的定義即可。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) （二）例子（二）例子 編碼過(guò)程如下：編碼過(guò)程如下： 讀入數(shù)據(jù)流字符讀入數(shù)據(jù)流字符 區(qū)間區(qū)間 區(qū)間范圍區(qū)間范圍 X 0.2, 0.4 0.2 Y 0.28, 0.36 0.08 SPACE 0.28, 0.296 0.016 Y 0.2864, 0.2928 0.0064 Z 0.29152, 0.2928 字符字符 概率概率 范圍范圍SPACE 0.2 0.0, 0.2X 0.2 0.2, 0.4Y 0.4 0.4, 0.8Z 0

23、.2 0.8, 1.0概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) （二）例子（二）例子 當(dāng)字符串被全部編碼后，其范圍當(dāng)字符串被全部編碼后，其范圍0.29152, 0.2928已經(jīng)很小，我們可以取這個(gè)區(qū)間的下限已經(jīng)很小，我們可以取這個(gè)區(qū)間的下限0.29152作為作為“XY YZ”進(jìn)行壓縮編碼后的輸出進(jìn)行壓縮編碼后的輸出代碼。代碼。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)從上述討論可以看出，統(tǒng)計(jì)編碼是一種高效編碼

24、方法。但從上述討論可以看出，統(tǒng)計(jì)編碼是一種高效編碼方法。但是，它也有是，它也有缺點(diǎn)缺點(diǎn)：1.1. 碼長(zhǎng)不同碼長(zhǎng)不同，需要用數(shù)據(jù)緩沖單元收集可變比特率的代碼，需要用數(shù)據(jù)緩沖單元收集可變比特率的代碼，使用不便；使用不便；2.2. 代碼缺乏構(gòu)造性，即不能用數(shù)學(xué)方法建立一一對(duì)應(yīng)的關(guān)代碼缺乏構(gòu)造性，即不能用數(shù)學(xué)方法建立一一對(duì)應(yīng)的關(guān)系，系，只能通過(guò)查表方法實(shí)現(xiàn)對(duì)應(yīng)關(guān)系只能通過(guò)查表方法實(shí)現(xiàn)對(duì)應(yīng)關(guān)系，如果消息數(shù)目太，如果消息數(shù)目太多，表就會(huì)很大，設(shè)備就會(huì)復(fù)雜；多，表就會(huì)很大，設(shè)備就會(huì)復(fù)雜；3.3. 這些方法在編碼過(guò)程中需要知道每個(gè)消息的出現(xiàn)概率，這些方法在編碼過(guò)程中需要知道每個(gè)消息的出現(xiàn)概率，實(shí)際使用時(shí)，實(shí)際

25、使用時(shí)，這些概率是很難事先確切得到的這些概率是很難事先確切得到的。l一：概述和分類一：概述和分類l二：基本概念和理論二：基本概念和理論l三：簡(jiǎn)單的編碼方法三：簡(jiǎn)單的編碼方法l四：預(yù)測(cè)編碼四：預(yù)測(cè)編碼l五：變換編碼五：變換編碼l六：國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介六：國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介l6.3.1 變長(zhǎng)編碼變長(zhǎng)編碼l6.3.2 位平面編碼位平面編碼概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) 位平面編碼是一種基于將灰度值圖像分位平面編碼是一種基于將灰度值圖像分解成一系列二值圖，再對(duì)每一幅二值圖采用解成一系列二值圖，再對(duì)每一幅二值圖采用二元壓縮的方法進(jìn)行壓縮的技術(shù)。這種技術(shù)二元

26、壓縮的方法進(jìn)行壓縮的技術(shù)。這種技術(shù)除能消除或減少編碼冗余外，也能消除或減除能消除或減少編碼冗余外，也能消除或減少圖像中的象素間冗余。少圖像中的象素間冗余。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)1. 位平面分解位平面分解2. 常數(shù)塊編碼常數(shù)塊編碼3. 1D游程編碼游程編碼4. 2D游程編碼游程編碼5. 邊界跟蹤和編碼邊界跟蹤和編碼6. 編碼算法比較編碼算法比較概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)1. 位平面分解位平面分解 具有具有mbit灰度級(jí)的圖像中象素的灰度值可灰度級(jí)的圖像中象素的灰度值

27、可以由如下多項(xiàng)式來(lái)表示：以由如下多項(xiàng)式來(lái)表示： am-12m-1+am-22m-2+a121+a020 把上述多項(xiàng)式的把上述多項(xiàng)式的m個(gè)系數(shù)分別分到個(gè)系數(shù)分別分到m個(gè)個(gè)1bit的位平面中去就能把一幅灰度圖分解成一系列的位平面中去就能把一幅灰度圖分解成一系列二值圖集合。二值圖集合。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)1. 位平面分解位平面分解 這種分解方法的缺點(diǎn)：象素點(diǎn)的微小變化這種分解方法的缺點(diǎn)：象素點(diǎn)的微小變化有可能對(duì)位平面的復(fù)雜度產(chǎn)生較明顯的影響。有可能對(duì)位平面的復(fù)雜度產(chǎn)生較明顯的影響。 例如：空間相鄰象素的灰度值分別為例如：空間相鄰象

28、素的灰度值分別為 127(01111111)2和和128(10000000)2 那么圖像的每個(gè)位平面在這個(gè)位置上都有那么圖像的每個(gè)位平面在這個(gè)位置上都有從從1到到0（或從（或從0到到1）的過(guò)渡。采用灰度碼減少）的過(guò)渡。采用灰度碼減少這種影響。這種影響。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)1. 位平面分解位平面分解 灰度碼定義：灰度碼定義： gi= ai ai+1 0=i=m-2 ai i=m-1 表示異或表示異或 用灰度碼表示用灰度碼表示127和和128分別為：分別為： 010000002 110000002此時(shí)此時(shí)8個(gè)位平面只有一個(gè)從個(gè)位

29、平面只有一個(gè)從0到到1的過(guò)渡。的過(guò)渡。+概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)例例6.3.2 利用灰度碼表達(dá)圖象的位平面圖實(shí)例利用灰度碼表達(dá)圖象的位平面圖實(shí)例下圖給出下圖給出1組灰度碼表達(dá)的位平面圖。圖組灰度碼表達(dá)的位平面圖。圖(a)為為1幅幅8 bit灰度級(jí)圖象。圖灰度級(jí)圖象。圖(b)至圖至圖(i)分別為用灰度碼表達(dá)的分別為用灰度碼表達(dá)的8個(gè)位個(gè)位面面(從高位到低位從高位到低位)圖。圖。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變

30、換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn) 由這些圖可見低位面圖比高位面圖復(fù)雜，即低位由這些圖可見低位面圖比高位面圖復(fù)雜，即低位面圖比高位面圖包括的細(xì)節(jié)要多，但也更隨機(jī)。如將面圖比高位面圖包括的細(xì)節(jié)要多，但也更隨機(jī)。如將這里的這里的8個(gè)灰度碼位面圖與其個(gè)灰度碼位面圖與其8個(gè)二值位面圖相比較，個(gè)二值位面圖相比較，可見灰度碼表達(dá)的位面圖復(fù)雜度較低，但具有視覺(jué)意可見灰度碼表達(dá)的位面圖復(fù)雜度較低，但具有視覺(jué)意義信息的位面圖數(shù)量更多。義信息的位面圖數(shù)量更多。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)2. 常數(shù)塊編碼（常數(shù)塊編碼（constant area coding, C

31、AC） 采用常數(shù)塊編碼技術(shù)將圖像分為全黑、全百或混采用常數(shù)塊編碼技術(shù)將圖像分為全黑、全百或混合的合的m*n尺寸的塊。對(duì)出現(xiàn)頻率高的一類編尺寸的塊。對(duì)出現(xiàn)頻率高的一類編0，其他，其他的分別編的分別編10和和11作為前綴，后面跟上該塊的用作為前綴，后面跟上該塊的用m*n比比特表示的模式。特表示的模式。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)2. 常數(shù)塊編碼（常數(shù)塊編碼（constant area coding, CAC） 舉例：文檔的壓縮編碼舉例：文檔的壓縮編碼 文檔的特點(diǎn)：大部分是白色部分組成。文檔的特點(diǎn)：大部分是白色部分組成。 編碼方法：白色塊

32、區(qū)域編成編碼方法：白色塊區(qū)域編成0，其他塊用，其他塊用1接上該塊接上該塊的位模式編碼。的位模式編碼。此法稱為跳躍白色塊此法稱為跳躍白色塊(white block skipping, WBS)概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)3. 1-D游程編碼（游程編碼（ Run Length Coding ,RLC）概念：概念：游程游程：具有相同灰度值的像素序列。：具有相同灰度值的像素序列。編碼思想：編碼思想：去除像素冗余。去除像素冗余。用游程的灰度和游程的長(zhǎng)度代替游程本身。用游程的灰度和游程的長(zhǎng)度代替游程本身。例：設(shè)重復(fù)次數(shù)為例：設(shè)重復(fù)次數(shù)為 iC,

33、 重復(fù)像素值為重復(fù)像素值為 iP編碼為：編碼為：iCiP iCiP iCiP 編碼前：編碼前：aaaaaaabbbbbbcccccccc 編碼后：編碼后：7a6b8c特別是對(duì)二值圖象，效果尤為顯著。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)3. 1-D游程編碼（游程編碼（ Run Length Coding ,RLC）分析：分析：對(duì)于有大面積色塊的圖像，壓縮效果很好對(duì)于有大面積色塊的圖像，壓縮效果很好對(duì)于紛雜的圖像，壓縮效果不好，最壞情況下，會(huì)加對(duì)于紛雜的圖像，壓縮效果不好，最壞情況下，會(huì)加倍圖像倍圖像概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)

34、編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)3. 1-D游程編碼（游程編碼（ Run Length Coding ,RLC）1-D游程編碼思想游程編碼思想 對(duì)圖象進(jìn)行行掃描時(shí)，行內(nèi)各象素的灰度級(jí)可對(duì)圖象進(jìn)行行掃描時(shí)，行內(nèi)各象素的灰度級(jí)可組成一個(gè)整數(shù)序列組成一個(gè)整數(shù)序列x x1 1, , x x2 2, , , , x xN N。在行程編碼中，在行程編碼中，我們將這個(gè)序列映射成整數(shù)對(duì)我們將這個(gè)序列映射成整數(shù)對(duì)( (g gk k, , l lk k) )，其中其中g(shù) gk k表表示灰度級(jí)，示灰度級(jí)， l lk k表示行程長(zhǎng)度，等于具有相同灰度表示行程長(zhǎng)度，等于具有相同灰度級(jí)的相鄰象素的數(shù)目。級(jí)的

35、相鄰象素的數(shù)目。 行程長(zhǎng)度行程長(zhǎng)度l lk k是一個(gè)隨機(jī)變量，其分布具有很大是一個(gè)隨機(jī)變量，其分布具有很大的不均勻性。采用的不均勻性。采用B B碼編碼更為合適。碼編碼更為合適。概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)3. 1-D游程編碼（游程編碼（ Run Length Coding ,RLC）1-D游程舉例游程舉例例：映射對(duì)例：映射對(duì) 8 8個(gè)灰度級(jí)，個(gè)灰度級(jí)，2424個(gè)象素個(gè)象素 對(duì)其編碼，總的比特?cái)?shù)，對(duì)其編碼，總的比特?cái)?shù)， 至少至少24243 37272bitbit。 如果對(duì)如果對(duì)( (g gk k, , l lk k) )編碼，灰度級(jí)編碼，灰度級(jí)3 3bitbit，游程游程4 4bitbit，每對(duì)參數(shù)用每對(duì)參數(shù)用7 7bitbit，總比特?cái)?shù)總比特?cái)?shù)2828bitbit就夠。就夠。kgklk1362510342486概述概述基本知識(shí)基本知識(shí)統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼 國(guó)際標(biāo)準(zhǔn)國(guó)際標(biāo)準(zhǔn)4. 2-D游程編碼（游程編碼（ Run Length Coding ,RLC）2-D游程編碼的思想游程編碼的思想 一維行程編碼：只考慮消除每行內(nèi)象素（或一維行程編碼：只考慮消除每行內(nèi)象素（或水平分解元素）的相關(guān)性，未考慮行間象素（垂水平分解元素）的相關(guān)性，未考慮行間象素（垂直分