なたで日記

いろいろな思ったこと書きますヽ(^▽^ゞ)

メディアンカットによる減色アルゴリズム

time 2007/06/21

メディアンカットによる減色アルゴリズム

3日前から、いつものHSP言語で減色プログラムを作ってたのですが、なかなか難しい。
メディアンカットを実装したいんだけど、資料がないんですよねー。

ということで、減色アルゴリズムを調べた形跡を紹介します。

減色アルゴリズム1
1. 全ての色からある程度階調を落とした色数のヒストグラム作成
2. 色数を多い方から昇順でソートする。
3. ソートした色の最初から指定した色数まで選ぶ。

これ、減色は出来てるのですが。
色数が少ない場所はもちろん全滅です。(当たり前)

というわけで、メディアンカットを調査。
検索エンジンで調べてみると、ブロックを作ればいいことが判明。(適当)

減色アルゴリズム2
1. 全ての色からある程度階調を落とした色数の直方体ブロック作成と色数を調べる
2. 直方体の中で色数が一番多いのを選ぶ。
3. 直方体の3辺の中で一番長いの辺を選ぶ。
4. 選んだ辺の真ん中から2つにぶったぎる。
5. その2つの色数を調べて、両方とも色が分散してたら色数カウントを増やす。
6. 2.~5.を繰り返して、色数が指定した色数になったら7.へ。
7. ブロックから平均をとってパレットに追加。

これが、なかなかうまくいった。
しかし何かがおかしい、あんまり使われていない色は全然出ていない。
よく検索で調べてみると、ブロックを区切る時に、真ん中ではなくて
区切った時に色数が大体半分になるような位置にしないといけないということが分かった。

減色アルゴリズム3
1. 全ての色からある程度階調を落とした色数の直方体ブロック作成と色数を調べる
2. 直方体の中で色数が一番多いのを選ぶ。
3. 直方体の3辺の中で一番長いの辺を選ぶ。
4. 選んだ辺で区切った時に色数が大体半分になるような位置を区切る。
5. その2つの色数を調べて、両方とも色が分散してたら色数カウントを増やす。
6. 2.~5.を繰り返して、色数が指定した色数になったら7.へ。
7. ブロックから平均をとってパレットに追加。

うーむ。たしかにいけるのだが、指定した色数まで減色できなくなった。
特に64色以上だと途中で止まってしまうことがある。

さらに調査してみると、
「2. 直方体の中で色数が一番多いのを選ぶ。」

これについても、
・ 直方体の中で色数が一番多いのを選ぶ。
・ 直方体の中で辺が一番長いのを選ぶ。
・ 直方体の中で体積が一番大きなものを選ぶ。

という種類があるということが判明。
ここのせいで指定した色数まで減色できないのかと思い、
どれも試してみましたが、指定した色まで減色できない。
おそらく、そもそもどこかにバグが入っているようだ。

一旦、体積を優先する方法で、64色まで限定というのが完成。
(それ以上の色数だとバグることがある・・・)
まあ、画像効果に利用するだけの予定なのでこれで十分だ!

・・・うーむ。どこが間違っていたのか。
どっかで収束してしまうのかな。

メディアンカットの意味
ところで、今までメディアンカットって1つのアルゴリズムの一種で、
その決められたアルゴリズムを実装したら誰でも簡単に減色で切ると思っていたけど、
実際は 色をブロックにして、それを分けていく という行為そのものがメディアンカットって言うのかな。
つまり、明確なこれだというアルゴリズムはない。

ポスタリゼーション
またまた話し変わりますがポスタリゼーションも作りました。
ただ、なぜか、PictBear、SHARAKU、みたいに綺麗にポスタリゼーションができない。
階調変更のみで、RGBテーブル参照のコントラスト処理で実装できると思って試したのですが、何かが違う。
それで、階調変更の前にコントラストを60あげて処理したら綺麗になった。
ポスタリゼーションの内部処理に”コントラストあげる”ってのが本当は必要なのかもしれない。




プロフィール

なたで

なたで

明るくて楽しいことが好きです!モノづくりや旅が趣味です!

RSS フィード RSS feed GitHub GitHub Twitter Twitter YouTube YouTube



sponsored link

タイムライン