2P1-C13

並列 Fast Level Set Method による実物体の高速な 3 次元形状復元
Real-time 3D Shape Reconstruction of human bodies by Parallel Fast Level Set Method
 学 岩下 友美（九州大）

正 倉爪 亮（九州大）†Yumi Iwashita†‡

正 原 健二（九州大）†Ryo Kurazume‡

Kenji Hara

正 長谷川 勉（九州大）

and Tsutomu Hasegawa†

Kyushu University,Graduate School of Information Science and Electorical Engineering
Kyushu University,Graduate School of Design

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 thescene at the same time, it is quite diﬃcult to reconstruct a precise 3D model of each person separately due to theocclu ｆ sion between them. To deal with these problem, we have developed a motion capture system using theFast Level Set Method for recoverying 3D models 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 LevelSet Method. As an application of the estimation method, we propose a load balancing method based on predictedmoving direction for parallel Fast Level Set Method implemented on a PC cluster, Tracking experiment 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

はじめにステムと比較してより高速に 3 次元形状の復元が可能であることを示す．

複数のカメラを周囲に配置して，人間の形状や動きだけではな
く 見え も計測し再現するマーカレスのモーションキャプチャシステムの研究が行われている．このシステムの実現方法の代表
2 Fast Level Set Method
的な手法として，視体積交差法と多視点ステレオが挙げられる．
視体積交差法は，任意の視点から対象を撮影したとき，その対象
Osher, Sethian らによって提案された Level Set Method
が 2 次元シルエットを実空間に投影した錐体中（視体積）に含ま(LSM)5)は，多くの計算量を必要とするため，リアルタイム性れるという制約条件に基づいている1)．そのため，多数台のカメが要求されるアプリケーションには不向きであると考えられてラを用いることにより詳細な 3 次元形状の復元が可能となるが， きた．この問題に対し，我々は LSM の高速化手法として Fast
一方カメラ台数の増加に伴い計算コストが高くなるという問題がLevel Set Method (FLSM)6)を提案した．以下，これらの手法ある．
を簡単に紹介する．
一方，多視点ステレオは異なる視点から撮影された 2 次元画像上で物体表面上の点の対応付けを行い，三角測量の原理により対2.1 Level Set Method とその高速化手法
象物体の 3 次元形状を復元する手法である．Kanade らは 51 台
2 次元 xy 平面上での LSM を用いた境界追跡法について説明すのカメラをドーム上に配置して多視点で計測するシステムを開発
る．本手法ではまず，平面上の各点 (x, y) において，時刻 t におけしている2) 3)．しかし，モデル構築のための計算コストやデータる補助関数 ψ(x, y, t) を導入し，境界位置 γ(x, y, t) は ψ(x, y, t) =量が非常に大きく，人間のような複雑形状の実時間計測は困難で0 を満たす (x, y) で表すこととする．次に，ψ についての差分方ある．
程式を以下のように定義する．
さらに，従来提案されている 3 次元形状復元手法では，そのほとんどが単一物体あるいはオクルージョンの生じない複数物体をn+1
nnψi,j= ψi,j− F (i, j)|∇ψi,j|∆t(1)対象とした手法であり，シーン内に複数物体が存在し物体間に相互オクルージョンが生じる場合，それぞれの物体形状を同時に復ここで，(i, j) は xy 平面上のグリッド座標，∆t は時間ステップ元することは困難である．
幅である．また，F は ψ の成長速度であり，単位時間あたりにこれに対し，我々はこれまでにシーン内に存在する複数対象物体
ψ が法線方向に移動する量を示す．補助関数値が 0 のセル (zeroの 3 次元形状をオクルージョンに頑強に復元するモーションスキャlevel set)，つまり ψ = 0 として境界を抽出することで，位相変ナシステムの試作機を提案した4)．試作システムでは，移動物体化に対応した境界追跡が可能となる．
追跡や 3 次元幾何モデリングなど，様々な分野で用いられる Level
式 1 を更新するには，2 次元画像上の全てのセルにおいて成長Set Method5)の高速化手法である Fast Level Set Method6)を，速度を決定する必要がある．拡張成長速度場を用いた LSM では，対象物体の周囲に 2 台配置したステレオカメラから取得したステ各セルの成長速度を決定するために, まず zero level set での成レオ距離画像に適用することで，複数対象物体の 3 次元形状をオ長速度を決定し，その他のボクセルでは最も近い zero level set
クルージョンに頑強に復元している．また，7 台の計算機からなのボクセルの成長速度をコピーして成長速度場を構築する．しかる PC クラスタへと実装し，Fast Level Set Method 処理の並列し，拡張成長速度場の構築処理において，各セルで現在の zero計算により，3 次元形状の実時間復元を実現している．しかし，level set からの距離を得る際，各セルからの最近傍 zero level set
試作システムでは並列 Fast Level Set Method 処理に割り当ての探索処理を行わなくてはならない．この計算コストは非常に高るボクセル空間を単純に分割しているため，物体の位置や形状，く，これが LSM の大きな問題となっている．
物体数によって特定の計算機に負荷が集中する場合があった．
LSM の計算コストを削減するために，これまでに様々な手法がそこで本報告では，Fast Level Set Method の特性に着目した提案されており，その代表的な手法として
Narrow Band Method
動物体境界の移動方向推定法を提案し，その応用例として，PC（以下,NB）が挙げられる．一般に境界領域の追跡において，空クラスタを用いた並列 Fast Level Set Method のための境界移間全体に対して補助関数を計算する必要はないことから，この手動方向の予測値に基づく計算負荷の均衡化手法を提案する．提案法では zero level set に近い領域 (Narrow Band) だけに処理を手法を用いた動物体の 3 次元形状追跡実験を行い，従来の試作シ限定することで処理の効率化を図っている．
[No. 06-4] Proceedings of the 2006 JSME Conference on Robotics and Mechatronics, Waseda, Japan, May 26-28, 2006
2P1-C13(1)2.2

Fast Level Set Method

3.1

NB は LSM と比べて高速な手法であるが，依然として計算コストは高い．この問題に対し，LSM の高速化手法として Fast Level
Set Method (FLSM)6)を提案した．
FLSM は Fig.1 (a) に示す参照マップを用いて，最近傍探索処
理をあるルールに基づく単純な数値の上書き処理に置き換えることで，高速に拡張成長速度場を構築する．この参照マップは，原点周辺にあるセルを原点からの距離に応じて分類したものである．
例えば，リスト Rr は原点からの 2 乗距離が r であるセルの集合とする．

810 59 410 581052129 104 5 8
1 2 5 100 1 4 9
1 2 5 105 45 810 9 10RrF1

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

F3F3F1 F5F6 F 1F4F7F1F6F6F7 F 1

F1 F3F7F6 F 1F4F6F3F75. 3. で抽出されたボクセル領域に対し FLSM を適用し，距離データ点を含む最も外側のボクセル（境界ボクセル，zerolevel set）を追跡し，複数対象物体の分離した 3 次元形状を復元する．オクルージョン領域内の形状は，前時刻での境界位置を保つことで連続した滑らかな形状を保持する．

F2 F1 F7 F1 F5F1zero level set(c1) Rr = 10(c2) Rr = 10F 2 F1 F1 F 1 F5F3F3F1 F5F1F6F6F7 F 1F2 F1 F 5F1F1 F3F7F6 F 1F4F6F3F7F2F3F3F4F2 F2F2 F2F2 F2F3 F2F3 F3F1 F5F1 F5F1 F5F1 F5F1 F6F5F5 F5F5 F6F6 F6F6 F76. 2 から 5 を繰り返す．

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

Fig.1: Reference map and the construction process of theextension velocity field.
次に，作成した参照マップを用いて拡張成長速度場を構築する．
ただし，zero level set での成長速度は予め決定されているとする．
まず，リスト Rδ(δ+1) を用いて，ある zero level set からの 2 乗距
離が δ(δ + 1) であるセルを選択し，その zero level set に格納されている成長速度の値を選択されたセルに仮登録する (Fig.1 (c1))．
この処理をすべての zero level set に対して行う (Fig.1 (c2))．次に，添字の値を 1 小さくして同じ処理を行い (Fig.1 (c3))，これを添字の値が 0 になるまで繰り返す．ただし，仮登録の際，異なる値がすでに仮登録されていた場合には，新たな値を上書きすることにする．これにより全ての処理が終了した時には，各セルには最も近い zero level set における成長速度の値が登録されている (Fig.1 (c4))．このように，参照マップ球の距離に応じたリストを利用することで，距離比較を行うことなく代入処理だけで拡張成長速度場を構築する．
さらに FLSM では Fig.1 (b) に示すように分割した参照マップを用いることで，拡張成長速度場の構築処理において書き込む領域を限定し，さらに効率化を実現している．例えば，ある zerolevel set Z の左側に zero level set A0 が隣接している場合，Zの左側の領域 (A，B ，H) には，A0 よりも Z に近い点は存在しない．このように，隣接するグリッドが zero level set かどうかを調べ，その位置関係によって，書き込みのオーバーラップを減らし，拡張成長速度場の高速な構築処理を可能としている．

32. 測定対象を内部に設置し，全てのステレオカメラを用いてステレオ距離画像を取得する．

4. 取得したステレオ距離画像と前フレームで復元した 3 次元形状情報を用い，オクルージョン領域を推定する．

F2 F1 F5F2 F1 F5F1 F3(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

F1F1

1. まず内部パラメータが既知の校正済みステレオカメラ (PointGreay 社製，BumbleBee) を大きさ・形状が既知の静止物体（例えば立方体）の周囲に設置し，物体の形状モデルとステレオ距離画像を用いて ICP アルゴリズムにより外部パラメータを推定する．

3. 複数距離画像を一つの 3 次元ボクセル空間に投影し，距離データを含むボクセルを抽出する．

F2 F1 F5 F1 F5F1FLSM による人体形状の復元と追跡開発したモーションスキャナシステムの処理の流れを以下に示す．

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

本章ではまずこれまでに提案した，複数対象物体の 3 次元形状をオクルージョンに頑強に復元するモーションスキャナシステムの試作機について概説する4)．従来，様々なオクルージョンの対応手法が提案されているが，一般に推定される物体形状は既知かつ楕円などで近似された単純な構造であり，自由形状物体のオクルージョン判定には拡張されていない7)．次に FLSM の特性に着目した動物体境界の移動方向推定手法を提案し，その応用例として，PC クラスタを用いた並列 FLSM のための境界移動方向の予測値に基づく計算負荷の均衡化手法を提案する．

上記の計算は，処理の高速化を図るため，ギガビット LAN の一つである Myrinetxp で相互に接続された 7 台の計算機 (PentiumXeon, 3.06 GHz) により並列処理される（Fig.2）．まずそれぞれステレオカメラが接続された 2 台の計算機 (PC1,PC2) により，同期した 2 枚のステレオ距離画像を取得する．次に得られた距離画像は FLSM 計算用計算機に送られる．ただしここではボクセル空間を 4 つの領域に均等に分割し，それぞれの空間に 1 台ずつ計算機を割り当て (PC3-PC6)，4 台で並列に FLSM の計算を実行した．各 FLSM 用計算機では，まず複数距離画像の統合を行った後，それぞれの領域に対して FLSM を適用する．最後に処理結果が表示用計算機 (PC7) に送られ，ボクセル空間全体の処理結果として統合，表示される．

PC1

PC2

PC4

PC5

PC3
PC3

PC6

PC4
PC6

PC5

Stereocamera 3

Stereocamera 1
PC7

PC cluster system3D voxel space

Fig.2: PC cluster system.
3.2

対象物体の移動方向の推定

次に動物体境界の移動方向の推定手法について述べる．まず，
時刻 t − ∆t で構築した 3 次元モデルの境界ボクセル Z(t − ∆t, i)(0 ≤ i < N (t − ∆t)) と時刻 t で構築した 3 次元モデルの境界ボクセル Z(t, j) (0 ≤ j < N (t)) との対応付けを行う．ここで，N (t) は時刻 t で復元した 3 次元モデルの境界ボクセルの総数とする．具体的には，まず時刻 t − ∆t で復元した境界ボクセルZ(t − ∆t, i) にラベル L(t − ∆t, i) を格納し，距離場の構築処理と同様の手順で Narrow Band 内のボクセルにラベル L(t − ∆t, i)をコピーする．全ての境界ボクセルのラベルを Narrow Band 内のボクセルにコピーすると，Narrow Band 内のボクセルには 3 次元形状の最近傍境界ボクセルのラベルが格納される（Fig.3(a)）．
次に，時刻 t で構築した 3 次元形状の境界ボクセル Z(t, j) に格納されているラベルより，境界ボクセル Z(t − ∆t, i) と境界ボクセル Z(t, j) との対応付けを行い，相対変位を表すベクトル Link(t, j) = Z(t, j) − Z(t − ∆t, i) とする．ここで，時刻(t − ∆t) ∼ t において対象物体の局所的な形状は保持され，かつ2P1-C13(2)PC4

対象物体の加速度は 0 と仮定すると，Link(t, j) と境界ボクセルZ(t, j) 近傍の境界面の法線ベクトル n(t, j) との一致度より，対象物体の移動方向を推定することができる（Fig.3.(b)）．そこで，
時刻 t における対象物体の移動方向ベクトル M D(t) はM D(t) = (1.0 − α)PC3

L4 L4 L3 L3 L7 L7 L8 L8zero level set (a)PC6(b)

Fig.4: Adaptive division of voxel space.
n(t, j')Z(t, j)

そこで，3.2 節で提案した動物体の移動方向の予測値を利用し，並列 FLSM に割り当てるボクセル空間領域をより最適に決定する．具体的には，物体形状分布を用いて決定した分割点
D(i, t) = (dx (i, t), dy (i, t), dz (i, t)) (i = 0 ∼ FLSM の PC 数) とすると，新たな分割点 Dnew (i, t) = (dnx (i, t), dny (i, t), dnz (i, t))を以下のように決定する．

Link(t, j)

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

Dnew (i, t) = D(i, t) + γM D(t)/|M D(t)|(b)Fig.3: Moving direction estimation of moving object.
対象物体の移動方向を推定する手法として，例えば復元した 3次元形状の重心位置の時系列データを用いることが考えられる．
しかし，例えば腕や足などの体の一部のみを動かす場合，全体の重心位置を用いる手法ではその部位のみの移動方向を推定することは困難である．これに対し，提案した移動方向推定法は，境界の局所的な移動方向の推定が可能であり，移動部位の切り出しも期待できる．
例として半径 0.1m の球体を用いて移動方向推定のシミュレーション実験を行い，その推定性能を評価した．実験条件は，X 軸，Y 軸，Z 軸に沿ってそれぞれ 0.01m ずつ，合計 1.5m 動かした
場合と，Y 軸を回転軸に 5 度ずつ回転した場合の 4 通りである．
また，軸方向へ移動する場合は α = 0.0，β = 0.98 とし，軸周りで回転する場合は α = 0.4，β = 0.98 とした．Table1 に推定された移動方向ベクトルと実際の移動方向ベクトルとの角度の差の平均と標準偏差を示す．これより，提案手法により物体の移動方向の推定が可能であることが確認できる．一方，軸方向への移動と比較し，軸周りの回転の推定結果が悪いことがわかる．これは，3 次元形状の境界ボクセルに格納されているラベルを Narrow
Band 内にコピーする際，異なるラベルが既に仮登録されている場合には，新たなラベルを上書きするため，正しいラベルが保持されない場合があるためと考えられる．この解決法として，復元した 3 次元形状のラベルを Narrow Band 内にコピーする際に，3 次元形状の法線方向へのコピーを優先することが挙げられる．

3.3PC3n(t, j)

Z(t, j')L3 L3 L2 L2 L6 L6 L7 L7L4 L3 L3 L2 L6 L7 L7 L8PC6(a)と定義する．ただし，α, β は定数である．
zero level set(Time=t)

PC5

Updated division
plane

Link(t, j) + αM D(t − ∆t)(2)

L1 L1 L1 L5 L5 L5L2 L2 L1 L1 L5 L5 L6 L6L3 L2 L2 L1 L5 L6 L6 L7PC4Objects|Link(t,j)·n(t,j)|>β

L1 L1 L5 L5PC5Division plane

並列 FLSM のための負荷分散の最適化

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

(3)

ただし，γ は定数である．これにより，各計算機で復元する 3 次
元形状のボクセル数はほぼ均一となり，並列 FLSM の負荷分散の最適化が期待される．

4実験

提案したモーションスキャナシステムを移動する人体へ適用し，境界移動予測値を用いた負荷均衡化手法の有効性を確認する実験を行った．使用したボクセル空間の解像度は 100 × 100 × 100（ボクセル空間の一辺は 1.5cm）である．
まず，Fig.5(a) のように腕をあげた状態でシーン内を移動する対象物体の追跡実験を行った．ただし，並列 FLSM に割り当てるボクセル空間領域を単純に 4 分割した場合 (Exp.A)，形状分布から分割面を決定した場合 (Exp.B)，及び対象物体の移動方向の予測値に基づいてボクセル空間を分割する場合 (Exp.C) について実験を行った．Fig.5(b) に (Exp.A) の結果，Fig.5(c) に(Exp.C) の結果をそれぞれ示す．この結果より，(Exp.A) では特定の計算機に FLSM 計算負荷が集中していたため，腕の一部に欠損が生じているが，(Exp.C) では，欠損を生じることなく 3 次元形状を復元している．また Table2 に (Exp.A)，(Exp.B)，及び (Exp.C) 対象物体の移動方向の予測値に基づいてボクセル空間を分割する場合の計算時間の比較を行った．ただし α = 0.3，
β = 0.9，γ = 4 である．これより，(Exp.C) の物体の移動方向の予測値に基づく FLSM 計算機間の計算負荷の均衡化を行う場
合，復元する 3 次元形状のボクセル数が増加するにも関わらず，より高速に 3 次元形状の復元が可能であることがわかる．

(b1)
(b2)
(b) Tracking result of a moving human body(a) Real scene

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

Fig.5: 3D model reconstruction using load balancing
method.
さらに提案した手法に基づき，ステレオカメラ 5 台を用いて詳細な人間動作の追跡実験を行った．実験では Fig.6 に示すように，ステレオカメラ 1∼4 は側面に，またステレオカメラ 5 は天2P1-C13(3)Table 1: Accuracy of the estimated moving direction.
Translation along the x-axis
Translation along the y-axis
Translation along the z-axis
Y-axis rotation

Average [deg.]
0.79
0.51
2.45
4.67

Standard variation [deg.]
1.77
1.59
2.72
2.45

Table 2: Computation time of the parallel FLSM.
Voxel space division(Exp.A) Equal division(Exp.B) Adaptive division(Exp.C) Adaptive division using moving direction

Average calculation
time [msec./1voxel ]
0.015
0.012
0.010

Total voxel number ofthe reconstructed 3D model
7638
9004
12019

井に設置した．Fig.7(a) に対象物体の実際の様子，及び Fig.7(b)に復元した形状を示す．また生成したモデルに対し，マーチング
キューブ法を適用し，その後テクスチャマッピングを行った結果を示す（Fig.7(c)）．
Stereo camera 5
Stereo camera 4

2.5m

2.5m

Stereo camera 3(b1) Cross view(b2) Top view(c1) Cross view(c2) Cross view(b) 3D model reconstruction

1.5m2.5m

2.5m

Center voxel(a) Real scene

1.5m(c) Texture mapping

Stereo camera 1

Stereo camera 2

Fig.7: Precise 3D model reconstruction.

Fig.6: 3D motion scanner using multiple stereo cameras
and the camera settings.

5

まとめ

本報告ではシーン内に存在する複数対象物体の 3 次元形状をオクルージョンに頑強に復元するモーションスキャナシステムの概要を示した．また，Fast Level Set Method の特性を用いた動物体の移動方向推定手法を提案し，その応用例として，PC クラス
タを用いた並列 Fast Level Set Method のための境界移動方向の予測値に基づく計算負荷の最適化手法を提案した．動物体の追跡実験により従来システムと比較して，より高速な 3 次元形状の復元が可能であることを示した．今後は増設したステレオカメラを用い，シーン内に存在する複数対象物体の 3 次元形状をオクルー
ジョンに頑強に実時間で復元するシステムを開発する．

1) W. Martin and J. Aggarwal, “Volumetric descriptionof objects from multiple views”, IEEE Transactions on
Pattern Analysis and Machine Intelligence, vol.5, No.2,pp.150-158, 1983
2) T. Kanade, P. Rander and P. Narayanan, “VirtualizedReality: Constructing Virtual Worlds from Real Scenes”,

IEEE Multimedia, Immersive Telepresence, vol.4, No.1,
pp.34-47, 1997
3) S. Vedula and S. Baker and T. Kanade, “Image-BasedSpatio-Temporal Modeling and View Interpolation of Dynamic Events”, ACM Transactions on Graphics, vol.24,
No.2, April, 2005
4) 岩下，倉爪，辻，原，長谷川, “Fast Level Set Method を用いた複数移動物体の 3 次元追跡”, 日本ロボット学会論文誌,
vol.23, No.7, pp.813-820, 2005
5) 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
6) 倉爪，由井，辻，岩下，原，長谷川, “Fast Level Set Methodの提案とビデオ画像の移動物体のリアルタイム追跡”, 情報処
理学会論文誌, vol.44, No.8, pp.2244-2254, 2003
7) K. Otsuka and N. Mukawa, “Multiview occlusion analysis
for tracking densely populated objects based on 2-D visualangles”, Proceedings of the 2004 IEEE Computer Society
Conference on Computer Vision and Pattern Recognition,
vol.1, pp.90-97, 2004

2P1-C13(4)