DEIM Forum 2014 F5-1

アセンブリ構造を持つ 3 次元モデルの投影データを用いた探索方法碓井 義彬†

飛田 雄樹†

王

天宇†

片山

薫†

† 首都大学東京大学院システムデザイン研究科 情報通信システム学域
E-mail: †{usui-yoshiaki,hida-yuki}@sd.tmu.ac.jp, ††wang-tianyu@ed.tmu.ac.jp, †††kaoru@tmu.ac.jp
あらまし

材質の違いや，部品の組み合わせ等のアセンブリ構造を考慮した 3 次元モデルの探索方法の提案とその評価について述べる．アセンブリ構造を特徴量として反映させるために 3 次元モデルに対し様々な角度から投影データを求める．外見が同じモデルでも中身が異なる場合は投影データは異なる結果となるため，それを特徴量としてマッ
チングを行うことを提案する．様々な角度らの投影データを用いることで物体が回転していてもマッチングが行える．
また平行移動に対してはフーリエ変換を施し，探索を可能にした．この特徴量を入力として主に相互部分空間法を用
いて 3 次元モデルのマッチングを行なった．提案手法の有効性は公開データセットによる識別実験によって検証する．
キーワード

アセンブリ構造，3 次元モデル，投影データ

1. は じ め に
本稿では，材質の違いや，部品の組み合わせ等のアセンブリ構造も考慮した 3 次元モデルのマッチング方法を提案する．近させるための特徴空間に射影してから相互部分空間法を行う手法である．また直交相互部分空間法は直交行列を用いて明示的に各クラスの部分空間の関係を直交化したうえで，相互部分空間法を適用する手法である．

年 3 次元のモデリングやデジタル化の技術が向上し，3 次元モ

坂野ら [3] は物体認識のために核非線形相互部分空間法によデルの作成は容易になってきている．また 3D プリンターも発るマッチング法を提案した．彼らも多視点の画像を特徴量とし展しており，3 次元 CAD データは増大している．さらにインたが，多視点の画像を用いることによりパターン分布が非線形

ターネットの普及により世界中からデータをダウンロードする的な分布になってしまう．そこで Scholkopf が提案した非線形ことが可能となっている．そのため効率的な 3 次元モデルの主成分分析を相互部分空間法に応用し，認識率を向上させた．

データの検索，マッチング技術が必要とされている．

呉ら [2] も多視点画像に対し核非線形相互部分空間法を用い

現在の 3 次元モデルのマッチングや検索方法はの多くはサーた．彼らの手法はまず非線形的な広がりを持つ対象パターン分

フィスデータを対象としている．しかしながら工業機械などは布をユークリッド距離に基づき複数のクラスタに分割し，各ク

材質も異なる複数の部品の組み合わせによりできている．外見

ラスタをそれぞれ線形部分空間で近似する．各クラスタに対しから得られる情報だけの検索方法ではこのような組み合わせ等

PCA を適用して得られた局所部分空間集合から類似度を求めの構造を考慮した検索は難しい．そこで本論文は材質の違いや，た．またパターン分布を分割する分割数と各局所部分空間の次部品の組み合わせなどのアセンブリ構造も考慮した 3 次元モデ

元，クラスタリングの初期値などのパラメータの決定のためにルのマッチング方法の開発を目標として，アセンブリ構造を反アンサンブル学習を用いることで性能向上を図った．

映するために様々な角度からの投影データを 3 次元モデルの特鈴木 [6] はボリュームデータを解析することで 3 次元モデル

徴量とすることを提案する． また相互部分空間法や核非線形相のマッチングに応用した．彼は解析のために 3 次元ボリューム

互部分空間法を用いて実験し，評価した．

データから直接形状特徴を抽出することを提案した．具体的に

2. 関 連 研 究

は 2 次元画像解析 (テクスチャー解析) に有効な手法とされている Laws マスクを 3 次元に応用した．

3 次元モデルのマッチング方法は数多く提案されている．

Yue ら [7] は多視点の画像のセットをもとに重み付き 2 部グ

Ding-YunChen ら [1] は正十二面体の頂点から 20 枚のシルエッ

ラフのマッチングを用いて 3 次元モデルの検索を行った．画像

ト画像のセットを求め，この画像を Light field descriptor と呼一枚一枚に初期値の重みを設定し，その後重みを更新する．最んだ．またこの 20 枚の取り方を様々な角度から行い，これに大重み付き 2 部グラフマッチングアルゴリズムを適用すること

より 3 次元モデルが回転していてもマッチングを可能にした．

で類似度を測定した．

またか彼らは 3 次元モデルが拡大，縮小していてもマッチング
できる手法を提案した．
新垣ら [4] は 3 次元物体のマッチングに対し，多視点から撮

3. 準

備

3. 1 投影データ

影した画像を用いた．さらにこの画像に HLAC や輪郭線特徴

本研究では 3 次元モデルに対し，アセンブリ構造を特徴抽出などを抽出し，手法ごとに精度を比較した．彼らはマッチングするために投影データを計算した．投影データとは，ボリューのために制約相互部分空間法や相互部分空間法などを用いた．

ムデータの場合ある方向へのボクセルの和により表される．座

制約相互部分空間法とは，制約空間と呼ばれる識別性能を向上

標 (s, t, r) は (x, y, z) を (ζ, η) だけ回転させたあとの座標であり以下のように表せる．
 s = x cos ζ cos η − y sin ζ cos η − z sin η(1)t = x sin ζ + y cos ζ r = x cos ζ cos η − y sin ζ sin η + z cos η

部分空間U
部分空間V

本研究で投影データは，回転させた 3 次元モデルを Z 軸に垂θ

直な面の和を計算することで求めた．

zr

図 2 相互部分空間法概念図

s，. . . ，i − 1)，vi ⊥vj (= 1，. . . ，i − 1) である．また，式 (3) の第ηti 番目に大きい固有値が第 i 正準角 θi に対する cos2 θi となる．

ς

2 つの部分空間の構造的な類似性を測る尺度として，第 n 正x

準角まで考慮した類似度 S [n] (n >= 1) を次のように定義する．

1∑
cos2 θin i=1n

S [n] =y
図1

(6)

本研究では第一正準角 cos2 θ1 と S [n] を用いてマッチングを

回転後の座標軸行い，両者の比較を行う．

3. 3 核非線形相互分空間法

3. 2 相互部分空間法
相互部分空間法とは，1985 年に前田らによって提案された部分空間法の拡張である．相互部分空間法では，複数の入力データが利用できる場合に適用される．入力パターンから特徴を抽出して入力部分空間を作り，それと辞書として登録された各クラスの部分空間とがなす最小角度 θ1 に基づいて識別を行う．相互部分空間法では M 次元部分空間 V と N 次元部分空間

U (M>=N) のなす最小角度の余弦を以下で定義し，これを類似度とする．

| (u，v) |2
cos2 θ1 =sup2
2
u∈U ，v∈V ，∥u∥=0| ，∥v∥=0| ∥ u ∥ ∥ v ∥非線形的なパターン分布の識別の効果的な手法として核非線形相互部分空間法 [5] が知られている．核非線形相互部分空間法は Scholkopf [8] が提案したカーネル主成分分析を相互部
分空間法へと適用したものである．特徴空間への非線形写像
を Ψ : RN → F と定義する．特徴ベクトル ⃗x を特徴空間へ写像すると Ψ(⃗x) となる．F は高次元もしくは無限次元であるため直接これらの内積を求めることは難しい．そこでカーネル
主成分分析を用いることで有限時間で計算を行えるようにした．クラス V と U の特徴空間上のベクトルを Vi (1 <
=i<
= m)，

(2)

この角度 θ1 は，以下で定義される行列 S の最大固有値とな

Uj (1 <=j<= n) とすると，それらの内積は次式で求められる
V i · Uj =

m ∑
n
∑

′

{αl }i {αl′ }j k(x⃗vl , x⃗ul′ )(7)

l=1 l′ =1

る [4]．

′

S = (sij ) (1 <=i<
= M ，1 <
=j<
= N)

(3)

ここで k(·, ·) はカーネル関数，{αl }i ，{αl′ }j は係数であり，特徴ベクトル x⃗v ，x⃗u′ から求まる．x⃗v ，x⃗u′ は V ，U の特徴ベク
l

sij =

M
∑

l

l

l

トルである．具体的にカーネル主成分分析で求められた基底同(ui ，vm )(vm ，uj )

(4)

m=1

士の角度を計算するためには，前節で引用した式 (4) に代入すればよい．

また 2 つの部分空間をなす角度である正準角を用いて相互部
分空間法を一般化する．M 次元空間 V と N 次元空間 U の間

4. 提 案 手 法には N 個の正準角が定義できる．ここで，un (1 <
= n <
= N)

多視点画像など外見の情報のみのマッチング手法では，サー，vm (1 <=m<= M ) は，それぞれ正規直交基底である．第 2 正

フィスデータの検索はできても，内部構造を持つボリューム

準角 θ2 は，第１正準角 θ1 に直交する方向において測った最小データを検索できない．外見は同じでも内部構造が異なる場合

角，第 3 正準角 θ3 は θ1 と θ2 に直交する方向で測った最小角があるためである．そこで 3 次元モデルに対し，内部構造を反である．以下同様に N 個の正準角が順次求まる．これを式で書くと次のようになる．

次元モデルの特徴量とすることを提案する．

| (ui ，vi ) |∥ ui ∥2 ∥ vi ∥2
2

cos2 θi = max

映させるために様々な角度からの投影データを求め，これを 3(5)

ここで、ui ∈ U ，vi ∈ V ，∥ ui ∥=| 0，∥ vi ∥=| 0, ui ⊥uj (= 13 次元モデルに対し，3 次元ラドン変換を用いることで投影データを求める．この複数枚の投影データを用いて相互部分空間法によりマッチングを行なう．しかし，角度により投影デー

タは大きく異なり，非線形的な分布になってしまう．そのため相互部分空間法にそのまま投影データと認識率が低くなってし(:,:,3)

まう．そこで複数の投影データを用いて核非線形相互部分空間

1

0

1

(:,:,2)0001法を用いてマッチングを行なった．また 3 次元モデルが平行移動していてもマッチングできるように投影データをフーリエ変

頂点番号

X座標

Y座標

Z座標

1

1

1

1

2

3

1

1

換したものや重心による位置合わせを用いる．

4. 1 重心による位置合わせ
本研究では 3 次元モデルが平行移動していてもマッチングできるようにするために，フーリエ変換を用いた場合と重心によ

3

3

3

1

4

1

3

1

5

1

1

3

6

3

1

3

7

3

3

3

8

1

3

3

0

01

00

(:,:,1)

0

0

0

1

0 0 1 0

0

0

0

0

1

0

1

る位置合わせを用いる２通りで実験を行なった．本節では重心による位置合わせについて述べる．投影データ一枚一枚の重心
図 4 頂点座標を 3 次元配列へ格納を求め，その重心の位置を画像の中心に合わせるように移動させる．ここで投影データの位置 (xn , yn )(1 <=n<= N ) における値を f (xn , yn ) とすると投影データの画像の重心 (xg , yg ) は，

1 ∑f (xn , yn )(xn , yn )N n=1
N(xg , yg ) =(8)と定義する．こうして求められた重心の座標 (xg , yg ) を投影
データの中心に合わせる．
内部が空のデータ

図5

ボリュームデータ

内部を埋めたボリュームデータ

4. 3 投影データを用いたマッチング方法の提案
本研究ではアセンブリ構造を考慮した 3 次元モデルのマッチ
ング方法を提案する．具体的には内部構造を反映するために 3次元モデルの投影データを求める．これを特徴量として核非線形相互部分空間法によりマッチングを行う．マッチングは学
習フェーズと分類フェーズからなる．学習フェーズについて述べる．
図 3 重心による位置合わせをした画像

4. 2 サーフィスデータからボリュームデータへの変換
本研究では内部構造の違いも考慮したマッチングを行えることを確かめるためにボリュームデータを実験に用いる．しかし比較実験に適した内部構造の異なる 3 次元モデルのデータが手に入らなかったため，今回は既存のサーフィスデータを加工することで実験用データを作成した．サーフィスデータは McGill

3D Shape Benchmark [9] の公開データセットを用いた．これ
らのデータは.ply 形式のファイルであり，.ply 形式のファイル
は 3 次元モデルの頂点座標を格納している．このサーフィス
データをボリュームデータに変換するためにまず，頂点座標に対応する番地の 3 次元配列に重みとしてボクセルの値 1 を格納する (図 4)．このままでは内部は空の状態なので空の部分にも同じく値 1 を与えることでボリュームデータとする (図 5)．また部分的に内部の重みの値を 1 以外に変更することで内部構造の違いとした．今回の実験では重み (ボクセルの値) を 20 ∼ 45に変更したモデルを作成した．

4. 3. 1 学習フェーズ
具体的にはまず辞書側となる 3 次元モデルに対し，3 次元ラ◦◦ドン変換により投影データを η が 0◦ <=ζ<= 170 の範囲で 10◦◦ずつ (ζ = 10, 20, . . . , 170)， η を 0◦ <=η<= 350 の範囲で 10ずつ (ζ = 10, 20, . . . , 350) の合計 648 枚求める．投影データは複数の画像の集まりである．次に 3 次元モデルが平行移動していてもマッチングできるようにフーリエ変換もしくは重心による位置合わせをおこなう．次に相互部分空間法を用いてマッチングするために投影データから辞書側の部分空間を構成する．
投影データの画像一枚一枚 (150 × 150) をベクトル化し，要素が 22500 のベクトルとする．画像のベクトル化の詳細は図 6 に示す．
このベクトル vi (1 <= M ) からカーネル関数を用いて行列
=i<
v
Kij
= k(⃗
vi , v⃗j ) を作り，固有ベクトル αv を求める．この固有ベクトルを固有値の昇順にソートし，正規化する．相互部分空間法の場合はベクトル化したあとベクトルを並べた行列を固有値分解することで固有値と固有ベクトルを求める．固有値の大きい順に固有ベクトルをソートし，これから部分空間 V を構成する．ここで M はクエリの投影データの入力枚数である．

4. 3. 2 分類フェーズ
学習フェーズと同様にクエリ側のクラス µ の 3 次元モデルの投影データをそれぞれ作成する．投影データから基底ベクト

< <
ル uµ
j (1 = j = N ) を作り，これからカーネル関数を用いて行
列 K u を作り，固有ベクトル αu を求める．この固有ベクトルを固有値の昇順にソートし，正規化する．学習フェーズで求め

1
2

た固有ベクトル αv と入力データをベクトル化した vi を式 (7)に代入することで式 (4) の行列 S を作る．但し本研究ではすべての固有ベクトルを利用するのではなく，辞書側，入力側から

3

それぞれ設定した本数のベクトルを用いた．この行列の最大固有値から cos2 θ1 と S [n] を求め，この値の最も高いクラスにク

1

2

3

4

4

5

6

5

7

8

9

6

エリを分類する．
相互部分空間法の場合は学習フェーズと同様に基底ベクトルを並べて行列を作り，固有値分解して求めた固有値の順に固有7うベクトルをソートし，正規化する．学習フェーズで求めた固8有ベクトルと分類フェーズで求めた固有ベクトルを式 (7) にす

9

ればよい．

Algorithm 2 核非線相互部分空間を用いた分類フェーズ
図 6 画像のベクトル化

′

′
′
µ
Input 入力側のクラス µ (1 <=µ <= Q) の 3 次元モデル U (m × m ×m)，使用する投影データの枚数 R，学習フェーズで求めた αµ 及び，vectorV µ (1 <=µ<= P )，入力側の次元数 ri ，辞書側の次元数 rd′

Output 辞書側のクラス µ と入力側のクラス ν との cos2 θ による類似度，S [rd ] による類似度′

for µ = 1 to Q do′′

projection V µ ← radontransform(U µ )′′F[U µ ] ← F F T (projection U µ )′′vectorU µ ← vectorization(F[U µ ])′x⃗i , x⃗j ∈ vectorU µ (1 <= i, j <= R)′(R × R)matrixK µ (i, j) ← k(x⃗i , x⃗j ) (k is kernel f unction)′′′

eigen vectorαµ , eigen valueλµ ← eig(K µ (i, j))
′

′

′

′

′

′

′

µ
< µ <
< µ
λµ
1 = λ2 = . . . = λR ← sort(eigen valueλ )′µInput 辞書側のクラス µ(1 <=µ<= P ) の 3 次元モデル V (m×m×m)，

µ
< µ <
< µ
αµ
1 = α2 = . . . = αR ← sort(eigen vectorα )end for

使用する投影データの枚数 R

for µ = 1 to P do

Algorithm 1 核非線相互部分空間を用いた学習フェーズ

Output 辞書側の関数空間上の固有ベクトル αµ′

for µ = 1 to Q do′′x⃗i ∈ vectorV µ , x⃗j ∈ vectorU µ

for µ = 1 to P do′

projection V µ ← radontransform(V µ )matrixK(i, j) ← k(x⃗i , x⃗j ) (k is kernel f unction)

F[V µ ] ← F F T (projection V µ )for l = 1 to rd do

vectorV µ ← vectorization(F[V µ ])′x⃗i , x⃗j ∈ vectorU µ (1 <= i, j <= R)(m × m)matrixK µ (i, j) ← k(x⃗i , x⃗j )(k is kernel f unction)
eigen vectorαµ , eigen valueλµ ← eig(K µ (i, j))
µ
µ
µ
λµ <
=λ <
= ... <= λ ← sort(eingen valueλ )
1
2
R
µ
µ
< αµ <
<
αµ
.
.
.
α
=
=
=
1
2
R ← sort(eingen vectorα )end forreturn αµ′

for l = 1 to ri do∑ri µ µ′′S(i, j) ←K(l, l )′ αl αi

end forend forcos2 θ ← M AX(eigen value(S))
S [rd ] ← AV ERAGE(eigen value(S))
end forend for′return クラス µ と µ との cos2 θ, S [rd ]5. 投影データを用いた 3 次元モデルの識別実験
投影データを用いることの有効性を相互部分空間法及び核非表1
入力側データ

実験データ一覧
投影データ

human

辞書側データ
辞書側データラドン変換+フーリエ変換
ラドン変換 フーリエ変換

入力側基底ベクトル

辞書側基底ベクトル

基底ベクトルからカーネル関数
を用いて行列Kを作成
を用いて行列 を作成
入力側行列K
入力側行列

辞書側行列K
辞書側行列

固有ベクトルを求める
入力側固有ベクトル
入力側基底ベクトル

辞書側固有ベクトル
入力側基底ベクトル

重み (ボクセルの値) はすべて 1
表2

行列S
行列
Sの固有値
の固有値を求めるの固有値を求める実験データ一覧
投影データ

spider

類似度

図7

処理手順

線形相互部分空間法による類似度によって評価する．なお，実験は MATLAB2012 を Xenon E31245 3.3GHz，メインメモリ

16Gb のマシン上で行った．また実験データのサーフィスデー

重み (ボクセルの値) はすべて 1

タは McGill 3D Shape Benchmark [9] の公開データセットを用いた．これに前章の変換を施してボリュームデータとした．

表3

実験データ一覧
投影データ

table1-1

5. 1 実 験 条 件
マッチングのサンプルとしては前章で述べたボリュームデー
タを用いた．この中からクエリの部分空間を構成するための入力枚数 R を 50 ∼ 200 で変化させ類似度の推移を調べた．デー
タベースの 3 次元モデルには(1) 同一のモデル(2) 回転移動させたモデル

重み (ボクセルの値) はすべて 1(3) 平行移動させたモデル(4) 回転及び平行移動させたモデル

表4(5) ボリュームデータの内部の値 (重み) を変えたモデル

table1-2

実験データ一覧
投影データの 5 種類を用いた．
核非線形相互部分空間を用いる際，辞書側部分空間の次元数

rd ，入力側部分空間次元数 ri ，使用する正準角の数 nc a，そしてスケールパラメーター s の 4 つがある．今回の実験では正準角の数は式 (4) の行列の行数，つまり辞書側部分空間の次元数

rd と等しくした．rd = 6，ri = 5 として今回は主に実験を行った．またカーネル関数としてはガウス型 RBF

k(⃗x, ⃗y ) = exp(−∥⃗x − ⃗
y ∥2
)
2
2σ

テーブルの脚 3 本の重みが 20(9)を用いた．スケールパラメーターは σ の値を決定するのに用い

5. 2 実 験 結 果
まず異なる複数のモデルに対し核非線形相互部分空間法(KMSM) 及び相互部分空間法 (MSM) を用いた結果を示す.

る．具体的には投影データから得られるベクトルを平均を計算

5. 2. 1 形状の異なる重みなしのモデル

しこれにスケールパラメーター s を乗じたものを σ とした．

まずどのモデルも重みは加えていないものとの類似度の結果

また精度の比較のために相互部分空間法を用いて同様の実験を示す．ここで table1-1-rot とは table1-1 を θ，ϕ ともに 5◦ だも行なった．相互部分空間法の場合は比較するモデルそれぞれ

け回転させたものである．これは投影データを 10◦ ずつとるたの投影データから求めたベクトルを並べて行列を作る．その行

め，最大誤差である 5◦ に設定した．実験の結果の数値は空間列の固有ベクトルを式 (4) に代入することで類似度を求めた．

同士の角度 θ を用いて表される cos2 θ1 の値及び，S [n] である．

表5

実験データ一覧

表9

実験データ一覧
投影データ

table2-1
投影データ

table1-3

重み (ボクセルの値) はすべて 1テーブルの脚 3 本の重みが 20 ただし配置が table1-2 と一箇所異なる
表 10 実験データ一覧
表6

投影データ

table2-2

実験データ一覧
投影データ

table1-4

テーブルの脚 2 本の重みが 20
テーブルの脚 5 本の重みが 25 ∼ 45
表 11
表7

実験データ一覧
投影データ

table1-5

テーブルの脚 5 本の重みが 20 ∼ 40 ただし配置は table1-4 と同じ
表8

cos2 θ1 (MSM) S [n](MSM)

spider,human

0.97460.1196

spider,table1-1

0.94620.1773

spider,table2-1

0.95060.1484

spider,table1-1-rot

0.94510.1582

human,table1-1

0.924

0.1651

human,table2-1

0.93110.1524

human,table1-1-rot

0.92040.1719table1-1,table2-1

0.94170.2848table1-1,table1-1-rot

0.9871

0.3925table2-1,table1-1-rot

0.93810.2642

実験データ一覧
表 12table1-6

異なる形状のモデルの類似度 (R=50，フーリエ変換)

モデル名

投影データ

テーブルの脚 5 本の重みが 25 ∼ 45 ただし配置は table1-4 と異なる

異なる形状のモデルの類似度 (R=50，フーリエ変換)

モデル名

cos2 θ1 (KMSM) S [n](KMSM)

spider,human

0.81760.2505

spider,table1-1

0.36980.0624

spider,table2-1

0.66820.1584

spider,table1-1-rot

0.35030.0591

human,table1-1

0.37470.068

human,table2-1

0.62960.139

human,table1-1-rot

0.3566

0.0649table1-1,table2-1

0.00005

0.00001

table1-1,table1-1-rot

0.94920.5905table2-1,table1-1-rot

0.00006

0.00001

今回辞書側部分空間の次元数 rd と等しい n = 6 とした．類似
度は cos2 θ1 ，S [n] ともに最大 1 である．
表 12 の table1-1 と table1-1-rot より回転していても同一の物体の類似度が最も高くなっていることが分かる．また R = 50を例に取ると MSM では table1-1 と table1-1-rot との類似度が0.9871 で，次に高い類似度は spider と human の 0.9746 と差があまりない．これに対し KMSM では table1-1 と table1-1rotとの類似度は 0.9492 で次に高い spiderto human との類似度は0.8176 となり差が大きく表される．類似の値の差から MSM に比べ KMSM のほうが識別性能が高いことが確認できる．

5. 2. 2 回転における類似度の差
次に回転の差がどれほど類似度の差として現れるか評価した．
同一の物体に対して投影を撮り始める角度を 1◦ ずつ変えた場

合の結果を示す．実験は table1-2 を用いて行った．

表 15

重みを加味したモデルとの類似度 (R=50，重心による位置合
わせ)

表 13
モデル名

同一物体の角度の違いによる類似度の推移 (R=50)

モデル名

cos2 θ1 (MSM) S [n](MSM) cos2 θ1 (KMSM) S [n](KMSM)

cos2 θ1 (KMSM) S [n](KMSM)

table1-1,table1-2

0.80210.1825table1-1,table1-3

0.82480.21991◦ 違い

0.99860.61090.99250.75292◦ 違い

0.99560.4242

0.97770.6431

table1-1,table1-2-1

0.81630.18393◦ 違い

0.99180.31990.95980.5626table1-1,table1-2-2

0.87970.27844◦ 違い

0.98770.2702

0.94180.5121

table1-2,table1-3

0.78040.13945◦ 違い

0.98390.26140.9266

0.4821

table1-2,table1-2-1

0.99210.7877table1-2,table1-2-2

0.93320.3039table1-3,table1-2-10.80110.1432

table1-3,table1-2-2

0.836

0.1921

table1-2-1,table1-2-2

0.93600.2975

表 13 より回転の違いが大きいほど類似度の低下につながっている．KMSM の方が S [n]，cos2 θ1 の値は MSM よりも小さい．しかし表 12 の human と spider という異なる物体の中でも最も高い類似度が cos2 θ1 = 0.8176, S [n] = 0.2505 である．

表 16

このことから例え最大誤差の 5◦ 回転していても同一物体であ

重みの大きさ，位置を変更した場合の類似度 (R=50, フーリエ変換)2cos2 θ1 (KMSM) S [n](KMSM)ると認識できることが分かる．またこれらの実験から cos θ1

モデル名の値を 0.9 をしきい値とし，それ以上であればマッチングする

table1-2,table1-4

0.69360.2247

モデル，それ以下であれば異なるモデルと判断することにする．

table1-2,table1-5

0.06800.02245. 2. 3 平行移動と回転を含む重みありモデルとの類似度

table1-2,table1-6

0.11910.0475table1-3,table1-4

0.05900.0195table1-3,table1-5

0.06970.0236table1-3,table1-6

0.11550.0413モデル table1-2-2 を用いた．具体的にはボリュームデータの値

table1-4,table1-5

0.982

0.7605を 1 から 20 に変更した．

table1-4,table1-6

0.85480.4037table1-5,table1-6

0.84750.3836次に平行移動や重みを加味したした場合の結果を示す．table1-

2 を平行移動したモデル table1-2-1 と，平行移動かつ回転した

表 14 重みを加味したモデルとの類似度 (R=50，フーリエ変換)
モデル名

cos2 θ1 (KMSM) S [n](KMSM)

table1-1,table1-2

0.86690.5100の差として現れている．表 14 の table1-2 と table1-2 の類似度

table1-1,table1-3

0.86910.5126が高くなるのは脚の違いが一つであり，重みが１箇所しか違わtable1-1,table1-2-1

0.89260.5108ないからと考えられる．フーリエ変換を施すと, 重みの位置がtable1-1,table1-2-2

0.85600.4137

異なる場合や，重みの値の差が大きい場合は正しくマッチング

table1-2,table1-3

0.95730.5647

できることがわかる．

table1-2,table1-2-1

0.99570.8142

table1-2,table1-2-2

0.91960.4726table1-3,table1-2-1

0.94530.5485

る位置合わせ)table1-3,table1-2-2

0.91390.4777モデル名

table1-2-1,table1-2-2

0.93600.4674

table1-2,table1-4

0.74490.1329table1-2,table1-5

0.73620.1372

表 14 より平行移動があってもマッチングは可能だと言える．

table1-2,table1-60.24150.0424

また同一形状であれば平行移動かつ回転移動していても高い類

table1-3,table1-4

0.19750.0388似度を示している．しかし一方で table1-2 と table1-3 の 0.9573

table1-3,table1-5

0.19300.0343

table1-3,table1-6

0.25330.0461

table1-4,table1-5

0.61890.1129table1-4,table1-6

0.63170.1110table1-5,table1-6

0.57850.0979のように構造が異なるモデル同士でも高い類似度を示している．次に重心による位置合わせを施した場合の結果を示す．表15 より table1-2 と table1-3 の類似度が 0.7804 となっており，

表 17

重みの大きさ，位置を変更した場合の類似度 (R=50, 重心によcos2 θ1 (KMSM) S [n](KMSM)

table1-2 と table1-2-2，つまり同一物体が移動，回転している
場合の類似度よりも高くなっている．このことからフーリエ変換を施すよりも効果的であるかことが確認できる.

5. 2. 4 構造の異なるモデルとの類似度
前節の結果を踏まえてさらに重みであるボリュームデータの値を 20 ∼ 45 に変え，さらに重みのある脚の本数も変え実験を行った．
表 16 より，table1-2 と table1-4，5，6 との類似度は低くなっている．この結果から重みのある位置が異なればそれも類似度

表 17 より table1-4 と table1-5 の類似度は 0.6189 となり，0.9 を下回っている．このことからフーリエ変換では誤ってマッチングしてしまうものも区別できることがわかる．

5. 3 投影データの枚数による類似度の推移
投影データの枚数 R = 50, 100, 200 に変化させ，類似度の値の推移を調べた．形状の異なる 3 次元モデルを重心による位置合わせを施して類似度を求めた．結果を以下に示す．

表 18 異なる形状のモデルの類似度 (R=50，重心による位置合わせ)cos2 θ1 (KMSM) S [n](KMSM)

モデル名

らに机の脚の位置や重みをを変更した単純な構造の異なるア
センブリモデルではマッチングできることが確認できた．またspider,human

0.82360.2077

今回投影データの計算を 3 次元ラドン変換を用いて行ったがspider,table1-1

0.00000.0000角度を細かくして求めようとすると膨大な計算時間になってしspider,table2-1

0.00250.0004

spider,table1-1-rot

0.00000.0000human,table1-1

0.00000.0000human,table2-1

0.00420.0007

human,table1-1-rot

0.00000.0000

我々は，投影データに相互部分空間法を用いることで内部構

table1-1,table2-1

0.80570.1532造を持つ 3 次元モデルに対してもマッチングを行った．今回用

table1-1,table1-1-rot

0.96330.4649いた３次元モデルの場合は外見は同じでも内部構造が異なれば，

table2-1,table1-1-rot

0.00030.0000

それらは異なると判断できた．今後は計算時間を少なくするた

まった．

6. まとめと今後の課題

めにより速く投影データを計算する手法や，少ない投影データ
表 19 異なる形状のモデルの類似度 (R=100，重心による位置合わせ)cos2 θ1 (KMSM) S [n](MSM)

モデル名

spider,human

0.83480.2364

spider,table1-1

0.00000.0000spider,table2-1

0.00390.0007

spider,table1-1-rot

0.00000.0000human,table1-1

0.00000.0000human,table2-1

0.00580.0001

human,table1-1-rot

0.00000.0000table1-1,table2-1

0.87160.1508table1-1,table1-1-rot

0.98440.4926table2-1,table1-1-rot

0.00020.0000

表 20 異なる形状のモデルの類似度 (R=200，重心による位置合わせ)cos2 θ1 (KMSM) S [n](MSM)

モデル名

spider,human

0.91180.3303

spider,table1-1

0.00000.0000spider,table2-1

0.00760.0013

spider,table1-1-rot

0.00000.0000human,table1-1

0.00000.0000human,table2-1

0.00840.0015

human,table1-1-rot

0.00000.0000table1-1,table2-1

0.91320.1638table1-1,table1-1-rot

0.9947

0.5212

table2-1,table1-1-rot

0.00040.0000

表 18,19,20 から投影データの枚数を増やすと類似度の値が増加する傾向にあることが分かる．

5. 3. 1 実 行 時 間
本研究の実行時間について示す．相互部分空間法を用いてマッチングを行う時間に比べ投影データの計算時間のほうが大きくかかることが分かる．
表 21 実 行 時 間
手法

計算時間 (秒)3 次元ラドン変換 (648 枚)

88.4

相互部分空間法 (R=50)0.8

核非線形相互部分空間法 (R=50,ri =5,rd =6)

1.1

本研究の結果として，今回用いた３次元モデルにおいては回転，移動，または回転移動していてもマッチングできた．さでマッチングをすることが課題となる．またより複雑なアセンブリ構造を持つ 3 次元モデルでのマッチングが課題となる．
文

献[1] Ding-Yun Chen，Xiao-pei Tian，Yu-te Shen and Ming
Ouhyoung”On Visual Similarity Based 3D Model Retrieval”，The Eurographics Association and Blackwell Publishers 2003 volume 22(2003)，Number 3.
[2] 呉嘉寧，福井和広”局所部分空間集合を用いたアンサンブル識別に基づく 3 次元物体認識”，部分空間法研究会 Subspace2008.
[3] 坂野鋭，武川直樹，中村太一”核非線形相互部分空間法による物体認識”，電子情報通信学会論文誌 D Vol．J84-D2 No．8 pp．
1549-1556.
[4] 新垣仁，福井和広”多視点画による類似形状を有する 3 次元物体の高精度識別の検討”，電子情報通信学会技術研究報告． PRMU，
パターン認識・メディア理解 107(539)， 151-156， 2008-03-03.
[5] 堀田政二，河原智一，山口修，坂野鋭”核非線形相互部分空間
法の振る舞いについて”，電子情報通信学会信学技報 Vol.110
No.187 ，2010-08-29[6] 鈴木一史”3 次元 Laws マスクによるボリュームデータの解析に関する研究”，電気通信普及財団研究調査報告書 (CD-ROM)
号：23 ページ：582-593，December 2008.
[7] YueGao，Qionghai Dai，Meng Qang，Naiyao Zhang”3D
model retrieval using weighted bipartite graph matching”，
Signal Processing: Image Communication，Volume 26, Issue 1, January 2011, Pages 39-47.
[8] Bernhard Scholkopf Alexander Smola and KlausRobert
Muller”Nonlinear Component Analysis as a Kernel
Eigenvalue Problem” Neural Computation，vol.10,pp.12991319,1999.
[9] McGill 3D Shape Benchmark，
http://www.cim.mcgill.ca/ shape/benchMark/