減色アルゴリズムの仕組み - メディアンカットと k-means による色数削減
減色 (カラー量子化) とは何か
減色 (Color Quantization) は、画像に含まれる色数を削減する処理です。24 ビットカラー画像は最大 1677 万色を表現できますが、GIF 形式は 256 色、一部のディスプレイは限られたパレットしか表示できません。減色アルゴリズムは、視覚的な品質を可能な限り維持しながら、使用する色数を指定された数に削減します。
なぜ減色が必要か:
減色が必要な場面は多岐にわたります。GIF アニメーション作成 (最大 256 色)、レトロゲーム風のピクセルアート生成、印刷時の色数制限 (特色印刷)、データ圧縮 (インデックスカラーによるファイルサイズ削減)、Web パフォーマンス最適化 (PNG-8 の活用) などです。また、画像のドミナントカラー抽出やカラーパレット生成にも同じアルゴリズムが応用されます。
減色の基本プロセス:
減色は 2 つのステップで構成されます。第 1 に、代表色 (パレット) の選択 - 元画像の色分布を分析し、最適な N 色を決定します。第 2 に、各ピクセルの割り当て - 元画像の各ピクセルを最も近い代表色に置き換えます。パレット選択の品質が最終的な画像品質を大きく左右します。
色空間の選択:
減色処理は RGB 空間で行うのが一般的ですが、人間の知覚に基づいた色空間 (CIELAB、CIELUV) を使用すると、知覚的により自然な結果が得られます。RGB 空間ではユークリッド距離が知覚的な色差と一致しないため、緑の領域が過剰に細分化される傾向があります。CIELAB 空間での ΔE (色差) は人間の知覚により近い距離尺度を提供します。
メディアンカット法 - 色空間の再帰的分割
メディアンカット法 (Median Cut) は Paul Heckbert が 1982 年に提案した減色アルゴリズムで、RGB 色空間を再帰的に分割して代表色を決定します。シンプルながら高品質な結果を生み、GIF エンコーダや画像編集ソフトで広く採用されています。
アルゴリズムの手順:
1. 画像の全ピクセルを RGB 色空間の 1 つのボックス (直方体) に格納します。2. ボックスの最も長い辺 (R, G, B のうち範囲が最大の軸) を特定します。3. その軸に沿ってピクセルをソートし、中央値 (メディアン) で 2 つのボックスに分割します。4. 目標の色数 N に達するまで、最大のボックスを繰り返し分割します。5. 各ボックス内のピクセルの平均色を代表色とします。
分割基準のバリエーション:
基本的なメディアンカットは「最も長い辺」で分割しますが、改良版では「ピクセル数が最も多いボックス」や「色の分散が最も大きいボックス」を優先的に分割します。分散ベースの分割は、色の多様性が高い領域をより細かく分割するため、視覚的に重要な色の区別を保持しやすくなります。
計算量と特性:
N 色への減色の計算量は O(P × log N) です (P はピクセル数)。メディアンカットの利点は、ピクセル数に基づく分割により、画像内で頻出する色に多くのパレットエントリを割り当てる点です。広い面積を占める色が正確に表現されるため、全体的な色再現性が高くなります。一方、少数ピクセルしか持たない鮮やかな色 (ハイライト、アクセントカラー) が失われやすいという欠点があります。
Python 実装のポイント:
NumPy を使用した効率的な実装では、ピクセルデータを (N, 3) の配列として扱い、np.partition() で O(N) のメディアン分割を実現します。再帰的な分割は深さ log2(N) で完了するため、256 色パレットの生成は 8 回の分割で済みます。
k-means 法による最適パレット生成
k-means クラスタリングは、色空間内のピクセルを k 個のクラスタに分割し、各クラスタの重心を代表色とする手法です。反復的な最適化により、量子化誤差 (各ピクセルと代表色の距離の総和) を最小化する最適なパレットを生成します。
アルゴリズムの手順:
1. k 個の初期代表色をランダムに選択 (または k-means++ で賢く初期化)。2. 各ピクセルを最も近い代表色のクラスタに割り当て。3. 各クラスタの重心 (平均色) を新しい代表色として更新。4. 割り当てが変化しなくなるまで 2-3 を繰り返し。通常 10-30 回の反復で収束します。
k-means++ 初期化:
ランダム初期化は局所最適解に陥りやすいため、k-means++ が推奨されます。最初の中心をランダムに選び、以降は既存の中心から遠いピクセルを高確率で選択します。これにより初期中心が色空間内に均等に分散し、収束が速く品質も向上します。scikit-learn の KMeans(n_clusters=k, init='k-means++') がこの実装を提供しています。
メディアンカットとの比較:
k-means はメディアンカットより高品質な結果を生みますが、計算コストが高くなります。メディアンカットが O(P × log N) なのに対し、k-means は O(P × k × I) です (I は反復回数)。256 色パレットの場合、k-means は数秒から数十秒を要しますが、メディアンカットは 1 秒未満で完了します。品質重視なら k-means、速度重視ならメディアンカットを選択します。
Mini-Batch k-means:
大きな画像での計算時間を削減するため、Mini-Batch k-means が有効です。全ピクセルではなくランダムサンプル (例: 10,000 ピクセル) で各反復を実行します。品質の低下は最小限で、処理速度は 10-100 倍向上します。scikit-learn の MiniBatchKMeans が利用可能です。
オクツリー法とその他の減色アルゴリズム
メディアンカットと k-means 以外にも、様々な減色アルゴリズムが存在します。用途や制約に応じて最適な手法を選択することが重要です。
オクツリー法 (Octree Quantization):
オクツリー法は RGB 色空間を八分木 (Octree) で階層的に分割します。各ピクセルの RGB 値をビット単位で分解し、木構造に挿入します。8 ビットの RGB では最大深さ 8 の木が構築されます。目標色数に達するまで、葉ノードが最も少ない枝を統合 (マージ) していきます。メモリ効率が良く、ストリーミング処理 (1 パス) が可能な点が利点です。
一様量子化 (Uniform Quantization):
最も単純な手法で、各色チャネルを均等に分割します。例えば R を 8 段階、G を 8 段階、B を 4 段階に分割すると 256 色になります。計算は極めて高速ですが、画像の色分布を考慮しないため品質は低くなります。人間の視覚が緑に敏感なことを利用し、G チャネルにより多くのビットを割り当てる (例: R:3, G:3, B:2 = 256 色) 工夫もあります。
NeuQuant (Neural Network Quantization):
Kohonen の自己組織化マップ (SOM) に基づく手法で、ニューラルネットワークが色空間内で代表色を学習します。学習率とネットワークサイズを調整することで、品質と速度のトレードオフを制御できます。GIF エンコーダの gifsicle で採用されており、特にグラデーションを含む画像で良好な結果を示します。
Wu の最適量子化:
Xiaolin Wu (1991) が提案した手法で、3D ヒストグラムの分散を最小化するように色空間を分割します。メディアンカットの改良版と位置づけられ、分割基準に分散を使用することで、視覚的に重要な色の区別をより良く保持します。計算量はメディアンカットと同程度ですが、品質は k-means に近い結果が得られます。
ディザリングとの組み合わせ - 視覚品質の向上
減色後の画像は、色数の制限により色の階調が失われ、バンディング (等高線状の縞模様) が発生することがあります。ディザリングを組み合わせることで、限られた色数でも滑らかなグラデーションを知覚的に再現できます。
なぜディザリングが必要か:
256 色に減色した画像では、元画像のグラデーション部分で急激な色の変化 (バンディング) が目立ちます。ディザリングは、隣接ピクセルに異なる色を配置することで、人間の目が空間的に平均化して中間色を知覚する効果を利用します。印刷のハーフトーンと同じ原理です。
Floyd-Steinberg ディザリング:
最も広く使用される誤差拡散ディザリングです。各ピクセルの量子化誤差 (元の色と代表色の差) を周囲のピクセルに分配します。分配比率は右 7/16、左下 3/16、下 5/16、右下 1/16 です。ラスタスキャン順に処理するため、1 パスで完了します。GIF 変換時のデフォルトディザリングとして広く採用されています。
順序付きディザリング (Bayer ディザリング):
Bayer 行列 (閾値マップ) を使用した規則的なディザリングです。各ピクセルの閾値を Bayer 行列から取得し、その閾値に基づいて量子化先を決定します。パターンが規則的なため、誤差拡散より品質は劣りますが、並列処理が容易で GPU 実装に適しています。レトロゲーム風の表現にも使用されます。
減色 + ディザリングの実装:
Python では Pillow の image.quantize(colors=256, method=Image.MEDIANCUT, dither=Image.FLOYDSTEINBERG) で減色とディザリングを同時に適用できます。ImageMagick の convert -colors 256 -dither FloydSteinberg も同様の処理を提供します。ディザリングの強度を調整することで、ノイズ感と滑らかさのバランスを制御できます。
実践的な応用 - GIF 変換とドミナントカラー抽出
減色アルゴリズムの実践的な応用として、GIF アニメーション作成とドミナントカラー (支配色) 抽出を解説します。Web 開発やデザインツールで頻繁に使用される技術です。
GIF 変換の最適化:
GIF 形式は最大 256 色のインデックスカラーを使用します。高品質な GIF を生成するには、パレット選択が重要です。グローバルパレット (全フレーム共通) とローカルパレット (フレームごと) の選択、透明色の確保 (255 色 + 1 透明色)、ディザリングの適用有無を考慮します。動画 GIF では、フレーム間の色の一貫性を保つためグローバルパレットが推奨されますが、色変化が大きいシーンではローカルパレットが有効です。
ドミナントカラー抽出:
Web デザインやアプリ開発で、画像から主要な色を抽出する需要があります。k-means (k=5-8) を適用し、クラスタサイズ順にソートすることで、画像のドミナントカラーパレットが得られます。Google の Material Design や Spotify のアルバムアート背景色生成に同様の技術が使用されています。
カラーパレット生成の工夫:
- 肌色や背景色など面積の大きい色を除外し、アクセントカラーを抽出する
- 彩度でフィルタリングし、鮮やかな色のみをパレットに含める
- CIELAB 空間で k-means を実行し、知覚的に均等なパレットを生成する
- 抽出した色のコントラスト比を確認し、アクセシビリティ基準を満たすか検証する
パフォーマンス最適化:
大量の画像を処理する場合、画像を縮小 (例: 100 × 100) してから減色処理を行うことで、品質をほぼ維持しながら処理速度を 100 倍以上向上できます。色分布の統計量は解像度にほとんど依存しないため、縮小画像から生成したパレットを元画像に適用しても品質の低下は最小限です。