第三章圖像壓縮編碼

第三章

圖像壓縮編碼中國(guó)礦業(yè)大學(xué)信電學(xué)院主要內(nèi)容

3.1圖像編碼理論分類(lèi)

3.2數(shù)據(jù)壓縮與信息論基礎(chǔ)

3.3霍夫曼編碼

3.4游程長(zhǎng)度編碼

3.5算術(shù)編碼

3.6LZW字典編碼

3.1圖像壓縮編碼分類(lèi)一般從信息論角度出發(fā)分為兩大類(lèi)：冗余度壓縮方法信息量壓縮方法1、冗余度壓縮方法：也稱(chēng)無(wú)損壓縮，信息保持編碼或熵編碼。具體講為解碼圖像和壓縮編碼前圖像嚴(yán)格相同，沒(méi)有失真。冗余度壓縮方法的核心是基于統(tǒng)計(jì)模型，減少或完全去除源數(shù)據(jù)流中的冗余，同時(shí)保持信息不變?？蓪?shí)現(xiàn)編碼與解碼互逆。(第3章壓縮方法)2、信息量壓縮方法：也稱(chēng)有損壓縮，失真度編碼或熵壓縮編碼。即解碼圖像和原始圖像是有差別的，允許有一定失真。信息量壓縮方法是以犧牲部分信息量為代價(jià)而換取縮短平均碼長(zhǎng)的編碼壓縮方法。由于在壓縮過(guò)程中在允許前提下丟失一部分信息，所以圖像還原后與壓縮前不會(huì)完全一致。(第4、5章壓縮方法)信息量壓縮方法不能實(shí)現(xiàn)編碼與解碼互逆。壓縮編碼分類(lèi)統(tǒng)計(jì)編碼(無(wú)損編碼)有損編碼游程編碼Huffman編碼算術(shù)編碼主要分兩大類(lèi)LZW字典編碼預(yù)測(cè)編碼變換編碼DFTDCTK-L變換香農(nóng)編碼一、圖像編碼技術(shù)的必要性：1.信息傳輸方式發(fā)生了很大的改變

通信方式的改變

文字+語(yǔ)音圖像+文字+語(yǔ)音

通信對(duì)象的改變

人與人人與機(jī)器，機(jī)器與機(jī)器要求圖像的保真度和傳輸?shù)膶?shí)時(shí)性。3.2.1數(shù)據(jù)壓縮與數(shù)據(jù)冗余3.2數(shù)據(jù)壓縮與信息論基礎(chǔ)

2.圖像傳輸與存儲(chǔ)需要的信息量空間：

如一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512512像素，每像素的R、G、B三分量分別占8bit，則總比特?cái)?shù)為90602435125128bit=97,200M。如一張CD光盤(pán)可存600兆字節(jié)數(shù)據(jù)，這部電影光圖像（還有聲音）就需要160張CD光盤(pán)用來(lái)存儲(chǔ)。

因此，傳輸帶寬、速度、存儲(chǔ)器容量的限制使得對(duì)圖象數(shù)據(jù)進(jìn)行壓縮顯得非常必要。二、圖像編碼技術(shù)的可能性：1、從信息論觀點(diǎn)來(lái)看，圖像作為一信源，描述圖像信源數(shù)據(jù)是有效信息量和冗余量?jī)刹糠纸M成。去除冗余量可節(jié)省存儲(chǔ)和傳輸中的開(kāi)銷(xiāo)，同時(shí)不損害圖像信源中有效信息量。如果不同的方法表示給定量的信息用了不同的數(shù)據(jù)量，那么使用較多數(shù)據(jù)量的方法中，有些數(shù)據(jù)必然代表無(wú)用的信息，或者為重復(fù)地表示了其它數(shù)據(jù)已表示的信息，這為數(shù)據(jù)冗余的概念。什么是數(shù)據(jù)冗余呢？一幅圖像中像素灰度出現(xiàn)的不均勻性。如果用同

樣長(zhǎng)度比特表示每一個(gè)灰度，則必然存在冗余。圖像能量在變換域內(nèi)分布的不均勻性，大部分能

量集中在低頻部分，而小部分能量集中在高和較

高的頻率部分。則高頻能量為數(shù)據(jù)冗余。圖像像素在時(shí)間和空間上的相關(guān)性造成信息冗余。空間冗余：鄰近像素灰度分布的相關(guān)性很強(qiáng)。頻間冗余：多譜段圖像中各譜段圖像對(duì)應(yīng)像素之間

灰度相關(guān)性很強(qiáng)。時(shí)間冗余：序列圖像幀間畫(huà)面對(duì)應(yīng)像素灰度的相關(guān)

性很強(qiáng)。視覺(jué)冗余：是指人眼不能感知或不敏感的那部分

圖像信息。信息熵冗余：也稱(chēng)編碼冗余，如果圖像中平均每個(gè)

像素使用的比特?cái)?shù)大于該圖像的信息

熵，則圖像中存在冗余。結(jié)構(gòu)冗余：圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。知識(shí)冗余：在有些圖像中還包含與某些先驗(yàn)知識(shí)

有關(guān)的信息。描述語(yǔ)言

1）“這是一幅2*2的圖像，圖像的第一個(gè)像素是紅的，第二個(gè)像素是紅的，第三個(gè)像素是紅的，第四個(gè)像素是紅的”。

2）“這是一幅2*2的圖像，整幅圖都是紅色的”。由此我們知道，整理圖像的描述方法可以達(dá)到壓縮的目的。圖像冗余無(wú)損壓縮的原理RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGB16RGB從原來(lái)的16*3*8=284bits壓縮為：

(1+3)*8=32bits圖像冗余有損壓縮的原理34343434343434343434343434343434343434343434343434253436353434343434323434333730343434343434343435343431利用各種冗余信息，壓縮編碼技術(shù)能夠很好地解決在將模擬信號(hào)轉(zhuǎn)換為數(shù)字信號(hào)后所產(chǎn)生的帶寬需求增加的問(wèn)題，是使數(shù)字信號(hào)走上實(shí)用化的關(guān)鍵技術(shù)之一。表1幾種常見(jiàn)應(yīng)用的碼率

2.應(yīng)用環(huán)境允許圖像有一定程度地失真：

接收端圖像設(shè)備分辨率降低，則可降低圖像分辨

率。

根據(jù)人的視覺(jué)特性對(duì)不敏感區(qū)進(jìn)行降分辨率編碼。

人眼對(duì)靜態(tài)物體的敏感程度大于對(duì)動(dòng)態(tài)物體敏感

程度，可減少表示動(dòng)態(tài)物體bit數(shù)；

人眼對(duì)圖像中心信息敏感程度大于對(duì)圖像邊緣信

息敏感程度，可對(duì)邊緣信息少分配bit數(shù)。

應(yīng)用方關(guān)心圖像區(qū)域有限，可對(duì)其余部分圖像可

采用空間和灰度級(jí)上的粗化。

對(duì)于識(shí)別，圖像特征抽取和描述也是數(shù)據(jù)壓縮。3.2.2圖像壓縮編碼系統(tǒng)的基本構(gòu)成3.2數(shù)據(jù)壓縮與信息論基礎(chǔ)圖像信息源信源編碼器信道編碼器信道信道解碼器信源解碼器圖像輸出編碼器解碼器信源編碼功能是將信源編碼輸出一系列二進(jìn)制數(shù)字序列信道編碼功能是將輸入二進(jìn)制序列形成能夠在信道中傳輸?shù)拇a，具有檢錯(cuò)糾錯(cuò)3.2.2圖像壓縮編碼系統(tǒng)的基本構(gòu)成3.2數(shù)據(jù)壓縮與信息論基礎(chǔ)編碼器構(gòu)成輸入圖像變換器量化器符號(hào)編碼器信道反變換器符號(hào)解碼器輸出圖像3.2.3信息論基礎(chǔ)3.2數(shù)據(jù)壓縮與信息論基礎(chǔ)一、圖像的信息熵：熵是信息量的度量方法,表達(dá)一個(gè)信源平均信息量的大小。它表示某一事件出現(xiàn)的消息越多,事件發(fā)生的可能性越小,數(shù)學(xué)上為概率越小.

出現(xiàn)概率小的事件（符號(hào)）比出現(xiàn)概率大的事件能提供更多的信息量。

設(shè)數(shù)字圖像X中包含的像素的分布灰度級(jí)的集合為A={ai|i=1,2,…,m}，ai在統(tǒng)計(jì)上是無(wú)關(guān)的，且ai出現(xiàn)概率為p(ai),則定義各灰度級(jí)ai所包含信息I(ai)為：如果對(duì)數(shù)字圖像X像素分布各灰度級(jí)作平均度量，則可得平均信息量：則稱(chēng)H(X)為數(shù)字圖像X的熵，單位為bit/像素。可看出，圖像的熵H是表示其各個(gè)灰度級(jí)比特?cái)?shù)的統(tǒng)計(jì)平均值。例如：有一幅40個(gè)像素組成的灰度圖像，灰度共有5級(jí)，分別用A、B、C、D、E表示。40個(gè)像素中出現(xiàn)灰度A的像素?cái)?shù)有15個(gè)；出現(xiàn)灰度B的像素?cái)?shù)有7個(gè)；出現(xiàn)灰度C的像素?cái)?shù)有7個(gè)等等，如下表所示。灰度等級(jí)ABCDE像素?cái)?shù)157765概率15/407/407/406/405/40假設(shè)每個(gè)像素占3位表示，則編碼這幅圖像共需403=120位。求這幅圖象的熵為：這就是說(shuō)每個(gè)像素用2.196位表示，40個(gè)像素需要用87.84位。可看出，通過(guò)求圖像的熵對(duì)圖像編碼，可起到壓縮圖像數(shù)據(jù)作用。二、無(wú)失真編碼理論(可變長(zhǎng)最佳編碼定理)等長(zhǎng)編碼：對(duì)于每個(gè)符號(hào)，如經(jīng)過(guò)量化后的圖像數(shù)據(jù)，如果對(duì)它們每個(gè)值都是以相同長(zhǎng)度的二進(jìn)制碼表示的，稱(chēng)之為等長(zhǎng)編碼或均勻編碼?？勺冮L(zhǎng)編碼：對(duì)于每個(gè)符號(hào)，表示符號(hào)的碼字的長(zhǎng)度不是固定不變的，而是隨符號(hào)出現(xiàn)概率而變化：對(duì)出現(xiàn)概率高的符號(hào)分配較短碼字，對(duì)出現(xiàn)概率低的符號(hào)分配較長(zhǎng)碼字。等長(zhǎng)編碼是將所有符號(hào)當(dāng)作等概率事件處理的。定理2：在變字長(zhǎng)編碼中，如果碼字長(zhǎng)度嚴(yán)格按照對(duì)應(yīng)符號(hào)出現(xiàn)的概率大小逆序排列，則其平均碼字長(zhǎng)度為最小。定理1：若編碼時(shí)，對(duì)出現(xiàn)概率較大的符號(hào)用較少比特?cái)?shù)(短碼)表示，對(duì)出現(xiàn)概率較小的符號(hào)用較多比特?cái)?shù)(長(zhǎng)碼)表示，則其平均碼字長(zhǎng)度L要比等長(zhǎng)編碼時(shí)所需碼字少。在非均勻符號(hào)概率分布情況下，變長(zhǎng)編碼效率高于等長(zhǎng)編碼。三、描述圖像壓縮性能的指標(biāo)：壓縮比：一般情況下壓縮比c1，c愈大則壓縮程度愈高。平均碼字長(zhǎng)度R：k為數(shù)字圖像第k個(gè)碼字Ck的長(zhǎng)度；pk為數(shù)字圖像第k個(gè)碼字Ck相應(yīng)出現(xiàn)概率。編碼效率：H為原始圖像的熵；R是實(shí)際編碼的平均碼字長(zhǎng)度。冗余度r：如果編碼效率100%，說(shuō)明還有冗余信息存在。r越小，說(shuō)明可壓縮的余地越小。統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼是一種無(wú)損編碼，是建立在圖像的統(tǒng)計(jì)特性基礎(chǔ)之上的壓縮編碼。信源統(tǒng)計(jì)編碼方法關(guān)鍵在于去除冗余度。統(tǒng)計(jì)編碼(無(wú)損編碼)游程編碼Huffman編碼算術(shù)編碼LZW字典編碼香農(nóng)編碼3.3霍夫曼編碼(HuffmanCoding)這為Huffman于1952年提出的一種編碼方法，是一種最佳編碼方法。所謂最佳編碼方法是指采用Huffman編碼方法得到的單元像素的比特?cái)?shù)最接近圖像的實(shí)際熵值。而熵為進(jìn)行無(wú)失真編碼的理論極限。Huffman編碼是根據(jù)可變長(zhǎng)最佳編碼定理，應(yīng)用哈夫曼算法而產(chǎn)生的一種編碼方法。1、Huffman編碼方法⑴概率統(tǒng)計(jì)(如對(duì)一幅圖像作灰度信號(hào)統(tǒng)計(jì))，得到n個(gè)不同概率的灰度信息符號(hào)；⑵將n個(gè)灰度信息符號(hào)出現(xiàn)的概率由大到小排序，概率相同的可以任意放；⑶將兩個(gè)最小概率相加(概率個(gè)數(shù)減為n-1個(gè)),形成新的概率集合；再按第⑵步方法重排，如此重復(fù)直到僅有兩個(gè)概率為止；⑷分配碼字。原則為從最后一步開(kāi)始反向進(jìn)行，以二進(jìn)制碼元(0,1)賦值，構(gòu)成Huffman碼字；注意：碼字分配從最后一步開(kāi)始反向進(jìn)行。對(duì)最后兩個(gè)概率一個(gè)賦予“0”碼，一個(gè)賦予“1”碼，這里賦予0和1完全隨機(jī)，不影響結(jié)束。2、舉例1：設(shè)有一圖像序列，含8個(gè)灰度級(jí)x1，x2，,x8，概率分別為：P1=0.04，P2=0.06，P3=0.10，P4=0.10，P5=0.07，P6=0.18，P7=0.05，P8=0.40。

試進(jìn)行Huffman編碼，并計(jì)算編碼效率、壓縮比及冗余度。符號(hào)概率p80.40p60.18p30.10p40.10p50.07p20.06p70.05p10.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)一：概率大的賦予碼字為“0”，概率小的賦予碼字為“1”。分配碼字x1x2x3x4x5x6x7x8碼長(zhǎng)0001101010110000010000100010154344351則有：則其平均碼字長(zhǎng)度為：則其熵為：則其編碼效率為：則其冗余度為：如果壓縮前8個(gè)符號(hào)需要3個(gè)比特量化，經(jīng)壓縮后平均碼字長(zhǎng)度為2.61，則壓縮比為：3.討論：試對(duì)圖像字符序列aaaa

bbb

cc

d

eeeee

fffffff進(jìn)行Huffman編碼。解：對(duì)該圖像字符序列中不同字符進(jìn)行概率統(tǒng)

計(jì)，有：P(a)=4/22P(b)=3/22P(c)=2/22

P(d)=1/22P(e)=5/22P(f)=7/22則進(jìn)行Huffman編碼過(guò)程為：統(tǒng)一：概率大的賦予碼字為“1”，概率小的賦予碼字為“0”。則賦予碼字時(shí)得：a=00b=100c=1011d=1010e=01f=11（或第2種答案：a=00b=101c=1001d=1000e=01f=11）4、Huffman編碼在圖像壓縮中的實(shí)現(xiàn)我們知道，對(duì)一幅圖像進(jìn)行編碼時(shí)，如果圖像的大小大于256時(shí)，這幅圖像的不同的碼字就有可能是很大，例如極限為256個(gè)不同的碼字。對(duì)整幅圖直接進(jìn)行Huffman編碼時(shí)，小分布的灰度值，就有可能具有很長(zhǎng)的編碼。如：100位以上，這樣不但達(dá)不到壓縮的效果反而會(huì)使數(shù)據(jù)量加大，應(yīng)該如何處理？常用的且有效的方法是：

將圖像分割成若干的小塊，對(duì)每塊進(jìn)行獨(dú)立的Huffman編碼。例如：分成的子塊，就可以大大降低不同灰度值的個(gè)數(shù)（最多是64而不是256）。3.4香農(nóng)編碼是一種可變長(zhǎng)編碼，碼字長(zhǎng)度由符號(hào)出現(xiàn)概率決定。1、基本原理(求可變長(zhǎng)度最佳編碼的平均碼字長(zhǎng)度)設(shè)進(jìn)行可變長(zhǎng)度最佳編碼時(shí)，被編碼的信息符號(hào)總數(shù)為N，所用碼元進(jìn)制為D，第i個(gè)符號(hào)出現(xiàn)的概率為Pi，與其對(duì)應(yīng)碼字長(zhǎng)度為ti，則可證明這種編碼結(jié)果的平均碼字長(zhǎng)度R落在下列區(qū)間內(nèi)：式中H為信息熵。由此可引導(dǎo)出對(duì)某一個(gè)信息符號(hào)(碼字)的長(zhǎng)度存在如下關(guān)系式：對(duì)二進(jìn)制進(jìn)一步簡(jiǎn)化為：可見(jiàn)，碼字長(zhǎng)度ti是根據(jù)信息符號(hào)出現(xiàn)概率Pi決定的。2、香農(nóng)編碼步驟：將輸入圖像灰度級(jí)（信息符號(hào)）按出現(xiàn)概率由大到小順序排列(相等者可任意顛倒排列位置)。按式子(1)或式子(2)計(jì)算各概率對(duì)應(yīng)的碼字長(zhǎng)度ti

。

計(jì)算各概率對(duì)應(yīng)的累加概率ai

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

試進(jìn)行香農(nóng)編碼，計(jì)算平均碼字長(zhǎng)度和編碼效率。解：計(jì)算ti：當(dāng)P1=0.04，有：ti=5依次類(lèi)推，得：符號(hào)概率x80.4020000x60.1830.4001100011x30.1040.58100101001x40.1040.68101001010x50.0740.78110001100x20.0650.85110110011011x70.0550.91111010011101x10.0450.96111101011110計(jì)算ti計(jì)算ai十變二

進(jìn)制去掉多余ti尾數(shù)(碼字)則其平均碼字長(zhǎng)度為：則其熵為：則其編碼效率為：可見(jiàn)，香農(nóng)編碼要比Huffman編碼的編碼效率略低一些。3.5行程長(zhǎng)度編碼（游程編碼）行程編碼又稱(chēng)行程長(zhǎng)度編碼（RunLengthEncoding，RLE），是一種熵編碼。行程：對(duì)于圖像編碼，可定義沿特定方向上具有相同灰度值的相鄰像元為一輪，其延續(xù)長(zhǎng)度稱(chēng)之為延續(xù)的行程，簡(jiǎn)稱(chēng)為“行程”。基本原理：將具有相同灰度值的連續(xù)串用其串長(zhǎng)（行程長(zhǎng)度）和一個(gè)代表灰度值來(lái)代替。將行程長(zhǎng)度和代表灰度值組合在一起構(gòu)成行程對(duì)，作為輸入的碼元進(jìn)行編碼。在二值圖像中，每一掃描行總由若干段連著的黑像素（灰度值為0）和連著的白像素（灰度值為1）組成，它們分別稱(chēng)為“黑行程”和“白行程”，且交替出現(xiàn)(全白或全黑掃描行除外)。對(duì)于不同的行程長(zhǎng)度根據(jù)其概率分布分配相應(yīng)的碼字，可以得到較好的壓縮。通常行程編碼比較適合于二值圖像的編碼。例如有一掃描線自左向右線段組成如下所示：線段序號(hào)線段性質(zhì)線段組成線段長(zhǎng)度

1白游程0003

2黑游程1113

3白游程000005

4黑游程11114

5白游程000005則游程長(zhǎng)度進(jìn)行統(tǒng)計(jì)為：3個(gè)0，3個(gè)1，5個(gè)0，4個(gè)0，5個(gè)1(含義為3個(gè)白，3個(gè)黑，5個(gè)白，4個(gè)黑，5個(gè)白)。游程長(zhǎng)度編碼的信息符號(hào)集由長(zhǎng)度為1,2,…,N等各種游程長(zhǎng)度組成。這里N是一條掃描線上的像素總數(shù)。例如，有一字符串“aabbbcddddd”，則經(jīng)行程長(zhǎng)度編碼后，該字符串可以只用“2a3b1c5d”來(lái)表示。

aa

bbb

c

ddddd

(共11*8=88bits)

2a3b1c5d(共8*8=64bits)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，93序號(hào)灰度值行程長(zhǎng)度灰度行程對(duì)1405（5，40）22325（5，232）308（8，0）4934（4，90）5561（1，56）6935（5，93）總數(shù)據(jù)量為：28×8=224bit則得到行程編碼的碼流為：5，40，5，232，8，0，4，93，1，56，5，93規(guī)則：行程長(zhǎng)度編碼用3位二進(jìn)制數(shù)灰度值用8位二進(jìn)制數(shù)8=7+15，40，5，232，7，0，1，0，4，93，1，56，5，93行程編碼所需用的比特位數(shù)為：7×3+7×8=77bit壓縮率為：2.二維行程編碼關(guān)鍵是進(jìn)行二維排序，使像素之間關(guān)系變成一維的鄰接關(guān)系此排序方法主要用于DCT系數(shù)的壓縮編碼。對(duì)以下二維圖象進(jìn)行行程長(zhǎng)度編碼原圖象數(shù)據(jù)大小為：64×8=512bit行程長(zhǎng)度編碼圖象數(shù)據(jù)大小為：3×41+8×41=451bit游程長(zhǎng)度編碼本質(zhì)上說(shuō)就是計(jì)算圖像信號(hào)出現(xiàn)行程長(zhǎng)度，然后將行程長(zhǎng)度轉(zhuǎn)換為代碼。如果不區(qū)分黑、白游程進(jìn)行統(tǒng)一游程長(zhǎng)度編碼，并設(shè)Pi為長(zhǎng)度為i的游長(zhǎng)的概率。則：游長(zhǎng)的熵H平均游長(zhǎng)L游程長(zhǎng)度的熵

(即平均每個(gè)像素的熵)當(dāng)根據(jù)各游長(zhǎng)的概率，利用Huffman編碼時(shí)，則每個(gè)游程的平均碼長(zhǎng)滿(mǎn)足下列不等式：若不等式兩邊同除以平均游長(zhǎng)L，可得每個(gè)像素的平均碼長(zhǎng)n的估值：則每個(gè)像素的熵h即為游長(zhǎng)編碼可達(dá)到的最小比特率的估值。3.6算術(shù)編碼為了解決計(jì)算機(jī)中必須以整數(shù)位進(jìn)行編碼問(wèn)題，提出算術(shù)編碼方法。1、基本原理假設(shè)一個(gè)信源的概率模型。根據(jù)該信源的概率模型，一般把一個(gè)信源集合表示為實(shí)數(shù)線上的0至1間的一個(gè)區(qū)間。這集合中每個(gè)元素用來(lái)縮短這個(gè)區(qū)間。信源集合的元素越多,信息越長(zhǎng),編碼表示所得區(qū)間間隔越小,表示這一間隔所需二進(jìn)制位就越多,碼字越長(zhǎng)。這就是區(qū)間作為代碼的原理。2、編碼方法：(舉例講解）設(shè)圖像信源編碼用a，b，c，d4個(gè)符號(hào)表示，符號(hào)a，b，c，d分別出現(xiàn)概率為：P(a)=0.4，P(b)=0.2,P(c)=0.2,P(d)=0.2假設(shè)各數(shù)據(jù)符號(hào)在[0,1內(nèi)賦值范圍設(shè)定:試對(duì)源數(shù)據(jù)集{dacab}進(jìn)行算術(shù)編碼。a=[0,0.4]，b=[0.4,0.6]，c=[0.6,0.8]，d=[0.8,1.0]解：給出一組關(guān)系式為：

StartN=StartB+LeftCLEndN=StartB

+RightCL式中StartN

為新子區(qū)間的起始位置；

EndN

為新子區(qū)間的結(jié)束位置；

StartB

為前子區(qū)間的起始位置；

LeftC

為當(dāng)前符號(hào)的區(qū)間左端；

RightC

為當(dāng)前符號(hào)的區(qū)間右端；

L

為前子區(qū)間長(zhǎng)度。第一個(gè)被壓縮符號(hào)為“d”，

則前符號(hào)區(qū)間為[0,1，而d為[0.8，1.0

StartN=0+0.81=0.8

EndN=0+1.01=1.0

代碼“d”編碼區(qū)間為[0.8,1.0，寬度為0.2第二個(gè)被壓縮符號(hào)為“a”，

前符號(hào)區(qū)間為[0.8，1.0，“a”為[0，0.4)，則“a”取值范圍應(yīng)在前符號(hào)區(qū)間[0.8，1.0的范圍之內(nèi)，則：

StartN=0.8+00.2=0.8

EndN=0.8+0.40.2=0.88

代碼“a”編碼區(qū)間為[0.8，0.88，寬度為0.08

第三個(gè)被壓縮符號(hào)為“c”，

前符號(hào)區(qū)間[0.8，0.88)，c為[0.6，0.8)

StartN

=0.8+0.60.08=0.848

EndN

=0.8+0.80.08=0.864

“c”實(shí)際編碼區(qū)間為[0.848，0.864，寬度為0.016第四個(gè)被壓縮符號(hào)為“a”，

前符號(hào)區(qū)間[0.848，0.864)，a為[0，0.4)

StartN=0.848+00.016=0.848

EndN

=0.848+0.40.016=0.8544

“a”實(shí)際編碼區(qū)間為[0.848，0.8544，寬度為0.0064第五個(gè)被壓縮符號(hào)為“b”，

前符號(hào)區(qū)間[0.848，0.8544)，b為[0.4，0.6)

StartN=0.848+0.40.0064=0.85056

EndN

=0.848+0.60.0064=0.85184

“b”實(shí)際編碼區(qū)間為[0.85056，0.85184至此，數(shù)據(jù)串{dacab}已經(jīng)被描述成一個(gè)編碼實(shí)數(shù)區(qū)間為[0.85056，0.85184?；蛘哒f(shuō)在此區(qū)間內(nèi)任一實(shí)數(shù)值都唯一對(duì)應(yīng)該數(shù)據(jù)序列。把該十進(jìn)制實(shí)數(shù)區(qū)間用二進(jìn)制表示為：[0.110110011011，0.110110100001。把該十進(jìn)制實(shí)數(shù)區(qū)間用二進(jìn)制表示為：

[0.110110011011，0.110110100001。但從這個(gè)區(qū)間可以看出，0.1101101位于這個(gè)區(qū)間內(nèi)并且其編碼最短，故把其作為數(shù)據(jù)序列{dacab}的編碼輸出?？紤]到算術(shù)編碼中任一數(shù)據(jù)序列的編碼都含有“0.”，所以編碼時(shí)可以不考慮“0.”。最后所得的碼點(diǎn)值“1101101”(忽視小數(shù)點(diǎn))就是對(duì){dacab}進(jìn)行算術(shù)編碼的結(jié)果。所以“dacab”的編碼區(qū)間為[0.85056，0.85184]“dacab”的編碼值為1101101信源熵為：平均碼長(zhǎng)：編碼效率：3.7LZW編碼LZW編碼又稱(chēng)字串表編碼，屬于無(wú)損編碼。

基本思想:

在編碼過(guò)程中，將所遇到的字符串建立一個(gè)字符串表，表中的每個(gè)字符串都對(duì)應(yīng)一個(gè)索引，編碼時(shí)用該字符串在字串表中的索引來(lái)代替原始的數(shù)據(jù)串。字符串表是在壓縮過(guò)程中動(dòng)態(tài)生成的，不必將它保存在壓縮文件里，因?yàn)榻鈮嚎s時(shí)字符串表可以由壓縮文件中的信息重新生成。

編碼方法(舉例講解)

設(shè)有一來(lái)源于4色（以a、b、c、d表示）圖像的數(shù)據(jù)流aabcabbbbd，現(xiàn)對(duì)其進(jìn)行LZW編碼。編碼過(guò)程如下：①設(shè)S1、S2為兩個(gè)存放字符串的臨時(shí)變量。

LZW_CLEAR為字符表初始化標(biāo)志。

LZW_EOI為字符表編碼結(jié)束標(biāo)志。②根據(jù)圖像中使用顏色數(shù)初始化一個(gè)字串表，每個(gè)顏色對(duì)應(yīng)字串表中一個(gè)索引。由于圖像中只有四種顏色，僅用4比特表示字符串表中每個(gè)字符串索引。建立初始化字符串表如下所示。字符串索引a0Hb1Hc2Hd3HLZW_CLEAR4HLZW_EOI5H表中前四項(xiàng)代表4種顏色，

后兩項(xiàng)分別表示初始化和圖像結(jié)束標(biāo)志。把S1和S2初始化為空（即NULL），輸出LZW_CLEAR的在字符串表中的索引值4H，接下來(lái)是對(duì)圖像數(shù)據(jù)的編碼。③從圖像數(shù)據(jù)流的第一個(gè)字符開(kāi)始，每次讀取一個(gè)字符，將其賦給字符串變量S2。則讀取的圖像數(shù)據(jù)流的第一個(gè)字符為“a”，賦給S2。④判斷“S1+S2”是否存在于字符串表中，如果字符串表中存在“S1+S2”，則S1=S1+S2，不輸出任何結(jié)果；否則，輸出S1在字符串表中索引，并且在字符串表末尾為“S1+S2”添加索引，同時(shí)S1=S2。讀取第一個(gè)字符為“a”賦給S2，則有S1+S2=“a”。而“a”存在于字符串表中，對(duì)應(yīng)索引值為0H，則不輸出任何結(jié)果，只使S1=S1+S2。接著讀入下一個(gè)字符“a”賦給S2，因S1+S2=“aa”不存在于字串表中，所以對(duì)應(yīng)輸出結(jié)果為輸出S1=“a”的索引0H，同時(shí)在字符串表末尾添加新字符串“aa”的索引6H，并使S1=S2=“a”。

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

依次讀取數(shù)據(jù)流中的每個(gè)字符，如果S1+S2沒(méi)有出現(xiàn)在字符串表中，則輸出S1中的字符串的索引作為輸出結(jié)果，并在字符串表末尾為新字符串S1+S2添加索引，并使S1=S2；否則，不輸出任何結(jié)果，只是使S1=S1+S2。最終，直到所有字符讀完為止。所有字符處理完畢后，輸出S1中的字符串的索引，最后輸出結(jié)束標(biāo)志LZW_EOI的索引。至此，編碼完畢，圖像數(shù)據(jù)流aabcabbbbd完整編碼過(guò)程如下表：輸入數(shù)據(jù)S2S1+S2輸出結(jié)果S1生成新字符串及索引NULLNULL4HNULLaaaaaa0Haaa<6H>bab0Hbab<7H>cbc1Hcbc<8H>aca2Haca<9H>bababbabb7Hbabb<AH>bbb1Hbbb<BH>bbbbbdb