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