(57)【要約】本発明は、シーン内の１又は複数の被写体の３−Ａ（三次元の）被写体外形の面間推定及び／又は距離の面間推定を行うシステム、装置及び方法に関する。方法は、（ａ）特徴タイプを生じさせる、各特徴タイプが固有の二次元構造により識別可能である所定の明確な特徴タイプの有限セットを準備すること、（ｂ）特徴タイプの多数の外観を含む符号化光パターンを準備すること、（ｃ）軸方向に変化する強度を有する符号化光パターンを、第１の面を生じさせまた第２の面を生じさせる少なくとも２つの面を有するシーン内の１又は複数の被写体に投射すること、（ｄ）被写体に投射された投射符号化光パターンを有する被写体の２−Ｄ（二次元の）画像を捕捉し、これにより、反射された特徴タイプを含む、捕捉された２−Ｄ画像を生じさせること、（ｅ）２−Ｄ捕捉画像の強度値を決定し、決定された強度値を生じさせること、及び（ｆ）決定された強度値に基づいてシーン内の１又は複数の被写体の３−Ｄ被写体外形面間推定及び／又は距離の面間推定を行うことを含む。【選択図】図６
2012504771.tif 000002
【特許請求の範囲】
【請求項１】
シーン内の１若しくは複数の被写体の３−Ｄ（三次元の）被写体外形の面間推定及び／又は距離の面間推定を行う方法であって、
ａ）複数の特徴タイプを生じさせる、所定の明確な特徴タイプの有限のセットを準備することであって、各特徴タイプが固有の二次元構造により識別可能である、所定の明確な特徴タイプの有限のセットを準備すること、
ｂ）前記特徴タイプの多数の外観を含む符号化光パターンを準備すること、
ｃ）軸方向に変化する強度を有する前記符号化光パターンを、第１の面を生じさせまた第２の面を生じさせる少なくとも２つの面を有するシーン内の１又は複数の被写体に投射すること、
ｄ）前記被写体に投射された前記投射符号化光パターンを有する前記被写体の２−Ｄ（二次元の）画像を捕捉し、これにより、反射された前記特徴タイプを含む、捕捉された２−Ｄ画像を生じさせること、
ｅ）前記２−Ｄ捕捉画像の複数の強度値を決定し、前記決定された強度値を生じさせること、及び
ｆ）前記決定された強度値に基づいて前記シーン内の前記１又は複数の被写体の３−Ｄ被写体外形面間推定及び／又は距離の面間推定を行うことを含む、方法。
【請求項２】
さらに前記決定された強度値に基づいて所定のコンピュータによる計算操作を行うことを含む、請求項１に記載の方法。
【請求項３】
前記所定のコンピュータによる計算操作を行うことは、前記強度値を少なくとも１つの所定の参照テーブルに関連付けることを含む、請求項２に記載の方法。
【請求項４】
さらに、２つの最大相関値ＭＡＸ１及びＭＡＸ２とを決定することを含み、前記２つの最大相関値は前記シーンの第１及び第２の面にそれぞれ対応する、請求項３に記載の方法。
【請求項５】
前記決定されたＭＡＸ１及びＭＡＸ２のほかに追加の２つの最大相関値ＭＩＮ１及びＭＩＮ２を決定することを含み、前記２つの最大相関値は前記シーンの第１及び第２の面にそれぞれ対応する、請求項４に記載の方法。
【請求項６】
前記所定のコンピュータによる計算操作を行うことは、前記シーンの第１及び第２の面のピーク率を計算することを含む、請求項２に記載の方法。
【請求項７】
さらに、前記最大相関値ＭＡＸ１を前記最大相関値ＭＡＸ２で割ることにより前記シーンの第１及び第２の面のピーク率を計算することを含む、請求項４及び６に記載の方法。
【請求項８】
前記所定のコンピュータによる操作を行うことは、前記シーンの第１の面における信号対雑音比ＳＮＲ１を計算することを含む、請求項２に記載の方法。
【請求項９】
さらに、前記最大相関値ＭＡＸ１を前記ＭＩＮ１値で割ることにより前記シーンの第１の面における信号対雑音比ＳＮＲ１を計算することを含む、請求項５及び８に記載の方法。
【請求項１０】
前記所定のコンピュータによる計算操作を行うことは、前記シーンの第２の面における信号対雑音比ＳＮＲ２を計算することを含む、請求項２に記載の方法。
【請求項１１】
さらに、前記最大ＭＡＸ２を前記ＭＩＮ１値で割ることにより前記シーンの第２の面における信号対雑音比ＳＮＲ２を計算することを含む、請求項５及び１０に記載の方法。
【請求項１２】
さらに、前記所定のコンピュータによる計算操作に基づいて前記シーン内の１又は複数の被写体の３−Ｄ幾何学的形状を決定することを含む、請求項２に記載の方法。
【請求項１３】
さらに、前記符号化光パターンを以下の
ａ）周期パターン、及び
ｂ）非周期パターン
を１又は複数のパターンとして与えることを含む、請求項１に記載の方法。
【請求項１４】
シーン内の１又は複数の被写体の３−Ｄ（三次元の）被写体外形の面間推定及び／又は距離の面間推定を行うように設定された装置であって、
ａ）特徴タイプの所定のセットであって、特徴タイプを生じさせ、各特徴タイプが固有の二次元構造により識別可能である、特徴タイプの所定のセットと、
ｂ）軸方向に変化する強度を有し、前記特徴タイプの多数の外観を含む、符号化光パターンと、
ｃ）シーン内の１又は複数の被写体に前記符号化パターンを投射するように設定されたプロジェクタであって、前記シーンが少なくとも２つの面を有し、第１の面と第２の面とを生じさせる、プロジェクタと、
ｄ）前記被写体に投射された前記投射符号化光パターンを有する前記被写体の２−Ｄ（二次元の）画像を捕捉するように設定された撮像装置であって、２−Ｄ捕捉画像を生じさせ、前記２−Ｄ画像が反射された前記特徴タイプを含む、撮像装置と、
ｅ）処理装置であって
ｅ.１  前記２−Ｄ捕捉画像の強度値を決定し、前記決定された強度値を生じさせ、また、
ｅ.２  前記決定された強度値を用いることにより前記シーン内の前記１又は複数の被写体の３−Ｄ被写体外形の面間推定及び／又は距離の面間推定を行うように設定された処理装置とを含む、装置。
【請求項１５】
さらに、前記符号化光パターンを前記１又は複数の被写体に向けて投射することができるように設計された回折光学要素を含む、請求項１４に記載の装置。
【請求項１６】
前記回折光学要素はビームスプリッタからなる、請求項１５に記載の装置。
【請求項１７】
前記プロジェクタは、さらに、捕捉される２−Ｄ画像上に対応する強度値を得ることができるように設定された位相マスクを含む、請求項１４に記載の装置。
【請求項１８】
前記位相マスクはビーム成形回折光学要素からなる、請求項１７に記載の装置。
【請求項１９】
前記処理装置は、さらに、前記決定された強度値に基づいて所定のコンピュータによる計算操作を行うように設定されている、請求項１４に記載の装置。
【請求項２０】
前記処理装置は、さらに、前記強度値を少なくとも１つの所定の参照テーブルと相互に関連付けるように設定されている、請求項１４に記載の装置。
【請求項２１】
前記処理装置は、さらに、２つの最大相関値ＭＡＸ１及びＭＡＸ２とを決定するように設定され、前記２つの最大相関値は前記シーンの第１及び第２の面にそれぞれ対応する、請求項１４に記載の装置。
【請求項２２】
前記処理装置は、さらに、前記決定されたＭＡＸ１及びＭＡＸ２のほかに追加の２つの最大相関値ＭＩＮ１及びＭＩＮ２を決定するように設定され、前記２つの最大相関値は前記シーンの第１及び第２の面にそれぞれ対応する、請求項２１に記載の装置。
【請求項２３】
前記処理装置は、さらに、前記シーンの前記第１及び第２の面のピーク率を計算するように設定されている、請求項１４に記載の装置。
【請求項２４】
前記シーンの第１及び第２の面のピーク率は、前記最大相関値ＭＡＸ１を前記最大相関値ＭＡＸ２で割ることにより計算される、請求項２１及び２３に記載の装置。
【請求項２５】
前記処理装置は、さらに、前記シーンの第１の面における信号対雑音比ＳＮＲ１を計算するように設定されている、請求項１４に記載の装置。
【請求項２６】
前記シーンの第１の面における信号対雑音比ＳＮＲ１は、前記最大相関値ＭＡＸ１を前記ＭＩＮ１値で割ることにより計算される、請求項２２及び２５に記載の装置。
【請求項２７】
前記処理装置は、さらに、前記シーンの第２の面における信号対雑音比ＳＮＲ２を計算するように設定されている、請求項１４に記載の装置。
【請求項２８】
さらに、前記シーンの第２の面における信号対雑音比ＳＮＲ２は、前記最大相関値ＭＡＸ２を前記ＭＩＮ１値で割ることにより計算される、請求項２２及び２７に記載の装置。
【請求項２９】
前記処理装置は、さらに、前記所定のコンピュータによる操作に基づいて前記シーン内の１又は複数の被写体の３−Ｄ幾何学的形状を決定するように設定されている、請求項１９に記載の装置。
【請求項３０】
前記符号化光パターンは、以下の
ａ）周期パターン、及び
ｂ）非周期パターン
のうちの１又は複数からなる、請求項１に記載の装置。
【請求項３１】
前記処理装置は前記撮像装置の内部に設けられている、請求項１４に記載の装置。
【請求項３２】
シーン内の１又は複数の被写体の３−Ｄ（三次元の）被写体外形の面間推定及び／又は距離の面間推定を行うように設定されたシステムであって、
ａ）軸方向に変化する強度を有しまた少なくとも２つの面を有するシーン内の１又は複数の被写体に対する複数の特徴タイプを有する、二次元の符号化光パターンを投射するように設定されたパターン投射装置であって、各特徴が前記シーン内の前記被写体の個々の反射位置から反射し、反射された特徴を生じさせ、前記特徴タイプが固有の二次元構造により識別可能である、パターン投射装置と、
ｂ）前記反射された特徴を含む前記シーンの２−Ｄ（二次元の）画像を捕捉するように設定された撮像装置と、
ｂ）前記反射された特徴を含む前記シーンの２−Ｄ（二次元の）画像を捕捉するように設定された撮像装置と、
ｃ）処理装置であって
ｃ.１  前記２−Ｄ捕捉画像の強度値を決定し、前記決定された強度値を生じさせ、また、
ｃ.２  前記決定された強度値を使用することにより前記シーン内の前記１又は複数の被写体の３−Ｄ被写体外形の面間推定及び／又は距離の面間推定を行うように設定された処理装置とを含む、システム。
【請求項３３】
前記パターン投射装置は、さらに、前記シーン内の１又は複数の被写体に前記符号化光パターンを投射するように設定されたプロジェクタを含む、請求項３２に記載のシステム。
【請求項３４】
さらに、前記符号化光パターンを前記１又は複数の被写体に向けて投射することができるように設計された回折光学要素を含む、請求項３２に記載のシステム。
【請求項３５】
前記回折光学要素はビームスプリッタからなる、請求項３４に記載のシステム。
【請求項３６】
前記パターン投射装置は、さらに、捕捉される２−Ｄ画像上に対応する強度値を得ることができるように設定された位相マスクを含む、請求項３２に記載のシステム。
【請求項３７】
前記位相マスクはビーム成形回折光学要素からなる、請求項３６に記載のシステム。
【請求項３８】
前記処理装置は、さらに、前記決定された強度値に基づいて所定のコンピュータによる操作を行うように設定されている、請求項３２に記載のシステム。
【請求項３９】
前記処理装置は、さらに、前記強度値を少なくとも１つの所定の参照テーブルと相互に関連付けるように設定されている、請求項３２に記載のシステム。
【請求項４０】
前記処理装置は、さらに、前記シーンの前記第１及び第２の面のピーク率を計算するように設定されている、請求項３２に記載のシステム。
【請求項４１】
前記処理装置は、さらに、前記シーンの第１の面における信号対雑音比ＳＮＲ１を計算するように設定されている、請求項３２記載のシステム。
【請求項４２】
前記処理装置は、さらに、前記シーンの第２の面における信号対雑音比ＳＮＲ２を計算するように設定されている、請求項３２に記載のシステム。
【請求項４３】
前記処理装置は、さらに、前記所定のコンピュータによる操作に基づいて前記シーン内の１又は複数の被写体の３−Ｄ幾何学的形状を決定するように設定されている、請求項３８に記載のシステム。
【請求項４４】
前記符号化光パターンは、以下の
ａ）周期パターン、及び
ｂ）非周期パターン
のうちの１又は複数からなる、請求項３２に記載のシステム。
【請求項４５】
前記処理装置は前記撮像装置の内部に設けられている、請求項３２に記載のシステム。
【請求項４６】
一連のＳＯＰ（単一光路）又は近似ＳＯＰのパターンを発生させる方法であって、前記方法は所定のパターンを調整しまた少なくとも１つの体積行列を使用することを含み、前記体積行列のそれぞれは１又は複数の所定のルールに従う、方法。
【請求項４７】
さらに、画像処理を用いることにより前記一連のパターンを操作することを含む、請求項４６に記載の方法。
【請求項４８】
さらに、以下の
ａ）反復する複数の行列、及び
ｂ）非反復の複数の行列
の１又は複数として前記体積行列を提供する、請求項４６に記載の方法。
【請求項４９】
一連のＳＯＰ（単一光路）又は近似ＳＯＰのパターンを生じさせるための方法であって、
ａ）複数の符号構造及び対応する符号構造変化を規定すること、
ｂ）前記符号構造のみを含む、局所的一意性行列の１又は複数のセットを生成すること、
ｃ）前記局所的一意性行列のみを含む、行列の少なくとも１つのセットを生成すること、
ｄ）前記符号構造変化に従う、前記一連の行列のみを含む、連続した行列の少なくとも１つのセットを生成することであって、前記連続した行列の少なくとも１つのセットは局所的一意性行列及び平均化局所的一意性行列の双方のいかなる軸方向反復をも含まない、連続した行列の少なくとも１つのセットを生成すること、
ｅ）前記連続した行列のみを含みかつ局所的一意性行列及び平均化局所的一意性行列の双方のいかなる軸方向反復をも含まない、体積行列の少なくとも１つのセットを生成すること、及び
ｆ）所定のパターンを調整しかつ少なくとも１つの前記体積行列を用いることにより一連のパターンを生成することを含む、方法。
【請求項５０】
さらに、画像処理を用いることにより前記一連のパターンを操作することを含む、請求項４９に記載の方法。
【請求項５１】
変換以外の対称性を有する複数の行列を提供することを含む、請求項４９に記載の方法。
【請求項５２】
さらに、前記一連の近似ＳＯＰパターンを得るために、所定方向への前記局所的一意性行列の反復を含み又は前記反復を含まない行列の少なくとも１つのセットを生成することを含む、請求項４９に記載の方法。
【請求項５３】
さらに、前記一連の近似ＳＯＰパターンを得るために、局所的一意性行列及び所定方向への平均化局所的一意性行列の双方の反復を含み又は前記反復を含まない連続した行列の少なくとも１つのセットを生成することを含む、請求項４９に記載の方法。
【請求項５４】
さらに、前記一連の近似ＳＯＰパターンを得るために、局所的一意性行列及び所定方向への平均化局所的一意性行列の双方の反復を含み又は前記反復を含まない体積行列の少なくとも１つのセットを生成することを含む、請求項４９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３−Ｄ（三次元の）及び距離の推定に関する。より詳細には、本発明は、従来のステレオベースラインの要求を除去し、これにより測定距離に拘わらず、比較的小さいパッケージ内に複数の光学要素を提供することを可能にする、ＳＯＰ（単一光路）三次元及び距離の撮像方法、その装置及びシステムに関する。
【背景技術】
【０００２】
定義、頭字語及び略語
本明細書を通して、以下の定義を用いる。
【０００３】
軸方向に変化する強度
１又は複数の軸に沿って変化する強度である。
【０００４】
立体視
これは、２つの眼の網膜に向けられた２つのわずかに異なる投射から奥行き感覚をもたらす視覚上のプロセスである。２つの網膜像の差は、通常、水平視差、網膜視差、又は両眼視差と呼ばれる。この差は、両眼が頭部の異なる位置にあることに起因する。立体視（stereopsis）は、通常、奥行き知覚と称される（立体を意味するstereo及び視覚又は視野を意味するopsisから）。
【０００５】
符号化（構造化）光
これは、複数の画素からなる所定パターンを用いることによりシーン上に投射される光である。前記パターンはこれが前記シーン内の１又は複数の被写体に当たると変形し、次いで、画像システムが、例えば構造化光３−Ｄスキャナを用いることにより、前記被写体の奥行き及び表面の情報を計算することを可能にする。
【０００６】
発明の背景
市販の距離撮像システムのほとんどは、一般的に、２つのメイングループすなわちａ）三角測量システムと、ｂ）ＴＯＦ（飛行時間）システムとに関連している。その他の一般的でない従来のシステム及び方法は、陰影付けから外形の技術（記事“Shape from shading: a method for obtaining the shape of a smooth
opaque object from one view” by B.K.P Horn,
Technical Report 79, Project MAC, Massachusetts Institute of Technology (MIT),
1970に示されている）、焦点ぼけから外形の技術（記事“A simple, real-time
range camera” by A. Pentland et. al, Proceedings of IEEE
Computer Society Conference on Computer Vision and Pattern Recognition (CVPR),
1989に示されている）、フォトメトリック技術（記事“Photometric method for
determining surface orientation from multiple images” by R.J. Woodham, Optical Engineering, Volume 19, No. 1, Pages
139-144, January-February 1980に示されている）、モアレ干渉測定技術（記事“Moire topography” by H. Takasaki,
Applied Optics, Volume 9, Issue 6, Pages 1467-1472, 1970に示されている）及びその他を含む。
【０００７】
前記従来の技術によれば、前記三角測量グループに基づくシステムは、本質的に、光の基本的性質‐その直進性に基づく。この幾何学的属性は、人間の両眼の奥行き知覚（立体視）に基づくものである、右左の眼で見えたものの間に相違を構成する。同様に、前記三角測量グループは２つの主要なサブグループである受動型三角測量と能動型三角測量とからなる。
【０００８】
さまざまな生物学的システムに触発された前記受動型三角測量法（パッシブステレオ法としても知られている）は恐らく最も古い距離撮像方法であり、奥行きデータは異なる角度から得られた２以上の画像間の対応を一致させることを通して抽出される。５０年近いこの分野での研究（“Towards the automation of binocular depth perception (AUTOMAP-1)”, Proceedings of IFIPS Congress, Munich, Pages 439-444, 1962と題する記事においてビー  ジュールズ（B. Julesz）により教示されているような）にも拘わらず、従来の受動型三角測量法は、特徴のない領域、パターン及び構造を繰り返す領域、また表面境界についてもこれらを再現するのに重大な無力に苦しんでいる。これらの欠点にも拘らず、受動型三角測量法は、例えば高空の空中写真からの３−Ｄ立体表現のような、きめが細かくかつ比較的連続する領域を再現することを目的とするいくつかの課題を未だに訴えている（例えばエル  エイチ  カム等（L. H. Quam et. al.）による記事“Stanford
automatic photogrammetry research”, Technical
Report STAN-CS-74-472, Department of Computer Science, Stanford University,
December 1974に示されている）。
【０００９】
受動型三角測量システムとは対照的に、能動型三角測量システムがその高い信頼性のためにこの分野において良く知られている。このシステムでは、「悪名高い」対応問題（例えばウエブページhttp://en.wikipedia.org/wiki/Correspondence_problemに記載されているような）が、構造化光を得られたシーン上に投影する、追加の専用能動型証明光源の使用のために完全に回避されている。構造化光は、前記シーンから反射して戻りカメラにより捕捉される前記構造化光の各局所的領域に明確な同一性を与えることを目的とする指定レイアウトを有する。前記対応は所定のフォーマットに従って生じるため、２つのカメラは必要でなく、通常、たった１つのカメラとたった１つのプロジェクタとを所要の三角測量を行うために用いることができる。この能動型三角測量システムは信頼できまた比較的単純なデザインを有することに加えて、奥行き測定において比較的高い精度を有する。
【００１０】
しかし、受動型三角測量システムと異なり、大部分の能動型三角測量システムは、通常、静的環境（被写体）の距離撮像に限定される。
これは、それらが実際に一時的な構造化光フォーマットを利用するため、同期された一連の投射及び画像捕捉の使用を意味し、角度が制御されるように撮像環境を走査する「古典的」光縞（Y. Shirai 等により“Recognition of
polyhedrons with a range finder”, 2nd International
Joint Conference on Artificial Intelligence (IJCAI), Pages 80-87, London, 1971と題する記事に示されている）で始まり、例えばさまざまな符号化光パターン（米国特許第４，１７４，８６２号に開示されているような）に迅速に変換するためにビデオプロジェクタを利用するより進化したシステムで終わる。
【００１１】
加えて、従来の能動型三角測量システムでは、得られたシーンが走査プロセス又はパターン切替が完了するまで静的に維持されなければならないということに留意すべきである。
【００１２】
他方、単一の符号化光パターンのみが用いられる場合には、動作中のシーンを得ることもできる。このコンセプトは、能動型三角測量の取り組みの初期からの研究テーマであった（P.M. Will等により“Grid coding: A
preprocessing technique for robot and machine vision”, Computers and Artificial Intelligence, pages 66-70, 1971と題する記事に示されている）。このようなタイプの法典化方法を発展させる主要な挑戦は、通常、単一パターンの小さい局所的領域内に非常に多数の識別符号語を埋め込むことを含んでいる（“Pattern codification strategies in structured light systems” by J. Salvi, Pattern Recognition, Volume 37, Issue 4, Pages
827-849, April 2004と題する記事に示されている）。従来技術の取り組みのほとんどは、着色縞（K.
L. Boyerにより“Color-encoded structured light for rapid
active ranging”, IEEE Transactions on Pattern Analysis and
Machine Intelligence (PAMI), Volume 9, Issue 1, Pages 14-28, January 1987と題する記事に示されている）、又は着色点（R. A. Moranoにより“Structured light using
pseudorandom codes”, IEEE Transactions on
Pattern Analysis and Machine Intelligence (PAMI), Volume 20, Issue 3, Pages
322-327, March 1998と題する記事に示されている）の符号化を含んでいる。これらの取り組みは、比較的低い周囲光条件下で中間色の被写体を捕捉するには、大抵の場合適当である。その他の従来の取り組みは、色に代わるものとしてさまざまな形や空間的特徴を用いることを示唆する（P. Vuylsteke等により“Range image acquisition
with a single binary-encoded light pattern”, IEEE Transactions on Pattern Analysis and Machine Intelligence
(PAMI), Volume 12, Issue 2, Pages 148-163, 1990と題する記事に示されている）。
【００１３】
従来の技術によれば、能動型三角測量システムでは、ステレオベースラインとして知られている、所定距離だけ、カメラとプロジェクタとを離して設置することが求められる。通常、前記ベースラインの大きさは、標的とされるシーンまでの距離の約１０％ないし５０％に設定される。一般に、短いベースラインは低精度レベルの結果となり、他方、長いベースラインは前記システムに面しない表面を捉えるのに困難な結果となる。このカメラ／プロジェクタの分離要求は、通常、前記従来の能動型三角測量システムの明らかな欠点の大部分の原因をなし、それらは、一般的には、次のようなものである。
良く知られた「立体的閉塞問題」
表面は、これがカメラ及びプロジェクタの双方で明瞭な視線を維持する場合にのみ再現される。この条件は、例えば深い凹面を扱うときにはこれを満たすことができない。
短い距離に対する適用可能性のみ
前記ベースラインは測定距離に比例して設定されるため、長い距離は非実用的なベースライン長さを必要とする。例えば、１００メートル離れた被写体を高い精度で測定するには、少なくとも１０メートルの長さのベースライン長さを必要とする。前記三角測量はカメラとプロジェクタとが比較的精度良くこれらの相対位置に維持されることを必要とするため、これは、通常、大きくて頑丈な設計と、また恐らくは振動及び温度の双方の変化から隔離された、制御された環境を必要とするであろう。
【００１４】
長い距離の距離撮像のための一般的な選択は、ＴＯＦ（飛行時間）である。能動型三角測量システムと異なり、従来のＴＯＦシステムは光の他の基本的性質‐一定速度でのその進行に基づいている。前記したＴＯＦグループに基づくシステムは、実際には、高速タイミング電気回路を用いて、高速光パルスがターゲットとされるシーンから戻るのに要する時間を測る、光学レーダとして働く。ほとんどのＴＯＦシステムは、点ごとに走査することにより作動し、したがって静的シーンにのみ適する。このような３−Ｄスキャナは、地上ＬＩＤＡＲ（光検出及び測距）システムからなる。しかし、いくつかのＴＯＦシステム、例えば従来のフラッシュＬＩＤＡＲシステム（R. Lange 等により“Time-of-flight range
imaging with a custom solid-state image sensor”, Laser Metrology and Inspection, Proceedings of the SPIE, Volume
3823, Pages 180-191, Munich, September 1999と題する記事に示されている）は、多数の点を同時に捕捉する能力を有し、またこれらを運動距離撮像に適したものにする。さらに、ＴＯＦ技術は、他の重要な特徴により、能動型三角測量の取り組みと異なり、ベースラインを必要としない。このため、従来のプリズムを用いることにより、ＳＯＰ（単一光路）構造内にカメラ及びパルス光エミッタの双方を配置することができる。撮像及び光放射の双方は同一の光路を移動して運ばれるため、「立体閉塞」が起こることはなく、また前記システムは物理的寸法に拘わらず長い距離で動作することができる。実施上、カメラと光エミッタとが互いに近接して配置された、ＳＯＰ構造に近い「近似」ＳＯＰ構造がしばしば実施に供される。それは、最大でもほんの取るに足らない「立体閉塞」を導入はするが、前記システムを簡単にするからである。
【００１５】
しかし、ＴＯＦ技術は遠いシーンの距離撮像及び凹面の双方に対する問題を解決する一方で、ＴＯＦシステムは通常複雑であり、このために能動型三角測量システムより費用がかかる。さらに、最先端の運動可能な距離撮像ＴＯＦ技術は、通常、距離測定精度の観点及び方位分解能の観点の双方において能動型三角測量システムに劣ると考えられている。
【００１６】
同様にステレオベースラインを必要としない、他の従来技術であるＳＯＰ（単一光路）距離撮像方法が、Ｄ．Ｓａｚｂｏｎ等により「“Qualitative real-time range extraction for preplanned scene
partitioning using laser beam coding”, Pattern
Recognition Letters, Volume 26, Issue 11, Pages 1772-1781, August 2005.」と題する記事に発表されている。この方法は、ビーム成形光学要素により発生された多様な軸方向変化の照明パターンの投射に基づく。最初の実験的設計では、各パターンが特定の角度に向けられたスリットの配列で構成されていた。したがって、ある表面までの距離は反射スリットの方向により示され、プロジェクタに結合されたカメラにより捕捉された。従来のＴＯＦシステムと同様、このシステムはＳＯＰ構造内に配置することができ、そこでは前記プロジェクタと捕捉カメラとが同一の光軸を共有（又はほぼ共有）し、また、距離測定精度はこれらの間隔によらない。ＴＯＦシステムと同様ではないが、それは、動く部分（例えば走査ミラー）、高速タイミング電気回路及び非常に高感度のフォームファクタ・ピクセル・アーキテクチャを必要としない（したがって、通常の低コストの高解像度カメラセンサの使用を可能にする）ため、簡単な設計からの恩恵を受ける。また、単一パターンの能動型三角測量法と同様、この距離撮像方法は、これが完全な距離画像を得るために単一のカメラのスナップ写真のみを必要とするだけであるため、動的シーンの運動距離撮像を可能とする。しかし、Ｄ．Ｓａｚｂｏｎ等により提案された前記距離撮像方法では、測定精度及び捕捉距離が、前記要素が発生可能である個々のパターンの数に依存する。前記要素の設計は、従来の反復数値法（Ｕ．Ｌｅｖｙ等により"Iterative algorithm for determining optimal beam profiles in a
three-dimensional space", Applied Optics, Volume 38, Issue 32, Pages
6732-6736, 1999と題する記事に示され、またこの記事はさらにＷ．Ｇｅｒｃｈｂｅｒｇ等による"A
practical algorithm for the determination of phase from image and diffraction
plane pictures", Optics, Volume 35, Pages 237-246. 1972と題する記事に基づく）を用いることによりなされる。前記反復数値法によれば、所望の光強度分布（すなわち複数のパターン）のセットが、さまざまな軸方向距離に配置された多数の個々の面のために与えられる。しかし、異なる面（３−Ｄ及び距離の推定のための測定精度を制限する）で生じた強度画像間に非線形の推移が存在し、これは、また、測定された作業空間がわずかな個々の距離セグメントのセットにより分割されることを意味する。この特性は、ロボットによる運航指示や障害物探知のような適用においては問題でなく、そこでは時空的にまばらな距離測定に十分である。例えば、前記ロボットが所定距離のセットを区別することができるであろうことには十分である。しかし、コンテンツの制作、製造における製品の品質管理、医用撮像等のための３Ｄ立体感表現のような適用においては、通常、より高い測定密度が求められる。
【発明の概要】
【発明が解決しようとする課題】
【００１７】
したがって、この分野には、比較的精度の高いＳＯＰ３次元及び距離の撮像方法並びにそのシステムを提供する継続した要求があり、それはステレオベースラインについての従来の必要性をなくし、また良く知られた「立体閉塞問題」を実質的に回避する一方で、測定距離に拘わらず、比較的小さいパッケージ内への光学要素の収容を可能にする。
【００１８】
また、この分野には、３−Ｄ被写体の外形及び距離の面間推定のための方法並びにシステムを提供する継続した要求がある。
【００１９】
加えて、この分野には、比較的安価であり、また比較的低い感度と比較的高い解像度とを有する撮像装置センサを使うことができる３−Ｄ及び距離の推定のための方法並びにシステムを提供する必要性がある。
【課題を解決するための手段】
【００２０】
発明の概要
本発明はＳＯＰ三次元及び距離撮像方法、その装置及びそのシステムに関し、ステレオベースラインに対する従来の必要性をなくし、これにより、測定距離に拘わらず、比較的小さいパッケージ内に光学要素を提供することを可能にする
【００２１】
シーン内の１若しくは複数の被写体の３−Ｄ（三次元の）被写体外形の面間推定及び／又は距離の面間推定を行う方法は、
ａ）複数の特徴タイプを生じさせる、所定の明確な特徴タイプの有限のセットを準備することであって、各特徴タイプが固有の二次元構造により識別可能である、所定の明確な特徴タイプの有限セットを準備すること、
ｂ）前記特徴タイプの多数の外観を含む符号化光パターンを準備すること、
ｃ）軸方向に変化する強度を有する前記符号化光パターンを、第１の面を生じさせまた第２の面を生じさせる少なくとも２つの面を有するシーン内の１又は複数の被写体に投射すること、
ｄ）前記被写体に投射された前記投射符号化光パターンを有する前記被写体の２−Ｄ（二次元の）画像を捕捉し、これにより、反射された前記特徴タイプを含む、捕捉された２−Ｄ画像を生じさせること、
ｅ）前記２−Ｄ捕捉画像の複数の強度値を決定し、前記決定された強度値を生じさせること、及び
ｆ）前記決定された強度値に基づいて前記シーン内の前記１又は複数の被写体の３−Ｄ被写体外形の面間推定及び／又は距離の面間推定を行うことを含む。
【００２２】
本発明の一実施形態によれば、前記方法はさらに前記決定された強度値に基づいて所定のコンピュータによる計算操作を行うことを含む。
【００２３】
本発明の他の実施形態によれば、前記所定のコンピュータによる計算操作を行うことは、前記強度値を少なくとも１つの所定の参照テーブルと関連付けることを含む。
【００２４】
本発明のさらに他の実施形態によれば、前記方法は、さらに、２つの最大相関値ＭＡＸ１及びＭＡＸ２とを決定することを含み、前記最大相関値が前記シーンの第１及び第２の面にそれぞれ対応する。
【００２５】
本発明のさらに他の実施形態によれば、前記方法は、前記決定されたＭＡＸ１及びＭＡＸ２のほかに追加の２つの最大相関値ＭＩＮ１及びＭＩＮ２を決定することを含み、前記２つの最大相関値は前記シーンの第１及び第２の面にそれぞれ対応する。
【００２６】
本発明のさらに他の実施形態によれば、前記所定のコンピュータによる計算操作を行うことは、前記シーンの第１及び第２の面のピーク率を計算することを含む。
【００２７】
本発明のさらに他の実施形態によれば、前記方法は、さらに、最大相関値ＭＡＸ１を最大相関値ＭＡＸ２で割ることにより前記シーンの第１及び第２の面のピーク率を計算することを含む。
【００２８】
本発明の他の実施形態によれば、前記所定のコンピュータによる計算操作を行うことは、前記シーンの第１の面における信号対雑音比ＳＮＲ１を計算することを含む。
【００２９】
本発明のさらに他の実施形態によれば、前記方法は、さらに、最大相関値ＭＡＸ１をＭＩＮ１値で割ることにより前記シーンの第１の面における信号対雑音比ＳＮＲ１を計算することを含む。
【００３０】
本発明のさらに他の実施形態によれば、前記所定のコンピュータによる計算操作を行うことは、前記シーンの第２の面における信号対雑音比ＳＮＲ２を計算することを含む。
【００３１】
本発明のさらに他の実施形態によれば、前記方法は、さらに、最大相関値ＭＡＸ２をＭＩＮ１値で割ることにより前記シーンの第２の面における信号対雑音比ＳＮＲ２を計算することを含む。
【００３２】
本発明のさらに他の実施形態によれば、前記方法は、さらに、前記所定の計算操作に基づいて前記シーン内の１又は複数の被写体の３−Ｄ幾何学的形状を決定することを含む。
【００３３】
本発明のさらに他の実施形態によれば、前記方法は、さらに、前記符号化光パターンを以下の１又は複数のパターンとして与えることを含む。
ａ）周期パターン、及び
ｂ）非周期パターン
【００３４】
装置がシーン内の１又は複数の被写体の３−Ｄ（三次元の）被写体外形の面間推定及び／又は距離の面間推定を行うように設定されており、前記装置は、
ａ）特徴タイプの所定のセットであって、特徴タイプを生じさせ、各特徴タイプが固有の二次元構造により識別可能である、特徴タイプの所定のセットと、
ｂ）軸方向に変化する強度を有し、前記特徴タイプの多数の外観を含む、符号化光パターンと、
ｃ）シーン内の１又は複数の被写体に前記符号化パターンを投射するように設定されたプロジェクタであって、前記シーンが少なくとも２つの面を有し、第１の面と第２の面とを生じさせる、プロジェクタと、
ｄ）前記被写体に投射された前記投射符号化光パターンを有する前記被写体の２−Ｄ（二次元の）画像を捕捉するように設定された撮像装置であって、２−Ｄ捕捉画像を生じさせ、前記２−Ｄ画像が反射された前記特徴タイプを含む、撮像装置と、
ｅ）処理装置であって
ｅ.１  前記２−Ｄ捕捉画像の強度値を決定し、前記決定された強度値を生じさせ、また、
ｅ.２  前記決定された強度値を用いることにより前記シーン内の前記１又は複数の被写体の３−Ｄ被写体外形の面間推定及び／又は距離の面間推定を行うように設定された処理装置とを含む。
【００３５】
本発明の一実施形態によれば、前記装置は、さらに、前記符号化光パターンを前記１又は複数の被写体に向けて投射することができるように設計された回折光学要素を含む。
【００３６】
本発明の他の実施形態によれば、前記回折光学要素はビームスプリッタからなる。
【００３７】
本発明のさらに他の実施形態によれば、前記プロジェクタは、さらに、捕捉される２−Ｄ画像上に対応する強度値を得ることができるように設定された位相マスクを含む。
【００３８】
本発明のさらに他の実施形態によれば、前記位相マスクはビーム成形回折光学要素からなる。
【００３９】
本発明の他の実施形態によれば、前記処理装置は、さらに、前記決定された強度値に基づいて所定のコンピュータによる計算操作を行うように設定されている。
【００４０】
本発明のさらに他の実施形態によれば、前記処理装置は前記撮像装置内に設けられている。
【００４１】
シーン内の１又は複数の被写体の３−Ｄ（三次元の）被写体外形の面間推定及び／又は距離の面間推定を行うように設定されたシステムであって、
ａ）軸方向に変化する強度を有しまた少なくとも２つの面を有するシーン内の１又は複数の被写体に対する複数の特徴タイプを有する、二次元の符号化光パターンを投射するように設定されたパターン投射装置であって、各特徴が前記シーン内の前記被写体の個々の反射位置から反射し、反射された特徴を生じさせ、前記特徴タイプが固有の二次元構造により識別可能である、パターン投射装置と、
ｂ）前記反射された特徴を含む前記シーンの２−Ｄ（二次元の）画像を捕捉するように設定された撮像装置と、
ｃ）処理装置であって
ｃ.１  前記２−Ｄ捕捉画像の強度値を決定し、前記決定された強度値を生じさせ、また、
ｃ.２  前記決定された強度値を使用することにより前記シーン内の前記１又は複数の被写体の３−Ｄ被写体外形面間推定及び／又は距離の面間推定を行うように設定された処理装置とを含む。
【００４２】
本発明の一実施形態によれば、前記パターン投射装置は、さらに、前記シーン内の１又は複数の被写体に前記符号化光パターンを投射するように設定されたプロジェクタを含む。
【００４３】
一連のＳＯＰ（単一光路）又は近似ＳＯＰのパターンを発生させる方法であって、前記方法は所定のパターンを調整しまた少なくとも１つの体積行列を使用することを含み、前記体積行列のそれぞれは１又は複数の所定のルールに従う。
【００４４】
本発明の一実施形態によれば、前記方法は、さらに、画像処理を用いることにより前記一連のパターンを操作することを含む。
【００４５】
本発明の実施形態によれば、前記方法は、さらに、以下の１又は複数の行列として前記体積行列を提供する。
ａ）反復する複数の行列、及び
ｂ）非反復の複数の行列
【００４６】
一連のＳＯＰ（単一光路）又は近似ＳＯＰのパターンを生じさせるための方法であって、
ａ）複数の符号構造及び対応する符号構造変化を規定すること、
ｂ）前記符号構造のみを含む、局所的一意性行列の１又は複数のセットを生成すること、
ｃ）前記局所的一意性行列のみを含む、行列の少なくとも１つのセットを生成すること、
ｄ）前記符号構造変化に従う、前記一連の行列のみを含む、連続した行列の少なくとも１つのセットを生成することであって、前記連続した行列の少なくとも１つのセットは局所的一意性行列及び平均化局所的一意性行列の双方のいかなる軸方向反復をも含まない、連続した行列の少なくとも１つのセットを生成すること、
ｅ）前記連続した行列のみを含みかつ局所的一意性行列及び平均化局所的一意性行列の双方のいかなる軸方向反復をも含まない、体積行列の少なくとも１つのセットを生成すること、及び
ｆ）所定のパターンを調整しまた少なくとも１つの前記体積行列を用いることにより一連のパターンを生成することを含む。
【００４７】
本発明の一実施形態によれば、前記方法は、さらに、変換以外の対称性を有する複数の行列を提供することを含む。
【００４８】
本発明の他の実施形態によれば、前記方法は、さらに、前記一連の近似ＳＯＰパターンを得るために、所定方向への前記局所的一意性行列の反復を含み又は前記反復を含まない行列の少なくとも１つのセットを生成することを含む。
【００４９】
本発明のさらに他の実施形態によれば、前記方法は、さらに、前記一連の近似ＳＯＰパターンを得るために、所定方向への前記局所的一意性行列及び平均化局所的一意性行列の双方の反復を含み又は前記反復を含まない連続した行列の少なくとも１つのセットを生成することを含む。
【００５０】
本発明の他の実施形態によれば、前記方法は、さらに、前記一連の近似ＳＯＰパターンを得るために、所定方向への前記局所的一意性行列及び平均化局所的一意性行列の双方の反復を含み又は前記反復を含まない体積行列の少なくとも１つのセットを生成することを含む。
【００５１】
本発明を理解し、また本発明がどのように実施されるかを見るため、非制限的な例のみにより、添付図面を参照して、さまざまな実施形態がここに記載されている。
【図面の簡単な説明】
【００５２】
【図１】本発明の一実施形態に従う、３−Ｄ被写体外形及び距離の推定システムの概略図である。
【図２】本発明の一実施形態に従う、投射された、構造化（符号化）光が、シーン内の１又は複数の被写体に向けて進行する間に通過する、複数の仮想面の概略図である。
【図３Ａ】本発明の一実施形態に従う、シーンの第１及び第２の面におけるサンプル光強度分布画像である。
【図３Ｂ】本発明の一実施形態に従う、シーンの第１及び第２の面におけるサンプル光強度分布画像である。
【図４Ａ】本発明の一実施形態に従う、計算され、さらに被写体の軸方向位置に関する決定を行うために使用される補間パラメータの概略的なグラフである。
【図４Ｂ】本発明の一実施形態に従う、計算され、さらに被写体の軸方向位置に関する決定を行うために使用される補間パラメータの概略的なグラフである。
【図４Ｃ】本発明の一実施形態に従う、計算され、さらに被写体の軸方向位置に関する決定を行うために使用される補間パラメータの概略的なグラフである。
【図５Ａ】本発明の他の実施例に従う、図１のシステムに比べてエネルギ的に効率的である３−Ｄ被写体外形及び距離の推定システムの概略図である。
【図５Ｂ】本発明のさらに他の実施形態に従う、３−Ｄ被写体外形及び距離の推定システムの他の概略図である。
【図６】本発明の一実施形態に従う、３−Ｄ被写体外形及び距離推定の概略的なフローチャートである。
【図７】本発明の一実施形態に従う、１２個の明確な２値パターンのサンプルセットの概略図である。各パターンは、（最大の点、最小の点、鞍点、コーナー、エッジ（例えば、ダブルエッジ）等のような識別可能な特徴タイプの有限セットの所定の配列を含む所定の二次元パターンであり、異なる横座標において所定のブロックを繰り返す。
【図８Ａ】本発明の一実施形態に従う、ＳＯＰ（単一光路）パターン生成の概略的なフローチャートである。
【図８Ｂ】本発明の他の一実施形態に従う、近似ＳＯＰパターン生成の概略的なフローチャートである。
【図９Ａ−９Ｄ】本発明の一実施形態に従う、サンプルパターンの概略図である。
【図１０Ａ−１０Ｄ】本発明の他の実施形態に従う、追加のサンプルパターンの概略図である。
【発明を実施するための形態】
【００５３】
当然のことながら、図の簡潔性及び明瞭性のために、図に示す要素は拡大縮小をするためには必ずしも描かれていない。例えば、いくつかの要素の寸法は、明瞭性のために、他の要素と比較して誇張されている。さらに、適当と考えられるところでは、参照符号は対応する又は類似の要素を示すために図間において繰り返されている。
【００５４】
特に述べることがない限り、以下の議論から明らかなように、本明細書を通して「処理」、「コンピュータによる計算」、「計算」、「決定」等のような用語を用いて行う議論は、データを他のデータへと操作し及び／又は変換するコンピュータの動作及び／又は作業に言及するものであり、前記データは物理的な、例えば電子的な量を表わす。用語「コンピュータ」は、パーソナルコンピュータ、サーバ、コンピュータシステム、通信装置、プロセッサ（例えばデジタル信号プロセッサ（ＤＳＰ）、マイクロコンピュータ、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ等）及び他の電子計算装置を含む非制限的な例を通して、データ処理能力を有する任意の種類の電子装置をカバーするように広範囲に解釈されるべきである。また、本明細書の教示に従う操作は、コンピュータ読み取り可能の記憶媒体に記憶されたコンピュータ・プログラムにより所望の目的向けに特別に構成されたコンピュータ又は所望の目的向けに特別に構成された汎用コンピュータを使って行われる。
【００５５】
図１は、本発明の一実施形態に従う、３−Ｄ被写体外形及び距離の面間推定システム／装置１０５の概略図である。システム１０５はパターンを投射するモジュール（装置）１２５を含み、また、モジュール１２５は、、強度が変化する光ビームの空間構造形態で識別可能な特徴タイプの有限セットの所定配列を含む構造化光パターンを生じさせる、複数の画素からなる所定の二次元パターンに対応する、軸方向に変化する強度を有する、構造化（符号化）光を投射するためのプロジェクタ１１５と、被写体１３０（３−Ｄ被写体のような）に向けて前記構造化光を投射することを可能にするためのビームスプリッタ１１０のような光学要素と、３−Ｄ被写体１３０から反射された複数のパターンを含む（二次元の）画像を捕捉するための撮像装置（ＣＣＤ（電荷結合素子）若しくはＣＭＯＳ（相補型金属酸化膜半導体）デジタル・ビデオ・カメラ、又は他の任意の光検出器要素の配列を一例とすることできるカメラ１２０のような）とを含む。プロジェクタ１１５は、さらに、ビーム成形回折光学素子であり、また例えば、前記所定の二次元パターンに従って、対応する強度分布（図３Ａ及び図３Ｂに示すように）を得ることを可能にするためのプロジェクタ１１５レーザ（図示せず）に取り付けられた、所定の位相マスク２０５を含むことに留意すべきである。
【００５６】
加えて、本発明の一実施形態によれば、システム１０５及び被写体１３０の双方が同一の光軸の周りに整列されていることに留意すべきである。本発明のこの実施形態によれば、両光路（被写体１３０に向かう及びカメラ１２０に戻る）の組み合わせは、エネルギの約７５％（前記投射された光の約５０％が被写体１３０に到達し、また、反射された光の約５０％がカメラ１２０に到達する）を消費することにより得られる。
【００５７】
本発明の一実施形態によれば、システム１０５は、軸方向に変化し又は変化しない複数のパターンの軸上投射により３−Ｄ（三次元の）推定と距離の推定とを決定することができる。プロジェクタ１１５は、３−Ｄ被写体１３０から得られた反射を撮像し、また反射された対応する識別可能な特徴タイプの有限セットを含む反射された複数のパターンを前記所定の軸方向に変化する分布と比較することにより３−Ｄトポグラフィと被写体３０までの距離とを推定するカメラと共に、軸上に整列されている。
【００５８】
本発明の他の実施形態によれば、軸方向に変化する複数のパターンは、光学要素２０５の数値的反復設計に制約として挿入される、有限数の軸方向面と共に異なる強度の分布を成形することができるビーム形成回折光学要素２０５を設計することにより実現される。例えば、この成形は、比較的多様性のある非制約で生成された位相分布において必要とされる軸方向に変化する振幅情報を符号化することにより実現することができる。
【００５９】
本発明のさらに他の実施形態によれば、所望のビーム成形分布が得られる、面の数は制限される。したがって、前記３−Ｄ推定及び／又は距離推定の所望精度を得るために、前記精度は隣接する２つの面間の軸方向間隔に等しくない一方で、前記面間の分布のための所定の評価が行われる。これは、例えば、異なる複数の面の様々なパターン間で前記変化の適当な設計を行うことにより行うことができる。その結果として、本発明の一実施形態によれば、相互関係に基づくコンピュータによる計算が、識別可能な特徴タイプの有限セットの所定の配列を含む、前記構造化光パターンを反射する被写体１３０の面間位置に関する比較的正確な指示の取得をもたらす。
【００６０】
従来のGerchberg-Saxton（ＧＳ）反復型アルゴリズム（U.Levy等により"Iterative algorithm for
determining optimal beam profiles in a 3-D space," Applied Optics, volume
38, pages 6732-6736, 1999と題する記事に示されている）を用いることにより、異なる軸方向位置（面）に異なる振幅分布を生じさせるための光学ビーム成形要素２０５を計画することができることに留意すべきである。次に、それは３−Ｄ光学システムを実現するために用いることができ、その３−Ｄ精度はプロジェクタ１１５と撮像装置１２０との間の距離に依存しない。結果として、プロジェクタ１１５により投射されまた撮像装置１２０により捕捉された（撮像された）前記反射パターンは被写体１３０までの距離を示す。設計されたビーム成形回折光学要素（位相マスク２０５のような）は、制限された数の分布面を得ることができるだけであるということに留意すべきである。したがって、本発明の一実施形態によれば、被写体１３０の面間距離の比較的正確な推定を可能にする面間補間法（図６に示す）がこれらの面の間の推定精度を改善するために用いられる。２つの隣接する面（面２及び面３のような（図２））間の距離は、前記２つの異なる面のそれぞれとの相互関係を評価することにより補間される。前記相互関係（ＣＯＲＲ）は、一般的に、以下のように定義することができる。
【００６１】
【数１】
2012504771.tif 000003
【００６２】
式中、Ａ及びＢは相互に関連付けられた変数であり、
【００６３】
【数２】
2012504771.tif 000004
【００６４】
はフーリエ変換演算子であり、
【００６５】
【数３】
2012504771.tif 000005
【００６６】
はフーリエ逆変換演算子である。結果として、Ａ及びＢが相似であれば、前記相互関係におけるピークが得られる。
【００６７】
本発明の一実施形態によれば、２つの面が例えば似たようなパターンを有し、その結果、両パターンがこれらの場所において（前記面内において）移されたすなわちシフトされただけであると仮定することができる。前記相互関係はシフト不変量であり、前記言及に関連する前記シフトの入力は前記相互関係のピークの位置をシフトさせるだけであることを意味する。したがって、この場合、前記ピークに関する２つの可能な位置があり、他方、両ピーク間の前記シフトは、前記２つの面における投射パターンの相対シフトに対応する。本発明のこの実施形態によれば、これらの最も近接する面間の距離において（他方、前記似たような両パターンはこれらの位置で変化するのみである。）、エネルギが一方の相関関係のピークから他方に移される。したがって、前記エネルギ移動の量を測ることにより、前記投射パターンの１又は複数の識別可能な特徴タイプを反映する、３−Ｄ被写体１３０の比較的正確な面間位置（場所）を推定することができる。
【００６８】
例えば、本発明の他の実施形態によれば、１９２×１９２画素の位相マスク２０５が、プロジェクタ１１５の内部に配置される８０８ナノメートルレーザのために１０ミクロンの画素サイズで計画されると仮定する。また、前記第１の所望強度面（例えば面１（図２））が前記位相マスクから０．１メートルの距離に配置され、また、前記第２の強度面（例えば面２（図２））が０．６メートルの距離に配置されていると仮定する。結果として生じる２つの獲得強度画像は図３Ａ及び３Ｂに記載されている。前記面間の任意の位置における距離（被写体位置）を推定するため、式（１）に似た、以下の相互関係式（２）が用いられる（式中ｍは、例えば１つ又は２つの−面１又は面２にそれぞれ等しい面の指数である。）。
【００６９】
【数４】
2012504771.tif 000006
【００７０】
式中、
【００７１】
【数５】
2012504771.tif 000007
【００７２】
は、面ｍ（例えば面１）の後ろの所望出力であり、またＩ（Ｚ）は任意の軸方向面間距離（位置）Ｚにおける強度である。
【００７３】
本発明の一実施形態によれば、前記シーン内の被写体１３０又は他の被写体の距離を評価するため、図４Ａないし図４Ｄに概略的に示すように、以下の３つのパラメータが考慮される。すなわち、２つの面（面１及び面２のような（図２））のそれぞれにおける２つの最大相互関係値（前記ピークの位置における相互関係）の比率である最大ピーク率、第１の面（面１のような）における第１の信号対雑音比（ＳＮＲ１で表わされる）、及び第２の面（面２のような）における第２の信号対雑音比（ＳＮＲ２で表わされる）である。
【００７４】
全ての必要とされる処理操作（捕捉画像の処理、対応する計算操作の実行、符号化光パターンが投射された、撮像されたシーン内の１若しくは複数の被写体の３−Ｄ被写体外形推定及び／又は距離推定に関する決定）が、ＤＳＰのような処理装置／システム（図示せず）、マイクロコントローラ、ＦＰＧＡ、ＡＳＩＣ等、あるいは、その他の従来の及び／又は専用の計算装置／システムにより、行うことができることに留意すべきである。さらに、本発明の他の実施形態によれば、前記処理装置／システムは撮像装置１２０の内部に設ける（結合する）ことができる。
【００７５】
また、本発明の一実施形態によれば、前記処理装置は、さらに、所定のコンピュータ操作の１つ又は複数の結果に基づいて前記シーン内の１又は複数の被写体１３０の３−Ｄ幾何学的形状を決定するように設定されていることに留意すべきである。
【００７６】
加えて、本発明の一実施形態によれば、前記符号化光パターンは、１−Ｄ、２−Ｄ、３−Ｄのような任意の次元のものとすることができることに留意すべきである。
【００７７】
さらに、本発明の他の実施形態によれば、光学要素１１０は回折要素又は非回折要素からなるものとすることができることに留意すべきである。図２は、面１ないし面４のような仮想面の概略図であり、本発明の一実施形態によれば、投射された、構造化（符号化）光が、被写体１３０（図１）に向けて進行する間に、これらの面を通過する。例えば、Ｚが前記軸方向位置（例えばプロジェクタ１０５（図１）内に設けられた、位相マスク２０５から面１までの範囲／距離、）を表わすと仮定する。加えて、ΔＺが仮想の面１及び面２間の距離を表わす。
【００７８】
用語「仮想」は、本発明の一実施形態によれば、前記面が前記シーン内の物理的被写体ではないことを強調するためにのみ使用され、したがって、この用語は限定するものとして考えられるべきない、ということに留意すべきである。
【００７９】
図３Ａ及び図３Ｂは、本発明の一実施形態に従う、シーンの第１及び第２の面（面１及び面２（図２））におけるサンプル光強度分布画像３０５及び３１０をそれぞれ示す。この実施形態によれば、光強度分布画像３０５及び３１０は、比較的正確な方法で被写体１３０（図１）までの距離／範囲を計算するため、所定の（基準）参照テーブルと相互に関連付けられ、例えばメモリ素子（図示せず）内に記憶される。
【００８０】
図４Ａないし図４Ｃは、本発明の一実施形態に従う、計算されさらに被写体１３０（図１）の軸方向面間位置（図２）に関する決定を行うために用いられる複数のパラメータの概略的なグラフである。図４Ａは最大ピーク率（ピーク率）パラメータの概略的なグラフ４０５であり、図４Ｂは第１の面（面１（図２）のような）における第１の信号対雑音比（ＳＮＲ１）を表わす他のパラメータの概略的なグラフ４１０であり、また、図４Ｃは第２の面（面２（図２）のような）における信号対雑音比（ＳＮＲ２）を表わす追加のパラメータの概略的なグラフ４１５である。前記した３つのパラメータであるピーク率、ＳＮＲ１及びＳＮＲ２に基づいて、前記補間が実行され、シーン内の被写体１３０の軸方向面間位置に関する決定がなされる。
【００８１】
図５Ａは、本発明の他の実施形態に従う、システム１０５（図１）と比べてエネルギ的に効率の良い、３−Ｄ被写体外形及び距離の面間推定システム／装置１０５の概略図である。この実施形態によれば、パターン投射モジュール１２５は、さらに、偏光され構造化された光を被写体１３０に向けて提供することを可能にするための偏光ビームスプリッタ１１０と、直線偏光を円偏光にまた反対に円偏光を直線偏光に変換するためのλ／４板１２６とを含み、ここにおいてλは光の波長である。さらに、プロジェクタ１５は、偏光ビームスプリッタ１１０の偏光分割比に適合する偏光を有する直線偏光レーザ（図示せず）を含む。
【００８２】
結果として、本発明のこの実施形態によれば、システム１０５は偏光に基づくエネルギ的に効率の良いシステムであり、実質的にすべての光エネルギ（実質的に１００％）が偏光ビームスプリッタ１１０から出力される。軸方向に変化する強度を有しかつ強度が変化する光ビームの空間構造形態で識別可能な特徴タイプの有限セットの所定配列を含む、構造化光パターンに対応する構造化光が、偏光ビームスプリッタ１１０から出力されると、その偏光がλ／４板１２６によって回転され、その結果として、前記光の偏光が円となる。偏光された構造化光はこれが被写体１３０から反射されて戻ると（被写体１３０は、投射された構造化光パターンの１又は複数の識別可能な特徴タイプを反射させる）、再びλ／４板１２６を通過し、その偏光は直線偏光となるが、それはプロジェクタ１１５により投射された光の元の偏光に対して直角をなす。結果として、常用のビームスプリッタ１１０（図１）に代わる偏光ビームスプリッタ１１０を使用することにより、ビームスプリッタ１１０を経る光の各通路におけるエネルギ損失が約５０％回避される。したがって、前記光は、分かれることなしに、偏光ビームスプリッタ１１０を経て撮像装置（カメラ１２０のような）へと進行する。
【００８３】
図５Ｂは、本発明のさらに他の実施形態に従う、３−Ｄ被写体外形及び距離の面間推定システム／装置１０５の概略図である。この実施形態によれば、システム１０５は、２つの異なる波長λ１及びλ２でそれぞれ動作する２つのプロジェクタ１１５’及び１１５”を含む。それぞれに対応する位相マスク２０５’及び２０５”を使用することにより異なる波長で、軸方向に変化する強度を有するいくつかの符号化光パターンを同時に投射するのに役立つからである。２つの異なる波長を使うことにより、パターン投射モジュール１２５の物理的寸法を増大させることなしに、そして、通される情報の量を増大させることなしに、より多くのパターンを作り出すことができることに留意すべきである。
【００８４】
２つの異なるセットのパターンを同時に投射することは、さまざまな方法でシステム１０５を増強する、二重投射及び撮像（同時継続特許出願WO 2008/062407に記載されているように）に言及することに留意すべきである。例えば、異なる波長でパターンのセット「Ａ」及び該「Ａ」の逆数である「Ｂ」を同時に投射しかつ撮像することにより、また、撮像装置１２０によって得られた対応する複数の画像間で減算を行うことにより、より強固でかつより正確な復号を生じさせる、符号付きのパターンが得られる。
【００８５】
図６は、本発明の一実施例に従う、３−Ｄ被写体外形及び距離の推定の実行の概略的なフローチャート６００である。ステップ６０５において、プロジェクタ１１５（図１）が、変化する強度の光ビームの空間構造の形で有限セットの識別可能な特徴タイプの所定配列を含む、構造化光パターンを対象１３０（図１）に向けて投射し、その結果得られる画像（投射パターンの１又は複数の反射された識別可能な特徴タイプを含む）が撮像装置１２０（図１）により捕捉される。次に、ステップ６１０において、捕捉された画像の強度値が、処理装置／システム（図示せず）により、第１及び第２の仮想面（例えばそれぞれ面１及び面２(図２)）に対応する、２つの対応する所定の（基準）参照テーブルと、例えば相関式（２）を用いて相互に関連付けられる。結果として、ステップ６０１において、２つの相互関係が実行され、第１の相互関係は第１の仮想面に関連し、また、第２は第２の仮想面に関連し、これらの間で前記補間法が実行される（前記シーン内の被写体１３０の比較的正確な軸方向面内位置に関する決定へと導く）。その後、ステップ６１５において、前記２つの相互関係のそれぞれの最大値が決定され、他方、各最大相互関係値は対応する面（面１又は面２のそれぞれ）に関連する。結果として、２つの最大相互関係値が決定され、これらは例えば「ＭＡＸ１」及び「ＭＡＸ２」として表示することができる。さらに、ステップ６２０において、前記２つの相互関係のそれぞれの追加の最大値（ステップ６１５で決定された最大値「ＭＡＸ１」及び「ＭＡＸ２」に加えて）が決定される。また、これらの追加の２つの最大値は、前記第１及び第２の面（それぞれ面１及び面２）に関連し、これらは「ＭＩＮ１」及び「ＭＩＮ２」として表示することができる。次のステップ６２５において、所定のコンピュータによる（計算）操作が、それぞれ、「ＭＡＸ１」の値を「ＭＡＸ２」で割ることによりピーク率（ピーク率＝ＭＡＸ１／ＭＡＸ２）を決定し、また、ＳＮＲ１又はＳＮＲ２すなわちＳＮＲ１＝ＭＡＸ１／ＭＩＮ１又はＳＮＲ２＝ＭＡＸ２／ＭＩＮ２を決定するように実行される。前記位相要素（位相マスク２０５のような）が前もって定められるため、全ての軸方向位置におけるパラメータ（前記「ピーク率」、ＳＮＲ１又はＳＮＲ２パラメータ）の値についての初期の情報があり、それらを前記面間に含む。最後に、ステップ６３０において、前記３つのパラメータであるピーク率、ＳＮＲ１及びＳＮＲ２からなる前記初期の情報により、被写体１３０の比較的正確な軸方向面間位置に関する決定がなされる。シーン内の被写体１３０の軸方向面間位置に関するこの決定が、この実施形態のみのために示される、前記したコンピュータによる操作とは異なる、他の所定のコンピュータによる操作の結果に基づいてなされ得ることに留意すべきである。
【００８６】
比較的高い３−Ｄ及び距離の推定の精度を得るため、２つの隣接する面（例えば面１及び面２）間の軸方向分離と、前記面間の強度分布のための対応する評価とを行うことができることに留意すべきである。これは、例えば、コンピュータによる計算（例えば式（２）を用いることにより実行される）に基づく相互関係が被写体１３０を反映する正確な面間位置（範囲／距離）に関する比較的正確な指示を与えることができるように、異なる（仮想）面内のパターン間に前記変化を適当に設計することにより行うことができることに留意すべきである。
【００８７】
本発明の一実施形態によれば、図７は１２個の明確な２値パターン７００のサンプルセットの概略図であり、各パターンは、複数の最大点、複数の最小点、複数の鞍点、複数のコーナー、複数のエッジ（例えばダブルエッジ、これは一方が他方に対して比較的近接している２つのエッジからなる）等のような、有限のセットの識別可能な特徴タイプの所定の配列を含む所定の二次元パターンからなる。明確な２値パターン７００はキーパターンＫ１ないしＫ１２と、エネルギパターンとしても言及されるパターン間Ｅ１．５ないしＥ１２．５とを含む。これらのパターン間Ｅ１．５ないしＥ１２．５は、各対の連続したキーパターン間での平均化プロセスの産物である。本発明の一実施形態によれば、各キーパターンは２つ折りの放射対称性と同様に周期的である。したがって、各キーパターンの周期は、パターン面にタイルを敷く、２つ折りの放射対称性二値画像からなる。このようなキーパターン９２０は、例えば図９Ｄに表われている。左上の矩形７６２（例えば、Ｍ×Ｎ行列を表わし、ここでＭ＝８、Ｎ＝２である。）は単一の周期を示し、また、複数の「×」マーク９０５は回転の放射対称性中心を示す。このようなタイルを敷く画像のそれぞれは、例えば９Ｂ図に示すように、三進法のＭ×Ｎ符号化行列７６３に従って、市松模様のパターンを調整することにより構成される。各三進法の値は、黒色の四角形及び白色の四角形の市松模様の各分岐合流点の周りの対応する星形領域（星形特徴）に影響を及ぼす。三進法の値「０」及び「２」は、それぞれ、前記領域を黒色及び白色に着色することを示し、他方「１」は前記市松模様の分岐合流点が修正されないように維持することに対応する（さらに、図９Ｃ及び図９Ｄにそれぞれ示されたパターン９１５及び９２０に（例えば図９Ｃ及び図９Ｄの左上の矩形７６２に）見られるように）。似たような従来の調整計画が同時継続出願WO 2008/062407に見ることができることに留意すべきである。
【００８８】
明確なＰ個（例えばＰ＝１２）のキーパターンは明確なＭ×Ｎ三進法符号化行列に由来するため、キーパターンＫ１ないしＫ１２のそれぞれは、変化領域として言及される前記星形領域（図９Ｂにおけるパターン上の黒色／白色星形領域）の着色のみにより互いに異なる。実質的な無変化領域として言及される、パターン９１０の残りの循環領域は、符号化（Ｍ×Ｎ三進法符号化行列７６５を用いることによる）によって修正されず、したがって全てのセットのパターン７００に従って同一に維持される。
【００８９】
本発明の一実施形態によれば、前記Ｍ×Ｎ×Ｐ行列は体積三進法行列であり、ここにＭ、Ｎ及びＰは整数値である（Ｐは多数の所定パターンである）。前記行列の値は、例えば以下のルールに従って、予め規定することができる。
ａ）全行列Ｍ×Ｎ×Ｐの各部分行列Ｕ×Ｖ×Ｐ（例えば、Ｕ＝２、Ｖ＝２）に関して、任意のＵ×Ｖ断面行列（部分行列７６５のような）は固有である。換言すると、任意のＰ（１２）のキーパターンＫ１ないしＫ１２における任意の所与の横方向位置に関して、任意のＵ×Ｖブロックが、全てのパターン配列に沿って（全セットのパターン７００に沿って）、一回だけ現れる。これは、相互関係によるパターン照合のプロセスがＵ×Ｖの大きさの複数の画像ブロックに依存し得ることを示す。このような各ブロックは照合することができ、これにより対応する３−Ｄ及び距離の情報を提供する。軸方向Ｕ×Ｖ固有のみが必要とされ、他方、図７に概略的に示すように、異なる横座標において反復するＵ×Ｖブロック７６５もまた実行され得ることに留意すべきである。
ｂ）全Ｍ×Ｎ×Ｐ行列の各Ｕ×Ｖ×Ｐ部分行列（サブセット）に関して、任意の連続したＵ×Ｖ断面行列の平均行列もまた固有である。換言すると、前記ルール（ａ）は面間照合を含むように拡張され、結果としてより高精度の３Ｄ及び距離の情報を得る。
ｃ）パターンにおける黒色領域及び白色領域の合計間の比率Ｒは半分で境界を付けられ（Ｒ１−１２＝０．５±０）、また、この比率は前記パターンの配列に沿って実質的に変化しないことを示す（すなわち、変化率はＡ＝０±０である）。結果として、これは一定の放射エネルギ制約に適合する。
ｄ）前記パターンにおける任意の２つの連続するＵ×Ｖブロック間の変化は、Ｄ＝２±０変化領域のような、所定数の変化領域に境界を付けることができる。また、これらの変化は、黒色から白色への直接推移、また逆に白色から黒色への直接推移からなる、禁止値変化の追加セットＣにより制限される。換言すると、本発明の一実施形態によれば、黒色のダブルエッジから交差する白色ダブルエッジ（互いに交差する）への推移、また逆に白色のダブルエッジから交差する黒色ダブルエッジへの推移は禁止され、他方、白色または黒色のダブルエッジから鞍点への推移（逆の場合も同様）は許される。これらのルールが分布の密度及び一様性に関しての双方の局所的エネルギの変化、並びに局所的な大きさ及び比率の制限に従うことに留意すべきである。したがって、このようなエネルギ変化を適当に予め規定しまた制御することにより、エネルギパターンＥ１．５ないしＥ１２．５は、前記エネルギ及びキーパターン間の比較的強い相互関係に導くキーパターンＫ１ないしＫ１２に十分に似たものとなる。他方、エネルギパターンＥ１．５ないしＥ１２．５は、キーパターンＫ１ないしＫ１２間の前記エネルギパターンの個々の位置をなおも決定することができるようにするため、キーパターンＫ１ないしＫ１２とは十分に異なる。加えて、任意の２つの連続するＵ×Ｖブロックは、変化しないように維持される、三進法の値「１」のＪ個の割り当て（例えばＪ＝１±０）を含む。これは、キーパターンＫ１ないしＫ１２及びパターン間Ｋ１．５ないしＫ１２．５の双方の全体にわたって、市松模様の分岐合流点の特徴が常にある形態と密度とで現れることを示す。分岐合流点の特徴は、これらが得られた画像（例えば、撮像装置１２０により（図１））の鞍点として現れるため、比較的良好な位置の特定を提供することが分かっていることに留意すべきである。前記鞍点の局所的対称性のため、このような鞍点は、不鮮明な状態下にあっても、これらの横の位置が画像面内に比較的正確に維持され、その結果これらのサブピクセルの横位置を比較的正確かつ一貫した方法で検出することができる。ＳＯＰ構造では、この横位置は通常動作の間固定される。しかし、近似ＳＯＰ構造では、撮像装置１２０（図１）とプロジェクタ１１５（図１）とは、わずかではあっても離され、被写体１３０（図１）から反射された前記パターン（有限のセットの識別可能な特徴タイプの所定配列を含む）の横位置は反射領域に対して相対的に変化し、このため良好な特徴位置特定が望まれる。
【００９０】
また、ＳＯＰ構造において、サンプルパターンセットが、全Ｐのキーパターン及びこれらの生成されたパターン間内のＵ×Ｖ符号化ブロックの一意性のために例えばＵ×Ｖ領域（Ｕ×Ｖ領域７６５のような）だけを反映する、表面の距離データを提供することに留意すべきである。本発明の他の実施形態によれば、これらの局所的一意性の基準を拡張することは、例えば、多数のさまざまなブロックサイズの一意性及び非矩形状の符号構造の実行を含む。
【００９１】
本発明のさらに他の実施形態によれば、各キーパターン（及び各パターン間）は、単一の基本的なＭ×Ｎ三進法符号行列のために周期的であり、このために記述的に小型である。符号の周期的な反復はパターン中に変換対称として現れ、ここでは各基本的タイル張りユニットは矩形である。適当な反復パターンによって得られた平行四辺形の形状のタイル張りのような非矩形状のタイル張りもまた用いることができることに留意すべきである。本発明の他の実施形態によれば、パターン７００のセット（一連）内の少なくとも１つのキーパターン及び／又は少なくとも１つのパターン間が非周期的パターンであることに留意すべきである。
【００９２】
本発明のさらに他の実施形態によれば、Ｍ×Ｎ行列を２つ折りの放射対称性に制約することは、全パターンセットもまた２つ折りの放射対称性であり、したがって、例えば、従来の壁紙群「ｐ２」に属することを示す。いくつかのビーム成形プロセスはこのような対称性から恩恵を受け、例えば、より効果的で精度の高い方法でビーム成形回折光学要素（位相マスク２０５（図１）のような）の設計することを可能にすることに留意すべきである。また、前記記述的小型化はこのような対称性によりさらに高められることに留意すべきである。また、３つ折り及び６つ折りの放射対称性並びに反射及び滑りの対称性（例えば壁紙群「ｐ４ｍ」及び「ｐ３１ｍ」）のような他の対称性も同様の方法で適用される。
【００９３】
本発明のさらに他の実施形態によれば、ＳＯＰ構造に関して、非周期的最大経路に由来するパターン配列も同様に適当である。他方、近似ＳＯＰ構造に関して、周期的配列は、これらが全Ｐの配列を何度も反復することを有益的に許すため、好ましい。非同軸のプロジェクタ／カメラ構造のため、前記反復は、各反復同一符号構造が、エピポーラ線又はエピポーラ曲線として知られる、明瞭な一方向トラックに沿って明瞭な場所で撮像されるため、識別の曖昧性を導入しない。したがって、前記エピポーラ線に沿った符号化パターン構造の位置は標識化フォーマットの一部となり、さらに、符号記述の小型化に寄与する。例えば、追加の面が一意的に標識化され、同一の局所的一意性仕様を与えられる。代わりに、より小さい一意性領域が所与の面数を維持する。
【００９４】
本発明のさらに他の実施形態によれば、近似ＳＯＰ構造において、例えばより小さい最小照合構造（Ｕ×Ｖブロックのような）を提示することにより局所的一意性の要求を最適化する手段を提示するように、できる限りＰ反復を行うことが望ましい。適当な方法で前記プロジェクタ／カメラの幾何学位置を整えることは、所定のエピポーラ線に沿っての画像変換を含む、前記反復分布パターンを最適化するための手段を提示する。このため、例えば、同時継続出願WO 2008/062407に記載されたような最適化方法を用いることができ、これは前記パターン投射の傾斜角等に関して最適化された角度でエピポーラフィールドを整列することを可能にする。加えて、WO 2008/062407によれば、好ましい方向性符号化として言及されている細長い周期的に反復する行列を用いることが望ましい。
【００９５】
これらの最適化は、また、従来の能動型三角測量に適用することに留意すべきである。また、特に近似ＳＯＰ構造において、前記好ましい方向性符号化は好ましい反復方向に面間符号反復を含むように拡張することができることに留意すべきである。また、特に近似ＳＯＰ構造において、このような反復する符号は、破線又は点線に似た、前記エピポーラ線に沿っての明瞭な複数のトラックを現す。トラックの間隔及び長さは、プロジェクタ１１５及び撮像装置１２０（図１）間の距離、並びに前記離れたキーパターン面間の軸方向間隔と密接に関連する。
【００９６】
図８Ａは、本発明の一実施例に従う、ＳＯＰ／近似ＳＯＰパターン生成の概略的なフローチャート８００である。ステップ８０５において、法典構造及び対応する法典構造変化が規定されている。用語「適法」とは、この操作（ステップ８０５の）が、例えばＵ×Ｖブロックに関する前記Ｃ、Ｊ、Ａ、Ｄ、Ｒパラメータに従うような、所定セットのルールに従って行われることを意味することに留意すべきである。次に、ステップ８１０において、法典構造のみを含む、１又は複数セットの有効な局所的一意性行列（Ｕ値、Ｖ値及びＪ値に従う、有効な三進法Ｕ×Ｖ行列のような）が生成される。また、用語「有効な」は、前記所定のセットのルールに従う、１又は複数の「適法な」操作の所産に対応することに留意すべきである。その後、ステップ８１５において、選択的に変換以外の対称性を有する（Ｍ、Ｎ及びＲに従う、コンピュータで計算されたＵ×Ｖ行列のみを含む、有効な２つ折りの放射性対称の三進法Ｕ×Ｖ行列のような）、適法な局所的一意性行列のみを含む１セットの有効な周期的に反復する行列が生成される。法典構造変化に従う、有効な周期的に反復する行列の有効な連続のみを含む、前記セットの有効な周期的に反復する連続した行列が、ステップ８２０においてさらに生成される。例えば、前記有効な連続した行列は有効な三進法Ｍ×Ｎ×Ｔ（Ｔ＝２）行列とすることができ、これは所望値Ａ、Ｄ及びＣに従う、可能な連続したコンピュータで計算されたＭ×Ｎ行列を表し、ここにおいてＡは変化率であり、Ｄは、任意の２つの連続したＵ×Ｖブロック間の変化が境界される、変化領域の数であり、また、Ｃは前記任意の２つの連続したＵ×Ｖブロック間の１セットの禁止値の変化である。このステップで生成された前記セットの有効な連続した行列が局所的一意性行列及び平均化された局所的一意性行列の双方のいずれの軸方向反復をも含まないことに留意すべきである。次に、ステップ８２５において、１組の有効な周期的に反復する体積行列が生成され、前記反復する体積行列は、有効な連続した行列をのみを含み、かつ局所的一意性行列及び平均化された局所的一意性行列の双方のいずれの軸方向反復も含まないような、１組の予定のルールに適合する。例えば、前記体積行列は、コンピュータで計算されたＭ×Ｎ×Ｔ行列のみを含みかついずれの軸方向Ｕ×Ｖ反復も含まない、全てが有効なＰ個の最大三進法Ｍ×Ｎ×Ｐ行列からなるものとすることができる。このステップは、グラフ内のハミルトン経路（又は同等に、オイラーサイクル）を発見することによりDe-Bruijn  シーケンスを生成する従来のプロセスを表示する、グラフ内の最大長さの周期的経路の検索（全数検索）として実行することができることに留意すべきである。前記グラフのエッジは、前述した軸方向一意性制約に適合する、可能性のある連続したＭ×Ｎ×Ｔ行列の全ての有効な組み合わせを表す。この制約は、また、前記経路生成プロセスそれ自体の間に実施され、検索木の成長を小さくする。さらに、前記体積行列のセットが、ステップ８２５において、例えば前記グラフにおける最も長い経路を検索することにより生成され得ることに留意すべきである。さらに、ステップ８３０において、一連の周期的に反復するパターン（例え��、キーパターン）が、例えば基本的な市松模様のパターンを調整しかつ所定の着色機構に従う、有効な周期的に反復する体積行列（コンピュータで計算されたＭ×Ｎ×Ｐ行列のような）を用いることにより生成される。
【００９７】
次に、ステップ８３５において選択的に、ステップ８３０において生成された、一連のパターンが、例えば、ぼやけさせ、２値化、コンボリューション、デコンボリューション、キャリア交代等のような従来の画像処理を用いて処理される。
【００９８】
本発明の他の実施形態によれば、前記所定のパラメータＵ、Ｖ、Ｊ、Ｍ、Ｎ、Ｒ、Ｔ、Ａ、Ｄ及びＣの対応値の選択に基づいて、任意の他のパターンを生成することができることに留意すべきである。また、連続した行列、体積行列等のような任意の行列及び／又はパターンを、反復する（周期的に）するもの又は反復しないもののいずれかとし、また周期的に反復するものとすることができることに留意すべきである。
【００９９】
図８Ｂは、本発明の他の実施形態に従う、近似ＳＯＰパターン生成の概略的なフローチャート８００である。この実施形態によれば、ステップ８１５’において、所定の（例えば好ましい）方向へのみの局所的一意性行列の反復を含み、あるいは代わりにこのような反復を全く含まないが、変換以外の対称性を選択的に有する、適法な局所的一意性行列のみを含む１セットの有効な周期的に反復する行列が生成される。次に、適法な符号構造変化に従って、有効な周期的に反復する行列の有効な配列のみを含む、前記セットの有効な周期的に反復する連続した行列が、ステップ８２０’においてさらに生成される。本発明のこの実施形態によれば、前記セットの有効な連続した行列は、局所的一意性行列及び平均化された局所的一意性行列の双方のいかなる軸方向反復も含まないが、局所的一意性行列及び平均化された局所的一意性行列の双方の反復を所定の（例えば好ましい）方向にのみ含みあるいは代わりにこのような反復を全く含まない。この後、ステップ８２５’において、１セットの有効な周期的に反復する体積行列が生成され、前記反復する体積行列は、有効な連続した行列のみを含みかつ局所的一意性行列及び平均化された局所的一意性行列の双方のいかなる軸方向反復も含まないが、局所的一意性行列及び平均化された局所的一意性行列の双方の反復を所定の（例えば、好ましい）方向にのみ含むか又は代わりにこのような反復を全く含まないような、１セットの所定のルールに適合する。
【０１００】
本発明の一実施形態によれば、パラメータＤ（任意の２つの連続したＵ×Ｖブロック間の変化がＤ領域（例えばＤ＝２±０））に対して境界されている）の設定に加えて、例えば異なる変化領域を消費する、図１０Ａに示すパターン１００５上に示されたひし形及び循環（図示せず）のような、前記した星形以外の形状を有する、着色領域により面間パターン変化の量をさらに制御することができることに留意すべきである。加えて、グレースケールの色等のような黒色及び白色以外の色を用いることも可能である。
【０１０１】
図１０Ｂは、本発明の他の実施形態に従う、追加のサンプルパターン１０１０の図である。パターン１０１０は、４５°だけ回転された従来のデカルトパターンに似た直角なひし形パターンである。したがって、ひし形着色形状を用いることによりかつ分岐合流点領域を一様に着色されたグレーのひし形領域で置き換えることにより、比較的小型のパターン表現を可能とし、各変化及び実質的に無変化の領域が、例えば単一の画素により表わされる。これは、さらに、位相マスク２０５（図１）のような、ビーム成形回折光学要素のビーム成形設計プロセスの間に求められるコンピュータによる計算を減少させる。
【０１０２】
３以上の着色グレー値の使用は三進法ベースからより高いベース（例えば、四進法ベース等）へと符号を拡張することを許し、これにより、例えばより明確な面の生成又は局所的一意性符号構造の減少を許すことに留意すべきである。
【０１０３】
図１０Ｃは、本発明のさらに他の実施形態に従う、他のサンプルパターン１０１５の追加の図である。パターン１０１５は、前記形状のエッジを滑らかにしかつ移すような、前記パターン内の（着色された）領域の形状の修正を含む。このパターンは、ぼやけさせ、２値化、コンボリューション、デコンボリューション等のような、パターンの任意の操作が可能であることを明示する。これは、例えば、パターン内により一様な平均強度をもたらし、また前記パターン照合プロセスにおけるＳＮＲを改善することに役立ち、その結果より高精度の３−Ｄ及び距離の情報を得る。
【０１０４】
このようなパターンの変形は、例えば、基礎的なパターンとして変形された非デカルト市松模様の使用、及び非一様な局所的変化領域の使用に相当する。また、これまで実質的に無変化の領域（例えば循環）は、前記したように、位置及び寸法の双方に関して、前記パターン配列に沿って変化することに留意すべきである。
【０１０５】
本発明の他の実施形態によれば、例えば、図１０Ｃのパターン変形に加えて、図１０Ｄに表わされた操作のような、パターンの他の操作が可能である。図１０Ｄでは、反対色の円又は長円がこれまでの実質的に無変化の領域に入れられ、これらの領域を置き換えており、他方、符号調整された領域のカラー化は不変に維持されている。キャリア交代として言及することができる、このプロセスは、さらに、局所的平均パターン強度の均衡、並びに、パターントラスト及びカラーエッジの曲率の増大を許す。前記パターンの操作（図１０Ｃ及び図１０Ｄに示されている）を何度も繰り返すことにより、前記パターン強度の釣り合わせを最適化し、パターンのコントラストを増大させる等のように、これらの特性をより最適化することに留意すべきである。
【０１０６】
本発明のいくつかの実施形態が図示により記載されているが、本発明が、本発明の精神から離れ又は請求の範囲を超えることなしに、多くの修正、変更及び適用をもって、また当業者の範囲内にある多くの等価又は代わりの解決手法の使用をもって、実施することができることは明らかであろう。
【図１】
2012504771.tif 000008
【図２】
2012504771.tif 000009
【図３Ａ】
2012504771.tif 000010
【図３Ｂ】
2012504771.tif 000011
【図４Ａ】
2012504771.tif 000012
【図４Ｂ】
2012504771.tif 000013
【図４Ｃ】
2012504771.tif 000014
【図５Ａ】
2012504771.tif 000015
【図５Ｂ】
2012504771.tif 000016
【図６】
2012504771.tif 000017
【図７】
2012504771.tif 000018
【図８Ａ】
2012504771.tif 000019
【図８Ｂ】
2012504771.tif 000020
【図９Ａ−９Ｄ】
2012504771.tif 000021
【図１０Ａ】
2012504771.tif 000022
【図１０Ｂ】
2012504771.tif 000023
【図１０Ｃ】
2012504771.tif 000024
【図１０Ｄ】
2012504771.tif 000025
【国際調査報告】
2012504771.tif 000026
2012504771.tif 000027
2012504771.tif 000028
2012504771.tif 000029
2012504771.tif 000030