第4章 多媒體數(shù)據(jù)壓縮技術(shù)課件

多媒體數(shù)據(jù)壓縮技術(shù)已成為當(dāng)今數(shù)字通信、廣播、存儲(chǔ)和多媒體娛樂中的一項(xiàng)關(guān)鍵的共性技術(shù)。

4.1多媒體數(shù)據(jù)壓縮概述

4.2數(shù)據(jù)壓縮的技術(shù)基礎(chǔ)

4.3常用的無損數(shù)據(jù)壓縮方法

4.4常用的有損數(shù)據(jù)壓縮方法

4.5數(shù)據(jù)壓縮國際標(biāo)準(zhǔn)4.1多媒體數(shù)據(jù)壓縮概述4.1.1多媒體數(shù)據(jù)壓縮的必要性⑴原始采樣的媒體數(shù)據(jù)量巨大⑵有效利用存儲(chǔ)器存儲(chǔ)容量⑶提高通信線路的傳輸效率⑷消除計(jì)算機(jī)系統(tǒng)處理視頻I/O瓶頸4.1.2多媒體數(shù)據(jù)壓縮的可能性常見的圖像數(shù)據(jù)冗余種類：⑴空間冗余：靜態(tài)圖像中存在的最主要的一種數(shù)據(jù)冗余。⑵時(shí)間冗余：運(yùn)動(dòng)圖像中經(jīng)常包含的冗余。⑶結(jié)構(gòu)冗余：在某些場(chǎng)景中，存在著明顯的圖像分布模式，稱作結(jié)構(gòu)。圖像中重復(fù)出現(xiàn)或相近的紋理結(jié)構(gòu)，結(jié)構(gòu)可以通過特定的過程來生成。⑷知識(shí)冗余：這類規(guī)律性的結(jié)構(gòu)可以由經(jīng)驗(yàn)知識(shí)和背景知識(shí)得到。⑸視覺冗余：人眼對(duì)亮度變化敏感，對(duì)色度的變化相對(duì)不敏感；在高亮度區(qū)，人眼對(duì)亮度變化敏感度下降；對(duì)物體邊緣敏感，內(nèi)部區(qū)域相對(duì)不敏感；對(duì)整體結(jié)構(gòu)敏感，而對(duì)內(nèi)部細(xì)節(jié)相對(duì)不敏感。⑹圖像區(qū)域的相同性冗余：圖像中的兩個(gè)或者多個(gè)區(qū)域所對(duì)應(yīng)的所有像素值相同或者相近，從而產(chǎn)生數(shù)據(jù)重復(fù)性存儲(chǔ)。⑺紋理的統(tǒng)計(jì)冗余：有些圖像紋理盡管不嚴(yán)格服從某個(gè)分布規(guī)律，但是在統(tǒng)計(jì)意義上服從這種規(guī)律。利用這種性質(zhì)可以減少表示圖像的數(shù)據(jù)量，所以被稱為紋理的統(tǒng)計(jì)冗余。4.1.3多媒體數(shù)據(jù)壓縮的原理1.圖像壓縮系統(tǒng)的組成由三部分組成：變換器、量化器和編碼器。2.圖像壓縮說明視頻壓縮與語音相比，語音的數(shù)據(jù)量較小，且基本壓縮方法已經(jīng)成熟，目前的數(shù)據(jù)壓縮研究主要集中于圖像和視頻信號(hào)的壓縮方面。壓縮處理過程有兩個(gè)過程，編碼過程是將原始數(shù)據(jù)經(jīng)過編碼進(jìn)行壓縮，以便存儲(chǔ)與傳輸；解碼過程是對(duì)編碼數(shù)據(jù)進(jìn)行解碼，還原為可以使用的數(shù)據(jù)。3.與壓縮相關(guān)的指標(biāo)衡量一種數(shù)據(jù)壓縮技術(shù)的好壞有四個(gè)重要的指標(biāo)：⑴壓縮比大：即壓縮前后所需要的信息存儲(chǔ)量之比要大。⑵算法簡(jiǎn)單：實(shí)現(xiàn)壓縮的算法簡(jiǎn)單，壓縮、解壓速度快，盡可能地做到實(shí)時(shí)壓縮解壓。⑶恢復(fù)效果好：恢復(fù)效果好，要盡可能地恢復(fù)原始數(shù)據(jù)。⑷壓縮能否用硬件實(shí)現(xiàn)。4.1.4數(shù)據(jù)壓縮方法的分類⑴冗余壓縮法也稱無損壓縮法，是指使用壓縮后的數(shù)據(jù)可以解壓縮，且解壓之后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同。它利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為2:1到5:1。⑵熵壓縮法也稱有損壓縮法，有失真壓縮，是指使用壓縮后的數(shù)據(jù)進(jìn)行解壓縮，解壓之后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不會(huì)讓人對(duì)原始資料表達(dá)的信息造成誤解。⑶熵壓縮法與冗余壓縮法的比較在圖像壓縮系統(tǒng)組成中，變換和編碼是無損耗的，而量化是有損耗的。無損壓縮方法僅利用了統(tǒng)計(jì)冗余，而沒有利用量化器。有損壓縮方法既利用了統(tǒng)計(jì)冗余又采用了量化器，利用了心理視覺冗余。根據(jù)壓縮方法的原理，可將其具體劃分為以下幾種：⑴量化與向量量化編碼⑵預(yù)測(cè)編碼⑶變換編碼⑷信息熵編碼⑸混合編碼4.2數(shù)據(jù)壓縮的技術(shù)基礎(chǔ)4.2.1熵的概念表示一條信息中真正需要編碼的信息量，即數(shù)據(jù)壓縮的理論極限。對(duì)于任何一種無損數(shù)據(jù)壓縮，最終的數(shù)據(jù)量一定大于信息熵，數(shù)據(jù)量越接近于熵值，說明其壓縮效果越好。信息熵如何計(jì)算：在計(jì)算機(jī)內(nèi)部是用二進(jìn)制來表示數(shù)據(jù)的，現(xiàn)在要用0和1組成的二進(jìn)制數(shù)碼來為含有n個(gè)符號(hào)的某條信息編碼，假設(shè)符號(hào)Fn在整條信息中重復(fù)出現(xiàn)的概率為Pn，則該符號(hào)的熵En也即表示該符號(hào)所需的位數(shù)為：En=log2(1/Pn)=-log2(Pn)整條信息的熵E也即表示整條信息所需的位數(shù)為：E=∑En4.2.2數(shù)據(jù)壓縮模型——主要有：靜態(tài)統(tǒng)計(jì)模型：預(yù)先掃描文件中的所有字符，統(tǒng)計(jì)出每個(gè)字符出現(xiàn)的概率。自適應(yīng)模型；在信息被輸入之前對(duì)信息內(nèi)容一無所知并假定每個(gè)字符的出現(xiàn)概率均等，隨著字符不斷被輸入和編碼，統(tǒng)計(jì)并紀(jì)錄已經(jīng)出現(xiàn)過的字符的概率并將這些概率應(yīng)用于對(duì)后續(xù)字符的編碼。字典模型：4.2.3數(shù)據(jù)壓縮編碼壓縮=模型+編碼4.3常用的無損數(shù)據(jù)壓縮方法4.3.1香農(nóng)-范諾與哈夫曼編碼1.香農(nóng)-范諾編碼——算法步驟：⑴將待編碼的符號(hào)按符號(hào)出現(xiàn)概率從大到小進(jìn)行排序。⑵將排好序的符號(hào)分成兩組，使這兩組符號(hào)概率和相等或盡可能的相近。⑶將第一組賦值為0，第二組賦值為1。⑷對(duì)每一組，只要不是一個(gè)符號(hào)，就重復(fù)步驟2的操作，否則操作完畢。例4-1有一串由6個(gè)字母組成的長(zhǎng)度為50的字符串，字母分別A、B、C、D、E和F，其中A出現(xiàn)3次，B出現(xiàn)5次，C出現(xiàn)15次，D出現(xiàn)11次，E出現(xiàn)12次，F(xiàn)出現(xiàn)4次，請(qǐng)使用香農(nóng)-范諾對(duì)其進(jìn)行編碼。解題步驟：⑴使用下表列出字母在字符串中的概率統(tǒng)計(jì)⑵首先對(duì)符號(hào)按出現(xiàn)次數(shù)的多少進(jìn)行排序，得下表所示。⑶然后對(duì)符號(hào)進(jìn)行分組，將其分為概率和最接近的兩組即為（C、E）和（D、B、F、A），其中（C、E）賦值為0，（D、B、F、A）賦值為1，依次遞歸下去。使用二叉樹左支為0，右支為1來進(jìn)行編碼，其最終實(shí)現(xiàn)如圖所示。⑷使用香農(nóng)-范諾編碼算法得到的編碼表，如下表所示。⑸總共需要4×3+3×5+2×15+2×11+2×12+4×4=119位，而如果用ASCII來進(jìn)行表示的話，至少要用到50×8=400位；如果用等長(zhǎng)碼3位二進(jìn)制來表示六個(gè)字母的話，這樣需用到50×3=150位，從這兩方面都實(shí)現(xiàn)數(shù)據(jù)壓縮。⑹再來看一看壓縮效果如何，這時(shí)就需來計(jì)算數(shù)據(jù)壓縮的極限—熵的值：2.Huffman編碼——算法步驟：⑴初始化，根據(jù)符號(hào)出現(xiàn)的次數(shù)按由大到小順序?qū)Ψ?hào)進(jìn)行排序。⑵把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)為兩符號(hào)次數(shù)之和，去掉已取出的兩個(gè)節(jié)點(diǎn)，加入這兩節(jié)點(diǎn)之和，重新排序，直至只有一個(gè)數(shù)據(jù)且該數(shù)據(jù)的值所有符號(hào)出現(xiàn)的總次數(shù)相同為止，跳向(4)步驟。⑶重復(fù)步驟2，得到新節(jié)點(diǎn)，形成一棵“樹”。⑷從根節(jié)點(diǎn)開始到相應(yīng)于每個(gè)符號(hào)的“樹葉”，從上到下標(biāo)上“0”或“1”。通常左支標(biāo)為0，右支標(biāo)為1。⑸從根節(jié)點(diǎn)開始順著樹枝到每個(gè)葉子分別寫出每個(gè)符號(hào)的代碼。例4-2就上面關(guān)于Shannon-Fano編碼的例子，現(xiàn)對(duì)其使用Huffman進(jìn)行編碼。解題步驟：⑴首先按照符號(hào)出現(xiàn)的概率有大到小排序，如表下所示。⑵然后選擇其中最小的兩個(gè)符號(hào)，組成一個(gè)節(jié)點(diǎn)，如圖所示。⑶去掉剛才的兩個(gè)符號(hào)，加入它們的和，重新排序如下表所示。⑷繼續(xù)選擇其中最小的兩個(gè)符號(hào)，組成一個(gè)新節(jié)點(diǎn)，如圖所示。⑸依次類推，進(jìn)行遞歸，排序如下表所示。生成的二叉樹如圖所示。⑹依次類推，進(jìn)行遞歸，排序如下表所示。生成的二叉樹如圖所示。⑺依次類推，進(jìn)行遞歸，排序如下表所示。生成的二叉樹如圖所示。⑻對(duì)其進(jìn)行編碼，左為0，右為1，如圖所示。⑼使用Huffman編碼算法得到的編碼表，如下表所示。⑽總共需要4×3+3×5+2×15+2×11+2×12+4×4=119位，與香農(nóng)-范諾編碼算法得到的最后數(shù)據(jù)相同，也同樣實(shí)現(xiàn)了壓縮，但通常情況下哈夫曼編碼比香農(nóng)-范諾編碼的效率要高一些。3.香農(nóng)-范諾編碼和huffman編碼⑴平均碼長(zhǎng)>=熵，但都是接近熵，而且越接近熵，說明壓縮效率越高。⑵保證解碼的唯一性，短字碼不構(gòu)成長(zhǎng)字碼的前綴。⑶在接收端需要一個(gè)與發(fā)送端相同的代碼表。4.3.2算術(shù)編碼算術(shù)編碼的基本原理是將編碼的消息表示成實(shí)數(shù)0和1之間的一個(gè)間隔，取間隔中的一個(gè)數(shù)來進(jìn)行表示消息，消息越長(zhǎng)，編碼表示它的間隔就越小，表示這一間隔所需的二進(jìn)制位就越多。1.自適應(yīng)統(tǒng)計(jì)模型的算術(shù)編碼與解碼例7-3假設(shè)某條信息中可能出現(xiàn)的字符只有a、b、c三種，要壓縮保存的信息為abba。解題步驟：2.靜態(tài)統(tǒng)計(jì)模型的算術(shù)編碼與解碼例4-4：假設(shè)信源符號(hào)為{a，b，c，d}，這些符號(hào)的概率分別為{0.1，0.4，0.2，0.3}，根據(jù)這些概率可把間隔[0，1]分成4個(gè)子間隔：[0，0.1]，[0.1，0.5]，[0.5，0.7]，[0.7，1]，其中[x，y]表示半開放間隔，即包含x不包含y。上面的信息表示在下表中統(tǒng)計(jì)了每個(gè)符號(hào)的概率和初始編碼間隔。如果二進(jìn)制消息序列的輸入為：cadacdb。編碼時(shí)首先輸入的符號(hào)是c，找到它的編碼范圍是[0.5，0.7]。由于消息中第二個(gè)符號(hào)a的編碼范圍是[0，0.1]，因此它的間隔就取[0.5，0.7]的第一個(gè)十分之一作為新間隔[0.5，0.52]。依此類推，編碼第3個(gè)符號(hào)d時(shí)取新間隔為[0.514，0.52]，…。消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)。整個(gè)編碼過程如圖所示。這個(gè)例子的編碼過程表示在下表中。這個(gè)例子的譯碼過程表示在下表中。3.算術(shù)編碼的特點(diǎn)算術(shù)編碼的模式選擇直接影響編碼效率，有固定模式，也有自適應(yīng)模式。算術(shù)編碼的自適應(yīng)模式無需先定義概率模型，對(duì)無法進(jìn)行概率統(tǒng)計(jì)的信源合適，在這點(diǎn)上優(yōu)越于哈夫曼編碼。在信源符號(hào)概率接近時(shí)，算術(shù)編碼比哈夫曼編碼效率高。算術(shù)編碼的硬件實(shí)現(xiàn)比哈夫曼編碼要復(fù)雜些。算術(shù)編碼在JPEG的擴(kuò)展系統(tǒng)中被推薦代替哈夫曼編碼。4.在算術(shù)編碼中有幾個(gè)問題需要注意由于實(shí)際的計(jì)算機(jī)精度不可能無限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問題，可使用比例縮放方法解決。

算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔[0，1]中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。4.3.3行程RLE編碼行程編碼是一種統(tǒng)計(jì)編碼，該編碼屬于無損壓縮編碼。對(duì)于二值圖有效。它的基本原理是：用一個(gè)符號(hào)值或串長(zhǎng)代替具有相同值的連續(xù)符號(hào)，使符號(hào)長(zhǎng)度少于原始數(shù)據(jù)的長(zhǎng)度。行程編碼可以分為定長(zhǎng)和變長(zhǎng)行程編碼兩種方式。行程編碼一般不直接用于多灰度圖像(彩色圖像)中，比較適用于二值圖像的編碼，如傳真圖像的編碼。4.3.4詞典編碼LZW是詞典編碼的一種?；驹硎鞘紫冉⒁粋€(gè)字符串表，把每一個(gè)第一次出現(xiàn)的字符串放入串表中，并用一個(gè)數(shù)字來表示，這個(gè)數(shù)字與此字符串在串表中的位置有關(guān)，將這個(gè)數(shù)字存入壓縮文件中，如果這個(gè)字符串再次出現(xiàn)時(shí)，即可用表示它的數(shù)字來代替，并將這個(gè)數(shù)字存入文件中。壓縮完成后將串表丟棄。4.4常用的有損數(shù)據(jù)壓縮方法4.4.1預(yù)測(cè)編碼預(yù)測(cè)編碼是根據(jù)離散信號(hào)之間存在著一定關(guān)聯(lián)性的特點(diǎn)，利用前面一個(gè)或多個(gè)信號(hào)對(duì)下一個(gè)信號(hào)進(jìn)行預(yù)測(cè)，然后對(duì)實(shí)際值和預(yù)測(cè)值的差（預(yù)測(cè)誤差）進(jìn)行編碼。1.脈沖編碼調(diào)制PCM均勻量化：采用相等的量化間隔處理采樣得到的信號(hào)值。非均勻量化：對(duì)輸入信號(hào)進(jìn)行量化時(shí)，大的輸入信號(hào)采用大的量化間隔，小的輸入信號(hào)采用小的量化間隔，這樣就可以在滿足精度要求的情況下用較少的位數(shù)來表示。2.差分脈沖編碼調(diào)制DPCM不對(duì)每一樣值都進(jìn)行量化，而是預(yù)測(cè)下一樣值，并量化實(shí)際值與預(yù)測(cè)值之間的差值進(jìn)行壓縮的方法。優(yōu)點(diǎn)是算法簡(jiǎn)單，容易硬件實(shí)現(xiàn)，缺點(diǎn)是對(duì)信道噪聲很敏感，會(huì)產(chǎn)生誤差擴(kuò)散。3.自適應(yīng)脈沖編碼調(diào)制ADPCM核心想法是：①利用自適應(yīng)的思想改變量化階的大小，即使用小的量化階(step-size)去編碼小的差值，使用大的量化階去編碼大的差值，②使用過去的樣本值估算下一個(gè)輸入樣本的預(yù)測(cè)值，使實(shí)際樣本值和預(yù)測(cè)值之間的差值總是最小。4.4.2變換編碼一種間接編碼方法，它將原始信號(hào)經(jīng)過數(shù)學(xué)上的正交變換后，得到一系列的變換系數(shù)，再對(duì)這些系數(shù)進(jìn)行量化、編碼、傳輸。變換編碼原理框圖變換編碼系統(tǒng)方框圖變換編、解碼過程示意圖變換編碼技術(shù)技術(shù)上比較成熟，理論也比較完備，廣泛用于各種圖像數(shù)據(jù)壓縮，諸如單色圖像、彩色圖像、運(yùn)動(dòng)圖像、靜止圖像以及多媒體計(jì)算機(jī)技術(shù)中的電視幀內(nèi)圖像壓縮和幀間圖像壓縮等。正交變換的種類有很多種，例如傅立葉變換、沃爾什哈達(dá)瑪變換、正弦變換、余弦變換以及K-L變換等。4.5數(shù)據(jù)壓縮國際標(biāo)準(zhǔn)4.5.1JPEG-靜止圖像壓縮標(biāo)準(zhǔn)一個(gè)適用于彩色和單色多灰度或連續(xù)色調(diào)靜止數(shù)字圖像的壓縮標(biāo)準(zhǔn)。它包括Huffman編碼的無損壓縮算法和基于DPCM（差分脈沖編碼調(diào)制）、DCT（離散余弦變換）的有損壓縮算法兩個(gè)部分。JPEG標(biāo)準(zhǔn)有三個(gè)范疇：⑴基本順序過程：實(shí)現(xiàn)有損圖像壓縮，重建圖像質(zhì)量達(dá)到人眼難以觀察出來的要求。⑵基于DCT的擴(kuò)展過程：基于DCT的擴(kuò)展過程使用累進(jìn)工作方式，采用自適應(yīng)算術(shù)編碼過程。⑶無失真過程：采用預(yù)測(cè)編碼及Huffman編碼（或算術(shù)編碼），可保證重建圖像數(shù)據(jù)與原始圖像數(shù)據(jù)完全相同。JPEG算法操作可分成以下幾個(gè)步驟：⑴通過離散余弦變換（DCT）去除數(shù)據(jù)冗余；⑵使用量化表對(duì)以DCT系數(shù)進(jìn)行量化；⑶對(duì)量化后的DCT系數(shù)進(jìn)行編碼使其熵達(dá)到最小，熵編碼采用Huffman可變字長(zhǎng)編碼。⑷熵編碼⑸組成位數(shù)據(jù)流

4.5.2一個(gè)JPEG的例子原始圖圖像分塊、計(jì)算DCT系數(shù)以及系數(shù)量化系數(shù)編碼4.5.3MPEG-運(yùn)動(dòng)圖像壓縮標(biāo)準(zhǔn)1.MPEG的標(biāo)準(zhǔn)化MPEG-1、2、4標(biāo)準(zhǔn)已經(jīng)正式發(fā)布，MPEG-7也已完成，在2001年底成為正式標(biāo)準(zhǔn)，MPEG-21在2002年形成。其中MPEG-1和2已經(jīng)得到廣泛應(yīng)用。例如，CD-交互系統(tǒng)，在網(wǎng)絡(luò)上的數(shù)字聲音廣播、數(shù)字電視廣播和視頻點(diǎn)播等。2.MPEG壓縮算法思想MPEG標(biāo)準(zhǔn)有三個(gè)組成部分：MPEG視頻；MPEG音頻；視頻與音頻的同步。MPEG視頻是MPEG標(biāo)準(zhǔn)的核心。MPEG視頻壓縮算法中包含兩種基本技術(shù)：一種是基于l6×16子塊的運(yùn)動(dòng)補(bǔ)償技術(shù)，用來減少幀序列的時(shí)域冗余；另一種是基于DCT