(57)【特許請求の範囲】
【請求項１】
マルチメディア信号を識別するハッシュ信号を生成するコンピュータ実行装置であって、
−入力された前記マルチメディア信号を一定の規則に基づいてダウンサンプル化するダウンサンプラーと、
−ダウンサンプル化した前記マルチメディア信号を一定量の相関関係を有する重なったフレームに分割するフレーミングモジュールと、
−前記フレーミングモジュールにより生成されたフレーム毎にハッシュワードを計算するハッシュワード生成器であって、
当該ハッシュワード生成器は、
−バンド分割モジュールにより、マルチメディア信号の各フレームを、一つ以上のバンドまたはブロックに分割し、
−属性導出モジュールにより、当該バンドまたはブロックのそれぞれにおけるマルチメディア信号の特徴から属性を抽出し、
−ビット導出モジュールにより、前記属性について、隣接するバンド間又はブロック間及び隣接するフレーム間の差分と個々の閾値を比較することによってハッシュビットを生成し、生成されたハッシュビットを連結してハッシュワードを計算するものであり、
前記ハッシュワード生成器の生成した連続したハッシュワードを連結させて前記ハッシュ信号を生成するコンピュータ実行装置。
【請求項２】
一つ以上の前記バンドまたはブロックが、前記マルチメディア信号の個々のフレームの周波数スペクトルの周波数バンドである、請求項１に記載の装置。
【請求項３】
前記周波数バンドのバンド幅が、前記周波数バンドの周波数に応じて増大する、請求項２に記載の装置。
【請求項４】
一つ以上の前記バンドの周波数バンドの当該属性が、当該周波数バンドのエネルギーである、請求項２に記載の装置。
【請求項５】
一つ以上の前記バンドの周波数バンドの当該属性が、当該周波数バンドの調性である、請求項２に記載の装置。
【請求項６】
前記マルチメディア信号が、ビデオフレームを備えるビデオ信号であって、前記ビデオフレームはブロックに分割され、一つ以上の前記ブロックからのブロックの前記属性が当該ブロックの平均輝度である、請求項１に記載の装置。
【請求項７】
前記ハッシュワードの個々のビットが、前記ハッシュワードのビットの信頼性を表す、請求項１に記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報信号を識別するハッシュ信号を生成するための方法および装置に関する。また、本発明は、このようなハッシュ信号を、データベースに格納されているハッシュ信号に突き合わせるための方法および装置にも関する。
【０００２】
【従来の技術】
ハッシュ関数は、一般的に、とりわけ、大量のデータを識別するためにハッシュ関数を使用する暗号の分野において、知られている。例えば、大きなファイルが正確に受理されたことを検証するためには、そのファイルのハッシュ値（シグニチャーとも呼ばれる）を送れば、十分である。返されたハッシュ値が元のファイルのハッシュ値に一致すれば、受け取り側がファイルを正確に受け取ったことは、ほぼ確実である。起こり得る不確実性は、衝突が起こる可能性、すなわち、2つの異なるファイルが、同じハッシュ値を持つ状況によって、発生する。ハッシュ関数を慎重に設計することにより、衝突の確率は、最小に抑えることが出来る。
【０００３】
暗号ハッシュに特有な属性は、暗号ハッシュが非常に壊れやすいことである。元データ内の単一のビットをフリップさせると、通常、ハッシュ値は完全に異なることになる。このため、同じコンテンツの品質が異なるバージョンが同じシグニチャーを生じなければならないマルチメディア・コンテンツを識別するには、暗号ハッシングは、不適切である。（処理を行ってもコンテンツの受容可能な品質が維持される限り）データ処理に対してある程度不変なマルチメディア・コンテンツのシグニチャーのことを、強固なシグニチャー、または我々の好ましい命名規約では、強固なハッシュと呼ぶ。
【０００４】
強固なハッシュおよびコンテンツ識別子のデータベースを使用することによって、未知の内容は、例え、それが（例えば、圧縮またはAD/DA転換によって）劣化していたとしても、識別することが可能となる。強固なハッシュは、オーディオ・ビジュアル・コンテンツの知覚上不可欠な部分を捕らえる。
【０００５】
マルチメディア・コンテンツを識別するために強固なハッシュを使用することは、この同じ目的のために透かし技術を使用することの代替手段となる。しかしながら、両者には大きな違いもある。透かしを入れるためには、送信前に元のコンテンツへの処置（すなわち、透かしの埋め込み）が必要で、この処理が、コンテンツの品質に潜在的な影響を与えかつロジスティックの問題を有するのに対し、強固なハッシングは、送信前の処置が不要である。ハッシング技術の欠点は、データベースへのアクセスが必要である点であるが（例えば、ハッシングは、接続されているコンテキストでしか実現できないが）、透かし検出器は局所的に（例えば、非接続のDVDプレーヤで）作動させることができる。
【０００６】
米国特許4,677,466は、放送監視用のテレビ信号からシグニチャーを導出する公知の方法を開示している。この従来技術の方法の場合、シグニチャーは、空白のフレームなどの指定された事象が発生した後の短い画像または音声のシークエンスから、導出される。
【０００７】
【課題を解決するための手段】
本発明の一般的な目的は、強固なハッシング技術を提供することである。より詳細には、本発明の第一の目的は、マルチメディア・コンテンツから、数が限られたハッシングビットを抽出するための方法と装置を提供することである。ハッシングビットは強固ではあるが、ビットエラーの確率がゼロであるというほど強固ではない。完全一致ではないパターンの突き合わせ（すなわち、データベース内で最も類似するハッシュ値をサーチすること）は、NP完全であることが知られている。これは、簡潔に言えば、最良のサーチ戦略が非常に労力の掛かるサーチであることを意味するが、このサーチは、大きなデータベースを取り扱う多くのアプリケーションでは、拒絶される。したがって、本発明の第二の目的は、このNP完全サーチの複雑さを解決する方法および装置を提供することである。
【０００８】
第一の目的は、情報信号を連続した（好ましくは、重なった）フレームに分割し、各フレームごとに１つのハッシュワードを計算し、かつ連続したハッシュワードを連結させてハッシュ信号（または、一言でハッシュ）を構成させることによって達成される。ハッシュワードは、情報信号（例えば、ばらばらの周波数帯のエネルギーまたはイメージブロックの中間輝度）の属性のスカラー属性またはベクトルを閾値化することによって、計算される。
【０００９】
第二の目的は、ハッシュワードの入力ブロックの単一のハッシュワードを選択し、データベース内で前記ハッシュワードをサーチし、かつハッシュワードの入力ブロックと、対応する格納されているハッシュワードのブロックとの差を計算することによって、達成される。これらのステップは、更に選択されるハッシュワードに対して、当該差があらかじめ定められた閾値より小さくなるまで、繰り返される。
【００１０】
本発明のさらなる特徴は、従属項において定義される。
【００１１】
【発明を実施するための形態】
望ましい実施例を解説する前に、本発明の根幹をなしている考察について、その概要を説明する。
【００１２】
2つの信号（音声、ビデオすなわち画像）は、知覚的には区別することが出来ないにもかかわらず、信号理論上の意味において、（例えば、圧縮によって）全く異なる信号となる場合がある。ハッシュ関数は、人間の聴覚(auditory)システム(HAS)または人間の視覚(visual)システム（HVS）の挙動を模倣する、すなわち、ハッシュ関数は、HAS/HVSによって同じものであるとされたコンテンツに対して、同じハッシュ信号を生成することが、理想である。しかしながら、この信号には、多種の処理（圧縮、ノイズ追加、エコー追加、D/AおよびA/D変換、均一化など）が、適用される可能性があるので、HAS/HVSを完全に模倣することができるアルゴリズムは存在しない。さらに状況を複雑にする要因は、HAS/HVSでさえも人や時間によって相違し、かつ単一のHAS/HVSという考え方すら、維持することができないことである。さらに、ハッシュの古い定義は、時間を考慮していない。強固なハッシュは、コンテンツを認識することができるのみならず、時間（間隔）の識別もできなければならない。この理由から、本明細書においては、強固なハッシュに対し、次の定義を使用する。強固なハッシュとは、HAS/HVSが認識するコンテンツの類似性に関し連続的である半ユニークビット-シーケンスを、マルチメディア・コンテンツの各基本的な時間単位に、関連付ける関数である。
【００１３】
言い換えれば、HAS/HVSが、音声、ビデオすなわち画像の2つの部分を非常に類似していると識別する場合は、この関連付けられたハッシュも非常に類似していなければならない。特に、元のコンテンツのハッシュと圧縮されたコンテンツのハッシュは、類似していなければならない。さらに、重なったフレームに対してハッシュワードを計算する場合も、ハッシュワードは類似していなければならない。すなわち、ハッシュは、ローパス特性を有していなけらばならない。一方、2つの信号が、実際に、異なるコンテンツを表している場合、この強固なハッシュは、2つの（半ユニーク）信号を区別することが可能でなくてはならない。このことは、典型的な暗号ハッシュに対する衝突要件と類似している。ハッシュ関数に必要な強固さは、ハッシュ関数を、強固な特徴（属性）、すなわち、処理に対して相当程度変化しない特徴から導出することによって達成される。強固さは、誤りビットの数とビットの合計数との比として定義されるビットエラーレート(BER)によって表すことができる。
【００１４】
強固なハッシングによって、多くの興味深いアプリケーションの基礎であるコンテンツの識別が、可能になる。マルチメディア・データベース内のコンテンツ認識の具体例を考察する。ある人がある映画の一場面を見ていて、その場面がどの映画からのものかを知りたい場合を仮定してみる。見つけ出す一つの方法は、その場面を、データベース内のすべての映画の同じサイズのすべてのフラグメントと、比較することである。データベースが大きい場合には、これが、完全に実行不可能であることは、明らかである。すなわち、ビデオ場面が短い場合であっても、それは、大量のバイトによって表現されているので、基本的には、これらを全てのデータベースと比較しなければならない。したがって、これが機能するためには、容易にアクセス可能な大量のデータを格納させる必要があり、かつ、これらのデータのすべてを、識別すべきビデオ場面と比較しなければならない。したがって、格納の問題（データベース）と計算の問題（大量のデータの突き合わせ）の両方が存在する。強固なハッシングは、ビデオ場面を表現するために必要なビット数を減らすことによって、両方の課題を解決する。
すなわち、相対的に、格納させる必要があるビット数は少なくなり、かつ使用する必要があるビット数も少なくなる。
【００１５】
まず、音声信号の強固なハッシングを説明する。この音声信号は、44.1kHzのサンプル周波数（ＣＤ品質）でサンプル化されたモノラル音声であると仮定する。音声がステレオの場合、2つの選択肢がある。すなわち、ハッシュ信号を左と右のチャンネルに対して別々に抽出する選択肢と、ハッシュ信号を抽出する前に、左と右のチャンネルを追加する選択肢である。
【００１６】
音声が（秒オーダーの）短い断片しかない場合でも、それが何の歌なのかを知りたい場合がある。音声は、音声サンプルの終わりのない流れとみなすことができるため、音声信号を時間間隔またはフレームに細分化し、かつ、すべてのフレームに対してハッシュワードを計算する必要がある。
【００１７】
データベース内でハッシュを突き合わせようとする場合、フレームの境界を決定できないことが、頻繁にある。音声ハッシュには、特に、この同期化の問題が、該当する。この問題は、この信号を重なったフレームに分割することによって、解決される。重ねることによって、隣接する各フレームのハッシュワードが、一定量の相関を有することが可能となる。言い換えれば、ハッシュは、時間に対してゆっくりと変化する。
【００１８】
図1は、本発明に従って、音声ハッシュ信号を生成するための装置の実施例の線図である。音声信号は、後の各操作の複雑さを軽減させ、かつこの操作を人間の音声体系に最も関連した300〜3000 Hzの周波数範囲に制限するために、まずダウンサンプラー11でダウンサンプル化される。
【００１９】
フレーミング回路12において、音声信号はフレームに分割される。このフレームは、16384サンプル（
0004723171.tif 000002
秒）の長さ、および31/32の重なり率を有するハニング窓によって重み付けされる。この重なりは、後の各フレームの間においてハッシュワードの相関性が高くなるように選択される。あらゆるフレームのスペクトル表現は、フーリエ変換回路13によって計算される。次のブロック14において、（複雑な）フーリエ係数の絶対値（振幅）が計算される。
【００２０】
バンド分割ステージ15において、この周波数スペクトルは、ある数（例えば、33）のバンドに分割される。このことは、図1において、それぞれが、個々のバンドのフーリエ係数を選択するセレクタ151によって線図的に示されている。この装置の望ましい実施例の場合、HASもほぼ対数関数的なバンドに演算するので、このバンドは、対数関数的な間隔を有する。バンドをこのように選択することによって、ハッシュは、圧縮やフィルタリングなどの処理の変化による影響を受けにくくなる。
この好ましい実施例の場合、第一のバンドは300Hzから開始し、かつどのバンドも、1つの楽音のバンド幅を有する（すなわち、バンド幅は、
0004723171.tif 000003
/バンドの割合で増加する）。図2は、あるフレームのスペクトル201と、それの対数間隔で配置されているバンド202への細分の一例である。
【００２１】
次いで、すべてのバンドに対して、ある種の（必ずしもスカラーではない）特有な属性が計算される。属性の例は、エネルギー、調性、およびパワースペクトル密度の標準偏差である。一般的に、この選択された属性は、フーリエ係数の任意の関数とすることが出来る。どのバンドのエネルギーも、多種の処理に最も強固である属性であることが、実験的に実証されている。このエネルギー計算は、エネルギー計算ステージ16において行われる。各バンドに対して、エネルギー計算は、そのバンド内におけるフーリエ係数の（二乗された）マグニチュードの和を計算する、ステージ161を有する。
【００２２】
フレームごとに2進のハッシュワードを得るために、強固な属性は、次いで、ビットに変換される。このビットは、おそらく異なっているフレームの強固な属性の任意の関数を計算し、次に、この関数を閾値と比較することによって、割り当てることができる。この閾値自体が、この強固な属性値の他の関数の結果である場合もあろう。
【００２３】
本装置の場合、ビット導出回路17は、バンドのエネルギーレベルをバイナリハッシュワードに変換する。単純な実施例の場合、この導出ステージは、バンドごとに1ビット生成する。例えば、エネルギーレベルが、ある閾値より高い場合は、「1」を1つ生成し、かつエネルギーレベルが当該閾値より低い場合は、「0」を1つ生成する。閾値は、バンドごとで異なる。これに代えて、エネルギーレベルがその隣のエネルギーレベルより大きい場合、バンドにはハッシュビット「1」が割り当てられ、小さい場合は、ハッシュ・ビット「0」が割り当てられる。本実施例は、後者の代替手段をさらに改良したバージョンを使用する。音声信号の主要な単一周波数が、連続するフレームに対して同一のハッシュワードを生成しないように、時間に対する振幅の変化も考慮される。より詳しくは、あるバンドには、そのエネルギーレベルがその隣のエネルギーレベルより大きく、かつ、これが以前のフレームでも同様の場合、ハッシュビット「1」が割り当てられ、それ以外の場合、ハッシュビットには「0」が割り当てられる。フレームnのバンドmのエネルギーをEB(n,m)と表記し、かつ、フレームnのハッシュワードHのm番目のビットをH(n,m)と表記すると、導出回路17は、次式によって、ハッシュワードのビットを生成する。
0004723171.tif 000004
【００２４】
この目的のために、ビット導出回路17は、バンドごとに、第一減算器171、フレームディレイ172、第二の減算器173、およびコンパレータ174を有する。音声フレームのスペクトルの33のエネルギーレベルは、このようにして、32ビットハッシュワードに変換される。連続するフレームのハッシュワードは、コンピュータ20がアクセスすることができるバッファ18に、最終的に格納される。このコンピュータは、データベース21内の多数の元の曲の強固なハッシュを格納する。
【００２５】
次の動作で、同じ装置が、未知のオーディオクリップのハッシュを計算する。図3の参照番号31は、データベース21に格納されているオーディオクリップの、256個の連続する重なった音声フレーム（
0004723171.tif 000005
秒）のハッシュワードを示す。この図において、各行は、32ビットのハッシュワードであり、白色の画素はハッシュワードの「1」ビットを表し、黒い画素は「0」ビットを表し、かつ時間は上から下へと進行する。参照番号32は、32kBit/sでMP3圧縮した後の同じオーディオクリップから抽出されたハッシュワードを示す。理想的には、この2つのハッシュブロックは同一であるべきだが、圧縮したために、いくつかのビットは異なっている。この違いは、図3において33と表記される。
【００２６】
次に、画像またはビデオ信号の強固なハッシュについて説明する。この場合にも、強固なハッシュは、情報信号の特有な特徴から導出される。尋ねるべき第一の疑問は、ハッシュワードを決定する当該の特徴を、どのドメインで抽出するかということである。周波数ドメインが知覚的な特性を最適に表す音声とは対照的に、使用すべきドメインが明確でない。複雑さに関する理由のために、DCTまたはDFT変換のような複雑な動作は、避けることが好ましい。したがって、空間-時間ドメインの特徴が計算される。さらに、大半の圧縮ビデオストリームからも容易に特徴を抽出できるようにするために、ブロックに基づくDCT係数から容易に計算することができる特徴が選択される。
【００２７】
これらの考察に基づくと、この好ましいアルゴリズムは、相対的に大きな画像領域全体で計算される平均および分散などの、単純な統計値に基づいている。この領域は、かなり単純な方法で選択される。すなわち、画像フレームは、64x64画素の正方ブロックに分割される。特徴は、輝度成分から抽出される。しかしながら、これは基本的な選択ではない。すなわち、クロミナンスの成分を使用することもできる。実際のところ、ハッシュビットの数を増大させる最も容易な方法は、ハッシュビットを、輝度から抽出する場合と同様の方法で、クロミナンス成分から抽出することである。
【００２８】
図4は、ビデオ信号を識別するハッシュ信号を、本発明に従って生成するための装置のブロックダイヤグラムである。この装置は、連続するビデオ信号のフレームを受信する。各フレームは、M+1ブロックに分割される（41）。これらの各ブロックごとに、画素の輝度値の平均が計算される（42）。フレームpのブロックkの平均輝度は、k=0,...,MをF(p,k)と表記される。
【００２９】
ハッシュをグローバルなレベルと輝度のスケールから独立させるために、2つの連続したブロック間の輝度差が計算される（43）。さらに、時間方向におけるハッシュワードの相関性を減少させるために、連続フレームにおける空間微分の平均輝度値の差も計算される（44、45）。換言すれば、単純な空間-時間 2x2 Haarフィルタが、平均輝度に適用される。結果の符号は、フレームpのブロックkに対して、ハッシュビットH(p,k)を構成する（46）。数学的な表記は、次の通りである。
0004723171.tif 000006
【００３０】
この例では、各フレームは、64x64のサイズの33ブロック（すなわちM=32）に分割される。完全なハッシュHは、30の連続するフレームから抽出されたビットにより構成されている。各々が32ビットの30個のハッシュワード（960ビット）により構成される、このようなハッシュブロックは、以下に示されるように、フォルスポジティブの確率(false positive probability)が、十分に小さくなる。典型的な元のハッシュブロックを、図5の51に表す。図中、黒と白はそれぞれ、「0」と「1」に対応している。同じデータの、対応するハッシュ・ブロックを水平に94%まで拡大したものを、参照番号52で示す。番号53は、ハッシュブロック51と52との差を表す。この場合、ビットエラー率は11.3%に等しい。誤りビットが、時間（垂直）方向に非常に大きい相関性を有することは、注目される。
【００３１】
次に、抽出されたハッシュブロックを、大きなデータベースのハッシュブロックに突き合わせる処理について説明する。これは、不完全な突き合わせ（抽出されたハッシュワードがビットエラーを有している場合があることに留意）がNP完全であることが周知であるので、重要な作業である。データベースには、約5分の曲が100,000種類（≡25000ハッシュワード／曲）格納される。256個のハッシュワードを有するハッシュブロック（例えば、図3のハッシュブロック32）は、未知のオーディオクリップから抽出されたものと仮定される。次に、抽出されたハッシュブロックが、格納されている100,000曲のどれに最も一致するかを、決定すべきである。したがって、抽出されたハッシュブロック、すなわち、ビットエラー率（BER）が最小であり、またはは、これに代えて、BERが特定の閾値よりも低いハッシュブロックにもっとも似ている、100,000曲中の1曲中のハッシュブロックの位置を見つけ出さなければならない。この閾値は、フォルスポジティブの率、すなわち、歌がデータベースから不正確に識別される率を、直接的に決定する。
【００３２】
2つの3秒のオーディオクリップの（または2つの30フレームのビデオシーケンス）は、2つの導出されたハッシュブロックH1とH2との間のハミング距離が、特定の閾値Tより小さい場合、同様であると宣言される。この閾値Tは、フォルスポジティブの率Pf、すなわち2つのオーディオクリップ／ビデオシーケンスが等しいと不正確に（すなわち人間が目で見て不正確に）表される率を、直接的に決定する。すなわち、Tが小さいほど、確率Pfは小さくなる。一方、ある小さな値Tは、フォルスネガティブの確率Pn、すなわち2つの信号は「等しい」が、そのように識別されない確率に対して、否定的な影響を与えるであろう。この閾値Tという選択肢を分析するために、ハッシュ抽出工程が、i.i.d.（独立であり、かつ同様に分散している）ビットを生ずると仮定する。従って，ビットエラーの数は、パラメータ(n,p)を有する二項分布を有するであろう。このパラメーターにおいて、nは抽出されたビットの数に等しく、かつ、p=(0.5)は「0」または「1」ビットが抽出される確率である。我々の用途においては、n（音声用の32x256=8192、かつビデオ用の32x30=960）が大きいため、二項分布は、平均μ=npおよび標準偏差
0004723171.tif 000007
を用いた通常の分布によって、近似値を求めることができる。ハッシュブロックH1が与えられた場合、無作為に選択されたハッシュブロックH2が、H1に対してT=αn未満のエラーを有する確率は、
0004723171.tif 000008
によって求められる。
【００３３】
しかしながら、実際には、強固なハッシュは、時間軸に沿って高い相関性を有する。これは、基本となるビデオ・シーケンスの大きな時間相関性、または音声フレームの重なりに起因する。実験は、誤りビットの数は通常分散するが、標準偏差はi.i.d.の場合よりも約3/2倍大きいことを示している。したがって、この換算係数3/2を含めるために、式(1)は次のように変更される。
0004723171.tif 000009
【００３４】
実験時に使用したBERの閾値は、α=0.25である。このことは、ハッシュブロックが同じ歌から発生していることを決定するためには、8192ビットのうち、2048未満のビットエラーしか発生してはならないことを意味する。この場合、ビットエラーは、np=4096の平均μ、と
0004723171.tif 000010
の標準偏差σを有する正規分布を有する。したがって、この選択された閾値の設定は、15.2σというフォルスアラームの確率(false alarm probability)に対応する。したがって、フォルスアラームの確率は、1.8・10-52に等しい。しかしながら、同様のハッシュワードを有する音楽（例えば、2人の異なるピアニストが演奏するモーツァルトの一曲）がデータベースに含まれている場合、実際にはフォルスアラームの確率がより高くなることは、留意すべきである。
【００３５】
抽出されたハッシュブロックのデータベース内におけるサーチは、ブルートフォース突き合わせによって行うことができる。これには、約25億(=25000x100,000)回の突き合わせが必要となる。さらに、データベースの大きさに応じて、突き合わせの数は線形的に増加する。
【００３６】
本発明の一態様に従って、コンピュータ20は、データベース21内の対応する歌を見つけ出すためのより効率的な方策を使用する。図6は、コンピュータが行う動作のフローチャートである。データベース内に元の歌が格納されると直ちに、コンピュータはステップ60のルックアップテーブル(LUT)を更新する。LUTは、図1では、分離したメモリ22として示されているが、実際には、メモリ22は大きなデータベース用のメモリ21の一部分であることが適切である。図7に示されるように、LUT 22は、可能な32ビットの各ハッシュワードに対するエントリを有する。LUTの各エントリは、各歌と、この歌の中において個々のハッシュワードが発生する位置とを指す。ハッシュワードは、多数の歌の中の多数の位置で発生しうるので、歌ポインタはリンクされたリスト内に格納される。このようにして、LUTは多数の候補曲を生成することができる。データベース内に、限られた数の歌しかない場合、232個のエントリを含むLUTが非実用的となりうることは注目される。このような場合、ハッシュ表およびリンクリストを用いてLUTを実行することは有利である。図7の参照番号70は、未知のオーディオクリップ（例えば、図3のハッシュブロック32）から抽出された256個のハッシュワードの1ブロックを示している。
【００３７】
突き合わせ方法の第一の実施例の場合、時折、単一のハッシュワードがビットエラーを全く有さないことが、仮定されるであろう。ステップ61においては、単一のハッシュワードH(m)が、ハッシュブロックから選択され、かつデータベースに送られる。最初、これは、抽出されたハッシュブロックの最後のハッシュワードH(256)になろう。図7に示される具体例の場合、これはハッシュワード0x00000001である。データベース内のLUTは、歌1の特定の位置を指す。この位置が、位置pであると仮定する。ステップ62において、コンピュータは、抽出されたハッシュブロックと、歌1の位置p-255から位置p（図7において71と示される）に至るハッシュワードのブロックとの間のBERを計算する。ステップ63において、BERが低い（<0.25）か高いかが確認される。BERが低い場合、抽出されたハッシュワードが歌1からのものである可能性が高い。BERが高い場合、歌がデータベースに存在しないか、この単一のハッシュワードH(m)が誤りを含んでいるかのいずれかである。後者が、この例に該当すると見なされる。次に、別の単一のハッシュワードが、ステップ64において選択され、LUTにおいて調べられる。図7において、今度は、最後から２番目の単一のハッシュワードH(255)が調べられる。このハッシュワードは、歌2において発生すると思われる。入力ブロック70と格納されたブロック72との間のBERは、今度は0.25未満であると考えられるため、歌2がオーディオクリップの出所となる歌として識別される。格納されたブロック52の最後のハッシュワードが0x00000000であることは、注目される。明らかに、前に選択されたハッシュワード0x0000001は、1つのビットエラーを有していた。
【００３８】
コンピュータはこのように、一度に単一のハッシュワードしか調べず、かつこのような単一のハッシュワードにはビットエラーが全くないことが時折あると仮定する。抽出されたハッシュブロックのBERは、次に、候補歌の対応する（時間軸上の）ハッシュブロックと比較される。BERが最も低い候補歌の題名は、最も低いBERが閾値（ステップ65）よりも低ければ、抽出されたハッシュワードの出所となる歌として、選択されるであろう。選択されない場合、データベースは、抽出されたハッシュブロックが見つからなかったと、報告するであろう。次に、もう一つの単一のハッシュワードが試される。単一のハッシュワードが1つも成功しない場合（ステップ66）、データベースは、データベース（ステップ67）には候補歌がないとの報告による応答を行う。
【００３９】
上述の方法は、抽出されたハッシュワードが、時折ビットエラーを全く含んでいない、すなわち、対応する格納されたハッシュワードと完全に等しい、という仮定に依存している。広範囲な実験によると、これが、大半の音声において、1秒に2、3回定期的に発生することが判明している。このことは、例えば、 図3Bの抽出されたブロックを形成する256個のハッシュワード中のビットエラーの数を示す図8に示されている。この3秒のオーディオクリップでは、13個のハッシュワードが、一切のビットエラーなしに発生する。
【００４０】
しかしながら、音声が厳格に処理される場合、ビットエラーが全く無いハッシュワードが発生することは、ありえない。この場合、歌の題名を以前の方法でサーチすることはできない。この目的のために、突き合わせ方法の別の実施例を説明する。この方法は、抽出されたハッシュワードをデータベース内で発見するために、ハッシュ抽出アルゴリズムのソフト情報を使用する。ソフト情報とは、ビットの信頼性、または、ハッシュビットが正確にサーチされた確率を意味するものと理解すべきである。この実施例の場合、ハッシュワードを抽出するための装置は、ビット信頼性決定回路を含む。ビット信頼性決定回路は、図1に示される音声ハッシュ抽出装置において、19と表記される。ビット信頼性決定回路は、微分エネルギーのバンドレベルを、実数の形で受信する。この実数が閾値（この例ではゼロ）に非常に近い場合、各ハッシュビットは信頼できない。この数が、代わりに閾値から非常に離れている場合、各ハッシュビットは信頼できるハッシュビットである。信頼できるビットの数が固定されるように、閾値を固定したり制御することは可能である。
【００４１】
ビット信頼性決定回路19は、すべてのハッシュビットの信頼性を決定し、かつこうして、抽出装置またはコンピュータ20は、各ハッシュワードごとにもっとも有望な代替のハッシュワードの一覧を、生成することができる。この場合も、代替のハッシュワードのうち少なくとも1つが正確であると仮定することによって、曲名を正確にかつ容易に受けることができる。図9は、図3のハッシュブロック32における256個すべてのハッシュワードに対して、ハッシュワードのどのビットがもっとも信頼できるかを示している。
【００４２】
図10は、抽出されたハッシュブロックをデータベース内で発見する方法の本実施例において、コンピュータによって実行される動作のフローチャートである。上述の動作では、同じ参照番号が使用されている。この場合においても、ハッシュブロックの最後に抽出されたハッシュワード（0x00000001、図7を参照）が最初に選択され、かつデータベース（ステップ61）に送られる。データベース内のLUTが、歌1の位置pを指す。抽出されたハッシュブロックと、歌1の対応するブロック71との間のBERが計算される（ステップ62）。一方、前の具体例から、BERが高いことが分かる。ステップ101において、コンピュータは、今度はビット信頼性決定回路19（図1）を調べ、かつ、この特定のハッシュワードでは、ビット0が最も信頼できないビットであることを知る。次に最も有望なハッシュワードの候補を、今度は、このビットをフリップして得ることができる。新規なハッシュワード（0x00000000）は、ステップ102のデータベースに送られる。図7に示されるように、ハッシュワード0x00000000は、データベース内の2つの可能な候補歌、すなわち歌1および歌2に至る。例えば、抽出されたハッシュワードが、今度は歌2のハッシュワードに対して低いBERを有する場合、歌2は抽出されたハッシュブロックの出所となる歌として識別される。そうでなければ、新しいハッシュワード候補が生成されたり、または、データベース内のそれぞれの歌を見出す試みのために、他のハッシュワードが用いられるであろう。この方策は、更なる代替の候補ハッシュワードが存在しないことが、ステップ103で判明するまで、続けられる。
【００４３】
一片のオーディオが、実際に特定の歌から生じていると識別されると、データベースは、全ての候補ハッシュワードを生成する前に、まず抽出されたハッシュワードをその歌に突き合わすことができる点は、注目される。
【００４４】
もっとも有望なハッシュワードのリストを生成するための非常に単純な方法は、全てのハッシュワードに、固定されているN個の最も信頼性が高いビット、および残留するビットのあらゆる可能な組合せを含めることである。32ビット／ハッシュ、かつN=23を選択する場合、512個の候補のハッシュワードの一覧が必要となる。さらに、このことは、ハッシュワードの最も信頼性が低い9つのビットが誤っていると、音声の抜粋をもはや識別することができないことを意味する。これは、図6に示す事例の場合、前の方法における13個の代わりに、117個のハッシュワードが、データベース内の歌への正確なポインタを生じることを意味する。
【００４５】
突き合わせ方法の別の実施例の場合、信頼性が高いとマークされているハッシュビットのみに基づいて、突き合わせが行われる。この方法は、受けたハッシュの信頼できないビットを、データベース内の対応するビットと比較する必要はないという洞察に基づいている。これは、はるかに少ないビットエラー率をもたらすが、これは、全ての必要な情報をデータベースに伝送させるために必要な、より複雑なサーチ戦略とより広いバンド幅という犠牲によって、もたらされる。
【００４６】
次に、強固なハッシュの2、3の用途を説明する。
−放送のモニタリング：ブロードキャスト監視システムは、2つの部分、すなわ
ち、多数の歌のハッシュを含んでいる中央のデータベース、およびハッシュ
ブロックを、例えば、無線局によって放送される音声から抽出するモニタリン
グ・ステーションから成る。このモニタリング・ステーションが、抽出された
ハッシュブロックを中央のデータベースに送信すると、データベースはどの歌
が放送されたかを決定することができる。
−携帯電話の音声情報：バーである歌を聞いていて、その題名を知りたくなった
場合を考えよう。先ず、自分の携帯電話を取り出し、音声ハッシュのデータベ
ースに電話をかける。すると、この音声ハッシュのデータベースは、その歌を
聞いて、ハッシュブロックを抽出する。次に、音声ハッシュのデータベースは
、ハッシュ・ブロックをデータベース内で見出すと、歌の題名を報告する。
−連結内容（メディアブリッジ(MediaBridge)）：ディジマーク社(Digimarc)は
、現在、透かし技術に基づくメディアブリッジ(MediaBridge)と呼ばれるアプ
リケーションを有している。この考えは、一片のマルチメディアの透かしが、
ある特別な情報を得ることができるインターネット上の特定のURLにユーザー
を導く、というものである。例えば、ある雑誌の広告に透かしを入れる。ウェ
ブカメラの前でこの広告を掲げると、透かし検出器が透かしの鍵を抽出し、透
かしの鍵はデータベースに送られる。したがって、このデータベースは、ユー
ザーがリダイレクトされるURLを含んでいる。同じアプリケーションは、強固
なハッシング技法を用いる場合にも機能することができる。将来は、自分の移
動テレビ電話を現実の物体に向ける人のことを考えつくかもしれない。その時
、音声ハッシュ・データベースは、この物体に関する情報を、直接的に、ある
いはインターネット上のURLを介して、報告する。
−マルチメディアの品質測定：高品質な元のコンテンツのハッシュワードがデー
タベースに記載されている場合、処理されたマルチメディア・コンテンツの抽
出されたハッシュワードのBERを決定することによって、品質の尺度を得るこ
とができる。
【００４７】
抽象的な観点から見ると、強固な音声ハッシュは、異なる周波数帯と時間に対してエネルギーを比較することによって、音声信号から抽出される。この手法の一般化は、LTIと非線形関数のいかなる縦続も考慮することである。特に強固なハッシュは、（ダイアディック）フィルタバンク（LTIオペレータ）を適用し、次いで、絶対語（非線形関数）を二乗しまたは取得し、次いで、時間および／またはバンドについて差分オペレータ（LTIオペレータ）を続け、最後に閾値化演算子を続けることによって、得ることもできる。慎重に設計された線形フィルタバンクを、初期の演算子として適用することによって、FFTの複雑さを回避できる。さらに、多くの圧縮エンジンは、線形フィルタバンクを初期相として有するため、特徴抽出を圧縮によって集積するオプションがある。
【００４８】
コンテンツを識別するため、強固なハッシュおよび電子透かしが、併用できることに、さらに注目すべきである。上述の方法、およびいくつかの透かし検出アルゴリズムは、いくつかの共通する初期処理ステップ、すなわちスペクトル表現の計算を有する。このことは、透かし検出および特徴抽出を、1つのアプリケーションにおいて容易に集積化できるという考え方に結びつく。したがって、サーチされた透かしおよびハッシュワードを、さらなる詳細な解析のために中央のデータベースに送ることによって、コンテンツの識別が可能になる。
【００４９】
要約すると、この開示された方法は、マルチメディア・コンテンツ、例えば、オーディオクリップのための強固なハッシュを生成する。オーディオ・クリップは、連続した（好ましくは、重なった）フレーム(12)に分割される。各フレームごとに、周波数スペクトルはバンド(15)へ分割される。各バンド（例えば、エネルギー）の強固な属性は、計算され（16）、かつ個々のハッシュビットによって表わされる(17)。オーディオクリップは、このように、各フレームごとに2進のハッシュワードの連結によって表現される。おそらく圧縮されている音声信号を識別するために、この音声信号から導出されるハッシュワードのブロックは、コンピュータ(20)によって、大きなデータベース（21）と突き合わせられる。このような突合せ戦略も、開示されている。有利な一実施例の場合、抽出処理は、どのハッシュビットが最も信頼できないかに関する情報(19)をも提供する。これらのビットを著しくフリップすることによって、突合せ処理の速度および効率が向上する。
【図面の簡単な説明】
【図１】  本発明に従って、オーディオ信号からハッシュ信号を抽出するための装置の実施例の回路線図である。
【図２】  オーディオ信号スペクトラムの細区分を、対数的に間隔を置いたバンドに示す線図である。
【図３】  オーディオクリップから抽出されたハッシュワードを示す線図である。
【図４】  本発明に従って、ビデオ信号からハッシュ信号を抽出するための装置の実施例の回路線図である。
【図５】  ビデオシーケンスから抽出されたハッシュワードを示す線図である。
【図６】  本発明に従って、図1に示されるコンピュータによって実行される操作のフローチャートである。
【図７】  図1に示されるコンピュータの操作を示す線図である。
【図８】  図3に示される抽出されたハッシュブロックを形成するハッシュワード内の、ビットエラーの数のグラフである。
【図９】  図3に示されるハッシュブロックのハッシュワードの最も信頼できるビットのグラフである。
【図１０】  本発明のさらなる実施例に従って、図1に示されるコンピュータによって実行される操作のフローチャートである。
【図１】
0004723171.tif 000011
【図２】
0004723171.tif 000012
【図３】
0004723171.tif 000013
【図４】
0004723171.tif 000014
【図５】
0004723171.tif 000015
【図６】
0004723171.tif 000016
【図７】
0004723171.tif 000017
【図８】
0004723171.tif 000018
【図９】
0004723171.tif 000019
【図１０】
0004723171.tif 000020