適応的空間分割を用いた色数削減

アルゴリズムの説明 • 色数削減誤差の測定

このドキュメントでは、ImageMagickが画像の色数削減を実行する方法について説明します。以下の内容を完全に理解するには、基本的な画像処理技術とツリーデータ構造および用語に関する知識が必要です。

アルゴリズムの説明

色割り当ての目的で、画像はn個のピクセルの集合であり、各ピクセルはRGB空間上の点です。RGB空間は3次元ベクトル空間であり、各ピクセルp(i)は、赤、緑、青の座標の順序付けられた3つ組(r(i), g(i), b(i))で定義されます。

各原色成分(赤、緑、または青)は、0から最大値Cmaxまで線形に変化する強度を表し、Cmaxはその色の完全な彩度に対応します。色割り当ては、(0, 0, 0)と(Cmax, Cmax, Cmax)を反対の頂点とするRGB空間内の立方体からなる領域上で定義されます。ImageMagickではCmax=255が必要です。

このアルゴリズムは、この領域をツリーにマッピングします。ツリーの各ノードは、その領域内の立方体を表します。以降の説明では、これらの立方体は、2つの反対の頂点の座標によって定義されます。RGB空間で原点に最も近い頂点と原点から最も遠い頂点です。

ツリーのルートノードは、(0,0,0)から(Cmax, Cmax, Cmax)までの領域全体を表します。ツリーの下位レベルは、1つのノードの立方体を8つの等しいサイズの小さな立方体に分割することで生成されます。これは、各辺の中点を通る平面で親立方体を二分することに対応します。

基本アルゴリズムは3つのフェーズで動作します。

1. 分類
2. 削減
3. 割り当て

分類

分類は、画像の色記述ツリーを構築します。削減は、ツリーが表すノード数が、出力画像で必要な色の数以下になるまでツリーを圧縮します。割り当ては、出力画像の色マップを定義し、削減されたツリーでの再分類によって各ピクセルの色を設定します。私たちの目標は、元のカラーと量子化されたカラー間の数値的な差異を最小限に抑えることです。 量子化誤差の詳細については、色数削減誤差の測定を参照してください。

分類は、可能なすべての入力色を葉に表現するのに十分な深さの色記述ツリーを初期化することから始まります。しかし、現実的なCmaxの値に対して、分類段階で完全に形成された色記述ツリーを生成することは非現実的です。入力画像の色成分がkビット精度に量子化され、Cmax = 2^k-1である場合、ツリーはルートノードの下にkレベル必要となり、葉に可能なすべての入力色を表すことができます。これは、ツリーのノードの総数が

total nodes = 1+Sum(8^i), i=1,k

For k=8,
nodes = 1 + (8^1+8^2+....+8^8)
      = 1 + 8(8^8 - 1)/(8 - 1)
      = 19,173,961 

したがって、完全に埋まったツリーを構築するのを避けるため、ImageMagickは

1. 必要な場合にのみノードのデータ構造を初期化します。
2. 出力画像で必要な色の数（現在、Cmaxの2を底とする対数）の関数として、ツリーの最大深さを選択します。

For Cmax=255,
maximum tree depth = log2(256)
                   = 8 

この深さのツリーは、一般的に、最速の計算速度と最小のメモリ量でソース画像の最適な表現を可能にします。ただし、デフォルトの深さは一部の画像には不適切です。そのため、呼び出し元は特定のツリーの深さを要求できます。

入力画像の各ピクセルについて、分類は色記述ツリーのルートから下方向にスキャンします。ツリーの各レベルで、ピクセルの色を含むRGB空間内の立方体を表す単一のノードを特定します。各ノードについて、以下のデータを更新します。

n1

このノードが表すRGB立方体に色が含まれるピクセルの数。

n2

ツリーの下位レベルのノードに色が表現されていないピクセルの数。最初は、ツリーの葉を除くすべてのノードでn2=0です。

Sr、Sg、Sb

下位レベルで分類されていないすべてのピクセルの赤、緑、青成分値の合計。これらの合計とn2の組み合わせにより、最終的にこのノードによって表されるピクセル集合の平均色が特徴付けられます。

E

ノードに含まれる各ピクセルとそのノードの中心との間のRGB空間における距離の二乗。これは、ノードの量子化誤差を表します。

削減

削減は、n2 > 0であるノードの数が、出力画像で許可される色の最大数以下になるまで、ツリーを繰り返し刈り込みます。ツリーに対する任意の反復では、E値が刈り込みのために最小のノードを選択し、その色統計を上方向にマージします。以下のとおり、ノードの選択を制御するために刈り込みしきい値Epを使用します。

Ep = 0
while number of nodes with (n2 > 0) > required maximum number of colors
   prune all nodes such that E <= Ep
   Set Ep  to minimum E in remaining nodes 

これにより、2つのノードをマージする際の量子化誤差を最小限に抑えることができます。

刈り込まれるノードに子ノードがある場合、刈り込み手順は再帰的に自身を呼び出して、葉から上方向にツリーを刈り込みます。刈り込まれるノードのn2、Sr、Sg、Sbの値は、常にそのノードの親の対応するデータに追加されます。これにより、後で平均化するために、刈り込まれたノードの色特性が保持されます。

各ノードについて、n2個のピクセルは、そのノードがそれらのピクセルの色を含むRGB空間における最小のボリュームを表すものになります。n2 > 0の場合、ノードは出力画像の色を一意に定義します。削減の開始時では、ツリーの葉（入力画像に存在する色を表す）を除くすべてのノードでn2 = 0です。

もう一方のピクセル数n1は、ノードが表す立方体ボリューム内の色の総数を示します。これには、ツリーの下位レベルのノードによって定義されるべきn1 - n2個のピクセルが含まれます。

割り当て

割り当ては、刈り込まれたツリーから出力画像を生成します。出力画像は2つの部分で構成されます。

1. 出力画像に存在する各色の色記述（RGB 3つ組）の配列であるカラーマップ。
2. 各ピクセルをカラーマップ配列へのインデックスとして表すピクセル配列。

まず、割り当てフェーズでは、刈り込まれた色記述ツリーを1回スキャンして、画像のカラーマップを作成します。n2 > 0の各ノードについて、Sr、Sg、Sbをn2で除算します。これにより、このノードよりも低いレベルで分類されないすべてのピクセルの平均色が生成されます。これらの各色は、カラーマップのエントリになります。

最後に、割り当てフェーズでは、刈り込まれたツリー内の各ピクセルを再分類して、ピクセルの色を含む最深のノードを特定します。ピクセル配列内のピクセルの値は、カラーマップ内のこのノードの平均色のインデックスになります。

経験的証拠から、YUVやYIQなどの色空間における距離は、RGB空間における距離よりも知覚的な色の違いに密接に対応することが示唆されています。これらの色空間は、画像の色数を削減する際に、より良い結果をもたらす可能性があります。ここでは、各ピクセルが代替色空間上の点である点を除いて、アルゴリズムは説明されているとおりです。便宜上、色成分は0から最大値Cmaxの範囲に正規化されます。その後、説明されているとおりに色数削減を進めることができます。

色数削減誤差の測定

画像によっては、色数削減誤差は明らかである場合もあれば、目に見えない場合もあります。高空間周波数（髪や草など）の画像は、大きな滑らかにシェーディングされた領域（顔など）の画像よりも、誤差がはるかに少なく表示されます。これは、色数削減プロセスによって導入された高周波数の輪郭エッジが、画像の高周波数によってマスクされるためです。

ImageMagickは、元の画像と色数削減された画像の差（合計色数削減誤差）を測定するために、画像内のすべてのピクセルについて、各元のピクセル値とその色数削減された値との間のRGB空間における距離の二乗を合計します。ImageMagickは、ピクセルあたりの平均誤差、正規化平均誤差、正規化最大誤差など、いくつかの誤差測定値を出力します。

正規化誤差測定値は、画像の比較に使用できます。一般に、平均誤差が0に近いほど、量子化された画像がソース画像に似ていることを示します。理想的には、人間の目は量子化品質の最終的な判断者であるため、誤差は知覚に基づいている必要があります。

これらの誤差は、-colorsオプションと-verboseオプションをmagickコマンドラインで指定した場合に測定および出力されます。