(57)【要約】【課題】画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得すること。【解決手段】画像入力部１０から参照画像と入力画像をそれぞれ入力し、分割処理部１１で参照部分画像および入力部分画像をそれぞれ作成、類似度画像作成部１３で参照部分画像と入力部分画像の類似度を求めた類似度画像をそれぞれ作成し、累積加算処理部１４で複数の類似度画像の累積加算処理を各方向ごと独立して再帰的におこない、類似度画像更新部１５でこれらの累積加算結果から得られる各画素の周辺画素の最大値を類似度画像の各画素の画素値に累積加算して類似度画像を更新し、更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまでこれらの処理を繰り返して、対応点決定部１６が対応点を決定する。【選択図】      図１
2004287522.tif 000002
【特許請求の範囲】
【請求項１】
入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索方法であって、
前記入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成する類似度画像生成工程と、
前記類似度画像生成工程により生成された複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返す累積加算工程と、前記累積加算工程により累積加算処理された類似度画像の各画素の周辺画素の最大値を前記類似度画像生成工程により生成された類似度画像の各画素の画素値に累積加算して前記類似度画像を更新する類似度画像更新工程と、
前記類似度画像更新工程により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまで前記累積加算工程による累積加算と前記類似度画像更新工程による更新を繰り返して、前記入力画像と参照画像の対応点を決定する対応点決定工程と
を含んだことを特徴とする画像の対応点探索方法。
【請求項２】
前記対応点決定工程は、前記類似度画像更新工程により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となったときの更新後の各類似度画像の最大値の位置を前記対応点として決定することを特徴とする請求項１に記載の画像の対応点探索方法。
【請求項３】
入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索装置であって、
前記入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成する類似度画像生成手段と、
前記類似度画像生成手段により生成された複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返す累積加算手段と、前記累積加算手段により累積加算処理された類似度画像の各画素の周辺画素の最大値を前記類似度画像生成手段により生成された類似度画像の各画素の画素値に累積加算して前記類似度画像を更新する類似度画像更新手段と、
前記類似度画像更新手段により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となった際の最大値の位置に基づいて、前記入力画像と参照画像の対応点を決定する対応点決定手段と
を備えたことを特徴とする画像の対応点探索装置。
【請求項４】
入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索プログラムであって、
前記入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成する類似度画像生成手順と、
前記類似度画像生成手順により生成された複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返す累積加算手順と、前記累積加算手順により累積加算処理された類似度画像の各画素の周辺画素の最大値を前記類似度画像生成手順により生成された類似度画像の各画素の画素値に累積加算して前記類似度画像を更新する類似度画像更新手順と、
前記類似度画像更新手順により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまで前記累積加算手順による累積加算と前記類似度画像更新手順による更新を繰り返して、前記入力画像と参照画像の対応点を決定する対応点決定手順と
をコンピュータに実行させることを特徴とする画像の対応点探索プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索方法、対応点探索装置および対応点探索プログラムに関し、特に、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる画像の対応点探索方法、対応点探索装置および対応点探索プログラムに関する。
【０００２】
【従来の技術】
従来、スキャナなどの画像入力装置から入力された入力画像をあらかじめ登録した参照画像とを照合する際に、両画像の対応点を探索して画像間の対応付けをおこなう技術が知られている。
【０００３】
たとえば、非特許文献１（従来技術１）には、設定したエネルギー関数を変分法の枠組みにより最小化する標準正則化理論を適用した技術が開示されている。この従来技術１が採用する標準正則化理論は、局所的な情報のみを使った繰り返し計算によりエネルギーを最小化することによって対応点を計算するものであるので、並列分散処理をおこなうことができ、人間の脳情報処理に近い処理を実現できる可能性がある。
【０００４】
また、非特許文献２（従来技術２）には、ＤＰ（Ｄｙｎａｍｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ）を用いて効率的に最適解を探索する２次元ＤＰワープ法を採用した技術が開示されている。この従来技術２によれば、最適化問題を効率的に計算することができる。
【０００５】
ところが、上記従来技術１のものは、局所的な情報のみを使った繰り返し計算によってエネルギーを最小化して対応点を計算するため、初期値の影響が大きくなるという問題や、局所解（ローカルミニマム）に陥り易いことから最適な対応付け結果を得られ難いという問題がある。また、従来技術２のものは、ＤＰによって効率よく最適解を探索できるものの、その計算量が膨大なものになるという問題がある。具体的には、最適解を得るためには画像サイズの指数オーダーの計算時間が必要となる。
【０００６】
これらのことから、本願特許出願人は、特願２００２−０５６６６１号（従来技術３）において、画像間の対応付けをおこなう際に、局所解に陥ることなく安定した対応付け結果を得ることができる画像の対応点探索装置、対応点探索方法およびその方法をコンピュータに実行させるプログラムを提案した。また、非特許文献３において、弛緩法を用いた画像マッチング法（従来技術４）を提案した。
【０００７】
【非特許文献１】
Ｔ．Ｐｏｇｇｉｏ，Ｖ．ＴｏｒｒｅａｎｄＣ．Ｋｏｃｈ，”Ｃｏｍｐｕｔａｔｉｏｎａｌ  ｖｉｓｉｏｎ  ａｎｄ  ｒｅｇｕｌａｒｉｚａｔｉｏｎ  ｔｈｅｏｒｙ”，ＮＡＴＵＲＥ  Ｖｏｌ．３１７，ｐｐ．  ３１４−３１９，１９８５
【非特許文献２】
内田誠一，迫江博昭，”動的計画法に基づく単調連続２次元ワープ法の検討”，信学論（Ｄ−ＩＩ）  Ｖｏｌ．  Ｊ８１−Ｄ−ＩＩ  ｎｏ．  ６，ｐｐ．１２５１−１２５８，Ｊｕｎｅ  １９９８
【非特許文献３】
大西弘之，金出武雄，”大局的弛緩法による画像マッチング”，画像の認識・理解シンポジウム（ＭＩＲＵ２００２），Ｖｏｌ．  １  ，    ｐｐ．９５−１００，Ｊｕｌｙ  ２００２
【０００８】
【発明が解決しようとする課題】
この従来技術３によれば、ｊ方向、−ｊ方向、ｉ方向、−ｉ方向にそれぞれ累積加算した類似度画像をさらに加算する時に、注目する類似度画像に、ｊ方向、−ｊ方向、ｉ方向、−ｉ方向にそれぞれ隣接した類似度画像の近傍領域の最大値を加算することにより、大局的な整合性を考慮することができる。
【０００９】
しかしながら、この従来技術３では、複数の類似度画像を作成し、ｊ方向に累積加算をおこなった後に、−ｊ方向に累積加算をおこない、その後ｉ方向に累積加算をおこない、さらに−ｉ方向に累積加算する一連の処理を繰り返すこととしていたので、これらの処理を並列化することができず、処理を迅速化する上での制約がある。
【００１０】
また、上記従来技術４では、弛緩法の更新式において方向別（ｊ方向、−ｊ方向、ｉ方向、−ｉ方向）に独立に累積加算した４つの類似度画像をさらに加算して１つの類似度画像を作成するようになっており、その際更新された類似度画像の各点には、更新前の値に４倍の重みが付けられ、局所的に重みを付けた更新式を計算しているため、局所解に陥りやすくなるという問題がある。
【００１１】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、画像間の対応付けをおこなう際に、局所解に陥ることなく安定した対応付け結果を高速かつ効率良く取得することができる画像の対応点探索方法、対応点探索装置および対応点探索プログラムを提供することを目的とする。
【００１２】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、請求項１の発明に係る画像の対応点探索方法は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索方法であって、前記入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成する類似度画像生成工程と、前記類似度画像生成工程により生成された複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返す累積加算工程と、前記累積加算工程により累積加算処理された類似度画像の各画素の周辺画素の最大値を前記類似度画像生成工程により生成された類似度画像の各画素の画素値に累積加算して前記類似度画像を更新する類似度画像更新工程と、前記類似度画像更新工程により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまで前記累積加算工程による累積加算と前記類似度画像更新工程による更新を繰り返して、前記入力画像と参照画像の対応点を決定する対応点決定工程とを含んだことを特徴とする。
【００１３】
また、請求項２の発明に係る画像の対応点探索方法は、請求項１の発明において、前記対応点決定工程は、前記類似度画像更新工程により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となったときの更新後の各類似度画像の最大値の位置を前記対応点として決定することを特徴とする。
【００１４】
また、請求項３の発明に係る画像の対応点探索装置は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索装置であって、前記入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成する類似度画像生成手段と、前記類似度画像生成手段により生成された複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返す累積加算手段と、前記累積加算手段により累積加算処理された類似度画像の各画素の周辺画素の最大値を前記類似度画像生成手段により生成された類似度画像の各画素の画素値に累積加算して前記類似度画像を更新する類似度画像更新手段と、前記類似度画像更新手段により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となった際の最大値の位置に基づいて、前記入力画像と参照画像の対応点を決定する対応点決定手段とを備えたことを特徴とする。
【００１５】
また、請求項４の発明に係る画像の対応点探索プログラムは、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索プログラムであって、前記入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成する類似度画像生成手順と、前記類似度画像生成手順により生成された複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返す累積加算手順と、前記累積加算手順により累積加算処理された類似度画像の各画素の周辺画素の最大値を前記類似度画像生成手順により生成された類似度画像の各画素の画素値に累積加算して前記類似度画像を更新する類似度画像更新手順と、前記類似度画像更新手順により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまで前記累積加算手順による累積加算と前記類似度画像更新手順による更新を繰り返して、前記入力画像と参照画像の対応点を決定する対応点決定手順とをコンピュータに実行させることを特徴とする。
【００１６】
【発明の実施の形態】
以下に添付図面を参照して、この発明に係る画像の対応点探索方法、対応点探索装置および対応点探索プログラムの実施の形態を詳細に説明する。
【００１７】
図１は、本実施の形態で用いる対応点探索装置の構成を示す機能ブロック図である。同図に示す対応点探索装置１は、大まかには、（１）入力画像を分割した入力部分画像と参照画像を分割した参照部分画像との間の類似度を示す類似度画像を作成する類似度画像作成段階と、（２）複数の類似度画像を累積加算した結果に基づいて最適な対応点を決定する対応点決定段階の２つの段階の処理を行う。
【００１８】
具体的には、（１）類似度画像作成段階では、たとえば７×７画素のサイズからなる参照部分画像を２１×２１画素のサイズからなる入力部分画像内を移動させつつ順次相関値を求め、この相関値を画素値として持つ類似度画像を作成する。このため、この類似度画像は、参照部分画像上の中心点が入力部分画像上の点にどの程度類似しているかを示すことになる。
【００１９】
次に、（２）対応点決定段階では、各類似度画像の画素値を垂直方向および水平方向別に独立に累積加算を繰り返した後に、これらの累積加算結果から得られる各画素の周辺画素の最大値を類似度画像の各画素の画素値に累積加算して類似度画像を更新し、更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまでこれらの処理を繰り返して、入力部分画像上での対応点を求める。
【００２０】
次に、図１に示した対応点探索装置１の構成について説明する。なお、ここでは参照画像、入力画像の順に画像を入力する場合を示すこととする。図１に示すように、この対応点探索装置１は、画像入力部１０と、分割処理部１１と、参照部分画像一時記憶部１２と、類似度画像作成部１３と、累積加算処理部１４と、類似度画像更新部１５と、対応点決定部１６とからなる。
【００２１】
画像入力部１０は、縦横のサイズＩ、Ｊからなる参照画像Ｉ０（ｉ，ｊ）および入力画像Ｉ１（ｉ，ｊ）（０≦ｉ≦Ｉ−１，０≦ｊ≦Ｊ−１）を入力する入力部である。具体的には、光学的に原稿を読み取って画像を取得するスキャナや、ネットワークから画像を取得するインターフェース部や、二次記憶装置から画像を読み出す読み出し部が該当する。ここで、この入力画像とは、対応点の探索対象となる画像であって、歪みや変形を伴うものであっても良い。これに対して、参照画像とは、入力画像の比較の対象となる画像であり、歪みなどを伴わないものであることが望ましい。
【００２２】
図２（ａ）には参照画像２１を示しており、同図（ｂ）には入力画像２２を示している。これらの参照画像２１および入力画像２２は、いずれもアルファベット「ａ」の文字画像であり、３２×３２画素からなる。
【００２３】
分割処理部１１は、画像入力部１０により入力された入力画像および参照画像を入力部分画像および参照部分画像にそれぞれ分割する処理部である。ただし、入力画像の分割手順と参照画像の分割手順はそれぞれ異なる。
【００２４】
参照画像を分割する場合には、参照画像上で縦方向にＭ個、横方向にＮ個サンプリングした点（ｐｍ，ｑｎ）（０≦ｍ≦Ｍ−１，０≦ｎ≦Ｎ−１）を中心とした参照部分画像を作成する。図３は、図２（ａ）に示した参照画像２１の分割結果の一例を示す図であり、同図に示すように、ここでは３２×３２画素の参照画像２１を７×７画素からなる２５個の参照部分画像に分割している。具体的には、ｐｍ＝ｒｏｕｎｄ（Ｉ／Ｍ）、ｑｎ＝ｒｏｕｎｄ（Ｊ／Ｎ）としている。ただし、ｒｏｕｎｄ（）は四捨五入を示している。
【００２５】
入力画像を分割する場合には、参照画像を分割する場合と異なり、各入力部分画像の一部が重なり合う重複したデータを持つように分割する。図４は、図２（ｂ）に示した入力画像２２の分割結果の一例を示す図であり、同図に示すように、ここでは３２×３２画素の入力画像２２を２１×２１画素からなる２５個の入力部分画像に分割している。
【００２６】
参照部分画像一時記憶部１２は、分割処理部１１で分割した各参照部分画像を一時記憶する記憶部であり、類似度画像作成部１３が類似度画像を作成する際に該当する参照部分画像が取り出される。
【００２７】
類似度画像作成部１３は、入力部分画像と参照部分画像の間の変形を考慮した類似度を算定して、該類似度を画素値として持つ類似度画像Ｃ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）（０≦ｍ≦Ｍ−１，０≦ｎ≦Ｎ−１，０≦ｕ≦Ｕ−１，０≦ｖ≦Ｖ−１）を作成する処理部である。ただし、Ｕ，Ｖはそれぞれ類似度画像の縦横のサイズであるものとする。この類似度として正規化相関係数を用いることができる。
【００２８】
図５は、参照部分画像と入力部分画像から類似度画像を作成する概念を説明するための説明図である。なお、ここでは図３および図４の２行２列に位置する入力部分画像と参照部分画像を用いることとする。
【００２９】
同図に示すように、入力部分画像５１と参照部分画像５２の類似度を求める場合には、参照部分画像５２の中心画素を入力部分画像５２の左上部の画素に対応づけて正規化相関係数を計算し、その計算結果を類似度画像５３の左上部の画素の画素値とする。その後、参照部分画像５２を右にずらし、同様の処理をおこなう。上記処理を参照部分画像５２をずらしながら入力部分画像５１の全画素についておこなうことにより、類似度画像５３が求められる。
【００３０】
かかる類似度画像の作成処理を各入力部分画像ごとにおこなうと、図６に示すような複数の類似度画像が得られる。なお、参照部分画像の全ての画素の画素値が一定値である場合には、正規化相関係数の分母がゼロとなるため、この場合の類似度画像の画素値もゼロとなる。
【００３１】
累積加算処理部１４は、図７に示すように、各類似度画像をｊ方向、−ｊ方向、ｉ方向、−ｉ方向にそれぞれ独立して累積加算する処理部である。具体的には、類似度画像全体Ｃ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）を４枚複写して、これをそれぞれＤ１（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）、Ｄ２（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）、Ｄ３（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）、Ｄ４（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）とし、それぞれｊ方向、−ｊ方向、ｉ方向、−ｉ方向の累積加算に使用する。たとえば、Ｄ１（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）を用いてｊ方向に累積加算する場合には、ｎ＝１〜Ｎ−１の類似度画像について、
Ｄ１（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＝Ｃ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＋α・Ｍａｘ（Ｄ１（ｍ  ，  ｎ−１  ，  ｐ  ，  ｑ））
を順次再帰的に計算する。ただし、Ｍａｘ（）は最大値を示し、αは定数であり、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−１、ｕ−１≦ｐ≦ｕ＋１、ｖ−１≦ｑ≦ｖ＋１とする。
【００３２】
すなわち、ｊ方向に累積加算する場合には、図８に示すように、Ｄ１（ｍ  ，  ｎ−１  ，  ｕ  ，    ｖ）を中心とする８近傍内の９画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）の画素値に加算する処理を再帰的に繰り返すことになる。
【００３３】
また、−ｊ方向に累積加算する場合には、ｎ＝Ｎ−２〜０の類似度画像について、
Ｄ３（ｍ  ，  ｎ  ，  ｕ  ，  ｖ  ）＝Ｃ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＋α・Ｍａｘ（Ｄ３（ｍ  ，  ｎ＋１  ，  ｐ  ，  ｑ））
を順次再帰的に計算する。ただし、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−２とする。すなわち、−ｊ方向に累積加算する場合には、図９に示すように、Ｄ３（ｍ  ，  ｎ＋１  ，ｕ  ，  ｖ）を中心とする８近傍内の９画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）の画素値に加算する処理を再帰的に繰り返すことになる。
【００３４】
また、ｉ方向に累積加算する場合には、ｍ＝１〜Ｍ−１の類似度画像について、
Ｄ２（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＝Ｃ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＋α・Ｍａｘ（Ｄ２（ｍ−１  ，  ｎ  ，  ｐ  ，  ｑ））
を順次再帰的に計算する。ただし、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、１≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−１とする。すなわち、ｉ方向に累積加算する場合には、図１０に示すように、Ｄ２（ｍ−１  ，  ｎ  ，  ｕ  ，  ｖ）を中心とする８近傍内の９画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）の画素値に加算する処理を再帰的に繰り返すことになる。
【００３５】
また、−ｉ方向に累積加算する場合には、ｍ＝Ｍ−２〜０の類似度画像について、
Ｄ４（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＝Ｃ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＋α・Ｍａｘ（Ｄ４（ｍ＋１  ，  ｎ  ，  ｐ  ，  ｑ））
を順次再帰的に計算する。ただし、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−２、０≦ｎ≦Ｎ−１とする。すなわち、−ｉ方向に累積加算する場合には、図１１に示すように、Ｄ４（ｍ＋１  ，  ｎ  ，    ｕ  ，  ｖ）を中心とする８近傍内の９画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）の画素値に加算する処理を再帰的に繰り返すことになる。
【００３６】
類似度画像更新部１５は、累積加算処理部１４の累積加算後の類似度画像に基づいて類似度画像を更新する処理部である。具体的には、まず各方向についての累積加算処理をおこなったならば、図１２の概念図に示すように、
2004287522.tif 000003
の算定式によりＣ（  ｍ  ，  ｎ  ，  ｕ  ，  ｖ）を更新する。
【００３７】
その後、対応点決定部１６は、各類似度画像の最大値の位置を検出し、それらの位置と前回の各類似度画像の最大値の位置との変化が所定の範囲内でなければ累積加算処理をフィードバックして繰り返し、所定の範囲内となった時点で繰り返しを終了し、そのときの各類似度画像の最大値の位置を対応点として決定する。なお、上述の前回の各類似度画像というのは、初回処理の場合は、類似度画像作成部１３により作成された各類似度画像であり、初回以降は類似度画像更新部１５により前回更新処理された各類似度画像となる。
【００３８】
たとえば、累積加算処理および更新処理によって図１３に示す各類似度画像が得られた場合には、各類似度画像の最大値の位置の前回の類似度画像の最大値の位置からの変化分を調べ、その変化分が所定の範囲内となった場合には、この時の最大値の位置を対応点とする。この最大値の位置の様子を図１４に示す。そして、この対応点に基づいて入力画像の歪みを図示すると図１５のようになる。
【００３９】
次に、図１に示した対応点検索装置１の処理手順について説明する。なお、上記説明と一部重複するが、図２〜図１５を用いて処理の流れを例示しつつ処理手順について説明することとする。
【００４０】
図１６は、図１に示した対応点検索装置１の処理手順を示すフローチャートである。同図に示すように、この対応点検出装置１が参照画像と入力画像を取得したならば、この参照画像を参照部分画像に分割する（ステップＳ１０１）。たとえば、図２（ａ）に示した３２×３２画素の参照画像２１を図３に示した７×７画素からなる２５個の参照部分画像に分割して記憶する。この参照部分画像は、参照したい画像毎に予め記憶しておいてもよいし、また、参照部分画像ではなく、参照画像のみを予め別途記憶しておき、後述する入力画像と参照画像との類似度の計算の際に、記憶された参照画像から参照部分画像に分割してもよい。
【００４１】
その後、入力画像を入力部分画像に分割する（ステップＳ１０２）。たとえば、図２（ｂ）に示した３２×３２画素の入力画像２２を図４に示した２１×２１画素からなる２５個の入力部分画像に分割する。
【００４２】
そして、この参照部分画像と入力部分画像の間の類似度画像を作成する（ステップＳ１０３）。たとえば、図５に示すようにして入力部分画像５１と参照部分画像５２の類似度を画素値とする類似度画像５３の作成を各入力部分画像ごとにおこなって、図６に示したような複数の類似度画像を作成する。続いて、各類似度画像の画素値が最大となる位置（以下、「最大値の位置」と記す）を検出する（ステップＳ１０４）。
【００４３】
その後、４方向、すなわち、ｊ方向の累積加算処理、−ｊ方向の累積加算処理、ｉ方向の累積加算処理、−ｉ方向の累積加算処理をそれぞれ独立しておこない（ステップ１０５）、ｊ、−ｊ、ｉ、−ｉ方向の累積加算された類似度画像の各画素の８近傍内の９画素の最大値をステップＳ１０３で作成された類似度画像の各画素に加算して各類似度画像を更新し（ステップＳ１０６）、続いて、この更新された類似度画像の最大値の位置を検出する（ステップＳ１０７）。具体的には、図８〜図１２に示した加算処理を繰り返すことにより、図１３に示したような類似度画像を作成し、図１４に示すような各類似度画像の最大値の位置を検出する。
【００４４】
次に、各類似度画像の最大値の位置変動を算出し（ステップＳ１０８）、すべての最大値の位置変動が所定値以内であるか否かを調べ（ステップＳ１０９）、所定値以内でなければ（ステップＳ１０９否定）、ステップＳ１０５に移行して同様の処理を繰り返し、所定値以内であれば（ステップＳ１０９肯定）、この位置を対応点と決定し（ステップＳ１１０）、処理を終了する。なお、上述のステップＳ１０９における処理は、各類似度画像の最大値の位置の前回の各類似度画像の最大値の位置からの変化分が所定値以内であるか否かを調べるという処理であり、所定値以内であれば、ステップＳ１１０において、更新処理後の各類似度画像の最大値の位置を入力画像の参照画像に対する対応点と決定する。
【００４５】
なお、ここでは説明の便宜上、ｊ方向の累積加算処理、−ｊ方向の累積加算処理、ｉ方向の累積加算処理および−ｉ方向の累積加算処理を順次おこなうこととしたが、これらはそれぞれ独立した処理をおこなうことができるので、並列処理化することもできる。
【００４６】
次に、図１に示した累積加算処理部１４によるｊ方向の累積加算処理手順について詳細に説明する。図１７は、図１に示した累積加算処理部１４によるｊ方向の累積加算処理手順を示すフローチャートである。なお、−ｊ方向、ｉ方向、−ｉ方向の累積加算処理も同様におこなうことができる。
【００４７】
同図に示すように、まず変数ｍ、ｕおよびｖを０にするとともに、変数ｎを１とする初期化をおこなう（ステップＳ２０１〜Ｓ２０４）。ここで、この変数ｍはｉ方向のインデックスとして用いる変数であり、変数ｎはｊ方向のインデックスとして用いる変数である。また、変数ｕ，ｖは探索範囲を示すｉ方向およびｊ方向の変数である。
【００４８】
そして、この初期化を終えたならば、
Ｄ１（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＝Ｃ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＋α・Ｍａｘ（Ｄ１（ｍ  ，  ｎ−１  ，  ｐ  ，  ｑ））
の算定式による計算をおこなう（ステップＳ２０５）。
【００４９】
その後、変数ｖをインクリメントし（ステップＳ２０６）、この変数ｖがＶよりも小さければ（ステップＳ２０７肯定）、ステップＳ２０５に移行して加算処理を繰り返す。つまり、探索範囲をｊ方向にずらすのである。
【００５０】
これに対して、変数ｖがＶ以上であれば（ステップＳ２０７否定）、変数ｕをインクリメントし（ステップＳ２０８）、この変数ｕがＵよりも小さければ（ステップＳ２０９肯定）、ステップＳ２０４に移行して加算処理を繰り返す。つまり、探索範囲をｉ方向にずらすことになる。
【００５１】
そして、変数ｕがＵ以上であれば（ステップＳ２０９否定）、ある画素についての計算を終了し、次の画素に移行する。具体的には、変数ｎをインクリメントして注目画素をｊ方向に移行させた後に（ステップＳ２１０）、この変数ｎをＮと比較し（ステップＳ２１１）、この変数ｎがＮよりも小さければ（ステップＳ２１１肯定）、ステップＳ２０３に移行して加算処理を繰り返す。
【００５２】
これに対して、変数ｎがＮ以上であれば（ステップＳ２１１否定）、変数ｍをインクリメントして注目画素をｉ方向に移行させた後に（ステップＳ２１２）、この変数ｍがＭよりも小さければ（ステップＳ２１３肯定）、ステップＳ２０２に移行して加算処理を繰り返し、変数ｍがＭ以上であれば（ステップＳ２１３否定）、処理を終了する。上記一連の処理をおこなうことにより、各類似度画像の全画素についてｊ方向の累積加算結果が得られることになる。
【００５３】
ところで、上記図１７のフローチャートでは、変数ｕ，ｖのインクリメントをおこないながら最大値を算出していた。別の計算方法として、あらかじめＣ（ｍ  ，  ｎ−１  ，  ｕ  ，  ｖ）に最大値フィルターをかけた最大値フィルター画像Ｄ１’（ｍ  ，    ｎ−１，  ｕ  ，  ｖ）を作成しておき、α倍してからＣ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）と加算することもできる。
【００５４】
そこで、かかる最大値フィルターを用いる場合の処理手順を図１８および図１９を用いて説明する。図１８は、図１に示した累積加算処理部１４による最大値フィルターを用いたｊ方向の累積加算処理手順を示すフローチャートであり、図１９は、最大値フィルターの処理手順を示すフローチャートである。
【００５５】
図１８に示すように、変数ｍを０に初期化し（ステップＳ３０１）、変数ｎを１に初期化した後（ステップＳ３０２）、最大値フィルターＤ１’（ｍ  ，  ｎ−１  ，  ｕ  ，  ｖ）を算定する（ステップＳ３０３）。
【００５６】
具体的には、図１９に示すように、変数ｕ，ｖを０に初期化した後に（ステップＳ４０１〜Ｓ４０２）、Ｄ１’（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＝Ｍａｘ［Ｄ１（ｍ  ，  ｎ  ，  ｐ  ，  ｑ）］を計算する（ステップＳ４０３）。ただし、ｕ−１≦ｐ≦ｕ＋１、ｖ−１≦ｑ≦ｖ＋１とする。そして、ｖをインクリメントして（ステップＳ４０４）、この変数ｖがＶよりも小さい場合には（ステップＳ４０５肯定）、ステップＳ４０３に移行して同様に計算をおこなう。また、変数ｖがＶ以上である場合には（ステップＳ４０５否定）、変数ｕをインクリメントして（ステップＳ４０６）、この変数ｕがＵよりも小さい場合には（ステップＳ４０６肯定）、ステップＳ４０２に移行して同様の処理を繰り返し、結果的に最大値を求める。
【００５７】
このようにして最大値フィルターを算定したならば、変数ｕおよびｖを０に初期化した後（ステップＳ３０４〜Ｓ３０５）、
Ｄ１（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＝Ｃ（ｍ  ，  ｎ  ，  ｕ  ，  ｖ）＋α・Ｍａｘ（Ｄ１’（ｍ  ，  ｎ−１  ，  ｐ  ，  ｑ））
の算定式による計算をおこなう（ステップＳ３０６）。
【００５８】
その後、変数ｖをインクリメントし（ステップＳ３０７）、この変数ｖがＶよりも小さければ（ステップＳ３０８肯定）、ステップＳ３０６に移行して加算処理を繰り返す。つまり、探索範囲をｊ方向にずらすのである。
【００５９】
これに対して、変数ｖがＶ以上であれば（ステップＳ３０８否定）、変数ｕをインクリメントし（ステップＳ３０９）、この変数ｕがＵよりも小さければ（ステップＳ３１０肯定）、ステップＳ３０５に移行して加算処理を繰り返す。つまり、探索範囲をｉ方向にずらすことになる。
【００６０】
そして、変数ｕがＵ以上であれば（ステップＳ３１０否定）、ある画素についての計算を終了し、次の画素に移行する。具体的には、変数ｎをインクリメントして注目画素をｊ方向に移行させた後に（ステップＳ３１１）、この変数ｎをＮと比較し（ステップＳ３１２）、この変数ｎがＮよりも小さければ（ステップＳ３１２肯定）、ステップＳ３０３に移行して加算処理を繰り返す。
【００６１】
これに対して、変数ｎがＮ以上であれば（ステップＳ３１２否定）、変数ｍをインクリメントして注目画素をｉ方向に移行させた後に（ステップＳ３１３）、この変数ｍがＭよりも小さければ（ステップＳ３１４肯定）、ステップＳ３０２に移行して加算処理を繰り返し、変数ｍがＭ以上であれば（ステップＳ３１４否定）、処理を終了する。
【００６２】
上述してきたように、本実施の形態によれば、画像入力部１０から参照画像と入力画像をそれぞれ入力し、分割処理部１１で参照部分画像および入力部分画像をそれぞれ作成、類似度画像作成部１３で参照部分画像と入力部分画像の類似度を求めた類似度画像をそれぞれ作成し、累積加算処理部１４で複数の類似度画像の累積加算処理を各方向ごと独立して再帰的に行い、更新前の値に重みが付かないように、類似度画像更新部１５で累積加算処理前の類似度画像の各画素の画素値に対して，４方向の類似度画像の累積加算処理後の画素値を加算して類似度画像を更新し、その結果に基づいて対応点決定部１６が対応点を決定するよう構成したので、大局的な最適化が行われローカルミニマムに陥るケースを低減することができる。
【００６３】
なお、本実施の形態では、説明の便宜上、参照画像と入力画像のサイズが同じ場合を示したが、本発明はこれに限定されるものではなく、参照画像と入力画像のサイズを異なる場合に適用することもできる。かかる場合にも同様の処理をおこなうことができる。
【００６４】
また、本実施の形態では、各類似度画像をｊ方向、−ｊ方向、ｉ方向、−ｉ方向の順序で再帰的に累積加算する場合を示したが、本発明は必ずしもこれに限定されるものではなく、斜め方向或いは一方向のみについて累積加算する場合に適用することもできる。一方向のみであっても、類似度が加算されることにより一定の大局情報が得られる。
【００６５】
また、本実施の形態では、類似度として正規化相関係数を用いた場合を示したが、本発明はこれに限定されるものではなく、ユークリッド距離などの他の指標を類似度として用いることもできる。
【００６６】
【発明の効果】
以上説明したように、本発明によれば、入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成し、生成した複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返し、累積加算処理された類似度画像の各画素の周辺画素の最大値を類似度画像の各画素の画素値に累積加算して類似度画像を更新する処理を更新前後の各類似度画像の最大値の位置の変動が所定値未満となるまで繰り返し、入力画像と参照画像の対応点を決定するよう構成したので、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる。
【図面の簡単な説明】
【図１】この発明の実施の形態に係る対応点探索装置の構成を示す機能ブロック図である。
【図２】本実施の形態で用いる参照画像および入力画像の一例を示す図である。
【図３】参照部分画像の一例を示す図である。
【図４】入力部分画像の一例を示す図である。
【図５】類似度画像の作成概念を説明するための説明図である。
【図６】図４に示した各入力部分画像に対応する類似度画像を示す図である。
【図７】累積加算手順を説明するための説明図である。
【図８】ｊ方向の累積加算処理を説明するための説明図である。
【図９】−ｊ方向の累積加算処理を説明するための説明図である。
【図１０】ｉ方向の累積加算処理を説明するための説明図である。
【図１１】−ｉ方向の累積加算処理を説明するための説明図である。
【図１２】各累積加算結果を加算する概念図である。
【図１３】累積加算後の類似度画像を示す図である。
【図１４】図１３に示した類似度画像の最大値の位置を示す図である。
【図１５】対応点に基づいて再構成した入力画像の歪み（変形）の一例を示す図である。
【図１６】図１に示した対応点探索装置の処理手順を示すフローチャートである。
【図１７】累積加算処理手順の一例を示すフローチャートである。
【図１８】最大値フィルターを用いて累積加算処理をおこなう場合の処理手順の一例を示すフローチャートである。
【図１９】最大値フィルターの処理手順の一例を示すフローチャートである。
【符号の説明】
１    対応点探索装置
１０    画像入力部
１１    分割処理部
１２    参照部分画像一時記憶部
１３    類似度画像作成部
１４    累積加算処理部
１５    類似度画像更新部
１６    対応点決定部
２１    参照画像
２２    入力画像
５１    入力部分画像
５２    参照部分画像
５３    類似度画像
【図１】
2004287522.tif 000004
【図２】
2004287522.tif 000005
【図３】
2004287522.tif 000006
【図４】
2004287522.tif 000007
【図５】
2004287522.tif 000008
【図６】
2004287522.tif 000009
【図７】
2004287522.tif 000010
【図８】
2004287522.tif 000011
【図９】
2004287522.tif 000012
【図１０】
2004287522.tif 000013
【図１１】
2004287522.tif 000014
【図１２】
2004287522.tif 000015
【図１３】
2004287522.tif 000016
【図１４】
2004287522.tif 000017
【図１５】
2004287522.tif 000018
【図１６】
2004287522.tif 000019
【図１７】
2004287522.tif 000020
【図１８】
2004287522.tif 000021
【図１９】
2004287522.tif 000022