JPEG 圧縮の裏にある秘密 — 離散余弦変換

（本記事は2023 iThome 鉄人賽に由来する）

誰もが耳にする JPG の裏側には、学ぶ価値のある圧縮技術が数多くある。先人たちがさまざまな賢い Engineering の手法で画像を圧縮してきたのを見ると、この時代に生きていられるのは本当に素晴らしいと思う。

JPEG

JPEG は厳密に言えばファイル形式ではなく、アルゴリズムの一種である。ファイルの形式は JFIF（JPEG File Interchange Format）によって規定されている。

YCbCr

まずは JPEG の色の保存方式から見ていく。一般的には光の三原色である R、G、B を使ってさまざまな色を表すが、科学者たちは、人間は色の変化よりも明るさの変化にずっと敏感だと発見した。

この人間の生来の特性をうまく利用するために、できるだけ色情報を減らし、明るさの変化を多く使って表現したい。画像処理では色を表すのに YCbCr がよく用いられる。

その内訳は以下の通りだ。

• Y は輝度（Luminance）
• Cr は赤色差チャンネル（Chrominance Red）
• Cb は青色差チャンネル（Chrominance Blue）

では G はどこへ行ったのか。答えは、捨てられたのである。しかし、一部の情報が失われても、人間の目は色の変化にあまり敏感ではないため、多少の情報が欠けても目立った変化にはなりにくい。

RGB から YCbCr への変換式は次の通りだ。

$$Y = 0.299R + 0.587G + 0.114B$$ $$Cb = -0.169R - 0.331G + 0.500B$$ $$Cr = 0.500R - 0.419G - 0.081B$$

離散余弦変換（DCT）

JPEG に画像を神秘的に圧縮できるアルゴリズムがあるとすれば、その背後で最も重要な働きをしているのが離散余弦変換（Discrete Cosine Transform）である。

画像中の高周波と低周波

離散余弦変換を簡略化して理解しやすくするために、まず 1D 配列を例にする。画像を信号として見なし、画素のグレースケール値を y 軸の高さとすると、各行の画素をひとつの信号として捉えられる。

画像を信号として見ることに何の利点があるのか。他の信号と同じように、周波数領域解析ができるからだ。線形変換を通すことで、低周波や高周波の成分を見つけられる。

変換後の信号は、次のように解釈できる。

cos の各周波数が画像の中でそれぞれどれくらいの割合を占めているか

あるいは、「どんな画像でも、さまざまな周波数の余弦波の合成として表せる」と考えてもよい。人間にとって重要なのは低周波なので、元の信号の高周波係数を下げたり、0 にしてしまっても、元画像にはそれほど大きな影響を与えない。

0 にできるなら、その分の空間はもう不要だ。これこそが JPEG 圧縮の核心概念である。

2D 離散余弦変換

2D の離散余弦変換の式はより複雑だが、根本原理は同じである。画像はまず 8×8 の小さなブロックに分割され、DCT 係数へ変換される。

2D DCT の式は次の通りだ。

$$F(u,v) = \frac{1}{4} C(u) C(v) \sum_{x=0}^{7} \sum_{y=0}^{7} f(x,y) \cos\frac{(2x+1)u\pi}{16} \cos\frac{(2y+1)v\pi}{16}$$

ここで、$C(k) = \frac{1}{\sqrt{2}}$ は $k = 0$ のとき、それ以外では $C(k) = 1$ である。

式だけ見るとかなり恐ろしく見えるが、要するに「この 8×8 のブロックは、どの基底パターンにどれだけ似ているか」を問うている。

DCT 係数 F(u,v) は、元画像とこの基底パターンの内積（dot product）を取ったものだ。つまり「この画像はこの模様にどれくらい似ているのか」であり、似ている度合いが高いほど係数は大きくなり、重みも高くなる。

インタラクティブ：DCT 可視化

下のインタラクティブツールには、64 個の DCT 基底パターンの可視化が含まれている。各 (u, v) は 1 つの周波数の組み合わせに対応する。左上の (0,0) は DC 成分（平均輝度）で、右下に行くほど周波数は高くなる。

圧縮時にどの基底パターンが保持されるか（明るい）、あるいは捨てられるか（暗い）を見ることができ、数字は zig-zag スキャンの順序を表す。

画像をアップロードすると、DCT 変換の結果や、さまざまな圧縮率で再構成した画像を実際に確認できる。

量子化表（Quantization Table）

DCT 係数行列をそのまま保存するなら、元画像はまったく圧縮されない。

実務では、DCT 係数を量子化表の値で割り、最も近い整数に丸める。この過程で新しい DCT 係数行列が得られ、大部分の高周波係数は量子化によって 0 になる。JPG アルゴリズムでは画像を複数の 8×8 ブロックに分割し、それらのブロックごとに DCT を計算する。

圧縮率を選ぶ際には、量子化表の係数も変わる。圧縮しない場合、量子化表の各要素はすべて 1 になる（画像の各画素をそのまま保持する）。

Zig-zag 走査

DCT 係数行列を量子化表で割ると、高周波部分の要素の大半は 0 になる。行列の左上は低周波、右下に行くほど高周波である。低周波の値を前に持ってくるため、画像ファイルの圧縮時には zig-zag 方式で行列を走査する。

例えば、量子化後の行列が次のような場合、

4 5 1 0
1 3 0 0
6 0 0 0
0 0 0 0

実際の符号化では次のようになる。

[4, 5, 1, 1, 3, 6, 9, 5, 0, 0, 0, 0, 0, 0, 0, 0]

その後ろに続く連続した 0 は、高効率に圧縮できる。

ハフマン符号化（Huffman Coding）

ハフマン符号化は損失のないデータ圧縮アルゴリズムであり、データを非常に効率よく符号化できる。JPG の符号化では、要素の大部分が 0 になるため、ハフマン符号化によって出現頻度の高い記号には短い符号を、頻度の低い記号には長い符号を割り当てられる。JPG では、DCT 行列が量子化と zig-zag 走査を経たあと、さらにハフマン符号化されて保存される。

実際に JPEG をデコードする

JPEG のデコードは、基本的に上の手順を逆順にたどるだけだ。

1. ファイル中のハフマン符号化表を取り出し、データをデコードする
2. zig-zag 配列を 8×8 行列に戻す
3. DCT 係数に量子化表を掛け、近似的な DCT 係数を得る
4. 逆 DCT（IDCT）を計算し、画素値を復元する
5. YCbCr を RGB に変換する

JPG ファイルには多くの区画があり、それらは 0xff のマーカーによって識別される。

• 0xffd8 — JPG のファイル先頭マーカー（SOI）
• 0xffc0 — Start of Frame、画像の幅や高さなどの情報を含む
• 0xffc4 — ハフマン符号化表（DHT）
• 0xffdb — 量子化表（DQT）
• 0xffda — Start of Scan、実際の画像データ
• 0xffd9 — JPG のファイル末尾マーカー（EOI）

以下は JPG marker を解析する簡易 JavaScript 実装だ。

function parseJPG(data) {
  const hfTables = {}
  const quantizationTables = {}
  let quantMapping
  let d = new Uint8Array(data)
  let w, h

  while (d.length > 0) {
    const marker = d.slice(0, 2)

    if (marker[0] === 0xff && marker[1] === 0xd8) {
      d = d.slice(2) // SOI
      continue
    }

    if (marker[0] === 0xff && marker[1] === 0xd9) {
      break // EOI
    }

    const len = (d[2] << 8) + d[3] + 2
    const chunk = d.slice(4, len)

    switch (marker[1]) {
      case 0xc4: { // DHT
        const { table, header } = decodeHuffman(chunk)
        hfTables[header] = table
        break
      }
      case 0xdb: { // DQT
        const { header, table } = buildQuantizationTables(chunk)
        quantizationTables[header] = table
        break
      }
      case 0xc0: { // SOF
        const { result, width, height } = baseDCT(chunk)
        quantMapping = result
        w = width
        h = height
        break
      }
      case 0xda: { // SOS
        startOfScan({ data: d, hdrlen: len, width: w, height: h,
          quantizationTables, quantMapping, hfTables })
        break
      }
    }

    d = d.slice(len)
  }
}

後記

実際の応用では、GPU や CPU に画像の符号化・復号化用の回路があるため、通常は別途プログラムを書く必要はない。しかし JPG の裏側にあるアルゴリズムは、離散余弦変換、ハフマン符号化、zig-zag 走査を組み合わせることで、画像の保存容量を見事に減らしている。

僕は、普段は当然だと思っていることを深く掘り下げると、多くの学ぶべき知識が隠れている、こういうものが好きだ。JPEG 圧縮のおかげで、僕たちは毎日インターネット上で何億もの画像を送信できている。そしてそのすべての背後には、数学、情報理論、そして人間の視覚特性の完璧な結びつきがある。