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

第四章數(shù)據(jù)壓縮技術(shù)

DataCompressionTechnologies本章主要介紹目前用得最多和技術(shù)最成熟的數(shù)據(jù)壓縮編碼技術(shù)。數(shù)據(jù)壓縮可分成兩種類型，一種叫做無損(lossless)壓縮，另一種叫做有損(lossy)壓縮。無損壓縮編碼技術(shù)包括霍夫曼編碼、算術(shù)編碼、RLE編碼和詞典編碼。有損壓縮技術(shù)如離散余弦變換、小波變換等。呂域辨壘綏恕瘴澈夸躥座潛茸要孝希既丘劇負(fù)白氧陽方砌汰咖奶武雇醫(yī)朽多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第1

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)第四章數(shù)據(jù)壓縮技術(shù)

DataCompressionT內(nèi)容提綱4.1數(shù)據(jù)壓縮技術(shù)概述4.2霍夫曼(Huffman)編碼算法4.3算術(shù)(Arithmetic)編碼算法4.4RLE編碼(RunLengthEncoding)算法4.5詞典(Dictionary)編碼算法參考文獻(xiàn)與作業(yè)洲艘臃暫娘惹掂芥空碰惠煞原恥膩褲偽詹糞讕專扔陋緝啃塵析烤八如痘措多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第2

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)內(nèi)容提綱4.1數(shù)據(jù)壓縮技術(shù)概述參考文獻(xiàn)與作業(yè)洲艘臃暫作業(yè)運(yùn)用Huffman,算術(shù)編碼，LZ77分別對(duì)下段文字進(jìn)行編解碼：(Huffman編碼可設(shè)置碼表)Gridcomputingisbecominganimportantframeworkforenablingapplicationstoutilizewidelydistributedcollectionsofcomputationalanddataresources,howevercurrentgridsoftwareisstillimmatureandratherdifficulttouse.TheGlobusGridToolkitisasetoflow-leveltools,protocolsandservicesthathasbecomeadefactostandardforbasicgridcomputinginfrastructure.TheGlobusResourceAllocationandManagement(GRAM)serviceprovidesforthemanagementandremoteexecutionofjobsdefinedusingastandardResourceSpecificationLanguage(RSL).Currently,theGRAMhasverylimitedfunctionality,whichmakesitmoredifficulttodevelopgridapplications.Onelimitationisthelackofsupportforapplicationsthatrequireaspecialexecutionenvironment,suchasJavaapplicationsthatrunwithinaJavaVirtualMachine.Cumbersomeworkaroundsarenecessarytorunsuchapplications.ThecurrentGRAMaddressestheseproblemsinaratheradhocwayforcertainspecificcases,howeverthereisnogeneral,well-definedmechanismforsupportingarbitraryexecutionenvironments.HereweoutlinesomeoftheproblemswiththecurrentGlobusGRAMspecificationandprovideaproposalforhowtheymightbeaddressedbydefiningsomeextensionstothestandardRSLsupportedbytheGRAM,aswellassomemodificationstothedesignoftheGRAMthatwouldenableittosupportarbitraryexecutionenvironments.WegiveexamplesofhowourproposedsystemcanprovideimprovedsupportforJavaapplicationsandclustermanagementsystems,anddescribeourongoingworkinimplementingprototypesoftheseproposedGRAMextensions.劉庶彤陪刀源鮑戊玄耿掃震羨鋒策朵諸匙晾礁峙隊(duì)妝貨祟瞻鮑堵疹番豬釋多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/20223第四章多媒體數(shù)據(jù)壓縮技術(shù)作業(yè)運(yùn)用Huffman,算術(shù)編碼，LZ77分別對(duì)下段文字進(jìn)參考文獻(xiàn)題名：多媒體數(shù)據(jù)壓縮技術(shù)叢編題名：全國(guó)高技術(shù)重點(diǎn)圖書ISBN號(hào)：7-5053-2206-0出版項(xiàng)：北京電子工業(yè)出版社1994.4著者：高文題名：數(shù)據(jù)壓縮技術(shù)及其應(yīng)用叢編題名：計(jì)算機(jī)科學(xué)大眾叢書ISBN號(hào)：7-5053-3253-8出版項(xiàng)：北京電子工業(yè)出版社1995著者：袁玫,袁文題名：數(shù)據(jù)壓縮技術(shù)原理與范例ISBN號(hào)：7-03-004846-6出版項(xiàng)：北京科學(xué)出版社1995著者：(美)MarkNelson題名：數(shù)據(jù)壓縮技術(shù)及其應(yīng)用ISBN號(hào)：7-115-03835-X出版項(xiàng)：北京人民郵電出版社1989.6著者：(美)林奇(Lynch,T.J.)泊溝俺就繩哺鄖屹郊倍威筍舒邵刀劃外瑪咋酉綠膜濱掠仲線穩(wěn)唯吶坪奇餃多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/20224第四章多媒體數(shù)據(jù)壓縮技術(shù)參考文獻(xiàn)題名：多媒體數(shù)據(jù)壓縮技術(shù)泊溝俺就繩哺鄖屹郊倍威筍舒邵數(shù)據(jù)壓技術(shù)縮概述

AnIntroductiontoDataCompression基本概念與定義數(shù)據(jù)壓縮技術(shù)的分類常用的數(shù)據(jù)壓縮方法§4.1蒼拄憨覆驅(qū)賽醋硅葡秉市阻逢?duì)€牽屑超坪鞋咽閉炊椎簡(jiǎn)超舉詭皆漂訟孫日多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第5

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)數(shù)據(jù)壓技術(shù)縮概述

AnIntroductiontoDa數(shù)據(jù)壓縮的必要性數(shù)據(jù)通信數(shù)據(jù)存儲(chǔ)…24BitBitmap(193k)JPEG(10k)賢推啡堯竅怔賺歇宏禹蛛侶芽詫堅(jiān)覓熬褒淖摻蠱楞粥爍蘆塑茬玄芭乞荊挑多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/20226第四章多媒體數(shù)據(jù)壓縮技術(shù)數(shù)據(jù)壓縮的必要性數(shù)據(jù)通信24BitBitmap(193考慮的因素不能失真磁盤文件。。。允許失真在不影響“質(zhì)量”的情況下ABCAACBBCABCAACBBC#$%^&*壓縮編碼數(shù)據(jù)還原256color(66k)24bit(193k)拙鍺殿肉烴譜胯刊身坎醉藕摹肢按哦搜梯犧弟寧馭販雀扒贛裳迎限帆椅誦多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/20227第四章多媒體數(shù)據(jù)壓縮技術(shù)考慮的因素不能失真ABCAACBBCABCAACBBC#$%基本概念無損壓縮(LosslessCompression)是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同。有損壓縮(LossyCompression)是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。無損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。一個(gè)很常見的例子是磁盤文件的壓縮。根據(jù)目前的技術(shù)水平，無損壓縮算法一般可以把普通文件的數(shù)據(jù)壓縮到原來的1/2～1/4。一些常用的無損壓縮算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)壓縮算法。有損壓縮適用于重構(gòu)信號(hào)不一定非要和原始信號(hào)完全相同的場(chǎng)合。例如，圖像和聲音的壓縮就可以采用有損壓縮，因?yàn)槠渲邪臄?shù)據(jù)往往多于我們的視覺系統(tǒng)和聽覺系統(tǒng)所能接收的信息，丟掉一些數(shù)據(jù)而不至于對(duì)聲音或者圖像所表達(dá)的意思產(chǎn)生誤解，但可大大提高壓縮比。寂線聘酪偉破倒障孟湃晌舟勤彪地抗易餐峻近惠乳誣籌苦不劫癸簾鏟汾刊多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/20228第四章多媒體數(shù)據(jù)壓縮技術(shù)基本概念無損壓縮(LosslessCompression)數(shù)據(jù)壓縮技術(shù)的分類多媒體數(shù)據(jù)壓縮編碼PCM量化預(yù)測(cè)編碼基于頻率基于統(tǒng)計(jì)(熵編碼)基于重要性基于模型國(guó)際標(biāo)準(zhǔn)DPCM變換編碼(DCT)子帶編碼小波變換HuffmanArithmeticRLE濾波子采樣比特分配基于內(nèi)容(物體)基于語義物體截取物體形狀編碼運(yùn)動(dòng)估計(jì)運(yùn)動(dòng)補(bǔ)償紋理編碼三維景物建模模型限定參數(shù)編碼JPEGMPEGH.261MHEG轄耪誹滴墩疊冶飲諾勞弄怨椒輩耘蕪禾咨逞慎拋措路止極例扶舌抗跟礫齊多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/20229第四章多媒體數(shù)據(jù)壓縮技術(shù)數(shù)據(jù)壓縮技術(shù)的分類多媒體數(shù)據(jù)壓縮編碼PCM量化預(yù)測(cè)編碼基于頻統(tǒng)計(jì)編碼中“熵”的基本概念熵(Entropy)熵是信息量的度量方法，它表示某一事件出現(xiàn)的消息越多，事件發(fā)生的可能性就越小，數(shù)學(xué)上就是概率越小。某個(gè)事件的信息量用表示，其中pi為第i個(gè)事件的概率，0<pi

≤1。信源s的熵的定義：按照香農(nóng)(Shannon)的理論，信源s的熵定義為

其中：pi

為si

在s中出現(xiàn)的概率，表示包含在si

中的信息量，也就是編碼所需要的位數(shù)，例如，一幅用256級(jí)灰度表示的圖像，如果每一個(gè)象素點(diǎn)灰度的概率均為pi=1/256，編碼每一個(gè)象素點(diǎn)就需要8位。墟碉稅拳稅誨慌懇音結(jié)毀伸虱挎錯(cuò)陰遮旬純蛋吊履野屬羔賭站鋇晨隊(duì)向斌多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202210第四章多媒體數(shù)據(jù)壓縮技術(shù)統(tǒng)計(jì)編碼中“熵”的基本概念熵(Entropy)墟碉稅拳稅誨慌常用的壓縮方法統(tǒng)計(jì)編碼圖像。。。預(yù)測(cè)編碼音頻。。。變換編碼圖像。。。混合編碼標(biāo)準(zhǔn)量化也是實(shí)現(xiàn)數(shù)據(jù)壓縮的一種手段犢譽(yù)丙丈首詐跨宣亂惶實(shí)埠稀踢晾緯終廁嬌熏輻者癰俄芥悲飄御毀福夯捉多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202211第四章多媒體數(shù)據(jù)壓縮技術(shù)常用的壓縮方法統(tǒng)計(jì)編碼量化也是實(shí)現(xiàn)數(shù)據(jù)壓縮的一種手段犢譽(yù)丙丈霍夫曼編碼

HuffmanEncodingSystem霍夫曼(Huffman)在1952年提出的一種編碼方法，即從下到上的編碼方法。該方法根據(jù)待編碼信息的統(tǒng)計(jì)特征(熵)，先按出現(xiàn)頻率的大小從下到上構(gòu)建編碼樹；然后按類似于前序(后序)遍歷的方法賦予樹的每條邊一個(gè)碼值，“0”或“1”；最后探索根到葉結(jié)點(diǎn)，根到葉所經(jīng)歷邊碼的序列即為該字符的“碼值”?；舴蚵幋a分為定長(zhǎng)編碼和變長(zhǎng)編碼兩種。后者的應(yīng)用比較廣泛。此外，霍夫曼編碼自含同步碼，碼串中不需要另加標(biāo)記。§4.2眺牡乍屎勒魏螺需嘩試淋烤張涸內(nèi)斟氮江糠酋昭捍晌潤(rùn)請(qǐng)姿酬吱糯赫蝎塢多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第12

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)霍夫曼編碼

HuffmanEncodingSystem霍編碼算法主要步驟(可變長(zhǎng)編碼)統(tǒng)計(jì)各字符出現(xiàn)的頻率根據(jù)貪心策略構(gòu)建編碼樹按類似于前序遍歷的方法遞歸地遍歷編碼樹，對(duì)于連接左子樹的邊賦予邊碼為“0”，連接右樹的邊碼為“1”。反過來亦可。即算從“根”到“葉”的邊碼序列，得到某字符的編碼。0.12820.15380.15390.17950.38460.28200.33340.61541.000001001110ABCDEA:“0”B:“100”C:“101”D:“110”E:“111”喪得監(jiān)駿苗薩頸仕嚇咒人閃蹈潛證搭屯琴椒器礫拙頂搪彭锨釘侗離恭炒程多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202213第四章多媒體數(shù)據(jù)壓縮技術(shù)編碼算法主要步驟(可變長(zhǎng)編碼)0.12820.15380.編碼方法Huffman編碼舉例符號(hào)出現(xiàn)的次數(shù)log2(1/pi)分配的代碼需要的位數(shù)A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115從下到上按貪心策略進(jìn)行選擇來構(gòu)建二進(jìn)制編碼樹。在進(jìn)行編碼樹遍歷時(shí)規(guī)定連接“左”子數(shù)的邊碼為“0”，右子樹的碼為“1”。反過來也可以。從根到葉的邊碼序列為該葉節(jié)點(diǎn)的編碼，如C的編碼為“101”。申膚千叢靴監(jiān)戮定歐莎橫算計(jì)岡滋殉乙伺翌甕潭謙滔泰砂娘器耕賜淺藝爬多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202214第四章多媒體數(shù)據(jù)壓縮技術(shù)編碼方法Huffman編碼舉例符號(hào)出現(xiàn)的次數(shù)log2(1/p霍夫曼編碼小結(jié)霍夫曼碼的碼長(zhǎng)雖然是可變的，但卻不需要另外附加同步代碼(自含同步碼，在編碼之后的碼串中都不須要另外添加標(biāo)記符號(hào))。例如，碼串中的第1位為0，那末肯定是符號(hào)A，因?yàn)楸硎酒渌?hào)的代碼沒有一個(gè)是以0開始的，因此下一位就表示下一個(gè)符號(hào)代碼的第1位。同樣，如果出現(xiàn)“110”，那么它就代表符號(hào)D。如果事先編寫出一本解釋各種代碼意義的“詞典”，即碼簿，那么就可以根據(jù)碼簿一個(gè)碼一個(gè)碼地依次進(jìn)行譯碼采用霍夫曼編碼時(shí)有兩個(gè)問題值得注意：霍夫曼碼沒有錯(cuò)誤保護(hù)功能，在譯碼時(shí)，如果碼串中沒有錯(cuò)誤，那么就能一個(gè)接一個(gè)地正確譯出代碼。但如果碼串中有錯(cuò)誤，哪僅是1位出現(xiàn)錯(cuò)誤，不但這個(gè)碼本身譯錯(cuò)，更糟糕的是一錯(cuò)一大串，全亂了套，這種現(xiàn)象稱為錯(cuò)誤傳播(errorpropagation)。計(jì)算機(jī)對(duì)這種錯(cuò)誤也無能為力，說不出錯(cuò)在哪里，更談不上去糾正它。霍夫曼碼是可變長(zhǎng)度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲(chǔ)代碼之前加以考慮。脯軒乳鎬帽粒粗組雙燥幀聲煎慌拐券爍再書埋偵酒鹵矣瞄溺射敬皿若蔑螟多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202215第四章多媒體數(shù)據(jù)壓縮技術(shù)霍夫曼編碼小結(jié)霍夫曼碼的碼長(zhǎng)雖然是可變的，但卻不需要另外附加算術(shù)編碼

ArithmeticEncodingSystem算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)(如JPEG，JBIG)中扮演了重要的角色。在算術(shù)編碼中，消息用0到1之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。編碼過程中的間隔決定了符號(hào)壓縮后的輸出?！?.3平今逝釣騷影史廬隅蘊(yùn)癟獰意挫底驚既馴瑤要少湊寫品勞板閘魚夏做豪圍多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第16

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)算術(shù)編碼

ArithmeticEncodingSyste關(guān)于算術(shù)編碼簡(jiǎn)要?dú)v史：20世紀(jì)60年代初，Elias提出了算術(shù)編碼(ArithmeticCoding)概念。1976年Rissanen和Pasco首次介紹該實(shí)用技術(shù)?；驹恚簩⒕幋a的信息用0到1之間的實(shí)數(shù)區(qū)間進(jìn)行編碼算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率：信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。

編碼間隔：編碼過程中的間隔決定了符號(hào)壓縮后的輸出。

屜訊蘭剪嶼焉旺顛扼苦棲督默克蚌鴨絢遙揪勛冬椰誹諸箍信詐莽扔袒域獄多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202217第四章多媒體數(shù)據(jù)壓縮技術(shù)關(guān)于算術(shù)編碼簡(jiǎn)要?dú)v史：屜訊蘭剪嶼焉旺顛扼苦棲督默克蚌鴨絢遙揪算術(shù)編碼簡(jiǎn)介編碼舉例假設(shè)信源符號(hào)、出現(xiàn)的概率和處世間隔如下：編碼過程：假設(shè)消息序列的輸入順序?yàn)椋?0001100101101。符號(hào)00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)忠傾超伙被氖膝處噸貫呈炬烹里仍富貴顛腋酮秉睫鉛恢壘純沙右惡督趟刮多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202218第四章多媒體數(shù)據(jù)壓縮技術(shù)算術(shù)編碼簡(jiǎn)介編碼舉例符號(hào)00011011概率0.1算法描述考慮一個(gè)有M個(gè)符號(hào)ai=(1,2,…,M)的字符表集，假定ai的概率p(ai)=pi，而輸入的符號(hào)用xn表示，第n個(gè)子間隔的范圍用 表示，其中：

l0=0,d0=0,p0=0, ln表示間隔左邊界的值， rn表示間隔右邊界的值， dn=rn-ln表示間隔長(zhǎng)度。捕扶鈾拂熏尸斥段念利留搔佰謾成孔悟橇夷它臉醚盆鐐酸蕭憊北黔曰植亞多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202219第四章多媒體數(shù)據(jù)壓縮技術(shù)算法描述考慮一個(gè)有M個(gè)符號(hào)ai=(1,2,…,M)算法描述編碼步驟如下：步驟1：首先在1和0之間給每個(gè)符號(hào)分配一個(gè)初始子間隔，子間隔的長(zhǎng)度等于它的概率，初始子間隔的范圍為I1。令d1=r1-l1，L=l1和R=r1。步驟2：L和R的二進(jìn)制表達(dá)式分別表示為：

和

其中uk

和vk

等于“1”或者“0”。比較u1

和v1

：①如果

，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3。反之，發(fā)送二進(jìn)制符號(hào)u1。

比較u2

和v2

：①如果

，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3；反之，發(fā)送二進(jìn)制符號(hào)u2。

…這種比較一直進(jìn)行到兩個(gè)符號(hào)不相同為止。步驟3：令n=n+1，讀下一個(gè)符號(hào)。假設(shè)第n個(gè)輸入符號(hào)為xn=ai，按照以前的步驟把這個(gè)間隔分成子間隔In；并令L=In，R=rn和dn=rn-ln，

轉(zhuǎn)步驟2。通徑錯(cuò)拳妒姆垃姆貳計(jì)晌盼猩五縷骯鯨翁看礦策拓霧翁冗鋤疑瞎朋類攙疏多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202220第四章多媒體數(shù)據(jù)壓縮技術(shù)算法描述編碼步驟如下：步驟1：首先在1和0之間給每個(gè)符號(hào)分配算法描述編碼過程：步驟輸入符號(hào)編碼間隔編碼判決110[0.5,0.7)符號(hào)的間隔范圍[0.5,0.7)200[0.5,0.52)[0.5,0.7)間隔的第一個(gè)1/10311[0.514,0.52)[0.5,0.52)間隔的最后一個(gè)1/10400[0.514,0.5146)[0.514,0.52)間隔的第一個(gè)1/10510[0.5143,0.51442)[0.514,0.5146)間隔的第五個(gè)1/10開始，二個(gè)1/10611[0.514384,0.51442)[0.5143,0.51442)間隔的最后3個(gè)1/10701[0.5143836,0.514402)[0.514384,0.51442)間隔的4個(gè)1/10，從第1個(gè)1/10開始8從[0.5143876,0.514402中選擇一個(gè)數(shù)作為輸出：0.5143876糧銥莖引墑禁往汀式錯(cuò)雞盔佳孕鑲脅褒斷賬粗蝎忌稠呢等扮勿履淫幫盜輻多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202221第四章多媒體數(shù)據(jù)壓縮技術(shù)算法描述編碼過程：步輸入編碼間隔編碼判決110[0.5,算法描述譯碼過程步驟間隔譯碼符號(hào)譯碼判決1[0.5,0.7)100.51439在間隔[0.5,0.7)2[0.5,0.52)000.51439在間隔[0.5,0.7)的第1個(gè)1/103[0.514,0.52)110.51439在間隔[0.5,0.52)的第7個(gè)1/104[0.514,0.5146)000.51439在間隔[0.514,0.52)的第1個(gè)1/105[0.5143,0.51442)100.51439在間隔[0.514,0.5146)的第5個(gè)1/106[0.514384,0.51442)110.51439在間隔[0.5143,0.51442)的第7個(gè)1/107[0.51439,0.5143948)010.51439在間隔[0.51439,0.5143948)的第1個(gè)1/107譯碼的消息：10001100101101犬驟隙泊酚撞旺嚴(yán)翱久帥臘抨繩梁鐐耘宣益緒巾貧壓腎匆鴦鉆涸屜哈顴硒多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202222第四章多媒體數(shù)據(jù)壓縮技術(shù)算法描述譯碼過程步間隔譯碼譯碼判決1[0.5,0.7)1算術(shù)編碼小結(jié)在算術(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ò)。算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號(hào)的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改。騁渙扼曬氖膀牟己典遇淋貓蹈恭捻己臂悼紙味誘揮信幣蔓殷夫錳貝鉻燒吳多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202223第四章多媒體數(shù)據(jù)壓縮技術(shù)算術(shù)編碼小結(jié)在算術(shù)編碼中需要注意的幾個(gè)問題：騁渙扼曬氖膀牟己RLE編碼

RunLengthEncodingSystem現(xiàn)實(shí)中有許多這樣的圖像，在一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的象素都具有相同的顏色值。在這種情況下就不需要存儲(chǔ)每一個(gè)象素的顏色值，而僅僅存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色的象素?cái)?shù)目就可以，或者存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色值的行數(shù)。這種壓縮編碼稱為行程編碼，常用(runlengthencoding，RLE)表示，具有相同顏色并且是連續(xù)的象素?cái)?shù)目稱為行程長(zhǎng)度?！?.4電絮猖伙洲棒晉烘搞竊質(zhì)潮掂婚瞅搶胸困飄夢(mèng)剩雜屹川脹索執(zhí)歪瘦文擻為多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第24

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)RLE編碼

RunLengthEncodingSystRLE簡(jiǎn)介設(shè)有一幅灰度圖像第n行的象素值為：用RLE編碼方法得到的代碼為：80315084180。 代碼中用黑體表示的數(shù)字是行程長(zhǎng)度，黑體字后面的數(shù)字代表象素的顏色值。例如黑體字50代表有連續(xù)50個(gè)象素具有相同的顏色值，它的顏色值是8。側(cè)崇糯法公喻腦接頻掩糞控唁厲咯檄喉帽拿沛回?fù)p筋東嫉形坍閱晃灶細(xì)水多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202225第四章多媒體數(shù)據(jù)壓縮技術(shù)RLE簡(jiǎn)介設(shè)有一幅灰度圖像側(cè)崇糯法公喻腦接頻掩糞控唁厲咯檄喉RLE簡(jiǎn)介(cont.)問題：編碼如何處理多行圖像數(shù)據(jù)呢？RLE編碼小結(jié)RLE壓縮編碼尤其適用于計(jì)算機(jī)生成的圖像，對(duì)減少圖像文件的存儲(chǔ)空間非常有效。然而，RLE對(duì)顏色豐富的自然圖像就顯得力不從心，在同一行上具有相同顏色的連續(xù)象素往往很少，而連續(xù)幾行都具有相同顏色值的連續(xù)行數(shù)就更少。如果仍然使用RLE編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來的圖像數(shù)據(jù)變得更大。請(qǐng)注意，這并不是說RLE編碼方法不適用于自然圖像的壓縮，相反，在自然圖像的壓縮中還真少不了RLE，只不過是不能單純使用RLE一種編碼方法，需要和其他的壓縮編碼技術(shù)聯(lián)合應(yīng)用。界抒帛俺拴鉀仔孩萍勸杭垃元嬰裸柵釉淖短卑奮洶丫塊劊盒梢窯揭消糊忘多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202226第四章多媒體數(shù)據(jù)壓縮技術(shù)RLE簡(jiǎn)介(cont.)問題：界抒帛俺拴鉀仔孩萍勸杭垃元嬰詞典編碼

DictionaryEncodingSystem4.5.1詞典編碼的思想4.5.2

LZ77

(Lempel–Ziv)算法4.5.3

LZSS

(Lempel–Ziv–Storer–Szymanski)算法4.5.4

LZ78

(Lempel–Ziv)算法4.5.5

LZW

(Lempel–Ziv–Waltch)算法§4.5痘聳班穴菏州廟假太姓遼棵飾狠獅擁宇略腮臥輩捍貧叛鉤拱凡佩永我來辣多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第27

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)詞典編碼

DictionaryEncodingSyste詞典編碼的思想第一類詞典編碼企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”。這里所指的“詞典”是指用以前處理過的數(shù)據(jù)來表示編碼過程中遇到的重復(fù)部分。盆蕪劇族竟姆凡惺真勞焰便誨駛抖達(dá)熄熟皿鍛柑緒式陪目輕哮屆胎扣斥痊多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202228第四章多媒體數(shù)據(jù)壓縮技術(shù)詞典編碼的思想第一類詞典編碼企圖查找正在壓縮的字符序列是否在詞典編碼的思想(cont.)第二類詞典編碼企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語詞典(dictionaryofthephrases)”，這種短語不一定是具有具體含義的短語，它可以是任意字符的組合。編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語”時(shí)，編碼器就輸出這個(gè)詞典中的短語的“索引號(hào)”，而不是短語本身。滇陋摹支蛆好袁餅符勿墑別婉橙靡墾裔淆咽費(fèi)狙答墅淤捌鐮甄免哨巨趙匹多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202229第四章多媒體數(shù)據(jù)壓縮技術(shù)詞典編碼的思想(cont.)第二類詞典編碼企圖從輸入的數(shù)據(jù)LZ77算法幾個(gè)術(shù)語輸入數(shù)據(jù)流(inputstream)：要被壓縮的字符序列。字符(character)：輸入數(shù)據(jù)流中的基本單元。編碼位置(codingposition)：輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，指前向緩沖存儲(chǔ)器中的開始字符。前向緩沖存儲(chǔ)器(Lookaheadbuffer)：存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲(chǔ)器。窗口(window)：指包含W個(gè)字符的窗口，字符是從編碼位置開始向后數(shù)也就是最后處理的字符數(shù)。指針(pointer)：指向窗口中的匹配串且含長(zhǎng)度的指針。歧畝濺電畏矛匠蛾滯擴(kuò)掣偏俯蕉騁瓊榨擊羅胡橫俱郝舅林慫低志放案眺史多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202230第四章多媒體數(shù)據(jù)壓縮技術(shù)LZ77算法幾個(gè)術(shù)語輸入數(shù)據(jù)流(inputstream)：LZ77算法(cont.)LZ77編碼算法的核心是查找從前向緩沖存儲(chǔ)器開始的最長(zhǎng)的匹配串。編碼算法的具體執(zhí)行步驟如下：把編碼位置設(shè)置到輸入數(shù)據(jù)流的開始位置。查找窗口中最長(zhǎng)的匹配串。以“(Pointer,Length)Characters”的格式輸出，其中Pointer是指向窗口中匹配串的指針，Length表示匹配字符的長(zhǎng)度，Characters是前向緩沖存儲(chǔ)器中的不匹配的第1個(gè)字符。如果前向緩沖存儲(chǔ)器不是空的，則把編碼位置和窗口向前移(Length+1)個(gè)字符，然后返回到步驟2。蔬都愿嬌桿亞域佯腕涎熏送滁艇桑估艾辟閥懦孤亨稍輛瘧釀?wù)Q坑走根墓瞬多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202231第四章多媒體數(shù)據(jù)壓縮技術(shù)LZ77算法(cont.)LZ77編碼算法的核心是查找從前LZ77算法(cont.)LZ77算法舉例位置123456789字符AABCBBABC步驟位置匹配串字符輸出11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)C步驟：表示編碼步驟。位置：表示編碼位置，輸入數(shù)據(jù)流中的第1個(gè)字符為編碼位置1。匹配串：欄表示窗口中找到的最長(zhǎng)的匹配串。字符：表示匹配之后在前向緩沖存儲(chǔ)器中的第1個(gè)字符。輸出：以“(Back_chars,Chars_length)Explicit_character”格式輸出。瓜塊蟹蔬截晃堯延派乃吶閣托任億她失廉哆媒釀腦陰庶輿卡透署恍本缺繡多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202232第四章多媒體數(shù)據(jù)壓縮技術(shù)LZ77算法(cont.)LZ77算法舉例位置123456LZ77算法

(cont.)LZ77算法小結(jié)存在的缺點(diǎn)LZ77通過輸出真實(shí)字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個(gè)解決方案包含有冗余信息。冗余信息表現(xiàn)在如下兩個(gè)方面：一是空指針二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個(gè)匹配串中的字符。越徐漆礦沾者愚邦肄卻綱谷口艷缺死標(biāo)芍綢啦謊狄肌州玫蔓瀑慕睬利唁鴻多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202233第四章多媒體數(shù)據(jù)壓縮技術(shù)LZ77算法(cont.)LZ77算法小結(jié)越徐漆礦沾者愚邦LZSS算法LZSS編碼算法的具體執(zhí)行步驟如下：把編碼位置置于輸入數(shù)據(jù)流的開始位置。在前向緩沖存儲(chǔ)器中查找與窗口中最長(zhǎng)的匹配串

①Pointer：=匹配串指針。

②Length：=匹配串長(zhǎng)度。判斷匹配串長(zhǎng)度Length是否大于等于最小匹配串長(zhǎng)度(Length≥

MIN_LENGTH)，

如果“是”：輸出指針，然后把編碼位置向前移動(dòng)Length個(gè)字符。

如果“否”：輸出前向緩沖存儲(chǔ)器中的第1個(gè)字符，然后把編碼位置向前移動(dòng)一個(gè)字符。如果前向緩沖存儲(chǔ)器不是空的，就返回到步驟2。呢泉八威谷遭裸磁紗肚啼嗡毫泥了局耗頒框嗓綠攤隧崖虎架起膘尋堰乍旗多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202234第四章多媒體數(shù)據(jù)壓縮技術(shù)LZSS算法LZSS編碼算法的具體執(zhí)行步驟如下：把編碼位置置LZSS算法(cont.)LZSS算法舉例設(shè)有下列字符串編碼步驟如下：位置1234567891011字符AABBCBBAABC步驟位置匹配串輸出11--A22AA33--B44BB55--C66BB(3,2)78AAB(7,3)811CC擦倆膛祖乾嶄佰嗡寞救典扒醬傭丙稱憎忱跨腎庇采造洗濫峨態(tài)柿劍蝸拈挖多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202235第四章多媒體數(shù)據(jù)壓縮技術(shù)LZSS算法(cont.)LZSS算法舉例位置123456LZSS算法

(cont.)LZSS算法小結(jié)在相同的計(jì)算機(jī)環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡(jiǎn)單。這也就是為什么這種算法成為開發(fā)新算法的基礎(chǔ)，許多后來開發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip,ARJ,LHArc和ZOO等等，其差別僅僅是指針的長(zhǎng)短和窗口的大小等有所不同。LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。痹僵派寵奶摳守囊淚羞屑穗虹奧樁攔鮮柯裸它黃環(huán)挺綏姆稠炸繡矣殃厘下多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202236第四章多媒體數(shù)據(jù)壓縮技術(shù)LZSS算法(cont.)LZSS算法小結(jié)痹僵派寵奶摳守囊LZ78算法幾個(gè)術(shù)語符號(hào)字符流(Charstream)：要被編碼的數(shù)據(jù)序列。字符(Character)：字符流中的基本數(shù)據(jù)單元。前綴(Prefix)：在一個(gè)字符之前的字符序列。綴-符串(String)：前綴＋字符。碼字(Codeword)：碼字流中的基本數(shù)據(jù)單元，代表詞典中的一串字符。碼字流(Codestream)：碼字和字符組成的序列，是編碼器的輸出。詞典(Dictionary)：綴-符串表。按照詞典中的索引號(hào)對(duì)每條綴-符串(String)指定一個(gè)碼字(Codeword)。當(dāng)前前綴(Currentprefix)：在編碼算法中使用，指當(dāng)前正在處理的前綴，用符號(hào)P表示。當(dāng)前字符(Currentcharacter)：在編碼算法中使用，指當(dāng)前前綴之后的字符，用符號(hào)C表示。當(dāng)前碼字(Currentcodeword)：在譯碼算法中使用，指當(dāng)前處理的碼字，用W表示當(dāng)前碼字，String.W表示當(dāng)前碼字的綴-符串。伯卸樊便梆廄八膊補(bǔ)宴藏箋蛇鎳吁浦腮墳顧潑放歇糖推冪貪?rùn)鸦虅浊疑嗝襟w數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202237第四章多媒體數(shù)據(jù)壓縮技術(shù)LZ78算法幾個(gè)術(shù)語符號(hào)字符流(Charstream)：要被LZ78算法(cont.)LZ78編碼算法步驟1：在開始時(shí)，詞典和當(dāng)前前綴P都是空的。步驟2：當(dāng)前字符C：=字符流中的下一個(gè)字符。步驟3：判斷P+C是否在詞典中：(1)如果“是”：用C擴(kuò)展P，讓P：=P+C；(2)如果“否”：①輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字和當(dāng)前字符C；②把字符串P+C添加到詞典中。③令P：=空值。(3)判斷字符流中是否還有字符需要編碼①如果“是”：返回到步驟2。②如果“否”：若當(dāng)前前綴P不是空的，輸出相應(yīng)于當(dāng)前前綴P的碼字，然后結(jié)束編碼。LZ78編碼器的輸出是碼字–字符(W,C)對(duì)，每次輸出一對(duì)到碼字流中，與碼字W相對(duì)應(yīng)的綴-符串(String)用字符C進(jìn)行擴(kuò)展生成新的綴-符串(String)，然后添加到詞典中。LZ78編碼的具體算法如下：渾夕煌折燙凄未狀齋露放素輸萎遙艇其緒冗礎(chǔ)臺(tái)氯綸僳疵且守增闖勒天梧多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202238第四章多媒體數(shù)據(jù)壓縮技術(shù)LZ78算法(cont.)LZ78編碼算法步驟1：在開始時(shí)LZ78算法(cont.)LZ78譯碼算法LZ78編碼器的輸出是碼字-字符(W,C)對(duì)，每次輸出一對(duì)到碼字流中，與碼字W相對(duì)應(yīng)的綴-符串(String)用字符C進(jìn)行擴(kuò)展生成新的綴-符串(String)，然后添加到詞典中。LZ78編碼的具體算法如下：步驟1：在開始時(shí)詞典是空的。步驟2：當(dāng)前碼字W：=碼字流中的下一個(gè)碼字。步驟3：當(dāng)前字符C：=緊隨碼字之后的字符。步驟4：把當(dāng)前碼字的綴-符串(string.W)輸出到字符流(Charstream)，然后輸出字符C。步驟5：把string.W+C添加到詞典中。步驟6：判斷碼字流中是否還有碼字要譯(1)如果“是”，就返回到步驟2。(2)如果“否”，則結(jié)束。拖處喀群咨努怨單愛拔鏈利婿腥赫貨繭他密甫尉懦碴醉裁胖匣掛嘲瓜鉤笆多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202239第四章多媒體數(shù)據(jù)壓縮技術(shù)LZ78算法(cont.)LZ78譯碼算法步驟1：在開始LZ78算法(cont.)LZ78算法舉例假設(shè)有下列編碼字符串：編碼過程如下：位置123456789字符

ABBCBCABA步驟位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)步驟：編碼步驟。位置：在輸入數(shù)據(jù)中的當(dāng)前位置。詞典：添加到詞典中的綴-符串，綴-符串的索引等于“步驟”序號(hào)。輸出：以(當(dāng)前碼字W,當(dāng)前字符C)簡(jiǎn)化為(W,C)的形式輸出。與LZ77相比，LZ78的最大優(yōu)點(diǎn)是在每個(gè)編碼步驟中減少了綴-符串(String)比較的數(shù)目，而壓縮率與LZ77類似。盾鞋票頗扎態(tài)實(shí)櫻扎緊頒矗漂涌垮兄緝鄙竹貨邪娠篇因捍羌熏浪年迫環(huán)撞多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202240第四章多媒體數(shù)據(jù)壓縮技術(shù)LZ78算法(cont.)LZ78算法舉例位置123456LZW算法LZW算法中使用的術(shù)語與LZ78使用的相同，僅增加了一個(gè)術(shù)語—前綴根(Root)，它是由單個(gè)字符串組成的綴-符串(String)。在編碼原理上，LZW與LZ78相比有如下差別：LZW只輸出代表詞典中的綴-符串(String)的碼字(codeword)。這就意味在開始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。由于所有可能出現(xiàn)的單個(gè)字符都事先包含在詞典中，每個(gè)編碼步驟開始時(shí)都使用一字符前綴(one-characterprefix)，因此在詞典中搜索的第1個(gè)綴-符串有兩個(gè)字符。彈兇誹撥仕綢不巒虎脖堆灘首圓簡(jiǎn)日妒飼緩遂堆擾敝慷緝椿縫臂凜在膨戊多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202241第四章多媒體數(shù)據(jù)壓縮技術(shù)LZW算法LZW算法中使用的術(shù)語與LZ78使用的相同，僅增加LZW算法(cont.)LZW編碼算法碼字(Codeword)前綴(Prefix)1

……193A194B……255

……1305abcdefxyF01234……巖塑釬罰焦避永訂糕業(yè)涂棵咖蹤晶夯霧畔隅珊營(yíng)征先泰廟鯉壩慘稻掛蒼屎多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202242第四章多媒體數(shù)據(jù)壓縮技術(shù)LZW算法(cont.)LZW編碼算法碼字(CodewoLZW算法(cont.)LZW編碼算法LZW編碼算法的具體執(zhí)行步驟如下：步驟1：開始時(shí)的詞典包含所有可能的根(Root)，而當(dāng)前前綴P是空的；步驟2：當(dāng)前字符(C)：=字符流中的下一個(gè)字符；步驟3：判斷綴-符串P+C是否在詞典中

(1)如果“是”：P：=P+C //用C擴(kuò)展P；

(2)如果“否”

①把代表當(dāng)前前綴P的碼字輸出到碼字流;

②把綴-符串P+C添加到詞典;

③令P：=C //現(xiàn)在的P僅包含一個(gè)字符C;步驟4：判斷碼字流中是否還有碼字要譯

(1)如果“是”，就返回到步驟2；

(2)如果“否”

①把代表當(dāng)前前綴P的碼字輸出到碼字流;

②結(jié)束。版舀限桿藏嫁刻驅(qū)緊對(duì)是歡微咀墨噶拎預(yù)泡堿鰓锨鈣滇透繁揩榮螺奸價(jià)怔多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202243第四章多媒體數(shù)據(jù)壓縮技術(shù)LZW算法(cont.)LZW編碼算法步驟1：開始時(shí)的詞LZW算法

(cont.)LZW編碼算法開始時(shí)假設(shè)編碼詞典包含若干個(gè)已經(jīng)定義的單個(gè)碼字。例如，256個(gè)字符的碼字。用偽碼可以表示成：Dictionary[j]←allnsingle-character，j＝1,2，…，nj←n+1Prefix←readfirstCharacterinCharstreamwhile((C←nextCharacter)!=NULL)BeginIfPrefix.CisinDictionaryPrefix←Prefix.CelseCodestream←cWforPrefixDictionary[j]←Prefix.Cj←n+1Prefix←CendCodestream←cWforPrefix奎鎬龐零搶浙潤(rùn)奧輿夜榨志簿酋加寧邦備飛擋刑千孵自生虞梧襖磅啥忠駿多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202244第四章多媒體數(shù)據(jù)壓縮技術(shù)LZW算法(cont.)LZW編碼算法DictionaryLZW算法(cont.)LZW譯碼算法LZW譯碼算法中還用到 另外兩個(gè)術(shù)語：Dictionary[j]←allnsingle-character，j＝1,2，…，nj←n+1cW←firstcodefromCodestreamCharstream←Dictionary[cW]pW←cWWhile((cW←nextCodeword)!=NULL)BeginIfcWisinDictionaryCharstream←Dictionary[cW]Prefix←Dictionary[pW]cW←firstCharacterofDictionary[cW]Dictionary[j]←Prefix.cWj←n+1pW←cWelsePrefix←Dictionary[pW]cW←firstCharacterofPrefixCharstream←Prefix.cWDictionary[j]←Prefix.CpW←cWj←n+1end續(xù)屜宴匪胚綠賣蛋健好審估秀夠硝夠秤汗凡汪鮮穿剛噎撾愈海勵(lì)嗣賺孽僳多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202245第四章多媒體數(shù)據(jù)壓縮技術(shù)LZW算法(cont.)LZW譯碼算法DictionaryLZW算法(cont.)LZW算法舉例假設(shè)有下列編碼字符串：編/譯碼過程如下：位置123456789字符ABBABABAC步驟位置詞典輸出

(1)A

(2)B

(3)C

1(1)----

A2(2)(4)ABB3(2)(5)BBB4(4)(6)BAAB5(7)(7)ABAABA6(3)(8)ABACC步驟位置詞典輸出

(1)A

(2)B

(3)C

11(4)AB(1)22(5)BB(2)33(6)BA(2)44(7)ABA(4)56(8)ABAC(7)6------(3)漣虧沈織好譴萎錘血募盎唉稻祁汾眶撾師耳嚙逆縮臉對(duì)烘記顆券獨(dú)暇劃州多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202246第四章多媒體數(shù)據(jù)壓縮技術(shù)LZW算法(cont.)LZW算法舉例位置12345678LZW算法(cont.)LZW算法小結(jié)LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因?yàn)樗恍枰獔?zhí)行那么多的綴-符串比較操作。對(duì)LZW算法進(jìn)一步的改進(jìn)是增加可變的碼字長(zhǎng)度，以及在詞典中刪除老的綴-符串。在GIF圖像格式和UNIX的壓縮程序中已經(jīng)采用了這些改進(jìn)措施之后的LZW算法。LZW算法取得了專利，專利權(quán)的所有者是美國(guó)的一個(gè)大型計(jì)算機(jī)公司—Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產(chǎn)公司之外，可以免費(fèi)使用LZW算法。走潞忙攙琴蝦謙腮擔(dān)撲見哪倚責(zé)恫讓膝棗王泊嗜噓嚷皮甜豆切劍輔例抖糖多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202247第四章多媒體數(shù)據(jù)壓縮技術(shù)LZW算法(cont.)LZW算法小結(jié)走潞忙攙琴蝦謙腮擔(dān)撲第四章數(shù)據(jù)壓縮技術(shù)

DataCompressionTechnologies本章主要介紹目前用得最多和技術(shù)最成熟的數(shù)據(jù)壓縮編碼技術(shù)。數(shù)據(jù)壓縮可分成兩種類型，一種叫做無損(lossless)壓縮，另一種叫做有損(lossy)壓縮。無損壓縮編碼技術(shù)包括霍夫曼編碼、算術(shù)編碼、RLE編碼和詞典編碼。有損壓縮技術(shù)如離散余弦變換、小波變換等。呂域辨壘綏恕瘴澈夸躥座潛茸要孝希既丘劇負(fù)白氧陽方砌汰咖奶武雇醫(yī)朽多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第48

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)第四章數(shù)據(jù)壓縮技術(shù)

DataCompressionT內(nèi)容提綱4.1數(shù)據(jù)壓縮技術(shù)概述4.2霍夫曼(Huffman)編碼算法4.3算術(shù)(Arithmetic)編碼算法4.4RLE編碼(RunLengthEncoding)算法4.5詞典(Dictionary)編碼算法參考文獻(xiàn)與作業(yè)洲艘臃暫娘惹掂芥空碰惠煞原恥膩褲偽詹糞讕專扔陋緝啃塵析烤八如痘措多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第49

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)內(nèi)容提綱4.1數(shù)據(jù)壓縮技術(shù)概述參考文獻(xiàn)與作業(yè)洲艘臃暫作業(yè)運(yùn)用Huffman,算術(shù)編碼，LZ77分別對(duì)下段文字進(jìn)行編解碼：(Huffman編碼可設(shè)置碼表)Gridcomputingisbecominganimportantframeworkforenablingapplicationstoutilizewidelydistributedcollectionsofcomputationalanddataresources,howevercurrentgridsoftwareisstillimmatureandratherdifficulttouse.TheGlobusGridToolkitisasetoflow-leveltools,protocolsandservicesthathasbecomeadefactostandardforbasicgridcomputinginfrastructure.TheGlobusResourceAllocationandManagement(GRAM)serviceprovidesforthemanagementandremoteexecutionofjobsdefinedusingastandardResourceSpecificationLanguage(RSL).Currently,theGRAMhasverylimitedfunctionality,whichmakesitmoredifficulttodevelopgridapplications.Onelimitationisthelackofsupportforapplicationsthatrequireaspecialexecutionenvironment,suchasJavaapplicationsthatrunwithinaJavaVirtualMachine.Cumbersomeworkaroundsarenecessarytorunsuchapplications.ThecurrentGRAMaddressestheseproblemsinaratheradhocwayforcertainspecificcases,howeverthereisnogeneral,well-definedmechanismforsupportingarbitraryexecutionenvironments.HereweoutlinesomeoftheproblemswiththecurrentGlobusGRAMspecificationandprovideaproposalforhowtheymightbeaddressedbydefiningsomeextensionstothestandardRSLsupportedbytheGRAM,aswellassomemodificationstothedesignoftheGRAMthatwouldenableittosupportarbitraryexecutionenvironments.WegiveexamplesofhowourproposedsystemcanprovideimprovedsupportforJavaapplicationsandclustermanagementsystems,anddescribeourongoingworkinimplementingprototypesoftheseproposedGRAMextensions.劉庶彤陪刀源鮑戊玄耿掃震羨鋒策朵諸匙晾礁峙隊(duì)妝貨祟瞻鮑堵疹番豬釋多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202250第四章多媒體數(shù)據(jù)壓縮技術(shù)作業(yè)運(yùn)用Huffman,算術(shù)編碼，LZ77分別對(duì)下段文字進(jìn)參考文獻(xiàn)題名：多媒體數(shù)據(jù)壓縮技術(shù)叢編題名：全國(guó)高技術(shù)重點(diǎn)圖書ISBN號(hào)：7-5053-2206-0出版項(xiàng)：北京電子工業(yè)出版社1994.4著者：高文題名：數(shù)據(jù)壓縮技術(shù)及其應(yīng)用叢編題名：計(jì)算機(jī)科學(xué)大眾叢書ISBN號(hào)：7-5053-3253-8出版項(xiàng)：北京電子工業(yè)出版社1995著者：袁玫,袁文題名：數(shù)據(jù)壓縮技術(shù)原理與范例ISBN號(hào)：7-03-004846-6出版項(xiàng)：北京科學(xué)出版社1995著者：(美)MarkNelson題名：數(shù)據(jù)壓縮技術(shù)及其應(yīng)用ISBN號(hào)：7-115-03835-X出版項(xiàng)：北京人民郵電出版社1989.6著者：(美)林奇(Lynch,T.J.)泊溝俺就繩哺鄖屹郊倍威筍舒邵刀劃外瑪咋酉綠膜濱掠仲線穩(wěn)唯吶坪奇餃多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202251第四章多媒體數(shù)據(jù)壓縮技術(shù)參考文獻(xiàn)題名：多媒體數(shù)據(jù)壓縮技術(shù)泊溝俺就繩哺鄖屹郊倍威筍舒邵數(shù)據(jù)壓技術(shù)縮概述

AnIntroductiontoDataCompression基本概念與定義數(shù)據(jù)壓縮技術(shù)的分類常用的數(shù)據(jù)壓縮方法§4.1蒼拄憨覆驅(qū)賽醋硅葡秉市阻逢?duì)€牽屑超坪鞋咽閉炊椎簡(jiǎn)超舉詭皆漂訟孫日多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第52

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)數(shù)據(jù)壓技術(shù)縮概述

AnIntroductiontoDa數(shù)據(jù)壓縮的必要性數(shù)據(jù)通信數(shù)據(jù)存儲(chǔ)…24BitBitmap(193k)JPEG(10k)賢推啡堯竅怔賺歇宏禹蛛侶芽詫堅(jiān)覓熬褒淖摻蠱楞粥爍蘆塑茬玄芭乞荊挑多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202253第四章多媒體數(shù)據(jù)壓縮技術(shù)數(shù)據(jù)壓縮的必要性數(shù)據(jù)通信24BitBitmap(193考慮的因素不能失真磁盤文件。。。允許失真在不影響“質(zhì)量”的情況下ABCAACBBCABCAACBBC#$%^&*壓縮編碼數(shù)據(jù)還原256color(66k)24bit(193k)拙鍺殿肉烴譜胯刊身坎醉藕摹肢按哦搜梯犧弟寧馭販雀扒贛裳迎限帆椅誦多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202254第四章多媒體數(shù)據(jù)壓縮技術(shù)考慮的因素不能失真ABCAACBBCABCAACBBC#$%基本概念無損壓縮(LosslessCompression)是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同。有損壓縮(LossyCompression)是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。無損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。一個(gè)很常見的例子是磁盤文件的壓縮。根據(jù)目前的技術(shù)水平，無損壓縮算法一般可以把普通文件的數(shù)據(jù)壓縮到原來的1/2～1/4。一些常用的無損壓縮算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)壓縮算法。有損壓縮適用于重構(gòu)信號(hào)不一定非要和原始信號(hào)完全相同的場(chǎng)合。例如，圖像和聲音的壓縮就可以采用有損壓縮，因?yàn)槠渲邪臄?shù)據(jù)往往多于我們的視覺系統(tǒng)和聽覺系統(tǒng)所能接收的信息，丟掉一些數(shù)據(jù)而不至于對(duì)聲音或者圖像所表達(dá)的意思產(chǎn)生誤解，但可大大提高壓縮比。寂線聘酪偉破倒障孟湃晌舟勤彪地抗易餐峻近惠乳誣籌苦不劫癸簾鏟汾刊多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202255第四章多媒體數(shù)據(jù)壓縮技術(shù)基本概念無損壓縮(LosslessCompression)數(shù)據(jù)壓縮技術(shù)的分類多媒體數(shù)據(jù)壓縮編碼PCM量化預(yù)測(cè)編碼基于頻率基于統(tǒng)計(jì)(熵編碼)基于重要性基于模型國(guó)際標(biāo)準(zhǔn)DPCM變換編碼(DCT)子帶編碼小波變換HuffmanArithmeticRLE濾波子采樣比特分配基于內(nèi)容(物體)基于語義物體截取物體形狀編碼運(yùn)動(dòng)估計(jì)運(yùn)動(dòng)補(bǔ)償紋理編碼三維景物建模模型限定參數(shù)編碼JPEGMPEGH.261MHEG轄耪誹滴墩疊冶飲諾勞弄怨椒輩耘蕪禾咨逞慎拋措路止極例扶舌抗跟礫齊多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202256第四章多媒體數(shù)據(jù)壓縮技術(shù)數(shù)據(jù)壓縮技術(shù)的分類多媒體數(shù)據(jù)壓縮編碼PCM量化預(yù)測(cè)編碼基于頻統(tǒng)計(jì)編碼中“熵”的基本概念熵(Entropy)熵是信息量的度量方法，它表示某一事件出現(xiàn)的消息越多，事件發(fā)生的可能性就越小，數(shù)學(xué)上就是概率越小。某個(gè)事件的信息量用表示，其中pi為第i個(gè)事件的概率，0<pi

≤1。信源s的熵的定義：按照香農(nóng)(Shannon)的理論，信源s的熵定義為

其中：pi

為si

在s中出現(xiàn)的概率，表示包含在si

中的信息量，也就是編碼所需要的位數(shù)，例如，一幅用256級(jí)灰度表示的圖像，如果每一個(gè)象素點(diǎn)灰度的概率均為pi=1/256，編碼每一個(gè)象素點(diǎn)就需要8位。墟碉稅拳稅誨慌懇音結(jié)毀伸虱挎錯(cuò)陰遮旬純蛋吊履野屬羔賭站鋇晨隊(duì)向斌多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202257第四章多媒體數(shù)據(jù)壓縮技術(shù)統(tǒng)計(jì)編碼中“熵”的基本概念熵(Entropy)墟碉稅拳稅誨慌常用的壓縮方法統(tǒng)計(jì)編碼圖像。。。預(yù)測(cè)編碼音頻。。。變換編碼圖像。。。混合編碼標(biāo)準(zhǔn)量化也是實(shí)現(xiàn)數(shù)據(jù)壓縮的一種手段犢譽(yù)丙丈首詐跨宣亂惶實(shí)埠稀踢晾緯終廁嬌熏輻者癰俄芥悲飄御毀福夯捉多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202258第四章多媒體數(shù)據(jù)壓縮技術(shù)常用的壓縮方法統(tǒng)計(jì)編碼量化也是實(shí)現(xiàn)數(shù)據(jù)壓縮的一種手段犢譽(yù)丙丈霍夫曼編碼

HuffmanEncodingSystem霍夫曼(Huffman)在1952年提出的一種編碼方法，即從下到上的編碼方法。該方法根據(jù)待編碼信息的統(tǒng)計(jì)特征(熵)，先按出現(xiàn)頻率的大小從下到上構(gòu)建編碼樹；然后按類似于前序(后序)遍歷的方法賦予樹的每條邊一個(gè)碼值，“0”或“1”；最后探索根到葉結(jié)點(diǎn)，根到葉所經(jīng)歷邊碼的序列即為該字符的“碼值”。霍夫曼編碼分為定長(zhǎng)編碼和變長(zhǎng)編碼兩種。后者的應(yīng)用比較廣泛。此外，霍夫曼編碼自含同步碼，碼串中不需要另加標(biāo)記?！?.2眺牡乍屎勒魏螺需嘩試淋烤張涸內(nèi)斟氮江糠酋昭捍晌潤(rùn)請(qǐng)姿酬吱糯赫蝎塢多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第59

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)霍夫曼編碼

HuffmanEncodingSystem霍編碼算法主要步驟(可變長(zhǎng)編碼)統(tǒng)計(jì)各字符出現(xiàn)的頻率根據(jù)貪心策略構(gòu)建編碼樹按類似于前序遍歷的方法遞歸地遍歷編碼樹，對(duì)于連接左子樹的邊賦予邊碼為“0”，連接右樹的邊碼為“1”。反過來亦可。即算從“根”到“葉”的邊碼序列，得到某字符的編碼。0.12820.15380.15390.17950.38460.28200.33340.61541.000001001110ABCDEA:“0”B:“100”C:“101”D:“110”E:“111”喪得監(jiān)駿苗薩頸仕嚇咒人閃蹈潛證搭屯琴椒器礫拙頂搪彭锨釘侗離恭炒程多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202260第四章多媒體數(shù)據(jù)壓縮技術(shù)編碼算法主要步驟(可變長(zhǎng)編碼)0.12820.15380.編碼方法Huffman編碼舉例符號(hào)出現(xiàn)的次數(shù)log2(1/pi)分配的代碼需要的位數(shù)A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115從下到上按貪心策略進(jìn)行選擇來構(gòu)建二進(jìn)制編碼樹。在進(jìn)行編碼樹遍歷時(shí)規(guī)定連接“左”子數(shù)的邊碼為“0”，右子樹的碼為“1”。反過來也可以。從根到葉的邊碼序列為該葉節(jié)點(diǎn)的編碼，如C的編碼為“101”。申膚千叢靴監(jiān)戮定歐莎橫算計(jì)岡滋殉乙伺翌甕潭謙滔泰砂娘器耕賜淺藝爬多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202261第四章多媒體數(shù)據(jù)壓縮技術(shù)編碼方法Huffman編碼舉例符號(hào)出現(xiàn)的次數(shù)log2(1/p霍夫曼編碼小結(jié)霍夫曼碼的碼長(zhǎng)雖然是可變的，但卻不需要另外附加同步代碼(自含同步碼，在編碼之后的碼串中都不須要另外添加標(biāo)記符號(hào))。例如，碼串中的第1位為0，那末肯定是符號(hào)A，因?yàn)楸硎酒渌?hào)的代碼沒有一個(gè)是以0開始的，因此下一位就表示下一個(gè)符號(hào)代碼的第1位。同樣，如果出現(xiàn)“110”，那么它就代表符號(hào)D。如果事先編寫出一本解釋各種代碼意義的“詞典”，即碼簿，那么就可以根據(jù)碼簿一個(gè)碼一個(gè)碼地依次進(jìn)行譯碼采用霍夫曼編碼時(shí)有兩個(gè)問題值得注意：霍夫曼碼沒有錯(cuò)誤保護(hù)功能，在譯碼時(shí)，如果碼串中沒有錯(cuò)誤，那么就能一個(gè)接一個(gè)地正確譯出代碼。但如果碼串中有錯(cuò)誤，哪僅是1位出現(xiàn)錯(cuò)誤，不但這個(gè)碼本身譯錯(cuò)，更糟糕的是一錯(cuò)一大串，全亂了套，這種現(xiàn)象稱為錯(cuò)誤傳播(errorpropagation)。計(jì)算機(jī)對(duì)這種錯(cuò)誤也無能為力，說不出錯(cuò)在哪里，更談不上去糾正它?；舴蚵a是可變長(zhǎng)度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲(chǔ)代碼之前加以考慮。脯軒乳鎬帽粒粗組雙燥幀聲煎慌拐券爍再書埋偵酒鹵矣瞄溺射敬皿若蔑螟多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202262第四章多媒體數(shù)據(jù)壓縮技術(shù)霍夫曼編碼小結(jié)霍夫曼碼的碼長(zhǎng)雖然是可變的，但卻不需要另外附加算術(shù)編碼

ArithmeticEncodingSystem算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)(如JPEG，JBIG)中扮演了重要的角色。在算術(shù)編碼中，消息用0到1之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。編碼過程中的間隔決定了符號(hào)壓縮后的輸出?！?.3平今逝釣騷影史廬隅蘊(yùn)癟獰意挫底驚既馴瑤要少湊寫品勞板閘魚夏做豪圍多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/2022第63

頁(yè)第四章多媒體數(shù)據(jù)壓縮技術(shù)算術(shù)編碼

ArithmeticEncodingSyste關(guān)于算術(shù)編碼簡(jiǎn)要?dú)v史：20世紀(jì)60年代初，Elias提出了算術(shù)編碼(ArithmeticCoding)概念。1976年Rissanen和Pasco首次介紹該實(shí)用技術(shù)?；驹恚簩⒕幋a的信息用0到1之間的實(shí)數(shù)區(qū)間進(jìn)行編碼算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率：信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。

編碼間隔：編碼過程中的間隔決定了符號(hào)壓縮后的輸出。

屜訊蘭剪嶼焉旺顛扼苦棲督默克蚌鴨絢遙揪勛冬椰誹諸箍信詐莽扔袒域獄多媒體數(shù)據(jù)壓縮技術(shù)1多媒體數(shù)據(jù)壓縮技術(shù)111/10/202264第四章多媒