データ圧縮の基礎(続き)

可逆圧縮の原理

JPEGコーデックは非可逆圧縮ですが、そのアルゴリズムには可逆圧縮を行う手続きが含まれています。実は あらゆる非可逆圧縮コーデックでは可逆圧縮アルゴリズムを利用する のです。まずは、全ての基本となる可逆圧縮の原理を理解しておきましょう。

説明用に単純化した、300×200ピクセル、3bpp、グレイスケール画像を考えます。3bppというのは耳慣れないかもしれませんが、その定義通り "1ピクセルを3ビットで表現" つまりピクセル値が 0～7 を取りうる8階調グレイスケール画像です。このデジタル画像を表現するには 300×200×3＝180000ビット が必要です。さて、このデジタル画像がもつ情報を全く損なわずに、もっと少ないビット量で表現することは可能でしょうか？

答えは：はい、可能です。デジタル画像がもつ データの統計的な偏りを利用すると、各ピクセル値はそのままに 情報を一切損なうこと無く、より少ないビット量で表現できる のです。これが可逆圧縮の原理です。この "より少ないビット量で表現" におけるビット量が、ピクセル値の集合というデジタル画像が持っている情報の量、つまり「エントロピー(entropy)」に対応します。¹

Let's ハフマン符号

騙されたように感じる方もいるでしょうから、具体的な数字で計算してみましょう²。先の3bppグレイスケール画像では、ピクセル値の度数分布データは下表の通りでした。表中 "ビット列" は各ピクセル値に対応する3ビット長のビットパターン、単に10進数ピクセル値から2進数へ変換したものです。

ではここで、魔法の（じゃないけど）対応表を取り出します。各ピクセルに対応するビット列が変化、つまりピクセル値0はビット列110000に、ピクセル値1はビット列1101にと対応させます。元々はビット長3で固定だったビット列が、新しい対応表ではビット長1～6の可変長となります。

この新しい対応表を使って、画像全体を表すのに必要となるビット量を求めます。ピクセル値0は6ビット必要で2個つまり6×2＝12ビット、ピクセル値1は4ビットが3744個つまり4×3744＝14976ビット、と計算していきます。最後に全ピクセル値0～7に対するビット量を合計すると 143602ビット です。³

変換前は画像全体で 180000ビット だったものが、ピクセル値とビット列の対応を変更した だけで 143602ビット へと縮みました。変換前後でのビット量比は 1:1.25 (1÷1.25=80%)、わずか20%ですがデータサイズ削減に成功しました。このとき、デジタル画像を構成するピクセル値は一切変化していませんから、この変換こそが可逆圧縮です！...納得できるまで読み返してくださいね。

ここで使った対応表は、JPEGコーデックでも利用する「ハフマン符号(Huffman coding)」によるものです⁴。ハフマン符号はエントロピー符号(entropy coding)の一種であり、前節で説明したエントロピーつまり "データの統計的な偏り" を利用した可逆圧縮アルゴリズムです。⁵

偏ったデータ Is Awesome

データ圧縮は魔法ではなく数学ですから、どんなデータでも可逆圧縮できるとは限りません。エントロピー符号（ハフマン符号）による可逆圧縮の本質は "データの統計的な偏り" にあります。定性的な説明では：

• データ値の分布が偏っているほどエントロピーは小さくなり、エントロピー符号化による大きなデータサイズ削減効果が見込めます。
• データ値の分布に偏りがない、つまりデータ値が均等に出現するときにエントロピーは最大となり、エントロピー符号化ではデータサイズを全く削減できません。

可逆圧縮では、どんなデータに対してもサイズ削減できるアルゴリズムというものは原理的に存在しません。データ圧縮処理に逆変換が存在するには、全ての入力値に対して何らかの出力値を1:1対応させる必要があります。Nビットの入力データは全部で $2 ^ N$ 通り存在しますから、1:1対応させる圧縮後データもまた $2 ^ N$ 通り存在するはずです。$2 ^ N$ 通りのデータを一意に表現するには少なくともNビット必要ですから、とりうる入力データ全体で考えると 入力ビット長 ＜ 圧縮後ビット長 となる入出力値の組が必ず存在します。見方をかえると、可逆圧縮アルゴリズムでは 入力ビット長 ＞ 圧縮後ビット長 が成り立つ範囲（$2 ^ N$ 通りよりもずっと候補数の少ないデータ集合）だけを取り扱っているのです。

次に、わざとらしいグラデーション画像とランダム･ドット画像を考えます。いずれもピクセル値度数分布が均一な200x200ピクセル, 3bppグレイスケール画像ですから、前節と同じハフマン符号を適用してもそのデータサイズは全く削減されません。右のランダム・ドット画像はともかく、左のグラデーション画像もデータ圧縮できないというのには違和感がありませんか？

予測と変換

先ほどはピクセル値そのもにをエントロピー符号を適用しましたが、一般的な画像コーデックではピクセル値 x に対して何らかの事前計算 y = Fwd(x) を行い、その計算結果 y に対してエントロピー符号を適用します。一連のデータ処理過程で可逆圧縮を実現するには、計算 Fwd() が可逆(reversible)、つまり対応する逆計算 Inv() によりピクセル値が完全に復元 x == Inv(Fwd(x)) されなければなりません。このような計算として、画像・音声コーデックでは下記方式が利用されます：⁶

• 予測符号化(predictive coding)：ほかのデータ値から対象データ値を予測する。実際のデータ値と予測値から、その "ずれ量" を出力する。最も単純な予測アルゴリズムは、直近データ値を予測値とし(pred = x[n-1])、実データ値(x[n])との差分値(y = x[n] - pred)を出力する。この計算は差分符号化(delta encoding)と呼ばれ、JPEGコーデックでも利用される。
• 変換符号化(transform coding)：入力データ値の集まり(x[0:N])から、出力データ値の集まり(y[0:N])へとまとめて変換する。JPEGコーデックでは原画像を8x8ブロック分割し、各ブロックに含まれる64個のピクセル値ベクトル $\mathbf{x}$ に64x64要素の変換行列 $\mathbf{T}$ を掛け、64個の出力ベクトル $\mathbf{y}$ へと変換する($\mathbf{y} = \mathbf{T} \mathbf{x}$)。逆変換は変換行列 $\mathbf{T}$ の逆行列 $\mathbf{T}^{-1}$ により $\mathbf{x} = \mathbf{T}^{-1} \mathbf{y}$ となる($\mathbf{T}^{-1} \mathbf{T}= \mathbf{I}$)。JPEGコーデックでは $\mathbf{T}$ にDCT(discrete cosine transform)変換行列を用いる。

いずれもエントロピー符号化への入力データを "統計的に偏らせる" こと、元データが持っている冗長性(じょうちょうせい)を取り除く「相関除去(decorrelation)」を目的としています。古典的なものから最新のものまで、ほとんどの実用的なデータ圧縮アルゴリズムは、相関除去とエントロピー符号化の組み合わせで構成されます。⁷

相関除去×エントロピー符号

先ほどのグラデーション画像とランダム・ドット画像に、差分符号化とハフマン符号を適用してみます。差分符号化エンコード／デコード処理は簡単なPythonコードで実装できます。x がデジタル画像のピクセル値、yがハフマン符号の対象となる差分値です。

# 差分エンコード処理: y[] = Fwd(x[])
def encode_delta(y, x):
  pred = 0
  for i in range(len(x)):
    y[i] = x[i] - pred
    pred = x[i]

# 差分デコード処理: x[] = Inv(y[])
def decode_delta(x, y):
  pred = 0
  for i in range(len(y)):
    x[i] = y[i] + pred
    pred = x[i]

この差分符号化とハフマン符号を組み合わせると、1ピクセルあたり平均ビット長は下表のようになります。グラデーション画像では原画像(3bpp)に対して平均ビット長 1.11bpp、ビット量比では 1:2.70 (＝3÷1.11)とそれなりにデータサイズ削減を達成しています。一方のランダム・ドット画像では原画像よりも増えて(+0.73bpp)しまいました。

差分符号化だけに着目すると、値のとりうる範囲がピクセル値(0～7の8段階)から差分値(-7～+7の15段階)へと広がるため、値表現に必要なビット数は一時的に3bitから4bitへと増えます。それでもグラデーション画像でデータサイズ削減ができたのは、差分値の度数分布が大きく偏っているためです。ピクセル値と差分値それぞれの度数分布表（ヒストグラム）を見比べると、"データの偏り" 度合いが大きくなったことが読み取れるかと思います。⁸

👈 #3 データ圧縮の基礎(前編) ／ #5 データ圧縮の基礎(後編) 👉