FrontPage 新規一覧検索ヘルプ RSS ログイン

Fast Hierarchical Importance Sampling With Blue Noise Propertiesの編集

Victor Ostromoukhov,  Charles Donohue,  Pierre-Marc Jodoin. Fast Hierarchical Importance Sampling With Blue Noise Properties.

http://www.iro.umontreal.ca/~ostrom/publications/

!タイトル
ブルーノイズ性質を利用した高速階層インポータンスサンプリング

!Abstract 日本語訳
本論文では、二次元領域上にインポータンスの密度が与えられているときに、優良なサンプリングパターンを効率的に生成するための、斬新な手法を提案します。ペンローズタイリング(Penrose tiling)を階層的に細分割していきます。そして十分に多いサンプル点の数を生成します。これらの点は、フィボナッチ数系(Fibonacci number system)を用いて番号付けられ、この番号はインポータンス密度の局所値に対してサンプルをしきい値化するのに用いられます。サンプリングパターンのスペクトル特性を改善するために、緩和法を用いて前計算により得られた補正ベクトル(correction vectors)を用います。本手法は決定論的であり非常に高速です。サンプリング時間は、必要なサンプルの数に線形に増えます。インポータンスベースの環境マップで我々の手法を説明しますが、本手法は、光輸送計算、デジタルハーフトーン、ジオメトリ処理、各種レンダリング手法など、コンピュータグラフィックの非常に多くの種類の応用にも用いることができるほど多様的な手法です。

!論文日本語訳とか概要とか。

!1. 導入
サンプリング(という問題)は、コンピュータグラフィックスのいたるところで現れます。多くの研究者たちが、レイトレーシング、モンテカルロパストレーシング、モーションブラー、ジオメトリ処理(geometry processing)、デジタルハーフトーン化などのアプリケーションにおいて、サンプリングの性質が達成される結果の品質にどのように影響を与えるか、について研究してきました。

今日では、ブルーノイズフーリエスペクトルをもつ等方性の二次元サンプリングが、幅広い用途に適していると認知されていす。たとえば [Cook 1986], [Ulichney 1988], [Shirley 1991], [Mitchell 1991], [McCool and Fiume 1992], [Glassner 1995], [Hiller et al. 2001], [Kolling and Keller 2002], [Kolling and Keller 2003] を参照してください。

通常、これらのグラフィックスの応用では、インポータンスに比例したサンプルの分布が必要となります。ここでインポータンスはサンプリングの前にすでに得られているものです(たとえば サーフェスのBRDF、ライトエネルギーの分布、幾何的な性質など)。

ブルーノイズによる二次元インポータンスサンプリングの問題は、以下で定義することができます。

*領域 D 上に、解析的な関数もしくは離散値の配列の形としてインポータンス密度(importance density) I が'''与えられた'''時に(ここで一般性を失うことなく、0 <= I(x,y) <= 1, ∀(x,y) ∈ D となるように I を正規化することができます。)
*サンプルの局所的な密度(局所的な計算による、単位面積あたりのサンプルの数)がインポータンス密度 I に比例するように、離散的なサンプルの集合を'''求める'''こと。またこのときそのフーリエスペクトルが以下を示していること。(a) 低い角度領域の異方性。(b) 放射状要素の特徴のあるブルーノイズプロファイル。つまり DC 項まわりは低い強さの環、サンプル間の平均距離を示す部分はに高い強さの環形(annulus)、そして環形の外側は中程度の強さの環。より詳細は [Ulichney 1987], [Hiller et al. 2001] を参照。

この問題を解くために、多くの多様な技法が発案されてきました。それらの手法のうちの緩和法は、注目すべき品質を生成することができます。とくに、ルロイドの緩和法(Lloyd's relaxation) [Lloyd 1983] とその変種は、セントロイダルボロノイ分割(centroidal Voronoi tessellations)を生みました。

しかし残念ながら、この品質に対して支払わなければならない価値は高いものです。
緩和法は本質的に低速な手法です。なぜなら緩和法では、各点の近傍点をすべての点から求める問題を、ほとんどの場合反復的に解く必要があるからです。最も進歩的で最適な実装でも、それでも低速なままです。ルロイドの緩和法のハードウェア支援による実装 [ Hoff et al. 1999 ] は高速ですが、しかしフレームバッファの解像度に制限があります。

いくつかの技法は、[McCool and Fiume 1992] で提案されているような手法のような、確率論的サンプリング(stochastic sampling)(ダーツ投げ(dart throwing))のたぐいを利用しています。確率論的サンプリングでは、ランダムな点が前回の点の近接度(proximity)に応じて追加さたり棄却されたりします。これらの手法は収束が遅いため、最高でもルロイドの手法と同程度のオーダになります。

以上の手法は強く降下的なもので、初期の点群にとても影響を受けます。

誤差拡散法([Ulichney 1987], [Ostromoukhov 2001], [Zhou and Fang 2003] を参照)として知られる、デジタルハーフトーン化で用いられているアプローチは、各点のかなり制限された近隣のみを探索するため、非常に高速です。

ジオメトリ処理における誤差拡散の効率的な利用も行なわれてきました [Alliez et al. 2002]。誤差拡散の主な欠点は、操作対象となる要素が本質的に離散的であるということです。つまり固定の空間的な解像度を持つ矩形のタイルでなければならないというこです。このため、誤差拡散法をコンピュータグラフィックスのサンプリング技法の一般的な用途として利用するのにはをかなり制限があります。なぜならコンピュータグラフィックスではしばしば多重解像度サンプリング(multi-resolution sampling)が必要となるからです。この欠点は明示的に [Surazhsky et al. 2003] で示されました。この論文ではルロイドの緩和法が誤差拡散に適していると示されています。

我々の手法と実行時間の点で比較することができるもう一つの高速なサンプリング技法は、確率密度から生成された累積密度関数(cumulative density function, CDF)を、、層別モンテカルロ(stratified Monte Carlo)法を利用してサンプルすることです。このようなアプローチは要求される局所的密度を反映して点を生成しますが、図 13 のように望まれるブルーノイズ分布には従いません。最近になり、 [Second et al. 2002] が、NPR の分野でグラフィックスプリミティブを分布させるために、よく知られているハルトン列(Halton sequences)とソボル列(Sobol sequences)などの低食い違い量列(low-discrepancy sequence)([Niederreiter 1992] 参照)を CDF と組み合わせて用いることで似たようなアプローチを利用しました。この決定論的なアプローチは結果が約束されてはいますが、多目的に利用できるという確信を得るには至りませんでした(図 13 参照)。

本論文では、斬新なペンローズタイル貼り(Penrose tiling)に基づいたインポータンスサンプリング技法を導入します。この手法は既存の技法よりもいくつかのアドバンテージがあります。この手法はポイントサンプリングのたぐいに含まれます。つまり、各点は他の点とは独立して処理されます。各点の扱いはシンプルで計算量も高くはありませんので、我々のアルゴリズムは非常に高速であることが保証されています。さらに、オフラインの最適化と特別に設計された参照テーブル(lookup table)により、サンプリングの品質は高く、重心ボロノイ分割(centroidal Voronoi tessellations)の品質に達するほどです。
参照テーブルのサイズは小さいです(典型的なものでは 1K 以下)。データ依存の計算は必要ありません。我々の技法は多重解像度であり、高ダイナミックレンジ画像(high dynamic range images)に対してうまく適用することができます(これは節 5 で説明します)。

本論文の残りは以下のように構成されています。節 2 では、いくつかの歴史的な事実とペンローズタイル貼りについて再説明を行ないます。節 3 では、我々のサンプリングシステムの核となる部分について述べます。節 4 では、すべてのインポータンスのレベルで、ほぼ完全なブルーノイズフーリエスペクトルを生成する先進的な緩和法を用いて、基本的な技法をより豊かなものにします。節 5 では、ケーススタディとして、提案する技法をインポータンスベースの環境マッピングに適用します。最後に、節 6 と 7 では、将来の研究について議論し、いくつかのまとめを引き出します。

!2 ペンローズタイル貼り(Penrose Tiling)

ペンローズのタイル貼りの歴史は非常に魅力的なものです。その歴史は、17 世紀の天文学者(astronemer)であり数学者(mathematician)でもあるヨハネス・ケプラー(Johannes Kepler)が行なった研究までさかのぼります。彼は、著書'''宇宙の和声(調和)(Harmonice Mundi)'''で、正則的な多角形でのいろいろなタイル貼りの模様を出版しました。それらのうちの一つである、図 2(左) に示されるものは、長い間多くの数学者のイマジネーションを刺激してきました。正則的な五角形、十角形、そして五芒星のみを用いて、タイル貼りすることは可能なのか? ケプラーの図形に従えば、ラベル Aa の部分に見られるような奇妙なピーナッツ型の形状("モンスター"(monsters))を許すのであれば、それは可能になります。

1970 年代初期、近代的な物理学者で数学者であるロジャー・ペンローズ(Roger Penrose)は、ケプラーの図形に魅了させられました。そして、彼は似たようなタイルのセットを用いて、平面を非周期的にタイル貼りするように修正を施しました。また彼はそれ以上のことも行ないました。彼は、タイルの辺上にマークを置くなどの特殊なマッチングルール(matching rule)を導入することで、タイルのどんな周期的な配置をも取り除くことができることを発見しました。それでも、タイル貼りには明らかに局所的な並びが見て取れました。このタイル貼りは準周期的構造(aperiodic structure)の一種になります。つまり非周期的な構造はマッチングルールにより引き起こされるということです。ペンローズはこの発見の最初の報告を [Penrose 1974] で発表しました。

続き(2 節中盤以降)を訳す...

タイムスタンプを更新しない

添付ファイル

[ヘルプ]

Fast Hierarchical Importance Sampling With Blue Noise Propertiesの編集

添付ファイル

メニュー

最近の更新

リンク