(57)【要約】      （修正有）【課題】メモリ消費および算出時間を改善した３Ｄモデル化オブジェクトのデータベース検索方法を提供する。【解決手段】本発明は、特に、データベースを照会するための、コンピュータによって実施される方法であって、データベースは、それぞれが機械部品を表す３Ｄモデル化オブジェクトを含み、さらに、各３Ｄモデル化オブジェクトについて、それぞれのモフォロジー署名を含む。方法は、モフォロジー基準を含むクエリを提供することＳ１と、クエリの結果として、データベースにおける各３Ｄモデル化オブジェクトを、モフォロジー基準に準拠したモフォロジー署名を有する程度に基づいて返すことＳ２とを含む。【効果】このような方法は、データベース内の機械部品検索の分野を改善する。【選択図】図１
2018022476.tif 000002
【特許請求の範囲】
【請求項１】
データベースを照会するための、コンピュータによって実施される方法であって、前記データベースは、それぞれが機械部品を表す３Ｄモデル化オブジェクトを含み、前記データベースはさらに、各３Ｄモデル化オブジェクトについて、それぞれのモフォロジー署名を含み、前記方法は、
モフォロジー基準を含むクエリを提供すること（Ｓ１）と、
前記クエリの結果として、データベースにおける各３Ｄモデル化オブジェクトを、モフォロジー基準に準拠したモフォロジー署名を有する程度に基づいて返すこと（Ｓ２）とを含む
ことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、前記モフォロジー署名は、各３Ｄモデル化オブジェクトの壁の対の組におけるそれぞれについて、各対の２つの壁同士の相対的な向きを表すラベルを含む
ことを特徴とする方法。
【請求項３】
請求項２に記載の方法であって、前記ラベルは、前記壁の対の組における前記壁に対しクリークグラフを形成する
ことを特徴とする方法。
【請求項４】
請求項２または３に記載の方法であって、前記モフォロジー署名の各ラベルは、少なくとも略平坦な壁同士の相対的な向きを表す
ことを特徴とする方法。
【請求項５】
請求項２〜４のいずれかに記載の方法であって、前記モフォロジー署名の各ラベルは、薄い壁同士の相対的な向きを表す
ことを特徴とする方法。
【請求項６】
請求項２〜５のいずれかに記載の方法であって、各ラベルは、ラベルの所定の有限集合内で決定される
ことを特徴とする方法。
【請求項７】
請求項６に記載の方法であって、各壁は、点およびそれぞれの法線ベクトルを含むそれぞれのノードに関連付けられ、ノード（ｐ1，ｎ1）に関連付けられた壁とノード（ｐ2，ｎ2）に関連付けられた壁との間の相対的な向きを表すラベルは、ｐ2から、（ｐ1，ｎ1）によって定義される平面までの距離の符号、ｐ1から、（ｐ2，ｎ2）によって定義される平面までの距離の符号、前記法線ベクトルのクロス積のノルムの符号、および／または前記法線ベクトルのスカラ積の符号に従って定義される
ことを特徴とする方法。
【請求項８】
３Ｄモデル化オブジェクトを含むデータベースであって、前記データベースは、各３Ｄモデル化オブジェクトについて、それぞれのモフォロジー署名を含むことを特徴とするデータベース。
【請求項９】
請求項８に記載のデータベースであって、前記モフォロジー署名は、各３Ｄモデル化オブジェクトの壁の対の組におけるそれぞれについて、各対の２つの壁同士の相対的な向きを表すラベルを含む
ことを特徴とするデータベース。
【請求項１０】
請求項８または９に記載にデータベースを構築する方法。
【請求項１１】
請求項１０に記載の方法であって、前記方法は、
前記モデル化オブジェクトを提供することと、
各３Ｄモデル化オブジェクトについて、当該３Ｄモデル化オブジェクトのモフォロジー署名を決定することと、
各３Ｄモデル化オブジェクトと、そのモフォロジー署名との関係を記憶することとを含む
ことを特徴とする方法。
【請求項１２】
請求項１〜７および／または１０〜１１のいずれかに記載の方法を実行するための命令を含むコンピュータプログラム。
【請求項１３】
請求項１２に記載のコンピュータプログラムおよび／または請求項８または９に記載のデータベースを記録したデータ記憶媒体。
【請求項１４】
請求項１３に記載のコンピュータプログラムおよび／または請求項８または９に記載のデータベースを記録したメモリに接続されたプロセッサを備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラム及びシステムの分野に関し、より具体的には、それぞれが機械部品を表す３Ｄモデル化オブジェクトを含むデータベースを照会するための方法、システム、およびプログラムと、そのようなデータベースに関する。
【背景技術】
【０００２】
オブジェクトの設計、エンジニアリング、製造のため、多数のシステムおよびプログラムが市場に提供されている。ＣＡＤは、コンピュータ支援設計（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ）の略語であり、例えば、オブジェクトを設計するためのソフトウェア・ソリューションに関する。ＣＡＥは、コンピュータ支援エンジニアリング（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｅｎｇｉｎｅｅｒｉｎｇ）の略語であり、例えば、将来の製品の物理的挙動をシミュレーションするためのソフトウェア・ソリューションに関する。ＣＡＭは、コンピュータ支援製造（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｍａｎｕｆａｃｔｕｒｉｎｇ）の略語であり、例えば、製造工程および動作を定義するためのソフトウェア・ソリューションに関する。このようなコンピュータ支援設計システムにおいて、グラフィカル・ユーザ・インターフェースは、技術の効率に関して、重要な役割を果たす。これらの技術は、製品ライフサイクル管理（Ｐｒｏｄｕｃｔ  Ｌｉｆｅｃｙｃｌｅ  Ｍａｎａｇｅｍｅｎｔ：  ＰＬＭ）システムに組み込むことができる。ＰＬＭとは、企業が、拡張エンタープライズの概念全体にわたって、製品データを共有し、共通の工程を適用し、構想に始まり製品寿命の終わりに至る製品開発のための企業知識を活用するのを支援するビジネス戦略を指す。ダッソー・システムズが提供するＰＬＭソリューション（製品名ＣＡＴＩＡ、ＥＮＯＶＩＡ、ＤＥＬＭＩＡ）は、製品エンジニアリング知識をオーガナイズするエンジニアリング・ハブ、製品エンジニアリング知識を管理する製造ハブ、およびエンジニアリング・ハブと製造ハブの両方に対するエンタープライズ統合と接続を可能にするエンタープライズ・ハブを提供する。全てのシステムは、製品、工程、リソースを結ぶオープンなオブジェクトモデルを提供し、最適化された製品定義、製造準備、生産およびサービスを推進する、動的な知識ベースの製品作成および意思決定支援を可能にする。
【０００３】
このような背景において、データベース内の既存の機械部品を、異なる基準に従って検索する必要がある。
【０００４】
所定の基準に従ったデータベース内の部品の検索は、多くの場合、３つのステップで実行される。第１のステップは、いわゆる「署名」または「記述子」を算出して、データベースの各立体に関連付けることである。署名は、部品の典型的な側面を合成するコンパクトな情報である。第２のステップは、ユーザが、署名を設定することによって要求を指定することである。典型的には、この署名は選択された部品のものである可能性があり、その目的は、データベースの類似の部品を見つけることであってもよい。また、署名は設計中の部品のものである可能性があり、その目的は、この場合も、データベースの類似の部品を見つけることである。第３のステップは検索ステップである。これは、システムが、ユーザが入力した署名に対応する署名を有するデータベースにおける部品を見つけるためのものである。このステップでは、署名は大量に比較される。
【０００５】
署名は、理想的には、必要とするメモリが少なく、算出が簡単で、比較が非常に速く、なおかつ高い再現率と高い適合率で、関連する結果につながるように設計することができる。
【０００６】
形状記述のための既存の署名は、多くの場合、球面関数に基づいている。特許文献１および非特許文献１ないし３は、このフレームワークを採用している既知のソリューションのリストである。
【０００７】
このような放射関数ベースの形状記述子は、トポロジおよび相対的な比率を含む、立体の全体形状を取得するように設計されている。それらは、機械の領域では問題があるとされている。
【０００８】
したがって、立体を正確に比較するために、署名には、立体の境界記述に密接に関連するジオメトリ情報が含まれることがある。特許文献２は、このフレームワークを採用している既知のソリューションである。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】欧州特許第２１６９５６７号
【特許文献２】国際公開２０１５／０８５４３５号
【非特許文献】
【００１０】
【非特許文献１】「Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors」、M．Kazhdan，T．Funkhouser著
【非特許文献２】「Eurographics Symposium on Geometry Processing」、S．Rusinkiewicz著、２００３年
【非特許文献３】「Efficient  3D  shape  matching  and  retrieval using  a  concrete  radicalized  spherical  projection  representation」、P．Papadakis，I．Pratikakis，S．Perantonis，T．Theoharis著、Pattern  Recognition  40（2007）2437-2452．
【発明の概要】
【発明が解決しようとする課題】
【００１１】
このようなジオメトリベースのソリューションでは、少なくともローカルで、類似した立体が同じ形状と同じ寸法を共有する。これは、比較的重い情報（すなわち、比較的正確なジオメトリ）が記憶され、比較されるため、メモリ消費および算出時間の点で、制限的、また禁止的であり得る。
【００１２】
したがって、既存の文献にもかかわらず、依然として、データベースにおける機械部品の検索の分野を改善する必要がある。
【課題を解決するための手段】
【００１３】
したがって、データベースを照会するための、コンピュータによって実施される方法が提供される。データベースは、それぞれが機械部品を表す３Ｄモデル化オブジェクトを含む。データベースはさらに、各３Ｄモデル化オブジェクトについて、それぞれのモフォロジー署名を含む。本方法は、モフォロジー基準を含むクエリを提供することを含む。本方法はまた、クエリの結果として、データベースの各３Ｄモデル化オブジェクトを返すことを含む。各３Ｄモデル化オブジェクトは、各３Ｄモデル化オブジェクトがモフォロジー基準に準拠したモフォロジー署名を有する程度に基づいて返される。
【００１４】
本方法は、以下のうちの１つまたは複数を含んでいてもよい。
【００１５】
・モフォロジー署名は、各３Ｄモデル化オブジェクトの壁の対の組におけるそれぞれについて、各対の２つの壁同士の相対的な向きを表すラベルを含み、
・ラベルは、壁の対の組における壁に対しクリークグラフを形成し、
・モフォロジー署名の各ラベルは、少なくとも略平坦な壁同士の相対的な向きを表し、
・モフォロジー署名の各ラベルは、薄い壁同士の相対的な向きを表し、
・各ラベルは、ラベルの所定の有限集合内で決定され、かつ／または、
・各壁は、点およびそれぞれの法線ベクトルを含むそれぞれのノードに関連付けられ、ノード（ｐ1，ｎ1）に関連付けられた壁と、ノード（ｐ2，ｎ2）に関連付けられた壁との相対的な向きを表すラベルは、ｐ2から、（ｐ1，ｎ1）によって定義される平面までの距離の符号、ｐ1から、（ｐ2，ｎ2）によって定義される平面までの距離の符号、法線ベクトルのクロス積のノルムの符号、および／または法線ベクトルのスカラ積の符号に従って定義される。
【００１６】
また、３Ｄモデル化オブジェクトを含むデータベースが提供される。データベースは、各３Ｄモデル化オブジェクトについて、それぞれのモフォロジー署名を含む。
【００１７】
一例において、各モフォロジー署名は、各３Ｄモデル化オブジェクトの壁の対の組それぞれについて、各対の２つの壁同士の相対的な向きを表すラベルを含んでいてもよい。
【００１８】
また、そのようなデータベースを構築するための方法が提供される。一例において、本方法は、モデル化オブジェクトを提供することと、各３Ｄモデル化オブジェクトについて、３Ｄモデル化オブジェクトそれぞれのモフォロジー署名を決定することと、各３Ｄモデル化オブジェクトと、それぞれのモフォロジー署名との関係を記憶することとを含んでいてもよい。
【００１９】
また、上記方法のうち、いずれか、またはいくつかを実行するための命令を含むコンピュータプログラムが提供される。
【００２０】
また、当該コンピュータプログラムを記録したデータ記憶媒体が提供される。
【００２１】
また、当該コンピュータプログラムを記録したメモリに接続されたプロセッサ備えるシステムが提供される。
【００２２】
以下、非限定的な例として、本発明の実施の形態を添付の図面を参照しつつ説明する。
【図面の簡単な説明】
【００２３】
【図１】本方法の一例のフローチャートを示す。
【図２】本方法の一例のフローチャートを示す。
【図３】同じモフォロジーを有する２つの機械部品を示す。
【図４】本システムのグラフィカル・ユーザ・インターフェースの一例を示す。
【図５】本システムの一例を示す。
【図６】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図７】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図８】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図９】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図１０】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図１１】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図１２】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【００２４】
【図１３】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図１４】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図１５】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図１６】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図１７】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図１８】データベースの例における３Ｄモデル化オブジェクトと、そのような３Ｄモデル化オブジェクトによって表される部品の絵を示す。
【図１９】本方法の例を説明する図である。
【図２０】本方法の例を説明する図である。
【図２１】本方法の例を説明する図である。
【図２２】本方法の例を説明する図である。
【図２３】本方法の例を説明する図である。
【図２４】本方法の例を説明する図である。
【図２５】本方法の例を説明する図である。
【図２６】本方法の例を説明する図である。
【図２７】本方法の例を説明する図である。
【図２８】本方法の例を説明する図である。
【図２９】本方法の例を説明する図である。
【図３０】本方法の例を説明する図である。
【図３１】本方法の例を説明する図である。
【図３２】本方法の例を説明する図である。
【図３３】本方法の例を説明する図である。
【図３４】本方法の例を説明する図である。
【図３５】本方法の例を説明する図である。
【図３６】本方法の例を説明する図である。
【図３７】本方法の例を説明する図である。
【図３８】本方法の例を説明する図である。
【図３９】本方法の例を説明する図である。
【図４０】本方法の例を説明する図である。
【図４１】本方法の例を説明する図である。
【図４２】本方法の例を説明する図である。
【図４３】本方法の例を説明する図である。
【図４４】本方法の例を説明する図である。
【図４５】本方法の例を説明する図である。
【発明を実施するための最良の形態】
【００２５】
図１のフローチャートを参照して、３Ｄモデル化オブジェクト（例えば、そのデータ）を含むデータベースを照会するための、コンピュータによって実施される方法を提案する。３Ｄモデル化オブジェクトは、機械部品を表す（すなわち、データベースの各３Ｄモデリング化オブジェクトは、機械部品、少なくともその外形を表し、例えば、「機械部品」という用語は、その集合体、および／またはその一部を総称する）。
【００２６】
データベースはさらに、各３Ｄモデル化オブジェクトについて、それぞれのモフォロジー署名を含む。言い換えれば、データベースは、各３Ｄモデル化オブジェクトと、それぞれのモフォロジー署名関数の値との関係を（例えば、ポインタおよび／またはリンクの形式で）格納する（例えば、モフォロジー署名関数は、考慮されるすべての３Ｄモデル化オブジェクトについて、予め決定された、かつ／または、同じ関数である可能性がある）。モフォロジー署名関数は、３Ｄモデル化オブジェクトの領域上で定義された関数である（したがって、考慮された３Ｄモデル化オブジェクトのそれぞれを入力とすることができる）。所与の３Ｄモデル化オブジェクトに対するモフォロジー署名関数（すなわち、前記所与の３Ｄモデル化オブジェクトのモフォロジー署名）の値は、当該３Ｄモデル化オブジェクトのモフォロジーに関する合成情報を構成する。「合成」という用語は、モフォロジー署名が、所与の３Ｄモデル化オブジェクトを定義する初期データよりも小さいデータを構成することを指す。モフォロジー署名関数は、異なるモフォロジー同士を区別する。言い換えれば、異なるモフォロジーを有する２つの３Ｄモデル化オブジェクトは、また、少なくとも統計的に一致しないモフォロジー署名も有する。しかし、同じモフォロジーを有する２つの異なる３Ｄモデル化オブジェクトは、少なくとも統計的に一致する可能性のある（例えば同一の）モフォロジー署名も有する。
【００２７】
本方法は、モフォロジー基準を含むクエリ（当該クエリを定義するデータの一部として含み、データベースの分野において非常に古典的であるように、例えば、クエリは、当該クエリを作成する可能性のあるいくつかの基準の少なくとも１つとしてモフォロジー基準を含み、例えば、クエリは、他の基準、および、場合により、異なる基準に割り当てられた重みを含む可能性がある）を提供するステップ（Ｓ１）（例えば、クライアントコンピュータシステムまたはサーバコンピュータシステム（すなわちデータベースホスト）におけるデータベース、またはそのようなデータベース上で動作するプラグイン／スクリプトに対して提供し、例えば、クライアントがサーバと混同されている可能性があり、これは例えば、これらがともに同じマシンによってホストされている場合に有りうる）を含む。本方法はまた、クエリの結果（ｒｅｓｕｌｔｓ）として（すなわち、返されるデータは、クエリおよび／または検索対象データの内容に応じて、１つまたは複数のこのような結果を含むか、あるいは、結果を含まない（ヌルの結果を含む）こともある。これは、必ずしもいくつかの結果が返されるわけではないことを意味し、複数形が用いられているのは、それが一般的な表現だからである）、データベースのそれぞれの３Ｄモデル化オブジェクトを（例えば、クライアントに対して、またはサーバにおいて）返すステップ（Ｓ２）を含む。各３Ｄモデル化オブジェクトは、各３Ｄモデル化オブジェクトがモフォロジー基準に準拠したモフォロジー署名を有する程度（言い換えれば、返されることが考えられる３Ｄモデル化オブジェクトにデータベース内で関連付けられたモフォロジー署名がモフォロジー基準に準拠する程度）に基づいて返される。「モフォロジー基準」という表現は、データベースの３Ｄモデル化オブジェクトを、それぞれのモフォロジー署名のみに基づいてフィルタリングおよび／またはランク付けする、任意の方法を指す。
【００２８】
そのような方法は、機械部品を表す３Ｄモデル化オブジェクトを含むデータベースの照会を改善する。
【００２９】
特に、本方法は、そのステップＳ１およびＳ２、およびモフォロジー署名の定義のおかげで、データベースにおけるモフォロジーに基づいて検索を実行するソリューションを提供する。これは、行為者、特に、以前設計された部品を再利用するために、それらを取得したいと考える設計者が、（とりわけ）モフォロジーの観点で機械部品について考えることが多い機械設計の分野で、特に有用である。モフォロジー署名の定義のおかげで、本方法は、比較的関連性の高い結果をＳ２で返すことを保証する。
【００３０】
各３Ｄモデル化オブジェクトのモフォロジー署名は、各３Ｄモデル化オブジェクトによって表される機械部品のモフォロジーを表す。機械部品のモフォロジーは、機械部品のスライス状の部分（または部材）の相対的な向きを表す情報であるが、寸法や比率ではない。機械部品のスライス状の部分は、略平坦な一般的な形状を有する材料の一部であり、例えば、その貫通孔および／または突起部に関係なく、例えば、その厚みに関して比較的大きく、かつ／または、比較的薄い。モフォロジー属性は、このように、機械的部品同士を区別し、類似する（すなわち同じモフォロジーを有する）部品のグループを作成する。これは、アルファベットが文字を区別し、さらには、異なる人によって、または異なるフォントを用いて書かれているという点のみにおいて互いに異なる、同じ文字の複数の実例の認識を可能にするプロセスと類似している。モフォロジーは、シンボルの類型の１つ、例えば、形状の種類のリストのうちのいずれか１つであってもよく、形状の種類は、例えば、Ｘ状、Ｔ状、Ｈ状、Ｙ状、Ｚ状、Π状、Ｏ状、Ｕ状、および／またはΩ状のいずれか１つまたは組み合わせを含む。このように、ユーザは、単にシンボルを入力することによって、あるいはそのようなシンボルに従って成形された３Ｄモデル化オブジェクトを入力することによって（すなわち、シンボルに関して考えることによって）、モフォロジー基準を入力することができる。
【００３１】
先行技術では、典型的なモフォロジーが特定されていない。従来技術は、実際、相対比率を含む寸法特性に深く関係していることが最も多く、あるいは逆に、主に寸法から独立している。例えば、図２の入力立体を考えて、データベースが図３の立体を含むと仮定することができる。これらの２つの部品は、Ω状であることを特徴とする。先行技術のアルゴリズムは、図１の方法とは対照的に、この類似したΩ状のモフォロジーを認識することができない。
【００３２】
本方法は、コンピュータにより実施される。すなわち、本方法のステップ（あるいは略全てのステップ）が少なくとも１つのコンピュータ、または類似の任意のシステムによって実行される。よって本方法のステップは、コンピュータにより、完全に自動的に、あるいは半自動的に実行される可能性がある。例えば、本方法の少なくともいくつかのステップは、ユーザとコンピュータの対話を通じて始動されてもよい。求められるユーザとコンピュータの対話レベルは、想定される自動性のレベルに応じたものであって、ユーザの要望を実装する必要性との間でバランスをとるものとしてもよい。例えば、このレベルは、ユーザが設定し、かつ／あるいは、予め定義されていてもよい。
【００３３】
本方法のコンピュータによる実施の典型的な例は、この目的に適したシステムを用いて本方法を実行することである。当該システムは、本方法を実行するための命令を含むコンピュータプログラムを記録したメモリに接続されたプロセッサ、および、グラフィカル・ユーザ・インターフェース（ＧＵＩ）を備えていてもよい。メモリは、例えばクエリが実行される、データベースを記憶していてもよい。メモリは、そのような記憶に適した任意のハードウェアであり、場合により、物理的に区別可能ないくつかの部分（例えば、プログラム用に１つ、場合によりデータベース用に１つ）を含む。したがって、システムは、クライアントサーバシステム、または単なるクライアントシステム（データベースは遠隔サーバ上に記憶され、この場合、図１の方法は、クライアントの観点から見られる）、または単なるサーバシステム（クエリはリモートクライアントシステムに由来し、図１の方法は、そのような場合にはサーバの観点から見られる）であってもよい。なお、図１の方法は、クライアントの観点から、および／またはサーバの観点から実施されても、両者とも本方法を実行するように通信するため、区別せずに見ることができる。返すこと（Ｓ２）は、実際には、能動的（データベース）または受動的（クエリを要求するクライアント）である可能性がある。
【００３４】
データベースとは、検索および取得用に最適化されたデータ（すなわち情報）の任意の集合（例えば所定の構造化言語、例えばＳＱＬに基づく、例えばリレーショナルデータベース）を意味する。データベースは、メモリに格納されると、コンピュータによる迅速な検索および取得を可能にする。データベースは、実際、様々なデータ処理動作と連動して、データの記憶、取得、修正、および削除を容易にするよう構造化されている。データベースは、それぞれ１つまたは複数のフィールドからなるレコードに分割可能な１つのファイルあるいはファイルのセットからなっていてもよい。フィールドは、データ記憶の基本単位である。ユーザは、主としてクエリによってデータを取得してもよい。ユーザは、使用されているデータベース管理システムのルールに従って、キーワードとソートコマンドを用いて、多数のレコードにおけるフィールドを、迅速に、検索、再配置、グループ化、および選択し、特定の集積データに関するレポートを取得または作成することができる。
【００３５】
本方法の場合、データベースは、機械部品を表す３Ｄモデル化オブジェクトを含む。データベースの各３Ｄモデル化オブジェクトはさらに、前記各オブジェクトのモフォロジー署名の値に対して、（使用中のデータベース技術に応じて、例えば、一列または他の任意の種類の関係で）関連付けられる。前記モフォロジー署名の値は予め定義されている（データベースのフィールドの値として定義されるか、あるいはいくつかのフィールドをカバーする。これはデータベースの最適化に関する実施の詳細であり、ここではこれ以上論じない）。このようなデータベースは、例えば、図１の照会方法で使用するために、新しい３Ｄモデル化オブジェクトを用いて構築および／またはインクリメントすることができる（データベースが適切に構成されている場合）。これには、３Ｄモデル化オブジェクトのモフォロジー署名を、各３Ｄモデル化オブジェクトについて決定することができればよい。したがって、データベースは、いかなる方法で構築されてもよく、前述のようにシステムのメモリ上に、またはそれに適した他の媒体上に格納することができる。このようなデータベースは、３Ｄモデル化オブジェクトを図１の方法に従って取得することを可能にし、したがって、（例えば、システムが再利用機能を備えている場合、設計者がすべての設計を最初から再設計するのではなく、関連する結果を検索して再利用するのを助けることによって）例えばＣＡＤ設計を加速させることができるツールである。
【００３６】
本方法は、一般に、モデル化オブジェクトを操作する。モデル化オブジェクトは、例えばデータベースに格納されたデータによって定義される任意のオブジェクトである。さらには、「モデル化オブジェクト」という表現は、データそのものも指す。システムの種類に応じて、異なる種類のデータによってモデル化オブジェクトが定義されてもよい。実際、システムは、ＣＡＤシステム、ＣＡＥシステム、ＣＡＭシステム、ＰＤＭシステム、および／またはＰＬＭシステムのうちの任意の組み合わせであってもよい。それら異なるシステムにおいて、モデル化オブジェクトは、対応するデータによって定義される。したがって、ＣＡＤオブジェクト、ＰＬＭオブジェクト、ＰＤＭオブジェクト、ＣＡＥオブジェクト、ＣＡＭオブジェクト、ＣＡＤデータ、ＰＬＭデータ、ＰＤＭデータ、ＣＡＭデータ、ＣＡＥデータについて言及することがある。しかしながら、モデル化オブジェクトは、これらのシステムの任意の組み合わせに対応するデータによって定義されてもよいため、これらのシステムは、互いに排他的なものではない。したがって、以下に示すこのようなシステムの定義から明らかなように、システムは、ＣＡＤ兼ＰＬＭシステムであってもよい。
【００３７】
ＣＡＤシステムは、少なくとも、ＣＡＴＩＡのようなモデル化オブジェクトのグラフィック表現に基づくモデル化オブジェクトの設計に適した任意のシステムをも意味する。この場合、モデル化オブジェクトを定義するデータは、モデル化オブジェクトを表現可能にするデータを含む。ＣＡＤシステムは、例えば、辺や線を用い、また、場合により面や曲面を用いて、ＣＡＤモデル化オブジェクトの表現を提供してもよい。線、辺、あるいは面は、例えば、非一様有理Ｂスプライン（ＮＵＲＢＳ）など、様々な様式で表現されてもよい。具体的には、ＣＡＤファイルは仕様を含み、その仕様に基づきジオメトリが生成可能であり、よって表現が生成可能となる。モデル化オブジェクトの仕様は１つまたは複数のＣＡＤファイルに格納されていてもよい。ＣＡＤシステムでモデル化オブジェクトを表現するファイルの典型的なサイズは、一部分あたり１メガバイトの範囲である。また、モデル化オブジェクトは、典型的には、数千の部分の集合体であってもよい。
【００３８】
ＣＡＤの文脈において、モデル化オブジェクトは、典型的には、３Ｄモデル化オブジェクト、例えば、一つの部品や部品の集合体などの製品、あるいは製品の集合体を表現するものであってもよい。「３Ｄモデル化オブジェクト」は、３Ｄ表現が可能なデータによってモデル化される任意のオブジェクトを意味する。３Ｄ表現は、その部品をすべての角度から見ることを可能にする。たとえば、３Ｄで表現された３Ｄモデル化オブジェクトは、その軸のうちの任意の軸、あるいは、その表現が表示された画面中の任意の軸を中心に、処理して回転させることが可能である。これは、特に、３Ｄモデル化されていない２Ｄアイコンについては除外される。３Ｄ表現の表示は、設計を容易にする（すなわち、設計者が作業を達成するスピードを統計的に速める）。製品の設計は製造工程の一部であるから、これによって当該産業における製造工程が迅速化する。
【００３９】
本方法において想定されるあらゆる３Ｄモデル化オブジェクトは、ＣＡＤソフトウェア・ソリューションやＣＡＤシステム等を用いた仮想的設計の完了後に実世界において製造される、（例えば、機械）部品や、部品の集合などの製品のジオメトリを表現してもよい。ＣＡＤソフトウェア・ソリューションは、航空宇宙、建築、建設、消費財、ハイテク機器、産業機器、輸送、海洋、および／または海洋石油／ガス生産、または交通を含む、限定されることのない様々な産業分野において製品の設計を可能にする。本方法において想定される３Ｄモデル化オブジェクトは、このように、地上車両の部品（例えば、自動車および軽トラック機器、レーシングカー、オートバイ、トラックおよびモーター機器、トラック、バス、電車を含む）、航空車両の部品（例えば、航空機体機器、航空宇宙機器、推進機器、防衛製品、航空路線機器、宇宙機器を含む）、海軍車両の部品（例えば、海軍用機器、商業用船舶、オフショア機器、ヨットおよび作業船、船舶用機器を含む）、一般的な機械部品（例えば、工業用製造機械、大型移動機械または機器、設置機器、産業機器製品、加工金属製品、タイヤ製造製品を含む）、電気機械部品または電子部品（例えば、家電、セキュリティおよび／または制御および／または計装製品、コンピューティングおよび通信機器、半導体、医療装置および設備を含む）、消費者製品（例えば、家具、家庭用および庭用製品、レジャー用品、ファッション用品、耐久消費財小売用品、織物類小売用品を含む）、および／または包装（例えば、食品および飲料およびたばこ、美容およびパーソナルケア、家庭用製品包装を含む）などのように、任意の機械的部品であり得る工業製品を表してもよい。モフォロジー基準がデータベースの照会を行うのに特に便利であるような、さらなる例については後述する。
【００４０】
ＰＬＭシステムは、物理的な、製造された製品（または製造される予定の製品）を表すモデル化オブジェクトの管理に適した任意のシステムを指す。ＰＬＭシステムでは、モデル化オブジェクトは、このように、物理的な物体の製造に適したデータによって定義される。これらは、典型的には、寸法の値および／または公差の値であってもよい。物体を正しく製造するために、実際、このような値を用いるのが望ましい。
【００４１】
ＣＡＭソリューションとは、製品の製造データを管理するのに適した、ハードウェアのソフトウェアである、あらゆるソリューションをも指す。製造データは、一般に、製造する製品、製造工程、および必要なリソースに関するデータを含む。ＣＡＭソリューションは、製品の製造工程全体を計画し最適化するのに用いられる。例えば、実現可能性、製造工程の期間、または製造工程における特定のステップで使用され得るリソース、例えば特定のロボットの数に関する情報をＣＡＭユーザに提供することができる。これにより、管理や必要な投資についての決定を可能にする。ＣＡＭは、ＣＡＤ工程、および、場合によりＣＡＥ工程に続く工程である。このようなＣＡＭソリューションは、ダッソー・システムズにより、ＤＥＬＭＩＡ（登録商標）として提供されている。
【００４２】
ＣＡＥソリューションとは、モデル化オブジェクトの物理的挙動の分析に適した、ハードウェアのソフトウェアである、あらゆるソリューションをも指す。よく知られており広く用いられているＣＡＥ技術は有限要素法（Ｆｉｎｉｔｅ  Ｅｌｅｍｅｎｔ  Ｍｅｔｈｏｄ：ＦＥＭ）であり、これは、典型的には、モデル化オブジェクトを、物理的挙動を方程式によって計算しシミュレーションできる要素に分割することを含む。このようなＣＡＥソリューションは、ダッソー・システムズにより、ＳＩＭＵＬＩＡ（登録商標）として提供されている。成長するＣＡＥ技術のもう１つは、ＣＡＤジオメトリデータを使用せずに異なる物理分野の複数の要素で構成される複雑なシステムのモデリングと解析を行うことを含む。ＣＡＥソリューションはシミュレーションを可能にし、それにより、製造する製品の最適化、改善および検証を可能にする。このようなＣＡＥソリューションは、ダッソー・システムズにより、ＤＹＭＯＬＡ（登録商標）として提供されている。
【００４３】
ＰＤＭはＰｒｏｄｕｃｔ  Ｄａｔａ  Ｍａｎａｇｅｍｅｎｔ（生産データ管理）の略である。ＰＤＭソリューションとは、特定の製品に関するすべての種類のデータを管理するのに適した、ハードウェアのソフトウェアである、あらゆるソリューションを指す。ＰＤＭソリューションは、製品のライフサイクルにかかわるすべての関係者によって使用されてもよい。これには、主として技術者のほか、プロジェクトマネージャー、財務担当者、営業担当者、およびバイヤーも含まれる。ＰＤＭソリューションは、一般に、製品指向のデータベースに基づく。これにより、関係者が製品に関する一貫したデータを共有することが可能になり、これにより、関係者が異なるデータを用いるのを防止する。このようなＰＤＭソリューションは、ダッソー・システムズにより、ＥＮＯＶＩＡ（登録商標）として提供されている。
【００４４】
図４は、本方法を実行するための（クライアント）システムのＧＵＩの一例を示し、本システムは、ＣＡＤシステムである。
【００４５】
ＧＵＩ２１００は、標準的なメニューバー２１１０，２１２０、ならびに底部および側面のツールバー２１４０，２１５０を有する典型的なＣＡＤのようなインターフェースであってもよい。このようなメニューバーおよびツールバーは、ユーザが選択可能なアイコンのセットを含み、各アイコンは、当技術分野で知られているように、１つまたは複数の操作または機能に関連付けられており、例えば、そのような操作／機能の１つは、図１の方法を起動することである（例えば、入力されたモデル化オブジェクト２０００に基づき、あるいは、例えば、結果として生じるモデル化オブジェクト２０００を表示させ、例えば、それはその他の結果からの選択の後に行われる）。これらのアイコンのいくつかは、ＧＵＩ２１００に表示された３Ｄモデル化オブジェクト２０００の編集および／または作業に適合したソフトウェアツールに関連付けられている。ソフトウェアツールはワークベンチに分類することができる。各ワークベンチは、ソフトウェアツールのサブセットを含む。特に、ワークベンチの１つは、モデル化製品２０００のジオメトリ的特徴を編集するのに適した編集ワークベンチである。操作中、設計者は、例えば、オブジェクト２０００の一部を予め選択し、次いで、適切なアイコンを選択することによって、操作を開始する（例えば、寸法、色などを変更する）か、ジオメトリ的制約を編集することができる。例えば、典型的なＣＡＤ操作は、スクリーン上に表示された３Ｄモデル化オブジェクトのパンチングまたは折り畳みのモデリングである。ＧＵＩは、例えば、表示された製品２０００に関連するデータ２５００を表示してもよい。図４の例では、「特徴ツリー」として表示されたデータ２５００およびそれらの３Ｄ表現２０００は、ブレーキキャリパおよびディスクを含むブレーキ部品に関するものである。ＧＵＩは、編集された製品の動作のシミュレーションを起動するため、または表示された製品２０００の様々な属性を描画するために、例えばオブジェクトの３Ｄ定位を容易にするための様々なタイプのグラフィックツール２１３０，２０７０，２０８０をさらに示してもよい。カーソル２０６０は、ユーザがグラフィックツールを用いて対話操作ができるように、触覚デバイスによって制御されてもよい。
【００４６】
図５は、本システムの一例を示すものであって、当該システムは、クライアントコンピュータシステム、例えばユーザのワークステーションである。
【００４７】
本例のクライアントコンピュータは、内部通信バス１０００に接続された中央演算処理装置（ＣＰＵ）１０１０、および同じくバスに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを備える。クライアントコンピュータは、さらに、バスに接続されたビデオランダムアクセスメモリ１１００と関連付けられたグラフィックス処理装置（ＧＰＵ）１１１０を備える。ビデオＲＡＭ１１００は、当該技術分野において、フレームバッファとしても知られる。大容量記憶装置コントローラ１０２０は、ハードドライブ１０３０などの大容量記憶装置へのアクセスを管理する。コンピュータプログラムの命令及びデータを具体的に実現するのに適した大容量メモリ装置は、例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ及びフラッシュメモリ装置のような半導体メモリ装置、内蔵ハードディスクやリムーバブルディスクなどの磁気ディスク、光磁気ディスク、およびＣＤ−ＲＯＭディスク１０４０を含む、全ての形式の不揮発性メモリを含む。前述のいずれも、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補完されてもよいし、組み入れられてもよい。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータはまた、カーソル制御装置、キーボードなどの触覚装置１０９０を含んでいてもよい。カーソル制御装置は、ユーザがディスプレイ１０８０上の任意の所望の位置にカーソルを選択的に位置させることを可能にするために、クライアントコンピュータ内で使用される。さらに、カーソル制御デバイスは、ユーザが様々なコマンドを選択し、制御信号を入力することを可能にする。カーソル制御装置は、システムに制御信号を入力するための多数の信号生成装置を含む。典型的には、カーソル制御装置はマウスであってもよく、マウスのボタンは信号を生成するために使用される。あるいは、または追加的に、クライアントコンピュータシステムは、感知パッドおよび／または感知スクリーンを備えてもよい。
【００４８】
コンピュータプログラムは、コンピュータによって実行可能な命令を含んでいてもよく、命令は、上記システムに方法を実行させるための手段を含む。プログラムは、システムのメモリを含む任意のデータ記憶媒体に記録可能であってもよい。プログラムは、例えば、デジタル電子回路、またはコンピュータハードウェア、ファームウェア、ソフトウェア、またはそれらの組み合わせで実装されてもよい。プログラムは、例えばプログラマブルプロセッサによる実行のための機械読み取り可能な記憶装置に具体的に実現された製品のような装置として実装されてもよい。方法ステップは、プログラム可能なプロセッサが命令のプログラムを実行し、入力データを操作して出力を生成することによって方法の機能を実行することによって実行されてもよい。したがって、プロセッサは、データ記憶システム、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスからデータおよび命令を受信し、また、それらにデータおよび命令を送信するようにプログラム可能であってもよく、またそのように接続されていてもよい。アプリケーションプログラムは、高水準の手続き型またはオブジェクト指向のプログラミング言語で、または必要に応じてアセンブリ言語または機械語で実装されていてもよい。いずれの場合も、言語はコンパイラ型言語またはインタープリタ型言語であってもよい。プログラムは、フルインストールプログラムまたは更新プログラムであってもよい。いずれの場合も、プログラムをシステムに適用すると、本方法を実行するための指示が得られる。
【００４９】
本方法は、３Ｄモデル化オブジェクトを設計する工程の一部であってもよく、またはそのような工程に従うことができる。「３Ｄモデル化オブジェクトの設計」とは、３Ｄモデル化オブジェクトを作り上げる工程の少なくとも一部である任意の行為あるいは一連の行為を指す。したがって、本方法は、（ユーザが）最初の３Ｄモデル化オブジェクトを、例えばスケッチのような工程を通して、一から作ることを含んでもよい。そして、本方法は、図１のクエリを（例えば、モフォロジー基準のユーザ入力に基づくユーザコマンドに応じて、あるいは、例えば、設計中のオブジェクトのモフォロジー署名に基づく自動的なバックグラウンドプロセスとして）実行することを含んでいてもよい。あるいは、モフォロジー基準は、ユーザによって直接、値として提供される。そして、本方法は、オプションとして、結果をユーザに表示することと、（少なくとも１つの結果がある場合）好ましい結果を（ユーザが）選択することを含んでいてもよい。最後に、ユーザは、クエリの結果（例えば、選択されたもの）を変更することによって、またはクエリの結果を現在の設計に追加することによって、設計を続けてもよい。これは、設計者が、以前に設計されたモデルを不必要に再設計することなく、その代わりに、そのような以前の設計を再利用するのを支援するのに役立つ。しかし、図１のクエリを実行する他の理由も考えられる。例えば、本方法は、（例えば、冗長性を排除してデータベースのサイズを縮小するために）複製された（またはほぼ複製された、すなわち非常に類似した）３Ｄモデル化オブジェクトをデータベースから探し出して、例えば削除したり、あるいは部品を同一のモフォロジーのカテゴリに、またはモフォロジーの類似性に基づいて、分類したりするのに用いてもよい。
【００５０】
本方法は、本方法を実行した後に、モデル化オブジェクトにジオメトリ的に対応する物理的製品を生産する工程を含み得る製造工程に含まれていてもよい。いずれの場合も、本方法によって設計されたモデル化オブジェクトは、製造オブジェクトを表してもよい。したがって、モデル化オブジェクトは、モデル化立体（すなわち、立体を表すモデル化オブジェクト）であってもよい。製造オブジェクトは、部品などの製品であってもよいし、または部品の集合体であってもよい。本方法は、モデル化オブジェクトの設計を改善するので、本方法はまた、製品の製造を改善し、したがって、製造工程の生産性を高める。
【００５１】
データベースは、締結具を表す３Ｄモデル化オブジェクトを含むか、またはそれらから構成されていてもよく、かつ／または、検索された３Ｄモデル化オブジェクト（例えば、モフォロジー基準で入力された３Ｄモデル化オブジェクト）が締結具を表してもよい。締結具は、２つ以上のオブジェクトを機械的に接合または固定するハードウェア装置である。そのような部品は機械設計者によってモフォロジーの観点から特によく考えられているため、そのような部品のデータベースおよび／またはそのような部品を照会することにより、図１の方法を特に効率的に利用することが可能になる。締結具の形状は、そのモフォロジーを決定する配置制約および剛性制約に適合する。主要な組立部品とは対照的に、締結具は、ある設計から別の設計に再利用できることが、より多い。これにより、図１の方法は、このような特定の状況において、特に有用となる。データベースにおける締結部は、クリップ、クリート、ストリンガ、Ｕリンク、および／または、その他の器具または組立部品のうちのいずれか１つまたは組合せを含んでいてもよい。図６〜１８は、そのような部品を表す３Ｄモデル化オブジェクトと、そのような部品の絵を示す。
【００５２】
データベースの３Ｄモデル化オブジェクトは、表現された機械部品の境界表現（Ｂ−Ｒｅｐ）を含むか、またはそれから構成されていてもよい。Ｂ−Ｒｅｐの概念は当技術分野で広く知られている。図１の方法において意図されているＢ−Ｒｅｐは、参照により本明細書に組み込まれ、互いに対応する以下の２つの文献に定義されているとおりであってもよい：ＥＰ２７５０１０７Ａ１、およびＵＳ２０１４１８８４３９Ａ１。
【００５３】
ここで、図１の方法について詳述する。
【００５４】
本方法は、機械部品を表す３Ｄモデル化オブジェクトを含むデータベースを照会するためのものである。データベースの照会とは、データベースからの情報が、照会の結果（場合によりヌル）としてデータベースから抽出されるという、データベースエンジニアリングにおけるそのような表現の古典的な意味に従って、クエリがデータベース上で実行されることを意味する。本方法の場合、データベースの３Ｄモデル化オブジェクト（すなわち、その任意の特徴データ）が、場合により、ダウンロードされる追加データのユーザによる選択および／またはユーザによる起動のために返される。これは、データベースエンジニアリングの分野、特にその３Ｄ検索への応用において、それ自体すべて知られている。
【００５５】
知られているように、クエリは、任意の種類の基準または任意の種類の複数の基準に従って実行されてもよい。結果は、データベース内のデータが基準／複数の基準に準拠する程度に基づいて（１つ、複数、またはヌルが）提供される。これは非常に古典的である。本方法の場合、クエリは、少なくとも１つのいわゆるモフォロジー基準（場合により当該モフォロジー基準のみ）、言い換えれば、モフォロジーに関連する基準、例えば、１つまたは複数のモフォロジー署名の値に関連する任意の検索基準、例えば入力され検索される３Ｄモデル化オブジェクト（その署名は本方法で算出される）を含む。これは、定義により、潜在的な結果（この時点では、データベースのデータ）がこの基準と一致する程度（いくつかの基準を扱うという問題、例えばクエリの重みを扱うことについては、古典的に対処する実施の詳細であるため、考慮しない）を評価して、情報が結果として考慮されるかどうかを評価することを意味する。この範囲をどの程度正確に評価できるかは、実施上の問題である。この程度はバイナリ（３Ｄモデル化オブジェクトのモフォロジー署名値がモフォロジー基準に準拠しているかどうか）であってもよいし、累進的（厳密には、２以上の準拠レベル、場合により最小値、例えばゼロから最大値、例えば１、これは例えば、結果が入力値と等しいモフォロジーを有するときにおける、２つの等しいモフォロジー値の場合に対応する）であってもよい。また、各３Ｄモデル化オブジェクトが、返されるべき結果であるか、あるいは各３Ｄモデル化オブジェクトについて評価した前記程度に基づいていないかが、どれだけ正確に決定されるかも、実施上の問題である。
【００５６】
例において、本方法は、所定の数の最も関連性の高い結果（例えば、他のものよりもモフォロジー基準を「準拠」する３Ｄモデル化オブジェクト）を返してもよいし、または１つだけ（例えば、「最も準拠する」１つ）を返してもよい。一例では、モフォロジー基準に準拠する程度は、バイナリ値であり、その例では、本方法は、すべての「準拠する」３Ｄモデル化オブジェクトを返す。これは、すべての結果がユーザに対して、少なくとも一度表示されることを示唆し、例えば、そのためにユーザによるスクロール操作が必要となる場合がある。例では、基準は「１０個の最良の結果」のような、あらゆる「非ブーリアン」型の基準を把握することができる。
【００５７】
一例では、モフォロジー基準は、モフォロジー署名の１つまたは複数の値である。このような各値は、それぞれの値を有する入力３Ｄモデル化オブジェクトの形態で提供されてもよい。例えば、各入力３Ｄモデル化オブジェクトのモフォロジー署名は、クエリを実行する前、例えば、クエリを起動するとすぐに、またはバックグラウンドプロセスとして事前に算出される。そのような場合、例えば、３Ｄモデル化オブジェクトは、１つまたは複数の値のうちの１つに（例えば正確にまたは実質的に）等しいモフォロジー署名を有する場合、およびその場合にのみ、モフォロジー基準に準拠する（と本方法にみなされる）としてもよい。
【００５８】
モフォロジー署名は、各３Ｄモデル化オブジェクトの壁の対の組のそれぞれについて、各対の２つの壁同士の相対的な向きを表す情報を含むか、あるいは、それにより構成されていてもよい。言い換えれば、各３Ｄモデル化オブジェクトの全ての壁が提供され、壁の対の所与の組が提供される（そのような組を決定する方法の例は後ほど提供する）。さらに、所与の組における壁の各対に対して、２つの壁同士の相対的な向きに関する情報が提供される。この情報は、一般に、１つの壁対１つの壁の相対向き情報の任意の種類のものであってよい。この情報は、各対の２つの壁同士の相対的な向きを表すラベルを含むか、あるいは、それにより構成されていてもよい。これにより、３Ｄモデル化オブジェクトによって表される機械部品のモフォロジーを効率的に把握することが可能になる。
【００５９】
モフォロジー署名は、例えば、それぞれが壁を表すノードと、２つのノード間の弧を有するグラフを含むか、またはそれからなり、各弧は、その弧を境界付けする２つのノードに対して２つの壁同士の相対的な向きを表すラベルに関連付けられている。そして、署名の比較はグラフの比較に相当し、これは高速である。グラフの比較は、どのような種類の比較であってもよく、一例では、２つのグラフが同形であるか否かを判定することに相当する（このような判定の例は後に提供する）。弧は、ラベルによって伝えられる情報が２つの壁同士の向きを必要とするか否かに応じて、有向であっても無向であってもよい。したがって、モフォロジー署名は、この「グラフ＋弧に関連付けられたラベル」というデータ構造、または「ラベル付きの弧のグラフ」を含むか、またはそれらからなっていてもよい。壁の個々の寸法および／または個々の比率に関する情報は破棄されてもよい。言い換えれば、一例では、モフォロジー署名は、壁の個々の寸法および／または個々の比率に関する情報を含まず、モフォロジー署名は、１つの壁対１つの壁の相対向き情報のみを含む。
【００６０】
一例では、ラベルは、壁の対の組における壁に対しクリークグラフを形成する。これは、定義により、壁の対の所与の組におけるすべての壁に関して、壁の各対が一意に対応する弧を有することを意味する（すなわち、ここでは、弧の任意の潜在的な方向は考慮されていない）。言い換えれば、壁の所与の組が提供され、そのような所与の組におけるすべての対がラベルに関連付けられる。さらに言い換えれば、壁の所与の組、例えば３Ｄモデル化オブジェクトの全ての壁に対して、例えば、フィルタリング基準が提供され、モフォロジー署名は、考えられるすべての壁の対について１つの壁対１つの壁の相対的な向きに関する情報を含む。これにより、所与の代表的な壁の組について、モフォロジー署名が１つの壁対１つの壁の相対的な向きに関する包括的な情報を含むので、モフォロジー署名が特に効率的になる。これは特に誤検出を減らすのに役立つ。
【００６１】
本方法は、以下のフレームワークを可能にする。機械部品は立体でモデル化され、署名はモフォロジーをキャプチャするように設計されている。モフォロジー署名を算出する方法は、２つのステップを含んでいてもよい。第１に、部品の代表的な壁を特定し、そして、例えば、点とベクトルの組によって符号化することができる。第２に、例えば点とベクトルの組の相対的な向きを捉えるためにグラフを算出することができる。モフォロジーの観点から、類似する部品を検索することは、入力部品と同じグラフ署名を特徴とするデータベース内の部品を見つけることであり得る。本方法は、ラベル付きグラフおよびラベル付きグラフマッチングを使用することができる。本方法のグラフは、弧だけでなくノードにもラベルが付いたラベル付きグラフではなく、弧のラベルのみを使用してもよい。これにより、署名がよりコンパクトになる。さらに、本方法で定義されたグラフの形態は、弧の向きを無視してもよい。グラフの構造（すなわちノードが弧によってどのように接続されているか）を介して、関連するトポロジ的態様を捉えるソリューションとは対照的に、図１の方法のグラフはクリークグラフ（ノードのすべての組を接続する弧）であってもよく、関連情報は、弧に関連付けられたラベルによって捉えられる。これにより比較が高速化される。
【００６２】
３Ｄモデル化オブジェクトの壁は、マテリアルの、略規則的なスライス状の部分を表す、互いに対向する３Ｄモデル化オブジェクトの表面の部分の対を指定する（前記マテリアルは、３Ｄモデル化オブジェクトによって表される機械部品を形成する）。したがって、壁を構成するそのような表面部分は、３Ｄモデル化オブジェクトの外面の略規則的な部分であり、例えば、場合により、貫通孔および／または比較的小さい凹凸を特徴とする部分である。このような表面部分は、以下では、「面」という用語で呼称することがあり、これは、Ｂ−Ｒｅｐ面のサブデータ、またはその縮小に対応する。面の縮小は、面の一部であって、例えば、以下で示す例における更新工程のような、縮小工程を通じて得られる。「互いに対向する」一対の面とは、２つの面のうち少なくとも１つの７５％以上の割合が他の面に直角に投影され得ることを意味してもよい。割合は１００％であってもよい。そのような組の面は平行、または略平行であってもよい。例えば、対のうち一方の面は、他方の面の少なくとも対応する部分と完全にまたは実質的に平行な部分を７５％以上有する（例えば、誤差角が閾値よりも小さく、例えば５度未満）。割合は１００％であってもよい。
【００６３】
「ラベル」とは、可算集合の任意の値を意味する。したがって、モフォロジー署名は、所与の３Ｄモデル化オブジェクトに対して、ある組について考慮することが可能であり、組の要素は、壁の対（すなわち、面対の対）である。そして、モフォロジー署名は、このようなセットの各対に対して、その対に関連付けられたラベルを含む。ラベルは、２つの壁同士の相対的な向きを表す。言い換えると、ラベルは、２つの壁が互いに対してどのように向けられているかに関する情報を提供する。「相対的な向き」という表現は、２つの壁が互いに対してどのように向けられているかに関する情報を示す。これにより、モフォロジー署名のラベルは、所定の組内で決定され得る。所定の組は、相対的な向きの分類法を表す任意の組であってもよく、決定は、いかなる方法で実行されてもよい。特に効率的な例については後述する。このように、この特定のモフォロジー署名は、壁と壁との相対向き情報を把握し、したがって、機械設計の観点から関連するモフォロジー情報を正確に伝える。
【００６４】
一緒に組み合わせることができ、モフォロジー署名を決定および／または比較するために、結果および／または迅速性の関連性についての方法の効率を高める本方法の異なる例をここで論じる。これらの例は、特に、３Ｄモデル化オブジェクトのモフォロジーを考慮する際、３Ｄモデル化オブジェクトから関連性のない情報を廃棄することにより、そのような効率の向上を達成する。
【００６５】
一例において、モフォロジー署名の各ラベルは、少なくとも略平坦な壁同士の相対的な向きを表す。言い換えれば、モフォロジー署名の関連情報を形成する各ラベルは、共に少なくとも実質的に平坦である一対の壁に関連する。さらに言い換えれば、モフォロジー署名は、少なくとも実質的に平坦ではない壁を含む一対の壁同士の相対的な向きに関する情報を含まない。「実質的に平坦」とは、壁を形成する２つの面のそれぞれについて、面の少なくとも７５％が平坦である（すなわち、平面に含まれる）ことを意味する。一例において、モフォロジー署名の各ラベルは、平坦な壁同士の相対的な向きを表す。そのような例では、完全に平坦な壁だけ（これはまた、完全に平坦な面だけであることを意味する）が、モフォロジー署名において考慮される。
【００６６】
一例において、モフォロジー署名の各ラベルは、薄い壁同士の相対的な向きを表す。言い換えれば、モフォロジー署名に関わるすべての壁は薄い壁である。さらに言い換えれば、モフォロジー署名は、薄い壁ではない壁を含む一対の壁同士の相対向きに関する情報を含まない。「薄い壁」とは、モデル化オブジェクトの厚みの平均のオーダーの厚み、例えば、モデル化オブジェクトの厚みの平均のせいぜい１０分の１（例えば４分の１）以下の厚みを有する壁である。厚みの平均は、参照によって本明細書中に援用される以下の文献のように定義されてもよい：２０１５年５月２８日出願の欧州特許出願第１５３０５８０９．４号。薄い壁は、壁の厚み（すなわち、壁の２つの面の間の平均距離または、ずれであり、これは、例えば任意のデータまたは代理で表される壁の包絡線についてのＥＰ１５３０５８０９．４の定義による平均厚みに対応し得る）を、モデル化オブジェクトによって表される立体の厚みの平均の代表データまたは代理と比較することによって認識され得る。この代表または代理は、２０１５年５月２８日出願の欧州特許出願第１５３０５８０９．４号に記載された方法のいずれかで決定されてもよく、または前記文献に記載された方法のいずれかによって決定された値に等しくてもよい。
【００６７】
一例において、モフォロジー署名の各ラベルは、比較的大きな壁同士の相対的な向きを表す。言い換えれば、モフォロジー署名に関与する全ての壁は比較的大きく、その表面が所定の閾値を超えていることを意味し、例えば、３Ｄモデル化オブジェクトの外面全体の面積に依存する。閾値は、３Ｄモデル化オブジェクトの外面全体の１０％未満の割合であってもよく、例えば５％未満、さらには３％未満、および／または０．１％より大きく、さらには０．５％より大きく、例えば１％であってもよい。
【００６８】
一例において、各ラベルは、ラベルの所定の有限集合内で決定される。言い換えれば、取りうる値の有限集合のみがラベルに提供される。したがって、壁と壁の相対的な向きの値の所定の有限集合が予め決定され、モフォロジー署名の各ラベルがこれらの値の１つとして決定される。そのような例では、モフォロジー署名は、算出が非常に速く、（必要なメモリという観点で）記憶容量が少なくなるように、ラベルの有限集合の操作に基づく。これはまた、迅速かつ単純な比較プログラムにも関連しており、これはデータアクセスが重要な大規模演算の文脈において、本方法を非常に効率的にする。そのような例における本方法は、堅牢で単純かつ迅速なモフォロジー署名の算出法を提供する。したがって、署名の算出および検索がより迅速になり、任意の形状の立体について署名を算出することができる。さらに、署名は実装が簡単で、ソフトウェアのメンテナンスも容易である。
【００６９】
ここで、図１の方法を含む全体的な工程の一例を説明し、図１９に示す。
【００７０】
本プロセスは類似部品の認識を扱う。データベースにおける各部品には署名が備えられている。これらの署名は、オフラインプロセス中に算出されて格納される。ユーザによって提供される入力部品の署名が算出され、データベース内の署名と比較される。これは、インライン（またはオンライン）プロセス中の「検索」ステップ中に実行される。入力部品の署名と同じ署名を特徴とする部品が選択され、類似部品としてユーザに提供される。
【００７１】
本方法は、このように、典型的には、Ｘ状、Ｔ状、Ｈ状、Ｙ状、Ｚ状、Π状、Ｏ状、Ｕ状、Ω状などのモフォロジー情報を捉えることが可能な署名を定義する。このリストは網羅的ではない。実際、入力部品が例えばＨ状を特徴とする場合、本方法は、予め定義された形状の辞書を参照することなく、当然、Ｈ状の部品をデータベースから報告する。
【００７２】
ここで本方法の様々な実施例について説明する。これらの実施例において、モフォロジー署名は、それぞれの３Ｄモデル化オブジェクトの壁の対の各組について、各対の２つの壁同士の相対的な向きを表すラベルを含む。また、ラベルは、壁の対の組における壁に対しクリークグラフを形成する。また、モフォロジー署名の各ラベルは、少なくとも略平坦な（例えば完全に平坦な例について後述する）壁同士の相対的な向きを表す。また、モフォロジー署名の各ラベルは、薄い壁同士の相対的な向きを表す。また、各ラベルは、ラベルの所定の有限集合内で決定される。また、各壁は、点およびそれぞれの法線ベクトルを含むノードに関連付けられている（言い換えれば、壁が関連付けられた、グラフのノードは、壁を表す、点と法線ベクトルからなる組とも関連付けられており、例えば、点は３Ｄ位置であり、かつ／または壁の重心を表し、かつ／または、法線ベクトルは３Ｄベクトルであり、かつ／または、壁に対する、例えば当該点における、法線方向を表す）。当該点に関連付けられたジオメトリおよびそれぞれの法線ベクトルは、ラベルの値を決定するのに関与する。
【００７３】
まず、署名算出の一例について説明し、図２０に示す。
【００７４】
本例の署名は、ラベル付きのグラフである。署名は、以下のステップに従って算出することができる。入力部品上で、薄い壁が認識される。次に、これらの壁のジオメトリが点とベクトルの組（ｐi，ｎi）を介して抽象化される。これらの点とベクトルの組は、グラフのノードである。２つのノードを接続する弧は、点とベクトルのノードの相対的な向きを捉えるように設計された記号でラベル付けされる。後処理により、グラフは、より比較プロセスに適したものになる。
【００７５】
ここで、薄い壁の認識の例について説明する。
【００７６】
薄い壁の認識は、平行な面の特徴的な組を識別することであってもよい。アルゴリズムは、立体の代表的な平坦な面のみを扱うものであってもよい。平坦でない面は破棄してもよい。立体の総面積の１％より小さい面積を特徴とする平坦な面も同様に廃棄されてもよい。図２１は典型的なΩ状の部品を示す。図２２は、相対面積が小さすぎるために廃棄された平坦な面を示している。３つ組（ｇi，ｖi，ａi）は、平坦な面Ｆiのそれぞれについて算出され、格納される。ここで、ｇiはその重心、ｖiはその外側法線ベクトル、ａiはその面積である。立体の代表的な厚みｔは、先に引用した２０１５年５月２８日付出願の欧州特許出願ＥＰ１５３０５８０９．４で定義されるような厚み署名σを用いて算出してもよい。厚み署名は、安全係数によって拡張されて、ｔ＝２σとなるような代表的な厚さが得られる。これらのデータは、本例の壁の認識のために集中的に使用される。
【００７７】
本例の第１ステップでは、以下の基準をチェックすることにより、面の代表的な組（ｉ，ｋ）が識別される。
【００７８】
まず、組の面は、対向する外側法線ベクトルと平行でなければならない：
【数１】
2018022476.tif 000003
図２３は、この基準に従った、非代表的な面の組を示す。
【００７９】
第２に、２つの平行な面によって画定される部分の厚みは、代表的な量のマテリアルを含まなければならない：
【数２】
2018022476.tif 000004
または同等に、
【数３】
2018022476.tif 000005
図２４は、この基準に従った、非代表的な面の組を示す。
【００８０】
第３に、平行面の相対的なずれ
【数４】
2018022476.tif 000006
は、面の大きさと比較して大き過ぎてはならない：
【数５】
2018022476.tif 000007
図２５は、この基準に従った、非代表的な面の組を示す。
【００８１】
３Ｄモデル化オブジェクトのモフォロジー署名決定の例のこの時点で、面の組が定義され、いくつかの面をいくつかの組で共有することができる。図２６は図２１〜２５の部品の例の面の組を示す。
【００８２】
この例における目標は、これらの面の組み合わせを解析して薄い壁を識別することである。いくつかの薄い壁に適切に寄与するために、いくつかの組が共有する面が更新される。薄い壁は、組（ｐ，ｎ）によって定義される。ここでｐは点であり、ｎは正規化ベクトルである。
【００８３】
以下の擬似コードが実装を示す。
【００８４】
【数６】
2018022476.tif 000008
更新シーケンスは、（ｉ，ｋ）の組を有する図２７に示すように、Ｔ字状の構成において有効である。本例では、更新シーケンス（上述のアルゴリズムのステップ０６〜１０）は、面ｋの数値データを変更する。図２８は、初期状態を示す。図２９は、面ｉ、および面ｋの一部を含む薄い壁（ｐ，ｎ）が識別された後の状況を示す。面ｋの面積を小さくし、それに応じて重心を移動させる。
【００８５】
本例を続けると、更新シーケンス（上述のアルゴリズムのステップ０６〜１０）は、面ｊに関連付けられたとき、（更新された）面ｋの数値データを再び変更する。図３０は、面ｊ、および面ｋの一部を含む薄い壁（ｐ’，ｎ’）が識別された後の状況を示す。面ｋ
の面積はより小さくなり、それに応じて重心が移動する。縮小された面ｋは、他の面に関連付けられていないため、破棄される。
【００８６】
結論として、本例の薄い壁の認識は、入力部品の薄い壁をそれぞれ表す点とベクトルのＮ個の組のリストをもたらす。ベクトルの向きは任意であるが、後で再作成することもできる（後述の例に示す）。
【００８７】
図３１は部品の例におけるＮ＝５のときの点とベクトルの組を示す。
【００８８】
ここで、グラフの定義の例について説明する。
【００８９】
グラフの各ノードは、点とベクトルの組である。ノードには１からＮの番号が付けられる。各ノードを他のすべてのノードに結合する弧が考慮される。これは、いわゆる「クリーク」グラフであり、
【数７】
2018022476.tif 000009
個の弧を特徴とする。図３２にＮ＝５で示されているように、従来、弧は小さいノード番号から大きいノード番号に向けられる。便宜上、このようなグラフは、図ではなくテーブルを用いて同等に表現してもよい。図３３のテーブルにおいて、Ｎ＝５であり、記号Ｘは不要なセルを識別する。各空のセルは、セルの行番号からセルの列番号に向けられた弧に関する情報を収集するのに使用される。
【００９０】
ここで、特に効率的な弧のラベルの例について説明する。
【００９１】
これらの例において、各壁は、上述したように、点およびそれぞれの法線ベクトルを含むそれぞれのノードに関連付けられている。そして、ノード（ｐ1，ｎ1）に関連付けられた壁とノード（ｐ2，ｎ2）に関連付けられた壁との間の相対的な向きを表すラベル（の値）が、点ｐ1およびｐ2と法線ベクトルｎ1およびｎ2とを含む少なくとも１つのジオメトリの特徴のリスト（の値）に応じて、定義される。このジオメトリの特徴のリストは、以下のジオメトリの特徴のいずれか１つまたは組み合わせを含んでいるか、またはそれらからなっていてもよい：
ｐ2から（ｐ1，ｎ1）で定義される平面までの距離の符号、
ｐ1から（ｐ2，ｎ2）で定義される平面までの距離の符号、
法線ベクトルのクロス積のノルムの符号、および／または
法線ベクトルのスカラ積の符号。
【００９２】
言い換えると、３Ｄモデル化オブジェクトのモフォロジー署名が決定されたときに弧のラベルを定義するために、本方法は、弧によって接続された壁に対するこれらのジオメトリのいずれかまたはその組合せの値を算出し、（例えば、弧の向きに応じて、または弧の向き付けを再び行って）これらの値に基づいて（例えば、所定の有限リストから）ラベルを決定することに相当してもよい。
【００９３】
これらの例の特に効率的な具体的実施例がここで提供される。弧のラベルは、以下に定義されるラベルの所定の有限集合において決定されてもよい。
【００９４】
ラベル付けの目的は、点とベクトルの２つの組の相対的な向きを３つの記号のシーケンスにエンコードすることである。このコーディングは、関連するジオメトリ的構成を捉え、容易に自動的なグラフ比較ができるように設計されている。以下において、「符号」は、「−」、「０」、あるいは「＋」の可能性がある。記号〈ｘ，ｙ〉はベクトルｘとｙのスカラ積である。
【００９５】
点とベクトルの２つの組（ｐ1，ｎ1）と（ｐ2，ｎ2）が与えられたとき、ノード（ｐ1，ｎ1）からノード（ｐ2，ｎ2）へと方向づけられた弧のラベルは、以下の量に従って定義される。ｐ2から（ｐ1，ｎ1）で定義される平面までの距離の符号、すなわち、ｄ12＝Ｓｇｎ〈ｐ2−ｐ1，ｎ1〉、ｐ1から（ｐ2，ｎ2）で定義される平面までの距離の符号、すなわち、ｄ21＝Ｓｇｎ〈ｐ1−ｐ2，ｎ2〉、ベクトルクロス積のノルムの符号
【数８】
2018022476.tif 000010
およびベクトルスカラ積の符号ｓ＝Ｓｇｎ〈ｎ1，ｎ2〉。従来、絶対値｜〈ｐ−ｑ，ｎ〉｜が厚みｔより小さいとき、Ｓｇｎ〈ｐ−ｑ，ｎ〉は０に設定する。これらの量の組み合わせは以下の通りである。
【００９６】
ｃ＝＋の場合、ベクトルｎ1、ｎ2が共線性を持たないことを意味し、９つの組
【数９】
2018022476.tif 000011
のすべてが考慮される。これらはｄ12Ａｄ21と記号化され、｛−Ａ−，−Ａ０，−Ａ＋，０Ａ−，０Ａ０，０Ａ＋，＋Ａ−，＋Ａ０，＋Ａ＋｝である。図３４は、すべての状況を示す。ｃ＝０かつｓ＝＋、つまりｎ1＝ｎ2である場合、３つの可能な組（ｄ12，ｄ21）がすべて考慮される。これらはｄ12Ｓｄ21と記号化され、｛０Ｓ０，−Ｓ＋，＋Ｓ−｝である。記号Ｓは「同じベクトル」であることを意味する。ジオメトリ上の理由から、−Ｓ−、＋Ｓ＋、０Ｓ＋、＋Ｓ０、−Ｓ０、および０Ｓ−はあり得ない。図３５は、すべての状況を示す。ｃ＝０かつｓ＝−、つまりｎ1＝ｎ2である場合、３つの可能な組（ｄ12，ｄ21）がすべて考慮される。これらはｄ12Ｒｄ21と記号化され、｛０Ｒ０，−Ｒ−，＋Ｒ＋｝である。記号Ｒは「反転ベクトル」を意味する。ジオメトリ上の理由から、−Ｒ＋、＋Ｒ−、０Ｒ＋、＋Ｒ０、−Ｒ０、および０Ｒ−はあり得ない。図３６は、すべての状況を示す。一般的に表現すると、ｉ＜ｊのとき、ノード（ｐi，ｎi）からのノード（ｐj，ｎj）までの弧のラベルは、ｄkl＝Ｓｇｎ〈ｐl−ｐk，ｎk〉、かつＸ∈｛Ａ，Ｓ，Ｒ｝のとき、ｄijＸｄjiである。
【００９７】
立体の例における点とベクトルの５つの組が図３７に示されている。この構成は、任意のベクトルの向きに基づいている。関連するラベル付きグラフは、図３８のテーブルに表される通りである。
【００９８】
ここで、後処理（例えばオフラインで発生してもよい）について説明する。この後処理は、予め定められた基準に準拠するように弧の向き（したがってラベル）を編集することに相当する。後処理は、ベクトルおよび／または弧を反転させ、それに応じてラベルを変更することを含んでいてもよい。このように、向きは全て同じ規則に準拠しており、モフォロジー署名を直接比較することができる。
【００９９】
ここで、ベクトルの反転時および／または弧の反転時にラベルがどのように変化する可能性があるかについて説明する。
【０１００】
ジオメトリの一貫性のため、上述の例におけるラベルは、弧の向きから独立したものではない。実際、弧の向きを変更するには、ラベルの記号を右から左に読む必要がある。
【０１０１】
【数１０】
2018022476.tif 000012
で表されるいわゆる「転置」演算とは、弧の向きを逆にする際にラベルを更新することである。式にすると、すべてのＸ∈｛Ａ，Ｒ，Ｓ｝およびすべてのｘ，ｙ∈｛−，０，＋｝について、Ｔｒ（ｘＸｙ）＝ｙＸｘである。
【０１０２】
ノードのベクトル方向を切り替えると、そこに入射する弧のラベルが変更される。これにより出力弧に付けられたラベルの最も左の記号が切り替わる。これにより入射弧に付けられたラベルの最も右の記号が切り替わる。また、記号０が記号Ｒに変更され、逆も同様である。
【０１０３】
図３９は、ベクトルの反転による全てのラベル変化を示す。図４０は、弧の反転による全てのラベル変化を示す。
【０１０４】
ここで、グラフの後処理の例について説明する。
【０１０５】
明らかに、与えられたジオメトリは、ラベル付けがベクトルの向きに依存するグラフを生み出す。このラベル付けを明確にするために、規則は、「−」記号の数ができるだけ少なくなるようにベクトルの向きを調整することである。これは、ｎiを−ｎiに反復的に変更し、「−」記号の数が減少していることをチェックすることによって行ってもよい。減少させることが不可能になると反復が止まる。
【０１０６】
すべてのｉ∈｛１，・・・，Ｎ｝に対して、ｉ番目の列の右の「−」記号の数をＭR（ｉ）とし、ｉ番目の列の右の「＋」記号の数をＰR（ｉ）とし、ｉ番目の行の左の「−」記号の数をＭL（ｉ）とし、ｉ番目の行の左の「−」記号の数をＰL（ｉ）とする。
【０１０７】
弧とノードの観点からは、ＭR（ｉ）は、ノードｉからの出力弧の右の「−」記号の数であり、ＰR（ｉ）は、ノードｉからの出力弧の右の「＋」記号の数であり、ＭL（ｉ）は、ノードｉに対する入力弧の左の「−」記号の数であり、ＰL（ｉ）はノードｉに対する入力弧の左の「−」記号の数である。
【０１０８】
整数関数ｂ（ｉ）は平衡関数であり、
【数１１】
2018022476.tif 000013
と定義される。
【０１０９】
これは、ベクトルｎiが逆転した場合に、「＋」記号に変更された「−」記号の数から、「−」記号に変更された「＋」記号の数を引いたものである。アルゴリズムは、平衡関数ｂ（ｉ）がすべてのベクトルｎiに対して負となると終了する。
【０１１０】
アルゴリズムは、以下のようなものであってもよい。
【０１１１】
【数１２】
2018022476.tif 000014
例えば、例のテーブルでは、ｂ（１）＝０＋０−０−４＝−４、ｂ（２）＝０＋１−１−２＝−２、ｂ（３）＝２＋１−０−１＝２、ｂ（４）＝３＋０−０−０＝３、およびｂ（５）＝３＋０−０−０＝である。
【０１１２】
図４１は、結果として得られる、「−」記号の数が最も少ないことを特徴とするテーブルの例を示す。図４２は、対応するジオメトリの例を示す。なお、ｎ3、ｎ4、およびｎ5が逆になっている。
【０１１３】
ここで、グラフの比較の例、すなわちモフォロジー署名の比較について説明する。
【０１１４】
ここでさらに、ラベル付けされた有向グラフの上述の公知の概念について説明する。
【０１１５】
グラフの比較には特別な数学的定式化が必要である。ラベル付き有向グラフは、６つ組のＧ＝（ＸG，ＵG，αG，ωG，ｔG，Ｌ）であり、ここでＸG＝｛（ｐi，ｎi），ｉ＝１，・・・，Ｎ｝は、ノードの集合であり、
【数１３】
2018022476.tif 000015
は弧の集合であり、
【数１４】
2018022476.tif 000016
は弧のラベルの集合であり、
【数１５】
2018022476.tif 000017
は弧の開始ノードを定義し、
【数１６】
2018022476.tif 000018
は弧の終了ノードを定義し、
【数１７】
2018022476.tif 000019
は、ラベルを各弧に関連付ける。
【０１１６】
入力部品が与えられると、そのグラフ署名が算出され、検索プロセスは、データベース内で類似のグラフ署名を見つけることである。したがって、プロセスの中核は、入力部品のグラフ署名とデータベースのグラフ署名とを比較することである。入力部品のグラフ署名は、Ｇ  ＝（ＸG，ＵG，αG，ωG，ｔG，Ｌ）で表される。データベースの部品のグラフ署名は、Ｈ＝ＸH，ＵH，αH，ωH，ｔ２，Ｌ）で表される。なお、ラベルの集合Ｌは両方のグラフについて同じである。
【０１１７】
ここで、グラフの同型写像という公知の概念について説明する。
【０１１８】
定義により、グラフＧとＨとの同型写像は、１対１のマッピング
【数１８】
2018022476.tif 000020
および
【数１９】
2018022476.tif 000021
の組である。マッピングｆはグラフＧの各ノードをグラフＨのノードに関連付ける。マッピングｇはグラフＧの各弧をグラフＨの弧に関連付ける。また、マッピングｆおよびｇは、すべてのｕ∈ＵGについて、図４３に示すようにｆ（αG（ｕ））＝αH（ｇ（ｕ））およびｆ（ωG（ｕ））＝ωH（ｇ（ｕ））であるか、あるいは、図４４に示すようにｆ（αG（ｕ））＝ωH（ｇ（ｕ））およびｆ（ωG（ｕ））＝αH（ｇ（ｕ））である。
【０１１９】
ここでラベル互換グラフ同型写像について説明する。
【０１２０】
定義により、同型写像ｆ、ｇは、さらに、関連する弧が、弧の向きに従って等価なラベルを有する場合、ラベル互換性がある。これは、前述のラベル転置を使用する、以下のＳａｍｅＬａｂｅｌ（ｕ，ｖ）関数によって実装される。
【０１２１】
【数２０】
2018022476.tif 000022
ＳａｍｅＬａｂｅｌ（ｕ，ｖ）関数の擬似コードは、以下のように読むこともできる。
【０１２２】
弧ｕの開始ノードが弧ｖの開始ノードにマッピングされ、弧ｕの終了ノードが弧ｖの終了ノードにマッピングされる場合において、
弧ｕおよびｖが同じラベルを有する場合、「ｔｒｕｅ」を返し
そうでない場合において、弧ｕの開始ノードが弧ｖの終了ノードにマッピングされ、弧ｕの終了ノードが弧ｖの開始ノードにマッピングされる場合、
弧ｕのラベルが弧ｖの転置ラベルと同じである場合、「ｔｒｕｅ」を返す。
条件分岐終了（ＥＮＤ  ＩＦ）
「ｆａｌｓｅ」を返す
【０１２３】
ここで、比較アルゴリズムの実装について説明する。
【０１２４】
グラフＧとＨの比較アルゴリズムは、２つのグラフ間にラベル互換同型写像を構築することであってもよい（言い換えれば、データベース内の３Ｄモデル化オブジェクトはモフォロジー基準に準拠すると考えられ、そのような互換同型写像が構築できる場合にのみ返される）。これは、Ａ＝（ＸA，ＵA，αA，ωA）、およびＢ＝（ＸB，ＵB，αB，ωB）でそれぞれ表される２つの作業グラフを必要としてもよい。グラフＡはグラフＧのサブグラフであり、グラフＢはグラフＨのサブグラフである。これらは、空のグラフで初期化される。以下のステップ０３で使用される関数マップ（Ａ，ａ，Ｂ，ｂ）は、同型写像を更新し、ラベル互換性をチェックする。これについては後で詳述する。以下のステップ０４および０５におけるノードの追加については後で詳述する。全体的なアルゴリズムは以下のとおりである。
【０１２５】
【数２１】
2018022476.tif 000023
上述のアルゴリズムのステップ０４における「Ａｄｄ  ｎｏｄｅ  ａ  ｔｏ  ｇｒａｐｈ  Ａ」という命令は、ノードａをグラフＡのノードの集合ＸAに追加し、グラフＡの弧の集合ＵAにグラフＧのすべての弧を追加してノードａをＸAのノードに加えるものである。
【０１２６】
上述のアルゴリズムのステップ０５における「Ａｄｄ  ｎｏｄｅ  ｂ  ｔｏ  ｇｒａｐｈ  Ｂ」という命令は、ノードｂをグラフＢのノードの集合ＸBに追加し、グラフＢの弧の集合ＵBにグラフＨのすべての弧を追加してノードｂをＸBのノードに加えるものである。
【０１２７】
関数マップ（Ａ，ａ，Ｂ，ｂ）の目的は、ノードａを追加したグラフＡとノードｂを追加したグラフＢの同型写像（ｆ，ｇ）を更新することである。これは、以下のステップ０１および０７で、新しい値をマッピングｆおよびｇに設定することによって行われる。また、以下のステップ０６で、更新された同型写像のラベル互換性もチェックする。以下のステップ０２、０３、および０５で調査した接続は、弧の向きを考慮しない。ステップＳ０６の関数ＳａｍｅＬａｂｅｌ（ｕ，ｖ）は、上述のように、弧の向きに従って弧ｕ∈ＵGおよびｖ∈ＵHのラベルを比較する。
【０１２８】
【数２２】
2018022476.tif 000024
図４５は、マップ（Ａ，ａ，Ｂ，ｂ）関数環境を示す。
【図１】
2018022476.tif 000025
【図２】
2018022476.tif 000026
【図３】
2018022476.tif 000027
【図４】
2018022476.tif 000028
【図５】
2018022476.tif 000029
【図６】
2018022476.tif 000030
【図７】
2018022476.tif 000031
【図８】
2018022476.tif 000032
【図９】
2018022476.tif 000033
【図１０】
2018022476.tif 000034
【図１１】
2018022476.tif 000035
【図１２】
2018022476.tif 000036
【図１３】
2018022476.tif 000037
【図１４】
2018022476.tif 000038
【図１５】
2018022476.tif 000039
【図１６】
2018022476.tif 000040
【図１７】
2018022476.tif 000041
【図１８】
2018022476.tif 000042
【図１９】
2018022476.tif 000043
【図２０】
2018022476.tif 000044
【図２１】
2018022476.tif 000045
【図２２】
2018022476.tif 000046
【図２３】
2018022476.tif 000047
【図２４】
2018022476.tif 000048
【図２５】
2018022476.tif 000049
【図２６】
2018022476.tif 000050
【図２７】
2018022476.tif 000051
【図２８】
2018022476.tif 000052
【図２９】
2018022476.tif 000053
【図３０】
2018022476.tif 000054
【図３１】
2018022476.tif 000055
【図３２】
2018022476.tif 000056
【図３３】
2018022476.tif 000057
【図３４】
2018022476.tif 000058
【図３５】
2018022476.tif 000059
【図３６】
2018022476.tif 000060
【図３７】
2018022476.tif 000061
【図３８】
2018022476.tif 000062
【図３９】
2018022476.tif 000063
【図４０】
2018022476.tif 000064
【図４１】
2018022476.tif 000065
【図４２】
2018022476.tif 000066
【図４３】
2018022476.tif 000067
【図４４】
2018022476.tif 000068
【図４５】
2018022476.tif 000069
【外国語明細書】
2018022476.tif 000070
2018022476.tif 000071
2018022476.tif 000072
2018022476.tif 000073
2018022476.tif 000074
2018022476.tif 000075
2018022476.tif 000076
2018022476.tif 000077
2018022476.tif 000078
2018022476.tif 000079
2018022476.tif 000080
2018022476.tif 000081
2018022476.tif 000082
2018022476.tif 000083
2018022476.tif 000084
2018022476.tif 000085
2018022476.tif 000086
2018022476.tif 000087
2018022476.tif 000088
2018022476.tif 000089
2018022476.tif 000090
2018022476.tif 000091
2018022476.tif 000092
2018022476.tif 000093
2018022476.tif 000094
2018022476.tif 000095
2018022476.tif 000096
2018022476.tif 000097
2018022476.tif 000098
2018022476.tif 000099
2018022476.tif 000100
2018022476.tif 000101
2018022476.tif 000102
2018022476.tif 000103
2018022476.tif 000104
2018022476.tif 000105
【図１】
2018022476.tif 000106
【図２】
2018022476.tif 000107
【図３】
2018022476.tif 000108
【図４】
2018022476.tif 000109
【図５】
2018022476.tif 000110
【図６】
2018022476.tif 000111
【図７】
2018022476.tif 000112
【図８】
2018022476.tif 000113
【図９】
2018022476.tif 000114
【図１０】
2018022476.tif 000115
【図１１】
2018022476.tif 000116
【図１２】
2018022476.tif 000117
【図１３】
2018022476.tif 000118
【図１４】
2018022476.tif 000119
【図１５】
2018022476.tif 000120
【図１６】
2018022476.tif 000121
【図１７】
2018022476.tif 000122
【図１８】
2018022476.tif 000123
【図１９】
2018022476.tif 000124
【図２０】
2018022476.tif 000125
【図２１】
2018022476.tif 000126
【図２２】
2018022476.tif 000127
【図２３】
2018022476.tif 000128
【図２４】
2018022476.tif 000129
【図２５】
2018022476.tif 000130
【図２６】
2018022476.tif 000131
【図２７】
2018022476.tif 000132
【図２８】
2018022476.tif 000133
【図２９】
2018022476.tif 000134
【図３０】
2018022476.tif 000135
【図３１】
2018022476.tif 000136
【図３２】
2018022476.tif 000137
【図３３】
2018022476.tif 000138
【図３４】
2018022476.tif 000139
【図３５】
2018022476.tif 000140
【図３６】
2018022476.tif 000141
【図３７】
2018022476.tif 000142
【図３８】
2018022476.tif 000143
【図３９】
2018022476.tif 000144
【図４０】
2018022476.tif 000145
【図４１】
2018022476.tif 000146
【図４２】
2018022476.tif 000147
【図４３】
2018022476.tif 000148
【図４４】
2018022476.tif 000149
【図４５】
2018022476.tif 000150