3Dグラフィックスにおけるウェーブレット
Wavelets in 3D Graphics (comonad.com)
要約
ウェーブレットは、特にコンピュータグラフィックス分野で多解像度解析やデータ圧縮に有用なツールとなっています。この記事では、開発中の3Dポリゴンゲームエンジンにおける低コントラストテクスチャの圧縮にHaarウェーブレットを適用する方法に焦点を当てています。テクスチャメモリの制約と、ミップマップ生成におけるスタッター問題を解決するため、Haarウェーブレットの特性を利用した非標準的な画像分解手法が提案されています。
全文翻訳
3Dグラフィックスにおけるウェーブレット
ウェーブレットは、一般の数学分野、特にコンピュータグラフィックスにおいて、注目を集めるトピックとなっています。これらは、データセットのマルチ解像度解析やデータ圧縮に役立つツールです。いくつかの一般的なウェーブレット基底関数やスケーリング関数が存在します。ここでは、私が開発中の3Dポリゴンゲームエンジンにおける低コントラストテクスチャの圧縮へのHaarウェーブレット基底とその応用を中心に説明します。この応用では、Haar基底のこれらの両方の特性を活用します。
用語
この記事では、テクスチャとは、2^nテクセル幅、2^nテクセル高の32ビット画像であると定義します。テクセルとは、テクスチャのピクセルを画面に投影する前の業界用語です。各画像にはミップマップも格納されます。各ミップマップは前のものより2のべき乗だけ小さく、前の画像からのアンチエイリアシングによって生成されます。したがって、128x128のテクスチャのミップマップセットは、64x64、32x32、16x16、8x8、4x4、2x2、1x1となります。通常、最低の3〜4つのミップマップレベルは、それに見合うだけの維持の手間がかからず、ゲームでは遠すぎるポリゴンを画面に表示しないようにシーンを制約できることが多いため、しばしば省略されます。また、それらが表示される場合でも、距離の小さなエイリアシング問題よりも、表示する必要のある小さなポリゴンの数自体の方が大きな問題となるでしょう。ミップマップを格納すると、テクスチャのストレージ要件が1/3増加します。
問題
典型的なテクスチャサイズは256x256です。テクセルあたり4バイトとすると、この単一の画像はテクスチャあたり256KBのRAMを消費します。実用的なシーンでは、一度に約1ダースのテクスチャが表示され、マップ全体に最大で100個のテクスチャが配置されますが、それらはすぐに表示されない場所にあります。すべてを常にロードしておくには、ゲームロジック、ライトマップ、ジオメトリはさておき、テクスチャとミップマップデータだけで約200MBのメモリが必要になります。言うまでもなく、この時点で一般的なエンドユーザーのコンピュータにそれだけのメモリを期待するのは非現実的です。
考えられる解決策
1つの解決策は、画像を8ビットパレット表現に縮小することです。これにより、メモリ要件は約50MBに削減され、マップ全体にテクスチャがどのように配置されるかのコヒーレンスを利用できれば、ディスクとの間で合理的にスワップできます。しかし、空間的コヒーレンスやキャッシングを一切利用できない場合、表示をレンダリングし続けるためにテクスチャを探し出す必要が生じた際の突然のヒットによるスタッターが発生します。このスタッターは非常に否定的な心理的影響を与えます。プレイヤーとして、ゲームをプレイしていることを突然思い出させられ、没入感が失われます。フレームレートの一貫性は、最良の場合のパフォーマンスよりも全体的に重要であるため、パフォーマンスを平準化する要因が必要です。スタッターは、テクスチャをスワップするためにエンジンがディスクにアクセスする必要があるという事実によって悪化します。ディスクアクセスはメモリから直接テクスチャにアクセスするよりも数桁遅くなります。また、パレット表現のテクスチャでは、画像格納のためにカラースペースのサブセットが小さくなり、変換で多くの品質を失いがちであり、標準的な6ビットカラーコンポーネントのパレットを使用している場合でも、再構築されたテクセルは最良でも18ビットにしかなりません。アルファ(半透明)チャンネルをパレット表現に格納したい場合、さらに複雑な問題が発生します。
別の選択肢は、メモリ内にテクスチャの圧縮表現を格納し、そこからミップマップを派生させることです。このアプローチの問題点は、256x256のテクスチャから32x32のミップマップしか必要ない場合でも、テクスチャ全体を解凍し、すべてのミップマップレベルを抽出する必要があることです。通常、特定のテクスチャの低レベルミップマップは、高レベルミップマップよりも前に必要になります。これは、シーン内を歩くにつれて、遠くのサーフェスが視野に入り、近づいてくるにつれて、より詳細(高レベルミップマップ)が必要になるため直感的です。このアプローチでは、一度にすべての負荷をかける必要があります。これによりスタッターが発生します。JPEGスタイルの圧縮は効果的に使用でき、通常は以下で説明するアプローチよりも高い圧縮率を得られます。残念ながら、その「すべてか無か」の性質は私のニーズには不向きです。また、より良い圧縮は、画像の各8x8ブロックに対して逆DCTを実行する必要があるというコストを伴います。Feigの方法(現在Intelプロセッサで最も効率的な公開されている方法)を使用すると、このプロセスはチャンネルあたり54回の乗算、462回の加算、462回のシフトを必要とします。比較すると、Haarを使用すると、同じ8x8ブロックの解凍にはチャンネルあたり256回の加算が必要です。
Haar基底の概要
これは、Haar基底がどのように機能するかを直感的に理解するためのものです。以下は、厳密な数学的証明や検討を意図したものではありません。
次のような2^n個のサンプルがあるとします: { 11, 1, 1, 7 }
サンプルをペアにして平均化します: { (11+1)/2, (1+7)/2 } = { 6, 4 }
1つの値になるまで繰り返します: { (6+4)/2 } = { 5 }
[画像: サンプル11, 1, 1, 7はペアで平均化され、6と4になり、さらにスケーリング値5になります。]
図1. ペアごとの平均とスケーリング値。
このツリーの最上部にある値(図1)がスケーリング値です。
次に、ペアにした階層を下に再帰します。各レベルで、現在のノードの右側のチャイルドの値を現在のノードの値から減算します。ツリーのリーフノードには再帰しないでください。
[画像: レベル0に1、レベル1に5とマイナス3を持つ係数ツリー。]
図2. レベルごとのウェーブレット係数。
あるレベルのツリーには2^n個の値があります。これらの値がウェーブレット係数です。これらの値を使用すると、この操作は可逆であるため、元のサンプルセットを再構築できます。
階層のm番目のレベルには2^m個の係数があります。このセットにスケーリング値を加えると、元のデータセットと同じ数のサンプルが得られます。ただし、Haar形式に変換されると、数値は前のレベルからの変化を示すようになります。
再構築は簡単です。スケーリング値とレベル0の係数から始めます。係数にスケーリング値を加えると左側のチャイルドが生成され、スケーリング値から減算すると右側のチャイルドが生成されます。これらのノードを取得し、ツリーを下に繰り返します。
[画像: 5から始まり、次に5プラス1と5マイナス1、次に6プラス5、6マイナス5、4プラスマイナス3、そして4マイナスマイナス3となる式ツリー。]
[画像: 評価されたツリー:5、次に6と4、そして回復されたサンプル11, 1, 1, 7。]
図3. 再構築:左側は加算、右側は減算。
次に、係数をツリー内のレベルで重み付けします。これは係数を正規化するために行われます。人気のある重み付けメカニズムがいくつかあります。それぞれが異なる用途で有効です。私は、各値を1/sqrt(2^j)(jは係数のツリー内のレベル)で乗算することによる正規化を好みます。
データは次のようになります。
スケーリング値 { 6 }
ウェーブレット係数 { 1, 5, -3}
重み付けされたウェーブレット係数 { 1, 5/sqrt(2), -3/sqrt(2) }
これまでのところ、このプロセスによる圧縮は一切発生していません。変換全体は、4つの値を別の4つの値と、それらから派生したいくつかの重み付けされた値に変換しただけです。
Haarの適用
次のステップは、これを画像圧縮にどのように適用するかを理解することです。画像はサンプルの2次元グリッドであり、前述のような1次元セットではありません。
2つの一般的なアプローチがあります。
標準的な画像の分解では、各行にHaar変換を適用し、次に列ごとに処理してそれぞれを変換します。これはミップマップの再構築には残念ながらあまり役立ちません。なぜなら、2x2のミップマップを抽出するために、画像全体を再構築し、アンチエイリアシングしながら2x2まで戻る必要があるからです。もしそうすると、低レベルのミップマップを再構築する利点はなくなります。
非標準的な分解では、各行を1レベルずつ変換し、次に各列を1レベルずつ変換し、スケーリング関数が残るまで繰り返します。したがって、直感的には、1x1ミップマップ(スケーリング係数)とレベル0の係数セット(1つの行係数と2つの列係数)から2x2ミップマップを抽出し、次にミップマップとレベル1の係数(2つの行係数、4つの列係数)を使用して2x2から4x4ミップマップを抽出できます。これにより、ゲーム内でサーフェスに近づくにつれて画像を段階的に再構築できます。大量のデータに対する突然の要求を回避できるため、スタッターを回避できます。アニメーションの1フレームで、解凍する処理時間がなかったために高レベルのミップマップを待たなければならなかった場合、解凍できるまで低レベルのミップマップを代わりに使うことができます。実際には、テクスチャが準備できていなかったために5fpsまで低下するよりも、一定の25fpsのリフレッシュレートを維持する方が良いことがわかりました。
私はテクスチャの非標準的な分解で作業することを選択しました。これはすべて良いのですが、ここでも、単に数字のセットを別のセットに置き換えただけです。圧縮は発生していません。ミップマップレベルの追加メモリを格納する必要がないという事実を圧縮と見なさない限り、それらは係数セットから画像を再構築する際に派生させることができます。
次のステップは、係数セットを圧縮することです。ウェーブレットの利点の1つは、係数セットへの小さな変更が、復元されたサンプルセットに同様に小さな変更をもたらし、そのエラーを画像全体にうまく分散させるため、このエラーによる目に見える不連続性を回避できることです。
ツリー内のレベルで適切に重み付けした後、全体的な画像への寄与が少ない項を、最も小さい重み付けされた係数を繰り返し破棄する(それを0に置き換える)ことで削除できます。これにより、指定された係数の数または削除する最大重みに達するまで続けます。(このヒューリスティックは過去に非常に役立つことが証明されています。なぜなら、一部の画像は他の画像よりも圧縮に対して本質的に寛容だからです。これにより、圧縮段階をインタラクティブなプロセスにせざるを得なくなりましたが、結果として芸術的な制御も向上します。
係数を0に置き換えることは、境界付きの最大誤差を提供する体系的な方法を提供します。残念ながら、それはあまり圧縮可能なデータセットを提供しないことも判明しました。残りの係数の量子化が必要でした。0置換ステップの後、係数のセットをニューラルネットワークに通します。このネットワークは、重み付けされた形式を使用して残りの係数の量子化を実行します。各係数を等しく数えるのではなく、ウェーブレット係数の重みに基づいて選択を重み付けすることに注意してください。ただし、ディスクに格納する際には、重み付けされていない形式を使用します。実際には、値における冗長性が正確な重みよりも高いことがわかり、私の場合は、量子化された値を重み付けなしで格納することで、より良い圧縮率が得られました。係数を「パレット」に量子化するためにニューラルネットワークを実行することは、やりすぎのように思えるかもしれませんが、私はすでに32ビットの元の表現からパレットテクスチャに変換するためのルーチンを書いていました。次に、より小さい量子化係数と出現回数カウンターのセットをハフマンツリージェネレータに渡し、次にデータをハフマン圧縮機に通します。これらはすべてプリプロセスであるため、処理時間は多かれ少なかれ無関係です。ただし、ゲームエンジンの変更がより面倒で流動的でなくなります。量子化ステージをスキップして係数を直接QM算術コーダーに渡すことで、わずかに優れた圧縮を得ることができましたが、解凍速度が大幅に低下し、私の目には3%の圧縮改善のために6倍の時間がかかることとIBMの特許に対処することは価値がありませんでした。
欠点としては、圧縮されたテクスチャはサーフェスキャッシングアルゴリズムの複雑さを劇的に増加させ、ゲームエンジン自体の広範な変更を大幅に困難にします。また、圧縮パイプライン自体に予想以上に多くの時間を費やしました。今思えば、最終圧縮段階のために、十分にテストされ、使いやすいインターフェースを備えたzlibなどのライブラリを使用した方が良かったかもしれません。
唯一の本当の問題は、高コントラストテクスチャで発生します。幸いなことに、これらのテクスチャは、ウェーブレットで発生するのと同じ一般的な圧縮アーティファクトがテクスチャのミップマッピングでも見えるため、ポリゴンエンジンでは通常、宗教的に回避されます。これらのアーティファクトは、異方性テクスチャサンプリングなどの技術で回避できますが、この記事の執筆時点では、リアルタイムグラフィックスには十分な速度ではなく、実際には関連性がありません。圧縮はまた、誤差しきい値を高く設定したことに比例して、テクスチャのブロック状性が顕著に増加します。このブロック状性は、バイリニアフィルタリングステップを追加することで軽減できますが、高コントラストテクスチャの問題を増加させます。バイリニアフィルタリングは、自動的にバイリニアフィルタリングを実行できるハイエンド3Dアクセラレータカードにテクスチャを渡す場合に、実際には必要ありません。経験則として、テクスチャは8:1圧縮までアーティファクトに気づかず、35:1圧縮に近づくと使用不可能になり始めました。その間のレベルの使いやすさは、大部分のテクスチャにおけるコントラストのレベルに大きく依存しました。コンプレッサーは、高コントラスト領域と低コントラスト領域が混在するテクスチャをうまく処理しました。ハードな色の変化には比較的高い重みが割り当てられるため、高コントラスト領域は十分な定義を保持し、低コントラスト領域は単にさらにミュートされました。この効果により、壁の看板や技術的なガジェットなどが、変化の頻度が低い背景に対して際立ちます。
ウェーブレットの分野では多くの研究が行われています。Haar基底は、実際にはまったく良いウェーブレット基底ではありません。それは、実質的にパルスの階層であるという不連続性のため醜く、その主な利点は、画像から抽出したり、画像から抽出したりするのが最も速いこと、そして多くのより高度なウェーブレットとは異なり、かなり直感的であることです。
ゲームエンジンの開発中に、ウェーブレットを自分のために機能させるためのいくつかの他の方法を検討しました。非常に高ポリゴン数のサーフェスを圧縮するためのいくつかの基底関数が存在します。残念ながら、実際には、階層を歩き、合理的なレベルのサーフェスデータキャッシングを管理するのにかかる時間は、私の場合に適用されるケースで最適なテッセレーションを事前に計算して使用するよりも、ストレージ要件を上回ります。最終的にはこの種の何かが要求されるでしょうが、現時点ではメモリは処理能力よりも豊富です。このフロントでは、ウェーブレットは少し期待外れでした。
参考文献
E. Stollnitz, T. Derose, D. Salesin. "Wavelets for Computer Graphics", ISBN 1-55860-375-1 Morgan Kaufmann Publishers Inc. San Francisco, CA 1996
W. Pennebaker, J. Mitchell. "JPEG: Still Image Data Compression Standard", ISBN 0-442-01272-1 Van Nostrand Reinhold Inc. New York, NY 1993
D. Morgan. "Numerical Methods for DSP in C", ISBN 0-471-12232-2 Jon Wiley & Sons Inc. Canada 1997
B. Hubbard. "The World According to Wavelets", ISBN 1-56881-047-4 AK Peters Ltd. Welleskey, MA 1996
Foley, van Dam, Feiner, Hughes, "Computer Graphics: Principles and Practice, 2nd Ed. in C" ISBN 0-201-84840-6 Addison-Wesley Publishing Co. Reading, MA 1996