第二章 離散餘弦轉換 離散餘弦轉(Discrete Cosine Transformation ,DCT)

Presentation on theme: "第二章 離散餘弦轉換 離散餘弦轉(Discrete Cosine Transformation ,DCT)"— Presentation transcript:

1 第二章 離散餘弦轉換 離散餘弦轉(Discrete Cosine Transformation ,DCT)
第二章 離散餘弦轉換 離散餘弦轉(Discrete Cosine Transformation ,DCT) 將一數位影像進行運算後轉換成另一種資料格式的方法。運算後的資料可以有利於再進一步處理應用。如特徵值的擷取或是資料的隱藏(data hiding)。 2.1 數位影像頻率域表示法 2.2 離散餘弦轉換的介紹 2.3 離散餘弦轉換程式釋意

2 2.1數位影像頻率域表示法 除了空間域數位影像資料格式之外，還有一種資料格式也可以清楚地表示數位影像，稱為「頻率域數位影像資料格式」。
常見的空間域至頻率域轉換運算方法有： 1.離散小波轉換 (Discrete Wavelet Transformation , DWT) 離散餘弦轉換 (Discrete Cosine Transformation , DWT) 頻率域數位影像資料係從空間域數位影像資料進行運算轉換得來。

3 何謂頻率域？ 由前一章的說明我們可以知道空間域數位資料是以二維陣列存放，現將二維陣列資料轉換成為一維陣列資料。
圖2.1、2.2、2.3是三張對一個有16個元素的一維空間域陣列進行DCT頻率域轉換的示意圖。

4 圖2.1 所顯示為DCT頻率域轉換的輸入值。 是一個一維空間域的陣列。 將輸入的值之大小以波的高度表示，即為圖中的波形圖。
元素位置由左至右為0~15

5 圖2.2 DCT基頻波形圖。 基頻波形編號(wave number) N 0~15 所代表的是頻率由低到高。

6 圖2.3 將輸入值進行頻率域轉換後會得到輸出值如圖。
輸出值位置0的係數是2，這2即表示2倍之編號0之基頻波(basis wave)簡稱基頻波0。 係數為0，則表示輸出值中沒有那個位置的基頻波形。

7 結論 所謂頻率域(frequency domain)之數位影像資料，即是將空間域數位影像資料經過運算後所得到的以數個基本頻率組合之結果。圖2.1中的輸入值之元素個數等於基頻波的個數，又等於輸出值係數的個數。 基頻波編號愈大，則其中相鄰小方塊的高度變化也愈大 基頻波形0中相鄰的小方塊的高度並沒有變化，所以我們也稱其為「直流波」(Direct Current , DC)，其他相鄰方塊高度有變化的基頻波形稱之為「交流波」(Altermating Current , AC)

8 2.2 離散餘弦轉換的介紹 本節首先以圖例介紹離散餘弦轉換的觀念

9 2.2.1離散餘弦轉換的概念 以離散餘弦轉換將空間域數位影像資料轉換成頻率域，這個動做又可稱之為離散餘弦”正”轉換(Forward Discrete Cosine Transformation , FDCT)。反之則稱為離散餘弦反轉換(Inverse DCT , IDCT) 以FDCT代表”正”轉換。 以IDCT 代表”反”轉換。

10 2.2.1離散餘弦轉換的概念 將數位灰階影像完整地劃分成8*8像素大小的區塊(block)且每一個部份並不重疊，如圖2.4
根據[4]中所描述的方法，FDCT將每一個空間域中所有像素值減去128後，再以特殊的公式做轉換，即可得到一個和空間域區塊中像素個數相同的頻率區塊，IDCT則是加上128。

11 O(x,y)表示在空間域數位影像(x,y)位置中的像素值。
f(x,y)是將O(x,y)的像素值減去128後的結果。 D(i,j)表示在頻率域資料(I,j)位置的係數值。 (D(I,j) | i=0 to N-1；j=0 to N=1)是對一個N*N的空間域數位影像(f(x,y) | i=0 to N-1；j=0 to N-1)進行FDCT運算後的結果。

12 2.2.1離散餘弦轉換的概念 基本上，將原空間域數位影像經FDCT轉換後，再以IDCT還原的空間域數位影像內的所有像素值不應該有誤差的存在。但在做FDCT及IDCT運算時須使用”浮點運算”，所以一定有截尾誤差(truncation error)發生，但只要在合理範圍內的誤差，一般我們都是可以忍受的。

13 2.2.2 離散餘弦正轉換和離散餘弦反 轉換的公式 相關公式有二： 空間域頻率域(FDCT) 頻率域空間域(IDCT)

14 2.2.3基頻影像、影像頻率，影像邊緣和影像 能量等觀念的釐清
將一個8*8的頻率域區塊陣列中(0,0)位置填入一個非零的數值，其餘位置的係數均為零，如右圖a。 經IDCT還原成一塊8*8像素大小的空間區塊，此8*8的頻率域區塊即為DCT的一個基頻影像(basis image)，如右圄b。 這個全黑的空間域區塊又稱為(0,0)基頻影像。

15 接下來再將(0,1)位置填入一個非零數值，其餘位置均填入零，再以IDCT還原成一塊8*8小大的(0,1)基頻影像…
不斷重複以上動做到(7,7)基頻影像還原後，即可得到8*8共64張基頻影像。按非零係數的位置排列，組合成一個64*64像素大小的大區塊，此大區塊就稱為DCT二維基頻影像(basis image of 2D DCT)

16

17 基本觀念 在對基頻影像有一粗略的瞭解後，我們必須建立的一些觀念 基頻影像所表示的意義和圖2.2中一維陣列 中的基頻相同

18 基本觀念 二維DCT係數不一定是正值，也有可能是負。

19 基頻影像之黑白相間區塊及垂直、水平交錯變化示意圖
每個區塊中黑白相間小區塊個數，依箭頭所指的方向愈來愈多

20 DCT係數中AC及DC之分佈結構圖 (0,0)基頻影像是一塊沒有變化，只有一種顏色的黑色小區塊，恰如一維頻率域的基頻波形0一樣。

21 如果我們以FDCT的公式，如(2.1)式去計算頻率域中的(0,0)位置的係數值，我們可以得到底下之結果：

22 DCT與頻率的關連性 在圖左上區域黑白相間小區塊個數較少的基頻影像所對應的頻率域係數稱為低頻(low frequency)
右下角黑白相間區塊個數較多的基頻影像，所對應的頻率域係數稱為高頻(high frequency) 在低頻和高頻中間的稱為中頻(medium frequency) 在最左上角全黑的區塊稱為DC。

23 二維基頻影像的頻率分佈圖

24 DCT轉換與邊緣的關係 在圖2.9中最上方一列中除了DC外，每一個基頻影像中的黑白小區塊都是以垂直方式互相交錯。如右上圖
凡黑白交錯之處皆稱為邊緣，如虛線所示。

25 邊緣是以垂直方式呈現，故稱垂直邊緣(vertical edge)
以水平方式呈現，稱水平邊緣(horizontal edges) 如右圖以交錯方式呈現則稱交錯邊緣。(diagonal edges)

26 二維基頻影像邊緣分佈圖 邊緣區域的係數值比較大

27 能量介紹 黑白小區塊以水平方向互相變化，表示有水平能量(horizontal energy)，如右上圖
黑白小區塊以垂直方向互相變化，表示有垂直能量(vertiacl energy)，如右下圖 至於能量以水平及垂直方式交錯呈現，則稱此為交錯能量(diagonal energy)。

28 二維基頻影像的能量分佈情形

29 能量比較圖 a圖有兩次水平變化，b圖有七次又平變化，所以b圖的水平能量大於a圖。 同理，d圖的垂直能量大於c圖。

30 如果一空間域數位影像的水平能量較大，則在頻率區塊中，上方的係 數值將較大。 如果一空間域數位影像的垂直能量較大，則在頻率區塊中，左方的係數 值將較大。 如果一空間域數位影像的交錯能量較大，則在頻率區塊中，中間的係數值將較大。

31 整理 垂直邊緣多水平能量大上方區域係數值較大 水平邊緣多垂直能量大左方區域係數值較大 交錯處較多交錯能量大中間區域係數值較大

32 離散餘弦轉換的例子 以實例的方式來表達FDCT與 IDCT的概念 例子：對於一個8*8像素大小的空間域區塊內所有像素值的影響。

33 在圖2.23的(0,0)位置放入一值，假設為200，其他放0。
表示原空間域的影像是由(0,0)基頻影像的200陪所組成的。 以IDCT轉換後，可得2.23下方的結果。 每一個像素值均相同。

34 在圖2.25的(0,7)位置放入一值，假設為200，其他放0。
表示原空間域的影像是由(0,7)基頻影像的200陪所組成的。 以IDCT轉換後，可得2.25下方的結果。 由垂直邊緣組合而成的影位影像

35 在圖2.27的(7,0)位置放入一值，假設為200，其他放0。
表示原空間域的影像是由(7,0)基頻影像的200陪所組成的。 以IDCT轉換後，可得2.27下方的結果 由水平邊緣所組合而成的數位影像。

36 將圖2.29中FDCT的結果分成兩部份，一部份僅含DC值，另一部份僅含(7,7)中的數值

37 分成兩部份後，結果如2.30圖左邊的頻率域原始陣列1、陣列2
結果為加上128之結果 將兩個結果各個像素減去128 再加兩個陣列相同位置的像素相加 得一新陣列，再加上128就得到IDCT結果3 發現IDCT結果3跟圖2.29的IDCT一樣。

38 上例說明了什麼？ 說明了空間域數位影像係由其轉換後的頻率域係數所相對的基頻影像所組合而成，而每個係數值的大小表示所相對應的基頻影像倍數。
依上例，空間原始陣列係由200倍的(0,0)基頻影像及200倍的(7,7)基頻影像所組成。

39 2.3 離散餘弦轉換程式釋意