(57)【要約】【課題】処理時間の短縮と視差の検出精度の向上とを両立させる【解決手段】測距装置１は、右画像データと左画像データを取得し、低解像度の右低解像度データと左低解像度データを作成する。測距装置１は、右低解像度データを、複数の画素で構成されたブロックに分割する。測距装置１は、複数のブロック毎に、左低解像度データ内でブロックと同じ領域が写っているブロックを、動的計画法を用いて探索することによりブロックの視差を検出する。測距装置１は、右画像データをブロックに分割する。測距装置１は、複数のブロック毎に、左画像データ内で同じ領域が写っているブロック（以下、撮影解像度対応ブロックという）をブロックマッチング法を用いて決定することにより、ブロックの視差を検出する。測距装置１は、動的計画法による視差検出結果に基づき、左画像データ内で撮影解像度対応ブロックを探索する探索範囲を限定する。【選択図】図１
2017045124.tif 000002
【特許請求の範囲】
【請求項１】
互いに異なる視点から同一の撮影領域を含むように同時に撮影された第１撮影画像および第２撮影画像を取得する画像取得手段（Ｓ１０）と、
前記画像取得手段により取得された前記第１撮影画像および前記第２撮影画像に対して前記第１撮影画像および前記第２撮影画像の解像度である撮影解像度よりも低くなるように予め設定された低解像度に変換した第１低解像度画像および第２低解像度画像を作成する低解像度画像作成手段（Ｓ３０）と、
前記第１低解像度画像を、複数の画素で構成されたブロックである低解像度ブロックに分割し、分割された複数の前記低解像度ブロック毎に、前記第２低解像度画像内において前記低解像度ブロックと同じ領域が写っている前記ブロックである低解像度対応ブロックを、動的計画法を用いて探索することにより、前記低解像度ブロックの視差を検出する第１視差検出手段（Ｓ２１０〜Ｓ２７０，Ｓ３１０〜Ｓ３７０）と、
前記画像取得手段により取得された前記第１撮影画像を、複数の画素で構成された前記ブロックである撮影解像度ブロックに分割し、分割された複数の前記撮影解像度ブロック毎に、前記第２撮影画像内において前記撮影解像度ブロックと同じ領域が写っている前記ブロックである撮影解像度対応ブロックを、前記第２撮影画像内において前記撮影解像度ブロックとの類似度が高い前記ブロックを探索するブロックマッチング法を用いて決定することにより、前記撮影解像度ブロックの視差を検出する第２視差検出手段（Ｓ６０）とを備え、
前記第２視差検出手段は、前記第１視差検出手段による視差検出結果に基づいて、前記第２撮影画像内において前記ブロックマッチング法を用いて前記ブロックを探索する探索範囲を限定する
ことを特徴とする視差検出装置（４）。
【請求項２】
前記第１視差検出手段は、
複数の前記低解像度ブロック毎に、前記低解像度ブロックの前記第１低解像度画像内における２次元位置と前記低解像度ブロックの視差とにより特定される節点を、前記低解像度ブロックの前記２次元位置と前記低解像度ブロックの視差とで定義される３次元空間である節点空間内に配置するとともに、前記節点に対して、対応する前記低解像度ブロックと、対応する前記節点に設定されている視差分離れている前記第２低解像度画像内の前記ブロックとの類似度が高いほど値が小さくなるように算出される節点コストを設定する節点配置手段（Ｓ２１０，Ｓ３１０）と、
前記節点空間内において１つの前記節点である第１節点から別の前記節点である第２節点へ移動する場合に、前記第１節点の視差と前記第２節点の視差との差が大きいほど値が大きくなるように算出される視差コストを設定し、前記節点空間内に配置された複数の前記節点のそれぞれについて、前記節点を終点として、前記節点空間の一端に位置する前記節点を第１始点として前記第１始点から前記終点へ向って移動する第１移動経路と、前記節点空間の一端とは反対側の他端に位置する前記節点を第２始点として前記第２始点から前記終点へ向って移動する第２移動経路とを設定し、前記第１移動経路上に存在する前記節点の前記節点コストと前記第１移動経路の前記視差コストとの総和を前記第１移動経路の第１移動コストとし、前記第２移動経路上に存在する前記節点の前記節点コストと前記第２移動経路の前記視差コストとの総和を前記第２移動経路の第２移動コストとして、前記第１移動コストが最小となる前記第１移動経路である第１最小移動経路と、前記第２移動コストが最小となる前記第２移動経路である第２最小移動経路とを前記動的計画法を用いて探索し、前記第１最小移動経路の前記第１移動コストと前記第２最小移動経路の前記第２移動コストとに基づいて、前記第１移動経路と前記第２移動経路によって特定される移動方向に沿って前記節点へ移動するときの移動コストを、前記節点の移動方向移動コストとして算出するコスト算出手段（Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０）と、
複数の前記低解像度ブロック毎に、前記低解像度ブロックに対応する複数の前記節点の中から、前記移動方向移動コストが最も小さい前記節点の視差を、前記低解像度ブロックの視差として決定する視差決定手段（Ｓ２６０，Ｓ２７０，Ｓ３６０，Ｓ３７０）とを備える
ことを特徴とする請求項１に記載の視差検出装置。
【請求項３】
前記コスト算出手段は、互いに異なる複数の前記移動方向で、前記移動方向移動コストを算出し、
前記視差決定手段は、前記コスト算出手段で算出された複数の前記移動方向移動コストに基づいて、前記低解像度ブロックの視差を決定する
ことを特徴とする請求項１または請求項２に記載の視差検出装置。
【請求項４】
前記低解像度画像作成手段は、互いに異なる複数の前記低解像度で、前記第１低解像度画像および前記第２低解像度画像を作成し、
前記第１視差検出手段は、複数の前記低解像度のそれぞれについて、前記低解像度の解像度が低い順に前記低解像度ブロックの視差を検出し、前記低解像度の解像度が高くなるにつれて、前記低解像度の解像度が低いときの視差検出結果に基づき前記動的計画法を用いて探索するときの視差の範囲を限定する
ことを特徴とする請求項１〜請求項３の何れか１項に記載の視差検出装置。
【請求項５】
前記第２視差検出手段は、前記撮影解像度対応ブロックを前記ブロックマッチング法を用いて探索する場合に、前記撮影解像度ブロックと前記第２撮影画像内の前記ブロックとの類似度を示す評価値と、前記撮影解像度ブロックと前記第２撮影画像内の前記ブロックとの視差との相対関係に対して、予め設定されたフィッティング関数を用いてフィッティングするサブピクセル推定を行うことにより、前記撮影解像度ブロックの視差を検出する
ことを特徴とする請求項１〜請求項４の何れか１項に記載の視差検出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、互いに異なる視点から撮影された複数の画像を用いて視差を検出する視差検出装置に関する。
【背景技術】
【０００２】
互いに平行に隣接して配置された第１撮影装置と第２撮影装置のそれぞれから第１画像と第２画像を取得し、第１画像と第２画像とを比較することにより、第１画像に写っている物体までの距離を測定する測距装置が知られている。このような測距装置において、データ項と正則化項を含む目的関数が最小となる点を動的計画法を用いて算出することにより視差を検出し、検出した視差に基づいて距離を測定するものが知られている（例えば、特許文献１を参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１５−１１４２６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１に記載の技術では、正則化項を含む目的関数を使用しているために、目的関数が極小値となる点の近傍において目的関数の値が急激に変化し、視差の検出結果が離散的になってしまうおそれがあった。視差の検出結果が離散的になると、視差に基づいて測定される距離の測定結果も離散的になってしまい、距離の測定精度が低下してしまう。
【０００５】
本発明は、こうした問題に鑑みてなされたものであり、処理時間の短縮と視差の検出精度の向上とを両立させることを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するためになされた本発明の視差検出装置は、画像取得手段と、低解像度画像作成手段と、第１視差検出手段と、第２視差検出手段とを備える。
画像取得手段は、互いに異なる視点から同一の撮影領域を含むように同時に撮影された第１撮影画像および第２撮影画像を取得する。
【０００７】
低解像度画像作成手段は、画像取得手段により取得された第１撮影画像および第２撮影画像に対して第１撮影画像および第２撮影画像の解像度である撮影解像度よりも低くなるように予め設定された低解像度に変換した第１低解像度画像および第２低解像度画像を作成する。
【０００８】
第１視差検出手段は、第１低解像度画像を、複数の画素で構成されたブロックである低解像度ブロックに分割する。また第１視差検出手段は、分割された複数の低解像度ブロック毎に、第２低解像度画像内において低解像度ブロックと同じ領域が写っているブロックである低解像度対応ブロックを、動的計画法を用いて探索することにより、低解像度ブロックの視差を検出する。
【０００９】
第２視差検出手段は、画像取得手段により取得された第１撮影画像を、複数の画素で構成されたブロックである撮影解像度ブロックに分割する。また第２視差検出手段は、分割された複数の撮影解像度ブロック毎に、第２撮影画像内において撮影解像度ブロックと同じ領域が写っているブロックである撮影解像度対応ブロックを、ブロックマッチング法を用いて決定することにより、撮影解像度ブロックの視差を検出する。ブロックマッチング法は、第２撮影画像内において撮影解像度ブロックとの類似度が高いブロックを探索する方法である。
【００１０】
また第２視差検出手段は、第１視差検出手段による視差検出結果に基づいて、第２撮影画像内においてブロックマッチング法を用いてブロックを探索する探索範囲を限定する。
このように構成された本発明の視差検出装置は、動的計画法を用いて視差を検出しているが、最終的にはブロックマッチング法を用いて視差を検出する。このため、本発明の視差検出装置は、動的計画法において正則化項を含む目的関数を使用することに起因して視差の検出結果が離散的になるのを回避することができ、視差の検出精度を向上させることができる。さらに、本発明の視差検出装置は、低解像度に変換した第１低解像度画像および第２低解像度画像に対して動的計画法を用いているため、動的計画法を用いて視差を検出するときの処理負荷を低減することができる。また、本発明の視差検出装置は、動的計画法を用いた視差検出結果に基づいて、ブロックマッチング法を用いてブロックを探索する探索範囲を限定するため、ブロックマッチング法を用いて視差を検出するときの処理負荷を低減することができる。以上より、本発明の視差検出装置は、処理時間の短縮と視差の検出精度の向上とを両立させることができる。
【図面の簡単な説明】
【００１１】
【図１】測距装置１の構成を示すブロック図である。
【図２】距離測定処理を示すフローチャートである。
【図３】解像度が互いに異なる複数の画像を示す図である。
【図４】第１視差算出処理を示すフローチャートである。
【図５】節点ＮＰを配置する方法を説明する図である。
【図６】節点空間ＮＰＳの斜視図である。
【図７】Ｘ−Ｚ平面を示す斜視図である。
【図８】Ｙ−Ｚ平面を示す斜視図である。
【図９】右斜め平面を示す斜視図である。
【図１０】左斜め平面を示す斜視図である。
【図１１】第２視差算出処理を示すフローチャートである。
【図１２】ブロックマッチングの実行方法を説明する図である。
【図１３】フィッティング方法を説明する図である。
【図１４】測距装置１の距離測定結果を説明する図である。
【発明を実施するための形態】
【００１２】
以下に本発明の実施形態を図面とともに説明する。
本実施形態の測距装置１は、車両に搭載され、図１に示すように、右撮像装置２と、左撮像装置３と、画像処理装置４とを備える。以下、測距装置１が搭載された車両を自車両という。
【００１３】
右撮像装置２と左撮像装置３は、自車両前方の風景を連続して撮影し、その撮影画像を示す画像データを画像処理装置４へ出力する。右撮像装置２と左撮像装置３はそれぞれ、自車両の進行方向に対して右側と左側に設置される。以下、右撮像装置２の画像データを右画像データ、左撮像装置３の画像データを左画像データという。
【００１４】
右撮像装置２と左撮像装置３は、平行等位に配置される。具体的には、右撮像装置２と左撮像装置３は、右撮像装置２の光軸と左撮像装置３の光軸とが平行になるように配置される。これにより、右撮像装置２の撮像面と左撮像装置３の撮像面が同一平面上に配置される。さらに、右撮像装置２と左撮像装置３は、右撮像装置２の撮像面の横軸と左撮像装置３の撮像面の横軸とが一致するように、水平方向に沿って予め設定された基線長だけ離れて配置される。撮像面の横軸は、撮像面上において撮像面と光軸との交点を原点とした二次元直交座標系のＸ軸およびＹ軸のうちのＸ軸である。
【００１５】
画像処理装置４は、ＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ及びこれらの構成を接続するバスラインなどからなる周知のマイクロコンピュータを中心に構成され、ＲＯＭに記憶されたプログラムに基づいて各種処理を実行する。
【００１６】
このように構成された測距装置１において、画像処理装置４は、距離測定処理を実行する。この距離測定処理は、画像処理装置４の動作中において繰り返し実行される処理である。
【００１７】
この距離測定処理が実行されると、画像処理装置４は、図２に示すように、まずＳ１０にて、右撮像装置２から右画像データを取得するとともに、左撮像装置３から左画像データを取得する。そしてＳ２０にて、Ｓ１０で取得した右画像データが示す右撮影画像と、Ｓ１０で取得した左撮像データが示す左撮影画像との間の垂直方向のずれを補正し、右撮影画像と左撮影画像を互いに平行化する。具体的には、右撮影画像と左撮影画像との間で互いに対応関係にある画像領域（例えば、画素）の高さが一致するように、予め設定された補正パラメータに従って画素全体の垂直方向の座標を変換し、垂直方向のずれを補正する。
【００１８】
次にＳ３０にて、Ｓ２０で平行化された右撮影画像および左撮影画像（図３の画像Ｇ０を参照）を用いて、これらの右撮影画像および左撮影画像の解像度よりも低くなるように予め設定された第１解像度と第２解像度の右撮影画像および左撮影画像を作成する。これにより、第１解像度の右撮影画像および左撮影画像（図３の画像Ｇ１を参照）と、第２解像度の右撮影画像および左撮影画像（図３の画像Ｇ２を参照）が作成される。なお、本実施形態では、第１解像度は、右撮像装置２と左撮像装置３で撮影された画像（以下、原画像ともいう）における横と縦それぞれの解像度を１／４にしたものである。また第２解像度は、原画像における横と縦それぞれの解像度を１／２にしたものである。
【００１９】
そしてＳ４０にて、第１視差算出処理を実行する。ここで、Ｓ４０で実行される第１視差算出処理の手順を説明する。
この第１視差算出処理が実行されると、画像処理装置４は、図４に示すように、まずＳ２１０にて、Ｓ３０で作成された第１解像度の右撮影画像および左撮影画像を用いて、節点空間ＮＰＳ内に節点ＮＰを配置するとともに、節点ＮＰのコストを算出する。
【００２０】
具体的には、図５に示すように、右撮影画像および左撮影画像のそれぞれについて、撮影画像を構成する各画素の位置を、物理座標系で設定する。物理座標は、撮影画像の左上の角を原点として、Ｘ軸の正方向が右向きとなり、Ｙ軸の正方向が下向きとなる座標である。これにより、撮影画像を構成する各画素の位置が、ピクセル単位で設定される。以下、Ｘ軸方向の位置をＸ座標位置、Ｙ軸方向の位置をＹ座標位置という。また、右撮影画像および左撮影画像をそれぞれ、基準画像および比較画像ともいう。
【００２１】
そして、第１解像度の基準画像を、Ｘ軸方向にｐ画素（ｐは正の整数）でＹ軸方向にｑ画素（ｑは正の整数）の矩形状のブロックＢＬに分割する。
次に、分割された複数のブロックＢＬのそれぞれについて、比較画像の中からＹ座標位置が同じ領域を探索領域として設定する（領域ＳＲを参照）。この探索領域において、ブロックＢＬとの視差が互いに異なり、且つ、ブロックＢＬと同じ大きさ（すなわち、Ｘ軸方向にｐ画素でＹ軸方向にｑ画素の矩形）の複数のブロックを節点設定用ブロックＢＬｎとして抽出する。そして、抽出された複数の節点設定用ブロックＢＬｎに基づいて、節点空間ＮＰＳ内に節点ＮＰを配置する。節点空間ＮＰＳは、図６に示すように、ブロックＢＬのＸ座標位置をＸ軸とし、ブロックＢＬのＹ座標位置をＹ軸とし、ブロックＢＬに対応する節点設定用ブロックＢＬｎの視差をＺ軸とした３次元直交座標空間である。
【００２２】
例えば、図５に示すように、基準画像内のブロックＢＢ１について、探索領域ＳＲ内でＸ座標位置が同じブロックＢＣ１（１）を節点設定用ブロックＢＬｎとして抽出するとする（矢印ＡＬ１を参照）。この場合に、ブロックＢＢ１のＸ座標位置をｘ１、ブロックＢＢ１のＹ座標位置をｙ１、ブロックＢＢ１とブロックＢＣ１（１）との視差をｄ１と表記すると、ブロックＢＣ１（１）に対応する節点ＮＰ１（１）は節点空間ＮＰＳ内の（ｘ１，ｙ１，ｄ１）に配置される（矢印ＡＬ２を参照）。なお、図５に示す節点空間ＮＰＳは、Ｙ座標がｙ１であるＸ−Ｚ平面である。
【００２３】
また、基準画像内のブロックＢＢ１について、探索領域ＳＲ内でＸ座標位置が異なるブロックＢＣ１（２）を節点設定用ブロックＢＬｎとして抽出するとする（矢印ＡＬ３を参照）。この場合に、ブロックＢＢ１とブロックＢＣ１（２）との視差をｄ２と表記すると、ブロックＢＣ１（２）に対応する節点ＮＰ１（２）は節点空間ＮＰＳ内の（ｘ１，ｙ１，ｄ２）に配置される（矢印ＡＬ４を参照）。
【００２４】
また、基準画像内のブロックＢＢ１に隣接するブロックＢＢ２についても、ブロックＢＢ１と同じ探索領域ＳＲ内で節点設定用ブロックＢＬｎを抽出する。
例えば、基準画像内のブロックＢＢ２について、探索領域ＳＲ内でＸ座標位置が同じブロックＢＣ２（１）を節点設定用ブロックＢＬｎとして抽出するとする（矢印ＡＬ５を参照）。この場合に、ブロックＢＢ２のＸ座標位置をｘ２、ブロックＢＬのＹ座標位置をｙ１、ブロックＢＢ２とブロックＢＣ２（１）との視差をｄ１と表記すると、ブロックＢＣ２（１）に対応する節点ＮＰ２（１）は節点空間ＮＰＳ内の（ｘ２，ｙ１，ｄ１）に配置される（矢印ＡＬ６を参照）。
【００２５】
また、節点空間ＮＰＳ内に配置された複数の節点ＮＰのそれぞれについて、コストを算出する。コストは、節点ＮＰを節点空間ＮＰＳ内に配置する際に用いられた２つのブロック間の類似度を表す値である。上記２つのブロックは、基準画像内のブロックＢＬと、このブロックＢＬに対応して節点ＮＰを配置するために比較画像から抽出された節点設定用ブロックＢＬｎである。例えば、節点ＮＰ１（１）のコストは、ブロックＢＢ１と、ブロックＢＣ１（１）とを用いて算出される。
【００２６】
節点空間ＮＰＳ内における節点ＮＰのＸ座標位置とＹ座標位置をまとめて節点位置ｐと表記し、節点ＮＰの視差をｕｐと表記する。さらに、節点空間ＮＰＳ内において節点位置ｐと視差ｕｐで特定される位置に配置される節点ＮＰのコストをＤ（ｐ，ｕｐ）と表記する。
【００２７】
本実施形態では、周知のＳＳＩＭ（Structural Similarity）を用いて、コストＤ（ｐ，ｕｐ）を下式（１）で算出する。
【００２８】
【数１】
2017045124.tif 000003
なお、上式（１）において、μｘは、基準画像内のブロックＢＬに含まれる画素の輝度の平均値である。μｙは、比較画像内の節点設定用ブロックＢＬｎに含まれる画素の輝度の平均値である。σｘは、基準画像内のブロックＢＬに含まれる画素の輝度の標準偏差である。σｙは、比較画像内の節点設定用ブロックＢＬｎに含まれる画素の輝度の標準偏差である。σｘｙは、基準画像内のブロックＢＬと比較画像内の節点設定用ブロックＢＬｎに含まれる画素の輝度の共分散である。ｃ１，ｃ２，ｃ３，α，β，γは予め設定される定数である。
【００２９】
このようにして、分割されたブロックＢＬの全てについて節点ＮＰを節点空間ＮＰＳ内に配置するとともに、配置された節点ＮＰの全てについてコストＤ（ｐ，ｕｐ）を算出すると、Ｓ２１０の処理を終了する。
【００３０】
Ｓ２１０の処理が終了すると、図４に示すように、Ｓ２２０にて、節点ＮＰのＸ方向移動コストＥｘ（後述）を算出する。ブロックＢＬはＹ軸方向に沿ってｑ画素毎に分割されている（図５を参照）。このため、図７に示すように、節点空間ＮＰＳ内には、複数の節点ＮＰが配置されたＸ−Ｚ平面がＹ軸方向に沿ってｑ画素毎に存在する（図７の平面ＰＬ１，ＰＬ２，ＰＬ３を参照）。
【００３１】
これら複数のＸ−Ｚ平面のそれぞれについて、節点ＮＰのＸ方向移動コストＥｘを算出する。以下に、節点ＮＰのＸ方向移動コストＥｘの算出方法を説明する。
例えば、図５に示すように、Ｘ−Ｚ平面において、複数の節点ＮＰが２次元行列状に配列されているとする。また、以下の説明のために、Ｚ軸方向を列方向とし、Ｘ軸方向を行方向として、第ｉ行（ｉは正の整数）の第ｊ列（ｊは正の整数）に位置する節点ＮＰをＮＰ（ｉ，ｊ）と表記する。なお、視差が小さいほどｉは小さくなり、Ｘ座標位置が原点から近いほどｊは小さくなる。
【００３２】
まず、Ｘ−Ｚ平面に配列されている複数の節点ＮＰの中から１つの節点ＮＰを終点として選択する。Ｘ座標位置が原点から最も近い複数の節点ＮＰ（すなわち、第ｉ行の第１列に位置する節点ＮＰ）のうちの１つを始点とする。そして、始点から、Ｘ軸の正方向に向かって、隣の列（すなわち、第２列）に位置する複数の節点ＮＰのうちの１つへ移動させる（図５と図７の移動方向Ｍ１を参照）。さらに、移動した節点ＮＰから更に隣の列（すなわち、第３列）に位置する複数の節点ＮＰのうちの１つへ移動させる。このように、始点の節点ＮＰから、Ｘ軸の正方向に向かって１列ずつ節点ＮＰへ順次移動させ、終点として選択された節点ＮＰまで移動させた１つの移動経路を確定する。以下、この移動経路を右方向移動経路という。図５では、左からＮＰ（４，１）、ＮＰ（３，２）、ＮＰ（３，３）、ＮＰ（３，４）の順に右方向へ移動する右方向移動経路を示している。
【００３３】
そして、確定した移動経路のコストＥを、下式（２）で算出する。
【００３４】
【数２】
2017045124.tif 000004
上式（２）の右辺の第１項は、移動経路上に存在する節点ＮＰのコストＤ（ｐ，ｕｐ）の総和を示す。上式（２）の右辺の第１項は、データ項という。上式（２）の右辺の第２項は、正則化項である。上式（２）の右辺の第２項のＳ（ｕｐ，ｕｑ）は、視差がｕｐである節点ＮＰから、視差がｕｑである節点ＮＰへ移動する場合の視差コストである。Ｓ（ｕｐ，ｕｑ）は、視差ｕｐと視差ｕｑとの差が大きくほど値が大きくなるように設定された関数である。本実施形態では、Ｓ（ｕｐ，ｕｑ）は、視差ｕｐと視差ｕｑとの差分の絶対値である。したがって、上式（２）の右辺の第２項は、移動経路を通過することによる視差の変化の総和を示す。
【００３５】
このようにして、第１列に位置する複数の節点ＮＰの何れか１点を始点とし、複数の節点ＮＰの中から選択された１つの節点ＮＰを終点とした場合において可能な全ての移動経路を確定することができ、確定した全ての移動経路についてコストＥを算出することができる。これにより、コストＥが最小となる移動経路を特定することができる。
【００３６】
本実施形態では、上記のように全ての移動経路でコストＥを算出する代わりに、動的計画法の一種である周知のビタビアルゴリズムを用いて、コストＥが最小となる移動経路を特定する演算を行う。
【００３７】
Ｓ２２０では、コストＥが最小となる右方向移動経路の特定を、１つのＸ−Ｚ平面に配列されている全ての節点ＮＰについて行う。これにより、このＸ−Ｚ平面に配列されている全ての節点ＮＰのそれぞれについて、右方向移動経路の最小コスト（以下、右方向移動コストという）が算出される。
【００３８】
次に、右方向移動コストの算出と同様にして、このＸ−Ｚ平面に配列されている全ての節点ＮＰのそれぞれについて、左方向移動経路の最小コスト（以下、左方向移動コストという）を算出する。
【００３９】
具体的には、Ｘ−Ｚ平面に配列されている複数の節点ＮＰの中から１つの節点ＮＰを終点として選択する。Ｘ座標位置が原点から最も遠い複数の節点ＮＰ（すなわち、第ｉ行の最終列に位置する節点ＮＰ）のうちの１つを始点とする。そして、始点から、Ｘ軸の負方向に向かって、隣の列に位置する複数の節点ＮＰのうちの１つへ移動させる（図５と図７の移動方向Ｍ２を参照）。さらに、移動した節点ＮＰから更に隣の列に位置する複数の節点ＮＰのうちの１つへ移動させる。このように、始点の節点ＮＰから、Ｘ軸の負方向に向かって１列ずつ節点ＮＰへ順次移動させ、終点として選択された節点ＮＰまで移動させた１つの移動経路を確定する。以下、この移動経路を左方向移動経路という。
【００４０】
Ｓ２２０では、右方向移動経路の場合と同様にして、コストＥが最小となる左方向移動経路の特定を、１つのＸ−Ｚ平面に配列されている全ての節点ＮＰについて行う。これにより、このＸ−Ｚ平面に配列されている全ての節点ＮＰのそれぞれについて、左方向移動経路の最小コスト（以下、左方向移動コストという）が算出される。
【００４１】
そして、Ｓ２２０では、このＸ−Ｚ平面に配列されている全ての節点ＮＰのそれぞれについて、右方向移動コストと左方向移動コストとを加算した加算値を、Ｘ方向移動コストＥｘとして算出する。
【００４２】
このＸ−Ｚ平面でＸ方向移動コストＥｘの算出が終了すると、次のＸ−Ｚ平面について、同様にして、Ｘ方向移動コストＥｘの算出を行う。そして、全てのＸ−Ｚ平面についてＸ方向移動コストＥｘの算出を行うと、Ｓ２２０の処理を終了する。
【００４３】
Ｓ２２０の処理が終了すると、図４に示すように、Ｓ２３０にて、節点ＮＰのＹ方向移動コストＥｙ（後述）を算出する。ブロックＢＬはＸ軸方向に沿ってｐ画素毎に分割されている（図５を参照）。このため、図８に示すように、節点空間ＮＰＳ内には、複数の節点ＮＰが配置されたＹ−Ｚ平面がＸ軸方向に沿ってｐ画素毎に存在する（図８の平面ＰＬ１１，ＰＬ１２，ＰＬ１３，ＰＬ１４を参照）。
【００４４】
Ｓ２３０では、これら複数のＹ−Ｚ平面のそれぞれについて、節点ＮＰのＹ方向移動コストＥｙを算出する。節点ＮＰのＹ方向移動コストＥｙの算出は、Ｘ−Ｚ平面の代わりにＹ−Ｚ平面を用いている点が、上述したＸ方向移動コストＥｘの算出と異なる。
【００４５】
具体的には、Ｙ−Ｚ平面において、Ｙ座標位置が原点から最も近い複数の節点ＮＰのうちの１つを始点して、Ｙ軸の正方向に向かって、１列ずつ節点ＮＰへ順次移動させ（図８の移動方向Ｍ３を参照）、終点として選択された節点ＮＰまで移動させた移動経路を下方向移動経路とする。また、Ｙ−Ｚ平面において、Ｙ座標位置が原点から最も遠い複数の節点ＮＰのうちの１つを始点して、Ｙ軸の負方向に向かって、１列ずつ節点ＮＰへ順次移動させ（図８の移動方向Ｍ４を参照）、終点として選択された節点ＮＰまで移動させた移動経路を上方向移動経路とする。
【００４６】
Ｓ２３０では、コストＥが最小となる下方向移動経路と上方向移動経路の特定を、１つのＹ−Ｚ平面に配列されている全ての節点ＮＰについて行う。これにより、このＹ−Ｚ平面に配列されている全ての節点ＮＰのそれぞれについて、下方向移動経路の最小コスト（以下、下方向移動コストという）と、上方向移動経路の最小コスト（以下、上方向移動コストという）が算出される。
【００４７】
そして、Ｓ２３０では、このＹ−Ｚ平面に配列されている全ての節点ＮＰのそれぞれについて、下方向移動コストと上方向移動コストとを加算した加算値を、Ｙ方向移動コストＥｙとして算出する。
【００４８】
このＹ−Ｚ平面でＹ方向移動コストＥｙの算出が終了すると、次のＹ−Ｚ平面について、同様にして、Ｙ方向移動コストＥｙの算出を行う。そして、全てのＹ−Ｚ平面についてＹ方向移動コストＥｙの算出を行うと、Ｓ２３０の処理を終了する。
【００４９】
Ｓ２３０の処理が終了すると、図４に示すように、Ｓ２４０にて、節点ＮＰの右斜め方向移動コストＥｘ−ｙ（後述）を算出する。
Ｓ２４０では、まず、図９に示すように、節点空間ＮＰＳ内において、Ｘ軸とＹ軸との間に跨ってＸ−Ｙ平面と垂直になるように形成された複数の平面（以下、右斜め平面という）を設定する（図９の平面ＰＬ２１，ＰＬ２２，ＰＬ２３を参照）。これら複数の右斜め平面は、互いに平行となるように、且つ、その平面の全面に亘って節点ＮＰが配置されるように設定されている。
【００５０】
Ｓ２４０では、これら複数の右斜め平面のそれぞれについて、節点ＮＰの右斜め方向移動コストＥｘ−ｙを算出する。節点ＮＰの右斜め方向移動コストＥｘ−ｙの算出は、Ｘ−Ｚ平面の代わりに右斜め平面を用いている点が、上述したＸ方向移動コストＥｘの算出と異なる。
【００５１】
具体的には、右斜め平面において、Ｙ軸から最も近い複数の節点ＮＰのうちの１つを始点して、Ｘ軸に向かって、１列ずつ節点ＮＰへ順次移動させ（図９の移動方向Ｍ５を参照）、終点として選択された節点ＮＰまで移動させた移動経路を右上方向移動経路とする。また、右斜め平面において、Ｘ軸からから最も遠い複数の節点ＮＰのうちの１つを始点して、Ｙ軸に向かって、１列ずつ節点ＮＰへ順次移動させ（図９の移動方向Ｍ６を参照）、終点として選択された節点ＮＰまで移動させた移動経路を左下方向移動経路とする。
【００５２】
Ｓ２４０では、コストＥが最小となる右上方向移動経路と左下方向移動経路の特定を、１つの右斜め平面に配列されている全ての節点ＮＰについて行う。これにより、この右斜め平面に配列されている全ての節点ＮＰのそれぞれについて、右上方向移動経路の最小コスト（以下、右上方向移動コストという）と、左下方向移動経路の最小コスト（以下、左下方向移動コストという）が算出される。
【００５３】
そして、Ｓ２４０では、この右斜め平面に配列されている全ての節点ＮＰのそれぞれについて、右上方向移動コストと左下方向移動コストとを加算した加算値を、右斜め方向移動コストＥｘ−ｙとして算出する。
【００５４】
この右斜め平面で右斜め方向移動コストＥｘ−ｙとの算出が終了すると、次の右斜め平面について、同様にして、右斜め方向移動コストＥｘ−ｙの算出を行う。そして、全ての右斜め平面について右斜め方向移動コストＥｘ−ｙの算出を行うと、Ｓ２４０の処理を終了する。
【００５５】
Ｓ２４０の処理が終了すると、図４に示すように、Ｓ２５０にて、節点ＮＰの左斜め方向移動コストＥｘ＋ｙ（後述）を算出する。
Ｓ２５０では、まず、図１０に示すように、節点空間ＮＰＳ内において、右斜め平面と交差するように形成された複数の平面（以下、左斜め平面という）を設定する。（図１０の平面ＰＬ３１，ＰＬ３２，ＰＬ３３，ＰＬ３４を参照）。これら複数の左斜め平面は、互いに平行となるように、且つ、その平面の全面に亘って節点ＮＰが配置されるように設定されている。
【００５６】
Ｓ２５０では、これら複数の左斜め平面のそれぞれについて、節点ＮＰの左斜め方向移動コストＥｘ＋ｙを算出する。節点ＮＰの左斜め方向移動コストＥｘ＋ｙの算出は、Ｘ−Ｚ平面の代わりに左斜め平面を用いている点が、上述したＸ方向移動コストＥｘの算出と異なる。
【００５７】
具体的には、左斜め平面において、原点から最も近い複数の節点ＮＰのうちの１つを始点して、原点から離れる方向に向かって、１列ずつ節点ＮＰへ順次移動させ（図１０の移動方向Ｍ７を参照）、終点として選択された節点ＮＰまで移動させた移動経路を右下方向移動経路とする。また、左斜め平面において、原点から最も遠い複数の節点ＮＰのうちの１つを始点して、原点へ近付く方向に向かって、１列ずつ節点ＮＰへ順次移動させ（図１０の移動方向Ｍ８を参照）、終点として選択された節点ＮＰまで移動させた移動経路を左上方向移動経路とする。
【００５８】
Ｓ２５０では、コストＥが最小となる右下方向移動経路と左上方向移動経路の特定を、１つの左斜め平面に配列されている全ての節点ＮＰについて行う。これにより、この左斜め平面に配列されている全ての節点ＮＰのそれぞれについて、右下方向移動経路の最小コスト（以下、右下方向移動コストという）と、左上方向移動経路の最小コスト（以下、左上方向移動コストという）が算出される。
【００５９】
そして、Ｓ２５０では、この左斜め平面に配列されている全ての節点ＮＰのそれぞれについて、右下方向移動コストと左上方向移動コストとを加算した加算値を、左斜め方向移動コストＥｘ＋ｙとして算出する。
【００６０】
この左斜め平面で左斜め方向移動コストＥｘ＋ｙとの算出が終了すると、次の左斜め平面について、同様にして、左斜め方向移動コストＥｘ＋ｙの算出を行う。そして、全ての左斜め平面について左斜め方向移動コストＥｘ＋ｙの算出を行うと、Ｓ２５０の処理を終了する。
【００６１】
Ｓ２５０の処理が終了すると、図４に示すように、Ｓ２６０にて、節点空間ＮＰＳ内の全ての節点ＮＰについて、総方向移動コストＥｓｕｍを、下式（３）で算出する。
【００６２】
【数３】
2017045124.tif 000005
そしてＳ２７０にて、基準画像を構成する全てのブロックＢＬのそれぞれについて、ブロックＢＬと同じＸ座標位置とＹ座標位置を有して視差が互いに異なる複数の節点ＮＰの中から、総方向移動コストＥｓｕｍが最小となる節点ＮＰを選択し、第１視差算出処理を終了する。
【００６３】
第１視差算出処理が終了すると、図２に示すように、Ｓ５０にて、第２視差算出処理を行う。ここで、Ｓ５０で実行される第２視差算出処理の手順を説明する。
この第２視差算出処理が実行されると、画像処理装置４は、図１１に示すように、まずＳ３１０にて、Ｓ３０で作成された第２解像度の右撮影画像および左撮影画像を用いて、節点空間ＮＰＳ内に節点ＮＰを配置するとともに、節点ＮＰのコストを算出する。節点ＮＰを配置する方法と、節点ＮＰのコストを算出する方法は、Ｓ２１０と同じであるため、説明を省略する。
【００６４】
Ｓ３１０の処理が終了すると、Ｓ３２０にて、節点ＮＰのＸ方向移動コストＥｘを算出する。Ｓ３２０では、節点空間ＮＰＳ内の全ての節点ＮＰではなく、Ｓ２７０で選択された節点ＮＰの付近に位置する節点ＮＰに限定して、Ｘ方向移動コストＥｘを算出する。Ｘ方向移動コストＥｘを算出する方法は、Ｓ２２０と同じであるため、説明を省略する。
【００６５】
Ｓ３２０の処理が終了すると、Ｓ３３０にて、節点ＮＰのＹ方向移動コストＥｙを算出する。Ｓ３３０では、節点空間ＮＰＳ内の全ての節点ＮＰではなく、Ｓ２７０で選択された節点ＮＰの付近に位置する節点ＮＰに限定して、Ｙ方向移動コストＥｙを算出する。Ｙ方向移動コストＥｙを算出する方法は、Ｓ２３０と同じであるため、説明を省略する。
【００６６】
Ｓ３３０の処理が終了すると、Ｓ３４０にて、節点ＮＰの右斜め方向移動コストＥｘ−ｙを算出する。Ｓ３４０では、節点空間ＮＰＳ内の全ての節点ＮＰではなく、Ｓ２７０で選択された節点ＮＰの付近に位置する節点ＮＰに限定して、右斜め方向移動コストＥｘ−ｙを算出する。右斜め方向移動コストＥｘ−ｙを算出する方法は、Ｓ２４０と同じであるため、説明を省略する。
【００６７】
Ｓ３４０の処理が終了すると、Ｓ３５０にて、節点ＮＰの左斜め方向移動コストＥｘ＋ｙを算出する。Ｓ３５０では、節点空間ＮＰＳ内の全ての節点ＮＰではなく、Ｓ２７０で選択された節点ＮＰの付近に位置する節点ＮＰに限定して、左斜め方向移動コストＥｘ＋ｙを算出する。左斜め方向移動コストＥｘ＋ｙを算出する方法は、Ｓ２５０と同じであるため、説明を省略する。
【００６８】
Ｓ３５０の処理が終了すると、Ｓ３６０にて、Ｓ２６０と同様にして、総方向移動コストＥｓｕｍを算出する。
そしてＳ３７０にて、Ｓ２７０と同様にして、基準画像を構成する全てのブロックＢＬのそれぞれについて、総方向移動コストＥｓｕｍが最小となる節点ＮＰを選択する。
【００６９】
さらにＳ３８０にて、Ｓ３７０で選択された節点ＮＰの視差を、対応するブロックＢＬの視差として決定する。Ｓ３８０にて、基準画像を構成する全てのブロックＢＬについて視差を決定すると、第２視差算出処理を終了する。
【００７０】
第２視差算出処理が終了すると、図２に示すように、Ｓ６０にて、Ｓ２０で平行化された右撮影画像および左撮影画像（すなわち、原画像）を用いて、ブロックマッチングを実行する。
【００７１】
Ｓ６０では、まず、Ｓ２０で平行化された右撮影画像および左撮影画像をそれぞれ基準画像および比較画像とし、基準画像を、Ｘ軸方向に（２ｍ＋１）画素（ｍは正の整数）でＹ軸方向に（２ｎ＋１）画素（ｎは正の整数）の矩形状のブロックＢＬｍに分割する。
【００７２】
Ｓ６０では、分割された複数のブロックＢＬｍのそれぞれについて、対応点探索の範囲を決定する。例えば、図１２に示すように、基準画像内の１つのブロックＢＬｍの座標を（ｘｍ，ｙｍ）とする。なお、ブロックＢＬｍの座標とは、ブロックＢＬｍの中心に位置する画素の位置に対応している。
【００７３】
そして、Ｓ３８０での結果に基づいて、ブロックＢＬｍの視差を決定する。具体的には、第２解像度の右撮影画像において、ブロックＢＬｍの座標（ｘｍ，ｙｍ）を含んでいるブロックＢＬを特定し、このブロックＢＬについて決定された視差を、ブロックＢＬｍの視差とする。
【００７４】
次に、基準画像内のブロックＢＬｍの座標と視差に基づいて、比較画像内の探索領域ＳＲｃを設定する。ブロックＢＬｍの視差をｄｓ［ピクセル］と表記すると、例えば、探索領域ＳＲｃのＸ方向長さを予め（２Ｌ＋１）［ピクセル］と設定している場合には、探索領域ＳＲｃのＸ方向範囲は、（ｘｍ＋ｄｓ−２Ｌ）〜（ｘｍ＋ｄｓ＋２Ｌ）である。また、探索領域ＳＲｃのＹ方向範囲は、（ｙｍ−２ｎ）〜（ｙｍ＋２ｎ）である。
【００７５】
そして、この探索領域ＳＲｃ内で、ブロックＢＬｍと同じ大きさ（すなわち、Ｘ軸方向にｍ画素でＹ軸方向にｎ画素の矩形）の探索ブロックＢＬｓを移動させる。探索領域ＳＲｃ内において探索ブロックＢＬｓを複数箇所移動させ、移動させた各箇所の探索ブロックＢＬｓの中に含まれる画素と、基準画像内のブロックＢＬｍ内に含まれる画素とを用いて、周知のＳＡＤ（Sum of Absolute Difference）を実行する。ブロックＢＬｍが座標（ｘｍ，ｙｍ）に位置し、探索ブロックＢＬｓのＸ座標位置がｘｓである場合に、ＳＡＤにより算出される評価値をＭ（ｘｍ，ｙｍ，ｘｓ）と表記すると、評価値Ｍ（ｘｍ，ｙｍ，ｘｓ）は、下式（４）で算出される。下式（４）のＩｍは、ブロックＢＬｍ内に含まれる各画素の輝度を示す。下式（４）のＩｓは、探索ブロックＢＬｓ内に含まれる各画素の輝度を示す。
【００７６】
【数４】
2017045124.tif 000006
そして、図１３に示すように、横軸をｘｓ（探索ブロックＢＬｓのＸ座標位置）とし、縦軸を評価値Ｍ（ｘｍ，ｙｍ，ｘｓ）として、算出された複数の評価値Ｍ（ｘｍ，ｙｍ，ｘｓ）をプロットしたグラフを作成する（プロット点ＰＴ１，ＰＴ２，ＰＴ３，ＰＴ４，ＰＴ５を参照）。そして、プロット点に対して、例えば２次関数等のフィッティング関数を用いてフィッティングを行い、フィッティングにより得られたフィッティング曲線（曲線ＦＬを参照）において極小値となるＸ座標位置ｘｆを算出する。このＸ座標位置ｘｆと、ブロックＢＬｍのＸ座標位置ｘｍとの差が、ブロックＢＬｍの視差である。
【００７７】
１つのブロックＢＬｍで視差の算出が終了すると、次のブロックＢＬｍについて、同様にして、視差の算出を行う。そして、全てのブロックＢＬｍについて視差の算出を行うと、Ｓ６０の処理を終了する。
【００７８】
Ｓ６０の処理が終了すると、図２に示すように、Ｓ７０にて、基準画像を構成する全てのブロックＢＬｍについて、Ｓ６０で算出された視差に基づき、視差を用いた周知の距離算出式を用いて距離を算出し、距離測定処理を終了する。これにより、基準画像を構成するブロックＢＬｍ毎に、ブロックＢＬｍ内に写っている物体までの距離が特定される。
【００７９】
図１４に、本実施形態の測距装置１による距離測定結果と、Ｓ６０においてブロックマッチングの代わりにＳ４０とＳ５０と同様に総方向移動コストＥｓｕｍを算出することで得られた距離測定結果（以下、比較用測定結果という）とを示す。
【００８０】
測距装置１による距離測定結果は、第１解像度の画像と、第２解像度の画像とで動的計画法を適用し、原画像でブロックマッチングを適用した測定結果である。
比較用測定結果は、第１解像度の画像と、第２解像度の画像と、原画像とで動的計画法を適用した測定結果である。
【００８１】
図１４に示す画像Ｇ１１は、右撮像装置２で撮影された画像である。画像Ｇ１２は、測距装置１が画像Ｇ１１を用いて距離を測定した結果を示す。画像Ｇ１３は、画像Ｇ１２の一部を拡大した図である。画像Ｇ１４は、画像Ｇ１１を用いた比較用測定結果を示す。画像Ｇ１５は、画像Ｇ１４の一部を拡大した図である。
【００８２】
図１４の画像Ｇ１３と画像Ｇ１５とを比較すると明らかなように、画像Ｇ１１において連続的に距離が変化している箇所（画像Ｇ１３の矢印Ｌｃ１と画像Ｇ１５の矢印Ｌｃ２を参照）において、画像Ｇ１３が示す距離測定結果は濃淡が連続的に変化しているのに対して、画像Ｇ１５が示す距離測定結果は濃淡が離散的に変化している。
【００８３】
このように構成された測距装置１は、互いに異なる視点から同一の撮影領域を含むように同時に撮影された右画像データおよび左画像データを取得する（Ｓ１０）。また測距装置１は、取得された右画像データおよび左画像データに対して右画像データおよび左画像データの解像度よりも低くなるように予め設定された第１解像度と第２解像度の右画像データ（以下、右低解像度データという）および左画像データ（以下、左低解像度データという）を作成する（Ｓ３０）。
【００８４】
また測距装置１は、右低解像度データを、複数の画素で構成されたブロックＢＬに分割する。また測距装置１は、分割された複数のブロックＢＬ毎に、左低解像度データ内においてブロックＢＬと同じ領域が写っている節点設定用ブロックＢＬｎを、動的計画法を用いて探索することにより、ブロックＢＬの視差を検出する（Ｓ２１０〜Ｓ２７０，Ｓ３１０〜Ｓ３７０）。
【００８５】
そして測距装置１は、取得された右画像データを、複数の画素で構成されたブロックＢＬｍに分割する。また測距装置１は、分割された複数のブロックＢＬｍ毎に、左画像データ内においてブロックＢＬｍと同じ領域が写っているブロック（以下、撮影解像度対応ブロックという）を、ブロックマッチング法を用いて決定することにより、ブロックＢＬｍの視差を検出する（Ｓ６０）。また測距装置１は、動的計画法による視差検出結果（Ｓ４０，Ｓ５０）に基づいて、左画像データ内においてブロックマッチング法を用いて撮影解像度対応ブロックを探索する探索範囲を限定する（Ｓ６０）。
【００８６】
このように測距装置１は、動的計画法を用いて視差を検出しているが、最終的にはブロックマッチング法を用いて視差を検出する。このため、測距装置１は、動的計画法において正則化項を含む目的関数を使用することに起因して視差の検出結果が離散的になるのを回避することができ、視差の検出精度を向上させることができる。さらに測距装置１は、低解像度に変換した右低解像度データおよび左低解像度データに対して動的計画法を用いているため、動的計画法を用いて視差を検出するときの処理負荷を低減することができる。また測距装置１は、動的計画法を用いた視差検出結果に基づいて、ブロックマッチング法を用いてブロックを探索する探索範囲を限定するため、ブロックマッチング法を用いて視差を検出するときの処理負荷を低減することができる。以上より、測距装置１は、処理時間の短縮と視差の検出精度の向上とを両立させることができる。
【００８７】
また測距装置１は、複数のブロックＢＬ毎に、ブロックＢＬの右低解像度データ内における２次元位置とブロックＢＬの視差とにより特定される節点ＮＰを、ブロックＢＬの２次元位置とブロックＢＬの視差とで定義される３次元空間である節点空間ＮＰＳ内に配置する（Ｓ２１０，Ｓ３１０）。また測距装置１は、節点ＮＰに対して、対応するブロックＢＬと、対応する節点ＮＰに設定されている視差分離れている左低解像度データ内の節点設定用ブロックＢＬｎとの類似度が高いほど値が小さくなるように算出されるコストＤ（ｐ，ｕｐ）を設定する（Ｓ２１０，Ｓ３１０）。
【００８８】
また測距装置１は、節点空間ＮＰＳ内において１つの節点ＮＰである第１節点から別の節点ＮＰである第２節点へ移動する場合に、第１節点の視差と第２節点の視差との差が大きいほど値が大きくなるように算出される視差コストＳ（ｕｐ，ｕｑ）を設定する（Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０）。
【００８９】
また測距装置１は、節点空間ＮＰＳ内に配置された複数の節点ＮＰのそれぞれについて、節点ＮＰを終点として、節点空間ＮＰＳの一端に位置する節点ＮＰを第１始点として第１始点から終点へ向って移動する右方向移動経路、下方向移動経路、右上方向移動経路および右下方向移動経路を設定する（Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０）。以下、右方向移動経路、下方向移動経路、右上方向移動経路および右下方向移動経路をまとめて第１移動経路という。また測距装置１は、節点空間ＮＰＳの一端とは反対側の他端に位置する節点ＮＰを第２始点として第２始点から終点へ向って移動する左方向移動経路、上方向移動経路、左下方向移動経路および左上方向移動経路を設定する（Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０）。以下、左方向移動経路、上方向移動経路、左下方向移動経路および左上方向移動経路をまとめて第２移動経路という。
【００９０】
また測距装置１は、第１移動経路上に存在する節点ＮＰのコストＤ（ｐ，ｕｐ）と第１移動経路の視差コストＳ（ｕｐ，ｕｑ）との総和を、右方向移動コスト、下方向移動コスト、右上方向移動コストおよび右下方向移動コストとする（Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０）。以下、右方向移動コスト、下方向移動コスト、右上方向移動コストおよび右下方向移動コストをまとめて第１移動コストという。
【００９１】
また測距装置１は、第２移動経路上に存在する節点ＮＰのコストＤ（ｐ，ｕｐ）と第２移動経路の視差コストＳ（ｕｐ，ｕｑ）との総和を、左方向移動コスト、上方向移動コスト、左下方向移動コストおよび左上方向移動コストとする（Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０）。以下、左方向移動コスト、上方向移動コスト、左下方向移動コストおよび左上方向移動コストをまとめて第２移動コストという。
【００９２】
そして測距装置１は、第１移動コストが最小となる第１移動経路（以下、第１最小移動経路という）と、第２移動コストが最小となる第２移動経路（以下、第２最小移動経路という）とを動的計画法を用いて探索する（Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０）。
【００９３】
さらに測距装置１は、第１最小移動経路の第１移動コストと第２最小移動経路の第２移動コストとに基づいて、節点ＮＰのＸ方向移動コストＥｘ、Ｙ方向移動コストＥｙ、右斜め方向移動コストＥｘ−ｙおよび左斜め方向移動コストＥｘ＋ｙを算出する（Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０）。
【００９４】
そして測距装置１は、複数のブロックＢＬ毎に、ブロックＢＬに対応する複数の節点ＮＰの中から、総方向移動コストＥｓｕｍが最も小さい節点ＮＰの視差を、ブロックＢＬの視差として決定する（Ｓ２６０，Ｓ２７０，Ｓ３６０，Ｓ３７０）。
【００９５】
このように測距装置１は、正則化項である視差コストＳ（ｕｐ，ｕｑ）を含む移動コストを目的関数として使用する動的計画法を用いて、視差を検出する。これに対して、測距装置１は、最終的にはブロックマッチング法を用いて視差を検出する。このため、測距装置１は、視差の検出結果が離散的になるのを回避することができ、視差の検出精度を向上させることができる。
【００９６】
また測距装置１は、互いに異なるＸ方向、Ｙ方向、右斜め方向および左斜め方向で、Ｘ方向移動コストＥｘ、Ｙ方向移動コストＥｙ、右斜め方向移動コストＥｘ−ｙおよび左斜め方向移動コストＥｘ＋ｙを算出する（Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０）。そして測距装置１は、算出されたＸ方向移動コストＥｘ、Ｙ方向移動コストＥｙ、右斜め方向移動コストＥｘ−ｙおよび左斜め方向移動コストＥｘ＋ｙに基づいて、ブロックＢＬの視差を決定する（Ｓ２６０，Ｓ２７０，Ｓ３６０，Ｓ３７０）。
【００９７】
このように、測距装置１は、複数の移動方向で算出された移動コストに基づいて視差を決定するため、右画像データおよび左画像データに含まれるノイズが視差検出結果に与える影響を低減し、視差の検出精度を向上させることができる。
【００９８】
また測距装置１は、互いに異なる第１解像度と第２解像度で、右低解像度データおよび左低解像度データを作成する（Ｓ３０）。そして測距装置１は、まず第１解像度の右低解像度データのブロックＢＬの視差を検出し（Ｓ４０）、第１解像度の視差検出結果に基づき、第２解像度の右低解像度データで動的計画法を用いて探索するときの視差の範囲を限定する（Ｓ５０）。
【００９９】
これにより、測距装置１は、第１解像度より高い第２解像度において動的計画法を用いて探索するときの視差の範囲を狭くすることができ、動的計画法を用いて視差を検出するときの処理負荷を低減することができる。
【０１００】
また測距装置１は、撮影解像度対応ブロックをブロックマッチング法を用いて探索する場合に、評価値Ｍ（ｘｍ，ｙｍ，ｘｓ）と、ブロックＢＬｍと左画像データ内の探索ブロックＢＬｓとの視差との相対関係に対して、フィッティング関数を用いてフィッティングするサブピクセル推定を行うことにより、ブロックＢＬｍの視差を検出する（Ｓ６０）。これにより、測距装置１は、サブピクセルの精度で視差を検出することができる。
【０１０１】
以上説明した実施形態において、画像処理装置４は本発明における視差検出装置、Ｓ１０の処理は本発明における画像取得手段、Ｓ３０の処理は本発明における低解像度画像作成手段、Ｓ２１０〜Ｓ２７０，Ｓ３１０〜Ｓ３７０の処理は本発明における第１視差検出手段、Ｓ６０の処理は本発明における第２視差検出手段である。
【０１０２】
また、右画像データは本発明における第１撮影画像、左画像データは本発明における第２撮影画像、第１解像度と第２解像度の右画像データは本発明における第１低解像度画像、第１解像度と第２解像度の左画像データは本発明における第２低解像度画像、ブロックＢＬは本発明における低解像度ブロック、ブロックＢＬｍは本発明における撮影解像度ブロックである。
【０１０３】
また、Ｓ２１０，Ｓ３１０の処理は本発明における節点配置手段、Ｓ２２０〜Ｓ２５０，Ｓ３２０〜Ｓ３５０の処理は本発明におけるコスト算出手段、Ｓ２６０，Ｓ２７０，Ｓ３６０，Ｓ３７０の処理は本発明における視差決定手段である。
【０１０４】
また、コストＤ（ｐ，ｕｐ）は本発明における節点コスト、コストＳ（ｕｐ，ｕｑ）は本発明における視差コスト、Ｘ方向移動コストＥｘ、Ｙ方向移動コストＥｙ、右斜め方向移動コストＥｘ−ｙおよび左斜め方向移動コストＥｘ＋ｙは本発明における移動方向移動コストである。
【０１０５】
以上、本発明の一実施形態について説明したが、本発明は上記実施形態に限定されるものではなく、本発明の技術的範囲に属する限り種々の形態を採ることができる。
（変形例１）
例えば上記実施形態では、２台の撮像装置（すなわち、右撮像装置２と左撮像装置３）を用いて視差を検出するものを示したが、３台以上の撮像装置を用いるようにしてもよい。
【０１０６】
（変形例２）
また上記実施形態では、互いに異なる２つの低解像度（すなわち、第１解像度と第２解像度）の右撮影画像および左撮影画像を作成するものを示したが、１つの低解像度または３つ以上の低解像度の右撮影画像および左撮影画像を作成するようにしてもよい。
【０１０７】
（変形例３）
また上記実施形態では、Ｘ方向移動コストＥｘ、Ｙ方向移動コストＥｙ、右斜め方向移動コストＥｘ−ｙおよび左斜め方向移動コストＥｘ＋ｙを加算した総方向移動コストＥｓｕｍを算出することにより視差を検出するものを示した。しかし、コストＥｘ，Ｅｙ，Ｅｘ−ｙ，Ｅｘ＋ｙに基づいて視差を検出する方法は、総方向移動コストＥｓｕｍに限定されるものではなく、コストＥｘ，Ｅｙ，Ｅｘ−ｙ，Ｅｘ＋ｙを考慮できる手法であればよい。
【０１０８】
上記実施形態における１つの構成要素が有する機能を複数の構成要素として分散させたり、複数の構成要素が有する機能を１つの構成要素に統合させたりしてもよい。また、上記実施形態の構成の一部を省略してもよい。また、上記実施形態の構成の少なくとも一部を、他の上記実施形態の構成に対して付加又は置換してもよい。なお、特許請求の範囲に記載した文言のみによって特定される技術思想に含まれるあらゆる態様が本発明の実施形態である。
【符号の説明】
【０１０９】
１…測距装置、２…右撮像装置、３…左撮像装置、４…画像処理装置
【図１】
2017045124.tif 000007
【図２】
2017045124.tif 000008
【図４】
2017045124.tif 000009
【図７】
2017045124.tif 000010
【図８】
2017045124.tif 000011
【図９】
2017045124.tif 000012
【図１０】
2017045124.tif 000013
【図１１】
2017045124.tif 000014
【図１２】
2017045124.tif 000015
【図１３】
2017045124.tif 000016
【図３】
2017045124.tif 000017
【図５】
2017045124.tif 000018
【図６】
2017045124.tif 000019
【図１４】
2017045124.tif 000020