(57)【要約】【課題】強固なハッシング技術を提供すること。より詳細には、マルチメディア・コンテンツから、数が限られたハッシングビットを抽出するための方法と装置を提供すること。【解決手段】ハッシュは、そのファイルを識別するために用いることができる、データファイルの短い要約またはシグニチャーである。元のコンテンツと処理された（例えば、圧縮された）コンテンツのハッシュは著しく異なる場合があるため、マルチメディア・コンテンツ（オーディオ、ビデオ、画像）のハッシングは困難である。開示されている方法は、マルチメディア・コンテンツ、例えば、オーディオクリップに対する強固なハッシュを生成する。オーディオクリップは、連続した（好ましくは重なる）フレームに分割される（１２）。各フレームごとに、周波数スペクトルはバンドに分割される（１５）。各バンドの強固な属性（例えば、エネルギー）は計算され（１６）、かつ個々のハッシュビットによって表される。オーディオクリップは、このように、２進のハッシュワードの連結、すなわち各フレームごとに１つの連結によって表される。おそらく圧縮されている音声信号を識別するために、音声信号から導出されたハッシュワードのブロックは、コンピュータ（２０）によって大きなデータベース（２１）に突き合わせられる。このような突き合わせ方策も開示される。有利な一実施例において、この抽出処理は、どのハッシュビットが最も信頼できないかに関する情報（１９）をも提供する。これらのビットをフリップさせることによって、突き合わせ処理の速度および性能が著しく向上する。【選択図】図１
2004519015.tif 000002
【特許請求の範囲】
【請求項１】
情報信号を識別するハッシュ信号を生成する方法であって、
−前記情報信号をフレームに分割するステップと、
−各フレームごとにハッシュワードを計算するステップと、
−前記ハッシュ信号を構成するために連続したハッシュワードを連結させるステップと、
を有する方法。
【請求項２】
当該計算ステップが、
−前記情報信号の各フレームを、ばらばらなバンドまたはブロックに分割するステップと、
−当該バンドまたはブロックのそれぞれにおける前記信号の属性を計算するステップと、
−前記バンドまたはブロックにおける前記属性を、個々の閾値と比較するステップと、
−当該比較の結果を、前記ハッシュワードの個々のビットによって表すステップと、
を有する、請求項１の方法。
【請求項３】
隣接するバンドまたはブロックの属性が、当該閾値を構成する、請求項２に記載の方法。
【請求項４】
前のフレーム内の対応するバンドまたはブロックの前記属性が、当該閾値を構成する、請求項２に記載の方法。
【請求項５】
前記バンドまたはブロックが、前記情報信号の個々のフレームの周波数スペクトルの周波数帯である、請求項２に記載の方法。
【請求項６】
前記周波数帯が、前記周波数の関数として増大するバンド幅を有する、請求項５に記載の方法。
【請求項７】
当該属性が、ある周波数帯のエネルギーである、請求項５に記載の方法。
【請求項８】
当該属性が、ある周波数帯の音調である、請求項５に記載の方法。
【請求項９】
当該情報信号が、重なったフレームに分割されている、請求項１の方法。
【請求項１０】
前記情報信号が、そのフレームがブロックであるビデオ信号で、ブロックの平均輝度が、当該ブロックの属性を構成する、請求項２に記載の方法。
【請求項１１】
前記ハッシュワードのビットの信頼性を表す情報を生成するために、当該比較ステップの入力を使用するステップを更に有する、請求項２の方法。
【請求項１２】
情報信号を識別するためのハッシュ信号を生成する方法であって、
−前記情報信号をブロックに分割するステップと、
−各ブロックごとに、当該ブロック内の前記情報信号の特徴を抽出するステップと、
−前記抽出された特徴の値を、ある閾値と比較するステップと、
−各ブロックごとに、前記抽出された特徴の値が、当該閾値より大きいか小さいかを示すハッシュビットを生成するステップと、
−各ブロックごとに、前記抽出された特徴の値が、当該閾値と実質上異なるか否かを示す信頼性情報を決定するステップと、
−当該ハッシュビットと前記ブロックの当該信頼性に関する情報を、前記抽出された特徴が当該閾値と実質的に異なる信頼できるハッシュビットと、前記抽出された特徴が当該閾値と実質的に異ならない信頼できないビットとを、有するハッシュ値に、結合するステップと、
を有する方法。
【請求項１３】
請求項１〜１２のいずれかに記載の方法に従って、情報信号を識別するハッシュ信号を生成するための装置。
【請求項１４】
情報信号の少なくとも一部を表すハッシュワードの入力ブロックと、データベース内に格納されている個々の情報信号を識別するハッシュ信号とを突き合わせる方法であって、
（ａ） ハッシュワードの当該入力ブロックのハッシュワードを選択するステップと、
（ｂ） データベース内の当該ハッシュワードをサーチするステップと、
（ｃ） ステップ（ｂ）で見出された前記ハッシュワードが、前記入力ブロック内の前記選択されたハッシュワードと同じ位置を有する、ハッシュワードの格納されているブロックと、ハッシュワードの前記入力ブロックとの差を計算するステップと、
（ｄ） 当該差があらかじめ定められた閾値よりも低くなるまで、さらに選択されたハッシュワードに対してステップ（ａ）〜（ｃ）を繰り返すステップと、
を有する方法。
【請求項１５】
さらに選択された前記ハッシュワードが、ハッシュワードの入力ブロックの別のハッシュワードである、請求項１４の方法。
【請求項１６】
さらに選択された前記ハッシュワードを、前記の前もって選択されたハッシュワードの１ビットを逆転させることによって得る、請求項１４の方法。
【請求項１７】
前記選択されたハッシュワードのビットの信頼性を表す情報を受信するステップと、反転すべき前記ビットを決定するために当該情報を使用するステップと、
をさらに有する、請求項１６の方法。
【請求項１８】
識別されていない情報信号を表示するハッシュ値を、データベースに格納されている複数のハッシュ値と突き合わせ、かつ個々の複数の情報信号を識別する方法であって、
（ａ） 当該ハッシュ値を、複数の信頼できるハッシュビットと信頼できないハッシュビットとの形で受け取るステップと、
（ｂ） 前記適用されたハッシュ値の信頼できるビットが、前記格納されているハッシュ値の対応するビットと一致する、前記格納されているハッシュ値を、データベース内でサーチするステップと、
（ｃ） ステップ（ｂ）で見出された個々の格納されているハッシュ値に対し、前記識別されていない情報信号を表すハッシュ値の信頼性が高いビットと、前記格納されているハッシュ値の対応するビットとの間のビットエラー率を計算するステップと、
（ｄ） 格納されている一連のハッシュ値のどれに対して、ビットエラー率が、最小でかつ十分に小さいかを決定するステップと、
を含む方法。
【請求項１９】
識別されていない情報信号を表すハッシュ信号を、データベースに格納されている複数のハッシュ信号と突き合わせ、かつ個々の複数の情報信号を識別する方法であって、
（ａ） 各々のハッシュ値が、信頼できるハッシュビットと信頼できないハッシュビットとを有するハッシュ値のシリーズの形態で、当該ハッシュ信号を受け取るステップと、
（ｂ） 当該シリーズのハッシュ値の１つを、データベースに印加するステップと、
（ｃ） 前記適用されたハッシュ値の信頼できるビットが、前記格納されているハッシュ値の対応するビットと一致する、格納されているハッシュ値を、データベース内でサーチするステップと、
（ｄ） ステップ（ｃ）で見つかった、格納されている各ハッシュ値ごとに、
−格納されているハッシュ値の前記対応するシリーズを、データベース内で選択し、
−前記識別されていない情報信号を表すハッシュ値の前記シリーズの信頼性が高いビットと、データベース内のハッシュ値の前記選択されたシリーズの前記対応するビットとの間のビットエラー率を計算するステップと、
（ｆ） 格納されているハッシュ値のどのシリーズに対して、ビットエラー率が最小であり、かつ、十分に小さいかを決定するステップと、
から成る方法。
【請求項２０】
ビットエラー率が最小であり、かつ、十分に小さい、格納されているハッシュ値のシリーズが見つかるまで、前記識別されていない情報信号の他のハッシュ値に対して、（ｂ）〜（ｆ）のステップを繰り返すステップ、をさらに有する、請求項１９に記載の方法。
【請求項２１】
請求項１４〜２０のいずれかに記載の方法に従って、情報信号の少なくとも一部を表すハッシュワードの入力ブロックを、データベースに格納されている個々の情報信号を識別するハッシュ信号に突き合わせるための装置。
【請求項２２】
情報信号のレシーバをインターネットのウェブサイトに切り換えるための方法であって、
当該情報信号からハッシュ信号を導出するステップと、
当該ハッシュ信号をデータベースに格納されているインターネット・ウェブサイトを識別するためのハッシュ信号に突き合わせるステップと、
を有する方法。
【請求項２３】
情報信号の品質を測るための方法であって、
当該情報信号からハッシュ信号を引き出すステップと、
当該ハッシュ信号を、データベースに格納されている当該情報信号を識別するハッシュ信号に突き合わせるステップと、
前記導出されたハッシュ信号と前記格納されているハッシュ信号との間の前記差を計算するステップと、
を有する方法。
【請求項２４】
マルチメディアの信号を識別するための方法であって、
当該マルチメディアの信号の少なくとも一部を受け取りおよび／または記録する当該ステップと、
当該マルチメディアの信号からハッシュ信号を導出するステップと、
当該ハッシュ信号をデータベースに送り、このハッシュ信号を、当該データベースに格納されているハッシュ信号と突き合わせるステップと、
当該データベースから前記マルチメディアの信号の識別子を受け取るステップと、
を有する方法。
【請求項２５】
前記マルチメディアの信号を受け取りおよび／または記録する当該ステップ、前記ハッシュ信号を導出しかつ送る当該ステップ、および前記識別子を受け取る当該ステップが、携帯電話装置によって実行される、請求項２４の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報信号を識別するハッシュ信号を生成するための方法および装置に関する。また、本発明は、このようなハッシュ信号を、データベースに格納されているハッシュ信号に突き合わせるための方法および装置にも関する。
【０００２】
【従来の技術】
ハッシュ関数は、一般的に、とりわけ、大量のデータを識別するためにハッシュ関数を使用する暗号の分野において、知られている。例えば、大きなファイルが正確に受理されたことを検証するためには、そのファイルのハッシュ値（シグニチャーとも呼ばれる）を送れば、十分である。返されたハッシュ値が元のファイルのハッシュ値に一致すれば、受け取り側がファイルを正確に受け取ったことは、ほぼ確実である。起こり得る不確実性は、衝突が起こる可能性、すなわち、２つの異なるファイルが、同じハッシュ値を持つ状況によって、発生する。ハッシュ関数を慎重に設計することにより、衝突の確率は、最小に抑えることが出来る。
【０００３】
暗号ハッシュに特有な属性は、暗号ハッシュが非常に壊れやすいことである。元データ内の単一のビットをフリップさせると、通常、ハッシュ値は完全に異なることになる。このため、同じコンテンツの品質が異なるバージョンが同じシグニチャーを生じなければならないマルチメディア・コンテンツを識別するには、暗号ハッシングは、不適切である。（処理を行ってもコンテンツの受容可能な品質が維持される限り）データ処理に対してある程度不変なマルチメディア・コンテンツのシグニチャーのことを、強固なシグニチャー、または我々の好ましい命名規約では、強固なハッシュと呼ぶ。
【０００４】
強固なハッシュおよびコンテンツ識別子のデータベースを使用することによって、未知の内容は、例え、それが（例えば、圧縮またはＡＤ／ＤＡ転換によって）劣化していたとしても、識別することが可能となる。強固なハッシュは、オーディオ・ビジュアル・コンテンツの知覚上不可欠な部分を捕らえる。
【０００５】
マルチメディア・コンテンツを識別するために強固なハッシュを使用することは、この同じ目的のために透かし技術を使用することの代替手段となる。しかしながら、両者には大きな違いもある。透かしを入れるためには、送信前に元のコンテンツへの処置（すなわち、透かしの埋め込み）が必要で、この処理が、コンテンツの品質に潜在的な影響を与えかつロジスティックの問題を有するのに対し、強固なハッシングは、送信前の処置が不要である。ハッシング技術の欠点は、データベースへのアクセスが必要である点であるが（例えば、ハッシングは、接続されているコンテキストでしか実現できないが）、透かし検出器は局所的に（例えば、非接続のＤＶＤプレーヤで）作動させることができる。
【０００６】
米国特許４，６７７，４６６は、放送監視用のテレビ信号からシグニチャーを導出する公知の方法を開示している。この従来技術の方法の場合、シグニチャーは、空白のフレームなどの指定された事象が発生した後の短い画像または音声のシークエンスから、導出される。
【０００７】
【課題を解決するための手段】
本発明の一般的な目的は、強固なハッシング技術を提供することである。より詳細には、本発明の第一の目的は、マルチメディア・コンテンツから、数が限られたハッシングビットを抽出するための方法と装置を提供することである。ハッシングビットは強固ではあるが、ビットエラーの確率がゼロであるというほど強固ではない。完全一致ではないパターンの突き合わせ（すなわち、データベース内で最も類似するハッシュ値をサーチすること）は、ＮＰ完全であることが知られている。これは、簡潔に言えば、最良のサーチ戦略が非常に労力の掛かるサーチであることを意味するが、このサーチは、大きなデータベースを取り扱う多くのアプリケーションでは、拒絶される。したがって、本発明の第二の目的は、このＮＰ完全サーチの複雑さを解決する方法および装置を提供することである。
【０００８】
第一の目的は、情報信号を連続した（好ましくは、重なった）フレームに分割し、各フレームごとに１つのハッシュワードを計算し、かつ連続したハッシュワードを連結させてハッシュ信号（または、一言でハッシュ）を構成させることによって達成される。ハッシュワードは、情報信号（例えば、ばらばらの周波数帯のエネルギーまたはイメージブロックの中間輝度）の属性のスカラー属性またはベクトルを閾値化することによって、計算される。
【０００９】
第二の目的は、ハッシュワードの入力ブロックの単一のハッシュワードを選択し、データベース内で前記ハッシュワードをサーチし、かつハッシュワードの入力ブロックと、対応する格納されているハッシュワードのブロックとの差を計算することによって、達成される。これらのステップは、更に選択されるハッシュワードに対して、当該差があらかじめ定められた閾値より小さくなるまで、繰り返される。
【００１０】
本発明のさらなる特徴は、従属項において定義される。
【００１１】
【発明を実施するための形態】
望ましい実施例を解説する前に、本発明の根幹をなしている考察について、その概要を説明する。
【００１２】
２つの信号（音声、ビデオすなわち画像）は、知覚的には区別することが出来ないにもかかわらず、信号理論上の意味において、（例えば、圧縮によって）全く異なる信号となる場合がある。ハッシュ関数は、人間の聴覚（ａｕｄｉｔｏｒｙ）システム（ＨＡＳ）または人間の視覚（ｖｉｓｕａｌ）システム（ＨＶＳ）の挙動を模倣する、すなわち、ハッシュ関数は、ＨＡＳ／ＨＶＳによって同じものであるとされたコンテンツに対して、同じハッシュ信号を生成することが、理想である。しかしながら、この信号には、多種の処理（圧縮、ノイズ追加、エコー追加、Ｄ／ＡおよびＡ／Ｄ変換、均一化など）が、適用される可能性があるので、ＨＡＳ／ＨＶＳを完全に模倣することができるアルゴリズムは存在しない。さらに状況を複雑にする要因は、ＨＡＳ／ＨＶＳでさえも人や時間によって相違し、かつ単一のＨＡＳ／ＨＶＳという考え方すら、維持することができないことである。さらに、ハッシュの古い定義は、時間を考慮していない。強固なハッシュは、コンテンツを認識することができるのみならず、時間（間隔）の識別もできなければならない。この理由から、本明細書においては、強固なハッシュに対し、次の定義を使用する。強固なハッシュとは、ＨＡＳ／ＨＶＳが認識するコンテンツの類似性に関し連続的である半ユニークビット−シーケンスを、マルチメディア・コンテンツの各基本的な時間単位に、関連付ける関数である。
【００１３】
言い換えれば、ＨＡＳ／ＨＶＳが、音声、ビデオすなわち画像の２つの部分を非常に類似していると識別する場合は、この関連付けられたハッシュも非常に類似していなければならない。特に、元のコンテンツのハッシュと圧縮されたコンテンツのハッシュは、類似していなければならない。さらに、重なったフレームに対してハッシュワードを計算する場合も、ハッシュワードは類似していなければならない。すなわち、ハッシュは、ローパス特性を有していなけらばならない。一方、２つの信号が、実際に、異なるコンテンツを表している場合、この強固なハッシュは、２つの（半ユニーク）信号を区別することが可能でなくてはならない。このことは、典型的な暗号ハッシュに対する衝突要件と類似している。ハッシュ関数に必要な強固さは、ハッシュ関数を、強固な特徴（属性）、すなわち、処理に対して相当程度変化しない特徴から導出することによって達成される。強固さは、誤りビットの数とビットの合計数との比として定義されるビットエラーレート（ＢＥＲ）によって表すことができる。
【００１４】
強固なハッシングによって、多くの興味深いアプリケーションの基礎であるコンテンツの識別が、可能になる。マルチメディア・データベース内のコンテンツ認識の具体例を考察する。ある人がある映画の一場面を見ていて、その場面がどの映画からのものかを知りたい場合を仮定してみる。見つけ出す一つの方法は、その場面を、データベース内のすべての映画の同じサイズのすべてのフラグメントと、比較することである。データベースが大きい場合には、これが、完全に実行不可能であることは、明らかである。すなわち、ビデオ場面が短い場合であっても、それは、大量のバイトによって表現されているので、基本的には、これらを全てのデータベースと比較しなければならない。したがって、これが機能するためには、容易にアクセス可能な大量のデータを格納させる必要があり、かつ、これらのデータのすべてを、識別すべきビデオ場面と比較しなければならない。したがって、格納の問題（データベース）と計算の問題（大量のデータの突き合わせ）の両方が存在する。強固なハッシングは、ビデオ場面を表現するために必要なビット数を減らすことによって、両方の課題を解決する。
すなわち、相対的に、格納させる必要があるビット数は少なくなり、かつ使用する必要があるビット数も少なくなる。
【００１５】
まず、音声信号の強固なハッシングを説明する。この音声信号は、４４．１ｋＨｚのサンプル周波数（ＣＤ品質）でサンプル化されたモノラル音声であると仮定する。音声がステレオの場合、２つの選択肢がある。すなわち、ハッシュ信号を左と右のチャンネルに対して別々に抽出する選択肢と、ハッシュ信号を抽出する前に、左と右のチャンネルを追加する選択肢である。
【００１６】
音声が（秒オーダーの）短い断片しかない場合でも、それが何の歌なのかを知りたい場合がある。音声は、音声サンプルの終わりのない流れとみなすことができるため、音声信号を時間間隔またはフレームに細分化し、かつ、すべてのフレームに対してハッシュワードを計算する必要がある。
【００１７】
データベース内でハッシュを突き合わせようとする場合、フレームの境界を決定できないことが、頻繁にある。音声ハッシュには、特に、この同期化の問題が、該当する。この問題は、この信号を重なったフレームに分割することによって、解決される。重ねることによって、隣接する各フレームのハッシュワードが、一定量の相関を有することが可能となる。言い換えれば、ハッシュは、時間に対してゆっくりと変化する。
【００１８】
図１は、本発明に従って、音声ハッシュ信号を生成するための装置の実施例の線図である。音声信号は、後の各操作の複雑さを軽減させ、かつこの操作を人間の音声体系に最も関連した３００〜３０００ Ｈｚの周波数範囲に制限するために、まずダウンサンプラー１１でダウンサンプル化される。
【００１９】
フレーミング回路１２において、音声信号はフレームに分割される。このフレームは、１６３８４サンプル（
2004519015.tif 000003
秒）の長さ、および３１／３２の重なり率を有するハニング窓によって重み付けされる。この重なりは、後の各フレームの間においてハッシュワードの相関性が高くなるように選択される。あらゆるフレームのスペクトル表現は、フーリエ変換回路１３によって計算される。次のブロック１４において、（複雑な）フーリエ係数の絶対値（振幅）が計算される。
【００２０】
バンド分割ステージ１５において、この周波数スペクトルは、ある数（例えば、３３）のバンドに分割される。このことは、図１において、それぞれが、個々のバンドのフーリエ係数を選択するセレクタ１５１によって線図的に示されている。この装置の望ましい実施例の場合、ＨＡＳもほぼ対数関数的なバンドに演算するので、このバンドは、対数関数的な間隔を有する。バンドをこのように選択することによって、ハッシュは、圧縮やフィルタリングなどの処理の変化による影響を受けにくくなる。
この好ましい実施例の場合、第一のバンドは３００Ｈｚから開始し、かつどのバンドも、１つの楽音のバンド幅を有する（すなわち、バンド幅は、
2004519015.tif 000004
／バンドの割合で増加する）。図２は、あるフレームのスペクトル２０１と、それの対数間隔で配置されているバンド２０２への細分の一例である。
【００２１】
次いで、すべてのバンドに対して、ある種の（必ずしもスカラーではない）特有な属性が計算される。属性の例は、エネルギー、調性、およびパワースペクトル密度の標準偏差である。一般的に、この選択された属性は、フーリエ係数の任意の関数とすることが出来る。どのバンドのエネルギーも、多種の処理に最も強固である属性であることが、実験的に実証されている。このエネルギー計算は、エネルギー計算ステージ１６において行われる。各バンドに対して、エネルギー計算は、そのバンド内におけるフーリエ係数の（二乗された）マグニチュードの和を計算する、ステージ１６１を有する。
【００２２】
フレームごとに２進のハッシュワードを得るために、強固な属性は、次いで、ビットに変換される。このビットは、おそらく異なっているフレームの強固な属性の任意の関数を計算し、次に、この関数を閾値と比較することによって、割り当てることができる。この閾値自体が、この強固な属性値の他の関数の結果である場合もあろう。
【００２３】
本装置の場合、ビット導出回路１７は、バンドのエネルギーレベルをバイナリハッシュワードに変換する。単純な実施例の場合、この導出ステージは、バンドごとに１ビット生成する。例えば、エネルギーレベルが、ある閾値より高い場合は、「１」を１つ生成し、かつエネルギーレベルが当該閾値より低い場合は、「０」を１つ生成する。閾値は、バンドごとで異なる。これに代えて、エネルギーレベルがその隣のエネルギーレベルより大きい場合、バンドにはハッシュビット「１」が割り当てられ、小さい場合は、ハッシュ・ビット「０」が割り当てられる。本実施例は、後者の代替手段をさらに改良したバージョンを使用する。音声信号の主要な単一周波数が、連続するフレームに対して同一のハッシュワードを生成しないように、時間に対する振幅の変化も考慮される。より詳しくは、あるバンドには、そのエネルギーレベルがその隣のエネルギーレベルより大きく、かつ、これが以前のフレームでも同様の場合、ハッシュビット「１」が割り当てられ、それ以外の場合、ハッシュビットには「０」が割り当てられる。フレームｎのバンドｍのエネルギーをＥＢ（ｎ，ｍ）と表記し、かつ、フレームｎのハッシュワードＨのｍ番目のビットをＨ（ｎ，ｍ）と表記すると、導出回路１７は、次式によって、ハッシュワードのビットを生成する。
2004519015.tif 000005
【００２４】
この目的のために、ビット導出回路１７は、バンドごとに、第一減算器１７１、フレームディレイ１７２、第二の減算器１７３、およびコンパレータ１７４を有する。音声フレームのスペクトルの３３のエネルギーレベルは、このようにして、３２ビットハッシュワードに変換される。連続するフレームのハッシュワードは、コンピュータ２０がアクセスすることができるバッファ１８に、最終的に格納される。このコンピュータは、データベース２１内の多数の元の曲の強固なハッシュを格納する。
【００２５】
次の動作で、同じ装置が、未知のオーディオクリップのハッシュを計算する。図３の参照番号３１は、データベース２１に格納されているオーディオクリップの、２５６個の連続する重なった音声フレーム（
2004519015.tif 000006
秒）のハッシュワードを示す。この図において、各行は、３２ビットのハッシュワードであり、白色の画素はハッシュワードの「１」ビットを表し、黒い画素は「０」ビットを表し、かつ時間は上から下へと進行する。参照番号３２は、３２ｋＢｉｔ／ｓでＭＰ３圧縮した後の同じオーディオクリップから抽出されたハッシュワードを示す。理想的には、この２つのハッシュブロックは同一であるべきだが、圧縮したために、いくつかのビットは異なっている。この違いは、図３において３３と表記される。
【００２６】
次に、画像またはビデオ信号の強固なハッシュについて説明する。この場合にも、強固なハッシュは、情報信号の特有な特徴から導出される。尋ねるべき第一の疑問は、ハッシュワードを決定する当該の特徴を、どのドメインで抽出するかということである。周波数ドメインが知覚的な特性を最適に表す音声とは対照的に、使用すべきドメインが明確でない。複雑さに関する理由のために、ＤＣＴまたはＤＦＴ変換のような複雑な動作は、避けることが好ましい。したがって、空間−時間ドメインの特徴が計算される。さらに、大半の圧縮ビデオストリームからも容易に特徴を抽出できるようにするために、ブロックに基づくＤＣＴ係数から容易に計算することができる特徴が選択される。
【００２７】
これらの考察に基づくと、この好ましいアルゴリズムは、相対的に大きな画像領域全体で計算される平均および分散などの、単純な統計値に基づいている。この領域は、かなり単純な方法で選択される。すなわち、画像フレームは、６４ｘ６４画素の正方ブロックに分割される。特徴は、輝度成分から抽出される。しかしながら、これは基本的な選択ではない。すなわち、クロミナンスの成分を使用することもできる。実際のところ、ハッシュビットの数を増大させる最も容易な方法は、ハッシュビットを、輝度から抽出する場合と同様の方法で、クロミナンス成分から抽出することである。
【００２８】
図４は、ビデオ信号を識別するハッシュ信号を、本発明に従って生成するための装置のブロックダイヤグラムである。この装置は、連続するビデオ信号のフレームを受信する。各フレームは、Ｍ＋１ブロックに分割される（４１）。これらの各ブロックごとに、画素の輝度値の平均が計算される（４２）。フレームｐのブロックｋの平均輝度は、ｋ＝０，．．．，ＭをＦ（ｐ，ｋ）と表記される。
【００２９】
ハッシュをグローバルなレベルと輝度のスケールから独立させるために、２つの連続したブロック間の輝度差が計算される（４３）。さらに、時間方向におけるハッシュワードの相関性を減少させるために、連続フレームにおける空間微分の平均輝度値の差も計算される（４４、４５）。換言すれば、単純な空間−時間２ｘ２ Ｈａａｒフィルタが、平均輝度に適用される。結果の符号は、フレームｐのブロックｋに対して、ハッシュビットＨ（ｐ，ｋ）を構成する（４６）。数学的な表記は、次の通りである。
2004519015.tif 000007
【００３０】
この例では、各フレームは、６４ｘ６４のサイズの３３ブロック（すなわちＭ＝３２）に分割される。完全なハッシュＨは、３０の連続するフレームから抽出されたビットにより構成されている。各々が３２ビットの３０個のハッシュワード（９６０ビット）により構成される、このようなハッシュブロックは、以下に示されるように、フォルスポジティブの確率（ｆａｌｓｅ ｐｏｓｉｔｉｖｅ ｐｒｏｂａｂｉｌｉｔｙ）が、十分に小さくなる。典型的な元のハッシュブロックを、図５の５１に表す。図中、黒と白はそれぞれ、「０」と「１」に対応している。同じデータの、対応するハッシュ・ブロックを水平に９４％まで拡大したものを、参照番号５２で示す。番号５３は、ハッシュブロック５１と５２との差を表す。この場合、ビットエラー率は１１．３％に等しい。誤りビットが、時間（垂直）方向に非常に大きい相関性を有することは、注目される。
【００３１】
次に、抽出されたハッシュブロックを、大きなデータベースのハッシュブロックに突き合わせる処理について説明する。これは、不完全な突き合わせ（抽出されたハッシュワードがビットエラーを有している場合があることに留意）がＮＰ完全であることが周知であるので、重要な作業である。データベースには、約５分の曲が１００，０００種類（≡２５０００ハッシュワード／曲）格納される。２５６個のハッシュワードを有するハッシュブロック（例えば、図３のハッシュブロック３２）は、未知のオーディオクリップから抽出されたものと仮定される。次に、抽出されたハッシュブロックが、格納されている１００，０００曲のどれに最も一致するかを、決定すべきである。したがって、抽出されたハッシュブロック、すなわち、ビットエラー率（ＢＥＲ）が最小であり、またはは、これに代えて、ＢＥＲが特定の閾値よりも低いハッシュブロックにもっとも似ている、１００，０００曲中の１曲中のハッシュブロックの位置を見つけ出さなければならない。この閾値は、フォルスポジティブの率、すなわち、歌がデータベースから不正確に識別される率を、直接的に決定する。
【００３２】
２つの３秒のオーディオクリップの（または２つの３０フレームのビデオシーケンス）は、２つの導出されたハッシュブロックＨ１とＨ２との間のハミング距離が、特定の閾値Ｔより小さい場合、同様であると宣言される。この閾値Ｔは、フォルスポジティブの率Ｐｆ、すなわち２つのオーディオクリップ／ビデオシーケンスが等しいと不正確に（すなわち人間が目で見て不正確に）表される率を、直接的に決定する。すなわち、Ｔが小さいほど、確率Ｐｆは小さくなる。一方、ある小さな値Ｔは、フォルスネガティブの確率Ｐｎ、すなわち２つの信号は「等しい」が、そのように識別されない確率に対して、否定的な影響を与えるであろう。この閾値Ｔという選択肢を分析するために、ハッシュ抽出工程が、ｉ．ｉ．ｄ．（独立であり、かつ同様に分散している）ビットを生ずると仮定する。従って，ビットエラーの数は、パラメータ（ｎ，ｐ）を有する二項分布を有するであろう。このパラメーターにおいて、ｎは抽出されたビットの数に等しく、かつ、ｐ＝（０．５）は「０」または「１」ビットが抽出される確率である。我々の用途においては、ｎ（音声用の３２ｘ２５６＝８１９２、かつビデオ用の３２ｘ３０＝９６０）が大きいため、二項分布は、平均μ＝ｎｐおよび標準偏差
2004519015.tif 000008
を用いた通常の分布によって、近似値を求めることができる。ハッシュブロックＨ１が与えられた場合、無作為に選択されたハッシュブロックＨ２が、Ｈ１に対してＴ＝αｎ未満のエラーを有する確率は、
2004519015.tif 000009
によって求められる。
【００３３】
しかしながら、実際には、強固なハッシュは、時間軸に沿って高い相関性を有する。これは、基本となるビデオ・シーケンスの大きな時間相関性、または音声フレームの重なりに起因する。実験は、誤りビットの数は通常分散するが、標準偏差はｉ．ｉ．ｄ．の場合よりも約３／２倍大きいことを示している。したがって、この換算係数３／２を含めるために、式（１）は次のように変更される。
2004519015.tif 000010
【００３４】
実験時に使用したＢＥＲの閾値は、α＝０．２５である。このことは、ハッシュブロックが同じ歌から発生していることを決定するためには、８１９２ビットのうち、２０４８未満のビットエラーしか発生してはならないことを意味する。この場合、ビットエラーは、ｎｐ＝４０９６の平均μ、と
2004519015.tif 000011
の標準偏差σを有する正規分布を有する。したがって、この選択された閾値の設定は、１５．２σというフォルスアラームの確率（ｆａｌｓｅ ａｌａｒｍ ｐｒｏｂａｂｉｌｉｔｙ）に対応する。したがって、フォルスアラームの確率は、１．８・１０−５２に等しい。しかしながら、同様のハッシュワードを有する音楽（例えば、２人の異なるピアニストが演奏するモーツァルトの一曲）がデータベースに含まれている場合、実際にはフォルスアラームの確率がより高くなることは、留意すべきである。
【００３５】
抽出されたハッシュブロックのデータベース内におけるサーチは、ブルートフォース突き合わせによって行うことができる。これには、約２５億（＝２５０００ｘ１００，０００）回の突き合わせが必要となる。さらに、データベースの大きさに応じて、突き合わせの数は線形的に増加する。
【００３６】
本発明の一態様に従って、コンピュータ２０は、データベース２１内の対応する歌を見つけ出すためのより効率的な方策を使用する。図６は、コンピュータが行う動作のフローチャートである。データベース内に元の歌が格納されると直ちに、コンピュータはステップ６０のルックアップテーブル（ＬＵＴ）を更新する。ＬＵＴは、図１では、分離したメモリ２２として示されているが、実際には、メモリ２２は大きなデータベース用のメモリ２１の一部分であることが適切である。図７に示されるように、ＬＵＴ ２２は、可能な３２ビットの各ハッシュワードに対するエントリを有する。ＬＵＴの各エントリは、各歌と、この歌の中において個々のハッシュワードが発生する位置とを指す。ハッシュワードは、多数の歌の中の多数の位置で発生しうるので、歌ポインタはリンクされたリスト内に格納される。このようにして、ＬＵＴは多数の候補曲を生成することができる。データベース内に、限られた数の歌しかない場合、２３２個のエントリを含むＬＵＴが非実用的となりうることは注目される。このような場合、ハッシュ表およびリンクリストを用いてＬＵＴを実行することは有利である。図７の参照番号７０は、未知のオーディオクリップ（例えば、図３のハッシュブロック３２）から抽出された２５６個のハッシュワードの１ブロックを示している。
【００３７】
突き合わせ方法の第一の実施例の場合、時折、単一のハッシュワードがビットエラーを全く有さないことが、仮定されるであろう。ステップ６１においては、単一のハッシュワードＨ（ｍ）が、ハッシュブロックから選択され、かつデータベースに送られる。最初、これは、抽出されたハッシュブロックの最後のハッシュワードＨ（２５６）になろう。図７に示される具体例の場合、これはハッシュワード０ｘ０００００００１である。データベース内のＬＵＴは、歌１の特定の位置を指す。この位置が、位置ｐであると仮定する。ステップ６２において、コンピュータは、抽出されたハッシュブロックと、歌１の位置ｐ−２５５から位置ｐ（図７において７１と示される）に至るハッシュワードのブロックとの間のＢＥＲを計算する。ステップ６３において、ＢＥＲが低い（＜０．２５）か高いかが確認される。ＢＥＲが低い場合、抽出されたハッシュワードが歌１からのものである可能性が高い。ＢＥＲが高い場合、歌がデータベースに存在しないか、この単一のハッシュワードＨ（ｍ）が誤りを含んでいるかのいずれかである。後者が、この例に該当すると見なされる。次に、別の単一のハッシュワードが、ステップ６４において選択され、ＬＵＴにおいて調べられる。図７において、今度は、最後から２番目の単一のハッシュワードＨ（２５５）が調べられる。このハッシュワードは、歌２において発生すると思われる。入力ブロック７０と格納されたブロック７２との間のＢＥＲは、今度は０．２５未満であると考えられるため、歌２がオーディオクリップの出所となる歌として識別される。格納されたブロック５２の最後のハッシュワードが０ｘ００００００００であることは、注目される。明らかに、前に選択されたハッシュワード０ｘ００００００１は、１つのビットエラーを有していた。
【００３８】
コンピュータはこのように、一度に単一のハッシュワードしか調べず、かつこのような単一のハッシュワードにはビットエラーが全くないことが時折あると仮定する。抽出されたハッシュブロックのＢＥＲは、次に、候補歌の対応する（時間軸上の）ハッシュブロックと比較される。ＢＥＲが最も低い候補歌の題名は、最も低いＢＥＲが閾値（ステップ６５）よりも低ければ、抽出されたハッシュワードの出所となる歌として、選択されるであろう。選択されない場合、データベースは、抽出されたハッシュブロックが見つからなかったと、報告するであろう。次に、もう一つの単一のハッシュワードが試される。単一のハッシュワードが１つも成功しない場合（ステップ６６）、データベースは、データベース（ステップ６７）には候補歌がないとの報告による応答を行う。
【００３９】
上述の方法は、抽出されたハッシュワードが、時折ビットエラーを全く含んでいない、すなわち、対応する格納されたハッシュワードと完全に等しい、という仮定に依存している。広範囲な実験によると、これが、大半の音声において、１秒に２、３回定期的に発生することが判明している。このことは、例えば、 図３Ｂの抽出されたブロックを形成する２５６個のハッシュワード中のビットエラーの数を示す図８に示されている。この３秒のオーディオクリップでは、１３個のハッシュワードが、一切のビットエラーなしに発生する。
【００４０】
しかしながら、音声が厳格に処理される場合、ビットエラーが全く無いハッシュワードが発生することは、ありえない。この場合、歌の題名を以前の方法でサーチすることはできない。この目的のために、突き合わせ方法の別の実施例を説明する。この方法は、抽出されたハッシュワードをデータベース内で発見するために、ハッシュ抽出アルゴリズムのソフト情報を使用する。ソフト情報とは、ビットの信頼性、または、ハッシュビットが正確にサーチされた確率を意味するものと理解すべきである。この実施例の場合、ハッシュワードを抽出するための装置は、ビット信頼性決定回路を含む。ビット信頼性決定回路は、図１に示される音声ハッシュ抽出装置において、１９と表記される。ビット信頼性決定回路は、微分エネルギーのバンドレベルを、実数の形で受信する。この実数が閾値（この例ではゼロ）に非常に近い場合、各ハッシュビットは信頼できない。この数が、代わりに閾値から非常に離れている場合、各ハッシュビットは信頼できるハッシュビットである。信頼できるビットの数が固定されるように、閾値を固定したり制御することは可能である。
【００４１】
ビット信頼性決定回路１９は、すべてのハッシュビットの信頼性を決定し、かつこうして、抽出装置またはコンピュータ２０は、各ハッシュワードごとにもっとも有望な代替のハッシュワードの一覧を、生成することができる。この場合も、代替のハッシュワードのうち少なくとも１つが正確であると仮定することによって、曲名を正確にかつ容易に受けることができる。図９は、図３のハッシュブロック３２における２５６個すべてのハッシュワードに対して、ハッシュワードのどのビットがもっとも信頼できるかを示している。
【００４２】
図１０は、抽出されたハッシュブロックをデータベース内で発見する方法の本実施例において、コンピュータによって実行される動作のフローチャートである。上述の動作では、同じ参照番号が使用されている。この場合においても、ハッシュブロックの最後に抽出されたハッシュワード（０ｘ０００００００１、図７を参照）が最初に選択され、かつデータベース（ステップ６１）に送られる。データベース内のＬＵＴが、歌１の位置ｐを指す。抽出されたハッシュブロックと、歌１の対応するブロック７１との間のＢＥＲが計算される（ステップ６２）。一方、前の具体例から、ＢＥＲが高いことが分かる。ステップ１０１において、コンピュータは、今度はビット信頼性決定回路１９（図１）を調べ、かつ、この特定のハッシュワードでは、ビット０が最も信頼できないビットであることを知る。次に最も有望なハッシュワードの候補を、今度は、このビットをフリップして得ることができる。新規なハッシュワード（０ｘ００００００００）は、ステップ１０２のデータベースに送られる。図７に示されるように、ハッシュワード０ｘ００００００００は、データベース内の２つの可能な候補歌、すなわち歌１および歌２に至る。例えば、抽出されたハッシュワードが、今度は歌２のハッシュワードに対して低いＢＥＲを有する場合、歌２は抽出されたハッシュブロックの出所となる歌として識別される。そうでなければ、新しいハッシュワード候補が生成されたり、または、データベース内のそれぞれの歌を見出す試みのために、他のハッシュワードが用いられるであろう。この方策は、更なる代替の候補ハッシュワードが存在しないことが、ステップ１０３で判明するまで、続けられる。
【００４３】
一片のオーディオが、実際に特定の歌から生じていると識別されると、データベースは、全ての候補ハッシュワードを生成する前に、まず抽出されたハッシュワードをその歌に突き合わすことができる点は、注目される。
【００４４】
もっとも有望なハッシュワードのリストを生成するための非常に単純な方法は、全てのハッシュワードに、固定されているＮ個の最も信頼性が高いビット、および残留するビットのあらゆる可能な組合せを含めることである。３２ビット／ハッシュ、かつＮ＝２３を選択する場合、５１２個の候補のハッシュワードの一覧が必要となる。さらに、このことは、ハッシュワードの最も信頼性が低い９つのビットが誤っていると、音声の抜粋をもはや識別することができないことを意味する。これは、図６に示す事例の場合、前の方法における１３個の代わりに、１１７個のハッシュワードが、データベース内の歌への正確なポインタを生じることを意味する。
【００４５】
突き合わせ方法の別の実施例の場合、信頼性が高いとマークされているハッシュビットのみに基づいて、突き合わせが行われる。この方法は、受けたハッシュの信頼できないビットを、データベース内の対応するビットと比較する必要はないという洞察に基づいている。これは、はるかに少ないビットエラー率をもたらすが、これは、全ての必要な情報をデータベースに伝送させるために必要な、より複雑なサーチ戦略とより広いバンド幅という犠牲によって、もたらされる。
【００４６】
次に、強固なハッシュの２、３の用途を説明する。
−放送のモニタリング：ブロードキャスト監視システムは、２つの部分、すなわち、多数の歌のハッシュを含んでいる中央のデータベース、およびハッシュブロックを、例えば、無線局によって放送される音声から抽出するモニタリング・ステーションから成る。このモニタリング・ステーションが、抽出されたハッシュブロックを中央のデータベースに送信すると、データベースはどの歌が放送されたかを決定することができる。
−携帯電話の音声情報：バーである歌を聞いていて、その題名を知りたくなった場合を考えよう。先ず、自分の携帯電話を取り出し、音声ハッシュのデータベースに電話をかける。すると、この音声ハッシュのデータベースは、その歌を聞いて、ハッシュブロックを抽出する。次に、音声ハッシュのデータベースは、ハッシュ・ブロックをデータベース内で見出すと、歌の題名を報告する。
−連結内容（メディアブリッジ（ＭｅｄｉａＢｒｉｄｇｅ））：ディジマーク社（Ｄｉｇｉｍａｒｃ）は、現在、透かし技術に基づくメディアブリッジ（ＭｅｄｉａＢｒｉｄｇｅ）と呼ばれるアプリケーションを有している。この考えは、一片のマルチメディアの透かしが、ある特別な情報を得ることができるインターネット上の特定のＵＲＬにユーザーを導く、というものである。例えば、ある雑誌の広告に透かしを入れる。ウェブカメラの前でこの広告を掲げると、透かし検出器が透かしの鍵を抽出し、透かしの鍵はデータベースに送られる。したがって、このデータベースは、ユーザーがリダイレクトされるＵＲＬを含んでいる。同じアプリケーションは、強固なハッシング技法を用いる場合にも機能することができる。将来は、自分の移動テレビ電話を現実の物体に向ける人のことを考えつくかもしれない。その時、音声ハッシュ・データベースは、この物体に関する情報を、直接的に、あるいはインターネット上のＵＲＬを介して、報告する。
−マルチメディアの品質測定：高品質な元のコンテンツのハッシュワードがデータベースに記載されている場合、処理されたマルチメディア・コンテンツの抽出されたハッシュワードのＢＥＲを決定することによって、品質の尺度を得ることができる。
【００４７】
抽象的な観点から見ると、強固な音声ハッシュは、異なる周波数帯と時間に対してエネルギーを比較することによって、音声信号から抽出される。この手法の一般化は、ＬＴＩと非線形関数のいかなる縦続も考慮することである。特に強固なハッシュは、（ダイアディック）フィルタバンク（ＬＴＩオペレータ）を適用し、次いで、絶対語（非線形関数）を二乗しまたは取得し、次いで、時間および／またはバンドについて差分オペレータ（ＬＴＩオペレータ）を続け、最後に閾値化演算子を続けることによって、得ることもできる。慎重に設計された線形フィルタバンクを、初期の演算子として適用することによって、ＦＦＴの複雑さを回避できる。さらに、多くの圧縮エンジンは、線形フィルタバンクを初期相として有するため、特徴抽出を圧縮によって集積するオプションがある。
【００４８】
コンテンツを識別するため、強固なハッシュおよび電子透かしが、併用できることに、さらに注目すべきである。上述の方法、およびいくつかの透かし検出アルゴリズムは、いくつかの共通する初期処理ステップ、すなわちスペクトル表現の計算を有する。このことは、透かし検出および特徴抽出を、１つのアプリケーションにおいて容易に集積化できるという考え方に結びつく。したがって、サーチされた透かしおよびハッシュワードを、さらなる詳細な解析のために中央のデータベースに送ることによって、コンテンツの識別が可能になる。
【００４９】
要約すると、この開示された方法は、マルチメディア・コンテンツ、例えば、オーディオクリップのための強固なハッシュを生成する。オーディオ・クリップは、連続した（好ましくは、重なった）フレーム（１２）に分割される。各フレームごとに、周波数スペクトルはバンド（１５）へ分割される。各バンド（例えば、エネルギー）の強固な属性は、計算され（１６）、かつ個々のハッシュビットによって表わされる（１７）。オーディオクリップは、このように、各フレームごとに２進のハッシュワードの連結によって表現される。おそらく圧縮されている音声信号を識別するために、この音声信号から導出されるハッシュワードのブロックは、コンピュータ（２０）によって、大きなデータベース（２１）と突き合わせられる。このような突合せ戦略も、開示されている。有利な一実施例の場合、抽出処理は、どのハッシュビットが最も信頼できないかに関する情報（１９）をも提供する。これらのビットを著しくフリップすることによって、突合せ処理の速度および効率が向上する。
【図面の簡単な説明】
【図１】本発明に従って、オーディオ信号からハッシュ信号を抽出するための装置の実施例の回路線図である。
【図２】オーディオ信号スペクトラムの細区分を、対数的に間隔を置いたバンドに示す線図である。
【図３】オーディオクリップから抽出されたハッシュワードを示す線図である。
【図４】本発明に従って、ビデオ信号からハッシュ信号を抽出するための装置の実施例の回路線図である。
【図５】ビデオシーケンスから抽出されたハッシュワードを示す線図である。
【図６】本発明に従って、図１に示されるコンピュータによって実行される操作のフローチャートである。
【図７】図１に示されるコンピュータの操作を示す線図である。
【図８】図３に示される抽出されたハッシュブロックを形成するハッシュワード内の、ビットエラーの数のグラフである。
【図９】図３に示されるハッシュブロックのハッシュワードの最も信頼できるビットのグラフである。
【図１０】本発明のさらなる実施例に従って、図１に示されるコンピュータによって実行される操作のフローチャートである。
【図１】
2004519015.tif 000012
【図２】
2004519015.tif 000013
【図３】
2004519015.tif 000014
【図４】
2004519015.tif 000015
【図５】
2004519015.tif 000016
【図６】
2004519015.tif 000017
【図７】
2004519015.tif 000018
【図８】
2004519015.tif 000019
【図９】
2004519015.tif 000020
【図１０】
2004519015.tif 000021
【国際公開パンフレット】
2004519015.tif 000022
2004519015.tif 000023
2004519015.tif 000024
2004519015.tif 000025
2004519015.tif 000026
2004519015.tif 000027
2004519015.tif 000028
2004519015.tif 000029
2004519015.tif 000030
2004519015.tif 000031
2004519015.tif 000032
2004519015.tif 000033
2004519015.tif 000034
2004519015.tif 000035
2004519015.tif 000036
2004519015.tif 000037
2004519015.tif 000038
2004519015.tif 000039
2004519015.tif 000040
2004519015.tif 000041
2004519015.tif 000042
2004519015.tif 000043
2004519015.tif 000044
2004519015.tif 000045
2004519015.tif 000046
【国際調査報告】
2004519015.tif 000047
2004519015.tif 000048
2004519015.tif 000049