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

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))

OperaのAndroid用データ節約アプリが合衆国と西ヨーロッパでベータへ

昨年の12月にOperaが発表した無料アプリMaxは、暗号化されていないデータをすべて、Operaのサーバをを使ってユーザのAndroidデバイスへ圧縮する。そのときは小規模な非公開アルファテストに登録できただけだが、でも今日からは、Maxのもうじき始まるベータへの登録を受け付ける。

Maxは、テキストでも写真でもビデオでも何でも圧縮してユーザの携帯に送るから、かなりの帯域節約になる。とくにビデオは帯域大食らいだから、このアプリによって、データプランの料金を相当節約できるだろう。

GoogleがChromeモバイルのためのデータ節約プロキシの展開を開始したのはごく最近だが、Operaはかなり前からデスクトップ向けに”Turbo“モードを提供してきたし、また一部のモバイルブラウザはOperaのサーバから圧縮データしか受け取らない。実は、Appleのブラウザエンジンを使っていないOperaのiPhoneアプリが承認されたのも、そのおかげだ。

Maxの技術的詳細はまだよく分からないが、同社によると、ブラウザのための圧縮技術をユーザのすべてのアプリに適用することにしたのだ。一部のアプリ、たとえばFacebookなんかは、つねにすべてのデータを圧縮していて、Operaのプロキシをバイパスしている。でも、Operaのスクリーンショットを見るかぎり(上図)、InstagramやFlipboard、Vineなど画像の多いアプリはこのツールで相当助かるだろう。

ただしすべてのデータがOperaのサーバ経由になるから、Operaという企業をかねてから十分に信用している人でないと、このツールは使い辛い。また、Operaのプロキシを使うことによって大きな遅延が生ずるなら、モザイク画像が多くなったりして困ることにもなりかねない。

このアプリはすでに、Google Playのストアで入手できる。インストールした人は、自動的にベータのユーザになる。ただし今のところこのツールを使えるのは、合衆国と西ヨーロッパだけだ。

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


Googleが新しい圧縮アルゴリズムZopfliをオープンソースで発表

Volvo_Large_Asphalt_Compactors

Googleが今日(米国時間2/28)、オープンソースの新しい圧縮アルゴリズムZopfliローンチした。今の標準圧縮技術であるzlibライブラリに比べて5〜8%圧縮率が高いといわれ、また解凍アルゴリズムは今のWebブラウザが現用しているもので間に合うため、Webサーバがこれを採用すれば、データの伝送速度が上がり、Webをやや速くすることができるだろう。

このアルゴリズムはチューリッヒ在住のGoogle社員Lode Vandevenneが20%プロジェクト*として作ったもので、Deflateアルゴリズムの実装だ。それはZIPやgzipが使っているアルゴリズムで、画像ファイルのPNGにも使われている。出力(圧縮結果)はzlibと互換性があるが、圧縮を行うアルゴリズムがzlibとは異なり、より効率的だ。〔*: 20%プロジェクト, 会社の拘束時間の20%は好きなこと(研究開発)をしてよい、というGoogleの内規。〕

Vandevenneは今日の発表声明で、“この徹底的で容赦のない圧縮アルゴリズムは、エントロピーモデルの反復と最短経路アルゴリズムを駆使し、可能なすべてのデフレート表現のグラフ中にビットコストの低い経路を見つける”、と述べている。

ただし、高い圧縮率の代償は長い圧縮時間だ(解凍時間は同じ)。Vandevenneはこう書いている: “最大でzlibの2〜3倍のCPU時間を要するので、Webの静的コンテンツのように、一度圧縮したらそれを今後何度でも使える、というアプリケーションに向いている”。

画像クレジット: Volvo

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