•
AV
• •
•
•
•
↑ ﹂
an
↑﹂
・工
D
ao
P
•
• •
F i g . 5 . 6 :
:最終再構成における曲面移動5.5. 等高面法による三次元物体モデリング
Objec七
(a)
q
h n
↑ ﹂ ・
‑
工
L
︑
α
w n
︒ ↑ ﹂
七
pn ns
・l
‑ L
e o
o r p p r
0
1ム
a c e
↑ ﹂
︑
G
a o o
D n m(c)
81
S七opping
Da七a
(b)
1
81
( d)
Fig.5.7:停止領域幅の位相に及ぼす影響
5.5. 等高面法による三次元物体モデリング
δ
←
δ‑f 1
oConsolidate cells
Se七 δwith a large value Set ini七ial surface
Surface reconstruction using cons七ant speed七erm
Calculate q
q
> t h
Divide cells
Surface recons七ruc七ion using da七a closeness term
Fig.5.8:処理手順
82
5.5. 等 高 面 法 に よ る 三 次 元 物 体 モ デ リ ン グ 83
在得られている曲面が誤った位相であると判断できるので， 8の値を小さくする.この手続き をqがめ以上になるまで繰り返す.
( 2 )最終再構成
上のステージで得られたモデルは，形状と位相の両方に関して物体曲面の妥当な近似と なっている.今度は，式(5.15)により与えられた運動方程式に切り替え，完全に動きが止ま るまでモデル曲面を変形させていく.この最終ステージは，前ステージでの曲面成長から生 じた局所的な凹凸を除去し，モデリング精度を向上させるために採用されたものである.
5.5.2 計算コストの削減
もう一つの大きな問題に，等高面法そのものが膨大な計算量を要求することが挙げられる.
速度関数F を決定するため，変数領域のすべての点について最近接な曲面点を探索しなければ ならない.例えば，各座標方向の分割セルの個数をNと仮定すると，移動曲面上に約O(N2)個 の点があるから，三次元空間では O(N5)の計算量が要求されることになる.これに対する一つ の手段として，ゼロ等高面の近傍のみ探索を行なうことが可能である.これはnarrow‑bandア ルゴリズムとして知られている [62]・この場合，三次元空間の計算量は O(kN4)に削減され
る.ここで，kはnarrow‑bandにおけるセノレの数を表す.この戦略はかなりのコスト削減を もたらすものの，多くの実際問題に応用するためにはまだ計算量が大きすぎる.
ところで，先に述べたアルゴ、リズムにおける初期再構成ステージの主目的は，位相的に矛 盾しないモデルを生成することであった.そこで，データ点問の距離がセル幅に比べて大き いとき，解像度Nの削減が可能である.この考えに基づき，計算コストをさらに減ずるため の以下の戦略が採用される.
まず，隣接するpxpxp個のセルを一つの大きなセルに統合する.この新しいセルにデータ 点が少なくとも一つ含まれていれば，そのセルは占有されているとみなされる.セルを統合す るための適切なpを選択するため，データ点の間隔Xlが正規分布N(μ1
，
σf)に従うと仮定する.ただし， μIとσ?はそれぞれ，母平均と母分散である.そのとき，確率 P(Xl
>
c)=
0.99を 満足する数cはc~μ l ‑ZO.Olσl (5.21)
となることが統計理論から広く知られている.ただし，標準正規分布における 1%点ZO.Olは 約2.326である.ここでは，データ点間距隣の標本平均 Xlと標本分散
s ?
を計算して，それら を μlとσ?の推定値とみなすことにする.したがって，pの最適値f
をp*
= ま [
l‑ZO.Ol S L] (5.22)5.6. 実験結果 84
とおくことができる.ここで，
[ α ]
は実数α
を越えない最大の整数である.このセル統合戦略 を利用することにより，新しいセルがデータ点を一個以上含む可能性は小さくなる.なお，次 の最終再構成処理の段階では，解像度を元に戻す.以上に述べた本手法のアルゴ、リズムの処理手}I債をFig.5.8に示す.
5 . 6 実験結果
本節では， Fig.5.9に示すように，六角ナットのCADデータをもとに表面点からなるデー タを合成し，これを用いた実験結果を示す.まず，式 (5.22)に現れるパラメータは，まl =
5.10， Sl = 1.22，すなわちp*= 2と求められた.したがって，セノレ統合における近傍サイズ が2x2x2と設定された.
Fig.5.10に，中間結果と最終結果を示す.Fig.5.10(a)に示すように，データを内部に含む 初期閉曲面を与えた.この初期曲面は物体曲面と同相ではないことに注意されたい.停止領 域幅の初期値をま!と比べて十分大きな d= 15と設定し，曲面を等速移動させた結果，位相 的にはまだ正しくないモデル曲面が得られた (Fig.5.10(b)).ここで，検出率qは73.1であ り，しきい値 th
=
95よりも小さい.dを次第に降下させる.Fig.5.10(c)と(d)は，それぞ れ d= 8とd= 6に対する当てはめ過程の結果を示す.d=6に対する当てはめ後に，初めてqの値が th
=
95を上回ったため，そこで初期再構成ステ}ジを終了した.Fig.5.10(e)は，最終再構成ステージでFig.5.10(d)に示した結果を用いることで得られた 最終モデルを示している.表1に，以上の各ステップでの5とqをまとめている.これをもっ とはっきり示すため， Fig.5.10(e)に示したモデルを2倍に拡大したものをFig.5.10(f)に示す.
5 . 7 結び
本章では，偏微分方程式の数値解析法として知られる等高面法を用い，物体の位相に関す る事前知識をもつことなく任意の位相に適応して柔軟に全周型物体モデルを生成する手法を 提案した.本手法の特徴の一つは，スパースな形状データにも対応できることである.また，
Whitaker によって提案された手法[63]と大きく異なる点は，本手法では各データ点がどの視 線方向から計測されたかという情報が事前に与えられなくても物体モデリングが可能なこと である.
85
.21FZ.r
・日 ・u.fH
hr
uパ・芯Jyl‑‑ ?"即 日 ・
M3・
. ︐ . .
・ ¥ い パ ・ . 1︑‑ q一
⁝ い
eI h⁝ ・ 一 " ↑ ・ ・ 九 日 一 一
uz
・ ⁝
・
J"一 日 ・ ・
rz
‑J
・se‑‑P ‑‑
U J h '
‑
目 I
E︐
•
••
• . .
. . .
. . . .
. . .
.. '﹃.
1. .. .
i
. l
. . . i︐
. '
'
.•
t.
. .
I4 ..
. . . .
ι .. I ︐.
h .
︐¥.J..
. . h
. '︐
••
1・
・ ー
・
・
︐
iil
一 ︑
・ ・
41
; ︑
.Z
川 ・
3ム
コ u.・5 e・2
・ 目 白河‑
h e‑‑‑ u‑・1・ . ・
J・A
・ ‑ 一
‑ u .
・42一 一
1 .J
・ 句 ︐
︐
﹄v
e‑
‑f・
J a
︐.
・ . 0 f
︑ ︐
at・g・‑‑‑2
・・
・
3t
‑‑
‑‑b‑‑‑‑
‑ ‑
.︐....・・べ
・・
・
・・︑
•..••..
Ilo‑
‑ 0
・
・ ・
a・ し・
・:
・・
・・
・
・
・ ・
0
・・
︑︐
. e a
︐
...••
.
・ ・ ・
・・ ︑ . ・
・ ・
・・
e
‑ ‑‑
‑
‑
‑
‑
‑
‑
・
•...
....
•..
︐目・
. ︐︐ .
・ ・
aa
‑
‑‑‑‑‑‑
‑
‑
‑
‑
‑
‑
‑ g
a
‑
‑
‑
‑
a e
‑
‑
・ .
一 ..•
︐ ・. .
. . 目
Fig.5.9:六角ナットの表面点からなる集合
1・
'・
・
目・
・︑
a
i 1 1
︑e
・・
2・
一 ︐・ ・ ぃ ・一
‑‑
‑‑
‑‑
‑d
‑e
‑‑
J
・・
2・‑‑
j・EI‑‑‑‑a
︐ ︐︑
・
‑ a
‑
‑ ‑7J6・・3 e
崎︑
.2
日ィ
n. ha
‑‑'
3 .
f︐
.•
・・h品‑ z・ ・ • ︒︑
1川U
J ZV 7・ ミ " に
・‑
・e a・r
4 1 4 e
・︐ .︐
a
・ ・ ︑ . .1
・ 守
‑
‑ e・
・い
2・
. • JJ.‑‑e・e・
‑‑
‑
︑ .
目・ ・ ・ ・
・ ・
. ・
一日 . tr
・h.‑4
・
‑ ‑ ‑ ‑ 恥
γ・ 一 パ ・
.11・M'UT‑u・ 勺
F・ ・ ・
1・‑
e・ ニ ﹁
1.‑u・. ・
".・ " ・ .
・. ・1
一 ・
17・U F . z ‑ ‑ ‑
‑・‑ .
5.7. 結び
5.7. 結び 86
(a) 'E1︑/︑ LU
(c) (d)
(e) ︑ノl︐ ︐
P+ i 〆'E1︑︑
Fig.5.10:各段階で得られた中間結果と最終結果