JP2009530701A - 深度マップを画像から判定する方法、深度マップを判定する装置 - Google Patents

Abstract

ウィンドウ・ベースのマッチングは、別々の向きから得られる画像から深度マップを判定するために使用される。固定マッチング・ウィンドウの組が、深度を判定する画像の点に対して使用される。マッチング・ウィンドウの組は、画像の点周りの画素のフットプリントを包含し、フットプリント（ＦＰ）の画素が属するマッチング・ウィンドウの平均数（Ｏ）は、フットプリントにおける画素数を１５で除算した数に１を加えた数未満（Ｏ＜ＦＰ／１５＋１）、好ましくは、フットプリントにおける画素数を２５で除算した数に１を加えた数未満（Ｏ＜ＦＰ／２５＋１）である。

Description

本発明は、画像の点に対するウィンドウ・ベースのマッチングを使用して、別々の向きから得られる画像から深度マップを判定する方法に関する。

本発明は、画像の点に対するウィンドウ・ベースのマッチングを使用して、別々の向きから得られる画像から深度マップを判定する装置にも関する。

いくつかのアプリケーションの場合、深度マップを画像から判定することが望ましい。前述のアプリケーションの例には、対話式で制御可能な向きから視たシーンの画像の計算を可能にするシステム、画像圧縮、検査等がある。ステレオ画像から深度マップを回復する作業は多くの場合、３Ｄ表示、製造時の品質管理、自律ナビゲーションや物体認識などの広範囲にわたるアプリケーションに非常に重要である。本明細書及び特許請求の範囲では、画像内の点の深度は、視点と、上記点を通り、カメラの光軸に垂直の平面との間の距離を表す。

カメラの視点を第１の視点から第２の視点に移動させると、画像点の深度は画像点の位置の平行移動の量から判定することが可能である。画像が点投影によって得られた場合、平行移動は、カメラの変位の量に比例し、画像の一部の深度に反比例する。

平行移動を測定するために、カメラの第１の向きから得られる第１の画像内の画素周りのウィンドウ内の画素値が、第２の向きから得られる第２の画像内の画素周りのウィンドウ内の画素値と比較される。マッチングには通常、マッチング・ウィンドウ内の画素の画素値間の差の総計を求めることが関係する。

ウィンドウ・ベースのマッチング手法は、共通の問題（すなわち、バウンダリ・オーバリーチ）を共有する。画像内の境界近傍では、マッチング・ウィンドウを使用したウィンドウ・ベースの手法により、問題に対する対応がなされる。回復されたオブジェクト境界は多くの場合、画像内で変位する。

適応型ウィンドウを使用することも提案されている。しかし、適応型ウィンドウの使用には通常、ウィンドウを適応させるための非常に複雑なアルゴリズムが必要である。

バウンダリ・オーバリーチの問題を軽減するための手法は、Ｍａｓａｔｏｓｈｉ Ｏｋｕｔｏｍｉらによる、「Ａ Ｓｉｍｐｌｅ Ｓｔｅｒｅｏ Ａｌｇｏｒｉｔｈｍ ｔｏ Ｒｅｃｏｖｅｒ Ｐｒｅｃｉｓｅ Ｏｂｊｅｃｔ Ｂｏｕｎｄａｒｉｅｓ ａｎｄ Ｓｍｏｏｔｈ Ｓｕｒｆａｃｅｓ （Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ ２００１， ＣＶＰＲ２００１， Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００１ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｏｌｕｍｅ ２．， ２００１， ｐａｇｅ ＩＩ−１３８乃至ＩＩ−１４２， ｖｏｌ． ２）」と題する論文に開示されている。

別の手法は、Ｇｅｉｇｅｒ ｅｔ ａｌによる「Ｏｃｃｕｌｕｓｉｏｎｓ ａｎｄ ｂｉｎｏｃｕｌａｒ ｓｔｅｒｅｏ， Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ， Ｎｏｒｗｅｌｌ， ＵＳ， ｖｏｌ． １４， ｎｏ． ３， １ Ａｐｒｉｌ １９９５， ｐａｇｅｓ ２１１−２２６」により、知られている。

Ｇｅｉｇｅｒ ｅｔ ａｌ記載の手法は、単一対の矩形マッチング・ウィンドウを使用する。

Ｏｋｕｔｏｍｉ ｅｔ ａｌによる論文によって知られている手法では、マッチングが行われる画像の点毎に、関心点の位置がウィンドウの点全てにわたって走査されるマッチング・ウィンドウが使用される。マッチング・ウィンドウがオブジェクト境界に及ばないようにマッチング・ウィンドウが関心画素の周りに非対称に設定された場合、バウンダリ・オーバリーチは生じない。関心画素が、マッチング・ウィンドウの組全体にわたって走査される。マッチング・ウィンドウの組全体が、関心画素周りのフットプリントに及ぶ。

前述の既知の手法により、バウンダリ・オーバリーチの問題に対する解決策が用意される。しかし、前述の解決策により、大量の計算が必要になる。更に、別の問題が生じる。平滑な視差面が破壊され、多くの段階的な方形が前述の平滑な視差面においてみられる。平滑な視差面における問題は、境界検出法を実現し、境界領域を非境界領域と違ったふうに処理することにより、既知の手法において対処される。

しかし、既知の手法は、大量の計算能力及び多少複雑なアルゴリズムを必要とする。

本発明の目的はとりわけ、深度の比較的信頼度及び正確性の高い推定を供給しながら、比較的少ない計算能力を必要とする方法を提供する。

本発明によれば、固定マッチング・ウィンドウの組が画像の点に対して使用され、マッチング・ウィンドウの組は、画像の点周りの画素のフットプリントに及び、フットプリントの画素が属するウィンドウの平均数は、フットプリント内の画素数を１５で除算した数に１を加えた数未満であり、別々の向きのマッチング・ウィンドウが使用される。

Ｏｋｕｔｏｍｉ ｅｔ ａｌによる論文によって知られている手法は、多少大きなウィンドウ及び大きなマッチング・ウィンドウ組を使用する。前述の既知の手法において提案された大きなウィンドウ組を使用すると、オーバリーチの問題が軽減されるが、大量の計算能力が必要になる。フットプリント、すなわち、少なくとも１つのマッチング・ウィンドウに属する関心画素の周り、又は上記関心画素の近くの画素は全て、大きく、更に、各画素が属する平均ウィンドウ数は、画素数を１２．５で除算した数に１を加えた数にほぼ等しい。このことは、フットプリント内の各画素が多数のウィンドウに属するという状態につながる。フットプリント内の画素は最大２０乃至２５個のウィンドウに属する。マッチング・ウィンドウの重なりは大きい。これは、２つの不利な影響を及ぼす。すなわち、計算の数が多く、エラーが伝播し、それによって、従来技術文献に記載された影響につながる。

Ｇｅｉｇｅｒ ｅｔ ａｌによる論文によって知られている手法は、単一対の矩形マッチング・ウィンドウを使用する。このことにより、制限された計算能力しか要求されないとされる手法に対する対処がなされるが、最適な結果に至らず、後処理が施される。

本願の発明者は、ウィンドウ・ベースの手法の場合、ウィンドウの適切な選択が重要であることを認識した。使用されるマッチング・ウィンドウのサイズが大きい場合、これは、境界が不正確であり、細部が喪失された、ぼやけた深度マップをもたらし得る。好適であり、計算能力を削減する一方で、より小さなウィンドウを使用すれば、雑音をこうむりやすい方法につながる。マッチング・ウィンドウの重なり及びその相互の向きも重要である。

本発明による方法では、固定されたマッチング・ウィンドウの組が使用される。固定ウィンドウを使用すれば、適用型ウィンドウに関連した問題がなくなる。

マッチング・ウィンドウの組により、関心画素周りのフットプリントが定められる。平均的な重なりは小さく、好ましくは、従来技術手法の少なくとも２分の１未満の大きさである。意外にも、この場合、「少ないほど良い」ということがあてはまることが分かっている。既知の手法の少なくとも２分の１以下にマッチング・ウィンドウの重なりの数を削減することにより、エラー伝播の問題も軽減する一方で、計算の数を削減することが可能である。ウィンドウは比較的小さくし、それにより、より多くの計算に対する必要性を緩和することが可能である。

方法は好ましくは、別々の向き（好ましくは、互いにほぼ垂直である向き）を備えたマッチング・ウィンドウの組を使用する。別々の向きのマッチング・ウィンドウを使用するので、マッチング・ウィンドウの別々の向きが理由で重なりを小さく保つことが可能な状態で、深度マップにおける画素毎に、いくつかの潜在的なマッチ（及び、よって視差値）がもたらされる。マッチング・ウィンドウの向きは、マッチング・ウィンドウの長軸又は短軸で表される。

マッチング・ウィンドウの位置決めの前述の選択が理由で、バウンダリ・オーバリーチが生じない一マッチング・ウィンドウが常に存在するか、又は少なくとも、上記一マッチング・ウィンドウが常に存在する可能性が非常に高いことになる。この冗長度により、この冗長度がなければ失われることがあり得る細部をより好適に回復することが可能になり、最終的な視差推定における信頼度がより高くなることも可能になる。マッチング・ウィンドウのサイズ、及びマッチング・ウィンドウの数は大きくなくてよいので、計算量的負担は低く、作業は容易に並列化される。ウィンドウは比較的小さな重なりしか有していないので、従来技術の問題（すなわち、平滑な視差面が損なわれること）が生じるのはずっと少なくなる。よって、既知の手法と比較してずっと単純な計算を使用すれば、同等に好適又はより好適な結果を得ることが可能である。なお、本発明は、従来技術文献に開示されたマッチング・ウィンドウのサイズを単純に削減することを意味するものでない。重要なことは、平均的な重なりが削減されるということであり。好ましくは、別々の向きのマッチング・ウィンドウがいくつか使用されるということである。別々の向きのマッチング・ウィンドウの前述の使用は、従来技術文献には開示されていない。従来技術文献では、同一の方形形状のウィンドウが使用されている。

好ましくは、フットプリントの画素が属する平均ウィンドウ数は、フットプリント内の画素の数を２５で除算した数に１を加えた数未満である。重なりはその場合、従来技術の少なくとも２分の１以下の大きさである。

好ましくは、フットプリントの画素が属するウィンドウの平均数は、フットプリント内の画素の数を５０で除算した数に１を加えた数未満である。

小さいウィンドウ（すなわち、２０個未満の画素、好ましくは１０個未満の画素を含むウィンドウ）の使用が好ましい。

ウィンドウのサイズは比較的小さくすることができるので、細部を捕捉することが可能である。

好ましくは、マッチング・ウィンドウは、向きが垂直であるウィンドウの向きに平行のエッジを備える。

好ましい実施例では、マッチング・ウィンドウの数は４個であり、マッチング・ウィンドウは、十文字形の形態のフットプリントを形成する。十文字形は、単純な配置であり、これは、好適な結果をもたらすことが分かっている。

別の好ましい実施例では、マッチング・ウィンドウの数は８個であり、ウィンドウは、フォアサム（４つで１組のもの）が２個あり、一方のフォアサムは、他方のフォアサムにおけるウィンドウの左側バージョン又は右側バージョンであり、それぞれが十文字形を形成している。マッチング・ウィンドウの一方のフォアサムを使用すると、左から右への偏り、又は右から左への偏りがわずかに生じ得る。２つのフォアサムを使用することにより、このバイアスをなくすことが可能である。

別の実施例では、マッチング・ウィンドウはほぼ三角形である。

好ましい実施例では、各ウィンドウはｎ１^＊ｎ２個の画素を有し、ここで、ｎ１≧２ｎ２である。

好ましくは、ｎ１は１、２又は３であり、最も好ましくは、２及びｎ２は５乃至８である。

本発明の前述及び他の効果的な局面は、以下の図面を使用して更に詳細に説明するものとする。

図は一律の縮尺に従わずに描いている。一般に、同じ構成部分は、図中の同じ参照符号で表す。

図１は、画像１０の一部の幾何形状、及び２つの向き１２ａ、１２ｂを示す。画像の一部は例えば、画像内の個人、又は何れかの物体であり得る。本発明は、画像の深度マップを提供する方法に関する。深度マップは、ｚ値（すなわち、深度値）を物体点に帰属させるものとしてみることが可能である。画像１０の一部を含むシーンの画像を、別々の向き１２ａ、ｂからの点投影を使用して得ると、画像の一部の上にある点１４、１５が画像において目に見える位置は、点１４、１５の投影１６ａ、ｂ、１７ａ、ｂである。投影は、線１９ａ乃至１９ｄを点１４，１５から向き１２ａ、ｂを通って画像平面まで引くことによって示すことが可能である。基本原則を説明するために、画像平面１８に平行の平面において向き１２ａ、ｂが選択されているが、本発明は、向き１２ａ、ｂの前述の選択に限定されるものでない。前述の線１９ａ乃至ｄと画像平面１８との間の交差は、画像１０の一部の点１４、１５が画像において目に見える位置を示す。

視点１２ａ、１２ｂが変わると、画像の一部における点１４、１５が画像平面１８において目に見える位置１６ａ、ｂ、１７ａ、ｂが平行移動する。この平行移動は、視点と上記点との間の深度「ｚ」に反比例し、視点の位置における変動の量に比例する。その結果、向き１２ａ、ｂからの異なる深度「ｚ」を有する画像１０の一部の点１４、１５毎に平行移動は異なる。

図２は、画像の一部が目に見える領域２２を含む画像２０を示す。画像２０には、平行移動ベクトル２３ａ、ｂ、２５ａ、ｂを示している。平行移動ベクトル２３ａ、ｂ、２５ａ、ｂにより、画像２０において画像の一部の点が目に見える位置が視点の移動に応じて平行移動される。平行移動ベクトル２５ａ、ｂは、視点からより遠くにある点の場合よりも、視点により近い画像の一部の点の場合、より大きくなる。点全ての深度が同じ線２６に沿って、平行移動は同じになる。

線２６に沿った軸及びその線に垂直の軸を有する座標系を使用すると、点が目に見える位置の平行移動「Ｄ」の振幅はＡ＋Ｂｕになる。ここで、ｕは、線２６に垂直の軸に沿って点が目に見える位置の座標である。平行移動の方向は視点の移動の方向と逆である。パラメータ「Ａ」は、ｕ＝０において深度「Ｚ0」の逆数に比例する。Ａ＝ｃ／Ｚ０であり、「Ｂ」はその深度に同様に比例し、画像の一部の傾き「ｓ」は視線方向に対して垂直である。すなわち、Ｂ＝ｃ^＊ｓ／Ｚ０である（ｃは、視点の変位、焦点距離、及び画像のスケールに比例する比例定数である）。図１及び図２は、２つのカメラを使用する状態を示す。深度マップを判定するために、３つ以上のカメラを使用することができる。３つ以上のカメラを使用すると、精度が向上し、フォアグラウンドにおける物体によるオクルージョンをバックグランド・オブジェクトが受ける可能性は減少する。

図３は、画像、又は少なくとも画像の一部の深度マップを作成する方法のフローチャートを略示する。

フローチャートの第１の工程３１及び第２の工程３２では、カメラ光学系は、第１の視点及び第２の視点それぞれに配置され、第１の視点及び第２の視点それぞれから第１の画像及び第２の画像が得られる。

フローチャートの第３の工程３３では、第１の画像における画素が選択される。第４の工程３４では、画素に対して最善のマッチが、画像間でマッチング・ウィンドウを使用して求められる。

フローチャートの工程３５では、工程３４の結果（すなわち、ウィンドウの最善のマッチ）を使用してｚ値を上記画素に帰属させる。最善のマッチを求め、それにより、ｚ値を設定する方法は、最小ＳＳＳＤが算出される上記引用論文記載の算出手法に限定されないが、前述の手法であり得る、マッチング・ウィンドウを使用して最善のｚ値を判定する何れかの方法であり得る。本発明による方法は、マッチング・ウィンドウを使用した方法全てに共通するバウンダリ・オーバリーチの問題を軽減するためのマッチング・ウィンドウの選択に関する。

前述の工程は、深度マップを得るために画像内の画素の全て又は一部について繰り返される。

図４は、引用された従来技術論文に開示されたマッチング・ウィンドウの組を示す。２５個のウィンドウが使用され、各ウィンドウは２５個の画素を含む。「関心点」と呼ばれる、ｚ値が求められる画素４１は、黒色方形で表す。５^＊５の画素の標準マッチング・ウィンドウが使用され、関心画素が、標準ウィンドウの点全てにわたって走査される。これにより、２５個のマッチング・ウィンドウが与えられる。図４では、前述の２５個のマッチング・ウィンドウは、灰色の方形の５^＊５の領域によって表す。大量の算出を行わなければならない。２５個のマッチング・ウィンドウは、関心画素周りの、関心画素を含む９^＊９＝８１個の画素のフットプリントに及ぶ。底部領域４３は、マッチング・ウィンドウのうちの少なくとも２つに共通した、９^＊９個の画素のより大きな領域内の画素を示す。このより大きな領域は、合計２５個のマッチング・ウィンドウの組のフットプリントである。フットプリントの画素毎に、各画素が共通であるウィンドウの数が示される。大半の画素は、３つ以上の（最大２０個の）マッチング・ウィンドウに共通している。特に、垂直軸及び水平軸に沿って数が多い。本願発明者は、重要なパラメータが、画素が共通画素である平均ウィンドウ数であることが分かった。この平均数は、フットプリントにおける数全てを加算し、フットプリントにおける画素の数で和を除算することにより、算出することが可能である。従来技術は、５^＊５個の画素のウィンドウを備えた９^＊９個の画素のフットプリントを一例として表す。従来技術はこの手法の一般化を開示していないが、より大きなフットプリント、又はより小さなフットプリント（例えば、１１^＊１１のフットプリント又は７^＊７のフットプリント）の場合、同じ手法を想定し得る。その場合、ウィンドウはそれぞれ、６^＊６個の画素及び４^＊４個の画素になる。既知の手法は、関心画素が標準ウィンドウの画素全てにわたって走査され、よって、４^＊４の標準ウィンドウで始めた場合、７^＊７のフットプリントに及ぶ１６個のマッチング・ウィンドウが存在することになり、６^＊６の標準ウィンドウで始めた場合、１１^＊１１のフットプリントに及ぶ３６個のマッチング・ウィンドウが存在することになる。

走査する対象の、各画素が共通であるウィンドウの平均数は、従来技術の構成の場合、以下のように算出される。

各ウィンドウ（図４の最上部における灰色領域）は、ｍ^＊ｍ個の画素を有し、この例ではｍ＝５である。ウィンドウの数もｍ^＊ｍである。関心画素が、標準ウィンドウの画素全てにわたって走査される。よって、完全なマッチング・ウィンドウの組が灰色である画素の合計数はｍ^＊ｍ^＊ｍ^＊ｍ＝ｍ^４である。ウィンドウの組全てのフットプリント（すなわち、少なくとも一ウィンドウの一部を形成する画素の組はｎ^＊ｎであり、この例ではｎ＝９である。実際に、従来技術の構成では、ｎ＝２ｍ−１（又は、ｍ＝０．５（n＋１））である。

よって、画素毎の平均ウィンドウ数はｍ^４／ｎ^２である。フットプリントの各画素は、少なくとも１つのウィンドウの一部である。画素が２つ以上のウィンドウの一部を形成した場合、これは問題を生じ得る。以下に説明する重要な値は、画素毎のウィンドウの平均数である。

本発明の概念において、この数は平均重なり数Ｏと呼ばれる。

式では、Ｏ＝ｍ^４／ｎ^２である。

ｎ＝２ｍ−１であると仮定すれば、これは、
Ｏ＝ｌ／１６（（ｎ＋ｌ）^２／ｎ）^２
として記述することが可能である。

図５は、グラフにおいて、フットプリントの数（すなわち、ｎ^２）としてＯの値を表す。

９^＊９の画素のフットプリントの場合、Ｏの値は７．７１６である。すなわち、各画素は平均的に、７．７１６個のウィンドウに共通である。

Ｏは、一次近似では、マッチング・ウィンドウの組のフットプリント（すなわち、ｎ^２）の線形関数である。一次近似では、Ｏは、おおよそ、フットプリントを１２．５で除算した数に１を加えた数である。

マッチング・ウィンドウの重なりにより、問題（すなわち、エラーの伝播）が特に、平滑な視差面において生じる。マッチング・ウィンドウの重なりが多いほど、問題は大きくなる。既知の手法では、平滑な視差面が損なわれるという問題は、境界検出手法を実現し、境界領域を非境界領域と違ったふうに処理することにより、解決される。しかし、これは更なる算出工程を必要とする。この伝播は、Ｏ−１の値が大きいほど、より大きくなる。従来技術では、数Ｏは大きく、更に垂直方向の線及び水平方向の線に沿って大きく、それにより、問題が加わる。

図６は、本発明の方法及び装置において使用されるマッチング・ウィンドウの組を示す。図の下半分はフットプリントを示し、図４に示すように、画素が共通であるウィンドウの数を示す。フットプリントは３２個の画素であり、平均重なり値Ｏ＝４０／３２＝１．２５である。この重なり数Ｏは、約２．５の匹敵するフットプリントを備えた従来技術の重なり数よりもずっと小さい。平滑な視差面が損なわれる問題は、Ｏ−１の値に比例する可能性が高い。定義上、Ｏの最小値は１であるからである。よって、Ｏ−１は、画素の重なりに最善の尺度である。Ｏ−１を比較すれば、０．２５と１．５との間に更に顕著な差（すなわち、６倍の差）がみられる。公式では、本発明の条件は以下として表すことができる。

Ｏ＜ＦＰ／１５＋１であり、好ましくは、Ｏ＜ＦＰ／２５＋１であり、ここで、ＦＰは、フットプリントにおける画素数を表す。より好ましくは、Ｏ＜ＦＰ／５０＋１である。

従来技術では、Ｏ≒ＦＰ／１２．５＋１があてはまる。少なくとも２０％だけ、好ましくは少なくとも２分の１に、より好ましくは少なくとも４分の１に削減することにより、従来技術の問題の重なりが低減する。

図６の例では、矩形の４つの５^＊２マッチング・ウィンドウの組が使用される。前述のマッチング・ウィンドウのフットプリントは、十文字形を形成する。矩形の長軸は、水平方向及び垂直方向に沿って指向させる。

図７は、ウィンドウの組の更なる例を示す。フットプリントは比較的小さい（すなわち、１７個の画素）である。数Ｏ＝２１／１７＝１／２４である（従来技術の場合のＯの値（約２．３６）よりもずっと小さい）。矩形の４つの５^＊１マッチング・ウィンドウの組を使用する。前述のマッチング・ウィンドウのフットプリントは十文字を形成する。

図８は、本発明による方法及び装置において使用されるウィンドウの組の更に別の例を示す。この場合、４つのマッチング・ウィンドウの２つの組が使用される。フットプリントは４５であり、平均値Ｏは８０／４５−１＝０．７７７であり、これは、同じフットプリントについての従来技術によって知られている構成の平均（すなわち、おおよそ３．６）よりもずっと少ない。

図９は、本発明による方法及び装置において使用されるウィンドウの組の更に別の例を示す。フットプリントは８１個の画素であり、Ｏの数は８８／８１＝１．０８６であり、これは、従来技術の値（６．７７）よりもずっと少ない。この例では、４つの三角形のマッチング・ウィンドウの組が使用される。三角形の対称性の適切な軸は、垂直方向及び水平方向に沿って配向されている。

図１０は、更に別の実施例を表す。

図は、本発明の更に別の実施例を表す。この例では、８つの三角形ウィンドウの組が使用される。フットプリントは８１であり、Ｏの数＝１２０／８１＝１．４８である。

マッチング・ウィンドウの図示した例は何れも方形でない。本発明の広い概念においては、方形ウィンドウを使用することができるが、マッチング・ウィンドウが非方形であることが好ましい。矩形マッチング・ウィンドウや三角形マッチング・ウィンドウなどの非方形形状のウィンドウは、（図１１に示す矩形マッチング・ウィンドウ又は三角形の場合、）水平エッジや垂直エッジなどの、又は（三角形マッチング・ウィンドウの場合、）４５度のエッジの特定の画像特徴へのロッキングに、より適切であるからである。

好ましくは、フットプリントの画素が属するウィンドウの平均数は、フットプリント内の画素の数を５０で除算した数に１を加えた数未満である。本願に示す例は全て、この規則に従う。図５、図６及び図７に示す例は、互いに垂直に配向され、組み合わせて十文字形状を形成する略矩形形状のマッチング・ウィンドウを示す。図９に示すマッチング・ウィンドウと同様に、前述のマッチング・ウィンドウは、垂直方向及び水平方向に沿ったエッジを示す。図５、６及び７に示すマッチング・ウィンドウは、ｎ１^＊ｎ２画素のサイズを有し、本願例では、５^＊１画素及び５^＊２画素を有する。垂直方向及び水平方向に沿って配向された前述の矩形形状のマッチング・ウィンドウが最も好ましい。

好ましくは、マッチング・ウィンドウは同じ形式を有し、フォアサムの形状を形成し、形状は配向され、各マッチング・ウィンドウの形状は別のマッチング・ウィンドウの形状に関連し、マッチング・ウィンドウのうちの別のものの９０度、１８０度又は２７０度の回転によって得ることができる。図６乃至図１２の組は、前述の構成を示し、マッチング・ウィンドウの組それぞれは、他の形態を提供するために９０度、１８０度及び２７０度だけ回転させた１つ（図６、図７、図９及び図１０）又は２つ（図８及び図１１）の基本配向形態から得られる。前述の構成により、計算が容易になる。好ましくは、視差候補を生成するよう、相互に直交方向に配向された小さく、比較的薄いマッチング・ウィンドウを使用することにより、バランスが取られる。

図１２は、本発明によるマッチング・ウィンドウの組の別の例を示す。この例におけるフットプリントは図１１に示すフットプリントよりも小さく、７^＊７の方形であり、Ｏ＝８０／４９＝１．６である。

フットプリントはなお、５^＊５方形に縮減することが可能であり、この場合、Ｏ＝４８／２５＝１．９２になり、これは、ちょうど、Ｏ＜Ｆ／２５＋１＝２という好ましい条件内であり得る。

本発明による装置は、別々の向きから得られた画像を入力する入力と、画像の点に対するウィンドウ・ベースのマッチングを使用して入力によって受信された画像から深度マップを判定する判定器とを含み、判定器では、固定マッチング・ウィンドウの組を、画像点に対して使用し、マッチング・ウィンドウの組は、画像点周りの画素のフットプリントに及び、フットプリント（ＦＰ）の画素が属するウィンドウの平均数（Ｏ）は、フットプリントにおける画素の数を１５で除算した数に１を加えた数未満であり（Ｏ＜ＦＰ／１５＋１）、好ましくは、フットプリントにおける画素の数を２５で除算した数に１を加えた数未満であり（Ｏ＜ＦＰ／２５＋１）、更に好ましくは、フットプリントにおける画素の数を５０で除算した数に１を加えた数よりも少ない（Ｏ＜ＦＰ／５０＋１）。

図１３は、本発明による装置を示す。図１３において立方体で表す物体の画像が、２台のカメラによって撮られる。この例では、２台のカメラが示されているが、装置は、３台以上のカメラを含み得る。カメラは、カラー画像、又はモノクロ画像あるいはＸ線画像あるいは赤外線画像を記録し得る。カメラはそれぞれ、２組のデータを供給し、各組のデータは、Ｄｌ（ｘｌ，ｙｌ）及びＤ２（ｘ２，ｙ２）（すなわち、２組の２次元データ）で図に示す２次元画像を表す。カメラは、別々の向きから画像を撮る。装置は、別々の向きから撮られた画像を入力する入力Ｉと、判定器Ｄとを備える。判定器Ｄ内では、画像は、本発明によるマッチング・ウィンドウ手法を使用した最善のマッチである。この目的で、判定器は、画像Ｄ１（ｘ１，ｙ１）又はＤ２（ｘ２，ｙ２）のうちの一方において画素を選択する選択器１３３を備えている。選択された画素のマッチング器１３４では、最善のマッチが、画像間でマッチング・ウィンドウを使用して求められる。

帰属器１３５では、上記画素にｚ値が、マッチング器１３４の結果（すなわち、ウィンドウの最善のマッチ）を使用して帰属される。好ましくは、カメラからのデータは、カメラの相互の向き上のデータを含み、判定器はカメラの相互の向きを判定するための手段を有するか、あるいは、カメラは、前述の相互の向きを判定器に通信するための手段を有するか、あるいは、判定器は、前述のデータを（例えば、手作業で）入力する手段を含むか、又は、カメラのセットアップは固定であるので、相互の向きが分かっている。カメラによる画像の撮影は、好ましくは同期化される。判定器は出力ＯＰを有する。出力データ・ストリームＤ（ｘ，ｙ，ｚ）は、ｘ点座標及びｙ点座標、並びにｚ座標（すなわち、深度マップ）を含むデータ・ストリームである。この出力データ・ストリームＤ（ｘ，ｙ，ｚ）は、記録装置に（例えば、ＤＶＤデータ担体や何れかの他のデータ担体上にデータ・ストリームを記録するために）送出してもよく、又は、上記出力データ・ストリームＤ（ｘ，ｙ，ｚ）は、３次元画像を表示する３次元表示装置に送出することができる。

図１３は、カメラなどの記録装置を含む装置を示す。

図１４は、データ担体（例えば、ＤＶＤ。データＤ１（ｘ１，ｙ１）及びＤ２（ｘ２，ｙ２）、並びにカメラの相互の向きに関するデータ（Ｄ（ｃａｍ１，ｃａｍ２））が記憶される）用の入力を有する装置を示す。本発明による装置は、データを読み出し、出力データ・ストリームＤ（ｘ，ｙ，ｚ）を供給する。

本発明による装置の好ましい実施例は、方法の上記好ましい実施例のうちの何れか１つ又は何れかの組み合わせ（例えば、フットプリント（ＦＰ）の画素が属するウィンドウの平均数（Ｏ）が、フットプリントにおける画素数を５０で除算した数に１を加えた数未満（Ｏ＜ＦＰ／５０＋１）であるか、又は、マッチング・ウィンドウ若しくは非方形）によって深度マップを判定する手段を備える。

本発明による装置は、画像を記録する手段を備え得る。すなわち、装置は、画像を撮影するためのカメラを含み得る。カメラは、画像に関するデータを前述の入力に送出する。装置は、記録装置からのデータを受信することもできる。

本発明の概念において、「判定器」、選択器、マッチング器等は、広く解するものとし、例えば、何れかのハードウェア（判定器など）、本願記載の判定、選択又はマッチング機能を行うよう企図された何れかの回路若しくはサブ回路、本発明による判定、選択又はマッチング動作を行うよう企図若しくはプログラムされた何れかのソフトウェア（コンピュータ・プログラムあるいはサブ・プログラムあるいはコンピュータ・プログラムの組、又はプログラム・コード）、並びに、後述する例示的な実施例に制限されることなく、単独に、又は組み合わせで、そういうものとして動作するハードウェア及びソフトウェアの何れかの組み合わせを含むものとする。一プログラムはいくつかの機能を組み合わせることができる。

約言すれば、本発明は以下のように説明することができる。

ウィンドウ・ベースのマッチングは、別々の向きから得られる画像から深度マップを判定するために使用される。固定マッチング・ウィンドウの組が、深度を判定する画像の点に対して使用される。マッチング・ウィンドウの組は、画像の点周りの画素のフットプリントを包含し、フットプリント（ＦＰ）の画素が属するマッチング・ウィンドウの平均数（Ｏ）は、フットプリント内の画素数を１５で除算した数に１を加えた数未満（０＜ＦＰ／１５＋１）であり、好ましくは、フットプリント内の画素数を２５で除算した数に１を加えた数未満（０＜ＦＰ／２５＋１）である。

本発明は、本発明による方法又は装置のために何れかのコンピュータ・プログラム・プロダクトにおいても実施される。コンピュータ・プログラムは、プロセッサ（汎用又は専用）が、一連のロード工程（最終プロセッサ言語及び中間言語への翻訳のような中間翻訳工程を含み得る）後に、プロセッサが、コマンドをプロセッサに入れて、本発明の特徴的な機能の何れかを実行することを可能にするコマンド集合体の何れかの物理的な実現手段として理解されるものとする。特に、コンピュータ・プログラム・プロダクトは、担体（例えば、ディスクやテープなど）上のデータ、メモリに存在しているデータ、ネットワーク接続（有線又は無線）を介して流れるデータや、紙上のプログラム・コードとして実現することができる。プログラム・コード以外に、プログラムに必要な特性データもコンピュータ・プログラム・プロダクトとして実施することができる。

方法の実施に必要な工程の一部（デ―タの入力工程及び出力工程など）は、コンピュータ・プログラム・プロダクトに記述されるかわりにプロセッサの機能において既に存在し得る。

上記実施例は本発明を限定するよりも例証するものであり、特許請求の範囲記載の範囲から逸脱しない限り、別の多くの実施例を当業者が企図することができるであろう。

特許請求の範囲では、括弧内にある参照符号は何れも、本特許請求の範囲を限定するものとして解釈されないものとする。

本発明の枠組みにおいて、多くの変形が可能であることは明らかである。上記記載内容に本発明が限定されないことを当業者は理解するであろう。本発明は、新規の特徴的な特性、及び、特徴的な特性の組み合わせ全てにおいて存在している。請求項における参照符号は、その保護範囲を限定するものでない。

例えば、方法は、画像の一部のみに使用することができるか、又は、本発明の方法の種々の実施例を、画像の種々の部分に対して（例えば、画像のエッジに別の実施例を使用する一方で、画像の中心に一実施例を使用して）使用することができる。

「ｔｏ ｃｏｍｐｒｉｓｅ」の動詞及びその活用形を用いていることは、特許請求の範囲記載のもの以外の構成要素が存在することを排除するものでない。構成要素に先行する冠詞「ａ」又は「ａｎ」を使用していることは、前述の構成要素が複数存在することを排除するものでない。

画像の一部の幾何形状、及び２つの向きを示す図である。 画像の一部の画像を示す図である。 深度マップを作成する方法のフローチャートである。 従来技術において使用されるマッチング・ウィンドウの組を示す図である。 既知の方法のフットプリントＰの関数としての重なりＯの数を示す図である。 本発明による方法及び装置のマッチング・ウィンドウの組の例を示す図である。 本発明による方法及び装置のマッチング・ウィンドウの組の例を示す図である。 本発明による方法及び装置のマッチング・ウィンドウの組の例を示す図である。 本発明による方法及び装置のマッチング・ウィンドウの組の例を示す図である。 本発明による方法及び装置のマッチング・ウィンドウの組の例を示す図である。 本発明による方法及び装置のマッチング・ウィンドウの組の例を示す図である。 本発明による方法及び装置のマッチング・ウィンドウの組の例を示す図である。 本発明による装置を示す図である。 本発明による装置を示す図である。

Claims (17)

1. 画像の点に対するウィンドウ・ベースのマッチングを使用して別々の向きから得られる画像から深度マップを判定する方法であって、固定マッチング・ウィンドウの組が前記画像の点に対して使用され、前記マッチング・ウィンドウの組は前記画像の点の周りの画素のフットプリントを包含し、前記フットプリント（ＦＰ）の画素が属するマッチング・ウィンドウの平均数（Ｏ）は、前記フットプリントにおける画素の数を１５で除算した数に１を加えた数未満である方法。
2. 請求項１記載の方法であって、前記フットプリントの画素が属するウィンドウの平均数（Ｏ）は、前記フットプリント内の画素の数を２５で除算した数に１を加えた数未満である（Ｏ＜ＦＰ／２５＋１）方法。
3. 請求項２記載の方法であって、前記フットプリントの画素が属するウィンドウの平均数（Ｏ）は、前記フットプリント内の画素の数を５０で除算した数に＋１を加えた数未満である（Ｏ＜ＦＰ／５０＋１）方法。
4. 請求項１、２又は３に記載の方法であって、前記マッチング・ウィンドウそれぞれは２０画素未満である方法。
5. 請求項４記載の方法であって、前記マッチング・ウィンドウそれぞれは１０画素未満である方法。
6. 請求項１乃至５の何れかに記載の方法であって、別々の向きを備えたマッチング・ウィンドウが使用される方法。
7. 請求項６記載の方法であって、前記マッチング・ウィンドウの前記向きは、互いに略垂直である方法。
8. 請求項１乃至７の何れかに記載の方法であって、前記マッチング・ウィンドウが非方形である方法。
9. 請求項８記載の方法であって、前記マッチング・ウィンドウの形状が矩形である方法。
10. 請求項８記載の方法であって、前記マッチング・ウィンドウの形状が三角形である方法。
11. 請求項９記載の方法であって、前記マッチング・ウィンドウがｎ１^＊ｎ２画素であり、ｎ１≧２ｎ２である方法。
12. 請求項１１記載の方法であって、ｎ１が１、２又は３であり、ｎ２が５乃至８である方法。
13. 画像の点に対するウィンドウ・ベースのマッチングを使用して別々の向きから得られる画像から深度マップを判定する装置であって、前記装置は、別々の向きから得られる画像（Ｄ１（ｘ１，ｙ１），Ｄ２（ｘ２，ｙ２））を入力する入力（Ｉ）と、前記画像の点に対するウィンドウ・ベースのマッチングを使用して前記入力によって受信された画像から深度マップを判定する判定器（Ｄ）とを備え、前記判定器（Ｄ）は、前記画像の前記点に対して固定マッチング・ウィンドウの組を使用するよう構成され、前記マッチング・ウィンドウの組は前記画像の前記点周りの画素のフットプリントを包含し、前記フットプリント（ＦＰ）の画素が属するマッチング・ウィンドウの平均数（Ｏ）は前記フットプリント内の画素の数を１５で除算した数に１を加えた数未満である（Ｏ＜ＦＰ／１５＋１）である装置。
14. 請求項１３記載の装置であって、前記フットプリントの画素が属するウィンドウの平均数は、前記フットプリント内の画素の数を２５で除算した数に＋１を加えた数未満である（Ｏ＜ＦＰ／２５＋１）装置。
15. 請求項１４記載の装置であって、前記フットプリントの画素が属するウィンドウの平均数は、前記フットプリント内の画素の数を５０で除算した数に１を加えた数未満である（Ｏ＜ＦＰ／５０＋１）装置。
16. プログラムをコンピュータ上で実行させると、請求項１乃至１２のうちの何れか一項に記載の方法を行うプログラム・コード手段を備えるコンピュータ・プログラム。
17. 請求項１乃至１２のうちの何れか一項に記載の方法を行うためにコンピュータ読み取り可能な媒体上に記憶されたプログラム・コード手段を備えたコンピュータ・プログラム・プロダクト。

Images