メッシュ復元アルゴリズムの概要

今回は、点群のデータを入力として、表面メッシュを復元する手法について紹介する。この内容は以下の2つの論文を元にした内容となっている。

• Carr et al. 2001, “Reconstruction and Representation of 3D Objects with Radial Basis Functions”
• Morse et al. 2001, “Interpolating Implicit Surfaces From Scattered Surface Data Using Compactly Supported Radial Basis Functions”

これらの論文はいずれも、三次元空間上に定義された陰関数 $f: \mathbb{R}^3 \rightarrow \mathbb{R}$を放射基底関数 (RBF, radial basis function) により補間することで表現する。陰関数が表現できたら、あとはマーチング・キューブ法などを用いて、陰関数のデータを表面メッシュに変換する。

RBFによる陰関数場の構成

RBFはある空間上の1点からの「距離」だけに依存する関数で、中心点 $\mathbf{c} \in \mathbb{R}^n$と関数の値を評価する点$\mathbf{x} \in \mathbb{R}^n$の間の距離$r = | \mathbf{x} - \mathbf{c} |$を用いて定義される。

RBFは距離だけに依存する関数一般を指すので、多様な定義の仕方が可能であり、応用に応じていろいろな定義が用いられる。例えば、

ガウス関数
\(\phi(r) = \exp(-\beta r^2)\)

薄板スプライン関数 (thin-plate spline)
\(\phi(r) = r^2 \log(|r|)\)

などがその代表例として知られる。メッシュ復元のためには、入力の点群それ自体を中心点としてRBF関数を定義し、その重み付き和により陰関数$f$を近似する。すなわち、

\[f(\mathbf{x}) = \sum_{i=0}^{N-1} w_i \phi(\| \mathbf{x}_i - \mathbf{x}\|)\]

のような形で、陰関数を表現し、$f(\mathbf{x}) = 0$となる等値面を復元される曲面とする。

上記の陰関数の定義にはパラメータとして$w_i$が含まれるので、これを入力点群のデータから求めることが必要となる。各入力頂点には、その点で陰関数が取るべき値がいくつになるのかを表す参照値$d_i$を与えておく。

この時、入力の点群は欲しい表面メッシュ上にあると考えられるので、$f(\mathbf{x}_i)$の値は全て0になるべきで、したがって$d_i = 0$であると考えられる。ところが、このような場合には、全ての$i$について$w_i = 0$となるような単純な解により、必要な条件を満たされてしまう。

そこで、入力の点群と法線の情報を用いて、点を法線方向に沿って正と負の方向にそれぞれ動かしたオフセット点の陰関数の値を$d_i = \{ 1, -1 \}$として入力点群に加える。この拡張された点群の情報を用いてRBF関数による近似を行う。

実際に、上記の陰関数$f$がオフセット点を含む入力頂点上で参照値と等しい値を取るとすると、全ての頂点に対する等式をひとまとめにすることで、連立一次方程式を得ることができる。

例えば、点群$\mathcal{X} = \{ \mathbf{x}_{j} \}_{j=1}^{N}$と、それに対応する符号付き距離関数の値$\{ {d}_{j} \}_{j=1}^{N}$が与えられているとすると、各点$\mathbf{x}_i$に対する重み係数$w_i$を要素とするようなベクトルを$\mathbf{w} \in \mathbb{R}^N$, 同様に$d_i$を要素とするようなベクトルを$\mathbf{d} \in \mathbb{R}^N$, また行列の$ij$成分が$\phi(|\mathbf{x}_i - \mathbf{x}_j|)$となるような行列を$\mathbf{A}$とすることで、解くべき連立一次方程式は、

\[\mathbf{A} \mathbf{w} = \mathbf{d}\]

となる。以降で詳しく説明する通り、この連立一次方程式に現れる係数行列$\mathbf{A}$は一般的には密行列である。一方で、入力されてくる点群は多い場合で数百万から数千万にもなりうるため、実用的には数値的に得ことが難しい場合が多い。そのため、RBFとして有限の狭い定義域を持つコンパクトサポートRBFを用いて、$\mathbf{A}$の成分の多くが0、すなわち疎行列になるように調整して、計算量と表現力のトレードオフを取ることが一般的である。

k-d木による最近傍点の探索

点群からメッシュを復元では、入力頂点を法線方向にオフセットすることで、その点での参照値が$\{ -1, 1 \}$となるような点を追加すると述べたが、例えば、以下の論文の図3(a)などのように、曲面が近い距離で向かい合っているような場合には、頂点を一定距離でオフセットした際に、それが曲面が囲む領域の内側に入り込んでしまう可能性がある。

• Carr et al. 2001, “Reconstruction and Representation of 3D Objects with Radial Basis Functions”

このような場合に、整合しない陰関数の参照値を与えてしまうことを防ぐため、頂点を法線方向にオフセットしたあと、入力の点群の中から、最もオフセット後の点の位置に近い頂点を探索してきて、その頂点の位置と法線の方向から実際の参照値$d_i$を計算する。

ここで重要となるのは、数万点程度の入力点群の中から、どのように最近傍となる頂点を効率的に探し出すか、ということである。このような効率的な近傍点の探索には、木構造をはじめとするデータ構造がよく用いられる。今回は、このようなデータ構造の中から前回のICPの項でも用いたk-d木を採用する。

陰関数が求まれば、あとはマーチング・キューブ法などにより、曲面を三角形メッシュなどとして取り出すことが可能となる。以降では、これらのステップをより詳しく見ていく。