Comments
Description
Transcript
3次元アセンブリモデルデータベースに対する 索引構造の提案とその評価
DEIM Forum 2015 F2-4 ３次元アセンブリモデルデータベースに対する 索引構造の提案とその評価 佐藤 拓実† 片山 薫 † † 首都大学東京大学院 システムデザイン研究科 情報通信システム学域 E-mail: †[email protected], ††[email protected] あらまし 近年、製造業などでは３次元 CAD を用いたモデル設計が行われている。機械設計などの分野では複数の 部品の組み合わせによって１つのアセンブリモデルが設計されていることが多く、３次元アセンブリモデルのデータ 量は年々増加している。このような大量の３次元アセンブリモデルを効率よく管理するためには、３次元アセンブリ モデルの形状や内部構造はもちろん、アセンブリモデルの各部品の配置や部品に使用されている材料まで識別する検 索手法が必要となる。しかし、このような点はこれまであまり考慮されなかった。以前、我々はアセンブリモデルの 部品の配置や材料などを識別する３次元モデル検索方法として複数の視点からの投影画像を用いた３次元モデル検索 を提案した。これはモデル間の類似度を複数の投影画像間の類似度から算出する手法である。しかし、すべての投影 画像間の類似度を計算するには時間を要する。そこで、本稿では投影画像を形状ごとに分類し、階層構造にすること で有用な類似度のみを計算することで検索を効率化する方法を提案する。また、３次元 CAD モデルを用いて提案手 法を実験的に評価した。 キーワード ３次元モデル，投影画像，アセンブリ構造，データ構造 1. は じ め に 近年、製造業などでは３次元ＣＡＤを用いたモデル設計が行 ごとに分類し、階層構造にすることでモデル間の類似度算出に 必要な類似度のみを計算する効率的な検索を可能にした。また、 ３次元ＣＡＤモデルを用いて、提案手法を実験的に評価した。 われており、３次元ＣＡＤモデルのデータ量は年々増加してい さらに、従来の投影を用いたモデル検索の手法と比較し、提案 る。大量の３次元モデルを効率よく管理するためには、３次元 手法の有効性を示す。 モデルの形状や内部構造などの情報に基づいた３次元モデルの 検索が必要となる。検索ができれば、既存の３次元モデルを再 利用することができるため、効率的なモデル設計が可能となる。 2. 関 連 研 究 ３次元モデルの形状をもとにした検索はこれまで数多く提 これまで、３次元モデルの検索としてモデルの形状をもとに 案されている [1]。Chen ら [2] は、３次元モデルを”Light Field 検索をする手法 [1] が多く研究されてきたが、機械設計などの Descriptor（LFD）”という特徴量から形状検索を行う方法を提 分野では複数の部品の組合わせによって１つのアセンブリモデ 案した。LFD は３次元モデルを複数の方向からレンダリングし、 ルが設計されていることが多く、このようなモデルに対しては 得られたシルエット画像を用いている。立間ら [3] は、”Multi- 従来の形状をもとにした検索手法では十分とはいえない。この Fourier spectra descriptor” と呼ばれる４種類のフーリエスペ ような複数の部品の組合わせによって構成されるアセンブリモ クトルを用いた形状検索の手法を提案している。 デルを対象とした検索を行うには、アセンブリモデルの内部構 しかし、３次元モデルの内部構造や材料情報、部品の配置の 造や部品に使用されている材料をもとにした検索、特に、各構 識別を目的とした検索法はあまり研究されていない。Zarpalas 成部品の配置まで識別して検索するような手法が必要となる ら [4] は、”Spherical Trace Transform” というモデルの内部 が、そのような検索手法はほとんど研究されていない。 構造を反映した特徴量をもとにした検索手法を提案している。 以前、我々は３次元モデルの形状や内部構造に加え、部品の Deshmukh ら [5] はモデルの構成部品を頂点としたグラフに変 配置やモデルの構成部品に使用されている材料の情報を識別す 換し、グラフ検索を行うことで、モデルの内部構造を識別する る検索方法を提案した。これは３次元モデルの内部構造の情報 モデル検索を提案している。構成部品間の関係をもとに、頂点 を含んだ特徴量として投影画像を用い、投影画像間の類似度か 間に枝をはる。Chen ら [6] もモデルを幾何学的な情報や意味的 らモデル間の類似度を計算する手法である。投影画像間の類似 情報に基づいてグラフに変換し、グラフをもとにした検索法を 度はラドン変換を用いた位相限定相関法により算出し、３次元 提案している。Hu ら [7] は３次元アセンブリモデルを部品ごと モデルを複数の方向から投影することで姿勢変化に頑強な検索 に分解し、LFD を特徴量として用いている。彼らの検索はモ が可能となる。しかし、各モデルの投影画像間の類似度をすべ デルの内部構造の識別を目的としており、部品の配置や材料情 て計算するのには時間を要する。そこで、本稿では３次元モデ 報の識別は行っていないため、我々の研究目的とは異なる。 ルの投影画像群に対する索引構造を提案する。投影画像を形状 また、我々は画像間の類似度をもとにモデル間の類似度を算 出している。画像間の類似度計算の手法は数多く研究されてい るが、我々はラドン変換を用いた類似度計算を提案手法に用い た。ラドン変換を用いた画像間の類似度計算の方法として、長 谷川ら [8] の手法がある。彼らは画像をラドン変換し、振幅成分 を取り出すことで幾何学的変化に不変な類似度計算を可能にし ている。また、取り出した振幅成分を対数変換することによっ て、画像内の物体のスケール変化にも不変な類似度計算を実現 した。 3. 準 備 3. 1 ラドン変換 N1 × N2 ピクセルの画像 f (n1 , n2 ) が与えられたとする。 こ こ で 、画 像 の イ ン デック ス を n1 = −M1 , ..., M1 お よ び 図 1: ２次元画像のラドン変換 n2 = −M2 , ..., M1 とし、N1 = 2M1 + 1 および N2 = 2M2 + 1 とする。このとき、画像 f (n1 , n2 ) のラドン変換 Rf (s, θ) は、 物体の平行移動はラドン変換 Rg (s, θ) の動径方向 s に変換さ 図 1 のような動径方向 s と投影方向 t を用いて次のように表さ れ、偏角 θ によって動径方向の移動量が変化する。物体の回転 れる。 はラドン変換 Rg (s, θ) の偏角方向 θ に変換される。 T ∑ Rf (s, θ) = RT (f (n1 , n2 )) = ここでは、便宜上、画像の大きさ N1 および N2 を奇数とし fRT (s, t) (1) t=−T √ 2 2 （注 1） 2) ⌉ である。また、ここでは画像 S = T = ⌈ (N1 ) +(N 2 f (n1 , n2 ) のラドン変換において、画像の範囲を越えるインデッ クスについてはすべて 0 として計算する。すなわち、 f( s, t) fRT (s, t) = 0 たが、これは必須ではない。 3. 2 振幅スペクトル １次元信号 f (n) を δ0 だけシフトさせた信号 g(n) の離散フー リエ変換 G(k) は次のように表される。 G(k) = F [g(n)] (−M1 < =s< = M1 , −M2 < =t< = M2 ) = N −1 ∑ 2π f (n − δ0 )e−i N kn n=0 (otherwise) (2) 2π = e−i N kδ0 N −1 ∑ 2π f (n)e−i N kn (6) n=0 としてラドン変換を行う。 振幅スペクトルのみを取り出すと次のようになる。 また、(s, t) 座標は (n1 , n2 ) 座標を θ だけ回転した座標なので ( ) s t ( = cosθ −sinθ sinθ )( ) n1 cosθ n2 2π (3) |G(k)| = |e−i N kδ0 || N −1 ∑ 2π f (n)e−i N kn | = |F (k)| (7) n=0 ここで、F (k) は信号 f (n) のフーリエ変換を表す。したがっ となる。したがって、ラドン変換 Rf (s, θ) は画像の回転と１方 向の和によって計算できる。 消えるため、平行移動に不変な特徴量となる。 画像 f (n1 , n2 ) 内の物体を δ1 , δ2 だけ平行移動した画像を g(n1 , n2 ) とすると、g(n1 , n2 ) のラドン変換 Rg (s, θ) は次のよ うに変換される。 3. 3 位相限定相関法 N1 × N2 ピクセルの２つの画像 f (n1 , n2 ), g(n1 , n2 ) が与え られたとき、それぞれの画像の２次元離散フーリエ変換を次の Rg (s, θ) = RT (f (n1 − δ1 , n2 − δ2 )) = Rf (s − δ1 cosθ − δ2 sinθ, θ) て、信号の振幅スペクトルを取り出すと信号のシフト量 δ0 が ように表される。 (4) F (k1 , k2 ) = ∑ k1 n1 k2 n2 f (n1 , n2 )WN WN 1 2 (8) n1 ,n2 また、画像 f (n1 , n2 ) 内の物体を ϕ0 だけ回転させた画像を h(n1 , n2 ) とすると、h(n1 , n2 ) のラドン変換 Rh (s, θ) は次のよ うに変換される。 G(k1 , k2 ) = (5) ただし、fpolar (s, θ) は f (n1 , n2 ) を極座標変換したものである。 （注 1）：⌈X⌉ は数値 X の切り上げを表す。 ∑ (9) k1 n1 k2 n2 g(n1 , n2 )WN WN 1 2 (10) n1 ,n2 Rh (s, θ) = RT (fpolar (s, θ − ϕ0 )) = Rf (s, (θ − ϕ0 )) = |F (k1 , k2 )|eiθF (k1 ,k2 ) = |G(k1 , k2 )|eiθG (k1 ,k2 ) ここでは回転子を WN1 = e −j 2π N1 、WN2 = e (11) −j 2π N2 と定義す る。|F (k1 , k2 )| および |G(k1 , k2 )| は振幅スペクトルを表し、 θF (k1 , k2 ) および θG (k1 , k2 ) は位相スペクトルを表す。また、 g1 g2 図 2: グラフの例 ∑ n1 ,n2 は ∑N1 −1 ∑N2 −1 n2 =0 n1 =0 を表す。 このとき、F (k1 , k2 ) と 図 3: ３次元モデルの偏角 (θ, ϕ) 方向への投影 G(k1 , k2 ) の正規化相互パワースペクトル C(k1 , k2 ) を次のよう に与える。 4. 提 案 手 法 C(k1 , k2 ) = F (k1 , k2 )G(k1 , k2 ) (12) |F (k1 , k2 )G(k1 , k2 )| = ei(θF (k1 ,k2 )−θG (k1 ,k2 )) (13) 4. 1 ３次元モデルの投影 本稿では、３次元ＣＡＤモデルを３次元ボクセルモデルに変 換してモデル検索を行う。３次元ボクセルモデルの各部品に使 G(k1 , k2 ) は G(k1 , k2 ) の複素共役を表す。次に、位相限定相 用されている材料に基づいた数値を振ることで、各部品の材料 関関数（POC 関数）c(n1 , n2 ) を正規化相互パワースペクトル 情報を反映した３次元モデルを生成する。また、３次元モデル C(u, v) の２次元離散逆フーリエ変換として定義する。 の内部情報や部品に使用されている材料などの情報を反映した ∑ 1 −k1 n1 −k2 n2 C(k1 , k2 )WN WN c(n1 , n2 ) = 1 2 N1 N2 (14) 数の方向から投影を行い、複数枚の投影画像を生成する。 k1 ,k2 ∑ ∑ 1 −1 ∑N2 −1 ここで、 k1 ,k2 は N k2 =0 を表す。 ２つの画像が類 k1 =0 似している場合、POC 関数はデルタ関数に近い鋭いピークを もつ。この相関ピークの高さは２つの画像の類似度の尺度とし て有用である。また、g(n1 , n2 ) が f (n1 , n2 ) を (δ1, δ2 ) だけ平 行移動させた画像ならば、POC 関数は c(δ1 , δ2 ) に相関ピーク をもつ。すなわち、位相限定相関法によって画像内の物体の平 行移動量を検知することができる。したがって、位相限定相関 法は画像内の物体の平行移動に不変となる特徴がある。 3. 4 隣 接 行 列 隣接行列はグラフの頂点のつながりを 0 と 1 を用いて表現す る。ある頂点 v と w の間に枝があれば、隣接行列の (v, w) 成 分および (w, v) 成分が 1 となり、枝がない場合は 0 となる。次 に隣接行列の例を示す。 ［例 3.1］ 行列 Ag1 , Ag2 は図 2 のグラフ g1 , g2 をそれぞれ表 g1 A 0 1 = 1 0 0 1 1 0 0 0 0 1 , Ag2 0 1 0 0 0 0 = 0 とに決定している。 図 3 に３次元モデルの投影の様子を示す。 投影画像の各ピクセルは２つの偏角によって定まる直線の線積 分から算出される。すなわち、３次元ボクセルモデルの内部を 通過する直線上にあるすべてのボクセルの和となる。各ボクセ ルには材料の情報によって数値が振られているので、３次元モ デルの投影画像は内部構造および部品に使用されている材料を 反映した画像となる。また、より多くの方向から３次元モデル の投影画像を生成することで、３次元モデルの姿勢変化に頑強 な特徴量となるが、投影画像が多くなれば多くなるほど、モデ ル検索に時間がかかる。 そこで、本稿では球面座標系の２つの偏角 θ, ϕ を 0 < = θ < 360 ,0< = ϕ < 180 の範囲のすべての角度を用いるのではなく、範 囲内の中から一定の間隔で角度を選択し、選択した角度をもと に３次元ボクセルモデルの投影方向を決定する。例えば、20 ° 1 °...,340 °の 18 個の角度となり、偏角 ϕ は 0 °,20 °,40 °,...,160 °の 9 個の角度となる。この場合、偏角 θ, ϕ の角度の組み合わ 0 1 1 1 0 0 0 0 0 0 1 1 隣接行列は対称行列であり、図 2 の各頂点の番号は隣接行列 の各行および各列に対応している。また、隣接行列の (v, w) 成 分および (w, v) 成分が 1 のとき、頂点 v は頂点 w と隣接して いるという。例えば、図 2 の g1 の頂点 1 は頂点 2、頂点 3 と 隣接している。さらに、ある頂点の隣接している頂点の数をそ の頂点の次数という。図 2 の g1 の場合、頂点 1 の次数は 2 と なる。 ３次元モデルの投影方向は球面座標系の２つの偏角 θ, ϕ をも 間隔で２つの偏角 θ, ϕ を選択する場合、偏角 θ は 0 °,20 °,40 現する隣接行列である。 特徴として投影画像を用いる。１つの３次元モデルについて複 せは 162 あるので、偏角 θ, ϕ を 20 °間隔で選択したときの投 影画像は 162 枚となる。 4. 2 特 徴 量 本稿では、投影画像をラドン変換し、振幅成分を取り出したも のを特徴量としている。投影画像を f (n1 , n2 ) とし、f (n1 , n2 ) のラドン変換を Rf (s, θ) とする。また、f (n1 , n2 ) を δ1 , δ2 だ け平行移動させ、ϕ だけ回転させたものを g(n1 , n2 ) とすると、 g のラドン変換 Rg (s, θ) は f のラドン変換 Rf (s, θ) を用いて 次のように表すことができる。 Rg (s, θ) = Rf (s − δ1 cosθ − δ2 sinθ, θ − ϕ0 ) (15) Rg (s, θ) の動径方向 s にフーリエ変換し、振幅スペクトル （ 1 ） ３次元モデルデータベース内のすべてのモデルについて複 ARg (ω, θ) を取り出すと次のようになる。 数の方向から投影をとり、投影画像群 P を生成する。 ARg (ω, θ) = |F [Rg (s, θ)]| （ 2 ） 投影画像群 P の内、投影方向の異なるすべての投影画像間 の類似度をラドン変換を用いた位相限定相関法で算出する。 = |F [Rf (s − x0 cosθ − y0 sinθ, θ − ϕ0 )]| = ARf (ω, θ − ϕ0 ) (16) したがって、ラドン変換した投影画像を動径方向についてフー （ 3 ） 類似度を閾値で２値化し、閾値以上を 1、それ以外を 0 と することで投影画像間の関係を表す隣接行列をつくる。 リエ変換し、振幅スペクトルを取り出すことで、画像内の物体 （ 4 ） 隣接行列から各投影画像の次数を計算する。 の回転量をラドン変換の偏角方向の平行移動量として扱うこと （ 5 ） すべての投影画像がグループ分けされるまで以下の処理を ができ、また物体の平行移動に不変な特徴量ができる。 行う。 4. 3 投影画像間の類似度計算 N1 × N2 ピクセルの２つの投影画像 f (n1 , n2 ), g(n1 , n2 ) の （ a ） 投影画像群 P の中から最も次数の多い投影画像 p ∈ P を選択する。 類似度をラドン変換を用いた位相限定相関法をもとに計算す る。類似度計算の手順は次のとおりである。 （ 1 ） 投影画像 f (n1 , n2 ), g(n1 , n2 ) をそれぞれラドン変換し、 Rf (s, θ) と Rg (s, θ) を得る。 （ b ） 投影画像 p と隣接しているすべての投影画像を同じグ ループにし、グループの代表投影画像を p とする。 （ c ） 投影画像 p とグループ分けされた投影画像をすべて P から除外する。 （ 2 ） ラドン変換した投影画像 Rf (s, θ), Rg (s, θ) を動径方向に フーリエ変換し、振幅スペクトル ARf (ω, θ), ARg (ω, θ) を取り出す。 まず、３次元モデルデータベース内のすべてのモデルについ て複数の方向から投影をとり、投影画像群を生成する。生成し た投影画像群の内、投影方向の異なるすべての投影画像間の類 （ 3 ） ２つの振幅スペクトル ARf (ω, θ), ARg (ω, θ) について位 相限定相関法を用いて２つの投影画像間の類似度を計算 類似度を閾値をもって２値化することで、投影画像間の関係を する。 表す隣接行列をつくる。本稿では、閾値は 0.1 に固定した。こ Df (u, v) = ∑ ARf (ω, θ)WΩuω WΘvθ ω,θ Dg (u, v) = ∑ ∑ ω,θ は ∑Ω−1 ∑Θ−1 2π Ω 築する。隣接行列から各投影画像の次数を計算し、次数の多い 本稿では、ある投影画像 p と隣接しているすべての投影画像 を同じグループにする方法でグループ分けを行い、グループ代 1 ∑ Df (u, v)Dg (u, v) c(ω, θ) = WΩ−uω WΘ−vθ ΩΘ |D (u, v)D (u, v)| g f ω,θ ここで、 の投影画像の隣接行列をもとに投影画像に対する索引構造を構 投影画像から順に投影画像のグループ分けを行う。 ARg (ω, θ)WΩuω WΘvθ ω,θ e−j 似度をラドン変換を用いた位相限定相関法で算出する。さらに、 ω=0 θ=0 表投影画像を投影画像 p とした。グループの代表投影画像は データベース検索の際に探索グループを決定するために用い る。また、投影画像が複数のグループに重複して分けられない ように、グループ分けがされた投影画像はグループ分けの処理 を 表 し 、回 転 子 を WΩ = の対象から除外する。すべての投影画像がグループ分けされる 2π 、WΘ = e−j Θ と 定 義 す る 。本 稿 で は Θ = 180、 √ Ω = ⌈ (N1 )2 + (N2 )2 ⌉ とした。 まで処理を繰り返すことで、投影画像群に対する索引構造を構 投影画像をラドン変換し、振幅スペクトルを取り出すことで、 図 4 にグループ分けの例を示す。投影画像の隣接行列から各 築する。 画像内の物体の平行移動に不変となり、物体の回転がラドン変 頂点の次数を計算する。図 4 の場合、次数が最大となる頂点は 換の偏角方向に変換される特徴量となる。また、位相限定相関 頂点 5 であるから、頂点 5 をもとにグループ分けを行う。頂点 法は画像の平行移動に頑強であるため、２つの特徴量について 5 の投影画像と隣接しているすべての投影画像を同じグループ 位相限定相関法を用いて類似度を算出することで、投影画像内 にし、グループの代表投影画像を頂点 5 の投影画像とする。グ の物体の平行移動および回転に頑強な類似度計算を行うことが ループ分けがされた頂点をグループ分けの対象から外し、次に できる。本稿では、この類似度計算方法をラドン変換を用いた 多い次数の頂点を探す。グループ分けがされていない頂点の中 位相限定相関法と呼ぶ。 で最大の次数をもつ頂点は頂点 8 なので、頂点 8 をもとにグ 4. 4 投影画像群に対する索引構造 ループ分けし、グループ分けされた頂点をグループ分けの対象 本稿では、３次元モデルデータベースの投影画像をあらかじ から外す。残った頂点 3 は単独のグループとして扱う。図 4 の め形状ごとに分類し、投影画像を階層構造にする。投影画像の グループ分けの結果を図 5 に示す。グループの代表投影画像は 分類はラドン変換を用いた位相限定相関法によって算出された クエリ画像と最も類似しているグループを選択するときに用 類似度を用いて行う。投影画像に対する索引構造の構築手順は いる。 次のとおりである。 投影画像の隣接関係 頂点 5 をもとにグループ分け 頂点 8 をもとにグループ分け 頂点 3 をもとにグループ分け 図 4: グループ分けの例 図 5: 図 4 のグループ分けの結果 4. 5 データベース検索 本稿では、３次元モデルデータベースの各モデルの投影画像 を生成し、投影画像に対する索引構造を構築する。索引構造を 図 6: ３次元モデルデータベース検索の流れ 構築することで、効率的な３次元モデルデータベースの検索 を行う。クエリモデルが与えられたときの３次元モデルデータ ベース内のモデル検索の流れは次の通りである（図 6）。ただ し、データベースの投影画像はあらかじめ索引構造を構築して 像群のすべての投影画像とデータベース内の投影画像との類似 度を計算し、クエリモデルの投影画像と最も類似している投影 画像を探し出す。まず、クエリモデルの投影画像群の中から投 おく。 影画像を選択し、クエリ投影画像とする。次に、クエリ投影画 （ 1 ） クエリモデルを複数の方向から投影し、投影画像群を生成 する。 （ 2 ） クエリモデルの投影画像群のすべての投影画像について以 下の処理を行う。 像とデータベース内の各グループの代表投影画像との類似度を 計算する。算出された類似度の内、最も高い類似度をもつ代表 投影画像のグループを次に探索すべきグループとして選択す る。次に、選択された探索グループのすべての投影画像とクエ リ投影画像との類似度を計算する。算出された類似度の内、最 （ a ） データベースの各グループの代表投影画像とクエリモ 大の類似度をもつ投影画像をクエリ画像と最も類似した投影画 デルの投影画像との類似度をラドン変換を用いた位相 像として選択する。最後に、選択された投影画像をもつデータ 限定相関法によって算出し、各グループの代表投影画 ベース内のモデルに１票を入れる。この処理をクエリモデルの 像の中で最も類似度の高い代表投影画像のグループを すべての投影画像について行う。すなわち、提案手法はクエリ 選択する。 モデルの投影画像の数を全票数とした投票形式でデータベース （ b ） 選択したグループのすべての投影画像とクエリモデル 内のモデルの類似度を測る。 の投影画像との類似度をラドン変換を用いた位相限定 相関法によって算出し、最も高い類似度をもつ投影画 像を選択する。 （ c ） 選択された投影画像をもつデータベース内のモデルに １票を入れる。 （ 3 ） データベースのモデルのうち、票数の最も多いモデルを検 索結果として出力する。 5. 評 価 実 験 我々の提案手法を評価するために、複数の部品から構成され る３種類の３次元 CAD モデルを用意した。図 7 に３種類の CAD モデル Clutch、Die、Gear とその構成部品を示す。これ らのモデルは Web サイト [9] から選び、簡単のため、いくつか の部品を除外して実験に使用した。我々は３次元 CAD モデル を３次元ボクセルモデルに変換し、180 × 180 × 180 の３次 はじめに、クエリモデルを複数の方向から投影し、クエリモ 元配列に格納した。また、各部品に対応するボクセルに材料に デルの投影画像群を生成する。その後、クエリモデルの投影画 よって異なる数値を振ることで、部品に使用されている材料を 表 1: モデルデータベースの各モデルに割り当てた数値 モデル 部品 タイプ A,B タイプ C clutch spring 30(2),70(4) 70(2),30(4) 10-80 10-80 gear planet others 10-130 10-130 die pillar 1 45(1),80(3) 80(1),45(3) others 10-85 10-85 others (a) Clutch (b) Die 40(3),115(2) 115(3),40(2) ただし、データベースの投影画像はあらかじめ用意しておく。 （ 1 ） クエリモデルを複数の方向から投影し、投影画像群 Pq を 生成する。 （ 2 ） データベース内のモデル M のすべてのモデルについて以 下の処理を行う。 (c) Gear 図 7: ３次元 CAD モデルデータベース内のモデル （ a ） データベースからモデルを 1 つ選択し、それを m ∈ M とおく。 （ b ） モデル m の投影画像群を Pm として、クエリモデル の投影画像群のすべての投影画像 p ∈ Pq について以 反映した３次元モデルを作成した。提案手法はモデルの形状だ けでなく、内部構造や部品に使用されている材料を識別する。 下の処理を行う。 i. クエリモデルの投影画像 p と投影画像群 Pm のす そこで、３種類の３次元 CAD モデルそれぞれについて３種類 べての投影画像との類似度をラドン変換を用いた の異なる数値の振り方を用意した。実験に用いた各モデルの数 位相限定相関法で算出する。 値の振り方を表 1 に示す。タイプ A とタイプ B は構成部品の 数は同じだが、一部の部品の配置が異なる。タイプ A とタイプ C は一部の部品の数が異なる。 例えば、Clutch モデルの構成部品の中には６つの spring があ り、spring は２種類の材料が使用されており、タイプによって各 ii. 算出した類似度の中で、最も高い類似度を Sm に 加える。 （ c ） クエリモデルのすべての投影画像から算出された類似 度 Sm のクエリの投影画像数で平均したものをモデル の類似度 sm とする。 spring の配置や数が異なる。表 1 の”30(2), 70(4)”は各 spring に割り当てた数値を表している。この場合、２つの spirng に 30 を割り当て、残りの４つの spring に 70 を割り当てること （ 3 ） 算出された各モデルの類似度の中で、最も高い類似度をも つモデルを検索結果として出力する。 を意味している。また、”10-80”は spring 以外の構成部品に この手法は、データベース内の１つのモデルとクエリモデル 10 から 80 までの数値を割り当てることを意味している。同様 との類似度を計算する処理を繰り返すことで、データベース内 に、”70(2), 30(4)”は２つの spring に 70 を割り当て、残りの 4 の各モデルとクエリモデルとの類似度を計算する。そのため、 つの spring に 30 を割り当てることを意味している。したがっ モデル検索の処理に時間を要するという欠点がある。以降では、 て、Clutch A（タイプ A） と Clutch C（タイプ C） spring 投影を用いた３次元モデル検索の手法を比較手法と呼ぶ。 に使用されている材料は同じだが、２種類の spring の数がそ 5. 2 モデルの内部構造および材料の識別 れぞれ異なる。また、Clutch A（タイプ A） と Clutch B（タ 我々の提案手法がモデルの内部構造や構成部品に使用されて イプ B） は spring に使用されている材料とそれぞれの spring いる材料を識別できるかどうかを実験し、その評価を行った。 の数は同じだが、spring の配置が異なる。 前述の配置や材料の異なる９つのモデルを３次元モデルデータ これらのモデルはすべてランダムに位置変化と姿勢変化を加 えて実験を行った。 ベースとし、それらのモデルについてあらかじめ投影画像を生 成し、投影画像に対する索引構造を構築しておく。投影画像は プログラム開発は Visual C++ 2012、MATLAB 2012b を 各モデルで 162 枚用意し、９つのモデルで合計 1458 枚の投影 Windows 7 Professional 64 bit 上で用い、2.8GHz Intel Core 画像に対して索引構造を構築し、それを用いた。クエリモデル i3 プロセッサ、16GB RAM のコンピュータで実験を行った。 もデータベースモデルと同様に 162 枚の投影画像を生成し、そ 5. 1 投影画像を用いた３次元モデル検索 れらを用いてデータベース検索を行った。 ここでは、提案手法の比較として投影画像を用いた３次元モ 図 8 に３次元モデルデータベース検索における各モデルの得 デル検索を行う。投影を用いた３次元モデル検索は提案手法と 票数を示す。クエリモデルは Clutch A、Gear A、Die A の３ 同様に、３次元モデルの内部構造や材料の情報を識別する。投 種類用意し、それぞれのクエリモデルを用いてデータベース検 影画像を用いた３次元モデル検索の手順は次のとおりである。 索を行った。図 8 から、クエリモデルと同じモデルが最も得票 図 8: Clutch A, Die A, Gear A の各モデルをクエリとしたと 図 10: Clutch A, Die A, Gear A の各モデルをクエリとしたと きの提案手法によるデータベース内の各モデルの得票数 きの比較手法によるデータベース内の各モデルの類似度 図 9: 提案手法による各クエリモデルの検索にかかる処理時間 図 11: 比較手法による各クエリモデルの検索にかかる処理時間 数が多いことがわかる。クエリモデルと配置が異なるモデルや かかる処理時間を示す。図 9 および図 11 から、比較手法に比 材料が異なるモデルが同じモデルの次に得票数が多い。また、 べ、我々の提案手法による検索処理にかかる時間が大幅に短縮 クエリモデルと異なるモデルには１票も入っていない。した されていることがわかる。 がって、我々の提案手法はモデルの形状による識別に加え、構 5. 4 投影画像の数による検索性能と処理時間への影響 成部品の配置を含めた内部構造や部品の材料による識別もでき 前節までは、クエリモデルの投影画像を 162 枚用意し、３次 ているといえる。 また、図 9 に各クエリモデルにおけるデータベース検索に 元モデルデータベース検索を行った。ここでは、クエリモデル の投影画像の枚数を変化させ、データベース検索の実験を行い、 かかる処理時間を示す。図 9 から、クエリモデルによって得票 我々の提案手法の検索性能と検索にかかる処理時間の評価を行 数計算にかかる時間が異なることがわかる。これは、モデルに う。図 12, 13 にクエリモデルの投影画像の数を変化させたと よって投影画像のグループ数やグループ内の画像数が異なるた きのデータベース検索の実験結果とその処理時間を示す。本稿 めに差ができたと考えられる。 では、投影画像数は偏角の角度間隔によって決定する。ここで 5. 3 索引構造を用いた方法と従来の方法との比較 は、偏角の角度間隔を 20 °, 30 °, 40 °, 50 °, 60 °と変化させ 投影画像に対する索引構造を用いることで、モデル検索の処 た。すなわち、投影画像数を 162 枚, 72 枚, 45 枚, 32 枚, 18 枚 理時間が短縮されているかどうかを実験し、その評価を行った。 と変化させたときのデータベースの各モデルの得票数と処理時 また、提案手法と従来の投影画像を用いた３次元モデル検索の 間への影響を評価する。偏角の角度によって投影画像数、すな 手法との処理時間を比較し、提案手法の有効性を示す。前節と わち、全票数が異なるため、図 12 では各モデルの得票数を全 同様に９つのモデルを３次元モデルデータベースとして、デー 票数で割ることで得票率を算出し、それを用いた。図 12 の (a) タベース検索の実験を行った。すべてのモデルの投影画像数は , (b), (c) はそれぞれクエリモデルを Clutch A、Die A、Gear 162 枚とした。前節と同様に Clutch A、Gear A、Die A をク A としたときのデータベース内の各モデルとの得票率を表して エリモデルとしたときのデータベース検索の実験の結果を図 10 いる。 に示す。図 10 から、提案手法と比較手法のどちらもクエリモ 実験結果から偏角の角度間隔を変化させると得票率が増減し デルと同じモデルが最も類似し、それに続いてクエリモデルと ていることがわかる。図 12 から、クエリモデルが Clutch A 配置が異なるモデルが類似していることがわかる。図 8 と図 10 、Die A のときは偏角の角度間隔を変化させてもクエリモデル から提案手法は比較手法と同様にクエリモデルと最も類似した と同じモデルが最大の得票率となっていることがわかる。した モデルを正しく検索できていることがわかる。 がって、クエリの投影画像数が減少しても正しく検索ができて また、図 11 に各クエリモデルにおけるデータベース検索に いるといえる。しかし、Gear A がクエリモデルのときでは、 (a) クエリモデル ： Clutch A 図 13: 投影画像数の変化と得票率算出の処理時間 る処理時間を大幅に短縮することができた。 今後はモデル検索にかかる処理時間のさらなる短縮に加え、 モデルの識別性能を向上させることが課題となる。 文 (b) クエリモデル ： Die A (c) クエリモデル ： Gear A 図 12: 投影画像数の変化と各クエリモデルにおけるデータベー スモデルの得票率 偏角の角度間隔によってはクエリモデルと異なるモデルが最大 の得票数となる場合があり、正しく検索できていない。これは、 モデルの姿勢の影響により、類似した投影画像が少ないために 誤った検索になってしまうと考えられる。 また、図 13 から、偏角の角度間隔を大きくすることで、処 理時間が短縮されていることがわかる。また、クエリモデル によって処理時間に差があることがわかる。これは、モデルに よって投影画像のグループ数やグループ内の投影画像数が異な るために差ができたと考えられる。 6. 結論と今後の課題 本稿では、投影画像に対する索引構造を用いた３次元モデル データベース検索の実験とその評価を行った。実験結果から、 各モデルについて複数の方向からの投影画像を用いることで、 ３次元アセンブリモデルの形状だけでなく、３次元アセンブリ モデルの部品の配置や材料を識別することが確認できた。また、 我々の提案手法は、従来の投影画像を用いた３次元モデル検索 と同等の検索性能を有し、従来の検索よりもモデル検索にかか 献 [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] A. Tatsuma and M. Aono, ”Multi-Fourier spectra descriptor and augmentation with spectral clustering for 3D shape retrieval,” Visual Computer, vol.25, issue.8, pp.785-804, 2009 [4] D. Zarpalas, P. Daras, A. Axenopoulos, D. Tzovaras, and M.G. Strintzis, ”3D Model Search and Retrieval Using the Spherical Trace Transform,” EURASIP Journal on Advances in Signal Processing, vol.2007, 2007 [5] A. S. Deshmukh, A. G. Banerjee, S. K. Gupta, R. D. Sriram, ”Content-based assembly search: A step towards assembly reuse,” Computer-Aided Design, vol 40, issue 2, Pages 244261, 2008 [6] Xiang Chen, Shuming Gao, Song Guo and Jing Bai, ”A flexible assembly retrieval approach for model reuse,” Computer-Aided Design, vol.44, issue 6, pp.554-574, 2012 [7] K. Hu, B. Wang, J.H. Yong, J.C. Paul, ”Relaxed lightweight assembly retrieval using vector space model,” ComputerAided Design, vol.45, issue.3, pp.739-750 , 2013 [8] M. Hasegawa and S. Tabbone, ”Amplitude-only log Radon transform for geometric invariant shape descriptor,” Pattern Recognition, vol.4, no.2, pp.643-658, 2014 [9] GrabCAD. http://grabcad.com/library