离散余弦变换

**離散餘弦變換**（英語：**discrete cosine transform, DCT**）是與傅立葉變換相關的一種變換，類似於離散傅立葉變換，但是只使用實數。離散餘弦變換相當於一個長度大概是它兩倍的離散傅立葉變換，這個離散傅立葉變換是對一個實偶函數進行的（因為一個實偶函數的傅立葉變換仍然是一個實偶函數），在有些變形裡面需要將輸入或者輸出的位置移動半個單位（DCT 有 8 種標準類型，其中 4 種是常見的）。

最常用的一種離散餘弦變換的類型是下面給出的第二種類型，通常我們所說的離散餘弦變換指的就是這種。它的逆，也就是下面給出的第三種類型，通常相應的被稱為 "反離散餘弦變換"，"逆離散餘弦變換" 或者 "IDCT"。

有兩個相關的變換，一個是離散正弦變換，它相當於一個長度大概是它兩倍的實奇函數的離散傅立葉變換；另一個是改進的離散餘弦變換，它相當於對交疊的數據進行離散餘弦變換。

## 應用

離散餘弦變換，尤其是它的第二種類型，經常被信號處理和圖像處理使用，用於對信號和圖像（包括靜止圖像和運動圖像）進行有損數據壓縮。這是由於離散餘弦變換具有很強的 "能量集中" 特性：大多數的自然信號（包括聲音和圖像）的能量都集中在離散餘弦變換後的低頻部分，而且當信號具有接近馬爾可夫過程的統計特性時，離散餘弦變換的去相關性接近於 K-L 變換（Karhunen-Loève 變換 —— 它具有最優的去相關性）的性能。

例如，在靜止圖像編碼標準 JPEG 中，在運動圖像編碼標準 MJPEG 和 MPEG 的各個標準中都使用了離散餘弦變換。在這些標準制中都使用了二維的第二種類型離散餘弦變換，並將結果進行量化之後進行熵編碼。這時對應第二種類型離散餘弦變換中的 _n_ 通常是 8，並用該公式對每個 8x8 塊的每行進行變換，然後每列進行變換。得到的是一個 8x8 的變換係數矩陣。其中（0,0）位置的元素就是直流分量，矩陣中的其他元素根據其位置表示不同頻率的交流分量。

一個類似的變換，改進的離散餘弦變換被用在高級音頻編碼，Vorbis 和 MP3 音頻壓縮當中。

離散餘弦變換也經常被用來使用譜方法來解偏微分方程，這時候離散餘弦變換的不同的變量對應著數組兩端不同的奇 / 偶邊界條件。

## 形式化定義

形式上來看，離散餘弦變換是一個線性的可逆函數 $F:R^{n}\rightarrow R^{n}$ 其中 **R** 是實數集，或者等價的說一個 $n\times n$ 的方陣。離散餘弦變換有幾種變形的形式， 它們都是根據下面的某一個公式把 $n$ 個實數 $x_{0},\ldots ,x_{n-1}$ 變換到另外 $n$ 個實數 $f_{0},\ldots ,f_{n-1}$ 的操作。

### DCT-I

　
: $f_{m}={\frac {1}{2}}(x_{0}+(-1)^{m}x_{n-1})+\sum _{k=1}^{n-2}x_{k}\cos \left[{\frac {\pi }{n-1}}mk\right]$

有些人認為應該將 $x_{0}$ 和 $x_{n-1}$ 乘以 ${\sqrt {2}}$ ，相應的將 $f_{0}$ 和 $f_{n-1}$ 乘以 ${\frac {1}{\sqrt {2}}}$ 。這樣做的結果是這種 DCT-I 矩陣變為了正交矩陣（再乘一個係數的話），但是這樣就不能直接和一個實偶離散傅立葉變換對應了。

一個 $n=5$ 的對實數 _abcde_ 的 DCT-I 型變換等價於一個 8 點的對實數 _abcdedcb_（偶對稱）的 DFT 變換，結果再除以 2（對應的，DCT-II~DCT-IV 相對等價的 DFT 有一個半個抽樣的位移）。需要指出的是，DCT-I 不適用於 $n<2$ 的情況（其它的 DCT 類型都適用於所有的整數 _n_）。

所以，DCT-I 暗示的邊界條件是： $x_{k}$ 相對於 $k=0$ 點偶對稱，並且相對於 $k=n-1$ 點偶對稱； 對 $f_{m}$ 的情況也類似。

### DCT-II

　
: $f_{m}=\sum _{k=0}^{n-1}x_{k}\cos \left[{\frac {\pi }{n}}m\left(k+{\frac {1}{2}}\right)\right]$

DCT-II 大概是最常用的一種形式，通常直接被稱為 DCT。

有些人更進一步的將 $f_{0}$ 再乘以 ${\frac {1}{\sqrt {2}}}$ （參見下面的 DCT-III 型的對應修改）。這將使得 DCT-II 成為正交矩陣（再乘一個係數的話），但是這樣就不能直接和一個有半個抽樣位移的實偶離散傅立葉變換對應了。

所以，DCT-II 暗示的邊界條件是： $x_{k}$ 相對於 $k=-{\frac {1}{2}}$ 點偶對稱，並且相對於 $k=n-{\frac {1}{2}}$ 點奇對稱； 對 $f_{m}$ 相對於 $m=0$ 點偶對稱，並且相對於 $m=n$ 點奇對稱。

### DCT-III

　
: $f_{m}={\frac {1}{2}}x_{0}+\sum _{k=1}^{n-1}x_{k}\cos \left[{\frac {\pi }{n}}\left(m+{\frac {1}{2}}\right)k\right]$

因為這是 DCT-II 的逆變換（再乘一個係數的話），這種變形通常被簡單的稱為逆離散餘弦變換。

有些人更進一步的將 $x_{0}$ 再乘以 ${\sqrt {2}}$ （參見上面的 DCT-II 型的對應修改），這將使得 DCT-III 成為正交矩陣（再乘一個係數的話），但是這樣就不能直接和一個結果有半個抽樣位移的實偶離散傅立葉變換對應了。

所以，DCT-III 暗示的邊界條件是： $x_{k}$ 相對於 $k=0$ 點偶對稱，並且相對於 $k=n$ 點奇對稱； 對 $f_{m}$ 相對於 $m=-{\frac {1}{2}}$ 點偶對稱，並且相對於 $m=n-{\frac {1}{2}}$ 點偶對稱。

### DCT-IV

　
: $f_{m}=\sum _{k=0}^{n-1}x_{k}\cos \left[{\frac {\pi }{n}}\left(m+{\frac {1}{2}}\right)\left(k+{\frac {1}{2}}\right)\right]$

DCT-IV 對應的矩陣是正交矩陣（再乘一個係數的話）。

一種 DCT-IV 的變形，將不同的變換的數據重疊起來，被稱為改進的離散餘弦變換。

DCT-IV 暗示的邊界條件是： $x_{k}$ 相對於 $k=-{\frac {1}{2}}$ 點偶對稱，並且相對於 $k=n-{\frac {1}{2}}$ 點奇對稱；對 $f_{m}$ 類似。

### DCT V~VIII

上面提到的 DCT I~IV 是和偶數階的實偶 DFT 對應的。原則上，還有四種 DCT 變換（Martucci, 1994）是和奇數階的實偶 DFT 對應的，它們在分母中都有一個 $n+{\frac {1}{2}}$ 的係數。但是在實際應用中，這幾種變型很少被用到。

最平凡的和奇數階的實偶 DFT 對應的 DCT 是 1 階的 DCT（1 也是奇數），可以說變換只是乘上一個係數 $a$ 而已，對應於 DCT-V 的長度為 1 的狀況。

## 反變換

DCT-I 的反變換是把 DCT-I 乘以係數 ${\frac {2}{n-1}}$ 。
DCT-IV 的反變換是把 DCT-IV 乘以係數 ${\frac {2}{n}}$ 。
DCT-II 的反變換是把 DCT-III 乘以係數 ${\frac {2}{n}}$ ，反之亦然。

和離散傅立葉變換類似，變化前面的歸一化係數僅僅是常規而已，改變這個係數並不改變變換的性質。例如，有些人喜歡在 DCT-II 變換的前面乘以 ${\sqrt {\frac {2}{n}}}$ ，這樣反變換從形式上就和變換更相似，而不需要另外的歸一化係數。

## 計算

儘管直接使用公式進行變換需要進行 $O(n^{2})$ 次操作，但是和快速傅立葉變換類似，我們有複雜度為 $O(n\log(n))$ 的快速算法，這就是常常被稱做蝶形變換的一種分解算法。另外一種方法是通過快速傅立葉變換來計算 DCT，這時候需要 $O(n)$ 的預操作和後操作。

以下簡單介紹兩種利用 DFT 來計算 DCT-II 的方法

### 方法一

令輸入信號為 $x(n)\,,n=0,1,...,N-1$

 
並將 $y(n)$ 以 $x(n)$ 在 $(2N-1)/2$ 處對稱表示

 
即 $y(n)=\left\{{\begin{matrix}x(n),&{\mbox{if }}n=0,1,...,N-1\\x(2N-n-1),&{\mbox{if }}n=N,N+1,...2N-1\end{matrix}}\right.$

 
此時令 $W_{2N}$ 表示 $e^{\frac {-j2\pi }{2N}}$

 
則 $y(n)$ 之 DFT 為

$$
Y(m)=\Sigma _{n=0}^{2N-1}y(n)W_{2N}^{nm}
$$

 
將 $Y(m)$ 做以下化簡

$$
{\begin{aligned}Y(m)&=\sum _{n=0}^{N-1}y(n)W_{2N}^{nm}+\sum _{n=N}^{2N-1}y(n)W_{2N}^{nm}\\&=\sum _{n=0}^{N-1}y(n)W_{2N}^{nm}+\sum _{n=N}^{2N-1}x(2N-n-1)W_{2N}^{nm}\\&=\sum _{n=0}^{N-1}y(n)W_{2N}^{nm}+\sum _{n=0}^{N-1}x(n)W_{2N}^{(2N-n-1)m}\\&=\sum _{n=0}^{N-1}x(n)[W_{2N}^{nm}+W_{2N}^{-(n+1)m}],\,\,\,\,m=0,1,...,2N-1\end{aligned}}
$$

 
此時兩側同乘 ${\frac {1}{2}}W_{2N}^{m/2}$

 
可得 ${\frac {1}{2}}W_{2N}^{m/2}Y(m)=\sum _{n=0}^{N-1}x(n)\cos {[(2n+1){\frac {m\pi }{2N}}]},\,\,\,\,\,\,m=0,1,...,N-1$

 
此時右式即為欲求之 DCT 轉換，而左式可藉由 2N 點數的 DFT 來計算，使用快速演算法的情況下，運算之時間複雜度為 $O(NlogN)$

### 方法二

第二個方法由 Narasimha 與 Peterson 在 1978 年提出，此方法係藉由巧妙的編排 $y(n)$ 來達成，首先令

$$
y(n)=x(2n)$ 並且 $y(N-1-n)=x(2n+1),\,\,\,\,\,\,n=0,1,...,{\frac {N}{2}}-1
$$

 
此時 X (m) 可化簡為

$$
X(m)=\sum _{n=0}^{N/2-1}y(n)\cos {[{\frac {(4n+1)m\pi }{2N}}]}+\sum _{n=0}^{N/2-1}y(N-n-1)\cos {[{\frac {(4n+3)m\pi }{2N}}]},\,\,\,\,\,\,\,m=0,1,...,N-1
$$

 
令第二項之 $n$ 改為 $n'=N-1-n$ ，則兩式可合併為

$$
X(m)=\sum _{n=0}^{N-1}y(n)\cos {[{\frac {(4n+1)m\pi }{2N}}]},\,\,\,\,\,\,m=0,1,...,N-1
$$

 
右側為對 $y(n)$ 之 N 點的 scaled DFT

 
因此， $X(m)=Re[Z(m)]$ ，其中

$$
Z(m)=W_{4N}^{m}Y(m)=W_{4N}^{m}\sum _{n=0}^{N-1}y(n)W_{N}^{nm},\,\,\,\,\,\,\,m=0,1,...,N-1
$$

 
其中 $Y(m)$ 是對 $y(n)$ 之 N 點的 DFT，並且可以簡單的驗證 $Z(m)$ 具有如下性質

$$
Z(N-m)=-jZ(m)^{*}
$$

 
而因 $y(n)$ 為實數輸入，

 
因此欲求之 $X(m)=Re[Z(m)]$ ， $X(N-m)=-Im[Z(m)],\,\,\,\,\,\,\,m=0,1,...,{\frac {N}{2}}$

 
在使用 FFT 快速演算法的情況下，運算之時間複雜度同樣為 $O(NlogN)$

但此方法較方法一直接運算 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 （頁面存檔備份，存於網際網路檔案館）

## 外部連結

* 離散餘弦變換 （頁面存檔備份，存於網際網路檔案館）