(57)【要約】【課題】ＳＩＦＴやＳＵＲＦよりも更に高速にコンテンツを検索することができるコンテンツ検索装置、プログラム及び方法を提供する。【解決手段】訓練／リファレンス／クエリの各コンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合を抽出する特徴ベクトル抽出手段と、訓練コンテンツのバイナリ特徴ベクトルの集合から、多変量ベルヌーイ分布に関する混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを算出するモデル推定手段と、リファレンスコンテンツ又はクエリコンテンツのバイナリ特徴ベクトルの集合から、混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、１つのフィッシャーベクトルを算出する特徴ベクトル変換手段と、クエリコンテンツのフィッシャーベクトルに最も類似する、リファレンスコンテンツのフィッシャーベクトルを検索する特徴ベクトル検索手段とを有する。【選択図】図２
2014146207.tif 000002
【特許請求の範囲】
【請求項１】
装置に搭載されたコンピュータを、訓練コンテンツから抽出されたモデルパラメータを用いて、リファレンスコンテンツの集合から、クエリコンテンツに類似したリファレンスコンテンツを検索するように機能させる検索プログラムであって、
訓練コンテンツ、リファレンスコンテンツ及びクエリコンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合x1〜xTを抽出する特徴ベクトル抽出手段と、
訓練コンテンツのバイナリ特徴ベクトルの集合から、i（1≦i≦N）番目の多変量ベルヌーイ分布に関する混合比ｗiと、i番目の多変量ベルヌーイ分布のd（1≦d≦D）番目のパラメータμidと、パラメータμidに関するフィッシャー情報量ｆidとを算出するモデル推定手段と、
混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを蓄積するモデルパラメータ蓄積手段と、
リファレンスコンテンツ又はクエリコンテンツのバイナリ特徴ベクトルの集合から、前記モデルパラメータ蓄積手段に蓄積された混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、リファレンスコンテンツ又はクエリコンテンツに対応する１つのフィッシャーベクトルを算出する特徴ベクトル変換手段と、
クエリコンテンツのフィッシャーベクトルに最も類似する、リファレンスコンテンツのフィッシャーベクトルを検索する特徴ベクトル検索手段と
してコンピュータを機能させることを特徴とする検索プログラム。
【請求項２】
前記特徴ベクトル抽出手段は、ＯＲＢ(Oriented FAST and Rotated BRIEF)又はＦＲＥＡＫ(Fast Retina Keypoint)を用いてバイナリ特徴ベクトルの集合を抽出するようにコンピュータを機能させることを特徴とする請求項１に記載の検索プログラム。
【請求項３】
前記モデル推定手段は、訓練コンテンツのバイナリ特徴ベクトルの集合x1〜xTから、
Ｅ(Expectation)ステップについて、バイナリ特徴ベクトルxi毎に潜在変数iの期待値γt (i)を推定し、
Ｍ(Maximization)ステップについて、前記期待値γt (i)を用いて、混合比ｗi及びパラメータμiを更新し、
これらＥステップ及びＭステップを、収束するまで繰り返すことによって、混合比ｗi及びパラメータμiのパラメータ群λを算出する
λ（w1、・・・、wN及びμ11、・・・、μND）
ようにコンピュータを機能させることを特徴とする請求項１又は２に記載の検索プログラム。
【請求項４】
前記モデル推定手段は、
前記パラメータμidの対数尤度関数を偏微分で定義したフィッシャースコアｓidを算出し、
前記フィッシャースコアｓidの分散としてフィッシャー情報量ｆidを算出する
ようにコンピュータを機能させることを特徴とする請求項１から３のいずれか１項に記載の検索プログラム。
【請求項５】
前記特徴ベクトル変換手段は、前記バイナリ特徴ベクトルの集合毎に、前記パラメータμidを用いてフィッシャースコアｓidを算出し、これらをid毎に累積した累積フィッシャースコアｓ'idを算出し、
各累積フィッシャースコアｓ'idを、対応するフィッシャー情報量ｆidの平方根√ｆidで除算したフィッシャーベクトルｖidを算出する
ようにコンピュータを機能させることを特徴とする請求項４に記載の検索プログラム。
【請求項６】
前記モデル推定手段は、
前記パラメータμidの対数尤度関数を偏微分で定義したフィッシャースコアｓidを算出し、
前記フィッシャースコアｓidの混合要素i毎のベクトル（si1〜siD）に対して主成分分析を実行し、
前記主成分分析の結果、固有値の大きいものからK個を、前記フィッシャー情報量ｆidとして出力し、
前記固有値に対応するK個の固有ベクトルｇiKを更に出力し、
前記モデルパラメータ蓄積手段は、前記固有ベクトルｇiKを更に蓄積する
ようにコンピュータを機能させることを特徴とする請求項１から３のいずれか１項に記載の検索プログラム。
【請求項７】
前記特徴ベクトル変換手段は、前記バイナリ特徴ベクトルの集合毎に、前記パラメータμidを用いてフィッシャースコアｓidを算出し、これらをid毎に累積した累積フィッシャースコアｓ'idを算出し、
混合要素i毎に、各累積フィッシャースコアｓ'idのベクトル（s'i1〜siD）を、対応する固有ベクトルｇiｋ（gi1〜giK）を用いて正規化（射影）した正規化ベクトルｖ'ikを算出し、
正規化ベクトルｖ'ikを、対応する固有ベクトルｇikの平方根√ｇikで除算したフィッシャーベクトルｖikを算出する
ようにコンピュータを機能させることを特徴とする請求項６に記載の検索プログラム。
【請求項８】
訓練コンテンツから抽出されたモデルパラメータを用いて、リファレンスコンテンツの集合から、クエリコンテンツに類似したリファレンスコンテンツを検索する検索装置であって、
訓練コンテンツ、リファレンスコンテンツ及びクエリコンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合x1〜xTを抽出する特徴ベクトル抽出手段と、
訓練コンテンツのバイナリ特徴ベクトルの集合から、i（1≦i≦N）番目の多変量ベルヌーイ分布に関する混合比ｗiと、i番目の多変量ベルヌーイ分布のd（1≦d≦D）番目のパラメータμidと、パラメータμidに関するフィッシャー情報量ｆidとを算出するモデル推定手段と、
混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを蓄積するモデルパラメータ蓄積手段と、
リファレンスコンテンツ又はクエリコンテンツのバイナリ特徴ベクトルの集合から、前記モデルパラメータ蓄積手段の混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、リファレンスコンテンツ又はクエリコンテンツに対応する１つのフィッシャーベクトルを算出する特徴ベクトル変換手段と、
クエリコンテンツのフィッシャーベクトルに最も類似する、リファレンスコンテンツのフィッシャーベクトルを検索する特徴ベクトル検索手段と
を有することを特徴とする検索装置。
【請求項９】
装置を用いて、訓練コンテンツから抽出されたモデルパラメータを用いて、リファレンスコンテンツの集合から、クエリコンテンツに類似したリファレンスコンテンツを検索する検索方法であって、
モデルパラメータを蓄積する第１のステップとして、
訓練コンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合x1〜xTを抽出し、
訓練コンテンツのバイナリ特徴ベクトルの集合から、i（1≦i≦N）番目の多変量ベルヌーイ分布に関する混合比ｗiと、i番目の多変量ベルヌーイ分布のd（1≦d≦D）番目のパラメータμidと、パラメータμidに関するフィッシャー情報量ｆidとを算出し、
混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを蓄積し、
リファレンス情報を蓄積する第２のステップとして、
リファレンスコンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合を抽出し、
リファレンスコンテンツそれぞれのバイナリ特徴ベクトルの集合から、モデルパラメータとして蓄積された混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、１つのフィッシャーベクトルを算出し、
前記フィッシャーベクトルを蓄積し、
クエリコンテンツからリファレンスコンテンツを検索する第３のステップとして、
クエリコンテンツそれぞれのバイナリ特徴ベクトルの集合から、モデルパラメータとして蓄積された混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、１つのフィッシャーベクトルを算出し、
クエリコンテンツのフィッシャーベクトルに最も類似する、リファレンスコンテンツのフィッシャーベクトルを検索する
を有することを特徴とする検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特徴ベクトルの集合で表されるリファレンスコンテンツ（検索対象のコンテンツ）の集合から、同じく特徴ベクトルの集合で表されるクエリコンテンツ（検索キーとなるコンテンツ）に類似したリファレンスコンテンツを検索する技術に関する。特に、特徴ベクトルの集合で表されるマルチメディアコンテンツ（例えば画像）の検索に適する。
【背景技術】
【０００２】
近年、オンライン／オフラインに限られず、ストレージの大容量化に伴って、大量のコンテンツを蓄積することが可能となっている。また、携帯電話機やスマートフォンに代表される情報端末機器の普及によって、ユーザ自ら取得した写真データのようなデジタルコンテンツも、データベースに大量かつ容易に蓄積することができる。オフラインデータベースとして、ＨＤＤ(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は、画像の局所特徴量を量子化し、量子化後の局所特徴量を単語と見立て、同様に頻度により定義される１つの特徴ベクトルとして表現し、ＩＤＦを用いた重み付けを利用して同一の類推方法を適用することができる。
【０００７】
更に、近年は、「Bag-of-Visual Words」の枠組みを発展させたフィッシャーベクトルに基づく技術が注目されている（例えば非特許文献３参照）。フィッシャーベクトルを用いた技術によれば、特徴ベクトルを混合ガウス分布でモデル化し、混合ガウス分布のパラメータに関するフィッシャーカーネルを、明示的に特徴ベクトルへマッピングしたものを画像を表現する特徴ベクトルとして利用することができる。この技術によれば、特徴ベクトルの集合を１つの固定長の特徴ベクトルで記述することができ、更にユークリッド距離を特徴ベクトル間の距離尺度として用いることができる。
【０００８】
図１は、従来技術におけるコンテンツの検索装置の機能構成図である。
【０００９】
図１の検索装置１によれば、モデルパラメータを生成するために、多数の訓練コンテンツを予め入力し、モデルパラメータを予め蓄積しておく。また、検索装置１は、多数のリファレンスコンテンツ（検索対象のコンテンツ）を予め入力し、モデルパラメータを用いて正規化に変換したリファレンス特徴ベクトルを予め蓄積しておく。その上で、検索装置１は、クエリコンテンツ（検索キーのコンテンツ）について、モデルパラメータを用いてクエリ特徴ベクトルを正規化し、そのクエリ特徴ベクトルに最も類似するリファレンス特徴ベクトルを検索し、リファレンスコンテンツを特定する。
【００１０】
図１によれば、検索装置１は、特徴ベクトル抽出部１１と、モデル推定部１２と、モデルパラメータ蓄積部１３と、特徴ベクトル変換部１４と、リファレンス情報蓄積部１５と、特徴ベクトル検索部１６とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００１１】
特徴ベクトル抽出部１１は、各マルチメディアコンテンツから、特徴ベクトルの集合を抽出する。例えばマルチメディアコンテンツが画像である場合、その特徴ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルである。訓練コンテンツは、特徴ベクトルの集合に変換され、モデル推定部１２へ出力される。また、リファレンスコンテンツ及びクエリコンテンツもそれぞれ、特徴ベクトルの集合に変換され、特徴ベクトル変換部１４へ出力される。これら全てのコンテンツについて、同一次元数（D次元）の特徴ベクトルが抽出される。
【００１２】
物体認識に用いる特徴ベクトルの抽出アルゴリズムとしては、回転やスケールの変化にロバストな、例えばＳＩＦＴ(Scale-Invariant Feature Transform)やＳＵＲＦ(Speeded
Up Robust Features)が用いられる。例えば、ＳＩＦＴの場合、１枚の画像からは１２８次元の特徴ベクトルの集合が抽出される。ＳＩＦＴとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる特徴ベクトルを記述する技術である。一方で、ＳＵＲＦの場合、ＳＩＦＴよりも高速処理が可能であって、１枚の画像から６４次元の特徴ベクトルの集合が抽出される。ＳＩＦＴは、処理コストが高く且つリアルタイムマッチングが困難であるのに対し、ＳＵＲＦは、積分画像を利用することによって処理を高速化している。
【００１３】
モデル推定部１２は、特徴ベクトル抽出部１１から出力された訓練コンテンツの特徴ベクトルの集合用いて混合ガウス分布(Gaussian Mixture Model)のモデルパラメータを推定し、そのモデルパラメータを出力する。Bag-of-Featuresの識別性能は、確率密度分布のモデル化の精度に依存する。混合ガウス分布は混合数とパラメータを調整することで、任意の連続な密度関数を表現できるため、混合ガウス分布を用いる。
【００１４】
モデルパラメータ蓄積部１３は、モデル推定部１２から出力されたモデルパラメータを蓄積する。
【００１５】
特徴ベクトル変換部１４は、リファレンスコンテンツ及びクエリコンテンツそれぞれの特徴ベクトルの集合を、１つの固定長の特徴ベクトルへ明示的にマッピングする。このマッピングには、モデルパラメータ蓄積部１３のモデルパラメータに基づくフィッシャーカーネルが用いられる。具体的には、特徴ベクトル集合からモデルの対数尤度関数の勾配ベクトルを求め、モデルパラメータに関するフィッシャー情報行列により正規化をすることで、特徴ベクトルへマッピングする。非特許文献３に記載された技術によれば、フィッシャー情報行列が対角行列と仮定されている。変換された１つの特徴ベクトルは、フィッシャーベクトルと称される。特徴ベクトル変換部１４は、リファレンスコンテンツの特徴ベクトルの集合からマッピングしたフィッシャーベクトルを、リファレンス蓄積部１５へ出力し、クエリコンテンツの特徴ベクトルの集合からマッピングしたフィッシャーベクトルを、特徴ベクトル検索部１６へ出力する。
【００１６】
リファレンス情報蓄積部１５は、特徴ベクトル変換部１４から出力された、リファレンスコンテンツの正規化されたフィッシャーベクトルを蓄積する。
【００１７】
特徴ベクトル検索部１６は、リファレンス情報蓄積部１５を用いて、クエリコンテンツのフィッシャーベクトルに最も類似する、リファレンスコンテンツのフィッシャーベクトルを検索する。ここでは、ユークリッド距離を用いることができ、クエリコンテンツのフィッシャーベクトルとの間の距離が短い、リファレンスコンテンツのフィッシャーベクトルが検索され、そのリファレンスコンテンツが特定される。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２０１０−２８２５８１号公報
【非特許文献】
【００１９】
【非特許文献１】J. Sivic et al., "Video Google: A Text Retrieval Approach toObject Matching in Videos," in Proc. ICCV, 2003.
【非特許文献２】D. G. Lowe, "Distinctive Image Features from Scale-InvariantKeypoints," International Journal of Computer Vision, vol. 60, no. 2, pp.91-110, 2004.
【非特許文献３】F. Perronnin, J. Sanchez, and T. Mensink, "Improving the FisherKernel for Large-Scale Image Classification," in Proc. ECCV, 2010.
【非特許文献４】E. Rublee, V. Rabaud, K. Konolige, and G. Bradski, "ORB: Anefficient alternative to SIFT or SURF," in Proc. ICCV, 2011.
【非特許文献５】A. Alahi, R. Ortiz, and P. Vandergheynst, "FREAK: Fast RetinaKeypoint," in Proc. CVPR, 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.
【非特許文献７】三品陽平、「CVReadiing、ORB: an efficient alternative toSIFT or SURF」、[online]、［平成２４年１２月５日検索］、インターネット＜URL:http://www.vision.cs.chubu.ac.jp/CV-R/jpdf/Rublee_iccv2011.pdf＞
【非特許文献８】原田達也、「大規模データを用いた一般物体・シーン認識の潮流と理論」、[online]、［平成２４年１２月５日検索］、インターネット＜URL:https://ipsj.ixsq.nii.ac.jp/ej/index.php?active_action=repository_view_main_item_detail&item_id=81096&item_no=1&page_id=13&block_id=8＞
【発明の概要】
【発明が解決しようとする課題】
【００２０】
しかしながら、スマートフォンやタブレット端末のようなモバイル端末が普及する中で、コンテンツ検索処理に対して、更なる省メモリ化及び高速マッチング化が要求されてきている。特に、拡張現実感（Augmented Reality, AR）の用途における画像認識の技術分野によれば、リアルタイムに処理するべく、ＳＩＦＴやＳＵＲＦよりも更に高速にコンテンツを検索することが要求される。
【００２１】
そこで、本発明によれば、ＳＩＦＴやＳＵＲＦよりも更に高速にコンテンツを検索することができる検索装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００２２】
本発明によれば、装置に搭載されたコンピュータを、訓練コンテンツから抽出されたモデルパラメータを用いて、リファレンスコンテンツの集合から、クエリコンテンツに類似したリファレンスコンテンツを検索するように機能させる検索プログラムであって、
訓練コンテンツ、リファレンスコンテンツ及びクエリコンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合x1〜xTを抽出する特徴ベクトル抽出手段と、
訓練コンテンツのバイナリ特徴ベクトルの集合から、i（1≦i≦N）番目の多変量ベルヌーイ分布に関する混合比ｗiと、i番目の多変量ベルヌーイ分布のd（1≦d≦D）番目のパラメータμidと、パラメータμidに関するフィッシャー情報量ｆidとを算出するモデル推定手段と、
混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを蓄積するモデルパラメータ蓄積手段と、
リファレンスコンテンツ又はクエリコンテンツのバイナリ特徴ベクトルの集合から、モデルパラメータ蓄積手段に蓄積された混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、リファレンスコンテンツ又はクエリコンテンツに対応する１つのフィッシャーベクトルを算出する特徴ベクトル変換手段と、
クエリコンテンツのフィッシャーベクトルに最も類似する、リファレンスコンテンツのフィッシャーベクトルを検索する特徴ベクトル検索手段と
してコンピュータを機能させることを特徴とする。
【００２３】
本発明の検索プログラムにおける他の実施形態によれば、
特徴ベクトル抽出手段は、ＯＲＢ(Oriented FAST and Rotated BRIEF)又はＦＲＥＡＫ(Fast Retina Keypoint)を用いてバイナリ特徴ベクトルの集合を抽出するようにコンピュータを機能させることも好ましい。
【００２４】
本発明の検索プログラムにおける他の実施形態によれば、
モデル推定手段は、訓練コンテンツのバイナリ特徴ベクトルの集合x1〜xTから、
Ｅ(Expectation)ステップについて、バイナリ特徴ベクトルxi毎に潜在変数iの期待値γt (i)を推定し、
Ｍ(Maximization)ステップについて、期待値γt (i)を用いて、混合比ｗi及びパラメータμiを更新し、
これらＥステップ及びＭステップを、収束するまで繰り返すことによって、混合比ｗi及びパラメータμiのパラメータ群λを算出する
λ（w1、・・・、wN及びμ11、・・・、μND）
ようにコンピュータを機能させることも好ましい。
【００２５】
本発明の検索プログラムにおける他の実施形態によれば、
モデル推定手段は、
パラメータμidの対数尤度関数を偏微分で定義したフィッシャースコアｓidを算出し、
フィッシャースコアｓidの分散としてフィッシャー情報量ｆidを算出する
ようにコンピュータを機能させることも好ましい。
【００２６】
本発明の検索プログラムにおける他の実施形態によれば、
特徴ベクトル変換手段は、バイナリ特徴ベクトルの集合毎に、パラメータμidを用いてフィッシャースコアｓidを算出し、これらをid毎に累積した累積フィッシャースコアｓ'idを算出し、
各累積フィッシャースコアｓ'idを、対応するフィッシャー情報量ｆidの平方根√ｆidで除算したフィッシャーベクトルｖidを算出する
ようにコンピュータを機能させることも好ましい。
【００２７】
本発明の検索プログラムにおける他の実施形態によれば、
モデル推定手段は、
パラメータμidの対数尤度関数を偏微分で定義したフィッシャースコアｓidを算出し、
フィッシャースコアｓidの混合要素i毎のベクトル（si1〜siD）に対して主成分分析を実行し、
主成分分析の結果、固有値の大きいものからK個を、フィッシャー情報量ｆidとして出力し、
固有値に対応するK個の固有ベクトルｇiKを更に出力し、
モデルパラメータ蓄積手段は、固有ベクトルｇiKを更に蓄積する
ようにコンピュータを機能させることも好ましい。
【００２８】
本発明の検索プログラムにおける他の実施形態によれば、
特徴ベクトル変換手段は、バイナリ特徴ベクトルの集合毎に、パラメータμidを用いてフィッシャースコアｓidを算出し、これらをid毎に累積した累積フィッシャースコアｓ'idを算出し、
混合要素i毎に、各累積フィッシャースコアｓ'idのベクトル（s'i1〜siD）を、対応する固有ベクトルｇiｋ（gi1〜giK）を用いて正規化（射影）した正規化ベクトルｖ'ikを算出し、
正規化ベクトルｖ'ikを、対応する固有ベクトルｇikの平方根√ｇikで除算したフィッシャーベクトルｖikを算出する
ようにコンピュータを機能させることも好ましい。
【００２９】
本発明によれば、訓練コンテンツから抽出されたモデルパラメータを用いて、リファレンスコンテンツの集合から、クエリコンテンツに類似したリファレンスコンテンツを検索する検索装置であって、
訓練コンテンツ、リファレンスコンテンツ及びクエリコンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合x1〜xTを抽出する特徴ベクトル抽出手段と、
訓練コンテンツのバイナリ特徴ベクトルの集合から、i（1≦i≦N）番目の多変量ベルヌーイ分布に関する混合比ｗiと、i番目の多変量ベルヌーイ分布のd（1≦d≦D）番目のパラメータμidと、パラメータμidに関するフィッシャー情報量ｆidとを算出するモデル推定手段と、
混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを蓄積するモデルパラメータ蓄積手段と、
リファレンスコンテンツ又はクエリコンテンツのバイナリ特徴ベクトルの集合から、モデルパラメータ蓄積手段の混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、リファレンスコンテンツ又はクエリコンテンツに対応する１つのフィッシャーベクトルを算出する特徴ベクトル変換手段と、
クエリコンテンツのフィッシャーベクトルに最も類似する、リファレンスコンテンツのフィッシャーベクトルを検索する特徴ベクトル検索手段と
を有することを特徴とする。
【００３０】
本発明によれば、装置を用いて、訓練コンテンツから抽出されたモデルパラメータを用いて、リファレンスコンテンツの集合から、クエリコンテンツに類似したリファレンスコンテンツを検索する検索方法であって、
モデルパラメータを蓄積する第１のステップとして、
訓練コンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合x1〜xTを抽出し、
訓練コンテンツのバイナリ特徴ベクトルの集合から、i（1≦i≦N）番目の多変量ベルヌーイ分布に関する混合比ｗiと、i番目の多変量ベルヌーイ分布のd（1≦d≦D）番目のパラメータμidと、パラメータμidに関するフィッシャー情報量ｆidとを算出し、
混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを蓄積し、
リファレンス情報を蓄積する第２のステップとして、
リファレンスコンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合を抽出し、
リファレンスコンテンツそれぞれのバイナリ特徴ベクトルの集合から、モデルパラメータとして蓄積された混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、１つのフィッシャーベクトルを算出し、
フィッシャーベクトルを蓄積し、
クエリコンテンツからリファレンスコンテンツを検索する第３のステップとして、
クエリコンテンツそれぞれのバイナリ特徴ベクトルの集合から、モデルパラメータとして蓄積された混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、１つのフィッシャーベクトルを算出し、
クエリコンテンツのフィッシャーベクトルに最も類似する、リファレンスコンテンツのフィッシャーベクトルを検索する
を有することを特徴とする。
【発明の効果】
【００３１】
本発明の検索装置、プログラム及び方法によれば、ＳＩＦＴやＳＵＲＦよりも更に高速にコンテンツを検索することができる。
【図面の簡単な説明】
【００３２】
【図１】従来技術におけるコンテンツの検索装置の機能構成図である。
【図２】本発明におけるコンテンツの検索装置の機能構成図である。
【発明を実施するための形態】
【００３３】
以下、本発明の実施の形態について、図面を用いて詳細に説明する。
【００３４】
本発明の検索装置、プログラム及び方法によれば、訓練コンテンツから抽出されたモデルパラメータを用いて、リファレンスコンテンツの集合から、クエリコンテンツに類似したリファレンスコンテンツを検索する。ここで、本発明によれば、コンテンツから抽出される特徴ベクトルについて、バイナリ特徴ベクトルを抽出することを第１の特徴としている。また、これらのバイナリ特徴ベクトルを多変量混合ベルヌーイ分布でモデル化し、それらのモデルパラメータからフィッシャーベクトルを抽出することを第２の特徴としている。
【００３５】
図２は、本発明におけるコンテンツの検索装置の機能構成図である。
【００３６】
図２の検索装置における機能構成は、図１の機能構成と同じものである。しかしながら、各機能構成部における処理内容が異なる。以下では、検索装置１における特徴ベクトル抽出部１１と、モデル推定部１２と、モデルパラメータ蓄積部１３と、特徴ベクトル変換部１４と、リファレンス情報蓄積部１５と、特徴ベクトル検索部１６とについて、順に説明する。
【００３７】
［特徴ベクトル抽出部１１］
本発明における特徴ベクトル抽出部１１は、訓練コンテンツ、リファレンスコンテンツ及びクエリコンテンツそれぞれについて、D次元のバイナリ特徴ベクトルの集合X＝{x1〜xT}を抽出する。例えばマルチメディアコンテンツが画像である場合、その特徴ベクトルは、画像の局所特徴領域から抽出された局所バイナリ特徴ベクトルである。訓練コンテンツから抽出されたバイナリ特徴ベクトルの集合は、モデル推定部１２へ出力される。リファレンスコンテンツ及びクエリコンテンツから抽出されたバイナリ特徴ベクトルの集合はそれぞれ、特徴ベクトル変換部１４へ出力される。
【００３８】
本発明によれば、バイナリ特徴ベクトルの抽出アルゴリズムとして、ＯＲＢ(Oriented FAST and Rotated BRIEF)（例えば非特許文献４及び非特許文献７参照）又はＦＲＥＡＫ(Fast Retina Keypoint)（例えば非特許文献５）を用いる。ＯＲＢの場合、１つのコンテンツから２５６ビットのバイナリ特徴ベクトルの集合が抽出される。例えば、高速にマッチングを実行するべく、バイナリコードによる特徴記述としてＢＲＩＥＦ(Binary Robust Independent Elementary Features)がある。本発明によれば、ＢＲＩＥＦに回転不変性を導入した特徴記述をすることができる「ＯＲＢ」を用いる。特に、ＯＲＢによれば、ＳＩＦＴやＳＵＲＦと比較して、同等以上の精度を保持すると共に、数百倍の高速化を実現することができる。
【００３９】
＜ＯＲＢについて＞
ＯＲＢは、「特徴点検出処理」と「特徴ベクトル記述処理」との２つのステップから構成される。
【００４０】
（特徴点検出処理）
ＯＲＢにおける特徴点検出処理によれば、高速にキーポイントを検出するためにＦＡＳＴ(Features from Accelerated Segment Test)を用いる。また、ＦＡＳＴでは、スケール変化に対してロバストではないため、画像を複数のサイズに変換し、それぞれのサイズの画像から特徴点を抽出する。
【００４１】
また、既存のＦＡＳＴには、回転不変性を得るためのキーポイントのオリエンテーション算出のアルゴリズムがない。そのために、ＯＲＢでは、回転不変性を得るべくOriented FASTを採用している。オリエンテーションを基準として特徴記述をすることによって、入力画像が回転していても、同一なキーポイントは同一な特徴量となって検出することができる。そのために、キーポイントの中心とパッチの輝度の重心の方向ベクトルを用いる。
【００４２】
（特徴ベクトル記述処理）
次に、ＯＲＢにおける特徴ベクトル記述処理によれば、検出された特徴点毎に、BRIEF特徴ベクトル記述子によってバイナリ特徴ベクトルが抽出される。これらは、特徴点周辺の２箇所のピクセルの輝度の大小関係から求められる。
【００４３】
ＢＲＩＥＦは、バイナリコードによってキーポイントの特徴量記述を実行することができる。ＳＩＦＴやＳＵＲＦによれば、特徴量記述に高次元の実数を用いていた。しかしながら、高次元の実数を用いた場合、メモリ容量の増加と類似度計算の増加と問題となる。そこで、ＯＲＢに基づくＢＲＩＥＦを用いることによって、バイナリコードによって特徴記述することで省メモリ化し、類似度計算にハミング距離を用いることで処理コストの抑制を実現する。
【００４４】
ＢＲＩＥＦによれば、パッチ内においてランダムに選択された２点の輝度差の符号からバイナリコードを生成する。選択するピクセルは、キーポイント位置を中心としたガウス分布に従ってランダムに選択する。ここで、ＯＲＢは、更に高精度にマッチングをさせるために、学習を用いてピクセルを選択している。選択するピクセル位置は、ペアのビット分散が大きく且つＮ組のペアの相関が低い場合に、特徴記述能力が高いバイナリコードとして、特徴記述に使用する。Ｎ組のペアは、Greedyアルゴリズムを用いて絞り込む。
【００４５】
［モデル推定部１２］
モデル推定部１２は、訓練コンテンツのバイナリ特徴ベクトルの集合から、i番目の多変量ベルヌーイ分布に関する混合比ｗiと、i番目の多変量ベルヌーイ分布のd番目のパラメータμidとを算出する。これらは、モデルパラメータλとして算出される。
λ（w1、・・・、wN及びμ11、・・・、μND）
また、本発明におけるモデル推定部１２は、パラメータμidに関するフィッシャー情報量ｆidも更に算出する。
f11、・・・、fND（N×D個）：フィッシャー情報量
【００４６】
＜多変量混合ベルヌーイ分布に基づくパラメータwi及びμidの算出＞
本発明によれば、バイナリ特徴ベクトルの集合を「多変量混合ベルヌーイ分布」でモデル化したモデルパラメータλを推定する。ベルヌーイ分布とは、確率pで1を、確率q＝1-pで0をとる離散確率分布という。Xをベルヌーイ分布に従う確率変数とすれば、確率変数Xの平均はp、分散はpq＝p(1-p)となる。「多変量混合ベルヌーイ分布」は、バイナリ特徴ベクトルxtが生成される確率p(xt|λ)を表現する。
【数１】
2014146207.tif 000003
N：混合数
【００４７】
混合分布であるため、p1からpNまでの異なる多変量ベルヌーイ分布が、それぞれ混合比wiで選択され、xtが生成される。i番目の多変量ベルヌーイ分布から、バイナリ特徴ベクトルxtが生成される確率は、以下の式で表現される。
【数２】
2014146207.tif 000004
μid：i番目の多変量ベルヌーイ分布のd番目のパラメータ
xt,d：バイナリ特徴ベクトルxtのd番目のビット
D：バイナリ特徴ベクトルのビット長
pi（xt|λ）：バイナリ特徴ベクトルxtがi番目の多変量ベルヌーイ分布から生成
された際に、d番目のビットが1となる確率
【００４８】
これらのパラメータは、具体的には、訓練コンテンツのバイナリ特徴ベクトルの集合x1〜xTから、ＥＭ(Expectation-Maximization)アルゴリズムの繰り返し処理によって推定する。ＥＭアルゴリズムとは、統計学について、確率モデルのパラメータを最尤法に基づいて推定方法であって、観測不可能な潜在変数に確率モデルが依存する場合に用いられるものである。
【００４９】
Ｅ(Expectation、期待値)ステップでは、バイナリ特徴ベクトルxi毎に、潜在変数ztiの分布に基づいて、モデルの尤度の期待値γt(i)を推定する。
【数３】
2014146207.tif 000005
γt(i)：t番目の訓練ベクトルがi番目の多変量ベルヌーイ分布から生成された確率
【００５０】
Ｍ(Maximization、最大化)ステップでは、Ｅステップで算出された尤度の期待値γt(i)を最大化するべく、混合比ｗi及びパラメータμiを更新する。Ｍステップで算出されたパラメータは、次のＥステップにおける潜在変数の分布を決定するために用いられる。
【数４】
2014146207.tif 000006
【００５１】
これらＥステップ及びＭステップを、収束するまで繰り返すことによって、対数尤度を最大化する混合比ｗi及びパラメータμiのパラメータ群λを算出する
λ（w1、・・・、wN及びμ11、・・・、μND）
【００５２】
＜フィッシャー情報量fidの算出＞
また、モデル推定部１２は、多変量混合ベルヌーイ分布のパラメータμidに関する「フィッシャー情報量fid」を算出する。フィッシャーカーネル(Fisher kernel）は、生成的アプローチ(generative
approach)と判別的アプローチ(discriminative approach)とを結合させる枠組みである（例えば非特許文献８参照）。フィッシャーカーネルでは、最初に、局所記述子を生成する確率密度分布から導出される勾配ベクトルを計算し、この勾配ベクトルをフィッシャー情報行列で正規化したものを、画像を表現する１つの特徴ベクトルとする。フィッシャー情報行列を対角行列と仮定した場合、正規化は各パラメータに関する勾配を、フィッシャー情報量で正規化することと同値である。フィッシャーカーネルによれば、Bag of Featuresと比較して、同一サイズのコードブックであっても、要素数のより多い特徴ベクトルを得ることができる。即ち、特徴ベクトルの表現する情報が多いため、計算コストの高いカーネル法を利用して高次元空間へ射影する必要がなく、線形的な識別であっても十分な性能を引き出すことができる。
【００５３】
（フィッシャー情報行列を対角行列とした第１の実施形態）
モデル推定部１２は、
（Ｓ１１）パラメータμidの対数尤度関数を偏微分で定義したフィッシャースコアｓidを算出し、
（Ｓ１２）フィッシャースコアｓidの分散としてフィッシャー情報量ｆidを算出する。
【００５４】
フィッシャー情報量は、フィッシャースコアの２次モーメントで定義される。μidに関するフィッシャースコアは、多変量混合ベルヌーイ分布に関して、バイナリ特徴ベクトル集合X＝{x1、・・・、xT}を観測した際の対数尤度関数L(λ|X)＝log P(X|λ)のμidに関する偏微分で定義される。
【００５５】
μidに関するフィッシャースコアsidは、以下の式で定義される。
【数５】
2014146207.tif 000007
【００５６】
また、前述のγt(i)を用いると、以下の式となる。
【数６】
2014146207.tif 000008
【００５７】
μidに関するフィッシャー情報量fidは、以下の式によって定義される。
【数７】
2014146207.tif 000009
【００５８】
従来（非特許文献３）では、フィッシャー情報量を、パラメータλから近似的に計算している。本発明では、以下に示すようにフィッシャー情報量をサンプルから直接計算することで、近似ではない正確なフィッシャー情報量を計算し、精度を担保する。
数７は、xtの独立性と、
【数８】
2014146207.tif 000010
とによって、フィッシャー情報量ｆidは、以下のようになる。
【数９】
2014146207.tif 000011
【００５９】
（主成分分析を用いた第２の実施形態）
モデル推定部１２は、
（Ｓ２１）対数尤度関数のパラメータμidに関する偏微分で定義されるフィッシャースコアｓidを算出し、
（Ｓ２２）フィッシャースコアｓidに対して主成分分析を実行し、
（Ｓ２３）主成分分析の結果、固有値の大きいものからK個を、正規化パラメータｆidとして出力し、
（Ｓ２４）固有値に対応するK個の固有ベクトルｇiKを更に出力する。
【００６０】
特に画像の場合、バイナリ特徴ベクトルのビット間には相関がある。そのために、第１の実施形態のような対角行列の仮定は必ずしも成立しない。そのため、第２の実施形態によれば、以下のように主成分分析を用いて無相関化と正規化を実行する。主成分分析とは、直交回転を用いて変数間に相関がある元の観測値を、相関の無い主成分とよばれる値に変換することをいう。
【００６１】
多変量混合ベルヌーイ分布のi番目の多変量ベルヌーイ分布について、フィッシャースコアｓi1、・・・、ｓiDを、バイナリ特徴ベクトル集合x1、・・・、xTに対して算出し、主成分分析を実行する。主成分分析の結果の固有値の大きいものからK個を、fi1、・・・、fiKとし、対応する固有ベクトルをgi1、・・・、giKとし、モデルパラメータとしてモデルパラメータ蓄積部１３へ出力する。
【００６２】
［モデルパラメータ蓄積部１３］
モデルパラメータ蓄積部１３は、モデル推定部１２から出力されたモデルパラメータとして、混合比ｗi（i＝1〜N）パラメータμid（i＝1〜N, d＝1〜D）とフィッシャー情報量ｆid（i＝1〜N, d＝1〜D）とを蓄積する。また、第２の実施形態によれば、モデルパラメータ蓄積部１３は、固有ベクトルｇik（i＝1〜N, k＝1〜K個）も更に蓄積する。
【００６３】
［特徴ベクトル変換部１４］
特徴ベクトル変換部１４は、リファレンスコンテンツ又はクエリコンテンツのバイナリ特徴ベクトルの集合x1〜xTから、モデルパラメータ蓄積部１３の混合比ｗiとパラメータμidとフィッシャー情報量ｆidとを用いて、リファレンスコンテンツ又はクエリコンテンツに対応する１つのフィッシャーベクトルｖを算出する。
【００６４】
（モデル推定部１２の第１の実施形態に対して）
特徴ベクトル変換部１４は、
（Ｓ１３）バイナリ特徴ベクトルの集合x1〜xT毎に、パラメータｗi及びμidを用いてフィッシャースコアｓid（s11〜sND）を算出し、これらをid毎に累積した累積フィッシャースコアｓ'id（s'11〜s'ND）算出し、
（Ｓ１４）各累積フィッシャースコアｓ'idを、対応するフィッシャー情報量ｆidの平方根√ｆidで除算したフィッシャーベクトルｖidを算出する。
vid＝sid／√fid
f11、・・・、fND（N×D個）：フィッシャー情報量
【００６５】
（モデル推定部１２の第２の実施形態に対して）
特徴ベクトル変換部１４は、
（Ｓ２５）バイナリ特徴ベクトルの集合毎に、パラメータｗi及びμidを用いてフィッシャースコアｓid（s11〜sND）を算出し、これらをid毎に累積した累積フィッシャースコアｓ'id（s'11〜s'ND）を算出し、
（Ｓ２６）混合要素i毎に、各累積フィッシャースコアｓ'id（s'i1〜s’iD）、対応する固有ベクトルｇiKを用いて正規化（射影）した正規化ベクトルｖ'idを算出し、
（Ｓ２７）正規化ベクトルｖ'idを、対応する固有ベクトルｇidの平方根√ｇidで除算したフィッシャーベクトルｖidを算出する。
vid＝v’id／√gid
【００６６】
特徴ベクトル変換部１４は、リファレンスコンテンツについて変換されたフィッシャーベクトルは、リファレンス情報蓄積部１５へ出力し、クエリコンテンツについて変換されたフィッシャーベクトルは、特徴ベクトル変換部１６へ出力される。
【００６７】
［特徴ベクトル検索部１６］
特徴ベクトル検索部１６は、従来技術の図１と同様に、リファレンス情報蓄積部１５を用いて、クエリコンテンツのフィッシャーベクトルｖQに最も類似する、リファレンスコンテンツのフィッシャーベクトルｖRを検索する。ここでは、ユークリッド距離を用いることができ、vQ及びvRの間の距離が短いほど、クエリコンテンツに対してそのリファレンスコンテンツの類似度が高いことを意味する。具体的には、最近傍探索(Approximate Nearest Neighbor)アルゴリズムの１つである直積量子化を用いた方法（例えば非特許文献６参照）やＬＳＨ(Locality-Sensitive Hashing)を用いることも好ましい。
【００６８】
以上、詳細に説明したように、本発明の検索装置、プログラム及び方法によれば、ＳＩＦＴやＳＵＲＦよりも更に高速にコンテンツを検索することができる。
【００６９】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００７０】
１  検索装置
１１  特徴ベクトル抽出部
１２  モデル推定部
１３  モデルパラメータ蓄積部
１４  特徴ベクトル変換部
１５  リファレンス情報蓄積部
１６  特徴ベクトル検索部
【図１】
2014146207.tif 000012
【図２】
2014146207.tif 000013