圖像壓縮(my)青島大學(xué)

圖像壓縮編碼圖像壓縮編碼

數(shù)據(jù)壓縮與信息論基礎(chǔ)圖像壓縮與編碼基本概念信息論基礎(chǔ)圖像壓縮編碼

無損壓縮

有損壓縮圖像壓縮編碼主要國際標(biāo)準(zhǔn)靜止圖像壓縮編碼標(biāo)準(zhǔn)-JPEG運(yùn)動圖像壓縮編碼標(biāo)準(zhǔn)-MPEG

第一節(jié)圖像壓縮與編碼基本概念

為什么要進(jìn)行圖像壓縮圖像數(shù)據(jù)壓縮的可能性數(shù)據(jù)冗余圖像壓縮的目的圖像數(shù)據(jù)壓縮技術(shù)的重要指標(biāo)圖像數(shù)據(jù)壓縮的應(yīng)用領(lǐng)域圖像編碼中的保真度準(zhǔn)則信息論基礎(chǔ)圖像壓縮模型一.為什么要進(jìn)行圖像壓縮？

數(shù)字圖像通常要求很大的比特數(shù)，這給圖像的傳輸和存儲帶來相當(dāng)大的困難。要占用很多的資源，花很高的費(fèi)用。如一幅512*512的灰度圖象的比特數(shù)為

512*512*8=256k

再如一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512*512象素，每象素的R、G、B三分量分別占8bit，總比特數(shù)為

90*60*24*3*512*512*8bit=97,200M。如一張CD光盤可存600兆字節(jié)數(shù)據(jù)，這部電影光圖像（還有聲音）就需要160張CD光盤用來存儲。

對圖像數(shù)據(jù)進(jìn)行壓縮顯得非常必要。二.圖像數(shù)據(jù)壓縮的可能性

一般原始圖像中存在很大的冗余度。用戶通常允許圖像失真。當(dāng)信道的分辨率不及原始圖像的分辨率時，降低輸入的原始圖像的分辨率對輸出圖像分辨率影響不大。用戶對原始圖像的信號不全都感興趣，可用特征提取和圖像識別的方法，丟掉大量無用的信息。提取有用的信息，使必須傳輸和存儲的圖像數(shù)據(jù)大大減少。

設(shè)：n1和n2是在兩個表達(dá)相同信息的數(shù)據(jù)集中，所攜帶的單位信息量。壓縮率：——描述壓縮算法性能

CR=n1/n2

其中，n1是壓縮前的數(shù)據(jù)量，n2是壓縮后的數(shù)據(jù)量相對數(shù)據(jù)冗余：

RD=1–1/CR例：CR=20;RD=19/20描述信源的數(shù)據(jù)是信息量（信源熵）和信息冗余量之和。三.數(shù)據(jù)冗余1）數(shù)據(jù)冗余的基本概念A(yù).編碼冗余：

2）常見的數(shù)據(jù)冗余在數(shù)字圖像壓縮中，常有3種基本的數(shù)據(jù)冗余：編碼冗余、像素間的冗余以及心理視覺冗余為表達(dá)圖像數(shù)據(jù)需要用一系列符號，用這些符號根據(jù)一定的規(guī)則來表達(dá)圖像就是對圖像編碼。對每個信息或事件所賦的符號序列稱為碼字，而每個碼字里的符號個數(shù)稱為碼字的長度。設(shè)定義在[0,1]區(qū)間的離散隨機(jī)變量sk代表圖像的灰度值，每個sk以概率ps(sk)出現(xiàn)Ps(sk)=nk/nk=0,1,2,…,L-1其中L為灰度級數(shù)，nk是第k個灰度級出現(xiàn)的次數(shù)，n是圖像中像素總個數(shù)。設(shè)用來表示sk的每個數(shù)值的比特數(shù)是，那么為表示每個像素所需的平均比特數(shù)就是編碼所用的符號構(gòu)成的集合稱為碼本。等長碼：對于一個消息集合中的不同消息，用相同長度的不同碼字表示，編解碼簡單，編碼效率不高。變長碼：與等長碼相對應(yīng)，對于一個消息集合中的不同消息，也可以用不同長度的碼字表示，編碼效率高，編碼解碼復(fù)雜。例：如果用8位表示該圖像的像素，我們就說該圖像存在著編碼冗余，因?yàn)樵搱D像的像素只有兩個灰度，用一位即可表示。如果一個圖像的灰度級編碼，使用了多于實(shí)際需要的編碼符號，就稱該圖像包含了編碼冗余。B.像素冗余：

由于任何給定的像素值，原理上都可以通過它的鄰居預(yù)測到，單個像素攜帶的信息相對是小的。對于一個圖像，很多單個像素對視覺的貢獻(xiàn)是冗余的。這是建立在對鄰居值預(yù)測的基礎(chǔ)上。原始圖像越有規(guī)則，各像素之間的相關(guān)性越強(qiáng)，它可能壓縮的數(shù)據(jù)就越多。例：原圖像數(shù)據(jù)：234223231238235

壓縮后數(shù)據(jù)：23411-8-73相同的目標(biāo)相同的直方圖象素間的相關(guān)性不同類似還有：圖像彩色光譜空間的冗余；

視頻圖像信號在時間上的冗余；

一些信息在一般視覺處理中比其它信息的相對重要程度要小，這種信息就被稱為視覺心理冗余。(3)視覺心理冗余：33K15K四.圖像壓縮的目的

圖像數(shù)據(jù)壓縮的目的是在滿足一定圖像質(zhì)量條件下，用盡可能少的比特數(shù)來表示原始圖像，以提高圖像傳輸?shù)男屎蜏p少圖像存儲的容量。在信息論中稱為信源編碼。

圖像從結(jié)構(gòu)上大體上可分為兩大類，一類是具有一定圖形特征的結(jié)構(gòu)，另一類是具有一定概率統(tǒng)計特性的結(jié)構(gòu)。基于不同的圖像結(jié)構(gòu)特性，應(yīng)采用不同的壓縮編碼方法。五.圖像數(shù)據(jù)壓縮技術(shù)的重要指標(biāo)（1）壓縮比：圖像壓縮前后所需的信息存儲量之比，壓縮比越大越好。（2）壓縮算法：利用不同的編碼方式，實(shí)現(xiàn)對圖像的數(shù)據(jù)壓縮。（3）失真性：壓縮前后圖像存在的誤差大小。

全面評價一種編碼方法的優(yōu)劣，除了看它的編碼效率、實(shí)時性和失真度以外，還要看它的設(shè)備復(fù)雜程度，是否經(jīng)濟(jì)與實(shí)用。常采用混合編碼的方案，以求在性能和經(jīng)濟(jì)上取得折衷。隨著計算方法的發(fā)展，使許多高效而又比較復(fù)雜的編碼方法在工程上有實(shí)現(xiàn)的可能。1）辦公自動化；

2）醫(yī)學(xué)圖像處理；

3）衛(wèi)星遙感遙測系統(tǒng)；

4）高清晰度電視HDTV；

5）可視電話、會議電視；

6）移動多媒體圖像及視頻傳輸：

彩信業(yè)務(wù)，手機(jī)視頻；……

凡是涉及到圖像數(shù)據(jù)的傳輸、交換與存儲的領(lǐng)域均要求進(jìn)行圖像數(shù)據(jù)的壓縮。六圖像數(shù)據(jù)壓縮的應(yīng)用領(lǐng)域七.圖像編碼中的保真度準(zhǔn)則

圖像信號在編碼和傳輸過程中會產(chǎn)生誤差，尤其是在有損壓縮編碼中，產(chǎn)生的誤差應(yīng)在允許的范圍之內(nèi)。在這種情況下，保真度準(zhǔn)則可以用來衡量編碼方法或系統(tǒng)質(zhì)量的優(yōu)劣。通常，這種衡量的尺度可分為客觀保真度準(zhǔn)則和主觀保真度準(zhǔn)則。

通常使用的客觀保真度準(zhǔn)則有輸入圖像和輸出圖像的均方根誤差；輸入圖像和輸出圖像的均方根信噪比兩種。

均方根誤差:

設(shè)輸入圖像是由N×N個像素組成，令其為f(x,y)，其中x,y=0,1,2,…,N-1。這樣一幅圖像經(jīng)過壓縮編碼處理后，送至受信端，再經(jīng)譯碼處理，重建原來圖像，這里令重建圖像為g(x,y)。它同樣包含N×N個像素，并且x,y=0,1,2,…,N-1。(1)客觀保真度準(zhǔn)則在0,1,2,…,N-1范圍內(nèi)x,y的任意值，輸入像素和對應(yīng)的輸出圖像之間的誤差可用下式表示：而包含N×N像素的圖像之均方誤差為:由式可得到均方根誤差為

如果把輸入、輸出圖像間的誤差看作是噪聲，那么，重建圖像g(x,y)可由下式表示：

在這種情況下，另一個客觀保真度準(zhǔn)則——重建圖像的均方信噪比如下式表示：

圖像處理的結(jié)果,大多是給人觀看，由研究人員來解釋的，因此，圖像質(zhì)量的好壞，既與圖像本身的客觀質(zhì)量有關(guān)，也與視覺系統(tǒng)的特性有關(guān)。有時候，客觀保真度完全一樣的兩幅圖像可能會有完全不相同的視覺質(zhì)量，所以又規(guī)定了主觀保真度準(zhǔn)則，這種方法是把圖像顯示給觀察者，然后把評價結(jié)果加以平均，以此來評價一幅圖像的主觀質(zhì)量。(2)主觀保真度準(zhǔn)則評分評價說明1優(yōu)秀的優(yōu)秀的具有極高質(zhì)量的圖像2好的

是可供觀賞的高質(zhì)量的圖像，干擾并不令人討厭

3可通過的

圖像質(zhì)量可以接受，干擾不討厭4邊緣的圖像質(zhì)量較低，希望能加以改善，干擾有些討厭5劣等的圖像質(zhì)量很差，尚能觀看，干擾顯著地令人討厭6不能用圖像質(zhì)量非常之差，無法觀看另外一種方法是規(guī)定一種絕對尺度，如：表6.1電視圖像質(zhì)量評價尺度八.信息理論（一）、信源空間概述

1、信息：事物運(yùn)動狀態(tài)或存在方式的不確定性的描述；

2、信源：信源是產(chǎn)生各類信息的實(shí)體。信源給出的符號是不確定的，可用隨機(jī)變量及其統(tǒng)計特性描述。信源空間：隨機(jī)符號及其出現(xiàn)概率的空間；

3、信源的分類：

（1）連續(xù)信源—離散信源；

（2）無記憶信源—有記憶信源（相關(guān)信源）—有限長度記憶信源（Markov信源）（二）、信息的度量

1、信息公理

（1）信息由不確定性程度進(jìn)行度量；

確定事件的信息量為零。

（2）不確定性程度越高信息量越大；

（3）相互獨(dú)立性與信息量可加性；

獨(dú)立事件的聯(lián)合信息等于兩個獨(dú)立事件的信息總和。

滿足上述公理的函數(shù)為：2、離散無記憶信源（DNMS）的信息量度量：

（1）信源符號的自信息量定義為：(a)非負(fù)性；(b)信息量的單位：底為2時——單位為：比特（bit）底為e時——單位為：奈特（Nat）底為10時——單位為：哈特（2）、信源平均自信息量（信息熵）

離散無記憶信源A的平均自信息量（信息熵）定義為：熵是編碼所需比特數(shù)的下限，即編碼所需要最少的比特例:設(shè)8個隨機(jī)變量具有同等概率為1／8，計算信息熵H。解:根據(jù)公式4-10可得：

H=8*[-1/8*(log2(1/8))=8*[-1/8*(-3)]=3

圖像熵指該圖像的平均信息量，即表示圖像中各個灰度級比特數(shù)的統(tǒng)計平均值，等概率事件的熵最大。3、平均碼字長借助熵的概念可以定義量度任何特定碼的性能的準(zhǔn)則，即平均碼字長度。其中βi為灰度級di所對應(yīng)的碼字長度。的單位也是比特/字符。4、編碼效率編碼符號是在字母集合A={a1,a2,a3,…am}中選取的。如果編碼后形成一個新的等概率的無記憶信源，字母數(shù)為n，則它的最大熵應(yīng)為logn比特/符號。因此這是一個極限值。如果H(d)/=logn，則可以認(rèn)為編碼效率已經(jīng)達(dá)到100%，如果H(d)/<logn，則可認(rèn)為編碼效率較低。編碼效率冗余度根據(jù)信息熵編碼理論，可以證明在H條件下，總可以設(shè)計出某種無失真編碼方法。若編碼結(jié)果使遠(yuǎn)大于H，表明這種編碼效率很低，占用的比特數(shù)太多。若編碼結(jié)果使等于或接近于H，這種狀態(tài)的編碼方法稱為最佳編碼。若要求編碼結(jié)果使<H，則必然丟失信息而引起圖像失真。這就是在允許失真條件下的一些失真編碼方法。5、壓縮比壓縮比是衡量數(shù)據(jù)壓縮程度的指標(biāo)之一。目前常用的壓縮比定義為其中LB為源代碼長度，Ld為壓縮后代碼長度，Pr為壓縮比。壓縮比的物理意義是被壓縮掉的數(shù)據(jù)占據(jù)源數(shù)據(jù)的百分比。當(dāng)壓縮比Pr接近100%時壓縮效果最理想。6、互信息

信源編碼輸出為bk給出的關(guān)于ai的信息量究竟為多少呢？為此將引入另外一個信息量度－互信息

對給定的兩個離散信源X和Y，Y中事件bk的發(fā)生給出關(guān)于X中事件ai的互信息I(ai:bk)定義為：其中，p(ai|bk)表示信源編碼輸出為bk，估計信源輸入為ai的條件概率。I(ai|bk)稱為條件自信息量，表示在發(fā)現(xiàn)信源編碼輸出為bk，對信源輸入為ai的不確定性的猜測或知道bk后ai還保留的信息量。I(ai)表示ai的不確定性。兩者值差即為bk解除的ai不確定性的多少。設(shè)一幅灰度級為K的圖像，圖像中第k級灰度出現(xiàn)的概率為pk，圖像大小為M×N，每個像素用d比特表示，每兩幀圖像間隔△t數(shù)字圖像的熵H圖像的平均碼字長度R為：編碼效率η定義為：信息冗余度為：每秒鐘所需的傳輸比特數(shù)bps為：壓縮比r為：圖像信息源圖像預(yù)處理圖像信源

編碼信道編碼調(diào)制信道傳輸解調(diào)信道解碼圖像信源

解碼顯示圖像九.圖像的壓縮模型源數(shù)據(jù)編碼：完成原數(shù)據(jù)的壓縮。通道編碼：為了抗干擾，增加一些容錯、校驗(yàn)位，實(shí)際上是增加冗余。通道：如Internet、廣播、通訊、可移動介質(zhì)源數(shù)據(jù)編碼通道編碼通道通道解碼源數(shù)據(jù)解碼源數(shù)據(jù)編碼的模型源數(shù)據(jù)解碼的模型映射器量化器符號編碼器符號解碼器反向映射器源數(shù)據(jù)編碼與解碼的模型映射器：減少像素冗余，如使用RLE編碼。或進(jìn)行圖像變換量化器：減少視覺心理冗余，僅用于有損壓縮符號編碼器：減少編碼冗余，如使用哈夫曼編碼源數(shù)據(jù)編碼與解碼的模型預(yù)測編碼圖像編碼無損壓縮編碼有損壓縮編碼哈夫曼編碼行程編碼算術(shù)編碼

頻率域方法

其他編碼方法常用的圖像壓縮編碼方法※無損壓縮算法中刪除的僅僅是圖像數(shù)據(jù)中冗余的信息，因此在解壓縮時能精確恢復(fù)原圖像，無損壓縮的壓縮比很少有能超過3：1的,常用于要求高的場合。第二節(jié)無損壓縮編碼哈夫曼編碼等長碼：對于一個消息集合中的不同消息，用相同長度的不同碼字表示，編解碼簡單，編碼效率不高。變長碼：與等長碼相對應(yīng)，對于一個消息集合中的不同消息，也可以用不同長度的碼字表示，編碼效率高，編碼解碼復(fù)雜。

哈夫曼編碼是一種利用信息符號概率分布特性的變字長的編碼方法。對于出現(xiàn)概率大的信息符號編以短字長的碼，對于出現(xiàn)概率小的信息符號編以長字長的碼。

方法：將信源符號按出現(xiàn)概率從大到小排成一列，然后把最末兩個符號的概率相加，合成一個概率。把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的概率加起來，合成一個概率。重復(fù)上述做法，直到最后剩下兩個概率為止。從最后一步剩下的兩個概率開始逐步向前進(jìn)行編碼。每步只需對兩個分支各賦予一個二進(jìn)制碼，如對概率大的賦予碼0，對概率小的賦予碼1。Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011哈夫曼編碼效率信源熵為：H=-∑Pilog2Pi=-(0.4log20.4+0.3log20.3+2*0.1log20.1+0.06log20.06+0.04log20.04)=2.14比特/符號平均碼字長度：R=∑βiPi碼字長度R=∑βiPi=0.4×1+0.3×2+0.1×3+0.1×4+0.06×5+0.04×5=2.2比特/符號編碼效率：η=H/R(%)η=H/R=2.14/2.2=0.973=97.3%編碼舉例cbafe7/225/224/222/2201f=10e=00a=01b=110c=1110d=1111d1/223/226/2222/2213/229/223/2201010101作業(yè)：1.有如下信源x，u1u2u3u4u5u6u7u8P1P2P3P4P5P6P7P8其中：P1＝0.21,P2＝0.09,P3＝0.11,P4＝0.13,P5＝0.07,P6＝0.12,P7＝0.08,P8＝0.19。將該信源進(jìn)行哈夫曼編碼。2.設(shè)一幅灰度級為8（分別用S0、S1、S2、S3、S4、S5、S6、S7表示）的圖像中，各灰度所對應(yīng)的概率分別為0.40、0.18、0.10、0.10、0.07、0.06、0.05、0.04?，F(xiàn)對其進(jìn)行哈夫曼編碼X＝3.設(shè)有一信源X={x1,x2,x3,x4}，對應(yīng)概率P={0.5,0.1975,0.1775,0.125}.

⑴進(jìn)行霍夫曼編碼(要求大概率的賦碼字0,小概率的賦碼字1)，給出碼字，平均碼長，編碼效率;

⑵對碼串10101011010110110000011110011解碼.

由于霍夫曼編碼法需要多次排序，當(dāng)很多時十分不便，為此費(fèi)諾(Fano)和香農(nóng)(Shannon)分別單獨(dú)提出類似的方法，使編碼更簡單。具體編碼方法如下：①把按概率由大到小、從上到下排成一列，然后把分成兩組，，并使得②把兩組分別按0，1賦值。然后分組、賦值，不斷反復(fù)，直到每組只有一種輸入為止。將每個所賦的值依次排列起來就是費(fèi)諾—香農(nóng)編碼。

香農(nóng)－費(fèi)諾編碼以前面哈夫曼編碼的例子進(jìn)行香農(nóng)－費(fèi)諾編碼：輸入概率

x10.400x20.31010x30.11001100x40.111101x50.06101110x60.0411111從理論上分析，采用哈夫曼編碼可以獲得最佳信源字符編碼效果;實(shí)際應(yīng)用中，由于信源字符出現(xiàn)的概率并非滿足2的負(fù)冪次方，因此往往無法達(dá)到理論上的編碼效率和信息壓縮比;算術(shù)編碼以信源字符序列{x，y}為例設(shè)字符序列{x，y}對應(yīng)的概率為{1/3，2/3}，Nx和Ny分別表示字符x和y的最佳碼長，則根據(jù)信息論有：字符x、y的最佳碼長分別為1.58bit和0.588bi;這表明，要獲得最佳編碼效果，需要采用小數(shù)碼字長度,這是不可能實(shí)現(xiàn)的;即采用哈夫曼方法對{x，y}的碼字分別為0和1，也就是兩個符號信息的編碼長度都為1。對于出現(xiàn)概率大的字符y并未能賦予較短的碼字;實(shí)際編碼效果往往不能達(dá)到理論效率;為提高編碼效率，Elias等人提出了算術(shù)編碼算法。算術(shù)編碼的特點(diǎn)

算術(shù)編碼是信息保持型編碼，它不像哈夫曼編碼，無需為一個符號設(shè)定一個碼字;算術(shù)編碼分為固定方式和自適應(yīng)方式兩種編碼;選擇不同的編碼方式，將直接影響到編碼效率;自適應(yīng)算術(shù)編碼的方式，無需先定義概率模型，適合于無法知道信源字符概率分布的情況;當(dāng)信源字符出現(xiàn)的概率比較接近時，算術(shù)編碼效率高于哈夫曼編碼的效率，在圖像通信中常用它來取代哈夫曼編碼;實(shí)現(xiàn)算術(shù)編碼算法的硬件比哈夫曼編碼復(fù)雜。編碼原理

算術(shù)編碼方法是將被編碼的信源消息表示成0-1之間的一個間隔，即小數(shù)區(qū)間，消息越長，編碼表示它的間隔就越小;以小數(shù)表示間隔，表示的間隔越小所需的二進(jìn)制位數(shù)就越多，碼字就越長。反之，間隔越大，編碼所需的二進(jìn)制位數(shù)就少，碼字就短。算術(shù)編碼將被編碼的圖像數(shù)據(jù)看作是由多個符號組成的字符序列，對該序列遞歸地進(jìn)行算術(shù)運(yùn)算后，成為一個二進(jìn)制分?jǐn)?shù);接收端解碼過程也是算術(shù)運(yùn)算，由二進(jìn)制分?jǐn)?shù)重建圖像符號序列。編碼舉例

設(shè)圖像信源編碼可用a、b、c、d這4個符號來表示，若圖像信源字符集為{dacba}，信源字符出現(xiàn)的概率分別如下表所示，采用算術(shù)編碼對圖像字符集編碼。信源字符abcd出現(xiàn)概率0.40.20.20.2算術(shù)編碼的基本步驟

(1)根據(jù)已知條件和數(shù)據(jù)可知，信源各字符在區(qū)間[0，1]內(nèi)的子區(qū)間間隔分別如下：

a=[0.0，0.4)b=[0.4，0.6)c=[0.6，0.8)d=[0.8，1.0)(2)計算中按如下公式產(chǎn)生新的子區(qū)間：(3)第1個被壓縮的字符為“d”，其初始子區(qū)間為[0.8，1.0)(4)第2個被壓縮的字符為“a”，由于其前面的字符取值區(qū)間為[0.8，1.0)范圍，因此，字符“a”應(yīng)在前一字符區(qū)間間隔[0.8，1.0)的[0.0，0.4)子區(qū)間內(nèi)，根據(jù)公式(8-15)可得：

=0.8+0.0×(1.0-0.8)=0.8=0.8+0.4×(1.0-0.8)=0.88(5)第3個被壓縮的字符為“c”，由于其前面的字符取值區(qū)間為[0.8，0.88)范圍內(nèi)，因此，字符“c”應(yīng)在前一字符區(qū)間間隔[0.8，0.88)的[0.6，0.8)子區(qū)間內(nèi)，根據(jù)(8-15)可得：

=0.8+0.6×(0.88-0.8)=0.848=0.8+0.8×(0.88-0.8)=0.864(6)第4個被壓縮的字符為“b”，由于其前面的字符取值區(qū)間為[0.848，0.864)范圍內(nèi)，因此，字符“b”應(yīng)在前一字符區(qū)間間隔[0.848，0.864)的[0.4，0.6)子區(qū)間內(nèi)，根據(jù)(8-15)可得：

=0.848+0.4×(0.864-0.848)=0.8544=0.848+0.6×(0.864-0.848)=0.8576(7)第5個被壓縮的字符為“a”，由于其前面的字符取值區(qū)間為[0.8544，0.8)范圍內(nèi)，因此，字符“a”應(yīng)在前一字符區(qū)間間隔[0.8544，0.8576)的[0.0，0.4)子區(qū)間內(nèi)，根據(jù)(8-15)可得：

=0.8544+0.0×(0.8576-0.8544)=0.8544=0.8544+0.4×(0.8576-0.86544)=0.85568經(jīng)過上述計算，字符集{dacba}被描述在實(shí)數(shù)[0.8544，0.85568)子區(qū)間內(nèi)，即該區(qū)間內(nèi)的任一實(shí)數(shù)值都惟一對應(yīng)該符號序列{dacba}；因此，可以用[0.8544，0.85568)內(nèi)的一個實(shí)數(shù)表示字符集{dacba}。[0.8544，0.85568)子區(qū)間的二進(jìn)制表示形式為：[0.1101101010000110，0.1101101100001101)；在該區(qū)間內(nèi)的最短二進(jìn)制代碼為0.11011011，去掉小數(shù)點(diǎn)及其前的字符，從而得到該字符序列的算術(shù)編碼為11011011。算術(shù)編碼可以通過硬件電路實(shí)現(xiàn)，在上述乘法運(yùn)算，可以通過右移來實(shí)現(xiàn)，因此在算術(shù)編碼算法中只有加法和移位運(yùn)算。算術(shù)編碼效能

根據(jù)上述運(yùn)算結(jié)果，編碼11011011惟一代表字符序列{dacba}，因此，平均碼字長度為：

bit/字符

[題]己知信源X=

試對1011進(jìn)行算術(shù)編碼。011/43/4[解](1)對二進(jìn)制信源只有兩個符號“0”

和“1”，設(shè)置小概率Qe=1/4，大概率

Pe=1–Qe=3/4.(2)設(shè)C為子區(qū)間的左端起始位置，A為子區(qū)間的寬度，符號“0”的子區(qū)間為[0,1/4),符號“1”的子區(qū)間為[1/4,1)(3)初始子區(qū)間為[0,1),C=0,A=1,子區(qū)間按以下各步依次縮小：步序符號CA110+1*1/4=1/41*3/4=3/4201/43/4*1/4=3/16311/4+3/16*1/4=19/643/16*3/4=9/644119/64+9/64*1/4=85/2569/64*3/4=27/25601/4119/6485/25610117/16112/256最后的子區(qū)間左端(起始位置)C=(85/256)d=(0.01010101)b最后的子區(qū)間右端(終止位置)C+A=(112/256)d=(0.01110000)b

編碼結(jié)果為子區(qū)間頭、尾之間取值，其值為0.011,可編碼為011，原來4個符號1011現(xiàn)被壓縮為三個符號011。行程編碼RLE編碼（游程長度編碼）——RunLengthEncoding概念：行程：具有相同灰度值的像素序列。編碼思想：去除像素冗余。用行程的灰度和行程的長度代替行程本身。由于一幅圖像中有許多顏色相同的圖塊，用一整數(shù)對存儲一個像素的顏色值及相同顏色像素的數(shù)目（長度）。例如：（G，L）

長度顏色值編碼時采用從左到右，從上到下的排列，每當(dāng)遇到一串相同數(shù)據(jù)時就用該數(shù)據(jù)及重復(fù)次數(shù)代替原來的數(shù)據(jù)串。000000003333333333222222222226666666111111111111111111111111555555555555888888888888888888555555555555553333222222222222222222(0,8)(3,10)(2,11)(6,7)(1,18)(1,6)(5,12)(8,18)(5,14)(3,4)(2,18)18*7的像素顏色僅用11對數(shù)據(jù)游程長度編碼RLE（RunLengthEncoding）：分析：對于有大面積色塊的圖像，壓縮效果很好直觀，經(jīng)濟(jì),是一種無損壓縮對于紛雜的圖像，壓縮效果不好，最壞情況下，會加倍圖像RLE編碼——RunLengthEncoding適合行程編碼的圖適合行程編碼的圖※有損壓縮是通過犧牲圖像的準(zhǔn)確率以實(shí)現(xiàn)較大的壓縮率，如果容許解壓圖像有一定的誤差，則壓縮率可顯著提高。有損壓縮在壓縮比大于30：1時仍然可重構(gòu)圖像，而如果壓縮比為10:1到20:1，則重構(gòu)的圖像與原圖幾乎沒有差別第三節(jié)有損壓縮編碼變換編碼圖像數(shù)據(jù)一般有較強(qiáng)的相關(guān)性，若所選用的正交矢量空間的基矢量與圖像本身的主要特征相近，在該正交矢量空間中描述圖像數(shù)據(jù)則會變得更簡單。經(jīng)過正交變換，會把原來分散在原空間的圖像數(shù)據(jù)在新的坐標(biāo)空間中得到集中。對于大多數(shù)圖像，大量變換系數(shù)很小，只要刪除接近于零的系數(shù)，并且對較小的系數(shù)進(jìn)行粗量化，而保留包含圖像主要信息的系數(shù)，以此進(jìn)行壓縮編碼。在重建圖像進(jìn)行解碼時，所損失的將是一些不重要的信息，幾乎不會引起圖像的失真?；靖拍睿簩⒖臻g域里描述的圖像，經(jīng)過某種變換（常用的是二維正交變換，如付里葉變換、離散余弦變換、沃爾什變換等），在變換域中進(jìn)行描述，達(dá)到改變能量分布的目的。優(yōu)點(diǎn)：將能量在空間域的分散分布變?yōu)樵谧儞Q域的相對集中分布有利于進(jìn)一步采用其它的處理方式，如“之”(zig-zag)字形掃描、自適應(yīng)量化、變長編碼等，從而對圖像信息量進(jìn)行有效壓縮。變換編碼的概念物理解釋：

圖像正交變換實(shí)現(xiàn)數(shù)據(jù)壓縮的物理本質(zhì)：經(jīng)過坐標(biāo)旋轉(zhuǎn)或變換，能夠把接近均勻散布在各個坐標(biāo)軸上的原始圖像數(shù)據(jù)，變換在新的坐標(biāo)系中，集中在少數(shù)坐標(biāo)上?？捎幂^少的編碼比特表示一幅子圖像。圖9.13正交變換物理概念012345677654321(a)變換前x1x2012345677654321(b)變換后x1x2y1y2從左圖可以看出，相鄰像素之間的相關(guān)性非常強(qiáng)。從右圖可以看出，直流系數(shù)位于左上角。變換域要傳送的數(shù)據(jù)量比空間域的大大減少。591106–1828–3414183350000000-1000000030000000-1000000000000000-1000000000000000(b)DCT系數(shù)矩陣圖9.14一個子圖象的二維余弦變換實(shí)例98929580758268509791947974816749958992777279654793879075707763459185887368756143898386716673594187888469647157398579826762695537(a)子圖像矩陣DCTxyuv00實(shí)例分析：

關(guān)于正交變換碼壓縮的說明：將被處理的數(shù)據(jù)按照某種變換規(guī)則映射到另一個域中處理。①如果將一幅圖像作為一個二維矩陣，則其正交變換計算量太大，通常將圖像分成8×8或16×16的小塊進(jìn)行處理。②正交變換沒有壓縮數(shù)據(jù)量，不改變信源的熵，③正交變換前后能量不變，只是重新分配。④變換前后信息量沒有丟失。典型的變換編碼系統(tǒng)中編碼器有四步：子圖像分割、變換、量化和編碼。先將整幅圖像分成n×n（n一般為8或16）的子圖像后分別處理：因?yàn)?1)小塊圖像的變換計算容易

(2)距離較遠(yuǎn)的像素之間的相關(guān)性比距離較近的像素之間的相關(guān)性小。壓縮并不是在變換步驟中取得，而是在量化變換系數(shù)和編碼時取得的。變換編碼的步驟一幅n×n圖像可表示成它的二維變換T(u,v)的函數(shù)。

(1)變換選擇許多圖像變換都可用于變換編碼,變換選擇取決于可允許的重建誤差和計算復(fù)雜性.由f(x,y)組成的n×n矩陣若定義一個截斷模板

F的截斷近似

M(u,v)消除求和貢獻(xiàn)最小的基礎(chǔ)圖像

整幅圖像的均方差為所有截除的變換系數(shù)的方差之和。因此，能把最多的信息集中到最少的系數(shù)上的變換所能產(chǎn)生的重建誤差最小。不同的變換，其信息集中能力不同。傅立葉變換、余弦變換、哈達(dá)瑪變換一維離散余弦變換：一維DCT變換實(shí)際上就是將信號f(x)分解成直流分量(u=0)、基波分量(u=1)和各次諧波分量(u>1)由于二維離散余弦變換的可分離性，二維DCT可以用一維DCT來實(shí)現(xiàn)

二維離散余弦變換：利用FFT的快速算法的FDCT算法余弦變換核實(shí)際上就是傅里葉變換核的實(shí)部。而變換計算中的乘法運(yùn)算就是f(x)與變換核的乘法運(yùn)算。一種自然的想法就是先對f(x)執(zhí)行FFT，然后對其取實(shí)部就可以了。利用代數(shù)分解的FDCT算法一維離散哈達(dá)瑪變換

一維離散哈達(dá)瑪反變換

離散哈達(dá)瑪變換二維離散哈達(dá)瑪變換

二維離散哈達(dá)瑪反變換

基于FFT變換的圖像壓縮技術(shù)基于DCT變換的圖像壓縮技術(shù)基于哈達(dá)瑪變換的圖像壓縮技術(shù)

FFT變換編碼效果

原始圖像壓縮比為2:1erms=0.0398

壓縮比為8:1erms=0.0474例erms均方根誤差DCT變換編碼效果原始圖像壓縮比為2:1erms=0.0359

壓縮比為8:1erms=0.0489

Hadamard變換編碼效果原始圖像壓縮比為2:1

erms=0.0362

壓縮比為8:1erms=0.0515

從erms值比較可知,DCT比FFT和HT有更強(qiáng)的信息集中能力.離散余弦變換在圖像壓縮中具有廣泛的應(yīng)用例如，在JPEG圖像壓縮算法中，首先將輸入圖像劃分為88的方塊，然后對每一個方塊執(zhí)行二維離散余弦變換，最后將變換得到的量化的DCT系數(shù)進(jìn)行編碼和傳送，形成壓縮后的圖像格式。在接受端，將量化的DCT系數(shù)進(jìn)行解碼，并對每個88方塊進(jìn)行二維IDCT，最后將操作完成后的塊組合成一幅完整的圖像。

在變換編碼中，首先要將圖像數(shù)據(jù)分割成子圖像，然后對子圖像數(shù)據(jù)塊實(shí)施某種變換，如DCT變換，那么子圖像尺寸取多少好呢？根據(jù)實(shí)踐證明子圖像尺寸取4×4、8×8、16×16適合作圖像的壓縮，這是因?yàn)椋?/p>

<1>如果子圖像尺寸取得太小，雖然計算速度快，實(shí)現(xiàn)簡單，但壓縮能力有一定的限制。

<2>如果子圖像尺寸取得太大，雖然去相關(guān)效果變好，因?yàn)橄驞FT、DCT等正弦型變換均具有漸近最佳性，但也漸趨飽和。若尺寸太大，由于圖像本身的相關(guān)性很小，反而使其壓縮效果不顯示，而且增加了計算的復(fù)雜性。

(2)子圖像尺寸選擇變換編碼的步驟這里考慮對子圖像經(jīng)過變換后，要截取的變換系數(shù)的數(shù)量和保留系數(shù)的精度。在大多數(shù)變換編碼中，選擇保留的系數(shù)辦法有以下二種：

<1>根據(jù)最大方差進(jìn)行選擇的，稱為區(qū)域編碼。

<2>根據(jù)最大值的量級選擇，稱為閾值編碼。而整個對變換后的子圖像的截取、量化和編碼過程稱為比特分配

(3)比特分配變換編碼的步驟典型的區(qū)域模板

區(qū)域編碼具有最大方差的變換系數(shù)攜帶著圖像大部分信息并在編碼處理的過程中應(yīng)該保留下來。最大方差的系數(shù)通常被定位在圖像變換的原點(diǎn)周圍。區(qū)域取樣處理可看成每個T(u,v)與相應(yīng)的區(qū)域模板中的元素相乘。對區(qū)域取樣過程中保留的系數(shù)必須進(jìn)行量化和編碼。因此，區(qū)域模板有時表示成對每個系數(shù)編碼的比特數(shù)。兩種分配方案：給系數(shù)分配相同的比特數(shù)給系數(shù)不均勻地分配幾個固定數(shù)目的比特數(shù)(a)(b)區(qū)域編碼的幾點(diǎn)說明：

因?yàn)槿搜蹖α炼刃盘柋葘ι钚盘柛舾校虼耸褂昧藘煞N量化表：亮度量化值和色差量化值。此外，由于人眼對低頻分量的圖像比對高頻分量的圖像更敏感，因此圖中的左上角的量化步距要比右下角的量化步距小。例：典型的閾值模板和系數(shù)排序序列閾值編碼(門限編碼)對任何子圖像,最大量級的變換系數(shù)對重構(gòu)子圖像的品質(zhì)具有最大的影響.因?yàn)椴煌訄D像的最大系數(shù)的位置是變化的,所以通常將m(u,v)T(u,v)的元素重新排列成一個一維行程編碼.有3種基本途徑對一幅變換后的子圖像進(jìn)行門限處理(即生成子圖像門限模板函數(shù))<1>對所有的子圖像使用單一的全局門限;

對不同圖像的壓縮等級不同.<2>對每幅圖像使用不同的門限;

對每幅子圖像丟棄相同數(shù)目的系數(shù),編碼率恒定.<3>門限隨子圖像中每個系數(shù)的位置函數(shù)的變化而變化.

編碼率變化,但是可以將門限處理和量化過程結(jié)合起來.是取閾值和量化近似，Z是變換的歸一化矩陣

使用下式代替m(u,v)T(u,v),

將取閾值和量化結(jié)合起來(a)一條門限編碼量化曲線對Z(u,v)賦予某個常數(shù)c(b)JPEG編碼標(biāo)準(zhǔn)中的DCT量化步長矩陣Z

使用8×8DCT系數(shù)的12.5%門限編碼區(qū)域編碼利用DCT標(biāo)準(zhǔn)化陣列的壓縮34:167:18:1誤差預(yù)測編碼的基本概念預(yù)測編碼（Prediction

Coding）是根據(jù)某一種模型，利用以前的（已收到）一個或幾個樣值，對當(dāng)前的（正在接收的）樣本值進(jìn)行預(yù)測，將樣本實(shí)際值和預(yù)測值之差進(jìn)行編碼。如果模型足夠好，圖像樣本時間上相關(guān)性很強(qiáng)，一定可以獲得較高的壓縮比。具體來說，從相鄰像素之間有很強(qiáng)的相關(guān)性特點(diǎn)考慮，比如當(dāng)前像素的灰度或顏色信號，數(shù)值上與其相鄰像素總是比較接近，除非處于邊界狀態(tài)。那么，當(dāng)前像素的灰度或顏色信號的數(shù)值，可用前面已出現(xiàn)的像素的值，進(jìn)行預(yù)測（估計），得到一個預(yù)測值（估計值），將實(shí)際值與預(yù)測值求差，對這個差值信號進(jìn)行編碼、傳送，這種編碼方法稱為預(yù)測編碼方法。預(yù)測編碼2023/2/6統(tǒng)計編碼126就是根據(jù)過去的信號樣值預(yù)測下一個樣值，并僅把預(yù)測值與現(xiàn)實(shí)的樣值之差（預(yù)測誤差）加以量化、編碼以后進(jìn)行傳輸?shù)姆绞剑缦聢D所示，在接收端，經(jīng)過和發(fā)信端的預(yù)測完全相同的操作，可以得到量化的原信號，然后再通過低通濾波便可恢復(fù)與原信號近似的波形。預(yù)測編碼的原理預(yù)測編碼的基本思想

建立一個數(shù)學(xué)模型

利用以往的樣本數(shù)據(jù)對新樣本值進(jìn)行預(yù)測

將預(yù)測值與實(shí)際值相減

對其差值進(jìn)行編碼，這時差值很少，可以減少編碼碼位預(yù)測編碼的分類預(yù)測編碼：在均方誤差最小的準(zhǔn)則下，使其誤差最小的方法。

線性預(yù)測：利用線性方程計算預(yù)測值的編碼方法。線性預(yù)測編碼方法，也稱差值脈沖編碼調(diào)制（Differention

Pulse

Code

Modulation，DPCM）非線性預(yù)測：利用非線性方程計算預(yù)測值的編碼方法。。

幀內(nèi)預(yù)測編碼：根據(jù)同一幀樣本進(jìn)行預(yù)測的編碼方法。幀間預(yù)測編碼：根據(jù)不同幀樣本進(jìn)行預(yù)測的編碼方法。

自適應(yīng)預(yù)測編碼（ADPCM）：預(yù)測器和量化器參數(shù)按圖像局部特性進(jìn)行調(diào)整的編碼方法。條件補(bǔ)充幀間預(yù)測編碼：在幀間預(yù)測編碼中，若幀間對應(yīng)像素樣本值超過某一閾值就保留，否則不傳或不存，恢復(fù)時就用上一幀對應(yīng)像素樣本值來代替，稱為條件補(bǔ)充幀間預(yù)測編碼。

運(yùn)動補(bǔ)償預(yù)測編碼：在活動圖像預(yù)測編碼中，根據(jù)畫面運(yùn)動情況，對圖像加以補(bǔ)償再進(jìn)行幀間預(yù)測的方法稱為運(yùn)動補(bǔ)償預(yù)測編碼方法。DPCM的基本原理對于具有M種取值的符號序列{xk},其第L個符號的熵滿足:知道了前面的符號xk(k<L),再猜后續(xù)符號xL,則知道得越多,熵越小。意味著該信源的不確定度減小,數(shù)碼率自然降低?；A(chǔ)理論：發(fā)展歷史1952年，Bell實(shí)驗(yàn)室的B.M.Oliver等人開始線性預(yù)測編碼理論研究。同年，該實(shí)驗(yàn)室的C.C.Culter取得了DPCM(DifferentialPulseCodeModulation,差分脈沖編碼調(diào)制)系統(tǒng)的專利，奠定了真正實(shí)用的預(yù)測編碼系統(tǒng)的基礎(chǔ)。預(yù)測編碼技術(shù)：從過去的符號樣本來預(yù)測下一個符號樣本的值。直觀理解：根據(jù)：認(rèn)為在信源符號之間存在相關(guān)性。如果符號的預(yù)測值與符號的實(shí)際值比較接近，它們之間的差值幅度的變化就比原始信源符號幅度值的變化小，因此量化這種差值信號時就可以用比較少的位數(shù)來表示差值。DPCM的基礎(chǔ)—對預(yù)測的樣本值與原始的樣本值之差進(jìn)行編碼。DPCM系統(tǒng)DPCM系統(tǒng)原理框圖量化器預(yù)測器編碼器xk-ekSk信道解碼器預(yù)測器接收端發(fā)送端發(fā)送端

先發(fā)送一個起始值x0;接著就只發(fā)送預(yù)測誤差值接收端接收到量化后的誤差與本地算出的預(yù)測值相加,得到恢復(fù)信號;式中線性預(yù)測：式中表示的時序在之前，為因果性預(yù)測，否則為非因果性預(yù)測。如果沒有傳輸誤碼，預(yù)測編碼系統(tǒng)的誤差為：這正是發(fā)送端量化器造成的量化誤差。即整個預(yù)測編碼系統(tǒng)的失真完全來自量化器。對于xk已經(jīng)是數(shù)字信號，去掉量化器，qk

=0：可用于“信息保持型”(Lossless)編碼；如果qk≠0:可用于“非信息保持型”(Lossy)編碼。

①算法簡單、速度快、易于硬件實(shí)現(xiàn)。②編碼壓縮比不太高,DPCM一般壓縮到2～4bit/s。③誤碼易于擴(kuò)散，抗干擾能力差。預(yù)測編碼方法的特點(diǎn)分形編碼

分形編碼分形是20世紀(jì)70年代出現(xiàn)的一門非線性學(xué)科。分形一詞最早由數(shù)學(xué)家Mandelbrot提出，用以描述這樣的幾何外形，它與歐幾里德外形相反，處處無規(guī)則可言，但在各種尺度上都有同樣程度的不規(guī)則性。

20世紀(jì)80年代中期，Barnsley提出了迭代函數(shù)系統(tǒng)(IFS)的分形圖像壓縮編碼方法，為圖像編碼提供了一個全新的思路。在此之后，他的學(xué)生Jacquin又提出分塊的迭代變換算法理論，為利用計算機(jī)自動進(jìn)行分形壓縮奠定了基礎(chǔ)。從分形的角度，許多視覺上感覺非常復(fù)雜的圖形其信息量并不大，可以用算法和程序集來表示，在借助計算機(jī)可以顯示其結(jié)合形態(tài)，這就是可以用分形的方法進(jìn)行圖像壓縮的原因。對于分形圖像壓縮，它是一個逆問題，即把欲編碼的圖像當(dāng)作一組壓縮仿射變換的迭代極限，假如能夠找到這些壓縮仿射變換的參數(shù)，就可以重建原始圖像。為此尋找一個壓縮仿射變換，使它對原圖像進(jìn)行壓縮仿射變換后的結(jié)果能與原圖像的一部分吻合。如果原圖像各個部分均可被對原圖的不同壓縮仿射變換的結(jié)果所覆蓋，則就找到了一個將圖像映射成自身的變換。分形編碼由于其計算量的繁復(fù)、龐大，在實(shí)際應(yīng)用中受到了限制。圖像標(biāo)準(zhǔn)的制定：

ISO和CCITT（國際電報電話咨詢委員會）聯(lián)合制定標(biāo)準(zhǔn)的類型：連續(xù)圖像壓縮標(biāo)準(zhǔn)：靜止幀黑白、彩色壓縮：(1)面向靜止的單幅圖像－JPEG連續(xù)幀黑白、彩色壓縮：(2)面向連續(xù)的視頻影像－MPEG

第四節(jié)圖像壓縮編碼標(biāo)準(zhǔn)

JPEG標(biāo)準(zhǔn)簡述

JPEG壓縮流程

JPEG壓縮算法的實(shí)現(xiàn)

JPEG壓縮舉例

靜止圖像壓縮編碼標(biāo)準(zhǔn)－JPEGJPEG標(biāo)準(zhǔn)簡述

由ISO/IEC與CCITT聯(lián)合發(fā)起的聯(lián)合圖像專家組，在過去十幾年圖像編碼研究成果的基礎(chǔ)上于20世紀(jì)90年代初制定了靜止圖像(包括8bit/像素的灰度圖像與24bit/像素的彩色圖像)的編碼標(biāo)準(zhǔn)。

JPEG標(biāo)準(zhǔn)在較低的計算復(fù)雜度下，能提供較高的壓縮比與保真度。在視覺效果不受到嚴(yán)重?fù)p失的前提下，算法可以達(dá)到15到20的壓縮比。如果在圖像質(zhì)量上稍微犧牲一點(diǎn)的話，可以達(dá)到40:1或更高的壓縮比。JPEG定義了一個基本系統(tǒng)，一個符合JPEG標(biāo)準(zhǔn)的編解碼器至少要滿足基本系統(tǒng)的技術(shù)指標(biāo)。JPEG基本系統(tǒng)其核