(57)【要約】      （修正有）【課題】３Ｄシーン内において３Ｄモデル化オブジェクトの位置を特定する際に精度や関連性や演算時間を改善する必要がある。【解決手段】３Ｄシーン内において、３Ｄモデル化オブジェクトの位置決めを行うことを含む。位置決めは、３Ｄモデル化オブジェクトの２つの３Ｄ点と、そのそれぞれに関連付けられた法線ベクトルからなる第１の対のそれぞれについて、３Ｄシーンの２つの３Ｄ点と、そのそれぞれに関連付けられた法線ベクトルとからなる第２の対のそれぞれとの一致に対して報酬を与えるアルゴリズムに従って実行される。第１の対と第２の対との一致は、第１の対の記述子の値と前記第２の対の記述子の値とが実質的に等価であることに相当する。記述子は、鏡面対称性の下で可変である。これにより、３Ｄシーン内における３Ｄモデル化オブジェクトの位置特定が改善される。【選択図】図１
2017168081.tif 000002
【特許請求の範囲】
【請求項１】
３Ｄシーン内において３Ｄモデル化オブジェクトの位置を特定するための、コンピュータによって実施される方法であって、３Ｄモデル化オブジェクトおよび３Ｄシーンのそれぞれが３Ｄ点を含み、各３Ｄ点はそれぞれの法線ベクトルに関連付けられ、前記方法は、
前記３Ｄシーン内において前記３Ｄモデル化オブジェクトの位置決めを行うステップを含み、
前記位置決めは、３Ｄモデル化オブジェクトの２つの３Ｄ点と、そのそれぞれに関連付けられた法線ベクトルからなる、第１の対のそれぞれについて、前記３Ｄシーンの２つの３Ｄ点と、そのそれぞれに関連付けられた法線ベクトルとからなる、第２の対のそれぞれとの一致に対して報酬を与えるアルゴリズムに従って実行され、
前記第１の対は実質的に前記第２の対の上に配置され、
前記第１の対と前記第２の対との一致は、前記第１の対の記述子の値と前記第２の対の記述子の値とが実質的に等価であることに相当し、
前記記述子は鏡面対称性の下で可変である
ことを特徴とする方法。
【請求項２】
対（（ｐ1，ｎ1），（ｐ2，ｎ2））∈ＰM∪ＰSの記述子は、
【数１】
2017168081.tif 000093
のタイプの項を含むベクトルであって、
【数２】
2017168081.tif 000094
は単位球であり、
【数３】
2017168081.tif 000095
は、３Ｄ点と法線ベクトルからなる対の集合であり、
Ｍは、Ｋの有限部分集合を含む前記３Ｄモデル化オブジェクトであり、すべてのｉについて、
【数４】
2017168081.tif 000096
のとき
【数５】
2017168081.tif 000097
であり、
Ｓは、Ｋの有限部分集合を含む前記３Ｄシーンであり、すべてのｉについて、
【数６】
2017168081.tif 000098
のとき
【数７】
2017168081.tif 000099
であり、
ＰMはＭの要素の全ての対の集合であって、
【数８】
2017168081.tif 000100
であり、
ＰSはＳの要素の全ての対の集合であって、
【数９】
2017168081.tif 000101
であり、
ｑ＝ｐ2−ｐ1である
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記記述子は、
【数１０】
2017168081.tif 000102
のタイプのマッピング
【数１１】
2017168081.tif 000103
に従って算出され、
【数１２】
2017168081.tif 000104
がベクトルｕおよびｖのスカラ積である
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記第１の対の記述子の値と前記第２の対の記述子の値が実質的に等価であることは、前記第１の対の記述子の値に対応する第１の整数と前記第２の対の記述子の値に対応する第２の整数が実質的に等価であることであり、
前記第１の整数と前記第２の整数は、前記第１の対の記述子の値と前記第２の対の記述子の値にそれぞれ適用される量子化マッピングを介して算出される
ことを特徴とする請求項１、２、または３に記載の方法。
【請求項５】
前記量子化マッピングは、合成
【数１３】
2017168081.tif 000105
によって定義される
【数１４】
2017168081.tif 000106
のタイプであり、全ての（（ｐ1，ｎ1），（ｐ2，ｎ2））∈ＰM∪ＰSについて、
【数１５】
2017168081.tif 000107
であり、
（（ｐ1，ｎ1），（ｐ2，ｎ2））∈ＰM∪ＰSのとき、Ｈ＝Ｆ（ＰM∪ＰS）は、４つの要素からなる全てのＦ（ｐ1，ｎ1，ｐ2，ｎ2）の有限集合であり、
【数１６】
2017168081.tif 000108
は、量子化マッピングであって、
【数１７】
2017168081.tif 000109
であり、
【数１８】
2017168081.tif 000110
であって、ｑiは、４つの要素からなる任意の（ｒ1，ｒ2，ｒ3，ｒ4）∈Ｈが与えられた場合、ｉ＝１，・・・，４について定義される整数であり、
δiは、ｉ＝１，・・・，４について
【数１９】
2017168081.tif 000111
で定義される整数であって、［ｒ］は、与えられた実数ｒ以下の最大の整数を表し、
ｉ＝１，・・・，４について、δiは、前記量子化の解像度を表す４つの実数であり、
ｉ＝１，・・・，４である
【数２０】
2017168081.tif 000112
は、ｉ＝１，・・・，４および全ての（ｒ1，ｒ2，ｒ3，ｒ4）∈Ｈについて
【数２１】
2017168081.tif 000113
である８つの実数である
ことを特徴とする請求項４に記載の方法。
【請求項６】
前記量子化の解像度は
【数２２】
2017168081.tif 000114
に等しいか、少なくとも±５０％である
ことを特徴とする請求項５に記載の方法。
【請求項７】
前記アルゴリズムは、一致する第２の対上の第１の対を位置させる全ての位置決めの中で最良の投票に対応し、
前記最良の投票は、前記３Ｄモデル化オブジェクトに含まれる３Ｄポイントの３つのアンカーポイントを実質的に同じように位置させる最大の位置決めグループを保持する
ことを特徴とする請求項１〜６のいずれかに記載の方法。
【請求項８】
前記アンカーポイントはモデルＭの整列されていない３つの点であり、好ましくはＡ＝（ｍ1，ｍ2，ｍ3）で表され、
【数２３】
2017168081.tif 000115
を満たす
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記最大の位置決めグループの位置決めが全て前記３つのアンカーポイントを所定の３×３Ｄグリッドの同じセル内に位置させる
ことを特徴とする請求項７または８に記載の方法。
【請求項１０】
前記実質的に等価であることは、前記第１の整数と前記第２の整数が完全に等価であることに相当する
ことを特徴とする請求項１〜９のいずれかに記載の方法。
【請求項１１】
前記アルゴリズムは、第２の対上で実行され、実行中のそれぞれの第２の対に一致するすべての第１の対にアクセスし、アクセスした第２の対上に実質的に配置される第１の対に対して報酬を与える３Ｄシーン内における３Ｄモデル化オブジェクトの位置決めを出力する
ことを特徴とする請求項１〜１０のいずれかに記載の方法。
【請求項１２】
前記アルゴリズムは、一致する第２の対上の第１の対を位置させる全ての剛体運動の中で最良の投票に対応し、
各剛体運動は、それぞれの第１の対に付された正規直交軸系と、それぞれの第２の対に付された正規直交軸系のみに基づいて決定され、
各正規直交軸系は、前記２つの点のうちの１つとそれぞれに関連付けられた法線ベクトルのみに基づいて、第１の対と第２の対から決定される
ことを特徴とする請求項１〜１１のいずれかに記載の方法。
【請求項１３】
請求項１〜１２のいずれかに記載の方法を実行するための命令を含むコンピュータプログラム。
【請求項１４】
請求項１３に記載のコンピュータプログラムを記録したコンピュータ読み取り可能記憶媒体。
【請求項１５】
請求項１３に記載のコンピュータプログラムを記録したメモリに接続されたプロセッサと、グラフィカル・ユーザ・インターフェイスとを備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータプログラムおよびシステムの分野に関連し、より詳細には、３Ｄシーンにおける３Ｄモデル化オブジェクトの位置特定のための方法、システム、およびプログラムに関する。
【背景技術】
【０００２】
オブジェクトの設計、エンジニアリング、製造のため、多数のシステムおよびプログラムが市場に提供されている。ＣＡＤは、コンピュータ支援設計（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ）の略語であり、例えば、オブジェクトを設計するためのソフトウェア・ソリューションに関する。ＣＡＥは、コンピュータ支援エンジニアリング（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｅｎｇｉｎｅｅｒｉｎｇ）の略語であり、例えば、将来の製品の物理的挙動をシミュレーションするためのソフトウェア・ソリューションに関する。ＣＡＭは、コンピュータ支援製造（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｍａｎｕｆａｃｔｕｒｉｎｇ）の略語であり、例えば、製造工程および動作を定義するためのソフトウェア・ソリューションに関する。このようなコンピュータ支援設計システムにおいて、グラフィカル・ユーザ・インターフェイスは、技術の効率に関して、重要な役割を果たす。これらの技術は、製品ライフサイクル管理（Ｐｒｏｄｕｃｔ  Ｌｉｆｅｃｙｃｌｅ  Ｍａｎａｇｅｍｅｎｔ：  ＰＬＭ）システムに組み込むことができる。ＰＬＭとは、企業が、拡張エンタープライズの概念全体にわたって、製品データを共有し、共通の工程を適用し、構想に始まり製品寿命の終わりに至る製品開発のための企業知識を活用するのを支援するビジネス戦略を指す。ダッソー・システムズが提供するＰＬＭソリューション（製品名ＣＡＴＩＡ、ＥＮＯＶＩＡ、ＤＥＬＭＩＡ）は、製品エンジニアリング知識をオーガナイズするエンジニアリング・ハブ、製品エンジニアリング知識を管理する製造ハブ、およびエンジニアリング・ハブと製造ハブの両方に対するエンタープライズ統合と接続を可能にするエンタープライズ・ハブを提供する。全てのシステムは、製品、工程、リソースを結ぶオープンなオブジェクトモデルを提供し、最適化された製品定義、製造準備、生産およびサービスを推進する、動的な知識ベースの製品作成および意思決定支援を可能にする。
【０００３】
これらのシステムは、コンピュータビジョンおよび／または仮想現実の分野に入るか、あるいは重なる可能性がある。これらの分野では、３Ｄシーン内において３Ｄモデル化オブジェクトの位置特定を行う異なる解決策が存在する。３Ｄモデル化オブジェクトおよび３Ｄシーンはそれぞれ３Ｄ点を含み、各３Ｄ点はそれぞれの法線ベクトルに関連付けられている。そのような３Ｄシーンでそのような３Ｄモデル化オブジェクトの位置特定を行うことは、実際、３Ｄ再構成（例えば、ｓｔｒｕｃｔｕｒｅ−ｆｒｏｍ−ｍｏｔｉｏｎ解析またはマルチビュー再構成）や仮想現実（例えば、マーカーレス拡張現実）など、多くのアプリケーションにとって有用であると考えられる。これらのアプリケーションにおいて、３Ｄシーンにおいて特定の３Ｄモデル化オブジェクトの位置特定を行うことにより、幾つかの既知の方法でエクスペリエンスを改善できる可能性がある。
【０００４】
こうした状況において、いくつかの解決法は、３Ｄシーン内において３Ｄモデル化オブジェクトの位置決めを含む方法を開示する。位置決めは、３Ｄモデル化オブジェクトの２つの３Ｄ点と、それらに関連付けられた法線ベクトルからなる、第１の対の各々について、３Ｄシーンの２つの３Ｄ点と、それらに関連付けられた法線ベクトルとからなる、第２の対のそれぞれとの一致に対して報酬を与えるアルゴリズムに従って実行され、第１の対は実質的に第２の対上に配置され、第１の対と第２の対の一致は、第１の対の記述子の値と第２の対の記述子の値とが実質的に等しいことに相当する。そのようなタイプの解決策の特徴的な例として、文献「Bertram Drost,Slobodan Ilic, 3D Object Detection and Localization using Multimodal Point Pair Features, Conference on 3D Imaging,Modeling,Processing,Visualization and Transmission(3DIMPVT),2012」、文献「Bertram Drost,Markus Ulrich,Nassir Navab,Slobodan Ilic,Model Globally,Match Locally:Efficient and Robust 3D Object Recognition,Conference on Computer vision and pattern recognition(CVPR),2010」、および欧州特許ＥＰ２３８５４８３がある。
【０００５】
しかしながら、依然として、３Ｄシーンにおける３Ｄモデル化オブジェクトの位置を特定する際の結果の精度や関連性、および／または演算時間を改善する必要がある。
【発明の概要】
【０００６】
したがって、３Ｄシーン内において３Ｄモデル化オブジェクトの位置を特定するための、コンピュータによって実施される方法が提供される。３Ｄモデル化オブジェクトと３Ｄシーンは、それぞれ３Ｄ点を含む。各３Ｄ点はそれぞれの法線ベクトルに関連付けられている。本方法は、３Ｄシーン内において３Ｄモデル化オブジェクトの位置決めを行うことを含む。位置決めは、アルゴリズムに従って行う。当該アルゴリズムは、第１の対のそれぞれについて、第２の対のそれぞれとの一致に対して報酬を与える。第１の対は、３Ｄモデル化オブジェクトの２つの３Ｄ点と、それらに関連付けられた法線ベクトルからなる。第２の対は、３Ｄシーンの２つの３Ｄ点と、それらに関連付けられた法線ベクトルとからなる。第１の対は、実質的に第２の対上に配置される。第１の対と第２の対の一致は、第１の対の記述子の値と第２の対の記述子の値が実質的に等価であることに相当する。
【０００７】
少なくともこのうちの一部が、後述する方法を含む多くの方法で実行可能であり、さらには文献「Ｂｅｒｔｒａｍ  Ｄｒｏｓｔ，Ｓｌｏｂｏｄａｎ  Ｉｌｉｃ，  ３Ｄ  Ｏｂｊｅｃｔ  Ｄｅｔｅｃｔｉｏｎ  ａｎｄ  Ｌｏｃａｌｉｚａｔｉｏｎ  ｕｓｉｎｇ  Ｍｕｌｔｉｍｏｄａｌ  Ｐｏｉｎｔ  Ｐａｉｒ  Ｆｅａｔｕｒｅｓ，  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ３Ｄ  Ｉｍａｇｉｎｇ，Ｍｏｄｅｌｉｎｇ，Ｐｒｏｃｅｓｓｉｎｇ，Ｖｉｓｕａｌｉｚａｔｉｏｎ  ａｎｄ  Ｔｒａｎｓｍｉｓｓｉｏｎ（３ＤＩＭＰＶＴ），２０１２」、文献「Ｂｅｒｔｒａｍ  Ｄｒｏｓｔ，Ｍａｒｋｕｓ  Ｕｌｒｉｃｈ，Ｎａｓｓｉｒ  Ｎａｖａｂ，Ｓｌｏｂｏｄａｎ  Ｉｌｉｃ，Ｍｏｄｅｌ  Ｇｌｏｂａｌｌｙ，Ｍａｔｃｈ  Ｌｏｃａｌｌｙ：Ｅｆｆｉｃｉｅｎｔ  ａｎｄ  Ｒｏｂｕｓｔ  ３Ｄ  Ｏｂｊｅｃｔ  Ｒｅｃｏｇｎｉｔｉｏｎ，Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ｖｉｓｉｏｎ  ａｎｄ  ｐａｔｔｅｒｎ  ｒｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ），２０１０」に開示された特定の方法、あるいは欧州特許ＥＰ２３８５４８３に開示された特定の方法で実行することが可能であり、それぞれ、そこで知られている利点をともなう。これら３つの開示が参照によりここに組み込まれる。しかしながら、ここでは特に以下が提案される。
【０００８】
記述子は、鏡面対称（すなわち、平面に対する対象）の下で可変である。記述子がこのような特定の可変性を有するため、本方法は、比較的「誤検出」が少ない位置特定を提供する。実際、先行技術の方法とは対照的に、本方法は、３Ｄモデル化オブジェクトが対称性（だけ）を有しているシーンにおいて３Ｄモデル化オブジェクトの位置特定を行わない。言い換えると、本方法では、２つの対称なオブジェクトを区別するが（これは良いことである。なぜなら２つのオブジェクトが数学的に対称であっても異なる物理的オブジェクトに対応する可能性があるため、これらは現実的なアプリケーションでは区別されるのが好ましいからである）、一方、従来技術に含まれる数学ではこの区別ができない。
【０００９】
さらには、当該方法を実行するための命令を含むコンピュータプログラムが提供される。
【００１０】
さらには、当該コンピュータプログラムを記録したコンピュータ読み取り可能記憶媒体が提供される。
【００１１】
さらには、当該コンピュータプログラムを記録したメモリに接続されたプロセッサと、グラフィカル・ユーザ・インターフェイスとを備えるシステムが提供される。
【図面の簡単な説明】
【００１２】
【図１】本方法の一例についてのフローチャートを示す。
【図２】本システムのグラフィカル・ユーザ・インターフェイスの一例を示す。
【図３】本システムの一例を示す。
【図４】本方法を例示した図である。
【図５】本方法を例示した図である。
【図６】本方法を例示した図である。
【図７】本方法を例示した図である。
【図８】本方法を例示した図である。
【図９】本方法を例示した図である。
【図１０】本方法を例示した図である。
【図１１】本方法を例示した図である。
【図１２】本方法を例示した図である。
【図１３】本方法を例示した図である。
【図１４】本方法を例示した図である。
【図１５】本方法を例示した図である。
【図１６】本方法を例示した図である。
【図１７】本方法を例示した図である。
【図１８】本方法を例示した図である。
【図１９】本方法を例示した図である。
【図２０】本方法を例示した図である。
【図２１】本方法を例示した図である。
【図２２】本方法を例示した図である。
【発明を実施するための形態】
【００１３】
図１のフローチャートを参照して、３Ｄシーン（例えば、現実の環境を表すもの、例えば、センサを介して取得されたもの）における３Ｄモデル化オブジェクト（例えば、現実の物体を表すもの、例えば、物理的な製品を表すもの、センサを介して取得されたもの、あるいはユーザによって設計されたもの）の位置を特定（すなわち、位置に関する情報を出力）するための、コンピュータによって実施される方法が提案される。３Ｄモデル化オブジェクトおよび３Ｄシーンは、それぞれ、３Ｄ点（例えば、他のタイプの所定のデータに基づいて、例えば、所定の、あるいは方法内で決定された、ジオメトリ／形状の表現）を含み、各３Ｄ点はそれぞれの法線ベクトル（例えば、３Ｄ点など、他のタイプの所定のデータに基づいて、例えば、所定の、あるいは方法内で決定された、ジオメトリ／形状に対する面法線の表現）に関連付けられている（すなわち、特定のリンクデータ、例えば、ポインタ、あるいは各３Ｄ点について関連データの取得を可能にする他の任意のデータを用いて、リンクされている）。本方法は、３Ｄシーン内において３Ｄモデル化オブジェクトの位置決めを行うステップ（Ｓ１０）（すなわち、１つまたは複数の３Ｄ位置を提供するルール／機能を記述するデータを決定する任意の演算）を含む。
【００１４】
後に詳述するように、３Ｄモデル化オブジェクトは、物体（例えば、製品のような、仮想または現実の物体、例えば、機械部品または消費者製品のような、部品、または部品の集合体）を表し、その３Ｄ表現を可能にする任意のデータセットである。３Ｄシーンもまた３Ｄモデル化オブジェクトであり、３Ｄモデル化オブジェクトによって（本方法の位置特定に基づき）表された物体が配置される可能性のある環境（すなわち、物体のセット／集合体およびそれらの間の空きスペース）を表す。３Ｄシーンは、仮想シーンあるいは現実シーンの表現（例えば、３Ｄモデル化オブジェクトによって表される現実の物体の１つのバージョンを含んでいる可能性がある）であってもよく、例えば、ＲＧＢデータおよび／または深度データおよび／または光学データなど、物理センサを介して取得されたジオメトリを含む（例えば、ｓｔｒｕｃｔｕｒｅ−ｆｒｏｍ−ｍｏｔｉｏｎ解析および／またはＲＧＢ深度再構成、または他の任意の、センサに基づく３Ｄ再構成のような、３Ｄ再構成を介して得られた任意の３Ｄシーン）。本方法は、このような３Ｄシーンにおける３Ｄモデル化オブジェクト（これは上述のようなセンサに基づく任意の３Ｄ再構成を介して、あるいはユーザが３Ｄモデル化オブジェクトを例えばＣＡＤシステムで設計することによって得られる）の位置特定を行うためのものである。
【００１５】
「位置特定」とは、単に、本方法が、３Ｄモデル化オブジェクトの位置に関する情報を出力することを意味する。そのような出力情報は、位置決めＳ１０の結果から導出され、「位置決め」は、３Ｄシーンにおける３Ｄモデル化オブジェクトの位置決めをするための少なくとも１つのルール／機能（当該ルール／機能も「位置決め」と呼ぶ）を決定（および／または、テスト、および／または提供）することに相当する（後に示す例では、「位置決め」は剛体運動、すなわち、並進運動および／または回転であり、以下の事実を意味する。すなわち、３Ｄモデル化オブジェクトおよび３Ｄシーンが、それぞれ、例えば正規直交するそれぞれの基準フレームに関連付けられており、３Ｄモデル化オブジェクトに対応するフレームは、３Ｄシーンに対応するフレームに対して、何らかの方法で、例えば、任意に、位置決めされており、また、位置決めは、３Ｄモデル化オブジェクトが３Ｄシーン内に正確に配置されるように、３Ｄモデル化オブジェクトに対してフレームを「再配置」する剛体運動（これは本方法の特定のやり方で実施される）に相当する。そのような出力情報は、３Ｄシーン内において３Ｄモデル化オブジェクトの位置に関する任意の情報であってもよい（例えば、本方法は、シーン内の３Ｄモデル化オブジェクトの存在の有無を認識するためにのみ使用されてもよい）。この情報は、例えば少なくとも１つの剛体運動を含む、３Ｄシーン内に３Ｄモデル化オブジェクトを配置するための規則を含むことができる（例えば、３Ｄシーン内の３Ｄモデル化オブジェクトの最初の位置決め、例えば任意の、および／または所定の、または本方法内で決定された位置を参照する）。３Ｄモデル化オブジェクトの、可能性のあるいくつかの位置が提供されてもよい。また、位置決めＳ１０は、３Ｄモデル化オブジェクトが３Ｄシーン内に位置していない（従って、位置決めが出力されていない）と判定される結果になる可能性もある。また、本方法は、信頼性情報（例えば、可能性のあるそれぞれの位置に関連付けられた信頼性／重要性のレベル）を決定するか、あるいは、（例えば、システマチックに、あるいは信頼性の閾値に達したときに）（例えば、Ｓ１０によって提供される）１つまたは複数の最適な位置を出力してもよい。さらに、本方法は、単一の３Ｄモデル化オブジェクト上で実行されてもよく、または基本３Ｄモデル化オブジェクトの異なるバージョン上で繰り返し実行されてもよい（例えば、異なる縮尺や、異なる修正を加えた場合においても、「３Ｄモデル化オブジェクト」という表現は、その基本バージョンまたは修正バージョンの両方を区別せずに指す）。こうした検討は、３Ｄシーン内において３Ｄモデル化オブジェクトの位置特定を行う従来技術から周知である。
【００１６】
一例において、位置決めＳ１０は、オプションとしてそれぞれが重要性レベルを有する、３Ｄシーン内の３Ｄモデル化オブジェクトの１つまたは複数の最良の位置決め機能を決定することに相当してもよく、位置特定は、場合によっては決定ステップの結果として生じるフィルタリングの後に、位置決めＳ１０の結果を出力するだけであってもよい（決定は、所定の重要性閾値、例えば、各重要性レベルと比較される閾値に基づく）。このような位置特定には、異なる周知のアプリケーションがある可能性がある（すなわち、位置特定は、当該アプリケーションの前または実行中、例えばリアルタイムで、行われる）。
【００１７】
あるアプリケーションでは、本方法は、仮想現実の拡張に（例えばマーカーレスで、また、例えばリアルタイムで）用いることができる。３Ｄシーンは仮想環境であり、その中における３Ｄモデル化オブジェクトの位置が（例えば、ユーザが仮想現実に没入すること、および／または、その中で移動するなど仮想現実に対して対話操作を行うことを含む、仮想現実の方法よりも先に、または、同時に、すなわちリアルタイムで）特定される。この位置特定は、仮想環境（すなわち、３Ｄシーン）にデータを追加（例えば３Ｄモデル化オブジェクトに関連する追加データ、例えば非ジオメトリデータ、例えばユーザ定義データ、例えばモデル化オブジェクトのＣＡＤバージョン上で作業し、制約、正確なジオメトリ、および／または表現された現実の物体のセンサに基づく３Ｄ再構成では直接得られない任意のデータなど、任意のタイプの情報を追加）するのに使用可能であり、それによって仮想現実（例えば、拡張前のモデル化オブジェクトについての最小限のデータのみ（例えばジオメトリデータのみ）を含む仮想現実）を豊かなものにする。本方法は、堅牢で正確な位置特定を実行するため、マーカーレスで（すなわち、後で位置特定を行うのを補助するために任意のマーカーを埋め込んだ３Ｄモデル化オブジェクトなしで）すべてを実行することができる。また、本方法は比較的速く実行されるため、リアルタイムで効率的に実行することができる。マーカーレスに対し、マーカー拡張現実とは、現実世界のシーンに特別な記号を配置し、コンピュータシステムがこの記号を認識して、追加の仮想オブジェクトを現実世界のシーンのビューの適切な場所に挿入することができるようにするマーカー拡張現実を指す。現実世界のシーンにあらかじめ定義された記号を配置することは必ずしも可能ではない。本方法は、明確に、マーカーレスの性能を提供する。
【００１８】
別のアプリケーションにおいて、本方法は、あらゆるｓｔｒｕｃｔｕｒｅ−ｆｒｏｍ−ｍｏｔｉｏｎ解析３Ｄ再構成に適用することができる。ｓｔｒｕｃｔｕｒｅ−ｆｒｏｍ−ｍｏｔｉｏｎ解析３Ｄ再構成（すなわち、現実のオブジェクトについての物理的データが、当該オブジェクトの３Ｄモデルを再構成するために、専用のセンサによって取得される）において、データ取得に中断期間が含まれている場合、本方法では、中断によって分離された２つの取得期間の修正を補助することができる。一方の期間中に取得されたデータ（すなわち３Ｄモデル化オブジェクト）の少なくとも一部は、実際には、他方の期間中に取得されたデータのみに基づいて再構成された３Ｄシーン内において位置を特定することができ（すなわち部分データに基づく「中間的」再構成）、それにより修正が達成される。これにより、完全な３Ｄ再構成のために、後で両方のデータセットを考慮／同期することが可能になる。ＲＧＤ−Ｄデータセットは、ＲＧＢ−Ｄカメラを使用して３Ｄシーンをキャプチャすることができる場合であってもよい。そのような装置は、ＲＧＢ（赤、緑、青）の画素の画像を各画素に関連付けられた深度（Ｄ）情報とともに提供する。これは、キャプチャ処理中に並進運動または円運動に従ってカメラを動かすことによって得られる。カメラの動きが中断され、別の位置から再開された場合、結果として生じる２つのデータセットは、カメラのキャプチャ視点に接続されない。スキャン全体を再開する必要がある。これは、本方法により回避することが可能である。同様に、本方法は、同時に実行される３Ｄ再構成を同期させるために適用可能であり、それにより、その２つの３Ｄ再構成を融合して、その情報を共同で使用する。
【００１９】
例えば、本方法は、マーカーレス拡張現実を実行することができる任意のソフトウェア製品に実装することができる。そして、そのような製品は、以下の特徴を有することができる。すなわち、ソフトウェアは、シーン内のモデルの部分的なオクルージョンに対して堅牢であり、演算時間はシーンのサイズに対して線形であり、依存係数は１より小さく、ソフトウェアは、三角メッシュとは対照的に、鏡面対称を扱うことができ、かつ／または、点および法線ベクトルが関与する。本方法は、このように、拡張現実を扱うことができる。この技術は、コンピュータによって生成された仮想要素（場合により３Ｄオブジェクト）を現実世界のシーンの３Ｄビューに挿入するためのものである。多くのアプリケーション、すなわち、エンターテイメント、ツーリズム、観光、ゲーム、家具デザイン、軍事などが、拡張現実の恩恵を受ける。本方法は、ＲＧＢ−Ｄデータセット管理ソフトウェアについても同様に使用することができる。上記先行技術の解決策は、異なる問題を特徴とする。それらは、鏡面対称のもとで不変の記述子を利用する。それらのソフトウェアでは、形状とその鏡面形状との間に違いがない。それらソフトウェアでは、モデルの代わりに、鏡像モデルの位置をシーンにおいて特定するかもしれない。さらに、これらの解決策は、すべてのモデルの対／シーン要素について網羅的な調査を頻繁に実行するため、演算時間の観点から問題がある。
【００２０】
その出力（上述）が何であれ、上記先行技術によって知られている種類の特定のアルゴリズムに従って位置決めが実行される（例えば、完全にまたは半自動的に）（アルゴリズムのいくつかの特異性に続き、位置決めＳ１０および上記先行技術の位置決めについて、本方法の例を参照して後述する）。そのようなタイプのアルゴリズムは、第１の対のそれぞれについて、第２の対のそれぞれとの一致に対して報酬を与える。これについてここで説明する。
【００２１】
「対」は、（関連付けられた法線ベクトルを有する）点の順序付けられたペアを指す。本方法によって処理されるこれらの特定のデータセットは、便宜上、以下では単に（第１および／または第２の）「対」、または、さらなる利便性のため「ペア」と呼ぶ（すなわち、順序に関する側面を無視する）。「第１」の対は３Ｄモデル化オブジェクトに関連し、「第２」の対は３Ｄシーンに関連する。具体的には、第１の対は、３Ｄモデル化オブジェクトの２つの３Ｄ点と、それらに関連付けられた法線ベクトルからなり、一方、第２の対は、３Ｄシーンの２つの３Ｄ点と、それらに関連付けられた法線ベクトルとからなる。
【００２２】
ここで、位置決めＳ１０は、第２の対に対して、３Ｄモデル化オブジェクトを「最良の方法」、例えば、後述の例を参照して説明する特定の方法で位置決め（または「整列」）を行う傾向がある。差し当たっては、位置決めＳ１０は理論的位置を考慮するアルゴリズムに従うと言うことが可能であり、これは「探査」位置決めとも呼ばれる。これは、例えば、アルゴリズムが特定の制約下で最適化プログラムを解決することに相当し得る、最適化の分野で知られている。ここで、このアルゴリズムは、可能な解決策を検討すること（すなわち、理論上の位置の関連性を評価すること）に相当する任意のスキームであってもよく、位置を（理論的に）考慮する場合には、アルゴリズムは常に、位置決めに関する特定の条件に報酬を与える（あるいは同様に、満たされていない条件にペナルティを与える）。これはすべて、それ自体、最適化とアルゴリズムの分野で知られている。なお、本方法は、何らかのやり方で、特に暗示的に、このような報酬付与を（アルゴリズムの特定のステップとして）実施することができる。すなわち、アルゴリズムは、暗示的に報酬付与が行われている解決策に直接向かう（つまり、例えばエネルギーなどの最適条件を実際に探索するのではない）。言い換えれば、報酬付与は、アルゴリズムによって実行される所定の選択肢の背後に「隠されて」いてもよい。
【００２３】
具体的には、位置決めＳ１０によって行われようとしている３Ｄシーンにおける３Ｄモデル化オブジェクトの任意の（理論上の）位置決めに関して、アルゴリズムは以下のように位置決めに報酬を与える。このアルゴリズムは、第１の対が、それぞれ第２の対の上に実質的に配置されているという事実、およびそのような第１の対に関して、記述子の値が第２の対についての記述子の値と、各回、実質的に等しいという事実に対し報酬を与える。言い換えれば、本方法は、第１の対（例えば、それらの最大数）を第２の対に送り（すなわちジオメトリの一致）、そのような対が同じ記述子の値を示すようにする傾向がある（すなわち、シナリオの現実の特性に固有のグローバルな最適化を意図した等価性および不完全性の「実質的な」特性）。さらに言い換えれば、アルゴリズムは、第１の対であって、それらが配置される対応する第２の対を持たない（またはそのような第２の対とほとんど一致しない）第１の対、および／または記述子の値の一致がない（またはほとんどない）第２の対にペナルティを課す。ここで、広く知られているように、これは一般に、多くの異なる方法で実施することが可能であり、それには、先行技術に記載された方法で行うこと、あるいは本方法の（１つまたは複数の）例の（１つまたは複数の）特異性を用いることが含まれる。
【００２４】
本方法は、コンピュータによって実施される。すなわち、本方法のステップ（あるいは略全てのステップ）が少なくとも１つのコンピュータ、または類似の任意のシステムによって実行される。よって本方法のステップは、コンピュータにより、完全に自動的に、あるいは半自動的に実行される可能性がある。例えば、本方法の少なくともいくつかのステップは、ユーザとコンピュータの対話を通じて始動されてもよい。求められるユーザとコンピュータの対話レベルは、想定される自動性のレベルに応じたものであって、ユーザの要望を実装する必要性との間でバランスをとるものとしてもよい。例えば、このレベルは、ユーザが設定し、および／または、予め定義されていてもよい。特に、位置決めＳ１０は、アルゴリズムに従って完全に自動的に行われてもよく、例えば、プロセッサによって実行されてもよい。
【００２５】
本方法のコンピュータによる実施の典型的な例は、この目的に適したシステムを用いて本方法を実行することである。当該システムは、本方法を実行するための命令を含むコンピュータプログラムを記録したメモリに接続されたプロセッサ、および、グラフィカル・ユーザ・インターフェイス（ＧＵＩ）を備えていてもよい。また、メモリはデータベースを記憶していてもよい。メモリは、そのような記憶に適した任意のハードウェアであり、場合により、物理的に区別可能ないくつかの部分（例えば、プログラム用に１つ、場合によりデータベース用に１つ）を含む。
【００２６】
データベースとは、検索および取得用に最適化されたデータ（すなわち情報）の任意の集合（例えば所定の構造化言語、例えばＳＱＬに基づく、例えばリレーショナルデータベース）を意味する。データベースは、メモリに格納されると、コンピュータによる迅速な検索および取得を可能にする。データベースは、実際、様々なデータ処理動作と連動して、データの記憶、取得、修正、および削除を容易にするよう構造化されている。データベースは、それぞれ１つまたは複数のフィールドからなるレコードに分割可能な１つのファイルあるいはファイルのセットからなっていてもよい。フィールドは、データ記憶の基本単位である。ユーザは、主としてクエリによってデータを取得してもよい。ユーザは、使用されているデータベース管理システムのルールに従って、キーワードとソートコマンドを用いて、多数のレコードにおけるフィールドを、迅速に、検索、再配置、グループ化、および選択し、特定の集積データに関するレポートを取得または作成することができる。
【００２７】
本方法は、一般に、モデル化オブジェクトを操作する。モデル化オブジェクトは、例えばデータベースに格納されたデータによって定義される任意のオブジェクトである。さらには、「モデル化オブジェクト」という表現は、データそのものも指す。システムの種類に応じて、異なる種類のデータによってモデル化オブジェクトが定義されてもよい。実際、システムは、ＣＡＤシステム、ＣＡＥシステム、ＣＡＭシステム、ＰＤＭシステム、および／またはＰＬＭシステムのうちの任意のもの（あるいは任意の組み合わせ）であってもよい。それら異なるシステムにおいて、モデル化オブジェクトは、対応するデータによって定義される。したがって、ＣＡＤオブジェクト、ＰＬＭオブジェクト、ＰＤＭオブジェクト、ＣＡＥオブジェクト、ＣＡＭオブジェクト、ＣＡＤデータ、ＰＬＭデータ、ＰＤＭデータ、ＣＡＭデータ、ＣＡＥデータについて言及することがある。しかしながら、モデル化オブジェクトは、これらのシステムの任意の組み合わせに対応するデータによって定義されてもよいため、これらのシステムは、互いに排他的なものではない。したがって、以下に示すこのようなシステムの定義から明らかなように、システムは、ＣＡＤ兼ＰＬＭシステムであってもよい。
【００２８】
ＣＡＤシステムは、少なくとも、ＣＡＴＩＡのようなモデル化オブジェクトのグラフィック表現に基づくモデル化オブジェクトの設計に適した任意のシステムをも意味する。この場合、モデル化オブジェクトを定義するデータは、モデル化オブジェクトを表現可能にするデータを含む。ＣＡＤシステムは、例えば、辺や線を用い、また、場合により面や曲面を用いて、ＣＡＤモデル化オブジェクトの表現を提供してもよい。線、辺、あるいは面は、例えば、非一様有理Ｂスプライン（ＮＵＲＢＳ）など、様々な様式で表現されてもよい。具体的には、ＣＡＤファイルは仕様を含み、その仕様に基づきジオメトリが生成可能であり、よって表現が生成可能となる。モデル化オブジェクトの仕様は１つまたは複数のＣＡＤファイルに格納されていてもよい。ＣＡＤシステムでモデル化オブジェクトを表現するファイルの典型的なサイズは、一部分あたり１メガバイトの範囲である。また、モデル化オブジェクトは、典型的には、数千の部分の集合体であってもよい。
【００２９】
ＣＡＤの文脈において、モデル化オブジェクトは、典型的には、３Ｄモデル化オブジェクト、例えば、一つの部品や部品の集合体などの製品、あるいは製品の集合体を表現するものであってもよい。「３Ｄモデル化オブジェクト」は、３Ｄ表現が可能なデータによってモデル化される任意のオブジェクトを意味する。３Ｄ表現は、その部品をすべての角度から見ることを可能にする。たとえば、３Ｄで表現された３Ｄモデル化オブジェクトは、その軸のうちの任意の軸、あるいは、その表現が表示された画面中の任意の軸を中心に、処理して回転させることが可能である。これは、特に、３Ｄモデル化されていない２Ｄアイコンについては除外される。３Ｄ表現の表示は、設計を容易にする（すなわち、設計者が作業を達成するスピードを統計的に速める）。製品の設計は製造工程の一部であるから、これによって当該産業における製造工程が迅速化する。
【００３０】
３Ｄモデル化オブジェクトは、ＣＡＤソフトウェア・ソリューションやＣＡＤシステム等を用いた仮想的デザインの完了後に実世界において製造される製品、すなわち（例えば機械的な）部品や、部品の集合（あるいは同様に部品の集合。なぜなら部品の集合は本方法の観点では一つの部品としてみることができ、また、本方法は集合体における各部品に独立して適用することができるからである）、より一般的には任意の剛体の集合体（例えば移動機構）などの製品のジオメトリを表現してもよい。ＣＡＤソフトウェア・ソリューションは、航空宇宙、建築、建設、消費財、ハイテク機器、産業機器、輸送、海洋、および／または海洋石油／ガス生産、または交通を含む、限定されることのない様々な産業分野において製品の設計を可能にする。本方法により設計される３Ｄモデル化オブジェクトは、このように、地上車両の部品（例えば、自動車および軽トラック機器、レーシングカー、オートバイ、トラックおよびモーター機器、トラック、バス、電車を含む）、航空車両の部品（例えば、航空機体機器、航空宇宙機器、推進機器、防衛製品、航空路線機器、宇宙機器を含む）、海軍車両の部品（例えば、海軍用機器、商業用船舶、オフショア機器、ヨットおよび作業船、船舶用機器を含む）、一般的な機械部品（例えば、工業用製造機械、大型移動機械または機器、設置機器、産業機器製品、加工金属製品、タイヤ製造製品を含む）、電気機械部品または電子部品（例えば、家電、セキュリティおよび／または制御および／または計装製品、コンピューティングおよび通信機器、半導体、医療装置および設備を含む）、消費者製品（例えば、家具、家庭用および庭用製品、レジャー用品、ファッション用品、耐久消費財小売用品、織物類小売用品を含む）、包装（例えば、食品および飲料およびたばこ、美容およびパーソナルケア、家庭用製品包装を含む）などのように、任意の機械的部品であり得る工業製品を表してもよい。３Ｄシーンは、そのようなモデル化オブジェクトであってもよい。しかし、３Ｄシーンは、典型的には現実のシーンを表し、したがって、例えば、３Ｄは、場合により他のタイプのモデル化オブジェクト（例えば、工場、および／または、部屋、および／または、設備などのような、風景、および／または、空間、および／または、建物）と、特定のやり方で組み立てられた（あるいは並べられた）そのようないくつかのモデル化オブジェクトを含む。
【００３１】
ＰＬＭシステムは、物理的な、製造された製品（または製造される予定の製品）を表すモデル化オブジェクトの管理に適した任意のシステムをも指す。ＰＬＭシステムでは、モデル化オブジェクトは、このように、物理的な物体の製造に適したデータによって定義される。これらは、典型的には、寸法の値および／または公差の値であってもよい。物体を正しく製造するために、実際、このような値を用いるのが望ましい。
【００３２】
ＣＡＭソリューションとは、製品の製造データを管理するのに適した、ハードウェアのソフトウェアである、あらゆるソリューションをも指す。製造データは、一般に、製造する製品、製造工程、および必要なリソースに関するデータを含む。ＣＡＭソリューションは、製品の製造工程全体を計画し最適化するのに用いられる。例えば、実現可能性、製造工程の期間、または製造工程における特定のステップで使用されるリソース、例えば特定のロボットの数に関する情報をＣＡＭユーザに提供することができる。これにより、管理や必要な投資についての決定を可能にする。ＣＡＭは、ＣＡＤ工程、および、場合によりＣＡＥ工程に続く工程である。このようなＣＡＭソリューションは、ダッソー・システムズにより、ＤＥＬＭＩＡ（登録商標）として提供されている。
【００３３】
ＣＡＥソリューションとは、モデル化オブジェクトの物理的挙動の分析に適した、ハードウェアのソフトウェアである、あらゆるソリューションをも指す。よく知られており広く用いられているＣＡＥ技術は有限要素法（Ｆｉｎｉｔｅ  Ｅｌｅｍｅｎｔ  Ｍｅｔｈｏｄ：ＦＥＭ）であり、これは、典型的には、モデル化オブジェクトを、物理的挙動を方程式によって計算しシミュレーションできる要素に分割することを含む。このようなＣＡＥソリューションは、ダッソー・システムズにより、ＳＩＭＵＬＩＡ（登録商標）として提供されている。成長するＣＡＥ技術のもう１つは、ＣＡＤジオメトリデータを使用せずに異なる物理分野の複数の要素で構成される複雑なシステムのモデリングと解析を行うことを含む。ＣＡＥソリューションはシミュレーションを可能にし、それにより、製造する製品の最適化、改善および検証を可能にする。このようなＣＡＥソリューションは、ダッソー・システムズにより、ＤＹＭＯＬＡ（登録商標）として提供されている。
【００３４】
ＰＤＭはＰｒｏｄｕｃｔ  Ｄａｔａ  Ｍａｎａｇｅｍｅｎｔ（生産データ管理）の略である。ＰＤＭソリューションとは、特定の製品に関するすべての種類のデータを管理するのに適した、ハードウェアのソフトウェアである、あらゆるソリューションを指す。ＰＤＭソリューションは、製品のライフサイクルにかかわるすべての関係者によって使用されてもよい。これには、主として技術者のほか、プロジェクトマネージャー、財務担当者、営業担当者、およびバイヤーも含まれる。ＰＤＭソリューションは、一般に、製品指向のデータベースに基づく。これにより、関係者が製品に関する一貫したデータを共有することが可能になり、これにより、関係者が異なるデータを用いるのを防止する。このようなＰＤＭソリューションは、ダッソー・システムズにより、ＥＮＯＶＩＡ（登録商標）として提供されている。
【００３５】
図２は、システムのＧＵＩの一例を示し、本システムは、例えば、先に３Ｄモデル化オブジェクトの設計を行い、そして本方法によって位置特定を行う、ＣＡＤシステムである。
【００３６】
ＧＵＩ２１００は、標準的なメニューバー２１１０，２１２０、ならびに底部および側面のツールバー２１４０，２１５０を有する典型的なＣＡＤのようなインターフェースであってもよい。このようなメニューバーおよびツールバーは、ユーザが選択可能なアイコンのセットを含み、各アイコンは、当技術分野で知られているように、１つまたは複数の操作または機能に関連付けられている。これらのアイコンのいくつかは、ＧＵＩ２１００に表示された３Ｄモデル化オブジェクト２０００の編集および／または作業に適合したソフトウェアツールに関連付けられている。ソフトウェアツールはワークベンチに分類することができる。各ワークベンチは、ソフトウェアツールのサブセットを含む。特に、ワークベンチの１つは、モデル化製品２０００のジオメトリ的特徴を編集するのに適した編集ワークベンチである。操作中、設計者は、例えば、オブジェクト２０００の一部を予め選択し、次いで、適切なアイコンを選択することによって、操作を開始する（例えば、寸法、色などを変更する）か、ジオメトリ的制約を編集することができる。例えば、典型的なＣＡＤ操作は、スクリーン上に表示された３Ｄモデル化オブジェクトのパンチングまたは折り畳みのモデリングである。ＧＵＩは、例えば、表示された製品２０００に関連するデータ２５００を表示してもよい。図２の例では、「特徴ツリー」として表示されたデータ２５００およびそれらの３Ｄ表現２０００は、ブレーキキャリパおよびディスクを含むブレーキ部品に関するものである。ＧＵＩは、編集された製品の動作のシミュレーションを起動するため、または表示された製品２０００の様々な属性を描画するために、例えばオブジェクトの３Ｄ定位を容易にするための様々なタイプのグラフィックツール２１３０，２０７０，２０８０をさらに示してもよい。カーソル２０６０は、ユーザがグラフィックツールを用いて対話操作ができるように、触覚デバイスによって制御されてもよい。
【００３７】
図３は、本システムの一例を示すものであって、当該システムは、クライアントコンピュータシステム、例えばユーザのワークステーションである。
【００３８】
本例のクライアントコンピュータは、内部通信バス１０００に接続された中央演算処理装置（ＣＰＵ）１０１０、および同じくバスに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを備える。クライアントコンピュータは、さらに、バスに接続されたビデオランダムアクセスメモリ１１００と関連付けられたグラフィックス処理装置（ＧＰＵ）１１１０を備える。ビデオＲＡＭ１１００は、当該技術分野において、フレームバッファとしても知られる。大容量記憶装置コントローラ１０２０は、ハードドライブ１０３０などの大容量記憶装置へのアクセスを管理する。コンピュータプログラムの命令及びデータを具体的に実現するのに適した大容量メモリ装置は、例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ及びフラッシュメモリ装置のような半導体メモリ装置、内蔵ハードディスクやリムーバブルディスクなどの磁気ディスク、光磁気ディスク、およびＣＤ−ＲＯＭディスク１０４０を含む、全ての形式の不揮発性メモリを含む。前述のいずれも、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補完されてもよいし、組み入れられてもよい。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータはまた、カーソル制御装置、キーボードなどの触覚装置１０９０を含んでいてもよい。カーソル制御装置は、ユーザがディスプレイ１０８０上の任意の所望の位置にカーソルを選択的に位置させることを可能にするために、クライアントコンピュータ内で使用される。さらに、カーソル制御デバイスは、ユーザが様々なコマンドを選択し、制御信号を入力することを可能にする。カーソル制御装置は、システムに制御信号を入力するための多数の信号生成装置を含む。典型的には、カーソル制御装置はマウスであってもよく、マウスのボタンは信号を生成するために使用される。あるいは、または追加的に、クライアントコンピュータシステムは、感知パッドおよび／または感知スクリーンを備えてもよい。
【００３９】
コンピュータプログラムは、コンピュータによって実行可能な命令を含んでいてもよく、命令は、上記システムに方法を実行させるための手段を含む。プログラムは、システムのメモリを含む任意のデータ記憶媒体に記録可能であってもよい。プログラムは、例えば、デジタル電子回路、またはコンピュータハードウェア、ファームウェア、ソフトウェア、またはそれらの組み合わせで実装されてもよい。プログラムは、例えばプログラマブルプロセッサによる実行のための機械読み取り可能な記憶装置に具体的に実現された製品のような装置として実装されてもよい。方法ステップは、プログラム可能なプロセッサが命令のプログラムを実行し、入力データを操作して出力を生成することによって方法の機能を実行することによって実行されてもよい。したがって、プロセッサは、データ記憶システム、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスからデータおよび命令を受信し、また、それらにデータおよび命令を送信するようにプログラム可能であってもよく、またそのように接続されていてもよい。アプリケーションプログラムは、高水準の手続き型またはオブジェクト指向のプログラミング言語で、または必要に応じてアセンブリ言語または機械語で実装されていてもよい。いずれの場合も、言語はコンパイラ型言語またはインタープリタ型言語であってもよい。プログラムは、フルインストールプログラムまたは更新プログラムであってもよい。いずれの場合も、プログラムをシステムに適用すると、本方法を実行するための指示が得られる。
【００４０】
「３Ｄモデル化オブジェクトの設計」とは、３Ｄモデル化オブジェクトを作り上げる工程の少なくとも一部である任意の行為あるいは一連の行為を指す。したがって、本方法は、３Ｄモデル化オブジェクトを一から作ることを含んでもよい。あるいは、本方法は、以前に作成された３Ｄモデル化オブジェクトを提供し、次いで３Ｄモデル化オブジェクトを修正することを含んでいてもよい。
【００４１】
ここで、本方法の例を説明する。この方法の異なるオプションが例によって実装され、それらについて以下に詳述する。これらの例において、すべてのオプションが実装されるわけではなく、および／または、一部のオプションがわずかに変更され、異なる方法で実装されてもよい。
【００４２】
これらの例における方法は、「モデル」と名付けられた物理的な３Ｄディテールを、「シーン」と名付けられた、より広い物理的３Ｄ環境に配置してもよい。まず、３Ｄの物理的シーンおよびモデルは、点及び法線ベクトルからなる２つの有限集合の対にそれぞれ変換されてもよい（例えば、そのようなすでに有限となっている集合から開始するか、あるいは対応する無限集合をサンプリングすることによって行う）。一例では、点は３Ｄシーンおよびモデルの表面からサンプリングされる。法線ベクトルは、サンプリング点での３Ｄシーンおよびモデルの表面のものである。図４はそのようなサンプリングを例示している。図５は、典型的なモデルのサンプリング点を示し、図６は、シーンのそれを示す（像が３Ｄシーンによって表される環境内に明らかに存在するので、図５の像（すなわち３Ｄモデル化オブジェクト）の表現が実際に見つけられ、図６の３Ｄシーン内に配置されるべきことを示す図の例）。
【００４３】
本方法における関心の対象は、（点，法線）の対のペアであり、（（点，法線），（点，法線））のようなものである。以下に説明する例では、本方法は、「３Ｄ投票」ステップを介して、モデルのペアをシーンのペアに変更するすべての剛体運動のうち最も頻度の高いものを選択してもよい。モデル内の「アンカーポイント」と呼ばれる３つの点を選択し、この選択は、モデルのペアをシーンのペアに変更する剛体運動によって変換されたすべてのアンカーポイントを格納することによって行ってもよい。これは、後述の「ペアからペアへの剛体運動」ステップである。最も頻繁な変換アンカーポイントは、「最良の剛体運動」が算出される、最も頻繁な剛体運動を開示する。さらに、例えば、ユーザが最良の剛体運動を後続の工程で使用できるかどうかを決定するために、「重要性レベル」を算出してもよい。パフォーマンス目的のために、全てのペアからペアへの剛体運動が調査されなくてもよい。（モデルの）ペアを（シーンの）類似のペアに変更する剛体運動のみが考慮されてもよい。あるペアに類似するペアは、数値署名を使用することによって集められ、専用のデータ構造に記憶されてもよい。これは、後述の「ペア署名」マッチングである。これらの個々のオプションのすべてを特徴とする方法の例が、図７のフローチャートに示されている。
【００４４】
例の方法がｓｔｒｕｃｔｕｒｅ−ｆｒｏｍ−ｍｏｔｉｏｎ解析に適用されると、いくつかのことが可能になる。カメラのスキャンが中断された場合、シーンの一部が、連続したデータセットによって共有されるように、隣接する位置から再開することができる。本方法は、共有部分をマッチングすることによって、２つのデータセットの正しい再配置を算出することができる。これにより、中断または摂動を許容することができるため、スキャン工程がより堅牢になる。マーカーレス拡張現実とは、所定の記号による補助なしに現実世界のビューに追加の仮想オブジェクトを挿入することである。そのような状況に適用すると、例の方法は、仮想オブジェクトの適切な挿入位置を算出することができる。上記先行技術と比較して、例の方法の主要なオプションの利点は、堅牢でありつつも、必要な演算が少ない投票工程である。実際、例の方法は、シーンの一定数のペアを用いて動作するが、上記従来技術では、可能性のあるすべてのペアが考慮される一定数の「参照点」を用いて動作する。例の方法は、（１）使用するシーンのペアのセットを適切に選択し、（２）２つのペア間の剛性変換を算出するための直接的な方法を有し、また（３）変換のためにグローバルに投票する方法（アンカーポイントとハッシュテーブル）を有することにより、堅牢性を保ち、さらには堅牢性を改善しつつ、「参照点」を破棄することができる。もう１つの違いは、記述子の第４の実数が効率的に対称性を扱うことである。実際は、上記先行技術とは対照的に、例の方法においては、鏡面対称の２つのペアが同じ記述子を共有しない。
【００４５】
図８〜１０の各図は、それぞれ３枚の絵を示す。左上の絵は３Ｄモデルであり、左下の絵は３Ｄシーンであり、右の絵はシーン内に配置されたモデルである（この表示はＳ１０に従って実行される方法のさらなるステップであり得る）。すべてのシーンとモデルは３Ｄ点の有限集合である。図８は「車」のモデルを示す。図９は「椅子」のモデルを示す。図１０は「ヴィーナス」のモデルを示す。
【００４６】
ここで「ペア」（または「対」）の表記について説明する。
【００４７】
単位球を
【数１】
2017168081.tif 000003
とし、３Ｄ点と法線ベクトルからなる対の集合を
【数２】
2017168081.tif 000004
とする。定義上、例の方法において、モデルＭとシーンＳは、Ｋの有限の部分集合であり、すべてのｉについて、
【数３】
2017168081.tif 000005
のとき
【数４】
2017168081.tif 000006
であり、すべてのｉについて、
【数５】
2017168081.tif 000007
のとき
【数６】
2017168081.tif 000008
であることを意味する。ＰMを
【数７】
2017168081.tif 000009
の要素の全ての対の集合とする。
【数８】
2017168081.tif 000010
についても同様である。
【００４８】
数学的な観点からは、ＰMまたはＰSの要素はいくつかの点と法線の対であるが、明確にするために、以下ではこれを「ペア」と呼ぶ。これは従来技術における表現とも一致する。要素の順番が重要であるため、明らかにこれは数学的観点からは「ペア」ではないが、真のペアの数学的概念は以下の説明では使用されていないため、誤解を招くことはない。図１１は典型的なペアを例示する。
【００４９】
アルゴリズムの一例と、上述の報酬付与をどのように実行するかについて説明する。
【００５０】
位置決めＳ１０に続くアルゴリズムは、（最初の対に対して実行され非常に迅速に禁止される可能性のある上述の先行技術のアルゴリズムとは異なり）第２の対上で（繰り返し）実行され、実行中のそれぞれの第２の対に一致するすべての第１の対にアクセスし、アクセスした第２の対上に実質的に配置される第１の対に対して報酬を与える３Ｄシーン内における３Ｄモデル化オブジェクトの位置決めを出力するものであってもよい。言い換えれば、位置決めは、３Ｄシーンの第２の対から構造的に開始し、候補となる第１の対（すなわち、考慮される第２の対のそれぞれの上に実質的に配置され得る３Ｄモデル化オブジェクトのもの）を考慮し、それらの候補を候補位置に変換する。この構造により、演算時間が短縮される。
【００５１】
特に、アルゴリズムが実行される第２の対は、３Ｄシーンに含まれるそれぞれの３Ｄ点の代表的な部分集合である（例えば、部分集合によって／対して形成される）。言い換えると、アルゴリズムは、全ての第２の対に対して実行される代わりに、その部分集合上（すなわち、３Ｄシーンに含まれる各３Ｄ点の代表的な部分集合に対応する）で実行される。「代表的」とは、第２の対が（最初のサンプリングと比較して）少ない情報量でシーンのジオメトリを表すことを意味する。具体的には、代表的部分集合は、３Ｄシーンに含まれる各３Ｄ点の縮小（すなわち、選択）から得られる。縮小には、３Ｄシーンに含まれる各３Ｄ点の空間クラスタリング（例えば、Ｋ平均法）と、クラスタリングの結果に基づく確率的選択が含まれる。言い換えると、３Ｄシーンの３Ｄ点がクラスタリングされ、クラスタに確率が割り当てられ、本方法は、割り当てられたクラスタ確率に基づいてランダム（例えば、擬似ランダム）に選択を実行する。確率は、確率的選択が、大きなクラスタ、および／または近いクラスタに報酬を与えるようなものであってもよい（ここで「近い」という用語は、基準位置から評価した距離であり、これは、３Ｄシーンが仮想現実環境である場合にはカメラの位置、すなわち、没入したユーザの視点であってもよく、例えば、また、本方法は、ユーザが仮想現実没入工程に入っていて、仮想環境と対話している間に、例えばリアルタイムで実行される）。
【００５２】
ここで、（演算の観点から見て）特に効率的な方法で特に正確な最終結果を導き出すような、ＰSのこのような縮小の例について説明する。この例では、カメラの位置を参照している。カメラの位置が与えられていない場合、関連する項を取り除くことによって（また一般的な空間クラスタリングを実行することによって）この例を適合させることができる。この例のクラスタリングの目的は、主に、対の分布を均質にし、同じオブジェクトに属する可能性が高い対をグループ化することである。
【００５３】
Ｓの要素数は非常に大きく、Ｍの要素数よりはるかに大きく、ＰSとＰMについても同様である。パフォーマンスのために、この例ではランダムに選択されたＰSの部分集合のみが考慮される。集合ＰSは、モデルの点の数、すなわち
【数９】
2017168081.tif 000011
に縮小される。縮小後の典型的な値は
【数１０】
2017168081.tif 000012
であり、モデルの典型的なサイズは
【数１１】
2017168081.tif 000013
である。本例の縮小は、集合Ｓのクラスタリングステップと、それに続くＰSの要素のランダム選択ステップとによって実行される。先に定義したように、Ｓの要素は、３Ｄ点と法線ベクトルとからなる対である。この例の縮小工程では法線ベクトルは使用されないため、「Ｓの点」とは、３Ｄ点のみを指す。この例のクラスタリングステップはＫ平均法アルゴリズムに基づき、例えば文献「Ｔａｐａｓ  Ｋａｎｕｎｇｏ，Ｄａｖｉｄ  Ｍ．Ｍｏｕｎｔ，Ｎａｔｈａｎ  Ｓ．Ｎｅｔａｎｙａｈｕ，Ｃｈｒｉｓｔｉｎｅ  Ｄ．Ｐｉａｔｋｏ，Ｒｕｔｈ  Ｓｉｌｖｅｒｍａｎ，ａｎｄ  Ａｎｇｅｌａ  Ｙ．Ｗｕ，Ａｎ  Ｅｆｆｉｃｉｅｎｔ  ｋ−Ｍｅａｎｓ  Ｃｌｕｓｔｅｒｉｎｇ  Ａｌｇｏｒｉｔｈｍ：Ａｎａｌｙｓｉｓ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，Ｖｏｌ．２４，Ｎｏ７，Ｊｕｌｙ  ２００２」に記載されている。入力は、クラスタの数Ｎ（２と５との間、例えば、経験的に良好な値である３）とポイントの集合Ｓである。出力は、クラスタと名付けられたＮ個の空でない互いに素な部分集合Ｃi、ｉ＝１，・・・，Ｎであり、それぞれＣiに関連付けられた、平均点と名付けられた数多くの３Ｄ点ｍi＝（ｘi，ｙi，ｚi）、ｉ＝１，・・・，Ｎである。出力は、次の特性が満たされるように算出される。まず、Ｓ＝Ｃ1∪・・・∪ＣNである。次に、全ての点ｍ∈Ｃiが、ｊ≠ｉである他の平均点ｍjよりも平均点ｍiに近い。すなわち、全てのｉ＝１，・・・，Ｎと全てのｍ∈Ｃiについて
【数１２】
2017168081.tif 000014
である。各クラスタＣi内の点の数はｎiで表される。平均点はｋ平均法アルゴリズムによって算出され、それらの点はＳに属さない。クラスタリングに使用される基準軸系は、ｚ座標がカメラまでの距離であり、全てのｉについてｚi＞０となるように定義される。本例の文脈においては、典型的なクラスタ数は３である。
【００５４】
図１２は、２Ｄポイントの例示的な集合を示す。図１３は、平均点ｍ1、ｍ2、ｍ3、ｍ4およびカメラ位置とともに、４つのクラスタＣ1、Ｃ2、Ｃ3、Ｃ4へのｋ平均法を例示する。本例のランダム選択ステップは、以下のように実行される。Ｃ(N+1)＝Ｓに注目することにより、集合Ｓ全体が含まれる。次に、ｉ＝１，・・・，Ｎ＋１について、確率ｐi∈［０，１］が以下の式に従って各Ｃiに関連付けられる。まず、
【数１３】
2017168081.tif 000015
である。次に、正規化係数は
【数１４】
2017168081.tif 000016
であり、最後に、すべてのｉ∈｛１，・・・，Ｎ｝について、確率は
【数１５】
2017168081.tif 000017
である。係数ｐ0は、ｐ1＋・・・＋ｐ(N+1)＝１となるように設計されている。確率ｐiはＣiの点の数の２乗ｎi2に比例し、その深度ｚiに反比例する。このように、同じ数の点を持つ２つのクラスタがある場合、最も可能性が高いのはカメラに近いものである。さらに、同じ深度を有する２つのクラスタがある場合、最も可能性が高いのは、点の数が最大のクラスタである。最後に、集合Ｃ(N+1)の確率はゼロにはならず、別個のクラスタにおける点を有するペアが選択される。
【００５５】
Ｎpを、ＰSにおいて選択するペアの数とする。選択アルゴリズムは、前段落で定義した確率に従って、集合｛１，・・・，Ｎ＋１｝における整数のランダム発生器を利用する。これをＲａｎｄＰｒｏｂと表す。ＲａｎｄＰｒｏｂを呼び出すたびに、新しい整数値が返される。整数ａとｂが与えられた場合、アルゴリズムは、一様な確率に従って、任意の集合｛ａ，ａ＋１，・・・，ｂ｝における整数の発生器もランダムに使用する。これをＲａｎｄ（ａ，ｂ）と呼ぶ。Ｒａｎｄ（ａ，ｂ）を呼び出すたびに、新しい整数値が返される。選択アルゴリズムは、以下のようなものであってもよい。
【数１６】
2017168081.tif 000018
【００５６】
簡略化のため、縮小した集合ＰSも依然としてＰSで表している。
【００５７】
一例では、本方法は、（さらに）ペアの前処理を含むことができる。前処理は、例えば所定の閾値に対して、ｐ2がｐ1に比較的近いか、あるいは、例えば所定の閾値に対して、ｎ1がｐ2−ｐ1との共線状態に比較的近い対（（ｐ1，ｎ1）、（ｐ2，ｎ2））から顕著にＰM∪ＰSを消去する（すなわち、後の処理のために取り除く）ものであってもよい。
【００５８】
本例では、効率化のため、集合ＰMとＰSは無意味なペアを削除することで消去される。無意味なペア（（ｐ1，ｎ1），（ｐ2，ｎ2））とは、ｐ1とｐ2の距離が不適切であるか、またはｎ1、ｎ2、およびｐ2−ｐ1がほぼ共線的であるようなものである。
【００５９】
第１の処理は、
【数１７】
2017168081.tif 000019
が大き過ぎるか、小さ過ぎるようなＰMとＰSのペアを取り除くものであってもよい。正確には、これは以下を算出することによって行われる。
【数１８】
2017168081.tif 000020
【００６０】
ここで、ｋmin＝０．１であり、ｋmax＝０．６である。そして、
【数１９】
2017168081.tif 000021
を満たすようなペア（（ｐ1，ｎ1），（ｐ2，ｎ2））∈ＰM∪ＰSのみが、さらなる処理のために保持される。
【００６１】
第２の前処理によれば、以下の関係を満たすペア（（ｐ1，ｎ1），（ｐ2，ｎ2））∈ＰM∪ＰSのみを保持することができる。
【数２０】
2017168081.tif 000022
【００６２】
ｄｅｔ［ｕ，ｖ，ｗ］は、ベクトル
【数２１】
2017168081.tif 000023
の３×３行列式を表す。閾値ｋの典型的な値は、ｋ＝０．２である（これは±５０％の範囲で変更できる）。以下で用いられている集合ＰMおよびＰSは、前処理で定義された特性を満たしてもよい。
【００６３】
ここで、署名の概念について説明する。
【００６４】
ペアについての数値署名が、以下の工程に従って定義されてもよい。ペアは、「記述子」と呼ばれる４つの要素からなる実数群に変換することができ、これはまた、整数に変換できる。そのような場合、署名は、以下に説明するように、両者の組み合わせを指す可能性がある。
【００６５】
まず、本方法の一例における記述子について説明する。
【００６６】
本例では、記述子は特定の項があるために、鏡面対称下で可変である。これにより、上記先行技術に対して、誤検出の低減が可能になる。
【００６７】
（（ｐ1，ｎ1），（ｐ2，ｎ2））∈ＰM∪ＰSが与えられた場合、記述子は、ｑ＝ｐ2−ｐ1および
【数２２】
2017168081.tif 000024
によって定義されるマッピング
【数２３】
2017168081.tif 000025
に従って算出されてもよい。
【００６８】
ここで、
【数２４】
2017168081.tif 000026
は、ベクトルｕとｖのスカラ積である。マッピングＦは、上記先行技術と同様、剛体運動の下では不変であるが、上記先行技術とは対照的に、鏡面対称の下では不変ではない。実際、鏡面対称線形マッピングＬに注目すると、鏡像ペアの記述子の第４の座標は、
【数２５】
2017168081.tif 000027
であってもよく、これはｄｅｔ  Ｌ＝−１だからである。
【００６９】
記述子（上記の例の特定の記述子、またはそのような他の記述子）は、一例において量子化されていてもよく、これは等価評価（必要な場合）の高速実行につながる。ここで、このような量子化について説明する。
【００７０】
一般的に、第１の対の記述子の値と第２の対の記述子の値が実質的に等価であることは、整数が実質的に等価であることと見なすことができる。具体的には、第１の対の記述子の値に対応する第１の整数と、第２の対の記述子の値に対応する第２の整数とが実質的に等価である可能性があり、そのような場合、第１の整数および第２の整数は、第１の対の記述子の値と第２の対の記述子の値にそれぞれ適用される量子化マッピングを介して算出されてもよい。これにより、整数の等価性のみが考慮されるため、工程が大幅に高速化される（実数の比較には時間がかかる）。
【００７１】
ここで、このような量子化を効率的かつ比較的高精度に（最終的な結果のために）実行する特定の方法について説明する。
【００７２】
Ｈ＝Ｆ（ＰM∪ＰS）を、（（ｐ1，ｎ1），（ｐ2，ｎ2））∈ＰM∪ＰSのとき、４つの要素からなる全てのＦ（ｐ1，ｎ1，ｐ2，ｎ2）の有限集合とする。本質的に、
【数２６】
2017168081.tif 000028
である。Ｈの各要素は、量子化マッピング
【数２７】
2017168081.tif 000029
を用いて整数に変換される。このマッピングについて以下に定義する。ｉ＝１，・・・，４およびすべての（ｒ1，ｒ2，ｒ3，ｒ4）∈Ｈについて
【数２８】
2017168081.tif 000030
であるような８つの実数
【数２９】
2017168081.tif 000031
および
【数３０】
2017168081.tif 000032
（ｉ＝１，・・・，４）が存在する。
【００７３】
実際、実数ｒ2とｒ3は正規化されたベクトルのスカラ積であるため、−１≦ｒ2≦１であり、また−１≦ｒ3≦１である。実数ｒ4は正規化ベクトルの行列式であるため、−１≦ｒ4≦１である。（言い換えれば、ｒ1に関して、より正確な最小値および／またはより正確な最大値も決定することができるが、
【数３１】
2017168081.tif 000033
および
【数３２】
2017168081.tif 000034
（ｉ＝２，３，４）について、−１および＋１を保持することができる）。
最後に、数ｒ1は、
【数３３】
2017168081.tif 000035
を満たすような数であり、
【数３４】
2017168081.tif 000036
および
【数３５】
2017168081.tif 000037
は、一例の上記前処理によって定義されてもよい。
【００７４】
「解像度」と呼ばれる４つの実数εi、ｉ＝１，・・・、４が考えられる。典型的な値は以下のとおりである。
【数３６】
2017168081.tif 000038
【００７５】
テストでは、分解能数の効率の範囲は、これらの名目値を中心に±５０％であることが示された（すなわち、本方法は、上述の４つの数値のそれぞれについて、±５０％以内で変動する値を検討することができる）。なお、
【数３７】
2017168081.tif 000039
および
【数３８】
2017168081.tif 000040
に関して、−１および＋１よりも正確な値が保持される場合、εi、ｉ＝２，３，４の値は、ε1と同様とすることができる。
【００７６】
実数ｒ以下である最大の整数［ｒ］に着目し、ｉ＝１，・・・，４について整数δiを定義すると、
【数３９】
2017168081.tif 000041
と表せる。
【００７７】
ここで、任意の（ｒ1，ｒ2，ｒ3，ｒ4）∈Ｈが与えられたとして、ｉ＝１，・・・，４に関して整数ｑiを定義すると、
【数４０】
2017168081.tif 000042
と表される。
【００７８】
そして、４つの要素からなる（ｒ1，ｒ2，ｒ3，ｒ4）∈Ｈの量子化は、
【数４１】
2017168081.tif 000043
と定義される。
【００７９】
最後に、署名は量子化した記述子、すなわち、合成
【数４２】
2017168081.tif 000044
によって定義されるマッピング
【数４３】
2017168081.tif 000045
であり、すべての（（ｐ1，ｎ1），（ｐ2，ｎ2））∈ＰM∪ＰSについて、
【数４４】
2017168081.tif 000046
であることを意味する。
【００８０】
例えば、
【数４５】
2017168081.tif 000047
および
【数４６】
2017168081.tif 000048
と、以下のペア（図１４〜１７に示す）を選択する。
【数４７】
2017168081.tif 000049
【００８１】
演算結果は以下のとおりとなる。
【数４８】
2017168081.tif 000050
【００８２】
なお、ペアａ1はペアａ2に近いため、σ（ａ1）＝σ（ａ4）である。さらに、ペアａ2とａ3は等長であり、マッピングＦは剛体運動の下で不変であるため、Ｆ（ａ2）＝Ｆ（ａ3）＝（１，０，０，−１）であり、σ（ａ2）＝σ（ａ3）である。
【００８３】
ここで、本方法の高速な実行を可能にするような、本方法の一例について説明する。この例では、アルゴリズムは３Ｄ投票原理に従う（すなわち、ハッシュテーブルが使用され、アルゴリズムの出力は、ハッシュテーブルの最も人気のある１つまたは複数のスロットに対応する）。具体的には、アルゴリズムは、一致する第２の対上の第１の対を位置させる全ての位置決め（例えば剛体運動）の中で最良の投票に対応していてもよい。そして、最良の投票は、３Ｄモデル化オブジェクトに含まれるそれぞれの３Ｄ点の、３つのいわゆる「アンカーポイント」を実質的に同じように位置させる最大の位置決めグループを保持するハッシュテーブルスロットに対応していてもよい（すなわち、グループの位置決めは、アンカーポイントをハッシュテーブルの同じスロットに送信する。これは、例えば所定の３×３Ｄハッシュテーブルであり、したがってスロットはこのような所定の３×３Ｄグリッドのセルである）。言い換えれば、第１の対を、一致する第２の対に位置付ける位置決め（例えば、「一致する」とは、上記の形状記述子に対応し、一例では、特に、署名に対応する）は、対の観点（例えば、具体的には、先に例を挙げて述べたように第２の対の観点）で考えられる。そのような候補の位置決めはすべて保持され、（１つまたは複数の）最も「人気のある」ものが検討される。これにより、位置決めＳ１０の迅速な決定が可能になる。アンカーポイントは、３Ｄモデル化オブジェクトに属する整列されていない３つの点であってもよい。これにより、３Ｄ投票が堅牢化される。
【００８４】
ここで、テストされ、特に良く機能するアンカーポイントの一例を説明する。この例では、アンカーポイントは、モデルＭのＡ＝（ｍ1，ｍ2，ｍ3）で表される３点であり、相互の距離ができるだけ大きくなるように選択されている。正確には、
【数４９】
2017168081.tif 000051
である。なお、点ｍ1、ｍ2、およびｍ3にそれぞれ関連付けられた法線ベクトルｎ1、ｎ2、ｎ3は、このアンカーポイントの定義に関与しない。
【００８５】
ここで、上記詳述した例に沿った全体的なアルゴリズムの例について説明する。アルゴリズムの概要は次のとおりである。第１のステップは、ペアからペアへの剛体運動ｄがアンカーポイントＡをどのように変化させるかをテーブルＴ（・）に記憶することである。本ステップは、パフォーマンスのために、以下の命令０３に記載のように、同じ署名を有するペアの対を調査してもよい。
【数５０】
2017168081.tif 000052
【００８６】
整数ｉmaxはアルゴリズムによって調査されたペアからペアへの剛体運動の数である。出力テーブルＴは、当該剛体運動を用いて変換したすべてのアンカーポイントを集める。Ｉｍ（Ｔ）をＴのすべての値の集合とする。すなわち、
【数５１】
2017168081.tif 000053
である。
【００８７】
第２のステップでは、以下の意味において最も頻繁に出現する剛体運動を識別する。ε＞０を閾値とする。値εについては後述する。任意のｔ∈Ｉｍ（Ｔ）を考える。Ｃ（ｔ、ε）は、Ｔ（ｉ）がｔに近くなるような｛１，・・・，ｉmax｝におけるインデックスｉの集合である。正確には
【数５２】
2017168081.tif 000054
である。
【００８８】
定義上、Ｉｍ（Ｔ）において選択された値ｔ*は、最大のＣ（ｔ，ε）を有する。すなわち、
【数５３】
2017168081.tif 000055
である。なお、この「最大の引数」の定式化は一般的なものである。アルゴリズムの一例については後述する。最後のステップは、シーンＳにおいてモデルＭを位置決め／位置特定する最良の剛体運動を返す。これは、
【数５４】
2017168081.tif 000056
が、可能な限り小さくなるような剛性運動ｄ*∈ＳＥ（３）である。ｄ*の算出の一例については後述する。
【００８９】
ここで、対の署名マッチング（上述のアルゴリズム例のステップ０３で使用される）のために保持されるデータ構造の具体例について説明する。この例では、第１の対の記述子の値に量子化マッピングを適用した結果は、本方法の全体的な効率を高めるために、インデックス付きテーブルに格納される。
【００９０】
実際、ある署名を有するＰMのすべての要素を取得することは、アルゴリズムにおいて集中的に使用され得る。例えば、上記の例の命令０３で、「Ｆｏｒ  ａｌｌ  ｘ∈ＰM  ｓｕｃｈ  ｔｈａｔ  σ（ｘ）＝ｋ  ｄｏ  ｂｅｇｉｎ」によってキャプチャされる。プログラミングの観点から、この演算は適切なデータ構造によって補助されて実行される。このデータ構造は、３つのテーブルＴ1、Ｔ2、およびＴ3を含み、以下のように算出することができる。
【００９１】
第１のステップは、Ｔ1（ｋ）がσ（ｘ）＝ｋとなるような要素ｘ∈ＰMの数であるようにテーブルＴ1を算出することである。テーブルＴ1は、すべてのｉについてＴ1（ｉ）＝０で初期化される。
【数５５】
2017168081.tif 000057
【００９２】
このステップの後には、整数ｎは、すべてのｘ∈ＰMについて１≦σ（ｘ）≦ｎとなる。これはσ（ＰM）⊂｛１，・・・，ｎ｝を意味する。なお、σ（ＰM）＝｛１，・・・，ｎ｝である必要はない。すなわち、ＰMの要素の署名ではない｛１，・・・，ｎ｝のいくつかの値が存在してもよい。言い換えれば、Ｔ1（ｉ）＝０となるような整数ｉが存在してもよい。
【００９３】
第２のステップは、（将来の）テーブルＴ3内のアドレスのディレクトリであるテーブルＴ2を算出することである。テーブルＴ2のサイズはｎである。テーブルＴ1は、このステップの後には使用されない。
【数５６】
2017168081.tif 000058
【００９４】
最後のステップは、テーブルＴ3に、同じ署名を有する要素のリストを供給することである。テーブルＴ3のサイズは、
【数５７】
2017168081.tif 000059
であり、テーブルＴ3は、すべての
【数５８】
2017168081.tif 000060
についてＴ3（ｉ）＝０で初期化される。
【数５９】
2017168081.tif 000061
【００９５】
このデータ構造は、以下のように用いられてもよい。シーンｙ∈ＰSの要素とその署名ｋ＝σ（ｙ）が与えられた場合、同じ署名ｋを有するモデル要素ｘ∈ＰMの数ｍがテーブルＴ3内の場所Ｔ2（ｋ）で読み取られる。すなわち、ｍ＝Ｔ3（Ｔ2（ｋ））である。当該モデル要素は、ｊ＝１，２，・・・，ｍについて、テーブルＴ3内の場所Ｔ3（Ｔ2（ｋ）＋ｊ）に配置される。
【００９６】
結果のデータ構造のサイズは
【数６０】
2017168081.tif 000062
であり、３つのステップの累積計算量は
【数６１】
2017168081.tif 000063
であるため、この演算は明らかに最適である。図１８のテーブルは、
【数６２】
2017168081.tif 000064
かつ、σ（ａ）＝σ（ｂ）＝σ（ｄ）＝σ（ｅ）＝２、かつσ（ｃ）＝σ（ｆ）＝４であり、ｎ＝４であるＰM＝｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ｝を有するデータ構造を例示したものである。署名値３を有するＰMの要素数はＴ3（Ｔ2（３））＝Ｔ3（７）＝０である。署名値２を有するＰMの要素数はＴ3（Ｔ2（２））＝Ｔ3（２）＝４であり、それらはＴ3（３）＝ａ、Ｔ3（４）＝ｂ、Ｔ3（５）＝ｄ、Ｔ3（６）＝ｅである。
【００９７】
ここで、（比較的正確な結果に導きつつ）全体的なスピードをさらに増加させるアルゴリズムの例について説明する。この例では、上述の例で説明したように、アルゴリズムは、一致するそれぞれの第２の対上のそれぞれの第１の対を位置させるすべての剛体運動の中で最良の投票に対応する。ここで、各剛体運動は、それぞれの第１の対に付された正規直交軸系と、それぞれの第２の対に付された正規直交軸系のみ（すなわち決定に他のデータは関与しない）に基づいて、特定の高速な方法で決定される（すなわち、ペアからペアへの剛体運動を算出。例えば、上記例のアルゴリズムのステップ０４）。正規直交軸系は、それぞれ、上記２つの点のうちの１つのみとそれに関連付けられた法線ベクトルに基づいて、それぞれの第１の対およびそれぞれの第２の対から決定され（言い換えると、考慮された対のペアのそれぞれについて、それらの間の剛性運動が、２つの正規直交系、すなわち各対につき１つの正規直交系のみに基づいて決定され、各系は、対を定義する情報／データの半分のみ、すなわち、対の上記２つの点のうち１つの位置およびそれに関連付けられた法線ベクトルに基づいて決定される。すなわち、もう一方の点の位置およびそれに関連付けられた法線ベクトルは用いられない）、それにより決定が高速になり、それに応じてアルゴリズム全体が高速になるようにする。
【００９８】
ここで、このような、上記前処理の例と特に相乗的に協働する剛体運動の決定の例（なぜなら、そのような前処理は、この決定の例が特に高速となるような入力である対を残すからである）について説明する。
【００９９】
本例では、剛体運動の算出は、アルゴリズムの命令０４で実行される。２つのペアａ、ａ’が与えられた場合、ある意味でｄ（ａ）がａ’に近づくような剛体運動ｄを算出する
。その原理は、ペアａとａ’にそれぞれ付された２つの直接的な正規直交軸系（Ｏ，Ｕ，
Ｖ，Ｗ）と（Ｏ’，Ｕ’，Ｖ’，Ｗ’）を定義し、そして（Ｏ，Ｕ，Ｖ，Ｗ）を（Ｏ’，
Ｕ’，Ｖ’，Ｗ’）に変換する剛体運動ｄを算出することである。正確には、剛体運動ｄ
は、回転Ｃが行列積
【数６３】
2017168081.tif 000065
で定義されるとき、全ての
【数６４】
2017168081.tif 000066
についてｄ（ｘ）＝Ｃｘ＋Ｄとなるような運動である。そして並進運動ＤはＤ＝Ｏ’−Ｃ
Ｏで定義される。ペア（（ｐ1，ｎ1），（ｐ2，ｎ2））に付された軸系（Ｏ，Ｕ，Ｖ，Ｗ）は、以下のように定義される。第１のベクトルＵは、Ｕ＝ｎ1である。第２のベクトルＶは、Ｕに垂直な平面上のｐ2−ｐ1の正規化投影である。これは２つのステップＶ：＝（Ｉ−ＵＵT）（ｐ2−ｐ1）で算出される。ここでＩは恒等行列であり、
【数６５】
2017168081.tif 000067
である。前処理を行ったため、ｐ2≠ｐ1であり、ｎ1はｐ2−ｐ1に対して共線的でないため、演算が効果的である。第３のベクトルＷは、交差積Ｗ＝Ｕ×Ｖである。最後に原点Ｏはｐ1である。図１９は、軸系の定義を例示している。軸系（Ｏ，Ｕ，Ｖ，Ｗ）はｎ2と長さ
【数６６】
2017168081.tif 000068
に依存しないにもかかわらず、実際には良好な結果が得られる。他方のペアに付された軸系（Ｏ’，Ｕ’，Ｖ’，Ｗ’）についても同様の演算が行われる。図２０は、剛体運動の
定義を例示している。
【０１００】
ここで、ｔ*の最大値の引数を算出することに相当する上記３Ｄ投票の例について説明する。
【０１０１】
構築すると、Ｉｍ（Ｔ）は３Ｄ点の３つ組の有限集合であり、これはＩｍ（Ｔ）の要素が
【数６７】
2017168081.tif 000069
における点として見ることができるということを意味する。閾値ε＞０が与えられた場合、実数の集合
【数６８】
2017168081.tif 000070
は、次のように、全ての区間［ｊε，（ｊ＋１）ε］の和集合として書くことができる。
【数６９】
2017168081.tif 000071
このように、
【数７０】
2017168081.tif 000072
は、ボックスの和集合として書くことができ、
【数７１】
2017168081.tif 000073
となる。すなわち、
【数７２】
2017168081.tif 000074
である。
この例における投票とは、
【数７３】
2017168081.tif 000075
を満たす各ボックス
【数７４】
2017168081.tif 000076
の範囲内のＩｍ（Ｔ）の９つ組の数をカウントし、９つ組の数が最も多いボックスを選択することである。好ましい閾値は、
【数７５】
2017168081.tif 000077
である。
【０１０２】
明確にするため、以下の擬似コード例のアルゴリズムにおける投票を更新するのに、整数のテーブルＶｏｔｅ（ｊ1，・・・，ｊ9）が用いられる。同様に、各ボックスの点の重心を更新するのに、
【数７６】
2017168081.tif 000078
における点のテーブルｂ（ｊ1，・・・，ｊ9）が用いられる。最適化のために、どちらもハッシュ化されたデータ構造に置き換えることができる。整数ＢｅｓｔＶｏｔｅは、現時点で最良の投票であり、工程全体にわたって更新される。整数ＳｅｃｏｎｄＶｏｔｅは、現時点で２番目に良い投票であり、工程全体にわたって更新される。これは重要性レベルに必要である。
【数７７】
2017168081.tif 000079
【０１０３】
重要性レベルは、ＢｅｓｔＶｏｔｅとＳｅｃｏｎｄＶｏｔｅの値を比較するための比率
【数７８】
2017168081.tif 000080
であってもよい。その原理は、ＢｅｓｔＶｏｔｅがＳｅｃｏｎｄＶｏｔｅよりも「はるかに大きい」場合、投票工程は有意であるということであり、典型的には、
【数７９】
2017168081.tif 000081
のときに「多くの」アンカーポイントが同じボックスに変換される。数学的には、投票が有意でないとしても、常に最良の剛体運動（次段落で詳述）が算出可能である。最良の剛体運動を保持するか、あるいは最良のもののうちいくつかを保持するか、あるいは保持しないかの決定は、実装の問題に過ぎず、本方法の適用の仕方による。
【０１０４】
選択された値ｔ*は、ボックス
【数８０】
2017168081.tif 000082
における点の重心であり、すなわち、
【数８１】
2017168081.tif 000083
である。
【０１０５】
便宜上、３つの点ｓ1、ｓ2、ｓ3が明示的となるように記述されている。
【数８２】
2017168081.tif 000084
【０１０６】
図２１〜図２２は、（９次元の状況とは対照的に）２次元の状況における投票工程を示す。図２１は、２Ｄ点の集合Ｉｍ（Ｔ）を示す。図２２は、
【数８３】
2017168081.tif 000085
を覆うε×εのボックスである。選択されたボックスは
【数８４】
2017168081.tif 000086
であり、それは点を最も多く含むからである。すなわち
【数８５】
2017168081.tif 000087
である。２番目に良い投票はＳｅｃｏｎｄＶｏｔｅ＝Ｖｏｔｅ（４，３）＝２であり、重要性レベルは
【数８６】
2017168081.tif 000088
である。
【０１０７】
ここで、最良の剛体運動を算出するための方法の例を示す。
【０１０８】
上記説明によると、ここでは、モデルＭのアンカーポイントＡ＝（ｍ1，ｍ2，ｍ3）をシーンＳの選択された３つ組の点ｔ*＝（ｓ1，ｓ2，ｓ3）に変更する最良の剛体運動ｄ*を見つけることが重要かもしれない。最良の剛体運動ｄ*は、並進運動Ｔ*および回転Ｒ*によって定義され、すべての
【数８７】
2017168081.tif 000089
について、ｄ*（ｘ）＝Ｒ*ｘ＋Ｔ*である。回転Ｒ*および並進運動Ｔ*は、以下のように算出され得る。
【０１０９】
以下のベクトルは、ｍ1、ｍ2、ｍ3を用いて算出される。
【数８８】
2017168081.tif 000090
【０１１０】
ｓ1、ｓ2、ｓ3についても同様である。
【数８９】
2017168081.tif 000091
【０１１１】
次に、行列Ｐが、Ｕ、Ｖ、Ｗ、Ｕ’、Ｖ’、およびＷ’を用いて算出される。
【数９０】
2017168081.tif 000092
【０１１２】
なお、（Ｕ，Ｖ，Ｗ）と（Ｕ’，Ｖ’，Ｗ’）は一般に非直交軸系であり、これにより
Ｐは一般に非直交行列となる。そのため、マッピングＲ*はＰに最も近い回転である。これは一意であり、例えば、文献「Ａｎｄｒｉｙ  Ｍｙｒｏｎｅｎｋｏ，Ｘｕｂｏ  Ｓｏｎｇ，Ｏｎ  ｔｈｅ  ｃｌｏｓｅｄ−ｆｏｒｍ  ｓｏｌｕｔｉｏｎ  ｏｆ  ｔｈｅ  ｒｏｔａｔｉｏｎ  ｍａｔｒｉｘ  ａｒｉｓｉｎｇ  ｉｎ  ｃｏｍｐｕｔｅｒ  ｖｉｓｉｏｎ  ｐｒｏｂｌｅｍｓ，９  Ａｐｒ  ２００９」で説明されているように、特異値分解を用いて算出することができる。最後に、並進運動Ｔ*はＴ*＝ｓ1−Ｒ*ｍ1によって定義される。
【図１】
2017168081.tif 000116
【図２】
2017168081.tif 000117
【図３】
2017168081.tif 000118
【図４】
2017168081.tif 000119
【図５】
2017168081.tif 000120
【図６】
2017168081.tif 000121
【図７】
2017168081.tif 000122
【図８】
2017168081.tif 000123
【図９】
2017168081.tif 000124
【図１０】
2017168081.tif 000125
【図１１】
2017168081.tif 000126
【図１２】
2017168081.tif 000127
【図１３】
2017168081.tif 000128
【図１４】
2017168081.tif 000129
【図１５】
2017168081.tif 000130
【図１６】
2017168081.tif 000131
【図１７】
2017168081.tif 000132
【図１８】
2017168081.tif 000133
【図１９】
2017168081.tif 000134
【図２０】
2017168081.tif 000135
【図２１】
2017168081.tif 000136
【図２２】
2017168081.tif 000137
【外国語明細書】
2017168081.tif 000138
2017168081.tif 000139
2017168081.tif 000140
2017168081.tif 000141
2017168081.tif 000142
2017168081.tif 000143
2017168081.tif 000144
2017168081.tif 000145
2017168081.tif 000146
2017168081.tif 000147
2017168081.tif 000148
2017168081.tif 000149
2017168081.tif 000150
2017168081.tif 000151
2017168081.tif 000152
2017168081.tif 000153
2017168081.tif 000154
2017168081.tif 000155
2017168081.tif 000156
2017168081.tif 000157
2017168081.tif 000158
2017168081.tif 000159
2017168081.tif 000160
2017168081.tif 000161
2017168081.tif 000162
2017168081.tif 000163
2017168081.tif 000164
2017168081.tif 000165
2017168081.tif 000166
2017168081.tif 000167
2017168081.tif 000168
2017168081.tif 000169
2017168081.tif 000170
2017168081.tif 000171
2017168081.tif 000172
2017168081.tif 000173
2017168081.tif 000174
2017168081.tif 000175
【図１】
2017168081.tif 000176
【図２】
2017168081.tif 000177
【図３】
2017168081.tif 000178
【図４】
2017168081.tif 000179
【図５】
2017168081.tif 000180
【図６】
2017168081.tif 000181
【図７】
2017168081.tif 000182
【図８】
2017168081.tif 000183
【図９】
2017168081.tif 000184
【図１０】
2017168081.tif 000185
【図１１】
2017168081.tif 000186
【図１２】
2017168081.tif 000187
【図１３】
2017168081.tif 000188
【図１４】
2017168081.tif 000189
【図１５】
2017168081.tif 000190
【図１６】
2017168081.tif 000191
【図１７】
2017168081.tif 000192
【図１８】
2017168081.tif 000193
【図１９】
2017168081.tif 000194
【図２０】
2017168081.tif 000195
【図２１】
2017168081.tif 000196
【図２２】
2017168081.tif 000197