(57)【要約】【課題】２枚の画像の間で対応する２つの領域の位置の差分に基づいて、差分の変動の影響が異なる２つの類似度を求める。【解決手段】分布生成部７１１は、第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、第１画像内の複数の領域各々と第２画像内の対応する領域との組み合わせを求める。そして、分布生成部７１１は、各組み合わせに含まれる第１画像内の第１領域の位置と第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成する。類似度生成部７１２は、第１分布情報に対して空間フィルタを適用することで第２分布情報を生成し、第１分布情報に基づいて第１画像と第２画像との間の第１類似度を求め、第２分布情報に基づいて第２類似度を求める。比較結果生成部７１３は、第１類似度と第２類似度とに基づいて、第１画像と第２画像とを比較した比較結果を生成する。【選択図】図７
2019046010.tif 000002
【特許請求の範囲】
【請求項１】
第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、前記第１画像内の複数の領域各々と前記第２画像内の対応する領域との組み合わせを求め、各組み合わせに含まれる前記第１画像内の第１領域の位置と前記第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成する分布生成部と、
前記第１分布情報に対して空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第２分布情報を生成し、前記第１分布情報に基づいて前記第１画像と前記第２画像との間の第１類似度を求め、前記第２分布情報に基づいて前記第１画像と前記第２画像との間の第２類似度を求める類似度生成部と、
前記第１類似度と前記第２類似度とに基づいて、前記第１画像と前記第２画像とを比較した比較結果を生成する比較結果生成部と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記分布生成部は、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶するメモリと、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントする加算回路とを含み、
前記類似度生成部は、
前記複数の差分範囲各々に対応する組み合わせの個数の最大値に基づいて、前記第１類似度を求める第１生成回路と、
前記複数の差分範囲各々に隣接する差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算し、加算結果を前記第２分布情報として出力するフィルタ回路と、
前記フィルタ回路が出力する組み合わせの個数の最大値に基づいて、前記第２類似度を求める第２生成回路とを含むことを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記分布生成部は、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶する複数のメモリと、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントする複数の加算回路とを含み、
前記類似度生成部は、
前記複数の差分範囲それぞれについて、前記複数のメモリが記憶する組み合わせの個数を集計する集計回路と、
前記集計回路が集計した組み合わせの個数に基づいて、前記複数の差分範囲各々に対応する組み合わせの個数の最大値を求め、前記最大値に基づいて前記第１類似度を求める第１生成回路と、
前記集計回路が集計した組み合わせの個数に基づいて、前記複数の差分範囲各々に隣接する差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算し、加算結果を前記第２分布情報として出力するフィルタ回路と、
前記フィルタ回路が出力する組み合わせの個数の最大値に基づいて、前記第２類似度を求める第２生成回路とを含むことを特徴とする請求項１記載の情報処理装置。
【請求項４】
前記比較結果生成部は、前記第１類似度と前記第２類似度とを用いて所定の演算を行うことで、前記第１画像と前記第２画像との間の第３類似度を求め、前記第３類似度に基づいて前記比較結果を生成することを特徴とする請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項５】
第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、前記第１画像内の複数の領域各々と前記第２画像内の対応する領域との組み合わせを求め、各組み合わせに含まれる前記第１画像内の第１領域の位置と前記第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成する分布生成部と、
前記第１分布情報に対して第１空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第２分布情報を生成し、前記第１分布情報に対して第２空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第３分布情報を生成し、前記第２分布情報に基づいて前記第１画像と前記第２画像との間の第１類似度を求め、前記第３分布情報に基づいて前記第１画像と前記第２画像との間の第２類似度を求める類似度生成部と、
前記第１類似度と前記第２類似度とに基づいて、前記第１画像と前記第２画像とを比較した比較結果を生成する比較結果生成部と、
を備えることを特徴とする情報処理装置。
【請求項６】
情報処理装置が、
第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、前記第１画像内の複数の領域各々と前記第２画像内の対応する領域との組み合わせを求め、
各組み合わせに含まれる前記第１画像内の第１領域の位置と前記第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成し、
前記第１分布情報に対して空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第２分布情報を生成し、
前記第１分布情報に基づいて前記第１画像と前記第２画像との間の第１類似度を求め、
前記第２分布情報に基づいて前記第１画像と前記第２画像との間の第２類似度を求め、
前記第１類似度と前記第２類似度とに基づいて、前記第１画像と前記第２画像とを比較した比較結果を生成する、
ことを特徴とする情報処理方法。
【請求項７】
第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、前記第１画像内の複数の領域各々と前記第２画像内の対応する領域との組み合わせを求め、
各組み合わせに含まれる前記第１画像内の第１領域の位置と前記第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成し、
前記第１分布情報に対して空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第２分布情報を生成し、
前記第１分布情報に基づいて前記第１画像と前記第２画像との間の第１類似度を求め、
前記第２分布情報に基づいて前記第１画像と前記第２画像との間の第２類似度を求め、
前記第１類似度と前記第２類似度とに基づいて、前記第１画像と前記第２画像とを比較した比較結果を生成する、
処理をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、及びプログラムに関する。
【背景技術】
【０００２】
データベース（database，ＤＢ）に蓄積された大量のＤＢ画像の中から目的の画像を検索する際、クエリとして入力されるクエリ画像の特徴量と各ＤＢ画像の特徴量とを比較するマッチング処理が行われる。
【０００３】
マッチング処理では、ＤＢ画像の特徴点における局所特徴量と、クエリ画像の特徴点における局所特徴量とを比較して、ＤＢ画像の特徴点に対応するクエリ画像の特徴点を探索する方法が利用される（例えば、特許文献１及び特許文献２を参照）。Binary Robust Independent Elementary Features（ＢＲＩＥＦ）と呼ばれるビット列の特徴量も知られている（例えば、非特許文献１を参照）。画像内の領域に対して空間フィルタ処理を行って、領域内の特徴量を抽出する画像処理方法も知られている（例えば、特許文献３を参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１５−２２５３５３号公報
【特許文献２】特開２０１６−１４３３６０号公報
【特許文献３】特開平９−４４６５２号公報
【非特許文献】
【０００５】
【非特許文献１】M. Calonder, V. Lepetit, C. Strecha, and P. Fua., “BRIEF: Binary Robust Independent Elementary Features”, In Proceedings of the European Conference on Computer Vision (ECCV) 2010, p.778-792, 2010
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＤＢ画像とクエリ画像との間の類似度を計算する際、ＤＢ画像内の領域の位置とクエリ画像内の対応する領域の位置との差分の変動を許容したい場合がある。この場合、ＤＢ画像とクエリ画像との間で、差分の変動の影響が異なる複数の類似度を計算すると、処理時間が長くなる。
【０００７】
なお、かかる問題は、ＤＢ画像とクエリ画像とを比較するマッチング処理に限らず、２枚の画像を比較する他の画像処理においても生ずるものである。
【０００８】
１つの側面において、本発明は、２枚の画像の間で対応する２つの領域の位置の差分に基づいて、差分の変動の影響が異なる２つの類似度を求めることを目的とする。
【課題を解決するための手段】
【０００９】
１つの案では、情報処理装置は、分布生成部、類似度生成部、及び比較結果生成部を含む。
【００１０】
分布生成部は、第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、第１画像内の複数の領域各々と第２画像内の対応する領域との組み合わせを求める。そして、分布生成部は、各組み合わせに含まれる第１画像内の第１領域の位置と第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成する。
【００１１】
類似度生成部は、第１分布情報に対して空間フィルタを適用することで、第１領域の位置と第２領域の位置との差分の分布を示す第２分布情報を生成する。そして、類似度生成部は、第１分布情報に基づいて第１画像と第２画像との間の第１類似度を求め、第２分布情報に基づいて第１画像と第２画像との間の第２類似度を求める。比較結果生成部は、第１類似度と第２類似度とに基づいて、第１画像と第２画像とを比較した比較結果を生成する。
【発明の効果】
【００１２】
１つの実施形態によれば、２枚の画像の間で対応する２つの領域の位置の差分に基づいて、差分の変動の影響が異なる２つの類似度を求めることができる。
【図面の簡単な説明】
【００１３】
【図１】マッチング処理を示す図である。
【図２】特徴点ペア計算を示す図である。
【図３】バイナリ特徴量を示す図である。
【図４】投票マップメモリを示す図である。
【図５】投票処理を示す図である。
【図６】マッチング処理の処理時間を示す図である。
【図７】情報処理装置の機能的構成図である。
【図８】画像処理のフローチャートである。
【図９】情報処理装置のハードウェア構成図である。
【図１０】ＦＰＧＡの構成図である。
【図１１】距離計算回路の構成図である。
【図１２】座標計算回路の構成図である。
【図１３】投票処理回路の構成図である。
【図１４】類似度生成回路の構成図である。
【図１５】フィルタ回路の構成図である。
【図１６】判定結果の表示画面を示す図である。
【図１７】登録処理のフローチャートである。
【図１８】検索処理のフローチャートである。
【図１９】判定処理のフローチャートである。
【図２０】空間フィルタを用いたマッチング処理の処理時間を示す図である。
【図２１】複数の投票マップメモリを含むＦＰＧＡの構成図である。
【図２２】複数の投票マップメモリを含むＦＰＧＡの投票処理回路の構成図である。
【図２３】複数の投票マップメモリを含むＦＰＧＡの類似度生成回路の構成図である。
【図２４】複数の投票マップメモリを用いた投票処理を示す図である。
【図２５】複数の投票マップメモリを用いた類似度計算を示す図である。
【図２６】複数の空間フィルタを含むフィルタ回路の構成図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照しながら、実施形態を詳細に説明する。
図１は、情報処理装置がＤＢ画像とクエリ画像とを比較するマッチング処理の例を示している。図１のマッチング処理では、データベースに蓄積された複数のＤＢ画像１０１それぞれと、画像検索のためのクエリ画像１０２とが比較され、それぞれのＤＢ画像１０１に対する類似度１０３が計算される。このマッチング処理は、特徴点ペア計算、投票処理、類似度計算、及び判定処理を含む。
【００１５】
図２は、特徴点ペア計算の例を示している。特徴点ペア計算において、まず、情報処理装置は、各画像内における特徴点配置を決定する。特徴点配置としては様々な配置が考えられるが、例えば、単純な一定間隔の格子を用いた格子状配置を用いることができる。
【００１６】
次に、情報処理装置は、各特徴点のバイナリ特徴量を計算する。特徴点のバイナリ特徴量は、その特徴点を含む所定領域内の複数の画素の画素値を用いて計算され、その所定領域内における局所的な画像特徴を表す。例えば、特徴点を含む所定領域としては矩形領域を用いることができ、バイナリ特徴量としてはＢＲＩＥＦを用いることができる。
【００１７】
次に、情報処理装置は、各ＤＢ画像１０１内の各特徴点のバイナリ特徴量と、クエリ画像１０２内のすべての特徴点のバイナリ特徴量との間のハミング距離を計算し、最も小さいハミング距離を有するクエリ画像１０２内の特徴点を選択する。そして、情報処理装置は、各ＤＢ画像１０１内の各特徴点と、選択したクエリ画像１０２内の特徴点との組み合わせ（特徴点ペア）を生成する。
【００１８】
図３は、バイナリ特徴量の例を示している。ＤＢ画像１０１内の特徴点のバイナリ特徴量３０１が“０１０１０００１”であり、クエリ画像１０２内の特徴点のバイナリ特徴量３０２が“０１１０１１００”である場合、これらのバイナリ特徴量の間のハミング距離は５である。
【００１９】
ハミング距離は、２つのビット列の間で値が異なるビット位置の個数を表す。したがって、バイナリ特徴量が１２８ビットのビット列である場合、ハミング距離の最小値は０であり、最大値は１２８である。
【００２０】
情報処理装置は、すべてのＤＢ画像１０１内のすべての特徴点に対して特徴点ペアを生成するため、生成される特徴点ペアの個数は、ＤＢ画像１０１内の特徴点の個数とＤＢ画像１０１の枚数との積で表される。
【００２１】
次に、情報処理装置は、投票結果を記憶する投票マップメモリを用いて、ＤＢ画像１０１毎に投票処理を行う。投票マップメモリは複数の投票箱を含み、各投票箱は、特徴点ペアに含まれるＤＢ画像１０１内の特徴点の位置とクエリ画像１０２内の特徴点の位置との差分の範囲（差分範囲）を表す。そして、各投票箱が記憶する投票結果は、ＤＢ画像１０１に対する特徴点ペアのうち、その投票箱が表す差分範囲に属する差分を有する特徴点ペアの個数を表す。
【００２２】
ここで、ＤＢ画像１０１の水平方向のサイズ（幅）をＷｄとし、ＤＢ画像１０１の垂直方向のサイズ（高さ）をＨｄとし、クエリ画像１０２の幅をＷｑとし、クエリ画像１０２の高さをＨｑとする。この場合、投票マップメモリの幅Ｗｍ及び高さＨｍは、次式により決定することができる。
【００２３】
Ｗｍ＝（Ｗｄ＋Ｗｑ＋Ｄ／２）／Ｄ      （１）
Ｈｍ＝（Ｈｄ＋Ｈｑ＋Ｄ／２）／Ｄ      （２）
【００２４】
式（１）及び式（２）のパラメータＤは、１以上の整数であり、投票箱が表す差分範囲を規定している。Ｄ×Ｄの矩形領域が１つの投票箱として用いられ、投票マップメモリに含まれる投票箱の個数は、Ｗｍ×Ｈｍ個である。
【００２５】
式（１）及び式（２）の除算記号“／”は、小数を切り捨てる除算を表す。したがって、式（１）の右辺は、Ｗｄ＋ＷｑをＤで除算した結果を四捨五入した値を表し、式（２）の右辺は、Ｈｄ＋ＨｑをＤで除算した結果を四捨五入した値を表す。Ｄを２以上の適当な整数に設定することで、投票メモリマップのリソースを削減することができるとともに、特徴点ペアが有する差分のばらつきを吸収することができる。
【００２６】
投票処理において、まず、情報処理装置は、投票マップメモリのすべての投票箱の投票結果を０に初期化する。次に、情報処理装置は、各特徴点ペアに含まれるＤＢ画像１０１内の特徴点の座標（Ｘｄ，Ｙｄ）と、クエリ画像１０２内の特徴点の座標（Ｘｑ，Ｙｑ）との差分から、投票マップメモリ内における投票箱の座標（Ｐｘ，Ｐｙ）を、次式により計算する。
【００２７】
Ｐｘ＝（Ｘｑ−Ｘｄ＋（Ｗｄ−１）＋Ｄ／２）／Ｄ      （３）
Ｐｙ＝（Ｙｑ−Ｙｄ＋（Ｈｄ−１）＋Ｄ／２）／Ｄ      （４）
【００２８】
ＤＢ画像１０１において、ＤＢ画像１０１の左上頂点がＸＹ座標系の原点に対応し、Ｘ軸は水平方向を表し、Ｙ軸は垂直方向を表す。クエリ画像１０２において、クエリ画像１０２の左上頂点がＸＹ座標系の原点に対応し、Ｘ軸は水平方向を表し、Ｙ軸は垂直方向を表す。したがって、式（３）のＰｘは、Ｘ座標の差分Ｘｑ−Ｘｄが属する差分範囲を示しており、式（４）のＰｙは、Ｙ座標の差分Ｙｑ−Ｙｄが属する差分範囲を示している。以下では、投票箱の座標（Ｐｘ，Ｐｙ）を投票点座標と記すことがある。
【００２９】
式（３）の右辺において、Ｘｑ−ＸｄにＷｄ−１を加算することで、Ｗｑ＝Ｗｄであり、かつ、Ｘｑ−Ｘｄ＝０である場合に、Ｐｘが投票マップメモリの水平方向における中央の投票箱を示す値になる。同様に、式（４）の右辺において、Ｙｑ−ＹｄにＨｄ−１を加算することで、Ｈｑ＝Ｈｄであり、かつ、Ｙｑ−Ｙｄ＝０である場合に、Ｐｙが投票マップメモリの垂直方向における中央の投票箱を示す値になる。
【００３０】
情報処理装置は、投票マップメモリにおいて、投票点座標（Ｐｘ，Ｐｙ）が表す位置の投票箱の投票結果を１だけインクリメントすることで、その投票箱の投票結果を更新する。
【００３１】
ここで、図２のＤＢ画像１０１内の特徴点２０１と、クエリ画像１０２内の特徴点２０２とが、特徴点ペアを形成している場合を想定する。Ｗｄ＝Ｗｑ＝Ｈｄ＝Ｈｑ＝２００であり、Ｄ＝８であり、特徴点２０１の座標（Ｘｄ，Ｙｄ）が（１２０，１０２）であり、特徴点２０２の座標（Ｘｑ，Ｙｑ）が（１５０，１０２）である場合、（Ｐｘ，Ｐｙ）は、次式により計算される。
【００３２】
Ｐｘ＝（１２０−１５０＋（２００−１）＋８／２）／８＝２１      （５）
Ｐｙ＝（１０２−１０２＋（２００−１）＋８／２）／８＝２５      （６）
【００３３】
この場合、（２１，２５）が表す位置の投票箱の投票結果が１だけインクリメントされる。
【００３４】
図４は、投票マップメモリの例を示している。図４（ａ）は、１枚のＤＢ画像１０１の最初の特徴点ペアを用いた投票結果を示している。図４（ａ）では、投票マップメモリの中央の投票箱４０１の投票結果が０から１に更新されている。
【００３５】
図４（ｂ）は、１枚のＤＢ画像１０１のすべての特徴点ペアを用いた投票結果を示している。図４（ｂ）では、投票マップメモリの複数の投票箱の投票結果がインクリメントされており、投票箱４０１の投票結果は８８に更新されている。図４（ｂ）が示す投票結果は、ＤＢ画像１０１内において、それぞれの特徴点ペアが有する座標差分の分布を表すヒストグラムに相当する。
【００３６】
類似度計算において、情報処理装置は、各ＤＢ画像１０１に対してそれぞれの投票箱が記憶する投票結果の最大値を、そのＤＢ画像１０１とクエリ画像１０２との間の類似度として抽出する。
【００３７】
判定処理において、情報処理装置は、類似度に基づいて各ＤＢ画像１０１とクエリ画像１０２とを比較した比較結果を判定する。例えば、情報処理装置は、類似度が閾値以上である場合、ＤＢ画像１０１がクエリ画像１０２と類似していると判定し、類似度が閾値未満である場合、ＤＢ画像１０１がクエリ画像１０２と類似していないと判定して、判定結果を出力する。情報処理装置は、類似度が大きなものから順番に所定枚数のＤＢ画像１０１を判定結果として出力することもできる。
【００３８】
ところで、マッチング処理では、ＤＢ画像１０１とクエリ画像１０２に写っている物体の形状の多少の変動を許容しながら、それらの画像を比較したい場合もある。この場合、各特徴点ペアについて、座標差分が属する単一の投票箱に投票するのではなく、その周囲の複数の投票箱にも投票することが有効であると考えられる。
【００３９】
図５は、投票処理の例を示している。図５（ａ）は、単一の投票箱に投票する投票処理を示している。図５（ａ）では、座標差分が属する投票箱５０１の投票結果が０から１に更新されている。
【００４０】
一方、図５（ｂ）は、複数の投票箱に投票する投票処理を示している。図５（ｂ）では、座標差分が属する投票箱５０１とその周囲の８個の投票箱の投票結果が０から１に更新されている。
【００４１】
例えば、投票マップメモリとして２ポート（１Ｒ１Ｗ）のメモリを用いた場合、座標差分が属する投票箱を含むＮ×Ｎ個（Ｎは３以上の奇数）の投票箱に投票すると、投票マップメモリに対するアクセスの回数がＮ＾２回になる。このため、マッチング処理の速度が低下する。
【００４２】
図６は、単一の投票箱に投票する投票処理と複数の投票箱に投票する投票処理とを併用するマッチング処理の処理時間の例を示している。まず、情報処理装置は、単一の投票箱に投票する投票処理を用いて検索処理６０１を行い、検索処理６０１の結果を判定する判定処理６０２を行う。検索処理６０１では、物体の形状の変動を許容することなく、クエリ画像１０２に類似するＤＢ画像１０１が検索される。
【００４３】
次に、情報処理装置は、複数の投票箱に投票する投票処理を用いて検索処理６０３を行い、検索処理６０３の結果を判定する判定処理６０４を行う。検索処理６０３では、物体の形状の変動を許容しながら、クエリ画像１０２に類似するＤＢ画像１０１が検索される。
【００４４】
検索処理６０１及び検索処理６０３は、特徴点ペア計算、投票処理、及び類似度計算を含む。図６のマッチング処理では、検索処理６０１に続いて、より長い時間のかかる検索処理６０３が行われるため、マッチング処理の処理時間は、検索処理６０１の処理時間の２倍以上になる。
【００４５】
図７は、実施形態の情報処理装置の機能的構成例を示している。図７の情報処理装置７０１は、分布生成部７１１、類似度生成部７１２、及び比較結果生成部７１３を含む。
【００４６】
図８は、図７の情報処理装置７０１が行う画像処理の例を示すフローチャートである。まず、分布生成部７１１は、第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、第１画像内の複数の領域各々と第２画像内の対応する領域との組み合わせを求める（ステップ８０１）。
【００４７】
次に、分布生成部７１１は、各組み合わせに含まれる第１画像内の第１領域の位置と第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成する（ステップ８０２）。
【００４８】
次に、類似度生成部７１２は、第１分布情報に対して空間フィルタを適用することで、第１領域の位置と第２領域の位置との差分の分布を示す第２分布情報を生成する（ステップ８０３）。
【００４９】
次に、類似度生成部７１２は、第１分布情報に基づいて第１画像と第２画像との間の第１類似度を求め（ステップ８０４）、第２分布情報に基づいて第１画像と第２画像との間の第２類似度を求める（ステップ８０５）。
【００５０】
そして、比較結果生成部７１３は、第１類似度と第２類似度とに基づいて、第１画像と第２画像とを比較した比較結果を生成する（ステップ８０６）。
【００５１】
図７の情報処理装置７０１によれば、２枚の画像の間で対応する２つの領域の位置の差分に基づいて、差分の変動の影響が異なる２つの類似度を求めることができる。
【００５２】
図９は、図７の情報処理装置７０１のハードウェア構成例を示している。図９の情報処理装置７０１は、Central Processing Unit（ＣＰＵ）９０１、メモリ９０２、入力装置９０３、出力装置９０４、補助記憶装置９０５、媒体駆動装置９０６、及びネットワーク接続装置９０７を含む。情報処理装置７０１は、さらにField-Programmable Gate Array（ＦＰＧＡ）９０８を含む。これらの構成要素はバス９０９により互いに接続されている。
【００５３】
メモリ９０２は、例えば、Read Only Memory（ＲＯＭ）、Random Access Memory（ＲＡＭ）、フラッシュメモリ等の半導体メモリであり、処理に用いられるプログラム及びデータを記憶する。
【００５４】
ＣＰＵ９０１（プロセッサ）は、例えば、メモリ９０２を利用してプログラムを実行することにより、複数のＤＢ画像とクエリ画像とを比較するマッチング処理を行う。例えば、ＤＢ画像は第１画像に対応し、クエリ画像は第２画像に対応する。
【００５５】
マッチング処理において、ＣＰＵ９０１は、複数のＤＢ画像の中からクエリ画像と類似するＤＢ画像を検索する。まず、ＣＰＵ９０１は、ＤＢ画像及びクエリ画像から各特徴点の座標及び特徴量を計算し、計算した特徴点の座標及び特徴量をデータベースとしてメモリ９０２に格納する。特徴点の特徴量としては、その特徴点を含む所定領域の局所的な画像特徴を表すバイナリ特徴量を用いることができる。
【００５６】
次に、ＣＰＵ９０１は、特徴点の座標及び特徴量をメモリ９０２からＦＰＧＡ９０８へ転送し、各ＤＢ画像とクエリ画像との間の複数の類似度をＦＰＧＡ９０８から受信する。これらの類似度には、第１類似度及び第２類似度が含まれる。ＣＰＵ９０１は、特徴点の座標及び特徴量を補助記憶装置９０５に格納してもよい。
【００５７】
マッチング処理において、ＣＰＵ９０１は、図７の比較結果生成部７１３としても動作し、各ＤＢ画像とクエリ画像とを比較した比較結果を生成する。このとき、ＣＰＵ９０１は、各ＤＢ画像に対する複数の類似度から類似度スコアを計算し、類似度スコアに基づいて、そのＤＢ画像がクエリ画像に類似しているか否かを判定する。
【００５８】
入力装置９０３は、例えば、キーボード、ポインティングデバイス等であり、ユーザ又はオペレータからの指示又は情報の入力に用いられる。出力装置９０４は、例えば、表示装置、プリンタ、スピーカ等であり、ユーザ又はオペレータへの問い合わせ及び処理結果の出力に用いられる。処理結果には、各ＤＢ画像とクエリ画像とを比較した比較結果が含まれる。
【００５９】
補助記憶装置９０５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。補助記憶装置９０５は、ハードディスクドライブであってもよい。情報処理装置は、補助記憶装置９０５にプログラム及びデータを格納しておき、それらをメモリ９０２にロードして使用することができる。補助記憶装置９０５が記憶するデータには、ＤＢ画像及びクエリ画像が含まれる。
【００６０】
媒体駆動装置９０６は、可搬型記録媒体９１０を駆動し、その記録内容にアクセスする。可搬型記録媒体９１０は、メモリデバイス、フレキシブルディスク、光ディスク、光磁気ディスク等である。可搬型記録媒体９１０は、Compact Disk Read Only Memory（ＣＤ−ＲＯＭ）、Digital Versatile Disk（ＤＶＤ）、又はUniversal Serial Bus（ＵＳＢ）メモリであってもよい。
【００６１】
ユーザ又はオペレータは、可搬型記録媒体９１０にプログラム及びデータを記録しておき、それらをメモリ９０２にロードして使用することができる。また、ユーザ又はオペレータは、可搬型記録媒体９１０にＦＰＧＡ９０８のためのプログラムを記録しておき、そのプログラムを用いてＦＰＧＡ９０８の再構成を行うこともできる。
【００６２】
このように、処理に用いられるプログラム及びデータを格納するコンピュータ読み取り可能な記録媒体には、メモリ９０２、補助記憶装置９０５、及び可搬型記録媒体９１０のような、物理的な（非一時的な）記録媒体が含まれる。
【００６３】
ネットワーク接続装置９０７は、Local Area Network（ＬＡＮ）、Wide Area Network（ＷＡＮ）等の通信ネットワークに接続され、通信に伴うデータ変換を行う通信インタフェース回路である。情報処理装置は、プログラム及びデータを外部の装置からネットワーク接続装置９０７を介して受信し、それらをメモリ９０２にロードして使用することができる。また、情報処理装置は、ＦＰＧＡ９０８のためのプログラムを外部の装置からネットワーク接続装置９０７を介して受信し、そのプログラムを用いてＦＰＧＡ９０８の再構成を行うこともできる。
【００６４】
ＦＰＧＡ９０８は、図７の分布生成部７１１及び類似度生成部７１２として動作し、ＣＰＵ９０１から受信した特徴点の座標及び特徴量を用いて、特徴点ペア計算、投票処理、及び類似度計算を行う。そして、各ＤＢ画像に対する複数の類似度をＣＰＵ９０１へ転送する。
【００６５】
図１０は、図９のＦＰＧＡ９０８の構成例を示している。図１０のＦＰＧＡ９０８は、制御回路１００１、距離計算回路１００２、投票処理回路１００３、投票マップメモリ１００４、及び類似度生成回路１００５を含む。投票処理回路１００３及び投票マップメモリ１００４は、分布生成部７１１に対応し、類似度生成回路１００５は、類似度生成部７１２に対応する。
【００６６】
制御回路１００１は、バス９０９を介してＣＰＵ９０１と通信し、ＦＰＧＡ９０８の起動制御及び停止制御を行う。また、制御回路１００１は、距離計算回路１００２、投票処理回路１００３、及び類似度生成回路１００５の制御も行う。
【００６７】
距離計算回路１００２は、ＤＢ画像及びクエリ画像の各特徴点の座標及び特徴量をメモリ９０２から読み出し、距離計算を行って特徴点ペアを生成する。そして、距離計算回路１００２は、特徴点ペアに含まれるＤＢ画像内の特徴点の座標とクエリ画像内の特徴点の座標との座標差分から投票点座標を計算し、計算した投票点座標を投票処理回路１００３へ出力する。
【００６８】
投票処理回路１００３は、距離計算回路１００２が出力する投票点座標に基づき、投票マップメモリ１００４を用いた投票処理を行い、投票マップメモリ１００４は、投票点座標が示す投票箱毎に、投票結果を記憶する。
【００６９】
類似度生成回路１００５は、投票マップメモリ１００４が記憶する投票結果から、各ＤＢ画像とクエリ画像との間の複数の類似度を求めて、それらの類似度をＣＰＵ９０１へ転送する。
【００７０】
距離計算回路１００２と投票処理回路１００３は同時に動作し、投票処理回路１００３と類似度生成回路１００５は、投票マップメモリ１００４に対して排他動作を行う。投票マップメモリ１００４は、不図示のセレクタを介してアクセスされる２ポート（１Ｒ１Ｗ）のメモリであり、投票処理回路１００３からの１Ｒ１Ｗアクセス、又は類似度生成回路１００５からの１Ｒアクセスのいずれかを許容する。
【００７１】
図１１は、図１０の距離計算回路１００２の構成例を示している。図１１の距離計算回路１００２は、メモリ１１０１、リード回路１１０２、リード回路１１０３、及び座標計算回路１１０４−１〜座標計算回路１１０４−６を含む。
【００７２】
リード回路１１０２は、バス９０９を介してメモリ９０２から、クエリ画像内の特徴点の座標及び特徴量を読み出し、読み出した座標及び特徴量をメモリ１１０１に格納する。メモリ１１０１は、１枚のクエリ画像に含まれるすべての特徴点の座標及び特徴量を記憶する。
【００７３】
リード回路１１０３は、バス９０９を介してメモリ９０２から、ＤＢ画像内の特徴点の座標及び特徴量を読み出し、読み出した座標及び特徴量を座標計算回路１１０４−１〜座標計算回路１１０４−６へ順番に出力する。
【００７４】
例えば、各特徴点の座標は３２ビットで表され、各特徴点の特徴量は１２８ビットで表される。この場合、メモリ１１０１と各座標計算回路１１０４−ｉ（ｉ＝１〜６）との間には、４個の特徴点の座標及び特徴量を同時に転送可能なデータバスが設けられる。このデータバスのバス幅ＢＷは、次式により計算される。
【００７５】
ＢＷ＝３２ビット×４＋１２８ビット×４
＝６４０ビット                              （１１）
【００７６】
一方、リード回路１１０３と各座標計算回路１１０４−ｉとの間には、１６個の特徴点の座標及び特徴量を同時に転送可能なデータバスが設けられる。このデータバスのバス幅ＢＷは、次式により計算される。
【００７７】
ＢＷ＝３２ビット×１６＋１２８ビット×１６
＝２５６０ビット                            （１２）
【００７８】
座標計算回路１１０４−１〜座標計算回路１１０４−６は、ＤＢ画像内の特徴点とクエリ画像内の特徴点との間の距離計算を並列に実行する。まず、座標計算回路１１０４−ｉは、メモリ１１０１からクエリ画像内の特徴点の座標及び特徴量を読み出し、リード回路１１０３からＤＢ画像内の特徴点の座標及び特徴量を受信する。
【００７９】
次に、座標計算回路１１０４−ｉは、ＤＢ画像内の各特徴点に対してクエリ画像内のすべての特徴点を走査して、特徴量の距離が最小となるクエリ画像内の特徴点を求め、ＤＢ画像内の特徴点とクエリ画像内の特徴点との特徴点ペアを生成する。そして、座標計算回路１１０４−ｉは、特徴点ペアに含まれる２つの特徴点の座標差分から投票点座標を計算する。
【００８０】
座標計算回路１１０４−ｉは、ＤＢ画像内の１６個の特徴点の座標及び特徴量を受信すると、クエリ画像内のすべての特徴点を走査して、１６個の特徴点それぞれに対する投票点座標を出力する。したがって、各座標計算回路１１０４−ｉは、１回の座標計算処理を行う度に１６個の投票点座標を出力し、座標計算回路１１０４−１〜座標計算回路１１０４−６は、併せて９６個の投票点座標を出力する。座標計算回路１１０４−１〜座標計算回路１１０４−６が座標計算処理を複数回繰り返すことで、ＤＢ画像内のすべての特徴点に対する投票点座標が生成される。
【００８１】
例えば、各投票点座標は式（３）のＰｘ及び式（４）のＰｙで表され、Ｐｘ及びＰｙはそれぞれ１６ビットで表される。この場合、各投票点座標は３２ビットで表され、１６個の投票点座標は５１２ビットで表される。
【００８２】
図１２は、図１１の座標計算回路１１０４−ｉの構成例を示している。図１２の座標計算回路１１０４−ｉは、ＤＢ画像内の１６個の特徴点それぞれに対する投票点座標を求める走査回路１２０１−１〜走査回路１２０１−１６を含む。各走査回路１２０１−ｊ（ｊ＝１〜１６）は、ＤＢ画像内の１個の特徴点に対して、クエリ画像内の特徴点を４個ずつ走査する。
【００８３】
走査回路１２０１−ｊは、ＸＯＲ回路１２１１−１〜ＸＯＲ回路１２１１−４、カウント回路１２１２−１〜カウント回路１２１２−４、探索回路１２１３、更新回路１２１４、選択回路１２１５、及び計算回路１２１６を含む。
【００８４】
ＸＯＲ回路１２１１−ｋ（ｋ＝１〜４）は、ＤＢ画像内の特徴点の特徴量とクエリ画像内の特徴点の特徴量との排他的論理和を計算し、カウント回路１２１２−ｋへ出力する。特徴量が１２８ビットで表される場合、ＸＯＲ回路１２１１−ｋは、１２８個の排他的論理和を出力する。カウント回路１２１２−ｋは、ＸＯＲ回路１２１１−ｋが出力する排他的論理和のうち論理“１”を示すビット値の個数をカウントして、カウント結果を探索回路１２１３へ出力する。カウント結果は、ＤＢ画像内の特徴点の特徴量とクエリ画像内の特徴点の特徴量との間のハミング距離を表している。
【００８５】
探索回路１２１３は、カウント回路１２１２−１〜カウント回路１２１２−４がカウント結果を出力する度に、４個のカウント結果の最小値を求めて更新回路１２１４へ出力する。探索回路１２１３は、座標計算回路１１０４−ｉがクエリ画像内の４個の特徴点の座標及び特徴量を受信する度に、最小値を出力する。選択回路１２１５は、探索回路１２１３が出力する最小値に対応する、クエリ画像内の特徴点の座標を選択して、計算回路１２１６へ出力する。
【００８６】
更新回路１２１４は、探索回路１２１３が出力する最小値を保持し、探索回路１２１３が新たな最小値を出力する度に、保持している最小値と新たな最小値とを比較する。そして、新たな最小値の方が小さい場合、更新回路１２１４は、保持している最小値を新たな最小値に書き換える。これにより、座標計算回路１１０４−ｉがクエリ画像内の４個の特徴点の座標及び特徴量を受信する度に、更新回路１２１４が保持する最小値が更新される。
【００８７】
座標計算回路１１０４−ｉがクエリ画像内のすべての特徴点の座標及び特徴量を受信したとき、計算回路１２１６は、更新回路１２１４が保持する最小値に対応する、クエリ画像内の特徴点の座標を選択する。これにより、走査回路１２０１−ｊの処理対象であるＤＢ画像内の特徴点と、選択されたクエリ画像内の特徴点とからなる、特徴点ペアが生成される。そして、計算回路１２１６は、特徴点ペアに含まれる２つの特徴点の座標を用いて、式（３）及び式（４）により投票点座標（Ｐｘ，Ｐｙ）を計算する。
【００８８】
図１３は、図１０の投票処理回路１００３の構成例を示している。図１３の投票処理回路１００３は、選択回路１３０１及び加算回路１３０２を含む。選択回路１３０１は、距離計算回路１００２の座標計算回路１１０４−１〜座標計算回路１１０４−６が出力する９６個の投票点座標を順番に選択して、投票マップメモリ１００４のアクセス対象アドレスとして出力する。
【００８９】
加算回路１３０２は、選択回路１３０１が選択した投票点座標の投票結果を投票マップメモリ１００４から読み出し、読み出した投票結果に１を加算して、加算結果を同じ投票点座標に書き込む。これにより、投票点座標が選択される度に、その投票点座標の投票結果が１だけインクリメントされる。
【００９０】
距離計算回路１００２は、９６個の投票点座標を出力してからある程度の時間が経過した後に、次の９６個の投票点座標を出力する。座標計算回路１１０４−ｉはクエリ画像内の特徴点を４個ずつ走査するため、クエリ画像内の特徴点の個数をＮＱとすると、距離計算回路１００２が投票点座標を出力する時間間隔Ｔ（単位はＦＰＧＡ９０８のクロックサイクル）は、次式により計算される。
【００９１】
Ｔ＝ＮＱ／４      （１３）
【００９２】
したがって、式（１３）が示す時間間隔Ｔ内に、投票処理回路１００３が９６個の投票点座標に対する投票処理を完了すれば、待ち時間が発生せず、高いハードウェア処理性能が実現される。
【００９３】
こうして、距離計算回路１００２がＤＢ画像内のすべての特徴点に対する投票点座標を出力すると、それらの投票点座標に対する投票処理が終了する。このとき、投票マップメモリ１００４内には、ＤＢ画像内の特徴点の座標とクエリ画像内の特徴点の座標との座標差分の分布を示す投票結果が格納されている。この投票結果は、第１分布情報に対応する。
【００９４】
図１４は、図１０の類似度生成回路１００５の構成例を示している。図１４の類似度生成回路１００５は、フィルタ回路１４０１、生成回路１４０２、生成回路１４０３、及びライト回路１４０４を含む。
【００９５】
フィルタ回路１４０１は、投票マップメモリ１００４が記憶する投票結果に対してＭ×Ｍ（Ｍは３以上の奇数）の空間フィルタを適用することで、ＤＢ画像内の特徴点の座標とクエリ画像内の特徴点の座標との差分の変動を許容する投票結果を生成する。これにより、例えば、ＤＢ画像とクエリ画像に写っている物体の形状の変動を許容する投票結果が生成される。フィルタ回路１４０１が生成する投票結果は、第２分布情報に対応する。
【００９６】
そして、フィルタ回路１４０１は、空間フィルタを適用した投票結果を順番に生成回路１４０２へ出力し、空間フィルタを適用していない投票結果を順番に生成回路１４０３へ出力する。
【００９７】
生成回路１４０２は、レジスタ１４１１、更新回路１４１２、及びレジスタ１４１３を含み、空間フィルタを適用した投票結果から、ＤＢ画像とクエリ画像との間の類似度ＭＡを求める。
【００９８】
レジスタ１４１１は、各投票点座標の投票結果を記憶し、更新回路１４１２は、レジスタ１４１１が記憶する投票結果をレジスタ１４１３に書き込む。更新回路１４１２は、レジスタ１４１３に先に書き込まれた投票結果と、レジスタ１４１１が記憶する投票結果とを比較し、レジスタ１４１１が記憶する投票結果の方が大きい場合に、その投票結果をレジスタ１４１３に上書きする。これにより、すべての投票結果の最大値が、類似度ＭＡとしてレジスタ１４１３に書き込まれる。
【００９９】
一方、生成回路１４０３は、レジスタ１４２１、更新回路１４２２、及びレジスタ１４２３を含み、空間フィルタを適用していない投票結果から、ＤＢ画像とクエリ画像との間の類似度ＭＢを求める。レジスタ１４２１、更新回路１４２２、及びレジスタ１４２３は、レジスタ１４１１、更新回路１４１２、及びレジスタ１４１３と同様に動作し、すべての投票結果の最大値が、類似度ＭＢとしてレジスタ１４２３に書き込まれる。
【０１００】
ライト回路１４０４は、レジスタ１４１３及びレジスタ１４２３から、それぞれ、類似度ＭＡ及び類似度ＭＢを読み出して、ＣＰＵ９０１へ転送する。
【０１０１】
図１５は、図１４のフィルタ回路１４０１の構成例を示している。図１５のフィルタ回路１４０１は、ＦＦ１〜ＦＦ９、ラインバッファ１５０１、ラインバッファ１５０２、及び加算回路１５０３を含み、３×３の空間フィルタ演算を行う。
【０１０２】
ＦＦ１〜ＦＦ９は、フリップフロップ回路であり、投票マップメモリ１００４が記憶する各投票点座標の投票結果を保持する。ＦＦ１は、投票マップメモリ１００４が出力する１個の投票結果をラッチして、ＦＦ２へ出力する。ＦＦ２は、ＦＦ１が出力する投票結果をラッチして、ＦＦ３へ出力する。ＦＦ３は、ＦＦ２が出力する投票結果をラッチして、ラインバッファ１５０１へ出力する。
【０１０３】
ラインバッファ１５０１は、Ｗｍ−３個の投票結果を保持し、それらの投票結果を１個ずつＦＦ４へ出力する。Ｗｍは投票マップメモリ１００４の幅を表し、式（１）により与えられる。
【０１０４】
ＦＦ４は、ラインバッファ１５０１が出力する１個の投票結果をラッチして、ＦＦ５へ出力する。ＦＦ５は、ＦＦ４が出力する投票結果をラッチして、ＦＦ６へ出力する。ＦＦ６は、ＦＦ５が出力する投票結果をラッチして、ラインバッファ１５０２へ出力する。
【０１０５】
ラインバッファ１５０２は、Ｗｍ−３個の投票結果を保持し、それらの投票結果を１個ずつＦＦ７へ出力する。ＦＦ８は、ＦＦ７が出力する投票結果をラッチして、ＦＦ９へ出力する。ＦＦ９は、ＦＦ８が出力する投票結果をラッチする。
【０１０６】
したがって、ＦＦ１〜ＦＦ３及びラインバッファ１５０１が投票マップメモリ１００４の特定の行の投票結果を保持しているとき、ＦＦ４〜ＦＦ６及びラインバッファ１５０２は、その行に隣接する行の投票結果を保持している。また、ＦＦ１〜ＦＦ４及びＦＦ６〜ＦＦ９は、ＦＦ５が保持している投票結果に対応する投票点座標に隣接する、８個の投票点座標の投票結果を保持している。
【０１０７】
加算回路１５０３は、ＦＦ１〜ＦＦ９が保持している９個の投票結果を加算することで、ＦＦ５が保持する投票結果に対して３×３の空間フィルタを適用した場合の投票結果を生成する。これにより、図５（ｂ）の投票箱５０１とその周囲の８個の投票箱に同時に投票する投票処理と等価な投票結果が得られる。そして、加算回路１５０３は、加算結果が表す投票結果を生成回路１４０２へ出力する。
【０１０８】
さらに、フィルタ回路１４０１は、ＦＦ５が保持する投票結果をそのまま生成回路１４０３へ出力する。この投票結果は、空間フィルタを適用していない投票結果に対応する。
【０１０９】
ＣＰＵ９０１は、各ＤＢ画像に対する類似度ＭＡ及び類似度ＭＢを類似度生成回路１００５から受信し、類似度ＭＡ及び類似度ＭＢを用いて所定の演算を行うことで、類似度スコアＳを求める。例えば、ＣＰＵ９０１は、次式により類似度スコアＳを計算することができる。
【０１１０】
Ｓ＝ＭＡ×Ｐ＋ＭＢ×（１−Ｐ）      （１４）
【０１１１】
式（１４）のパラメータＰは、０以上１以下の実数であり、ＤＢ画像内の特徴点の座標とクエリ画像内の特徴点の座標との差分の変動に対する許容度を表す。パラメータＰが小さいほど、差分の変動を許容しないことを示し、パラメータＰが大きいほど、差分の変動を許容することを示す。Ｐ＝０の場合、ＳはＭＢと一致し、Ｐ＝１の場合、ＳはＭＡと一致する。パラメータＰは、ユーザが指定することができる。
【０１１２】
そして、ＣＰＵ９０１は、類似度スコアＳに基づいて、ＤＢ画像がクエリ画像に類似しているか否かを判定し、出力装置９０４の画面に判定結果を表示する。例えば、ＣＰＵ９０１は、類似度スコアＳが閾値以上である場合、ＤＢ画像がクエリ画像と類似していると判定し、類似度スコアＳが閾値未満である場合、ＤＢ画像がクエリ画像と類似していないと判定する。ＣＰＵ９０１は、類似度スコアＳが大きなものから順番に所定枚数のＤＢ画像を判定結果として表示することもできる。
【０１１３】
図１６は、判定結果の表示画面の例を示している。図１６の表示画面は、パラメータＰを調整するためのスライダ１６０３及び検索ボタン１６０４を含む。ユーザは、クエリ画像１６０１を指定し、スライダ１６０３を操作してパラメータＰを指定して、検索ボタン１６０４をクリックする。これにより、情報処理装置７０１は、マッチング処理を行って、類似度スコアＳが上位の所定枚数のＤＢ画像１６０２を表示する。
【０１１４】
情報処理装置７０１は、各ＤＢ画像の類似度ＭＡ及び類似度ＭＢをメモリ９０２に保存しておき、ユーザによってパラメータＰが変更された場合、直ちに各ＤＢ画像の類似度スコアＳを再計算して、ＤＢ画像１６０２の表示を更新する。検索処理の時間と比較して、類似度スコアＳの再計算の時間は十分に短い。したがって、パラメータＰに基づいて類似度スコアＳを変更することで、判定結果の表示画面において、差分の変動を許容するか否かをリアルタイムに変更することができる。
【０１１５】
図１７は、検索処理の事前準備として、ＤＢ画像を情報処理装置７０１に登録する登録処理の例を示すフローチャートである。まず、ユーザは、登録対象のＤＢ画像を情報処理装置７０１に入力し（ステップ１７０１）、ＣＰＵ９０１は、入力されたＤＢ画像から各特徴点の特徴量を計算する（ステップ１７０２）。そして、ＣＰＵ９０１は、各特徴点の座標及び特徴量を、メモリ９０２又は補助記憶装置９０５内のデータベースに登録する（ステップ１７０３）。
【０１１６】
次に、ＣＰＵ９０１は、登録対象のすべてのＤＢ画像を処理したか否かをチェックし（ステップ１７０４）、未処理のＤＢ画像が残っている場合（ステップ１７０４，ＮＯ）、次のＤＢ画像についてステップ１７０１以降の処理を繰り返す。そして、すべてのＤＢ画像を処理した場合（ステップ１７０４，ＹＥＳ）、ＣＰＵ９０１は、処理を終了する。
【０１１７】
図１８は、マッチング処理における検索処理の例を示すフローチャートである。まず、ユーザは、クエリ画像を情報処理装置７０１に入力し（ステップ１８０１）、ＣＰＵ９０１は、入力されたクエリ画像から各特徴点の特徴量を計算する（ステップ１８０２）。
【０１１８】
次に、ＦＰＧＡ９０８の距離計算回路１００２は、データベースから処理対象のＤＢ画像を選択して（ステップ１８０３）、特徴点ペア計算を行う（ステップ１８０４）。そして、投票処理回路１００３は、投票処理を行い（ステップ１８０５）、類似度生成回路１００５は、類似度計算を行う（ステップ１８０６）。
【０１１９】
次に、距離計算回路１００２は、処理対象のすべてのＤＢ画像を処理したか否かをチェックし（ステップ１８０７）、未処理のＤＢ画像が残っている場合（ステップ１８０７，ＮＯ）、次のＤＢ画像についてステップ１８０３以降の処理を繰り返す。そして、すべてのＤＢ画像を処理した場合（ステップ１８０７，ＹＥＳ）、ＦＰＧＡ９０８は、処理を終了する。
【０１２０】
図１９は、マッチング処理における判定処理の例を示すフローチャートである。まず、ユーザは、パラメータＰを情報処理装置７０１に入力する（ステップ１９０１）。そして、ＣＰＵ９０１は、ＦＰＧＡ９０８が計算したＤＢ画像の類似度ＭＡ及び類似度ＭＢを取得して（ステップ１９０２）、式（１４）により類似度スコアＳを計算する（ステップ１９０３）。
【０１２１】
次に、ＣＰＵ９０１は、すべてのＤＢ画像の類似度スコアＳを計算したか否かをチェックし（ステップ１９０４）、未処理のＤＢ画像が残っている場合（ステップ１９０４，ＮＯ）、次のＤＢ画像についてステップ１９０２以降の処理を繰り返す。そして、すべてのＤＢ画像の類似度スコアＳを計算した場合（ステップ１９０４，ＹＥＳ）、ＣＰＵ９０１は、類似度スコアＳが上位の所定枚数のＤＢ画像を画面に表示する（ステップ１９０５）。
【０１２２】
図２０は、空間フィルタを用いたマッチング処理の処理時間の例を示している。情報処理装置７０１は、検索処理２００１を行った後、判定処理２００２を行う。検索処理２００１では、図１８の検索処理が行われ、判定処理２００２では、図１９の判定処理が行われる。この場合、１回の検索処理２００１によって、差分の変動を許容する類似度ＭＡと差分の変動を許容しない類似度ＭＢの両方が得られるため、図６のマッチング処理の半分以下の処理時間で、マッチング処理が終了する。
【０１２３】
このように、図９の情報処理装置７０１によれば、投票結果に対して空間フィルタを適用することで、１回の検索処理によって差分の変動の影響が異なる２つの類似度を求めることができ、マッチング処理の処理時間が削減される。また、ＦＰＧＡ９０８のハードウェアを用いて検索処理を実行することで、マッチング処理がさらに高速化される。
【０１２４】
ところで、図１０のＦＰＧＡ９０８では、単一の投票マップメモリ１００４を用いて投票処理が行われるが、複数の投票マップメモリを用いて投票処理を高速化することも可能である。
【０１２５】
図２１は、複数の投票マップメモリを含むＦＰＧＡ９０８の構成例を示している。図２１のＦＰＧＡ９０８は、制御回路１００１、距離計算回路１００２、投票処理回路２１０１、投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４、及び類似度生成回路２１０３を含む。投票処理回路２１０１及び投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４は、分布生成部７１１に対応し、類似度生成回路２１０３は、類似度生成部７１２に対応する。
【０１２６】
制御回路１００１及び距離計算回路１００２の動作は、図９の場合と同様である。投票処理回路２１０１は、投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４を用いて投票処理を並列に行う。そして、類似度生成回路２１０３は、投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４が記憶する投票結果から、各ＤＢ画像とクエリ画像との間の複数の類似度を求める。
【０１２７】
投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４内における投票箱の位置は、それらの投票マップメモリに共通する投票点座標によって記述される。そして、投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４は、同じ投票点座標に対する投票結果を分散して記憶する。
【０１２８】
図２２は、図２１の投票処理回路２１０１の構成例を示している。図２２の投票処理回路２１０１は、選択回路２２０１及び加算回路２２０２−１〜加算回路２２０２−４を含む。選択回路２２０１は、距離計算回路１００２の座標計算回路１１０４−１〜座標計算回路１１０４−６が出力する９６個の投票点座標の中から４個の投票点座標を選択する。そして、選択回路２２０１は、それらの４個の投票点座標を、それぞれ、投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４のアクセス対象アドレスとして出力する。
【０１２９】
加算回路２２０２−ｒ（ｒ＝１〜４）は、選択回路２２０１が選択した投票点座標の投票結果を投票マップメモリ２１０２−ｒから読み出し、読み出した投票結果に１を加算して、加算結果を同じ投票点座標に書き込む。加算回路２２０２−１〜加算回路２２０２−４は、このような加算処理を並列に行う。
【０１３０】
そして、距離計算回路１００２がＤＢ画像内のすべての特徴点に対する投票点座標を出力すると、それらの投票点座標に対する投票処理が終了する。このとき、投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４内には、ＤＢ画像内の特徴点の座標とクエリ画像内の特徴点の座標との座標差分の分布を示す投票結果が、分散して格納されている。
【０１３１】
図２３は、図２１の類似度生成回路２１０３の構成例を示している。図２３の類似度生成回路２１０３は、集計回路２３０１、フィルタ回路２３０２、生成回路２３０３、生成回路２３０４、及びライト回路２３０５を含む。生成回路２３０３は、レジスタ２３１１、更新回路２３１２、及びレジスタ２３１３を含み、生成回路２３０４は、レジスタ２３２１、更新回路２３２２、及びレジスタ２３２３を含む。
【０１３２】
集計回路２３０１は、各投票点座標について、投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４が記憶する４個の投票結果を加算することで、それらの投票結果を集計する。そして、集計回路２３０１は、集計した投票結果をフィルタ回路２３０２へ出力する。
【０１３３】
フィルタ回路２３０２、生成回路２３０３、生成回路２３０４、及びライト回路２３０５の動作は、図１４のフィルタ回路１４０１、生成回路１４０２、生成回路１４０３、及びライト回路１４０４の動作と同様である。
【０１３４】
図２４は、図２２の投票処理回路２１０１が行う投票処理の例を示している。この例では、距離計算回路１００２が出力するｑ番目（ｑ＝０〜７）の投票点座標（Ｐｘ，Ｐｙ）が、＃ｑ（Ｐｘ，Ｐｙ）と記述されている。
【０１３５】
例えば、距離計算回路１００２が０番目〜７番目の８個の投票点座標を順に出力した場合、投票処理回路２１０１は、＃０（４，２）及び＃４（３，１）を投票マップメモリ２１０２−１のアクセス対象アドレスとして出力する。これにより、投票マップメモリ２１０２−１の投票点座標（４，２）及び投票点座標（３，１）に１が書き込まれる。
【０１３６】
また、投票処理回路２１０１は、＃１（２，２）及び＃５（３，２）を投票マップメモリ２１０２−２のアクセス対象アドレスとして出力する。これにより、投票マップメモリ２１０２−２の投票点座標（２，２）及び投票点座標（３，２）に１が書き込まれる。
【０１３７】
また、投票処理回路２１０１は、＃２（３，３）及び＃６（２，１）を投票マップメモリ２１０２−３のアクセス対象アドレスとして出力する。これにより、投票マップメモリ２１０２−３の投票点座標（３，３）及び投票点座標（２，１）に１が書き込まれる。
【０１３８】
そして、投票処理回路２１０１は、＃３（２，２）及び＃７（２，２）を投票マップメモリ２１０２−４のアクセス対象アドレスとして出力する。これにより、投票マップメモリ２１０２−４の投票点座標（２，２）に２が書き込まれる。
【０１３９】
このように、投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４を用いて並列に投票処理を行うことで、図１０のＦＰＧＡ９０８と比較して、４倍の速度で投票処理を完了することができる。
【０１４０】
図２５は、図２３の類似度生成回路２１０３が行う類似度計算の例を示している。この例では、投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４から同時にラスタスキャン順で投票結果が読み出され、集計回路２３０１によって、同じ投票点座標の４個の投票結果が加算される。そして、それらの投票結果の合計に基づいて、類似度計算が行われる。
【０１４１】
図１５のフィルタ回路１４０１は、３×３の空間フィルタ演算を行うことで、単一の空間フィルタを適用した投票結果を生成しているが、フィルタ回路１４０１は、複数の空間フィルタを適用した複数の投票結果を生成することも可能である。
【０１４２】
図２６は、複数の空間フィルタを含むフィルタ回路１４０１の構成例を示している。図２６のフィルタ回路１４０１は、ＦＦ１〜ＦＦ２５、ラインバッファ２６０１〜ラインバッファ２６０４、加算回路２６０５、及び加算回路２６０６を含み、３×３の空間フィルタ演算及び５×５の空間フィルタ演算を行う。
【０１４３】
ＦＦ１〜ＦＦ２５は、フリップフロップ回路であり、投票マップメモリ１００４が記憶する各投票点座標の投票結果を保持する。ラインバッファ２６０１〜ラインバッファ２６０４は、それぞれＷｍ−５個の投票結果を保持する。ＦＦ１〜ＦＦ２５及びラインバッファ２６０１〜ラインバッファ２６０４の動作は、図１５のＦＦ１〜ＦＦ９及びラインバッファ１５０１及びラインバッファ１５０２の動作と同様である。
【０１４４】
例えば、ＦＦ１〜ＦＦ５及びラインバッファ２６０１が投票マップメモリ１００４の特定の行Ｒ１の投票結果を保持しているとき、ＦＦ６〜ＦＦ１０及びラインバッファ２６０２は、行Ｒ１に隣接する行Ｒ２の投票結果を保持している。このとき、ＦＦ１１〜ＦＦ１５及びラインバッファ２６０３は、行Ｒ２に隣接する行Ｒ３の投票結果を保持しており、ＦＦ１６〜ＦＦ２０及びラインバッファ２６０４は、行Ｒ３に隣接する行Ｒ４の投票結果を保持している。
【０１４５】
また、ＦＦ１〜ＦＦ２５は、ＦＦ１３が保持している投票結果に対応する投票点座標を中心とする５×５の領域の２５個の投票結果を保持している。
【０１４６】
加算回路２６０６は、ＦＦ１〜ＦＦ２５が保持している２５個の投票結果を加算することで、ＦＦ１３が保持する投票結果に対して５×５の空間フィルタを適用した場合の投票結果を生成する。そして、加算回路２６０６は、加算結果が表す投票結果を生成回路１４０２へ出力する。
【０１４７】
一方、加算回路２６０５は、ＦＦ７〜ＦＦ９、ＦＦ１２〜ＦＦ１４、及びＦＦ１７〜ＦＦ１９が保持している９個の投票結果を加算する。これにより、加算回路２６０５は、図１５の加算回路１５０３と同様に、ＦＦ１３が保持する投票結果に対して３×３の空間フィルタを適用した場合の投票結果を生成する。そして、加算回路２６０５は、加算結果が表す投票結果を生成回路１４０３へ出力する。
【０１４８】
図２６のフィルタ回路１４０１によれば、３×３及び５×５の２種類の空間フィルタを適用した投票結果が生成される。この場合、類似度生成回路１００５は、２種類の空間フィルタを適用した投票結果から、差分の変動の影響が異なる類似度ＭＡ及び類似度ＭＢを求めることができる。
【０１４９】
フィルタ回路１４０１は、３種類以上の空間フィルタを適用した投票結果を生成することも可能である。この場合、類似度生成回路１００５は、３種類以上の空間フィルタを適用した投票結果から、差分の変動の影響が異なる３種類以上の類似度を求め、ＣＰＵ９０１は、それらの類似度を用いて類似度スコアＳを求める。同様に、図２３のフィルタ回路２３０２も、複数の空間フィルタを適用した投票結果を生成することができる。
【０１５０】
なお、情報処理装置７０１は、ＤＢ画像及びクエリ画像の各特徴点の特徴量として、ＢＲＩＥＦ以外の局所特徴量を用いることも可能である。例えば、情報処理装置７０１は、ＢＲＩＥＦの代わりに、以下のような局所特徴量を用いることができる。
（１）Scale-Invariant Feature Transform（ＳＩＦＴ）
（２）Speeded Up Robust Features（ＳＵＲＦ）
（３）Oriented FAST and Rotated BRIEF（ＯＲＢ）
（４）Fast Retina Keypoint（ＦＲＥＡＫ）
【０１５１】
また、ＣＰＵ９０１は、プログラムを実行することによって、ＦＰＧＡ９０８が行うすべての処理を代わりに行うことも可能である。この場合、投票マップメモリ１００４及び投票マップメモリ２１０２−１〜投票マップメモリ２１０２−４としてメモリ９０２を利用し、情報処理装置７０１からＦＰＧＡ９０８を省略することができる。
【０１５２】
図７及び図９の情報処理装置７０１の構成は一例に過ぎず、情報処理装置７０１の用途又は条件に応じて、一部の構成要素を省略又は変更してもよい。例えば、図９の可搬型記録媒体９１０又は通信ネットワークを利用しない場合は、媒体駆動装置９０６又はネットワーク接続装置９０７を省略することができる。ＦＰＧＡ９０８の代わりに、Application Specific Integrated Circuit（ＡＳＩＣ）等の他の論理演算回路を用いて、特徴点ペア計算、投票処理、及び類似度計算を行ってもよい。
【０１５３】
図１０及び図２１のＦＰＧＡ９０８、図１１の距離計算回路１００２、図１２の座標計算回路１１０４−ｉ、図１３の投票処理回路１００３、及び図１４の類似度生成回路１００５の構成は一例に過ぎない。図１５及び図２６のフィルタ回路１４０１、図２２の投票処理回路２１０１、及び図２３の類似度生成回路２１０３の構成も一例に過ぎない。情報処理装置７０１の用途又は条件に応じて、これらの回路の一部の構成要素を省略又は変更してもよい。
【０１５４】
例えば、図１１の距離計算回路１００２において、座標計算回路１１０４−ｉの個数は６個以外であってもよい。図１２の座標計算回路１１０４−ｉにおいて、走査回路１２０１−ｊの個数は１６個以外であってもよく、ＸＯＲ回路１２１１−ｋ及びカウント回路１２１２−ｋの個数は４個以外であってもよい。走査回路１２０１−ｊは、特徴量のハミング距離以外の指標に基づいて、特徴点ペアを求めてもよい。図１５及び図２６のフィルタ回路１４０１において、３×３及び５×５の空間フィルタの代わりに、別の空間フィルタを設けてもよい。
【０１５５】
図８及び図１７〜図１９のフローチャートは一例に過ぎず、情報処理装置７０１の構成又は条件に応じて一部の処理を省略又は変更してもよい。例えば、図１９のステップ１９０５において、ＣＰＵ９０１は、類似度スコアＳが上位の所定枚数のＤＢ画像を表示する代わりに、類似度スコアＳと閾値とを比較した判定結果を表示することもできる。
【０１５６】
図１のマッチング処理、図２の特徴点ペア計算、図３のバイナリ特徴量、図４及び図５の投票結果、図２４の投票処理、及び図２５の類似度計算は一例に過ぎず、これらの処理及び情報は、ＤＢ画像及びクエリ画像に応じて変化する。
【０１５７】
図６及び図２０の処理時間は一例に過ぎず、処理時間は、ＤＢ画像及びクエリ画像に応じて変化する。図１６の表示画面は一例に過ぎず、ＣＰＵ９０１は、別の形式で判定結果を表示してもよい。
【０１５８】
式（１）〜式（１４）は一例に過ぎず、情報処理装置７０１は、別の計算式を用いて、投票マップメモリの幅Ｗｍ及び高さＨｍ、投票点座標（Ｐｘ，Ｐｙ）、類似度スコアＳ等を計算してもよい。
【０１５９】
開示の実施形態とその利点について詳しく説明したが、当業者は、特許請求の範囲に明確に記載した本発明の範囲から逸脱することなく、様々な変更、追加、省略をすることができるであろう。
【０１６０】
図１乃至図２６を参照しながら説明した実施形態に関し、さらに以下の付記を開示する。
（付記１）
第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、前記第１画像内の複数の領域各々と前記第２画像内の対応する領域との組み合わせを求め、各組み合わせに含まれる前記第１画像内の第１領域の位置と前記第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成する分布生成部と、
前記第１分布情報に対して空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第２分布情報を生成し、前記第１分布情報に基づいて前記第１画像と前記第２画像との間の第１類似度を求め、前記第２分布情報に基づいて前記第１画像と前記第２画像との間の第２類似度を求める類似度生成部と、
前記第１類似度と前記第２類似度とに基づいて、前記第１画像と前記第２画像とを比較した比較結果を生成する比較結果生成部と、
を備えることを特徴とする情報処理装置。
（付記２）
前記分布生成部は、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶するメモリと、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントする加算回路とを含み、
前記類似度生成部は、
前記複数の差分範囲各々に対応する組み合わせの個数の最大値に基づいて、前記第１類似度を求める第１生成回路と、
前記複数の差分範囲各々に隣接する差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算し、加算結果を前記第２分布情報として出力するフィルタ回路と、
前記フィルタ回路が出力する組み合わせの個数の最大値に基づいて、前記第２類似度を求める第２生成回路とを含むことを特徴とする付記１記載の情報処理装置。
（付記３）
前記分布生成部は、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶する複数のメモリと、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントする複数の加算回路とを含み、
前記類似度生成部は、
前記複数の差分範囲それぞれについて、前記複数のメモリが記憶する組み合わせの個数を集計する集計回路と、
前記集計回路が集計した組み合わせの個数に基づいて、前記複数の差分範囲各々に対応する組み合わせの個数の最大値を求め、前記最大値に基づいて前記第１類似度を求める第１生成回路と、
前記集計回路が集計した組み合わせの個数に基づいて、前記複数の差分範囲各々に隣接する差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算し、加算結果を前記第２分布情報として出力するフィルタ回路と、
前記フィルタ回路が出力する組み合わせの個数の最大値に基づいて、前記第２類似度を求める第２生成回路とを含むことを特徴とする付記１記載の情報処理装置。
（付記４）
前記比較結果生成部は、前記第１類似度と前記第２類似度とを用いて所定の演算を行うことで、前記第１画像と前記第２画像との間の第３類似度を求め、前記第３類似度に基づいて前記比較結果を生成することを特徴とする付記１乃至３のいずれか１項に記載の情報処理装置。
（付記５）
第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、前記第１画像内の複数の領域各々と前記第２画像内の対応する領域との組み合わせを求め、各組み合わせに含まれる前記第１画像内の第１領域の位置と前記第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成する分布生成部と、
前記第１分布情報に対して第１空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第２分布情報を生成し、前記第１分布情報に対して第２空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第３分布情報を生成し、前記第２分布情報に基づいて前記第１画像と前記第２画像との間の第１類似度を求め、前記第３分布情報に基づいて前記第１画像と前記第２画像との間の第２類似度を求める類似度生成部と、
前記第１類似度と前記第２類似度とに基づいて、前記第１画像と前記第２画像とを比較した比較結果を生成する比較結果生成部と、
を備えることを特徴とする情報処理装置。
（付記６）
前記分布生成部は、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶するメモリと、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントする加算回路とを含み、
前記類似度生成部は、
前記複数の差分範囲各々に隣接する第１差分範囲に対応する組み合わせの個数と、前記第１差分範囲に隣接する第２差分範囲に対応する組み合わせの個数とを、前記複数の差分範囲各々に対応する組み合わせの個数に加算し、加算結果を前記第２分布情報として出力し、前記第１差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算し、加算結果を前記第３分布情報として出力するフィルタ回路と、
前記第２分布情報が表す組み合わせの個数の最大値に基づいて、前記第１類似度を求める第１生成回路と、
前記第３分布情報が表す組み合わせの個数の最大値に基づいて、前記第２類似度を求める第２生成回路とを含むことを特徴とする付記５記載の情報処理装置。
（付記７）
前記分布生成部は、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶する複数のメモリと、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントする複数の加算回路とを含み、
前記類似度生成部は、
前記複数の差分範囲それぞれについて、前記複数のメモリが記憶する組み合わせの個数を集計する集計回路と、
前記集計回路が集計した組み合わせの個数に基づいて、前記複数の差分範囲各々に隣接する第１差分範囲に対応する組み合わせの個数と、前記第１差分範囲に隣接する第２差分範囲に対応する組み合わせの個数とを、前記複数の差分範囲各々に対応する組み合わせの個数に加算し、加算結果を前記第２分布情報として出力し、前記第１差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算し、加算結果を前記第３分布情報として出力するフィルタ回路と、
前記第２分布情報が表す組み合わせの個数の最大値に基づいて、前記第１類似度を求める第１生成回路と、
前記第３分布情報が表す組み合わせの個数の最大値に基づいて、前記第２類似度を求める第２生成回路とを含むことを特徴とする付記５記載の情報処理装置。
（付記８）
前記比較結果生成部は、前記第１類似度と前記第２類似度とを用いて所定の演算を行うことで、前記第１画像と前記第２画像との間の第３類似度を求め、前記第３類似度に基づいて前記比較結果を生成することを特徴とする付記６乃至７のいずれか１項に記載の情報処理装置。
（付記９）
情報処理装置が、
第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、前記第１画像内の複数の領域各々と前記第２画像内の対応する領域との組み合わせを求め、
各組み合わせに含まれる前記第１画像内の第１領域の位置と前記第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成し、
前記第１分布情報に対して空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第２分布情報を生成し、
前記第１分布情報に基づいて前記第１画像と前記第２画像との間の第１類似度を求め、
前記第２分布情報に基づいて前記第１画像と前記第２画像との間の第２類似度を求め、
前記第１類似度と前記第２類似度とに基づいて、前記第１画像と前記第２画像とを比較した比較結果を生成する、
ことを特徴とする情報処理方法。
（付記１０）
前記情報処理装置は、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶するメモリを含み、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントし、
前記複数の差分範囲各々に対応する組み合わせの個数の最大値に基づいて、前記第１類似度を求め、
前記複数の差分範囲各々に隣接する差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算することで、前記第２分布情報を生成し、
前記第２分布情報が表す組み合わせの個数の最大値に基づいて、前記第２類似度を求めることを特徴とする付記９記載の情報処理方法。
（付記１１）
前記情報処理装置は、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶する複数のメモリを含み、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントし、
前記複数の差分範囲それぞれについて、前記複数のメモリが記憶する組み合わせの個数を集計し、
集計した組み合わせの個数に基づいて、前記複数の差分範囲各々に対応する組み合わせの個数の最大値を求め、
前記最大値に基づいて前記第１類似度を求め、
集計した組み合わせの個数に基づいて、前記複数の差分範囲各々に隣接する差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算することで、前記第２分布情報を生成し、
前記第２分布情報が表す組み合わせの個数の最大値に基づいて、前記第２類似度を求めることを特徴とする付記９記載の情報処理方法。
（付記１２）
第１画像内の複数の領域それぞれの特徴量と第２画像内の複数の領域それぞれの特徴量とに基づいて、前記第１画像内の複数の領域各々と前記第２画像内の対応する領域との組み合わせを求め、
各組み合わせに含まれる前記第１画像内の第１領域の位置と前記第２画像内の第２領域の位置との差分の分布を示す第１分布情報を生成し、
前記第１分布情報に対して空間フィルタを適用することで、前記第１領域の位置と前記第２領域の位置との差分の分布を示す第２分布情報を生成し、
前記第１分布情報に基づいて前記第１画像と前記第２画像との間の第１類似度を求め、
前記第２分布情報に基づいて前記第１画像と前記第２画像との間の第２類似度を求め、
前記第１類似度と前記第２類似度とに基づいて、前記第１画像と前記第２画像とを比較した比較結果を生成する、
処理をコンピュータに実行させるためのプログラム。
（付記１３）
前記コンピュータは、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶するメモリを含み、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントし、
前記複数の差分範囲各々に対応する組み合わせの個数の最大値に基づいて、前記第１類似度を求め、
前記複数の差分範囲各々に隣接する差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算することで、前記第２分布情報を生成し、
前記第２分布情報が表す組み合わせの個数の最大値に基づいて、前記第２類似度を求めることを特徴とする付記１２記載のプログラム。
（付記１４）
前記コンピュータは、
前記第１分布情報として、複数の差分範囲それぞれについて差分範囲に属する差分を有する組み合わせの個数を記憶する複数のメモリを含み、
前記第１領域の位置と前記第２領域の位置との差分が生成される度に、前記複数の差分範囲のうち、生成された差分が属する差分範囲に対応する組み合わせの個数をインクリメントし、
前記複数の差分範囲それぞれについて、前記複数のメモリが記憶する組み合わせの個数を集計し、
集計した組み合わせの個数に基づいて、前記複数の差分範囲各々に対応する組み合わせの個数の最大値を求め、
前記最大値に基づいて前記第１類似度を求め、
集計した組み合わせの個数に基づいて、前記複数の差分範囲各々に隣接する差分範囲に対応する組み合わせの個数を、前記複数の差分範囲各々に対応する組み合わせの個数に加算することで、前記第２分布情報を生成し、
前記第２分布情報が表す組み合わせの個数の最大値に基づいて、前記第２類似度を求めることを特徴とする付記１２記載のプログラム。
【符号の説明】
【０１６１】
１０１、１６０２  ＤＢ画像
１０２、１６０１  クエリ画像
１０３  類似度
２０１、２０２  特徴点
３０１、３０２  バイナリ特徴量
４０１、５０１  投票箱
６０１、６０３、２００１  検索処理
６０２、６０４、２００２  判定処理
７０１  情報処理装置
７１１  分布生成部
７１２  類似度生成部
７１３  比較結果生成部
９０１  ＣＰＵ
９０２、１１０１  メモリ
９０３  入力装置
９０４  出力装置
９０５  補助記憶装置
９０６  媒体駆動装置
９０７  ネットワーク接続装置
９０８  ＦＰＧＡ
９０９  バス
９１０  可搬型記録媒体
１００１  制御回路
１００２  距離計算回路
１００３、２１０１  投票処理回路
１００４、２１０２−１〜２１０２−４  投票マップメモリ
１００５、２１０３  類似度生成回路
１１０２、１１０３  リード回路
１１０４−１〜１１０４−６  座標計算回路
１２０１−１〜１２０１−１６  走査回路
１２１１−１〜１２１１−４  ＸＯＲ回路
１２１２−１〜１２１２−４  カウント回路
１２１３  探索回路
１２１４、１４１２、１４２２  更新回路
１２１５、１３０１、２２０１  選択回路
１２１６  計算回路
１３０２、１５０３、２２０２−１〜２２０２−４、２６０５、２６０６  加算回路
１４０１、２３０２  フィルタ回路
１４０２、１４０３、２３０３、２３０４  生成回路
１４０４  ライト回路
１４１１、１４１３、１４２１、１４２３、２３１１、２３１３、２３２１、２３２３  レジスタ
１５０１、１５０２、２６０１〜２６０４  ラインバッファ
１６０３  スライダ
１６０４  検索ボタン
２３０１  集計回路
【図１】
2019046010.tif 000003
【図２】
2019046010.tif 000004
【図３】
2019046010.tif 000005
【図４】
2019046010.tif 000006
【図５】
2019046010.tif 000007
【図６】
2019046010.tif 000008
【図７】
2019046010.tif 000009
【図８】
2019046010.tif 000010
【図９】
2019046010.tif 000011
【図１０】
2019046010.tif 000012
【図１１】
2019046010.tif 000013
【図１２】
2019046010.tif 000014
【図１３】
2019046010.tif 000015
【図１４】
2019046010.tif 000016
【図１５】
2019046010.tif 000017
【図１６】
2019046010.tif 000018
【図１７】
2019046010.tif 000019
【図１８】
2019046010.tif 000020
【図１９】
2019046010.tif 000021
【図２０】
2019046010.tif 000022
【図２１】
2019046010.tif 000023
【図２２】
2019046010.tif 000024
【図２３】
2019046010.tif 000025
【図２４】
2019046010.tif 000026
【図２５】
2019046010.tif 000027
【図２６】
2019046010.tif 000028