第十章 轉換編碼 視轉換為座標軸之旋轉 視轉換為基底函數之分解 影像轉換 轉換編碼之方法 JPEG DCT 演算法 JPEG DCT 之結果

Presentation on theme: "第十章 轉換編碼 視轉換為座標軸之旋轉 視轉換為基底函數之分解 影像轉換 轉換編碼之方法 JPEG DCT 演算法 JPEG DCT 之結果"— Presentation transcript:

1 第十章 轉換編碼 視轉換為座標軸之旋轉 視轉換為基底函數之分解 影像轉換 轉換編碼之方法 JPEG DCT 演算法 JPEG DCT 之結果
總結 靜宜大學資訊工程系

2 轉換編碼(transform coding)
轉換編碼的做法 將原訊號經過一個轉換變成另一種表示法。轉換後的表示法之能量較原始訊號來得集中，而且可以經由逆轉換(reverse transformation)回復成原始訊號。 轉換編碼包含兩個部分 正向轉換處理(forward transformation) 逆向轉換(reverse transformation) 轉換編碼的特性 理論上，轉換編碼必須是可逆的 實際的運作會受限於資料型態與電腦的溢位(overflow or underflow)而造成失真

3 轉換編碼(transform coding)
影像轉換的做法 將原來N×N的影像先分割成不重疊的n×n影像區塊，然後對每一個區塊進行單位轉換(unitary transform) ，將原本影像區塊中的像素相關性打散，使得訊號的能量集中於很少數的幾個轉換係數中，如此一來，許多不重要的轉換係數再經過量化後就可忽略，可提升整體的編碼效率。 可配合HVS(Human visual system)之對比敏感函數於轉換係數的量化工作上，而達到視覺的無失真壓縮。

4 absolute dct values of lenna row 256
Row 256 of lenna absolute dct values of lenna row 256 200.00 160.00 120.00 80.00 40.00 500.00 0.00 0.00 0.00 200.00 400.00 600.00 0.00 200.00 400.00 600.00

5 利用DFT轉換前後的範例

6 10.1 視轉換為座標軸之旋轉 二維向量的座標軸轉換 假設x1x2座標系統上的每一個二維向量x代表一對相鄰的像素值
定義xj軸的變異數(variance)為： 其中，M代表影像中的向量總數， xji是第i個向量的xj值，xj是所有的向量的xj之平均值。

7 10.1 座標軸旋轉的例子

8 10.1 視轉換為座標軸之旋轉 單位轉換(unitary transform) 轉換的特性
為一可逆之線性轉換，其核心為一組完整、相互正交之單位基底函數。 單位轉換不會改變向量間的歐基里得距離(Euclidean distance) ，也就是它具有距離保持性。 所以經過單位轉換前後的總變異數大小不變 轉換的特性 將原本資料的相關性(取樣間累贅)打散，並將訊號的大部分能量集中到相當少的轉換係數上 轉換本身並不能達到資料壓縮的效果

9 10.1 視轉換為座標軸之旋轉 二維座標轉換：旋轉45度 正轉換 Y=AX，其中A為轉換矩陣 逆轉換 X=BY，其中B=A-1。

10 10.2 視轉換為基底函數之分解 轉換的動作可視為座標軸的旋轉 把在X與Y中的每一列視為基底函數 Y=AX ，其中A為轉換矩陣
X=BY ，其中B=A-1。 不同的轉換只是旋轉的方式不同而已。 把在X與Y中的每一列視為基底函數 正轉換可看成將原本的影像分解成一組給定之基底函數的線性和(linear sum) ，所得到之係數即各基底函數作線性和時所該乘上的加權比重。 逆轉換可看成將給定的基底函數乘上轉換係數Y作為各基底函數之加權比重。

11 10.3 影像轉換 影像轉換的基本特性 將影像內像素間的相關性打散 利用獨立於影像的基底函數 轉換需能快速完成
希望能將大部分的能量集中於少數的轉換係數上 利用獨立於影像的基底函數 最佳的轉換函數會隨著影像區塊的統計特性而不同，也就是必須針對不同的影像區塊使用不同的基底函數 通常會捨棄最佳的轉換而採用獨立於影像的基底函數，也就是針對任意的影像區塊都使用相同的基底函數 轉換需能快速完成 N個點轉換所需的計算一般為O(n2) 的等級。有一些轉換具有快速演算法能將其所需的計算量由O(n2) 的等級，降低至O(nlogn) 的等級。因此對於一個可分開的n×n的二維轉換，藉由依序作橫列及縱列的一維轉換，其所需的計算量為O(n2logn) 而非O(n4) 。

12 10.3.2 數位傅利葉轉換(DFT) 數位傅利葉轉換(DFT)
DFT通常被用在做頻譜分析與濾波器之設計上，對於一個n×n的方塊，二維正DFT之定義為 二維逆DFT定義為 其中 ，f 為原始影像訊號，F 為轉換後之結果。

13 10.3.2.數位傅利葉轉換(DFT) DFT轉換的二維核心(kernel)是可分開的 因此二維的DFT可以用一維的DFT來完成
DFT產生的係數為複數(包括實部與虛部) ，而儲存與處理這些2n2個轉換項的複數是DFT的缺點。但是因為這些轉換項具有共軶對稱性，因此有將近一半的轉換項實際上可由其他轉換項所算得。

14 10.3.3. 數位餘絃轉換(DCT) 一個n×n的影像區塊其二維DCT正轉換為 一個n×n的影像區塊其二維DCT逆轉換為
其中f 為原始影像訊號，F 為轉換後之結果。

15 數位餘絃轉換(DCT)

16 數位餘絃轉換(DCT)

17 10.3.5 Walsh-Hadamard 轉換(WHT)
基底函數為不同頻率的方波 基底函數非常簡單，只含+1與-1 適合硬體實作 將原始資料相關性打散的能力略差

18 10.3.5 Walsh-Hadamard 轉換(WHT)
，其中H2n為2×2的Hadamard矩陣

19 10.3.5 Walsh-Hadamard 轉換(WHT)

20

21 10.4 轉換編碼之方法 一般轉換編碼都使用DCT或WHT 這種獨立於影像的二維轉換，而在轉換後得到轉換係數後(coefficients) ，採用特定的方法來作選擇，量化以及編碼這些係數。 轉換函數 影像區塊 轉換係數 區域取樣之選擇法 編碼 量化

22 10.4.1 區域取樣之選擇法 區域取樣之選擇法 區域區樣法(zonal sampling)
如果轉換係數視坐落在某個特定區域內，則予以保留；否則將其值設為0。 保留的係數隨後進行量化與編碼的動作 可利用固定位元數編碼或依照頻率給定不同的位元數 位元配置法(bit allocation) 在每一個區域內的係數可以使用不同的位元數(但總位元數相同) ，使得整個量化誤差最小 第一回合需計算係數方差值(variance)並決定量化器的位元分配 第二回合真正為每一個方塊作編碼的動作

23 10.5 JPEG 演算法 JPEG包含三個主要元件 基本系統(base system) 系統擴充程式 獨立的無失真壓縮法
滿足大部分的影像編碼使用之演算法 系統擴充程式 包含12bit/pixel的輸入，漸進式(progressive)以及階層式重建(hierarchical build-up) 獨立的無失真壓縮法 DPCM/Huffman Coding DPCM/Arithmetic Coding

24 10.5.1 JPEG 基本系統 Input image Blocking DCT Thresholder
Binary bit stream Entropy coder Zigzag Scan D sequencing Quantizer Entropy decoder Inverse Zigzag Scan Dequantizer output image Blocking Integration Thresholder compensator IDCT

25 10.5.1 JPEG 基本系統 DCT/IDCT formula Separable
BASIS2D(i,j;u,v) = BASIS1D(i;U)BASSIS1D(j ; v) process row, then column.

26 10.5.1 JPEG 基本系統 Quantization T=deadzone threshold
T+3Q/2 T+Q/2 -T-2Q -T-Q -T T T+Q T+2Q -T-Q/2 -T-3Q/2 T=deadzone threshold Q=quantizer step size

27 JPEG 基本系統 二維DCT之結果的係數矩陣中，左上角那個係數稱為直流係數(DC) ，它與原方塊之平均明亮度成正比；其他的63個轉換係數成為交流係數(AC) 。 直流係數會以無失真的DPCM作編碼，DPCM是利用前一個方塊的直流係數來作預測 交流係數量化後會產生許多0，尤其是高頻的部分，為了能夠從這些0取得好處，原來的二維DCT係數會以鋸齒狀掃描(zigzag scan)成一維向量。

28 JPEG 基本系統

29 JPEG 基本系統 編碼交流係數(AC) 每一個非零的係數首先會以8位元(0-255)(以I來描述) ，其二進位形式為
I=‘NNNNSSSS’ 四個最低位元SSSS用來定義係數的大小類別 前四個位元NNNN用來記錄相對於前一個非0系數的位置 I=0 表示方塊結束(end of block) I=‘ ’表示一個長度為16的連續0 總共有10*16+2=162個符號 每個符號送出前均經過 Huffman 編碼 接著傳送對應類別所需的k個位元 第k類別的範圍為(2k-1, 2k-1)與(-2k+1, -2k-1)

30 JPEG 基本系統

31 JPEG 基本系統

32 JPEG DCT之一例

33 JPEG DCT之一例 所有的轉換係數藉由使用一個使用者自訂的正常化矩陣(normalization matrix)達到正常化的目的。

34 JPEG DCT之一例 EOB

35 10.5.2 JPEG 基本系統—解壓縮 量化後的係數先藉由Huffman解碼法重建，然後依下面的式子與以逆正常化
接著利用整數DCT做逆轉換，得到重建的方塊。

36 JPEG 基本系統—解壓縮 由編碼所產生的誤差為

37 JPEG 基本系統—解壓縮

38 Results bytes 23116 bytes, Cr=34.0

39 Results bytes 33079 bytes, Cr=23.78

40 Results bytes 49746 bytes, Cr=15.80

41 Results bytes 26614 bytes, Cr=29.55

42 Results bytes 25485 bytes, Cr=30.86

43 JPEG Lossless Coding DPCM Prediction No 1 A 2 B 3 C 4 A+B-C 5
No 1 A 2 B 3 C 4 A+B-C 5 A-(B-C)/2 6 B-(A-C)/2 7 (A+B)/2