JP7601378B2 - ３次元ｃａｄモデル部分検索方法 - Google Patents

Description

特許法第３０条第２項適用 令和２年２月１４日にウェブサイト（ＵＲＬ：ｈｔｔｐｓ：／／ｃｍｓ．ｄｅｉｍ－ｆｏｒｕｍ．ｏｒｇ／ｄｅｉｍ２０２０／ｐａｐｅｒ／？ｐ＝Ｐ３３３ａ３ｄ８ａｆ１ｆ３８９３６６ｃ４４ｂ３８２ｂ３ｅ５３１４ｂｅ５７１４６ｅｆ２）に掲載された第１２回データ工学と情報マネジメントに関するフォーラムの予稿集で公開

特許法第３０条第２項適用 令和２年３月４日にオンライン開催された第１２回データ工学と情報マネジメントに関するフォーラムで発表

本発明は、３次元ＣＡＤモデル部分検索方法に関する。

近年、製造業などでは、３次元コンピュータ設計ツール（ＣＡＤ：Computer-Aided Design）を用いたモデル設計が行われている。設計業務の効率化を進めるためには、蓄積された３次元モデルデータの活用が必要不可欠である。そのため、３次元モデルデータの検索、クラスタリング、分類、検出など様々な技術の研究開発が行われている。

３次元モデルデータ活用の技術について共通して必要となるものの一つに、モデル間の類似度計算がある。また、モデル間の類似度計算の研究として、モデル同士の検索技術の研究が多く行われている。これまで、３次元モデルの検索技術に関する研究は盛んに行われているものの、そのほとんどはモデルの形状の情報のみを考慮した検索技術となっており、部品のレイアウトを厳密に比較できる検索技術は見られない。

機械設計などで作られる３次元モデルは、複数の部品を組み合わせたアセンブリモデルであることが多い。特に自動車などの複雑で大型な機械の設計では、複数の階層に渡って部品が組み合わさって構成されており、膨大な数の部品を含んだ巨大なモデルが作られている。このような、複数の部品を組み合わせたモデルをアセンブリモデルと呼び、各階層でのまとまりをサブアセンブリモデルという。３次元ＣＡＤモデルの最小単位を部品として、サブアセンブリモデルは部品の集合であり、アセンブリモデルはサブアセンブリモデルの集合である。アセンブリモデルに対しては、その複雑さのために部分検索技術の活用が困難であった。

このようなサブアセンブリモデルの検索を行う検索方法として、特許文献１には、３次元ＣＡＤデータを構成する構成要素ごとに検索を行い、かかる構成要素から完成品である３次元ＣＡＤデータにアクセスする３次元ＣＡＤモデル検索方法が提案されている。

特開２０１８－１３６９４６号公報

しかしながら、従来提案されている検索方法では、３次元ＣＡＤデータの投影画像に２次元ラドン変換を施し、得られたサイノグラムの性質を利用し比較を行うことで部分検索を実現しているため、３次元データから算出された特徴量のデータ量が大きくなり未だ迅速な検索の点では不十分であるという問題があった。

本発明は、迅速かつ正確性の高い検索を行うことができる３次元ＣＡＤモデル部分検索方法の提供を目的の一つとする。

本発明に係る３次元ＣＡＤモデル部分検索方法は、検索モデルを、データベース中に保存された比較モデルと比較し相違度を評価する３次元ＣＡＤモデル部分検索方法であり、前記検索モデルおよび前記比較モデルは、複数のサブアセンブリモデルから構成されるアセンブリモデルの３次元ＣＡＤデータであり、コンピュータが、前記検索モデルの特徴量を算出する第１の算出ステップと、前記コンピュータが、前記比較モデルの特徴量を算出する第２の算出ステップと、前記コンピュータが、前記検索モデルおよび前記比較モデルの特徴量を比較し、前記検索モデルおよび前記比較モデルの相違度を算出する比較ステップと、を有し、前記第１の算出ステップおよび前記第２の算出ステップでは、前記検索モデルおよび前記比較モデルを構成する全てのサブアセンブリモデルに対して、サブアセンブリモデルと、当該サブアセンブリモデルを除いたアセンブリモデルと、がそれぞれ３次元ラドン変換され、変換された値から前記特徴量が導かれる。

本発明によれば、迅速かつ正確性の高い検索を行うことができる３次元ＣＡＤモデル部分検索方法を提供できる。

図１は、検索モデルの一例として示すアセンブリモデルの透視図である。 図２は、比較モデルの一例として示すアセンブリモデルの透視図である。 図３は、比較モデルの一例として示すアセンブリモデルの透視図である。 図４は、本実施形態の３次元ＣＡＤモデル部分検索方法の一例を示す模式図であり、主に比較ステップを表す。 図５は、本実施形態の３次元ＣＡＤモデル部分検索方法の一例を示す模式図であり、主に比較ステップの方向固定第１ステップを表す。

本実施形態の３次元ＣＡＤモデル部分検索方法（以下、単に部分検索方法）において対象となる３次元ＣＡＤデータ（以下、単にＣＡＤデータ）は、複数のサブアセンブリモデルを含むアセンブリモデルである。

本実施形態の部分検索方法は、検索モデルを、データベース中に保存された比較モデルと比較し相違度を評価する方法である。なお、本実施形態の部分検索方法は、検索モデルが比較モデルの一部を含む場合であっても、比較モデルが検索モデルの一部を含む場合であっても、何れにおいても対応可能である。本実施形態では、データベースに保存された複数の比較モデルの中から、検索モデルに含まれるものを見つけ出す場合について説明する。

なお、検索モデルおよび比較モデルは、複数のサブアセンブリモデルから構成されるアセンブリモデルの３次元ＣＡＤデータである。
また、相違度とは、比較モデルが検索モデルにどの程度含まれていないか（検索モデルと比較モデルとが概念的にどれほど離間しているか）を表す指標である。相違度は、０又は０以上の正の値をとる。検索モデルが比較モデルを含んでいれば、相違度は０になる。したがって、相違度の値が小さくなればなるほど、比較モデルが検索モデルに含まれる程度が高いことを意味する。

本明細書において、アセンブリモデルとは、複数のサブアセンブリモデルを組み合わせて構成される３次元モデルである。また、本明細書において、サブアセンブリモデルとは、アセンブリモデルの一部を構成する３次元モデルである。したがって、アセンブリモデルは、複数の異なる又は同一のサブアセンブリモデルを有する。サブアセンブリモデルは、複数の部品を組み合わせて構成される３次元モデルである。また、サブアセンブリモデルは、単一の部品のみを有する３次元モデルであってもよい。

＜例示的な説明＞
図１～図３を基に、本実施形態の部分検索方法について例示的に説明する。ここでの説明はあくまで、部分検索方法の概念を例示的に説明するものであり、厳密な意味において後述する実施形態の部分検索方法とは手法が異なる。

図１～図３は、それぞれ第１～第３のアセンブリモデル１１、１２、１３の透視図である。図１～図３において、それぞれのアセンブリモデルに含まれるサブアセンブリモデルは、模様分けされている。

図１に示す第１のアセンブリモデル１１は、ベース部１０と、第１のサブアセンブリモデル２１と、第２のサブアセンブリモデル２２と、第３のサブアセンブリモデル２３と、第４のサブアセンブリモデル２４と、を有する。
図２に示す第２のアセンブリモデル１２は、ベース部１０と、第１のサブアセンブリモデル２１と、第２のサブアセンブリモデル２２と、第５のサブアセンブリモデル２５と、を有する。
図３に示す第３のアセンブリモデル１３は、ベース部１０と、第１のサブアセンブリモデル２１と、第５のサブアセンブリモデル２５と、第６のサブアセンブリモデル２６と、を有する。
なお、ベース部１０も、サブアセンブリモデルの１つとみなされる。

ここでは、第１のアセンブリモデル１１に対する第２および第３のアセンブリモデル１２、１３の相違度の判定について検討する。すなわち、この例では、第１のアセンブリモデル１１が、検索モデルにあたり、第２および第３のアセンブリモデル１２、１３が比較モデルにあたる。

第２のアセンブリモデル１２は、第１のアセンブリモデル１１が有さない第５のサブアセンブリモデル２５を有する。また、第３のアセンブリモデル１３は、第１のアセンブリモデル１１が有さない第５のサブアセンブリモデル２５および第６のサブアセンブリモデル２６を有する。

第２および第３のアセンブリモデル１２、１３に含まれる第５のサブアセンブリモデル２５は、第１のアセンブリモデル１１に含まれる第３のサブアセンブリモデル２３の一部である。一方で、第３のアセンブリモデル１３に含まれる第６のサブアセンブリモデル２６は、第１のアセンブリモデル１１に含まれるサブアセンブリモデル２２と同じ部品から構成されるが、第１のアセンブリモデル１１とは他のサブアセンブリモデルとの位置関係が異なる。

第１のアセンブリモデル１１と第２および第３のアセンブリモデル１２、１３とを比較した結果、第２のアセンブリモデル１２に含まれる部品は全て、第１のアセンブリモデル１１に同じ配置で含まれている。それに対して、第３のアセンブリモデル１３に含まれる部品は全て、第１のアセンブリモデル１１に含まれるものの、第６のサブアセンブリモデル２６の配置が、第１のアセンブリモデル１１に含まれる第２のサブアセンブリモデル２２とは異なる。そこで、このような例の場合、第１のアセンブリモデル１１と類似性が高い（すなわち相違度が低い）のは、第２のアセンブリモデル１２であると判定される。このように、本実施形態の部分検索方法は、サブアセンブリモデルの配置を考慮したものである。

ここで例示した第１～第３のアセンブリモデル１１、１２、１３は、姿勢が互いにそろっている。しかしながら、実際に作成さているアセンブリモデルのデータは、基準となる方向がモデル毎に互いに異なっている場合がある。このため、部分検索方法では、アセンブリモデル間で、相対的な姿勢を変えた場合のそれぞれの相対的な位置関係を考慮する必要がある。

＜実施形態＞
以下、実施形態について説明する。
本実施形態では、検索対象のアセンブリモデルを検索モデルと呼ぶ。また、データベース中に保存された被検索対象のアセンブリモデルを比較モデルと呼ぶ。

本実施形態の部分検索方法は、第１の算出ステップと、第２の算出ステップと、比較ステップと、出力ステップと、を有する。なお、第１の算出ステップと第２の算出ステップの順序は、逆であってもよい。また、比較ステップは、第１および第２の算出ステップで得た値（特徴量）を用いるため、第１および第２の算出ステップの後に行う。

第１の算出ステップと第２の算出ステップとは、主に同様の手順で行われるが、算出対象となるＣＡＤデータが異なる。第１の算出ステップは、検索対象である検索モデルから特徴量を算出するステップである。一方で、第２の算出ステップは、データベース中に保存された比較モデルの特徴量をそれぞれ算出するステップである。

本実施形態の部分検索方法のアルゴリズムをメインアルゴリズムとして表１に示す。

ここで、メインアルゴリズムおよび以降で用いる記号を定義する。
Ｍ_ｃｏｍｐは、検索モデルを表す。
Ｍ_ｐａｒｔは、比較モデルを表す。
検索モデルＭ_ｃｏｍｐおよび比較モデルＭ_ｐａｒｔはサブアセンブリモデルｓａの集合である。
Ｖ_ｃｏｍｐおよびＶ_ｐａｒｔは、それぞれ３次元ラドン変換を行う方向の集合である。Ｖ_ｃｏｍｐおよびＶ_ｐａｒｔの要素ｖは空間極座標で方向を表す２次元ベクトルである。より具体的には、単位球面上に一様に分布する点で方向を指定する。

本実施形態において、第１の算出ステップにおける３次元ラドン変換を行う方向の数（Ｖ_ｃｏｍｐに含まれる要素数）は、第２の算出ステップにおける３次元ラドン変換を行う方向の数（Ｖ_ｐａｒｔに含まれる要素数）より少ない。一般的に、検索モデルから特徴量を算出するステップ（第１の算出ステップ）は、オンラインで実行され、比較モデルから特徴量を算出するステップ（第２の算出ステップ）は、同一サーバー内で予め実行され記憶される。第１の算出ステップにおける３次元ラドン変換を行う方向の数を抑制することで、オンラインで行う特徴量の算出を高速に行うとともに、第２の算出ステップにおける３次元ラドン変換を行う方向の数を増加させることで、検索結果の正確性を担保できる。

メインアルゴリズムは、以下に示す３つのステップを経て検索モデルと比較モデルとの間の相違度計算を行う。
（１）第１の算出ステップ
（２）第２の算出ステップ
（３）比較ステップ
以下、それぞれのステップについてより具体的に説明する。

＜第１および第２の算出ステップ＞
第１の算出ステップでは、検索対象である検索モデルを複数の方向から３次元ラドン変換することで特徴量が算出される。同様に、第２の算出ステップでは、被検索対象の比較モデルを複数の方向から３次元ラドン変換することで特徴量が算出される。

検索モデルＭ_ｃｏｍｐと比較モデルＭ_ｐａｒｔが与えられたとき、２つのアセンブリモデル（検索モデルおよび比較モデル）間のサブアセンブリモデルの対応は一般的に未知である。また、２つのアセンブリモデルの位置や向きの関係も未知である。よって本実施形態の部分検索方法では、すべてのサブアセンブリモデル同士の組み合わせ、すべて方向の組み合わせで比較をし、その中でアセンブリモデル間の相違度が最小となるような組み合わせを選択する。

ここで、３次元ラドン変換のアルゴリズムを第１のサブアルゴリズムとして、表２に示す。第１のサブアルゴリズムは、第１および第２の算出ステップの一部であり、３次元ラドン変換を導出するアルゴリズムである。第１のサブアルゴリズムは、表１に示すメインアルゴリズムにおいて、Radon3Dと表現されたアルゴリズムである。

第１のサブアルゴリズムにおいて、方向ｖ∈Ｖに沿って３次元ラドン変換を行うとき、まずはｖがｘ軸正の方向になるようモデルの回転を行う。
第１のサブアルゴリズムでは、２行目の関数ｓａ´＝Ｒｏｔａｔｅ（ｓａ，ｖ）において、回転前のサブアセンブリモデルｓａにおけるｖがｓａ′のｘ軸正の方向となるよう回転する。

次にｘ軸正の方向に沿って、ｘ軸に垂直な面でのモデルの断面積を計算する。第１のサブアルゴリズムの４行目の関数calculateCrossSectionArea（ｓａ′，ｘ）は、モデルｓａ′のｘ軸方向の値がｘであるところでの断面積を求める関数である。ここでｘは指定されたサンプリング間隔ごとに変化し、モデルの存在する区間を走査する。

実際の３次元ＣＡＤモデルは、様々なデータ形式で保存される。標準的な形状の記述形式にＳＴＬ（Standard Triangulated Language）データ形式がある。ＳＴＬファイル形式は、３次元立体の表面を小さな三角形の面の集合で表すポリゴン形式である。ＳＴＬデータ形式は、全ての主要な３次元データ形式から変換可能な形式である。このような形式において、幾何学的な計算から断面積が計算できる。こうして得られる特徴量ｆｅａｔｕｒｅは、非負の値を持つ、（方向の個数）×（サンプリング数）の二次実数配列である。

第１の算出ステップにおいて、第１のサブアルゴリズムを実行することで、比較モデルＭ_ｐａｒｔの特徴量Ｆ_ｐａｒｔが算出される。第１の算出ステップにおいて、第１のサブアルゴリズムを実行することで、検索モデルＭ_ｃｏｍｐの特徴量Ｆ_ｃｏｍｐが算出される。

本実施形態によれば、第１の算出ステップおよび第２の算出ステップにおいて、３次元ＣＡＤモデルを３次元ラドン変換することで特徴量が算出される。３次元ラドン変換は、原点に対する方向（球面上の座標）および原点からの距離における３次元ＣＡＤモデルの断面積を算出する計算方法である。このため、３次元ラドン変換によって得られる特徴量は、原点に対する方向および距離に紐づけられたスカラー値となり、特許文献１に開示される検索方法と比較して、データ量を小さくすることができる。結果的に、第１の算出ステップおよび第２の算出ステップにおける特徴量の算出時間、並びに、後述する比較ステップにおける計算時間を大幅に短縮することができる。加えて、計算時間が短縮されることから、サンプル数を増加させやすくなり、相違度の評価の正確性を高めることができる。

本実施形態によれば、第１の算出ステップおよび第２の算出ステップにおいて、複数の方向から断面積を計算する。このため、互いに姿勢が異なる検索モデルと比較モデルとの比較においても、有効に差分を評価できる特徴量が算出される。

本実施形態の第１および第２の算出ステップでは、アセンブリモデルに含まれるサブアセンブリモデルの相対的な位置関係を特徴量として算出することが求められる。そこで、本発明者らは、比較するサブアセンブリモデルと、当該サブアセンブリモデルを除くアセンブリモデルとを、それぞれ３次元ラドン変換して得た値を組み合わせて特徴量として扱うことを想到した。

本実施形態によれば、第１の算出ステップおよび第２の算出ステップにおいて、構成する全てのサブアセンブリモデルに対し、サブアセンブリモデルと、当該サブアセンブリモデルを除いたアセンブリモデルと、がそれぞれ３次元ラドン変換され、変換された値が特徴量とされる。
すなわち、第１の算出ステップで導かれる特徴量ｆ_ｃｏｍｐは、サブアセンブリモデルｓａの３次元ラドン変換の結果（ｆ_ｃｏｍｐ，_ｓａ）と、当該サブアセンブリモデルｓａを除いたアセンブリモデルの３次元ラドン変換の結果（ｆ_ｃｏｍｐ，_{ｏｔｈｅｒｓ}）と、からなる。
同様に、第２の算出ステップで導かれる特徴量ｆ_ｐａｒｔは、サブアセンブリモデルｓａの３次元ラドン変換の結果（ｆ_ｐａｒｔ，_ｓａ）と、当該サブアセンブリモデルｓａを除いたアセンブリモデルの３次元ラドン変換の結果（ｆ_ｐａｒｔ，_{ｏｔｈｅｒｓ}）と、からなる。

第１の算出ステップおよび第２の算出ステップにおいて、サブアセンブリモデルおよび当該サブアセンブリモデルを除いたアセンブリモデルの特徴量は、正規化されている。これにより、各部品の大小が特徴量に影響を与えることを抑制することができる。
より具体的には、第１の算出ステップおよび第２の算出ステップにおいて、サブアセンブリモデルおよび当該サブアセンブリモデルを除いたアセンブリモデルの特徴量は、それぞれ含まれるすべての部品を個別に３次元ラドン変換して部品の体積の近似値で割った値の総和である。

図４および図５は、本実施形態の３次元ＣＡＤモデル部分検索方法の一例を示す模式図である。各図において、比較モデル３０のサブアセンブリモデル３１、３２および検索モデル４０のサブアセンブリモデル４１、４２、４３を模式的に示す。各図において、１つの立方体は、１つの部品を表す。同一の模様で表される立方体の集合は、１つのサブアセンブリを表す。

この例において、比較モデル３０は、第１のサブアセンブリモデル３１と第２のサブアセンブリモデル３２とを有する。比較モデル３０の第１のサブアセンブリ３１は、２つの部品３１ａ、３１ｂからなる。比較モデル３０の第２のサブアセンブリ３２は、１つの部品３２ａからなる。

この例において、検索モデル４０は、第１のサブアセンブリモデル４１と第２のサブアセンブリモデル４２と第３のサブアセンブリモデル４３とを有する。検索モデル４０の第１のサブアセンブリ４１は、１つの部品４１ａからなる。検索モデル４０の第２のサブアセンブリ４２は、２つの部品４２ａ、４２ｂからなる。検索モデル４０の第３のサブアセンブリ４３は、１つの部品４３ａからなる。

図４は、後述する比較ステップにおいて、比較モデル３０および検索モデル４０のサブアセンブリモデルの比較する組み合わせＢ１、Ｂ２、Ｂ３、Ｂ４、Ｂ５、Ｂ６を表す図である。比較ステップでは、図４の全ての組み合わせＢ１、Ｂ２、Ｂ３、Ｂ４、Ｂ５、Ｂ６の比較を順次行う。

図５は、後述する比較ステップにおいて、比較モデル３０の第１のサブアセンブリモデル３１と、検索モデル４０の第１のサブアセンブリ４１と、を比較する際のそれぞれの特徴量の取り扱いを示す図である。図５は、比較ステップのうち、図４の表中の組み合わせＢ１における比較する工程を示す図であり、比較モデル３０および検索モデル４０の第１のサブアセンブリ３１、４１が比較される。

図５に示すように、比較モデル３０の特徴量としては、第１のサブアセンブリモデル３１の特徴量と、第１のサブアセンブリモデル３１を除いたアセンブリモデル（すなわち、第２のサブアセンブリモデル３２）の特徴量と、が算出される。なお、比較モデル３０の特徴量を算出するステップは、第１の算出ステップである。

上述したように、比較されるサブアセンブリモデルおよび当該比較されるサブアセンブリモデルを除いたアセンブリモデルの特徴量は、それぞれ含まれるすべての部品を個別に３次元ラドン変換して部品の体積の近似値で割った値の総和である。

比較モデル３０の第１のサブアセンブリモデル３１には、２つの部品３１ａ、３１ｂが含まれる。このため、２つの部品３１ａ、３１ｂを個別に３次元ラドン変換して、それぞれの部品の体積の近似値で割った値の総和が、比較モデル３０の第１のサブアセンブリモデル３１の特徴量となる。

一方で、比較モデル３０の第１のサブアセンブリモデル３１を除いたアセンブリモデル（すなわち、第２のサブアセンブリモデル３２）に含まれるのは、１つの部品３２ａのみである。このため、部品３２ａを３次元ラドン変換した値を、部品３２ａの体積の近似値で割った値が第２のサブアセンブリモデル３１を除いたアセンブリモデルの特徴量となる。

また、検索モデル４０の特徴量としては、第１のサブアセンブリモデル４１の特徴量と、第１のサブアセンブリモデル４１を除いたアセンブリモデル（すなわち、第２、第３のサブアセンブリモデル４２、４３）の特徴量と、が算出される。なお、検索モデル４０の特徴量を算出するステップは、第２の算出ステップである。

検索モデル４０の第１のサブアセンブリモデル４１に含まれるのは、１つの部品４１ａのみである。このため、部品４１ａを３次元ラドン変換した値を、部品４１ａの体積の近似値で割った値が検索モデル４０の第１のサブアセンブリモデル４１の特徴量となる。

一方で、検索モデル４０の第１のサブアセンブリモデル４１を除いたアセンブリモデル（すなわち、第２、第３のサブアセンブリモデル４２、４３）には、合わせて３つの部品４２ａ、４２ｂ、４３ａか含まれる。このため、３つの部品４２ａ、４２ｂ、４３ａを個別に３次元ラドン変換して、それぞれの部品の体積の近似値で割った値の総和が、第１のサブアセンブリモデル４１を除いたアセンブリモデルの特徴量となる。

本実施形態によれば、サブアセンブリモデルと当該サブアセンブリモデルを除くアセンブリモデルと、をそれぞれ個別に３次元ラドン変換して特徴量とする。これら２つの特徴量を同時に比較することにより、アセンブリモデルに対するサブアセンブリモデルの相対的な位置関係が考慮された特徴量を算出できる。結果的に、サブアセンブリモデルの幾何学的な配置を考慮して検索モデルと比較モデルとの相違度の算出を行うことができる。

本実施形態によれば、サブアセンブリモデルを３次元ラドン変換した値と、当該サブアセンブリモデルを除くアセンブリモデルを３次元ラドン変換した値と、をそれぞれ個別に特徴量として扱う。このため、例えば、これらの値の和を用いる場合（特許文献１参照）と比較して、相対的な位置関係を表す情報が薄まることがなく、特徴量によって相違度を明確に判定し易い。
なお、本実施形態によれば、特許文献１に開示される検索方法と比較して、特徴量を算出する手法として３次元ラドン変換が採用されることで特徴量のデータ容量が情報量に対して小さくすることができている。このため、サブアセンブリモデルを３次元ラドン変換した値と、当該サブアセンブリモデルを除くアセンブリモデルを３次元ラドン変換した値と、をそれぞれ個別に特徴量とした場合であっても、全体としてのデータ容量が大きくなりすぎることを抑制できる。

＜比較ステップ＞
比較ステップは、検索モデルおよび比較モデルの特徴量を比較し、検索モデルおよび比較モデルの相違度を算出するステップである。

表１のメインアルゴリズムに示すように、（３）比較ステップは、（３－１）方向固定第１ステップと、（３－２）方向固定第２ステップと、（３－３）決定ステップと、を有する。
（３－１）方向固定第１ステップは、方向を固定した上で、サブアセンブリ間の可能な全ての対応関係に対して、検索モデルと比較モデルの特徴量から、それらの間の相違度（特定組み合わせ相違度）を計算するステップである。
（３－２）
方向固定第２ステップは、方向固定第１ステップで導かれた複数の特定組み合わせ相違度の中から最小の値を選び、この方向における相違度（特定方向相違度）とするステップである。
（３－３）決定ステップは、方向固定第２ステップで導かれたそれぞれの方向における特定方向相違度の中から、最小のものを選び、比較モデルと検索モデルの相違度を導くステップである。

（方向固定第１ステップ）
方向固定第１ステップは、特定の方向に対し、検索モデルと比較モデルのサブアセンブリモデルの全ての組み合わせに対して相違度を算出するステップである。方向固定第１ステップでは、検索モデルの全てのサブアセンブリモデルと、比較モデルの全てのサブアセンブリモデルとの相違度を総当たりで算出する。

方向固定第１ステップでは、固定された特定の方向に対して、検索モデルと比較モデルとが比較される。また、後述する決定ステップに示すように、固定される特定の方向をあらゆる方向に変化させることで、最終的にすべての方向に対して、検索モデルと比較モデルとが比較される。

ここで、方向固定第１ステップで算出される、総当たりのサブアセンブリモデルの組み合わせのそれぞれの相違度を、「特定組み合わせ相違度」と呼ぶ。方向固定第１ステップでは、固定された方向において総当たりでされたサブアセンブリモデルの組み合わせと同数の特定組み合わせ相違度が算出される。

すなわち、方向固定第１ステップは、方向を固定して、検索モデルの全てのサブアセンブリモデルと、比較モデルの全てのサブアセンブリモデルと、の全ての組み合わせに対して、特徴量の差分の総和を特定組み合わせ相違度として算出するステップである。

この点について、図４の模式図を基に説明する。
この例において、比較モデル３０は、２つのサブアセンブリモデル（第１および第２のサブアセンブリモデル３１、３２）を有する。一方で、検索モデル４０は、３つのサブアセンブリモデル（第１、第２および第３のサブアセンブリモデル４１、４２、４３）を有する。方向固定第１ステップでは、固定された特定の方向において、比較モデル３０の第１のサブアセンブリモデル３１に対し検索モデル４０の第１、第２および第３のサブアセンブリモデル４１、４２、４３を比較し、比較モデル３０の第２のサブアセンブリモデル３２に対し検索モデル４０の第１、第２および第３のサブアセンブリモデル４１、４２、４３を比較する。結果的に、比較モデル３０のサブアセンブリモデルの個数と、検索モデル４０のサブアセンブリモデルの個数と、の積（図４において、２×３）に相当する個数の特定組み合わせ相違度を算出する。

第１および第２の算出ステップにおいて検索モデルＭ_ｃｏｍｐおよび比較モデルＭ_ｐａｒｔの比較する特徴量ｆ_ｃｏｍｐ，ｆ_ｐａｒｔを決めたとき、特定組み合わせ相違度を計算するアルゴリズムを第２のサブアルゴリズムとして、表３に示す。第２のサブアルゴリズムは、表１に示すメインアルゴリズムにおいて、ComputePartialDissimilarityと表現されたアルゴリズムである。

アセンブリモデルは一般に、３次元空間内における姿勢や位置がデータによって異なる。そのため、回転や平行移動に対して頑健な特徴量の差分を導出するため、特徴量は平行移動させながら差分を導出する。ただし、アセンブリ内におけるサブアセンブリモデルの相対的な位置情報は必要なため、着目しているサブアセンブリモデルを平行移動させると同時に、当該サブアセンブリモデルを除いたアセンブリモデル全体の特徴量（ｆ_ｃｏｍｐ，_{ｏｔｈｅｒｓ}、ｆ_ｐａｒｔ，_{ｏｔｈｅｒｓ}）を同時に平行移動させ、これについても同様に特徴量の差分を導出する。

すなわち、比較ステップにおいて、比較する特徴量同士を相対的に平行移動させて、特徴量の差分の総和が最小となる値を相違度とする。

本実施形態によれば、検索モデルおよび比較モデルの特徴量を相対的に平行移動させて相違度を算出すため、検索モデルと比較モデルとの相対的な位置関係について網羅的に確認して最適な相違度を算出でき、相対的な位置関係のずれを相殺することができる。

比較モデルのサブアセンブリモデルの特徴量ｆ_ｐａｒｔ，_ｓａおよび検索モデルのサブアセンブリモデルの特徴量ｆ_ｃｏｍｐ，_ｓａには、着目しているサブアセンブリモデルの形状、および配置の情報が含まれており、その差分（ｆ_ｐａｒｔ，_ｓａ － ｆ_ｃｏｍｐ，_ｓａ）は、形状や配置の違いを表す値となる。ここで比較モデルが検索モデルに完全に含まれるとき、（ｆ_ｐａｒｔ，_ｓａ － ｆ_ｃｏｍｐ，_ｓａ）の要素に正の値は含まれず、０または負の値のみとなる。

このとき、第２のサブアルゴリズムの７行目および８行目のように、差の値と０の大きい方の値を採用することにより、完全に部分一致する場合は０に、そうでない場合は0でない差が検索モデルに含まれていない程度を表しており、はみ出した部分の値が特徴量同士の差分となる。

また、当該サブアセンブリモデルを除いた検索モデルの特徴量ｆ_ｃｏｍｐ，_{ｏｔｈｅｒｓ}および当該サブアセンブリモデルを除いた比較モデルの特徴量ｆ_ｐａｒｔ，_{ｏｔｈｅｒｓ}も同時に比較している。図５を基に説明したように、これらはそれぞれ、対象となるサブアセンブリモデルを構成する部品の特徴量の和をもって計算される。

第２のサブアルゴリズムの１０行目および１１行目において、サブアセンブリモデルの特徴量の差と当該サブアセンブリモデルを除いたアセンブリモデルの特徴量の差のそれぞれを比較モデル側のサブアセンブリモデルに含まれる部品の数で割っている。また、この割った値を用いて、比較ステップの各特徴量の差の比較が行われる。これにより、サブアセンブリモデルに含まれる部品の数が、特徴量の差に影響を及ぼすことを抑制できる。

図５において模式的に示すように、比較ステップにおいて、第１の算出ステップおよび第２の算出ステップで算出されたサブアセンブリモデルおよび当該サブアセンブリモデルを除いたアセンブリモデルの特徴量として、それぞれを構成する部品を３次元ラドン変換し当該部品の体積の近似値で割ったものの総和を用いることが好ましい。

すなわち、方向固定第１ステップにおいて、検索モデルおよび比較モデルについて、比較するサブアセンブリモデル同士の特徴量の差分と、当該比較するサブアセンブリモデルを除いたアセンブリモデル同士の特徴量の差分と、の和を基に特定組み合わせ相違度が算出される。３次元ラドン変換による特徴量の値は、モデルの体積に影響を受ける。本実施形態では、部品を３次元ラドン変換し当該部品の体積の近似値で割ったものの総和を基に、特定組み合わせ相違度を算出することで、部品の体積が特定組み合わせ相違度の算出に及ぼす影響を軽減できる。

なお、体積の近似値としては、３次元ラドン変換により算出した断面積の合計（積分値）を用いることもできる。これにより、別途体積の算出を行うことなく正規化を実行でき、処理時間の短縮を図ることができる。

さらに、方向固定第１ステップにおいて、検索モデルおよび比較モデルについての比較するサブアセンブリモデル同士の特徴量の差分と、当該比較するサブアセンブリモデルを除いたアセンブリモデル同士の特徴量の差分と、の和を、さらに、比較モデルの比較するサブアセンブリモデルの部品数で割ったもので特定組み合わせ相違度を算出することが好ましい。上述の和を、比較モデルのサブアセンブリモデルの部品数で割ることで、部品の数が特定組み合わせ相違度の算出に及ぼす影響を軽減できる。

この点について、図５の模式図を基に説明する。
方向固定第１ステップでは、方向を固定して、比較モデル３０と検索モデル４０との、全てのサブアセンブリモデル同士の組み合わせに対して、特徴量の差分の総和を特定組み合わせ相違度として算出するステップである。

図５では、比較モデル３０の第１のサブアセンブリモデル３１と、検索モデル４０の第１のサブアセンブリモデル４１と、を比較している。

比較モデル３０の第１のサブアセンブリ３１の特徴量は、２つの部品３１ａ、３１ｂを個別に３次元ラドン変換して、それぞれの部品の体積の近似値で割り正規化したものの総和である。一方で、検索モデル４０の第１のサブアセンブリ４１の特徴量は、部品４１ａを３次元ラドン変換して部品４１ａの体積の近似値で割り正規化したものである。
このステップでは、比較モデル３０の第１のサブアセンブリ３１の特徴量と、検索モデル４０の第１のサブアセンブリ４１の特徴量と、の差分（第１の差分Ｄ１）が算出される。

比較モデル３０の第１のサブアセンブリモデル３１を除いたアセンブリモデル（すなわち、第２のサブアセンブリモデル３２）の特徴量は、部品３２ａを３次元ラドン変換して部品３２ａの体積の近似値で割り正規化されたものである。一方で、検索モデル４０の第１のサブアセンブリモデル４１を除いたアセンブリモデル（すなわち、第２、第３のサブアセンブリモデル４２、４３）の特徴量は、３つの部品４２ａ、４２ｂ、４３ａを個別に３次元ラドン変換して、それぞれの部品の体積の近似値で割り正規化したものの総和である。
このステップでは、比較モデル３０の第１のサブアセンブリモデル３１を除いたアセンブリモデルと、検索モデル４０の第１のサブアセンブリモデル４１を除いたアセンブリモデルの特徴量と、の差分（第２の差分Ｄ２）が算出される。

方向固定ステップでは、第１の差分Ｄ１と第２の差分Ｄ２との和を、さらに、比較モデル３０の比較する第１のサブアセンブリモデル３１の部品数で割って、特定組み合わせ相違度を算出する。図５の例では、比較モデル３０の比較する第１のサブアセンブリ３１の部品数は、２である。このため、この例では、第１の差分Ｄ１と第２の差分Ｄ２との和は、２で割られる。

本実施形態によれば、第１の算出ステップにおいて、比較モデル３０の第１のサブアセンブリモデル３１および当該サブアセンブリモデル３１を除いたアセンブリモデル（すなわち、サブアセンブリモデル３２）の特徴量は、それぞれ含まれるすべての部品を個別に３次元ラドン変換して当該部品の体積の近似値で割った値の総和である。同様に、本実施形態の第２の算出ステップにおいて、検索モデル４０の第１のサブアセンブリモデル４１および当該サブアセンブリモデル４１を除いたアセンブリモデル（すなわち、サブアセンブリモデル４２、４３）の特徴量は、それぞれ含まれるすべての部品を個別に３次元ラドン変換して当該部品の体積の近似値で割った値の総和である。また、本実施形態の方向固定第１ステップにおいて、比較モデル３０および検索モデル４０について、比較するサブアセンブリモデル（第１のサブアセンブリモデル３１、４１）同士の特徴量の差分と、当該比較するサブアセンブリモデルを除いたアセンブリモデル同士の特徴量の差分と、の和を基に特定組み合わせ相違度を算出する。より具体的には、この和を、さらに、比較モデル３０の比較する第１のサブアセンブリモデル３１の部品数（この構成では２つ）で割ったもので特定組み合わせ相違度を算出する。これらの操作を行うことで、サブアセンブリモデルに含まれる部品の体積および部品の数に関わらず、全てのサブアセンブリモデルが等しい重みで評価され、正確にアセンブリモデル間の相違度を評価できる。

（方向固定第２ステップ）
方向固定第２ステップは、特定の方向に対する相違度（以下、「特定方向相違度と呼ぶ）を選ぶステップである。このステップで導かれた特定方向相違度は、特定の方向に限ってみた場合の、検索モデルと比較モデルとの相違度を表す。

方向固定第２ステップでは、まず、方向固定第１ステップで導かれた複数の特定組み合わせ相違度の中から最小の値が選ばれる。次いで、選ばれた最小の値を、この方向における相違度（特定方向相違度）と定める。

すなわち、方向固定第２ステップは、方向固定第１ステップにおいて算出した特定組み合わせ相違度が最小となるサブアセンブリモデルの組み合わせを導き、このときの特定組み合わせ相違度を、当該方向に対する特定方向相違度とするステップである。

この点について、図４の模式図を基に説明する。
この例において、比較モデル３０が２つのサブアセンブリモデル３１、３２を有し、検索モデル４０が３つのサブアセンブリモデル４１、４２、４３を有する。このため、比較モデル３０と検索モデル４０は、４０とは、６つのサブアセンブリモデルの組み合わせＢ１、Ｂ２、Ｂ３、Ｂ４、Ｂ５、Ｂ６の特定組み合わせ相違度を比較し、さらに、６つそれぞれの組み合わせＢ１、Ｂ２、Ｂ３、Ｂ４、Ｂ５、Ｂ６の特定組み合わせ相違度のうち最小の値を選び特定方向相違度とする。

表１に示すメインアルゴリズムの方向固定第２ステップについて詳細を示す。
まず、メインアルゴリズムの１６行目にて、これまでの処理で得られた特徴量ｆ_ｃｏｍｐ，ｆ_ｐａｒｔについて，ｓａ_ｃｏｍｐ∈Ｍ_ｃｏｍｐとｓａ_ｐａｒｔ∈Ｍ_ｐａｒｔのすべての組み合わせの中から、特徴量同士の差分の総和が最小となる組み合わせを解く。本実施形態では、比較モデルのサブアセンブリの数が、検索モデルのサブアセンブリの数より少ない。この場合、全ての組み合わせとは、比較モデルのサブアセンブリの集合から検索モデルのサブアセンブリの集合への全ての単射(写像)を意味する。

方向固定第２ステップにおける特徴量同士の差分の総和を、アセンブリ間の差分の総和とする。この最適な組み合わせを探す問題は、割当問題と呼ばれる組み合わせ最適化問題として定式化して解いている。

（決定ステップ）
決定ステップでは、想定される全ての方向に対して最も小さい相違度を決定するステップである。決定ステップを経ることで、検索モデルと比較モデルとの相違度を示す相違度が算出される。本実施形態では、検索モデルの特徴量を算出する際の３次元ラドン変換を行う方向の数（Ｖ_ｃｏｍｐに含まれる要素数）は、比較モデルの特徴量を算出する際の３次元ラドン変換を行う方向の数（Ｖ_ｐａｒｔに含まれる要素数）より少ない。相違度は、Ｖ_ｃｏｍｐからＶ_ｐａｒｔへの単射の中から相違度が最小となる単射を見つけ、その時の相違度から最終的なアセンブリ間の相違度を導く。相違度が最小となる単射は、割当問題として定式化して解かれる。

決定ステップでは、まず、全ての方向に対して、方向固定第１ステップおよび方向固定第２ステップを行う。すなわち、方向を変えながら、方向固定第１ステップおよび方向固定第２ステップを繰り返し行う。これにより、全ての方向の組み合わせにおいて特定方向相違度が求まる。次に、これらのなかで最も小さい特定方向相違度を選び出す。さらに、最も小さい特定方向相違度を、比較モデルのサブアセンブリの数で割ることで相違度を導く。

すなわち、決定ステップは、全ての方向に対して、方向固定第１ステップおよび方向固定第２ステップを行い、特定方向相違度が最小となる方向を導き、このときの特定方向相違度から検索モデルと比較モデルとの相違度を導くステップである。

また、本実施形態では、メインアルゴリズム（表１参照）の１９行目に示すように、決定ステップにおいて得られた結果（検索モデルと比較モデルとの相違度）は、比較モデルに含まれるサブアセンブリの数（｜Ｍ_ｐａｒｔ｜）によって割られる。すなわち、本実施形態によれば、相違度は、比較モデルに含まれるサブアセンブリの数によって正規化される。これによって、比較モデルのサブアセンブリの数が、相違度に影響を与えることを抑制できる。検索モデルと複数の比較モデルとの相違度を比較する場合に、比較モデル同士のサブアセンブリの数に差異がある場合であっても、正確な検索結果を算出することができる。

こうして得られた相違度をもとに行う検索は、モデルの姿勢や位置に対して頑健であり、サブアセンブリモデルの識別子にも依存せず、モデルの形状と配置をともに考慮した部分検索となっている。

ここでは、被検索対象として、１つの比較モデルを用意する場合について説明した。しかしながら、実際の実装では、データベースには、被検索対象として複数の比較モデルが記憶される。それぞれの比較モデルは、予め特徴量が算出され、関連情報として記憶されていることが好ましい。

検索モデルを、データベース中の複数のアセンブリモデルに対して検索する場合、検索モデルと、データベース中の複数の比較モデルとを順に比較し相違度が最も小さい比較モデルを導出する。これにより、データベース中の複数の比較モデルから、検索モデルに最も類似した１つを検索者に提供することができる。

以上に、本発明の様々な実施形態を説明したが、各実施形態における各構成およびそれらの組み合わせ等は一例であり、本発明の趣旨から逸脱しない範囲内で、構成の付加、省略、置換およびその他の変更が可能である。また、本発明は実施形態によって限定されることはない。

１０…ベース部、１１…第１のアセンブリモデル、１２…第２のアセンブリモデル、１３…第３のアセンブリモデル、２１…第１のサブアセンブリモデル、２２…第２のサブアセンブリモデル、２３…第３のサブアセンブリモデル、２４…第４のサブアセンブリモデル、２５…第５のサブアセンブリモデル、２６…第６のサブアセンブリモデル

Claims (9)

1. 検索モデルを、データベース中に保存された比較モデルと比較し相違度を評価する３次元ＣＡＤモデル部分検索方法であり、
   前記検索モデルおよび前記比較モデルは、複数のサブアセンブリモデルから構成されるアセンブリモデルの３次元ＣＡＤデータであり、
   コンピュータが、前記検索モデルの特徴量を算出する第１の算出ステップと、
   前記コンピュータが、前記比較モデルの特徴量を算出する第２の算出ステップと、
   前記コンピュータが、前記検索モデルおよび前記比較モデルの前記特徴量を比較し、前記検索モデルおよび前記比較モデルの相違度を算出する比較ステップと、を有し、
   前記第１の算出ステップおよび前記第２の算出ステップでは、前記検索モデルおよび前記比較モデルを構成する全てのサブアセンブリモデルに対して、サブアセンブリモデルと、当該サブアセンブリモデルを除いたアセンブリモデルと、がそれぞれ３次元ラドン変換され、変換された値から前記特徴量が導かれる、
   ３次元ＣＡＤモデル部分検索方法。
2. 前記第１の算出ステップおよび前記第２の算出ステップにおいて、前記コンピュータが、複数の方向から３次元ラドン変換を行う、
   請求項１に記載の３次元ＣＡＤモデル部分検索方法。
3. 前記比較ステップは、
   前記コンピュータが、前記方向を固定して、前記検索モデルと前記比較モデルとの、全てのサブアセンブリモデル同士の組み合わせに対して、前記特徴量の差分の総和を特定組み合わせ相違度として算出する方向固定第１ステップと、
   前記コンピュータが、前記方向固定第１ステップにおいて算出した特定組み合わせ相違度が最小となるサブアセンブリモデルの組み合わせを導き、このときの特定組み合わせ相違度を、前記方向に対する特定方向相違度とする方向固定第２ステップと、
   さらに、前記コンピュータが、全ての方向に対して、前記方向固定第１ステップおよび前記方向固定第２ステップを行い、前記特定方向相違度が最小となる前記方向を導き、このときの前記特定方向相違度から前記検索モデルと前記比較モデルとの前記相違度を導く決定ステップと、を有する、
   請求項２に記載の３次元ＣＡＤモデル部分検索方法。
4. 前記決定ステップにおいて、前記コンピュータが、前記特定方向相違度が最小となる前記方向を導き、このときの前記特定方向相違度を前記比較モデルのサブアセンブリの数で割ることで前記相違度を導く、
   請求項３に記載の３次元ＣＡＤモデル部分検索方法。
5. 前記第１の算出ステップおよび前記第２の算出ステップにおいて、
   サブアセンブリモデルおよび当該サブアセンブリモデルを除いたアセンブリモデルの前記特徴量は、それぞれ含まれるすべての部品を個別に３次元ラドン変換して当該部品の体積の近似値で割った値の総和である、
   請求項４に記載の３次元ＣＡＤモデル部分検索方法。
6. 前記方向固定第１ステップにおいて、前記コンピュータが、前記検索モデルおよび前記比較モデルについて、比較するサブアセンブリモデル同士の特徴量の差分と、当該比較するサブアセンブリモデルを除いたアセンブリモデル同士の特徴量の差分と、の和を基に前記特定組み合わせ相違度を算出する、
   請求項５に記載の３次元ＣＡＤモデル部分検索方法。
7. 前記方向固定第１ステップにおいて、前記コンピュータが、前記和を、さらに、前記比較モデルの比較するサブアセンブリモデルの部品数で割ったもので前記特定組み合わせ相違度を算出する、
   請求項６に記載の３次元ＣＡＤモデル部分検索方法。
8. 前記比較ステップにおいて、前記コンピュータが、比較する前記特徴量同士を相対的に平行移動させて、前記特徴量の差分の総和が最小となる値を求める、
   請求項１～７の何れか一項に記載の３次元ＣＡＤモデル部分検索方法。
9. 前記データベースには、被検索対象の複数の前記比較モデルが記憶され、
   前記コンピュータが、前記検索モデルを、複数の前記比較モデルと順に比較し前記相違度が最も小さいものを導出する、
   請求項１～８の何れか一項に記載の３次元ＣＡＤモデル部分検索方法。

Images