DEIM Forum 2019 G6-1

球面調和関数を用いた部品配置の異なる３次元アセンブリモデルの検索手法
長山 大輔†

片山薫†† 首都大学東京 システムデザイン研究科 情報通信システム学域 〒 191–0065 東京都日野市旭が丘 6–6
E-mail: †nagayama-daisuke@ed.tmu.ac.jp, ††kaoru@tmu.ac.jp
あらまし

近年，３次元 CAD ソフトウェアを使用してアセンブリモデルを構築して製品を設計することが一般的になっている．アセンブリモデルを検索する手法として複数の視点からの投影画像を使用する手法があるが，特徴量のサイズが大きく，視点同士の対応付けのために類似度計算に時間がかかる問題がある．本稿では，複数の視点からの投影画像を球上の値とみなし，球面調和変換を利用して特徴量を得る．先行研究に比べ，特徴量のサイズが 90%以上削減され，類似度計算にかかる時間が最大 50%削減された．その結果，より解像度が高い投影の作成や，より多くの投影画像を扱うことが可能になり，より複雑なアセンブリモデルの検索が可能になった．
キーワード ３次元モデル，投影画像，アセンブリ構造，球面調和関数
る．また，部品の種類ごとに付与されるラベルについて，事前

1 はじめに
近年，GPU 性能の大幅な向上や低価格帯 3D プリンタ，材料の普及により，製造業などでは３次元モデルによるものづくりが広く普及している．自動車や携帯電話，建築物といった分野
では，設計や強度解析に CAD などのデジタルモデリングソフ
トによる３次元モデルが利用されており，また，工業分野だけでなく教育・医療など様々な分野でも３次元モデルは利用されており，３次元モデルのデータ量は年々増加している．３次元
モデルデータには技術者のノウハウが織り込まれており，既存の３次元モデルデータを参照することで，モデルデータそのものに加え，モデルの強度解析や生産工程，加工のための工具の情報，コストなどの情報などエンジニアリングに関わる全てのに対象データベース内で統一されている場合には付与されたラ
ベル値をもとに対応する部品を決定することができるが，例えばモデルの作成者が違うために同じ基準でラベルが振られていない等，振られているラベル値があてにならない場合も考えられる．ラベルの統一をあらかじめ行うにしても，データベースのモデル数が多くなれば多くなるほど，ラベルの統一は現実的ではなくなる．ラベルが統一されていない場合には，比較する部品の対応関係が分からないことを前提に検索手法を考える必要がある．よって，このような部品の対応関係が分からないことを考慮した上で，内部構造の微妙な違いも考慮して識別し，形状・内部構造ともに同一なモデルを検索できるような手法を考える必要がある．

情報を利用することができる．そのため，既存の３次元モデルを再利用することで，３次元モデルの設計者は新しい製品を効率よく設計することが可能となる．そのため，３次元モデルの検索に関する研究はこれまで多くなされてきており，例えば，
飛行機や自動車を識別するような形状類似モデルの検索を対象とする手法が多く研究されてきた [1]．
しかし，機械設計などの工業分野では，部品の組み合わせ
で１つのモデルを構築する３次元 CAD アセンブリモデル（以下アセンブリモデル）を用いて設計することが一般的になっている．例として Gear と呼ばれるアセンブリモデルの形状と内部構造を図 1 に示す．図 1 の Gear は Cover，Bolt，Cap，Planet，Output，Shaft，Spacer Case の 6 種類の部品から構図 1: Gear モデルの形状と内部構造成されている．また Bolt と Planet のように部品の色が異なる箇所は，例えば同じ形状でも材質が異なる部品を区別するために異なるラベルを付与している場合を想定している．このような内部構造や部品の情報の微妙な違いも考慮して識別し，形状・内部構造ともに同一なモデルを検索できるような手法が確立されれば，より効率的にアセンブリモデルを扱うことができアセンブリモデルの形状と内部構造を考慮した同一モデル検索手法として，多視点レンダリングした透過投影画像を用いた検索手法 [2] がある．複数枚の投影画像の特徴量をそれぞれ計算して，それらの集合を３次元モデルの特徴量とする手法である．この手法では以下の手順で特徴量を構築する．前処理とし

て部品の種類ごとに体積の逆数に基づいたラベル付けを行い，対応した振幅スペクトルを角度 × 周波数の２次元行列に整列さアセンブリモデルの周囲から多数の透過投影画像をとる．する

せる．以降は提案手法（1D 投影）の球面調和変換以降と同様と，投影視点に対応した，アセンブリモデルの内部構造や部品の手順で，最終的な部品の特徴量が得られる．また，アセンブの配置の情報が含まれた投影画像が得られる．投影画像に対しリモデル間の距離と類似度の計算方法については提案手法（1Dて２次元ラドン変換と動径方向離散フーリエ変換を行うこと投影）と同様である．

で，投影画像の面内における回転と平行移動について不変な特評価実験として，まず，データベースモデルに部品配置が異徴量が得られる．多視点レンダリングと（面内で）回転不変ななるアセンブリモデルを 15 種類用意し，それらのモデルに対画像の全体特徴を組み合わせた手法では，視点数を十分取れば，して内部の部品の配置が異なるモデルをそれぞれ 5 タイプ，計

元々のアセンブリモデルの回転に不変な検索が可能になる．し

75 個用意し，提案手法（1D 投影）で同一モデル検索を行い各

かし，１つのモデルを視点の数だけの特徴の集合で記述するた

クエリモデルと各データベースモデルとの類似度を評価した．

め，モデル１対の比較は特徴集合と特徴集合の比較になり，計次に，先行研究である Katayama ら [2] の手法と提案手法２種

算コストが高いという問題点がある．３次元モデル検索では，による同一モデル検索で，クエリモデル１つあたりにかかる処

データベースモデルの数が増えればそれだけモデル間の類似度

理時間を比較評価した．加えて，先行研究と提案手法２種で，を計算する回数が増えるため，類似度計算の計算コストは３次投影枚数を変化させたときの，部品１つあたりの特徴量のサイ

元モデル検索全体の処理時間に大きく影響する．

ズと正答率の関係を比較評価した．最後に，先行研究と提案手

そこで本稿では，部品の対応関係が分からないようなアセンブリモデルを対象として，多視点レンダリングした投影画像と法２種について，投影枚数を変化させたときの手法ごとの同一モデル検索の正答率を評価した．

球面調和変換を利用し，形状・内部構造ともに同一なモデルを検索する手法を提案する．その際，多視点レンダリングした投
影画像による特徴集合を，球面調和変換を用いて１つの特徴量に統合することで，より効率的な同一モデル検索手法を実現す
る．多視点レンダリングした投影画像について，アセンブリモ
デルの１次元投影を使用する手法（以下提案手法（1D 投影））とアセンブリモデルの２次元投影を使用する手法（以下提案手法（2D 投影））の２つの手法を提案する．
提案手法（1D 投影）では，１次元投影計算，離散フーリエ変換，球面調和変換を用いて，回転と平行移動に不変なアセンブリモデルの特徴量を構築することで同一モデル検索を行う．
アセンブリモデルを構成する部品ごとに以下の手順で特徴量を計算する．まず，モデルの周囲からの１次元投影を作成した後，各投影について動径方向に離散フーリエ変換を行い振幅スペク
トルを得ることで，元々のモデルの平行移動に不変な特徴になる．そして，それぞれの投影角度に対応した振幅スペクトルの集合を，角度 × 周波数の２次元行列だとみなす．この行列を角度方向の各列に分け，それぞれ球面場と見なし，球面調和変換を行い，次数ごとのノルムを求めることで元々のモデルの回転に不変な特徴を得る．最後に，各球面場のノルムを順に並べる
ことで最終的な部品の特徴量が得られる．また，アセンブリモ
デル間の距離は部品同士の特徴量のユークリッド距離の総和が最小となるときの値として，アセンブリモデル間の類似度はその逆数とする．
提案手法（2D 投影）では，２次元投影計算，２次元ラドン
変換，離散フーリエ変換，球面調和変換を用いて，回転と平行移動に不変なアセンブリモデルの特徴量を構築することで同一モデル検索を行う．アセンブリモデルを構成する部品ごとに以下の手順で特徴量を計算する．まず，球面直交座標に基づいて周囲からの２次元投影を作成した後，各投影について２次元ラドン変換を行い，動径方向に離散フーリエ変換を行い振幅スペ
クトルを得ることで，２次元投影の面内における回転と平行移動について不変な特徴になる．そして，それぞれの投影角度に

2 関連研究これまで，３次元モデルの検索に関する研究は多く行われてきた [1]．例えば，Chen ら [3] は多視点レンダリングに基づくLight Field Discriptor(LFD) という形状モデル検索法を提案している．LFD ではモデルを中心とした正十二面体の頂点からレンダリングし，得られたシルエット画像の周波数スペクト
ルやツェルニケモーメントを特徴量として検索しており，これにより３次元モデルが回転していても検索を可能にしている．
平行移動と大きさについてはレンダリング前に行う姿勢正規化で対応している．また，Knopp ら [4] は３次元ボクセルグリッドから直接 SIFT，SURF 特徴量を抽出して利用することにより３次元形状を識別する手法を提案している．
本稿でも用いている球面調和関数を用いた３次元モデル検索の研究も多くある．Kazhdan ら [5] の手法では，ボクセル化した３次元モデルをシェルサンプリング（同心球状サンプリング）
し，各球面をそれぞれ球面調和変換して次数ごとのノルムを計算することでモデルの回転に不変な特徴量を構成している．しかし，この手法ではモデルの中心が揃っている必要があるため事前の平行移動正規化が必要になる．加えて，シェルサンプリ
ングによる各球面の間の連続性が考慮されていないという問題がある．その後，Papadakis ら [6] が提案した手法では，６つの軸からの深さ画像に対して離散フーリエ変換を行った２次元
特徴量と，Kazhdan ら [5] が提案したシェルサンプリングと球
面調和変換を用いた３次元特徴量とを合わせて，これをモデル
全体の特徴量とした手法を用いている．深さ画像による２次元
特徴量を組み合わせることによって，Kazhdan ら [5] の手法にあったシェルサンプリングによる各球面の間の連続性が考慮されていないという問題を解決している．ただし，モデルの回転と平行移動については事前の正規化に任せている．球面調和関数を用いたこれらの手法は，３次元モデルを対象とした形状が類似するモデルの検索手法であり，本稿の目的であるアセンブリモデルを対象とする形状・内部構造を考慮した同一モデル検索に関する研究はまだなされていない．
また，アセンブリモデルを対象としたモデル検索手法として，

Deshmukh ら [7] はモデルの構成部品を頂点としたグラフに変換し，グラフ検索を行うことでモデルの内部構造を識別するモ
デル検索を提案している．また，Hu ら [8] はアセンブリモデル
を部品ごとに分けた上で，Chen ら [3] の LFD を特徴量として使用するモデル検索を提案している．しかし，これらの手法はアセンブリモデルの内部構造を考慮した検索手法ではあるが，構成する部品の配置や種類といった内部構造までは考慮されていない我々の提案手法とは異なる．
アセンブリモデルの形状・内部構造を考慮したモデル検索の先行研究には，Katayama ら [2] が提案した手法がある．この3 提案手法
球面調和変換を用いて部品の対応関係が未知であるような３次元アセンブリモデルの形状・内部構造を考慮した同一モデル
検索手法を提案する．我々は２つの手法を提案する．特徴量の抽出に際し，３次元モデルの 1 次元投影を使用する手法と３次元モデルの２次元投影を使用する手法の２つであり，それぞれ提案手法（1D 投影），提案手法（2D 投影）と表記する．検索に用いるアセンブリモデルは部品ごとに分かれたポリゴンメッ
シュ頂点データである．また，付随ファイルにて部品の種類ごとのラベルが指定される．

3. 1 提案手法（1D 投影）

手法では，アセンブリモデルを多視点レンダリングして投影画提案手法（1D 投影）では，３次元モデルの１次元投影から像を計算し，得られた投影画像に対して部品の体積の逆数の重特徴量を構成し，その特徴量をもとに同一モデル検索を行う．

み付けを行う．その後，２次元ラドン変換，２次元離散フーリ

その後，離散フーリエ変換，球面調和変換を用いて回転と平行

エ変換の順に計算し振幅スペクトルを得ることで，アセンブリ

移動に不変なアセンブリモデルの特徴量を構築する．

モデルの回転と平行移動について不変な特徴量を計算する．モ

3. 1. 1 提案手法（1D 投影）：特徴量の抽出

デル間の類似度は，それらのモデルの特徴量間のユークリッド

提案手法（1D 投影）でのアセンブリモデルの部品から特距離を計算することで決定する．この類似度計算をデータベー徴量を得る手順を図 2 に示す．また，特徴量の抽出の手順を

スモデル全てに対して総当たりで行い最近傍となったモデルをAlgorithm 1 に示し，重み付け１次元投影の手順を Algorithm

クエリモデルに対する完全一致モデルとする．この手法により，2 に示す．

高い精度でアセンブリモデルの形状・内部構造を考慮した同一

本稿では，アセンブリモデルをラベルの異なる部品ごとに分モデル検索を行うことができる．しかし，１つのモデルを投影解し，それぞれの部品ごとに特徴量を計算する．始めに，モデ視点の数だけの特徴の集合で記述するため，モデル１対の比較

ルの周囲からの重み付け１次元投影を作成する．そして，各１は特徴集合と特徴集合の比較になり，計算コストが高いという次元投影を動径方向に離散フーリエ変換することによって，各問題点がある．３次元モデル検索では，データベースモデルの投影視点ごとに対応した元々のモデルの平行移動に不変な振幅数が増えればそれだけモデル間の類似度を計算する回数が増えスペクトルが得られる．こうして得られた投影角度ごとの振幅

るため，類似度計算の計算コストは３次元モデル検索全体の処

スペクトルを１つの特徴量に統合する．始めに，それぞれの投理時間に大きく影響する．本稿の提案手法では，多視点レンダ

影角度に対応した振幅スペクトルの集合を，角度 × 周波数の２リングによる特徴集合を球面調和変換によって一つの特徴量に次元行列だと見なす．次に，この行列を角度方向の各列に分け，統合することで特徴量のサイズを削減し，類似度計算にかかる

それぞれ球面場と見なして球面調和変換を行う．そして，次数時間を減らす手法を提案する．

ごとのノルムを求めることで元々のモデルの回転に不変な特徴

加えて，多視点レンダリングした特徴集合の計算コストを下げる研究には，Ansary ら [9] の手法がある．この手法では，機を得る．最後に，各球面場のノルムを順に並べることで最終的な部品の特徴量が得られる．

械学習によって弁別性の高い少数の視点を選び出すことによっ

ここで，２次元球面上のサンプリング定理（Driscoll ら [11]）て，類似度計算の手間を減らしている．別の手法では，Furuya

に従い，帯域幅 B で帯域制限されている場合，つまり l >=Bら [10] は多視点の画像群から抽出した多数の深さ画像による局についての球面調和係数が 0 のとき，元の関数は Gauss の求所特徴を，Bag-Of-Feature（BOF）法を用いて３次元モデルあ積法によって，B × (2B − 1) 個のサンプリング点から復元できたり１つの SIFT 特徴に統合することで類似度計算の計算コスる．したがって，Algorithm 1 での球面調和係数の最大展開次√
数 L は，⌈ Θ × Φ⌉ + 1 であれば十分である．

トを下げている．これらの研究は３次元モデルを対象とした形状が類似するモデルの検索手法であり，アセンブリモデルの同

3. 1. 2 提案手法（1D 投影）：類似度計算一モデル検索を目的とする本稿とは異なる．

特徴量から２つのアセンブリモデル間の距離を計算する手順

本研究では，アセンブリモデルの部品ごとに回転と平行移動を図 3，図 4 に示す．また，２つのアセンブリモデルの部品間のについて不変な特徴量を構成することによって，アセンブリモ

距離を計算する手順を Algorithm 3 に示す．アセンブリモデル

デルを対象とする形状・内部構造どちらも考慮した同一モデルの特徴量は３次元配列であり，部品ごとの特徴量である２次元検索に関する球面調和関数に基づいた手法を提案する．この際，配列をまとめたもので表される．部品同士の距離はそれぞれの多視点レンダリングによる特徴集合を球面調和変換によって一特徴量のユークリッド距離で表す．２つのアセンブリモデルのつの特徴量に統合することで類似度計算の計算コストを削減す

距離を求めるには，始めに，図 3 にあるように，それぞれの部

るが，同様の手法の研究はこれまでなされていない．

1D Projection

DFT…

Focus onone component

Align to a 2-dimensional
array of 𝒂𝒏𝒈𝒍𝒆 × 𝒇𝒓𝒆𝒒𝒖𝒆𝒏𝒄𝒚

summarize

Feature of thecomponent focused

SHT each row
and calculate norms

図 2: 提案手法（1D 投影）：アセンブリモデルの部品から特徴量を得る手順

Algorithm 1 ComputeFeature1D(s, R, Θ, Φ, N, L)

Algorithm 2 ComputeWeighted1DProjection(s, R, Θ, Φ)Input: アセンブリモデル m，アセンブリモデルの部品 s，原点からInput: アセンブリモデル m，アセンブリモデルの部品 s，１次元投の距離 R，極角 Θ，方位角 Φ，離散フーリエ係数の最高周波数を影のサイズ R，極角 Θ，方位角 Φ

指定する正の整数 N ，球面調和係数の最大次数を指定する 0 以上

Output: s の重み付け１次元投影の結果 pの整数 L

1: サイズ R × Θ × Φ の３次元配列 p を初期化する

Output: s の特徴量 sfp

2: S(m) ← m の部品の集合

1: p ← ComputeWeighted1DProjection(m, s, R, Θ, Φ)

3: for all (θ, ϕ) ∈ Θ × Φ do

2: サイズ Θ × Φ × N の３次元配列 fp を初期化する

4:vs ← 0

3: for each (θ, ϕ) ∈ Θ × Φ do

5:v S(m)\s ← 0
for all r ∈ R do

4:p(r, θ, ϕ) を r 方向に離散フーリエ変換する

6:5:

周波数 n = 0, . . . , N − 1 についての振幅スペクトルを３次元配7:(r, θ, ϕ) で定義された平面による，部品 s の断面積 a(s, r) と

6: end for8:v s ← v s + a(s, r)

7: サイズ N × L の２次元配列 sfp を初期化する

9:v S(m)\s ← v S(m)\s + a(S(m)\s, r)

8: for n = 1 to N do

列 fp(θ, ϕ, n) に格納する

他の部品 S(m)\s の断面積 a(S(m)\s, r) を求める

10:

end for9:fp(θ, ϕ, n) を次数 0 to L の範囲で球面調和変換する

11:

for all r ∈ R do

10:

球面調和係数の次数ごとのノルムの合計を求めて，２次元配列

12:p(r, θ, ϕ) ←sfp(n, l) に格納する（l = 0, . . . , L and n = 0, . . . , N − 1）13:a(s,r)a(S(m))\s,r+
vsv S(m)\s

end for

11: end for

14: end for

12: return sfp(n, l)

15: return p

品の間のユークリッド距離をすべて調べる．そして，得られた部品間の距離の行列から，ユークリッド距離の合計が最小になる組み合わせを求める．本稿では，最適な組み合わせを求める
ために Munkres の割り当てアルゴリズム（ハンガリー法）[12]を利用した．最後に，図 4 にあるように，その組み合わせの合計値を２つのアセンブリモデルの距離とする．また，類似度は距離の逆数とする．

3. 2 提案手法（2D 投影）

図 3: ２つのアセンブリモデルの特徴量比較

提案手法（2D 投影）では，３次元モデルの２次元投影から特徴量を構成し，その特徴量をもとに同一モデル検索を行う．
全体の特徴量抽出の手順は提案手法（1D 投影）と似ているが，投影からモデルの姿勢変化について不変な特徴を得るための処理が異なっている．提案手法（2D 投影）では，２次元投影計

算，２次元ラドン変換，離散フーリエ変換，球面調和変換を用いて回転と平行移動に不変なアセンブリモデルの特徴量を構築する．

処理の直前の形と同じであり，提案手法（1D 投影）と同様に
球面調和変換による特徴量の統合ができる．したがって，以降
は提案手法（1D 投影）と同様の手順で，最終的な部品の特徴量を得る．
図 4: 部品間の距離から２つのアセンブリモデルの距離を求める

Algorithm 4 ComputeFeature2D(s, R, Θ, Φ, N, L)
Input: アセンブリモデル m，アセンブリモデルの部品 s，投影のサ
イズ R，極角 Θ，方位角 Φ，離散フーリエ係数の最高周波数を指Algorithm 3 ComputeDistance(md , mq , R, Θ, Φ, N, L)
Input:

定する正の整数 N ，球面調和係数の最大次数を指定する 0 以上の整数 L，２次元ラドン変換の角度 A

データベースモデル md ，クエリモデル mq ，原点からの距離

R，極角 Θ，方位角 Φ，離散フーリエ係数の最高周波数を指定する
正の整数 N ，球面調和係数の最大次数を指定する 0 以上の整数 L

Output: s の特徴量 smﬀrp
1: for each (θ, ϕ) ∈ Θ × Φ do

Output: md と mq の各部品間の距離 sd

2:

p(θ, ϕ) ← ComputeWeighted2DProjection(m, s, R, θ, ϕ)

1: S(md ) ← md の部品の集合

3:for each ak ∈ A （k = 1, . . . , |A|） do

2: S(mq ) ← mq の部品の集合

4:

3: if |S(md )| = |S(mq )| then5:

end forrp(θ, ϕ, k, R) ← p(θ, ϕ) の角度 ak の直線への１次元投影

4:

サイズ |S(md )| × |S(mq )| の配列 sd を初期化する

6:

rp(θ, ϕ, k, R) を R 方向に離散フーリエ変換する

5:

for all sdi ∈ S(md ) do

7:

周波数 n = 0, . . . , N − 1 についての振幅スペクトルを４次元配sfp[sdi ] ← ComputeF eature1D/2D(sdi , R, Θ, Φ, N, L)

6:

列 frp(θ, ϕ, k, n) に格納する

7:

end for

8:

8:

9:

9:

for all sqj ∈ S(mq ) do
sfp[sqj ] ← ComputeF eature1D/2D(sqj , R, Θ, Φ, N, L)

10:

end for10:

11:

for all (sdi , sqj ) ∈ S(md ) × S(mq ) do

frp(θ, ϕ, k, n) を k 方向に離散フーリエ変換する
周波数 n = 0, . . . , N − 1 についての振幅スペクトルを４次元配列 ﬀrp(θ, ϕ, n, n) に格納する

ﬀrp(θ, ϕ, n, n) を３次元配列 mﬀrp(θ, ϕ, Z) に成形する (z =0, . . . , N 2 − 1）12:sd(sdi , sqj ) ← 0

11: end for13:

for all (n, l) ∈ N × L do

12: サイズ Z × L の２次元配列 smﬀrp を初期化する

sd(sdi , sqj ) ← sd(sdi , sqj ) + ||sfp[sdi ](n, l) − sfp[sqj ](n, l)||14:

end for15:
16:

end for

13: for z = 1 to |Z| do
14:mﬀrp(θ, ϕ, z) を次数 0 to L の範囲で球面調和変換する

15:

球面調和係数の次数ごとのノルムの合計を求めて，２次元配列

smﬀrp(z, l) に格納する（l = 0, . . . , L and z = 0, . . . , Z − 1）

17: else
18:

サイズ |S(md )| × |S(mq )| の配列 sd の各要素を ∞ で初期化

16: end forする

17: return smﬀrp(z, l)

19: end if
20: return sd

Algorithm 5 ComputeWeighted2DProjection(m, s, R, Θ, Φ)
3. 2. 1 提案手法（2D 投影）：特徴量の抽出

Input: アセンブリモデル m, アセンブリモデルの部品 s，投影のサイ
ズ R，極角 Θ，方位角 Φ

提案手法 (2D 投影) によってアセンブリモデルの部品から特徴量を得る手順を図 5 に示す．また，特徴量の抽出の手順を

Algorithm 4 に示し，重み付け２次元投影の作成手順を Algorithm 5 に示す．図 5 より，アセンブリモデルを構成する部品ごとに以下の手順で特徴量を計算する．まず，モデルの周囲か

Output: s の重み付け２次元投影の結果 p
1: サイズ R × R × Θ × Φ の４次元配列 p を初期化する
2: S(m) ← m の部品の集合
3: for all (θ, ϕ) ∈ Θ × Φ do4:

vs ← 05:v S(m)\s ← 0

元ラドン変換を行うことで，動径方向 × 角度方向の２次元配6:

for all r ∈ R do

列に変換する．得られた２次元配列について，動径方向に離散7:ら重み付け２次元投影を作成する．次に，各２次元投影に２次品 S(m)\s の投影画像 a(S(m)\s, r) を求める

フーリエ変換を行い振幅スペクトルを得ることで，元々のモデルの平行移動に不変な特徴が得られる．続けて，角度方向に離散フーリエ変換を行い振幅スペクトルを得ることで，２次元投影の面内における回転と平行移動について不変な特徴が得られ

角度 (θ, ϕ) の平面への，部品 s の投影画像 a(s, r) と他の部

8:v s ← v s + a(s, r)

9:v S(m)\s ← v S(m)\s + a(S(m)\s, r)

10:

end for11:

for all r ∈ R do

る．ここまでの手順で，投影角度ごとに元々のモデルの回転と12:平行移動について不変な２次元配列特徴量が得られたことにな

13:る．ここで，投影角度ごとの２次元配列特徴量を１列に並べて

14: end for

１次元配列にすると，それぞれの投影角度 × 周波数の２次元行

15: return p

列になる．これは提案手法（1D 投影）の球面調和変換による

a(s,r)p(r, r, θ, ϕ) ← sum(vs ) +end fora(S(m))\s,rsum(v S(m)\s )2D Projection

DFT

Radon
transform…

Focus onone component

Align to a 2-dimensional
array of 𝒂𝒏𝒈𝒍𝒆 × 𝒇𝒓𝒆𝒒𝒖𝒆𝒏𝒄𝒚

SHT each row
and calculate norms

summarize

Feature of thecomponent focused

図 5: 提案手法（2D 投影）：アセンブリモデルの部品から特徴量を得る手順

3. 2. 2 提案手法（2D 投影）：類似度計算提案手法（2D 投影）のアセンブリモデル間の距離の計算手••

メモリ (RAM)：32.0 GB
ソフトウェア：MATLAB 2018b

法は提案手法（1D 投影）の場合と同様であり, Algorithm3 の処理に従う．

4 評価実験
我々は，提案手法について，部品の配置が異なる３次元 CAD
アセンブリモデルを用いて実験的評価する．本稿の評価実験では，図 6 に示す 15 種類の３次元アセンブリモデルを使用する．
これらは GrabCAD [13] から選んだモデルと，それらを複数結

図 6: 使用したアセンブリモデル

合したモデルである．ただし，簡素化のためにいくつかの部品を除外する．15 種類のアセンブリモデルのそれぞれについて，
部品配置が異なるタイプ１からタイプ 5 までを用意する．図 7
では Pump モデルを例に示している．使用されている部品の種類が異なることを色の違いで表現しており，図 7 の (a)〜(e)は，全体の形状，使用されている部品の形や個数は同じである
が，互いに異なる部品配置になっている．これら，15 種類 ×5タイプの 75 個のモデルをデータベースモデルとする．ただし，データベースモデルにはランダムに回転と平行移動を加える．

図 7: 部品のレイアウトが異なるアセンブリモデルの例

また，各アセンブリモデルのタイプ 1 をクエリモデルとする．
実験の際には，データベースモデルと同様にランダムに回転と平行移動を加える．先行研究での投影枚数は Geodesic Dome

4. 1 類似モデルの識別確認実験の頂点数によって決まるため，投影枚数は 12 枚，42 枚，92 枚，提案手法（1D 投影）によって同一モデル検索を行い，各ク

162 枚，252 枚，362 枚，492 枚のいずれかとする．提案手法

エリモデルと各データベースモデルとの類似度を評価する．投での投影枚数は球面直交座標によって決まるため，投影枚数は影枚数を 364((|Θ|, |Φ|) = (13, 28)) として同一モデル検索を行12(= 3×4) 枚，45(= 5×9) 枚，91(= 7×13) 枚，162(= 9×18)

う．そのときの実験結果を図 8 に示す．図 8 は，クエリモデル

枚，253(= 11 × 23) 枚，364(= 13 × 28) 枚，495(= 15 × 33)

である 15 種類のアセンブリモデルとデータベースである 75 個

枚のいずれかとする．投影のサイズである Algorithm1 におけとの類似度を示している．正解モデルは各モデルのタイプ１でる |R| は 96 とし，Algorithm4 における |R| は 96 とする．本

あり，各折れ線上に赤い菱形で示している．図 8 より，各クエ

稿の評価実験に使用した PC 環境は以下の通りである．

リモデルについてそれぞれの正解モデルとの類似度が最も高い．

•
•

TM
R
CPU: Intel⃝Core
i7-7700K @4.20 GHz
OS：Windows10 Education 64 bit

また，クエリモデルと同じ種類のモデルとの類似度より他の種類のモデルとの類似度が高い場合もない．この結果から，我々

図 8: クエリモデルとデータベースとの類似度の提案手法は形状の違いを識別できており，内部構造の異なるモデルも識別できていることが分かる．

4. 2 先行研究との処理時間の比較実験
先行研究と提案手法（1D 投影），提案手法（2D 投影）について，投影枚数を変化させたときの，クエリモデル１つあたりの同一モデル検索にかかる処理時間を比較する．投影枚数を変化させたときの，先行研究と提案手法（1D 投影），提案手法（2D 投影）の処理時間の変化を図 9 に示す．先行研究の問題
点は，アセンブリモデル間の類似度計算においての総当たり計
算による視点の対応付けが必要であり，その分処理時間が長くなってしまう点である．図 9 より，投影枚数が 91 枚以上の場
合は提案手法２種の方が全体の処理時間が短いことが分かる．
提案手法２種は先行研究に比べ，類似度計算にかかる時間が最
大 50%削減されている．また，全体の処理時間は最大 31%削減されている．この結果から提案手法は先行研究の問題点を解消できたと言える．しかし投影枚数が 91 枚より少ない場合は先行研究の方が全体の処理時間が短い．これは，投影枚数が小さい場合は，総当たり計算による視点の対応付けにかかる計算コ
ストが小さいためだと考えられる．提案手法（1D 投影) と提案手法（2D 投影）の処理時間はほとんど変わらなかったが，提案手法（2D 投影）の方が特徴量計算にかかる時間が若干長い．

4. 3 先行研究との特徴量のサイズの比較実験
先行研究と提案手法（1D 投影），提案手法（2D 投影）について，部品１つあたりの特徴量のサイズと正答率の関係を評価する．投影枚数を変化させたときの部品１つあたりの特徴量のサイズと正答率の関係を図 10 に示す．横軸は対数軸である．図10 より，提案手法（1D 投影）と提案手法（2D 投影）の特徴量のサイズは近い値である．これは，特徴量抽出における球面調
和変換の処理で，最大展開次数が投影枚数に応じて決まるためである．そのため，投影枚数が同じであり投影のサイズも同じであるならば，特徴量のサイズも同じになる．図 10 より，提案手法２種は，先行研究と比較して約 100 分の 1 のサイズの特徴量で同一モデル検索が可能である．Alrorithm4 での表記を√流用すると，先行研究での特徴量のサイズは 2|N | × |A| ×「投影枚数」と表され，提案手法での特徴量のサイズは |L| × |N |と表される．また，球面調和係数の最大次数 L は，２次元球√

面上のサンプリング定理 [11] に従い，⌈ 「投影枚数」⌉ + 1 である．したがって，投影枚数を M ，投影のサイズを R としたときの特徴量のサイズのオーダーは，先行研究は O(M × R)，提√案手法２種では O( M × R) となる．このことからも，投影枚数の増加による特徴量のサイズの増加は，提案手法２種の方が先行研究よりも緩やかであることが言える．

これは，投影視点ごとに２次元投影の２次元ラドン変換を行うなど，提案手法（1D 投影) よりも特徴超量抽出にかかる処理が多いためだと考えられる．

図 10: 投影枚数を変化させたときの部品１つあたりの特徴量のサイズと正答率の関係
図 9: 投影枚数を変化させたときの処理時間の変化．横軸の括
弧の中身は投影枚数（P：先行研究（Previous），1D：提案手法（1D 投影），2D：提案手法（2D 投影））

4. 4 手法ごとの正答率の比較実験
先行研究と提案手法 (1D 投影)，提案手法（2D 投影）について，投影枚数を変化させたときの同一モデル検索の正答率を評価する．また，手法ごとの処理時間あたりの正答率を評価する．

投影枚数を変化させたときの手法ごとの正答率の変化を図 11

体の処理時間が最大 31%削減された．また，先行研究と比較しに示す．手法ごとのクエリ 1 件あたりの同一モデル検索にかかて約 100 分の 1 のサイズの特徴量で同一モデル検索が可能とる処理時間と正答率の関係を図 12 に示す．

なった．

図 11 より，いずれの手法も投影枚数を増やすほど正答率が今後は，投影枚数が少ない場合でも，より高い正答率が得ら100%に近づき，先行研究では投影枚数 362 枚のときに初めてれる手法を考案することができればより柔軟なアセンブリモ

正答率が 100%になり，提案手法（1D 投影）と提案手法（2D

デル検索ができるようになると考えられる．また，提案手法に投影）では投影枚数 364 枚 ((|Θ|, |Φ|) = (13, 28)) のときに初より特徴量のサイズが小さくなったことによって扱えるようにめて正答率が 100%になった．投影枚数が小さい場合は提案手なった，より複雑で巨大なアセンブリモデルの検索についての

法２種は先行研究よりも正答率が下回っている．これは，投影研究や，ほかの多視点レンダリング手法への提案手法の転用に

枚数の削減により角度方向の空間分解能が下がり，提案手法でついて考察したい．

球面調和変換する際に角度方向のエイリアシングが発生しているためと思われる．角度方向のエイリアシングを防ぐには元々のモデルの角度方向の複雑さ（周波数）に応じて投影枚数を増やすことが必要である．
また，図 12 より，提案手法２種はクエリ１件にかかる処理
時間あたりの正答率は先行研究に近い値を取っており，クエリ
１件にかかる処理時間が 20 秒以上の場合では先行研究の 90%以上の正答率を出せている．

図 11: 投影枚数を変化させたときの手法ごとの正答率

図 12: 手法ごとのクエリ 1 件あたりの同一モデル検索にかかる処理時間と正答率の関係

5 結論と今後の課題
本稿では，球面調和変換を用いて部品の対応関係が未知であるような３次元アセンブリモデルの形状・内部構造を考慮した同一モデル検索を提案した．アセンブリモデルを部品ごとに分け，それぞれ多視点レンダリングして投影を得る．１次元投影の場合は動径方向に離散フーリエ変換を，２次元投影の場合は２次元ラドン変換と離散フーリエ変換を，それぞれ使用することによって，投影視点ごとに対応した元々のモデルの平行移動に不変な特量が得られる．こうして得た特徴の集合を角度方向の各列ごとに球面調和変換を用いてノルムを求めることで，１つの特徴量に統合する．この手法により，先行研究と比較して，類似度計算の処理時間が最大 50%削減され，同一モデル検索全文

献[1] Tangelder, J. W. H. and Veltkamp, R. C. (2008) A survey ofcontent 3d shape retrieval methods, Multimedia Tools andApplications, Vol. 39, No. 3, pp. 441-471.
[2] Katayama, K. and Sato T. (2017) A Matching Method for
3D CAD Models with Diﬀerent Assembly Structures Using
Projections of Weighted Components, Journal of Information Processing, Vol. 25, pp. 376-385.
[3] Chen, D.-Y. and Tian, X.-P. and Shen, Y.-T. and Ouhyoung, M. (2003) On Visual Similarity Based 3D Model Retrieval, Computer Graphics Forum, Vol. 22, pp. 223-232.
[4] Knopp, J. and Prasad, M. and Willems, G. and Timofte, R.
and Van Gool, L. (2010) Hough Transform and 3D SURF
for Robust Three Dimensional Classiﬁcation, Proceedings ofthe 11th European Conference on Computer Vision: PartVI, pp. 589-602.
[5] Kazhdan, M. and Funkhouser, T. and Rusinkiewicz,
S. (2003) Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors, Proceedings ofthe 2003 Eurographics/ACM SIGGRAPH Symposium
on Geometry Processing, , SGP ’03, pp. 156-164,
http://dl.acm.org/citation.cfm?id=882370.882392.
[6] Papadakis, P. and Pratikakis, I. and Theoharis, T. andPassalis, G. and Perantonis, S. (2008) 3D Object Retrieval using an Eﬃcient and Compact Hybrid Shape
Descriptor. Proceedings of the 1st Eurographics Conference on 3D Object Retrieval, 3DOR ’08, pp. 9-16,
http://dx.doi.org/10.2312/3DOR/3DOR08/009-016.
[7] Deshmukh, A. S. and Banerjee, A. G. and Gupta, S. K. andSriram, R. D. (2008) Content-based assembly search: A step
towards assembly reuse, Computer-Aided Design, Vol. 40,
No. 2, pp. 244–261, http://dx.doi.org/10.1016/j.cad.2007.10.012.
[8] Hu, K.-M. and Wang, B. and Yong, J.-H. and Paul, J.-C.
(2013) Relaxed lightweight assembly retrieval using vector
space model, Computer-Aided Design, Vol. 45, No. 3, pp.
739-750.
[9] Ansary, T. F. and Daoudi, M. and Vandeborre, J.-P. (2007)
A Bayesian 3-D Search Engine Using Adaptive Views Clustering, IEEE Transactions on Multimedia, vol. 9, No. 1,
pp.78-88. https://hal.archives-ouvertes.fr/hal-00666134.
[10] Furuya, T. and Ohbuchi, R. (2009) Dense Sampling andFast Encoding for 3D Model Retrieval Using Bag-of-Visual
Features. Proceedings of the ACM International Conference
on Image and Video Retrieval, CIVR ’09, No. 8, pp. 26:126:8, http://doi.acm.org/10.1145/1646396.1646430.
[11] Driscoll, J. R. and Healy, D. M. (1994) Computing Fourier Transforms and Convolutions on the 2Sphere, Adv. Appl. Math., Vol. 15, No. 2, pp. 202-250,
http://dx.doi.org/10.1006/aama.1994.1008.
[12] Munkres, J. R. (1957) Algorithms for The Assignment andTransportation Problems, Journal of the Society for Industrial and Applied Mathematics, Vol. 5, No. 1, pp.32-38.
[13] GrabCAD, http://www.grabcad.com.