JP4286565B2

JP4286565B2 - Corresponding point search method, corresponding point search device, and corresponding point search program

Info

Publication number: JP4286565B2
Application number: JP2003075534A
Authority: JP
Inventors: 弘之大西
Original assignee: Glory Ltd
Current assignee: Glory Ltd
Priority date: 2003-03-19
Filing date: 2003-03-19
Publication date: 2009-07-01
Anticipated expiration: 2023-03-19
Also published as: JP2004287522A

Description

【０００１】
【発明の属する技術分野】
この発明は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索方法、対応点探索装置および対応点探索プログラムに関し、特に、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる画像の対応点探索方法、対応点探索装置および対応点探索プログラムに関する。
【０００２】
【従来の技術】
従来、スキャナなどの画像入力装置から入力された入力画像をあらかじめ登録した参照画像とを照合する際に、両画像の対応点を探索して画像間の対応付けをおこなう技術が知られている。
【０００３】
たとえば、非特許文献１（従来技術１）には、設定したエネルギー関数を変分法の枠組みにより最小化する標準正則化理論を適用した技術が開示されている。この従来技術１が採用する標準正則化理論は、局所的な情報のみを使った繰り返し計算によりエネルギーを最小化することによって対応点を計算するものであるので、並列分散処理をおこなうことができ、人間の脳情報処理に近い処理を実現できる可能性がある。
【０００４】
また、非特許文献２（従来技術２）には、ＤＰ（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
【非特許文献３】
大西弘之，金出武雄，”大局的弛緩法による画像マッチング”，画像の認識・理解シンポジウム(MIRU2002)，Vol. 1 , pp.95-100，July 2002
【０００８】
【発明が解決しようとする課題】
この従来技術３によれば、ｊ方向、−ｊ方向、ｉ方向、−ｉ方向にそれぞれ累積加算した類似度画像をさらに加算する時に、注目する類似度画像に、ｊ方向、−ｊ方向、ｉ方向、−ｉ方向にそれぞれ隣接した類似度画像の近傍領域の最大値を加算することにより、大局的な整合性を考慮することができる。
【０００９】
しかしながら、この従来技術３では、複数の類似度画像を作成し、ｊ方向に累積加算をおこなった後に、−ｊ方向に累積加算をおこない、その後ｉ方向に累積加算をおこない、さらに−ｉ方向に累積加算する一連の処理を繰り返すこととしていたので、これらの処理を並列化することができず、処理を迅速化する上での制約がある。
【００１０】
また、上記従来技術４では、弛緩法の更新式において方向別（ｊ方向、−ｊ方向、ｉ方向、−ｉ方向）に独立に累積加算した４つの類似度画像をさらに加算して１つの類似度画像を作成するようになっており、その際更新された類似度画像の各点には、更新前の値に４倍の重みが付けられ、局所的に重みを付けた更新式を計算しているため、局所解に陥りやすくなるという問題がある。
【００１１】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、画像間の対応付けをおこなう際に、局所解に陥ることなく安定した対応付け結果を高速かつ効率良く取得することができる画像の対応点探索方法、対応点探索装置および対応点探索プログラムを提供することを目的とする。
【００１２】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、請求項１の発明に係る画像の対応点探索方法は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索方法であって、前記入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成する類似度画像生成工程と、前記類似度画像生成工程により生成された複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返す累積加算工程と、前記累積加算工程により累積加算処理された類似度画像の各画素の周辺画素の最大値を前記類似度画像生成工程により生成された類似度画像の各画素の画素値に累積加算して前記類似度画像を更新する類似度画像更新工程と、前記類似度画像更新工程により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまで前記累積加算工程による累積加算と前記類似度画像更新工程による更新を繰り返して、前記入力画像と参照画像の対応点を決定する対応点決定工程とを含んだことを特徴とする。
【００１３】
また、請求項２の発明に係る画像の対応点探索方法は、請求項１の発明において、前記対応点決定工程は、前記類似度画像更新工程により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となったときの更新後の各類似度画像の最大値の位置を前記対応点として決定することを特徴とする。
【００１４】
また、請求項３の発明に係る画像の対応点探索装置は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索装置であって、前記入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成する類似度画像生成手段と、前記類似度画像生成手段により生成された複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返す累積加算手段と、前記累積加算手段により累積加算処理された類似度画像の各画素の周辺画素の最大値を前記類似度画像生成手段により生成された類似度画像の各画素の画素値に累積加算して前記類似度画像を更新する類似度画像更新手段と、前記類似度画像更新手段により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となった際の最大値の位置に基づいて、前記入力画像と参照画像の対応点を決定する対応点決定手段とを備えたことを特徴とする。
【００１５】
また、請求項４の発明に係る画像の対応点探索プログラムは、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する画像の対応点探索プログラムであって、前記入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成する類似度画像生成手順と、前記類似度画像生成手順により生成された複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返す累積加算手順と、前記累積加算手順により累積加算処理された類似度画像の各画素の周辺画素の最大値を前記類似度画像生成手順により生成された類似度画像の各画素の画素値に累積加算して前記類似度画像を更新する類似度画像更新手順と、前記類似度画像更新手順により更新された更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまで前記累積加算手順による累積加算と前記類似度画像更新手順による更新を繰り返して、前記入力画像と参照画像の対応点を決定する対応点決定手順とをコンピュータに実行させることを特徴とする。
【００１６】
【発明の実施の形態】
以下に添付図面を参照して、この発明に係る画像の対応点探索方法、対応点探索装置および対応点探索プログラムの実施の形態を詳細に説明する。
【００１７】
図１は、本実施の形態で用いる対応点探索装置の構成を示す機能ブロック図である。同図に示す対応点探索装置１は、大まかには、（１）入力画像を分割した入力部分画像と参照画像を分割した参照部分画像との間の類似度を示す類似度画像を作成する類似度画像作成段階と、（２）複数の類似度画像を累積加算した結果に基づいて最適な対応点を決定する対応点決定段階の２つの段階の処理を行う。
【００１８】
具体的には、（１）類似度画像作成段階では、たとえば７×７画素のサイズからなる参照部分画像を２１×２１画素のサイズからなる入力部分画像内を移動させつつ順次相関値を求め、この相関値を画素値として持つ類似度画像を作成する。このため、この類似度画像は、参照部分画像上の中心点が入力部分画像上の点にどの程度類似しているかを示すことになる。
【００１９】
次に、（２）対応点決定段階では、各類似度画像の画素値を垂直方向および水平方向別に独立に累積加算を繰り返した後に、これらの累積加算結果から得られる各画素の周辺画素の最大値を類似度画像の各画素の画素値に累積加算して類似度画像を更新し、更新後の各類似度画像の最大値の位置と更新前の各類似度画像の最大値の位置との変動が所定値未満となるまでこれらの処理を繰り返して、入力部分画像上での対応点を求める。
【００２０】
次に、図１に示した対応点探索装置１の構成について説明する。なお、ここでは参照画像、入力画像の順に画像を入力する場合を示すこととする。図１に示すように、この対応点探索装置１は、画像入力部１０と、分割処理部１１と、参照部分画像一時記憶部１２と、類似度画像作成部１３と、累積加算処理部１４と、類似度画像更新部１５と、対応点決定部１６とからなる。
【００２１】
画像入力部１０は、縦横のサイズＩ、Ｊからなる参照画像Ｉ₀（ｉ，ｊ）および入力画像Ｉ₁（ｉ，ｊ）（０≦ｉ≦Ｉ−１，０≦ｊ≦Ｊ−１）を入力する入力部である。具体的には、光学的に原稿を読み取って画像を取得するスキャナや、ネットワークから画像を取得するインターフェース部や、二次記憶装置から画像を読み出す読み出し部が該当する。ここで、この入力画像とは、対応点の探索対象となる画像であって、歪みや変形を伴うものであっても良い。これに対して、参照画像とは、入力画像の比較の対象となる画像であり、歪みなどを伴わないものであることが望ましい。
【００２２】
図２（ａ）には参照画像２１を示しており、同図（ｂ）には入力画像２２を示している。これらの参照画像２１および入力画像２２は、いずれもアルファベット「ａ」の文字画像であり、３２×３２画素からなる。
【００２３】
分割処理部１１は、画像入力部１０により入力された入力画像および参照画像を入力部分画像および参照部分画像にそれぞれ分割する処理部である。ただし、入力画像の分割手順と参照画像の分割手順はそれぞれ異なる。
【００２４】
参照画像を分割する場合には、参照画像上で縦方向にＭ個、横方向にＮ個サンプリングした点（ｐ_m，ｑ_n）（０≦ｍ≦Ｍ−１，０≦ｎ≦Ｎ−１）を中心とした参照部分画像を作成する。図３は、図２（ａ）に示した参照画像２１の分割結果の一例を示す図であり、同図に示すように、ここでは３２×３２画素の参照画像２１を７×７画素からなる２５個の参照部分画像に分割している。具体的には、ｐ_m＝round（Ｉ／Ｍ）、ｑ_n＝round（Ｊ／Ｎ）としている。ただし、round（）は四捨五入を示している。
【００２５】
入力画像を分割する場合には、参照画像を分割する場合と異なり、各入力部分画像の一部が重なり合う重複したデータを持つように分割する。図４は、図２（ｂ）に示した入力画像２２の分割結果の一例を示す図であり、同図に示すように、ここでは３２×３２画素の入力画像２２を２１×２１画素からなる２５個の入力部分画像に分割している。
【００２６】
参照部分画像一時記憶部１２は、分割処理部１１で分割した各参照部分画像を一時記憶する記憶部であり、類似度画像作成部１３が類似度画像を作成する際に該当する参照部分画像が取り出される。
【００２７】
類似度画像作成部１３は、入力部分画像と参照部分画像の間の変形を考慮した類似度を算定して、該類似度を画素値として持つ類似度画像Ｃ（m , n , u , v）（０≦ｍ≦Ｍ−１，０≦ｎ≦Ｎ−１，０≦ｕ≦Ｕ−１，０≦ｖ≦Ｖ−１）を作成する処理部である。ただし、Ｕ，Ｖはそれぞれ類似度画像の縦横のサイズであるものとする。この類似度として正規化相関係数を用いることができる。
【００２８】
図５は、参照部分画像と入力部分画像から類似度画像を作成する概念を説明するための説明図である。なお、ここでは図３および図４の２行２列に位置する入力部分画像と参照部分画像を用いることとする。
【００２９】
同図に示すように、入力部分画像５１と参照部分画像５２の類似度を求める場合には、参照部分画像５２の中心画素を入力部分画像５２の左上部の画素に対応づけて正規化相関係数を計算し、その計算結果を類似度画像５３の左上部の画素の画素値とする。その後、参照部分画像５２を右にずらし、同様の処理をおこなう。上記処理を参照部分画像５２をずらしながら入力部分画像５１の全画素についておこなうことにより、類似度画像５３が求められる。
【００３０】
かかる類似度画像の作成処理を各入力部分画像ごとにおこなうと、図６に示すような複数の類似度画像が得られる。なお、参照部分画像の全ての画素の画素値が一定値である場合には、正規化相関係数の分母がゼロとなるため、この場合の類似度画像の画素値もゼロとなる。
【００３１】
累積加算処理部１４は、図７に示すように、各類似度画像をｊ方向、−ｊ方向、ｉ方向、−ｉ方向にそれぞれ独立して累積加算する処理部である。具体的には、類似度画像全体Ｃ(m , n , u , v)を４枚複写して、これをそれぞれD1(m , n , u , v)、D2(m , n , u , v)、D3(m , n , u , v)、D4(m , n , u , v)とし、それぞれｊ方向、−ｊ方向、ｉ方向、−ｉ方向の累積加算に使用する。たとえば、D1(m , n , u , v)を用いてｊ方向に累積加算する場合には、ｎ＝１〜Ｎ−１の類似度画像について、
Ｄ１（m , n , u , v）＝Ｃ（m , n , u , v）＋α・Ｍａｘ（Ｄ１（m , n-1 , p , q））
を順次再帰的に計算する。ただし、Ｍａｘ（）は最大値を示し、αは定数であり、０≦ｕ≦Ｕ−１、０≦ｖ≦Ｖ−１、０≦ｍ≦Ｍ−１、０≦ｎ≦Ｎ−１、ｕ−１≦ｐ≦ｕ＋１、ｖ−１≦ｑ≦ｖ＋１とする。
【００３２】
すなわち、ｊ方向に累積加算する場合には、図８に示すように、D1(m , n-1 , u , v)を中心とする8近傍内の９画素のうちの最大の画素値を求め、この最大の画素値をα倍してＣ(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））
の算定式による計算をおこなう（ステップＳ３０６）。
【００５８】
その後、変数ｖをインクリメントし（ステップＳ３０７）、この変数ｖがＶよりも小さければ（ステップＳ３０８肯定）、ステップＳ３０６に移行して加算処理を繰り返す。つまり、探索範囲をｊ方向にずらすのである。
【００５９】
これに対して、変数ｖがＶ以上であれば（ステップＳ３０８否定）、変数ｕをインクリメントし（ステップＳ３０９）、この変数ｕがＵよりも小さければ（ステップＳ３１０肯定）、ステップＳ３０５に移行して加算処理を繰り返す。つまり、探索範囲をｉ方向にずらすことになる。
【００６０】
そして、変数ｕがＵ以上であれば（ステップＳ３１０否定）、ある画素についての計算を終了し、次の画素に移行する。具体的には、変数ｎをインクリメントして注目画素をｊ方向に移行させた後に（ステップＳ３１１）、この変数ｎをＮと比較し（ステップＳ３１２）、この変数ｎがＮよりも小さければ（ステップＳ３１２肯定）、ステップＳ３０３に移行して加算処理を繰り返す。
【００６１】
これに対して、変数ｎがＮ以上であれば（ステップＳ３１２否定）、変数ｍをインクリメントして注目画素をｉ方向に移行させた後に（ステップＳ３１３）、この変数ｍがＭよりも小さければ（ステップＳ３１４肯定）、ステップＳ３０２に移行して加算処理を繰り返し、変数ｍがＭ以上であれば（ステップＳ３１４否定）、処理を終了する。
【００６２】
上述してきたように、本実施の形態によれば、画像入力部１０から参照画像と入力画像をそれぞれ入力し、分割処理部１１で参照部分画像および入力部分画像をそれぞれ作成、類似度画像作成部１３で参照部分画像と入力部分画像の類似度を求めた類似度画像をそれぞれ作成し、累積加算処理部１４で複数の類似度画像の累積加算処理を各方向ごと独立して再帰的に行い、更新前の値に重みが付かないように、類似度画像更新部１５で累積加算処理前の類似度画像の各画素の画素値に対して，４方向の類似度画像の累積加算処理後の画素値を加算して類似度画像を更新し、その結果に基づいて対応点決定部１６が対応点を決定するよう構成したので、大局的な最適化が行われローカルミニマムに陥るケースを低減することができる。
【００６３】
なお、本実施の形態では、説明の便宜上、参照画像と入力画像のサイズが同じ場合を示したが、本発明はこれに限定されるものではなく、参照画像と入力画像のサイズを異なる場合に適用することもできる。かかる場合にも同様の処理をおこなうことができる。
【００６４】
また、本実施の形態では、各類似度画像をｊ方向、−ｊ方向、ｉ方向、−ｉ方向の順序で再帰的に累積加算する場合を示したが、本発明は必ずしもこれに限定されるものではなく、斜め方向或いは一方向のみについて累積加算する場合に適用することもできる。一方向のみであっても、類似度が加算されることにより一定の大局情報が得られる。
【００６５】
また、本実施の形態では、類似度として正規化相関係数を用いた場合を示したが、本発明はこれに限定されるものではなく、ユークリッド距離などの他の指標を類似度として用いることもできる。
【００６６】
【発明の効果】
以上説明したように、本発明によれば、入力画像と参照画像をそれぞれ複数のブロックに分割した入力部分画像と参照部分画像の間の類似度を画素値として持つ縦方向および横方向に整列した複数の類似度画像を生成し、生成した複数の類似度画像を形成する各画素の周辺画素の最大値を、横方向（ｊ方向）、該横方向の逆方向（−ｊ方向）、縦方向（ｉ方向）、該縦方向の逆方向（−ｉ方向）にそれぞれ隣接する類似度画像の画素値に対してそれぞれ独立に累積加算する処理を繰り返し、累積加算処理された類似度画像の各画素の周辺画素の最大値を類似度画像の各画素の画素値に累積加算して類似度画像を更新する処理を更新前後の各類似度画像の最大値の位置の変動が所定値未満となるまで繰り返し、入力画像と参照画像の対応点を決定するよう構成したので、画像間の対応付けをおこなう際に、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することができる。
【図面の簡単な説明】
【図１】この発明の実施の形態に係る対応点探索装置の構成を示す機能ブロック図である。
【図２】本実施の形態で用いる参照画像および入力画像の一例を示す図である。
【図３】参照部分画像の一例を示す図である。
【図４】入力部分画像の一例を示す図である。
【図５】類似度画像の作成概念を説明するための説明図である。
【図６】図４に示した各入力部分画像に対応する類似度画像を示す図である。
【図７】累積加算手順を説明するための説明図である。
【図８】ｊ方向の累積加算処理を説明するための説明図である。
【図９】−ｊ方向の累積加算処理を説明するための説明図である。
【図１０】ｉ方向の累積加算処理を説明するための説明図である。
【図１１】−ｉ方向の累積加算処理を説明するための説明図である。
【図１２】各累積加算結果を加算する概念図である。
【図１３】累積加算後の類似度画像を示す図である。
【図１４】図１３に示した類似度画像の最大値の位置を示す図である。
【図１５】対応点に基づいて再構成した入力画像の歪み（変形）の一例を示す図である。
【図１６】図１に示した対応点探索装置の処理手順を示すフローチャートである。
【図１７】累積加算処理手順の一例を示すフローチャートである。
【図１８】最大値フィルターを用いて累積加算処理をおこなう場合の処理手順の一例を示すフローチャートである。
【図１９】最大値フィルターの処理手順の一例を示すフローチャートである。
【符号の説明】
１対応点探索装置
１０画像入力部
１１分割処理部
１２参照部分画像一時記憶部
１３類似度画像作成部
１４累積加算処理部
１５類似度画像更新部
１６対応点決定部
２１参照画像
２２入力画像
５１入力部分画像
５２参照部分画像
５３類似度画像[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an image corresponding point search method, a corresponding point search device, and a corresponding point search program for searching for corresponding points that associate an input image with a reference image to be compared with the input image, and in particular, correspondence between images. The present invention relates to a corresponding point search method, a corresponding point search device, and a corresponding point search program for an image that can acquire a stable matching result that is difficult to fall into a local solution at high speed and efficiency.
[0002]
[Prior art]
2. Description of the Related Art Conventionally, a technique is known in which when an input image input from an image input device such as a scanner is collated with a reference image registered in advance, a corresponding point between both images is searched and the images are associated with each other.
[0003]
For example, Non-Patent Document 1 (Prior Art 1) discloses a technique that applies a standard regularization theory that minimizes a set energy function by a framework of a variational method. The standard regularization theory adopted by this prior art 1 is to calculate corresponding points by minimizing energy by iterative calculation using only local information, so that parallel distributed processing can be performed. There is a possibility that processing close to human brain information processing can be realized.
[0004]
Non-Patent Document 2 (Prior Art 2) discloses a technique that employs a two-dimensional DP warp method that efficiently searches for an optimal solution using DP (Dynamic Programming). According to this prior art 2, the optimization problem can be calculated efficiently.
[0005]
However, in the above prior art 1, since the corresponding points are calculated by minimizing energy by iterative calculation using only local information, there is a problem that the influence of the initial value becomes large, and a local solution (local minimum). There is a problem that it is difficult to obtain an optimum matching result because it is easy to fall into the process. Moreover, although the thing of the prior art 2 can search an optimal solution efficiently by DP, there exists a problem that the computational complexity becomes huge. Specifically, in order to obtain an optimal solution, calculation time in the exponent order of the image size is required.
[0006]
From these facts, the applicant of the present patent application can obtain a stable matching result without falling into a local solution when performing matching between images in Japanese Patent Application No. 2002-056661 (Prior Art 3). An image corresponding point searching apparatus, a corresponding point searching method, and a program for causing a computer to execute the method have been proposed. In Non-Patent Document 3, an image matching method using the relaxation method (prior art 4) was proposed.
[0007]
[Non-Patent Document 1]
T.Poggio, V.TorreandC.Koch, “Computational vision and regularization theory”, NATURE Vol.317, pp. 314-319, 1985
[Non-Patent Document 2]
Seiichi Uchida and Hiroaki Sakoe, “Study of monotonic continuous two-dimensional warp method based on dynamic programming”, IEICE theory (D-II) Vol. J81-D-II no. 6, pp.1251-1258, June 1998
[Non-Patent Document 3]
Hiroyuki Onishi, Takeo Kanade, “Image Matching by Global Relaxation”, Image Recognition and Understanding Symposium (MIRU2002), Vol. 1, pp.95-100, July 2002
[0008]
[Problems to be solved by the invention]
According to this prior art 3, when the similarity images cumulatively added in the j direction, −j direction, i direction, and −i direction are further added, the similarity image to be noticed is added to the j direction, −j direction, i, The global consistency can be taken into consideration by adding the maximum values of the neighborhood regions of the similarity images adjacent to each other in the direction and the -i direction.
[0009]
However, in this prior art 3, after creating a plurality of similarity images, performing cumulative addition in the j direction, performing cumulative addition in the -j direction, then performing cumulative addition in the i direction, and further in the -i direction. Since a series of processes for accumulative addition is repeated, these processes cannot be parallelized, and there are restrictions in speeding up the processes.
[0010]
Further, in the above-mentioned conventional technique 4, four similarity images that are cumulatively added independently for each direction (j direction, -j direction, i direction, -i direction) in the update method of the relaxation method are further added to obtain one similarity. An image is created, and each point of the similarity image updated at that time is weighted four times as much as the value before the update, and a locally weighted update formula is calculated. Therefore, there is a problem that it is easy to fall into a local solution.
[0011]
The present invention was made to solve the above-described problems caused by the prior art, and when performing association between images, a stable association result can be acquired quickly and efficiently without falling into a local solution. An object of the present invention is to provide a corresponding point searching method, a corresponding point searching apparatus, and a corresponding point searching program.
[0012]
[Means for Solving the Problems]
In order to solve the above-described problems and achieve the object, the corresponding point search method for an image according to the invention of claim 1 searches for a corresponding point that associates an input image with a reference image to be compared with the input image. A method for searching for corresponding points of an image, wherein the input image and the reference image are each divided into a plurality of blocks, and a plurality of images arranged in the vertical and horizontal directions having a similarity between the input partial image and the reference partial image as pixel values A similarity image generation step of generating a similarity image of the image, a maximum value of peripheral pixels of each pixel forming the plurality of similarity images generated by the similarity image generation step in a horizontal direction (j direction), A process of accumulatively adding the pixel values of similarity images adjacent to each other in the reverse direction of the horizontal direction (-j direction), the vertical direction (i direction), and the reverse direction of the vertical direction (-i direction). Repeat cumulative addition process and previous The similarity image is obtained by cumulatively adding the maximum value of the peripheral pixels of each pixel of the similarity image subjected to the cumulative addition process in the cumulative addition process to the pixel value of each pixel of the similarity image generated by the similarity image generation process. And a variation between a maximum value position of each similarity image updated by the similarity image update process and a maximum value position of each similarity image before update is predetermined. A corresponding point determining step of determining a corresponding point between the input image and the reference image by repeating the cumulative addition in the cumulative adding step and the update by the similarity image updating step until the value becomes less than a value. .
[0013]
According to a second aspect of the present invention, the corresponding point searching method according to the first aspect of the present invention is the method according to the first aspect, wherein the corresponding point determining step is a maximum of each updated similarity image updated by the similarity image updating step. The position of the maximum value of each similarity image after update when the variation between the position of the value and the position of the maximum value of each similarity image before the update is less than a predetermined value is determined as the corresponding point. And
[0014]
An image corresponding point search device according to the invention of claim 3 is an image corresponding point search device that searches for a corresponding point that associates an input image with a reference image to be compared with the input image, and Similarity image generation that generates a plurality of similarity images arranged in the vertical and horizontal directions with the similarity between the input partial image and the reference partial image as pixel values obtained by dividing the input image and the reference image into a plurality of blocks, respectively. And the maximum value of the peripheral pixels of each pixel forming the plurality of similarity images generated by the similarity image generation unit, the horizontal direction (j direction), the reverse direction of the horizontal direction (-j direction), A cumulative addition unit that repeatedly performs cumulative addition on pixel values of similarity images adjacent to each other in the vertical direction (i direction) and in the opposite direction (−i direction) of the vertical direction, and the cumulative addition unit Cumulative addition processing Similarity image update means for updating the similarity image by cumulatively adding the maximum value of neighboring pixels of each pixel of the similarity image to the pixel value of each pixel of the similarity image generated by the similarity image generation means; The maximum value when the variation between the position of the maximum value of each similarity image updated by the similarity image update unit and the position of the maximum value of each similarity image before the update is less than a predetermined value. And corresponding point determining means for determining corresponding points between the input image and the reference image based on the position of the input image.
[0015]
An image corresponding point search program according to the invention of claim 4 is an image corresponding point search program for searching for a corresponding point that associates an input image with a reference image to be compared with the input image, Similarity image generation that generates a plurality of similarity images arranged in the vertical and horizontal directions with the similarity between the input partial image and the reference partial image as pixel values obtained by dividing the input image and the reference image into a plurality of blocks, respectively. A maximum value of peripheral pixels of each pixel forming the plurality of similarity images generated by the procedure and the similarity image generation procedure in the horizontal direction (j direction), the reverse direction of the horizontal direction (−j direction), A cumulative addition procedure that repeats cumulative addition processing independently for pixel values of similarity images adjacent to each other in the vertical direction (i direction) and the reverse direction (−i direction) of the vertical direction, and the cumulative addition procedure Accumulation A similarity degree that updates the similarity image by cumulatively adding a maximum value of peripheral pixels of each pixel of the similarity degree image that has been subjected to the arithmetic processing to a pixel value of each pixel of the similarity degree image generated by the similarity degree image generation procedure Until the variation between the image update procedure and the position of the maximum value of each similarity image updated by the similarity image update procedure and the position of the maximum value of each similarity image before the update is less than a predetermined value The cumulative addition by the cumulative addition procedure and the update by the similarity image update procedure are repeated to cause the computer to execute a corresponding point determination procedure for determining corresponding points between the input image and the reference image.
[0016]
DETAILED DESCRIPTION OF THE INVENTION
Exemplary embodiments of a corresponding point search method, a corresponding point search apparatus, and a corresponding point search program according to the present invention will be described below in detail with reference to the accompanying drawings.
[0017]
FIG. 1 is a functional block diagram showing the configuration of the corresponding point search apparatus used in the present embodiment. The corresponding point search apparatus 1 shown in FIG. 1 roughly includes (1) a similarity image that creates a similarity image indicating a similarity between an input partial image obtained by dividing an input image and a reference partial image obtained by dividing a reference image. The process of the two steps of the degree image creation stage and (2) the corresponding point determination stage for determining the optimum corresponding point based on the result of accumulating a plurality of similarity images is performed.
[0018]
Specifically, (1) in the similarity image creation stage, for example, a correlation value is sequentially obtained while moving a reference partial image having a size of 7 × 7 pixels within an input partial image having a size of 21 × 21 pixels, A similarity image having the correlation value as a pixel value is created. Therefore, this similarity image indicates how similar the center point on the reference partial image is to the point on the input partial image.
[0019]
Next, in (2) the corresponding point determination stage, the pixel values of each similarity image are repeatedly accumulated and added separately for each of the vertical direction and the horizontal direction, and then the maximum of the peripheral pixels of each pixel obtained from these cumulative addition results The value is cumulatively added to the pixel value of each pixel of the similarity image to update the similarity image, and the position of the maximum value of each similarity image after the update and the position of the maximum value of each similarity image before the update These processes are repeated until the fluctuation becomes less than a predetermined value, and corresponding points on the input partial image are obtained.
[0020]
Next, the configuration of the corresponding point search apparatus 1 shown in FIG. 1 will be described. Here, the case where the images are input in the order of the reference image and the input image is shown. As shown in FIG. 1, the corresponding point search apparatus 1 includes an image input unit 10, a division processing unit 11, a reference partial image temporary storage unit 12, a similarity image creation unit 13, and a cumulative addition processing unit 14. The similarity image updating unit 15 and the corresponding point determining unit 16 are included.
[0021]
The image input unit 10 generates a reference image I having vertical and horizontal sizes I and J. ₀ (I, j) and input image I ₁ (I, j) is an input unit for inputting (0 ≦ i ≦ I−1, 0 ≦ j ≦ J−1). Specifically, a scanner that optically reads a document to acquire an image, an interface unit that acquires an image from a network, and a reading unit that reads an image from a secondary storage device are applicable. Here, the input image is an image to be searched for corresponding points, and may be one that is distorted or deformed. On the other hand, the reference image is an image to be compared with the input image, and it is desirable that the image is not accompanied by distortion.
[0022]
FIG. 2A shows a reference image 21 and FIG. 2B shows an input image 22. The reference image 21 and the input image 22 are both character images of the alphabet “a” and are composed of 32 × 32 pixels.
[0023]
The division processing unit 11 is a processing unit that divides the input image and the reference image input by the image input unit 10 into an input partial image and a reference partial image, respectively. However, the procedure for dividing the input image is different from the procedure for dividing the reference image.
[0024]
When the reference image is divided, M points in the vertical direction and N points in the horizontal direction on the reference image (p _m , Q _n ) A reference partial image centered on (0 ≦ m ≦ M−1, 0 ≦ n ≦ N−1) is created. FIG. 3 is a diagram showing an example of the division result of the reference image 21 shown in FIG. 2A. As shown in FIG. 3, the reference image 21 of 32 × 32 pixels is composed of 7 × 7 pixels. The image is divided into 25 reference partial images. Specifically, p _m = Round (I / M), q _n = Round (J / N). However, round () indicates rounding off.
[0025]
When the input image is divided, unlike the case of dividing the reference image, the input image is divided so that a part of each input partial image has overlapping data. FIG. 4 is a diagram showing an example of the division result of the input image 22 shown in FIG. 2B. As shown in FIG. 4, the 32 × 32 pixel input image 22 is composed of 21 × 21 pixels. It is divided into 25 input partial images.
[0026]
The reference partial image temporary storage unit 12 is a storage unit that temporarily stores each reference partial image divided by the division processing unit 11, and the reference partial image corresponding when the similarity image creating unit 13 creates the similarity image is displayed. It is taken out.
[0027]
The similarity image creation unit 13 calculates a similarity considering the deformation between the input partial image and the reference partial image, and a similarity image C (m 1, n 2, u 3 v) having the similarity as a pixel value. (0 ≦ m ≦ M−1, 0 ≦ n ≦ N−1, 0 ≦ u ≦ U−1, 0 ≦ v ≦ V−1). However, U and V are the vertical and horizontal sizes of the similarity image. A normalized correlation coefficient can be used as this similarity.
[0028]
FIG. 5 is an explanatory diagram for explaining the concept of creating a similarity image from a reference partial image and an input partial image. Here, the input partial image and the reference partial image located in 2 rows and 2 columns of FIGS. 3 and 4 are used.
[0029]
As shown in the figure, when obtaining the similarity between the input partial image 51 and the reference partial image 52, the normalization phase relationship is obtained by associating the center pixel of the reference partial image 52 with the upper left pixel of the input partial image 52. The number is calculated, and the calculation result is set as the pixel value of the upper left pixel of the similarity image 53. Thereafter, the reference partial image 52 is shifted to the right, and the same processing is performed. The similarity image 53 is obtained by performing the above processing for all the pixels of the input partial image 51 while shifting the reference partial image 52.
[0030]
When such similarity image creation processing is performed for each input partial image, a plurality of similarity images as shown in FIG. 6 are obtained. Note that when the pixel values of all the pixels of the reference partial image are constant, the denominator of the normalized correlation coefficient is zero, and the pixel value of the similarity image in this case is also zero.
[0031]
As shown in FIG. 7, the cumulative addition processing unit 14 is a processing unit that cumulatively adds each similarity image independently in the j direction, the −j direction, the i direction, and the −i direction. Specifically, four similar images C (m, n, u, v) are copied, and these are copied as D1 (m, n, u, v) and D2 (m, n, u, v), respectively. , D3 (m, n, u, v), D4 (m, n, u, v), which are used for cumulative addition in the j direction, -j direction, i direction, and -i direction, respectively. For example, in the case of cumulative addition in the j direction using D1 (m, n, u, v), for similarity images of n = 1 to N−1,
D1 (m, n, u, v) = C (m, n, u, v) + α · Max (D1 (m, n-1, p, q))
Are sequentially recursively calculated. However, Max () indicates the maximum value, α is a constant, 0 ≦ u ≦ U−1, 0 ≦ v ≦ V−1, 0 ≦ m ≦ M−1, 0 ≦ n ≦ N−1, u −1 ≦ p ≦ u + 1 and v−1 ≦ q ≦ v + 1.
[0032]
That is, when accumulatively adding in the j direction, as shown in FIG. 8, the maximum pixel value of 9 pixels in 8 neighborhoods centering on D1 (m, n-1, u, v) is obtained. The process of multiplying the maximum pixel value by α and adding it to the pixel value of C (m, n, u, v) is recursively repeated.
[0033]
When accumulatively adding in the −j direction, n = N−2 to 0 similarity images,
D3 (m, n, u, v) = C (m, n, u, v) + α · Max (D3 (m, n + 1, p, q))
Are sequentially recursively calculated. However, 0≤u≤U-1, 0≤v≤V-1, 0≤m≤M-1, and 0≤n≤N-2. That is, in the case of cumulative addition in the −j direction, as shown in FIG. 9, the maximum pixel value among 9 pixels in 8 neighborhoods centered on D3 (m, n + 1, u, v) is set. The process of obtaining and multiplying the maximum pixel value by α and adding it to the pixel value of C (m, n, u, v) is recursively repeated.
[0034]
In addition, in the case of cumulative addition in the i direction, for m = 1 to M−1 similarity images,
D2 (m, n, u, v) = C (m, n, u, v) + α · Max (D2 (m−1, n, p, q))
Are sequentially recursively calculated. However, 0≤u≤U-1, 0≤v≤V-1, 1≤m≤M-1, and 0≤n≤N-1. That is, when accumulatively adding in the i direction, as shown in FIG. 10, the maximum pixel value of 9 pixels in 8 neighborhoods centering on D2 (m−1, n, u, v) is obtained. The process of multiplying the maximum pixel value by α and adding it to the pixel value of C (m, n, u, v) is recursively repeated.
[0035]
In addition, in the case of cumulative addition in the -i direction, for similarity images of m = M-2 to 0,
D4 (m, n, u, v) = C (m, n, u, v) + α · Max (D4 (m + 1, n, p, q))
Are sequentially recursively calculated. However, 0≤u≤U-1, 0≤v≤V-1, 0≤m≤M-2, and 0≤n≤N-1. That is, when accumulatively adding in the -i direction, as shown in FIG. 11, the maximum pixel value of 9 pixels in 8 neighborhoods centered on D4 (m + 1, n, u, v) is set. The process of obtaining and multiplying the maximum pixel value by α and adding it to the pixel value of C (m, n, u, v) is recursively repeated.
[0036]
The similarity image update unit 15 is a processing unit that updates the similarity image based on the similarity image after the cumulative addition of the cumulative addition processing unit 14. Specifically, if cumulative addition processing is performed for each direction, as shown in the conceptual diagram of FIG.
C (m, n, u, v) = C (m, n, u, v) + α · Max (D1 (m, n-1, p, q))
+ Α · Max (D2 (m−1, n, p, q))
+ Α · Max (D3 (m, n + 1, p, q))
+ Α · Max (D4 (m + 1, n, p, q))
C (m, n, u, v) is updated by the following formula.
[0037]
Thereafter, the corresponding point determination unit 16 detects the position of the maximum value of each similarity image, and performs cumulative addition unless the change between the position and the position of the maximum value of each previous similarity image is within a predetermined range. The process is repeated by feeding back, and the repetition is terminated when it falls within a predetermined range, and the position of the maximum value of each similarity image at that time is determined as a corresponding point. Note that the previous similarity images described above are each similarity image created by the similarity image creation unit 13 in the case of the initial processing, and the similarity image update unit 15 performs the previous update processing after the first time. Each similarity image thus obtained is obtained.
[0038]
For example, when each similarity image shown in FIG. 13 is obtained by the cumulative addition process and the update process, the change from the position of the maximum value of the previous similarity image to the position of the maximum value of each similarity image is calculated. When the change is within a predetermined range, the position of the maximum value at this time is set as the corresponding point. The state of the maximum value position is shown in FIG. FIG. 15 illustrates the distortion of the input image based on the corresponding points.
[0039]
Next, the processing procedure of the corresponding point search apparatus 1 shown in FIG. 1 will be described. Although partially overlapping with the above description, the processing procedure will be described with reference to FIGS.
[0040]
FIG. 16 is a flowchart showing a processing procedure of the corresponding point search apparatus 1 shown in FIG. As shown in the figure, when the corresponding point detection device 1 acquires a reference image and an input image, the reference image is divided into reference partial images (step S101). For example, the reference image 21 of 32 × 32 pixels shown in FIG. 2A is divided into 25 reference partial images composed of 7 × 7 pixels shown in FIG. 3 and stored. This reference partial image may be stored in advance for each image to be referred to, or only a reference image is stored separately in advance, not a reference partial image, and the similarity between an input image and a reference image, which will be described later, is stored. When calculating the degree, the stored reference image may be divided into reference partial images.
[0041]
Thereafter, the input image is divided into input partial images (step S102). For example, the 32 × 32 pixel input image 22 shown in FIG. 2B is divided into 25 input partial images consisting of 21 × 21 pixels shown in FIG.
[0042]
Then, a similarity image between the reference partial image and the input partial image is created (step S103). For example, as shown in FIG. 5, the similarity image 53 having the similarity between the input partial image 51 and the reference partial image 52 as a pixel value is created for each input partial image, and a plurality of such as shown in FIG. Create a similarity image of. Subsequently, a position where the pixel value of each similarity image is maximized (hereinafter referred to as “maximum value position”) is detected (step S104).
[0043]
Thereafter, the cumulative addition process in four directions, that is, the j direction, the cumulative addition process in the -j direction, the cumulative addition process in the i direction, and the cumulative addition process in the -i direction are performed independently (step 105), j,- Each similarity image is obtained by adding the maximum value of 9 pixels within 8 neighborhoods of each pixel of the similarity image cumulatively added in the j, i, and -i directions to each pixel of the similarity image created in step S103. Update (step S106), and then detect the position of the maximum value of the updated similarity image (step S107). Specifically, by repeating the addition processing shown in FIGS. 8 to 12, a similarity image as shown in FIG. 13 is created, and the position of the maximum value of each similarity image as shown in FIG. To detect.
[0044]
Next, the position fluctuation of the maximum value of each similarity image is calculated (step S108), and it is checked whether or not the position fluctuations of all the maximum values are within a predetermined value (step S109). (No at step S109), the process proceeds to step S105, and the same process is repeated. If it is within the predetermined value (Yes at step S109), this position is determined as a corresponding point (step S110), and the process is terminated. Note that the process in step S109 described above is a process of checking whether or not the change in the position of the maximum value of each similarity image from the position of the maximum value of each previous similarity image is within a predetermined value. If it is within the predetermined value, in step S110, the position of the maximum value of each similarity image after the update process is determined as the corresponding point of the input image with respect to the reference image.
[0045]
Here, for convenience of explanation, the cumulative addition process in the j direction, the cumulative addition process in the -j direction, the cumulative addition process in the i direction, and the cumulative addition process in the -i direction are sequentially performed. Since processing can be performed, parallel processing can also be performed.
[0046]
Next, the cumulative addition processing procedure in the j direction by the cumulative addition processing unit 14 shown in FIG. 1 will be described in detail. FIG. 17 is a flowchart showing the cumulative addition processing procedure in the j direction by the cumulative addition processing unit 14 shown in FIG. The cumulative addition processing in the −j direction, i direction, and −i direction can be performed in the same manner.
[0047]
As shown in the figure, first, the variables m, u, and v are set to 0, and the variable n is set to 1 (steps S201 to S204). Here, the variable m is a variable used as an index in the i direction, and the variable n is a variable used as an index in the j direction. Variables u and v are i-direction and j-direction variables indicating the search range.
[0048]
And when this initialization is finished,
D1 (m, n, u, v) = C (m, n, u, v) + α · Max (D1 (m, n-1, p, q))
The calculation is performed according to the formula (step S205).
[0049]
Thereafter, the variable v is incremented (step S206). If the variable v is smaller than V (Yes in step S207), the process proceeds to step S205 and the addition process is repeated. That is, the search range is shifted in the j direction.
[0050]
On the other hand, if the variable v is greater than or equal to V (No at Step S207), the variable u is incremented (Step S208). If the variable u is smaller than U (Yes at Step S209), the process proceeds to Step S204. Repeat the addition process. That is, the search range is shifted in the i direction.
[0051]
If the variable u is greater than or equal to U (No at step S209), the calculation for a certain pixel is terminated and the process proceeds to the next pixel. Specifically, after the variable n is incremented to shift the pixel of interest in the j direction (step S210), the variable n is compared with N (step S211). If the variable n is smaller than N (step S211) (Yes in S211), the process proceeds to step S203 and the addition process is repeated.
[0052]
On the other hand, if the variable n is greater than or equal to N (No in step S211), the variable m is incremented to shift the pixel of interest in the i direction (step S212), and if the variable m is smaller than M (step S212). If the result of step S213 is affirmative, the process proceeds to step S202 and the addition process is repeated. By performing the above-described series of processing, a cumulative addition result in the j direction is obtained for all the pixels of each similarity image.
[0053]
By the way, in the flowchart of FIG. 17, the maximum value is calculated while incrementing the variables u and v. As another calculation method, a maximum value filter image D1 ′ (m, n−1, u, v) obtained by applying a maximum value filter to C (m, n−1, u, v) in advance is created, and α It is also possible to add C (m, n, u, v) after multiplying.
[0054]
Therefore, a processing procedure when using such a maximum value filter will be described with reference to FIGS. FIG. 18 is a flowchart showing the cumulative addition processing procedure in the j direction using the maximum value filter by the cumulative addition processing unit 14 shown in FIG. 1, and FIG. 19 is a flowchart showing the processing procedure of the maximum value filter.
[0055]
As shown in FIG. 18, after the variable m is initialized to 0 (step S301) and the variable n is initialized to 1 (step S302), the maximum value filter D1 ′ (m 1, n−1, u
, v) is calculated (step S303).
[0056]
Specifically, as shown in FIG. 19, after the variables u and v are initialized to 0 (steps S401 to S402), D1 ′ (m, n, u, v) = Max [D1 (m, n, p, q)] is calculated (step S403). However, u−1 ≦ p ≦ u + 1 and v−1 ≦ q ≦ v + 1. Then, v is incremented (step S404), and when the variable v is smaller than V (Yes at step S405), the process proceeds to step S403 and the same calculation is performed. When the variable v is V or more (No at Step S405), the variable u is incremented (Step S406). When the variable u is smaller than U (Yes at Step S406), the process proceeds to Step S402. The same processing is repeated, and the maximum value is obtained as a result.
[0057]
If the maximum value filter is calculated in this way, after the variables u and v are initialized to 0 (steps S304 to S305),
D1 (m, n, u, v) = C (m, n, u, v) + α · Max (D1 ′ (m, n−1, p, q))
The calculation is performed according to the formula (step S306).
[0058]
Thereafter, the variable v is incremented (step S307). If the variable v is smaller than V (Yes at step S308), the process proceeds to step S306 and the addition process is repeated. That is, the search range is shifted in the j direction.
[0059]
On the other hand, if the variable v is equal to or greater than V (No at Step S308), the variable u is incremented (Step S309). If the variable u is smaller than U (Yes at Step S310), the process proceeds to Step S305. Repeat the addition process. That is, the search range is shifted in the i direction.
[0060]
If the variable u is greater than or equal to U (No at step S310), the calculation for a certain pixel is terminated and the process proceeds to the next pixel. Specifically, after the variable n is incremented to shift the pixel of interest in the j direction (step S311), the variable n is compared with N (step S312), and if the variable n is smaller than N (step S311). (S312 Yes), it moves to step S303 and repeats an addition process.
[0061]
On the other hand, if the variable n is greater than or equal to N (No in step S312), the variable m is incremented to shift the pixel of interest in the i direction (step S313), and if the variable m is smaller than M (step S313). If step S314 is affirmative, the process proceeds to step S302 and the addition process is repeated.
[0062]
As described above, according to the present embodiment, the reference image and the input image are respectively input from the image input unit 10, and the reference partial image and the input partial image are respectively generated by the division processing unit 11. 13 respectively create similarity images for which the similarity between the reference partial image and the input partial image is obtained, and the cumulative addition processing unit 14 performs recursive addition processing of a plurality of similarity images independently in each direction, Pixels after cumulative addition processing of similarity images in four directions are performed on the pixel values of each pixel of the similarity image before cumulative addition processing by the similarity image update unit 15 so that the values before update are not weighted. Since the similarity image is updated by adding the values, and the corresponding point determination unit 16 determines the corresponding points based on the result, it is possible to reduce the case where global optimization is performed and falls into the local minimum. Can do.
[0063]
In this embodiment, for convenience of explanation, the case where the size of the reference image and the input image is the same is shown. However, the present invention is not limited to this, and the size of the reference image and the input image is different. It can also be applied. In such a case, similar processing can be performed.
[0064]
Further, in the present embodiment, a case has been described in which each similarity image is recursively added in the order of j direction, −j direction, i direction, and −i direction, but the present invention is not necessarily limited thereto. However, the present invention can be applied to the case where cumulative addition is performed only in an oblique direction or only in one direction. Even in only one direction, constant global information can be obtained by adding similarities.
[0065]
In this embodiment, the case where the normalized correlation coefficient is used as the similarity is shown. However, the present invention is not limited to this, and another index such as the Euclidean distance is used as the similarity. You can also.
[0066]
【The invention's effect】
As described above, according to the present invention, the input image and the reference image are divided into a plurality of blocks, and the input partial image and the reference partial image are aligned in the vertical direction and the horizontal direction having pixel values as similarities. A plurality of similarity images are generated, and the maximum value of the peripheral pixels of each pixel forming the generated plurality of similarity images is set in the horizontal direction (j direction), the reverse direction of the horizontal direction (−j direction), and the vertical direction. (I direction), each pixel value of the similarity image subjected to the cumulative addition process is repeated by repeatedly accumulating the pixel values of the similarity image pixels adjacent to each other in the reverse direction (−i direction) of the vertical direction. The process of updating the similarity image by cumulatively adding the maximum value of the peripheral pixels of the image to the pixel value of each pixel of the similarity image until the variation in the position of the maximum value of each similarity image before and after the update becomes less than a predetermined value Repeatedly determine the corresponding points between the input image and the reference image Since it is configured to, when performing correspondence between images, a correlation result of fall hardly stable in a local solution can be obtained fast and efficient manner.
[Brief description of the drawings]
FIG. 1 is a functional block diagram showing a configuration of a corresponding point search apparatus according to an embodiment of the present invention.
FIG. 2 is a diagram illustrating an example of a reference image and an input image used in the present embodiment.
FIG. 3 is a diagram illustrating an example of a reference partial image.
FIG. 4 is a diagram illustrating an example of an input partial image.
FIG. 5 is an explanatory diagram for explaining a concept of creating a similarity image.
6 is a view showing a similarity image corresponding to each input partial image shown in FIG. 4. FIG.
FIG. 7 is an explanatory diagram for explaining a cumulative addition procedure.
FIG. 8 is an explanatory diagram for explaining cumulative addition processing in the j direction.
FIG. 9 is an explanatory diagram for explaining cumulative addition processing in the −j direction.
FIG. 10 is an explanatory diagram for explaining cumulative addition processing in the i direction.
FIG. 11 is an explanatory diagram for explaining cumulative addition processing in the -i direction.
FIG. 12 is a conceptual diagram for adding each cumulative addition result.
FIG. 13 is a diagram showing a similarity image after cumulative addition.
14 is a diagram showing the position of the maximum value of the similarity image shown in FIG.
FIG. 15 is a diagram illustrating an example of distortion (deformation) of an input image reconstructed based on corresponding points.
16 is a flowchart showing a processing procedure of the corresponding point search apparatus shown in FIG. 1;
FIG. 17 is a flowchart illustrating an example of a cumulative addition processing procedure.
FIG. 18 is a flowchart illustrating an example of a processing procedure when cumulative addition processing is performed using a maximum value filter.
FIG. 19 is a flowchart illustrating an example of a maximum value filter processing procedure;
[Explanation of symbols]
1 Corresponding point search device
10 Image input section
11 Division processing part
12 Reference partial image temporary storage unit
13 Similarity Image Creation Unit
14 Cumulative addition processing unit
15 Similarity image update unit
16 Corresponding point determination part
21 Reference image
22 Input image
51 Input partial image
52 Reference partial image
53 Similarity Image

Claims

A corresponding point search method for an image for searching for a corresponding point that associates an input image with a reference image to be compared with the input image,
A similarity image for generating a plurality of similarity images aligned in the vertical and horizontal directions having the similarity between the input partial image and the reference partial image obtained by dividing the input image and the reference image into a plurality of blocks, respectively, as pixel values Generation process;
The maximum value of the peripheral pixels of each pixel forming the plurality of similarity images generated by the similarity image generation step is set in the horizontal direction (j direction), the reverse direction of the horizontal direction (−j direction), the vertical direction ( i direction), and a cumulative addition step of repeating a process of independently cumulatively adding to pixel values of similarity images respectively adjacent in the reverse direction (−i direction) of the vertical direction;
The similarity is obtained by accumulatively adding the maximum value of the peripheral pixels of each pixel of the similarity image subjected to the cumulative addition process in the cumulative addition process to the pixel value of each pixel of the similarity image generated by the similarity image generation process. A similarity image update process for updating the image;
By the cumulative addition process until the variation between the maximum value position of each updated similarity image updated by the similarity image update process and the maximum value position of each similarity image before the update is less than a predetermined value. A corresponding point search method for an image, comprising: a corresponding point determination step for determining a corresponding point between the input image and a reference image by repeating cumulative addition and updating by the similarity image updating step.

In the corresponding point determination step, the variation between the maximum value position of each updated similarity image updated by the similarity image update step and the maximum value position of each similarity image before the update is less than a predetermined value. 2. The method for searching for corresponding points of an image according to claim 1, wherein the position of the maximum value of each similarity image after being updated is determined as the corresponding point.

An image corresponding point search device that searches for corresponding points that associate an input image with a reference image to be compared with the input image,
A similarity image for generating a plurality of similarity images aligned in the vertical and horizontal directions having the similarity between the input partial image and the reference partial image obtained by dividing the input image and the reference image into a plurality of blocks, respectively, as pixel values Generating means;
The maximum values of the peripheral pixels of each pixel forming the plurality of similarity images generated by the similarity image generating means are set in the horizontal direction (j direction), the reverse direction of the horizontal direction (−j direction), the vertical direction ( i direction), and cumulative addition means for repeating the process of independently cumulatively adding to the pixel values of the similarity images respectively adjacent in the vertical direction (−i direction).
The similarity is obtained by cumulatively adding the maximum value of the peripheral pixels of each pixel of the similarity image that has been cumulatively added by the cumulative addition means to the pixel value of each pixel of the similarity image generated by the similarity image generation means. Similarity image updating means for updating an image;
The maximum value when the variation between the position of the maximum value of each similarity image updated by the similarity image update unit and the position of the maximum value of each similarity image before the update is less than a predetermined value. A corresponding point searching apparatus for an image, comprising: a corresponding point determining means for determining a corresponding point between the input image and the reference image based on a position.

A corresponding point search program for an image for searching for a corresponding point that associates an input image with a reference image to be compared with the input image,
A similarity image for generating a plurality of similarity images aligned in the vertical and horizontal directions having the similarity between the input partial image and the reference partial image obtained by dividing the input image and the reference image into a plurality of blocks, respectively, as pixel values Generation procedure,
The maximum values of the peripheral pixels of each pixel forming the plurality of similarity images generated by the similarity image generation procedure are set in the horizontal direction (j direction), the reverse direction of the horizontal direction (−j direction), the vertical direction ( i direction), and a cumulative addition procedure that repeats a process of cumulatively adding each pixel value of the similarity image adjacent to each other in the reverse direction (−i direction) of the vertical direction,
The similarity value is obtained by cumulatively adding the maximum value of the peripheral pixels of each pixel of the similarity image that has been cumulatively added by the cumulative addition procedure to the pixel value of each pixel of the similarity image generated by the similarity image generation procedure. Similarity image update procedure for updating an image,
According to the cumulative addition procedure until the variation between the position of the maximum value of each similarity image after update updated by the similarity image update procedure and the position of the maximum value of each similarity image before update is less than a predetermined value. A corresponding point search program for an image, characterized by causing a computer to execute a corresponding point determination procedure for determining a corresponding point between the input image and a reference image by repeating cumulative addition and updating by the similarity image updating procedure.