DEIM Forum 2017 B4-3

サイノグラムの比較を用いた３次元アセンブリモデルの部分検索手法の
提案
加藤

就†

片山

薫†

† 首都大学東京大学院 システムデザイン研究科 情報通信システム学域
E-mail: †kato-syu@ed.tmu.ac.jp, ††kaoru@tmu.ac.jp
あらまし 近年, 製造業で用いられる 3 次元 CAD ソフトの普及により, 3 次元 CAD モデルの数は増加する一方である. これらを再利用するために 3 次元モデルの検索に対する需要は高まることが期待される. さらなる再利用の効率化にはモデルの一部分からモデル全体の検索を行う部分検索技術が必要になる. 本稿では, モデルの構成からタイプごとに分類する必要はあるが, ３次元 CAD アセンブリモデルの形状に加えて, 部品の配置まで考慮した部分検索手法を提案する. アセンブリモデルを構成する部品の識別のため, 使用されている部品の種類ごとに数値を付与する. アセン
ブリモデルに対して, 複数の視点から投影画像を生成する. こうすることで部品に付与された数値を投影画像に反映させる. この投影画像に対してラドン変換を行い, サイノグラムを生成し, 得られたサイノグラム同士を比較して検索を行う. データベースモデルには部品の配置が異なる 3 次元 CAD アセンブリモデルを３種類用意し，提案手法を実験的に評価した．
キーワード 部分検索，３次元モデル，アセンブリ構造,

1. は じ め に

投影データ
Gear モデルは, Bolt ５つ, Planet ５つを構成部品に含むモデルである. クエリモデルが Bolt ５つでありデータベースモデルの

近年, 製造業などでは３次元 CAD を用いてモデル設計が行Bolt と同じ配置であれば部分検索の対象である. しかし本研究われている. 特に製造業では部品の組み合わせによって１つのではクエリモデルの Bolt, Planet の数が５つより少ない, 図 2

モデルを表すアセンブリモデルを用いて設計を行うことが多い.

のような場合もデータベースモデルと同じ配置であれば, 部分

年々増えているデータを効率的に管理するためには, ３次元ア

検索の対象として扱う. 同じ部品で構成されている場合であっセンブリモデルの検索手法が必要となる. 効率的に管理するこても, 部品の配置が異なる場合は部分検索の対象として扱わなとが可能になれば, 設計者の設計にかかる時間が短縮されよりい. 本稿ではクエリモデルを Gear モデルとした場合, Gear モ

効率的な設計, 生産につながる. ３次元モデルの検索手法としデルに形状が似ているデータベースモデルを検索することを形て, 形状だけを特徴量に反映して検索を行うのが一般的である.

状検索という. 形状検索の場合は, クエリモデルに対して類似す

３次元アセンブリモデルにおいては, 形状に加えて, 各部品のるデータベースモデルを検索することが目的であるため, クエ

配置まで識別する検索手法が必要になる. またデータの再利用

リモデルと検索したいデータベースモデルの形状が類似していをする場合, 構成部品単位で検索を行うことができれば, よりるという前提がある. しかし部分検索においては, クエリモデ

効率的な再利用が可能になる. 部品単位で検索を行う場合, モルがデータベースモデルの一部であるため, 検索したいデータ

デルの一部分から全体を検索する部分検索技術が必要になるが,ベースのモデルと形状が類似しているとは限らない. そのため,比較するモデルの形状が異なるため, 類似するモデルを検索す

画像の類似度を計算する方法では, 部分検索の実現は難しい.

る技術の流用では実現が難しい. アセンブリモデルの形状と部

本稿では投影画像に２次元ラドン変換を行い, 得られたサイ品の配置を識別する３次元モデルの検索手法として複数の視点

ノグラムの性質を利用し比較を行う手法を提案する. 検索の前からの投影画像を用いた３次元モデル検索がある. 複数枚の投準備として, データベースモデルの構成部品でありクエリモデ

影画像の類似度を計算して, ３次元モデルの類似度とするもの

ルの構成部品でない部品の削除と部品を表すラベル値の重み付である. 投影画像に対してラドン変換を行い, フーリエ変換をけを行う. なお元々のラベルはデータベース内で部品に対して行い位相限定相関法で比較することでモデルの類似度を計算し一意にラベルが決まっているものとする. ラベルの値は検索結ている. しかし得られた投影画像の類似度を計算する方法では果に必ず影響してしまう. その影響を少なくするため, それぞ

その物体が比較対象の部分モデルなのかどうかはわからない.

れの部品に対して体積に基づいたラベルの値の設定を行う. サ

部分検索の場合には, モデル全体に対して比較対象がそのモデイノグラムの性質上, ３次元アセンブリモデルの平行移動と回ルを構成する部品であるため, 必ずしも類似しているわけでは転量がサイノグラムの上下の平行移動に置き換わる. このサイない. 図 1 の Gear モデルを例に本稿で扱う部分検索についてノグラムの性質を利用してサイノグラムの比較を行う. サイノ

説明する. 図 1 の Gear モデルは複数の部品が組み合わさり１グラムの比較には時間がかかってしまう. そのため, クエリモ

つのモデルが構成されているアセンブリモデルである. 例えばデルの投影点間の回転量を計算し, データベースの投影点を絞

Spacer Case
PlanetCover

ぎやノイズに対して頑強な３次元モデルの検索を行う手法を提案している. ３次元モデルは製作者によって, 位置・大きさ・向きが任意である. ３次元モデルの検索の手法としてモデルの位
置や向きを合わせて検索を行う方法がある. 立間ら [4] は検索を行う前の処理として, モデルの面上に点をランダムにとり, 点群の主成分分析を行うことでモデルの軸を決定し, その軸を利用した位置合わせの手法を提案した. 位置合わせを行ったモデルに対して, レンダリングを行い, ４つの形状表現を生成し, それぞれのフーリエスペクトルを計算し, それらの低周波成分のBolt

Output Sha.
Cap
図 1: Gear モデル

組み合わせを特徴量として検索を行っている. これらの手法については, アセンブリモデル構造を持たない３次元モデルを検索の対象としている. アセンブリ構造を持つモデルを対象にした研究として, Deshmukh ら [5] はモデルの構成部品を頂点としたグラフに変換し, グラフ検索を行うことで, モデルの内部構造を識別するモデル検索を提案している. 部分検索の研究として, Pablo ら [6] が提案した KAZE 特徴量がある. SIFT やSURF に用いられる Gaussian Filter によるスケールスペース
は, Gaussian Filter が等方的であるため, モデルの輪郭をぼやかしてしまい, 局所的な特徴量をうまくとれないことがある. それを解決するために, 非線形なスケールスペースを用いたのがKAZE 特徴量である. 小坂ら [7] は複数視点から Depth Buﬀer
画像という物体の深さ画像を生成し, Depth Buﬀer 画像から抽出した KAZE 特徴量のエンコーディング手法に Vector of

Locally Aggregated Descriptors(VLAD) を用いて, 局所特徴
図 2: 部分検索の対象モデルの例

量を３次元モデルの特徴量として統合し, ３次元物体の部分検索を実現している. この手法は３次元モデルのアセンブリ構造

り比較に用いるサイノグラムの数を少なくすることで計算量の削減を行う. 本稿では提案手法に対して, 実験的に評価を行う
ことで性能を評価する. 本稿では, アセンブリモデルの構成にを考慮した部分検索ではないため, 提案手法とは異なる.

3. 提 案 手 法

よってデータベースモデルをタイプ１からタイプ３に分類する.

３次元 CAD アセンブリモデルの形状と, 構成部品の配置をアセンブリモデルの部品のことをコンポーネントと呼ぶとする

考慮した部分検索手法を提案する. 検索に用いるアセンブリモと, タイプ１はコンポーネントの総数に違いがあるモデル, タイデルの形式は３次元配列であり, 異なる形式で表されている場

プ２はコンポーネント数は一致, コンポーネントの部品数に違合は３次元配列へと変換する. ３次元配列の大きさは元の３次いがあるモデル, タイプ３はコンポーネントの総数, 部品数両方

元アセンブリモデルの大きさに比例した大きさとする. 構成部に違いがあるモデルである. 提案手法は, タイプ内では正しい

品ごとにラベルを付与することで部品の情報を含む３次元配列

検索結果が得られるが, 検索結果間の比較が正しくできないたとなる.

め, 一致度の高いものから順には並べることができない. モデ

3. 1 検索に不要な部品の削除とラベル値の再付与

ルの分類は, コンポーネント数とコンポーネントの総数の２つ

一般に部分検索の場合, 構成部品の種類や数が異なる為, 比較の情報が必要であるが, これは検索を行う中で容易に把握でき

対象との形状が異なり検索が難しい. 検索の精度を上げる為に,る. そのためタイプの分類は必要になるが, 提案手法は形状と検索の前処理として不要な部品の削除とラベル値の再付与を行

部品の配置を考慮した部分検索の方法として有用である.

う. 不要な部品の削除とは, データベースモデルに含まれてい2. 関 連 研 究る部品の中でクエリモデルに含まれていない部品を削除することを表す. 元々のラベルの値を検索に用いると, ラベル間の差

３次元モデルの形状をもとにした検索はこれまで数多く提異によって検索の結果に影響を及ぼす. ラベル値の影響は完全案されている [1]. Chen ら [2] は３次元モデルを Light Fieldにはなくならないが, ラベルの値を再付与し影響をできるだけ

Descriptor(LFD) という特徴量から形状検索を行う方法を提案

少なくする. ３次元アセンブリモデル m の３次元配列の要素

した. LFD は３次元モデルを複数の方向からレンダリングし,数を V (m) とする. 同様に m の構成部品である ck の要素数を得られたシルエット画像を検索に用いている. 古屋ら [3] は, 検V (ck ) とする. また比較対象のモデルを p とする. このとき前索者が書いたスケッチを用いて, 手書きの線画スケッチの揺ら処理として以下の方法を行う.

(1)m の構成部品のうち, p の構成部品ではない部品 ck に対Algorithm 1 ComputeFeature(m, V , A)
Input: ３次元 CAD アセンブリモデル m, 投影画像を得るための球
面座標 V , ２次元ラドン変換の角度 A

Output: m の特徴量 SY N (m, V )1: for all vi ∈ V where i = 1 to |V | do2:p(m, vi ) ← vi から得た m の投影画像

3:r(p(m, vi )) ← p(m, vi ) に対して A の角度から２次元ラドン変4:

SY N (m, V ) の要素 syn(m, vi ) ← r(p(m, vi ))換を行う
5: end for

図 3: 投影

してラベル０を付与する.

(2)m の構成部品である ck のうち要素が０でない部品に対して, 1/V (ck ) をラベル値として再付与する.

3. 2 ３次元 CAD アセンブリモデルの特徴量
３次元モデルの位置や向きはそれぞれ異なるため, 一般的には事前に姿勢の正規化を行う. ３次元アセンブリモデルの検索

6: return SY N (m, V )Algorithm 2 CompareSynogram(syn1 , syn2 )Input: サイノグラム syn1 , syn2
Output: サイノグラム syn1 と syn2 の一致度
1: r1 ← syn1 の動径方向の大きさ
2: r2 ← syn2 の動径方向の大きさ
3: d2 ← syn2 の偏角方向の大きさ
4: for i = 1 to r1 doの場合, 機械部品を扱うため対称の形状を持ったり, 部品が円形5:であったりするため向きが一意に決まらないという問題がある.

6:

３次元モデルの平行移動や回転に普遍な検索を行う為には, モ

7:

syn3 ←Circ(syn2 (j, :), k)

デルの平行移動や回転に対して頑強な特徴量が必要である. そ8:mdegree1(k, :) ←ComputeSynColumn(syn1 (i, :), syn3 (:タベースモデルの比較は投影画像の特徴量を用いる. 投影画像

for k = 0 to d2 − 1 do))のような特徴量を得る為に, 図 3 のように様々な角度からアセ
ンブリモデルに対しての投影画像を得る. クエリモデルとデー

for j = 1 to r2 do

9:10:

end formdegree2(i) = min(mdegree1(:, j))11:

end forは, アセンブリモデルの３次元配列の投影面に対して垂直な値

12:

mdegree3(i) = sum(mdegree2(i))の和であり, モデルの形状や構成部品の配置も画像に反映され

13: end forている. 本稿では Geodesic Dome の頂点座標を投影点として,14: mdegree = sum(mdegree3)

３次元アセンブリモデルの特徴量を得る. こうして得られた投15: return mdegree

影画像に対して, ２次元ラドン変換を行うことでサイノグラム
を得る. サイノグラムの性質として２次元平面上の平行移動がAlgorithm 3 CompareSynColumn(s1 , s2 )

動径方向の平行移動で表され, ２次元平面上の回転が偏角方向

Input: サイノグラムの列 s1 , s2の平行移動として表される. その後, 動径方向に対して１次元離Output: サイノグラムの列 s1 と s2 の一致度

散フーリエ変換を行い振幅スペクトルを得て, さらに角度方向
へ, １次元離散フーリエ変換を行い振幅スペクトルを得る. こ

1: r1 ← s1 の動径方向の大きさ
2: for i = 0 to r1 − 1 do
3:

うすることにより, ２次元空間において平行移動と回転に対しs3 ←Extension(s1 , i)

4:

N (i, :) ← s3 (:) − s2 (:)て頑強な特徴量が得られる. 本稿では振幅スペクトルを位相限

5:if N の要素 n > 0 then

定相関法で計算する手法を比較手法として行う. それに加えて

6:

形状が異なる部分検索を実現するために投影画像を２次元ラド7:ン変換したサイノグラムを比較に用いる.

8: end for3. 3 アセンブリモデル間の一致度
アセンブリモデルの特徴量は２次元配列で表されている. 一n←0
end if

9: mdegree ← sum(N )10: return mdegree

致度の計算に用いるのは投影画像に対して２次元ラドン変換を行ったサイノグラムである. 特徴量の抽出の手順は Algorithm1

納していく処理を表している. これは２次元平面上の物体の回に示す. ２つのサイノグラムを比較し, サイノグラム間の一転量が偏角方向の平行移動に置き換わるサイノグラムの性質を致度を計算する. ２つのサイノグラムの一致度の計算の手順利用した処理である. Algorithm3 はサイノグラムの列同士の比は Algorithm2 と Algorithm3 に表す. Algorithm2 はサイノ

較の手順を表している. Algorithm3 の Extension(s, i) は s をグラム間の一致度の計算の手順を表している. Algorithm2 の動径方向に i だけずらし, 配列の大きさが動径方向の大きさを超Circ(syn, k) は syn を偏角方向に k ずらし, 配列の大きさが偏えた場合は, 配列を拡張し０を代入する処理を表している. また角の大きさを超えた場合は, また配列の１番目から順に値を格

サイノグラムの比較の例を図 4 と図 5 に示す. 図 4 はサイノグ

Algorithm 4 ComputeMatchingDegree(m1 , m2 , V1 , V2 , A)
Input: ３次元 CAD アセンブリモデル m1 , m2 , 投影画像を得るための球面座標 V1 , V2 , ２次元ラドン変換の角度 A

Output: m1 と m2 の一致度 mdegree
1: mdegree ← 0
2: SY N (m1 , V1 ) ←ComputeFeature(m1 , V1 , A)
3: SY N (m2 , V2 ) ←ComputeFeature(m2 , V2 , A)
4: for i = 1 to |V1 | do
5:
6:

for j = 1 to |V2 | domdegree1(i, j) ←CompareSynogram(syn(m1 , v1 ), syn(m2 , v2 ))7:

end for8:n ← max(mdegree1(i, :))9:while n < 0 do

図 5: サイノグラムの全体の比較の例

3. 4 一致度計算の効率化

10:max(mdegree1(i, :)) ← 0

３次元アセンブリモデルの一致度の計算に, サイノグラムを

11:n ← max(mdegree1(i, :))用いて部分検索を行う. サイノグラムの比較に時間がかかって

12:

end while13:

mdegree2(i) ← max(mdegree1(i, :))14: end for
15: mdegree ← sum(mdegree2)
16: return mdegree

しまう問題がある. 検索にかかる時間を削減するために２つの工夫を行う. １つ目が投影数の削減である. 以前は, クエリモデ
ルの投影数とデータベースモデルの投影数を等しくして投影画像の比較を行っていた. 提案手法ではクエリモデルの投影数を減らして検索を行った. ２つ目の工夫として, クエリモデルの投影点間から回転量を計算し, データベースモデルの投影点を絞り比較するサイノグラムの数を減らすことで計算量の削減を行う. 例えば図 6 のクエリモデルの投影点のように, A から F ま
での６つの投影点から投影画像を生成している場合, 点 A から生成したクエリモデルの投影画像１枚に対してデータベースモ
デルの全ての投影点から生成した投影画像との一致度を計算していた. クエリモデルの投影画像に対して, 最も一致度が高い
投影画像を持つ投影点を対応点と呼ぶとすると, クエリモデルの投影画像１枚目の対応点がわかれば, ２枚目の対応点の座標
は Geodesic Dome の頂点座標の回転量から計算することができる. クエリモデルの投影画像１枚目の対応点は, クエリモデ

図 4: サイノグラムの列同士の比較の例

ルの投影画像１枚目とデータベースモデルの全ての投影画像の一致度を計算し, 最も一致度が高い投影画像の投影点を対応点

ラムの一列同士の比較の手順を示しており, 図 5 はサイノグラ
ムの全体の比較の流れを示している. パラメータはそれぞれのAlgorithm と対応している. 図 4 はサイノグラムの列 s1 と s2の比較の手順を示している. まずは s1 と s2 の各要素の差を計算する. 計算した値の中で０より大きい値は０とする. s2 を動径方向に一行ずつずらしてこの処理を繰り返す. 得られた N の総和をサイノグラムの列間の一致度とする. 図 5 はサイノグラ
ム syn1 と syn2 の比較の手順を示している. まずそれぞれのサイノグラムの列を取り出し, 列間の一致度を図 4 の手順で計算する. syn2 を偏角方向にずらしてこの処理を繰り返す. そうして得られた mdegree1 の各列の最小値を mdegree2 とする.

mdegree2 の総和がサイノグラム間の一致度 mdegree となる.
計算された一致度については差であり, 数値は負になるが値が大きいほどモデルが一致していることを表す. しかし一致度が０を超える場合は, クエリモデルの方が大きいことを表すため除く. モデル間の一致度を計算する手順を Algorithm4 に示す.

とする. 例えば図 6 においてクエリモデルの投影画像１枚目の対応点が投影点 G だったとする. 投影点 G に対して, Geodesic

Dome の頂点座標から計算した回転量分だけ回転をした点を G’とすると, クエリモデルの投影画像２枚目の対応点が G’ 付近となるはずである. 同じ点から投影されるということが起こりにくいため, 提案手法では計算した点の座標から距離が近い５つの投影点を対応点の候補の点, 候補点とする. クエリモデルの投影画像２枚目以降との一致度計算についてはこの候補点から得られた投影画像のみと計算を行い, 候補点の中で最も一致度が高い投影画像が得られた点をそれ以降の対応点とし一致度計算を行っていく.

4. 評 価 実 験
我々は, 提案手法について, 部品の配置が異なる３次元 CAD
アセンブリモデルを用いて実験的評価をした. GrabCAD [9] から選んだ, 様々な部品を持つ図 7 に示したような Clutch, Die,

Gear の３種類の３次元 CAD アセンブリモデルを選び, 簡素化のためにいくつかの部品を削除した. ３種類のモデルそれぞれ

z

z

B
A
C

Clutch A

Clutch B

Clutch C

Clutch D

Clutch E

Clutch F

Clutch G

Clutch H

Clutch I

Gear A

Gear B

Gear C

Gear D

Gear E

Gear F

Gear G

Gear H

Gear I

Die A

Die B

Die C

Die D

Die E

Die F

Die G

Die H

Die I

x

x

I
G’

F

H

D
G

E
y

y

(a) クエリモデルの投影点(b) データベースモデルの投影点

図 6: 対応点決定の例

図 8: 使用したモデル一覧

表 1: モデル一覧

図 7: 使用したモデル

モデル名

タイプ１

タイプ２

タイプ３

正解モデル

ClutchA, B, C

D, E, F

G, H, I

A, D, GDie

A, B, C

D, E, F

G, H, I

A, D, G

Gear

A, B, C

D, E, F

G, H, I

A, D, G

表 2: Clutch モデルの構成をモデルの構成によってタイプ１からタイプ３に分類した. タ

ラベル値

イプ１はコンポーネントの総数に違いがあるモデル, タイプ２600

1, 2, 3, 4 1, 2, 3, 6 1, 3, 4, 6 2, 3, 4 1, 2, 3 2, 4, 6 1, 2 1, 3 1, 4はコンポーネント数は一致, コンポーネントの部品数に違いが

500

2, 3, 42, 3, 4

1, 3, 5

3, 4

4, 5

1, 5

2

5

5

400

0

0

0

6

5

3

0

0

0

あるモデル, タイプ３はコンポーネントの総数, 部品数両方に違

300

0

0

0

6

1

3

0

0

0

いがあるモデルである. それぞれのタイプの中で部品の配置が

100

1

1

1

1

1

1

1

1

1

A

B

C

D

E

F

G

H

I

異なる３種類のモデルを作成した. Clutch, Gear, Die それぞれに対して, タイプ１として A, B, C の３種類のモデルを用意し度計算の手順については Algorithm5 に示す. Algorithm5 のた. A を正解モデルとし, B,C を不正解モデルとする. タイプ

POC(f (m1 , v), f (m2 , v)) は特徴量 f (m1 , v) と f (m2 , v) を位

２については D を正解モデル, E, F を不正解モデルとする. タ

相限定相関法で比較することを表す.

イプ３については G を正解モデル, H,I を不正解モデルとする.
モデルの一覧を表 1 に示す. クエリとして与えられたアセンブ

4. 2 部品の配置が異なる３次元 CAD アセンブリモデルの
識別

リモデルをクエリモデルと呼び, クエリモデルと比較するアセ

我々は, 部品の配置が異なるモデルを用いて, 提案手法を実

ンブリモデルをデータベースモデルと呼ぶ. データベースモデ

験的に評価した. 前述の計 27 個のアセンブリモデルをデータ

ルは, Clutch, Die, Gear の３種類に対して９パターン, 計 27 個

ベースモデルとし, それらのモデルについてあらかじめ投影画のアセンブリモデルを用意した. クエリモデルとして Clutch1,

像を生成しておく. 投影画像は各モデルで 162 枚用意し, 27 個

Die1, Gear1 の３モデルを用意した. それぞれにランダムに平のモデルの投影画像に対してサイノグラムを生成し, それらを行移動と回転を加えたアセンブリモデルを 10 種類ずつ用意し用いた. クエリモデルも同様に投影画像を 42 枚生成し, それら

た. データベースモデルにも, それぞれランダムな平行移動と回を用いてデータベース検索を行う. 図 9 が Clutch, Die, Gear

転を加えた. 実験に用いたモデルを図 8 に示す. 色の違いは部の各データベースモデルとクエリモデルとの一致度を提案手法

品の違いを表している. Clutch モデルの構成を表 2 に示す. モで計算したものである. Clutch, Die, Gear の各モデルのタイ

デルのサイズは 64 × 64 × 64, データベースモデルの投影数はプ内で正解モデル (各モデルの A, D, G) の一致度が最も高い

162, クエリモデルの投影数は 42 で実験を行う. Visual C++という結果を得ることができた. この結果から, 我々の提案手

2012, MATLAB 2015b を Windows 7 Professional 64 bit 上法は実験で使用したアセンブリモデルについては, タイプごとで用い, 2.8GHz Intel Core i3 プロセッサ, 16GB RAM のコンに分類すれば, 形状だけでなく, 部品の配置が異なるアセンブ

ピュータで実験を行った.

リモデルの部分検索の識別ができているとわかる. Clutch モデ

4. 1 比 較 手 法ルのタイプ３のモデル (Clutch G, H, I) については他のタイプ

位相限定相関法を用いた３次元モデル検索を行う. 提案

１, ２の結果より全体的に一致度が高い. Clutch H, I について手法と同様に, ３次元モデルの形状と部品の配置の識別をす

は不正解モデルであるが, タイプ２の正解モデルより一致度がる. 検索に用いる特徴量は Algorithm1 で得たサイノグラム

高くなっている. すなわちタイプごとに分類せずに検索を行うのパワースペクトルを計算したものである. モデル間の一致と, 正解モデルを正しく検出できない. 各手法の検索精度を図x 100000

Algorithm 5 ComputeMatchingDegree2(m1 , m2 , V1 , V2 ,A)
Input: ３次元 CAD アセンブリモデル m1 , m2 , 投影画像を得るため-8-10

Output: m1 と m2 の一致度 mdegree

-12
-14

1: SY N (m1 , V1 ) ←ComputeFeature(m1 , V1 , A)

4:

Clutch A Clutch B Clutch C Clutch D Clutch E Clutch F Clutch GClutch H Clutch I(a) Clutch1 をクエリモデルとした場合の各モデルとの一致度
x 100000

3: for i = 1 to |V1 | dosyn(m1 , vi ) に対して動径方向に離散フーリエ変換を行い, 振幅
スペクトルをとる

5:

さらに角度方向に対しても同様に, 離散フーリエ変換を行い, 振

-4
-6

一
致
度

の球面座標 V1 , V2 , ２次元ラドン変換の角度 A

2: SY N (m2 , V2 ) ←ComputeFeature(m2 , V2 , A)

0
-2

0
-2
-4

一
致
度

-6

幅スペクトルをとる-8

6:

f (m1 , vi ) に格納する

-10

7:

for j = 1 to |V2 | do8:

syn(m2 , vj ) に対して動径方向に離散フーリエ変換を行い, 振

-12
Die A

x 100000

さらに角度方向に対しても同様に, 離散フーリエ変換を行い振幅スペクトルをとる

10:

f (m2 , vj ) に格納する

11:

s(i, j) ←POC(f (m1 , vi ), f (m2 , vj ))12:

16: return mdegree

検索精度 =| タイプ内で最も一致度が高いモデルのうち, 正解モデルであるモデルの数 ||Q|

各処理にかかった時間を図 11 に示す. サイノグラムの比較を用いた手法は一致度計算, サイノグラムの比較にかかる時間が処理時間のほとんどを占めていることがわかる. また位相限定

Die F

Die G

Die H

Die I

0

-3
-4
-5
-6
Gear A Gear B Gear C Gear D Gear E Gear F Gear G Gear H Gear I(c) Gear1 をクエリモデルとした場合の各モデルとの一致度
図 9: サイノグラムの比較を用いた手法による各モデルとクエリモデ
ルとの一致度10 に示す. 本実験における検索精度とは, クエリモデルの集合
を Q とすると以下のように表される.

Die E

-1

13: end for
14: mdegree ← s の各行の最大値の総和

Die D

-2
一
致
度

end for

15: mdegree ← mdegree/|V1 |Die C(b) Die1 をクエリモデルとした場合の各モデルとの一致度

幅スペクトルをとる
9:

Die B

位相限定相関法

サイノグラム

1
0.9
0.8
0.7
検 0.6
索
精 0.5
度 0.4
0.3
0.2
0.1
0

図 10: サイノグラムの比較を用いた手法と位相限定相関法を用いた手法の検索精度相関法より検索精度が高いが, 処理時間が長いことがわかる.

4. 3 投影数を変化させた時の検索精度と処理時間
投影画像の枚数を変化させ, データベース検索の実験を行い,
我々の提案手法の検索精度とモデル間の一致度計算にかかる処理時間の評価を行う. 本稿では投影画像の枚数は, Geodesic

Dome の頂点数によって決定する. ここでは頂点数を 42, 92,
162, 252, 362 と変化させ, 投影枚数を 42 枚, 92 枚, 162 枚, 252
枚, 362 枚と変化させたときのデータベースの各モデルの一致度と処理時間を評価する. 図 12 はそれぞれ正解モデルを Clutch

前処理

投影画像作成

一致度計算

250
200
150
100
50
0
サイノグラム

位相限定相関法

図 11: サイノグラムの比較を用いた手法と位相限定相関法を用いた手法のモデル間の一致度計算にかかる時間

A, Die A, Gear A としたときのクエリモデルとデータベース
内の各モデルとの一致度を表している. 図 12 から, 正解モデル

表している. 図 13 より投影数を増やせば処理時間が長くなる

が Clutch A, Die A のときは, 投影数を変えても正解モデルのことがわかる.

一致度が一番高くなっていることがわかる. すなわちタイプご

4. 4 計算量削減による処理時間への影響とであれば正しく検索ができているといえる. しかし, 正解モ

最も処理時間がかかっているのが, サイノグラムの比較であデルが Gear A のときでは, 投影数によっては正解モデルではる. 処理時間を短縮するためにサイノグラムの比較を行う回数ないモデルの一致度が最大の一致度となっている場合がある.

を減らし, 計算量を削減する. 提案手法では 3. 4 で述べた方法

これは, モデルの姿勢の影響により, 一致度が高い投影画像が少で計算量の削減を行い, 検索精度とモデル間の一致度計算にかないために, 検索ができなかったと考えられる. 図 13 は投影数

かる処理時間を評価する. ２枚目以降の一致度計算に用いる投を変化させたときのモデル間の一致度計算にかかる処理時間を

影点の数を 3, 5, 12, 42, 92, 162 と変化させた場合の処理時間

一
致度

x 100000

Clutch A

Clutch B

1

Clutch C

0.95

0
-2

一 0.9
致
度 0.85

-4
-6
-8
-10

0.8

-12

0.75

-14
42

92

162

252

3

362

5

(a) Clutch1 をクエリモデルとした場合の各モデルとの一致度

一致度

x 100000

Die A

Die B

12

42

92

162

一致度計算に用いる投影点の数

投影数

図 15: 検索に用いる投影点を削減した場合の検索精度

Die C

0

位相限定相関法-2

サイノグラム

1

-4

0.8

-6

検 0.6
索
精
度 0.4

-8
-10
-12
42

92

162

252

0.2

362

0

投影数

64×64×64

128×128×128

180×180×180

モデルサイズ(b) Die1 をクエリモデルとした場合の各モデルとの一致度

一致度

x 100000Gear A

Gear B

図 16: モデルのサイズを変更した場合の検索精度

Gear C0-1

サイノグラム-2

位相限定相関法

6000

-3

5000

-4

4000
処
理
時 3000
間
2000

-5
42

92

162

252

362

投影数

1000
0

(c) Gear1 をクエリモデルとした場合の各モデルとの一致度
図 12: 投影数の変化と各クエリモデルにおけるデータベースモデルの一致度

64×64×64

128×128×128

180×180×180

図 17: モデルのサイズを変更した場合のモデル間の一致度計算にかかる時間

ClutchDie

Gear

4. 5 モデルのサイズによる検索精度と処理時間の影響

350

モデルのサイズを 128 × 128 × 128, 180 × 180 × 180 に変更

300
250
処
理 200
時 150
間
100

した場合の検索精度とモデル間の一致度計算にかかる処理時間を図 16, 17 にそれぞれ示す. 図 16 よりモデルのサイズを大き

50
0
42

92

162

252

362

投影数

図 13: 投影数を変化させたときのモデル間の一致度計算にかかる時間

くすると検索精度が向上していることがわかる. これは, モデ
ルのサイズを大きくすることにより, モデルの形状が投影画像により鮮明に反映し検索精度が向上していることが原因だと思われる. 図 17 よりモデルのサイズを大きくすると, モデル間の

4000
3500
3000

一致度計算にかかる処理時間が長くなることがわかる. これは処 2500理
時 2000間 1500モデルのサイズを大きくしたことにより, 投影画像の生成にかかる時間と一致度計算にかかる時間が長くなっていることが原

1000
500
0
3

5

12

42

92

162

因である.

一致度計算に用いる投影点の数

図 14: 検索に用いる投影点を削減した場合のモデル間の一致度計算にかかる時間

5. 結論と今後の課題
データベースモデルをモデルの構成からタイプごとに分類す
る必要はあるが, 投影画像を用いて, ３次元 CAD アセンブリモが図 14 である. また投影点を削減した場合の提案手法の検索精

デルの形状や部品の数だけでなく, 部品の配置まで考慮した部

度の変化を図 15 に示す. 図 15 より投影点を５点まで削減して分検索手法を提案した. 形状が異なる部分検索の実現のためにも検索精度にあまり影響がないことがわかる. しかし, 投影点

サイノグラムを用いて比較を行い, 比較にかかる時間を早くす

を３点まで削減してしまうと, 検索精度が低下してしまう. こるために投影数の削減と比較に用いる投影点の削減を行った.

れは, 投影点の削減により正しい対応点がとれなくなっている

我々は, 提案手法の評価に３種類のモデルに対して, モデル構成ことが原因だと思われる. 投影点の削減を行わない場合, 比較の違う３タイプそれぞれ３種類のモデルをデータベースモデルに用いる投影点の数は 162 である. 提案手法では２枚目以降のとして用意し, 実験結果からタイプごとの識別については提案

一致度計算に用いる投影点の数を５点に削減し, モデル間の一手法の有効性を示した. 今回はタイプごとでの識別であったが,致度計算にかかる処理時間を５％まで短縮することができた.

今後はモデル構成の違う場合でも識別が可能にできるような部

分検索手法の提案が必要である.

文

献[1] J.H. Tangelder and R.C. Veltkamp. A survey of content
3d shape retrieval methods. Multimedia Tools and Applications, Vol. 39, No. 3, pp. 441–471, 2008.
[2] D.Y. Chen, X.P. Tian, Y.T. Shen, and M. Ouhyoung. On
visual similarity based 3d model retrieval. Computer Graphics Forum, Vol. 22, No. 3, pp. 223–232, 2003.
[3] 古屋貴彦, 松田隆弘, 栗田侑希紀. 多視点画像特徴の多様体を用いたスケッチによる３ d モデルの検索. NICOGRAPH, 2013.
[4] 立間淳司, 関洋平. 多重フーリエスペクトル表現に基づく三次元モデルの形状類似検索. 電子情報通信学会論文誌, Vol. J91-D,
No. 1, pp. 23–36, 2008.
[5] A.S. Deshmukh, A.G. Banerjee, S.K. Gupta, and R.D. Sriram. Content-based assembly search: A step towards assembly reuse. Computer-Aided Design, Vol. 40, No. 2, pp.
244–261, 2008.
[6] Pablo F. Alcantarilla, Adrien Bartoli, and Andrew J. Davison. Kaze features. European Conference on Computer
Vision, 2012.
[7] 小坂龍一, 立間淳司, 青野雅樹. 複数視点画像の局所特徴量を用いた三次元物体の部分検索手法. ITE Technical Report, Vol. 37,
No. 56, pp. ME2013–124, 2013.
[8] 千田伸男, 佐藤拓実, 片山薫. 部品を強調した投影画像による 3次元モデルの検索手法とその実験的評価. データ工学と情報マネジメントに関するフォーラム, pp. E5–2, 2016.
[9] Grabcad.http://grabcad.com/library.