(57)【要約】【課題】高次元な特徴量で表現されたコンテンツが大量に蓄積されたコンテンツデータベースを検索する際に用いるハッシュ関数とハッシュ値を、高速かつ省メモリで生成する。【解決手段】デジタルデータに対応して定まるＤ（Ｄ＞０）次元実数値ベクトルをバイナリ値に変換するハッシュ関数生成方法であって、１以上Ｄ以下の自然数の集合の中から、予め定めた自然数Ｃ（０＜Ｃ≦Ｄ）の数だけ重複なく自然数の組を選択するステップと、自然数Ｃと同数の次元を持つパラメータベクトルを生成するステップと、選択された自然数Ｃの組とパラメータベクトルの組によってハッシュ関数を生成するステップとを有する。ハッシュ値生成方法は、デジタルデータに対応するＤ（Ｄ＞０）次元実数値ベクトルを算出するステップと、ハッシュ関数生成方法により生成された１つ以上のハッシュ関数を用いて、前記デジタルデータを１つ以上のバイナリ値に変換するステップとを有する。【選択図】図１
2015079333.tif 000002
【特許請求の範囲】
【請求項１】
デジタルデータに対応して定まるＤ（Ｄ＞０）次元実数値ベクトルをバイナリ値に変換するハッシュ関数生成方法であって、
１以上Ｄ以下の自然数の集合の中から、予め定めた自然数Ｃ（０＜Ｃ≦Ｄ）の数だけ重複なく自然数の組を選択する選択ステップと、
前記自然数Ｃと同数の次元を持つパラメータベクトルを生成するベクトル生成ステップと、
前記選択された自然数Ｃの組と前記パラメータベクトルの組によってハッシュ関数を生成する関数生成ステップと
を有すること特徴とするハッシュ関数生成方法。
【請求項２】
前記選択ステップでは、前記自然数の選択をランダムに行うことを特徴とする請求項１に記載のハッシュ関数生成方法。
【請求項３】
前記ベクトル生成ステップでは、前記パラメータベクトルを指数型分布族に属する確率分布に従う乱数によって生成することを特徴とする請求項１または２に記載のハッシュ関数生成方法。
【請求項４】
デジタルデータに対応するＤ（Ｄ＞０）次元実数値ベクトルを算出するベクトル算出ステップと、
請求項１から３のいずれか１項に記載のハッシュ関数生成方法により生成された１つ以上のハッシュ関数を用いて、前記デジタルデータを１つ以上のバイナリ値に変換する変換ステップと
を有することを特徴とするハッシュ値生成方法。
【請求項５】
デジタルデータに対応して定まるＤ（Ｄ＞０）次元実数値ベクトルをバイナリ値に変換するハッシュ関数生成装置であって、
１以上Ｄ以下の自然数の集合の中から、予め定めた自然数Ｃ（０＜Ｃ≦Ｄ）の数だけ重複なく自然数の組を選択する選択手段と、
前記自然数Ｃと同数の次元を持つパラメータベクトルを生成するベクトル生成手段と、
前記選択された自然数Ｃの組と前記パラメータベクトルの組によってハッシュ関数をハッシュ関数を生成する関数生成手段と
を備えることを特徴とするハッシュ関数生成装置。
【請求項６】
デジタルデータに対応するＤ（Ｄ＞０）次元実数値ベクトルを算出するベクトル算出手段と、
請求項５に記載のハッシュ関数生成装置により生成された１つ以上のハッシュ関数を用いて、前記デジタルデータを１つ以上のバイナリ値に変換する変換手段と
を備えることを特徴とするハッシュ値生成装置。
【請求項７】
コンピュータに、請求項１から３のいずれか１項に記載のハッシュ関数生成方法を実行させるためのハッシュ関数生成プログラム。
【請求項８】
コンピュータに、請求項４に記載のハッシュ値生成方法を実行させるためのハッシュ値生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高次元な特徴量で表現されたコンテンツが大量に蓄積されたコンテンツデータベースに対して、高速かつ省メモリな検索を可能にするハッシュ関数生成方法、ハッシュ値生成方法、ハッシュ関数生成装置、ハッシュ値生成装置、ハッシュ関数生成プログラム及びハッシュ値生成プログラムに関する。
【背景技術】
【０００２】
通信環境やコンピュータ、分散処理基盤技術の高度・高品質化により、ネットワークに流通するコンテンツ（画像・映像・音声・文書等）の数は膨大なものとなっている。例えば、ある検索エンジンがインデクシングしているウェブページの数は数兆にのぼるといわれている。また、あるサイトでは、日々３．５億の画像がアップロードされていると報告されており、また、あるサイトでは、１分当たり６４時間分の映像が新規に公開されているとの報告もある。
【０００３】
このような膨大な量のコンテンツは、利用者にとっては豊富な情報源となる一方で、閲覧したいコンテンツに素早くアクセスすることがますます困難になっているという課題ももたらしている。このような流れの中、閲覧・視聴したいコンテンツを効率的に探し出すためのメディア解析技術への要望がますます高まってきている。
【０００４】
コンテンツの解析においては、類似コンテンツの検索が重要な役割を果たす。例えば、コンテンツを分類する場合は、類似したコンテンツは同じカテゴリに分類する。あるいは検索の場合、あるコンテンツをクエリとして与えたとき、このコンテンツに類似したコンテンツを検索することが基本的な要件となる。そのほか、コンテンツ推薦においても利用者がこれまでに閲覧した／閲覧しているコンテンツと類似したコンテンツを発見してこれを推薦するし、コンテンツ要約の場合においても、類似したコンテンツを提示することは冗長であるため、これを発見して省くような処理が必要となる。
【０００５】
ここで、類似コンテンツを発見する典型的な手続きについて説明する。まず、コンテンツをある特徴量によって表現する。次に、特徴量同士の近さを測ることで類似度を計算し、この類似度に基づいて類似コンテンツを発見する。単純な例を挙げれば、コンテンツが画像や映像であれば、画像（映像フレーム）の色ヒストグラムを特徴量としてその類似度を測ることができる。コンテンツが文書であれば、単語の出現頻度をヒストグラム化したもの（Ｂａｇ−ｏｆ−Ｗｏｒｄｓヒストグラムなどと呼ぶ）を特徴量として類似度を測ることができる。いうまでもなく、仮にコンテンツの数が１０００あれば、１０００のコンテンツそれぞれに対して類似度を計算し、結果類似度の高いコンテンツを類似コンテンツとして拾い上げる必要がある。
【０００６】
しかしながら、前述のように、膨大な量のコンテンツを対象にした場合、下記２つの重要な課題がある。第１の課題は、計算時間がかかることである。第２の課題は、メモリを大量に消費することである。
【０００７】
通常、特徴量の次元がＤ、コンテンツがＮ個あったとすると、あるコンテンツとそれ以外の全てのコンテンツとの類似度を計算する際、Ｏ（ＤＮ）の計算時間を要する。また、即時検索を実行するためには、特徴量あるいはその類似度をメモリに蓄積しておくことが好ましいが、これを行うためにはＯ（Ｎ２）のメモリが必要となる。億を超えるオーダのコンテンツを扱う必要がある昨今においては、非現実的な時間とメモリを要するのである。
【０００８】
さらに、コンテンツの特徴量（ベクトル）の次元Ｄは高次元になることが多く、その類似度の計算には膨大な時間を要する。一般に、文書のＢａｇ−ｏｆ−Ｗｏｒｄｓヒストグラムの次元は、単語の種類（語彙）と同次元になる。画像の色ヒストグラムのような単純な特徴量であっても、一般に数百〜数千次元の実数値ベクトルとなるし、最近用いられるスパース表現やフィッシャーカーネルに基づく特徴表現では、数十万〜数百万次元のベクトルとなることもあり得る。
【０００９】
以上の事情から、コンテンツ数Ｎおよび特徴量の次元Ｄの双方に対して、効率的な類似コンテンツ検索を実現する手段が求められているのである。
【００１０】
この課題に対して、コンテンツの特徴量を低容量な表現に変換し、効率的に類似コンテンツを発見する技術に関する取り組みがなされてきた。従来いくつかの発明がなされ、開示されてきている。特許文献１に開示されている技術では、コンテンツの特徴量と、異なる２つのコンテンツを関連付けるべきか否かを示す関連情報（正解データ）に基づいてハッシュ関数のパラメータを求め、このハッシュ関数を基に特徴量を低ビットなハッシュ値に変換する。便宜上コンテンツの特徴量をｘ∈ＲＤ、これに対応するハッシュ値をｙ∈｛±１｝Ｂと表すとすると、ハッシュ関数は
【数１】
2015079333.tif 000003
の形式で与えられる。ここで、Ｗ∈ＲＤ×Ｂ、およびｂ∈ＲＢは、上記求める対象となるハッシュ関数のパラメータである。パラメータは、関連するコンテンツ同士のハッシュ値が同一又は近しい値になるように調整されるので、ハッシュ値の参照によって全てのコンテンツ間で類似度を求めることなく、近似的に類似コンテンツを検索することができる。
【００１１】
また、非特許文献１に開示されている技術では、類似する２つのコンテンツ（特徴量）において、元の特徴量の類似度と衝突確率が等しくなるようなハッシュ関数群を生成する。典型的な類似度としてコサイン類似度を考えており、その場合のハッシュ関数生成の基本的な手続きは、特徴量空間にランダムな超平面を複数生成することによる（ｒａｎｄｏｍ  ｐｒｏｊｅｃｔｉｏｎと呼ばれる）。具体的には、ハッシュ関数は
【数２】
2015079333.tif 000004
と定義され、ランダムに生成されるＷ∈ＲＤ×ＢはＢ個の超平面を規定する。
【００１２】
また、非特許文献２に開示されている技術は、特徴量の分布を捉え、その分布に対して最適なハッシュ値を構成する。具体的には、特徴量空間における多様体構造を捉え、その多様体構造を最適に保存するバイナリ空間（ハッシュ空間）への非線形な埋め込みを求めることで、元の高次元な特徴量を、低ビットなハッシュ値に変換する。そのハッシュ値の類似性を評価することで、高速な類似コンテンツ発見を実現することができる。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２０１３−６８８８４号公報
【非特許文献】
【００１４】
【非特許文献１】M. Datar, N. Immorlica, P. Indyk, V.S. Mirrokni, "Locality-Sensitive Hashing Scheme based on p-Stable Distributions", In Proceedings of the Twentieth Annual Symposium on Computational Geometry, 2004, p.253-262
【非特許文献２】入江  豪、Ｚｈｅｎｇｕｏ  Ｌｉ、Ｓｈｉｈ−Ｆｕ  Ｃｈａｎｇ，“構造を保存するハッシング”、画像の認識・理解シンポジウム、２０１３．
【発明の概要】
【発明が解決しようとする課題】
【００１５】
上記の特許文献１、非特許文献１に開示されている技術では、（１）式および（２）式に示したように、ハッシュ値ｙを求めるため、元のＤ次元特徴量ｘとそのパラメータＷとの内積を求める必要があった。したがって、ハッシュ値を求めるための時／空間計算量はＯ（ＤＢ）、すなわち元の特徴量空間の次元Ｄに対して線形時間必要であった。
【００１６】
非特許文献２に開示されている技術では、特徴量の分布を柔軟な多様体構造として捉え、さらにハッシュ値に変換することで非常に高精度かつ高速な類似コンテンツの発見を可能にしている。しかしながら、この技術は、陽にハッシュ関数を持たず、ノンパラメトリックな形式での埋め込みによってハッシュ値を求めるため、ハッシュ関数の学習には多くの時間を要し、また、ハッシュ値の生成には元の高次元な特徴量をメモリ上に保持しておく必要があったために、上記特許文献１、非特許文献１よりもさらに多くのメモリが必要になるという問題がある。
【００１７】
以上のことから、これまで、コンテンツ数Ｎに対して線形時間以下の計算時間で類似コンテンツを求める手段は実現されていたものの、依然として特徴量の次元Ｄに対しては線形以上の計算時間を要していた。すなわち、現状、上記いずれの技術によっても、コンテンツ数Ｎ、および、特徴量の次元Ｄ双方に対して効率的な類似コンテンツ検索は実現されていないのが実状である。
【００１８】
本発明は、このような事情に鑑みてなされたもので、高次元な特徴量で表現されたコンテンツが大量に蓄積されたコンテンツデータベースに対して、高速かつ省メモリな検索を可能にするハッシュ関数とハッシュ値を生成することができるハッシュ関数生成方法、ハッシュ値生成方法、ハッシュ関数生成装置、ハッシュ値生成装置、ハッシュ関数生成プログラム及びハッシュ値生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
本発明は、デジタルデータに対応して定まるＤ（Ｄ＞０）次元実数値ベクトルをバイナリ値に変換するハッシュ関数生成方法であって、１以上Ｄ以下の自然数の集合の中から、予め定めた自然数Ｃ（０＜Ｃ≦Ｄ）の数だけ重複なく自然数の組を選択する選択ステップと、前記自然数Ｃと同数の次元を持つパラメータベクトルを生成するベクトル生成ステップと、前記選択された自然数Ｃの組と前記パラメータベクトルの組によってハッシュ関数を生成する関数生成ステップとを有すること特徴とする。
【００２０】
本発明は、前記選択ステップでは、前記自然数の選択をランダムに行うことを特徴とする。
【００２１】
本発明は、前記ベクトル生成ステップでは、前記パラメータベクトルを指数型分布族に属する確率分布に従う乱数によって生成することを特徴とする。
【００２２】
本発明は、デジタルデータに対応するＤ（Ｄ＞０）次元実数値ベクトルを算出するベクトル算出ステップと、前記ハッシュ関数生成方法により生成された１つ以上のハッシュ関数を用いて、前記デジタルデータを１つ以上のバイナリ値に変換する変換ステップとを有することを特徴とする。
【００２３】
本発明は、デジタルデータに対応して定まるＤ（Ｄ＞０）次元実数値ベクトルをバイナリ値に変換するハッシュ関数生成装置であって、１以上Ｄ以下の自然数の集合の中から、予め定めた自然数Ｃ（０＜Ｃ≦Ｄ）の数だけ重複なく自然数の組を選択する選択手段と、前記自然数Ｃと同数の次元を持つパラメータベクトルを生成するベクトル生成手段と、前記選択された自然数Ｃの組と前記パラメータベクトルの組によってハッシュ関数をハッシュ関数を生成する関数生成手段とを備えることを特徴とする。
【００２４】
本発明は、デジタルデータに対応するＤ（Ｄ＞０）次元実数値ベクトルを算出するベクトル算出手段と、前記ハッシュ関数生成装置により生成された１つ以上のハッシュ関数を用いて、前記デジタルデータを１つ以上のバイナリ値に変換する変換手段とを備えることを特徴とする。
【００２５】
本発明は、コンピュータに、前記ハッシュ関数生成方法を実行させるためのハッシュ関数生成プログラムである。
【００２６】
本発明は、コンピュータに、前記ハッシュ値生成方法を実行させるためのハッシュ値生成プログラムである。
【発明の効果】
【００２７】
本発明によれば、高次元な特徴量で表現されたコンテンツが大量に蓄積されたコンテンツデータベースを検索する際に用いるハッシュ関数とハッシュ値を、高速かつ省メモリで生成することができるという効果が得られる。
【図面の簡単な説明】
【００２８】
【図１】本発明の一実施形態の構成を示すブロック図である。
【図２】ハッシュ関数生成処理の動作を示すフローチャートである。
【図３】ハッシュ値生成処理の動作を示すフローチャートである。
【図４】ハッシュ値によるハッシュテーブルを示す説明図である。
【図５】類似コンテンツ検索を実施する場合において、その一例の装置構成を示すブロック図である。
【発明を実施するための形態】
【００２９】
以下、図面を参照して、本発明の一実施形態によるハッシュ関数生成装置及びハッシュ値生成装置を実現するための情報処理装置を説明する。図１は同実施形態の構成を示すブロック図である。同図に示す情報処理装置１は、入力部１１、特徴抽出部１２、ハッシュ関数生成部１３、ハッシュ関数記憶部１４、ハッシュ値生成部１５及び出力部１６を備える。このうち、本発明の主たる機能を備える構成要素はハッシュ関数生成部１３及びハッシュ値生成部１５である。
【００３０】
情報処理装置１は、コンテンツデータベース２と通信手段を介して接続され、入力部１１、出力部１６を介して相互に情報通信し、指定された特徴量の次元Ｄに対して予め定められた自然数Ｃ（０＜Ｃ≦Ｄ）を参照してハッシュ関数を生成するハッシュ関数生成処理と、生成したハッシュ関数を用いてコンテンツを複数のバイナリ値に変換するハッシュ値生成処理を行う。
【００３１】
コンテンツデータベース２は、情報処理装置１の内部にあっても外部にあっても構わず、通信手段は任意の公知ものを用いることができるが、本実施形態においては、外部にあるものとして、通信手段は、インターネット、ＴＣＰ／ＩＰにより通信するよう接続されているものとする。コンテンツデータベース２は、いわゆるＲＤＢＭＳ（Relational Database Management System）などで構成されているものとしてもよい。
【００３２】
コンテンツデータベース２には、少なくともコンテンツ自体、あるいは、当該データの所在を一意に示すアドレスが記憶されている。コンテンツは、例えば、文書であれば文書ファイル、画像であれば画像ファイル、音であれば音ファイル、映像であれば映像ファイルなどである。好ましくは、コンテンツデータベース２には、各コンテンツを一意に識別可能な識別子が含まれているものとする。その他、メタデータとして、例えばコンテンツの内容を表現するもの（コンテンツのタイトル、概要文、キーワード）、コンテンツのフォーマットに関するもの（コンテンツのデータ量、サムネイル等のサイズ）などを含んでいてもよい。
【００３３】
情報処理装置１が備える各部およびコンテンツデータベース２は、演算処理装置、記憶装置等を備えたコンピュータやサーバ等により構成して、各部の処理がプログラムによって実行されるものとしてもよい。このプログラムは情報処理装置１が備える記憶装置に記憶されており、磁気ディスク、光ディスク、半導体メモリ等の記録媒体に記録することも、ネットワークを通して提供することも可能である。もちろん、その他いかなる構成要素についても、単一のコンピュータやサーバによって実現しなければならないものではなく、ネットワークによって接続された複数のコンピュータに分散して実現してもよい。
【００３４】
次に、図１に示す情報処理装置１の構成について説明する。入力部１１は、ハッシュ関数生成処理時には、自然数Ｃをハッシュ関数生成部１３に出力する。ハッシュ値生成処理時には、コンテンツデータベース２からコンテンツデータを取得して特徴抽出部１２に出力する。特徴抽出部１２は、入力部１１より得たコンテンツデータを解析し、コンテンツを特徴的に表す特徴量を抽出し、ハッシュ値生成部１５に出力する。
【００３５】
ハッシュ関数生成部１３は、入力部１１から出力された自然数Ｃに基づいて、１つ以上のハッシュ関数を生成してハッシュ関数記憶部１４に記憶する。ハッシュ関数記憶部１４は、ハッシュ関数生成部１３が生成した１つ以上のハッシュ関数を記憶する。ハッシュ値生成部１５は、ハッシュ関数記憶部１４に記憶された１つ以上のハッシュ関数に基づいて、特徴抽出部１２から出力された特徴量を複数のバイナリ値であるハッシュ値に変換し、出力部１６に出力する。出力部１６は、ハッシュ値生成部１５で求めたハッシュ値をコンテンツデータベース２に出力して記憶する。
【００３６】
次に、図１に示す情報処理装置１の処理動作を説明する。図１に示す情報処理装置１は、ハッシュ関数を生成するハッシュ関数生成処理と、特徴量をハッシュ化するハッシュ値生成処理を実行する。以下、これら２つの処理について説明する。
【００３７】
最初に、ハッシュ関数生成処理について説明する。図２は、ハッシュ関数生成処理の処理動作を示すフローチャートである。ハッシュ関数生成処理は、実際にコンテンツデータをハッシュ化する前に、少なくとも１度実施しておく処理である。
【００３８】
まず、入力部１１は、特徴量の次元Ｄ及び予め定めた自然数Ｃをハッシュ関数生成部１３に出力する（ステップＳ２０１）。続いて、ハッシュ関数生成部１３は、自然数Ｃに基づいて１つ以上のハッシュ関数を生成し、ハッシュ関数記憶部１４に記憶する（ステップＳ２０２）。
【００３９】
以上の処理によりハッシュ関数を生成することができる。なお、ハッシュ関数生成処理の詳細については後述する。
【００４０】
次に、ハッシュ値生成処理について説明する。図３は、ハッシュ値生成処理の処理動作を示すフローチャートである。ハッシュ値生成処理は、ハッシュ関数記憶部１４に記憶されたハッシュ関数を用いてコンテンツの特徴量をハッシュ化する処理である。
【００４１】
まず、入力部１１は、コンテンツデータベース２あるいは外部から直接コンテンツデータを入力し特徴抽出部１２に出力する（ステップＳ３０１）。続いて、特徴抽出部１２は、コンテンツデータから特徴量を抽出してハッシュ値生成部１５に出力する（ステップＳ３０２）。
【００４２】
次に、ハッシュ値生成部１５は、ハッシュ関数記憶部１４に記憶された１つ以上のハッシュ関数を用いて、特徴量をハッシュ値に変換し、出力部１６に出力する（ステップＳ３０３）。本実施形態においては、１つのハッシュ関数につき、特徴量は１ビットに変換されるので、ハッシュ関数記憶部１４にＢ個のハッシュ関数が記憶されている場合は、特徴量はＢビットのハッシュ値に変換される。
【００４３】
最後に、出力部１６は、ハッシュ値をコンテンツデータベース２に記憶する（ステップＳ３０４）。
【００４４】
以上の処理により、入力したコンテンツのハッシュ値を求めることができる。
【００４５】
次に、各処理の詳細を説明する。始めに、ハッシュ関数生成処理について詳細に説明する。本実施形態においては、コンテンツはそれぞれ特徴量ｘｉ∈ＲＤ、すなわちＤ（Ｄ＞０）次元の実数値ベクトルとして表現する。特徴量として何を抽出するか、また、Ｄをいくつに設定するかは本発明の主たる特徴とは無関係であり、本実施形態では、実数値ベクトルであればいかなる特徴量を選んだ場合でも、その特徴量とは無関係に適用可能であり、非常に汎用的であるという利点を持つ。
【００４６】
したがって、コンテンツの種類や目的に応じて、任意の公知のものを用いてよいが、いくつかのコンテンツの種類と、代表的な特徴量の例についてはハッシュ値生成処理の詳細説明の際に詳述する。
【００４７】
ｈ：ＲＤ→｛−１，１｝となるハッシュ関数の集合を求める。｛−１，１｝と｛０，１｝は情報量という観点で本質的に差異がないことに注意すれば、各ｈによって、ＲＤは０または１を取るバイナリ値に写像されるから、特徴量ｘｉ∈ＲＤは、ハッシュ関数集合Ｈ＝｛ｈ１，ｈ２，・・・，ｈＢ｝によってＢ個（Ｂ≧１）のバイナリ値、すなわち、Ｂビットのハッシュ値に変換されることになる。
【００４８】
本発明の目的は、このハッシュ値によって時間のかかる類似度計算を省略することである。したがって、ハッシュ関数は、元のコンテンツの類似度を表すものであることが要請され、高い類似度を持つコンテンツほど、ハッシュ値の距離（ハミング距離）が近くなることが好ましい。以降、一般性を失うことなく、特徴量は、各次元でその平均が０になるように正規化（平行移動）されているとする。正規化するには、ｘｉの平均を、各ｘｉから減算すればよいのであり、これはｘｉ∈ＲＤにおいて常に可能である。
【００４９】
以下、ハッシュ関数を１つ求める手続きについて説明する。Ｂビットのハッシュ値を得たい場合には、同じ手続きをＢ回繰り返せばよい。
【００５０】
ここで、先行技術の一つである非特許文献１の技術について、さらに詳細に説明する。非特許文献１の技術では、下記に示すハッシュ関数を用いていた。
【数３】
2015079333.tif 000005
ｗ∈ＲＤは指数型分布族に属する確率分布、例えば標準正規に従う乱数によってランダムに生成されるパラメータであり、ランダムな超平面を規定する。言うまでもなく、（３）式により規定されるハッシュ関数は、ｈ：ＲＤ→｛−１，１｝である。さらに、このように生成されたハッシュ関数は、元のコンテンツの類似度を保存する。
【００５１】
ある任意の特徴量のペアｘｉ，ｘｊ∈ＲＤを考え、これら２点間のなす角をθｉｊとする。これら２点間の距離ｄｉｓｔ（ｘｉ，ｘｊ）とθｉｊは、それぞれ
【数４】
2015079333.tif 000006
特徴量ｘｉのノルムが１に正規化されていたとすると、
【数５】
2015079333.tif 000007
【００５２】
したがって、距離ｄｉｓｔ（ｘｉ，ｘｊ）とθｉｊには１対１の関係が存在する。非特許文献１のハッシュ関数ｈは、次の性質を持つ。
（１）ある距離ｒに対して、もしθｉｊ≦ｒであれば、ｈ（ｘｉ）とｈ（ｘｊ）が衝突する確率は１−ｒ／π以上となる。
（２）ｒよりもｒε倍だけ離れた距離ｒ（１＋ε）に対して、もしθｉｊ＞ｒ（１＋ε）であれば、ｈ（ｘｉ）とｈ（ｘｊ）が衝突する確率は１−ｒ（１＋ε）／π以下となる。
【００５３】
すなわち、元の距離に対するハッシュの衝突確率が対応しており、ここで求めようとする性質を満たす。
【００５４】
しかしながら、この技術は、元の特徴量空間が高次元であるような場合、すなわち、Ｄが大きい場合には適用できないという問題がある。なぜならば、ハッシュ値を生成するためには（３）式を計算する必要があるが、ｗをメモリにストアするためには空間計算量がＯ（Ｄ）、（３）式に含まれるｗとｘとの内積計算には時間計算量がＯ（Ｄ）掛かるため、Ｄに対してその計算量が線形に増加してしまうためである。
【００５５】
例えば、近年よく用いられるフィッシャーカーネル等による高次元特徴量を用いたとすると、Ｄ＝１００００００の場合、１２８バイトのハッシュ値を生成するのにメモリは３．８ＧＢ、およそ２秒程度を要する。実際、モバイル端末を用いた実時間アプリケーション等を想定した場合には現実的な計算量とはならない。
【００５６】
本実施形態は、上記問題を解決するハッシュ関数を生成することができる。ハッシュ関数として次のようなハッシュ関数を考える。
【数６】
2015079333.tif 000008
【００５７】
また、ｗ∈ＲＤ、Ｓ∈｛０，１｝Ｄ×Ｄはパラメータである。ここで、Ｓについて、下記の制約を付す。
・対角行列（対角成分以外は全て０を持つ行列）であること。
・対角成分についても、限られたＣ個（Ｃ≦Ｄ）の要素のみ１を取り、それ以外は０であること。
【００５８】
このようにして定義されたＳは、Ｓ：ＲＤ→ＲＣへの写像としての役割を果たし、Ｓｘ∈ＲＣ、また同時に、Ｓｗ∈ＲＣとなる。なお、下記の性質がある。
【数７】
2015079333.tif 000009
【００５９】
上記のように定義されたハッシュ関数は、非特許文献１に記載のハッシュ関数による時空間計算量Ｏ（Ｄ）よりも小さくできる。なぜならば、実体として、（６）式を計算する上で必要となるのは、Ｓｗをメモリにストアするために必要なＯ（Ｃ）、（７）式より、ＳｗとＳｘの内積計算に掛かる計算量もＯ（Ｃ）であるからである。前述の通り、Ｃは予め定められたＣ≦Ｄの自然数であり、どのように与えてもよい。例えば、Ｃ＝１０００などとしてもよく、この場合、Ｄ＝１００００００であるとすると、１２８バイトのハッシュ値を生成するのにメモリは０．００３８ＧＢ、およそ０．００２秒程度で計算可能となる。非特許文献１を用いた場合と比較して、メモリ、計算時間ともに１／１０００で実行できることとなり、モバイル端末を用いた実時間アプリケーション等を想定した場合であっても、現実的な計算時間で実行可能となる。
【００６０】
ここで、非特許文献１の技術においては、元の距離に対するハッシュの衝突確率が対応しており、高い類似度を持つコンテンツほど、ハッシュ値の距離が近くなるような、検索を実行する上で好ましい性質を有していた。一方、本実施形態のハッシュ関数も、以下詳述するような手続きによってｗおよびＳを決定することで、全く同様の性質を持つようにハッシュ関数を決定することができる。以下順に説明する。
【００６１】
まず、ｗの決定について説明する。ｗ∈ＲＤは、非特許文献１と同様、指数型分布族に属する確率分布、例えば標準正規に従う乱数によってランダムに生成すればよい。乱数を生成する方法は、任意の公知の方法を利用してよい。例えば、予め用意した乱数表によるもの（メルセンヌツイスター等）、超一様分布列に基づくもの、ボックスミュラー法によるものなどを用いればよい。
【００６２】
次に、Ｓの決定について説明する。Ｓは、次の２段階の手続きによって求めればよい。
（ｉ）１以上Ｄ以下の自然数の集合の中から、一様な確率でＣ個を選択する。Ｃ個の自然数の集合を便宜上Ｉと表す。
（ｉｉ）Ｓの対角成分ｓｉｉのうち、ｉ∈Ｉである要素のみ１とする。
【００６３】
上記のようにランダムに決定したｗおよびＳによって構成される（６）式のハッシュ関数は、次の性質を持つ。
（１）ある距離ｒに対して、もしθｉｊ≦ｒであれば、ｈ（ｘｉ）とｈ（ｘｊ）が衝突する確率は１−ｒ／π以上となる。
（２）ｒよりもｒε倍だけ大きい距離ｒ（１＋ε）に対して、もしθｉｊ＞ｒ（１＋ε）であれば、ｈ（ｘｉ）とｈ（ｘｊ）が衝突する確率は１−（ｒ（１＋ε）−θｉｊ⊥）／π以下となる。
【００６４】
ただし、θｉｊ⊥は、Ｓの対角成分の内、¬（ｉ∈Ｉ）（¬は、否定を表す）となる要素に対応する次元のみによって構成される空間（すなわち、ＲＣの直交補空間）上でｘｉとｘｊがなす角である。
【００６５】
この性質は、一般に、θｉｊとθｉｊ⊥、さらにＳによって写像される部分空間上でｘｉとｘｊがなす角θｉｊｓとの間に、θｉｊ−θｉｊ⊥≦θｉｊｓ≦θｉｊという関係が成り立つこと、および、ｘｉとｘｊのハッシュ値が等しくなる確率が１−θｉｊｓ／πとなることから導かれる。
【００６６】
以上のことから、本実施形態により生成されるハッシュ関数は、非特許文献１の技術と同様に、ハッシュ値の衝突確率と元の距離が対応するという、コンテンツ検索において望ましい性質を持ちながら、さらに、非特許文献１の技術よりも数段高速かつ省メモリであるという特徴を兼ね備えている。
【００６７】
以上のようにして求めたハッシュ関数のパラメータｗ、Ｓをハッシュ関数記憶部１４に保存する。この際、ｗとＳをそのまま記憶してもよいし、または、選択された要素の集合、すなわち、上記で言うところのＩとＳｗ（ｗにＳを掛けたもの）を記憶してもよい。両者のどちらの場合においても、後述するハッシュ値生成処理を実施できるが、後者の方がストレージ上よりコンパクトに記憶できる利点がある。
【００６８】
また、ＩとＳｗは、そのまま記憶しても、あるいは可変長符号化などの任意の公知の可逆圧縮手段を用いて記憶してもよい。
【００６９】
次に、前述したハッシュ関数生成処理によって生成されたハッシュ関数によって、ハッシュ値を生成する処理の一例について詳述する。前述の通り、本実施形態においては、ステップＳ３０１において、入力部１１が、コンテンツデータを得た後、続くステップＳ３０２において、特徴抽出部１２がコンテンツデータから特徴量を抽出、その後、ステップＳ３０３において、ハッシュ値生成部１５が、ハッシュ関数記憶部１４に記憶された１つ以上のハッシュ関数を用いて、特徴量をハッシュ値に変換する。したがって、ここでは、特徴量抽出処理、ハッシュ値生成処理について詳細に説明する。
【００７０】
始めに特徴量の抽出処理について説明する。特徴量を抽出する処理は、コンテンツの種類に依存する。例えば、コンテンツが文書であるか、画像であるか、音であるか、映像であるかによって、抽出するまたは抽出できる特徴量は変化する。ここで、どのような特徴量を抽出するかは、本実施形態の要件として重要ではなく、一般に知られた公知の特徴抽出処理を用いてよい。具体的には、あるコンテンツから抽出された次元を持つ数値データ（スカラー又はベクトル）であれば、あらゆる特徴量に対して有効である。したがって、ここでは、本実施形態の一例に適する、各種コンテンツに対する特徴抽出処理の一例を説明する。
【００７１】
コンテンツが文書である場合には、文書中に出現する単語の出現頻度を用いることができる。例えば、公知の形態素解析を用いて、名詞、形容詞等に相当する単語ごとに、その出現頻度を計数すればよい。この場合、各文書は単語種別と同じだけの次元を持つベクトルとして表現される。
【００７２】
また、コンテンツが画像である場合には、例えば、明るさ特徴、色特徴、テクスチャ特徴、コンセプト特徴、景観特徴などを抽出する。明るさ特徴は、ＨＳＶ色空間におけるＶ値を数え上げることで、ヒストグラムとして抽出することができる。この場合、各画像はＶ値の量子化数（例えば、１６ビット量子化であれば２５６諧調）と同数の次元を持つベクトルとして表現される。色特徴は、Ｌ＊ａ＊ｂ＊色空間における各軸（Ｌ＊、ａ＊、ｂ＊）の値を数え上げることで、ヒストグラムとして抽出することができる。各軸のヒストグラムのビンの数は、例えば、Ｌ＊に対して４、ａ＊に対して１４、ｂ＊に対して１４などとすればよく、この場合、３軸の合計ビン数は、４×１４×１４＝７８４、すなわち７８４次元のベクトルとなる。
【００７３】
テクスチャ特徴としては、濃淡ヒストグラムの統計量（コントラスト）やパワースペクトルなどを求めればよい。あるいは、局所特徴量を用いると、色や動きなどと同様、ヒストグラムの形式で抽出することができるようになるため好適である。局所特徴としては、例えば下記の参考文献１に記載されるＳＩＦＴ（Scale Invariant Feature Transform）や、下記の参考文献２に記載されるＳＵＲＦ（Speeded Up Robust Features）などを用いることができる。
［参考文献１］D.G. Lowe, "Distinctive Image Features from Scale-Invariant Keypoints ", International Journal of Computer Vision, pp.91-110, 2004
［参考文献２］H. Bay, T. Tuytelaars, and L.V. Gool, "SURF: Speeded Up Robust Features", Lecture Notes in Computer Science, vol. 3951, pp.404-417, 2006
【００７４】
これらによって抽出される局所特徴は、例えば１２８次元の実数値ベクトルとなる。このベクトルを、予め学習して生成しておいた符号長を参照して、符号に変換し、その符号の数を数え上げることでヒストグラムを生成することができる。この場合、ヒストグラムのビンの数は、符号長の符号数と一致する。又は、参考文献３に記載のスパース表現や、参考文献４、５に記載のフィッシャーカーネルに基づく特徴表現などを利用してもよい。
［参考文献３］  Jinjun Wang, Jianchao Yang, Kai Yu, Fengjun Lv, Thomas Huang, and Yihong Gong, "Locality-constrained Linear Coding for Image Classification", IEEE Conference on Computer Vision and Pattern Recognition, pp. 3360-3367, 2010.
［参考文献４］  Florent Perronnin, Jorge Sanchez, Thomas Mensink, "Improving the Fisher Kernel for Large-Scale Image Classification", European Conference on Computer Vision, pp. 143-156, 2010.
［参考文献５］  Herve Jegou, Florent Perronnin, Matthijs Douze, Jorge Sanchez, Patrick Perez, Cordelia Schmid, "Aggregating Local Image Descriptors into Compact Codes", IEEE Trans. Pattern Recognition and Machine Intelligence, Vol. 34, No. 9, pp. 1704-1716, 2012.
【００７５】
結果として生成される特徴量は、いずれの場合にも、符号長の符号数に依存した長さを持つ実数値ベクトルになる。
【００７６】
コンセプト特徴とは、画像中に含まれる物体や、画像が捉えているイベントのことである。任意のものを用いてよいが、例を挙げれば、「海」、「山」、「ボール」などのようなものである。もし、ある画像に「海」が映っていた場合、その画像は「海」コンセプトに帰属する画像であるという。その画像が、各コンセプトに帰属するか否かは、コンセプト識別器を用いて判断することができる。通常、コンセプト識別器はコンセプト毎に一つ用意され、画像の特徴量を入力として、その画像があるコンセプトに帰属しているか否かを帰属レベルとして出力する。コンセプト識別器は、予め学習して獲得しておくものであり、決められた画像特徴、例えば先に述べた局所特徴と、予め人手によって、その画像がどのコンセプトに帰属しているかを表した正解ラベルとの関係を学習することによって獲得する。学習器としては、例えばサポートベクターマシンなどを用いればよい。コンセプト特徴は、各コンセプトへの帰属レベルをまとめてベクトルとして表現することで得ることができる。この場合、生成される特徴量はコンセプトの数と同数の次元を持つベクトルとなる。
【００７７】
景観特徴は、画像の風景や場面を表現した特徴量である。例えば参考文献６に記載のＧＩＳＴ記述子を用いることができる。ＧＩＳＴ記述子は画像を領域分割し、各領域に対して一定のオリエンテーションを持つフィルタを掛けたときの係数によって表現されるが、この場合、生成される特徴量は、フィルタの種類（分割する領域の数とオリエンテーションの数）に依存した長さのベクトルとなる。
［参考文献６］A. Oliva and A. Torralba, "Building the gist of a scene: the role of global image features in recognition", Progress in Brain Research, 155, pp.23-36, 2006
【００７８】
コンテンツが音である場合には、音高特徴、音圧特徴、スペクトル特徴、リズム特徴、発話特徴、音楽特徴、音イベント特徴などを抽出する。音高特徴は、例えばピッチを取るものとすればよく、下記の参考文献７に記載される方法などを用いて抽出することができる。この場合、ピッチを１次元ベクトル（スカラー）として表現するか、あるいはこれをいくつかの次元に量子化しておいてもいい。
［参考文献７］古井貞熙，“ディジタル音声処理，４．９ピッチ抽出”，ｐｐ．５７−５９，１９８５
【００７９】
音圧特徴としては、音声波形データの振幅値を用いるものとしてもよいし、短時間パワースペクトルを求め、任意の帯域の平均パワーを計算して用いるものとしてもよい。いずれにしても、音圧を計算するバンドの数に依存した長さのベクトルとなる。スペクトル特徴としては、例えばメル尺度ケプストラム係数（ＭＦＣＣ：Mel-Frequency Cepstral Coefficients）を用いることができる。
【００８０】
リズム特徴としては、例えばテンポを抽出すればよい。テンポを抽出するには、例えば下記の参考文献８に記載される方法などを用いることができる。
［参考文献８］E.D. Scheirer, "Tempo and Beat Analysis of Acoustic Musical Signals ", Journal of Acoustic Society America, Vol. 103, Issue 1, pp.588-601, 1998
【００８１】
発話特徴、音楽特徴は、それぞれ、発話の有無、音楽の有無を表す。発話・音楽の存在する区間を発見するには、例えば下記の参考文献９に記載される方法などを用いればよい。
［参考文献９］K. Minami, A. Akutsu, H. Hamada, and Y. Tonomura, "Video Handling with Music and Speech Detection", IEEE Multimedia, vol. 5, no. 3, pp.17-25, 1998
【００８２】
音イベント特徴としては、例えば、笑い声や大声などの感情的な音声、あるいは、銃声や爆発音などの環境音の生起などを用いるものとすればよい。このような音イベントを検出するには、例えば下記の参考文献１０に記載される方法などを用いればよい。
［参考文献１０］国際公開第２００８／０３２７８７号
【００８３】
コンテンツが映像である場合、映像は、一般に画像と音のストリームであるから、上記説明した画像特徴と音特徴を用いることができる。映像中のどの画像、音情報を分析するかについては、例えば、予め映像をいくつかの区間に分割し、その区間ごとに１つの画像、音から特徴抽出を実施する。
【００８４】
映像を区間に分割するには、予め決定しておいた一定の間隔で分割するものとしてもよいし、例えば下記の参考文献１１に記載される方法などを用いて、映像が不連続に切れる点であるカット点によって分割するものとしてもよい。
［参考文献１１］Y. Tonomura, A. Akutsu, Y. Taniguchi, and G. Suzuki, "Structured Video Computing", IEEE Multimedia, pp.34-43, 1994
【００８５】
望ましくは、後者の方法を採用する。映像区間分割処理の結果として、区間の開始点（開始時刻）と終了点（終了時刻）が得られるが、この時刻毎に別々の特徴量として扱えばよい。
【００８６】
以上のように抽出した特徴量は、一つあるいは複数を利用してもよいし、その他の公知の特徴量を用いるものとしてもよい。
【００８７】
次に、ハッシュ値生成処理について説明する。前述のハッシュ関数生成処理が済んでいれば、ハッシュ関数記憶部１４には、Ｂ個のハッシュ関数が記憶されている。これを用いれば、（６）式にしたがって、特徴量で表現された任意のコンテンツを、Ｂビット以下のハッシュ値で表現することができる。
【００８８】
ここで、実際には（６）式をそのまま計算する必要はなく、より効率的にそのハッシュ値を求めることができることを説明する。（６）式とＳの性質上、２つのベクトルｗおよびｘの要素のうち、結局のところハッシュ値を求めるために使われる要素は、先に選択されたＣ個の自然数に対応する次元の要素（すなわち、自然数の集合Ｉの要素に対応する次元）のみである。従って、ｗ、ｘそれぞれＩに含まれる次元に対応する要素のみを抜きだし、これらの内積を計算して符号関数を通せばよい。
【００８９】
簡単な例を示す。例えばＤ＝５、Ｃ＝２であり、ｗ＝（０．２，０．４，−０．４，０．１，０．５）Ｔ、ｘ＝（−０．５，０．２，０．７，−０．３，０．２）Ｔ、選択された自然数の集合がＩ＝｛３，４｝だったとする。このとき、ｗとｘそれぞれ３番目、４番目の要素のみを抜き出した新たなベクトルｗｃ＝（−０．４，０．１）Ｔ、ｘｃ＝（０．７，−０．３）Ｔの内積を計算すると、−０．４×０．７＋０．１×（−０．３）＝−０．３１で、負となるから、ハッシュ値の値は−１となる（｛０，１｝の場合は０とすればよい）。
【００９０】
この例が示したように、実際のハッシュ値の計算に使われるのは、ｗのＣ個の要素のみであるため、前述の通り、ハッシュ関数記憶部１４には、ｗ全てを記憶する必要はない。また、非特許文献１ではベクトル全体の内積計算が必要であるのに対し、本実施形態においては、その一部の計算のみでそのハッシュ値を求めることができるため、高い効率を得ることができる。
【００９１】
次に、ハッシュ値に基づくコンテンツ検索について説明する。以上、前述したハッシュ関数によって、類似コンテンツを高速かつ省メモリに検索する一例について説明する。コンテンツデータベース２にＮ個の特徴量Ｘ＝｛ｘ１，・・・，ｘＮ｝が記憶されているとし、これらの特徴量は全て（６）式に基づいてハッシュ値Ｙ＝｛ｙ１，・・・，ｙＮ｝に変換されているものとする。このとき、目的はＸに含まれない特徴量ｘｑに対して類似するコンテンツをＸの中から発見することである。
【００９２】
まず、（６）式に基づいて、特徴量ｘｑをハッシュ値ｙｑに変換しておく。最も単純には、図４に示すハッシュテーブルによる方法がある。まず、コンテンツデータベース２に登録されているハッシュ値Ｙによって、図４に示すようなハッシュテーブルを構成する。このテーブルでは、あるハッシュ値と、そのハッシュ値に変換された特徴量（コンテンツ識別子）を対応づけて記憶しており、ハッシュ値が与えられた際に、それと同一のハッシュ値を取るコンテンツを即時発見することができる。例えば、ハッシュ値“００００”を指定した場合、それに対応づけられたコンテンツ１、コンテンツ５・・・を直ちに発見できる。同様に、このハッシュテーブルを利用すれば、ハッシュ値ｙｑに対応したコンテンツを即座に発見することが可能となる。
【００９３】
この方法によれば、コンテンツデータベース２に登録されたコンテンツの数Ｎに寄らず、ほぼ一定の時間で高速に、かつ、元の特徴量をメモリに保持する必要がないため、省メモリに類似コンテンツを発見できるという利点がある。
【００９４】
また、別の方法として、ハミング距離による距離計算を利用することができる。すなわち、ハッシュ値ｙｑとＹに含まれるＮ個のハッシュ値との距離を計算し、距離の小さいものを類似コンテンツとして得るものである。ハッシュ値はバイナリであるため、距離計算は例えばハミング距離で計算することができるが、ハミング距離はＸＯＲ（排他的論理和）とｐｏｐｃｎｔ演算（すなわち、バイナリ列のうち、１となっているビットの数を数える演算）のみで計算できること、および、ハッシュ値は通常少数のバイナリ値で表現できることから、元の特徴量で距離計算する場合に比べ、遥かに高速に演算できる。
【００９５】
実験の結果、２．５３ＧＨｚ  Ｉｎｔｅｌ  Ｘｅｏｎ  ＣＰＵ  ａｎｄ  ６４ＧＢ  ＲＡＭのコンピュータを利用し、それぞれ９６０次元の景観特徴量で記述された約１００万枚の画像が記憶されたコンテンツデータベースに対し、６４ビットのハッシュ値を生成した場合には、元の特徴量で距離計算する場合に比べて、ハッシュ値でハミング距離計算した方が、約１０００倍高速に演算できた。
【００９６】
以上説明したように、本実施形態によれば、高次元な特徴量で表現されたコンテンツが大量に蓄積されたコンテンツデータベースに対して、高速かつ省メモリな検索を可能にするハッシュ関数、ハッシュ値の生成、およびコンテンツ検索を実現することができる。
【００９７】
なお、本実施形態の主要な特徴を満たす範囲内において、任意の用途と構成を取ることができることは言うまでもない。例えば、ハッシュ関数生成部１３とハッシュ値生成部１５は分離可能であり、例えば、上記例における装置構成を示す図１以外にも、サーバクライアント装置構成を取ることもできる。図５に、コンテンツ検索を実施する場合について、その一例を示す。
【００９８】
同図に示すサーバ装置８は、入力部８１、特徴抽出部８２、ハッシュ関数生成部８３、ハッシュ関数記憶部８４、ハッシュ値生成部８５、および出力部８６を備える。また、同図に示すクライアント装置１０は、入力部１０１、特徴抽出部１０２、ハッシュ値生成部１０３、ハッシュ関数記憶部１０４、および出力部１０５を備える。
【００９９】
ここで、サーバ装置８とクライアント装置１０において、共通する構成要素（入力部、特徴抽出部、ハッシュ関数記憶部、ハッシュ値生成部）はそれぞれ同一の機能を有するように構成し、また、図１に記載した各構成要素と同一名称のものは、図１の場合と同一の機能を有するものとしてよい。さらに、ハッシュ値生成部の内容は、それぞれ何らかの通信手段で適宜同期されているものとする。
【０１００】
図５に示す装置構成における処理動作は下記の通りである。まずサーバ装置８は、上記説明した処理と同様の処理を以って、適宜ハッシュ関数を生成、クライアント装置のそれと同期する。さらに、コンテンツデータベース９中のコンテンツに対して、やはり上記説明した処理と同様の処理を以って、ハッシュ値を生成、コンテンツデータベース９に記憶しておく。
【０１０１】
一方、クライアント装置１０は、利用者からの検索要求、すなわち、新規コンテンツの入力部１０１への入力を受け付けたら、当該コンテンツに対してハッシュ値を生成クライアント装置で生成された新たなコンテンツに対するハッシュ値を生成し、出力部１０５からサーバ装置８の入力部８１へと当該ハッシュ値を出力する。
【０１０２】
クライアント装置１０からハッシュ値を受けた場合、サーバ装置８は、当該ハッシュ値を用いて、コンテンツデータベース９へと検索を掛け、ハッシュ値に基づいて類似コンテンツを発見し、その結果をクライアント装置１０へと出力する。
【０１０３】
最後に、クライアント装置１０は、サーバ装置８より受け取った検索結果を利用者に出力する。
【０１０４】
このように構成することで、サーバ装置８でハッシュ関数生成処理を実施し、クライアント装置ではハッシュ値生成処理のみを実施するように構成することができる。
【０１０５】
この構成を取るメリットを説明する。一般に、クライアント装置（ＰＣ，携帯端末等）は、サーバ装置と比較して演算能力に乏しいため、ハッシュ関数生成のように演算量が比較的多い処理には適さない場合がある。この構成にすれば、ハッシュ関数生成処理は演算能力の高いサーバ装置で適宜実施し、クライアント装置では演算量の少ないハッシュ値生成処理だけを実施することができる。さらに、通常、ネットワークを介した通信によってデータ容量の多い情報を伝送する場合、伝送時間が掛かるという問題があるが、当該構成によって、伝送するのは情報量の小さいハッシュ値のみでよくなり、検索に対する即応性を高めることができる。
【０１０６】
以上説明したように、この構成によれば、高次元な特徴量で表現されたコンテンツが大量に蓄積されたコンテンツデータベースに対して、高速かつ省メモリな検索を可能にすることができる。この構成により、省メモリであることから、例えば、メモリ量の小さいモバイル端末（スマートフォンやタブレット）での利用も可能となる。また、高速であることから、実時間性の要求される利用に対しても対応可能である。これらの効果を活用した具体的な利用シーンとして、街中を歩いているときに気になる場所や商品をモバイル端末で写真撮影し、類似した場所・商品を検索することが可能になる。
【０１０７】
前述した実施形態におけるハッシュ関数生成部、ハッシュ値生成部をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＰＬＤ（Programmable Logic Device）やＦＰＧＡ（Field Programmable Gate Array）等のハードウェアを用いて実現されるものであってもよい。
【０１０８】
以上、図面を参照して本発明の実施の形態を説明してきたが、上記実施の形態は本発明の例示に過ぎず、本発明が上記実施の形態に限定されるものではないことは明らかである。したがって、本発明の技術思想及び範囲を逸脱しない範囲で構成要素の追加、省略、置換、その他の変更を行ってもよい。
【産業上の利用可能性】
【０１０９】
高次元な特徴量で表現されたコンテンツが大量に蓄積されたコンテンツデータベースに対して、高速かつ省メモリな検索を可能にすることが不可欠な用途にも適用できる。
【符号の説明】
【０１１０】
１・・・情報処理装置、１１、８１、１０１・・・入力部、１２、８２、１０２・・・特徴抽出部、１３、８３・・・ハッシュ関数生成部、１４、８４、１０４・・・ハッシュ関数記憶部、１５、８５、１０３・・・ハッシュ値生成部、１６、８６、１０５・・・出力部、２・・・コンテンツデータベース、８・・・サーバ装置、９・・・コンテンツデータベース
【図１】
2015079333.tif 000010
【図２】
2015079333.tif 000011
【図３】
2015079333.tif 000012
【図４】
2015079333.tif 000013
【図５】
2015079333.tif 000014