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

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

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

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

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

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

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

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

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

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

其中：pi

為si

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

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

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

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

HuffmanEncodingSystem霍編碼算法主要步驟(可變長編碼)統(tǒng)計各字符出現(xiàn)的頻率根據(jù)貪心策略構建編碼樹按類似于前序遍歷的方法遞歸地遍歷編碼樹，對于連接左子樹的邊賦予邊碼為“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ù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202213第四章多媒體數(shù)據(jù)壓縮技術編碼算法主要步驟(可變長編碼)0.12820.15380.編碼方法Huffman編碼舉例符號出現(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從下到上按貪心策略進行選擇來構建二進制編碼樹。在進行編碼樹遍歷時規(guī)定連接“左”子數(shù)的邊碼為“0”，右子樹的碼為“1”。反過來也可以。從根到葉的邊碼序列為該葉節(jié)點的編碼，如C的編碼為“101”。申膚千叢靴監(jiān)戮定歐莎橫算計岡滋殉乙伺翌甕潭謙滔泰砂娘器耕賜淺藝爬多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202214第四章多媒體數(shù)據(jù)壓縮技術編碼方法Huffman編碼舉例符號出現(xiàn)的次數(shù)log2(1/p霍夫曼編碼小結霍夫曼碼的碼長雖然是可變的，但卻不需要另外附加同步代碼(自含同步碼，在編碼之后的碼串中都不須要另外添加標記符號)。例如，碼串中的第1位為0，那末肯定是符號A，因為表示其他符號的代碼沒有一個是以0開始的，因此下一位就表示下一個符號代碼的第1位。同樣，如果出現(xiàn)“110”，那么它就代表符號D。如果事先編寫出一本解釋各種代碼意義的“詞典”，即碼簿，那么就可以根據(jù)碼簿一個碼一個碼地依次進行譯碼采用霍夫曼編碼時有兩個問題值得注意：霍夫曼碼沒有錯誤保護功能，在譯碼時，如果碼串中沒有錯誤，那么就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，哪僅是1位出現(xiàn)錯誤，不但這個碼本身譯錯，更糟糕的是一錯一大串，全亂了套，這種現(xiàn)象稱為錯誤傳播(errorpropagation)。計算機對這種錯誤也無能為力，說不出錯在哪里，更談不上去糾正它?；舴蚵a是可變長度碼，因此很難隨意查找或調用壓縮文件中間的內容，然后再譯碼，這就需要在存儲代碼之前加以考慮。脯軒乳鎬帽粒粗組雙燥幀聲煎慌拐券爍再書埋偵酒鹵矣瞄溺射敬皿若蔑螟多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202215第四章多媒體數(shù)據(jù)壓縮技術霍夫曼編碼小結霍夫曼碼的碼長雖然是可變的，但卻不需要另外附加算術編碼

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

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

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

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

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

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

和

其中uk

和vk

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

和v1

：①如果

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

比較u2

和v2

：①如果

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

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

轉步驟2。通徑錯拳妒姆垃姆貳計晌盼猩五縷骯鯨翁看礦策拓霧翁冗鋤疑瞎朋類攙疏多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202220第四章多媒體數(shù)據(jù)壓縮技術算法描述編碼步驟如下：步驟1：首先在1和0之間給每個符號分配算法描述編碼過程：步驟輸入符號編碼間隔編碼判決110[0.5,0.7)符號的間隔范圍[0.5,0.7)200[0.5,0.52)[0.5,0.7)間隔的第一個1/10311[0.514,0.52)[0.5,0.52)間隔的最后一個1/10400[0.514,0.5146)[0.514,0.52)間隔的第一個1/10510[0.5143,0.51442)[0.514,0.5146)間隔的第五個1/10開始，二個1/10611[0.514384,0.51442)[0.5143,0.51442)間隔的最后3個1/10701[0.5143836,0.514402)[0.514384,0.51442)間隔的4個1/10，從第1個1/10開始8從[0.5143876,0.514402中選擇一個數(shù)作為輸出：0.5143876糧銥莖引墑禁往汀式錯雞盔佳孕鑲脅褒斷賬粗蝎忌稠呢等扮勿履淫幫盜輻多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202221第四章多媒體數(shù)據(jù)壓縮技術算法描述編碼過程：步輸入編碼間隔編碼判決110[0.5,算法描述譯碼過程步驟間隔譯碼符號譯碼判決1[0.5,0.7)100.51439在間隔[0.5,0.7)2[0.5,0.52)000.51439在間隔[0.5,0.7)的第1個1/103[0.514,0.52)110.51439在間隔[0.5,0.52)的第7個1/104[0.514,0.5146)000.51439在間隔[0.514,0.52)的第1個1/105[0.5143,0.51442)100.51439在間隔[0.514,0.5146)的第5個1/106[0.514384,0.51442)110.51439在間隔[0.5143,0.51442)的第7個1/107[0.51439,0.5143948)010.51439在間隔[0.51439,0.5143948)的第1個1/107譯碼的消息：10001100101101犬驟隙泊酚撞旺嚴翱久帥臘抨繩梁鐐耘宣益緒巾貧壓腎匆鴦鉆涸屜哈顴硒多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202222第四章多媒體數(shù)據(jù)壓縮技術算法描述譯碼過程步間隔譯碼譯碼判決1[0.5,0.7)1算術編碼小結在算術編碼中需要注意的幾個問題：由于實際的計算機的精度不可能無限長，運算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機器都有16位、32位或者64位的精度，因此這個問題可使用比例縮放方法解決。算術編碼器對整個消息只產生一個碼字，這個碼字是在間隔[0,1)中的一個實數(shù)，因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。算術編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導致整個消息譯錯。算術編碼可以是靜態(tài)的或者自適應的。在靜態(tài)算術編碼中，信源符號的概率是固定的。在自適應算術編碼中，信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進行修改。騁渙扼曬氖膀牟己典遇淋貓蹈恭捻己臂悼紙味誘揮信幣蔓殷夫錳貝鉻燒吳多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202223第四章多媒體數(shù)據(jù)壓縮技術算術編碼小結在算術編碼中需要注意的幾個問題：騁渙扼曬氖膀牟己RLE編碼

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

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

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

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

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

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

①Pointer：=匹配串指針。

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

MIN_LENGTH)，

如果“是”：輸出指針，然后把編碼位置向前移動Length個字符。

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

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

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

……193A194B……255

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

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

(2)如果“否”

①把代表當前前綴P的碼字輸出到碼字流;

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

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

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

(2)如果“否”

①把代表當前前綴P的碼字輸出到碼字流;

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

(cont.)LZW編碼算法開始時假設編碼詞典包含若干個已經定義的單個碼字。例如，256個字符的碼字。用偽碼可以表示成：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奎鎬龐零搶浙潤奧輿夜榨志簿酋加寧邦備飛擋刑千孵自生虞梧襖磅啥忠駿多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202244第四章多媒體數(shù)據(jù)壓縮技術LZW算法(cont.)LZW編碼算法DictionaryLZW算法(cont.)LZW譯碼算法LZW譯碼算法中還用到 另外兩個術語：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ù)屜宴匪胚綠賣蛋健好審估秀夠硝夠秤汗凡汪鮮穿剛噎撾愈海勵嗣賺孽僳多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202245第四章多媒體數(shù)據(jù)壓縮技術LZW算法(cont.)LZW譯碼算法DictionaryLZW算法(cont.)LZW算法舉例假設有下列編碼字符串：編/譯碼過程如下：位置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)漣虧沈織好譴萎錘血募盎唉稻祁汾眶撾師耳嚙逆縮臉對烘記顆券獨暇劃州多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202246第四章多媒體數(shù)據(jù)壓縮技術LZW算法(cont.)LZW算法舉例位置12345678LZW算法(cont.)LZW算法小結LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因為它不需要執(zhí)行那么多的綴-符串比較操作。對LZW算法進一步的改進是增加可變的碼字長度，以及在詞典中刪除老的綴-符串。在GIF圖像格式和UNIX的壓縮程序中已經采用了這些改進措施之后的LZW算法。LZW算法取得了專利，專利權的所有者是美國的一個大型計算機公司—Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產公司之外，可以免費使用LZW算法。走潞忙攙琴蝦謙腮擔撲見哪倚責恫讓膝棗王泊嗜噓嚷皮甜豆切劍輔例抖糖多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202247第四章多媒體數(shù)據(jù)壓縮技術LZW算法(cont.)LZW算法小結走潞忙攙琴蝦謙腮擔撲第四章數(shù)據(jù)壓縮技術

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

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

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

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

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

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

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

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

其中：pi

為si

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

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

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

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

HuffmanEncodingSystem霍編碼算法主要步驟(可變長編碼)統(tǒng)計各字符出現(xiàn)的頻率根據(jù)貪心策略構建編碼樹按類似于前序遍歷的方法遞歸地遍歷編碼樹，對于連接左子樹的邊賦予邊碼為“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ù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202260第四章多媒體數(shù)據(jù)壓縮技術編碼算法主要步驟(可變長編碼)0.12820.15380.編碼方法Huffman編碼舉例符號出現(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從下到上按貪心策略進行選擇來構建二進制編碼樹。在進行編碼樹遍歷時規(guī)定連接“左”子數(shù)的邊碼為“0”，右子樹的碼為“1”。反過來也可以。從根到葉的邊碼序列為該葉節(jié)點的編碼，如C的編碼為“101”。申膚千叢靴監(jiān)戮定歐莎橫算計岡滋殉乙伺翌甕潭謙滔泰砂娘器耕賜淺藝爬多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202261第四章多媒體數(shù)據(jù)壓縮技術編碼方法Huffman編碼舉例符號出現(xiàn)的次數(shù)log2(1/p霍夫曼編碼小結霍夫曼碼的碼長雖然是可變的，但卻不需要另外附加同步代碼(自含同步碼，在編碼之后的碼串中都不須要另外添加標記符號)。例如，碼串中的第1位為0，那末肯定是符號A，因為表示其他符號的代碼沒有一個是以0開始的，因此下一位就表示下一個符號代碼的第1位。同樣，如果出現(xiàn)“110”，那么它就代表符號D。如果事先編寫出一本解釋各種代碼意義的“詞典”，即碼簿，那么就可以根據(jù)碼簿一個碼一個碼地依次進行譯碼采用霍夫曼編碼時有兩個問題值得注意：霍夫曼碼沒有錯誤保護功能，在譯碼時，如果碼串中沒有錯誤，那么就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，哪僅是1位出現(xiàn)錯誤，不但這個碼本身譯錯，更糟糕的是一錯一大串，全亂了套，這種現(xiàn)象稱為錯誤傳播(errorpropagation)。計算機對這種錯誤也無能為力，說不出錯在哪里，更談不上去糾正它。霍夫曼碼是可變長度碼，因此很難隨意查找或調用壓縮文件中間的內容，然后再譯碼，這就需要在存儲代碼之前加以考慮。脯軒乳鎬帽粒粗組雙燥幀聲煎慌拐券爍再書埋偵酒鹵矣瞄溺射敬皿若蔑螟多媒體數(shù)據(jù)壓縮技術1多媒體數(shù)據(jù)壓縮技術111/10/202262第四章多媒體數(shù)據(jù)壓縮技術霍夫曼編碼小結霍夫曼碼的碼長雖然是可變的，但卻不需要另外附加算術編碼

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

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

ArithmeticEncodingSyste關于算術編碼簡要歷史：20世紀60年代初，Elias提出了算術編碼(ArithmeticCoding)概念。1976年Rissanen和Pasco首次介紹該實用技術。基本原理：將編碼的信息用0到1之間的實數(shù)區(qū)間進行編碼算術編碼用到兩個基本的參數(shù)：符號的概率：信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在0到1之間。

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

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