第九章圖象數據壓縮編碼

1、,,第六章圖象數據壓縮編碼,圖像壓縮基礎 無損壓縮 有損壓縮 靜止圖像壓縮編碼的技術標準JPEG,基本內容,數字圖象通常有很大的比特數，這給圖象的傳輸和存儲帶來相當大的困難。數據的壓縮是必不可少的。,圖象壓縮的必要性,the total byte number is: 460×520×3 = 700kB,一部90分鐘的彩色電影，每秒放映24幀。把它數字化，每幀512×512象素，每象

2、素的R、G、B三分量分別占1byte，總比特數為 90×60×24×3×512×512= 101922MB 若用一張可存600兆字節(jié)數據的CD光盤存儲這部電影，光圖象（還有聲音）就需要170張CD光盤。,圖象壓縮的必要性,對圖象數據進行壓縮顯得非常必要 本章討論的問題：在滿足一定條件下，能否減小圖象比特數，以及用什么樣的編碼方法使之減少。,,圖象壓縮的必要性,圖

3、象壓縮是可能的,一般原始圖象中存在很大的冗余度,用戶通常允許圖象失真當信道的分辨率不及原始圖象的分辨率時，降低輸入的原始圖象的分辨率對輸出圖象分辨率影響不大。用戶所關心的圖像區(qū)域有限，可對其余部分圖像采用空間和灰級上的粗化。根據人的視覺特性對不敏感區(qū)進行降分辨率編碼 （視覺冗余）。,圖象壓縮是可能的,原始圖象越有規(guī)則，各象素之間的相關性越強，它可能壓縮的數據就越多。值得指出的是：當前采用的編碼方法得到的結果，離可能壓縮的極限還相

4、差很遠，這說明圖象數據壓縮的潛力是很大的，直到目前為止，它還是個正在繼續(xù)研究的領域。,圖象壓縮是可能的,6.1 圖像壓縮基礎,圖像壓縮所解決的問題是盡量減少表示數字圖像時需要的數據量。減少數據量的基本原理是除去其中多余的數據。 以數學的觀點看，這一過程實際上就是將二維像素陣列變換為一個在統計上無關聯的數據集合。,圖像熵,圖像像素灰度級集合為{ d1 , d2 , …, dm }，對應概率為p ( d1 ) , p ( d2

5、 ),…, p ( dm ) , 則圖像熵定義為,,H表示對輸入灰度級集合進行編碼時所需要的平均位數的下限。 di 出現的概率相等時，熵最大。,圖像編碼壓縮名詞術語,平均碼長,,l為灰度級 rk 所對應的碼字長度。,編碼效率,圖像熵與平均碼長之比,香農無干擾編碼定理,在無干擾條件下,存在一種無失真的編碼方法,使編碼的平均碼長和信源的熵任意接近。,壓縮比Ls為源代碼長度， Ld為壓縮后代碼長度,保真度標準,保真度標準——評價壓

6、縮算法的標準（1）客觀保真度標準（2）主觀保真度標準,a）輸入圖和輸出圖之間的均方根（rms）誤差,b）輸入圖和輸出圖的均方根信噪比,(1) 客觀保真度標準,(2)主觀保真度標準 通過視覺比較兩個圖像，給出一個定性的評價，如很粗、粗、稍粗、相同、稍好、較好、很好，這種評價被稱為主觀保真度標準。,冗余,在數字圖像壓縮中的三種基本的數據冗余:編碼冗余像素間冗余心理視覺冗余,編碼冗余,通過圖像灰度級直方圖可以深入

7、了解編碼結構，從而減少表達圖像所需的數據量。,例：,由于任何給定的像素值，原理上都可以通過它的鄰居預測到，所以單個像素攜帶的信息相對是小的。 為減少圖像中的像素間冗余，二維像素陣列必須變換為更有效的形式。,像素間冗余,空間冗余 幾何冗余 幀間冗余,例：原圖像數據： 234 223 231 238 235 壓縮后數據： 234 11 -8 -7 3,心理視覺

8、冗余,在正常的視覺處理過程中各種信息的相對重要程度不同，那些不重要的信息稱做心理視覺冗余,無損壓縮與有損壓縮,無損壓縮基于統計模型，減少源數據流中的冗余，同時保持信息不變。又稱為冗余壓縮。典型代表有Huffman 編碼，算術編碼、游程長度編碼等。有損壓縮以犧牲部分信息量為代價而換取縮短平均碼長的編碼壓縮方法。在壓縮中丟失了部分信息，又稱為熵壓縮。典型代表有離散余弦變換編碼、有損預測編碼等。一般地，有損壓縮的壓縮效率高于無損壓縮。,實

9、驗二 圖像增強 下周二做 ，地點不變（交郵政編碼分割程序）,No.13,6.2 無損壓縮,在很多應用中，如醫(yī)療和商業(yè)文檔的歸檔、衛(wèi)星成像的處理、數字X光照相術，無損壓縮時唯一可以接受的數據壓縮方式。 無損壓縮常由兩種彼此獨立的操作組成：(1)為減少像素間冗余建立一種可替代的圖像表達方式；(2)對這種表達方式進行編碼以便消除編碼冗余。,一、基本原理 通過減少編碼冗余來達到壓縮的目的。將在圖像中出現次數多

10、的像素值給一個短的編碼，將出現次數少的像數值給一個長的編碼。二、霍夫曼編碼是即時碼: 是唯一可譯碼,其中任意一個碼字都只能與一種信號存在對應關系,而且任意一個碼字都不能是其他碼字的前綴。,6.2.1 霍夫曼編碼（屬于統計編碼）,信號源 a={a1, a2, a3, a4, a5, a6}，其概率分布為p1=0.1 p2=0.4 p3=0.06 p4=0.1 p5=0.04 p6=0.3，求最佳Huffman碼。,方法：將信

11、源符號按出現概率從大到小排成一列，然后把最末兩個符號的概率相加，合成一個概率。,二、Huffman編碼舉例,Huffman編碼,方法：把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的概率加起來，合成一個概率。 重復上述做法，直到最后剩下兩個概率為止。從最后一步剩下的兩個概率開始逐步向前進行編碼。每步只需對兩個分支各賦予一個二進制碼，如對概率大的賦予碼元0，對概率小的賦予碼元1。,建立概率統計表和編碼樹符號

12、 概率 1 2 3 4 a2 0.4 0.4 0.4 0.4 0.6 a6 0.3 0.3 0.3 0.3 0.4 a1 0.1 0.1 0.2 0.3 a4 0.1 0.1

13、 0.1 a3 0.06 0.1 a5 0.04,霍夫曼編碼舉例,編碼過程：符號 概率 編碼 1 2 3 4a2 0.4 1 0.4 1 0.4 1 0.4 1 0.6 0a6

14、0.3 00 0.3 00 0.3 00 0.3 00 0.4 1a1 0.1 011 0.1 011 0.2 010 0.3 01a4 0.1 0100 0.1 0100 0.1 011 a3 0.06 01010 0.1 0101 a5

15、0.04 01011,霍夫曼編碼舉例,霍夫曼編碼,例子：將010100111100解碼 解碼過程： 01010 011 1 1 00 a3 a1 a2 a2 a6,a2 a6 a1 a4 a3 a5 1 00 011 0100 01010 01011,信號源 a={a1,

16、a2, a3, a4, a5, a6}，其概率分布為p1=0.1 p2=0.4 p3=0.06 p4=0.1 p5=0.04 p6=0.3，求最佳Huffman碼。,a2 a6 a1 a4 a3 a5 1 00 011 0100 01010 01011,編碼的平均長度:,其信源的熵為2.14bits/symbol,霍夫曼編碼編碼效率為0.937,霍

17、夫曼編碼,靜態(tài)編碼在壓縮之前就建立好一個概率統計表和編碼樹。算法速度快，但壓縮效果不是最好動態(tài)編碼對每一個圖像，臨時建立概率統計表和編碼樹。算法速度慢，但壓縮效果最好,霍夫曼編碼的特點,編碼值不唯一當圖像灰度值分布很不均勻時，霍夫曼編碼效率高。編碼過程要經過Ｎ-２次合并（有Ｎ個灰度級），Ｎ較大時，計算量大．改進：用亞最優(yōu)變長碼：截斷霍夫曼編碼，霍夫曼平移編碼,6.2.2 算術編碼（屬于統計編碼 ）（自學）,假設某個字符的出現

18、概率為 80%，該字符事實上只需要 -log2(0.8) = 0.322 個二進制位進行編碼,難道真的能只輸出 0.322 個 0 或 0.322 個 1 嗎？,算術編碼的輸出是：一個小數,算術編碼對整條信息（無論信息有多么長），其輸出僅僅是一個數，而且是一個介于0和1之間的二進制小數。例如算術編碼對某條信息的輸出為1010001111，那么它表示小數0.1010001111，也即十進制數0.64,,,從整個符號序列出發(fā)，采用遞推形式

19、連續(xù)編碼在算術編碼中源符號和碼字間的一一對應關系并不存在。1個算術碼字要賦給整個信源符號序列而碼字本身確定0和1之間的1個實數區(qū)間隨著符號序列中的符號數量增加，用來代表它的區(qū)間減小，而表達區(qū)間的信息單位數量變大,算術編碼的特點,例：來自一個4-符號信源{a,b,c,d}的由5個符號組成的符號序列：abccd. 已P(a)=0.2, P(b)=0.2, P(c)=0.4, P(d)=0.2.,可用0.068來表示整個符號序列,6.2.

20、3 行程編碼 RLE（ 屬于統計編碼 ）,行程：具有相同灰度值的像素序列。是一種熵編碼，廣泛應用于各種圖象格式的數據壓縮處理中,　如BMP, TIFF, JPEG。編碼思想：用行程的灰度和行程的長度代替行程本身。,例：設重復次數為 iC, 重復像素值為 iP 編碼為：iCiP iCiP iCiP,編碼前：aaaaaaabbbbbbcccccccc 編碼后：7a6b8c,RLE比較適合于二值圖像的編碼,(1)

21、一維行程編碼 對圖象進行行掃描時，行內各象素的灰度級可組成一個整數序列x1, x2, …, xN。在行程編碼中，我們將這個序列映射成整數對(gk, lk)，其中gk表示灰度級， lk表示行程。,行程編碼,(2)二維行程編碼 一維行程編碼只考慮消除每行內象素的相關性，未考慮行間象素的相關性。二維行程編碼的基本原理是跟蹤各個黑色和白色游程的起始和終結點。,原圖象文件：277560字節(jié),行程編碼文件：279860字

22、節(jié),壓縮比：0.992,原圖象文件：66616字節(jié),行程編碼文件：9272字節(jié),壓縮比：7.185,行程編碼,如果圖像是由很多塊顏色或灰度相同的大面積區(qū)域組成的，特別是二值圖象，采用行程編碼可以達到很高的壓縮比。如果圖像中的數據非常分散，則行程編碼不但不能壓縮數據，反而會增加圖像文件的大小。為了達到較好的壓縮效果，一般不單獨采用行程編碼， 而是和其他編碼方法結合使用。,分析：,6.3 有損壓縮,有損壓縮是以犧牲圖像重構的準確

23、度為代價換取壓縮能力增加的概念為基礎的。如果產生的失真是可以容忍的，則壓縮能力上的增加就是有效的。,有損預測編碼：直接對像素在圖像空間進行操作, 稱為空域方法。鄰近的M個值預測當前值，當前值與預測值之差量化編碼，（一維、二維預測等）變換編碼：基于圖像變換的編碼方法，稱為頻域方法。,預測編碼的基本原理 利用已有樣本對新樣本進行預測，將樣本的實際值與其預測值相減得到誤差值，再對誤差值進行編碼。通常誤差值比樣本值小

24、得多，從而達到數據壓縮的效果。,6.3.1 有損預測編碼,預測器,可以是固定的，也可以是自適應的；可以是線性的，也可以是非線性的。 預測器設計得越好，對輸入的數據壓縮就越多。,有損預測編碼,有損預測編碼–DPCM(差分脈沖編碼調制)系統,量化器,,編碼器,,,預測器,,,,,,,,,,,壓縮圖像,輸入圖像,,德爾塔調制最優(yōu)量化器最佳線性預測器線性自適應預測編碼,有損預測編碼,一維線性預測,有損預測編碼,最佳線性預測 采

25、用均方誤差（MSE）為極小值的準則來獲得DPCM，稱為最佳線性預測，亦即此時預測誤差最小。對于圖像來說，最佳線性預測的關鍵就是求出各個預測系數，使得預測誤差最小，從而使得接收圖像和原圖像差別最小。,有損預測編碼,,量化器,,編碼器,,,預測器,,,,,,,,,,,壓縮圖像,輸入圖像,,為簡化分析，設：,最佳線性預測 選 ak 使E{e 2n }最小。,在假fn具有零均值和方差為σ2的條件下解出聯立方程的解集：,R-1是m

26、15;m自相關矩陣的逆矩陣,方程的解 a1, a2, …, am 便是一組最佳的預測系數。壓縮效果可用方差σ2e(n)來衡量：,原始序列相關性越強， R(i)越大，σ2e(n)越小，壓縮效果越顯著；原始序列互不相關，即R(i) =0，i≠0，則， σ2e(n)= σ2一點也不能壓縮。,,,最佳線性預測,6.3.2 變換編碼,變換編碼通常是指將某種正交變換作為映射變換，用變換系數來表示原始圖象，對變換系數進行編碼。對一個 N ×

27、; N 的圖像f(x,y) ：,正變換逆變換,變換編碼,若輸入是廣義平穩(wěn)序列，則存在一種最佳的正交變換—K-L變換。所謂最佳： 1.變換系數互不相關； 2.數值較大的方差出現在少數系數中，即能量高度集中。 這樣，可在允許的總的均方誤差一定的條件下，將數據減到最少。,變換編碼,由于卡洛變換(KLT)的基向量是原始圖象協方差矩陣的特征向量，對于不同的圖象，有著不同的最佳基向量。基向量不

28、是固定的，所以一般沒有快速算法，因此只宜于作理論分析和試驗用。實用上用得較多的是離散傅立葉變換(DFT)、離散余弦變換(DCT)、離散小波變換(DWT)和沃爾什—哈達瑪變換(WHT)。它們的基向量是固定的，有比較成熟的快速算法。,變換編碼壓縮框圖,各框圖實現了何種冗余壓縮?,基于DCT的圖像壓縮編碼,離散余弦變換 是圖像壓縮中最常用的一種變換 。,DCT變換在信息壓縮能力和計算復雜性之間提供了平衡。,,,MATLAB函數

29、 g = dct2 ( f );反變換 f = idct2 ( g );,討論 1: 子圖像的選擇,保留 25% 的系數來重構圖像,,計算復雜度,子圖像的尺寸對變換編碼重構誤差的影響,子圖像的選擇,放大的原圖,使用 25%的DCT系數、 8x8子圖恢復圖像,DCT 系數,子圖:8x8 pixels,子圖:2x2 pixels,子圖:4x4 pixels,討論 2:量化處

30、理: 比特分配,表示變換系數時，可根據每個系數的重要程度分配不同比特數: - 較重要的系數 ? 分配大比特數 - 不太重要的系數 ? 分配小比特數或不分配兩種常用的比特分配方法 -區(qū)域編碼 : 基于最大方差分配比特,對所有子圖使用單一固定的模板進行編碼 -門限編碼 : 基于最大量級的變換系數分配比特,區(qū)域編碼舉例,,門限編碼舉例,門限模板,門限系數排序序列,,討論3: DCT 量化矩陣,圖

31、像質量和量化程度的矛盾：大的量化步長會產生大的圖像失真；小的又會導致低壓縮率 如何有效地量化 DCT 系數? 由于人眼對高頻不敏感，低頻信號就比高頻信號更重要。 如， JPEG 對高頻系數用了大的量化步長，圖像并沒有出現明顯的失真。,變換編碼舉例,原圖512x512 pixels,Fourier,Hadamard,DCT,Error,子圖像:　8x8 pixels,量化時截取50% 系數 (只保留32 個最大系數),RMS Err

32、or = 1.28,RMS Error = 0.86,RMS Error = 0.68,制定圖像標準的國際組織： ISO（國際標準化組織）CCITT（國際電報電話咨詢委員會）聯合組織下進行制定的,連續(xù)色調圖像壓縮標準靜止幀黑白、彩色壓縮（JPEG標準）連續(xù)幀單色、彩色壓縮（MPEG標準）,6.4 靜止圖像壓縮編碼的技術標準JPEG,,靜止幀黑白、彩色壓縮（JPEG）JPEG標準簡述JPEG壓縮流程JPEG壓縮算法的實現

33、 顏色變換零偏置轉換 頻域變換系數量化 符號編碼JPEG壓縮舉例,有三種壓縮系統：（1）基線編碼系統：面向大多數有損壓縮的應用，采用DCT變換壓縮。（2）擴展編碼系統：面向遞進式應用，從低分辨率到高分辨率逐步遞進傳遞的應用。（3）獨立編碼系統：面向無損壓縮的應用，采用無損預測壓縮，符號編碼采用霍夫曼或算術編碼。一個產品或系統必須包括對基線系統的支持,,1. JPEG標準簡述,2. JP

34、EG壓縮流程,,構造8x8的子圖,,輸入圖像NxN,(2)顏色空間轉換 人眼對亮度更敏感，提取亮度特征，將RGB轉換為YCbCr模型，編碼時對亮度采用特殊編碼：Y = 0.299R + 0.5870G + 0.1140B（亮度）Cb = –0.1787R – 0.3313G +0.5000B +128（色度）Cr = 0.5000R – 0.4187G – 0.0813B + 128（色度）,,,,顏色解碼：

35、R = Y + 1.40200(Cr – 128)G = Y – 0.34414(Cb – 128) – 0.71414(Cr – 128)B = Y + 1.77200(Cb –128),(1)構造子圖像 (子圖像尺寸：8 x 8),JPEG,(３) 零偏置轉換對于灰度級是2n的像素，通過減去2n-1，替換像素本身對于n=8，即將0~255的值域，通過減去128，轉換為值域在-128~127之間的值目的：使像素的絕對

36、值出現3位10進制的概率大大減少,,JPEG,,例:用8x8的JEPG基線標準，壓縮并重構下列子圖525561667061647363596690109856972625968113144104667363587112215410670696761681041268868707965607077685875857164595561

37、65838779696865767894,,JPEG,0偏置轉換后-76-73-67-62-58-67-64-55-65-69-62-38-19-43-59-56-66-69-60-1516-24-62-55-65-70-57-626-22-58-59-61-67-60-24-2-40-60-58-49-63-68-58-51

38、-65-70-53-43-57-64-69-73-67-63-45-41-49-59-60-63-52-50-34,,JPEG,(４) 頻域變換 （DCT 變換）頻域變換產生64個系數第一個系數稱為直流系數（DC系數）其余的63個系數稱為交流系數（AC系數）,,JPEG,正向DCT變換（N = 8）后變成-415-29-62 25 55-20-1 3 7-21-62

39、 9 11-7-6 6-46 8 77-25-30 10 7-5-50 13 35-15-9 6 0 3 11-8-13-2-1 1-4 1-10 1 3-3-1 0 2-1-4-1 2-1 2-3 1-2-1-1-1-2-1-1 0-1,,JPEG,(５) 系數量化對于亮度和度色使用

40、不同的量化閾值模板，并取整,,JPEG,色度的量化模板系數17 1824479999999918212666999999992426569999999999476699999999999999999999999999999999999999999999999999999999999999999999999

41、99999,,,量化是JPEG算法中損失圖像精度的根源,JPEG,,量化變換后的數組(取整采用四舍五入方式),經正向DCT變換后,(６) 符號編碼將量化后的系數，按之字形重新排序成矢量，全零結尾用特殊符號EOB,Zig-Zag編碼,[-26 -3 1 -3 -2 -6 2 -4 1 -4 1 1 5 0 2 0 0 -1 2 0 0 0 0 0 -1 -1 EOB],符號編碼：[-26 -3 1 -3 -2 -6 2 -4

42、1 -4 1 1 5 0 2 0 0 -1 2 0 0 0 0 0 -1 -1 EOB],,DC和AC系數用不同的方式分別編碼,JPEG,DC的編碼方式（預測+統計）第一步：求DPCM (差分脈沖調制碼)，用當前的DC，減去前一個子圖的DC VVVV ：DIFF = DC – PRE_DC第二步：根據DIFF求出區(qū)間號： SSSS 通過DIFF查區(qū)間編號表得出區(qū)間號SSSS根據SSSS查哈夫曼編碼表得出SSSS的哈夫

43、曼編碼第三步：對VVVV編碼，正數是自己，負數用補碼（求反）,,JPEG,用-9查區(qū)間表得： SSSS = 4 用4查哈夫曼編碼表得：101 VVVV = -9二進制編碼為: 1001求反: 1001 = 0110 最后的編碼為: 101+0110= 1010110,,,PreDC-17,,,DC-26,,,DC的編碼方式（預測+統計）,例子：DC = -26PRE_DC = -17

44、 DIFF = -26 - （-17）= -9,JPEG,AC系數的編碼方式編碼由兩部分組成：區(qū)間號編碼(RRRR/SSSS)+系數本身(VVVV)第一部分： SSSS： 區(qū)間號(查AC區(qū)間表) RRRR：該系數前值為0的系數的個數（行程數）。RRRR/SSSS的編碼:查區(qū)間編碼表第二部分： VVVV：系數本身編碼,,[-26 -3 1 -3 -2 -6 2 -4 1 -4 1 1 5 0 2 0

45、0 -1 2 0 0 0 0 0 -1 -1 EOB],JPEG,符號編碼結果舉例完成后的編碼數組（重排的）是：1010110 0100 001 0100 0101 100001 0110 100011 001 100011 001 001 100101 1101110 111000 0110 11110100 000 1010完成編碼的重排數組的總位數是92，不壓縮需要8x8x8=512

46、位。結果的壓縮率是5.6:1。,,[-26 -3 1 -3 -2 -6 2 -4 1 -4 1 1 5 0 2 0 0 -1 2 0 0 0 0 0 -1 -1 EOB],JPEG,JPEG2000 vs. JPEG,low bit-rate performance,作業(yè)：,已知信源a,b,c,d，e,f,g,h出現的概率分別為0.20,　0.09,　0.11,　0.13,　0.07,　0.12,　0.08,　0.20。 試將該信源編

47、為霍夫曼編碼，要求寫出編碼過程，并計算霍夫曼編碼的平均碼長及編碼效率．,區(qū)間DC哈夫曼編碼表,,,區(qū)間 編碼 區(qū)間 編碼 0 00 6 1110 1 010 7 11110 2 011

48、 8 111110 3 100 9 1111110 4 101 A 11111110 5 110 B 111111110,,,,返

49、,區(qū)間表,,范圍 DC差區(qū)間 AC區(qū)間 0 0 N/A -1，1 1 1 -3，-2，2，3 2 2 -7,…,-4，4,…,7

50、 3 3 -15,…,-8，8,…,15 4 4 -31,…,-16，16,…,31 5 5 -63,…,-32，32,…,63 6 6,,,,,AC,DC,

51、區(qū)間AC哈夫曼編碼表,,,行程/區(qū)間 編碼 行程/區(qū)間 編碼 0/0 1010 0/7 1111000 0/1 00 0/8 1111110110 0/2

52、 01 0/9 11111111100000 0/3 100 0/A 11111111100000 0/4 1011 1/1 1100 0/5 11010