快速傅立葉轉換與譜方法

離散餘弦轉換(discrete cosine transform)

每次你檢視一張 JPEG 照片、串流一段影片、或聽一首 MP3,背後扛重活的都是離散餘弦轉換。它是 DFT 的近親,只用實數的餘弦波而非複數指數,而且對壓縮有一個神奇性質:對自然影像與音訊常見的平滑、緩慢變化的資料,它幾乎把所有重要資訊塞進少數幾個低頻係數,其餘趨近於零、可安全捨棄。

DCT 把一塊樣本表示成頻率遞增的餘弦波之和。長度為 N 的訊號 x 的常見形式(DCT-II)是 C_k = 對 n 從 0 到 N-1 求和 x_n * cos(pi * k * (n + 0.5) / N),給出 N 個實數係數:C_0 正比於平均值,較高的 C_k 捕捉越來越精細的擺動。它在壓縮上勝過 DFT 的原因微妙卻重要。DFT 假設你的塊週期性重複,這通常在接縫處製造跳變(洩漏)並把能量散到許多格點上。DCT 則隱含地在塊的邊緣作鏡像反射再重複,使延拓的訊號連續——沒有人為跳變——能量便集中在最低的少數幾個係數上。這種「能量壓縮」正是讓壓縮奏效的關鍵,而且如同 FFT,DCT 也有 O(N log N) 的快速演算法。

在 JPEG 中,影像被切成 8x8 像素的塊,每塊跑一次 2D DCT,所得的 64 個係數被量化(高頻者粗略量化,因為眼睛幾乎察覺不到),趨近於零的係數被丟棄、其餘壓縮。解壓縮以反 DCT 反向進行各步驟。這是「有損」的:資訊確實被捨棄,誠實承認這點很重要——量化推得太狠,你就會看到過度壓縮 JPEG 那洩漏天機的 8x8 方塊狀瑕疵。DCT 的親戚——離散正弦轉換與各種邊界變體——在不同邊界條件的譜方法 PDE 求解器中扮演相同角色。

取一列 8 像素,由暗平滑漸亮。它的 DCT 幾乎把所有能量放進 C_0(平均值)與 C_1(單一緩坡),而 C_2 到 C_7 基本上為零。只保留前兩個係數、其餘設為零,反 DCT 便幾乎完美地重現該列——六個數字只存兩個。

平滑資料壓縮成少數幾個低頻餘弦——這是 JPEG 的核心。

JPEG 與 MP3 是「有損」的:DCT 本身可逆,但其後的量化步驟刻意捨棄資訊、無法復原。過度激進的量化會產生熟悉的 8x8 方塊瑕疵。

又稱
DCTDCT-II離散餘弦變換DCT