JP5598925B2

JP5598925B2 - 高次元の特徴ベクトルを高精度で検索する検索装置及びプログラム

Info

Publication number: JP5598925B2
Application number: JP2011144832A
Authority: JP
Inventors: 祐介内田; 茂之酒澤
Original assignee: KDDI Corp
Current assignee: KDDI Corp
Priority date: 2011-06-29
Filing date: 2011-06-29
Publication date: 2014-10-01
Anticipated expiration: 2031-06-29
Also published as: JP2013012076A

Description

本発明は、特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、同じく特徴ベクトルの集合で表されるクエリコンテンツ（検索キー）に類似したリファレンスコンテンツを高精度に検索する技術に関する。特に、高次元の特徴ベクトルの集合で表されるマルチメディアコンテンツ（例えば画像）の検索に適する。

近年、オンライン／オフラインに限られず、ストレージの大容量化に伴って、大量のコンテンツを蓄積することが可能となっている。また、携帯電話機やスマートフォンに代表される情報端末機器の普及によって、ユーザ自ら取得した写真データのようなデジタルコンテンツも、データベースに大量かつ容易に蓄積することができる。オフラインデータベースとして、ＨＤＤ(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'を割り当てるのではなく、距離が小さくなる代表ベクトルにおける上位いくつかの複数のＩＤを割り当ててもよい。また、異なるコードブックを複数保持しておき、それぞれのコードブックで個別にＩＤを割り当ててもよい。これらの処理によって、Ｄ次元の特徴ベクトルの集合ｆ₁〜ｆ_Kそれぞれに、１つ以上のハッシュＩＤが割り当てられる。

（第２のハッシュ処理）ハッシュ化部１１２は、リファレンス特徴ベクトル及びクエリ特徴ベクトルと、同次元の既定のベクトルとの内積の値を、所定閾値で離散化することによって、リファレンスハッシュＩＤ及びクエリハッシュＩＤを算出する。

尚、ハッシュ化部１１２では、近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの１つであるＬＳＨ(Locality-Sensitive Hashing)で用いられるハッシュ関数を用いることもできる。ＬＳＨによれば、類似するデータ同士のハッシュＩＤは一致し、非類似のデータ同士のハッシュＩＤは異なる可能性が高くなるように、ハッシュＩＤを出力する。

リファレンス特徴ベクトルをハッシュ化したリファレンスハッシュＩＤは、リファレンス情報蓄積部１００へ出力される。また、クエリ特徴ベクトルをハッシュ化したクエリハッシュＩＤは、距離算出部１１３へ出力される。

リファレンス情報蓄積部１００は、リファレンスハッシュＩＤ毎に、リファレンスコンテンツＩＤと、リファレンス特徴ベクトルとの組み合わせを、複数蓄積する（図３の１００参照）。即ち、リファレンスハッシュＩＤ毎に、リファレンスコンテンツＩＤ及びリファレンス特徴ベクトルがリスト化される。

再び図２へ戻って、距離算出部１１３は、リファレンス情報蓄積部１００がリファレンス特徴ベクトルを蓄積している場合、クエリ特徴ベクトルにおけるクエリハッシュＩＤikに対応するリファレンス特徴ベクトルのリストを参照する。そして、各リファレンス特徴ベクトルと、クエリ特徴ベクトルとの間の距離を算出する（図３の１１３参照）。算出された距離の情報は、距離ソート部１１４へ出力される。

距離ソート部１１４は、クエリハッシュＩＤに対応する全てのリファレンスコンテンツＩＤを、距離が短い昇順にソートする。リファレンスコンテンツＩＤ及び距離のペア毎に、ソートされる。

リファレンスコンテンツＩＤ抽出部１１５は、ソートされたリファレンスコンテンツＩＤ全体の中で、上位閾値割合Ｐ（％）に含まれるリファレンスコンテンツＩＤ群のみを抽出する（図３の１１４参照）。

類似検索部１１６は、クエリコンテンツ（クエリ特徴ベクトルの集合）とリファレンスコンテンツ（リファレンス特徴ベクトルの集合）との間の類似度を判定する。リファレンスコンテンツＩＤ抽出部１１５によって抽出されたリファレンスコンテンツＩＤに対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する。

ここで、類似検索部１１６は、クエリコンテンツに含まれる複数のクエリ特徴ベクトル毎に導出された複数のリファレンスコンテンツＩＤを、当該リファレンスコンテンツＩＤ毎に投票し、その投票数に応じたリファレンスコンテンツＩＤを抽出する。

図５は、リファレンスコンテンツＩＤの投票を表すグラフである。

最初に、リファレンスコンテンツＩＤ抽出部１１５によって抽出されたリファレンスコンテンツＩＤ群について、クエリ特徴ベクトルのクエリハッシュＩＤ毎に、各リファレンスコンテンツＩＤの個数をカウントする（図５（ａ）参照）。例えば、１つのクエリコンテンツについて、クリエ特徴ベクトル毎にクエリハッシュＩＤ１〜３が導出されたとする。そのクエリハッシュＩＤ毎に、リファレンスコンテンツＩＤが抽出される。
クリエハッシュＩＤリファレンスコンテンツＩＤ
１ -> ５，６
２ -> １，４，５
３ -> １，５
ここで、リファレンスコンテンツＩＤの出現頻度は、以下のように表される。
リファレンスコンテンツＩＤ出現頻度
１ -> ２
２ -> ０
３ -> ０
４ -> １
５ -> ３（投票数の局所最大）
６ -> １

次に、リファレンスコンテンツＩＤ毎の総個数を、正規化項で正規化する。ここで、正規化項は、以下のように算出される。

リファレンス情報蓄積部１００は、ハッシュＩＤがＩＤ１〜４をとる場合、リファレンスコンテンツ毎に、各ハッシュＩＤの出現頻度を蓄積する（図５（ｂ）参照）。例えば、リファレンスコンテンツＩＤ１における、リファレンスハッシュＩＤの出現頻度は、以下のようになる。
［リファレンスコンテンツＩＤ１の場合］
リファレンスハッシュＩＤ出現頻度
１ -> １
２ -> ３
３ -> ０
４ -> １

そして、リファレンスハッシュＩＤ毎の出現頻度に応じて、以下のように２種類の正規化項を算出する。以下では、リファレンスハッシュＩＤ１についてのみ記述する。
リファレンスハッシュＩＤ１のＬ１ノルム
１＋３＋０＋１＝５
リファレンスハッシュＩＤ１のＬ２ノルムの場合
√(１²＋３²＋０²＋１²)＝√(１＋９＋０＋１)＝√１１

最終的に、クエリコンテンツに対するリファレンスコンテンツの類似度は、以下のように表される（図５（ｃ）参照）。
リファレンスコンテンツＩＤＬ１ノルム類似度Ｌ２ノルム類似度
１ -> ２／５２／√１１
２ -> ０／９０／√９
３ -> ０／１１０／√１１
４ -> １／８１／√８
５ -> ３／９３／√９
６ -> １／８１／√８

このように、類似検索部１１６は、リファレンスコンテンツ毎の得票数を、対応するリファレンスコンテンツのＬｐノルムで正規化した値を、類似度として算出する。そして、類似度が最も高いリファレンスコンテンツＩＤを、検索結果として出力する。

［第２の実施形態］
図６は、本発明における検索装置の第２の機能構成図である。
図７は、本発明におけるデータ構造を表す第２の説明図である。

前述した第１の実施形態によれば、リファレンス情報蓄積部１００は、リファレンスハッシュＩＤ毎に、リファレンスコンテンツＩＤと、リファレンス特徴ベクトルとの組み合わせを、複数蓄積する。これに対し、第２の実施形態によれば、リファレンス情報蓄積部１００は、リファレンスハッシュＩＤ毎に、リファレンスコンテンツＩＤと、当該リファレンス特徴ベクトルに対するリファレンス符号との組み合わせを、複数蓄積する。第２の蓄積情報は、第１の蓄積情報のリファレンス特徴ベクトルに代えて、リファレンス符号を蓄積する。

図６によれば、図２と比較して、リファレンス特徴ベクトル及びクエリ特徴ベクトルを、リファレンス符号及びクエリ符号（若しくはクエリ差分ベクトル）に符号化する符号化部１１７を更に有する。

図７によれば、リファレンス情報蓄積部１００は、リファレンスコンテンツＩＤ毎に、リファレンス符号を記憶する（図７の１００参照）。また、距離算出部１１３は、リファレンス符号と、クエリ符号（又はクエリ差分ベクトル）との間の距離を算出する（図７の１１３参照）。それらの点以外は、前述した図３と全く同様である。

図８は、本発明における符号化部の機能構成図である。

符号化部１１７は、大きく２通りの符号化処理の中で、いずれか一方の処理が実行される。尚、リファレンス特徴ベクトル及びクエリ特徴ベクトルには、同じ符号化処理が実行される。

（第１の符号化処理）
符号化部１１７は、特徴ベクトル集合抽出部１１１から出力されたリファレンス特徴ベクトル及びクエリ特徴ベクトルを入力する。次に、各特徴ベクトルｆkについて、割り当てられたハッシュＩＤikに対応する代表ベクトルｇikからの差分ベクトルｒkを算出する（ｒk＝ｆk−ｇik）。そして、差分ベクトルｒkに対してランダムな直交射影(Random Orthogonal Projection)によって射影変換を実行する。次に、変換後の各次元の値を、閾値で二値化することによって、バイナリ列のリファレンス符号及びクエリ符号を生成する。尚、直積量子化の場合には、差分ベクトルｒkを複数の部分ベクトルに分割し、それぞれを個別のコードブックで量子化し、量子化ＩＤの列を符号ｃkとする。リファレンス符号は、リファレンス情報蓄積部１００へ出力され、クエリ符号は、距離算出部１１３へ出力される。

このような符号化処理に対して、距離算出部１１３は、リファレンス符号及びクエリ符号のハミング距離(Hamming Embedding)を算出する（例えば非特許文献２参照）。

（第２の符号化処理）
符号化部１１７は、ハッシュＩＤに対応する代表ベクトルを蓄積する。代表ベクトルとは、当該ハッシュＩＤを持つ多数の特徴ベクトルの平均ベクトル又は中央値ベクトルから算出されるものであってもよい。そして、符号化部１１７は、リファレンス特徴ベクトルと、当該リファレンス特徴ベクトルのリファレンスハッシュＩＤに対応する代表ベクトルとの間のリファレンス差分ベクトルを算出し、そのリファレンス差分ベクトルをリファレンス符号に符号化する。

符号化部１１７は、直積量子化のためのコードブックを更に有する。そして、リファレンス差分ベクトルを、コードブックを用いて直積量子化によってリファレンス符号に符号化する（例えば非特許文献３参照）。また、符号化部１１７は、クエリ特徴ベクトルと、クエリハッシュＩＤに対応する代表ベクトルとの間のクエリ差分ベクトルを算出する。リファレンス符号は、リファレンス情報蓄積部１００へ出力され、クエリ差分ベクトルは、距離算出部１１３へ出力される。

このような符号化処理に対して、距離算出部１１３は、リファレンス符号とクエリ差分ベクトルとのＬｐ距離を算出する（例えば非特許文献４及び５参照）。

第１の符号化処理及び第２の符号化処理の両方とも、予め大量のリファレンス特徴ベクトルから、ハッシュ化部１１２によって各ハッシュＩＤが割り当てられるリファレンス特徴ベクトルの平均ベクトルを算出しておく。

前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。

１検索装置
１００リファレンス情報蓄積部
１１１特徴ベクトル集合抽出部
１１２ハッシュ化部
１１３距離算出部
１１４距離ソート部
１１５リファレンスコンテンツＩＤ抽出部
１１６類似検索部
１１７符号化部

Claims

特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索する検索装置であって、
リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、
前記クエリコンテンツについて、クエリ特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、
前記リファレンス情報蓄積手段を用いて、前記クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、前記クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、
前記クエリハッシュ識別値に対応する全ての前記リファレンスコンテンツ識別値を、前記距離が短い昇順にソートする距離ソート手段と、
ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合（％）に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、
抽出された前記リファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段と
を有することを特徴とする検索装置。
前記リファレンス情報蓄積手段は、前記リファレンス特徴ベクトルに代えて、当該リファレンス特徴ベクトルに対するリファレンス符号を蓄積しており、
前記ハッシュ化手段は、多数の前記リファレンス特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のリファレンスハッシュ識別値を更に導出し、
前記リファレンス特徴ベクトルを、リファレンス符号に符号化し、前記リファレンス情報蓄積手段へ蓄積する符号化手段を更に有し、
前記距離算出手段は、前記リファレンス情報蓄積手段を用いて、前記クエリハッシュ識別値に対応する各リファレンス符号と、前記クエリ特徴ベクトルとの間の距離を算出する
ことを特徴とする請求項１に記載の検索装置。
前記類似検索手段は、前記クエリコンテンツに含まれる複数のクエリ特徴ベクトル毎に導出された複数のリファレンスコンテンツ識別値を、当該リファレンスコンテンツ識別値毎に投票し、その投票数に応じたリファレンスコンテンツ識別値を抽出することを特徴とする請求項１又は２に記載の検索装置。
前記リファレンス情報蓄積手段は、前記リファレンスコンテンツ毎に、前記リファレンスハッシュ識別値の頻度のＬｐノルムを蓄積し、
前記類似検索手段は、前記リファレンスコンテンツ毎の得票数を、対応するリファレンスコンテンツのＬｐノルムで正規化した値を、類似度として算出することを特徴とする請求項３に記載の検索装置。
前記符号化手段は、前記リファレンス特徴ベクトル及び前記クエリ特徴ベクトルに対して射影変換を行い、変換後の各次元の値を閾値で二値化することによって、バイナリ列のリファレンス符号及びクエリ符号を生成し、
前記距離算出手段は、前記リファレンス符号及びクエリ符号のハミング距離を算出する
ことを特徴とする請求項４に記載の検索装置。
前記符号化手段は、
前記ハッシュ識別値に対応する代表ベクトルを蓄積しており、
前記リファレンス特徴ベクトルと、当該リファレンス特徴ベクトルのリファレンスハッシュ識別値に対応する代表ベクトルとの間のリファレンス差分ベクトルを算出し、そのリファレンス差分ベクトルをリファレンス符号に符号化する
ことを特徴とする請求項４に記載の検索装置。
前記代表ベクトルは、当該ハッシュ識別値を持つ多数の特徴ベクトルの平均ベクトル又は中央値ベクトルから算出されることを特徴とする請求項６に記載の検索装置。
前記符号化手段は、
直積量子化のためのコードブックを更に有し、
前記リファレンス差分ベクトルを、前記コードブックを用いて直積量子化によってリファレンス符号に符号化し、
前記クエリ特徴ベクトルと、前記クエリハッシュ識別値に対応する代表ベクトルとの間のクエリ差分ベクトルを算出するものであり、
前記距離算出手段は、前記リファレンス符号とクエリ差分ベクトルとのＬｐ距離を算出する
ことを特徴とする請求項７に記載の検索装置。
前記ハッシュ化手段は、ベクトル量子化用のコードブックを更に有し、前記ハッシュ関数はベクトル量子化を行うことでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出する
ことを特徴とする請求項５又は８に記載の検索装置。
前記ハッシュ化手段は、前記リファレンス特徴ベクトル及びクエリ特徴ベクトルと、同次元の既定のベクトルとの内積の値を、所定閾値で離散化することでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出する
ことを特徴とする請求項５又は８に記載の検索装置。
前記ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであることを特徴とする請求項９又は１０に記載の検索装置。
特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索するように、コンピュータを機能させるプログラムであって、
リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、
前記クエリコンテンツについて、クエリ特徴ベクトル毎に、１つ以上のハッシュ関数を用いて、１つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、
前記リファレンス情報蓄積手段を用いて、前記クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、前記クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、
前記クエリハッシュ識別値に対応する全ての前記リファレンスコンテンツ識別値を、前記距離が短い昇順にソートする距離ソート手段と、
ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合（％）に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、
抽出された前記リファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段と
してコンピュータを機能させることを特徴とする検索プログラム。