1、第三章第三章 圖像壓縮編碼圖像壓縮編碼中國(guó)礦業(yè)大學(xué)中國(guó)礦業(yè)大學(xué)信電學(xué)院信電學(xué)院l 3.1 圖像編碼理論分類圖像編碼理論分類l 3.2 數(shù)據(jù)壓縮與信息論基礎(chǔ)數(shù)據(jù)壓縮與信息論基礎(chǔ)l 3.3 霍夫曼編碼霍夫曼編碼l 3.4 游程長(zhǎng)度編碼游程長(zhǎng)度編碼l 3.5 算術(shù)編碼算術(shù)編碼 l 3.6 LZW字典編碼字典編碼 3.1 圖像壓縮編碼分類圖像壓縮編碼分類 一般從信息論角度出發(fā)分為兩大類：一般從信息論角度出發(fā)分為兩大類： 冗余度壓縮方法冗余度壓縮方法 信息量壓縮方法信息量壓縮方法1、冗余度壓縮方法：也稱無損壓縮，信息保、冗余度壓縮方法：也稱無損壓縮，信息保持編碼或熵編碼。持編碼或熵編碼。具體講為解碼圖像

2、和壓縮編碼具體講為解碼圖像和壓縮編碼前圖像嚴(yán)格相同，沒有失真。前圖像嚴(yán)格相同，沒有失真。冗余度壓縮方法的核心是基于統(tǒng)計(jì)模型，減少或完冗余度壓縮方法的核心是基于統(tǒng)計(jì)模型，減少或完全去除源數(shù)據(jù)流中的冗余，同時(shí)保持信息不變?？扇コ磾?shù)據(jù)流中的冗余，同時(shí)保持信息不變?？蓪?shí)現(xiàn)編碼與解碼互逆。實(shí)現(xiàn)編碼與解碼互逆。 ( (第第3 3章壓縮方法章壓縮方法) )2、信息量壓縮方法：、信息量壓縮方法：也稱有損壓縮，失真度編碼或熵壓縮編碼。也稱有損壓縮，失真度編碼或熵壓縮編碼。即解碼圖像和原始圖像是有差別的，允許有一定失即解碼圖像和原始圖像是有差別的，允許有一定失真。真。信息量壓縮方法是以犧牲部分信息量為代價(jià)而換

3、取信息量壓縮方法是以犧牲部分信息量為代價(jià)而換取縮短平均碼長(zhǎng)的編碼壓縮方法。由于在壓縮過程中縮短平均碼長(zhǎng)的編碼壓縮方法。由于在壓縮過程中在允許前提下丟失一部分信息，所以圖像還原后與在允許前提下丟失一部分信息，所以圖像還原后與壓縮前不會(huì)完全一致。壓縮前不會(huì)完全一致。 (第第4、5章壓縮方法章壓縮方法)信息量壓縮方法不能實(shí)現(xiàn)編碼與解碼互逆。信息量壓縮方法不能實(shí)現(xiàn)編碼與解碼互逆。 壓縮編碼分類統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼(無損編碼無損編碼)有損編碼有損編碼游程編碼游程編碼Huffman編碼編碼算術(shù)編碼算術(shù)編碼主要分兩大類主要分兩大類LZW字典編碼字典編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼DFTDCTK-L變換變換香

4、農(nóng)編碼香農(nóng)編碼一、圖像編碼技術(shù)的必要性：一、圖像編碼技術(shù)的必要性：1. 1. 信息傳輸方式發(fā)生了很大的改變信息傳輸方式發(fā)生了很大的改變n 通信方式的改變通信方式的改變 文字文字+語音語音圖像圖像+文字文字+語音語音n 通信對(duì)象的改變通信對(duì)象的改變 人與人人與人人與機(jī)器，機(jī)器與機(jī)器人與機(jī)器，機(jī)器與機(jī)器要求圖像的保真度和傳輸?shù)膶?shí)時(shí)性。要求圖像的保真度和傳輸?shù)膶?shí)時(shí)性。3.2.1 數(shù)據(jù)壓縮與數(shù)據(jù)冗余數(shù)據(jù)壓縮與數(shù)據(jù)冗余3.2 數(shù)據(jù)壓縮與信息論基礎(chǔ)數(shù)據(jù)壓縮與信息論基礎(chǔ) 2.2.圖像傳輸與存儲(chǔ)需要的信息量空間：圖像傳輸與存儲(chǔ)需要的信息量空間： 如一部如一部9090分鐘的彩色電影，每秒放映分鐘的彩色電影，每秒

5、放映2424幀。把幀。把它數(shù)字化，每幀它數(shù)字化，每幀512512 512512像素，每像素的像素，每像素的 、 、 三三分量分別占分量分別占8bit8bit，則總比特?cái)?shù)為，則總比特?cái)?shù)為 9090 6060 2424 3 3 512512 512512 8bit=8bit=。 如一張如一張CDCD光盤可存光盤可存600600兆字節(jié)數(shù)據(jù)，這部電影光兆字節(jié)數(shù)據(jù)，這部電影光圖像（還有聲音）就需要圖像（還有聲音）就需要張張CDCD光盤用來存儲(chǔ)。光盤用來存儲(chǔ)。 因此，傳輸帶寬、速度、存儲(chǔ)器容量的限因此，傳輸帶寬、速度、存儲(chǔ)器容量的限制使得對(duì)圖象數(shù)據(jù)進(jìn)行壓縮顯得非常必要。制使得對(duì)圖象數(shù)據(jù)進(jìn)行壓縮顯得非常必要

6、。二、圖像編碼技術(shù)的可能性：二、圖像編碼技術(shù)的可能性：1 1、從信息論觀點(diǎn)來看，圖像作為一信源，描、從信息論觀點(diǎn)來看，圖像作為一信源，描述圖像信源數(shù)據(jù)是有效信息量和冗余量?jī)刹糠质鰣D像信源數(shù)據(jù)是有效信息量和冗余量?jī)刹糠纸M成。組成。 去除冗余量可節(jié)省存儲(chǔ)和傳輸中的開銷，同時(shí)去除冗余量可節(jié)省存儲(chǔ)和傳輸中的開銷，同時(shí)不損害圖像信源中有效信息量。不損害圖像信源中有效信息量。 如果不同的方法表示給定量的信息用了不同的如果不同的方法表示給定量的信息用了不同的數(shù)據(jù)量，那么使用較多數(shù)據(jù)量的方法中，有些數(shù)據(jù)數(shù)據(jù)量，那么使用較多數(shù)據(jù)量的方法中，有些數(shù)據(jù)必然代表無用的信息，或者為重復(fù)地表示了其它數(shù)必然代表無用的信息，

7、或者為重復(fù)地表示了其它數(shù)據(jù)已表示的信息，這為數(shù)據(jù)冗余的概念。據(jù)已表示的信息，這為數(shù)據(jù)冗余的概念。 什么是數(shù)據(jù)冗余呢？什么是數(shù)據(jù)冗余呢？ 一幅圖像中像素灰度出現(xiàn)的不均勻性。如果用同一幅圖像中像素灰度出現(xiàn)的不均勻性。如果用同 樣長(zhǎng)度比特表示每一個(gè)灰度，則必然存在冗余。樣長(zhǎng)度比特表示每一個(gè)灰度，則必然存在冗余。 圖像能量在變換域內(nèi)分布的不均勻性，大部分能圖像能量在變換域內(nèi)分布的不均勻性，大部分能 量集中在低頻部分，而小部分能量集中在高和較量集中在低頻部分，而小部分能量集中在高和較 高的頻率部分。則高頻能量為數(shù)據(jù)冗余。高的頻率部分。則高頻能量為數(shù)據(jù)冗余。 圖像像素在時(shí)間和空間上的相關(guān)性造成信息冗余。圖

8、像像素在時(shí)間和空間上的相關(guān)性造成信息冗余?？臻g冗余：鄰近像素灰度分布的相關(guān)性很強(qiáng)?？臻g冗余：鄰近像素灰度分布的相關(guān)性很強(qiáng)。頻間冗余：多譜段圖像中各譜段圖像對(duì)應(yīng)像素之間頻間冗余：多譜段圖像中各譜段圖像對(duì)應(yīng)像素之間 灰度相關(guān)性很強(qiáng)?；叶认嚓P(guān)性很強(qiáng)。時(shí)間冗余：序列圖像幀間畫面對(duì)應(yīng)像素灰度的相關(guān)時(shí)間冗余：序列圖像幀間畫面對(duì)應(yīng)像素灰度的相關(guān) 性很強(qiáng)。性很強(qiáng)。 視覺冗余：視覺冗余： 是指人眼不能感知或不敏感的那部分是指人眼不能感知或不敏感的那部分 圖像信息。圖像信息。信息熵冗余：信息熵冗余： 也稱編碼冗余，如果圖像中平均每個(gè)也稱編碼冗余，如果圖像中平均每個(gè) 像素使用的比特?cái)?shù)大于該圖像的信息像素使用的比特?cái)?shù)

9、大于該圖像的信息 熵，則圖像中存在冗余。熵，則圖像中存在冗余。結(jié)構(gòu)冗余：結(jié)構(gòu)冗余： 圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。 知識(shí)冗余：知識(shí)冗余： 在有些圖像中還包含與某些先驗(yàn)知識(shí)在有些圖像中還包含與某些先驗(yàn)知識(shí) 有關(guān)的信息。有關(guān)的信息。n描述語言描述語言 1 1）“這是一幅這是一幅 2 2* *2 2的圖像，的圖像，圖像的第一個(gè)像素是紅的，圖像的第一個(gè)像素是紅的，第二個(gè)像素是紅的，第三個(gè)第二個(gè)像素是紅的，第三個(gè)像素是紅的，第四個(gè)像素是像素是紅的，第四個(gè)像素是紅的紅的”。2 2）“這是一幅這是一幅2 2* *2 2的圖的圖 像，像，整幅圖都是紅色的整幅圖都是紅色

10、的”。 由此我們知道，整理圖 像的描述方法可以達(dá)到 壓縮的目的。 圖像冗余無損壓縮的原理圖像冗余無損壓縮的原理RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGB16RGB從原來的從原來的16*3*8=284bits壓縮為：壓縮為： (1+3)*8=32bits 圖像冗余有損壓縮的原理圖像冗余有損壓縮的原理34343434343434343434343434343434343434343434343434253436353434343434323434333730343434343434343435343431利用各種冗余信息，利用各種冗余信息， 壓

11、縮編碼技術(shù)能夠很好地解決在壓縮編碼技術(shù)能夠很好地解決在將模擬信號(hào)轉(zhuǎn)換為數(shù)字信號(hào)后所產(chǎn)生的帶寬需求增加將模擬信號(hào)轉(zhuǎn)換為數(shù)字信號(hào)后所產(chǎn)生的帶寬需求增加的問題，的問題， 是使數(shù)字信號(hào)走上實(shí)用化的關(guān)鍵技術(shù)之一。是使數(shù)字信號(hào)走上實(shí)用化的關(guān)鍵技術(shù)之一。表表1 幾種常見應(yīng)用的碼率幾種常見應(yīng)用的碼率 2.2.應(yīng)用環(huán)境允許圖像有一定程度地失真：應(yīng)用環(huán)境允許圖像有一定程度地失真： 接收端圖像設(shè)備分辨率降低，則可降低圖像分辨接收端圖像設(shè)備分辨率降低，則可降低圖像分辨 率。率。 根據(jù)人的視覺特性對(duì)不敏感區(qū)進(jìn)行降分辨率編碼。根據(jù)人的視覺特性對(duì)不敏感區(qū)進(jìn)行降分辨率編碼。 人眼對(duì)靜態(tài)物體的敏感程度大于對(duì)動(dòng)態(tài)物體敏感人眼對(duì)靜

12、態(tài)物體的敏感程度大于對(duì)動(dòng)態(tài)物體敏感 程度，可減少表示動(dòng)態(tài)物體程度，可減少表示動(dòng)態(tài)物體bitbit數(shù)；數(shù)； 人眼對(duì)圖像中心信息敏感程度大于對(duì)圖像邊緣信人眼對(duì)圖像中心信息敏感程度大于對(duì)圖像邊緣信 息敏感程度，可對(duì)邊緣信息少分配息敏感程度，可對(duì)邊緣信息少分配bitbit數(shù)。數(shù)。 應(yīng)用方關(guān)心圖像區(qū)域有限，可對(duì)其余部分圖像可應(yīng)用方關(guān)心圖像區(qū)域有限，可對(duì)其余部分圖像可 采用空間和灰度級(jí)上的粗化。采用空間和灰度級(jí)上的粗化。 對(duì)于識(shí)別，圖像特征抽取和描述也是數(shù)據(jù)壓縮。對(duì)于識(shí)別，圖像特征抽取和描述也是數(shù)據(jù)壓縮。3.2.2 圖像壓縮編碼系統(tǒng)的基本構(gòu)成圖像壓縮編碼系統(tǒng)的基本構(gòu)成3.2 數(shù)據(jù)壓縮與信息論基礎(chǔ)數(shù)據(jù)壓縮與

13、信息論基礎(chǔ)圖圖像像信信息息源源信信源源編編碼碼器器信信道道編編碼碼器器信信道道信信道道解解碼碼器器信信源源解解碼碼器器圖圖像像輸輸出出編碼器編碼器解碼器解碼器信源編碼功能是將信源編碼輸出一系列信源編碼功能是將信源編碼輸出一系列二進(jìn)制數(shù)字序列二進(jìn)制數(shù)字序列信道編碼功能是將輸入二進(jìn)制序列形信道編碼功能是將輸入二進(jìn)制序列形成能夠在信道中傳輸?shù)拇a，具有檢錯(cuò)成能夠在信道中傳輸?shù)拇a，具有檢錯(cuò)糾錯(cuò)糾錯(cuò)3.2.2 圖像壓縮編碼系統(tǒng)的基本構(gòu)成圖像壓縮編碼系統(tǒng)的基本構(gòu)成3.2 數(shù)據(jù)壓縮與信息論基礎(chǔ)數(shù)據(jù)壓縮與信息論基礎(chǔ)編碼器構(gòu)成編碼器構(gòu)成輸入輸入圖像圖像變變換換器器量量化化器器符符號(hào)號(hào)編編碼碼器器信信道道反反變變換

14、換器器符符號(hào)號(hào)解解碼碼器器輸出輸出圖像圖像3.2.3 信息論基礎(chǔ)信息論基礎(chǔ)3.2 數(shù)據(jù)壓縮與信息論基礎(chǔ)數(shù)據(jù)壓縮與信息論基礎(chǔ)一、圖像的信息熵：一、圖像的信息熵： 熵是信息量的度量方法熵是信息量的度量方法, ,表達(dá)一個(gè)信源平均信息表達(dá)一個(gè)信源平均信息量的大小。它表示某一事件出現(xiàn)的消息越多量的大小。它表示某一事件出現(xiàn)的消息越多, ,事件發(fā)事件發(fā)生的可能性越小生的可能性越小, ,數(shù)學(xué)上為概率越小數(shù)學(xué)上為概率越小. . 出現(xiàn)概率小的事件（符號(hào)）比出現(xiàn)概率大的事出現(xiàn)概率小的事件（符號(hào)）比出現(xiàn)概率大的事件能提供更多的信息量。件能提供更多的信息量。 設(shè)數(shù)字圖像設(shè)數(shù)字圖像X X中包含的像素的分布灰度級(jí)的集合為中

15、包含的像素的分布灰度級(jí)的集合為A=A=ai|i=1,2,m，ai在統(tǒng)計(jì)上是無關(guān)的，且在統(tǒng)計(jì)上是無關(guān)的，且ai出現(xiàn)概出現(xiàn)概率為率為p(ai), ,則定義則定義各灰度級(jí)各灰度級(jí)ai所包含信息所包含信息I(ai)為為：221()loglog()()iiiI ap ap a 如果對(duì)數(shù)字圖像如果對(duì)數(shù)字圖像X X像素分布各灰度級(jí)作平均度量，則像素分布各灰度級(jí)作平均度量，則可得平均信息量：可得平均信息量：211()(). ()().log()mmiiiiiiH Xp aI ap ap a 則稱則稱H(X)H(X)為數(shù)字圖像為數(shù)字圖像X X的熵，單位為的熵，單位為bit/bit/像素。像素?？煽闯?，圖像的熵可

16、看出，圖像的熵H是表示其各個(gè)灰度級(jí)比特?cái)?shù)的是表示其各個(gè)灰度級(jí)比特?cái)?shù)的統(tǒng)計(jì)平均值。統(tǒng)計(jì)平均值。例如：例如：有一幅有一幅4040個(gè)像素組成的灰度圖像，灰度共有個(gè)像素組成的灰度圖像，灰度共有5 5級(jí)，分級(jí)，分別用別用A A、B B、C C、D D、E E表示。表示。4040個(gè)像素中出現(xiàn)灰度個(gè)像素中出現(xiàn)灰度A A的的像素?cái)?shù)有像素?cái)?shù)有1515個(gè)；出現(xiàn)灰度個(gè)；出現(xiàn)灰度B B的像素?cái)?shù)有的像素?cái)?shù)有7 7個(gè)；出現(xiàn)灰個(gè)；出現(xiàn)灰度度C C的像素?cái)?shù)有的像素?cái)?shù)有7 7個(gè)等等，如下表所示。個(gè)等等，如下表所示。灰度等級(jí)灰度等級(jí)ABCDE像素?cái)?shù)像素?cái)?shù)157765概率概率15/407/407/406/405/40 假設(shè)每個(gè)像素

17、占假設(shè)每個(gè)像素占3 3位表示，則編碼這幅圖像位表示，則編碼這幅圖像共需共需4040 3=1203=120位。位。 求這幅圖象的熵為：求這幅圖象的熵為：222( )(15/40) log (40/15)(7/40) log (40/7)(5/40) log (40/5)2.196/H S 位 像素位 像素這就是說每個(gè)像素用這就是說每個(gè)像素用2.1962.196位表示，位表示，4040個(gè)像素需要個(gè)像素需要用用87.8487.84位。位?？煽闯?，通過求圖像的熵對(duì)圖像編碼，可起到壓縮可看出，通過求圖像的熵對(duì)圖像編碼，可起到壓縮圖像數(shù)據(jù)作用。圖像數(shù)據(jù)作用。二、無失真編碼理論二、無失真編碼理論( (可變長(zhǎng)

18、最佳編碼定理可變長(zhǎng)最佳編碼定理) ) 等長(zhǎng)編碼：對(duì)于每個(gè)符號(hào)，如經(jīng)過量化后的圖等長(zhǎng)編碼：對(duì)于每個(gè)符號(hào)，如經(jīng)過量化后的圖像數(shù)據(jù)，如果對(duì)它們每個(gè)值都是以相同長(zhǎng)度的二像數(shù)據(jù)，如果對(duì)它們每個(gè)值都是以相同長(zhǎng)度的二進(jìn)制碼表示的，稱之為等長(zhǎng)編碼或均勻編碼。進(jìn)制碼表示的，稱之為等長(zhǎng)編碼或均勻編碼?？勺冮L(zhǎng)編碼：對(duì)于每個(gè)符號(hào)，表示符號(hào)的碼字的可變長(zhǎng)編碼：對(duì)于每個(gè)符號(hào)，表示符號(hào)的碼字的長(zhǎng)度不是固定不變的，而是隨符號(hào)出現(xiàn)概率而變長(zhǎng)度不是固定不變的，而是隨符號(hào)出現(xiàn)概率而變化：化：等長(zhǎng)編碼是將所有符號(hào)當(dāng)作等概率事件處理的。等長(zhǎng)編碼是將所有符號(hào)當(dāng)作等概率事件處理的。定理定理2 2：在變字長(zhǎng)編碼中，如果碼字長(zhǎng)度嚴(yán)格按在變字長(zhǎng)

19、編碼中，如果碼字長(zhǎng)度嚴(yán)格按照對(duì)應(yīng)符號(hào)出現(xiàn)的概率大小逆序排列，則其照對(duì)應(yīng)符號(hào)出現(xiàn)的概率大小逆序排列，則其為最小。為最小。 定理定理1 1：若編碼時(shí)，對(duì)出現(xiàn)概率較大的符號(hào)用較若編碼時(shí)，對(duì)出現(xiàn)概率較大的符號(hào)用較少比特?cái)?shù)少比特?cái)?shù)( (短碼短碼) )表示，對(duì)出現(xiàn)概率較小的符號(hào)用表示，對(duì)出現(xiàn)概率較小的符號(hào)用較多比特?cái)?shù)較多比特?cái)?shù)( (長(zhǎng)碼長(zhǎng)碼) )表示，則其表示，則其要比要比等長(zhǎng)編碼時(shí)所需碼字少。等長(zhǎng)編碼時(shí)所需碼字少。在非均勻符號(hào)概率分布情況下，變長(zhǎng)編碼效率高于在非均勻符號(hào)概率分布情況下，變長(zhǎng)編碼效率高于等長(zhǎng)編碼。等長(zhǎng)編碼。三、描述圖像壓縮性能的指標(biāo)：三、描述圖像壓縮性能的指標(biāo)： 壓縮比：壓縮比：均比特?cái)?shù)均

20、比特?cái)?shù)壓縮后圖像每像素的平壓縮后圖像每像素的平均比特?cái)?shù)均比特?cái)?shù)壓縮前圖像每像素的平壓縮前圖像每像素的平 21bbc一般情況下壓縮比一般情況下壓縮比c c 1 1，c c愈大則壓縮程度愈高。愈大則壓縮程度愈高。 平均碼字長(zhǎng)度平均碼字長(zhǎng)度R：)/(1字符字符bitpRMkkk k為數(shù)字圖像第為數(shù)字圖像第k個(gè)碼字個(gè)碼字Ck的長(zhǎng)度；的長(zhǎng)度；pk為數(shù)字圖像第為數(shù)字圖像第k個(gè)碼字個(gè)碼字Ck 相應(yīng)出現(xiàn)概率。相應(yīng)出現(xiàn)概率。 編碼效率編碼效率 ：%100 RH H為原始圖像的熵；為原始圖像的熵；R是實(shí)際編碼的平均碼字長(zhǎng)度。是實(shí)際編碼的平均碼字長(zhǎng)度。 冗余度冗余度r： 1r如果編碼效率如果編碼效率100%，說明還

21、有冗余信息存在。，說明還有冗余信息存在。r 越小，說明可壓縮的余地越小。越小，說明可壓縮的余地越小。統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼是一種無損編碼，是建立在圖像的統(tǒng)計(jì)特性統(tǒng)計(jì)編碼是一種無損編碼，是建立在圖像的統(tǒng)計(jì)特性基礎(chǔ)之上的壓縮編碼?；A(chǔ)之上的壓縮編碼。信源統(tǒng)計(jì)編碼方法關(guān)鍵在于去除冗余度。信源統(tǒng)計(jì)編碼方法關(guān)鍵在于去除冗余度。統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼(無損編碼無損編碼)游程編碼游程編碼Huffman編碼編碼算術(shù)編碼算術(shù)編碼LZW字典編碼字典編碼香農(nóng)編碼香農(nóng)編碼3.3 霍夫曼編碼霍夫曼編碼(Huffman Coding) 這為這為HuffmanHuffman于于19521952年提出的一種編碼方法，是年提出的一

22、種編碼方法，是一種最佳編碼方法。所謂最佳編碼方法是指采用一種最佳編碼方法。所謂最佳編碼方法是指采用HuffmanHuffman編碼方法得到的單元像素的比特?cái)?shù)最接近圖編碼方法得到的單元像素的比特?cái)?shù)最接近圖像的實(shí)際熵值。而熵為進(jìn)行無失真編碼的理論極限。像的實(shí)際熵值。而熵為進(jìn)行無失真編碼的理論極限。 Huffman Huffman編碼是根據(jù)可變長(zhǎng)最佳編碼定理，應(yīng)用編碼是根據(jù)可變長(zhǎng)最佳編碼定理，應(yīng)用哈夫曼算法而產(chǎn)生的一種編碼方法。哈夫曼算法而產(chǎn)生的一種編碼方法。1 1、HuffmanHuffman編碼方法編碼方法 概率統(tǒng)計(jì)概率統(tǒng)計(jì)( (如對(duì)一幅圖像作灰度信號(hào)統(tǒng)計(jì)如對(duì)一幅圖像作灰度信號(hào)統(tǒng)計(jì)) )，得到，

23、得到n n個(gè)不同概率的灰度信息符號(hào)；個(gè)不同概率的灰度信息符號(hào)； 將將n n個(gè)灰度信息符號(hào)出現(xiàn)的概率由大到小排序，個(gè)灰度信息符號(hào)出現(xiàn)的概率由大到小排序，概率相同的可以任意放；概率相同的可以任意放； 將兩個(gè)最小概率相加將兩個(gè)最小概率相加( (概率個(gè)數(shù)減為概率個(gè)數(shù)減為n-1n-1個(gè)個(gè)),),形成形成新的概率集合；再按第新的概率集合；再按第步方法重排，如此重復(fù)直步方法重排，如此重復(fù)直到僅有兩個(gè)概率為止；到僅有兩個(gè)概率為止； 分配碼字。原則為從最后一步開始反向進(jìn)行，以分配碼字。原則為從最后一步開始反向進(jìn)行，以二進(jìn)制碼元二進(jìn)制碼元(0,1)(0,1)賦值，構(gòu)成賦值，構(gòu)成HuffmanHuffman碼字；碼

24、字；注意：碼字分配從最后一步開始反向進(jìn)行。對(duì)最后注意：碼字分配從最后一步開始反向進(jìn)行。對(duì)最后兩個(gè)概率一個(gè)賦予兩個(gè)概率一個(gè)賦予“0”0”碼，一個(gè)賦予碼，一個(gè)賦予“1”1”碼，這碼，這里賦予里賦予0 0和和1 1完全隨機(jī)，不影響結(jié)束。完全隨機(jī)，不影響結(jié)束。 2 2、舉例、舉例1 1：設(shè)有一圖像序列，含設(shè)有一圖像序列，含8 8個(gè)灰度級(jí)個(gè)灰度級(jí)x1 1，x2 2，, ,x8 8，概率，概率分別為：分別為：P P1 1=0.04=0.04，P P2 2=0.06=0.06，P P3 3=0.10=0.10，P P4 4=0.10=0.10，P P5 5=0.07=0.07，P P6 6=0.18=0.1

25、8，P P7 7=0.05=0.05，P P8 8=0.40=0.40。試進(jìn)行試進(jìn)行HuffmanHuffman編碼，并計(jì)算編碼效率、壓縮比及編碼，并計(jì)算編碼效率、壓縮比及冗余度。冗余度。符號(hào)符號(hào) 概率概率p8 0.40p6 0.18p3 0.10p4 0.10p5 0.07p2 0.06p7 0.05p1 0.040.400.180.100.100.070.090.060.400.180.130.100.100.090.400.180.190.130.100.400.230.190.180.400.370.230.600.4010111111000000 統(tǒng)一：概率大的賦予碼統(tǒng)一：概率大的賦

26、予碼字為字為“0”，概率小的賦，概率小的賦予碼字為予碼字為“1”。分配碼字分配碼字x1x2x3x4x5x6x7x8碼長(zhǎng)碼長(zhǎng)0001101010110000010000100010154344351則有：則有：則其平均碼字長(zhǎng)度為：則其平均碼字長(zhǎng)度為：字符字符比特比特/61. 2504. 0505. 0406. 0407. 041 . 031 . 0318. 014 . 081 kkkpR 則其熵為：則其熵為：字符字符比特比特/55. 2log812 kkkppH則其編碼效率為：則其編碼效率為：%8 .97%10061. 255. 2%100 RH 則其冗余度為：則其冗余度為：%2 . 2978.

27、 011 r如果壓縮前如果壓縮前8個(gè)符號(hào)需要個(gè)符號(hào)需要3個(gè)比特量化，經(jīng)壓縮后平個(gè)比特量化，經(jīng)壓縮后平均碼字長(zhǎng)度為均碼字長(zhǎng)度為2.61，則壓縮比為：，則壓縮比為：15. 161. 23 C3. 討論：試對(duì)圖像字符序列討論：試對(duì)圖像字符序列 aaaa bbb cc d eeeee fffffff 進(jìn)行進(jìn)行Huffman編碼。編碼。解：對(duì)該圖像字符序列中不同字符進(jìn)行概率統(tǒng)解：對(duì)該圖像字符序列中不同字符進(jìn)行概率統(tǒng) 計(jì)，有：計(jì)，有： P(a)=4/22 P(b)=3/22 P(c)=2/22 P(d)=1/22 P(e)=5/22 P(f)=7/22則進(jìn)行則進(jìn)行Huffman編碼過程為：編碼過程為： 統(tǒng)

28、一：概率大的賦予碼字為統(tǒng)一：概率大的賦予碼字為“1”，概率小，概率小的賦予碼字為的賦予碼字為“0”。則賦予碼字時(shí)得：則賦予碼字時(shí)得：a=00 b=100 c=1011 a=00 b=100 c=1011 d=1010 e=01 f=11d=1010 e=01 f=11（或第（或第2 2種答案：種答案：a=00 b=101 c=1001 a=00 b=101 c=1001 d=1000 e=01 f=11 d=1000 e=01 f=11 ）4 4、HuffmanHuffman編碼在圖像壓縮中的實(shí)現(xiàn)編碼在圖像壓縮中的實(shí)現(xiàn) 我們知道，對(duì)一幅圖像進(jìn)行編碼時(shí)，如果圖我們知道，對(duì)一幅圖像進(jìn)行編碼時(shí)，如果

29、圖像的大小大于像的大小大于256256時(shí)，這幅圖像的不同的碼字就有時(shí)，這幅圖像的不同的碼字就有可能是很大，例如極限為可能是很大，例如極限為256256個(gè)不同的碼字。個(gè)不同的碼字。 對(duì)整幅圖直接進(jìn)行對(duì)整幅圖直接進(jìn)行HuffmanHuffman編碼時(shí)，小分布的編碼時(shí)，小分布的灰度值，就有可能具有很長(zhǎng)的編碼?；叶戎担陀锌赡芫哂泻荛L(zhǎng)的編碼。 如：如：100100位以上，這樣不但達(dá)不到壓縮的效果位以上，這樣不但達(dá)不到壓縮的效果反而會(huì)使數(shù)據(jù)量加大，應(yīng)該如何處理？反而會(huì)使數(shù)據(jù)量加大，應(yīng)該如何處理？ 常用的且有效的方法是：常用的且有效的方法是： 將圖像分割成若干的小塊，對(duì)每塊進(jìn)將圖像分割成若干的小塊，對(duì)每塊

30、進(jìn)行獨(dú)立的行獨(dú)立的HuffmanHuffman編碼。例如：分成編碼。例如：分成 的子塊，就可以大大降低不同灰度值的的子塊，就可以大大降低不同灰度值的個(gè)數(shù)（最多是個(gè)數(shù)（最多是6464而不是而不是256256）。）。3.4 香農(nóng)編碼香農(nóng)編碼是一種可變長(zhǎng)編碼，碼字長(zhǎng)度由符號(hào)出現(xiàn)概率決定。是一種可變長(zhǎng)編碼，碼字長(zhǎng)度由符號(hào)出現(xiàn)概率決定。1 1、基本原理、基本原理( (求可變長(zhǎng)度最佳編碼的平均碼字長(zhǎng)度求可變長(zhǎng)度最佳編碼的平均碼字長(zhǎng)度) )設(shè)進(jìn)行可變長(zhǎng)度最佳編碼時(shí)，被編碼的信息符號(hào)總設(shè)進(jìn)行可變長(zhǎng)度最佳編碼時(shí)，被編碼的信息符號(hào)總數(shù)為數(shù)為N，所用碼元進(jìn)制為，所用碼元進(jìn)制為D，第，第i個(gè)符號(hào)出現(xiàn)的概率個(gè)符號(hào)出現(xiàn)的

31、概率為為Pi，與其對(duì)應(yīng)碼字長(zhǎng)度為，與其對(duì)應(yīng)碼字長(zhǎng)度為ti，則可證明這種編碼結(jié)，則可證明這種編碼結(jié)果的平均碼字長(zhǎng)度果的平均碼字長(zhǎng)度R落在下列區(qū)間內(nèi)：落在下列區(qū)間內(nèi)：1loglog DHRDH式中式中H為信息熵。為信息熵。iNiiPPHlog1 由此可引導(dǎo)出對(duì)某一個(gè)信息符號(hào)由此可引導(dǎo)出對(duì)某一個(gè)信息符號(hào)( (碼字碼字) )的長(zhǎng)度存在的長(zhǎng)度存在如下關(guān)系式：如下關(guān)系式：loglog1(1)loglogiiiPPtDD 對(duì)二進(jìn)制進(jìn)一步簡(jiǎn)化為：對(duì)二進(jìn)制進(jìn)一步簡(jiǎn)化為：22loglog1(2)iiPtP 可見，碼字長(zhǎng)度可見，碼字長(zhǎng)度ti是根據(jù)信息符號(hào)出現(xiàn)概率是根據(jù)信息符號(hào)出現(xiàn)概率Pi決定決定的。的。2 2、香農(nóng)

32、編碼步驟：、香農(nóng)編碼步驟：(1)(1) 將輸入圖像灰度級(jí)（信息符號(hào)）按出現(xiàn)概率由將輸入圖像灰度級(jí)（信息符號(hào)）按出現(xiàn)概率由大到小順序排列大到小順序排列( (相等者可任意顛倒排列位置相等者可任意顛倒排列位置) )。(2)(2) 按式子按式子(1)(1)或式子或式子(2)(2)計(jì)算各概率對(duì)應(yīng)的碼字長(zhǎng)計(jì)算各概率對(duì)應(yīng)的碼字長(zhǎng) 度度ti 。(3)(3) 計(jì)算各概率對(duì)應(yīng)的累加概率計(jì)算各概率對(duì)應(yīng)的累加概率ai ：12132221433321111210iiiiiaaPaPaPPaPaPPPaPaPPP (4) (4) 把各個(gè)累加概率由十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小把各個(gè)累加概率由十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)，保留最高

33、的數(shù)，保留最高的t ti i位，去掉小數(shù)點(diǎn)，即獲得各個(gè)與累位，去掉小數(shù)點(diǎn)，即獲得各個(gè)與累加概率相對(duì)應(yīng)的信息符號(hào)的碼字。加概率相對(duì)應(yīng)的信息符號(hào)的碼字。3 3、舉例、舉例1 1：仍采用上面仍采用上面HuffmanHuffman例子進(jìn)行香農(nóng)編碼：例子進(jìn)行香農(nóng)編碼：設(shè)有一圖像序列，含設(shè)有一圖像序列，含8 8個(gè)灰度級(jí)個(gè)灰度級(jí)x1 1，x2 2，, ,x8 8，概，概率分別為：率分別為：P P1 1=0.04=0.04，P P2 2=0.06=0.06，P P3 3=0.10=0.10，P P4 4=0.10=0.10，P P5 5=0.07=0.07，P P6 6=0.18=0.18，P P7 7=0.

34、05=0.05，P P8 8=0.40=0.40。試進(jìn)行試進(jìn)行香農(nóng)編碼香農(nóng)編碼，計(jì)算平均碼字長(zhǎng)度和編碼效率。，計(jì)算平均碼字長(zhǎng)度和編碼效率。解：解：計(jì)算計(jì)算ti：22loglog1iiPtP 由公式得：由公式得：當(dāng)當(dāng)P P1 1=0.04=0.04，有：，有：4.645.64itti =5104. 0log04. 0log22 it依次類推，得：依次類推，得：符號(hào)符號(hào) 概率概率x8 0.40 2 0 0 00 x6 0.18 3 0.40 01100 011x3 0.10 4 0.58 10010 1001x4 0.10 4 0.68 10100 1010 x5 0.07 4 0.78 1100

35、0 1100 x2 0.06 5 0.85 1101100 11011x7 0.05 5 0.91 1110100 11101x1 0.04 5 0.96 1111010 11110計(jì)算計(jì)算ti計(jì)算計(jì)算ai十變二十變二 進(jìn)制進(jìn)制去掉多余去掉多余ti尾數(shù)尾數(shù)(碼字碼字)則其平均碼字長(zhǎng)度為：則其平均碼字長(zhǎng)度為：810.420.1830.10 420.0740.06 50.05 50.04 53.17/i iiRPt 比特 字符比特 字符則其熵為：則其熵為：字符字符比特比特/55. 2log812 kkkppH則其編碼效率為：則其編碼效率為：2.55100%100%80.4%3.17HR 可見，香農(nóng)

36、編碼要比可見，香農(nóng)編碼要比Huffman編碼的編碼效率略低一編碼的編碼效率略低一些。些。3.5 行程長(zhǎng)度編碼（游程編碼）行程長(zhǎng)度編碼（游程編碼）行程編碼又稱行程長(zhǎng)度編碼（行程編碼又稱行程長(zhǎng)度編碼（Run Length Encoding， RLE），）， 是一種熵編碼。是一種熵編碼。行程：行程：對(duì)于圖像編碼，可定義沿特定方向上具有相對(duì)于圖像編碼，可定義沿特定方向上具有相同灰度值的相鄰像元為一輪，其延續(xù)長(zhǎng)度稱之為延同灰度值的相鄰像元為一輪，其延續(xù)長(zhǎng)度稱之為延續(xù)的行程，簡(jiǎn)稱為續(xù)的行程，簡(jiǎn)稱為“行程行程”。基本原理基本原理：將具有相同灰度值的連續(xù)串用其串長(zhǎng)：將具有相同灰度值的連續(xù)串用其串長(zhǎng)（行程長(zhǎng)度）

37、和一個(gè)代表灰度值來代替。將（行程長(zhǎng)度）和一個(gè)代表灰度值來代替。將行程長(zhǎng)行程長(zhǎng)度和代表灰度值組合在一起構(gòu)成行程對(duì)度和代表灰度值組合在一起構(gòu)成行程對(duì)，作為輸入作為輸入的碼元進(jìn)行編碼的碼元進(jìn)行編碼。 在二值圖像中，每一掃描行總由若干段連著的黑像素在二值圖像中，每一掃描行總由若干段連著的黑像素（灰度值為（灰度值為0）和連著的白像素（灰度值為）和連著的白像素（灰度值為1）組成，）組成，它們分別稱為它們分別稱為“”和和“”，且交替出現(xiàn)，且交替出現(xiàn) (全白或全黑掃描行除外全白或全黑掃描行除外)。對(duì)于不同的行程長(zhǎng)度根據(jù)。對(duì)于不同的行程長(zhǎng)度根據(jù)其概率分布分配相應(yīng)的碼字，可以得到較好的壓縮。其概率分布分配相應(yīng)的碼

38、字，可以得到較好的壓縮。例如有一掃描線自左向右線段組成如下所示：例如有一掃描線自左向右線段組成如下所示：線段序號(hào)線段序號(hào) 線段性質(zhì)線段性質(zhì) 線段組成線段組成 線段長(zhǎng)度線段長(zhǎng)度 1 白游程白游程 000 3 2 黑游程黑游程 111 3 3 白游程白游程 00000 5 4 黑游程黑游程 1111 4 5 白游程白游程 00000 5則游程長(zhǎng)度進(jìn)行統(tǒng)計(jì)為：則游程長(zhǎng)度進(jìn)行統(tǒng)計(jì)為：3個(gè)個(gè)0，3個(gè)個(gè)1，5個(gè)個(gè)0，4個(gè)個(gè)0，5個(gè)個(gè)1(含義為含義為3個(gè)個(gè)白白，3個(gè)黑，個(gè)黑，5個(gè)白，個(gè)白，4個(gè)黑，個(gè)黑，5個(gè)白個(gè)白)。游程長(zhǎng)度編碼的信息符號(hào)集由長(zhǎng)度為游程長(zhǎng)度編碼的信息符號(hào)集由長(zhǎng)度為1,2,N等各種等各種游程長(zhǎng)

39、度組成。這里游程長(zhǎng)度組成。這里N是一條掃描線上的像素總數(shù)。是一條掃描線上的像素總數(shù)。例如，有一字符串例如，有一字符串“aabbbcddddd”， 則經(jīng)行程長(zhǎng)度則經(jīng)行程長(zhǎng)度編碼后，編碼后， 該字符串可以只用該字符串可以只用“2a3b1c5d”來表示。來表示。 aa bbb c ddddd (共11*8=88 bits) 2a3b1c5d (共8*8=64 bits)1. 1. 一維行程編碼一維行程編碼例如：圖像中某行灰度值例如：圖像中某行灰度值40，40，40，40，40，232，232，232，232，232，0，0，0，0，0，0，0，0，93，93，93，93，56，93，93，93，93

40、，93序號(hào)序號(hào)灰度值灰度值行程長(zhǎng)度行程長(zhǎng)度灰度行程對(duì)灰度行程對(duì)1405（5，40）22325（5，232）308（8，0）4934（4，90）5561（1，56）6935（5，93）總數(shù)據(jù)量為：總數(shù)據(jù)量為：288=224 bit則得到行程編碼的碼流為：則得到行程編碼的碼流為：5，40，5，232，8，0，4，93，1，56，5，93規(guī)則：行程長(zhǎng)度編碼用規(guī)則：行程長(zhǎng)度編碼用3位二進(jìn)制數(shù)位二進(jìn)制數(shù) 灰度值用灰度值用8位二進(jìn)制數(shù)位二進(jìn)制數(shù)8=7+15，40，5，232，7，0， 1，0， 4，93，1，56，5，93行程編碼所需用的比特位數(shù)為：行程編碼所需用的比特位數(shù)為：73+ 78=77 bit壓

41、縮率為：壓縮率為：%375.3422477 2. 2. 二維行程編碼二維行程編碼關(guān)鍵是進(jìn)行二維排序，使像素之間關(guān)系變成一維的鄰關(guān)鍵是進(jìn)行二維排序，使像素之間關(guān)系變成一維的鄰接關(guān)系接關(guān)系此排序方法主要用于此排序方法主要用于DCT系數(shù)的壓縮編碼。系數(shù)的壓縮編碼。 13113113012612812812512713213312912712912912612513213212812712812712812713013112913112912712812712912913013012913013012913013013213212913013013013013013313412913013013013

42、0129133134129130130130f對(duì)以下二維圖象進(jìn)行行程長(zhǎng)度編碼對(duì)以下二維圖象進(jìn)行行程長(zhǎng)度編碼原圖象數(shù)據(jù)大小為：原圖象數(shù)據(jù)大小為：648=512bit行程長(zhǎng)度編碼圖象數(shù)據(jù)大小為：行程長(zhǎng)度編碼圖象數(shù)據(jù)大小為：341+841=451bit 游程長(zhǎng)度編碼本質(zhì)上說就是計(jì)算圖像信號(hào)出現(xiàn)行程游程長(zhǎng)度編碼本質(zhì)上說就是計(jì)算圖像信號(hào)出現(xiàn)行程長(zhǎng)度，然后將行程長(zhǎng)度轉(zhuǎn)換為代碼。長(zhǎng)度，然后將行程長(zhǎng)度轉(zhuǎn)換為代碼。如果不區(qū)分黑、白游程進(jìn)行統(tǒng)一游程長(zhǎng)度編碼，并如果不區(qū)分黑、白游程進(jìn)行統(tǒng)一游程長(zhǎng)度編碼，并設(shè)設(shè)Pi為長(zhǎng)度為為長(zhǎng)度為i的游長(zhǎng)的概率。則：的游長(zhǎng)的概率。則：iiiPPH 2log.游長(zhǎng)的熵游長(zhǎng)的熵H平均游長(zhǎng)

43、平均游長(zhǎng)L iiPiL 游程長(zhǎng)度的熵游程長(zhǎng)度的熵(即平均每個(gè)像素的熵即平均每個(gè)像素的熵)LHh/ 當(dāng)根據(jù)各游長(zhǎng)的概率，利用當(dāng)根據(jù)各游長(zhǎng)的概率，利用Huffman編碼時(shí)，則每編碼時(shí)，則每個(gè)游程的平均碼長(zhǎng)個(gè)游程的平均碼長(zhǎng) 滿足下列不等式：滿足下列不等式：N1 HNH若不等式兩邊同除以平均游長(zhǎng)若不等式兩邊同除以平均游長(zhǎng)L，可得每個(gè)像素的，可得每個(gè)像素的平均碼長(zhǎng)平均碼長(zhǎng)n的估值：的估值：Lhnh/1 則每個(gè)像素的熵則每個(gè)像素的熵h即為游長(zhǎng)編碼可達(dá)到的最小比特即為游長(zhǎng)編碼可達(dá)到的最小比特率的估值。率的估值。3.6 算術(shù)編碼算術(shù)編碼為了解決計(jì)算機(jī)中必須以整數(shù)位進(jìn)行編碼問題，提為了解決計(jì)算機(jī)中必須以整數(shù)位進(jìn)

44、行編碼問題，提出算術(shù)編碼方法。出算術(shù)編碼方法。1 1、基本原理、基本原理假設(shè)一個(gè)信源的概率模型。根據(jù)該信源的概率模型，假設(shè)一個(gè)信源的概率模型。根據(jù)該信源的概率模型，一般把一個(gè)信源集合表示為實(shí)數(shù)線上的一般把一個(gè)信源集合表示為實(shí)數(shù)線上的0至至1間的一個(gè)間的一個(gè)區(qū)間。這集合中每個(gè)元素用來縮短這個(gè)區(qū)間。信源集區(qū)間。這集合中每個(gè)元素用來縮短這個(gè)區(qū)間。信源集合的元素越多合的元素越多,信息越長(zhǎng)信息越長(zhǎng),編碼表示所得區(qū)間間隔越小編碼表示所得區(qū)間間隔越小,表示這一間隔所需二進(jìn)制位就越多表示這一間隔所需二進(jìn)制位就越多,碼字越長(zhǎng)。這就碼字越長(zhǎng)。這就是是區(qū)間作為代碼區(qū)間作為代碼的原理。的原理。 2 2、編碼方法：、編

45、碼方法：( (舉例講解）舉例講解）設(shè)圖像信源編碼用設(shè)圖像信源編碼用a，b，c，d 4個(gè)符號(hào)表示，符號(hào)個(gè)符號(hào)表示，符號(hào)a，b，c，d分別出現(xiàn)概率為：分別出現(xiàn)概率為： P(a)=0.4，P(b)=0.2 ,P(c)=0.2, P(d)=0.2假設(shè)各數(shù)據(jù)符號(hào)在假設(shè)各數(shù)據(jù)符號(hào)在0,1 內(nèi)賦值范圍設(shè)定內(nèi)賦值范圍設(shè)定:試對(duì)源數(shù)據(jù)集試對(duì)源數(shù)據(jù)集dacab進(jìn)行算術(shù)編碼。進(jìn)行算術(shù)編碼。a=0,0.4，b =0.4,0.6，c=0.6,0.8，d=0.8,1.0解：解：給出一組關(guān)系式為：給出一組關(guān)系式為： StartN = StartB + LeftC L EndN = StartB + RightC L 式中式

46、中StartN 為新子區(qū)間的起始位置；為新子區(qū)間的起始位置； EndN 為新子區(qū)間的結(jié)束位置；為新子區(qū)間的結(jié)束位置； StartB 為前子區(qū)間的起始位置；為前子區(qū)間的起始位置； LeftC 為當(dāng)前符號(hào)的區(qū)間左端；為當(dāng)前符號(hào)的區(qū)間左端； RightC 為當(dāng)前符號(hào)的區(qū)間右端；為當(dāng)前符號(hào)的區(qū)間右端； L 為前子區(qū)間長(zhǎng)度。為前子區(qū)間長(zhǎng)度。 第一個(gè)被壓縮符號(hào)為第一個(gè)被壓縮符號(hào)為“d”，則前符號(hào)區(qū)間為則前符號(hào)區(qū)間為0,1 ，而，而d為為0.8，1.0 StartN=0+0.8 1=0.8 EndN=0+1.0 1=1.0 代碼代碼“d”編碼區(qū)間為編碼區(qū)間為0.8,1.0 ，寬度為，寬度為0.2第二個(gè)被壓縮

47、符號(hào)為第二個(gè)被壓縮符號(hào)為“a”，前符號(hào)區(qū)間為前符號(hào)區(qū)間為0.8，1.0 ， “a”為為0，0.4)，則，則“a” 取取值范圍應(yīng)在前符號(hào)區(qū)間值范圍應(yīng)在前符號(hào)區(qū)間0.8，1.0 的范圍之內(nèi)，則：的范圍之內(nèi)，則： StartN=0.8+0 0.2=0.8 EndN=0.8+0.4 0.2=0.88 代碼代碼“a”編碼區(qū)間為編碼區(qū)間為0.8，0.88 ，寬度為，寬度為0.08 第三個(gè)被壓縮符號(hào)為第三個(gè)被壓縮符號(hào)為“c”， 前符號(hào)區(qū)間前符號(hào)區(qū)間0.8，0.88) ，c為為0.6，0.8) StartN = 0.8 + 0.6 0.08=0.848 EndN = 0.8 + 0.8 0.08=0.864

48、“c” 實(shí)際編碼區(qū)間為實(shí)際編碼區(qū)間為0.848，0. 864 ，寬度為，寬度為0.016 第四個(gè)被壓縮符號(hào)為第四個(gè)被壓縮符號(hào)為“a”， 前符號(hào)區(qū)間前符號(hào)區(qū)間0.848，0. 864) ，a為為0，0.4) StartN= 0.848 + 0 0.016=0.848 EndN = 0.848 + 0.4 0.016=0.8544 “a” 實(shí)際編碼區(qū)間為實(shí)際編碼區(qū)間為0.848，0. 8544 ，寬度為，寬度為0.0064第五個(gè)被壓縮符號(hào)為第五個(gè)被壓縮符號(hào)為“b”， 前符號(hào)區(qū)間前符號(hào)區(qū)間0.848，0. 8544) ，b為為0.4，0.6) StartN= 0.848 + 0.4 0.0064=0

49、.85056 EndN = 0.848 + 0.6 0.0064=0.85184 “b” 實(shí)際編碼區(qū)間為實(shí)際編碼區(qū)間為0.85056，0. 85184 至此，數(shù)據(jù)串至此，數(shù)據(jù)串dacab已經(jīng)被描述成一個(gè)編碼實(shí)數(shù)區(qū)已經(jīng)被描述成一個(gè)編碼實(shí)數(shù)區(qū)間為間為0.85056，0.85184 。或者說在此區(qū)間內(nèi)任一實(shí)數(shù)?；蛘哒f在此區(qū)間內(nèi)任一實(shí)數(shù)值都唯一對(duì)應(yīng)該數(shù)據(jù)序列。值都唯一對(duì)應(yīng)該數(shù)據(jù)序列。把該十進(jìn)制實(shí)數(shù)區(qū)間用二進(jìn)制表示為：把該十進(jìn)制實(shí)數(shù)區(qū)間用二進(jìn)制表示為： 0.1101100110110.110110011011，0. 1101101000010. 110110100001 。把該十進(jìn)制實(shí)數(shù)區(qū)間用二進(jìn)制表示

50、為：把該十進(jìn)制實(shí)數(shù)區(qū)間用二進(jìn)制表示為： 0.110110011011，0. 110110100001 。但從這個(gè)區(qū)間可以看出，但從這個(gè)區(qū)間可以看出，0. 1101101位于這個(gè)區(qū)間內(nèi)位于這個(gè)區(qū)間內(nèi)并且其編碼最短，故把其作為數(shù)據(jù)序列并且其編碼最短，故把其作為數(shù)據(jù)序列dacab的編的編碼輸出碼輸出?？紤]到算術(shù)編碼中任一數(shù)據(jù)序列的編碼都。考慮到算術(shù)編碼中任一數(shù)據(jù)序列的編碼都含有含有“0.”，所以編碼時(shí)可以不考慮，所以編碼時(shí)可以不考慮“0.”。最后所得的碼點(diǎn)值最后所得的碼點(diǎn)值“1101101”(忽視小數(shù)點(diǎn)忽視小數(shù)點(diǎn))就是對(duì)就是對(duì)dacab進(jìn)行算術(shù)編碼的結(jié)果。進(jìn)行算術(shù)編碼的結(jié)果。所以所以“dacab”的

51、編碼區(qū)間為的編碼區(qū)間為0.85056，0.85184“dacab”的編碼值為的編碼值為1101101信源熵為信源熵為：字符字符比特比特/92. 1)32 . 0log2 . 04 . 0log4 . 0(log22812 kkkppH平均碼長(zhǎng)：平均碼長(zhǎng)：字符字符比特比特/25/105/)85056. 085184. 0(log(2 ceitL編碼效率：編碼效率：%96292. 1 LH 3.7 LZW編碼編碼LZW編碼又稱字串表編碼，編碼又稱字串表編碼， 屬于無損編碼。屬于無損編碼。l 基本思想基本思想: : 在編碼過程中，將所遇到的字符串建立一個(gè)字符在編碼過程中，將所遇到的字符串建立一個(gè)字符

52、串表，表中的每個(gè)字符串都對(duì)應(yīng)一個(gè)索引，編碼時(shí)串表，表中的每個(gè)字符串都對(duì)應(yīng)一個(gè)索引，編碼時(shí)用該字符串在字串表中的索引來代替原始的數(shù)據(jù)串。用該字符串在字串表中的索引來代替原始的數(shù)據(jù)串。 字符串表是在壓縮過程中動(dòng)態(tài)生成的，不必將字符串表是在壓縮過程中動(dòng)態(tài)生成的，不必將它保存在壓縮文件里，因?yàn)榻鈮嚎s時(shí)字符串表可以它保存在壓縮文件里，因?yàn)榻鈮嚎s時(shí)字符串表可以由壓縮文件中的信息重新生成。由壓縮文件中的信息重新生成。 l 編碼方法編碼方法( (舉例講解舉例講解) ) 設(shè)有一來源于設(shè)有一來源于4色（以色（以a、b、c、d表示）圖像的表示）圖像的數(shù)據(jù)流數(shù)據(jù)流aabcabbbbd，現(xiàn)對(duì)其進(jìn)行，現(xiàn)對(duì)其進(jìn)行LZW編碼

53、。編碼過編碼。編碼過程如下：程如下： 設(shè)設(shè)S1、S2為兩個(gè)存放字符串的臨時(shí)變量。為兩個(gè)存放字符串的臨時(shí)變量。 LZW_CLEAR為字符表初始化標(biāo)志。為字符表初始化標(biāo)志。 LZW_EOI為字符表編碼結(jié)束標(biāo)志。為字符表編碼結(jié)束標(biāo)志。 根據(jù)圖像中使用顏色數(shù)初始化一個(gè)字串表，每個(gè)根據(jù)圖像中使用顏色數(shù)初始化一個(gè)字串表，每個(gè)顏色對(duì)應(yīng)字串表中一個(gè)索引。顏色對(duì)應(yīng)字串表中一個(gè)索引。由于圖像中只有四種顏色，僅用由于圖像中只有四種顏色，僅用4比特表示字符串表比特表示字符串表中每個(gè)字符串索引。建立初始化字符串表如下所示。中每個(gè)字符串索引。建立初始化字符串表如下所示。字符串字符串索引索引a0Hb1Hc2Hd3HLZW_

54、CLEAR4HLZW_EOI5H表中前四項(xiàng)代表表中前四項(xiàng)代表4 4種顏色，種顏色， 后兩項(xiàng)分別表示初始化和圖像后兩項(xiàng)分別表示初始化和圖像結(jié)束標(biāo)志。結(jié)束標(biāo)志。把把S1和和S2初始化為空（即初始化為空（即NULL），輸出），輸出LZW_CLEAR的在字符串表中的索引值的在字符串表中的索引值4H， 接下來是對(duì)圖像數(shù)據(jù)的編碼。接下來是對(duì)圖像數(shù)據(jù)的編碼。 從圖像數(shù)據(jù)流的第一個(gè)字符開始，每次讀取一個(gè)從圖像數(shù)據(jù)流的第一個(gè)字符開始，每次讀取一個(gè)字符，將其賦給字符串變量字符，將其賦給字符串變量S2。則則讀取的圖像數(shù)據(jù)流的第一個(gè)字符為讀取的圖像數(shù)據(jù)流的第一個(gè)字符為“a”a”，賦給，賦給S2S2。 判斷判斷“S1

55、+S2”是否存在于字符串表中，如果字符是否存在于字符串表中，如果字符串表中存在串表中存在“S1 +S2”，則，則S1 = S1 +S2 ，不輸出任何，不輸出任何結(jié)果結(jié)果 ；否則，輸出；否則，輸出S1在字符串表中索引，并且在字在字符串表中索引，并且在字符串表末尾為符串表末尾為“S1 +S2”添加索引，同時(shí)添加索引，同時(shí)S1 =S2。讀取第一個(gè)字符為讀取第一個(gè)字符為“a”a”賦給賦給S2S2，則有，則有S1 +S2= “a”S1 +S2= “a”。而而“a”a”存在于字符串表中，對(duì)應(yīng)索引值為存在于字符串表中，對(duì)應(yīng)索引值為0H0H，則不，則不輸出任何結(jié)果，只使輸出任何結(jié)果，只使S1 = S1 +S2

56、。 接著讀入下一個(gè)字符接著讀入下一個(gè)字符“a”a”賦給賦給S2S2， 因因S1+S2=“aaS1+S2=“aa”不存在于字串表中，不存在于字串表中， 所以對(duì)應(yīng)輸出所以對(duì)應(yīng)輸出結(jié)果為輸出結(jié)果為輸出S1=“a”S1=“a”的索引的索引0H0H，同時(shí)在字符串表末，同時(shí)在字符串表末尾添加新字符串尾添加新字符串“aaaa”的索引的索引6H6H， 并使并使S1=S2=“a”S1=S2=“a”。 接著讀入第三個(gè)字符接著讀入第三個(gè)字符“b”b”賦給賦給S2 ,S2 ,因因S1+S2=“abS1+S2=“ab”不存在于字串表中，所以對(duì)應(yīng)輸出結(jié)不存在于字串表中，所以對(duì)應(yīng)輸出結(jié)果為輸出果為輸出S1=“a”S1=“a

57、”的索引的索引0H0H，同時(shí)在字符串表末尾，同時(shí)在字符串表末尾添加新字符串添加新字符串“abab”的索引的索引7H7H，并使，并使S1=S2=“b”S1=S2=“b”。 依次讀取數(shù)據(jù)流中的每個(gè)字符，如果依次讀取數(shù)據(jù)流中的每個(gè)字符，如果S1+S2S1+S2沒有出現(xiàn)沒有出現(xiàn)在字符串表中，則輸出在字符串表中，則輸出S1S1中的字符串的索引作為輸中的字符串的索引作為輸出結(jié)果，并在字符串表末尾為新字符串出結(jié)果，并在字符串表末尾為新字符串S1+S2S1+S2添加索添加索引，并使引，并使S1=S2S1=S2； 否則，不輸出任何結(jié)果，只是使否則，不輸出任何結(jié)果，只是使S1=S1+S2S1=S1+S2。最終，直到所有字符讀完為止。最終，直到所有字符讀完為止。所有字符處理完畢后，輸出所有字符處理完畢后，輸出S1S1中的字符串的索引，中的字符串的索引，最后輸出結(jié)束標(biāo)志最后輸出結(jié)束標(biāo)志LZW_EOILZW_EOI的索引。的索引。至此，編碼完畢，至此，編碼完畢，圖像數(shù)據(jù)流圖像數(shù)據(jù)流aabcabbbbd完整編碼過程如下表：完整編碼過程如下表：輸入數(shù)據(jù)輸入數(shù)據(jù)S2S2S1+S2