Compute ShaderでModified Median Cutを実装してGPU上でColor Quantizationをリアルタイム実行可能にしたので、その際に調べたことの一部を整理しておく。

Introduction

Color Quantizationとは、要するに画像の減色処理のことだ。
ここではさらに狭義のIndexed Color（カラーパレット）を使用して任意の色数未満に収める処理を扱い、さらにそのIndexed Colorを求めることにフォーカスしている。

昨今では、ハードウェアリソースが潤沢になったこともあり、Indexed Colorを使用してまで減色する必要性は減り、研究分野としてもやはり比較的ニッチになっている。そのため伝統的なアルゴリズムも結構通用する。伝統的ゆえに、特に最適化せずマシンパワーに任せて強引に実行しても、“一般的”にリアルタイムな処理速度で実行できてしまう。
ここでいう一般的とは、画像処理ソフトとかで減色したときに何分何時間も待つような規模ではなく、人間がストレスなく完了を待つことができる秒単位の実行時間のことである。

しかし、ゲーム的な意味での真のリアルタイムとなると話は別である。60FPS実行されるゲームの場合、16.6ms以内にすべての処理を完了させなくてはならない。
このミリ秒単位の時間内に、CPU上でIndexed Colorを普通に求めようとしても、まだ収まりきらないのが昨今のマシンパワーである。今ではニッチな研究分野であると述べたが、高速化においてもそこまで発展していない。掘り下げていく余地がある。
今回、ベースラインとして並列処理で最適化したModified Median CutのCPU版も作成してあるが、フルHD（1980×720）のような解像度となると、16色のIndexed Colorを求めるにも20ms以上要している。伝統的なシングルコア実行だと言うまでもない結果だろう。

Pixelismでは、工程の最初から最後までGPUをCPUとの同期無しに活用することで、16ms以内の実行を達成している。それどころか2ms程度で済む。リアルタイムレンダリングの感覚としては2ms”も”なんだけれど…

Median Cut

Median Cut は1980年にPaul S. Heckbertによって考案された、代表的なColor Quantizationアルゴリズムの一つだ。40年前のアルゴリズムだが今日まで通用する優れたアルゴリズムだ。名前の通り、中央値を用いて分割していく。

Bad Median Cut

さて、どこで誰が言い出したのをコピペしてまわっているのかどうか知らないが、ネット上で言及されているいくつかの Median Cut アルゴリズムはいい加減だ。それらは、大体次にようになっている。

1. 画像の全ピクセルを処理しやすいように一次元配列にする
2. ピクセル配列を調べてRGBのうち最も範囲が大きいチャンネル調べる
3. 2で求めたチャンネルをキーとしてピクセル配列をソートする
4. 中央値で分割する
5. 最も大きい配列を次の分割対称とする
6. 所定の数になるまで2~4を繰り返す
7. それぞれ平均値を求めて最終的なカラーとする

だが、コピペする前に少しは自分の頭で考えて欲しい。Median Cutアルゴリズムが考案されたのは1980年だ。今日のPCと比べて当時のスパコンですら処理速度が極めて低い時代だ。そんな時代に、1回の分割をするたびに、(2)で都度大量のピクセルを捜査 O(N) して分割軸を求めて、あまつさえ(3)で大量のピクセルをソート O(N logN)していただろうか？
1980年はそんな富豪的なことが許容されていた時代ではないはずだ。

Original Median Cut

では、本来の考案されたアルゴリズムとは何か。発表元の論文を読めばよいのである。古い時代のものだが、幸いにもPaul S. Heckbertご本人がウェブサイトで公開しているので、ACM会員にならなくとも読むことが出来る。

http://www.cs.cmu.edu/~ph/

• Color Image Quantization for Frame Buffer Display, SIGGRAPH ’82, July 1982, pp. 297-307. (Postscript, missing figures)
• Color Image Quantization for Frame Buffer Display, Bachelor’s thesis, Architecture Machine Group, MIT, May 1980, 57 pp. (text file, missing most equations, and all 20 figures). My 1982 paper above is based on this work. For a complete copy of this thesis, contact the CMU or MIT library.

これで述べられている Color Quantization 全体は、次のような工程で行われる。

1. 元画像をサンプルして色の分布を求める
2. 分布情報を元にカラーマップを選択する
3. 元の色に最も近いカラーマップをマッピングする
4. カラーマップを適用して量子化する

このうち Median Cutなどのカラーマップ（Indexed Color）を求めるアルゴリズムは(2)にあたる。

• 分布情報には、RGBそれぞれ5ビットからなる15ビットのヒストグラムを用いる。
• RGB各要素の最小最大値からなるboxを分割する。
  • 分割対象となるboxをどのように選択するか、については具体的に明記されていない
    • 直前に既存手法の The Popularity Algorithmを比較対象として挙げていることから、暗黙的にPopularity、すなわちピクセル数を指標としているようである。
• 分割は、RGBのうち最も範囲の広い成分を対象として、名前通り中央値を使用して分割する。

ヒストグラムを求めておけばそれを参照することで、都度ピクセル全てを捜査することもなく、ソートも必要ないのである。

ヒストグラムにおいてRGBの各チャンネルを一旦8ビットから5ビットの計15ビットに減らすのは、当時のコンピュータが16ビットであり、これに収まることが主要因である。64ビット時代の現代においては、この5ビットに縛られる必要は無く、パフォーマンスとメモリを考慮してビットを決定すればよさそうである。
また、切り捨てられる3ビット分は、Popularity Algorithmを実装した当時のプログラム「IMAGE」では、(3)を高速化するためにハッシュとして使用されていたようだ…が、このプログラムは現存するのだろうか？
IMAGEでは、全工程を実行するのに2.5分要している、とも記述されている（恐らく512×512程度の画像）。いかに富豪的なアルゴリズムが当時現実的でないことが読み取れる。

ところで、ネット上の実装では、分割成分の決定において知覚的な色の選択としてR=1.0, G=1.2, B=0.8の重みがつけられていることがある。この数値の出どころについて誰も言及がなされていないが、論文内で改善手法の一つとして言及されており、Limb, J. O., C. B. Rubinstein, and J. E. Thompson, “Digital Coding of Color Video Signals – A Review,” IEEE Trans. on Communications, Vol. COM-25, No. 11, Nov. 1977, p. 1349. が元ネタであることが分かる。
残念ながら、この参照元の論文は読むことできなかったので、どのようにしてこの重みが提唱されたのかを知ることが出来なかったが、あくまで個人的な見解となるが、もっと良い値があるのではないかと思う。キリが良すぎる。

Modified Median Cut

Modified Median Cut は、Dan Bloomberg によるMedian Cutの改良版の一種である。改良点は以下のとおり。

1. 分割時に中央値を新しい領域の範囲とするのではなく、(中央値-最小)と(最大-中央値)のいずれか大きい方の、さらにその中央値を分割値とする。
2. 分割対象を選択する際に、最大となるピクセル数と、最大となる (ピクセル数 x 体積) を併用する。これらは係数によって割合を決める。

(1) は、分割時になるべく大きい方の領域が残らないようにしていき、小さい方の領域をなるべく維持していくことで、色の再現性を上げるという試みだ。

(2) は、色の分布状態によっては小さい領域に大量のピクセルが含まれているとき、そこが支配的になりその領域ばかりを分割しようとして、広範囲に分布する領域に対して分割が行われないという問題を解消するためだ。
この問題点は、Weighted median cut quantization and its applications でも指摘されていて改善が試みられているようだ。

Implementation on GPU

以上を踏まえて、Modified Median Cut を Compute Shaderで実装したが、ヒストグラムに使用するビット数をRGB各4ビット、計12ビットに減らしている。
これは、Thread Group Shared Memoryを使用した高速化を行う都合で、このメモリの最大値16kbないしは32kb（今どきはこちら）に収めるためだ。15ビットだと 32,768 * 4-byte = 131,072 bytes = 128 kbで超過するが、12ビットだと 4,096 * 4-byte = 16,384bytes = 16 kbと丁度収まるようになっている。