FNB による高速化

本項では，3と4.1で示したFNBの高速性を示すため，3種類の距離画像を用いて実験を 行った．それぞれの実験では，NB，Hermes AlgorithmおよびFNBの計算時間(sec.)の比較 結果を示し，FNBの高速性を示す．

4.2.

実験

42

複数物体の曲面再構成

まず，複数物体の同時曲面再構成に対するFNBの有効性を確かめるため，図4.5(a)に示 す２体のうさぎの距離画像データに対して実験を行った．図4.5(a)に示す距離画像データ点 の個数は70406点であり，停止領域の定数をk= 2，各座標方向の格子点の数をn= 100，バ ンド幅をδ = 6^{，時間ステップ幅を}∆t= 1^{とした．図}4.5(b)(c)は最終結果であり，三角形 パッチの頂点数は17036点，三角形パッチの数は34064個であった．ここで設定した∆tの値 はCFL条件を満たしていないが，補助関数の更新時に再初期化処理を行い，拡張成長速度を 用いているため，正しい最終曲面形状が得られる様子がわかる．また，FNBを用いた曲面形 状進化がNBと同じ計算精度を保つかどうかを確かめるため，同じ条件でNBを用いたモデ リングも行った．その結果，FNBを用いたものと同じモデルが得られることを確認した．ま た，本手法では，各々のうさぎが適切にモデリングされている様子がわかる(図4.5(c))．

表4.1^にNB^，Hermes Algorithm^およびFNB^{の計算時間}(sec.)の比較結果を示す．なお，

上段は曲面形状進化(4.1.1Step2)の計算時間，下段は最終結果が得られるまでの全計算時間 である．この表からFNBの計算時間はNBに比べて87倍ほど高速化されていることがわか る．各座標方向のボクセル数をnとすると，NBの計算量はO(n⁴)，FNBの計算量はO(n²)

であり，n= 100であるため，FNBとNBの計算時間比は理論値とほぼ一致している．また，

Hermes algorithmより8.7倍ほど高速化されていることもわかる．

これらの結果から，FNBのモデリング精度はNBと同じであり，従来手法と比較して高速 化が実現されている事を，複数物体の距離画像を用いて確認した．

穴とふちを持つ物体の曲面再構成

次に，図4.6(a)に示すティーカップの曲面再構成を行った．対象物の全周型距離画像デー

タを取得するため，物体を針金でつるし，多視点からレンジファインダによる全周計測を行っ た．このとき，得られた距離画像データを図4.6(b)^{に示す．データ点数は}78235^{点であった．}

停止領域の定数をk = 2，各座標方向の格子点の数をn = 100，バンド幅をδ = 6，時間ス テップ幅を∆t= 1とし，FNBを用いて初期曲面が停止するまで収縮・分裂させて得られた 結果を図4.6(c)に示す．図4.6(d)は，最終結果である．図4.6(d)の頂点数は27779点，三角 形パッチの数は49559個であった．ここでオクルージョンにおけるデータ欠損問題について 検討する．実物体をレーザレンジファインダ等で計測する際，データの取得が困難な部位が しばしば生じる．例えば，本実験では，ティーカップの取っ手の内側データはほとんど取得で きなかった．しかし，FNBを用いることによって，そのような部位でも滑らかに平面パッチ が生成され(図4.7)，本手法は多少のデータ欠損に対しても頑健な手法であることがわかる．

4.2.

実験

43

(a) (b)

(c)

Fig.4.5: 2

体のうさぎのモデリング

4.2.

実験

44

(a) (b)

(c) (d)

Fig.4.6:

ティーカップのモデリング

Fig.4.7:

底からながめたティーカップ

4.2.

実験

45

次に，NB^，Hermes Algorithm^およびFNB^{の計算時間}(sec.)^{の比較結果を表}4.1^に示す．

この表からFNBの計算時間はNBに比べて81倍高速化されている．各座標方向のボクセル 数をnとすると，NBの計算量はO(n⁴)，FNBの計算量はO(n²)であり，n= 100であるた め，FNBとNBの計算時間比は理論値とほぼ一致している．また，Hermes Algorithmより も5.5倍ほど，それぞれ高速化されていることもわかる．

これらの結果から，FNBは従来手法と比較して高速化された事を，穴とふちを持つ物体の 距離画像を用いて確認した．

Table.4.1:

計算時間の比較

NB Hermes FNB

図

4.5 4.1.1 Step2 5760 576 66

[sec.] Total 5819 637 128

図

4.6 4.1.1 Step2 6246 430 77

[sec.] Total 6330 514 160

図

4.8 4.1.1 Step2 5204 450 56

[sec.] Total 5229 488 81

複雑な位相を持つ物体の曲面再構成

最後に，より複雑な位相を持つ物体の曲面再構成に対する本手法の有効性を確かめるため，

図4.8(a)に示す細い針金で作られたバスケットの曲面再構成を行った．図4.8(b)は，レンジ

ファインダを用いて得られたバスケットの全周型距離画像データである．データ点数は5530 点であった．停止領域の定数をk = 2，各座標方向の格子点の数をn = 100，バンド幅を δ = 6^{，時間ステップ幅を}∆t= 1とした．曲面が収縮・分裂して物体形状が抽出される過程 を図4.9(a)-(f)に示す(4.1.1Step2)．図4.9(f)では，物体表面近くで曲面形状進化が停止し，

物体の概形が得られたことがわかる．さらに，図4.9(f)に示すモデル対し，従来の変形可能 曲面を用いて補正を行った最終結果が図4.8(c)である．頂点数は12376点，三角形パッチの

数は24787個であった．このように複雑な位相をもった物体に対してもFNBを用いて適切に

モデリングできることがわかる．

表4.1にNBとHermes AlgorithmとFNBの計算時間(sec.) の比較結果を示す．この表か らFNB^{の計算時間は}NB^に比べて93^倍，Hermes algorithm^より8.0^{倍ほど，それぞれ高速} 化されたことがわかる．

4.2.

実験

46

Fig.4.8:

バスケットのモデリング

4.2.

実験

47

Fig.4.9:

モデリング生成過程

4.2.

実験

48

これらの結果から，FNB^{のモデリング精度は}NBと同じであり，従来手法と比較して高速 化が実現されている事を，複雑な位相を持つ物体の距離画像を用いて確認した．

ドキュメント内 LEVEL SET METHODの高速化および医療画像への応用に関する研究 (ページ 46-53)