(57)【特許請求の範囲】
【請求項１】
第一の画像取得手段からの第一の画像と第二の画像取得手段からの第二の画像が入力される画像入力手段と、
前記第一の画像に含まれる画素ごとに、前記第一の画像に設定される第一のウィンドウと、前記第一のウィンドウに対応して前記第二の画像に設定される第二のウィンドウとの間の非類似性に応じた評価値であるウィンドウコストを計算するウィンドウコスト計算処理手段と、
前記第一の画像に含まれる画素ごとに計算されたウィンドウコストを累積加算して累積加算コストを計算する累積加算コスト計算処理手段と、
前記累積加算コストを修正する修正コストを計算する修正コスト計算処理手段と、
前記修正コストに基づいて前記第一のウィンドウに含まれる画素に対応する点を前記第二の画像において求め、視差データを出力する対応点判定手段と、
前記視差データを記憶する視差データ記憶手段と、
を有してなり、
前記ウィンドウコスト計算処理手段は、前記第一のウィンドウに含まれる注目画素に対応して設定された複数の対応点候補ごとに前記第二のウィンドウを設定して前記ウィンドウコストを計算し、
前記累積加算コスト計算処理手段は、前記複数の対応点候補のそれぞれに応じた視差ごとに、前記第一の画像に含まれる画素のうち前記注目画素から同じ方向上の画素のウィンドウコストを累積加算して、前記注目画素からの方向ごとに前記累積加算コストを計算し、
前記修正コスト計算処理手段は、前記複数の対応点候補のそれぞれに応じた視差ごとに、前記注目画素からの方向ごとの信頼性を評価し、前記注目画素からの方向ごとに計算された前記累積加算コストを前記信頼性の低い方向の累積加算コストから順に加算して前記修正コストを計算し、
前記対応点判定手段は、前記注目画素に対応して設定された複数の対応点候補のうち、前記修正コストが最小となる対応点候補を対応点として、前記注目画素と前記対応点との視差データを出力し、
前記累積加算コスト計算処理手段が前記複数の対応点候補のそれぞれに応じた視差ごとに計算する前記累積加算コストは、前記視差から所定の範囲に隣接する画素ごとの累積加算コストのうち最小の累積加算コストが累積加算されて計算され、
前記修正コスト計算処理手段が前記複数の対応点候補のそれぞれに応じた視差ごとに計算する前記修正コストは、前記視差から所定の範囲に隣接する画素ごとの累積加算コストのうち最小の累積加算コストが累積加算されて計算される、
ことを特徴とするステレオ画像処理装置。
【請求項２】
前記修正コスト計算処理手段は、前記注目画素からの方向ごとの信頼性を、ウィンドウコストが小さい画素が存在する方向を信頼性が高いものとして評価することを特徴とする請求項１記載のステレオ画像処理装置。
【請求項３】
前記対応点判定手段は、前記第一の画像と前記第二の画像に共通する走査線を座標軸とする探索平面を作成し、前記探索平面上の座標値が単調増加する点列の候補の中から、前記点列上の各点の前記修正コストの合計が最小となる点列を探索して対応点を求めることを特徴とする請求項１または２記載のステレオ画像処理装置。
【請求項４】
第一の画像取得手段からの第一の画像と第二の画像取得手段からの第二の画像が入力される画像入力ステップと、
前記第一の画像に含まれる画素ごとに、前記第一の画像に設定される第一のウィンドウと、前記第一のウィンドウに対応して前記第二の画像に設定される第二のウィンドウとの間の非類似性に応じた評価値であるウィンドウコストを計算するウィンドウコスト計算ステップと、
前記第一の画像に含まれる画素ごとに計算されたウィンドウコストを累積加算して累積加算コストを計算する累積加算コスト計算ステップと、
前記累積加算コストを修正する修正コストを計算する修正コスト計算ステップと、
前記修正コストに基づいて前記第一のウィンドウに含まれる画素に対応する点を前記第二の画像において求め、視差データを出力する対応点判定ステップと、
前記視差データを記憶する視差データ記憶ステップと、
を有してなり、
前記ウィンドウコスト計算ステップは、前記第一のウィンドウに含まれる注目画素に対応して設定された複数の対応点候補ごとに前記第二のウィンドウを設定して前記ウィンドウコストを計算し、
前記累積加算コスト計算ステップは、前記複数の対応点候補のそれぞれに応じた視差ごとに、前記第一の画像に含まれる画素のうち前記注目画素から同じ方向上の画素のウィンドウコストを累積加算して、前記注目画素からの方向ごとに前記累積加算コストを計算し、
前記修正コスト計算ステップは、前記複数の対応点候補のそれぞれに応じた視差ごとに、前記注目画素からの方向ごとの信頼性を評価し、前記注目画素からの方向ごとに計算された前記累積加算コストを前記信頼性の低い方向の累積加算コストから順に加算して前記修正コストを計算し、
前記対応点判定ステップは、前記注目画素に対応して設定された複数の対応点候補のうち、前記修正コストが最小となる対応点候補を対応点として、前記注目画素と前記対応点との視差データを出力し、
前記累積加算コスト計算処理手段が前記複数の対応点候補のそれぞれに応じた視差ごとに計算する前記累積加算コストは、前記視差から所定の範囲に隣接する画素ごとの累積加算コストのうち最小の累積加算コストが累積加算されて計算され、
前記修正コスト計算処理手段が前記複数の対応点候補のそれぞれに応じた視差ごとに計算する前記修正コストは、前記視差から所定の範囲に隣接する画素ごとの累積加算コストのうち最小の累積加算コストが累積加算されて計算される、
ことを特徴とするステレオ画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２台以上のカメラで同一の対象物の基準画像と参照画像とを撮影し、これらの画像の対応点をエピポーラ線上で探索して、その対応点のずれを示す視差データを算出するものであって、２枚の画像の画素それぞれを相互に対応付けて２台のカメラの対象物に対する視差を画素ごとに求めるステレオ画像処理装置に関する。
【背景技術】
【０００２】
現在、さまざまな分野において複数のカメラを用いた３次元計測システムが利用されている。計測対象物を複数のカメラで撮影し、撮影された画像間の視差を検出し、これにより、対象物までの距離を算出するようにしている。一般的には、２つのカメラからの画像信号の輝度を比較することで、２つの画像信号が最も類似する位置を求めている。
【０００３】
また、計測の精度を向上するために、先験的な知識が利用されている。その一つは、物体の表面は連続しているので、カメラによって観測される物体表面の奥行き情報も連続することが期待できるというものである。この知識を計測のアルゴリズムに反映させるいくつかの手法が提案されている。
【０００４】
特許文献１では、特徴の抽出が容易なエッジ等を有する領域から、テクスチャが複雑で特徴の抽出が困難な領域へと奥行き情報の伝播を試みている。注目画素とその隣接画素の視差はほぼ等しいと仮定し、注目画素の視差と隣接画素の視差との差が一定数以下になるよう探索範囲を限定し、その範囲内で最も類似する対応点を採用する。
【０００５】
また、非特許文献１では、ウィンドウコストに修正を加えることが提案されている。注目画素を挟んで左と右の二方向からウィンドウコストを累積的に加算し、かつ両者を合計する。こうして得た修正コストは、連続性の仮定に反するため対応させるべきでない点との非類似性が強調される。それにより、画像の水平方向について滑らかに連続する奥行きを支持する修正コストが得られる。
【０００６】
また、非特許文献２では、対応点を判定する方法として動的計画法が、また非特許文献１と非特許文献３では、走査線最適化法が提案されている。
【０００７】
【特許文献１】特許第2843034号「画像処理方法」
【０００８】
【非特許文献１】Kim,  J.,  Lee,  K.,  Choi,  B.,  and  Lee,  S.  A  dense  stereo  matching  using  two-pass  dynamic  programming  with  generalized  ground  control  points.  Proc.  on  Computer  Vision  and  Pattern  Recognishon,  Vol.2,  p.1075−1082,  2005.
【非特許文献２】A.  F.  Bobick  and  S.  S.  Intille.  Large  occlusion  stereo.  International  Journal  of  Computer  Vision,  Vol.33,  No.3,  p.1−20,  1999.
【非特許文献３】D.  Scharstein  and  R.  Szeliski,  A  taxonomy  and  evaluation  of  dense  two-frame  stereo  correspondence  algorithms,  International  Jounal  of  Computer  Vision,  Vol.47,  p.  7−42,  2002.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、特許文献１の構成では、テクスチャが弱く抽出すべき特徴そのものに乏しい領域では、対応させるべき点について類似性が極大とならず、適切な奥行き情報を伝播することができない、という問題がある。
【００１０】
また、非特許文献１に開示された方法でも、奥行きに段差があるとき適切な結果が得られない。奥行きの段差に対して、テクスチャの弱い領域へ誤った奥行き情報を伝播する、あるいは段差の形状を平滑化してしまう、という問題がある。物体の表面については奥行きを滑らかに連続させて、同時に段差については奥行きの不連続を保存しなければならない場合に、誤りが生じてしまう。
【００１１】
本発明は、上述した従来技術の課題に鑑みてなされたもので、テクスチャの弱い領域および奥行きの段差を有する画像であっても、画像の対応付けに際しミスマッチングを軽減して高精度の視差検出を行うことができるステレオ画像処理装置、方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明では、画像入力手段と、ウィンドウコスト計算処理手段と、累積加算コスト計算処理手段と、修正コスト計算処理手段と、対応点判定手段と、視差データ記憶手段と、を有するステレオ画像処理装置を提案する。画像入力手段は、第一の画像取得手段からの第一の画像と第二の画像取得手段からの第二の画像が入力される。ウィンドウコスト計算処理手段は、第一の画像の第一の画素データを相互に異なる位置に含む複数の第一のウィンドウの各々について、当該第一ウィンドウと、指定された視差データに対応した第二の画像の第二のウィンドウとの間の非類似性に応じた評価値であるウィンドウコストを生成する。累積加算コスト計算処理手段は、第一のウィンドウのウィンドウコストに、第一の画素データに隣接する三以上の画素データのウィンドウコストを累積加算する。修正コスト計算処理手段は、累積加算コスト計算処理手段により計算した累積加算コストを集計した修正コストを計算する。対応点判定手段は、修正コストに基づいて第一の画像の画素データそれぞれの対応点を第二の画像において求め、視差データを出力する。視差データ記憶手段は、視差データを記憶する。
【００１３】
さらに上記構成において、修正コスト計算処理手段は、累積加算した方向各々のウィンドウコストを合計し、累積加算した隣接する画素の数から一を減じた数の前記第一の画素のウィンドウコストを、合計したウィンドウコストから減算することで修正コストを計算するステレオ画像処理装置を提案する。
【００１４】
また、上記構成において、修正コスト計算処理手段は、隣接する方向それぞれの信頼性を評価し、評価値に基づいてそれぞれの方向に対応する隣接する画素のウィンドウコストを累積加算することで修正コストを計算するステレオ画像処理装置を提案する。
【００１５】
また、対応点判定手段は、ウィンドウコストが最小値となる第二の画像データにおける画素データを対応点として判定するステレオ画像処理装置を提案する。
【００１６】
さらに、対応点判定手段は、動的計画法により対応点を判定するステレオ画像処理装置を提案する。
【発明の効果】
【００１７】
本発明によれば、複数の面により奥行きの段差が形成される対象の計測において、計測する点に隣接する３以上の方向、例えば、上下左右４方向、あるいは斜めを含む８方向、あるいは任意の複数の方向から奥行きの連続性を反映することで、特定の方向においてテクスチャが弱い場合や、同じ方向にテクスチャが類似する場合であっても、他の方向から連続する奥行きが支持され、ステレオマッチングの精度を向上させることができる。
【００１８】
また、方向に優先順位を与えることによって、奥行きの段差を保存する。画素ごとに、各方向の信頼性を推定し、信頼性の低い方向の評価を低く、信頼性の高い方向の評価を高くすることによって、修正コストが平滑化されることを抑止することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の画像処理装置の構成を示す図である。
【図２】ステレオ計測の原理を示す図である。
【図３】参照画像における対応点の探索方法を示す図である。
【図４】本発明におけるステレオ画像処理装置のブロック図である。
【図５】本発明における画像処理方法を示すフローチャートである。
【図６】累積加算における加算結果の再利用方法を説明する図である。
【図７】本発明における修正コストの算出方法を説明する図である。
【図８】累積加算における修正コストの算出方法の概要を示すフローチャートである。
【図９】最小ウィンドウコストの算出方法を示すフローチャートである。
【図１０】方向の順位付け方法を示すフローチャートである。
【図１１】方向間の累積加算方法を示すフローチャートである。
【図１２】最下位の方向による初期値設定の方法を示すフローチャートである。
【図１３】残りの方向における累積加算方法を示すフローチャートである。
【図１４】加算と最小値の判定方法を示すフローチャートである。
【図１５】入力するステレオ画像の例である。
【図１６】本発明を適用した場合の三次元計測結果である。
【発明を実施するための形態】
【００２０】
図１は、本発明のステレオ画像処理装置の構成を示す図である。本発明のステレオ画像処理装置は、同一の対象物を撮影する二台のカメラと、撮影された二枚の画像から対応点を探索して奥行き情報を出力するコンピュータを備える。
【００２１】
基準カメラによって撮影された画像はケーブル１によってコンピュータに転送され、基準画像として記憶される。参照カメラで撮影した画像はケーブル２によってコンピュータに転送され、参照画像として記憶される。これ以降、基準カメラと参照カメラの組をステレオカメラと呼び、基準画像と参照画像の組をステレオ画像と呼ぶ。
【００２２】
基準カメラと参照カメラは、ピントや絞り，感度などの特性が等しくなるようにあらかじめ調整されており、撮影する位置のみが異なる。基準カメラと参照カメラは平行ステレオカメラとなるように配置される。平行ステレオカメラとは、二台のカメラの光軸が互いに平行であり、かつ撮像面が同一平面上にあって水平方向に整列されたものを指す。カメラの配置は左右が逆であっても、水平方向ではなく垂直方向に整列して配置してもよい。以降では説明を簡単にするため、左側を基準カメラ、右側を参照カメラとして扱う。
【００２３】
コンピュータはステレオマッチング装置と記憶装置とディスプレイを備える。ステレオマッチング装置はステレオ画像から対応点を探索する処理を行う。記憶装置は、カメラから取得したステレオ画像、およびステレオマッチング装置により作成する奥行き情報を記憶する。ディスプレイは奥行き情報に基づいて対象物を立体表示する。
【００２４】
図２は、ステレオ計測の原理を示す図である。三次元空間中の点P はステレオ画像に投影され、点P0および点P1をもたらす。基準カメラと参照カメラの位置が異なるため、それぞれの画像に投影された点の二次元座標は一致することなく、カメラから点Pまでの距離に応じて二次元座標のずれを生じる。このずれの大きさを視差と呼ぶ。計測前の点Pの三次元座標は未知であるため、その視差もまた未知である。ステレオカメラによる計測は、画像処理を用いてステレオ画像から視差を獲得することにより達せられる。基準画像上の点P0に対応する点P1を参照画像から精度良く求めるほど、より正確に点Pの三次元座標を計測することが可能となる。本発明において、視差と三次元座標を区別する必要がないとき、単に奥行き情報と呼ぶ。
【００２５】
コンピュータから，ステレオカメラに二枚の画像の撮影を指示する命令がされる。ステレオカメラにより撮影された画像はデジタル化され，コンピュータへと転送される。ステレオ画像が入力されると、コンピュータは基準画像上の点P0に対応する点P1を参照画像から探索する。点Pの視差が確定すると、三角測量の原理によりカメラ中心O0とO1および画像中の点P0とP1から三次元空間中の点Pの三次元座標が直ちに求まる。以上の処理を基準画像上の各画素について繰り返すことにより、ステレオカメラによって撮影された対象物に関する奥行き情報を獲得する。
【００２６】
コンピュータは、得られた奥行き情報に基づいてディスプレイに対象物を立体的に表示する。あるいは対象物の形状を分析する処理を行って分析結果をディスプレイに表示する。
【００２７】
図３は、対応点の探索方法を示す図である。ステレオ相関法は、基準画像上の各点ごとに、対応する点を参照画像より探索する。平行ステレオカメラよって撮影すると、一方の画像上のある一点に対する他方の画像上での対応点は、上下位置が同一の走査線上に存在することが知られている。走査線とは画像上に水平に並んだ画素の列である。すなわち基準画像上にある一点に対して対応点を求めるためには、参照画像上のただ一列の走査線を探索すればよい。平行ステレオカメラではない二台のカメラによって撮影が行われた場合でも、基準カメラと参照カメラの相対的な位置関係が既知であれば、平行化と呼ばれる画像変換によって同様の対応点探索が可能となる。
【００２８】
対応点の探索は、基準画像上に設けた小領域と、参照画像上に設けた小領域とを比較する。この小領域をウィンドウと呼ぶ。基準画像上の注目した画素に対し、その近傍にウィンドウを設ける。参照画像の走査線上に並んでいる対応点候補それぞれの近傍にウィンドウを設ける。ウィンドウ内に写る像より、注目画素と各対応点候補との非類似性を数値化する。この非類似性の評価値をウィンドウコストと呼ぶ。ウィンドウコストには、輝度の差分の絶対値の総和などを用いる。
図３のように、縦軸にウィンドウコストを、横軸に対応点候補の視差をとってグラフ化すると、類似性が最も高い候補においてピークを示す谷を描く曲線となる。ウィンドウコストが最小となる候補を対応点とする。
【００２９】
図４は、本発明におけるステレオ画像処理装置のブロック図である。カメラなどの画像取得手段４０１ａ、ｂと、画像取得手段からの画像を入力する画像入力部４０２、取得した画像を記憶するステレオ画像記憶手段４０３、ステレオマッチング装置４１０とステレオマッチング装置で算出された視差データを記憶する視差記憶手段４０８と、視差データに基づいて対象物体を立体表示するディスプレイなどの立体表示手段４０９を有している。
【００３０】
ステレオマッチング装置４１０は、２台以上のカメラで構成されるステレオカメラからの画像であるステレオ画像の対応点を検出し視差データを得るための装置であって、通常は、コンピュータの制御手段が処理を行う。制御手段は、例えば、ＣＰＵ（Central  Processing  Unit：中央演算処理装置）やＶＤＰ（Video  Display  Processor）などのプロセッサや、ＡＳＩＣ、ＩＣメモリなどから構成される。ステレオマッチング装置４１０は、ウィンドウコスト計算処理部４０４、累積加算コスト計算処理部４０５、修正コスト計算処理部４０６、対応点判定部４０７を有している。
【００３１】
ウィンドウコスト計算処理部４０４は、参照画像における対応点を探索するために、基準画像に含まれる各画素についてウィンドウコストの計算を行う。ステレオ画像入力部４０２よりステレオ画像が入力されると、ウィンドウコスト計算処理部４０４はウィンドウコストの計算を開始する。ウィンドウコストの計算は、基準画像に含まれる各画素について繰り返す。
【００３２】
累積加算コスト計算処理部４０５は、基準画像の各画素について、ウィンドウコストの累積加算を行う。累積加算は、基準画素を中心として任意の方向に隣接する３以上の画素であればよく、例えばある画素を中心とする８方向において隣接する画素からコストを累積加算することによって行う。
【００３３】
修正コスト計算処理部４０６は、累積加算コスト計算処理部４０５において計算した累積加算コストについて、奥行きの連続性が反映されるように、合計か、各方向の信頼性を算出することで修正コストの算出を行う。修正コストの計算方法の詳細については、後述する。
【００３４】
対応点判定部４０７は、修正コスト計算処理部４０６で計算された修正コストに基づいて、カメラから対象物までの奥行きを推定して、対応点を判定し、対応点の視差を計算する。
【００３５】
視差記憶手段４０８は、対応点判定部４０７において計算された視差データを記憶する。立体表示手段４０９は、計算された視差データをもとに、対象物の３次元表示を可能とする表示手段である。
【００３６】
図５は、本発明における画像処理方法を示すフローチャートである。まず、画像取得手段（４０１ａ、ｂ）は、ステレオ画像を撮影し、撮影されたステレオ画像は画像入力部（４０２）からステレオ画像記憶手段（４０３）へ記憶される（Ｓ５０１）。
【００３７】
記憶されたステレオ画像に基づいて、対応点探索のためにウィンドウコストを計算する（Ｓ５０２）。オペレータはあらかじめ、対応点の探索範囲の上限dmaxと下限dmin、奥行きの不連続にペナルティを課すためのしきい値T，奥行きの連続性が反映される視差の範囲m、奥行きの連続性を反映する方向とその数n、対応点の探索に用いるウィンドウの大きさwをコンピュータに入力しておく。ウィンドウの形状は正方形であり、wは一辺の長さを表す。なお、ウィンドウの形状は必ずしも正方形に制限されず、長方形などであってもよい。ウィンドウコストは、次のように計算される。まず画像の水平座標値をx、垂直座標値をyによって表す。基準画像上のある二次元座標(x,  y)の画素に注目し、図３に示すように(x,  y)を中心としてウィンドウを設ける。対応点候補となる視差dの画素について、参照画像上の座標(x-d,  y)を中心にウィンドウを設ける。
【００３８】
基準画像と参照画像のウィンドウの組より、ウィンドウコストC(x, y, d)を以下の計算によって求める。Ilは基準画像の画素の輝度，Irは参照画像の画素の輝度を表す。このウィンドウコストをSAD（Sum of Absolute Differences）と呼ぶ。ウィンドウコストはウィンドウ間の非類似性を表す指標であればよく、SSD（Sum of Squared Differences）すなわち輝度の差の自乗和などを用いてもよい。
【００３９】
【数１】
0005682065.tif 000002
【００４０】
次にコンピュータは基準画像の各画素について、ウィンドウコストの累積加算を繰り返す（Ｓ５０３）。基準画像の画素に注目したとき、視差dのウィンドウコストの加算について説明する。注目画素(x, y)の視差dに関する累積加算コストGk(x, y, d)を求めるため、次の計算を行う。注目画素から見て方向kに隣接する画素の座標を(x+a, y+b)とする。d-mからd+mまでの範囲に含まれる視差をd’で表す。隣接画素の累積加算コストGk(x+a, y+b, d’)と、奥行きの不連続に対するペナルティ関数t(d, d’)の値とを合計する。視差d’の範囲d-mからd+mの中から最小となる合計値を求め、前記処理によって求めたウィンドウコストC(x, y, d)に加算して、累積加算コストGk(x, y, d)として記憶する。
【００４１】
【数２】
0005682065.tif 000003
【００４２】
記憶した累積加算コストGk(x, y, d)は、将来において同じ方向k上の画素の累積加算時に参照することが可能となる。したがって過去に累積加算コストを計算した画素が存在す
る方向は、記憶済みの累積加算コストを参照することによって、累積加算の計算量を削減できる。
【００４３】
例として、注目画素を中心とする８方向からウィンドウコストを累積加算する場合、図６のように順方向ラスタスキャンにおいて左方向から斜め右下方向にかけての計算を行う。同様に逆方向ラスタスキャンにおいて右方向から斜め左上方向にかけての計算を行うと、画像を二回走査するだけで累積加算の処理が完了する。ここで順方向ラスタスキャンとは画像の左上から右下へ向かう経路を意味し、走査線上の画素を左から右へ走査し、走査線を上から下へ辿る。一方、逆方向ラスタスキャンとは画像の右下から左上へ向かう経路を意味し、走査線上の画素を右から左へ走査し、走査線を下から上へ辿る。
【００４４】
なおt(d,  d’)は次の関数とする。奥行きが連続するという仮定が成り立つとき値が0となり、仮定から外れるとき値がTとなる。Tはペナルティの大きさを表すしきい値である。
【００４５】
【数３】
0005682065.tif 000004
【００４６】
また、上記の計算方法における視差d’の範囲d-mからd+mは、m>0でなければならない。この範囲内からGk(x+a,  y+b,  d’)の最小値を求めた場合、その値が描く曲線はピークが平坦なものになる。すなわちm>0とすることによって、注目画素から画像上の距離が離れている画素ほど、そのウィンドウコストが修正コストに与える影響は小さくなる。これにより、注目画素から遠く離れた画素が、注目画素に対して奥行きを連続させるよう過剰に拘束をかけることを防止する。
【００４７】
以上の処理を注目画素の全ての対応点候補について行い、注目画素の方向ｋに累積加算された累積加算コストを計算する。この処理を1からnまで繰り返し、各方向のウィンドウコストを累積加算して記録する。
【００４８】
コンピュータは前記処理によって累積加算した累積加算コストより、n個の方向より奥行きの連続性が反映されるよう修正された修正コストを計算する（Ｓ５０４）。n個の処理結果を合計する（Ｓ５０５）か、あるいはn個の処理結果を累積加算して（Ｓ５０６）、修正コストを求める。後者を用いることにより、奥行きの段差を保存する効果が得られる。合計による修正コストの計算方法及び累積加算による修正コストの計算方法については、後述する。
【００４９】
次に、ステレオマッチング装置４１０の対応点判定部４０７は、修正コストの情報を基に、画像取得手段（４０１ａ、ｂ）から対象物までの奥行きを推定して、視差データを作成する（Ｓ５０７）。対応点の探索範囲を[dmin,  dmax]で表すとき、画素(x,  y)について
【００５０】
【数４】
0005682065.tif 000005
【００５１】
となる対応点の視差D(x,  y)を計算する処理を行う（Ｓ５０９）。これを基準画像の各画素について繰り返す。対応点を判定する方法には、非特許文献２に記載されている動的計画法を用いてもよい（Ｓ５０８）。また、動的計画法の代わりに、非特許文献３に記載されている走査線最適化法を用いてもよい。
【００５２】
動的計画法によって対応点を判定する場合は次のように行う。まず探索平面を作成する。これは基準画像と参照画像に共通する水平な走査線を二本の座標軸とする平面である。探索平面上の点は、基準画像および参照画像の走査線上にある二点の対応関係を表現する。ある二点をステレオカメラで撮影したとき、それらの点の位置関係は両方の画像で同じになること可能性が高い。つまり、一般的には一方の画像に左右の関係で写った二点は、他方の画像に左側の点と右側の点が入れ替わって写ることはない。したがって探索平面上の対応点は、座標値が基準・参照ともに小さい方から大きい方へ単調に増加する点の列となる。これによって作られる点列の候補の中から、漸化計算を用いて点列上の各点の修正コストの合計が最小となる点列を動的計画法により探索し、その点列に含まれる各点を対応点として採用する。
【００５３】
走査線最適化法は、探索平面の座標軸を基準画像の水平な走査線および視差とし、基準画像の水平座標が単調増加する点列を候補とする。また連続する二点間の視差が異なる場合にはペナルティとなる値を加える。それ以外は動的計画法と同様の方法によって対応点を決定する。
【００５４】
次に、ステレオマッチング装置４１０は、対応点の判定によって得られた結果を出力し、基準画像の各画素について視差データを記憶する（Ｓ５１０）。
【００５５】
修正コストの算出方法について、まず合計による修正コスト算出方法（Ｓ５０５）について図７を参照しながら、説明する。本発明では、奥行きの連続性を注目画素に反映するために、注目画素を挟む水平な二方向だけでなく、複数の任意の方向を考慮して修正コストを算出する。図７に示すように注目画素(x,  y)を中心するn個の方向kに累積加算したコストを合計する。なお、８近傍の方向を考慮する場合、ｎ＝８であり、８方向となる。このように合計された値には注目画素のウィンドウコストがn倍されて含まれることになる。注目画素の奥行きに対する不要な重みづけを取り除くため、方向数nから１を減じた数に倍する注目画素のウィンドウコストC(x,  y,  d)を減算し、注目画素の修正コストS(x,  y,  d)とする。修正コストS(x, y, d)は次の式によって表される。
【００５６】
【数５】
0005682065.tif 000006
【００５７】
次に信頼性に基づいて方向ごとに優先順位を与え、奥行きの段差が保存されるよう修正コストを算出する方法（Ｓ５０６）について説明する。図８は累積加算による修正コストの算出方法を示す概要フローチャートである。各画素にn個の方向を順序付けるため、下記の計算によって各方向の信頼性を評価する。すなわち、注目画素の隣接画素を参照し、よりウィンドウコストの小さい画素が存在する方向をより信頼性が高いものとする。まず、注目画素の各方向の隣接画素について最小ウィンドウコストをそれぞれ探索する（Ｓ８０１）。次に、最小ウィンドウコストの集合を降順にソートすることで方向の順位付けを行い（Ｓ８０２）、方向間の累積加算を行う（Ｓ８０３）。
【００５８】
図９は、Ｓ８０１における最小ウィンドウコストの探索方法を具体的に示すフローチャートである。注目画素(x,  y)に対して方向kで隣接する画素の、視差dに応じて変化するウィンドウコストC(x+a,  y+b,  d)から、最小値Mk(x+a,  y+b)を求める。方向は注目画素に対して相対的なので、最小値の算出は画素ごとに方向の数だけ繰り返す必要はなく、画素ごとに１回ずつ求める。最初の画像座標から注目画素(x,  y)として設定し（Ｓ９０１）、方向kで隣接する画素のウィンドウコストの上限値をM(x,  y)として設定する（Ｓ９０２）。ウィンドウコストの最小値を求めるために最小視差から最大視差までdの値を１ずつ増やして計算する（Ｓ９０３）。視差dの値に応じて変化するC(x,  y,  d)がM(x,  y)より小さいか判定し（Ｓ９０４）、M(x,  y)＞C(x,  y,  d)の場合はC(x,  y,  d)をM(x,  y)として設定する（Ｓ９０５）。このように判定していくことで注目画素(x,  y)の方向kにおけるウィンドウコストの最小値を求める（Ｓ９０６）。次の画像座標を(x,  y)と設定し（Ｓ９０７）、同様に、また全ての画素についてスキャンを行ってウィンドウコストの最小値を算出していく（Ｓ９０８）。
【００５９】
図１０は、Ｓ８０２における方向の順位付け方法を具体的に示すフローチャートである。最初の画像座標から注目画素(x,  y)として設定し（Ｓ１００１）、方向の番号と最小ウィンドウコストをn個分、列に格納していく（Ｓ１００２）。第k方向の隣接画素の相対座標を(a,  b)と設定し（Ｓ１００３）、列rのk番目の要素に第k方向の最小ウィンドウコストM(x+a,  y+b)を格納し、列q(x,  y)のk番目の要素に方向kの番号を格納し（Ｓ１００４）、同様にn個分について繰り返す（Ｓ１００５）。次に列rのウィンドウコストの降順に方向の列q(x,  y)をソートする（Ｓ１００６）。次の画像座標を(x,  y)と設定し（Ｓ１００７）、同様に、すべての画像座標についてスキャンを行って処理を繰り返す（Ｓ１００８）。以上の処理によって、優先順位iを方向kに対応付ける関数q(x,  y,  i)を得る。なお、iは数値が大きいほど信頼性が高いものとする。このとき(x,  y)の優先順位iについて次の関係が成り立つ。
【００６０】
【数６】
0005682065.tif 000007
【００６１】
図１１は、Ｓ８０３における方向間の累積加算方法を具体的に示すフローチャートである。最初の画像座標から注目画素(x,  y)として設定し（Ｓ１１０１）、優先順位が最下位の方向の累積加算コストを修正コスト計算の初期値として設定する（Ｓ１１０２）。図１２は、最下位の方向による初期値の設定方法のフローを示している。まず、q(x,  y,  1)より得られる最下位の方向の番号を方向jに設定する（Ｓ１２０１）。次に、dを最小視差から最大視差まで１ずつ増やし（Ｓ１２０２）、j方向の累積加算コストGj(x,  y,  d)を修正コストS(x,  y,  d)の初期値とし（Ｓ１２０３）、すべての視差について繰り返す（Ｓ１２０４）。
【００６２】
次に残りの方向について累積加算を行っていく（Ｓ１１０３）。図１３は、残りの方向による累積加算の算出方法を示すフローチャートである。優先順位の変数iを２から最上位まで順に１ずつ増やすことで順次、累積加算を行っていく（Ｓ１３０１）。すなわち、優先順位を下からi番目とした場合に、q(x, y, i)より得られる第i位の方向の番号を方向jに設定する（Ｓ１３０２）。ｄを最小視差から最大視差まで１ずつ増やして累積加算コストを加算していく（Ｓ１３０３）。累積加算コストの加算と累積加算コストの最小値の判定処理を行い（Ｓ１３０４）、全ての視差について繰り返す（Ｓ１３０５）。以上の処理によって求めた第i位までの方向の加算結果Ｓ’（ｄ）を、ｄを最小視差から最大視差まで１ずつ増やして（Ｓ１３０６）、修正コストS(x, y, d)に代入し（Ｓ１３０７）、すべての視差について繰り返す（Ｓ１３０８）。同様に、全ての順位の方向について繰り返す（Ｓ１３０９）。
【００６３】
加算と最小値の判定処理（Ｓ１３０４）について、図１４により説明する。修正コストの上限値をＢと設定する（Ｓ１４０１）。すでに計算された下位の方向の計算結果のうち、視差dとの差が奥行きの連続性が反映される範囲mに含まれる視差d’について（Ｓ１４０２）、Bが修正コストS(x, y, d)にペナルティ関数t(d, d’)を加算した値よりも大きいか判定する。Ｂの値が大きい場合はS(x, y, d)+t(d, d’)をＢに代入し（Ｓ１４０４）、そうでない場合はBを変えない。同様に、範囲内の全ての視差d’について繰り返す（Ｓ１４０５）。方向jの累積加算コストに求めた最小値を積算し、S’(d)に代入する（Ｓ１４０６）。
【００６４】
図１１に戻り、このようにしてすべての方向における累積加算を行った後、注目画素のウィンドウコストを最小視差から最大視差まで全ての視差の値において累積加算した修正コストから減算する処理を行う（Ｓ１１０４）。つまり、S(x,  y,  d)−C(x,  y,  d)を修正コストS(x, y, d)とする処理を繰り返す（Ｓ１１０５、Ｓ１１０６）。そして次の画像座標へと移り、すべての画素について累積加算により修正コストを得る。
【００６５】
このように、各方向について累積加算したウィンドウコストを、さらに方向間で累積加算することによって段差を保存する修正コストを得る。注目画素から離れた画素のウィンドウコストは注目画素の修正コストに与える影響が小さくなる。累積加算の方法を各方向の結果にも適用し、信頼性の低い方向から高い方向へ処理を進めることによって、確からしい方向の結果ほどより強く修正コストに反映させる。累積加算によって求める場合の、n個の方向に基づく修正コストS(x, y, d)は次の式によって表される。
【００６６】
【数７】
0005682065.tif 000008
【００６７】
次に、本発明の適用例を説明する。図１５は、入力するステレオ画像の例を示している。この画像には、背景にテクスチャの弱い領域である壁面や類似するテクスチャが水平方向に続く領域がある。本発明の画像処理装置により、８方向において修正コストを算出してステレオマッチング処理を行い、三次元計測を行った結果が図１６である。このように、本発明を適用することで、複数の面によって奥行きに段差が形成されているような画像においても正確にステレオマッチング処理を行うことができる。
【産業上の利用可能性】
【００６８】
本発明は、ステレオ画像をもとに視差データを算出する画像処理装置に適用可能である。
【符号の説明】
【００６９】
４０１ａ，ｂ  画像取得手段
４０２        画像入力部
４０３        ステレオ画像記憶手段
４０４        ウィンドウコスト計算処理部
４０５        累積加算コスト計算処理部
４０６        修正コスト計算処理部
４０７        対応点判定部
４０８        視差記憶手段
４０９        立体表示手段
４１０        ステレオマッチング装置
【図１】
0005682065.tif 000009
【図２】
0005682065.tif 000010
【図３】
0005682065.tif 000011
【図４】
0005682065.tif 000012
【図５】
0005682065.tif 000013
【図６】
0005682065.tif 000014
【図７】
0005682065.tif 000015
【図８】
0005682065.tif 000016
【図９】
0005682065.tif 000017
【図１０】
0005682065.tif 000018
【図１１】
0005682065.tif 000019
【図１２】
0005682065.tif 000020
【図１３】
0005682065.tif 000021
【図１４】
0005682065.tif 000022
【図１５】
0005682065.tif 000023
【図１６】
0005682065.tif 000024