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あげて処理したら綺麗になった。
ポスタリゼーションの内部処理に”コントラストあげる”ってのが本当は必要なのかもしれない。

関連記事

  • Bresenhamアルゴリズムで線分の計算は早いのかなBresenhamアルゴリズムで線分の計算は早いのかな 以前、直線を描くのにこんなのを作った。 特に工夫点もない、素直な方法である。 #module "linem" #deffunc line2 int line_x1,int line_y1,int line_x2,int line_y2 line_xabs = abs(line_x1-line_x2) line_yabs = […] Posted in アルゴリズム
  • セカンドライフで綺麗な水面を作るセカンドライフで綺麗な水面を作る こんにちは! 「セカンドライフ技術系 Advent Calendar 2015」の12月13日(日)担当の なたで […] Posted in セカンドライフ制作
  • Javaで3Dゲーム開発日記 part5 画像補間Javaで3Dゲーム開発日記 part5 画像補間 以前の続きでテクスチャのパーリンノイズの補間法の話です。 いい加減補間について調べようといろいろとプログラムして作ってみました。 テクスチャなので、上下と左右が繋がるように補間します。 8x8px → 256x256px […] Posted in ゲーム制作
  • HSPで高DPI対応ソフトを作ろうHSPで高DPI対応ソフトを作ろう こんにちは! 久しぶりにHSPの記事を書きたいと思います! 今回は、HSPの高DPI対応です。 はじめに 高DPIとはなんぞや、という説明をします。 昔のディスプレイは、1ドットのサイズが細かくないため、 1ピクセル=1ドットのような設計がほとんどでした。 そして、1ピクセルの大きさも、どのディスプレイもだいたい同じようなサイズ(96dpi)でし […] Posted in プログラミング
  • マップオンデマンドの地図更新でパスワードが入力できないマップオンデマンドの地図更新でパスワードが入力できない 車を購入時にカーナビとしてNSZT-W61Gを付けたのですが、 カーナビ購入してから3年間はマップ情報のバージョンアップが無料ということで、 バージョンアップをしようとしました。 バージョンアップ方法の流れ 1. 購入時についていた「マップオンデマンドセットアップディスク」のDVDでセットアップツールをインストール 2. 「GAZOO」を無料でユーザー登録(「TOYOTA […] Posted in 雑記
  • C言語のアドレス演算子の不思議C言語のアドレス演算子の不思議 前々から、C言語のポインタで不思議だったこと。 最適化C 言語 […] Posted in プログラミング