コンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラム
【課題】大量のマルチメディアコンテンツから、高速、省メモリでありながら、高精度で類似するコンテンツを発見することのできるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供すること。
【解決手段】複数のコンテンツｉの各特徴量ｘｉを特徴量空間Ｒｄ上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線を求め、特徴点が当該直線によって２分割されたいずれの空間側にあるかに基づいてコンテンツｉをバイナリ値に変換するハッシュ関数ｈｋを生成する。
【解決手段】複数のコンテンツｉの各特徴量ｘｉを特徴量空間Ｒｄ上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線を求め、特徴点が当該直線によって２分割されたいずれの空間側にあるかに基づいてコンテンツｉをバイナリ値に変換するハッシュ関数ｈｋを生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大量のマルチメディアコンテンツから類似するコンテンツを検索する際に利用されるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムに関する。
【背景技術】
【０００２】
通信網、ストレージ、分散環境の高度化により、オンラインで流通するマルチメディアコンテンツの数は膨大な量となっている。
【０００３】
例えば、ある検索エンジンが検索可能としているウェブページ数は数十億とも数兆ともいわれている。集合知による事典として有名なWikipediaでは、３５０万以上の記事が閲覧可能となっている。
【０００４】
あるソーシャルメディアサイトでは、毎月２５億の画像がアップロードされているとの報告があり、また、ある動画共有サイトでは、１分当たり４８時間分の映像が新規に公開され続けているとの報告がある。
【０００５】
このような膨大な量のマルチメディアコンテンツは、視聴者にとって豊富な選択肢となる一方で、視聴・閲覧したいコンテンツに素早くアクセスしたり、内容を一覧して素早く把握したりするなどといったことが困難になっているという深刻な課題ももたらしている。
【０００６】
したがって、現在、閲覧・視聴したいコンテンツを効率的に探し出すためのコンテンツ検索・推薦や、コンテンツ内の冗長な部分を省いて短くまとめるコンテンツ要約への要望がますます高まってきている。
【０００７】
このようなコンテンツ検索、推薦、要約を実現する上で、最も基本的かつ重要な機能の１つは、類似したコンテンツ、あるいはコンテンツの一部を発見する機能である。
【０００８】
例えば、コンテンツを検索する場合、あるコンテンツをクエリとして与えたとき、このコンテンツに類似したコンテンツを検索することが基本的な要件となる。推薦の場合においても同様に、利用者がこれまでに閲覧した又は閲覧しているコンテンツと類似したコンテンツを発見し、これを推薦する。また、要約の場合においても、類似したコンテンツを提示することは冗長であるため、これを発見して省くような機能が必要となる。
【０００９】
ここで、よく知られた類似コンテンツの発見手法を説明しておく。コンテンツ、あるいはその一部が、ある特徴量によって表現されているとする。このとき、特徴量同士の近さを測ることで類似度を計算し、この類似度に基づいて類似コンテンツを発見する。
【００１０】
単純な例を挙げれば、コンテンツが画像であれば、画像の色ヒストグラムを特徴量としてその類似度を測ることができる。コンテンツが文書であれば、単語の出現頻度をヒストグラム化したもの（Bag-of-Wordsヒストグラムなどと呼ぶ）を特徴量として類似度を測ることができる。
【００１１】
いうまでもなく、仮にコンテンツの数が１万であれば、その１万のコンテンツそれぞれに対して類似度を計算し、その結果、類似度の高いコンテンツを類似コンテンツとして拾い上げる必要がある。
【００１２】
しかしながら、前述のように、大量のコンテンツを対象にしようとした場合、（１）計算時間がかかる、（２）メモリを大量に消費する、という２つの重要な課題がある。
【００１３】
通常、コンテンツの特徴量は多次元になることが多く、その類似度の計算には時間を要する。一般に、文書のBag-of-Wordsヒストグラムの次元は、単語の種類（語彙）と同次元になるし、画像の色ヒストグラムは、一般に、数百〜数千次元の実数値ベクトルとなる。
【００１４】
さらに、全てのコンテンツの組に対してその類似度を計算する必要があるため、どのような類似度計算手段を用いたとしても、コンテンツがＮ個あったとするとＯ（Ｎ）の計算量を要する。
【００１５】
また、即時検索を実行するには、特徴量あるいはその類似度をメモリに蓄積しておくことが好ましいが、これを行うためにはＯ（Ｎ２）のメモリが必要となる。
【００１６】
このような課題に対して、コンテンツを低容量な特徴量で表現し、効率的に類似コンテンツを発見する技術に関する取り組みがなされてきた。この課題を解決するため、従来いくつかの発明がなされ、開示されてきている。
【００１７】
特許文献１に開示されている技術では、コンテンツの特徴量を、主成分分析により次元圧縮して低次元化し、この低次元な特徴量同士の距離を測ることで、特徴量の低容量化、高速化を図っている。
【００１８】
非特許文献１に開示されている技術では、近接する任意の２つのコンテンツ（特徴量）において、元の特徴量の類似度と衝突確率が等しくなるようなハッシュ関数群を生成する。
【００１９】
典型的な類似度としてコサイン類似度を考えており、その場合におけるハッシュ関数生成の基本的な手法は、特徴量空間にランダムな超平面を複数生成することによる（random projectionと呼ばれる）。
【００２０】
各超平面のどちら側に特徴量が存在するかによって特徴量をハッシュ化し、全てのコンテンツ間で類似度を求めることなく、近似的に類似コンテンツを発見することができる。
【００２１】
非特許文献２に開示されている技術は、非特許文献１が考えるコサイン類似度とは異なり、Shift-Invariant Kernelによる類似度を考えるハッシュ関数生成技術である。
【００２２】
基本的な手続きこそ非特許文献１と似ており、やはりランダムな写像を生成し、これに基づいて特徴量をハッシュ化する。一方で、その性質は非特許文献１とは異なり、非特許文献１が「元の特徴量の類似度と衝突確率が等しくなるようなハッシュ関数群を生成する」のに対して、非特許文献２では、ハッシュ値間のハミング距離が、Shift-Invariant Kernelによる類似度に依存したバウンド（上界・下界）によって抑えられるようなハッシュ関数を生成する。
【００２３】
なお、上記非特許文献１、２の双方とも、ハッシュ関数あたり１ｂｉｔのバイナリ値を割り当てることになる。すなわち、ハッシュ関数の数をＢとすると、ハッシュ値はＢｂｉｔとなる。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】特許第３７３０１７９号公報
【非特許文献】
【００２５】
【非特許文献１】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
【非特許文献２】M. Raginsky、S. Lazebnik、“Locality-Sensitive Binary Codes from Shift-Invariant Kernels”、Advances in Neural Information Processing Systems 22、2009年、p.1509-1517
【発明の概要】
【発明が解決しようとする課題】
【００２６】
上記の特許文献１に記載の技術は、特徴量を圧縮表現するものの、圧縮された特徴量間の類似度をユークリッド距離で求める必要があるため、大幅な計算時間の削減を実現できなかった。
【００２７】
非特許文献１、２に開示されている技術では、ハッシュ関数（超平面）の生成はランダムであるため、コンテンツの類似度を反映するようなハッシュ関数を生成するには、ハッシュ数を十分に大きく取り、多数のハッシュ関数を生成する必要があった。
【００２８】
本発明は、この課題を鑑みてなされたものであり、大量のマルチメディアコンテンツから、高速、省メモリでありながら、高精度で類似するコンテンツを発見することのできるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供することを課題とする。
【課題を解決するための手段】
【００２９】
第１の本発明に係るコンテンツ変換方法は、コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換方法において、コンピュータにより、記憶手段からコンテンツを読み出して、複数のコンテンツの各特徴量をそれぞれ抽出する抽出ステップと、前記各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、前記特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいて前記コンテンツをバイナリ値に変換するハッシュ関数を生成する生成ステップと、を有することを特徴とする。
【００３０】
第２の本発明に係るコンテンツ変換方法は、前記生成ステップが、前記２つの群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いたｔｒａｃｅ｛ｗＴ（Ｓｂ−Ｓｗ）ｗ｝（但し、ｗＴｗ＝１）の演算値が最大となるｗの値を傾きとして前記図形を求めることを特徴とする。
【００３１】
第３の本発明に係るコンテンツ変換方法は、前記生成ステップが、前記ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように前記特徴点の分布状態を変化させることを特徴とする。
【００３２】
第４の本発明に係るコンテンツ変換方法は、前記ハッシュ関数を１つ以上用いて前記コンテンツを１つ以上のバイナリ値に変換する変換ステップを更に有することを特徴とする。
【００３３】
第５の本発明に係るコンテンツ変換装置は、コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換装置において、記憶手段からコンテンツを読み出して、複数のコンテンツの各特徴量をそれぞれ抽出する抽出手段と、前記各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、前記特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいて前記コンテンツをバイナリ値に変換するハッシュ関数を生成する生成手段と、を有することを特徴とする。
【００３４】
第６の本発明に係るコンテンツ変換装置は、前記生成手段が、前記２つの群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いたｔｒａｃｅ｛ｗＴ（Ｓｂ−Ｓｗ）ｗ｝（但し、ｗＴｗ＝１）の演算値が最大となるｗの値を傾きとして前記図形を求めることを特徴とする。
【００３５】
第７の本発明に係るコンテンツ変換装置は、前記生成手段が、前記ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように前記特徴点の分布状態を変化させることを特徴とする。
【００３６】
第８の本発明に係るコンテンツ変換プログラムは、第１から第４の発明におけるコンテンツ変換方法をコンピュータに実行させることを特徴とする。
【００３７】
以上より、本発明によれば、複数のコンテンツの各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいてコンテンツをバイナリ値に変換するハッシュ関数を生成するため、揺らぎに頑健なハッシュ関数を生成できることから、結果として、大量のマルチメディアコンテンツから、高速、省メモリでありながら、高精度で類似するコンテンツを発見することのできるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供できる。
【００３８】
また、本発明によれば、ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように特徴点の分布状態を変化させるため、互いに相関の低いハッシュ関数を生成できることから、結果として、より少ないハッシュ関数の数（ビット数）で、高精度な類似コンテンツ検索を実施することができるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供できる。
【発明の効果】
【００３９】
本発明によれば、大量のマルチメディアコンテンツから、高速、省メモリでありながら、高精度で類似するコンテンツを発見することのできるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供できる。
【図面の簡単な説明】
【００４０】
【図１】情報処理装置の機能ブロック構成例を示す図である。
【図２】ハッシュ関数生成処理例の流れを示すフローチャートである。
【図３】ハッシュ化処理例の流れを示すフローチャートである。
【図４】ハッシュ関数の幾何学的な意味を説明する図である。
【図５】類似する２群を分割するハッシュ関数を説明する図である。
【図６】類似検索精度の比較結果を示す図である。
【発明を実施するための形態】
【００４１】
以下、本発明の実施の形態について図面を用いて説明する。
【００４２】
〔情報処理装置の構成〕
図１は、本実施の形態に係る情報処理装置の機能ブロック構成を示す図である。同図に示す情報処理装置１は、コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換装置であって、入力部１１と、特徴抽出部１２と、ハッシュ関数生成部１３と、ハッシュ関数記憶部１４と、ハッシュ化部１５と、出力部１６とで主に構成される。
【００４３】
情報処理装置１は、通信手段を介してコンテンツデータベース２に接続され、入力部１１と出力部１６を介して相互に情報通信し、コンテンツデータベース２に登録されたコンテンツに基づいてハッシュ関数を生成するハッシュ関数生成処理と、生成したハッシュ関数を用いてコンテンツを１つ以上のバイナリ値に変換するハッシュ化処理を行う。
【００４４】
情報処理装置１が備える各部は、演算処理装置や記憶装置等を備えたコンピュータにより構成して、各部の処理がプログラムによって実行されるものとしてもよい。このプログラムは、情報処理装置１が備える記憶装置に記憶されており、磁気ディスク、光ディスク、半導体メモリ等の記録媒体に記録することも、通信ネットワークを通して提供することも可能である。
【００４５】
コンテンツデータベース２は、情報処理装置１の内部にあっても外部にあっても構わない。また、通信手段は、任意の公知のものを用いることができるが、本実施の形態においては、外部にあるものとして、インターネット、ＴＣＰ／ＩＰにより通信するよう接続されているものとする。
【００４６】
また、コンテンツデータベース２は、いわゆるＲＤＢＭＳ（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、L.V. Gool、“SURF: Speeded Up Robust Features”、Lecture Notes in Computer Science、vol. 3951、pp.404-417、2006年
【００７８】
これらによって抽出される局所特徴は、例えば、１２８次元の実数値ベクトルとなる。このベクトルを、予め学習して生成しておいた符号長を参照して、符号に変換し、その符号の数を数え上げることでヒストグラムを生成することができる。この場合、ヒストグラムのビンの数は、符号長の符号数と一致する。符号数は任意のものを用いてよいが、例えば、５１２あるいは１０２４などとしてもよい。
【００７９】
コンセプト特徴とは、画像中に含まれる物体や、画像が捉えているイベントのことである。任意のものを用いてよいが、例を挙げれば、「海」、「山」、「ボール」などのようなものである。もし、ある画像に「海」が映っていた場合、その画像は「海」コンセプトに帰属する画像であるという。
【００８０】
その画像が、各コンセプトに帰属するか否かは、コンセプト識別器を用いて判断することができる。通常、コンセプト識別器はコンセプト毎に一つ用意され、画像の特徴量を入力として、その画像があるコンセプトに帰属しているか否かを帰属レベルとして出力する。
【００８１】
コンセプト識別器は、予め学習して獲得しておくものであり、決められた画像特徴、例えば、先に述べた局所特徴と、予め人手によって、その画像がどのコンセプトに帰属しているかを表した正解ラベルとの関係を学習することによって獲得する。
【００８２】
学習器としては、例えば、サポートベクターマシンなどを用いればよい。コンセプト特徴は、各コンセプトへの帰属レベルをまとめてベクトルとして表現することで得ることができる。
【００８３】
景観特徴は、画像の風景や場面を表現した特徴量である。例えば、下記の参考文献３に記載のＧＩＳＴ記述子を用いることができる。
［参考文献３］A. Oliva、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年
【００８４】
コンテンツが音である場合には、音高特徴、音圧特徴、スペクトル特徴、リズム特徴、発話特徴、音楽特徴、音イベント特徴などを抽出する。
【００８５】
音高特徴は、例えば、ピッチを取るものとすればよく、下記の参考文献４に記載される方法などを用いて抽出することができる。
［参考文献４］古井貞熙、“ディジタル音声処理, ４. ９ピッチ抽出”、pp.57-59、1985年
【００８６】
音圧特徴としては、音声波形データの振幅値を用いるものとしてもよいし、短時間パワースペクトルを求め、任意の帯域の平均パワーを計算して用いるものとしてもよい。
【００８７】
スペクトル特徴としては、例えば、メル尺度ケプストラム係数（ＭＦＣＣ：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、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、G. Suzuki、“Structured Video Computing”、IEEE Multimedia、pp.34-43、1994年
【００９３】
望ましくは、後者の方法を採用する。映像区間分割処理の結果として、区間の開始点（開始時刻）と終了点（終了時刻）が得られるが、この時刻毎に別々の特徴量として扱えばよい。
【００９４】
以上のように抽出した特徴量は、一つあるいは複数を利用してもよいし、その他の公知の特徴量を用いるものとしてもよい。
【００９５】
〔ハッシュ関数の生成処理〕
次に、ハッシュ関数の生成処理について説明する。コンテンツｉ（ｉ＝１，２，…，Ｎ）から抽出された特徴量をｘｉとし、その特徴量ｘｉは特徴量空間Ｒｄに属するとする（ｘｉ∈Ｒｄ）。
【００９６】
このとき、前述したステップＳ１０３では、ｈ：Ｒｄ→｛０，１｝となるハッシュ関数ｈの集合を求める。特徴量ｘｉは、各ｈにより０または１をとるバイナリ値に写像されるので、ハッシュ関数集合Ｈ＝｛ｈ１，ｈ２，…，ｈＢ｝によってＢ個のバイナリ値、すなわち、Ｂｂｉｔのハッシュ値に変換されることになる。
【００９７】
本発明の目的は、このハッシュ値によって、時間のかかるコンテンツ間の類似度計算を省略可能にすることである。したがって、ハッシュ関数は、元の特徴量ｘｉ間の類似度ｓ：Ｒｄ×Ｒｄ→Ｒと関連したハッシュ値への写像であることが要請され、高い類似度を持つコンテンツほど、ハッシュ値の距離（ハミング距離）が近くなることが好ましい。
【００９８】
以下、ハッシュ関数の生成処理について詳述する。まず、ハッシュ関数生成部１３によって生成されるハッシュ関数ｈｋ（ｋ＝１，２，…，Ｂ）として、式（１），（２）に示すような線形関数に基づくハッシュ関数を考える。
【数１】
【数２】
【００９９】
ここで、ｓｉｇｎ（ｘ）は、ｗｋ∈Ｒｄ、ｂｋ∈Ｒをパラメータに持ち、ｘ≧０のとき１、ｘ＜０のとき−１をとる符号関数である。このような符号関数に基づくハッシュ関数であることから、コンテンツｉの特徴量ｘｉは、０または１のバイナリ値に変換されることになる。
【０１００】
このハッシュ関数ｈｋにおいて、未知のパラメータは、ｗｋとｂｋの二つだけである。ここで、仮に、コンテンツｉの特徴量ｘｉが平均０に正規化されているとき、ｂｋ＝０としても一般性を失うことはない。
【０１０１】
特徴量ｘｉを０に正規化するには、特徴量ｘｉの平均ｍを各特徴量ｘｉから減算すればよいのであり、これはｘｉ∈Ｒｄにおいて可能であることから、ｂｋ＝０と決定できる。
【０１０２】
したがって、以降、特徴量ｘｉの平均は０に正規化されているとし、式（２）を式（３）のように定義しなおして説明する。
【数３】
【０１０３】
式（１），（３）のハッシュ関数ｈｋにおいて、ｗｋ（ｋ＝１，２，…，Ｂ）のパラメータを定めることが、本ハッシュ関数の生成処理の目的となる。
【０１０４】
ここで、式（１），（３）のように表現されるハッシュ関数ｈｋの意味は、図４を用いて幾何的に説明できる。同図には、特徴量空間Ｒｄ上に、各コンテンツｉからそれぞれ抽出された特徴量ｘｉが特徴点として分布している。なお、同図では、便宜上２次元のように図示しているが、実際にはｄ次元の空間である。
【０１０５】
ここで、ハッシュ関数ｈｋを構成するφｋ（ｘｉ）は、この特徴量空間Ｒｄ上の原点を通る直線（実際は、（ｄ−１）次元の超平面）を表している。ハッシュ関数ｈｋ（ｘｉ）は、前述したように本質的には符号関数であるから、特徴量ｘｉを示す特徴点がこの直線φｋ（ｘｉ）によって２分割されたいずれの空間側にあるかによって、１または０をとる。
【０１０６】
すなわち、式（１），（３）によって定義されるハッシュ関数ｈｋ（ｘｉ）は、特徴量空間Ｒｄを直線φｋ（ｘｉ）によって１と０の２つの領域に分割する関数である。パラメータｗｋは、この直線φｋ（ｘｉ）の傾きに対応し、そのｗｋの値が変化すれば、分割する角度が変化することになる。
【０１０７】
したがい、本実施の形態によれば、コンテンツｉの特徴量ｘｉの分布に基づいて、パラメータｗｋを合理的に決定するハッシュ関数ｈｋの生成方法を提供することができる。以下、その原理と処理内容について説明する。
【０１０８】
前述した目的に合うハッシュ関数となるように、パラメータｗｋを求めるもっとも合理的な方法の一つは、類似したコンテンツ群が、先の図４の例における直線の片側に集まるように直線を引く（すなわち、パラメータｗｋを決める）ことである。
【０１０９】
ここで、わかりやすく図５を用いて説明する。同図では、白丸（○）で表されている特徴量ｘｉと、黒丸（●）で表されている特徴量ｘｉが存在する。また、これらとは別に、二重丸（◎）で表されている特徴量ｘｉが存在するが、ひとまずこれは無視してよい。
【０１１０】
今、白丸と黒丸で表されている特徴量ｘｉは、同色であれば互いに類似したコンテンツの特徴量であるとする。このとき、これらの類似したコンテンツ群が直線の片側に集まるように直線を引けばよい。このような直線は、２群の間を通るような直線であり、実際には無限に存在するが、例えば、直線５１のようなものがある。
【０１１１】
しかしながら、そのような直線５１は、頑健性（ロバスト性）に欠けるものである。ここで、先ほど無視した二重丸の特徴量ｘｉについて考える。これは、どちらかといえば白丸の群の周辺にあり、本来、白丸の群に属すべきコンテンツの特徴量であることが一目して見て取れる。
【０１１２】
しかしながら、この二重丸の特徴量ｘｉは、直線５１によって黒丸の群の方に分類されてしまっており、誤った分類を与えられてしまっている。もし、この二重丸の特徴量ｘｉを持つコンテンツｉがノイズによる揺らぎによって発生してしまった場合には、正しい分類を与えることができない。
【０１１３】
通常、コンテンツｉの特徴量ｘｉは揺らぎを伴って得られることが普通であるから、任意に引いた直線５１では、このような揺らぎに対して頑健性がなく、精度の低下を招いてしまう。
【０１１４】
これに対して本実施の形態では、無限にある直線の中から、頑健性の高い直線を求めることができる。頑健性の高い直線とは、マージンを最大化する直線、すなわち、それら両群のすべての特徴量ｘｉ（特徴点）からの垂線距離が等しくなるような直線である、直線５２を選べばよい。
【０１１５】
このようにして選ばれた直線５２は、互いの群から平等に最も遠い位置にある直線である。このため、両群の周辺に揺らいで発生するような二重丸のような特徴量ｘｉがあったとしても、正しい分類ができる。
【０１１６】
すなわち、ハッシュ関数生成部１３は、複数のコンテンツｉの各特徴量ｘｉを特徴量空間Ｒｄ上に特徴点として分布させて少なくとも２つの群に分類し、各郡の全ての特徴点からの垂直距離が等しい直線を計算し、特徴点が当該直線によって２分割されたいずれの空間側にあるかに基づいて、コンテンツｉをバイナリ値に変換するハッシュ関数を生成する。
【０１１７】
このような直線５２は、例えば、それら両群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いた式（４）の目的関数の演算値を最大化するｗの値を求めることにより、得ることができる。なお、ｔｒａｃｅ（トレース）とは、｛｝内のｎ次正方行列の対角成分の和を計算するものであり、線形代数学分野などにおいて一般に利用される。
【数４】
【０１１８】
なお、群間分散値Ｓｂ、郡内分散値Ｓｗは、それぞれ、式（５），（６）を用いて計算すればよい。ただし、ｍｊは群ｊ（ｊ＝０，１）の平均ベクトル、ｍは全体の平均ベクトル、Ｎｊは群ｊに属する特徴量ｘｉの数、Ｎは全体の特徴量ｘｉの数である。先に述べたように、全体の平均が０になるよう正規化されている場合、理論的にはｍ＝０となる。
【数５】
【数６】
【０１１９】
なお、式（４）を最大化するｗは、例えば、ラグランジュ未定乗数法によって、下記の固有値問題の解（固有ベクトル）として求めることができる。
【数７】
【０１２０】
この固有値問題を解いてｗを求める方法については、例えば、反復法など、種々の公知の方法を用いればよい。
【０１２１】
以上は、予めコンテンツｉの特徴量ｘｉがどちらの群に属しているかが既知である必要がある。以降、この情報を群指示情報と呼ぶ。一方で、現実の問題においては、群指示情報は未知である。つまり、このままでは現実にある多くの問題において、上記手法を取ることができない。
【０１２２】
そこで、本実施の形態では、群指示情報が未知の場合においても、同様のハッシュ関数を生成できる処理をとる。以降、この処理の一例について詳述する。
【０１２３】
まず、特徴量ｘｉ間の類似度を格納した類似度行列Ｖを求める。この類似度行列Ｖは、どのようなものでも構わないが、例えば、式（８）を利用して求めればよい。
【数８】
【０１２４】
また、その類似度行列Ｖに基づいて対角行列Ｄを計算する。
【数９】
【０１２５】
そして、式（４）に対して、群指示情報に依存しない正則化項を導入する。
【数１０】
【０１２６】
式（１０）の第２項がその正則化項であり、群間分散値Ｓｂや郡内分散値Ｓｗが含まれていないので、群指示情報がなくとも計算可能な項である。
【０１２７】
この式（１０）の演算値を最大化するｗの値は、ラグランジュ未定乗数法によって下記の固有値問題の解として求めることができる。なお、ηはパラメータであり、Ｘはハッシュ関数を求めた際の特徴量ｘｉの集合である。
【数１１】
【０１２８】
このような固有値問題の解は、前述の通り、反復法などの公知の方法によって計算できるので、仮に、群間分散値Ｓｂや郡内分散値Ｓｗがゼロ行列（要素がすべて０である行列）とすれば、群指示情報が全くなかったとしても、式（１１）を満たすｗを求めることができる。こうして求めたｗを、ｗ１とする。
【０１２９】
ハッシュ関数が１つ（すなわち、各特徴量ｘｉを１ビットのハッシュ値に変換する）でよければ、以上の手続きを以てハッシュ関数の生成処理を終了して構わない。
【０１３０】
しかしながら、通常は複数のハッシュ関数を用意し、複数ビットのハッシュ値に変換する。ここでは、以下の手続きにより、Ｂ個のハッシュ関数を用意するとして、ｗ１から順次ｗ２，ｗ３，…，ｗＢを求める。
【０１３１】
今、ｋ個のハッシュ関数ｈｋが求まっているとしたとき、ｋ＋１個目のハッシュ関数ｈｋ＋１を求めることを考える。本実施の形態では、ｋ個目までのハッシュ関数ｈｋを用いて、各特徴量ｘｉに疑似的な群指示情報を決定する。この付与方法は任意の方法で構わないが、例えば、ｋ個目のハッシュ関数ｈｋを用いて、次の規則に基づいて疑似群指示情報を与える。
【数１２】
【０１３２】
ここで、δはパラメータである。このように決定された疑似群指示情報を群指示情報であるとみなすことによって、式（５），（６）を用いて群間分散値Ｓｂや郡内分散値Ｓｗを計算することができ、式（１１）を満たすｗｋ＋１を得ることができる。
【０１３３】
基本的には、上記の処理をｋ＝１，２，…，Ｂと繰り返すことにより、ハッシュ関数ｈｋを逐次求めていけばよい。
【０１３４】
一方で、そのように「ｋ個目までのハッシュ関数ｈｋを用いて、各特徴量ｘｉに疑似的な群指示情報を決定する」場合、ｋ個目までのハッシュ関数ｈｋとｋ＋１個目のハッシュ関数ｈｋ＋１が互いに相関の高いもの（類似したもの）になってしまう確率が高く、非効率的である。
【０１３５】
そこで、本実施の形態では、より少ないハッシュ関数数でも高精度なハッシュ関数生成が実現できるよう、複数のハッシュ関数を生成する際に、互いに相関の低いハッシュ関数を生成する補正処理を導入する。
【０１３６】
例えば、ｋ個目のハッシュ関数ｈｋを用いて、ｋ個目のハッシュ関数ｈｋを求めた際の特徴量ｘｉの集合Ｘｋ＝｛ｘ１，ｘ２，…，ｘＮ｝を、次のように補正する。すなわち、ハッシュ関数間の相関度が低くなるように特徴点の分布状態を変化させる。
【数１３】
【０１３７】
この補正により、特徴量の分布から、ｗｋＴＸｋが示す方向成分が縮退されるので、その結果、既に得られているハッシュ関数と相関の低い特徴量分布へと変化する。この補正により、互いに相関の小さいハッシュ関数が生成されるようになる。
【０１３８】
以上の処理を繰り返すことにより、Ｂ個のハッシュ関数を得ることができる。処理の一例をまとめると、下記のように表現することができる。
【０１３９】
（手順１）最初に、ｋ＝１とし、Ｓｂｋ＝１＝０、Ｓｗｋ＝１＝０、Ｘｋ＝１＝Ｘとする。
【０１４０】
（手順２）次に、下記の固有値問題を解き、最大の固有値に対応する固有ベクトルをｗｋとする。
【数１４】
【０１４１】
（手順３）次に、式（１２）を用いて疑似群指示情報を計算する。
【０１４２】
（手順４）次に、ｋ＝Ｂなら処理を終了し、それ以外なら（手順５）に進む。なお、Ｂは任意に設定できる。
【０１４３】
（手順５）次に、式（１５）〜式（１７）を用いて、Ｓｂｋ＋１、Ｓｗｋ＋１、Ｘｋ＋１を求める。
【数１５】
【数１６】
【数１７】
【０１４４】
（手順６）（手順２）に戻る。
【０１４５】
上記の処理手続きによって生成されたハッシュ関数ｈｋ、すなわち、具体的には、パラメータｗｋ（ｋ＝１，２，…，Ｂ）は、ハッシュ関数記憶部１４に格納される。
【０１４６】
〔ハッシュ化処理〕
前述のハッシュ関数生成処理が済んでいれば、ハッシュ関数記憶部１４には、Ｂ個のハッシュ関数が格納されている。これを用いることにより、特徴量ｘｉで表現された任意のコンテンツｉを、Ｂビット以下のハッシュ値で表現することができる。
【０１４７】
〔実施例〕
ここでは、画像データベースを対象に、本実施の形態で実施したハッシュ値に基づいて類似画像を検索する一実施例について説明する。
【０１４８】
この実施例の画像データベースには、約２０，０００の画像が登録されている。各画像は、１０種類の異なるオブジェクトが示されている。この実施例では、同じオブジェクトを示す画像を、画像データベースに登録された画像の中から探し出すことを目的とした。
【０１４９】
従来の手法であれば、画像データベースに登録された全ての画像から特徴量を抽出しておき、閲覧画像の特徴量と類似度の高い画像データベース中の画像を推薦結果として出力する。
【０１５０】
一方、本実施例では、これをハッシュ値によって実施する。特徴量は任意のものを用いて構わないが、本実施例では画像を２８ピクセル×２８ピクセル＝７８４ピクセルに縮小し、各ピクセルの輝度値（２５６諧調）をそのまま用いた。
【０１５１】
すなわち、７８４次元の整数ベクトルであり、６，２７２ｂｉｔに相当する。これは予め、画像データベース中の全ての画像からこの特徴量を抽出しておく。さらに、本実施の形態によって、コンテンツの特徴量からハッシュ値を生成し、これを画像データベースに登録しておく。
【０１５２】
この実施例では、本実施の形態によって生成したハッシュ値による類似検索精度と、非特許文献１、２の技術によって生成したハッシュ値による類似検索精度とを比較した。図６に、ハッシュ値のビット数（ハッシュ関数の数）を変化させたときの検索精度を示す。
【０１５３】
いずれのビット数においても、本実施例の方が高い精度を得ている。本実施例によれば、通常１コンテンツあたり６，２７２ｂｉｔが必要であったところを、８ｂｉｔ〜３２ｂｉｔといった非常に小さい情報量で表現した場合であっても、高い精度を実現できている。このことから、本実施例による技術の高い効果が確認できる。
【０１５４】
以上説明したように、本実施の形態によれば、複数のコンテンツｉの各特徴量ｘｉを特徴量空間Ｒｄ上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線を求め、特徴点が当該直線によって２分割されたいずれの空間側にあるかに基づいてコンテンツｉをバイナリ値に変換するハッシュ関数ｈｋを生成する、より具体的には、特徴量ｘｉの群間距離と群内距離に基づいてハッシュ関数ｈｋを生成するので、揺らぎに頑健なハッシュ関数を生成することができることから、結果として、大量のマルチメディアコンテンツから、高速、省メモリでありながら、高精度で類似するコンテンツを発見することのできるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供できる。
【０１５５】
また、本実施の形態によれば、複数のハッシュ関数ｈｋを生成する際に、特徴量ｘｉの分布を逐次補正しながらハッシュ関数を生成するので、互いに相関の低いハッシュ関数を生成できることから、結果として、より少ないハッシュ関数の数（ビット数）で、高精度な類似コンテンツ検索を実施することができる。
【符号の説明】
【０１５６】
１…情報処理装置（コンテンツ変換装置）
２…コンテンツデータベース
１１…入力部
１２…特徴抽出部（抽出手段）
１３…ハッシュ関数生成部（生成手段）
１４…ハッシュ関数記憶部（記憶手段）
１５…ハッシュ化部
１６…出力部
Ｓ１０１〜Ｓ１０３、Ｓ２０１〜Ｓ２０４…ステップ
【技術分野】
【０００１】
本発明は、大量のマルチメディアコンテンツから類似するコンテンツを検索する際に利用されるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムに関する。
【背景技術】
【０００２】
通信網、ストレージ、分散環境の高度化により、オンラインで流通するマルチメディアコンテンツの数は膨大な量となっている。
【０００３】
例えば、ある検索エンジンが検索可能としているウェブページ数は数十億とも数兆ともいわれている。集合知による事典として有名なWikipediaでは、３５０万以上の記事が閲覧可能となっている。
【０００４】
あるソーシャルメディアサイトでは、毎月２５億の画像がアップロードされているとの報告があり、また、ある動画共有サイトでは、１分当たり４８時間分の映像が新規に公開され続けているとの報告がある。
【０００５】
このような膨大な量のマルチメディアコンテンツは、視聴者にとって豊富な選択肢となる一方で、視聴・閲覧したいコンテンツに素早くアクセスしたり、内容を一覧して素早く把握したりするなどといったことが困難になっているという深刻な課題ももたらしている。
【０００６】
したがって、現在、閲覧・視聴したいコンテンツを効率的に探し出すためのコンテンツ検索・推薦や、コンテンツ内の冗長な部分を省いて短くまとめるコンテンツ要約への要望がますます高まってきている。
【０００７】
このようなコンテンツ検索、推薦、要約を実現する上で、最も基本的かつ重要な機能の１つは、類似したコンテンツ、あるいはコンテンツの一部を発見する機能である。
【０００８】
例えば、コンテンツを検索する場合、あるコンテンツをクエリとして与えたとき、このコンテンツに類似したコンテンツを検索することが基本的な要件となる。推薦の場合においても同様に、利用者がこれまでに閲覧した又は閲覧しているコンテンツと類似したコンテンツを発見し、これを推薦する。また、要約の場合においても、類似したコンテンツを提示することは冗長であるため、これを発見して省くような機能が必要となる。
【０００９】
ここで、よく知られた類似コンテンツの発見手法を説明しておく。コンテンツ、あるいはその一部が、ある特徴量によって表現されているとする。このとき、特徴量同士の近さを測ることで類似度を計算し、この類似度に基づいて類似コンテンツを発見する。
【００１０】
単純な例を挙げれば、コンテンツが画像であれば、画像の色ヒストグラムを特徴量としてその類似度を測ることができる。コンテンツが文書であれば、単語の出現頻度をヒストグラム化したもの（Bag-of-Wordsヒストグラムなどと呼ぶ）を特徴量として類似度を測ることができる。
【００１１】
いうまでもなく、仮にコンテンツの数が１万であれば、その１万のコンテンツそれぞれに対して類似度を計算し、その結果、類似度の高いコンテンツを類似コンテンツとして拾い上げる必要がある。
【００１２】
しかしながら、前述のように、大量のコンテンツを対象にしようとした場合、（１）計算時間がかかる、（２）メモリを大量に消費する、という２つの重要な課題がある。
【００１３】
通常、コンテンツの特徴量は多次元になることが多く、その類似度の計算には時間を要する。一般に、文書のBag-of-Wordsヒストグラムの次元は、単語の種類（語彙）と同次元になるし、画像の色ヒストグラムは、一般に、数百〜数千次元の実数値ベクトルとなる。
【００１４】
さらに、全てのコンテンツの組に対してその類似度を計算する必要があるため、どのような類似度計算手段を用いたとしても、コンテンツがＮ個あったとするとＯ（Ｎ）の計算量を要する。
【００１５】
また、即時検索を実行するには、特徴量あるいはその類似度をメモリに蓄積しておくことが好ましいが、これを行うためにはＯ（Ｎ２）のメモリが必要となる。
【００１６】
このような課題に対して、コンテンツを低容量な特徴量で表現し、効率的に類似コンテンツを発見する技術に関する取り組みがなされてきた。この課題を解決するため、従来いくつかの発明がなされ、開示されてきている。
【００１７】
特許文献１に開示されている技術では、コンテンツの特徴量を、主成分分析により次元圧縮して低次元化し、この低次元な特徴量同士の距離を測ることで、特徴量の低容量化、高速化を図っている。
【００１８】
非特許文献１に開示されている技術では、近接する任意の２つのコンテンツ（特徴量）において、元の特徴量の類似度と衝突確率が等しくなるようなハッシュ関数群を生成する。
【００１９】
典型的な類似度としてコサイン類似度を考えており、その場合におけるハッシュ関数生成の基本的な手法は、特徴量空間にランダムな超平面を複数生成することによる（random projectionと呼ばれる）。
【００２０】
各超平面のどちら側に特徴量が存在するかによって特徴量をハッシュ化し、全てのコンテンツ間で類似度を求めることなく、近似的に類似コンテンツを発見することができる。
【００２１】
非特許文献２に開示されている技術は、非特許文献１が考えるコサイン類似度とは異なり、Shift-Invariant Kernelによる類似度を考えるハッシュ関数生成技術である。
【００２２】
基本的な手続きこそ非特許文献１と似ており、やはりランダムな写像を生成し、これに基づいて特徴量をハッシュ化する。一方で、その性質は非特許文献１とは異なり、非特許文献１が「元の特徴量の類似度と衝突確率が等しくなるようなハッシュ関数群を生成する」のに対して、非特許文献２では、ハッシュ値間のハミング距離が、Shift-Invariant Kernelによる類似度に依存したバウンド（上界・下界）によって抑えられるようなハッシュ関数を生成する。
【００２３】
なお、上記非特許文献１、２の双方とも、ハッシュ関数あたり１ｂｉｔのバイナリ値を割り当てることになる。すなわち、ハッシュ関数の数をＢとすると、ハッシュ値はＢｂｉｔとなる。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】特許第３７３０１７９号公報
【非特許文献】
【００２５】
【非特許文献１】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
【非特許文献２】M. Raginsky、S. Lazebnik、“Locality-Sensitive Binary Codes from Shift-Invariant Kernels”、Advances in Neural Information Processing Systems 22、2009年、p.1509-1517
【発明の概要】
【発明が解決しようとする課題】
【００２６】
上記の特許文献１に記載の技術は、特徴量を圧縮表現するものの、圧縮された特徴量間の類似度をユークリッド距離で求める必要があるため、大幅な計算時間の削減を実現できなかった。
【００２７】
非特許文献１、２に開示されている技術では、ハッシュ関数（超平面）の生成はランダムであるため、コンテンツの類似度を反映するようなハッシュ関数を生成するには、ハッシュ数を十分に大きく取り、多数のハッシュ関数を生成する必要があった。
【００２８】
本発明は、この課題を鑑みてなされたものであり、大量のマルチメディアコンテンツから、高速、省メモリでありながら、高精度で類似するコンテンツを発見することのできるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供することを課題とする。
【課題を解決するための手段】
【００２９】
第１の本発明に係るコンテンツ変換方法は、コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換方法において、コンピュータにより、記憶手段からコンテンツを読み出して、複数のコンテンツの各特徴量をそれぞれ抽出する抽出ステップと、前記各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、前記特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいて前記コンテンツをバイナリ値に変換するハッシュ関数を生成する生成ステップと、を有することを特徴とする。
【００３０】
第２の本発明に係るコンテンツ変換方法は、前記生成ステップが、前記２つの群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いたｔｒａｃｅ｛ｗＴ（Ｓｂ−Ｓｗ）ｗ｝（但し、ｗＴｗ＝１）の演算値が最大となるｗの値を傾きとして前記図形を求めることを特徴とする。
【００３１】
第３の本発明に係るコンテンツ変換方法は、前記生成ステップが、前記ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように前記特徴点の分布状態を変化させることを特徴とする。
【００３２】
第４の本発明に係るコンテンツ変換方法は、前記ハッシュ関数を１つ以上用いて前記コンテンツを１つ以上のバイナリ値に変換する変換ステップを更に有することを特徴とする。
【００３３】
第５の本発明に係るコンテンツ変換装置は、コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換装置において、記憶手段からコンテンツを読み出して、複数のコンテンツの各特徴量をそれぞれ抽出する抽出手段と、前記各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、前記特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいて前記コンテンツをバイナリ値に変換するハッシュ関数を生成する生成手段と、を有することを特徴とする。
【００３４】
第６の本発明に係るコンテンツ変換装置は、前記生成手段が、前記２つの群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いたｔｒａｃｅ｛ｗＴ（Ｓｂ−Ｓｗ）ｗ｝（但し、ｗＴｗ＝１）の演算値が最大となるｗの値を傾きとして前記図形を求めることを特徴とする。
【００３５】
第７の本発明に係るコンテンツ変換装置は、前記生成手段が、前記ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように前記特徴点の分布状態を変化させることを特徴とする。
【００３６】
第８の本発明に係るコンテンツ変換プログラムは、第１から第４の発明におけるコンテンツ変換方法をコンピュータに実行させることを特徴とする。
【００３７】
以上より、本発明によれば、複数のコンテンツの各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいてコンテンツをバイナリ値に変換するハッシュ関数を生成するため、揺らぎに頑健なハッシュ関数を生成できることから、結果として、大量のマルチメディアコンテンツから、高速、省メモリでありながら、高精度で類似するコンテンツを発見することのできるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供できる。
【００３８】
また、本発明によれば、ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように特徴点の分布状態を変化させるため、互いに相関の低いハッシュ関数を生成できることから、結果として、より少ないハッシュ関数の数（ビット数）で、高精度な類似コンテンツ検索を実施することができるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供できる。
【発明の効果】
【００３９】
本発明によれば、大量のマルチメディアコンテンツから、高速、省メモリでありながら、高精度で類似するコンテンツを発見することのできるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供できる。
【図面の簡単な説明】
【００４０】
【図１】情報処理装置の機能ブロック構成例を示す図である。
【図２】ハッシュ関数生成処理例の流れを示すフローチャートである。
【図３】ハッシュ化処理例の流れを示すフローチャートである。
【図４】ハッシュ関数の幾何学的な意味を説明する図である。
【図５】類似する２群を分割するハッシュ関数を説明する図である。
【図６】類似検索精度の比較結果を示す図である。
【発明を実施するための形態】
【００４１】
以下、本発明の実施の形態について図面を用いて説明する。
【００４２】
〔情報処理装置の構成〕
図１は、本実施の形態に係る情報処理装置の機能ブロック構成を示す図である。同図に示す情報処理装置１は、コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換装置であって、入力部１１と、特徴抽出部１２と、ハッシュ関数生成部１３と、ハッシュ関数記憶部１４と、ハッシュ化部１５と、出力部１６とで主に構成される。
【００４３】
情報処理装置１は、通信手段を介してコンテンツデータベース２に接続され、入力部１１と出力部１６を介して相互に情報通信し、コンテンツデータベース２に登録されたコンテンツに基づいてハッシュ関数を生成するハッシュ関数生成処理と、生成したハッシュ関数を用いてコンテンツを１つ以上のバイナリ値に変換するハッシュ化処理を行う。
【００４４】
情報処理装置１が備える各部は、演算処理装置や記憶装置等を備えたコンピュータにより構成して、各部の処理がプログラムによって実行されるものとしてもよい。このプログラムは、情報処理装置１が備える記憶装置に記憶されており、磁気ディスク、光ディスク、半導体メモリ等の記録媒体に記録することも、通信ネットワークを通して提供することも可能である。
【００４５】
コンテンツデータベース２は、情報処理装置１の内部にあっても外部にあっても構わない。また、通信手段は、任意の公知のものを用いることができるが、本実施の形態においては、外部にあるものとして、インターネット、ＴＣＰ／ＩＰにより通信するよう接続されているものとする。
【００４６】
また、コンテンツデータベース２は、いわゆるＲＤＢＭＳ（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、L.V. Gool、“SURF: Speeded Up Robust Features”、Lecture Notes in Computer Science、vol. 3951、pp.404-417、2006年
【００７８】
これらによって抽出される局所特徴は、例えば、１２８次元の実数値ベクトルとなる。このベクトルを、予め学習して生成しておいた符号長を参照して、符号に変換し、その符号の数を数え上げることでヒストグラムを生成することができる。この場合、ヒストグラムのビンの数は、符号長の符号数と一致する。符号数は任意のものを用いてよいが、例えば、５１２あるいは１０２４などとしてもよい。
【００７９】
コンセプト特徴とは、画像中に含まれる物体や、画像が捉えているイベントのことである。任意のものを用いてよいが、例を挙げれば、「海」、「山」、「ボール」などのようなものである。もし、ある画像に「海」が映っていた場合、その画像は「海」コンセプトに帰属する画像であるという。
【００８０】
その画像が、各コンセプトに帰属するか否かは、コンセプト識別器を用いて判断することができる。通常、コンセプト識別器はコンセプト毎に一つ用意され、画像の特徴量を入力として、その画像があるコンセプトに帰属しているか否かを帰属レベルとして出力する。
【００８１】
コンセプト識別器は、予め学習して獲得しておくものであり、決められた画像特徴、例えば、先に述べた局所特徴と、予め人手によって、その画像がどのコンセプトに帰属しているかを表した正解ラベルとの関係を学習することによって獲得する。
【００８２】
学習器としては、例えば、サポートベクターマシンなどを用いればよい。コンセプト特徴は、各コンセプトへの帰属レベルをまとめてベクトルとして表現することで得ることができる。
【００８３】
景観特徴は、画像の風景や場面を表現した特徴量である。例えば、下記の参考文献３に記載のＧＩＳＴ記述子を用いることができる。
［参考文献３］A. Oliva、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年
【００８４】
コンテンツが音である場合には、音高特徴、音圧特徴、スペクトル特徴、リズム特徴、発話特徴、音楽特徴、音イベント特徴などを抽出する。
【００８５】
音高特徴は、例えば、ピッチを取るものとすればよく、下記の参考文献４に記載される方法などを用いて抽出することができる。
［参考文献４］古井貞熙、“ディジタル音声処理, ４. ９ピッチ抽出”、pp.57-59、1985年
【００８６】
音圧特徴としては、音声波形データの振幅値を用いるものとしてもよいし、短時間パワースペクトルを求め、任意の帯域の平均パワーを計算して用いるものとしてもよい。
【００８７】
スペクトル特徴としては、例えば、メル尺度ケプストラム係数（ＭＦＣＣ：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、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、G. Suzuki、“Structured Video Computing”、IEEE Multimedia、pp.34-43、1994年
【００９３】
望ましくは、後者の方法を採用する。映像区間分割処理の結果として、区間の開始点（開始時刻）と終了点（終了時刻）が得られるが、この時刻毎に別々の特徴量として扱えばよい。
【００９４】
以上のように抽出した特徴量は、一つあるいは複数を利用してもよいし、その他の公知の特徴量を用いるものとしてもよい。
【００９５】
〔ハッシュ関数の生成処理〕
次に、ハッシュ関数の生成処理について説明する。コンテンツｉ（ｉ＝１，２，…，Ｎ）から抽出された特徴量をｘｉとし、その特徴量ｘｉは特徴量空間Ｒｄに属するとする（ｘｉ∈Ｒｄ）。
【００９６】
このとき、前述したステップＳ１０３では、ｈ：Ｒｄ→｛０，１｝となるハッシュ関数ｈの集合を求める。特徴量ｘｉは、各ｈにより０または１をとるバイナリ値に写像されるので、ハッシュ関数集合Ｈ＝｛ｈ１，ｈ２，…，ｈＢ｝によってＢ個のバイナリ値、すなわち、Ｂｂｉｔのハッシュ値に変換されることになる。
【００９７】
本発明の目的は、このハッシュ値によって、時間のかかるコンテンツ間の類似度計算を省略可能にすることである。したがって、ハッシュ関数は、元の特徴量ｘｉ間の類似度ｓ：Ｒｄ×Ｒｄ→Ｒと関連したハッシュ値への写像であることが要請され、高い類似度を持つコンテンツほど、ハッシュ値の距離（ハミング距離）が近くなることが好ましい。
【００９８】
以下、ハッシュ関数の生成処理について詳述する。まず、ハッシュ関数生成部１３によって生成されるハッシュ関数ｈｋ（ｋ＝１，２，…，Ｂ）として、式（１），（２）に示すような線形関数に基づくハッシュ関数を考える。
【数１】
【数２】
【００９９】
ここで、ｓｉｇｎ（ｘ）は、ｗｋ∈Ｒｄ、ｂｋ∈Ｒをパラメータに持ち、ｘ≧０のとき１、ｘ＜０のとき−１をとる符号関数である。このような符号関数に基づくハッシュ関数であることから、コンテンツｉの特徴量ｘｉは、０または１のバイナリ値に変換されることになる。
【０１００】
このハッシュ関数ｈｋにおいて、未知のパラメータは、ｗｋとｂｋの二つだけである。ここで、仮に、コンテンツｉの特徴量ｘｉが平均０に正規化されているとき、ｂｋ＝０としても一般性を失うことはない。
【０１０１】
特徴量ｘｉを０に正規化するには、特徴量ｘｉの平均ｍを各特徴量ｘｉから減算すればよいのであり、これはｘｉ∈Ｒｄにおいて可能であることから、ｂｋ＝０と決定できる。
【０１０２】
したがって、以降、特徴量ｘｉの平均は０に正規化されているとし、式（２）を式（３）のように定義しなおして説明する。
【数３】
【０１０３】
式（１），（３）のハッシュ関数ｈｋにおいて、ｗｋ（ｋ＝１，２，…，Ｂ）のパラメータを定めることが、本ハッシュ関数の生成処理の目的となる。
【０１０４】
ここで、式（１），（３）のように表現されるハッシュ関数ｈｋの意味は、図４を用いて幾何的に説明できる。同図には、特徴量空間Ｒｄ上に、各コンテンツｉからそれぞれ抽出された特徴量ｘｉが特徴点として分布している。なお、同図では、便宜上２次元のように図示しているが、実際にはｄ次元の空間である。
【０１０５】
ここで、ハッシュ関数ｈｋを構成するφｋ（ｘｉ）は、この特徴量空間Ｒｄ上の原点を通る直線（実際は、（ｄ−１）次元の超平面）を表している。ハッシュ関数ｈｋ（ｘｉ）は、前述したように本質的には符号関数であるから、特徴量ｘｉを示す特徴点がこの直線φｋ（ｘｉ）によって２分割されたいずれの空間側にあるかによって、１または０をとる。
【０１０６】
すなわち、式（１），（３）によって定義されるハッシュ関数ｈｋ（ｘｉ）は、特徴量空間Ｒｄを直線φｋ（ｘｉ）によって１と０の２つの領域に分割する関数である。パラメータｗｋは、この直線φｋ（ｘｉ）の傾きに対応し、そのｗｋの値が変化すれば、分割する角度が変化することになる。
【０１０７】
したがい、本実施の形態によれば、コンテンツｉの特徴量ｘｉの分布に基づいて、パラメータｗｋを合理的に決定するハッシュ関数ｈｋの生成方法を提供することができる。以下、その原理と処理内容について説明する。
【０１０８】
前述した目的に合うハッシュ関数となるように、パラメータｗｋを求めるもっとも合理的な方法の一つは、類似したコンテンツ群が、先の図４の例における直線の片側に集まるように直線を引く（すなわち、パラメータｗｋを決める）ことである。
【０１０９】
ここで、わかりやすく図５を用いて説明する。同図では、白丸（○）で表されている特徴量ｘｉと、黒丸（●）で表されている特徴量ｘｉが存在する。また、これらとは別に、二重丸（◎）で表されている特徴量ｘｉが存在するが、ひとまずこれは無視してよい。
【０１１０】
今、白丸と黒丸で表されている特徴量ｘｉは、同色であれば互いに類似したコンテンツの特徴量であるとする。このとき、これらの類似したコンテンツ群が直線の片側に集まるように直線を引けばよい。このような直線は、２群の間を通るような直線であり、実際には無限に存在するが、例えば、直線５１のようなものがある。
【０１１１】
しかしながら、そのような直線５１は、頑健性（ロバスト性）に欠けるものである。ここで、先ほど無視した二重丸の特徴量ｘｉについて考える。これは、どちらかといえば白丸の群の周辺にあり、本来、白丸の群に属すべきコンテンツの特徴量であることが一目して見て取れる。
【０１１２】
しかしながら、この二重丸の特徴量ｘｉは、直線５１によって黒丸の群の方に分類されてしまっており、誤った分類を与えられてしまっている。もし、この二重丸の特徴量ｘｉを持つコンテンツｉがノイズによる揺らぎによって発生してしまった場合には、正しい分類を与えることができない。
【０１１３】
通常、コンテンツｉの特徴量ｘｉは揺らぎを伴って得られることが普通であるから、任意に引いた直線５１では、このような揺らぎに対して頑健性がなく、精度の低下を招いてしまう。
【０１１４】
これに対して本実施の形態では、無限にある直線の中から、頑健性の高い直線を求めることができる。頑健性の高い直線とは、マージンを最大化する直線、すなわち、それら両群のすべての特徴量ｘｉ（特徴点）からの垂線距離が等しくなるような直線である、直線５２を選べばよい。
【０１１５】
このようにして選ばれた直線５２は、互いの群から平等に最も遠い位置にある直線である。このため、両群の周辺に揺らいで発生するような二重丸のような特徴量ｘｉがあったとしても、正しい分類ができる。
【０１１６】
すなわち、ハッシュ関数生成部１３は、複数のコンテンツｉの各特徴量ｘｉを特徴量空間Ｒｄ上に特徴点として分布させて少なくとも２つの群に分類し、各郡の全ての特徴点からの垂直距離が等しい直線を計算し、特徴点が当該直線によって２分割されたいずれの空間側にあるかに基づいて、コンテンツｉをバイナリ値に変換するハッシュ関数を生成する。
【０１１７】
このような直線５２は、例えば、それら両群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いた式（４）の目的関数の演算値を最大化するｗの値を求めることにより、得ることができる。なお、ｔｒａｃｅ（トレース）とは、｛｝内のｎ次正方行列の対角成分の和を計算するものであり、線形代数学分野などにおいて一般に利用される。
【数４】
【０１１８】
なお、群間分散値Ｓｂ、郡内分散値Ｓｗは、それぞれ、式（５），（６）を用いて計算すればよい。ただし、ｍｊは群ｊ（ｊ＝０，１）の平均ベクトル、ｍは全体の平均ベクトル、Ｎｊは群ｊに属する特徴量ｘｉの数、Ｎは全体の特徴量ｘｉの数である。先に述べたように、全体の平均が０になるよう正規化されている場合、理論的にはｍ＝０となる。
【数５】
【数６】
【０１１９】
なお、式（４）を最大化するｗは、例えば、ラグランジュ未定乗数法によって、下記の固有値問題の解（固有ベクトル）として求めることができる。
【数７】
【０１２０】
この固有値問題を解いてｗを求める方法については、例えば、反復法など、種々の公知の方法を用いればよい。
【０１２１】
以上は、予めコンテンツｉの特徴量ｘｉがどちらの群に属しているかが既知である必要がある。以降、この情報を群指示情報と呼ぶ。一方で、現実の問題においては、群指示情報は未知である。つまり、このままでは現実にある多くの問題において、上記手法を取ることができない。
【０１２２】
そこで、本実施の形態では、群指示情報が未知の場合においても、同様のハッシュ関数を生成できる処理をとる。以降、この処理の一例について詳述する。
【０１２３】
まず、特徴量ｘｉ間の類似度を格納した類似度行列Ｖを求める。この類似度行列Ｖは、どのようなものでも構わないが、例えば、式（８）を利用して求めればよい。
【数８】
【０１２４】
また、その類似度行列Ｖに基づいて対角行列Ｄを計算する。
【数９】
【０１２５】
そして、式（４）に対して、群指示情報に依存しない正則化項を導入する。
【数１０】
【０１２６】
式（１０）の第２項がその正則化項であり、群間分散値Ｓｂや郡内分散値Ｓｗが含まれていないので、群指示情報がなくとも計算可能な項である。
【０１２７】
この式（１０）の演算値を最大化するｗの値は、ラグランジュ未定乗数法によって下記の固有値問題の解として求めることができる。なお、ηはパラメータであり、Ｘはハッシュ関数を求めた際の特徴量ｘｉの集合である。
【数１１】
【０１２８】
このような固有値問題の解は、前述の通り、反復法などの公知の方法によって計算できるので、仮に、群間分散値Ｓｂや郡内分散値Ｓｗがゼロ行列（要素がすべて０である行列）とすれば、群指示情報が全くなかったとしても、式（１１）を満たすｗを求めることができる。こうして求めたｗを、ｗ１とする。
【０１２９】
ハッシュ関数が１つ（すなわち、各特徴量ｘｉを１ビットのハッシュ値に変換する）でよければ、以上の手続きを以てハッシュ関数の生成処理を終了して構わない。
【０１３０】
しかしながら、通常は複数のハッシュ関数を用意し、複数ビットのハッシュ値に変換する。ここでは、以下の手続きにより、Ｂ個のハッシュ関数を用意するとして、ｗ１から順次ｗ２，ｗ３，…，ｗＢを求める。
【０１３１】
今、ｋ個のハッシュ関数ｈｋが求まっているとしたとき、ｋ＋１個目のハッシュ関数ｈｋ＋１を求めることを考える。本実施の形態では、ｋ個目までのハッシュ関数ｈｋを用いて、各特徴量ｘｉに疑似的な群指示情報を決定する。この付与方法は任意の方法で構わないが、例えば、ｋ個目のハッシュ関数ｈｋを用いて、次の規則に基づいて疑似群指示情報を与える。
【数１２】
【０１３２】
ここで、δはパラメータである。このように決定された疑似群指示情報を群指示情報であるとみなすことによって、式（５），（６）を用いて群間分散値Ｓｂや郡内分散値Ｓｗを計算することができ、式（１１）を満たすｗｋ＋１を得ることができる。
【０１３３】
基本的には、上記の処理をｋ＝１，２，…，Ｂと繰り返すことにより、ハッシュ関数ｈｋを逐次求めていけばよい。
【０１３４】
一方で、そのように「ｋ個目までのハッシュ関数ｈｋを用いて、各特徴量ｘｉに疑似的な群指示情報を決定する」場合、ｋ個目までのハッシュ関数ｈｋとｋ＋１個目のハッシュ関数ｈｋ＋１が互いに相関の高いもの（類似したもの）になってしまう確率が高く、非効率的である。
【０１３５】
そこで、本実施の形態では、より少ないハッシュ関数数でも高精度なハッシュ関数生成が実現できるよう、複数のハッシュ関数を生成する際に、互いに相関の低いハッシュ関数を生成する補正処理を導入する。
【０１３６】
例えば、ｋ個目のハッシュ関数ｈｋを用いて、ｋ個目のハッシュ関数ｈｋを求めた際の特徴量ｘｉの集合Ｘｋ＝｛ｘ１，ｘ２，…，ｘＮ｝を、次のように補正する。すなわち、ハッシュ関数間の相関度が低くなるように特徴点の分布状態を変化させる。
【数１３】
【０１３７】
この補正により、特徴量の分布から、ｗｋＴＸｋが示す方向成分が縮退されるので、その結果、既に得られているハッシュ関数と相関の低い特徴量分布へと変化する。この補正により、互いに相関の小さいハッシュ関数が生成されるようになる。
【０１３８】
以上の処理を繰り返すことにより、Ｂ個のハッシュ関数を得ることができる。処理の一例をまとめると、下記のように表現することができる。
【０１３９】
（手順１）最初に、ｋ＝１とし、Ｓｂｋ＝１＝０、Ｓｗｋ＝１＝０、Ｘｋ＝１＝Ｘとする。
【０１４０】
（手順２）次に、下記の固有値問題を解き、最大の固有値に対応する固有ベクトルをｗｋとする。
【数１４】
【０１４１】
（手順３）次に、式（１２）を用いて疑似群指示情報を計算する。
【０１４２】
（手順４）次に、ｋ＝Ｂなら処理を終了し、それ以外なら（手順５）に進む。なお、Ｂは任意に設定できる。
【０１４３】
（手順５）次に、式（１５）〜式（１７）を用いて、Ｓｂｋ＋１、Ｓｗｋ＋１、Ｘｋ＋１を求める。
【数１５】
【数１６】
【数１７】
【０１４４】
（手順６）（手順２）に戻る。
【０１４５】
上記の処理手続きによって生成されたハッシュ関数ｈｋ、すなわち、具体的には、パラメータｗｋ（ｋ＝１，２，…，Ｂ）は、ハッシュ関数記憶部１４に格納される。
【０１４６】
〔ハッシュ化処理〕
前述のハッシュ関数生成処理が済んでいれば、ハッシュ関数記憶部１４には、Ｂ個のハッシュ関数が格納されている。これを用いることにより、特徴量ｘｉで表現された任意のコンテンツｉを、Ｂビット以下のハッシュ値で表現することができる。
【０１４７】
〔実施例〕
ここでは、画像データベースを対象に、本実施の形態で実施したハッシュ値に基づいて類似画像を検索する一実施例について説明する。
【０１４８】
この実施例の画像データベースには、約２０，０００の画像が登録されている。各画像は、１０種類の異なるオブジェクトが示されている。この実施例では、同じオブジェクトを示す画像を、画像データベースに登録された画像の中から探し出すことを目的とした。
【０１４９】
従来の手法であれば、画像データベースに登録された全ての画像から特徴量を抽出しておき、閲覧画像の特徴量と類似度の高い画像データベース中の画像を推薦結果として出力する。
【０１５０】
一方、本実施例では、これをハッシュ値によって実施する。特徴量は任意のものを用いて構わないが、本実施例では画像を２８ピクセル×２８ピクセル＝７８４ピクセルに縮小し、各ピクセルの輝度値（２５６諧調）をそのまま用いた。
【０１５１】
すなわち、７８４次元の整数ベクトルであり、６，２７２ｂｉｔに相当する。これは予め、画像データベース中の全ての画像からこの特徴量を抽出しておく。さらに、本実施の形態によって、コンテンツの特徴量からハッシュ値を生成し、これを画像データベースに登録しておく。
【０１５２】
この実施例では、本実施の形態によって生成したハッシュ値による類似検索精度と、非特許文献１、２の技術によって生成したハッシュ値による類似検索精度とを比較した。図６に、ハッシュ値のビット数（ハッシュ関数の数）を変化させたときの検索精度を示す。
【０１５３】
いずれのビット数においても、本実施例の方が高い精度を得ている。本実施例によれば、通常１コンテンツあたり６，２７２ｂｉｔが必要であったところを、８ｂｉｔ〜３２ｂｉｔといった非常に小さい情報量で表現した場合であっても、高い精度を実現できている。このことから、本実施例による技術の高い効果が確認できる。
【０１５４】
以上説明したように、本実施の形態によれば、複数のコンテンツｉの各特徴量ｘｉを特徴量空間Ｒｄ上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線を求め、特徴点が当該直線によって２分割されたいずれの空間側にあるかに基づいてコンテンツｉをバイナリ値に変換するハッシュ関数ｈｋを生成する、より具体的には、特徴量ｘｉの群間距離と群内距離に基づいてハッシュ関数ｈｋを生成するので、揺らぎに頑健なハッシュ関数を生成することができることから、結果として、大量のマルチメディアコンテンツから、高速、省メモリでありながら、高精度で類似するコンテンツを発見することのできるコンテンツ変換方法、コンテンツ変換装置及びコンテンツ変換プログラムを提供できる。
【０１５５】
また、本実施の形態によれば、複数のハッシュ関数ｈｋを生成する際に、特徴量ｘｉの分布を逐次補正しながらハッシュ関数を生成するので、互いに相関の低いハッシュ関数を生成できることから、結果として、より少ないハッシュ関数の数（ビット数）で、高精度な類似コンテンツ検索を実施することができる。
【符号の説明】
【０１５６】
１…情報処理装置（コンテンツ変換装置）
２…コンテンツデータベース
１１…入力部
１２…特徴抽出部（抽出手段）
１３…ハッシュ関数生成部（生成手段）
１４…ハッシュ関数記憶部（記憶手段）
１５…ハッシュ化部
１６…出力部
Ｓ１０１〜Ｓ１０３、Ｓ２０１〜Ｓ２０４…ステップ
【特許請求の範囲】
【請求項１】
コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換方法において、
コンピュータにより、
記憶手段からコンテンツを読み出して、複数のコンテンツの各特徴量をそれぞれ抽出する抽出ステップと、
前記各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、前記特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいて前記コンテンツをバイナリ値に変換するハッシュ関数を生成する生成ステップと、
を有することを特徴とするコンテンツ変換方法。
【請求項２】
前記生成ステップは、
前記２つの群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いたｔｒａｃｅ｛ｗＴ（Ｓｂ−Ｓｗ）ｗ｝（但し、ｗＴｗ＝１）の演算値が最大となるｗの値を傾きとして前記図形を求めることを特徴とする請求項１記載のコンテンツ変換方法。
【請求項３】
前記生成ステップは、
前記ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように前記特徴点の分布状態を変化させることを特徴とする請求項１又は２記載のコンテンツ変換方法。
【請求項４】
前記ハッシュ関数を１つ以上用いて前記コンテンツを１つ以上のバイナリ値に変換する変換ステップを更に有することを特徴とする請求項１乃至３のいずれかに記載のコンテンツ変換方法。
【請求項５】
コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換装置において、
記憶手段からコンテンツを読み出して、複数のコンテンツの各特徴量をそれぞれ抽出する抽出手段と、
前記各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、前記特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいて前記コンテンツをバイナリ値に変換するハッシュ関数を生成する生成手段と、
を有することを特徴とするコンテンツ変換装置。
【請求項６】
前記生成手段は、
前記２つの群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いたｔｒａｃｅ｛ｗＴ（Ｓｂ−Ｓｗ）ｗ｝（但し、ｗＴｗ＝１）の演算値が最大となるｗの値を傾きとして前記図形を求めることを特徴とする請求項５記載のコンテンツ変換装置。
【請求項７】
前記生成手段は、
前記ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように前記特徴点の分布状態を変化させることを特徴とする請求項５又は６記載のコンテンツ変換装置。
【請求項８】
請求項１乃至４のいずれかに記載のコンテンツ変換方法をコンピュータに実行させることを特徴とするコンテンツ変換プログラム。
【請求項１】
コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換方法において、
コンピュータにより、
記憶手段からコンテンツを読み出して、複数のコンテンツの各特徴量をそれぞれ抽出する抽出ステップと、
前記各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、前記特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいて前記コンテンツをバイナリ値に変換するハッシュ関数を生成する生成ステップと、
を有することを特徴とするコンテンツ変換方法。
【請求項２】
前記生成ステップは、
前記２つの群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いたｔｒａｃｅ｛ｗＴ（Ｓｂ−Ｓｗ）ｗ｝（但し、ｗＴｗ＝１）の演算値が最大となるｗの値を傾きとして前記図形を求めることを特徴とする請求項１記載のコンテンツ変換方法。
【請求項３】
前記生成ステップは、
前記ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように前記特徴点の分布状態を変化させることを特徴とする請求項１又は２記載のコンテンツ変換方法。
【請求項４】
前記ハッシュ関数を１つ以上用いて前記コンテンツを１つ以上のバイナリ値に変換する変換ステップを更に有することを特徴とする請求項１乃至３のいずれかに記載のコンテンツ変換方法。
【請求項５】
コンテンツを１つ以上のバイナリ値に変換するコンテンツ変換装置において、
記憶手段からコンテンツを読み出して、複数のコンテンツの各特徴量をそれぞれ抽出する抽出手段と、
前記各特徴量を特徴量空間上に特徴点として分布させ少なくとも２つの群に分類し、各郡の全特徴点からの垂直距離が等しい直線又は超平面を求め、前記特徴点が当該図形によって二分されたいずれの空間側にあるかに基づいて前記コンテンツをバイナリ値に変換するハッシュ関数を生成する生成手段と、
を有することを特徴とするコンテンツ変換装置。
【請求項６】
前記生成手段は、
前記２つの群の群間分散値Ｓｂと郡内分散値Ｓｗを変数に用いたｔｒａｃｅ｛ｗＴ（Ｓｂ−Ｓｗ）ｗ｝（但し、ｗＴｗ＝１）の演算値が最大となるｗの値を傾きとして前記図形を求めることを特徴とする請求項５記載のコンテンツ変換装置。
【請求項７】
前記生成手段は、
前記ハッシュ関数を複数生成する際に、他のハッシュ関数との相関度が低くなるように前記特徴点の分布状態を変化させることを特徴とする請求項５又は６記載のコンテンツ変換装置。
【請求項８】
請求項１乃至４のいずれかに記載のコンテンツ変換方法をコンピュータに実行させることを特徴とするコンテンツ変換プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１３−１０９４７９（Ｐ２０１３−１０９４７９Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５２７０８（Ｐ２０１１−２５２７０８）
【出願日】平成２３年１１月１８日（２０１１．１１．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月１８日（２０１１．１１．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
[ Back to top ]