(57)【要約】      （修正有）【課題】３線テンソルを使用して、ローカル３Ｄ表面形状を再構築する。【解決手段】システムは、３ビュー光学ヘッドと、機械式マニピュレータと、ローカル３Ｄ表面形状再構築ユニットと、表面形状スティッチユニットとを含む。３ビュー光学ヘッドは、物体の少なくとも一部分の少なくとも３つのビューを生成するように動作可能である。機械式マニピュレータは、物体の第１の部分が見える第１の相対的向きから、第１の部分とオーバラップする部分が見える第２の相対的向きまで、物体と光学ヘッドとの向きを変更するように動作可能である。ローカル３Ｄ表面形状再構築ユニットは、光学ヘッドによって生成された第１および第２の部分の３つのビューのうちの少なくとも２つに基づいて、表面形状のローカル再構築を生成するように動作可能である。表面形状スティッチユニットは、物体の第１および第２の部分の相対位置を決定するように動作可能である。【選択図】図１
2008145431.tif 000002
【特許請求の範囲】
【請求項１】
物体の表面形状を再構築するための３Ｄ表面形状再構築システムであって、
Ａ．  前記物体の、第１および第２部分の各第１および第２三次元表示を生成すべく構成された表明形状部分生成器モジュールであって、前記第１および第２三次元表示は、前記物体の、各部分の複数の二次元表示を備える、各二次元表示セットから生成されるモジュールと、
Ｂ．  第１および第２三次元表示から前記物体の前記第１および第２部分の両方の単一の三次元表示を生成すべく構成された表面形状ステッチ・モジュールと、を具備することを特徴とするシステム。
【請求項２】
二次元表示の両方のセットが、少なくとも表面形状の領域（以下、「オーバーラップ領域」と呼ばれる領域）の投影と、表面形状部分生成器モジュールと、を含む請求項１に記載のシステムにおいて、
Ａ．  前記二次元表示セットのうちの、選択されたセットの二次元表示の中に、前記オーバーラップ領域内の、少なくとも一つの点の投影の位置を決定すべく構成された投影位置決定モジュールと、
Ｂ．  前記選択されたセットに関する、少なくとも一つの点の三次元表示を生成すべく構成された三次元表示生成モジュールと、
Ｃ．  前記投影位置決定モジュールおよび前記三次元表示生成モジュールによって使用される前記二次元表示セットのうちの、各セットを選択すべく構成された制御モジュールと、を具備することを特徴とするシステム。
【請求項３】
投影位置決定モジュールは、
Ａ．  対応ペアにおける、各二次元表示上の表面形状の同一の点の投影の位置に関する変位値を決定すべく構成されたセット間変位値生成モジュールであって、前記対応ペアは、前記二次元表示セットの各々から、一つの二次元表示を備えるモジュールと、
Ｂ．  前記二次元表示セットのうちの一つからの対応ペアの二次元表示上の、および前記二次元表示セットのうちの前記一つからの、別の各二次元表示上の表面形状の同一点の投影の位置に関係する変位値を決定すべく構成されたセット内変位値生成モジュールと、
Ｃ．  前記表面形状からの一点の投影に対応する、前記二次元表示セットのうちの、もう一つから対応ペアの二次元表示における、少なくとも一つの点について、
（ｉ）  前記対応ペアにおける二次元表示上の表面形状の同一点の投影の位置に関係する変位値を使用し、前記二次元表示セットのうちの前記一つから対応するペアの二次元表示における、少なくとも一点の投影の位置を決定し、
（ｉｉ）  前記二次元表示セットのうちの前記一つから、各ほかの二次元表示について、前記二次元表示セットのうちの前記一つからの対応ペアの二次元表示上の、および前記二次元表示セットのうちの前記一つからの、他の各二次元表示上の表面形状の同一点の投影に関係する変位値を使用し、前記二次元表示セットのうちの前記一つから、それぞれ一つの二次元表示の二次元表示における、少なくとも一つの点の投影の位置を決定すべく、構成された位置決定モジュールを具備する請求項２に記載のシステム。
【請求項４】
前記セット間変位値生成モジュールは、
Ａ．  前記オーバーラップ領域内の対応ペアにおける、各二次元表示での投影の強度の勾配に関して、遠い方の変位値を決定すべく構成された遠距離対応モジュールと、
Ｂ．  前記遠い方の変位値を使用し、前記オーバーラップ領域内の少なくとも一つのウィンドウ内の対応ペアにおける、各二次元表示での投影の強度の勾配に関して、前記変位値を決定すべく構成された対応モジュールとを具備する請求項３に記載のシステム。
【請求項５】
前記第１および第２の三次元表示は、各第１および第２座標系に関係し、前記ステッチ・モジュールは、前記第１座標系を前記第２座標系に関係させるべく構成される、請求項１に記載のシステム。
【請求項６】
前記ステッチ・モジュールは、前記第１座標系を前記第２座標系に関係させることにおいて、回転”Ｒ”と並進”ｔ”とを決定し、各点｛Ｐｉ｝（”ｉ”は整数）について、前記第１座標系に関する前記表面形状の再構築の各点を表示し、｛Ｑｉ｝について、前記第２座標系に関する対応する各点を表示すべく、
【数１】
2008145431.tif 000014
を最小化するように構成される、請求項５に記載のシステム。
【請求項７】
物体の表面形状を再構築するための３Ｄ表面形状再構築方法であって、
Ａ．  前記物体の、各第１および第２部分の第１および第２三次元表示を生成すべく構成された表明形状部分生成器モジュールであって、前記第１および第２三次元表示は、前記物体の各部分の複数の二次元表示を備える各二次元表示セットから生成するステップと、
Ｂ．  第１および第２三次元表示から前記物体の前記第１および第２部分の両方の単一の三次元表示を生成するステップとを具備することを特徴とする方法。
【請求項８】
物体の表面形状を再構成する３Ｄ表面形状再構成システムを提供すべく、コンピュータに接続して使用されるコンピュータ可読媒体であって、
Ａ．  前記コンピュータが、前記物体の、各第１および第２部分の第１および第２の三次元表示を生成することを可能にすべく構成された表面形状部分生成器モジュールであって、前記第１および第２の三次元表示が、前記オブジェクトの、各部分の複数の二次元表示を具備する、各二次元表示セットから生成されるモジュールと、
Ｂ．  前記コンピュータが、前記第１および第２の三次元表示から、前記オブジェクトの前記第１および第２部分の両者の合体した三次元表示を生成することを可能にすべく構成された表面形状ステッチ・モジュールとをエンコードさせたコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元表面形状再構築のための装置および方法に関する。
【背景技術】
【０００２】
本発明は、３次元（以下“３Ｄ”という）表面再構築のための装置および方法に関する。
【０００３】
３Ｄ表面再構築に関連する計算方法は、以下の論文、 “Ｔｒｉｌｉｎｅａｒｉｔｙ  ｏｆ  ｔｈｒｅｅ  ｐｅｒｓｐｅｃｔｉｖｅ  ｖｉｅｗｓ  ａｎｄ  ｉｔｓ  ａｓｓｏｃｉａｔｅｄ  ｔｅｎｓｏｒ”、ＳｈａｓｈｕａおよびＷｅｒｍａｎ、ＩＣＣＶ（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ）’９５、１９９５年６月、  “Ｒｅｌａｔｉｖｅ  ａｆｆｉｎｅ  ｓｔｒｕｃｔｕｒｅ：  ｃａｎｏｎｉｃａｌ  ｍｏｄｅｌ  ｆｏｒ  ３Ｄ  ｆｒｏｍ  ２Ｄ  ｇｅｏｍｅｔｒｙ  ａｎｄ  ａｐｐｌｉｃａｔｉｏｎｓ”、ＳｈａｓｈｕａおよびＮａｖａｂ、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ＰＡＭＩ，１８（９）、１９９６年９月、“Ａｌｇｅｂｒａｉｃ  ｆｕｎｃｔｉｏｎｓ  ｆｏｒ  ｒｅｃｏｇｎｉｔｉｏｎ”、Ａ．Ｓｈａｓｈｕａ、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ＰＡＭＩ，１７（８）、１９９５年８月に記載されている。
【０００４】
非接触測定のための最新式の方法の調査は、Ｔａｔｔｅｒｓｏｎ，Ｋ．Ｇ．の“Ｌａｓｅｒ  ｍｅａｓｕｒｅｍｅｎｔ  ｆｉｎｄｓ  ｉｔｓ  ｍａｒｋｅｔｓ”、Ｐｈｏｔｏｎｉｃｓ Ｓｐｅｃｔｒａ、１９９６年１０月に記載されている。
【０００５】
本明細書に記載されたすべての文献およびそこに引用されている文献、ならびにイスラエル特許出願第１１３４９６号および米国特許出願第０８／４９７２２４号（その開示は１９９６年１０月３１日に発行された国際公開ＷＯ９６／３４３６５号に対応する）および第０８／７８７３４５号（その開示は米国特許第５５９８５１５号に対応する）の開示は、参照により本明細書に組み込まれる。
【０００６】
スペックル（ｓｐｅｃｋｌｅ）計測法およびスペックル干渉計は様々な応用例について知られている。スペックル計測法では、検査または測定するために探求された物体上でスペックルが生成される。注目（ｉｎｔｅｒｅｓｔ）物体上でこのように生成されたスペックルは、注目物体の各表面とその上でスペックルを生成するために使用するレーザまたは他の光源との間の角度関係に非常に依存する。スペックル計測法については、Ｓｐｅｃｋｌｅ Ｍｅｔｒｏｌｏｇｙ、Ｒａｊｐａｌ Ｓ．Ｓｉｒｏｈｉ(Ｅｄ.)、Ｍａｒｃｅｌ Ｄｅｋｋｅｒ，Ｉｎｃ.、１９９３年に記載されている。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、新規かつ非常に効率のよい３Ｄ表面形状再構築システムを提供しようとするものである。
【課題を解決するための手段】
【０００８】
本発明の好ましい実施形態により、所与の精度まで物体の表面形状を再構築するための３Ｄ表面形状再構築システムが提供され、このシステムは、 物体の少なくとも一部分の少なくとも３つのビュー（ｖｉｅｗ）を生成するように動作可能な３ビュー光学ヘッドと、物体の第１の部分が見える第１の相対的向きから、物体の第２の部分であって第１の部分とオーバラップする部分が見える少なくとも１つの第２の相対的向きまで、所与の精度未満の精度で物体と光学ヘッドとの相対的向きを変更するように動作可能な機械式マニピュレータと、 光学ヘッドによって生成された第１および第２の部分の３つのビューのうちの少なくとも２つに基づいて、物体の第１および第２の部分の表面形状を再構築するように動作可能なローカル３Ｄ表面形状再構築ユニットと、 物体の第１および第２の部分の相対位置を決定するように動作可能な表面形状スティッチユニット（ｓｔｉｔｃｈｉｎｇ ｕｎｉｔ）とを含む。
【０００９】
本発明の好ましい実施形態によれば、機械式マニピュレータは、物体を移動するように動作可能な物体マニピュレータを含む。
【００１０】
好ましくは、機械式マニピュレータは、光学ヘッドを移動するように動作可能な光学ヘッドマニピュレータを含む。
【００１１】
本発明の好ましい実施形態によれば、光学ヘッドによって生成された３つのビューは、３Ｄ表面形状再構築がそれに基づく２つのビューと、３つのビューのそれぞれの内部の向きと３つのビューの相対的向きとを表すテンソルがそれから計算される第３のビューとを含む。
【００１２】
好ましくは、物体は、 ３つのビューのうちの１つで見られる、物体の第１のセクションと、３つのビューのうちの他のビューで見られる、物体の第２のセクションと、第１のセクションと第２のセクションに含まれる、物体のオーバラップセクションとを含み、３Ｄ表面形状再構築ユニットは、オーバラップセクションのテクスチャを分析するように動作可能なオーバラップセクション分析器を含む。
【００１３】
本発明の好ましい実施形態によれば、表面形状スティッチユニットは、第１の部分とオーバラップする第２の部分の１セクションのテクスチャを分析し、それにより、第１の部分と第２の部分の相対位置を決定するように動作可能なオーバラップテクスチャ分析器を含む。
【００１４】
テクスチャは、物体の表面テクスチャまたはテクスチャ付けプロセスによって物体に付着されたテクスチャを含むことができる。
【００１５】
好ましくは、テクスチャは、物体と光学ヘッドとの相対的向きの変動の結果として変化することはない。
【００１６】
本発明の好ましい実施形態によれば、テクスチャ付けプロセスは、物体上にパターンを重ね合わせるための光学プロセスを含む。好ましくは、光学プロセスは、物体上にスペックルパターンを投影することを含む。
【００１７】
好ましくは、テクスチャは物体上に投影される。
【００１８】
本発明の好ましい実施形態によれば、テクスチャは物体上に投影されたスペックルパターンである。
【００１９】
好ましくは、このシステムは、それぞれが物体上にランダムスペックルパターンを投影する、複数のスペックル生成器を含む。
【００２０】
各スペックル生成器は好ましくは、その上にスペックルパターンが生成され、それにより拡散器（ｄｉｆｆｕｓｅｒ）から物体の一部分上にスペックルパターンを投影するために光が投影される拡散器を含む。
【００２１】
好ましくは、各スペックル生成器は、レンズを介してレーザ光を前記拡散器上に向けるレーザダイオードを含む。
【００２２】
本発明の好ましい実施形態によれば、拡散器はホログラフィ拡散器である。
【００２３】
さらに、本発明の好ましい実施形態により、 結像（ｉｍａｇｉｎｇ）ヘッドと、結像すべき物体と結像ヘッドとの間の相対位置を変更するための位置決め装置と、物体上にスペックルパターンを投影する少なくとも１つのスペックル生成器であって、そのスペックルパターンは物体に対して固定され、そこから結像ヘッドによってそれが見られる角度によって変化しない、少なくとも１つのスペックル生成器と、複数の画像のうちの様々な画像上のスペックルパターンの一部分を付き合わせることにより、それに対する異なる相対位置で結像ヘッドによって見られる通りに物体の複数の画像を結合するための画像結合器とを含む、３次元結像システムが提供される。
【００２４】
また、本発明の好ましい実施形態により、物体の表面形状を再構築するための３Ｄ表面形状再構築システムも提供され、このシステムは、光学ヘッドと、少なくとも５自由度で物体と光学ヘッドとの相対的向きを変更するように動作可能な機械式マニピュレータであって、物体を移動するように動作可能な物体マニピュレータと、光学ヘッドを移動するように動作可能な光学ヘッドマニピュレータとを含む、機械式マニピュレータと、光学ヘッドによって生成された物体の少なくとも一部分の画像を分析することにより、物体の表面形状を再構築するように動作可能な３Ｄ表面形状再構築ユニットとを含む。
【００２５】
好ましくは、機械式マニピュレータは、物体の表面全体が光学ヘッドによって結像されるように物体と光学ヘッドとの複数の相対的向きを提供し、表面形状スティッチユニットは物体の表面全体を再構築するように動作可能である。
【００２６】
さらに、本発明の好ましい実施形態により、物体の表面形状を再構築するための３Ｄ表面形状再構築システムが提供され、このシステムは、物体の表面上に存在する多数の位置を計算するように動作可能な表面位置計算ユニットを含む。
【００２７】
さらに、本発明の好ましい実施形態により、物体の３Ｄ表面形状を再構築するための３Ｄ表面形状再構築方法が提供され、この方法は、物体と光学ヘッドとの相対的向きを手動で変更し、対応する複数の光学ヘッド／物体の相対的向きに関する物体の少なくとも一部分の複数の画像を生成するステップと、複数の画像を分析することにより、物体の３Ｄ表面形状を再構築するステップとを含む。
【００２８】
本明細書に示し記載するシステムの好ましい実施形態の特定の利点は、従来システムでは物体の表面の上で高精度走査運動を行うために使用する精密機械要素なしに、このシステムが物体の３Ｄ表面形状を正確に再構築できることである。
【００２９】
このシステムは、その一部分のみが固定結像装置によって捕捉可能になるようなサイズおよび／または形状を有する物体の再構築に特に適している。
【００３０】
本明細書に示し記載するシステムの好ましい実施形態の他の利点は、どのようなものであっても人間の介入なしに、完全に自動的な表面再構築を行えることである。
【００３１】
本明細書に示し記載するシステムの好ましい実施形態の他の利点は、特に高密度の再構築済み表面ポイントが得られることである。
【００３２】
本発明のロボットは好ましくは、物体を操作するための垂直自由度と、光学ヘッドを操作するための垂直自由度とを含む、６自由度を有する。あるいは、このような垂直自由度のうちの一方だけが得られる場合もある。
【００３３】
本発明は、添付図面に関連して示す以下の詳細な説明から理解されるだろう。
【発明を実施するための最良の形態】
【００３４】
本発明は、物体の表面形状を再構築するために動作可能な３次元表面形状再構築システムを提供する。本発明のシステムの特定の特徴は、従来システムでは物体の表面の上で高精度走査運動を行うために使用する精密機械要素なしに、それが物体の３Ｄ表面形状を正確に再構築できることである。このシステムは、その一部分のみが固定結像装置によって捕捉可能になるようなサイズおよび／または形状を有する物体の再構築に特に適している。本明細書に示し記載するシステムの他の利点は、どのようなものであっても人間の介入なしに、完全に自動的な表面再構築を行えることである。
【００３５】
図１を参照すると、同図は、本発明の好ましい実施形態により構築され、動作可能な３Ｄ表面結像再構築システムの簡略半絵半ブロック図である。
【００３６】
図１のシステムでは、位置決めアセンブリ１０は、それぞれが少なくとも２通りの、好ましくは少なくとも３通りの観点から見て、所定のシーケンスで結合すべき注目物体の一部分同士がオーバラップするように注目物体２０の一部分と光学ヘッド３０とがオーバラップするように、相対的に大きく光学的にテクスチャを付けた注目物体２０と光学ヘッド３０との相対運動を行うように動作可能である。このような各オーバラップ部分から物体の表面の一部分が再構築され、このように再構築された部分は好ましくはその後、“スティッチ”され、物体の表面全体または表面全体のうち見えた部分または注目部分のいずれかからなる統一再構築が形成される。テクスチャ付き表面は、スティッチに“向きの手がかり”を提供することにより、再構築した個々の表面部分をスティッチして単一の再構築化表面の形成を容易にする。
【００３７】
位置決めアセンブリ１０は好ましくは、光学ヘッド３０とそれにより結像すべき注目物体２０との相対位置決めのために合計６自由度を提供する。
【００３８】
本発明の好ましい実施形態によれば、光学ヘッド３０は、マスト３３上に取り付けられた取付けアーム３４上に選択可能な方式でしかも軸３２の周りを回転可能な方式で位置決めされ、マスト３３内に定義される垂直軸３６に沿って選択可能な方式で上下することができる。マストは、固定ベース４２に対して、それぞれ相互に垂直なＸ軸３８およびＹ軸４０に沿って水平に移動することができる。
【００３９】
物体サポートアセンブリ４４は、ベース４２に対して固定され、垂直軸４６に沿って垂直にしかも軸４６の周りを回転可能なやり方で注目物体を位置決めする物体サポート４５を含む。
【００４０】
電気モータ（図示せず）あるいは他の適当な位置決め駆動装置は、光学ヘッド３０および注目物体を前述の６自由度内で互いに対して位置決めするように動作可能である。
【００４１】
本発明の好ましい実施形態によれば、複数のテクスチャ生成器４８が物体サポート４５に固定され、それにきわめて接近して配置されており、そのテクスチャ生成器は注目物体２０上にテクスチャパターンを投影するように動作可能である。本発明の特定の特徴は、光学ヘッド３０によるその結像中の間、テクスチャ付きパターンが注目物体に対して精密に固定された関係を維持することである。スケーリング物体５０は、後述するように、テンソルベースのスケーリングを実行するために使用することができる。
【００４２】
本発明の他の特定の特徴は、従来技術とは対照的に、構造光ではなく未構造光を使用して物体上にテクスチャを作成し、個々の画像内の対応する特徴を検出しやすくすることである。
【００４３】
光学ヘッド３０と注目物体２０との相対位置決めの制御は、通常はパーソナルコンピュータ内に実現される捕捉制御ユニット６２の一部を形成する動き制御装置６０によって行われる。この動き制御装置は、Ｓｉｌｉｃｏｎ Ｇｒａｐｈｉｃｓのワークステーションなどのワークステーション６６内に実現される経路計画（ｐａｔｈ ｐｌａｎｎｉｎｇ）モジュール６４から出力を受け取る。経路計画モジュール６４は、適当なユーザインタフェース６７を介してユーザ入力に応答し、その代わりにまたはそれに加えてワークステーション６６に供給可能なＣＡＤファイル６８の出力に応答する。
【００４４】
光学ヘッド３０への操作入力は画像捕捉回路７０によって供給され、光学ヘッド３０からの画像出力は画像捕捉回路７０に供給されるが、その画像捕捉回路は、経路計画モジュール６４から入力を受け取り、ワークステーション６６内に実現されるテンソルベースの３Ｄ表面再構築モジュール７２に出力を供給する。また、モジュール７２は、ＣＡＤファイル６８から入力を受け取り、注目物体を表す雲状ポイント（ｃｌｏｕｄ ｏｆ ｐｏｉｎｔｓ）または雲状ポイントとＣＡＤファイル６８との比較の結果を供給する。
【００４５】
また、照明制御回路７６も、経路計画モジュール６４から入力を受け取り、テクスチャ生成器４８に出力を供給する。
【００４６】
本明細書では、“光学テクスチャ”という用語は、表面の不均一な光学特性を意味するために使用する。光学テクスチャは、表面上に光学パターンを投影することにより、光学手段によって生成することができ、あるいは表面粗さまたは表面の色の変化などの表面特性による場合もある。
【００４７】
次に図２を参照すると、同図は、本発明の好ましい実施形態により構築され、動作可能な光学ヘッドの好ましい実施形態を示している。この光学ヘッドは、その上に複数のカメラ１０４が取り付けられたシャシ１０２を含み、そのカメラは通常は３つであり、好ましくはすべて共通の点に焦点が合っている。カメラ１０４はそれぞれ、ＣＣＤカメラなど、適当なタイプの電子カメラにすることができる。
【００４８】
本発明の好ましい実施形態によれば、シャシ１０２上には、カメラ１０４によって見ている注目物体の諸領域上に補助テクスチャを投影するためのプロジェクタ１０６も取り付けられている。プロジェクタは、その構成のために、テクスチャ生成器９０によって設けた投影テクスチャが欠落している物体の諸領域を見ることが望ましい場合に有用である。
【００４９】
また、本発明の好ましい実施形態により、照明ランプ１０８も設けられている。このランプは、通常、テクスチャ生成器９０によって生成されたテクスチャを使用して画像の自動“スティッチ”が行われるシステムの自動動作中には使用しないが、手動経路計画モードで  システムを操作するためには有用である。
【００５０】
次に図３を参照すると、同図は、図１のシステムで使用するテクスチャ生成器の一部を形成する照明モジュール１２０の簡略断面図である。通常、各テクスチャ生成器９０は複数の照明モジュール１２０を使用し、その照明モジュールはそれぞれ、注目物体上に固定ランダムテクスチャパターンを投影するように動作可能である。
【００５１】
ただし、注目物体上のランダムテクスチャパターンの位置がそれに対して固定されるように、テクスチャ生成器９０は注目物体に対して固定されていることに留意されたい。通常、注目物体の所与の領域は、複数のテクスチャ生成器９０からその上にテクスチャパターンがすでに投影されている可能性がある。このため、広い照明到達範囲角度が得られ、様々な表面の向きをより適切に照らすことになる。さらに、テクスチャパターンのランダム性のため、これは本発明のシステムの動作に干渉または影響することはない。
【００５２】
各照明モジュール１２０は、通常、機械的取付けハウジング１２２を含み、その一方の端部には単一モードレーザダイオード１２４が設けられ、もう一方の端部にはホログラフィ拡散器１２６が設けられている。レーザダイオード１２４とホログラフィ拡散器１２６の中間には集束レンズ１２８が配置されている。レーザダイオード出力がホログラフィ拡散器１２６に衝突すると、拡散器は注目物体上に投影されるスペックルを生成し、したがって、ランダムパターンでその物体を効果的に“ペイント”する。光学ヘッド３０によってその物体を見ている間に照明モジュール１２０と注目物体との相対運動は実際にはまったく発生せず、したがって、ランダムパターンは注目物体上の基準パターンとして機能することができ、高精度でその別々の画像の“スティッチ”を可能にすることは重要なことである。
【００５３】
注目物体上に投影された個々のパターンスポットの平均サイズは、レーザダイオード１２４および拡散器１２６に対するレンズ１２８の光学パワーおよび位置によって決定することができる。注目物体上での投影の成角およびその強度分布の制御を可能にするので、ホログラフィ拡散器を使用することが好ましい。また、それにより、テクスチャパターンは空間周波数が変動するパターンで構成することができる。
【００５４】
図１２Ａ〜図１２Ｆに関連して後述するように、周波数が変動するパターン成分を使用すると、最初に低周波パターンを使用して“対応プロセス”を行い、高周波パターンを使用してより高精度へと進化することができる。
【００５５】
スペックル生成拡散器を使用することは本発明の特定の特徴である。このような拡散器は、結像技法に基づく既存のテクスチャ投影システムとは対照的に、微細パターンと大きい被写界深度を提供しながらその上にスペックルを投影すべき注目物体から比較的短距離のところで使用することができる。
【００５６】
好ましくは、スペックル生成拡散器は２次元ランダム回折格子である。本発明の好ましい実施形態によれば、この拡散器は、所望の全体パターン構成を提供するホログラフィ光成形拡散器である。たとえば、ホログラフィ光成形拡散器は、矩形の全体スペックルパターンを提供するために使用することができる。
【００５７】
このようにスペックルを使用するのは、注目物体上にレーザビームが直接衝突するとスペックルがその上に生成される従来技術のスペックル計測法とは区別するためである。従来技術では、それから使用される角度の関数として変化するスペックルパターンを生成する。本発明では、スペックルパターンはそれから見られる角度に対して不変でなければならない。
【００５８】
次に図１５を参照すると、同図は、図１のテンソルベースの３Ｄ表面再構築モジュール５０のための好ましい操作方法を記載したものである。図１５の方法は、本発明の好ましい実施形態により物体の３Ｄ表面構造を再構築するように動作可能であり、以下のステージを含む。
【００５９】
ステージ６０４： それに沿って物体の結像器（ｉｍａｇｅｒ）が前進する結像経路を生成する。通常、画像がスティッチされる順序は結像経路に基づくものである。
【００６０】
ステージ６１０： テンソルデータを生成することにより、３Ｄ表面構造再構築プロセスのためのスケーリングを行う。
【００６１】
ステージ６２０： 注目物体を結像する。
【００６２】
ステージ６３０： ローカル３Ｄ表面構造再構築 
【００６３】
ステージ６４０： 再構築したローカル３Ｄ表面構造をスティッチし、注目物体のための完全実際表面構造を形成する。
【００６４】
ステージ６４０で生成された完全実際表面構造は、別々にまたは組み合わせて実施可能なステージ６５０〜７２０の応用例を含みかつそれに限定されない幅広い種類の応用例で有用である。このような応用例について次に説明する。
【００６５】
ステージ６５０： 注目物体の実際の表面構造を所望の表面構造と比較する。
【００６６】
通常、所望の表面構造はＣＡＤモデルによって定義され、この比較プロセスは、実際の構造と所望の構造を位置合わせし、各再構築化ポイントとＣＡＤ表面との距離を計算することによって行われる。この距離は本明細書では“再構築化ポイントの偏差”ともいう。
【００６７】
あるいは、所望の表面構造は“金製部品”によって定義され、図１５のプロセスは金製部品と、その金製部品に類似させるべき注目物体について、別々に行われる。結果として得られる２つの雲状ポイントは位置合わせされ、次に、１つの雲内の各個々のポイントについて以下のステップを実行することによって比較される。
【００６８】
ａ．個々のポイントに最も近い、他の雲内の所定の数のポイント（通常は３〜６つのポイント）を選択する。
【００６９】
ｂ．これらのポイントに近い、平面などの幾何表面を生成する。
【００７０】
ｃ．この幾何表面から個々のポイントまでの距離を計算する。この距離は本明細書では“個々の再構築化ポイントの偏差”ともいう。
【００７１】
目視検査を使用する応用例では、各再構築化ポイントは好ましくはその偏差に基づいて着色されている。たとえば、濃い色調は偏差が大きいポイントを意味し、淡い色調は偏差が小さいポイントを意味する。あるいは、異なる色を使用して、異なる範囲の偏差を示すこともできる。
【００７２】
ステージ６５０は、実際の生産出力に基づいて金型またはその他の製造工具を補正する工具補正応用例(ステージ６６０)、品質管理応用例（ステージ６７０）
などの応用例の前段階である。
【００７３】
あるいは、たとえば、ステージ６８０〜７２０の応用例のうちの１つが対象になる場合、ステージ６５０は省略することができる。
【００７４】
ステージ６８０は、スティッチステージ６４０の出力に基づいて、物体のＣＡＤ表面のＣＡＤモデルを生成する。このプロセスは、ミシガン州アナーバーのＩｍａｇｅ Ｗａｒｅ Ｃｏｒｐ．から販売されているＳｕｒｆａｃｅｒなどの市販の適当な工具を使用して実施することができる。
【００７５】
このステージは、ＣＡＤモデルを使用して、たとえば、青写真を作成し、それに基づいて製造することにより、リバースエンジニアリングを行った物体の複製を製造する、リバースエンジニアリング応用例（ステージ６９０）などの応用例の前段階である。他の応用例は、設計プロセス中にその粘土モデルなど、物体の物理的モデルが設計者によって作成される、設計改良である。物理的粘土モデルのＣＡＤモデルを生成して分析し、その分析の結果を使用して物体の設計を改良する。
【００７６】
スティッチステージ６４０の出力は、米国カリフォルニア州バレンシアの３ＤＳｙｓｔｅｍｓ Ｉｎｃ．が製造したＳＬＡ−１９０モデルなどの適当な高速プロトタイプマシンを使用する高速プロトタイプ手順用の入力として使用することができる。高速プロトタイプは、潜在的な製品のプロトタイプの高速生成や、娯楽産業、観光業界、記念品産業、たとえば、顧客の上半身などの目新しい商品の生成など、幅広い種類の分野で有用である。
【００７７】
ステージ７１４では、ステージ６４０で生成した雲状ポイントに着色する。雲内の各ポイントに割り当てられる色は、注目実際の物体内のそのポイントに対応する位置の元の色である。好ましくは、従来の表面補間は、連続着色表面を生成するためにすべてのポイントについて行われる。適当な表面補間技法については、１９８１〜１９８２年に発行されたＷ．Ｅ．Ｌ．ＧｒｉｍｓｏｎによるＭＩＴＰｒｅｓｓの書籍に記載されている。
【００７８】
結果として得られる着色雲は、たとえば、マルチメディア応用例、教育ソフト、コンピュータ化されたカタログ、コンピュータゲームまたはビデオゲームに挿入するために、リアルな３Ｄグラフィックモデルとして表示することができる。
【００７９】
着色雲は、その自然のテクスチャを使用して表示することができ、あるいは金属的テクスチャなどの人為的効果を発生するように変更することができる。着色雲は、３Ｄアニメーション映画または従来の映画の特殊効果などの娯楽目的のためにアニメーション化する（ステップ７２０）ことができる。ステージ６０４〜６４０のそれぞれについて次に説明する。
【００８０】
ステージ６０４： 経路計画 このステージは、通常、図１の経路計画モジュール８０によって行われる。経路計画モジュール８０は好ましくは、以下の３つの出力を生成する。
【００８１】
出力１： 測定中の物体の一部分に対応する１組の“パッチ”。各パッチは、前記一部分のオーバラップ画像のトリプレットと、そこからロボットが画像トリプレットを生成した位置とを含む。
【００８２】
出力２： 複数のパッチ対のシーケンス。第１のパッチ対を除く各パッチ対内の２つのパッチは、２つの画像トリプレット内の対応する画像のうちの１つ、２つまたは好ましくは３つすべてがオーバラップするという意味でオーバラップする。第１の対のパッチは、左側の宛先パッチと、“スティッチ”操作を使用して同じシーケンス内の残りのパッチにより宛先パッチにスティッチするための右側のソースパッチとを含む。
【００８３】
セット内の各パッチは、少なくとも１つのシーケンス内のソースパッチとして現れなければならない。
【００８４】
出力３： スティッチ操作によって各隣接対のパッチ間の変換がすでに計算されていることを特徴とする、複数のパッチのシーケンス。これによって、一連の変換シーケンスが生成される。このシーケンス内の最後のパッチは、その変換シーケンスの複合変換を計算することにより、そのシーケンスの第１のパッチに変換することができる。
【００８５】
経路計画モジュール８０によって実行される経路計画プロセスは、以下の３つのステップを含む。
【００８６】
ステップ８１０−−出力１のタイリングおよび生成ステップ８２０−−スティッチグラフを作成する ステップ８３０−−スティッチグラフを走査し、経路自体を含む出力１〜３を生成する 上記の各ステップについて次に説明する。
【００８７】
ステップ８１０−−タイリング： 経路計画モジュール８０は好ましくは、測定すべき物体の一部分をいっしょにカバーするオーバラップ画像のシーケンスを作成するために、結像すべき物体のオーバラップ部分を選択するようユーザにプロンプト指示する対話型ソフトウェアモジュールを含む。次にユーザは、作成したすべてのシーケンスがこのプロセスの終わりに接続されるように、自分が作成した隣接シーケンスを接続する。ロボット目視位置およびその実行順序は、出力１を生成するこのステップで定義される。
【００８８】
オーバラップする隣接物体部分の画像対のリストを獲得する方法はいくつか可能である。検査すべき物体のＣＡＤモデル７０が存在する場合、“ＣＡＤモデル使用可能”モードで動作する経路計画モジュール８０は好ましくは、経路をＣＡＤモデルに重ね合わせ、どちらの画像対が隣接しオーバラップする物体部分に関係するかを決定するように動作可能である。いずれのＣＡＤモデル７０も存在しない場合、“ＣＡＤモデル使用不能”モードで動作する経路計画モジュールは好ましくは、物体が結像されたロボット位置を記録し、したがって、どちらの画像対が隣接しオーバラップする物体部分に関係するかを決定することができる。結像が手動で行われる場合、人間のオペレータは好ましくは、どちらの画像対が隣接しオーバラップする物体部分に関係するかに関する手動入力を行えるように動作可能である。
【００８９】
ステップ８２０−−スティッチグラフを作成する： 本明細書で“スティッチグラフ”と呼ばれるグラフを作成するが、そのグラフでは、各ノードが一連の部分オーバラップ画像トリプレットであり、ノードｖにおける少なくとも１つのパッチがノードｕにおける少なくとも１つのパッチに部分的にオーバラップする場合にグラフの１対のノードｖおよびｕが１つの辺によって接続されている。
【００９０】
ステップ８３０−−スティッチグラフを走査し、経路自体を含む出力１〜３を生成する： ステップ８２０で生成したスティッチグラフを系統的に走査して、未処理（すなわち、隣接するものにまだスティッチされていない）画像シーケンスを求める。
【００９１】
好ましくは幅優先検索（ｂｒｅａｄｔｈ−ｆｉｒｓｔ ｓｅａｒｃｈ）などの適当な検索方式を使用することができる。求めた第１の未処理シーケンス内の第１の画像トリプレット（“パッチ”）は“ベース”という。そのシーケンス内のすべてのパッチはベースにスティッチされる。求めた各後続未処理シーケンスは、すでに処理された隣接するもの（すなわち、辺によってそのシーケンスに接続されたノード）にスティッチされる。このプロセスの出力は以下のものを含む。
【００９２】
それぞれがシーケンス内の各パッチとベースとの間のスティッチを記述する、出力２の複数の線と、 出力２の上記のフォーマットを使用する場合に２つのシーケンス間のスティッチを記述する、出力２の単一の線と、 出力３の上記のフォーマットを使用する場合の出力３の単一の線である。この線は、現行シーケンスからベースの座標系への変換の計算を記述するものである。
【００９３】
ステージ６１０： テンソルデータを生成することによる３Ｄ表面構造再構築プロセスの較正 ステージ６１０は、図１６に示すように、以下のステップを含む。
ａ．ステップ７００： スケーリング物体を結像する−−スケーリング物体の２Ｄ画像のトリプレットを生成する。このトリプレットは、スケーリング物体の本質的に同じ部分の３つのビューを含む。スケーリング物体は、テクスチャが付けられ、複数（通常は、少なくとも５つ）の既知のポイントフィーチャを含むことを特徴とする。“既知のポイントフィーチャ”という用語は、コーナーまたは円の中心など、手動または自動のいずれかで容易に識別可能であり、既知の（ｘ，ｙ，ｚ）位置に発生するポイントフィーチャである。好ましいスケーリング物体については図１９〜図２１に示す。
【００９４】
具体的には、図１９は、好ましいスケーリング物体の写真である。図示の通り、図１９は、２通りの高度レベル、すなわち、高レベルと低レベルにある複数の精密に製造した穴を含む。通常、この穴は、高レベル穴と低レベル穴が交互に“チェッカーボード”のフォーマット状に並んでいるグリッドとして配置される。
【００９５】
スケーリング物体の表面は、表面の高度を高レベルから低レベルに低減し、通常は隣接低レベル穴が検出される直前に低レベルに達するように、各高レベル穴の周りに形成された複数のほぼ円錐形の部分を含む。
【００９６】
図２０は、図１９のスケーリング物体の前段階を示す等角投影図であり、それらを接続する表面なしに２通りのレベルの穴のみを示している。図２１は、図２０の線ＸＸＩ−ＸＸＩに沿って示す断面図である。
【００９７】
ｂ．ステップ７１０： ステップ７６０に関連して後述するように、画像トリプレットの第１の画像内の“コーナー”表面ポイントを求める。第１の画像内の各“コーナー”表面ポイントごとに、残りの２つのスケーリング画像内の対応する位置を識別する。スケーリング物体が不連続表面を有する場合、ポイントフィーチャ検出が行われる。あるいは、連続するか否かにかかわらず、スケーリング物体内の対応する位置を手動で識別することもできる。ステップ（ｂ）の出力は、１組の対応する位置のトリプレットであり、通常は少なくとも７つのトリプレットである。対応する位置は必ずしも既知のポイントフィーチャではない。
【００９８】
ｃ．ステップ７２０： ステップ（ｂ）の出力を使用して、テンソルを作成する。対応する位置のトリプレットからテンソルを作成するための好ましい方法については、同時係属の米国特許出願第０８／４９７２２４号に記載されている。
【００９９】
ｄ．ステップ７３０： ステップ（ａ）で生成された３つのビューのそれぞれにおける既知のポイントフィーチャの位置を識別し、それにより、対応する位置の複数のトリプレット、通常は対応する位置の少なくとも５つのトリプレットを生成する。特定の既知のポイントフィーチャの２Ｄ位置からなる各トリプレットをそのポイントフィーチャの既知の３Ｄ位置に関連付ける。
【０１００】
ポイントフィーチャの既知の３Ｄ位置は外部に供給される。ステップ（ｄ）は手動で実行することもできる。
【０１０１】
ステップ（ｄ）の出力は、それぞれ少なくとも５つの既知のポイントフィーチャに関する少なくとも５つの情報ユニットであり、各情報ユニットは、ステップ（ａ）で生成された３つのスケーリングビューのそれぞれにおけるそのポイントフィーチャの３Ｄ位置とそのポイントフィーチャの２Ｄ位置とを含む。
【０１０２】
あるいは、一方がテクスチャ付きであり、もう一方が複数の既知のポイントフィーチャを含む、２つのスケーリング物体を使用することができる。ステップ（ｂ）および（ｃ）は、テクスチャ付きの第１のスケーリング物体について実行される。ステップ（ｄ）は、複数の既知のポイントフィーチャを含む第２のスケーリング物体について実行される。第１のスケーリング物体は、たとえば、注目物体そのものにすることができる。第２のスケーリング物体は、連続表面または不連続表面のいずれかを有する場合がある。カメラのトリプレット間の固定した同じ向きを使用して、２つのスケーリング物体のそれぞれについて２Ｄ画像のトリプレットが生成される。
【０１０３】
ｅ．ステップ７４０： スケーリングデータの一部が通常はステップ（ｃ）で計算したテンソルの識別コードになるので本明細書では“テンソルデータ”ともいうスケーリングデータを生成するために、ステップ（ｄ）の出力とステップ（ｃ）で生成されたテンソルとを使用する。ステップ７４０を実行するための好ましい方法については、同時係属の米国特許出願第０８／４９７２２４号および第０８／７８７３４５号と、米国特許第５５９８５１５号に記載されている。テンソルデータは好ましくは、テンソル自体は別として、投影座標からユークリッド座標への変換、基本マトリックス、エピポールを含む。
【０１０４】
ステージ６２０： 注目物体の結像 ステージ６２０は以下のステップｆを含む。
【０１０５】
ｆ．ステップ７５０： 注目物体の結像−−物体の表面の少なくとも一部分の２Ｄ画像の複数のトリプレットを生成する。各トリプレットは、物体の表面の本質的に同じ一部分の３つのビューを含む。
【０１０６】
複数のトリプレットは通常、注目区域全体をカバーし、隣接トリプレット同士のオーバラップが発生する。たとえば、物体の表面全体が対象になる場合、トリプレットは通常、表面全体をカバーし、オーバラップが発生する。
【０１０７】
ステージ６１０および６２０用に各トリプレットの画像を生成するには、３台のカメラが本質的に同じ区域を結像するように、ベース上に固定して取り付けられた“写真”出力を備えた３台のディジタルカメラなど、相互の向きが一定の従来のカメラの可動トリプレットを使用することができる。１つまたは複数のスケーリング物体を結像し、注目物体を結像するために、相互の向きが同じカメラを使用する。カメラトリプレットの可動性は、物体の一連のオーバラップ部分が結像されるように、ベースとカメラを携帯して物体の周りを移動し、物体を繰り返し結像する人間のオペレータによってもたらされる場合もある。物体に光学的にテクスチャが付けられていない場合、たとえば、物体に手動でスペックルを付けることによって、光学テクスチャが人工的に施される。人間のオペレータは、自分の動きを監視し、どのトリプレットがオーバラップするかを手動で記録する。
【０１０８】
本発明の一実施形態で使用する“写真”ファイルフォーマット出力については後述する。
【０１０９】
あるいは、ステップ（ａ）および（ｂ）用の画像トリプレットは、物体に光学的にテクスチャが付けられていない場合に光学テクスチャ付けサブシステムを含む、本明細書に示し記載する結像装置を使用することによって得られる。
【０１１０】
ステップ（ｆ）では、カメラの固定した相互の向きは、スケーリングステップ（ａ）で使用するカメラの相互の向きと同じである。ステップ（ｆ）で使用する各カメラの焦点距離および口径はステップ（ａ）で使用する同じカメラの焦点距離および口径と同じである。
【０１１１】
あるいは、ステージ６２０およびすべての後続ステージでは、２Ｄ画像のトリプレットは、それぞれが物体の表面の同じ部分の２つのビューのみを含む、２Ｄ画像の対で置き換えることができる。
【０１１２】
ステージ６３０： ローカル３Ｄ表面構造再構築 ローカル再構築−−各画像トリプレットごとに、すなわち、注目物体の特定の部分の３つの画像ごとに、その物体部分の３Ｄ表面構造を再構築する。
【０１１３】
図１７に示すように、ステージ６３０は、各画像トリプレットごとに以下のステップを実行することを含む。
【０１１４】
ｇ．ステップ７６０： 画像トリプレット内の１つの画像における“コーナー”表面ポイントを求める。
【０１１５】
ｈ．ステップ７７０： 画像トリプレット内の残りの２つの画像における対応するポイントを求める。
【０１１６】
ｉ．ステップ７８０： 投影再構築により３Ｄ表面ポイントを計算する。
【０１１７】
ｊ．ステップ７９０： ３Ｄ表面ポイントをユークリッド座標にマッピングする。
【０１１８】
単一の画像トリプレットについて、上記の４つのステップを次に説明する。
【０１１９】
ｇ．ステップ７６０： 画像トリプレット内の１つの画像における“コーナー”表面ポイントを求める−− 本明細書では“良好なポイント”ともいうコーナーポイントは、表面の３つの次元のうちの複数に沿って勾配の変化が発生している表面位置である。
【０１２０】
ステップ７６０“良好なポイントを求める”を実行するための好ましい方法については後述する。
【０１２１】
ｈ．ステップ７７０： 画像トリプレット内の残りの２つの画像における対応するポイントを求める−−このステップを実行するための好ましい方法については以下の“対応の記述”で説明する。この方法は、各画像を平滑化し、デシメートするために使用する錐体を構築することを含む。図１２Ａに示す画像に錐体構築プロセスを適用し、それにより、５レベル錐体を生成した結果のシミュレーションを図１２Ｂ〜図１２Ｆに示すが、これらの図は錐体の第１〜第５レベルを示す図である。
【０１２２】
ステップ（ｉ）および（ｊ）を実行するための好ましい方法については、イスラエル特許出願第１１３４９６号と、同時係属の米国特許出願第０８／４９７２２４号および第０８／７８７３４５号と、米国特許第５５９８５１５号に記載されている。
【０１２３】
ステップ（ｊ）の出力は、ユークリッド座標で表した１組の３Ｄ表面ポイントである。
任意選択で、以下の“測定ノイズを除去するための方法”で説明するように、域外の３Ｄ表面ポイントを取り除くために、上記の方法によって生成された３Ｄ表面ポイントを分析する。
【０１２４】
ステージ６４０： 再構築したローカル３Ｄ表面構造をスティッチし、注目物体のための完全実際表面構造を形成する スティッチプロセスへの入力は、経路計画モジュールからの出力２および３である。図１８に示す１対の部分オーバラップパッチについてスティッチプロセスを実行するための方法については、以下の“２Ｄスティッチ”に詳述する。
【０１２５】
一般に、スティッチプロセスは、以下の２つのステップを含む。
【０１２６】
ステップｊ−−出力２に指定された画像の各対ごとに、その対内の第１および第２の画像トリプレットからそれぞれ再構築した第１の表面部分と第２の表面部分との回転かつ並進３Ｄ変換を計算する。
【０１２７】
ステップｋ−−それぞれの表面部分についてステップ（ｊ）で計算した変換を操作することにより、再構築した表面部分を位置合わせして単一平面を形成する。
【０１２８】
ステップ（ｊ）は好ましくは、各画像トリプレット内に結像した物体の部分同士の近似空間関係を識別する外部入力を頼りにする。この入力は、図１の経路計画モジュール８０によって供給されるかまたはロボット１０の実際の動きに関する情報を含む場合があり、その情報はロボットのエンコーダによって生成され、かつ／あるいはオーバラップする隣接物体部分の画像に発生する特徴を識別することにより地理的関係を識別する人間のオペレータが生成した情報を含む場合もある。あるいは、空間関係に関する外部入力はまったく供給されない。
【０１２９】
ステップｋ−−前述のように、ステップｋは、それぞれの表面部分についてステップ（ｊ）で計算した変換を操作することにより、再構築した表面部分を位置合わせして単一平面を形成することを含む。
【０１３０】
ステージ６５０： 注目物体の実際の表面構造を所望の表面構造と比較する １．実際の表面構造を所望の表面構造に位置合わせする−−このプロセス用の座標変換は好ましくは、その上に注目物体２０（図１）が設置され、物体のＣＡＤモデルに対するその３Ｄ位置が分かっているベース（図示せず）に接続された、少なくとも３つの好ましくは球形の位置合せ物体（図示せず）を結像することによって生成される。位置合せ物体が球形である場合、その位置はその中心の位置によって決定される。この位置合せ物体は、米国特許出願第０８／４９７２２４号に記載されている方法を使用して再構築され、その物体の残りの部分に“スティッチ”される。球形再構築の座標系とＣＡＤモデルの座標系との変換は、Ｇｅｎｅ Ｈ．ＣｏｌｕｂおよびＣｈａｒｌｅｓ Ｆ．Ｖａｎ ＬｏａｎによるＭａｔｒｉｘ Ｃｏｍｐｕｔａｔｉｏｎｓの第２版の５８２ページ（Ｊｏｈｎ Ｈｏｐｋｉｎｓ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ、１９８９年）に記載されている方法などの既知の方法を使用して計算される。この変換は、実際の表面構造と所望の表面構造を位置合わせするように機能する。
【０１３１】
ｍ．実際の表面構造と所望の表面構造との偏差を識別する−−好ましくは、このステップは以下のように実行される。物体の各再構築化ポイントごとに、ＣＡＤモデルにおける最も近いかまたはほぼ最も近いパッチを求め、反復ニュートン−ラフソン手順により、“最も近いポイント”すなわち現行の再構築化ポイントに最も近いかまたはほぼ最も近いパッチ上のポイントを求める。最も近いポイントと再構築化ポイントとの距離を計算する。好ましくは、求めた偏差は、色分け、たとえば、様々な範囲内の距離を表すための様々な色の使用によって表示される。
【０１３２】
ステージ６５０は、ステージ６１０〜６４０の出力用として可能な唯一の応用例であることに留意されたい。あるいは、たとえば、ステージ６１０〜６４０の出力はリバースエンジニアリングに使用することができる。
【０１３３】
また、本発明のソフトウェア構成要素は、望ましい場合、ＲＯＭ（読取り専用メモリ）の形で実現できることに留意されたい。ソフトウェア構成要素は一般に、望ましい場合、従来の技法を使用してハードウェアで実現される。
【０１３４】
図４〜図１４Ｃに関連して、本発明の動作について一般的に説明する。
【０１３５】
図４は、図１のシステムを使用して結像可能な典型的な３次元物体を示している。この場合、３次元物体は自動車のスケールモデルであり、光学ヘッド３０によって一度にその全体が見えるほど十分小さいものである。図５は、本発明の好ましい実施形態によりその表面上に投影されるスペックルを有する、図４の３次元物体を示している。
【０１３６】
本発明のシステムは、図４および図５の３次元物体に対応する雲状ポイントを生成するように動作可能である。この雲状ポイントについては図６に示す。この組上ポイントは、図４および図５の物体の３次元表現である。
【０１３７】
図７は、図１のシステムを使用して結像可能な他の典型的な３次元物体を示している。この３次元物体は、たとえば、車両のバンパーであり、大きすぎて光学ヘッド３０によってその全体を見ることができない。図８は、本発明の好ましい実施形態によりその表面上のテクスチャ上にペイントした図７の３次元物体を示している。このペイント済みテクスチャは、本発明の好ましい実施形態により提供される投影スペックルテクスチャパターンのシミュレーションとして提示される。
【０１３８】
図９は、図７および図８の３次元物体に対応し、図１のシステムによって生成される雲状ポイントを示している。
【０１３９】
本発明の好ましい実施形態によれば、図１のシステムは、図９の雲状ポイントを同じ物体用の対応するＣＡＤファイルと比較するように動作可能である。図７の物体の典型的なＣＡＤモデルは、図１０Ａ（ワイヤフレーム）および図１０Ｂ（立体モデル）に示されており、その物体用のＣＡＤファイルを表している。
【０１４０】
図１１は、図７の物体の３次元表現と図１０Ａ〜図１０ＢのそのＣＡＤモデルとの偏差を示す図である。
【０１４１】
図１２Ａ〜図１２Ｆは、ステップ７７０の対応ポイント検出プロセスの一部を形成する錐体構築プロセスのシミュレーションである。
【０１４２】
図１３Ａおよび図１３Ｂは、図８のテクスチャを有する図７の物体上の隣接区域の２つの部分的にオーバラップする画像である。
【０１４３】
図１４Ａおよび図１４Ｂは、図１２Ａおよび図１２Ｂの画像に対応し、本発明のシステムによって生成される雲状ポイントの一部分である。
【０１４４】
図１４Ｃは、図１２Ａおよび図１２Ｂの画像の“スティッチ済み”表現を表す、２つの結合した雲状ポイントの組合せである。
【０１４５】
明瞭にするために別々の実施形態に関連して説明した本発明の様々な特徴は、単一の実施形態において組み合わせて提供することもできることに留意されたい。これに対して、簡潔にするために単一の実施形態に関連して説明した本発明の様々な特徴は、別々にまたは特定の補助的組合せにおいて提供することもできる。
【０１４６】
対応の記述 問題： ３Ｄ物体の２つの画像の場合、その２つの画像間のピクセル対ピクセルの対応（一致）を求める。
【０１４７】
解法： 粗大から微細へ（階層的に）実現したローカル移動の５×５領域の平方和階差（ＳＳＤ：Ｓｕｍ ｏｆ Ｓｑｕａｒｅｓ Ｄｉｆｆｅｒｅｎｃｅ）の１次テイラー展開に基づく微分法を使用する。ｆ（ｘ，ｙ）およびｇ（ｘ，ｙ）
は２つの画像を示し、ｆx（ｘ，ｙ）およびｆy（ｘ，ｙ）はｘ，ｙにおけるｆの勾配の成分を示すものとする。オーバラップする小さい領域（たとえば、５×
【０１４８】
【数１】
2008145431.tif 000003
【０１４９】
うにｕ，ｖが最適変換である場合、以下の微分方程式 ufx+vfy+(f-g)=０ （１）
【０１５０】
【数２】
2008145431.tif 000004
【０１５１】
ついて最小にすることができ、式中、ｆt＝ｆ−ｇである。式（１）中のｕ，ｖ
【０１５２】
【数３】
2008145431.tif 000005
【０１５３】
のｋ×ｋのウィンドウを使用するすべてのピクセルに適用される(ただし、“ｋ”は好ましくは５に対応するが、他の値を使用することもできる)。すべてのｘ，ｙ位置でｕ，ｖが求められると、すなわち、変位フィールドｕ（ｘ，ｙ）およびｖ（ｘ，ｙ）が得られると、変位フィールドを使用して画像ｆおよびｇを位置合わせし（“ゆがませ”）、プロセスを繰り返す(それにより、ニュートン−ラフソン反復最適化を実行し、ｆとｇとのＳＳＤを最適化するｕ，ｖを求めることになる)。
【０１５４】
パフォーマンスを改善するため、特に大きい画像変位に沿って、粗大から微細へ反復を適用する。これは、各画像をそれぞれが周波数範囲（低周波から高周波へ）を表す一連の画像に分割することによって行うことができる。その場合、ｋ×ｋのウィンドウのサイズは、低周波の場合は増加し、高周波の場合は減少する。同様に、画像を平滑化しデシメートして、反転錐体を作成することができる。
【０１５５】
この錐体の低い方のレベルは高周波成分を表し、高い方のレベル（より小さい画像）は低周波成分を表す。反復は、錐体の最高レベル（画像の最も粗大な表現）から始まり、その詳細レベルにとって最適の変位フィールドを生成する。次に変位レベルを増幅し、錐体内の１レベル下のレベル（より詳細なレベルを表す）に適用し、そのレベルにとって最適の変位フィールドをもう一度生成するために反復を続行する。このプロセスは、錐体の最低レベルに到達するまで続行する。
【０１５６】
遠距離対応（Ｆａｒ−Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ）の記述 問題： ３Ｄ物体の２つの画像の場合、画像空間内のオーバラップの量を求める、すなわち、その２つの画像間のオーバラップ画像情報を位置合わせする水平変換および垂直変換の大きさｕ，ｖを求める。
【０１５７】
解法： ２つの画像の平方和階差（ＳＳＤ）の１次テイラー展開に基づく微分法を使用する。ｆ（ｘ，ｙ）およびｇ（ｘ，ｙ）は２つの画像を示し、ｆx（ｘ，ｙ）およびｆy（ｘ，ｙ）はｘ，ｙにおけるｆの勾配の成分を示すものとする。
【０１５８】
【数４】
2008145431.tif 000006
【０１５９】
うにｕ，ｖが最適変換である場合、以下の微分方程式 ufx+vfy+(f-g)=0 （２）
【０１６０】
【数５】
2008145431.tif 000007
【０１６１】
ついて最小にすることができ、式中、ｆt＝ｆ−ｇである。式（２）中のｕ，ｖ
【０１６２】
【数６】
2008145431.tif 000008
【０１６３】
ることにより、ニュートン−ラフソン反復最適化を実行し、ｆとｇとのＳＳＤを最適化するｕ，ｖを求めることになる。
【０１６４】
良好なポイントを求める 問題： １つの画像の場合、他の画像内の良好な一致を有する可能性のあるポイント、すなわち、そのローカル強度分布が“コーナー”に類似するポイントの位置（ｘ，ｙ位置）を求める。
【０１６５】
解法： そのローカル強度変動が非常に低い（平らな強度プロファイル）かまたはそのローカル変動が直線の形状になっているポイントを消去することが好ましい。ｆ（ｘ，ｙ）はその画像の強度マップを示し、ｆx（ｘ，ｙ）およびｆy（ｘ，ｙ）はｘ，ｙにおけるｆの勾配の成分を示すものとする。成分
【０１６６】
【数７】
2008145431.tif 000009
【０１６７】
２×２のマトリックスＭが定義され、その総和がそのポイント周辺のローカル領域におけるものである場合、そのポイントが“良好なポイント”である場合のみ、マトリックスＭの階数は値２である。階数２の基準は、マトリックスＭの２つの固有値の相対規模を検討することによって実施される。固有値同士の割合が１に近く、小さい方の固有値の値がオペレータによって設定可能な所定のしきい値を上回る場合、そのポイントは“良好”と見なされる。この基準は好ましくはｆのすべてのポイントｘ，ｙについて実施され、その基準を満たすポイントだけが良好なポイントと見なされる。
【０１６８】
２次元ステイッチ 問題： ２組の画像が存在すると想定する。第１の組の画像、すなわち、画像Ａ0、Ａ1、Ａ2はある場面のパッチＡに対応し、第２の組の画像、すなわち、画像Ｂ0、Ｂ1、Ｂ2はある場面のパッチＢに対応する。さらに、パッチＡとＢがその場面で少なくともある程度はオーバラップすると想定する。両方の組の画像が同じカメラ構成で取られた場合、再構築プロセスでこれらの画像に同じ３線テンソルを適用して、その場面内の３Ｄ再構築ポイントを求めることができる（前述のイスラエル特許出願第１１３４９６号および米国特許出願第０８／４９７２２４号(その開示は１９９６年１０月３１日に発行された国際公開ＷＯ９６／３４３６５号に対応する）を参照のこと)。すなわち、｛Ｐi，Ｐ'i，Ｐ''i｝iがそれぞれ第１の組の画像Ａ0、Ａ1、Ａ2内の対応ポイントである場合、しかも、｛ｑj，ｑ'j，ｑ''j｝jがそれぞれ第２の組の画像Ｂ0、Ｂ1、Ｂ2内の対応ポイントである場合、どのような３つ組｛ｐi，ｐ'i，ｐ''i｝iについても同じ３線テンソルを使用して、その場面内の３Ｄ再構築化ポイントＰiを求めることができ、同様にどのような３つ組｛ｑj，ｑ'j，ｑ''j｝jについてもその場面内の３Ｄ再構築化ポイントＱiを求めることができる。その目的は、画像Ａ0、Ａ1、Ａ2、Ｂ0、Ｂ1、Ｂ2を使用して、３Ｄ再構築化ポイント｛Ｐi｝iを３Ｄ再構築化ポイント｛Ｑj｝jに位置合わせすることである。
【０１６９】
解法： 第１のステップは、第１の組の第１の画像Ａ0と第２の組の第１の画像Ｂ0との稠密な対応を決定することである。特に、画像Ａ0内のポイントであって、パッチＡおよびＢの共通部分に現れる任意のポイントｐiの場合、対応対｛ｐi，ｑi｝が得られる。この第１のステップを実行するための好ましい方法は、以下のステップを含む。
【０１７０】
（ａ）前述の“遠距離対応の記述”の方法を使用して優性変換を求める。
【０１７１】
（ｂ）前述の“対応の記述”の方法を使用して残りの変位を求める。
ｑiを求めた後、前述の“対応の記述”の方法を使用して画像Ｂ1およびＢ2内のｑ'iおよびｑ"iを求める。画像Ａ0内のポイントｐiがパッチＡ内のポイントＰiに対応する場合、トリプレット｛ｑi，ｑ'i，ｑ''i｝は同じポイントＰiに対応する。
【０１７２】
その後、３ＤポイントＱiを再構築するために３線テンソルを適用する。ただし、独立した２組の３Ｄポイントが存在した最初の状況とは異なり、現在では、実際には２通りの座標系、すなわち、第１の組の画像Ａ0、Ａ1、Ａ2を記録するために使用したカメラ構成に関連する第１の座標系と、第２の組の画像Ｂ0、Ｂ1、Ｂ2を記録するために使用したカメラ構成に関連する第２の座標系において同じ組の３Ｄポイントを表す２組の３Ｄポイントが存在し、第１の座標系を第２の座標系に関連付けるための変換を求めることが望ましいことに留意されたい。
【０１７３】
【数８】
2008145431.tif 000010
【０１７４】
最小にする回転“Ｒ”と並進（ｔｒａｎｓｌａｔｉｏｎ）“ｔ”を含む変換が生成される。その操作では並進“ｔ”を消去することができる。というのは、回転“Ｒ”を求めた後、適切な並進は単にＱ'−ＲＰ'にすぎず、Ｐ'がポイント｛Ｐi｝iにおける平均であり、Ｑ'がポイント｛Ｑj｝jにおける平均であることは明白であるからである。また、その平均Ｐ'およびＱ'を生成した後、新しいポイントの組｛Ｐi−Ｐ'｝iおよび｛Ｑj−Ｑ'｝jを取り入れた場合、これらの組のそれぞれの中心は原点であり、このため、ある組を他の組にマッピングするための最良変換は単に回転のみを必要とする。組｛Ｐi−Ｐ'｝iと｛Ｑj−Ｑ'｝jとの間の回転Ｒを生成するために既知のアルゴリズムを使用することができ、たとえば、Ｇｅｎｅ Ｈ．ＧｏｌｕｂおよびＣｈａｒｌｅｓ Ｆ．ＶａｎＬｏａｎによる“Ｍａｔｒｉｘ Ｃｏｍｐｕｔａｔｉｏｎｓ”（第２版）（Ｊｏｈｎｓ Ｈｏｐｋｉｎｓ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ、１９８９年）の５８２ページを参照のこと。
【０１７５】
測定ノイズを除去するための方法 問題： ２つの画像間の一致対のリストまたはセットの場合、アウトライアを除去する。
【０１７６】
解法： いくつかの例示的な方法がある。
【０１７７】
１．３Ｄ平滑性の仮定： 一致ポイントを使用し、対応する３Ｄポイントの３Ｄ座標を再構築する。表面形状が平滑であり、曲率が低いと想定した場合、すべてのポイントＰについて、隣接ローカル領域内のポイントの２次表面近似を計算する。ローカル２次パッチからポイントＰまでの距離が所定のしきい値を上回る場合、Ｐはアウトライアである。
【０１７８】
２．光度特性： ２つの画像内でおそらく一致する各対ｐ，ｑについて検討する。対応プロセスを実行することにより、ｐがｑをその一致対と“見なす”場合であって、しかも対応プロセスを逆に実行することにより、ｑもｐをその一致対と“見なす”場合、ｐ，ｑはアウトライアとは見なされない。しかし、対応プロセスを実行することにより、ｐがｑをその一致対と“見なす”が、対応プロセスを逆に実行することにより、ｑはｐをその一致対と“見なさない”場合、ｐ，ｑはアウトライアと見なされる。
【０１７９】
他の方法も使用することができる。
【０１８０】
“写真”ファイルフォーマットの記述 以下のデータ構造は、“Ｃ”プログラミング言語の構文で写真画像ファイルのフォーマットを記述したものである。
【０１８１】
【数９】
2008145431.tif 000011
【０１８２】
/*画像へのポインタは必ず画像の先頭を指し示し、境界線を含 むすべてのブロックを指し示すわけではない。ピクセルマップ 要素img->pixmap_arr[d][i][j]へのアクセス、た
だし、ｄは深さ
【０１８３】
【数１０】
2008145431.tif 000012
【数１１】
2008145431.tif 000013
【０１８４】
本発明によるシステムは、専用ハードウェアまたは汎用コンピュータシステムあるいはその組合せから全部または一部を構築でき、そのどの部分も適当なプログラムによって制御できることに留意されたい。どのようなプログラムも、全部または一部が従来通りにシステムの一部を含むかまたはシステム上に格納することができ、あるいはネットワークまたはその他の従来通りに情報を転送するためのメカニズムにより全部または一部をシステムに供給することができる。さらに、システムは、システムに直接接続可能かまたはネットワークまたはその他の従来通りに情報を転送するためのメカニズムによりシステムに情報を転送できるオペレータ入力要素（図示せず）を使用してオペレータが供給する情報により操作し、かつ／またはその他の方法で制御できることに留意されたい。
【０１８５】
上記の説明は本発明の具体的な実施形態に限定されている。しかし、本発明の利点の一部または全部を達成しながら、本発明の様々な変形および変更が可能であることに留意されたい。本発明の真の精神および範囲に該当する上記その他の変形および変更を含むことが請求の範囲の目的である。
【０１８６】
新規であると請求し、米国特許により保護されることを希望するものは、以下の通りである。
【図面の簡単な説明】
【０１８７】
【図１】は、本発明の好ましい実施形態により構築され、動作可能な３Ｄ表面結像再構築システムの簡略半絵半ブロック図である。
【図２】は、図１のシステムで使用する光学ヘッドの簡略絵図である。
【図３】は、図１のシステムで使用するテクスチャ生成器の一部を形成する照明モジュールの簡略断面図である。
【図４】は、図１のシステムを使用して結像可能な典型的な３次元物体を示す図である。
【図５】は、本発明の好ましい実施形態によりその表面上に投影されるスペックルを有する、図４の３次元物体を示す図である。
【図６】は、図４および図５の３次元物体に対応し、図１のシステムによって生成される雲状ポイントを示す図である。
【図７】は、図１のシステムを使用して結像可能な他の典型的な３次元物体を示す図である。
【図８】は、本発明の好ましい実施形態によりその表面上のテクスチャ上にペイントした図７の３次元物体を示す図である。
【図９】は、図７および図８の３次元物体に対応し、図１のシステムによって生成される雲状ポイント（ａ ｃｌｏｕｄ ｏｆ ｐｏｉｎｔｓ）を示す図である。
【図１０Ａ】は、図７の物体のＣＡＤモデルを示す図である。
【図１０Ｂ】は、図７の物体のＣＡＤモデルを示す図である。
【図１１】は、図７の物体の３次元表現と図１１のそのＣＡＤモデルとの偏差を示す図である。
【図１２Ａ】は、錐体対応方法（ｐｙｒａｍｉｄ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｍｅｔｈｏｄ）のシミュレーションである。
【図１２Ｂ】は、錐体対応方法（ｐｙｒａｍｉｄ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｍｅｔｈｏｄ）のシミュレーションである。
【図１２Ｃ】は、錐体対応方法（ｐｙｒａｍｉｄ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｍｅｔｈｏｄ）のシミュレーションである。
【図１２Ｄ】は、錐体対応方法（ｐｙｒａｍｉｄ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｍｅｔｈｏｄ）のシミュレーションである。
【図１２Ｅ】は、錐体対応方法（ｐｙｒａｍｉｄ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｍｅｔｈｏｄ）のシミュレーションである。
【図１２Ｆ】は、錐体対応方法（ｐｙｒａｍｉｄ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｍｅｔｈｏｄ）のシミュレーションである。
【図１３Ａ】は、図８のテクスチャを有する図７の物体上の隣接区域の２つの部分的にオーバラップする画像を示す図である。
【図１３Ｂ】は、図８のテクスチャを有する図７の物体上の隣接区域の２つの部分的にオーバラップする画像を示す図である。
【図１４Ａ】は、図１２Ａおよび図１２Ｂの画像に対応し、本発明のシステムによって生成される雲状ポイントの一部分を示す図である。
【図１４Ｂ】は、図１２Ａおよび図１２Ｂの画像に対応し、本発明のシステムによって生成される雲状ポイントの一部分を示す図である。
【図１４Ｃ】は、図１２Ａおよび図１２Ｂの画像の“スティッチ済み”表現を表す、２つの結合した雲状ポイントの組合せを示す図である。
【図１５】は、図１のテンソルベースの３Ｄ表面再構築モジュール５０のための好ましい操作方法の簡略流れ図である。
【図１６】は、図１の３Ｄ表面構造再構築モジュールのためにスケーリングを実行するための好ましい方法の簡略流れ図である。
【図１７】は、ローカル再構築のための好ましい方法の簡略流れ図である。
【図１８】は、１対の部分的にオーバラップするパッチを示す図である。
【図１９】は、好ましいスケーリング物体の写真である。
【図２０】は、図１９のスケーリング物体の前段階（ｐｒｅｃｕｒｓｏｒ）を示す等角投影図である。
【図２１】は、図２０の線ＸＸＩ−ＸＸＩに沿って示す断面図である。
【図１】
2008145431.tif 000015
【図２】
2008145431.tif 000016
【図３】
2008145431.tif 000017
【図４】
2008145431.tif 000018
【図５】
2008145431.tif 000019
【図６】
2008145431.tif 000020
【図７】
2008145431.tif 000021
【図８】
2008145431.tif 000022
【図９】
2008145431.tif 000023
【図１０Ａ】
2008145431.tif 000024
【図１０Ｂ】
2008145431.tif 000025
【図１１】
2008145431.tif 000026
【図１２Ａ】
2008145431.tif 000027
【図１２Ｂ】
2008145431.tif 000028
【図１２Ｃ】
2008145431.tif 000029
【図１２Ｄ】
2008145431.tif 000030
【図１２Ｅ】
2008145431.tif 000031
【図１２Ｆ】
2008145431.tif 000032
【図１３Ａ】
2008145431.tif 000033
【図１３Ｂ】
2008145431.tif 000034
【図１４Ａ】
2008145431.tif 000035
【図１４Ｂ】
2008145431.tif 000036
【図１４Ｃ】
2008145431.tif 000037
【図１５】
2008145431.tif 000038
【図１６】
2008145431.tif 000039
【図１７】
2008145431.tif 000040
【図１８】
2008145431.tif 000041
【図１９】
2008145431.tif 000042
【図２０】
2008145431.tif 000043
【図２１】
2008145431.tif 000044