離散餘弦變換

離散傅里葉變換需要進行復數運算，儘管有FFT可以提高運算速度，但在圖像編碼、特別是在實時處理中非常不便。離散傅里葉變換在實際的圖像通信系統中很少使用，但它具有理論的指導意義。根據離散傅里葉變換的性質，實偶函數的傅里葉變換隻含實的餘弦項，因此構造了一種實數域的變換——離散餘弦變換(DCT)。通過研究發現，DCT除了具有一般的正交變換性質外，其變換陣的基向量很近似於Toeplitz矩陣的特徵向量，後者體現了人類的語言、圖像信號的相關特性。因此，在對語音、圖像信號變換的確定的變換矩陣正交變換中，DCT變換被認為是一種準最佳變換。在近年頒佈的一系列視頻壓縮編碼的國際標準建議中，都把 DCT 作為其中的一個基本處理模塊。

DCT除了上述介紹的幾條特點，即：實數變換、確定的變換矩陣、準最佳變換性能外，二維DCT還是一種可分離的變換，可以用兩次一維變換得到二維變換結果。

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

有兩個相關的變換，一個是離散正弦變換(DST for Discrete Sine Transform),它相當於一個長度大概是它兩倍的實奇函數的離散傅里葉變換；另一個是改進的離散餘弦變換(MDCT for Modified Discrete Cosine Transform),它相當於對交疊的數據進行離散餘弦變換。

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

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

一個類似的變換, 改進的離散餘弦變換被用在高級音頻編碼(AAC for Advanced Audio Coding)，Vorbis 和 MP3 音頻壓縮當中。

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

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

改進的離散餘弦變換（Modified Discrete Cosine Transform, MDCT）是一種與傅立葉變換相關的變換，以第四型離散餘弦變換（DCT-IV）為基礎，重疊性質如下：它是應用於處理較大的資料集合，當連續的資料區塊中，當前的資料區塊跟後續的資料區塊有重疊到的情形；即當前資料區塊的後半段與下一個資料區塊的前半段為重疊的狀態。這樣的重疊情形，除了具有離散餘弦變換（Discrete Cosine Transform, DCT）的能量壓縮特性外，也使這種變換在應用於信號壓縮時更引人注目。因為它有助於避免由於資料區塊邊界所產生的多餘資料。因此，這種變換可應用於MP3，AC-3， ogg vorbis，和AAC的音頻壓縮等方面。

改進的離散餘弦變換是由Princen，Johnson和Bradley承接早前（1986年）Princen和Bradley所提出關於時域混疊消除法（Time-Domain Aliasing Cancellation, TDAC ）的改進的離散餘弦變換基本定理，於1987年所提出，詳述如下。至於其他類似的變換還有如以離散正弦變換為基礎的改進的離散正弦變換（Modified Discrete Sine Transform, MDST）。以及其他較少使用的變換，例如以其他不同類型的DCT或DCT/DST的組合為基礎的改進的離散餘弦變換。

在MP3的應用上，改進的離散餘弦變換，並不適用於直接處理音頻信號，而適用於處理32波段多相正交濾波器（Polyphase quadrature filter, PQF）陣列的輸出端信號。這樣的改進的離散餘弦變換輸出是由一個混疊削減公式作後置處理，用以減少多相正交濾波器陣列的特殊混疊。這樣的改進的離散餘弦變換與濾波器陣列組合，被稱作混合濾波器陣列或子帶改進的離散餘弦變換 。相反地，AAC通常使用一個純粹的改進的離散餘弦變換；僅Sony公司使用的MPEG – 4 AAC - SSR技術採用了運用改進的離散餘弦變換的四波段多相正交濾波器陣列（但也是很少使用）。自適應聽覺變換編碼（Adaptive Transform Acoustic Coding, ATRAC）利用運用改進的離散餘弦變換的堆疊型正交鏡像濾波器（Quadrature Mirror Filter, QMF）。

改進離散餘弦變換(Modified Discrete Cosine Transform )，簡稱MDCT，是一種線性正交交疊變換。它使用了一種時域混疊抵消技術(TDAC)，包含50%的時域交疊窗，在不降低編碼性能的情況下有效地克服加窗離散餘弦變換(DCT)塊處理運算中的邊緣效應，從而有效地去除由邊緣效應產生的週期化噪聲，在相同編碼率的情況下，MDCT性能優於DCT，廣泛應用於語音、寬帶音頻和圖像信號的變換編碼中。MDCT本身計算量龐大，對於實時編解碼系統，直接計算複雜度很難接受，其快速算法一類是基於FFT，另一類是基於DCT。 ^[2]