(57)【要約】複数の異なる配向から得られた画像から奥行きマップを決定するためにウィンドウ・ベースのマッチングが使われる。奥行きが決定されるべき画像の点について、一組のマッチング・ウィンドウが使用される。各点に二つ以上の候補奥行き値が割り当てられた仮奥行きマップが生成される。仮奥行きマップは表面フィルタ処理によってフィルタリングされ、それにより近隣点の候補奥行き値から着目点の候補奥行き値に向かう単位ベクトルの和のノルムの少なくともｚ成分が最小化される。
2010502945.tif 000002
【特許請求の範囲】
【請求項１】
複数の異なる配向から得られた画像から、画像の点についてウィンドウ・ベースのマッチングを使って奥行きマップを決定する方法であって、少なくとも画像の一部分について、画像の前記一部分の点について、一組のマッチング・ウィンドウが使われ、各点についていくつかの候補視差値が計算されて、各点に二つ以上の候補視差値が割り当てられる仮の奥行きマップを与え、その後、各点について、近傍点についての候補視差値から前記点に向かう単位ベクトルの和のノルムの少なくともｚ成分を最小化することによってさらなる奥行きマップが計算される、方法。
【請求項２】
近傍点の単位ベクトルの和のノルムのすべての成分が最小化される、請求項１記載の方法。
【請求項３】
前記一組のマッチングが、着目点がマッチング・ウィンドウに対して離心的に位置するような一つまたは複数のマッチング・ウィンドウを含む、請求項１記載の方法。
【請求項４】
前記単位ベクトルの和は重み付けされた和であり、計算内での各単位ベクトルについての重みは着目点までの距離の関数である、請求項１ないし３のうちいずれか一項記載の方法。
【請求項５】
平均からある閾値より大きく異なっている単位ベクトルを計算から削除するチェックが実行される、請求項１ないし４のうちいずれか一項記載の方法。
【請求項６】
前記一組のマッチング・ウィンドウは、マッチング・ウィンドウの実質的に直交する集合である、請求項１ないし５のうちいずれか一項記載の方法。
【請求項７】
マッチング・ウィンドウの数は４であり、該マッチング・ウィンドウは十字を形成する、請求項６記載の方法。
【請求項８】
マッチング・ウィンドウの数は８であり、該ウィンドウは二つの四つ組からなり、一方の四つ組は他方の四つ組をなす諸ウィンドウの左手バージョンまたは右手バージョンであり、各四つ組が十字をなす、請求項７記載の方法。
【請求項９】
前記マッチング・ウィンドウが実質的に三角形状である、請求項６記載の方法。
【請求項１０】
前記さらなる奥行きマップに対して突出値拒否／隠蔽検出が実行される、請求項１ないし９のうちいずれか一項記載の方法。
【請求項１１】
前記さらなる奥行きマップに対して画像ベースの穴重点が実行される、請求項１０記載の方法。
【請求項１２】
当該プログラムがコンピュータ上で走らされたときに請求項１ないし１１のうちいずれか一項記載の方法を実行するためのプログラム・コード手段を有するコンピュータ・プログラム。
【請求項１３】
請求項１ないし１１のうちいずれか一項記載の方法を実行するための、コンピュータ可読媒体上に記憶されたプログラム・コード手段を有するコンピュータ・プログラム。
【請求項１４】
複数の異なる配向から得られた画像データを入力するための入力と、前記入力によって受領された画像データから、前記画像のある点についてウィンドウ・ベースのマッチングを使って仮奥行きマップを決定する決定器とを有する装置であって、前記決定器においては、一組のマッチング・ウィンドウが前記画像の前記点について使用されて、前記諸点について候補視差値が生成され、当該装置はさらに、前記仮奥行きマップに基づいて、各点について、近傍点についての候補視差値から前記点に向かう単位ベクトルの和のノルムの少なくともｚ成分を最小化することによって、さらなる奥行きマップを提供するよう構成されている表面フィルタを有する、装置。
【請求項１５】
前記表面フィルタが近傍点の単位ベクトルの和のノルムのすべての成分を最小化するよう構成されている、請求項１４記載の装置。
【請求項１６】
前記決定器が、前記一組のマッチングが、着目点がマッチング・ウィンドウに対して離心的に位置するような一つまたは複数のマッチング・ウィンドウを含むよう構成されている、請求項１４記載の装置。
【請求項１７】
前記表面フィルタが、前記単位ベクトルの和は重み付けされた和であり、計算内での各単位ベクトルについての重みは着目点までの距離の関数であるよう構成されている、請求項１４記載の装置。
【請求項１８】
前記表面フィルタが、平均からある閾値より大きく異なっている単位ベクトルを計算から削除するチェックが実行されるよう構成される、請求項１４記載の装置。
【請求項１９】
当該装置が画像を記録する手段を有する、請求項１４記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、異なる配向から得られた複数の画像から、画像のある点についてウィンドウ・ベースのマッチングを使って奥行きマップを決定する方法に関する。本発明は、異なる配向から得られた複数の画像から、画像のある点についてウィンドウ・ベースのマッチングを使って奥行きマップを決定する装置にも関する。
【背景技術】
【０００２】
いくつかの応用について、画像から奥行きマップを決定することが望ましい。そのような応用の例は、対話的に制御可能な配向から見たシーンの画像を計算することを可能にするシステム、画像圧縮、検査などを含む。ステレオ画像から奥行きマップを復元する課題はしばしば、3Dディスプレイ、製造における品質管理、自律的ナビゲーションおよびオブジェクト認識といった幅広い範囲の応用について決定的に重要である。本稿では、画像中のある点の奥行き（depth）とは、視点と、前記点を通りカメラの光学軸に垂直な平面との間の距離を指す。
【０００３】
カメラの視点が第一の視点から第二の視点に動かされるとき、画像点の位置の並進量から画像点の奥行きが決定できる。画像が点投影によって得られる場合、並進はカメラの変位の量に比例し、画像のその部分の奥行きに反比例する。
【０００４】
並進を測定するために、カメラの第一の配向から得られた第一の画像におけるあるピクセルのまわりのあるウィンドウ内のピクセル値が第二の配向から得られた第二の画像におけるあるピクセルのまわりのあるウィンドウ内のピクセル値と比較される、ウィンドウ・ベースのマッチングを使うことが知られている。マッチングは通例、マッチング・ウィンドウ内のピクセルのピクセル値の差の集計（aggregate）を決定することを含む。
【０００５】
適応的ウィンドウを使うことも提案されている。しかしながら、適応的ウィンドウを使うことは、ウィンドウを適応させるために、通例きわめて込み入ったアルゴリズムを必要とする。
【０００６】
ウィンドウ・ベースのマッチングを使って奥行きマップを決定する方法は非特許文献１に記載されている。
【０００７】
既知の方法では、マッチングが実行される画像の各点について、マッチング・ウィンドウが使用され、該マッチング・ウィンドウ内で、着目点の位置が該ウィンドウのすべての点にわたって走査される。マッチング・ウィンドウが着目ピクセルのまわりに非対称的に設定されていてマッチング・ウィンドウがオブジェクト境界をカバーしない場合、境界突出（boundary  overreach）は現れない。着目ピクセルは、マッチング・ウィンドウの全集合にわたって走査される。結果として得られるSSSD（SSDの和［Sum  of  SSD］、ここで、SSDは平方差分和［Sum  of  Squared  differences］）の最小値を見出すことで、前記点についての視差推定値（disparity  estimate）が与えられる。
【０００８】
既知の方法は、境界突出の問題に解決を提供する。しかしながら、その解決はより多数の計算の必要性という代償を伴う。さらに別の問題が生じる：なめらかな視差表面（smooth  disparity  surfaces）は破壊され、そのようななめらかな視差表面に多くの階段状の正方形（stepwise  squares）が観察される。なめらかな視差表面における問題は、既知の方法では、境界検出方法を実装し、境界領域を非境界領域とは異なる仕方で処理することによって対処される。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】奥富正敏ら、「精確なオブジェクト境界およびなめらかな表面を回復するための簡単なステレオ・アルゴリズム」、コンピュータ視覚およびパターン認識2001（CVPR2001）、2001年米国電気電子技術者協会・コンピュータ協会会議集録、第２巻、第II-138‐II-142頁（Masatoshi  Okutomi  et  al.,  "Simple  Stereo  Algorithm  to  Recover  Precise  Object  Boundaries  and  Smooth  Surfaces",  Computer  Vision  and  Pattern  Recognition  2001,  CVPR  2001,  Proceedings  of  the  2001  IEEE  Computer  Society  Conference,  Volume  2,  2001,  pp.  II-138‐II-142,  vol.  2）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、既知の方法は大量の計算パワーおよびかなり複雑なアルゴリズムを必要とする。
【００１１】
なかんづく、比較的信頼できかつ精確な奥行きの推定を提供しつつ、比較的少なめの計算パワーしか要求しない方法を提供することが本発明の一つの目的である。
【課題を解決するための手段】
【００１２】
本発明によれば、少なくとも画像の一部分について、画像の前記一部分の諸点について、一組のマッチング・ウィンドウが使われ、各点についていくつかの候補視差値が計算されて、各点に二つ以上の候補視差値が割り当てられる仮の奥行きマップを与え、その後、各点について、近傍点についての候補視差値から前記点に向かう単位ベクトルの和のノルムの少なくともｚ成分を最小化することによってさらなる奥行きマップが計算される。
【００１３】
既知の方法は「勝者総取り」戦略に基づいている。すなわち、各点について、単一の最良の視差値が計算される。これは高い精度を要求し、そのことは大量の計算パワーを要求する。そうではあっても、精度はマッチング・ウィンドウの特定の選択次第である。つまり、ある特定の問題がマッチング・ウィンドウの選択に関連付けられる場合、問題は残る。
【００１４】
本発明では異なるアプローチが取られる。各点について、いくつかの候補視差値が最初に一組のマッチング・ウィンドウを使って計算される。
【００１５】
発明者は、ウィンドウ・ベースの技法についてはウィンドウの適正な選択が重要であることを認識するに至った。用いられるマッチング・ウィンドウの大きさが大きければ、これは不正確な境界をもち細かな詳細が失われたぼやけた奥行きマップにつながりうる。他方、小さなウィンドウを使うことは、計算パワーを節減し、良好である一方、ノイズの影響を受けやすい方法につながりうる。比較的小さなウィンドウを用いたマッチングの結果は、ノイズのある奥行きマップであるが、重要な小さな画像特徴を含んでいるものとなる。着目点についての視差値としてSSDまたはSADスコアが最低になるウィンドウの結果を選択するマルチ・ウィンドウ・マッチングへの一般的なアプローチの代わりに、本発明に基づく方法の主要な特徴は、候補を正則化空間（a  regularizing  space）として使っての視差推定値の再計算である。ノイズのある仮奥行きマップが作られる。ここで、各点について、いくつかの候補視差値が計算される。そのような計算のためには、限られた計算パワーしか必要とされない。その後、なめらかにする動作が実行されて、各点がｚ値を与えられる。
【００１６】
「真の視差値」を見出すために候補視差値の平均または中央値を取ることは、有望な結果を与えないことがわかった。しかしながら、再計算のための単位ベクトルを使うと、前記さらなる奥行きマップは良好な結果を与えることがわかった。前記さらなる奥行きマップは、本稿の以下では時に局所的奥行きマップとも呼ばれるが、近傍の諸3D点（近傍内であり、種々のスーパーインポーズされた複数候補データ・セットから来る）からある点をポイントする単位ベクトルを計算し、これらの単位ベクトルの和のノルムの少なくともｚ成分を前記点において最小化する視差を見出すことによって計算される。これは、表面の前記一部分の各点について行われる。「各点」とは、さらなる奥行きマップが作られるべきであるような画像の部分の点を指す。画像の前記一部分についての前記計算内の点の数は、通例ピクセル数と等価である。この場合には各ピクセルにある点が帰される。「各点」は、数学的な意味での、無限にある「各点」を意味するものと誤解すべきではない。近傍とは、本発明の概念の範囲内では、着目点のまわりの所与の範囲を表す。
【００１７】
好ましい諸実施形態では、単位ベクトルの和のノルムが最小化される。関心が、主として前額平行な表面を復元することにある場合、単位ベクトルの差のノルムのｚ成分のみを最小化することが十分な手続きでありうる。
【００１８】
より洗練された諸方法では、近傍点の単位ベクトルの和のノルムのすべての成分が最小化される。
【００１９】
好ましくは、単位ベクトルの和は重み付けされた和である。ここで、計算内での各単位ベクトルについての重みは着目点までの距離の関数である。これは精度を改善することになる。着目点の視差値は、着目点から遠く離れた点よりも近くにある近傍点の視差値に似ている可能性がより高い。
【００２０】
好ましくは、前記一組のマッチングは、着目点がマッチング・ウィンドウに対して離心的に位置するような一つまたは複数のマッチング・ウィンドウを含む。正方形のブロックがマッチング・ウィンドウについて最も一般的に使われる形であるが、マッチング・ウィンドウについての離心的に位置された形は、横または縦の辺といった特定の画像特徴上にロックするためにより好適である。画像中の着目点を中心としていないという事実により、ウィンドウの少なくとも一つが、隠蔽する境界（occluding  boundaries）の近くで適正にマッチすることができる。
【００２１】
好ましくは、平均からある閾値より大きく異なっている単位ベクトルを計算から削除するチェックが実行される。それにより、逸脱した候補視差値、すなわち何らかの計算誤差のために正常な範囲から大きく外れている候補視差値が結果に負の影響を与える可能性が小さくなる。閾値は固定値であってもよいし、他の値に基づいて計算されてもよいし、あるいはスプレッド計算（a  spread  calculation）に関係していてもよい。
【００２２】
好ましくは、前記一組のマッチング・ウィンドウは、マッチング・ウィンドウの実質的に直交する集合である。実質的に直交する（orthogonal）マッチング・ウィンドウとは、ウィンドウ間のピクセルの重なりがウィンドウ当たりのピクセル数の１／４未満であるマッチング・ウィンドウである。
【００２３】
好ましい諸実施形態では、マッチング・ウィンドウの数は４であり、それらのマッチング・ウィンドウは十字を形成する。十字は単純な配置であるが、良好な結果を与えることが示されている。
【００２４】
もう一つの好ましい実施形態では、マッチング・ウィンドウの数は８であり、それらのウィンドウはそれぞれが十字を形成する二つの四つ組（foursome）からなり、一方の四つ組が他方の四つ組のウィンドウの左手バージョンまたは右手バージョンである。マッチング・ウィンドウの一つの四つ組を使うことは、若干の左から右または右から左のバイアスを導入しうる。二つの四つ組を使うことによって、このバイアスは消去できる。
【００２５】
もう一つの実施形態では、マッチング・ウィンドウは実質的に三角形状である。
【００２６】
本発明のこれらおよびその他の利点が以下の図面を使ってより詳細に記述される。
【００２７】
図面は縮尺通りに描かれてはいない。一般に、同一の構成要素は複数の図面において同じ参照符号によって示されている。
【図面の簡単な説明】
【００２８】
【図１】画像の一部分および二つの配向の幾何学を示す図である。
【図２】画像の一部分の画像を示す図である。
【図３】Ａは、奥行きマップを作成する方法のフローチャートである。Ｂは、本発明に基づく方法の一部を例解する図である。
【図４】結果として得られる仮の奥行きマップを、一次元で線に沿って示す図である。
【図５】本発明の方法におけるさらなる段階を示す図である。
【図６】従来技術において記載されている一組のマッチング・ウィンドウを示す図である。
【図７】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図８】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図９】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１０】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１１】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１２】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１３】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１４】本発明に基づく方法を示す図である。
【図１５】本発明に基づく装置を示す図である。
【図１６】本発明に基づく装置を示す図である。
【図１７】本発明に基づく方法の結果を示す図である。
【図１８Ａ】本発明に基づく方法の結果をさらに示す図である。
【図１８Ｂ】本発明に基づく方法の結果をさらに示す図である。
【図１８Ｃ】本発明に基づく方法の結果をさらに示す図である。
【図１８Ｄ】本発明に基づく方法の結果をさらに示す図である。
【発明を実施するための形態】
【００２９】
図１は、画像１０の一部分および二つの配向１２ａ、１２ｂの幾何構造を示している。画像の一部分はたとえば、人物であってもよいし、画像内の他のいかなるオブジェクトであってもよい。本発明は、画像についての奥行きマップを与える方法に関する。奥行きマップとは、オブジェクトの点にｚ値、すなわち奥行き値を帰属させるものと見ることができる。画像１０の一部分を含むシーンの画像が異なる配向１２ａ、１２ｂからの点投影を使って得られるとき、画像の前記部分の上の点１４、１５が見える像の中の位置が、点１４、１５の投影１６ａ、ｂ、１７ａ、ｂである。投影は、点１４、１５から配向１２ａ、１２ｂを通って像平面１８への描線１９ａ〜１９ｄによって図示できる。基本原理を述べるために、配向１２ａ、ｂは像平面１８に平行な面内に選択されているが、本発明は配向１２ａ、ｂのそのような選択に限定されない。これらの線１９ａ〜１９ｄと像平面１８との交点が、画像１０の前記部分の点１４、１５が像において見える位置を示す。
【００３０】
視点１２ａ、１２ｂの変化は、画像の一部分の上の点１４、１５が像平面１８内に見える位置１６ａ、ｂ、１７ａ、ｂの並進につながることを注意しておく。この並進は、視点と前記点との間の奥行き「ｚ」に反比例し、視点の位置の変化量に比例する。結果として、並進は、配向１２ａ、１２ｂからの奥行き「ｚ」が異なる画像１０の前記部分の点１４、１５について、異なることになる。
【００３１】
図２は、画像の一部分が見える領域２２を含む画像２０を示している。画像２０において、画像２０内に見える画像の前記一部分の点が視点の移動に応答して受ける並進を表す並進ベクトル２３ａ、ｂ、２５ａ、ｂが示されている。並進ベクトル２５ａ、ｂは、視点により近い画像の部分の点についてのほうが、視点からより遠い点についてよりも大きくなることを注意しておく。すべての点の奥行きが同じである直線２６に沿っては、並進は同じである。
【００３２】
直線２６に沿った軸およびその直線に垂直な軸をもつ座標系を使うと、点が見える位置の並進の幅「D」はA＋Buに比例する。ここで、uはその点が直線２６に垂直な軸に沿って見える位置の座標である。並進の方向は、視点の動きの方向とは逆である。パラメータ「A」はu＝0における奥行き「Z0」の逆数に比例し、「B」は同様にその奥行きと、見る方向に垂直な、画像の前記一部分の傾き「s」に比例する：B＝c×s/Z0（cは視点の変位、焦点距離および画像のスケールに比例する比例定数）。図１および図２は、二つのカメラが使用される状況を示している。奥行きマップを決定するためには、３つ以上のカメラが使用されてもよい。３つ以上のカメラを使用することは、精度を高め、背景オブジェクトが前景にあるオブジェクトによって隠蔽される可能性を減らす。
【００３３】
図３のＡは、画像について、あるいは画像の一部分について奥行きマップを作成する方法の一部のフローチャートを概略的に示している。
【００３４】
フローチャートの第一および第二のステップ３１、３２では、カメラ光学系が第一および第二の視点にそれぞれ位置される。それらの視点から第一および第二の画像が得られる。
【００３５】
フローチャートの第三のステップ３３では、第一の画像中のあるピクセルが選択される。第四のステップ３４では、そのピクセルについて、マッチング・ウィンドウを使って前記画像間でマッチがみつけられる。
【００３６】
フローチャートのステップ３５では、前記ピクセルに対して、ステップ３４の結果、すなわちウィンドウどうしのマッチを使ってｚ値が割り当てられる。既知の諸方法では、勝者総取りの原則により、各ピクセルに対して、単一の「最良」ｚ値が割り当てられる、すなわち最良マッチが求められ、これが視差値（＝ｚ値）を確立する。高い信頼レベルを与えるために、精度は高くなければならない。これはかなり大きなマッチング・ウィンドウの選択につながる。しかしながら、そのような比較的大きなマッチング・ウィンドウは、そのサイズに起因して小さな詳細を捉えることができない。
【００３７】
図３のＢは、本発明に基づく方法を示している。着目点について一つの視差値を与えるのではなく、ある着目点について、比較的小さな離心マッチング・ウィンドウのセットが使われ、各点についていくつかの候補視差値（ｚ値１、ｚ値２、ｚ値３など）が与えられる。いかなる点についても確定的な決断はされず、各点に対して二つ以上の候補視差値が割り当てられる。すべての候補視差値が組み合わされたものが、ノイズのある奥行きマップを与える。
【００３８】
図４は、一次元において線に沿って候補視差（すなわちｚ値）が示される、結果として得られる仮の奥行きマップを示している。この例では、二つの異なる色についての視差値が計算されている。二つの異なる値は概略的に黒丸および白丸で示されている。
【００３９】
図５は、本発明の方法内の次のステップを示している。
【００４０】
ノイズのあるサンプルからある点について実際の奥行き、すなわち実際の視差値を推定するために、図５に示された方式が使用される。各ピクセルについて、再構成されたサンプルから候補点をポイントする単位ベクトルの和のノルムを最小にする奥行き値が計算される。奥行き値が表面から遠い場合には、これらのベクトルの和のノルムは大きいが、表面に当たると、最小または最小近くであると期待される。本記述の枠組み内では、これは「表面フィルタ（surface  filter）」とも呼ばれる。すなわち、仮のノイズのある奥行きマップに対して特定的なフィルタリングが行われるのである。仮のノイズのある奥行きマップは、本方法が使われる対象となる画像の前記一部分における各点について、いくつかの候補視差値を含む。単位ベクトルの和自身もベクトルである。
【００４１】
ベクトルのノルムは、数学的には、このベクトルの「強さ」として理解できる。本発明の方法では、これらすべての単位ベクトルの和であるこのベクトルの強さが最小化される。この強さが小さい場合には表面マップに達する。さて、ベクトルの強さを測るいくつかの方法があるが、最も一般的なのはLpノルムである。これは次の公式で記述される：
【００４２】
【数１】
2010502945.tif 000003
個別的な場合として：
・L2ノルムまたはユークリッド・ノルム（p＝2）
【００４３】
【数２】
2010502945.tif 000004
・L1ノルム（p＝1）
【００４４】
【数３】
2010502945.tif 000005
・L∞と呼ばれる極限の場合で、
【００４５】
【数４】
2010502945.tif 000006
として定義される場合、がある。
【００４６】
数学的には、サイトiのまわりの小さな近傍N内での単位ベクトルの和のL-1ノルムが視差diに関して最小化される（下記にL-1ノルムを与えておく）。
【００４７】
【数５】
2010502945.tif 000007
ここで、Pi＝（Pix,Piy,Pz(di)）は最適化されるべき視差値diに対応する再構成された点（正則（regular）格子上にいるのでｚ成分だけがdiに依存する）、Pj＝（Pjx,Pjy,Pjz）は異なるウィンドウ配位によって推定される視差に対応する再構成された点である。近傍Nの大きさは小さく保つことができ、一方で、異なる奥行き推定器（異なるウィンドウ・マッチング配位）から来る冗長さのために、表面抽出は堅牢なままである。主として前額平行な表面を復元することに関心があるのであれば、(1)のｚ成分だけを最小化することができる。これは、計算コストを下げる。
【００４８】
近傍Nは、点に重みを割り当てることによって設定されることもできる。ここで、重みは点の間の距離の関数である。
【００４９】
【数６】
2010502945.tif 000008
ここで、W(Pi)は、点Piと点Pとの間の距離の関数で、距離が増すにつれて値が減少する。
【００５０】
計算は、表面の各点についてなされる。そこにあるいくつの点が計算にはいるかは、通例、ピクセル数に等しい。すなわち、各ピクセルに点が割り当てられ、その点について、単位ベクトルの和のノルムを最小化することによってｚ値が計算される。これは、計算を比較的簡単にする。
【００５１】
これは、視差値に対して平滑化フィルタ効果をもつことになる。着目点のまわりのある範囲の点が使われるので、これは、本発明の枠組み内では、表面フィルタ（surface  filter）と呼ばれる。
【００５２】
完全性のため、やはり使用可能なL-2ノルムも与えておく：
【００５３】
【数７】
2010502945.tif 000009
L-2ノルム＝{S2(di)}1/2である。
【００５４】
さらなる実施形態では、画像制約条件が使われる。
【００５５】
表面フィルタは、堅牢に視差を抽出するが、奥行き不連続の過剰な平滑化は避けることを示すことができる。そして、小さな詳細のよりよい復元のために、画像マッチング制約条件（image-matching  constraint）も含める。この条件のために、いかなる局所的な画像類似性基準を使うこともできる。たとえば、非常に小さなウィンドウ上でのSSDを採用することができる。局所的に最小化される最終的な基準は：
E(i)＝S(di)＋λSSD(di)        (2)
である。ここで、λはなめらかな視差領域抽出を精確な境界復元とバランスさせる因子である。最適化は、単に最小および最大の許容される離散的視差値の間を走査してE(i)を最小化する視差を見出すことによって実行される。
【００５６】
ある意味では、これは、ある点についてのSSDと近傍点からの単位ベクトルの和のノルムの組み合わせを最小化する組み合わされた方法と見ることができる。単位ベクトルの和のノルムは最小化されるが、前記和のノルムにその点におけるSSDを加えたものによって与えられるE(i)が最小化されるという制約条件のもとでである。
【００５７】
図６は、非特許文献１に記載される一組のマッチング・ウィンドウを示している。25個のウィンドウが使用され、各ウィンドウは25個のピクセルを含む。「着目点」と呼ばれるｚ値が決定されようとしているピクセル６１は黒い正方形によって表されている。5×5ピクセルの標準的なマッチング・ウィンドウが使用され、着目ピクセルが該標準的なウィンドウのすべての点にわたって走査される。これは25個のマッチング・ウィンドウ６２を与える。図４では、これら25個のマッチング・ウィンドウは灰色の正方形からなる5×5の領域によって表されている。大量の計算を実行する必要がある。
【００５８】
図７は、本発明の方法および装置において使用される一組のマッチング・ウィンドウを示している。マッチング・ウィンドウの間の重なりは小さい。
【００５９】
図８は、ウィンドウの組のさらなる例を示している。
【００６０】
図９は、本発明に基づく方法および装置で使用されるウィンドウの組のさらにもう一つの例を示している。この場合、４つのマッチング・ウィンドウからなる組二つが使用される。
【００６１】
図１０は、本発明に基づく方法および装置で使用されるウィンドウの組のさらにもう一つの例を示している。
【００６２】
図１１は、さらなる例を示している。
【００６３】
図１２および図１３は本発明のさらなる実施形態を示している。これらの例では、８つの三角形ウィンドウの組が使用される。
【００６４】
マッチング・ウィンドウの示された例のいずれも正方形ではないことを注意しておく。好ましくは、マッチング・ウィンドウは非正方形である。これは、長方形もしくは三角形のマッチング・ウィンドウといった非正方形の形をしたウィンドウは、横および縦の辺（図１１に示されるような長方形マッチング・ウィンドウまたは三角形について）あるいは45度の角度の辺（三角形マッチング・ウィンドウについて）といった特定の画像特徴の上にロックするのにより好適だからである。
【００６５】
図７、図８、図９に示される例は、実質的に長方形の形のマッチング・ウィンドウを示す。ウィンドウは互いに直交して配向され、組み合わさって十字形を形成する。これらのマッチング・ウィンドウは、図９に示されるマッチング・ウィンドウのように、縦および横の方向に沿った辺を示す。縦および横の方向に沿って配向されたそのような長方形の形のマッチング・ウィンドウが最も好ましい。
【００６６】
好ましくは、諸マッチング・ウィンドウは同じ形をもち、形の四つ組を形成し、前記形は配向され、各マッチング・ウィンドウの形は別のマッチング・ウィンドウの形と関係しており、別のマッチング・ウィンドウの90度、180度または270度回転によって得られるものであってもよい。図７ないし図１３の諸セットはそのような配置を示している。ここで、マッチング・ウィンドウの各セットは、一つ（図７、図８、図９、図１０）または二つ（図９、図１２）の基本配向形から、それを90度、180度および270度回転させて他の形を与えることで導出されている。好ましくは、視差候補を生成するために互いに直交する方向に配向された小さな比較的細いマッチング・ウィンドウを採用することによってバランスが取られる。
【００６７】
この方式は、仮奥行きマップに基づいて、さらなる奥行きマップを与える。
【００６８】
計算は、いくつかの好ましい改良によってさらに最適化されうる。
【００６９】
・S(D)の計算において、平均値からある閾値より大きく異なる単位ベクトルをS(D)の計算から削除するチェックが実行される。逸脱した候補視差値、すなわち何らかの計算誤差に起因する候補視差値が結果に負の影響を与える可能性が小さくなる。閾値は固定値であってもよいし、他の値に基づいて計算されてもよいし、あるいはスプレッド計算（a  spread  calculation）に関係していてもよい。
【００７０】
・偽のマッチを拒否し、隠蔽された領域を検出するために種々の方式が可能である。ある簡単な方式は、ストレートな左‐右／右‐左整合性チェックである。これは、得られた対応の一意性を保証し、隠蔽領域のラベル付けを許容する。
【００７１】
・画像ベースの後処理
突出値（outlier）拒否および隠蔽検出は前記さらなる奥行きマップにおける穴、すなわち視差値がない領域を生じることになる。突出値拒否および隠蔽検出ステップから帰結する穴を埋めるため、我々は色に基づく平均化を使う。これは、我々のサイト（Ri,Gi,Bi）での色に近い色ピクセルに対応する視差の平均（局所的な近傍内での）を計算することからなる。ある穴におけるサイトiにおける奥行きを再計算するために非線形フィルタが使用されることができる。
【００７２】
【数８】
2010502945.tif 000010
ここで、TCは色差閾値である。
【００７３】
Σjwij＝0の場合については、古い奥行き値が保持される。
【００７４】
このフィルタは、逐次反復的に使用されることができ、奥行きマップの境界を対応する色画像の境界と再整列させるという利点がある。これは３Ｄレンダリング用途のためには非常に重要である。色差閾値を含める選択は、実際の画像不連続に一致する鋭い奥行き不連続をもちたいという意向によって要求されるものである。実際上、この選択はうまく機能することが証明されている。
【００７５】
図１４は、本発明に基づく方法をより詳細に示している。
【００７６】
図１４は、４つのモジュール１４１〜１４４を示している。最初の二つのモジュール１４１および１４２は最も広い範囲における本発明の方法の一部である。あとの二つのモジュール１４３および１４４は、好ましい実施形態の一部であり、任意的である。
【００７７】
第一のモジュール１４１に対して、左および右の画像のデータが、あるいは画像が二つより多い視点から撮られる場合にはさまざまな視点からの画像データが与えられる。このモジュールでは、ウィンドウ・ベースのマッチングを使って仮奥行きマップが生成される。この仮奥行きマップは、各点について二つ以上の候補視差値を含むものであり、表面フィルタ・モジュール１４２に送られる。表面フィルタ・モジュールは、前記点を近傍点についての候補視差値からポイントする単位ベクトルの和のノルムの少なくともｚ成分を最小化することによって、表面フィルタを仮奥行きマップに適用する。これはさらなる奥行きマップを提供する。任意的であるさらなるモジュール１４３および１４４は、突出値／隠蔽検出およびその後の穴充填を提供する。最終産物は最終的な奥行きマップである。
【００７８】
本発明に基づく装置は、異なる配向から得られた画像データを入力するための入力と、前記入力によって受領された画像データから前記画像のある点についてウィンドウ・ベースのマッチングを使って仮奥行きマップを決定する決定器（１４２）とを有する。ここで、前記決定器においては、一組のマッチング・ウィンドウが前記画像の前記点について使用されて、前記諸点について候補視差値を生成する。ここで、前記一組のマッチング・ウィンドウは前記諸点に関して離心的に位置されており、当該装置はさらに、各点について、前記点を近傍点についての候補視差値からポイントする単位ベクトルの和のノルムの少なくともｚ成分を最小化することによって、仮奥行きマップに基づいてさらなる奥行きマップを提供するよう構成されている表面フィルタ（１４２）を有する。
【００７９】
図１５は、本発明に基づく装置を示している。図１５では立方体によって表現されているあるオブジェクトについて、二つのカメラによって画像が取得される。この例では二つのカメラが示されているが、本装置は三つ以上のカメラを有していてもよい。カメラはカラー画像または白黒画像またはＸ線画像または赤外線画像を記録してもよい。カメラのそれぞれは２セットのデータを与え、データの各セットは二次元画像を表す。２セットのデータは、図ではD1(x1,y1)およびD2(x2,y2)によって示されている、すなわち２つの二次元データ・セットである。前記複数のカメラは異なる配向から画像を取得する。本装置は、異なる配向から取得された画像を入力するための入力Ｉと、決定器１４１とを有する。決定器内において、前記画像が、本発明に基づいてマッチング・ウィンドウ手法を使ってマッチされる。決定器は仮奥行きマップを与え、これが表面フィルタ１４２に送られる。表面フィルタ１４２はさらなる奥行きマップを与える。このさらなる奥行きマップは、突出値拒否／隠蔽検出および画像ベースの穴充填によってさらに改善されてもよい。
【００８０】
割り当て器１５１において、前記ピクセルに対して、前記さらなる奥行きマップ、あるいは最終的な奥行きマップを使ってｚ値が割り当てられる。好ましくは、カメラからのデータがカメラ相互の配向についてのデータを含む、決定器がカメラ相互の配向を決定する手段を有する、あるいはカメラがそのような相互配向を決定器に伝える手段を有する、あるいは決定器がそのようなデータを（たとえば手で）入力するための手段を有する、あるいはカメラのセットアップが固定で相互配向が既知である。カメラによる画像の取得は、好ましくは同期される。本装置は出力OPを有する。出力データ・ストリームD(x,y,z)は、点のxおよびy座標の両方ならびにz座標、すなわち奥行きマップを含むデータ・ストリームである。この出力データ・ストリームD(x,y,z)は、たとえば該データ・ストリームをDVDデータ担体もしくは他の任意のデータ担体上に記録するために、記録装置に送られてもよい。あるいは出力データ・ストリームD(x,y,z)は、三次元画像を表示するための三次元表示装置に送られてもよい。
【００８１】
図１５は、カメラのような記録装置を有する装置を示している。
【００８２】
図１６は、たとえばDVDのようなデータ担体のための入力をもつ装置を示している。該データ担体上に、データD1(x1,y1)およびD2(x2,y2)ならびにカメラ相互配向についてのデータ（D(cam1,cam2)）が記憶されている。本発明に基づく装置は前記データを読み、出力データ・ストリームD(x,y,z)を与える。
【００８３】
本発明に基づく装置の好ましい諸実施形態は、マッチング・ウィンドウが非正方形であるなど、前記方法の上述した好ましい諸実施形態の任意の一つまたは任意の組み合わせに基づいて奥行きマップを決定する手段を有する。
【００８４】
本発明に基づく装置は画像を記録する手段を有していてもよい。すなわち、本装置は、画像を取得するための前記のカメラを含んでいてもよい。ここでは、カメラが画像についてのデータを前述の入力に送る。本装置は、記録装置からデータを受領してもよい。
【００８５】
本発明の概念の範囲内では、「決定器」フィルタなどは広義に理解されるものであり、たとえば記載された決定、選択またはマッチング機能を実行するために設計された任意のハードウェア（決定装置のような）、任意の回路または部分回路、ならびに、本発明に基づく決定、選択またはマッチング動作を実行するよう設計されたまたはプログラムされた任意のソフトウェア（コンピュータ・プログラムまたはサブプログラムまたはコンピュータ・プログラムのセットまたはプログラム・コード）、ならびに、単独でまたは組み合わせでそのように機能するハードウェアおよびソフトウェアの任意の組み合わせを含むものであり、以下に与える例示的な実施形態に制限されることはない。一つのプログラムがいくつかの機能を組み合わせてもよい。
【００８６】
図１７は、本発明に基づく方法の結果を示している。
【００８７】
性能評価のために、我々のアルゴリズムをスチール画像の対（図１７）に対して走らせてみる。最初の二つの画像が左と右の画像であり、最後の図が奥行きマップの画像を与えるもので、グレー値が奥行きの指標になっている。結果は、低テクスチャー領域内での奥行きの抽出および奥行き不連続における高い精度の両方において、非常に良好な性能を示している。低テクスチャー領域内の奥行きの堅牢な再現は、堅牢な表面フィルタの使用および複数の候補から来る冗長性によって許容されるものである。また、表面の暗黙的モデルの使用も重要な因子であった。整合性を検査することによる突出値拒否も、左から右へおよび右から左への奥行き推定値の堅牢性からすると、うまく機能しており、ほとんど隠蔽されたまたは事実上無テクスチャーの領域が検出されている。最後に、画像ベースの後処理段階が、非常に単純であるにもかかわらず、適正なギャップ充填および境界再整列の両方を許容する。画像シーケンスに対する試験は、本発明に基づくアルゴリズムが、高品質の奥行きおよび良好な時間整合性（time  consistency）の両方を与えたことを示した。一方、そのようなシーケンスについては、収束（convergence）が局所的であり、よって初期化が決定的になることからすると、主要な最適化駆動の技法（the  leading  optimization-driven  techniques）はそれほど安定ではないことが立証された。本発明のもう一つの利点は、システムのモジュール的性質である。これは柔軟な実装を許容し、リアルタイムでの稼働につながる最適化の妥協を許容する。
【００８８】
図１８Ａないし図１８Ｄは本発明をさらに例解する。
【００８９】
図１８Ｂには、図１８Ａの左（L）‐右（R）画像対の、図７に示されるような四つの異なる小さな細いウィンドウ（左の二つは水平のウィンドウをもち、右の二つは垂直のウィンドウをもつ）を使ったステレオ・マッチング〔ステレオ照合〕の結果が示されている。得られた仮奥行きマップは予想通り非常にノイズがあるものである。メジアン・フィルタリングの結果が図１８Ｃに示されており、図１８Ｄの本発明の表面フィルタの結果と比較される。このように、図１８Ｄは、本発明に基づく方法によって作られたさらなる奥行きマップを示す。メジアン・フィルタは奥行きマップを過剰に平滑化し、細かな詳細の損失につながることが明らかである。たとえばランプ上には、図１８Ｄでは図１８Ｃより多くの詳細が見える。表面フィルタは他方、このように、ノイズを除去しつつ、元来の奥行きマップからより多くの情報を再現する。画像ベースの後処理のあとの最終的な結果は、メジアン・フィルタについても表面フィルタについても改善された。前記さらなる奥行きマップおよび最終的な奥行きマップがもとからわかっている事実と比較されるとき、表面フィルタはメジアン・フィルタより15%少ない「不良ピクセル」を有している。
【００９０】
まとめると、本発明は次のように記述されうる：
異なる配向から得られた複数の画像から奥行きマップを決定するために、ウィンドウ・ベースのマッチングが使用される。奥行きが決定されるべき画像の諸点について、一組のマッチング・ウィンドウが使用される。仮奥行きマップが生成される。仮奥行きマップでは、各点に対して、二つ以上の候補視差値が帰属させられる。仮奥行きマップは、表面フィルタを使ってフィルタリングされる。それにより、着目点を近傍点についての候補視差値からポイントする単位ベクトルの和のノルムの少なくともｚ成分が最小化される。
【００９１】
本発明はまた、本発明に基づく方法または装置についての何らかのコンピュータ・プログラム・プロダクトにおいても具現される。コンピュータ・プログラム・プロダクトのもとでは、汎用ものもであれ特殊目的のものであれプロセッサが、コマンドをプロセッサに取り込むための一連のローディング・ステップ（これは中間言語および最終的なプロセッサ言語への翻訳のような中間的な変換ステップを含んでいてもよい）後に、発明の特徴的機能のいずれかを実行することができるようにするコマンドの集合の任意の物理的な実現が理解されるべきである。特に、コンピュータ・プログラム・プロダクトは、たとえばディスクまたはテープのような担体上のデータ、メモリ内に存在するデータ、有線または無線のネットワーク接続を通じて伝搬するデータまたは紙の上のプログラム・コードとして実現されてもよい。プログラム・コードは別として、本プログラムのために要求される特徴的なデータがコンピュータ・プログラム・プロダクトとして具現されてもよい。
【００９２】
本方法の機能のために要求されるステップのいくつかは、データ入力および出力ステップのように、コンピュータ・プログラム・プロダクトにおいて記述される代わりに、プロセッサの機能性において既に存在していてもよい。
【００９３】
上述した実施形態は本発明を限定するのではなく例解すること、当業者は付属の請求項の範囲から外れることなく多くの代替的な実施形態を設計できるであろうことを注意しておくべきであろう。
【００９４】
請求項において、括弧に入れられた参照符号があったとしてもその請求項を限定するものと解釈してはならない。
【００９５】
本発明の枠組み内において、多くの変形が可能であることは明らかであろう。本発明が、本稿で上に個別的に示され、説明されてきたことによって限定されないことは、当業者は理解するであろう。本発明は、新規な特徴的な点一つ一つおよび特徴的な点の組み合わせの一つ一つに存する。請求項における参照符号はその保護範囲を限定しない。
【００９６】
たとえば、本方法は、画像の一部分のみについて使用されてもよい。あるいは本発明の方法の異なる諸実施形態が画像の異なる一部分について使用されてもよい。たとえば、画像の中心について一つの実施形態を使い、画像の周辺について別の実施形態を使うのである。
【００９７】
また、前記諸例では、三次元での単位ベクトル、すなわち三つの座標x、y、z座標をもつ単位ベクトルが使用されている。より高次元のベクトルが使用されてもよい：
一例は、空間座標(Px,Py,Pz)および関連する赤、緑、青の色値(Pr,Pg,Pb)を含む六次元ベクトルの使用である。これは増大したベクトル(Px,Py,Pz,Pr,Pg,Pb)を与える。この場合を使うと、今やL-1ノルムについての基準を次のように
【００９８】
【数９】
2010502945.tif 000011
と一般化できる。
【００９９】
また、重みが単位ベクトルに割り当てられるとき、これは視差候補と着目点との間の距離の関数であることができるが、使用されるマッチング・ウィンドウに依存して割り当てられる重みもあってよい。示された諸例で与えられるように配向は異なるが基本的に一様であるマッチング・ウィンドウのセットが使用されるとき、すべての推定が等しい重みである可能性が非常に高い。しかしながら、マッチング・ウィンドウのセットは、大きさまたは形において根本的に異なる複数のマッチング・ウィンドウをもつことができる。一例は、図７に示される型と図１０に示される型の複合されたマッチング・ウィンドウの複合セットを使うことであろう。各点に対して、各サブセットについて４つで、８つの候補視差値が割り当てられることになる。候補視差値の重みはサブセット内では同じであってもよいが、サブセット間では異なっていてもよい。この信頼重みは、異なる推定器での自らの経験に依存してユーザーによって与えられる固定された数であってもよい。
【０１００】
「有する」およびその活用形の使用は、請求項において述べられている以外の要素の存在を排除するものではない。要素の単数形の表現はそのような要素の複数の存在を排除するものではない。
【図１】
2010502945.tif 000012
【図２】
2010502945.tif 000013
【図３】
2010502945.tif 000014
【図４】
2010502945.tif 000015
【図５】
2010502945.tif 000016
【図６】
2010502945.tif 000017
【図７】
2010502945.tif 000018
【図８】
2010502945.tif 000019
【図９】
2010502945.tif 000020
【図１０】
2010502945.tif 000021
【図１１】
2010502945.tif 000022
【図１２】
2010502945.tif 000023
【図１３】
2010502945.tif 000024
【図１４】
2010502945.tif 000025
【図１５】
2010502945.tif 000026
【図１６】
2010502945.tif 000027
【図１７】
2010502945.tif 000028
【図１８Ａ】
2010502945.tif 000029
【図１８Ｂ】
2010502945.tif 000030
【図１８Ｃ】
2010502945.tif 000031
【図１８Ｄ】
2010502945.tif 000032
【手続補正書】
【提出日】平成21年3月5日(2009.3.5)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、異なる配向から得られた複数の画像から、画像のある点についてウィンドウ・ベースのマッチングを使って奥行きマップを決定する方法に関する。本発明は、異なる配向から得られた複数の画像から、画像のある点についてウィンドウ・ベースのマッチングを使って奥行きマップを決定する装置にも関する。
【背景技術】
【０００２】
いくつかの応用について、画像から奥行きマップを決定することが望ましい。そのような応用の例は、対話的に制御可能な配向から見たシーンの画像を計算することを可能にするシステム、画像圧縮、検査などを含む。ステレオ画像から奥行きマップを復元する課題はしばしば、3Dディスプレイ、製造における品質管理、自律的ナビゲーションおよびオブジェクト認識といった幅広い範囲の応用について決定的に重要である。本稿では、画像中のある点の奥行き（depth）とは、視点と、前記点を通りカメラの光学軸に垂直な平面との間の距離を指す。
【０００３】
カメラの視点が第一の視点から第二の視点に動かされるとき、画像点の位置の並進量から画像点の奥行きが決定できる。画像が点投影によって得られる場合、並進はカメラの変位の量に比例し、画像のその部分の奥行きに反比例する。
【０００４】
並進を測定するために、カメラの第一の配向から得られた第一の画像におけるあるピクセルのまわりのあるウィンドウ内のピクセル値が第二の配向から得られた第二の画像におけるあるピクセルのまわりのあるウィンドウ内のピクセル値と比較される、ウィンドウ・ベースのマッチングを使うことが知られている。マッチングは通例、マッチング・ウィンドウ内のピクセルのピクセル値の差の集計（aggregate）を決定することを含む。
【０００５】
適応的ウィンドウを使うことも提案されている。しかしながら、適応的ウィンドウを使うことは、ウィンドウを適応させるために、通例きわめて込み入ったアルゴリズムを必要とする。
【０００６】
ウィンドウ・ベースのマッチングを使って奥行きマップを決定する方法は非特許文献１に記載されている。
【０００７】
既知の方法では、マッチングが実行される画像の各点について、マッチング・ウィンドウが使用され、該マッチング・ウィンドウ内で、着目点の位置が該ウィンドウのすべての点にわたって走査される。マッチング・ウィンドウが着目ピクセルのまわりに非対称的に設定されていてマッチング・ウィンドウがオブジェクト境界をカバーしない場合、境界突出（boundary  overreach）は現れない。着目ピクセルは、マッチング・ウィンドウの全集合にわたって走査される。結果として得られるSSSD（SSDの和［Sum  of  SSD］、ここで、SSDは平方差分和［Sum  of  Squared  differences］）の最小値を見出すことで、前記点についての視差推定値（disparity  estimate）が与えられる。
【０００８】
既知の方法は、境界突出の問題に解決を提供する。しかしながら、その解決はより多数の計算の必要性という代償を伴う。さらに別の問題が生じる：なめらかな視差表面（smooth  disparity  surfaces）は破壊され、そのようななめらかな視差表面に多くの階段状の正方形（stepwise  squares）が観察される。なめらかな視差表面における問題は、既知の方法では、境界検出方法を実装し、境界領域を非境界領域とは異なる仕方で処理することによって対処される。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】奥富正敏ら、「精確なオブジェクト境界およびなめらかな表面を回復するための簡単なステレオ・アルゴリズム」、コンピュータ視覚およびパターン認識2001（CVPR2001）、2001年米国電気電子技術者協会・コンピュータ協会会議集録、第２巻、第II-138‐II-142頁（Masatoshi  Okutomi  et  al.,  "Simple  Stereo  Algorithm  to  Recover  Precise  Object  Boundaries  and  Smooth  Surfaces",  Computer  Vision  and  Pattern  Recognition  2001,  CVPR  2001,  Proceedings  of  the  2001  IEEE  Computer  Society  Conference,  Volume  2,  2001,  pp.  II-138‐II-142,  vol.  2）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、既知の方法は大量の計算パワーおよびかなり複雑なアルゴリズムを必要とする。
【００１１】
なかんづく、比較的信頼できかつ精確な奥行きの推定を提供しつつ、比較的少なめの計算パワーしか要求しない方法を提供することが本発明の一つの目的である。
【課題を解決するための手段】
【００１２】
本発明によれば、少なくとも画像の一部分について、画像の前記一部分の諸点について、一組のマッチング・ウィンドウが使われ、それにより各点についていくつかの候補奥行き値が計算されて、各点に二つ以上の候補奥行き値が割り当てられる仮の奥行きマップを与え、各点について、近傍点の候補奥行き値から前記点の候補奥行き値に向かう単位ベクトルの和のノルムの少なくともｚ成分を最小化することによってさらなる奥行きマップが計算される。
【００１３】
既知の方法は「勝者総取り」戦略に基づいている。すなわち、各点について、単一の最良の視差値が計算される。これは高い精度を要求し、そのことは大量の計算パワーを要求する。そうではあっても、精度はマッチング・ウィンドウの特定の選択次第である。つまり、ある特定の問題がマッチング・ウィンドウの選択に関連付けられる場合、問題は残る。
【００１４】
本発明では異なるアプローチが取られる。各点について、いくつかの候補視差値が最初に一組のマッチング・ウィンドウを使って計算される。
【００１５】
発明者は、ウィンドウ・ベースの技法についてはウィンドウの適正な選択が重要であることを認識するに至った。用いられるマッチング・ウィンドウの大きさが大きければ、これは不正確な境界をもち細かな詳細が失われたぼやけた奥行きマップにつながりうる。他方、小さなウィンドウを使うことは、計算パワーを節減し、良好である一方、ノイズの影響を受けやすい方法につながりうる。比較的小さなウィンドウを用いたマッチングの結果は、ノイズのある奥行きマップであるが、重要な小さな画像特徴を含んでいるものとなる。着目点についての視差値としてSSDまたはSADスコアが最低になるウィンドウの結果を選択するマルチ・ウィンドウ・マッチングへの一般的なアプローチの代わりに、本発明に基づく方法の主要な特徴は、候補を正則化空間（a  regularizing  space）として使っての視差推定値の再計算である。ノイズのある仮奥行きマップが作られる。ここで、各点について、いくつかの候補視差値が計算される。そのような計算のためには、限られた計算パワーしか必要とされない。その後、なめらかにする動作が実行されて、各点がｚ値を与えられる。
【００１６】
「真の視差値」を見出すために候補視差値の平均または中央値を取ることは、有望な結果を与えないことがわかった。しかしながら、再計算のための単位ベクトルを使うと、前記さらなる奥行きマップは良好な結果を与えることがわかった。前記さらなる奥行きマップは、本稿の以下では時に局所的奥行きマップとも呼ばれるが、近傍の諸3D点（近傍内であり、種々のスーパーインポーズされた複数候補データ・セットから来る）からある点をポイントする単位ベクトルを計算し、これらの単位ベクトルの和のノルムの少なくともｚ成分を前記点において最小化する視差を見出すことによって計算される。これは、表面の前記一部分の各点について行われる。「各点」とは、さらなる奥行きマップが作られるべきであるような画像の部分の点を指す。画像の前記一部分についての前記計算内の点の数は、通例ピクセル数と等価である。この場合には各ピクセルにある点が帰される。「各点」は、数学的な意味での、無限にある「各点」を意味するものと誤解すべきではない。近傍とは、本発明の概念の範囲内では、着目点のまわりの所与の範囲を表す。
【００１７】
好ましい諸実施形態では、単位ベクトルの和のノルムが最小化される。関心が、主として前額平行な表面を復元することにある場合、単位ベクトルの差のノルムのｚ成分のみを最小化することが十分な手続きでありうる。
【００１８】
より洗練された諸方法では、近傍点の単位ベクトルの和のノルムのすべての成分が最小化される。
【００１９】
好ましくは、単位ベクトルの和は重み付けされた和である。ここで、計算内での各単位ベクトルについての重みは着目点までの距離の関数である。これは精度を改善することになる。着目点の視差値は、着目点から遠く離れた点よりも近くにある近傍点の視差値に似ている可能性がより高い。
【００２０】
好ましくは、前記一組のマッチングは、着目点がマッチング・ウィンドウに対して離心的に位置するような一つまたは複数のマッチング・ウィンドウを含む。正方形のブロックがマッチング・ウィンドウについて最も一般的に使われる形であるが、マッチング・ウィンドウについての離心的に位置された形は、横または縦の辺といった特定の画像特徴上にロックするためにより好適である。画像中の着目点を中心としていないという事実により、ウィンドウの少なくとも一つが、隠蔽する境界（occluding  boundaries）の近くで適正にマッチすることができる。
【００２１】
好ましくは、平均からある閾値より大きく異なっている単位ベクトルを計算から削除するチェックが実行される。それにより、逸脱した候補視差値、すなわち何らかの計算誤差のために正常な範囲から大きく外れている候補視差値が結果に負の影響を与える可能性が小さくなる。閾値は固定値であってもよいし、他の値に基づいて計算されてもよいし、あるいはスプレッド計算（a  spread  calculation）に関係していてもよい。
【００２２】
好ましくは、前記一組のマッチング・ウィンドウは、マッチング・ウィンドウの実質的に直交する集合である。実質的に直交する（orthogonal）マッチング・ウィンドウとは、ウィンドウ間のピクセルの重なりがウィンドウ当たりのピクセル数の１／４未満であるマッチング・ウィンドウである。
【００２３】
好ましい諸実施形態では、マッチング・ウィンドウの数は４であり、それらのマッチング・ウィンドウは十字を形成する。十字は単純な配置であるが、良好な結果を与えることが示されている。
【００２４】
もう一つの好ましい実施形態では、マッチング・ウィンドウの数は８であり、それらのウィンドウはそれぞれが十字を形成する二つの四つ組（foursome）からなり、一方の四つ組が他方の四つ組のウィンドウの左手バージョンまたは右手バージョンである。マッチング・ウィンドウの一つの四つ組を使うことは、若干の左から右または右から左のバイアスを導入しうる。二つの四つ組を使うことによって、このバイアスは消去できる。
【００２５】
もう一つの実施形態では、マッチング・ウィンドウは実質的に三角形状である。
【００２６】
本発明のこれらおよびその他の利点が以下の図面を使ってより詳細に記述される。
【００２７】
図面は縮尺通りに描かれてはいない。一般に、同一の構成要素は複数の図面において同じ参照符号によって示されている。
【図面の簡単な説明】
【００２８】
【図１】画像の一部分および二つの配向の幾何学を示す図である。
【図２】画像の一部分の画像を示す図である。
【図３】Ａは、奥行きマップを作成する方法のフローチャートである。Ｂは、本発明に基づく方法の一部を例解する図である。
【図４】結果として得られる仮の奥行きマップを、一次元で線に沿って示す図である。
【図５】本発明の方法におけるさらなる段階を示す図である。
【図６】従来技術において記載されている一組のマッチング・ウィンドウを示す図である。
【図７】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図８】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図９】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１０】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１１】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１２】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１３】本発明の方法のために使用可能なマッチング・ウィンドウの組の実施形態を示す図である。
【図１４】本発明に基づく方法を示す図である。
【図１５】本発明に基づく装置を示す図である。
【図１６】本発明に基づく装置を示す図である。
【図１７】本発明に基づく方法の結果を示す図である。
【図１８Ａ】本発明に基づく方法の結果をさらに示す図である。
【図１８Ｂ】本発明に基づく方法の結果をさらに示す図である。
【図１８Ｃ】本発明に基づく方法の結果をさらに示す図である。
【図１８Ｄ】本発明に基づく方法の結果をさらに示す図である。
【発明を実施するための形態】
【００２９】
図１は、画像１０の一部分および二つの配向１２ａ、１２ｂの幾何構造を示している。画像の一部分はたとえば、人物であってもよいし、画像内の他のいかなるオブジェクトであってもよい。本発明は、画像についての奥行きマップを与える方法に関する。奥行きマップとは、オブジェクトの点にｚ値、すなわち奥行き値を帰属させるものと見ることができる。画像１０の一部分を含むシーンの画像が異なる配向１２ａ、１２ｂからの点投影を使って得られるとき、画像の前記部分の上の点１４、１５が見える像の中の位置が、点１４、１５の投影１６ａ、ｂ、１７ａ、ｂである。投影は、点１４、１５から配向１２ａ、１２ｂを通って像平面１８への描線１９ａ〜１９ｄによって図示できる。基本原理を述べるために、配向１２ａ、ｂは像平面１８に平行な面内に選択されているが、本発明は配向１２ａ、ｂのそのような選択に限定されない。これらの線１９ａ〜１９ｄと像平面１８との交点が、画像１０の前記部分の点１４、１５が像において見える位置を示す。
【００３０】
視点１２ａ、１２ｂの変化は、画像の一部分の上の点１４、１５が像平面１８内に見える位置１６ａ、ｂ、１７ａ、ｂの並進につながることを注意しておく。この並進は、視点と前記点との間の奥行き「ｚ」に反比例し、視点の位置の変化量に比例する。結果として、並進は、配向１２ａ、１２ｂからの奥行き「ｚ」が異なる画像１０の前記部分の点１４、１５について、異なることになる。
【００３１】
図２は、画像の一部分が見える領域２２を含む画像２０を示している。画像２０において、画像２０内に見える画像の前記一部分の点が視点の移動に応答して受ける並進を表す並進ベクトル２３ａ、ｂ、２５ａ、ｂが示されている。並進ベクトル２５ａ、ｂは、視点により近い画像の部分の点についてのほうが、視点からより遠い点についてよりも大きくなることを注意しておく。すべての点の奥行きが同じである直線２６に沿っては、並進は同じである。
【００３２】
直線２６に沿った軸およびその直線に垂直な軸をもつ座標系を使うと、点が見える位置の並進の幅「D」はA＋Buに比例する。ここで、uはその点が直線２６に垂直な軸に沿って見える位置の座標である。並進の方向は、視点の動きの方向とは逆である。パラメータ「A」はu＝0における奥行き「Z0」の逆数に比例し、「B」は同様にその奥行きと、見る方向に垂直な、画像の前記一部分の傾き「s」に比例する：B＝c×s/Z0（cは視点の変位、焦点距離および画像のスケールに比例する比例定数）。図１および図２は、二つのカメラが使用される状況を示している。奥行きマップを決定するためには、３つ以上のカメラが使用されてもよい。３つ以上のカメラを使用することは、精度を高め、背景オブジェクトが前景にあるオブジェクトによって隠蔽される可能性を減らす。
【００３３】
図３のＡは、画像について、あるいは画像の一部分について奥行きマップを作成する方法の一部のフローチャートを概略的に示している。
【００３４】
フローチャートの第一および第二のステップ３１、３２では、カメラ光学系が第一および第二の視点にそれぞれ位置される。それらの視点から第一および第二の画像が得られる。
【００３５】
フローチャートの第三のステップ３３では、第一の画像中のあるピクセルが選択される。第四のステップ３４では、そのピクセルについて、マッチング・ウィンドウを使って前記画像間でマッチがみつけられる。
【００３６】
フローチャートのステップ３５では、前記ピクセルに対して、ステップ３４の結果、すなわちウィンドウどうしのマッチを使ってｚ値が割り当てられる。既知の諸方法では、勝者総取りの原則により、各ピクセルに対して、単一の「最良」ｚ値が割り当てられる、すなわち最良マッチが求められ、これが視差値（＝ｚ値）を確立する。高い信頼レベルを与えるために、精度は高くなければならない。これはかなり大きなマッチング・ウィンドウの選択につながる。しかしながら、そのような比較的大きなマッチング・ウィンドウは、そのサイズに起因して小さな詳細を捉えることができない。
【００３７】
図３のＢは、本発明に基づく方法を示している。着目点について一つの視差値を与えるのではなく、ある着目点について、比較的小さな離心マッチング・ウィンドウのセットが使われ、各点についていくつかの候補視差値（ｚ値１、ｚ値２、ｚ値３など）が与えられる。いかなる点についても確定的な決断はされず、各点に対して二つ以上の候補視差値が割り当てられる。すべての候補視差値が組み合わされたものが、ノイズのある奥行きマップを与える。
【００３８】
図４は、一次元において線に沿って候補視差（すなわちｚ値）が示される、結果として得られる仮の奥行きマップを示している。この例では、二つの異なる色についての視差値が計算されている。二つの異なる値は概略的に黒丸および白丸で示されている。
【００３９】
図５は、本発明の方法内の次のステップを示している。
【００４０】
ノイズのあるサンプルからある点について実際の奥行き、すなわち実際の視差値を推定するために、図５に示された方式が使用される。各ピクセルについて、再構成されたサンプルから候補点をポイントする単位ベクトルの和のノルムを最小にする奥行き値が計算される。奥行き値が表面から遠い場合には、これらのベクトルの和のノルムは大きいが、表面に当たると、最小または最小近くであると期待される。本記述の枠組み内では、これは「表面フィルタ（surface  filter）」とも呼ばれる。すなわち、仮のノイズのある奥行きマップに対して特定的なフィルタリングが行われるのである。仮のノイズのある奥行きマップは、本方法が使われる対象となる画像の前記一部分における各点について、いくつかの候補視差値を含む。単位ベクトルの和自身もベクトルである。
【００４１】
ベクトルのノルムは、数学的には、このベクトルの「強さ」として理解できる。本発明の方法では、これらすべての単位ベクトルの和であるこのベクトルの強さが最小化される。この強さが小さい場合には表面マップに達する。さて、ベクトルの強さを測るいくつかの方法があるが、最も一般的なのはLpノルムである。これは次の公式で記述される：
【００４２】
【数１】
2010502945.tif 000033
個別的な場合として：
・L2ノルムまたはユークリッド・ノルム（p＝2）
【００４３】
【数２】
2010502945.tif 000034
・L1ノルム（p＝1）
【００４４】
【数３】
2010502945.tif 000035
・L∞と呼ばれる極限の場合で、
【００４５】
【数４】
2010502945.tif 000036
として定義される場合、がある。
【００４６】
数学的には、サイトiのまわりの小さな近傍N内での単位ベクトルの和のL-1ノルムが視差diに関して最小化される（下記にL-1ノルムを与えておく）。
【００４７】
【数５】
2010502945.tif 000037
ここで、Pi＝（Pix,Piy,Pz(di)）は最適化されるべき視差値diに対応する再構成された点（正則（regular）格子上にいるのでｚ成分だけがdiに依存する）、Pj＝（Pjx,Pjy,Pjz）は異なるウィンドウ配位によって推定される視差に対応する再構成された点である。近傍Nの大きさは小さく保つことができ、一方で、異なる奥行き推定器（異なるウィンドウ・マッチング配位）から来る冗長さのために、表面抽出は堅牢なままである。主として前額平行な表面を復元することに関心があるのであれば、(1)のｚ成分だけを最小化することができる。これは、計算コストを下げる。
【００４８】
近傍Nは、点に重みを割り当てることによって設定されることもできる。ここで、重みは点の間の距離の関数である。
【００４９】
【数６】
2010502945.tif 000038
ここで、W(Pi)は、点Piと点Pとの間の距離の関数で、距離が増すにつれて値が減少する。
【００５０】
計算は、表面の各点についてなされる。そこにあるいくつの点が計算にはいるかは、通例、ピクセル数に等しい。すなわち、各ピクセルに点が割り当てられ、その点について、単位ベクトルの和のノルムを最小化することによってｚ値が計算される。これは、計算を比較的簡単にする。
【００５１】
これは、視差値に対して平滑化フィルタ効果をもつことになる。着目点のまわりのある範囲の点が使われるので、これは、本発明の枠組み内では、表面フィルタ（surface  filter）と呼ばれる。
【００５２】
完全性のため、やはり使用可能なL-2ノルムも与えておく：
【００５３】
【数７】
2010502945.tif 000039
L-2ノルム＝{S2(di)}1/2である。
【００５４】
さらなる実施形態では、画像制約条件が使われる。
【００５５】
表面フィルタは、堅牢に視差を抽出するが、奥行き不連続の過剰な平滑化は避けることを示すことができる。そして、小さな詳細のよりよい復元のために、画像マッチング制約条件（image-matching  constraint）も含める。この条件のために、いかなる局所的な画像類似性基準を使うこともできる。たとえば、非常に小さなウィンドウ上でのSSDを採用することができる。局所的に最小化される最終的な基準は：
E(i)＝S(di)＋λSSD(di)        (2)
である。ここで、λはなめらかな視差領域抽出を精確な境界復元とバランスさせる因子である。最適化は、単に最小および最大の許容される離散的視差値の間を走査してE(i)を最小化する視差を見出すことによって実行される。
【００５６】
ある意味では、これは、ある点についてのSSDと近傍点からの単位ベクトルの和のノルムの組み合わせを最小化する組み合わされた方法と見ることができる。単位ベクトルの和のノルムは最小化されるが、前記和のノルムにその点におけるSSDを加えたものによって与えられるE(i)が最小化されるという制約条件のもとでである。
【００５７】
図６は、非特許文献１に記載される一組のマッチング・ウィンドウを示している。25個のウィンドウが使用され、各ウィンドウは25個のピクセルを含む。「着目点」と呼ばれるｚ値が決定されようとしているピクセル６１は黒い正方形によって表されている。5×5ピクセルの標準的なマッチング・ウィンドウが使用され、着目ピクセルが該標準的なウィンドウのすべての点にわたって走査される。これは25個のマッチング・ウィンドウ６２を与える。図４では、これら25個のマッチング・ウィンドウは灰色の正方形からなる5×5の領域によって表されている。大量の計算を実行する必要がある。
【００５８】
図７は、本発明の方法および装置において使用される一組のマッチング・ウィンドウを示している。マッチング・ウィンドウの間の重なりは小さい。
【００５９】
図８は、ウィンドウの組のさらなる例を示している。
【００６０】
図９は、本発明に基づく方法および装置で使用されるウィンドウの組のさらにもう一つの例を示している。この場合、４つのマッチング・ウィンドウからなる組二つが使用される。
【００６１】
図１０は、本発明に基づく方法および装置で使用されるウィンドウの組のさらにもう一つの例を示している。
【００６２】
図１１は、さらなる例を示している。
【００６３】
図１２および図１３は本発明のさらなる実施形態を示している。これらの例では、８つの三角形ウィンドウの組が使用される。
【００６４】
マッチング・ウィンドウの示された例のいずれも正方形ではないことを注意しておく。好ましくは、マッチング・ウィンドウは非正方形である。これは、長方形もしくは三角形のマッチング・ウィンドウといった非正方形の形をしたウィンドウは、横および縦の辺（図１１に示されるような長方形マッチング・ウィンドウまたは三角形について）あるいは45度の角度の辺（三角形マッチング・ウィンドウについて）といった特定の画像特徴の上にロックするのにより好適だからである。
【００６５】
図７、図８、図９に示される例は、実質的に長方形の形のマッチング・ウィンドウを示す。ウィンドウは互いに直交して配向され、組み合わさって十字形を形成する。これらのマッチング・ウィンドウは、図９に示されるマッチング・ウィンドウのように、縦および横の方向に沿った辺を示す。縦および横の方向に沿って配向されたそのような長方形の形のマッチング・ウィンドウが最も好ましい。
【００６６】
好ましくは、諸マッチング・ウィンドウは同じ形をもち、形の四つ組を形成し、前記形は配向され、各マッチング・ウィンドウの形は別のマッチング・ウィンドウの形と関係しており、別のマッチング・ウィンドウの90度、180度または270度回転によって得られるものであってもよい。図７ないし図１３の諸セットはそのような配置を示している。ここで、マッチング・ウィンドウの各セットは、一つ（図７、図８、図９、図１０）または二つ（図９、図１２）の基本配向形から、それを90度、180度および270度回転させて他の形を与えることで導出されている。好ましくは、視差候補を生成するために互いに直交する方向に配向された小さな比較的細いマッチング・ウィンドウを採用することによってバランスが取られる。
【００６７】
この方式は、仮奥行きマップに基づいて、さらなる奥行きマップを与える。
【００６８】
計算は、いくつかの好ましい改良によってさらに最適化されうる。
【００６９】
・S(D)の計算において、平均値からある閾値より大きく異なる単位ベクトルをS(D)の計算から削除するチェックが実行される。逸脱した候補視差値、すなわち何らかの計算誤差に起因する候補視差値が結果に負の影響を与える可能性が小さくなる。閾値は固定値であってもよいし、他の値に基づいて計算されてもよいし、あるいはスプレッド計算（a  spread  calculation）に関係していてもよい。
【００７０】
・偽のマッチを拒否し、隠蔽された領域を検出するために種々の方式が可能である。ある簡単な方式は、ストレートな左‐右／右‐左整合性チェックである。これは、得られた対応の一意性を保証し、隠蔽領域のラベル付けを許容する。
【００７１】
・画像ベースの後処理
突出値（outlier）拒否および隠蔽検出は前記さらなる奥行きマップにおける穴、すなわち視差値がない領域を生じることになる。突出値拒否および隠蔽検出ステップから帰結する穴を埋めるため、我々は色に基づく平均化を使う。これは、我々のサイト（Ri,Gi,Bi）での色に近い色ピクセルに対応する視差の平均（局所的な近傍内での）を計算することからなる。ある穴におけるサイトiにおける奥行きを再計算するために非線形フィルタが使用されることができる。
【００７２】
【数８】
2010502945.tif 000040
ここで、TCは色差閾値である。
【００７３】
Σjwij＝0の場合については、古い奥行き値が保持される。
【００７４】
このフィルタは、逐次反復的に使用されることができ、奥行きマップの境界を対応する色画像の境界と再整列させるという利点がある。これは３Ｄレンダリング用途のためには非常に重要である。色差閾値を含める選択は、実際の画像不連続に一致する鋭い奥行き不連続をもちたいという意向によって要求されるものである。実際上、この選択はうまく機能することが証明されている。
【００７５】
図１４は、本発明に基づく方法をより詳細に示している。
【００７６】
図１４は、４つのモジュール１４１〜１４４を示している。最初の二つのモジュール１４１および１４２は最も広い範囲における本発明の方法の一部である。あとの二つのモジュール１４３および１４４は、好ましい実施形態の一部であり、任意的である。
【００７７】
第一のモジュール１４１に対して、左および右の画像のデータが、あるいは画像が二つより多い視点から撮られる場合にはさまざまな視点からの画像データが与えられる。このモジュールでは、ウィンドウ・ベースのマッチングを使って仮奥行きマップが生成される。この仮奥行きマップは、各点について二つ以上の候補視差値を含むものであり、表面フィルタ・モジュール１４２に送られる。表面フィルタ・モジュールは、前記点を近傍点についての候補視差値からポイントする単位ベクトルの和のノルムの少なくともｚ成分を最小化することによって、表面フィルタを仮奥行きマップに適用する。これはさらなる奥行きマップを提供する。任意的であるさらなるモジュール１４３および１４４は、突出値／隠蔽検出およびその後の穴充填を提供する。最終産物は最終的な奥行きマップである。
【００７８】
本発明に基づく装置は、異なる配向から得られた画像データを入力するための入力と、前記入力によって受領された画像データから前記画像のある点についてウィンドウ・ベースのマッチングを使って仮奥行きマップを決定する決定器（１４２）とを有する。ここで、前記決定器においては、一組のマッチング・ウィンドウが前記画像の前記点について使用されて、前記諸点について候補視差値を生成する。ここで、前記一組のマッチング・ウィンドウは前記諸点に関して離心的に位置されており、当該装置はさらに、各点について、前記点を近傍点についての候補視差値からポイントする単位ベクトルの和のノルムの少なくともｚ成分を最小化することによって、仮奥行きマップに基づいてさらなる奥行きマップを提供するよう構成されている表面フィルタ（１４２）を有する。
【００７９】
図１５は、本発明に基づく装置を示している。図１５では立方体によって表現されているあるオブジェクトについて、二つのカメラによって画像が取得される。この例では二つのカメラが示されているが、本装置は三つ以上のカメラを有していてもよい。カメラはカラー画像または白黒画像またはＸ線画像または赤外線画像を記録してもよい。カメラのそれぞれは２セットのデータを与え、データの各セットは二次元画像を表す。２セットのデータは、図ではD1(x1,y1)およびD2(x2,y2)によって示されている、すなわち２つの二次元データ・セットである。前記複数のカメラは異なる配向から画像を取得する。本装置は、異なる配向から取得された画像を入力するための入力Ｉと、決定器１４１とを有する。決定器内において、前記画像が、本発明に基づいてマッチング・ウィンドウ手法を使ってマッチされる。決定器は仮奥行きマップを与え、これが表面フィルタ１４２に送られる。表面フィルタ１４２はさらなる奥行きマップを与える。このさらなる奥行きマップは、突出値拒否／隠蔽検出および画像ベースの穴充填によってさらに改善されてもよい。
【００８０】
割り当て器１５１において、前記ピクセルに対して、前記さらなる奥行きマップ、あるいは最終的な奥行きマップを使ってｚ値が割り当てられる。好ましくは、カメラからのデータがカメラ相互の配向についてのデータを含む、決定器がカメラ相互の配向を決定する手段を有する、あるいはカメラがそのような相互配向を決定器に伝える手段を有する、あるいは決定器がそのようなデータを（たとえば手で）入力するための手段を有する、あるいはカメラのセットアップが固定で相互配向が既知である。カメラによる画像の取得は、好ましくは同期される。本装置は出力OPを有する。出力データ・ストリームD(x,y,z)は、点のxおよびy座標の両方ならびにz座標、すなわち奥行きマップを含むデータ・ストリームである。この出力データ・ストリームD(x,y,z)は、たとえば該データ・ストリームをDVDデータ担体もしくは他の任意のデータ担体上に記録するために、記録装置に送られてもよい。あるいは出力データ・ストリームD(x,y,z)は、三次元画像を表示するための三次元表示装置に送られてもよい。
【００８１】
図１５は、カメラのような記録装置を有する装置を示している。
【００８２】
図１６は、たとえばDVDのようなデータ担体のための入力をもつ装置を示している。該データ担体上に、データD1(x1,y1)およびD2(x2,y2)ならびにカメラ相互配向についてのデータ（D(cam1,cam2)）が記憶されている。本発明に基づく装置は前記データを読み、出力データ・ストリームD(x,y,z)を与える。
【００８３】
本発明に基づく装置の好ましい諸実施形態は、マッチング・ウィンドウが非正方形であるなど、前記方法の上述した好ましい諸実施形態の任意の一つまたは任意の組み合わせに基づいて奥行きマップを決定する手段を有する。
【００８４】
本発明に基づく装置は画像を記録する手段を有していてもよい。すなわち、本装置は、画像を取得するための前記のカメラを含んでいてもよい。ここでは、カメラが画像についてのデータを前述の入力に送る。本装置は、記録装置からデータを受領してもよい。
【００８５】
本発明の概念の範囲内では、「決定器」フィルタなどは広義に理解されるものであり、たとえば記載された決定、選択またはマッチング機能を実行するために設計された任意のハードウェア（決定装置のような）、任意の回路または部分回路、ならびに、本発明に基づく決定、選択またはマッチング動作を実行するよう設計されたまたはプログラムされた任意のソフトウェア（コンピュータ・プログラムまたはサブプログラムまたはコンピュータ・プログラムのセットまたはプログラム・コード）、ならびに、単独でまたは組み合わせでそのように機能するハードウェアおよびソフトウェアの任意の組み合わせを含むものであり、以下に与える例示的な実施形態に制限されることはない。一つのプログラムがいくつかの機能を組み合わせてもよい。
【００８６】
図１７は、本発明に基づく方法の結果を示している。
【００８７】
性能評価のために、我々のアルゴリズムをスチール画像の対（図１７）に対して走らせてみる。最初の二つの画像が左と右の画像であり、最後の図が奥行きマップの画像を与えるもので、グレー値が奥行きの指標になっている。結果は、低テクスチャー領域内での奥行きの抽出および奥行き不連続における高い精度の両方において、非常に良好な性能を示している。低テクスチャー領域内の奥行きの堅牢な再現は、堅牢な表面フィルタの使用および複数の候補から来る冗長性によって許容されるものである。また、表面の暗黙的モデルの使用も重要な因子であった。整合性を検査することによる突出値拒否も、左から右へおよび右から左への奥行き推定値の堅牢性からすると、うまく機能しており、ほとんど隠蔽されたまたは事実上無テクスチャーの領域が検出されている。最後に、画像ベースの後処理段階が、非常に単純であるにもかかわらず、適正なギャップ充填および境界再整列の両方を許容する。画像シーケンスに対する試験は、本発明に基づくアルゴリズムが、高品質の奥行きおよび良好な時間整合性（time  consistency）の両方を与えたことを示した。一方、そのようなシーケンスについては、収束（convergence）が局所的であり、よって初期化が決定的になることからすると、主要な最適化駆動の技法（the  leading  optimization-driven  techniques）はそれほど安定ではないことが立証された。本発明のもう一つの利点は、システムのモジュール的性質である。これは柔軟な実装を許容し、リアルタイムでの稼働につながる最適化の妥協を許容する。
【００８８】
図１８Ａないし図１８Ｄは本発明をさらに例解する。
【００８９】
図１８Ｂには、図１８Ａの左（L）‐右（R）画像対の、図７に示されるような四つの異なる小さな細いウィンドウ（左の二つは水平のウィンドウをもち、右の二つは垂直のウィンドウをもつ）を使ったステレオ・マッチング〔ステレオ照合〕の結果が示されている。得られた仮奥行きマップは予想通り非常にノイズがあるものである。メジアン・フィルタリングの結果が図１８Ｃに示されており、図１８Ｄの本発明の表面フィルタの結果と比較される。このように、図１８Ｄは、本発明に基づく方法によって作られたさらなる奥行きマップを示す。メジアン・フィルタは奥行きマップを過剰に平滑化し、細かな詳細の損失につながることが明らかである。たとえばランプ上には、図１８Ｄでは図１８Ｃより多くの詳細が見える。表面フィルタは他方、このように、ノイズを除去しつつ、元来の奥行きマップからより多くの情報を再現する。画像ベースの後処理のあとの最終的な結果は、メジアン・フィルタについても表面フィルタについても改善された。前記さらなる奥行きマップおよび最終的な奥行きマップがもとからわかっている事実と比較されるとき、表面フィルタはメジアン・フィルタより15%少ない「不良ピクセル」を有している。
【００９０】
まとめると、本発明は次のように記述されうる：
異なる配向から得られた複数の画像から奥行きマップを決定するために、ウィンドウ・ベースのマッチングが使用される。奥行きが決定されるべき画像の諸点について、一組のマッチング・ウィンドウが使用される。仮奥行きマップが生成される。仮奥行きマップでは、各点に対して、二つ以上の候補視差値が帰属させられる。仮奥行きマップは、表面フィルタを使ってフィルタリングされる。それにより、着目点を近傍点についての候補視差値からポイントする単位ベクトルの和のノルムの少なくともｚ成分が最小化される。
【００９１】
本発明はまた、本発明に基づく方法または装置についての何らかのコンピュータ・プログラム・プロダクトにおいても具現される。コンピュータ・プログラム・プロダクトのもとでは、汎用ものもであれ特殊目的のものであれプロセッサが、コマンドをプロセッサに取り込むための一連のローディング・ステップ（これは中間言語および最終的なプロセッサ言語への翻訳のような中間的な変換ステップを含んでいてもよい）後に、発明の特徴的機能のいずれかを実行することができるようにするコマンドの集合の任意の物理的な実現が理解されるべきである。特に、コンピュータ・プログラム・プロダクトは、たとえばディスクまたはテープのような担体上のデータ、メモリ内に存在するデータ、有線または無線のネットワーク接続を通じて伝搬するデータまたは紙の上のプログラム・コードとして実現されてもよい。プログラム・コードは別として、本プログラムのために要求される特徴的なデータがコンピュータ・プログラム・プロダクトとして具現されてもよい。
【００９２】
本方法の機能のために要求されるステップのいくつかは、データ入力および出力ステップのように、コンピュータ・プログラム・プロダクトにおいて記述される代わりに、プロセッサの機能性において既に存在していてもよい。
【００９３】
上述した実施形態は本発明を限定するのではなく例解すること、当業者は付属の請求項の範囲から外れることなく多くの代替的な実施形態を設計できるであろうことを注意しておくべきであろう。
【００９４】
請求項において、括弧に入れられた参照符号があったとしてもその請求項を限定するものと解釈してはならない。
【００９５】
本発明の枠組み内において、多くの変形が可能であることは明らかであろう。本発明が、本稿で上に個別的に示され、説明されてきたことによって限定されないことは、当業者は理解するであろう。本発明は、新規な特徴的な点一つ一つおよび特徴的な点の組み合わせの一つ一つに存する。請求項における参照符号はその保護範囲を限定しない。
【００９６】
たとえば、本方法は、画像の一部分のみについて使用されてもよい。あるいは本発明の方法の異なる諸実施形態が画像の異なる一部分について使用されてもよい。たとえば、画像の中心について一つの実施形態を使い、画像の周辺について別の実施形態を使うのである。
【００９７】
また、前記諸例では、三次元での単位ベクトル、すなわち三つの座標x、y、z座標をもつ単位ベクトルが使用されている。より高次元のベクトルが使用されてもよい：
一例は、空間座標(Px,Py,Pz)および関連する赤、緑、青の色値(Pr,Pg,Pb)を含む六次元ベクトルの使用である。これは増大したベクトル(Px,Py,Pz,Pr,Pg,Pb)を与える。この場合を使うと、今やL-1ノルムについての基準を次のように
【００９８】
【数９】
2010502945.tif 000041
と一般化できる。
【００９９】
また、重みが単位ベクトルに割り当てられるとき、これは視差候補と着目点との間の距離の関数であることができるが、使用されるマッチング・ウィンドウに依存して割り当てられる重みもあってよい。示された諸例で与えられるように配向は異なるが基本的に一様であるマッチング・ウィンドウのセットが使用されるとき、すべての推定が等しい重みである可能性が非常に高い。しかしながら、マッチング・ウィンドウのセットは、大きさまたは形において根本的に異なる複数のマッチング・ウィンドウをもつことができる。一例は、図７に示される型と図１０に示される型の複合されたマッチング・ウィンドウの複合セットを使うことであろう。各点に対して、各サブセットについて４つで、８つの候補視差値が割り当てられることになる。候補視差値の重みはサブセット内では同じであってもよいが、サブセット間では異なっていてもよい。この信頼重みは、異なる推定器での自らの経験に依存してユーザーによって与えられる固定された数であってもよい。
【０１００】
「有する」およびその活用形の使用は、請求項において述べられている以外の要素の存在を排除するものではない。要素の単数形の表現はそのような要素の複数の存在を排除するものではない。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の異なる配向から得られた画像から、画像の点についてウィンドウ・ベースのマッチングを使って奥行きマップを決定する方法であって、少なくとも画像の一部分について、画像の前記一部分の点について、一組のマッチング・ウィンドウが使われ、それにより各点についていくつかの候補奥行き値が計算されて、各点に二つ以上の候補奥行き値が割り当てられる仮の奥行きマップを与え、各点について、近傍点の候補奥行き値から前記点の候補奥行き値に向かう単位ベクトルの和のノルムの少なくともｚ成分を最小化することによってさらなる奥行きマップが計算される、方法。
【請求項２】
近傍点の単位ベクトルの和のノルムのすべての成分が最小化される、請求項１記載の方法。
【請求項３】
前記一組のマッチングが、着目点がマッチング・ウィンドウに対して離心的に位置するような一つまたは複数のマッチング・ウィンドウを含む、請求項１記載の方法。
【請求項４】
前記単位ベクトルの和は重み付けされた和であり、計算内での各単位ベクトルについての重みは着目点までの距離の関数である、請求項１ないし３のうちいずれか一項記載の方法。
【請求項５】
平均からある閾値より大きく異なっている単位ベクトルを計算から削除するチェックが実行される、請求項１ないし４のうちいずれか一項記載の方法。
【請求項６】
前記一組のマッチング・ウィンドウは、マッチング・ウィンドウの直交する集合である、請求項１ないし５のうちいずれか一項記載の方法。
【請求項７】
マッチング・ウィンドウの数は４であり、該マッチング・ウィンドウは十字を形成する、請求項６記載の方法。
【請求項８】
マッチング・ウィンドウの数は８であり、該ウィンドウは二つの四つ組からなり、一方の四つ組は他方の四つ組をなす諸ウィンドウの左手バージョンまたは右手バージョンであり、各四つ組が十字をなす、請求項７記載の方法。
【請求項９】
前記マッチング・ウィンドウが三角形状である、請求項６記載の方法。
【請求項１０】
前記さらなる奥行きマップに対して突出値拒否／隠蔽検出が実行される、請求項１ないし９のうちいずれか一項記載の方法。
【請求項１１】
前記さらなる奥行きマップに対して画像ベースの穴重点が実行される、請求項１０記載の方法。
【請求項１２】
当該プログラムがコンピュータ上で走らされたときに請求項１ないし１１のうちいずれか一項記載の方法を実行するためのプログラム・コード手段を有するコンピュータ・プログラム。
【請求項１３】
請求項１ないし１１のうちいずれか一項記載の方法を実行するための、コンピュータ可読媒体上に記憶されたプログラム・コード手段を有するコンピュータ・プログラム。
【請求項１４】
複数の異なる配向から得られた画像データを入力するための入力と、前記入力によって受領された画像データから、前記画像のある点についてウィンドウ・ベースのマッチングを使って仮奥行きマップを決定する決定器とを有する装置であって、前記決定器においては、一組のマッチング・ウィンドウが前記画像の前記点について使用されて、前記諸点について候補奥行き値が生成され、当該装置はさらに、前記仮奥行きマップに基づいて、各点について、近傍点の候補奥行き値から前記点の候補奥行き値に向かう単位ベクトルの和のノルムの少なくともｚ成分を最小化することによって、さらなる奥行きマップを提供するよう構成されている表面フィルタを有する、装置。
【請求項１５】
前記表面フィルタが近傍点の単位ベクトルの和のノルムのすべての成分を最小化するよう構成されている、請求項１４記載の装置。
【請求項１６】
前記決定器が、前記一組のマッチングが、着目点がマッチング・ウィンドウに対して離心的に位置するような一つまたは複数のマッチング・ウィンドウを含むよう構成されている、請求項１４記載の装置。
【請求項１７】
前記表面フィルタが、前記単位ベクトルの和は重み付けされた和であり、計算内での各単位ベクトルについての重みは着目点までの距離の関数であるよう構成されている、請求項１４記載の装置。
【請求項１８】
前記表面フィルタが、平均からある閾値より大きく異なっている単位ベクトルを計算から削除するチェックが実行されるよう構成される、請求項１４記載の装置。
【請求項１９】
当該装置が画像を記録する手段を有する、請求項１４記載の装置。
【国際調査報告】
2010502945.tif 000042
2010502945.tif 000043
2010502945.tif 000044