|
4.15 【Quantization】
現在16日の午前0時2分だったりするが、ファイルを作成したのは15日なのでそういうことにしておく。日付けが変わると同時にSherlockの索引作成が始まってしまった。そうか、デフォルトではそういう設定なのか。
前回書いた、Carbon版で起こった問題について、ある程度解決したものをリリースした。本当は先週用意していたのだが、アップロードができず、遅くなってしまった。
IconPartyのCarbon版でも、レイヤー機能は正常に動作した。GetPictInfoの使用できない機能には該当しなかったようだ。ふう、よかった。「使用中の色」の機能は、自前のルーチンを用意してなんとか解決。256色しか考えなくていいから、左上から順に使われている色をチェックするだけでよく、簡単に作成できた。せっかく作ったので、Classic版についても自前のルーチンを使うようにしておいた。
QT-Qについては、自分で減色ルーチンを用意することに。とはいえ、画像処理に関する知識はほとんどないので、なにか手がかりになる情報はないとちょっとつらい。そこで、いろいろ検索してみたところ、こんなページをみつけた。いろいろな減色アルゴリズムについて若干解説があり、また、実際にそれを使っているソフトや、そのソースコードが掲載されている。なんと親切なページ。
まず、減色についての簡単な考え方から。たぶん、減色処理は、大きくわけると２つのステップからなる。ひとつは減色したカラーパレットの作成、もうひとつは作成したパレットにあわせて画像をコピーする作業だ。上記のページで書かれているのは、前者のカラーパレット作成の部分。紹介されているのは、Median
Cut、Variance-based method、Octree、Kohonen Neural Network Quantization、Local K-meansというものらしい。名前を聞いてもさっぱりピンとこないな（汗）。
後者のコピー処理では、単に近い色を選ぶもの、近い色との差（誤差）を周りの色に反映するもの（誤差拡散）、誤差の代わりにあらかじめ作成しておいたパターンを使用するものなどがあるらしい。とりあえず、後の部分はあとで考えることにして、まずはカラーパレットを作ってみようかな。
アルゴリズムがいろいろあってどれを使ったものかと悩むところだけど、アルゴリズムの説明もあって、ソースコードが手に入ったものということで、Median
Cutを使ってみることに（GetPixMapInfoで使われているmedianMethodというのがこれなんじゃないかという予想もあって）。余裕があったら他のものも試してみて、自由に選べるようにできたらベストかな。
Median Cutは、Netpbmという画像変換ツールで使われているものらしい。具体的には、その中のppmquant.cというファイルになる（色を減らすことを、量子化：Quantizationと呼ぶらしい）。ここに、mediancutというそのままの名前の関数がある。これだ。
Median Cutにおける、処理の流れについてざっと解説。まず、画像の中で使われている色を調べ、それぞれの色が使用されている回数を記録する。次に、使われている色を、赤・緑・青の三原色のうち、明るい部分と暗い部分の差が一番大きい要素について並びかえる。そして、使用されているピクセルの数が半分ずつになるように、色をわける（それぞれを「ボックス」と呼ぶ）。そして、できたボックスを、使われているピクセル数で並びかえ、多いものについて、もう一度、三原色のうち、明るい部分と暗い部分の差が一番大きい要素について並びかえ……、と、ボックスの数が必要な色数になるまでくり返す。最後に、それぞれのボックスについて、ボックスを代表する色を決定すれば終了となる。
R・G・Bで差が大きいところを分割していくわけだから、最終的には使われている色全体の中で比較的似た色が同じボックスに入ってくる計算になる。「差が大きい」ことの判定や、最後のボックスの代表する色を決定するところでいくつか方法があるようだ。詳細については、上記のソースを参照のこと。
使われている色を調べるところでは、単純に考えると、可能性のある数だけカウンタを用意しておいて順に足していくということになるが、24ビットでは16,777,216個の色があるから、1色に4バイト使うとすると64Mのメモリを使用してしまう。しかし、実際には、1024*768ピクセルの画像でも786,432個しか点がないわけで、これは非常に無駄だ。あるいは、使われている色を順に配列に格納しながら数えるという手もあるが、終わり頃になると非常に動作効率が悪くなる。
ひとつの方法は、どちらにしても256色以下にしてしまうわけだから、24ビット→12ビットや15ビットに情報を落とし、必要なカウンタの数を減らす方法。こうするとメモリの使用効率はよくなるが、最初に情報を落としてしまうため、やはり若干画質が落ちてしまう。
Netpbmでは、ハッシュを使い、どちらの問題も解決しているようだ。なるほど、これはすばらしい（libppmcmap.c）。ハッシュに使っている関数にどういう意味があるのかはちょっとわからないが、使われている数はすべて素数のようだ。
だいたい内容がわかったところで、PixMapHandleからCTabHandleを作るルーチンに書き換えてみる。ppm.hを24ビットの画像にあうように修正して、mainをざっと書き換えてみると、２、３バグはあったものの、すぐにちゃんと動いてくれた。おおお。
しかし、CopyBitsの問題（描画色を黒、背景色を白にしていないとditherCopyがきれいにいかない）があり、カラーパレットを作成しただけではだめなようだ。うむむ……。次は画像のコピーの部分を作らないといけないのかな。
|