(57)【要約】【課題】高速かつ省メモリでありながらも高精度にハッシュ関数の生成及びハッシュ値の生成を行う。【解決手段】ハッシュ関数生成方法は、コンテンツデータをＤ（Ｄ＞０）次元実数値ベクトルとして表現する特徴量を抽出するステップと、メディア種別ごとに特徴量について、その近傍の相対的幾何関係を求めるステップと、メディア種別が異なる複数のコンテンツデータの内容の関係性を示す関係指示子と相対的幾何関係とに基づいて、ハッシュ関数を表現するパラメータを決定してハッシュ関数を生成するステップとを有する。ハッシュ値生成方法は、コンテンツデータをＤ（Ｄ＞０）次元実数値ベクトルとして表現する特徴量を抽出するステップと、前記ハッシュ関数生成方法により生成された１つ以上のハッシュ関数を用いて、前記特徴量を１つ以上のバイナリ値に変換するステップとを有する。【選択図】図１
2015079102.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツデータをバイナリ値に変換するハッシュ関数生成方法であって、
コンテンツデータ及び該コンテンツデータのメディア種別から、該コンテンツデータをＤ（Ｄ＞０、Ｄはメディア種別により定まる）次元実数値ベクトルとして表現する特徴量を抽出する特徴量抽出ステップと、
前記メディア種別ごとに前記特徴量について、その近傍の相対的幾何関係を求める幾何関係算出ステップと、
前記メディア種別が異なる複数のコンテンツデータの内容の関係性を示す関係指示子と前記相対的幾何関係とに基づいて、ハッシュ関数を表現するパラメータを決定して前記ハッシュ関数を生成する関数生成ステップと
を有することを特徴とするハッシュ関数生成方法。
【請求項２】
前記ハッシュ関数は、前記特徴量と前記パラメータとの内積によって規定されることを特徴とする請求項１に記載のハッシュ関数生成方法。
【請求項３】
コンテンツデータ及び該コンテンツデータのメディア種別から、該コンテンツデータをＤ（Ｄ＞０、Ｄはメディア種別により定まる）次元実数値ベクトルとして表現する特徴量を抽出する特徴量抽出ステップと、
請求項１または２に記載のハッシュ関数生成方法により生成された１つ以上のハッシュ関数を用いて、前記特徴量を１つ以上のバイナリ値に変換する変換ステップと
を有することを特徴とするハッシュ値生成方法。
【請求項４】
コンテンツデータをバイナリ値に変換するハッシュ関数生成装置であって、
コンテンツデータ及び該コンテンツデータのメディア種別から、該コンテンツデータをＤ（Ｄ＞０、Ｄはメディア種別により定まる）次元実数値ベクトルとして表現する特徴量を抽出する特徴量抽出手段と、
前記メディア種別ごとに前記特徴量について、その近傍の相対的幾何関係を求める幾何関係算出手段と、
前記メディア種別が異なる複数のコンテンツデータの内容の関係性を示す関係指示子と前記相対的幾何関係とに基づいて、ハッシュ関数を表現するパラメータを決定して前記ハッシュ関数を生成する関数生成手段と
を備えることを特徴とするハッシュ関数生成装置。
【請求項５】
前記ハッシュ関数は、前記特徴量と前記パラメータとの内積によって規定されることを特徴とする請求項４に記載のハッシュ関数生成装置。
【請求項６】
コンテンツデータ及び該コンテンツデータのメディア種別から、該コンテンツデータをＤ（Ｄ＞０、Ｄはメディア種別により定まる）次元実数値ベクトルとして表現する特徴量を抽出する特徴量抽出手段と、
請求項４または５に記載のハッシュ関数生成装置により生成された１つ以上のハッシュ関数を用いて、前記特徴量を１つ以上のバイナリ値に変換する変換手段と
を備えることを特徴とするハッシュ値生成装置。
【請求項７】
コンピュータに、請求項１または２記載のハッシュ関数生成方法を実行させるためのハッシュ関数生成プログラム。
【請求項８】
コンピュータに、請求項３記載のハッシュ値生成方法を実行させるためのハッシュ値生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大量のメディアコンテンツの中から、類似コンテンツを発見するためのハッシュ関数生成方法、ハッシュ値生成方法、ハッシュ関数生成装置、ハッシュ値生成装置、ハッシュ関数生成プログラム及びハッシュ値生成プログラムに関する。
【背景技術】
【０００２】
通信環境やコンピュータ、分散処理基盤技術の高度・高品質化により、ネットワークに流通するメディアコンテンツ（画像・映像・音声・文書等）の数は膨大なものとなっている。例えば、ある検索エンジンがインデクシングしているウェブページの数は数兆にのぼるといわれている。また、あるサイトでは、日々３．５億の画像がアップロードされていると報告されており、また、あるサイトでは、１分当たり６４時間分の映像が新規に公開されているとの報告もある。
【０００３】
このような膨大な量のメディアコンテンツは、利用者にとっては豊富な情報源となる一方で、閲覧したいコンテンツに素早くアクセスすることがますます困難になっているという課題ももたらしている。このような流れの中、閲覧・視聴したいコンテンツを効率的に探し出すためのメディア解析技術への要望がますます高まってきている。
【０００４】
コンテンツの解析においては、類似したコンテンツの発見が重要な役割を果たす。例えば、コンテンツを分類する場合は、同じようなコンテンツは同じカテゴリに分類する。あるいは検索の場合、あるコンテンツをクエリとして与えたとき、このコンテンツに類似したコンテンツを検索することが基本的な要件となる。そのほか、コンテンツ推薦においても利用者がこれまでに閲覧した／閲覧しているコンテンツと類似したコンテンツを発見してこれを推薦するし、コンテンツ要約の場合においても、類似したコンテンツを提示することは冗長であるため、これを発見して省くような処理が必要となる。
【０００５】
ここで、類似コンテンツを発見する典型的な手続きについて説明する。まず、コンテンツをある特徴量によって表現する。次に、特徴量同士の近さを測ることで類似度を計算し、この類似度に基づいて類似コンテンツを発見する。単純な例を挙げれば、コンテンツが画像や映像であれば、画像（映像フレーム）の色ヒストグラムを特徴量としてその類似度を測ることができる。コンテンツが文書であれば、単語の出現頻度をヒストグラム化したもの（Ｂａｇ−ｏｆ−Ｗｏｒｄｓヒストグラムなどと呼ぶ）を特徴量として類似度を測ることができる。いうまでもなく、仮にコンテンツの数が１０００あれば、１０００のコンテンツそれぞれに対して類似度を計算し、結果類似度の高いコンテンツを類似コンテンツとして拾い上げる必要がある。
【０００６】
しかしながら、前述のように、膨大な量のコンテンツを対象にした場合、下記２つの重要な課題がある。第１の課題は、計算時間とメモリを大量に消費することである。第２の課題は、同一種別の類似コンテンツのみが発見対象である。
【０００７】
通常、コンテンツの特徴量（ベクトル）の次元は高次元になることが多く、その類似度の計算には膨大な時間を要する。一般に、文書のＢａｇ−ｏｆ−Ｗｏｒｄｓヒストグラムの次元は、単語の種類（語彙）と同次元になる。画像の色ヒストグラムのような単純な特徴量であっても、一般に数百〜数千次元の実数値ベクトルとなるし、最近用いられるスパース表現やフィッシャーカーネルに基づく特徴表現では、数十万〜数百万次元のベクトルとなることもあり得る。さらに、全てのコンテンツの組に対してその類似度を計算する必要があるため、どのような類似度計算手段を用いようとも、特徴量の次元がＤ、コンテンツがＮ個あったとするとＯ（ＤＮ）の計算量を要する。また、即時検索を実行するためには、特徴量あるいはその類似度をメモリに蓄積しておくことが好ましいが、これを行うためにはＯ（Ｎ２）のメモリが必要となる。このように、億を超えるオーダのコンテンツを扱う必要がある昨今においては、非現実的な時間とメモリを要するのである。
【０００８】
さらに、昨今のメディアコンテンツは、単一種別のみで流通することは稀である。例えば、通常ウェブページには文書や画像が混在しているし、映像や音声が付加されていることも少なくない。これらのコンテンツは、メディアの種別こそ異なるものの、あるコンテキストに即しながら相互に関連した内容を持つことが多い。然るに、例えば文書に類似した文書だけでなく、関連する画像や映像、音声に至るまで、メディアの隔たり無く類似したコンテンツを発見できることが好ましい。
【０００９】
しかしながら、これは上記通常のやり方では不可能である。コンテンツの類似度を測るためには、コンテンツを表現する特徴量が同一である必要があるが、メディアの種別が異なる以上、同一の特徴量で記述することが不可能であるためである。検索エンジンなどにおいては、キーワード検索によって画像や映像などを検索することができるが、これは「同一ウェブページに共起している単語と画像なら類似している」といったごく単純な仮定に基づくものであって、文書の内容と画像の内容を評価しているわけではない。
【００１０】
このような問題を解決するために、従来からいくつかの発明がなされている。特許文献１に開示されている技術では、コンテンツの特徴量と、異なる２つのコンテンツを関連付けるべきか否かを示す関連情報（正解データ）に基づいてハッシュ関数を求め、このハッシュ関数を基に特徴量を低ビットなハッシュ値に変換する。
【００１１】
また、非特許文献１に開示されている技術では、近接する任意の２つのコンテンツ（特徴量）において、元の特徴量の類似度と衝突確率が等しくなるようなハッシュ関数群を生成する。典型的な類似度としてコサイン類似度を考えており、その場合のハッシュ関数生成の基本的な手続きは、特徴量空間にランダムな超平面を複数生成することによる（ｒａｎｄｏｍ  ｐｒｏｊｅｃｔｉｏｎと呼ばれる）。各超平面のどちら側に特徴量が存在するかによって特徴量をハッシュ化し、全てのコンテンツ間で類似度を求めることなく、近似的に類似コンテンツを発見することができる。
【００１２】
また、非特許文献２に開示されている技術は、特徴量の分布を捉え、その分布に対して最適なハッシュ値を構成する。具体的には、特徴量空間における多様体構造を捉え、その多様体構造を最適に保存するバイナリ空間（ハッシュ空間）への非線形な埋め込みを求めることで、元の高次元な特徴量を、低ビットなハッシュ値に変換する。そのハッシュ値の類似性を評価することで、高速な類似コンテンツ発見を実現することができる。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２０１３−６８８８４号公報
【非特許文献】
【００１４】
【非特許文献１】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）などで構成されているものとしてもよい。
【００３０】
コンテンツデータベース２には、少なくともコンテンツ自体、あるいは、当該データの所在を一意に示すアドレスが格納されている。コンテンツは、例えば、文書であれば文書ファイル、画像であれば画像ファイル、音であれば音ファイル、映像であれば映像ファイルなどであり、好ましくは、コンテンツデータベース２には、各コンテンツのメディア種別とそれ自体を一意に識別可能な識別子が含まれているものとする。
【００３１】
さらに、コンテンツデータベース２には、複数種別のメディアが含まれているものとし（例えば、画像と文書等）、相互の関係を示す関係指示子が対応づけられているものとする。関係指示子は、異種メディアコンテンツ間の内容の関係性を表すものであり、最も単純には関係がある２つのコンテンツの識別子を記述したものでよい。内容の関連性を決定する手段は問わず、人手によって与えるもの、機械的に与えられるもの、あるいはその双方によるもの、いずれでもよい。
【００３２】
例えば、人手により与える場合には、例えば、“画像３”の識別子を持つ３番目の画像と、“文書８”の識別子を持つ８番目の文書の内容が、人手で見て相互に関連している場合には、関係指示子として｛“画像３”、“文書８”｝のペアを指し示す情報をコンテンツデータベース２に格納しておけばよい。
【００３３】
また、機械的に与えられる場合の例として、例えばＷｅｂページから画像を収集するような場合があげられる。最も単純には、同一Ｗｅｂページ内にある画像と文書は関連していると見做し、人手の場合と同様の関係指示子を与えてもよい。あるいは、Ｗｅｂページ上周辺にある画像と文書同士は関連していると見做し、関係指示子を与えてもよい。機械的に与えられる場合、人手をかけることなく関係指示子が得られるというメリットがある。
【００３４】
ここで、関係指示子は、必ずしもコンテンツデータベース２に格納されている全てのコンテンツに対して与えられている必要はなく、その一部でよい。その他、メタデータとして、例えばコンテンツの内容を表現するもの（コンテンツのタイトル、概要文、キーワード）、コンテンツのフォーマットに関するもの（コンテンツのデータ量、サムネイル等のサイズ）などを含んでいてもよい。
【００３５】
情報処理装置１が備える各部およびコンテンツデータベース２は、演算処理装置、記憶装置等を備えたコンピュータやサーバ等により構成して、各部の処理がプログラムによって実行されるものとしてもよい。このプログラムは情報処理装置１が備える記憶装置に記憶されており、磁気ディスク、光ディスク、半導体メモリ等の記録媒体に記録することも、ネットワークを通して提供することも可能である。もちろん、その他いかなる構成要素についても、単一のコンピュータやサーバによって実現しなければならないものではなく、ネットワークによって接続された複数のコンピュータに分散して実現してもよい。
【００３６】
次に、図１に示す情報処理装置１の構成について説明する。入力部１１は、コンテンツデータベース２から各コンテンツのコンテンツデータ、メディア種別を入力し特徴抽出部１２に出力するとともに、関係識別子を入力しハッシュ関数生成部１３に対して出力する。特徴抽出部１２は、入力部１１から入力したコンテンツデータを解析し、メディア種別ごとにコンテンツを特徴的に表す特徴量を抽出する。特徴量は、ハッシュ値生成処理時にはハッシュ値生成部１５に、ハッシュ関数生成処理時にはハッシュ関数生成部１３に対して出力する。
【００３７】
ハッシュ関数生成部１３は、特徴抽出部１２から出力された特徴量とメディア種別、入力部１１から入力した関係指示子に基づいて、各メディア種別ごとに１つ以上のハッシュ関数を生成してハッシュ関数記憶部１４に記憶する。ハッシュ関数記憶部１４は、ハッシュ関数生成部１３が生成した１つ以上のハッシュ関数を、そのメディア種別ごとに記憶する。
【００３８】
ハッシュ値生成部１５は、特徴抽出部１２から出力された特徴量を、ハッシュ関数記憶部１４に格納されたそのメディア種別に対応する１つ以上のハッシュ関数に基づいて、複数のバイナリ値であるハッシュ値に変換し、出力部１６に出力する。出力部１６は、ハッシュ値生成部１５で求めたハッシュ値をコンテンツデータベース２に出力して記憶する。
【００３９】
次に、図１に示す情報処理装置１の処理動作を説明する。図１に示す情報処理装置１は、ハッシュ関数を生成するハッシュ関数生成処理と、特徴量をハッシュ化するハッシュ値生成処理を実行する。以下、これら２つの処理について説明する。
【００４０】
最初に、図２を参照して、ハッシュ関数生成処理について説明する。図２は、ハッシュ関数生成処理の動作を示すフローチャートである。ハッシュ関数生成処理は、実際にコンテンツデータをハッシュ化する前に、少なくとも１度実施しておく処理である。
【００４１】
まず、入力部１１は、コンテンツデータベース２からコンテンツデータ、メディア種別を入力し特徴抽出部１２に出力し、また、関係指示子を入力してハッシュ関数生成部１３に対して出力する（ステップＳ２０１）。続いて、特徴抽出部１２は、コンテンツデータに対して、そのメディア種別に即した特徴量を抽出してハッシュ関数生成部１３に出力する（ステップＳ２０２）。
【００４２】
次に、ハッシュ関数生成部１３は、特徴量とメディア種別、および関係指示子に基づいて１つ以上のハッシュ関数を生成し、ハッシュ関数記憶部１４に記憶する（ステップＳ２０３）。
【００４３】
以上の処理により、コンテンツデータベース２に格納されたコンテンツデータと関係指示子からハッシュ関数を生成することができる。なお、特徴量の抽出、ハッシュ関数の生成の詳細については後述する。
【００４４】
次に、図３を参照して、ハッシュ値生成処理の動作を説明する。図３は、ハッシュ値生成処理の動作を示すフローチャートである。ハッシュ値生成処理は、ハッシュ関数記憶部１４に格納されたハッシュ関数を用いてコンテンツの特徴量をハッシュ化する処理である。
【００４５】
まず、入力部１１は、コンテンツデータベース２あるいは外部から直接コンテンツデータおよびメディア種別を入力し特徴抽出部１２に対して出力する（ステップＳ３０１）。続いて、特徴抽出部１２は、コンテンツデータに対して、そのメディア種別に即した特徴量を抽出してハッシュ値生成部１５に出力する（ステップＳ３０２）。
【００４６】
次に、ハッシュ値生成部１５は、ハッシュ関数記憶部１４に記憶されたそのコンテンツのメディア種別に対応する１つ以上のハッシュ関数を用いて、特徴量をハッシュ値に変換し、出力部１６に出力する（ステップＳ３０３）。本実施形態の一例においては、メディアの種別によらず、１つのハッシュ関数につき、特徴量は１ビットに変換されるので、ハッシュ関数記憶部１４にＢ個のハッシュ関数が格納されている場合は、特徴量はＢビットのハッシュ値に変換される。
【００４７】
最後に、出力部１６は、ハッシュ値をコンテンツデータベース２に記憶する（ステップＳ３０４）。
【００４８】
以上の処理により、入力したコンテンツに対して、メディアの種別によらずハッシュ値を求めることができる。
【００４９】
次に、各処理の詳細を説明する。始めに、特徴量の抽出について説明する。特徴量を抽出する処理は、コンテンツのメディア種別に依存する。例えば、コンテンツが文書であるか、画像であるか、音であるか、映像であるかによって、抽出するまたは抽出できる特徴量は変化する。ここで、各メディア種別に対してどのような特徴量を抽出するかは、本発明の要件として重要ではなく、一般に知られた公知の特徴抽出処理を用いてよい。具体的には、あるコンテンツから抽出された次元を持つ数値データ（スカラー又はベクトル）であれば、あらゆる特徴量に対して有効である。したがって、ここでは、本実施形態の一例に適する、各種コンテンツに対する特徴抽出処理の一例を説明する。
【００５０】
コンテンツが文書である場合には、文書中に出現する単語の出現頻度を用いることができる。例えば、公知の形態素解析を用いて、名詞、形容詞等に相当する単語ごとに、その出現頻度を計数すればよい。この場合、各文書は単語種別と同じだけの次元を持つベクトルとして表現される。
【００５１】
コンテンツが画像である場合には、例えば、明るさ特徴、色特徴、テクスチャ特徴、コンセプト特徴、景観特徴などを抽出する。明るさ特徴は、ＨＳＶ色空間におけるＶ値を数え上げることで、ヒストグラムとして抽出することができる。この場合、各画像はＶ値の量子化数（例えば、１６ビット量子化であれば２５６諧調）と同数の次元を持つベクトルとして表現される。
【００５２】
色特徴は、Ｌ＊ａ＊ｂ＊色空間における各軸（Ｌ＊、ａ＊、ｂ＊）の値を数え上げることで、ヒストグラムとして抽出することができる。各軸のヒストグラムのビンの数は、例えば、Ｌ＊に対して４、ａ＊に対して１４、ｂ＊に対して１４などとすればよく、この場合、３軸の合計ビン数は、４×１４×１４＝７８４、すなわち７８４次元のベクトルとなる。
【００５３】
テクスチャ特徴としては、濃淡ヒストグラムの統計量（コントラスト）やパワースペクトルなどを求めればよい。あるいは、局所特徴量を用いると、色や動きなどと同様、ヒストグラムの形式で抽出することができるようになるため好適である。局所特徴としては、例えば下記の参考文献１に記載されるＳＩＦＴ（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
【００６６】
望ましくは、後者の方法を採用する。映像区間分割処理の結果として、区間の開始点（開始時刻）と終了点（終了時刻）が得られるが、この時刻毎に別々の特徴量として扱えばよい。
【００６７】
以上のように抽出した特徴量は、一つあるいは複数を利用してもよいし、その他の公知の特徴量を用いるものとしてもよい。
【００６８】
次に、ハッシュ関数の生成について説明する。あるメディア種別ｍのコンテンツｉから抽出された特徴量をｘｍ、ｉ∈ＲＤｍと表す。メディア種別ｍのコンテンツの特徴量次元はＤｍである。このとき、図２に示すステップＳ１０３では、メディア種別ｍに対して、ｈｍ、ｋ：ＲＤｍ→｛−１，１｝となるハッシュ関数の集合を求める。｛−１，１｝と｛０，１｝は情報量という観点で本質的に差異がないことに注意すれば、各ｈによって、特徴量ｘｍ、ｉ∈ＲＤｍは０または１を取るバイナリ値に写像されるから、メディア種別ｍの特徴量ｘｍ、ｉは、ハッシュ関数集合Ｈｍ＝｛ｈｍ、１、ｈｍ、２、・・・、ｈｍ、Ｂ｝によってＢ個のバイナリ値、すなわち、Ｂビットのハッシュ値に変換されることになる。
【００６９】
本発明の目的は、このハッシュ値によって、異なるメディア種別であっても類似度の計測を可能にしたうえ、さらに時間のかかる類似度計算を省略することである。したがって、ここで生成するハッシュ関数と、それにより生成されるハッシュ値は、次の２つの性質を持つ。
（Ａ）元のメディア種別ｍにおいて、元の空間ＲＤｍでの類似度を表すハッシュ値へと変換する。すなわち、高い類似度を持つコンテンツほど、ハッシュ値の距離（ハミング距離）が近くなること。
（Ｂ）異なるメディア種別の特徴量のうち、関係指示子が関連性を示すペアについては、ハッシュ値の距離が近くなること。
【００７０】
本実施形態の一例では、ハッシュ関数として（１）式で示す線形関数に基づくハッシュ関数を適用する。
【数１】
2015079102.tif 000003
ここで、ｓｉｇｎ（ｘ）は符号関数であり、ｘ≧０のとき１、ｘ＜０のとき−１をとる関数である。また、ｗｍ、ｋ∈ＲＤｋ、ｂｍ、ｋ∈Ｒのパラメータである。このハッシュ関数において、未知のパラメータはｗｍ、ｋとｂｍ、ｋの二つだけである。
【００７１】
ここで、仮にｘｍ、ｉ（ｉ＝１，２，・・・，Ｎｍ）が平均０に正規化されているとき、ｂｍ、ｋ＝０としても一般性を失わない。ｘｍ、ｉを０に正規化するには、ｘｍ、ｉの平均を、各ｘｍ、ｉから減算すればよいのであり、これはｘｍ、ｉ∈ＲＤｋにおいて常に可能であることから、ｂｍ、ｋ＝０と決定できる。したがって、以降、ｘｍ，ｉの平均は０に正規化されているとし、（１）式を（２）式のように定義しなおして説明する。
【数２】
2015079102.tif 000004
【００７２】
このハッシュ関数の定義によれば、関数φｍ、ｋ内にあるパラメータｗｍ、ｋを定めることで、ハッシュ関数を一意に定めることができる。したがって、本ハッシュ関数生成処理の目的は、このｗｍ、ｋ（ｋ＝  １，２，…，Ｂ）を求めることである。
【００７３】
ここで、（２）式のように規定されるハッシュ関数の意味は、幾何的には図４を用いて説明できる。図４には、特徴量空間ＲＤｍ上に、メディア種別ｍの各コンテンツ（ｉ＝１，２，・・・，Ｎｍ）から抽出された特徴量ｘｍ，ｉ（ｉ＝１，２，・・・，Ｎｍ）が分布している。図４では、便宜上２次元のように図示しているが、実際にはＤｍ次元の空間である。ここでハッシュ関数を構成するφｍ、ｋ（ｘ）は、この特徴量空間上の原点を通る直線（実際はＤｍ−１次元の超平面）を表す。ｈｍ、ｋ（ｘ）は、本質的には符号関数であるから、その値は、特徴量の点がこの直線φｍ、ｋ（ｘ）のどちら側にあるかによって、１または０をとる。すなわち、（２）式によって定義されるハッシュ関数４１は、特徴量空間を直線によって１と０の２つの領域に分割する関数である。ここで、ｗｍ、ｋはこの直線の傾きに対応し、ｗｍ、ｋが変化すれば、分割する角度が変化することになる。
【００７４】
前述した２つの性質、すなわち、
（Ａ）元のメディア種別ｍにおいて、元の空間ＲＤｍでの類似度を表すハッシュ値へと変換する。すなわち、高い類似度を持つコンテンツほど、ハッシュ値の距離（ハミング距離）が近くなること。
（Ｂ）異なるメディア種別の特徴量のうち、関係指示子が関連性を示すペアについては、ハッシュ値の距離が近くなること。
に合うハッシュ関数となるように、ｗｍ、ｋを求めるには、
（Ａ）各メディア種別において、類似したコンテンツ群が、先の図４の例における直線の片側に集まるように直線を引き（すなわち、ｗｍ、ｋを決める）、
（Ｂ）なおかつ、異種メディア種別において、関係指示子が示す関連するコンテンツ同士が、ハッシュ値の空間において近い値を持つようすればよい。
【００７５】
まず、（Ａ）の性質を満たすための方法を説明する。メディアコンテンツにおいては、前述した特徴量の種別によらず、類似したコンテンツ同士の特徴量の分布は滑らかな多様体構造を形成することがよく知られている。多様体構造とは、簡単に言えば滑らかな変化である。分かりやすく図５を用いて説明すると、各特徴量は大まかに、曲線５１と曲線５２の滑らかに変化する２本の曲線上に分布しており、同じ曲線上の点同士は互いに類似していることが多い。この図でいうところの、白丸（○）と黒丸（●）で表されている特徴量は、同色であれば互いに類似したコンテンツの特徴量となる。
【００７６】
この知見に基づけば、これらの類似したコンテンツ群が直線の片側に集まるように直線を引けばよい。この観点に基づけば、図６に示す直線の内、直線６１のような直線は好ましくなく、２群の間を通る直線６２のような直線を規定するハッシュ関数のパラメータｗｍ、ｋを求めればよいことになる。
【００７７】
続いて、（Ｂ）の性質を満たすための方法を説明する。例えば、メディア種別が画像と文書である場合について、図７を用いて説明する。図７の例では、画像特徴量を丸、文書特徴量を三角で表している。仮に、それぞれの画像と文書の特徴量空間において、性質（Ａ）を満たすように、すなわち、多様体構造を分離するような直線７１、７２がそれぞれ得られているとし、さらに、関係指示子によって破線７３〜７６で示す関係が得られているとする。このとき、直線７１、７２によって分離されている画像および文書特徴量のうち、関係指示子によって示される関係のある画像／文書特徴量同士が、互いに同じハッシュ値を持つようにハッシュ関数のパラメータｗｍ、ｋを求めればよいことになる。例えば、図７の例では白丸と白三角（△）、黒丸と黒三角（▲）がそれぞれ同じハッシュ値を持てばよい。
【００７８】
以上示した２つの方法に基づき、本実施形態の一例では、前述の（Ａ）と（Ｂ）の２つの性質を満たすパラメータｗｍ、ｋを求める。本実施形態の一例では、次の２つの手続きによってｗｍ、ｋを求める。第１の手続きは、メディア種別ｍごとに、その特徴量空間における多様体構造を捉える。第２の手続きは、各メディア種別の多様体構造、および、関係指示子が示す異種メディア種別間の関係に基づいて、ｗｍ、ｋを求める。
【００７９】
以下、それぞれの手続きについて詳述する。第１の手続きは、メディア種別によらず同じであり、各メディア種別に対してそれぞれ同じ処理を適用すればよい。例えば、非特許文献３に記載の公知の方法を用いることができる。以下、非特許文献３に記載の方法を説明する。
【００８０】
多様体とは、大まかに言えば滑らかな図形であり、言い換えれば局所的に見ればユークリッドな空間とみなせる。例えば、図５に示すような曲線のように、いくつかの直線の集まりとして近似されるようなものであると解釈してもよい。このことは、多様体とは局所的に見れば線形で近似される構造を持つことを表しているのであり、言い換えれば、多様体上任意の点は、同じ多様体上にあるいくつかの近傍点に基づく、近傍の相対的幾何関係によって表現できることを意味している。
【００８１】
非特許文献３では、次の問題を解くことによって多様体を発見する。
【数３】
2015079102.tif 000005
ここで、第一項は特徴量ｘｍ，ｉを、そのユークリッド空間上での近傍集合ε（ｘｍ，ｉ）に含まれる特徴量インデクスに対応する特徴量の集合｛ｘｍ、ｊ｜ｊ∈ε（ｘｍ，ｉ）｝によって線形結合で表したときの誤差であり、ｓｍ，ｉｊはその際の結合重みである。第二項は、結合重みのベクトルｓｍ，ｉ＝｛ｓｍ，ｉ１，・・・，ｓｍ，ｉＮ｝に対して、その要素がスパースであることを要請する、すなわち、ベクトル中のいくつかの限られた要素にのみ非ゼロの値を持つように正則化するスパース項であり、ｖｍ，ｉはｘｍ，ｉに近いほど小さな値を持つような定数を要素として持つベクトルである。例えば、（４）式のようにしてもよい。
【数４】
2015079102.tif 000006
【００８２】
つまるところ、この問題を解くことによってある特徴量ｘｍ，ｉをできる限り少数の近傍点の線形結合として表した場合の結合重みｓｍ，ｉを求めることができるが、これは多様体を表現するいくつかの近傍点と、その相対的幾何関係（結合重み）を表しているに他ならない。この問題は、公知のスパース問題ソルバによって解決することができる。例えば、ＳＰＡＭＳなどのオープンソースソフトウェアを用いてもよい。
【００８３】
なお、近傍集合ε（ｘｍ，ｉ）は、いかなる方法を用いて求めてもよい。最も単純な方法は、各特徴量ｘｍ、ｊに対して、その他全ての点ｘｍ、ｊ≠ｉとのユークリッド距離を求め、近いものからｔ個を近傍集合とするものである。ｔは任意の正の整数でよく、例えばｔ＝１０などとしてもよい。
【００８４】
しかし、この方法では１つの特徴量に対してその他全ての特徴量との距離を求める必要があるため、未知の特徴量ｘｍ、ｊに対して近傍集合を求めようとすると、Ｏ（Ｎ）の計算時間が掛かるという問題がある。したがって、高速に計算できる手法を用いることが好ましい。例えば、クラスタリングやハッシュによる方法を用いることができる。
【００８５】
クラスタリングを用いる場合、例えばｋ−ｍｅａｎｓ法などにより全Ｎ個の特徴量をクラスタリングし、Ｌ個のクラスタ（Ｌ＜＜Ｎ）と、各クラスタを代表するＬ個の代表特徴量（クラスタ中心）を求めておく。Ｌの値は任意の正の整数としてよいが、例えば、Ｌ＝１２８などとすればよい。この結果、各特徴量がどのクラスタに属するか、および、当該クラスタの代表特徴量を得ることができる。この前提のもと、下記の手続きによって、未知の特徴量ｘｉに対する近傍集合を得ることができる。まず、特徴量ｘｍ、ｊに対して、Ｌ個の代表特徴量との距離を計算し、最も近いクラスタを特定する；次に、当該クラスタに属する全ての特徴量を、近傍集合ε（ｘｍ，ｉ）として得る。この処理に必要な計算時間はＯ（Ｌ）であり、Ｌ＜＜Ｎであることから、単純な方法に比べて高速に近傍集合を得ることができる。
【００８６】
また、ハッシュを用いる場合、例えば非特許文献１などの方法によって、全Ｎ個の特徴量に対するハッシュ値を求めておく。この前提のもと、未知の特徴量ｘｍ、ｊのハッシュ値を求め、これと同一またはハミング距離上近い値を持つハッシュ値を持つ（すなわち、同一あるいはそれに近接するバケットに属する）全ての特徴量を、近傍集合ε（ｘｍ，ｉ）として得ればよい。この処理に必要な計算時間は参照するバケットの数に依存するが、一般に参照バケット数はＮよりも小さいことから、こちらも高速に近傍集合を得ることができる。なお、非特許文献１の方法によるハッシュ値は、ユークリッド空間上のコサイン類似度を保存するようなハッシュ関数であり、ユークリッド空間上の角度が近ければ近いほどハッシュ値が衝突する確率が高くなる。一方で、本実施形態により生成されるハッシュ値は、ユークリッド空間上ではなく、多様体上の近さ（測地線距離に基づく近さ）を保存するようなハッシュ関数であり、特徴量の分布をより正確に捉えたハッシュ値を生成できることに注意されたい。以上の手続きを、対象とするすべてのメディア種別に対して適用すればよい。
【００８７】
次に、第２の手続きについて説明する。手続き１によって得た各メディア種別のｓｍ，ｉ（ｉ＝１，２，・・・，Ｎｍ）と同様の近傍の相対的幾何関係を持つハッシュ空間（埋め込み）を求めることによって、ｗｍ、ｋを求める。
【００８８】
簡単のため、メディア種別は２つ、例えば画像と文書とし、ｍ＝１のとき画像、ｍ＝２のとき文書を表すものとする。もちろん、いかに説明する実施形態の一例は、その他のメディア種別、あるいは、メディア種別が３以上の場合に対しても同様に適用できるものである。
【００８９】
具体的には、下記の問題を解決する。便宜上、画像特徴量ｘ１，ｉ（ｉ＝１，２，・・・，Ｎ１）および文書特徴量ｘ２，ｉ（ｉ＝１，２，・・・，Ｎ２）を並べた行列Ｘ１＝｛ｘ１，１，・・・，ｘ１、Ｎ１｝、Ｘ２＝｛ｘ２，１，・・・，ｘ２、Ｎ２｝を定義する。さらに、画像特徴量のためのハッシュ関数のパラメータｗ１，ｋ（ｋ＝  １，２，…，Ｂ）および文書特徴量のためのハッシュ関数のパラメータｗ２，ｋ（ｋ＝  １，２，…，Ｂ）を並べた行列Ｗ１＝｛ｗ１、１，・・・，ｗ１、Ｂ｝、Ｗ２＝｛ｗ２、１，・・・，ｗ２、Ｂ｝を定義する。
【００９０】
具体的には、以下の問題を解く。
【数５】
2015079102.tif 000007
ここで、Ｓｍはそれぞれｓｍ，ｉｊを要素に持つ行列、Ｒｍｌはメディア種別ｍとメディア種別ｌとの関係指示子により指示される関係を示す行列である。例えば、ＲｍｌをＮｍ×Ｎｌの行列とし、関係指示子により関係があるとされている要素のみ１、そうでないところを０とすればよい。
【００９１】
Ｊｍ（Ｗｍ；Ｘｍ，Ｓｍ）は、それぞれメディア種別ｍにおける特徴量空間の多様体構造を保存するための関数であり、例えば、（６）式のように定義することができる。
【数６】
2015079102.tif 000008
この式は、元々の特徴量空間における多様体構造、すなわち、ｓｍ，ｉｊとその線形結合を、ハッシュ関数
【数７】
2015079102.tif 000009
によって変換された先においてもそのまま再構築することを要請するものであり、（３）式とも相似性を持つものである。すなわち、（５）式に代入されたとき、ハッシュ値に変換された先でも元の空間と同様の多様体構造を持つようにＷｍを決定することができる。
【００９２】
また、Ｊｍｌ（Ｗｍ、Ｗｌ；Ｘｍ，Ｘｌ，Ｒｍｌ）は、メディア種別ｍとｌの間の関係指示子が示す関係を保存するための関数であり、例えば、（８）式のように定義することができる。
【数８】
2015079102.tif 000010
この式では、関係指示子によって関係があるとされた特徴量ペアを、変換先で同一の値にするよう要請するものである。上記式は、Ｒｍｌのｉｊ要素が１であった場合、メディア種別ｍのｉ番目の特徴量ｘｍ，ｉとメディア種別ｌのｊ番目の特徴量ｘｌ，ｊのペアについて、それぞれ（７）式によって与えられるハッシュ関数により変換された値の距離を表している。したがって、これを（５）式に代入することで、できる限りその距離を小さくするようにＷｍを決定することができる。
【００９３】
以上のように定義された（６）式および（８）式を、（５）式に代入し、代数変形を適用すると、次の（９）式の問題が得られる。
【数９】
2015079102.tif 000011
ここで、
【数１０】
2015079102.tif 000012
である。上記（９）式は、ＷｍおよびＷｌ、すなわちＰについて凸であるので、Ｗについて微分して極値を取ることで、次の一般化固有値問題に帰着される。
【数１１】
2015079102.tif 000013
このような一般化固有値問題の解は、反復法などの公知の方法によって求めることができる。
【００９４】
このようにして求めたＷｍおよびＷｌは、元の空間における多様体構造を最適に保存し、かつ、関係指示子によって関係があるとされる異種メディアを可能な限り同じハッシュ値に変換するものである。したがって、目的としていた２つの性質（Ａ）、（Ｂ）を最適に満たすようなＷｍおよびＷｌを得ることができる。
【００９５】
新たなハッシュ値を生成する際には、（７）式を計算した後、その符号を調べればよいだけである。この計算に必要となるメモリ量は、ｗｍ，ｋとｘｍ，ｉそれぞれを格納するに必要なメモリ量のみであり、仮に、特徴量が浮動小数点表示であり、次元Ｄが１００の場合８００Ｂ程度、仮に次元Ｄが１０００００程度になったとしても高々８００ＫＢと、現存する一般的なコンピュータにおいても極めて容易に蓄積できるメモリ量に抑えることができる。したがって、この方法によって、多様体の構造を捉えることによる高い精度でありながら、高速かつ省メモリなハッシュ値生成が可能である。
【００９６】
上記の処理詳細によって生成されたハッシュ関数、すなわち、具体的には、全てのメディア種別における｛Ｗｍ｝は、ハッシュ関数記憶部１４に記憶される。
【００９７】
次に、第２の手続きの変形例を説明する。前述した第２の手続きでは、（２）式の形をとるハッシュ関数の場合において、そのパラメータｗｋ  （ｋ＝１，２，…，Ｂ）を求める方法について述べたが、本発明で扱えるハッシュ関数は、何もこの形に限るものではなく、別の形式をとるハッシュ関数であっても、同様にそのパラメータを決定することができる。
【００９８】
例えば、次のようなハッシュ関数も扱うことができる。
【数１２】
2015079102.tif 000014
ここで、αｍ，ｋ，ｔはパラメータ、κ（ｘｍ，ｔ，ｘｍ）はカーネル関数である。カーネル関数は、
【数１３】
2015079102.tif 000015
のような関数であり、さらにＮｍ個の特徴量｛ｘｍ，１，・・・，ｘｍ，Ｎｍ｝に対して、
【数１４】
2015079102.tif 000016
および、任意の実数αｉ、αｊに対して
【数１５】
2015079102.tif 000017
を満たすような任意の関数である。このような関数は無数に存在するが、例を挙げれば、
【数１６】
2015079102.tif 000018
【数１７】
2015079102.tif 000019
【数１８】
2015079102.tif 000020
などが存在する。ただし、β、γは正の実数値パラメータ、ｐは整数パラメータであり、適宜決定してよい。
【００９９】
（１２）式において、ｂｍ，ｋは
【数１９】
2015079102.tif 000021
すなわち平均値で定められる定数なので、（１２）式は、
【数２０】
2015079102.tif 000022
と、内積の形に変換できる。ただし、
【数２１】
2015079102.tif 000023
である。ここで、Ｔはハッシュ関数を定める定数である。上記ハッシュ関数、具体的にはカーネルベクトル写像κｍ（ｘｍ）は、Ｔ個の特徴量によって定められるが、ＴはＴ＜Ｎｍの範囲で任意の値に決めてよい。例えば、Ｔ＝３００等として、全特徴量｛ｘｍ，１，・・・，ｘｍ，Ｎｍ｝の中からランダムにＴ個選んでもよいし、あるいはＫ−ｍｅａｎｓなどのクラスタリング法を用いて選ばれた代表ベクトルとしてもよい。
【０１００】
このように定義されたハッシュ関数は、カーネル関数の形で定義された非線形写像を扱うことができる。したがって、非線形な関数、すなわち、直線だけでなく、曲線も扱える点で、（６）式によるハッシュ関数よりも柔軟な表現が可能であるという利点を持つ。
【０１０１】
以下、（２０）式の形式をとるハッシュ関数において、そのパラメータαｍ，ｋを決定する方法を説明する。ここでも、画像特徴量（ｍ＝１）と文書特徴量（ｍ＝２）の場合を考え、便宜上、κ１（ｘ１，ｉ）（ｉ＝  １，２，…，Ｎ１）およびκ２（ｘ２，ｉ）（ｉ＝  １，２，…，Ｎ２）を並べた行列Κ１＝｛κ１（ｘ１，１），・・・，κ１（ｘ１、Ｎ）｝、Κ＝｛κ２（ｘ２，１），・・・，κ２（ｘ２，Ｎ）｝を定義する。さらに、画像特徴量のためのハッシュ関数のパラメータα１，ｋ（ｋ＝  １，２，…，Ｂ）および文書特徴量のためのハッシュ関数のパラメータα２，ｋ（ｋ＝  １，２，…，Ｂ）を並べた行列Α１＝｛α１，１，・・・，α１，Ｂ｝、Α２＝｛α２，１，・・・，α２，Ｂ｝を定義する。
【０１０２】
具体的には、（２）式で定義されるハッシュ関数で言うところの（５）式に相当する、以下の問題を解く。
【数２２】
2015079102.tif 000024
Ｊｍ（Αｍ；Κｍ，Ｓｍ）およびＪｍｌ（Αｍ、Αｌ；Κｍ，Κｌ，Ｒｍｌ）は、（６）式、（８）式と同様の理由で、例えば、下記のように定義することができる。
【数２３】
2015079102.tif 000025
【０１０３】
（２２）式を、（５）式に代入し、代数変形を適用すると、次の（２４）式の問題が得られる。
【数２４】
2015079102.tif 000026
ここで、
【数２５】
2015079102.tif 000027
である。この問題は、（９）式の問題と等価であるため、全く同様の手続きで解くことができる。
【０１０４】
上記の処理詳細によって生成されたハッシュ関数、すなわち、具体的には、全てのメディア種別における｛Αｍ｝およびカーネル関数κｍ（ｘｍ）は、ハッシュ関数記憶部１４に記憶される。
【０１０５】
次に、ハッシュ値生成処理について説明する。前述のハッシュ関数生成処理が済んでいれば、ハッシュ関数記憶部１４には、メディア種別ごとにＢ組のハッシュ関数が格納されている。これを用いれば、（２）式にしたがって、特徴量で表現された任意のコンテンツを、Ｂビット以下のハッシュ値で表現することができる。
【０１０６】
次に、前述の処理により生成したハッシュ関数によって、類似コンテンツを高速かつ省メモリに検索する実施形態の一例について説明する。例えば、コンテンツデータベース２に、Ｎ１個の画像特徴量Ｘ１＝｛ｘ１，１，・・・，ｘ１，Ｎ１｝とＮ２個の文書特徴量Ｘ２＝｛ｘ２，１，・・・，ｘ２，Ｎ２｝とが格納されているとし、これらの特徴量は全て（２）式に基づいてハッシュ値Ｙ１＝｛ｙ１，１，・・・，ｙ１，Ｎ１｝およびＹ２＝｛ｙ２，１，・・・，ｙ２，Ｎ２｝に変換されているものとする。このとき、目的はＸ１、Ｘ２いずれにも含まれない特徴量ｘ１，ｑあるいはｘ２，ｑに対して類似するコンテンツをＸ１およびＸ２の中から発見することである。
【０１０７】
まず、（２）式に基づいて、特徴量ｘ１，ｑあるいはｘ２，ｑをハッシュ値ｙ１，ｑあるいはｙ２，ｑに変換しておく。最も単純には、図８に示すハッシュテーブルを用いる方法がある。まず、コンテンツデータベース２に登録されているハッシュ値Ｙ１およびＹ２によって、図８に示すようなハッシュテーブルを構成する。このテーブルでは、あるハッシュ値と、そのハッシュ値に変換された特徴量（コンテンツ識別子）を対応づけて格納しており、ハッシュ値が与えられた際に、それと同一のハッシュ値を取るコンテンツを即時発見することができる。ここで、本発明により生成されるハッシュ値においては、メディア種別に寄らず、関連するもの、類似するものを同一のハッシュ値に変換できることが特徴である。すなわち、例えば、ハッシュ値「００００」を指定した場合、それに対応づけられた画像と文書（画像１、文書３・・・）を、メディア種別に寄らずに直ちに発見できるのである。同様に、このハッシュテーブルを利用すれば、ハッシュ値ｙ１，ｑあるいはｙ２，ｑに対応したコンテンツを即座に発見することが可能となる。
【０１０８】
この方法によれば、コンテンツデータベース２に登録された画像、文書の数Ｎ１、Ｎ２に寄らず、ほぼ一定の時間で高速に、かつ、元の特徴量をメモリに保持する必要がないため、省メモリに類似コンテンツを発見できるという利点がある。
【０１０９】
また、別の方法として、ハミング距離による距離計算を利用することができる。すなわち、ハッシュ値ｙ１，ｑあるいはｙ２，ｑと、Ｙ１およびＹ２に含まれるＮ１＋Ｎ２個のハッシュ値との距離を計算し、距離の小さいものを類似コンテンツとして得るものである。ハッシュ値はバイナリであるため、距離計算は例えばハミング距離で計算することができるが、ハミング距離はＸＯＲ（排他的論理和）とｐｏｐｃｎｔ演算（すなわち、バイナリ列のうち、１となっているビットの数を数える演算）のみで計算できること、および、ハッシュ値は通常少数のバイナリ値で表現できることから、元の特徴量で距離計算する場合に比べ、遥かに高速に演算できる。
【０１１０】
以上説明したように、本実施形態によれば、メディア種別ごとの特徴量空間の多様体構造を捉え、かつ異種メディア種別間の関係指示子により指示された関係を保存するようにパラメトリックなハッシュ関数を生成することによって、相互に異なる種別でありながら、関連するコンテンツ同士を、高速かつ省メモリでありながらも高精度に発見することができる。
【０１１１】
なお、本実施形態の主要な特徴を満たす範囲内において、任意の用途と構成を取ることができることは言うまでもない。例えば、ハッシュ関数生成部とハッシュ値生成部は分離可能であり、例えば、上記例における装置構成図１以外にも、サーバ―クライアント装置構成を取ることもできる。図９に、類似コンテンツ検索を実施する場合について、その一例を示す。
【０１１２】
同図に示すサーバ装置８は、入力部８１、特徴抽出部８２、ハッシュ関数生成部８３、ハッシュ関数記憶部８４、ハッシュ値生成部８５、および出力部８６を備える。また、同図に示すクライアント装置１０は、入力部１０１、特徴抽出部１０２、ハッシュ値生成部１０３、ハッシュ関数記憶部１０４、および出力部１０５を備える。
【０１１３】
ここで、サーバ装置８とクライアント装置１０において、共通する構成要素（入力部、特徴抽出部、ハッシュ関数記憶部、ハッシュ値生成部）はそれぞれ同一の機能を有するように構成し、また、図１に記載した各構成要素と同一名称のものは、図１の場合と同一の機能を有するものとしてよい。さらに、ハッシュ値生成部の内容は、それぞれ何らかの通信手段で適宜同期されているものとする。
【０１１４】
図９に示す装置構成における処理動作は下記の通りである。まずサーバ装置８は、上記説明した処理と同様の処理を以って、適宜ハッシュ関数を生成、クライアント装置のそれと同期する。さらに、コンテンツデータベース９中のコンテンツに対して、やはり上記説明した処理と同様の処理を以って、ハッシュ値を生成、コンテンツデータベース９に格納しておく。
【０１１５】
一方、クライアント装置１０は、利用者からの検索要求、すなわち、新規コンテンツの入力部１０１への入力を受け付けたら、当該コンテンツに対してハッシュ値を生成クライアント装置で生成された新たなコンテンツに対するハッシュ値を生成し、出力部１０５からサーバ装置８の入力部８１へと当該ハッシュ値を出力する。
【０１１６】
クライアント装置１０からハッシュ値を受けた場合、サーバ装置８は、当該ハッシュ値を用いて、コンテンツデータベース９へと検索を掛け、ハッシュ値に基づいて類似コンテンツを発見し、その結果をクライアント装置１０へと出力する。
【０１１７】
最後に、クライアント装置１０は、サーバ装置８より受け取った検索結果を利用者に出力する。
【０１１８】
このように構成することで、サーバ装置８でハッシュ関数生成処理を実施し、クライアント装置ではハッシュ値生成処理のみを実施するように構成することができる。
【０１１９】
この構成を取るメリットを説明する。一般に、クライアント装置（ＰＣ，携帯端末等）は、サーバ装置と比較して演算能力に乏しいため、ハッシュ関数生成のように演算量が比較的多い処理には適さない場合がある。この構成にすれば、ハッシュ関数生成処理は演算能力の高いサーバ装置で適宜実施し、クライアント装置では演算量の少ないハッシュ値生成処理だけを実施することができる。さらに、通常、ネットワークを介した通信によってデータ容量の多い情報を伝送する場合、伝送時間が掛かるという問題があるが、当該構成によって、伝送するのは情報量の小さいハッシュ値のみでよくなり、検索に対する即応性を高めることができる。
【０１２０】
以上説明したように、前述したハッシュ関数とハッシュ値を用いることにより、画像同士、文書同士などといった、同一のメディア種別のコンテンツのみならず、画像から文書、画像から音声などのように、関連する異なる種別のメディアコンテンツ同士を、高速かつ省メモリでありながらも高精度に発見することが可能になる。この構成により、省メモリであることから、例えば、メモリ量の小さいモバイル端末（スマートフォンやタブレット）での利用も可能となる。また、高速であることから、実時間性の要求される利用に対しても対応可能である。これらの効果を活用した具体的な利用シーンとして、街中を歩いているときに気になる場所や商品をモバイル端末で写真撮影し、類似した場所・商品を検索することが可能になる。
【０１２１】
前述した実施形態におけるハッシュ関数生成部、ハッシュ値生成部をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＰＬＤ（Programmable Logic Device）やＦＰＧＡ（Field Programmable Gate Array）等のハードウェアを用いて実現されるものであってもよい。
【０１２２】
以上、図面を参照して本発明の実施の形態を説明してきたが、上記実施の形態は本発明の例示に過ぎず、本発明が上記実施の形態に限定されるものではないことは明らかである。したがって、本発明の技術思想及び範囲を逸脱しない範囲で構成要素の追加、省略、置換、その他の変更を行ってもよい。
【産業上の利用可能性】
【０１２３】
画像から文書、画像から音声などのように、関連する異なる種別のメディアコンテンツ同士を、高速かつ省メモリでありながらも高精度に発見するためのハッシュ関数の生成及びハッシュ値の生成を行うことが不可欠な用途に適用できる。
【符号の説明】
【０１２４】
１・・・情報処理装置、１１、８１、１０１・・・入力部、１２、８２、１０２・・・特徴抽出部、１３、８３・・・ハッシュ関数生成部、１４、８４、１０４・・・ハッシュ関数記憶部、１５、８５、１０３・・・ハッシュ値生成部、１６、８６、１０５・・・出力部、２・・・コンテンツデータベース、８・・・サーバ装置、９・・・コンテンツデータベース
【図１】
2015079102.tif 000028
【図２】
2015079102.tif 000029
【図３】
2015079102.tif 000030
【図４】
2015079102.tif 000031
【図５】
2015079102.tif 000032
【図６】
2015079102.tif 000033
【図７】
2015079102.tif 000034
【図８】
2015079102.tif 000035
【図９】
2015079102.tif 000036