7 圖像壓縮, 為什么要壓縮？ 為什么能壓縮？ 常用的壓縮方法 JPEG/MPEG格式,數(shù)據(jù)編碼,信源編碼 提高數(shù)據(jù)表達(dá)效率（壓縮） 信道編碼 提高數(shù)據(jù)存貯/傳輸可靠性,一些信號的原始數(shù)據(jù)量,數(shù)據(jù)壓縮的依據(jù) 存在數(shù)據(jù)冗余,時(shí)間冗余 時(shí)間軸上的相關(guān)性 空間冗余 像素間的相關(guān)性 信息熵冗余 數(shù)據(jù)表示的效率 知識冗余 先驗(yàn)知識的利用 心理視覺冗余 合理的分辨率,coding redundancy,Redundancy: R = 1 L /m Approaches: - Standard Huffman - Shifted Huffman - Arithmetic Coding,No redundancy: 8bit,Interpixel redundancy,Spatial redundancy Approaches: - Run Length coding - intraframe predicative coding - LZW coding,Interpixel redundancy,Spatial, time redundancy Approaches: - interframe predicative coding (motion prediction),Psychovisual redundancy,Original 25% quality 15% quality 45,339 b 3,905 b 3,197 b Remove Less important information Approaches: - quantization(lossy), DCT,Compression system model,Two parts: Encoder , Decoder Source encoder: remove redundancy Channel encoder: reduce noise,Source encoder and decoder,Mapper: transform input data to a special format for reducing interpixel redundancy,數(shù)據(jù)編碼分類,無損壓縮(lossless): 變長編碼（Huffman) 行程編碼 算術(shù)編碼 - 醫(yī)學(xué)或商用數(shù)據(jù)的壓縮,有損數(shù)據(jù)壓縮(lossy),預(yù)測編碼 變換編碼（Cosine, Wavelet) - 視頻數(shù)據(jù)的壓縮,Run-Length Encoding (1D),Original data: 05, 05, 05, 05, 11, 11, 1A, 1A, 1A, 1A, 20, 22, 22, 22, 22,Encoding: 05, 04, 11, 02, 1A, 04, 20, 01, 22, 04,Application: be suitable for uniform gray images, FAX coding,Run-Length Encoding (2D),05, 02, 05, 01, 10, 01, 21, 04, 05, 01, 10, 01, 10, 04, 21, 02, 31, 02, 10, 02, 10, 02, 15, 01, 31, 02, 31, 01, 15, 01, 31, 01,Rules: basic unit - maximal square left - right, top - bottom,LZW coding,根據(jù)數(shù)據(jù)本身包含有重復(fù)的字符串(不一定要求空間上相鄰) 每接收一個(gè)字符系列，判斷以前是否出現(xiàn)過，然后用出現(xiàn)過的字符串代替該重復(fù)的部分，輸出對應(yīng)的“指針”（位置） 例如： “aabbccddee” 的指針是 0100，以后每次出現(xiàn)該字符串，就用0100代替。,LZW Notes,Dictionary is not null at first, single symbol Building decompression dictionary is needed Application: GIF(graphic interchange format) TIFF(tagged image file format) PDF(portable document format),Huffman coding,灰度 0 1 2 3 4 5 6 7 概率 0.05 0.05 0.10 0.15 0.25 0.20 0.15 0.05,0.10,0.15,0.25,0.30,0.45,0.55,1.0,0,1,0,0,1,0,1,0,1,0,1,0,1,1,編碼,01100,01101,100,101,00,11,010,0111,編碼: 從根節(jié)點(diǎn)開始到葉子節(jié)點(diǎn) !,Standard Huffman coding,Average bits : 2.2Entropy :2.14 efficiency: 0.973,Standard Huffman disadvantages,Even if 1 bit error, a series of errors , no solutions (example in next page) When decoding, fail to abstract contents from randomly position Computation: k-2 source ranking To symbol with less probability: code length is too long (max: k-1 bits) - shifted Huffman,Error decoding example of Huffman,Code : 011, 1, 01010, 0100, 01011, 00,Gray : a1 a2 a3 a4 a5 a6,a3,a1,a2,a2,a6 .,01010 011 1 1 00,* Encoding : Gray Code,Decoding : Code Gray,010100111100.,01010 00 1 1 1 1 00.,01010 01011 00.,a3,a6,a2,a2,a2,a2,a6.,a3,a5,a6.,* Add 0 : error decoding,* 011 - 010,Shifted Huffman encoding 1,Truncate: 90%(main) - standard Huffman Divide blocks: assign a prefix to each block Shift: prefix + standard Huffman code,Shifted Huffman encoding 2,主區(qū)間120 150，編碼為：c120c150 119=sum(0119)， 低界碼 c119 151=sum(151255)，高階碼 c151 c119 和c151分別作為正、負(fù)區(qū)間碼,Shifted Huffman encoding 3,0區(qū)間：120 150 ， 120150 1區(qū)間：151 181， c151 + 0區(qū)間中對應(yīng)位置的編碼，如170 - 139, 編碼為：c151c139 2區(qū)間：182 212， 區(qū)間碼為：c151 c151 -1區(qū)間：89 119，區(qū)間碼為：c119,算術(shù)編碼(Arithmetic Encoding),將信息量的增加映射為實(shí)數(shù)精度的提高 編碼過程將0，1）區(qū)間不斷細(xì)分,符號序列：C, A, D, A, C, D, B,.,0,1,.,Lossy compression,Lossless: 8:1 lossy: 100:1200:1, quantization 10：1 to 100：1 same in human eyes JPEG, MPEG, H.263 Lossy predictive coding Transform based coding,Lossy predictive coding,DPCM(differential pulse code modulation),Difference:,Predictor :,Delta modulation(DM),Simplest predictor : m=1 Quantier - 1 bit/pixel,Problems: Slope overload: when gray values change rapidly distortion edge blurred Granular noise: when gray values change small spot noise,Problems of delta modulation,Optimal predictor,Minimizing :,Optimal predictor,Global predicator,Fixed predictive coefficients:,Comparison of four predicators,m=1,2,3,1, 階數(shù)增加, 誤差減小,Transform based coding,Principle: Magnitude near 0 in higher frequency Data compression removing those data near 0, same visual result 正交變換 DFT，DCT，Wavelet,Transform based coding model,能量最高的系數(shù)被最細(xì)量化，而能量較低的系數(shù)就被粗量化或被簡單地舍去 。 優(yōu)點(diǎn)：變換系數(shù)的編碼誤差只影響該系數(shù)所在的塊，不會擴(kuò)散到其他的子塊，故變換編碼的抗干擾能力優(yōu)于預(yù)測編碼。,subimage size,Size: larger than 8*8 saturation,Image Compression Standards,Joint Photographics Experts Group(JPEG),reordering,JPEG Coder,DC: F(0,0) , DPCM AC: RLC, Huffman DCT coefficients: Zig-Zig reordering,original image,size : 66616 bytes,JPEG compressed,size：8181 bytes,quality factor : 0.6,original image,size : 66616 bytes,JPEG compressed,size：2742 bytes,quality factor : 0.1,視頻編碼技術(shù),國際電聯(lián)(ITU-T), 標(biāo)準(zhǔn)有: H.261、H.262 、H.263、H.263+ 國際標(biāo)準(zhǔn)化組織(ISO) 標(biāo)準(zhǔn)有MPEG-1、MPEG-2、MPEG-4 、MPEG-7 由兩個(gè)組織聯(lián)合組建的聯(lián)合視頻組(JVT)共同制定的新數(shù)字視頻編碼標(biāo)準(zhǔn): H.264, MPEG-4 part 10(100:1), 四種圖像,I-圖像幀內(nèi)圖，每個(gè)圖像群組由此類型的圖像開始。編碼時(shí)獨(dú)立編碼（ JPEG），解碼時(shí)不參考其他幀； P-圖像預(yù)測圖，用前面的I圖或P圖像進(jìn)行預(yù)測編碼得到，并可以作為下一個(gè)預(yù)測（B圖像或P圖像）的參照圖像。 B-圖像插補(bǔ)圖(雙向預(yù)測圖)，預(yù)測時(shí), 需要用先前及后續(xù)的若干個(gè)圖像作參考， 并作運(yùn)動補(bǔ)償和運(yùn)動估計(jì)； D-圖像，用于快速進(jìn)帶。僅由DC直流分量構(gòu)造的圖像，可在低比特率的時(shí)候做瀏覽用。,MPEG,視頻流的組成:,允許編碼端自行選擇I圖像的使用頻率和在視頻流中的位置。 允許編碼端自行選擇任意兩幀參考圖像（I-圖或P-圖）之間的B圖像數(shù)。 編碼端的視頻流記錄格式可以和圖像顯示順序不同。,顯示的順序：I B B P B B P B B P B B P B B I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 視頻流順序：I P B B P B B P B B P B B I B B 1 4 2 3 7 5 6 10 8 9 13 11 12 16 14 15,MPEG,“I-圖像”編碼,圖像數(shù)據(jù)壓縮采用類似JPEG的算法,“P-圖像”的編碼,差分方法；運(yùn)動矢量估計(jì)；,差分預(yù)測編碼,假設(shè) ：宏塊MPI是宏塊MRJ的最佳匹配塊,運(yùn)動矢量估計(jì),最佳匹配,MSE：,MAD：,“B-圖像”的壓縮編碼,計(jì)算方法與預(yù)測圖像P的算法類似。,可伸縮性分層編碼 （scalable layered coding）,原始視頻流被壓縮至多個(gè)壓縮層碼流（substreams）： 基本層碼流（base substream）：可以被獨(dú)立解碼，提供基本的視頻質(zhì)量保證。 增強(qiáng)層碼流：需要和基本層一起解碼，提供增強(qiáng)的細(xì)節(jié)上的視頻質(zhì)量。,可伸縮性分層編碼,時(shí)域：通過增加或者減少非關(guān)鍵幀（B幀）的方法來調(diào)整幀率從而達(dá)到調(diào)整碼率的目的。 空域：多分辨率 原始視頻通過下采樣得到低分辨率基本層碼流； 原始視頻 - 基本層視頻 增強(qiáng)層碼流。 質(zhì)量: 不同的量化方法,傳統(tǒng)分層編碼的不足,由于它的編碼是以層為最小單位的，所以接收端解碼的時(shí)候也必須以層為最小單位。即要么解碼整個(gè)層的數(shù)據(jù)，要么丟棄整個(gè)層 ；增強(qiáng)層解碼需要在基本層的基礎(chǔ)上進(jìn)行，一旦基本層接收失敗，則整個(gè)解碼過程將失?。?各個(gè)壓縮層的碼率在編碼完成時(shí)就固定了，并且一般比特率相差較大 ，因此，只能實(shí)現(xiàn)離散的有限的碼率調(diào)整，無法保證在帶寬波動范圍內(nèi)始終能得到較高的帶寬利用率。,FGS精細(xì)的可擴(kuò)展性編碼 （fine granular scalable coding）,目標(biāo) ：將原始視頻編碼成一個(gè)可以單獨(dú)解碼的基本層碼流和一個(gè)可以在任何點(diǎn)截?cái)嗟脑鰪?qiáng)層碼（即，增強(qiáng)層中接收到任意量的數(shù)據(jù)后都可以立即解碼） MPEG-4中的FGS： 基本層: 基于變換編碼方式, 提供最低視頻質(zhì)量; 增強(qiáng)層: 位平面編碼技術(shù). 每一幀的增強(qiáng)層碼流可以在任意地點(diǎn)被截?cái)?，接收端解碼獲得的視頻質(zhì)量與實(shí)際收到的數(shù)據(jù)量成正比，提高了帶寬的利用率; 多信道，多優(yōu)先級分層傳輸: 基本層用最高優(yōu)先級和最優(yōu)信道環(huán)境，增強(qiáng)層用低優(yōu)先級較差信道.,