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