2012年01月23日 19:30 [Edit]

algorithm - JPEGminiの仕組みを推理する

JPEGの仕組みをおぼろげに知っている人ほど、むしろこれみて「ありえない」と思ったのではないのでしょうか。

でもよーく考えてみると、これでいけるという方法を発見というか再発見したので。


なぜJPEGminiがありえなさそうに見えるかは、以下に集約されます。

なぜコンピュータの画像はリアルに見えるのか」 P.131
たとえば「ここは文字」「ここは背景の空」などと、ユーザーが自由に品質を設定できれば、さらによい画像になるはずです(できれば、それもコンピュータが自動で決めてくれるとうれしいのですが)。

同書も指摘しているように、JPEG 2000のようにそれに相当することをやっている画像フォーマットは複数あります。しかしJPEGminiが生成するJPEGは、古き佳きJPEG、さらく詳しく言えばJFIFなのです。品質の設定は画像全体に対してしかできないはずのJFIFに「ここは文字」「ここは背景の空」をどうやって実現した--ように見える--のでしょうか?

JPEGのキモ、量子化テーブル

ここでJPEGがどうやって不要な情報を捨てているのかを改めて見てみましょう。簡単のため、画像は256階調グレイスケールだとします。

  1. 画像全体を8x8のミニ画像=ブロックに分解。画像の縦横が8の倍数でない場合適当な画素で埋めて、再生時に切り落とす
  2. それぞれのブロックに対して
  3. 離散コサイン変換(Descrete Cosine Transform, DCT)を施す→左上に大きな数値が集中する
  4. 量子化テーブルの数値でそれを割って整数に丸める→この操作で情報が捨てられる。JPEGで非可逆的なのはこのため。以下はq=50のときの、(団体名としての)JPEGが推奨する値。
    1611101624405161
    1212141926586055
    1413162440576956
    1417222951878062
    182237566810910377
    243555648110411392
    49647887103121120101
    7292959811210010399
    おおまかに左上に行く程数字は小さく、右下にいくほど数字は大きくなっている。最大値である255をこれで割った数が、量子化数。1なら0から255までの階調があり、128なら0と1の2階調になり、そして255だったら255以外の場合は全て0になる事実上の1階調。
  5. これを左上から右下にジグザグにスキャンしていく→末尾の方には0ばかりならぶ
  6. あとはこれをRLE連長圧縮した上で、エントロピー符号化する。

英語版Wikipediaの図解がかなりわかりやすいのでそちらも参照していただくとして、キモは二つだけ

  1. 画像を8x8ピクセルのブロックをならべたタイルとみなして、それぞれのタイルを圧縮する
  2. それぞれのブロックがどれだけ圧縮できるかは、DCT適用後のブロックの各要素の値をどれだけ小さく--特にゼロに--できるかで決まる。

この2を担当しているのが量子化テーブル(DQT)なのですが、画像の場所によって圧縮率を変えるということは、いわばタイルごとに異なる量子化テーブルを適用していると言い換えることができます。

ところがJFIFフォーマットの仕組み上、ファイルに載せられるテーブル数はたかだか16個であり、さらに規格では4つまでということになっています。たいていのフルカラーJFIFではYCbCrのY(輝度)用とCbCr共用(彩度)の二つしか持っていません。DQTを取り出すPerl Scriptをgistにはっておいたので各自確認していただきたいのですが、JPEGminiが生成するJFIFも、この点に関しては何の変哲もない普通の規格どおりのJFIFです。

仮にテーブルをいくつでも搭載できるようにしても、今度はそれでファイルがかさばってしまいます。だからこそJFIFは全てのブロックで使うテーブルを一つか二つだけ持つようにしているのですが、それでは前述のとおりブロックごとに最適化されたテーブルを適用するなんて無理なはずです。

ゼロに何をかけてもゼロ

それでは今度は元の画像を復元させるときのことを考えてみましょう。画像をJPEGにした時の逆をたどるだけです。

  • エントロピー圧縮を解いて8x8のブロックを埋める
  • ブロックのそれぞれの位置に量子化テーブルの対応する位置の数値をかける
  • それを逆コサイン変換する(IDCT)
  • 元のブロックの出来上がり

このとき量子化テーブルが異なれば、再生される画像は大きく狂ってしまうはずです。例えば一番右上の元の数値が42、量子化テーブルが4だったとしたら、JPEGではそれは10として記載されます。それに4をかければ40という元の数値と近い数値が得られますが、そこをいじくって8とかにしたら、80になってしまいます。

しかし、量子化テーブルの数値がどんな場合でも必ず同じ数になる数値が存在します。

ゼロです。ゼロに何をかけても0なのですから、当然ですよね。

ということは、「各ブロックのしっぽ」のゼロの長さを、本来のものより長く--その分「あたま」の非ゼロを短く--すれば、量子化テーブルを一切変更することなく、そしてファイルフォーマットを損なうことなく圧縮率を上げることができることになります。

もちろん圧縮率を上げる代償として画質が損なわれるのですが、どれだけのトレードオフが許されるかは、元となるJPEGの量子化テーブルが知っています。

あとはたとえば「元画像の圧縮誤差と同じ程度の誤差におさまるような『ゼロ化』をそれぞれのブロックに適用していけば、minifiedされたJPEGが出来上がることになります。ブロックの大きさは64、うちブロック全体を支配する一番左上(DC成分)を除いて63個までのゼロがありうるとしたら、「ブロックを符号化して復号化して元ブロックと比較する」という作業を最悪63回繰り返せばいい…

あくまで推理

以上がJPEGminiの動作原理に対する推理です。あくまで推理であって、もっとすごい技術を彼らが持っている可能性を否定するものではありません。特に以下のFirst Partに関しては。

JPEGmini | Technology
JPEGmini technology has two main components: The first is an image quality detector, which imitates the perceptual qualities of the human visual system, to determine the maximum amount of compression which can be applied to each individual photo without causing visible artifacts. The second is a unique JPEG encoder, which adapts the JPEG encoding process to the original photos, creating the most compact representation of the photos that is possible under the JPEG standard. Combining these two components enables JPEGmini to achieve an extremely high recompression ratio of up to 5x, or 80% reduction on digital photos, depending on their resolution.

しかしSecond Partのunique JPEG encoderの実装は、推理通りなのではないかと。

互換性に負けた機能、昨日に負けた今日

しかし彼らの発想のするどさに対する敬意とおなじぐらい、もう技術的では最新とはいいがたいJPEGをさらに後押しすることに対するうしろめたさを禁じ得ません。

JPEGmini uses the standard baseline JPEG format, which is by far the established market leader in the image compression space. Newer formats such as JPEG2000, JPEG-XR and WebP have not gained any significant market share yet. Although these formats presumably offer better compression than JPEG, JPEGmini’s unique recompression technology can produce JPEG files that are smaller in size than corresponding JPEG2000, JPEG-XR or WebP files.

なんだかVistaがXPに負けたときみたいな。

Windowsで7に相当する、JPEGを置き換える非可逆画像ファイルフォーマットが台頭する日は来るのでしょうか…

Dan the Lossy Blogger

Extract DQT


この記事へのトラックバックURL

この記事へのコメント
本質ではないですが残念な間違いがあったので指摘しておきます。
DCT後の要素の最大値は255ではありません。
(具体的にいくつかはよく知りませんが1023あたりだったかと)
よって量子化テーブルが255でも1階調になることはありません。
Posted by ikadzuchi at 2012年02月09日 22:54