[&] Tiny Pictures : An Optimization Case Study

Tiny Pictures : An Optimization Case Study
Penultimate (by Ben Zotto)
-----------------------------------------------------------------

要約：Evernoteと同期できる手書きアプリPenultimateの画像圧縮に関して。
UIImagePNGRepresentation()は遅すぎるので、PNG-8を使うことにし、
pngquantも遅すぎるので、あらかじめカラーパレットを作っておきループを無くしました。
最終的には OpenGL ES のルックアップテーブルで超高速化しました。


-----------------------------------------------------------------

Evernoteのユーザーの方、手を挙げてくれるとうれしいんですが...
Ben Zotto といいます。このような機会を設けてくださり、ありがとうございます。

今日は Image Optimization ということで、かなり技術的な内容になります。
Evernote API, SDKのことを聞いたことがありますか？

簡単に API, SDKはご存知のように、非常に人気のあるクラウドメモサービスを同期する仕組みです。
私たちのアプリはこのプラットフォームは、アクセスのための汎用ツールですが、
パワフルな APIを公開していますので、開発者の方々に使ってもらえると思います。

特にこのアプリケーションによって様々なコンテンツを、永久的に保存したいと
思っている人たちにとって、素晴らしい仕組みだと思います。
もうすでに github に iOS SDKが使えるようになっています。
もっとシンプルなバージョンを作っていきたいと考えています。
使った印象を寄せて頂けるとうれしいです。

●さて、Evernote Platform Awards に関して。
一年に一回開催しているアワードです。
最高のアプリケーションをお祝いするものです。
このアワードに是非参加して欲しいと考えております。
9月の頭にアワードが発表される予定です。

●Image Optimization というテーマに入っていきます。
Penultimate という iPad アプリをご存知の方は？
iPad 用の手書きアプリです。
一冊一冊の本としてメモが存在するというアプリです。

iPad でメモを書くと、Evernote に同期されます。
この段階ではすべてイメージとして保存されます。

●さて問題は？
同期のプロセスの際に、すべて画像としてレンダリングする、
編集するたびに頻繁に更新されます。
ところが事情としては、帯域も限られていますし、
Evernote のアップロードの容量も限られています。
そこで、もっとも小さなイメージを作るのが課題となってきます。

●イメージとは何か？
イメージとは、色の値の集まりです。
ビットマップは大きなグリッドとして存在します。
すべてのピクセルが数値として表されています。
イメージを保存したり、転送したりすると、
バイトストリームのエンコードをすることになります。



●RGBA
7 254 7 255
RGBは色、Aは透明を表します。4バイト、4チャンネルで32ビットになります。

●どこが問題なのか？
iOSの世界では二つの関数があります。
UIImagePNGRepresentation() ロスレス、差異は無い
UIImageJPEGRepresentation() ロスがある。
ロスレスの方はソリッドカラーに向いていて、
JPEGの方は写真のようなものに向いています。
このシステム関数があって、高速に使えます。

Evernote に同期する際にどうするのか？

●一つの実験として、
３つの種類のイメージがあります。
メモ、図、それらを組み合わせたもの（Dense）

Raw PNG JPEG
------------------------------------
Writing 2.5mb 145kb 155kb
Diagram 2.5mb 110kb 136kb
Dense 2.5mb 251kb 191kb
------------------------------------
素材はすべて 2.5mb と違いはありません。
実際に PNGと JPEGを比べたところ、数値としては小さくなっています。
PNG と JPEG を比較すると、Dense に関しては JPEGの勝利。

確かにもともとの数値と比べると小さくなっていますが、
いつもEvernote と同期しているのであれば、この数字で充分なのか？と考えます。

JPEGの圧縮パラメータをもっとも小さくなるものにしていますが...

●どちらが良い？
PNGはロスレス PNG と同じくらいしか期待できません。
24bit のカラーとアルファ、
サブセットしか使っていない、ページの下地もだいたい白い。
そこで色深度をベースに最適化を計ります。



●PNG-8
PNG が登場して GIFに代替する際に、PNG-8 というのがありました。
PNG-8 は 256色のパレットを使い、
ピクセルをフルで使うのではなく、インデックス化して使います。
もともとは pixel あたり 4バイトでしたが、1/4 のサイズになりました。

パレットの場合には、255色、32bit カラーをパレットに格納してあります。

●Quantization
フルカラーのイメージをパレットに変換していくのですが、詳しく説明していきます。
Quantization　は３つのステップです。

1. 元の素材から、色のヒストグラムを作ります。
2. 256の共通項をみつけて、最適解を導き出します
3. パレットの中から最良の色を、各ピクセルに対応づけます。

実は pngquant というコマンドも出来ます。

●pngquant
---------------
Writing 61kb
Diagram 36kb
Dense 91kb
---------------
Mac で 0.7秒くらい。
まず、Penultimate では使える色が限定されていることあって、
圧縮された後と比較してもほどんど違いが分からないくらいです。
これが写真であれば、だいぶ異なるのですが。
これは大歓迎できる数字です。

まずは pngquant を使うことで、だいぶ改善できました。

●First attempt
実際にアプリの中で pngquant を使ったところ、1ページあたり6秒かかりました。
これは遅すぎます。iPad で 6秒なんて、とんでもない遅さです。
6秒、悲惨な数値なのですが、ぜひ問題がどこにあるのかプロファイルをとります。
remap_to_palette と nearest_search, colordifference にかなり時間がかかって
いることがわかります。

どこに時間がかかっているのか？
Quantization のプロセスのどこに時間がかかっているのか？
リマッピングにかなり時間を食っているということが分かりました。

for (pixel in image) {
for (color in palette) {
// evaluate color distance.
}
// emit best match for pixel.
}

要は、ループの中を分析することで、もっと速くできないかと考えました。

●Inner Loop
元の pngquant はベクトル式の SSE コードが使われていました。
iOS の ARM 用には ARM NEON があり、それを使って実装しました。

●Outer Loop
元の pngquant では OpenMP を使っていて、ピクセルの並列処理を行っていました。
OpenMP は iOS では使えます。
Grand Central Dispatch を使ってだいたい同じようなことができます。

●Second attempt
これからがクールな作業です。
アウターループの処理を行いましたが、前回は 6秒でした。
今回は ..... 5秒でした。遅すぎますね。（ため息）

●Face
何が問題化というとアルゴリズムが遅い場合は、
いくら実装を速くしたとしても、遅いのだ
ということです。
ここでの命題はインナーループを消してしまったらどうなる？
ルックアップテーブルをあらかじめ持っていたとしたら、
そこから当てはまる色をすぐにピックアップできるだろうということです。

現実の世界では、色合いは違うのですが、
このアプリの場合は、あらかじめルックアップテーブルを予想することができます。

●Third attempt
さて、オフラインで使うことによって、
パレットとルックアップテーブルを、あらかじめバックグラウンド、オフラインで作るようにしました。
前回は 5秒でした、インターループが無くなると、
0.5秒でした！

デスクトップだとしても速いですし、iPad 上の処理としても0.5秒は
素晴らしいスピードだと思います。
イメージのサイズによってスピードは異なりますが、指数的には増えません。



●Is that the end?
いろいろ努力してきました。
そこまでくると、もうちょっとしてみようと、もっと速くできないかと
考えるようになりました。
ルックアップテーブルは3Dテクスチャに見えないか？と考えました。
GPU, OpenGL はもしかしたら使えるのではないかと考えました。

●
スライシングされているように見えると思います。
OpenGL のスライドがありますが、詳細は省略します。
OpenGLの実装は、2Dのジオメトリ, 8bit のパレット、
さらにオフスクリーンのレンダーバッファーを活用。

●Fourth attempt
すべてを GPU の上でやってみました。今回は
0.025秒でした。
これは本当に速いですよね。
どうして 0.025秒まで速くなったのか。
その鍵は、GPUは超並列処理だということ、
シェーダーがピクセルを並行して同時に計算することができます。
Texture lookup も非常に高速です。

●Ship it
UIImagePNGRepresentation よりも、55〜70% 小さくなりました。
見た目は見分けがつかないほど、
とても速い。
特定のユースケースではとても効果がある。

●Morals of the Story. まとめ。

- プロファイリングをしよう。ボトルネックを見つけよう
- 標準のツールは、多くのケースに対応しているので、実際の利用にはどういうニーズ、用途で使われているのか見極める
- 今回はOpenGL を使いましたが、目的のプラットフォームの上で動作するか確認する必要があり

だいたい一週間かけて、このような努力を行いました。
よりよいプロダクトにすることができるのか？
改善できなければ無駄骨です。

Q ルックアップテーブルの大きさは？
A. すべての色が含まれたルックアップテーブルが 4GB ぐらいで大きすぎます。
透明（アルファ）の部分を削除すると、16Mbit まで下げることができます。
最終的には 64x64zx64 のルックアップテーブルになりました。

Q. GPUでバッテリー消費は？
A. テストしてません。懸念も持ちませんでした。