(57)【特許請求の範囲】
【請求項１】
特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索する検索装置であって、
リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、
前記クエリコンテンツについて、クエリ特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、
前記リファレンス情報蓄積手段を用いて、前記クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、前記クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、
前記クエリハッシュ識別値に対応する全ての前記リファレンスコンテンツ識別値を、前記距離が短い昇順にソートする距離ソート手段と、
ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合（％）に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、
抽出された前記リファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段と
を有することを特徴とする検索装置。
【請求項２】
前記リファレンス情報蓄積手段は、前記リファレンス特徴ベクトルに代えて、当該リファレンス特徴ベクトルに対するリファレンス符号を蓄積しており、
前記ハッシュ化手段は、多数の前記リファレンス特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のリファレンスハッシュ識別値を更に導出し、
前記リファレンス特徴ベクトルを、リファレンス符号に符号化し、前記リファレンス情報蓄積手段へ蓄積する符号化手段を更に有し、
前記距離算出手段は、前記リファレンス情報蓄積手段を用いて、前記クエリハッシュ識別値に対応する各リファレンス符号と、前記クエリ特徴ベクトルとの間の距離を算出する
ことを特徴とする請求項１に記載の検索装置。
【請求項３】
前記類似検索手段は、前記クエリコンテンツに含まれる複数のクエリ特徴ベクトル毎に導出された複数のリファレンスコンテンツ識別値を、当該リファレンスコンテンツ識別値毎に投票し、その投票数に応じたリファレンスコンテンツ識別値を抽出することを特徴とする請求項１又は２に記載の検索装置。
【請求項４】
前記リファレンス情報蓄積手段は、前記リファレンスコンテンツ毎に、前記リファレンスハッシュ識別値の頻度のＬｐノルムを蓄積し、
前記類似検索手段は、前記リファレンスコンテンツ毎の得票数を、対応するリファレンスコンテンツのＬｐノルムで正規化した値を、類似度として算出することを特徴とする請求項３に記載の検索装置。
【請求項５】
前記符号化手段は、前記リファレンス特徴ベクトル及び前記クエリ特徴ベクトルに対して射影変換を行い、変換後の各次元の値を閾値で二値化することによって、バイナリ列のリファレンス符号及びクエリ符号を生成し、
前記距離算出手段は、前記リファレンス符号及びクエリ符号のハミング距離を算出する
ことを特徴とする請求項４に記載の検索装置。
【請求項６】
前記符号化手段は、
前記ハッシュ識別値に対応する代表ベクトルを蓄積しており、
前記リファレンス特徴ベクトルと、当該リファレンス特徴ベクトルのリファレンスハッシュ識別値に対応する代表ベクトルとの間のリファレンス差分ベクトルを算出し、そのリファレンス差分ベクトルをリファレンス符号に符号化する
ことを特徴とする請求項４に記載の検索装置。
【請求項７】
前記代表ベクトルは、当該ハッシュ識別値を持つ多数の特徴ベクトルの平均ベクトル又は中央値ベクトルから算出されることを特徴とする請求項６に記載の検索装置。
【請求項８】
前記符号化手段は、
直積量子化のためのコードブックを更に有し、
前記リファレンス差分ベクトルを、前記コードブックを用いて直積量子化によってリファレンス符号に符号化し、
前記クエリ特徴ベクトルと、前記クエリハッシュ識別値に対応する代表ベクトルとの間のクエリ差分ベクトルを算出するものであり、
前記距離算出手段は、前記リファレンス符号とクエリ差分ベクトルとのＬｐ距離を算出する
ことを特徴とする請求項７に記載の検索装置。
【請求項９】
前記ハッシュ化手段は、ベクトル量子化用のコードブックを更に有し、前記ハッシュ関数はベクトル量子化を行うことでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出する
ことを特徴とする請求項５又は８に記載の検索装置。
【請求項１０】
前記ハッシュ化手段は、前記リファレンス特徴ベクトル及びクエリ特徴ベクトルと、同次元の既定のベクトルとの内積の値を、所定閾値で離散化することでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出する
ことを特徴とする請求項５又は８に記載の検索装置。
【請求項１１】
前記ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであることを特徴とする請求項９又は１０に記載の検索装置。
【請求項１２】
特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索するように、コンピュータを機能させるプログラムであって、
リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、
前記クエリコンテンツについて、クエリ特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、
前記リファレンス情報蓄積手段を用いて、前記クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、前記クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、
前記クエリハッシュ識別値に対応する全ての前記リファレンスコンテンツ識別値を、前記距離が短い昇順にソートする距離ソート手段と、
ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合（％）に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、
抽出された前記リファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段と
してコンピュータを機能させることを特徴とする検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、同じく特徴ベクトルの集合で表されるクエリコンテンツ（検索キー）に類似したリファレンスコンテンツを高精度に検索する技術に関する。特に、高次元の特徴ベクトルの集合で表されるマルチメディアコンテンツ（例えば画像）の検索に適する。
【背景技術】
【０００２】
近年、オンライン／オフラインに限られず、ストレージの大容量化に伴って、大量のコンテンツを蓄積することが可能となっている。また、携帯電話機やスマートフォンに代表される情報端末機器の普及によって、ユーザ自ら取得した写真データのようなデジタルコンテンツも、データベースに大量かつ容易に蓄積することができる。オフラインデータベースとして、ＨＤＤ(Hard Disk Drive)、ＤＶＤ(Digital Versatile Disk)、Blu-ray disc等の記憶装置がある。また、オンラインデータベースとしては、Flickr（登録商標）やMySpace（登録商標）のようなソーシャルネットワークサービスがある。これら記憶装置及びサービスによれば、データベースに蓄積された個人の大量且つ多様なマルチメディアコンテンツを検索するする技術が重要となる。
【０００３】
マルチメディアコンテンツを検索するために、これらコンテンツから多数の特徴ベクトルを抽出し、この特徴ベクトルの集合同士の間の類似度が高いコンテンツを検索結果として出力する技術がある。この技術によれば、マルチメディアコンテンツの特徴ベクトルを量子化し、量子化された特徴ベクトルの頻度からヒストグラムを作成する。そのヒストグラム同士の間のＬ１ノルム又はＬ２ノルムの距離によって類似度（距離）を算出する。ノルムとは、２つの点の間の距離を表す。Ｌ１ノルムとは、２つの点の各次元の値の絶対値の和を意味し、Ｌ２ノルムとは、２つの点の各次元の値を二乗した和を意味する。
【０００４】
また、画像コンテンツから大量の局所特徴ベクトルを抽出し、それらをベクトル量子化し、同一の代表ベクトルにベクトル量子化された局所特徴ベクトルの数で類似度を算出する技術もある（例えば非特許文献１参照）。
【０００５】
更に、画像から複数の局所不変特徴量を抽出し、特徴ベクトルの頻度のヒストグラム化し、そのヒストグラムの重なり率によって画像とカテゴリとの間の類似度を算出する技術もある（例えば特許文献１参照）。この技術によれば、ヒストグラムに基づいて被写体のパターン認識に不要となる特徴（例えば背景の特徴）を除くことができる。これによって、画像中から物体と物体以外とを予め分離することなく、当該物体の特徴を抽出することができる。
【０００６】
一方で、前述した従来技術によれば、量子化によって、元々の特徴ベクトルの情報が失われる。その量子化の粗さによって、以下のような問題が生じる。
（誤検出）粗く量子化した場合、異なる特徴ベクトルが同じ識別値（ＩＤ(IDentifier)）を持つ代表ベクトルに量子化される可能性が高くなる。これによって、異なるコンテンツを類似していると判定するという誤検出が、増加する。
（未検出）逆に、細かく量子化した場合、類似した特徴ベクトルが異なるＩＤを持つ代表ベクトルに量子化される可能性が高くなる。これによって、類似したコンテンツが類似していると判定されないという未検出が、増加する。
【０００７】
このような問題を解決するべく、誤検出及び未検出の２種類のエラーのトレードオフを改善する技術がある（例えば非特許文献２及び３）。この技術によれば、予め特徴ベクトルを、コンパクトなコードに符号化する。そして、ベクトル量子化で同じＩＤとなった特徴ベクトル間の距離を、符号間の距離で近似する。その距離が所定閾値以下となる特徴ベクトル同士のみが、類似度に貢献するものとする。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−２８２５８１号公報
【特許文献２】特開２００９−０２０７６９号公報
【非特許文献】
【０００９】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、前述した非特許文献２及び３に記載された技術によれば、全ての量子化ＩＤについて、同一の所定閾値によって類似度に貢献するか否かを判定しているために、量子化ＩＤ毎の特徴ベクトルの密度については全く考慮されていない。このため、ある量子化ＩＤでは、過剰に特徴ベクトルが類似度に貢献し、一方で、別の量子化ＩＤでは、類似度に貢献する特徴ベクトルが少なくなるといった問題が生じる。
【００１１】
そこで、本発明によれば、高次元の特徴ベクトルを検索する際に、量子化ＩＤ毎の特徴ベクトルの密度を考慮することによって、量子化ＩＤ同士の間の類似度の決定における不公平性を緩和することができる検索装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明によれば、特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索する検索装置であって、
リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、
クエリコンテンツについて、クエリ特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、
リファレンス情報蓄積手段を用いて、クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、
クエリハッシュ識別値に対応する全てのリファレンスコンテンツ識別値を、距離が短い昇順にソートする距離ソート手段と、
ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合（％）に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、
抽出されたリファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段と
を有することを特徴とする。
【００１３】
本発明の検索装置における他の実施形態によれば、
リファレンス情報蓄積手段は、リファレンス特徴ベクトルに代えて、当該リファレンス特徴ベクトルに対するリファレンス符号を蓄積しており、
ハッシュ化手段は、多数のリファレンス特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のリファレンスハッシュ識別値を更に導出し、
リファレンス特徴ベクトルを、リファレンス符号に符号化し、リファレンス情報蓄積手段へ蓄積する符号化手段を更に有し、
距離算出手段は、リファレンス情報蓄積手段を用いて、クエリハッシュ識別値に対応する各リファレンス符号と、クエリ特徴ベクトルとの間の距離を算出することも好ましい。
【００１４】
本発明の検索装置における他の実施形態によれば、類似検索手段は、クエリコンテンツに含まれる複数のクエリ特徴ベクトル毎に導出された複数のリファレンスコンテンツ識別値を、当該リファレンスコンテンツ識別値毎に投票し、その投票数に応じたリファレンスコンテンツ識別値を抽出することも好ましい。
【００１５】
本発明の検索装置における他の実施形態によれば、
リファレンス情報蓄積手段は、リファレンスコンテンツ毎に、リファレンスハッシュ識別値の頻度のＬｐノルムを蓄積し、
類似検索手段は、リファレンスコンテンツ毎の得票数を、対応するリファレンスコンテンツのＬｐノルムで正規化した値を、類似度として算出することも好ましい。
【００１６】
本発明の検索装置における他の実施形態によれば、
符号化手段は、リファレンス特徴ベクトル及びクエリ特徴ベクトルに対して射影変換を行い、変換後の各次元の値を閾値で二値化することによって、バイナリ列のリファレンス符号及びクエリ符号を生成し、
距離算出手段は、リファレンス符号及びクエリ符号のハミング距離を算出することも好ましい。
【００１７】
本発明の検索装置における他の実施形態によれば、
符号化手段は、
ハッシュ識別値に対応する代表ベクトルを蓄積しており、
リファレンス特徴ベクトルと、当該リファレンス特徴ベクトルのリファレンスハッシュ識別値に対応する代表ベクトルとの間のリファレンス差分ベクトルを算出し、そのリファレンス差分ベクトルをリファレンス符号に符号化することも好ましい。
【００１８】
本発明の検索装置における他の実施形態によれば、代表ベクトルは、当該ハッシュ識別値を持つ多数の特徴ベクトルの平均ベクトル又は中央値ベクトルから算出されることも好ましい。
【００１９】
本発明の検索装置における他の実施形態によれば、
符号化手段は、
直積量子化のためのコードブックを更に有し、
リファレンス差分ベクトルを、コードブックを用いて直積量子化によってリファレンス符号に符号化し、
クエリ特徴ベクトルと、クエリハッシュ識別値に対応する代表ベクトルとの間のクエリ差分ベクトルを算出するものであり、
距離算出手段は、リファレンス符号とクエリ差分ベクトルとのＬｐ距離を算出することも好ましい。
【００２０】
本発明の検索装置における他の実施形態によれば、ハッシュ化手段は、ベクトル量子化用のコードブックを更に有し、ハッシュ関数はベクトル量子化を行うことでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出することも好ましい。
【００２１】
本発明の検索装置における他の実施形態によれば、ハッシュ化手段は、リファレンス特徴ベクトル及びクエリ特徴ベクトルと、同次元の既定のベクトルとの内積の値を、所定閾値で離散化することでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出することも好ましい。
【００２２】
本発明の検索装置における他の実施形態によれば、ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであることも好ましい。
【００２３】
本発明によれば、特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索するように、コンピュータを機能させるプログラムであって、
リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、
クエリコンテンツについて、クエリ特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、
リファレンス情報蓄積手段を用いて、クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、
クエリハッシュ識別値に対応する全てのリファレンスコンテンツ識別値を、距離が短い昇順にソートする距離ソート手段と、
ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合（％）に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、
抽出されたリファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段と
してコンピュータを機能させることを特徴とする。
【発明の効果】
【００２４】
本発明の検索装置及びプログラムによれば、高次元の特徴ベクトルを検索する際に、量子化ＩＤ毎の特徴ベクトルの密度を考慮することによって、量子化ＩＤ同士の間の類似度の決定における不公平性を緩和することができる。
【図面の簡単な説明】
【００２５】
【図１】リファレンス特徴ベクトルの集合に対するクラスタリングを表す説明図である。
【図２】本発明における検索装置の第１の機能構成図である。
【図３】本発明におけるデータ構造を表す第１の説明図である。
【図４】ハッシュ化部の機能構成を表す説明図である。
【図５】リファレンスコンテンツＩＤの投票を表すグラフである。
【図６】本発明における検索装置の第２の機能構成図である。
【図７】本発明におけるデータ構造を表す第２の説明図である。
【図８】本発明における符号化部の機能構成図である。
【発明を実施するための形態】
【００２６】
以下では、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２７】
本発明の検索装置及びプログラムによれば、多数のリファレンスコンテンツ（検索対象のコンテンツ）の中から、クエリコンテンツ（検索キーのコンテンツ）に最も類似するリファレンスコンテンツを検索する。検索のために、マルチメディアコンテンツから、特徴ベクトルの集合を抽出する。即ち、特徴ベクトルの集合の１つが、１つのマルチメディアコンテンツに対応する。具体的には、リファレンスコンテンツは、複数のリファレンス特徴ベクトルの集合からなり、同様に、クエリコンテンツも、複数のクエリ特徴ベクトルの集合からなる。リファレンス特徴ベクトル及びクエリ特徴ベクトルは、同じ次元数のベクトルである。
【００２８】
尚、マルチメディアコンテンツが画像である場合、その特徴ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルである。
【００２９】
図１は、リファレンス特徴ベクトルの集合に対するクラスタリングを表す説明図である。
【００３０】
図１（ａ）によれば、多数のリファレンス特徴ベクトルが、例えばＮ個のクラスタＦn（ｎ＝１〜Ｎ）にクラスタリングされている。クラスタリングには、例えばk-means又はk-means++のようなアルゴリズムが用いられる。各クラスタ内には、多数のリファレンス特徴ベクトルが含まれている。クラスタ内にクエリ特徴ベクトルが含まれる場合、そのクエリ特徴ベクトルから所定閾値の距離範囲に属するリファレンス特徴ベクトルが、候補として導出される。図１によれば、以下のように表される。
×    ：リファレンス特徴ベクトル
＋    ：クラスタにおける代表ベクトル（平均ベクトル又は中央値ベクトル）
黒丸●：クエリ特徴ベクトル
波線○：クエリ特徴ベクトルから所定閾値の距離範囲
【００３１】
例えば、クラスタＦ１にクエリ特徴ベクトルａが含まれ、クラスタＦ３にクエリ特徴ベクトルｂが含まれるとする。従来技術によれば、クエリ特徴ベクトルから、所定閾値の距離範囲に属するリファレンス特徴ベクトルの数によって類似度を算出している。
【００３２】
しかしながら、クラスタのセル範囲によっては、以下のように分かれる。
・クラスタのセル範囲が小さい場合、特徴ベクトルの分布密度が高い。この場合、クエリ特徴ベクトルから、所定閾値範囲に属するリファレンス特徴ベクトルの数も多く、類似度が高いと判定される。
・クラスタのセル範囲が大きい場合、特徴ベクトルの分布密度が低い。この場合、クエリ特徴ベクトルから、所定閾値範囲に属するリファレンス特徴ベクトルの数も少なく、類似度も低いと判定される。
【００３３】
これに対し、図１（ｂ）に基づく本発明によれば、クラスタ内のリファレンス特徴ベクトルの中で、上位閾値割合Ｐ（％）に含まれるリファレンス特徴ベクトルのみを抽出する。抽出されたリファレンス特徴ベクトルについてのみ、クエリ特徴ベクトルから所定閾値範囲に属する数が多いほど、類似度が高いと判定される。即ち、本発明によれば、クラスタのセル範囲（リファレンス特徴ベクトルの分布）に応じて、判定対象となるリファレンス特徴ベクトルが異なる。
【００３４】
以下では、クエリコンテンツ及びリファレンスコンテンツについて、類似検索のための比較対象が異なる２通りの実施形態について説明する。
［第１の実施形態］クエリコンテンツのクエリ特徴ベクトルと、リファレンスコンテンツのリファレンス特徴ベクトルとを比較して、類似度を判定する。
［第２の実施形態］クエリコンテンツのクエリ特徴ベクトルにおけるクエリ符号（又はクエリ差分ベクトル）と、リファレンスコンテンツのリファレンス特徴ベクトルにおけるリファレンス符号とを比較して、類似度を判定する。
【００３５】
［第１の実施形態］
図２は、本発明における検索装置の第１の機能構成図である。
図３は、本発明におけるデータ構造を表す第１の説明図である。
【００３６】
図２によれば、検索装置１は、リファレンス情報蓄積部１００と、特徴ベクトル集合抽出部１１１と、ハッシュ化部１１２と、距離算出部１１３と、距離ソート部１１４と、リファレンスコンテンツＩＤ抽出部１１５と、類似検索部１１６とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００３７】
検索装置１は、多数のリファレンスコンテンツを予め入力し、リファレンス情報蓄積部１００に、リファレンスコンテンツに関する情報を記憶する。また、検索装置１は、検索の際に、検索キーとなるクエリコンテンツを入力し、リファレンス情報蓄積部１００を用いて、クエリコンテンツに最も類似するリファレンスコンテンツを検索する。
【００３８】
特徴ベクトル集合抽出部１１１は、マルチメディアコンテンツから、特徴ベクトルの集合を抽出する。ここでは、リファレンスコンテンツから、複数のリファレンス特徴ベクトルの集合が抽出され、同様に、クエリコンテンツから、複数のクエリ特徴ベクトルの集合が抽出される（図３の１１１参照）。例えば、ＳＩＦＴ(Scale-Invariant Feature Transform)アルゴリズムによれば、１枚の画像からは、１２８次元（Ｄ＝１２８）の特徴ベクトルの集合が抽出される（例えば非特許文献４参照）。ＳＩＦＴとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる特徴ベクトルを記述する技術である。
特徴ベクトルｆ：  ｆ＝（ｆ１，ｆ２，・・・，ｆＤ）
抽出されたリファレンス特徴ベクトルは、ハッシュ化部１１２及びリファレンス情報蓄積部１００へ出力される。また、抽出されたクエリ特徴ベクトルは、ハッシュ化部１１２及び距離算出部１１３へ出力される。
【００３９】
ハッシュ化部１１２は、リファレンスコンテンツについて、リファレンス特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のリファレンスハッシュＩＤ（識別値）を導出する。同様に、クエリコンテンツについても、クエリ特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のクエリハッシュＩＤを導出する（図３の１１２参照）。
【００４０】
図４は、ハッシュ化部の機能構成を表す説明図である。
【００４１】
ハッシュ化部１１２は、以下の２つの処理のいずれか一方を用いる。尚、リファレンス特徴ベクトル及びクエリ特徴ベクトルには、同じハッシュ化処理が実行される。
【００４２】
（第１のハッシュ処理）ハッシュ化部１１２は、ベクトル量子化用のコードブックを有し、特徴ベクトルに対してベクトル量子化を実行する。これによって、リファレンスハッシュＩＤ及びクエリハッシュＩＤを算出する。
【００４３】
ここで、コードブックとは、特徴ベクトルｆを量子化するために、ハッシュＩＤｎ（＝１〜Ｎ）と、代表ベクトルｆｎとを対応付けたものである。
ハッシュＩＤｎ：  代表ベクトルｆｎ
１：  ｆ１＝（ｆ１１，ｆ１２，・・・，ｆ１Ｄ）
２：  ｆ２＝（ｆ２１，ｆ２２，・・・，ｆ２Ｄ）
３：  ｆ３＝（ｆ３１，ｆ３２，・・・，ｆ３Ｄ）
・・・
Ｎ：  ｆＮ＝（ｆＮ１，ｆＮ２，・・・，ｆＮＤ）
【００４４】
コードブックは、以下のステップを実行することによって生成される（例えば図１参照）。
（Ｓ１）リファレンス特徴ベクトルの集合を、Ｎ個のクラスタにクラスタリングする。
（Ｓ２）次に、クラスタ毎に、代表ベクトルを導出する（平均ベクトル又は中央値ベクトル）。
（Ｓ３）各代表ベクトルに、一意のハッシュＩＤｎ（＝１〜Ｎ）を割り当てたコードブックを生成する。
【００４５】
第１のハッシュ処理によれば、入力された特徴ベクトルｆとの距離が最も小さくなる代表ベクトルｆｎ'を算出し、特徴ベクトルｆに、識別値ＩＤn'を割り当てる。
ｎ＝ｑ（ｆ）＝ａｒｇｍｉｎｎ||ｆ−ｆｎ||２
（登録ベクトルｆの量子化関数ｑ（ｆ）は、||ｆ−ｆｎ||２が最小となるｎを導出）
ｑ：ＲＤ->Ｎ（量子化を意味する）
ｆｎ：代表ベクトル
【００４６】
このとき、特徴ベクトルに対して、最も距離が小さくなる１つのＩＤn'を割り当てるのではなく、距離が小さくなる代表ベクトルにおける上位いくつかの複数のＩＤを割り当ててもよい。また、異なるコードブックを複数保持しておき、それぞれのコードブックで個別にＩＤを割り当ててもよい。これらの処理によって、Ｄ次元の特徴ベクトルの集合ｆ1〜ｆKそれぞれに、１つ以上のハッシュＩＤが割り当てられる。
【００４７】
（第２のハッシュ処理）ハッシュ化部１１２は、リファレンス特徴ベクトル及びクエリ特徴ベクトルと、同次元の既定のベクトルとの内積の値を、所定閾値で離散化することによって、リファレンスハッシュＩＤ及びクエリハッシュＩＤを算出する。
【００４８】
尚、ハッシュ化部１１２では、近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの１つであるＬＳＨ(Locality-Sensitive Hashing)で用いられるハッシュ関数を用いることもできる。ＬＳＨによれば、類似するデータ同士のハッシュＩＤは一致し、非類似のデータ同士のハッシュＩＤは異なる可能性が高くなるように、ハッシュＩＤを出力する。
【００４９】
リファレンス特徴ベクトルをハッシュ化したリファレンスハッシュＩＤは、リファレンス情報蓄積部１００へ出力される。また、クエリ特徴ベクトルをハッシュ化したクエリハッシュＩＤは、距離算出部１１３へ出力される。
【００５０】
リファレンス情報蓄積部１００は、リファレンスハッシュＩＤ毎に、リファレンスコンテンツＩＤと、リファレンス特徴ベクトルとの組み合わせを、複数蓄積する（図３の１００参照）。即ち、リファレンスハッシュＩＤ毎に、リファレンスコンテンツＩＤ及びリファレンス特徴ベクトルがリスト化される。
【００５１】
再び図２へ戻って、距離算出部１１３は、リファレンス情報蓄積部１００がリファレンス特徴ベクトルを蓄積している場合、クエリ特徴ベクトルにおけるクエリハッシュＩＤikに対応するリファレンス特徴ベクトルのリストを参照する。そして、各リファレンス特徴ベクトルと、クエリ特徴ベクトルとの間の距離を算出する（図３の１１３参照）。算出された距離の情報は、距離ソート部１１４へ出力される。
【００５２】
距離ソート部１１４は、クエリハッシュＩＤに対応する全てのリファレンスコンテンツＩＤを、距離が短い昇順にソートする。リファレンスコンテンツＩＤ及び距離のペア毎に、ソートされる。
【００５３】
リファレンスコンテンツＩＤ抽出部１１５は、ソートされたリファレンスコンテンツＩＤ全体の中で、上位閾値割合Ｐ（％）に含まれるリファレンスコンテンツＩＤ群のみを抽出する（図３の１１４参照）。
【００５４】
類似検索部１１６は、クエリコンテンツ（クエリ特徴ベクトルの集合）とリファレンスコンテンツ（リファレンス特徴ベクトルの集合）との間の類似度を判定する。リファレンスコンテンツＩＤ抽出部１１５によって抽出されたリファレンスコンテンツＩＤに対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する。
【００５５】
ここで、類似検索部１１６は、クエリコンテンツに含まれる複数のクエリ特徴ベクトル毎に導出された複数のリファレンスコンテンツＩＤを、当該リファレンスコンテンツＩＤ毎に投票し、その投票数に応じたリファレンスコンテンツＩＤを抽出する。
【００５６】
図５は、リファレンスコンテンツＩＤの投票を表すグラフである。
【００５７】
最初に、リファレンスコンテンツＩＤ抽出部１１５によって抽出されたリファレンスコンテンツＩＤ群について、クエリ特徴ベクトルのクエリハッシュＩＤ毎に、各リファレンスコンテンツＩＤの個数をカウントする（図５（ａ）参照）。例えば、１つのクエリコンテンツについて、クリエ特徴ベクトル毎にクエリハッシュＩＤ１〜３が導出されたとする。そのクエリハッシュＩＤ毎に、リファレンスコンテンツＩＤが抽出される。
クリエハッシュＩＤ              リファレンスコンテンツＩＤ
１                  ->    ５，６
２                  ->    １，４，５
３                  ->    １，５
ここで、リファレンスコンテンツＩＤの出現頻度は、以下のように表される。
リファレンスコンテンツＩＤ      出現頻度
１                  ->    ２
２                  ->    ０
３                  ->    ０
４                  ->    １
５                  ->    ３（投票数の局所最大）
６                  ->    １
【００５８】
次に、リファレンスコンテンツＩＤ毎の総個数を、正規化項で正規化する。ここで、正規化項は、以下のように算出される。
【００５９】
リファレンス情報蓄積部１００は、ハッシュＩＤがＩＤ１〜４をとる場合、リファレンスコンテンツ毎に、各ハッシュＩＤの出現頻度を蓄積する（図５（ｂ）参照）。例えば、リファレンスコンテンツＩＤ１における、リファレンスハッシュＩＤの出現頻度は、以下のようになる。
［リファレンスコンテンツＩＤ１の場合］
リファレンスハッシュＩＤ        出現頻度
１                  ->    １
２                  ->    ３
３                  ->    ０
４                  ->    １
【００６０】
そして、リファレンスハッシュＩＤ毎の出現頻度に応じて、以下のように２種類の正規化項を算出する。以下では、リファレンスハッシュＩＤ１についてのみ記述する。
リファレンスハッシュＩＤ１のＬ１ノルム
１＋３＋０＋１＝５
リファレンスハッシュＩＤ１のＬ２ノルムの場合
√(１2＋３2＋０2＋１2)＝√(１＋９＋０＋１)＝√１１
【００６１】
最終的に、クエリコンテンツに対するリファレンスコンテンツの類似度は、以下のように表される（図５（ｃ）参照）。
リファレンスコンテンツＩＤ      Ｌ１ノルム類似度  Ｌ２ノルム類似度
１                  ->    ２／５              ２／√１１
２                  ->    ０／９              ０／√９
３                  ->    ０／１１            ０／√１１
４                  ->    １／８              １／√８
５                  ->    ３／９              ３／√９
６                  ->    １／８              １／√８
【００６２】
このように、類似検索部１１６は、リファレンスコンテンツ毎の得票数を、対応するリファレンスコンテンツのＬｐノルムで正規化した値を、類似度として算出する。そして、類似度が最も高いリファレンスコンテンツＩＤを、検索結果として出力する。
【００６３】
［第２の実施形態］
図６は、本発明における検索装置の第２の機能構成図である。
図７は、本発明におけるデータ構造を表す第２の説明図である。
【００６４】
前述した第１の実施形態によれば、リファレンス情報蓄積部１００は、リファレンスハッシュＩＤ毎に、リファレンスコンテンツＩＤと、リファレンス特徴ベクトルとの組み合わせを、複数蓄積する。これに対し、第２の実施形態によれば、リファレンス情報蓄積部１００は、リファレンスハッシュＩＤ毎に、リファレンスコンテンツＩＤと、当該リファレンス特徴ベクトルに対するリファレンス符号との組み合わせを、複数蓄積する。第２の蓄積情報は、第１の蓄積情報のリファレンス特徴ベクトルに代えて、リファレンス符号を蓄積する。
【００６５】
図６によれば、図２と比較して、リファレンス特徴ベクトル及びクエリ特徴ベクトルを、リファレンス符号及びクエリ符号（若しくはクエリ差分ベクトル）に符号化する符号化部１１７を更に有する。
【００６６】
図７によれば、リファレンス情報蓄積部１００は、リファレンスコンテンツＩＤ毎に、リファレンス符号を記憶する（図７の１００参照）。また、距離算出部１１３は、リファレンス符号と、クエリ符号（又はクエリ差分ベクトル）との間の距離を算出する（図７の１１３参照）。それらの点以外は、前述した図３と全く同様である。
【００６７】
図８は、本発明における符号化部の機能構成図である。
【００６８】
符号化部１１７は、大きく２通りの符号化処理の中で、いずれか一方の処理が実行される。尚、リファレンス特徴ベクトル及びクエリ特徴ベクトルには、同じ符号化処理が実行される。
【００６９】
（第１の符号化処理）
符号化部１１７は、特徴ベクトル集合抽出部１１１から出力されたリファレンス特徴ベクトル及びクエリ特徴ベクトルを入力する。次に、各特徴ベクトルｆkについて、割り当てられたハッシュＩＤikに対応する代表ベクトルｇikからの差分ベクトルｒkを算出する（ｒk＝ｆk−ｇik）。そして、差分ベクトルｒkに対してランダムな直交射影(Random Orthogonal Projection)によって射影変換を実行する。次に、変換後の各次元の値を、閾値で二値化することによって、バイナリ列のリファレンス符号及びクエリ符号を生成する。尚、直積量子化の場合には、差分ベクトルｒkを複数の部分ベクトルに分割し、それぞれを個別のコードブックで量子化し、量子化ＩＤの列を符号ｃkとする。リファレンス符号は、リファレンス情報蓄積部１００へ出力され、クエリ符号は、距離算出部１１３へ出力される。
【００７０】
このような符号化処理に対して、距離算出部１１３は、リファレンス符号及びクエリ符号のハミング距離(Hamming Embedding)を算出する（例えば非特許文献２参照）。
【００７１】
（第２の符号化処理）
符号化部１１７は、ハッシュＩＤに対応する代表ベクトルを蓄積する。代表ベクトルとは、当該ハッシュＩＤを持つ多数の特徴ベクトルの平均ベクトル又は中央値ベクトルから算出されるものであってもよい。そして、符号化部１１７は、リファレンス特徴ベクトルと、当該リファレンス特徴ベクトルのリファレンスハッシュＩＤに対応する代表ベクトルとの間のリファレンス差分ベクトルを算出し、そのリファレンス差分ベクトルをリファレンス符号に符号化する。
【００７２】
符号化部１１７は、直積量子化のためのコードブックを更に有する。そして、リファレンス差分ベクトルを、コードブックを用いて直積量子化によってリファレンス符号に符号化する（例えば非特許文献３参照）。また、符号化部１１７は、クエリ特徴ベクトルと、クエリハッシュＩＤに対応する代表ベクトルとの間のクエリ差分ベクトルを算出する。リファレンス符号は、リファレンス情報蓄積部１００へ出力され、クエリ差分ベクトルは、距離算出部１１３へ出力される。
【００７３】
このような符号化処理に対して、距離算出部１１３は、リファレンス符号とクエリ差分ベクトルとのＬｐ距離を算出する（例えば非特許文献４及び５参照）。
【００７４】
第１の符号化処理及び第２の符号化処理の両方とも、予め大量のリファレンス特徴ベクトルから、ハッシュ化部１１２によって各ハッシュＩＤが割り当てられるリファレンス特徴ベクトルの平均ベクトルを算出しておく。
【００７５】
本発明の検索装置及びプログラムによれば、高次元の特徴ベクトルを検索する際に、量子化ＩＤ毎の特徴ベクトルの密度を考慮することによって、量子化ＩＤ同士の間の類似度の決定における不公平性を緩和することができる。
【００７６】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００７７】
１  検索装置
１００  リファレンス情報蓄積部
１１１  特徴ベクトル集合抽出部
１１２  ハッシュ化部
１１３  距離算出部
１１４  距離ソート部
１１５  リファレンスコンテンツＩＤ抽出部
１１６  類似検索部
１１７  符号化部
【図１】
0005598925.tif 000002
【図２】
0005598925.tif 000003
【図３】
0005598925.tif 000004
【図４】
0005598925.tif 000005
【図５】
0005598925.tif 000006
【図６】
0005598925.tif 000007
【図７】
0005598925.tif 000008
【図８】
0005598925.tif 000009