Note: Real-time GPU Color Quantization

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と丁度収まるようになっている。

【令和最新】 .NET Core で Susie Plug-in 呼び出し

みなさんは Susie をご存じでしょうか…
SusieはWindows 3.1の頃からあるグラフィクスビューアです。
画像ファイルのみならずアーカイブファイルにも対応したオープンなプラグイン仕様によって、多種多様なプラグインが有志によって作られていて、かつては日本でかなり使われていたんじゃないかというような素晴らしいビューアでした。


前置きはその辺にしておいて、.NET CoreでSusie Plug-inを呼びだして扱えるようにした。プラグイン呼び出し部分は一通り出来たので、あとはアプリケーション部分を飽きるまで。

https://github.com/longod/WhiteAlbum/tree/main/WA.Susie

 

ことの発端は、最近HDDのデータを整理をしているときに、古い画像ファイルとともに、昔使っていたプラグインが出土したことに起因する。
Susieは長らく更新が停止して動作が怪しくなりつつあるし、OSの更新でいつ動かなくなるかも分からない。プラグインに対応した他のアプリケーションも同様に軒並み古くなってしまったし、そもそもアーカイブまでサポートされたものは少なかった記憶がある。
プラグインもプラグインで、インターネット上に存在するプラグインはサイトの消滅と共に徐々に消えつつあり、惜しい状態だ。同様にインターネット上に存在するプラグインに関する情報も徐々に消えつつある。
じゃあ、今のうちに、次を満たす呼び出し側(ホスト)を作っておくか、というのが動機だ。

  • オープンソース
  • 扱いやすい
  • 今の時代にモダンに動作する
  • 将来的にも動作する可能性が高い

.NET CoreのバージョンはPrismの都合で3.1になったが、単体だけなら5とかに6に上げても動作すると思う。

x86 (32-bit) の影響を受ける

当たり前だけれど、プラグインは時代的に32-bitライブラリとして作られている。
正攻法でプラグインを呼び出すには、呼び出し側もx86でなくてはならない。それに伴って連鎖的にアプリケーション全体がx86になってしまう。今の64bit OSが主流の時代に。

プラグイン仕様書だけを見て作るのは大変

本家のプラグイン仕様書は、Plug-in packageのプラグイン集にテキストファイルとして同梱されている。プラグインを作る側はこれでも大体は問題ないが、プラグインを呼び出す側となると、Susieの内部挙動が公開されていないので大変だ。

このあたりの先人の知見は特に役に立った。

自分でダミーのプラグインを作る

いきなり既存のプラグインを叩いてみると、見事にデバッグ出来ない状況でクラッシュしたりハングアップしたりする。呼び出し方が悪いのか、プラグインそのものに問題があるのかを把握するために、自分で仕様書を元に適当なプラグインを作ってそれを呼び出してみた方が良い。
プラグインは当時の状況を想像しながら作る必要がある。

  • 当然x86で作る。原理的には、x86以外にx64版プラグインも作れるだろうけれど、それに対応したアプリは皆無だろう。
  • 時代が時代なので、非Unicodeのマルチバイト文字セットで作る。
  • dllexportは、例えばMSVCだと既に無くなっているので、コンパイラが新たに提供している命令に置き換える必要がある。
  • cdeclとstdcallを正しく指定する必要がある。正しくないといとも簡単にクラッシュする。仕様書にはPASCALを全般に渡って使用しているが、今はそれだと駄目だった。

Visual Studio 2019 Version 16.7以降でディレクトリ生成を伴うシェーダコンパイルに失敗する

8月頃にリリースされた16.7.1から、現在リリースされている16.7.5まで確認済み。
そう、二か月以上Visual Studio 2019でシェーダがコンパイルできない致命的な状態なのである。

再現手順はとても簡単で、DirectX-Graphics-SamplesのVS2019に対応した適当なリビジョン(タグ10.0.19041.0以降あたり)を取得してきて、VS2019でModelViewerをビルドするだけ。シェーダコンパイル時に大体次のような意味不明なエラーを吐く。プロファイルによってはfxcである場合もある。

dxc failed : error code 0x80070459.

詳細な条件は次の通り。

  • hlslファイルをソリューションエクスプローラーに設定して、本来なら正常にコンパイルできる設定にしてある
  • 「ヘッダー ファイル名」または 「オブジェクトファイル名」にディレクトリ生成を伴うパスを指定している
    • 例えば、CompiledShaders\%(Filename).h や $(OutDir)CompiledShaders\%(Filename).cso は該当する
    • 一方、 $(OutDir)%(Filename).cso  はディレクトリを生成しないので該当しない

この原因は以下に報告されている。

Typo in FXC Target in VS 16.7.1 (Developer Community)

要するに、「 FxcOutputs 」と記述されるべき設定が「 _FxcOutputs 」とタイポされているというあまりにもお粗末で下らないバグだ。

幸いにも、プログラムによるバグではなく、設定ファイルによるバグであるため、手元で修正することが出来る。
Visual Studio 2019のインストール場所を変更していない場合、次のファイルをテキストエディタ開く。Community以外の場合も適宜読み替えてほしい。

C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\MSBuild\Microsoft\VC\v160\
Microsoft.CppBuild.targets

「 _FxcOutputs 」で検索すると一か所該当する箇所があるので、これを「 FxcOutputs 」に変更し保存する。ただし、管理者権限が必要である。

重複した別の報告(HLSL Shader Compiler fails to create output directory for header files)のリプライによると、Preview版では修正されたようだが、こんな致命的で馬鹿げたバグは即座にhotfixがリリースされるべきだろう。

Asynchronous Capture Screen on Unity 2019.3

Unity 2019.3から、あれこれ自作せずともやっと、ようやく、悲願の非同期スクリーンキャプチャが出来るようになりました。

前提知識として、Unity APIの呼び出しは、一部のAPIを除いてメインスレッドからの呼び出しのみが許可されています。レガシーな同期アプローチは検索すると吐いて捨てるほど出てくるのでそっちを見てください。

スクリーンキャプチャの流れは3工程あり、バージョンアップを経て段階的に非同期可能になっています。

  1. レンダーテクスチャのシステムメモリへの読み戻し
  2. 画像ファイルフォーマットへのエンコード
  3. ファイル書き込み

1は、ScreenCapture.CaptureScreenshotIntoRenderTexture が2019.1で追加され、ようやく非同期でシステムメモリに読み戻せるようになりました。

1で読み戻したメモリはレンダーテクスチャに指定したフォーマットのバイト配列(NativeArray<byte>)ですが、これを一般的な画像ファイルフォーマットにエンコードするには 2017.1から追加されているImageConversionクラスのAPI、ImageConversion.EncodeToPNG など(フォーマット別)を使用します。しかし、これは引数にバイト配列ではなくTexture2D を要求する上に、メインスレッドのみ呼び出し可能なので同期処理を避けられません。
流石に使えないAPIだと思ったのか、2019.3 でバイト配列(byte[])を使用する ImageConversion.EncodeArrayToPNG が追加されました。リファレンスにも”This method is thread safe.”と書かれていて、メインスレッド以外からの呼び出しが許可されています。

3は、.Net APIで以前から非同期可能です。

これらを組み合わせれば、”ほぼ”非同期にスクリーンキャプチャを行えます。

 

今後改善して欲しいところ。

  • ScreenCapture.CaptureScreenshotIntoRenderTexture リファレンスのサンプルコードが間違っている。
    using (var imageBytes = request.GetData<byte>()) で使用されているが、ユーザがこのNativeArrayに対してusingや明示的なDisposeの呼び出しを行うと、例外が出力される(InvalidOperationException: The NativeArray can not be Disposed because it was not allocated with a valid allocator.)。AsyncGPUReadbackRequest が管理しているはず?
  • NativeArray<byte>からbyte[]の変換をメインスレッドで行う必要があるが、そこで巨大なマネージドメモリのアロケートが走る。
    NativeArray<byte>のまま処理するAPI、つまりJob System with Burstでエンコードを行って欲しい。
  • ImageConversion.EncodeArrayToPNG のエンコード済みバイト列として巨大なマネージドメモリのアロケートが走る。
    必要メモリ量の計算と、事前確保したメモリを使用するAPIが欲しい。NativeArrayでの非同期ファイル読み書きをサポートして欲しい。
  • 要するに、最初から最後までNativeArrayのまま処理が完結するようにして欲しい。
  • ImageConversion.EncodeArrayToPNG は出力フォーマットの指定ができない。つまり入力フォーマットと出力フォーマットは同一になる。また、RGBAのデータをRGBしかもたないJPGにすると、rowBytesを指定してもRGBAからRGBへ変換してくれないようだ。
  • 上下が反転している。グラフィクスAPI依存?ImageConversion.EncodeToPNG はTexture2D の段階でそれが打ち消されている?
    ユーザが面倒を見るべき処理ではないので、内部で処理して欲しい。

 

追記:
2019.4で ImageConversion.EncodeNativeArrayToPNG が追加されていました。やったね。

TwitchChatPlugin 1.0 for Yukarinette

TwitchChatPlugin 1.0 on GitHub

TwitchChatPlugin は、ゆかりねっとで音声認識した文章をTwitchの自身のチャンネルに発言することが出来ます。使用にはチャット用OAuthの取得が必要ですが、詳細はREADMEを読んで下さい。

streamingラグを考慮した遅延送信機能と、スパム抑制機能を追加しています。遅延時間は自身の配信設定やTwtichサーバーとのラグを考慮しながらいい感じに調整してみてください。