04數(shù)據(jù)壓縮基礎(chǔ)課件

數(shù)據(jù)壓縮基礎(chǔ)...數(shù)據(jù)壓縮基礎(chǔ)...1數(shù)據(jù)壓縮編碼技術(shù)概述多媒體數(shù)據(jù)壓縮的必要性和可行性衡量多媒體數(shù)據(jù)壓縮技術(shù)的指標(biāo)： 壓縮比 算法簡(jiǎn)單，壓縮解壓縮速度快 盡可能地恢復(fù)原始數(shù)據(jù)壓縮方法分類(lèi) 無(wú)損壓縮：Huffman編碼、游程編碼、算術(shù)編碼、LZW編碼 有損壓縮：預(yù)測(cè)編碼、變換編碼、模型編碼、基于重要性的編 碼、混合編碼新一代的數(shù)據(jù)壓縮方法：矢量量化和子代編碼、基于模型的壓 縮、分形壓縮、小波變換壓縮等等。...數(shù)據(jù)壓縮編碼技術(shù)概述...2

壓縮的必要性

音頻、視頻的數(shù)據(jù)量很大，如果不進(jìn)行處理，計(jì)算機(jī)系統(tǒng)幾乎無(wú)法對(duì)它進(jìn)行存取和交換。 例如，一幅具有中等分辨率（640×480）的真彩色圖像（24b/像素），它的數(shù)據(jù)量約為7.37Mb/幀，一個(gè)700MB（Byte）的硬盤(pán)只能存放約100幀圖像。若要達(dá)到每秒25幀的全動(dòng)態(tài)顯示要求，每秒所需的數(shù)據(jù)量為184Mb，而且要求系統(tǒng)的數(shù)據(jù)傳輸率必須達(dá)到184Mb/s。對(duì)于聲音也是如此，若采用16b樣值的PCM編碼，采樣速率選為44.1kHZ，則雙聲道立體聲聲音每秒將有176KB的數(shù)據(jù)量。... 壓縮的必要性...3數(shù)據(jù)壓縮的好處

時(shí)間域壓縮──迅速傳輸媒體信源 頻率域壓縮──并行開(kāi)通更多業(yè)務(wù) 空間域壓縮──降低存儲(chǔ)費(fèi)用 能量域壓縮──降低發(fā)射功率...數(shù)據(jù)壓縮的好處...4數(shù)據(jù)壓縮技術(shù)實(shí)現(xiàn)的衡量標(biāo)準(zhǔn)

壓縮比要大 恢復(fù)后的失真小 壓縮算法要簡(jiǎn)單、速度快 壓縮能否用硬件實(shí)現(xiàn)...數(shù)據(jù)壓縮技術(shù)實(shí)現(xiàn)的衡量標(biāo)準(zhǔn)...5多媒體數(shù)據(jù)壓縮技術(shù)分類(lèi)

平均信息量編碼──可逆壓縮──去冗 余──統(tǒng)計(jì)特性 源編碼──不可逆壓縮──有失真編碼 特征提取等 兩種壓縮技術(shù)不互斥，兩種壓縮技 術(shù)的結(jié)合，可以達(dá)到最高可能的壓縮率。...多媒體數(shù)據(jù)壓縮技術(shù)分類(lèi)...6

多媒體數(shù)據(jù)壓縮技術(shù)分類(lèi)

無(wú)損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)完全相同；無(wú)損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。

有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)有所不同，但不會(huì)使人對(duì)原始資料表達(dá)的信息造成誤解。有損壓縮適用于重構(gòu)信號(hào)不一定非要和原始信號(hào)完全相同的場(chǎng)合。... 多媒體數(shù)據(jù)壓縮技術(shù)分類(lèi)...7無(wú)損數(shù)據(jù)壓縮

主要介紹目前用得最多和技術(shù)最成熟的 無(wú)損壓縮編碼技術(shù)，包括： 霍夫曼編碼 算術(shù)編碼 游程編碼RLE 詞典編碼LZW...無(wú)損數(shù)據(jù)壓縮...8

霍夫曼(Huffman)編碼

霍夫曼(Huffman)在1952年提出了另一種編碼方法，即從 下到上的編碼方法。

幾個(gè)個(gè)問(wèn)題值得注意：1.霍夫曼碼沒(méi)有錯(cuò)誤保護(hù)功能；2.霍夫曼碼是可變長(zhǎng)度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼;3.接收端需保存一個(gè)與發(fā)送端相同的霍夫曼碼表。... 霍夫曼(Huffman)編碼...9字母頻率編碼A25%01B15%110C10%111D20%10E30%00霍夫曼(Huffman)編碼...字母頻率編碼A25%01B15%110C10%111D20%10信源消減信源符號(hào)集B={b1,b2,b3,b4}

概率矢量u={0.1，0.38，0.22，0.3}

步驟1：信源消減...信源消減...11步驟2：對(duì)信源符號(hào)賦值平均碼長(zhǎng)Lavg=1.946...步驟2：對(duì)信源符號(hào)賦值...12霍夫曼碼的特點(diǎn)1，塊碼（組碼）

2，即時(shí)碼

3，唯一可解碼...霍夫曼碼的特點(diǎn)...13霍夫曼碼改型亞最優(yōu)犧牲編碼效率來(lái)?yè)Q取編碼速度截?cái)嗷舴蚵a前M個(gè)符號(hào)用霍夫曼編碼其余用前綴碼+定長(zhǎng)碼（自然碼）平移霍夫曼碼分組：相同符號(hào)數(shù)用霍夫曼編碼編第1組其余組用平移符號(hào)+第一組霍夫曼碼......14霍夫曼碼改型

......15霍夫曼(Huffman)編碼 依賴(lài)于信源的統(tǒng)計(jì)特性，必須先統(tǒng)計(jì)得到信源 的概率特性才能編碼，這就限制了實(shí)際的應(yīng)用。 缺乏構(gòu)造性，即它不能用某種數(shù)學(xué)方法建立起 消息和碼字之間的一一對(duì)應(yīng)關(guān)系，而只能通過(guò) 某種查表的方法建立起它們的對(duì)應(yīng)關(guān)系。 如果消息數(shù)目很多，那么所需存儲(chǔ)的碼表也很 大，這將影響系統(tǒng)的存儲(chǔ)量及編、譯碼速度。...霍夫曼(Huffman)編碼...16練習(xí)初始信源：a1：0.1，a2：0.4，a3:：0.06，a4:0.1，a5：0.04，a6：0.3....練習(xí)初始信源：...17練習(xí)...練習(xí)...18算術(shù)編碼只需要用到加法和位移運(yùn)算從整個(gè)符號(hào)序列出發(fā)算術(shù)編碼不再是塊碼，采用遞推形式連續(xù)編碼

...算術(shù)編碼...19算術(shù)編碼的特點(diǎn)：1種從整個(gè)符號(hào)序列出發(fā)，采用遞推形式連續(xù)編碼的方法不存在源符號(hào)和碼字間的一一對(duì)應(yīng)關(guān)系1個(gè)算術(shù)碼字要賦給整個(gè)信源符號(hào)序列，而每個(gè)碼字本身確定了0和1之間的1個(gè)實(shí)數(shù)區(qū)間算術(shù)編碼過(guò)程只需用到加法和移位運(yùn)算

...算術(shù)編碼的特點(diǎn)：...20算術(shù)編碼

b1=0.1b2=0.38b3=0.22b4=0.30.0000100120.0351562510碼串：b1；b2；b3；b4...算術(shù)編碼b1=0.1b2=0.38b3=0.22b4=0.321

算術(shù)編碼在算術(shù)編碼中需要注意的幾個(gè)問(wèn)題：1.由于實(shí)際計(jì)算機(jī)精度不可能無(wú)限長(zhǎng)，運(yùn)算中溢出是明顯的問(wèn)題，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此可使用比例縮放法解決。2.算術(shù)編碼器對(duì)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在[0,1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。3.算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。... 算術(shù)編碼...22算數(shù)編碼練習(xí)初始信源：a1：0.1，a2：0.4，a3：0.5，碼串：a1，a1，a2，a3...算數(shù)編碼練習(xí)初始信源：...23

游程RLE編碼RLE(runlengthencoding）編碼的概念

用RLE編碼方法得到的代碼為：80315084180。代碼中用黑體表示的數(shù)字是行程長(zhǎng)度，黑體字后面的數(shù)字代表象素的顏色值。例如黑體字50代表有連續(xù)50個(gè)象素具有相同的顏色值，它的顏色值是8。 譯碼時(shí)按照與編碼時(shí)采用的相同規(guī)則進(jìn)行，還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。... 游程RLE編碼...24

詞典編碼

詞典編碼的思想

第一類(lèi)詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過(guò)，然后用已經(jīng)出現(xiàn)過(guò)的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過(guò)的字符串的“指針”。... 詞典編碼...25詞典編碼

詞典編碼的思想

第二類(lèi)算法的想法 是企圖從輸入的數(shù)據(jù)中 創(chuàng)建一個(gè)“短語(yǔ)詞典

(dictionaryofthe phrases)”，這種短語(yǔ)可 以是任意字符的組合。 編碼數(shù)據(jù)過(guò)程中當(dāng)遇到 已經(jīng)在詞典中出現(xiàn)的“短 語(yǔ)”時(shí)，編碼器就輸出這 個(gè)詞典中的短語(yǔ)的“索引 號(hào)”，而不是短語(yǔ)本身。...詞典編碼...26

詞典編碼

J.Ziv和A.Lempel在1978年首次發(fā)表了介紹上述第二類(lèi)編碼方法的文章。在他們的研究基礎(chǔ)上，TerryA.Welch在1984年發(fā)表了改進(jìn)這種編碼算法的文章，因此把這種編碼方法稱(chēng)為L(zhǎng)ZW(Lempel-ZivWalch)壓縮編碼，

LZW算法

在編碼原理上，LZW與LZ78相比有如下差別：①LZW只輸出代表詞典中的綴-符串(String)的碼字(codeword)。這就意味在開(kāi)始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。②由于所有可能出現(xiàn)的單個(gè)字符都事先包含在詞典中，每個(gè)編碼步驟開(kāi)始時(shí)都使用一字符前綴(one-characterprefix)，因此在詞典中搜索的第1個(gè)綴-符串有兩個(gè)字符。

LZW編碼是圍繞稱(chēng)為詞典的轉(zhuǎn)換表來(lái)完成的。... 詞典編碼...27

詞典編碼

LZW算法

LZW編碼器使用了一種很實(shí)用的分析(parsing)算法，稱(chēng)為貪婪分析算法(greedyparsingalgorithm)。在貪婪分析算法中，每一次分析都要串行地檢查來(lái)自字符流(Charstream)的字符串，從中分解出已經(jīng)識(shí)別的最長(zhǎng)的字符串，也就是已經(jīng)在詞典中出現(xiàn)的最長(zhǎng)的前綴(Prefix)。用已知的前綴(Prefix)加上下一個(gè)輸入字符C也就是當(dāng)前字符(Currentcharacter)作為該前綴的擴(kuò)展字符，形成新的擴(kuò)展字符串——綴-符串(String)：Prefix.C。這個(gè)新的綴-符串(String)是否要加到詞典中，還要看詞典中是否存有和它相同的綴-符串String。如果有，那么這個(gè)綴-符串(String)就變成前綴(Prefix)，繼續(xù)輸入新的字符，否則就把這個(gè)綴-符串(String)寫(xiě)到詞典中生成一個(gè)新的前綴(Prefix)，并給一個(gè)代碼。... 詞典編碼...28

詞典編碼

LZW算法

LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因?yàn)樗恍枰獔?zhí)行那么多的綴-符串比較操作。對(duì)LZW算法進(jìn)一步的改進(jìn)是增加可變的碼字長(zhǎng)度，以及在詞典中刪除老的綴-符串。在GIF圖像格式和UNIX的壓縮程序中已經(jīng)采用了這些改進(jìn)措施之后的LZW算法。

LZW算法取得了專(zhuān)利，專(zhuān)利權(quán)的所有者是美國(guó)的一個(gè)大型計(jì)算機(jī)公司—Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產(chǎn)公司之外，可以免費(fèi)使用LZW算法。... 詞典編碼...29

詞典編碼壓縮算法基于以下的中心思想

1. 為原始文本文件中的每個(gè)字母分配一個(gè)代碼并存儲(chǔ)到 一個(gè)代碼表中

2. 設(shè)置一個(gè)循環(huán)，每次從文件中獲取一個(gè)字符。將使用 一個(gè)緩沖字符串，把從文件中取出的字符連接在一起

3. 在每次循環(huán)中，讀取一個(gè)字符接到緩沖字符串的后 面，形成一個(gè)新的臨時(shí)字符串。如果該臨時(shí)字符串以前 曾經(jīng)出現(xiàn)過(guò)就把它移到緩沖區(qū)里

4. 如果臨時(shí)字符串不出現(xiàn)在代碼表中，就為它分配一個(gè) 代碼，并把字符串和代碼存儲(chǔ)到代碼表中，同時(shí)發(fā)送緩 沖字符串所對(duì)應(yīng)的代碼 重新設(shè)置緩沖字符串為剛剛讀取的單個(gè)字符。... 詞典編碼...30JPEG算法概要JPEG(JointPhotographicExpertsGroup)是一個(gè)由ISO和IEC兩個(gè)組織機(jī)構(gòu)聯(lián)合組成的一個(gè)專(zhuān)家組，負(fù)責(zé)制定靜態(tài)的數(shù)字圖像數(shù)據(jù)壓縮編碼標(biāo)準(zhǔn)，這個(gè)專(zhuān)家組開(kāi)發(fā)的算法稱(chēng)為JPEG算法，并且成為國(guó)際上通用的標(biāo)準(zhǔn)，因此又稱(chēng)為JPEG標(biāo)準(zhǔn)。JPEG是一個(gè)適用范圍很廣的靜態(tài)圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)，既可用于灰度圖像又可用于彩色圖像。使用有損壓縮算法時(shí)，在壓縮比為25:1的情況下，壓縮后還原得到的圖像與原始圖像相比較，非圖像專(zhuān)家難于找出它們之間的區(qū)別，因此得到了廣泛的應(yīng)用。V-CD、DVD-Video。

圖像和視頻的壓縮技術(shù)...JPEG算法概要JPEG(JointPhotographi31

圖像和視頻的壓縮技術(shù)JPEG壓縮的三個(gè)階段

離散余弦變換（DiscreteCosineTransform,DCT） 量化（Quantization） 編碼階段（EncodingPhase）壓縮圖像原始圖像DCT階段量化階段編碼階段... 圖像和視頻的壓縮技術(shù)壓縮圖像原始圖像DCT階段量化階段編碼321.離散余弦變換 下面對(duì)正向離散余弦變換(FDCT)變換作幾點(diǎn)說(shuō)明。 (1)對(duì)每個(gè)單獨(dú)的彩色圖像分量，把整個(gè)分量圖像分成8×8的圖像塊，并作為兩維離散余弦變換DCT的輸入。通過(guò)DCT變換，把能量集中在少數(shù)幾個(gè)系數(shù)上。

...1.離散余弦變換...33離散余弦變換階段P(x,y)經(jīng)DCT變換之后，T(0，0)是直流系數(shù)，其他為交流系數(shù)。在計(jì)算兩維的DCT變換時(shí)，可把兩維的DCT變換變成一維的DCT變換...離散余弦變換階段P(x,y)經(jīng)DCT變換之后，T(0，0)34圖像和視頻的壓縮技術(shù)2.量化階段量化是對(duì)經(jīng)過(guò)FDCT變換后的頻率系數(shù)進(jìn)行量化。量化的目的是減小非“0”系數(shù)的幅度以及增加“0”值系數(shù)的數(shù)目。量化是圖像質(zhì)量下降的最主要原因Q=integer(T/U)其中：DCT變換系數(shù)T；U是量化器步長(zhǎng)，它是量化表的元素。...圖像和視頻的壓縮技術(shù)其中：DCT變換系數(shù)T；...35圖像和視頻的壓縮技術(shù)

量化器步長(zhǎng)1520-480-80-7013579111315T=00000000357911131517-480380-30205791113151719U=

00000000-80-30130-10 0000 0000-7 020-1070 0000 0000

79111315171921 911131517192123111315171921232513151719212325271517192123252729...圖像和視頻的壓縮技術(shù)1520-480-836Q=圖像和視頻的壓縮技術(shù)

根據(jù)公式，量化后將得到

1520-100-10-10 00000000-100400000

00-10 00-10 00000000001000000000000000000000...Q=圖像和視頻的壓縮技術(shù)-10040037對(duì)于有損壓縮算法，JPEG算法使用均勻量化器進(jìn)行量化，量化步長(zhǎng)是按照系數(shù)所在的位置和每種顏色分量的色調(diào)值來(lái)確定。因?yàn)槿搜蹖?duì)亮度信號(hào)比對(duì)色差信號(hào)更敏感，因此使用了兩種量化表：亮度量化表和色差量化表。...對(duì)于有損壓縮算法，JPEG算法使用均勻量化器進(jìn)行量化383.Z字形編碼階段。量化后的系數(shù)要重新編排，目的是為了增加連續(xù)的“0”系數(shù)的個(gè)數(shù)，就是“0”的游程長(zhǎng)度，方法是按照Z(yǔ)字形的式樣編排。這樣就把一個(gè)8×8的矩陣變成一個(gè)1×64的矢量。編碼階段152

0-10

0 -1 0 -1 000000000-10

0 0 0 0 0 0 000000000-1 0 0 0 0 0 0 000000000-1 0 0 0 0 0 0 000000000...3.Z字形編碼階段。編碼階段1520-100-10-10.394.直流系數(shù)的編碼階段 8×8圖像塊經(jīng)過(guò)DCT變換之后得到的直流系數(shù)有兩個(gè)特點(diǎn)：一是系數(shù)的數(shù)值比較大，二是相鄰8×8圖像塊的直流系數(shù)值變化不大。 根據(jù)這個(gè)特點(diǎn)，JPEG算法使用了差分脈沖編碼調(diào)制(DPCM)技術(shù)，對(duì)相鄰圖像塊之間的直流系數(shù)的差值(Delta)進(jìn)行編碼，

Delta＝DC(0,0)k-DC(0,0)k-1

...4.直流系數(shù)的編碼階段...405.交流系數(shù)的編碼階段量化交流系數(shù)的特點(diǎn)是1×64矢量中包含有許多“0”系數(shù)，并且許多“0”是連續(xù)的，因此使用非常簡(jiǎn)單和直觀(guān)的游程長(zhǎng)度編碼(RLE)對(duì)它們進(jìn)行編碼。JPEG使用了1個(gè)字節(jié)的高4位來(lái)表示連續(xù)“0”的個(gè)數(shù)，而使用它的低4位來(lái)表示編碼下一個(gè)非“0”系數(shù)所需要的位數(shù)，跟在它后面的是量化交流系數(shù)的數(shù)值。...5.交流系數(shù)的編碼階段...416.熵編碼階段使用熵編碼還可以對(duì)DPCM編碼后的直流系數(shù)和RLE編碼后的交流A系數(shù)作進(jìn)一步的壓縮。在JPEG有損壓縮算法中，使用霍夫曼編碼器來(lái)減少熵。使用霍夫曼編碼器的理由是可以使用很簡(jiǎn)單的查表方法進(jìn)行編碼。壓縮數(shù)據(jù)符號(hào)時(shí)，霍夫曼編碼器對(duì)出現(xiàn)頻度比較高的符號(hào)分配比較短的代碼，而對(duì)出現(xiàn)頻度較低的符號(hào)分配比較長(zhǎng)的代碼。這種可變長(zhǎng)度的霍夫曼碼表可以事先進(jìn)行定義。...6.熵編碼階段...42MPEG標(biāo)準(zhǔn)是面向運(yùn)動(dòng)圖像壓縮的一個(gè)系列標(biāo)準(zhǔn)。多媒體運(yùn)動(dòng)圖像和伴音的數(shù)據(jù)壓縮編碼標(biāo)準(zhǔn)，即MPEG標(biāo)準(zhǔn)，實(shí)際上包括四個(gè)部分，MPEG視頻、MPEG音頻和MPEG系統(tǒng)、MPEG測(cè)試。...MPEG標(biāo)準(zhǔn)是面向運(yùn)動(dòng)圖像壓縮的一個(gè)系列標(biāo)準(zhǔn)。...43MPEG標(biāo)準(zhǔn)簡(jiǎn)介最初MPEG專(zhuān)家組的工作項(xiàng)目是3個(gè)，即在1.5Mbps，10Mbps，40Mbps傳輸速率下對(duì)圖像編碼，分別命名為MPEG-1，MPEG-2，MPEG-3。MPEG-3后被取消.為了滿(mǎn)足不同的應(yīng)用要求，MPEG又將陸續(xù)增加其他一些標(biāo)準(zhǔn)MPEG-4，MPEG-7，MPEG-21。...MPEG標(biāo)準(zhǔn)簡(jiǎn)介最初MPEG專(zhuān)家組的工作項(xiàng)目是3個(gè)，即在144

MPEG算法編碼過(guò)程和解碼過(guò)程是一種非鏡象對(duì)稱(chēng)算法(不對(duì)稱(chēng))，解碼過(guò)程要比編碼過(guò)程相對(duì)簡(jiǎn)單些。MPEG-1和MPEG-2只規(guī)定了解碼的方案，重點(diǎn)將解碼算法標(biāo)準(zhǔn)化。最近幾年，隨著MPC性能的提高，軟件解壓功能也逐漸得到支持。...MPEG算法編碼過(guò)程和解碼過(guò)程是一種非鏡象對(duì)稱(chēng)算法(不對(duì)45在MPEG中將圖像分為3種類(lèi)型：I圖像：也叫I幀，就是靜態(tài)圖像，用JPEG幀內(nèi)壓縮的方法得到；P圖像

用最近的前一個(gè)I圖像(或P圖像)預(yù)測(cè)編碼得到(前向預(yù)測(cè))，稱(chēng)為前向預(yù)測(cè)；而且可以作為下一個(gè)B幀或P幀的照?qǐng)D像。B圖像B圖像在預(yù)測(cè)時(shí)，既可使用了前一個(gè)圖像作參照，也可使用下一個(gè)圖像做參照或同時(shí)使用前后兩個(gè)圖像作為參照?qǐng)D像(雙向預(yù)測(cè))。B圖像壓縮比最大，I圖像壓縮比最小。幀間編碼技術(shù)...在MPEG中將圖像分為3種類(lèi)型：幀間編碼技術(shù)...46運(yùn)動(dòng)視頻流的組成1、允許編碼端自行選擇I幀的使用頻率和在視頻流的位置，典型每秒使用2次。2、允許編碼端自行選擇任何兩幀參考圖像（I，P）之間的B幀。插入兩個(gè)B幀較為適宜。...運(yùn)動(dòng)視頻流的組成1、允許編碼端自行選擇I幀的使用頻率和在視頻47運(yùn)動(dòng)圖像的顯示順序與傳輸順序不同顯示的順序：1234567

IBBPBBP

傳輸?shù)捻樞颍?423756

IPBBPBB

MPEG編碼器需對(duì)上述圖像重新排序，以便解碼器高效工作，因?yàn)閰⒄請(qǐng)D像必須先于B圖像恢復(fù)之前恢復(fù)。...運(yùn)動(dòng)圖像的顯示順序與傳輸順序不同顯示的順序：123448壓縮技術(shù)比較...壓縮技術(shù)比較...49音頻壓縮編碼標(biāo)準(zhǔn)及應(yīng)用范圍

G.7111972年CCITT為電話(huà)質(zhì)量和語(yǔ)音壓縮制定。其速率為

64kb/s，使用非線(xiàn)性量化技術(shù)，主要用于公共電話(huà)網(wǎng)中。

G.7221988年CCITT為調(diào)幅廣播質(zhì)量的音頻信號(hào)壓縮制定，它使用 子帶編碼(SBC)方案，其濾波器組將輸入信號(hào)分成高低兩個(gè)子帶信 號(hào)，然后分別使用ADPCM進(jìn)行編碼。G.722能將224kb/s的調(diào)幅廣播 質(zhì)量的音頻信號(hào)壓縮為64kb/s，主要用于視聽(tīng)多媒體和會(huì)議電視 等。

G.7231996年ITU-T通過(guò)了——“用于多媒體傳輸?shù)?.3kb/s或6.3kb/s

雙速率話(huà)音編碼”標(biāo)準(zhǔn)。它采用多脈沖激勵(lì)最大似然量化(MP-MLQ)

算法，此標(biāo)準(zhǔn)可應(yīng)用于視頻電話(huà)及IP傳輸電話(huà)等方面。

G.728 使用基于低時(shí)延碼本激勵(lì)線(xiàn)性預(yù)測(cè)編碼(LD-CELP)算法，其速率為

16kb/s，主要用于公共電話(huà)網(wǎng)中。

G.729它使用8kb/s的共軛結(jié)構(gòu)代數(shù) 碼激勵(lì)線(xiàn)性預(yù)測(cè)(CS-ACELP)算法，此標(biāo)準(zhǔn)在無(wú)線(xiàn)移動(dòng)網(wǎng)、數(shù)字多 路復(fù)用系統(tǒng)和計(jì)算機(jī)通信系統(tǒng)中應(yīng)用。...音頻壓縮編碼標(biāo)準(zhǔn)及應(yīng)用范圍...50運(yùn)動(dòng)視頻定量要求技術(shù)或標(biāo)準(zhǔn)未壓縮的Mbps壓縮的Mbps質(zhì)量HDTV 1920Xl080／60fps未壓縮的壓縮的演插室質(zhì)量數(shù)字電視未壓縮的

壓縮的常規(guī)廣播質(zhì)量電視

VCR品質(zhì)

視頻會(huì)議MPEG一2ITU-R601MPEG-2MPEG-2 MPEG-1 H.261

2000一166一一一一一25一30

3一6 2一4 1．2 0．1...運(yùn)動(dòng)視頻定量要求技術(shù)或標(biāo)準(zhǔn)未壓縮的Mbps51視頻壓縮編碼標(biāo)準(zhǔn)及其應(yīng)用范圍

目前，由國(guó)際標(biāo)準(zhǔn)化組織(ISO)和國(guó)際電聯(lián)(ITU-T)

正式公布的視頻壓縮編碼標(biāo)準(zhǔn)中，有MPEG系列和

H.26x系列建議。...視頻壓縮編碼標(biāo)準(zhǔn)及其應(yīng)用范圍...52

H.261

CCITT制定的國(guó)際上第一個(gè)視頻壓縮標(biāo)準(zhǔn)，主要用于電視電話(huà)和會(huì)議電視，以滿(mǎn)足ISDN日益發(fā)展的需要。

H.261視頻壓縮算法的核心是運(yùn)動(dòng)估值預(yù)測(cè)和DCT編碼，其許多技術(shù)(包括視頻數(shù)據(jù)格式、運(yùn)動(dòng)估算與補(bǔ)償、DCT變換、量化和熵編碼)都被后來(lái)的MPEG-1和MPEG-2所借鑒和采用。... H.261...53

MPEG-1標(biāo)準(zhǔn)

“運(yùn)動(dòng)圖像和伴隨聲音的編碼——用于速率約在1.5Mb/s以下的數(shù)字存儲(chǔ)媒體”。 主要用于多媒體存儲(chǔ)與再現(xiàn)，如VCD等。

MPEG-1采用CIF視頻格式，幀速率為25幀/秒或30幀/秒，碼率為1.5Mb/s(其中視頻約1.2Mb/s，音頻約0.3Mb/s)。MPEG-1為了追求更高的壓縮率，同時(shí)滿(mǎn)足多媒體等應(yīng)用所需的隨機(jī)存取要求，將視頻圖象序列劃分為I幀、P幀和B幀，根據(jù)不同的圖象類(lèi)型而不同對(duì)待。 該標(biāo)準(zhǔn)草案于1991年11月完成，1992年11月正式通過(guò)。... MPEG-1標(biāo)準(zhǔn)...54

MPEG-2標(biāo)準(zhǔn)

基本算法也是運(yùn)動(dòng)補(bǔ)償?shù)念A(yù)測(cè)和帶有DCT的幀間內(nèi)變長(zhǎng)編碼。 繼MPEG-1之后，MPEG制定的又一視頻壓縮標(biāo)準(zhǔn)（ISO/IEC13818)（其中視頻部分即為H.262）。它能適用于更廣的應(yīng)用領(lǐng)域，主要包括數(shù)字存儲(chǔ)媒體，廣播電視和通信。制定MPEG-2標(biāo)準(zhǔn)的出發(fā)點(diǎn)是保持通用性，適用于廣泛的應(yīng)用領(lǐng)域、比特率、分辨率、質(zhì)量和服務(wù)。MPEG-2適于高于2Mb/s的視頻壓縮，這包括了原打算為HDTV的發(fā)展而制定MPEG-3標(biāo)準(zhǔn)的內(nèi)容。 根據(jù)MPEG-2的標(biāo)準(zhǔn)CCIR601格式(702×576×25幀)的信號(hào)可壓縮到4Mb/s～6Mb/s，而HDTV格式(1280×720×60幀)的信號(hào)可壓縮到20Mb/s左右。... MPEG-2標(biāo)準(zhǔn)...55

H.263及H.263+

H.263是ITU-T的關(guān)于低于64kb/s比特率的窄帶通道視頻編碼建議，其目的是能在現(xiàn)有的電話(huà)網(wǎng)上傳輸活動(dòng)圖象。 由于H.263是面向低速信道的，所以必須在幀頻和圖象失真之間作出選擇。H.263是在H.261建議的基礎(chǔ)上發(fā)展起來(lái)的，其信源編碼算法仍然是幀間預(yù)測(cè)/DCT混合編碼，但H.263與H.261不同的是，它采用半象素的分辨率進(jìn)行運(yùn)動(dòng)補(bǔ)償，它處理的圖象格式可以覆蓋從sub-QCIF到16CIF，而且，H.263還提供了4種可協(xié)商選擇的編碼方法：無(wú)限制范圍的運(yùn)動(dòng)矢量、基于語(yǔ)法的算法編碼方法、先進(jìn)預(yù)測(cè)和PB幀。... H.263及H.263+...56

MPEG-4標(biāo)準(zhǔn)

1994年，MPEG專(zhuān)家組正式開(kāi)始制定MPEG-4標(biāo)準(zhǔn)，到1998年11月將發(fā)布MPEG-4視頻國(guó)際標(biāo)準(zhǔn)草案。它主要是針對(duì)多媒體應(yīng)用的，對(duì)可移動(dòng)性的視頻編碼速率為5～64kb/s，而對(duì)影視應(yīng)用最高速率可達(dá)2Mb/s。MPEG-4標(biāo)準(zhǔn)的突出特點(diǎn)是對(duì)音視頻數(shù)據(jù)采用基于內(nèi)容(Content-based)的操作、存取及傳輸。 為了達(dá)到此目的，MPEG-4引入了“視頻對(duì)象”(VO)的概念。這樣可把視頻流中的每一幀分割成任意形狀的圖象區(qū)域—稱(chēng)為視頻對(duì)象平面(VOP)，然后根據(jù)每一VOP的特點(diǎn)和需要，分別進(jìn)行編碼。要獲得VOP，必須使用圖象分割技術(shù)，如果將紋理信息與運(yùn)動(dòng)信息結(jié)合起來(lái)，則可產(chǎn)生較好的效果。

... MPEG-4標(biāo)準(zhǔn)...57

MPEG-4標(biāo)準(zhǔn)

MPEG-4標(biāo)準(zhǔn)是一個(gè)開(kāi)放、靈活、可擴(kuò)展的結(jié)構(gòu)形式，可隨時(shí)加入新的、有效的算法模板，并可根據(jù)不同的應(yīng)用要求現(xiàn)場(chǎng)配置解碼器。它具有如下一些新功能：?基于內(nèi)容的交互性(Content-basedinteractivity)：即可進(jìn)行基于內(nèi)容的多媒體數(shù)據(jù)訪(fǎng)問(wèn)和比特流編輯，并可混合自然和人工數(shù)據(jù)編碼。?高壓縮率：這不僅表現(xiàn)在可提高編碼效率，在移動(dòng)環(huán)境下可傳輸高質(zhì)量圖象，而且能對(duì)多個(gè)并發(fā)數(shù)據(jù)流進(jìn)行編碼，使其能有效地描述三維自然景物。?易錯(cuò)環(huán)境中的抗錯(cuò)性(Robustness)：指可應(yīng)用于各種有線(xiàn)、無(wú)線(xiàn)網(wǎng)中，特別是提供了在易錯(cuò)的移動(dòng)環(huán)境下、低比特率應(yīng)用中的對(duì)抗殘留錯(cuò)誤的能力。?基于內(nèi)容的可擴(kuò)縮性(Content-basedscalability)：即可給圖象中的各個(gè)對(duì)象分配優(yōu)先級(jí)，其中，比較重要的對(duì)象用較高的空間和時(shí)間分辨率表示。基于內(nèi)容的可擴(kuò)縮性是MPEG-4的核心。... MPEG-4標(biāo)準(zhǔn)...58

MPEG-7標(biāo)準(zhǔn)

隨著信息的增多，尋找到所需要的信息越來(lái)越困難。目前，基于文本(text-based)型式的搜索引擎已廣泛使用，但基于視聽(tīng)內(nèi)容的檢索還很困難。MPEG-7正是為滿(mǎn)足這方面的需求而制定的，主要用于基于內(nèi)容的多媒體檢索。

MPEG-7又稱(chēng)為“多媒體內(nèi)容描述接口”，它規(guī)定了一套可用于描述各種多媒體信息的描述符的標(biāo)準(zhǔn)。這些描述與多媒體信息的內(nèi)容本身一起，將支持用戶(hù)對(duì)其感興趣的資源進(jìn)行快速、有效的檢索。

MPEG-7標(biāo)準(zhǔn)建立在其它標(biāo)準(zhǔn)表示的基礎(chǔ)上，但MPEG-7描述符不依賴(lài)于被描述內(nèi)容的編碼和存儲(chǔ)方式。MPEG-7只提供內(nèi)容的描述，而不是內(nèi)容本身。

MPEG-7不包括特征提取(分析)和搜索引擎(應(yīng)用)部分。其原因，一是為了促進(jìn)各公司和研究所間的競(jìng)爭(zhēng)，其二是為以后各種新技術(shù)的發(fā)展留下余地。... MPEG-7標(biāo)準(zhǔn)...59MPEG-7標(biāo)準(zhǔn)應(yīng)用領(lǐng)域

數(shù)字化圖書(shū)館(包括圖象分類(lèi)目錄、音樂(lè)字典等)； 多媒體目錄服務(wù)(例如黃頁(yè))； 廣播式媒體選擇(包括個(gè)人電子新聞服務(wù)、媒體著作等)； 潛在的應(yīng)用領(lǐng)域，如旅游信息、文化服務(wù)、地理信息系統(tǒng)等。

MPEG-7已在2001年11月形成國(guó)際標(biāo)準(zhǔn)。目前，雖有許多公司和研究機(jī)構(gòu)，如IBM、MIT已開(kāi)始對(duì)其中的關(guān)鍵技術(shù)進(jìn)行研究并已取得一些成果，但離實(shí)際應(yīng)用還有相當(dāng)距離。...MPEG-7標(biāo)準(zhǔn)應(yīng)用領(lǐng)域...60MPEG－21

MPEG－21致力于為多媒體傳輸和使用定義一個(gè)標(biāo)準(zhǔn)化的開(kāi)放框架。這種框架將在開(kāi)放的市場(chǎng)中為內(nèi)容提供商和業(yè)務(wù)提供商創(chuàng)造同等的機(jī)會(huì)。同時(shí)，這將在一種互操作的模式下為用戶(hù)提供更豐富的信息，用戶(hù)將因此而受益。

MPEG－21可以總結(jié)如下：一個(gè)多媒體框架，它可以在廣闊的范圍里，為不同的網(wǎng)絡(luò)用戶(hù)提供透明的和可不斷擴(kuò)展的多媒體資源。

...MPEG－21

MPEG－21致力于為多媒體傳輸和使用61數(shù)據(jù)壓縮基礎(chǔ)...數(shù)據(jù)壓縮基礎(chǔ)...62數(shù)據(jù)壓縮編碼技術(shù)概述多媒體數(shù)據(jù)壓縮的必要性和可行性衡量多媒體數(shù)據(jù)壓縮技術(shù)的指標(biāo)： 壓縮比 算法簡(jiǎn)單，壓縮解壓縮速度快 盡可能地恢復(fù)原始數(shù)據(jù)壓縮方法分類(lèi) 無(wú)損壓縮：Huffman編碼、游程編碼、算術(shù)編碼、LZW編碼 有損壓縮：預(yù)測(cè)編碼、變換編碼、模型編碼、基于重要性的編 碼、混合編碼新一代的數(shù)據(jù)壓縮方法：矢量量化和子代編碼、基于模型的壓 縮、分形壓縮、小波變換壓縮等等。...數(shù)據(jù)壓縮編碼技術(shù)概述...63

壓縮的必要性

音頻、視頻的數(shù)據(jù)量很大，如果不進(jìn)行處理，計(jì)算機(jī)系統(tǒng)幾乎無(wú)法對(duì)它進(jìn)行存取和交換。 例如，一幅具有中等分辨率（640×480）的真彩色圖像（24b/像素），它的數(shù)據(jù)量約為7.37Mb/幀，一個(gè)700MB（Byte）的硬盤(pán)只能存放約100幀圖像。若要達(dá)到每秒25幀的全動(dòng)態(tài)顯示要求，每秒所需的數(shù)據(jù)量為184Mb，而且要求系統(tǒng)的數(shù)據(jù)傳輸率必須達(dá)到184Mb/s。對(duì)于聲音也是如此，若采用16b樣值的PCM編碼，采樣速率選為44.1kHZ，則雙聲道立體聲聲音每秒將有176KB的數(shù)據(jù)量。... 壓縮的必要性...64數(shù)據(jù)壓縮的好處

時(shí)間域壓縮──迅速傳輸媒體信源 頻率域壓縮──并行開(kāi)通更多業(yè)務(wù) 空間域壓縮──降低存儲(chǔ)費(fèi)用 能量域壓縮──降低發(fā)射功率...數(shù)據(jù)壓縮的好處...65數(shù)據(jù)壓縮技術(shù)實(shí)現(xiàn)的衡量標(biāo)準(zhǔn)

壓縮比要大 恢復(fù)后的失真小 壓縮算法要簡(jiǎn)單、速度快 壓縮能否用硬件實(shí)現(xiàn)...數(shù)據(jù)壓縮技術(shù)實(shí)現(xiàn)的衡量標(biāo)準(zhǔn)...66多媒體數(shù)據(jù)壓縮技術(shù)分類(lèi)

平均信息量編碼──可逆壓縮──去冗 余──統(tǒng)計(jì)特性 源編碼──不可逆壓縮──有失真編碼 特征提取等 兩種壓縮技術(shù)不互斥，兩種壓縮技 術(shù)的結(jié)合，可以達(dá)到最高可能的壓縮率。...多媒體數(shù)據(jù)壓縮技術(shù)分類(lèi)...67

多媒體數(shù)據(jù)壓縮技術(shù)分類(lèi)

無(wú)損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)完全相同；無(wú)損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。

有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)有所不同，但不會(huì)使人對(duì)原始資料表達(dá)的信息造成誤解。有損壓縮適用于重構(gòu)信號(hào)不一定非要和原始信號(hào)完全相同的場(chǎng)合。... 多媒體數(shù)據(jù)壓縮技術(shù)分類(lèi)...68無(wú)損數(shù)據(jù)壓縮

主要介紹目前用得最多和技術(shù)最成熟的 無(wú)損壓縮編碼技術(shù)，包括： 霍夫曼編碼 算術(shù)編碼 游程編碼RLE 詞典編碼LZW...無(wú)損數(shù)據(jù)壓縮...69

霍夫曼(Huffman)編碼

霍夫曼(Huffman)在1952年提出了另一種編碼方法，即從 下到上的編碼方法。

幾個(gè)個(gè)問(wèn)題值得注意：1.霍夫曼碼沒(méi)有錯(cuò)誤保護(hù)功能；2.霍夫曼碼是可變長(zhǎng)度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼;3.接收端需保存一個(gè)與發(fā)送端相同的霍夫曼碼表。... 霍夫曼(Huffman)編碼...70字母頻率編碼A25%01B15%110C10%111D20%10E30%00霍夫曼(Huffman)編碼...字母頻率編碼A25%01B15%110C10%111D20%71信源消減信源符號(hào)集B={b1,b2,b3,b4}

概率矢量u={0.1，0.38，0.22，0.3}

步驟1：信源消減...信源消減...72步驟2：對(duì)信源符號(hào)賦值平均碼長(zhǎng)Lavg=1.946...步驟2：對(duì)信源符號(hào)賦值...73霍夫曼碼的特點(diǎn)1，塊碼（組碼）

2，即時(shí)碼

3，唯一可解碼...霍夫曼碼的特點(diǎn)...74霍夫曼碼改型亞最優(yōu)犧牲編碼效率來(lái)?yè)Q取編碼速度截?cái)嗷舴蚵a前M個(gè)符號(hào)用霍夫曼編碼其余用前綴碼+定長(zhǎng)碼（自然碼）平移霍夫曼碼分組：相同符號(hào)數(shù)用霍夫曼編碼編第1組其余組用平移符號(hào)+第一組霍夫曼碼......75霍夫曼碼改型

......76霍夫曼(Huffman)編碼 依賴(lài)于信源的統(tǒng)計(jì)特性，必須先統(tǒng)計(jì)得到信源 的概率特性才能編碼，這就限制了實(shí)際的應(yīng)用。 缺乏構(gòu)造性，即它不能用某種數(shù)學(xué)方法建立起 消息和碼字之間的一一對(duì)應(yīng)關(guān)系，而只能通過(guò) 某種查表的方法建立起它們的對(duì)應(yīng)關(guān)系。 如果消息數(shù)目很多，那么所需存儲(chǔ)的碼表也很 大，這將影響系統(tǒng)的存儲(chǔ)量及編、譯碼速度。...霍夫曼(Huffman)編碼...77練習(xí)初始信源：a1：0.1，a2：0.4，a3:：0.06，a4:0.1，a5：0.04，a6：0.3....練習(xí)初始信源：...78練習(xí)...練習(xí)...79算術(shù)編碼只需要用到加法和位移運(yùn)算從整個(gè)符號(hào)序列出發(fā)算術(shù)編碼不再是塊碼，采用遞推形式連續(xù)編碼

...算術(shù)編碼...80算術(shù)編碼的特點(diǎn)：1種從整個(gè)符號(hào)序列出發(fā)，采用遞推形式連續(xù)編碼的方法不存在源符號(hào)和碼字間的一一對(duì)應(yīng)關(guān)系1個(gè)算術(shù)碼字要賦給整個(gè)信源符號(hào)序列，而每個(gè)碼字本身確定了0和1之間的1個(gè)實(shí)數(shù)區(qū)間算術(shù)編碼過(guò)程只需用到加法和移位運(yùn)算

...算術(shù)編碼的特點(diǎn)：...81算術(shù)編碼

b1=0.1b2=0.38b3=0.22b4=0.30.0000100120.0351562510碼串：b1；b2；b3；b4...算術(shù)編碼b1=0.1b2=0.38b3=0.22b4=0.382

算術(shù)編碼在算術(shù)編碼中需要注意的幾個(gè)問(wèn)題：1.由于實(shí)際計(jì)算機(jī)精度不可能無(wú)限長(zhǎng)，運(yùn)算中溢出是明顯的問(wèn)題，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此可使用比例縮放法解決。2.算術(shù)編碼器對(duì)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在[0,1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。3.算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。... 算術(shù)編碼...83算數(shù)編碼練習(xí)初始信源：a1：0.1，a2：0.4，a3：0.5，碼串：a1，a1，a2，a3...算數(shù)編碼練習(xí)初始信源：...84

游程RLE編碼RLE(runlengthencoding）編碼的概念

用RLE編碼方法得到的代碼為：80315084180。代碼中用黑體表示的數(shù)字是行程長(zhǎng)度，黑體字后面的數(shù)字代表象素的顏色值。例如黑體字50代表有連續(xù)50個(gè)象素具有相同的顏色值，它的顏色值是8。 譯碼時(shí)按照與編碼時(shí)采用的相同規(guī)則進(jìn)行，還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。... 游程RLE編碼...85

詞典編碼

詞典編碼的思想

第一類(lèi)詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過(guò)，然后用已經(jīng)出現(xiàn)過(guò)的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過(guò)的字符串的“指針”。... 詞典編碼...86詞典編碼

詞典編碼的思想

第二類(lèi)算法的想法 是企圖從輸入的數(shù)據(jù)中 創(chuàng)建一個(gè)“短語(yǔ)詞典

(dictionaryofthe phrases)”，這種短語(yǔ)可 以是任意字符的組合。 編碼數(shù)據(jù)過(guò)程中當(dāng)遇到 已經(jīng)在詞典中出現(xiàn)的“短 語(yǔ)”時(shí)，編碼器就輸出這 個(gè)詞典中的短語(yǔ)的“索引 號(hào)”，而不是短語(yǔ)本身。...詞典編碼...87

詞典編碼

J.Ziv和A.Lempel在1978年首次發(fā)表了介紹上述第二類(lèi)編碼方法的文章。在他們的研究基礎(chǔ)上，TerryA.Welch在1984年發(fā)表了改進(jìn)這種編碼算法的文章，因此把這種編碼方法稱(chēng)為L(zhǎng)ZW(Lempel-ZivWalch)壓縮編碼，

LZW算法

在編碼原理上，LZW與LZ78相比有如下差別：①LZW只輸出代表詞典中的綴-符串(String)的碼字(codeword)。這就意味在開(kāi)始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。②由于所有可能出現(xiàn)的單個(gè)字符都事先包含在詞典中，每個(gè)編碼步驟開(kāi)始時(shí)都使用一字符前綴(one-characterprefix)，因此在詞典中搜索的第1個(gè)綴-符串有兩個(gè)字符。

LZW編碼是圍繞稱(chēng)為詞典的轉(zhuǎn)換表來(lái)完成的。... 詞典編碼...88

詞典編碼

LZW算法

LZW編碼器使用了一種很實(shí)用的分析(parsing)算法，稱(chēng)為貪婪分析算法(greedyparsingalgorithm)。在貪婪分析算法中，每一次分析都要串行地檢查來(lái)自字符流(Charstream)的字符串，從中分解出已經(jīng)識(shí)別的最長(zhǎng)的字符串，也就是已經(jīng)在詞典中出現(xiàn)的最長(zhǎng)的前綴(Prefix)。用已知的前綴(Prefix)加上下一個(gè)輸入字符C也就是當(dāng)前字符(Currentcharacter)作為該前綴的擴(kuò)展字符，形成新的擴(kuò)展字符串——綴-符串(String)：Prefix.C。這個(gè)新的綴-符串(String)是否要加到詞典中，還要看詞典中是否存有和它相同的綴-符串String。如果有，那么這個(gè)綴-符串(String)就變成前綴(Prefix)，繼續(xù)輸入新的字符，否則就把這個(gè)綴-符串(String)寫(xiě)到詞典中生成一個(gè)新的前綴(Prefix)，并給一個(gè)代碼。... 詞典編碼...89

詞典編碼

LZW算法

LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因?yàn)樗恍枰獔?zhí)行那么多的綴-符串比較操作。對(duì)LZW算法進(jìn)一步的改進(jìn)是增加可變的碼字長(zhǎng)度，以及在詞典中刪除老的綴-符串。在GIF圖像格式和UNIX的壓縮程序中已經(jīng)采用了這些改進(jìn)措施之后的LZW算法。

LZW算法取得了專(zhuān)利，專(zhuān)利權(quán)的所有者是美國(guó)的一個(gè)大型計(jì)算機(jī)公司—Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產(chǎn)公司之外，可以免費(fèi)使用LZW算法。... 詞典編碼...90

詞典編碼壓縮算法基于以下的中心思想

1. 為原始文本文件中的每個(gè)字母分配一個(gè)代碼并存儲(chǔ)到 一個(gè)代碼表中

2. 設(shè)置一個(gè)循環(huán)，每次從文件中獲取一個(gè)字符。將使用 一個(gè)緩沖字符串，把從文件中取出的字符連接在一起

3. 在每次循環(huán)中，讀取一個(gè)字符接到緩沖字符串的后 面，形成一個(gè)新的臨時(shí)字符串。如果該臨時(shí)字符串以前 曾經(jīng)出現(xiàn)過(guò)就把它移到緩沖區(qū)里

4. 如果臨時(shí)字符串不出現(xiàn)在代碼表中，就為它分配一個(gè) 代碼，并把字符串和代碼存儲(chǔ)到代碼表中，同時(shí)發(fā)送緩 沖字符串所對(duì)應(yīng)的代碼 重新設(shè)置緩沖字符串為剛剛讀取的單個(gè)字符。... 詞典編碼...91JPEG算法概要JPEG(JointPhotographicExpertsGroup)是一個(gè)由ISO和IEC兩個(gè)組織機(jī)構(gòu)聯(lián)合組成的一個(gè)專(zhuān)家組，負(fù)責(zé)制定靜態(tài)的數(shù)字圖像數(shù)據(jù)壓縮編碼標(biāo)準(zhǔn)，這個(gè)專(zhuān)家組開(kāi)發(fā)的算法稱(chēng)為JPEG算法，并且成為國(guó)際上通用的標(biāo)準(zhǔn)，因此又稱(chēng)為JPEG標(biāo)準(zhǔn)。JPEG是一個(gè)適用范圍很廣的靜態(tài)圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)，既可用于灰度圖像又可用于彩色圖像。使用有損壓縮算法時(shí)，在壓縮比為25:1的情況下，壓縮后還原得到的圖像與原始圖像相比較，非圖像專(zhuān)家難于找出它們之間的區(qū)別，因此得到了廣泛的應(yīng)用。V-CD、DVD-Video。

圖像和視頻的壓縮技術(shù)...JPEG算法概要JPEG(JointPhotographi92

圖像和視頻的壓縮技術(shù)JPEG壓縮的三個(gè)階段

離散余弦變換（DiscreteCosineTransform,DCT） 量化（Quantization） 編碼階段（EncodingPhase）壓縮圖像原始圖像DCT階段量化階段編碼階段... 圖像和視頻的壓縮技術(shù)壓縮圖像原始圖像DCT階段量化階段編碼931.離散余弦變換 下面對(duì)正向離散余弦變換(FDCT)變換作幾點(diǎn)說(shuō)明。 (1)對(duì)每個(gè)單獨(dú)的彩色圖像分量，把整個(gè)分量圖像分成8×8的圖像塊，并作為兩維離散余弦變換DCT的輸入。通過(guò)DCT變換，把能量集中在少數(shù)幾個(gè)系數(shù)上。

...1.離散余弦變換...94離散余弦變換階段P(x,y)經(jīng)DCT變換之后，T(0，0)是直流系數(shù)，其他為交流系數(shù)。在計(jì)算兩維的DCT變換時(shí)，可把兩維的DCT變換變成一維的DCT變換...離散余弦變換階段P(x,y)經(jīng)DCT變換之后，T(0，0)95圖像和視頻的壓縮技術(shù)2.量化階段量化是對(duì)經(jīng)過(guò)FDCT變換后的頻率系數(shù)進(jìn)行量化。量化的目的是減小非“0”系數(shù)的幅度以及增加“0”值系數(shù)的數(shù)目。量化是圖像質(zhì)量下降的最主要原因Q=integer(T/U)其中：DCT變換系數(shù)T；U是量化器步長(zhǎng)，它是量化表的元素。...圖像和視頻的壓縮技術(shù)其中：DCT變換系數(shù)T；...96圖像和視頻的壓縮技術(shù)

量化器步長(zhǎng)1520-480-80-7013579111315T=00000000357911131517-480380-30205791113151719U=

00000000-80-30130-10 0000 0000-7 020-1070 0000 0000

79111315171921 911131517192123111315171921232513151719212325271517192123252729...圖像和視頻的壓縮技術(shù)1520-480-897Q=圖像和視頻的壓縮技術(shù)

根據(jù)公式，量化后將得到

1520-100-10-10 00000000-100400000

00-10 00-10 00000000001000000000000000000000...Q=圖像和視頻的壓縮技術(shù)-10040098對(duì)于有損壓縮算法，JPEG算法使用均勻量化器進(jìn)行量化，量化步長(zhǎng)是按照系數(shù)所在的位置和每種顏色分量的色調(diào)值來(lái)確定。因?yàn)槿搜蹖?duì)亮度信號(hào)比對(duì)色差信號(hào)更敏感，因此使用了兩種量化表：亮度量化表和色差量化表。...對(duì)于有損壓縮算法，JPEG算法使用均勻量化器進(jìn)行量化993.Z字形編碼階段。量化后的系數(shù)要重新編排，目的是為了增加連續(xù)的“0”系數(shù)的個(gè)數(shù)，就是“0”的游程長(zhǎng)度，方法是按照Z(yǔ)字形的式樣編排。這樣就把一個(gè)8×8的矩陣變成一個(gè)1×64的矢量。編碼階段152

0-10

0 -1 0 -1 000000000-10

0 0 0 0 0 0 000000000-1 0 0 0 0 0 0 000000000-1 0 0 0 0 0 0 000000000...3.Z字形編碼階段。編碼階段1520-100-10-10.1004.直流系數(shù)的編碼階段 8×8圖像塊經(jīng)過(guò)DCT變換之后得到的直流系數(shù)有兩個(gè)特點(diǎn)：一是系數(shù)的數(shù)值比較大，二是相鄰8×8圖像塊的直流系數(shù)值變化不大。 根據(jù)這個(gè)特點(diǎn)，JPEG算法使用了差分脈沖編碼調(diào)制(DPCM)技術(shù)，對(duì)相鄰圖像塊之間的直流系數(shù)的差值(Delta)進(jìn)行編碼，

Delta＝DC(0,0)k-DC(0,0)k-1

...4.直流系數(shù)的編碼階段...1015.交流系數(shù)的編碼階段量化交流系數(shù)的特點(diǎn)是1×64矢量中包含有許多“0”系數(shù)，并且許多“0”是連續(xù)的，因此使用非常簡(jiǎn)單和直觀(guān)的游程長(zhǎng)度編碼(RLE)對(duì)它們進(jìn)行編碼。JPEG使用了1個(gè)字節(jié)的高4位來(lái)表示連續(xù)“0”的個(gè)數(shù)，而使用它的低4位來(lái)表示編碼下一個(gè)非“0”系數(shù)所需要的位數(shù)，跟在它后面的是量化交流系數(shù)的數(shù)值。...5.交流系數(shù)的編碼階段...1026.熵編碼階段使用熵編碼還可以對(duì)DPCM編碼后的直流系數(shù)和RLE編碼后的交流A系數(shù)作進(jìn)一步的壓縮。在JPEG有損壓縮算法中，使用霍夫曼編碼器來(lái)減少熵。使用霍夫曼編碼器的理由是可以使用很簡(jiǎn)單的查表方法進(jìn)行編碼。壓縮數(shù)據(jù)符號(hào)時(shí)，霍夫曼編碼器對(duì)出現(xiàn)頻度比較高的符號(hào)分配比較短的代碼，而對(duì)出現(xiàn)頻度較低的符號(hào)分配比較長(zhǎng)的代碼。這種可變長(zhǎng)度的霍夫曼碼表可以事先進(jìn)行定義。...6.熵編碼階段...103MPEG標(biāo)準(zhǔn)是面向運(yùn)動(dòng)圖像壓縮的一個(gè)系列標(biāo)準(zhǔn)。多媒體運(yùn)動(dòng)圖像和伴音的數(shù)據(jù)壓縮編碼標(biāo)準(zhǔn)，即MPEG標(biāo)準(zhǔn)，實(shí)際上包括四個(gè)部分，MPEG視頻、MPEG音頻和MPEG系統(tǒng)、MPEG測(cè)試。...MPEG標(biāo)準(zhǔn)是面向運(yùn)動(dòng)圖像壓縮的一個(gè)系列標(biāo)準(zhǔn)。...104MPEG標(biāo)準(zhǔn)簡(jiǎn)介最初MPEG專(zhuān)家組的工作項(xiàng)目是3個(gè)，即在1.5Mbps，10Mbps，40Mbps傳輸速率下對(duì)圖像編碼，分別命名為MPEG-1，MPEG-2，MPEG-3。MPEG-3后被取消.為了滿(mǎn)足不同的應(yīng)用要求，MPEG又將陸續(xù)增加其他一些標(biāo)準(zhǔn)MPEG-4，MPEG-7，MPEG-21。...MPEG標(biāo)準(zhǔn)簡(jiǎn)介最初MPEG專(zhuān)家組的工作項(xiàng)目是3個(gè)，即在1105

MPEG算法編碼過(guò)程和解碼過(guò)程是一種非鏡象對(duì)稱(chēng)算法(不對(duì)稱(chēng))，解碼過(guò)程要比編碼過(guò)程相對(duì)簡(jiǎn)單些。MPEG-1和MPEG-2只規(guī)定了解碼的方案，重點(diǎn)將解碼算法標(biāo)準(zhǔn)化。最近幾年，隨著MPC性能的提高，軟件解壓功能也逐漸得到支持。...MPEG算法編碼過(guò)程和解碼過(guò)程是一種非鏡象對(duì)稱(chēng)算法(不對(duì)106在MPEG中將圖像分為3種類(lèi)型：I圖像：也叫I幀，就是靜態(tài)圖像，用JPEG幀內(nèi)壓縮的方法得到；P圖像

用最近的前一個(gè)I圖像(或P圖像)預(yù)測(cè)編碼得到(前向預(yù)測(cè))，稱(chēng)為前向預(yù)測(cè)；而且可以作為下一個(gè)B幀或P幀的照?qǐng)D像。B圖像B圖像在預(yù)測(cè)時(shí)，既可使用了前一個(gè)圖像作參照，也可使用下一個(gè)圖像做參照或同時(shí)使用前后兩個(gè)圖像作為參照?qǐng)D像(雙向預(yù)測(cè))。B圖像壓縮比最大，I圖像壓縮比最小。幀間編碼技術(shù)...在MPEG中將圖像分為3種類(lèi)型：幀間編碼技術(shù)...107運(yùn)動(dòng)視頻流的組成1、允許編碼端自行選擇I幀的使用頻率和在視頻流的位置，典型每秒使用2次。2、允許編碼端自行選擇任何兩幀參考圖像（I，P）之間的B幀。插入兩個(gè)B幀較為適宜。...運(yùn)動(dòng)視頻流的組成1、允許編碼端自行選擇I幀的使用頻率和在視頻108運(yùn)動(dòng)圖像的顯示順序與傳輸順序不同顯示的順序：1234567

IBBPBBP

傳輸?shù)捻樞颍?423756

IPBBPBB

MPEG編碼器需對(duì)上述圖像重新排序，以便解碼器高效工作，因?yàn)閰⒄請(qǐng)D像必須先于B圖像恢復(fù)之前恢復(fù)。...運(yùn)動(dòng)圖像的顯示順序與傳輸順序不同顯示的順序：1234109壓縮技術(shù)比較...壓縮技術(shù)比較...110音頻壓縮編碼標(biāo)準(zhǔn)及應(yīng)用范圍

G.7111972年CCITT為電話(huà)質(zhì)量和語(yǔ)音壓縮制定。其速率為

64kb/s，使用非線(xiàn)性量化技術(shù)，主要用于公共電話(huà)網(wǎng)中。

G.7221988年CCITT為調(diào)幅廣播質(zhì)量的音頻信號(hào)壓縮制定，它使用 子帶編碼(SBC)方案，其濾波器組將輸入信號(hào)分成高低兩個(gè)子帶信 號(hào)，然后分別使用ADPCM進(jìn)行編碼。G.722能將224kb/s的調(diào)幅廣播 質(zhì)量的音頻信號(hào)壓縮為64kb/s，主要用于視聽(tīng)多媒體和會(huì)議電視 等。

G.7231996年ITU-T通過(guò)了——“用于多媒體傳輸?shù)?.3kb/s或6.3kb/s

雙速率話(huà)音編碼”標(biāo)準(zhǔn)。它采用多脈沖激勵(lì)最大似然量化(MP-MLQ)

算法，此標(biāo)準(zhǔn)可應(yīng)用于視頻電話(huà)及IP傳輸電話(huà)等方面。

G.728 使用基于低時(shí)延碼本激勵(lì)線(xiàn)性預(yù)測(cè)編碼(LD-CELP)算法，其速率為

16kb/s，主要用于公共電話(huà)網(wǎng)中。

G.729它使用8kb/s的共軛結(jié)構(gòu)代數(shù) 碼激勵(lì)線(xiàn)性預(yù)測(cè)(CS-ACELP)算法，此標(biāo)準(zhǔn)在無(wú)線(xiàn)移動(dòng)網(wǎng)、數(shù)字多 路復(fù)用系統(tǒng)和計(jì)算機(jī)通信系統(tǒng)中應(yīng)用。...音頻壓縮編碼標(biāo)準(zhǔn)及應(yīng)用范圍...111運(yùn)動(dòng)視頻定量要求技術(shù)或標(biāo)準(zhǔn)未壓縮的Mbps壓縮的Mbps質(zhì)量HDTV 1920Xl080／60fps未壓縮的壓縮的演插室質(zhì)量數(shù)字電視未壓縮的

壓縮的常規(guī)廣播質(zhì)量電視

VCR品質(zhì)

視頻會(huì)議MPEG一2ITU-R601MPEG-2MPEG-2 MPEG-1 H.261

2000一166一一一一一25一30

3一6 2一4 1．2 0．1...運(yùn)動(dòng)視頻定量要求技術(shù)或標(biāo)準(zhǔn)未壓縮的Mbps112視頻壓縮編碼標(biāo)準(zhǔn)及其應(yīng)用范圍

目前，由國(guó)際標(biāo)準(zhǔn)化組織(ISO)和國(guó)際電聯(lián)(ITU-T)

正式公布的視頻壓縮編碼標(biāo)準(zhǔn)中，有MPEG系列和

H.26x系列建議。...視頻壓縮編碼標(biāo)準(zhǔn)及其應(yīng)用范圍...113

H.261

CCITT制定的國(guó)際上第一個(gè)視頻壓縮標(biāo)準(zhǔn)，主要用于電視電話(huà)和會(huì)議電視，以滿(mǎn)足ISDN日益發(fā)展的需要。

H.261視頻壓縮算法的核心是運(yùn)動(dòng)估值預(yù)測(cè)和DCT編碼，其許多技術(shù)(包括視頻數(shù)據(jù)格式、運(yùn)動(dòng)估算與補(bǔ)償、DCT變換、量化和熵編碼)都被后來(lái)的MPEG-1和MPEG-2所借鑒和采用。... H.261...114

MPEG-1標(biāo)準(zhǔn)

“運(yùn)動(dòng)圖像和伴隨聲音的編碼——用于速率約在1.5Mb/s以下的數(shù)字存儲(chǔ)媒體”。 主要用于多媒體存儲(chǔ)與再現(xiàn)，如VCD等。

MPEG-1采用CIF視頻格式，幀速率為25幀/秒或3