トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 対応点探索方法及びこれを用いたマッチング装置
【発明者】 【氏名】岩舘 祐一

【氏名】今泉 浩幸

【氏名】片山 美和
【要約】 【課題】誤差や探索誤りを軽減し、滑らかな対応点探索が可能な技術を提供することにある。

【解決手段】一対の撮像画像の内の一方の撮像画像の画素毎の対応先を、他方の撮像画像において特定する画像間の対応点探索方法において、前記一方の撮像画像での走査線を特定するステップと、前記他方の撮像画像の探索範囲に含まれる視差ベクトル値を状態遷移モデルのノードとして設定するステップと、予め設定されたブロック内のマッチング誤差及び隣接ノード間でのベクトルの連続性を前記状態遷移モデルのノード間のパスの重みとして設定するステップと、前記状態遷移モデルに基づいてビタビアルゴリズムにより前記他方の撮像画像の１走査線上の各画素の対応点を一括して推定するステップとを備える。
【特許請求の範囲】
【請求項１】 一対の撮像画像の内の一方の撮像画像の画素毎の対応先を、他方の撮像画像に対して特定する画像間の対応点探索方法において、前記一方の撮像画像での走査線を特定するステップと、前記他方の撮像画像の探索範囲に含まれる視差ベクトル値を状態遷移モデルのノードとして設定するステップと、予め設定されたブロック内のマッチング誤差及び隣接ノード間でのベクトルの連続性を前記状態遷移モデルのノード間のパスの重みとして設定するステップと、前記状態遷移モデルに基づいてビタビアルゴリズムにより前記他方の撮像画像の１走査線上の各画素の対応点を一括して推定するステップとを備えることを特徴とする画像間の対応点探索方法。
【請求項２】 請求項１に記載の画像間の対応点探索法において、前記一方の撮像画像での走査線に前後する何れか一の走査線での画素の視差ベクトル値を、前記状態遷移モデルの拘束条件とするステップを備えたことを特徴とする画像間の対応点探索方法。
【請求項３】 動画像の連続するフレーム間での画素毎の対応先を特定するフレーム間の対応点探索方法において、前記動画像の内の先のフレーム像での走査線を特定するステップと、前記先の動画像に連続する後の動画像の２次元方向の探索範囲に含まれる動きベクトル値を状態遷移モデルのノードとして設定するステップと、予め設定されたブロック内のマッチング誤差及び隣接ノード間でのベクトルの連続性を前記状態遷移モデルのノード間のパスの重みとして設定するステップと、前記状態遷移モデルに基づいてビタビアルゴリズムにより前記後のフレームの１走査線上の各画素の対応点を一括して推定するステップとを備えることを特徴とするフレーム間の対応点探索方法。
【請求項４】 一対の撮像画像の内の一方の撮像画像の画素毎の対応先を、他方の撮像画像において特定するマッチング装置において、前記一方の撮影画像の１走査線上の画素と前記１走査線に対応する前記他方の撮像画像の探索範囲の画素とから視差ベクトル値を演算する手段と、視差ベクトル値を状態遷移モデルのノードとして設定すると共に、予め設定されたブロック内のマッチング誤差及び隣接ノード間でのベクトルの連続性を前記状態遷移モデルのノード間のパスの重みとして設定し、前記状態遷移モデルに基づいてビタビアルゴリズムにより前記他方の撮像画像の１走査線上の各画素の対応点を一括して推定する手段とを備えたことを特徴とするマッチング装置。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、対応点探索方法及びこれを用いたマッチング装置に関し、特に、ステレオ画像の対応点探索法や動画像の動きベクトル探索法に適用して有効な技術に関するものである。
【０００２】
【従来の技術】画像間の対応点探索法として最も基本的な手法はブロックマッチング法であり、ＭＰＥＧ等の符号化システムで動きベクトル検出用途で実用されている。或いは、ステレオ画像による距離計測システムなどでも利用されており、幾つかのシステムが市販されている。
【０００３】この手法はアルゴリズムが簡単であるが、雑音による誤差や対応点探索の手がかりとなるテキスチャが少ない場合には誤りが生じ易いという欠点がある。
【０００４】この欠点を改善するために、「朴鍾一、井上誠喜、“映像合成のための多眼カメラを用いた奥行き抽出”、信学技法、ＰＲＭＵ９６−１３３，ｐｐ．３３−４０，１９９７−０１．」に開示される、縮小画像を階層的に生成しておき、低解像度画像から順次ブロックマッチングを行うことにより破綻の少ない対応点探索が可能な階層型ブロックマッチング法がある。また、「Ｗ．Ｗｏｏ，Ｎ．Ｋｉｍａｎｄ Ｙ．Ｉｗａｄａｔｅ，“Ｏｂｊｅｃｔ Ｓｅｇｍｅｎｔａｔｉｏｎｆｏｒ Ｚ−ｋｅｙｉｎｇ Ｕｓｉｎｇ Ｓｔｅｒｅｏ Ｉｍａｇｅｓ，”ｉｎＰｒｏｃ．ＩＥＥＥ ＷＣＣ−ＩＣＳＰ’００，ｐｐ．１２４９−１２５４，Ａｕｇ．２０００．」に開示される、隣接する画素との連続性を考慮して対応点を探索する手法の研究例がある。また、「Ｙｕｉｃｈｉ ＯＨＴＡ，ＴａｋｅｏＫＡＮＡＤＥ，“Ｓｔｅｒｅｏ ｂｙ Ｉｎｔｒａ−ａｎｄ Ｉｎｔｅｒ−Ｓｃａｎｌｉｎｅ Ｓｅａｒｃｈ Ｕｓｉｎｇ Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｍｉｎｇ”，ＩＥＥＥ Ｔｒａ．Ｏｎ Ｐ．Ａ．Ｍ．ｌ．，Ｖｏｌ．ＰＡＭ−７，Ｎｏ．２，ｐｐ．１３９−１５４，Ｍａｒｃｈ １９８５．」に開示されるように、ビタビアルゴリズムを用いたステレオ画像の対応点探索に関しても研究例がある。この方法では、画像中の１走査線上のエッジ位置をノードとした状態遷移モデルを構成し、近傍エッジとの距離をパラメータとしたコスト関数を用いている。
【０００５】
【発明が解決しようとする課題】本発明者は、前記従来技術を検討した結果、以下の問題点を見いだした。従来手法の一つである階層型ブロックマッチング法では、単純なブロックマッチング手法に対して、雑音の影響やテキスチャが少ない部分で生じる誤りなどの影響を軽減できることが知られている。しかし、階層数やブロックサイズに依存して性能が異なり、必ずしも十分な効果が得られない場合もある。
【０００６】また、隣接画素との連続性を考慮した手法においては、隣接画素との拘束条件のみを用いているために、十分に滑らかな対応点が得られないという問題がある。
【０００７】さらには、従来のビタビアルゴリズムによる方法では、高解像度の視差ベクトルが得られるものの、エッジの位置情報のみを使っているために雑音による誤差が生じてしまうという問題がある。
【０００８】本発明の目的は誤差や探索誤りを軽減し、滑らかな対応点探索が可能な技術を提供することにある。
【０００９】本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかになるであろう。
【００１０】
【課題を解決するための手段】本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記のとおりである。
【００１１】（１）一対の撮像画像の内の一方の撮像画像の画素毎の対応先を、他方の撮像画像において特定する画像間の対応点探索方法において、前記一方の撮像画像での走査線を特定するステップと、前記他方の撮像画像の探索範囲に含まれる視差ベクトル値を状態遷移モデルのノードとして設定するステップと、予め設定されたブロック内のマッチング誤差及び隣接ノード間でのベクトルの連続性を前記状態遷移モデルのノード間のパスの重みとして設定するステップと、前記状態遷移モデルに基づいてビタビアルゴリズムにより前記他方の撮像画像の１走査線上の各画素の対応点を一括して推定するステップとを備える。
【００１２】（２）動画像の連続するフレーム間での画素毎の対応先を特定するフレーム間の対応点探索方法において、前記動画像の内の先の動画像での走査線を特定するステップと、前記先の動画像に連続する後のフレームの２次元方向の探索範囲に含まれる動きベクトル値を状態遷移モデルのノードとして設定するステップと、予め設定されたブロック内のマッチング誤差及び隣接ノード間でのベクトルの連続性を前記状態遷移モデルのノード間のパスの重みとして設定するステップと、前記状態遷移モデルに基づいてビタビアルゴリズムにより前記後のフレームの１走査線上の各画素の対応点を一括して推定するステップとを備える。
【００１３】（３）一対の撮像画像の内の一方の撮像画像の画素毎の対応先を、他方の撮像画像において特定するマッチング装置において、前記一方の撮影画像の１走査線上の画素と前記１走査線に対応する前記他方の撮像画像の探索範囲の画素とから視差ベクトル値を演算する手段と、視差ベクトル値を状態遷移モデルのノードとして設定すると共に、予め設定されたブロック内のマッチング誤差及び隣接ノード間でのベクトルの連続性を前記状態遷移モデルのノード間のパスの重みとして設定し、前記状態遷移モデルに基づいてビタビアルゴリズムにより前記他方の撮像画像の１走査線上の各画素の対応点を一括して推定する手段とを備えた。
【００１４】前述した手段によれば、一方の撮像画像での走査線を特定し、視差ベクトルの探索範囲に含まれる視差ベクトル値を状態遷移モデルのノードとして設定し、マッチング誤差及び隣接ノード間のベクトルの連続性を状態遷移モデルのノード間のパスの重みとして設定し、この状態遷移モデルに基づいて、ビタビアルゴリズムにより前記他方の撮像画像の１走査線上の各画素の対応点を一括して推定するので、滑らかで誤差の少ない視差ベクトルを求めることができる。
【００１５】また、動画像の連続するフレーム間での画素毎の対応先を特定するフレーム間の対応点を探索する場合には、動画像の内の先のフレームでの走査線を特定し、先のフレームに連続する後の動画像の２次元方向の探索範囲に含まれる動きベクトル値を状態遷移モデルのノードとして設定し、予め設定されたブロック内のマッチング誤差及び隣接ノード間（連続するフレーム間）でのベクトルの連続性を状態遷移モデルのノード間のパスの重みとして設定し、この状態遷移モデルに基づいてビタビアルゴリズムにより後の動画像の１走査線上の各画素の対応点を一括して推定するので、滑らかで誤差の少ない動画像の動きベクトルを求めることができる。
【００１６】
【発明の実施の形態】以下、本発明について、発明の実施の形態（実施例）とともに図面を参照して詳細に説明する。なお、発明の実施の形態を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
【００１７】（実施の形態１）図１は本発明の実施の形態１の画像間の対応点探索方法を説明するための図であり、特に、ビタビアルゴリズムを適用するための状態遷移を説明するための図である。ただし、一対の画像に対して、周知のビタビアルゴリズムを適用するための状態遷移を示すものである。
【００１８】図１に示すように、実施の形態１では、画像の左端側（０（ゼロ）で示す）で始まり、右端側（Ｎ−１で示す）で終わる場合を示すものである。従って、画像の収集手段として、例えば周知のテレビカメラを用いる場合には、走査線の左端で始まり、右端で終わることとなる。
【００１９】この場合、それぞれの画素位置には、探索範囲０〜Ｓ−１に対応したノード１０１からなる列があり、このノード列間が図１中に矢印で示すパス１０２で結ばれている。このパス１０２は対応度を表すマッチング誤差エネルギー成分と、視差ベクトルの滑らかさを表す視差ベクトル場のエネルギー成分とにより重み付けされている。このとき、図１から明らかなように、パス１０２の組み合わせは水平画素数をＮとした場合、ＳＮ通り存在することとなるが、実施の形態１ではビタビアルゴリズムを適用する構成となっているので、このパス１０２の組み合わせからマッチング誤差が小さく、且つ視差ベクトルが滑らかになるような最適なパス１０２を効率的に推定することができる。このとき、各画素の視差ベクトルは、最適パスが通過するノード番号として得られる。ただし、実施の形態１では、ビタビアルゴリズムで最適パスを推定するにあたり、前述するように、図１の左端から計算を始め、各画素位置のそれぞれのノード１０１で、生き残りパスを求める。
【００２０】例えば、カメラを並行移動して撮影した図２に示すような２枚のステレオ画像の場合には、Ｒ画像の所定の走査線上の画素の対応点は、必ずＬ画像の同じ走査線上に存在する。
【００２１】従って、実施の形態１の対応点探索方法では、一つの走査線上の各画素に対する視差ベクトル値をノード１０１とする状態遷移を図１に示すように構成し、一つの走査線上の各画素に対応する視差ベクトルをビタビアルゴリズムを用いて一括して求める。
【００２２】次に、図３にビタビアルゴリズムによる生き残りパスの推定手順を説明するための図を示し、以下、図３に基づいてビタビアルゴリズムによる生き残りパスの推定手順を説明する。なお、以下の説明では、図１に示す画素位置ｉ−１から画素位置ｉへのＳ本のパス１０２から１本のパスである生き残りパスを決定する手順を説明する。ただし、このときの決定法は、マッチング誤差と視差ベクトルの滑らかさを基にして決定する。
【００２３】画素位置ｉの任意の位置ｖのノード１０１での生き残りパスがもつパスメトリックをＥｖとし、Ｅｕを画素位置ｉ−１の各ノード１０１のパスメトリックとすると、Ｅｖは下記の式（１）で決定される。ただし、本願明細書中におけるパスメトリックは、生き残りパスに含まれるパスが持つエネルギーの総和を示すものである。また、ｕは画素位置ｉ−１の縦方向のノード１０１に対応しており、ｖは画素位置ｉの縦方向のノード１０１に対応しているので、ｕ及びｖはそれぞれ０≦ｕ≦Ｓ−１，０≦ｖ≦Ｓ−１となる。
【００２４】
【数１】

ここで、ｓｓｄｖは視差ベクトルをｖとした場合のマッチング誤差エネルギー、Ｄｕ，ｖは視差ベクトルの滑らかさを表すエネルギー成分であり、下記の式（２），（３）で与えられる。
【００２５】
【数２】

マッチング誤差エネルギーには、式（２）に示すように、画素ｉを中心としたＸｉで示す矩形ブロック４０２内の積分値を用いている。なお、画素ｉを中心としたＸｉで示す矩形ブロック４０２内の積分値については、後述する。
【００２６】また、滑らかさは式（３）に示すように、ｕとｖのノルムである。なお、式（１）の初期値は、ｉ＝０の場合にＥｕ＝０とする。
【００２７】このようにして、例えば画素位置ｉのノード１０１に入力するＳ本のパス１０２から１本のパスが決定される。画素ｉに対応するすべてのノード１０１の内から１本のパスが残されるので、画素位置ｉ−１の各ノード１０１と画素位置ｉの各ノード１０１との間には、常時Ｓ本のパスが生き残る。画素位置が右端の終点に至ったら、Ｓ本のパスの中からパスメトリックが最も小さいパスを選択し、そのパスが通過したノード番号を各画素の視差ベクトルとする。このプロセスを全ての走査線について行い、画像全体の視差ベクトルを求めることができる。
【００２８】ここで、Ｒ画像の所定の走査線上の画素の対応点は、必ずＬ画像の同じ走査線上に存在する、すなわち視差ベクトルの垂直方向の連続性と対応点が同じ垂直位置の走査線上存在するという特徴に基づいて、前述の式（３）による視差ベクトルの滑らかさを表すエネルギー成分を、下記の式（４）に示すように演算することによって、一つの走査線上の各画素に対応する視差ベクトルをビタビアルゴリズムを用いて一括して求めるものである。
【００２９】
【数３】

ただし、式（４）の第一項はエピポーラ線上の拘束条件であり、Ｒ画像での所定の画素の対応点は必ずその前画素の対応点の右側に存在することを条件としたものである。この条件はオクルージョン、すなわち一方では見えるが他方では隠されている状態になっていない限り成り立つ。
【００３０】また、第二項は垂直方向の条件である。ｄｐは１ライン前の画素位置での視差ベクトルであり、現画素位置でのｓｓｄｖが小さい、すなわち信頼性が高い場合にはこの拘束条件が小さくなるようにｓｓｄｖを乗じている。
【００３１】図４は実施の形態１の矩形ブロックを説明するための図である。図４に示すように、実施の形態１では、前述する式（２）におけるマッチング誤差エネルギーは、所定の画素（例えば、画素ｉ）を中心とした３×３画素の矩形ブロック４０２内の積分値を用いている。なお、矩形ブロック４０２の画素数は、３×３に限定されることはなく、他の画素数でもよいことはいうまでもない。
【００３２】図５は実施の形態１の対応点探索方法を用いて計算した視差ベクトル画像であり、図６は従来の対応点探索方法であるブロックマッチング法により計算した視差ベクトル画像である。
【００３３】ただし、図５及び図６は、図２に示す一対のステレオ画像から視差ベクトル画像を得たものである。また、図５に示す視差ベクトル画像は、Ｘｉで示す矩形ブロック４０２のブロックサイズが３×３画素、λＬが３０００、λＳが１０００、λ２が０．６、探索範囲が０〜３１として得られたものである。また、図５及び図６は階調の違いを分かりやすくるために、演算により得られた階調値を８倍にしたものである。
【００３４】図５及び図６から明らかなように、実施の形態１の対応点探索方法を用いて計算した視差ベクトル画像では、ブロックマッチング法により計算した視差ベクトル画像よりも得られた視差ベクトルの誤りが少ない。その結果、画像のエッジ部分の先鋭度を維持しつつ全体的に滑らかな画像を得ることができることが明らかである。
【００３５】以上説明したように、実施の形態１の対応点探索法では、１走査線上の画素列に対して、探索範囲に含まれる全ての視差ベクトル値をノード１０１とし、マッチング誤差及び隣接ノード間でのベクトルの連続性をノード間のパス１０２の重みとして状態遷移モデルを構成し、ビタビアルゴリズムにより１走査線分の視差ベクトルを一括して求めるので、滑らかで誤差の少ない視差ベクトルを求めることができる。
【００３６】また、実施の形態１の対応点探索法では、１走査線上のすべての画像情報を用いるとともに、画面垂直方向の連続性も考慮して対応点探索を行うので、雑音やテキスチャ不足による影響を受け難くすることができ、安定した対応点探索が行える。
【００３７】また、雑音に強いので、コスト関数を計算するブロックのサイズを小さくすることができ、高解像度の対応点探索が可能となる。さらには、ビタビアルゴリズムは畳み込み符号の復号などで実用化されているので、ハードウェア化も容易である。
【００３８】なお、実施の形態１の画像間の対応点探索方法では、対をなす２枚のステレオ画像に対する視差ベクトルの対応点探索法について説明したが、これに限定されることはなく、視差ベクトルの探索範囲に含まれる視差ベクトル値であるノード１０１を２次元化し、１走査線上の各画素の動きベクトルを一括して推定することによって、動画像の動きベクトルの対応点探索方法にも適用可能である。
【００３９】ただし、動画像の動きベクトルには、水平方向成分と垂直方向成分とがある。従って、動画像の動きベクトルの対応点探索方法に本願発明を適用する場合には、例えば、前述する図１に示すノード１０１を、図７に示すように面上（以下、「ノード面」と記す）に配置された複素数ノード７０１に置き換えることにより適用可能となる。ただし、図７における水平ベクトルは実数部を示しており、垂直ベクトルは虚数部を示している。
【００４０】すなわち、図７に示すように、座標位置（０，０）で示す複素数ノード７０１を基準とし、水平方向の探索範囲が±Ｈであり、垂直方向の探索範囲が±Ｖである複素数ノード７０１を図１に示す各ノード１０１毎に設ける。このとき、図１の隣接するノード１０１間のパスは、隣接するノード面間のパスとして、一方のノード面に配列される各複素数ノード７０１から他方のノード面に配列される各複素数ノード７０１への全てのノード状態の組み合わせとしてのパスとなる。
【００４１】このようにして、隣接するノード面間でのパスを定義することによって、２次元の状態遷移モデルを構成し、ビタビアルゴリズムを用いて最適パスを選択することで各ノード位置での動きベクトル値を推定することが可能となるので、滑らかで誤差の少ない動画像の動きベクトルを求めることができる。
【００４２】従って、ＭＰＥＧ符号化装置における動きベクトル探索へ本願発明を適用することが可能であり、例えば図９に示すように、前述する本願発明の動画像の動きベクトルの対応点探索方法を従来の動きベクトル探索部に適用することによって、従来の動きベクトル探索部を本願発明の動画像の動きベクトルの対応点探索方法を用いた動きベクトル探索部９０１に置き換えることが可能である。すなわち、図９に示すように、本願発明を適用した動きベクトル探索部９０１の出力を周知のＭＰＥＧ映像符号化部９０２と周知の動きベクトル符号化部９０３とに入力し、ＭＰＥＧ映像符号化部９０２と動きベクトル符号化部９０３とからの出力を周知の多重化手段９０４で多重化することによって、ＭＰＥＧ符号が得られることとなる。このとき、本願発明の動画像の動きベクトルの対応点探索方法を動きベクトル探索部９０１に適用することによって、動きベクトルの推定精度を向上させることが可能となるので、ＭＰＥＧ映像符号化で使われているフレーム間予測符号化の符号化効率を向上させることができる。
【００４３】また、ＭＰＥＧでは、動きベクトル情報がＤＰＣＭにより符号化されて多重伝送される。すなわち、前画素の動きベクトル値との差分のみが伝送される。この差分値はさらにハフマン符号化され、差分値が小さい情報は頻度が高い情報として短い符号が割り当てられる。従って、差分値が小さいほど効率的な伝送が期待できる。一方、従来の動きベクトル推定手法では、推定誤差が大きく、ＤＰＣＭ符号化された差分値も大きくなる場合があった。それに対して、本願発明を適用することによりビタビアルゴリズムで滑らかなベクトル列が得られるので、ＤＰＣＭ符号化された差分値を小さくすることができ、動きベクトルの効率的な伝送が可能となる。
【００４４】（実施の形態２）図８は本発明の実施の形態２のマッチング装置の概略構成を説明するための図である。ただし、８０１〜８０３は格納手段、８０４〜８０７はマッチング誤差エネルギー演算手段、８０８はビタビ演算部、８０９は最小値選択部を示す。また、実施の形態２のマッチング装置は、Ｒ画像の所定の走査線上の画素の対応点が必ずＬ画像の同じ走査線上に存在する、すなわち視差ベクトルの垂直方向の連続性と対応点が同じ垂直位置の走査線上存在することを条件とするものである。さらには、実施の形態２のマッチング装置は、実施の形態１とは逆の構成であり、左側画像であるＬ画像の対応先を右側画像であるＲ画像から探索する装置である。
【００４５】図８に示す実施の形態２のマッチング装置は、右側画像（Ｒ画像）がＲ画像の入力端子から入力され、左側画像（Ｌ画像）がＬ画像の入力端子からそれぞれ入力される構成となっている。このとき、Ｒ画像およびＬ画像の入力端子から入力される画像は、それぞれが同じ１走査線の画素値が順次入力される構成となっている。すなわち、Ｒ画像およびＬ画像が同じ走査線の同じ画素順で同期して読み出され、それぞれ対応する入力端子（Ｒ画像の入力端子およびＬ画像の入力端子）に入力される構成となっている。
【００４６】また、実施の形態２のマッチング装置は、たとえばＲ画像の入力端子から入力される画素毎の画素値を順次格納する周知の格納手段８０１〜８０３を有する構成となっている。図８に示すように、各格納手段８０１〜８０３は複数個の格納手段８０１〜８０３が直列に接続される構成となっており、Ｒ画像の入力端子から入力される画素値が第１番目の格納手段（第１の格納手段）８０１から順次第３の格納手段８０３にまで、順次シフトされ格納される構成となっている。ただし、格納手段８０１〜８０３の個数すなわち段数は、Ｒ画像の探索範囲とする画素数によって適宜決定されるものである。さらには、第１の格納手段８０１に入力される画素と同じ画素の画素値が第０番目のマッチング誤差エネルギー演算手段８０４に入力される構成となっている。
【００４７】また、実施の形態２のマッチング装置は、Ｌ画像の入力端子から入力された画素毎の画素値を一方の入力とすると共に、Ｒ画像の入力端子あるいは格納手段８０１〜８０３から出力される画素値を他方の入力とするマッチング誤差エネルギー演算手段８０４〜８０７を有する構成となっている。このマッチング誤差エネルギー演算手段８０４〜８０７は、前述した実施の形態１に示すように、２つの入力から視差ベクトルをｖとした場合のマッチング誤差エネルギーｓｓｄｖを式（２）に基づいて演算する手段であり、例えば周知の情報処理装置上で動作するプログラムによって実現される。また、実施の形態２のマッチング装置は、複数のマッチング誤差エネルギー演算手段８０４〜８０７を有する構成となっており、各マッチング誤差エネルギー演算手段８０４〜８０７はＬ画像の入力に対して並列に接続される構成となっている。ただし、マッチング誤差エネルギー演算手段８０４〜８０７は、格納手段８０１〜８０３の個数に１を加算した個数となる。
【００４８】各マッチング誤差エネルギー演算手段８０４〜８０７の出力は、ビタビ演算部８０８に入力される構成となっており、ビタビ演算部８０８において周知のビタビアルゴリズムに基づいてパスメトリックの演算を順次行う構成となっている。ただし、ビタビ演算部８０８によるパスメトリックの演算は、入力される画素が走査線の左側に達した場合にリセットされる構成となっており、このような構成とすることにより走査線ごとの探索範囲のパスメトリックを演算するものである。
【００４９】ビタビ演算部８０８の出力は、最小値選択部８０９に入力される構成となっており、ビタビ演算部８０８によるパスメトリックの演算が走査線上の右端のノードに至った場合に、最小値選択部８０９はビタビ演算手段より入力されるパスメトリックの内でその値が最小となるパスを選択し、そのパスの最小のパスとして１走査分の視差ベクトルを出力する構成となっている。また、最小値選択部８０９による最小パスの選択は、画素値に入力が右端に達した場合に行う構成となっており、このような構成とすることにより走査線ごとのパスメトリックを演算するものである。また、実施の形態２のマッチング装置は、以上に説明した動作を全ての走査線について順次行う構成となっている。
【００５０】以上説明したように、実施の形態２のマッチング装置は、一対の画像の対応点を探索する際に、１走査線分の視差ベクトルを一括して求める動作を順次繰り返すことによって一対の画像の対応点を探索するので、滑らかで誤差の少ない視差ベクトルを得ることができる。
【００５１】また、１走査線上のすべての画像情報を用いるとともに、画面垂直方向の連続性も考慮して対応点探索を行うので、雑音やテキスチャ不足による影響を受け難くすることができ、安定した対応点探索が行える。
【００５２】さらには、雑音に強いので、コスト関数を計算するブロックのサイズを小さくすることができ、高解像度の対応点探索が可能となる。
【００５３】また、図１０に示すように、本願発明の対応点探索方法を用いたマッチング装置１００１の出力である視差ベクトルから距離を演算する周知の距離演算手段１００２を設けることによって、精度の高い距離情報が得ることが可能なステレオ画像による距離計測装置を構成できることはいうまでもない。ただし、Ｌ画像とＲ画像との間の対応点探索により得られる視差ベクトル（視差値）に基づいて、カメラから被写体までの距離を求めるためには、Ｌ画像とＲ画像とをそれぞれ撮影したカメラの間隔をＢ、カメラの焦点距離をＦ、カメラの画素の物理的な大きさをｐｓ、視差値（画素数）をｄとして、下記の式（５）によって演算可能である。
【００５４】
【数４】

【００５５】以上、本発明者によってなされた発明を、前記発明の実施の形態に基づき具体的に説明したが、本発明は、前記発明の実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【００５６】
【発明の効果】本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
【００５７】（１）ビタビアルゴリズムにより１走査線分の視差ベクトルを一括して求めることができるので、滑らかで誤差の少ない視差ベクトルを求めることができる。
（２）１走査線上のすべての画像情報を用いるとともに、画面垂直方向の連続性も考慮して対応点探索を行うので、雑音やテキスチャ不足による影響を受け難くすることができ、安定した対応点探索が行える。
【００５８】（３）雑音に強いので、コスト関数を計算するブロックのサイズを小さくすることができ、高解像度の対応点探索が可能となる。
（４）ビタビアルゴリズムは畳み込み符号の復号などで実用化されているので、ハードウェア化も容易である。
【出願人】 【識別番号】０００００４３５２
【氏名又は名称】日本放送協会
【出願日】 平成１３年９月１０日（２００１．９．１０）
【代理人】 【識別番号】１０００８３５５２
【弁理士】
【氏名又は名称】秋田 収喜
【公開番号】 特開２００３−８５５６６（Ｐ２００３−８５５６６Ａ）
【公開日】 平成１５年３月２０日（２００３．３．２０）
【出願番号】 特願２００１−２７３４２８（Ｐ２００１−２７３４２８）