修士論文審査資料

複数シルエットを実現する立体の探索アルゴリズム
数理情報学専攻 66206

大神 智洋
指導教員: 杉原厚吉 教授
平成 20 年 2 月 4 日

1 概要
複数のシルエットが与えられたときに，それらのシルエットをもつ立体を構成することは，コンピュータビジョンの分野における基本的問題の一つである．シルエットに対する視点が未知である場合 [1]，与えられたシルエットをもつような立体は，ただ一つに決まるとは限らず，与えられたシルエットの組によっては，そのような立体が全く存在しないこともある．本研究において，立体が存在するときに，目的の立体を探索する手法を提案した．

そして，volume intersection によって作られた立体が元の複数の任意のシルエットを与えたとき，それらのシルエットをもつ立体を作る問題を考える．

直すと，シルエットが 3 つ与えられたときに，実現可能な(θ, φ, d) を見つけることである．

p(k)

S

=シルエットをもつ (θ, φ, d) を実現可能なパラメタという．
これらの仮定や記号を用いて，最初に述べた問題を書き入力のシルエットを次のように表現する：[φ : S2 と S3 の第 1 軸のなす角,d : S3 の第 1 軸方向の移動距離.

2 問題と問題設定(k)

図 1 実験で用いた入力シルエット画像．

(k)(k)[x2i−1 , x2i ],0 ≤ k ≤ ymax .

(1)

i=1

シルエットが定義される座標系を投影面座標系とよぶ．すべての基準となる座標系をワールド座標系とよぶ．

3 θ, φ を固定したときの d の範囲実現可能な (θ, φ, d) を見つけるために，実現可能となるときの，(θ, φ, d) の条件式を導出できればいい．しかし，ここでいくつか仮定をおく．シルエットに関する仮定と条件式を導出するのが困難であるため，まず，θ, φ を固定して，入力シルエットの数は 3 とし，それぞれ S1 , S2 , S3

し，実現可能となる d の範囲を求めることにする．そのアとする．投影法は垂直投影であるとする．それぞれの座ルゴリズムを示す．

標系同士の関係に関する仮定として，すべての投影面座標系の第 2 軸と，ワールド座標系の第 3 軸を一致させる．
このとき，1 つのシルエットの配置に対して，投影面座標系の第 1 軸，と第 1 軸方向の移動，の 2 つの自由度があるので，シルエット 3 つでは自由度は 6 になる．ここで，volume intersection [2] という方法により，立体を作る．
Volume intersection とは，それぞれのシルエットを投影面と垂直な方向に移動させてできる領域の積集合を計算

アルゴリズム: 固定された θ, φ に対する d の実現可能範囲を求めるアルゴリズム
入力: 2D シルエット S1 , S2 , S3 , θ, φ
出力: 立体が実現可能なときの d の範囲
手続き:

1. k = 0, . . . , ymax に対して，高さ k における実現可能となる d の範囲 D(k) を求める．
y\max

して立体をつくる方法である．Volume intersection で作

2. D =られた立体は，与えられたシルエットをもつ立体か，もし3. D を出力する．

くは，その立体に最も近い立体になることが，分かっている．実際に，volume intersection で立体を作って，元のシルエットをもつかを判定すればいいが，できる立体はシルエットの配置に依存する．しかし，volume intersectionによってできる立体の形状だけに着目すればは，先述の 6自由度ではなく，3 自由度でよいことが分かる．詳細は，論文に示されている．

θ : S1 と S2 の第 1 軸のなす角,D(k) を計算する．

k=0

計算機実験の結果を示す．入力として使用したシルエットを図 1 に，結果を図 2 に示す．

4 探索アルゴリズム(θ, φ) を固定したとき，実現可能となる d の範囲を求めることができた．これを用いて，実現可能となる d が存在するときの (θ, φ) の組を探索する．(θ, φ) における d の範囲を D(θ, φ) と表すことにする．

図 3 (a) 元のシルエット S(k) と (b) filled シルエット S 0 (k)．

図 2 θ, φ を固定したときの d の範囲 D ．

4.1 全探索
対象の空間を離散化して，それらのすべての点について，D(θ, φ) を計算するという，もっとも素朴な方法である．図 4 に全探索によって求めた実現可能な θ, φ の領域を濃色で示した．入力シルエットは，図 1 に示したものである．刻み幅は 1◦ とした．

4.2 ヒューリスティック探索
実現可能領域内部の点を，少なくとも一つ見つけることを目的として，効率的に探索する，ヒューリスティック探索を提案した．ここに，そのアルゴリズムを示す．
図 4 実現可能な θ, φ の探索．

アルゴリズム: ヒューリスティック探索
入力: 2D シルエット S1 , S2 , S3 , 初期値 (θ0 , φ0 ), 終了条件の刻み幅 hL組に対する実現可能領域になっているので，評価関数を最大化すればよいことが分かる．(θ, φ) が filled シルエット

出力: θ, φ,の組に対する実現可能領域に含まれることが，元のシル

手続き:エットに対する実現可能領域に含まれることの必要条件と1. 初期刻み幅 h = 1◦ とする．

なっており，この評価関数は，その必要条件を満たす領域

2. θnow に θ0 ， φnow に φ0 を代入する．
3. (θnow , φnow ),(θnow − h, φnow ),(θnow +h, φnow ), (θnow , φnow − h), (θnow , φnow + h)の 5 つに対して，評価関数値を計算する．

4. この中で，(θnow , φnow ) における評価関数値が最も大きいとき，h ← h2 とする．それ以外の場合は，(θnow , φnow ) を更新して，最も大きい評価関数値を返す (θ, φ) を新しい (θnow , φnow )とする．

5. h が hL より小さければ (θnow , φnow ) を出力して終了，そうでなければ ステップ 3. へ進む．

を探索するためのものであるといえる．
図 4 にヒューリスティック探索による軌跡を示す．入力シルエットは，図 1 に示したものである．ヒューリス
ティック探索の初期値として，(θ, φ) = (30i◦ , 30j ◦ )(i, j =1, . . . , 11) の 121 点を用いた．終了条件の刻み幅を 0.2◦とした．評価関数は，式 (2) を用いた．濃色の領域が実現可能領域で，淡色と濃色を合わせた領域が filled シルエットの実現可能領域である．121 点の初期値のうち，88 点が，実現可能領域に到達している．

参考文献

以下に，実験で用いた評価関数について説明する．入力[1] A. Bottino and A. Laurentini, “Introducing a new

シルエットに対して，図 3 のように，水平方向の間を埋

problem: Shape-from-silhouette when the relative

めて作ったシルエットを，filled シルエットという．filledpositions of the viewpoints is unknown.” IEEE

シルエットの組に対しては，θ, φ における実現可能な d のTrans. Pattern Analysis and Machine Intelligence,範囲の最大値 dmax と最小値 dmin が独立して求められる．

vol. 25, pp. 1484–1493, 2003.
[2] A. K. Pujari, “Volume intersection for shape from

そこで，評価関数をf (θ, φ) = dmax − dmin(2)とすると，評価関数が非負の領域が，filled シルエットのsilhouette.” Sadhana, vol. 18, pp. 325–336, 1993.