離散餘弦轉換(英語:discrete cosine transform, DCT)是與傅立葉轉換相關的一種轉換,類似於離散傅立葉轉換,但是只使用實數。離散餘弦轉換相當於一個長度大概是它兩倍的離散傅立葉轉換,這個離散傅立葉轉換是對一個實偶函數進行的(因為一個實偶函數的傅立葉轉換仍然是一個實偶函數),在有些變形裏面需要將輸入或者輸出的位置移動半個單位(DCT有8種標準類型,其中4種是常見的)。
最常用的一種離散餘弦轉換的類型是下面給出的第二種類型,通常我們所說的離散餘弦轉換指的就是這種。它的逆,也就是下面給出的第三種類型,通常相應的被稱為「反離散餘弦轉換」,「逆離散餘弦轉換」或者「IDCT」。
有兩個相關的轉換,一個是離散正弦轉換,它相當於一個長度大概是它兩倍的實奇函數的離散傅立葉轉換;另一個是改進的離散餘弦轉換,它相當於對交疊的數據進行離散餘弦轉換。
離散餘弦轉換,尤其是它的第二種類型,經常被信號處理和圖像處理使用,用於對信號和圖像進行有損數據壓縮。這是由於離散餘弦轉換具有很強的「能量集中」特性:大多數的信號資訊(包括聲音和圖像)往往集中在離散餘弦轉換後的低頻部分,而且當信號具有接近馬可夫過程的統計特性時,離散餘弦轉換的去相關性接近於K-L轉換(Karhunen-Loève轉換——它具有最優的去相關性)的性能。
例如,在圖像編碼標準JPEG與視訊編碼標準MJPEG和MPEG的各個標準中都使用了離散餘弦轉換。在這些標準制中都使用了二維的第二種類型離散餘弦轉換,並將結果進行量化之後進行熵編碼。這時對應第二種類型離散餘弦轉換中的n通常是8,並用該公式對每個8x8塊的每行進行轉換,然後每列進行轉換。得到的是一個8x8的轉換系數矩陣。其中(0,0)位置的元素就是直流分量,矩陣中的其他元素根據其位置表示不同頻率的交流分量。
一個類似的轉換,改進的離散餘弦轉換被用在高級音頻編碼、Vorbis和MP3音頻壓縮當中。
離散餘弦轉換也經常被用來使用譜方法來解偏微分方程,這時候離散餘弦轉換的不同的變量對應着數組兩端不同的奇/偶邊界條件。
上面提到的DCT I~IV是和偶數階的實偶DFT對應的。原則上,還有四種DCT轉換(Martucci, 1994)是和奇數階的實偶DFT對應的,它們在分母中都有一個的系數。但是在實際應用中,這幾種變型很少被用到。
最平凡的和奇數階的實偶DFT對應的DCT是1階的DCT(1也是奇數),可以說轉換只是乘上一個系數而已,對應於DCT-V的長度為1的狀況。
儘管直接使用公式進行轉換需要進行次操作,但是和快速傅立葉轉換類似,我們有複雜度為的快速算法,這就是常常被稱做蝶形轉換的一種分解算法。另外一種方法是通過快速傅立葉轉換來計算DCT,這時候需要的預操作和後操作。
以下簡單介紹兩種利用DFT來計算DCT-II的方法
令輸入信號為
並將以在處對稱表示
即
此時令 表示
則之DFT為
將 做以下化簡
此時兩側同乘
可得
此時右式即為欲求之DCT轉換,而左式可藉由2N點數的DFT來計算,使用快速演算法的情況下,運算之時間複雜度為
第二個方法由Narasimha與Peterson在1978年提出,此方法係藉由巧妙的編排來達成,首先令
並且
此時X(m)可化簡為
令第二項之改為 ,則兩式可合併為
右側為對之N點的scaled DFT
因此,,其中
其中 是對之N點的DFT,並且可以簡單的驗證具有如下性質
而因 為實數輸入,
因此欲求之 ,
在使用FFT快速演算法的情況下,運算之時間複雜度同樣為
但此方法較方法一直接運算2N點數的DFT快上約2倍。
- K. R. Rao and P. Yip, 離散餘弦轉換:算法、優點和應用(Discrete Cosine Transform: Algorithms, Advantages, Applications) (Academic Press, Boston, 1990).
- A. V. Oppenheim, R. W. Schafer, and J. R. Buck, 時間離散信號處理 (Discrete-Time Signal Processing), second edition (Prentice-Hall, New Jersey, 1999).
- S. A. Martucci, 對稱卷積和離散正弦餘弦轉換 (Symmetric convolution and the discrete sine and cosine transforms), IEEE Trans. Sig. Processing SP-42, 1038-1051 (1994).
- Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/ (頁面存檔備份,存於互聯網檔案館). 一個免費的C語言庫GPL,可以計算DCT-I~IV的1維到多維的任意大小的轉換
- M. Frigo and S. G. Johnson, "FFTW3的設計和實現 (頁面存檔備份,存於互聯網檔案館)," Proceedings of the IEEE 93 (2), 216–231 (2005).
- On the Computation of the Discrete Cosine Transform. (1978, June 1). IEEE Journals & Magazine | IEEE Xplore. https://ieeexplore.ieee.org/document/1094144 (頁面存檔備份,存於互聯網檔案館)
- ^ 引用錯誤:沒有為名為
Luo
的參考文獻提供內容
- ^ 4.0 4.1 引用錯誤:沒有為名為
Stankovic
的參考文獻提供內容
- ^ 引用錯誤:沒有為名為
Britanak
的參考文獻提供內容
- ^ 6.0 6.1 引用錯誤:沒有為名為
Hersent
的參考文獻提供內容
- ^ 7.0 7.1 引用錯誤:沒有為名為
AppleInsider standards 1
的參考文獻提供內容
Rao, R. K., & Yip, P. (1990). Discrete Cosine Transform: Algorithms, Advantages, Applications (1st ed.). Academic Press.