(57)【特許請求の範囲】
【請求項１】
入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索装置であって、
前記参照画像を複数のブロックに分割して参照部分画像を生成する参照部分画像生成手段と、
互いにその一部が重なり合う複数のブロックに前記入力画像を分割して複数の入力部分画像を生成する入力部分画像生成手段と、
前記入力部分画像と前記参照部分画像の間の類似度を算定する類似度算定手段と、
前記類似度算定手段により算定された類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成手段と、
所定の方向に並んだ複数の類似度画像の各画素の周辺画素の各画素値のうちの最大の画素値を他の類似度画像の画素値に順次累積加算する累積加算手段と、
前記累積加算手段により累積加算された各類似度画像の画素値が最大となる画素の画素位置を対応点として特定する対応点特定手段と
を備えたことを特徴とする画像の対応点探索装置。
【請求項２】
前記類似度算定手段は、前記入力部分画像と参照部分画像の正規化相関係数或いはユークリッド距離を類似度とすることを特徴とする請求項１に記載の画像の対応点探索装置。
【請求項３】
前記累積加算手段は、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）に再帰的に累積加算を繰り返すことを特徴とする請求項１又は２に記載の画像の対応点探索装置。
【請求項４】
前記累積加算手段は、各類似度画像の最大値の位置の変動幅が所定値未満となるまで、前記横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）の累積加算を繰り返すことを特徴とする請求項１、２または３に記載の画像の対応点探索装置。
【請求項５】
入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索方法であって、
前記参照画像を複数のブロックに分割して参照部分画像を生成する参照部分画像生成工程と、
互いにその一部が重なり合う複数のブロックに前記入力画像を分割して複数の入力部分画像を生成する入力部分画像生成工程と、
前記入力部分画像と前記参照部分画像の間の類似度を算定する類似度算定工程と、
前記類似度算定工程により算定された類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成工程と、
所定の方向に並んだ複数の類似度画像の各画素の周辺画素の各画素値のうちの最大の画素値を他の類似度画像の画素値に順次累積加算する累積加算工程と、
前記累積加算工程により累積加算された各類似度画像の画素値が最大となる画素の画素位置を対応点として特定する対応点特定工程と
を含んだことを特徴とする画像の対応点探索方法。
【請求項６】
前記類似度算定工程は、前記入力部分画像と参照部分画像の正規化相関係数或いはユークリッド距離を類似度とすることを特徴とする請求項５に記載の画像の対応点探索方法。
【請求項７】
前記累積加算工程は、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）に再帰的に累積加算を繰り返すことを特徴とする請求項５又は６に記載の画像の対応点探索方法。
【請求項８】
前記累積加算工程は、各類似度画像の最大値の位置の変動幅が所定値未満となるまで、前記横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）の累積加算を繰り返すことを特徴とする請求項５、６または７に記載の画像の対応点探索方法。
【請求項９】
前記請求項５〜８に記載された方法をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索装置、対応点探索方法およびその方法をコンピュータに実行させるプログラムに関し、特に、画像間の対応付けをおこなう際に、局所解に陥ることなく安定した対応付け結果を高速に得ることができる画像の対応点探索装置、対応点探索方法およびその方法をコンピュータに実行させるプログラムに関する。
【０００２】
【従来の技術】
従来、スキャナなどの画像入力装置から入力された入力画像をあらかじめ登録した参照画像とを照合する際に、両画像の対応点を探索して画像間の対応付けをおこなう技術が知られている。
【０００３】
たとえば、「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）を用いて効率的に最適解を探索する２次元ＤＰワープ法を採用した技術が開示されている。この従来技術２によれば、最適化問題を効率的に計算することができる。
【０００５】
【発明が解決しようとする課題】
しかしながら、上記従来技術１のものは、局所的な情報のみを使った繰り返し計算によってエネルギーを最小化して対応点を計算するため、初期値の影響が大きくなるという問題や、局所解（ローカルミニマム）に陥り易いことから最適な対応付け結果を得られ難いという問題がある。
【０００６】
また、従来技術２のものは、ＤＰによって効率よく最適解を探索できるものの、その計算量が膨大なものになるという問題がある。具体的には、最適解を得るためには画像サイズの指数オーダーの計算時間が必要となる。
【０００７】
これらのことから、画像間の対応付けをおこなう際に、局所解に陥ることなく安定した対応付け結果を高速に得ることができる画像の対応点探索装置をいかに実現するかが重要な課題となっている。
【０００８】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、画像間の対応付けをおこなう際に、局所解に陥ることなく安定した対応付け結果を高速に得ることができる画像の対応点探索装置、対応点探索方法およびその方法をコンピュータに実行させるプログラムを提供することを目的とする。
【０００９】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、本発明は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索装置であって、前記参照画像を複数のブロックに分割して参照部分画像を生成する参照部分画像生成手段と、互いにその一部が重なり合う複数のブロックに前記入力画像を分割して複数の入力部分画像を生成する入力部分画像生成手段と、前記入力部分画像と前記参照部分画像の間の類似度を算定する類似度算定手段と、前記類似度算定手段により算定された類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成手段と、所定の方向に並んだ複数の類似度画像の各画素の周辺画素の各画素値のうちの最大の画素値を他の類似度画像の画素値に順次累積加算する累積加算手段と、前記累積加算手段により累積加算された各類似度画像の画素値が最大となる画素の画素位置を対応点として特定する対応点特定手段とを備えたことを特徴とする。
【００１２】
また、本発明は、上記発明において、前記類似度算定手段は、前記入力部分画像と参照部分画像の正規化相関係数或いはユークリッド距離を類似度とすることを特徴とする。
【００１４】
また、本発明は、上記発明において、前記累積加算手段は、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）に再帰的に累積加算を繰り返すことを特徴とする。
【００１５】
また、本発明は、上記発明において、前記累積加算手段は、各類似度画像の最大値の位置の変動幅が所定値未満となるまで、前記横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）の累積加算を繰り返すことを特徴とする。
【００１８】
また、本発明は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索方法であって、前記参照画像を複数のブロックに分割して参照部分画像を生成する参照部分画像生成工程と、互いにその一部が重なり合う複数のブロックに前記入力画像を分割して複数の入力部分画像を生成する入力部分画像生成工程と、前記入力部分画像と前記参照部分画像の間の類似度を算定する類似度算定工程と、前記類似度算定工程により算定された類似度を画素値として持つ複数の類似度画像を生成する類似度画像生成工程と、所定の方向に並んだ複数の類似度画像の各画素の周辺画素の各画素値のうちの最大の画素値を他の類似度画像の画素値に順次累積加算する累積加算工程と、前記累積加算工程により累積加算された各類似度画像の画素値が最大となる画素の画素位置を対応点として特定する対応点特定工程とを含んだことを特徴とする。
【００２１】
また、本発明は、上記発明において、前記類似度算定工程は、前記入力部分画像と参照部分画像の正規化相関係数或いはユークリッド距離を類似度とすることを特徴とする。
【００２３】
また、本発明は、上記発明において、前記累積加算工程は、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）に再帰的に累積加算を繰り返すことを特徴とする。
【００２４】
また、本発明は、上記発明において、前記累積加算工程は、各類似度画像の最大値の位置の変動幅が所定値未満となるまで、前記横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）の累積加算を繰り返すことを特徴とする。
【００２７】
また、本発明は、請求項５〜８のいずれか一つに記載された方法をコンピュータに実行させるプログラムであることを特徴とする。
【００２８】
【発明の実施の形態】
以下に添付図面を参照して、この発明に係る画像の対応点探索装置、対応点探索方法およびその方法をコンピュータに実行させるプログラムの実施の形態を詳細に説明する。
【００２９】
図１は、本実施の形態で用いる対応点探索装置の構成を示す機能ブロック図である。同図に示す対応点探索装置１は、（１）入力画像を分割した入力部分画像と参照画像を分割した参照部分画像との間の類似度を示す類似度画像を作成する類似度画像作成段階と、（２）複数の類似度画像を累積加算した結果に基づいて最適な対応点を決定する対応点決定段階とからなる。
【００３０】
具体的には、（１）類似度画像作成段階では、たとえば７×７画素のサイズからなる参照部分画像を２１×２１画素のサイズからなる入力部分画像内を移動させつつ順次相関値を求め、この相関値を画素値として持つ類似度画像を作成する。このため、この類似度画像は、参照部分画像上の中心点が入力部分画像上の点にどの程度類似しているかを示すことになる。
【００３１】
次に、（２）対応点決定段階では、各類似度画像の画素値を垂直方向および水平方向に再帰的に累積加算を繰り返しながら各類似度画像を更新し、各類似度画像を形成する画素のうち最大の画素値を持つ画素の位置を求め、この位置を入力部分画像上での対応点として決定する。
【００３２】
このように、この対応点探索装置１によれば、従来よりも大局的な最適化をおこなっているためローカルミニマムに陥り難くなり、また累積加算を繰り返す最適化の微調整により対応付けの精度が高くなり、さらに並列分散処理が可能になるのでハードウエア化が容易となる。
【００３３】
次に、図１に示した対応点探索装置１の構成について説明する。なお、ここでは参照画像、入力画像の順に画像を入力する場合を示すこととする。図１に示すように、この対応点探索装置１は、画像入力部１０と、分割処理部１１と、参照部分画像一時記憶部１２と、類似度画像作成部１３と、累積加算処理部１４と、対応点決定部１５とからなる。
【００３４】
画像入力部１０は、縦横のサイズＩ，Ｊからなる参照画像Ｉ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-1（ｕ，ｖ）に最大値フィルターをかけた最大値フィルター画像Ｃ’mn-1（ｕ，ｖ）を作成しておき、α倍してからＣmn（ｕ，ｖ）と加算することもできる。
【００６５】
そこで、かかる最大値フィルターを用いる場合の処理手順を図１７および図１８を用いて説明する。図１７は、図１に示した累積加算処理部１４による最大値フィルターを用いたｊ方向の累積加算処理手順を示すフローチャートであり、図１８は、最大値フィルターの処理手順を示すフローチャートである。
【００６６】
図１７に示すように、変数ｍを０に初期化し（ステップＳ３０１）、変数ｎを１に初期化した後（ステップＳ３０２）、最大値フィルターＣ’mn-1（ｕ，ｖ）を算定する（ステップＳ３０３）。
【００６７】
具体的には、図１８に示すように、変数ｕ，ｖを０に初期化した後に（ステップＳ４０１〜Ｓ４０２）、Ｃ’mn（ｐ，ｑ）＝Ｍａｘ［Ｃmn（ｐ，ｑ）］を計算する（ステップＳ４０３）。ただし、ｕ−１≦ｐ≦ｕ＋１、ｖ−１≦ｑ≦ｖ＋１とする。そして、ｖをインクリメントして（ステップＳ４０４）、この変数ｖがＶよりも小さい場合には（ステップＳ４０５肯定）、ステップＳ４０３に移行して同様に計算をおこなう。また、変数ｖがＶ以上である場合には（ステップＳ４０５否定）、変数ｕをインクリメントして（ステップＳ４０６）、この変数ｕがＵよりも小さい場合には（ステップＳ４０６肯定）、ステップＳ４０２に移行して同様の処理を繰り返し、結果的に最大値を求める。
【００６８】
このようにして最大値フィルターを算定したならば、変数ｕおよびｖを０に初期化した後（ステップＳ３０４〜Ｓ３０５）、
Ｃmn（ｕ，ｖ）＝Ｃmn（ｕ，ｖ）＋α・Ｍａｘ（Ｃ’mn-1（ｐ，ｑ））
の算定式による計算をおこなう（ステップＳ３０６）。
【００６９】
その後、変数ｖをインクリメントし（ステップＳ３０７）、この変数ｖがＶよりも小さければ（ステップＳ３０８肯定）、ステップＳ３０６に移行して加算処理を繰り返す。つまり、探索範囲をｊ方向にずらすのである。
【００７０】
これに対して、変数ｖがＶ以上であれば（ステップＳ３０８否定）、変数ｕをインクリメントし（ステップＳ３０９）、この変数ｕがＵよりも小さければ（ステップＳ３１０肯定）、ステップＳ３０５に移行して加算処理を繰り返す。つまり、探索範囲をｉ方向にずらすことになる。
【００７１】
そして、変数ｕがＵ以上であれば（ステップＳ３１０否定）、ある画素についての計算を終了し、次の画素に移行する。具体的には、変数ｎをインクリメントして注目画素をｊ方向に移行させた後に（ステップＳ３１１）、この変数ｎをＮと比較し（ステップＳ３１２）、この変数ｎがＮよりも小さければ（ステップＳ３１２肯定）、ステップＳ３０３に移行して加算処理を繰り返す。
【００７２】
これに対して、変数ｎがＮ以上であれば（ステップＳ３１２否定）、変数ｍをインクリメントして注目画素をｉ方向に移行させた後に（ステップＳ３１３）、この変数ｍがＭよりも小さければ（ステップＳ３１４肯定）、ステップＳ３０２に移行して加算処理を繰り返し、変数ｍがＭ以上であれば（ステップＳ３１４否定）、処理を終了する。
【００７３】
次に、対応点探索後の処理について説明する。図１に示した対応点探索装置１により対応点を見つけ出したならば、この対応点から入力画像が参照画像に比べてどのように歪んでいるかが分かる。
【００７４】
具体的には、図１９に示すように、「５２３」の数字列を情報として持つ画像を入力画像とし、「２」の数字を情報として持つ画像を参照画像とした場合には、図中に示すような歪みが生じていることが分かる。また、「３」の数字を情報として持つ画像を参照画像とした場合にも、同様に図中に示す歪みが生じていることが分かる。
【００７５】
このように、かかる対応点に基づく歪みを用いることにより、連続して書かれた文字列の中から各文字を分離して、正確な文字認識をおこなうことが可能となる。
【００７６】
この点についてさらに説明すると、たとえば参照画像として「０」の数字を持つ画像を選んだ場合には、入力画像の数字５と数字２の間の閉曲線部分が数字「０」とされ、対応点すなわち歪みが判明する。この場合の歪みは、「２」の数字を持つ画像を参照画像とした場合よりも歪み度が大きくなるので、かかる入力画像に数字「０」が存在しないものと判定することができる。
【００７７】
また、図２０に示すように、「鳥」の漢字を情報として持つ画像を参照画像および入力画像とする場合には、入力画像に同図に示すような歪みが生ずる。このため、かかる歪みすなわち変形を戻して類似度を計算することにより、正確な類似度合いを把握し、もって照合精度を高めることができる。
【００７８】
また、図２１に示すように、本発明はサイン照合に適用することもできる。英文によるサインをサイン認証することは極めて難しい問題であるが、本発明の対応点に基づく歪み度合いを求めれば、登録サインと照合対象となるサインの照合を精度良くおこなうことができる。なお、説明の便宜上図示省略するが、オプティカルフローの検出、ステレオ画像による３次元計測、外観検査装置などに適用することもできる。
【００７９】
上述してきたように、本実施の形態によれば、画像入力部１０から参照画像と入力画像をそれぞれ入力し、分割処理部１１で参照部分画像および入力部分画像をそれぞれ作成、類似度画像作成部１３で参照部分画像と入力部分画像の類似度を求めた類似度画像をそれぞれ作成し、累積加算処理部１４で複数の類似度画像の累積加算処理を再帰的におこない、その結果に基づいて対応点決定部１５が対応点を決定するよう構成したので、（１）大局的な最適化をおこなっているのでローカルミニマムに陥るケースを低減することができ、（２）繰り返し処理によって最適化の微調整をおこなうことができ、（３）並列分散処理ができるため高速に処理することができる。
【００８０】
なお、本実施の形態では、説明の便宜上、参照画像と入力画像のサイズが同じ場合を示したが、本発明はこれに限定されるものではなく、参照画像と入力画像のサイズを異なる場合に適用することもできる。かかる場合にも同様の処理をおこなうことができる。
【００８１】
また、本実施の形態では、各類似度画像をｊ方向、−ｊ方向、ｉ方向、−ｉ方向の順序で再帰的に累積加算する場合を示したが、本発明は必ずしもこれに限定されるものではなく、斜め方向或いは一方向のみについて累積加算する場合に適用することもできる。一方向のみであっても、類似度が加算されることにより一定の大局情報が得られる。
【００８２】
また、本実施の形態では、類似度として正規化相関係数を用いた場合を示したが、本発明はこれに限定されるものではなく、ユークリッド距離などの他の指標を類似度として用いることもできる。
【００８３】
【発明の効果】
以上説明したように、本発明によれば、参照画像を複数のブロックに分割して参照部分画像を生成し、互いにその一部が重なり合う複数のブロックに入力画像を分割して複数の入力部分画像を生成し、入力部分画像と参照部分画像の間の類似度を算定し、算定した類似度を画素値として持つ複数の類似度画像を生成し、所定の方向に並んだ複数の類似度画像の各画素の周辺画素の各画素値のうちの最大の画素値を他の類似度画像の画素値に順次累積加算し、累積加算した各類似度画像の画素値が最大となる画素の画素位置を対応点として特定するよう構成したので、画像間の対応付けをおこなう際に、局所解に陥ることなく安定した対応付け結果を高速に得ることができる。特に、ブロックごとの繰り返し処理によって高速な処理をおこなうことができ、また、入力画像の歪み（変形）を考慮した処理をおこなうことができる。また、大局的な情報を用いることができるため、ローカルミニマムに陥るケースを低減することができる。さらに、無駄な累積加算を省いて効率良く変形を吸収することができる。
【００８６】
また、本発明によれば、入力部分画像と参照部分画像の正規化相関係数或いはユークリッド距離を類似度とするよう構成したので、画像のコントラストの変動に頑健な類似度画像を得ることができる。
【００８８】
また、本発明によれば、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）に再帰的に累積加算を繰り返すよう構成したので、より大局的な情報を用いた処理をおこなうことができる。
【００８９】
また、本発明によれば、各類似度画像の最大値の位置の変動幅が所定値未満となるまで、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）の累積加算を繰り返すよう構成したので、繰り返し処理によって最適化の微調整をおこなうことができる。
【０１０１】
また、本発明によれば、請求項５〜８のいずれか一つに記載された方法をコンピュータに実行させることが可能なプログラムが得られるという効果を奏する。
【図面の簡単な説明】
【図１】この発明の実施の形態に係る対応点探索装置の構成を示す機能ブロック図である。
【図２】本実施の形態で用いる参照画像および入力画像の一例を示す図である。
【図３】参照部分画像の一例を示す図である。
【図４】入力部分画像の一例を示す図である。
【図５】類似度画像の作成概念を説明するための説明図である。
【図６】図４に示した各入力部分画像に対応する類似度画像を示す図である。
【図７】累積加算手順を説明するための説明図である。
【図８】ｊ方向の累積加算処理を説明するための説明図である。
【図９】−ｊ方向の累積加算処理を説明するための説明図である。
【図１０】ｉ方向の累積加算処理を説明するための説明図である。
【図１１】−ｉ方向の累積加算処理を説明するための説明図である。
【図１２】累積加算後の類似度画像を示す図である。
【図１３】図１２に示した類似度画像の最大値の位置を示す図である。
【図１４】対応点に基づいて再構成した入力画像の歪み（変形）の一例を示す図である。
【図１５】図１に示した対応点探索装置の処理手順を示すフローチャートである。
【図１６】累積加算処理手順の一例を示すフローチャートである。
【図１７】最大値フィルターを用いて累積加算処理をおこなう場合の処理手順の一例を示すフローチャートである。
【図１８】最大値フィルターの処理手順の一例を示すフローチャートである。
【図１９】複数文字からなる入力画像から文字を切り出す場合を説明するための説明図である。
【図２０】本発明を漢字の文字認識に適用した一例を示す図である。
【図２１】本発明をサイン照合に適用した一例を示す図である。
【符号の説明】
１    対応点探索装置
１０    画像入力部
１１    分割処理部
１２    参照部分画像一時記憶部
１３    類似度画像作成部
１４    累積加算処理部
１５    対応点決定部
２１    参照画像
２２    入力画像
５１    入力部分画像
５２    参照部分画像
５３    類似度画像
【図１】
0004160762.tif 000002
【図２】
0004160762.tif 000003
【図３】
0004160762.tif 000004
【図４】
0004160762.tif 000005
【図５】
0004160762.tif 000006
【図６】
0004160762.tif 000007
【図７】
0004160762.tif 000008
【図８】
0004160762.tif 000009
【図９】
0004160762.tif 000010
【図１０】
0004160762.tif 000011
【図１１】
0004160762.tif 000012
【図１２】
0004160762.tif 000013
【図１３】
0004160762.tif 000014
【図１４】
0004160762.tif 000015
【図１５】
0004160762.tif 000016
【図１６】
0004160762.tif 000017
【図１７】
0004160762.tif 000018
【図１８】
0004160762.tif 000019
【図１９】
0004160762.tif 000020
【図２０】
0004160762.tif 000021
【図２１】
0004160762.tif 000022