減色アルゴリズム

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

この文書は、ImageMagick が画像の減色をどう行うかを説明します。以下を完全に理解するには、基本的な画像処理技術と、木（tree）データ構造とその用語の知識が必要です。

アルゴリズムの説明

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

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

アルゴリズムはこの領域を、各ノードがその領域内の立方体を表す木にマッピングします。以下の議論では、これらの立方体は 2 つの対角頂点の座標で定義されます: RGB 空間で原点に最も近い頂点と、原点から最も遠い頂点です。

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

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

1. 分類（Classification）
2. 削減（Reduction）
3. 割り当て（Assignment）

分類

分類は画像のカラー記述木を構築します。削減は、表す色数が最大でも出力画像で望む色数になるまで木を縮約します。割り当ては、出力画像のカラーマップを定義し、縮約された木での再分類で各ピクセルの色を設定します。目標は元の色と量子化された色の数値的な差を最小化することです。量子化誤差について詳しくは「減色誤差の測定」を参照してください。

分類は、各取りうる入力色を葉で表せる十分な深さのカラー記述木の初期化から始まります。しかし、現実的な Cmax の値では、分類フェーズで完全に形成されたカラー記述木を生成するのは非現実的です。入力画像の色成分が k ビット精度に量子化され Cmax = 2^k-1 の場合、各取りうる入力色を葉で表せるよう、木はルートノードの下に k レベルを必要とします。これは木の総ノード数のため過大になります:

                   = 8

この深さの木は一般に、最速の計算速度と最小のメモリで元画像の最良の表現を可能にします。ただし、既定の深さは一部の画像には不適切です。そのため、呼び出し側は特定の木の深さを要求できます。

入力画像の各ピクセルについて、分類はカラー記述木のルートから下方に走査します。木の各レベルで、そのピクセルの色を含む RGB 空間内の立方体を表す単一のノードを識別します。そして各ノードについて次のデータを更新します:

n1

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

n2

木のより低い深さのノードで色が表されないピクセルの数。初期状態では、木の葉を除くすべてのノードで n2=0。

Sr,Sg,Sb

より低い深さで分類されないすべてのピクセルの赤・緑・青成分値の和。これらの和と n2 の組み合わせが、最終的にこのノードが表すピクセル集合の平均色を特徴づける。

E

ノード内に含まれる各ピクセルとノードの中心との間の RGB 空間での距離の 2 乗。これはノードの量子化誤差を表す。

削減

削減は、n2 > 0 のノード数が出力画像で許される最大色数以下になるまで、木を繰り返し剪定します。木を巡る任意の反復で、E 値が最小のノードを剪定対象として選び、その色統計を上方にマージします。剪定しきい値 Ep を使い、次のようにノード選択を制御します:

Ep = 0
while （n2 > 0 のノード数）> 必要な最大色数
   E <= Ep のすべてのノードを剪定する
   Ep を残りのノードの最小 E に設定する

これにより、2 つのノードをマージする際の量子化誤差を最小化する効果があります。

剪定するノードに子孫がある場合、剪定手続きは葉から上方へ木を剪定するために自身を再帰的に呼び出します。剪定されるノードの n2, Sr, Sg, Sb の値は、常にそのノードの親の対応データに加算されます。これにより、後の平均化のために剪定されたノードの色特性が保持されます。

各ノードについて、そのノードがそれらのピクセルの色を含む RGB 空間内の最小体積を表す n2 個のピクセルが存在します。n2 > 0 のとき、そのノードは出力画像で一意の色を定義します。削減の開始時、入力画像に存在する色を表す木の葉を除き、すべてのノードで n2 = 0 です。

もう 1 つのピクセル数 n1 は、ノードが表す立方体積内の総色数を示します。これには、木のより低いレベルのノードで色が定義されるべき n1 − n2 個のピクセルが含まれます。

割り当て

割り当ては、剪定された木から出力画像を生成します。出力画像は 2 つの部分から成ります:

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

まず、割り当てフェーズは、剪定されたカラー記述木を 1 回走査して画像のカラーマップを確立します。n2 > 0 の各ノードについて、Sr, Sg, Sb を n2 で割ります。これにより、このノードより低く分類されないすべてのピクセルの平均色が生成されます。これらの各色がカラーマップのエントリになります。

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

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

減色誤差の測定

画像によって、減色誤差は明白なこともあれば見えないこともあります。空間周波数の高い画像（髪や草など）は、大きく滑らかに陰影づけられた領域を持つ画像（顔など）よりはるかに誤差が目立ちにくくなります。これは、減色処理で導入される高周波の輪郭エッジが、画像内の高周波でマスクされるためです。

元画像と減色画像の差（総減色誤差）を測定するため、ImageMagick は画像のすべてのピクセルにわたって、各元ピクセル値とその減色値との間の RGB 空間での距離の 2 乗を合計します。ImageMagick は、ピクセルあたり平均誤差、正規化平均誤差、正規化最大誤差を含むいくつかの誤差測定を表示します。

正規化誤差測定は画像の比較に使えます。一般に、平均誤差が 0 に近いほど、量子化画像は元画像に似ています。理想的には、量子化品質の最終的な判断者は人間の目なので、誤差は知覚ベースであるべきです。

これらの誤差は、magick コマンドラインで -colors と -verbose オプションが指定されたときに測定・表示されます: