画像マッチング装置、画像マッチング方法および画像マッチング用プログラム
【課題】 動的計画法を用いた画像マッチング装置において、照明変化に頑健で輪郭部での対応精度の良い、かつ物体領域内部などの輝度値が平滑領域においても正しい対応を得ることが可能な画像マッチングを行う。
【解決手段】 ステレオ画像の走査線対をそれぞれ座標軸にとる探索平面上の各点について、正規化相関係数を算出すると同時に輝度値差分による類似度も算出する。対応経路として接続すべき点を探索する際に、まず正規化相関係数を参照し、正規化相関係数が所定の閾値（ＴＨ１）を上回る場合は正規化相関係数を類似度評価値として用いる。正規化相関係数が所定の閾値（ＴＨ１）を下回る場合には、輝度値差分を参照し、輝度値差分が所定の閾値（ＴＨ２）を上回る場合は、輝度値差分を正規化相関係数の代替として用いる。輝度値差分が所定の閾値（ＴＨ２）を下回る場合は、非対応領域として、当該点を探索対象から除外する。
【解決手段】 ステレオ画像の走査線対をそれぞれ座標軸にとる探索平面上の各点について、正規化相関係数を算出すると同時に輝度値差分による類似度も算出する。対応経路として接続すべき点を探索する際に、まず正規化相関係数を参照し、正規化相関係数が所定の閾値（ＴＨ１）を上回る場合は正規化相関係数を類似度評価値として用いる。正規化相関係数が所定の閾値（ＴＨ１）を下回る場合には、輝度値差分を参照し、輝度値差分が所定の閾値（ＴＨ２）を上回る場合は、輝度値差分を正規化相関係数の代替として用いる。輝度値差分が所定の閾値（ＴＨ２）を下回る場合は、非対応領域として、当該点を探索対象から除外する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像マッチング装置、画像マッチング方法および画像マッチング用プログラムに関し、特に動的計画法を用いて対応探索を行う画像マッチング装置、画像マッチング方法および画像マッチング用プログラムに関する。
【背景技術】
【０００２】
複数のカメラを用いて物体を撮影して得たステレオ画像から、三角測量の原理を適用して対象物体の位置や形状を求める画像マッチング処理技術において、画像内の対応を得る方法の一つとして、動的計画法（Dynamic Programming, DP）を走査線毎に適用するＤＰマッチング方法が知られている。
【０００３】
非特許文献１には、両眼立体視における対応問題への動的計画法の適用方法が記載されている。非特許文献１では、左右のカメラのレンズ中心を結ぶ直線とシーン中の任意の一点で決定される平面（エピポーラ平面）が左右の画像面と作る交線をエピポーラ線と呼び、シーン点の左右画像上の像は必ず左右一対のエピポーラ線上に存在するという性質を利用して、左右エピポーラ線間の１次元における対応関係を求める問題に分解することによってＤＰの枠組みに当てはめる方法を紹介している。具体的には、左右一対のエピポーラ線を２本の座標軸とする探索平面として捉え、左右エピポーラ線をそれぞれ複数の部分に分割し、探索平面上で単調上昇性を守ることによってＤＰで最適解が見つかることを保証するＭａｒｃｏｖ性を満たし、部分要素間の対応の適合性と連続性を評価関数によって表現すると、エピポーラ線全体の対応が、再帰評価の漸化式によって最適解を求めることで得られると紹介している。この際、部分要素として、個々の画素を用いる方法、エッジを用いる方法、２個のエッジで区切られた区間を用いる方法を挙げている。
【０００４】
また、非特許文献２には、多くのエッジが近隣する場合や雑音によるエッジが存在する場合などに対応のあいまいさを避けるために、左右１対の走査線上での対応探索を探索結果とする従来のＤＰマッチング方法から発展させ、各走査線内の対応探索に加えて、複数の走査線にまたがる連結エッジ同士の対応探索にも動的計画法を導入し、整合性が保たれる条件下で左右画像間の最適な対応を求める方法が記載されている。具体的には、各走査線内探索に使用する２次元探索平面を走査線に垂直な方向に積み重ねた３次元探索空間において、左右１対の連結エッジが共通の走査線にまたがっているときに探索平面上でそれぞれ１つのノードをつくる。それらノードが３次元空間中に形成するノードの集合を３Ｄノードと呼び、各３Ｄノードにおいてそこに至るパスの集合のうち、最小コストのものを選択することによって最適集合を求める方法を紹介している。この際、パスの集合のコストは、それに属する個々のパスのコストの和とし、実験では、個々のパスとのコストを左右区間内の画素の明度の分散に基づいて算出している。
【０００５】
また、双方向に対応探索を行うことでオクルージョン領域を検出し、オクルージョン領域が検出された領域内の対応点についてはパスを与えないという対応不連続なパスを許す動的計画法を用いることで、より正確な対応を得る方法がある（例えば、特許文献１。）。特許文献１に記載されている方法では、まず、二つの画像Ａ，Ｂを走査線毎に分割し、さらに走査線をセグメントに分割し、同位置の走査線上に存在するセグメント間の対応について、画素値の相互相関を計算する。次に、対応毎の相関係数の値を用い、ＡからＢ画像上のセグメントへの順位づけおよびＢからＡ画像上のセグメントへの順位付けを行い、ＡＢ方向の順位とＢＡ方向の順位を加算した値をコストとし、更に対応を与えないブロックの数に比例するペナルティを加え、探索平面内で相関計算を行った範囲に含まれる格子点について、最小の到達コストを動的計画法を用いて計算する。
【０００６】
【非特許文献１】大田友一，山田博三，「動的計画法によるパターンマッチング」，情報処理，１９８９年，Ｖｏｌ．３０，Ｎｏ．９，ｐ．１０５８−１０６６
【非特許文献２】大田友一，金出武雄，「走査線間の整合性を考慮した２段の動的計画法によるステレオ対応探索」，情報処理，１９８５年，Ｖｏｌ．２６，Ｎｏ．１１，ｐ．１３５６−１３６８
【特許文献１】特許第００３０２７９９５号公報（段落００１８−００２２）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
類似度として正規化相関係数を用いる従来の方法では、エッジ付近では正確な対応が取れるが、輝度値が平滑な領域で対応が取れず、結果、視差を正しく計算できないという問題がある。対応が取れない理由は、正規化相関係数が、ブロック内の輝度値が一様な場合に算出できない、または信頼できる値にならないためである。
【０００８】
本発明の目的は、照明変化に対し頑健な特徴を維持しつつ、輝度値の平滑な領域においても対応を得ることの可能な画像マッチング装置、画像マッチング方法および画像マッチング用プログラムを提供する。
【課題を解決するための手段】
【０００９】
本発明による画像マッチング装置は、画像対の対応探索時に評価する類似度として相関係数と輝度値差分を併用することによってステレオ画像のマッチングを行う画像マッチング手段を備えたことを特徴とする。
【００１０】
また、画像マッチング手段は、画像対の部分要素間の類似度を、相関類似度として、相互相関によって求める相関類似度算出手段と、画像対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求める輝度値差分類似度算出手段と、画像対の部分要素間の類似度評価値を抽出し、類似度評価値を抽出する際に、相関類似度算出手段により求められた相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度算出手段により求められた輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする統合類似度判定手段とを備えていてもよい。
【００１１】
また、統合類似度判定手段は、画像対の部分要素間の類似度評価値を抽出する際に、相関類似度算出手段により求められた相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度算出手段により求められた輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を、相関類似度の分布範囲と類似度方向に一致するように変換して相関類似度の代替としてもよい。そのような場合には、類似度の代替を意識しないでその後の動作に用いることができる。
【００１２】
また、本発明による画像マッチング装置は、同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶するステレオ画像記憶手段と、ステレオ画像記憶手段に記憶されたステレオ画像に対して、それぞれの画面上で同一物体を写す点が走査線と平行となるよう画像を変換する画像平行化手段とを備え、相関類似度算出手段が、画像平行化手段により変換された画像の走査線対の部分要素間の類似度を求め、輝度値差分算出手段が、画像平行化手段により変換された画像の走査線対の部分要素間の類似度を求めてもよい。そのような場合には、対応探索を走査線に沿って行うことができるため、部分要素を抽出する際の補完計算などの余計な処理をしなくてもすむ。また、対応探索の結果を簡潔なパラメータで表すこともできる。
【００１３】
また、本発明による画像マッチング装置は、統合類似度判定手段により抽出された類似度評価値に基づいて、走査線対における各点対の接続関係を示す接続行列を作成する接続行列作成手段と、接続行列作成手段により作成された接続行列を用いて、走査線対における視差を確定する対応経路を求める対応経路接続手段とを備えていてもよい。
【発明の効果】
【００１４】
本発明の効果は、照明変化に強く、物体領域内部などの輝度値が平滑な領域でも対応を得ることができ、よって高精度かつ頑健な画像マッチングを実現することができる。
【発明を実施するための最良の形態】
【００１５】
以下、発明を実施するための最良の形態について図面を参照して詳細に説明する。図１は、本発明による画像マッチング装置の構成例を示すブロック図である。図１に示す画像マッチング装置は、ステレオ画像記憶手段１と画像平行化手段２とＤＰマッチング手段３と視差データ記憶手段４とを備える。ＤＰマッチング手段３は、相関値テーブル作成手段３１と輝度値差分テーブル作成手段３４と接続行列作成手段３２と対応経路接続手段３３とを備える。
【００１６】
ステレオ画像記憶手段１は、同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶する。画像平行化手段２は、ステレオ画像記憶手段１に記憶されたステレオ画像に対して平行化操作を行う。相関値テーブル作成手段３１は、画像平行化手段２により平行化された画像における各走査線対に対して、相互相関による類似度を求めて相関値テーブルを作成する。輝度値差分テーブル作成手段３４は、画像平行化手段２により平行化された画像における各走査線対に対して、輝度値差分による類似度を求めて輝度値差分テーブルを作成する。接続行列作成手段３２は、相関値テーブルおよび輝度値差分テーブルを用いて、各走査線対における各点対の接続関係を示す接続行列を作成する。対応経路接続手段３３は、接続行列作成手段３２により作成された接続行列を用いて、各走査線対における視差を確定するための対応経路を求める。視差データ記憶手段４は、ＤＰマッチング手段３により得られた対応経路を視差データとして記憶する。
【００１７】
本実施の形態において、ステレオ画像記憶手段１および視差データ記憶手段４は、記憶装置によって実現される。画像平行化手段２、相関値テーブル作成手段３１、輝度値差分テーブル作成手段３４、接続行列作成手段３２および対応経路接続手段３３は、例えば、プログラムに従って動作するＣＰＵによって実現される。なお、プログラムは、画像マッチング装置が備える記憶装置（図示せず。）に記憶される。
【００１８】
次に、図２のフローチャートを参照して画像マッチング装置の動作について詳細に説明する。図２は、画像マッチング装置の動作例を示すフローチャートである。画像平行化手段２は、ステレオ画像記憶手段１に記憶されている、同一対象を異なる角度から撮影したステレオ画像に対し、ステレオ画像を撮影したカメラ間の幾何情報を用いて、画像内の同一物体の対応を拘束するエピポーラ線を走査線に一致するように変換する（ステップＡ１）。この処理は平行化と呼ばれ、左右の各カメラの焦点を結ぶ直線に対し平行な仮想画像平面を考え、この仮想画像平面に各画像を射影することにより行う。このような平行化の処理を行うことによって、一般に水平でない画像中全てのエピポーラ線を走査線と同じ水平方向に揃えることができ、対応探索の問題を同一ｙ座標の走査線内で対応位置を求める１次元問題として捉えることができる。
【００１９】
次に、画像平行化手段２により平行化された画像対は、ＤＰマッチング手段３に与えられる。ＤＰマッチング手段３においては、まず、相関値テーブル作成手段３１が、平行化済みの画像対における各走査線対について、相関値テーブルを作成する（ステップＡ２）。図３は、平行化済みの画像対における走査線対の探索平面を示す模式図である。図３に示すように、対象とする対応走査線対をそれぞれ座標軸にとった探索平面として捉えると、探索平面上の各点は、各走査線対上でのｘ座標の組み合わせによって表される。図３に示す例では、平行化された画像対をそれぞれ左画像、右画像とした場合、左画像上の対応走査線を横軸、右画像上の対応走査線を縦軸にとった探索平面として捉える。この探索平面上で同じ物体が撮像されていると思われる点を求め、それを接続した対応経路を描くことで、当該走査線対上の全ての画素についての視差を得ることができる。
【００２０】
相関値テーブルの作成動作を具体的に説明する。相関値テーブル作成手段３１は、探索平面上の各点に対応する左右の走査線上各点の周辺にそれぞれ所定の同じ大きさのブロック（図３における小領域）を設け、ブロック間の類似度を計算する。この際のブロック間類似度は、ブロック内画素値の正規化相関係数を用いる。相関値テーブル作成手段３１は、計算によって求めた正規化相関係数を相関値として、探索平面に対応させた２次元配列に格納する。この配列を相関値テーブルと呼ぶ。相関値は１から−１の値をとり、最も類似している場合に最大値１をとる。なお、走査線上に配置されるブロックは縦の広がりをもつブロックであってもよい。このような場合には、走査線を跨いだ類似度の評価を行うことができる。
【００２１】
また、相関値テーブルの作成動作と並行して、輝度値差分テーブル作成手段３４が、平行化済みの画像対における各走査線対について、輝度値差分テーブルを作成する（ステップＡ３）。具体的には、相関値テーブルの作成動作と同様に、探索平面上の各点に対応する左右の走査線上各点の周辺にそれぞれ所定の同じ大きさのブロックを設け、ブロック間の類似度を計算する。この際のブロック間類似度は、ブロック間の対応画素における輝度値差分を用いる。輝度値差分には、例えば、輝度値差分の絶対値をブロック内画素数で平均化した値を用いる。輝度値差分テーブル作成手段３４は、計算によって求めた輝度値差分を、相関値の範囲と一致し、かつ相関値の類似度方向とも一致するように変換した値を正規化輝度差分値として、探索平面に対応させた２次元配列に格納する。この配列を輝度値差分テーブルと呼ぶ。正規化輝度差分値は、相関値と同様に、１から−１の値をとり、最も類似している場合に最大値１をとる。
【００２２】
次に、接続行列作成手段３２が、各走査線対について得られた相関値テーブルと輝度値差分テーブルとを用いて接続行列を作成する（ステップＡ４）。接続行列とは、探索平面上の各点について、当該点に経路を接続すべき点の座標と、累積された評価値で構成される情報であり、対応経路を求める際に用いる情報である。
【００２３】
図４を参照して接続行列の作成動作を具体的に説明する。図４は、接続行列作成処理を示す模式図である。まず、接続行列作成手段３２は、探索平面内において、ある閾値を超える類似度が得られている点を探索対象点として、探索対象点を右上隅にとる矩形探索窓を設ける。次に、この探索窓範囲内において、同じ閾値を超える類似度を持つ点の集合について、各点の累積重みに探索対象点との市街地距離（city block metric, Manhattan metric）を加味した値を調べ、この値が最大となる点の座標を接続すべき点として接続行列に記録する。また、このときの最大値に探索対象点の類似度を加えた値を、探索対象点の累積重みとして記録する。接続すべき点を探索するにあたって、探索窓範囲に含まれる点における累積重みの計算を事前に終了しておく必要があるため、接続行列作成手段３２は、探索対象点の抽出および接続すべき点の探索を、探索平面の原点から出発して対角線方向に進める。
【００２４】
図５は、接続行列作成の際の探索平面上の各点における類似度の決定動作を示すフローチャートである。接続行列作成手段３２は、まず、相関値テーブルを参照し（ステップＢ１）、相関値と閾値ＴＨ１を比較する（ステップＢ２）。相関値が閾値ＴＨ１を越える場合には、その相関値をそのまま統合類似度とする（ステップＢ６）。相関値が閾値ＴＨ１を越えない場合には、輝度値差分テーブルを参照し（ステップＢ３）、輝度値差分と閾値ＴＨ２を比較する（ステップＢ４）。ここで、輝度値差分が閾値ＴＨ２を越える場合には、輝度値差分に対して、類似度範囲の調整を行う（ステップＢ５）。具体的には、相関値と輝度値差分の分布の違いを補正するため、輝度値差分に閾値の比（閾値ＴＨ１／閾値ＴＨ２）をかけ、更に最大値を１とする調整を行う。この調整により、輝度値差分を正規化相関係数の代替として用いることができる。そして、類似度範囲の調整によって得た値を統合類似度とする（ステップＢ６）。輝度値差分が閾値ＴＨ２を越えない場合には、その点は類似しないものとし、探索対象点の抽出および接続すべき点の探索の対象から除外する。本動作における統合類似度は、接続行列作成の際に用いる類似度として用いる。
【００２５】
次に、対応経路接続手段３３が、各走査線対について得られた接続行列を用いて探索平面内の対応経路を求める（ステップＡ５）。図６は、対応経路接続処理を示す模式図である。対応経路接続手段３３は、探索平面の対角線上右上端を探索開始点とし、その点に対応する接続行列に記録された情報を参照して得られる座標点を順次接続しながら移動していく動作を、探索平面原点に達するまで繰り返す。このように、座標点を接続することによって得られた経路が、当該走査線対における対応を示す対応経路である。
【００２６】
次に、視差データ記憶手段４は、ＤＰマッチング手段３により得られた対応経路の経路点列データを視差データとして記憶する。
【００２７】
以上のように、本実施の形態によれば、ＤＰマッチングを行う際に、エッジ付近で有効な相関値による類似度と、相関係数で算出が困難な輝度値の平滑な領域でも安定した値を得られる輝度値差分による類似度とを併用し、相関値が低い場合にのみ輝度値差分による評価を行うことで、照明変化に強く、物体領域内部でも対応を失わない、高精度かつ頑健な（輝度値にばらつきのある領域において照明が変化した場合でも、輝度値が平滑な領域においても、共に正しい対応を得ることができる）画像マッチング装置を提供することができる。
【００２８】
なお、本発明の実施の形態は上記説明に限定されるものではなく、様々な条件での実施が可能である。例えば、対象とするステレオ画像は２枚に限定されるものではなく、同一対象を撮影した３枚以上の画像を対象としてもよい。３枚以上の画像群のうちに複数の画像ペアを設定し、それぞれの画像ペアについて既に説明した方法を用いて得られた視差データを、例えば、視差データから計算される奥行きについて多数決を行うなどの方法を用いて統合してもよい。そのような場合には、より高い精度の画像マッチングが可能となる。
【００２９】
また、対象のステレオ画像に対し平行化を行わず、画像中の全ての点について求めたエピポーラ線対に対して探索平面を構成してもよい。そのような場合には、画像の画素配置とずれた位置にある画素を補間計算により求める手段と、対応経路をエピポーラ線のパラメータと対応させて記録する手段とを備えることで、同等の効果を得ることができる。
【００３０】
また、輝度値差分に関しても上記で説明した絶対値差分平均に限らず、差分の二乗和などを用いても同等の効果を得ることができる。
【００３１】
また、正規化相関係数を求める際に用いる画素値は、その画素を特徴づける値であって、単一の値に限定されるものではない。もちろん、輝度値であってもよい。また、カラー画像などで画素値を単一の値に変換しない場合は、例えば、画素に与えられたそれぞれの値について正規化相関係数を求め、平均化した値を用いてもよい。
【００３２】
なお、本実施の形態において、画像マッチング手段はＤＰマッチング手段３によって実現される。また、相関類似度算出手段は相関テーブル作成手段３１によって実現される。輝度値差分類似度算出手段は輝度値差分テーブル作成手段３４によって実現される。統合類似度判定手段、接続行列作成手段は接続行列作成手段３２によって実現される。ステレオ画像記憶手段はステレオ画像記憶手段１によって実現される。画像平行化手段は画像平行化手段２によって実現される。対応経路接続手段は対応経路接続手段３３によって実現される。
【実施例】
【００３３】
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作を説明する。まず、対象となる物体を異なる視点より撮影した複数の画像、すなわちステレオ画像対を得る。対象物体の形状や位置に時間的な変化が無い場合、同一カメラを移動して撮影した画像の組を用いても構わないが、異なる位置に設置した複数のカメラを用いて撮影した画像対を用いても良い。さらにこの対象画像対の幾何的な位置関係を、何らかのキャリブレーション方法により求めておく。この処理におけるキャリブレーション方法については特に制限は無い。このようにして幾何的配置が既知となったステレオ画像を、ステレオ画像記憶手段１に記憶する。なお、本実施例におけるステレオ画像は、レンズ歪みが無視できるほど小さいか、キャリブレーション操作により歪みを補正したものとする。
【００３４】
次に、画像平行化手段２は、このステレオ画像に対し、求められたカメラ間の幾何情報を用いて、画像中の同一物体の対応を拘束するエピポーラ線を、走査線に一致するよう変換する。この処理は平行化と呼ばれ、対応探索を容易にするためにステレオ処理の前処理として行われる。
【００３５】
以下、図７を参照して平行化処理について説明する。ステレオ画像におけるエピポーラ線とは、撮影対象のある１点を対象点とし、対象点とそれぞれのカメラ中心で決まる平面が、左右それぞれの画像面と交わってできる画像上の直線のことである。対象点を映した左右それぞれの画像上の像は、このエピポーラ線の上に限定される。よって、左画像上のある点に対応する、右画像上の同一の物体を映した点を探索する場合には、このエピポーラ線上を探索すればよいことになる。左右の画像の幾何的配置や焦点距離を用いれば、このエピポーラ線を求めることができるが、一般に、エピポーラ線は走査線に対し水平でなく傾いた直線となるため、このままでは、探索範囲は複数の走査線に分布されることとなる。そこで、左右の各カメラの焦点を結ぶ線に対し平行な仮想画像平面を考え、これに左右の画像を射影することで、平行に配置された画像面の一致するステレオカメラで撮影された場合と等価になり、一般に水平でない画像中全てのエピポーラ線を、走査線と同じ水平方向に揃えることが出来る。これにより、ステレオマッチングを同一ｙ座標の走査線内で対応位置を求める１次元問題とすることができる。
【００３６】
次に、ＤＰマッチング手段３が、画像平行化手段２により平行化された画像対に対し、ＤＰマッチングを行う。ＤＰマッチングの処理は、左画像と右画像から得られる対応する走査線の対を単位として行い、画像対全体の対応計算結果は、画像対にある全ての走査線対について行ったＤＰマッチングの処理結果を集積して得ることができる。
【００３７】
以下、ある走査線対におけるＤＰマッチング動作について説明する。
【００３８】
図３に示すように、左右それぞれの画像から得られた２本の走査線のｘ座標を、直交する２軸に再配置した座標平面として捉え、これを探索平面と呼ぶ。走査線のｘ座標は、例えば、画面の一番左を０とする画素位置を表すものとする。探索平面上の各点は、左画像走査線上と右画像走査線上にそれぞれ配置した点のｘ座標の組で表すことができる。本実施例では、左画像走査線におけるｘ座標を右方向に、右画像走査線におけるｘ座標を上方向にとる。つまり、左下隅が左右の走査線上で共に左端にある点の組を表し、右上隅が左右の走査線上で共に右端にある点の組を表す。この左下隅と右上隅を結ぶ対角線は、左画像と右画像でｘ座標が一致している組の集合であり、視差がない状況を表す。ＤＰマッチングは、この探索平面上において、同一の物体が撮像されている座標の組みを求めて繋いでいき、一本の経路を求めることが目的であって、この経路は対応経路と呼ばれ、当該走査線対における視差を表す。この対応経路を求めるには、画像対から求めた探索平面各点の類似度を経路に従いながら集積し、累積評価値が最大をとる経路を選択していく。
【００３９】
まず、探索平面上の各点に対応する左右の画像間の類似度を得る。ＤＰマッチングに用いられる類似度の評価値はいくつかあるが、その代表例として正規化相関係数がある。相関値テーブル作成手段３１は、左右の画像走査線上に置いたブロック間の正規化相関係数ｒを以下の式を用いて算出する。以下の式において、Ｎをブロック内画素数、Ｉ１，Ｉ２をそれぞれ左右の各ブロックにおける輝度値とする。なお、分母の値を評価して、所定の閾値を下回る場合には、得られる値の信頼度が低いものとして、ｒの値を０にする。
【００４０】
【数１】
【００４１】
この正規化相関係数ｒは１から−１の値をとり、２つのブロック内の輝度値波形が全ての点で一致するときに最大値１を示す。この値が大きいほど、ブロック間の類似度が高いと評価できる。相関値テーブル作成手段３１は、探索平面原点から開始して、ブロックを置く位置を一画素ずつずらしながら、全ての探索平面上の点を埋めるまで、各ブロック間の正規化相関係数ｒを求め、この値を探索平面の各点に対応づけて相関値テーブルに記録する。なお、ブロックの置く位置は、探索平面上の点によって表される各走査線のｘ座標と当該走査線のｙ座標を中心点とする位置とする。
【００４２】
また、輝度値差分テーブル作成手段３４は、相関値テーブル作成手段３１と同様に設置した各ブロック間の輝度値差分ｄを以下の式を用いて算出する。以下の式において、Ｎをブロック内画素数、Ｉ１，Ｉ２をそれぞれ左右の各ブロックにおける輝度値とする。
【００４３】
ｄ＝（１／Ｎ）Σ｜Ｉ１−Ｉ２｜
【００４４】
ここで、輝度値のとりうる範囲を０〜Ｄ（Ｄは整数）とすると、この輝度値差分ｄも同一の範囲０〜Ｄ（Ｄは整数）であり、輝度値差分ｄの値が低いほど類似度が高いことを示す。この輝度値差分ｄを正規化相関係数ｒの分布範囲(−１〜１)と一致させるため、かつ、類似度の方向（値が大きい方が高い類似度を指す）とも一致させるため、輝度値差分テーブル作成手段３４は、以下の式を用いて輝度値差分ｄを変換し、正規化輝度差分値ｄ’を得る。
【００４５】
ｄ’＝１−２×（ｄ／Ｄ）
【００４６】
輝度値差分テーブル作成手段３４は、この正規化輝度差分値ｄ’を探索平面の各点に対応づけて輝度値差分テーブルに記録する。
【００４７】
次に、接続行列作成手段３２が、各走査線対について得られた相関値テーブルと輝度値差分テーブルとを用いて接続行列を作成する接続行列作成処理を行う。接続行列作成処理は、まず、探索平面上の各点における類似度の決定動作に基づいて、探索対象とする統合類似度を得た点（以下、探索対象点という）につき、探索対象点を右上隅にとる矩形探索窓を探索平面上に設ける。次に、この探索窓範囲内の全ての点について、同様に探索平面上の各点における類似度の決定動作に基づいて、探索対象とする統合類似度を得た点の集合を得る。更に、この点集合について、各点の累積重みに、探索対象点との市街地距離に相関の閾値ＴＨ１をかけた値を加算し、この値が最大となる点を選ぶ。この点の座標を接続すべき点として接続行列に記録する。また、このときの最大値に探索対象点の統合類似度を加算した値を探索対象点の累積重みとして接続行列に記憶する。
【００４８】
接続すべき点を探索するにあたって、探索窓範囲に含まれる点では累積重みの計算を事前に終了しておく必要があるため、上記で説明した接続行列作成処理は、探索平面の原点から初期条件を設定して出発し、順次対角線方向に進める。つまり、図４に示すように、探索平面において傾きが−１となる直線ｘ１＋ｘ２＝ｔを考え、パラメータｔを０に初期化して出発し、この直線上にある全ての点について、上記の手順で統合類似度の評価と矩形探索窓内での接続座標の探索を行い、順次パラメータｔに１を加えた直線に移り、同様の処理を行い、右上端まで到達したならば処理を終了する。
【００４９】
次に、対応経路接続手段３３が、上記処理で得られた接続行列を用いて、探索平面内の対応経路を求める処理を行う。具体的には、まず探索平面の右上隅を起点として初期参照点とする。次に、参照点の接続行列に記録された座標を取得し、参照点からその記録された座標点に経路を接続する。その上で、経路を延長した座標点に参照点を移動し、再度その点の接続行列に記録された座標情報を読み出して同様の処理を繰り返し、探索平面の原点に到達した時点で完成した経路が対応経路となる。これを視差データとして記録して当該走査線対のＤＰマッチングを終了する。
【００５０】
以上の処理を左右画像の全ての走査線対について行うことで、画像対全体の視差を得ることが出来る。
【産業上の利用可能性】
【００５１】
本発明によれば、ステレオ撮像された画像から対象までの距離や対象の形状を計測することができるため、写真計測や航空写真による大規模空間の形状計測、工業製品や部品の計測および検査、コンピュータグラフィック応用などの用途に適用できる。
【図面の簡単な説明】
【００５２】
【図１】本発明における画像マッチング装置の構成例を示すブロック図である。
【図２】画像マッチング装置の動作例を示すフローチャートである。
【図３】平行化済みの画像対における走査線対の探索平面を示す模式図である。
【図４】本発明における接続行列作成処理を示す模式図である。
【図５】探索平面上の各点における類似度の決定動作を示すフローチャートである。
【図６】本発明における対応経路接続処理を示す模式図である。
【図７】本発明における平行化処理を示す模式図である。
【符号の説明】
【００５３】
１ ステレオ画像記憶手段
２ 画像平行化手段
３ ＤＰマッチング手段
３１ 相関値テーブル作成手段
３２ 接続行列作成手段
３３ 対応経路接続手段
３４ 輝度値差分テーブル作成手段
４ 視差データ記憶手段
【技術分野】
【０００１】
本発明は、画像マッチング装置、画像マッチング方法および画像マッチング用プログラムに関し、特に動的計画法を用いて対応探索を行う画像マッチング装置、画像マッチング方法および画像マッチング用プログラムに関する。
【背景技術】
【０００２】
複数のカメラを用いて物体を撮影して得たステレオ画像から、三角測量の原理を適用して対象物体の位置や形状を求める画像マッチング処理技術において、画像内の対応を得る方法の一つとして、動的計画法（Dynamic Programming, DP）を走査線毎に適用するＤＰマッチング方法が知られている。
【０００３】
非特許文献１には、両眼立体視における対応問題への動的計画法の適用方法が記載されている。非特許文献１では、左右のカメラのレンズ中心を結ぶ直線とシーン中の任意の一点で決定される平面（エピポーラ平面）が左右の画像面と作る交線をエピポーラ線と呼び、シーン点の左右画像上の像は必ず左右一対のエピポーラ線上に存在するという性質を利用して、左右エピポーラ線間の１次元における対応関係を求める問題に分解することによってＤＰの枠組みに当てはめる方法を紹介している。具体的には、左右一対のエピポーラ線を２本の座標軸とする探索平面として捉え、左右エピポーラ線をそれぞれ複数の部分に分割し、探索平面上で単調上昇性を守ることによってＤＰで最適解が見つかることを保証するＭａｒｃｏｖ性を満たし、部分要素間の対応の適合性と連続性を評価関数によって表現すると、エピポーラ線全体の対応が、再帰評価の漸化式によって最適解を求めることで得られると紹介している。この際、部分要素として、個々の画素を用いる方法、エッジを用いる方法、２個のエッジで区切られた区間を用いる方法を挙げている。
【０００４】
また、非特許文献２には、多くのエッジが近隣する場合や雑音によるエッジが存在する場合などに対応のあいまいさを避けるために、左右１対の走査線上での対応探索を探索結果とする従来のＤＰマッチング方法から発展させ、各走査線内の対応探索に加えて、複数の走査線にまたがる連結エッジ同士の対応探索にも動的計画法を導入し、整合性が保たれる条件下で左右画像間の最適な対応を求める方法が記載されている。具体的には、各走査線内探索に使用する２次元探索平面を走査線に垂直な方向に積み重ねた３次元探索空間において、左右１対の連結エッジが共通の走査線にまたがっているときに探索平面上でそれぞれ１つのノードをつくる。それらノードが３次元空間中に形成するノードの集合を３Ｄノードと呼び、各３Ｄノードにおいてそこに至るパスの集合のうち、最小コストのものを選択することによって最適集合を求める方法を紹介している。この際、パスの集合のコストは、それに属する個々のパスのコストの和とし、実験では、個々のパスとのコストを左右区間内の画素の明度の分散に基づいて算出している。
【０００５】
また、双方向に対応探索を行うことでオクルージョン領域を検出し、オクルージョン領域が検出された領域内の対応点についてはパスを与えないという対応不連続なパスを許す動的計画法を用いることで、より正確な対応を得る方法がある（例えば、特許文献１。）。特許文献１に記載されている方法では、まず、二つの画像Ａ，Ｂを走査線毎に分割し、さらに走査線をセグメントに分割し、同位置の走査線上に存在するセグメント間の対応について、画素値の相互相関を計算する。次に、対応毎の相関係数の値を用い、ＡからＢ画像上のセグメントへの順位づけおよびＢからＡ画像上のセグメントへの順位付けを行い、ＡＢ方向の順位とＢＡ方向の順位を加算した値をコストとし、更に対応を与えないブロックの数に比例するペナルティを加え、探索平面内で相関計算を行った範囲に含まれる格子点について、最小の到達コストを動的計画法を用いて計算する。
【０００６】
【非特許文献１】大田友一，山田博三，「動的計画法によるパターンマッチング」，情報処理，１９８９年，Ｖｏｌ．３０，Ｎｏ．９，ｐ．１０５８−１０６６
【非特許文献２】大田友一，金出武雄，「走査線間の整合性を考慮した２段の動的計画法によるステレオ対応探索」，情報処理，１９８５年，Ｖｏｌ．２６，Ｎｏ．１１，ｐ．１３５６−１３６８
【特許文献１】特許第００３０２７９９５号公報（段落００１８−００２２）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
類似度として正規化相関係数を用いる従来の方法では、エッジ付近では正確な対応が取れるが、輝度値が平滑な領域で対応が取れず、結果、視差を正しく計算できないという問題がある。対応が取れない理由は、正規化相関係数が、ブロック内の輝度値が一様な場合に算出できない、または信頼できる値にならないためである。
【０００８】
本発明の目的は、照明変化に対し頑健な特徴を維持しつつ、輝度値の平滑な領域においても対応を得ることの可能な画像マッチング装置、画像マッチング方法および画像マッチング用プログラムを提供する。
【課題を解決するための手段】
【０００９】
本発明による画像マッチング装置は、画像対の対応探索時に評価する類似度として相関係数と輝度値差分を併用することによってステレオ画像のマッチングを行う画像マッチング手段を備えたことを特徴とする。
【００１０】
また、画像マッチング手段は、画像対の部分要素間の類似度を、相関類似度として、相互相関によって求める相関類似度算出手段と、画像対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求める輝度値差分類似度算出手段と、画像対の部分要素間の類似度評価値を抽出し、類似度評価値を抽出する際に、相関類似度算出手段により求められた相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度算出手段により求められた輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする統合類似度判定手段とを備えていてもよい。
【００１１】
また、統合類似度判定手段は、画像対の部分要素間の類似度評価値を抽出する際に、相関類似度算出手段により求められた相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度算出手段により求められた輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を、相関類似度の分布範囲と類似度方向に一致するように変換して相関類似度の代替としてもよい。そのような場合には、類似度の代替を意識しないでその後の動作に用いることができる。
【００１２】
また、本発明による画像マッチング装置は、同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶するステレオ画像記憶手段と、ステレオ画像記憶手段に記憶されたステレオ画像に対して、それぞれの画面上で同一物体を写す点が走査線と平行となるよう画像を変換する画像平行化手段とを備え、相関類似度算出手段が、画像平行化手段により変換された画像の走査線対の部分要素間の類似度を求め、輝度値差分算出手段が、画像平行化手段により変換された画像の走査線対の部分要素間の類似度を求めてもよい。そのような場合には、対応探索を走査線に沿って行うことができるため、部分要素を抽出する際の補完計算などの余計な処理をしなくてもすむ。また、対応探索の結果を簡潔なパラメータで表すこともできる。
【００１３】
また、本発明による画像マッチング装置は、統合類似度判定手段により抽出された類似度評価値に基づいて、走査線対における各点対の接続関係を示す接続行列を作成する接続行列作成手段と、接続行列作成手段により作成された接続行列を用いて、走査線対における視差を確定する対応経路を求める対応経路接続手段とを備えていてもよい。
【発明の効果】
【００１４】
本発明の効果は、照明変化に強く、物体領域内部などの輝度値が平滑な領域でも対応を得ることができ、よって高精度かつ頑健な画像マッチングを実現することができる。
【発明を実施するための最良の形態】
【００１５】
以下、発明を実施するための最良の形態について図面を参照して詳細に説明する。図１は、本発明による画像マッチング装置の構成例を示すブロック図である。図１に示す画像マッチング装置は、ステレオ画像記憶手段１と画像平行化手段２とＤＰマッチング手段３と視差データ記憶手段４とを備える。ＤＰマッチング手段３は、相関値テーブル作成手段３１と輝度値差分テーブル作成手段３４と接続行列作成手段３２と対応経路接続手段３３とを備える。
【００１６】
ステレオ画像記憶手段１は、同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶する。画像平行化手段２は、ステレオ画像記憶手段１に記憶されたステレオ画像に対して平行化操作を行う。相関値テーブル作成手段３１は、画像平行化手段２により平行化された画像における各走査線対に対して、相互相関による類似度を求めて相関値テーブルを作成する。輝度値差分テーブル作成手段３４は、画像平行化手段２により平行化された画像における各走査線対に対して、輝度値差分による類似度を求めて輝度値差分テーブルを作成する。接続行列作成手段３２は、相関値テーブルおよび輝度値差分テーブルを用いて、各走査線対における各点対の接続関係を示す接続行列を作成する。対応経路接続手段３３は、接続行列作成手段３２により作成された接続行列を用いて、各走査線対における視差を確定するための対応経路を求める。視差データ記憶手段４は、ＤＰマッチング手段３により得られた対応経路を視差データとして記憶する。
【００１７】
本実施の形態において、ステレオ画像記憶手段１および視差データ記憶手段４は、記憶装置によって実現される。画像平行化手段２、相関値テーブル作成手段３１、輝度値差分テーブル作成手段３４、接続行列作成手段３２および対応経路接続手段３３は、例えば、プログラムに従って動作するＣＰＵによって実現される。なお、プログラムは、画像マッチング装置が備える記憶装置（図示せず。）に記憶される。
【００１８】
次に、図２のフローチャートを参照して画像マッチング装置の動作について詳細に説明する。図２は、画像マッチング装置の動作例を示すフローチャートである。画像平行化手段２は、ステレオ画像記憶手段１に記憶されている、同一対象を異なる角度から撮影したステレオ画像に対し、ステレオ画像を撮影したカメラ間の幾何情報を用いて、画像内の同一物体の対応を拘束するエピポーラ線を走査線に一致するように変換する（ステップＡ１）。この処理は平行化と呼ばれ、左右の各カメラの焦点を結ぶ直線に対し平行な仮想画像平面を考え、この仮想画像平面に各画像を射影することにより行う。このような平行化の処理を行うことによって、一般に水平でない画像中全てのエピポーラ線を走査線と同じ水平方向に揃えることができ、対応探索の問題を同一ｙ座標の走査線内で対応位置を求める１次元問題として捉えることができる。
【００１９】
次に、画像平行化手段２により平行化された画像対は、ＤＰマッチング手段３に与えられる。ＤＰマッチング手段３においては、まず、相関値テーブル作成手段３１が、平行化済みの画像対における各走査線対について、相関値テーブルを作成する（ステップＡ２）。図３は、平行化済みの画像対における走査線対の探索平面を示す模式図である。図３に示すように、対象とする対応走査線対をそれぞれ座標軸にとった探索平面として捉えると、探索平面上の各点は、各走査線対上でのｘ座標の組み合わせによって表される。図３に示す例では、平行化された画像対をそれぞれ左画像、右画像とした場合、左画像上の対応走査線を横軸、右画像上の対応走査線を縦軸にとった探索平面として捉える。この探索平面上で同じ物体が撮像されていると思われる点を求め、それを接続した対応経路を描くことで、当該走査線対上の全ての画素についての視差を得ることができる。
【００２０】
相関値テーブルの作成動作を具体的に説明する。相関値テーブル作成手段３１は、探索平面上の各点に対応する左右の走査線上各点の周辺にそれぞれ所定の同じ大きさのブロック（図３における小領域）を設け、ブロック間の類似度を計算する。この際のブロック間類似度は、ブロック内画素値の正規化相関係数を用いる。相関値テーブル作成手段３１は、計算によって求めた正規化相関係数を相関値として、探索平面に対応させた２次元配列に格納する。この配列を相関値テーブルと呼ぶ。相関値は１から−１の値をとり、最も類似している場合に最大値１をとる。なお、走査線上に配置されるブロックは縦の広がりをもつブロックであってもよい。このような場合には、走査線を跨いだ類似度の評価を行うことができる。
【００２１】
また、相関値テーブルの作成動作と並行して、輝度値差分テーブル作成手段３４が、平行化済みの画像対における各走査線対について、輝度値差分テーブルを作成する（ステップＡ３）。具体的には、相関値テーブルの作成動作と同様に、探索平面上の各点に対応する左右の走査線上各点の周辺にそれぞれ所定の同じ大きさのブロックを設け、ブロック間の類似度を計算する。この際のブロック間類似度は、ブロック間の対応画素における輝度値差分を用いる。輝度値差分には、例えば、輝度値差分の絶対値をブロック内画素数で平均化した値を用いる。輝度値差分テーブル作成手段３４は、計算によって求めた輝度値差分を、相関値の範囲と一致し、かつ相関値の類似度方向とも一致するように変換した値を正規化輝度差分値として、探索平面に対応させた２次元配列に格納する。この配列を輝度値差分テーブルと呼ぶ。正規化輝度差分値は、相関値と同様に、１から−１の値をとり、最も類似している場合に最大値１をとる。
【００２２】
次に、接続行列作成手段３２が、各走査線対について得られた相関値テーブルと輝度値差分テーブルとを用いて接続行列を作成する（ステップＡ４）。接続行列とは、探索平面上の各点について、当該点に経路を接続すべき点の座標と、累積された評価値で構成される情報であり、対応経路を求める際に用いる情報である。
【００２３】
図４を参照して接続行列の作成動作を具体的に説明する。図４は、接続行列作成処理を示す模式図である。まず、接続行列作成手段３２は、探索平面内において、ある閾値を超える類似度が得られている点を探索対象点として、探索対象点を右上隅にとる矩形探索窓を設ける。次に、この探索窓範囲内において、同じ閾値を超える類似度を持つ点の集合について、各点の累積重みに探索対象点との市街地距離（city block metric, Manhattan metric）を加味した値を調べ、この値が最大となる点の座標を接続すべき点として接続行列に記録する。また、このときの最大値に探索対象点の類似度を加えた値を、探索対象点の累積重みとして記録する。接続すべき点を探索するにあたって、探索窓範囲に含まれる点における累積重みの計算を事前に終了しておく必要があるため、接続行列作成手段３２は、探索対象点の抽出および接続すべき点の探索を、探索平面の原点から出発して対角線方向に進める。
【００２４】
図５は、接続行列作成の際の探索平面上の各点における類似度の決定動作を示すフローチャートである。接続行列作成手段３２は、まず、相関値テーブルを参照し（ステップＢ１）、相関値と閾値ＴＨ１を比較する（ステップＢ２）。相関値が閾値ＴＨ１を越える場合には、その相関値をそのまま統合類似度とする（ステップＢ６）。相関値が閾値ＴＨ１を越えない場合には、輝度値差分テーブルを参照し（ステップＢ３）、輝度値差分と閾値ＴＨ２を比較する（ステップＢ４）。ここで、輝度値差分が閾値ＴＨ２を越える場合には、輝度値差分に対して、類似度範囲の調整を行う（ステップＢ５）。具体的には、相関値と輝度値差分の分布の違いを補正するため、輝度値差分に閾値の比（閾値ＴＨ１／閾値ＴＨ２）をかけ、更に最大値を１とする調整を行う。この調整により、輝度値差分を正規化相関係数の代替として用いることができる。そして、類似度範囲の調整によって得た値を統合類似度とする（ステップＢ６）。輝度値差分が閾値ＴＨ２を越えない場合には、その点は類似しないものとし、探索対象点の抽出および接続すべき点の探索の対象から除外する。本動作における統合類似度は、接続行列作成の際に用いる類似度として用いる。
【００２５】
次に、対応経路接続手段３３が、各走査線対について得られた接続行列を用いて探索平面内の対応経路を求める（ステップＡ５）。図６は、対応経路接続処理を示す模式図である。対応経路接続手段３３は、探索平面の対角線上右上端を探索開始点とし、その点に対応する接続行列に記録された情報を参照して得られる座標点を順次接続しながら移動していく動作を、探索平面原点に達するまで繰り返す。このように、座標点を接続することによって得られた経路が、当該走査線対における対応を示す対応経路である。
【００２６】
次に、視差データ記憶手段４は、ＤＰマッチング手段３により得られた対応経路の経路点列データを視差データとして記憶する。
【００２７】
以上のように、本実施の形態によれば、ＤＰマッチングを行う際に、エッジ付近で有効な相関値による類似度と、相関係数で算出が困難な輝度値の平滑な領域でも安定した値を得られる輝度値差分による類似度とを併用し、相関値が低い場合にのみ輝度値差分による評価を行うことで、照明変化に強く、物体領域内部でも対応を失わない、高精度かつ頑健な（輝度値にばらつきのある領域において照明が変化した場合でも、輝度値が平滑な領域においても、共に正しい対応を得ることができる）画像マッチング装置を提供することができる。
【００２８】
なお、本発明の実施の形態は上記説明に限定されるものではなく、様々な条件での実施が可能である。例えば、対象とするステレオ画像は２枚に限定されるものではなく、同一対象を撮影した３枚以上の画像を対象としてもよい。３枚以上の画像群のうちに複数の画像ペアを設定し、それぞれの画像ペアについて既に説明した方法を用いて得られた視差データを、例えば、視差データから計算される奥行きについて多数決を行うなどの方法を用いて統合してもよい。そのような場合には、より高い精度の画像マッチングが可能となる。
【００２９】
また、対象のステレオ画像に対し平行化を行わず、画像中の全ての点について求めたエピポーラ線対に対して探索平面を構成してもよい。そのような場合には、画像の画素配置とずれた位置にある画素を補間計算により求める手段と、対応経路をエピポーラ線のパラメータと対応させて記録する手段とを備えることで、同等の効果を得ることができる。
【００３０】
また、輝度値差分に関しても上記で説明した絶対値差分平均に限らず、差分の二乗和などを用いても同等の効果を得ることができる。
【００３１】
また、正規化相関係数を求める際に用いる画素値は、その画素を特徴づける値であって、単一の値に限定されるものではない。もちろん、輝度値であってもよい。また、カラー画像などで画素値を単一の値に変換しない場合は、例えば、画素に与えられたそれぞれの値について正規化相関係数を求め、平均化した値を用いてもよい。
【００３２】
なお、本実施の形態において、画像マッチング手段はＤＰマッチング手段３によって実現される。また、相関類似度算出手段は相関テーブル作成手段３１によって実現される。輝度値差分類似度算出手段は輝度値差分テーブル作成手段３４によって実現される。統合類似度判定手段、接続行列作成手段は接続行列作成手段３２によって実現される。ステレオ画像記憶手段はステレオ画像記憶手段１によって実現される。画像平行化手段は画像平行化手段２によって実現される。対応経路接続手段は対応経路接続手段３３によって実現される。
【実施例】
【００３３】
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作を説明する。まず、対象となる物体を異なる視点より撮影した複数の画像、すなわちステレオ画像対を得る。対象物体の形状や位置に時間的な変化が無い場合、同一カメラを移動して撮影した画像の組を用いても構わないが、異なる位置に設置した複数のカメラを用いて撮影した画像対を用いても良い。さらにこの対象画像対の幾何的な位置関係を、何らかのキャリブレーション方法により求めておく。この処理におけるキャリブレーション方法については特に制限は無い。このようにして幾何的配置が既知となったステレオ画像を、ステレオ画像記憶手段１に記憶する。なお、本実施例におけるステレオ画像は、レンズ歪みが無視できるほど小さいか、キャリブレーション操作により歪みを補正したものとする。
【００３４】
次に、画像平行化手段２は、このステレオ画像に対し、求められたカメラ間の幾何情報を用いて、画像中の同一物体の対応を拘束するエピポーラ線を、走査線に一致するよう変換する。この処理は平行化と呼ばれ、対応探索を容易にするためにステレオ処理の前処理として行われる。
【００３５】
以下、図７を参照して平行化処理について説明する。ステレオ画像におけるエピポーラ線とは、撮影対象のある１点を対象点とし、対象点とそれぞれのカメラ中心で決まる平面が、左右それぞれの画像面と交わってできる画像上の直線のことである。対象点を映した左右それぞれの画像上の像は、このエピポーラ線の上に限定される。よって、左画像上のある点に対応する、右画像上の同一の物体を映した点を探索する場合には、このエピポーラ線上を探索すればよいことになる。左右の画像の幾何的配置や焦点距離を用いれば、このエピポーラ線を求めることができるが、一般に、エピポーラ線は走査線に対し水平でなく傾いた直線となるため、このままでは、探索範囲は複数の走査線に分布されることとなる。そこで、左右の各カメラの焦点を結ぶ線に対し平行な仮想画像平面を考え、これに左右の画像を射影することで、平行に配置された画像面の一致するステレオカメラで撮影された場合と等価になり、一般に水平でない画像中全てのエピポーラ線を、走査線と同じ水平方向に揃えることが出来る。これにより、ステレオマッチングを同一ｙ座標の走査線内で対応位置を求める１次元問題とすることができる。
【００３６】
次に、ＤＰマッチング手段３が、画像平行化手段２により平行化された画像対に対し、ＤＰマッチングを行う。ＤＰマッチングの処理は、左画像と右画像から得られる対応する走査線の対を単位として行い、画像対全体の対応計算結果は、画像対にある全ての走査線対について行ったＤＰマッチングの処理結果を集積して得ることができる。
【００３７】
以下、ある走査線対におけるＤＰマッチング動作について説明する。
【００３８】
図３に示すように、左右それぞれの画像から得られた２本の走査線のｘ座標を、直交する２軸に再配置した座標平面として捉え、これを探索平面と呼ぶ。走査線のｘ座標は、例えば、画面の一番左を０とする画素位置を表すものとする。探索平面上の各点は、左画像走査線上と右画像走査線上にそれぞれ配置した点のｘ座標の組で表すことができる。本実施例では、左画像走査線におけるｘ座標を右方向に、右画像走査線におけるｘ座標を上方向にとる。つまり、左下隅が左右の走査線上で共に左端にある点の組を表し、右上隅が左右の走査線上で共に右端にある点の組を表す。この左下隅と右上隅を結ぶ対角線は、左画像と右画像でｘ座標が一致している組の集合であり、視差がない状況を表す。ＤＰマッチングは、この探索平面上において、同一の物体が撮像されている座標の組みを求めて繋いでいき、一本の経路を求めることが目的であって、この経路は対応経路と呼ばれ、当該走査線対における視差を表す。この対応経路を求めるには、画像対から求めた探索平面各点の類似度を経路に従いながら集積し、累積評価値が最大をとる経路を選択していく。
【００３９】
まず、探索平面上の各点に対応する左右の画像間の類似度を得る。ＤＰマッチングに用いられる類似度の評価値はいくつかあるが、その代表例として正規化相関係数がある。相関値テーブル作成手段３１は、左右の画像走査線上に置いたブロック間の正規化相関係数ｒを以下の式を用いて算出する。以下の式において、Ｎをブロック内画素数、Ｉ１，Ｉ２をそれぞれ左右の各ブロックにおける輝度値とする。なお、分母の値を評価して、所定の閾値を下回る場合には、得られる値の信頼度が低いものとして、ｒの値を０にする。
【００４０】
【数１】
【００４１】
この正規化相関係数ｒは１から−１の値をとり、２つのブロック内の輝度値波形が全ての点で一致するときに最大値１を示す。この値が大きいほど、ブロック間の類似度が高いと評価できる。相関値テーブル作成手段３１は、探索平面原点から開始して、ブロックを置く位置を一画素ずつずらしながら、全ての探索平面上の点を埋めるまで、各ブロック間の正規化相関係数ｒを求め、この値を探索平面の各点に対応づけて相関値テーブルに記録する。なお、ブロックの置く位置は、探索平面上の点によって表される各走査線のｘ座標と当該走査線のｙ座標を中心点とする位置とする。
【００４２】
また、輝度値差分テーブル作成手段３４は、相関値テーブル作成手段３１と同様に設置した各ブロック間の輝度値差分ｄを以下の式を用いて算出する。以下の式において、Ｎをブロック内画素数、Ｉ１，Ｉ２をそれぞれ左右の各ブロックにおける輝度値とする。
【００４３】
ｄ＝（１／Ｎ）Σ｜Ｉ１−Ｉ２｜
【００４４】
ここで、輝度値のとりうる範囲を０〜Ｄ（Ｄは整数）とすると、この輝度値差分ｄも同一の範囲０〜Ｄ（Ｄは整数）であり、輝度値差分ｄの値が低いほど類似度が高いことを示す。この輝度値差分ｄを正規化相関係数ｒの分布範囲(−１〜１)と一致させるため、かつ、類似度の方向（値が大きい方が高い類似度を指す）とも一致させるため、輝度値差分テーブル作成手段３４は、以下の式を用いて輝度値差分ｄを変換し、正規化輝度差分値ｄ’を得る。
【００４５】
ｄ’＝１−２×（ｄ／Ｄ）
【００４６】
輝度値差分テーブル作成手段３４は、この正規化輝度差分値ｄ’を探索平面の各点に対応づけて輝度値差分テーブルに記録する。
【００４７】
次に、接続行列作成手段３２が、各走査線対について得られた相関値テーブルと輝度値差分テーブルとを用いて接続行列を作成する接続行列作成処理を行う。接続行列作成処理は、まず、探索平面上の各点における類似度の決定動作に基づいて、探索対象とする統合類似度を得た点（以下、探索対象点という）につき、探索対象点を右上隅にとる矩形探索窓を探索平面上に設ける。次に、この探索窓範囲内の全ての点について、同様に探索平面上の各点における類似度の決定動作に基づいて、探索対象とする統合類似度を得た点の集合を得る。更に、この点集合について、各点の累積重みに、探索対象点との市街地距離に相関の閾値ＴＨ１をかけた値を加算し、この値が最大となる点を選ぶ。この点の座標を接続すべき点として接続行列に記録する。また、このときの最大値に探索対象点の統合類似度を加算した値を探索対象点の累積重みとして接続行列に記憶する。
【００４８】
接続すべき点を探索するにあたって、探索窓範囲に含まれる点では累積重みの計算を事前に終了しておく必要があるため、上記で説明した接続行列作成処理は、探索平面の原点から初期条件を設定して出発し、順次対角線方向に進める。つまり、図４に示すように、探索平面において傾きが−１となる直線ｘ１＋ｘ２＝ｔを考え、パラメータｔを０に初期化して出発し、この直線上にある全ての点について、上記の手順で統合類似度の評価と矩形探索窓内での接続座標の探索を行い、順次パラメータｔに１を加えた直線に移り、同様の処理を行い、右上端まで到達したならば処理を終了する。
【００４９】
次に、対応経路接続手段３３が、上記処理で得られた接続行列を用いて、探索平面内の対応経路を求める処理を行う。具体的には、まず探索平面の右上隅を起点として初期参照点とする。次に、参照点の接続行列に記録された座標を取得し、参照点からその記録された座標点に経路を接続する。その上で、経路を延長した座標点に参照点を移動し、再度その点の接続行列に記録された座標情報を読み出して同様の処理を繰り返し、探索平面の原点に到達した時点で完成した経路が対応経路となる。これを視差データとして記録して当該走査線対のＤＰマッチングを終了する。
【００５０】
以上の処理を左右画像の全ての走査線対について行うことで、画像対全体の視差を得ることが出来る。
【産業上の利用可能性】
【００５１】
本発明によれば、ステレオ撮像された画像から対象までの距離や対象の形状を計測することができるため、写真計測や航空写真による大規模空間の形状計測、工業製品や部品の計測および検査、コンピュータグラフィック応用などの用途に適用できる。
【図面の簡単な説明】
【００５２】
【図１】本発明における画像マッチング装置の構成例を示すブロック図である。
【図２】画像マッチング装置の動作例を示すフローチャートである。
【図３】平行化済みの画像対における走査線対の探索平面を示す模式図である。
【図４】本発明における接続行列作成処理を示す模式図である。
【図５】探索平面上の各点における類似度の決定動作を示すフローチャートである。
【図６】本発明における対応経路接続処理を示す模式図である。
【図７】本発明における平行化処理を示す模式図である。
【符号の説明】
【００５３】
１ ステレオ画像記憶手段
２ 画像平行化手段
３ ＤＰマッチング手段
３１ 相関値テーブル作成手段
３２ 接続行列作成手段
３３ 対応経路接続手段
３４ 輝度値差分テーブル作成手段
４ 視差データ記憶手段
【特許請求の範囲】
【請求項１】
動的計画法を用いてステレオ画像のマッチングを行う画像マッチング装置であって、
画像対の対応探索時に評価する類似度として相関係数と輝度値差分を併用することによってステレオ画像のマッチングを行う画像マッチング手段を備えた
ことを特徴とする画像マッチング装置。
【請求項２】
画像マッチング手段は、
画像対の部分要素間の類似度を、相関類似度として、相互相関によって求める相関類似度算出手段と、
画像対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求める輝度値差分類似度算出手段と、
画像対の部分要素間の類似度評価値を抽出し、前記類似度評価値を抽出する際に、前記相関類似度算出手段により求められた相関類似度が所定の評価値に満たない場合であって、前記輝度値差分類似度算出手段により求められた輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする統合類似度判定手段とを備えた
請求項１記載の画像マッチング装置。
【請求項３】
統合類似度判定手段は、
画像対の部分要素間の類似度評価値を抽出する際に、相関類似度算出手段により求められた相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度算出手段により求められた輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を、相関類似度の分布範囲と類似度方向に一致するように変換して前記相関類似度の代替とする
請求項２記載の画像マッチング装置。
【請求項４】
同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶するステレオ画像記憶手段と、
前記ステレオ画像記憶手段に記憶されたステレオ画像に対して、それぞれの画面上で同一物体を写す点が走査線と平行となるよう画像を変換する画像平行化手段とを備え、
相関類似度算出手段は、前記画像平行化手段により変換された画像における走査線対の部分要素間の類似度を求め、
輝度値差分算出手段は、前記画像平行化手段により変換された画像における走査線対の部分要素間の類似度を求める
請求項２または請求項３に記載の画像マッチング装置。
【請求項５】
前記統合類似度判定手段により抽出された類似度評価値に基づいて、走査線対における各点対の接続関係を示す接続行列を作成する接続行列作成手段と、
前記接続行列作成手段により作成された接続行列を用いて、走査線対における視差を確定する対応経路を求める対応経路接続手段とを備えた
請求項２から請求項４のうちのいずれか１項に記載の画像マッチング装置。
【請求項６】
動的計画法を用いてステレオ画像のマッチングを行う画像マッチング方法であって、
画像マッチング手段が、画像対の対応探索時に評価する類似度として相関係数と輝度値差分を併用することによってステレオ画像のマッチングを行う
ことを特徴とする画像マッチング方法。
【請求項７】
画像マッチング手段が備える相関類似度算出手段が、画像対の部分要素間の類似度を、相関類似度として、相互相関によって求め、
画像マッチング手段が備える輝度値差分算出手段が、画像対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求め、
画像マッチング手段が備える統合類似度判定手段が、画像対の部分要素間の類似度評価値を抽出し、前記類似度評価値を抽出する際に、相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする
請求項６記載の画像マッチング方法。
【請求項８】
ステレオ画像記憶手段が、同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶し、
画像平行化手段が、前記ステレオ画像記憶手段に記憶されたステレオ画像に対して、それぞれの画面上で同一物体を写す点が走査線と平行となるよう画像を変換し、
相関類似度算出手段が、前記画像平行化手段により変換された画像の走査線対の部分要素間の類似度を求め、
輝度値差分算出手段が、前記画像平行化手段により変換された画像の走査線対の部分要素間の類似度を求める
請求項７記載の画像マッチング方法。
【請求項９】
接続行列作成手段が、統合類似度判定手段により抽出された類似度評価値に基づいて、走査線対における各点対の接続関係を示す接続行列を作成し、
対応経路接続手段が、前記接続行列作成手段により作成された接続行列を用いて、走査線対における視差を確定する対応経路を求める
請求項７または請求項８に記載の画像マッチング方法。
【請求項１０】
動的計画法を用いてステレオ画像のマッチングを行うコンピュータに搭載される画像マッチングプログラムであって、
前記コンピュータに、
画像対の対応探索時に評価する類似度として相関係数と輝度値差分を併用することによってステレオ画像のマッチングを行う処理
を実行させるための画像マッチングプログラム。
【請求項１１】
動的計画法を用いてステレオ画像のマッチングを行うコンピュータに搭載される画像マッチングプログラムであって、
前記コンピュータに、
画像対の部分要素間の類似度を、相関類似度として、相互相関によって求める処理、
画像対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求める処理、および
画像対の部分要素間の類似度評価値を抽出し、前記類似度評価値を抽出する際に、相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする処理
を実行させるための画像マッチングプログラム。
【請求項１２】
動的計画法を用いてステレオ画像のマッチングを行うコンピュータであって、同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶するステレオ画像記憶手段を備えたコンピュータに搭載される画像マッチングプログラムであって、
前記コンピュータに、
記憶されたステレオ画像に対して、それぞれの画面上で同一物体を写す点が走査線と平行となるよう画像を変換する処理、
変換された画像の走査線対の部分要素間の類似度を、相関類似度として、相互相関によって求める処理、
変換された画像の走査線対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求める処理、
走査線対の部分要素間の類似度評価値を抽出し、前記類似度評価値を抽出する際に、前記相関類似度が所定の評価値に満たない場合であって、前記輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする処理、
抽出された類似度評価値に基づいて、走査線対における各点対の接続関係を示す接続行列を作成する処理、および
前記接続行列を用いて、走査線対における視差を確定する対応経路を求める処理
を実行させるための画像マッチングプログラム。
【請求項１】
動的計画法を用いてステレオ画像のマッチングを行う画像マッチング装置であって、
画像対の対応探索時に評価する類似度として相関係数と輝度値差分を併用することによってステレオ画像のマッチングを行う画像マッチング手段を備えた
ことを特徴とする画像マッチング装置。
【請求項２】
画像マッチング手段は、
画像対の部分要素間の類似度を、相関類似度として、相互相関によって求める相関類似度算出手段と、
画像対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求める輝度値差分類似度算出手段と、
画像対の部分要素間の類似度評価値を抽出し、前記類似度評価値を抽出する際に、前記相関類似度算出手段により求められた相関類似度が所定の評価値に満たない場合であって、前記輝度値差分類似度算出手段により求められた輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする統合類似度判定手段とを備えた
請求項１記載の画像マッチング装置。
【請求項３】
統合類似度判定手段は、
画像対の部分要素間の類似度評価値を抽出する際に、相関類似度算出手段により求められた相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度算出手段により求められた輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を、相関類似度の分布範囲と類似度方向に一致するように変換して前記相関類似度の代替とする
請求項２記載の画像マッチング装置。
【請求項４】
同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶するステレオ画像記憶手段と、
前記ステレオ画像記憶手段に記憶されたステレオ画像に対して、それぞれの画面上で同一物体を写す点が走査線と平行となるよう画像を変換する画像平行化手段とを備え、
相関類似度算出手段は、前記画像平行化手段により変換された画像における走査線対の部分要素間の類似度を求め、
輝度値差分算出手段は、前記画像平行化手段により変換された画像における走査線対の部分要素間の類似度を求める
請求項２または請求項３に記載の画像マッチング装置。
【請求項５】
前記統合類似度判定手段により抽出された類似度評価値に基づいて、走査線対における各点対の接続関係を示す接続行列を作成する接続行列作成手段と、
前記接続行列作成手段により作成された接続行列を用いて、走査線対における視差を確定する対応経路を求める対応経路接続手段とを備えた
請求項２から請求項４のうちのいずれか１項に記載の画像マッチング装置。
【請求項６】
動的計画法を用いてステレオ画像のマッチングを行う画像マッチング方法であって、
画像マッチング手段が、画像対の対応探索時に評価する類似度として相関係数と輝度値差分を併用することによってステレオ画像のマッチングを行う
ことを特徴とする画像マッチング方法。
【請求項７】
画像マッチング手段が備える相関類似度算出手段が、画像対の部分要素間の類似度を、相関類似度として、相互相関によって求め、
画像マッチング手段が備える輝度値差分算出手段が、画像対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求め、
画像マッチング手段が備える統合類似度判定手段が、画像対の部分要素間の類似度評価値を抽出し、前記類似度評価値を抽出する際に、相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする
請求項６記載の画像マッチング方法。
【請求項８】
ステレオ画像記憶手段が、同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶し、
画像平行化手段が、前記ステレオ画像記憶手段に記憶されたステレオ画像に対して、それぞれの画面上で同一物体を写す点が走査線と平行となるよう画像を変換し、
相関類似度算出手段が、前記画像平行化手段により変換された画像の走査線対の部分要素間の類似度を求め、
輝度値差分算出手段が、前記画像平行化手段により変換された画像の走査線対の部分要素間の類似度を求める
請求項７記載の画像マッチング方法。
【請求項９】
接続行列作成手段が、統合類似度判定手段により抽出された類似度評価値に基づいて、走査線対における各点対の接続関係を示す接続行列を作成し、
対応経路接続手段が、前記接続行列作成手段により作成された接続行列を用いて、走査線対における視差を確定する対応経路を求める
請求項７または請求項８に記載の画像マッチング方法。
【請求項１０】
動的計画法を用いてステレオ画像のマッチングを行うコンピュータに搭載される画像マッチングプログラムであって、
前記コンピュータに、
画像対の対応探索時に評価する類似度として相関係数と輝度値差分を併用することによってステレオ画像のマッチングを行う処理
を実行させるための画像マッチングプログラム。
【請求項１１】
動的計画法を用いてステレオ画像のマッチングを行うコンピュータに搭載される画像マッチングプログラムであって、
前記コンピュータに、
画像対の部分要素間の類似度を、相関類似度として、相互相関によって求める処理、
画像対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求める処理、および
画像対の部分要素間の類似度評価値を抽出し、前記類似度評価値を抽出する際に、相関類似度が所定の評価値に満たない場合であって、輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする処理
を実行させるための画像マッチングプログラム。
【請求項１２】
動的計画法を用いてステレオ画像のマッチングを行うコンピュータであって、同一物体を異なる角度から撮影した２枚以上のステレオ画像を記憶するステレオ画像記憶手段を備えたコンピュータに搭載される画像マッチングプログラムであって、
前記コンピュータに、
記憶されたステレオ画像に対して、それぞれの画面上で同一物体を写す点が走査線と平行となるよう画像を変換する処理、
変換された画像の走査線対の部分要素間の類似度を、相関類似度として、相互相関によって求める処理、
変換された画像の走査線対の部分要素間の類似度を、輝度値差分類似度として、輝度値差分によって求める処理、
走査線対の部分要素間の類似度評価値を抽出し、前記類似度評価値を抽出する際に、前記相関類似度が所定の評価値に満たない場合であって、前記輝度値差分類似度が所定の評価値を満たす場合に、輝度値差分類似度を相関類似度の代替とする処理、
抽出された類似度評価値に基づいて、走査線対における各点対の接続関係を示す接続行列を作成する処理、および
前記接続行列を用いて、走査線対における視差を確定する対応経路を求める処理
を実行させるための画像マッチングプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００６−３５０４６５（Ｐ２００６−３５０４６５Ａ）
【公開日】平成１８年１２月２８日（２００６．１２．２８）
【国際特許分類】
【出願番号】特願２００５−１７２７５２（Ｐ２００５−１７２７５２）
【出願日】平成１７年６月１３日（２００５．６．１３）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成１８年１２月２８日（２００６．１２．２８）
【国際特許分類】
【出願日】平成１７年６月１３日（２００５．６．１３）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]