JPEG圧縮の裏に隠された秘密 — 離散コサイン変換

（この記事は2023 iThome 鐵人賽に由来する）

誰もがよく知るJPGの裏には、学ぶべき多くの圧縮技術が存在する。先人たちがさまざまな巧妙なエンジニアリング手法を駆使して画像を圧縮した成果を見ると、この時代に生きられて本当によかったと実感する。

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, DCT）である。

画像における高周波と低周波

理解しやすくするために、まずは1次元配列を例として考えてみよう。画像を1つの信号と見なし、ピクセルのグレースケール値をy軸の高さとすると、1行分のピクセルをひと続きの信号と見なすことができる。

画像を信号として見なすことのメリットは何だろうか？他の信号と同じように、周波数領域の解析（周波数分解）を行えるようになる点だ。線形変換を通すことで、低周波成分や高周波成分を特定できるようになる。

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

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

あるいは、「どんな画像も異なる周波数のコサイン波の重ね合わせとして表現できる」と考えてもよい。人間にとって画像を構成する本質的な情報は低周波成分であり、元信号の高周波成分の係数を下げたり、極端な話0にしてしまったりしても、元の画像にはそれほど大きな影響を与えない。

0にできるのであれば、余分なスペースを消費しなくて済む。これこそがJPEG圧縮の核となるアイデアだ。

2次元離散コサイン変換

2次元の離散コサイン変換の数式はやや複雑だが、根本的な原理は同じである。画像はまず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成分（平均輝度）であり、右下に進むほど周波数が高くなる。

どの基底パターンが圧縮時に保持されるか（明るい部分）、あるいは破棄されるか（暗い部分）が確認できる。数字はジグザグスキャンの順序を示している。

画像をアップロードすると、DCT変換の結果や、異なる圧縮レベルで再構築された画像を実際に確認できる。

量子化テーブル（Quantization Table）

DCT係数行列をそのまま保存しただけでは、元の画像は一切圧縮されていない。

実際には、DCT係数を量子化テーブルの値で割り、最も近い整数へと四捨五入する。このプロセスによって新しいDCT係数行列が得られ、高周波成分の係数の多くは量子化によってゼロになる。JPGのアルゴリズムは画像を複数の8×8のブロックに分割し、それぞれのブロックに対してDCTを計算する。

圧縮率の設定によって、量子化テーブル内の係数も変化する。もし圧縮を行わないのであれば、量子化テーブル内の要素はすべて1になる（画像の全ピクセル情報が保持される）。

ジグザグ走査（Zig-zag Scan）

DCT係数行列を量子化テーブルで割った後、高周波部分の要素はほとんどが0になる。行列の左上は低周波であり、右下へ進むほど高周波になる。低周波の数値を前方に集めるため、画像ファイルを圧縮する際は行列をジグザグ順に走査する。

例えば、量子化後の行列が以下のようだったとする：

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]

後ろに連続するゼロは、極めて効率的に圧縮できる。

ハフマン符号化（Huffman Coding）

ハフマン符号化は可逆データ圧縮アルゴリズムの一種であり、データを非常に効率よくエンコードできる。JPGのエンコード時、データの大部分は0になる。ハフマン符号化は出現頻度の高い記号に短いコードを割り当て、出現頻度の低い記号には長いコードを割り当てる。JPGでは、DCT行列が量子化とジグザグ走査を経た後、さらにハフマン符号化されて保存される。

JPEGの実際のデコード処理

JPEGをデコードする手順は、基本的に上述のステップを逆順に実行することだ：

1. ファイル内のハフマン符号化テーブルを取り出し、データをデコードする
2. ジグザグの配列を8×8の行列に復元する
3. DCT係数に量子化テーブルを掛け合わせ、近似されたDCT係数を得る
4. 逆離散コサイン変換（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マーカーを解析するシンプルな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の背後にあるアルゴリズムは、離散コサイン変換、ハフマン符号化、ジグザグ走査を組み合わせることで、画像の保存容量を見事に削減している。

普段当たり前のように使っている技術を深く掘り下げ、そこに秘められた多くの知恵を学ぶプロセスが、僕はとても好きだ。JPEG圧縮のおかげで、僕たちは毎日インターネット上で何億枚もの画像を送受信できている。そしてその裏側には、数学、情報理論、人間の視覚特性の完璧な融合が存在しているのだ。