跳轉到

5.2 DCT離散餘弦轉換#

概念說明#

離散餘弦轉換 (Discrete Cosine Transform, DCT) 用餘弦函數取代傅立葉的複指數：

F(u, v) = (1/4)·C(u)·C(v) · Σₓ Σᵧ f(x,y) · cos((2x+1)uπ/16) · cos((2y+1)vπ/16)

其中 C(0) = 1/√2，其餘 C(k) = 1。輸出全是實數，不需處理複數與相位。DCT 有多種形式，影像壓縮用的是 DCT-II（8×8 區塊版本）。

DCT 最重要的性質是能量集中 (energy compaction)：對高度相關的訊號（影像正是如此——相鄰像素通常相近），大部分能量集中在少數低頻係數上。原因在於 DCT 的基底函數近似於「偶對稱的傅立葉基底」：影像邊界不必像 DFT 那樣被強迫週期延拓（那會在邊界製造不連續、把能量灑到高頻），而是鏡射延拓，連續性好，高頻係數自然小。

這個性質正是壓縮的鑰匙：如果 64 個係數裡大部分接近 0，就只需儲存少數幾個大係數。JPEG 的流程（詳見 6.2 節）把影像切成 8×8 區塊、逐塊 DCT、用量化矩陣除掉人眼不敏感的高頻、再熵編碼。DCT 也是 MPEG/H.264/H.265 與 AAC 音訊的核心，是當代數位媒體的事實基礎。

8×8 區塊的 64 個係數有明確的視覺意義：F(0,0) 是區塊平均（DC），F(1,0) 是水平方向的緩慢漸層，F(7,7) 是最細的棋盤狀紋理。量化矩陣的設計就建立在此：人眼對低頻誤差敏感、對高頻誤差遲鈍，所以高頻可以「除以更大的數」，多數變成 0 而被丟棄。

演算法步驟（以 8×8 區塊為例）#

  1. 影像切成互不重疊的 8×8 區塊（像素值先減 128 置中）。
  2. 每區塊做 2D DCT：得 64 個係數。
  3. （壓縮情境）係數除以量化矩陣並四捨五入 → 大量高頻歸零。
  4. （還原）反量化、做 2D 逆 DCT、加回 128。
  5. 重組所有區塊為影像。

Python 程式碼範例#

import numpy as np
from PIL import Image

N = 8
# 建立 DCT 基底矩陣（可分離：2D DCT = T @ block @ T.T）
k = np.arange(N)
D = np.cos((2*k[None, :]+1) * k[:, None] * np.pi / (2*N))
D[0] /= np.sqrt(2)          # 正規化
D *= np.sqrt(2/N)
print("DCT 基底是正交矩陣:", np.allclose(D @ D.T, np.eye(N)))

# 一個平緩漸層區塊 vs 一個雜訊區塊
smooth = np.add.outer(np.arange(8), np.arange(8)) * 8 + 50
noise = np.random.default_rng(7).integers(0, 256, (8, 8)).astype(float)

for name, B in [("平緩區塊", smooth), ("雜訊區塊", noise)]:
    C = D @ (B - 128) @ D.T
    energy = C**2
    print(f"{name}: DC 佔總能量 {100*energy[0,0]/energy.sum():.1f}%"
          f", 最大的 6 個係數佔 {100*np.sort(energy.ravel())[-6:].sum()/energy.sum():.1f}%")

# 模擬 JPEG 式量化：保留左上角 r 個低頻，其餘歸零
Q = np.ones((8, 8)) * np.arange(1, 65).reshape(8, 8) * 4   # 高頻量化更粗
img = (np.random.default_rng(8).normal(128, 40, (64, 64))).clip(0, 255).astype(np.uint8)
recon = np.zeros_like(img, dtype=float)
for y in range(0, 64, 8):
    for x in range(0, 64, 8):
        B = img[y:y+8, x:x+8].astype(float) - 128
        C = D @ B @ D.T
        Qc = np.round(C / Q)               # 量化
        R = D.T @ (Qc * Q) @ D             # 逆 DCT
        recon[y:y+8, x:x+8] = R + 128
err = np.abs(recon - img)
print("量化後平均誤差:", err.mean().round(2), " 最大誤差:", err.max())
nz = sum((np.round(D @ (img[y:y+8,x:x+8].astype(float)-128) @ D.T / Q) != 0).sum()
         for y in range(0,64,8) for x in range(0,64,8))
print("非零係數比例:", round(nz / (64*64), 3), "（未壓縮為 1.0）")

執行後：平緩區塊的 DC 係數就佔九成以上能量，雜訊區塊的能量則分散——這正說明 DCT 適合「自然影像」而非隨機雜訊；量化後非零係數比例大幅下降而誤差仍小，預演了 JPEG 的壓縮邏輯。

複雜度分析#

直接 2D DCT：O(N⁴) 對 N×N 區塊。利用可分離性（先列後行）：O(2·N³)。再利用 DCT 的蝶形結構（FFT 型快速演算法）：O(N log N) 每一維，二維 O(N² log N)。對 8×8 區塊常數極小，硬體甚至用查找表直接算。對整張 H×W 影像逐區塊處理：O(H·W·log 8) = O(H·W)。空間 O(H·W)。與 FFT 的比較：DCT 只輸出實數、邊界行為好、無相位問題，是壓縮應用的首選；傅立葉則在濾波與頻譜分析上更通用。

練習#

  1. 對 8×8 的純水平條紋區塊做 DCT，列出係數矩陣，說明為何能量集中在第一行。
  2. 改變量化強度（把 Q 乘 2、4、8），畫出「非零係數比例 vs 平均誤差」的曲線，找出你認為的最佳工作點。
  3. JPEG 在高壓縮時 8×8 區塊邊界會出現「方塊效應」。用程式把一張漸層影像壓縮再還原，計算跨區塊邊界的梯度與區塊內梯度的比值來量化它。