(57)【特許請求の範囲】
【請求項１】
入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する対応点探索装置であって、
前記入力画像と前記参照画像の間の類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成手段と、
前記類似度画像生成手段により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点とする対応点探索手段と
を備えたことを特徴とする対応点探索装置。
【請求項２】
前記対応点探索手段は、前記類似度画像生成手段により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算する累積加算手段と、前記累積加算手段により累積加算された各類似度画像の画素値を正規化する正規化手段と、各類似度画像のうちの最大の画素値を持つ画素の画素位置の変動幅が所定値未満となった場合に該画素位置を対応点として特定する対応点特定手段とを備えたことを特徴とする請求項１に記載の対応点探索装置。
【請求項３】
前記正規化手段は、前記累積加算手段により各類似度画像を横方向、該横方向の逆方向、縦方向、該縦方向の逆方向の順で累積加算をおこなった後に、各類似度画像の画素値を正規化することを特徴とする請求項２に記載の対応点探索装置。
【請求項４】
前記正規化手段は、前記類似度画像の各画素の画素値が浮動小数点で表現される場合に、前記累積加算手段により累積加算された各類似度画像の各画素の画素値から該類似度画像内の最大の画素値を減じて正規化することを特徴とする請求項２または３に記載の対応点探索装置。
【請求項５】
前記正規化手段は、前記類似度画像の各画素の画素値が浮動小数点で表現される場合に、前記累積加算手段により累積加算された各類似度画像の各画素の画素値から全ての類似度画像内の最大の画素値を減じて正規化することを特徴とする請求項２または３に記載の対応点探索装置。
【請求項６】
前記正規化手段は、前記類似度画像の各画素の画素値が整数で表現される場合に、前記累積加算手段により累積加算された各類似度画像の各画素の画素値から該類似度画像内の最大の画素値を減じるとともに、その結果に所定の値を加算して正規化することを特徴とする請求項２または３に記載の対応点探索装置。
【請求項７】
前記所定の値は、縦方向にＭ個および横方向にＮ個の類似度画像が存在し、各類似度画像の画素値を整数型で表現できる範囲が０からＩmaxである場合に、このＩmaxにM(M+1)N(N+1)／４を乗じた値よりも小さな値であることを特徴とする請求項６に記載の対応点探索装置。
【請求項８】
入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する対応点探索装置における対応点探索処理方法であって、
所定の画像入力部から入力された参照画像を所定の記憶部に一時記憶する一時記憶工程と、
前記画像入力部から入力された入力画像と前記一時記憶工程により前記記憶部に一時記憶された前記参照画像の間の類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成工程と、
前記類似度画像生成工程により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点とする対応点探索処理工程と
を含んだことを特徴とする対応点探索処理方法。
【請求項９】
前記対応点探索処理工程は、前記類似度画像生成工程により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算処理する累積加算処理工程と、前記累積加算処理工程により累積加算処理された各類似度画像の画素値を正規化する正規化処理工程と、各類似度画像のうちの最大の画素値を持つ画素の画素位置の変動幅が所定値未満となった場合に該画素位置を対応点として特定処理する対応点特定処理工程とを含んだことを特徴とする請求項８に記載の対応点探索処理方法。
【請求項１０】
入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する対応点探索装置の対応点探索処理プログラムであって、
所定の画像入力部から入力された参照画像を所定の記憶部に一時記憶する一時記憶手順と、
前記画像入力部から入力された入力画像と前記一時記憶手順により前記記憶部に一時記憶された前記参照画像の間の類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成手順と、
前記類似度画像生成手順により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点とする対応点探索処理手順と
をコンピュータに実行させることを特徴とする対応点探索処理プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する対応点探索装置、対応点探索処理方法および対応点探索処理プログラムに関し、特に、類似度画像の各画素値を累積加算する処理を繰り返して対応点を求める場合に、サチュレーションや桁あふれの影響を防止しつつ正確かつ高速に対応点を求めることができる対応点探索装置、対応点探索処理方法および対応点探索処理プログラムに関する。
【０００２】
【従来の技術】
従来、スキャナなどの画像入力装置から入力された入力画像をあらかじめ登録した参照画像とを照合する際に、両画像の対応点を探索して画像間の対応付けをおこなう技術が知られている。
【０００３】
たとえば、「T.Poggio，V.TorreandC.Koch，”Computational vision and regularization theory”，NATURE Vol.317，pp. 314-319，1985」（従来技術１）には、設定したエネルギー関数を変分法の枠組みにより最小化する標準正則化理論を適用した技術が開示されている。この従来技術１が採用する標準正則化理論は、局所的な情報のみを使った繰り返し計算によりエネルギーを最小化することによって対応点を計算するものであるので、並列分散処理をおこなうことができ、人間の脳情報処理に近い処理を実現できる可能性がある。
【０００４】
また、「内田誠一，迫江博昭，”動的計画法に基づく単調連続２次元ワープ法の検討”，信学論（D-II） Vol. J81-D-II no. 6，pp.1251-1258，June 1998」（従来技術２）には、ＤＰ（Dynamic Programming）を用いて効率的に最適解を探索する２次元ＤＰワープ法を採用した技術が開示されている。この従来技術２によれば、最適化問題を効率的に計算することができる。
【０００５】
ところが、上記従来技術１のものは、局所的な情報のみを使った繰り返し計算によってエネルギーを最小化して対応点を計算するため、初期値の影響が大きくなるという問題や、局所解（ローカルミニマム）に陥り易いことから最適な対応付け結果を得られ難いという問題がある。また、従来技術２のものは、ＤＰによって効率よく最適解を探索できるものの、その計算量が膨大なものになるという問題がある。具体的には、最適解を得るためには画像サイズの指数オーダーの計算時間が必要となる。
【０００６】
これらのことから、画像間の対応付けをおこなう際に、局所解に陥ることなく安定した対応付け結果を高速に得る必要がある。このため、大西弘之氏等は、２００１年３月２３日に米国に出願された出願番号０９／８１５，２６７（従来技術３）において、従来例より大局的に最適な対応点を安定して求めることができる対応点探索技術を提案している。
【０００７】
【発明が解決しようとする課題】
しかしながら、この従来技術３のものは、類似度画像を再帰的に更新する際に再帰的な加算を繰り返すため、繰り返し回数が一定値以上になると演算誤差が大きくなり、結果的に正確な対応点を求めることができないという問題がある。
【０００８】
図２２は、上記従来技術３の問題点を説明するための説明図である。なお、ここでは類似度画像の各画素値を浮動小数点で表現できる場合を示しており、説明の便宜上、６画素の類似度画像Ａ(k-1)に６画素の類似度画像Ｂ(k)を加算して６画素の類似度画像Ａ(k)を作成することとする。また、データの有効桁数を１０進数９桁とする。
【０００９】
同図に示す類似度画像Ａ(k-1)の各画素に類似度画像Ｂ(k)の対応する画素を加算すると、類似度画像Ａ(k)を得ることができるが、サチュレーションを起こしたために、最大値の画素値1.16666667E+09の位置が３箇所現れてしまうため、最大値の位置が不明確になってしまう。この場合に、最大値として検出した３つの画素の重心を求めて対応点の位置としたのでは、対応点を正確に求めることができなくなる。
【００１０】
この問題は、類似度画像の各画素値を浮動小数点で表現する場合だけでなく、画素値を整数で表現する場合にも起こる問題であるので、サチュレーションや桁あふれに伴う対応点の精度の低下がいずれにしても重要な問題となる。なお、各画素の有効桁数をあげてサチュレーションや桁あふれの影響を回避することも考えられるが、多倍長演算などの特殊な演算が必要になるので、処理速度の低下を招く結果となる。
【００１１】
これらのことから、類似度画像の各画素値を累積加算する処理を繰り返して対応点を求める場合に、いかにしてサチュレーションや桁あふれの影響を防止しつつ高速に対応点を求めるかが重要な課題となっている。
【００１２】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、類似度画像の各画素値を累積加算する処理を繰り返して対応点を求める場合に、サチュレーションや桁あふれの影響を防止しつつ正確かつ高速に対応点を求めることができる対応点探索装置、対応点探索処理方法および対応点探索処理プログラムを提供することを目的とする。
【００１３】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、請求項１の発明に係る対応点探索装置は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する対応点探索装置であって、前記入力画像と前記参照画像の間の類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成手段と、前記類似度画像生成手段により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点とする対応点探索手段とを備えたことを特徴とする。
【００１４】
また、請求項２の発明に係る対応点探索装置は、請求項１の発明において、前記対応点探索手段は、前記類似度画像生成手段により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算する累積加算手段と、前記累積加算手段により累積加算された各類似度画像の画素値を正規化する正規化手段と、各類似度画像のうちの最大の画素値を持つ画素の画素位置の変動幅が所定値未満となった場合に該画素位置を対応点として特定する対応点特定手段とを備えたことを特徴とする。
【００１５】
また、請求項３の発明に係る対応点探索装置は、請求項２の発明において、前記正規化手段は、前記累積加算手段により各類似度画像を横方向、該横方向の逆方向、縦方向、該縦方向の逆方向の順で累積加算をおこなった後に、各類似度画像の画素値を正規化することを特徴とする。
【００１６】
また、請求項４の発明に係る対応点探索装置は、請求項２または３の発明において、前記正規化手段は、前記類似度画像の各画素の画素値が浮動小数点で表現される場合に、前記累積加算手段により累積加算された各類似度画像の各画素の画素値から該類似度画像内の最大の画素値を減じて正規化することを特徴とする。
【００１７】
また、請求項５の発明に係る対応点探索装置は、請求項２または３の発明において、前記正規化手段は、前記類似度画像の各画素の画素値が浮動小数点で表現される場合に、前記累積加算手段により累積加算された各類似度画像の各画素の画素値から全ての類似度画像内の最大の画素値を減じて正規化することを特徴とする。
【００１８】
また、請求項６の発明に係る対応点探索装置は、請求項２または３の発明において、前記正規化手段は、前記類似度画像の各画素の画素値が整数で表現される場合に、前記累積加算手段により累積加算された各類似度画像の各画素の画素値から該類似度画像内の最大の画素値を減じるとともに、その結果に所定の値を加算して正規化することを特徴とする。
【００１９】
また、請求項７の発明に係る対応点探索装置は、請求項６の発明において、前記所定の値は、縦方向にＭ個および横方向にＮ個の類似度画像が存在し、各類似度画像の画素値を整数型で表現できる範囲が０からＩmaxである場合に、このＩmaxにM(M+1)N(N+1)／４を乗じた値よりも小さな値であることを特徴とする。
【００２０】
また、請求項８の発明に係る対応点探索処理方法は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する対応点探索装置における対応点探索処理方法であって、所定の画像入力部から入力された参照画像を所定の記憶部に一時記憶する一時記憶工程と、前記画像入力部から入力された入力画像と前記一時記憶工程により前記記憶部に一時記憶された前記参照画像の間の類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成工程と、前記類似度画像生成工程により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点とする対応点探索処理工程とを含んだことを特徴とする。
【００２１】
また、請求項９の発明に係る対応点探索処理方法は、請求項８の発明において、前記対応点探索処理工程は、前記類似度画像生成工程により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算処理する累積加算処理工程と、前記累積加算処理工程により累積加算処理された各類似度画像の画素値を正規化する正規化処理工程と、各類似度画像のうちの最大の画素値を持つ画素の画素位置の変動幅が所定値未満となった場合に該画素位置を対応点として特定処理する対応点特定処理工程とを含んだことを特徴とする。
【００２２】
また、請求項１０の発明に係る対応点探索処理プログラムは、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する対応点探索装置の対応点探索処理プログラムであって、所定の画像入力部から入力された参照画像を所定の記憶部に一時記憶する一時記憶手順と、前記画像入力部から入力された入力画像と前記一時記憶手順により前記記憶部に一時記憶された前記参照画像の間の類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成手順と、前記類似度画像生成手順により生成された所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点とする対応点探索処理手順とをコンピュータに実行させることを特徴とする。
【００２３】
以下に添付図面を参照して、この発明に係る対応点探索装置、対応点探索処理方法および対応点探索処理プログラムの実施の形態を詳細に説明する。なお、下記実施の形態１では類似度画像の各画素が浮動小数点で表される場合を示し、実施の形態２では類似度画像の各画素が整数値で表される場合を示すこととする。
【００２４】
（実施の形態１）
図１は、本実施の形態で用いる対応点探索装置の構成を示す機能ブロック図である。同図に示す対応点探索装置１は、（１）入力画像を分割した入力部分画像と参照画像を分割した参照部分画像との間の類似度を示す類似度画像を作成する類似度画像作成段階と、（２）複数の類似度画像を累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点として決定する対応点決定段階とからなる。
【００２５】
具体的には、（１）類似度画像作成段階では、たとえば７×７画素のサイズからなる参照部分画像を２１×２１画素のサイズからなる入力部分画像内を移動させつつ順次相関値を求め、この相関値を画素値として持つ類似度画像を作成する。このため、この類似度画像は、参照部分画像上の中心点が入力部分画像上の点にどの程度類似しているかを示すことになる。
【００２６】
次に、（２）対応点決定段階では、各類似度画像の画素値を垂直方向および水平方向に再帰的に累積加算を繰り返しながら各類似度画像を更新しつつ正規化処理を適宜おこない、各類似度画像を形成する画素のうち最大の画素値を持つ画素の位置を求め、この位置を入力部分画像上での対応点として決定する。
【００２７】
このように、この対応点探索装置１によれば、従来よりも大局的な最適化をおこなっているためローカルミニマムに陥り難くなり、また累積加算を繰り返す最適化の微調整により対応付けの精度が高くなり、さらに並列分散処理が可能になるのでハードウエア化が容易となる。また、累積加算後に正規化処理をおこなっているので、桁あふれやサチュレーションによる悪影響（対応点の精度低下）を防止することができる。
【００２８】
次に、図１に示した対応点探索装置１の構成について説明する。なお、ここでは参照画像、入力画像の順に画像を入力する場合を示すこととする。図１に示すように、この対応点探索装置１は、画像入力部１０と、分割処理部１１と、参照部分画像一時記憶部１２と、類似度画像作成部１３と、累積加算処理部１４と、対応点決定部１５と、正規化処理部１６とからなる。
【００２９】
画像入力部１０は、縦横のサイズＩ，Ｊからなる参照画像Ｉ0（ｉ，ｊ）および入力画像Ｉ1（ｉ，ｊ）（０≦ｉ≦Ｉ−１，０≦ｊ≦Ｊ−１）を入力する入力部である。具体的には、光学的に原稿を読み取って画像を取得するスキャナや、ネットワークから画像を取得するインターフェース部や、二次記憶装置から画像を読み出す読み出し部が該当する。ここで、この入力画像とは、対応点の探索対象となる画像であって、歪みや変形を伴うものであっても良い。これに対して、参照画像とは、入力画像の比較の対象となる画像であり、歪みなどを伴わないものであることが望ましい。
【００３０】
図２（ａ）には参照画像２１を示しており、同図（ｂ）には入力画像２２を示している。これらの参照画像２１および入力画像２２は、いずれもアルファベット「ａ」の文字画像であり、３２×３２画素からなる。
【００３１】
分割処理部１１は、画像入力部１０により入力された入力画像および参照画像を入力部分画像および参照部分画像にそれぞれ分割する処理部である。ただし、入力画像の分割手順と参照画像の分割手順はそれぞれ異なる。
【００３２】
参照画像を分割する場合には、参照画像上で縦方向にＭ個、横方向にＮ個サンプリングした点（ｐm，ｑn）（０≦ｍ≦Ｍ−１，０≦ｎ≦Ｎ−１）を中心とした参照部分画像を作成する。図３は、図２（ａ）に示した参照画像２１の分割結果の一例を示す図であり、同図に示すように、ここでは３２×３２画素の参照画像２１を７×７画素からなる２５個の参照部分画像に分割している。具体的には、ｐm＝round（Ｉ／Ｍ）、ｑn＝round（Ｊ／Ｎ）としている。ただし、round（）は四捨五入を示している。
【００３３】
入力画像を分割する場合には、参照画像を分割する場合と異なり、各入力部分画像の一部が重なり合う重複したデータを持つように分割する。図４は、図２（ｂ）に示した入力画像２２の分割結果の一例を示す図であり、同図に示すように、ここでは３２×３２画素の入力画像２２を２１×２１画素からなる２５個の入力部分画像に分割している。
【００３４】
参照部分画像一時記憶部１２は、分割処理部１１で分割した各参照部分画像を一時記憶する記憶部であり、類似度画像作成部１３が類似度画像を作成する際に該当する参照部分画像が取り出される。
【００３５】
類似度画像作成部１３は、入力部分画像と参照部分画像の間の変形を考慮した類似度を算定して、該類似度を画素値として持つ類似度画像Ｃｍｎ（ｕ，ｖ）（０≦ｍ≦Ｍ−１，０≦ｎ≦Ｎ−１，０≦ｕ≦Ｕ−１，０≦ｖ≦Ｖ−１）を作成する処理部である。ただし、Ｕ，Ｖはそれぞれ類似度画像の縦横のサイズであるものとする。この類似度として正規化相関係数（σfg／（σf・σg））を用いることができる。
【００３６】
図５は、参照部分画像と入力部分画像から類似度画像を作成する概念を説明するための説明図である。なお、ここでは図３および図４の２行２列に位置する入力部分画像と参照部分画像を用いることとする。
【００３７】
同図に示す入力部分画像５１と参照部分画像５２の類似度を求める場合には、参照部分画像５２の中心画素を入力部分画像５２の左上部の画素に対応づけて正規化相関係数を計算し、その計算結果を類似度画像５３の左上部の画素の画素値とする。その後、参照部分画像５２を右にずらし、同様の処理をおこなう。上記処理を参照部分画像５２をずらしながら入力部分画像５１の全画素についておこなうことにより、類似度画像５３が求められる。
【００３８】
かかる類似度画像の作成処理を各入力部分画像ごとにおこなうと、図６に示すような複数の類似度画像が得られる。なお、参照部分画像の全ての画素の画素値が一定値である場合には、正規化相関係数の分母がゼロとなるため、この場合の類似度画像の画素値もゼロとなる。
【００３９】
累積加算処理部１４は、図７に示すように、各類似度画像をｊ方向、−ｊ方向、ｉ方向、−ｉ方向の順序で再帰的に累積加算する処理部である。具体的には、ｊ方向に累積加算する場合には、ｎ＝１〜Ｎ−１の類似度画像について、
Ｃmn（ｕ，ｖ）＝Ｃmn（ｕ，ｖ）＋α・Ｍａｘ（Ｃmn-1（ｐ，ｑ））
を順次再帰的に計算する。ただし、Ｍａｘ（）は最大値を示し、αは定数であり、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−１、ｕ−１≦ｐ≦ｕ＋１、ｖ−１≦ｑ≦ｖ＋１とする。
【００４０】
すなわち、ｊ方向に累積加算する場合には、図８に示すように、Ｃmn-1（ｐ，ｑ）を中心とする３×３画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣmn（ｐ，ｑ）の画素値に加算する処理を再帰的に繰り返すことになる。
【００４１】
また、−ｊ方向に累積加算する場合には、ｎ＝Ｎ−２〜０の類似度画像について、
Ｃmn（ｕ，ｖ）＝Ｃmn（ｕ，ｖ）＋α・Ｍａｘ（Ｃmn+1（ｐ，ｑ））
を順次再帰的に計算する。ただし、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−２とする。すなわち、−ｊ方向に累積加算する場合には、図９に示すように、Ｃmn+1（ｐ，ｑ）を中心とする３×３画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣmn（ｐ，ｑ）の画素値に加算する処理を再帰的に繰り返すことになる。
【００４２】
また、ｉ方向に累積加算する場合には、ｍ＝１〜Ｍ−１の類似度画像について、
Ｃmn（ｕ，ｖ）＝Ｃmn（ｕ，ｖ）＋α・Ｍａｘ（Ｃm-1n（ｐ，ｑ））
を順次再帰的に計算する。ただし、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、１≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−１とする。すなわち、ｉ方向に累積加算する場合には、図１０に示すように、Ｃm-1n（ｐ，ｑ）を中心とする３×３画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣmn（ｐ，ｑ）の画素値に加算する処理を再帰的に繰り返すことになる。
【００４３】
また、−ｉ方向に累積加算する場合には、ｍ＝Ｍ−２〜０の類似度画像について、
Ｃmn（ｕ，ｖ）＝Ｃmn（ｕ，ｖ）＋α・Ｍａｘ（Ｃm+1n（ｐ，ｑ））
を順次再帰的に計算する。ただし、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−２、０≦ｎ≦Ｎ−１とする。すなわち、−ｉ方向に累積加算する場合には、図１１に示すように、Ｃm+1n（ｐ，ｑ）を中心とする３×３画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣmn（ｐ，ｑ）の画素値に加算する処理を再帰的に繰り返すことになる。
【００４４】
対応点決定部１５は、累積加算処理部１４と連携しながら累積加算後の類似度画像に基づいて対応点を決定する処理部である。具体的には、各方向についての累積加算処理をおこなった時点で各類似度画像の最大値の位置を検出し、それらの位置と前回の累積加算処理時における最大値の位置との変化が所定の範囲内でなければ累積加算処理をフィードバックして繰り返し、所定の範囲内となった時点で繰り返しを終了し、そのときの各類似度画像の最大値の位置を対応点として決定する。
【００４５】
たとえば、累積加算処理の繰り返しによって図１２に示す各類似度画像が得られた場合には、各類似度画像の最大値の位置の変化分を調べ、その変化分が所定の範囲内となった場合には、図１３に示すように各類似度画像の最大値の位置を求めてこれを対応点とする。そして、この対応点に基づいて入力画像の歪みを図示すると図１４のようになる。
【００４６】
正規化処理部１６は、各類似度画像の画素値を累積加算する場合に生ずる桁あふれを防止するために、各類似度画像の画素値をそれぞれ正規化する処理部であり、具体的には、各類似度画像の画素値の最大値をそれぞれ求め、類似度画像内の画素値から最大値を減算し、最大値の画素の画素値が０になるよう正規化をおこなう。
【００４７】
具体的には、上記累積加算処理部１４による累積加算処理は、
Ｃ’mn（ｕ，ｖ）＝Ｃmn（ｕ，ｖ）＋α×Ｍａｘ（Ｃmn-1（ｐ，ｑ））
として記述できる。ただし、類似度画像のサイズがＵ×Ｖであり、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−１、ｕ−１≦ｐ≦ｕ＋１、ｖ−１≦ｑ≦ｖ＋１である。
【００４８】
ここで、ｋ回目の演算Ｃmn、Ｍａｘ（Ｃmn-1（ｐ，ｑ））をＡ(k)、Ｂ(k)と表すと、Ａ(k)＝Ａ(k-1)＋αＢ(k)となる。任意の数ａ、ｂをＡ(k-1)、Ｂ(k)から減算した場合の演算結果は、要素が１の行列をＩとすると、
0003898936.tif 000002
となるので、Ａ’(k)はＡ(k)の各要素から（ａ＋αｂ）を減算した結果と等しくなり、最大値の位置は変わらない。
【００４９】
累積加算処理によって、Ｃmnの値は指数関数的に増加するが、Ｃmnの各要素の値の差は指数関数的に増加するとは限らない。このため、従来技術によれば、mnの最大値の有効桁数では各要素の差が表現できなくなるサチュレーションが起こり得るのである。
【００５０】
これに対して、この正規化処理部１６では、最大値が常に０に正規化されるので、各要素の値の差、特に最大値付近の値の差は有効桁数を使ってフルに保存される。副作用として、最小値付近の値の差についてサチュレーションが起こる可能性が出てくるが、全体の演算に対する影響がないので、無視することができるのである。
【００５１】
また、この正規化処理部１６は、累積加算処理部１４により各類似度画像がｊ方向、−ｊ方向、ｉ方向、−ｉ方向の順序で再帰的に累積加算され、対応点決定部１５により求められた最大値の変位量が所定値未満である場合に、正規化処理をおこなう。その後、累積加算処理部１４は、この正規化処理結果を用いて再度累積加算処理をおこなう。
【００５２】
図１５は、図１に示した正規化処理部１６の処理概念を説明するための説明図である。なお、ここでは説明の便宜上、すでに説明した図２２と同様に、６画素の類似度画像Ａ(k-1)に６画素の類似度画像Ｂ(k)を加算して６画素の類似度画像Ａ(k)を作成する場合を示すこととする。また、データの有効桁数を１０進数９桁とする。
【００５３】
同図（ａ）に示すような類似度画像Ａ(k-1)に類似度画像Ｂ(k)を加算する場合には、同図（ｂ）に示すように類似度画像Ａ(k-1)の各画素値から最大値である5.55555559E08を減算し、類似度画像Ｂ(k)の各画素値から最大値である6.11111111E08を減算してそれぞれ類似度画像を正規化する。その後、正規化した類似度画像をそれぞれ加算して類似度画像Ａ(k)を作成する。
【００５４】
これにより、累積加算処理部１４が累積加算をおこなった後に、この類似度画像Ａ(k)の最大値−2.00000000E00の位置を正確に求めることができる。なお、同図（ｃ）に示すように、この類似度画像Ａ(k)の画素値をさらに正規化しておくことにより、その後に累積加算をおこなう場合であっても、サチュレーションの影響を防止して、最大値の正確な位置を求めることができる。
【００５５】
なお、各類似度画像の最大値は、類似度画像ごとに異なるので、各類似度画像ごと別々に計算して最大値を求めることになる。また、ここでは、各類似度画像ごとに最大値を求め、求めた最大値を当該類似度画像の各画素値から減算することにしたが、各類似度画像の最大値をそれぞれ比較して最も値が大きな画素値を全体の最大値とし、各類似度画像の画素値からこの全体の最大値を減算することもできる。
【００５６】
次に、図１に示した対応点探索装置１の処理手順について説明する。なお、上記説明と一部重複するが、図２〜図１５を用いて処理の流れを例示しつつ処理手順について説明することとする。
【００５７】
図１６は、図１に示した対応点探索装置１の処理手順を示すフローチャートである。同図に示すように、この対応点探索装置１が参照画像と入力画像を取得したならば、この参照画像を参照部分画像に分割する（ステップＳ１０１）。たとえば、図２（ａ）に示した３２×３２画素の参照画像２１を図３に示した７×７画素からなる２５個の参照部分画像に分割して記憶する。この参照部分画像は、参照したい画像毎に予め記憶しておいてもよいし、また、参照部分画像ではなく、参照画像のみを予め別途記憶しておき、後述する入力画像と参照画像との類似度の計算の際に、記憶された参照画像から参照部分画像に分割してもよい。
【００５８】
その後、入力画像を入力部分画像に分割する。たとえば、図２（ｂ）に示した３２×３２画素の入力画像２２を図４に示した２１×２１画素からなる２５個の入力部分画像に分割する。
【００５９】
そして、この参照部分画像と入力部分画像の間の類似度画像を作成する（ステップＳ１０２）。たとえば、図５に示すようにして入力部分画像５１と参照部分画像５２の類似度を画素値とする類似度画像５３の作成を各入力部分画像ごとにおこなって、図６に示したような複数の類似度画像を作成する。
【００６０】
その後、ｊ方向の累積加算処理（ステップＳ１０３）、−ｊ方向の累積加算処理（ステップＳ１０４）、ｉ方向の累積加算処理（ステップＳ１０５）、−ｉ方向の累積加算処理（ステップＳ１０６）をおこない、類似度画像の最大値の位置を検出する（ステップＳ１０７）。具体的には、図８〜図１１に示した加算処理を図７に示すように再帰的に繰り返すことにより、図１２に示したような類似度画像を作成し、図１３に示すように各類似度画像の最大値の位置を検出する。
【００６１】
そして、最大値の位置の変動が一定値以内であるか否かを調べ（ステップＳ１０８）、一定値以内でなければ（ステップＳ１０８否定）、図１５（ａ）に示す類似度画像から最大値を減算して図１５（ｂ）のような類似度画像にする正規化処理をおこなった後に（ステップＳ１０９）、ステップＳ１０３に移行して同様の処理を繰り返し、一定値以内であれば（ステップＳ１０８肯定）、この位置を対応点として処理を終了する。
【００６２】
次に、図１に示した累積加算処理部１４によるｊ方向の累積加算処理手順について説明する。図１７は、図１に示した累積加算処理部１４によるｊ方向の累積加算処理手順を示すフローチャートである。なお、−ｊ方向、ｉ方向、−ｉ方向の累積加算処理も同様におこなうことができる。
【００６３】
同図に示すように、まず変数ｍ、ｕおよびｖを０にするとともに、変数ｎを１とする初期化をおこなう（ステップＳ２０１〜Ｓ２０４）。ここで、この変数ｍはｉ方向のインデックスとして用いる変数であり、変数ｎはｊ方向のインデックスとして用いる変数である。また、変数ｕ，ｖは探索範囲を示すｉ方向およびｊ方向の変数である。
【００６４】
そして、この初期化を終えたならば、
Ｃmn（ｕ，ｖ）＝Ｃmn（ｕ，ｖ）＋α・Ｍａｘ（Ｃmn-1（ｐ，ｑ））
の算定式による計算をおこなう（ステップＳ２０５）。
【００６５】
その後、変数ｖをインクリメントし（ステップＳ２０６）、この変数ｖがＶよりも小さければ（ステップＳ２０７肯定）、ステップＳ２０５に移行して加算処理を繰り返す。つまり、探索範囲をｊ方向にずらすのである。
【００６６】
これに対して、変数ｖがＶ以上であれば（ステップＳ２０７否定）、変数ｕをインクリメントし（ステップＳ２０８）、この変数ｕがＵよりも小さければ（ステップＳ２０９肯定）、ステップＳ２０４に移行して加算処理を繰り返す。つまり、探索範囲をｉ方向にずらすことになる。
【００６７】
そして、変数ｕがＵ以上であれば（ステップＳ２０９否定）、ある画素についての計算を終了し、次の画素に移行する。具体的には、変数ｎをインクリメントして注目画素をｊ方向に移行させた後に（ステップＳ２１０）、この変数ｎをＮと比較し（ステップＳ２１１）、この変数ｎがＮよりも小さければ（ステップＳ２１１肯定）、ステップＳ２０３に移行して加算処理を繰り返す。
【００６８】
これに対して、変数ｎがＮ以上であれば（ステップＳ２１１否定）、変数ｍをインクリメントして注目画素をｉ方向に移行させた後に（ステップＳ２１２）、この変数ｍがＭよりも小さければ（ステップＳ２１３肯定）、ステップＳ２０２に移行して加算処理を繰り返し、変数ｍがＭ以上であれば（ステップＳ２１３否定）、処理を終了する。上記一連の処理をおこなうことにより、各類似度画像の全画素についてｊ方向の累積加算結果が得られることになる。
【００６９】
ところで、上記図１７のフローチャートでは、変数ｕ，ｖのインクリメントをおこないながら最大値を算出していた。別の計算方法として、あらかじめＣmn-1（ｕ，ｖ）に最大値フィルターをかけた最大値フィルター画像Ｃ’mn-1（ｕ，ｖ）を作成しておき、α倍してからＣmn（ｕ，ｖ）と加算することもできる。
【００７０】
そこで、かかる最大値フィルターを用いる場合の処理手順を図１８および図１９を用いて説明する。図１８は、図１に示した累積加算処理部１４による最大値フィルターを用いたｊ方向の累積加算処理手順を示すフローチャートであり、図１９は、最大値フィルターの処理手順を示すフローチャートである。
【００７１】
図１８に示すように、変数ｍを０に初期化し（ステップＳ３０１）、変数ｎを１に初期化した後（ステップＳ３０２）、最大値フィルターＣ’mn-1（ｕ，ｖ）を算定する（ステップＳ３０３）。
【００７２】
具体的には、図１９に示すように、変数ｕ，ｖを０に初期化した後に（ステップＳ４０１〜Ｓ４０２）、Ｃ’mn（ｐ，ｑ）＝Ｍａｘ［Ｃmn（ｐ，ｑ）］を計算する（ステップＳ４０３）。ただし、ｕ−１≦ｐ≦ｕ＋１、ｖ−１≦ｑ≦ｖ＋１とする。そして、ｖをインクリメントして（ステップＳ４０４）、この変数ｖがＶよりも小さい場合には（ステップＳ４０５肯定）、ステップＳ４０３に移行して同様に計算をおこなう。また、変数ｖがＶ以上である場合には（ステップＳ４０５否定）、変数ｕをインクリメントして（ステップＳ４０６）、この変数ｕがＵよりも小さい場合には（ステップＳ４０６肯定）、ステップＳ４０２に移行して同様の処理を繰り返し、結果的に最大値を求める。
【００７３】
このようにして最大値フィルターを算定したならば、変数ｕおよびｖを０に初期化した後（ステップＳ３０４〜Ｓ３０５）、
Ｃmn（ｕ，ｖ）＝Ｃmn（ｕ，ｖ）＋α・Ｍａｘ（Ｃ’mn-1（ｐ，ｑ））
の算定式による計算をおこなう（ステップＳ３０６）。
【００７４】
その後、変数ｖをインクリメントし（ステップＳ３０７）、この変数ｖがＶよりも小さければ（ステップＳ３０８肯定）、ステップＳ３０６に移行して加算処理を繰り返す。つまり、探索範囲をｊ方向にずらすのである。
【００７５】
これに対して、変数ｖがＶ以上であれば（ステップＳ３０８否定）、変数ｕをインクリメントし（ステップＳ３０９）、この変数ｕがＵよりも小さければ（ステップＳ３１０肯定）、ステップＳ３０５に移行して加算処理を繰り返す。つまり、探索範囲をｉ方向にずらすことになる。
【００７６】
そして、変数ｕがＵ以上であれば（ステップＳ３１０否定）、ある画素についての計算を終了し、次の画素に移行する。具体的には、変数ｎをインクリメントして注目画素をｊ方向に移行させた後に（ステップＳ３１１）、この変数ｎをＮと比較し（ステップＳ３１２）、この変数ｎがＮよりも小さければ（ステップＳ３１２肯定）、ステップＳ３０３に移行して加算処理を繰り返す。
【００７７】
これに対して、変数ｎがＮ以上であれば（ステップＳ３１２否定）、変数ｍをインクリメントして注目画素をｉ方向に移行させた後に（ステップＳ３１３）、この変数ｍがＭよりも小さければ（ステップＳ３１４肯定）、ステップＳ３０２に移行して加算処理を繰り返し、変数ｍがＭ以上であれば（ステップＳ３１４否定）、処理を終了する。
【００７８】
上述してきたように、本実施の形態１によれば、画像入力部１０から参照画像と入力画像をそれぞれ入力し、分割処理部１１で参照部分画像および入力部分画像をそれぞれ作成し、類似度画像作成部１３で参照部分画像と入力部分画像の類似度を求めた類似度画像をそれぞれ作成し、累積加算処理部１４で複数の類似度画像の累積加算処理を再帰的におこない、対応点決定部１５が最大値を持つ画素値の位置を対応点とできるか否かを判断し、対応点とできない場合には、正規化処理部１６により正規化処理をおこなった後に、累積加算処理部１４での累積加算を繰り返しおこなって、対応点を決定するよう構成したので、桁あふれやサチュレーションの影響を防止しつつ正確かつ高速に対応点を求めることができる。
【００７９】
なお、本実施の形態１では、説明の便宜上、参照画像と入力画像のサイズが同じ場合を示したが、本発明はこれに限定されるものではなく、参照画像と入力画像のサイズを異なる場合に適用することもできる。かかる場合にも同様の処理をおこなうことができる。
【００８０】
また、本実施の形態１では、類似度として正規化相関係数を用いた場合を示したが、本発明はこれに限定されるものではなく、ユークリッド距離などの他の指標を類似度として用いることもできる。
【００８１】
（実施の形態２）
ところで、上記実施の形態１では、類似度画像の各画素の画素値が浮動小数点表現される場合を示したが、本発明はこれに限定されるものではなく、各画素の画素値が整数表現される場合に適用することもできる。このため、本実施の形態２では、各類似度画像の各画素の画素値が整数表現される場合を示すこととする。なお、対応点探索装置の全体構成などは、上記実施の形態１と同様のものとなるので、ここでは重複する説明を省略し、正規化処理部１６の内部処理に焦点を当てて説明することとする。
【００８２】
実施の形態１のように、類似度画像の各画素の画素値を浮動小数点で表現した場合には、類似度画像の各画素の画素値から最大値を減算して最大値の画素値を０にすることが有効であるが、類似度画像の画素値が整数表現される場合には、このような正規化処理を適用することができない。したがって、本実施の形態２では、類似度画像の最大値から一定範囲の値を整数型で表現できる値の範囲内の値に正規化することとしている。
【００８３】
具体的には、類似度画像の最大値がＣmaxであり、整数型で表現できる値の範囲が０〜Imaxの場合には、正規化後の類似度画像の値C'mn(u,v)を
Ｃ’mn（ｕ，ｖ）＝Ｃmn（ｕ，ｖ）  −  Ｃmax  +  Ｉmax×K
により求める。ただし、Ｃ’mn（ｕ，ｖ）が０より小さい場合にはＣ’mn（ｕ，ｖ）＝０とする。また、定数Ｋの値は、K＝M(M+1)N(N+1)／４よりも小さい値であればよい。
【００８４】
図２０は、本実施の形態２に係る正規化処理の概念を説明するための説明図である。なお、ここでは説明の便宜上、ある類似度画像の値を模式的に２次元平面の分布として表現している。同図（ａ）に示すように、類似度画像の最大値がＣmaxであり、整数型で表現できる値の範囲が０〜Ｉmaxである場合には、この最大値の値を小さくしないと累積加算により桁あふれが生じてしまう。したがって、このＩmaxに定数Ｋを乗じた範囲に最大値Cmaxを抑える必要がある。
【００８５】
このため、本実施の形態２では、同図（ｂ）に示すように、最大値ＣmaxからＩmax×Ｋを減じた値を各画素値からそれぞれ減じることにより、類似度画像の各画素値がＩmax×K以下になるようにしている。そして、０以下の値が出現しないように、０以下の画素値については０にする切り詰めをおこなう。このため、正規化処理後に累積加算したとしても、桁あふれは生じない。
【００８６】
次に、定数Ｋのとり得る値の範囲について説明する。図２１は、定数Ｋのとり得る値の範囲を説明するための説明図である。なお、ここでは説明の便宜上、同図（ａ）に示すように、類似度画像の画素の画素値の最大がｐであるものとし、Ｎ×Ｍ個の類似度画像が存在するものとする。同図（ｂ）に示すように、ｊ方向（図中の右方向）に類似度画像の画素値を再帰的に累積加算すると、最右端の類似度画像の画素の画素値の最大は、Ｎｐとなる。その後、同図（ｃ）に示すように、−ｊ方向（図中の左方向）に類似度画像の画素値を再帰的に累積加算すると、最左端の類似度画像の画素の画素値は、Ｎ（Ｎ＋１）ｐ／２となる。
【００８７】
さらに、同図（ｄ）に示すように、ｉ方向（図中の下方向）に類似度画像の画素値を再帰的に累積加算すると、左下端の類似度画像の画素の画素値は、ＭＮ（Ｎ＋１）ｐ／２となる。その後、同図（ｅ）に示すように、−ｉ方向（図中の上方向）に類似度画像の画素値を再帰的に累積加算すると、左上端の類似度画像の画素の画素値は、（Ｍ（Ｍ＋１）／２）（Ｎ（Ｎ＋１）／２）×ｐとなる。
【００８８】
したがって、この左上端の類似度画像の画素の画素値を再度ｐに戻すためには、Ｍ（Ｍ＋１）Ｎ（Ｎ＋１）／４で割り算すれば良いことが分かるので、ここではＫの値をＭ（Ｍ＋１）Ｎ（Ｎ＋１）／４未満の値としている。
【００８９】
上述してきたように、本実施の形態２では、類似度画像の各画素の画素値が整数で表現される場合に、累積加算された各類似度画像の各画素の画素値から該類似度画像内の最大の画素値を減じるとともに、その結果に所定の値を加算して正規化するよう構成したので、画素値が整数表現される場合であっても累積加算に伴う桁あふれの悪影響を防止することができる。
【００９０】
なお、上記実施の形態１および２では、各類似度画像をｊ方向、−ｊ方向、ｉ方向、−ｉ方向の順序で再帰的に累積加算する場合を示したが、本発明は必ずしもこれに限定されるものではなく、斜め方向或いは一方向のみについて累積加算する場合に適用することもできる。一方向のみであっても、類似度が加算されることにより一定の大局情報が得られる。
【００９１】
また、本実施の形態１および２では、各類似度画像をｊ方向、−ｊ方向、ｉ方向、−ｉ方向の順序で一巡の累積加算をおこなった後に正規化処理をおこなうこととしたが、本発明はこれに限定されるものではなく、各方向の累積加算をおこなった時点で正規化処理をおこなうこともできる。さらに、本実施の形態１および２では、類似度画像の各画素値から最大値を減算することとしたが、たとえば大きさが２番目のような最大値に近い値を減算することもできる。最大値よりも小さい値で減算すればするほど、桁あふれが生ずる可能性が高くなるが、３番目、４番目等の値を減算することもできる。
【００９２】
【発明の効果】
以上説明したように、請求項１の発明によれば、入力画像と参照画像の間の類似度を画素値として持つ複数の類似度画像を生成し、生成した所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点とするよう構成したので、桁あふれやサチュレーションの影響を防止しつつ正確かつ高速に対応点を求めることが可能な対応点探索装置が得られるという効果を奏する。
【００９３】
また、請求項２の発明によれば、所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算し、累積加算した各類似度画像の画素値を正規化し、各類似度画像のうちの最大の画素値を持つ画素の画素位置の変動幅が所定値未満となった場合に該画素位置を対応点として特定するよう構成したので、累積加算に伴うサチュレーションの影響を正規化により防止しつつ対応点を正確に特定することが可能な対応点探索装置が得られるという効果を奏する。
【００９４】
また、請求項３の発明によれば、各類似度画像を横方向、該横方向の逆方向、縦方向、該縦方向の逆方向の順で累積加算をおこなった後に、各類似度画像の画素値を正規化するよう構成したので、異なる方向への繰り返し処理によって最適化の微調整をおこないつつ、累積加算に伴うサチュレーションの影響を防止することが可能な対応点探索装置が得られるという効果を奏する。
【００９５】
また、請求項４の発明によれば、類似度画像の各画素の画素値が浮動小数点で表現される場合に、累積加算された各類似度画像の各画素の画素値から該類似度画像内の最大の画素値を減じて正規化するよう構成したので、最大値を用いた減算という簡単な演算で高速にサチュレーションの影響を防止することが可能な対応点探索装置が得られるという効果を奏する。
【００９６】
また、請求項５の発明によれば、類似度画像の各画素の画素値が浮動小数点で表現される場合に、累積加算された各類似度画像の各画素の画素値から全ての類似度画像内の最大の画素値を減じて正規化するよう構成したので、複数の類似度画像の最大値を用いた減算という簡単な演算で高速にサチュレーションの影響を防止することが可能な対応点探索装置が得られるという効果を奏する。
【００９７】
また、請求項６の発明によれば、類似度画像の各画素の画素値が整数で表現される場合に、累積加算された各類似度画像の各画素の画素値から該類似度画像内の最大の画素値を減じるとともに、その結果に所定の値を加算して正規化するよう構成したので、画素値が整数表現される場合であっても累積加算に伴う桁あふれの悪影響を防止することが可能な対応点探索装置が得られるという効果を奏する。
【００９８】
また、請求項７の発明によれば、、縦方向にＭ個および横方向にＮ個の類似度画像が存在し、各類似度画像の画素値を整数型で表現できる範囲が０からＩmaxである場合に、このＩmaxにM(M+1)N(N+1)／４を乗じた値よりも小さな値を所定の値とするよう構成したので、桁あふれを起こす事態を未然に防ぎ正確に対応点を検出することが可能な対応点探索装置が得られるという効果を奏する。
【００９９】
また、請求項８の発明によれば、所定の画像入力部から入力された参照画像を所定の記憶部に一時記憶し、画像入力部から入力された入力画像と記憶部に一時記憶された参照画像の間の類似度を画素値として持つ複数の類似度画像を生成し、生成した所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点とするよう構成したので、桁あふれやサチュレーションの影響を防止しつつ正確かつ高速に対応点を求めることが可能な対応点探索処理方法が得られるという効果を奏する。
【０１００】
また、請求項９の発明によれば、所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算処理し、累積加算処理した各類似度画像の画素値を正規化処理し、各類似度画像のうちの最大の画素値を持つ画素の画素位置の変動幅が所定値未満となった場合に該画素位置を対応点として特定処理するよう構成したので、累積加算に伴うサチュレーションの影響を正規化により防止しつつ対応点を特定することが可能な対応点探索処理方法が得られるという効果を奏する。
【０１０１】
また、請求項１０の発明によれば、所定の画像入力部から入力された参照画像を所定の記憶部に一時記憶し、画像入力部から入力された入力画像と記憶部に一時記憶された参照画像の間の類似度を画素値として持つ複数の類似度画像を生成し、生成した所定の方向に並んだ複数の類似度画像の各画素の周辺画素の画素値を他の類似度画像の画素値に累積加算しつつ正規化する処理を繰り返し、各類似度画像の最大の画素値を持つ画素位置を対応点とするよう構成したので、桁あふれやサチュレーションの影響を防止しつつ正確かつ高速に対応点を求めることが可能な対応点探索処理プログラムが得られるという効果を奏する。
【図面の簡単な説明】
【図１】この発明の実施の形態に係る対応点探索装置の構成を示す機能ブロック図である。
【図２】本実施の形態で用いる参照画像および入力画像の一例を示す図である。
【図３】参照部分画像の一例を示す図である。
【図４】入力部分画像の一例を示す図である。
【図５】類似度画像の作成概念を説明するための説明図である。
【図６】図４に示した各入力部分画像に対応する類似度画像を示す図である。
【図７】累積加算手順を説明するための説明図である。
【図８】ｊ方向の累積加算処理を説明するための説明図である。
【図９】−ｊ方向の累積加算処理を説明するための説明図である。
【図１０】ｉ方向の累積加算処理を説明するための説明図である。
【図１１】−ｉ方向の累積加算処理を説明するための説明図である。
【図１２】累積加算後の類似度画像を示す図である。
【図１３】図１２に示した類似度画像の最大値の位置を示す図である。
【図１４】対応点に基づいて再構成した入力画像の歪み（変形）の一例を示す図である。
【図１５】図１に示した正規化処理部の処理概念を説明するための説明図である。
【図１６】図１に示した対応点探索装置の処理手順を示すフローチャートである。
【図１７】累積加算処理手順の一例を示すフローチャートである。
【図１８】最大値フィルターを用いて累積加算処理をおこなう場合の処理手順の一例を示すフローチャートである。
【図１９】最大値フィルターの処理手順の一例を示すフローチャートである。
【図２０】本実施の形態２に係る正規化処理の概念を説明するための説明図である。
【図２１】定数Ｋのとり得る値の範囲を説明するための説明図である。
【図２２】従来技術によるサチュレーションの問題を説明するための説明図である。
【符号の説明】
１    対応点探索装置
１０    画像入力部
１１    分割処理部
１２    参照部分画像一時記憶部
１３    類似度画像作成部
１４    累積加算処理部
１５    対応点決定部
１６    正規化処理部
２１    参照画像
２２    入力画像
５１    入力部分画像
５２    参照部分画像
５３    類似度画像
【図１】
0003898936.tif 000003
【図２】
0003898936.tif 000004
【図３】
0003898936.tif 000005
【図４】
0003898936.tif 000006
【図５】
0003898936.tif 000007
【図６】
0003898936.tif 000008
【図７】
0003898936.tif 000009
【図８】
0003898936.tif 000010
【図９】
0003898936.tif 000011
【図１０】
0003898936.tif 000012
【図１１】
0003898936.tif 000013
【図１２】
0003898936.tif 000014
【図１３】
0003898936.tif 000015
【図１４】
0003898936.tif 000016
【図１５】
0003898936.tif 000017
【図１６】
0003898936.tif 000018
【図１７】
0003898936.tif 000019
【図１８】
0003898936.tif 000020
【図１９】
0003898936.tif 000021
【図２０】
0003898936.tif 000022
【図２１】
0003898936.tif 000023
【図２２】
0003898936.tif 000024