レベルセット（データ構造）

コンピュータ サイエンスでは、レベルセット データ構造は、離散的にサンプリングされた動的レベル セット関数を表すように設計されています。

この形式のデータ構造の一般的な用途は、効率的な画像レンダリングです。基礎となる方法は、境界から広がる符号付き距離フィールドを構築し、このフィールド内の境界の動きを解析するために使用できます。

強力なレベルセット法は、OsherとSethian 1988によるものです。^[1]しかし、値の密なd次元配列を介した単純な実装では、時間とストレージの複雑さの両方がになります。ここで、は領域の空間範囲の断面解像度であり、は領域の空間次元の数です。 ${\displaystyle O(n^{d})}$${\displaystyle n}$${\displaystyle d}$

1995 年に Adalsteinsson と Sethian によって導入された狭帯域レベル セット法^[2]は、ほとんどの計算をインターフェイスのすぐ周囲のアクティブボクセルの細い帯に制限し、ほとんどの操作で 3 次元の時間計算量を に削減しました。アクティブ ボクセルのリストを再構築するために、狭帯域構造を定期的に更新する必要がありましたが、これにはボリューム全体のボクセルにアクセスする操作が必要でした。この狭帯域スキームのストレージ計算量は依然として狭帯域ドメイン エッジでの微分構成には、ソリューションを安定させるために慎重な補間とドメイン変更スキームが必要です。^[3]${\displaystyle O(n^{2})}$${\displaystyle O(n^{3})}$${\displaystyle O(n^{3}).}$

この時間的複雑さは、1998 年に Whitaker によって導入された近似的な「スパース フィールド」レベル セット法で解消されました。 ^[4]スパース フィールド レベル セット法では、一連のリンク リストを使用して、インターフェイス周辺のアクティブ ボクセルを追跡します。これにより、大きなオーバーヘッドを発生させることなく、必要に応じてアクティブ領域を段階的に拡張できます。スパース フィールド レベル セット法は、時間的に一貫して効率的ですが、それでもストレージ スペースが必要です。実装の詳細については、 ^[5]を参照してください。 ${\displaystyle O(n^{3})}$${\displaystyle O(n^{2})}$${\displaystyle O(n^{3})}$

2003 年に Bridson によって導入されたスパース ブロック グリッド法^[6]は、サイズの境界ボリューム全体を、それぞれがボクセルの小さな立方体ブロックに分割します。サイズの粗いグリッドには、レベル セットの狭い帯域と交差するブロックへのポインタのみが格納されます。ブロックの割り当てと割り当て解除は、サーフェスが変形に合わせて伝播するにつれて発生します。この方法のストレージ複雑度は と最適ではありませんが、密なグリッドに固有の一定時間のアクセスが維持されます。 ${\displaystyle n^{3}}$${\displaystyle m^{3}}$${\displaystyle (n/m)^{3}}$${\displaystyle O\left((nm)3+m^{3}n^{2}\right)}$

1999 年に Strain によって導入され^[7]、Losasso、Gibou、Fedkiw [8] によって改良され、最近では Min と Gibou [9] によって改良された octree^レベルセット^法では、葉ノードに符号付き距離値が含まれるネストされた立方体のツリーを使用します。octree レベル セットでは現在、十分な精度を得るために、インターフェイス (つまり、狭帯域) に沿って均一に改良する必要があります。この表現は、ストレージの点では効率的であり、アクセス クエリの点では比較的効率的です。octreeデータ構造に対するレベル メソッドの利点は、レベル セット メソッドを使用する一般的な自由境界問題に関連する偏微分方程式を解くことができることです。CASL 研究グループ^[10]は、計算材料、計算流体力学、電気運動学、画像誘導手術および制御の分野でこの研究分野を開発してきました。 ${\displaystyle O(n^{2}),}$${\displaystyle O(\log \,n).}$

2004 年に導入されたランレングス符号化( RLE) レベル セット法^[11]は、 RLE 方式を適用して、狭帯域から離れた領域を符号表現のみに圧縮し、狭帯域を完全な精度で保存します。狭帯域の順次走査は最適であり、ストレージ効率はオクツリー レベル セットよりもさらに向上します。加速ルックアップ テーブルの追加により、高速ランダム アクセスが可能になります (r は断面あたりの実行数)。RLE 方式を次元再帰方式で適用すると、さらに効率が向上します。これは、ニールセンとムセスの同様の DT-Grid によって導入された手法です^{[12] 。}${\displaystyle O(\log r)}$

ハッシュテーブルローカルレベルセット法は、2011年にEyiyurekliとBreen ^[13]によって導入され 、2012年にBrun、Guittet、Gibou ^[14]によって拡張されましたが、狭帯域レベルセット法と同様に、インターフェイスの周囲のバンド内のレベルセットデータのみを計算し、同じバンド内のデータのみを保存します。ハッシュテーブルデータ構造が使用され、データへのアクセスを提供します。しかし、Brunらは、彼らの方法は実装が簡単である一方で、四分木実装よりもパフォーマンスが悪いと結論付けています。${\displaystyle O(1)}$

現状では、[...] レベルセットアルゴリズムにはハッシュテーブルデータ構造よりも四分木データ構造の方が適しているようです。

効率が悪くなる主な理由は次の 3 つです。

1. 正確な結果を得るためには、インターフェースから遠いグリッド ノードが存在しないことを相殺する、インターフェースに近いかなり大きなバンドが必要です。
2. ローカルグリッドの外縁部における外挿手順によってパフォーマンスが低下し、
3. バンドの幅によって時間ステップが制限され、メソッドの速度が低下します。

2005年にCorbett ^[15]はポイントベースのレベルセット法を導入しました。レベルセットの均一なサンプリングを使用する代わりに、移動最小二乗法を使用して、整理されていないポイントサンプルのセットから連続レベルセット関数を再構築します。