Color Palette

久々に色彩のプログラムを改良しました。今回は画像のカラーパレットをつくってみました。

画像から代表的な色を選ぶというのが大まかな流れですが、減色パレットのアルゴリズムが方向性に近いと思いその方向で進めることにしました。減色アルゴリズムはメディアンカットとK平均法を実装してみました。デバッグ目的も兼ねてアルゴリズムも視覚化してみました。

Median-Cut（メディアンカット）

メディアンカットは色空間に立方体を配置し、それを細分化していくことでグループ分けをしていくような仕組みです。

メディアンカットの流れ

１．ピクセルデータすべてを含む立方体を配置する

２．一番長い辺を軸にして立方体を分割する

３．立方体に含まれるピクセルデータの平均色を求めて、立方体の代表色とする

４．２～３をパレットの数だけ繰り返す

HSV空間のHue方向にだけ重みを付けて分割しやすくするようにしましたが、メディアンカットだけだと結果が大雑把な色になりがちなのでK平均法を試すことにしました。

K-Means（K平均法）

各ピクセルをグループに分けて、グループに含まれるピクセルの平均色を代表色にする仕組みです。クラスタリングの代表的なアルゴリズムです。

K平均法の流れ

１．減色する色数分の代表色をランダムに色空間に配置する

２．各ピクセルデータとの距離を計算し、一番近いピクセルをその代表色のグループに含む

３．代表色をグループに含まれるピクセルデータの平均の位置（重心）に移動させる

４．２～３をある程度の回数繰り返す

距離を測るのでそれなりに重いです。K平均法は初めのランダム配置で結果までの計算量が変わるのでメディアンカットである程度まで分割した立方体の位置を初期位置として実行するようにしました。

最低限の色は取れているかと思うのですが、まだまだ精度が甘いですね。もう少しアルゴリズムを改良していく予定です。

開発環境：VIsual Studio Express 2008, XNA 3.1

試行錯誤