(57)【要約】【課題】画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得すること。【解決手段】類似度画像圧縮処理部１４で類似度画像に対して最大値圧縮を段階的に繰り返しおこない、累積加算処理部１７、類似度画像更新部１８および対応点決定部１９で最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定し、シフト補正部１６で各類似度画像内で対応点が存在するとして特定された領域が画像中心になるようにシフト補正し、累積加算処理部１７、類似度画像更新部１８および対応点探索処理部１９で各類似度画像内の領域に限定して対応点探索処理をおこなった後に、シフトの累積量に応じて各類似度画像内の対応点を決定する。【選択図】        図１
2005165928.tif 000002
【特許請求の範囲】
【請求項１】
入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索方法であって、
前記類似度画像に対して最大値圧縮をおこなった後に、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定工程と、
前記領域特定工程によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなって、各類似度画像内の対応点を決定する対応点決定工程と
を含んだことを特徴とする画像の対応点探索方法。
【請求項２】
入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索方法であって、
前記類似度画像に対して最大値圧縮を段階的に繰り返しおこなう類似度画像圧縮処理工程と、
前記類似度画像圧縮処理工程によって最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定工程と、
前記領域特定工程によって各類似度画像内で対応点が存在するとして特定された領域が画像中心になるようにシフトするシフト工程と、
前記領域特定工程によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなった後に、前記シフト工程による前記シフトの累積量に応じて各類似度画像内の対応点を決定する対応点決定工程と
を含んだことを特徴とする画像の対応点探索方法。
【請求項３】
入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索装置であって、
前記類似度画像に対して最大値圧縮をおこなった後に、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定手段と、
前記領域特定手段によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなって、各類似度画像内の対応点を決定する対応点決定手段と
を備えたことを特徴とする画像の対応点探索装置。
【請求項４】
入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索装置であって、
前記類似度画像に対して最大値圧縮を段階的に繰り返しおこなう類似度画像圧縮処理手段と、
前記類似度画像圧縮処理手段によって最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定手段と、
前記領域特定手段によって各類似度画像内で対応点が存在するとして特定された領域が画像中心になるようにシフトするシフト手段と、
前記領域特定手段によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなった後に、前記シフト手段による前記シフトの累積量に応じて各類似度画像内の対応点を決定する対応点決定手段と
を備えたことを特徴とする画像の対応点探索装置。
【請求項５】
入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索プログラムであって、
前記類似度画像に対して最大値圧縮をおこなった後に、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定手順と、
前記領域特定手順によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなって、各類似度画像内の対応点を決定する対応点決定手順と
をコンピュータに実行させることを特徴とする画像の対応点探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索方法、対応点探索装置および対応点探索プログラムに関し、特に、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる画像の対応点探索方法、対応点探索装置および対応点探索プログラムに関する。
【背景技術】
【０００２】
従来より、スキャナなどの画像入力装置から入力された入力画像をあらかじめ登録した参照画像とを照合する際に、両画像の対応点を探索して画像間の対応付けをおこなう技術が知られている。
【０００３】
たとえば、非特許文献１（従来技術１）には、設定したエネルギー関数を変分法の枠組みにより最小化する標準正則化理論を適用した技術が開示されている。この従来技術１が採用する標準正則化理論は、局所的な情報のみを使った繰り返し計算によりエネルギーを最小化することによって対応点を計算するものであるので、並列分散処理をおこなうことができ、人間の脳情報処理に近い処理を実現できる可能性がある。
【０００４】
また、非特許文献２（従来技術２）には、ＤＰ（Dynamic Programming）を用いて効率的に最適解を探索する２次元ＤＰワープ法を採用した技術が開示されている。この従来技術２によれば、最適化問題を効率的に計算することができる。
【０００５】
ところが、上記従来技術１のものは、局所的な情報のみを使った繰り返し計算によってエネルギーを最小化して対応点を計算するため、初期値の影響が大きくなるという問題や、局所解（ローカルミニマム）に陥り易いことから最適な対応付け結果を得られ難いという問題がある。また、従来技術２のものは、ＤＰによって効率よく最適解を探索できるものの、その計算量が膨大なものになるという問題がある。具体的には、最適解を得るためには画像サイズの指数オーダーの計算時間が必要となる。
【０００６】
これらのことから、本願特許出願人は、特許文献１（従来技術３）において、画像間の対応付けをおこなう際に、局所解に陥ることなく安定した対応付け結果を得ることができる画像の対応点探索装置、対応点探索方法およびその方法をコンピュータに実行させるプログラムを提案した。
【０００７】
具体的には、各類似度画像の画素値を垂直方向および水平方向別に累積加算を繰り返した後に、これらの累積加算結果から得られる各画素の周辺画素の最大値を類似度画像の各画素の画素値に累積加算して類似度画像を更新し、更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまでこれらの処理を繰り返して、入力部分画像上での対応点を求めるものである。
【０００８】
【非特許文献１】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
【特許文献１】特願２００２−０５６６６１号
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、この従来技術３では、各類似度画像の全画素を探索範囲として累積加算処理および更新処理を繰り返して対応点を求めるものであるため、処理を迅速化する上での制約があった。
【００１０】
また、同じパターンが周期的に現れる画像間の対応付けをおこなう場合、精度の良い対応付け結果を取得することが困難であるという問題点があった。具体的には、参照画像および入力画像に同じパターンが周期的に存在することに起因して同一の類似度画像内に画素値の近い画素が複数存在するようになる。このため、類似度画像の最大値の位置が曖昧になり、精度の良い対応付け結果を取得することができない。
【００１１】
そこで、この発明は、上述した従来技術による問題点を解消するためになされたものであり、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる画像の対応点探索方法、対応点探索装置および対応点探索プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、請求項１の発明に係る画像の対応点探索方法は、入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索方法であって、前記類似度画像に対して最大値圧縮をおこなった後に、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定工程と、前記領域特定工程によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなって、各類似度画像内の対応点を決定する対応点決定工程とを含んだことを特徴とする。
【００１３】
また、請求項２の発明に係る画像の対応点探索方法は、入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索方法であって、前記類似度画像に対して最大値圧縮を段階的に繰り返しおこなう類似度画像圧縮処理工程と、前記類似度画像圧縮処理工程によって最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定工程と、前記領域特定工程によって各類似度画像内で対応点が存在するとして特定された領域が画像中心になるようにシフトするシフト工程と、前記領域特定工程によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなった後に、前記シフト工程による前記シフトの累積量に応じて各類似度画像内の対応点を決定する対応点決定工程とを含んだことを特徴とする。
【００１４】
また、請求項３の発明に係る対応点探索装置は、入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索装置であって、前記類似度画像に対して最大値圧縮をおこなった後に、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定手段と、前記領域特定手段によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなって、各類似度画像内の対応点を決定する対応点決定手段とを備えたことを特徴とする。
【００１５】
また、請求項４の発明に係る対応点探索装置は、入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索装置であって、前記類似度画像に対して最大値圧縮を段階的に繰り返しおこなう類似度画像圧縮処理手段と、前記類似度画像圧縮処理手段によって最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定手段と、前記領域特定手段によって各類似度画像内で対応点が存在するとして特定された領域が画像中心になるようにシフトするシフト手段と、前記領域特定手段によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなった後に、前記シフト手段による前記シフトの累積量に応じて各類似度画像内の対応点を決定する対応点決定手段とを備えたことを特徴とする。
【００１６】
また、請求項５の発明に係る対応点探索プログラムは、入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索プログラムであって、前記類似度画像に対して最大値圧縮をおこなった後に、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定する領域特定手順と、前記領域特定手順によって特定された各類似度画像内の領域に限定して対応点探索処理をおこなって、各類似度画像内の対応点を決定する対応点決定手順とをコンピュータに実行させることを特徴とする。
【発明の効果】
【００１７】
本発明に係る対応点探索方法によれば、類似度画像に対して最大値圧縮をおこなった後に、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定し、各類似度画像内の領域に限定して対応点探索処理をおこなって、各類似度画像内の対応点を決定するように構成したので、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる。さらに、これに関連して、最大値圧縮した類似度画像に対して「対応点探索処理」をおこなうことにより、隣接するブロック（類似度画像）間の変形許容度が大きくなり、画像の大きな変形に追従できるようになる。このため、元の類似度画像に対して「対応点探索処理」をおこなう際に変形許容度を限定する（累積加算処理部１７におけるαの値を１に近づける）ことが可能になり、同じパターンが周期的に現れる画像間の対応付けをおこなう場合でも、精度の良い対応付け結果を取得することができる。
【００１８】
また、本発明によれば、類似度画像に対して最大値圧縮を段階的に繰り返しおこない、最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定し、各類似度画像内で対応点が存在するとして特定された領域が画像中心になるようにシフトし、各類似度画像内の領域に限定して対応点探索処理をおこなった後に、シフトの累積量に応じて各類似度画像内の対応点を決定するよう構成したので、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる。
【発明を実施するための最良の形態】
【００１９】
以下に添付図面を参照して、この発明に係る画像の対応点探索方法、対応点探索装置および対応点探索プログラムの好適な実施例を詳細に説明する。
【実施例１】
【００２０】
図１は、本実施例で用いる対応点探索装置の構成を示す機能ブロック図である。同図に示す対応点探索装置１は、概略的には、（１）入力画像を分割した入力部分画像と参照画像を分割した参照部分画像との間の類似度を示す類似度画像を作成する類似度画像作成段階と、（２）類似度画像に対して最大値圧縮をおこなった後に、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域（対応点候補位置）を特定する「対応点候補位置特定段階」（特許請求の範囲に記載の「領域特定手段」に相当する。）と、（３）対応点候補位置特定段階で特定された各類似度画像内の領域に限定して対応点探索処理をおこなって、各類似度画像内の対応点を決定する「対応点決定段階」の３つの段階の処理をおこなう。
【００２１】
具体的には、（１）類似度画像作成段階では、たとえば１６×１６画素のサイズからなる参照部分画像を４８×４８画素のサイズからなる入力部分画像内を移動させつつ順次相関値を求め、この相関値を画素値として持つ類似度画像を作成する（図５参照）。このため、この類似度画像は、参照部分画像上の中心点が入力部分画像上の点にどの程度類似しているかを示すことになる。
【００２２】
次に、（２）対応点候補位置特定段階では、類似度画像に対して１／４最大値圧縮をおこない、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、類似度画像の解像度が１／４の場合（粗探索時）での対応点を求める（図８参照）。この粗探索時での「対応点」（すなわち、「対応点候補位置」）は、元の類似度画像の対応点が存在し得る領域を示唆するものである。さらに、類似度画像に対して１／２最大値圧縮をおこなった場合についても同様に「対応点候補位置」を求め（図９参照）、各類似度画像内で対応点が存在する領域を段階的に絞り込んでいく（図６参照）。
【００２３】
そして、（３）対応点決定段階では、対応点探索処理の探索範囲を各類似度画像内で対応点が存在する領域に限定し、該限定された探索範囲（各類似度画像内で対応点が存在する領域）の画素値を累積加算した結果に基づいて最適な対応点を決定する（図６および図１０参照）。
【００２４】
次に、図１に示した対応点探索装置１の構成について説明する。なお、ここでは参照画像、入力画像の順に画像を入力する場合を示すこととする。図１に示すように、この対応点探索装置１は、画像入力部１０と、分割処理部１１と、参照部分画像一時記憶部１２と、類似度画像作成部１３と、類似度画像圧縮処理部１４と、シフト量算出部１５と、シフト補正部１６と、累積加算処理部１７と、類似度画像更新部１８と、対応点決定部１９と、からなる。
【００２５】
画像入力部１０は、縦横のサイズＩ、Ｊからなる参照画像Ｉ0（ｉ，ｊ）および入力画像Ｉ1（ｉ，ｊ）（０≦ｉ≦Ｉ−１，０≦ｊ≦Ｊ−１）を入力する入力部である。具体的には、光学的に原稿を読み取って画像を取得するスキャナや、ネットワークから画像を取得するインターフェース部や、二次記憶装置から画像を読み出す読み出し部が該当する。ここで、この入力画像とは、対応点の探索対象となる画像であって、歪みや変形を伴うものであっても良い。これに対して、参照画像とは、入力画像の比較の対象となる画像であり、歪みなどを伴わないものであることが望ましい。
【００２６】
図２−１には参照画像２１を示しており、図２−２には入力画像２２を示している。これらの参照画像２１および入力画像２２は、いずれも同じパターン（斜線）が繰り返し周期的に現れる画像であり、４８×６４画素からなる。
【００２７】
分割処理部１１は、画像入力部１０により入力された入力画像および参照画像を入力部分画像および参照部分画像にそれぞれ分割する処理部である。ただし、入力画像の分割手順と参照画像の分割手順はそれぞれ異なる。
【００２８】
参照画像を分割する場合には、参照画像上で縦方向にＭ個、横方向にＮ個サンプリングした点（ｐm，ｑn）（０≦ｍ≦Ｍ−１，０≦ｎ≦Ｎ−１）を中心とした参照部分画像を作成する。図３は、図２−１に示した参照画像２１の分割結果の一例を示す図であり、同図に示すように、ここでは４８×６４画素の参照画像２１を１６×１６画素からなる１２個の参照部分画像に分割している。具体的には、ｐm＝round（Ｉ／Ｍ）、ｑn＝round（Ｊ／Ｎ）としている。ただし、round（）は四捨五入を示している。
【００２９】
入力画像を分割する場合には、参照画像を分割する場合と異なり、各入力部分画像の一部が重なり合う重複したデータを持つように分割する。図４は、図２−２に示した入力画像２２の分割結果の一例を示す図であり、同図に示すように、ここでは４８×６４画素の入力画像２２を４８×４８画素からなる１２個の入力部分画像に分割している。
【００３０】
参照部分画像一時記憶部１２は、分割処理部１１で分割した各参照部分画像を一時記憶する記憶部であり、類似度画像作成部１３が類似度画像を作成する際に該当する参照部分画像が取り出される。
【００３１】
類似度画像作成部１３は、入力部分画像と参照部分画像の間の変形を考慮した類似度を算定して、該類似度を画素値として持つ類似度画像Ｃ（m , n , u , v）（０≦ｍ≦Ｍ−１，０≦ｎ≦Ｎ−１，０≦ｕ≦Ｕ−１，０≦ｖ≦Ｖ−１）を作成する処理部である。ただし、Ｕ，Ｖはそれぞれ類似度画像の縦横のサイズであるものとする。この類似度として正規化相関係数を用いることができる。
【００３２】
図５は、参照部分画像と入力部分画像から類似度画像を作成する概念を説明するための説明図である。なお、ここでは図３および図４の２行２列に位置する入力部分画像と参照部分画像を用いることとする。
【００３３】
同図に示すように、入力部分画像５１と参照部分画像５２の類似度を求める場合には、参照部分画像５２の中心画素を入力部分画像５１の左上部の画素に対応づけて正規化相関係数を計算し、その計算結果を類似度画像５３の左上部の画素の画素値とする。その後、参照部分画像５２を右にずらし、同様の処理をおこなう。上記処理を参照部分画像５２をずらしながら入力部分画像５１の全画素についておこなうことにより、類似度画像５３が求められる。
【００３４】
かかる類似度画像の作成処理を各入力部分画像ごとにおこなうと、図６に示す（１）のような複数の類似度画像が得られる。なお、参照部分画像の全ての画素の画素値が一定値である場合には、正規化相関係数の分母がゼロとなるため、この場合の類似度画像の画素値もゼロとなる。
【００３５】
類似度画像圧縮処理部１４は、類似度画像作成部１３によって作成された類似度画像に対して最大値圧縮をおこなう処理部である。具体的には、類似度画像作成部１３によって作成された類似度画像（図６に示す（１））に対して１／４最大値圧縮または１／２最大値圧縮をおこなう（図６に示す（２）および図６に示す（３）参照）。このように、類似度画像に対して最大値圧縮をおこなうこととしたのは、最大値圧縮がおこなわれた類似度画像に対して、後述する「対応点探索処理」をおこなって「対応点候補位置」を求めることにより、各類似度画像内で対応点（解）が存在する領域を特定するためである。
【００３６】
また、「最大値圧縮」とは、画像を所定の圧縮率で圧縮する場合に、圧縮画像として画素値が最大のものを抽出して画像を圧縮することを言う。例えば、図７に示すように、８×８画素の画像を１／４最大値圧縮する場合、４×４マスク内の最大値を１画素として抽出する。
【００３７】
シフト量算出部１５は、「対応点候補位置特定段階」で「対応点探索処理」によって特定された「対応点候補位置」に基づいて元の類似度画像の対応点が存在する領域が画像中心となるシフト量を算出する処理部である。具体的には、１／４最大値圧縮または１／２最大値圧縮がおこなわれた類似度画像の中心点に対する「対応点候補位置」のずれから算出される。また、１／４最大値圧縮された類似度画像における対応点候補位置から求められた「シフト量」および１／２最大値圧縮された類似度画像における対応点候補位置から求められた「シフト量」を順次累積して「累積シフト量」を算出する。
【００３８】
シフト補正部１６は、シフト量算出部１５によって算出されたシフト量に応じて元の類似度画像の対応点が存在する領域が中心となるように元の類似度画像をシフト補正する処理部である。具体的には、１／４最大値圧縮された類似度画像の「対応点候補位置」が特定された後、１／２最大値圧縮における類似度画像に対して対応点探索処理をおこなう前処理としてシフト量算出部１８によって算出されたシフト量に応じて元の類似度画像をシフト補正する（図９参照）。同様にして、１／２最大値圧縮された類似度画像の対応点候補位置が特定された後（「対応点候補位置特定段階」が終了した後）、「対応点決定段階」において、元の類似度画像の対応点を決定する前処理としてシフト量算出部１５によって算出されたシフト量に応じて元の類似度画像をシフト補正する（図１０参照）。
【００３９】
ここで、本発明に密接に関連する「対応点探索処理」について説明する。この「対応点探索処理」は、概略的に、各類似度画像の画素値を垂直方向および水平方向別に独立に累積加算を繰り返した後に、これらの累積加算結果から得られる各画素の周辺画素の最大値を類似度画像の各画素の画素値に累積加算して類似度画像を更新し、更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまでこれらの処理を繰り返して、入力部分画像上での対応点を求める処理であり、機能概念的に、累積加算処理部１７、類似度画像更新部１８および対応点決定部１９によって上記の処理がおこなわれる。
【００４０】
このうち、累積加算処理部１７は、図１１に示すように、各類似度画像を横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ独立して累積加算する処理部である。具体的には、類似度画像全体Ｃ(m , n , u , v)を４枚複写して、これをそれぞれＤ１(m , n, u , v)、Ｄ２(m , n , u , v)、Ｄ３(m , n , u , v)、Ｄ４(m , n , u , v)とし、それぞれｊ方向、−ｊ方向、ｉ方向、−ｉ方向の累積加算に使用する。たとえば、Ｄ１(m , n , u , v)を用いてｊ方向に累積加算する場合には、ｎ＝１〜Ｎ−１の類似度画像について、
Ｄ１（m , n , u , v）＝Ｃ（m , n , u , v）＋α・Ｍａｘ（Ｄ１（m , n-1 ,p , q））
を順次再帰的に計算する。ただし、Ｍａｘ（）は最大値を示し、αは定数であり、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−１、ｕ−１≦ｐ≦ｕ＋１、ｖ−１≦ｑ≦ｖ＋１とする。
【００４１】
すなわち、ｊ方向に累積加算する場合には、図１２に示すように、Ｄ１(m , n-1 , u , v)を中心とする８近傍内の９画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣ(m , n , u , v)の画素値に加算する処理を再帰的に繰り返すことになる。
【００４２】
また、−ｊ方向に累積加算する場合には、ｎ＝Ｎ−２〜０の類似度画像について、
Ｄ３（m , n , u , v ）＝Ｃ（m , n , u , v）＋α・Ｍａｘ（Ｄ３（m , n+1 , p , q））
を順次再帰的に計算する。ただし、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−２とする。すなわち、−ｊ方向に累積加算する場合には、図１３に示すように、Ｄ３（m , n+1 ,u , v）を中心とする８近傍内の９画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣ(m , n , u , v)の画素値に加算する処理を再帰的に繰り返すことになる。
【００４３】
また、ｉ方向に累積加算する場合には、ｍ＝１〜Ｍ−１の類似度画像について、
Ｄ２（m , n , u , v）＝Ｃ（m , n , u , v）＋α・Ｍａｘ（Ｄ２（m-1 , n, p , q））
を順次再帰的に計算する。ただし、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、１≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−１とする。すなわち、ｉ方向に累積加算する場合には、図１４に示すように、Ｄ２（m-1 , n , u , v）を中心とする８近傍内の９画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣ(m , n , u , v)の画素値に加算する処理を再帰的に繰り返すことになる。
【００４４】
また、−ｉ方向に累積加算する場合には、ｍ＝Ｍ−２〜０の類似度画像について、
Ｄ４（m , n , u , v）＝Ｃ（m , n , u , v）＋α・Ｍａｘ（Ｄ４（m+1 , n ,p , q））
を順次再帰的に計算する。ただし、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−２、０≦ｎ≦Ｎ−１とする。すなわち、−ｉ方向に累積加算する場合には、図１５に示すように、Ｄ４（m+1 , n , u , v）を中心とする８近傍内の９画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣ(m , n , u , v)の画素値に加算する処理を再帰的に繰り返すことになる。
【００４５】
類似度画像更新部１８は、累積加算処理部１７の累積加算後の類似度画像に基づいて類似度画像を更新する処理部である。具体的には、まず各方向についての累積加算処理をおこなったならば、図１６の概念図に示すように、
Ｃ（m , n , u , v）＝Ｃ（m , n , u , v）＋α・Ｍａｘ（Ｄ１（m , n-1 ,p , q））
＋α・Ｍａｘ（Ｄ２（m-1 , n , p , q））
＋α・Ｍａｘ（Ｄ３（m , n+1 , p , q））
＋α・Ｍａｘ（Ｄ４（m+1, n , p , q））
の算定式によりＣ( m , n , u , v)を更新する。
【００４６】
その後、対応点決定部１９は、各類似度画像の最大値の位置を検出し、それらの位置と前回の各類似度画像の最大値の位置との変化が所定の範囲内でなければ累積加算処理をフィードバックして繰り返し、所定の範囲内となった時点で繰り返しを終了し、そのときの各類似度画像の最大値の位置を対応点として決定する（図６に示す（４）参照）。
【００４７】
ここで、この対応点探索装置１は、類似度画像圧縮処理部１４によって最大値圧縮された類似度画像に対して「対応点探索処理」をおこなうことによって各類似度画像内で対応点が存在する領域を示唆する「対応点候補位置」を特定する「対応点候補位置特定段階」と、「対応点候補位置特定段階」で得られた「対応点候補位置」が示唆する各類似度画像内の領域に限定して対応点探索処理をおこなって、各類似度画像内の対応点を決定する「対応点決定段階」に主たる特徴がある。
【００４８】
この主たる特徴を具体的に説明すると、類似度画像圧縮処理部１４によって１／４最大値圧縮がおこなわれた類似度画像を累積加算した結果に基づいて「対応点候補位置」を特定する（図６に示す（２）参照）。さらに、類似度画像圧縮処理部１４によって１／２最大値圧縮された類似度画像に対して「対応点探索処理」をおこなう際に、１／４最大値圧縮された類似度画像の「対応点候補位置」に基づいて対応点探索処理の探索範囲を限定し（図９参照）、該限定された探索範囲（各類似度画像内で対応点が存在する領域）の画素値を累積加算した結果に基づいて対応点候補位置を特定する（図６に示す（３）参照）。このようにして、「対応点候補位置特定段階」では、各類似度画像内で対応点が存在する領域を段階的に絞り込んでいく（図６参照）。
【００４９】
そして、「対応点決定段階」では、「対応点候補位置特定段階」で得られた「対応点候補位置」に基づいて対応点探索処理の探索範囲（各類似度画像の全画素）を各類似度画像内で対応点が存在し得る領域に限定し（図１０参照）、該限定された探索範囲（各類似度画像内で対応点が存在する領域）の画素値を累積加算した結果に基づいて最適な対応付け結果を求め、該対応付け結果にシフト量算出部１８によって算出された「累積シフト量」を反映して対応点を決定する（図６に示す（４）参照）。
【００５０】
したがって、上記した従来技術の例で言えば、各類似度画像の全画素を探索範囲として「対応点探索処理」をおこなうのではなく、類似度画像に対して最大値圧縮をおこなった後に、該最大値圧縮がおこなわれた類似度画像に対して対応点探索処理をおこなって、各類似度画像内で対応点が存在する領域を特定し、各類似度画像内の領域に限定して「対応点探索処理」をおこなって、各類似度画像内の対応点を決定するよう構成したので、画像間の対応付け結果の精度を維持しつつ、高速かつ効率良く対応付け結果を取得することができる。
【００５１】
さらに、これに関連して、最大値圧縮した類似度画像に対して「対応点探索処理」をおこなうことにより、隣接するブロック（類似度画像）間の変形許容度が大きくなり、画像の大きな変形に追従できるようになる。このため、元の類似度画像に対して「対応点探索処理」をおこなう際に変形許容度を限定する（累積加算処理部１７におけるαの値を１に近づける）ことが可能になり、同じパターンが周期的に現れる画像間の対応付けをおこなう場合でも、精度の良い対応付け結果を取得することができる。
【００５２】
次に、図１に示した対応点探索装置１の処理手順について説明する。なお、上記説明と一部重複するが、図２〜図１６を用いて処理の流れを例示しつつ処理手順について説明することとする。
【００５３】
図１７は、図１に示した対応点探索装置１の処理手順を示すフローチャートである。同図に示すように、この対応点探索装置１が参照画像と入力画像を取得したならば、この参照画像を参照部分画像に分割する（ステップＳ１０１）。たとえば、図２−１に示した４８×６４画素の参照画像２１を図３に示した１６×１６画素からなる１２個の参照部分画像に分割して記憶する。この参照部分画像は、参照したい画像ごとに予め記憶しておいてもよいし、また、参照部分画像ではなく、参照画像のみを予め別途記憶しておき、後述する入力画像と参照画像との類似度画像の計算の際に、記憶された参照画像から参照部分画像に分割してもよい。
【００５４】
その後、入力画像を入力部分画像に分割する（ステップＳ１０２）。たとえば、図２−２に示した４８×６４画素の入力画像２２を図４に示した４８×４８画素からなる１２個の入力部分画像に分割する。
【００５５】
そして、この参照部分画像と入力部分画像の間の類似度画像を作成する（ステップＳ１０３）。たとえば、図５に示すようにして入力部分画像５１と参照部分画像５２の類似度を画素値とする類似度画像５３の作成を各入力部分画像ごとにおこなって、図６に示した（１）のような複数の類似度画像を作成する。
【００５６】
続いて、類似度画像（図６に示す（１））に対して１／４最大値圧縮をおこなった後に（ステップＳ１０４）、１／４最大値圧縮された類似度画像に対して「対応点探索処理」をおこなう（ステップＳ１０５）。具体的には、類似度画像圧縮処理部１４によって１／４最大値圧縮がおこなわれた類似度画像を累積加算した結果に基づいて対応点候補位置を特定する（図６に示す（２）参照）。
【００５７】
その後、１／４最大値圧縮がおこなわれた類似度画像の中心点に対する「対応点候補位置」のずれに基づいて元の類似度画像の対応点が存在する領域が画像中心となるシフト量を算出し（ステップＳ１０６）、元の類似度画像をシフト補正する（ステップＳ１０７）。
【００５８】
そして、類似度画像（図６に示す（１））に対して１／２最大値圧縮をおこなった後に（ステップＳ１０８）、１／４最大値圧縮された類似度画像の「対応点候補位置」が示唆する各類似度画像内の領域に限定して、１／２最大値圧縮がおこなわれた類似度画像に対して「対応点探索処理」を実行する（ステップＳ１０９）。
【００５９】
続いて、１／２最大値圧縮がおこなわれた類似度画像の中心点に対する「対応点候補位置」のずれに基づいて元の類似度画像の対応点が存在する領域が画像中心となるシフト量を算出し（ステップＳ１１０）、元の類似度画像をシフト補正する（ステップＳ１１１）。
【００６０】
そして、１／２最大値圧縮された類似度画像の「対応点候補位置」が示唆する各類似度画像内の領域に限定して「対応点探索処理」を実行し（ステップＳ１１２）、該「対応点探索処理」の対応付け結果に「累積シフト量」を反映して対応点を決定する（ステップＳ１１３）。
【００６１】
次に、本発明に密接に関連する「対応点探索処理」における累積加算処理手順について詳細に説明する。図１８は、図１に示した累積加算処理部１７によるｊ方向の累積加算処理手順を示すフローチャートである。なお、−ｊ方向、ｉ方向、−ｉ方向の累積加算処理も同様におこなうことができる。
【００６２】
同図に示すように、まず変数ｍ、ｕおよびｖを０にするとともに、変数ｎを１とする初期化をおこなう（ステップＳ２０１〜Ｓ２０４）。ここで、この変数ｍはｉ方向のインデックスとして用いる変数であり、変数ｎはｊ方向のインデックスとして用いる変数である。また、変数ｕ，ｖは探索範囲を示すｉ方向およびｊ方向の変数である。
【００６３】
そして、この初期化を終えたならば、
Ｄ１（m , n , u , v）＝Ｃ（m , n , u , v）＋α・Ｍａｘ（Ｄ１（m , n-1, p , q））
の算定式による計算をおこなう（ステップＳ２０５）。
【００６４】
その後、変数ｖをインクリメントし（ステップＳ２０６）、この変数ｖがＶよりも小さければ（ステップＳ２０７肯定）、ステップＳ２０５に移行して加算処理を繰り返す。つまり、探索範囲をｊ方向にずらすのである。
【００６５】
これに対して、変数ｖがＶ以上であれば（ステップＳ２０７否定）、変数ｕをインクリメントし（ステップＳ２０８）、この変数ｕがＵよりも小さければ（ステップＳ２０９肯定）、ステップＳ２０４に移行して加算処理を繰り返す。つまり、探索範囲をｉ方向にずらすことになる。
【００６６】
そして、変数ｕがＵ以上であれば（ステップＳ２０９否定）、ある画素についての計算を終了し、次の画素に移行する。具体的には、変数ｎをインクリメントして注目画素をｊ方向に移行させた後に（ステップＳ２１０）、この変数ｎをＮと比較し（ステップＳ２１１）、この変数ｎがＮよりも小さければ（ステップＳ２１１肯定）、ステップＳ２０３に移行して加算処理を繰り返す。
【００６７】
これに対して、変数ｎがＮ以上であれば（ステップＳ２１１否定）、変数ｍをインクリメントして注目画素をｉ方向に移行させた後に（ステップＳ２１２）、この変数ｍがＭよりも小さければ（ステップＳ２１３肯定）、ステップＳ２０２に移行して加算処理を繰り返し、変数ｍがＭ以上であれば（ステップＳ２１３否定）、処理を終了する。上記一連の処理をおこなうことにより、各類似度画像の全画素についてｊ方向の累積加算結果が得られることになる。
【００６８】
ところで、上記図１８のフローチャートでは、変数ｕ，ｖのインクリメントをおこないながら最大値を算出していた。別の計算方法として、あらかじめＣ（m, n-1 , u , v）に最大値フィルターをかけた最大値フィルター画像Ｄ１'（m , n-1, u , v）を作成しておき、α倍してからＣ（m , n , u , v）と加算することもできる。
【００６９】
そこで、かかる最大値フィルターを用いる場合の処理手順を図１９および図２０を用いて説明する。図１９は、図１に示した累積加算処理部１７による最大値フィルターを用いたｊ方向の累積加算処理手順を示すフローチャートであり、図２０は、最大値フィルターの処理手順を示すフローチャートである。
【００７０】
図１９に示すように、変数ｍを０に初期化し（ステップＳ３０１）、変数ｎを１に初期化した後（ステップＳ３０２）、最大値フィルターＤ１'（m , n-1 , u , v）を算定する（ステップＳ３０３）。
【００７１】
具体的には、図２０に示すように、変数ｕ，ｖを０に初期化した後に（ステップＳ４０１〜Ｓ４０２）、Ｄ１'（m , n , u , v）＝Ｍａｘ［Ｄ１（m , n , p, q）］を計算する（ステップＳ４０３）。ただし、ｕ−１≦ｐ≦ｕ＋１、ｖ−１≦ｑ≦ｖ＋１とする。そして、ｖをインクリメントして（ステップＳ４０４）、この変数ｖがＶよりも小さい場合には（ステップＳ４０５肯定）、ステップＳ４０３に移行して同様に計算をおこなう。また、変数ｖがＶ以上である場合には（ステップＳ４０５否定）、変数ｕをインクリメントして（ステップＳ４０６）、この変数ｕがＵよりも小さい場合には（ステップＳ４０６肯定）、ステップＳ４０２に移行して同様の処理を繰り返し、結果的に最大値を求める。
【００７２】
このようにして最大値フィルターを算定したならば、変数ｕおよびｖを０に初期化した後（ステップＳ３０４〜Ｓ３０５）、
Ｄ１（m , n , u , v）＝Ｃ（m , n , u , v）＋α・Ｍａｘ（Ｄ１'（m , n-1 , p , q））
の算定式による計算をおこなう（ステップＳ３０６）。
【００７３】
その後、変数ｖをインクリメントし（ステップＳ３０７）、この変数ｖがＶよりも小さければ（ステップＳ３０８肯定）、ステップＳ３０６に移行して加算処理を繰り返す。つまり、探索範囲をｊ方向にずらすのである。
【００７４】
これに対して、変数ｖがＶ以上であれば（ステップＳ３０８否定）、変数ｕをインクリメントし（ステップＳ３０９）、この変数ｕがＵよりも小さければ（ステップＳ３１０肯定）、ステップＳ３０５に移行して加算処理を繰り返す。つまり、探索範囲をｉ方向にずらすことになる。
【００７５】
そして、変数ｕがＵ以上であれば（ステップＳ３１０否定）、ある画素についての計算を終了し、次の画素に移行する。具体的には、変数ｎをインクリメントして注目画素をｊ方向に移行させた後に（ステップＳ３１１）、この変数ｎをＮと比較し（ステップＳ３１２）、この変数ｎがＮよりも小さければ（ステップＳ３１２肯定）、ステップＳ３０３に移行して加算処理を繰り返す。
【００７６】
これに対して、変数ｎがＮ以上であれば（ステップＳ３１２否定）、変数ｍをインクリメントして注目画素をｉ方向に移行させた後に（ステップＳ３１３）、この変数ｍがＭよりも小さければ（ステップＳ３１４肯定）、ステップＳ３０２に移行して加算処理を繰り返し、変数ｍがＭ以上であれば（ステップＳ３１４否定）、処理を終了する。
【００７７】
上述してきたように、本実施例に係る対応点探索装置によれば、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる。さらに、これに関連して、同じパターンが周期的に現れる画像間の対応付けをおこなう場合でも、精度の良い対応付け結果を取得することができる。
【００７８】
なお、本実施例では、類似度画像に対して１／４最大値圧縮および１／２最大値圧縮をおこなって本発明を実施する場合について説明したが、本発明はこれに限定されるものではなく、さらに最大値圧縮を段階的に繰り返しておこなう場合についても同様に適用することができる。また、最大値圧縮の圧縮率は、任意の倍率において適用することが可能な旨を追記しておく。
【００７９】
また、本実施例では、「対応点探索処理」における累積加算処理手順として、各類似度画像をｊ方向、−ｊ方向、ｉ方向、−ｉ方向の順序で再帰的に累積加算する場合を示したが、本発明は必ずしもこれに限定されるものではなく、斜め方向或いは一方向のみについて累積加算する場合に適用することもできる。一方向のみであっても、類似度が加算されることにより一定の大局情報が得られる。
【００８０】
また、本実施例では、類似度として正規化相関係数を用いた場合を示したが、本発明はこれに限定されるものではなく、ユークリッド距離などの他の指標を類似度として用いることもできる。
【００８１】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００８２】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【産業上の利用可能性】
【００８３】
以上のように、本発明に係る画像の対応点探索方法、対応点探索装置および対応点探索プログラムは、入力画像と参照画像の類似度を画素値として持つ類似度画像を作成し、該類似度画像に対して対応点探索処理をおこなって対応点を決定する画像の対応点探索方法、対応点探索装置および対応点探索プログラムに有用であり、特に、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる画像の対応点探索方法、対応点探索装置および対応点探索プログラムに適している。
【図面の簡単な説明】
【００８４】
【図１】本実施例に係る対応点検索装置の構成を示す機能ブロック図である。
【図２−１】本実施例で用いる参照画像の一例を示す図である。
【図２−２】本実施例で用いる入力画像の一例を示す図である。
【図３】参照部分画像の一例を示す図である。
【図４】入力部分画像の一例を示す図である。
【図５】類似度画像の作成概念を説明するための説明図である。
【図６】各処理段階における類似度画像の一例を示す図である。
【図７】最大値圧縮を説明するための概念図である。
【図８】対応点候補位置特定段階を説明するための概念図である。
【図９】対応点候補位置特定段階を説明するための概念図である。
【図１０】対応点決定段階を説明するための概念図である。
【図１１】累積加算手順を説明するための説明図である。
【図１２】ｊ方向の累積加算処理を説明するための説明図である。
【図１３】−ｊ方向の累積加算処理を説明するための説明図である。
【図１４】ｉ方向の累積加算処理を説明するための説明図である。
【図１５】−ｉ方向の累積加算処理を説明するための説明図である。
【図１６】各累積加算結果を加算する概念図である。
【図１７】図１に示した対応点探索装置の処理手順を示すフローチャートである。
【図１８】累積加算処理手順の一例を示すフローチャートである。
【図１９】最大値フィルターを用いて累積加算処理をおこなう場合の処理手順の一例を示すフローチャートである。
【図２０】最大値フィルターの処理手順の一例を示すフローチャートである。
【符号の説明】
【００８５】
１    対応点探索装置
１０    画像入力部
１１    分割処理部
１２    参照部分画像一時記憶部
１３    類似度画像作成部
１４    類似度画像圧縮処理部
１５    シフト量算出部
１６    シフト補正部
１７    累積加算処理部
１８    類似度画像更新部
１９    対応点決定部
２１    参照画像
２２    入力画像
５１    入力部分画像
５２    参照部分画像
５３    類似度画像
【図１】
2005165928.tif 000003
【図２−１】
2005165928.tif 000004
【図２−２】
2005165928.tif 000005
【図３】
2005165928.tif 000006
【図４】
2005165928.tif 000007
【図５】
2005165928.tif 000008
【図６】
2005165928.tif 000009
【図７】
2005165928.tif 000010
【図８】
2005165928.tif 000011
【図９】
2005165928.tif 000012
【図１０】
2005165928.tif 000013
【図１１】
2005165928.tif 000014
【図１２】
2005165928.tif 000015
【図１３】
2005165928.tif 000016
【図１４】
2005165928.tif 000017
【図１５】
2005165928.tif 000018
【図１６】
2005165928.tif 000019
【図１７】
2005165928.tif 000020
【図１８】
2005165928.tif 000021
【図１９】
2005165928.tif 000022
【図２０】
2005165928.tif 000023