轉換編碼 視轉換為座標軸之旋轉 視轉換為基底函數之分解 轉換編碼之方法 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 1. 視轉換為座標軸之旋轉 二維向量的座標軸轉換 假設x1x2座標系統上的每一個二維向量x代表一對相鄰的像素值
定義xj軸的變異數(variance)為： 其中，M代表影像中的向量總數， xji是第i個向量的xj值，xj是所有的向量的xj之平均值。

7 1. 座標軸旋轉的例子 y y1 x1 (4,4) x 二維直角座標系，座標系統可以是無限多個
只要找到具有正交(orthogonal)特性的基底向量即可。正交的基底向量其個別向量的內積值為零。

8 1. 座標軸旋轉的例子

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

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

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

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

13 3. 影像轉換 二維空間 兩個基底向量，個別是二維的向量 Ex: (1,0) and (0,1) 三維空間 三個基底向量，個別是三維的向量
…. k維空間 k個基底向量，個別是k維的向量

14 頻率域表示法 (cont.) 16維空間 16個基底向量，個別是16維的向量

15 已知： 十六個基底向量的第一維資料 輸入向量的第一維度資料 未知：十六個基底向量的個別加權 wi 頻率域表示法 第一維度

16 已知： 十六個基底向量的第二維資料 輸入向量的第二維度資料 未知：十六個基底向量的個別加權 wi 頻率域表示法 第二維度

17 已知： 十六個基底向量的第三維資料 輸入向量的第三維度資料 未知：十六個基底向量的個別加權 wi 頻率域表示法 第三維度

18 解 聯立方程式 十六個未知數：十六個基底向量的個別加權 wi 十六個等式，每個維度產生一個等式 頻率域表示法

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

20 3. 數位餘絃轉換(DCT)

21 基頻影像 空間域         DC         AC 頻率域 (8X8) DCT 二維基頻影像

22 基頻影像頻率圖

23 基頻影像邊緣分佈圖

24 基頻影像能量分佈圖

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

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