ImageMagick 改造入門 (その弐) 減色処理前編

2012/09/21

よや

こんにちは。クライアント基盤チームのよやです。

アバター等を表示する為に PNG や JPEG の画像を元に GIF アニメーションを生成する事がよくありますが、GIF は 256色までしか扱えない為、元画像が数万といった単位で色を使っていると減色処理に大変時間がかかります。そこで、ImageMagick の減色処理を改造して高速化した事例をご紹介します。

尚、一度に読む分量ではまとめ切れない為、前編と後編に分けました。前編は減色処理、後編はその改造について説明します。

プログラム構成では上の図の magick/quantize.c が減色処理に相当します。

まず、減色処理の一般的な話から始めます。

減色の利点

Web で見かける画像ファイルの多くは、1つのpixel(描画の最小単位)に対して、Red, Green, Blue が各々8bits で計 24bits(= 3bytes) 、透明度の Alpha 値を含めると更に 8bits 足して計 32bits(= 4bytes)の色情報を持ちます。それを素直に PNG 形式で表すと以下のようになります。

同じ色が多い(=使っている色数が少ない)場合は、描画に必要な色を先頭にまとめるパレット形式を用いるとサイズ的に有利です。例えば256色以下であれば、1pixel 辺り 8bits(= 1byte)で 1つの色を表現できるので、十分大きな画像であれば 1/3 近くまでサイズが減る事があります。

色を大量に使っている画像でも、色数を減らす事でパレット形式に持ち込めれば、画像ファイルのデータ量を大幅に減らせます。また画像ファイルは通常何かしらの圧縮がなされ、一般に色数が少ない(=パターンが少ない)ほど圧縮が効く為、画質に問題がない範囲で出来るだけ色数を減らす事は画像ファイルサイズや、それをユーザに運ぶネットワーク転送時間に有利に働きます。

減色の原理

減色は色のリストラです。リストラされた色の分は、残った色で頑張って補います。

グラデーションの画像を例にとります。ImageMagick の convert コマンドを用いて、黒から緑まで段階的に64色使った画像を作ります。

% convert -size 64x64 gradient:green-blue -rotate 90 grad-g2b.png

1	% convert -size 64x64 gradient:green-blue -rotate 90 grad-g2b.png

多少無理がありますが、三色を使って以下のようにも表現出来ます。

% convert -colors 3 grad-g2b.png grad-g2b-3.png

1	% convert -colors 3 grad-g2b.png grad-g2b-3.png

↓ 真ん中を拡大↓

複数の色を適切な割合で混ぜ合わせて消えたはずの色を表現しています。この手法はディザリングと呼びます。
今回は緑と黒という極端に違う色をたった 3色で表現した為に見た目が悪いですが、128～256色も残せば、大抵は似た色が存在するので、これよりまともな画質が期待できます。

RGB色空間

画像が使っている色(パレット)を Red, Green, Blue を軸にとった 3次元の色空間にマッピングすると、実際にどんな色を使っているのか一目で分かります。

3Ｄカラーマップ表示ツール
- http://d.hatena.ne.jp/yoya/20080927
色の分布を3Dで表示するJavaScriptをThree.jsで作った
- http://flspz.blogspot.jp/2012/08/3dplotcolor.html

PNG のアバター画像をパレット形式に変換して、各々、画像と色パレットRGB空間を横に並べます。

% convert avatar.png png8:avatar-palette.png

1	% convert avatar.png png8:avatar-palette.png

avatar.png (色数:16259)

avatar-palette.gif (色数:256)

おおよそ変わりの無い画像に見えますが、パレット形式PNG画像の色空間を見ると、使っている色が大幅に減っているのが分かります。

% ls -ltr avatar.png  avatar-palette.png
-rw-r--r-- 1 yoya yoya 100517 2012-08-10 04:44 avatar.png
-rw-r--r-- 1 yoya yoya 36102 2012-09-21 10:06 avatar-palette.png

% ls -ltr avatar.png avatar-palette.png

-rw-r--r-- 1 yoya yoya 100517 2012-08-10 04:44 avatar.png

-rw-r--r-- 1 yoya yoya 36102 2012-09-21 10:06 avatar-palette.png

画像ファイルサイズも激減します。(100,517 bytes → 36,102 bytes)

ただ、この色空間を見ると、緑や赤紫が減り過ぎて直感的に怪しいです。ピクセル毎の差分の絶対値を取って確認しましょう。

差分抽出ツール: http://d.hatena.ne.jp/yoya/20120712/php

差分を強調しているので実際より極端な表示ですが、色相的に緑と赤紫が多く書き換えられている事が分かります。

減色アルゴリズム

元の画像と見た目をなるべく変えずに減色する目的で、様々な色決定アルゴリズムが存在します。

均等量子化法

RGB 色空間の立方体を均等に分割して、各立方体毎に含まれる色を 1つの色に代表させます。

各格子毎に、キリの良い一点に収束する様子のアニメーション。

この減色アルゴリズムは非常に単純で、PHP だと20行程度で実装出来ます。(上の図のように 8x8x8 分割にすると 512 になり、256 色に収まらないので、青は 4 分割)

<?php

$imgdata = file_get_contents($argv[1]);
$output_file = $argv[2];
$im1 = imagecreatefromstring($imgdata);

$width  = imagesx($im1);
$height = imagesy($im1);

$im2 = imagecreatetruecolor($width, $height);

for ($y = 0 ; $y < $height ; $y++) {
    for ($x = 0 ; $x < $width ; $x++) {
        $i1 = imagecolorat($im1, $x, $y);
        $rgba1 = imagecolorsforindex($im1, $i1);
        $red   = $rgba1['red']   & -(0x100/8); // quantize 8
        $green = $rgba1['green'] & -(0x100/8); // quantize 8
        $blue  = $rgba1['blue']  & -(0x100/4); // quantize 4
        $color = imagecolorallocate($im2, $red, $green, $blue);
        imagesetpixel($im2, $x, $y, $color);
    }
}

imagegif($im2, $output_file);

<?php

$imgdata = file_get_contents($argv[1]);

$output_file = $argv[2];

$im1 = imagecreatefromstring($imgdata);

$width = imagesx($im1);

$height = imagesy($im1);

$im2 = imagecreatetruecolor($width, $height);

for ($y = 0 ; $y < $height ; $y++) {

for ($x = 0 ; $x < $width ; $x++) {

$i1 = imagecolorat($im1, $x, $y);

$rgba1 = imagecolorsforindex($im1, $i1);

$red = $rgba1['red'] & -(0x100/8); // quantize 8

$green = $rgba1['green'] & -(0x100/8); // quantize 8

$blue = $rgba1['blue'] & -(0x100/4); // quantize 4

$color = imagecolorallocate($im2, $red, $green, $blue);

imagesetpixel($im2, $x, $y, $color);

}

imagegif($im2, $output_file);

実行します。

% php bitmap_quantize.php avatar.png avatar-quantize.gif

1	% php bitmap_quantize.php avatar.png avatar-quantize.gif

処理結果

顔の辺りをドット単位で拡大してみます。

大抵の画像で画質がかなり劣化するので、この方法は実際にはあまり使われません。

他、メジャーな方法

中央値分割法(median cut)、頻度均等化法(population equalize)が実用的でかつメジャーだと思われますが、これらは説明図を描くのが難しいので、すみません、端折らせて下さい。

分かり易い説明のある URL にリンクを張ります。ご参考までに。

24bit → 8bit 減色
- http://koujinz.cocolog-nifty.com/blog/2009/04/24bit-8bit-a879.html
メディアンカット法による画像の減色
- http://www.spicysoft.com/spicylab/blog/?itemid=1073

ImageMagick の減色処理解説

ImageMagick の減色処理の概要は公式サイトにあります。

http://www.imagemagick.org/www/quantize.html

ImageMagick の減色処理は 3つのフェイズに分かれます。

(1) 色空間の分割と各立方体に含まれる色の量子化誤差(ばらつき具合)の算出
- (1.1) 色空間の立方体を再帰的に 8分割

(1.2) 立方体に含まれる各色の立方体中央からの距離を合算

該当するコード: imagemagick-6.6.0.4/magick/quantize.c (ClassifyImageColors)

static MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
  const Image *image,ExceptionInfo *exception)
＜略＞
        if (node_info->child[id] == (NodeInfo *) NULL)
          {
            /*
              Set colors of new node to contain pixel.
            */
            node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
            if (node_info->child[id] == (NodeInfo *) NULL)
              (void) ThrowMagickException(exception,GetMagickModule(),
                ResourceLimitError,"MemoryAllocationFailed","`%s'",
                image->filename);
            if (level == MaxTreeDepth)
              cube_info->colors++;
          }
        /*
          Approximate the quantization error represented by this node.
        */
        node_info=node_info->child[id];
        error.red=QuantumScale*(pixel.red-mid.red);
        error.green=QuantumScale*(pixel.green-mid.green);
        error.blue=QuantumScale*(pixel.blue-mid.blue);
        if (cube_info->associate_alpha != MagickFalse)
          error.opacity=QuantumScale*(pixel.opacity-mid.opacity);
        node_info->quantize_error+=sqrt((double) (count*error.red*error.red+
          count*error.green*error.green+count*error.blue*error.blue+
          count*error.opacity*error.opacity));
        cube_info->root->quantize_error+=node_info->quantize_error;
        index--;

static MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,

const Image *image,ExceptionInfo *exception)

＜略＞

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

{

Set colors of new node to contain pixel.

node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);

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

(void) ThrowMagickException(exception,GetMagickModule(),

ResourceLimitError,"MemoryAllocationFailed","`%s'",

image->filename);

if (level == MaxTreeDepth)

cube_info->colors++;

}

Approximate the quantization error represented by this node.

node_info=node_info->child[id];

error.red=QuantumScale*(pixel.red-mid.red);

error.green=QuantumScale*(pixel.green-mid.green);

error.blue=QuantumScale*(pixel.blue-mid.blue);

if (cube_info->associate_alpha != MagickFalse)

error.opacity=QuantumScale*(pixel.opacity-mid.opacity);

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

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

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

cube_info->root->quantize_error+=node_info->quantize_error;

index--;

(2) 量子化誤差(quantize_error)の小さな立方体を、それを含む一回り大きな立方体に吸収する
- (2.1) 量子化誤差の小さい立方体を探す

(2.2) ひとつ親の立方体に吸収する

該当するコード: imagemagick-6.6.0.4/magick/quantize.c (ReduceImageColors)

static void ReduceImageColors(const Image *image,CubeInfo *cube_info)
＜略＞
  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);
    offset=(MagickOffsetType) span-cube_info->colors;
    proceed=SetImageProgress(image,ReduceImageTag,offset,span-
      cube_info->maximum_colors+1);
    if (proceed == MagickFalse)
      break;
  }

static void ReduceImageColors(const Image *image,CubeInfo *cube_info)

＜略＞

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

offset=(MagickOffsetType) span-cube_info->colors;

proceed=SetImageProgress(image,ReduceImageTag,offset,span-

cube_info->maximum_colors+1);

if (proceed == MagickFalse)

break;

}

(3) 削除された立方体に含まれていた色を残った立方体の色に割り当て直す。
- (3.1) 消した立方体の色を上位の立方体の色として扱う。

(3.2) その立方体に子供がいれば、子供の中で近い色に再割当する

該当するコード: imagemagick-6.6.0.4/magick/quantize.c (AssignImageColors)

static MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)
＜略＞
          ClosestColor(image,cube_info,node_info->parent);
          index=cube_info->color_number;
          for (i=0; i < (long) count; i++)
          {
            if (image->storage_class == PseudoClass)
              indexes[x+i]=(IndexPacket) index;
            if (cube_info->quantize_info->measure_error == MagickFalse)
              {
                q->red=image->colormap[index].red;
                q->green=image->colormap[index].green;
                q->blue=image->colormap[index].blue;
                if (cube_info->associate_alpha != MagickFalse)
                  q->opacity=image->colormap[index].opacity;
              }
            q++;
          }

static MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)

＜略＞

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

index=cube_info->color_number;

for (i=0; i < (long) count; i++)

{

if (image->storage_class == PseudoClass)

indexes[x+i]=(IndexPacket) index;

if (cube_info->quantize_info->measure_error == MagickFalse)

{

q->red=image->colormap[index].red;

q->green=image->colormap[index].green;

q->blue=image->colormap[index].blue;

if (cube_info->associate_alpha != MagickFalse)

q->opacity=image->colormap[index].opacity;

}

q++;

}

ImageMagick の色空間分割動画

減色が進むにつれ、色空間の分割が荒くなる様子を動画にしました。
いずれも 1色まで減色していますが、通常はその途中(128色や256色まで減った所)で止めます。

4色の画像を 1色に減色

赤青緑黄の 4色でバラバラになっている立方体が、一つにまとまる様子です。

クリノッペのかけっこ写真を 1色に減色

元画像に純粋な青(RGB:#0000FF)が無いので、その辺りの立方体が欠けています。

まとめ

RGB 色空間を小さな立方体に再帰的に分割して 8分木ツリー構造で保持
ツリーの深い方から色のばらつきが小さい順に立方体を削除
削除した立方体の色はツリー構造的に近くて深い方の立方体の色に書き替え

備考

透明度つきの画像では RGBA の 4つの軸が出来るので、4次元のハイパーキューブを 16 進木で表現します。4次元の図はさすがに分かり難いので、今回は RGB の3次元を例にしました。
量子化誤差(quantization error)は本来、アナログ信号をデジタル値にサンプリングする際の誤差を表す言葉ですが、ImageMagick の NodeInfo 構造体にある quantize_error メンバ変数は分割した色空間内のパレット色のばらつき具合を表しているので、それに合わせました。
色空間を分割する際に、立方体が細かくなり過ぎないよう深さを抑えたり、色を割り当て直す際にも近い色を効率的に探す処理など、説明を省略した面白い部分が結構あります。
ディザリングの説明で気付くと思いますが、削除対象の色を別の色に書き替える際に、一つの色になるとは限りません。ですので、パレットからパレットへの単純な写像ではなく、ビットマップのピクセル毎に色の更新を行います。
RGB 色空間のアニメーション作成手順は、ImageMagick の減色処理に printf を仕込み、その文字列を PHP で受け取って OpenGL extension を通し X11 で描画、スクリーンから RGB 配列に落として GD extension で PNG の静止画に保存。最後に ffmpeg で MP4 動画に変換。簡単ですね！

最後に

さて、ここまでが前置きになります。

次回、ImageMagick 減色処理の改造についてお話します。それでは！