(57)【特許請求の範囲】
【請求項１】
同一のシーンをとらえた複数の入力画像のうち、１の入力画像を基準画像、他の入力画像を参照画像として取得する取得手段と、
前記基準画像に注目点を順次設定し、設定した注目点を含むように前記基準画像にウインドウを設定すると共に、前記参照画像にウインドウを設定し、前記参照画像に設定したウインドウをずらしながら、両ウインドウ内の画像の一致度を求めることで、前記参照画像から前記注目点の対応点を探索する探索手段と、
前記ウインドウ内に、前記入力画像の画像領域からはみ出した外領域が含まれているか否かを前記ウインドウがずらされる毎に判定する判定手段と、
前記判定手段により前記外領域が含まれていると判定された場合、前記ウインドウ内の入力画像の少なくとも端に位置する画素の画素値に基づいて、前記外領域の補間画素値を算出する補間手段とを備え、
前記補間手段は、前記ウインドウ内の入力画像の端の画素の画素平均値を前記補間画素値として算出し、前記外領域において、前記ウインドウの端に向かうにつれてなだらかに変化するように前記補間画素値を算出することを特徴とする対応点探索装置。
【請求項２】
同一のシーンをとらえた複数の入力画像のうち、１の入力画像を基準画像、他の入力画像を参照画像として取得する取得手段と、
前記基準画像に注目点を順次設定し、設定した注目点を含むように前記基準画像にウインドウを設定すると共に、前記参照画像にウインドウを設定し、前記参照画像に設定したウインドウをずらしながら、両ウインドウ内の画像の一致度を求めることで、前記参照画像から前記注目点の対応点を探索する探索手段と、
前記ウインドウ内に、前記入力画像の画像領域からはみ出した外領域が含まれているか否かを前記ウインドウがずらされる毎に判定する判定手段と、
前記判定手段により前記外領域が含まれていると判定された場合、前記ウインドウ内の入力画像の少なくとも端に位置する画素の画素値に基づいて、前記外領域の補間画素値を算出する補間手段とを備え、
前記補間手段は、前記ウインドウ内の入力画像を構成する各画素の画素平均値を前記補間画素値として算出し、前記外領域において、前記ウインドウの端に向かうにつれてなだらかに変化するように前記補間画素値を算出することを特徴とする対応点探索装置。
【請求項３】
同一のシーンをとらえた複数の入力画像のうち、１の入力画像を基準画像、他の入力画像を参照画像として取得する取得手段と、
前記基準画像に注目点を順次設定し、設定した注目点を含むように前記基準画像にウインドウを設定すると共に、前記参照画像にウインドウを設定し、前記参照画像に設定したウインドウをずらしながら、両ウインドウ内の画像の一致度を求めることで、前記参照画像から前記注目点の対応点を探索する探索手段と、
前記ウインドウ内に、前記入力画像の画像領域からはみ出した外領域が含まれているか否かを前記ウインドウがずらされる毎に判定する判定手段と、
前記判定手段により前記外領域が含まれていると判定された場合、前記ウインドウ内の入力画像の少なくとも端に位置する画素の画素値に基づいて、前記外領域の補間画素値を算出する補間手段とを備え、
前記補間手段は、前記ウインドウ内の入力画像の端に位置する各画素の画素平均値を基準として上下に一定のマージンを与えた値を前記補間画素値として算出することを特徴とする対応点探索装置。
【請求項４】
前記補間手段は、前記ウインドウ内の入力画像の端の位置において、前記画素平均値よりも画素値の高い画素の割合が、低い画素の割合より高い場合、前記画素平均値に一定のマージンを加えた値を前記補間画素値とし、その逆の場合、前記画素平均値から一定のマージンを差し引いた値を前記補間画素値とすることを特徴とする請求項３記載の対応点探索装置。
【請求項５】
同一のシーンをとらえた複数の入力画像のうち、１の入力画像を基準画像、他の入力画像を参照画像として取得する取得手段と、
前記基準画像に注目点を順次設定し、設定した注目点を含むように前記基準画像にウインドウを設定すると共に、前記参照画像にウインドウを設定し、前記参照画像に設定したウインドウをずらしながら、両ウインドウ内の画像の一致度を求めることで、前記参照画像から前記注目点の対応点を探索する探索手段と、
前記ウインドウ内に、前記入力画像の画像領域からはみ出した外領域が含まれているか否かを前記ウインドウがずらされる毎に判定する判定手段と、
前記判定手段により前記外領域が含まれていると判定された場合、前記ウインドウ内の入力画像の少なくとも端に位置する画素の画素値に基づいて、前記外領域の補間画素値を算出する補間手段とを備え、
前記補間手段は、前記ウインドウ内の入力画像の端に位置する各行の画素の画素値を、前記外領域の各行に対応する補間画素値として算出し、前記外領域において、前記ウインドウの端に向かうにつれてなだらかに変化するように前記補間画素値を算出することを特徴とする対応点探索装置。
【請求項６】
前記探索手段は、下位の階層から上位の階層に向かうにつれて解像度が高くなるように、解像度の異なる複数の前記基準画像及び前記参照画像を階層的に生成し、下位の階層での対応点の探索結果に基づいて、当該階層の探索範囲よりも小さな探索範囲を１つ上の階層の参照画像に設定し、当該探索範囲内で対応点を探索する探索処理を上位の階層に向けて階層的に実行することで対応点を探索することを特徴とする請求項１〜５のいずれかに記載の対応点探索装置。
【請求項７】
前記探索手段は、前記基準画像に設定したウインドウ内の画像と前記参照画像に設定したウインドウ内の画像とを相関演算することで前記一致度を算出することを特徴とする請求項１〜６のいずれかに記載の対応点探索装置。
【請求項８】
前記探索手段は、前記基準画像に設定したウインドウ内の画像と前記参照画像に設定したウインドウ内の画像とを周波数分解することで得られる位相成分に基づいて前記一致度を算出することを特徴とする請求項１〜７のいずれかに記載の対応点探索装置。
【請求項９】
前記探索手段は、高速フーリエ変換、離散フーリエ変換、離散コサイン変換、離散サイン変換、ウエーブレット変換、及びアダマール変換のいずれかを用いて周波数分解することを特徴とする請求項８記載の対応点探索装置。
【請求項１０】
前記探索手段は、位相限定相関法を用いて前記一致度を算出することを特徴とする請求項９記載の対応点探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、基準画像に設定された注目点の対応点を参照画像から探索する対応点探索装置に関するものである。
【背景技術】
【０００２】
近年、ステレオカメラを用いて物体を撮影し、得られた入力画像を用いて物体までの距離等を算出するステレオマッチングが知られている。ステレオマッチングでは、ステレオカメラにより撮影された複数の画像のうち、１の入力画像を基準画像、他の入力画像を参照画像とし、基準画像に注目点を設定し、設定した注目点を中心として基準画像にウインドウを設定すると共に、参照画像にも同じウインドウを設定し、両画像の一致度を求めることで、当該注目点の対応点を参照画像から探索する探索処理が採用される。
【０００３】
この探索処理において、ウインドウは、入力画像の端の方に設定されると、入力画像からはみ出してしまう。この場合、ウインドウ内に入力画像の画像領域からはみ出した外領域が含まれてしまい、入力画像と外領域との境界にエッジが現れ、画像が不連続に変化する結果、本来の対応点とは異なる点が対応点として探索される誤探索が発生し、対応点の探索精度が低下するという問題がある。
【０００４】
この問題を解決する手法として、以下に示す４つの従来手法が知られている。第１の従来手法は、ウインドウ内の画像をある領域から周辺に向かって所定のフィルタを用いてぼかすぼかし処理を行うことで不連続性を低減する手法である。第２の従来手法は、外領域の全域を、固定値（例えば０値）で埋める手法である（例えば、特許文献１）。第３の従来手法は、外領域が含まれないような位置に設定されたウインドウ内の入力画像の情報から補間画素値を予め求めておき、当該補間画素値を用いて外領域を設定する手法である。第４の手法は、入力画像をウインドウ内でミラー状に折り返すことによって外領域を埋める手法である。
【特許文献１】特開２００４−１０２３２３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、第１の従来手法では、フィルタを用いたぼかし処理が行われているため、演算量が増大すると共に、入力画像の情報を用いて外領域が補間されていないため、ウインドウ内の画像にエッジが現れ、誤探索が発生してしまう。また、第２の従来手法では、固定値と入力画像の端の画素の画素値との差が大きい場合、ウインドウ内の画像にエッジが現れ、誤探索が発生してしまう。
【０００６】
また、第３の従来手法では、ウインドウ内の入力画像の情報が補間画素値に全く反映されていないケースが発生し、この場合、ウインドウ内の画像にエッジが現れ、誤探索が発生してしまう。また、第４の従来手法では、外領域において、入力画像と逆パターンが現れているため、外領域内の点が対応点として探索されるおそれがある。
【０００７】
本発明の目的は、ウインドウが入力画像からはみ出して設定された場合であっても、演算コストを増大させることなく、対応点を精度良く探索することができる対応点探索装置を提供することである。
【課題を解決するための手段】
【０００８】
（１）本発明による対応点探索装置は、同一のシーンをとらえた複数の入力画像のうち、１の入力画像を基準画像、他の入力画像を参照画像として取得する取得手段と、前記基準画像に注目点を順次設定し、設定した注目点を含むように前記基準画像にウインドウを設定すると共に、前記参照画像にウインドウを設定し、前記参照画像に設定したウインドウをずらしながら、両ウインドウ内の画像の一致度を求めることで、前記参照画像から前記注目点の対応点を探索する探索手段と、前記ウインドウ内に、前記入力画像の画像領域からはみ出した外領域が含まれているか否かを前記ウインドウがずらされる毎に判定する判定手段と、前記判定手段により前記外領域が含まれていると判定された場合、前記ウインドウ内の入力画像の少なくとも端に位置する画素の画素値に基づいて、前記外領域の補間画素値を算出する補間手段とを備え、前記補間手段は、前記ウインドウ内の入力画像の端の画素の画素平均値を前記補間画素値として算出し、前記外領域において、前記ウインドウの端に向かうにつれてなだらかに変化するように前記補間画素値を算出することを特徴とする。
【０００９】
この構成によれば、対応点を探索するに際し、基準画像及び参照画像の両入力画像の端付近でウインドウが設定された場合に、ウインドウ内に含まれてしまう外領域が、ウインドウ内の入力画像の少なくとも端の画素の画素値に基づいて算出された補間画素値によって埋められる。そのため、外領域と入力画像との境界でのエッジの発生が抑制され、対応点を精度良く探索することができる。また、外領域に補間画素値を設定することで外領域が埋められているため、演算コストの増大を防止することができる。更に、基準画像及び参照画像の両入力画像に設定されるウインドウがずらされる毎に補間画素値が算出されるため、補間画素値は、ウインドウ内に含まれる入力画像の情報がより正確に反映された値になる結果、外領域と入力画像との境界におけるエッジの発生をより確実に抑制することができる。
また、この構成によれば、補間画素値の算出に用いられる画素が、ウインドウ内の入力画像の端の画素のみとなるため、高速に補間画素値を求めることができる。また、ウインドウ内の入力画像の端の画素の画素平均値が補間画素値として算出されるため、外領域と入力画像との境界におけるエッジの発生をより確実に抑制することができる。
また、この構成によれば、ウインドウの端に向かうにつれてなだらかに変化するように外領域に補間画素値が設定され、探索精度を高めることができる。
【００１１】
（２）本発明による別の対応点探索装置は、同一のシーンをとらえた複数の入力画像のうち、１の入力画像を基準画像、他の入力画像を参照画像として取得する取得手段と、前記基準画像に注目点を順次設定し、設定した注目点を含むように前記基準画像にウインドウを設定すると共に、前記参照画像にウインドウを設定し、前記参照画像に設定したウインドウをずらしながら、両ウインドウ内の画像の一致度を求めることで、前記参照画像から前記注目点の対応点を探索する探索手段と、前記ウインドウ内に、前記入力画像の画像領域からはみ出した外領域が含まれているか否かを前記ウインドウがずらされる毎に判定する判定手段と、前記判定手段により前記外領域が含まれていると判定された場合、前記ウインドウ内の入力画像の少なくとも端に位置する画素の画素値に基づいて、前記外領域の補間画素値を算出する補間手段とを備え、前記補間手段は、前記ウインドウ内の入力画像を構成する各画素の画素平均値を前記補間画素値として算出し、前記外領域において、前記ウインドウの端に向かうにつれてなだらかに変化するように前記補間画素値を算出することを特徴とする。
この構成によれば、ウインドウ内の入力画像の画素平均値が補間画素値として採用されているため、両ウインドウ内の画像の一致度が、両ウインドウ内の画像全域ではなく一部の領域を用いて局所的に算出されるような場合であっても、外領域と入力画像との境界におけるエッジの発生をより確実に抑制することができる。
【００１３】
（３）同一のシーンをとらえた複数の入力画像のうち、１の入力画像を基準画像、他の入力画像を参照画像として取得する取得手段と、前記基準画像に注目点を順次設定し、設定した注目点を含むように前記基準画像にウインドウを設定すると共に、前記参照画像にウインドウを設定し、前記参照画像に設定したウインドウをずらしながら、両ウインドウ内の画像の一致度を求めることで、前記参照画像から前記注目点の対応点を探索する探索手段と、前記ウインドウ内に、前記入力画像の画像領域からはみ出した外領域が含まれているか否かを前記ウインドウがずらされる毎に判定する判定手段と、前記判定手段により前記外領域が含まれていると判定された場合、前記ウインドウ内の入力画像の少なくとも端に位置する画素の画素値に基づいて、前記外領域の補間画素値を算出する補間手段とを備え、前記補間手段は、前記ウインドウ内の入力画像の端に位置する各画素の画素平均値を基準として上下に一定のマージンを与えた値を前記補間画素値として算出することを特徴とする。
この構成によれば、補間画素値の算出対象となる画素において、画素値が画素平均値より大きな画素の割合の方が、小さな画素の割合よりも高いような場合、或いは、低いような場合、画素平均値に上下にマージンを与えて補間画素値の値が調節されるため、外領域と入力画像との境界におけるエッジの発生をより確実に抑制することができる。
【００１４】
（４）また、前記補間手段は、前記ウインドウ内の入力画像の端の位置において、前記画素平均値よりも画素値の高い画素の割合が、低い画素の割合より高い場合、前記画素平均値に一定のマージンを加えた値を前記補間画素値とし、その逆の場合、前記画素平均値から一定のマージンを差し引いた値を前記補間画素値とすることが好ましい。この構成によれば、外領域と入力画像との境界におけるエッジの発生をより確実に抑制することができる。
【００１５】
（５）本発明による更に別の対応点探索装置は、同一のシーンをとらえた複数の入力画像のうち、１の入力画像を基準画像、他の入力画像を参照画像として取得する取得手段と、前記基準画像に注目点を順次設定し、設定した注目点を含むように前記基準画像にウインドウを設定すると共に、前記参照画像にウインドウを設定し、前記参照画像に設定したウインドウをずらしながら、両ウインドウ内の画像の一致度を求めることで、前記参照画像から前記注目点の対応点を探索する探索手段と、前記ウインドウ内に、前記入力画像の画像領域からはみ出した外領域が含まれているか否かを前記ウインドウがずらされる毎に判定する判定手段と、前記判定手段により前記外領域が含まれていると判定された場合、前記ウインドウ内の入力画像の少なくとも端に位置する画素の画素値に基づいて、前記外領域の補間画素値を算出する補間手段とを備え、前記補間手段は、前記ウインドウ内の入力画像の端に位置する各行の画素の画素値を、前記外領域の各行に対応する補間画素値として算出し、前記外領域において、前記ウインドウの端に向かうにつれてなだらかに変化するように前記補間画素値を算出することを特徴とする。
【００１６】
この構成によれば、ウインドウ内の入力画像の端の各行の画素の画素値を用いて各行の補間画素値が算出される。そのため、参照画像に設定したウインドウを１ライン分だけ注目点が位置する行と同一行にずらして対応点を探索する手法を採用した場合において、外領域での補間画素値の設定処理の高速化を図りつつ、外領域と入力画像との境界においてエッジの発生を抑制することができる。
【００１７】
（６）また、前記探索手段は、下位の階層から上位の階層に向かうにつれて解像度が高くなるように、解像度の異なる複数の前記基準画像及び前記参照画像を階層的に生成し、下位の階層での対応点の探索結果に基づいて、当該階層の探索範囲よりも小さな探索範囲を１つ上の階層の参照画像に設定し、当該探索範囲内で対応点を探索する探索処理を上位の階層に向けて階層的に実行することで対応点を探索することが好ましい。
【００１８】
この構成によれば、探索処理としていわゆる多重解像度戦略手法を採用した場合、外領域となる部分がより多く現れる低階層の入力画像において、エッジの発生をより軽減することが可能となり、対応点の探索精度を高めることができる。
【００１９】
（７）また、前記探索手段は、前記基準画像に設定したウインドウ内の画像と前記参照画像に設定したウインドウ内の画像とを相関演算することで前記一致度を算出することが好ましい。この構成によれば、一致度を精度良く算出することができる。
【００２０】
（８）また、前記探索手段は、前記基準画像に設定したウインドウ内の画像と前記参照画像に設定したウインドウ内の画像とを周波数分解することで得られる位相成分に基づいて前記一致度を算出することが好ましい。
【００２１】
この構成によれば、基準画像及び参照画像に設定したウインドウ内の両画像を周波数分解して得られる位相成分に基づいて一致度が算出されるため、画像間の輝度差やノイズの影響を受けにくい、ロバストな探索処理を実現することができる。
【００２２】
（９）また、前記探索手段は、高速フーリエ変換、離散フーリエ変換、離散コサイン変換、離散サイン変換、ウエーブレット変換、及びアダマール変換のいずれかを用いて周波数分解することが好ましい。
【００２３】
この構成によれば、ウインドウ内の画像が、ウインドウ内の画像を周波数分解する手法として、高速フーリエ変換、離散フーリエ変換、離散コサイン変換、離散サイン変換、ウエーブレット変換、及びアダマール変換のいずれかの手法が採用されるため、周波数分解を精度良く行うことができる。
【００２４】
（１０）また、前記探索手段は、位相限定相関法を用いて前記一致度を算出することが好ましい。この構成によれば、位相限定相関法を用いて対応点が探索されるため、対応点を精度良く探索することができる。
【発明の効果】
【００２５】
本発明によれば、ウインドウが入力画像からはみ出して設定された場合であっても、演算コストを増大させることなく、対応点を精度良く探索することができる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の一実施の形態により対応点探索装置について説明する。図１は、本対応点探索装置の概略構成図を示している。対応点探索装置は、２台のカメラＣ１，Ｃ２、及びコントローラ１０を備えている。
【００２７】
以下の説明では、本対応点探索装置を自動車等の車体に搭載した場合を例に挙げて説明するが、これは一例にすぎず、対応点を探索するような処理を行う装置であればどのような装置に搭載してもよい。
【００２８】
カメラＣ１，Ｃ２は、例えば車体の進行方向に直交し、かつ水平方向に平行な方向である左右方向に所定の間隔を設けて、進行方向を中心に対称となるように同一高さ位置に配設され、所定のフレームレートで車体の前方のシーンを撮影する。ここで、カメラＣ１，Ｃ２は、同一時刻においてフレームが撮影されるように撮影タイミングの同期が図られている。また、カメラＣ１，Ｃ２は予めキャリブレーションがされており、カメラパラメータも予め分かっているものとする。
【００２９】
なお、カメラＣ１，Ｃ２は２台としたが、これに限定されず３台以上のカメラを採用してもよい。また、時系列画像により物体の移動量を算出する場合や、撮影データと登録データとを比較するような場合においては、カメラの台数を１台にしてもよい。
【００３０】
コントローラ１０は、例えばＣＰＵ、ＲＯＭ、ＲＡＭ等を備えるハードウエア装置により構成され、通信ケーブル介してカメラＣ１，Ｃ２により撮影された画像を順次取り込む。なお、コントローラ１０は、無線によりカメラＣ１，Ｃ２から画像データを取り込んでも良い。
【００３１】
図２は、コントローラ１０の機能ブロック図を示している。コントローラ１０は、画像取得部１１（取得手段の一例）、設定部１２（探索手段の一例）、ウインドウ設定部１３（探索手段の一例）、判定部１４（判定手段の一例）、補間部１５（補間手段の一例）、及び探索処理部１６（探索手段の一例）を備える。
【００３２】
画像取得部１１は、カメラＣ１，Ｃ２により所定のフレームレートでシーンが撮影された２枚の入力画像を順次取得し、基準画像取得部１１ａ及び参照画像取得部１１ｂを備えている。基準画像取得部１１ａは、カメラＣ１から送信される入力画像を基準画像として順次取得する。参照画像取得部１１ｂは、カメラＣ２から送信される入力画像を参照画像として順次取得する。基準画像及び参照画像としては、例えば０（黒）〜２５５（白）の２５６階調値を有する複数の画素がマトリックス状に配列されたたデジタルの画像データを採用することができる。
【００３３】
設定部１２は、注目点設定部１２ａ及び中心点設定部１２ｂを備えている。注目点設定部１２ａは、基準画像取得部１１ａにより取得された基準画像に注目点を設定する。なお、注目点は対応点の探索対象となる基準画像上の画素を示す。ここで、注目点設定部１２ａは、例えば、基準画像上の全画素又は一定間隔で間引かれた所定の画素を、左上から右下に向けてラスタ走査するように順次注目点として設定する。
【００３４】
図３は、注目点の設定処理の説明図である。図３に示すように、格子状に区画された基準画像上の全画素又は一定間隔で間引かれた所定の画素が注目点ＣＰとして順次設定される。図３の例では、左上の画素が注目点ＣＰとして設定されている。
【００３５】
中心点設定部１２ｂは、参照ウインドウの中心点を参照画像に設定する。ここで、中心点設定部１２ｂは、注目点設定部１２ａにより１つの注目点が設定されている間に、参照画像上の各画素を例えば左上から右下に向けて順次ラスタ走査するように中心点として設定する。
【００３６】
ウインドウ設定部１３は、基準ウインドウ設定部１３ａ及び参照ウインドウ設定部１３ｂを備えている。基準ウインドウ設定部１３ａは、注目点設定部１２ａにより設定された注目点を中心として所定行×所定列のサイズを有する基準ウインドウを基準画像に設定する。図４は、基準ウインドウが設定された基準画像を示した図である。図４に示すように、基準画像Ｉ１の左上の画素が注目点ＣＰとして設定され、注目点ＣＰを中心として１４×１４のサイズを有する基準ウインドウＷ１が設定されていることが分かる。また、基準ウインドウＷ１は基準画像Ｉ１からはみ出ており、基準ウインドウＷ１内に基準画像Ｉ１からはみ出た外領域Ｄ１が含まれていることが分かる。また、参照ウインドウにおいても同様のことが起こり得る。
【００３７】
参照ウインドウ設定部１３ｂは、中心点設定部１２ｂにより設定された中心点を中心として基準ウインドウと同一サイズの参照ウインドウを参照画像に設定する。以下、基準ウインドウと参照ウインドウとを特に区別しない場合は、両者を総称して「ウインドウ」と称し、基準画像と参照画像とを特に区別しない場合は、両者を総称して「入力画像」と称する。なお、図４では、説明の便宜上、１４×１４のウインドウを例示したが、これは一例であり、ウインドウのサイズは、入力画像全体の画素数、撮影対象により好ましい値に適宜変更すればよい。
【００３８】
判定部１４は、判定部１４ａ，１４ｂを備えている。判定部１４ａは、基準画像に設定された基準ウインドウにおいて外領域が含まれているか否かを基準ウインドウがずらされる毎に判定する。ここで、判定部１４ａは、例えば基準画像の端に位置する画素が１つでも含まれている場合、基準ウインドウ内に外領域が含まれていると判定すればよい。
【００３９】
判定部１４ｂは、判定部１４ａと同様にして、参照画像に設定された参照ウインドウ内に外領域が含まれているか否かを参照ウインドウがずらされる毎に判定する。
【００４０】
補間部１５は、判定部１４により外領域が含まれていると判定された場合、ウインドウ内の入力画像の少なくとも端に位置する画素の画素値に基づいて、外領域の補間画素値を算出する。ここで、補間部１５ａは、基準ウインドウの外領域を補間する補間部１５ａと、参照ウインドウの外領域を補間する補間部１５ｂとを備えている。なお、補間部１５の処理の詳細については後述する。また、補間画素値は、外領域において入力画像と同一の解像度で仮想的に画素を設定した場合の画素値を示す。また、外領域において仮想的に設定した画素を「補間画素」と称する。
【００４１】
探索処理部１６は、参照ウインドウをずらしながら、基準ウインドウ内の画像と、参照ウインドウ内の画像との一致度を求めることで、参照画像から注目点の対応点を探索する。ここで、探索処理部１６は、ＳＡＤ（Sum of Absolute Difference）、ＳＳＤ（Sum of Squared intensity Difference）、ＮＣＣ（Normalized Cross Correlation）、及び位相限定相関法のいずれかを用いて一致度を算出することができる。
【００４２】
ＳＡＤによる探索処理は、参照ウインドウをずらしながら、式（１）により得られる相関値から基準ウインドウ内の画像と参照ウインドウ内の画像との一致度を求め、一致度が最も高い値を示すときの参照ウインドウの中心点を注目点の対応点として探索する。式（１）に示すようにＳＡＤは、２枚の画像の画素値をそのまま減算することで相関値を算出するため、計算量が少なく、高速処理可能であるといった特徴を有している。
【００４３】
【数１】
0004831084.tif 000002
但し、ＭＬは基準ウインドウ内の画像を示し、ＭＲは参照ウインドウ内の画像を示し、Ｑはウインドウの水平方向のサイズを示し、Ｐはウインドウの垂直方向のサイズを示す。
【００４４】
ＳＳＤによる探索処理は、式（２）により得られる相関値から、基準ウインドウ内の画像と参照ウインドウ内の画像との一致度を求める以外はＳＡＤの場合と同様にして対応点を探索する。
【００４５】
【数２】
0004831084.tif 000003
式（２）に示すように、ＳＳＤは、２枚の画像の画素値の減算値が２乗されているため、ウインドウサイズが小さい場合であっても両画像の誤差を明確にすることができる。
【００４６】
ＮＣＣによる探索処理は、式（３）により得られる相関値から基準ウインドウ内の画像と参照ウインドウ内の画像との一致度を求める以外はＳＡＤと同様にして対応点を探索する。
【００４７】
【数３】
0004831084.tif 000004
但し、μＭＬは基準ウインドウ内の画像の局所的な平均値を示し、μＭＲは参照ウインドウ内の画像の局所的な平均値を示す。
【００４８】
ＮＣＣは、式（３）に示すように、局所的な平均値が減じられた２枚の画像の分散値によって相関値が求められるため、線形な明るさの変化（画素値及びコントラストの線形変化やノイズ等）に影響されない手法である。
【００４９】
位相限定相関法を用いた探索処理は、基準画像に設定したウインドウ内の画像と参照画像に設定したウインドウ内の画像とを周波数分解することで得られる位相成分に基づいて一致度を算出し、対応点を探索する。なお、周波数分解する手法としては、高速フーリエ変換、離散フーリエ変換、離散コサイン変換、離散サイン変換、ウエーブレット変換、及びアダマール変換のいずれかを採用することができる。
【００５０】
図５は、位相限定相関法の処理の流れを示した図である。まず、基準ウインドウ内の画像ｆ及び参照ウインドウ内の画像ｇが離散フーリエ変換（ＤＦＴ）され、画像Ｆ及び画像Ｇが得られる。次に、画像Ｆ及び画像Ｇが規格化され、画像Ｆ´及び画像Ｇ´が得られる。次に、画像Ｆ´及び画像Ｇ´が合成され、相関画像Ｒが得られる。次に、相関画像Ｒが離散フーリエ逆変換（ＩＤＦＴ）され、ＰＯＣ関数ｒが得られる。図６はＰＯＣ関数ｒを示したグラフである。
【００５１】
図６に示すようにＰＯＣ関数ｒは、急峻な相関ピークを有し、画像マッチングにおけるロバスト性と推定精度とが高いことが知られている。そして、この相関ピークの高さは画像ｆ及び画像ｇの相関が高いほど大きくなる。したがって、一致度として、例えば相関ピークの高さを採用することで、両ウインドウ内の画像ｆ及び画像ｇがどれだけ近似しているかを示すことが可能となる。そして、参照ウインドウをずらしていった場合に一致度が最も高くなったときの参照ウインドウの中心点が対応点として探索される。
【００５２】
次に、ウインドウ内に外領域が含まれることによる探索精度の低下について説明する。図７は、対応点の探索処理の説明図である。図７においては、基準画像に設定された注目点ＣＰの参照画像上の対応点であるＴＰが水平方向にＮ画素ずれている。また、図７において、参照ウインドウＷ２の中心点が、注目点ＣＰと同一座標の参照画像上の点であるＣＰ´に位置するように、参照ウインドウＷ２が参照画像に設定され、探索処理が開始され、参照ウインドウＷ２がＣＰ´から水平方向に１画素ずつずらされていく。この場合、本来的には、参照ウインドウをＮ画素ずらしたときに基準ウインドウＷ１内及び参照ウインドウＷ２内の両画像の一致度が最も高くなり、ＴＰが対応点として探索されるはずである。
【００５３】
しかしながら、図７に示すように、基準ウインドウＷ１内に外領域Ｄ１が含まれて基準画像と外領域Ｄ１との境界にエッジが発生すると、このエッジの影響により、対応点がＴＰではなく、ＴＰよりエッジ側の例えばＣＰ´で探索されてしまい、誤探索が発生してしまう。
【００５４】
そこで、補間部１５ａ，１５ｂは、共に、以下に示す第１〜第４の手法を用いて外領域を補間する。まず、第１の手法について説明する。図８は、第１及び第３の手法の説明図である。第１の手法は、ウインドウＷ内の入力画像Ｉ１の端Ｅ１に位置する画素の画素平均値を補間画素値として算出し、この補間画素値を外領域Ｄ１の各補間画素に設定する手法である。ここで、ウインドウＷ内に入力画像Ｉ１の水平及び垂直方向の２辺が含まれ、外領域Ｄ１がＬ字状になる場合は、ウインドウＷ内の入力画像Ｉ１の端の水平方向に１ライン及び垂直方向に１ラインに含まれる画素が端Ｅ１に位置する画素となる。また、ウインドウＷ内に入力画像Ｉ１の水平又は垂直方向の一辺が含まれ、外領域Ｄ１が帯状になる場合は、ウインドウＷの端の水平方向の１ライン又は垂直方向の１ラインに含まれる画素が端Ｅ１に位置する画素となる。なお、端Ｅ１に位置する画素のライン数を１ラインに代えて２、３ライン等の複数ラインにしてもよい。
【００５５】
また、第１の手法において、ウインドウＷの端に向かうにつれて、補間画素値がなだらかに変化するように外領域Ｄ１に各補間画素を設定してもよい。この場合、外領域Ｄ１の画素値がウインドウＷの端に向かうにつれて大きくなるようにしてもよいし、ウインドウＷの端に向かうにつれて小さくなるようにしてもよい。
【００５６】
具体的には、ウインドウＷの端に向かうにつれて補間画素値を小さくする場合は、画素平均値を基準として段階的に小さくなるように、補間画素値を算出すればよい。また、ウインドウＷの端に向かうにつれて補間画素値を大きくする場合は、画素平均値を基準として段階的に大きくなるように補間画素値を算出すればよい。
【００５７】
また、ウインドウＷの端に向かうにつれて画素値を大きくする場合は、画素平均値よりも所定の値だけ大きい画素値と画素平均値とを補間画素値として採用し、ウインドウＷの端に向かうにつれて、大きい画素値の個数が多くなるように、外領域Ｄ１の画素値を設定すればよい。
【００５８】
第１の手法によれば、補間画素値の算出に用いられる画素がウインドウ内の入力画像Ｉ１の端Ｅ１の画素のみとなるため、高速に補間画素値を求めることができる。また、ウインドウＷ内の入力画像Ｉ１の端の画素の画素平均値が補間画素値として算出されるため、外領域Ｄ１と入力画像Ｉ１との境界におけるエッジの発生をより確実に抑制することができる。
【００５９】
次に、第２の手法について説明する。図９は第２の手法の説明図である。第２の手法は、ウインドウＷ内の入力画像Ｉ１、すなわち、図９のＥ２の濃い色で示す矩形状の領域を構成する各画素の画素平均値を補間画素値として算出し、外領域Ｄ１に設定する手法である。第２の手法においても、第１の手法と同様、端に向かうにつれてなだらかに変化するように外領域Ｄ１に補間画素値を設定してもよい。
【００６０】
第２の手法によれば、ウインドウＷ内の入力画像Ｉ１の画素平均値が補間画素値として採用されているため、基準画像及び参照画像のウインドウＷ内の両画像の一致度が、両ウインドウ内の画像全域ではなく一部の領域を用いて局所的に算出されるような場合であっても、外領域と入力画像との境界におけるエッジの発生をより確実に抑制することができる。
【００６１】
次に、第３の手法について図８を用いて説明する。第３の手法は、ウインドウＷ内の入力画像Ｉ１の端Ｅ１に位置する各画素の画素平均値を基準として上下に一定のマージンαを与えた値を補間画素値として算出する手法である。この場合、ウインドウＷ内の入力画像Ｉ１の端Ｅ１に位置する各画素のうち、画素値が画素平均値より高い画素の割合が、画素平均値より低い画素の割合よりも高い場合、画素平均値に一定のマージンを加えた値（＝画素平均値＋α）を補間画素値とし、その逆の場合、画素平均値から一定のマージンを差し引いた値（＝画素平均値−α）を補間画素値として算出すればよい。
【００６２】
第３の手法によれば、画素平均値に上下にマージンαを与えて補間画素値の値が調節されるため、外領域Ｄ１と入力画像Ｉ１との境界におけるエッジの発生をより確実に抑制することができる。なお、マージンαとしては、平均画素値の１〜１０％の値を採用してもよいし、平均画素値に応じて予め定められた値を採用してもよい。
【００６３】
次に、第４の手法について用いて説明する。図１０は第４の手法の説明図である。第４の手法は、ウインドウＷ内の入力画像Ｉ１の端に位置する第ｉ行の画素Ｇｉの画素値を、外領域Ｄ１の第ｉ行に対応する補間画素値Ｈｉとして算出し、外領域Ｄ１の第ｉ行を構成する各補間画素を、補間画素値Ｈｉを用いて設定する手法である。
【００６４】
この場合、探索処理部１６は、参照ウインドウの中心点を注目点が位置する行と同一行に設定し、当該行において参照ウインドウを１ライン分だけずらして対応点を探索することが好ましい。カメラＣ１，Ｃ２は、光軸が平行に設置されているため、対応点は、参照画像において、基準画像に設定された注目点と同一行に存在する可能性が高い。そのため、注目点が設定された行と同じ参照画像上の１行を探索範囲として、この探索範囲に中心点が位置するように参照画像をずらすことで、高速に対応点を探索することが可能となる。
【００６５】
そして、参照ウインドウを水平方向に１ラインだけずらして対応点を探索する探索処理を採用すると、外領域Ｄ１において、各行の値が異なって横縞が発生していても、水平方向において画素値が連続的に変化していれば、探索に影響を与えない。そこで、補間画素値Ｈｉによって外領域Ｄ１を水平方向に一律に埋めることで、探索精度を高くし、かつ、処理の高速化を図ることができる。
【００６６】
なお、第４の手法において、ウインドウＷ内に入力画像Ｉ１の２辺が含まれ、外領域Ｄ１がＬ字状となる場合には、入力画像Ｉ１において水平方向と平行な端の１ラインに隣接する外領域Ｄ１の各補間画素の画素値を、当該１ラインに位置する画素であって、ウインドウＷ内の画素の画素平均値で埋めればよい。具体的には、図１０の場合、ウインドウＷ内において、入力画像Ｉ１の１行目に位置する画素の画素平均値を用いて、当該１行目に隣接する外領域Ｄ１の各補間画素の画素値を設定すればよい。
【００６７】
次に、本対応点探索装置の動作について説明する。図１１は、対応点探索装置の動作を示すフローチャートである。図１１のフローチャートは、時刻ｔにおいて、カメラＣ１，Ｃ２により撮影された２枚の入力画像を処理する場合を示しており、カメラＣ１，Ｃ２から入力画像が撮影される毎に実行される。
【００６８】
まず、ステップＳ１１において、基準画像取得部１１ａは、カメラＣ１により撮影された入力画像を基準画像として取得し、参照画像取得部１１ｂは、カメラＣ２により撮影された入力画像を参照画像として取得する。
【００６９】
ステップＳ１２において、注目点設定部１２ａが基準画像上の所定の位置に注目点を設定し、基準ウインドウ設定部１３ａは、注目点を中心として基準ウインドウを基準画像上に設定する。
【００７０】
ステップＳ１３において、判定部１４ａは、基準ウインドウ内に外領域が含まれているか否かを判定する。そして、外領域が含まれている場合（ステップＳ１４でＹＥＳ）、補間部１５ａは、上記第１〜第４のいずれかの手法を用いて外領域を補間する（ステップＳ１５）。
【００７１】
一方、基準ウインドウ内に外領域が含まれていない場合（ステップＳ１４でＮＯ）、ステップＳ１５がスルーされ、中心点設定部１２ｂは、参照画像上の所定の位置に中心点を設定し、参照ウインドウ設定部１３ｂは、中心点を中心として参照ウインドウを参照画像上に設定する（ステップＳ１６）。
【００７２】
ステップＳ１７において、判定部１４ｂは、参照ウインドウ内に外領域が含まれているか否かを判定する。そして、外領域が含まれている場合（ステップＳ１８でＹＥＳ）、補間部１５ｂは、上記第１〜第４のいずれかの手法を用いて外領域を補間する（ステップＳ１９）。
【００７３】
一方、参照ウインドウ内に外領域が含まれていない場合（ステップＳ１８でＮＯ）、ステップＳ１９がスルーされ、探索処理部１６は、基準ウインドウ及び参照ウインドウ内の両画像の一致度を算出する（ステップＳ２０）。
【００７４】
ステップＳ２１において、参照ウインドウ設定部１３ｂが参照ウインドウを最終の位置に設定しており、参照ウインドウのスライドが終了している場合（ステップＳ２１でＹＥＳ）、探索処理部１６は、ステップＳ２０で一致度が算出された参照ウインドウの中心点のうち一致度が最も高い中心点を対応点として算出する（ステップＳ２２）。
【００７５】
一方、参照ウインドウ設定部１３ｂが参照ウインドウを最終の位置に設定していない場合（ステップＳ２１でＮＯ）、処理をステップＳ１６に戻す。そして、中心点設定部１２ｂは、参照画像に次の中心点を設定し、参照ウインドウ設定部１３ｂは、この中心点を中心に参照ウインドウを設定する（ステップＳ１６）。以上ステップＳ１６〜Ｓ２１の処理が繰り返され、参照ウインドウが参照画像上をずらされていく。
【００７６】
ステップＳ２３において、基準ウインドウ設定部１３ａが基準ウインドウを最終の位置に設定しており、基準ウインドウのスライドが終了している場合（ステップＳ２３でＹＥＳ）、処理が終了される。一方、基準ウインドウが最終の位置に設定されていない場合（ステップＳ２３でＮＯ）、処理がステップＳ１２に戻される。
【００７７】
なお、探索処理部１６は、以下に示す多重解像度戦略手法を用いて対応点を探索してもよい。図１２は、多重解像度戦略手法の説明図である。多重解像度戦略手法は、下位の階層から上位の階層に向かうにつれて解像度が高くなるように、解像度の異なる複数の基準画像及び参照画像を階層的に生成し、下位の階層での対応点の探索結果に基づいて、当該階層の探索範囲よりも小さな探索範囲を１つ上の階層の参照画像に設定し、当該探索範囲内で対応点を探索する探索処理を上位の階層に向けて階層的に実行することで対応点を探索する手法である。この手法によれば、対応点を高速かつ高精度に探索することが可能となる。
【００７８】
各階層でのウインドウサイズを同一として多重解像度戦略手法を採用すると、下位の層に向かうにつれて、入力画像Ｉ１の解像度が低くなるため、外領域を含むウインドウが設定される箇所が増大し、探索精度が低くなる。上位の層は下位の層での探索結果を承継して探索範囲が設定されるため、下位の層での探索結果は重要である。
【００７９】
本対応点探索装置では、外領域が上記第１〜第４の手法を用いて補間されるため、下位の層においても対応点を精度良く探索することが可能となり、多重解像度戦略手法を採用した場合においても、対応点を高速、かつ高精度に探索することが可能となる。
【００８０】
図１３は、多重解像度戦略手法を採用した場合の探索処理のフローチャートである。まず、ステップＳ３１において、図１１に示すステップＳ１１と同様、基準画像及び参照画像が取得される。
【００８１】
ステップＳ３２において、注目点設定部１２ａ及び中心点設定部１２ｂは、基準画像及び参照画像を階層毎に予め定められた解像度で低解像度化する処理を実行し、解像度の異なる複数の基準画像及び参照画像を階層的に生成する。ここで、階層数及び各階層における解像度は予め定められており、下位の階層から上位の階層に向かうにつれて解像度が高くなり、解像度変換が行われていない基準画像及び参照画像が最上位の階層とされる。
【００８２】
ステップＳ３３において、注目点設定部１２ａは、最上位の階層の基準画像に注目点を設定する。ステップＳ３４において、注目点設定部１２ａ及び中心点設定部１２ｂは、処理対象となる注目層を設定する。ここで、注目層は、まず、最下位の階層を注目層として設定し、次に１つ上の階層を注目層として設定するというように、最上位の階層に向けて順次注目層を設定する。
【００８３】
ステップＳ３５において、基準ウインドウ設定部１３ａは、ステップＳ３３で設定した注目点に対応する注目層の基準画像上の投影点を注目点として基準ウインドウを設定する。
【００８４】
ステップＳ３６において、判定部１４ａは、ステップＳ３５で設定された基準ウインドウに外領域が含まれているか否かを判定する。そして、外領域が存在すると判定された場合（ステップＳ３７でＹＥＳ）、補間部１５ａは、外領域を上記第１〜第４のいずれかの手法を用いて補間する（ステップＳ３８）。一方、外領域が存在しないと判定された場合（ステップＳ３７でＮＯ）、ステップＳ３８がスルーされ、探索処理部１６により探索処理が実行される（ステップＳ３９）。なお、ステップＳ３９の処理の詳細については後述する。
【００８５】
ステップＳ４０において、最上位の階層に対する探索処理が終了された場合は（ステップＳ４０でＹＥＳ）、処理がステップＳ４１に進められる。一方、最上位の階層に対する探索処理が終了されていない場合は（ステップＳ４０でＮＯ）、処理がステップＳ３４に戻され、一つ上の階層が注目層として設定される。
【００８６】
ステップＳ４１において、注目点設定部１２ａにより基準画像上において注目点として順次設定されることが予め定められた点のうち、最後の点が注目点として設定されている場合（ステップＳ４１でＹＥＳ）、処理が終了される。一方、最後の点が注目点として設定されていない場合（ステップＳ４１でＮＯ）、処理がステップＳ３３に戻され、次の注目点が設定される。
【００８７】
次に、図１３に示すステップＳ３９の探索処理の詳細について説明する。図１４は探索処理の詳細を示すフローチャートである。まず、ステップＳ６１において、中心点設定部１２ｂは、注目層の参照画像に探索領域を設定する。ここで、中心点設定部１２ｂは、例えば最下位の階層の参照画像においては全域を探索範囲として設定し、それより階層が上の注目層の参照画像においては、注目層の１つ下の階層で算出された対応点に対応する注目層の参照画像の投影点を基準とし、当該投影点が含まれ、かつ、１つ下の階層で設定した探索範囲よりも狭い領域を探索範囲として設定する。
【００８８】
ステップＳ６２において、中心点設定部１２ｂは、ステップＳ６１で設定された探索範囲の所定の位置に中心点を設定し、参照ウインドウ設定部１３ｂは、当該中心点を中心として参照ウインドウを設定する。
【００８９】
ステップＳ６３において、判定部１４ｂは、参照ウインドウ内に外領域が含まれているか否かを判定する。そして、外領域が含まれている場合（ステップＳ６４でＹＥＳ）、補間部１５ｂは、外領域を上記第１〜第４の手法のいずれかを用いて補間する（ステップＳ６５）。
【００９０】
一方、外領域が含まれていない場合（ステップＳ６４でＮＯ）、ステップＳ６５がスルーされ、探索処理部１６は、注目層の基準ウインドウ及び参照ウインドウ内の両画像の一致度を算出する（ステップＳ６６）。
【００９１】
ステップＳ６７において、探索処理部１６は、参照ウインドウ設定部１３ｂにより参照ウインドウが探索範囲の所定の最終位置に設定され、参照ウインドウのスライドが終了した場合（ステップＳ６７でＹＥＳ）、探索処理部１６は、ステップＳ６６で一致度が算出された参照ウインドウの中心点のうち一致度が最も高い中心点を対応点として算出する（ステップＳ６８）。
【００９２】
一方、参照ウインドウのスライドが終了していない場合（ステップＳ６７でＮＯ）、処理がステップＳ６２に戻され、注目層の参照画像上に次の中心点が設定される。
【００９３】
以上説明したように、本対応点探索装置によれば、ウインドウが入力画像からはみ出して設定された場合であっても、演算コストを増大させることなく、対応点を精度良く探索することができる。
【００９４】
なお、上記説明では、参照画像を１枚としたが、これに限定されず、参照画像を複数枚としてもよい。この場合、各参照画像に対応する複数のカメラを設置すればよい。また、各参照画像に対応する複数の中心点設定部１２ｂ〜補間部１５ｂを設ければよい。そして、探索処理部１６は、各参照画像に対して対応点を求めればよい。
【図面の簡単な説明】
【００９５】
【図１】本発明の実施の形態による対応点探索装置の概略構成図を示している。
【図２】コントローラの機能ブロック図を示している。
【図３】注目点の設定処理の説明図である。
【図４】基準ウインドウが設定された基準画像を示した図である。
【図５】位相限定相関法の処理の流れを示した図である。
【図６】ＰＯＣ関数を示したグラフである。
【図７】対応点探索処理の説明図である。
【図８】第１及び第３の手法の説明図である。
【図９】第２の手法の説明図である。
【図１０】第４の手法の説明図である。
【図１１】対応点探索装置の動作を示すフローチャートである。
【図１２】多重解像度戦略手法の説明図である。
【図１３】多重解像度戦略手法を採用した場合の探索処理のフローチャートである。
【図１４】探索処理の詳細を示すフローチャートである。
【符号の説明】
【００９６】
１０  コントローラ
１１  画像取得部
１１ａ  基準画像取得部
１１ｂ  参照画像取得部
１２  設定部
１２ａ  注目点設定部
１２ｂ  中心点設定部
１３  ウインドウ設定部
１３ａ  基準ウインドウ設定部
１３ｂ  参照ウインドウ設定部
１４，１４ａ，１４ｂ  判定部
１５，１５ａ，１５ｂ  補間部
１６  探索処理部
Ｃ１，Ｃ２  カメラ
【図１】
0004831084.tif 000005
【図２】
0004831084.tif 000006
【図３】
0004831084.tif 000007
【図４】
0004831084.tif 000008
【図５】
0004831084.tif 000009
【図７】
0004831084.tif 000010
【図８】
0004831084.tif 000011
【図９】
0004831084.tif 000012
【図１０】
0004831084.tif 000013
【図１１】
0004831084.tif 000014
【図１２】
0004831084.tif 000015
【図１３】
0004831084.tif 000016
【図１４】
0004831084.tif 000017
【図６】
0004831084.tif 000018