(57)【特許請求の範囲】
【請求項１】
特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索する検索装置であって、
複数のリファレンスコンテンツＲjから抽出された各特徴ベクトルに対応付けて、リファレンスコンテンツ識別子を記憶したリファレンス情報蓄積手段と、
前記リファレンス情報蓄積手段を用いて、クエリコンテンツの各特徴ベクトルｑiについて、類似した特徴ベクトルを持つリファレンスコンテンツの特徴ベクトルの集合Ｄを、少なくとも１つ以上探索する類似ベクトル探索手段と、
混合パラメータλを用いて、前記クエリコンテンツの各特徴ベクトルｑiが、探索された各リファレンスコンテンツから生成される確率λ・ｐ(ｑi|Ｒj)と、当該リファレンスコンテンツと無関係な背景モデルから生成される確率(1-λ)・ｐ(ｑi)との確率比に基づいて、リファレンスコンテンツＲj毎にスコアを加算することを、当該クエリコンテンツの全ての特徴ベクトルｑiについて実行し、最終的に、所定閾値以上の上位のスコアを得たリファレンスコンテンツＲjを、検索結果として出力する投票手段と
を有することを特徴とする検索装置。
【請求項２】
前記投票手段は、前記確率比を、探索されたリファレンスコンテンツの特徴ベクトルの集合Ｄに含まれる、全リファレンスコンテンツの特徴ベクトルの出現数(Ｄs)に対する、当該リファレンスコンテンツＲjの特徴ベクトルの出現数(ｎj)との比（ｎj／Ｄs)に基づいて算出することを特徴とする請求項１に記載の検索装置。
【請求項３】
前記投票手段は、前記確率比を、更に以下の式における比に基づいて算出する
（集合Ｄに含まれる当該リファレンスコンテンツＲjの特徴ベクトルの数(ｎj)×
全リファレンスコンテンツの特徴ベクトルの数(|Ｒall|)）／
（集合Ｄに含まれる全リファレンスコンテンツの特徴ベクトルの数(Ｄs)×
当該リファレンスコンテンツＲjの特徴ベクトルの数(Ｒj)）
ことを特徴とする請求項２に記載の検索装置。
【請求項４】
前記類似ベクトル探索手段は、探索されたリファレンスコンテンツの特徴ベクトルの集合を、クエリコンテンツの特徴ベクトルｑiに対する平均的な類似度に応じて１つ以上の部分集合（クラスタ）Ｄに区分し、上位からの近傍数m（≧1）番目までの部分集合Ｄを順序付けし、
前記投票手段は、部分集合Ｄt（1≦t≦m）毎に各リファレンスコンテンツについてスコアを算出し、当該スコアが最大となる部分集合Ｄt’におけるスコアを投票に用いる
ことを特徴とする請求項２又は３に記載の検索装置。
【請求項５】
前記投票手段は、上位からt番目までの特徴ベクトルの集合Ｄtについて、クエリコンテンツの特徴ベクトルｑiに対するリファレンスコンテンツjのスコアｓjを、以下の式によって算出する
ｓj＝maxj log｛λ/(1-λ)・(ｎtj・|Ｒall|)／(Σs=1t|Ｄs(ｑi)|・|Ｒj|)＋１)}
ｎtj：  t番目までの部分集合Ｄtに含まれる
リファレンスコンテンツjの特徴ベクトルの数
Σs=1t|Ｄs(ｑi)|：  t番目までの部分集合Ｄtに含まれる
全リファレンスコンテンツjの特徴ベクトルの数
|Ｒall|：  全リファレンスコンテンツにおける全特徴ベクトルの数
|Ｒj|：  当該リファレンスコンテンツjにおける全特徴ベクトルの数
λ、1-λ：  混合パラメータ
ことを特徴とする請求項４に記載の検索装置。
【請求項６】
前記リファレンス情報蓄積手段は、各部分集合（クラスタ）Ｄ毎に、特徴ベクトルの平均的な代表ベクトルを更に対応付けて記憶しており、
前記類似ベクトル探索手段は、クエリコンテンツの各特徴ベクトルｑiと、各部分集合Ｄの代表ベクトルとを比較して、部分集合Ｄを探索する
ことを特徴とする請求項４又は５に記載の検索装置。
【請求項７】
前記類似ベクトル探索手段は、
クエリコンテンツの各特徴ベクトルｑiに類似する、リファレンスコンテンツの特徴ベクトルのうちk個の部分集合を探索する第１の手段と、
近傍数kの部分集合に含まれる、リファレンスコンテンツの特徴ベクトルの数Ｌを計数する第２の手段と、
近傍数k個の部分集合に含まれるＬ個のリファレンスコンテンツの特徴ベクトルのうち、更にｑiに類似した上位m（m≦Ｌ）個の特徴ベクトルを探索する第３の手段と
を有し、
第３の手段における特徴ベクトル数mは、第２の手段によって計数された特徴ベクトルの数Ｌに応じて更新され、
前記Ｄt(ｑi)（1≦t≦m）は、ｔ番目の特徴ベクトルのみで構成される
ことを特徴とする請求項４から６のいずれか１項に記載の検索装置。
【請求項８】
第３の手段における特徴ベクトル数mは、第２の手段によって得られる特徴ベクトルの数Ｌを用いて、αＬ（α≦１）によって決定される
ことを特徴とする請求項７に記載の検索装置。
【請求項９】
第３の手段における特徴ベクトル数mは、第２の手段によって得られる特徴ベクトルの数Ｌを用いて、Ｌα（α≦１）によって決定される
ことを特徴とする請求項７に記載の検索装置。
【請求項１０】
リファレンスコンテンツ及びクエリコンテンツから、特徴ベクトルを抽出する特徴ベクトル集合抽出手段を更に有し、
前記特徴ベクトル集合抽出手段は、異なる種類のアルゴリズム毎に、複数の特徴ベクトルを出力することができ、
前記投票手段は、クエリコンテンツ及びリファレンスコンテンツそれぞれについて、異なる種類の特徴ベクトル毎にスコアｓを算出し、各リファレンスコンテンツについて異なる種類の特徴ベクトルのスコアｓを重み付け和した値を、最終的なスコアとする
ことを特徴とする請求項１から９のいずれか１項に記載の検索装置。
【請求項１１】
前記クエリコンテンツ及びリファレンスコンテンツは、画像であって、
前記リファレンスコンテンツとしての画像には、同一の物体又は同一カテゴリに属する少なくとも１つのインスタンス（対象物、オブジェクト）が写っている
ことを特徴とする請求項１から１０のいずれか１項に記載の検索装置。
【請求項１２】
特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索する装置に搭載されたコンピュータを機能させる検索プログラムであって、
複数のリファレンスコンテンツＲjから抽出された各特徴ベクトルに対応付けて、リファレンスコンテンツ識別子を記憶したリファレンス情報蓄積手段と、
前記リファレンス情報蓄積手段を用いて、クエリコンテンツの各特徴ベクトルｑiについて、類似した特徴ベクトルを持つリファレンスコンテンツの特徴ベクトルの集合Ｄを、少なくとも１つ以上探索する類似ベクトル探索手段と、
混合パラメータλを用いて、前記クエリコンテンツの各特徴ベクトルｑiが、探索された各リファレンスコンテンツから生成される確率λ・ｐ(ｑi|Ｒj)と、当該リファレンスコンテンツと無関係な背景モデルから生成される確率(1-λ)・ｐ(ｑi)との確率比に基づいて、リファレンスコンテンツＲj毎にスコアを加算することを、当該クエリコンテンツの全ての特徴ベクトルｑiについて実行し、最終的に、所定閾値以上の上位のスコアを得たリファレンスコンテンツＲjを、検索結果として出力する投票手段と
してコンピュータを機能させることを特徴とする検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、同じく特徴ベクトルの集合で表されるクエリコンテンツ（検索キー）に類似したリファレンスコンテンツを高精度に検索する技術に関する。特に、高次元の特徴ベクトルの集合で表されるマルチメディアコンテンツ（例えば画像）の検索に適する。
【背景技術】
【０００２】
近年、オンライン／オフラインに限られず、ストレージの大容量化に伴って、大量のコンテンツを蓄積することが可能となっている。また、携帯電話機やスマートフォンに代表される情報端末機器の普及によって、ユーザ自ら取得した写真データのようなデジタルコンテンツも、データベースに大量かつ容易に蓄積することができる。オフラインデータベースとして、ＨＤＤ(Hard Disk Drive)、ＤＶＤ(Digital Versatile Disk)、Blu-ray disc等の記憶装置がある。また、オンラインデータベースとしては、Flickr（登録商標）やMySpace（登録商標）のようなソーシャルネットワークサービスがある。これら記憶装置及びサービスによれば、データベースに蓄積された個人の大量且つ多様なマルチメディアコンテンツを検索するする技術が重要となる。
【０００３】
マルチメディアコンテンツを検索するために、これらコンテンツから多数の特徴ベクトルを抽出し、この特徴ベクトルの集合同士の間の類似度が高いコンテンツを検索結果として出力する技術がある。この技術によれば、マルチメディアコンテンツの特徴ベクトルを量子化し、量子化された特徴ベクトルの頻度からヒストグラムを作成する。そのヒストグラム同士の間のＬ１ノルム又はＬ２ノルムの距離によって類似度（距離）を算出する。ノルムとは、２つの点の間の距離を表す。Ｌ１ノルムとは、２つの点の各次元の値の絶対値の和を意味し、Ｌ２ノルムとは、２つの点の各次元の値を二乗した和を意味する。
【０００４】
また、画像コンテンツから大量の局所特徴ベクトルを抽出し、それらをベクトル量子化し、同一の代表ベクトルにベクトル量子化された局所特徴ベクトルの数で類似度を算出する技術もある（例えば非特許文献１参照）。
【０００５】
更に、画像から複数の局所不変特徴量を抽出し、特徴ベクトルの頻度のヒストグラム化し、そのヒストグラムの重なり率によって画像とカテゴリとの間の類似度を算出する技術もある（例えば特許文献１参照）。この技術によれば、ヒストグラムに基づいて被写体のパターン認識に不要となる特徴（例えば背景の特徴）を除くことができる。これによって、画像中から物体と物体以外とを予め分離することなく、当該物体の特徴を抽出することができる。
【０００６】
従来、局所特徴量を用いた類似画像検索の枠組みは、「Bag-of-Visual Words」（又はBag-of-Features、Bag-of-Keypoints）と称される（例えば非特許文献１参照）。この技術によれば、Bag-of-Wordsモデル及び転置インデックスを用いた文章の検索方法を、類似画像の検索に適用したものである。Bag-of-Wordsは、文章を１つの単語の頻度により定義される特徴ベクトルで表現し、文章集合に基づいて予め導出されたＩＤＦ(Inverse Document Frequency)を単語の重みとして文章間の類似度を導出する枠組みである。これに対し、Bag-of-Visual Wordsは、画像の局所特徴量を量子化し、量子化後の局所特徴量を単語と見立て、同様に頻度により定義される１つの特徴ベクトルとして表現し、ＩＤＦを用いた重み付けを利用して同一の類推方法を適用することができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１０−２８２５８１号公報
【特許文献２】特開２００９−０２０７６９号公報
【非特許文献】
【０００８】
【非特許文献１】J. Sivic et al., "Video Google: A Text Retrieval Approach toObject Matching in Videos," in Proc. ICCV, 2003.
【非特許文献２】H. Jegou, M. Douze, and C. Schmid, "Improving bag-offeaturesfor large scale image search," in IJCV, vol.87, no.3, pp.316-336, 2010.
【非特許文献３】Y. Uchida, M. Agrawal, and S. Sakazawa, "Accurate Content-BasedVideo Copy Detection with Efficient Feature Indexing," in Proc. of ICMR,2011.
【非特許文献４】D. G. Lowe, "Distinctive Image Features from Scale-InvariantKeypoints," International Journal of Computer Vision, vol. 60, no. 2, pp.91-110, 2004.
【非特許文献５】H. Jegou, M. Douze, and C. Schmid, "Product quantization fornearest neighbor search," in IEEE Trans. on PAMI, vol. 33, no. 1, pp117-128, 2011.
【非特許文献６】O. Boiman, E. Shechtman, and M. Irani, "In defense ofnearest-neighbor based image classification," in Proc. of CVPR, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、既存のBag-of-Visual Wordsの技術によれば、特徴ベクトルに基づいてコンテンツ間の類似度のスコアを算出する際に、文章検索におけるＩＤＦを用いている。ＩＤＦとは、テキストマイニングの用途について、文章中に出現した特定の単語がどのくらい特徴的であるかを識別するための指標を表す。ＩＤＦの場合、例えば固有名詞のような、「各文章は、当該文章内に含まれる少数の単語によって検索される」という前提で設計されている。言い換えれば、「各文章は、当該文章内に含まれない単語によっては検索されない」という前提である。ＩＤＦは、具体的には、当該文章の中で特定の単語が出現した回数と、コーパス全体の中でその文章を含む文章数の自然対数とから、そのコーパス中におけるその単語の特徴度として算出される。
【００１０】
一方、画像検索の場合、局所不変特徴領域から、高次元の特徴ベクトルを抽出する必要がある。例えば、物体認識に用いる特徴ベクトルを抽出するために代表的なＳＩＦＴ(Scale-Invariant Feature Transform)によれば、特徴領域を複数のブロックに分割し、各ブロックから輝度勾配の方向を重み付きヒストグラムとして抽出する。
【００１１】
ここで、リファレンスコンテンツ（検索対象のコンテンツ）に対して、クエリコンテンツ（検索キーのコンテンツ）は、対象物とは無関係な特徴ベクトルが多く含まれる場合がある。具体的には、対象物をカメラで撮影した画像を、クエリコンテンツとした場合である。リファレンスコンテンツには、例えば背景が白で、検索対象物のみが写っているのに対し、クエリコンテンツには、当該対象物だけでなく、その背景に様々な物が写り込む。即ち、クエリコンテンツの背景には、当該対象物とは無関係の様々特徴ベクトルが検出される。これが、検索精度を低下させる原因となっている。
【００１２】
そこで、本発明によれば、高次元の特徴ベクトル集合を検索する際に、クエリコンテンツの特徴ベクトルに、無関係な特徴ベクトルが含まれていることを考慮して、リファレンスコンテンツに対するスコア付けをすることができる検索装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明によれば、特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索する検索装置であって、
複数のリファレンスコンテンツＲjから抽出された各特徴ベクトルに対応付けて、リファレンスコンテンツ識別子を記憶したリファレンス情報蓄積手段と、
リファレンス情報蓄積手段を用いて、クエリコンテンツの各特徴ベクトルｑiについて、類似した特徴ベクトルを持つリファレンスコンテンツの特徴ベクトルの集合Ｄを、少なくとも１つ以上探索する類似ベクトル探索手段と、
混合パラメータλを用いて、クエリコンテンツの各特徴ベクトルｑiが、探索された各リファレンスコンテンツから生成される確率λ・ｐ(ｑi|Ｒj)と、当該リファレンスコンテンツと無関係な背景モデルから生成される確率(1-λ)・ｐ(ｑi)との確率比に基づいて、リファレンスコンテンツＲj毎にスコアを加算することを、当該クエリコンテンツの全ての特徴ベクトルｑiについて実行し、最終的に、所定閾値以上の上位のスコアを得たリファレンスコンテンツＲjを、検索結果として出力する投票手段と
を有することを特徴とする。
【００１４】
本発明の検索装置における他の実施形態によれば、投票手段は、確率比を、探索されたリファレンスコンテンツの特徴ベクトルの集合Ｄに含まれる、全リファレンスコンテンツの特徴ベクトルの出現数(Ｄs)に対する、当該リファレンスコンテンツＲjの特徴ベクトルの出現数(ｎj)との比（ｎj／Ｄs)に基づいて算出することも好ましい。
【００１５】
本発明の検索装置における他の実施形態によれば、投票手段は、確率比を、更に以下の式における比に基づいて算出する
（集合Ｄに含まれる当該リファレンスコンテンツＲjの特徴ベクトルの数(ｎj)×
全リファレンスコンテンツの特徴ベクトルの数(|Ｒall|)）／
（集合Ｄに含まれる全リファレンスコンテンツの特徴ベクトルの数(Ｄs)×
当該リファレンスコンテンツＲjの特徴ベクトルの数(Ｒj)）
ことも好ましい。
【００１６】
本発明の検索装置における他の実施形態によれば、
類似ベクトル探索手段は、探索されたリファレンスコンテンツの特徴ベクトルの集合を、クエリコンテンツの特徴ベクトルｑiに対する平均的な類似度に応じて１つ以上の部分集合（クラスタ）Ｄに区分し、上位からの近傍数m（≧1）番目までの部分集合Ｄを順序付けし、
投票手段は、部分集合Ｄt（1≦t≦m）毎に各リファレンスコンテンツについてスコアを算出し、当該スコアが最大となる部分集合Ｄt’におけるスコアを投票に用いる
ことも好ましい。
【００１７】
本発明の検索装置における他の実施形態によれば、
投票手段は、上位からt番目までの特徴ベクトルの集合Ｄtについて、クエリコンテンツの特徴ベクトルｑiに対するリファレンスコンテンツjのスコアｓjは、以下の式によって算出される
ｓj＝maxj log｛λ/(1-λ)・(ｎtj・|Ｒall|)／(Σs=1t|Ｄs(ｑi)|・|Ｒj|)＋１)}
ｎtj：  t番目までの部分集合Ｄtに含まれる
リファレンスコンテンツjの特徴ベクトルの数
Σs=1t|Ｄs(ｑi)|：  t番目までの部分集合Ｄtに含まれる
全リファレンスコンテンツjの特徴ベクトルの数
|Ｒall|：  全リファレンスコンテンツにおける全特徴ベクトルの数
|Ｒj|：  当該リファレンスコンテンツjにおける全特徴ベクトルの数
λ、1-λ：  混合パラメータ
ことも好ましい。
【００１８】
本発明の検索装置における他の実施形態によれば、
リファレンス情報蓄積手段は、各部分集合（クラスタ）Ｄ毎に、特徴ベクトルの平均的な代表ベクトルを更に対応付けて記憶しており、
類似ベクトル探索手段は、クエリコンテンツの各特徴ベクトルｑiと、各部分集合Ｄの代表ベクトルとを比較して、部分集合Ｄを探索することも好ましい。
【００１９】
本発明の検索装置における他の実施形態によれば、類似ベクトル探索手段は、
クエリコンテンツの各特徴ベクトルｑiに類似する、リファレンスコンテンツの特徴ベクトルのうちk個の部分集合を探索する第１の手段と、
近傍数kの部分集合に含まれる、リファレンスコンテンツの特徴ベクトルの数Ｌを計数する第２の手段と、
近傍数k個の部分集合に含まれるＬ個のリファレンスコンテンツの特徴ベクトルのうち、更にｑiに類似した上位m（m≦Ｌ）個の特徴ベクトルを探索する第３の手段と
を有し、
第３の手段における特徴ベクトル数mは、第２の手段によって計数された特徴ベクトルの数Ｌに応じて更新され、
Ｄt(ｑi)（1≦t≦m）は、ｔ番目の特徴ベクトルのみで構成されることも好ましい。
【００２０】
本発明の検索装置における他の実施形態によれば、第３の手段における特徴ベクトル数mは、第２の手段によって得られる特徴ベクトルの数Ｌを用いて、αＬ（α≦１）によって決定されることも好ましい。
【００２１】
本発明の検索装置における他の実施形態によれば、第３の手段における特徴ベクトル数mは、第２の手段によって得られる特徴ベクトルの数Ｌを用いて、Ｌα（α≦１）によって決定されることも好ましい。
【００２２】
本発明の検索装置における他の実施形態によれば、
リファレンスコンテンツ及びクエリコンテンツから、特徴ベクトルを抽出する特徴ベクトル集合抽出手段を更に有し、
特徴ベクトル集合抽出手段は、異なる種類のアルゴリズム毎に、複数の特徴ベクトルを出力することができ、
投票手段は、クエリコンテンツ及びリファレンスコンテンツそれぞれについて、異なる種類の特徴ベクトル毎にスコアｓを算出し、各リファレンスコンテンツについて異なる種類の特徴ベクトルのスコアｓを重み付け和した値を、最終的なスコアとする
ことも好ましい。
【００２３】
本発明の検索装置における他の実施形態によれば、
クエリコンテンツ及びリファレンスコンテンツは、画像であって、
リファレンスコンテンツとしての画像には、同一の物体又は同一カテゴリに属する少なくとも１つのインスタンス（対象物、オブジェクト）が写っている
ことも好ましい。
【００２４】
本発明によれば、特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索する装置に搭載されたコンピュータを機能させる検索プログラムであって、
複数のリファレンスコンテンツＲjから抽出された各特徴ベクトルに対応付けて、リファレンスコンテンツ識別子を記憶したリファレンス情報蓄積手段と、
リファレンス情報蓄積手段を用いて、クエリコンテンツの各特徴ベクトルｑiについて、類似した特徴ベクトルを持つリファレンスコンテンツの特徴ベクトルの集合Ｄを、少なくとも１つ以上探索する類似ベクトル探索手段と、
混合パラメータλを用いて、クエリコンテンツの各特徴ベクトルｑiが、探索された各リファレンスコンテンツから生成される確率λ・ｐ(ｑi|Ｒj)と、当該リファレンスコンテンツと無関係な背景モデルから生成される確率(1-λ)・ｐ(ｑi)との確率比に基づいて、リファレンスコンテンツＲj毎にスコアを加算することを、当該クエリコンテンツの全ての特徴ベクトルｑiについて実行し、最終的に、所定閾値以上の上位のスコアを得たリファレンスコンテンツＲjを、検索結果として出力する投票手段と
してコンピュータを機能させることを特徴とする。
【発明の効果】
【００２５】
本発明の検索装置及びプログラムによれば、高次元の特徴ベクトル集合を検索する際に、クエリコンテンツの特徴ベクトルに、無関係な特徴ベクトルが含まれていることを考慮して、リファレンスコンテンツに対するスコア付けをすることができる。
【図面の簡単な説明】
【００２６】
【図１】本発明における検索装置の機能構成図である。
【図２】リファレンス情報生成部の処理内容を表す説明図である。
【図３】リファレンスコンテンツの特徴ベクトルの１つの集合Ｄから投票する説明図である。
【図４】リファレンスコンテンツの特徴ベクトルの複数の集合Ｄから投票する説明図である。
【図５】階層的なコードブックを表す説明図である。
【図６】複数のリファレンスコンテンツの複数の特徴ベクトルから投票する説明図である。
【発明を実施するための形態】
【００２７】
以下では、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２８】
本発明の検索装置及びプログラムによれば、多数のリファレンスコンテンツ（検索対象のコンテンツ）の中から、クエリコンテンツ（検索キーのコンテンツ）に最も類似するリファレンスコンテンツを検索する。
【００２９】
図１は、本発明における検索装置の機能構成図である。
【００３０】
図１によれば、検索装置１は、リファレンス情報蓄積部１０と、特徴ベクトル集合抽出部１１と、リファレンス情報生成部１２と、類似ベクトル探索部１３と、投票部１４とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００３１】
検索装置１は、多数のリファレンスコンテンツを予め入力し、リファレンス情報蓄積部１０に、リファレンスコンテンツに関する情報を記憶する。また、検索装置１は、検索の際に、検索キーとなるクエリコンテンツを入力し、リファレンス情報蓄積部１０を用いて、クエリコンテンツに最も類似するリファレンスコンテンツを検索する。
【００３２】
クエリコンテンツ及びリファレンスコンテンツは、例えば画像である。この場合、リファレンスコンテンツとしての画像には、同一の物体又は同一カテゴリに属する少なくとも１つのインスタンス（対象物、オブジェクト）が写っている。
【００３３】
［特徴ベクトル集合抽出部１１］
特徴ベクトル集合抽出部１１は、１つのマルチメディアコンテンツから、特徴ベクトルの集合を抽出する。例えばマルチメディアコンテンツが画像である場合、その特徴ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルである。
【００３４】
特徴ベクトル集合抽出部１１は、具体的には、リファレンスコンテンツＲj毎に特徴ベクトルの集合を抽出し、それら特徴ベクトルの集合は、リファレンス情報蓄積部１０へ出力される。また、特徴ベクトル集合抽出部１１は、クエリコンテンツから特徴ベクトルの集合Ｑ（＝{ｑi}）を抽出し、それら特徴ベクトルの集合は、類似ベクトル探索部１３へ出力される。尚、リファレンスコンテンツの特徴ベクトルと、クエリコンテンツの特徴ベクトルとは、同じ次元数である。
【００３５】
物体認識に用いる特徴ベクトルの抽出アルゴリズムとしては、例えばＳＩＦＴやＳＵＲＦ(Speeded Up Robust Features)が用いられる。例えば、ＳＩＦＴの場合、１枚の画像からは１２８次元の特徴ベクトルの集合が抽出される（例えば非特許文献４参照）。ＳＩＦＴとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる特徴ベクトルを記述する技術である。一方で、ＳＵＲＦの場合、ＳＩＦＴよりも高速処理が可能であって、１枚の画像から６４次元の特徴ベクトルの集合が抽出される。
【００３６】
［リファレンス情報生成部１２］
リファレンス情報生成部１２は、リファレンスコンテンツの特徴ベクトルの集合Ｒjに対して、以下の処理を実行し、リファレンス情報蓄積部１０へコードブックを出力する。
【００３７】
図２は、リファレンス情報生成部の処理内容を表す説明図である。
【００３８】
（Ｓ２１）リファレンスコンテンツの特徴ベクトルの集合を、k個のクラスタにクラスタリングする。クラスタリングには、例えばk-meansが用いられる。
（Ｓ２２）次に、クラスタ毎に、代表ベクトルを導出する（平均ベクトル又は中央値ベクトル）。この代表ベクトルは、"Visual Words"とも称される。
（Ｓ２３）各代表ベクトルに、一意のＩＤｎ（＝１〜Ｎ）を割り当てたコードブックを生成する。
【００３９】
例えば、入力された特徴ベクトルｆとの距離が最も小さくなる代表ベクトルｆｎを算出する。
代表ベクトルｆｎ＝argminｎ||ｆ−ｆｎ||２
ここで、コードブックとは、代表ベクトルｆｎ毎に、そのクラスタに属する１つ以上のリファレンスコンテンツＩＤ（識別子）を対応付けたものである。
【００４０】
［リファレンス情報蓄積部１０］
リファレンス情報蓄積部１０は、複数のリファレンスコンテンツＲjから抽出された各特徴ベクトルに対応付けて、リファレンスコンテンツ識別子を記憶する。ここで、リファレンス情報蓄積部１０は、リファレンス情報生成部１２から出力されたコードブック（転置インデックス）を記憶するものであってもよい。コードブックは、複数のリファレンスコンテンツＲjから抽出された特徴ベクトルを、類似度に応じて複数の集合（クラスタ）Ｄに区分したものであり、集合毎に、リファレンスコンテンツ識別子と、これら特徴ベクトルの平均的な代表ベクトルとを割り当てたものである。
【００４１】
尚、以下の実施形態によれば、複数のリファレンスコンテンツjから特徴ベクトルの集合Ｒjを抽出した場合について詳述している。一方で、例えば非特許文献６のように、特徴ベクトルの集合Ｒjを、特定のカテゴリに基づく特徴ベクトルの集合とすることによって、クエリコンテンツを、カテゴリに分類することもできる。この場合、後述するように、クエリコンテンツに対して、各カテゴリに対するスコアを算出し、最もスコアの高い上位複数件のカテゴリに分類するか、スコアが一定以上のカテゴリのタグを付加することができる。
【００４２】
［類似ベクトル探索部１３］
類似ベクトル探索部１３は、リファレンス情報蓄積部１０を用いて、クエリコンテンツの各特徴ベクトルｑiについて、類似した特徴ベクトルを持つリファレンスコンテンツの特徴ベクトルの集合Ｄを、少なくとも１つ以上探索する。クエリコンテンツの特徴ベクトルｑiと、リファレンスコンテンツの特徴ベクトルとの間の距離が短いほど、類似度が高いことを意味する。具体的には、最近傍探索(Approximate Nearest Neighbor)アルゴリズムの１つである直積量子化を用いた方法（例えば非特許文献５参照）やHamming Embeddingを用いた方法（例えば非特許文献２参照）、ＬＳＨ(Locality-Sensitive Hashing)を用いることも好ましい。探索された１つ以上の特徴ベクトルの集合Ｄに基づくリファレンスコンテンツＩＤは、投票部１４へ出力される。
【００４３】
［投票部１４］
投票部１４は、リファレンスコンテンツＲj毎にスコアを加算することを、当該クエリコンテンツの全ての特徴ベクトルｑiについて実行し、最終的に、所定閾値以上の上位のスコアを得たリファレンスコンテンツＲjを、検索結果として出力する。投票部１４は、従来技術によればＩＤＦによって投票していたのに対し、本発明によれば、以下に詳述する算出式によって投票される。
【００４４】
本発明によれば、クエリコンテンツを生成したであろう可能性の最も高いリファレンスコンテンツj’を導出する。以下の式は、事後確率を意味し、クエリコンテンツが、j番目のリファレンスコンテンツから生成されたであろう確率ｐを表す。
j’＝argmaxjｐ(Ｒj|Ｑ)
Ｑ：クエリコンテンツの特徴ベクトルの集合
Ｒj：j番目のリファレンスコンテンツの特徴ベクトルの集合
ｐ(Ｒj|Ｑ)：クエリコンテンツの特徴ベクトルの集合Ｑから、
リファレンスコンテンツの特徴ベクトルの集合Ｒjが生成される事後確率
argmaxj：右項の事後確率を最大とするjを導出することを意味する
【００４５】
前述の事後確率の式は、一般的に、ベイズの定理を用いて以下の式が成立する。これは、事前確率に尤度確率を乗算することによって、事後確率を算出するものである。
j’＝argmaxj ｐ(Ｒj|Ｑ)＝argmaxj ｐ(Ｑ|Ｒj)ｐ(Ｒj)
ｐ(Ｑ|Ｒj)：リファレンスコンテンツの特徴ベクトルの集合Ｒjから、
クエリコンテンツの特徴ベクトルの集合Ｑが生成される尤度確率
ｐ(Ｒj)    ：リファレンスコンテンツの特徴ベクトルの集合Ｒjが検索される
事前確率
（ｐ(Ｒj)が高いほど、検索される確率が高いことを意味する）
【００４６】
尚、ここで、検索されるリファレンスコンテンツには偏りがなく、ｐ(Ｒj)は、いずれのjであっても一定であると仮定する。そうすると、ｐ(Ｒj)を削除することができ、単に以下のように表される。
j’＝argmaxj ｐ(Ｑ|Ｒj)
【００４７】
ここで、クエリコンテンツの特徴ベクトルの集合Ｑは、独立に生成されたものであると仮定する。「独立に生成」とは、ある特徴が出た場合、次に必ず特定の特徴が出るような影響が無い、即ち、以前の結果に影響しないことを意味する。この場合、クエリコンテンツの特徴ベクトルの集合Ｑの各特徴ベクトルｑ1,ｑ2,ｑ3,・・・,ｑnの個々に基づく確率の積となる。この場合、以下の式によって表される。
j’＝argmaxj Πi=1n ｐ(ｑi|Ｒj)
【００４８】
更に、確率の積Πは、一般に、logの和Σによって表すことができる。単調増加関数であるために、確率の大小関係は維持されるためである。この場合、以下の式によって表される。
j’＝argmaxj Πi=1n ｐ(ｑi|Ｒj)＝argmaxj Σi=1n logｐ(ｑi|Ｒj)
【００４９】
ここで、各クエリ特徴ベクトルが、リファレンスコンテンツの特徴ベクトル集合から生成された確率と、リファレンスコンテンツとは無関係な背景モデルから生成された確率の線形結合としてモデル化を行う。
j’＝argmaxj Σi=1n logｐ(ｑi|Ｒj)
＝argmaxj Σi=1n log(λｐ(ｑi|Ｒj)＋(1-λ)・ｐ(ｑi))
＝argmaxj Σi=1n (log(λｐ(ｑi|Ｒj)＋(1-λ)・ｐ(ｑi))−log(1-λ)・ｐ(ｑi))
＝argmaxj Σi=1n log{λ/(1-λ)・ｐ(ｑi|Ｒj)/ｐ(ｑi)＋１}
i：クエリコンテンツの特徴ベクトルのＩＤ
λ：線形結合の混合パラメータ
ｐ(ｑi)：リファレンスコンテンツとは無関係な背景モデルから生成された確率
（クエリコンテンツにおける対象物と無関係な背景画像に基づく）
λｐ(ｑi|Ｒj)＋(1-λ)・ｐ(ｑi)：
λにおけるｐ(ｑi|Ｒj)の確率と、(1-λ)におけるｐ(ｑi)の確率との和は、
全体の確率を意味する
−log(1-λ)・ｐ(ｑi)：
変形のため全体的なペナルティを引いても、順番は変わらない。
後述する式の変形のためのもの。
λ/(1-λ)・ｐ(ｑi|Ｒj)/ｐ(ｑi)＋１：
"logａ−logｂ＝logａ/ｂ"に基づいて、式を変形したもの
【００５０】
本発明によれば、混合パラメータλを用いて、クエリコンテンツの各特徴ベクトルｑiが、探索された各リファレンスコンテンツから生成される確率λ・ｐ(ｑi|Ｒj)と、当該リファレンスコンテンツと無関係な背景モデルから生成される確率(1-λ)・ｐ(ｑi)との確率比を用いる。
【００５１】
ここで、以下の式のように置く。
ｓij＝log{λ/(1-λ)・ｐ(ｑi|Ｒj)/ｐ(ｑi)＋１}
i：クエリコンテンツの特徴ベクトルのＩＤ
j：リファンレンスコンテンツのＩＤ
ｑi：クエリコンテンツの特徴ベクトル
Ｒj：リファンレンスコンテンツ
ｓijとは、クエリコンテンツ特徴ベクトルｑiが観測された際に、ｑiそれぞれが、リファンレンスコンテンツjが得られるスコアを意味する。即ち、ｑiが観測された時点で、それぞれが、リファレンスコンテンツjから生成された尤もらしさを意味する。
【００５２】
そして、クエリコンテンツの特徴ベクトルi及びリファンレンスコンテンツjの全てについて、「ｓij」を算出する。そして、スコアΣi=1n ｓijが最大となるリファレンスコンテンツＲjを検索結果として選択する。
【００５３】
しかしながら、ｓijは、各iについて全てのjについて算出しなければならないために、大規模データベースを対象とした場合、その計算量が膨大なものとなる。
【００５４】
そこで、本発明によれば、近似法を適用し、クエリコンテンツの特徴ベクトルｑiについて、リファレンスコンテンツの特徴ベクトル集合の中から、ｑiに類似した特徴ベクトル集合Ｄ(ｑi)を抽出する。そして、以下のようにｓijの算出を近似する。
Ｄ(ｑi)に対応する特徴ベクトルが含まれるリファレンスコンテンツＲjのみについて「ｓij」を算出する
それ以外のＲjについては、ｐ(ｑi|Ｒj)＝０とする
このとき、ｓij＝log(1)＝０となるために、Ｄ(ｑi)に対応する特徴ベクトルが含まれないリファレンスコンテンツのスコアは増減しない。
【００５５】
ここで、Ｄ(ｑi)は更に、m（1〜M）個の互いに素な集合から構成されるとする。
Ｄ(ｑi)＝Ｄ1(ｑi)∪Ｄ2(ｑi)∪・・・∪Ｄm(ｑi)
リファレンス情報蓄積部１０は、コードブックに、多数のリファレンスコンテンツにおける複数の代表ベクトルが登録されている。そして、各代表ベクトルには、リファンレンスコンテンツのＩＤが紐付けられている。ここで、各代表ベクトルに紐付くリファンレンスコンテンツの特徴ベクトルの集合は、それらm個の中で、特徴ベクトルが互いにオーバラップしない。即ち、「互いに素」であると言える。
【００５６】
また、Ｄt(ｑi)及びＤs(ｑi)について、t＜sであれば、以下の不等式が成立する。
ｐ(ｑi|Ｄt(ｑi)) ＞ ｐ(ｑi|Ｄs(ｑi))
即ち、t＜sのとき、ｑiは、Ｄs(ｑi)よりもＤt(ｑi)から生成された確率が高い。このＤ1(ｑi)・・・Ｄm(ｑi)それぞれについて、ｓijを以下のように算出する。
【００５７】
各Ｄt(ｑi)について、ｐ(ｑi|Ｒj)及びｐ(ｑi)は、ｋ近傍密度推定法によって算出される。
ｐ(ｑi|Ｒj)＝ｎtj／(|Ｒj|・Ｖt)
ｐ(ｑi)＝Σs=1t|Ｄs(ｑi)|／(|Ｒall|・Ｖt)
ｎtj：Ｄ1(ｑi)・・・Ｄt(ｑi)に出現するＲjの特徴ベクトルの数
Ｒall：リファレンスコンテンツ全ての特徴ベクトル集合
Ｖt：ｑiとｒ’tの距離を半径とする超球（３次元以上）の体積
（尚、２次元であれば面積、１次元であれば長さを表す）
ｒ’t：Ｄt(qi)の中で最もｑiから遠い特徴ベクトル
ここで、ｐ(ｑi)は、|Ｒall|個（ｋ近傍密度推定法におけるＮ）のうち、Σs=1t|Ｄs(ｑi)|個（ｋ近傍密度推定法におけるk）が落ちる確率を、体積Ｖtで割ったものであることを表す。
【００５８】
ここで、Ｖtを算出する場合、多大な計算量が必要となる。そこで、本発明によれば、ｓijの式に代入することによって、Ｖtの項を削除し、以下の式によって算出する。
ｓij＝log{λ/(1-λ)・ｎtj|Ｒall|／Σs=1t(|Ｄs(ｑi)|・|Ｒj｜)＋１}
このスコアは、各画像について、最も大きなスコアのみが加算されることとする。
【００５９】
即ち、本発明の投票部１４は、上位からt番目までの特徴ベクトルの集合Ｄtについて、クエリコンテンツの特徴ベクトルｑiに対するリファレンスコンテンツjのスコアｓjは、以下の式によって算出される。
ｓj＝maxj log｛λ/(1-λ)・(ｎtj・|Ｒall|)／(Σs=1tＤs(ｑi)・|Ｒj|)＋１)}
ｎtj：  t番目までの部分集合Ｄtに含まれる
リファレンスコンテンツjの特徴ベクトルの数
Σs=1tＤs(ｑi)：  t番目までの部分集合Ｄtに含まれる
全リファレンスコンテンツjの特徴ベクトルの数
|Ｒall|：  全リファレンスコンテンツにおける全特徴ベクトルの数
|Ｒj|：  当該リファレンスコンテンツjにおける全特徴ベクトルの数
λ、1-λ：  混合パラメータ
【００６０】
上述の式によれば、確率比「ｎtj／Σs=1t(|Ｄs(ｑi)|」は、探索されたリファレンスコンテンツの特徴ベクトルの集合Ｄに含まれる、全てのリファレンスコンテンツＲjの出現数に対する、各リファレンスコンテンツＲjの出現数との比によって表される出現頻度とする。
【００６１】
［類似ベクトル探索部１３及び投票部１４における具体的な処理内容］
以下では、本発明における類似ベクトル探索部１３及び投票部１４における具体的な処理内容について詳述する。
【００６２】
検索の際、クエリコンテンツから特徴ベクトルの集合Ｑが抽出され、各特徴ベクトルｑi毎に、ベクトル量子化によって、代表ベクトルに紐付いているリファレンスコンテンツの特徴ベクトルの１つ以上の集合Ｄが検索される。そして、対応するリファレンスコンテンツＩＤに投票する。クエリコンテンツの全ての特徴ベクトルｑiについて投票した後、スコアの上位のリファレンスコンテンツＩＤを検索結果とする。
【００６３】
図３は、リファレンスコンテンツの特徴ベクトルの１つの集合Ｄから投票する説明図である。
【００６４】
類似ベクトル探索部１３は、クエリコンテンツの各特徴ベクトルｑiに対して類似する順に上位m件の集合Ｄを探索することも好ましい。図３によれば、上位１つの集合Ｄ(ｑi)が探索されている（m＝1，Ｄ(ｑi)＝Ｄ1(ｑi)）。その１つの集合には、８つのリファレンスコンテンツＩＤが登録されている。但し、ここで、８件のＩＤに順序が付けられていないことに注意する。８つのリファレンスコンテンツＩＤの中で、ユニークなＩＤは４つ（１，４，５，６）ある。
【００６５】
リファレンスコンテンツＩＤ＝１：  ｎ11＝３個
score1＝score1＋log｛λ/(1-λ)・(３|Ｒall|／８|Ｒ1|)＋１｝
（８個の中で３個が、ＩＤ＝１であることを意味）
リファレンスコンテンツＩＤ＝４：  ｎ14＝２個
score4＝score4＋log｛λ/(1-λ)・(２|Ｒall|／８|Ｒ1|)＋１｝
（８個の中で２個が、ＩＤ＝４であることを意味）
リファレンスコンテンツＩＤ＝５：  ｎ15＝１個
score5＝score5＋log｛λ/(1-λ)・(１|Ｒall|／８|Ｒ1|)＋１｝
（８個の中で１個が、ＩＤ＝５であることを意味）
リファレンスコンテンツＩＤ＝６：  ｎ16＝２個
score5＝score5＋log｛λ/(1-λ)・(２|Ｒall|／８|Ｒ1|)＋１｝
（８個の中で２個が、ＩＤ＝６であることを意味）
本発明によれば、投票部１４は、部分集合Ｄt（1≦t≦m）毎に各リファレンスコンテンツについてスコアを算出し、当該スコアが最大となる部分集合Ｄt’におけるスコアを投票に用いる。
【００６６】
図４は、リファレンスコンテンツの特徴ベクトルの複数の集合Ｄから投票する説明図である。
【００６７】
図３は、最近傍の代表ベクトルに紐付いている集合Ｄから投票するのに対し、図４は、ｋ近傍の代表ベクトルに紐付いている集合Ｄから投票する。類似ベクトル探索部１３は、探索されたリファレンスコンテンツの特徴ベクトルの集合を、クエリコンテンツの特徴ベクトルｑiに対する平均的に類似度に応じて１つ以上の部分集合Ｄに区分し、上位からの近傍数m（m≧1）番目までの部分集合Ｄを順序付けするものであってもよい。
【００６８】
図４によれば、類似ベクトル探索部は、クエリコンテンツの１つの特徴ベクトルｑiについて、ｋ近傍探索（m＝3）によって、リファレンスコンテンツの特徴ベクトルの３つの集合Ｄ(ｑi)を探索する(m＝3，Ｄ(ｑi)＝Ｄ1(ｑi)、Ｄ2(ｑi)、Ｄ3(ｑi))。図４によれば、Ｄ1(ｑi)の集合には、３つのリファレンスコンテンツＩＤが登録されており、Ｄ2(ｑi)の集合には、３つのリファレンスコンテンツＩＤが登録されており、Ｄ3(ｑi)の集合には、２つのリファレンスコンテンツＩＤが登録されている。図４によれば、Ｄ1->Ｄ2->Ｄ3の順に順序付けられている。
【００６９】
（第１の集合t＝1、|Ｄ1(ｑi)|＝３個、Σs=1t|Ｄ1(ｑi)|＝３個）
リファレンスコンテンツＩＤ＝１：  ｎ11＝２個
score1＝score1＋log｛λ/(1-λ)・(２|Ｒall|／３|Ｒ1|)＋１｝
リファレンスコンテンツＩＤ＝４：  ｎ14＝１個
score4＝score4＋log｛λ/(1-λ)・(１|Ｒall|／３|Ｒ4|)＋１｝
（第２の集合t＝2、|Ｄ2(ｑi)|＝３個、Σs=1t|Ｄ2(ｑi)|＝６個）
リファレンスコンテンツＩＤ＝５：  ｎ15＝１個
score5＝score5＋log｛λ/(1-λ)・(１|Ｒall|／６|Ｒ5|)＋１｝
リファレンスコンテンツＩＤ＝４：  ｎ14＝１個
×score4＝score4＋log｛λ/(1-λ)・(２|Ｒall|／６|Ｒ4|)＋１｝
★ここで、先のＤ1で得られたscore4と同じであるために、採用しない。
リファレンスコンテンツＩＤ＝１：  ｎ11＝１個
×score1＝score1＋log｛λ/(1-λ)・(３|Ｒall|／６|Ｒ1|)＋１｝
★ここで、先のＤ1で得られたscore1よりも小さい（２／３＞３／６）ために、
採用しない。
（第３の集合t＝3、|Ｄ3(ｑi)|＝２個、Σs=1t|Ｄ3(ｑi)|＝８個）
リファレンスコンテンツＩＤ＝６：  ｎ16＝２個
score6＝score6＋log｛λ/(1-λ)・(２|Ｒall|／８|Ｒ6|)＋１｝
【００７０】
図５は、階層的なコードブックを表す説明図である。
【００７１】
図５によれば、図３及び図４と比較して、コードブックが階層的に構成されている（例えば非特許文献７参照）。このような場合であっても、前述した図３及び図４と同様に、リファレンスコンテンツの特徴ベクトルの集合毎にスコアを投票することができる。
【００７２】
図６は、複数のリファレンスコンテンツの複数の特徴ベクトルから投票する説明図である。
【００７３】
図６によれば、図３及び図４のように複数のリファレンスコンテンツの複数の特徴ベクトルが集合Ｄとして構成されることなく、個別に分散して構成されたものである。クエリコンテンツの各特徴ベクトルから、直積量子化を用いた方法やHamming Embeddingを用いた方法（例えば非特許文献２参照）、ＬＳＨ等のアルゴリズムを用いて、単にm近傍探索として、リファレンスコンテンツの近傍特徴ベクトルが探索されたものである。
【００７４】
（第１の特徴ベクトルt＝1、|Ｄ1(ｑi)|＝１個、Σs=1t|Ｄ1(ｑi)|＝１個）
リファレンスコンテンツＩＤ＝１：  ｎ11＝１個
score1＝score1＋log｛λ/(1-λ)・(１|Ｒall|／１|Ｒ1|)＋１｝
（第２の特徴ベクトルt＝2、|Ｄ2(ｑi)|＝１個、Σs=1t|Ｄ2(ｑi)|＝２個）
リファレンスコンテンツＩＤ＝４：  ｎ24＝１個
score4＝score4＋log｛λ/(1-λ)・(１|Ｒall|／２|Ｒ1|)＋１｝
（第３の特徴ベクトルt＝3、|Ｄ3(ｑi)|＝１個、Σs=1t|Ｄ3(ｑi)|＝３個）
リファレンスコンテンツＩＤ＝１：  ｎ31＝１個
×score1＝score1＋log｛λ/(1-λ)・(２|Ｒall|／３|Ｒ1|)＋１｝
★ここで、先のＤ1で得られたscore1よりも小さい（１／１＞２／３）ために、
採用しない。
（第４の特徴ベクトルt＝4、|Ｄ4(ｑi)|＝１個、Σs=1t|Ｄ4(ｑi)|＝４個）
リファレンスコンテンツＩＤ＝５：  ｎ45＝１個
score5＝score5＋log｛λ/(1-λ)・(１|Ｒall|／４|Ｒ1|)＋１｝
（第５の特徴ベクトルt＝5、|Ｄ5(ｑi)|＝１個、Σs=1t|Ｄ5(ｑi)|＝５個）
リファレンスコンテンツＩＤ＝４：  ｎ54＝１個
score4＝score4＋log｛λ/(1-λ)・(２|Ｒall|／５|Ｒ1|)＋１｝
★ここで、先のＤ2で得られたscore4よりも小さい（１／２＞２／５）ために、
採用しない。
（第６の特徴ベクトルt＝6、|Ｄ6(ｑi)|＝１個、Σs=1t|Ｄ6(ｑi)|＝６個）
リファレンスコンテンツＩＤ＝１：  ｎ61＝１個
score1＝score1＋log｛λ/(1-λ)・(３|Ｒall|／６|Ｒ1|)＋１｝
★ここで、先のＤ1で得られたscore1よりも小さい（１／１＞３／６）ために、
採用しない。
（第７の特徴ベクトルt＝7、|Ｄ7(ｑi)|＝１個、Σs=1t|Ｄ7(ｑi)|＝７個）
リファレンスコンテンツＩＤ＝６：  ｎ76＝１個
score6＝score6＋log｛λ/(1-λ)・(１|Ｒall|／７|Ｒ1|)＋１｝
（第８の特徴ベクトルt＝8、|Ｄ8(ｑi)|＝１個、Σs=1t|Ｄ8(ｑi)|＝８個）
リファレンスコンテンツＩＤ＝６：  ｎ86＝１個
score6＝score6＋log｛λ/(1-λ)・(２|Ｒall|／８|Ｒ1|)＋１｝
★ここで、先のＤ7で得られたscore6よりも大きい（１／７＜２／８）ために、
先のＤ7で得られたscore6を採用しない。
【００７５】
［類似ベクトル探索部１３における近傍特徴ベクトル数mの決定方法］
（直積量子化を用いた方法やHamming Embeddingを用いた方法、ＬＳＨ等のような、２段階のm近傍探索を利用する場合）
類似ベクトル探索部１３は、近傍特徴ベクトル数mを固定値とすることなく、更新（可変）することも好ましい。この場合、類似ベクトル探索部１３は、以下の２つのステップを有する（例えば非特許文献２及び５参照）。
【００７６】
（Ｓ１）クエリコンテンツの各特徴ベクトルｑiに類似する、リファレンスコンテンツの特徴ベクトルのうちk個の部分集合を探索する。即ち、Ｓ１では、大まかな近傍集合を求めることで絞込む。例えばベクトル量子化を用いて大まかな近傍集合を導出することも好ましい（例えば非特許文献２及び５参照）。
【００７７】
（Ｓ２）次に、近傍数k個の部分集合に含まれる、リファレンスコンテンツの特徴ベクトルの数Lを計数する。この数Lは、クエリコンテンツの特徴ベクトル周辺の特徴ベクトルの密度を反映している。例えば、Ｓ２における距離計算について、特徴ベクトルをバイナリ符号化した符号を用いるものであってもよいし（例えば非特許文献２参照）、特徴ベクトルを直積量子化により符号化したものであってもよい（例えば非特許文献３参照）。
【００７８】
（Ｓ３）次に、近傍数k個の部分集合に含まれるL個のリファレンスコンテンツの特徴ベクトルのうち、更にｑiに類似した上位m（m≦L）個の特徴ベクトルを探索する。即ち、ｑiとリファレンスコンテンツの特徴ベクトルとの（近似）距離を更に導出し、更に厳密な近傍集合を導出する。その上で、Ｓ１における近似特徴ベクトル数mは、Ｓ２によって計数された特徴ベクトルの数Lに応じて更新される。例えば、Ｓ２によって計数された特徴ベクトルの数Lが、所定閾値以上であれば、Ｓ３における近傍特徴ベクトル数mを増加させることができる。尚、t番目の集合Ｄt(qi)（1≦t≦m）は、t番目の特徴ベクトルのみで構成される。
【００７９】
また、Ｓ１における近傍特徴ベクトル数mを、Ｓ２によって得られる特徴ベクトルの数Ｌを用いて、αＬ（α≦１）によって決定するものであってもよい。また、Ｌα（α≦１）によって決定するものであってもよい。
【００８０】
尚、他の実施形態として、特徴ベクトル集合抽出部１１は、異なる種類のアルゴリズム毎に、複数の特徴ベクトルを出力することも好ましい。異なる種類のアルゴリズムとしては、例えばＳＩＦＴ及びＳＵＲＦの両方に基づくものである。この場合、投票部１４は、クエリコンテンツ及びリファレンスコンテンツそれぞれについて、異なる種類の特徴ベクトル毎にスコアｓを算出し、各リファレンスコンテンツについて異なる種類の特徴ベクトルのスコアｓを重み付け和した値を、最終的なスコアとする。
【００８１】
以上、詳細に説明したように、本発明の検索装置及びプログラムによれば、高次元の特徴ベクトル集合を検索する際に、クエリコンテンツの特徴ベクトルに、無関係な特徴ベクトルが含まれていることを考慮して、リファレンスコンテンツに対するスコア付けをすることができる。
【００８２】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００８３】
１  検索装置
１０  リファレンス情報蓄積部
１１  特徴ベクトル集合抽出部
１２  リファレンス情報生成部
１３  類似ベクトル探索部
１４  投票部
【図１】
0005833499.tif 000002
【図２】
0005833499.tif 000003
【図３】
0005833499.tif 000004
【図４】
0005833499.tif 000005
【図５】
0005833499.tif 000006
【図６】
0005833499.tif 000007