compression
Silicon Valley

Dropboxのロスレス画像圧縮ソフトウェアLeptonは、あの‘middle-out’アルゴリズムを使っている

次の記事

ファッション雑誌さながらのアプリ「TOPLOG」が新たに2億円を調達

lepton-14

Pied Piperではないが、でも似ている。

“middle-out”(ミドルアウト)アルゴリズムは、テレビドラマ「シリコンバレー(Silicon Valley)」のもっとも劣悪な(そしてたぶんもっともおかしい)シーンで有名になったが、Dropboxが最近作ったクールなロスレス画像圧縮ソフトウェアLeptonでは、それがフィクションではなくて本物だ。

Leptonは、JPEGで圧縮した画像のファイルサイズのほとんどをさらに最大22%縮小するが、それでいてオリジナルのビットを一つも失わない。どうやれば、それが可能なのか?…ミドルアウトを使うのだ。

本当は、話はもっと複雑で、Leptonのサイズ節減のある部分は、JPEGではきわめて画一的に保存される明度の値を、より効率的にエンコードする。その詳細はふつうの人には(ぼくみたいなブロガーにも)難しすぎるが、このブログ記事に書かれている。

ミドルアウトされたビットは、解凍されたビットの終端にある。このアルゴリズムは、JPEGが作る8×8ピクセルのブロック2つの境界を見る。そのとき、片方のブロックはすでにデコードされている。まだデコードされていない方のブロックはその明度が、それの中央部(middle)からの…middleからoutにかけての…グラデーションに合っている傾向がある。そこでアルゴリズムは、その前提に従って明度値を予測する。そして、その予測値と実値のデルタのみを保存する。VP8コーダーの演算に適した形式で。

lepton-13

中央(middle)から……..外(out)へ。

この方法でエンコードされた明度係数は、Dropboxのチームが遭遇した画像の平均約8%で正しいが、彼らはその8%を約61%縮めることにより、この方法だけで全体的なファイルサイズの5%を縮減した。22%のうちの残る17%は、そのほかのさまざまなテクニックで実現しているが、あなたがぼくを信じてくれるならば、それらのお話はそれほどおもしろくはない。

しかもユーザーがそれらのどれかに気づくことはない。Leptonによる圧縮はDropboxのサーバー上でのみ行われ、そのデータはコールドストレージに保存される。ユーザーが画像をリクエストするとLeptonはその逆の仕事を(しかも高速に)して、ユーザーにはふつうのJPEGを渡す。しかしDropboxの上では、数ペタバイトものスペースが節約される。

Leptonはオープンソースで、DropboxはそのコードをGithubに置いている。それをいじくるのは自由だし、この記事を最後まで読めた人なら、きっと遊びたくなるだろう!

[原文へ]
(翻訳:iwatani(a.k.a. hiwa))