【手続補正書】
【提出日】平成18年7月5日(2006.7.5)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】明細書
【発明の名称】光学的に深さを決定する方法及び装置
【特許請求の範囲】
【請求項１】
被写体の画像中に見える曲面片の視認深さを光学的に決定する方法であって、
異なる視点から見た前記曲面片を含む第１及び第２の画像を得る工程と、
利用可能な深さ値を前記曲面片と関連付ける工程であって、これらの利用可能な深さ値の各々は第１の画像の点と第２の画像の点との間の対応を予測するもので、これら対応する点が曲面片の同一の位置を見せるものである工程と、
前記利用可能な深さ値の中から、対応する点における第１の画像の画素値と第２の画像の画素値との間に差の集合が最小になる最良の深さ値を検索する工程と
を具える深さ決定方法において、
前記検索は、曲面片についての深さ及び向きの値の利用可能な組合せの中における最良の深さ及び向きの値の組合せについて行い、各利用可能な組合せが前記対応を深さ及び向きの関数として予測し、異なる利用可能な組合せが異なる向きを含むことを特徴とする深さ決定方法。
【請求項２】
請求項１に記載の方法において、
第１の画像の予め定めた第１の領域を取り出す工程と、
前記第１の領域の第１の点の予め定めた組を取り出す工程と、
深さ及び向きの利用可能な組の各々について、前記第１の点と対応する第２の画像中の第２の点を計算し、前記第１及び第２の点について第１の画像の画素値と第２の画像の画素値との間の差の集合を計算する工程と、
差の集合が最小になる深さ及び向きの値の組を選択する工程とを具える方法。
【請求項３】
請求項２に記載の方法において、
請求項２に記載の前記方法を、前記第１の領域に対して、この第１の画像をカバーするグリッド状ブロックの各ブロックを用いてそれぞれに繰り返し適用する方法。
【請求項４】
請求項１又は２に記載の方法において、前記深さ及び向き値の利用可能な組合せが、深さ及び向き値の全ての取り得る組合せの適当なサブセットを形成し、前記利用可能な組合せが、第１の画像の前記曲面片が見られる領域と隣接する領域に対して最良の組合せとして見出された組合せを含ませることにより選択される方法。
【請求項５】
請求項２に記載の方法において、
以前に得られた深さ及び向きの組合せが、前記領域について、第１の画像及び第２の画像の曲面片の同一の位置を見る点の変位から評価され、前記深さ及び向き値の利用可能な組合せが、深さ及び向き値の全ての取り得る組合せの適当なサブセットを形成し、利用可能な組合せが前記以前に得られた深さ及び向きの組合せを含ませることにより選択される方法。
【請求項６】
視認深さを光学的に決定する装置であって、
異なる視点から見た曲面片を含む第１及び第２のディジタル化された画像を得るための画像形成回路と、
最良の深さ値を検索する検索ユニットであって、当該検索ユニットは利用可能な深さ値を曲面片と関連付け、各利用可能な深さ値は第１の画像の点と第２の画像の点との間の対応を予測させるもので、対応する点は前記曲面片の同一の位置を見せるものであり、当該検索ユニットは、前記利用可能な深さ値の中から、対応する点における第１の画像の画素値と第２の画像の画素値との間に差の集合が最小になる最良の深さ値を検索する当該検索ユニットと
を具える深さ決定装置において、
前記検索ユニットは、曲面片についての深さ及び向きの値の利用可能な組合せの中から最良の深さ及び向きの値の組合せを検索し、各利用可能な組合せが深さ及び向きの関数として前記対応を予測し、異なる利用可能な組合せが異なる向きを含むように構成されていることを特徴とする深さ決定装置。
【請求項７】
請求項６に記載の装置において、
第１の画像の予め定めた第１の領域を取り出し、
前記第１の領域の第１の点の予め定めた組を取り出し、
深さ及び向きの利用可能な組の各々について、前記第１の点と対応する第２の画像中の第２の点を計算し、前記第１及び第２の点のそれぞれについて第１の画像の画素値と第２の画像の画素値との間の差の集合を計算し、
差の集合が最小になる深さ及び向きの値の組を選択するように構成されている前記検索ユニットを具える装置。
【請求項８】
請求項６に記載の装置において
前記検索ユニットが、前記第１の領域として、第１の画像をカバーするグリッド状ブロックの各ブロックを取り出すようになっている装置。
【請求項９】
請求項６又は７に記載の装置において、
前記深さ及び向き値の利用可能な組合せが、深さ及び向き値の全ての取り得る組合せの適当なサブセットを形成し、前記検索ユニットが、第１の画像の前記曲面片が見られる領域と隣接する領域に対して最良の組合せとして見出された組合せを含ませることにより前記利用可能な組合せを選択する装置。
【請求項１０】
請求項６に記載の装置において、
以前に得られた深さ及び向きの組合せが、前記領域について、第１の画像及び第２の画像の曲面片の同一の位置を見る点の変位から評価され、前記深さ及び向き値の利用可能な組合せが、深さ及び向き値の全ての取り得る組合せの適当なサブセットを形成し、利用可能な組合せが前記以前に得られた深さ及び向きの組合せを含ませることにより選択されるようになっている装置。
【発明の詳細な説明】
【０００１】
補正は、種々の視点得られた画像から被写体の曲面片の視認深さを光学的に決定する請求項１の前段部分に記載方法に関するものである。
【０００２】
多数の用途において、画像中で見られる曲面片の深さを決定することが望まれている。このような用途の例として、対話的に制御可能な視点から見た被写体の画像を計算できるシステム、画像圧縮、検査等が含まれる。本明細書において、曲面片上の点の深さは、当該点を通りカメラ光軸と直交する面と視点との間の距離を意味する。
【０００３】
カメラの視点が第１の視点から第２の視点に移動すると、曲面片の深さはその曲面片が見える画像領域の位置の並進量から計算することができる。画像が点投影により得られる場合、並進量はカメラの変位量に比例し曲面片の深さに反比例する。
【０００４】
並進を測定するため、第１の視点から得られた第１の画像中の第１の画像領域の画素値を、第２の視点から得られた第２の画像中の並進された画像領域の画素値に整合させることが知られている。この整合は、第１の画像領域の画素値と別の領域の画素値との間の差の集合を決定することを含んでいる。これは、第２の画像の種々の位置における別の多数の領域について繰り返される。これらの位置の中から、差の測定値が差の集合が最小になることを示す１個の位置が選択される。
【０００５】
曲面片が小さい場合或いは曲面片がカメラ光軸と直交する面内に存在する場合には、第１の画像領域の画素値と、整合性の並進した画像領域の画素値との間の測定値の差は、ほぼ完全な整合を示す。しかし、カメラ光軸と直交する面内に存在しない大きな曲面片では完全な整合が得られず、小さな曲面片にセグメント化されこれら小さな曲面片について計算される深さ値の間に不連続を生ずる傾向がある。
【０００６】
本発明の目的は、とりわけ、カメラの光軸と直交する面内に存在しない一層大きな曲面片の深さの評価の信頼性及び精度を改良することにある。
【０００７】
本発明による方法は、請求項１に記載された特徴部分により特徴付けられる。本発明においては、曲面片について深さ値及び向き値の両方の組合せについて検索する（曲面片の深さは、例えば曲面片上の特定点の深さとする）。各組合せは第１の画像の画像点と第２の画像の画像点との間の特有の対応性の基礎となる。この対応性は、対応する点における画素値の差の集合を計算することによりテストされる。深さと向きの最良の組合せが得られると、カメラの光軸と直交する面内に存在しない大きな曲面片についてもほぼ完全な整合が可能になる。つまり、大きな曲面片が小さな曲面片にセグメント化される理由がなくなる。
【０００８】
好ましくは、第１の画像中の画素の方形ブロックのような予め定めた領域を取り出すことにより曲面片を選択する。この場合、曲面片について事前に仮定をおく必要はない。各領域毎に、その領域に見える曲面片の深さ及び向きの取り得る複数の組合せを選択する。次に、深さ及び向きの組合せが正しい場合、その領域の画素をどの位置に移動させるべきかを決定する。第１の画像中のこれらの画素の画素内容と第２の画像中のこれらの画素が移動した位置における画素の画素内容との間の差の集合（ａｇｇｒｅｇａｔｅ）を決定する。この集合を最小にする深さ及び向きの組合せを、この領域中に見える曲面片の深さ及び向きの最良の近似値として選択する。
この処理は、画像をカバーする格子状ブロックに対して適用するのが好ましい。
【０００９】
好ましくは、全ての深さ及び向きの組合せについて試行するのではなく、例えば深さ及び向きの最良の組合せを見出そうとしている領域と隣接する領域において最良の近似値となることが見出された組合せのような、最も高い可能性が予期される組合せだけについて試行する。この可能性のある組合せの一例は、当該領域の画像と別の画像との以前の比較により最も高い可能性の深さ及び向きの組合せとして見出された組合せを含む。
【００１０】
本発明のこれらの及び他の有益な概念は以下の図面を用いて詳細に説明する。
【００１１】
図１は曲面片１０の形態及び２個の視点１２ａ，１２ｂを示す。曲面片１０を含む被写体の像を異なる視点１２ａ，１２ｂからの点投影を用いて得る場合、画像中で曲面片上の点１４，１５が見える位置は点１４，１５の投影点１６ａ，１６ｂ，１７ａ，１７ｂである。これらの投影点は、点１４，１５から視点１２ａ，１２ｂを経て像面１８に至るライン１９ａ〜１９ｄを引くことにより図示することができる。基本原理を説明するために、視点１２ａ，１２ｂを像面１８と平行な面内に選択しているが、本発明はこのような視点１２ａ，１２ｂの選択に制限されるものではない。これらのライン１９ａ〜１９ｄと像面１８との間の交点が、画像中で曲面片上の点１４，１５が見える位置を示している。
【００１２】
視点１２ａ，１２ｂを変化させることにより、像面１８において曲面片上の点１４，１５が見える位置１６ａ，１６ｂ，１７ａ，１７ｂが並進する。この並進は、視点と曲面片上の点との間の深さ「Ｚ」に反比例し、視点の位置の変化量に比例する。その結果、視点１２ａ及び１２ｂからの深さ「Ｚ」が異なる曲面片１０上の点１４及び１５のそれぞれに対する並進が異なることになる。
【００１３】
図２は、曲面片が見えるようになる領域１２を含む画像２０を示す。画像２０において、並進ベクトル２３ａ，２３ｂ，２５ａ，２５ｂが図示され、この並進ベクトルに従って画像２０中に見える曲面片上の点の位置が視点の移動に応じて並進する。並進ベクトル２５ａ，２５ｂの大きさは、視点から遠い曲面片上の点より視点に近い曲面片上の点の方が大きくなる。ライン２６に沿って全ての点の深さが同一である場合、並進は同一である。
【００１４】
ライン２６に沿う軸線とこのライン２６と直交する軸線とを有する座標系を用いる場合、像中で点が見える位置に関する並進ベクトルＤの大きさはＡ＋Ｂｕに比例する。ここで、ｕは、ライン２６と直交する軸線に平行な像中に見える点の位置を示す座標である。並進方向は視点の移動方向と反対である。パラメータ「Ａ」はｕ＝０における深さＺ０の逆数に比例するもので、Ａ＝ｃ／Ｚ0 となる。また、Ｂは、観察方向と直交する曲面片の傾き「ｓ」及び深さに比例するもので、Ｂ＝ｃ×ｓ／Ｚ０となる（ｃは、視点の変位、焦点距離及び画像スケールに比例する比例定数である）。
【００１５】
しばしば、曲面片には「テクスチャ」が付けられている。すなわち曲面片により、被写体の画像中で曲面片が見える領域において位置依存性のグレイ値又はカラーベクトル値（一般的に「画像内容」）が生ずるようになっている。視点の移動に起因してこの領域が移動したり変形したりした場合には、このテクスチャがあることにより、元の領域の画像内容と、移動及び変形後の画像内容とをマッチングすることで上記移動を追跡しうるようになる。
【００１６】
図３は曲面片の深さ及び向きを評価する方法のフローチャートを示す。
【００１７】
このフローチャートの第１及び第２のステップ３１，３２において、カメラ光学系をそれぞれ第１及び第２の視点に配置し、これら第１及び第２の視点から第１及び第２の画像をそれぞれ得るようにする。
【００１８】
フローチャートの第３のステップ３３において、第１の画像の領域を選択する。フローチャートの第４のステップ３４において、複数の深さ−向きの対の候補を選択する。これらの対をそれぞれ用いてライン２６の向き及びパラメータＡ及びＢを決定することができる。
【００１９】
これら候補の対は、例えば先の画像に関する以前のカメラ移動から隣接する領域又は同一の領域について決定した深さ−向きの対に基づいて選択することができる。候補の深さ値を選択する方法は、例えば欧州特許出願第９８２００３５８．４号及びその優先権の基礎となる特許出願から知られており、これらの特許出願は本明細書において参考として記載する。この既知の方法において種々の領域を選択しその概算された深さ値を候補の深さ値として用いる方法と同じようにして、このような選択された領域の深さ及び向きを候補となる深さ−向き対として用いることができる。
【００２０】
深さ−向き対は、第１の画像の点と第２の画像の点との間の対応を規定する。第１の画像及び第２の画像の対応する点は、曲面片の深さ及び向きが深さ−向き対と等しい場合、曲面片の同一の位置がそれぞれ第１の画像及び第２の画像上へ投影された点である。
【００２１】
このフローチャートの第５のステップ３５において、複数の深さ−向き対の各々に関して、第１の画像の点の画素内容と、第２の画像の対応する点の画素内容とを比較する。
【００２２】
これは、例えば第１の画像の点における画素内容（グレイ値又はカラーベクトル）と第２の画像の対応する点の画素内容との間の差の絶対値を加算することにより行うことができる。この場合、差の計算は以下の式で表される。
ＳＵＭR ｜Ｉ１(R) −Ｉ２（Ｆ(R))｜
ここで、加算は第１の画像中の領域の複数のｘ，ｙ位置Ｒについて行われるもので、Ｉ１(R) は位置Ｒにおける第１の画像の画素内容であり、Ｉ２(R)は並進位置Ｆ（Ｒ）における第２の画像の画素内容である。並進位置Ｆ（Ｒ）は、オリジナルの位置Ｒと、測定値の差を計算する深さ−向き対の深さ及び向きとの関数であるｘｙ成分を有する。
【００２３】
差の絶対値を加算する代りに、差の２乗のような他の差の測定値を加算することができる。また、対応する点を得るために、いずれか１つの画像の予め定めた位置について加算する必要はなく、その代りに第１及び第２の画像の対応する点Ｒ１＝Ｆ１（Ｗ）及びＲ２＝Ｆ２（Ｗ）にマップされる基準点について加算することもできる。
ＳＵＭ'w｜Ｉ１（Ｆ１（Ｗ））−Ｉ２（Ｆ２（Ｗ））｜
【００２４】
曲面片のテクスチャは差の測定の信頼性を得るためのものである。曲面片がテクスチャを有していないと、種々の深さ−向き対について計算される測定値の差は極めて小さくなる。
【００２５】
フローチャートの第６のステップ３６において、どの深さ−向き対が最小の測定値の差になるかを決定する。第７のステップ３７において、この差が十分に小さいか否かを決定する。この差が十分に小さくない場合、ステップ３４ａにおいて深さ−向き対を用いて、最小の測定値の差を有する深さ−向き対に基づいて新たな候補の深さ−向き対を発生させ、フローチャートを第５のステップ３５から繰り返す。
【００２６】
最後に、任意であるが、例えば深さ及び向きに関する測定値の差の勾配を用いる反復最小値検出アルゴリズムを用いて、最良の候補に近い最適値を検索することにより、深さ−向き対を更に最適化することができる。
【００２７】
差の測定が十分に小さい場合、第１画像からの全ての所望の領域が処理されたか否かをテストする。そうでない場合、第１画像の種々の領域についてこの処理を繰り返す。
【００２８】
結果として、画像中の複数の領域について、深さ及び向きの評価を利用することができるようになる。
【００２９】
所定の深さ−向き対に対する並進位置Ｆ（Ｒ）は以下のようにして計算することができる。初めに、第１の視点から撮像した画像中の像点Ｒに対応する３次元位置Ｐを計算する。この点Ｐは、当該点Ｐが深さ−向き対を有する曲面片上に存在するという仮定の下で一意的に計算される。第１の視点から第２の視点に移動した際の点Ｐ、並進及びカメラ光学系の回転が与えられると、第２の視点からの点Ｐの投影点Ｆ（Ｒ）が計算される。
【００３０】
例えば、点Ｐが第１の視点からのカメラ光学系に対して座標（Ｐx ，Ｐy ，Ｐz）を有する場合、第１の視点からの画像中でこの点Ｐが見える位置Ｒ＝（ｘ，ｙ）は以下の式で与えられる。
ｘ＝Ｓ×Ｐx ／Ｐz 
ｙ＝Ｓ×Ｐy ／Ｐz 
Ｓは所定のカメラ光学系のパラメータである。所定の深さ−向き対は、Ｐが式Ａ×Ｐ＝Ｃを満たすことを規定している。ここで、Ａ×Ｐは所定の向きを有する表面経路に直交するベクトルＡとＰとのスカラ積であり、ＣはベクトルＡと深さとに依存する定数である。このようにして、深さ−向き対はＡ，Ｃにより表される（ここで、Ａの２個の成分だけが独立して可変になる必要がある）。
【００３１】
従って、座標（Ｐx ，Ｐy ，Ｐz ）をＲの関数として解くことができる３個の式を利用することができる。
【００３２】
第２の視点の点Ｐからの投影位置Ｆ（Ｒ）＝（Ｆx （Ｒ），Ｆy （Ｒ））は、
・視点の位置（これは、第１の視点からの３次元並進ベクトルＤとして表わすことができる）と、
・カメラ光学系の向き（これは、第１の位置におけるカメラ光学系の軸線の組を第２の視点におけるカメラ光学系の軸線の組に変換する回転マトリックスＱを用いて表わすことができる）と
の関数であり、以下の式で表される。
Ｆx （Ｒ）＝Ｓ〔Ｑ（Ｒ＋Ｄ）〕x ／〔Ｑ（Ｒ＋Ｄ）〕z 
Ｆy （Ｒ）＝Ｓ〔Ｑ（Ｐ＋Ｄ）〕y ／〔Ｑ（Ｐ＋Ｄ）〕z 
カメラ光学系の移動がＱ，Ｄの項で与えられると、Ｆ（Ｒ）はＰから容易に導かれる。実際に、この計算は、測定値の差を計算するために用いられるＦ（Ｒ）の代数式で収集されるので、Ｐは毎回明確に計算する必要はない。例えば、カメラ光学系が回転せず像面１８に平行に並進する簡単な構成の場合、以下のようになる。
Ｆ（Ｒ）＝Ｒ＋Ｔ×（１＋Ｒ・Ｎ）／Ｚ0 
この式において、Ｚ0 は曲面片の深さ−向き対からの深さであり、Ｔ（Ｄに対応する）は視点の並進方向と反対方向の像面のベクトルであり、ＲとベクトルＮとのスカラ積は深さ−向き対からの曲面片の向きを表わす。Ｎは、カメラ光学系の光軸に沿う法線成分の長さによって分割された曲面片に垂直な像面に対する垂直投影を意味する。
【００３３】
第１および第２の画像の対応する点Ｒ１，Ｒ２は、特定の深さ−向き対を満足するように選択されたＰz 値を有するＰx ，Ｐy のグリッドから得られたＰx ，Ｐy ，Ｐz 値からＲ１及びＲ２の両方を計算することにより得ることもできる。この場合、第１及び第２の画像の一方の画像からのグリッドの点について加算する代わりに、Ｐx ，Ｐy のグリッド上の点について得られた画素値Ｉ１（Ｒ１），Ｉ２（Ｒ２）の差について加算することもできる。グリッド上のＰx ，Ｐy 値は、任意の方向に等間隔で離間させたり、ランダムに選択したり、または等しい深さのラインに沿って等しい間隔で且つ深さに反比例して変化するこれらラインと直交する方向に間隔を空けて取り出したりして画像中での分布が均一になるようにする。
【００３４】
図４は深さを評価する装置を示す。この装置は、第１及び第２の画像メモリユニット４２ａ，４２ｂに結合したカメラ光学系及びセンサを含む。制御ユニット４１をメモリ制御ユニット４５及び深さ検索ユニット４６に結合する。任意であるが、動き測定及び／又は制御ユニット４４を、制御ユニット４４とカメラ光学系及びセンサ４０との間に結合する。メモリ制御ユニット４５が第１及び第２の画像メモリ４２ａ，４２ｂに結合されている。深さ探索ユニット４６は、画像メモリユニット４２ａ，４２ｂに結合したアドレス出力部を有する。画像メモリユニット４２ａ，４２ｂは差計算ユニット４７に結合した画像データ出力部４７を有する。
【００３５】
動作時には、初めに制御ユニット４４により、メモリ制御ユニット４５が、カメラ光学系及びセンサ４０により得られた第１及び第２の画像を記憶し、これらが画像メモリ４２ａ，４２ｂにそれぞれ記憶されるようにする。次に、制御ユニット４４により、深さ検索ユニット４６が、第１及び第２の画像メモリユニット４２ａ，４２ｂに記憶されている画像のマッチング領域を検索するようにする。制御ユニット４４は深さ検索ユニット４６に対して移動パラメータも供給しうる。これら移動パラメータは観測または制御されたカメラ光学系及びセンサ４０の動きから決定されたものである。しかしながら、これは必ずしも必要な処理ではない。必要としない場合、評価深さは、画像中の全ての位置について共通な任意のファクタにより決定される。
【００３６】
深さ検索ユニット４６は領域及び候補となる深さ向き対を選択する。所定の領域及び候補となる深さ向き対について、深さ検索ユニットは第１及び第２の画像上の対応する位置の画素アドレスを第１及び第２のメモリユニット４２ａ，４２ｂにそれぞれ発生する。これらの位置における画像内容を差計算ユニット４７に供給する。領域についての得られた測定値の差を深さ検索ユニット４６に供給する。この得られた測定値の差を深さ検索ユニットにロードする。この操作を複数の候補の深さ−向き対及び領域について繰り返す。各領域について、深さ検索ユニット４６は測定値の差が最小になるように深さ−向き対を選択する。
【００３７】
この方法及び装置を用いることで曲面片の深さ及び向きが得られる。この情報は、画像中に見える全てのまたは大部分の表面について得ることができる。この情報を用いて、例えば種々の視点からの被写体の画像を再構成することができる。既知のテクスチャ、位置及び向きを有する曲面片の観点から被写体を表現しておけば、通常のコンピュータグラフィック技術を用いて種々の視点からの被写体の画像をレンダリングすることができる。
【００３８】
深さ及び向き情報の他の用途としては画像圧縮がある。ＭＰＥＧビデオのような圧縮技術において、情報は画像中の画素のブロックを別の画像に対する動きの観点から符号化することにより圧縮される。これは、ブロック中の各画素に対して同一の動きを割り当てることである。ブロック中の画素の他の変化は、個々の画素に対して付加的な情報を含ませることにより符号化される。ＭＰＥＧにおいて、ブロックは大きくなり過ぎないように形成される。この理由は、特に、ブロックが大きくなり過ぎると、付加的な情報に対する必要性が大幅に増大し、従って圧縮比が低下するからである。
【００３９】
ブロックについての深さ及び向きの情報を符号化することにより（それ自身について又は動きベクトルのような別の情報に加えて）、種々の画素に対して種々の動きを割り当てることができ、この動きによって得られたブロック中の画素と実際の画素との間に一層密接な整合性を得ることができるようになる。このような符号化を用いることにより、画像を符号化するために必要な付加的な情報が少なくなり、一層大きなブロックを用いて画像を一層圧縮することができる。この目的のために深さ及び向きを用いることにより、人間の知覚が最も敏感な画像アスペクトの整合性がより確実になるという追加の利点が得られる。
【００４０】
画像の再構成及び符号化に関して、均質な画像領域について得られる深さ及び向きの情報の精度が低下する問題は生じない。均質化のために、深さ及び向きの情報は再構成又は圧縮精度に対してほとんど影響を及ぼすことはない。
【図面の簡単な説明】
【図１】  曲面片の形態及び２個の視点を示す。
【図２】  曲面片の画像を示す。
【図３】  曲面片の深さ及び向きを評価する方法のフローチャートを示す。
【図４】  視点と曲面片との間の深さを評価する装置を示す。