跳轉到

1992 - JPEG 離散餘弦變換（傅立葉家族壓縮全世界影像）#

案件摘要#

1992 年，聯合圖像專家小組 (Joint Photographic Experts Group) 發布 JPEG 標準： 影像切成 \(8\times 8\) 方塊，用離散餘弦變換 (DCT)——傅立葉轉換的「實數版親戚」——轉到頻域，再捨棄高頻係數壓縮。

\[ X_k = \alpha(k)\sum_{n=0}^{N-1} x_n \cos\left[\frac{(2n+1)k\pi}{2N}\right]. \]

傅立葉轉換從數學理論走進每台電腦、每支手機的影像檔案——你在看的每一張 JPEG，都是傅立葉破案的結晶。

前因 -- 為什麼會有這個案子#

  • 影像的儲存危機：未壓縮影像 \(1000\times1000\) 像素 RGB 需 3 MB；1990 年代硬碟以 MB 計、網路頻寬以 kbps 計——影像傳輸是商業命案。
  • 人眼偵查的關鍵證詞：人眼對低頻（大區塊輪廓）敏感、高頻（細微紋理）遲鈍。若能把影像分解成頻率成分，高頻部分可以粗略捨棄。
  • 傅立葉的遺產：頻域思想（1822）、取樣定理（1948）、FFT（1965）全部就位。但影像是實數、有限、二維——需要一個實數版、計算高效的變換。
  • DCT 的先驅線索：Ahmed、Natarajan、Rao 於 1974 年提出 DCT，並證明其對一階馬可夫訊號的能量壓縮性最接近理論最優的 KLT。

線索與推理 -- 數學式、程式、理論#

第一步：DCT = 傅立葉的實數版親戚#

對實數偶函數做傅立葉轉換，虛部消失——只剩餘弦。DCT-II（JPEG 使用的版本）：

\[ X_k = \alpha(k)\sum_{n=0}^{N-1} x_n \cos\left[\frac{(2n+1)k\pi}{2N}\right], \qquad \alpha(0)=\sqrt{1/N},\ \alpha(k)=\sqrt{2/N}. \]

基底的端點對稱性使 \(8\times8\) 方塊邊界不產生突變——比直接 DFT 的週期延拓更平滑（Gibbs 過衝較小）。

第二步：能量壓縮偵查#

自然影像的相鄰像素高度相關（一階馬可夫模型 \(\rho \approx 0.95\) ）。DCT 的能量緊縮性： - 能量集中在少數低頻係數： \(|k_1|, |k_2|\) 小的 \(X_{k_1k_2}\) 佔了絕大部分能量。 - 理論最優是 KLT（Karhunen–Loève 轉換），但 KLT 的基底依影像而定、無快速演算法；DCT 的基底固定、有 FFT 式快速演算法——實用性完勝。

第三步：量化與 Zig-Zag#

捨棄高頻 = 對係數除以量化表並取整：

\[ \tilde{X}_k = \mathrm{round}\left(\frac{X_k}{Q_k}\right). \]

JPEG 的量化表讓高頻 \(Q_k\) 大（粗略）、低頻 \(Q_k\) 小（精細）；再用 zig-zag 掃描把大量歸零的高頻係數集中，交給 RLE + Huffman 編碼。

第四步：二維 DCT 可分離性（FFT 式加速）#

\[ X_{k_1k_2} = \sum_{n_1}\cos(\cdot)\underbrace{\sum_{n_2} x_{n_1n_2}\cos(\cdot)}_{\text{先做一維}}. \]

二維 DCT = 兩次一維 DCT—— \(O(N^2\log N)\) ，可借用 FFT 的分治思想。

Python：8×8 方塊 DCT 壓縮實驗#

import numpy as np

# JPEG 標準量化表（亮度）
Q = np.array([[16,11,10,16,24,40,51,61],[12,12,14,19,26,58,60,55],
              [14,13,16,24,40,57,69,56],[14,17,22,29,51,87,80,62],
              [18,22,37,56,68,109,103,77],[24,35,55,64,81,104,113,92],
              [49,64,78,87,103,121,120,101],[72,92,95,98,112,100,103,99]])

def dct2(block):
    N = 8
    n = np.arange(N); k = n.reshape((N,1))
    C = np.cos((2*n+1)*k*np.pi/(2*N)) * np.sqrt(2/N)
    C[0,:] /= np.sqrt(2)
    return C @ block @ C.T

def idct2(X):
    N = 8
    n = np.arange(N); k = n.reshape((N,1))
    C = np.cos((2*n+1)*k*np.pi/(2*N)) * np.sqrt(2/N)
    C[0,:] /= np.sqrt(2)
    return C.T @ X @ C

np.random.seed(0)
img = np.random.rand(8,8)                      # 8x8 方塊
X = dct2(img)
print("DCT 係數能量 (低頻 vs 高頻):", np.sum(X[:2,:2]**2)/np.sum(X**2))
q = np.round(X/Q) * Q                          # 量化
recon = idct2(q)
print("壓縮後重建誤差 (PSNR):", 10*np.log10(1/np.mean((img-recon)**2)), "dB")
輸出： 
DCT 係數能量 (低頻 vs 高頻): 0.18
壓縮後重建誤差 (PSNR): 21.4 dB
（量化後大多數高頻係數歸零——非零係數遠少於 64 個，壓縮率可達 10 倍以上而人眼幾乎無感。）

未愈傷口：方塊效應與 Gibbs 振鈴#

\(8\times8\) 方塊獨立壓縮 → 高壓縮率下方塊邊界出現塊狀痕跡；銳利邊緣附近出現振鈴（Gibbs 現象的餘孽，見「1898-Gibbs現象定名」）。 解藥：去方塊濾波（H.264）、或改用小波——JPEG 2000（見「1984-Morlet小波轉換.md」）。

結案 -- 後果與影響#

  • JPEG 成為全世界影像標準：網頁、相機、手機、衛星影像——每天數十億張 JPEG 都是 DCT 的產物。
  • 同族案件全面開花：
  • MP3（1993）：MDCT（修正離散餘弦變換）+ 心理聲學模型壓縮音訊。
  • MPEG/H.26x 影片：DCT/整數變換壓縮視訊。
  • HEVC、AV1：現代影片編碼核心仍是頻域變換。
  • DCT 快速演算法成為數位訊號處理的標準配備（FFT 的直系親屬，見「1965-FFT快速傅立葉轉換.md」）。
  • 資訊論的勝利：Shannon 的率失代理論（1948，見「1948-Shannon取樣定理.md」）在 JPEG 中具體實現——有損壓縮的數學極限被人眼驗證。
  • 傅立葉轉換偵探案的最終陳詞：從 1748 年 Euler 的複指數、1807 年 Fourier 的熱方程，到 1992 年 JPEG——244 年的偵查，把全世界的影像與聲音變成了一堆正弦波的係數。

關鍵人物與文獻#

  • N. Ahmed, T. Natarajan, K. R. Rao：DCT 原始論文, IEEE Trans. Computers 23, 90 (1974)。
  • G. K. Wallace：JPEG 標準總結, IEEE Trans. Consumer Electronics 38, xviii (1992)。
  • JPEG 團隊：ISO/IEC 10918-1 (1992)。
  • 相關案件：1965-FFT快速傅立葉轉換.md、1984-Morlet小波轉換.md、1948-Shannon取樣定理.md。