基礎論文

局所形状の類似度を用いたエネルギー最小化による三次元欠損修復
河合 紀彦*1*2∗

佐藤 智和 1∗

横矢 直和 1

3D Surface Completion by Minimizing Energy Based on Similarity of Local Shape∗∗

Norihiko Kawai*1*2 , Tomokazu Sato 1 and Naokazu Yokoya 1
Abstract – 3D mesh models generated with a range scanner or video images often haveholes due to occlusions by other objects and the object itself. This paper proposes a novel
method to ﬁll in the missing regions in incomplete models. The missing regions are ﬁlled
in by minimizing an energy function that is deﬁned based on the similarity of local shapes
between the missing region and the rest of the object. The proposed method can generatecomplex and consistent shapes in the missing region. In experiments, the eﬀectiveness ofthe proposed method is successfully demonstrated by applying it to various objects withmissing regions.

Keywords: Surface Completion, 3D Inpainting, Energy Minimization, Similarity of

Shape

1

はじめに

仮想的に観光地を体験するウォークスルーや都市計
画のための景観シミュレーションを目的とした，現実
環境に基づく仮想環境の構築が近年盛んである．このような仮想環境の構築には，CG による三次元モデルが用いられることが多いが，現状ではこれらを CADなどを用いて作成することが一般的であり，詳細な形状を再現するためには多くの人的コストが必要となる．
このため，近年，実物体を計測することで，三次元モ
デルを自動的に生成する研究が盛んに行われている．
三次元モデルを生成するための三次元計測手法として
は，レーザレンジファインダを用いる手法 [1, 2] や画
像計測による手法 [3] などが存在するが，いずれの計測手法も，センサの位置から観測できる部分形状しか得られない．従って，完全なモデルを得るためには，対象物体を複数地点から計測し，得られた部分形状を統合する必要がある．しかし，屋外環境のような様々な物体が存在する環境や複雑な構造を持つ物体を対象とした場合，各計測によって得られる部分形状にオクルージョンによる計測もれが発生するため，欠損のな
い完全なモデルを作成することは難しい．この問題に対して，計測もれによって発生する欠損領域を自動的に修復することで，完全な三次元モデルを生成する手法が提案されている．以下では，従来提案されている三次元モデルの欠損領域の修復手法を概観し，本研究の位置づけを述べる．
従来の欠損修復手法の大半は，頂点群と面により構成される三次元メッシュモデルを対象としている．これら三次元メッシュモデルに対する欠損領域修復の最も基礎的な方法として，欠損領域の境界上の頂点同士を結ぶことで欠損領域に表面形状を生成する手法が古くから用いられているが，平面的な表面形状しか生成できないため，大きな欠損領域に対する修復に用いた
場合には違和感が生じることが多い．このため，単純に頂点を結ぶのではなく，欠損領域周辺の情報を修復に利用する手法が提案されている．Castellani ら [4]は，欠損領域の境界におけるエッジを直線的に伸ばす
ことで，エッジや角を違和感なく修復できる手法を提案しているが，この手法は曲面形状には対応できない．
これに対して，微分方程式，Willmore 曲面などを用いることで滑らかな補間を行う手法 [5, 6, 7] が提案されている．これらの手法では，小さな欠損領域に対しては良好な結果を得ることができる．しかし，欠損領
域内部で複雑な形状を再現することは難しく，大きな欠損領域を修復した場合，周囲と三次元構造の性質が大きく異なる形状が生成されることが多い．
また，欠損領域周辺の情報を利用する別のアプロー
チとして，三次元空間をボクセルに分割し，符号付距
離場を用いて補間する手法 [8, 9, 10, 11, 12] が提案されている．Curless ら [8] は，各ボクセルを Unseen，*1 奈良先端科学技術大学院大学

Nearsurface，Empty の 3 種類に分類し，Unseen とEmpty の間にメッシュを張ることで欠損を修復する手*1 Nara Institute of Science and Technology法を提案している．Davis ら [9] は，欠損領域の境界*2 日本学術振興会特別研究員 DC2*2 JSPS Research Fellow

日本バーチャルリアリティ学会論文誌

Vol.15, No.1, 2010から符号付距離場のボリュームデータを拡散させるこ

領域全体から探索し，それを欠損領域にコピーする処とで，欠損領域内の符号付距離場を生成する手法を提理を，欠損領域の境界付近から逐次的に繰り返すこと案している．また，Masuda[10] は，符号付距離場にで修復を行う．このため，欠損領域周辺で周期的な構

対して逐次的に二次曲面を当てはめていくことで，滑造を持たない場合でも，データ領域全体の類似形状を

らかな面を生成する手法を提案している．これらの手利用し修復することができる．しかし，これらの手法

法では，観測の位置や数に依存する符号付距離場に結では，直前の局所形状のコピーによる修復結果を最良果が大きく影響されるため，観測位置が不均等で数もとみなし，その時点で最も類似した局所形状を用いて多くない場合には，良い結果を得ることは難しい．こ

未修復箇所を修復するため，最終的に生成される形状のような問題に対して，ベイズ推定により各ボクセル全体を評価した場合には，最適な形状が得られているの状態を推定する手法 [11] や，周辺のボクセル間の関保証がなく，欠損領域の中心付近において同一物体上係から符号付距離場を整合化する手法 [12] が提案されにない形状が現れ，違和感が生じる場合がある．

ており，これらの手法では結果が観測の位置や数に依本研究では，従来手法 [16, 17, 18] と同様にデータ存する問題は解決されている．しかし，これらの手法

領域内の類似した形状を利用し修復するアプローチをにおいても，修復に用いる情報が欠損領域の境界付近採用するが，従来の逐次的なコピーによる修復で生じに限定されているため，欠損領域内部に複雑な形状をる問題に対して，本論文では，欠損領域とデータ領域

再現することは難しい．

間の局所形状の類似度を用いて欠損領域の形状の尤も

これまでに挙げた手法に対して，用いる情報を欠損

らしさに基づくエネルギー関数を定義し，これを欠損領域周辺に限定せず，同一物体上の欠損領域以外の領領域全体に対して最小化することで欠損領域を違和感

域 (以下，データ領域) やデータベース上の対象物体以なく修復する手法を提案する．本手法では，予め欠損外の物体の表面形状も利用するの手法 [13, 14, 15, 16,領域に頂点と面から成る初期形状を与えた上で，欠損

17, 18] が提案されている．これらの手法は，欠損領域

領域の局所形状と類似した局所形状をデータ領域から周辺で複雑な形状が存在する場合でも，データ領域中

探索し，データ領域の局所形状に類似するよう欠損領の類似した形状を用いることで欠損領域内に複雑な形

域の表面形状を変形することで複雑な形状を再現する．

状を再現することができる．Kraevoy ら [13] や Pauly

また，エネルギーを欠損領域全体で最小化するよう欠ら [14] は，事前に準備した対象物体に類似した物体を損領域内の頂点の位置を並列に更新することで，欠損用い，その類似物体全体を対象物体の形状に合わせる

領域内の任意の場所における局所形状がデータ領域内

ように変形し，類似物体上における対象物体の欠損にの形状と類似するよう最適化され，違和感のない形状

あたる領域の形状を欠損領域に当てはめることで修復を生成する．

を行っている．これらの手法では，対象物体と類似し

以下，2 節では，局所形状の類似度に基づくエネルた事例物体をあらかじめモデル化した上でデータベー

ギー関数を最小化することで，欠損領域を修復する提ス化する必要があり，データベースの構築に人的コス

案手法について述べる．3 節では，様々な特徴を持つ

トがかかるという問題がある．

モデルに対して欠損修復を行い，従来手法による修復

一方，同一物体上のデータ領域の表面形状を利用することで特別なデータベースを用いることなく欠損領結果と比較することで提案手法の有効性を示す．最後に 4 節で，まとめと今後の課題について述べる．

域を修復する手法 [15, 16, 17, 18] が提案されている．
これらの手法は，欠損領域周辺の構造をモデル化する

2

エネルギー最小化による三次元欠損修復

ことで欠損領域内の形状を予測する手法 [15] と，デー提案手法の処理の流れを図 1 に示す．本研究では，

タ領域内の局所形状を修復のための事例として欠損領

まず修復対象となる欠損領域を手動で指定し，何らか域にコピーすることで修復する手法 [16, 17, 18] に分類の方法を用いて欠損領域に初期値となる頂点群とそれできる．前者の手法 [15] は，対象物体中に周期的な構

らを結ぶ面を与える．次に，各頂点に対する類似局所造が存在するという仮定の下，構成要素形状とその周形状の探索 (i)，各頂点の位置の並列的な更新 (ii)，頂期をモデル化することで，欠損領域内の形状を予測し点群の密度を考慮した頂点の追加と統合 (iii) を繰り返

頂点を与えている．この手法は，集合住宅のような周すことでエネルギーを最小化し，欠損領域の修復を行

期的な構造を持つ物体中の欠損に対しては有効である．

う．本節では，まず局所形状の類似度 SSD（Sum of

しかし，周期構造を自動的に発見することが前提となるため，欠損領域周辺で周期的な構造を持たない物体

Squared Distances）によるエネルギー関数を定義し，次に定義したエネルギー関数の最小化手法について述に対しては修復が難しい．後者の手法 [16, 17, 18] は，べる．最後に，エネルギー関数の最小化処理で用いる

欠損領域周辺の表面形状と類似した局所形状をデータ

粗密法について述べる．

河合・佐藤・横矢 : 局所形状の類似度を用いたエネルギー最小化による三次元欠損修復㛤ጞᑐ㇟䛸䛺䜛Ḟᦆ㡿ᇦ䛾ᣦᐃḞᦆ㡿ᇦ䛻ึᮇᙧ≧(㡬Ⅼ䛸㠃)䜢⏕ᡂ(i) 㢮ఝᒁᡤᙧ≧䛾᥈⣴総和として以下のように定義する．
pi ∈Ω wpi SSD(pi , p̂i )E=
p ∈Ω wpi

(1)i

ここで，重み wpi として，領域 Ω ∩ Ω では各点の位置が固定であるため wpi = 1 を，領域 Ω では欠損領(ii) 㡬Ⅼ䛾఩⨨䛾᭦᪂

域の境界に近いほど頂点の位置の信頼度が高くなるた
め wpi = 1/sm（m は Ω の境界の頂点から欠損領域内(iii) 㡬Ⅼ䛾㏣ຍ䛸⤫ྜ䛔䛔䛘䜶䝛䝹䜼䞊䛜཰᮰䛧䛯䛛䛿䛔⤊஢

の頂点 pi までの最小のリンク数，s は正の定数）を用いる．ただし，後述のエネルギー最小化処理により領域 Ω 内の頂点の追加と統合が行われ，各頂点の重みが変化するため，式 (1) では重みの総和による正規化を

図 1 提案手法の処理の流れ
Fig. 1 Flow diagram of the proposed method.

行っている．
局所形状の類似度 SSD
三次元モデルの生成における物体計測の条件等によḞᦆ㡿ᇦ Ω

䝕䞊䝍㡿ᇦ ΦΩ′

⠊ᅖ Ap i ⠊ᅖ Ap̂ i

pi

p̂ i

り，三次元モデル中の頂点群の密度は位置によって異なる場合が多い．このため，本研究では，欠損領域の頂点とデータ領域の面の距離を用いることで密度に依存しない類似度 SSD を定義する．具体的には，欠損領域とデータ領域の表面形状の類似度を表す SSD(pi , p̂i )を，領域 Ω 内の頂点 pi を中心とする一定球状範囲

Api 内の頂点群と領域 Φ 内の頂点 p̂i 周辺の面を位置合わせした上での頂点と面の距離の総和として以下の
図 2 三次元モデルの各領域
Fig. 2 Missing and data regions on a surface
model.

式で定義する．

  pk − Mpˆ p gi (pk ) 2i i
(2)N (Api )SSD(pi , p̂i ) =pk ∈Api2.1

局所形状の類似度 SSD に基づくエネルギー関数の定義

ただし，Mp̂i pi は，図 3 に示すように局所形状を位置合わせするための座標変換行列を表す．また，欠損領

以下では，まず欠損領域内の局所形状とデータ領域
内の局所形状の類似度を用いたエネルギー関数の定義について述べ，次に局所形状の類似度の算出方法について述べる．
局所形状の類似度を用いたエネルギー関数の定義
本研究では，図 2 に示すように，三次元モデルをユーザが指定した欠損領域 Ω を含む領域 Ω と，同一域内の頂点 pk (∈ Api ) の法線と位置合わせ済みのデー
タ領域の面の交点を Mpˆi pi gi (pk )（ただし，gi (pk ) は

pk に対応する位置合わせ前におけるデータ領域の面上の点），pi を中心とする一定半径の球状範囲 Api の内部に存在する頂点の数を N (Api ) とする．
局所形状位置合わせのための変換行列 Mpˆi pi は，頂点 pi =(xpi , ypi , zpi )，頂点 p̂i =(xp̂i , yp̂i , zp̂i ) を原点

モデル内の Ω 以外のデータ領域 Φ に分け，領域 Ω 内とする座標系をそれぞれ設定し，算出する．ここでは，の形状の尤もらしさをデータ領域 Φ 内の局所表面形

頂点 pi ，p̂i における物体の座標系での基底ベクトルを状を用いて定義する．ここでは，三次元モデル内におそれぞれ，(xpi , ypi , zpi )，(xp̂i , yp̂i , zp̂i ) とする．こいて，ある頂点を中心とする半径が一定の大きさの球

A の内部に一部でも欠損領域 Ω 内の頂点 (初期位置)が含まれる球 A の中心点の集合を Ω とする．本研究では，欠損領域の表面形状の尤もらしさに基づくエネ
ルギー E を，領域 Ω 内の頂点 pi 周辺の頂点群と点pi に対応するデータ領域 Φ 内の頂点 p̂i 周辺の表面形状との距離に基づく局所形状類似度 SSD の重み付きの時，座標変換行列 Mp̂i pi は以下の式により算出できる．

Mp̂i pi =
⎛
xpi
⎜
⎜ yp
i
⎜
⎜
zpi
⎝
0 0

0

⎞−1 ⎛
xp̂i
−xpi
⎟ ⎜
⎟
⎜
−ypi ⎟ ⎜ yp̂i⎜
−zpi ⎟
zp̂i
⎠ ⎝
1
0 0

⎞
−xp̂i
⎟
−yp̂i ⎟⎟
−zp̂i ⎟⎠
0
1
(3)

日本バーチャルリアリティ学会論文誌

䝕䞊䝍㡿ᇦ䛾㠃
఩⨨ྜ䜟䛫䛾
䛯䜑䛾⾜ิ M pˆ pi iᇶᗏ䝧䜽䝖䝹

M pˆ i pi g i (p k )

z pi

x pi

pk

Ḟᦆ㡿ᇦ䛾Ⅼ⩌のヘッセ行列 H を導出する．

g i (p k )x pˆ iy pi

Vol.15, No.1, 2010ᇶᗏ䝧䜽䝖䝹p̂ iH=z pˆ i∂ 2 z(x,y)∂x2∂ 2 z(x,y)∂y∂x∂ 2 z(x,y)∂x∂y∂ 2 z(x,y)
∂y 2

=

2a
c

c
2b

(6)

このとき，行列 H の固有ベクトルは，主成分分析に

y pˆ iより構成した座標系において，頂点 pi の曲率が最大・最小である主方向を表している．また，同座標系におp i = M pˆ i p i pˆ i

ける頂点 pi の法線ベクトル n̄i は，以下のように算出する．

図3

類似度算出における欠損領域の頂点群とデータ領域の表面の位置合わせ
Fig. 3 Alignment of vertices and surface forsimilarity measure of local shape.

n̄i = (−∂z(0, 0) ∂z(0, 0),−, 1) = (−d, −e, 1) (7)∂x∂y

これにより得られた主方向および法線方向を元の物体座標系に変換し，それぞれの単位ベクトルを基底ベク

ここで，類似度 SSD は各頂点に対する基底ベクト
ル (x, y, z) に大きく依存する．従来手法 [16, 17, 18]では，頂点の法線ベクトルを軸とし一定角度ずつ回転させた基底ベクトルを設定し，全ての回転させた表面形状に対して類似度を計算していたため，効率的でなく，類似形状の探索に多くの時間を必要とした．これに対して，本研究では，頂点 pi ，p̂i を中心とする一定
範囲 Bpi ，Bp̂i 内の頂点群に対してそれぞれ二次曲面
当てはめを行い，曲面の法線方向および曲率が最大・最小となる主方向を算出することで，最適な基底ベク
トルを一意に決定する．これにより複数の回転させた表面形状に対する不要な類似度の計算を省略し，計算コストを削減できる．以下では，基底ベクトルとなる
法線方向および曲率が最大・最小となる主方向の算出
方法について述べる．まず，頂点 pi を中心とする一
定範囲 Bpi 内の頂点群を用いて主成分分析を行い，第一・第二・第三主成分の方向が，x 軸，y 軸，z 軸，かつ pi が原点となる座標系を構成し，以下の式で表わされる二次曲面関数を当てはめる．

z(x, y) = ax2 + by 2 + cxy + dx + ey + f(4)

トル xpi , ypi , zpi として設定する．ただし，平面を対象とした場合など，得られた二次曲面の主方向が一意に決まらない場合は，各ベクトルが直交するように任意の方向を用いて xpi , ypi を設定する．
欠損修復のためのエネルギー最小化手法

2.2

本項では，Greedy Algorithm の枠組みを用いて式(1) で定義したエネルギー E を最小化する手法を述べる．類似形状の逐次的なコピーにより修復を行う従来手法 [16, 17, 18] では，欠損領域の中心付近においてデータ領域にはない形状が現れ違和感が生じる場合が多いが，これに対して本手法では欠損領域全体でエネ
ルギーを最小化することで，欠損領域内の任意の場所
における局所形状がデータ領域内の形状と類似するよ
うに全ての頂点の位置が並列に更新され，違和感のない表面形状を生成する．具体的には，全ての類似局所

pi ) を固定すると，エネルギー E を欠損
形状の組 (pi ，̂領域 Ω 内の各頂点で独立に扱えることに着目し，(i) 各頂点 pi に対する類似形状を持つ頂点 p̂i の探索(ii) 欠損領域内の各頂点 pi の位置の並列的な更新(iii) 密度を考慮した頂点の追加と統合の 3 つのプロセスをエネルギーが収束するまで繰り返すことで，表面形状全体のエネルギーを最小化する．

ただし，二次曲面関数の各パラメータ (a, b, c, d, e, f )以下，各プロセスについて詳述する．

は，以下のコスト関数 Q が最小となるよう最小二乗(i) 類似形状を持つ頂点の探索
プロセス (i) では，欠損領域内の頂点位置を全て固法を用いて決定する．

Qpi =



{z(x̄k , ȳk ) − z̄k }2(5)

pk ∈Bpi

定することで，対応する類似局所形状の位置を探索す
る．基本的には，データ領域 Φ 内の全ての頂点に対して式 (2) で SSD を算出し，以下の式を満たす頂点のなお，(x̄k , ȳk , z̄k ) は，主成分分析により構成した座標

位置 p̂i を決定することで類似局所形状の位置を更新

系における pk の座標である．次に，得られた二次曲面

する．

から，曲率が最大・最小となる主方向および法線方向を算出する．具体的には，曲率が最大・最小となる主方向を算出するために，以下に示す二次曲面関数 z(x, y)f(pi ) = p̂i = argmin(SSD(pi , p ))
p ∈Φ

(8)

ただし，データ領域 Φ の全範囲を対象に SSD を計算する処理は計算負荷が高いため，本研究では前節で述

河合・佐藤・横矢 : 局所形状の類似度を用いたエネルギー最小化による三次元欠損修復

ΦM f ( p k )p k g k (p i )㢮ఝᒁᡤᙧ≧Ω′pk

f (p k )pi

g k (p i )pi 䛾ἲ⥺
䝧䜽䝖䝹 n p఩⨨ྜ䜟䛫῭䜏䛾䝕䞊䝍㡿ᇦ䛾㠃

pi p ktpiit(p k ,pi )Ḟᦆ㡿ᇦ䛾Ⅼ⩌p0

図 4 エネルギー算出時の頂点の関係
Fig. 4 Relationship between vertices in energy calculation.

図 5 パラメータの置換
Fig. 5 Conversion of parameters.

べた当てはめた曲面から算出される最大・最小主曲率を用いて，類似していないと考えられる局所形状同士に対する類似度の算出処理を省略する．具体的には，まず各頂点において式 (6) で表されるヘッセ行列 Hて，以下のように表すことができる．

E(pi ) =
pk ∈Apiの固有値のうち，値が大きい方を最大主曲率，値が小wpk
 pi − Mf(pk )pk gk (pi ) 2
N (Api )(10)

さい方を最小主曲率として算出する．ここでは，頂点pi とそれに対応する頂点 p̂i の最大主曲率をそれぞれ
k1pi , k1p̂i ，最小主曲率をそれぞれ k2pi , k2p̂i とする．
次に，式 (9) で得られるコスト K を昇順にソートし，
データ領域中の頂点のうち上位 n%の K に対応する頂点の組に対してのみ SSD を算出することで処理の高速化を図る．

Kpi p̂i = (k1pi − k1p̂i )2 + (k2pi − k2p̂i )2(9)

なお，本研究では，一般に三次元物体上の局所形状には面対称なものが多く存在することを考慮し，面対称形状も修復に利用する．具体的には，座標変換行列

Mp̂i pi の要素である基底ベクトル xpi または ypi の符号を逆にした形状についても類似度を算出する．

この時，欠損領域全体のエネルギー E と各頂点での要素エネルギー E(pi ) の関係は，以下のように表せる．

E=

E(pi ) + C

(11)

pi ∈Ω

C は，領域 Ω ∩ Ω 内にある頂点に関するエネルギー
であり，ここでは類似局所形状の位置が固定されているため，定数として扱える．
ここで，頂点 pi に対応する全ての点 Mf(pk )pk gk (pi )(∀pk ∈ Api ) は，必ず頂点 pi の法線上に存在することから，図 5 に示すように，頂点 pi と点 Mf(pk )pk gk (pi )は，頂点 pi の単位法線ベクトル npi と，頂点 pi の法線上の任意の三次元点 p0 を用いて以下のように表せる．

(ii) 欠損領域内の各頂点の位置の並列的な更新

pi = p0 + tpi npi(12)プロセス (ii) では，類似局所形状の組を固定し，式(1) で定義したエネルギー E を最小化するように欠損

Mf(pk )pk gk (pi ) = p0 + t(pk ,pi ) npi(13)

領域内の頂点 pi の位置を並列に更新する．以下では，これらを，式 (10) に代入することにより次式が得ら

類似局所形状の組を固定した場合の頂点 pi の位置のれる．

更新方法について詳述する．類似局所形状の組を固定した場合，エネルギー E を決定する変数は欠損領域

E(pi ) =pk ∈Api内の頂点数だけ存在するが，本研究で定義したエネル
ギー E は，欠損領域内の各頂点 pi のみを含む要素エ
ネルギー E(pi ) に分解できることに着目し，各頂点を

wpk(tp − t(pk ,pi ) )2
N (Api ) i(14)

ここで，pi の更新前後において法線ベクトル npi が変化しないと仮定すれば，E(pi ) の変数は tpi の 1 パ

独立に扱うことを可能にする．図 4 に示すように，更ラメータのみとなり，加えて tpi の変化は pi 以外の点

新対象となる頂点の位置を pi とすると，点 pk (∈ Api )の要素エネルギーには影響しない．よって，このようを中心とする局所形状に対して式 (8) で求まる類似局

な仮定の下では，要素エネルギー E(pi ) を独立に最小所形状の位置は f(pk ) であり，この類似局所形状上に化することで，全体のエネルギー E を最小化できる．

おいて pi と対応する面上の点の位置は gk (pi ) とな
る．ここで，注目点 pi に関する E の要素エネルギーE(pi ) は，pi ，gk (pi )，および点 f(pk ) から点 pk への位置合わせのための座標変換行列 Mf(pk )pk を用い

すなわち，E を最小化する tpi は以下のように求めら
れる．

tpi =



pk ∈Api wpk t(pk ,pi )

pk ∈Api wpk(15)

日本バーチャルリアリティ学会論文誌

Vol.15, No.1, 2010

実験に用いたパラメータ（lave はデータ領域における面の頂点間の平均長）
Table 1 Parameters in experiments (lave indicates average length between points
in data region).
表1

ୖ㝈䛾㜈್
௨ୖ䛾㛗䛥

㡬Ⅼ䛾㏣ຍ
ୗ㝈䛾㜈್
௨ୗ䛾㛗䛥

粗密レベル
重み w における s㡬Ⅼ䛾⤫ྜ

範囲 A の半径
範囲 B の半径

図 6 頂点の追加と統合
Fig. 6 Addition and integration of vertices.

従って，式 (12)，(13)，(15) から，頂点 pi の位置は
以下のように算出できる．
pk ∈Api wpk Mf(pk )pk gk (pi )pi =p ∈Ap wpkk

探索における割合 n
領域 Ω ∩ Ω における間引く頂点の割合
上限の閾値
下限の閾値

1
2
3
2.0 (モデル (I)，(II))
3.0 (モデル (III))
9lave
7lave
5lave
12lave (モデル (I))
26lave (モデル (II))
8lave (モデル (III))
10%
8/9
4lave
1.5lave

3/4
2lave
0.8lave0
1.3lave
0.4lave(16)i

ただし，実際には各頂点位置の更新によって，法線ベ
クトル npi および Mf(pk )pk gk (pi ) の位置が変化する
ため，式 (16) で得られる値は近似解となる．しかし，エネルギーが収束するに従って，法線ベクトルの変化が小さくなるため，エネルギーが収束するにつれて良い近似解となる．

(iii) 密度を考慮した頂点の追加と統合

では細かい形状まで再現する．また，領域 Ω 内の残りの領域 Ω ∩ Ω では，形状が既に与えられているため頂点の数と位置が固定されているが，初期段階ではこの領域内の頂点を一定の割合で間引いてエネルギーの算出を行う．間引かれる頂点の割合を段階的に小さくしながら最適化処理を繰り返すことで，効率的に修復処理を行う．

前述したエネルギー最小化処理により頂点の位置が3

実験

移動すると，欠損領域内の頂点群の分布に偏りが生じる．このとき，頂点の密度が必要以上に高い場合には，

本節では，まず 3 種類の欠損を持つ三次元モデルに最適化処理が非効率となり，また，点が疎な箇所では，対する提案手法と従来手法による修復結果を比較する

形状の細部を再現することができない．そこで本研究ことで，提案手法の有効性を示す．次に，提案手法にでは，反復処理の中で点群の密度を一定に保つようにおけるパラメータの結果への影響を考察する．
修復結果の比較による提案手法の評価

頂点の追加と統合を行う．具体的には，図 6 に示すよ

3.1

うに，頂点間の線分の長さに関して上限と下限の閾値

本実験では，図 7，8，10(a) に示す 3 種類の三次元を設ける．上限の閾値以上の長さの線分に対しては中モデル (I)，(II)，(III) に対して修復実験を行う．ここ

間に頂点を追加し，それに応じて面を分割する．下限

では，提案手法と同様に欠損領域に予め初期形状を与の閾値以下の長さの線分に対しては，線分の両端の頂えた上で，逐次的なコピーにより修復を行う従来手法

点をそれらの中間位置に統合し，それに応じて面を削[18] を実装し，従来手法と提案手法による修復結果 (各除する．

図の (c) と (d) にモデル全体図及び部分拡大図) を比

2.3 粗密法による反復処理
本研究では前項で述べた最適化の繰り返し処理において，SSD の算出に用いる局所形状の範囲および，領較することで，提案手法の有効性を示す．なお，(I)，(II) は故意に欠損領域を与えたモデルであり，(III) は
実際に建物を計測した際のオクルージョンにより欠損

域 Ω 内のエネルギーの算出に用いる頂点数をエネルが生じたモデルである．

ギーが収束するごとに段階的に変化させる粗密法によ各モデルの修復実験には PC(CPU:Xeon 3.0GHz メ

り，処理コストの低減と局所解の回避を図る．具体的

モリ:8GB) を用いた．提案手法による修復では，3 段には，SSD の算出に用いる局所形状の範囲 Ap の半径階の粗密法により修復処理を行い，修復に用いるパラを段階的に小さくする．また，領域 Ω 内のエネルギーメータは，経験的に表 1 に示すように設定した．また，計算に用いる頂点数を段階的に増やす．ここでは，領頂点群の初期値として，各図 (b) に示すように，欠損域 Ω 内の欠損領域 Ω においては，前節で述べた頂点

領域境界の頂点群の重心位置に頂点を配置し，境界の群の追加と削除の閾値を段階的に小さくすることで，頂点群と重心点を結ぶよう面を構成したものを用いた．

欠損領域内の頂点の密度を段階的に上げる．これによ従来手法 [18] による修復では，欠損領域の初期形状とり，初期段階ではおおまかな形状を生成し，最終段階

して滑らかな表面形状を与えることが前提となってい河合・佐藤・横矢 : 局所形状の類似度を用いたエネルギー最小化による三次元欠損修復(a) 欠損領域を持つ三次元モデル(b) 提案手法に与えられた
初期モデル

(前)

(後)

(a) 欠損領域を持つ三次元モデル(c) 従来手法により修復したモデル (半径 7lave )(d) 提案手法により修復したモデル(b) 提案手法に与えられた初
期モデル

図7

モデル (I) に対する欠損修復（欠損を持つモデル (a) の頂点数 3404，修復後 (d) の欠損領域内の頂点数 1579，処理時間 234 秒）
Fig. 7 Surface completion for Model (I).

る．このため本実験では，従来手法にとって適切な初期形状を与えるために，モデル (I)，(II) では欠損を与える前の元の表面形状を平滑化したものを，モデル(III) では元の形状が存在しないため，提案手法により修復した形状を平滑化したものを初期形状とした．
また，従来手法のパラメータである類似度評価に用い(c) 従来手法により修復したモデル (半径 5lave )る局所形状の範囲 A の半径を 9lave から 5lave の間で

1lave ずつ変化させながら修復を行い，最も違和感の小さい修復結果を各図 (c) 示した．以下，各三次元モデルの修復結果について考察する．
モデル (I)(図 7(a)) は，欠損領域の周辺に滑らかな曲面形状が存在する比較的単純な形状のモデルである．
図 7(c) より，従来手法による修復モデルでは，欠損領域の中心付近で隆起したエッジが歪み，データ領域に(d) 提案手法により修復したモデル

ないエッジが現れているため違和感が生じていることが分かる．これに対して，図 7(b) に示すモデルを初期値として，提案手法による最適化を行ったモデル (図7(d)) では，欠損領域に滑らかな曲面形状が生成され，また，境界部分の隆起している箇所が，欠損領域内で連続的に接続されることで，違和感のないモデルが生成されている．
モデル (II)(図 8(a)) は，欠損領域の周辺で起伏のあ

図8モデル (II) に対する欠損修復（欠損を持つモデル (a) の頂点数 17522，修復後 (d) の欠損領域内の頂点数 1505，処理時間 1682
秒）
Fig. 8 Surface completion for Model (II) .

日本バーチャルリアリティ学会論文誌(a) 2 回の反復処理後

Vol.15, No.1, 2010(b) 12 回の反復処理後(a) 欠損領域を持つ三次元モデル(c) 22 回 (2 段階目で 2 回)の反復処理後(b) 提案手法に与えられた
初期モデル(d) 26 回 (3 段階目で 2 回)の反復処理後

図 9 モデル (II) の反復処理による形状の変化
Fig. 9 Changes in shape with iterations for
Model (II).

る表面形状と，窪んだエッジが存在する比較的複雑な(c) 従来手法により修復したモデル (半径 6lave )モデル (Stanford Bunny) である．図 8(c) に示す従来手法による修復モデルでは，欠損領域の中心付近でエッジがつながっているものの，データ領域には存在
しない滑らかでないエッジが現れ違和感のある形状が生成されている．これに対して，初期形状 (図 8(b)) から提案手法により生成したモデル (図 8(d)) では，起伏のある表面形状が再現されており，また，Bunny の
後ろ側の足と同様の滑らかなエッジも再現されている
ため，全体に違和感の小さいモデルが生成されている．
図 9 に反復処理による形状の変化を示す．同図から，(d) 提案手法により修復したモデル

反復回数に応じて形状が徐々に修復されていることが分かる．また，図 9(c)(d) から，徐々に頂点群の密度を増やしながら反復処理を行うことによって，最終的には窪んだ形状が細部まで再現されていることが分かる．
モデル (III)(図 10(a)) は，現実の屋外環境を計測し

図 10

モデル (III) に対する欠損修復（データ領域の頂点数 12749，修復後の欠損領域の頂点数 474，処理時間 1688 秒）
Fig. 10 Surface completion for Model (III) .

窓および地面が欠損したモデルである．逐次的なコピーにより修復したモデル (図 10(c)) では，窓の付近に違和感のある形状が生じているのに対し，初期形
状 (図 10(b)) から提案手法により生成したモデル (図10(d)) では，壁・地面・窓枠とも違和感なく修復されている．
図 11 に各モデルの反復処理におけるエネルギーの変化を示す．ただし，図中のエネルギーは初期モデルのエネルギーを 1 として正規化している．図から，どのモデルにおいても，初期モデルから反復処理を行うことによって，エネルギーが徐々に減少していることが確認できる．ただし，粗密法において全体の頂点のṇつ໬䛧䛯䜶䝛䝹䜼䞊た際に，街灯によるオクルージョンにより建物の壁と䝰䝕䝹(I)
䝰䝕䝹(II)
䝰䝕䝹(III)

1

0.1

0.01

0

5

10

15

20

25
⧞䜚㏉䛧ᅇᩘ

図 11 各モデルのエネルギーの変化
Fig. 11 Changes in energy with respect to iterations for each model.

河合・佐藤・横矢 : 局所形状の類似度を用いたエネルギー最小化による三次元欠損修復

s = 1.1

図 12

s = 1.5

1.1
467
1891

1.5
303
1307

2.0
234
1682

3.0
215
1237

的形状が単純なモデル (I) では重みの変化による修復
結果への影響は小さかったが，モデル (II) においては修復結果への大きな影響が見られた．具体的には，sが小さすぎる場合 (s ≤ 1.5)，窪んだエッジがつながら処理時間 (秒)ss = 5.0

重み w の s を変化させた時の修復結果 (上段：モデル (I)，下段：モデル (II))
Fig. 12 Results with diﬀerent values of parameter s.

表 2 重み w の s を変化させた時の処理時間
Table 2 Processing time with diﬀerent valuesof parameter s for each model.

モデル (I)
モデル (II)s = 3.0

5.0
174
958

ず，欠損領域内の表面形状が全体的に滑らかになる傾向が見られた．一方，s が大きすぎる場合 (s ≥ 3.0)，
窪んだエッジがつながり，起伏のある表面形状が生成されているが，欠損領域の中心付近でデータ領域に存密度および類似度 SSD の算出における範囲 A が変化した時点 (モデル (I) では 18 回目，26 回目，モデル

在しない違和感のある形状が生成されやすいことが確認できた．
これらの結果から，重み w 中の s を大きくするこ(II) では，20 回目，24 回目，モデル (III) では，8 回目，
12 回目) においてはエネルギーが不連続に変化する．

とでエネルギーの収束を早め効率的に修復できること

パラメータの結果に対する影響の考察が考えられるが，修復結果に関しては，現状において提案手法では，表 1 に示すような複数のパラメータ

最適なパラメータを自動で決定することは難しく，試を決定する必要があるが，本項では特に結果への影響

行錯誤による調整が必要である．このため，今後，効が大きい，エネルギー関数 (式 (1)) における重み w 中

率的かつ違和感のない修復を実現するためには，欠損

3.2の s の変化による処理時間および修復結果を考察する．
表 2 と図 12 に，3.1 節で示した実験に対して s を変化させた場合のモデル (I)，(II) の処理時間と修復結果を示す．
まず処理時間に関して表 2 から，s が大きくなる，

領域周辺の形状の特徴や修復過程における形状の変化を分析することにより重みのパラメータを適応的に決定する手法を確立する必要がある．

4

まとめ

すなわち欠損領域の境界からのリンク数に基づく頂点

本論文では，三次元表面形状モデルにおける欠損領間の重みの変化率が大きくなるに従って，処理時間が域の尤もらしさに基づくエネルギー関数を，局所表面短くなる傾向が見られた．これは，重みの変化率が大形状の類似度 SSD を用いて定義し，これを最小化す

きいほど，頂点位置の更新の際に欠損領域の境界に近ることで，三次元モデルにおける欠損領域を修復する

い頂点が欠損領域のより内部にある頂点に及ぼす影響

手法を提案した．実験では，滑らかな曲面形状を持つが大きくなるため，一度の反復処理で欠損領域内部の単純な形状のモデル，起伏のある複雑な形状のモデル,

形状が大きく変化し，結果的に反復回数が減少するこ

実際の屋外環境を計測したモデルに対して違和感なとによる．

い修復が実現できること示した．しかし，修復結果が次に修復結果に関して，図 12 に示すように，比較

パラメータに大きく依存することも確認した．今後，

日本バーチャルリアリティ学会論文誌

様々な特徴を持つ三次元モデルに対して違和感のない修復を実現するためには，三次元モデルの特徴や修復過程における形状の変化から最適なパラメータを自動的に決定する手法を確立する必要がある．また，形状とテクスチャの同時修復を実現する手法を開発する．
謝辞
本研究の一部は科学研究費補助金 (基盤研究 (A)，No.19200016，若手研究 (B)，No.20700162，および，特別研究員奨励費，No.8045) による．

参考文献
[1] C. Früh, A. Zakhor: “An automated method forlarge-scale, ground-based city model acquisition”,
Int. Jour. of Computer Vision, vol.60, pp. 5–24,
2004.
[2] 浅井俊弘, 神原誠之, 横矢直和: “全方位距離画像と全方位カラー画像の統合による屋外環境の三次元モデル化”, 画像電子学会誌, vol.34, no.5, pp. 529–538,
2005.
[3] T. Sato, M. Kanbara, N. Yokoya and H. Takemura:“Dense 3-D reconstruction of an outdoor scene by
hundreds-baseline stereo using a hand-held video
camera,” Int. Jour. of Computer Vision, vol.47,
no.1-3 pp. 119–129, 2002.
[4] U. Castellani, S. Livatino and R.B. Fisher: “Improving environment modelling by edge occlusion surface completion,” Proc. Int. Symp. on 3D
Data Processing, Visualization and Transmission,
pp. 672–675, 2002.
[5] J. Verdera, V. Caselles, M. Bertalmio and G.
Sapiro: “Inpainting surface holes,” Proc. Int.
Conf. on Image Processing, vol.2, pp. 903–906,
2003.
[6] J. Wang and M.M. Oliveira: “A hole-ﬁlling strategy for reconstruction of smooth surfaces in range
images,” Proc. SIBGRAPI03, pp. 11–18, 2003.
[7] H. Xie, K.T. McDonnell and H. Qin: “A ﬁnite element method for surface restoration with smoothboundary conditions,” Computer Aided Geometric
Design Archive, vol.21, no.5, pp. 427–445, 2004.
[8] B. Curless and M. Levoy: “A volumetric method
for building complex models from range images,”
Proc. ACM SIGGRAPH96, pp. 303–312, 1996.
[9] J. Davis, S.R. Marschner, M. Garr and M. Levoy:“Filling holes in complex surfaces using volumetricdiﬀusion,” Proc. Int. Symp. on 3D Data Processing, Visualization and Transmission, pp. 428–438,
2002.
[10] T. Masuda: “Filling the signed distance ﬁeld byﬁtting local quadrics,” Proc. Int. Symp. on 3D
Data Processing, Visualization and Transmission,
pp. 1003–1010, 2004.
[11] 板野友哉, 森栄晃彦, 古川亮, 川崎洋: “未観測ボクセ
ルのクラス推定を用いた形状の統合及び補間手法とGPU を用いた高速な実装”, 画像の認識・理解シンポ
ジウム講演論文集, pp. 365–371, 2007.
[12] R. Sagawa and K. Ikeuchi: “Hole ﬁlling of a 3Dmodel by ﬂipping signs of a signed distance ﬁeld
in adaptive resolution,” IEEE Trans. on PatternAnalysis and Machine Intelligence, vol.30, no.4,
pp. 686–699, 2008.

Vol.15, No.1, 2010[13] V. Kraevoy and A. Sheﬀer: “Template-based meshcompletion,” Proc. Eurographics Symp. on Geometry Processing, pp. 13–22, 2005.
[14] M. Pauly: “Example-based 3D scan completion,”
Proc. Eurographics Symp. on Geometry Processing, pp. 23–32, 2005.
[15] M. Pauly, N.J. Mitra, J. Wallner, H. Pottmann
and L.J. Guibas: “Discovering structural regularity in 3D Geometry,” Proc. ACM SIGGRAPH2008, vol.27, no. 3, #43, pp. 1–11, 2008.
[16] S. Park, X. Guo, H. Shin and H. Qin: “Surface
completion for shape and appearance,” Int. J. of
Computer Graphics, vol.22, pp. 168–180, 2006.
[17] A. Sharf, M. Alexa and D. Cohen-Or: “Contextbased surface completion,” Proc. ACM SIGGRAPH2004, pp. 878–887, 2004.
[18] T.P. Breckon and R.B. Fisher: “Non-parametric
3D Surface Completion,” Proc. Int. Conf. on 3-D
Digital Imaging and Modeling, pp. 573–580, 2005.
(2009 年 9 月 18 日受付)

［著 者 紹 介］
河合 紀彦
2005 年京大・工・情報卒．2007 年奈
良先端科学技術大学院大学情報科学研究科博士前期課程修了．現在，同大博士後期課程に在学中．2009 年日本学術振興会
特別研究員 (DC2)．2009 年電子情報通信学会学術奨励賞受賞．電子情報通信学会，情報処理学会，IEEE 各会員．

佐藤 智和 （正会員）
1999 年阪府大・工・情報工卒．2003 年
奈良先端科学技術大学院大学情報科学研
究科博士後期課程修了．現在，同大情報科学研究科助教．コンピュータビジョンの研究に従事．2001 年電子情報通信学会
学術奨励賞受賞．博士 (工学)．電子情報通信学会，情報処理学会，IEEE 各会員．

横矢 直和 （正会員）
1974 年阪大・基礎工・情報工卒．1979
年同大大学院博士後期課程修了．同年電子技術総合技術研究所入所．以来，画像処
理ソフトウェア，画像データベース，コン
ピュータビジョンの研究に従事．1986〜
87 年マッギル大・知能機械研究センター
客員教授．1992 年奈良先端科学技術大
学院大学・情報科学センター教授．現在，
同大情報科学研究科教授．1990 年，2007
年情報処理学会論文賞受賞．2005 年情報処理学会フェロー，電子情報通信学会
フェロー，工博．電子情報通信学会，情報処理学会，人工知能学会，日本認知科学会，映像情報メディア学会，IEEE，ACM
SIGGRAPH 各会員．