(57)【要約】【課題】  フィンガープリントのデータベースを効率よくサーチすることを可能にするための方法および装置を提供すること。【解決手段】  方法及び装置は、それぞれの情報信号を識別するデータベースに格納されているフィンガープリントと、各々のフィンガープリント・ブロックが情報信号の少なくとも一部を表している、入力フィンガープリント・ブロックの組とのマッチングに関して記載される。この方法は、当該入力フィンガープリント・ブロックの組の第1のフィンガープリント・ブロックを選択すること（10）、および、前記選択されたフィンガープリント・ブロックにマッチする当該データベースにおける少なくとも一つのフィンガープリント・ブロックを検出することを含む（20,40）。それから、更なるフィンガープリント・ブロックが、当該第1の選択されたフィンガープリント・ブロックの所定の位置で、当該フィンガープリント・ブロックの組から選択される（60）。対応するフィンガープリント・ブロックは、それから、検出されたフィンガープリント・ブロックと関連する、同じ所定の位置でデータベースに位置決めされ（70）、かつ、位置を決められたフィンガープリント・ブロックが選択された更なるフィンガープリント・ブロックにマッチングされる場合、それは、決定される（80）。
2006506659.tif 000002
【特許請求の範囲】
【請求項１】
それぞれの情報信号を識別するデータベースに格納されているフィンガープリントと、各々のフィンガープリント・ブロックが情報信号の少なくとも一部を表している、入力フィンガープリント・ブロックの組とのマッチングの方法であって、
当該入力フィンガープリント・ブロックの組の第1のフィンガープリント・ブロックを選択するステップと、
前記選択されたフィンガープリント・ブロックにマッチする当該データベースにおける少なくとも一つのフィンガープリント・ブロックを検出するステップと、
当該第1の選択されたフィンガープリント・ブロックと関連する所定の位置で当該フィンガープリント・ブロックの組から更なるフィンガープリント・ブロックを選択するステップと、
当該検出されたフィンガープリント・ブロックと関連する所定の位置で当該データベースの少なくとも一つの対応するフィンガープリント・ブロックを位置決めするステップと、
当該位置決めされたフィンガープリント・ブロックが当該選択された更なるフィンガープリント・ブロックにマッチするか否かを決定するステップとを備える、マッチングの方法。
【請求項２】
更なるフィンガープリント・ブロックを選択するステップと、
当該データベースにおける対応するフィンガープリント・ブロックの位置決めをするステップと、
当該位置決めされたフィンガープリント・ブロックが、前記第1の選択されたフィンガープリント・ブロックに関連する異なる所定の位置に対する当該選択された更なるフィンガープリント・ブロックにマッチングさせるか否かを決定するステップとを、
反復的に繰り返すことを更に備えている、請求項1に記載の方法。
【請求項３】
前記所定の位置は、隣接した位置であることを特徴とする請求項1記載の方法。
【請求項４】
当該検出ステップにおけるマッチは、前記フィンガープリント・ブロック間の差分の数が第一の閾値未満の場合、マッチが、発生したと仮定され、かつ、
当該決定ステップにおけるマッチは、前記フィンガープリント・ブロック間の差分の数が第二の閾値未満の場合、マッチが、発生したと仮定される、請求項１に記載の方法。
【請求項５】
当該第2の閾値は、当該第1の閾値と異なる、請求項４に記載の方法。
【請求項６】
情報信号を受けるステップと、
前記情報信号を区分に分けるステップと、
各々の区分に対するフィンガープリント・ブロックを算出することによって当該入力ブロックを生成するステップとを、
更に備える、請求項１に記載の方法。
【請求項７】
前記情報信号を類似のコンテンツ部分に分けるステップと、
各々の部分に対する入力フィンガープリント・ブロックを生成するステップと、
当該ブロックの各々を識別するために請求項1に記載されている各方法ステップを繰り返すステップとを備える、情報信号に対するロギング報告を生成する方法。
【請求項８】
当該情報信号が、音声信号を備え、かつ、各々の区分が、歌曲の少なくとも一部に対応する、請求項７に記載の方法。
【請求項９】
請求項1に記載の方法を実行するように構成されているコンピュータプログラム。
【請求項１０】
請求項９に記載のコンピュータプログラムを備える記録担体。
【請求項１１】
請求項9に記載のコンピュータプログラムをダウンロードさせることが可能な方法。
【請求項１２】
それぞれの情報信号を識別するデータベースに格納されているフィンガープリントと、各々のフィンガープリント・ブロックが情報信号の少なくとも一部を表している、入力フィンガープリント・ブロックの組とをマッチするように構成されている装置であって、
当該入力フィンガープリント・ブロックの組の第1のフィンガープリント・ブロックを選択し、
前記選択されたフィンガープリント・ブロックにマッチする当該データベースにおける少なくとも一つのフィンガープリント・ブロックを検出し、
当該第1の選択されたフィンガープリント・ブロックと関連する所定の位置で当該入力ブロックの組から更なるフィンガープリント・ブロックを選択し、
当該検出されたフィンガープリント・ブロックと関連する所定の位置で当該データベースの少なくとも一つの対応するフィンガープリント・ブロックを位置決めし、
当該位置決めされたフィンガープリント・ブロックが当該選択された更なるフィンガープリント・ブロックにマッチするか否かを決定するように構成されている処理ユニットを備える装置。
【請求項１３】
それぞれの情報信号、および、各々の信号と関係するメタデータを識別するフィンガープリントを格納するように構成されているデータベースを更に備えている、請求項12に記載の装置。
【請求項１４】
情報信号を受信する受信器、および、当該情報信号から入力フィンガープリント・ブロックの当該組を生成するように構成されているフィンガープリントの生成器を、更に備えている、請求項12に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フィンガープリントと、データベースに格納されているフィンガープリントとのマッチングに適した方法および装置に関する。
【背景技術】
【０００２】
ハッシュ関数は、一般的に、大量のデータを要約しかつ検証するために一般的に用いられる暗号の世界において、用いられている。たとえば、MIT（マサチューセッツ工科大学）のアール・エル・リベスト（R L Rivest）教授によって開発されたMD5アルゴリズムは、入力として任意の長さのメッセージを有し、かつ、出力として前記入力の128ビットの「フィンガープリント」、「シグナチュア」または「ハッシュ」を発生する。2つの異なるメッセージが同じフィンガープリントを有することは、統計上、非常に起こりにくいと推測されていた。その結果、このような暗号フィンガープリント・アルゴリズムは、データ保全性を検証するために有用な方法となる。
【０００３】
多くの用途では、音声および／またはビデオ・コンテンツを含む、マルチメディア信号を識別することは、望ましい。しかしながら、マルチメディア信号は、しばしば、様々なファイル・フォーマットで伝達される。たとえば、WAV、MP3およびWindowsメディアのような、更には、様々な圧縮または品質レベルの、オーディオ・ファイルには、幾つかの異なるファイル・フォーマットが存在している。MD5のような暗号ハッシュは、イナリデータ・フォーマットに基づいていて、したがって、同じマルチメディア・コンテンツの異なるファイル・フォーマットに対して、異なるフィンガープリント値を提供するであろう。
【０００４】
これにより、暗号ハッシュがマルチメディア・データを要約することが不適当になり、同じコンテンツの異なる品質バージョンが同じハッシュまたは少なくとも類似のハッシュを産出することが、要求される。マルチメディア・コンテンツのハッシュは、堅牢なハッシュと称されているが（たとえば、ヤープ ハッシマ（Jaap Haitsma）、トン カークァ（Ton Kalker）、および、ジョブ オースティーブン（Job Oostveen）による、2001年9月イタリアのブレーシアでの、マルチメディア・インデックスに基づくコンテンツ2001（Content Based Multimedia Indexing 2001）の「コンテンツ認証に対する堅牢なオーディオ・ハッシュ法（Robust Audio Hashing for Content Identification）」）、ここでは、一般にマルチメディア・フィンガープリントと称する。
【０００５】
（コンテンツの許容可能な品質を保持する処理である限り）データ処理が相対的に不変であるマルチメディア・コンテンツのフィンガープリントは、堅牢な要約、堅牢なシグナチュア、堅牢なフィンガープリント、知覚的または堅牢なハッシュと称されている。堅牢なフィンガープリントは、ヒューマン・オーディオ・システム（HAS：Human Auditory System）および／またはヒューマン・ヴィジュアル・システム（HVS：Human Visual System）によって知覚されるような、オーディオヴィジュアルコンテンツの知覚的に必須の部分をキャプチャーする。
【０００６】
マルチメディア・フィンガープリントにおける一つの定義は、マルチメディア・コンテンツの基本的な時間ユニット毎に、HAS/HVSによって認識されるコンテンツの類似性に関して連続的な、ややユニークなビット・シーケンスと関連する関数である。換言すれば、HAS/HVSが非常に類似している音声、ビデオまたは画像の2つ部分を識別する場合、関連するフィンガープリントもまた、非常に類似しているはずである。特に、元のコンテンツおよび圧縮されたコンテンツのフィンガープリントは、類似しているはずである。他方、2つの信号が実際は異なるコンテンツを示す場合、堅牢なフィンガープリントは、2つの信号（ややユニーク）を区別することが可能なはずである。その結果として、マルチメディア・フィンガープリンティングは、多くの用途に対して基準となる、コンテンツの識別を可能にする。
【０００７】
たとえば、一つの用途には、多数のマルチメディアのオブジェクトのフィンガープリントは、各々のオブジェクトの関連メタデータとともに、データベースに格納されている。メタデータは、通常、オブジェクト・コンテンツに関する情報というよりはむしろ、オブジェクトに関する情報であり、たとえば、オブジェクトが歌曲のオーディオ・クリップである場合、メタデータは、曲名、アーティスト、作曲家、アルバム、クリップ長、および、歌曲のクリップ位置を含むであろう。
【０００８】
通常、単一のフィンガープリント値または項目は、完全なマルチメディア信号の全体に対して算出されることはない。その代わりに、多数のフィンガープリント（以下、サブフィンガープリントと称す。）は、マルチメディア信号の多数の部分の各々に対して算出され、たとえば、サブフィンガープリントは、各々のピクチャー・フレーム（または、ピクチャー・フレームの位置）または、音声トラックのタイム・スライスに対して算出される。その結果として、歌曲のような音声トラックのフィンガープリントは、単に、サブフィンガープリントのリストとなる。
【０００９】
フィンガープリント・ブロックは、情報源を確実に識別するために十分な情報（たとえば歌曲）を含む、一連（通常、256）のサブフィンガープリントである。原則として、歌曲のフィンガープリント・ブロックは、その歌曲のその後のサブフィンガープリントのいかなるブロックとすることもできる。通常、多数のフィンガープリント・ブロックは、各々のブロックが歌曲の隣接する区分を示す、各々の歌曲に対して形成されている。
【００１０】
マルチメディア・コンテンツがその後にいかなるメタデータもなく受信される場合、マルチメディア・コンテンツのメタデータは、マルチメディア・コンテンツの一つ以上のフィンガープリント・ブロックを計算することによって、かつ、データベースの対応するフィンガープリント・ブロックを検出することによって、決定することができる。
【００１１】
マルチメディア・コンテンツ自体というよりむしろ、フィンガープリント・ブロックのマッチングは、知覚的に無関係のものが、通常、フィンガープリント内で組み込まれないので、要求されるメモリ／ストレージがより少ないことから、ずっと効率がよい。
【００１２】
データベースに格納されているフィンガープリント・ブロックに対する、（受信されたマルチメディア・コンテンツから）抽出されたフィンガープリント・ブロックのマッチングは、データベースの各々のフィンガープリント・ブロックに対する、受信信号のフィンガープリント・ブロック（または、受信信号の長さが充分なフィンガープリント・ブロック）とマッチするために、強力なサーチによって、実行することができる。
【００１３】
ヤープ ハッシマ（Jaap Haitsma）、トン カークァ（Ton Kalker）、および、ジョブ オースティーブン（Job Oostveen）による、2001年9月イタリアのブレーシアでの、マルチメディア・インデックスに基づくコンテンツ2001（Content Based Multimedia Indexing 2001）の「コンテンツ認証に対する堅牢なオーディオ・ハッシュ法（Robust Audio Hashing for Content Identification）」という論文は、適切な音声フィンガープリントサーチ技術を記述している。これに記述されている計画は、全ての可能な限りのサブフィンガープリント値に対して、ルックアップ・テーブルを利用する。それぞれのサブフィンガープリント値のところで歌曲が発生するという理由から、テーブルの入力は、歌曲および位置を指す。抽出されたサブフィンガープリント値の各々に対して、ルックアップ・テーブルを検査することによって、要求されるフィンガープリント・ブロックのマッチングの範囲を効果的に限定するために、歌曲および位置の候補リストが、生成される。
【００１４】
本発明の実施例の目的は、フィンガープリントのデータベースを効率よくサーチすることを可能にするための方法および装置を提供することである。
【発明の開示】
【課題を解決するための手段】
【００１５】
第1の態様では、本発明は、それぞれの情報信号を識別するデータベースに格納されているフィンガープリントと、各々のフィンガープリント・ブロックが情報信号の少なくとも一部を表している、入力フィンガープリント・ブロックの組とのマッチングの方法であって、
当該入力フィンガープリント・ブロックの組の第1のフィンガープリント・ブロックを選択するステップと、
前記選択されたフィンガープリント・ブロックにマッチする当該データベースにおける少なくとも一つのフィンガープリント・ブロックを検出するステップと、
当該第1の選択されたフィンガープリント・ブロックと関連する所定の位置で当該フィンガープリント・ブロックの組から更なるフィンガープリント・ブロックを選択するステップと、
当該検出されたフィンガープリント・ブロックと関連する所定の位置で当該データベースの少なくとも一つの対応するフィンガープリント・ブロックを位置決めするステップと、
当該位置決めされたフィンガープリント・ブロックが当該選択された更なるフィンガープリント・ブロックにマッチするか否かを決定するステップとを備える。
【００１６】
このように、この方法でサーチすることは、サーチの範囲を著しく限定するために初期のマッチを用い、かつ、その後に対応する位置でフィンガープリント・ブロックをマッチングすることによって、サーチスピードを効果的に減少させ、および／または、堅牢性を増加させる。
【００１７】
別の態様においては、本発明は、
前記情報信号を類似のコンテンツ部分に分けるステップと、
各々の部分に対する入力フィンガープリント・ブロックを生成するステップと、
当該ブロックの各々を識別するために請求項1に記載されている各方法ステップを繰り返すステップとを備える、情報信号に対するロギング報告を生成する方法を提供する。
【００１８】
更なる態様では、本発明は、上記のような方法を実行するように構成されているコンピュータプログラムを提供する。
【００１９】
別の態様では、本発明は、上記のコンピュータプログラムを備える記録搬送装置を提供する。
【００２０】
更なる態様では、本発明は、上記のコンピュータプログラムをダウンロードさせることが可能な方法を提供する。
【００２１】
別の態様においては、本発明は、それぞれの情報信号を識別するデータベースに格納されているフィンガープリントと、各々のフィンガープリント・ブロックが情報信号の少なくとも一部を表している、入力フィンガープリント・ブロックの組とをマッチするように構成されている装置であって、
当該入力フィンガープリント・ブロックの組の第1のフィンガープリント・ブロックを選択し、
前記選択されたフィンガープリント・ブロックにマッチする当該データベースにおける少なくとも一つのフィンガープリント・ブロックを検出し、
当該第1の選択されたフィンガープリント・ブロックと関連する所定の位置で当該入力ブロックの組から更なるフィンガープリント・ブロックを選択し、
当該検出されたフィンガープリント・ブロックと関連する所定の位置で当該データベースの少なくとも一つの対応するフィンガープリント・ブロックを位置決めし、
当該位置決めされたフィンガープリント・ブロックが当該選択された更なるフィンガープリント・ブロックにマッチするか否かを決定するように構成されている処理ユニットを備える。
【００２２】
更なる本発明の特徴は、従属項において規定されている。
【発明を実施するための最良の形態】
【００２３】
本発明のより良い理解のため、および、同じ実施方法を示すことを実行に移すために、一例として、次に添付の概略図面が参照されるであろう。
【００２４】
通常、データベースに格納されているフィンガープリントとフィンガープリント・ブロックをマッチングすることによるフィンガープリント・ブロックの識別は、我々は（たとえば、ヤープ ハッシマ（Jaap Haitsma）、トン カークァ（Ton Kalker）、および、ジョブ オースティーブン（Job Oostveen）による、2001年9月イタリアのブレーシアでの、マルチメディア・インデックスに基づくコンテンツ2001（Content Based Multimedia Indexing 2001）の「コンテンツ認証に対する堅牢なオーディオ・ハッシュ法（Robust Audio Hashing for Content Identification）」に記述されているサーチ技術を用いることによる）完全なサーチと称するであろうことを要求する。
【００２５】
本発明は、後の（または、前の）フィンガープリント・ブロックが、同じ情報部分（たとえば、歌曲またはビデオクリップ）から生じる可能性が高い、という事実を活用する。その結果として、一度、一つのフィンガープリント・ブロックが識別されると、その後に、フィンガープリント・ブロックは、そのフィンガープリント・ブロックを、データベースの対応するフィンガープリント・ブロックにのみ、マッチを試みることによって、直ちに識別される。
【００２６】
図1は、本発明の第1の実施例による、このようなサーチを実行する際に関係するステップのフローチャートを例示する。
【００２７】
このサーチは、情報信号の異なる区分に対応する複数のフィンガープリントを含むデータベースが存在すると仮定する。たとえば、このデータベースは、多数の歌曲のフィンガープリント・ブロックを含み、各々のフィンガープリント・ブロックは、一連のサブフィンガープリントを備えているであろう。サブフィンガープリントは、歌曲の短い部分（たとえば11.8ミリ秒）に対応する。メタデータは、たとえば、曲名、歌長、実演家、作曲家、レコード会社などを示す各々の歌曲に関係している。
【００２８】
情報信号（たとえば、歌曲または歌曲の一部）が受信され、かつ、それが、歌曲、および／または、歌曲に関連するメタデータが識別されることが望ましい。これは、データベースのフィンガープリント・ブロックに対応する歌曲のフィンガープリント・ブロックにマッチングさせることによって達成される。
【００２９】
図1に示すように、第1のフィンガープリント・ブロックXは、情報信号の第1の位置xに対して算出される（ステップ10）。たとえば、歌曲では、これは、歌曲の3〜5秒間のタイム・スライスに関係あるかもしれない。
【００３０】
それから、データベースのフィンガープリント・ブロックのいずれが、算出されたフィンガープリント・ブロックXとマッチするか否かを識別するために、データベース内で、サーチが、実行される（ステップ20）。
【００３１】
このようなサーチ（ステップ20）は、データベース内の徹底的なサーチであろう。こうして、データベース内のすべてのフィンガープリント・ブロックを、反復的にフィンガープリント・ブロックXと比較する。これに代えて、ヤープ ハッシマ、トン カークァ、および、ジョブ オースティーブンによる、2001年9月イタリアのブレーシアでの、マルチメディア・インデックスに基づくコンテンツ2001の「コンテンツ認証に対する堅牢なオーディオ・ハッシュ法」という論文に記述されているように、最も適当なマッチを選択するために、ルックアップ・テーブルを、用いることができる。
【００３２】
信号タイムスロットのフレーミングの変化と、伝送および／または圧縮に起因する信号劣化とに起因して、フィンガープリント・ブロックXが、データベースに格納されている、いかなる単一のフィンガープリント・ブロックにも正確にマッチするであろうことは、好ましくない。しかしながら、フィンガープリント・ブロックXとデータベースのフィンガープリント・ブロックのいずれか一つとの間の類似性が十分に高い場合には、マッチは、発生すると仮定される（ステップ20）。
【００３３】
同等に、フィンガープリント・ブロックXとデータベースのフィンガープリント・ブロックと間の差違（たとえば、差分の数）を、比較することができる。この差違（二つのフィンガープリント・ブロック間の差分の数）が所定の閾値T1未満の場合、マッチが、発生したと仮定される。
【００３４】
フィンガープリント・ブロックのマッチングがデータベースに存在しないことが決定された場合（ステップ40）、フィンガープリント・ブロックは、信号内の新たな開始位置に対して算出され（ステップ50）、かつ、サーチが、再び実行される（ステップ20およびステップ40）。
【００３５】
1またはおそらくより多くの（2曲の歌曲が非常に類似の場合、これは発生するであろう。）フィンガープリント・ブロックが類似であることが検出される場合、データベースにおけるそれらの位置は、強調される。マッチの信頼性が十分に高い場合（ステップ55）、その結果は、記録され（ステップ90）、かつ、識別処理は、停止される。マッチに十分な信頼性がない場合、フィンガープリント・ブロックYは、信号の位置Xに隣接する位置（たとえば、音声信号の前の、または、後のタイム・スライス）に対して決定される（ステップ60）。
【００３６】
それから、データベースの対応する位置のフィンガープリント・ブロックは、フィンガープリント・ブロックYと比較される（ステップ70）。たとえば、フィンガープリント・ブロックYが、音声信号の直後の位置Xのタイムスロットに対して算出された場合、フィンガープリント・ブロックYは、フィンガープリント・ブロックXにマッチするフィンガープリント・ブロックの直後に発生すると期待されるであろうデータベースのフィンガープリント・ブロックと比較されるであろう。
【００３７】
さらにまた、フィンガープリント・ブロックのマッチングは、フィンガープリント・ブロック間の差違に関する所定の閾値（T2）を用いて実行されるであろう。閾値T2は、閾値T1と同じでもよいし、閾値T1よりも低くてもよい。しかしながら、閾値T2は、閾値T1よりも、わずかに高いことが好ましい。ブロックが同じ情報源に関係がない場合には、2つの隣接するフィンガープリント・ブロックが、データベースにおける2つの隣接するフィンガープリント・ブロックにマッチするであろうということは、ほとんど起こりえない。フィンガープリント・ブロックYがデータベース（これは、たとえば、新たな歌曲の演奏が始まった場合に、生じるであろう。）の対応するフィンガープリント・ブロックにマッチしない場合、完全なサーチは、フィンガープリント・ブロックYに対して実行することができる。
【００３８】
データベースにおけるマッチがない場合（ステップ80）、サーチ処理は、再開される。すなわち、完全なサーチは、今のブロックYのマッチに対してデータベース中で実行され（ステップ20）、かつ、その後のステップが、必要に応じて、繰り返し行われる。
【００３９】
データベースにおける対応するフィンガープリント・ブロックの一つ以上がマッチする場合（ステップ80）、マッチのいずれかが、高信頼性であるか否か（たとえば、情報信号を確実に識別するために、十分に優れたマッチであるか否か）が決定される（ステップ85）。マッチが高信頼性である場合、その結果は記録され（ステップ90）、かつ、識別処理は停止される。そうでない場合には、新たなフィンガープリント・ブロックYは、信号の次に隣接する（すなわち、前のフィンガープリント・ブロックYの位置と隣接する）タイムスロットに対して、決定される（ステップ60）。
【００４０】
上記の実施例は、単に一例としてのみ提供されていることはいうまでもない。たとえば、本実施例は、サーチが実行されるように、受信される情報信号、および、情報信号内の位置に対して算出されるフィンガープリント・ブロックに関して記述されている（ステップ10、50、60）。同様に、サーチ技術は、受信される情報信号と、信号の一つ以上の位置（すべての位置に至るまで）に対して（サーチの開始前に）算出され、後にサーチ処理で用いるために選択される、フィンガープリント・ブロックとに適用できる。これに代えて、情報信号の少なくとも一部に対応する単に2つ以上の単一のフィンガープリント・ブロックが、受信され、かつ、元の情報信号を識別するために、これらのフィンガープリント・ブロックを用いて、サーチが、実行される。
【００４１】
マッチングの閾値は、実施されるサーチに従って変化させることができる。
【００４２】
たとえば、情報信号が歪みそうであることが予想される場合には、閾値T1は、歪みに対してより堅牢としかつ偽陰性率を減少させるために、通常よりも高く設定することができる（2つのフィンガープリント・ブロックがマッチしないと決定された場合には、これらが情報信号の同じ部分に関するにも拘わらず、偽陰性率は、発生すると仮定される。）。
【００４３】
偽陰性率を減少させることにより、一般的には、より高い偽陽性率になる（この場合、マッチは、異なる情報に関係する、2つのフィンガープリント・ブロックの間で発生したとみなされる）。しかしながら、次の（または前の）フィンガープリント・ブロックがデータベースの対応するブロックにマッチするか否かを考慮することによって、擬陽性率を、全体的なサーチに対して減少させることができる。
【００４４】
上記方法は、情報信号からマッチングさせるために選択される各々の後のフィンガープリント・ブロックが前のフィンガープリント・ブロックに隣接（順に前にも後にもと）すると仮定されている。しかしながら、フィンガープリント・ブロックに対応する情報が、すでに選択されたフィンガープリント・ブロックの情報と隣接している場合にも、同じ方法を用いることができるということはいうまでもない。同様に、情報信号のフィンガープリント・ブロック間のいかなる既知の関係も、または、フィンガープリント・ブロックに関係する情報の位置も、この関係が、対応する位置に関するフィンガープリント・ブロックがデータベース内に位置されている限り、利用することができる。
【００４５】
たとえば、画像を備える情報信号では、サーチは、画像の対角線に沿って画像部分に対応するフィンガープリント・ブロックを用いて実行してもよい。本発明の実施例は、さらに、歌曲または他の音楽作品の、ワイヤレス放送またはワイヤライン放送をモニタするために用いることができる。たとえば、音声フィンガープリンティングシステムは、多数の歌曲から構成されているであろう、音声ストリームに存在している、全ての時間ブロック（通常、3〜5秒オーダー）に対するロギング報告を生成するために用いることができる。一つの部分に対するログ情報は、通常、歌曲、アーティスト、アルバム、および、歌曲の位置を含む。
【００４６】
モニタリング処理は、オフラインで実行することができる。すなわち、音声ストリーム（たとえば、無線局放送）のフィンガープリント・ブロックは、まず、たとえば音声の時間のフィンガープリント・ブロックを含むフィンガープリントファイルに記録される。音声のこの時間のログは、上記方法を用いることによって、効率的に生成することができる。
【００４７】
図2は、各々の歌曲がそれぞれの時間（t1、t2、t3）続く、3つの歌曲（歌曲1、歌曲2、歌曲3）に対するフィンガープリント・ブロックを含むフィンガープリントファイル90を例示する。フィンガープリント・ブロックの全ての完全なサーチを実行する代わりに、完全なサーチは、フィンガープリント・ブロックの小さい組のみ実行される（たとえば、91、95、および、98）。これは、平均的な歌長（約3〜4分）と、最小の歌曲長（最小の歌長が2分以上と知られていると仮定すると、たとえば、2分）とのいずれかの間隔を空けることが好ましい。通常、サブフィンガープリントは、約10ミリ秒間続くであろう、そして、フィンガープリント・ブロックは、3〜5秒間続くであろう。
【００４８】
小さい組（91、95、98）の中からフィンガープリント・ブロックが識別されると、隣接するブロック（92、93、96、97…）は、図1に関して記述されている方法を用いて、データベースの対応するフィンガープリント・ブロックとマッチングすることによってのみ、非常に効率的に識別することができる。対応ブロックは、識別されたブロックの歌曲の位置および識別された歌曲の歌長を用いて、識別することができる。マッチを実行した後に、未識別のブロックの組の中からの新たなフィンガープリント・ブロックが、完全なサーチのために選択される。全体の手順は、フィンガープリント・ブロックの全てがマッチによって明らかに識別されるまで、または、完全なサーチが既知でないフィンガープリント・ブロックを識別するまで、それ自体、繰り返される。
【００４９】
本発明の実施例は、リアルタイム・モニタリングに対しても用いることができることに、留意すべきである。たとえば、実施例は、歌曲が歌われると、ほぼ同時に、ラジオの歌曲を識別するために用いることができる。その場合、すでに識別されたフィンガープリント・ブロックの後のフィンガープリント・ブロックのみ、データベースの対応するブロックとマッチングするために、容易に用いることができる。しかしながら、若干の遅延が現在のブロックの受信と情報源の識別との間で可能とされる場合、多数の前のフィンガープリント・ブロックは、さらに、識別処理でも用いることができる。
【００５０】
図3は、情報信号のこのようなリアルタイム・モニタリングの実行に用いるのに適切な、本発明の実施例に対する方法のステップのフローチャートを示す。
【００５１】
図3においては、図1の場合と同じ方法ステップに対応する方法ステップには、同じ参照番号が、用いられている。
【００５２】
まず、フィンガープリント・ブロックXは、信号の位置Xに対して算出される（ステップ10）。それから、フィンガープリント・ブロックにマッチングするために、第1の閾値T1で、サーチが、データベース中で実行され（ステップ20）、かつ、その結果が、記録される（ステップ30）。
【００５３】
マッチングするブロックがデータベース内で検出されない場合（ステップ40）、フィンガープリント・ブロックが、情報信号内の新たな位置に対して、算出され（ステップ50）、かつ、そのサーチが再び実行される（ステップ20）。
【００５４】
一つ以上のマッチングさせているフィンガープリント・ブロックが、データベース内で検出される場合（ステップ40）、フィンガープリント・ブロックYは、情報信号の隣接した位置に対して算出される（ステップ60）。たとえば、情報信号が絶え間なく受信されている場合、フィンガープリント・ブロックYは、その信号の次に受信されるタイム・スライスに対して算出されるかもしれない。
【００５５】
ブロックYは、それから、第2の閾値T2で、データベースの対応するブロックと比較される（ステップ70）。換言すると、ブロックYは、ブロックXにマッチする、ステップ20で検出されたブロックの位置に隣接する情報信号における位置に関するデータベースにおける、これらのブロックとしか比較されない。
【００５６】
ブロックYがデータベースの対応するブロックのいずれともマッチしないことが検出された場合（ステップ80）、データベースの完全なサーチは、フィンガープリント・ブロックYに対して実行される（ステップ20）。
【００５７】
しかしながら、ブロックYがデータベースの対応するブロックの一つ以上にマッチングすることが検出された場合（ステップ80）、その結果が、記録され（ステップ90）、かつ、隣接する位置に対するフィンガープリント・ブロックが、算出され、かつ、処理が、繰り返される。図3に記述されている全体の処理は、完全なサーチでは未知である、フィンガープリント・ブロックの全てが明らかに識別され、または、決定されるまで、続けられる。
【００５８】
この実施例は、マッチが十分な可能性であるか否かを決定するために、データベースの対応するブロックで、情報信号のサーチされたフィンガープリント・ブロックのいずれかの間の類似性を検討することによって更に改良することができる。換言すれば、マッチングするブロックの経歴を、比較することができる。たとえば、フィンガープリント・ブロックXの適度なマッチは、データベース内で検出されていたかもしれない。これは、完全に、情報信号を識別するために、信頼性が十分高かったかもしれない。ブロックYの適度なマッチは、さらに、データベースで検出されていたかもしれない。その上、それだけで、情報信号を識別するために充分に信頼できるものと考えられないかもしれない。しかしながら、XとYとの両方のマッチが同じ情報信号と関係がある場合には、偶発する両方のマッチの可能性は、相対的に低い。すなわち、発生しているマッチの共用の可能性は、伝達されている情報信号を、確実に識別するのに十分優れている。
【００５９】
本発明は、複数のフィンガープリンティング法に関連して用いることに適している。たとえば、ハッシマほかの音声フィンガープリンティング法は、2001年9月イタリアのブレーシアでの、マルチメディア・インデックスに基づくコンテンツ2001の「コンテンツ認証に対する堅牢なオーディオ・ハッシュ法」に示されているように、音声信号の基本的な猶予時間のインターバルに対するサブフィンガープリント値を計算する。このように、音声信号は、フレームに分割され、その後に、各々のタイムフレームのスペクトル表示が、フーリエ変換によって計算される。この技術は、HASの動作を擬態する堅牢なフィンガープリント関数を提供する。すなわち、それは、リスナーによって理解されるであろう、音声信号のコンテンツに擬態するフィンガープリントを提供する。
【００６０】
このようなフィンガープリンティング技術では、図4に図示したように、音声信号と、音声信号を組み込んでいるビット・ストリームとのいずれか一方を、入力することができる。
【００６１】
ビット・ストリーム信号がフィンガープリントされる場合、符合化された音声信号を含むビット・ストリームは、ビット・ストリーム復号器110によって受けられる。ビット・ストリーム復号器は、音声信号を発生するために、完全に、ビット・ストリームを復号化する。それから、この音声信号は、フレーミング・ユニット120に渡される。
【００６２】
これに代えて、音声信号が、直接音声入力部 100で受けられ、かつ、フレーミング・ユニット120に渡されてもよい。
【００６３】
フレーミング・ユニットは、音声信号を一連の基本的な猶予時間のインターバルに分割する。後のフレームから生じるサブフィンガープリント値が概ね類似するように、時間インターバルが、重複することが好ましい。
【００６４】
それから、各々の猶予時間インターバル信号は、各々の時間猶予ウィンドウに対するフーリエ変換を算出する、フーリエ変換ユニット130に渡される。それから、絶対値算出ユニット140は、フーリエ変換の絶対値を算出するために用いられる。この算出は、ヒューマン・オーディオ・システム（HAS）が位相に対して相対的に反応しないように実行され、かつ、スペクトルの絶対値が、人間の耳によって聞こえるであろうトーンに対応するように保持されるのみである。
【００６５】
周波数スペクトル内の所定の一連の周波数帯域の各々に対する、別々のサブフィンガープリント値の算出を可能とするために、選択器151、152、…、158、159は、所望の帯域に対応するフーリエ変換係数を選択するように用いられる。それから、各々の帯域に対するフーリエ変換係数は、それぞれのエネルギー・コンピューティング・ステージ161、162、…、168、169に渡される。それから、各々のエネルギー・コンピューティング・ステージは、周波数帯域の各々のエネルギーを算出し、それから、計算されたエネルギーを、サブフィンガープリントビット（H(n,x)、ここで、xは、それぞれの周波数帯域に対応し、かつ、nは、重要な時間フレーム・インターバルに対応する。）を計算しかつそれを出力180に送るビット微分回路へ、渡す。最も単純な場合、ビットは、エネルギーが所定の閾値より大きいか否かを示すサインとなるであろう。単一の時間フレームに対応するビットを照合することによって、サブフィンガープリントは、各々の所望の時間フレームに対して計算される。
【００６６】
それから、各々のフレームに対するサブフィンガープリントは、フィンガープリント・ブロックを形成するために、バッファ190に格納される。バッファのコンテンツは、その後に、データベースサーチエンジン195によってアクセスされる。それから、データベースサーチエンジンは、ビット・ストリーム復号器110または直接音声入力100に入力された情報ストリーム（および／または、情報ストリームに関係したメタデータ）を効率的に識別するために、上記方法を用いて、バッファ190に格納されているフィンガープリント・ブロックを、データベースに格納されているフィンガープリント・ブロックにマッチさせるためのサーチを実行する。
【００６７】
本発明の上記の実施例は音声情報ストリームに関して記述されていたが、本発明が他の情報信号（特に、映像信号を含む、マルチメディア信号）に適用することができることは、いうまでもない。
【００６８】
たとえば、論文「ジェイ．スィ．オースティーブン、エイ．エイ．スィ． カークァ、ジェイ．エイ．ハッシマの「ディジタル・ビデオの映像ハッシュ法：応用及び技術」、米国サンディエゴでの、2001年7月31日〜8月3日の、SPIE、ディジタル画像処理XXIVは、移動画像シーケンスからの基本的な知覚的特徴に対して適切な技術について記述されている。
【００６９】
この技術は視覚的なフィンガープリンティングに関係するので、知覚的な特徴は、HVSによって見られるであろう特徴に関係する。すなわち、それは、HVSによって同じコンテンツと考えられるコンテンツに対して、同じ（または、類似の）フィンガープリント信号を発生することが目的である。提案されたアルゴリズムは、輝度素子と、代わりにピクセルのブロックに亘って計算されるクロミナンス素子といずれから抽出される特徴を考察するように見うけられる。
【００７０】
当業者であれば、特に記述されていない様々な実施態様が、本発明の範囲に含まれることを理解するであろうことは言うまでもない。たとえば、フィンガープリント・ブロック発生装置の機能性のみ記述されていたが、この装置が、ディジタル回路、アナログ回路、コンピュータプログラム、または、その組合せで実現することができるとはいうまでもない。
【００７１】
同様に、上記の実施例が特定のタイプの符合化方式に関して記述されていたが、本発明が他のタイプの符号化方式、特に、マルチメディア信号を伝えるときに、知覚的に本質的な情報に関する係数を含むものに適用することができることはいうまでもない。
【００７２】
読者の注目は、この出願に伴うこの明細書と同時またはこれより前に提出され、かつ、この明細書と共に公衆の閲覧に付された、全ての論文および文献に向けられる。そして、このような論文および文献のコンテンツは、全て、本願明細書に引用されたものとする。
【００７３】
この明細書（添付の特許請求の範囲、要約書、および、図面のいずれも含む）に開示された特徴の全て、および／または、そこに記載された方法および処理のステップの全ても、このような特徴および／またはステップの少なくともいずれかが相互に矛盾するという組み合わせを除き、如何様にも組み合わせることができる。
【００７４】
この明細書（添付の特許請求の範囲、要約書、および、図面のいずれも含む）に開示された各々の特徴は、明白に定まった他の方法を除き、同じ、等価、または類似の目的をもたらす代わりの特徴によって置き換えることができる。したがって、明白に定まった他の方法を除き、開示された各々の特徴は、一般的な一連の等価または類似の特徴のみ一例である。
【００７５】
本発明は、上記実施例の詳細に、限定されるものではない。本発明は、この明細書（添付の特許請求の範囲、要約書、および、図面のいずれも含む）に開示された特徴のいかなる新規なものにも、また、いかなる新規なもの組み合わせにも拡張することができ、また、そこに記載された方法および処理のステップにおける、いかなる新規なものまたはいかなる新規なもの組み合わせにも拡張することができる。
【００７６】
本明細書内では、用語「備える」は、他の要素またはステップを除外するものではく、用語「一つの（a）または（an）」は、複数を除外するものではなく、単一の処理装置または他のユニットは、特許請求の範囲に列挙された、いくつかの手段の機能を遂行することができるということは、言うまでもない。
【００７７】
本発明は、以下のように要約することができる。方法及び装置は、それぞれの情報信号を識別するデータベースに格納されているフィンガープリントと、各々のフィンガープリント・ブロックが情報信号の少なくとも一部を表している、入力フィンガープリント・ブロックの組とのマッチングに関して記載されている。この方法は、当該入力フィンガープリント・ブロックの組の第1のフィンガープリント・ブロックを選択すること、および、前記選択されたフィンガープリント・ブロックにマッチする当該データベースにおける少なくとも一つのフィンガープリント・ブロックを検出することを含む。それから、更なるフィンガープリント・ブロックが、当該第1の選択されたフィンガープリント・ブロックの所定の位置で、当該フィンガープリント・ブロックの組から選択される。対応するフィンガープリント・ブロックは、それから、検出されたフィンガープリント・ブロックと関連する、同じ所定の位置でデータベースに位置決めされ、かつ、位置を決められたフィンガープリント・ブロックが選択された更なるフィンガープリント・ブロックにマッチングされる場合、それは、決定される。
【図面の簡単な説明】
【００７８】
【図１】本発明の第1の実施例の方法のステップのフローチャートである。
【図２】本発明の一実施例によってサーチするための選択に対する音声信号の部分に対応するフィンガープリント・ブロックを例示するダイヤグラムである。
【図３】第2の実施例の方法のステップのフローチャートである。
【図４】入力情報ストリームからフィンガープリント・ブロック値を生成し、かつ、その後に、本発明の更なる実施例によってフィンガープリント・ブロックにマッチングさせるための構成のブロック線図である。
【符号の説明】
【００７９】
90  フィンガープリントファイル
91、95、98  フィンガープリント・ブロックの小さい組
92、93、96、97  隣接するブロック
100  直接音声入力部
110  ビット・ストリーム復号器
120  フレーミング・ユニット
130  フーリエ変換ユニット
140  絶対値算出ユニット
151、152、…、158、159  選択器
161、162、…、168、169  エネルギー・コンピューティング・ステージ
180  出力
190  バッファ
195  データベースサーチエンジン
【図１】
2006506659.tif 000003
【図２】
2006506659.tif 000004
【図３】
2006506659.tif 000005
【図４】
2006506659.tif 000006
【国際調査報告】
2006506659.tif 000007
2006506659.tif 000008
2006506659.tif 000009