ImageMagick 改造入門 (その参) 減色処理後編
よやこんにちは。クライアント基盤チームのよやです。
減色処理の話の続きで、ImageMagick の改造についてお話します。
ImageMagick 減色処理の３つのフェーズのうち２つ目にあたる「RGB 空間で分割された立方体の統合処理」で特に時間がかかっていたので、少し手を加えて高速化しました。
前回のこの図に相当する処理です。
ImageMagick の既存の処理
前回、説明した「RGB 空間で分割された立方体の統合処理」のより細かい解説です。
統合処理の詳細
既存の ImageMagick の減色処理では、quantize_error の小さい順にRGB色空間内の立方体を削除して、それらのひとつ親の立方体に統合する処理を繰り返します。
-
対応コード (magick/quantize.c)
- 望みの色数になるまで繰り返す (ReduceImageColors)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
static void ReduceImageColors(const Image *image,CubeInfo *cube_info) { #define ReduceImageTag "Reduce/Image" MagickBooleanType proceed; MagickOffsetType offset; unsigned long span; cube_info->next_threshold=0.0; for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; ) { cube_info->pruning_threshold=cube_info->next_threshold; cube_info->next_threshold=cube_info->root->quantize_error-1; cube_info->colors=0; Reduce(image,cube_info,cube_info->root); ＜略＞ |
- ツリーを辿って、prune_threshold 以下の立方体をひとつ上に吸収させる (Reduce)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
static void Reduce(const Image *image,CubeInfo *cube_info, const NodeInfo *node_info) { register long i; unsigned long number_children; /* Traverse any children. */ number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; for (i=0; i < (long) number_children; i++) if (node_info->child[i] != (NodeInfo *) NULL) Reduce(image,cube_info,node_info->child[i]); if (node_info->quantize_error <= cube_info->pruning_threshold) PruneChild(image,cube_info,node_info); else { /* Find minimum pruning threshold. */ if (node_info->number_unique > 0) cube_info->colors++; if (node_info->quantize_error < cube_info->next_threshold) cube_info->next_threshold=node_info->quantize_error; } } |
ステップを追って解説
まずは、消す対象を探すのにRGB色空間のツリーを全探索して、一番小さな quantize_error 値を取得します。(図の例は深さ１ですが、実際には再帰でもっと深いツリーが構成されます)
前回見つけた quantize_error = 10 の立方体を削除して、同時に、残りの立方体の中で一番 quantize_error の小さなものを探します。勿論、ツリーは全探索です。
前回、quantize_error = 20 の立方体を見つけたので、今回それを削除して、また次に quantize_error の小さな立方体を探します。
このように、１つの立方体を消す毎にツリーを全部辿り、その処理を何度も繰り返すのが既存の処理です。
ImageMagick の高速化解説
色が残るギリギリの閾値を先に探しておけば、繰り返す必要が無くなると考え、quantize_error を小さい順に並べて、閾値を探す処理を入れました。
改造詳解
まず、RGB色空間のツリーを全て辿り、含まれる全ての quantize_error を１つの一次元配列に並べます。
- 対応コード (magick/quantize.c)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
static unsigned int QuantizeErrorFlatten(const Image *image, CubeInfo *cube_info, const NodeInfo *node_info, MagickRealType *quantize_error_list, int quantize_error_offset, int quantize_error_offset_max) { long number_children; register long i, num ; if (quantize_error_offset >= quantize_error_offset_max) { fprintf(stderr, "quantize_error_offset >= quantize_error_offset_max\n"); return 0; } quantize_error_list[quantize_error_offset] = node_info->quantize_error; num = 1; number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; for (i = 0; i < number_children ; i++) { if (node_info->child[i] != (NodeInfo *) NULL) { num += QuantizeErrorFlatten(image,cube_info,node_info->child[i], quantize_error_list, quantize_error_offset+num, quantize_error_offset_max); } } return num; } |
qsort で小さい順に並べて、残したい色数ギリギリの quantize_error を敷居値として採用します。
こうして見つけた quantize_error を cube_info->pruning_threshold の初期値として代入しておけば、ツリーを一度辿るだけで色空間の統合処理が終わります。尚、コードの上では next_threshold を介して while の頭で pruning_threshold に代入しています。
- 対応コード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
static int MagickRealTypeCmp(const void *a, const void *b) { MagickRealType *af = (MagickRealType *) a; MagickRealType *bf = (MagickRealType *) b; if (*af > *bf) return 1; return -1; } static void ReduceImageColors(const Image *image,CubeInfo *cube_info) { ＜略＞ cube_info->next_threshold=0.0; /* yoya speed up customize */ if (cube_info->colors > cube_info->maximum_colors) { MagickRealType *quantize_error_list; unsigned int quantize_error_result; quantize_error_list = malloc(sizeof(MagickRealType) * cube_info->nodes); quantize_error_result = QuantizeErrorFlatten(image, cube_info,cube_info->root, quantize_error_list, 0, cube_info->nodes); qsort(quantize_error_list, cube_info->nodes, sizeof(MagickRealType), MagickRealTypeCmp); cube_info->next_threshold = quantize_error_list[cube_info->nodes - cube_info->maximum_colors]; free(quantize_error_list); } |
改造結果の検証
- ImageMagick の convert コマンドを使ってアバター画像を PNG から GIF アニメーションに変換して、改造前後で時間を比較します。
パフォーマンス計測
処理の重たそうなアバター画像で実験します。
- オリジナル ImageMagick (v6.6.0)
|
1 2 3 4 5 |
% time /home/yoya/test/im660/bin/convert -layers optimize avatar[1-8].png avatar.gif real 0m5.436s user 0m5.416s sys 0m0.052s |
- 改造版 ImageMagick
|
1 2 3 4 5 |
% time /home/yoya/test/im660y/bin/convert -layers optimize avatar[1-8].png avatar.gif real 0m0.581s user 0m0.548s sys 0m0.052s |
10倍近く速くなりました。
これは極端な例ですが、色数の多いアバター画像であれば、大抵は数倍速くなります。
計測グラフ
本番サービス上で実際に表示されていたアバター画像から1000種類サンプリングして、処理時間がどう変わるのかグラフ化しました。
各々のアバター素材の静止画像を convert コマンドで GIF アニメーションに変換して、処理時間のトリム平均(*1)を短い順で並べます。縦軸の単位は秒数です。
処理に時間がかかる程、改善効果が強くあらわれる、大変都合の良い結果が出ました。
これなら、今までアバターの画像生成でユーザが30秒待たされるような状況でも2,3秒で済むかもしれません。
問題点
うまい話ばかりでなく、赤青緑がまんべんなく使われ、かつ各々にグラデーションが多用される画像でカラーバンディング(*2)が発生し易くなります。
ユーザのアバター画像を300枚程チェックしてようやく見つけた例を挙げます。
=> 
ぱっと見では分かりにくいので、拡大してピクセル単位で見ていきましょう。
左頬の領域に着目すると、グラデーションの諧調が一つ減っているのが分かります。この原因はまだ不明です。
実は、QuantizeErrorFratten の処理において、１つの立方体の中に複数の色パレットがある場合を考慮していない問題がありますが、色空間の分割をケチるのは22万ノードに達した時で、上記の元画像は１万色なので、この問題にはあたりません。
仮に22万色以上あったとしても、指定した色数の立方体が残るようにオフセットを指定しているので、大目に色が残り省略するつもりのループが少し動いてしまうだけで画質に影響は出ないはずです。
最終的な見た目にはほぼ影響ない上に表示にかかる時間が圧倒的に短くなる為、これをサービスに適用しない手はないですが、画質も維持できればそれが理想なので今後の研究課題としています。
他の改善案
- RGB色空間は人間の視覚特性とは軸も距離も合いません。別の色空間で処理した方がより画質を保てそうです。例えば、CIE XYZ やその派生系の Lab 等が候補として挙げられます。
- 色空間内の距離を計算する際に sqrt で平方根をとっていますが、距離については加算と比較しかないので、距離の自乗のまま処理した方が CPU の負荷が低いと思われます。
- ImageMagick はデフォルトで build すると RGB を各々 16bits で内部処理します。Web の世界ではほぼ 8bits ですので、configure 時に --with-quantum-depth=8 (はじめの - は二つ)を指定すると画質を殆ど維持したまま、性能を少なからず up できます。ただ、減色処理に関しては殆ど変りませんでした。
最後にまとめ
今回の改造を短く説明すると
- 減色処理に使う RGB(A) 色空間を表す 8進木(or16進木)の各ノードにある quantize_error を一次元配列に展開して qsort で昇順に並べ、256色が残るオフセットで quantize_error の閾値を取得し、cube_info->pruning_threshold の初期値にする。
となります。改造自体は簡単です。
その壱で紹介した GIF アニメ(携帯端末)不具合対応パッチも含め、本件の改造パッチを Github に commit しました。参考になれば幸いです。
少しやり過ぎた為、社内では属人的なパッケージ名で呼ばれています。御了承下さい。
Debian squeeze のパッケージに合わせて ImageMagick の元 version は 6.6.0.4 ですが、最新の ImageMagick にも、ほぼコピペで適用出来ると思います。
以上です。