(57)【要約】【課題】リファレンス画像に基づくマーカが平面上に配置されており、そのリファレンス画像がクエリ画像中に存在する場合に、クエリ画像とリファレンス画像との間の類似度を、できる限り正確に算出するプログラム、装置及び方法を提供する。【解決手段】クエリ画像の特徴点ｐ'及びリファレンス画像の特徴点ｐと、リファレンス画像からクエリ画像へ射影するHomography行列Ｈとを入力し、リファレンス画像から、クエリ画像に対する平面画像への回転並進行列Ｔを算出し、リファレンス画像の他の複数の特徴点について、Homography行列Ｈ及び回転並進行列Ｔを用いて射影変換した点と、クエリ画像の特徴点との類似度を算出する類似度算出手段を有する。【選択図】図１
2014225168.tif 000002
【特許請求の範囲】
【請求項１】
特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度を算出するべく、装置に搭載されたコンピュータを機能させるプログラムであって、
前記クエリ画像の特徴点ｐ'及び前記リファレンス画像の特徴点ｐの点対応集合Ｐと、前記リファレンス画像から前記クエリ画像へ射影するHomography行列Ｈとを入力し、
２つの点対応（ｐ1,ｐ1'）（ｐ2,ｐ2'）を任意に選択する第１のステップと、
前記２つの点対応を用いて、前記リファレンス画像から前記クエリ画像に対する平面画像への回転並進行列Ｔを算出する第２のステップと、
前記Homography行列Ｈ及び前記回転並進行列Ｔを用いて射影変換した点と、前記クエリ画像の特徴点との間の誤差が、所定範囲に収まった近傍数を計数する第３のステップと
を有し、前記点対応集合Ｐの全ての点対応に対して第１〜第３のステップを繰り返し、
前記近傍数が最も多い高整合の回転並進行列Ｔを導出する第４のステップと、
前記高整合の回転並進行列Ｔについて所定範囲に収まった近傍点対応数を、前記リファレンス画像と前記クエリ画像との間の類似度とする第５のステップと
を実行する類似度算出手段としてコンピュータを機能させることを特徴とするプログラム。
【請求項２】
前記クエリ画像及び前記リファレンス画像から局所特徴点の特徴点集合を抽出する局所特徴点抽出手段と、
前記クエリ画像の特徴点集合と前記リファレンス画像の特徴点集合とをマッチングし、所定範囲で類似した前記クエリ画像の特徴点ｐ'及び前記リファレンス画像の特徴点ｐを前記類似度算出手段へ出力するマッチング手段と
してコンピュータを更に機能させることを特徴とする請求項１に記載のプログラム。
【請求項３】
前記クエリ画像に、複数のリファレンス画像が含まれており、
前記Homography行列Ｈは、当該リファレンス画像とは別のリファレンス画像から、前記クエリ画像へ射影されたものである
ようにコンピュータを機能させることを特徴とする請求項２に記載のプログラム。
【請求項４】
複数の前記リファレンス画像それぞれから抽出された局所特徴点集合を蓄積するリファレンス特徴点蓄積手段と、
前記リファレンス特徴点蓄積手段を用いて、前記クエリ画像の特徴点集合と類似する上位Ｎ件のリファレンス画像を検索する画像検索手段と、
前記上位Ｎ件のリファレンス画像について、類似度の上位から順に、前記クエリ画像との間のHomography行列Ｈを算出し、所定閾値以上で類似する近傍点対応（inliner）となったHomography行列Ｈを出力するHomography行列推定手段と
してコンピュータを更に機能させることを特徴とする請求項２又は３に記載のプログラム。
【請求項５】
前記Homography行列推定手段は、前記上位Ｎ件のリファレンス画像について、類似度の上位から順に、前記クエリ画像との間のHomography行列Ｈを算出していく際に、最初に前記近傍点対応（inliner）が所定数以上となったHomography行列を出力する
ようにコンピュータを機能させることを特徴とする請求項４に記載のプログラム。
【請求項６】
前記マッチング手段は、各クエリ特徴点ｐ'に対し、最も類似したリファレンス特徴点ｐを対応付けて出力する
ようにコンピュータを機能させることを特徴とする請求項２から５のいずれか１項に記載のプログラム。
【請求項７】
前記マッチング手段は、各クエリ特徴点ｐ'に対し、最も類似したリファレンス特徴点ｐを対応付け、リファレンス特徴点ｐに複数のクエリ特徴点ｐ'が対応付けられた場合にはリファレンス特徴点ｐに最も類似するクエリ特徴点ｐ'のみを対応付けて出力する
ようにコンピュータを機能させることを特徴とする請求項６に記載のプログラム。
【請求項８】
前記回転並進行列Ｔは、１つの回転パラメータθと、２つの並進パラメータｔx,ｔyとを有し、
前記クエリ画像の特徴点ｐ'と、前記リファレンス画像の特徴点ｐと、前記Homography行列Ｈと、前記回転並進行列Ｔとは、ｐ'＝Ｈ・Ｔ・ｐの関係にある
【数１】
2014225168.tif 000006
ようにコンピュータを機能させることを特徴とする請求項１から７のいずれか１項に記載のプログラム。
【請求項９】
前記回転並進行列Ｔは、２組の点対応関係から、非線形最小二乗法、レーベンバーグ・マーカート法、又は、ニュートン法を用いて推定されるようにコンピュータを機能させることを特徴とする請求項８に記載のプログラム。
【請求項１０】
特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度を算出する装置であって、
前記クエリ画像の特徴点ｐ'及び前記リファレンス画像の特徴点ｐの点対応集合Ｐと、前記リファレンス画像から前記クエリ画像へ射影するHomography行列Ｈとを入力し、
２つの点対応（ｐ1,ｐ1'）（ｐ2,ｐ2'）を任意に選択する第１のステップと、
前記２つの点対応を用いて、前記リファレンス画像から前記クエリ画像に対する平面画像への回転並進行列Ｔを算出する第２のステップと、
前記Homography行列Ｈ及び前記回転並進行列Ｔを用いて射影変換した点と、前記クエリ画像の特徴点との間の誤差が、所定範囲に収まった近傍数を計数する第３のステップと
を有し、前記点対応集合Ｐの全ての点対応に対して第１〜第３のステップを繰り返し、
前記近傍数が最も多い高整合の回転並進行列Ｔを導出する第４のステップと、
前記高整合の回転並進行列Ｔについて所定範囲に収まった近傍点対応数を、前記リファレンス画像と前記クエリ画像との間の類似度とする第５のステップと
を実行する類似度算出手段を有することを特徴とする装置。
【請求項１１】
装置を用いて、特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度を算出する方法であって、
前記クエリ画像の特徴点ｐ'及び前記リファレンス画像の特徴点ｐの点対応集合Ｐと、前記リファレンス画像から前記クエリ画像へ射影するHomography行列Ｈとを入力し、
２つの点対応（ｐ1,ｐ1'）（ｐ2,ｐ2'）を任意に選択する第１のステップと、
前記２つの点対応を用いて、前記リファレンス画像から前記クエリ画像に対する平面画像への回転並進行列Ｔを算出する第２のステップと、
前記Homography行列Ｈ及び前記回転並進行列Ｔを用いて射影変換した点と、前記クエリ画像の特徴点との間の誤差が、所定範囲に収まった近傍数を計数する第３のステップと
を有し、前記点対応集合Ｐの全ての点対応に対して第１〜第３のステップを繰り返し、
前記近傍数が最も多い高整合の回転並進行列Ｔを導出する第４のステップと、
前記高整合の回転並進行列Ｔについて所定範囲に収まった近傍点対応数を、前記リファレンス画像と前記クエリ画像との間の類似度とする第５のステップと
を有することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特徴点集合で表される画像間の類似度を算出する技術に関する。また、画像間の類似度を算出することによって、特徴点集合で表されるリファレンス画像（検索対象の画像）の集合から、同じく特徴点集合で表されるクエリ画像（検索キーとなる画像）に類似したリファレンス画像を高精度に検索する技術に関する。
【背景技術】
【０００２】
近年、局所特徴点（特徴ベクトル）に基づいた画像認識や検索技術が注目されている。特に、ＳＩＦＴ(Scale-Invariant Feature Transform)やＳＵＲＦ(Speeded Up Robust Features)のようなアルゴリズムが、回転やスケールの変化にロバストであって、広く利用されている。
【０００３】
従来、局所特徴量を用いた類似画像検索の枠組みは、「Bag-of-Visual Words」（又はBag-of-Features、Bag-of-Keypoints）と称される（例えば特許文献１及び非特許文献１参照）。この技術によれば、Bag-of-Wordsモデル及び転置インデックスを用いた文章の検索方法を、類似画像の検索に適用したものである。Bag-of-Wordsは、文章を１つの単語の頻度により定義される特徴ベクトルで表現し、文章集合に基づいて予め導出されたＩＤＦ(Inverse Document Frequency)を単語の重みとして文章間の類似度を導出する枠組みである。これに対し、Bag-of-Visual Wordsは、画像の局所特徴量を量子化し、量子化後の局所特徴量を単語と見立て、同様に頻度により定義される１つの特徴ベクトルとして表現し、ＩＤＦを用いた重み付けを利用して同一の類推方法を適用することができる。
【０００４】
これら従来技術に対して、クエリ画像に対して類似度の高い順に並べられたリファレンス画像のリストについて、更なる正確度を高めたい場合もある。また、クエリ画像とリファレンス画像とに、同一の物体が含まれているか否かを、類似度に基づいて閾値で判定したい場合もある。これらの場合に対して、最初の検索結果で得られた上位Ｎ件のリファレンス画像について、更に正確なスコアを計算するリランキング技術がある（例えば非特許文献２及び３参照）。非特許文献２に記載の技術によれば、上位Ｎ件の各リファレンス画像について、クエリ画像との近傍点対応に基づいて、リファレンス画像とクエリ画像間のHomography行列を推定する。そのHomography行列により定義される拘束条件を満たす点対応 (inlier) の数を新たなスコアとして利用することで、スコアの高精度化を実現している。
【０００５】
一方で、サービスの視点によれば、従来、例えばトレーディングカードゲーム（Trading Card Game、略称「トレカ」）について、拡張現実感（Augmented Reality, AR）の技術を用いたものがある。例えば、カードに、ＡＲマーカが記載されたものがある（例えば非特許文献４参照）。これは、所定アプリをダウンロードしたスマートフォンで、そのカードに記載されたＡＲマーカを読み込み。これによって、そのスマートフォンのディスプレイに、キャラクタが浮かび上がるように出現し、ゲームを進行させるものである。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１０−２８２５８１号公報
【非特許文献】
【０００７】
【非特許文献１】J. Sivic et al., "Video Google: A Text Retrieval Approach toObject Matching in Videos," in Proc. ICCV, 2003.
【非特許文献２】J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman,"Object Retrieval with Large Vocabularies and Fast Spatial Matching,"in Proc of CVPR, 2007.
【非特許文献３】O. Chum and J. Matas, "Matching with PROSAC - ProgressiveSample Consensus," in Proc. of CVPR, 2005.
【非特許文献４】バンダイ、「ＡＲコンテンツを搭載したカードダスを7月30日に発売」、[online]、［平成２５年４月１９日検索］、インターネット＜URL:http://gamebiz.jp/?p=15875＞
【非特許文献５】D. G. Lowe, "Distinctive Image Features from Scale-InvariantKeypoints," International Journal of Computer Vision, vol. 60, no. 2, pp.91-110, 2004.
【非特許文献６】Y. Uchida, K. Takagi, and S. Sakazawa, "An Alternative to IDF:Effective Scoring for Accurate Image Retrieval with Non-Parametric DensityRatio Estimation," in Proc. of ICPR, 2012.
【非特許文献７】H. Jegou, M. Douze, and C. Schmid, "Product quantization fornearest neighbor search," in IEEE Trans. on PAMI, vol. 33, no. 1, pp117-128, 2011.
【非特許文献８】H. Jegou, M. Douze, and C. Schmid, "Improving bag-offeaturesfor large scale image search," in IJCV, vol.87, no.3, pp.316-336, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、既存のリランキング技術によれば、上位Ｎ件の画像に対し、個別にHomography行列を推定し且つスコアを算出している。そのために、以下のような問題が生じる。
（１）Homography行列の推定には、最低４組の点対応が必要である。そのために、４組全ての点対応が、inlierでなければ正解のHomography行列が得られない。４組全ての点対応がinlierである確率は、outlierの割合の増加に応じて、指数的に減少し、認識精度も低下する。
（２）Homography行列は、その算出に用いられた点対応以外の点対応を利用して、その信頼度が算出される。そのために、少なくとも４組よりも多い点対応が得られていなければ、Homography行列の検証ができない。結果的に未検出を発生させる。
【０００９】
このような画像の局所特徴点の技術は、カードを用いたマーカ認識技術に適用することもできる。例えばＡＲマーカやＱＲコード(Quick Response Code)（登録商標）のような人工的なマーカではなく、自然画像をマーカとして認識することができる。特に、カードのようなものは、テーブルのような平面上に配置されるのが一般的である。
【００１０】
そこで、本発明によれば、リファレンス画像に基づくマーカ（例えばカード）が平面上に配置された状態で写るクエリ画像について、クエリ画像とリファレンス画像との間の類似度を、できる限り正確に算出するプログラム、装置及び方法を提供する。
【課題を解決するための手段】
【００１１】
本発明によれば、特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度を算出するべく、装置に搭載されたコンピュータを機能させるプログラムであって、
クエリ画像の特徴点ｐ'及びリファレンス画像の特徴点ｐの点対応集合Ｐと、リファレンス画像からクエリ画像へ射影するHomography行列Ｈとを入力し、
２つの点対応（ｐ1,ｐ1'）（ｐ2,ｐ2'）を任意に選択する第１のステップと、
２つの点対応を用いて、リファレンス画像からクエリ画像に対する平面画像への回転並進行列Ｔを算出する第２のステップと、
Homography行列Ｈ及び回転並進行列Ｔを用いて射影変換した点と、クエリ画像の特徴点との間の誤差が、所定範囲に収まった近傍数を計数する第３のステップと
を有し、点対応集合Ｐの全ての点対応に対して第１〜第３のステップを繰り返し、
近傍数が最も多い高整合の回転並進行列Ｔを導出する第４のステップと、
高整合の回転並進行列Ｔについて所定範囲に収まった近傍点対応数を、リファレンス画像とクエリ画像との間の類似度とする第５のステップと
を実行する類似度算出手段としてコンピュータを機能させることを特徴とする。
【００１２】
本発明のプログラムにおける他の実施形態によれば、
クエリ画像及びリファレンス画像から局所特徴点の特徴点集合を抽出する局所特徴点抽出手段と、
クエリ画像の特徴点集合とリファレンス画像の特徴点集合とをマッチングし、所定範囲で類似したクエリ画像の特徴点ｐ'及びリファレンス画像の特徴点ｐを類似度算出手段へ出力するマッチング手段と
してコンピュータを更に機能させることも好ましい。
【００１３】
本発明のプログラムにおける他の実施形態によれば、
クエリ画像に、複数のリファレンス画像が含まれており、
Homography行列Ｈは、当該リファレンス画像とは別のリファレンス画像から、クエリ画像へ射影されたものである
ようにコンピュータを機能させることも好ましい。
【００１４】
本発明のプログラムにおける他の実施形態によれば、
複数のリファレンス画像それぞれから抽出された局所特徴点集合を蓄積するリファレンス特徴点蓄積手段と、
リファレンス特徴点蓄積手段を用いて、クエリ画像の特徴点集合と類似する上位Ｎ件のリファレンス画像を検索する画像検索手段と、
上位Ｎ件のリファレンス画像について、類似度の上位から順に、クエリ画像との間のHomography行列Ｈを算出し、所定閾値以上で類似する近傍点対応（inliner）となったHomography行列Ｈを出力するHomography行列推定手段と
してコンピュータを更に機能させることも好ましい。
【００１５】
本発明のプログラムにおける他の実施形態によれば、
Homography行列推定手段は、上位Ｎ件のリファレンス画像について、類似度の上位から順に、クエリ画像との間のHomography行列Ｈを算出していく際に、最初に近傍点対応（inliner）が所定数以上となったHomography行列を出力する
ようにコンピュータを機能させることも好ましい。
【００１６】
本発明のプログラムにおける他の実施形態によれば、
マッチング手段は、各クエリ特徴点ｐ'に対し、最も類似したリファレンス特徴点ｐを対応付けて出力する
ようにコンピュータを機能させることも好ましい。
【００１７】
本発明のプログラムにおける他の実施形態によれば、
マッチング手段は、各クエリ特徴点ｐ'に対し、最も類似したリファレンス特徴点ｐを対応付け、リファレンス特徴点ｐに複数のクエリ特徴点ｐ'が対応付けられた場合にはリファレンス特徴点ｐに最も類似するクエリ特徴点ｐ'のみを対応付けて出力する
ようにコンピュータを機能させることも好ましい。
【００１８】
本発明のプログラムにおける他の実施形態によれば、
回転並進行列Ｔは、１つの回転パラメータθと、２つの並進パラメータｔx,ｔyとを有し、
クエリ画像の特徴点ｐ'と、リファレンス画像の特徴点ｐと、Homography行列Ｈと、回転並進行列Ｔとは、ｐ'＝Ｈ・Ｔ・ｐの関係にある
【数１】
2014225168.tif 000003
ようにコンピュータを機能させることも好ましい。
【００１９】
本発明のプログラムにおける他の実施形態によれば、
回転並進行列Ｔは、２組の点対応関係から、非線形最小二乗法、レーベンバーグ・マーカート法、又は、ニュートン法を用いて推定されるようにコンピュータを機能させることも好ましい。
【００２０】
本発明によれば、特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度を算出する装置であって、
クエリ画像の特徴点ｐ'及びリファレンス画像の特徴点ｐの点対応集合Ｐと、リファレンス画像からクエリ画像へ射影するHomography行列Ｈとを入力し、
２つの点対応（ｐ1,ｐ1'）（ｐ2,ｐ2'）を任意に選択する第１のステップと、
２つの点対応を用いて、リファレンス画像からクエリ画像に対する平面画像への回転並進行列Ｔを算出する第２のステップと、
Homography行列Ｈ及び回転並進行列Ｔを用いて射影変換した点と、クエリ画像の特徴点との間の誤差が、所定範囲に収まった近傍数を計数する第３のステップと
を有し、点対応集合Ｐの全ての点対応に対して第１〜第３のステップを繰り返し、
近傍数が最も多い高整合の回転並進行列Ｔを導出する第４のステップと、
高整合の回転並進行列Ｔについて所定範囲に収まった近傍点対応数を、リファレンス画像とクエリ画像との間の類似度とする第５のステップと
を実行する類似度算出手段を有することを特徴とする。
【００２１】
本発明によれば、装置を用いて、特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度を算出する方法であって、
クエリ画像の特徴点ｐ'及びリファレンス画像の特徴点ｐの点対応集合Ｐと、リファレンス画像からクエリ画像へ射影するHomography行列Ｈとを入力し、
２つの点対応（ｐ1,ｐ1'）（ｐ2,ｐ2'）を任意に選択する第１のステップと、
２つの点対応を用いて、リファレンス画像からクエリ画像に対する平面画像への回転並進行列Ｔを算出する第２のステップと、
Homography行列Ｈ及び回転並進行列Ｔを用いて射影変換した点と、クエリ画像の特徴点との間の誤差が、所定範囲に収まった近傍数を計数する第３のステップと
を有し、点対応集合Ｐの全ての点対応に対して第１〜第３のステップを繰り返し、
近傍数が最も多い高整合の回転並進行列Ｔを導出する第４のステップと、
高整合の回転並進行列Ｔについて所定範囲に収まった近傍点対応数を、リファレンス画像とクエリ画像との間の類似度とする第５のステップと
を有することを特徴とする。
【発明の効果】
【００２２】
本発明のプログラム、装置及び方法によれば、リファレンス画像に基づくマーカが平面上に配置された状態で写るクエリ画像について、クエリ画像とリファレンス画像との間の類似度を、できる限り正確に算出することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明における検索装置の機能構成図である。
【図２】Homography行列に基づくinlier及びoutlierを表す画像対応図である。
【図３】クエリ画像座標系とリファレンス画像座標系との間の変換を表す説明図である。
【図４】クエリ画像に写る一方のカードとリファレンス画像とを対応付けた説明図である。
【図５】図４に基づいて、クエリ画像に写る他方のカードとリファレンス画像とを対応付けた説明図である。
【図６】本発明の検索装置を組み込んだスマートフォンを用いた使用形態を表す説明図である。
【発明を実施するための形態】
【００２４】
以下では、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２５】
本発明によれば、以下のように２つの実施の形態に区分できる。
（１）類似度算出機能：特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度を算出する。
（２）検索装置：類似度算出機能を用いて、大量のリファレンス画像の中から、クエリ画像に写る１つ以上のリファレンス画像を検索する。
尚、以下では、本発明を、類似度算出部を含む検索装置として説明する。
【００２６】
図１は、本発明における検索装置の機能構成図である。
【００２７】
図１によれば、検索装置１は、大量の「リファンレンス画像」を予め入力する。リファレンス画像には、同一の物体又は同一カテゴリに属する少なくとも１つのインスタンス（対象物、マーカ）が写っている。そして、検索の際、検索装置１は、検索キーとなる「クエリ画像」を入力し、そのクエリ画像に写る１枚以上のリファレンス画像を検索する。
【００２８】
図１の検索装置１は、局所特徴点抽出部１１と、リファレンス特徴点蓄積部１２と、画像検索部１３と、マッチング・リランキング部１４と、Homography推定部１５と、類似度算出部１６とを有する。これら機能構成部は、検索装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現できる。特に、本発明の特徴部分である類似度算出部１６は、その処理の流れから、類似度算出方法としても理解できる。
【００２９】
［局所特徴点抽出部１１］
局所特徴点抽出部１１は、クエリ画像及びリファレンス画像それぞれから局所特徴点の特徴点集合を抽出する。リファレンス画像の特徴点集合は、リファレンス特徴点蓄積部１２へ出力され、クエリ画像の特徴点集合は、画像検索部１３へ出力される。
【００３０】
局所特徴点の抽出アルゴリズムとしては、例えばＳＩＦＴやＳＵＲＦ、ＯＲＢ(Oriented FAST and Rotated BRIEF)が用いられる。これらの局所特徴点は、座標ｐ＝(x,y)と特徴量ベクトルfとによって記述される。尚、クエリ画像の局所特徴点と、リファレンス画像の局所特徴点とは、その特徴ベクトルについて同じ次元数である。
【００３１】
例えば、ＳＩＦＴの場合、１枚の画像からは１２８次元の特徴点集合が抽出される（例えば非特許文献５参照）。ＳＩＦＴとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる特徴ベクトルを記述する技術である。一方で、ＳＵＲＦの場合、ＳＩＦＴよりも高速処理が可能であって、１枚の画像から６４次元の特徴点集合が抽出される。また、ＯＲＢは、バイナリコードによる特徴記述としてＢＲＩＥＦ(Binary Robust Independent Elementary Features)を用いて、１つのコンテンツから２５６ビットのバイナリ特徴ベクトルの集合を抽出する。特に、ＯＲＢによれば、ＳＩＦＴやＳＵＲＦと比較して、同等以上の精度を保持すると共に、数百倍の高速化を実現することができる。
【００３２】
［リファレンス特徴点蓄積部１２］
リファレンス特徴点蓄積部１２は、リファレンス画像毎（リファレンス画像識別子毎）に、局所特徴点の特徴点集合を蓄積する。
【００３３】
［画像検索部１３］
画像検索部１３は、リファレンス特徴点蓄積部１２を用いて、クエリ画像の特徴点集合と類似する上位Ｎ（＞１）件のリファレンス画像を検索する（例えば非特許文献６参照）。クエリ画像の特徴点と、リファレンス画像の特徴点との間の距離が短いほど、類似度が高いことを意味する。具体的には、最近傍探索(Approximate Nearest Neighbor)アルゴリズムの１つである直積量子化を用いた方法（例えば非特許文献７参照）やHamming Embeddingを用いた方法（例えば非特許文献８参照）、ＬＳＨ(Locality-Sensitive
Hashing)を用いることも好ましい。上位Ｎ件のリファレンス画像の特徴点集合は、マッチング・リランキング部１４へ出力され、リファレンス画像の類似度順位は、Homography推定部１５へ出力される。
【００３４】
［マッチング・リランキング部１４］
マッチング・リランキング部１４は、マッチング機能とリランキング機能とを有する。
＜マッチング機能＞
マッチング機能は、各クエリ特徴点ｐ'に対し、最も類似したリファレンス特徴点ｐを対応付ける。また、リファレンス特徴点ｐに複数のクエリ特徴点ｐ'が対応付けられた場合にはリファレンス特徴点ｐに最も類似するクエリ特徴点ｐ'のみを対応付ける。対応付けられたリファレンス画像とクエリ画像との点対応Ｐ＝{(p, p')}集合は、Homography推定部１５及び類似度算出部１６へ出力される。
【００３５】
＜リランキング機能＞
画像検索部１３から出力されたリファレンス画像のリストを、類似度算出部１６から出力された類似度に応じて降順にリランキングする。リランキングには、例えばＩＤＦ(Inverse Document Frequency)を用いることができる。最終的に、所定閾値以上の上位のスコアを得たリファレンス画像を、検索結果として出力する。
【００３６】
［Homography推定部１５］
Homography推定部１５では、画像検索部１３からの上位Ｎ件のリファレンス画像について、類似度の上位から降順に、クエリ画像との間のHomography行列Ｈを算出する。ここで、所定閾値以上で類似する近傍点対応（inliner）となったHomography行列Ｈを検出した際、そのHomography行列Ｈを、類似度算出部１６へ出力する。
【００３７】
図２は、Homography行列に基づくinlier及びoutlierを表す画像対応図である。outlierは、破線で表されている。
【００３８】
クエリ画像及び対象リファレンス画像は、類似度が高いほど、特徴ベクトル同士が射影幾何学的に線形となる。従って、平面射影変換行列であるHomography行列Ｈによって、座標を置き換えることができる。Homography行列Ｈは、以下のように表される。
【数２】
2014225168.tif 000004
【００３９】
Homography行列の算出には、マッチング・リランキング部１４から入力された特徴点の対応点の集合が用いられる。Homography行列Ｈの未知パラメータ数は、８個（h11〜h33、h33=1）であり、一組の対応点は２個の制約式を与える。従って、この行列Ｈは、４組以上の対応点があれば、最小二乗法によって算出することができる。
【００４０】
そこで、Homography行列推定部１５は、入力された特徴点の対応点の集合の中で、ランダムに４組を選択し、その４組からHomography行列Ｈを算出する。その後、そのHomography行列Ｈを用いて、各クエリ特徴点を射影した際に、以下のように判定する。
（１）リファレンス特徴点に対して所定閾値以下の近くに射影されれば、inlierと判定する。
（２）逆に、所定閾値よりも遠くに射影されれば、outlierと判定する。
この処理を複数回実行した後、inlierの数が最も多かったHomography行列Ｈのみを採用する。
【００４１】
［類似度算出部１６］
類似度算出部１６は、クエリ画像の特徴点ｐ'及びリファレンス画像の特徴点ｐの点対応Ｐ＝{(ｐ, ｐ')}集合と、Homography行列Ｈとを入力する。そして、以下のステップを実行する。
（Ｓ１）２つの点対応（ｐ1,ｐ1'）（ｐ2,ｐ2'）を任意（ランダム）に選択する。
（Ｓ２）２つの点対応を用いて、リファレンス画像からクエリ画像に対する平面画像への回転並進行列Ｔを算出する。
（Ｓ３）Homography行列Ｈ及び回転並進行列Ｔを用いて射影変換した点と、クエリ画像の特徴点との間の誤差が、所定範囲に収まった近傍数を計数する。その誤差は、類似度を意味し（誤差が小さいほど類似度も高い）、以下のように表される。
誤差：||ｐ'−Ｈ・Ｔ・ｐ||2
そして、その誤差が所定閾値以下の近傍点対応をinlierと判定する。最終的には、inlierの数をカウントする。
【００４２】
ここで、点対応集合Ｐの全ての点対応に対して、Ｓ１〜Ｓ３を繰り返す。
【００４３】
（Ｓ４）近傍数が最も多い高整合の回転並進行列Ｔを導出する。即ち、最もinlierの数が多かった回転並進行列Ｔを採用する。
（Ｓ５）高整合の回転並進行列Ｔについて所定範囲に収まった近傍点対応数を、リファレンス画像とクエリ画像との間の類似度とする。
【００４４】
図３は、クエリ画像座標系とリファレンス画像座標系との間の変換を表す説明図である。
【００４５】
リファレンス画像は、回転並進行列Ｔによって中間座標系へ変換でき、更に、Homography行列Ｈによってクエリ画像へ変換できる。回転並進行列Ｔは、１つの回転パラメータθと、２つの並進パラメータｔx,ｔyとを有する。そして、クエリ画像の特徴点ｐ'と、リファレンス画像の特徴点ｐと、Homography行列Ｈと、回転並進行列Ｔとは、以下のような関係にある。
ｐ'＝Ｈ・Ｔ・ｐ
【数３】
2014225168.tif 000005
【００４６】
回転並進行列Ｔは、３つの未知変数（ｔx,ｔy、θ）であるために、少なくとも点対応（ｐ,ｐ'）の２つの組を用いて、最小二乗法によって算出することができる。その他の方法として、回転並進行列Ｔは、２組の点対応関係から、レーベンバーグ・マーカート法やニュートン法のような非線形最小二乗法を用いて算出することもできる。
【００４７】
前述したHomography推定部１５によれば、８個のパラメータを推定するために、少なくとも４組の点対応が必要となる。これに対し、類似度算出部１６によれば、２組の点対応のみで、回転並進パラメータを推定することができる。これは、リファレンス画像の存在する平面が既知であることを前提とすることによって、平行移動及び回転に基づく３パラメータのみを推定すればよいからである。これによって、以下のような効果が得られる。
（１）２組の点対応の全てがinlierである確率は、通常のHomography推定で求められる４組の点対応全てがinlierである確率よりも、圧倒的に高い。そのために、正解のパラメータが推定できる可能性が高くなり、認識精度も高くなる。
（２）２組の点対応のみがパラメータ推定に用いられるために、それ以外の点対応が検証に利用することができ、未検出率が低くなる。
【００４８】
図４は、クエリ画像に写る一方のカードとリファレンス画像とを対応付けた説明図である。
【００４９】
図４によれば、クエリ画像には、例えば平面上に２枚のカード（複数のリファレンス画像）が配置された状態が写っているとする。その中で、１枚のカードについて、リファレンス画像と類似することが検出されることによって、リファレンス画像からクエリ画像へ変換するためのHomography行列Ｈが算出される。
【００５０】
図５は、図４に基づいて、クエリ画像に写る他方のカードとリファレンス画像とを対応付けた説明図である。
【００５１】
図５によれば、図４によって算出されたHomography行列Ｈを用いて、別途、回転並進行列Ｔを算出するだけで、クエリ画像の他方のカードに類似するリファレンス画像を検出することできる。即ち、図５によれば、Homography行列Ｈとして、当該リファレンス画像とは別のリファレンス画像から、クエリ画像へ射影されたものを用いる。
【００５２】
図６は、本発明の検索装置を組み込んだスマートフォンを用いた使用形態を表す説明図である。
【００５３】
図６によれば、ユーザが、スマートフォンのカメラを用いて、テーブル上に配置されたカードを撮影している。このとき、スマートフォンは、複数のカードが写るクエリ画像（撮影写真）から、できる限り正確に複数のカード（リファレンス画像）を検出することができる。これによって、所定アプリをダウンロードしたスマートフォンでは、複数のカードを撮影したクエリ画像を取り込むことによって、そのスマートフォンのディスプレイに、そのキャラクタが浮かび上がるように出現させることもできる。例えば、カードＡとカードＢとが揃って撮影された場合にのみ、キャラクタＡを出現させることができる。
【００５４】
以上、詳細に説明したように、本発明のプログラム、装置及び方法によれば、リファレンス画像に基づくマーカが平面上に配置された状態で写るクエリ画像について、クエリ画像とリファレンス画像との間の類似度を、できる限り正確に算出することができる。
【００５５】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００５６】
１  検索装置
１１  局所特徴点抽出部
１２  リファレンス特徴点蓄積部
１３  画像検索部
１４  マッチング・リランキング部
１５  Homography推定部
１６  類似度算出部
【図１】
2014225168.tif 000007
【図２】
2014225168.tif 000008
【図３】
2014225168.tif 000009
【図４】
2014225168.tif 000010
【図５】
2014225168.tif 000011
【図６】
2014225168.tif 000012