JPEGの仕組みをおぼろげに知っている人ほど、むしろこれみて「ありえない」と思ったのではないのでしょうか。
でもよーく考えてみると、これでいけるという方法を発見というか再発見したので。
2012年4月19日木曜日
404 Blog Not Found:algorithm - JPEGminiの仕組みを推理する
なぜJPEGminiがありえなさそうに見えるかは、以下に集約されます。
「なぜコンピュータの画像はリアルに見えるのか」 P.131たとえば「ここは文字」「ここは背景の空」などと、ユーザーが自由に品質を設定できれば、さらによい画像になるはずです(できれば、それもコンピュータが自動で決めてくれるとうれしいのですが)。
同書も指摘しているように、JPEG 2000のようにそれに相当することをやっている画像フォーマットは複数あります。しかしJPEGminiが生成するJPEGは、古き佳きJPEG、さらく詳しく言えばJFIFなのです。品質の設定は画像全体に対してしかできないはずのJFIFに「ここは文字」「ここは背景の空」をどうやって実現した--ように見える--のでしょうか?
JPEGのキモ、量子化テーブル
ここでJPEGがどうやって不要な情報を捨てているのかを改めて見てみましょう。簡単のため、画像は256階調グレイスケールだとします。
cは、辞書式順序を実行するためのアルゴリズム
- 画像全体を8x8のミニ画像=ブロックに分解。画像の縦横が8の倍数でない場合適当な画素で埋めて、再生時に切り落とす
- それぞれのブロックに対して
- 離散コサイン変換(Descrete Cosine Transform, DCT)を施す→左上に大きな数値が集中する
- 量子化テーブルの数値でそれを割って整数に丸める→この操作で情報が捨てられる。JPEGで非可逆的なのはこのため。以下はq=50のときの、(団体名としての)JPEGが推奨する値。
おおまかに左上に行く程数字は小さく、右下にいくほど数字は大きくなっている。最大値である255をこれで割った数が、量子化数。1なら0から255までの階調があり、128なら0と1の2階調になり、そして255だったら255以外の場合は全て0になる事実上の1階調。16 11 10 16 24 40 51 61 12 12 14 19 26 58 60 55 14 13 16 24 40 57 69 56 14 17 22 29 51 87 80 62 18 22 37 56 68 109 103 77 24 35 55 64 81 104 113 92 49 64 78 87 103 121 120 101 72 92 95 98 112 100 103 99 - これを左上から右下にジグザグにスキャンしていく→末尾の方には0ばかりならぶ
- あとはこれをRLE連長圧縮した上で、エントロピー符号化する。
英語版Wikipediaの図解がかなりわかりやすいのでそちらも参照していただくとして、キモは二つだけ
一緒に複数のマイクを接続するために使用されているもの
- 画像を8x8ピクセルのブロックをならべたタイルとみなして、それぞれのタイルを圧縮する
- それぞれのブロックがどれだけ圧縮できるかは、DCT適用後のブロックの各要素の値をどれだけ小さく--特にゼロに--できるかで決まる。
この2を担当しているのが量子化テーブル(DQT)なのですが、画像の場所によって圧縮率を変えるということは、いわばタイルごとに異なる量子化テーブルを適用していると言い換えることができます。
ところがJFIFフォーマットの仕組み上、ファイルに載せられるテーブル数はたかだか16個であり、さらに規格では4つまでということになっています。たいていのフルカラーJFIFではYCbCrのY(輝度)用とCbCr共用(彩度)の二つしか持っていません。DQTを取り出すPerl Scriptをgistにはっておいたので各自確認していただきたいのですが、JPEGminiが生成するJFIFも、この点に関しては何の変哲もない普通の規格どおりのJFIFです。
仮にテーブルをいくつでも搭載できるようにしても、今度はそれでファイルがかさばってしまいます。だからこそJFIFは全てのブロックで使うテーブルを一つか二つだけ持つようにしているのですが、それでは前述のとおりブロックごとに最適化されたテーブルを適用するなんて無理なはずです。
ゼロに何をかけてもゼロ
それでは今度は元の画像を復元させるときのことを考えてみましょう。画像をJPEGにした時の逆をたどるだけです。
テキストをHTMLに90度回転させる方法
- エントロピー圧縮を解いて8x8のブロックを埋める
- ブロックのそれぞれの位置に量子化テーブルの対応する位置の数値をかける
- それを逆コサイン変換する(IDCT)
- 元のブロックの出来上がり
このとき量子化テーブルが異なれば、再生される画像は大きく狂ってしまうはずです。例えば一番右上の元の数値が42、量子化テーブルが4だったとしたら、JPEGではそれは10として記載されます。それに4をかければ40という元の数値と近い数値が得られますが、そこをいじくって8とかにしたら、80になってしまいます。
しかし、量子化テーブルの数値がどんな場合でも必ず同じ数になる数値が存在します。
ゼロです。ゼロに何をかけても0なのですから、当然ですよね。
ということは、「各ブロックのしっぽ」のゼロの長さを、本来のものより長く--その分「あたま」の非ゼロを短く--すれば、量子化テーブルを一切変更することなく、そしてファイルフォーマットを損なうことなく圧縮率を上げることができることになります。
もちろん圧縮率を上げる代償として画質が損なわれるのですが、どれだけのトレードオフが許されるかは、元となるJPEGの量子化テーブルが知っています。
あとはたとえば「元画像の圧縮誤差と同じ程度の誤差におさまるような『ゼロ化』をそれぞれのブロックに適用していけば、minifiedされたJPEGが出来上がることになります。ブロックの大きさは64、うちブロック全体を支配する一番左上(DC成分)を除いて63個までのゼロがありうるとしたら、「ブロックを符号化して復号化して元ブロックと比較する」という作業を最悪63回繰り返せばいい…
あくまで推理
以上がJPEGminiの動作原理に対する推理です。あくまで推理であって、もっとすごい技術を彼らが持っている可能性を否定するものではありません。特に以下のFirst Partに関しては。
JPEGmini | TechnologyJPEGmini 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
These are our most popular posts:
GlusterFSとElastic Hash Algorithm
一方、すべての分散ストレージに共通の特徴、それはスケーラビリティです。GlusterFS はElastic Hash Algorithm (以下EHA) というアルゴリズムを使ってデータの分散とノン ストップでのスケールアウトを実現していますが、英語／日本語ともに文献が十分とは ... read moreAnalysis of Algorithms
return b. Analysis of Algorithms. 22. Analysis of Algorithms. Exercise 1-2. What are the outputs of Test2(100) and Test3(1000) ? Test2（100）とTest3（1000 ）の 出力結果は何ですか？ Test2とTest3は次のアルゴリズムです。 Algorithm Test2(n). b 0 ... read moreアルゴリズム - Wikipedia
アルゴリズム（英: Algorithm）とは、数学、コンピューティング、言語学、あるいは関連 する分野において、問題を解くための効率的手順を定式化した形で表現したものを意味 する。算法（さんぽう）と訳されることもある。 コンピュータにアルゴリズムを指示するため の（ ... read moreAnswer Book for Basic Larning Algorithm
1999年1月26日 ... これを実現するアルゴリズムが、次の時間軸スムージング学習です。 図1 空間と時間の 対応付け. （2.2）時間軸スムージング [Temporal Smoothing(TS) Learning] 学習って 何ですか？ 図2のように、センサの信号を入力とする学習装置（ ... read more
登録:
コメントの投稿 (Atom)
0 件のコメント:
コメントを投稿