ホーム 主筆 その他ソフト その他情報 Syuhitu.org English

Windows関連

スクリーンセーバー作成法

半透明ウインドウの性能

bootfont.bin

キャビネット形式

ウインドウスタイルをいじる

Java製ソフトをServiceに登録する

イベントログにメッセージを出力する

コントロールパネルにアイコンを追加する

スクリプトによる拡張1

スクリプトによる拡張2

ガジェットの作成

大容量メモリ

メモリ搭載量の下限に挑む

スパースファイルにする

表示されるアイコンの種類を調べてみた

メモリマップIOとエラー処理

ファイルを作る順番と速度の関係

Cryptography API: Next Generationを使う

Windows 10のアクセントカラー

iSCSIディスクにバックアップを取る

サーバプロセスを分離して実装する

サーバプロセスを分離して実装する - F#

レジストリに大量に書き込む

Solaris関連

OpenGL

Solaris設定

ディレクトリの読み込み

主筆プラグイン開発

マルチスレッドでの開発

door

音を出す

Blade100の正しい虐め方

パッケージの作成

画像入出力

BMPファイル

ICOファイル

ANIファイル

JPEGファイル

減色アルゴリズム

減色アルゴリズムの並列化

その他アルゴリズムなど

自由軸回転

Base64

文字列操作

CPU利用率の取得

正規表現ライブラリ

メタボールを作る

メタボールを作る2

正規表現とNFA・DFA

C言語の構文解析

液晶ディスプレイを解体してみた

iSCSIの理論と実装

単一フォルダにファイルを沢山作る

USB-HUBのカスケード接続

SafeIntの性能

VHDファイルのフォーマット

USBメモリに書き込み続けてみた

減色アルゴリズム

2006年9月17日公開

24bitカラーの画像を8bitカラー(256色)に落とすことを考えてみる。

24bitカラー

24bitカラーの画像というのは、そもそもどういうものなのか。

いろいろやり方はあるのだろうが、もっとも基本的なのは、各ピクセルの色を、光の三原色である赤・緑・青のそれぞれの強さ(明るさ)で表現する方法だ。でもって、24bitだから、それぞれの色の強さを8bitで表現するのが一般的だ。

つまり、赤の強さを0〜255、緑の強さを0〜255、青の強さを0〜255で表すことになる。

そういうことで、24bitカラーの画像では、全部で1677万7216色表すことができる。

8bitカラー

これもいろいろ方法はあるのだろうが、一般的には256個のカラーパレットを用意しておき、各ピクセルの色はカラーパレットを参照する形で表現する方法がとられる。

画像の各ピクセルには、カラーパレットのインデックス値が設定される。

カラーパレットに設定される値は、通常RGB各色8bitずつの24bitカラーである。

結果として、画像で使用可能な色は、1677万7216色の内の任意の256色という事になる。

減色の方法

減色の手順を大きく分けると、次の二つに分けられる。

  • カラーパレットの色を決定する。
  • ピクセルに設定する、カラーパレットのインデックス値を決定する。

8bitカラーの画像が上記のような方法で表現されるというのだから、当然といえば当然。

カラーパレットの色を決定する

単純な方法

使用可能な色は全部で256色。

単純に考えるのなら、RGBのぞれぞれに数ビットずつ割り当てて、機械的に色を生成すればいい。

例えば、赤に2bit、緑に3bit、青に3bit割り当てて色を生成するなら、こんな感じになる。

#include <stdio.h>

int main()
{
  int r, g, b;
  int i;

  printf( "<html><table border=\"1\">\n" );

  for ( i = 0; i < 256; i++ ) {
    r = ( i & 0xC0 ) >> 6;  // rは0から3
    r = r * 255 / 3;
    g = ( i & 0x38 ) >> 3;  // gは0から7
    g = g * 255 / 7;
    b = ( i & 0x07 );       // bは0から7
    b = b * 255 / 7;

    // HTMLのタグを出力
    printf( "<tr>" );
    printf( "<td bgcolor=\"#%02X%02X%02X\">", r, g, b );
    if ( r + g + b > 384 )
      printf( "<font color=\"#000000\">" );
    else
      printf( "<font color=\"#FFFFFF\">" );
    printf( "0x%02X%02X%02X", r, g, b );
    printf( "</font></td></tr>\n" );
  }

  printf( "</table></html>\n" );
  return 0;
}

上のコードはHTMLのコードを生成するようになっている。実行するとこういう出力が得られる。

coltbl1.html

この方法では、全ての色を平等に取り扱うことになる。だが、それは必ずしも最適解であるとは限らない。

例えばこういう画像について考えてみる。

この画像では、赤や白・黒といった色は使用していない。だから、256個しか使えない貴重なカラーパレットに、赤や黒といった色を設定するのは無駄である。

つまり、カラーパレットに設定するべき色は、入力画像によってそれぞれ異なるということである。

入力画像に合わせて決定する

大概の画像では、使用している色には偏りがある。だから、だからその偏りを考慮して色を設定してあげる必要がある。

ではどうするのか。大体、下記のような手順で求める。

  1. 色のヒストグラムを求める。
  2. 近い色同士をまとめる。
  3. 256色以下になるまで2を繰り返す。

1.色のヒストグラムを求める

まず初めに、各色がそれぞれ何ピクセルずつ使用されているのか、を数え上げる。

プログラムで書くならこんな感じ。

void CountColor( int v[256][256][256], 入力画像 )
{
  int x, y, r, g, b;
  int width, height;

  // 幅と高さを取得
  width = 幅;
  height = 高さ;

  // 配列vを0で初期化
  memset( v, 0, sizeof( int ) * 256 * 256 * 256 );

  // 色を数える
  for ( y = 0; y < height; y++ ) {
    for ( x = 0; x < width; x++ ) {
      // 座標( x, y )の色を取得
      r = ( x, y )の赤の値;
      g = ( x, y )の緑の値;
      b = ( x, y )の青の値;
      v[r][g][b]++;
    }
  }
}

もちろん、上のやり方をそのまま使おうとするのは愚の骨頂である。何せ、intが4バイトだとしたら配列vは64MBにもなるのだから。

いずれにせよ、上記のようにすることで、それぞれの色が何ピクセルずつ使用されているのかを求めることができる。

2.近い色同士をまとめる

使用可能なカラーパレットの数は256個しかない。だから、似たような色を一つにまとめて色数を削減する。

ではまず、二つの色が「似てる」とはどういう事なのかについて考えてみる。これもいろいろやり方はあるのだろうが、もっとも単純な方法はRGBのユークリッド距離を求める方法だ。

二つの色がそれぞれ( R1, G1, B1 )と( R2, G2, B2 )であれば、

  • 距離 = sqrt( ( R1 - R2 ) * ( R1 - R2 ) + ( G1 - G2 ) * ( G1 - G2 ) + ( B1 - B2 ) * ( B1 - B2 ) );

となる。

だが、人間の目には赤・緑・青のそれぞれの色はちょっとずつ感じ方が違うとも言うし、俺の感覚からすると、明るさの変化よりも色相の変化の方が目立つような気がするし、なかなか難しいものがあるように思う。

だが、とりあえず今のところは、上記の方法で「色の差」を求めることにする。

次に、二つの色を「一つにまとめる」とはどういう事か。

単純に行けば、赤・青・緑のそれぞれの平均を求めるということになる。だが、ここに一つ問題がある。

例えば、下記の二つ色をまとめることを考える。

  • R=255, G=0, B=0 (つまり赤), ピクセル数=9999
  • R=0, G=0, B=255(つまり青), ピクセル数=1

何で全然違う色をまとめなければならないのか、という突っ込みはおいておくものとして、とにかく上記の二つの色をまとめてみる。

単純に平均を求めるのなら、

  • R=128, G=0, B=128(つまり紫)

となる。しかし、赤は全部で9999ピクセルなのに対して、青は1ピクセルだけである。そのたった1ピクセルの青のせいで、9999ピクセルの赤が紫になってしまっていいのだろうか。

直感的に考えれば、青は赤に埋没して消滅してしまうのではないだろうか。

そういうことで、ピクセル数の重み付けを考慮して平均をとることにする。

  • 新しい赤 = ( 255 * 9999  + 0 * 1 ) / 10000
  • 新しい緑 = ( 0 * 9999  + 0 * 1 ) / 10000
  • 新しい青 = ( 0 * 9999 + 255 * 1 ) / 10000

もっと一般的な表記にするとこうなる。二つの色をそれぞれ( R1, G1, B1 )・( R2, G2, B2 )として、ピクセル数をP1・P2、生成された色を( R3, G3, B3 )、生成された色のピクセル数をP3とした場合、

  • P3 = P1 + P2
  • R3 = ( R1 * P1 + R2 * P2 ) / P3
  • G3 = ( G1 * P1 + G2 * P2 ) / P3
  • B3 = ( B1 * P1 + B2 * P2 ) / P3

となる。

3.256色以下になるまで2を繰り返す

読んで字のごとく。特に解説することもない。

色とピクセル数の配列の中から、一番近い色を二つ選び出して、2の手順に従って色をまとめて、それを全体の色数が256色になるまで繰り返せばいい。

コードにするならこうなる。

void Matomeru( 色とピクセル数の配列 v ) {
  int i, j;

  while ( 色数が256色以下になるまで ) {
    int idx1, idx2;
    int w = INT_MAX;
    // 一番近い色を求める
    for ( i = 0; i < 色数 - 1; i++ ) {
      for ( j = i + 1; j < 色数; j++ ) {
        int w2 = v[i]とv[j]の色の差;
        if ( w2 < w ) {
          idx1 = i;
          idx2 = j;
          w = w2;
        }
      }
    }
    // 色をまとめる
    新しい色を求める;
    v[idx1]をv[idx2]を削除;
    vに新しい色を追加;
  }
}

だがしかし、上記の方法をそのまま使うと、非常に長い処理時間を要することになる。これをどうやって高速化するかが問題となる。だが、その方法はここでは解説しない。

以上の方法で、何となくそれっぽい色を抽出することができる。

ピクセルの色を決定する

カラーパレットの256色が決定したら、次は各ピクセルごとのインデックス値を決定する必要がある。

もし、入力画像で使用されている色の数が、全部で256色以下だった場合は、何の問題もない。単に、完全一致するものを選択して、そのインデックス値を設定してやればいい。

元の画像で使用されている色が256種類以上あった場合は、どうしたらいいのか。

一番近いものを選択する

究極的には、各ピクセルごと最も近い色を選択して、その色のインデックス値を設定すればいい。

だが、その手法を実直に適用すると、グラデーションがかかったような画像に対しては、しましまが発生してしまうことになる。

例えば、下記のような画像の減色を考えてみる。

 

この画像を元に256色を決定し、各ピクセルごと一番近い色を選択して設定すると、こうなる。

当然といえば当然の帰結。

もちろん、グラデーション的な模様がほとんど無い様な画像であれば、この手法でも何ら問題はない。むしろ、好ましい結果になる場合もある。

その辺りは、元の画像と個人の感じ方に依存する問題だと思われる。

誤差の微調整を行う

誤差拡散法という手法がある。

これは、元画像の色と選択した色との差(つまり誤差)を、近隣のピクセルを使って補正しよう、という発想。

例えば、下記のような元画像があったと仮定する。

255, 255, 255(確定) 255, 255, 255(確定) 255, 255, 255(確定)
255, 255, 255(確定) 255, 0, 128(着目) 255, 0, 128
255, 0, 128 255, 0, 128 255, 0, 128

(確定)と書かれているところは、すでに何らかの方法でインデックス値を確定したピクセルである。今現在は、(着目)と書かれている真ん中のセルのインデックス値を決めることを考えている。

また、カラーテーブルに設定された色の内、255, 0, 128(赤紫)に最も近い色が、255, 0, 0(赤)だったと仮定してみる。

単純に、一番近いからという理由で、255, 0, 128(赤紫)を255, 0, 0(赤)にしてしまったら、下記のようになる。

255, 255, 255(確定) 255, 255, 255(確定) 255, 255, 255(確定)
255, 255, 255(確定) 255, 0, 0 255, 0, 0
255, 0, 0 255, 0, 0 255, 0, 0

これではさっきと同じである。 

だから、255, 0, 128(赤紫)と255, 0, 0(赤)の差、つまり0, 0, 128を、着目しているピクセルの周囲のピクセルに加算して、補正を試みる。

また、誤差は下記のような割合で加算する。

   
  (着目しているピクセル) 誤差の3/8
  誤差の3/8 誤差の1/4

つまり、0, 0, 128は、下記のように配分される。

255, 255, 255(確定) 255, 255, 255(確定) 255, 255, 255(確定)
255, 255, 255(確定) 255, 00, 00(着目) 255, 0, 128 + 0, 0, 48
255, 0, 128 255, 0, 128 + 0, 0, 48 255, 0, 128 + 0, 0, 32

現在着目しているセルが、255, 0, 0(赤)になるのは、致し方がない。だが、その分その右隣と下のセルが、255, 0, 176になり、右下のセルが255, 0, 160になる。

そして。次の段階で右隣のセルの色を確定する際には、255, 0, 176にもっとも近い色を検索する。

そうすることで、うまい具合に補正が行われて、全体としては何となくいい感じになるようになる。

さっきの画像に対して、この手法を用いて変換を行うとこうなる。

多少ムラがあるような気もするが、元画像には存在しなかった亀甲模様が浮かび上がるよりかはマシだと思われる。とはいっても、上記のような画像は256色にするにはもっとも不向きなものであり、致し方が無いとも言える。

試行錯誤して作ったプログラムだから、酷く汚いし何の参考にもならないだろうけど、とりあえずサンプルのプログラムを公開しておく。

使い方は、dcol.cppとBmpIoLib.cをコンパイル・リンクして実行するだけだ。

コマンドは、

コマンド名 入力ファイル名 出力ファイル名

となっている。

入力できるファイル名は24bitカラーのビットマップファイルだけで、出力される画像は8bitカラーのビットマップファイルである。

なお、コマンドの引数で"-b ビット数"を指定してあげれば、4bitカラーや1bitカラーにも落とすことができるようになっている。


連絡先 - サイトマップ - 更新履歴
Copyright (C)  2000 - 2016 nabiki_t All Rights Reserved.