« プログラマー的デザイン表現(7) | トップページ | 時間を大切に »

2010年6月 8日 (火)スモールA、スモールA、聞こえていますか?

ほんの数週間まえからようやく暖かくなってきた、と思ったのもつかの間、急に汗ばむほどの暑さになってきた今日この頃、皆様、いかがお過ごしでしょうか?

最近Webで青い鳥は身近な鳥かごにいるとの情報を得て鳥かごを置く場所を作るために部屋の掃除をする道具を求めてネットの海で釣られないように疑心暗鬼になりながら青い鳥なんて実はいないんじゃね~のと呟くのに忙しいM.L.Kです。プログラマです。
あ、おはようございます。本日の当番です。LはLuckのLです(Luck&Lack!!)。

さて、前回は減色の奥深さの迷宮に踏み込んでしまいましたが、小手先だけの問題解決の様相となっていたのを改めて、少し初心に還ろうと思います。

メディアンカット法とは、色の分布を中央値で分割していき、目的の分割数となるまで、これを繰り返す、というものです。かなり大雑把な説明ですが。

色の分布、というのを聞いて、たいていのヒトは次のようなものを思いつくと思います。

INT anFrec[256][256][256];

画像中にある色

が1ピクセルあれば、

anFrec[R0][G0][B0]++;

として、24bits色(すなわち、1677万色)のうちのどのいろがどれだけ出現したかを数え上げようという魂胆なワケですね。

ちなみに、上の配列は、256×256×256×4bytes=64Mbytesとなります。
ひと昔前なら「M?ないやろ~!」とか言っていたんですが、昨今のメモリ容量の増大化の風潮では、思うべくところもありません。いや?穢された?ワタシ?若干?

昔話はさておき、後はこのanFrecの中のデータをもとに、グループ分けを行います。
とりあえず、各チャンネルの最大値と最小値を求めましょう。
と、思いきや、これはちょっと面倒。

Rチャンネルの最小値を求める場合、anFrec[0][0][0]から初めて、anFrec[0][0][1]、anFrec[0][0][2]と、どこに1以上の値が入っているかをチェックして、初めて1以上の値が入っていたところが、Rチャンネルの最小値となります。

コードで書くとこんなカンジ?

for( int i = 0; i < 256; i++ )
{
  for( int j = 0; j < 256; j++ )
  {
    for( int k = 0; k < 256; k++ )
    {
      if( anFrec[i][j][k] > 0 )
      {
        min = i; //minは最小値の格納変数
        i = 256;
        j = 256;
        break;
      }
    }
  }
}

最大値の場合は、これを255から始めて、0までデクリメントしていくカンジでしょうか?しかも、Gチャンネル、Bチャンネルについてこれを繰り返すワケです。
う~ん、ループし過ぎ!

で、次は中央値(メディアン)を求めるワケなのですが、仮に、画像中のピクセル数をnとします。とすると、中央値の基準はn/2ですね。
あと、各チャンネルの最小値、最大値をRmin、Rmax、Gmin、Gmax、Bmin、Bmaxとします。

Rチャンネルの中央値を求めるコードを書くとこんなカンジ?

int count = 0;

for( int i = Rmin; i <= Rmax; i++ )
{
  for( int j = Gmin; j <= Gmax; j++ )
  {
    for( int k = Bmin; k <= Bmax; k++ )
    {
      count += anFrec[i][j][k];
      if( count >= n/2 )
      {
        median = i; //minは最小値の格納変数
        i = 256;
        j = 256;
        break;
      }
    }
  }
}

うあっ!またループだよっ!

まあ、気を取り直して、メディアンカットのココロ、グループ分けに入ります。
グループのデータとして保持しなければならないのは、各チャンネルの最小値、最大値、それに中央値です。

struct GROUP
{
  INT anMin[3];
  INT anMax[3];
  INT anMedian[3];
};

とでもいたしましょうか、ここに先ほど求めた各値を入れると、ジャーン!メディアンカット1色減色のグループ分けが完了です!

あ、ぶたないでっ。Mとかないんでっ。

真面目な話、このグループを2つに分ける方法さえ揃えば、後はその繰り返しです。
…繰り返し…?ゴクリ…。

例えば、GROUPがm個あったとして、

INT differenceMax = 0;
INT idxDivide;
INT chDivide;

for( int i = 0; i < m; i++)
{
  for( int j = 0; j < 3; j++ )
  {
    INT difference = group[i].anMax[j] - group[i].anMin[j];
    if( difference > differenceMax )
    {
      idxDivide = i;
      chDivide = j;
      differenceMax = difference;
    }
  }
}

新しいグループをgroup[m+1]、分割される元のグループをgroup[idxDivide]とすると、先ほど最も差が大きかったチャンネルについては、とりあえず、

group[m+1] = group[idxDivide];

として、

group[m+1].anMin[chDivide] = group[idxDivide].anMedian[chDivide];
group[idxDivide].anMax[chDivide] = group[idxDivide].anMedian[chDivide]-1;

と、新たに分割されたグループとして書き換えを行い、最初に出てきた最小値を求めるループの0と256が書かれているトコロを、各々のanMin[]とanMax[]を各チャンネルで対応してやれば、それぞれの最小値が求まります。
同様に、最大値、中央値も求められる、といった具合です。

“後はその繰り返し”と言ったのは、このグループの分割とそれぞれの値を求めることを、目的の色数になるまで繰り返して行う、ということを指しています。

これだけループを繰り返しているワケですから、当然のことながら、処理には時間がかかります。救いと言えば、このやり方なら、元画像のピクセル数が膨大な数になったとしても、最初のanFrec[][][]のデータを作成する時に処理が増えますが、以後の処理量は変わりません。まあ、それを差し引いても、余りあるくらいに遅くはあるのですが。

こうやって振り返ってみると、やり方によって処理の時間が大幅に減せる(例えば、以前に紹介した200行程度の実装のように)ということに、改めて思い至ります。

前回のブログで、「むちゃくちゃ遅い」といっていた実装も、ひょっとするともっと速くするやり方があるかもしれません。…少し希望が湧いてきました。

ま、家の中を探したら実は鳥かごがあった、程度の希望なんですけどね。

follow us in feedly
result = encodeURIComponent( "http://www.accessgames-blog.com/blog/2010/06/post-c9c6.html" );document.write( "result = " , result );&media=https%3A%2F%2Ffarm8.staticflickr.com%2F7027%2F6851755809_df5b2051c9_z.jpg&description=Next%20stop%3A%20Pinterest">

| | コメント (0) | トラックバック (0)

« プログラマー的デザイン表現(7) | トップページ | 時間を大切に »

プログラマー」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック


この記事へのトラックバック一覧です: スモールA、スモールA、聞こえていますか?:

« プログラマー的デザイン表現(7) | トップページ | 時間を大切に »