(57)【特許請求の範囲】
【請求項１】
２つ以上の撮像手段により同じ物体を含む情景の映像を撮影したステレオ画像について、一方の画像の各局所領域に対して、他方画像の探索範囲内における局所映像の対応の唯一性を評価して対応度を定め、上記対応度に基づき、対応が容易に得られる順序で一方の画像の各局所領域と他方の画像の局所領域とを対応付ける方法であって、
対応が唯一に定まらない局所領域に関しては、該局所領域の対応可能性情報に加えて、該局所領域から一定範囲にある周辺の局所領域で既に対応の求まっている局所領域の対応可能性情報を用いて唯一の対応を求め、該対応付けに基づき立体形状を検出する
ことを特徴とする立体形状検出方法。
【請求項２】
対応が唯一に求まらない局所領域の持つ対応可能性情報と、その局所領域から一定範囲にある既に対応の求まっている局所領域の対応可能性情報とを個別に扱い、
それぞれの対応可能性の組み合わせから算出した唯一の対応を決定する
ことを特徴とする請求項１の立体形状検出方法。
【請求項３】
２つ以上の撮像手段により同じ物体を含む情景の映像を撮影したステレオ画像について、一方の画像の各局所領域に対して、他方画像の探索範囲内における局所映像の対応の唯一性を評価して対応度を定め、上記対応度に基づき、対応が容易に得られる順序で一方の画像の各局所領城と他方の画像の局所領域とを対応付ける方法であって、
一方の画像から他方画像へ対応を求めた場合の他己対応度に加えて、一方の画像から同一画像へ対応を求めた場合の自己対応度を用いて定義した対応度を使用する
ことを特徴とする立体形状検出方法。
【請求項４】
請求項１または請求項２のいずれかの立体形状検出方法と、請求項３に記載の立体形状検出方法を組み合わせた
ことを特徴とする立体形状検出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、立体映像通信や、立体映像放送、立体画像生成、３次元形状計測、３次元物体認識、移動ロボット用ナビゲーションなど、ステレオ画像に基づく３次元情報の抽出を行なう広範囲の産業分野で利用することができる、両眼視差を用いて立体の３次元位置や形状を安定に検出する立体形状検出方法に関する。
【０００２】
【従来の技術】
従来より、２つあるいは３つ以上の撮像手段により得た２つあるいは３つ以上の画像による両眼視差を利用して立体の形状を検出する方法が各種提案されている。この種の立体形状検出方法の原理を、最も基本となる２つの撮像手段による場合について図１４を用いて説明する。
テレビカメラのような一対の撮像手段（以下カメラという）１−１，１−２の撮像面Ｉ１、Ｉ２に対してレンズＬ１、Ｌ２を通じて物体上の同一点Ｐが投影されている。ここで、撮像面Ｉ１、Ｉ２は互いに同一平面上に配置され、各撮像面から対応するレンズ間での焦点距離ｆは等しく、さらにカメラ１−１，１−２の光軸は互いに平行でｂだけ離れて設置してあるとする。
【０００３】
もし、一対の撮像手段１−１，１−２が任意の配置となっていても、カメラ間の幾何関係をあらかじめ測定しておくことで、撮像された画像を上記状態で得られた画像に変換することは可能である。したがって、上記状態を基準に話を進める。このとき、物体上の点Ｐは撮像された画像ではそれぞれｐ1 （ｐ1x，ｐ1y）、ｐ2 （ｐ2x，ｐ2y）の位置で観測される。ここで、両画像で対応する点の画像上での位置のずれを視差ｄとよぶ。ここでは、ｄ＝ｐ2x−ｐ1xとなる。
一方のカメラ（ここではカメラ１−１とする) から見た時の物体点ｐの３次元座標（Ｘ１，Ｙ１，Ｚ１）は以下の式(1a)〜(1c)のように表される。
【０００４】
Ｚ１＝ｆ・（ｂ／ｄ）  …(1a)
Ｘ１＝ｐ1x・（ｂ／ｄ）…(1b)
Ｙ１＝ｐ1y・（ｂ／ｄ）…(1c)
【０００５】
ここで、Ｚ１はカメラ１−１からの距離、ｆはカメラの焦点距離、ｂは両カメラ間距離、ｄは視差、Ｘ１はカメラ１−１からの３次元Ｘ座標、ｐ1xは画像中心からのＸ座標、Ｙ１はカメラ１−１からの３次元ｙ座標, ｐ1yは画像中心からのＹ座標である。
このように、３次元情景中の任意の点に対する両画像での投影点を定めれば、投影点の画像での座標値と視差値が求められるので、上式(1a)〜(1c)により３次元位置を求めることができる。これが両眼視による３次元位置算出の原理である。なお、３つ以上の撮像手段を用いた場合でも、任意の２つの撮像手段を考えれば、上記と同じとなる。
【０００６】
上記原理より明らかなように、視差を用いて３次元位置を求めるためには、両画像で対応する同一物体の投影点を求めることが必要である。これを「対応探索問題」と呼ぶ。
以下、「対応探索問題」についてさらに詳しく説明する。
いま、一対の撮像手段により得られたステレオ画像を考える。一方の画像( ここでは左画像とする) のある点ｐ1 に着目する。このとき、他方画像（ここでは右画像とする) でのｐ1 に対応する点ｐ2 は、２つのカメラの位置関係より決定されるエピポーラ線と呼ばれる拘束線上に位置する。
【０００７】
ここでは２つのカメラの光軸は互いに平行と等価な場合に画像変換を行なうので、エピポーラ線は同一走査線( 同一ｙ座標) で、かつ、ｐ2 はｐ1 を他方画像へ写した位置より左方に位置する。したがって、対応点探索には左画像の各位贋（ｐ1 ）に対して、右画像での同一走査線上を、ｐ1 のｘ座標より左方に向けてある探索範囲Ｒだけ走査しながら最も類似した箇所を定めることで対応する組みが得られる。このとき、点のみで類似度を定めるのは困難なため、点を含む一定の範囲の情報を利用して類似度を求める。
一般には、探索範囲には複数の対応候補が存在するので、真の対応箇所を定めることは容易ではなく、いかに正しく対応箇所を得るかが両眼視差を用いる３次元距離計測の要点である。
【０００８】
これまで提案された代表的な方式としては以下のものに大別できる。
(1) 画像の各位置で独立に対応を求める方法。
(2) 画像の各位置で周囲の一定範囲あるいは画像全体での何らかの支持を元に対応を求める方法。
上記(1) の代表的なものとしては、一方の画像を一定の大きさを持つ小領域に区切り各小領域に対して、あるいは一方の画像の各画素に対して、あるいは一方の画像の特徴点に対して、他方画像を走査して小領域内の輝度分布の類似性を、正規化相関、輝度差の絶対値和（ＳＡＤ）、輝度値の差の２乗和（ＳＳＤ）などで評価して最も類似した部分と対応を付けるものがある。
【０００９】
上記(2) では以下のものなどがある。
(a) 近傍の距離変化は小さいとして視差変化の大きさに制限を設ける方法。
(b) 局所的な領域で求めた対応度合（対応エネルギー）と隣り合う領域の視差の違いで定義される歪みエネルギーの画像全体の総和を弛緩的に最小化することで全体で最も良い対応を得るエネルギー最小化法。
(c) 対応付ける特徴量の信頼性に着目して高信頼なエッジ点から順に対応を求めていき、より信頼性が低いエッジ点の対応に既に求まったより信頼性の高いエッジ点の対応情報を利用するもの。
【００１０】
ここでは、(c) 特徴の信頼性に基づく方法（山口・中山・白井・浅田「信頼性の高い対応を優先した多段階ステレオ法」電子情報通信学会論文誌、Vo1,J74-D-II、No.7,1991 ）について説明する。
これによれば、輝度値の急変する部分（エッジ点) を対応付ける特徴点とするとき、次の２つの特長を持つ。
i)エッジ点の位置情報は輝度変化（コントラスト）が大きいほど確かで逆に低いほど不安定なる。
ii) 画像においてコントラストが大きいエッジ点の個数は少ないので対応候補が少なく容易に対応付けられる。
これら特長に着目し、あらかじめエッジをコントラスト値の大きさで複数のグループに分類しておき、まず、最もコントラストの高いグループに属す信頼が高く容易に対応付けられるエッジ点の対応を求め、順によりコントラストの低いグループのエッジ点を対応付ける。
【００１１】
【発明が解決しようとする課題】
まず、前記(1) の画像の各位置で独立に対応を求める方法では、画像の各位置で独立に対応を求めている。しかし、独立に対応付けたのでは、対象情景中に類似した形状の立体が複数あったり繰り返し模様を含む物体があると、真に対応する部分と偽の対応の部分との類似度の違いはわずかであるため、画像のノイズや照明の影響により容易に誤った部分と対応してしまう。実際には物体のない位置の距離を示すことがある。
次に、前記(2) の周囲の何らかの支持を元に対応を求める方法の問題について述べる。
【００１２】
まず、前記(a) の方法では、着目部分の対応を独立に求めるのではなく、近接領域との視差変化の大きさに制限を設けて周囲の対応状況を反映させることで安定した対応を得ている。
しかし、画像中に設けた着目部分をあらかじめ決められた順序で走査して、対応付けの難易度に無関係に処理するものがほとんどであり、繰り返しパターンがあるなど対応付けが困難な部分を先に対応付けてしまい、もしその部分が誤対応となれば、その影響が後段に伝わり、結果として広い範囲で誤った対応を生じる。
【００１３】
次に前記(b) の方法では、エネルギー最小化により画像の部分でなく全体の対応の一貫性を考えることで、矛盾のない対応を得ているが、一般にエネルギー最小化には多くの繰り返し演算が必要であり実用的でない。
また前記(c) の方法では、グループ分けはコントラストの大きさにより分けているが、同一コントラスト群に属すエッジ点については、従来の固定的な順序で対応を求めているので、繰り返しパターンでの順序性による誤対応伝播の問題がある。
しかも、高コントラストのエッジの対応に誤りを生じると、その情報が後段のよりコントラストの低いエッジ点への対応付けに利用され、結果として誤った情報が広範囲に伝播して誤対応が増加する。さらに、対応付けの初期段階では高コントラストの少量のエッジ点しか用いないので、視差のヒストグラムに投票するエッジ点の個数が少なくヒストグラム形状が不安定となり、繰り返しパターンにより弱くなるという問題もある。
【００１４】
本発明は上記した事情を考慮してなされたものであって、従来では対応付けが困難であった繰り返しパターン部の対応を安定に得ることができ、画像全体から正しい対応を得ることができる立体形状検出方法を提供することである。
【００１５】
【課題を解決するための手段】
立体の３次元情報獲得する方法を基本である２つの撮像装置を用いた場合について本発明を説明する。
２次元の配列で各要素に値を持つ形式の情報を画像と定義する。図１に示すように、一対のテレビカメラなどの撮像手段１−１，１−２を用いて対象情景を撮像して２つの画像を得る。これをステレオ画像と呼ぶ。もし、一対の撮像手段１−１，１−２の光軸が互いに平行でかつ撮像面が同一平面上にないならば、画像補正部３で取得したカメラの外部（幾何）パラメータおよびカメラ内部パラメータを用いて、互いに平行に置かれた一対の撮像手段１−１，１−２で得られた画像と等価となるように画像補正を行ない、特徴抽出部４において２つの画像毎に特徴画像を抽出する。
【００１６】
次いで、上記特徴画像を入力とし、ステレオ対応付け部５で情景中にある立体２の２つの画像での投影点を定めることで２つの画像を対応付け、２つの画像間での位置のずれ（両眼視差：以下では単に視差と呼ぶ) を求め、距離変換部６において前記した式(1a)〜(1c)によりカメラ１−１からの３次元位置を定める。
２つの画像での同一立体２の投影点は、一方の画像のある部分ついて他方面像中から似通った部分を探索することで得る。ここで、対象情景中に類似した形状の立体が複数あったり、繰り返し模様を含む物体があると、それら類似パターンのために似通った部分が複数存在して対応が曖昧となる。このような場合に、最も似通った部分と対応付けると、画像のノイズや照明の影響により容易に誤った部分と対応して、実際とは異なった３次元位置を算出する可能性がある。
【００１７】
そこで、本発明では、両画像間での対応の唯一性を対応の安定度の指標として、対象領域の位置によらず、対応の安定度（唯一度）の高い順序で対応付けることで、従来手法の問題である固定の走査順序による誤った対応情報の伝播を防ぐ。これにより繰り返しパターンの存在下でも安定な対応は他の影響を受けず正しい対応を得ることを可能とする。
また、繰り返しパターン部など局所的には類似したパターンがあり安定度が低い部分の対応を求めるときには、周囲にある既に対応の求まった安定度の高い部分の視差値の助けを得ることで対応情報を伝播していき、徐々に安定した対応を得る。このように、対応が唯一で曖昧性がないという意味で最適な順序で対応を求めているので、繰り返しパターンの存在下でも安定した対応が得られる。
上記対応の唯一性は次のように求める。一方の画像の着目領域と他方画像での対応候補領域とで定義される何らかの類似度を、候補領域を走査しながら求めた類似度分布について、類似度が最も高い部分が次に高い部分に比べて突出しているほど唯一性が高いとする。
【００１８】
すなわち、本発明においては、図１に示すように、ステレオ対応付け部５に、撮像した同じ物体を含む情景の画像を小領域に分割する小領域分割手段５ａと、一方の画像の各小領域に対して、他方画像の探索範囲内における局所画像の対応の唯一性を評価して対応度を定める対応度計算部５ｂと、上記対応度に基づき処理順序を決定する処理順序決定部５ｃと、上記処理順序で上記両小領域を対応付ける小領域対応付け部５ｄを設ける。そして、対応度計算部５ｂにおいて、対応の求まっていない小領域毎に探索領域内での類似度の分布を作成し、該類似度の分布から対応可能性を決める対応度を求める。次いで、処理順序決定部５ｃで対応度のよいものから順番に並べ、小領域対応付け部５ｄにおいて安定した対応が得られる部分から順に対応を求めていく。
また、類似パターンなどで局所的には対応が求まらない部分については、周囲にある既に対応が求まった部分の対応情報を利用することで徐々に安定した対応を得る。
【００１９】
対応付ける特徴量としては、エッジを用いる場合にはコントラストによらず着目領域内の全てのエッジ点を用い、輝度値を用いる場合には、着目領域内の輝度値分布をそのまま利用することで、十分な数の特徴により安定した類似度分布を得て、正しい対応の取得を可能となる。
これにより、対応が明らかな部分は他に影響されず安定に対応が求まり、繰り返しパターンなどで対応が不明確な部分は周囲からの既に対応の求まった小領域の対応情報を使用することで安定した対応を得ることができる。
したがって、画像全体に渡って安定して正しい視差が得られるので、立体の３次元位置や形状を正しく求めることが可能となる。
また、上記において、一方の画像から同一画像へ対応を求めた場合の自己対応度と、一方の画像から他方の画像へ対応を求めた場合の他己対応度を用いて小領域の対応度を求めてもよい。
【００２０】
【発明の実施の形態】
図２は本発明の実施例のシステムの構成例を示す図である。同図において、１１はＣＰＵ、１２はＣＲＴ、液晶ディスプレイ等の表示装置、キーボード、マウス等の入力装置から構成される入出力装置、１３はＲＯＭ、ＲＡＭ等から構成されるメモリ、１４はプログラム、データ等を記憶する外部記憶装置、１５は電話回線を使用してデータ通信をするためのモデム、ＬＡＮ等のネットワークを使用してデータ通信を行うためのネットワークカード等を含む通信インタフェースである。
【００２１】
撮像装置（以下カメラという）１−１，１−２で撮像された対象情景は、インタフェースＩ／Ｆを介してＣＰＵ１１に入力される。外部記憶装置１４には本発明の処理を行うためのプログラムが格納されており、ＣＰＵ１１に入力された対象情景は上記プログラムで処理されて立体形状が検出され、処理結果が外部記憶装置１４に格納され、また入出力装置１１から出力される。また、第３のカメラ１−３を設け、第３のカメラ１−３で撮像された対象情景をＣＰＵ１１に入力し、上記カメラ１−１，１−２で撮像された対象情景に加えて、カメラ１−３で撮像された対象情景を利用して立体形状を検出するようにしてもよい。
【００２２】
次に本発明の第１の実施例の対応付け処理の概略を図３により説明する。なお、ここでは２台のカメラを用いて対象情景を撮像した場合について説明するが、上記のように３台以上のカメラを用い、これらのカメラで撮像された対象情景のそれぞれの対応を取り、より対応度の高いものを用いて立体形状を検出するようにしてもよい。
図３において、カメラ１−１，１−２により対象情景を撮像し、その結果であるａ，ｂの２つの濃淡画像（左右濃淡画像) を得る。ここで、一対のカメラ１−１，１−２間の位置関係は任意とするが、あらかじめ何らかの手段によって２つのカメラ間の幾何的な関係は求まっているものとする。なお、ここでは便宜上カメラ１−１を左カメラ、カメラ１−２を右カメラと呼ぶ。以下ではこの規則にのっとり、左と右の接頭文字を付けて２つのカメラの出力を区別する。
【００２３】
次に、画像補正部３では、２つのカメラ１−１，１−２で撮像された２つの画像について、２つのカメラ１−１，１−２の光軸が平行で、しかも撮像面が同一平面となるような関係（基準配置) にしたときに観測できる画像となるように、画像補正部３においてカメラ間の幾何関係を用いて２つの濃淡画像ａ、ｂを補正し、左右補正濃淡画像ｃ，ｄを得る。
上記補正は、任意位置でのカメラに対する基準配置のカメラのＸ，Ｙ，Ｚ軸それぞれの回転角度をθ、φ、ξとし、２次歪み係数をκとすると、基準配置での画像の座標ｐc （ｘc ，ｙc ）は、任意位置で撮像された画像の座標ｐo （ｘo ，ｙo ）を用いて以下の式(2a)，（2b) のように表される。
【００２４】
【数１】
0004424797.tif 000002
【００２５】
この関係式により任意配置のカメラで撮像された両画像を基準配置のカメラで撮像した画像に変換できる。これら補正濃淡画像ｃ，ｄより特徴抽出部４で２つの画像毎に特徴画像ｅ，ｆ（エッジ点、エッジ強度、エッジ方向) を求める。
エッジ点、エッジ強度、エッジ方向を求める手段についてはここでは言及しないが、例えばエッジ点は濃淡画像にラプラシアンガウシアンを積和的に作用させたもののゼロ交差点から得られ、エッジ強度は濃淡画像にグラーディエントガウシアンを積和的に作用させて得られたベクトルの大きさで、また、エッジ方向はそのベクトルの方向でそれぞれ得ることもできる。
ステレオ対応付け部５では、これら特徴画像ｅ，ｆを入力として２つの画像のエッジ点間の対応付け処理を行ない、各エッジ点位置について視差値を持つ視差画像ｇを得る。この視差画像ｇより距離変換部６で前記式(1a)〜(1c)で示した関係式を用いて対象物の距離ｈを算出する。
【００２６】
次に、図３におけるステレオ対応付け処理部５の詳細について図４により説明する。
ステレオ対応付け処理部５では、図４に示すように、まず左特徴画像を、小領域分割部５ａにおいて一定の大きさの小領域に分割する。このとき、小領域は互いに重ならないように配置しても良いし、互いにある程度重なるように小領域を配置しても良い。ここでは、小領域の一辺の大きさの１／２だけずらしながら配置したものを考える。
次に、対応度計算部５ｂでは、対応の求まっていない小領域（以下では未対応小領域と呼ぶ) 毎に、属するエッジ点と、その対応候補点を用いて対応可能性の善し悪しを決める対応度を求める。ここで、対応候補点とは、他方特徴画像（右特徴画像) のエピポーラ線上で対応探索範囲にあるエッジ点群でエッジの属性（エッジ強度とエッジ方向) が対応付ける対象のエッジと類似しているものを指す。また、対応度を求めるとは、小領域を代表する視差（代表視差と呼ぶ) を求めるとともに、その視差がどれだけ安定しているかを定めることを意味する。
【００２７】
これに続き、対応度による処理順序決定部５ｃでは、未対応小領域について対応度の良いものから順に並べ、その上位α％を「対応付け処理対象小領域」とする。ここで、上位α％の代わりに、上位β個としても良い。
次に、上記「対応付け処理対象小領域」とされた各小領域について、小領域対応付け部５ｄにおいて、小領域に属す各エッジ点について、他方特徴画像を調べ。そして、小領域の代表視差に相当する位置に実際にエッジ点があれば、それらエッジ点対を対応付ける。これにより、各エッジ点毎の視差値が求まる。それを前記した視差画像ｇに書き込む。さらに、実際に対応付けたエッジ点があれば、その旨を記録しておく。
次いで、対応点が一点以上求まったかを調べ、対応点が一点以上求まった場合には、前記対応度計算部５ｂに戻り、その周囲の未対応小領域に周囲伝播（後述する）させ、さらに対応度の良いものから悪いものへの一連の処理を繰り返す。そして対応点が求まらなくなったら処理を終了する。
【００２８】
次に、上記対応度計算部５ｂについて図５を用いて説明する。対応度計算部５ｂにおいては、まず、小領域の中から未対応であってまだ対応度を計算していないものがあるかを調べ、未対応領域を求める（５ｂ−１）。
そして、未対応領域について視差のヒストグラムを作成し、対応の類似度分布を求める（５ｂ−２）。
続いて対応度計算処理部５ｂ−３で小領域の代表視差および対応度を実際に計算する。この操作を対応度を求めていない未対応小領域について繰り返す。
【００２９】
ここで、上述した視差のヒストグラムの作成方法について図６により説明する。ここでは左画像のある小領域について考える。
左画像の小領域に属す全てのエッジ点について次の操作を行なう。まず、あるエッジ点ＰＬi に着目する。ここでは、左右補正画像は光軸が平行で撮像面が同一平面に位置するカメラで撮像された場合と同じとなるように補正されているので、ＰＬi のエピポーラ線は水平線となり、ＰＬi を右画像に投影するとＰＬi'の位置となる。
ＰＬi の対応点はＰＬi'と同一水平線上で、かつ、ＰＬi'よりも左側に位置する。ここで、探索範囲をＲとして、ＰＬi'から左に最大Ｒまで走査していき、得られたエッジ点の中で、ＰＬi と属性値であるエッジ強度とエッジ方向が類似したエッジ点を対応候補点として抽出する。そして、これら対応点対とで定義される視差値でもって、横軸を視差値とし縦軸を頻度とする視差のヒストグラムに投票する。
【００３０】
図６では、ＰＲ１〜ＰＲ３がＰＬi のエピポーラ線上から得られ、ＰＲ２、ＰＲ３は属性値が類似していたので対応候補となったが、ＰＲ１は属性値が異なっていたので対応候補とならなかった場合を示している。対応候補点ＰＲ２、ＰＲ３については、同図に示すようにそれぞれ視差がｄ１，ｄ２となり、これを視差のヒストグラムに投票する。
同様の操作を、左小領域内の各エッジ点について行なうことにより、図６に示すような類似度分布として視差のヒストグラムが得られる。
【００３１】
次に、図５に示した対応度計算処理部５ｂ−３について図７により説明する。まず、図６に示した類似度分布に基づいて対応度算出部５ｂ−３１で対応度を計算する。対応度が閾値以下ならば周囲視差伝播部５ｂ−３２で周囲の小領域の対応情報を元に代表視差を決定するとともに対応度を再計算する。もし、対応度が閾値以上ならばその対応度を採用する。
以下、対応度算出部５ｂ−３１について更に詳述する。
ここで、図８に示すような類似度分布があったとする。ここでは、類似度分布のピークの大きさの大きい順にＰ１，Ｐ２，…とし、それを与える視差値をｄ１，ｄ２…とし、最大ピークＰ１の左右それぞれでの谷の位置をｖ１，ｖ２としている。ここで、最大ピーク値（Ｐｍ）、ピーク比（Ｐｒ）、尖度（Ｐｋ）、対応集中度（Ｐｃ）を以下のように定義する。
【００３２】
Ｐｍ＝Ｐ１／（小領域の一辺の大きさ）…(3a)
Ｐｒ＝１−Ｐ２／Ｐ１…(3b)
Ｐｋ＝ｍ（４）／〔ｍ（２）・ｍ（２）〕−３…(3c)
Ｐｃ＝（ｖ１〜ｖ２までの面積）／（少領域内のエッジ点の個数）…(3d)
【００３３】
ただし、ｍ（ｋ）は以下の式(3e)(3f)に示すように、視差値をｄとしてｖ１〜ｖ２までの値を用いた視差頻度のｋ次モーメントを表す。なお、式(3e)(3f)において、ｄは視差値、ｄｖは視差値の平均、Ｐ（ｄ）は視差ｄでの頻度、ｖ１は最小視差値、ｖ２は最大視差値を表す。
【００３４】
【数２】
0004424797.tif 000003
【００３５】
そして、対応度Ｓｍは、Ｐｍ，Ｐｒ，Ｐｋ，Ｐｃと任意の混合関数ｆ（・）を用いて以下の式(3g)のように定義する。
Ｓｍ＝ｆ（Ｐｍ，Ｐｒ，Ｐｋ，Ｐｃ）…(3g)
ここで、ｆ（・）は任意であるが、一例として、次の式(3h)のように定義できる。ただし、ｋ１〜ｋ４は任意の混合係数である。
ｆ（Ｐｍ，Ｐｒ，Ｐｋ，Ｐｃ）
＝ｋ１・Ｐｍ＋ｋ２・Ｐｒ＋ｋ３・Ｐｋ＋ｋ４・Ｐｃ…(3h)
【００３６】
次に、図７に示した周囲視差伝播部５ｂ−３２について説明する。図９に示すように着目小領域の周囲のある一定範囲に存在するＮｗ個の小領域をＷｎ（ｉ）｛ｉ：ｊ＝１〜Ｎｗ｝、その中で既に対応の求まったＮｍ個の小領域群（図９の斜線を付した領域）をＷｍ（ｉ）｛ｉ：ｊ＝１〜Ｎｍ｝とし、Ｗｍ（ｉ）が持つ代表視差値を周囲小領域視差ｄｍ（ｉ）｛ｉ：ｊ＝１〜Ｎｍ｝とする。
次に、図１０に示すように周囲小領域視差ｄｍ（ｉ）を横軸にとり、縦軸に頻度を取った周囲小領域視差ｄｍ（ｉ）の値のヒストグラムを作成する。このヒストグラムの最大ピークをＰｄ１、次ピークをＰｄ２として、最大ピークを与える視差をｄｎとする。
ここで、対応率Ｎｍ／Ｎｗが閾値以上で、かつ、図１０に示すｄｍ（ｉ）のヒストグラムの最大ピークが次ピークに比べ十分大きいなら、そのピークを与える視差値ｄｎを周囲代表視差とする。
【００３７】
次に、図１１に示すように、着目小領域の視差のヒストグラムについて、第１、第２、第３ピークそれぞれの左右の谷部を求め、それに挟まれる領域を第１山（ｖ１１〜ｖ１２）、第２山（ｖ２１〜ｖ２２）、第３山（ｖ３１〜ｖ３２）とする。
周囲の小領域から求めた代表視差ｄｎが第１山、第２山、第３山のいずれかに含まれるなら、その山の最大値を与える視差を代表視差とする。また、その時の対応度をＷｍ（ｉ）の対応度の平均値とする。
【００３８】
以上説明したように、本実施例においては、対応度、代表視差を求めて対応度の順に処理順序を決定して２つの画像のエッジ点を対応付け、各エッジ点位置について視差値を持つ視差画像を得ているので、従来手法の問題である固定の走査順序による誤った対応情報の伝播を防ぐことができ、正しい対応を得ることができる。また、局所的には対応が求まらない部分については、周囲にある既に対応が求まった部分の対応情報を利用して、徐々に安定した対応を得ているので、繰り返しパターンなどの存在下でも安定した対応を得ることができる。
【００３９】
上述した第１の実施例では、類似度をエッジを用いて求めているが、類似度として輝度の正規化相関値、輝度差の絶対値和（ＳＡＤ) 、輝度値の差の２乗和（ＳＳＤ）のいずれかの値を用いることもできる。
以下、輝度の正規化相関値、輝度差の絶対値和（ＳＡＤ) 、輝度値の差の２乗和（ＳＳＤ）を用いる本発明の第２に実施例について説明する。
本実施例の処理は、前記図２〜図１１により説明した第１の実施例の処理と基本的には同じであるが、前記図８に示した類似度分布を、輝度の正規化相関値、輝度差の絶対値和（ＳＡＤ) もしくは輝度値の差の２乗和（ＳＳＤ）を用いて求める。
【００４０】
すなわち、図１２に示すように、一方画像の対応付け対象の小領域Ａに対して、他方画像の探索領域に設けた同形状の小領域Ｂとで計算される輝度の正規化相関値、輝度差の絶対値和（ＳＡＤ) 、輝度値の差の２乗和（ＳＳＤ）のいずれかの値をＶとするとき、（Ｃ−Ｖ）を類似度として、探索領域内での小領域を走査しながら類似度分布を作成する。なお、Ｃは類似度を負値にしないための任意の定数である。それ以外の処理は、第１の実施例と同様であり、上記類似度に基づき対応度を計算して処理順序を決定し対応付けを行う。
【００４１】
以下に、上記正規化相関値、輝度差の絶対値和（ＳＡＤ) 、輝度値の差の２乗和（ＳＳＤ）について説明する。
▲１▼正規化相関
左画像の小領域内の各位置（ｉ，ｊ）での輝度値をｑL （ｉ，ｊ）、右画像の小領域Ｂの各位置（ｉ，ｊ）での輝度値をｑR （ｉ，ｊ）、小領域の一辺の大きさをｗとして、正規化相関値は次の式(4a)〜(4c)で表される。
【００４２】
【数３】
0004424797.tif 000004
【００４３】
▲２▼輝度値の絶対和（ＳＡＤ）
上記▲１▼と同じ記号を用いると輝度差の絶対値和Ｅ２は次の式(5a)で表される。
【００４４】
【数４】
0004424797.tif 000005
【００４５】
▲３▼輝度差の２乗和（ＳＳＤ）
上記▲１▼と同じ記号を用いると輝度差の２乗和Ｅ３は次の式(6a)で表される。
【００４６】
【数５】
0004424797.tif 000006
【００４７】
以上の実施例では、図７に示した対応度算出部５ｂ−３１で対応度を計算する際、一方の画像から他方の画像への対応を求めた場合の他己対応度を用いているが、他己対応度に加え、一方の画像から同一画像へ対応を求めた場合の自己対応度を用い、その両者から対応度を求めることもできる。
以下、上記自己対応度を用いた本発明の第３の実施例について説明する。
本実施例の処理は、前記図２〜図１１により説明した第１の実施例の処理と基本的には同じであるが、上記したように他己対応度Ｓ１に加え、自己対応度Ｓ２を導入する。
自己対応度Ｓ２は図１３に示すように左画像中の小領域Ａと同一左画像の左探索範囲内の候補領域Ｃとで定められる類似度ヒストグラムより同様に計算される。図１３に示す左探索範囲は、着目小領域Ａを挟んで左右に同じだけ右画像の探索範囲分の幅を持つ。また、他己対応度Ｓ１は図１３に示すように左画像での小領域Ａと右画像の右探索範囲内の候補領域Ｂとで定められる類似度ヒストグラムより前記実施例で定義された方法で計算される。
【００４８】
対応度算出部５ｂ−３１における対象小領域Ａの対応度の算出は、上記２つの対応度Ｓ１，Ｓ２からｆ２（Ｓ１，Ｓ２）の混合関数を用いた値として算出される。ここで、ｆ（・）は任意であるが、例えば以下のようなものが考えられる。
ｆ２（Ｓ１，Ｓ２）＝Ｃ１・Ｓ１＋Ｃ２・Ｓ２
ここで、Ｃ１，Ｃ２は任意の混合係数である。
本実施例においては、以上のようにして算出された対応度を用いて、前記第１の実施例で説明した手法により対応付け処理を行い、以下第１の実施例と同様な処理を行って視差画像を得る。
【００４９】
【発明の効果】
以上のように本発明においては、以下の効果を得ることができる。
（１）両画像間の対応付けを、画像の位置によらず対応の唯一性に基づいて正しい対応が得られる順序で行うことにより、従来方式の問題であった、固定の走査順序による誤った対応情報の伝播を防ぐことができる。さらに、類似パターンなどで安定度が低く対応付けが困難な部分については、周囲にある安定度の高い対応の視差値を参考に対応を求めることで、  従来では対応付けが困難であった繰り返しパターン部の対応を安定に得ることができ、画像全体について正しい対応を得ることができる。
（２）対応付ける特徴量としては、エッジを用いる場合にはコントラストによらず着目領域内の全てのエッジ点を用い、輝度値を用いる場合には着目領域内の輝度値分布をそのまま利用することで、十分な数の特徴を使用して安定した類似度分布形状を得ることができる。
これにより、高コントラストのエッジ点など一部の特徴を用いた際に起こり得る少量の偽の部分による顕著な類似度ピークの形成の阻害がなくなり、画像全体から正しい対応を得ることができる。
【図面の簡単な説明】
【図１】本発明の原理を説明する図である。
【図２】本発明の実施例のシステムの構成例を示す図である。
【図３】第１の実施例の対応付け処理の概略を示す図である。
【図４】図３に示したステレオ対応付け処理部の詳細を示す図である。
【図５】図４に示した対応度計算部の詳細を示す図である。
【図６】視差のヒストグラムの作成方法を説明する図である。
【図７】図５に示した対応度計算処理部の詳細を示す図である。
【図８】類似度分布とピークとの関係を示す図である。
【図９】対象小領域と周囲小領域の関係を示す図である。
【図１０】周囲小領域の視差のヒストグラムを示す図である。
【図１１】対象少領域の視差のヒストグラムと山との関係を示す図である。
【図１２】相関値／ＳＳＤ値／ＳＡＤ値を用いた類似度分布の作成を説明する図である。
【図１３】自己対応度と他己対応度の関係を示す図である。
【図１４】ステレオ距離計測の原理を説明する図である。
【符号の説明】
１−１〜１−３  撮像手段（カメラ）
２              立体
３              画像補正部
４              特徴抽出部
５              ステレオ対応付け部
５ａ            小領域分割手段
５ｂ            対応度計算部
５ｃ            処理順序決定部
５ｄ            小領域対応付け部
６              距離変換部
【図１】
0004424797.tif 000007
【図２】
0004424797.tif 000008
【図３】
0004424797.tif 000009
【図４】
0004424797.tif 000010
【図５】
0004424797.tif 000011
【図６】
0004424797.tif 000012
【図７】
0004424797.tif 000013
【図８】
0004424797.tif 000014
【図９】
0004424797.tif 000015
【図１０】
0004424797.tif 000016
【図１１】
0004424797.tif 000017
【図１２】
0004424797.tif 000018
【図１３】
0004424797.tif 000019
【図１４】
0004424797.tif 000020