1、第三講 多媒體數(shù)據(jù)壓縮的基本技術(shù)（1）,Outline 多媒體數(shù)據(jù)壓縮的理論依據(jù) 量化 標(biāo)量量化 矢量量化 預(yù)測(cè)編碼 差分脈沖編碼調(diào)制 （DPCM） 自適應(yīng)差分脈碼調(diào)制 （ADPCM）,壓縮的必要性,AUDIO,VIDEO,數(shù)據(jù)壓縮可分為兩類： 無(wú)損壓縮 有損壓縮 無(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á)信息的理解。,多媒體數(shù)據(jù)壓縮的理論依據(jù),信息論 現(xiàn)在科學(xué)領(lǐng)域中的一個(gè)重要分支 Shannon所創(chuàng)立的信息論對(duì)數(shù)據(jù)壓縮有極為重要的指導(dǎo)意義 給出了數(shù)據(jù)壓縮的理論

2、極限 指明了數(shù)據(jù)壓縮的技術(shù)途徑 為通信技術(shù)的發(fā)展奠定了理論基礎(chǔ),兩個(gè)基本概念：熵和信源熵,Entropy(熵)的概念 ： (1) 熵是信息量的度量方法，它表示某一事件出現(xiàn)的消息越多，事件發(fā)生的可能性就越小，數(shù)學(xué)上就是概率越小。 (2) 某個(gè)事件的信息量用 Ii = -log2Pi 表示 ， 其中Pi為第 i 個(gè)事件的概率,信源熵的定義,其中 P i 是符號(hào) S i 在 S 中出現(xiàn)的概率，,表示包含在 Si 的信息量，也就是編碼 Si 所需要的位數(shù),例如，一幅用256級(jí)灰度表示的圖像，如果每一個(gè)象素點(diǎn)灰度的概率均為 Pi = 1/256 ，編碼每一個(gè)象素點(diǎn)就需要8位。,無(wú)損編碼定理,離散信源X無(wú)

3、損編碼所能達(dá)到的最小速率不能低于該信源的信源熵，即：,信源編碼定理（有損編碼定理）,對(duì)于給定的信源，在允許一定的失真D情況下，存在一率失真函數(shù)R(D)，當(dāng)編碼速率R不低于R(D)時(shí)，編碼失真能夠不大于D。 R(D)一般不容易計(jì)算 該定理沒(méi)有給出編碼方法,熵編碼（保熵編碼 、無(wú)損壓縮 ）,定長(zhǎng)編碼 香農(nóng)-范諾(Shannon- Fano)編碼 霍夫曼編碼 算術(shù)編碼 Ziv-Lempel編碼（70年代末J.Ziv和A.Lempel） 行程編碼（Run Length Encoding，RLE）,舉例說(shuō)明：,有一幅40個(gè)象素組成的灰度圖像，灰度共有5級(jí)，分別用符號(hào)A、B、C、D和E表示，40個(gè)象素中出

4、現(xiàn)灰度A的象素?cái)?shù)有15個(gè)，出現(xiàn)灰度B的象素?cái)?shù)有7個(gè)，出現(xiàn)灰度C的象素?cái)?shù)有7個(gè)等等，如右邊所示。 如果用3個(gè)位表示5個(gè)等級(jí)的灰度值（定長(zhǎng)編碼），也就是每個(gè)象素用3位表示，編碼這幅圖像總共需要120位。,就是說(shuō)每個(gè)符號(hào)用2.196位表示，40個(gè)象素需用87.84位,按照信息論理論，這幅圖像的熵為:,香農(nóng)-范諾(Shannon- Fano) 編碼,按照符號(hào)出現(xiàn)的頻度或概率排序，然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù)。 Shannon(1948年)和Fano(1949年)最早闡述和實(shí)現(xiàn)這種編碼，因此被稱為香農(nóng)-范諾(Shannon- Fano)算法。這種方法采用從上到下的方法進(jìn)行編碼

5、。,香農(nóng)-范諾編碼舉例,上例按照香農(nóng)范諾算法的編碼結(jié)果,編碼后的位數(shù) 30 14 14 18 15 91 （位）,霍夫曼編碼,霍夫曼(Huffman)在1952年提出了一種編碼方法，是從下到上的編碼方法。 基本思想是：對(duì)于出現(xiàn)概率較大的符號(hào)取較短的碼長(zhǎng)，而對(duì)概率較小的符號(hào)取較長(zhǎng)的碼長(zhǎng)。 是一種變長(zhǎng)碼 ，霍夫曼碼通常被稱為最優(yōu)碼,仍以上一個(gè)例子說(shuō)明它的編碼步驟：,1.初始化，根據(jù)符號(hào)概率的大小按由大到小順序?qū)Ψ?hào)進(jìn)行排序 2. 把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)，D和E組成節(jié)點(diǎn)P1 3.重復(fù)步驟2，得到節(jié)點(diǎn)P2、P3和P4，形成一棵“樹”，其中的P4稱為根節(jié)點(diǎn) 4.從根節(jié)點(diǎn)P4開始到相應(yīng)于每個(gè)符號(hào)

6、的“樹葉”，從上到下標(biāo)上“0”(上枝)或者“1”(下枝)，至于哪個(gè)為“1”哪個(gè)為“0”則無(wú)關(guān)緊要，最后的結(jié)果僅僅是分配的代碼不同，而代碼的平均長(zhǎng)度是相同的。 5.從根節(jié)點(diǎn)P4開始順著樹枝到每個(gè)葉子分別寫出每個(gè)符號(hào)的代碼,上例按照霍夫曼編碼的結(jié)果（總共90位 ）,霍夫曼碼的碼長(zhǎng)雖然是可變的，但卻不需要另外附加同步代碼。例如，碼串中的第1位為0，那末肯定是符號(hào)A，因?yàn)楸硎酒渌?hào)的代碼沒(méi)有一個(gè)是以0開始的，因此下一位就表示下一個(gè)符號(hào)代碼的第1位。同樣，如果出現(xiàn)“110”，那么它就代表符號(hào)D。如果事先編寫出一本解釋各種代碼意義的“詞典”，即碼簿，那么就可以根據(jù)碼簿一個(gè)碼一個(gè)碼地依次進(jìn)行譯碼。,采用霍

7、夫曼編碼時(shí)需要注意的問(wèn)題：,霍夫曼碼沒(méi)有錯(cuò)誤保護(hù)功能，在譯碼時(shí)，如果碼串中沒(méi)有錯(cuò)誤，那么就能一個(gè)接一個(gè)地正確譯出代碼。但如果碼串中有錯(cuò)誤，哪怕是1位出現(xiàn)錯(cuò)誤，不但這個(gè)碼本身譯錯(cuò)，更糟糕的是一錯(cuò)一大串，全亂了套，這種現(xiàn)象稱為錯(cuò)誤傳播(error propagation)。計(jì)算機(jī)對(duì)這種錯(cuò)誤是無(wú)能為力的，說(shuō)不出錯(cuò)在哪里，更談不上去糾正它。 霍夫曼碼是可變長(zhǎng)度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲(chǔ)代碼之前加以考慮 。,量化,量化是將具有連續(xù)幅度值的輸入信號(hào)轉(zhuǎn)換到只有有限個(gè)幅度值的輸出信號(hào)的過(guò)程。 標(biāo)量量化 均勻量化 非均勻量化 對(duì)數(shù)量化 自適應(yīng)量化 矢量量化,標(biāo)量量化

8、, 標(biāo)量量化對(duì)信號(hào)的每個(gè)樣點(diǎn)分別量化 連續(xù)信號(hào)的量化過(guò)程是將給定的連續(xù)信號(hào)幅度值x變成 有限個(gè)離散幅度值集合中的一個(gè)值y的過(guò)程 數(shù)學(xué)描述： 對(duì)取值連續(xù)的無(wú)限集合x，通過(guò)變換Q映射到一個(gè)只有L個(gè)離散值集合yk,k=1,2,L上,量化器 Q 輸入 x 落入:,時(shí), 量化器輸出為 yk , 即:,其中 xk 稱作分層電平或判決電平，yk 稱作量化電平或重建電平。共有L1個(gè)分層電平和L個(gè)量化電平，要用 R 比特表示。 其中：,輸入輸出特性曲線（量化器量化特性）,量化誤差（量化噪聲）,對(duì)于確定信號(hào)x，q也是確定信號(hào)；對(duì)于語(yǔ)音、圖象等隨機(jī)信號(hào)，q也是隨機(jī)信號(hào)。 設(shè)x的概率分布密度函數(shù)是px(x)，q的概率

9、分布密度為pq(x)，則q的均方值為：,量化誤差的方差同 px(x) 、xk、yk及L都有關(guān)。那么問(wèn)題就轉(zhuǎn)化成為在給定px(x)和L的前提下，如何確定xk、yk，使量化誤差功率（方差）最??？,1均勻量化,各量化區(qū)間相等,設(shè)量化器量化范圍是-V到+V，則,量化電平取各量化區(qū)間中點(diǎn),在這里我們只討論輸入信號(hào)幅度受限情況：,量化誤差:,當(dāng)L足夠大,即足夠小，近似有,為均勻分布，類似白噪聲，也稱顆粒噪聲,只同L，V有關(guān)，同信號(hào)幅度概率分布及輸入功率都無(wú)關(guān), 定義：,用分貝表示：, 量化器每增加一個(gè)比特，SNR提高約6db, SNR與2x有關(guān)，即與信號(hào)大小和幅度概率分布有關(guān), 臨界過(guò)載時(shí)SNR達(dá)最大值,

10、均勻分布信號(hào)：,正弦信號(hào)：臨界過(guò)載時(shí), 語(yǔ)音為非平穩(wěn)隨機(jī)信號(hào)，電話語(yǔ)音電平變化超過(guò)40db。對(duì)小信號(hào)電平輸入，SNR應(yīng)保證約2030db，即最大SNR需6070db，均勻量化器要1113比特。,2非均勻量化, 均勻量化簡(jiǎn)單、易實(shí)現(xiàn)，但量化器特性曲線同輸入信號(hào)幅度概率密度函數(shù)不匹配，采用非均勻量化可解決此問(wèn)題，使量化效果更好。 給定信號(hào)幅度概率分布密度，求解最佳分層電平和最佳量化電平。 兩種求解方法：迭代求解，大R值近似求解。,（1）最佳非均勻量化器的迭代求解方法,Lloyd 和Max提出，通常稱勞依得-麥克思(Lloyd-Max)量化器，適用于L為任意值 由,為使上式達(dá)最小，分別對(duì)各分層電平和

11、量化電平求偏導(dǎo)，并令其為零：,將量化噪聲公式代入上兩式可以得到,有：,以及：,因此有：, 最佳分層電平應(yīng)取兩個(gè)相鄰重建電平中點(diǎn) 最佳重建電平處于量化間隔概率質(zhì)心上 一般情況下(L3)，求解需要使用迭代方法，其步驟如下所述： A 選初始值y1，由式（2）求出x2； B 根據(jù)y1，x2由式（1）求出y2； C 根據(jù)y2,x2，由式（2）求出x3。 重復(fù)以上步驟，求出x2,x3,xL和y1,y2,yL。然后將xL及xL+1= 代入（2）式右端求出值，看此值是否很接近已求出的yL。若不接近，則根據(jù)偏差調(diào)整y1的初值，重復(fù)以上過(guò)程，直到偏差滿足給定的容差。,（2）大R值非均勻量化器近似求解,對(duì)于大R值，

12、L足夠大，可認(rèn)為在每個(gè)量化間隔中，輸入信號(hào)幅度概率密度近似為固定值,在該區(qū)間內(nèi)，信號(hào)出現(xiàn)的概率為：,并有,當(dāng)L值足夠大，可以選V值較大，使,的概率很小，過(guò)載噪聲功率可以忽略不計(jì)。,這時(shí)量化噪聲方差為：,最佳量化電平應(yīng)滿足：,將（4）式代入上式，得：, 最佳量化電平處于相鄰兩個(gè)分層電平中心，這是假定每一分層間隔內(nèi)px(x)為均勻分布的必然結(jié)果。將上式代入（4）式可得：, 總量化噪聲是各量化間隔產(chǎn)生的量化噪聲概率加權(quán)之和, 2q 與分層電平有關(guān)，需進(jìn)行優(yōu)化。,將式（3）代入上式，得：,其中:,由于:,因此：,式中 K 為常數(shù)。以上式為約束條件，利用拉格朗日乘子法，有：,求出,代入式（5），解出可得

13、到：, 上式說(shuō)明各量化間隔內(nèi)產(chǎn)生的量化噪聲功率相等時(shí)，總量化噪聲功率最小。 信號(hào)概率密度大的區(qū)間，量化間隔應(yīng)該小些；反之，信號(hào)概率密度小的區(qū)間，量化間隔應(yīng)該大些。 可通過(guò)上式迭代求出各量化間隔，進(jìn)而求出各分層電平。,通過(guò)引入壓縮特性曲線,可以導(dǎo)出更方便的求解公式。,采用非線性壓縮擴(kuò)張的非均勻量器非線性壓縮示意圖,將輸入非均勻分層映射成均勻分層，并滿足：,當(dāng)L很大時(shí)：,有：,利用式（3），得：,3對(duì)數(shù)量化,對(duì)數(shù)量化最大信噪比雖然沒(méi)有最佳量化器的高，但動(dòng)態(tài)范圍大，可直接用于語(yǔ)音信號(hào)的量化。 理想對(duì)數(shù)量化壓縮特性為：,與輸入信號(hào)概率分布無(wú)關(guān)。量化噪聲方差為：,與輸入信號(hào)方差成正比，這時(shí),與輸入信號(hào)的

14、方差無(wú)關(guān)。, 理想對(duì)數(shù)壓縮無(wú)法實(shí)現(xiàn)，x0時(shí)c(x)-，將對(duì)數(shù)量化特性在x0的小信號(hào)區(qū)域進(jìn)行修正。 G.711采用A律和律兩種壓縮特性:,式中A取87.56，取255。,實(shí)際實(shí)現(xiàn)時(shí)壓縮曲線分別用13段折線和15段折線近似。,4自適應(yīng)量化,自適應(yīng)量化根據(jù)輸入信號(hào)短時(shí)方差，對(duì)量階大小進(jìn)行調(diào)整，使量化器與輸入信號(hào)電平匹配，進(jìn)一步改善量化效果。 根據(jù)對(duì)短時(shí)方差估值方法來(lái)分，自適應(yīng)量化可分為前向自適應(yīng)量化（AQF）和后向自適應(yīng)量化（AQB）。 AQF估值不受量化噪聲影響，延時(shí)大，要傳邊信息。 AQB估值受量化噪聲影響，延時(shí)小，不要傳邊信息。 采用自適應(yīng)量化明顯提高分段信噪比。,矢量量化,矢量量化是先將 K

15、個(gè)（K2）個(gè)采樣值形成 K維空間 RK 中的一個(gè)矢量，然后將這個(gè)矢量一次進(jìn)行量化。它可以大大降低數(shù)碼率。 矢量量化總是優(yōu)于標(biāo)量量化的。這是因?yàn)槭噶苛炕行У貞?yīng)用了矢量中各分量間的四種相互關(guān)聯(lián)的性質(zhì)：線性依賴性，非線性依賴性，概率函數(shù)的型狀以及矢量數(shù)。, 將NK個(gè)信號(hào)采樣組成的信源序列 xj中每 K個(gè)為一組分為 N個(gè)隨機(jī)矢量，構(gòu)成信源空間 XX1,X2,XN(X在K維歐氏空間RK中),其中第 J個(gè)矢量可記為：,再把RK無(wú)遺漏地劃分成 L = 2M個(gè)互不相交的子空間R1，R2，。，RL，即滿足:, 在每個(gè)子空間Ri中找一個(gè)代表矢量Yi，令恢復(fù)矢量集,Y 也叫輸出空間、碼本或碼書(Code Book

16、)，Yi 稱為碼矢(Code Vector)或碼字(Code Word)，Y內(nèi)矢量的數(shù)目L，則叫做碼本長(zhǎng)度或碼本尺寸。,當(dāng)矢量量化器輸入任意矢量,它首先判斷Xj屬于那個(gè)子空間，然后輸出該子空間Ri的代表矢量,矢量量化過(guò)程就是用Yi代表Xj , 即,式中Q為量化函數(shù)。, VQ編譯碼的全過(guò)程完成一個(gè)從 K 維歐氏空間RK到RK空間中有限子集的映射：,發(fā)端完成映射,收端完成映射,矢量量化Q則是C和D的結(jié)合,編碼:,解碼:,矢量量化示意圖, 矢量量化的比特率：,log2L:每個(gè)矢量所需要的編碼比特?cái)?shù) K:每個(gè)矢量所包含的信號(hào)樣點(diǎn)數(shù) K=1時(shí), VQ退化成標(biāo)量量化（SQ）,矢量量化的特點(diǎn)：, 壓縮能力強(qiáng)

17、 一定產(chǎn)生失真, 但失真易控制：X的分類越細(xì)，失真越小 可以實(shí)現(xiàn)每一維非整數(shù)比特量化 計(jì)算量大：每輸入一個(gè)Xj，都要和L 個(gè)Yi逐一比較，搜索出畸變最小的。Xj和Yi都是K維矢量，故矢量搜索工作的計(jì)算量大。 VQ是定長(zhǎng)碼,預(yù)測(cè)編碼,預(yù)測(cè)編碼基本思想：去處相鄰樣本之間的冗余度。 這里說(shuō)的“相鄰”，包括“空間上的相鄰”和“時(shí)間上的相鄰”。例如，空間上的相鄰指的是同一幀圖像內(nèi)上、下、左、右的像素之間；時(shí)間上的相鄰指的是前幀、后幀圖像中對(duì)應(yīng)于同一空間位置上的像素。 內(nèi)容： 差分脈沖編碼調(diào)制 （DPCM） 自適應(yīng)脈沖編碼調(diào)制 （APCM） 自適應(yīng)差分脈碼調(diào)制 （ADPCM）,差分脈沖編碼調(diào)制（DPCM）

18、,差分脈沖編碼調(diào)制DPCM(differential pulse code modulation)是利用樣本與樣本之間存在的信息冗余度來(lái)進(jìn)行編碼的一種數(shù)據(jù)壓縮技術(shù)。 差分脈沖編碼調(diào)制的思想是，根據(jù)過(guò)去的樣本去估算(estimate)下一個(gè)樣本信號(hào)的幅度大小，這個(gè)值稱為預(yù)測(cè)值，然后對(duì)實(shí)際信號(hào)值與預(yù)測(cè)值之差進(jìn)行量化編碼，從而就減少了表示每個(gè)樣本信號(hào)的位數(shù)。 DPCM是對(duì)實(shí)際信號(hào)值與預(yù)測(cè)值之差進(jìn)行量化編碼，存儲(chǔ)或者傳送的是差值而不是幅度絕對(duì)值，這就降低了傳送或存儲(chǔ)的數(shù)據(jù)量。 它能適應(yīng)大范圍變化的輸入信號(hào)。,采用全極點(diǎn)預(yù)測(cè)器的DPCM原理如圖所示,差值信號(hào)(余量信號(hào)、殘差信號(hào)、預(yù)測(cè)誤差信號(hào))為：,量化

19、后:,重建信號(hào):,重建信號(hào)中的誤差信號(hào)就是差值信號(hào)量化產(chǎn)生的量化誤差信號(hào),設(shè),的方差分別為,那么DPCM的信噪比為：,式中,為預(yù)測(cè)增益，,是差值信號(hào)量化信噪比。,同PCM相比，DPCM通過(guò)預(yù)測(cè)使量化信噪比增加了10lgGp,（1）全極點(diǎn)預(yù)測(cè)器,Sp(n)由n時(shí)刻以前的N個(gè)重建語(yǔ)音樣點(diǎn)線性組合得，,式中i ，(i=1,N)稱為線性預(yù)測(cè)系數(shù)。重建信號(hào)可寫成:,兩邊取Z變換，有:,式中:,稱做重建濾波器，是一個(gè)全極點(diǎn)濾波器， 其系數(shù) i可用語(yǔ)音信號(hào)的長(zhǎng)時(shí)相關(guān)系數(shù)求出。 定義系數(shù)矢量:,相關(guān)系數(shù)矢量,語(yǔ)音相關(guān)系數(shù)矩陣:,由線性預(yù)測(cè)理論，最佳線性預(yù)測(cè)系數(shù)矢量為：,可得最小預(yù)測(cè)誤差為:,以上表明預(yù)測(cè)誤差的

20、平均功率比原始信號(hào)的功率要小 在相同的均方量化誤差下，要求較小的量化級(jí)數(shù)， 傳輸上的數(shù)據(jù)率要低。,可證明，當(dāng)預(yù)測(cè)器階數(shù) N時(shí)，極限最小預(yù)測(cè)誤差為：,式中,是輸入信號(hào)的功率譜密度。,可得極限最大預(yù)測(cè)增益為：,其中,定義為輸入信號(hào)的譜平坦度，,反映了信號(hào)可預(yù)測(cè)程度?？梢钥闯觯?DPCM系統(tǒng)在極限情況下，產(chǎn)生的最小量化噪聲為：,所能達(dá)到的極限最大信噪比為：,（2）其它類型預(yù)測(cè)器,DPCM系統(tǒng)也可以用全零點(diǎn)預(yù)測(cè)器或零極點(diǎn)混合器。, 全零點(diǎn)預(yù)測(cè)器：預(yù)測(cè)信號(hào)由 n 時(shí)刻以前的M個(gè)量化 后的差值信號(hào)樣點(diǎn)線性組合得到，即 ：,重建信號(hào)為：,兩邊取Z變換，有:,重建濾波器是一個(gè)全零點(diǎn)濾波器。, 對(duì)于零極點(diǎn)混合預(yù)測(cè)器DPCM，有：,以及：,其z變換表達(dá)式為：,重建濾波器為：,是一個(gè)零點(diǎn)極點(diǎn)混合濾波器。,自適應(yīng)脈沖編碼調(diào)制(APCM),自適應(yīng)脈沖編碼調(diào)制(adaptive pulse code modulation，APCM)是根據(jù)輸入信號(hào)幅度大小來(lái)改變量化階大小的一種波形編碼技術(shù)。 這種自適應(yīng)可以是瞬時(shí)自適應(yīng)