JPH11512856A - ２次元イメージから３次元イメージを生成する方法 - Google Patents

Abstract

(57)【要約】 複数の２次元イメージから３次元イメージを構築する方法は、イメージのうちの１つを基準イメージとして選択するステップと、第２のイメージを選択するステップとを備える。第２のイメージにおける１又はそれより多くの点が、基準イメージにおける各点に対する可能なマッチ点として識別される。他のイメージは、第２のイメージにおいて見つけられた可能なマッチ点を検証するために用いられる。可能なマッチ点の投影は３次元の領域にグループ化され、それら領域は偽の領域を識別するために基準イメージに投影される。偽の領域は除去され、残りの領域を組み合わせることによって３次元イメージが構築される。

Description

【発明の詳細な説明】 ２次元イメージから３次元イメージを生成する方法 発明の背景 発明の分野 本発明は広くはイメージング・システムに関し、より特定的には３次元イメー ジ・システムに関する。 背景の説明 ステレオ・ビジョン（stereo vision）はイメージからの深さ（depth、深度） 情報の回復のための古典的な方法である。人間及び他の動物は、部分的に、２つ の目からのイメージを比較することによって深度を見ることが数世紀にわたって 知られている。このプロセスの幾何学的基礎が図１に示されている。図１におい て、左と右の両方のカメラは、近点（near point）と遠点（far point）とラベ ル付けされた２つの同じ点を見る。両方の点に対して、三角形が形成され、その 三角形の１つの辺はカメラのベースラインであり、これは知られているものと推 定され、カメラの光学的中心から空間中の点への２つの光線が他の２つの辺を形 成する。カメラのイメージ上の点の位置が知られているので、深度における点の 位置は、単に、光線をイメージ点を通じて、空間においてそれらが交差するまで 延長することによって、計算される。その交差点はイメージからの点の３次元座 標である。 そのプロセスを行うために知らねばならない情報は以下のものを含む。 ・左のイメージのどの点が、右のイメージのどの点に対応するかについて。こ れは対応関係の問題として知られている。 ・カメラの特性、即ち、それらの焦点距離、相対的配置、その他について。こ れは校正の問題として知られている。 何れの問題も容易には解決できない。対応関係については困難である。なぜな ら、多くのイメージは反復的な質感を有するが、人間は多くの他の情報を適用す ることができるので混乱することはない。しかし、そのような質感はコンピュー タを容易に混乱させる。校正は概念的には困難ではない。しかし、校正は、信頼 性のある結果を導出するために高い精度をもって行われねばならないので、技術 的に困難である。 対応関係又は校正におけるエラーの結果は厳しいものとなる。対応関係におけ る誤りが図１の例においてなされ、右イメージの遠点のイメージが、左イメージ の近点のイメージとして誤って識別された仮定する。その結果は図２に示されて いる。真の近点も真の遠点もも発見されず、代わりに、誤った点（偽の点）が見 られる。他方、校正エラーは、深度においてイメージのひずみを生じさせる。例 えば、ベースラインの距離が測定されるものよりも実際に少ないならば、イメー ジ全体の深度が実際と比較して延ばされる。校正の問題は、多種の手段によって カメラの特性を正確に測定することによって解決できるので、典型的には対応関 係の問題によって大きな問題が発生する。 左イメージにおける点、例えば図２の近点、に対するマッチ（match、整合、 一致）を見つけることの問題を考慮する。この点に対する正しい深度は未知であ るので、左イメージのこの点を通る光線を探さねばならない。その光線は、右イ メージの、エピポーラ（epipolar）・ラインと呼ばれるラインに投射する。その ラインのイメージは図３に示すように現れる。左イメージからのピクセルのイン テンシティ（intensity、輝度）は知られているので、エピポーラ・ラインは、 右イメージの同じインテンシティのピクセルに対してサーチ（探査）され得る。 それは、空間における点が両方のカメラに対しておなじ外観を有することを仮定 し、これは、対象物がミラー様の仕上げを有していないことを暗黙のうちに仮定 する。（この分野で既知のステレオ・アルゴリズムは光る金属面に対して作用し ないのはこの理由のためである。）サーチによって、いくつかの可能なマッチ点 （整合点である可能性のある点）が識別される。正しいマッチ点を適切に選択せ ねばならない。さもなければ、深度の回復において、誤り、恐らくは重大な誤り がなされてしまう。 正しい選択を行う試みのためのいくつかの従来技術の方法がある。第１に、カ メラが互いに近接して配置されたならば、ベースラインが、固定された深度範囲 に対して減少される。ベースラインが短いので、ラインが偽のマッチ（誤った整 合）に交差する可能性が低くなる。このアプローチの問題は、カメラの光学的中 心と空間中の点とで形成される三角形が狭くなるので、精度も低下することであ る。結果として、マッチの概算における小さいエラーが、深度の概算における大 きなエラーを導く。 第２の従来技術の技法は、個々のピクセルではなく領域を整合（マッチ）させ ることである。例えば、左イメージからの各ピクセルのまわりの小さい矩形が領 域であり得、該領域に対して右イメージにおけるマッチが探され得る。独立性を 仮定したときに、Ｎピクセルのマッチする可能性は１ピクセルがマッチする可能 性の１／Ｎであるので、偽のマッチの可能性は減少される。このアプローチの問 題は、空間の点が両方のイメージにおいて同じようにアライメントされていると 仮定せねばならないことである。即ち、カメラ間のベースライン距離が大きいな らば、左イメージからの矩形が、右イメージの平行四辺形に投影し得る。平行四 辺形の形状は未知である。なぜなら、それは空間における面の垂直、及びその位 置に依存するからである。結果として、右イメージにおいて、左イメージからの 矩形を見つけるための、検査する正しいピクセルを識別することができない。見 る者（ビューワ）に対して正面に呈示された表面を見るときは、その影響は無視 できる。しかし、表面がビューワから曲がって遠ざかるにつれて、及び左イメー ジからの矩形が大きく異なる深度の点を含み得る対象物の境界では、より顕著に なる。このアプローチを基にする従来技術のステレオ技術は、対象物の境界でそ の能力が低下する傾向がある。 別の従来技術のアプローチは、１つのイメージにおける大きな特徴であって、 他方のイメージにおいてもサーチ可能である特徴、例えば、縁部、を識別するこ とを試みることである。このアプローチは、領域のマッチングに幾分類似してい る。しかし、上述の問題に苦しむ度合いが低い。なぜなら、視野の広い範囲にわ たって同一に見える傾向のある特徴部が選択され得るからである。しかしながら このアプローチの問題は、深度が少なくなってしまうことである。なぜなら、多 くの表面、特に、人工的なものは、識別されるべき多くの特徴部を有していない からである。 最も保証された技術の１つは複数のカメラを用いることである。複数のイメー ジにおけるマッチが捜されるならば、使用されるカメラの数に比例して偽のマッ チ（誤ったマッチ）の可能性が低減され得る。Ｎ＋１のカメラを用いたときの偽 のマッチの可能性は、２つのカメラを用いたときの偽のマッチの可能性の１／Ｎ である。しかしながら、誤った数のピクセルがマッチされると、偽のマッチは起 こり、また、マッチングを行うのは計算的に高価である。したがって、信頼性が 高く、正確で、適正なマッチを識別するのに必要な時間と計算リソースとを減ら すような、複数のカメラによって生成された複数の２次元イメージから３次元イ メージを生成する方法に対する必要性が存在する。 発明の概要 本発明は少なくとも２つの２次元イメージから３次元イメージを構築する方法 に関する。この方法は基準イメージとなるようにイメージの１つを選択するステ ップを備える。他方のイメージの１つ以上の点が、基準イメージにおける各点に 対する可能なマッチ点として識別される。マッチする点の投影（プロジェクショ ン）は３次元領域にグループ化され、その領域は、偽の領域（誤った領域）を識 別するために基準イメージに投影される。偽の領域は除去され、３次元イメージ が正しい領域を用いて構成される。 領域を基準イメージに投影することによって、従来技術のシステムで見られた 欠点が克服される。個々のピクセルや正方形のような任意の範囲ではなく、全体 の領域を見ることによって、偽のマッチを識別して除去する能力が大きく向上す る。残りの領域は真のマッチ点を表すであろうため、それにより、２次元イメー ジからの正確な３次元の再構築を提供する。 本発明の１つの実施形態に従うと、付加的な２次元イメージを生成するために 付加的なカメラが用いられ得る。この付加的な２次元イメージは、マッチの可能 性のあるもののうちの特定のものを除去するために用いられ得、これは、残りの マッチしたものが共に組み合わされて３次元領域が形成される前になされ得る。 使用可能な情報が多いほど、より正確な３次元イメージが再構築される可能性が 大きくなり、結果的な３次元イメージの精度がより高くなる。 本発明の別の実施形態に従うと、この方法が実施された後に、基準イメージに おける各ピクセルは他のイメージにおけるマッチ点を有する。その情報を基にし て、各ピクセルに対するインテンシティ値と他のイメージにおけるすべてのその マッチが基準化（normalize）され、再構築される３次元イメージの精度を向上 させるためにプロセスは反復される。 本発明は従来技術に関連する多くの問題を克服し、再構築された３次元イメー ジの精度および信頼性を向上させる。本発明の方法は、計算リソースが最少化さ れ、イメージの処理に必要な時間が分単位ではなく時間単位で減少されるように して、ソフトウエアで実現され得る。更に、２次元イメージを生成するために必 要なハードウエアは、商業的に入手可能であり、比較的低価格である。本発明の 方法を実施するシステムは、数百ドルから数千ドルのオーダーで構築され得るこ とが予想される。これは、数万ドルから数十万ドルのオーダーの費用がかかる現 状の技術での３次元イメージング・システムとは対照的である。従って、本発明 は、パーソナル・コンピュータを所有する者が支払い得るコスト・レベルで２次 元イメージから３次元イメージを再構築する能力において顕著な躍進を表す。本 発明のそれら及び他の利点及び利益は、以下の好適な実施形態の説明から明らか になるであろう。 図面の簡単な説明 本発明をより容易に理解し且つ実施するために、本発明を図面と関連させて説 明する。 図１は、２つのイメージの同じ点から深度情報を抽出するための幾何学的関係 を示す。 図２は、図１の右イメージの遠点が、左イメージの近点のイメージとして誤っ て識別された場合に起こるであろうエラーを示す。 図３は、エピポーラ・ラインを示す。 図４は、本発明の方法を実施するための装置を示す。 図５は、作業空間の３次元の対象物に焦点合わせされた４つのカメラによって 生成される４つのイメージを示す。 図６は、４つのイメージのそれぞれが投影された作業空間を示す。 図７は、本発明の方法を示す高レベルのフロー・チャートである。 図８は、どのようにして１つのカメラからのイメージの点を、別のカメラから のイメージのラインに投影するかを示す。 図９は、エピポーラ・ラインに沿った値を計算するためにバイポーラ補間技術 を適用することによって得られる一連のランプ（ramp）を示す。 図１０は、領域にグループ化された点を示す。 図１１及び１２は、基準化プロセスを示す。 好適な実施形態の説明 図４は、本発明の方法を実施するための装置を示す。図４において、本発明の 装置１０はＮ個のカメラを備え得る。図４において４つのカメラ、１２、１４、 １６、１８が示されている。これらのカメラは、バー又はメンバ２０に接続され る。このバーによって、カメラ１２、１４、１６、１８は、互いに水平に配置さ れて、作業空間（workspace）２２に焦点合わせすることが可能となる。各カメ ラの他のカメラに対しての水平位置は調整可能であり、バー２０には、カメラの そのような配置を行うための適当な機械的アタッチメント（示さず）が備えられ る。典型的に、カメラ１４と１６は互いに最も近接して配置され、この２つのカ メラのうちの１つが基準カメラとして選択される。この実施形態では、カメラは 合計で約３分の２メートル離れて配置され、約０.５ｍ×０.５ｍの作業空間２２ に集中するように配置される。作業空間２２にストライプ・パターンを投影する ライト２３又は他の手段が、後に説明する理由により、提供される。ライトは通 常は基準カメラの後ろに又は隣接して配置され、図４では、説明を明瞭にするた めに別に示している。 図５に示すように、カメラ１２、１４、１６、１８は、作業空間２２に配置さ れた３次元の対象物２５のイメージ１２'、１４'、１６'、１８'をそれぞれ生成 する。カメラ１２、１４、１６、１８の各々は、作業空間２２内の対象物の僅か に異なる視界を有し、イメージ１２'、１４'、１６'、１８'の各々は３次元の対 象物２５の僅かに異なる２次元イメージである。図４に示すように、各２次元イ メージは入力電子装置２４によって捕捉される。入力電子装置２４は、カメラ１ ２、１４、１６、１８からイメージを受信できる既知のデバイスの任意の組み合 わせでよい。入力電子装置２４の正確な構成は使用されるカメラに依存する。例 えば、安価なアナログ・カメラでは、複数のアナログ／デジタル変換器、又はカ メラ１２、１４、１６、１８によって生成されるイメージを順次に処理する多重 化様式で動作する１つのアナログ／デジタル変換器が必要とされる。入力電子装 置２４の目的は、作業空間２２に含まれる３次元の対象物２５の少なくとも２つ の２次元イメージを提供することである。それらのイメージはデジタル化されて コンピュータ２６に供給される。多種の安価なカメラ１２、１４、１６、１８に 適当な入力電子装置２４を与え、コンピュータ２６に作業空間２２内の３次元の 対象物２５の少なくとも２つの２次元イメージをデジタル形式で供給でき得るこ とを、当業者は認識するであろう。 コンピュータ２６は、キーボード２８及びマウス３０のような典型的な形式の 入力装置に接続される。また、コンピュータ２６は、表示装置のような出力装置 ３２に既知の様式で接続される。好適な実施形態において、本発明の方法は、コ ンピュータ２６に記憶され且つ実行されるソフトウエアで実施される。 図５に戻る。従来のステレオ・イメージング技術は、相関（correlation）技 術、特徴マッチング（fearure-matching）、又は対象物の形状を再構築する他の 技術を用いてイメージ１２'、１４'、１６'、１８'を比較する。図６に示される ように、本発明においては、イメージ１２'、１４'、１６'、１８'を直接的に比 較する代わりに、それらを作業空間２２に再び投影（投射）する。結果として、 作業空間の各エレメント、又は「ボクセル（voxel）」は、各カメラから１つず つの、複数の値を受け取る。ボクセルの数Ｗは、再構築の所望される解像度を基 にする。エンジニアリングの目的のために有用な再構築に対しては、解像度はミ ル（mil）のオーダーである必要があり得る。整形手術の目的のために有用な再 構築に対しては、解像度はミリメートルのオーダーである必要があり得る。 対象物２５が質感のある背景に対してセットされると仮定すると、各ボクセル に見られる値に対しては３つのみの可能性がある。 １．それらが等しいか又はほぼ等しい。これは、ボクセルが或る対象物の表面 であることを意味する。 ２．それらの幾つかのものが等しいか又はほぼ等しく、他のものが大きく異な る。これは、ボクセルが対象物の表面であるが、すべてのカメラで見えないこと を意味するか、又は、類似の対象物の特徴の事故的アライメントが起こったこと を意味する。 ３．それらすべてが大きく異なる。これは、ボクセルが対象物の表面ではない ことを意味する。 上述のアプローチの問題は、計算に関する要求度が高いことである。もしＮが イメージの数であり、Ｍがイメージの解像度であり、Ｗが作業空間の解像度であ れば、各イメージを作業空間の各ボクセルに投影し、表面を見つけるために接続 された領域に対して作業空間をサーチするためには、Ｎ＊Ｍ²＊Ｗ³回のオーダー を要する。たとえば、５１２×５１２解像度の１６イメージと１０２４×１０２ ４×１０２４の作業空間は、２⁵²の更新が行われねばならないであろう。たとえ 更新が２００ＭＨｚでスーパーコンピュータを用いて行えたとしても、なおも、 ２⁵²／２００,０００,０００＝２２５１７９９８１.３７秒又は２６０６.２５日 を必要とする。これは、許容できないほど遅い。計算速度を大きく向上させるた めに多種の方法を使用できるが、本発明のアプローチは、作業空間のサーチを対 象物の表面が存在するであろう範囲に制限することである。本発明の方法は３つ のフェーズで働く。 ・イメージ・ドメイン（イメージ範囲）における計算によって、近くのカメラ を用いて可能性のある表面点を位置付する。 ・離れたカメラを用いて表面点を検証（verify）する。 ・表面領域を抽出するために不透明面強制（opaque surfaces constraint）を 適用する。 図７は本発明の方法を示す高レベルフローチャートである。図７において第１ のステップ、ステップ３４は、３次元のアーティクル（物）の必要なイメージを 捕捉するためのものである。これはカメラ１２、１４、１６、１８及び光源２３ と関連して動作する入力電子装置２４によって行われる。また、対応するフレー ムが決定されることを可能にするためにタイミング信号が供給される限り、カメ ラに取り付けたビデオテープ装置にデータを予め記録しておくこともできる。 プロセスの次のステップは、プリ-ノーマリゼーション（pre-normalization、 前基準化）ステップ３６である。イメージの各々の主要なイメージ特徴は光源２ ３によって投影されたパターンであるので、その下にあるイメージ値は、各カメ ラの見通しの聞く地点（vantage point）と独立的に概算され得る。各ピクセル での基準化されたイメージ値は、各ピクセルを投影されたパターンにおけるピー ク及び谷と比較することによって計算され得る。次に、プロセスはステップ３８ に続き、ここで可能なマッチ（マッチである可能性のもの）が決定される。 従来技術の方法では、マッチング点は、図３に示されたタイプのエピポーラ・ ラインに沿ってサーチすることによって発見される。「正しい」マッチは、その ラインに沿って関数を最小化することによって見つけられる。このアプローチの 問題は、たとえ「正しい選択」を行うために従来技術で見つけられた方法を用い ても、偽のマッチ（誤ったマッチ）がなおも見つけられ、それらのエラーを除去 するために更なる処理が必要とされることである。この付加的な処理によって、 多くの推定がもたらされ、これによって信頼性が低下し、計算時間が増加する。 従来技術のアプローチの基本的問題は、それらがすべてイメージに関して排他的 に集中していることである。一般的に、イメージを見るこ及びイメージのドメイ ンを考えることによって純粋にピクセルに対する正しいマッチを決定する方法は ない。 図８において、カメラ１６が基準カメラであり、イメージ１６'が基準イメー ジであると仮定する。パースペクティブ・プロジェクション（投影）の下では、 イメージ１６'からの各ピクセルＰはイメージ１４'のラインＬ上に投影する。こ れは、深度が未知であるためであり、ピクセルＰに対してマッチするピクセルは ラインＬに沿ったどこかにあるためである。カメラ１４と１６のように互いに物 理的に近接したカメラについては、イメージ１４'においてラインＬが横切るピ クセルの数は、作業空間において点４２と４４によってライン・セグメントが横 切るボクセルの数よりも少ない。これは、カメラ１４と１６の視点及び光学軸が 類似であるからであり、それによって、基準カメラ１６から投影されたラインＬ がカメラ１４の視野において大きく短縮されるからである。結果として、作業空 間においてではなく、イメージ空間においてサーチすることによって、ラインＬ に沿ってピクセルＰに対してのマッチするピクセルを捜すことによって、時間を 節約することができる。近くのカメラに対するエピポーラ・ラインが比較的短い 傾向があるというのみではなく、近い視点からは一般に対象物が大いに類似して 見え、そのため、視点の変更に起因する外観のシフトの結果として真のマッチが 拒絶されないであろう可能性が増するので、ステップ３８で使用するためにカメ ラ１４と１８が選択される。 ラインＬは図３に示したタイプのエピポーラ・ラインである。イメージ１４' の個別性のため、その値は補間（interpolation）によって計算されなければな らない。バイリニア（bilinear、双線形）補間のような、簡単ではあるが有効な 補間の技術を用いると、ラインＬに沿って計算された値は、図９に示すような一 連のリニア（線形）のランプのようになる。高次の補間を用いることができ、こ れはＬの構造を幾らか複雑にするが、以下に説明する性能は同じオーダーにとど まる。 イメージ空間は、図９に示すＬのリニアのランプと基準イメージ１６'からの ピクセルＰに対する値でのコンスタントのラインとの交差点を見つけることによ りサーチされる。それら交差点の半分は、Ｐに対する値との交差点でグラジエン ト（gradient）の符号（サイン）を含むことによって除去できる。その結果はピ クセルＰに対する可能なマッチ点の集合体であり、それらは次に偽のマッチを除 くために検証（verify）されねばならない。この実施形態では、典型的に基準イ メージ１６'における各ピクセルに対して４つの偽のマッチが見つけられる。 次に基準ピクセルと可能なマッチ・ピクセルとを通る光線は３次元空間に投影 され、その交差点は可能なマッチの３次元座標である。各基準ピクセルに対する すべての可能なマッチのリストが生成され、これがステップ３８の出力である。 ステップ３８を表す擬似コードがテーブルＮｏ．１に見られる。 テーブルＮｏ.１ インテンシティ(intensity)（ｃ，ｐ）は、位置「ｐ」でのカメラｃに対して のインテンシティ（ピクセル，値）である。 可能なマッチ（マッチである可能性のあるもの）の位置を見つけるためのプロ セスは、イメージ１４'上のラインＬの投影（プロジェクション）におけるピク セルの数に比例する時間で行われることができる。ステップ３８を行うために必 要な時間はＣ＊Ｎ²＊Ｔのオーダーであり、ここにおいて、Ｃはローカル・セッ トに含まれるカメラの数である（図８の例では２である）。Ｎは、ユーザの要求 するイメージの解像度であり、ＴはラインＬがその上にマップするピクセルの数 である。 図７に戻る。プロセスの次のステップ、ステップ４６は、ステップ３８で見つ けたマッチを検証してマッチの精度を向上させるためのものである。これは、基 準イメージからのピクセルの各々に対するイメージ値を、他のカメラ１２、１８ により生成された対応するイメージ値と比較することにより達成される。他のイ メージにおいての基準ピクセルがマップする、エピポーラ・ラインに沿ってサー チが行われる。しかしながら、それぞれの可能なマッチの両側における固定の短 い距離にサーチを制限することによって、計算時間が減少される。他のイメージ においてマッチする点が見つけられると、マッチ点のすべてを共に平均すること によって、予測される深度の位置が得られる。マッチ点は、基準カメラと各カメ ラの間のベースライン距離の長さに従って重みを付けられることができ、最も遠 く離れたカメラが最も大きい重みをもつ。マッチが見つからなければ、イメージ １４'において見つけられた可能なマッチは拒絶される。ステップ４６の出力は 可能なマッチの改善された集合である。 ステップ４６の実行において、イメージの各点はすべてのカメラにおいて同じ 外観を有するものと仮定される。これは、ランバーシアン・オブジェクツ・アサ ンプション（Lambertian object assumption、ランバート的対象物仮定）と呼ば れる（本質的に、すべての世界の表面は平らな壁の塗装のように僅かに荒れてい ると仮定し、これはステレオ・ビジョンにおいてほぼ普遍的な仮定である）。最 近、対象物上のハイライトを検出して考慮から除くことにより、反射する（光っ た）対象物の場合を含むように、ステレオ・ビジョンを拡張することが可能であ ることが示されている。対象物の表面の広い範囲の認識を可能とするように、こ のアプローチが本発明の方法に適用され得ることが考慮される。 現在の実施形態においては、１５ミリメートルのサーチ距離が用いられる。典 型的に、偽のマッチが少しだけ減少される（基準ピクセルあたり４又は５の偽の マッチから、基準ピクセルあたり３から４の偽のマッチへ）が、データの精度は 大きく向上する。ステップ４６に対する時間はＤ＊Ｎ₂＊Ｕのオーダーであり、 Ｄは距離セットにおけるカメラの数（図４に示す実施形態では２）であり、Ｎは イメージの解像度であり、Ｕは最初のステップから残っているピクセルに対する 可能なマッチの数である。ステップ４６を行うための擬似コードをテーブル２に 示す。 テーブルＮｏ.２ 検証ステップの始めに、基準イメージにおける各ピクセルｘに対する可能なマ ッチのリストが生成されている。そのリストはPoints_list(x)と呼ばれる。 テーブル２に示した擬似コードは検証のために２つのカメラ、カメラ１２及び １８を使用するものと仮定することに留意されたい。一般の場合は、検証ステッ プ２６は、更なるに次元イメージを供給するために更なるカメラが使用可能であ るならば、必要なだけ繰り返されるであろう。 次のステップ、ステップ４８は、点を領域に接続する（つなぐ）ことである。 もしスライスがこの時に一定の高さで作業空間を通じて作られるならば、点のグ ループは図１０に示すように見えるであろう。ここまでのフィルタリンング・ス テップでは実際の対象物の面から真の点を除去しておらず、また、すべての偽の 点も除去されていない。これは、真の表面からの深度オフセットでの「エコー」 が見られる反復する質感の場合には、真実である。真の表面の不連続部及び対象 物の境界もまた視覚可能である。真の表面を識別するために、その光景における 対象物は不透明であるという仮定が適用される。ここで、どの点が同じ不透明の 領域に属し得るかが判定される。これは、基準イメージ１６'における近くにあ るピクセルを考慮することにより行われる。近くにある３次元の点に対するマッ チは、すべてのカメラからのすべてのイメージにおいて、もし、それらの投影が イメージにおいて同じ順で起こるならば、及びそれらの投影が何れかのイメージ において決して遠く離れすぎないならば、同じ領域に属し得る。それらが深度に おいておおよそ同じ位置にあるという要求もまた課される。図１０において、こ れらの基準に適合する点が楕円で囲まれている。これらの基準の下で等価のクラ スの点を判定することによって、３次元空間における点の接続された領域が抽出 される。現在の実施形態において、この時点では典型的に、数百の領域があり、 最大のものは数万の点を有する。ステップ４８を行うための擬似コードがテーブ ルＮｏ.３に示されている。 テーブルＮｏ.３ 接続ステップは、前のステップから可能な良い点のリストを取り、領域の集合 を生成する。上述のように、以下の擬似コードは、２つの検証カメラ１２及び１ ８を使用するために設計されている。一般の場合、ステップ５におけるテストが すべての検証カメラに対して繰り返されるであろう。 ステップ５２において、偽の領域（図１０の５１）が除去される。イメージか らの最大の領域が抽出され、それが関連する基準ピクセルがマークされる。次に 大きい領域が抽出され、該次に大きい領域からの基準ピクセルが、前の領域から のピクセルとかなり多く重なるか（オーバーラップするか）についての判定が行 われる。そうであるならば、該次に大きい領域は除去される。そうでない場合、 それは、良い領域（図１０の５０）のリストに付加される。このプロセスは、領 域のサイズがかなり小さくなるまで反復される。現在の実施形態においては、領 域サイズの約９０％のオーバーラップをチェックする。最小の領域サイズは約１ ０００点である。 ステップ５２における仮定は、表面が不透明であるということである。前のス テップで真の点を全く除去していないので、残されるエラーは誤ったエコーのみ である。それらのエコーのサイズは、ステップ４６とステップ４８とに関連して 使用するカメラをより多く含むことによって、減少させることができる。十分な 数のカメラを用いると、すべての誤ったエコーが表面の点の何れよりも小さくな る。残りの誤ったエコーはステップ５２で除去される。 偽の領域を除去するステップ５２を示す擬似コードがテーブルＮｏ.４に示さ れる。 テーブルＮｏ.４ ステップ５２の終わりでは、殆どのイメージに対する深度の値が概算されてい る。幾らかのイメージ・ピクセルが深度値を有さないことも可能であり、なぜな ら、それらは近い対象物の境界やそれと同様のものであるからである。更に、本 発明の方法はマッチング・プロセスに関して大変伝統的であるので、概算される 深度値がない多くの点が存在する。しかしながら、表面の多くに対する真の深度 値が判定されているので、補間を基にする方法を用いて多くの点の位置付けを行 う（位置を見つける）ためにその情報を用いることができる。 プロセスの最後のステップはポスト-ノーマリゼーション（post-normalizatio n、後基準化）ステップ５４である。この時点では、基準イメージにおける多数 のイメージ点に対するマッチが計算されているので、各マッチの投影のまわりの イメージ値の平均及び標準偏差を計算することにより、その下にある真のイメー ジ値をより正確に概算することができる。すべてのイメージにおけるイメージ値 は、平均及び標準偏差を均一化するために調節される。このプロセスは図１１及 び図１２にグラフで示されており、図１１は第１の反復を示し、図１２は第２の 反復を示す。その後、プロセスはステップ３８に戻ることによって繰り返され得 る。ステップ３８に戻ると、調節されたイメージ値を用いて、より多くのマッチ 点が見つけられ、マッチがより正確に見つけられる。現在、ポイント-ノーマリ ゼーション（点基準化）は１回のみ行われ、プロセスを通じて第２の反復がなさ れると、プロセスはステップ５２で終了し、そこで偽の領域が除去される。基準 化のためのウインドウはかなり小さい（３×５ピクセル）。なぜなら、パターン からのインテンシティの変化（variation）がイメージにおける他の変化を支配 することが知られているからである。 本発明は、この技術での幾つかの実質的な進歩を表す。まず、点を領域に接続 し、領域に基づいて判断を行うことにより、高い忠実度で元の対象物の３次元イ メージを再生成する能力が大きく向上する。更に、本方法における幾つかの位置 で、必要とされる計算時間を減少させるためのステップが行われる。例えば、互 いに近接した２つのカメラから始め、作業空間ではなくイメージ空間におけるエ ピポーラ・ラインをサーチすることによって、計算時間が減少される。その後、 基準カメラから離れたカメラからのイメージ、従って、より長いエピポーラ・ラ インを有するイメージに関して行われなければならないサーチの量を制限するた めに、その情報が用いられる。この技術は、必要とされる計算リソース（資源） を大きく減らし、それによって、本発明の方法が商業的に入手可能なハードウエ アで、分のオーダーの時間フレームで、実施されることを可能にする。 当業者は本発明の多くの改造及び変形が可能であることを認識するであろう。 例えば、３次元空間における可能なマッチ及び領域の位置を見つけるステップは 上述のように行う必要はない。本発明の方法は、可能なマッチを見つける他の方 法とともに同じように良く動作する本発明の他の方法とともに同じように良く動 作する。すべてのそのような改造及び変形は上述り説明及び特許請求の範囲の精 神及び範囲に含まれることを意図する。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ， ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＬＳ，ＭＷ，ＳＤ，Ｓ Ｚ，ＵＧ)，ＵＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ ，ＲＵ，ＴＪ，ＴＭ)，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ ，ＢＡ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ， ＣＵ，ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，Ｇ Ｅ，ＨＵ，ＩＬ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ ，ＫＺ，ＬＣ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ， ＭＤ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，Ｐ Ｌ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ ，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＵＡ，ＵＧ，ＵＺ，ＶＮ

Claims (1)

1. 【特許請求の範囲】 １． 少なくとも２つの２次元イメージから３次元イメージを構築する方法に おいて、 イメージのうちの１つを基準イメージとして選択するステップと、 他方のイメージにおける１又はそれより多くの点を、前記基準イメージにおけ る各点に対する可能なマッチ点として識別するステップと、 マッチする点の投影を３次元領域にグループ化するステップと、 偽の領域を識別するために前記領域を前記基準イメージに投影するステップと 、 前記偽の領域を除去するステップと、 偽の領域ではない前記領域を付加することによって３次元イメージを構築する ステップと を備える方法。 ２． 請求項１に記載の方法において、前記イメージにおける前記点を基準化 し、前記方法を繰り返すステップを含む方法。 ３． 請求項１に記載の方法において、前記の１又はそれより多くの可能なマ ッチ点を識別するステップは、それに対してマッチが捜される前記基準イメージ における点に対応する前記他方のイメージにおけるエピポーラ・ラインに沿って サーチするステップを含む、方法。 ４． 請求項１に記載の方法において、前記基準イメージにおける点を通じて 延びる光線が前記可能なマッチ点を通じて延びる光線と交差する、作業空間にお ける第１の点を識別するステップを更に備える方法。 ５． 請求項４に記載の方法において、第３の２次元のイメージが使用可能で あり、前記第３のイメージにおける１又はそれより多くの点を、前記基準イメー ジにおける各点に対する可能なマッチ点として識別するステップと、前記基準イ メージにおける点を通じて延びる光線が前記可能なマッチ点を通じて延びる光線 と交差する、作業空間における第２の点を識別するステップと、前記第１の点と 前記第２の点を組み合わせるステップとを更に備える方法。 ６． 請求項５に記載の方法において、前記の前記第３のイメージにおける１ 又はそれより多くの点を識別するステップは、前記他方のイメージからのマッチ 点によって制限されるサーチ範囲において、それに対してマッチが捜される前記 基準イメージにおける点に対応する前記第３のイメージにおけるエピポーラ・ラ インに沿ってサーチするステップを含む、方法。 ７． 請求項６に記載の方法において、前記サーチ範囲は、前記第３のイメー ジの前記エピポーラ・ライン上の前記他方のイメージのマッチ点の位置の両側の 約１５ｍｍに制限される、方法。 ８． 請求項１に記載の方法において、前記のマッチする点の投影を領域にグ ループ化するステップは、前記マッチする点の投影をそれらの間隔および各イメ ージにおける順に従ってグループ化することを含む、方法。 ９． 請求項８に記載の方法において、前記のグループ化するステップは、約 ５ｍｍの間隔に従ってグループ化することを含む、方法。 １０． 請求項８に記載の方法において、前記のグループ化するステップは、 前記マッチする点の前記投影をそれらの個々の深度に従ってグループ化すること を含む、方法。 １１． 請求項１に記載の方法において、前記の前記偽の領域を識別するステ ップは、（ｉ）最大の領域を選択し、前記最大の領域によって明らかにされる前 記基準イメージ上の点をマークするステップと、（ii）次に大きい領域を選択し 、前記次に大きい領域によって明らかにされる前記基準イメージ上の点をマーク するステップと、（iii）前記のマークされた点の間のオーバーラップの度合い が所定のスレッショルドよりも上であるならば、前記次に大きい領域を偽の領域 として識別するステップと、（iv）所定のサイズよりも大きいすべての領域が選 択されるまでステップ（ii）からステップ（iv）を繰り返すステップとを含む、 方法。 １２． 請求項１１に記載の方法において、前記の前記次に大きい領域を偽の 領域として識別するステップは、もしオーバーラップの度合いが少なくとも約１ ０パーセントであるならば、前記次に大きい領域を偽の領域として識別すること を含む、方法。 １３． 請求項１１に記載の方法において、前記ステップ（ii）から前記ステ ップ（iv）は、約１０００点よりも多くの点を有するすべての領域が選択される まで繰り返される、方法。 １４． 複数の２次元イメージから３次元イメージを構築する方法において、 イメージのうちの１つを基準イメージとして選択するステップと、 第２のイメージを選択するステップと、 前記第２のイメージにおける１又はそれより多くの点を、前記基準イメージに おける各点に対する可能なマッチ点として識別するステップと、 前記可能なマッチ点を検証するために前記複数のイメージの残りのものを用い るステップと、 前記の検証したマッチ点の投影を３次元領域にグループ化するステップと、 偽の領域を識別して除去するために前記領域を前記基準イメージに投影するス テップと、 偽の領域ではない前記領域を付加することによって３次元イメージを構築する ステップと を備える方法。 １５． 請求項１４に記載の方法において、前記の第２のイメージを選択する ステップは、前記基準イメージに対して最も短いベースラインを有するイメージ を選択するステップを含む、方法。 １６． 請求項１４に記載の方法において、前記の前記可能なマッチ点を検証 するために前記複数のイメージの残りのものを用いるステップは、前記マッチ点 の範囲における前記の残りのイメージの各々におけるエピポーラ・ラインをサー チするステップと、サーチされる前記エピポーラ・ラインの部分に沿って更なる マッチが発見できない何れのマッチ点も除くステップとを含む、方法。 １７． 請求項１４に記載の方法において、前記イメージにおける前記点を基 準化するステップと、前記方法を繰り返すステップとを含む方法。 １８． 請求項１４に記載の方法において、３次元の対象物にパターンを投影 するステップと、前記複数の２次元イメージを生成するステップと、前記３次元 対象物の前記複数の２次元イメージを生成するステップとを更に備える方法。 １９． 請求項１８に記載の方法において、前記複数のイメージのインテンシ ティを基準化するために前記２次元イメージの各々において見つけられる前記パ ターンからの情報を用いるステップを更に備える方法。