中部大学工学部情報工学科 卒業論文 視体積交差法による3次元形状

中部大学工学部情報工学科
卒業論文
視体積交差法による 3 次元形状復元の高速化
奥村 幸司
2004 年 3 月
A Graduation Thesis of College of Engineering, Chubu University
Improvement in The Speed of 3D Shape Reconstruction by Sihouette
Volume Intersection
Kouji Okumura
目次
第1章
はじめに
1
第2章
視体積交差法
3
2.1 視体積交差法の基本アルゴリズム . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.1
VIM(Volume intersection method)
. . . . . . . . . . . . . . . . . .
3
2.1.2
SCM(Space carving method) . . . . . . . . . . . . . . . . . . . . . .
4
2.1.3
カメラ配置 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.1.4
ボクセル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.1.5
VIM におけるボクセルデータの欠損 . . . . . . . . . . . . . . . . .
6
2.1.6
SCM におけるボクセルデータの欠損 . . . . . . . . . . . . . . . . .
8
2.1.7
VIM と SCM の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
第3章
VIM-SCM の複合アルゴリズム
11
. . . . . . . . . . . . . . . . . . . . . 11
3.0.8
複合アルゴリズムの処理手順
3.0.9
提案手法の利点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
第4章
評価実験
15
4.1 ルックアップテーブルによる高速化 . . . . . . . . . . . . . . . . . . . . . . 15
4.2 実験結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
第5章
おわりに
23
謝 辞
25
参考文献
27
iii
図目次
2.1 VIM の概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2 SCM の概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3 カメラ配置 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.4 ボクセル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.5 VIM におけるボクセルデータの欠損 (1) . . . . . . . . . . . . . . . . . . . .
7
2.6 VIM におけるボクセルデータの欠損 (2) . . . . . . . . . . . . . . . . . . . .
8
2.7 SCM におけるボクセルデータの欠損 . . . . . . . . . . . . . . . . . . . . .
8
3.1 シルエット画像 (4 視点) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 VIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 SCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 人物領域 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.1 パターン 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 パターン 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.3 パターン 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 パターン 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.5 パターン 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.6 パターン 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.7 パターン 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.8 パターン 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.9 パターン 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.10 パターン 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.11 ボクセル数と各アルゴリズムの処理時間 . . . . . . . . . . . . . . . . . . . 21
v
表目次
2.1 カメラキャリブレーション結果 . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2 ボクセルのサイズと個数 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3 VIM と SCM の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
4.1 各アルゴリズムの処理時間 [sec] . . . . . . . . . . . . . . . . . . . . . . . . 21
vii
第1章
はじめに
多視点映像から物体の 3 次元形状を復元する手法として，ステレオ法と視体積交差法が用
いられている．ステレオ法は，異なる視点から撮影された 2 次元画像上で物体表面上の点
の対応づけを行い，三角測量の要領で対象までの距離を求める手法である．視体積交差法
では，対応づけを行わないために誤対応が生じず，安定な形状復元が行える．
既に提案されている視体積交差法のアルゴリズムは，VIM(Volume intersection method)
と SCM(Space carving method) の二種類に分類される．VIM は，実際に複数のシルエッ
トを元の 3 次元空間に投影し，それぞれの視体積の共通部分を求める手法である．SCM
は，3 次元空間中の個々の点を，各画像平面に逆投影したとき，全てのシルエットの内部
に逆投影される点は，対象の内部の点として残し，それ以外は対象の外部の点として除
去する手法である．本研究では，SCM と VIM の利点を組み合わせた視体積交差法を提案
し，視体積交差法の高速化を目指す．
1
第2章
視体積交差法
視体積交差法とは，物体の 2 次元シルエットを基に 3 次元形状を復元する手法である．
異なる視点により得られた対象物体の 2 次元シルエットを 3 次元空間に投影した際に得ら
れる錐体 (視体積) の交差しているボクセル群を対象の形状とする．
ボクセルとは計測空間を x，y ，z に分割する際の単位格子である．
2.1
視体積交差法の基本アルゴリズム
視体積交差法には基本アルゴリズムとして以下の二種類が提案されている．
2.1.1
VIM(Volume intersection method)
複数の対象物体の 2 次元シルエットを元の 3 次元空間に投影し，各視体積の共通部分を
求める (図 2.1 参照)．すなわちシルエット制約を満足する点の集合を視体積の共通部分と
して求める手法である．
ここでシルエット制約とは対象 (本研究では人物) は任意の視点から撮影して得られる物
体の 2 次元シルエットを実空間に投影して得られる錐体 (視体積) の中に含まれるという
ことである．
3
第 2 章 視体積交差法
カメラ1
カメラ2
図 2.1: VIM の概念
2.1.2
SCM(Space carving method)
3 次元空間中の個々の点 (ボクセル) を各画像平面に逆投影したとき，全ての人物領域
(シルエット) の内部に逆投影される点は対象の内部の点として残し，それ以外は外部の点
として削除する (図 2.2 参照)．すなわちシルエット制約に基づいて物体の内点は残し，そ
れ以外の点を削除するという手法である．
u
(u1,v1) v
u
v (u2,v2)
画像1
画像2
V[x1][y1][z1]
z
y
x
ボクセル空間
u
v
(u3,v3)
画像3
図 2.2: SCM の概念
4
2.1. 視体積交差法の基本アルゴリズム
カメラ配置
2.1.3
本研究では，3 次元空間の領域を，縦 2m，横 3m，高さ 2m とした．カメラは地面から
の高さを全て 2.8m とし，図 2.3 のように配置し，ボクセルデータの復元を実行した．
カメラ3
カメラ2
z
カメラ1
カメラ0
o
y
x
2.8m
(4台共通)
2m
2m
3m
ボクセル対象空間
図 2.3: カメラ配置
また，カメラキャリブレーションの結果を表 2.1 に示す．
表 2.1: カメラキャリブレーション結果
カメラ番号
カメラ位置 (x,y,z)
焦点距離
画像中心 (uc,vc)
縦横比
レンズ歪
0
4405,1265,2804
536.4
341,227
1.007
8.825e-07
1
4489,6132,2953
533.5
370,174
1.005
1.044e-06
2
624,11389,2846
551.6
373,225
1.011
1.828e-06
3
703,1343,2786
536.1
306,196
1.007
1.783e-06
2.1.4
ボクセル
ボクセルとは，x 軸，y 軸，z 軸の 3 次元空間において分割された単位格子のことであ
る (図 2.4 参照)．
5
第 2 章 視体積交差法
ボクセル(voxel)
z
y
x
図 2.4: ボクセル
本研究におけるボクセルのサイズと個数の関係を表 2.2 に示す．
表 2.2: ボクセルのサイズと個数
サイズ [cm]
個数
10
20 × 30 × 20
5
40 × 60 × 40
2
100 × 150 × 100
1
200 × 300 × 200
3 次元空間の領域が縦 2m，横 3m，高さ 2m なため，それに対応して分解能が高くなれば
ボクセル数が増加する．
2.1.5
VIM におけるボクセルデータの欠損
VIM におけるボクセルデータの欠損は，高分解能の場合に生じる．分解能を 2cm，1cm
としたときの VIM と SCM それぞれにより復元したボクセルデータを示す (図 2.5)．SCM
と比較すると，VIM の方はボクセルデータの欠損が目立つ．これは，画像中において連
続する画素を注目したときに分解能 5cm のボクセルの場合は連続してボクセルを通過し
ているが，分解能 2cm にするとボクセルの間隔が狭くなり通過しない部分が出現してし
まうからである．(図 2.6 中の斜線部分)．
6
2.1. 視体積交差法の基本アルゴリズム
(a)VIM(2cm)
(b)SCM(2cm)
(c)VIM(1cm)
(d)SCM(1cm)
図 2.5: VIM におけるボクセルデータの欠損 (1)
7
第 2 章 視体積交差法
5cm
5cm
2cm
2cm
ボクセルの穴
カメラ
図 2.6: VIM におけるボクセルデータの欠損 (2)
2.1.6
SCM におけるボクセルデータの欠損
SCM におけるボクセルの欠損は，低分解能の場合に生じる．分解能を 10cm としたと
きの VIM と SCM それぞれにより復元したボクセルデータを図 2.7 に示す．
(a)VIM(10cm)
(b)SCM(10cm)
図 2.7: SCM におけるボクセルデータの欠損
8
2.1. 視体積交差法の基本アルゴリズム
低分解能によるボクセルデータ作成では，画像サイズに対してボクセルが少数になる．ま
た，SCM はボクセルを画像に投影する手法である．そのため，ボクセルが少数であると
SCM の画像に対する注目範囲が狭くなる．例えば，本研究では 10cm のボクセルデータ
を作成する場合，ボクセル数が 20 × 30 × 20 の 12000 個になる．画像サイズは 640×480
を使用し，画素数は 307200 画素になる．画像に対して，SCM によって注目できる範囲が
最大でも 12000 画素までしか対応できない．すなわち，ボクセル数が画素数よりも少ない
ため，ボクセルの欠損が生じる．
ボクセル数 = 12000 < 307200 = 画素数
(2.1)
SCM におけるボクセルデータの欠損は，これが原因である．
2.1.7
VIM と SCM の比較
VIM はシルエット制約を満足する点の集合を視体積の共通部分として求める手法であ
る．これに対し，SCM はシルエット制約に基づいて物体の内点を残して，それ以外の点
を削除する手法である．各手法の特徴として，表 2.3 に復元対象の解像度を低分解能，高
分解能としたときの処理時間とボクセルの欠損について示す．
表 2.3: VIM と SCM の比較
低分解能
高分解能
処理時間
欠損
処理時間
欠損
VIM
長い
なし
長い
あり
SCM
短い
あり
短い
なし
9
第3章
VIM-SCM の複合アルゴリズム
本研究では，VIM と SCM を組合わせた手法を提案する．本手法は VIM の低分解能にお
けるボクセルデータと，SCM の高分解能におけるボクセルデータの欠損なしという利点
を組み合わせたものである．
3.0.8
複合アルゴリズムの処理手順
以下に複合アルゴリズムの処理手順を示す．
Step1 背景差分により物体領域 (シルエット) を抽出する．本研究では人手により抽出
したものを用いる．
図 3.1: シルエット画像 (4 視点)
11
第 3 章 VIM-SCM の複合アルゴリズム
Step2 VIM により低分解能 (10cm) のボクセルデータを作成する (図 3.2 参照)．これに
より次のステップにおける SCM の走査対象領域の絞り込みが可能となる．
Step2
画像1
画像2
z
y
x
ボクセルデータ
ボクセル空間
図 3.2: VIM
Step3 Step2 で得られたボクセル領域を対象に，SCM により高分解能 (2cm) なボクセ
ルデータを復元する (図 3.3 参照)．
Step2
画像1
画像2
z
y
x
ボクセル空間
ボクセルデータ
図 3.3: SCM
3.0.9
提案手法の利点
本提案手法の利点は，VIM により粗い人物領域のボクセルを絞り込み，SCM のラスタ
走査の量を削減することで，計算時間の短縮が可能となる点である．更に，低分解能で
12
VIM，高分解能で SCM を実行しているためボクセルデータの欠損がない．図 3.4 に 2 人
の場合と 3 人の場合の復元したボクセルデータを示す．
(a)2人
(b) 3人
図 3.4: 人物領域
13
第4章
評価実験
4 枚の多視点画像を用いた 3 次元形状の復元実験を行った．実験には Point Grey Research
社の Dragonfly(IEEE-1394 カメラ) を使用した．得られる画像の解像度は 640×480 画素で
ある．実験に使用した PC は XEON2.20GHz の DualCPU である．
4.1
ルックアップテーブルによる高速化
提案手法は，ルックアップテーブルを使用している．ボクセルデータを作成するにあ
たって，計算を要する部分は光線を求める部分にある．光線を求めることにより，画像座
標と対応する世界座標 (3 次元空間の座標) が分かる (または，世界座標と対応する画像座
標)．VIM では画像座標から対応する世界座標を，SCM では世界座標から対応する画像
座標を求める (図 2.1，図 2.2 参照)．ルックアップテーブルはこの光線を求める計算を対
象に作成し，計算時間を短縮できるようにした．
4.2
実験結果
本手法において，分解能を 5cm とした場合と 2cm とした場合の復元に費やす時間を評
価した．本手法では，分解能 5cm では VIM の分解能を 10cm，SCM の分解能を 5cm とし
て作成し，分解能 2cm では VIM の分解能を 10cm，SCM の分解能を 2cm としてボクセル
データを作成する．以下にシルエットを抽出した 10 パターンの画像と復元したボクセル
データを示す．
15
第 4 章 評価実験
図 4.1: パターン 1
図 4.2: パターン 2
16
4.2. 実験結果
図 4.3: パターン 3
図 4.4: パターン 4
17
第 4 章 評価実験
図 4.5: パターン 5
図 4.6: パターン 6
18
4.2. 実験結果
図 4.7: パターン 7
図 4.8: パターン 8
19
第 4 章 評価実験
図 4.9: パターン 9
図 4.10: パターン 10
20
4.2. 実験結果
次に，この 10 パターンの各アルゴリズムの処理時間とボクセル数の関係を図 4.11 に示し，
処理時間の平均を表 4.1 に示す．
0.9
vim
scm
vim-scm
0.8
処理時間 [sec]
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
15500
16000
16500
17000
17500
18000
18500
19000
19500
20000
20500
21000
ボクセル数
図 4.11: ボクセル数と各アルゴリズムの処理時間
表 4.1: 各アルゴリズムの処理時間 [sec]
SCM
本手法
平均 (5cm)
0.3280 0.0153
0.0335
平均 (2cm)
0.7349 0.2095
0.0438
VIM
分解能 5cm のボクセルデータを作成する場合，SCM は 0.015[sec]，本手法は 0.034[sec] で
あり，本手法よりも SCM のみで作成した方が計算時間が短い．これは，対象ボクセルが
低分解能のとき，SCM のラスタ走査の範囲が本手法より狭くなるため，時間がかからな
いからである．しかし，ボクセルを 2cm と高分解能にした場合，VIM は平均 0.735[sec]，
SCM は平均 0.210[sec] に対し，本手法では，約 0.04[sec] と計算時間を大幅に短縮するこ
とができた．
21
第5章
おわりに
本研究では，VIM の低分解能におけるボクセルデータと，SCM の高分解能におけるボク
セルデータの欠損なしという利点を組み合わせたアルゴリズムを使用することで，それぞ
れのアルゴリズム単体で用いるときよりもボクセルデータ作成の時間を短縮させることが
出来た．分解能 5cm のボクセルデータを作成する場合，対象ボクセルが低分解能なため，
SCM のラスタ走査の範囲が本手法より狭くなり，SCM のみで作成した方が計算時間が短
い．しかし，分解能 2cm のボクセルデータを作成する場合，本手法では約 0.04[sec] で作
成することができた．本手法は高分解能のボクセルデータを復元する際に有効である．
背景差分による物体検出の時間が約 0.045[sec] であるので，このアルゴリズムでリアル
タイム表示を実行すれば，約 0.085[sec] でボクセルデータを作成できると考えられる．今
後はこのアルゴリズムを用いたリアルタイムアプリケーションの実現を目指す．
23
謝 辞
本研究を行うにたり，終始懇切なるご指導を頂きました中部大学工学部 藤吉弘亘助教
授に謹んで深謝する．最後に，本研究で用いたプログラムの開発において協力して頂いた
藤吉研究室の皆様に感謝する．
25
参考文献
[1] ウ小軍, 和田俊和, 東海彰吾, 松山隆司,” 平面間透視投影を用いた並列視体積交差法”,
情報処理学会論文誌: Vol.42,No.SIG6,pp.33-43,June 2001
[2] ウ小軍, 延原章平, 和田俊和, 松山隆司,” 多視点映像 k らの実時間 3 次元形状復元とそ
の高精度化”, 情報処理学会論文誌:コンピュータビジョンとイメージメディア
[3] 延原章平, 和田俊和, 松山隆司,” 弾性メッシュモデルを用いた多視点画像からの高精
度 3 次元形状復元”, 情報処理学会論文誌:コンピュータビジョンとイメージメディ
ア,Vol43,No.SIG11,pp.53-63,2002
[4] 高井勇志, 松山隆司,”3D ビデオ映像の生成・編集・表示”, 映像情報メディア学会技術
報告,Vol25,No.53,pp.17-22,2001
27
視体積交差法による 3 次元形状の復元
奥村 幸司
（中部大学工学部情報工学科）
2004 年 3 月