多媒體數(shù)據(jù)壓縮與編碼技術(shù)

第4章多媒體數(shù)據(jù)壓縮與編碼技術(shù)本章重點(diǎn)：編碼模型編碼壓縮方法分類統(tǒng)計(jì)編碼的基本原理預(yù)測編碼的基本原理變換編碼的基本原理視頻編碼的基本原理?第4章多媒體數(shù)據(jù)壓縮與編碼技術(shù)4.1編碼壓縮的必要性與可能性4.2編碼模型4.3編碼壓縮方法分類4.4統(tǒng)計(jì)編碼4.5預(yù)測編碼4.6變換編碼4.7其他編碼4.8視頻編碼4.9本章小結(jié)?4.1編碼壓縮的必要性與可能性4.1.1編碼壓縮的必要性4.1.2編碼壓縮的可能性

?4.1.1編碼壓縮的必要性眾所周知，圖像量化所需數(shù)據(jù)量大。圖像和視頻的龐大數(shù)據(jù)對(duì)計(jì)算機(jī)的處理速度、存儲(chǔ)容量都提出過高的要求。因此必須進(jìn)行數(shù)據(jù)量壓縮。從傳送的角度來看，在信道帶寬、通信鏈路容量一定的前提下，采用編碼壓縮技術(shù)，減少傳輸數(shù)據(jù)量，是提高通信速度的重要手段。因此，更要求數(shù)據(jù)量壓縮。?4.1.2編碼壓縮的可能性

眾所周知，視頻由一幀一幀的圖像組成，而圖像的各像素之間，無論是在行方向還是在列方向，都存在著一定的相關(guān)性，即冗余度。應(yīng)用某種編碼方法提取或減少這些冗余度，便可以達(dá)到壓縮數(shù)據(jù)的目的。常見的靜態(tài)圖像數(shù)據(jù)冗余包括：1.空間冗余這是靜態(tài)圖像存在的最主要的一種數(shù)據(jù)冗余。一幅圖像記錄了畫面上可見景物的顏色。同一景物表面上各采樣點(diǎn)的顏色之間往往存在著空間連貫性，從而產(chǎn)生了空間冗余。

?4.1.2編碼壓縮的可能性2.時(shí)間冗余在視頻的相鄰幀間，往往包含相同的背景和移動(dòng)物體，因此，后一幀數(shù)據(jù)與前一幀數(shù)據(jù)有許多共同的地方，即在時(shí)間上存在大量的冗余。3.結(jié)構(gòu)冗余在有些圖像的紋理區(qū)，圖像的像素值存在著明顯的分布模式。例如，方格狀的地板圖案等。我們稱這種冗余為結(jié)構(gòu)冗余。4.知識(shí)冗余有些圖像的理解與某些知識(shí)有相當(dāng)大的相關(guān)性。例如，人臉的圖像有固定的結(jié)構(gòu)。這類?4.1.2編碼壓縮的可能性

規(guī)律性的結(jié)構(gòu)可由先驗(yàn)知識(shí)和背景知識(shí)得到，我們稱此類冗余為知識(shí)冗余。5.視覺冗余事實(shí)表明，人類的視覺系統(tǒng)對(duì)圖像場的敏感性是非均勻的和非線性的。然而，在記錄原始圖像數(shù)據(jù)時(shí)，通常假定視覺系統(tǒng)是線性的和均勻的，對(duì)視覺敏感和不敏感的部分同等對(duì)待，從而產(chǎn)生了比理想編碼更多的數(shù)據(jù)，這就是視覺冗余。6.圖像區(qū)域的相同性冗余

是指在圖像中的兩個(gè)或多個(gè)區(qū)域所對(duì)應(yīng)的所有?4.1.2編碼壓縮的可能性像素值相同或相近，從而產(chǎn)生的數(shù)據(jù)重復(fù)性存儲(chǔ)，這就是圖像區(qū)域的相似性冗余。

7.紋理的統(tǒng)計(jì)冗余有些圖像紋理盡管不嚴(yán)格服從某—分布規(guī)律，但是它在統(tǒng)計(jì)的意義上服從該規(guī)律。利用這種性質(zhì)也可以減少表示圖像的數(shù)據(jù)量，所以我們稱之為紋理的統(tǒng)計(jì)冗余。

?4.2編碼模型

4.2.1信源編碼器和信源解碼器4.2.2信道編碼器和解碼器?4.2編碼碼模型如圖4.1所所示，一個(gè)壓壓縮系統(tǒng)包括括兩個(gè)不同的的結(jié)構(gòu)塊：一一個(gè)編碼器和和一個(gè)解碼器器。圖像f（x，y）輸入到編碼碼器中，這個(gè)個(gè)編碼器可以以根據(jù)輸入數(shù)數(shù)據(jù)生成一組組符號(hào)。在通通過信道進(jìn)行行傳輸之后，，將經(jīng)過編碼碼的表達(dá)符號(hào)號(hào)送入解碼器器，經(jīng)過重構(gòu)構(gòu)后，就生成成了輸出圖像像。?信信源編碼器器和信源解碼碼器信源編碼器的的任務(wù)是減少少或消除輸入入圖像中的冗冗余。編碼的的框圖如圖下下圖(a)所所示。從原理來看主主要分為三個(gè)個(gè)階段，第一一階段將輸入入數(shù)據(jù)轉(zhuǎn)換為為可以減少輸輸入圖像中像像素間冗余的的數(shù)據(jù)的集合合。第二階段段設(shè)法去除原原圖象信號(hào)的的相關(guān)性，例例如對(duì)電視信信號(hào)就可以去去掉幀內(nèi)各種種相關(guān)，還可可以去除幀間間相關(guān)。這樣樣有利?信信源編碼器器和信源解碼碼器于編碼壓縮。。第三階段就就是找一種更更近于熵，又又利于計(jì)算機(jī)機(jī)處理的編碼碼方式。下圖(b)中中顯示的信源源解碼器僅包包含兩部分：：一個(gè)符號(hào)解解碼器和一個(gè)個(gè)反向轉(zhuǎn)換器器。這些模塊塊的運(yùn)行次序序與編碼器的的符號(hào)編碼器器和轉(zhuǎn)換模塊塊的操作次序序相反。?信信道編碼器器和解碼器當(dāng)信道帶有噪噪聲或易于出出現(xiàn)錯(cuò)誤時(shí)，，信道編碼器器和解碼器就就在整個(gè)譯碼碼解碼處理中中扮演了重要要的角色。最有用的—種種信道編碼技技術(shù)是由R．．w．Hamming提提出的。該技技術(shù)基于這樣樣的思想，即即向被編碼數(shù)數(shù)據(jù)中加入足足夠的位數(shù)以以確?？捎玫牡拇a字間變化化的位數(shù)最小小。例如，利利用Hamming碼將將3位冗余碼碼加到4位字字上，使得任任意兩個(gè)有效效碼字間的距距離為3，則則所有的一位位錯(cuò)誤都可以以檢測出來并并得到糾止。。與4位二進(jìn)進(jìn)制數(shù)b3b2b1b0相聯(lián)系的7位Hamming(7，4)碼字字?4.2.2信道編編碼器和解解碼器h1h2……h(huán)5h6h7是：：這里表示異異或運(yùn)算。。h1，h2和h4位分別是是位字段b3b2b0，b3b1b0和b2b1b0的的偶校驗(yàn)位位。?4.2.2信道編編碼器和解解碼器為了將漢明明（Hamming）編碼結(jié)結(jié)果進(jìn)行解解碼，信道道解碼器必必須為先前前設(shè)立的偶偶校驗(yàn)的各各個(gè)位字段段進(jìn)行奇校校驗(yàn)并檢查查譯碼值。。一位錯(cuò)誤誤由一個(gè)非非零奇偶校校驗(yàn)字c4c2c1給出，這這里，?4.3編編碼壓縮方方法分類數(shù)據(jù)壓縮的的目標(biāo)是去去除各種冗冗余。根據(jù)據(jù)壓縮后是是否有信息息丟失，多多媒體數(shù)據(jù)據(jù)壓縮技術(shù)術(shù)可分為無無損壓縮技技術(shù)和有損損壓縮技術(shù)術(shù)兩類。數(shù)數(shù)據(jù)壓縮編編碼分類如如圖4.3所示。常見的無損損壓縮技術(shù)術(shù)有：霍夫曼編碼碼算術(shù)編碼行程編碼詞典編碼?4.3編編碼壓縮方方法分類常用的一些些有損壓縮縮技術(shù)包括括：預(yù)測編碼變換編碼基于模型編編碼分形編碼其他編碼?4.3編編碼壓縮方方法分類?4.4統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼屬屬無損編碼碼，它是根根據(jù)消息出出現(xiàn)概率的的分布特性性而進(jìn)行的的壓縮編碼碼。統(tǒng)計(jì)編編碼又可分分為定長碼碼和變長碼碼。常用的統(tǒng)計(jì)計(jì)編碼有Huffman編碼碼、行程編編碼和算術(shù)術(shù)編碼三種種。4.4.1哈夫曼曼（Huffman）編碼4.4.2香農(nóng)-費(fèi)諾編碼碼4.4.3算術(shù)編編碼4.4.4游程編編碼（RLC）4.4.5LZW編碼?4.4.1哈夫曼曼（Huffman）編碼在一幅圖像像中，有些些圖像數(shù)據(jù)據(jù)出現(xiàn)的頻頻率高，有有些圖像數(shù)數(shù)據(jù)出現(xiàn)的的頻率低。。如果對(duì)那那些出現(xiàn)頻頻率高的數(shù)數(shù)據(jù)用較少少的位數(shù)來來表示，而而出現(xiàn)頻率率低的數(shù)據(jù)據(jù)用較多的的位數(shù)來表表示，這樣樣從總的效效果來看還還是節(jié)省了了存儲(chǔ)空間間。這種編編碼思想首首先由香農(nóng)農(nóng)（Shannon）提出，，哈夫曼后后來對(duì)它提提出了一種種改進(jìn)的編編碼方法，，用這種方方法得到的的編碼稱為為Huffman編編碼，Huffman編碼是是一種變長長編碼。?哈哈夫夫曼曼（（Huffman））編編碼碼1.理理論論基基礎(chǔ)礎(chǔ)一個(gè)個(gè)事事件件集集合合x1,x2,……，，xn處處于于一一個(gè)個(gè)基基本本概概率率空空間間，，其其相相應(yīng)應(yīng)概概率率為為p1,p2,……，，pn，，且且p1+p2+……pn=1。。每每一一個(gè)個(gè)信信息息的的信信息息量量為為（4-3））定義義在在概概率率空空間間中中每每——事事件件的的概概率率不不相相等等時(shí)時(shí)的的平平均均信信息息量量為為信信息息熵熵，，則則信信息息熵熵H可可采采用用如如下下公公式式計(jì)計(jì)算算：：（4-4））?哈哈夫夫曼曼（（Huffman））編編碼碼【例例4.1】】信信息息熵熵的的計(jì)計(jì)算算。。設(shè)8個(gè)個(gè)隨隨機(jī)機(jī)變變量量具具有有同同等等概概率率為為1/8，，則則熵熵即計(jì)算出H=3比特。2.Huffman編碼Huffman編碼是1952年由Huffman提出的一種編碼方法。它在變長編碼方法中是最佳的。?哈哈夫夫曼曼（（Huffman））編編碼碼設(shè)信信源源A的的信信源源空空間間為為：：其中中，現(xiàn)用用r個(gè)個(gè)碼碼符符號(hào)號(hào)的的碼碼符符號(hào)號(hào)集集對(duì)信信源源A中中的的每每個(gè)個(gè)符符號(hào)號(hào)（（i＝＝1，，2，，……，，N））進(jìn)進(jìn)行行編編碼碼。。具具體體編編碼碼的的方方法法是是：：(1)把把信信源源符符號(hào)號(hào)按按其其出出現(xiàn)現(xiàn)概概率率的的大大小小順順序序排排列列起起來來；；(2)把把最最末末兩兩個(gè)個(gè)具具有有最最小小概概率率的的元元素素之之概概率率加加起起來來；；?哈哈夫夫曼曼（（Huffman））編編碼碼(3)把把該該概概率率之之和和同同其其余余概概率率由由大大到到小小排排隊(duì)隊(duì)，，然然后后再再把把兩兩個(gè)個(gè)最最小小概概率率加加起起來來，，再再重重新新排排隊(duì)隊(duì)；；重復(fù)復(fù)步步驟驟,直直到到最最后后只只剩剩下下兩兩個(gè)個(gè)概概率率為為止止。。在上上述述工工作作完完畢畢之之后后，，從從最最后后兩兩個(gè)個(gè)概概率率開開始始逐逐步步向向前前進(jìn)進(jìn)行行編編碼碼。。對(duì)對(duì)于于概概率率大大的的賦賦予予0，，小小的的賦賦予予1。。?哈哈夫夫曼曼（（Huffman））編編碼碼?哈哈夫夫曼曼（（Huffman））編編碼碼經(jīng)霍霍夫夫曼曼編編碼碼后后，，平平均均碼碼長長為為：：=0.4××1＋＋0.30××2＋＋0.1××4+0.06××5+0.04××5=2.20（（bit））?哈哈夫夫曼曼（（Huffman））編編碼碼3.Huffman編編碼碼的的幾幾點(diǎn)點(diǎn)說說明明（1））Huffman編編碼碼是是最最佳佳的的，，雖雖然然構(gòu)構(gòu)造造出出來來的的碼碼不不唯唯一一，，但但其其平平均均碼碼長長卻卻相相同同，，所所以以不不影影響響編編碼碼效效率率和和數(shù)數(shù)據(jù)據(jù)壓壓縮縮性性能能。。（2）由由于Huffman碼碼的碼長長參差不不齊，因因此，存存在一個(gè)個(gè)輸入、、輸出速速率匹配配問題。。解決的的辦法是是設(shè)置一一定容量量的緩沖沖存儲(chǔ)器器。（3）Huffman碼在存存儲(chǔ)或傳傳輸過程程中，如如果出現(xiàn)現(xiàn)誤碼，，可能會(huì)會(huì)引起誤誤碼的連連續(xù)傳播播，1bit的的誤碼可可能把一一大串碼碼字全部部破壞，，因此，，限制了了Huffman碼的的使用。。?哈哈夫曼（（Huffman）編編碼（4）Huffman編碼對(duì)對(duì)不同信信源其編編碼效率率也不盡盡相同。。當(dāng)信源源概率是是2的負(fù)負(fù)次冪時(shí)時(shí)，Huffman碼碼的編碼碼效率達(dá)達(dá)到100％；；當(dāng)信源源概率相相等時(shí)，，其編碼碼效率最最低。這這表明在在使用Huffman方法編編碼時(shí)，，只有當(dāng)當(dāng)信源概概率分布布很不均均勻時(shí)，，Huffman碼才才會(huì)收到到顯著的的效果。。（5）Huffman編碼應(yīng)應(yīng)用時(shí)，，均需要要與其他他編碼結(jié)結(jié)合起來來使用，，才能進(jìn)進(jìn)一步提提高數(shù)據(jù)據(jù)壓縮比比。例如如，在靜靜態(tài)圖像像處理標(biāo)標(biāo)準(zhǔn)JPEG中中，先對(duì)對(duì)圖像像像素進(jìn)行行DCT變換、、量化、、Z形掃掃描、游游程編碼碼后，再再進(jìn)行霍霍夫曼編編碼。?4.4.2香農(nóng)農(nóng)-費(fèi)諾諾編碼具體編碼碼方法如如下：（1）把把按按概概率由大大到小、、從上到到下排成成一列，，然后把把分成兩組組，，，，并使這這兩組符符號(hào)概率率和相等等或幾乎乎相等，，即：（2）把把兩組分分別按0，1賦賦值,例例如將第第一組賦賦值為0，則第第二組賦賦值為1。然后后分組、、賦值，，不斷反反復(fù)，直直到每組組只有一一種輸入入為止。。將每個(gè)個(gè)所賦的的值依次次排列起起來就是是香農(nóng)-費(fèi)費(fèi)諾編碼碼。?4.4.2香農(nóng)農(nóng)-費(fèi)諾諾編碼以前面的的數(shù)據(jù)為為例，香香農(nóng)-編編碼費(fèi)諾諾如圖4.5所所示。?算算術(shù)編碼碼理論上，，用Huffman方方法對(duì)源源數(shù)據(jù)流流進(jìn)行編編碼可達(dá)達(dá)到最佳佳編碼效效果。但但由于計(jì)計(jì)算機(jī)中中存儲(chǔ)、、處理的的最小單單位是““位”，，因此，，在一些些情況下下，實(shí)際際壓縮比比與理論論壓縮比比的極限限相去甚甚遠(yuǎn)。算術(shù)編碼碼把要壓壓縮處理理的整段段數(shù)據(jù)映映射到——段實(shí)數(shù)數(shù)半開區(qū)區(qū)間[0，1]內(nèi)的某某一區(qū)段段，構(gòu)造造出小于于1且大大于或等等于0的的數(shù)值。。這個(gè)數(shù)數(shù)值是輸輸入數(shù)據(jù)據(jù)流的唯唯—可譯譯代碼。。?算算術(shù)編碼碼下面通過過一個(gè)例例子來說說明算術(shù)術(shù)編碼的的方法。。對(duì)一個(gè)5符號(hào)信信源A＝＝{a1，a2，a3，a2，a4}，各各字符出出現(xiàn)的概概率和設(shè)設(shè)定的取取值范圍圍如下表表4.2：?算算術(shù)編碼碼為討論方方便起見見，假定定有式中Ns為新子子區(qū)間的的起始位位置；Fs為前前子區(qū)間間的起始始位置，，Cl當(dāng)當(dāng)前符號(hào)號(hào)的區(qū)間間左端；；Ne為新子子區(qū)間的的結(jié)束位位置；Fe為前前子區(qū)間間的結(jié)束束位置；；Cr當(dāng)當(dāng)前符號(hào)號(hào)的區(qū)間間右端；；L為前前子區(qū)間間的長度度。按上述區(qū)區(qū)間的定定義，最最終結(jié)果果如表4.3：：?算算術(shù)編碼碼給定事件件序列的的算術(shù)編編碼步驟驟如下：：（1）編編碼器在在開始時(shí)時(shí)將“當(dāng)當(dāng)前間隔隔”[L，H]設(shè)設(shè)置為[0，1）。（2）對(duì)對(duì)每一事事件，編編碼器按按步驟（（a）和和（b））進(jìn)行處處理?算算術(shù)編碼碼（a）編編碼器將將“當(dāng)前前間隔””分為子子間隔，，每一個(gè)個(gè)事件一一個(gè)。（b）一一個(gè)子間間隔的大大小與下下一個(gè)將將出現(xiàn)的的事件的的概率成成比例，，編碼器器選擇子子間隔對(duì)對(duì)應(yīng)于下下一個(gè)確確切發(fā)生生的事件件相對(duì)應(yīng)應(yīng)，并使使它成為為新的““當(dāng)前間間隔”。。最后輸出出的“當(dāng)當(dāng)前間隔隔”的下下邊界就就是該給給定事件件序列的的算術(shù)編編碼。?算算術(shù)編碼碼在算術(shù)編編碼中有有幾個(gè)問問題需要要注意：：由于實(shí)際際的計(jì)算算機(jī)的精精度不可可能無限限長，一一個(gè)明顯顯的問題題是運(yùn)算算中出現(xiàn)現(xiàn)溢出，，但多數(shù)數(shù)機(jī)器都都有16、32或者64位的的精度，，因此這這個(gè)問題題可使用用比例縮縮放方法法解決。。算術(shù)編碼碼器對(duì)整整個(gè)消息息只產(chǎn)生生一個(gè)碼碼字，這這個(gè)碼字字是在間間隔[0，1]中的一一個(gè)實(shí)數(shù)數(shù)，因此此譯碼器器在接收收到表示示這個(gè)實(shí)實(shí)數(shù)的所所有位之之前不能能進(jìn)行譯譯碼。算術(shù)編碼碼也是一一種對(duì)錯(cuò)錯(cuò)誤很敏敏感的編編碼方法法，如果果有一位位發(fā)生錯(cuò)錯(cuò)誤就會(huì)會(huì)導(dǎo)致整整個(gè)消息息譯錯(cuò)。。?游游程編碼碼（RLC）游程編碼碼是一種種利用空空間冗余余度壓縮縮圖像的的方法，，相對(duì)比比較簡單單，也屬屬于統(tǒng)計(jì)計(jì)編碼類類。設(shè)圖像中中的某一一行或某某一塊像像素經(jīng)采采樣或經(jīng)經(jīng)某種方方法變換換后的系系數(shù)為，，如如圖4.7所示示。某一一行或某某一塊內(nèi)內(nèi)像素值值可可分為k段，長長度為為的連續(xù)續(xù)串，每每個(gè)串具具有相同同的值，，那么，，該圖像像的某一一行或某某一塊可可由下面面偶對(duì)來來表示：：，，其中為為每個(gè)個(gè)串內(nèi)的的代表值值，為為串的長長度。?游游程編碼碼（RLC）?游游程編碼碼（RLC）串長li就是游程程長度（（Run-length），，簡寫為為RL，，即由字字符或采采樣值或或灰度值值構(gòu)成的的數(shù)據(jù)流流中各個(gè)個(gè)字符等等重復(fù)出出現(xiàn)而形形成的字字符串的的長度。?；窘Y(jié)結(jié)構(gòu)如圖圖4.8所示。。?游游程編編碼（（RLC））游程編編碼分分為定定長游游程編編碼和和變長長游程程編碼碼兩類類。定定長游游程編編碼是是指RL位數(shù)數(shù)是固固定的的。變變長游游程編編碼是是指RL位數(shù)數(shù)是不不固定定的。。游程編編碼一一般不不直接接應(yīng)用用于多多灰度度圖像像，但但比較較適合合于二二值圖圖像的的編碼碼。例例如黑黑白傳傳真圖圖像的的編碼碼等。。為了了達(dá)到到較好好的壓壓縮效效果，，有時(shí)時(shí)游程程編碼碼和其其他一一些編編碼方方法混混合使使用。。定義游游程和和游程程長度度后，，就可可以把把任何何二元元序列列變換換成游游程長長度的的序列列，簡簡稱游游程序序列。。這一一變換換是可可逆的的，一一一對(duì)對(duì)應(yīng)的的。?編編碼LZW壓縮縮編碼碼是一一種無無損壓壓縮編編碼。。LZW的的基本本思想想是用用符號(hào)號(hào)代替替一串串字符符，這這一串串字符符可以以是有有意義義的，，也可可以是是無意意義的的。在在編碼碼中僅僅僅把把字符符串看看成是是一個(gè)個(gè)號(hào)碼碼，而而不去去管它它代表表什么么意思思。1.編編碼碼算法法LZW編碼碼是圍圍繞稱稱為詞詞典的的轉(zhuǎn)換換表來來完成成的。。這張張轉(zhuǎn)換換表用用來存存放稱稱為前前綴（（Prefix）的的字符符序列列，并并且為為每個(gè)個(gè)表項(xiàng)項(xiàng)分配配一個(gè)個(gè)碼字字（Codeword），，或者者叫做做序號(hào)號(hào)。?編編碼LZW編碼碼算法法的具具體執(zhí)執(zhí)行步步驟如如下：：步驟1：開開始時(shí)時(shí)的詞詞典包包含所所有可可能的的根（（Root），，而當(dāng)當(dāng)前前前綴P是空空的；；步驟2：當(dāng)當(dāng)前字字符（（C））：=字符符流中中的下下一個(gè)個(gè)字符符；步驟3：判判斷綴綴-符符串P+C是否否在詞詞典中中如果““是””：P：=P+C，，即用用C擴(kuò)擴(kuò)展P）；；如果““否””把代表表當(dāng)前前前綴綴P的的碼字字輸出出到碼碼字流流；把綴-符串串P+C添添加到到詞典典；令P：：=C，，即即現(xiàn)在在的P僅包包含一一個(gè)字字符C；步驟4：判判斷碼碼字流流中是是否還還有碼碼字要要譯如果““是””，就就返回回到步步驟2；如果““否””把代表表當(dāng)前前前綴綴P的的碼字字輸出出到碼碼字流流；結(jié)束。。LZW編碼碼算法法可用用偽碼碼表示示。開開始時(shí)時(shí)假設(shè)設(shè)編碼碼詞典典包含含若干干個(gè)已已經(jīng)定定義的的單個(gè)個(gè)碼字字。?編編碼【例4.4】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?編編碼2.譯譯碼碼算法法LZW譯碼碼算法法中還還用到到另外外兩個(gè)個(gè)術(shù)語語：①①當(dāng)前前碼字字（Currentcodeword）：：指當(dāng)當(dāng)前正正在處處理的的碼字字，用用cW表示示，用用string.cW表表示當(dāng)當(dāng)前綴綴-符符串；；②先先前碼碼字（（Previouscodeword）：：指先先于當(dāng)當(dāng)前碼碼字的的碼字字，用用pW表示示，用用string.pW表表示先先前綴綴-符符串。。LZW譯碼碼算法法開始始時(shí)，，譯碼碼詞典典與編編碼詞詞典相相同，，它包包含所所有可可能的的前綴綴根（roots））。?編編碼LZW譯碼碼算法法的具具體執(zhí)執(zhí)行步步驟如如下：：步驟1：在在開始始譯碼碼時(shí)詞詞典包包含所所有可可能的的前綴綴根（（Root）；；步驟2：cW：：=碼碼字流流中的的第一一個(gè)碼碼字；；步驟3：輸輸出當(dāng)當(dāng)前綴綴-符符串string.cW到碼碼字流流；步驟4：先先前碼碼字pW：：=當(dāng)當(dāng)前前碼字字cW；步驟5：當(dāng)當(dāng)前碼碼字cW：：=碼碼字字流中中的下下一個(gè)個(gè)碼字字；步驟6：判判斷先先前綴綴-符符串string.pW是否否在詞詞典中中如果“是””：把先前綴-符串string.pW輸輸出到字符符流；當(dāng)前前綴P：=先前前綴-符串串string.pW；當(dāng)前字符C：=當(dāng)前前前綴-符符串string.cW的第第一個(gè)字符符；把綴-符串串P+C添添加到詞典典；如果“否””：當(dāng)前前綴P：=先前前綴-符串串string.pW；當(dāng)前字符C：=當(dāng)前前綴-符串串string.cW的第一一個(gè)字符；；輸出綴-符符串P+C到字符流流，然后把把它添加到到詞典中。。步驟7：判判斷碼字流流中是否還還有碼字要要譯如果“是””，就返回回到步驟4；如果“否””，結(jié)束。。?4.4.5LZW編碼【例4.6】編碼字字符串如表表4.6所所示，編碼碼過程如表表4.7所所示?，F(xiàn)說說明如下：：“步驟””欄表示編編碼步驟；；“位置””欄表示在在輸入數(shù)據(jù)據(jù)中的當(dāng)前前位置；““詞典”欄欄表示添加加到詞典中中的綴-符符串，它的的索引在括括號(hào)中；““輸出”欄欄表示碼字字輸出。?4.4.5LZW編碼表4.8解解釋了譯碼碼過程。每每個(gè)譯碼步步驟譯碼器器讀一個(gè)碼碼字，輸出出相應(yīng)的綴綴-符串，，并把它添添加到詞典典中。例如如，在步驟驟4中，先先前碼字（（2）存儲(chǔ)儲(chǔ)在先前碼碼字（pW）中，當(dāng)當(dāng)前碼字（cW））是（4）），當(dāng)前綴-符符串?4.4.5LZW編碼string.cW是輸出（（“AB”），先先前綴-符符串string.pW（（"B"））是用當(dāng)前前綴-符串串string.cW（"A"）的的第一個(gè)字字符，其結(jié)結(jié)果（"BA"））添加到到詞典中，，它的索引引號(hào)是（6）。?4.5預(yù)預(yù)測編碼4.5.1概述4.5.2無損預(yù)預(yù)測編碼4.5.3有損預(yù)預(yù)測編碼?4.5.1概述預(yù)測編碼是是根據(jù)離散散信號(hào)之間間存在著一一定的相關(guān)關(guān)性，利用用前面的一一個(gè)或多個(gè)個(gè)信號(hào)對(duì)下下一信號(hào)進(jìn)進(jìn)行預(yù)測，，然后對(duì)實(shí)實(shí)際值和預(yù)預(yù)測值的差差（預(yù)測誤誤差）進(jìn)行行編碼。預(yù)測編碼中中典型的壓壓縮方法有有脈沖編碼碼調(diào)制（PCM，PulseCodeModulation）、差分分脈沖編碼碼調(diào)制（DPCM，，DifferentialPulseCodeModulation）、、自適應(yīng)差差分脈沖編編碼調(diào)制（（ADPCM，AdaptiveDifferentialPulseCodeModulation）等。。預(yù)測編碼可可分為無損損預(yù)測編碼碼和有損預(yù)預(yù)測編碼。。?4.5.2無損預(yù)預(yù)測編碼無損預(yù)測編編碼器的工工作原理圖圖和預(yù)測原原理如圖4.9和圖圖4.10所示。其其中f（i,j）的預(yù)測值為為，將的的差值進(jìn)進(jìn)行無損熵熵編碼，熵熵編碼器可可采用霍夫夫曼編碼或或算術(shù)編碼碼。圖4.10給出出了像素（（i，j））的預(yù)測圖圖，圖中給給出了（i，j）的的三個(gè)相鄰鄰像素，由由先前三三點(diǎn)預(yù)測，，定義為：：其中a1,a2,a3稱預(yù)測系系數(shù)，都是是待定參數(shù)數(shù)。如果預(yù)預(yù)測器中預(yù)預(yù)測系數(shù)是是固定不變變的常數(shù)，，稱之為線線性預(yù)測。。?4.5.2無損預(yù)預(yù)測編碼圖4.9

無損預(yù)測編碼器工作原理壓縮源圖像預(yù)測器熵編碼器編碼表?4.5.2無損預(yù)預(yù)測編碼預(yù)測誤差計(jì)計(jì)算公式如如下：設(shè)a=f（（i,j-1），b=f（i-1,j）,c=f（i-1,j-1），，的的預(yù)測方法法如圖4.11所示示，可有8種選擇方方法。?4.5.2無損預(yù)預(yù)測編碼?4.5.2無損預(yù)預(yù)測編碼【例4.7】設(shè)有一一幅圖像，，f（i-1,j-1），f（i-1,j），，f（i,j-1）），f（i,j）的的灰度值分分別為253,252,253,255，用圖圖4.11第四種選選擇方法預(yù)預(yù)測f（i,j）的灰度值，，并計(jì)算預(yù)預(yù)測誤差。。解：=a+b-c=f（i,j-1）+f（i-1,j）-f（i-1,j-1）=253+252-252=253預(yù)測誤差=255-253=2?4.5.3有損預(yù)預(yù)測編碼如果不是直直接對(duì)差值值信號(hào)進(jìn)行行編碼，而而是對(duì)差值值信號(hào)進(jìn)行行量化后再再進(jìn)行編碼碼就稱之為為有損預(yù)測測編碼。有有損預(yù)測方方法有多種種，其中差差分脈沖編編碼調(diào)制（（DifferentialPulseCodeModulation，簡簡稱DPCM），是是一種具有有代表性的的編碼方法法。DPCM系系統(tǒng)由編碼碼器和解碼碼器組成，，它們各有有一個(gè)相同同的預(yù)測器器。圖像DPCM系系統(tǒng)的工作作原理如圖圖4.12所示。系系統(tǒng)包括發(fā)發(fā)送、接收收和信道傳傳輸三個(gè)部部分。?4.5.3有損預(yù)預(yù)測編碼?4.6變變換編碼4.6.1變換編編碼的基本本原理4.6.2離散余余弦變換編編碼4.6.3小波變變換?4.6.1變換編編碼的基本本原理變換編碼的的原理如圖圖4.13所示。從從圖中看出出，存儲(chǔ)或或傳輸都是是在變換域域中進(jìn)行的的，即傳輸輸或存儲(chǔ)都都不是空域域圖像而是是變換域系系數(shù)。圖4.13變換編編碼、解碼碼原理框圖圖?4.6.2離散余余弦變換編編碼DCT計(jì)算復(fù)復(fù)雜度適中，，又具有可分分離特性，還還有快速算法法等特點(diǎn)，所所以近年來在在圖像數(shù)據(jù)壓壓縮中，采用用離散余弦變變換編碼的方方案很多，特特別是20世世紀(jì)80年代代迅速崛起的的多媒體技術(shù)術(shù)中，JPEG、MPEG、H.261等壓縮縮標(biāo)準(zhǔn)，都用用到離散余弦弦變換編碼進(jìn)進(jìn)行數(shù)據(jù)壓縮縮。二維離散偶余余弦正變換公公式為：式中，x,y,u,v＝＝0，1………，N-1。。，當(dāng)u=v=0時(shí)。，當(dāng)u=1，2……，N-1；；v=1，2…，N-1時(shí).?離離散余弦變變換編碼二維離散偶余余弦逆變換公公式為：式中，x,y,u,v＝＝0，1………，N-1。。，當(dāng)u=v=0時(shí)。，當(dāng)u=1，，2…，N-1；v=1，2…，N-1時(shí)。?離離散余弦變變換編碼從圖4-14可以看出，，采用DCT進(jìn)行變換編編碼時(shí)，通常常首先將原始始圖像分成子子塊，對(duì)每一一子塊經(jīng)正交交變換得到變變換系數(shù)，并并對(duì)變換系數(shù)數(shù)經(jīng)過量化和和取舍，然后后采用熵編碼碼等方式進(jìn)行行編碼后，再再由信道傳輸輸?shù)浇邮斩?。。在接收端，，?jīng)過解碼、、反量化、逆逆變換后，得得到重建圖像像。?小小波變換小波變換對(duì)圖圖像的壓縮類類似于離散余余弦變換，即即都是對(duì)圖像像進(jìn)行變換。。由時(shí)域變換換到頻域，然然后再量化、、編碼、輸出出。不同之處處在于小波變變換是對(duì)整幅幅圖像進(jìn)行變變換；小波變變換沒有量化化表，它主要要依據(jù)變換后后各級(jí)分辨率率之間的自相相似的特點(diǎn)，，采用逐級(jí)逼逼近技術(shù)實(shí)現(xiàn)現(xiàn)減少數(shù)據(jù)存存儲(chǔ)的目的。。小波變換繼承承了Fourier分析析的優(yōu)點(diǎn)，同同時(shí)又克服它它的許多缺點(diǎn)點(diǎn)，所以它在在靜態(tài)和動(dòng)態(tài)態(tài)圖像壓縮領(lǐng)領(lǐng)域得到廣泛泛的應(yīng)用，并并且已經(jīng)成為為某些圖像壓壓縮國際標(biāo)準(zhǔn)準(zhǔn)（如MPEG-4）的的重要環(huán)節(jié)。。?4.7其他編編碼分分形編碼矢矢量量化編編碼子子帶編碼?分分形編碼分形編碼與分分形幾何相關(guān)關(guān)。所謂分形形幾何就是研研究無限復(fù)雜雜但具有一定定意義下的自自相似圖形和和結(jié)構(gòu)的幾何何學(xué)。分形編編碼正是利用用分形幾何中中自相似的原原理來實(shí)現(xiàn)數(shù)數(shù)據(jù)壓縮的。。首先對(duì)圖像像進(jìn)行分塊，，然后再去尋尋找各塊之間間的相似性，，這里相似性性的描述主要要是依靠仿射射變換來確定定的，一旦找找到了每塊的的仿射變換，，就保存下這這個(gè)仿射變換換的系數(shù)，由由于每塊的數(shù)數(shù)據(jù)量遠(yuǎn)大于于仿射變換的的系數(shù)，因而而圖像得以大大幅度地壓縮縮。分形圖像編碼碼和解碼不夠夠成熟，產(chǎn)生生的壓縮比不不夠高。壓縮縮效果還不十十分理想，在在當(dāng)前圖像壓壓縮編碼中還還不能占據(jù)主主導(dǎo)地位。?矢矢量量化編編碼矢量量化編碼碼利用相鄰圖圖像數(shù)據(jù)間的的高度相關(guān)性性，將輸入圖圖像數(shù)據(jù)序列列分組，每一一組由m個(gè)數(shù)數(shù)據(jù)構(gòu)成一個(gè)個(gè)M維矢量，，一起進(jìn)行編編碼，即一次次量化多個(gè)點(diǎn)點(diǎn)。根據(jù)香農(nóng)農(nóng)失真率理論論，對(duì)于無記記憶信源，矢矢量量化編碼碼總是優(yōu)于標(biāo)標(biāo)量量化編碼碼。矢量量化編碼碼是有損編碼碼。?子子帶編碼由于人眼對(duì)不不同頻域段的的敏感程度不不同，圖像信信號(hào)可以劃分分為不同的頻頻域段。子帶編碼的基基本思想是利利用一濾波器器組，將采樣樣將輸入信號(hào)號(hào)分解為高頻頻分量和低頻頻分量，然后后分別對(duì)高頻頻和低頻分量量進(jìn)行量化和和編碼。解碼碼時(shí)，高頻分分量和低頻分分量經(jīng)過插值值和共軛濾波波器而合成原原信號(hào)。?4.8視頻頻編碼幀幀內(nèi)預(yù)測編碼碼幀幀間預(yù)測編編碼活活動(dòng)圖像幀幀間內(nèi)插?4.8視頻頻編碼視頻編碼系統(tǒng)統(tǒng)的基本結(jié)構(gòu)構(gòu)如圖4.15所示。信源模型量化參數(shù)參數(shù)統(tǒng)計(jì)特性重建視頻噪聲輸入視頻分析量化二進(jìn)制編碼編碼器有損過程無損過程信道綜合反量化二進(jìn)制解碼解碼器圖4.15視頻編碼系統(tǒng)的一般組成?幀幀內(nèi)預(yù)測編碼碼在視頻預(yù)測編編碼中，主要要分為幀內(nèi)預(yù)預(yù)測編碼和幀幀間預(yù)測編碼碼。所謂幀內(nèi)預(yù)測測，就是在一一個(gè)視頻幀，，即一幅圖像像內(nèi)進(jìn)行的預(yù)預(yù)測。幀內(nèi)預(yù)測編碼碼的優(yōu)點(diǎn)是算算法簡單，易易于實(shí)現(xiàn)，但但壓縮比比較較低，因此在在視頻圖像壓壓縮中幾乎不不單獨(dú)使用。。?幀幀間預(yù)測編編碼幀間預(yù)測編碼碼就是利用視視頻圖像幀間間的相關(guān)性，，即時(shí)間相關(guān)關(guān)性，來獲得得比幀內(nèi)編碼碼高得多的壓壓縮比。具有運(yùn)動(dòng)補(bǔ)償償?shù)膸g預(yù)測測編碼是視頻頻壓縮的關(guān)鍵鍵技術(shù)之一，，它包括以下下幾個(gè)步驟：：首先，將圖像像分解成相對(duì)對(duì)靜止的背景景和若干運(yùn)動(dòng)動(dòng)的物體，通通過運(yùn)動(dòng)估值值得到每個(gè)物物體的位移矢矢量；然后，利用位位移矢量計(jì)算算經(jīng)運(yùn)動(dòng)補(bǔ)償償后的預(yù)測值值最后對(duì)預(yù)測誤誤差進(jìn)行量化化、編碼、傳傳輸，同時(shí)將將位移矢量和和圖像分解方方式等信息送送到接收端。。?幀幀間預(yù)測編編碼在具有運(yùn)動(dòng)補(bǔ)補(bǔ)償?shù)膸g預(yù)預(yù)測編碼系統(tǒng)統(tǒng)中，對(duì)圖像像靜止區(qū)和不不同運(yùn)動(dòng)區(qū)的的實(shí)時(shí)完善分分解和運(yùn)動(dòng)矢矢量計(jì)算是較較為復(fù)雜和困困難的。在實(shí)實(shí)際實(shí)現(xiàn)時(shí)經(jīng)經(jīng)常采用的是是像素遞歸法法和塊匹配法法兩種簡化的的辦法。像素遞歸法的的具體作法是是，通過某種種較為簡單的的方法首先將將圖像分割成成運(yùn)動(dòng)區(qū)和靜靜止區(qū)，在靜靜止區(qū)內(nèi)像素素的位移為零零，不進(jìn)行遞遞歸運(yùn)算；對(duì)對(duì)運(yùn)動(dòng)區(qū)內(nèi)的的像素，利用用該像素左邊邊或正上方像像素的位移矢矢量D作為本本像素的位移移矢量，然后后用前一幀對(duì)對(duì)應(yīng)位置上經(jīng)經(jīng)位移D后的的像素值作為為當(dāng)前幀中該該像素的預(yù)測測值。如果預(yù)預(yù)測誤差小于于某一閾值，，則認(rèn)為該像像素可預(yù)測，，無需傳送信信息；如果預(yù)預(yù)測誤差大于于該閾值，編編碼器則需傳傳送量化后的的預(yù)測誤差、、以及該像素素的地址，收收、發(fā)雙方各各自根據(jù)量化化后的預(yù)測誤誤差更新位移移矢量。?幀幀間預(yù)測編編碼塊匹配法將圖圖像劃分為許許多子塊，并并認(rèn)為將每個(gè)個(gè)子塊視為一一個(gè)“運(yùn)動(dòng)物物體”。對(duì)于于某一時(shí)間t，圖像幀中中的某一子塊塊如果在另一一時(shí)間t-t1的幀中可可以找到若干干與其十分相相似的子塊，，則稱其中最最為相似的子子塊為匹配塊塊，并認(rèn)為該該匹配塊是時(shí)時(shí)間t-t1的幀中相應(yīng)應(yīng)子塊位移的的結(jié)果。位移移矢量由兩幀幀中相應(yīng)子塊塊的坐標(biāo)決定定。在塊匹配方法法中需要解決決兩個(gè)問題：：一是確定判判別兩個(gè)子塊塊匹配的準(zhǔn)則則；二是尋找找計(jì)算量最少少的匹配搜索索算法。?活活動(dòng)圖像幀幀間內(nèi)插活動(dòng)圖像的幀幀間內(nèi)插編碼碼是在系統(tǒng)發(fā)發(fā)送端每隔一一段時(shí)間丟棄棄一幀或幾幀幀圖像，而在在接收端再利利用圖像的幀幀間相關(guān)性將將丟棄的幀通通過內(nèi)插恢復(fù)復(fù)出來，以防防止幀率下降降引起閃爍和和動(dòng)作不連續(xù)續(xù)?；謴?fù)丟棄幀的的一個(gè)簡單辦辦法是利用線線性內(nèi)插，缺缺點(diǎn)在于當(dāng)圖圖像中有運(yùn)動(dòng)動(dòng)物體時(shí)，引引起圖像模糊糊，為解決這這一問題可采采用帶有運(yùn)動(dòng)動(dòng)補(bǔ)償?shù)膸g間內(nèi)插。?4.9本章小小結(jié)在多媒體應(yīng)用用系統(tǒng)中，必必須解決視頻頻、圖像、音音頻等大容量量數(shù)據(jù)的存儲(chǔ)儲(chǔ)和實(shí)時(shí)展示示等問題。多多媒體數(shù)據(jù)壓壓縮的目的，，就是為了最最有效地利用用有限資源。。我們希望用盡盡可能少的比比特?cái)?shù)來表示示源信號(hào)并能能將其還原。。因此，壓縮縮的任務(wù)就是是保持信源信信號(hào)在一個(gè)可可以接受的狀狀況的前提下下把需要的比比特?cái)?shù)減到最最少程度，這這樣來減少存存儲(chǔ)、處理和和傳輸?shù)某杀颈尽?謝謝1月-2320:39:1220:3920:391月-231月-2320:3920:3920:39:121月-231月-2320:39:122023/1/520:39:129、靜夜四四無鄰，，荒居舊舊業(yè)貧。。。1月-231月-23Thursday,January5,202310、雨中黃葉樹樹，燈下白頭頭人。。20:39:1320:39:1320:391/5/20238:39:13PM11、以我獨(dú)獨(dú)沈久，，愧君相相見頻。。。1月-2320:39:1320:39Jan-2305-Jan-2312、故人江海別別，幾度隔山山川。。20:39:1320:39:1320:39Thursday,January5,202313、乍見翻疑疑夢，相悲悲各問年。。。1月-231月-2320:39:1320:39:13January5,202314、他鄉(xiāng)生白發(fā)發(fā)，舊國見青青山。。05一月20238:39:13下午20:39:131月-2315、比比不不了了得得就就不不比比，，得得不不到到的的就就不不要