(57)【要約】【課題】  ステレオ法で奥行を求めるとき、領域ベースの手法では計算コストが大きく、特徴ベースの手法では取得できる対応点の数が少ない。  【解決手段】  注目点Ｐ１の対応点は検出できず、その奥行値は不明である。しかし、その点の周囲の点ＰｉとＰｊについては対応点が検出され、奥行値が既知である。そこで、注目点Ｐ１の奥行値を補間で求め、それをもとに仮の対応点位置を求め、その位置付近で領域ベースの探索を実施し、対応点位置の精度を高める。【選択図】図２
2005037378.tif 000002
【特許請求の範囲】
【請求項１】
第１画像上の注目点の属性に基づき、当該注目点の第２画像上の対応点を取得する属性ベース探索部と、
対応点が取得できた注目点について三角測量の原理によって奥行値を算出する奥行算出部と、
対応点が取得できなかった注目点の奥行値を、すでに奥行値が存在する１つ以上の注目点の奥行値からの補間によって導出する奥行補間部と、
導出された奥行値から、前記対応点が取得できなかった注目点の仮対応点を定める仮対応点取得部と、
領域ベースの探索を前記仮対応点付近に限定して実行し、前記仮対応点よりも正確な対応点を取得する対応点再計算部と、
を備え、前記奥行算出部は、前記対応点再計算部によって、より正確な対応点が取得された注目点について奥行値を算出することを特徴とする奥行計測装置。
【請求項２】
前記対応点再計算部は、前記対応点が取得できなかった注目点の第２画像におけるエピポーラ線上において、前記仮対応点付近に限定して、前記領域ベースの探索を行うことを特徴とする請求項１に記載の奥行計測装置。
【請求項３】
第１画像上の注目点の属性に基づき、当該注目点の第２画像上の対応点を取得する属性ベース探索部と、
対応点が取得できた注目点について三角測量の原理によって奥行値を算出する奥行算出部と、
対応点が取得できなかった注目点の奥行値を、すでに奥行値が存在する１つ以上の注目点の奥行値からの補間によって導出する奥行補間部と、
導出された奥行値から、前記対応点が取得できなかった注目点の仮対応点を定める仮対応点取得部と、
領域ベースの探索を前記対応点および前記仮対応点付近に限定して実行し、前記対応点および前記仮対応点よりも正確な対応点をそれぞれ取得する対応点再計算部と、
を備え、前記奥行算出部は、前記対応点再計算部によって、より正確な対応点が取得された注目点について奥行値を算出することを特徴とする奥行計測装置。
【請求項４】
前記対応点再計算部は、前記注目点の第２画像におけるエピポーラ線上において、前記対応点および前記仮対応点付近に限定して、前記領域ベースの探索を行うことを特徴とする請求項３に記載の奥行計測装置。
【請求項５】
前記注目点はエッジ点であり、前記属性はエッジの両側の画像領域の特徴であることを特徴とする請求項１から４のいずれかに記載の奥行計測装置。
【請求項６】
前記奥行補間部は、前記すでに奥行値が存在する複数の注目点と前記対応点が取得できなかった注目点の位置関係をもとに前記奥行値を導出することを特徴とする請求項１から５のいずれかに記載の奥行計測装置。
【請求項７】
第１画像上の注目点の属性に基づき、当該注目点の第２画像上の対応点を取得するステップと、
対応点が取得できた注目点について三角測量の原理によって奥行値を算出するステップと、
対応点が取得できなかった注目点の奥行値を、すでに奥行値が存在する１つ以上の注目点の奥行値からの補間によって導出するステップと、
導出された奥行値から、前記対応点が取得できなかった注目点の仮対応点を定めるステップと、
領域ベースの探索を前記仮対応点周辺に限定して実行し、前記仮対応点よりも正確な対応点を取得するステップと、
より正確な対応点が取得された注目点について三角測量の原理により奥行値を算出するステップと、
を含むことを特徴とする奥行計測方法。
【請求項８】
第１画像のエッジを抽出するステップと、
抽出されたエッジ上のエッジ点の属性に基づき、当該エッジ点の第２画像上の対応点を取得するステップと、
対応点が取得できたエッジ点について三角測量の原理によって奥行値を算出するステップと、
対応点が取得できなかったエッジ点の奥行値を、すでに奥行値が存在する１つ以上のエッジ点の奥行値からの補間によって導出するステップと、
導出された奥行値から、前記対応点が取得できなかったエッジ点の仮対応点を定めるステップと、
前記対応点が取得できなかったエッジ点の第２画像におけるエピポーラ線上において、領域ベース相関法による探索を前記仮対応点付近に限定して実行し、前記仮対応点よりも正確な対応点を取得するステップと、
前記仮対応点よりも正確な対応点が取得されたエッジ点について三角測量の原理により奥行値を算出するステップと、
エッジ点以外の点の奥行値をエッジ点の奥行値からの補間によって導出するステップと、
を含むことを特徴とする奥行計測方法。
【請求項９】
第１画像のエッジを抽出するステップと、
抽出されたエッジ上のエッジ点の属性に基づき、当該エッジ点の第２画像上の対応点を取得するステップと、
対応点が取得できたエッジ点について三角測量の原理によって奥行値を算出するステップと、
対応点が取得できなかったエッジ点の奥行値を、すでに奥行値が存在する１つ以上のエッジ点の奥行値からの補間によって導出するステップと、
導出された奥行値から、前記対応点が取得できなかったエッジ点の仮対応点を定めるステップと、
前記エッジ点の第２画像におけるエピポーラ線上において、領域ベース相関法による探索を前記対応点および前記仮対応点付近に限定して実行し、前記対応点および前記仮対応点よりも正確な対応点をそれぞれ取得するステップと、
前記対応点および前記仮対応点よりも正確な対応点が取得されたエッジ点について三角測量の原理により奥行値を算出するステップと、
エッジ点以外の点の奥行値をエッジ点の奥行値からの補間によって導出するステップと、
を含むことを特徴とする奥行計測方法。
【請求項１０】
前記領域ベース相関法による探索をサブピクセルレベルで行うことを特徴とする請求項８または９に記載の奥行計測方法。
【請求項１１】
請求項７から１０のいずれかに記載の各ステップをコンピュータに実行せしめることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は奥行計測技術に関し、特に、ステレオ法によって奥行を計測する方法と装置に関する。
【背景技術】
【０００２】
非特許文献１に示すごとく、２枚の画像間で対応しあう点を検出し、三角測量の原理を適用して画像内の各点の奥行を計測する技術が知られている。
【０００３】
画像間で対応しあう点を検出する手法は「特徴ベース」と「領域ベース」に大別される。特徴ベースの手法は、画像内の特徴的な部分どうしで対応付けを行うもので、第１の画像における注目点の属性に基づき、第２の画像における対応点候補を絞り込む。候補がひとつに絞られれば、それを対応点と決める。一方、領域ベースの手法は、各画素について、その周辺領域の相関値をもとに対応付けを行う。探索範囲において、最も良好な相関値を有する点を対応点と決める。
【非特許文献１】谷内田著，「ロボットビジョン」，昭晃堂，１９９０年，ｐ．１８１−１８５
【発明の開示】
【発明が解決しようとする課題】
【０００４】
特徴ベースの手法は、対応点の精度が特徴抽出の精度に依存する。一般に、特徴抽出は高周波成分の抽出等、ノイズ成分を拾いやすい傾向にあり、ノイズフリーな検出が困難である。また、信頼できる特徴点の数に限りがあり、画像全体の奥行計測に制約がある。
【０００５】
一方、領域ベースの手法は、繰り返しパターンのある画像を不得手とする。また、探索範囲が広ければ計算負荷が大きく、探索範囲を狭めれば、対応点を見失うおそれがある。以上、いずれの手法にも一長一短がある。
【０００６】
本発明はこうした状況に鑑みてなされたものであり、その目的は、特徴ベースの手法に比べ、より多くの対応点を発見できるとともに、領域ベースの手法の計算負荷を軽減する技術の提供にある。本発明の別の目的は、より正確に対応点を導出し、その結果、より正確な奥行を計測する技術の提供にある。
【課題を解決するための手段】
【０００７】
本発明のある態様は奥行計測装置であり、第１画像上の注目点の属性に基づき、当該注目点の第２画像上の対応点を取得する属性ベース探索部と、対応点が取得できた注目点について三角測量の原理によって奥行値を算出する奥行算出部と、対応点が取得できなかった注目点の奥行値を、すでに奥行値が存在する１つ以上の注目点の奥行値からの補間によって導出する奥行補間部と、導出された奥行値（これを適宜「仮奥行値」ともよぶ）から、対応点が取得できなかった注目点の仮対応点を定める仮対応点取得部と、領域ベースの探索を仮対応点付近に限定して実行し、仮対応点よりも正確な対応点を取得する対応点再計算部とを備え、奥行算出部は、対応点再計算部によって、より正確な対応点が取得された注目点について奥行値を算出する。
【０００８】
ここで奥行補間部において注目点の奥行値を補間する際、補間対象となる、すでに奥行値が存在する注目点が１つの場合は、当該注目点の奥行値をそのまま仮奥行値とし、これも補間とよぶことにする。
【０００９】
この構成により、注目点の属性によって対応点を探索するだけでなく、領域ベースの探索がなされるため、より多くの注目点について対応点が取得できる。また、その対応点の位置の精度を高めることができる。領域ベースの探索は、仮対応点付近に限定されるため、計算コストを抑制できる。
【００１０】
注目点は例えばエッジ点であり、その属性はエッジの両側の画像領域の特徴、例えば色やテクスチャであってもよい。「エッジ点」はエッジ上の点である。エッジは画像からハイパスフィルター等で抽出してもよい。また、予めストライプ光を被写体に投じてこれを撮影し、エッジが抽出しやすい前処理をしてもよい。
【００１１】
奥行補間部は、属性ベースの探索で対応点が取得できた複数の注目点（これらを「一次注目点」という）またはすでに奥行値が存在する複数の注目点と、対応点が取得できなかった注目点（これを「二次注目点」という）の位置関係をもとに仮奥行値を導出してもよい。
【００１２】
本発明の別の態様は奥行計測装置であり、第１画像上の注目点の属性に基づき、当該注目点の第２画像上の対応点を取得する属性ベース探索部と、対応点が取得できた注目点について三角測量の原理によって奥行値を算出する奥行算出部と、対応点が取得できなかった注目点の奥行値を、すでに奥行値が存在する１つ以上の注目点の奥行値からの補間によって導出する奥行補間部と、導出された奥行値（これも適宜「仮奥行値」ともよぶ）から、対応点が取得できなかった注目点の仮対応点を定める仮対応点取得部と、領域ベースの探索を、属性ベース探索部において取得された対応点および、仮対応点取得部において定められた仮対応点付近に限定して実行し、対応点および仮対応点よりも正確な対応点をそれぞれ取得する対応点再計算部とを備え、奥行算出部は、対応点再計算部によって、より正確な対応点が取得された注目点について奥行値を算出する。
【００１３】
対応点再計算部は、二次注目点の第２画像におけるエピポーラ線上において、仮対応点付近に限定して、領域ベースの探索を行ってもよい。また、一次注目点についても領域ベースの探索を行う場合、一次注目点の第２画像におけるエピポーラ線上において、対応点付近に限定して、領域ベースの探索を行ってもよい。この場合、当然ながら計算がエピポーラ線上だけで済むため、計算コストが低い。さらに、仮対応点または対応点付近だけの探索でよいため、計算コストの抑制効果が大きい。
【００１４】
また奥行補間部において仮奥行値を導出する際、シャープな形状部分については、二次注目点の近隣に複数存在する、一次注目点のうちの一つの奥行値を仮奥行値とすることができ、逆に、フラットな形状部分については、一次注目点の奥行値からの補間に基づいて仮奥行値を導出することができる。これにより、対象物体の形状に応じた、適切な奥行値を導出することが可能となる。また、既に奥行値が導出されている注目点が疎である場合にも、仮奥行値を算出できる可能性が上がる。
【００１５】
本発明のさらに別の態様は奥行計測方法であり、第１画像上の注目点の属性に基づき、当該注目点の第２画像上の対応点を取得するステップと、対応点が取得できた注目点について三角測量の原理によって奥行値を算出するステップと、対応点が取得できなかった注目点の仮奥行値を、すでに奥行値が存在する１つ以上の注目点の奥行値からの補間によって導出するステップと、導出された奥行値から、対応点が取得できなかった注目点の仮対応点を定めるステップと、領域ベースの探索を仮対応点周辺に限定して実行し、仮対応点よりも正確な対応点を取得するステップと、より正確な対応点が取得された注目点について三角測量の原理により奥行値を算出するステップとを含む。
【００１６】
本発明のさらに別の態様は奥行計測方法であり、第１画像のエッジを抽出するステップと、抽出されたエッジ上のエッジ点の属性に基づき、当該エッジ点の第２画像上の対応点を取得するステップと、対応点が取得できたエッジ点について三角測量の原理によって奥行値を算出するステップと、対応点が取得できなかったエッジ点の奥行値を、すでに奥行値が存在する１つ以上のエッジ点の奥行値からの補間によって導出するステップと、導出された奥行値から、対応点が取得できなかったエッジ点の仮対応点を定めるステップと、対応点が取得できなかったエッジ点の第２画像におけるエピポーラ線上において、領域ベース相関法による探索を仮対応点付近に限定して実行し、仮対応点よりも正確な対応点を取得するステップと、仮対応点よりも正確な対応点が取得されたエッジ点について三角測量の原理により奥行値を算出するステップと、エッジ点以外の点の奥行値をエッジ点の奥行値からの補間によって導出するステップとを含む。
【００１７】
本発明のさらに別の態様は奥行計測方法であり、第１画像のエッジを抽出するステップと、抽出されたエッジ上のエッジ点の属性に基づき、当該エッジ点の第２画像上の対応点を取得するステップと、対応点が取得できたエッジ点について三角測量の原理によって奥行値を算出するステップと、対応点が取得できなかったエッジ点の奥行値を、すでに奥行値が存在する１つ以上のエッジ点の奥行値からの補間によって導出するステップと、導出された奥行値から、対応点が取得できなかったエッジ点の仮対応点を定めるステップと、エッジ点の第２画像におけるエピポーラ線上において、領域ベース相関法による探索を対応点および仮対応点付近に限定して実行し、対応点および仮対応点よりも正確な対応点をそれぞれ取得するステップと、対応点および仮対応点よりも正確な対応点が取得されたエッジ点について三角測量の原理により奥行値を算出するステップと、エッジ点以外の点の奥行値をエッジ点の奥行値からの補間によって導出するステップと、を含む
【００１８】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１９】
本発明によれば、正確で効率的な奥行情報の取得が実現する。
【発明を実施するための最良の形態】
【００２０】
図１、図２は実施の形態に係る奥行計測技術の原理を示す。図１は、従来一般的な対応点検出技術を模式的に示し、第１画像Ｉ１上にとられた注目点Ｐ１の第２画像Ｉ２上の対応点Ｐ２を求める。ここで、第１画像Ｉ１のカメラ焦点Ｆ１と注目点Ｐ１を結ぶ延長線Ｌを第２画像Ｉ２のカメラ焦点Ｆ２から見たとき、これが第２画像Ｉ２上にエピポーラ線ｅｌとして定まる。したがって、対応点Ｐ２はこのエピポーラ線ｅｌ上で探索される。
【００２１】
一方、図２は実施の形態に係る奥行計測技術の特徴を示す。実施の形態では、当初、奥行値が判明している注目点、すなわち一次注目点の奥行値から、奥行値が判明していない注目点、すなわち二次注目点の仮奥行値を補間によって導出し、仮奥行値から仮対応点を導出し、その二次注目点のエピポーラ線上の仮対応点付近（この部分を「限定エピポーラ線」とよぶ）に対応点が存在すると想定するものである。なお実施の形態では、仮奥行値とはいっても、後述のごとく別の点の仮奥行値を導出する際に再投入される。したがって、処理上は仮奥行値であるか、属性ベースの探索で当初より判明した奥行値であるかの区別はなくなるが、説明の便宜のため仮奥行値という言い方をする。
【００２２】
いま仮に、二次注目点Ｐ１がふたつの一次注目点ＰｉとＰｊの中点にあるとし、これらふたつの一次注目点の奥行値の平均がｄ１であるとする。このとき二次注目点Ｐ１の仮奥行値はｄ１とすればよく、したがって、限定エピポーラ線ｅｌ２は、二次注目点Ｐ１に関するエピポーラ線ｅｌのうち、仮対応点付近として奥行値ｄ１−Δｄ〜ｄ１＋Δｄの部分と定まる。実施の形態では、二次注目点Ｐ１の対応点Ｐ２はこの限定エピポーラ線ｅｌ２上にあると考える。そして、図３に示すごとく、限定エピポーラ線ｅｌ２上で領域ベースのマッチングをとり、二次注目点Ｐ１を中心とする領域Ｒと相関が高い領域の位置を特定し、その中心を対応点Ｐ２と決める。なお、二次注目点Ｐ１の奥行値が仮奥行値ｄ１となるような対応点を以下「仮対応点」ともよぶ。
【００２３】
以上が実施の形態の概要であり、限定エピポーラ線上に限って領域ベースの探索が行われる。このため、エピポーラ線を利用した対応点探索のメリットを享受しつつ、さらに計算コストを抑制して領域ベースの探索による対応点精度改善が図られる。また、二次注目点についても対応点が与えられるため、対応付けがより多くの点でなされ、特徴ベースの対応付け手法に一般的な対応点不足を解消することができる。
【００２４】
なお、図２の例では、二次注目点Ｐ１が一次注目点Ｐｉ、Ｐｊの中点であるとしたが、これは例えば位置ベクトルの考えで一般化できる。すなわち、ある二次注目点Ｐの位置ベクトル（単にＰと表記する）がｎ個の一次注目点Ｐｉの位置ベクトル（単にＰｉと表記する）によって以下のように記述できるとする。以下、Σはいずれもｉ＝１、２、・・・ｎに関する和である。  
Ｐ＝Σαｉ×Ｐｉ  ただし、Σαｉ＝１
【００２５】
このとき、二次注目点Ｐの仮奥行値ｄは、一次注目点Ｐｉの仮奥行値ｄｉを用いて以下のとおり記述できる。
ｄ＝Σαｉ×ｄｉ
【００２６】
また、図２では仮対応点の奥行前後について、等しくΔｄの範囲を探索したが、これは当然不均等な範囲であってもよい。
【００２７】
図４は以上の原理を適用したシステムの構成を示す。このシステムはモデリングの対象であるオブジェクト１０と、それにパターン光を投ずる投光器１２と、オブジェクト１０を撮影するステレオカメラ１４と、ステレオカメラ１４の出力からオブジェクト１０のモデリングを行う奥行計測装置１００を有する。パターン光は、複数色からなるストライプ光とする。
【００２８】
奥行計測装置１００の構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリのロードされた奥行計測機能のあるプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。
【００２９】
奥行計測装置１００の画像入力部２０は、ステレオカメラ１４から左右画像を入力するインタフェイスである。入力された左右画像その他のデータはメモリ２２に格納される。以下、左右画像のうち注目点を定義する側であるマスタ画像を第１画像、対応点を探索する側であるスレーブ画像を第２画像とよぶ。
【００３０】
属性ベース探索部２４は、第１画像上のエッジを抽出し、エッジ点の属性に基づき各エッジ点の第２画像上の対応点を取得する。ここで属性として、エッジ点の両側のストライプの色や、そのエッジ点が特徴点である場合、その特徴自体を利用する。一例として、そのエッジ点が当該点付近で画素値が極大または極小になるような点であれば、その情報を属性として利用してもよい。
【００３１】
奥行算出部２６は、属性を利用して対応点が取得できたエッジ点（一次エッジ点ともいう）について、三角測量の原理で奥行値を算出する。奥行算出部２６にはステレオカメラ１４の位置情報が投入されている。奥行補間部３０は、対応点が取得できなかったエッジ点（二次エッジ点ともいう）の仮奥行値を複数の一次エッジ点の奥行値からの補間によって導出する。
【００３２】
仮対応点取得部３２は、仮奥行値から二次エッジ点の仮対応点を定める。対応点再計算部３４は、領域ベースの探索、ここでは相互相関法による探索を二次エッジ点の限定エピポーラ線上に限定して実行し、仮対応点よりも正確な対応点を取得する。以上の処理で求められた対応点をもとに、奥行算出部２６は奥行値を再度算出しなおし、その結果を最終的な奥行値としてメモリ２２へ格納する。
【００３３】
図５は、奥行計測装置１００による処理の手順を示す。オブジェクト１０にはパターン光が投じられているとする。まず、ステレオカメラ１４によって撮影された画像が１０によりメモリ２２へ入力される（Ｓ１０）。属性ベース探索部２４はストライプ光によって形成されるエッジを後述の図８のごとく抽出し（Ｓ１２）、エッジ点の属性を取得する（Ｓ１４）。つづいて、奥行算出部２６はエッジ点ごとに属性ベースの対応点探索処理である後述の「第１処理」を実行する（Ｓ１６）。その結果、対応点が定まったエッジ点について、エッジ点と対応点の組がメモリ２２へ記録される。一次エッジ点は後述の図９に模式化される。この時点では、二次エッジ点については、対応点の情報が欠如している。
【００３４】
つづいて、奥行補間部３０により、二次エッジ点について、補間により仮奥行値が求められ（Ｓ１８）、仮対応点取得部３２と対応点再計算部３４により、エッジ点ごとの仮対応点取得と領域ベースの探索処理である後述の「第２処理」が実行される（Ｓ２０）。補間の様子は後述の図１０（ａ）（ｂ）に模式化される。なお、後述の理由からＳ１８の仮奥行値はエッジ点のみならず、第１画像上のすべての点について求められる。こうした仮奥行値が定められたすべての点は、後述の図１１に模式化される。
【００３５】
つぎに、対応点再計算部３４によりエッジ点以外の点（以下単に非エッジ点という）に関し、Ｓ１８で求められた奥行値をクリアし（Ｓ２２）、エッジ点とその対応点だけが情報として残される。このとき、一次エッジ点は「×」、二次エッジ点は「○」として後述の図１２に模式化される。すべてのエッジ点とその対応点の情報は奥行算出部２６へ再投入され、補間によりすべての点、すなわち全画素の奥行値が最終値として求まる（Ｓ２４）。
【００３６】
図６は「第１処理」、すなわちＳ１６の処理手順を示す。あるエッジ点の対応点を決める際、エピポーラ幾何の適用（Ｓ１００）とエッジ点の属性の参照（Ｓ１０２）が行われる。いま、パターン光が赤、青、白の繰り返しであり、注目しているエッジ点が「赤と青の境界線上」にあるとき、この対応点も当然「赤と青の境界線上」にある。さらに、この対応点は注目しているエッジ点のエピポーラ線上にあるはずだから、前記の境界線とエピポーラ線の交点が対応点の候補となる。問題は、「赤と青の境界線」は周期的に現れることであり、そのため、候補は一般に複数となる。複数の候補から正しい対応点を絞り込むためには、パターン光に含まれるいずれかの青いストライプを一時的に別の色に変えるなど、周期性を崩す処理をしたり、色以外の属性を併用する既知の手法などを用いる。また、色以外の属性を利用する方法のほかに、例えば三眼ステレオのごとくカメラを増やし、幾何的な制約を増やす手法もある。その場合、異なるスレーブ画像を用いても、同じ奥行値が得られるような点どうしが正しく対応しあうと判断することができる。
【００３７】
いずれにしても、こうした処理によって対応点候補がひとつになれば、対応点が確定できたと判断し（Ｓ１０４のＹ）、その対応点ともとのエッジ点との対により、奥行算出部２６において三角測量の原理で奥行値が算出される（Ｓ１０６）。これで一次エッジ点に関する奥行値が定まる。一方、Ｓ１０４において対応点候補がひとつに絞り込めなかった場合、または撮影状況やオブジェクト１０の形状等に起因し、そもそも対応点候補がうまく検出できなかった場合、対応点が確定できないと判断し（Ｓ１０４のＮ）、そのときのエッジ点を二次エッジ点としてＳ１０６の処理をスキップする。
【００３８】
図７は「第２処理」、すなわちＳ２０の処理手順を示す。この処理の前に、非エッジ点を含むすべての点について仮奥行値が定まっている。Ｓ２２において、非エッジ点の奥行値はクリアされ、結局エッジ点の奥行値しか利用されないのに、Ｓ１８ですべての点について仮奥行値を取得するのは、現実的な事情による。すなわち、オブジェクト１０の形状、色、テクスチャ等によってはエッジがきれいに抽出できないことがある。その場合、後述の図１０（ａ）（ｂ）のように、所定のマスク領域Ｍを設けて、その中で奥行値を有する点から奥行値を有しない点の奥行値を補間しようとしても、そもそも奥行値を有する点が領域内に存在しない事態が発生しうる（このような領域を「不能領域」とよぶ）。この事態を避けるべく、補間によって仮であっても奥行値が定義できる点はどんどん定義していき、仮奥行値であってもつぎの補間の際には一次エッジ点の奥行値と区別せずに利用してしまい、不能領域の発生を極力抑制するのである。ただし、エッジの抽出が確実にできたような場合は、当然ながらＳ１８の処理はエッジ点のみについて行ってもよく、そのほうが計算コストは下がる。
【００３９】
ここでは、すべての点について仮奥行値が定まっているとする。仮対応点取得部３２は仮奥行値からすべてのエッジ点について仮対応点の位置を特定し（Ｓ２００）、限定エピポーラ線上で領域ベースの探索を行う（Ｓ２０２）。領域ベースの探索のために、例えば以下の式による正規化相互相関を求める。
【００４０】
【数１】
2005037378.tif 000003
別の例として、以下のいわゆる二乗誤差総和を求めてもよい。  
【００４１】
【数２】
2005037378.tif 000004
いずれにしても、領域ベースの探索で対応点候補がひとつに絞られれば、対応点が確定できたと判断し（Ｓ２０４のＹ）、その対応点ともとのエッジ点との対により、奥行算出部２６において三角測量の原理で奥行値が算出および更新される（Ｓ２０６）。これですべてのエッジ点に関する奥行値が定まる。一方、Ｓ２０４において対応点候補がひとつに絞り込めなかった場合、対応点が確定できないと判断し（Ｓ２０４のＮ）、Ｓ２０の処理を抜ける。以上が奥行計測装置１００による処理である。
【００４２】
図８から図１２は、処理フローの途上における対応点の定まり方を模式的に示す。図８は第１画像においてエッジ抽出だけが終わった様子を示す。図９は、一次エッジ点の分布を示す。エッジ点のうち属性ベースの探索で対応点が定まるものは必ずしも多くなく、一次エッジ点が離散的に存在する状態が示されている。図１０（ａ）（ｂ）は、一次エッジ点の奥行値からすべての点の仮奥行値を定める補間の具体的方法を示す。図１０（ａ）のごとく、所定サイズのマスク領域Ｍをとる。このマスク領域Ｍの中に含まれる、ある点Ｐの仮奥行値ｄは、図１０（ｂ）のごとく、３個の一次エッジ点の奥行値ｄ１〜ｄ３、およびそれらの点からの距離ｒ１〜ｒ３を用いて、例えば以下のように決める。
d=(d1/r1+d2/r2+d3/r3)／(1/r1+1/r2+1/r3)
【００４３】
なお、図１０（ａ）（ｂ）において、マスク領域Ｍを横長にとるのは、横幅をエッジ間隔より大きくとるためである。すなわち、エッジ上には比較的密に一次エッジ点があるのに対し、横方向はエッジ間では一次エッジ点がない。補間のためには、処理しようとする点の上下左右いろいろな方向に一次エッジ点があること、とくに、その点を取り囲むように一次エッジ点があることが望ましいため、横方向に複数のエッジが入るよう配慮するのである。
【００４４】
図１１は補間によりすべての点について仮奥行値が求まった状態を模式的に示す。この後、領域ベースの探索を行い、非エッジ点の奥行値をいったんクリアした状態が図１２であり、ここでは一次エッジ点「×」と二次エッジ点「○」が奥行値をもっている。この後、エッジ点の奥行値からすべての点の奥行値を補間で求め、最終解として処理を終える。
【００４５】
なお、図１３に示すように、領域ベースの探索はサブピクセル単位で行ってもよい。ここでは、領域の位置をシフトしながら相関計算した結果、ある画素Ｘが領域の基準位置にきたとき、相関値が最大になったとする。このとき、この画素Ｘにおける相関値、および隣接する画素Ｘ−１とＸ＋１について相関値の合計３点を放物線その他の曲線で近似し、その曲線の最大値を求める。同図ではサブピクセルレベルでの画素Ｐにおいて相関値が最大になると判断できるため、対応点をこの画素Ｐの位置と定める。これにより、画素の物理的な解像度を超える対応点精度が実現しうる。
【００４６】
また、領域ベースの探索をサブピクセル単位で行う場合など、対応点再計算部３４における領域ベースの探索が、属性ベース探索部２４における属性ベースの探索と比較して精度的に有利な場合は、属性ベース探索部２４にて対応点が取得できた一次エッジ点についても、その対応点付近において領域ベースの探索を施し、より正確な対応点を取得した上で、奥行算出部２６にて奥行値を計算してもよい。ここで領域ベースの探索は、二次エッジ点の場合と同様、一次エッジ点のエピポーラ線上の、対応点付近を探索してもよい。
【００４７】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下、そうした例を挙げる。
【００４８】
実施の形態では、マスク領域Ｍが不能領域である場合、周囲の奥行値が次第に確定していき、いずれ不能領域ではなくなることを待ったが、別の処置として、マッチング領域Ｍのサイズを、奥行値を有する点が領域内に入るまで、暫定的または恒久的に大きくしてもよい。いずれにしても、投じられる光の特徴に応じたマスク領域Ｍを設けることが望ましい。
【００４９】
また、補間のためには、処理しようとする点を取り囲むように奥行を有する点があることが望ましいため、奥行を有する点が領域内に存在しても、処理しようとする点の上方向のみに存在する場合のように、取り囲む位置にない場合は不能領域として扱ってもよい。
【００５０】
実施の形態では、奥行値の補間の際に線形補間を利用したが、これは当然任意の非線形補間であってもよい。
【００５１】
また、奥行補間部３０によるエッジ点の奥行値の補間は、複数の一次エッジ点の奥行値に基づく線形補間や非線形補間に限らない。複数ある近隣の一次エッジ点のうちの一つの奥行値をそのまま二次エッジ点の仮奥行値としてもよい。非常にシャープな形状部分の奥行値の補間においては、このような方法は有効である。逆にフラットな形状部分の奥行値の補間においては、上述した線形補間等が有効である。
【００５２】
同様に、奥行補間部３０による注目点の奥行値の補間においても、複数ある近隣の一次注目点のうち一つの奥行値をそのまま二次注目点の仮奥行値としてもよい。
【００５３】
また、近隣に一次エッジ点、或いは一次注目点がひとつしかない場合は、その奥行値をそのまま注目点の奥行値としてもよい。
【図面の簡単な説明】
【００５４】
【図１】エピポーラ線を利用する奥行算出の原理を説明する図である。
【図２】実施の形態において、限定エピポーラ線を利用する奥行算出の原理を説明する図である。
【図３】実施の形態において、限定エピポーラ線上で領域ベースの対応点探索がなされる様子を示す図である。
【図４】実施の形態に係る奥行計測装置を含むシステムの全体構成図である。
【図５】実施の形態に係る奥行計測装置による処理手順を示すフローチャートである。
【図６】図５のＳ１６の詳細を示すフローチャートである。
【図７】図５のＳ２０の詳細を示すフローチャートである。
【図８】第１画像においてエッジが抽出された状態を模式的に示す図である。
【図９】エッジ上に、一次エッジ点が取得された状態を模式的に示す図である。
【図１０】図１０（ａ）（ｂ）は奥行値の補間の方法を示す図である。
【図１１】第１画像のすべての点について、仮奥行値が求められた状態を模式的に示す図である。
【図１２】第１画像において、すべてのエッジ点に対して奥行値が定まった状態を模式的に示す図である。
【図１３】実施の形態において、領域ベースの探索をサブピクセルレベルで行う方法を示す図である。
【符号の説明】
【００５５】
１０  オブジェクト、  １２  投光器、  １４  ステレオカメラ、  ２０、  ２２  メモリ、  ２４  属性ベース探索部、  ２６  奥行算出部、  ３０  奥行補間部、  ３２  仮対応点取得部、  ３４  対応点再計算部、  １００  奥行計測装置。
【図１】
2005037378.tif 000005
【図２】
2005037378.tif 000006
【図３】
2005037378.tif 000007
【図４】
2005037378.tif 000008
【図５】
2005037378.tif 000009
【図６】
2005037378.tif 000010
【図７】
2005037378.tif 000011
【図８】
2005037378.tif 000012
【図９】
2005037378.tif 000013
【図１０】
2005037378.tif 000014
【図１１】
2005037378.tif 000015
【図１２】
2005037378.tif 000016
【図１３】
2005037378.tif 000017