無損壓縮技術(shù)

無損壓縮技術(shù)第1頁(yè)，共41頁(yè)，2023年，2月20日，星期五數(shù)據(jù)壓縮技術(shù)的性能指標(biāo)

壓縮的必要性音頻、視頻的數(shù)據(jù)量很大，如果不進(jìn)行處理，計(jì)算機(jī)系統(tǒng)幾乎無法對(duì)它進(jìn)行存取和交換。例如：基本原理和方法一幅中等分辨率（640×480）的真彩色圖像（24b/像素），它的數(shù)據(jù)量約為0.9MB/幀，若要達(dá)到每秒25幀的全動(dòng)態(tài)顯示要求，每秒所需的數(shù)據(jù)量約為22MB。對(duì)于聲音也是如此，CD音質(zhì)的聲音每秒將有約為172KB的數(shù)據(jù)量。第2頁(yè)，共41頁(yè)，2023年，2月20日，星期五第3頁(yè)，共41頁(yè)，2023年，2月20日，星期五視頻、圖像、聲音有很大的壓縮潛力

信息論認(rèn)為：若信源編碼的熵大于信源的實(shí)際熵，該信源中一定存在冗余度（信息熵冗余）。原始信源的數(shù)據(jù)存在著很多冗余度：空間冗余、時(shí)間冗余、視覺冗余、聽覺冗余、統(tǒng)計(jì)冗余、結(jié)構(gòu)冗余、知識(shí)冗余、信息熵冗余等?；驹砗头椒〝?shù)據(jù)壓縮技術(shù)的性能指標(biāo)第4頁(yè)，共41頁(yè)，2023年，2月20日，星期五冗余的基本概念

指信息存在的各種性質(zhì)的多余度舉例：（1）廣播員讀文稿時(shí)每分鐘約讀180字，一個(gè)漢字占兩個(gè)字節(jié)；文本數(shù)據(jù)量為360B；（2）如果對(duì)語(yǔ)音錄音，由于人說話的音頻范圍為20Hz到4kHz，即語(yǔ)音的帶寬為4kHz，若設(shè)量化位數(shù)為8bit,則一秒鐘的數(shù)據(jù)量為：

4×2×8=64kbit/s=8KB/s則一分鐘的數(shù)據(jù)是480KB。

數(shù)據(jù)冗余的類型與壓縮方法分類基本原理和方法360B

480KB第5頁(yè)，共41頁(yè)，2023年，2月20日，星期五數(shù)據(jù)冗余的類別空間冗余時(shí)間冗余統(tǒng)計(jì)冗余信息熵冗余結(jié)構(gòu)冗余知識(shí)冗余視覺冗余聽覺冗余數(shù)據(jù)冗余的類型與壓縮方法分類基本原理和方法第6頁(yè)，共41頁(yè)，2023年，2月20日，星期五●空間冗余數(shù)據(jù)冗余的類型與壓縮方法分類規(guī)則物體和規(guī)則背景的表面物理特性都具有相關(guān)性，數(shù)字化后表現(xiàn)為數(shù)據(jù)冗余。●時(shí)間冗余序列圖像（如電視圖像和運(yùn)動(dòng)圖像）和語(yǔ)音數(shù)據(jù)的前后有著很強(qiáng)的相關(guān)性，經(jīng)常包含著冗余。在播出該序列圖像時(shí)，時(shí)間發(fā)生了推移，但若干幅畫面的同一部位沒有變化，變化的只是其中某些地方，這就形成了時(shí)間冗余。基本原理和方法第7頁(yè)，共41頁(yè)，2023年，2月20日，星期五

空間冗余和時(shí)間冗余是把圖像信號(hào)看作概率信號(hào)時(shí)反應(yīng)出的統(tǒng)計(jì)特性，因此，這兩種冗余也被稱為統(tǒng)計(jì)冗余。數(shù)據(jù)冗余的類型與壓縮方法分類●統(tǒng)計(jì)冗余●信息熵冗余信息熵實(shí)際情況又稱編碼冗余。信息熵是指一組數(shù)所攜帶的信息量?！窠Y(jié)構(gòu)冗余數(shù)字化圖像中的物體表面紋理等結(jié)構(gòu)往往存在著冗余基本原理和方法第8頁(yè)，共41頁(yè)，2023年，2月20日，星期五

由圖像的記錄方式與人對(duì)圖像的知識(shí)差異所產(chǎn)生的冗余稱為知識(shí)冗余?！裰R(shí)冗余

人類的視覺系統(tǒng)對(duì)于圖像場(chǎng)的注意在非均勻和非線性的，視覺系統(tǒng)并不是對(duì)圖像的任何變化都能感知?！褚曈X冗余

●聽覺冗余

人耳對(duì)不同頻率的聲音的敏感性是不同的，并不能察覺所有頻率的變化，對(duì)某些頻率不必特別關(guān)注，因此存在聽覺冗余。數(shù)據(jù)冗余的類型與壓縮方法分類基本原理和方法第9頁(yè)，共41頁(yè)，2023年，2月20日，星期五從哪些方面評(píng)價(jià)一個(gè)壓縮系統(tǒng)？數(shù)據(jù)壓縮技術(shù)的性能指標(biāo)基本原理和方法●壓縮比●圖像質(zhì)量●壓縮解壓速度●硬件和軟件第10頁(yè)，共41頁(yè)，2023年，2月20日，星期五壓縮比

輸入數(shù)據(jù)和輸出數(shù)據(jù)比例如：圖像512×480，24位輸入＝(512×480×24)/8=737280B

輸出15000B

壓縮比＝737280/15000＝49數(shù)據(jù)壓縮技術(shù)的性能指標(biāo)基本原理和方法第11頁(yè)，共41頁(yè)，2023年，2月20日，星期五圖像質(zhì)量壓縮方法：無損壓縮有損壓縮有損壓縮：失真情況很難量化，只能對(duì)測(cè)試的圖像進(jìn)行估計(jì)。

數(shù)據(jù)壓縮技術(shù)的性能指標(biāo)基本原理和方法第12頁(yè)，共41頁(yè)，2023年，2月20日，星期五壓縮解壓速度在許多應(yīng)用中，壓縮和解壓可能不同時(shí)用，在不同的位置不同的系統(tǒng)中。所以，壓縮、解壓速度分別估計(jì)。靜態(tài)圖像中，壓縮速度沒有解壓速度嚴(yán)格；動(dòng)態(tài)圖像中，壓縮、解壓速度都有要求，因?yàn)樾鑼?shí)時(shí)地從攝像機(jī)或其他設(shè)備中抓取動(dòng)態(tài)視頻。數(shù)據(jù)壓縮技術(shù)的性能指標(biāo)基本原理和方法第13頁(yè)，共41頁(yè)，2023年，2月20日，星期五硬軟件系統(tǒng)

有些壓縮解壓工作可用軟件實(shí)現(xiàn)。設(shè)計(jì)系統(tǒng)時(shí)必須充分考慮：算法復(fù)雜－壓縮解壓過程長(zhǎng)算法簡(jiǎn)單－壓縮效果差目前有些特殊硬件可用于加速壓縮/解壓。硬件系統(tǒng)速度快，但各種選擇在初始設(shè)計(jì)時(shí)已確定，一般不能更改。因此在設(shè)計(jì)硬接線壓縮/解壓系統(tǒng)時(shí)必須先將算法標(biāo)準(zhǔn)化。數(shù)據(jù)壓縮技術(shù)的性能指標(biāo)基本原理和方法第14頁(yè)，共41頁(yè)，2023年，2月20日，星期五數(shù)據(jù)壓縮技術(shù)分類指使壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。

典型的算法有：Huffman編碼，算術(shù)編碼，行程編碼等。特點(diǎn)：壓縮比較低，為2:1---5:1，一般用來壓縮文本，數(shù)據(jù)。數(shù)據(jù)冗余的類型與壓縮方法分類●無損壓縮基本原理和方法第15頁(yè)，共41頁(yè)，2023年，2月20日，星期五是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。典型的算法有：混合編碼的JPEG標(biāo)準(zhǔn)，MPEG標(biāo)準(zhǔn)等。特點(diǎn)：壓縮比高，為幾十到幾百倍一般用于圖像，聲音，視頻壓縮。數(shù)據(jù)冗余的類型與壓縮方法分類●有損壓縮基本原理和方法第16頁(yè)，共41頁(yè)，2023年，2月20日，星期五數(shù)據(jù)壓縮的方法統(tǒng)計(jì)編碼預(yù)測(cè)編碼變換編碼混合編碼

分析合成編碼常用數(shù)據(jù)壓縮方法的基本原理基本原理和方法第17頁(yè)，共41頁(yè)，2023年，2月20日，星期五熵是信息量的度量方法某個(gè)事件的信息量用表示

，其中為第個(gè)I個(gè)事件的概率。信源S的熵的定義

常用數(shù)據(jù)壓縮方法的基本原理●香農(nóng)-范諾與霍夫曼編碼第18頁(yè)，共41頁(yè)，2023年，2月20日，星期五

根據(jù)消息出現(xiàn)概率的分布特性而進(jìn)行的壓縮編碼。

Huffman編碼行程編碼詞典編碼算術(shù)編碼常用數(shù)據(jù)壓縮方法的基本原理基本原理和方法●統(tǒng)計(jì)編碼第19頁(yè)，共41頁(yè)，2023年，2月20日，星期五Huffman編碼它是統(tǒng)計(jì)獨(dú)立信源能達(dá)到最小平均碼長(zhǎng)的編碼方法。編碼效率高。統(tǒng)計(jì)編碼基本原理和方法第20頁(yè)，共41頁(yè)，2023年，2月20日，星期五Huffman編碼編碼步驟：

(1)初始化，根據(jù)符號(hào)概率的大小按由大到小順序?qū)Ψ?hào)進(jìn)行排序。

(2)把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)。

(3)重復(fù)步驟2。

(4)從根節(jié)點(diǎn)開始到相應(yīng)于每個(gè)符號(hào)的“樹葉”，從上到下標(biāo)上“0”(上枝)或者“1”(下枝)，至于哪個(gè)為“1”哪個(gè)為“0”則無關(guān)緊要，最后的結(jié)果僅僅是分配的代碼不同，而代碼的平均長(zhǎng)度是相同的。

(5)從根節(jié)點(diǎn)開始順著樹枝到每個(gè)葉子分別寫出每個(gè)符號(hào)的代碼，統(tǒng)計(jì)編碼基本原理和方法第21頁(yè)，共41頁(yè)，2023年，2月20日，星期五a10.20a20.19a30.18a40.17a50.15a60.10a70.01010.11010.2600.3510.611101000.391.00碼字碼長(zhǎng)01200233344平均碼長(zhǎng)：2.72Huffman編碼過程第22頁(yè)，共41頁(yè)，2023年，2月20日，星期五Huffman編碼的注意點(diǎn)Huffman編碼沒有錯(cuò)誤保護(hù)功能，如果碼中有錯(cuò)誤，則可能引起接下來的一連串譯碼錯(cuò)誤。Huffman編碼是可變長(zhǎng)編碼，因此很難隨意查找或調(diào)用中的文件內(nèi)容。Huffman依賴于信源的統(tǒng)計(jì)特性。Huffman編碼的每個(gè)碼字都是整數(shù)，因此實(shí)際上平均碼長(zhǎng)很難達(dá)到信息熵的大小。Huffman編碼解碼必須要有碼表，如果消息數(shù)目很多，那么所需要存儲(chǔ)的碼表也很大，這將影響系統(tǒng)的存儲(chǔ)量及編、譯碼速度。統(tǒng)計(jì)編碼基本原理和方法第23頁(yè)，共41頁(yè)，2023年，2月20日，星期五算術(shù)編碼算術(shù)編碼把一個(gè)信源集合表示為實(shí)數(shù)線上的0到1之間的一個(gè)區(qū)間。這個(gè)集合中的每個(gè)元素都要用來縮短這個(gè)區(qū)間。信源集合的元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時(shí)，就需要一些更多的數(shù)位來表示這個(gè)區(qū)間，這就是區(qū)間作為代碼的原理。算術(shù)編碼首先假設(shè)一個(gè)信源的概率模型，然后用這些概率來縮小表示信源集的區(qū)間。統(tǒng)計(jì)編碼基本原理和方法第24頁(yè)，共41頁(yè)，2023年，2月20日，星期五算術(shù)編碼新子區(qū)間的起始位置＝前子區(qū)間的起始位置＋當(dāng)前符號(hào)的區(qū)間左端×前子區(qū)間長(zhǎng)度新子區(qū)間的長(zhǎng)度＝前子區(qū)間的長(zhǎng)度×當(dāng)前符號(hào)的概率（等價(jià)于范圍長(zhǎng)度）最后得到的子區(qū)間的長(zhǎng)度決定了表示該區(qū)域內(nèi)的某一個(gè)數(shù)所需的位數(shù)。統(tǒng)計(jì)編碼基本原理和方法第25頁(yè)，共41頁(yè)，2023年，2月20日，星期五算術(shù)編碼統(tǒng)計(jì)編碼基本原理和方法[例]假設(shè)信源符號(hào)為{00,01,10,11}，這些符號(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。上面的信息可綜合在下表中。符號(hào)00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)第26頁(yè)，共41頁(yè)，2023年，2月20日，星期五算術(shù)編碼統(tǒng)計(jì)編碼基本原理和方法第27頁(yè)，共41頁(yè)，2023年，2月20日，星期五算術(shù)編碼要注意的幾個(gè)問題：由于實(shí)際的計(jì)算機(jī)的精度不可能無限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問題，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此這個(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ò)。統(tǒng)計(jì)編碼基本原理和方法第28頁(yè)，共41頁(yè)，2023年，2月20日，星期五行程編碼是最簡(jiǎn)單、最古老的壓縮技術(shù)之一，主要技術(shù)是檢測(cè)重復(fù)的比特或字符序列，并用它們的出現(xiàn)次數(shù)取而代之。該方法有兩大模式：一是消零(消空白)，二是行(游)程(runlength)編碼。

消零(或消空白)法

將數(shù)字中連續(xù)的“0”或文本中連續(xù)的空白用一個(gè)標(biāo)識(shí)符(或特殊字符)后跟數(shù)字N(連續(xù)“0”的個(gè)數(shù))來代替。

如數(shù)字序列：742300000000000000000055

編碼為：7423Z1855統(tǒng)計(jì)編碼基本原理和方法第29頁(yè)，共41頁(yè)，2023年，2月20日，星期五行程編碼行程編碼法

任何重復(fù)的字符序列可被一個(gè)短格式取代。該算法適合于任何重復(fù)的字符。一組n個(gè)連續(xù)的字符c將被c和一個(gè)特殊的字符取代。當(dāng)然，若給定字符僅重復(fù)兩次就不要用此方法。任何重復(fù)4次或4次以上的字符由“該字符＋記號(hào)(M)＋重復(fù)次數(shù)”代替。例如數(shù)字序列：Name:..........CR

編碼為：Name:

.M10CR統(tǒng)計(jì)編碼基本原理和方法第30頁(yè)，共41頁(yè)，2023年，2月20日，星期五詞典編碼

詞典編碼(dictionaryencoding)的根據(jù)是數(shù)據(jù)本身包含有重復(fù)代碼這個(gè)特性。例如文本文件和光柵圖像就具有這種特性。歸納起來大致有兩類。

統(tǒng)計(jì)編碼基本原理和方法第31頁(yè)，共41頁(yè)，2023年，2月20日，星期五第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”。

詞典編碼基本原理和方法第32頁(yè)，共41頁(yè)，2023年，2月20日，星期五第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語(yǔ)詞典(dictionaryofthephrases)”，編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語(yǔ)”時(shí)，編碼器就輸出這個(gè)詞典中的短語(yǔ)的“索引號(hào)”，而不是短語(yǔ)本身。

詞典編碼基本原理和方法第33頁(yè)，共41頁(yè)，2023年，2月20日，星期五詞典編碼基本原理和方法第34頁(yè)，共41頁(yè)，2023年，2月20日，星期五LZW編碼簡(jiǎn)介L(zhǎng)ZW通過建立一個(gè)字符串表,用較短的代碼來表示較長(zhǎng)的字符串來實(shí)現(xiàn)壓縮。字符串和編碼的對(duì)應(yīng)關(guān)系是在壓縮過程中動(dòng)態(tài)生成的,并且隱含在壓縮數(shù)據(jù)中,解壓的時(shí)候根據(jù)表來進(jìn)行恢復(fù),是一種無損壓縮。全稱Lempel-Ziv-WelchEncoding，簡(jiǎn)稱LZW的壓縮算法。詞典編碼基本原理和方法第35頁(yè)，共41頁(yè)，2023年，2月20日，星期五LZW壓縮有三個(gè)重要的對(duì)象數(shù)據(jù)流(CharStream)編碼流(CodeStream)編譯表(StringTable)。在編碼時(shí)，數(shù)據(jù)流是輸入對(duì)象（文本文件的數(shù)據(jù)序列），編碼流就是輸出對(duì)象（經(jīng)過壓縮運(yùn)算的編碼數(shù)據(jù)）；在解碼時(shí)，編碼流則是輸入對(duì)象，數(shù)據(jù)流是輸出對(duì)象；而編譯表是在編碼和解碼時(shí)都須要用借助的對(duì)象。詞典編碼基本原理和方法第36頁(yè)，共41頁(yè)，2023年，2月20日，星期五LZW編碼基本原理提取原始文本文件數(shù)據(jù)中的不同字符，基于這些字符創(chuàng)建一個(gè)編譯表，然后用編譯表中的字符的索引來替代原始文本文件數(shù)據(jù)中的相應(yīng)字符，減少原始數(shù)據(jù)大小?？雌饋砗驼{(diào)色板圖象的實(shí)現(xiàn)原理差不多，但是應(yīng)該注意到的是，我們這里的編譯表不是事先創(chuàng)建好的，而是根據(jù)原始文件數(shù)據(jù)動(dòng)態(tài)創(chuàng)建的，解碼時(shí)還要從已編碼的數(shù)據(jù)中還原出原來的編譯表.詞典編碼基本原理和方法第37頁(yè)，共41頁(yè)，2023年，2月20日，星期五LZW算法LZW算法基于轉(zhuǎn)換串表（字典）T，將輸入字符串映射成定長(zhǎng)（通常為12位）的碼字。在12位4096種可能的代碼中，256個(gè)代表單字符，剩下3840給出現(xiàn)的字符串。1)初始化：將所有的單字符串放入串表2)讀第一個(gè)輸入字符給前綴串ω3)Step:讀下一個(gè)輸入字符K;if沒有這樣的K(輸入已窮盡)：碼字(