(57)【要約】      （修正有）【課題】三次元モデルを整列するシステムおよび方法を提供する。【解決手段】それぞれ三次元モデルを示す１つまたは複数の点群（１２）を受け取ることと、点群（１２）から代表データセット（１４）をサンプリングすることと、代表データセット（１４）の可能な局所整列誤差最小値の集合（１６）について解くことと、可能な局所最小値の集合（１６）から代表最小値（１８）を選択することと、代表最小値（１８）を初期推定値として使用して点群（１２）の整列における大域最小値（２０）について解くこととを含む三次元モデル（１０）を整列する方法。【選択図】図１
2007035042.tif 000002
【特許請求の範囲】
【請求項１】
三次元モデル（１０）を整列する方法であって、
それぞれ三次元モデル（１０）を示す１つまたは複数の点群（１２）を受け取ることと、
前記点群（１２）から代表データセット（１４）をサンプリングすることと、
前記代表データセット（１４）の可能な局所整列誤差最小値の集合（１６）について解くことと、
前記可能な局所最小値の集合（１６）から代表最小値（１８）を選択することと、
前記代表最小値（１８）を初期推定値として使用して前記点群（１２）の整列誤差における大域最小値（２０）について解くこととを含む方法。
【請求項２】
さらに、第１の三次元モデル（１０）から第２の三次元モデル（１０）へ第１のデータセット（２２）を補間することを含む請求項１記載の方法。
【請求項３】
可能な局所整列誤差最小値の集合（１６）を前記解くことは、ＴｒＩＣＰまたはＩＣＰアルゴリズム（１０７）を使用する請求項１記載の方法。
【請求項４】
さらに、前記補間データ（２２）を含む出力ファイルを書き込むことを含む請求項２記載の方法。
【請求項５】
三次元モデル（１０）を整列するシステムであって、
三次元モデル（１０）を示す１つまたは複数の点群（１２）を受け取る手段と、
前記点群（１２）から代表データセット（１４）をサンプリングする手段と、
前記代表データセット（１４）の可能な局所整列誤差最小値の集合（１６）について解く手段と、
可能な局所最小値の前記集合（１６）から代表最小値（１６）を選択する手段と、
前記代表最小値（１６）を初期推定値として使用して前記点群（１２）の整列における大域最小値（１６）について解く手段とを備えるシステム。
【請求項６】
さらに、第１の三次元モデル（１０）から第２の三次元モデル（１０）へ第１のデータセット（２２）を補間することを含む請求項５記載のシステム。
【請求項７】
可能な局所整列誤差最小値の集合（１６）を前記解く手段は、ＴｒＩＣＰまたはＩＣＰアルゴリズム（１０７）を使用する請求項５記載のシステム。
【請求項８】
三次元モデル（１０）を整列するためのコンピュータプログラム製品であって、
それぞれ三次元モデル（１０）を示す１つまたは複数の点群（１２）を受け取ることを実行する命令と、
前記点群（１２）から代表データセット（１４）をサンプリングすることを実行する命令と、
前記代表データセット（１４）の可能な局所整列誤差最小値の集合（１６）について解くことを実行する命令と、
前記可能な局所最小値の集合（１６）から代表最小値（１８）を選択することを実行する命令と、
前記代表最小値を初期推定値として使用して前記点群（１２）の整列誤差における大域最小値（２０）について解くことを実行する命令とを含むコンピュータプログラム製品。
【請求項９】
さらに、第１の三次元モデル（１０）から第２の三次元モデル（１０）へ第１のデータセット（１２６）の補間（１２４）を実行する命令を含む請求項８記載のコンピュータプログラム製品。
【請求項１０】
それぞれ三次元モデル（１０）を示す前記点群（１２）を、ＡＮＳＹＳまたはＣＦＤソフトウェア（１０１）から受け取る請求項８記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、三次元モデルを整列するシステムおよび方法に関する。より具体的には、本開示は、三次元航空力学的および熱伝達計算モデルを整列し、モデル間でデータを補間することに関する。
【背景技術】
【０００２】
設計者は、より堅牢で信頼性の高いハードウェアを製作するために熱伝達および航空力学的翼設計に深く関わりつつある。このタイプのモデリングは、三次元構造ソフトウェアおよび三次元計算流体ソフトウェアの両方を使用する必要がある。さらに、このタイプのモデリングは、三次元構造ソフトウェアから三次元計算流体ソフトウェアへ、逆に三次元計算流体ソフトウェアから三次元構造ソフトウェアへ境界条件を渡す必要がある。現在、このプロセスは、ソフトウェアを使用して一方のモデルから他方のモデルへの境界条件を補間することにより実行される。航空力学および熱伝達モデリングに現在の慣例を使用している設計者は、手作業で、２つの三次元モデルを整列し、ソフトウェアを使用して、一方のモデルから他方のモデルへ三次元データを補間しなければならない。
【０００３】
熱伝達および航空力学の両方の解析で一方の三次元モデルから他方のモデルへのデータの補間を行うために、ＳＩＥＳＴＡと呼ばれるソフトウェアパッケージが一般に使用される。しかし、プロセスの整列要素は、手作業で、ＳＩＥＳＴＡに入力されなければならず、これは、設計プロセスに非繰り返し性ステップを導入する。熱伝達および航空力学解析はモデル整列の影響を受けやすい場合があるため、この非繰り返し性要素は、分散と誤差の容認できない発生源となる。
【０００４】
画像処理アプリケーションでは、ＩＣＰ（反復最近傍点）アルゴリズムなどのコンピュータアルゴリズムを使用することで、三次元モデルをデジタル整列することに成功している。ＩＣＰアルゴリズムは、２つの「点群（ポイントクラウド）」の間の整列誤差の局所最小値（local minimum）への単調収束を保証する数理モデルである。これらの「点群」は、モデルの幾何学的データを表す。ＩＣＰアルゴリズムの制限の１つは、最良の整列を表す、整列誤差（alignment error）における多数の局所最小値の１つを返し、大域最小整列誤差を返さないというものである。画像処理分野では大域最小値を求める作業を支援する方法に関する研究論文が多数存在する。しかし、ＩＣＰアルゴリズムを航空力学および熱伝達計算モデリングに適用することに関する研究は、これまで行われていなかった。したがって、このような整列問題に対する大域最小値（global minimum）を求める方法に関する概念は存在していない。
【非特許文献１】"The Trimmed Iterative Closest Point Algorithm," Chetverikov et al., 2002 IEEE, 1051-4651/02, pp 545-549
【非特許文献２】"A Method for Registration of 3-D Shapes," Besl et al., IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, No. 2, Feb. 1992.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、上記従来技術の課題を解決することを目的の一つとする。
【課題を解決するための手段】
【０００６】
本明細書で開示されるのは、それぞれ三次元モデルを示す１つまたは複数の点群を受け取ることと、点群から代表データセットをサンプリングすることと、代表データセットの可能な局所整列誤差最小値の集合について解くことと、可能な局所最小値の集合から代表最小値を選択することと、代表最小値を初期推定値として使用して点群の整列における大域最小値について解くこととを含む三次元モデルを整列する方法である。
【０００７】
また、本明細書で開示されるのは、三次元モデルを示す１つまたは複数の点群を受け取る手段と、点群から代表データセットをサンプリングする手段と、前記代表データセットの可能な局所整列誤差最小値の集合について解く手段と、可能な局所最小値の集合から代表最小値を選択する手段と、代表最小値を初期推定値として使用して点群の整列における大域最小値について解く手段とを含む三次元モデルを整列するシステムである。
【０００８】
さらに本明細書で開示されるのは、三次元モデルを整列するためのコンピュータプログラム製品であって、前記コンピュータプログラム製品は、それぞれ三次元モデルを示す１つまたは複数の点群を受け取ることを実行する命令と、点群から代表データセットをサンプリングすることを実行する命令と、代表データセットの可能な局所整列誤差最小値の集合について解くことを実行する命令と、可能な局所最小値の集合から代表最小値を選択することを実行する命令と、代表最小値を初期推定値として使用して点群の整列誤差における大域最小値について解くことを実行する命令とを含む。
【０００９】
例示的な実施形態による他のシステム、方法、および／またはコンピュータプログラム製品は、以下の図面および詳細な説明を吟味すれば、当業者にとって明白であるか、または明白なものとなるであろう。すべてのこのような追加のシステム、方法、および／またはコンピュータプログラム製品は、この説明に含まれ、本発明の開示の範囲内にあり、付属の請求項により保護されることが意図されている。
【００１０】
付属の図において類似の要素は類似の番号が振られている例示的な図面を参照する。
【発明を実施するための最良の形態】
【００１１】
三次元モデル１０を整列する方法の一実施形態のブロック図が図１に示されている。プロセスブロック１２では、三次元モデル１０を整列する方法は、それぞれが三次元モデルを表す１つまたは複数の点群を受け取る。次いで、三次元モデル１０を整列する方法は、各点群から代表データセットをサンプリングするが、ただし、代表データセットは、三次元モデルの一般的幾何形状が代表データセットにより保持されるように選択され、これはプロセスブロック１４に示されている。代表データセットをサンプリングした後、三次元モデル１０を整列する方法は、プロセスブロック１６に示されているように、可能なすべての局所整列誤差最小値の集合について解く。次いで、プロセスブロック１８で、代表最小値が選択されるが、これは、可能なすべての局所整列誤差最小値の集合の中の最小のものである。プロセスブロック２０で、三次元モデル１０を整列する方法は、ＴｒＩＣＰ（Trimmed Iterative Closest Point：トリム反復最近傍点）またはＩＣＰアルゴリズムのいずれかを点群に適用し、代表最小値を初期推定値として使用することにより点群の整列の大域最小差について解く。適宜、プロセスブロック２２に示されているように、三次元モデル１０を整列する方法は、大域最小値により表される、モデルの最良整列が計算された後、一方の三次元モデルから他方の三次元モデルへのデータの補間を行う。
【００１２】
例示的な一実施形態では、三次元モデル１０を整列する方法は、ＴｒＩＣＰまたはＩＣＰアルゴリズムを使用して、可能な複数の整列のそれぞれについて局所整列誤差最小値を計算し、可能なすべての局所整列誤差最小値の集合を生成する。ＴｒＩＣＰおよびＩＣＰアルゴリズムにはいくつかの制限が内在するため、局所整列誤差最小値は、限定された範囲の整列についてのみ最小値であることを保証できる。この制限を説明するために、三次元モデル１０を整列する方法は、可能なすべての整列がカバーされることを保証する、整列の集合について可能なすべての局所整列誤差最小値を計算する。例えば、多くのＴｒＩＣＰアルゴリズムでは、２０度の広がりに対してしか最小値を保証できないため、このアルゴリズムを三次元空間に適用する場合、可能なすべての整列が含まれるようにするために３１２個の可能な整列の集合が使用される。
【００１３】
上の方法で使用されているようなＴｒＩＣＰおよびＩＣＰアルゴリズムでは、整列問題を、モデル間の整列の誤差を最小にする最小化問題に還元する。単独では、ＴｒＩＣＰアルゴリズムもＩＣＰアルゴリズムも、大域最小解が生成されることを保証せず、したがって大域最小値を求める他の戦略をこのアルゴリズムと併用しなければならない。したがって、ＴｒＩＣＰアルゴリズムおよび三次元モデル間の最良の整列を表す数値求める他の戦略を組み込んだ剛体双方向座標重ね合わせ（ＭＡＴＲＩＣＳ）アルゴリズム（rigid-body interactive coordinate superimposition algorithm）によるモデル整列が開発されている。
【００１４】
上述のように、ＩＣＰおよびＴｒＩＣＰアルゴリズムでは、最良整列が決定されることを保証するために初期推定値は大域最小値から２０度回転の範囲内にある必要がある。大域最小値は知られていないので、局所最小値ではなく大域最小値が決定されるようにするために、ＩＣＰおよびＴｒＩＣＰアルゴリズムは、他の何らかの機能を追加する必要がある。三次元モデルに適用される、この「２０度」という要件は、最小化問題に対し３１２個の可能な局所最小値があることを意味する。したがって、ＭＡＴＲＩＣＳは、サンプリングされたモデルの集合上で可能な３１２個すべての初期推定値について解く。次いで、最終整列のため三次元モデルの元の集合上で、最も小さい局所最小値に対応する初期推定値および対応する局所最小値を使用する。次に、ＴｒＩＣＰアルゴリズムを元の点群に適用し、三次元モデル間の数値的に最もよい整列を作成する。
【００１５】
次に図２を参照すると、ＭＡＴＲＩＣＳアルゴリズム１００の例示的な一実施形態の流れ図が示されている。ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１０１に示されているようなＡＮＳＹＳまたはＣＦＤソフトウェアなどの１つまたは複数のソースから入力を受け取る。入力を受け取った後、ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１０２に示されているように、受け取ったデータをフォーマットし、データをマージして、プロセスブロック１０３に示されているように、完全な三次元モデルを示す点群を形成する。データが入力され、適切にフォーマットされた後、ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１０４に示されているように、点群から代表データセットをサンプリングすることにより粗点群を抽出する。代表データセットが決定された後、ＭＡＴＲＩＣＳアルゴリズム１００は、一般にプロセスブロック１０５として示されている反復プレレジストレーションフェーズ（iterative pre-registration phase）に入る。
【００１６】
プレレジストレーションフェーズは、プロセスブロック１０６に示されているように、３１２個の可能な初期整列の集合から初期推定値を選択することを含む。可能な初期整列のそれぞれについて、ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１０７に示されているように、２つの点群の点の間の対応関係を計算し、プロセスブロック１０８に示されているように、対応関係をソートし、プロセスブロック１０９に示されているように、最大対応関係をトリミングする。ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１１０に示されているように、並進ベクトルおよび回転ベクトルを含むプレレジストレーションベクトルを計算し、プロセスブロック１１１に示されているように、プレレジストレーションベクトルを代表データセットに適用する。プレレジストレーションベクトルを適用した後、ＭＡＴＲＩＣＳアルゴリズム１００は、ＴｒＩＣＰまたはＩＣＰアルゴリズムのいずれかを使用して、代表データセット間の整列誤差の局所最小値が見つかったかどうかを判定し、見つかった場合、ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１１３に進み、見つからなかった場合、プロセスは、プロセスブロック１０７に示されているように、代表データセットの点同士の間の対応関係を計算することに戻ることにより反復する。プロセスブロック１１３で、ＭＡＴＲＩＣＳアルゴリズム１００は、可能なすべての初期整列が解かれたかどうかを判定し、解かれている場合、ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１１４に進み、解かれていない場合、プロセスは、プロセスブロック１０６で他の初期整列推定値を選択することに戻ることにより反復する。
【００１７】
可能なすべての初期整列に対す局所最小値が解かれた後、ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１１４に示されているように、最良の整列解、代表最小値を選択する。プロセスブロック１１５で、ＭＡＴＲＩＣＳアルゴリズム１００は、最良整列解に対応するプレレジストレーションベクトルを代表データセットに適用する。プレレジストレーションベクトルを代表データセットに適用した後、ＭＡＴＲＩＣＳアルゴリズム１００は、元の点群からのデータ点のすべてを三次元モデル内に挿入し戻す。すべてのデータ点が三次元モデル内に挿入され、プレレジストレーションベクトルが適用された後、ＭＡＴＲＩＣＳアルゴリズムは、プロセスブロック１１７として一般に示されている、レジストレーションフェーズに入る。
【００１８】
ＭＡＴＲＩＣＳアルゴリズム１００のレジストレーションフェーズ１１７では、プロセスブロック１１８に示されているように、２つの点群の点の間の対応関係を計算し、プロセスブロック１１９に示されているように、対応関係をソートし、プロセスブロック１２０に示されているように、最大対応関係をトリミングする。ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１２１に示されているように、並進ベクトルおよび回転ベクトルを含むレジストレーションベクトルを計算し、プロセスブロック１２２に示されているように、レジストレーションベクトルを点群に適用する。プロセスブロック１２３に示されているように、レジストレーションベクトルを点群に適用した後、ＭＡＴＲＩＣＳアルゴリズム１００は、ＴｒＩＣＰまたはＩＣＰアルゴリズムのいずれかを使用して、点群の可能な最良の整列が決定されたかどうかを判定し、決定された場合、プロセスはプロセスブロック１２４に進み、決定されていない場合、プロセスは、プロセスブロック１１８に戻り、点群の間の対応関係を再び計算することにより反復する。
【００１９】
可能な最良の整列およびレジストレーションベクトルが決定された後、ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１２４として一般に示される、補間フェーズに進む。補間フェーズは、プロセスブロック１２５として示されている、三次元モデルに対応するデータを登録すること、およびプロセスブロック１２６として示されている、一方の三次元モデルから他方の三次元モデルへのデータの補間を含む。最後に、一方の三次元モデルから他方の三次元モデルにデータが補間された後、ＭＡＴＲＩＣＳアルゴリズム１００は、プロセスブロック１２７に示されているように、出力データファイルを書き込む。
【００２０】
ＭＡＴＲＩＣＳアルゴリズム１００は、ＩＣＰまたはＴｒＩＣＰに加えて、モデルからすべての無関係なノードおよび要素を除去する機能と、設計者がＡＮＳＹＳから「シェル」要素または「ロード」要素を持ち込めるようにする機能と、設計者がＣＦＤから任意の数のＵＩＦを持ち込めるようにする機能と、設計者がＡＮＳＹＳまたはＣＦＤから三角形要素、四辺形要素、または要素の混合を持ち込めるようにする機能と、四辺形要素の双線形補間および三角形要素の線形補間を行う機能と、ＵＩＦ（後処理用）、ＵＯＦ（ＣＦＤ用）、およびロード（ＡＮＳＹＳ用）ファイルを書き出す機能とを含む。さらに、ＭＡＴＲＩＣＳアルゴリズム１００は、三次元モデルの幾何学形状全体を保持する特別に考案されたスキームを使用して、三次元モデルをサンプリングする。
【００２１】
例示的な一実施形態では、ＭＡＴＲＩＣＳアルゴリズム１００は、点群内のそれぞれの点を、
【００２２】
【数１】
2007035042.tif 000003
および
【００２３】
【数２】
2007035042.tif 000004
などのデカルトベクトルとして表すが、ただし、ｍｉおよびｓｉは、２つの別々の点群内の点を表す。２つの点ｍｉとｓｉとの間のユークリッド距離は、
【００２４】
【数３】
2007035042.tif 000005
として定義される。ＭＡＴＲＩＣＳアルゴリズム１００は、ユークリッド距離を使用して、点群の間の最も近い対応する点を見つけ、この情報を使用して、並進ベクトルおよび回転ベクトルを含む、レジストレーションベクトルを計算する。並進ベクトルは、点群を並進させるために使用され、回転ベクトルは、点群を回転させるために使用される。レジストレーションベクトルおよび対応する単位回転行列は、
【００２５】
【数４】
2007035042.tif 000006
として定義される。
【００２６】
ＭＡＴＲＩＣＳアルゴリズム１００が整列誤差を最小化し、レジストレーションを計算するために使用する関数は、
【００２７】
【数５】
2007035042.tif 000007
である。ただし、最適な並進ベクトルは、
【００２８】
【数６】
2007035042.tif 000008
であり、最適な回転ベクトルは単位固有ベクトル
【００２９】
【数７】
2007035042.tif 000009
であり、これは、
【００３０】
【数８】
2007035042.tif 000010
【００３１】
【数９】
2007035042.tif 000011
および
【００３２】
【数１０】
2007035042.tif 000012
とする、行列
【００３３】
【数１１】
2007035042.tif 000013
の最大固有値に対応する。
【００３４】
ＭＡＴＲＩＣＳアルゴリズム１００は、さらに、一方の三次元モデルから他方の三次元モデルへのデータの補間を行う機能も備える。例えば、熱伝達解析の場合、ＭＡＴＲＩＣＳアルゴリズム１００は、ループ内で２回実行される。これは、ＡＮＳＹＳモデルをＣＦＤモデルに合わせて整列し、ＡＮＳＹＳモデルからＣＦＤモデルへ温度を補間するために使用される。これは、さらに、ＣＦＤモデルをＡＮＳＹＳモデルに合わせて整列し、ＣＦＤモデルからＡＮＳＹＳモデルへ熱伝達係数および圧力を補間するために使用される。同様に、航空力学解析の場合、ＭＡＴＲＩＣＳアルゴリズム１００は、ＡＮＳＹＳモデルをＣＦＤモデルに合わせて整列し、ＡＮＳＹＳモデルからＣＦＤモデルへモデル変位を補間する。
【００３５】
本発明は、例示的な実施形態に関して説明されているが、当業者であれば、本発明の範囲から逸脱することなく、さまざまな変更を加え、これらの要素の代わりに同等物を使用できることを理解するであろう。さらに、本発明の本質的範囲から逸脱することなく、さまざまな修正を行って、特定の状況または材料を本発明の教示に適合させることができる。したがって、本発明は、本発明を実施するために考えられた最良のまたは唯一の様式として開示されている特定の実施形態に限定されないことが意図されているが、本発明は、付属の請求項の範囲内にあるすべての実施形態を含むことが意図されている。さらに、第１、第２などの用語を使用していても、順序または重要性を表すわけではなく、むしろ、第１、第２などの用語は、一方の要素を他方の要素から区別するために使用される。さらに、「１つの」などの数詞が使用されている場合や、数詞が使用されていない場合であっても、この数詞の存在／不存在が数量の制限を表すわけではなく、むしろ、参照されている項目のうちの少なくとも１つが存在することを表す。
【図面の簡単な説明】
【００３６】
【図１】三次元モデルを整列する方法の例示的な実施形態のブロック図である。
【図２】剛体双方向座標重ね合わせアルゴリズム１００を介したモデル整列の例示的な実施形態の流れ図である。
【符号の説明】
【００３７】
１０  三次元モデル
１２  点群
１４  代表データセット
１６  可能な局所整列誤差最小値の集合
１８  代表最小値
２０  大域最小値
２２  第１のデータセット
１００  ＭＡＴＲＩＣＳアルゴリズム
１０１  ＡＮＳＹＳまたはＣＦＤソフトウェア
１０７  ＴｒＩＣＰまたはＩＣＰアルゴリズム
１２４  補間
１２６  第１のデータセット
【図１】
2007035042.tif 000014
【図２】
2007035042.tif 000015