(57)【要約】  【課題】  局所画像特徴量を用いた画像検索技術において、画像検索に用いるデータの量を抑える。  【解決手段】  画像検索システム１００は、クエリ画像処理装置１０と検索サーバ装置２０とからなる。クエリ画像処理装置１０は、クエリ画像について、局所画像特徴量群と、画像全体の特徴を示す全体画像特徴量とを生成する。検索サーバ装置２０は、複数の参照画像の各々について局所画像特徴量群と、各参照画像の全体の特徴を示す全体画像特徴量を保存している。一次画像検索部２５は、クエリ画像及び参照画像の全体画像特徴量を互いに比較することで、参照画像の中から、クエリ画像に対応する対応画像の候補となる候補画像を決定する。二次画像検索部２６は、クエリ画像及び候補画像の局所画像特徴量を比較することで、候補画像の中から、対応画像を決定する。【選択図】  図１
2015111339.tif 000002
【特許請求の範囲】
【請求項１】
クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を生成する局所画像特徴量群生成部と、
前記局所画像特徴量群から、前記クエリ画像の全体の特徴を示す全体画像特徴量を生成する全体画像特徴量生成部と、
複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存部と、
前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存部と、
前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索部と、
前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記候補画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索部と、
を備えることを特徴とする画像検索システム。
【請求項２】
前記一次画像検索部は、前記クエリ画像の全体画像特徴量と距離の近い全体画像特徴量を有する参照画像を、前記候補画像として決定することを特徴とする請求項１に記載の画像検索システム。
【請求項３】
前記二次画像検索部は、前記クエリ画像の局所画像特徴量にマッチングする前記局所特徴量を多く有する前記候補画像を前記対応画像として決定することを特徴とする請求項１又は２に記載の画像検索システム。
【請求項４】
前記複数の参照画像を保存する参照画像保存部をさらに備え、
前記画像検索システムは、前記参照画像保存部に保存された参照画像から、前記対応画像を読み出す
ことを特徴とする請求項１ないし３のいずれか一項に記載の画像検索システム。
【請求項５】
前記クエリ画像及び前記参照画像の全体画像特徴量は、それぞれ前記クエリ画像及び前記参照画像の複数の前記局所画像特徴量をヒストグラムにすることにより得られることを特徴とする請求項１ないし４のいずれか一項に記載の画像検索システム。
【請求項６】
前記クエリ画像及び前記参照画像の全体画像特徴量は、それぞれ前記クエリ画像及び前記参照画像の複数の前記局所画像特徴量をガウス混合モデルでクラスタリングすることにより得られることを特徴とする請求項１ないし４のいずれか一項に記載の画像検索システム。
【請求項７】
前記クエリ画像及び前記参照画像の全体画像特徴量は、それぞれ前記クエリ画像及び前記参照画像の複数の前記局所画像特徴量をｋ−ｍｅａｎｓ法でクラスタリングすることにより得られることを特徴とする請求項１ないし４のいずれか一項に記載の画像検索システム。
【請求項８】
前記局所画像特徴量群生成部は、実数ベクトルで構成された局所画像特徴量をバイナリコードに変換して、前記局所画像特徴量群を生成し、
前記局所画像特徴量群保存部は、バイナリコードに変換された局所画像特徴量からなる局所画像特徴量群を保存する
ことを特徴とする請求項１ないし７のいずれか一項に記載の画像検索システム。
【請求項９】
前記全体画像特徴量群生成部は、実数ベクトルで構成された全体画像特徴量をバイナリコードに変換して、前記全体画像特徴量を生成し、
前記全体画像特徴量群保存部は、バイナリコードに変換された全体画像特徴量を保存する
ことを特徴とする請求項１ないし８のいずれか一項に記載の画像検索システム。
【請求項１０】
前記二次画像検索部は、前記候補画像の局所画像特徴量群と、前記クエリ画像の局所画像特徴量群との間で局所画像特徴量が類似する特徴点の組の個数を数え上げ、前記組の個数に基づいて前記対応画像を決定することを特徴とする請求項１ないし９のいずれか一項に記載の画像検索システム。
【請求項１１】
前記二次画像検索部は、前記候補画像の局所画像特徴量群と、前記クエリ画像の局所画像特徴量群との類似する局所画像特徴量の組の個数を数え上げ、前記組の個数に基づいて前記候補画像の中から選択画像を選択し、前記選択画像と前記クエリ画像との間で画像上での位置が特定の射影関係にある特徴点の組の個数を数え上げ、前記特定の射影関係にある特徴点の組の個数が最も多い選択画像を前記対応画像として決定することを特徴とする請求項１ないし９のいずれか一項に記載の画像検索システム。
【請求項１２】
クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を生成する局所画像特徴量群生成部と、
前記局所画像特徴量群から、前記クエリ画像の全体の特徴を示す全体画像特徴量を生成する全体画像特徴量生成部と、
複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存部と、
前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存部と、
前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索部と、
前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記候補画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索部と、
を備えることを特徴とする画像検索装置。
【請求項１３】
クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群と、前記クエリ画像の全体の特徴を示す全体画像特徴量とを取得するクエリ情報取得部と、
複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存部と、
前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存部と、
前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索部と、
前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記参照画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索部と、
を備えることを特徴とする検索サーバ装置。
【請求項１４】
クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群及び前記クエリ画像の全体の特徴を示す全体画像特徴量を取得するクエリ情報取得ステップと、
複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存ステップと、
前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存ステップと、
前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索ステップと、
前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記候補画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索ステップと、
を含むことを特徴とする画像検索方法。
【請求項１５】
コンピュータを、
クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群及び前記クエリ画像の全体の特徴を示す全体画像特徴量を取得するクエリ情報取得部、
複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存部、
前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存部、
前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索部、及び
前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記候補画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索部、
として機能させることを特徴とする画像検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大量の参照画像の中からクエリ画像に対応する対応画像を検索する画像検索技術に関するものである。
【背景技術】
【０００２】
複数の画像の間で対応点を抽出する際に、局所画像特徴量が用いられる。例えば、１つの被写体を異なる２つの視点から撮影して得た２枚の画像を用いれば、撮影した機材の焦点距離などの内部パラメータと呼ばれる装置固有の情報が与えられたときに、三角測量の原理で撮影場所から被写体までの距離を測定したり、被写体の大きさを推定したりできる。
【０００３】
このとき、被写体上のある点は、２つの画像上にそれぞれ投影され、２つの画像間で共通して観測される。このような２つの画像間で共通して観測される点（対応点）を検出するために、局所画像特徴量が用いられる。即ち、局所画像特徴量が一致する点が対応点であると判断する。
【０００４】
この局所画像特徴量を応用して、画像検索を実現できることが知られている。この画像検索技術では、複数の画像をデータベースに保存しておくとともに、それらすべての画像について、特徴点を抽出して、抽出した特徴点の局所画像特徴量を計算し、これらもデータベースに保存しておく。クエリ画像が入力されると、クエリ画像から特徴点を抽出し、それらの局所画像特徴量を算出する。そして、データベースに保存された複数の画像の各々について、クエリ画像に含まれる特徴点の局所画像特徴量と一致する局所画像特徴量を有する特徴点を対応点としてカウントし、その対応点の数が最も多い画像が、クエリ画像に最も近似した画像であると判断される。
【０００５】
さらに、この局所画像特徴量を用いた画像検索技術では、特徴点の位置情報も利用される。上述のように、局所画像特徴量を用いた画像検索技術では、データベース中の画像の中で、クエリ画像の特徴点と対応する特徴点を多く持つ画像をクエリ画像に近い画像と判断するが、このように局所画像特徴量の比較のみで対応点であると判断すると、実際には対応しないが偶然に局所画像特徴量が一致する点同士が対応点であると誤って判断されることになる。
【０００６】
このようなノイズによる誤判断を防ぐため、クエリ画像のある特徴点の局所画像特徴量とデータベース中の画像のある特徴点の局所画像特徴量とが一致するか否かのみではなく、クエリ画像の当該特徴点の位置とデータベース中の画像の当該特徴点の位置との幾何的射影関係を求めて、クエリ画像の当該特徴点がデータベース中の画像の当該特徴点に正しく射影されているかを判定し、その判定結果も合わせて、それらの特徴点が対応点であるかを判断する手法がある。
【０００７】
具体的には、被写体が紙面などの二次元平面であると仮定できる場合、次のようにして、局所画像特徴量が一致する特徴点同士について、それらの位置も一致しているか否かを判断する。まず、クエリ画像とデータベース中の画像との間で、局所画像特徴量が一致する特徴点の組をすべて検出する。そして、それらの複数の特徴点の組について、ＲＡＮＳＡＣ法を使用して、クエリ画像の特徴点の位置をその特徴点と組になったデータベース中の画像の特徴点の位置に射影するホモグラフィ行列を計算する。
【０００８】
さらに、そのホモグラフィ行列によって、再度、データベース中の画像の特徴点と局所画像特徴量が一致すると判断されたクエリ画像の特徴点の位置を射影する。そして、その結果得られた位置が、クエリ画像の特徴点と局所画像特徴量が一致すると判断されたデータベース中の画像の特徴点の位置とどれだけずれているかを計算し（位置のマッチング）、その計算結果（マッチングスコア）に基づいて、最終的にそれらの特徴点が対応点であるか否かを判断する。
【０００９】
ところで、１つの画像から数百点の特徴点を抽出し、それぞれの点ごとの局所画像特徴量を算出し、さらに、他の画像の局所画像特徴量と比較すると、その演算に用いられるデータ量は膨大になり、大容量のメモリや高速なＣＰＵ、さらに大容量の保存用ストレージが必要となる。局所画像特徴量として一般に知られているＳＩＦＴ特徴量の場合には、各特徴点の情報を表す特徴点データとして、局所画像特徴量の他に、スケール情報、位置情報、主軸情報等の付随情報が含まれる。これらをすべての特徴点について足し合わせると、例えば、１枚の画像に８００点の特徴点が含まれるとすると、１枚あたり約４２２Ｋバイトのデータ量になる。このため、例えば１０，０００枚の画像を検索対象に使用すると、扱うデータの量は（４２２Ｋバイト×１０，０００）約４．２Ｇバイトにもなる。
【００１０】
このような課題に対して、各特徴点の局所画像特徴量を圧縮することで、対応点の抽出を高速化する技術として、ＯＲＢ、ｂｒｉｓｋ、ＣＡＲＤ等の技術が提案されており、本願発明者らもそのような技術に関して特許出願をしている（特許文献１）。これらの技術は、各特徴点の局所画像特徴量を実数ベクトルではなく、二値のベクトルで表現することによって、局所画像特徴量の圧縮を実現している。また、従来とは異なる計算手法を採用することで、局所画像特徴量の高速な算出を実現している。
【００１１】
しかしながら、このような高速計算が可能でかつサイズの小さい局所画像特徴量を用いても、検索のために必要なデータ量及び計算量の増大を抑えることは困難である。この理由は以下のとおりである。例えば、１０，０００枚の画像を検索対象とする場合、その画像から抽出される特徴点の数が平均８００点であるとすると、８，０００，０００個の特徴量の中からクエリ画像に含まれる８００点の特徴点の特徴量の各々に最も近いものを検索する必要がある。検索の際には、この８，０００，０００個の特徴量をメモリ上に保持する必要がある。また、８，０００，０００個の特徴点の中から、最も近い特徴点を効率よく検索するためには、検索のための検索木などを構築する必要があり、そのための計算コストも無視できない。
【００１２】
一方で、局所画像特徴量をそのまま用いるのではなく、１枚の画像に含まれる複数の局所画像特徴量から、当該画像の全体の特徴を示す１つの画像特徴量（以下、「全体画像特徴量」ともいう。）を生成する手法も提案されている。この手法によれば、１つの画像ごとに１つの特徴量が生成されるため、これを画像検索に適応すると、例えば、１０，０００枚の画像を検索対象とする場合、１０，０００個の画像の中から、全体画像特徴量に最も近い全体画像特徴量を持つものを探索することになり、上述の局所画像特徴量をそのまま用いる手法と比較すると、検索対象及び検索回数を抑えることができる。
【００１３】
なお、本発明に関連する先行技術として、以下の先行技術文献がある。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２０１２−１６００４７号公報
【非特許文献】
【００１５】
【非特許文献１】David G. Lowe, "Object recognition from local scale-invariant features," International Conference on Computer Vision, Corfu, Greece (September 1999), pp. 1150-1157
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、全体画像特徴量を用いる手法では、局所画像特徴量を用いる手法と比較して、精度が低いことが知られている。近年、比較的精度の高い全体画像特徴量を生成する技術として、ＶＬＡＤ（Vector of Locally Aggregated Descriptors）と呼ばれる手法が提案されているが、それでも局所画像特徴量をそのまま用いる手法と比較すると、精度が劣る。
【００１７】
以上のように、局所画像特徴量だけを用いる場合は、検索精度は高いが計算コストやメモリ使用量が大きく、全体画像特徴量を用いる場合は、計算コストやメモリ使用量が抑えられるという長所はあるが、検索精度が低くなるという問題がある。
【００１８】
また、全体画像特徴量を用いる場合は、画像に含まれる特徴点がすべて集約されて一つの特徴量になってしまうため、後段の処理で、マッチングした特徴点同士の位置関係を利用した検索の確認作業ができないという問題もある。
【００１９】
本願発明は、上記の問題点に鑑みてなされたものであり、画像検索の精度を維持しながら、計算コストやメモリ使用量を低減させることが可能な画像検索システムを提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明の第１の態様は、画像検索システムであり、この画像検索システムは、クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を生成する局所画像特徴量群生成部と、前記局所画像特徴量群から、前記クエリ画像の全体の特徴を示す全体画像特徴量を生成する全体画像特徴量生成部と、複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存部と、前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存部と、前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索部と、前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記候補画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索部とを備えた構成を有している。
【００２１】
この構成により、まず全体画像特徴量を用いてすべての参照画像について粗い検索を行って候補画像を決定し、その後に候補画像について局所画像特徴量を用いた精度の高い検索を行うので、すべての参照画像について局所画像特徴量を用いた検索を行う場合と比較して、検索精度を犠牲にすることなく計算量を大幅に削減することができる。
【００２２】
本発明の第２の態様は、前記一次画像検索部は、前記クエリ画像の全体画像特徴量と距離の近い全体画像特徴量を有する参照画像を、前記候補画像として決定することを特徴とする第１の態様の画像検索システムである。この構成により、全体画像特徴量を用いて適切に候補画像を決定できる。
【００２３】
本発明の第３の態様は、前記二次画像検索部は、前記クエリ画像の局所画像特徴量にマッチングする前記局所特徴量を多く有する前記候補画像を前記対応画像として決定することを特徴とする第１又は第２の態様の画像検索システムである。この構成により、局所画像特徴量を用いて精度の高い検出を行うことができる。
【００２４】
本発明の第４の態様は、前記複数の参照画像を保存する参照画像保存部をさらに備え、前記画像検索システムは、前記参照画像保存部に保存された参照画像から、前記対応画像を読み出すことを特徴とする第１ないし第３のいずれかの態様の画像検索システムである。この構成により、クエリ画像に対応する参照画像が得られる。
【００２５】
本発明の第５の態様は、前記クエリ画像及び前記参照画像の全体画像特徴量は、それぞれ前記クエリ画像及び前記参照画像の複数の前記局所画像特徴量をヒストグラムにすることにより得られることを特徴とする。第１ないし第４のいずれかの態様の画像検索システムである。この構成により、クエリ画像及び参照画像の全体の特徴を好適に示す全体画像特徴量が得られる。具体的には、全体画像特徴量は、ＢＡＧ−ＯＦ−ＷＯＲＤＳであってよい。
【００２６】
本発明の第６の態様は、前記クエリ画像及び前記参照画像の全体画像特徴量は、それぞれ前記クエリ画像及び前記参照画像の複数の前記局所画像特徴量をガウス混合モデルでクラスタリングすることにより得られることを特徴とする第１ないし第４のいずれかの態様の画像検索システムである。この構成によっても、クエリ画像及び参照画像の全体の特徴を好適に示す全体画像特徴量が得られる。具体的には、全体画像特徴量は、フィッシャーベクトルであってよい。
【００２７】
本発明の第７の態様は、前記クエリ画像及び前記参照画像の全体画像特徴量は、それぞれ前記クエリ画像及び前記参照画像の複数の前記局所画像特徴量をｋ−ｍｅａｎｓ法でクラスタリングすることにより得られることを特徴とする第１ないし第４のいずれかの態様の画像検索システムである。この構成によっても、クエリ画像及び参照画像の全体の特徴を好適に示す全体画像特徴量が得られる。具体的には、全体画像特徴量は、ＶＬＡＤ特徴量であってよい。
【００２８】
本発明の第８の態様は、前記局所画像特徴量群生成部は、実数ベクトルで構成された局所画像特徴量をバイナリコードに変換して、前記局所画像特徴量群を生成し、前記局所画像特徴量群保存部は、バイナリコードに変換された局所画像特徴量からなる局所画像特徴量群を保存することを特徴とする第１ないし第７のいずれかの態様の画像検索システムである。この構成により、局所画像特徴量による選択画像の決定を高速化できる。
【００２９】
本発明の第９の態様は、前記全体画像特徴量群生成部は、実数ベクトルで構成された全体画像特徴量をバイナリコードに変換して、前記全体画像特徴量を生成し、前記全体画像特徴量群保存部は、バイナリコードに変換された全体画像特徴量を保存することを特徴とする第１ないし第８のいずれかの態様の画像検索システムである。この構成により、全体画像特徴量による対応画像の決定を高速化できる。
【００３０】
本発明の第１０の態様は、前記二次画像検索部は、前記候補画像の局所画像特徴量群と、前記クエリ画像の局所画像特徴量群との間で局所画像特徴量が類似する特徴点の組の個数を数え上げ、前記組の個数に基づいて前記対応画像を決定することを特徴とする第１ないし第９のいずれかの態様の画像検索システムである。この構成により、局所画像特徴量を用いて精度の高い対応画像の決定を行うことができる。
【００３１】
本発明の第１１の態様は、前記二次画像検索部は、前記候補画像の局所画像特徴量群と、前記クエリ画像の局所画像特徴量群との類似する局所画像特徴量の組の個数を数え上げ、前記組の個数に基づいて前記候補画像の中から選択画像を選択し、前記選択画像と前記クエリ画像との間で画像上での位置が特定の射影関係にある特徴点の組の個数を数え上げ、前記特定の射影関係にある特徴点の組の個数が最も多い選択画像を前記対応画像として決定することを特徴とする第１ないし第９のいずれかの態様の画像検索システムである。この構成により、アウトライアを除去することで精度の高い対応画像の決定を行うことができる。
【００３２】
本発明の第１２の態様は、画像検索装置であって、この画像検索装置は、クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を生成する局所画像特徴量群生成部と、前記局所画像特徴量群から、前記クエリ画像の全体の特徴を示す全体画像特徴量を生成する全体画像特徴量生成部と、複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存部と、前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存部と、前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索部と、前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記候補画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索部とを備えた構成を有している。
【００３３】
この構成によっても、まず全体画像特徴量を用いてすべての参照画像について粗い検索を行って候補画像を決定し、その後に候補画像について局所画像特徴量を用いた精度の高い検索を行うので、すべての参照画像について局所画像特徴量を用いた検索を行う場合と比較して、検索精度を犠牲にすることなく計算量を大幅に削減することができる。
【００３４】
本発明の第１３の態様は、検索サーバ装置であって、この検索サーバ装置は、クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群と、前記クエリ画像の全体の特徴を示す全体画像特徴量とを取得するクエリ情報取得部と、複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存部と、前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存部と、前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索部と、前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記候補画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索部とを備えた構成を有している。
【００３５】
この構成によっても、まず全体画像特徴量を用いてすべての参照画像について粗い検索を行って候補画像を決定し、その後に候補画像について局所画像特徴量を用いた精度の高い検索を行うので、すべての参照画像について局所画像特徴量を用いた検索を行う場合と比較して、検索精度を犠牲にすることなく計算量を大幅に削減することができる。
【００３６】
本発明の第１４の態様は、画像検索方法であって、この画像検索方法は、クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群及び前記クエリ画像の全体の特徴を示す全体画像特徴量を取得するクエリ情報取得ステップと、複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存ステップと、前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存ステップと、前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索ステップと、前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記候補画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索ステップとを含む構成を有している。
【００３７】
この構成によっても、まず全体画像特徴量を用いてすべての参照画像について粗い検索を行って候補画像を決定し、その後に候補画像について局所画像特徴量を用いた精度の高い検索を行うので、すべての参照画像について局所画像特徴量を用いた検索を行う場合と比較して、検索精度を犠牲にすることなく計算量を大幅に削減することができる。
【００３８】
本発明の第１５の態様は、画像検索プログラムであって、この画像検索プログラムは、コンピュータを、クエリ画像中の複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群及び前記クエリ画像の全体の特徴を示す全体画像特徴量を取得するクエリ情報取得部、複数の参照画像の各々について、複数の特徴点の各々の局所画像特徴量からなる局所画像特徴量群を保存する局所画像特徴量群保存部、前記複数の参照画像の各々について、各参照画像の全体の特徴を示す全体画像特徴量を保存する全体画像特徴量保存部、前記クエリ画像の全体画像特徴量と前記全体画像特徴量保存部に保存された前記参照画像の全体画像特徴量との比較に基づいて、前記参照画像の中から、前記クエリ画像に対応する対応画像の候補となる候補画像を決定する一次画像検索部、及び前記クエリ画像の局所画像特徴量と前記局所画像特徴量群保存部に保存された前記候補画像の局所画像特徴量との比較に基づいて、前記候補画像の中から、前記対応画像を決定する二次画像検索部として機能させる構成を有している。
【００３９】
この構成によっても、まず全体画像特徴量を用いてすべての参照画像について粗い検索を行って候補画像を決定し、その後に候補画像について局所画像特徴量を用いた精度の高い検索を行うので、すべての参照画像について局所画像特徴量を用いた検索を行う場合と比較して、検索精度を犠牲にすることなく計算量を大幅に削減することができる。
【発明の効果】
【００４０】
本発明によれば、まず全体画像特徴量を用いてすべての参照画像について粗い検索を行って候補画像を決定し、その後に候補画像について局所画像特徴量を用いた精度の高い検索を行うので、すべての参照画像について局所画像特徴量を用いた検索を行う場合と比較して、検索精度を犠牲にすることなく計算量を大幅に削減することができる。
【図面の簡単な説明】
【００４１】
【図１】本発明の実施の形態における画像検索システムの構成を示すブロック図
【図２】本発明の実施の形態における局所画像特徴量群生成部の構成を示すブロック図
【図３】本発明の実施の形態における全体画像特徴量生成部の構成を示すブロック図
【図４】本発明の実施の形態における二次画像検索部の構成を示すブロック図
【図５】本発明の実施の形態における比較マッチングの例を示す図
【図６】本発明の実施の形態における変換行列の算出のフロー図
【発明を実施するための形態】
【００４２】
以下、本発明の実施の形態の画像検索システムについて、図面を参照しながら説明する。なお、以下に説明する実施の形態は、本発明を実施する場合の一例を示すものであって、本発明を以下に説明する具体的構成に限定するものではない。本発明の実施にあたっては、実施の形態に応じた具体的構成が適宜採用されてよい。
【００４３】
図１は、本発明の実施の形態の画像検索システムの構成を示す図である。画像検索システム１００は、クエリ画像処理装置１０と、検索サーバ装置２０とを備えている。クエリ画像処理装置１０と検索サーバ装置２０とは、ネットワークＮＷを介して通信可能に接続されている。ネットワークＮＷの一部は無線であってよい。クエリ画像処理装置１０は携帯情報端末であってよく、アプリケーションプログラムが実行されることで図１に示す構成が実現されてもよい。また、検索サーバ装置２０についても、プログラムが実行されることで、図１に示す構成が実現されてよい。
【００４４】
クエリ画像装置１０は、検索したい画像を撮影して、それをクエリ画像として検索サーバ装置２０に送信するとともに、検索サーバ装置２０から当該クエリ画像に対応する対応画像及び／又は対応画像に関連付けられた関連情報を取得する装置である。検索サーバ装置２０は、クエリ画像処理装置１０からクエリ画像を受信すると、そのクエリ画像に含まれる被写体に対応する被写体を含む対応画像を検索して、検索された対応画像及び／又は検索された対応画像に関連付けられた関連情報を当該クエリ画像に関する情報としてクエリ画像処理装置１０に送信する。
【００４５】
検索画像システム１００は、検索サーバ装置２０に保存する画像及びそれに付随させる関連情報の如何によって様々な応用が可能である。本実施の形態では、画像検索システム１００がポスターを検索するためのシステムとして応用される例を説明する。即ち、検索サーバ装置２０には、参照画像として複数のポスターの画像が保存されており、かつ各ポスターの画像には当該ポスターに関連する関連情報が関連付けられている。
【００４６】
ユーザは、クエリ画像処理装置１０にてポスター画像を撮影して、その画像をクエリ画像として検索サーバ装置２０に送信すると、検索サーバ装置２０では、当該撮影されたポスターの画像に対応する画像が検索され、検索された画像及びそれに関連付けられた関連情報がクエリ画像処理装置１０に返信される。
【００４７】
なお、画像検索システム１００の応用例はこれに限られない。例えば、検索サーバ２０に大量の書籍の表表紙の画像を参照画像として保存しておき、各保存画像に関連情報として各書籍のユーザレビュー、購入のための情報、関連する他の書籍等の情報を付随させておくことで、画像検索システム１００を書籍検索システムとして応用できる。また、検索サーバ装置２０に、参照画像として各観光地に特有の建造物等の画像を保存し、かつ、関連情報としてその建造物の解説を保存しておくことで、画像検索システム１００を観光地案内システムとして応用できる。さらに、検索サーバ２０に、参照画像として野鳥の画像を保存し、かつ、関連情報としてその野鳥の解説を記載したウェブページのＵＲＬを保存しておくことで、画像検索システム１００を野鳥検索システムとして応用できる。
【００４８】
クエリ画像処理装置１０は、撮像部１１と、局所画像特徴量群生成部１２と、全体画像特徴量生成部１３と、通信部１４とを備えている。撮像部１１は、光学系、撮像素子、信号処理回路等からなる一般的なカメラユニットである。撮像部１１は、光学系を通して撮像素子で被写体を撮影し、信号処理回路で信号処理を行い、局所画像特徴量群生成部１２に画像信号（以下、単に「画像」という。）を出力する。
【００４９】
図２は、局所画像特徴量群生成部１２の構成を示すブロック図である。局所画像特徴量群生成部１２は、特徴点検出部１２１と、局所画像特徴量抽出部１２２と、バイナリ変換部１２３とを備えている。撮像部１１による撮影によって生成された画像は、特徴点検出部１２１に入力される。
【００５０】
特徴点検出部１２１は、入力画像から特徴点を検出する。特徴点検出部１２１は、画像からエッジを抽出してエッジ画像を生成し、そのエッジ画像から特徴点を検出する。一般的には、１つの画像からは複数の特徴点が検出される。特徴点を検出するアルゴリズムとして、既存の任意のものを採用できる。特徴点検出部１２１は、検出したすべての特徴点について、特徴点を識別する情報、画像内での特徴点の位置情報を含む特徴点情報を局所画像特徴量抽出部１２２に出力する。なお、特徴点の位置の情報は、特徴点のＸ座標及びＹ座標であり、Ｘ座標及びＹ座標の値は入力画像の１画素を１単位とする。
【００５１】
局所画像特徴量抽出部１２２は、特徴点検出部１２１にて検出された複数の特徴点の各々の局所画像特徴量を抽出する。局所画像特徴量を抽出する方法としては、既知の技術を用いることが可能であり、例えば、局所画像特徴量を１２８次元のベクトルとして算出する方法として、ＳＩＦＴ特徴量を利用する方法（David G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, 60, 2 (2004), pp.91-110.参照）などを用いることができる。局所画像特徴量抽出部１２２において、局所画像特徴量は、単精度実数のベクトルとして求められる。局所画像特徴量抽出部１２２は、各特徴点について、その識別情報とともに、抽出された複数の局所画像特徴量をバイナリ変換部１２３及び全体画像特徴量生成部１３に出力する。
【００５２】
バイナリ変換部１２３は、検出されたすべての特徴点について、それらの局所画像特徴量をバイナリコードに変換する。局所画像特徴量抽出部１２２にて抽出された局所画像特徴量は１２８次元のベクトルｖ∈Ｒ128であるので、バイナリ変換部１２３は、この局所画像特徴量を下式（１）でバイナリコードに変換する。
【数１】
2015111339.tif 000003
【００５３】
但し、式（１）において、ｄは変換後のバイナリコードのサイズ（即ちビット数）であり、ｓｇｎ関数は、下式（２）で与えられる。
【数２】
2015111339.tif 000004
また、ベクトルｗkは、１２８次元における半径１の超球上の点から、正規分布に従ってランダムサンプリングをして得られるベクトルである。ｗk（ｋ＝１，・・・，ｄ）は、１２８行ｄ列の行列として表現できる。本実施の形態では、バイナリコードのビット長を１２８ビットとし、即ちｄ＝１２８とする。バイナリ変換部１２３は、複数の特徴点の各々について、その特徴点情報とともに、バイナリコードに変換された局所画像特徴量を全体画像特徴量生成部１３及び通信部１４に出力する。この１つの画像に含まれる複数の特徴点についての複数の局所画像特徴量を「局所画像特徴量群」という。
【００５４】
図３は、全体画像特徴量生成部１３の構成を示すブロック図である。全体画像特徴量生成部１３は、ＶＬＡＤ特徴量生成部１３１と、バイナリ変換部１３２とを備えている。ＶＬＡＤ特徴量生成部１３１は、１枚の画像から得られる局所画像特徴量をすべて用いて、１つの全体画像特徴量を生成する。本実施の形態では、ＶＬＡＤ特徴量生成部１３１にて全体画像特徴量としてＶＬＡＤと呼ばれる特徴量を生成する。しかし、本発明において、全体画像特徴量として必ずしもＶＬＡＤを採用しなくてもよい。
【００５５】
全体画像特徴量生成部１３は、あらかじめ、多数の画像を用いて生成したクラスタ情報を生成する。このために、全体画像特徴量生成部１３は、多数の画像から大量の局所画像特徴量を生成し、それをｋ−ｍｅａｎｓ法を用いてクラスタリングする。本実施の形態では、ｋ−ｍｅａｎｓ法を用いるにあたって、あらかじめ決めなければならないクラスタ数を６４とする。その結果、大量の局所画像特徴量を代表する６４個のセントロイドｃ1，・・・ｃ64が得られる。ここで、ｃkは局所画像特徴量と同じ次元、即ち１２８次元となる。全体画像特徴量生成部１３は、これをクラスタ情報として使用する。
【００５６】
全体画像特徴量生成部１３は、クエリ画像から得られた局所画像特徴量群に含まれる局所画像特徴量の各々に下式（３）の計算を適用して、ＶＬＡＤ特徴量を算出する。ＶＬＡＤ特徴量は、６４×１２８次元のベクトルＶとなる。ベクトルＶは、Ｖ＝［Ｖ1，・・・，Ｖ64］と表現され、ここで、Ｖiの次元は１２８次元である。このＶiをＶのサブベクトルと呼ぶ。式（３）において、ｖは、局所画像特徴量群生成部１２にてクエリ画像から生成された局所画像特徴量群に含まれる局所画像特徴量である。局所画像特徴量群に含まれる特徴量数をＮとすると、１≦ｉ≦Ｎとなる。
【数３】
2015111339.tif 000005
なお、式（３）のＮＮ（ｖ）＝ｃkは、セントロイド｛ｃ1，ｃ2，…，ｃk，…，ｃ64｝の中でもｃkが最も近いようなｖを意味する。ＶＬＡＤ特徴量生成部１３１は、生成したＶＡＬＤ特徴量をバイナリ変換部１３２に出力する。
【００５７】
バイナリ変換部１３２は、後述の一次画像検索手段の処理を高速化するため、ＶＬＡＤ特徴量生成部１３１にて生成されたＶＬＡＤ特徴量を下式（４）によってバイナリコードに変換する。
【数４】
2015111339.tif 000006
ここで、ｂiは変換後のバイナリコードであり、変換後のバイナリコードの長さを１２８ビットとすると、ＶＬＡＤ特徴量は、１２８次元の０あるいは１の要素を持つベクトルに変換される。Ｒは正規分布から発生させた乱数を要素に持つ１２８×１２８次元の行列である。Ｏiはオフセットベクトルである。オフセットベクトルＯiは、あらかじめ多数の画像から多数のＶＬＡＤ特徴量を計算しておき、Ｖ＝［Ｖ1，・・・，Ｖ64］のそれぞれのサブベクトルごとに平均を取ることで生成しておく。
【００５８】
バイナリ変換部１３２は、以上の処理によって、ＶＬＡＤ特徴量Ｖ＝［Ｖ1，・・・，Ｖ64］をバイナリコードｂ＝［ｂ1，・・・，ｂ64］に変換する。このバイナリコードｂは、本実施の形態では、１２８×６４＝８１９２次元となり、従って８１９２次元の０又は１の要素からなるベクトルとなる。バイナリ変換部１３２は、このバイナリコードｂを全体画像特徴量として、通信部１４に出力する。
【００５９】
図１に戻って、通信部１４は、ネットワークＮＷを介して、局所画像特徴量群生成部１２で生成されたクリエ画像の局所画像特徴量群、及び全体画像特徴量生成部１３で生成されたクエリ画像の全体画像特徴量、及び特徴点情報を含むクエリ情報を検索サーバ装置２０に送信する。
【００６０】
なお、以上の撮像部１１、局所画像特徴量群生成部１２、全体画像特徴量生成部１３、及び通信部１４による一連の処理は、撮像部１１でレリーズ操作（撮影操作）が行われたタイミングで、それによって生成された１つの画像について行ってもよいし、過去に撮像部１１にて生成された画像が図示しないストレージに保存されており、ユーザが保存された画像を選択して指示することで、局所画像特徴量群生成部１２、全体画像特徴量生成部１３、及び通信部１４による上述の処理がなされてもよい。また、撮像部１１で連続的にプレビュー動画が生成され、そのプレビュー動画の各フレーム画像をクエリ画像として、局所画像特徴量群生成部１２、全体画像特徴量生成部１３、及び通信部１４による上述の処理が順次なされてもよい。
【００６１】
次に、検索サーバ装置２０について説明する。検索サーバ装置２０は、参照画像のデータベースを構築するための構成として、局所画像特徴量群生成部２１、全体画像特徴量生成部２２、及び画像データベース２３を備えている。画像データベース２３は、複数の参照画像を保存する参照画像保存部２３１、複数の参照画像の各々の局所画像特徴量群を保存する局所画像特徴量群保存部２３２、複数の参照画像の各々の全体画像特徴量を保存する全体画像特徴量保存部２３３、及び参照画像の関連情報を保存する関連情報保存部２３４からなる。
【００６２】
局所画像特徴量群生成部２１は、複数の参照画像の各々について、特徴点を検出して、各特徴点の局所画像特徴量からなる局所画像特徴量群を生成する。その構成は、図２を用いて説明したクエリ画像処理装置１０の局所画像特徴量群生成部１２の構成と同じである。局所画像特徴量群生成部２１にて生成された複数の参照画像の各々の特徴点情報及び局所画像特徴量群は、全体画像特徴量生成部２２に出力されるとともに、画像データベース２３の局所画像特徴量群保存部２３２に保存される。なお、複数の参照画像は、通信部２４を介して外部から取得されてよく、あるいは他の方法によって取得されてもよい。
【００６３】
全体画像特徴量生成部２２は、局所画像特徴量群生成部２１にて生成された局所画像特徴量群について、全体画像特徴量を生成する。その構成は、図３を用いて説明したクエリ画像処理装置１０の全体画像特徴量生成部１３の構成と同じである。全体画像特徴量生成部２２にて生成された複数の参照画像の各々の全体画像特徴量は、画像データベース２３の全体画像特徴量保存部２３３に保存される。
【００６４】
画像データベース２３では、各参照画像について、その画像データ、局所画像特徴量群、全体画像特徴量、特徴点情報、及び関連情報のデータが関連付けられて記憶されている。なお、画像データ及び関連情報データは、別の保存手段に保存され、識別情報等によって画像データベース２３に保存されたその他のデータと紐付けられていてもよい。
【００６５】
ここで、関連情報とは、画像検索の結果の１つとしてクエリ画像処理装置１０に返信される情報である。本実施の形態の画像検索システム１００は、上述のようにポスター画像を検索するものであり、関連情報としては、そのポスターによる告知の詳細内容ないし、そのような詳細内容を掲示したウェブサイトへのアクセス方法（ＵＲＬ等）が含まれる。即ち、クエリ画像処理装置１０のユーザは、例えば、街中であるポスターを見かけたときに、そのポスターを撮影してその画像をクエリ画像として検索サーバ装置２０に詳細内容をリクエストすると、検索サーバ装置２０は、そのクエリ画像に対応する参照画像を検索して、検出された参照画像に関連付けられた関連情報をユーザに返信する。これによって、ユーザは、撮影したポスターの詳細内容を知ることができる。
【００６６】
検索サーバ装置２０は、さらに画像検索を行うための構成として、通信部２４、一次画像検索部２５、及び二次画像検索部２６を備えている。通信部２４は、クエリ画像処理装置１０から送信されてきたクエリ情報（局所画像特徴量群、全体画像特徴量、及び特徴点情報を含む）を受信する。
【００６７】
一次画像検索部２５は、参照画像の中からクエリ画像に近しい画像を検索する。このために、一次画像検索部２５は、全体画像特徴量保存部２３３を参照して、通信部２４にて取得したクエリ画像の全体画像特徴量との相違が所定の閾値以下である全体画像特徴量を有する参照画像を候補画像として検索する。なお、上述のように本実施の形態では、クエリ画像及び参照画像の全体画像特徴量はいずれもバイナリコードである。
【００６８】
一次画像検索部２５は、クエリ画像の全体画像特徴量（バイナリコード）と、すべての参照画像の各々の全体画像特徴量（バイナリコード）とのハミング距離を求めて、得られたハミング距離を昇順に並び替える。なお、仮に全体画像特徴量のみで判断すると、一次画像検索部２５においてハミング距離が最も小さい参照画像がクエリ画像に似ている画像（検索すべき画像）と判定されることになる。サーバ検索装置２０は、上述のように、すべての参照画像について、全体画像特徴量を保存しているのみではなく、局所画像特徴量も保存している。
【００６９】
そこで、本実施の形態の検索サーバ装置２０は、全体画像特徴量のみで直ちにクエリ画像に最も似ている参照画像をそのクエリ画像の対応画像として決定するのではなく、参照画像のうち、クエリ画像との間の全体画像特徴量のハミング距離が小さい順から上位数件（本実施の形態では５件）を候補画像として選出し、これらの候補画像について、さらに局所画像特徴量を用いた精密な判断を行う。このために、一次画像検索部２５は、昇順に並び替えられたハミング距離のリストから上位５件を候補画像として選出し、これらの候補画像を特定する情報を二次画像検索部２６に出力する。
【００７０】
二次画像検索部２６は、一次画像検索部２５から一次画像検索の結果である候補画像の情報を取得して、それらの候補画像の局所画像特徴量群を局所画像特徴量群保存部２３２から読み出す。二次画像検索部２６は、候補画像の中からクエリ画像に対応する対応画像を決定する。
【００７１】
図４は、二次画像検索部２６の構成を示すブロック図である。二次画像検索部２６は、比較マッチング部２６１、変換行列算出部２６２、及び射影判定部２６３を備えている。二次画像検索部２６は、比較マッチング部２６１において、クエリ画像の局所画像特徴量群と、複数の候補画像の各々の局所画像特徴量群とを比較して、その一致度を求める。この一致度が最も高いものをクエリ画像に対応する対応画像であると決定することもできる。しかしながら、本実施の形態では、さらに、変換行列算出部２６２及び射影判定部２６３において、比較マッチング部２６１における比較マッチングの結果の正当性を確認することで、対応画像を決定する精度を向上させている。
【００７２】
まず、比較マッチング部２６１について説明する。比較マッチング部２６１は、通信部２４にて受信したクエリ画像の局所画像特徴量群と、局所画像特徴量群保存部２３２に保存されているすべての候補画像の局所画像特徴量群に含まれる局所画像特徴量とを比較して、クエリ画像の局所画像特徴量群に含まれる局所画像特徴量の各々について、候補画像の局所画像特徴量群に含まれる局所画像特徴量のうち、最も距離の近い（すなわち、一致度が最も高い）ものを探索する。クエリ画像及び候補画像の局所画像特徴量はいずれも同じビット数にバイナリコード化されているので、それらのハミング距離を計算することで高速に一致度を計算できる。
【００７３】
比較マッチング部２６１は、特徴点の位置に関わらず、一致度が最も高い特徴点の組、換言すれば局所画像特徴量の差が最も小さい特徴点の組を対応点としてカウントする。こうすることで、クエリ画像のすべての特徴点がいずれかの候補画像のいずれかの特徴点と対応すると判断され、即ちクエリ画像のすべての特徴点がいずれかの候補画像に投票されることになる。
【００７４】
図５は、比較マッチング部２６１における比較マッチングの例を示す図である。図５の例では、クエリ画像Ｑから１１個の特徴点が検出されてその局所画像特徴量が抽出され、候補画像Ｃ１〜Ｃ４において、それぞれ図５に示す特徴点が検出されてその局所画像特徴量が抽出されている。なお、実際には１つの画像からは数百の特徴点が検出されるが、図５の例では説明の簡略化のために少数の特徴点を示している。
【００７５】
図５において、一致度が最も高い特徴点（以下、単に「対応点」という。）の組を線で連結して示している。図５の例では、候補画像Ｃ１〜Ｃ３から、それぞれ５点、２点、４点の対応点が検出され、候補画像Ｃ４からは対応点は検出されていない。比較マッチング部２６１は、対応点の数が所定の数以上である画像を選択画像として選択する。図５の例では、比較マッチング部２６１は、対応点の数が３以上である候補画像を選択画像として選択する。その結果、候補画像Ｃ１及びＣ３が選択画像として選択される。
【００７６】
これらの選択画像の対応点について、変換行列算出部２６２及び射影判定部２６３の処理で、位置情報も対応関係に基づいて真の対応点であるか否かの判定がされ、真の対応点であると判定された対応点の数が最も多い選択画像が、クエリ画像の対応画像であると決定される。具体的には、変換行列算出部２６２及び射影判定部２６３は、クエリ画像の局所画像特徴量群と、選択画像の各々の局所画像特徴量群とについて、インライア数の計算を行って、各選択画像の局所画像特徴量群のインライア数を求める。
【００７７】
変換行列算出部２６２は、あらかじめ設定した閾値よりインライア数が大きく、かつインライア数が最も大きい候補画像をクエリ画像の対応画像であると判断する。このとき、二次画像検索部２６は、すべての選択画像についてあらかじめ設定した閾値よりもインライア数が低い場合は、クエリ画像に対応する対応画像はないと判断する。
【００７８】
変換行列算出部２６２及び射影判定部２６３は、以下のようにしてインライア数の計算を行う。まず、変換行列算出部２６２は、選択画像ごとに、対応点を射影するための変換行列を算出する。変換行列算出部２６２は、ＲＡＮＳＡＣ法を用いて、変換行列としてホモグラフィ行列を算出する。具体的には以下のとおりである。
【００７９】
図６は、変換行列算出部２６２における変換行列の算出のフロー図である。変換行列算出部２６２は、選択画像ごとに、図６のフロー図の処理を行い、選択画像ごとに変換行列を求める。いま、クエリ画像とある選択画像との間に対応点がｎ組あるとし、クエリ画像の対応点をａi（ｘi，ｙi）、選択画像の対応点をＡi（Ｘi，Ｙi）とする（ｉ＝１〜ｎ）。このとき、被写体が２次元平面であると仮定すると、以下の（５）を満たす変換行列Ｈが存在する。
【数５】
2015111339.tif 000007
【００８０】
式（５）を展開すると、以下の式（６）が得られる。
【数６】
2015111339.tif 000008
式（６）においてｗを消去すると以下の式（７）の連立方程式が得られる。
【数７】
2015111339.tif 000009
【００８１】
１組の対応点の組について、上記の式（７）の連立方程式が得られることから、４組の対応点の組があれば８つの連立方程式が得られ、これを解くことで変換行列Ｈに含まれる８つの要素（ｈ11、ｈ12、ｈ13、ｈ21、ｈ22、ｈ23、ｈ31、ｈ32）を求めることができる。
【００８２】
そこで、変換行列算出部２６２は、クエリ画像と選択画像との間のｎ組の対応点から任意の４組の対応点を選択して、上記のとおりに変換行列Ｈを求める（ステップＳ６１）。次に、変換行列算出部２６２は、この変換行列Ｈを用いて、ｎ組のすべての対応点の組について、射影誤差を求める（ステップＳ６２）。具体的には、以下の式（８）によって、各対応点の組の射影誤差ｅiを算出する。
【数８】
2015111339.tif 000010
【００８３】
次に、変換行列算出部２６２は、各対応点について、各射影誤差ｅiが所定の閾値（許容誤差）より小さいインライア（ｉｎｌｉｅｒ）か、各射影誤差ｅiが所定の閾値以上であってアウトライア（ｏｕｔｌｉｅｒ、外れ値）であるかを判定し、インライアの総数をカウントし、インライアの総数が増加したか否かを判断する（ステップＳ６３）。インライアの総数が増加したときは（ステップＳ６３でＹＥＳ）、変換行列算出部２６２は、そのときの変換行列Ｈで、変換行列Ｈを更新する（ステップＳ６４）。インライアの総数が増加していないときは（ステップＳ６３でＮＯ）、変換行列Ｈは更新しない。
【００８４】
次に、ステップＳ６１〜６４の処理が規定回数に達しているかを判断し（ステップＳ６５）、達していなければ（ステップＳ６５にてＮＯ）、ステップＳ６１〜Ｓ６３を繰り返す。規定回数に達した場合には（ステップＳ６５にてＹＥＳ）、変換行列算出部２６２は、そのときの変換行列Ｈを、クエリ画像を当該選択画像に変換するための変換行列と決定して出力する（ステップＳ６６）。
【００８５】
射影判定部２６３は、変換行列算出部２６２にて各選択画像について決定された変換行列Ｈでもって選択画像のすべての対応点を射影して、クエリ画像の対応点との間の射影誤差を求める。各対応点について、射影誤差が所定の閾値（許容誤差）より小さい（インライア）か、射影誤差が所定の閾値以上である（アウトライア）であるかを判定し、インライアの総数を最終的な対応点の数とする。インライアの対応点の組は、即ち幾何的整合性を満足する対応点の組である。射影判定部２６３は、このような処理をすべての選択画像について行って、最終的な対応点が最も多い選択画像を、クエリ画像中の被写体と同じ被写体を含む対応画像であると判定する。
【００８６】
射影判定部２６３は、対応画像であると判定した参照画像に関連付けられた関連情報を画像データベース２３の関連情報保存部２４４から読み出して、通信部２４に出力する。通信部２４は、クエリ画像処理装置１０に関連情報を送信する。これによって、クエリ画像処理装置１０のユーザは、自らが撮影した被写体に関する関連情報を検索サーバ装置２０から取得できる。
【００８７】
以上説明したとおり、本実施の形態では、クエリ画像のデータを送信してクエリ画像に関する関連情報を受信するクエリ画像処理装置１０、及びクエリ画像を受信してその対応画像を検索し、対応画像に関連付けられた関連情報をクエリ画像処理装置１０に返信する検索サーバ装置２０において、全体画像特徴量と局所画像特徴量を併用する構成を採用している。即ち、検索サーバ装置２０は、まず全体画像特徴量を用いてすべての参照画像について粗い検索を行って候補画像を抽出し、その後に候補画像について局所画像特徴量を用いた精度の高い検索を行う。これにより、すべての参照画像について局所画像特徴量を用いた検索を行う場合と比較して、検索精度を犠牲にすることなく計算量を大幅に削減することができ、検索速度が速くなる。
【００８８】
以下、上記の実施の形態に対する種々の変形例を説明する。
【００８９】
上記の実施の形態では、二次画像検索部２６は、比較マッチング部２６１による比較マッチングの結果から直ちに対応画像を決定せずに、比較マッチング部２６１で選択された複数の選択画像の各々についてインライア数を求めて、インライア数に基づいて、選択画像の中から対応画像を決定したが、必ずしもインライア数の評価を行わなくてもよい。この場合には、二次画像検索部２６は、クエリ画像の局所画像特徴量群に含まれる局所画像特徴量すべてについて、候補画像の局所画像特徴量群に含まれる最も距離が近い局所画像特徴量を計算するときに、最も近い距離と、２番目に近い距離の比が一定の値よりも大きいときは、近いと判定せず、その局所画像特徴量について組はなしと判定し、クエリ画像の局所画像特徴量群と、選択画像の局所画像特徴量群が成す組の数を計算し、組数が最も多い局所画像特徴群の組数が所定の閾値以上であるときに、この局所画像特徴量群を有する候補画像を対応画像であると判定してもよい。
【００９０】
上記の実施の形態では、サーバ検索装置２０の画像データベース２３には、バイナリコードに変換された局所画像特徴量及び全体画像特徴量を保存し、クエリ画像処理装置１０においても、クエリ画像の局所画像特徴量及び全体画像特徴量をバイナリコードに変換したが、局所画像特徴量及び全体画像特徴量のいずれか一方又は両方が、バイナリコードに変換されていなくてもよい。この場合には、Ｌ２ノルム等を用いて参照画像の特徴量とクエリ画像の特徴量との距離を評価できる。特に、上記の実施の形態によれば、すべての参照画像について、クエリ画像との間で局所画像特徴量を用いた検索を行う必要がないので、バイナリ変換されていない局所画像特徴量を用いたとしても、十分に高速度の検索が可能である。
【００９１】
また、上記の実施の形態では、局所画像特徴量をバイナリコードに変換したが、全体画像特徴量は、バイナリ変換されていない局所画像特徴量を用いて算出されたが、全体画像特徴量はバイナリ変換された局所画像特徴量を用いて算出されてもよい。
【００９２】
上記の実施の形態では、全体画像特徴量としてＶＬＡＤ特徴量を用いたが、全体画像特徴量として、ＢＡＧ−ＯＦ−ＷＯＲＤＳ（ＢＡＧ−ＯＦ−ＶＩＳＵＡＬ−ＷＯＲＤＳ、ＢＡＧ−ＯＦ−ＦＥＡＴＵＲＥともいう。）、フィッシャー（Ｆｉｓｈｅｒ）ベクトル等の他の特徴量を採用することも可能である。
【００９３】
全体画像特徴量としてＢＡＧ−ＯＦ−ＷＯＲＤＳを採用する場合、以下のようにして全体画像特徴量が計算される。なお、この場合、全体画像特徴量は６４次元のベクトルＢとなる。全体画像特徴量生成部１３，２２は、上記の６４個のセントロイドｃ1，・・・ｃ64を用いて、各特徴量ｖiについて、最も近いセントロイドを探し、近かったセントロイドがｃjである場合、ベクトルＢjの要素に１を加える。ベクトルＢは、特徴量のヒストグラムとなり、ベクトルＢの要素の総和は、特徴量の個数と等しくなる。このベクトルＢは、この総数で全体を除算し、正規化して利用する。
【００９４】
フィッシャーベクトルを全体画像特徴量とする場合は、全体画像特徴量生成部１３，２２は、セントロイドではなく、ＥＭアルゴリズムによって、あらかじめ計算した多数の局所画像特徴量をガウス混合モデルでクラスタリングする。このフィッシャーベクトルの計算方法は、"Fisher Kernels on Visual Vocabularies for Image Categorization", Florent Perronnin and Christopher Danceに詳しく説明されている。この計算の結果得られる全体画像特徴量は、本変形例の場合、１６４４７次元となる。この次元が大きすぎるため、主成分分析などの手法によってあらかじめ局所画像特徴量を次元削減してもよい。
【００９５】
また、検索サーバ装置２０は、最終的な対応点が最も多い参照画像を対応画像と判定するだけでなく、最終的な対応点の数が２番目、３番目、・・・に多い参照画像についても、最終的な対応点が最も多い参照画像とともに、又はクエリ画像処理装置１０からのリクエストに応じて、関連情報を画像データベース２３から読み出してクエリ画像処理装置１０に送信してよい。
【００９６】
また、上記の実施の形態では、比較マッチング部２６１において対応点が所定の数以上ある参照画像のみを選択画像として、位置情報のマッチングを行って、最終的な対応点を求めたが、対応点を少なくとも１つ含むすべての参照画像を選択画像としてもよい。
【００９７】
また、上記の実施の形態では、比較マッチング部２６１は、局所画像特徴量の差が最も小さい特徴点の組を対応点としてカウントしたが、比較マッチングの方法はこれに限られない。例えば、比較マッチング部２６１は、クエリ画像Ｑのすべての特徴点の局所画像特徴量と、選択画像Ｃ１〜Ｃ４に含まれるすべての特徴点の局所画像特徴量とを比較し、その一致度が所定の閾値を上回る特徴点の組、即ち局所画像特徴量の差が所定の誤差範囲内にある特徴点の組を検出してもよい。なお、この場合には、クエリ画像の１つの特徴点が、複数の候補画像に投票されることがあり、また、いずれの候補画像にも投票されないこともある。
【００９８】
また、上記の実施の形態では、変換行列Ｈは、選択画像の特徴点を射影する行列であり、選択画像の特徴点を変換行列Ｈで射影して、クエリ画像の対応する特徴点との射影誤差を評価したが、逆に、クエリ画像の特徴点を選択画像の特徴点に射影する行列を変換行列として、クエリ画像の特徴点を変換行列で射影して、選択画像の対応する特徴点との射影誤差を評価してもよい。
【００９９】
また、上記の実施の形態において、クエリ画像処理装置１０及び検索サーバ装置２０の各要素は、他の要素と別の装置に備えられてよく、クエリ画像処理装置１０の一部又は全部の要素と検索サーバ装置２０の一部又は全部の要素とが同一の装置に備えられて、画像検索装置が構成されてもよい。
【産業上の利用可能性】
【０１００】
本発明は、まず全体画像特徴量を用いてすべての参照画像について粗い検索を行って候補画像を決定し、その後に候補画像について局所画像特徴量を用いた精度の高い検索を行うので、すべての参照画像について局所画像特徴量を用いた検索を行う場合と比較して、検索精度を犠牲にすることなく計算量を大幅に削減することができるという効果を有し、大量の参照画像の中からクエリ画像に対応する対応画像を検索する画像検索システム等として有用である。
【符号の説明】
【０１０１】
１００  画像検索システム
１０  クエリ画像処理装置
１１  撮像部
１２  局所画像特徴量群生成部
１２１  特徴点検出部
１２２  局所画像特徴量抽出部
１２３  バイナリ変換部
１３  全体画像特徴量生成部
１３１  ＶＬＡＤ特徴量生成部
１３２  バイナリ変換部
１４  通信部
２０  検索サーバ装置
２１  局所画像特徴量群生成部
２２  全体画像特徴量生成部
２３  画像データベース
２３１  参照画像保存部
２３２  局所画像特徴量群保存部
２３３  全体画像特徴量保存部
２３４  関連情報保存部
２４  通信部
２５  一次画像検索部
２６  二次画像検索部
２６１  比較マッチング部
２６２  変換行列算出部
２６３  射影判定部
【図１】
2015111339.tif 000011
【図２】
2015111339.tif 000012
【図３】
2015111339.tif 000013
【図４】
2015111339.tif 000014
【図５】
2015111339.tif 000015
【図６】
2015111339.tif 000016