(57)【要約】【課題】  ウィンドウマッチングを行う場合に必要な演算器の個数を、演算時間の増大を抑制しつつ減少させることができるようにする。【解決手段】  画像処理装置は、基準画像１９１の現在の基準領域２２１に対して、１つ前の基準領域２０１の第１列と、１つ前の比較領域２０２−０の第１列２３１−０との第１の積和と、現在の基準領域２２１の第５列と、現在の比較領域２２２−０の第５列２３２−０との第２の積和とを演算する。画像処理装置は、既に演算した、１つ前の基準領域２０１と、マッチング数M=0における１つ前の比較領域２０２−０との積和から、第１の積和を減算し、第２の積和を加算することで、現在の基準領域２２１と、比較領域２２２−０との積和の演算を行う。本発明は、ウィンドウマッチングを利用する画像処理装置に適用可能である。【選択図】図１４
2005084698.tif 000002
【特許請求の範囲】
【請求項１】
第１の画像から基準領域が切り出され、かつ、第２の画像から、前記基準領域と同一のサイズの比較領域が切り出された場合、前記基準領域と前記比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、前記基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、前記比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、前記関数f(a,b)の前記基準領域の画素数分の出力値の総和を演算する画像処理装置において、
前記画像処理装置自身により演算された、前記基準領域と前記比較領域との組に対する前記第１の値を記憶する記憶手段と、
前記記憶手段に、現在の第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、前記第２の基準領域との相対的な位置関係が前記第１の基準領域と現在の第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する前記第１の値が記憶されている場合、これから演算される、前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値と、前記記憶手段に記憶されている、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値との差異に相当する第２の値を演算する第１の演算手段と、
前記記憶手段に記憶された、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値と、前記第１の演算手段により演算された前記第２の値とに基づいて、前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値を演算する第２の演算手段と
を備えることを特徴とする画像処理装置。
【請求項２】
第１の画像から基準領域が切り出され、かつ、第２の画像から、前記基準領域と同一のサイズの比較領域が切り出された場合、前記基準領域と前記比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、前記基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、前記比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、前記関数f(a,b)の前記基準領域の画素数分の出力値の総和を演算する画像処理装置の画像処理方法において、
これから演算される、現在の第１の基準領域と現在の第１の比較領域との組に対する前記第１の値と、前記画像処理装置により既に演算された、前記第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、前記第２の基準領域との相対的な位置関係が前記第１の基準領域と前記第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する前記第１の値との差異に相当する第２の値を演算する第１の演算ステップと、
前記画像処理装置により既に演算された、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値と、前記第１の演算ステップの処理により演算された前記第２の値とに基づいて、前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値を演算する第２の演算ステップと
を含むことを特徴とする画像処理方法。
【請求項３】
第１の画像から基準領域が切り出され、かつ、第２の画像から、前記基準領域と同一のサイズの比較領域が切り出された場合、前記基準領域と前記比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、前記基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、前記比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、前記関数f(a,b)の前記基準領域の画素数分の出力値の総和を演算する画像処理を、コンピュータに実行させるプログラムであって、
前記コンピュータにこれから演算させる、現在の第１の基準領域と現在の第１の比較領域との組に対する前記第１の値と、前記コンピュータに既に演算させた、前記第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、前記第２の基準領域との相対的な位置関係が前記第１の基準領域と前記第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する前記第１の値との差異に相当する第２の値を演算する第１の演算ステップと、
前記コンピュータに既に演算させた、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値と、前記第１の演算ステップの処理により演算された前記第２の値とに基づいて、前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値を演算する第２の演算ステップと
を含むプログラムを記録していることを特徴とする記録媒体。
【請求項４】
第１の画像から基準領域が切り出され、かつ、第２の画像から、前記基準領域と同一のサイズの比較領域が切り出された場合、前記基準領域と前記比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、前記基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、前記比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、前記関数f(a,b)の前記基準領域の画素数分の出力値の総和を演算する画像処理を、コンピュータに実行させるプログラムであって、
前記コンピュータにこれから演算させる、現在の第１の基準領域と現在の第１の比較領域との組に対する前記第１の値と、前記コンピュータに既に演算させた、前記第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、前記第２の基準領域との相対的な位置関係が前記第１の基準領域と前記第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する前記第１の値との差異に相当する第２の値を演算する第１の演算ステップと、
前記コンピュータに既に演算させた、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値と、前記第１の演算ステップの処理により演算された前記第２の値とに基づいて、前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値を演算する第２の演算ステップと
を含むプログラム。
【請求項５】
第１の画像から、N画素×N画素（Nは、前記第１の画像の縦と横の画素数のいずれよりも小さい整数値）からなる基準領域が切り出され、かつ、第２の画像から、N画素×N画素からなる比較領域が切り出された場合、前記基準領域と前記比較領域との組に対する前記第１の値として、所定の関数f(a,b)に対して、変数aとして、前記基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、前記比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、前記関数f(a,b)のN×N個の出力値の総和を演算する電子回路において、
前記電子回路自身により演算された、前記基準領域と前記比較領域との組に対する前記第１の値を記憶するバッファ回路と、
入力された２つの値のそれぞれを、前記関数f(a,b)の前記変数aまたは前記変数bとして、前記関数f(a,b)の出力値を演算するN個の第１の関数演算回路と、N個の前記第１の関数演算回路の出力の総和を演算する第１の加算回路とを有し、前記第１の加算回路からの出力を演算結果として出力する第１の積和演算回路と、
入力された２つの値のそれぞれを、前記関数f(a,b)の前記変数aまたは前記変数bとして、前記関数f(a,b)の出力値を演算するN個の第２の関数演算回路と、N個の前記第２の関数演算回路の出力の総和を演算する第２の加算回路とを有し、前記第２の加算回路からの出力を演算結果として出力する第２の積和演算回路と、
前記バッファ回路の記憶内容、前記第１の積和演算回路の前記演算結果、および、前記第２の積和演算回路の前記演算結果に基づいて所定の演算を行い、その演算の結果を、現在の第１の基準領域と第１の比較領域との組に対する前記第１の値として出力する総合演算回路と
を備えることを特徴とする電子回路。
【請求項６】
前記バッファ回路に、現在の第１の基準領域の位置に対して前記第１の画像の縦または横方向と平行に１画素分だけ離間された位置に配置される第２の基準領域と、前記第２の基準領域との相対的な位置関係が前記第１の基準領域と現在の第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する前記第１の値が記憶されている場合、
前記第１の積和演算手段は、N個の前記第１の関数演算回路のそれぞれに対して、前記変数aとして、前記第１の基準領域を構成する画素のうちの、前記第１の基準領域と前記第２の基準領域との間で共通する前記画素を除く、N個の画素のそれぞれの画素値を入力させるとともに、前記変数bとして、前記第１の比較領域を構成する画素のうちの、対応する場所に位置するN個の画素のそれぞれの画素値を入力させ、前記関数f(a,b)の出力値のそれぞれを演算させ、かつ、前記第１の加算回路に、N個の前記第１の関数演算回路の出力の総和を演算させて、その第１の加算回路の演算結果を第２の値として出力し、
前記第２の積和演算手段は、N個の前記第２の関数演算回路のそれぞれに対して、前記変数aとして、前記第２の基準領域を構成する画素のうちの、前記第１の基準領域と前記第２の基準領域との間で共通する前記画素を除く、N個の画素のそれぞれの画素値を入力させるとともに、前記変数bとして、前記第２の比較領域を構成する画素のうちの、対応する場所に位置するN個の画素のそれぞれの画素値を入力させて、前記関数f(a,b)の出力値のそれぞれを演算させ、かつ、前記第２の加算回路に、N個の前記第２の関数演算回路の出力の総和を演算させて、その第２の加算回路の演算結果を第３の値として出力し、
前記総合演算回路は、前記バッファ回路に記憶された、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値から、前記第２の積和演算回路から出力された前記第３の値を減算し、前記第１の積和演算回路から出力された前記第２の値を加算する演算を行い、その演算の結果を、現在の前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値として出力する
ことを特徴とする請求項５に記載の電子回路。
【請求項７】
前記バッファ回路に、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値が記憶されていない場合、
前記第１の積和演算回路と前記第２の積和演算回路のそれぞれは、さらに、N画素×N画素からなる前記第１の基準領域が、N個の画素からなるN個の小領域に区分され、かつ、N画素×N画素からなる前記第１の比較領域が、前記第１の基準領域のN個の前記小領域の位置のそれぞれに対応する、N個の小領域に区分された場合における、前記第１の基準領域のうちの所定の１つの前記小領域と、前記第１の比較領域のうちの対応する前記小領域とからなるN個の組のうちの、N/2組ずつを処理の対象として分担し、1組毎に、N個の前記第１または前記第２の関数演算回路のそれぞれに対して、前記変数aとして、前記第１の基準領域における前記小領域を構成するN個の画素のそれぞれの画素値を入力させるとともに、前記変数bとして、前記第１の比較領域における前記小領域を構成するN個の画素のそれぞれの画素値を入力させて、前記関数f(a,b)の出力値のそれぞれを演算させ、前記第１または前記第２の加算回路に、N個の前記第１または前記第２の関数演算回路の出力の総和を演算させて、前記第１または前記第２の加算回路のN/2組の演算結果のそれぞれを順次出力し、
前記総合演算回路は、前記第１の積和演算回路から出力されたN/2個の演算結果のそれぞれと、前記第２の積和演算回路から出力されたN/2個の演算結果のそれぞれの全てを加算する演算を行い、その演算の結果を、現在の前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値として出力する
ことを特徴とする請求項６に記載の電子回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置および方法、記録媒体、プログラム、並びに電子回路に関し、特に、ウィンドウマッチングを行う場合に、基準領域（ウィンドウ）と比較領域（検出領域）との相関値の演算に必要な演算器の個数を、演算時間の増大を抑制しつつ減少させることができる、画像処理装置および方法、記録媒体、プログラム、並びに、電子回路に関する。
【背景技術】
【０００２】
近年、所定の実物体の位置（所定の場所からの距離等）を検出するために、ステレオ法（ステレオビジョン手法）と称される手法が利用されている。即ち、ステレオ法とは、２つ以上の方向（異なる視線方向）からカメラで同一対象物（実物体）を撮影して得られる複数の画像間の画素同士を対応付けることで、対応する画素間の視差情報を求め、この視差情報から、カメラから実物体までの距離や、実物体の形状を求める手法である。
【０００３】
具体的には、例えば、いま、２台のカメラが左右に離間して配置されているとする。この場合、左側に配置されたカメラ（以下、左カメラと称する）で所定の実物体を撮影して得られる画像（以下、左画像と称する）と、右側に配置されたカメラ（以下、右カメラと称する）で同一の実物体を撮影して得られる画像（以下、右画像と称する）との間の画素同士を対応付けることで、対応する画素間の視差情報を求めることができる。
【０００４】
詳細には、例えば、左画像のうちの、実物体の一部分を示す所定の第１の点（第１の画素）に対応する、右画像のうちの、実物体のその一部分を示す第２の点（第２の画素）を検出することで、第１の画素と第２の画素とを対応付けることができる。なお、これらの第１の点と第２の点とのそれぞれは、（他方の点に対する）対応点と称されている。
【０００５】
このような対応点を求める代表的な手法として、ウィンドウマッチング手法と称される、特許文献１に示されるような手法が知られている。即ち、特許文献１によると、ウィンドウマッチング手法を利用する画像処理装置は、はじめに、例えば、左画像のうちの、処理の対象として注目する画素（以下、注目画素と称する）を中心とする所定の第１の領域を切り出す。そして、画像処理装置は、その第１の領域を右画像の上に配置させ、所定の方向に順次変移させる。このとき、画像処理装置は、右画像上の第１の領域の変移位置のそれぞれにおいて、第１の領域と、それと重なり合う右画像の第２の領域との一致の度合（相関値）を順次演算していく。そして、画像処理装置は、一致の度合が演算された右画像の領域のうちの、一致の度合が最も高い領域の中心点（中心画素）を、左画像の注目画素に対する、右画像上の対応点（対応画素）として検出する。
【０００６】
なお、以下、注目画素を含む画像、即ち、いまの場合、左画像を、基準画像と適宜称する。また、基準画像から切り出される、注目画素を中心とする第１の領域を、一般的にはウィンドウと称することもあるが、以下においては、基準領域と適宜称する。一方、注目画像に対する対応点が存在する画像（基準領域が配置され、変移されていくことで、対応点が検索される対象の画像）、即ち、いまの場合、右画像を、比較画像と適宜称する。また、比較画像のうちの、基準領域との一致の度合いが演算される第２の領域を、一般的には検出領域と称することもあるが、以下においては、比較領域と適宜称する。
【０００７】
以下、図１を参照して、ウィンドウマッチング手法についてさらに説明する。
【０００８】
図１において、位置検出の対象とされている実物体１は、図示せぬ左カメラ（ただし、図１には、その光学中心点２が図示されている）と、図示せぬ右カメラ（ただし、図１には、その光学中心点３が図示されている）とのそれぞれにより撮影される。即ち、左カメラからは、実物体１の左画像（基準画像）１１が出力され、右カメラからは、実物体１の右画像（比較画像）１２が出力される。
【０００９】
この左画像１１の注目画素の対応点は、右画像１２のうちの、所定の方向に水平な直線（このような直線は、エピポーララインと一般的に称されている）上に存在することが知られている。即ち、図１に図示せぬ画像処理装置は、左画像１１の基準領域との一致の度合いを演算する、右画像１２の比較領域として、その右画像１２におけるエピポーラライン上の点を中心とする領域だけを選択すればよいことになる。即ち、画像処理装置は、基準領域の中心点（注目画素）を、右画像１２のエピポーラライン上に沿って変移させればよいことになる。
【００１０】
しかしながら、エピポーララインの方向は、右画像１２の水平方向（画素が連続して並ぶ横方向）とは異なる方向となることが多く、この場合、画像処理装置は、基準領域をエピポーララインに平行な方向に変移させるためには、多くの演算が必要となるとともに、その演算結果の誤差（デジタル誤差）も大きくなってしまう、といった課題がある。
【００１１】
そこで、この課題を解決するために、図１の矢印３１−１と矢印３１−２で示されるように、左画像１１と右画像１２のそれぞれを、左カメラの光学中心点２と右カメラの光学中心点３とを結ぶ直線と平行な左画像２１と右画像２２のそれぞれに射影変換する手法が知られている。なお、このような手法は、レクティフィケーション（平行化）と称されている。
【００１２】
この手法が適用されて、レクティフィケーション（平行化）された左画像２１と右画像２２においては、左画像２１の注目画素の理論上の対応点は、右画像２２のうちの、所定の水平ライン（注目画素が配置されている左画像２１の水平ラインに対応する水平ライン）上に存在することになる。即ち、この右画像２２の水平ラインが、エピポーララインとなる。
【００１３】
従って、画像処理装置は、左画像１１と右画像２２のそれぞれを、レクティフィケーション（平行化）により、左画像２１と右画像２２のそれぞれに変換させ、その後、左画像２１と右画像２２とを重ねてから（即ち、基準領域の中心点（注目画素）をエピポーラライン上に配置させてから）、矢印３２に示されるように、左画像２１を水平方向に動かしていくことで（即ち、右画像２２上で、左画像２１の注目画素を中心とする基準領域を、エピポーララインと平行に順次変移させていくことで）、基準領域と比較領域との一致の度合の演算を容易に行うことができ、かつ、その演算結果の誤差（デジタル誤差）も小さくなる。
【００１４】
ところで、この場合、画像処理装置は、左画像２１の基準領域として、図２に示されるような領域４１を切り出すことが多い。即ち、図２は、左画像２１の基準領域と、右画像２２の比較領域との例を示している。
【００１５】
図２の左画像２１において、水平方向（横方向）は、画素が連続して並ぶ空間方向xaとされており、垂直方向（縦方向）は、空間方向xaと垂直な空間方向yaとされている。そして、左画像２１の画素を、長さが１の正方形であるとして、左画像２１の図２中左上端（正確には、左上端から、水平方向xaと垂直方向yaとのそれぞれの方向に、画素の一辺の長さの１／２だけ離間された位置）を原点(0,0)とする座標系(xa,ya)が定義されている。
【００１６】
即ち、例えば、図２の左画像２１において、一番左から水平方向xaにX番目（Xは、左画像２１の、水平方向xaに並ぶ画素の画素数以下の整数値）で、一番上から垂直方向yaにY番目（Yは、左画像２１の、垂直方向yaに並ぶ画素の画素数以下の整数値）の画素４１−０の中心の位置は、この座標系(xa,ya)では、座標（X,Y）で表される。
【００１７】
同様に、図２の右画像２２において、水平方向（横方向）は、画素が連続して並ぶ空間方向xbとされており、垂直方向（縦方向）は、空間方向xbと垂直な空間方向ybとされている。そして、右画像２２の画素を、長さが１の正方形であるとして、右画像２２の図２中左上端（正確には、左上端から、水平方向xbと垂直方向ybとのそれぞれの方向に、画素の一辺の長さの１／２だけ離間された位置）を原点(0,0)とする座標系(xb,yb)が定義されている。
【００１８】
即ち、例えば、図２の右画像２２において、一番左から水平方向xbにX＋M番目（X＋Mは、右画像２２の、水平方向xbに並ぶ画素の画素数以下の整数値）で、一番上から垂直方向ybにY番目（Yは、右画像２２の、垂直方向ybに並ぶ画素の画素数以下の整数値）の画素４２−０の中心の位置は、この座標系(xb,yb)では、座標（X+M,Y）で表される。
【００１９】
なお、以下、画素の中心の位置（座標）を、単に画素の位置（座標）と称する。
【００２０】
例えば、いま、画像処理装置は、左画像２１の注目画素として、座標系(xa,ya)における座標（X+2,Y+2）に配置された画素４１−１２を設定したとする。
【００２１】
この場合、画像処理装置は、左画像２１の基準領域として、例えば、注目画素４１−１２を中心とする、一辺がＮ個（Ｎは、左画像２１の水平方向xaに並ぶ画素の画素数と、垂直方向yaに並ぶ画素の画素数のいずれよりも小さい整数値であって、図２の例では５個とされている）の画素からなる正方形状の領域４１を切り出す。
【００２２】
なお、以下、水平方向にｏ個（ｏは、任意の整数値）の画素が並び、かつ、垂直方向にｐ個（ｐは、任意の整数値）の画素が並んで構成される（即ち、ｏ×ｐ個の画素から構成される）画像（領域）を、ｏ×ｐの画像（領域）と称する。
【００２３】
即ち、左画像２１の基準領域として、注目画素４１−１２を中心とする、Ｎ×Ｎ（図２の例では、５×５）の領域４１が切り出される。
【００２４】
このとき、左画像２１の注目画素４１−１２のya座標は（Y+2）とされるので、右画像２２におけるエピポーララインは、上述したように、yb座標が（Y+2）の水平ライン（水平方向xbに平行なライン）２３とされる。
【００２５】
そこで、画像処理装置は、左画像２１の注目画素４１−１２の対応点を検出するために、左画像２１の基準領域４１と、その中心がエピポーラライン２３上に位置する各画素のそれぞれを中心とする、N×Nの比較領域のそれぞれとの一致の度合を順次演算していく。
【００２６】
具体的には、例えば、画像処理装置は、初期状態として、左画像２１と右画像２２とをあたかも重ね合わせた状態にした後、基準領域４１を、水平方向（空間方向xb＝空間方向xa）と平行に、長さ１（＝画素の長さ）ずつ順次変移させていくとする。
【００２７】
この場合、例えば、右画像２２上で、基準領域４１が水平方向xbにM回変移されたとすると、基準領域４１の中心点（注目画素４１−１２）は、座標系(xb,yb)における座標（X+2+M，Y+2）に配置される右画像２２の画素４２−１２と重なる。そこで、画像処理装置は、その画素４２−１２を中心とする、５×５の領域４２を、その時点での比較領域として設定し、基準領域４１と比較領域４２との一致の度合（即ち、注目画素４１−１２と画素４２−１２との一致の度合）を演算する。
【００２８】
このとき、画像処理装置は、基準領域４１と比較領域４２との一致の度合（即ち、相関値s）を演算するために、一般的に、式（１）に示される正規化相関関数、式（２）に示されるＳＳＤ(Sum of Squared Difference)と称される評価式、または、式（３）に示されるＳＡＤ(Sum of Absolute Difference)と称される評価式を利用することが多い。
【００２９】
【数１】
2005084698.tif 000003
・・・（１）
【数２】
2005084698.tif 000004
・・・（２）
【数３】
2005084698.tif 000005
・・・（３）
【００３０】
式（１）乃至式（３）において、iは、NxNの領域（いまの場合、図２の基準領域４１と比較領域４２）の各画素のそれぞれに、所定の規則に従って付与された番号を示している。具体的には、例えば、図２の例では、図中左上端の画素の番号が０とされて、垂直方向（空間方向yaまたは空間方向yb）に上から下に向かって、各画素のそれぞれに番号が順次付与され、図中一番下の画素（ya座標またはyb座標が(Y+4)の画素）に番号が付されると、いままで番号が付されていた列の右隣の列の各画素のそれぞれに対して、上述した順番に番号が付されていく。
【００３１】
また、aiは、図２に示されるように、左画像２１の基準領域４１のうちの、番号ｉが付された画素の画素値を示している。具体的には、例えば、a0は画素４１−０の画素値を、a12は注目画素４１−１２の画素値を、それぞれ示している。同様に、biは、図２に示されるように、右画像２２の比較領域４２のうちの、番号ｉが付された画素の画素値を示している。具体的には、例えば、b0は画素４２−０の画素値を、b12は画素４２−１２の画素値を、それぞれ示している。
【００３２】
従来、画像処理装置のうちの相関値を演算する回路、例えば、式（１）に示される正規化相関関数を演算する回路は、図３に示されるように構成されている。
【００３３】
即ち、図３に示されるように、式（１）に示される正規化相関関数を演算する従来の回路は、左右画像メモリ５１、ΣAB乗算器５２、ΣA2乗算器５３、ΣB2乗算器５４、乗算器５５、除算器５６、および、S2正規化相関値メモリ５７から構成される。
【００３４】
左右画像メモリ５１は、左画像２１と右画像２２（図２）のデータ（即ち、各画素値）を保存する。
【００３５】
ΣAB乗算器５２は式（１）の右辺の分子を、ΣA2乗算器５３は式（１）の右辺の分母のうちのai(iは、図２の場合、０乃至２４)の自乗の総和を、ΣB2乗算器５４は式（１）の右辺の分母のうちのbi(iは、図２の場合、０乃至２４)の自乗の総和を、それぞれ演算する。
【００３６】
乗算器５５は、ΣA2乗算器５３の演算結果と、ΣB2乗算器５４の演算結果とを乗算する。即ち、乗算器５５は、式（１）の右辺の分母のルートの中を演算する。
【００３７】
除算器５６は、ΣAB乗算器５２の演算結果から、乗算器５５の演算結果のルートを除算する。即ち、除算器５６は、式（１）の右辺の分子から分母を除算する。
【００３８】
S2正規化相関値メモリ５７は、除算器５６の演算結果（式（１）の演算結果）、即ち、左画像２１の基準領域４１と、右画像２２の比較領域（例えば、図２の例では、比較領域４２）との相関値sを保存する。
【特許文献１】特開２００１−２６４０３３号公報
【発明の開示】
【発明が解決しようとする課題】
【００３９】
しかしながら、従来、ΣAB乗算器５２、ΣA2乗算器５３、および、ΣB2乗算器５４のそれぞれは、所定の１つのi（図２の場合、iは、０乃至２４のうちのいずれかの値）に対する、ai×bi、ai×ai、または、bi×biを演算する乗算器を、N×N個有する必要があり、その結果、左画像２１の基準領域のサイズが大きくなっていくと（即ち、Nが大きくなっていくと）、必要となる乗算器の数が膨大となる、といった課題があった。
【００４０】
具体的には、例えば、画像処理装置が、図２の左画像２１における、５×５の基準領域４１と、右画像２２における、５×５の比較領域４２との組に対する正規化相関関数を演算する場合、ΣAB乗算器５２は、例えば、図４に示されるように構成される。
【００４１】
図４に示されるように、ΣAB乗算器５２には、左画像２１の基準領域４１内の所定の画素の画素値aiを抽出する抽出回路６１、右画像２２の比較領域４２内の所定の画素の画素値biを抽出する抽出回路６２、所定の１つのiに対するai×biを演算する乗算器６３、および、ラインレジスタ（１つのDフリップフロップ回路）６４が、それぞれ所定の個数（例えば、乗算器６３は、N×N個＝５×５個）設けられている。
【００４２】
即ち、所定の１つの乗算器６３には、対応する抽出回路６１から１つの画素値aiが入力されるとともに、対応する抽出回路６２またはシフトレジスタ６４から１つの画素値biが入力されるので、その乗算器６３は、これらの２つの入力値の積（＝ai×bi）を演算し、その演算結果を出力する。
【００４３】
ところで、上述したように、基準領域４１は、右画像２２上を水平方向xbに沿って毎回１の長さ（画素の長さ）だけ右側に変移していく。
【００４４】
以下、基準領域４１が変移されて、基準領域４１と、その時点で基準領域４１と重なる比較領域４２との相関価が演算される処理を、マッチングと称する。また、その時点の基準領域４３の変移数（スライド数）Mを、以下、マッチング数Mとされる。なお、最初のマッチングにおいては、基準領域４１はまだ変移されていないので、マッチング数M、即ち、スライド数M=0となる。即ち、マッチングの回数は、M+1で表されることになる。
【００４５】
従って、マッチング数Mにおいて、画素値bi（ただし、ここでは、iは、０乃至１９のうちのいずれか）として使用された値は、直後のマッチング数M+1においては、（基準領域４１が、１つ右側に変移された次の処理においては）、今度は、画素値bi-5として利用されることになる。そこで、マッチング数Mにおいて、ai×biを演算する乗算器６３に画素値biとして入力される値は、その乗算器６３の図中右斜め上のシフトレジスタ６４にも入力され、保持される。そして、次のマッチング数M+1においては（次のクロックでは）、そのシフトレジスタ６４は、保持していた値（直前のクロックにおいて、即ち、マッチング数Mにおいて、画素値biとされていた値）を、今度は、画素値bi-5として、ai-5×bi-5を演算する乗算器６３（ai×biの乗算器６３の図中右隣の乗算器６３）に入力させる。
【００４６】
ΣAB乗算器５２にはまた、所定の５つの乗算器６３（図４中、所定の１列分の乗算器６３）の演算結果の総和を演算する加算器５５が５個（＝N個）設けられ、また、それらの５個の加算器５５の演算結果の総和（即ち、５×５個（＝N×N個）の乗算器６３の演算結果の総和）を演算する加算器５６が１個設けられている。
【００４７】
５個の加算器５５のそれぞれは、マッチング数Mにおいては、基準領域４１の所定の列の各画素（即ち、xa座標（X+L（ただし、Lは、０乃至４のうちのいずれかの値））に位置する各画素）のそれぞれと、比較領域４２の対応する列の各画素（即ち、xb座標（X+L＋M）に位置する各画素）のそれぞれとの積が、対応する５つの乗算器６３より供給されてくるので、それらの総和を演算する。
【００４８】
即ち、５個の加算器５５のそれぞれは、基準領域４１の所定の列に対応する、ai×biの総和を演算する。
【００４９】
従って、加算器５６は、５個の加算器５５のそれぞれの演算結果（基準領域４１の各列のそれぞれにおける、ai×biの総和）の総和を演算し、その演算結果を、式（１）の右辺の分子の値であるとして出力する。
【００５０】
このように、画像処理装置が、図２の左画像２１における、５×５の基準領域４１と、右画像２２における、５×５の比較領域４２との組に対する正規化相関関数を演算する場合、ΣAB乗算器５２は、５×５個の乗算器６３が必要となる、といった課題があった。
【００５１】
なお、従来の画像処理装置では、相関値を演算する評価式として、式（２）に示されるＳＳＤ、または、式（３）に示されるＳＡＤを利用する場合であっても、所定の１つのi（図２の場合、iは、０乃至２４のうちのいずれかの値）に対する、ai-biの自乗または絶対値を演算する演算器を、N×N個有する必要がある、ということには変わりは無い。即ち、従来の画像処理装置では、相関値を演算する評価式として、式（２）に示されるＳＳＤ、または、式（３）に示されるＳＡＤを利用する場合であっても、上述した課題（式（１）の正規化相関関数を利用する場合の課題）と、全く同様の課題が発生する。
【００５２】
本発明は、このような状況に鑑みてなされたものであり、ウィンドウマッチングを行う場合に、基準領域（ウィンドウ）と比較領域（検出領域）の相関値の演算に必要な演算器の個数を、演算時間の増大を抑制しつつ減少させることができるようにするものである。
【課題を解決するための手段】
【００５３】
本発明の画像処理装置は、第１の画像から基準領域が切り出され、かつ、第２の画像から、基準領域と同一のサイズの比較領域が切り出された場合、基準領域と比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、関数f(a,b)の基準領域の画素数分の出力値の総和を演算する画像処理装置において、画像処理装置自身により演算された、基準領域と比較領域との組に対する第１の値を記憶する記憶手段と、記憶手段に、現在の第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、第２の基準領域との相対的な位置関係が第１の基準領域と現在の第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する第１の値が記憶されている場合、これから演算される、第１の基準領域と第１の比較領域との組に対する第１の値と、記憶手段に記憶されている、第２の基準領域と第２の比較領域との組に対する第１の値との差異に相当する第２の値を演算する第１の演算手段と、記憶手段に記憶された、第２の基準領域と第２の比較領域との組に対する第１の値と、第１の演算手段により演算された第２の値とに基づいて、第１の基準領域と第１の比較領域との組に対する第１の値を演算する第２の演算手段とを備えることを特徴とする。
【００５４】
本発明の画像処理方法は、第１の画像から基準領域が切り出され、かつ、第２の画像から、基準領域と同一のサイズの比較領域が切り出された場合、基準領域と比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、関数f(a,b)の基準領域の画素数分の出力値の総和である第１の値を演算する画像処理装置の画像処理方法であって、これから演算される、現在の第１の基準領域と現在の第１の比較領域との組に対する第１の値と、画像処理装置により既に演算された、第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、第２の基準領域との相対的な位置関係が第１の基準領域と第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する第１の値との差異に相当する第２の値を演算する第１の演算ステップと、画像処理装置により既に演算された、第２の基準領域と第２の比較領域との組に対する第１の値と、第１の演算ステップの処理により演算された第２の値とに基づいて、第１の基準領域と第１の比較領域との組に対する第１の値を演算する第２の演算ステップとを含むことを特徴とする。
【００５５】
本発明の記録媒体のプログラムは、第１の画像から基準領域が切り出され、かつ、第２の画像から、基準領域と同一のサイズの比較領域が切り出された場合、基準領域と比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、関数f(a,b)の基準領域の画素数分の出力値の総和である第１の値を演算する画像処理をコンピュータに実行させるプログラムであって、これから演算される、現在の第１の基準領域と現在の第１の比較領域との組に対する第１の値と、画像処理装置により既に演算された、第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、第２の基準領域との相対的な位置関係が第１の基準領域と第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する第１の値との差異に相当する第２の値を演算する第１の演算ステップと、画像処理装置により既に演算された、第２の基準領域と第２の比較領域との組に対する第１の値と、第１の演算ステップの処理により演算された第２の値とに基づいて、第１の基準領域と第１の比較領域との組に対する第１の値を演算する第２の演算ステップとを含むことを特徴とする。
【００５６】
本発明のプログラムは、第１の画像から基準領域が切り出され、かつ、第２の画像から、基準領域と同一のサイズの比較領域が切り出された場合、基準領域と比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、関数f(a,b)の基準領域の画素数分の出力値の総和である第１の値を演算する画像処理をコンピュータに実行させるプログラムであって、これから演算される、現在の第１の基準領域と現在の第１の比較領域との組に対する第１の値と、画像処理装置により既に演算された、第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、第２の基準領域との相対的な位置関係が第１の基準領域と第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する第１の値との差異に相当する第２の値を演算する第１の演算ステップと、画像処理装置により既に演算された、第２の基準領域と第２の比較領域との組に対する第１の値と、第１の演算ステップの処理により演算された第２の値とに基づいて、第１の基準領域と第１の比較領域との組に対する第１の値を演算する第２の演算ステップとを含むことを特徴とする。
【００５７】
本発明の画像処理装置および方法、記録媒体、並びにプログラムにおいては、第１の画像から基準領域が切り出され、かつ、第２の画像から、基準領域と同一のサイズの比較領域が切り出された場合、基準領域と比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、関数f(a,b)の基準領域の画素数分の出力値の総和が演算される。
【００５８】
詳細には、これから演算される、現在の第１の基準領域と現在の第１の比較領域との組に対する第１の値と、既に演算された、第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、第２の基準領域との相対的な位置関係が第１の基準領域と第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する第１の値との差異に相当する第２の値が演算され、既に演算された、第２の基準領域と第２の比較領域との組に対する第１の値と、演算された第２の値とに基づいて、第１の基準領域と第１の比較領域との組に対する第１の値が演算される。
【００５９】
本発明の電子回路は、第１の画像から、N画素×N画素（Nは、前記第１の画像の縦と横の画素数よりも小さい整数値）からなる基準領域が切り出され、かつ、第２の画像から、N画素×N画素からなる比較領域が切り出された場合、基準領域と比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、関数f(a,b)のN×N個の出力値の総和である第１の値を演算する電子回路であって、電子回路自身により演算された、基準領域と比較領域との組に対する第１の値を記憶するバッファ回路と、入力された２つの値のそれぞれを、関数f(a,b)の変数aまたは変数bとして、関数f(a,b)の出力値を演算するN個の第１の関数演算回路と、N個の第１の関数演算回路の出力の総和を演算する第１の加算回路とを有し、第１の加算回路からの出力を演算結果として出力する第１の積和演算回路と、入力された２つの値のそれぞれを、関数f(a,b)の変数aまたは変数bとして、関数f(a,b)の出力値を演算するN個の第２の関数演算回路と、N個の第２の関数演算回路の出力の総和を演算する第２の加算回路とを有し、第２の加算回路からの出力を演算結果として出力する第２の積和演算回路と、バッファ回路の記憶内容、第１の積和演算回路の演算結果、および、第２の積和演算回路の演算結果に基づいて、所定の演算を行い、その演算の結果を、現在の第１の基準領域と、現在の第１の比較領域との組に対する第１の値として出力する総合演算回路とを備えることを特徴とする。
【００６０】
さらに、バッファ回路に、現在の第１の基準領域の位置に対して第１の画像の縦または横方向と平行に１画素分だけ離間された位置に配置される第２の基準領域と、第２の基準領域との相対的な位置関係が第１の基準領域と現在の第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する第１の値が記憶されている場合、第１の積和演算手段は、N個の第１の関数演算回路のそれぞれに対して、変数aとして、第１の基準領域を構成する画素のうちの、第１の基準領域と第２の基準領域との間で共通する画素を除く、N個の画素のそれぞれの画素値を入力させるとともに、変数bとして、第１の比較領域を構成する画素のうちの、対応する場所に位置するN個の画素のそれぞれの画素値を入力させて、関数f(a,b)の出力値のそれぞれを演算させ、第１の加算回路に、N個の第１の加算回路の出力の総和を演算させて、第１の加算回路からの演算結果を第２の値として出力し、第２の積和演算手段は、N個の第２の関数演算回路のそれぞれに対して、変数aとして、第２の基準領域を構成する画素のうちの、第１の基準領域と第２の基準領域との間で共通する画素を除く、N個の画素のそれぞれの画素値を入力させるとともに、変数bとして、第２の比較領域を構成する画素のうちの、対応する場所に位置するN個の画素のそれぞれの画素値を入力させて、関数f(a,b)の出力値のそれぞれを演算させ、第２の加算回路に、N個の第２の関数演算回路の出力の総和を演算させて、第２の加算回路の演算結果を第３の値として出力し、総合演算回路は、バッファ回路に記憶された、第２の基準領域と第２の比較領域との組に対する第１の値から、第１の積和演算回路から出力された第２の値を加算し、第２の積和演算回路から出力された第３の値を減算する演算を行い、その演算の結果を、現在の第１の基準領域と第１の比較領域との組に対する第１の値として出力するようにすることができる。
【００６１】
また、バッファ回路の記憶内容として、第２の基準領域と第２の比較領域との組に対する第１の値が存在しない場合、第１の積和演算回路と第２の積和演算回路のそれぞれは、さらに、N画素×N画素からなる第１の基準領域が、N個の画素からなるN個の小領域に区分され、かつ、N画素×N画素からなる第１の比較領域が、第１の基準領域のN個の小領域の位置のそれぞれに対応する、N個の小領域に区分された場合における、第１の基準領域のうちの所定の１つの小領域と、第１の比較領域のうちの対応する前記小領域とからなるN個の組のうちの、N/2組ずつを処理の対象として分担し、1組毎に、N個の第１または第２の関数演算回路のそれぞれに対して、変数aとて、第１の基準領域における小領域を構成するN個の画素のそれぞれの画素値を入力させるとともに、変数bとして、第１の比較領域における小領域を構成するN個の画素のそれぞれの画素値を入力させて、関数f(a,b)の出力値のそれぞれを演算させ、第１または第２の加算回路に、N個の第１または第２の関数演算回路の総和を演算させ、第１または第２の加算回路のN/2組の演算結果のそれぞれを順次出力し、総合演算回路は、第１の積和演算回路から出力されたN/2個の演算結果のそれぞれと、第２の積和演算回路から出力されたN/2個の演算結果のそれぞれとを、全て加算する演算を行い、その演算の結果を、現在の第１の基準領域と第１の比較領域との組に対する前記第１の値として出力するようにすることができる。
【００６２】
本発明の電子回路においては、第１の画像から、N画素×N画素（Nは、前記第１の画像の縦と横の画素数よりも小さい整数値）からなる基準領域が切り出され、かつ、第２の画像から、N画素×N画素からなる比較領域が切り出された場合、基準領域と比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、関数f(a,b)のN×N個の出力値の総和である第１の値が演算される。
【００６３】
詳細には、本発明の電子回路自身により演算された、基準領域と比較領域との組に対する第１の値を記憶するバッファ回路と、入力された２つの値のそれぞれを、関数f(a,b)の変数aまたは変数bとして、関数f(a,b)の出力値を演算するN個の第１の関数演算回路と、N個の第１の関数演算回路の出力の総和を演算する第１の加算回路とを有し、第１の加算回路からの出力を演算結果として出力する第１の積和演算回路と、入力された２つの値のそれぞれを、関数f(a,b)の変数aまたは変数bとして、関数f(a,b)の出力値を演算するN個の第２の関数演算回路と、N個の第２の関数演算回路の出力の総和を演算する第２の加算回路とを有し、第２の加算回路からの出力を演算結果として出力する第２の積和演算回路と、バッファ回路の記憶内容、第１の積和演算回路の演算結果、および、第２の積和演算回路の演算結果に基づいて、所定の演算を行い、その演算の結果を、現在の第１の基準領域と、現在の第１の比較領域との組に対する第１の値として出力する総合演算回路とが設けられており、最終的に、第１の基準領域と第１の比較領域との組に対する第１の値が外部に出力される。
【発明の効果】
【００６４】
以上のごとく、本発明によれば、ウィンドウマッチングを行う場合に、基準領域（ウィンドウ）と、それに対応する比較領域（検出領域）との相関値の演算、または、その演算に必須な値の演算を行うことができる。特に、そのような演算にとって必要な演算器の個数を、演算時間の増大を抑制しつつ減少させることができる。
【発明を実施するための最良の形態】
【００６５】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００６６】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【００６７】
請求項１に記載の画像処理装置（図１２の画像マッチング部７７、或いは、そのうちの、ΣAB乗算器１２２と捉えてもよい）は、第１の画像（例えば、図５の左カメラ７１から出力され、左画像変換部７２を介して供給された、図１４の左画像１９１）から基準領域（例えば、図１４の基準領域２２１）が切り出され、かつ、第２の画像（例えば、図５の右カメラ７４から出力され、右画像変換部７５を介して供給された、図１４の右画像１９２）から、前記基準領域と同一のサイズ（例えば、図１４に示されるように、５画素×５画素）の比較領域（例えば、図１４の比較領域２２２−０）が切り出された場合、前記基準領域と前記比較領との組に対する第１の値（例えば、式（１）の右辺の分子）として、所定の関数f(a,b)（例えば、式（４）の右辺のΣの中、即ち、a(i,j)×b(i+M,j)）に対して、変数a（例えば、式（４）のa(i,j)）として、前記基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数b（例えば、式（４）のb(i+M,j)）として、前記比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、前記関数f(a,b)の前記基準領域の画素数分の出力値の総和（例えば、式（４）の右辺）であるを演算する画像処理装置であって、前記画像処理装置自身により演算された、前記基準領域と前記比較領域との組に対する前記第１の値を記憶する記憶手段（例えば、図１６のバッファ３２６）と、前記記憶手段に、現在の第１の基準領域（例えば、図１４の基準領域２２１）と共通する画素を少なくとも含む第２の基準領域（例えば、図１４の基準領域２０１）と、前記第２の基準領域との相対的な位置関係が前記第１の基準領域と現在の第１の比較領域（例えば、図１４の比較領域２２２−０）との相対的な位置関係と同一の第２の比較領域（例えば、図１４の比較領域２０２−０）との組に対する前記第１の値が記憶されている場合、これから演算される、前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値と、前記記憶手段に記憶されている、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値との差異（例えば、図１４において、１つ前の比較領域２０２−０のうちの、第１列（小領域）２３１−０に対応する部分の演算成分、および、現在の比較領域２２２−０のうちの、第５列（小領域）２３２−０に対応する部分の演算成分）に相当する第２の値を演算する第１の演算手段（例えば、図１６の列積和演算回路３５１および列積和演算回路３５２）と、前記記憶手段に記憶された、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値と、前記第１の演算手段により演算された前記第２の値とに基づいて、前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値を演算する第２の演算手段（例えば、図１６の総合演算回路３５３）とを備えることを特徴とする。
【００６８】
請求項２に記載の画像処理方法は、第１の画像から基準領域が切り出され、かつ、第２の画像から、前記基準領域と同一のサイズの比較領域が切り出された場合、前記基準領域と前記比較領域との組に対する第１の値として、所定の関数f(a,b)に対して、変数aとして、前記基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数bとして、前記比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、前記比較領域を構成する画素の総数と同一の数の前記関数f(a,b)の出力値の総和を演算する画像処理装置の画像処理方法（例えば、図１２の画像マッチング部７７、或いは、そのうちの、ΣAB乗算器１２２が実行する図２１のΣAB乗算器の処理に対応する方法）であって、これから演算される、現在の第１の基準領域と現在の第１の比較領域との組に対する前記第１の値と、前記画像処理装置により既に演算された、前記第１の基準領域と共通する画素を少なくとも含む第２の基準領域と、前記第２の基準領域との相対的な位置関係が前記第１の基準領域と前記第１の比較領域との相対的な位置関係と同一の第２の比較領域との組に対する前記第１の値との差異に相当する第２の値を演算する第１の演算ステップ（例えば、図２１のステップＳ３０、即ち、図２３のマッチング処理用のΣAB演算処理のうちの、ステップＳ７１とＳ７２）と、前記画像処理装置により既に演算された、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値と、前記第１の演算手段により演算された前記第２の値とに基づいて、前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値を演算する第２の演算ステップ（例えば、図２１のステップＳ３０、即ち、図２３のマッチング処理用のΣAB演算処理のうちの、ステップＳ７３とＳ７４）とを含むことを特徴とする。
【００６９】
請求項５に記載の電子回路（例えば、図１６のΣAB乗算器１２２）は、第１の画像（例えば、図５の左カメラ７１から出力され、左画像変換部７２を介して供給された、図１４の左画像１９１）から、N画素×N画素（Nは、前記第１の画像の縦と横の画素数よりも小さい整数値）からなる基準領域（例えば、N=５、即ち、５画素×５画素からなる、図１４の基準領域２２１）が切り出され、かつ、第２の画像（例えば、図５の右カメラ７４から出力され、右画像変換部７５を介して供給された、図１４の右画像１９２）から、N画素×N画素からなる比較領域（例えば、図１４の比較領域２２２−０）が切り出された場合、前記基準領域と前記比較領域との組に対する第１の値（例えば、式（１）の右辺の分子）として、所定の関数f(a,b) （例えば、式（４）の右辺のΣの中、即ち、a(i,j)×b(i+M,j)）に対して、変数a（例えば、式（４）のa(i,j)）として、前記基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数b（例えば、式（４）のb(i+M,j)）として、前記比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、前記関数f(a,b)のN×N個の出力値の総和（例えば、式（４）の右辺）である第１の値を演算する電子回路であって、前記電子回路自身により演算された、前記基準領域と前記比較領域との組に対する前記第１の値を記憶するバッファ回路（例えば、図１６のバッファ３２６）と、入力された２つの値のそれぞれを、前記関数f(a,b)の前記変数aまたは前記変数bとして、前記関数f(a,b)の出力値を演算するN個の第１の関数演算回路（例えば、図１６の、「Mul」として示される、５（＝Ｎ）個の乗算器３０１−１１乃至３０１−５１）と、N個の前記第１の関数演算回路の出力の総和を演算する第１の加算回路（例えば、図１６の、「Add」と記述された加算器３２１−１）とを有し、前記第１の加算回路からの出力を演算結果として出力する第１の積和演算回路（例えば、図１６の列積和演算回路３５１）と、入力された２つの値のそれぞれを、前記関数f(a,b)の前記変数aまたは前記変数bとして、前記関数f(a,b)の出力値を演算するN個の前記第２の関数演算回路（例えば、図１６の、「Mul」として示される、５（＝Ｎ）個の乗算器３０１−１２乃至３０１−５２）と、N個の前記第２の関数演算回路の出力の総和を演算する第２の加算回路（例えば、図１６の、「Add」と記述された加算器３２１−１）とを有し、前記第２の加算回路からの出力を演算結果として出力する第２の積和演算回路（例えば、図１６の列積和演算回路３５２）と、前記バッファ回路の記憶内容、前記第１の積和演算回路の前記演算結果、および、前記第２の積和演算回路の前記演算結果に基づいて、所定の演算を行い、その演算の結果を、現在の第１の基準領域と、現在の第１の比較領域との組に対する前記第１の値として出力する総合演算回路（例えば、図１６の総合演算回路３５３）とを備えることを特徴とする。
【００７０】
請求項６に記載の電子回路は、前記バッファ回路に、現在の第１の基準領域（例えば、図１４の左下に示される、基準画像（左画像）１９１の基準領域２２１）の位置に対して前記第１の画像（基準画像（左画像）１９１）の縦または横方向と平行に１画素分だけ離間された位置に配置される第２の基準領域（例えば、図１４の左上に示される、現在の基準領域２２１に対して、空間方向xaの逆方向に１画素分だけ離間された位置に配置される基準領域２０１）と、前記第２の基準領域との相対的な位置関係が前記第１の基準領域と現在の第１の比較領域（例えば、相対的な位置関係は、マッチング数Mで表現され、図１４に示される、M=０における、比較領域２０２−０）との相対的な位置関係と同一の第２の比較領域（例えば、図１４の比較領域２２２−０）との組に対する前記第１の値が記憶されている場合、前記第１の積和演算手段は、N個の前記第１の関数演算回路のそれぞれに対して、前記変数aとして、前記第１の基準領域を構成する画素のうちの、前記第１の基準領域と前記第２の基準領域との間で共通する前記画素を除く、N個の画素（例えば、図１４の基準領域２２１の第５列（小領域）を構成する５（＝N）個の画素）のそれぞれの画素値を入力させるとともに、前記変数bとして、前記第１の比較領域を構成する画素のうちの、対応する場所に位置するN個の画素（例えば、図１４の比較領域２２２−０の第５列（小領域）２３２−０を構成する５（＝N）個の画素）のそれぞれの画素値を入力させて、前記関数f(a,b)の出力値のそれぞれを演算させ、前記第１の加算回路に、N個の前記第１の関数演算回路の出力の総和を演算させて、その第１の加算回路の演算結果を第２の値として出力し、前記第２の積和演算手段は、N個の前記第２の関数演算回路のそれぞれに対して、前記変数aとして、前記第２の基準領域を構成する画素のうちの、前記第１の基準領域と前記第２の基準領域との間で共通する前記画素を除く、N個の画素（例えば、図１４の基準領域２０１の第５列（小領域）を構成する５（＝N）個の画素）のそれぞれの画素値を入力させるとともに、前記変数bとして、前記第２の比較領域を構成する画素のうちの、対応する場所に位置するN個の画素（例えば、図１４の比較領域２０２−０の第５列（小領域）２３１−０を構成する５（＝N）個の画素）のそれぞれの画素値を入力させて、前記関数f(a,b)の出力値のそれぞれを演算させ、前記第２の加算回路に、N個の前記第２の関数演算回路の出力の総和を演算させて、その第２の加算回路の演算結果を第３の値として出力し、前記総合演算回路は、前記バッファ回路に記憶された、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値から、前記第２の積和演算回路から出力された前記第３の値を減算し、前記第１の積和演算回路から出力された前記第２の値を加算する演算を行い（図１４において、１つ前の比較領域２０２−０に対応する分の演算結果から、比較領域２０２−０の第１列２３１−０分の演算結果を減算し、比較領域２２２−０の第５列２３２−０分の演算結果を加算することで、比較領域２２２−０に対応する分の演算を行い）、その演算の結果を、現在の前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値として出力することを特徴とする。
【００７１】
請求項７に記載の電子回路は、前記バッファ回路に、前記第２の基準領域と前記第２の比較領域との組に対する前記第１の値が記憶されていない場合（例えば、図１３に示されるように、最初の基準領域２０１が切り出された場合）、前記第１の積和演算回路と前記第２の積和演算回路のそれぞれは、さらに、N画素×N画素からなる前記第１の基準領域が、N個の画素からなるN個の小領域（例えば、１画素×５画素からなる、第１列（小領域）乃至第５列（小領域））に区分され、かつ、N画素×N画素からなる前記第１の比較領域（例えば、図１３のM=0における、比較領域２０２−０）が、前記第１の基準領域のN個の前記小領域の位置のそれぞれに対応する、N個の小領域（例えば、図１３の第１列２１１−０，第２列２１２−０，第３列２１１−１，第４列２１２−１，第５列２１１−２）に区分された場合における、前記第１の基準領域のうちの所定の１つの前記小領域と、前記第１の比較領域のうちの対応する前記小領域とからなるN個の組のうちの、N/2組（例えば、実線で示される列（第１列２１１−０，第３列２１１−１，第５列２１１−２）を含む組と、点線で示される列（第２列２１２−０，第４列２１２−１）を含む組。ただし、Nが奇数の場合、マッチング２回分でN組通し分担すると考える。即ち、M＝０の場合、実線で示される列は３列あるのに対して、点線で示される列は２列である。そこで、今度は、M=1の場合、実線で示される列を２列とし、点線で示される列を３列とする）ずつを処理の対象として分担し、1組毎に（即ち、1クロック毎に１組ずつ）、N個の前記第１または前記第２の関数演算回路のそれぞれに対して、前記変数aとて、前記第１の基準領域における前記小領域を構成するN個の画素のそれぞれの画素値を入力させるとともに、前記変数bとして、前記第１の比較領域における前記小領域を構成するN個の画素のそれぞれの画素値を入力させて、前記関数f(a,b)の出力値のそれぞれを演算させ、前記第１または前記第２の加算回路に、N個の前記第１または前記第２の関数演算回路の出力の総和を演算させて、前記加算回路のN/2組の演算結果のそれぞれを順次出力し（図１３に示されるように、各クロック毎に出力し）、前記総合演算回路は、前記第１の積和演算回路から出力されたN/2個の演算結果のそれぞれと、前記第２の積和演算回路から出力されたN/2個の演算結果のそれぞれの全てを加算する演算を行い（即ち、図１３のｔ＝０からｔ＝２までに行われた、第１列２１１−０，第２列２１２−０，第３列２１１−１，第４列２１２−１，第５列２１１−２分の積和を総加算し）、その演算の結果を、現在の前記第１の基準領域と前記第１の比較領域との組に対する前記第１の値として出力することを特徴とする。
【００７２】
以下、図面を参照して、本発明が適用される画像処理システム、画像処理装置、および、電子回路の実施の形態について説明する。
【００７３】
図５は、本実施の形態の画像処理システムの構成例を表している。
【００７４】
図５の画像処理システム６１は、上述したレクティフィケーション（平行化）、および、上述したウィンドウマッチング手法を伴う、上述したステレオ法を利用して、実物体の距離を演算する画像処理システムとされている。
【００７５】
なお、ウィンドウマッチング手法において、基準領域が切り出される画像（基準画像）は、左画像と右画像のうちのいずれでも構わないが、以下、従来の例とあわせて、左画像とされる。即ち、右画像が、比較画像とされる。
【００７６】
また、実際には、画像処理システム６１は、画像データを処理の対象とするが、画面に表示される画像等と画像データとを区別する必要が特にない場合、以下、画像データを、単に画像と称する。
【００７７】
図５の画像処理システム６１には、左画像（基準画像）を出力する左画像出力部７１、レクティフィケーション（平行化）等によりその左画像を変換する左画像変換部７２、および、左画像変換部７２の処理に必要な情報が含まれるテーブル（以下、このようなテーブルを左変換テーブルと称する）を記憶する左変換テーブル記憶部７３が設けられている。
【００７８】
同様に、図５の画像処理システム６１には、右画像（比較画像）を出力する右画像出力部７４、レクティフィケーション（平行化）等により、その右画像を変換する右画像変換部７５、および、右画像変換部７５の処理に必要な情報が含まれるテーブル（以下、このようなテーブルを右変換テーブルと称する）を記憶する右変換テーブル記憶部７６が設けられている。
【００７９】
左画像出力部７２と右画像出力部７４のそれぞれは、例えば、デジタルスチルカメラやデジタルビデオカメラ（以下、これらを単にカメラと称する）等で構成することができる。なお、左画像出力部７１と右画像出力部７４のそれぞれは、例えば、スキャナ等の、印画紙にプリントされた写真や、フィルムの写真等をデータ化する装置等で構成することも可能であるが、以下、カメラであるとする。即ち、以下、左画像出力部７１と右画像出力部７４のそれぞれを、左カメラ７１および右カメラ７４のそれぞれと称する。
【００８０】
左画像変換部７２と右画像変換部７５とには、画像補正部８１若しくは画像補正部８３、並びに、レクティフィケーション（画像平行化）部８２若しくはレクティフィケーション（画像平行化）部８４が設けられている。
【００８１】
画像補正部８１は、例えば、左カメラ７１から出力された左画像に対して、左カメラ７１のレンズ歪曲収差を除去する等、所定の画像処理を施して、レクティフィケーション（画像平行化）部８２に供給する。レクティフィケーション（画像平行化）部８２は、画像補正部８１より供給された左画像に対して、上述したレクティフィケーション（画像平行化）を施し（図１の矢印３１−１に相当する処理を施し）、画像マッチング部７７に供給する。
【００８２】
同様に、画像補正部８３は、例えば、右カメラ７４から出力された右画像に対して、右カメラ７４のレンズ歪曲収差を除去する等、所定の画像処理を施して、レクティフィケーション（画像平行化）部８４に供給する。レクティフィケーション（画像平行化）部８４は、画像補正部８３より供給された右画像に対して、上述したレクティフィケーション（画像平行化）を施し（図１の矢印３１−２に相当する処理を施し）、画像マッチング部７７に供給する。
【００８３】
このとき、左画像変換部７２と右画像７５のそれぞれは、左変換テーブル記憶部７３に記憶された左変換テーブル、または、右変換テーブル７５に記憶された右変換テーブルを利用して、対応する画像処理を実行する。
【００８４】
即ち、左変換テーブル記憶部７３と右変換テーブル記憶部７６は、例えば、ROM（Read Only Memory）等のメモリからなり、左変換テーブルまたは右変換テーブルを記憶する。左変換テーブルと右変換テーブルには、左カメラ７１と右カメラ７４のうちの対応するカメラのレンズ係数や、左カメラ７１と右カメラ７４の位置関係、或いは、それらの情報に基づいて予め算出された数値等が含まれる。
【００８５】
画像マッチング部７７は、上述したウィンドウマッチング手法を利用して、左画像変換部７２より供給された左画像を構成する各画素のそれぞれに対して、右画像変換部７５より供給された右画像内の対応点（画素）を検出し、それらの検出結果（左画像の各画素のそれぞれの対応点）に基づいて視差情報を生成し、距離演算部７８に供給する。
【００８６】
距離演算部７８は、画像マッチング部７７より供給された視差情報に基づいて、実物体（左画像と右画像に含まれる実物体）の距離を演算し、外部に出力する。なお、視差情報は、距離の算出以外の処理にも使用可能であり、この場合、画像処理システム６１には、距離演算部７８の代わりに、対応する処理を実行するブロックが設けられる。
【００８７】
これらの、左画像変換部７２、右画像変換部７５、および、距離演算部７８はいずれも、ハードウエア（回路等）で構成しても構わないし、ソフトウエアで構成しても構わないし、或いは、ハードウエアとソフトウエアの組合せで構成しても構わない。
【００８８】
また、画像マッチング部７７も、勿論、ハードウエア（回路等）で構成しても構わないし、ソフトウエアで構成しても構わないし、或いは、ハードウエアとソフトウエアの組合せで構成しても構わない。ただし、以下においては、画像マッチング部７７は、ハードウエアで構成されるとして説明を行う。
【００８９】
このように、画像処理システム６１は、レクティフィケーション（平行化）、および、ウィンドウマッチング手法を伴う、ステレオ法を利用して、実物体の距離を演算する。
【００９０】
ここで、図６乃至図１１を参照して、ウィンドウマッチング手法を伴うステレオ法と、その手法を効率的に行わせるためのレクティフィケーション（平行化）のそれぞれの詳細についてその順番に説明する。
【００９１】
はじめに、一般的なステレオ法の詳細について説明する。
【００９２】
即ち、例えば、図６において、光学中心が点cbとなるように配置された左カメラ７１と、光学中心が点cdとなるように配置された右カメラ７４のそれぞれが、点Pをその表面に含む実物体を撮影すると、左カメラ７１からは実物体の投影像を含む左画像９１が得られ、また、右カメラ７４からも実物体の投影像を含む右画像９２が得られる。この場合、実物体上の点Ｐが表示されている左画像９１上の点na（対応する画素）と、同じく、実物体上の点Ｐが表示されている右画像９２上の点nb（対応する画素）とから（即ち、点naと、その対応点nbとから）、左カメラ７１と右カメラと７４との間の視差を求めることができ、さらに、三角測量の原理を用いて、点Pの三次元空間における位置（三次元位置）を求めることができる。
【００９３】
従って、上述したように、ステレオ法では、まず、対応点を検出することが必要となるが、その検出方法としては，例えば、上述したように、エピポーラライン（Epipolar Line）を用いたウィンドウマッチング手法（エリアベースマッチング法と称されることもある）等がある。
【００９４】
即ち、図６に示されるように、実物体上の点Pの、左画像９１における位置は、その点Pと左カメラ７１の光学中心（レンズ中心）cbとを結ぶ直線９３上の、左カメラ７１の撮像面（左画像９１）との交点na（対応する画素）となる。
【００９５】
また、実物体上の点Ｐの、右画像９２上の位置は、その点Pと右カメラ７４の光学中心（レンズ中心）cdとを結ぶ直線上の、右カメラ７４の撮像面（右画像９２）との交点nb（対応する画素）となる。
【００９６】
この場合、直線９３が右カメラにより撮影されたとすると、その直線９３の投影像は、光学中心cb、光学中心cd、および、点nb（または点Ｐ）の３点を通る平面と、撮像面（右画像９２）との交線９４として、撮像面（右画像９２）に含まれることになる。従って、撮像面（右画像９２）において、点Ｐの投影像である点nbは、当然ながら、直線９３の投影像である直線９４上に存在し、この直線９４が、一般的にエピポーララインと称されている。即ち、左画像９１内の点na（それに対応する画素）の、右画像９２内の対応点nb（それに対応する画素）の配置位置は、必ずエピポーラライン９４上であり、従って、対応点nbの探索（検出）は、エピポーラライン９４上を対象に行えばよい。
【００９７】
このエピポーララインは、例えば、左画像（基準画像）９１を構成する各画素毎に考えることができるが、左カメラ７１と右カメラ７４の位置関係が既知であれば、その画素ごとに存在するエピポーララインは求めることができる。
【００９８】
また、求められたエピポーラライン９４上の各点の中から、対応点nbを検出するためには、例えば、次のようなウィンドウマッチング手法（エリアベースマッチング法）を適用すればよい。
【００９９】
即ち、ウィンドウマッチング手法では、図７に示されるように、左画像（基準画像）９１のうちの、例えば、対応点を求めたい点na（例えば、対角線の交点であって、実際には、上述した注目画素）を中心とする、例えば、長方形（正方形含む）状の小ブロック（この小ブロックが、上述した基準領域である）が、左画像９１から抜き出される（切り出される）。また、図８に示されるように、右画像（比較画像）９２に投影されたエピポーラライン９４上の、ある点（実際には、画素）を中心とする、左画像９１の基準領域と同一の大きさの小ブロックで（この小ブロックが、上述した比較領域である）が、右画像（比較画像）９２から抜き出される。
【０１００】
このような比較領域の中心点として、例えば、図８の例では、エピポーラライン９４上に、点nb1乃至点nb6の６点が設けられている。この点nb1乃至点nb6は、図６に示される、三次元空間における直線９３を、例えば、１ｍなどの所定の一定距離ごとに区分する点（左カメラ７１からの距離が１ｍ，２ｍ，３ｍ，４ｍ，５ｍ，６ｍのそれぞれとなる点）を、右カメラ７４の撮像面（右画像９２）に投影した点である。即ち、点nb1乃至点nb6のそれぞれは、左カメラ７１からの距離が１ｍ，２ｍ，３ｍ，４ｍ，５ｍ，６ｍ（距離の推定値）のそれぞれの点に対応している（この場合、距離分解能が１ｍであるということができる）。
【０１０１】
このように、この例のウィンドウマッチング手法では、左画像（基準画像）９１から、注目点naを中心とする基準領域が切り出されるとともに、右画像（比較画像）９２から、エピポーラライン９４上に設けられている点nb1乃至点nb6のそれぞれを中心とする比較領域が抜き出される。
【０１０２】
そして、各比較領域のそれぞれと、基準領域との相関が、所定の評価関数を用いて演算され、それらの演算結果のうちの、基準領域との相関が最も高い演算結果を有する比較領域の中心点（点nb1乃至点nb6のうちのいずれかの点）が、注目点naの対応点として求められる。
【０１０３】
換言すると、ウィンドウマッチング手法では、基準となる左カメラ７１の左画像９１より所定の領域を基準領域として切りだし、その基準領域を、他の右カメラ７４の右画像９２のエピポーラライン９４上で順次変移させ、その各変移位置のそれぞれにおいて、この基準領域と、それと重なり合う右画像９２の領域（比較領域）との間で一致度（相関）を、所定の評価関数等を用いて演算する。そして、もっとも一致度（相関）が高いと演算された右画像９２の比較領域の中心点（もっとも一致度（相関）が高いと演算された時点での、基準領域の変移量に対応する点）を、基準領域の中心点（注目画素）の対応点として設定する。
【０１０４】
なお、このような評価関数（評価値s）として、例えば、上述した式（１）乃至式（３）を利用することができる。
【０１０５】
例えば、いま、評価関数（評価値ｓ）として、上述した式（３）が利用されたとする。この場合、式（３）で表される評価値sは、その値が小さいほど、相関が大きいことを示すという特徴を有しているので、右画像（比較画像）９２上の点nb1乃至点nb6のうちの、評価値sを最も小さくする点が、左画像（基準画像）９１上の点naの対応点として求められる。
【０１０６】
具体的には、例えば、いま、右画像９２上の点nb1乃至点nb6のそれぞれと、左画像９１上の点naとの評価値（式（３）の評価関数の値）sとして、図９に示されるような結果が得られたとする。
【０１０７】
この場合、右画像９２上の点nb1乃至点nb6のうちの、評価値sが最も小さい（最も相関が高い）点nb3が、左画像９１上の点naの対応点として検出される。
【０１０８】
また、上述したように、点nb1乃至点nb6のそれぞれは、左カメラ７１からの距離が１ｍ，２ｍ，３ｍ，４ｍ，５ｍ，６ｍ（距離の推定値）のそれぞれの点に対応しているので、図９の水平方向の軸を、距離として捉えることもできる。即ち、評価値sを最も小さくする点の水平方向の距離軸の座標値が、点naに対応する三次元実空間上の点P（図６）の左カメラ７１からの距離を示すことになる。具体的には、図９の例では、点Pの距離は、点nb3に対応する３ｍとされる。
【０１０９】
さらに、図９において、右画像９２上の点nb1乃至点nb6それぞれについて求められた評価値（図９においては●印で示されている）のうちの最小値付近のものを用いて補間を行い、評価値がより小さくなる点（図９においては×印で示されている）を求めて、その点を、最終的な対応点として検出することも可能である。この場合、点Pの距離に換算すると、×印で示される点は3.3ｍとされる。
【０１１０】
このように、左画像９１の所定の点naの対応点を検出するための点として、図９等の上述した例では、三次元空間における実物体P上の点と、左カメラ７１の光学中心cbとを結ぶ直線９３を所定の等距離ごとに区分する点を、右カメラ７４の撮像面（右画像）９４に投影した点nb1乃至点nb6が予め設定されている。
【０１１１】
このような設定は、例えば、左カメラ７１および右カメラ７４のキャリブレーション時に行うことができる（キャリブレーションの方法は、特に限定されるものではない）。
【０１１２】
そして、このような設定を、左カメラ７１の撮像面（左画像９１）を構成する画素毎に存在する各エピポーララインのそれぞれに対して行い、各エピポーラライン上のそれぞれに設定された各点（以下、適宜、設定点という）と、左カメラ７１からの距離とを対応付けるテーブルをあらかじめ作成することもできる。そこで、例えば、距離演算部７８（図５）が、そのテーブルをあらかじめ保持し、画像マッチング７７が、対応点となる設定点を検出し、その設定点を視差情報として距離演算部７８に供給することで、距離演算部７８は、その視差情報を、そのテーブルを参照して、左カメラ７１からの距離（実物体上の点までの距離の推定値）に即座に変換することができる。即ち、いわば、対応点から、距離を直接求めることができる。
【０１１３】
或いは、このような設定点が予め設定されていなくとも、画像マッチング部７７は、左画像（基準画像）９１上の所定の点（注目画素）に対して、右画像（比較画像）９２上の対応点（画素）を検出し、その２点（注目画素と、対応点に対応する画素と）の視差を求め、それを視差情報として供給することで（或いは、単にこの２点を距離演算部７８に提供し、距離演算部７８が視差を求めてもよい）、距離演算部７８は、左カメラ７１と右カメラ７４の位置関係（既知とする）、および、供給された視差情報を用いて、三角測量の原理に基づく所定の演算を行い、実物体までの距離を求めることができる。勿論、この場合も、視差と距離とを対応付けるテーブルをあらかじめ作成しておけば、距離演算部７８は、このテーブルを参照することで、左カメラ７１からの距離を即座に求めることができる。
【０１１４】
なお、対応点の検出に、基準領域および比較領域といった複数画素でなるブロックを用いるのは、ノイズの影響を軽減し、左画像（基準画像）９１上の画素（点）naの周囲の画素のパターンの特徴と、右画像（比較画像）９２上の対応点（画素）nbの周囲の画素のパターンの特徴との間の相関性を利用することにより、対応点の検出の確実を期すためであり、特に、変化の少ない左画像９１および右画像９２に対しては、画像の相関性により、ブロックの大きさを大きくすれば、対応点の検出の確実性を向上させることができる。
【０１１５】
次に、図１０と図１１を参照して、レクティフィケーション（平行化）について説明する。
【０１１６】
上述したように、ステレオ法では、左カメラ７１と右カメラ７４とが平行でない場合、図６に示されるように、エピポーラライン９４は一般的に水平とならない。このため、左画像９１上の注目点naの、右画像９２上の対応点nbの探索を、エピポーラライン９４に沿って行うと、多くの演算が必要となるとともに、デジタル誤差が大きくなってしまう、といった課題が発生してしまう。
【０１１７】
換言すると、左カメラ７１と右カメラ７４とが平行である場合、図１０に示されるように、エピポーラライン９４は水平となり（即ち、右画像９４の垂直方向の座標が、左画像９１の注目点naの垂直方向の座標vと同一の直線となり）、このような課題は発生しない。
【０１１８】
そこで、この課題を解決するためには、左カメラ７１と右カメラ７４とが平行でない場合、そのとき得られた左画像９１と右画像７２のそれぞれを、左カメラ７１と右カメラ７４とが平行であった場合に得られる画像と同様の画像に変換する手法を適用すればよい。この手法が、上述したように、レクティフィケーション（平行化）と称されている。
【０１１９】
即ち、レクティフィケーション（平行化）では、図１１に示されるように、仮想的な画像平面１０３を置き、左画像９１と右画像９２のそれぞれを、この仮想画像平面１０３に射影させた場合の画像（即ち、平行カメラ（平行に配置された左カメラ７１と右カメラ７４）によりあたかも撮影されたような画像）に変換させる。これにより、もともと平行でなかったエピポーララインは、仮想画像平面上では平行（水平方向に平行）となり、また、左カメラ７１の光学中心cbと、右カメラ７４の光学中心cdとを結ぶ直線と平行になる。
【０１２０】
次に、図１２を参照して、図５の画像マッチング部７７の詳細について説明する。即ち、図１２は、評価式として上述した式（１）で示される正規化相関関数を利用する画像マッチング部７７の構成例を表している。
【０１２１】
図３と図１２とを比較するに、本実施の形態の画像マッチング部７７（図１２）も、マクロ的に見ると、従来の画像マッチング部（図３）と基本的に同様の構成を有していることがわかる。ただし、本実施の形態の画像マッチング部７７にはさらに、視差情報生成部１２８も設けられているが、この視差情報生成部１２８については後述する。
【０１２２】
即ち、本実施の形態の画像マッチング部７７にも、従来の左右画像メモリ５１乃至S2正規化相関値メモリ５７のそれぞれに対応する、左右画像メモリ１２１乃至S2正規化相関値メモリ１２７のそれぞれが設けられている。
【０１２３】
換言すると、本実施の形態においても、左右画像メモリ１２１乃至S2正規化相関値メモリ１２７のそれぞれにおける、入出力値自体や他のブロック（回路）との接続形態自体は、従来における、左右画像メモリ５１乃至S2正規化相関値メモリ５７のそれぞれにおける、入出力値や他のブロックとの接続形態と基本的に同様とされている。従って、それらの説明については省略する。
【０１２４】
しかしながら、仮に、本実施の形態に対しても、上述した式（１）の右辺の分子や、分母のルートの中の演算を行う電子回路として、図３に示されるような従来の回路、即ち、乗算器の数がNxN個必要な電子回路であって、具体的には、ΣAB乗算器５２（詳細な構成は、図４参照）、ΣA2乗算器５３、および、ΣB2乗算器５４のそれぞれをそのまま適用させた場合、従来の課題を解決することができない。
【０１２５】
そこで、この課題を解決するために、本実施の形態の画像マッチング７７には、従来の電子回路（即ち、ΣAB乗算器５２、ΣA2乗算器５３、および、ΣB2乗算器５４のそれぞれ）の代わりに、N×Nの基準領域に対する正規化相関関数の演算に必要となる乗算器の数を2×N個に抑えつつ、その処理時間を、従来のもの（乗算器の数がNxN個必要な電子回路）と比べても、1%から2%程度の増加に収えることが可能な構成を有する電子回路（即ち、ΣAB乗算器１２２、ΣA2乗算器１２３、および、ΣB2乗算器１２４のそれぞれ）が設けられている。
【０１２６】
或いは、従来から存在する画像マッチング部（図３）のうちの、上述した式（１）の右辺の分子や、分母のルートの中の演算を行う電子回路として、従来のΣAB乗算器５２、ΣA2乗算器５３、および、ΣB2乗算器５４のそれぞれの代わりに、本実施の形態の電子回路、即ち、ΣAB乗算器１２２、ΣA2乗算器１２３、および、ΣB2乗算器１２４のそれぞれが適用されたと捉えることもできる。
【０１２７】
なお、以下、従来の例と比較するために、画像マッチング部７７は、左画像変換部７２より供給される左画像（基準画像）の注目画素の対応点を検出する場合、即ち、ウィンドウマッチングを行なう場合、左画像から、注目画素（注目点）を中心として５×５の基準領域を切り出すとする。
【０１２８】
この場合、画像マッチング部７７は、例えば、マッチング数M=0においては、左画像と右画像とを重ねた場合に、左画像の５×５の基準領域と重なる右画像の５×５の領域を、比較領域として切り出し、その比較領域と基準領域との相関値sを演算する（式（１）を演算する）。即ち、１回目のマッチングが行われる。
【０１２９】
次に、画像マッチング部７７は、マッチング数M=1においては、基準領域を右画像の水平方向（エピポーララインと平行）に1画素分スライドさせ、その時点で基準領域と重なる領域、即ち、前回のマッチング数M=0における比較領域に対して水平方向（エピポーララインと平行）に1画素分平行移動された領域を、比較領域として切り出し、その比較領域と基準領域との相関値sを演算する（式（１）を演算する）。即ち、２回目のマッチングが行われる。
【０１３０】
以降、画像マッチング部７７は、同様の処理を繰り返す。即ち、画像マッチング部７７は、マッチング数M=k（kは、最大値以下の任意の整数値。ただし、最大値については後述する）においては、１つ前のマッチング数M＝k-1における比較領域を、右画像の水平方向（エピポーララインと平行）に１画素分平行移動させた領域を、現在の比較領域（マッチング数Mにおける比較領域）として切り出し、その比較領域と基準領域との相関値sを演算する。即ち、k+1回目のマッチングが行われる。
【０１３１】
ところで、以下、切り出された基準領域を構成する各画素の位置は、上述した座標系(xa,ya)（図２）を参照して説明する。同様に、基準領域に対する、右画像変換部７５より供給される右画像（比較画像）を構成する各画素の位置は、上述した座標系(xb,yb)（図２）を参照して説明する。
【０１３２】
ただし、これまでは（従来の例の説明においては）、左画像の基準領域を構成する各画素の画素値は、対応する画素に付与された番号で示されたが（即ち、例えば、番号Iが付与された画素の画素値は、aIと示されたが）、以下、対応する画素の座標系(xa,ya)における座標値（即ち、(x,y)に位置する画素の画素値は、a(x,y)）で示されるとする。
【０１３３】
具体的には、例えば、図２において、注目画素４１−１２の画素値は、これまでa12で示されていたが、以下においては、a(X+2,Y+2)で示されることになる。また、基準領域の左上端の画素４１−０の画素値は、これまではa0で示されていたが、以下においては、a(X,Y)で示されることになる。
【０１３４】
同様に、これまでは、右画像の比較領域を構成する各画素の画素値は、対応する画素に付与された番号で示されたが（即ち、例えば、番号Iが付与された画素の画素値は、bIと示されたが）、以下、対応する画素の座標系(xb,yb)における座標値で示される（即ち、(x,y)に位置する画素の画素値は、b(x,y)）で示されるとする。
【０１３５】
具体的には、例えば、図２において、比較領域４２は、マッチング数（スライド数）Mにおける比較領域を示しているが、この比較領域４２のうちの、画素４２−１２の画素値は、これまでb12で示されていたが、以下においては、b(X+2+M,Y+2)で示されることになる。また、基準領域の左上端の画素４２−０の画素値は、これまではb0で示されていたが、以下においては、b(X＋M,Y)で示されることになる。
【０１３６】
従って、図２に示されるような、基準領域４１とマッチング数Mにおける比較領域４２との組に対する、式（１）の右辺で示される正規化相関関数の成分は、次の式（４）乃至式（６）で示される。ただし、式（４）乃至式（６）においては、一般的なN×Nの基準領域に対する式とされているが、ここでは、上述したように、N=５とされる。
【０１３７】
即ち、式（１）の右辺の分子は、以下、次の式（４）の右辺で示されるように変換される。なお、式（４）の左辺は、式（１）の右辺の分子を表しているが、式（１）においては小文字のiで表されている画素の番号は、式（４）の右辺の座標iと混同しないように、大文字のIで記述されている。
【０１３８】
【数４】
2005084698.tif 000006
・・・（４）
【０１３９】
同様に、式（１）の右辺の分母のうちのaiの自乗の総和は、以下、式（５）の右辺で示されるように変換される。なお、式（５）の左辺は、式（１）の右辺の分母のうちのaiの自乗の総和を表しているが、やはり、式（１）においては小文字のiで表されている画素の番号は、式（５）の右辺の座標iと混同しないように、大文字のIで記述されている。
【０１４０】
【数５】
2005084698.tif 000007
・・・（５）
【０１４１】
また、式（１）の右辺の分母のうちのbiの自乗の総和は、以下、式（６）の右辺で示されるように変換される。なお、式（６）の左辺は、式（１）の右辺の分母のうちのbiの自乗の総和を表しているが、やはり、式（１）においては小文字のiで表されている画素の番号は、式（６）の右辺の座標iと混同しないように、大文字のIで記述されている。
【０１４２】
【数６】
2005084698.tif 000008
・・・（６）
【０１４３】
即ち、以下、ΣAB乗算器１２２は式（４）の右辺を、ΣA2乗算器１２３は式（５）の右辺を、ΣB2乗算器１２４は式（６）の右辺を、それぞれ演算するとして説明する。
【０１４４】
ところで、例えば、ΣB2乗算器１２４は、マッチング数（スライド数）M=kにおける図２の比較領域４２に対する式（６）の右辺を演算する場合、その直前のマッチング数M=k-1における演算結果を使用することで、その演算を簡単に行うことができる。なお、マッチング数M=k-1における演算結果とは、マッチング数M=k-1における比較領域（図示はしないが、比較領域４２が、水平方向xbの負の方向に１だけ水平移動された（１画素分ずれた）５×５の領域）に対する式（６）の右辺の演算結果を指す。
【０１４５】
即ち、マッチング数M=kにおける比較領域４２は、図２の座標系(xb,yb)において、左上端の画素の中心値が座標(X+k，Y)とされ、右下端の画素の中心値が座標(X+4+k,Y+4)とされる領域である。
【０１４６】
一方、マッチング数M=k-1における図示せぬ比較領域は、座標系(xb,yb)において、左上端の画素の中心値が座標(X+k-1，Y)とされ、右下端の画素の中心値が座標(X+4+(k-1),Y+4)、即ち座標(X+3+k,Y+4)とされる領域である。
【０１４７】
従って、マッチング数M=kにおける比較領域４２と、マッチング数M=k-1における比較領域との差異は、結局、次の２つのみ（それ以外は、共通画素）である。
【０１４８】
即ち、１つ目の差異は、「座標(X+k-1,j（jは、Y乃至Y+4のうちのいずれか）)に位置する５個の画素は、マッチング数M=k-1の比較領域には（第１列目の成分として）含まれているが、マッチング数M=kの比較領域４２には含まれていない」ことである。
【０１４９】
また、２つ目の差異は、「座標(X+4+k,j（jは、Y乃至Y+4のうちのいずれか）)に位置する５個の画素は、マッチング数M=k-1の比較領域には含まれていないが、マッチング数M=kの比較領域４２には（第５列目の成分として）含まれている」ことである。
【０１５０】
そこで、ΣB2乗算器１２４は、「直前の演算結果（マッチング数M=k-1の比較領域に対する式（６）の右辺の演算結果）」から、「座標(X+k-1,j)に位置する５個（N個）の画素のそれぞれの画素値の自乗の総和」を減算し、「座標(X+4+k,j)に位置する５個の画素のそれぞれの画素値の自乗の総和」を加算することで、「マッチング数Mの比較領域４２に対する式（６）の右辺の演算結果（それを行ったのと等価な値）」を出力することができる。
【０１５１】
従って、図示はしないが、ΣB2乗算器１２４は、「座標(X+k-1,j)に位置する５個（N個）の画素のそれぞれの画素値の自乗」のそれぞれを演算する５個（N個）の乗算器（かつ、それらの総和を加算する加算器）、「座標(X+4+k,j)に位置する５個の画素のそれぞれの画素値の自乗」のそれぞれを演算する５個（N個）の乗算器（かつ、それらの総和を加算する加算器）、および、「直前の演算結果（マッチング数M=k-1の比較領域に対する式（６）の右辺の演算結果）」を保持するバッファやシフトレジスタを、それぞれ構成要素として有すれば、「マッチング数Mの比較領域４２に対する式（６）の右辺の演算結果（それを行ったのと等価な値）」の出力を簡単に実現することができる。
【０１５２】
同様に、ΣA2乗算器１２３も、ΣB2乗算器１２４と基本的に同様の構成を有することで、式（５）の右辺の演算結果（それを行ったのと等価な値）の出力を簡単に実現することができる。
【０１５３】
ところが、式（４）においては、基準領域４１のうちの、座標(i,j)に位置する画素の画素値a(i,j)に乗算される値は、比較領域のうちの、座標(i+M,j)に位置する画素の画素値b(i+M,j)とされている。従って、画素値b(i+M,j)におけるMはマッチング数を表していることから、画素値a(i,j)に乗算される値は、マッチング数M=kにおいては、画素値b(i+k,j)となるるが、次のマッチング数M=k+1においては、それとは異なる画素値b(i+k+1,j)となる。即ち、マッチング数Mが変化する毎に、基準領域４１の全ての画素の画素値a(i,j)に乗算される値は刻々と変化することになる。
【０１５４】
従って、ΣAB乗算器１２２は、ΣA2乗算器１２３が実行する式（５）の右辺の演算や、ΣB2乗算器１２４が実行する式（６）の右辺の演算のような、基準領域または比較領域の両端の単なる加減算を行っても、式（４）の右辺の演算を行うことができない。
【０１５５】
そこで、本実施の形態においては、ΣAB乗算器１２２は、図１３乃至図１５に示されるような手順で式（４）の右辺の演算を行う。即ち、図１３乃至図１５は、ΣAB乗算器１２２が実行する式（４）の右辺の演算の手順を説明する図である。
【０１５６】
図１３において、図中、左上には、左画像（基準画像）１９１が示されている。図１３に示されるように、左画像１９１は320×240画素から構成されており、例えば、いま、１回目の基準領域として、左上端の画素の位置が座標(1,1)となる、５×５の基準領域２０１が切り出されたとする。即ち、注目画素（基準領域２０１の中心画素）として、その位置が座標(3,3)となる画素が設定され、このため、その注目画素を中心とする、５×５の基準領域２０１が切り出されたとする。
【０１５７】
また、図１３に示されるように、１つの基準領域（いまの場合、基準領域２０１）に対しては、６４回のマッチング（式（１）の演算処理）が実行されるとする。即ち、図１３においては、左画像１９１の図中右方に、マッチング数（スライド数）M＝０乃至６３のそれぞれに対する、右画像１９２の比較領域２０２−０乃至比較領域２０２−６３のそれぞれが示されている（ただし、M＝３乃至６２については省略されている）。
【０１５８】
即ち、図１３は、一番左の列（それを構成する５つの画素）のxa座標Xが初期値X0（図１３の例では、X0＝１）となるように、左画像１９１から切り出された基準領域２０１を対象とする、式（４）の右辺の演算の手順の例を表している。
【０１５９】
具体的には、例えば、マッチング数（スライド数）M＝０の場合、左画像１９１の基準領域２０１と、図中その右隣に図示されている、右画像１９２の比較領域２０２−０との組に対する、式（４）の右辺の演算が行われることになる。このときの手順が、比較領域２０２−０が描画された右画像１９２の下方に示されている。即ち、比較領域２０２−０を含む右画像１９２の下方に図示されている、３つの右画像１９２のそれぞれが、マッチング数M=0における処理の対象を表している。
【０１６０】
このことは、他のマッチング処理M=kにおいても同様とされている。即ち、マッチング数M＝kの場合、左画像１９１の基準領域２０１と、右画像１９２の比較領域２０２−ｋとの組に対する、式（４）の右辺の演算が行われることになる。このときの手順が、比較領域２０２−ｋが描画された右画像１９２の下方に示されている。即ち、比較領域２０２−ｋを含む右画像１９２の下方に図示されている、３つの右画像１９２のそれぞれが、マッチング数M=kにおける処理対象を表している。
【０１６１】
なお、これらの処理対象を示す３つの右画像１９２の左方には、図中垂直上方向に時間軸（矢印）が示されている。この時間軸は、マッチング数（スライド数）M＝0乃至６３それぞれの手順にとって、他のマッチング数Mとは独立した時間軸とされている。即ち、例えば、マッチング数M=0とマッチング数M=1とのそれぞれに対して、式（４）の右辺の演算が同時に行われるのではなく、マッチング数Mにおける処理対象を示す、各右画像１９２のそれぞれの図中右下に図示された処理の時刻tで、それぞれの対応する処理が開始される。
【０１６２】
この時刻tは、1クロックの時間長T［秒］を１単位とする時刻であって、最初のクロックパルスが発生した時点を起点(時刻t=0)とする時刻とされている。即ち、時刻t=r（図１３の例では、rは、0乃至１５９のうちのいずれかの値）の時点では、r［クロック］、即ち、r×T［秒］が経過していることになる。
【０１６３】
また、以下、基準領域２０１、および、比較領域２０２−０乃至比較領域２０２−６３のそれぞれを、５行５列（N行N列）の行列とみなし、水平方向（空間方向xbまたは空間方向xa）に並ぶ５個（N個）の画素の群（小領域）を行と称し、垂直方向（空間方向ybまたは空間方向ya）に並ぶ５個（N個）の画素の群（小領域）を列と称する。ただし、行列の成分は、画素の画素値とされる。
【０１６４】
具体的には、例えば、基準領域２０１において、第１列とは、座標(X(=1),h)（hは、１乃至５のうちのいずれかの整数値）に配置される５個の画素の群を指す。同様に、第２列とは、座標(X+1(=2),h)に配置される５個の画素群を、第３列とは、座標(X+2(=3),h)に配置される５個の画素群を、第４列とは、座標(X+3(=4),h)に配置される５個の画素群を、第５列とは、座標(X+4(=5),h)に配置される５個の画素群を、それぞれ指す。
【０１６５】
また、以下、「第１の行列を構成する各行列成分（即ち、画素値）のそれぞれと、第２の行列を構成する各行列成分（即ち、画素）のそれぞれとの積の総和」を、「第１の行列と第２の行列との積和」と称する。
【０１６６】
以上の前提に基づいて、第１列のxa座標Xが初期値X0に位置する(X=X0とする)ように、左画像１９１から切り出された基準領域２０１を対象とする、式（４）の右辺の演算の手順について説明する。
【０１６７】
即ち、上述したように、ΣAB乗算器１２２は、乗算器（例えば、後述する図１６の乗算器３０１）を２×Ｎ（いまの場合、Ｎ＝５）個有しており、また、基準領域２０１の各列と、比較領域２０２−１乃至比較領域２０２−６３の各列のそれぞれは、Ｎ個の画素から構成されているので、ΣAB乗算器１２２は、１クロック（時間Ｔ）毎に、２列分の積和を演算することができる。
【０１６８】
そこで、時刻t=0において、ΣAB乗算器１２２は、基準領域２０１の第１列と、比較領域２０２−０の第１列２１１−０との積和を演算するとともに、基準領域２０１の第２列と、比較領域２０２−０の第２列２１２−０との積和を演算する。
【０１６９】
時刻t=1において、ΣAB乗算器１２２は、基準領域２０１の第３列と、比較領域２０２−０の第３列２１１−１との積和を演算するとともに、基準領域２０１の第４列と、比較領域２０２−０の第４列２１２−１との積和を演算する。
【０１７０】
時刻t=2において、ΣAB乗算器１２２は、基準領域２０１の第５列と、比較領域２０２−０の第５列２１１−２との積和を演算する。
【０１７１】
そして、ΣAB乗算器１２２は、時刻t=0乃至t=2のマッチング数0における演算結果の全てを加算することで、基準領域２０１と比較領域２０２−０との積和、即ち、式（４）の右辺を演算することができる。なお、この場合、式（４）における、X＝Y=1とされ、N＝5とされ、かつ、M=0とされる。
【０１７２】
ところで、ΣAB乗算器１２２は、上述したように、１クロック（時間Ｔ）の間に、２列分の積和を演算可能である。そこで、図１３に示されるように、t=2において、ΣAB乗算器１２２は、さらに、次のマッチング数M=1における、右画像の比較領域２０２−１（マッチング数M=0における比較領域２０２−０の図中右隣に図示されている）に対する１回目の処理（マッチング数M=1における最初のクロックの処理）として、比較領域２０２−１の下方に示される３つの右画像１９２のうちの一番下の右画像１９２に示されるように、基準領域２０１の第１列と、比較領域２０２−１の第１列２１２−２との積和を演算する。
【０１７３】
その後、時刻t=3において、ΣAB乗算器１２２は、基準領域２０１の第２列と、比較領域２０２−１の第２列２１１−３との積和を演算するとともに、基準領域２０１の第３列と、比較領域２０２−１の第３列２１２−３との積和を演算する。
【０１７４】
時刻t=4において、ΣAB乗算器１２２は、基準領域２０１の第４列と、比較領域２０２−１の第４列２１１−４との積和を演算するとともに、基準領域２０１の第５列と、比較領域２０２−１の第５列２１２−４との積和を演算する。
【０１７５】
そして、ΣAB乗算器１２２は、時刻t=2乃至時刻t=4のマッチング数M=1における演算結果の全てを加算することで、基準領域２０１と比較領域２０２−１の積和、即ち、式（４）の右辺を演算することができる。なお、この場合、式（４）における、X=2とされ、Y=1とされ、N＝5とされ、かつ、M=1とされる。
【０１７６】
このように、ΣAB乗算器１２２は、時刻t=0乃至t=4の時間で、即ち、N(=5)クロックで、基準領域２０１と、２つの比較領域２０２−０と比較領域２０２−１のそれぞれとの積和（式（４）の右辺の演算）を実行することができる。
【０１７７】
即ち、時刻t=2においては、基準領域２０１の第５列と、マッチング数M=0における比較領域２０２−０の第５列２１１−２との積和と、基準領域２０１の第１列と、マッチング数M=1における比較領域２０２−１の第１列２１２−２との積和とが同時に実行されているが、これらの２つの積和のそれぞれが、あたかも１／２クロックずつ順次実行されたとみなした場合、マッチング数M=kに対応する式（４）の右辺の演算（基準領域２０１と、比較領域２０２-kとの積和の演算）に必要な時間は、Ｎ／２クロック（いまの場合、２．５クロック）であると言える。
【０１７８】
時刻t=５以降についても、ΣAB乗算器１２２は、上述した時刻t=0乃至t=4における処理と全く同様の処理を行っていき、最終的に、時刻t=160で、即ち、160（=64×5/2）クロックで、基準領域２０１と、全ての比較領域２０２−０乃至比較領域２０２−６３のそれぞれとの積和の演算処理を完了させる。
【０１７９】
このようにして、最初の基準領域２０１に対する対応点の検索処理（それに伴う、式（４）の右辺の演算処理）が実行されると、今度は、左画像（基準画像）１９１において、基準領域２０１の中心画素（これまでの注目画素）の右隣の画素（水平方向xaに１つずらした画素）、即ち、座標(4,3)に位置する画素が新たな注目画素として設定されて、図１４に示されるように、その注目画素を中心とする５×５の領域が、基準領域２２１として切り出されることになる。
【０１８０】
従って、ΣAB乗算器１２２は、今度は、この基準領域２２１を対象として、各マッチング数M=0乃至６３のそれぞれに対して、図１４に示されるような手順で式（４）の右辺の演算を実行する。即ち、図１４は、ΣAB乗算器１２２が、この基準領域２２１を対象として、各マッチング数M=0乃至６３のそれぞれに対して、式（４）の右辺の演算を実行する場合の手順を表している。
【０１８１】
図１４の下方の図に示されるように、マッチング数M=0においては、基準領域２２１の中心画素（注目画素）の配置位置と対応する右画像１９２の位置、即ち、座標(4,3)に位置する画素を中心とする、５×５の領域２２２−０が、比較領域として切り出され、基準領域２２１とこの比較領域２２２−０との積和が演算されることになる。
【０１８２】
ところで、図１４に示されるように、マッチング数M=0においては、１つ前の基準領域２０１と、現在の基準領域２２１との差異は、「１つ前の基準領域２０１の第１列が、現在の基準領域２２１の構成要素とされていない」ことと、「1つ前の基準領域２２１の第５列が、現在の基準領域２０１の構成要素とされていない」ことの２つである。
【０１８３】
同様に、マッチング数M=0においては、１つ前の比較領域２０２−０と、現在の基準領域２２１に対する比較領域２２２−０との差異は、「１つ前の比較領域２０２−０の第１列が、現在の比較領域２２２−０の構成要素とされていない」ことと、「１つ前の比較領域２２２−０の第５列が、現在の比較領域２０２−０の構成要素とされていない」ことである。
【０１８４】
即ち、マッチング数M=0においては、現在の基準領域２２１のうちの第１列乃至第４列は、１つ前の基準領域２０１との共通領域（１つ前の基準領域２０１のうちの第２列乃至第４列とされていた領域）である。同様に、現在の比較領域２２２−０のうちの第１列乃至第４列は、１つ前の比較領域２０２−０との共通領域（１つ前の比較領域２０２−０のうちの第２列乃至第４列とされていた領域）である。
【０１８５】
従って、現在のマッチング数M=0における、現在の基準領域２２１のうちの第１列乃至第４列のそれぞれと、現在の比較領域２２２−０のうちの第１列乃至第４列のそれぞれとの積和は、１つ前のマッチング数M=0における式（４）の右辺の演算結果（１つ前の基準領域２０１と、マッチング数M=0における１つ前の比較領域２０２−０との積和）の一成分として含まれていることになる。
【０１８６】
そこで、ΣAB乗算器１２２は、次のような簡単な手順で、マッチング数M=0における、現在の基準領域２２１と、比較領域２２２−０との積和、即ち、式（４）の右辺の演算を行うことができる。
【０１８７】
即ち、ΣAB乗算器１２２は、上述した差異のある領域に対する積和、即ち、図１４に示されるように、１つ前の基準領域２０１の第１列と、１つ前の比較領域２０２−０の第１列２３１−０との第１の積和と、現在の基準領域２２１の第５列と、現在の比較領域２２２−０の第５列２３２−０との第２の積和とを演算する。
【０１８８】
そして、ΣAB乗算器１２２は、１つ前のマッチング数M=0における式（４）の右辺の演算結果（１つ前の基準領域２０１と、マッチング数M=0における１つ前の比較領域２０２−０との積和）から、第１の積和を減算し、かつ、第２の積和を加算することで、マッチング数M=0における、現在の基準領域２２１と、比較領域２２２−０との積和の演算を行う（式（４）の右辺と等価な演算を行う）。
【０１８９】
ここで注目すべき点は、上述したように、ΣAB乗算器１２２は、１クロックで２列分の積和を演算することができるので、上述した第１の積和と第２の積和の演算を、１クロックで行うことができる、という点である。即ち、ΣAB乗算器１２２は、マッチング数M=0における、現在の基準領域２２１と、比較領域２２２−０との積和（即ち、式（４））の演算を、１クロックで行うことができる。
【０１９０】
以上、マッチング数M=0の場合についてのみ説明したが、他のマッチング数M=k（kは、０を除く、１乃至６３のうちのいずれかの整数値）においても、現在の基準領域２２１と、１つ前の基準領域２０１との位置関係や、現在の比較領域２２２−ｋと、１つ前の比較領域２０２−ｋとの位置関係は全く同様とされるので、マッチング数M=0の場合と全く同様な手順で、現在の基準領域２２１と、マッチング数M=kにおける比較領域２２２−ｋとの積和の演算（式（４）の右辺と等価な演算を行う）を、１クロックで行うことができる。
【０１９１】
即ち、ΣAB乗算器１２２は、上述した差異のある領域に対する積和、即ち、図１４に示されるように、１つ前の基準領域２０１の第１列と、１つ前の比較領域２０２−kの第１列２３１−kとの第１の積和と、現在の基準領域２２１の第５列と、現在の比較領域２２２−kの第５列２３２−kとの第２の積和を演算する。
【０１９２】
そして、ΣAB乗算器１２２は、１つ前のマッチング数M=kにおける式（４）の右辺の演算結果（１つ前の基準領域２０１と、マッチング数M=kにおける１つ前の比較領域２０２−kとの積和）から、第１の積和を減算し、かつ、第２の積和を加算することで、マッチング数M=kにおける、現在の基準領域２２１と、比較領域２２２−kとの積和の演算を行う。
【０１９３】
このようにして、２つ目の基準領域２２１に対する対応点検索処理（それに伴う、式（４）の右辺の演算処理）が実行されると、今度は、左画像（基準画像）１９１において、基準領域２２１の中心画素（これまでの注目画素）の右隣の画素（水平方向xaに１つずらした画素）、即ち、中心位置が座標(5,3)に位置する画素が新たな注目画素として設定されて、図１５に示されるように、その注目画素を中心とする５×５の領域が、３つ目の基準領域２４１として切り出されることになる。
【０１９４】
従って、ΣAB乗算器１２２は、今度は、この基準領域２４１を対象として、各マッチング数M=0乃至６３のそれぞれに対して、図１５に示されるような手順で式（４）の右辺の演算を実行する。即ち、図１５は、ΣAB乗算器１２２が、この基準領域２４１を対象として、各マッチング数M=0乃至６３のそれぞれに対して、式（４）の右辺の演算を実行する場合の手順を表している。
【０１９５】
図１４と図１５とを比較するに、現在の基準領域２４１と、１つ前の基準領域２２１との位置関係（図１５）は、１つ前の基準領域２２１と、さらに１つ前の基準領域２０１との位置関係（図１４）と全く同様とされる。同様に、現在の比較領域２４２−ｋと、１つ前の比較領域２２２−ｋとの位置関係（図１５）は、１つ前の比較領域２２２−ｋと、さらに１つ前の比較領域２０２−ｋとの位置関係（図１４）と全く同様とされる。
【０１９６】
従って、ΣAB乗算器１２２は、図１４を参照して説明した上述の手順と全く同様な手順で、現在の基準領域２４１と、比較領域２４２−ｋとの積和の演算を行うことができる。即ち、ΣAB乗算器１２２は、現在の基準領域２４１と、比較領域２４２−ｋとの積和の演算についても、１クロックで行うことができる。
【０１９７】
詳細には、ΣAB乗算器１２２は、差異のある領域に対する積和、即ち、図１５に示されるように、１つ前の基準領域２２１の第１列と、１つ前の比較領域２２２−kの第１列２５１−kとの第１の積和と、現在の基準領域２４１の第５列と、現在の比較領域２４２−kの第５列２５２−kとの第２の積和とを演算する。
【０１９８】
そして、ΣAB乗算器１２２は、１つ前のマッチング数M=kにおける式（４）の右辺の演算結果（１つ前の基準領域２２１と、マッチング数M=kにおける１つ前の比較領域２２２−kとの積和）から、第１の積和を減算し、かつ、第２の積和を加算することで、マッチング数M=kにおける、現在の基準領域２４１と、比較領域２４２−kとの積和（即ち、式（４））の演算を行う。
【０１９９】
その後、左画像（基準画像）１９１において、水平方向xaに沿って注目画素順次設定され、その注目画素を中心とする５×５の領域が、新たな基準領域として切り出される毎に、ΣAB乗算器１２２は、上述した手順（図１４と図１５に示される手順）と全く同様の手順で、マッチング数M=kにおける、現在の基準領域と、比較領域との積和の演算を行う。
【０２００】
即ち、ΣAB乗算器１２２は、マッチング数M=0乃至６３における、現在の基準領域と、比較領域との積和の演算を６４クロックで行うことができる。
【０２０１】
以上、説明したように、ΣAB乗算器１２２は、上述した手順（図１３乃至図１５に示される手順）に従ってその処理を実行することになる。この場合、ΣAB乗算器１２２は、その処理を実行するために、結局、所定の基準領域と所定の比較領域との積和のうちの２列分の積和の演算を行うことが可能で、かつ、１つ前の基準領域と、１つ前の各比較領域（マッチング数M=０乃至６３のそれぞに対する比較領域）のとの積和（即ち、式（４））の演算結果を保存することが可能な構成を有する必要がある。換言すると、ΣAB乗算器１２２は、このような構成を少なくとも有すれば、その形態は特に限定されない。
【０２０２】
例えば、ΣAB乗算器１２２をハードウエアで構成する場合、上述したように、基準領域と比較領域の列は、１×Nの小領域、即ち、N個の要素（画素）で構成されるので、１列分の積和のためには、N個の乗算器と、それらの加算を行う１つの加算器があればよい。即ち、２列分の積和のためには、2×N個の乗算器と、それらの加算のそれぞれを行う２つの加算器があればよい。また、１つ前の基準領域と、１つ前の各比較領域（マッチング数M=０乃至６３のそれぞに対する比較領域）のとの積和（即ち、式（４））の演算結果を保存するバッファが必要となる。
【０２０３】
従って、例えば、ΣAB乗算器１２２をハードウエアで構成する場合、2×N個の乗算器と、それらの加算のそれぞれを行う２つの加算器と、バッファとを少なくとも有すればよい。即ち、ハードウエアとして構成されるΣAB乗算器１２２は、これらの構成要素を有していれば、その構成は特に限定されない。
【０２０４】
具体的には、例えば、本実施の形態においては、ΣAB乗算器１２２は、図１６に示されるように構成されている。即ち、図１６は、本実施の形態のΣAB乗算器１２２の詳細な構成例を表している。
【０２０５】
図１６に示されるように、ΣAB乗算器１２２には、２×Ｎ（＝２×５）個の乗算器３０１−１１乃至乗算器３０１−５２が設けられている。
【０２０６】
これらの乗算器３０１−１１乃至乗算器３０１−５２のそれぞれが有する、２つの入力のうち一方の入力には、例えば、デュアルメモリのポート３０７−１乃至ポート３１１−２のうちのいずれかが接続され、また、他方の入力には、デュアルメモリのポート３０２−１乃至ポート３０６−２のうちのいずれかが接続される。
【０２０７】
即ち、例えば、いま、上述した図１３に示されるように、一番左の列（それを構成する５つの画素の中心）のxa座標Xが初期値X0（図１３の例では、X0＝１）となるように、左画像１９１から切り出された基準領域２０１が、処理の対象とされているとする。なお、図２に示されるように、基準領域の左上端の画素の位置は、座標(X,Y)とされている。そこで、以下においては、この左上端の画素の座標(X,Y)を基準とし、基準領域の左上端の画素のxa座標Xを用いて基準領域の位置を示すとする。即ち、以下、「左画像１９１から、左上端の画素のxa座標Xがkである５×５の領域が、基準領域として切り出された場合」のことを、単に、「X=kの場合」と記述する。
【０２０８】
具体的には、例えば、いま、乗算器３０１−１１乃至乗算器３０１−５２のうちの、図１６中一番上に図示される、乗算器３０１−１１と乗算器３０１−１２とに着目する。
【０２０９】
X=X0の場合、乗算器３０１−１１は、点線で示される列（例えば、マッチング数M=０における比較領域２０２−０のうちの、第２列２１２−０，第４列２１２−１等）の上端の画素の画素値（列の一番上）と、対応する位置の画素（対応する列の一番上の画素）の画素値との積を演算する（そのように、図１６のΣAB乗算器１２２は構成されている）。
【０２１０】
一方、X=X0の場合、乗算器３０１−１２は、図１３中、実線で示される列（例えば、マッチング数M=０における比較領域２０２−０のうちの、第１列２１１−０，第３列２１１−１，第５列２１１−２等）の上端の画素（列の一番上の画素）の画素値と、基準領域２０１のうちの、対応する位置の画素（対応する列の一番上）の画素値との積を演算する（そのように、図１６のΣAB乗算器１２２は構成されている）。
【０２１１】
また、図１３に示されるように、１クロックで２列分の積和が演算されるので、乗算器３０１−１１と乗算器３０１−１２は、同クロックに、相互に独立してその処理を実行することになる。
【０２１２】
従って、乗算器３０１−１１と乗算器３０１−１２のそれぞれに対して、基準領域２０１のうちの、対応する画素のそれぞれの画素値をほぼ同時に入力させ、かつ、比較領域２０２−０のうちの、対応する画素のそれぞれの画素値をほぼ同時に入力させる必要がある。
【０２１３】
そこで、本実施の形態のΣAB乗算器１２２には、乗算器３０１−１１と乗算器３０１−１２のそれぞれに対して、基準領域２０１のうちの、所定の２つの画素のそれぞれを同時に出力させることが可能な第１のデュアルポートメモリと、比較領域２０２−kのうちの、対応する画素のそれぞれの画素値をほぼ同時に出力させることが可能な第２のデュアルポートメモリが設けられている。
【０２１４】
ただし、第１のデュアルポートメモリ自身は図示されていなく、それらのうちの２つのポート３０２−１とポート３０２−２が図示されている。
【０２１５】
なお、ポート３０２−１とポート３０２−２のそれぞれに示されるau(p,0)とau(q,0)のそれぞれは、左画像（基準画像）１９１の座標系(xa,ya)における座標(p,0)と座標(q,0)のそれぞれに配置される画素の画素値を表している。
【０２１６】
ただし、上述した図１３乃至図１５の例では、基準領域の左上端の画素の位置を示すya座標Yはいずれも１とされるため、図１６においても、au(p,1)とau(q,1)と示されているが、実際には、図２に示されるように、基準領域の左上端の画素の位置を示すya座標Yは０とは限らない。即ち、au(p,1)とau(q,1)のうちのuは、基準領域の切り出し回数を表しているが、u回目に切り出された基準領域の左上端の座標(p,Y)，（q,Y）のそれぞれが、座標(p,1),(q,1)のそれぞれに座標変換された場合の画素の画素値の表現方法として、au(p,1),au(q,1)のそれぞれと示されている、と考えることもできる。
【０２１７】
同様に、第２のデュアルポートメモリ自身は図示されていなく、それらのうちの２つのポート３０７−１とポート３０７−２が図示されている。なお、ポート３０７−１とポート３０７−２のそれぞれに示されるb(r,1)とb(s,1)のそれぞれも、比較画像（右画像）１９２の座標系(xb,yb)における座標(r,1)と座標(s,1)のそれぞれに配置される画素の画素値（出力する画素値）を表している。
【０２１８】
この場合も、上述した図１３乃至図１５の例では、比較領域の左上端の画素の中心位置のyb座標はいずれも1とされるため、図１６においても、b(r,1)とb(s,1)と示されているが、実際には、図２に示されるように、基準領域の左上端の画素の位置を示すya座標Yは０とは限らない。即ち、u回目に切り出された基準領域に対する比較領域の左上端の座標(r,Y)，（s,Y）のそれぞれが、座標(r,1),(s,1)のそれぞれに座標変換された場合の画素の画素値の表現方法として、b(r,1),q(r,1)のそれぞれと示されている、と考えることもできる。
【０２１９】
このような、左上端の画素X=X0（＝１）における、ポート３０２−１，ポート３０２−２，ポート３０７−１，ポート３０７−２のそれぞれの、各時刻t毎の出力値（出力画素の画素値）が、図１７に示されている。
【０２２０】
また、X=X0以外の場合、乗算器３０１−１１は、図１４と図１５中、点線で示される列（例えば、図１４におけるマッチング数M=０においては、現在の比較領域２２２−０のうちの、第５列２３２−０）の上端の画素の画素値（列の一番上）と、現在の基準領域２２１のうちの、対応する位置の画素（対応する列の一番上）の画素値との積を演算する（そのように、図１６のΣAB乗算器１２２は構成されている）。
【０２２１】
一方、X=X0以外の場合、乗算器３０１−１２は、図１４と図１５中、実線で示される列（例えば、図１４におけるマッチング数M=０においては、１つ前の比較領域２０２−０のうちの、第１列２３１−０）の上端の画素（列の一番上の画素）の画素値と、１つ前の基準領域２０１のうちの、対応する位置の画素（対応する列の一番上の画素）の画素値との積を演算する（そのように、図１６のΣAB乗算器１２２は構成されている）。
【０２２２】
そこで、左上端の画素X=X0以外の場合、ポート３０２−１，ポート３０２−２，ポート３０７−１，ポート３０７−２のそれぞれは、図１８や図１９に示されるような画素値を出力する。即ち、図１８は、左上端の画素X=１の場合（図１４の場合）における、ポート３０２−１，ポート３０２−２，ポート３０７−１，ポート３０７−２のそれぞれの、各時刻t毎の出力値（出力画素の画素値）を示している。また、図１９は、左上端の画素X=２の場合（図１５の場合）における、ポート３０２−１，ポート３０２−２，ポート３０７−１，ポート３０７−２のそれぞれの、各時刻t毎の出力値（出力画素の画素値）を示している。
【０２２３】
図１６に戻り、それ以外の乗算器（乗算器３０１−２１乃至乗算器３０１−５１、および、乗算器３０１−２２乃至乗算器３０１−５２）についても、全く同様に、対応する第１のデュアルポートメモリと第２のデュアルポートメモリ（いずれも図示せず）のそれぞれの所定のポート（ポート３０３−１乃至ポート３０６−２のうちの所定の１つと、ポート３０８−１乃至ポート３１１−２のうちの所定の１つ）から出力される、基準領域内の所定の１つの画素値と、比較領域内の対応する１つの画素値とが入力される。
【０２２４】
このように、2×N個の乗算器３０１−１１乃至乗算器３０１−５２のそれぞれは、左画像１９１の基準領域を構成する各画素の画素値のうちの所定の１つと、右画像１９２の比較領域を構成する各画素のうちの所定の１つとの積を演算し出力する。
【０２２５】
2×N個のうちの、Ｎ個の乗算器３０１−１１乃至乗算器３０１−５１のそれぞれの出力は、加算器３２１−１に接続されている。即ち、加算器３２１−１は、Ｎ個の乗算器３０１−１１乃至乗算器３０１−５１のそれぞれの演算結果（積）の総和を出力する。
【０２２６】
即ち、Ｎ個の乗算器３０１−１１乃至乗算器３０１−５１のそれぞれと、加算器３２１−１とが図１６に示されるように接続された回路３５１が、基準領域と比較領域との積和のうちの所定の１列分を演算し、出力するともいえる。そこで、以下、回路３５１を、列積和演算回路３５１と称する。
【０２２７】
同様に、2×N個のうちの、Ｎ個の乗算器３０１−１２乃至乗算器３０１−５２のそれぞれの出力は、加算器３２１−２に接続されている。即ち、加算器３２１−２は、Ｎ個の乗算器３０１−１２乃至乗算器３０１−５２のそれぞれの演算結果（積）の総和を出力する。
【０２２８】
即ち、Ｎ個の乗算器３０１−１２乃至乗算器３０１−５２のそれぞれと、加算器３２１−２とが図１６に示されるように接続された回路３５２が、基準領域と比較領域との積和のうちの所定の１列分を演算し、出力するともいえる。そこで、以下、回路３５２を、列積和演算回路３５２と称する。
【０２２９】
即ち、ΣAB乗算器１２２には、２つの列積和演算回路３５１および列積和演算回路３５２が設けられている。これにより、ΣAB乗算器１２２は、上述した図１３乃至図１５の手順に従った処理を実行するために必要な、基準領域と比較領域との積和のうちの所定の２列分の演算成分（２列分の積和）を演算することができる。
【０２３０】
セレクタ３２２は、加算器３２１−１からの出力（列積和演算回路３５１からの出力）を、所定の条件が満たされた場合、セレクタ３２８に供給し、それ以外の場合、加算器３２３に供給する。
【０２３１】
即ち、X=X0の場合、各クロック毎に（時刻ｔ毎に）、実線で示される列２１１−ｔに対する１列分の積和と、点線で示される列２１２−ｔに対する１列分の積和の演算が必要とされる。
【０２３２】
そこで、図１６の例では、列積和演算回路３５１が、点線で示される列２１２−ｔに対する１列分の積和を演算し、列積和演算回路３５２が、実線で示される列２１１−ｔに対する１列分の積和を演算するように、ΣAB乗算器１２２が構成されている。
【０２３３】
ただし、図１３に示されるように、時刻t=5n+2（nは、0を含む任意の整数値）においては、点線で示される列２１２−ｔに対する１列分の積和は、現在の積和の対象とされている（マッチング数M=kにおける）比較領域２０２−ｋではなく、次の対象の（マッチング数M=k+1における）比較領域２０２−ｋ+1に対する積和に使用される。具体的には、時刻t=２においては、点線で示される列２１２−２に対する１列分の積和は、現在の積和の対象とされている（マッチング数M=０における）比較領域２０２−０ではなく、次の対象の（マッチング数M=１における）比較領域２０２−１に対する積和に使用される。
【０２３４】
このため、セレクタ３２２は、X=X0であって、かつ、時刻t=5n+2（nは、0を含む任意の整数値）の場合、加算器３２１−１からの出力（列積和演算回路３５１からの出力）を、次のマッチング数M=k+1で使用する値として、セレクタ３２８に供給し、それ以外の場合、現在のマッチング数M=kで使用する値として、加算器３２３に供給する。
【０２３５】
一方、セレクタ３２４は、加算器３２１−２からの出力（列積和演算回路３５２からの出力）を、所定の条件が満たされた場合、加算器３２３に供給し、それ以外の場合、減算器３２５に供給する。
【０２３６】
即ち、X=X0の場合（図１３で示される状態場合）、上述したように、列積和演算回路３５２は、実線で示される列２１１−ｔに対する１列分の積和を演算するように、ΣAB乗算器１２２が構成されている。この場合、上述したように、実線で示される列２１１−ｔに対する１列分の積和は、最終的な演算で加算される。
【０２３７】
これに対して、X=X0以外の場合（図１４や図１５で示される状態等の場合）、図１６の例では、列積和演算回路３５１が、点線で示される列２３２−ｋ、または、列２５２−ｋに対する１列分の積和を演算し、一方、列積和演算回路３５２が、実線で示される列２３１−ｋ、または、列２５１−ｋに対する１列分の積和を演算するように、ΣAB乗算器１２２が構成されている。この場合、上述したように、実線で示される列２３１−ｋ、または、列２５１−ｋに対する１列分の積和は、最終的な演算では減算される。
【０２３８】
そこで、セレクタ３２４は、X=X0の場合、加算器３２１−２からの出力（列積和演算回路３５２からの出力）をそのまま（プラスのまま）、加算器３２３に供給する。
【０２３９】
これに対して、セレクタ３２４は、X=X0以外の場合、加算器３２１−２からの出力（列積和演算回路３５２からの出力）を、減算器３２５に供給する。
【０２４０】
減算器３２５は、バッファ３２６から出力された値から、セレクタ３２４から出力された値（列積和演算回路３５２からの出力）を減算し、加算器３２３に供給する。
【０２４１】
即ち、このバッファ３２６が、１つ前の基準領域（切り出し回数Uの現在の基準領域の１つ前に切り出された、切り出し回数u-1の基準領域）と、１つ前の各比較領域（マッチング数M=０乃至６３のそれぞに対する比較領域）のとの積和（即ち、式（４）の右辺）の演算結果を保存するバッファである。
【０２４２】
従って、例えば、図１４に示されるような、左上端の座標X=1の場合、列積和演算回路３５２は、１つ前の基準領域２０１の第１列と、１つ前の比較領域２０２−kの第１列２３１−kとの第１の積和を演算し、セレクタ３２４を介して減算器３２５に供給する。
【０２４３】
すると、減算器３２５は、バッファ３２６より、１つ前のマッチング数M=kにおける式（４）の右辺の演算結果（１つ前の基準領域２０１と、マッチング数M=kにおける１つ前の比較領域２０２−kとの積和）を取得し、それから、セレクタ３２４から供給された第１の積和を減算し、その演算結果を加算器３２３に出力する。
【０２４４】
このとき、加算器３２３には、列積和演算回路３５２の演算結果、即ち、現在の基準領域２２１の第５列と、現在の比較領域２２２−kの第５列２３２−kとの第２の積和も、セレクタ３２２を介して供給されている。従って、加算器３２３は、結局、１つ前のマッチング数M=kにおける式（４）の右辺の演算結果（１つ前の基準領域２０１と、マッチング数M=kにおける１つ前の比較領域２０２−kとの積和）から、第１の積和を減算し、かつ、第２の積和を加算し、その演算結果を、マッチング数M=kにおける、現在の基準領域２２１と、比較領域２２２−kとの積和（即ち、式（４））をセレクタ３２７として出力するのである。
【０２４５】
セレクタ３２７は、X=X0の場合であって、t=2,4,7,9,12,14等のとき（即ち、t=5n+2若しくは5n+4のとき）、または、X=X0以外の場合、加算器３２３からの出力を、マッチング数M=kにおける、現在の基準領域と比較領域との積和（即ち、式（４）の右辺の演算結果）として、外部に出力するとともに、次に切り出される（u+1回目に切り出される）基準領域に対する演算のための参考データとして、バッファ３２６に記憶させる。
【０２４６】
これに対して、それ以外の場合、即ち、X=X0の場合、図１３に示されるように、t=0,1,2,3,5,6等のとき（即ち、t=5n+2と5n+4のうちのいずれでもないとき）、基準領域２０１と、所定の比較領域２０２−ｋとの積和に必要な全ての成分（列積和）がまだ演算されていない。
【０２４７】
即ち、このとき、加算器３２３の演算結果が、基準領域２０１と、所定の比較領域２０２−ｋとの積和のうちの、その時点までに演算された列積和の総和となっている。
【０２４８】
そこで、この列積和の総和を、次のクロックで列積和演算回路３５１と列積和演算回路３５２により演算される列積和に加算させるために、セレクタ３２７は、X=X0の場合であって、t=0,1,2,3,5,6等のとき（即ち、t=5n+2と5n+4のうちのいずれでもないとき）、加算器３２３からの出力を、セレクタ３２８に供給する。
【０２４９】
セレクタ３２８は、所定の条件が満たされた場合、セレクタ３２２からの出力を、ラインレジスタ（１つのD-フリップフロップ回路）３２９に供給する。
【０２５０】
即ち、上述したように、図１３に示されるように、時刻t=5n+2（nは、0を含む任意の整数値）においては、点線で示される列２１２−ｔに対する１列分の積和は、現在の積和の対象とされている（マッチング数M=kにおける）比較領域２０２−ｋではなく、次の対象の（マッチング数M=k+1における）比較領域２０２−ｋに対する積和に使用される。具体的には、時刻t=２においては、点線で示される列２１２−２に対する１列分の積和は、現在の積和の対象とされている（マッチング数M=０における）比較領域２０２−０ではなく、次の対象の（マッチング数M=１における）比較領域２０２−１に対する積和に使用される。
【０２５１】
このため、セレクタ３２２は、X=X0であって、かつ、時刻t=5n+2（nは、0を含む任意の整数値）の場合、加算器３２１−１からの出力（列積和演算回路３５１からの出力）を、セレクタ３２８に供給する。
【０２５２】
そこで、セレクタ３２８も、これに連動して、即ち、X=X0であって、かつ、時刻t=5n+2（nは、0を含む任意の整数値）の場合、セレクタ３２２からの出力（列積和演算回路３５１からの出力）を、ラインレジスタ３２９に供給する。
【０２５３】
これに対して、上述したように、セレクタ３２７は、X=X0の場合であって、かつ、t=0,1,2,3,5,6等のとき（即ち、t=5n+2と5n+4のうちのいずれでもないとき）、加算器３２３からの出力（即ち、基準領域２０１と、所定の比較領域２０２−ｋとの積和のうちの、その時点までに演算された列積和）を、セレクタ３２８に供給する。
【０２５４】
そこで、セレクタ３２８も、これに連動して、即ち、X=X0であって、かつ、t=0,1,2,3,5,6等のとき（即ち、t=5n+2と5n+4のうちのいずれでもないとき）、加算器３２３からの出力（基準領域２０１と、所定の比較領域２０２−ｋとの積和のうちの、その時点までに演算された列積和）を、ラインレジスタ３２９に供給する。
【０２５５】
ラインレジスタ３２９は、セレクタ３２８から供給されたデータを保持し、次のクロックで、セレクタ３３１に供給する。
【０２５６】
セレクタ３３１は、X=X0であって、t=5nの場合、演算対象のマッチング数Mが変化するため、レジスタ３３０に格納された０のデータを、加算器３２３に出力し、それ以外の場合、ラインレジスタ３２９より出力されるデータを、加算器３２３に加算する。
【０２５７】
このように、セレクタ３２２乃至セレクタ３３１が、図１６に示されるように接続された回路３５３は、列積和演算回路３５１と列積和演算回路３５３との演算結果に基づいて、所定の基準領域と、マッチング数Mにおける所定の比較領域との積和（式（４）の右辺の演算）を求めるための総合的な演算を行う回路であるといえる。そこで、以下、回路３５３を、総合演算回路３５３と称する。
【０２５８】
以上、図１２の画像マッチング部７７のうちの、本実施の形態のΣAB乗算器１２２の詳細な説明を行った。
【０２５９】
ところで、図１２において、除算器１２６からは、１つの基準領域（即ち、注目画素とされた所定の画素）に対して、マッチング回数（上述した例では、６４回分）分の相関値sが出力されてくるので、S2正規化相関値メモリ１２７は、これらの全ての相関値sを保存する。
【０２６０】
視差情報生成部１２８は、このS2正規化相関値メモリ１２７に保存された相関値sのうちの、所定の１つの基準領域（即ち、注目画素とされた所定の画素）に最も相関が高いことを示す相関値sを検索し、検索した相関値sが演算された比較領域の中心点（画素）を、注目画素の対応点として検出する。
【０２６１】
このとき、上述したように、視差情報生成部１２８は、注目画素の対応点に基づいて、様々な形態の視差情報を生成することができる。即ち、視差情報生成部１２８は、例えば、注目画素の配置位置と、対応点の配置位置との組そのもの、注目画素における視差を示す情報、または、対応点がどの設定点に対応するのかを示す情報等を生成することができる。
【０２６２】
そして、視差情報生成部１２８は、このようにして生成した視差情報を、距離演算部７８に供給する。
【０２６３】
なお、このとき、視差情報生成部１２８は、注目画素とされた画素毎に、視差情報を距離演算部７８に順次供給してもよいし、左画像（基準画像）１９１の全ての画素に対して、視差情報を生成した後、それらを一括して距離演算部７８に供給してよい。例えば、視差情報生成部１２８は、左画像１９１と同一サイズの画像を生成し、その画像の各画素のそれぞれの画素値として、左画像１９１の対応する画素に対して生成した視差情報を代入させ、その画像（以下、このような画像を、視差情報画像と称する）を距離演算部７８に供給することができる。
【０２６４】
次に、図２０を参照して、図５の画像処理システムが実行する処理（以下、ステレオビジョンシステムの処理と称する）について説明する。即ち、図２０は、ステレオビジョンシステムの処理の例を示すフローチャートである。
【０２６５】
ステップＳ１において、左画像変換部７２は、左画像出力部（左カメラ）７１より出力された画像に基づいて基準画像（左画像）を生成するとともに、右画像変換部７５は、右画像出力部（右カメラ）７４より出力された画像に基づいて比較画像（右画像）を生成する。
【０２６６】
即ち、本実施の形態では、上述したように、左画像出力部（左カメラ）７１より出力された画像そのものが、基準画像（左画像）とされる訳ではなく、レクティフィケーション（平行化）等の所定の画像処理が施された画像が、基準画像とされる。同様に、右画像出力部（右カメラ）７４より出力された画像そのものが、比較画像とされる訳ではなく、レクティフィケーション（平行化）等の所定の画像処理が施された画像が、比較画像とされる。
【０２６７】
基準画像と、比較画像とのそれぞれが画像マッチング部７７に供給されると、ステップＳ２において、画像マッチング部７７は、基準画像の各画素毎に（即ち、各画素のそれぞれを順次注目画素に設定し）、比較画像とのウィンドウマッチング処理を行い、その処理結果から各画素毎の対応点を検出し、検出した各画素毎の対応点に基づいて視差情報を生成する。
【０２６８】
視差情報が距離演算部７８に供給されると、ステップＳ３において、距離演算部７８は、その視差情報に基づいて、基準画像の各画素のそれぞれの距離を演算する。
【０２６９】
ところで、上述したステップＳ２の処理の最中、図１２のΣAB乗算器１２２は、上述した図１３乃至図１５に示される手順に従って、所定の基準領域と、所定の比較領域との積和の演算、即ち、上述した式（４）の右辺の演算を行っている。
【０２７０】
このような、ΣAB乗算器１２２の処理の詳細が、図２１のフローチャートに示されている。そこで、以下、図２１を参照して、ΣAB乗算器１２２の処理について説明する。
【０２７１】
なお、上述した説明にあわせて、ここでも、図２に示されるように、基準領域を構成する画素のうちの、左上端の画素の配置位置を示す、座標系(xa,ya)における座標(X,Y)を基準として、ΣAB乗算器１２２の処理について説明する。ただし、以下においては、図２１のフローチャートの記載にあわせて、左上端の画素のxa座標Xを、マッチング探索位置Xと称し、また、左上端の画素のya座標Yを、マッチング探索位置Yと称する。
【０２７２】
また、基準領域のサイズは、上述した例では、５×５とされたが、図２１のフローチャートにおいては、任意のサイズであるN×Nとされている。また、マッチング数Mの初期値は０とされていることは、上述した例と同様であるが、マッチング数Mの最大値は、上述した例では、６３とされていたのに対して、図２１のフローチャートにおいては、任意の値（ただし、左画像の横サイズ以下）であるMmaxとされている。即ち、図２１のフローチャートにおいては、マッチングの回数（１つの基準領域に対する式（４）の右辺の演算回数）は、Mmax+１とされている。
【０２７３】
はじめに、ステップＳ２１において、ΣAB乗算器１２２は、マッチング探索範囲の開始点を設定する（Y=Y0,X=X0に設定する）。
【０２７４】
ステップＳ２２において、ΣAB乗算器１２２は、X=X0であるか否かを判定する。
【０２７５】
ステップＳ２２において、ΣAB乗算器１２２は、X=X0であると判定した場合、ステップＳ２３において、マッチング数Mを０(M=0)に設定した後、ステップＳ２４において、図１３に示されるような手順に従って、基準領域と、マッチング数M=0における比較領域との積和（式（４）の右辺）を演算する。
【０２７６】
以下、このようなステップＳ２４の処理（図１３に示される手順に従って実行される処理）を、「X=X0におけるマッチング処理用のΣAB演算処理」と称する。なお、「X=X0におけるマッチング処理用のΣAB演算処理」の詳細については、図２２を参照して後述する。
【０２７７】
ΣAB乗算器１２２は、マッチング数M=0における「X=X0におけるマッチング処理用のΣAB演算処理」を終了させると、ステップＳ２５において、マッチング数M＝Mmaxではないと判定し、ステップＳ２６において、マッチング数MをM+1に更新する（新M=旧M+1）。
【０２７８】
その後、処理はステップＳ２４に戻され、それ以降の処理が繰り返される。即ち、マッチング数M=０乃至Mmaxのそれぞれにおける、「X=X0におけるマッチング処理用のΣAB演算処理」が繰り返し実行される。
【０２７９】
そして、最後のマッチング数M=Mmaxにおける、「X=X0におけるマッチング処理用のΣAB演算処理」を終了させると（ステップＳ２５において、M=Mmaxであると判定すると）、ΣAB乗算器１２２は、ステップＳ２７において、X=Xmaxであるか否かを判定する。
【０２８０】
なお、ここでは、マッチング探索位置Xは、水平方向xa（基準画像（左画像）の右方向）にスライドされていくので、最右端と設定された位置、或いは、実際の最右端となる位置を、Xmaxと記述している。
【０２８１】
いまの場合、マッチング探索位置X=X0であるので、ΣAB乗算器１２２は、ステップＳ２７において、X=Xmaxではないと判定し、ステップＳ２８において、マッチング探索位置XをX+1に更新する（新X=旧X+1）。即ち、新たな注目画素として、現在の注目画素である第１の画素から、水平方向xa（基準画像（左画像）の右方向）に１つスライドされた（第１の画素の右隣の）第２の画素に設定される。そして、この第２の画素を中心とするN×Nの領域が、新たな基準領域として切り出される。換言すると、基準領域が、水平方向xa（基準画像（左画像）の右方向）に１画素分スライドされる。
【０２８２】
その後、処理はステップＳ２２に戻され、ステップＳ２２において、X=X0ではないと判定され、処理はステップＳ２９に進められる。
【０２８３】
即ち、ΣAB乗算器１２２は、ステップＳ２２において、X=X0ではないと判定した場合、ステップＳ２９において、マッチング数Mを０(M=0)に設定した後、ステップＳ３０において、図１４や図１５に示されるような手順（いまの場合、X=X0+1なので、図１４に示される手順）に従って、基準領域と、マッチング数M=0における比較領域との積和（式（４）の右辺）を演算する。
【０２８４】
以下、このようなステップＳ３０の処理（図１４や図１５に示されるような手順に従って実行される処理）を、「マッチング処理用のΣAB演算処理」と称する。なお、「マッチング処理用のΣAB演算処理」の詳細については、図２３を参照して後述する。
【０２８５】
ΣAB乗算器１２２は、M=0における「マッチング処理用のΣAB演算処理」を終了させると、ステップＳ３１において、マッチング数M＝Mmaxではないと判定し、ステップＳ３２において、マッチング数MをM+1に更新する（新M=旧M+1）。
【０２８６】
その後、処理はステップＳ３０に戻され、それ以降の処理が繰り返される。即ち、マッチング数M=０乃至Mmaxのそれぞれに対して、X=X0+1における「マッチング処理用のΣAB演算処理」が繰り返し実行される。
【０２８７】
そして、最後のマッチング数M=Mmaxに対して、X=X0+1における「マッチング処理用のΣAB演算処理」を終了させると（ステップＳ３１において、M=Mmaxであると判定すると）、ΣAB乗算器１２２は、ステップＳ２７において、X=Xmaxであるか否かを判定する。
【０２８８】
いまの場合、X=X0+1であるので、ステップＳ２７において、X=Xmaxではないと判定されて、それ以降の処理が繰り返される。即ち、X=X0+2乃Xmaxのそれぞれにおける、マッチング数M=０乃至Mmaxのそれぞれに対する「マッチング処理用のΣAB演算処理」が繰り返し実行される。
【０２８９】
そして、ΣAB乗算器１２２は、最後のマッチング探索位置Xmaxにおける、マッチング数M=０乃至Mmaxのそれぞれに対する「マッチング処理用のΣAB演算処理」を終了させると、ステップＳ２７において、X=Xmaxであると判定し、ステップＳ３３において、Y=Ymaxであるか否かを判定する。
【０２９０】
なお、ここでは、マッチング探索位置Yは、垂直方向xa（基準画像（左画像）の下方向）にスライドされていくので、最下端と設定された位置、或いは、実際の再下端の位置を、Ymaxと記述している。
【０２９１】
いまの場合、マッチング探索位置Y=Y0であるので、ΣAB乗算器１２２は、ステップＳ２７において、Y=Ymaxではないと判定し、ステップＳ３４において、マッチング探索位置YをY+1に更新する（新Y=旧Y＋１）とともに、マッチング探索位置Xを開始点に設定する(X=X0)。
【０２９２】
即ち、新たな注目画素として、現在の注目画素である第１の画素から、垂直方向ya（基準画像（左画像）の下方向）に１つスライドされ、かつ、水平方向xaの逆方向（基準画像（左画像）の左方向）に左端（或いは、左端と設定された場所）までスライドされた第２の画素に設定される。そして、この第２の画素を中心とするN×Nの領域が、新たな基準領域として切り出される。換言すると、基準領域が、垂直方向ya（基準画像（左画像）の下方向）に１画素分スライドされるとともに、水平方向xaの逆方向（基準画像（左画像）の左方向）に左端（或いは、左端と設定された場所）までスライドされる。
【０２９３】
その後、処理はステップＳ２２に戻され、それ以降の処理が繰り返される。
【０２９４】
即ち、今度は、マッチング探索位置Y=Y0+1に対して、マッチング探索位置X=X0における、マッチング数M=０乃至Mmaxのそれぞれに対する「X=X0におけるマッチング処理用のΣAB演算処理」と、マッチング探索位置X=X1乃至Xmaxのそれぞれにおける、マッチング数M=０乃至Mmaxのそれぞれに対する「マッチング処理用のΣAB演算処理」が繰り返し実行される。
【０２９５】
同様に、マッチング探索位置Y=Y0+2乃至Ymaxのそれぞれに対しても、マッチング探索位置X=X0における、マッチング数M=0乃至Mmaxのそれぞれに対する「X=X0におけるマッチング処理用のΣAB演算処理」と、マッチング探索位置X=X1乃至Xmaxのそれぞれにおける、マッチング数M=０乃至Mmaxのそれぞれに対する「マッチング処理用のΣAB演算処理」が繰り返し実行されると、即ち、全画素（或いは、設定された全画素）の処理が実行されると、ステップＳ３３において、Y=Ymaxであると判定され、ΣAB乗算器の処理は終了となる。
【０２９６】
次に、図２２を参照して、「X=X0におけるマッチング処理用のΣAB演算処理（図２１のステップＳ２４の処理）」の詳細について説明する。
【０２９７】
はじめに、ステップＳ５１において、ΣAB乗算器１２２は、演算補正位置Iを０に初期設定し、演算途中結果Sを０に初期設定する(I=0,S=0)。なお、演算補正位置Iと、演算途中結果Sとのそれぞれについては後述する。
【０２９８】
ステップＳ５２において、ΣAB乗算器１２２は、比較領域のうちの、xb座標(X0+M+I)である列（小領域）に対応する列積和S1を演算する。
【０２９９】
即ち、ΣAB乗算器１２２は、次の式（７）の右辺を演算することで、列積和S1を演算する。
【０３００】
【数７】
2005084698.tif 000009
・・・（７）
【０３０１】
また、ステップＳ５３において、ΣAB乗算器１２２は、比較領域のうちの、xb座標(X0+M+I+1)である列（小領域）に対応する列積和S2を演算する。
【０３０２】
即ち、ΣAB乗算器１２２は、次の式（８）の右辺を演算することで、列積和S2を演算する。
【０３０３】
【数８】
2005084698.tif 000010
・・・（８）
【０３０４】
具体的には、例えば、いま、ΣAB乗算器１２２は、上述した図１３に示されるように、基準領域２０１と、M=0における比較領域２０２−０との組に対する積和（式（４）の右辺）を演算するとする。
【０３０５】
この場合、t=0においては、演算補正位置I=0に設定され、演算途中結果Sも０に設定されている。また、X0＝１，Y=0，N=5とされている。
【０３０６】
従って、ステップＳ５２の処理では、基準領域２０１の第１列と、比較領域２０２−０の第１列２１１−０（即ち、xb座標（１（＝X0+M+I＝１+0+0））である列２１１−０）との積和（列積和）S1が演算される。
【０３０７】
また、ステップＳ５３の処理では、基準領域２０１の第２列と、比較領域２０２−０の第２列２１２−０（即ち、xb座標（２（＝X0+M+I+1＝1+0+0+1））である列２１２−０）との積和（列積和）S2が演算される。
【０３０８】
なお、上述したように、これら２つの列積和S1と列積和S2のそれぞれは、並行して（独立して）演算されるので、ステップＳ５２とＳ５３の処理の順番は、特に図２２の例に限定されないことになる。
【０３０９】
その後、ステップＳ５４において、ΣAB乗算器１２２は、演算途中結果Ｓを更新する（新S＝旧S＋S1＋S2）。
【０３１０】
ステップＳ５５において、ΣAB乗算器１２２は、I=N-1であるか否かを判定する。
【０３１１】
いまの場合、I=0であるので、ΣAB乗算器１２２は、ステップＳ５５において、I=N-1ではないと判定し、ステップＳ５６において、演算補正位置Iを更新する(新I=旧I+2)。その後、処理は、ステップＳ５２に戻され、それ以降の処理が繰り返される。
【０３１２】
即ち、いまの場合、演算補正位置Iは２に更新されるので、ステップＳ５２の処理では、基準領域２０１の第３列と、比較領域２０２−０の第３列２１１−１（即ち、xb座標（３（＝X0+M+I＝1+0+2））である列２１１−１）との積和（列積和）S1が演算される。
【０３１３】
また、ステップＳ５３の処理では、基準領域２０１の第４列と、比較領域２０２−０の第４列２１２−１（即ち、xb座標（４（＝X0+M+I+1＝1+0+2+1））である列２１２−１）との積和（列積和）S2が演算される。
【０３１４】
そして、ステップＳ５４の処理で、演算途中結果Ｓが、Ｓ＝Ｓ＋Ｓ１＋Ｓ２に更新される。即ち、図１３に示されるように、時刻t=1までの演算結果の総和（第１列乃至第４列までの列積和の総和）が、演算途中結果Ｓとなる。
【０３１５】
いまの場合、演算補正値Iは２に設定されているので、その後、ステップＳ５５において、I=N-1ではないと判定され、ステップＳ５６において、演算補正位置Iは４に更新される。
【０３１６】
そして、ステップＳ５２の処理では、基準領域２０１の第５列と、比較領域２０２−０の第５列２１１−２（即ち、xb座標（５（＝X0+M+I＝1+0+4））である列２１１−２）との積和（列積和）S1が演算される。
【０３１７】
ただし、xb座標（６（＝X0+M+I+1＝1+0+4+1））である列は、比較領域２０２−０には含まれないので、ステップＳ７３の処理は実行されない（実際には、上述したように、このとき、次のマッチング数m=1の第１列目に対する処理として実行される）。即ち、このような場合、列積和S2=0として取り扱われる。
【０３１８】
そして、ステップＳ５４の処理で、演算途中結果Ｓが、Ｓ＝Ｓ＋Ｓ１＋Ｓ２に更新される。即ち、図１３に示されるように、時刻t=２までの演算結果（マッチング数M=1の分は除く）の総和（第１列乃至第５列までの列積和の総和）が、演算途中結果Ｓとなる。
【０３１９】
このとき、演算補正値Iは４に設定されているので、ΣAB乗算器１２２は、ステップＳ５５において、I=N-1(=5-1=4)であると判定し、ステップＳ５７において、現時点の演算途中結果Sを、最終的な演算結果W(X0,Y,M)として（W(X0,Y,M)＝S）として出力する。
【０３２０】
なお、このとき出力される最終的な演算結果W(X0,Y,M)は、結局、次の式（９）を演算した結果と等価となる。
【０３２１】
【数９】
2005084698.tif 000011
・・・（９）
【０３２２】
以上の処理で、「X=X0におけるマッチング処理用のΣAB演算処理（図２１のステップＳ２４の処理）」は終了となり、処理は、上述した図２１のステップＳ２５に進められる。
【０３２３】
次に、図２３を参照して、「マッチング処理用のΣAB演算処理（図２１のステップＳ３０の処理）」の詳細について説明する。
【０３２４】
はじめに、ステップＳ７１において、ΣAB乗算器１２２は、現在の基準領域に対する比較領域のうちの、第５列、即ち、xb座標(X+N-1+M)である列（小領域）に対応する列積和S1を演算する。
【０３２５】
詳細には、ΣAB乗算器１２２は、次の式（１０）の右辺を演算することで、列積和S1を演算する。
【０３２６】
【数１０】
2005084698.tif 000012
・・・（１０）
【０３２７】
また、ステップＳ７２において、ΣAB乗算器１２２は、１つ前の基準領域に対する比較領域のうちの、第１列、即ち、xb座標((X-1)+M)である列（小領域）に対応する列積和S2を演算する。なお、ここでは、Xは、現在のマッチング探索範囲、即ち、現在の比較領域の１列目のxb座標値を表している。従って、１つ前の基準領域に対応するマッチング探索範囲、即ち、１つ前のウィンドウに対する比較領域のうちの第１列のxb座標値は、X-1と表される。
【０３２８】
詳細には、ΣAB乗算器１２２は、次の式（１１）の右辺を演算することで、列積和S2を演算する。
【０３２９】
【数１１】
2005084698.tif 000013
・・・（１１）
【０３３０】
具体的には、例えば、いま、ΣAB乗算器１２２は、上述した図１４に示されるように、現在の基準領域２２１と、M=0における現在の比較領域２２２−０との組に対する積和（式（４）の右辺）を演算するとする。
【０３３１】
この場合、１つ前の基準領域は領域２０１とされ、１つ前のその基準領域２０１に対する、M=0における比較領域は、領域２０２−０とされる。また、マッチング探索位置X＝2，Y=0，N=5とされている。
【０３３２】
従って、ステップＳ７１の処理では、現在の基準領域２２１の第５列と、比較領域２２２−０の第５列２３２−０（即ち、xb座標（６＝X+N-1+M＝2+5-1+0））ある列２３２−０）との積和（列積和）S1が演算される。
【０３３３】
また、ステップＳ７２の処理では、1つ前の基準領域２０１の第１列と、比較領域２０２−０の第１列２３１−０（即ち、xb座標（１（＝(X-1)+M＝(2-1)+1））である列２３１−０）との積和（列積和）S2が演算される。
【０３３４】
そして、ステップＳ７３において、ΣAB乗算器１２２は、１つ前の基準領域の演算結果W(X-1,Y,M)を読み出す（いまの場合、基準領域２０１の演算結果W(X0,Y,M)を読み出す）。
【０３３５】
なお、このとき読み出される演算結果W(X-1,Y,M)は、結局、次の式（１２）を演算した結果と等価となる。
【０３３６】
【数１２】
2005084698.tif 000014
・・・（１２）
【０３３７】
そして、ステップＳ７４において、ΣAB乗算器１２２は、１つ前の基準領域の演算結果W(X-1,Y,M)に対して、列積和S1を加算し、かつ、列積和S2を減算した値を、演算結果W(X,Y,M)として（W(X,Y,M)＝W(X-1,Y,M)+S1-S2）として出力する。
【０３３８】
なお、このとき出力される演算結果W(X,Y,M)は、結局、次の式（１３）を演算した結果と等価となる。
【０３３９】
【数１３】
2005084698.tif 000015
・・・（１３）
【０３４０】
以上の処理で、「マッチング処理用のΣAB演算処理（図２１のステップＳ３０の処理）」は終了となり、処理は、上述した図２１のステップＳ３１に進められる。
【０３４１】
なお、上述したように、図１６の構成のΣAB乗算器１２２においては、減算される列積和S2は、列積和演算回路３５２により行われ、セレクタ３２４を介して、減算器３２５に供給される。このとき、この減算器３２５には、１つ前の基準領域の演算結果W(X-1,Y,M)が入力されており、結局、減算器３２５が、W(X-1,Y,M)-S2の演算を実行して、その演算結果（=W(X-1,Y,M)−S2）を加算器３２３に供給する。そして、加算器３２３が、減算器３２５より供給されたこの演算結果（=W(X-1,Y,M)-S2）と、列積和演算回路３５１より供給された列積和S1とを加算することで、最終的な演算結果W(X,Y,M)を算出し、出力している。
【０３４２】
即ち、最終的な演算結果W(X,Y,M)が出力されれば、「マッチング処理用のΣAB演算処理（図２１のステップＳ３０の処理）」の処理の順番は、図２３の例に限定されず、いずれの順番とされてもよい。
【０３４３】
以上、画像マッチング部７７は、式（１）で示される正規化相関関数を利用するとして説明した。このため、画像マッチング部７７は、例えば、図１２に示されるように構成されている。
【０３４４】
しかしながら、上述したように、画像マッチング部７７は、式（２）で示されるＳＳＤや、式（３）で示されるＳＡＤを利用することも勿論可能である。
【０３４５】
この場合、画像マッチング部７７は、ＳＳＤやＳＡＤの演算も、上述した一連の処理（手順）と全く同様に実行することができる。即ち、図２４と図２５に示されるように、図１６のΣAB乗算器１２２と基本的に同様の構成、即ち、２×N個の演算器と、１つ前の基準領域の演算結果を保存するバッファとを有する構成として実現可能である。
【０３４６】
具体的には、ＳＳＤを演算する回路は、図２４に示されるように、ＳＡＤを演算する回路は、図２５に示されるように、それぞれ構成することができる。即ち、図２４は、本実施の形態のＳＳＤを演算する回路の構成例を表しており、図２５は、本実施の形態のＳＡＤを演算する回路の構成例を表している。
【０３４７】
図１６と図２４とを比較するに、図２４のＳＳＤを演算する回路においては、図１６の１０個（２×Ｎ＝２×５個）の、「Mul」として示される乗算器３０１−１１乃至乗算器３０１−５２のそれぞれの代わりに、１０個（２×Ｎ＝２×５個）の、「SubSQ」として示される演算器４０１−１１乃至演算器４０１−５２のそれぞれが接続されている。即ち、これらの演算器４０１−１１乃至演算器４０１−５２のそれぞれは、基準領域を構成する画素のうちの所定の１つの画素の画素値aiから、比較領域を構成する画素のうちの対応する画素の画素値biを減算し、その自乗を演算する回路である。
【０３４８】
同様に、図１６と図２５とを比較するに、図２５のＳＡＤを演算する回路においては、図１６の１０個（２×Ｎ＝２×５個）の、「Mul」として示される乗算器３０１−１１乃至乗算器３０１−５２のそれぞれの代わりに、１０個（２×Ｎ＝２×５個）の、「SubAbs」として示される演算器４１１−１１乃至演算器４１１−５２のそれぞれが接続されている。即ち、これらの演算器４１１−１１乃至演算器４１１−５２のそれぞれは、基準領域を構成する画素のうちの所定の１つの画素の画素値aiから、比較領域を構成する画素のうちの対応する画素の画素値biを減算し、その絶対値を演算する回路である。
【０３４９】
従って、結局のところ、次の式（１４）の演算は、上述した一連の処理（手順）と全く同様に実行することができ、また、それを演算する回路は、図１６と全く同様に構成することが可能である。ただし、この場合、図１６の１０個（２×Ｎ＝２×５個）の、「Mul」として示される乗算器３０１−１１乃至乗算器３０１−５２のそれぞれの代わりに、１０個（２×Ｎ＝２×５個）の、関数f(ai,bi)を演算する演算回路（図示せず）が接続される。
【０３５０】
【数１４】
2005084698.tif 000016
・・・（１４）
【０３５１】
なお、以下、上述した図１６のΣAB乗算器１２２、図２４のＳＳＤを演算する回路、および、図２５のＳＡＤを演算する回路も含めて、式（１４）の右辺の演算を行う画像処理装置を、Σf(ai,bi)演算装置と称する。
【０３５２】
即ち、例えば、いま、第１の画像（例えば、図５の左カメラ７１から出力され、左画像変換部７２を介して供給された、図１４の左画像１９１）から、N×Nの基準領域（例えば、図１４の基準領域２２１）が切り出され、かつ、第２の画像（例えば、図５の右カメラ７４から出力され、右画像変換部７５を介して供給された、図１４の右画像１９２）から、N×Nの比較領域（例えば、図１４の比較領域２２２−０）が切り出されるとする。
【０３５３】
この場合、Σf(ai,bi)演算装置は、その基準領域とその比較領域との組に対する第１の値として、式（１３）のΣの中の関数f(ai,bi)に対して、変数aiとして、その基準領域を構成する各画素のそれぞれの画素値を代入し、かつ、変数biとして、その比較領域を構成する画素のうちの、対応する場所に位置する各画素のそれぞれの画素値を代入したときに得られる、関数f(ai,bi)のN×N個の出力値の総和（例えば、式（１４）の右辺）である第１の値を演算することになる。
【０３５４】
このようなΣf(ai,bi)演算装置（画像処理装置）として、次のような３つの構成を少なくとも適用すれば、上述した一連の処理（手順）と全く同様に、第１の値を算出する（式（１４）の右辺を演算したの等価な演算を行う）ことができる。
【０３５５】
即ち、図示はしないが、１つ目の構成要素は、Σf(ai,bi)演算装置（画像処理装置）自身により演算された、基準領域と比較領域との組に対する前記第１の値を記憶する記憶部である。
【０３５６】
２つ目の構成要素は、記憶部に、現在の第１の基準領域（例えば、図１４の基準領域２２１）と共通する画素を少なくとも含む第２の基準領域（例えば、図１４の基準領域２０１）と、第２の基準領域との相対的な位置関係が第１の基準領域と現在の第１の比較領域（例えば、図１４の比較領域２２２−０）との相対的な位置関係と同一の第２の比較領域（例えば、図１４の比較領域２０２−０）との組に対する第１の値が記憶されている場合、これから演算される、第１の基準領域と第１の比較領域との組に対する第１の値と、記憶部に記憶されている、第２の基準領域と第２の比較領域との組に対する第１の値との差異（例えば、図１４において、１つ前の比較領域２０２−０のうちの、第１列（小領域）２３１−０に対応する部分の演算成分、および、現在の比較領域２２２−０のうちの、第５列（小領域）２３２−０に対応する部分の演算成分）に相当する第２の値を演算する第１の演算部である。
【０３５７】
そして、３つ目の構成要素は、記憶部に記憶された、第２の基準領域と第２の比較領域との組に対する第１の値と、第１の演算部により演算された第２の値とに基づいて、第１の基準領域と第１の比較領域との組に対する第１の値を演算する第２の演算部である。
【０３５８】
なお、以下、このような３つの構成を少なくとも有するΣf(ai,bi)演算装置を、従来のΣf(ai,bi)演算装置（画像処理装置）と区別するために、本実施の形態のΣf(ai,bi)演算装置と称する。
【０３５９】
本実施の形態のΣf(ai,bi)演算装置をハードウエアで構成すれば、処理時間の増加を抑えつつ、関数f(ai,bi)を演算する演算回路（乗算器等）の数を効果的に減らすことができる。即ち、Σf(ai,bi)演算装置は、小さい回路規模のハードウエアとして容易に実現可能であり、かつ、大きな基準領域サイズのウィンドウマッチングの処理を実行することができる。
【０３６０】
具体的には、例えば、マッチング回数m（＝マッチング数M+1）が６４回、基準画像（比較画像）のサイズ(=W×H)が320x240とされ、基準領域のサイズ(=N×N)が11x11とされた場合、従来の画像処理装置（例えば、図４のΣAB乗算器５２に対応する装置）においては、関数f(ai,bi)の演算器は121(=11×11)個必要となる。
【０３６１】
また、この場合、従来のΣf(ai,bi)演算装置の処理時間は、一般的に、クロックを単位とすると、H×｛(W-m-xo)×m＋(m+1)×m/2｝［クロック］で表される。即ち、基準画像の右部分が注目画素とされた場合、64回のマッチングのうち後半については、比較領域が存在しなくなるため（基準領域を比較画像上をスライドさせると考えると、基準領域がその比較画像の外に出てしまうため）、X=256以降においては、64乃至0と順々にマッチング回数が減ってゆく。このため、１水平ラインあたりのマッチング回数は、W×mとはならず、(W-m-xo)×m＋(m+1)×m/2となる。なお、x0は、上述したマッチング開始点を示している。従って、具体的には、マッチング開始点x0=0とされると、いまの場合、4,431,360（=240x{(320-64-0)x64+(64+1)x64/2}［クロック］となる。
【０３６２】
これに対して、本実施の形態のΣf(ai,bi)演算装置では、関数f(ai,bi)の演算器は22(=2×11)個で済むことになる。
【０３６３】
また、処理時間においては、上述したマッチング探索開始位置X=X0の場合（初期状態の場合）のみ、1回のマッチングにN/2［クロック］かかり（即ち、m回のマッチングでN/2×m［クロック］かかり、この分が、従来よりも処理時間が多くかかることになる。しかしながら、この分の処理回数は、全体の処理回数から見て極わずかであり（画像のサイズが大きくなるほど、全体の処理に対する、この分の比率は少なくなり）、それ以外の場合（マッチング探索開始位置X=X0以外の場合）、１回のマッチングは１［クロック］で済むので、従来の処理時間に対してわずかな増加にとどめることが可能になる。
【０３６４】
具体的には、本実施の形態のΣf(ai,bi)演算装置の処理時間は、H×｛n/2×m＋(W-m-(xo-1))×m＋(m+1)×m/2｝［クロック］で表されるので、結局、4,500,480(=240x{11/2x64+(320-64-1)x64+(64+1)x64/2}［クロック］となる。
【０３６５】
このように、本実施の形態のΣf(ai,bi)演算装置は、従来のものと比較して、関数f(ai,bi)を演算する演算器の数を82%も減少させることができるにも関わらず、処理時間を約１%の増加のみで抑制させることが可能である。
【０３６６】
なお、本実施の形態のΣf(ai,bi)演算装置（画像処理装置）をハードウエアで構成する場合、バッファが必要となるが、そのバッファの必要な容量は、例えば、画素値が8bitの場合16bitx64=128byteとされる。
【０３６７】
なお、ハードウエアで構成された本実施の形態のΣf(ai,bi)演算装置が有する機能をソフトウエアで実現することも可能である。即ち、上述した一連の処理を、ソフトウエアで実行させることも勿論可能である。
【０３６８】
この場合、Σf(ai,bi)演算装置は、例えば、図２６に示されるようにパーソナルコンピュータとして構成することもできる。
【０３６９】
図２６において、CPU（Central Processing Unit）５０１は、ROM（Read Only Memory）５０２に記録されているプログラム、または記憶部５０８からRAM（Random Access Memory）５０３にロードされたプログラムに従って各種の処理を実行する。RAM５０３にはまた、CPU５０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０３７０】
CPU５０１、ROM５０２、およびRAM５０３は、バス５０４を介して相互に接続されている。このバス５０４にはまた、入出力インタフェース５０５も接続されている。
【０３７１】
入出力インタフェース５０５には、キーボードやマウス等よりなる入力部５０６、ディスプレイ等よりなる出力部５０７、ハードディスク等よりなる記憶部５０８、および、モデムやターミナルアダプタ等よりなり、ネットワーク等を介する他の情報処理装置との通信を制御する通信部５０９が接続されている。
【０３７２】
入出力インタフェース５０５にはさらに、必要に応じてドライブ５１０が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどよりなるリムーバブル記録媒体５１１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部５０８にインストールされる。
【０３７３】
一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウエアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、ネットワークや記録媒体からインストールされる。
【０３７４】
この記録媒体は、図２６に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フロッピディスクを含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（ＭＤ（Mini-Disk）を含む）、もしくは半導体メモリなどよりなるリムーバブル記録媒体（パッケージメディア）５１１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているROM５０２や、記憶部５０８に含まれるハードディスクなどで構成される。
【０３７５】
さらにまた、本実施の形態のΣf(a,b)演算装置は、上述した用途以外に限定されず、様々な用途に適用可能である。具体的には、例えば、本実施の形態のΣf(a,b)演算装置は、横（水平）方向の探索を終えた後、縦（垂直）方向の値をインクリメントして、再び水平方向の探索することを繰り返すことにより、水平方向だけの対応点の検索から、縦と横の２次元平面上での対応点の検索の用途に適用することが可能である。即ち、本実施の形態のΣf(a,b)演算装置は、ステレオ視のなど、２台のカメラの入力だけでなく、同一のカメラの異なる２つの時間の、動き補償などの対応点の検索等使用可能なことを意味する。
【０３７６】
なお、本明細書において、上述した一連の処理を実行するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０３７７】
また、本明細書において、システムとは、複数の装置や処理部により構成される装置全体を表すものである。
【図面の簡単な説明】
【０３７８】
【図１】ステレオ法について説明する図である。
【図２】図１のステレオ法において、対応点を求めるために必要な基準領域と、比較領域の構成例を示す図である。
【図３】従来の正規化相関値を演算する回路の構成例を示すブロック図である。
【図４】正規化相関値を演算するために必要な、ΣABを演算する回路の構成例を示す回路図である。
【図５】本実施の形態の画像処理システムの構成例を示すブロック図である。
【図６】ステレオ法を説明する図である。
【図７】ステレオ法における、ウィンドウマッチング手法を説明する図である。
【図８】ステレオ法における、ウィンドウマッチング手法を説明する図である。
【図９】ステレオ法における、ウィンドウマッチング手法を説明する図である。
【図１０】ステレオ法における、レクティフィケーション（平行化）を説明する図である。
【図１１】ステレオ法における、レクティフィケーション（平行化）を説明する図である。
【図１２】図５の画像処理システムのうちの、正規化相関値を利用する画像マッチング部の構成例を示すブロック図である。
【図１３】図１２の画像マッチング部のうちの、本実施の形態のΣAB乗算器の処理の手順を説明する図である。
【図１４】図１２の画像マッチング部のうちの、本実施の形態のΣAB乗算器の処理の手順を説明する図である。
【図１５】図１２の画像マッチング部のうちの、本実施の形態のΣAB乗算器の処理の手順を説明する図である。
【図１６】図１２の画像マッチング部のうちの、本実施の形態のΣAB乗算器の詳細な構成例を示す回路図である。
【図１７】図６のΣAB乗算器の各乗算器に入力される画素値の例を示す図である。
【図１８】図６のΣAB乗算器の各乗算器に入力される画素値の例を示す図である。
【図１９】図６のΣAB乗算器の各乗算器に入力される画素値の例を示す図である。
【図２０】図５の画像処理システムが実行するステレオビジョンシステムの処理例を説明するフローチャートである。
【図２１】図１２の画像マッチング部のうちの、本実施の形態のΣAB乗算器の処理の例を説明するフローチャートである。
【図２２】図２１の「X=X0におけるマッチング処理用のΣAB演算処理」の例の詳細な説明をするフローチャートである。
【図２３】図２１の「マッチング処理用のΣAB演算処理」の例の詳細な説明をするフローチャートである。
【図２４】図１６のΣAB乗算器に対する、本実施の形態のSSDを演算する回路の構成例を示す回路図である。
【図２５】図１６のΣAB乗算器に対する、本実施の形態のSADを演算する回路の構成例を示す回路図である。
【図２６】ΣABの演算、SSDの演算、または、SADの演算等を行う、本実施の形態の画像処理装置の他の形態の構成例を示すブロック図である。
【符号の説明】
【０３７９】
７１  画像マッチング部，  １２１  左右画像メモリ，  １２２  ΣAB乗算器１２２  ΣA2乗算器，  １２４  ΣB2乗算器，  １２５  乗算器，  １２６  除算器，  １２７  S2正規化相関値メモリ，  １２８  視差情報生成部，  １９１  基準画像（左画像），  １９２  比較画像（右画像），  ２０１  基準領域（ウィンドウ），  ２０２  比較領域，  ２１１，２１２  比較領域の列（小領域），  ２２１  基準領域（ウィンドウ），  ２２２  比較領域，  ２３１，２３２  比較領域の列（小領域），  ２４１  基準領域（ウィンドウ），  ２４２  比較領域，  ２５１，２５２  比較領域の列（小領域）．  ３０１  乗算器，  ３２６  バッファ，  ３５１，３５２  列積和演算回路，  ３５３  総合演算回路，  ４０１  演算器，  ４１１  演算器
【図１】
2005084698.tif 000017
【図２】
2005084698.tif 000018
【図３】
2005084698.tif 000019
【図４】
2005084698.tif 000020
【図５】
2005084698.tif 000021
【図６】
2005084698.tif 000022
【図７】
2005084698.tif 000023
【図８】
2005084698.tif 000024
【図９】
2005084698.tif 000025
【図１０】
2005084698.tif 000026
【図１１】
2005084698.tif 000027
【図１２】
2005084698.tif 000028
【図１３】
2005084698.tif 000029
【図１４】
2005084698.tif 000030
【図１５】
2005084698.tif 000031
【図１６】
2005084698.tif 000032
【図１７】
2005084698.tif 000033
【図１８】
2005084698.tif 000034
【図１９】
2005084698.tif 000035
【図２０】
2005084698.tif 000036
【図２１】
2005084698.tif 000037
【図２２】
2005084698.tif 000038
【図２３】
2005084698.tif 000039
【図２４】
2005084698.tif 000040
【図２５】
2005084698.tif 000041
【図２６】
2005084698.tif 000042