離散餘弦轉換

File:Disambig gray.svg關於同樣縮寫為DCT的一種汽車變速箱，請見「雙離合變速箱」。

File:Dandelion clock quarter dft dct.png

2d DCT（type II） 與離散傅立葉轉換的比較.

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

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

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

應用

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

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

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

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

常見應用

• 音頻信號處理 — 音訊編碼、音訊資料壓縮（有損和無損）、環繞聲、回音消除、音位辨識、時域混疊消除法（TDAC）
  • 數位音訊
  • 數位廣播 — 數位聲音廣播（DAB+）
  • 語音處理 — 語音編碼、語音辨識、語音活性檢測（VAD）
  • 數位電話 — VoIP、流動電話、視訊通話
• 生物辨識技術 — 指紋定向、臉部辨識系統、生物辨識浮水印、掌紋辨識
  • 人臉檢測

形式化定義

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

DCT-I

<math>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} m k \right]</math>

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

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

所以，DCT-I暗示的邊界條件是：<math>x_k</math>相對於<math>k=0</math>點偶對稱，並且相對於<math>k=n-1</math>點偶對稱； 對<math>f_m</math>的情況也類似。

DCT-II

<math>f_m =

  \sum_{k=0}^{n-1} x_k \cos \left[\frac{\pi}{n} m \left(k+\frac{1}{2}\right) \right]</math>

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

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

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

DCT-III

<math>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]</math>

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

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

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

DCT-IV

<math>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]</math>

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

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

DCT-IV暗示的邊界條件是：<math>x_k</math>相對於<math>k=-\frac{1}{2}</math>點偶對稱，並且相對於<math>k=n-\frac{1}{2}</math>點奇對稱；對<math>f_m</math>類似。

DCT V~VIII

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

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

反轉換

DCT-I的反轉換是把DCT-I乘以係數<math>\frac{2}{n-1}</math>。 DCT-IV的反轉換是把DCT-IV乘以係數<math>\frac{2}{n}</math>。 DCT-II的反轉換是把DCT-III乘以係數<math>\frac{2}{n}</math>，反之亦然。

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

計算

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

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

方法一

令輸入信號為<math> x(n) \, , n=0,1,...,N-1</math>

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

即<math> 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.</math>

此時令<math>W_{2N}</math> 表示 <math>e^{\frac{-j2\pi}{2N}}</math>

則<math>y(n)</math>之DFT為

<math>Y(m) = \Sigma_{n=0}^{2N-1}y(n)W_{2N}^{nm}</math>

將<math>Y(m)</math> 做以下化簡

<math>\begin{align} 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{align}</math>

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

可得<math> \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 </math>

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

方法二

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

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

此時X(m)可化簡為

<math> 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</math>

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

<math>X(m)=\sum_{n=0}^{N-1}y(n)\cos{[\frac{(4n+1)m\pi}{2N}]}, \,\,\,\,\,\, m=0,1,...,N-1</math>

右側為對<math>y(n)</math>之N點的scaled DFT

因此，<math>X(m)=Re[Z(m)]</math>，其中

<math>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</math>

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

<math>Z(N-m)=-jZ(m)^{*}</math>

而因<math> y(n) </math> 為實數輸入，

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

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

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

外部連結

• 離散餘弦轉換 （頁面存檔備份，存於互聯網檔案館）