(57)【特許請求の範囲】
【請求項１】
端末及び物体検索サーバを有するシステムの物体検索方法であって、
前記物体検索サーバは、物体が写る参照画像を予め蓄積しており、
前記端末が、物体が写る質問画像における複数の特徴ベクトルを含む質問情報を、前記物体検索サーバへ送信する第１のステップと、
前記物体検索サーバが、前記質問情報の複数の特徴ベクトルと各参照画像との間の類似度を算出する第２のステップと、
前記物体検索サーバが、前記質問情報と複数の参照画像との間の類似度判定結果を、前記端末へ返信する第３のステップと、
前記端末が、受信した前記類似度判定結果に応じて、前記質問画像の座標情報を含む幾何情報を選択する第４のステップと、
前記端末が、選択された前記幾何情報を、前記物体検索サーバへ送信する第５のステップと、
前記物体検索サーバが、第２のステップで検索された複数の参照画像の中で、前記幾何情報の座標情報に所定閾値以上で類似する１つ以上の参照画像を検索する第６のステップと、
前記物体検索サーバが、第５のステップによって検索された各参照画像の参照画像ＩＤを、前記端末へ返信する第７のステップと
を有することを特徴とする物体検索方法。
【請求項２】
第１のステップについて、前記端末は、
物体が写る質問画像から、特徴ベクトル及び座標情報を含む局所特徴を抽出するステップと、
前記特徴ベクトルを量子化ベクトルに量子化するステップと、
複数の量子化ベクトルを含む質問情報を、前記物体検索サーバへ送信するステップと
を有し、
第２のステップについて、前記物体検索サーバは、
前記質問情報の複数の量子化ベクトルと各参照画像との間の類似度を算出する
ことを特徴とする請求項１に記載の物体検索方法。
【請求項３】
前記質問情報に含まれる前記量子化ベクトルは、Visual Word識別子である
ことを特徴とする請求項２に記載の物体検索方法。
【請求項４】
前記質問情報は、Visual Word識別子に対応付けて、方向及び／又はスケールを更に含む
ことを特徴とする請求項３に記載の物体検索方法。
【請求項５】
第３のステップについて、前記物体検索サーバが、前記類似度判定結果として、以下の３つのコマンドのいずれか１つを、前記端末へ返信し、
yes1：類似度が閾値TH1以上の参照画像が１つ以上ある
yes2：類似度が閾値TH1未満且つ閾値TH2以上の参照画像が１つ以上ある
no  ：全ての類似度がTH2未満である
閾値TH1：検索成功の可能性が極めて高い類似度の指標
閾値TH2：検索成功の可能性が比較的高い類似度の指標
第４のステップについて、前記端末が、前記類似度判定結果に応じて、前記物体検索サーバへ送信する前記幾何情報を以下のように制御する
yes1：幾何情報は、座標情報のみを含む
yes2：幾何情報は、座標情報及び特徴ベクトルを含む
no  ：検索失敗として、処理を終了する
ことを特徴とする請求項２から４のいずれか１項に記載の物体検索方法。
【請求項６】
第３のステップについて、前記物体検索サーバが、前記類似度判定結果として、３つ以上の閾値によって４つ以上のコマンドのいずれか１つを、前記端末へ返信し、
第４のステップについて、前記端末が、類似度判定結果に基づく閾値が低いほど、長い特徴ベクトル（特徴ベクトルの上位ビットのみ->全体ビット）を前記幾何情報に含める
ことを特徴とする請求項５に記載の物体検索方法。
【請求項７】
第６のステップについて、前記物体検索サーバは、
前記幾何情報の座標情報と、各参照画像の座標情報との間で、幾何的な所定条件を満たす特徴点対応組を算出し、
前記特徴点対応組の数が最大又は所定数以上となる参照画像を検索する
ことを特徴とする請求項１から６のいずれか１項に記載の物体検索方法。
【請求項８】
端末及び物体検索サーバを有するシステムであって、
前記端末は、
物体が写る質問画像における複数の特徴ベクトルを含む質問情報を、前記物体検索サーバへ送信する質問情報送信手段と、
受信した類似度判定結果に応じて、前記質問画像の座標情報を含む幾何情報を選択する幾何情報選択手段と、
選択された前記幾何情報を、前記物体検索サーバへ送信する幾何情報送信手段と
を有し、
前記物体検索サーバは、物体が写る参照画像を予め蓄積しており、
前記質問情報の複数の特徴ベクトルと各参照画像との間の類似度を算出する類似度算出手段と、
前記質問情報と複数の参照画像との間の類似度判定結果を、前記端末へ返信する類似度判定送信手段と、
前記類似度判定結果によって類似すると判定された複数の参照画像の中で、前記幾何情報の座標情報に所定閾値以上で類似する１つ以上の参照画像を検索する幾何検証手段と、
前記幾何検証手段によって検索された各参照画像の参照画像ＩＤを、前記端末へ返信する検索結果送信手段と
を有することを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、撮影画像に写る物体を検索する技術に関する。
【背景技術】
【０００２】
従来、画像から抽出された局所特徴を用いて物体を検索する技術がある（例えば非特許文献１参照）。この技術によれば、物体をカメラで撮影し、その物体が写る撮影画像（質問（クエリ）画像）から局所特徴ベクトルを抽出する。そして、質問画像の局所特徴ベクトルと、予め登録された物体が写る画像（参照（リファレンス）画像）の局所特徴ベクトルとを比較することによって、物体を検索する。また、類似度が上位Ｎ件の参照画像と質問画像との間で、幾何検証 (geometric verification)を実行することによって、検索精度を高めている。そして、幾何検証における条件を満たした特徴点対応組(inlier)の数を、新たな画像間類似度とする。 
【０００３】
これに対して、参照画像と質問画像との両方に同一の物体が含まれているか否かを、類似度に基づいて閾値で判定したい場合もある。画像間類似度の閾値が大きいほど、認識の適合率が高くなるためである。
【０００４】
図１は、従来技術における端末及び物体検索サーバの機能構成図である。
【０００５】
図１によれば、カメラ付き携帯端末を用いて、撮影画像に写る物体を検索するシステムである。携帯端末は、撮影画像から局所特徴ベクトルを抽出し、その局所特徴ベクトルを量子化する。一方で、物体検索サーバも、大量の参照画像か局所特徴ベクトルを抽出し、その局所特徴ベクトルを量子化し、その量子化ベクトルを画像ＩＤ毎に予め記憶する。携帯端末は、撮影画像の量子化ベクトルを含む質問情報を、ネットワークを介して物体検索サーバへ送信する。物体検索サーバは、その質問情報に最も類似する参照画像を検索し、その参照画像ＩＤを携帯端末へ返信する。これによって、携帯端末は、その撮影画像に写る物体は、その参照画像ＩＤに基づくものであると認識することができる。
【０００６】
このようなサービスをリアルタイムで実行するためには、端末からネットワークを介して検索サーバへ送信する質問情報のサイズが重要となる。データサイズが大きいほど、通信時間が長くなり、リアルタイム性が損なわれる。これに対し、検索に用いる局所特徴ベクトルのサイズを小さくすることによって、送信するデータサイズを削減する技術もある（例えば特許文献１参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】ＷＯ２０１３０７３６２２Ａ１
【非特許文献】
【０００８】
【非特許文献１】Philbin. J, Chum. O, Isard. M, Sivic. J, and Zisserman. A, “Object retrieval with large vocabularies and fast spatial matching,” In Computer Vision and Pattern Recognition, pp.1-8, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
特許文献１に記載の技術によれば、局所特徴ベクトルのサイズを削減することによって、ネットワークを介して転送されるデータサイズを削減しようとしている。一般に、局所特徴ベクトルの削減は、物体の検索精度の低下につながると考えられる。これに対し、本願の発明者らは、物体の検索精度を低下させることなく、ネットワークを介して転送されるデータサイズを削減することができないか？と考えた。特に、局所特徴の「座標情報」に対するデータサイズを削減することができないか？と考えた。
【００１０】
そこで、本発明は、撮影画像に写る物体を検索する際に、物体の検索精度を低下させることなく、ネットワークを介して転送される局所特徴のデータサイズを削減することができるシステム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明によれば、端末及び物体検索サーバを有するシステムの物体検索方法であって、
物体検索サーバは、物体が写る参照画像を予め蓄積しており、
端末が、物体が写る質問画像における複数の特徴ベクトルを含む質問情報を、物体検索サーバへ送信する第１のステップと、
物体検索サーバが、質問情報の複数の特徴ベクトルと各参照画像との間の類似度を算出する第２のステップと、
物体検索サーバが、質問情報と複数の参照画像との間の類似度判定結果を、端末へ返信する第３のステップと、
端末が、受信した類似度判定結果に応じて、質問画像の座標情報を含む幾何情報を選択する第４のステップと、
端末が、選択された幾何情報を、物体検索サーバへ送信する第５のステップと、
物体検索サーバが、第２のステップで検索された複数の参照画像の中で、幾何情報の座標情報に所定閾値以上で類似する１つ以上の参照画像を検索する第６のステップと、
物体検索サーバが、第５のステップによって検索された各参照画像の参照画像ＩＤを、端末へ返信する第７のステップと
を有することを特徴とする。
【００１２】
本発明の物体検索方法における他の実施形態によれば、
第１のステップについて、端末は、
物体が写る質問画像から、特徴ベクトル及び座標情報を含む局所特徴を抽出するステップと、
特徴ベクトルを量子化ベクトルに量子化するステップと、
複数の量子化ベクトルを含む質問情報を、物体検索サーバへ送信するステップと
を有し、
第２のステップについて、物体検索サーバは、
質問情報の複数の量子化ベクトルと各参照画像との間の類似度を算出する
ことも好ましい。
【００１３】
本発明の物体検索方法における他の実施形態によれば、
質問情報に含まれる量子化ベクトルは、Visual Word識別子であることも好ましい。
【００１４】
本発明の物体検索方法における他の実施形態によれば、
質問情報は、Visual Word識別子に対応付けて、方向及び／又はスケールを更に含むことも好ましい。
【００１５】
本発明の物体検索方法における他の実施形態によれば、
第３のステップについて、物体検索サーバが、類似度判定結果として、以下の３つのコマンドのいずれか１つを、端末へ返信し、
yes1：類似度が閾値TH1以上の参照画像が１つ以上ある
yes2：類似度が閾値TH1未満且つ閾値TH2以上の参照画像が１つ以上ある
no  ：全ての類似度がTH2未満である
閾値TH1：検索成功の可能性が極めて高い類似度の指標
閾値TH2：検索成功の可能性が比較的高い類似度の指標
第４のステップについて、端末が、類似度判定結果に応じて、物体検索サーバへ送信する幾何情報を以下のように制御する
yes1：幾何情報は、座標情報のみを含む
yes2：幾何情報は、座標情報及び特徴ベクトルを含む
no  ：検索失敗として、処理を終了する
ことも好ましい。
【００１６】
本発明の物体検索方法における他の実施形態によれば、
第３のステップについて、物体検索サーバが、類似度判定結果として、３つ以上の閾値によって４つ以上のコマンドのいずれか１つを、端末へ返信し、
第４のステップについて、端末が、類似度判定結果に基づく閾値が低いほど、長い特徴ベクトル（特徴ベクトルの上位ビットのみ->全体ビット）を幾何情報に含める
ことも好ましい。
【００１７】
本発明の物体検索方法における他の実施形態によれば、
第６のステップについて、物体検索サーバは、
幾何情報の座標情報と、各参照画像の座標情報との間で、幾何的な所定条件を満たす特徴点対応組を算出し、
特徴点対応組の数が最大又は所定数以上となる参照画像を検索する
ことも好ましい。
【００１８】
本発明によれば、端末及び物体検索サーバを有するシステムであって、
端末は、
物体が写る質問画像における複数の特徴ベクトルを含む質問情報を、物体検索サーバへ送信する質問情報送信手段と、
受信した類似度判定結果に応じて、質問画像の座標情報を含む幾何情報を選択する幾何情報選択手段と、
選択された幾何情報を、物体検索サーバへ送信する幾何情報送信手段と
を有し、
物体検索サーバは、物体が写る参照画像を予め蓄積しており、
質問情報の複数の特徴ベクトルと各参照画像との間の類似度を算出する類似度算出手段と、
質問情報と複数の参照画像との間の類似度判定結果を、端末へ返信する類似度判定送信手段と、
類似度判定結果によって類似すると判定された複数の参照画像の中で、幾何情報の座標情報に所定閾値以上で類似する１つ以上の参照画像を検索する幾何検証手段と、
幾何検証手段によって検索された各参照画像の参照画像ＩＤを、端末へ返信する検索結果送信手段と
を有することを特徴とする。
【発明の効果】
【００１９】
本発明のシステム及び方法によれば、撮影画像に写る物体を検索する際に、物体の検索精度を低下させることなく、ネットワークを介して転送される局所特徴のデータサイズを削減することができる。
【図面の簡単な説明】
【００２０】
【図１】従来技術における端末及び物体検索サーバの機能構成図である。
【図２】本発明における端末及び物体検索サーバの機能構成図である。
【図３】本発明における端末及び物体検索サーバ間のシーケンス図である。
【図４】転置インデックスを表す説明図である。
【図５】質問画像と参照画像との間のマッチングを表す説明図である。
【図６】質問画像と参照画像との間におけるＶＷＩＤ（量子化ベクトル）の類似度を表す説明図である。
【図７】質問画像と参照画像との間における幾何的な特徴点対応組を表す説明図である。
【図８】本発明における他のシステム構成図である。
【発明を実施するための形態】
【００２１】
以下、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２２】
図２は、本発明における端末及び物体検索サーバの機能構成図である。
図３は、本発明における端末及び物体検索サーバ間のシーケンス図である。
【００２３】
本発明は、端末１及び物体検索サーバ２を有するシステムによって、撮影画像に写る物体を検索することができる。端末１は、例えばスマートフォンや携帯電話機であって、一般的にカメラを搭載したものである。カメラに対するユーザ操作に応じて、様々な物体が写る撮影画像を取得することができる。一方で、物体検索サーバ２は、物体が写る参照画像を予め蓄積している。そして、端末１は、ネットワークを介して物体検索サーバ２と通信することによって、その撮影画像に写り込む物体を識別することができる。
【００２４】
図２によれば、端末１は、局所特徴抽出部１１と、量子化部１２と、幾何情報蓄積部１３と、質問情報送信部１４と、幾何情報選択部１５と、幾何情報送信部１６とを有する。これら機能構成部は、端末に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
また、端末１と通信する物体検索サーバ２は、局所特徴抽出部２１と、量子化部２２と、幾何情報蓄積部２３と、転置インデックス記憶部２４と、類似度算出部２５と、類似度判定送信部２６と、幾何検証部２７と、検索結果送信部２８とを有する。これら機能構成部は、サーバに搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００２５】
以下では、図３のシーケンスに沿って、図２の各機能構成部について説明する。
【００２６】
従来技術によれば、質問画像に写る物体の検索は、図１のように１段階のシーケンスで実行される。これに対し、本発明は、２段階のシーケンスで実行される。１段階目では、質問画像に対して、特徴ベクトル的に類似する複数の参照画像を検索し、２段階目で、それら参照画像の中で、幾何的に類似する参照画像を更に検索する。
【００２７】
＜Ｓ０１＞［端末１：局所特徴抽出部１１］
局所特徴抽出部１１は、カメラによる撮影画像を入力し、その画像における局所特徴を抽出する。局所特徴は、特徴点位置を、例えば以下の要素によって表す。
特徴ベクトル：f（例えば4byte）
座標：ｐ＝(x,y)（例えば4byte(ｘ(2byte)ｙ(2byte)）
方向：θ
スケール：ｓ
本発明によって抽出される局所特徴は、少なくとも特徴ベクトル及び座標情報を含む。
【００２８】
通常、１枚の画像から検出された局所特徴群は、配列上に格納され、その配列の添え字を「局所特徴ＩＤ」として識別する。また、局所特徴の特徴ベクトルｆは、量子化部１２へ出力される。
【００２９】
物体認識に用いる特徴ベクトルの抽出アルゴリズムとしては、例えばＳＩＦＴやＳＵＲＦ(Speeded Up Robust Features)、ＯＲＢ(Oriented FAST and Rotated BRIEF)が用いられる。例えば、ＳＩＦＴの場合、１枚の画像からは１２８次元の特徴ベクトルの集合が抽出される。ＳＩＦＴとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる特徴ベクトルを記述する技術である。一方で、ＳＵＲＦの場合、ＳＩＦＴよりも高速処理が可能であって、１枚の画像から６４次元の特徴ベクトルの集合が抽出される。ＯＲＢによれば、１つのコンテンツから２５６ビットのバイナリ局所特徴ベクトルの集合が抽出される。
【００３０】
＜Ｓ０２＞［端末１：量子化部１２］
量子化部１２は、局所特徴抽出部１１から特徴ベクトルfを入力する。また、量子化部１２は、Visual Word（ＶＷ）と称される複数の量子化ベクトルを予め記憶している。これら量子化ベクトルは、コードブックとして記憶されている。そして、量子化部１２は、特徴ベクトルｆに最も距離が近くなる（類似する）ＶＷのＩＤ（ＶＷＩＤ）へ量子化する。ここで、ＶＷＩＤは、最も近い１個であってもよいし、距離が近い上位Ｎ件のものであってもよい。特徴ベクトルｆ毎にＶＷＩＤを抽出し、それらＶＷＩＤ群は、量子化結果として、質問情報送信部１４へ出力される。
【００３１】
＜Ｓ０３＞［端末１：幾何情報蓄積部１３］
幾何情報蓄積部１３は、局所特徴抽出部１１から局所特徴群を入力する。そして、幾何情報蓄積部１３は、局所特徴ＩＤの順に、幾何情報をリスト構造で蓄積する。幾何情報は、座標情報ｐとマッチング情報とを結合したものである。マッチング情報は、ＶＷＩＤであってもよいし、特徴ベクトルであってもよい（特徴ベクトルの全体、特徴ベクトルの一部、又は、符号化された特徴ベクトルであってもよい）。尚、幾何情報蓄積部１３は、幾何情報の蓄積後、所定時間経過した際に、その幾何情報を破棄することも好ましい。
【００３２】
［物体検索サーバ２：局所特徴抽出部２１］
局所特徴抽出部２１は、物体が写る多数の参照画像を入力し、各参照画像における局所特徴を抽出する。その機能は、前述した端末１の局所特徴抽出部１１と全く同様である。抽出した特徴ベクトルは、量子化部２２へ出力される。
【００３３】
［物体検索サーバ２：量子化部２２］
量子化部２２は、局所特徴抽出部２１から特徴ベクトルfを入力し、コードブックを用いて、ＶＷＩＤへ量子化する。その機能は、前述した端末１の量子化部１２と全く同様である。量子化結果としてのＶＷＩＤの群は、幾何情報蓄積部２３及び転置インデックス記憶部２４へ出力される。
【００３４】
［物体検索サーバ２：幾何情報蓄積部２３］
幾何情報蓄積部２３は、局所特徴抽出部２１から局所特徴群を入力する。その機能は、前述した端末１の幾何情報蓄積部２３と全く同様である。
【００３５】
［物体検索サーバ２：転置インデックス記憶部２４］
転置インデックス記憶部２４は、ＶＷＩＤ（単語ＩＤ）毎に、参照画像ＩＤ及び局所特徴の情報を対応付けてリスト構造で記憶する。
【００３６】
図４は、転置インデックスを表す説明図である。
【００３７】
図４によれば、ＶＷＩＤ毎に、参照画像ＩＤ及び局所特徴の情報が対応付けられている。局所特徴の情報として、特徴ベクトルｆ、座標情報ｐ、方向θ、スケールｓを含む。
【００３８】
図５は、質問画像と参照画像との間のマッチングを表す説明図である。
【００３９】
図５（ａ）は、参照画像に対して、質問画像の視点が異なっていることを表す。そのたに、質問画像に写る物体は、参照画像に写る物体に対して、幾何的に変換されている。
図５（ｂ）は、質問画像及び参照画像から抽出された局所特徴が表されている。局所特徴としては、少なくとも特徴ベクトルｆ及び座標情報ｐがあり、更に方向θ及びスケールｓがあってもよい。
図５（ｃ）は、質問画像及び参照画像から抽出された特徴点同士のマッチングが表されている。マッチングする特徴点対応組が多いほど、幾何的な類似度が高い。
【００４０】
＜Ｓ１＞［端末１：質問情報送信部１４］
質問情報送信部１４は、物体が写る質問画像における複数の量子化ベクトル（特徴ベクトル）を含む質問情報を、物体検索サーバ２へ送信する。ここで、量子化ベクトルは、ＶＷＩＤ（Visual Word識別子）であることが好ましい。質問情報は、量子化部１２から出力されたＶＷＩＤを、局所特徴ＩＤの順に並べた質問情報を生成する。即ち、質問情報は、ＶＷＩＤの群となる。尚、Hamming embeddingやWeak geometry consistencyを用いる場合、質問情報は、Visual Word識別子に対応付けて、方向θ及び／又はスケールｓを更に含むものであってもよい。
【００４１】
質問画像に写る物体の検索は、従来技術によれば、図１のように１段階のシーケンスで実行されるのに対し、本発明は、２段階のシーケンスで実行される。
１段階目：質問画像のＶＷＩＤ群に類似する複数の参照画像を検索する
（質問情報に座標情報を含まない。投票による類似度を算出）
２段階目：検索された参照画像の中で、質問情報の幾何情報に類似する参照画像を
更に検索する
（１段階目で類似度が閾値以上である場合にのみ、幾何検証を実行）
【００４２】
例えば、従来技術によれば、質問情報が特徴ベクトル＋座標情報である場合、8byte必要となる。これに対し、本発明によれば、１段階目では、質問情報がＶＷＩＤのみであえるために、その半分の4byteしか必要とならない。即ち、質問情報のデータサイズを５割削減することができる。
また、１段階目のシーケンスの実行によって、類似する参照画像無しと判定された場合、２段階目のシーケンスを実行する必要がない。即ち、物体検索サービスを継続するほど、ネットワークを介して送受信されるデータサイズは、必然的に減少することとなる。
【００４３】
＜Ｓ２＞［サーバ２：類似度算出部２５］
類似度算出部２５は、転置インデックス記憶部２４を用いて、質問情報の複数の量子化ベクトルと各参照画像との間の「類似度」を算出する。具体的には、多数の参照画像のＶＷＩＤ群と、受信した質問情報に含まれるＶＷＩＤ群とを比較して、類似度を算出する。
【００４４】
図６は、質問画像と参照画像との間におけるＶＷＩＤ（量子化ベクトル）の類似度を表す説明図である。
【００４５】
ここでは、質問情報に含まれる各ＶＷＩＤに対応する、転置インデックスのリストに含まれる参照画像ＩＤに対して、スコアを投票する（図４参照）。投票するスコアは、固定の大きさであってもよいし、何らかの重み付けをしてもよい。投票されたスコアが大きいほど、質問画像と参照画像との間の類似度が高いことを意味する。
【００４６】
転置インデックスは、参照画像毎に総ＶＷ数に差があるために、投票したスコア同士の大きさを比較することは難しい。そのため、参照画像毎の類似度スコアを、各参照画像のＶＷヒストグラムのＬｐノルムで除算することによって正規化することも好ましい。
【００４７】
ＶＷＩＤiに対して、以下のように設定したとする。
ｘi：参照画像の局所特徴が割り当てられた個数
ｎ：予め用意されたＶＷの個数
ここで、参照画像のＶＷヒストグラムは、以下のように表される。
ベクトルｘ→＝（ｘ1，ｘ2，・・・，ｘn）
このとき、例えば参照画像のＶＷヒストグラムのノルムは、以下のように表される。
Ｌ１ノルム：Σi=1n｜ｘi｜
：参照画像のＶＷヒストグラムにおける、各ＶＷに量子化された局所
特徴の個数の総和
Ｌ２ノルム：√(Σi=1n ｘi2)
：各ＶＷに量子化された局所特徴の個数の二乗和の平方根
参照画像ＩＤ毎に、Ｌ１ノルムの逆数、Ｌ２ノルムの逆数、又は、他の正規化係数を乗算することによって、類似度を正規化する。最終的に、全ての参照画像ＩＤに対応する類似度を算出する。
【００４８】
＜Ｓ３＞［物体検索サーバ２：類似度判定送信部２６］
類似度判定送信部２６は、質問情報と複数の参照画像との間の類似度判定結果を、端末１へ返信する。類似度判定結果は、質問情報に対する全ての参照画像ＩＤの類似度に対して、閾値で判定する。例えば、類似判定結果は、以下のように２つの閾値に対する３つのコマンドで表される。
（コマンド）
yes1：類似度が閾値TH1以上の参照画像が１つ以上ある
yes2：類似度が閾値TH1未満且つ閾値TH2以上の参照画像が１つ以上ある
no  ：全ての類似度がTH2未満である
閾値TH1：検索成功の可能性が極めて高い類似度の指標
閾値TH2：検索成功の可能性が比較的高い類似度の指標
【００４９】
コマンド「yes1」「yes2」の場合、類似度判定送信部２６は、コマンドと共に、その判定条件を満たした参照画像ＩＤも、端末１へ送信する。
また、コマンド「no」の場合、類似度判定送信部２６は、検索失敗とみなして、そのコマンドのみを、端末１へ送信する。これによって、端末１は、２段階目のシーケンスを実行することなく、「検索失敗」として終了することができる。
【００５０】
尚、類似度判定結果として、３つ以上の閾値によって４つ以上のコマンドのいずれかを、端末へ返信するものであってもよい。また、参照画像ＩＤの個数は、類似度が大きい順に所定Ｎ個であってもよいし、全てであってもよい。
【００５１】
＜Ｓ４＞［端末１：幾何情報選択部１５］
幾何情報選択部１５は、物体検索サーバ２から、類似度判定結果を受信する。そして、その類似度判定結果に応じて、質問画像の座標情報を含む幾何情報を選択する。具体的には、物体検索サーバ２へ送信する幾何情報を以下のように制御する。
（受信コマンド）
yes1：幾何情報は、座標情報のみを含む
yes2：幾何情報は、座標情報及び特徴ベクトルを含む
no  ：検索失敗として、処理を終了する
【００５２】
ここで、幾何情報選択部１５は、類似度判定結果に基づく閾値が低いほど、長い特徴ベクトル（特徴ベクトルの上位ビットのみ->全体ビット）を幾何情報に含めることも好ましい。
（受信コマンド）
yes1（判定閾値が高い）：幾何情報は、座標情報のみを含む
yes2                  ：幾何情報は、座標情報、及び特徴ベクトルの一部を含む
yes3（判定閾値が低い）：幾何情報は、座標情報、及び特徴ベクトルの全部を含む
no                    ：保持していた幾何情報を、時間ｔの経過後に破棄
【００５３】
＜Ｓ５＞［端末１：幾何情報送信部１６］
幾何情報送信部１６は、質問画像の座標情報を含む幾何情報を、物体検索サーバ２へ送信する。
【００５４】
＜Ｓ６＞［物体検索サーバ２：幾何検証部２７］
幾何検証部２７は、類似度判定結果によって類似すると判定された複数の参照画像の中で、幾何情報の座標情報に所定閾値以上で類似する１つ以上の参照画像を検索する（図４、図５（ｃ）参照）。具体的には、幾何情報の座標情報と、各参照画像の座標情報との間で、幾何的な所定条件を満たす特徴点対応組（inlier）を算出する。そして、特徴点対応組の数が最大又は所定数以上となる参照画像を検索する。
【００５５】
最初に、座標マッチングによって、同一のＶＷＩＤに量子化された局所特徴の座標情報同士をマッチングさせた特徴点対応組を算出する。例えば、特徴ベクトルfの距離が最も近いもの同士をマッチングさせてもよい。
次に、マッチングされた特徴点対応組に対して、ＲＡＮＳＡＣ(RANdom SAmple Consensus) アルゴリズム等のロバスト推定法を用いて、一方の座標系から他方の座標系へのHomography行列を算出する。
次に、Homography行列を用いて一方の特徴点の座標を射影し、対応している他方の特徴点の座標との距離がＬ以内であれば、その特徴点対応組をinlierと判定する。
そして、inlierの数が所定閾値以上となる参照画像のみを、「検索成功」として判定する。但し、inlierの数が所定閾値以上となる参照画像が無い場合、「検索失敗」と判定する。
尚、Homography行列に代えて、Affine行列や基礎行列など、幾何学的変換に基づく行列を用いてもよい。
【００５６】
図７は、質問画像と参照画像との間における幾何的な特徴点対応組を表す説明図である。
【００５７】
図７（ａ）は、質問画像と参照画像との間における特徴点対応組を表す。
図７（ｂ）は、Homography行列に基づくinlier及びoutlierの画像対応を表す。outlierは、破線で表されている。
【００５８】
＜Ｓ７＞［物体検索サーバ２：検索結果送信部２８］
検索結果送信部２８は、幾何検証部２７によって検索された各参照画像の参照画像ＩＤを、端末１へ返信する。
【００５９】
図８は、本発明における他のシステム構成図である。
【００６０】
図８によれば、図２の物体検索サーバが、類似度判定サーバ及び幾何検証サーバとして個別に配置されたものである。このように別個のサーバに構築することによって、各サーバの処理負荷を軽減させることができる。
【００６１】
この場合、Ｓ３（物体検索サーバの類似度判定送信部）について、物体検索サーバ２は、類似度判定結果と共に、複数の参照画像ＩＤも、端末１へ返信する。
次に、Ｓ５（端末の幾何情報送信部）について、端末１は、幾何情報と共に、先に受信した参照画像ＩＤも送信する。
そして、Ｓ６（物体検索サーバの幾何検証部）について、物体検索サーバ２は、端末１から受信した複数の参照画像ＩＤの中で、幾何検証の処理を実行すればよい。
【００６２】
以上、詳細に説明したように、本発明のシステム及び方法によれば、撮影画像に写る物体を検索する際に、物体の検索精度を低下させることなく、ネットワークを介して転送される局所特徴のデータサイズを削減することができる。
【００６３】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６４】
１  端末
１１  局所特徴抽出部
１２  量子化部
１３  幾何情報蓄積部
１４  質問情報送信部
１５  幾何情報選択部
１６  幾何情報送信部
２  物体検索サーバ
２１  局所特徴抽出部
２２  量子化部
２３  幾何情報蓄積部
２４  転置インデックス記憶部
２５  類似度算出部
２６  類似度判定送信部
２７  幾何検証部
２８  検索結果送信部
【図１】
0006460926.tif 000002
【図２】
0006460926.tif 000003
【図３】
0006460926.tif 000004
【図４】
0006460926.tif 000005
【図５】
0006460926.tif 000006
【図６】
0006460926.tif 000007
【図７】
0006460926.tif 000008
【図８】
0006460926.tif 000009