跳轉到

6.1 無損壓縮與PNG原理#

概念說明#

無損壓縮 (lossless compression)：解壓結果與原圖逐位元相同。法律文件、醫學影像、程式截圖都必須用無損。核心思想只有一個：去除冗餘。

RLE (Run-Length Encoding, 游程編碼) 是最直觀的：連續重複的值記成「值 × 次數」。如 AAAAABBB → A×5, B×3。對大面積純色（卡通、掃描文件）極有效，對雜訊影像反而可能膨脹。

Huffman 編碼 (1952) 攻擊編碼冗餘：等長編碼（8-bit 一個灰階值）對「出現機率不均」的資料很浪費。Huffman 用貪婪法建立二元樹，高頻符號給短碼、低頻符號給長碼，且任何碼都不是另一碼的前綴 (prefix-free)，因此可即時解碼。可以證明 Huffman 是最優的前綴碼，平均碼長逼近資訊熵 H = −Σ p·log₂p。

PNG 的實際流水線：

  1. 過濾 (filtering)——攻擊空間冗餘。對每列像素先做預測：用左鄰 (Sub)、上鄰 (Up)、左上 (Average) 或 Paeth 預測器估計當前像素，只儲存預測誤差。自然影像相鄰像素相近，誤差值集中在 0 附近，後續壓縮效率大增。
  2. LZ77 (DEFLATE)——攻擊重複模式。用滑動視窗把重複的位元組序列替換成「(向後距離, 長度)」的參照。GZIP、ZIP 同源。
  3. Huffman——對 LZ77 的符號再壓一次。

DEFLATE = LZ77 + Huffman，這個組合是無損壓縮的黃金標準。關鍵洞察：先預測（轉換）再編碼——預測誤差的分布比原始像素尖銳得多，熵變小，Huffman/LZ77 的收益隨之放大。

何時無損效果差：真實照片的雜訊讓預測誤差分布變寬、變平，熵接近 8 bit/像素，無損壓縮率通常只有 1.5~3 倍；要 10 倍以上就得走向有損（6.2 節）。

演算法步驟（迷你 PNG：Sub 過濾 + Huffman）#

  1. 對每列做 Sub 過濾：e[x] = p[x] − p[x−1]（首元素不減）。
  2. 統計誤差值的直方圖。
  3. 建立 Huffman 樹：反覆合併機率最小的兩節點。
  4. 依樹產生前綴碼表。
  5. 用碼表把誤差序列編成位元流。
  6. 解碼走反向流程：讀位元流查樹 → 還原誤差 → 加回左鄰。

Python 程式碼範例#

import numpy as np
from collections import Counter, namedtuple
import heapq

rng = np.random.default_rng(10)
img = np.tile(np.linspace(30, 220, 64), (64, 1)) + rng.normal(0, 2, (64, 64))
img = img.clip(0, 255).astype(np.uint8)
raw_bits = img.size * 8
print("原始位元數:", raw_bits)

# Sub 過濾
err = img.astype(np.int16)
err[:, 1:] -= img[:, :-1].astype(np.int16)
err = err.astype(np.int8)
freq = Counter(err.ravel().tolist())
print("誤差值種類:", len(freq), " 最常見:", freq.most_common(3))

# Huffman 建樹
Node = namedtuple("Node", ["freq", "sym", "left", "right"])
heap = [Node(f, s, None, None) for s, f in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
    a, b = heapq.heappop(heap), heapq.heappop(heap)
    heapq.heappush(heap, Node(a.freq + b.freq, None, a, b))
codes = {}
def walk(n, code=""):
    if n.sym is not None:
        codes[n.sym] = code or "0"
        return
    walk(n.left, code + "0"); walk(n.right, code + "1")
walk(heap[0])

avg_len = sum(freq[s] * len(codes[s]) for s in freq) / err.size
print("平均碼長:", round(avg_len, 2), "bit/像素（原 8 bit）")
comp_bits = sum(freq[s] * len(codes[s]) for s in freq)
print("壓縮率:", round(raw_bits / comp_bits, 2), ": 1")

# 解碼驗證（用碼表反向查）
inv = {v: k for k, v in codes.items()}
stream = "".join(codes[v] for v in err.ravel().tolist())
out, i = [], 0
while i < len(stream):
    for L in range(1, 9):
        if stream[i:i+L] in inv:
            out.append(inv[stream[i:i+L]]); i += L; break
dec = np.array(out, dtype=np.int16).reshape(img.shape).astype(np.int16)
dec[:, 1:] += img[:, :-1].astype(np.int16)
print("解碼後與原圖相同:", np.array_equal(dec.astype(np.uint8), img))

執行後：平緩影像的預測誤差集中在 −6~+6，種類不到 20 個，Huffman 平均碼長約 3 bit，壓縮率超過 2.5 倍，且解碼結果與原圖完全相同——無損的承諾兌現。

複雜度分析#

Sub 過濾 O(N)。統計 O(N)。Huffman 建樹：k 種符號時 O(k log k)，k ≤ 256 故 O(1)。編碼 O(N·L)（L 平均碼長）或用查表 O(N)。解碼逐位元走樹 O(總位元數)，用表格解碼可 O(N)。總計 O(N)。空間 O(N)。LZ77 的滑動視窗匹配是主要成本，DEFLATE 實作用雜湊鏈加速，實務上 zlib 對 1 MB 影像不到 50 ms。理論上限是資訊熵：若符號分布均勻（雜訊），任何無損方法都救不了——這是山農定理的硬牆。

練習#

  1. 對「隨機雜訊影像」與「純色塊影像」各跑本節流程，比較壓縮率，驗證「熵決定上限」。
  2. 實作 Up 過濾（用上鄰預測）與 Paeth 預測器，對漸層影像比較三種過濾器的誤差熵，哪個最小？
  3. 用 3 個符號 {A:0.5, B:0.3, C:0.2} 手算 Huffman 碼長，與理論熵比較，並計算固定 2-bit 編碼浪費多少。