減色アルゴリズム[量子化/メディアンカット/k平均法]
写真などの画像を減色する均等量子化、中央値分割法(メディアンカット)、K平均法(Kmeans)のアルゴリズムの解説です。
減色対象の画像
この画像の色数は「24,955色」です。今回の記事では画像のファイルサイズを小さくする為に全ての画像をJPEGで圧縮しています。その為、「実際の減色の品質はもう少し綺麗」です。(JPEGで圧縮すると色数が増えて画質が落ちます)
この記事で紹介しているメディアンカットなどの減色をテストするにはブラウザで動作する「画像の減色」のページで確認する事が可能です。
1.均等量子化
量子化という大そうな言葉ですが、要は赤色256種類、緑色256種類、青色256種類の色情報「256x256x256」(1670万色)を「64x64x64」(26万色)「32x32x32」(32,000色)などに色を削る事です。
これはプログラムで「色の各RGBの値をシフト」または「色の各RGBの値を任意の範囲で振り分ける」事で可能です。256色の場合は「7x7x5」、16色だと「4x2x2」などにすると良いです。2色は白と黒にする事が多いです。
この均等量子化は高速ですが基本的に品質は良くありません。ただ、画像によって稀に品質が良い場合もあります。
減色後
均等量子化で256色に減色した結果です。
2.K平均法(Kmeans)
K平均法は「代表色を元に各ピクセルをグループに分割して、そのグループ毎のピクセルデータの平均色を代表色に置き換える」という事を代表色の変化がなくなるまで繰り返します。そして、最後の代表色が減色後のパレットとなり色数となります。
減色の流れ
2.各ピクセルを一番近い代表色のグループに分割する
3.グループ毎に平均色を求めて新しい代表色とする
※2,3を代表色の変化がなくなるまで繰り返す(1-100回位)
| 補足 | 内容 |
|---|---|
| 1 | 減色する色数分(2色-256色の任意)の代表色をランダムで作成する。 ※256色に減色する場合は256個の代表色を作成する。 |
| 2 | 一番近い近似色を求めるにはRGBの3次元空間の2点間の距離を求めます。これはユークリッド距離で計算式は次の通りです。 「距離 = sqrt((R1- R2)^2 + (G1- G2)^2 + (B1- B2 )^2)」 この距離が近いものが近似色となります。 |
| 3 | 平均色の求め方は単純に割るのではなく各色に対して「色の使用数」を重み係数として求めると精度が上がります。 ※サンプルはメディアンカットの章をご覧ください。 |
問題点
このK平均法は計算量が多く非常に時間がかかります。
計算量を減らす為にメディアンカットなどで減色した後にK平均法を実施すると、処理時間が短縮される上に品質が向上します。
減色後
K平均法を100回繰り返して256色に減色した結果です。
ChromeでのK平均法のJavascriptの実行時間は「117820.558ms」です。繰り返し回数を増やせばもう少しは画質があがると思います。
次の画像はメディアンカット(面積)の後にK平均法を16回繰り返した結果です。
画質は綺麗ですが、Javascriptで実行すると「58322.889ms」かかりました。メディアンカット自体はそれなりに高速ですが、K平均法が異常に遅いのでJavascriptでは実用的ではありません。
3.メディアンカット(中央値分割法) - 面積
メディアンカット(面積)はフォトレタッチソフトなどのアプリケーションで一般的に使用されるアルゴリズムです。K平均法と比べると高速で安定した品質を得る事が可能です。
減色の流れ
2.キューブ毎にピクセルデータの平均色を求めてキューブの代表色とする
3.ピクセルデータに代表色を設定する
| 補足 | 内容 |
|---|---|
| 1 | キューブは日本語では「立方体」です。「色の面積」は「色の使用数」と同意です。分割回数は2-256回で減色する色数となります。(257以上の分割も可能です) ※最初のキューブは1個で全てのピクセルデータが対象です。 |
| キューブ内の各色のR、G、Bの中で「一辺の長さ」が一番長い色を「軸色」とする。そのR、G、Bの「一辺の長さ」を比較する際は人間の目は赤と緑が認識しやすいのでRとGの「一辺の長さ」に1.2などの係数を乗算すると良いです。 ※「一辺の長さ」は「最大値 - 最小値」で算出する。 ※「軸色」はR/G/Bのいずれかです。 ※R、G、Bが同じ場合はRを「軸色」とします。 | |
| 「軸色」を元に中央値を算出して分割する。中央値の計算式は次の通りです。 「中央値 = floor((対象キューブの軸色の数+1)/2)」 | |
| 2 | 平均色の求め方は単純に割るのではなく各色に対して「色の使用数」を重み係数として求めると精度が上がります。 [簡略的なサンプルコード] for(;;){ // 色の使用数を係数とする(3回は色の使用数の例) r += cubes.r * 3回 g += cubes.g * 3回 b += cubes.b * 3回 // 色の使用数の合計 count += 3回 } return {'r': Math.round(r/count), 'g': Math.round(g/count), 'b': Math.round(b/count)}; |
メディアンカットの減色のイメージ動画
※花鳥風月さんの作品です。
減色後
メディアンカット(面積)で256色に減色した結果です。
Javascriptでの実行時間は「300ms前後」です。
4.メディアンカット(中央値分割法) - 分散
メディアンカット(面積)は基本的に全体を中心とした減色で安定した品質ですが、実は「細部の減色」に若干、弱いです。そこで、メディアンカットを「面積」から「分散」に改良すると細部を中心とした減色となります。
分散はデータの散らばり具合を表します。分散が大きいと散らばりが大きい、分散が小さいと散らばりが小さい事となります。
[面積]
[分散]
※分散の大きさはR、G、B毎の分散の平均値を算出します。
分散の計算には「数学の公式」があります。詳しくはネットで検索してくださいね。
減色後
メディアンカット(分散)で256色に減色した結果です。
Javascriptでの実行時間は「300ms前後」です。
5.メディアンカットの面積と分散の比較
顔をアップで確認すると、分散の方が綺麗に減色できているのがわかります。但し、分散は空や海などの背景があると空や海が「縞模様」になる事が多いです。
[面積]
[分散]
次は空と菜の花の画像で比較してみます。
[面積]
[分散]
以上となります。
減色の研究は色空間をYUVやLABなどで試す方法やメディアンカットの計算方法の変更など手法は無数にありますが、今回で一旦、私の減色研究は〆とさせて頂きます。また時間が空いた時にでも色々と試して見ますね。
減色のテスト
減色のソースコード
参考リンク
メディアンカット減色法
減色アルゴリズム
メディアンカット法による画像の減色
24bit → 8bit 減色
k-means法で画像を減色するサンプルコード
メディアンカット法による画像の減色
関連記事
