「画像の認識・理解シンポジウム（ＭＩＲＵ2006）」 2006年 7月

境界移動予測に基く並列 Fast Level Set Method の計算負荷均衡化
岩下

友美†

倉爪

亮†

原

健二††

長谷川 勉†† 九州大学大学院システム情報科学研究院 福岡市東区箱崎 6-10-1†† 九州大学大学院芸術工学研究院 福岡市南区塩原 4-9-1
E-mail: †yumi@irvs.is.kyushu-u.ac.jp
あらまし

人間の動きや形状だけでなく 見え も計測し復元する，複数カメラを用いたマーカレスなモーションキャ

プチャシステムの代表的な手法として，視体積交差法と多視点ステレオが提案されている．しかしこれらの手法は，
単一物体あるいはオクルージョンが生じない複数物体を対象とした手法であり，シーン内に複数物体が存在し物体間にオクルージョンが生じる場合，それぞれの物体形状を同時かつ分離して復元することは困難である．そこでこれまでに我々は，高速な境界追跡手法である Fast Level Set Method を複数ステレオ距離画像に適用し，複数対象物体の 3次元形状をオクルージョンに頑強に復元するモーションスキャナシステムを提案している．本報告では，Fast Level Set

Method の特性に着目した動物体境界の移動方向推定法を提案し，その応用例として，PC クラスタを用いた並列 Fast
Level Set Method のための境界移動方向の予測値に基づく計算負荷の均衡化手法を提案する．さらに，動物体の追跡実験により，従来システムと比較してより高速に 3 次元形状の復元が可能であることを示す．
キーワード

Fast level set method，3 次元形状復元，PC クラスタ，負荷分散

Predictive Load Balancing for Parallel Fast Level Set Method
Yumi IWASHITA† , Ryo KURAZUME† , Kenji HARA†† , and Tsutomu HASEGAWA†† Graduate School of Information Science and Electrical Engineering, Kyushu University Hakozaki 6-10-1,
Higashi-ku, Fukuoka†† Graduate School of Design, Kyushu University Shiobaru 4-9-1, Minami-ku, Fukuoka
E-mail: †yumi@irvs.is.kyushu-u.ac.jp
Abstract Various markerless motion capture systems using video cameras, which enable to recover not only motion of atarget but also its appearance, have been proposed so far. However, in case that there are multiple persons in the scene at thesame time, it is quite difficult to reconstruct a precise 3D model of each person separately due to the occlusion between them.
To deal with this problem, we have proposed a motion capture system using the Fast Level Set Method for recoverying 3Dmodels of multiple persons separately and robustly against occlusion. This paper introduces an estimation method of target’s
moving direction based on a property of the Fast Level Set Method. As an application of the estimation method, we propose aload balancing method based on predicted moving direction for parallel Fast Level Set Method implemented on a PC cluster.
Tracking experiments of a moving target using the proposed system are successfully carried out.
Key words Fast level set method, 3D shape reconstruction, Pc-cluster, Load balancing

1. は じ め に題が多い．
一方，複数のカメラを周囲に配置して，人間の形状や動きだ

人間国宝の巧みの技や格闘技の動作など，実際の人間の動きを計測し記録するモーションキャプチャは，高品質な CG 作成，技術の蓄積・継承や歩行ロボット開発などの分野で，多くの需要が見込まれる．しかし現在実用化されているモーションキャ
プチャには磁気式，光学式，リンク装着式などがあるが，これらは磁気，光学マーカや特殊な計測装置を装着する必要があり，また撮影環境が専用のスタジオに限られるなど，解決すべき課

けではなく

見え

も計測し再現するマーカレスのモーション

キャプチャシステムの研究も行われており，このシステムの実
現方法の代表的な手法として，視体積交差法と多視点ステレ
オが提案されている．視体積交差法は，任意の視点から対象を撮影したとき，その対象が 2 次元シルエットを実空間に投影した錐体中（視体積）に含まれるという制約条件に基づいている [1] [2]．すなわち，この制約条件により異なる視点の 2 次元430

シルエットから複数の視体積を求め，その交差領域を対象物体元を可能にする．

の 3 次元形状として復元するものである．そのため，多数台の

本報告では，まず第 2 章では Osher, Sethian らによって提案

カメラを用いることにより詳細な 3 次元形状の復元が可能となされた Level Set Method，及びその高速化手法として提案されるが，一方カメラ台数の増加に伴い計算コストが高くなるといた Fast Level Set Method を紹介する．次に第 3 章では，これまう問題がある．これに対し，対象物体の 3 次元形状を実時間ででに提案されたモーションスキャナシステムについて概説する．

復元するために，PC クラスタを用いたシステム [3] [4] やハー

また動物体の移動方向推定法を提案し，提案手法を用いた並列ドウエアを用いたシステム [5] が提案されている．

Fast Level Set Method のための負荷分散の最適化について紹介

また，凸形状物体のみしか復元できないという視体積交差法
固有の問題に対して，Voxel carving 法や物体表面の色情報を用する．第 4 章では開発したシステムを用いた人体形状の追跡実
験の様子を示す．第 5 章はまとめである．

いて凹部分の形状復元を行う手法が提案されている [6] [7]．し2. Fast Level Set Method

かし，いずれの手法も計算コストが高く，実時間での 3 次元形
状復元は実現されていない．
一方，多視点ステレオは異なる視点から撮影された 2 次元画
像上で物体表面上の点の対応付けを行い，三角測量の原理により対象物体の 3 次元形状を復元する手法である．Kanade らは

51 台のカメラをドーム上に配置して多視点で計測するシステム
を開発している [8] [9]．しかし，モデル構築のための計算コス
トやデータ量が非常に大きく，人間のような複雑形状の実時間計測は困難である．また近年，このシステムと Voxel coloring

Level Set Method (LSM) [12] [13] は，位相変化が可能な動的輪郭モデルとして Osher, Sethian らによって提案され，移動体追跡や 3 次元幾何モデルなどの応用分野が報告されている．しかし LSM は多くの計算量を必要とするため，リアルタイム性が要求されるアプリケーションには不向きであると考えられてきた．この問題に対し，精度を低下させることなく LSM を高速に実現できる Fast Level Set Method (FLSM) [14] [15] が提案され，2 次元画像上での複数移動物体の実時間同時追跡へと適用されている．以下，これらの手法を簡単に紹介する．

法を組み合わせることで，より詳細な 3 次元形状を復元する手

2. 1 Level Set Method とその高速化手法法が提案されている [10]．
さらに，従来提案されている 3 次元形状復元手法では，そのほとんどが単一物体あるいはオクルージョンの生じない複数物体を対象とした手法であり，シーン内に複数物体が存在し物体間に相互オクルージョンが生じる場合，それぞれの物体形状を

2 次元 xy 平面上での LSM を用いた境界追跡法について説明する．本手法ではまず，平面上の各点 (x, y) において，時刻t における補助関数 ψ(x, y, t) を導入し，境界位置 γ(x, y, t) は
ψ(x, y, t) = 0 を満たす (x, y) で表すこととする．次に，ψ についての差分方程式を以下のように定義する．

同時に復元することは困難である．

n+1
n
n
ψi,j
= ψi,j− F (i, j)|∇ψi,j|∆t

そこでこれまでに我々は，シーン内に存在する複数対象物体(1)の 3 次元形状をオクルージョンに頑強に復元するモーションス

ここで，(i, j) は xy 平面上のグリッド座標，∆t は時間ステップ

キャナシステムを提案している [11]．このシステムでは，移動幅である．また，F は ψ の成長速度であり，単位時間あたりに物体追跡や 3 次元幾何モデリングなど，様々な分野で用いられψ が法線方向に移動する量を示す．補助関数値が 0 のセル (zeroる Level Set Method [12] [13] の高速化手法である Fast Level Set

level set)，つまり ψ = 0 として境界を抽出することで，位相変Method [14] [15] を，対象物体の周囲に 2 台配置したステレオ化に対応した境界追跡が可能となる．

カメラから取得したステレオ距離画像に適用することで，複数式 1 を更新するには，2 次元画像上の全てのセルにおいて成対象物体の 3 次元形状をオクルージョンに頑強に復元してい長速度を決定する必要がある．拡張成長速度場 [16] を用いた

る．また，7 台の計算機からなる PC クラスタへと実装し，Fast

LSM では，各セルの成長速度を決定するために, まず zero level

Level Set Method 処理の並列計算により，3 次元形状の実時間復set での成長速度を決定し，その他のボクセルでは最も近い zero元を実現している．しかし，従来システムでは並列 Fast Level

level set のボクセルの成長速度をコピーして成長速度場を構築

Set Method 処理に割り当てるボクセル空間を単純に分割していする．また，補助関数を更新する場合，更新とともに積分誤差るため，物体の位置や形状，物体数によって特定の計算機に負も蓄積されるため，安定な解を得るには一定回数更新後に各セ荷が集中する場合があった．

ル毎に補助関数の値（一般には zero level set からの距離）を再そこで本報告では，Fast Level Set Method の特性に着目した計算し，以降の計算の初期値として設定する「再初期化」の処

動物体境界の移動方向推定法を提案し，その応用例として，PC理が必要となる．しかし，拡張成長速度場の構築処理や再初期クラスタを用いた並列 Fast Level Set Method のための境界移動化処理において，各セルで現在の zero level set からの距離を得方向の予測値に基づく計算負荷の均衡化手法を提案する．本手

る際，各セルからの最近傍 zero level set の探索処理を行わなく法ではまず，復元した 3 次元形状分布に応じてボクセル空間のてはならない．この計算コストは非常に高く，これが LSM の仮分割面を決定する．次に，推定した動物体の移動方向の予測

大きな問題となっている．

値とボクセルの仮分割面情報とを組み合わせ，次時刻でのボク

LSM の計算コストを削減するために，これまでに様々な手

セル空間の最適な分割面を予測し決定する．これにより，並列法が提案されており，その代表的な手法として Narrow Band

Fast Level Set Method における計算機間での計算負荷の均衡化

Method（以下，NB）が挙げられる [17]．一般に境界領域の追跡を実現し，従来システムと比較してより高速な 3 次元形状の復において，空間全体に対して補助関数を計算する必要はないこ

431

とから，この手法では zero level set に近い領域 (Narrow Band)

在しない．このように，隣接するグリッドが zero level set かど

だけに処理を限定することで処理の効率化を図っている．

うかを調べ，その位置関係によって，書き込みのオーバーラッ
プを減らし，拡張成長速度場を高速に構築している．

2. 2 Fast Level Set Method
NB は LSM と比べて高速な手法であるが，依然として計算

3. 境界の移動方向推定及び並列 Fast Level Set
Method のための負荷分散の最適化

コストは高い．この問題に対し，LSM の高速化手法として Fast

Level Set Method (FLSM) [14] [15] が提案されている．

本章ではまずこれまでに提案されている，複数対象物体の 3

FLSM は図 1 (a) に示す参照マップを用いて，最近傍探索処
理をあるルールに基づく単純な数値の上書き処理に置き換える
ことで，高速に拡張成長速度場を構築する．この参照マップは，原点周辺にあるセルを原点からの距離に応じて分類したものである．例えば，リスト Rr は原点からの 2 乗距離が r であるセルの集合とする．

8
10 5
9 4
10 5
8

10
5
2
1
2

9 10
4 5 8
1 2 5 100 1 4 91 2 5 105 4

5 8

10 9 10Rr

H H H 0 G 0 F0 F F
H H G F F
H G F(b) Divided reference map

ナシステムについて概説する [11]．従来，様々なオクルージョンの対応手法が提案されているが，一般に推定される物体形
状は既知かつ楕円などで近似された単純な構造であり，自由形状物体のオクルージョン判定には拡張されていない [18]．次にFLSM の特性に着目した動物体境界の移動方向推定手法を提案
F1

F 2 F1 F5 F 1 F5

F1
F1

F1

F3
F3
F1 F5

F6 F 1

F4

F7
F1

F6

F6
F7 F1

F2 F1 F 5

F 2 F1 F5F1 F3し，その応用例として，PC クラスタを用いた並列 FLSM のための境界移動方向の予測値に基づく計算負荷の均衡化手法を提案する．

3. 1 FLSM による人体形状の復元と追跡

F1 F3
F7
F6 F1
F4
F6
F3
F7

FLSM を用いたモーションスキャナシステムの処理の流れをF 2 F1 F7 F 1 F5

F1zero level set(a) Reference map

B C D
B B C D D
B B B0 C0 D0 D D
A A A0 Z E0 E E

次元形状をオクルージョンに頑強に復元するモーションスキャ

(c1) Rr = 10以下に示す．

(c2) Rr = 10

（ 1 ） まず内部パラメータが既知の校正済みステレオカメラ
F 2 F1 F1 F 1 F5
F3
F3
F1 F5
F1

F6

F6
F7 F1

F2 F1 F 5

F1

F1 F3
F7
F6 F1
F4
F6
F3
F7

F2
F3
F3
F4

F2 F2
F2 F2
F2 F2
F3 F2
F3 F3

F1 F5
F1 F5
F1 F5
F1 F5
F1 F6

F5
F5 F5
F5 F6
F6 F6
F6 F7

F 4 F 4 F3 F1 F6 F7 F7F 2 F1 F1 F 1 F5F 4 F 4 F4 F1 F7 F7 F7(c3) Rr = 9(c4) Final result

図 1 参照マップと拡張成長速度場の構築(PointGrey 社製，BumbleBee) を大きさ・形状が既知の静止物体（例えば立方体）の周囲に設置し，物体の形状モデルとステレ
オ距離画像を用いて ICP アルゴリズムにより外部パラメータを推定する．
（ 2 ） 測定対象を内部に設置し，全てのステレオカメラを用いてステレオ距離画像を取得する．
（ 3 ） 複数距離画像を一つの 3 次元ボクセル空間に投影し，次に，作成した参照マップを用いて拡張成長速度場を構築す

距離データを含むボクセルを抽出する．

る．ただし，zero level set での成長速度は予め決定されている（ 4 ） 取得したステレオ距離画像と前フレームで復元した 3とする．まず，リスト Rδ(δ+1) を用いて，ある zero level set か次元形状情報を用い，オクルージョン領域を推定する．

らの 2 乗距離が δ(δ + 1) であるセルを選択し，その zero level（ 5 ） (3) で抽出されたボクセル領域に対し FLSM を適用し，set に格納されている成長速度の値を選択されたセルに仮登録

距離データ点を含む最も外側のボクセル（境界ボクセル，zeroする (図 1 (c1))．この処理をすべての zero level set に対して行

level set）を追跡し，複数対象物体の分離した 3 次元形状を復う (図 1 (c2))．次に，添字の値を 1 小さくして同じ処理を行い元する．オクルージョン領域内の形状は，前時刻での境界位置(図 1 (c3))，これを添字の値が 0 になるまで繰り返す．ただし，を保つことで連続した滑らかな形状を保持する．

仮登録の際，異なる値がすでに仮登録されていた場合には，新（ 6 ） (2) から (5) を繰り返す．

たな値を上書きすることにする．これにより全ての処理が終了

上記の計算は，処理の高速化を図るため，ギガビット LAN のした時には，各セルには最も近い zero level set における成長速一つである Myrinetxp で相互に接続された 7 台の計算機 (Pen-

度の値が登録されている (図 1 (c4))．このように，参照マップ

tium Xeon, 3.06 GHz) により並列処理される（図 2）．まずそれ球の距離に応じたリストを利用することで，距離比較を行うこ

ぞれステレオカメラが接続された 2 台の計算機 (PC1，PC2) にとなく代入処理だけで拡張成長速度場を構築する．また，拡張より，同期した 2 枚のステレオ距離画像を取得する．次に得ら

成長速度場の構築処理の過程において，同時に距離も上書きすれた距離画像は FLSM 計算用計算機に送られる．ただしここでることで，各セルに zero level set からの距離を簡単に設定できはボクセル空間を 4 つの領域に均等に分割し，それぞれの空間

る．この際，追加される処理は単なるメモリーアクセスだけでに 1 台ずつ計算機を割り当て (PC3-PC6)，4 台で並列に FLSMあり，全体の計算量はほとんど変化しない．

の計算を実行した．各 FLSM 用計算機では，まず複数距離画

さらに FLSM では図 1 (b) に示すように分割した参照マップ

像の統合を行った後，それぞれの領域に対して FLSM を適用すを用いることで，拡張成長速度場の構築処理において書き込む

る．ここで，各処理空間内を移動する対象物体の３次元形状を領域を限定し，さらなる効率化を実現している．例えば，ある

安定して復元するために，処理空間が隣接する FLSM 計算機間

zero level set Z の左側に zero level set A0 が隣接している場合，において，3 次元空間の分割面近傍領域の FLSM 処理結果の情

Z の左側の領域 (A，B ，H) には，A0 よりも Z に近い点は存報を共有している．最後に処理結果が表示用計算機 (PC7) に送432

3. 2 対象物体の移動方向の推定

られ，ボクセル空間全体の処理結果として統合，表示される．

次に動物体境界の移動方向の推定手法について述べる．まず，
時刻 t−∆t で構築した 3 次元モデルの境界ボクセル Z(t−∆t, i)
PC1

PC2

PC4

PC5

PC3
PC3

PC6

(0 <
= i < N (t − ∆t)) と時刻 t で構築した 3 次元モデルの境界ボクセル Z(t, j) (0 <= j < N (t)) との対応付けを行う．ここPC4で，N (t) は時刻 t で復元した 3 次元モデルの境界ボクセルの

PC5

PC6

Stereocamera 3

Stereocamera 1

総数とする．具体的には，まず時刻 t − ∆t で復元した境界ボ
クセル Z(t − ∆t, i) にラベル L(t − ∆t, i) を格納し，距離場

PC7の構築処理と同様の手順で Narrow Band 内のボクセルにラベ

3D voxel space

PC cluster system

ル L(t − ∆t, i) をコピーする．全ての境界ボクセルのラベルを

図 2 PC クラスタシステム

Narrow Band 内のボクセルにコピーすると，Narrow Band 内の構築システムを用いた，人間動作の実時間追跡実験におけ

ボクセルには 3 次元形状の最近傍境界ボクセルのラベルが格納

る FLSM 処理時間を表 1 に示す．この時使用したボクセル空間

される（図 4(a)）．次に，時刻 t で構築した 3 次元形状の境界の解像度は 100 × 100 × 100，距離画像のサイズは 640 × 480

ボクセル Z(t, j) に格納されているラベルより，境界ボクセルである．また，一回のステレオ距離画像取得は 37[msec.] であり，PC クラスタを用いた並列 FLSM 処理の計算時間は最大で24[msec.] であった．これに対し，一台の計算機のみを用いた場

Z(t − ∆t, i) と境界ボクセル Z(t, j) との対応付けを行い，相対変位を表すベクトル Link(t; j) = Z(t, j) − Z(t − ∆t, i) とする．ここで，時刻 (t − ∆t) ∼ t において対象物体の局所的合では FLSM 処理の計算時間は 77[msec.] であった．次に，複な形状は保持されると仮定すると，Link(t; j)と境界ボクセ

数移動物体の追跡実験結果を図 3 に示す．図 3(a) は実際の実験

ル Z(t, j) 近傍の境界面の法線ベクトル n(t, j) との一致度より，の様子，図 3(b) はボクセル空間を上方から示したもの，図 3(c)

対象物体の移動方向を推定することができる（図 4.(b)）．そこ

はボクセル空間を斜め上から示したもので，対象物体は図 3 中の矢印の向きに移動する．これより，複数対象物が交差し，相で，時刻 t における対象物体の移動方向ベクトルM D(t)はX
M D(t) = (1.0 − α)Link(t; j)|Link(t; j) ´ n(t; j)|>β

互オクルージョンが発生する場合でも，人体概形を保存しつつ+αM D(t ` ∆t)

追跡できていることがわかる．

(2)

表 1 FLSM の計算時間の比較

PC cluster
Average Max.

と定義する．ただし，α, β は定数である．

Single PC
Min.

L1 L1 L5 L5

Calculation timeof the FLSM [msec.]

17

24

9

77

5765

7418

3481

13357

L1 L1 L1 L5 L5 L5
L2 L2 L1 L1 L5 L5 L6 L6
L3 L2 L2 L1 L5 L6 L6 L7

Number of thereconstructed 3D voxel

Stereocamera 1

L4 L4 L3 L3 L7 L7 L8 L8zero level set (a)Stereocamera 1
1

2
2

1

2

Link(t, j)

Link(t, j')Z(t-∆t, i)Z(t-∆t, i')zero level set(Time=t-∆t)(b)

対象物体の移動方向を推定する手法として，例えば復元した

3 次元形状の重心位置の時系列データを用いることが考えられる．しかし，例えば腕や足などの体の一部のみを動かす場合，
12n(t, j')Z(t, j)

図 4 動物体の移動方向の推定

Stereo Stereo
camera 3 camera 31n(t, j)Z(t, j')L3 L3 L2 L2 L6 L6 L7 L7
L4 L3 L3 L2 L6 L7 L7 L8

1
1

zero level set(Time=t)22全体の重心位置を用いる手法ではその部位のみの移動方向を推定することは困難である．これに対し，提案した移動方向推定
法は，境界の局所的な移動方向の推定が可能であり，移動部位の切り出しも期待できる．
例として図 5 に示す半径 0.1m の球体を用いて移動方向推定

1

1
2

2

(a)Moving objects

図3(b)Top view

2

1のシミュレーション実験を行い，その推定性能を評価した．実験条件は，X 軸，Y 軸，Z 軸に沿ってそれぞれ 0.01m ずつ，合(c)Cross view

複数対象物体の 3 次元形状復元

計 1.5m 動かした場合と，Y 軸を回転軸に 5 度ずつ回転した場
合の 4 通りである．また，軸方向へ移動する場合は α = 0.0，

β = 0.98 とし，軸周りで回転する場合は α = 0.4，β = 0.98 とした．表 2 に推定された移動方向ベクトルと実際の移動方向ベ
クトルとの角度の差の平均と標準偏差を示す．これより，提案433

手法により物体の移動方向の推定が可能であることが確認でき

PC4

PC4

PC5
Division planePC5

る．一方，軸方向への移動と比較し，軸周りの回転の推定結果が悪いことがわかる．これは，3 次元形状の境界ボクセルに格Objects

納されているラベルを Narrow Band 内にコピーする際，異なるUpdated division
plane

ラベルが既に仮登録されている場合には，新たなラベルを上書きするため，正しいラベルが保持されない場合があるためと考

PC3

PC3

PC6

PC6

(a)

えられる．この解決法として，復元した 3 次元形状のラベルをNarrow Band 内にコピーする際に，3 次元形状の法線方向への(b)

図 6 物体形状に応じた適応的なボクセル空間の分割

コピーを優先することが挙げられる．

(dx (i, t), dy (i, t), dz (i, t)) (0 <= i < F LSM の P C 数) とする

Yと，新たな分割点 Dnew (i, t) = (dnx (i, t), dny (i, t), dnz (i, t))を以下のように決定する．

0.1

Dnew (i, t) = D(i, t) + γM D(t)/|M D(t)|mSphere(3)

ただし，γ は定数である．これにより，各計算機で復元する 3X

次元形状のボクセル数はほぼ均一となり，並列 FLSM の負荷分散の最適化が期待される．

Z

4. 実

図 5 球体の移動方向の推定

提案したモーションスキャナシステムを移動する人体へ適用

表 2 推定された動物体の移動方向の精度評価

Average [deg.]Standard
variation [deg.]験し，境界移動予測値を用いた負荷均衡化手法の有効性を確認する実験を行った．使用したボクセル空間の解像度は 100×100×100（ボクセル空間の一辺は 1.5cm）である．

Translation along the x-axis

0.79

1.77

Translation along the y-axis

0.51

1.59

Translation along the z-axis

2.45

2.72

対象物体の追跡実験を行った．ただし，並列 FLSM に割り当

Y-axis rotation

4.67

2.45

てるボクセル空間領域を単純に 4 分割した場合 (Exp.A)，形状

3. 3 並列 FLSM のための負荷分散の最適化
3.1 節で示した従来のシステムは，並列 FLSM 処理において
ボクセル空間を単純に分割しているため，物体の位置や形状，
物体数によって特定の計算機に負荷が集中する場合があった（図 6(a)）．そこで推定した動物体の移動方向情報を用いた，PC
クラスタを用いた並列 FLSM のための計算負荷の均衡化手法を提案する．
まず，対象物体の位置と復元した 3 次元形状のボクセル数に応じて，ボクセル空間の分割面を決定する．具体的には，まずFLSM 計算機において復元したそれぞれの 3 次元形状情報を表
示用計算機へと送信する．次に表示用計算機において対象物体の形状分布を統合し各領域内の 3 次元形状のボクセル数が等しくなるようにボクセル空間を 4 つの領域へと分割し，ボクセル
空間の分割面を更新する（図 6(b)）．最後に，更新したボクセ

まず，図 7(a) のように腕をあげた状態でシーン内を移動する

分布から分割面を決定した場合 (Exp.B)，及び対象物体の移動方向の予測値に基づいてボクセル空間を分割する場合 (Exp.C)
について実験を行った．図 7(b) に (Exp.A) の結果，図 7(c) に(Exp.C) の結果をそれぞれ示す．この結果より，(Exp.A) では特定の計算機に FLSM 計算負荷が集中したため，3 次元形状復元のために必要な FLSM 処理の収束計算回数が得られず，腕の一部に欠損が生じている．一方，(Exp.C) では，欠損を生じることなく 3 次元形状を復元している．また表 3 に (Exp.A)，(Exp.B)，及び (Exp.C) の計算時間の比較を行った結果を示す．
ただし α = 0.3，β = 0.9，γ = 4 である．これより，(Exp.C)の物体の移動方向の予測値に基づく FLSM 計算機間の計算負荷の均衡化を行う場合，復元する 3 次元形状のボクセル数が増加するにも関わらず，より高速に 3 次元形状の復元が可能である
ことがわかる．
表 3 並列 FLSM の計算時間の比較

ル空間の分割面情報を各 FLSM 計算機へと送信し，FLSM 計算

Voxel space division

機では更新された分割面に応じて FLSM 処理領域を変更する．

Average calculation

Total voxel number of thetime [msec./1voxel ]reconstructed 3D model

しかしこの手法では，並列 FLSM 処理において更新されたボク(Exp.A) Equal division

0.015

7638

セル空間の分割面情報は，表示用計算機で更新されるため，実(Exp.B) Adaptive division

0.012

9004

際には前時刻以前で復元した 3 次元形状分布を用いることにな(Exp.C) Adaptive division

る．このため，各 FLSM 計算機間で復元する 3 次元形状のボク

using moving direction

0.010

12019

セル数は正確には均一化されない場合がある．
そこで，3.2 節で提案した動物体の移動方向の予測値を利用し，さらに提案した手法に基づき，ステレオカメラ 5 台を用いて並列 FLSM に割り当てるボクセル空間領域をより最適に決定す

詳細な人間動作の追跡実験を行った．実験では図 8 に示すようる．具体的には，物体形状分布を用いて決定した分割点 D(i, t) =に，ステレオカメラ 1∼4 は側面に，またステレオカメラ 5 は天井に設置した．図 9(a) に対象物体の実際の様子，及び図 9(b)434

の概要を示した．また，Fast Level Set Method の特性を用いた動物体の移動方向推定手法を提案し，その応用例として，PC ク
ラスタを用いた並列 Fast Level Set Method のための境界移動方向の予測値に基づく計算負荷の最適化手法を提案した．動物体
(b1)
(b2)
(b) Tracking result of a moving human bodyの追跡実験により従来システムと比較して，より高速な 3 次元形状の復元が可能であることを示した．今後は増設したステレ
オカメラを用い，シーン内に存在する複数対象物体の 3 次元形(a) Real scene

状をオクルージョンに頑強に実時間で復元するシステムを開発
する．
文

(c1)
(c2)
(c) Tracking result of a moving human body by adaptive divisionof voxel space using moving direction

図 7 負荷分散の最適化手法を用いた 3 次元形状復元に復元した形状を示す．また生成したモデルに対し，マーチン
グキューブ法を適用し，その後テクスチャマッピングを行った結果を示す（図 9(c)）．
Stereo camera 5
Stereo camera 4

2.5m

2.5m

Stereo camera 3

1.5m

2.5m

2.5m

Center voxel
1.5m

Stereo camera 1

Stereo camera 2

図 8 複数ステレオカメラを用いた 3 次元モーションスキャナシステム(b1) Cross view(b2) Top view(c1) Cross view(c2) Cross view

献[1] W. Martin and J. Aggarwal, “Volumetric description of objects frommultiple views”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.5, No.2, pp.150-158, 1983
[2] A. Laurentini, “The visual hull concept for silhouette-based image
understanding”, IEEE Transactions on Pattern Analysis and MachineIntelligence, vol.16, No.2, pp.150-162, 1994
[3] E. Borovikov and L. Davis, “A Distributed System for Real-timeVolume Reconstruction”, IEEE Proc. of CAMP-2000, 200[4] K. Cheung, T. Kanade, J. Bouguet and M. Holler, “A real time system for robust 3D voxel reconstruction of human motions”, Proceedings of the 2000 IEEE Conference on Computer Vision and Pattern
Recognition, vol.2, pp.714-720, 2000
[5] M. Li, M. Magnor and H. Seidel, “Hardwareaccelerated visual hullreconstruction and rendering”, In Proc. of Graphics Interface, 2003
[6] K. Kutulakos and S. Seitz, “A theory of shape by space carving”,
International Journal of Computer Vision, vol.38, No.3, pp.199-218,
2000[7] S. Nobuhara and T. Matsuyama, “Heterogeneous Deformation
Model for 3D Shape and Motion Recovery from Multi-Viewpoint
Images”, Proceedings of the 2nd International Symposium on 3D
Data Processing, Visualization, and Transmission, pp.566-573, 2004
[8] T. Kanade, P. Rander and P. Narayanan, “Virtualized Reality: Constructing Virtual Worlds from Real Scenes”, IEEE Multimedia, Immersive Telepresence, vol.4, No.1, pp.34-47, 1997
[9] P. Narayanan and P. Rander and T. Kanade, “Constructing Virtual
Worlds using Dense Stereo”, Proceedings of 6th IEEE International
Conference on Computer Vision, pp.3-10, 1998
[10] S. Vedula and S. Baker and T. Kanade, “Image-Based SpatioTemporal Modeling and View Interpolation of Dynamic Events”,
ACM Transactions on Graphics, vol.24, No.2, April, 2005[11] 岩下，倉爪，辻，原，長谷川, “Fast Level Set Method を用いた複数移動物体の 3 次元追跡”, 日本ロボット学会論文誌, vol.23, No.7,
pp.813-820, 2005[12] J. Sethian, “A fast marching level set method for monotonically advancing fronts”, Proceedings of the National Academy of Science,
vol.93, pp.1591-1595, 1996[13] J. Sethian, Level Set Methods and Fast Marching Methods, second
edition“”, Cambridge University Press, UK, 1999
[14] 倉爪，由井，辻，岩下，原，長谷川, “Fast Level Set Method の提案とビデオ画像の移動物体のリアルタイム追跡”, 情報処理学会
論文誌, vol.44, No.8, pp.2244-2254, 2003[15] Y. Iwashita, R. Kurazume, T. Tsuji, K. Hara and T. Hasegawa, “Fast
Implementation of Level Set Method and Its Realtime Applications”,
IEEE International Conference on Systems, Man and Cybernetics,
pp.6302-6307, 2004[16] D. Adalsteinsson and J. Sethian, “The fast construction of extension
velocities in level set methods”, J. Computational Physics, vol.148,
pp.2-22, 1999[17] D. L. Chopp, “Computing minimal surfaces via level set curvingflow”, J. Computational Physics, vol.106, pp.77-91, 1993[18] K. Otsuka and N. Mukawa, “Multiview occlusion analysis for tracking densely populated objects based on 2-D visual angles”, Proceedings of the 2004 IEEE Computer Society Conference on Computer
Vision and Pattern Recognition, vol.1, pp.90-97, 2004(b) 3D model reconstruction(a) Real scene(c) Texture mapping

図 9 詳細な 3 次元形状復元

5. ま と め
本報告ではシーン内に存在する複数対象物体の 3 次元形状を
オクルージョンに頑強に復元するモーションスキャナシステム

435