1.轉(zhuǎn)自:離散余弦變換(DCT)的定義_小火車_新浪博客
已知離散傅里葉變換(DFT)為:
由于許多要處理的信號都是實信號霸褒,在使用DFT時由于傅里葉變換時由于實信號傅立葉變換的共軛對稱性導(dǎo)致DFT后在頻域中有一半的數(shù)據(jù)冗余偏化。
離散余弦變換(DCT)是對實信號定義的一種變換,變換后在頻域中得到的也是一個實信號舍肠,相比DFT而言,DCT可以減少一半以上的計算。DCT還有一個很重要的性質(zhì)(能量集中特性):大多書自然信號(聲音窘面、圖像)的能量都集中在離散余弦變換后的低頻部分翠语,因而DCT在(聲音、圖像)數(shù)據(jù)壓縮中得到了廣泛的使用财边。由于DCT是從DFT推導(dǎo)出來的另一種變換肌括,因此許多DFT的屬性在DCT中仍然是保留下來的。
推導(dǎo)N點長實序列的DCT酣难,首先來定義一個新的長度為2N的序列:
可看作是將周期為N的序列x[m]做一個周期延拓成一個周期為2N的序列谍夭。如圖1中第一張圖。
再來看圖1中第一張圖是關(guān)于x = -1/2對稱的憨募,要讓他關(guān)于x = 0對稱需要將其向右平移1/2個單位紧索,得到x’[m] = x’[m – 1/2]就是關(guān)于x = 0對稱的周期序列了(如圖1中第二張圖)。
然后求這個2N序列的DFT:
就是DCT-2型離散余弦變換.從上面的過程也可以直接看出,離散余弦變換相當于一個長度大概是它兩倍的離散傅里葉變換.
變換后的x[n]是以2N為周期,偶對稱的序列: X[N+n] = X[N+n-2N] = X[n-N] = x[N-n]
定義變換矩陣C[n,m]:
用計算機計算DCT-2 (用的是O(n^2)樸素算法菜谣,用于驗證正交特性以及觀察其頻域數(shù)據(jù)):
DCT的結(jié)果:
對相同序列FFT的結(jié)果:
比較DFT和FFT的結(jié)果可以觀察出DCT變換只有實部珠漂,而DFT變換后有虛部。在這個例子中DCT在頻域中只用3個點就可以表示這個信號尾膊,而DFT變換后在頻域中需要5個點來表示信號甘磨。
參考:http://fourier.eng.hmc.edu/e161/lectures/dct/node1.html
2.轉(zhuǎn)自:二維DCT變換 - Wuyuan's Blog
寫這篇文章的目的主要是為了給x264打好基礎(chǔ),x264用的是整數(shù)DCT變換眯停,所以就先來說說DCT變換吧济舆。
DCT(Discrete Cosine Transform),又叫離散余弦變換莺债,它的第二種類型滋觉,經(jīng)常用于信號和圖像數(shù)據(jù)的壓縮签夭。經(jīng)過DCT變換后的數(shù)據(jù)能量非常集中,一般只有左上角的數(shù)值是非零的椎侠,也就是能量都集中在離散余弦變換后的直流和低頻部分第租,下面我會用matlab來演示整個過程。
我們首先來看看一維的DCT變換我纪,這是二維的基礎(chǔ)慎宾。一維的DCT變換共有8種,其中最實用的是第二種形式浅悉,公式如下:
其中c(u)是加上去一個系數(shù)趟据,為了能使DCT變換矩陣成為正交矩陣,在后面二維變換將看到他的作用术健。N是f(x)的總數(shù)汹碱。相比其他幾種形式,他的運算還是比較簡單的荞估,因此也用的比較廣咳促。
二維DCT變換是在一維的基礎(chǔ)上再進行一次DCT變換,這個比較好理解勘伺,直接看公式:
這里我只討論兩個N相等的情況跪腹,也就是數(shù)據(jù)是方陣的形式,在實際應(yīng)用中對不是方陣的數(shù)據(jù)都是先補齊再進行變換的飞醉。為了matlab仿真方便點冲茸,寫成矩陣形式:
下面就用matlab來模擬一下,使用隨機生成的4x4矩陣作為輸入冒掌,程序如下:
Y是使用上面的公式進行變換,YY是用matlab自帶的dct2函數(shù)變換蹲盘,結(jié)果是是:
可以看出Y和YY的結(jié)果是一樣的股毫,這也進一步驗證了上面的公式是正確的。由于X是我隨機生成的召衔,相關(guān)性很小铃诬,變換后的結(jié)果比較亂;如果是信號或圖像這樣相關(guān)性比較大的數(shù)據(jù)的話苍凛,數(shù)值會集中在左上角趣席,右下角一般都是零,再使用“之”字型掃描得到數(shù)據(jù)流會包含很多連續(xù)的零醇蝴,編碼后數(shù)據(jù)量會非常小宣肚,這就是DCT變換帶來的好處。
DCT逆變換的公式如下:
矩陣形式可以由正變換的公式直接推出來悠栓,因為在A中加了c(i)這個系數(shù)霉涨,使得A成為了正交矩陣按价,所以我們就可以這樣做:
在用matlab來驗證是否能反變換出原來的數(shù)據(jù):
X使用的是上面正變換用的數(shù)據(jù),運行后得到的X1為:
X1=
61.000019.000050.000020.0000
82.000026.000061.000045.0000
89.000090.000082.000043.0000
93.000059.000053.000097.0000
和X完全相等笙瑟。在實際進行編碼的時候楼镐,比如JPEG壓縮的時候,只會對Y左上角的數(shù)據(jù)進行傳輸往枷,所以解碼出來的內(nèi)容不會完全和原來的相同框产。
說道DCT就順便提一下x264中的整數(shù)DCT變換,整數(shù)DCT變換是以DCT變換為基礎(chǔ)的错洁,為了減少計算量做的一些調(diào)整秉宿,下面我寫一下整數(shù)DCT變換公式的大致推導(dǎo)過程:
然后根據(jù)A是正交矩陣,把c=bd帶入A中墓臭,使行向量為單位向量可以得到d=0.4142蘸鲸。令d=0.5,得到b*b=0.4,代入上面的式子中窿锉,把0.5提取出來放到右邊的點乘中就得到了:
這樣在對大括號部分進行計算時就都是加法和減法了酌摇,而且在精度上沒有太大降低。在x264實際編碼中嗡载,變換和量化是一起進行的窑多,使得編碼速度有了很大的提高。