3Dグラフィックスにおけるウェーブレット

ウェーブレットは、一般的に数学のホットなトピックであり、特にコンピュータグラフィックスでは注目されています。これらは、データセットの多解像度解析やデータ圧縮に役立つツールです。いくつかの一般的なウェーブレット基底関数やスケーリング関数が存在します。ここでは、Haarウェーブレット基底と、私が開発中の3Dポリゴンゲームエンジンにおける低コントラストテクスチャの圧縮への応用を中心に説明します。このアプリケーションでは、Haar基底のこれらの特性の両方を活用します。 用語 この記事の目的のために、テクスチャは32ビット画像であり、幅2^nテクセル、高さ2^nテクセルです。テクセルとは、画面に投影される前のテクスチャのピクセルに対する業界用語です。各画像にはミップマップも格納されています。各ミップマップは前の画像よりも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の方法を使用すると、チャネルあたり54回の乗算、462回の加算、6回のシフトを必要とします。Feigの方法は、現在Intelプロセッサ上で最も効率的な公開されている方法です。比較すると、Haarを使用すると、同じ8x8ブロックの解凍にはチャネルあたり256回の加算が必要です。 Haar基底の概要 これは、Haar基底がどのように機能するかを直感的に理解するためのものです。以下は、厳密な数学的証明や主題の検討を意図したものではありません。 2^n個のサンプルがあるとします（例: { 11, 1, 1, 7 }）。 ペアをサンプリングし、平均を取ります。 { (11+1)/2, (1+7)/2 } = { 6, 4 } 1つの値になるまで繰り返します。 { (6+4)/2 } = { 5 } 図1. ペアごとの平均とスケーリング値。このツリーの最上部（図1）の値がスケーリング値です。 次に、ペアにした階層を再帰的に下降します。各レベルで、現在のノードの右側の子の値から現在のノードの値を引きます。ツリーのリーフノードには再帰しません。 図2. レベルごとのウェーブレット係数。あるレベルには2^n個の値があります。これらの値がウェーブレット係数です。これらの値があれば、元のサンプルセットを再構築できます。なぜなら、この操作は可逆だからです。m番目の階層レベルには2^m個の係数があります。スケーリング値をこのセットに追加すると、元のデータセットと同じ数のサンプルが得られます。ただし、Haar形式に変換すると、数値は前のレベルからの変更を示すようになります。 再構築は簡単です。スケーリング値とレベル0の係数から始めます。係数をスケーリング値に加算して左側の子を生成し、スケーリング値から減算して右側の子を生成します。それらのノードを取得し、ツリーを下降して繰り返します。 =図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ミップマップを抽出し、次にミップマップとレベルの係数を使用して4x4ミップマップを2x2から抽出できます。