ImageMagick 改造入門 (その四)

2013/12/07

よや

こんにちは。マルチメディアエンジニアリングチームのよやです。最近は ImageMagick のストーキング(アップデートの差分追跡)に余念のない日々を送っています。

尚、本エントリは GREE Advent Calendar 2013 の 7日目です。よろしくお願いいたします！

ImageMagick をサービスに適用している皆様におかれましては、バージョンアップに大変な慎重さをもって臨まれていると思いますが、自分なりの薀蓄を共有出来ればと、バージョンアップに絡んだ最近の闘いの記録を公開します。(長文です)

参考までに今まで ImageMagick について解説したエントリを並べます。

初めに

ImageMagick 公式サイト > http://www.imagemagick.org/
ImageMagick は開発の大変活発なプロジェクトです。提案されたコードを取り込むのも素早いです。その代わりといってか、バージョンによって画質が大きく変わったり、細かいデグレードも結構入ります。
ImageMagick は x.y.z-p のバージョン形式を取りますが、major version miner version, patch 番号といった区別は無しに、xyzp という4桁の１つのバージョンであると捉えるのが正しいです。(但し p は 0～10なので、そこだけ11進数)
リーダーの Cristy さんは svn commit コメントを殆ど書きません。でも、ソースコード自体は読み易いので差分を追うのは怖くないです。コワくない、コワくない。。

色んなバージョンで試す

弊社の画像担当者は複数のバージョンの実行ファイルを手元に用意して、調査に備えています。

~/ImageMagick% ls | tail -5
6.8.7-4
6.8.7-5
6.8.7-6
6.8.7-7
6.8.7-8
~/ImageMagick% ls -l | wc
    647    5098   33803
~/ImageMagick% ls 6.8.7-8/bin/
Magick-config      Wand-config  composite  display   mogrify
MagickCore-config  animate      conjure    identify  montage
MagickWand-config  compare      convert    import    stream

~/ImageMagick% ls | tail -5

6.8.7-4

6.8.7-5

6.8.7-6

6.8.7-7

6.8.7-8

~/ImageMagick% ls -l | wc

647 5098 33803

~/ImageMagick% ls 6.8.7-8/bin/

Magick-config Wand-config composite display mogrify

MagickCore-config animate conjure identify montage

MagickWand-config compare convert import stream

この環境を作るのは簡単で、探せるだけのバージョンの tar.gz を集めて、以下のようなスクリプトでまとめて build 出来ます。尚、zlib が 1.2.6 だと ImageMagick-6.7.5-0 以降しかコンパイル出来ません。(*1) 参考 > http://www.imagemagick.org/discourse-server/viewtopic.php?t=20267&p=80457

#! /bin/sh
for file in `ls -r ImageMagick*.tar.*` ; do
  version=`echo $file | sed 's/ImageMagick-\(.*\).tar\(.*\)/\1/'`
  version2=`echo $file | sed 's/ImageMagick-\(.*\)-[0-9]\+.tar\(.*\)/\1/'`
  if [ "$pre_version" != "$version" ] ; then
    echo === $file ===
    tar xf $file
    dir="ImageMagick-$version"
    if ! [ -d $dir ] ; then
        dir="ImageMagick-$version2";
    fi
    if [ -d $dir ] ; then
      (cd $dir ; ./configure --without-perl --without-magick-plus-plus --prefix=$HOME/ImageMagick/$version ; make install)
      rm -rf $dir
    fi
    pre_version=$version
  fi
done

#! /bin/sh

for file in `ls -r ImageMagick*.tar.*` ; do

version=`echo $file | sed 's/ImageMagick-$.*$.tar$.*$/\1/'`

version2=`echo $file | sed 's/ImageMagick-$.*$-[0-9]\+.tar$.*$/\1/'`

if [ "$pre_version" != "$version" ] ; then

echo === $file ===

tar xf $file

dir="ImageMagick-$version"

if ! [ -d $dir ] ; then

dir="ImageMagick-$version2";

if [ -d $dir ] ; then

(cd $dir ; ./configure --without-perl --without-magick-plus-plus --prefix=$HOME/ImageMagick/$version ; make install)

rm -rf $dir

pre_version=$version

done

実行ファイルが用意出来れば、以下のようなスクリプトで各バージョンでの convert コマンドをまとめて実行出来ます。

convert_allver.sh

#! /bin/sh
imagemagick_dir=$HOME/ImageMagick
last_arg=`eval echo '$'{$#}`
for ver in `ls -r $imagemagick_dir`
do
  option=""
  for arg in $*
  do
     if [ "$arg" != "$last_arg" ]; then
       option="$option $arg"
     else
       option="$option $ver-$arg"
     fi
  done
convert=$imagemagick_dir/$ver/bin/convert
echo $convert $option
time $convert $option
done

#! /bin/sh

imagemagick_dir=$HOME/ImageMagick

last_arg=`eval echo '$'{$#}`

for ver in `ls -r $imagemagick_dir`

option=""

for arg in $*

if [ "$arg" != "$last_arg" ]; then

option="$option $arg"

else

option="$option $ver-$arg"

done

convert=$imagemagick_dir/$ver/bin/convert

echo $convert $option

time $convert $option

done

実行例

% sh convert_allver.sh ~/ava/000[0123].png test.gif
% ls
4.2.9-test.gif     6.4.5-5-test.gif   6.5.9-5-test.gif   6.7.3-2-test.gif
5.5.7-36-test.gif  6.4.5-6-test.gif   6.5.9-6-test.gif   6.7.4-0-test.gif
6.0.0-7-test.gif   6.4.5-7-test.gif   6.5.9-7-test.gif   6.7.4-1-test.gif
6.2.6-8-test.gif   6.4.5-8-test.gif   6.5.9-8-test.gif   6.7.4-10-test.gif
＜略＞

% sh convert_allver.sh ~/ava/000[0123].png test.gif

% ls

4.2.9-test.gif 6.4.5-5-test.gif 6.5.9-5-test.gif 6.7.3-2-test.gif

5.5.7-36-test.gif 6.4.5-6-test.gif 6.5.9-6-test.gif 6.7.4-0-test.gif

6.0.0-7-test.gif 6.4.5-7-test.gif 6.5.9-7-test.gif 6.7.4-1-test.gif

6.2.6-8-test.gif 6.4.5-8-test.gif 6.5.9-8-test.gif 6.7.4-10-test.gif

＜略＞

バージョン比較

上記のスクリプトで作った画像ファイルをテーブル表示して比較します。

通常、古いバージョンを見る必要は無いのですが、古い不具合がずっと放置され、後の方で入った他のコミットとの相性で問題が顕在化する事もあり、デグレードの根本原因を調べるのに網羅的な確認は欠かせません。

この一覧を拡大してよく見ていくと、いくつかのバージョンで画質が大幅に変わる所があります。

顔だけ拡大した比較画像。

(*2)

画像にブツブツが入る問題は当時の最新バージョンでも残っていました。
その為、弊社で使っている ImageMagick は 6.3.x 系からなかなかバージョンアップ出来なかったのですが、脆弱性の対応で是が非でもバージョンを上げる必要が出てきました。
脆弱性パッチだけバックポートする手もありますが、我々は後ろに倒れるのをよしとせず前のめりで行きます。本体の改造です！

改造

急ぎだった事もあり、改造分のソースは ImageMagick から fork した YoyaMagick で公開しました。
- https://github.com/gree/YoyaMagick ＞ releases/tag/6.8.5-6-y3

顔にブツブツ問題

6.4.1-7 では問題なしで、6.4.1-8 から画質が悪化しています。

ImageMagick-6.4.1-7	ImageMagick-6.4.1-8

同僚との会話。

(kazuma.morimoto)
色距離の計算が元々pixel単位で
6.3.5
 778     node_info->quantize_error+=sqrt((double) (error.red*error.red+
 779       error.green*error.green+error.blue*error.blue+error.opacity*
 780       error.opacity));

となっていたのが、pixelのRGBA値が等しい場合は纏めて計算するようになっていて
その際にcountがsqrtの中に入っています。

6.4.5
 813     node_info->quantize_error+=sqrt((double) (count*error.red*error.red+
 814       count*error.green*error.green+count*error.blue*error.blue+
 815       count*error.opacity*error.opacity));

(yoya)
なるほど。ヒストグラムでの重み付けの要素が強かったので、少し抑えたか。間違えて入れてしまったか。。（多分、後者）

(kazuma.morimoto)

色距離の計算が元々pixel単位で

6.3.5

778 node_info->quantize_error+=sqrt((double) (error.red*error.red+

779 error.green*error.green+error.blue*error.blue+error.opacity*

780 error.opacity));

となっていたのが、pixelのRGBA値が等しい場合は纏めて計算するようになっていて

その際にcountがsqrtの中に入っています。

6.4.5

813 node_info->quantize_error+=sqrt((double) (count*error.red*error.red+

814 count*error.green*error.green+count*error.blue*error.blue+

815 count*error.opacity*error.opacity));

(yoya)

なるほど。ヒストグラムでの重み付けの要素が強かったので、少し抑えたか。間違えて入れてしまったか。。（多分、後者）

つまり、quantize_error に色空間内の色と中央との距離を計算してトータルを出す時、ビットマップ画像内に複数の場所で同じ色が使われる場合は、その分を足しこむアルゴリズムですが、その色数を count 変数で数えておく事で、同じ色の距離は一度しか計算しない。という高速化を施したけれど、count を sqrt の中にしてしまったので計算結果が変わってしまったという事です。

好ましくない画質の変わり方をしていたので、count を sqrt の外に出して元のアルゴリズムと同じ結果になるよう修正しました。

白が混ざる問題

稀に白いピクセルが混ざる事があります。

ImageMagick-6.6.7-6 以前	ImageMagick-6.6.7-7 以降

6.6.7-6 までは大丈夫で、6.6.7-7 から問題が発生するのを確認。
関連するコード。

      /*
        Identify the deepest node containing the pixel's color.
      */
      node_info=p->root;
      for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
      {
        id=ColorToNodeId(cube_info,&pixel,index);
        if (node_info->child[id] == (NodeInfo *) NULL)
          break;
        node_info=node_info->child[id];
      }
      node_info=node_info->parent; // ☆ これが余計な行
      /*
        Find closest color among siblings and their children.
      */
      p->target=pixel;
      p->distance=(MagickRealType) (4.0*(QuantumRange+1.0)*((MagickRealType)
        QuantumRange+1.0)+1.0);
      ClosestColor(image,p,node_info->parent);
      p->cache[i]=(ssize_t) p->color_number;
    }

Identify the deepest node containing the pixel's color.

node_info=p->root;

for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)

{

id=ColorToNodeId(cube_info,&pixel,index);

if (node_info->child[id] == (NodeInfo *) NULL)

break;

node_info=node_info->child[id];

}

node_info=node_info->parent; // ☆ これが余計な行

Find closest color among siblings and their children.

p->target=pixel;

p->distance=(MagickRealType) (4.0*(QuantumRange+1.0)*((MagickRealType)

QuantumRange+1.0)+1.0);

ClosestColor(image,p,node_info->parent);

p->cache[i]=(ssize_t) p->color_number;

}

色空間ツリーのイメージ図

コメントによると、色空間ツリーで自分の色が含まれるnodeの親兄弟までの範囲で似た色を探すのに、一つ親を余計に辿ってるので、叔父叔母の所を見ちゃってます。余計に親を辿る処理を消すと症状が収まりました。(*3)

コメント大切ですね！

ImageMagick 本家へフィードバック

不具合修正

まずは軽いジャブとして、軽い不具合修正２点を報告。

RiemersmaDither でツリーを辿る処理が間違ってたのを正した

http://www.imagemagick.org/discourse-server/viewtopic.php?f=2&t=23735

yoya:
  I found tree walking mistake for RiemersmaDither function.
  It's 2 times walking through parent until ClosestColor, so not siblings but uncle node.
  I think L1805 code must be removed. 
      node_info=node_info->parent;

magick:
  We can reproduce the problem you posted and applied your patch to ImageMagick 6.8.6-5 Beta available by sometime tomorrow. Thanks.

yoya:

I found tree walking mistake for RiemersmaDither function.

It's 2 times walking through parent until ClosestColor, so not siblings but uncle node.

I think L1805 code must be removed.

node_info=node_info->parent;

magick:

We can reproduce the problem you posted and applied your patch to ImageMagick 6.8.6-5 Beta available by sometime tomorrow. Thanks.

(訳)

yoya:
  RiemersmaDither 関数でツリーを辿る処理が間違ってるの見つけたよ。
  ClosestColor までに二回親を辿ってるので、従兄弟でなく叔父ノード。
  L1805 は消すべきじゃないかな。
      node_info=node_info->parent;

magick:
  投稿して貰った件の問題を再現したので、そのパッチを当てた ImageMagick 6.8.6-5 Beta を明日にでも出すよ。

yoya:

RiemersmaDither 関数でツリーを辿る処理が間違ってるの見つけたよ。

ClosestColor までに二回親を辿ってるので、従兄弟でなく叔父ノード。

L1805 は消すべきじゃないかな。

node_info=node_info->parent;

magick:

投稿して貰った件の問題を再現したので、そのパッチを当てた ImageMagick 6.8.6-5 Beta を明日にでも出すよ。

なんと、話の早い。

量子化エラーの計算処理を正した

http://www.imagemagick.org/discourse-server/viewtopic.php?f=2&t=23734

yoya:
  This change causes a color quality degradation of quantized images.
  correct code, I think.
      if (IsColorSimilar(image,p,p+count) == MagickFalse)
        break;
          (omit...)
      node_info->quantize_error+=count*sqrt((double) (error.red*error.red+
        error.green*error.green+error.blue*error.blue+
        error.opacity*error.opacity));

magick:
  We can reproduce the problem you posted and added your patch to ImageMagick 6.8.6-5 Beta available by sometime tomorrow. Thanks.

yoya:

This change causes a color quality degradation of quantized images.

correct code, I think.

if (IsColorSimilar(image,p,p+count) == MagickFalse)

break;

(omit...)

node_info->quantize_error+=count*sqrt((double) (error.red*error.red+

error.green*error.green+error.blue*error.blue+

error.opacity*error.opacity));

magick:

We can reproduce the problem you posted and added your patch to ImageMagick 6.8.6-5 Beta available by sometime tomorrow. Thanks.

(訳)

yoya:
  この変更だと画像の減色で品質が落ちますね。
  正しいコードはこうだと思います。
      if (IsColorSimilar(image,p,p+count) == MagickFalse)
        break;
          (omit...)
      node_info->quantize_error+=count*sqrt((double) (error.red*error.red+
        error.green*error.green+error.blue*error.blue+
        error.opacity*error.opacity));

magick:
  投稿して貰った件の問題を再現したので、そのパッチを当てた ImageMagick 6.8.6-5 Beta を明日にでも出すよ。

yoya:

この変更だと画像の減色で品質が落ちますね。

正しいコードはこうだと思います。

if (IsColorSimilar(image,p,p+count) == MagickFalse)

break;

(omit...)

node_info->quantize_error+=count*sqrt((double) (error.red*error.red+

error.green*error.green+error.blue*error.blue+

error.opacity*error.opacity));

magick:

投稿して貰った件の問題を再現したので、そのパッチを当てた ImageMagick 6.8.6-5 Beta を明日にでも出すよ。

6.8.6-5, 6.8.6-6

どちらも 6.8.6-5 で取り込まれました。

ImageMagick-6.8.6-5 差分＞ http://d.hatena.ne.jp/yoya/20130713/im

ですが、これには問題があって、マージされたコードの量子化エラーの計算を勝手にレビューした所、

node_info->quantize_error+=count*sqrt((double) (error.red*error.red+
  count*error.green*error.green+count*error.blue*error.blue+
  count*error.opacity*error.opacity));

node_info->quantize_error+=count*sqrt((double) (error.red*error.red+

count*error.green*error.green+count*error.blue*error.blue+

count*error.opacity*error.opacity));

というコードを確認。これはアカン。。(red から count* を移動してるけど、green, blue, opacity がそのままや。。)

http://www.imagemagick.org/discourse-server/viewtopic.php?f=2&t=23734 (続き)

yoya:
  Thank you for your quick response.
  At 6.8.6-5, this modified code has wrong calculation.
  In sqrt all count multiplication must be removed.

magick:
  We can reproduce the problem you posted and added your patch to ImageMagick 6.8.6-6 Beta available by sometime tomorrow. Thanks.

yoya:

Thank you for your quick response.

At 6.8.6-5, this modified code has wrong calculation.

In sqrt all count multiplication must be removed.

magick:

We can reproduce the problem you posted and added your patch to ImageMagick 6.8.6-6 Beta available by sometime tomorrow. Thanks.

(訳)

yoya:
  早速の対応ありがとう。
  でも、6.8.6-5 で修正コードは間違ってます。
  sqrt の中で count を掛け算してるのは全部消さないと。

magick:
  投稿して貰った件の問題を再現したので、そのパッチを当てた ImageMagick 6.8.6-6 Beta を明日にでも出すよ。

yoya:

早速の対応ありがとう。

でも、6.8.6-5 で修正コードは間違ってます。

sqrt の中で count を掛け算してるのは全部消さないと。

magick:

投稿して貰った件の問題を再現したので、そのパッチを当てた ImageMagick 6.8.6-6 Beta を明日にでも出すよ。

すぐに直して貰えました。

ImageMagick-6.8.6-6 差分＞ http://d.hatena.ne.jp/yoya/20130718/im

レビューは大切。

高速化の提案

幸い、エンジニアブログに解説記事があったので、それを単純に英訳して渡しました。

英語の説明(エンジニアブログの英訳) ＞ http://d.hatena.ne.jp/yoya/20130724/im

英訳は Google 翻訳、Nifty 翻訳、Excite翻訳で生成した英語のいいとこ取りをし、それでも残る不自然な文章を手で治すやり方です。(*4)

提案メッセージ (Proposal: Quantize Bulk Reduce Acceleration)
- http://www.imagemagick.org/discourse-server/viewtopic.php?f=2&t=24324

yoya:
  I would like to propose QBRA (Quantize Bulk Reduce Acceleration) configuration to enable rapid color reduction.
  The explanation of idea is here.
  - http://d.hatena.ne.jp/yoya/20130724/im
  With only a small code addition and without changing the fundamental algorithm we can get a performance boost.
  However image quality deteriorates slightly, disabled by default is good.

magick:
  Color reduction acceleration is an often requested enhancement. We'll add your patch to ImageMagick within a day or two. Thanks.

yoya:

I would like to propose QBRA (Quantize Bulk Reduce Acceleration) configuration to enable rapid color reduction.

The explanation of idea is here.

- http://d.hatena.ne.jp/yoya/20130724/im

With only a small code addition and without changing the fundamental algorithm we can get a performance boost.

However image quality deteriorates slightly, disabled by default is good.

magick:

Color reduction acceleration is an often requested enhancement. We'll add your patch to ImageMagick within a day or two. Thanks.

(訳)

yoya:
  減色処理を高速化する QBRA (Quantize Bulk Reduce Acceleration) Configuration を提案させて下さい。
  アイデアの説明は以下の所にあります。
  - http://d.hatena.ne.jp/yoya/20130724/im
  基本的なアルゴリズムを変更せずに、少しのコード追加で性能が上がります。
  しかしながら、画質はわずかに落ちるので、デフォルト無効が良いです。

magick:
  減色の高速化は結構リクエストあるんだよねー、両日中にパッチを取り込むねー。

yoya:

減色処理を高速化する QBRA (Quantize Bulk Reduce Acceleration) Configuration を提案させて下さい。

アイデアの説明は以下の所にあります。

- http://d.hatena.ne.jp/yoya/20130724/im

基本的なアルゴリズムを変更せずに、少しのコード追加で性能が上がります。

しかしながら、画質はわずかに落ちるので、デフォルト無効が良いです。

magick:

減色の高速化は結構リクエストあるんだよねー、両日中にパッチを取り込むねー。

遠慮がちに configure で明示的に enable 指定しないとデフォルトでは無効になる方式で提案したのですが、切り替えなしで僕のコードが取り入れられました。これは嬉しい。 ~~リリースされた11月1日は自分の誕生日だったので更に嬉しい＼(^o^)／~~

ImageMagick-6.8.7-4 差分＞ http://d.hatena.ne.jp/yoya/20131101/im

尚、このバージョンは YoyaMagick の高速化と別に、OpenCL のガチな対応が入っていて、ImageMagick にとって高速化のエポックメイキング的な更新になっていると思います。
あ、ボクの更新というより OpenCL の方がです。

最後に

俺達の戦いはまだ始まったばかりだ！というノリで今後も ImageMagick を追いかけて行こうと思います。

以上です。最後までお読み頂き、ありがとうございました。

明日は JavaScript で色々とマニアックなライブラリを公開してる imaya さんです。お楽しみに！

*1: Debian 6 squeeze は zlib 1.2.3 で都合が良いですが、Debian 7 wheezy は zlib 1.2.7 なので困ったりします

*2: 6.4.0-11 は一見綺麗ですが、デフォルトでディザが無効になる不具合があって、グラデを真面目に扱ってないだけです。ただの階調表示です。

*3: 黒は色空間ツリーの頂点なので、その更に上のノードを漁ったつもりで処理するのは結構怖い事が起こってそうです。

*4: 英語ネイティブの同僚から、機械翻訳のように見えて何故か普通に読める不思議な文章という評価を頂きました。^^;