取 樣 與 量 化 中原大學 電子工程學系暨研究所 通訊科技研究實驗室 繆紹綱 博士.

Presentation on theme: "取 樣 與 量 化 中原大學 電子工程學系暨研究所 通訊科技研究實驗室 繆紹綱 博士."— Presentation transcript:

1 取 樣 與 量 化 中原大學 電子工程學系暨研究所 通訊科技研究實驗室 繆紹綱 博士

2 取樣與量化 fs 數位影像：影像在空間座標和亮度都離散化的影像 取樣：在不同空間位置取出函數(灰階)值做為樣本
量化：用一組整數值來表示這些樣本的過程 fs 輸入影像 取樣器 量化器 數位計算機 影像數位化的兩大過程

3 取樣 均勻矩形取樣 ， y x 傅立葉轉換 2. 另一個二維取樣函數 : 傅立葉轉換 : R
：限頻寬(bandlimited)的二維連續函數 傅立葉轉換 2. 另一個二維取樣函數 : 傅立葉轉換 : ， R y x

4 取樣(Cont.) 3. :為影像取樣點灰度值的二維脈衝函數陣列 傅立葉轉換 : 4. 二維取樣定理： 為有限頻寬，且滿足
:為影像取樣點灰度值的二維脈衝函數陣列 傅立葉轉換 : 4. 二維取樣定理： 為有限頻寬，且滿足 使得各個相鄰區域R不彼此混疊

5 其他取樣型態(1) 取樣矩陣 取樣點位置 : 矩陣 稱為取樣矩陣 取樣矩陣 V 所產生的取樣點陣 x 1 2 y v0

6 其他取樣型態(2) 取樣矩陣 取樣點陣圖 y x 1 1                     
取樣矩陣 取樣點陣圖      y          1  1          x                         

7 其他取樣型態(3) 週期性矩陣 一維週期性函數： N 維週期性函數： < Ex > N = 2 取樣矩陣： 週期矩陣：
取樣矩陣： 週期矩陣： 單位矩陣： , k為整數 , k為整數向量

8 其他取樣型態(4) 取樣密度 u v 1. 矩形取樣 代表四邊形面積 對一有限頻寬函數，設 則其取樣不產生混疊的最小取樣密度 2.六角形取樣
取樣點數與四邊形的個數一樣； 1. 矩形取樣 對一有限頻寬函數，設 則其取樣不產生混疊的最小取樣密度 2.六角形取樣 週期矩陣 取樣矩陣 代表四邊形面積 u 2r v

9 其他取樣型態(5) 最小取樣密度 3.比較 …… 效率比1.15倍 …… 減少13.4%取樣點數 （六角形）

10 重建 1.運用空間濾波器 (理想二維低通濾波器) 頻率響應： < 重建影像 是許多二維sinc函數的加權和 > 反轉換 ；

11 重建(Cont.) 2.空間內插函數 方形函數 方形內插（零階內插） 三角形函數 三角形內插（一階內插）

12 量化 純量量化(scalar quantization, SQ)：
對於無記憶性 ( memoryless )的資料源，將各個取 樣值視為互不相關彼此獨立， 針對個別取樣點作逐點量化 多對一函數的映射(mapping)關係： 把樣本值的取值範圍分成若干個區間，用某個代表值代表這一區間內所 有可能的值 多對一對映函數 量化器 量化器的輸入及輸出

13 均勻量化(1) 條件 取樣結果： ， 取值範圍 均勻地分成L個子區間 ， 每個子區間 對應到一個定值
機率密度函數 常數P 取樣結果： ， 取值範圍 均勻地分成L個子區間 ， 每個子區間 對應到一個定值 其中的L個 ， ，稱為重建(reconstruction)位準 另外(L+1)個 ， ，稱為決策(decision)邊界或位準

14 均勻量化(2) 量化過程 量化值： 量化誤差： 常用的失真測度： 量化器最佳化：要使平均失真D 最小 L個子區間誤差平方總和： ，

15 均勻量化(3) 最佳量化值： ，即每個子區間 的中間值 可得最小的量化誤差 Example 設子區間 的長度為 誤差平方總和：
最佳量化值： ，即每個子區間 的中間值 可得最小的量化誤差 Example 設子區間 的長度為 誤差平方總和： 加大量化區間的數目L對原影像的保真度有很大的幫助 ；

16 非均勻量化(1) 條件 機率密度 不是常數 在 較小處，可取較大的量化區間長度；反之，則取較小 的量化區間 採用 失真測度之非均勻量化器
機率密度 不是常數 在 較小處，可取較大的量化區間長度；反之，則取較小 的量化區間 採用 失真測度之非均勻量化器 量化過程 誤差平方總和

17 非均勻量化(2) 令D值最小化： ， 得到 與 的兩個關係式： (A) (B) 各子區間決策邊界 是量化重建位準值間 的中間值
得到 與 的兩個關係式： ， (A) 各子區間決策邊界 是量化重建位準值間 的中間值 (B) 每一個 是 落在子區間 下的條件期望值

18 非均勻量化(3) 實現：最佳最小均方或Lloyd-Max量化器 給定 、 、L 及 (高斯) (1) 假定一個 的值，由 (B)式取 ，求出
如果不相等，則重新假定值 ，再回到第(1)步，繼續計算求出 ，直到 符合要求為止 (高斯) (拉普拉斯) 或

19 非均勻量化(4) 最佳均方誤差量化器之性質 非均勻量化與均勻量化之關係 b. 量化誤差對量化器的輸出為正交，即
a. 量化器的輸出是輸入的不偏(unbiased)估測，即 b. 量化誤差對量化器的輸出為正交，即 c. 若 與 分別為零平均且變異量為1之隨機變數 ， 則 非均勻量化與均勻量化之關係 機率密度 為均勻分佈： 得到決策與重建準位： 為與 有相同分佈但平均為 且便異數為　之隨機變數 ， (常數) 推導出：

20 非均勻量化(5) 均方誤差 均方誤差量化器之訊雜比(SNR) 均勻量化器的誤差 ， 均勻分佈在 之間
均勻量化器的誤差 ， 均勻分佈在 之間 均方誤差量化器之訊雜比(SNR) 一個均勻分佈的隨機變數，範圍為A 時其變異數 若有 個位元的均勻量化器，我們有 均勻分佈之最佳均方誤差量化器：每個位元約有6分貝的訊雜比增益 均方誤差： (dB) 訊雜比(SNR) =

21 壓縮擴展型量化器 壓縮擴展器(compander) ：具有非均勻量化的功能 g f g g 非線性轉換 非線性轉換 均勻量化

22 壓縮擴展型量化器(Cont.) 壓縮擴展器之非線性轉移函數 若 ，且若 為一零平均的隨機變數，則 非線性轉換函數
若 ，且若 為一零平均的隨機變數，則 非線性轉換函數 對雷利(Rayleigh)機率密度函數 正轉換函數 逆轉換函數 , 可得

23 向量量化(1) 向量量化(vector quantization,VQ)： 過程： 向量，以此向量為量化的單位
由於實際信號各取樣值之間存在有相關性，故把若干取樣值集合成一個 向量，以此向量為量化的單位 過程： a. 由 N 個實數連續純量值 fi 組成的 被映射到 另一個 N 維向量 b. f 的VQ是將一個 N 維向量空間分割成L個決策區域Ci， ：碼向量(codevector) 碼向量的集合：碼簿(codebook)

24 向量量化(2) c. VQ 的量化誤差 ；失真測度 決定重建向量 ri 以及決策區域 Ci 的邊界 失真量最小化 平均失真D=E[ ] 令
最佳的重建向量

25 向量量化(3) K-平均(K-mean)演算法 (2) 中心條件： 將 對 最小化
(1) 最近距離條件： < 使平均失真度測度 D 為最小的最近距離條件 > (2) 中心條件： 將 對 最小化 < 每個重建向量 必須使 Ci 中的平均失真最小 > Step 1 ：由初估值 ，將所有可能的 f 代入 (1) 式中找到Ci 的估測 Step 2 ：給了Ci 的估測後，計算 (2) 式之條件中的重心以得 Step 3 ：以此 做為一新估測值重複上述動作

26 向量量化(4) LBG演算法 1. 初始化:定出碼簿大小L、失真臨界值ε、初始碼簿R0={ri,0；1≦i≦L}及
訓練序列T={fn；n = 1,2,…..,N}，N>>L 2. 對碼簿 Rm={ri,m；1≦i≦L}，找出訓練序列T 的最小誤差分割 若d ( fn,ri,m ) ≦ d ( fn,rj,m ) , 3. 計算平均失真： 若(Dm-1-Dm)/Dm≦ε，則輸出碼簿 Rm 4. 求得 使 最小 若 d(f, ) = (f – )T(f– )，即平方誤差，則 正是 個向量的算術平均值

27 向量量化 (VQ) 的設計與運用 訓練序列與長度的選擇 失真測度的選擇 改進最佳分割疊代法的收斂速度 縮短最佳向量的比對時間 減少碼簿大小
發展自適性碼簿以擴大適用性 發展多級殘餘向量量化 VQ與小波轉換結合

28 量化造成的假輪廓的結果展示 (a)原影像，位元數 B= 8 (b)B = 6 (c)B = 4 (d) B = 3

29 向量量化的編解碼結果展示 (a)原始Lena影像 (b)碼簿=cb_64x4，PSNR=32.8，CR=5.33
(c)碼簿=cb_64x16，PSNR=28.9，CR=21.33 (d)碼簿=cb_128x4，PSNR=34.5，CR=4.57