(57)【要約】  量子化されたエネルギ値が評価され、メディア・シーケンスのコンテンツ要素の時間的に関連するグループを最初に表現する。エネルギ値は、最初の表現が分割されてなる複数の領域のマトリックスにわたり評価される。最初の表現は、ダウンサンプルされ、および／または、そのコンテンツから切り取られる。基底ベクトルのセットが、その値から次元空間において推定される。最初の表現は、別の次元空間の次の表現に変換される。次の表現は、基底ベクトルに基づいて、最初の表現を投影する。次の表現は、メディア・コンテンツ部分の幾何学的方向の変化においてメディア・コンテンツ部分に信頼性よく対応する。グループの他のメディア・コンテンツ部分に対し繰り返して、第１部分と他の部分の次の表現は、時間で平均化され、または、変換される。平均化された／変換された値は、速度変化においてコンテンツ部分に信頼性よく対応する。最初の表現は、空間のまたは変換された関連のある情報を含んでもよい。【選択図】図１
2011511489.tif 000002
【特許請求の範囲】
【請求項１】
ａ）ビデオメディア・コンテンツのシーケンスにおけるコンテンツ部分の時間的に関連するグループのビデオメディア・コンテンツ部分の第１表現について、前記第１表現が分割されてなる複数の領域のマトリックスに対してコンテンツ要素の量子化されたエネルギ値を評価する工程と；
ｂ）前記量子化されたエネルギ値から第１の次元空間の基底ベクトルのセットを推定する工程と；
ｃ）前記第１表現を、第２の次元空間のビデオメディア・コンテンツ部分の第２表現に変換する工程であって、前記第２表現は前記推定した基底ベクトルに基づく前記第１表現の投影を備える、工程とを備え；
メディア・フィンガープリントが前記第２表現に少なくとも一部は基づいて導き出される；
方法。
【請求項２】
前記第２表現は、前記ビデオメディア・コンテンツ部分の幾何学的方向の任意の変化において前記ビデオメディア・コンテンツ部分に信頼性よく対応する；
請求項１の方法。
【請求項３】
前記第１表現は、前記ビデオメディア・コンテンツ部分に関連する解像度より低い解像度にダウンサンプルされる；
請求項１の方法。
【請求項４】
前記第１表現は、前記ビデオメディア・コンテンツ部分から切り取られる；
請求項１の方法。
【請求項５】
前記ビデオメディア・コンテンツ部分の前記第１表現は：
前記シーケンスの１つ以上のビデオフレームの少なくとも１つのセクションに関連する空間領域表現；または、
前記シーケンスの前記１つ以上のビデオフレームの前記少なくとも１つのセクションに関連する変換された表現；
の１つ以上に関係する；
請求項１の方法。
【請求項６】
前記空間領域表現は、前記ビデオフレームに関連する空間解像度に関して粗い特徴を備える；
請求項５の方法。
【請求項７】
前記変換された表現は、変換関数により前記ビデオフレーム内の空間的に分散した情報から計算される；
請求項５の方法。
【請求項８】
前記変換関数は：
離散コサイン変換；
修正離散コサイン変換；
離散フーリエ変換；
ウェーブレット変換；または、
高速フーリエ変換；
の少なくとも１つを備える；
請求項５の方法。
【請求項９】
前記ビデオメディア・コンテンツ部分は、ビデオコンテンツ部分の前記時間的に関連したグループの第１の部分を備え；
前記時間的に関連したビデオコンテンツ部分のグループの少なくとも第２のビデオメディア・コンテンツ部分について工程ａ）からｃ）を繰り返す工程と；
ｄ）前記時間的に関連した部分のグループ内の前記第１のコンテンツ部分と前記第２のコンテンツ部分とを分離する時間期間にわたり前記第１のコンテンツ部分と前記第２のコンテンツ部分との前記第２表現の平均値を計算する工程とをさらに備える；
請求項１の方法。
【請求項１０】
前記第２表現の平均値は、前記メディア・コンテンツのシーケンスの速度の任意の変化において前記時間的に関連したコンテンツ部分のグループに信頼性よく対応する；
請求項９の方法。
【請求項１１】
ｅ）前記第２表現の平均値をランダムベクトルのセットに投影して投影値のセットを得る工程と；
ｆ）前記投影値のセットに閾値を適用する工程と；
ｇ）前記コンテンツ部分の時間的に関連するグループについてメディア・フィンガープリントを計算する工程とをさらに備える；
請求項９の方法。
【請求項１２】
前記メディア・フィンガープリントは、前記コンテンツ部分の時間的に関連するグループの幾何学的方向の任意の変化や前記メディア・コンテンツのシーケンスの速度の任意の変化において前記コンテンツ部分の時間的に関連するグループに信頼性よく対応する；
請求項１１の方法。
【請求項１３】
工程ｂ）は、前記ピクセル値に基づき特異値分解を計算する工程を備え；
前記基底ベクトルは、前記特異値分解に基づき推定される；
請求項１の方法。
【請求項１４】
前記基底ベクトルの第１は、前記ピクセル値の最大分散の軸に沿った方向であり、前記基底ベクトルの少なくとも第２は前記第１基底ベクトルに直交する；
請求項１３の方法。
【請求項１５】
前記ピクセル値は、前記領域それぞれに関連する平均値の合計を備え；
前記平均値は、前記領域からの前記メディア・コンテンツの少なくとも１つの特質のサンプルに関係する；
請求項１の方法。
【請求項１６】
ａ）ビデオメディア・コンテンツのシーケンスにおけるコンテンツ部分の時間的に関連するグループのビデオメディア・コンテンツ部分の第１表現について、前記第１表現が分割されてなる複数の領域のマトリックスに対してコンテンツ要素のエネルギ値を量子化する工程であって、前記第１表現は低解像度にダウンサンプルされ、前記メディア・コンテンツ部分から切り取られる、工程と；
ｂ）前記量子化されたエネルギ値から第１の次元空間の基底ベクトルのセットを推定する工程と；
ｃ）前記第１表現を、第２の次元空間のビデオメディア・コンテンツ部分の第２表現に変換する工程であって、前記第２表現は前記推定した基底ベクトルに基づく前記第１表現の投影を備える、工程とを備え；
前記ビデオメディア・コンテンツ部分の前記第１表現は：
前記シーケンスの１つ以上のビデオフレームの少なくとも１つのセクションに関連する空間領域表現；または、
前記シーケンスの前記１つ以上のビデオフレームの前記少なくとも１つのセクションに関連する変換された表現；
の１つ以上に関係し；
メディア・フィンガープリントが前記第２表現に少なくとも一部は基づいて導き出される；
方法。
【請求項１７】
前記第２表現は、前記ビデオメディア・コンテンツ部分の幾何学的方向の任意の変化において前記ビデオメディア・コンテンツ部分に信頼性よく対応する；
請求項１６の方法。
【請求項１８】
前記空間領域表現は、前記ビデオフレームに関連する空間解像度に関して粗い特徴を備える；
請求項１６の方法。
【請求項１９】
前記変換された表現は、変換関数により前記ビデオフレーム内の空間的に分散した情報から計算される；
請求項１６の方法。
【請求項２０】
前記変換関数は：
離散コサイン変換；
修正離散コサイン変換；
離散フーリエ変換；
ウェーブレット変換；または、
高速フーリエ変換；
の少なくとも１つを備える；
請求項１９の方法。
【請求項２０】
前記ビデオメディア・コンテンツ部分は、ビデオコンテンツ部分の前記時間的に関連したグループの第１の部分を備え；
前記時間的に関連したビデオコンテンツ部分のグループの少なくとも第２のビデオメディア・コンテンツ部分について工程ａ）からｃ）を繰り返す工程と；
ｄ）前記時間的に関連した部分のグループ内の前記第１のコンテンツ部分と前記第２のコンテンツ部分とを分離する時間期間にわたり前記第１のコンテンツ部分と前記第２のコンテンツ部分との前記第２表現の平均値を計算する工程とをさらに備える；
請求項１６の方法。
【請求項２１】
前記第２表現の平均値は、前記メディア・コンテンツのシーケンスの速度の任意の変化において前記時間的に関連したコンテンツ部分のグループに信頼性よく対応する；
請求項２０の方法。
【請求項２２】
ｅ）前記第２表現の平均値をランダムベクトルのセットに投影して投影値のセットを得る工程と；
ｆ）前記投影値のセットに閾値を適用する工程と；
ｇ）前記コンテンツ部分の時間的に関連するグループにメディア・フィンガープリントを計算する工程とをさらに備える；
請求項２０の方法。
【請求項２３】
前記メディア・フィンガープリントは、前記コンテンツ部分の時間的に関連するグループの幾何学的方向の任意の変化や前記メディア・コンテンツのシーケンスの速度の任意の変化において前記コンテンツ部分の時間的に関連するグループに信頼性よく対応する；
請求項２２の方法。
【請求項２４】
工程ｂ）は、前記ピクセル値に基づき特異値分解を計算する工程を備え；
前記基底ベクトルは、前記特異値分解に基づき推定される；
請求項１６の方法。
【請求項２５】
前記基底ベクトルの第１は、前記ピクセル値の最大分散の軸に沿った方向であり、前記基底ベクトルの少なくとも第２は前記第１基底ベクトルに直交する；
請求項２４の方法。
【請求項２６】
前記ピクセル値は、前記領域それぞれに関連する平均値の合計を備え；
前記平均値は、前記領域からの前記メディア・コンテンツの少なくとも１つの特質のサンプルに関係する；
請求項１６の方法。
【請求項２７】
システムであって：
少なくとも１つのプロセッサと；
前記少なくとも１つのプロセッサで実行されると、前記システムに請求項１〜２６または３２の１つ以上に記載の方法の少なくとも１つの工程を行うようにさせるコード化された命令を備えるコンピュータ可読記憶媒体とを備える；
システム。
【請求項２８】
請求項１〜２６または３２の１つ以上に記載の方法の少なくとも１つの工程を実施する手段を備える；
システム。
【請求項２９】
請求項１〜２６に記載の１つ以上の方法の工程を実施するように構成されまたはプログラムされた、または、請求項２７〜２８に記載のシステムの１つ以上を具体化し、配置し、若しくはサポートする；
集積回路（ＩＣ）デバイス；
【請求項３０】
前記ＩＣは、プロセッサ、プログラム可能論理回路、マイクロコントローラ、フィールド・プログラマブル・ゲート・アレイ、または、特定用途向けＩＣの少なくとも１つを備える；
請求項２９のＩＣデバイス。
【請求項３１】
１つ以上のプロセッサで実行されると、前記１つ以上のプロセッサに：
請求項１〜２６または３２〜３５の１つ以上に記載の方法の少なくとも１つの工程を行うようにさせ；
請求項２７〜２８の１つ以上に記載のシステムの少なくとも１つを構成しもしくはプログラムさせ；または、
請求項２９〜３０に記載されたＩＣデバイスの少なくとも１つを構成しもしくはプログラムさせる；
コード化された命令を備える；
コンピュータ可読記憶装置。
【請求項３２】
前記ビデオメディア・コンテンツ部分は、少なくとも１つの次のビデオメディア・コンテンツ部分に関して、前記コンテンツ部分の時間的に関連するグループの前記ビデオメディア・コンテンツに時間窓を備え；
前記ビデオメディア・コンテンツのシーケンスについて工程ａ）からｃ）を繰り返す工程と；
時間窓に変換関数を適用する工程であって、時間窓により前記ビデオメディア・コンテンツの早い部分と次の部分とが時間において関係付けられる、工程とを備え；
前記変換関数を適用する工程は、時間窓にわたる前記ビデオ・コンテンツのイメージの特徴の変化を表す；
請求項１の方法。
【請求項３３】
前記時間窓は、前記ビデオメディア・コンテンツの時間的に早い部分を備える；
請求項３２の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的にメディアに関する。より詳細には、本発明の実施の形態は、メディア・コンテンツに信頼性よく対応するメディア・フィンガープリントに関する。
【背景技術】
【０００２】
メディア・コンテンツは、少なくとも１つのメディアで統合され、保管され、変換され、受信され、処理され、そして使用される情報である。たとえば、オーディオ情報コンテンツはオーディオメディアに関連し、ビデオ情報コンテンツはビデオメディアに関連する。ビデオメディアはビデオ情報コンテンツに加え、関連するオーディオ情報コンテンツを有してもよく、よって、少なくとも時々は、オーディオ／ビジュアル（ＡＶ）メディアあるいはいわゆるマルチメディア、混合メディア等の例とみなされる。本書では、用語「メディア・コンテンツ」、「情報コンテンツ」および「コンテンツ」は、同じ意味で用いられる。
【０００３】
メディア・コンテンツは対応する表現に関連する。メディア・コンテンツのいくつかの表現は、そのメディア・コンテンツ内の、またはその一部を備える情報から導き出される（たとえば、計算され、抽出される）。メディア・フィンガープリントは、対応するメディアの情報コンテンツのエッセンスを統合または獲得し、それで一意的に識別される。メディア・フィンガープリントは、ときにはメディア・シグネチャあるいはメディア・シグネチャのストリームとも称され、メディア・コンテンツ表現の例である。ビデオ・フィンガープリントは、ビデオメディアから導き出されるメディア・フィンガープリントである。オーディオ（音響の）フィンガープリントは、オーディオメディア・コンテンツ（ビデオメディア内のオーディオメディア・コンテンツを含んで）から導き出されるメディア・フィンガープリントである。本書では、用語「メディア・フィンガープリント」は、それが関連し、導き出されるメディア・コンテンツの低ビットレートの表現を指す。
【０００４】
このセクションで説明するアプローチは、たどることができるアプローチであるが、既に考えられまたはたどられたアプローチでは必ずしもない。したがって、特に示されない限り、このセクションで説明されるアプローチは、このセクションに含まれるという理由だけで、従来技術であると仮定してはならない。同様に、１つ以上のアプローチに関して識別される問題は、特に示されない限り、このセクションに基づいて先行技術で認識されていたと仮定してはならない。
【０００５】
本発明を、添付の図面の図で、限定の目的ではなく、例示の目的で説明し、図中、類似の参照番号は類似の要素を示す。
【図面の簡単な説明】
【０００６】
【図１】図１は、本発明の実施の形態による、第１の例のプロシージャを示す。
【図２】図２は、本発明の実施の形態による、切り取ったメディア・コンテンツの例を示す。
【図３】図３は、本発明の実施の形態による、第２の例のプロシージャを示す。
【図４】図４は、コンピュータシステム・プラットフォームの例を示し、本発明の実施の形態は、それで実行される。
【図５】図５は、集積回路（ＩＣ）デバイスの例を示し、本発明の実施の形態は、それで実行される。
【図６】図６は、本発明の実施の形態による、ビデオ信号の信頼性のある識別を獲得するのに用いられるビデオ・シグネチャ生成装置の概略的ブロック図である。
【図７】図７は、本発明の実施の形態による、ビデオ信号の信頼性のある識別を獲得するのに用いられるビデオ・シグネチャ生成装置の概略的ブロック図である。
【図８】図８は、イメージ・プリプロセッサで実施されるプロセスの概略的ブロック図である。
【図９】図９は、本発明の実施の形態による、空間領域プロセッサにより獲得される低解像度イメージの概略的ブロック図である。
【図１０】図１０は、本発明の実施の形態による、セグメントに配置されたビデオフレームの概略的ブロック図である。
【図１１】図１１は、本発明の実施の形態による、１セットのビデオ・シグネチャを生成するビデオコンテンツのセグメントを処理するビデオ・シグネチャ生成装置の概略的ブロック図である。
【図１２】図１２は、本発明の実施の形態による、ビデオコンテンツのコピー検出用のシグネチャデータベースを管理するシステムの概略的ブロック図である。
【図１３】図１３は、本発明の種々の態様を実施するのに用いられる装置の概略的ブロック図である。
【発明を実施するための形態】
【０００７】
信頼性よくメディア・コンテンツに対応するメディア・フィンガープリントに関連する実施の形態の例を、本書で説明する。以下の説明では、説明のために、本発明を十分に理解できるように多くの特定な詳細が説明される。しかし、本発明がそれらの詳細なしでも実施できることは明らかであろう。別の例では、周知の構造や装置は、不必要に本発明を隠したり、ぼかしたり、わかりにくくしたりしないように、完全に詳細には説明しない。
【０００８】
メディア・コンテンツに信頼性よく対応するメディア・フィンガープリントに関連する本発明の実施の形態の例を説明する。メディア・フィンガープリントを、ビデオ、グラフィカル、およびオーディオビジュアルおよび他のマルチメディアを含む１つ以上のメディアの例を参照して、本書で説明する。本説明におけるメディアの例は、単純化と簡潔な統一性のために選定され、異なると明確に述べない限り、実施の形態を特定のメディアに限定するものと解釈してはならない。本発明の実施の形態は、ビデオ、オーディオビジュアルおよび他のマルチメディア、グラフィカルおよび他のメディアによく適合する。さらに、本発明の実施の形態は、２次元空間または３次元空間で方向付けられたビデオおよびグラフィカル情報を表示するビデオメディアの機能とよく適合する。
【０００９】
［実施の形態の例の概要］
この概要では、本発明の実施の形態のいくつかの態様の基本を説明する。この概要は、実施の形態の態様の広範囲または包括的なまとめではないことに留意願う。さらに、この概要は、実施の形態の具体的に重要な態様や要素を識別したり、詳細に実施の形態の範囲や、概略的に本発明を説明したりする意図はないことに留意願う。この概要は、要約し単純化した形式で実施の形態の例に関連する概念を単に提供するだけであり、以下に続く実施の形態の例のより詳細な説明に対する単なる概念的な前置きであると理解すべきである。
【００１０】
メディア・コンテンツのシーケンスにおいてコンテンツ部分の時間的に関連するグループのメディア・コンテンツの一部の最初の表現のために、コンテンツ要素の量子化されたエネルギ値のようなピクセル値にアクセスする。量子化されたエネルギ値または他のピクセル値は、最初の表現が分割された領域のマトリックスについて評価される。最初の表現は、低解像度にダウンサンプルされ、メディア・コンテンツ部分から切り取られる。基底ベクトルのセットが、量子化されたエネルギ値または他のピクセル値から、第１次元の空間で推定される。最初の表現は、メディア・コンテンツ部分の次の表現に変換される。次の表現は第２次元の空間にある。次の表現は、推定した基底ベクトルに基づいた、最初の表現の投影を備える。次の表現は、幾何学的方向での任意の変化についてメディア・コンテンツ部分に信頼性よく対応する。最初の表現は、空間的に分散した情報についての変換関数に関する空間の情報を含む。実施の形態は、離散コサイン変換（ＤＣＴ）、修正離散コサイン変換（ＭＤＣＴまたはｍＤＣＴ）、離散フーリエ変換（ＤＦＴ）、高速フーリエ変換（ＦＦＴ）および／またはウェーブレット変換を含むが、これらには限定されない変換関数で機能する。
【００１１】
前記パラグラフで説明したプロシージャは、少なくとも時間的に関連したコンテンツ部分のグループの第２のメディア・コンテンツ部分に対して繰り返される。すると、時間的に関連した部分のグループでの第１のコンテンツ部分と第２のコンテンツ部分を分離する時間間隔にわたり第１のコンテンツ部分と第２のコンテンツ部分の第２表現について平均値が計算される。第２表現についての平均値は、メディア・コンテンツのシーケンスの速度の任意の変化にわたる時間的に関連したコンテンツ部分のグループに信頼性よく対応する。実施の一形態では、ビデオメディア・コンテンツ部分は、コンテンツ部分の時間的に関連するグループの、少なくとも１つの次のビデオメディア・コンテンツ部分に関して、ビデオメディア・コンテンツ（の、たとえば時間的に早い部分）での時間窓を備える。よって、変換関数を時間窓に適用し、時間窓でビデオメディア・コンテンツの早い部分（または他の時間窓）と次の部分とを時間的に関連させる。変換関数を適用することにより、時間窓についてビデオコンテンツのイメージの特徴の変化を表現できる。この変換は、トレーニングデータのセットから導き出される、またはトレーニングデータのセットに関連した統計に関連し、トレーニングデータのセットは、多数のサンプルおよびフレームについて収集される。
【００１２】
本発明の実施の一形態により計算される（導き出される、抽出される）メディア・シグネチャは、それが導き出されるメディア・コンテンツ部分に信頼性よく対応する。よって、メディア・フィンガープリントはロバストなコンテンツ部分の識別子と考えられ、その識別子は、メディア・コンテンツに対する種々の信号処理作業に柔軟に対応する力がある。実施の一形態により計算されたメディア・シグネチャは、実質的に、種々の信号処理作業に付されるメディア・コンテンツのロバストな識別子である。そのような信号処理作業は、メディア著作権侵害行為として、おそらく権利や許可なしでコンテンツへのアクセスを実行する、メディア・コンテンツに対する攻撃である。信号処理は、また、あるいは、種々の正規の実施からも得られる（たとえば、映画の宣伝でスタジオでビデオクリップから映画の予告編を製作する）。信号処理機能は、1つ以上の方法でメディア・コンテンツを変更することがある。
【００１３】
たとえば、メディア・コンテンツは、引き延ばしや回転などの幾何学的ゆがみや乱れ、あるいは、圧縮、輝度調整、および、フレーム速度変換や遅い再生および／または再録音などの空間調整や時間操作に付されることにより、変更される。本書では、用語「メディア・シグネチャ」は、ビデオ信号やオーディオ信号の時間的に離散したセグメント（たとえば、塊＝チャンク＝）のような、コンテンツ部分の表現であるビットストリームを意味する。例示的セグメントのビデオクリップの例は、種々の状態で存在する。第１のビデオクリップの例は、オリジナルの例に関して、ありのままの、実質的に同一の、自然な、または、加工していない状態を有し、よって、本質的に圧縮していないフォーマットで存在する。追加または代替として、同じビデオクリップの第２の例は、Ｈ．２６４／ＡＶＣ−ＭＰＥＧ４またはＭＰＥＧ３コーデックに実質的に準拠するエンコーダからのような、オリジナルの例と比較して、圧縮した状態にある。コンテンツおよび関連する基本的信号を表現する実際のビットストリームは、非圧縮のおよび圧縮したフォーマットにより異なり、対応するビデオコンテンツは、多くの実用的目的のために本質的に同一として、自然な、実質的に普通の心理視覚的技能の人間により感知される。多くの最新式オーディオ・コーデックもまた、知覚的に機能する。
【００１４】
実施の一形態は、かなりの類似性を共有する同じメディア・コンテンツの非圧縮および圧縮フォーマットまたはバージョンのそれぞれからのシグネチャを計算する（導き出す、抽出する）ように機能する。そのように計算されたメディア・シグネチャは、それが対応するメディア・コンテンツの核心を信頼性よく捉え、コンテンツのデータの種々の信号処理作業（たとえば、圧縮）に本質的にロバストであり、コンテンツのデータは関連するコンテンツを維持する。さらに、実施の一形態により計算されたシグネチャは、幾何学的攻撃に対して強くロバストである。よって、実施の一形態を用いて、たとえば著作権のあるビデオクリップの修正されたバージョンを識別できる。たとえば、仮説のオリジナルの著作権のあるコンテンツを、圧縮、輝度調整、フレーム速度変換、幾何学的ゆがみなどのような種々の信号処理作業で修正することができる。しかし、計算されたシグネチャとフィンガープリントはそのような処理作業に対してロバストであり、よって、それらが存在すると、あるいは少なくとも部分的にそれらに応答すると、それらが導き出されたコンテンツと関連をなくすことに対してロバストである。よって、実施の一形態は、信号処理による修正を伴っても、オリジナルの著作権のあるコンテンツの正確で精密な識別を、信頼性よく可能にできる。
【００１５】
例示の実施の一形態は、インプットされたビデオ信号についてビデオ信号を時間的に小さな塊に分割するよう機能し、その塊は、オーバーラップしてもしなくてもよい。各ビデオデータの塊に対し、特徴が基本的コンテンツから導き出され、そして基本的コンテンツを表現する。シグネチャ、たとえばコンテンツの相対的に低次元のビットストリーム表現は、そこから形成される。本書では、用語「シグネチャ」は、ビデオの塊のような、メディア・コンテンツ部分に関して、ビデオデータの塊のビットストリーム表現を意味する。本書では、用語「ビデオ・フィンガープリント」は、ビデオファイルまたは他のコンテンツ部分の全シグネチャのセットを意味し、よって、本質的に全体としてのインプットされたビデオ信号に関して適用される。各ビデオの塊のシグネチャは、それぞれが導き出されたコンテンツ部分のインスタンスが種々の信号処理作業に付されるとしても、実質的に類似のままである。よって、実施の一形態は、非圧縮でも圧縮されても、与えられたメディア・コンテンツの種々のインスタンスから導き出された（サンプリングされた、抽出された、計算された）シグネチャの特徴の間に存在する類似性に、少なくとも部分的に基づいて機能する。
【００１６】
［名称、用語、および、プラットフォームの例］
本書では、用語「メディア」（単数および複数）は、データや他の情報の記憶または伝達のための入れ物を意味する。本書では、用語「マルチメディア」は、複数の形式の情報を含むメディアを意味する。マルチメディア情報ファイルは、たとえば、オーディオ、ビデオ、イメージ、グラフィカル、テキスト、アニメーションおよび／または他の情報、およびそれらの種々の組合せを含む。本書では、用語「関連情報」は、情報メディア・コンテンツに何らかで関係する情報を意味する。関連情報は、たとえば、予備的コンテンツを含む。
【００１７】
本書では、用語「導き出す」、「導き出された」、「導き出している」等は、メディア・コンテンツの信号成分をサンプリングし、および／または、サンプルから、対応するユニークなシグネチャまたはフィンガープリントを計算することを意味する。シグネチャまたはフィンガープリトを「抽出する」のような用語もまた、導き出すことを意味する。
【００１８】
本書では、用語「メディア・フィンガープリント」は、その特徴的成分から導き出されたメディア・コンテンツファイルの表現を意味する。メディア・フィンガープリントは、対応するメディア・コンテンツから導き出される（たとえば、計算され、抽出され、生成される等）。本書では、用語「ビデオ・フィンガープリント」は、ある程度詳細にビデオメディアに関連する（ビデオ・フィンガープリントはまた他のメディアにも関連するが）メディア・フィンガープリントを意味する。本書の実施の一形態で用いられるメディア・フィンガープリントは、ビデオ、イメージ、グラフィカル、テキスト、アニメーション・オーディオビジュアルおよび／または他のマルチメディア、他のメディア情報コンテンツ、および／またはそれらの組み合わせに対応し、ある程度詳細に関連するメディアに加え、他のメディアを参照してもよい。
【００１９】
ビデオ・フィンガープリントは、ユニークなデジタルビデオファイルを備え、デジタルビデオファイルの成分はビデオコンテンツの特徴的成分から導き出される（たとえば、計算され、生成され、書かれ、抽出され、そして／または、圧縮される）。導き出されたビデオコンテンツの特徴的成分は、圧縮されて対応するビデオ・フィンガープリントを形成するが、輝度値またはルマ値（luma values）、クロミナンス値またはクロマ値（chroma values）、動作の推定、予想および補償値、等を含むが、これらには限定されない。
【００２０】
よって、本書で説明されるメディア・フィンガープリントは、導き出されたメディア・コンテンツを表現するが、メディア・コンテンツに関連するメタデータあるいは他のタグを備えず、そして（たとえば本書の説明のためにまた説明の文書においては）メタデータあるいは他のタグと混同されるものではない。メディア・フィンガープリントは、それが導き出されたメディア・コンテンツより、低ビットレートで伝達できる。重要なこととして、本書では、「導き出す」、「生成する」、「書く」、「抽出する」および／または「備える」のような用語は、「フィンガープリントを計算する」のようなフレーズと実質的に同様に、メディア・コンテンツ部分からメディア・フィンガープリンを獲得することに関連し、また、このような状況で、同義語としてまたは互換的に用いられる。
【００２１】
よって、これらのおよび類似の用語は、メディア・フィンガープリントの、または、関連するソースメディア・コンテンツとメディア・フィンガープリントの関係に関連する。実施の一形態では、メディア・コンテンツ部分はメディア・フィンガープリントのソースであり、メディア・フィンガープリントは本質的にメディア・コンテンツのユニークな成分を備える。たとえば、ビデオ・フィンガープリントは、ビデオコンテンツのフレーム中のクロミナンスおよび／または輝度に関連する値から導き出される（たとえば、少なくとも部分的に備える）。ビデオ・フィンガープリントはまた（あるいは代替として）、ビデオフレーム中の動作の推定、予想または補償、たとえば動作ベクトルおよび類似の動作関連記述子に関する値を備える。よって、メディア・フィンガープリントは、それが導き出されたメディア・コンテンツ部分をユニークに表現し、識別し、言及しあるいは意味する機能を有する。付随して、本書ではこれらのおよび類似の用語は、メディア・フィンガープリントはメタデータ、タグおよび他の記述子とは区別されることが強調されるものと理解され、メタデータ、タグおよび他の記述子は、ラベル付けしたり説明するためにコンテンツに追加され、その後抽出される。派生的メディア・コンテンツに関する状況では、用語「派生的」または「導き出す」はさらに、メディア・コンテンツのオリジナルの事例以外の事例を表現しまたは備えるメディア・コンテンツに関係してもよい。
【００２２】
［メディア・フィンガープリントの例示的誘導 ］
メディア・シーケンス内のコンテンツは、複数のコンテンツ要素を備える。たとえば、ビデオメディアは、複数のビデオフレームを備える。たとえば一つのビデオメディアを用いる場合、図１は、本発明の一実施形態においてメディアデータのストリームからコンテンツの特徴を抽出するための例示的プロシージャ１００を示す。ビデオシーケンスのフレームは、時間とともに流れ、間隔Ｔｉｎｔに分割される。１つ以上の時間間隔Ｔｉｎｔは、ビデオシーケンスの部分の期間継続する時間の塊Ｔｃｈｕｎｋを備える。各間隔Ｔｉｎｔは、間隔Ｔｉｎｔの期間継続するビデオコンテンツの部分を備えるビデオフレームＦ１、Ｆ２、・・・、ＦＮのグループに関連する。
【００２３】
一実施の形態では各時間間隔Ｔｉｎｔについてメディア・フィンガープリントを導き出す（たとえば、計算する、抽出する）。間隔Ｔｉｎｔは、最小のフレーム速度変換係数から導き出され、そのフレーム速度変換係数においてメディア・シグネチャは、メディア・シグネチャが抽出されたところのオリジナルのメディア・コンテンツのフレームに信頼性よく対応することが期待される。たとえば、オリジナルのビデオシーケンスの速度が３０フレーム／秒（ｆｐｓ）で、そのビデオ・フィンガープリントが１２ｆｐｓまでのフレーム速度変換についてオリジナルのフレームコンテンツに信頼性よく対応することが期待される場合、ビデオ・フィンガープリントは１２分の１秒でそれぞれ抽出され、よって、Ｔｉｎｔ＝１／１２秒である。実施の一形態は、実質的に所与のメディア要素の速度（例えば、ビデオフレーム速度）やその範囲を限定をすることなく機能することが理解される。
【００２４】
ステップ１０１で、現在の間隔ＴｉｎｔについてのフレームＦ１、Ｆ２、・・・、ＦＮのグループが選択される。グループＦ１、Ｆ２、・・・、ＦＮは、間隔Ｔｉｎｔについての時間間隔で動作するビデオコンテンツ部分に対応する。よって、フレームのグループＦ１、Ｆ２、・・・、ＦＮは、Ｔｉｎｔの最初の瞬間に先行する１つ以上のフレームを含み得る。ＴｉｎｔについてのグループＦ１、Ｆ２、・・・、ＦＮはまた、Ｔｉｎｔの最後の瞬間に後続する１つ以上のフレームを含み得る。
【００２５】
フレームのグループＦ１、Ｆ２、・・・、ＦＮが所定のフレーム速度で動作する時間間隔の期間は、本書では、時間塊Ｔｃｈｕｎｋと称される。たとえば、現在の間隔Ｔｉｎｔは、時間ステップｊとして参照される。時間ステップｊは、瞬間ｊ−１で始まり、瞬間ｊまで継続する。時間ステップｊについての現在のフレームのグループＦ１、Ｆ２、・・・、ＦＮは、ｊ−１まで継続する間隔の間に始まり、継続時間Ｔｃｈｕｎｋで瞬間ｊ＋１まで継続する間隔の間に終了する。たとえば、ステップ１０１は、時間塊Ｔｃｈｕｎｋが時間ステップｊについて２秒間動作するフレームのグループＦ１、Ｆ２、・・・、ＦＮに対応するように実行され、フレームのグループＦ１、Ｆ２、・・・、ＦＮは、３０ｆｐｓのフレーム速度で動作するインプットされたビデオの部分またはシーケンスを備える。フレームＦ１、Ｆ２、・・・、ＦＮの１つ以上は、複数の時間間隔Ｔｉｎｔにオーバーラップし得る。
【００２６】
ステップ１０２では、インプットされたビデオストリームは、時間的にダウンサンプルされる。前記の例を続けると、３０ｆｐｓのフレーム速度でインプットされたビデオは、フレームを落とすことで１２ｆｐｓのような低フレーム速度にダウンサンプルされる。フレーム速度が１５ｆｐｓでインプットされるビデオは、同様にフレームを落として１２ｆｐｓにダウンサンプルすることができる。落とされるフレーム数は、異なったフレーム速度の違ったビデオストリームをダウンサンプルする点で異なる。フレームは、Ｔｃｈｕｎｋに対応するグループでのフレーム数がＮのままであるように、どんなフレーム速度でインプットされたビデオでも時間的にダウンサンプルして落としてよい。Ｎ＝２４とすると、インプットされたビデオは、選定されたフレームのグループＦ１、Ｆ２、・・・、ＦＮが２４フレームを維持するように、時間的にダウンサンプルされる。
【００２７】
Ｔｃｈｕｎｋの値は、プロシージャ３００により計算されたメディア・フィンガープリントが、オリジナルのメディア・コンテンツからフレーム速度変換のようなビデオ処理作業を経て導き出されるときに、オリジナルのメディア・コンテンツに対応することに対する信頼性のレベルに関係する。たとえば、時間間隔Ｔｉｎｔは２秒の値で実行され、Ｔｃｈｕｎｋは３秒の値で実行される。この例では、ＴｃｈｕｎｋはＴｉｎｔよりかなり大きい。２つの連続したシグネチャを導き出すのに用いられる時間的に近似したフレームのグループ間で、重複の度合いが高い。時間的に近似したフレームのグループ間で高い重複の度合いは、連続したシグネチャを導き出し、それらは、フレーム速度変換についてオリジナルのフレームの対応において顕著な信頼性を示す。
【００２８】
ステップ１０３で、フレームＦ１、Ｆ２、・・・、ＦＮのそれぞれは、空間的にダウンサンプルされる。ステップ１０４では、空間的にダウンサンプルされたフレームのそれぞれは、切り取られ、一部が対応する表現のイメージになる。各フレームの最初の表現のイメージは、本書では、フレームの第１表現と称される。たとえば、フレームの切り取りは、図１と図２を参照して、実行される。各フレームの最初の表現のイメージは、本書では、フレームの第１表現と称される。
【００２９】
図２は、本発明の実施の一形態によるメディア・コンテンツの切り取り２００の例を示す。各フレームイメージＦｉから、ビデオ・シグネチャ生成用にステップ１０４で領域Ａが切り取られる。領域Ａは、形態的に実質的に円形でよい。フレームＦｉの幾何学的方向が任意に変化したとき、切り取られた領域Ａから得られたビデオ・シグネチャは、Ｆｉに整合したままである。たとえば、フレームＦｉは、軸方向に、たとえば領域Ａ内のどこかのピクセル周りに回転してもよい。Ｆｉでの幾何学的方向の変化にもかかわらず、領域Ａ内に含まれるピクセルは切り取られたサブイメージ内に留まる。よって、切り取られた領域Ａ内のピクセルは、インプットされたイメージＦｉの全ての回転を切り抜けて残る。
【００３０】
領域Ｃのピクセルは、幾何学的方向が変わるにつれ、回転してＦｉに関連する表示エリアの外側になる。イメージＢからのピクセルはＦｉの幾何学的方向の変化を切り抜けて残るが、実行により領域Ｂを、イメージ領域のテキスト重複またはコーナー周りのグラフィックスの取り入れ等、他の使用にとっておく。よって、実行により、領域ＢとＣからのピクセル値をゼロに設定し得る。
【００３１】
図１を再度参照して、ステップ１０５において、それぞれの表現するイメージを複数の領域のマトリックスに分割する。その領域は、表現するイメージの方向に関して水平アスペクトと垂直アスペクトで分割して得られるブロックと一致し得る。その領域はまた、ブロックとは別にまたはこれに加えて、回転面またはゆがむシートのような形状にも一致するようにすることもでき、それらはブロックとはいくらか異なって分割される。
【００３２】
ステップ１０６において、各領域内のエネルギにアクセスして合計し、合計は量子化合計Ｑｉに量子化される。各領域のエネルギは、たとえば、ＤＣＴやその変形、たとえば、ｍＤＣＴ、ＤＦＴ、ＦＦＴおよび/またはウェーブレット変換、などのような、高速フーリエ型の変換を用いて合計される。領域のエネルギを合計するのに他の変換法を用いることもできる。量子化された合計は、フレームの第１表現のいくらか粗い表現を備える。図２を再度参照すると、ステップ１０５または１０６の１つ以上は領域Ａからのピクセルについて効果的に実行される。
【００３３】
Ｆｉから切り取られたサブイメージは、Ｆｃｉで表わされる。ＦｃｉはサイズではＦｉに対応するが、Ｆｉの領域ＢおよびＣからサンプルされたＦｃｉ値は、ゼロになされる。Ｆｃｉの粗い表現Ｑｉは、サイズＷｘ＊Ｗｙのイメージ・ブロックでのピクセル強度を平均することにより求められる。図２を参照すると、表現Ｑｉは、垂直スケール１２０と水平スケール１６０で実行され、そこではイメージＦｉはＭ１＊Ｗｘ＝１２０、Ｍ２＊Ｗｙ＝１６０となるように表示され、ここでＱｉは（Ｍ１＊Ｍ２）のサイズを有する。よって、たとえば、Ｑｉは、下記の式１により計算される。
【数１】
2011511489.tif 000003
・・・式１
【００３４】
式１では、「ｍ」と「ｎ」はそれぞれ、イメージＦｃｉの水平および垂直次元のインデックスを表わし、「ｋ」と「ｌ」は、イメージ表現Ｑｉのインデックスを表わす。粗くしたイメージ表現もまた、実行される。たとえば、Ｑｉの粗い４４＊６０表現は、Ｍ１を値４４に、Ｍ２を値６０にセットすることによりなされる。
基本的に式２により平均することはまた、ダウンサンプルの形式を備え、よって、ステップ３０４を参照して説明したようにイメージを切り取る前に実施される。記載された例示のパラメータは説明のために選定されたもので、いかなる意味でも限定するものと解釈してはならないことに留意されたい。実施の形態は、パラメータの広く変化する範囲で機能するように適合している。この粗い表現Ｑｉは、領域内に存在する変化について領域内の平均強度を保持する。オリジナルのイメージは本質的に、切り取り後（Ｍ１＊Ｍ２）のサイズのイメージにダウンサイズされる。よって、ステップ３０３〜３０６は、より少ない（例えば１）処理ステップで実行できる。さらに、フレームＦｉの基底ベクトルもまた同様に、より少ないステップで実行できる。たとえば、フレームの基底ベクトルは、オリジナルのフレームから推定され、または、たとえばその表現から、概念的に推定される。
【００３５】
よって、第１のメディア要素の表現Ｑｉは、本質的にダウンサンプルされ切り取られたフレームイメージからの量子化されたエネルギ値であり、グループＦ１、Ｆ２、・・・、ＦＮのフレームのそれぞれに対しステップ１０６（またはより少ない処理ステップで）からのアウトプットを備える。ステップ１０７で、第１のメディア要素の表現Ｑｉはバッファリングされる。
【００３６】
ブロック１０８では、基底ベクトルのセットＢ１、Ｂ２、・・・、ＢＮが、シーケンスＱ１、Ｑ２、・・・、ＱＮに対して推定される。例示の実施の一形態では、基底ベクトルは、第１のメディア要素表現のシーケンスＱ１、Ｑ２、・・・、ＱＮについて計算される特異値分解（ＳＶＤ）に基いて推定される。別の実施の一形態では、基底ベクトルはシーケンスＱ１、Ｑ２、・・・、ＱＮに対してなされる他の計算法に基いて推定されてもよい。実施の一形態では、基底ベクトルはグループＦ１、Ｆ２、・・・、ＦＮのフレームの表現から推定することもできる。たとえば、粗い表現Ｆｉを空間領域（Ｑｉ）で用いてもよい。代替としてまたは追加で、基底ベクトルは、ＤＣＴ、ｍＤＣＴ、ＤＦＴ、ＦＦＴまたはウェーブレット変換表現などの変換領域表現から推定してもよい。
【００３７】
ステップ１０９において、Ｑｉの座標は新しい空間にて得られ、新しい空間はＱｉを各基底ベクトルに投影することによりＢ１、Ｂ２、・・・、ＢＮにより長さを測られる。投影は、行列Ｑｉｓ＝（Ｑｉｓ，１，Ｑ２ｓ，２，・・・，Ｑｉｓ，Ｎ）として表現される。Ｑｉは、Ｍ１＊Ｍ２の次元のベクトルを備えるが、Ｂ１、Ｂ２、・・・、ＢＮにより長さを測られる新しい空間ではＮ次元のベクトルであるＱｉｓにより表現されることに気付くであろう。よって、実施の一形態では第１のメディア要素の表現を新しい次元空間での第２のメディア要素の表現に、推定した基底ベクトルに基づいて第１のメディア要素の表現を投影することにより、変換する。新しい次元空間は、そのオリジナルの次元空間に関してユニークである。
【００３８】
さらに、第２のメディア要素の表現は、オリジナルのメディア・コンテンツ部分の幾何学的方向を任意に変更してもオリジナルのメディアに信頼性よく対応する。基底ベクトルＢ１、Ｂ２、・・・、ＢＮは、Ｑ１、Ｑ２、・・・、ＱＮから推定される。よって、オリジナルのビデオコンテンツが空間的回転、アスペクト比の変化、垂直または水平方向（または、２空間次元より大きな空間次元で表示されるメディアでは、垂直または水平方向の少なくとも１方向に垂直な第３の方向）での並進的移動、幾何学的方向のアフィン・ワープや他の変化をする場合、各メディア要素の表現Ｑｉは、そこから得られる基底ベクトルがするように、対応する変化をする。
【００３９】
Ｑ１、Ｑ２、・・・、ＱＮから基底ベクトルＢ１、Ｂ２、・・・、ＢＮを求めることは、行列Ｙを作ることで実行される。行列Ｙの各列（ｊ）は、フレームＱｊを表す。行列Ｙの行の数は（Ｍ１＊Ｍ２）であり、行ごとにスキャンされたＱｊの要素数である。行列Ｙの次元は、（Ｍ１＊Ｍ２）×Ｎである。行列Ｙの階数は、最大でＮに等しい値である。基底ベクトルＢ１、Ｂ２、・・・、ＢＮは、行列Ｙの特異値分解（ＳＶＤ）を用いて計算できる。行列ＹのＳＶＤの計算は、たとえば下記の式２により、実行することができる。
【数２】
2011511489.tif 000004
・・・式２
【００４０】
式２では、Ｕは次元（Ｍ１＊Ｍ２）×Ｎであり、Ｓは次元Ｎ×Ｎであり、Ｖは次元Ｎ×Ｎである。Ｕの列は基底ベクトルＢ１、Ｂ２、・・・、ＢＮを備える。基底ベクトルは、基本的に行列積ＹＹＴを対角化し、Ｙの列の長さの変換を備える。Ｓは、大きさを下げるように単一の値の対角行列を備える。Ｖの列は、ＹＴＹを対角化し、Ｙの列に及ぶ変換の基底ベクトルを備える。
【００４１】
基底ベクトルＢ１、Ｂ２、・・・、ＢＮを求める際、たとえば、ＳＶＤの計算で、Ｑｉの座標は、たとえば、下記の式３により、新しい変換された空間ＱｉＳで計算される。
【数３】
2011511489.tif 000005
・・・式３
【００４２】
次元（Ｍ１＊Ｍ２）×１のベクトルＱｉＶは、次元Ｍ１＊Ｍ２の行列Ｑｉから計算される。ベクトルＱｉＶを計算することは、行列の全体を行ごとに調べることにより行うことができる。
【００４３】
積Ｑｉｓは、オリジナルのメディア・コンテンツの幾何学的方向の変化において対応するメディア要素の表現Ｑｉを信頼性よく表現する。よって、積Ｑｉｓは、第１のメディア要素の表現Ｑｉの第２表現を備える。第２表現Ｑｉｓは、本質的に、幾何学的メディア・コンテンツの変化に対し不変である。
【００４４】
ステップ１１０で、新しい座標Ｑｉｓについて時間平均が計算される。時間的に平均された座標Ｑｉｓは、ビデオシーケンスでの速度変化について、オリジナルのメディア・コンテンツに信頼性よく対応する。よって、Ｑｉｓは、幾何学的変化に加え、フレーム速度変換にもロバストである。シーケンスＱｉｓ、Ｑ２ｓ、・・・、Ｑｉｓの時間平均Ｇの計算は、たとえば下記の式４により、行うことができる。
【数４】
2011511489.tif 000006
・・・式４
実施の一形態では、ビデオメディア・コンテンツ部分は、コンテンツ部分の時間的に関連したグループの、少なくとも１つの次のビデオメディア・コンテンツ部分に関係した、ビデオメディア・コンテンツ（の、たとえば時間的に早い部分）における時間窓を備える。よって、ビデオメディア・コンテンツの早い部分（または別の時間窓）と次の部分とが時間について関係付けられる時間窓に変換関数を適用する。変換関数を適用することで、時間窓におけるビデオコンテンツのイメージの特徴の変化の記述が可能となる。この変換の基礎は、複数のサンプルとフレームで集めたトレーニングデータのセットから導き出せ、または、トレーニングデータのセットと関連する統計に関係する。
【００４５】
ステップ１１１で、現在の時間ステップについてのＮ個の投影の時間平均を有する、Ｇの第１のＬ値が選定され、Ｒ×Ｌのサイズを有するバッファＤに保存される。バッファＤは、Ｒ個の最近の時間ステップについてのＧの最高Ｌ値を保持する。よって、バッファＤは、時間についてＧの最高Ｌ値の変動を捕捉できる。Ｇについての値のサブセットを、Ｒ個の最近の時間ステップについての行列Ｄとしてバッファに保存する。
【００４６】
ステップ１１２において、シグネチャビットが行列Ｄについて生成される。シグネチャビットの生成は、行列Ｄと同じ次元を有するＫ個のベクトルＰ１、Ｐ２、・・・、ＰＫの生成で行われる。行列Ｄは、下記の式５により、Ｋ個のベクトルのセットに投影される。
【数５】
2011511489.tif 000007
・・・式５
【００４７】
シグネチャビットは、Ｋ１個の投影を閾値とすることにより導き出される。図３は、本発明の実施の一形態が機能する擬似ベクトルへの投影に基づいてハッシュビットを生成するプロシージャ３００を示す。Ｋ１個のベクトルＰ１、Ｐ２、・・・、ＰＫのセットに基づく投影は、行列Ｄの別の態様を捕捉する。たとえば、Ｋ１個のベクトルのいずれか２個が類似しているならば、Ｋ１個のビットからの２ビットは同一である。よって、Ｋ１個の直交基底ベクトルのセットが用いられる。あるいは、Ｋ１個の擬似ランダムベクトルは互いにほぼ直交すると考えられるので、Ｋ１個の擬似ランダムベクトルのセットを用いてもよい。
【００４８】
Ｋ１個のハッシュビットは、Ｋ１個の擬似ランダムベクトルへのアダマール積の投影（Hadamard product projections）Ｈ１、Ｈ２、・・・、ＨＫ１に基づいてＤから生成できる。１からＫ１に至る数ｉについて、ｉ番目のシグネチャビットは、ＨｉがＨ１、Ｈ２、・・・、ＨＫ１のメジアンより大きいと「１」の値にセットされる。しかし、ＨｉがＨ１、Ｈ２、・・・、ＨＫ１のメジアンより大きくないと、対応するシグネチャビットは「０」の値にセットされる。本質的に同様の方法で、Ｋ２個のハッシュビットがＶｒ個のビットから生成される。
【００４９】
たとえば、対応するオリジナルのビデオコンテンツのフィンガープリントと比較したり、参照したりするのに、修正ビデオコンテンツからビデオ・フィンガープリントを再生する際に、パラメータＴｃｈｕｎｋ、Ｍ１、Ｍ２、Ｋ、Ｌ、Ｒの値や擬似ランダム行列の値は、本質的に変化しない。
【００５０】
たとえば行列ＹのＳＶＤを用いて、基底ベクトルＢ１、Ｂ２、・・・、ＢＮを推定するステップ１０８は、計算的に集約されている。行列Ｙは、（Ｍ１＊Ｍ２）×Ｎのサイズを有し、行列Ｙの各列はＱｉの要素を有し、ここでｉは１からＮに至る値を有する。よって、各々の次の時間ステップに対し、行列Yの第１列は取り除かれ、新しい列が加えられる。前の時間ステップから得られた行列U、ＳおよびＶの増分更新が行われる。前の時間ステップから得られた行列U、ＳおよびＶの増分更新は、各々の現在の時間ステップに対し行列ＹについてＳＶＤを計算することを不要とする。
【００５１】
行列ＹについてのＳＶＤでの増分更新は２つの計算作業で行われる。計算作業は、Ｙ＋ＡＢＴの式による行列Ｙの第１列の削除から始められ、ここで、「Ａ」は（Ｍ１＊Ｍ２）×１の次元のベクトルを備え、行列Ｙから削除される第１列の負数に等しく、「Ｂ」はＮ×１の次元のベクトルを備え、［１，０，０，・・・０］に等しい。
【００５２】
行列Ｙは、上記のようにＵＳＶに等しかった。よって、行列ＹのＳＶＤを更新して増分更新を実行することは、次のように行われる。ベクトルＰは、直交基底ベクトルＡ−Ｕ（ＵＴＡ）を備える。ベクトルＡ−Ｕ（ＵＴＡ）はＵに直交するＡの成分である。Ｐの計算は、たとえば下記の式６によるグラム・シュミット直交化法を用いて、ＱＲ分解により行われる。式６では、ＲＡは、ＰＴ（Ａ−Ｕ（ＵＴＡ））と等価である。
【００５３】
シグネチャビットを導き出すことは、Ｋ個の投影を閾値とすることにより行われる。Ｋ個のベクトルＰ１、Ｐ２、・・・ＰＫのセットに基づく投影は、行列Ｄの別の態様を捕捉する。
【００５４】
Ｋ個の直交基底ベクトルのセットまたはＫ個の擬似ランダムベクトルのセットが実行される。基底ベクトルに関して直交した方向の、または、Ｋ個の擬似ランダムベクトルのセットである、Ｋ個のベクトルの実行は、たとえばＫ個のベクトルのうち類似した２つについて、Ｋ個のビットから２つのビットを区別できないことを回避する。Ｋ個の擬似ランダムベクトルのセットが実行される場合、Ｋ個の擬似ランダムベクトルは互いにほぼ直交していると仮定される。
【００５５】
行列Ｙは上記のようにＵＳＶに等しかった。よって、行列ＹのＳＶＤを更新して増分更新を実行することは、次のように行われる。ベクトルＰは、直交基底ベクトルＡ−Ｕ（ＵＴＡ）を備える。ベクトルＡ−Ｕ（ＵＴＡ）はＵに直交するＡの成分である。Ｐの計算は、たとえば、下記の式６のような、グラム・シュミット直交化法を用いて、ＱＲ分解により行われる。式６では、ＲＡは、ＰＴ（Ａ−Ｕ（ＵＴＡ））と等価である。
【数６】
2011511489.tif 000008
・・・式６
【００５６】
同様に、ベクトルＱは、直交基底ベクトルＢ−Ｖ（ＶＴＢ）を備える。ベクトルＢ−Ｖ（ＶＴＢ）は、Ｖに直交する基底ベクトルＢの成分を備える。Ｑの計算も、ＱＲ分解で行われ、ここで、ＲＢは、ＱＴ（Ｂ−Ｖ（ＶＴＢ））と等価である。
【００５７】
行列Ｙの第１列の削除は、たとえば下記の式７により、右辺（ＲＨＳ）のＳＶＤを計算して（Ｙ＋ＡＢＴ）のＳＶＤを計算することにより行われる。
【数７】
2011511489.tif 000009
・・・式７
【００５８】
式７は、右辺（ＲＨＳ）のＳＶＤを計算して（Ｙ＋ＡＢＴ）のＳＶＤを計算することで十分なことを示唆する。式７のＲＨＳ項のＳＶＤがＵ０Ｓ０Ｖ０で与えられる場合、式Ｙ＋ＡＢＴのＳＶＤを更新することは、下記の式８により行われる。
【数８】
2011511489.tif 000010
・・・式８
【００５９】
項Ｕ＊Ｓ＊Ｖ＊は、式Ｙ＋ＡＢＴの分解を備える。よって、ＳＶＤの更新は、式７のＲＨＳ項のような、（Ｎ＋１）×（Ｎ＋１）の次元を有する行列についてＳＶＤを計算することにより行われる。式７のＲＨＳのＳＶＤの計算は、（Ｍ１＊Ｍ２）×（Ｎ＋１）の次元を有する式（Ｙ＋ＡＢＴ）のＳＶＤのよりコストの掛かる計算を回避する。例示の実施では、Ｎは３９の値にセットされ、１，３６０となるところの（３４＊４０）の（Ｍ１＊Ｍ２）の値と対照的である。しかし、Ｎについては他の値や範囲が実行できることは明らかである。
【００６０】
上述のように、列を取り除くと、行列ＹのＳＶＤの増分更新は、行列に新たな列を追加することで行われる。行列Ｙへの新たな列の追加は、式Ｙ＋ＡＢＴを用いて行われる。項Ａは、（Ｍ１＊Ｍ２）×１の次元を有するベクトルを備え、行列Ｙに追加される新しい列に基本的に等価である。項Ｂは、（Ｎ＋１）×１の次元を有するベクトルを備え、［０，０，０，・・・１］に基本的に等価である。よって、式Ｙ＋ＡＢＴについてＳＶＤを増分更新することは、上記の式６、７、８の１つ以上により行うこともできる。
【００６１】
本発明の例示の実施の一形態を、メディア・コンテンツに信頼性よく対応するメディア・フィンガープリントに関連して上記に説明した。例示の実施の一形態の説明では、たとえば図１と図２を参照して、ビデオメディアを例として用いた。上記のように、ビデオメディアは上記の説明で単純化および単一性のために例示のメディアとして選定されただけであり、別のことが明記された場合を除き、実施の一形態を特定のメディアに制限すると解してはならない。本発明の実施の一形態は、ビデオメディアと同様に、オーディオメディアで機能するのにも適している。
【００６２】
たとえば、実施の一形態は、サウンド、音楽および音声記録のようなオーディオメディアから音響シグネチャや合成音響フィンガープリントを生成するのに適している。オーディオメディアは、ビデオメディアおよび／または他のマルチメディアフォーマットでエンコードされる、たとえば記録されたサウンドトラックのような、ビデオメディアに関連してもよい。
【００６３】
メディア・コンテンツ要素の説明で上記では例としてビデオフレームを用いたが、実施の一形態は、同様に、メディア・コンテンツ・クリップとしてオーディオクリップのオーディオスペクトログラムで機能するのに適している。よって、上記説明のように用いて、オーディオクリップは、時間について流れるオーディオメディア・コンテンツの一部を備える。プロシージャ３００をオーディオクリップのスペクトログラムに適用して、対応する音響フィンガープリントを抽出する。全時間ステップＴｃｈｕｎｋについて、オーディオスペクトログラムに新しいスペクトル表現が加えられ、古いスペクトル表現が取り除かれる。
【００６４】
本実施の一形態によりオーディオスペクトログラムから抽出された音響フィンガープリントは、オーディオピッチシフトや遅いオーディオプレイなどの幾何学的方向における任意の変化についてオーディオスペクトログラムに信頼性よく対応する。たとえば、ピッチシフトの効果は、基本的に周波数次元でのオーディオスペクトログラムの非線形な引き伸ばしであると考えられる。プロシージャ３００は、１セットの基底関数を用いて、オーディオデータから推定されるオーディオデータを説明する。このように、プロシージャは、スペクトログラムのゆがみに対して不変のオーディオスペクトログラムから特徴を抽出することを可能にする。
【００６５】
［例示の実施のプラットフォーム］
プロシージャ１００や３００（それぞれ図１、３）の一部のような、本発明の実施の一形態は、コンピュータシステム、電子回路や電子部品で構成されたシステム、マイクロコントローラのような集積回路（ＩＣ）デバイス、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、または特定用途向けＩＣ（ＡＳＩＣ）、および／またはそのようなシステム、デバイスまたは部品を１つ以上含む装置で行われる。
【００６６】
図４は、本発明の実施の一形態が実行される例示のコンピュータシステム・プラットフォーム４００を示す。コンピュータシステム４００は、情報通信のためのバス４０２または他の通信メカニズム、および、情報処理のためのバス４０２に接続されたプロセッサ４０４を含む。コンピュータシステム４００はまた、情報やプロセッサ４００で実行される命令を記憶するための、ランダムアクセスメモリ（ＲＡＭ）や他のダイナミック記憶装置のようなメインメモリ４０６を含む。メインメモリ４０６は、プロセッサ４０４で実行される命令の実行中に一時的変数や他の中間的情報を記憶するのにも用いられる。コンピュータシステム４００は、静的情報やプロセッサ４００用命令を記憶するための、バス４０２に接続された読み出し専用メモリ（ＲＯＭ）４０８または他の静的記憶装置をさらに含む。磁気ディスクや光ディスクなどの記憶装置４１０が備えられ、情報や命令を記憶するためバス４０２に接続される。プロセッサ４０４は、１つ以上のデジタル信号処理機能を実行する。
【００６７】
コンピュータシステム４００は、コンピュータユーザに情報を表示するため、バス４０２経由で、液晶ディスプレイ（ＬＣＤ）、ブラウン管（ＣＲＴ）等のようなディスプレイ４１２に接続される。英数字や他のキーを含む、入力装置４１４が、情報やコマンド選択をプロセッサ４０４に通信するためにバス４０２に接続される。ユーザ入力装置の他のタイプは、指示情報やコマンド選択をプロセッサ４０４に通信し、ディスプレイ４１２上のカーソルの動きをコントロールするための、マウス、トラックボール、カーソル指示キーなどのカーソルコントローラ４１６である。この入力装置は、典型的には第１軸（たとえば、ｘ）と第２軸（たとえばｙ）の２軸に２自由度を有し、入力装置が平面上の位置を特定することを可能にする。
【００６８】
本発明は、メディア・コンテンツに信頼性よく一致するメディア・フィンガープリントを実行するためのコンピュータシステム４００の使用に関する。本発明の実施の一形態によれば、遠隔オブジェクトでクエリを書き換えることが、メインメモリ４０６に記憶された１つ以上の命令の１つ以上のシーケンスを実行するプロセッサ４０４に応答して、コンピュータシステム４００により提供される。そのような命令は、記憶装置４１０のような別の機械可読媒体からメインメモリ４０６に読み込まれる。メインメモリ４０６に保存された命令のシーケンスを実行すると、プロセッサ４０４はここで述べた処理ステップを実施する。マルチタスク配置での１つ以上のプロセッサもまた、メインメモリ４０６に保存された命令のシーケンスを実行するのに用いられる。代替の実施の一形態では、本発明を実行するソフトウェアの命令の代わりに、または組み合わせて、固定シーケンスの回路を用いてもよい。よって、本発明の実施の一形態は、ハードウェアの回路とソフトウェアとのいかなる特定の組合せに限定されるものではない。
【００６９】
本書で用いる用語「機械可読媒体」は、機械を特定の方法で作動するデータを提供するのに関与するいかなる媒体をも意味する。コンピュータシステム４００を用いて実行される実施の一形態では、たとえば、実行用にプロセッサ４０４に命令を提供するのに、種々の機械可読媒体が含まれる。そのような媒体は、多くの形をとり、不揮発性記憶媒体、揮発性媒体および伝送媒体を含むが、これらには限定されない。記憶媒体には、不揮発性媒体と揮発性媒体とを含む。不揮発性媒体には、たとえば、記憶装置４１０のような、光または磁気ディスクを含む。揮発性媒体には、メインメモリ４０６のような、ダイナミックメモリを含む。伝送媒体には、バス４０２を備えるワイヤを含むところの、同軸ケーブル、銅線および他の導体や光ファイバーを含む。伝送媒体は、電波および赤外線データ通信の間に生ずるもののような、音波や光波の形を取ることもできる。そのような媒体のすべては、メディアにより送られる命令が、その命令を機械に読み込む物理的メカニズムにより検知できるように、実体的でなければならない。
【００７０】
機械可読媒体の一般的な形には、たとえば、フロッピーディスク、フレキシブルディスク、ハードディスク、磁気テープまたは他の磁気媒体、ＣＤ−ＲＯＭ、他の光学媒体、パンチカード、紙テープまたは孔のパターンを有する他のレガシーもしくは他の物理媒体、ＲＡＭ、ＰＲＯＭおよびＥＰＲＯＭ、フラッシュＥＰＲＯＭ、他のメモリチップもしくはカートリッジ、後述する搬送波、または、コンピュータが読むことができる他の媒体を含む。
【００７１】
実行用にプロセッサ４０４に１つ以上の命令の１つ以上のシーケンスを運ぶのに、種々の形のコンピュータ可読媒体が含まれる。たとえば、初めには命令は遠隔コンピュータの磁気ディスクで送られた。遠隔コンピュータはその命令をダイナミックメモリに取り込み、モデムを用いて電話線で送信できる。コンピュータシステム４００でしか使えないモデムは、電話線のデータを受信し、赤外線送信機を用いて信号を赤外線信号に変換する。バス４０２に接続された赤外線検出器は、赤外線信号で送られたデータを受信し、データをバス４０２に載せる。バス４０２は、データをメインメモリ４０６に送り、そこからプロセッサ４０４は命令を取り出し、実行する。オプションとして、メインメモリ４０６が受信した命令は、プロセッサ４０４での実行前もしくは後のいずれかに記憶装置４１０に記憶される。
【００７２】
コンピュータシステム４００はまた、バス４０２に接続される通信インターフェース４１８を含む。通信インターフェース４１８は、ローカルネットワーク４２２に接続されたネットワークリンク４２０に双方向データ通信結合を提供する。たとえば、通信インターフェース４１８は、総合デジタル通信網（ＩＳＤＮ）またはデジタル加入者回線（ＤＳＬ）、対応するタイプの電話回線にデータ通信接続を提供する他のモデムである。別の例として、通信インターフェース４１８は、互換性のあるローカルエリアネットワーク（ＬＡＮ）へのデータ通信接続を提供するＬＡＮカードでもよい。無線リンクもまた、行うことができる。そのような実施において、通信インターフェース４１８は、種々のタイプの情報を表現するデジタルデータストリームを搬送する電気、電磁または光学信号を送受信する。
【００７３】
ネットワークリンク４２０は、典型的には、１つ以上のネットワークを通じて他のデータデバイスへのデータ通信を提供する。たとえば、ネットワークリンク４２０は、ローカルネットワーク４２２を通じて、ホストコンピュータ４２４またはインターネットサービスプロバイダ（ＩＳＰ）４２６により運営されるデータ機器への接続を提供する。ＩＳＰ４２６は順に、今一般的に「インターネット」４２８と呼ばれるワールドワイド・パケットデータ通信ネットワークを通じて、データ通信サービスを提供する。ローカルネットワーク４２２とインターネット４２８は共に、デジタルデータストリームを搬送する電気、電磁または光学信号を用いる。デジタルデータをコンピュータシステム４００から、およびコンピュータシステム４００へ運ぶ、種々のネットワークを通じての信号およびネットワークリンク４２０上のまた通信インターフェース４１８を通じての信号は、情報を運ぶ搬送波の例示的な形である。
【００７４】
コンピュータシステム４００は、プログラムコードを含み、ネットワーク（単数および複数）、ネットワークリンク４２０および通信インターフェース４１８を通じて、メッセージを送信し、データを受信できる。インターネットの例では、サーバ４３０は、インターネット４２８、ＩＳＰ４２６、ローカルネットワーク４２２および通信インターフェース４１８を通じて、アプリケーションプログラム用に要求されたコードを伝達してもよい。本発明によれば、そのようにダウンロードされたアプリケーションは、本書で説明するように、メディア・コンテンツに信頼性よく一致するメディア・フィンガープリントの実行を提供する。
【００７５】
受信したコードは、受信されるとプロセッサ４０４で実行され、および／または、後に実行するために記憶装置４１０もしくは他の不揮発性記憶装置に記憶される。この方法により、コンピュータシステム４００は、搬送波の形でアプリケーションコードを獲得する。
【００７６】
図５は、本発明の実施の一形態を実行する例示のＩＣデバイス５００を示す。ＩＣデバイス５００は、インプット／アウトプット（Ｉ／Ｏ）機構５０１を有する。Ｉ／Ｏ機構５０１は、インプット信号を受信し、それらをルーティング構成５１０経由で中央処理装置（ＣＰＵ）５０２へ送り、ＣＰＵ５０２は記憶装置５０３と一緒に機能する。Ｉ／Ｏ機構５０１はまた、ＩＣデバイス５００の他の構成からアウトプット信号を受信し、ルーティング構成５１０について信号フローの一部をコントロールできる。
デジタル信号処理（ＤＳＰ）機構は、少なくともデジタル信号処理に関する機能を実施する。インターフェース５０５は、外部信号にアクセスし、それらをＩ／Ｏ機構５０１へ送り、ＩＣデバイス５００が信号をエクスポートできるようにする。ルーティング構成５１０は、ＩＣデバイス５００の種々の構成間で信号と電力を送る。
【００７７】
論理ゲートアレイのような、設定可能な、および／または、プログラム可能な処理要素（ＣＰＰＥ）５１１は、ＩＣデバイス５００の専用機能を実施し、実施の一形態では、メディア・コンテンツに信頼性よく一致するメディア・フィンガープリントを抽出し処理することに関連する。記憶装置５１２は、十分なメモリセルをＣＰＰＥ５１１専用とし、効率的に機能する。ＣＰＰＥは１つ以上の専用ＤＳＰ機構５１４を含んでもよい。
【００７８】
［例示のビデオ・シグネチャ生成］
図６は、信号セグメント３のビデオコンテンツを分析してそのコンテンツを識別または表現するビデオ・シグネチャ１９３を生成するビデオ・シグネチャ・エクストラクタ６００の概略的ブロック図を示す。図示の例では、信号セグメント３は一連のビデオフレーム３ａ〜３ｄを含む。ビデオ信号が、ビデオコンテンツに加えオーディオコンテンツも搬送するなら、オーディオコンテンツを表現するオーディオシグネチャが、オーディオコンテンツを様々な方法で処理することにより得られる。
【００７９】
［ビデオ・シグネチャ・エクストラクタ］
ビデオ・シグネチャ・ジェネレータ６００を図７に図示する。この実施では、イメージ・プリプロセッサ６１０は、フレーム３ａ、３ｂ、３ｃ、３ｄで搬送される画像用の一連のフォーマットに依存しないイメージを獲得する。空間領域プロセッサ６３０は、フォーマットに依存しないイメージをダウンサンプルして、フォーマットに依存しないイメージの一連の低解像度の表現を生成する。時間領域プロセッサ６５０は、一連の低解像度の表現の合成を表現する値を生成する。そして、ビデオ・シグネチャプロセッサ６７０は、ハッシュ関数を合成値に適用して信号セグメント３のコンテンツを表現し識別するビデオ・シグネチャ１９３を生成する。プロセッサ６１０、６３０、６５０、６７０で実施される処理は、種々の方法で実行できる。これらの処理の好適な実行を以下に説明する。
【００８０】
［イメージ・プリプロセッサ］
一つの例示の実行では、信号セグメント３の各ビデオフレーム３ａ、３ｂ、３ｃ、３ｄは、ピクセルＤのアレイで表現される画像を搬送する。イメージ・プリプロセッサ６１０は、各フレームの画像のフォーマットに依存しないイメージを導き出す。フォーマットに依存しないイメージはピクセルＦのアレイによって表現される。フォーマットに依存しないイメージの誘導は色々な方法で行われる。いくつかの例を以下に説明する。
【００８１】
ある用途では、ビデオ・シグネチャ・ジェネレータ６００は、４８０×６４０ピクセルの標準画質（ＳＤ）解像度および１０８０×１９２０ピクセルの高画質（ＨＤ）解像度の順次走査および飛び越し走査を含む種々のフォーマットのビデオコンテンツを搬送するテレビビデオ信号用シグネチャを生成する。イメージ・プリプロセッサ６１０は、各フレームの画像を興味のある全ての信号フォーマットに共通のフォーマットを有するフォーマットに依存しないイメージに変換する。好適な実行では、フォーマットに依存しないイメージのピクセルＦは、フレーム中のピクセルＤをダウンサンプルすることにより得られ、ビデオフレームが異なったフォーマットに変換される時に生ずる変更に対する感度を低減する。
【００８２】
一例では、フォーマットに依存しないイメージの解像度は１２０×１６０ピクセルの解像度を有するように選定され、その解像度は、順次走査と飛び越し走査の両方のＨＤおよびＳＤ解像度のイメージを搬送するテレビ信号用に便利な選択である。イメージ・プリプロセッサ６１０は、各フレーム画像のピクセルを４の係数でダウンサンプルすることによりＳＤフォーマットのビデオコンテンツをフォーマットに依存しないイメージに変換する。イメージ・プリプロセッサ６１０は、各フレーム画像を切り取り、左側縁から２４０ピクセルと右側縁から２４０ピクセルと除去して１０８０×１４４０ピクセルの解像度の中間イメージを得て、中間イメージのピクセルを９の係数でダウンサンプルすることにより、ＨＤフォーマットのビデオコンテンツをフォーマットに依存しないイメージに変換する。
【００８３】
ビデオ信号が、ビデオのフレームが２フィールドにアレンジされた飛び越し走査フォーマットのコンテンツを搬送するなら、その信号は、フォーマットに依存しないイメージを得る前に順次走査フォーマットに変換される。あるいは、飛び越し走査フォーマットのフィールドの１つだけからフォーマットに依存しないイメージを獲得することにより、走査フォーマットの選択からより大きな独立性が得られる。たとえば、フォーマットに依存しないイメージは、各フレームの第１フィールドだけから、または、各フレームの第２フィールドだけから得ることもできる。他のフィールドのビデオコンテンツは無視される。この処理により、フォーマットに依存しないイメージを得る前に順次走査フォーマットに変換する必要性を回避する。
【００８４】
適切な切り取りとダウンサンプリングを用いるならば、出来たイメージは基本的にフレーム画像フォーマットに依存せず、次のシグネチャ生成プロセスは異なったフォーマットやフォーマット間の変換から生ずる変更に鈍感となる。このアプローチは、画像がフォーマット変換を受けても、一連のフォーマットに依存しないイメージから生ずるビデオ・シグネチャが一連のフレーム画像のビデオコンテンツを正しく識別する可能性を高める。
【００８５】
フォーマットに依存しないイメージは、意図的に変更に影響されるような画像の領域を含まないのが、好ましい。例えばテレビのようなビデオ用途では、このことは、ロゴや他のグラフィカルなオブジェクトがビデオコンテンツに挿入される、イメージの角や縁を含まないように切り取ることによりなされる。
【００８６】
図８は、上記の切り取りおよびダウンサンプル作業を含むイメージ・プリプロセッサ６１０によってなされるプロセス６１２によって得られる結果の概略的図を提供する。セグメント３内のフレーム３ａの画像は切り取られ、画像の中心部におけるピクセルＤを抽出する。この中心部のピクセルＤがダウンサンプルされ、フォーマットに依存しないイメージ５ａにピクセルＦを得る。一連のイメージ５のフォーマットに依存しないイメージ５ａ、５ｂ、５ｃ、５ｄが、セグメント３の各フレーム３ａ、３ｂ、３ｃ、３ｄに対して得られる。このプロセスは、下記のように表わされる。
｛Ｆｍ｝＝ＩＰ［｛Ｄｍ｝］，  ０≦ｍ≦Ｍ          （１）
ここで、｛Ｆｍ｝＝フレームｍについてのフォーマットに依存しないイメージのピクセルのセット
ＩＰ［  ］＝フレームｍの画像に適用されるイメージ・プリプロセス作業
｛Ｄｍ｝  ＝フレームｍの画像のピクセルのセット
Ｍ      ＝セグメント中のフレームの数
【００８７】
フォーマット変換用に画像のサイズを変更する切り取り作業は、ロゴの挿入のような意図的変更により影響される画像の領域を含まないようにする取り作業と組み合わされ、または、別になされる。切り取り作業は、ダウンサンプル作業の前もしくは後になされる。たとえば、フォーマットに依存しないイメージは、ビデオコンテンツを切り取り、続いて切り取られたイメージをダウンサンプルすることにより得られ、また、ビデオコンテンツをダウンサンプルし、続いてダウンサンプルされたイメージを切り取ることによりなされ、また、上記の２つの切り取り作業の間に行われるダウンサンプル作業により得られる。
【００８８】
各ビデオフレームが、例えば赤、緑、青（ＲＧＢ）で表現されるピクセルを備えるカラーイメージを搬送するなら、各フレームで赤、緑、青のそれぞれに別のフォーマットに依存しないイメージが得られる。フレームの赤、緑、青の値から導き出されるピクセルの輝度あるいは明るさから、各フレームに１つのフォーマットに依存しないイメージが得られるのが好ましい。各ビデオフレームがモノクロイメージを搬送するなら、そのフレームの個々のピクセルの強度からフォーマットに依存しないイメージが得られる。
【００８９】
［空間領域プロセッサ］
例示の実行では、空間領域プロセッサ６３０は、ＧＸピクセル幅でＧＹピクセル高さである領域へフォーマットに依存しないイメージの各々のピクセルＦをグループ化することにより、フォーマットに依存しないイメージのダウンサイズされた低解像度の表現を獲得する。画素Ｅを有する低解像度イメージは、各領域の平均強度を計算することにより、それぞれのフォーマットに依存しないイメージのピクセルＦの強度から導き出される。各低解像度イメージは、Ｋ×Ｌ要素の解像度を有する。このことを、図９に概略的に示す。画素Ｅは、以下の式を実行するプロセスを行うことにより得られる。
【数９】
2011511489.tif 000011
ここで、Ｅｍ（ｋ，ｌ）＝フレームｍの低解像度イメージでの画素
ＧＸ＝ピクセルＦの数で表されたピクセルグループの幅
ＧＹ＝ピクセルＦの数で表されたピクセルグループの高さ
Ｋ＝低解像度イメージの水平解像度
Ｌ＝低解像度イメージの垂直解像度
Ｆｍ（ｉ，ｊ）＝フレームｍのフォーマットに依存しないイメージでのピクセル
【００９０】
グループの水平サイズＧＸはＫ・ＧＸ＝ＲＨとなるように選択され、グループの垂直サイズＧＹはＬ・ＧＹ＝ＲＶとなるように選択され、ここで、ＲＨとＲＶはそれぞれフォーマットに依存しないイメージの水平および垂直解像度である。１２０×１６０ピクセルの解像度のダウンサンプルされたフォーマットに依存しないイメージの要素を生成する上記の例示の実行では、グループのための適当なサイズの一つは８×８であり、低解像度イメージに１２０／８×１６０／８＝１５×２０画素の解像度を提供する。
【００９１】
あるいは、空間領域プロセッサ６３０によりなされるグループ化は、イメージ・プリプロセッサ６１０によりなされる処理と組み合わされ、または、その処理より前に行われてもよい。
【００９２】
ビデオ・シグネチャを生成するのに、高解像度ピクセルＦではなく低解像度画素Ｅを用いることにより、生成されたビデオ・シグネチャは、ビデオ信号コンテンツの詳細を変更するプロセスには敏感ではなくなるが、平均強度は維持する。
【００９３】
［時間領域プロセッサ］
時間領域プロセッサ６５０の例示の実行では、一連の低解像度イメージの合成を表現する値は、各画素Eの時間平均および分散から求められる。
【００９４】
各画素Ｅ（Ｋ，ｌ）の時間平均Ｚ（ｋ，ｌ）は、以下の式から計算できる。
【数１０】
2011511489.tif 000012
【００９５】
あるいは、信号セグメント３内の選定されたセグメントのビデオコンテンツは、以下の式に示すように、画素の重み付平均から時間平均を計算することにより、より重要性が増されてもよい。
【数１１】
2011511489.tif 000013
ここで、ｗｍ＝フレームｍのビデオコンテンツから導き出された低解像度イメージでの画素に対する重み係数
【００９６】
必要に応じて、式３ａまたは３ｂで表される時間領域処理は、式２で表される空間領域処理の前に行われてもよい。
【００９７】
値Ｚ（ｋ，ｌ）は、時間と空間の双方について各画素Ｅ（ｋ，ｌ）の平均強度を表す。したがって、これらの平均値は、信号セグメント３のビデオコンテンツにより表現される動きについてあまり多くの情報を搬送しない。動きの表現は、各画素Ｅ（ｋ，ｌ）の分散を計算することにより求められる。
【００９８】
各画素Ｅ（ｋ，ｌ）についての平均値Ｚ（ｋ，ｌ）が式３ａで示されるように計算されると、それぞれの画素Ｅ（ｋ，ｌ）の分散Ｖ（ｋ，ｌ）が以下の式で計算される。
【数１２】
2011511489.tif 000014
【００９９】
各画素の平均値が式３ｂに示されるように計算されると、それぞれの画素Ｅ（ｋ，ｌ）の分散Ｖ（ｋ，ｌ）が以下の式で計算される。
【数１３】
2011511489.tif 000015
【０１００】
好適な実行においては、一連の低解像度イメージの合成を表わす値は、時間平均Ｚと分散配列Ｖからそれぞれ導き出される２つの階数行列(rank matrix)ＺｒとＶｒの要素の値である。階数行列の各要素の値は、関連する配列でのそれぞれの要素の順位（rank order）を表す。たとえば、要素Ｚ（２，３）が平均値配列の４番目に大きな要素であると、その階数行列Ｚｒでの対応する要素Ｚｒ（２，３）の値は、４に等しくなる。この好適な実行について、合成値ＱＺとＱＶは、以下のように表される。
ＱＺ（ｋ，ｌ）＝Ｚｒ（ｋ，ｌ）  ０≦ｋ＜Ｋ；０≦ｌ＜Ｌ      （５）
ＱＶ（ｋ，ｌ）＝Ｖｒ（ｋ，ｌ）  ０≦ｋ＜Ｋ；０≦ｌ＜Ｌ      （６）
【０１０１】
階数行列の使用は、随意である。代替の実行では、一連の低解像度イメージの合成を表す値は、時間平均Ｚと分散配列Ｖの要素の値である。この代替の実行について、合成値ＱＺとＱＶは、以下のように表される。
ＱＺ（ｋ，ｌ）＝Ｚ（ｋ，ｌ）  ０≦ｋ＜Ｋ；０≦ｌ＜Ｌ      （７）
ＱＶ（ｋ，ｌ）＝Ｖ（ｋ，ｌ）  ０≦ｋ＜Ｋ；０≦ｌ＜Ｌ      （８）
【０１０２】
［ビデオ・シグネチャプロセッサ］
ビデオ・シグネチャプロセッサ６７０はハッシュ関数を合成値ＱＺとＱＶのＫ×Ｌ配列に適用して、２セットのハッシュビットを生成する。これら２つのハッシュビットの組み合わせは、信号セグメント３のコンテンツを識別するビデオ・シグネチャを構成する。ハッシュ関数は合成値の変化には相対的に鈍感で、用いられるハッシュキーの変化にはより敏感であることが好ましい。そのインプットの単一ビットの変化にもアウトプットが大きく変化する、典型的な暗号ハッシュ関数と違って、この用途での好適なハッシュ関数は、入力された合成値の小さな変化に対してほんの僅かなしか変化しないアウトプットを提供する。このことにより、生成されたビデオ・シグネチャは、ビデオコンテンツの小さな変化でほんの僅かしか変化しなくなる。
【０１０３】
一つの適切なハッシュ関数は、１セットのＮＺの基本行列を用いてＱＺ合成値用ＮＺのハッシュビットのセットを生成し、１セットのＮＶの基本行列を用いてＱＶ合成値用ＮＶのハッシュビットのセットを生成する。各々の基本行列は、Ｋ×Ｌの要素配列である。これらの要素は、好ましくは互いに直交するまたはほぼ直交する１セットのベクトルを表す。以下に説明する実行では、基本行列の要素は、これらの要素は互いにほぼ直交するベクトルのセットを表すとの仮定の下で乱数発生器により生成される。
【０１０４】
合成値ＱＺと用いる各基本行列ＰＺｎの行列要素ｐｚｎ（ｋ，ｌ）は、以下の式より生成される。
【数１４】
2011511489.tif 000016
ここで、ＲＮＧ＝乱数発生器のアウトプット
2011511489.tif 000017
【０１０５】
合成値ＱＶと用いる各基本行列ＰＶｎの行列要素ｐｖｎ（ｋ，ｌ）は、以下の式より生成される。
【数１５】
2011511489.tif 000018
【０１０６】
乱数発生器ＲＮＧは、範囲［０，１］に均一に分布する乱数または擬似乱数を発生する。乱数発生器の初期状態は、ハッシュキーにより初期化され、ハッシュ関数と生成されたビデオ・シグネチャを暗号法的により安全にする。
【０１０７】
ハッシュビットＢＺｎの１セットは、Ｎｚ基本行列の各々に合成値ＱＺを先ず投影することにより獲得され、以下のように表される。
【数１６】
2011511489.tif 000019
ここで、ＨＺｎ＝合成値ＱＺの基本行列ＰＺｎへの投影
【０１０８】
すると、ハッシュビットＢＺｎのセットは、各投影を全投影のメジアンと比較し、投影が閾値と等しいか超えるならばハッシュビットを第１の値にセットし、投影が閾値より小さければハッシュビットを第２の値にセットすることにより、求められる。このプロセスの一例は以下のように表される。
【数１７】
2011511489.tif 000020
ここで、
2011511489.tif 000021
2011511489.tif 000022
【０１０９】
ハッシュビットＢＶｎの別のセットが、次式に示すように同様に求められる。
【数１８】
2011511489.tif 000023
2011511489.tif 000024
ここで、ＨＶｎ＝合成値ＱＶの基本行列ＰＶｎへの投影
2011511489.tif 000025
【０１１０】
ビデオ・シグネチャはＮＺ＋ＮＶに等しい全ビット長を有する値を形成する、２セットのハッシュビットの連結により求められる。ＮＺとＮＶの値は、最終的ビデオ・シグネチャに対するＱＺとＱＶの合成値の相対的寄与に重み付けするのに加え、所望の全ビット長を提供するようにセットされる。
【０１１１】
［用途］
［シグネチャ・セット］
ビデオ・シグネチャ・ジェネレータ６００で生成されたシグネチャは、シグネチャが生成されたセグメントのビデオコンテンツを表現する。セグメントよりかなり長い信号のインターバルにおけるビデオコンテンツの信頼性のある識別は、そのインターバルに含まれるセグメントに対しシグネチャのセットを生成することにより得られる。
【０１１２】
図１０に示す線図は、ビデオフレームのいくつかのセグメントを含む信号のインターバルの概略図である。５つのセグメントが示される。信号の第１セグメント３はビデオフレーム３ａ〜３ｄを含む。続く各セグメント４、５、６、７は、それぞれビデオフレーム４ａ〜４ｄ、５ａ〜５ｄ、６ａ〜６ｄ、７ａ〜７ｄを含む。下記のように、ビデオ信号ジェネレータ６００を用いて各セグメントのビデオフレームのコンテンツを処理することにより、これらのセグメントに対してシグネチャのセットが、生成できる。
【０１１３】
各セグメントは、整数のビデオフレームを含む。各セグメントの１連のフレームは、公称長さＬに等しいか公称長さＬの１フレーム期間内の時間のインターバル間にビデオコンテンツを搬送するのが好ましい。用語「フレーム期間」は、１フレームにより搬送されるビデオコンテンツの継続時間を意味する。次のセグメントに対する公称開始時間ｔ＃は、オフセットΔＴだけ互いに分離される。このオフセットは、ビデオ・シグネチャ・ジェネレータ６００により処理される信号の最低フレーム速度のフレーム期間に等しく設定される。たとえば、処理される最低速度が１２フレーム／秒であると、オフセットΔＴは１／１２秒、すなわち約８３．３ミリ秒に等しく設定される。
【０１１４】
公称長さＬは、フレーム速度変換のようなコンテンツ変更に対する次に生成されるビデオ・シグネチャの感度を下げることと、ビデオ・シグネチャにより提供される表現の時間解像度を高くすることとの競合する利益をバランスするように選択される。経験的な研究によれば、ほぼ２秒のビデオコンテンツに対応する公称セグメント長さＬは、多くの用途でよい結果を提供する。
【０１１５】
セグメント長さＬおよびオフセット量ΔＴについて述べた特定の値は、例示に過ぎない。オフセットΔＴが、整数のフレーム期間に等しくないと、次のセグメントの実際の開始時間の間のオフセットは、異なったオフセット量Δ１、Δ２により図に示されるように変化する。必要なら、実際の開始時間の間のオフセットの長さは、公称オフセットΔＴの１フレーム期間内に保たれる。
【０１１６】
図１１は、セグメント３〜７のビデオコンテンツから生成されたビデオ・シグネチャ６９３〜６９７のセットを示す概略ブロック図である。図１０と図１１を参照すると、ビデオ・シグネチャ・ジェネレータ６００は公称開始時間ｔ１で開始するセグメント３のビデオコンテンツを獲得し、そのビデオコンテンツを処理してビデオ・シグネチャ６９３を生成する。つぎにビデオ・シグネチャ・ジェネレータ６００は、公称開始時間ｔ２で開始するセグメント４のビデオコンテンツを獲得し、そのビデオコンテンツを処理してビデオ・シグネチャ６９４を生成する。ビデオ・シグネチャ・ジェネレータ６００は、公称開始時間ｔ３、ｔ４、ｔ５で始まるセグメント５、６、７のビデオコンテンツを処理することにより、ビデオ・シグネチャ６９５、６９６、６９７を生成し続ける。シグネチャは、基本的に所望のセグメント数に対して生成される。
【０１１７】
公称開始時間は、ビデオコンテンツに付随する特定の時間データに対応する必要はない。原則として、公称開始時間とビデオコンテンツ間の調整は、任意である。たとえば、一実行においては、公称開始時間は、処理される信号の開始からの相対的オフセットとして表される。各セグメントは、それぞれの公称開始時間に最も近い開始時間を有するビデオコンテンツを搬送するビデオフレームで始まる。あるいは、各セグメントは、そのセグメントの公称開始時間に及ぶビデオフレームで始まることもできる。基本的に、開始フレームと公称開始時間のいかなる調整を用いてもよい。
【０１１８】
［コピーの検出］
ビデオコンテンツのセグメントから生成されたシグネチャ・セットを用いて、上記のプロセスを含む種々のプロセスでコンテンツが修正されたときにでも、コンテンツを識別することができる。修正されたときでも、特定のビデオコンテンツが参照コンテンツのコピーであるかどうかを信頼性よく判定する能力は、下記を含んで種々の方法で用いることができる。
【０１１９】
［無許可コピーの検出］
ピアツーピアのサーバのネットワークは、コンテンツの配布を容易にできるが、ピアツーピアのサーバ間には多くのコンテンツのコピーが存在するので、所有権のあるコンテンツの無許可のあるいは海賊版のコピーを検出することの困難性を増大している。ネットワークから入手可能な全コンテンツにシグネチャ・セットを生成し、そのシグネチャ・セットを参照シグネチャ・セットのデータベースに対してチェックすることにより、無許可のコピーがネットワーク内に存在するかを、設備は自動的に判定できる。
【０１２０】
［放送の確認］
放送網と契約して特定のコンテンツを配信するビジネスは、放送受信者で受信される信号からシグネチャ・セットを生成し、そのシグネチャ・セットを特定のコンテンツに対する参照シグネチャ・セットと比較することにより契約条件が満たされることを確認することができる。
【０１２１】
［受信の識別］
放送網に評価を提供するビジネスは、受信された信号からシグネチャ・セットを生成し、そのシグネチャ・セットを参照シグネチャ・セットと比較することにより、受信者に受信されたコンテンツを識別できる。
【０１２２】
図１２は、前に列記されたような種々の用途を実行するのに用いられるシステムの概略ブロック図である。ビデオ・シグネチャ・ジェネレータ６００は、パス３１から受信した参照ビデオコンテンツのストリームから参照ビデオ・シグネチャ・セットを生成する。生成した参照ビデオ・シグネチャ・セットは、シグネチャデータベース６８０に記憶される。参照シグネチャ・セットは、用途の実行を容易にする他の情報と一緒に記憶されてもよい。たとえば、参照シグネチャ・セットは、基本的コンテンツそのものと一緒に、または、コンテンツの所有者、コンテンツのライセンス条件、コンテンツのタイトルもしくはコンテンツのテキスト記述などのコンテンツに関する情報と一緒に記憶されてもよい。各参照シグネチャ・セットはデータベース検索キーを有する。このキーは、所望されるどのような方法で導き出されてもよい。そのキーは、関連する参照シグネチャ・セットのシグネチャに基づき、または、導き出されるのが好ましい。
【０１２３】
いかなる特定のビデオコンテンツも、シグネチャデータベースに保存された１つ以上のシグネチャ・セットにより表される参照コンテンツに対してチェックされる。チェックされるコンテンツを、本書では、テスト・コンテンツとする。テスト・ビデオコンテンツの同一性は、ビデオ・シグネチャ・ジェネレータ６０１にパス３３から受信したテスト・ビデオコンテンツから１つ以上のテスト・ビデオ・シグネチャ・セットを生成させ、テスト・ビデオ・シグネチャ・セットをビデオ検索エンジン６８５に渡すことによりチェックされる。ビデオ検索エンジン６８５は、テスト・ビデオ・シグネチャ・セットに正しくまたはほぼマッチする参照ビデオ・シグネチャ・セットをシグネチャデータベース６８０で見つけようとする。
【０１２４】
ある実行では、ビデオ検索エンジン６８５は、ビデオ・シグネチャ・ジェネレータ６０１から１つ以上のテスト・シグネチャ・セットを受信する。各テスト・シグネチャ・セットは、テスト・コンテンツから生成された順序で、順序付けされた一連のテスト・シグネチャＳＴＥＳＴを含む。ビデオ検索エンジン６８５は、シグネチャデータベース６８０からパス６８２経由で参照シグネチャ・セットを受信する。各参照シグネチャ・セットは、対応する参照コンテンツから生成された順序で、順序付けされた一連の参照シグネチャＳＲＥＦを含む。ビデオ検索エンジン６８５は、テスト・コンテンツに対するテスト・シグネチャ・セットと特定の参照コンテンツに対する参照シグネチャゼットの間の相違点の大きさＤＳＭを計算することにより、テスト・コンテンツと特定の参照コンテンツ間の類似性を判定する。この相違点の大きさＤＳＭは、特定の参照コンテンツに対する参照シグネチャ・セットとテスト・シグネチャ・セットとに対する一連のシグネチャの対応するシグネチャ間のハミング距離から導き出される。この大きさは以下の各式を含め、多くの方法で計算できる。
【数１９】
2011511489.tif 000026
ここで、ＤＳＭ＝算定された相違点の大きさ
ＨＤ［ｘ，ｙ］＝シグネチャｘとｙ間のハミング距離
ＳＲＥＦ（ｓ）＝一連の参照シグネチャのｓ番目のシグネチャ
ＳＴＥＳＴ（ｓ）＝一連のテスト・シグネチャのｓ番目のシグネチャ
【０１２５】
ビデオ検索エンジン６８５は、テスト・シグネチャ・セットと最小の相違点の大きさとなる参照シグネチャ・セットを求めてシグネチャデータベース６８０を検索する。この参照シグネチャ・セットと関連する参照コンテンツは、テスト・コンテンツと共通起源を持つ、データベース中の最有力候補である。相違点の大きさがある分類閾値より小さいと、そのテスト・シグネチャ・セットに関連するテスト・コンテンツは、一致する参照シグネチャ・セットに関連する参照コンテンツと共通起源を持つ、または、コピーであるとみなされる。経験的な結果では、各シグネチャ・セットの一連のシグネチャが約２秒のビデオコンテンツを表現すれば、種々のビデオコンテンツについてよい結果が得られることが示される。
【０１２６】
以下の記述で説明を簡単にするため、テスト・コンテンツと特定の参照コンテンツとは、テスト・コンテンツが特定の参照コンテンツと共通起源を有するならば、「マッチングする」と言う。
【０１２７】
上記の分類閾値用に選ばれた値は、テスト・コンテンツと参照コンテンツが互いにマッチングするかマッチングしないかを正しく認識する可能性に影響する。また、誤った判定をする可能性にも影響する。マッチングするコンテンツがマッチングしていないコンテンツに誤って分類される「誤った否定判定」の可能性は、分類閾値の値が低下すると増加する。反対に、マッチングしていないコンテンツがマッチングしているコンテンツと誤って分類される「誤った肯定判定」の可能性は、分類閾値の値が増大すると増加する。
【０１２８】
分類閾値は所望の方法で設定できる。分類閾値を設定するのに用いられる１つの方法は、データベース６８０内の参照シグネチャ・セットにより表されるオリジナルビデオコンテンツを得て、このオリジナルコンテンツのたくさんのコピーを作り出す。コピーは、フレーム速度変換や上述の他の意図的または無意識の修正のいずれかなど、種々の方法で修正される。その方法で、各コピーにテスト・シグネチャ・セットを生成し、テスト・シグネチャ・セットと参照シグネチャ・セット間の相違点の大きさＤＳＭの第１のセットを計算する。その方法でまた、テスト・シグネチャ・セットとオリジナルコンテンツと共通起源を有さない他のビデオコンテンツのシグネチャ・セット間の相違点の大きさＤＳＭの第２のセットを計算する。２つのセットの値の範囲はオーバーラップしなくてもよい。それらがオーバーラップするとしても、オーバーラップの量は、典型的にはそれぞれのセットの値の範囲の極僅かな部分である。分類閾値は、オーバーラップの範囲内または２つのセットがオーバーラップしないならば２つの範囲の間に設定される。この閾値の値は、用途の必要性により調整され、誤った肯定判定または誤った否定判定を引き起こすリスクをバランスする。
【０１２９】
［実行］
本発明の種々の態様を具体化するデバイスは、コンピュータや、汎用コンピュータにあるものと類似のコンポーネントに接続されたデジタル信号プロセッサ（ＤＳＰ）回路などのより特化した構成を含む他のデバイスにより実行されるソフトウェアを含み、様々な方法で実行できる。図１３は、本発明の態様を実行するのに用いられるデバイス７０の概略ブロック図である。プロセッサ７２は、計算資源を提供する。ＲＡＭ７３は、処理のためにプロセッサ７２で使用されるシステムランダムアクセスメモリ（ＲＡＭ）である。ＲＯＭ７４は、デバイス７０を作動するのに必要なプログラムを保存し、場合により本発明の種々の態様を実施するための読み取り専用メモリ（ＲＯＭ）のような固定記憶装置のある形を表す。Ｉ／Ｏコントロール７５は、通信チャンネル７６、７７により信号を受信し送信するインターフェース回路を表す。図示の実施の一形態では、すべての主要な構成はバス７１に接続し、バス７１は複数の物理的または論理的バスを表すが、バスアーキテクチャは本発明の実行には必要ではない。
【０１３０】
汎用コンピュータシステムで実行される実施の一形態では、キーボードまたはマウスとディスプレイのような装置とインターフェースするのに、また、磁気テープや磁気ディスクまたは光媒体などの記憶媒体を有する記憶装置７８をコントロールするのに、追加のコンポーネントを含んでもよい。記憶媒体は、オペレーティングシステム、ユティリティ、およびアプリケーションを動作するための命令のプログラムを記録するのに用いられ、本発明の種々の態様を実行するプログラムを含む。
【０１３１】
［実施例］
実施の一形態では、方法は以下の工程を備え、命令の１つ以上のシーケンスを持っているコンピュータ可読媒体は、１つ以上のプロセッサで実行されると、その命令により１つ以上のコンピュータに以下の工程を実行させ：ａ）ビデオメディア・コンテンツのシーケンスにおけるコンテンツ部分の時間的に関連したグループのビデオメディア・コンテンツの部分の第１表現として、前記第１表現が分割される領域の行列についてコンテンツ要素の量子化されたエネルギ値にアクセスする工程と、ｂ）前記量子化された第１次元空間で基底ベクトルのセットを推定する工程と、ｃ）前記第１表現を、第２次元の空間でのビデオメディア・コンテンツ部分の第２表現に変換する工程であって、第２表現は前記推定した基底ベクトルに基づいた前記第１表現の投影を備え、メディア・フィンガープリントが、少なくとも部分的に前記第２表現に基づいて導き出される。
【０１３２】
実施の一形態では、方法またはコンピュータ可読媒体は、前記第２表現は、幾何学的方向の任意の変化について信頼性よく前記ビデオメディア・コンテンツ部分に対応することを、さらに備える。
【０１３３】
実施の一形態では、方法またはコンピュータ可読媒体は、前記ビデオメディア・コンテンツ部分に関連する解像度より低い解像度に前記第１表現をダウンサンプルすることを、さらに備える。
【０１３４】
実施の一形態では、方法またはコンピュータ可読媒体は、前記第１表現が前記メディア・コンテンツ部分から切り取られることを、さらに備える。
【０１３５】
実施の一形態では、方法またはコンピュータ可読媒体は、前記メディア・コンテンツ部分の前記第１表現が、次のうちの１つ以上と関連することを、さらに備える：
前記シーケンスの１つ以上のビデオフレームの少なくとも１つのセクションと関連する空間領域表現、または、前記シーケンスの１つ以上のビデオフレームの少なくとも１つのセクションと関連する変換された表現。
【０１３６】
実施の一形態では、方法またはコンピュータ可読媒体は、空間領域表現は、前記ビデオフレームに関連する空間解像度に関する粗い特徴を備えることを、さらに備える。
【０１３７】
実施の一形態では、方法またはコンピュータ可読媒体は、変換された表現は、変換関数によりビデオフレーム内の空間的に分散した情報から計算されることを、さらに備える。
【０１３８】
実施の一形態では、方法またはコンピュータ可読媒体は、変換関数は、離散コサイン変換、修正離散コサイン変換、離散フーリエ変換、ウェーブレット変換、高速フーリエ変換の少なくとも１つを備えることを、さらに備える。
【０１３９】
実施の一形態では、方法またはコンピュータ可読媒体は、ビデオメディア・コンテンツ部分は、ビデオコンテンツ部分の時間的に関連するグループの第１の部分を備えることを備え、前記方法は、時間的に関連したビデオコンテンツ部分のグループの少なくとも第２のビデオメディア・コンテンツ部分に工程ａ）から工程ｃ）を繰り返すことと、ｄ）時間的に関連した部分のグループ内の第１のコンテンツ部分と第２のコンテンツ部分を分離する時間期間についての第１のコンテンツ部分と第２のコンテンツ部分の第２表現に平均値を計算する工程をさらに備えることを、さらに備える。
【０１４０】
実施の一形態では、方法またはコンピュータ可読媒体は、第２表現の平均値は、メディア・コンテンツシーケンスの速度の任意の変化について時間的に関連したコンテンツ部分に信頼性よく対応することを、さらに備える。
【０１４１】
実施の一形態では、方法またはコンピュータ可読媒体は、ｅ）第２表現の平均値をランダムベクトルのセットに投影し、投影値のセットを求める工程と、ｆ）閾値を投影値のセットに適用する工程と、ｇ）コンテンツ部分の時間的に関連するグループのメディア・フィンガープリントを計算する工程とをさらに備える。
【０１４２】
実施の一形態では、方法またはコンピュータ可読媒体は、メディア・フィンガープリントはコンテンツ部分の時間的に関連するグループに、その幾何学的方向の任意の変化およびメディア・コンテンツシーケンスの速度の任意の変化において信頼性よく対応することを、さらに備える。
【０１４３】
実施の一形態では、方法またはコンピュータ可読媒体は、ステップｂ）がピクセル値に基づいて特異値分解を計算する工程を備え、基底ベクトルは特異値分解に基づいて推定されることを、さらに備える。
【０１４４】
実施の一形態では、方法またはコンピュータ可読媒体は、少なくとも第１の基底ベクトルは、ピクセル値の最大分散の軸に沿った方向であり、少なくとも第２の基底ベクトルは、第１の基底ベクトルに直交することを、さらに備える。
【０１４５】
実施の一形態では、方法またはコンピュータ可読媒体は、ピクセル値は各領域に関連する平均値の合計を備え、その平均値はその領域からのメディア・コンテンツの少なくとも１つの特質のサンプルに関連することを、さらに備える。
【０１４６】
実施の一形態では、方法は以下の工程を備え、命令の１つ以上のシーケンスを持っているコンピュータ可読媒体は、１つ以上のプロセッサで実行されると、その命令により１つ以上のコンピュータに以下の工程を実行させ：ａ）ビデオメディア・コンテンツのシーケンスにおけるコンテンツ部分の時間的に関連したグループのビデオメディア・コンテンツの部分の第１表現として、前記第１表現が分割される領域の行列についてコンテンツ要素のエネルギ値を量子化する工程であって、前記第１表現が低解像度にダウンサンプルされ、メディア・コンテンツ部分から切り取られる、工程と、ｂ）前記量子化された第１次元空間で基底ベクトルのセットを推定する工程と、ｃ）前記第１表現を、第２次元の空間でのビデオメディア・コンテンツ部分の第２表現に変換する工程であって、第２表現は前記推定した基底ベクトルに基づいた前記第１表現の投影を備え、前記ビデオメディア・コンテンツ部分の第１表現は前記シーケンスの１つ以上のビデオフレームの少なくとも１セクション、または、前記シーケンスの１つ以上のビデオフレームの少なくとも１セクションに関連する変換された表現に関連し、メディア・フィンガープリントが、少なくとも部分的に前記第２表現に基づいて導き出される。
【０１４７】
実施の一形態では、方法またはコンピュータ可読媒体は、第２表現がビデオコンテンツ部分に、その幾何学的方向の任意の変化においてビデオメディア・コンテンツ部分に信頼性よく対応することを、さらに備える。
【０１４８】
実施の一形態では、方法またはコンピュータ可読媒体は、空間領域表現は、ビデオフレームに関連する空間解像度に関する粗い特徴を備えることを、さらに備える。
【０１４９】
実施の一形態では、方法またはコンピュータ可読媒体は、変換された表現は、変換関数によりビデオフレーム内に空間的に分布された情報から計算されることを、さらに備える。
【０１５０】
実施の一形態では、方法またはコンピュータ可読媒体は、変換関数は、離散コサイン変換、修正離散コサイン変換、離散フーリエ変換、ウェーブレット変換あるいは高速フーリエ変換の少なくとも１つを備えることを、さらに備える。
【０１５１】
実施の一形態では、方法またはコンピュータ可読媒体は、ビデオメディア・コンテンツ部分は、ビデオコンテンツ部分の時間的に関連するグループの第１の部分を備えることを備え、前記方法は、時間的に関連したビデオコンテンツ部分のグループの少なくとも第２のビデオメディア・コンテンツ部分に工程ａ）から工程ｃ）を繰り返すことと、ｄ）時間的に関連した部分のグループ内の第１のコンテンツ部分と第２のコンテンツ部分を分離する時間期間についての第１のコンテンツ部分と第２のコンテンツ部分の第２表現に平均値を計算する工程をさらに備えることを、さらに備える。
【０１５２】
実施の一形態では、方法またはコンピュータ可読媒体は、第２表現の平均値は、メディア・コンテンツシーケンスの速度の任意の変化について時間的に関連したコンテンツ部分に信頼性よく対応することを、さらに備える。
【０１５３】
実施の一形態では、方法またはコンピュータ可読媒体は、ｅ）第２表現の平均値をランダムベクトルのセットに投影し、投影値のセットを求める工程と、ｆ）閾値を投影値のセットに適用する工程と、ｇ）コンテンツ部分の時間的に関連するグループのメディア・フィンガープリントを計算する工程とをさらに備える。
【０１５４】
実施の一形態では、方法またはコンピュータ可読媒体は、メディア・フィンガープリントはコンテンツ部分の時間的に関連するグループに、その幾何学的方向の任意の変化およびメディア・コンテンツシーケンスの速度の任意の変化において信頼性よく対応することを、さらに備える。
【０１５５】
実施の一形態では、方法またはコンピュータ可読媒体は、ステップｂ）がピクセル値に基づいて特異値分解を計算する工程を備え、基底ベクトルは特異値分解に基づいて推定されることを、さらに備える。
【０１５６】
実施の一形態では、方法またはコンピュータ可読媒体は、少なくとも第１の基底ベクトルは、ピクセル値の最大分散の軸に沿った方向であり、少なくとも第２の基底ベクトルは、第１の基底ベクトルに直交することを、さらに備える。
【０１５７】
実施の一形態では、方法またはコンピュータ可読媒体は、ピクセル値は各領域に関連する平均値の合計を備え、その平均値はその領域からのメディア・コンテンツの少なくとも１つの特質のサンプルに関係することを、さらに備える。
【０１５８】
実施の一形態では、システムは、少なくとも１つのプロセッサと、前記少なくとも１つのプロセッサで実行されると前記システムに上記した方法の少なくとも１工程を行わせるコード化された命令を備えるコンピュータ可読記憶媒体とを備える。
【０１５９】
実施の一形態では、システムは、上記した方法の少なくとも１工程を行う手段を備える。
【０１６０】
実施の一形態では、上記した方法の１つ以上の工程を行うように構成されまたはプログラムされた集積回路（ＩＣ）デバイスは、上記したシステムの１つ以上を具現化し、配置し、または、支援する。
【０１６１】
実施の一形態では、ＩＣデバイスは、ＩＣが少なくとも１つのプロセッサ、プログラム可能論理回路、マイクロコントローラ、フィールド・プログラマブル・ゲート・アレイ、または、特定用途向けＩＣの１つを備えることを、さらに備える。
【０１６２】
［均等、拡張、代替および諸々のこと］
前述の明細書では、本発明の実施の形態を実行ごとに異なる多くの特定な詳細を参照して説明した。よって、何が本発明であるのか、また何が出願人により発明であると意図されているかの、唯一かつ排他的な示唆は、本出願により公表され、請求項が特定の形で公表された特許請求の範囲であり、その後の補正を含む。それゆえ、請求項で明確に記載されていない限定、要素、特性、特徴、利点あるいは属性は、いかなる場合でも請求項の範囲を限定しない。したがって、明細書および図面は、限定的な意味ではなく、説明的な意味としてみなされるべきである。
【図１】
2011511489.tif 000027
【図２】
2011511489.tif 000028
【図３】
2011511489.tif 000029
【図４】
2011511489.tif 000030
【図５】
2011511489.tif 000031
【図６】
2011511489.tif 000032
【図７】
2011511489.tif 000033
【図８】
2011511489.tif 000034
【図９】
2011511489.tif 000035
【図１０】
2011511489.tif 000036
【図１１】
2011511489.tif 000037
【図１２】
2011511489.tif 000038
【図１３】
2011511489.tif 000039
【手続補正書】
【提出日】平成21年8月5日(2009.8.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ａ）ビデオメディア・コンテンツのシーケンスのコンテンツ部分の時間的に関連するグループのビデオメディア・コンテンツ部分の第１表現について、前記第１表現が分割される領域のマトリックスに対してコンテンツ要素の量子化されたエネルギ値を評価する工程と；
ｂ）前記量子化されたエネルギ値から第１の次元空間の基底ベクトルを推定する工程と；
ｃ）前記第１表現を、第２の次元空間のビデオメディア・コンテンツ部分の第２表現に変換する工程であって、前記第２表現は前記推定した基底ベクトルに基づく前記第１表現の投影を備える、工程とを備え；
前記第２表現に少なくとも一部は基づいて、メディア・フィンガープリントが導き出され；
前記ビデオメディア・コンテンツ部分は、ビデオコンテンツ部分の前記時間的に関連したグループの第１の部分を備え；
前記時間的に関連したビデオコンテンツ部分のグループの少なくとも第２のビデオメディア・コンテンツ部分について工程ａ）からｃ）を繰り返す工程と；
ｄ）前記時間的に関連した部分のグループ内の前記第１のコンテンツ部分と前記第２のコンテンツ部分とを分離する時間期間にわたり前記第１のコンテンツ部分と前記第２のコンテンツ部分との前記第２表現の平均値を計算する工程と；
ｅ）前記第２表現の平均値をランダムベクトルのセットに投影して投影値のセットを得る工程と；
ｆ）前記投影値のセットに閾値を適用する工程と；
ｇ）前記投影値のセットに基づいて前記コンテンツ部分の時間的に関連するグループについてメディア・フィンガープリントを計算する工程とを備え；
前記メディア・フィンガープリントは、前記コンテンツ部分の時間的に関連するグループの１つ以上の幾何学的方向の任意の変化や前記メディア・コンテンツのシーケンスの速度の任意の変化において前記コンテンツ部分の時間的に関連するグループに対応する；
方法。
【請求項２】
前記第２表現は、前記ビデオメディア・コンテンツ部分の幾何学的方向の任意の変化において前記ビデオメディア・コンテンツ部分に対応する；
請求項１の方法。
【請求項３】
前記第１表現は、前記ビデオメディア・コンテンツ部分に関連する解像度より低い解像度にダウンサンプルされる；
請求項１の方法。
【請求項４】
前記第１表現は、前記ビデオメディア・コンテンツ部分から切り取られる；
請求項１の方法。
【請求項５】
前記ビデオメディア・コンテンツ部分の前記第１表現は：
前記シーケンスの１つ以上のビデオフレームの少なくとも１つのセクションに関連する空間領域表現；または、
前記シーケンスの前記１つ以上のビデオフレームの前記少なくとも１つのセクションに関連する変換された表現；
の１つ以上に関係する；
請求項１の方法。
【請求項６】
前記空間領域表現は、前記ビデオフレームに関連する空間解像度に関して粗い特徴を備える；
請求項５の方法。
【請求項７】
前記変換された表現は、変換関数により前記ビデオフレーム内の空間的に分散した情報から計算される；
請求項５の方法。
【請求項８】
前記変換関数は：
離散コサイン変換；
修正離散コサイン変換；
離散フーリエ変換；
ウェーブレット変換；または、
高速フーリエ変換；
の少なくとも１つを備える；
請求項５の方法。
【請求項９】
前記第２表現の平均値は、前記メディア・コンテンツのシーケンスの速度の任意の変化において前記時間的に関連したコンテンツ部分のグループに対応する；
請求項１の方法。
【請求項１０】
工程ｂ）は、前記ピクセル値に基づき特異値分解を計算する工程を備え；
前記基底ベクトルは、前記特異値分解に基づき推定される；
請求項１の方法。
【請求項１１】
前記基底ベクトルの少なくとも第１は、前記ピクセル値の最大分散の軸に沿った方向であり、前記基底ベクトルの少なくとも第２は前記第１基底ベクトルに直交する；
請求項１０の方法。
【請求項１２】
前記ピクセル値は、前記領域それぞれに関連する平均値の合計を備え；
前記平均値は、前記領域からの前記メディア・コンテンツの少なくとも１つの特質のサンプルに関係する；
請求項１の方法。
【請求項１３】
ａ）ビデオメディア・コンテンツのシーケンスにおけるコンテンツ部分の時間的に関連するグループのビデオメディア・コンテンツ部分の第１表現について、前記第１表現が分割されてなる複数の領域のマトリックスに対してコンテンツ要素のエネルギ値を量子化する工程であって、前記第１表現は低解像度にダウンサンプルされ、前記メディア・コンテンツ部分から切り取られる、工程と；
ｂ）前記量子化されたエネルギ値から第１の次元空間の基底ベクトルのセットを推定する工程と；
ｃ）前記第１表現を、第２の次元空間のビデオメディア・コンテンツ部分の第２表現に変換する工程であって、前記第２表現は前記推定した基底ベクトルに基づく前記第１表現の投影を備える、工程とを備え；
前記ビデオメディア・コンテンツ部分の前記第１表現は：
前記シーケンスの１つ以上のビデオフレームの少なくとも１つのセクションに関連する空間領域表現；または、
前記シーケンスの前記１つ以上のビデオフレームの前記少なくとも１つのセクションに関連する変換された表現；
の１つ以上に関係し；
メディア・フィンガープリントが前記第２表現に少なくとも一部は基づいて導き出され；
前記ビデオメディア・コンテンツ部分は、ビデオコンテンツ部分の前記時間的に関連したグループの第１の部分を備え；
前記時間的に関連したビデオコンテンツ部分のグループの少なくとも第２のビデオメディア・コンテンツ部分について工程ａ）からｃ）を繰り返す工程と；
ｄ）前記時間的に関連した部分のグループ内の前記第１のコンテンツ部分と前記第２のコンテンツ部分とを分離する時間期間にわたり前記第１のコンテンツ部分と前記第２のコンテンツ部分との前記第２表現の平均値を計算する工程と；
ｅ）前記第２表現の平均値をランダムベクトルのセットに投影して投影値のセットを得る工程と；
ｆ）前記投影値のセットに閾値を適用する工程と；
ｇ）前記コンテンツ部分の時間的に関連するグループについてメディア・フィンガープリントを計算する工程とを備え；
前記メディア・フィンガープリントは、前記コンテンツ部分の時間的に関連するグループの幾何学的方向の任意の変化や前記メディア・コンテンツのシーケンスの速度の任意の変化において前記コンテンツ部分の時間的に関連するグループに対応する；
方法。
【請求項１４】
前記第２表現は、前記ビデオメディア・コンテンツ部分の幾何学的方向の任意の変化において前記ビデオメディア・コンテンツ部分に対応する；
請求項１３の方法。
【請求項１５】
前記空間領域表現は、前記ビデオフレームに関連する空間解像度に関して粗い特徴を備える；
請求項１３の方法。
【請求項１６】
前記変換された表現は、変換関数により前記ビデオフレーム内の空間的に分散した情報から計算される；
請求項１３の方法。
【請求項１７】
前記変換関数は：
離散コサイン変換；
修正離散コサイン変換；
離散フーリエ変換；
ウェーブレット変換；または、
高速フーリエ変換；
の少なくとも１つを備える；
請求項１６の方法。
【請求項１８】
前記第２表現の平均値は、前記メディア・コンテンツのシーケンスの速度の任意の変化において前記時間的に関連したコンテンツ部分のグループに対応する；
請求項１７の方法。
【請求項１９】
工程ｂ）は、前記ピクセル値に基づき特異値分解を計算する工程を備え；
前記基底ベクトルは、前記特異値分解に基づき推定される；
請求項１３の方法。
【請求項２０】
前記基底ベクトルの少なくとも第１は、前記ピクセル値の最大分散の軸に沿った方向であり、前記基底ベクトルの少なくとも第２は前記第１基底ベクトルに直交する；
請求項１９の方法。
【請求項２１】
前記ピクセル値は、前記領域それぞれに関連する平均値の合計を備え；
前記平均値は、前記領域からの前記メディア・コンテンツの少なくとも１つの特質のサンプルに関係する；
請求項１３の方法。
【請求項２２】
前記ビデオメディア・コンテンツ部分は、少なくとも１つの次のビデオメディア・コンテンツ部分に関して、前記コンテンツ部分の時間的に関連するグループの前記ビデオメディア・コンテンツに時間窓を備え；
前記ビデオメディア・コンテンツのシーケンスについて工程ａ）からｃ）を繰り返す工程と；
時間窓に変換関数を適用する工程であって、時間窓により前記ビデオメディア・コンテンツの早い部分と次の部分とが時間において関係付けられる、工程とを備え；
前記変換関数を適用する工程は、時間窓にわたる前記ビデオ・コンテンツのイメージの特徴の変化を表す；
請求項１の方法。
【請求項２３】
前記時間窓は、前記ビデオメディア・コンテンツの時間的に早い部分を備える；
請求項２２の方法。
【請求項２４】
システムであって：
少なくとも１つのプロセッサと；
前記少なくとも１つのプロセッサで実行されると、前記システムに請求項１〜２３の１つ以上に記載の方法の少なくとも１つの工程を行うようにさせるコード化された命令を備えるコンピュータ可読記憶媒体とを備える；
システム。
【請求項２５】
請求項１〜２３の１つ以上に記載の方法の少なくとも１つの工程を実施する手段を備える；
システム。
【請求項２６】
請求項１〜２３に記載の１つ以上の方法の工程を実施するように構成されまたはプログラムされた、または、請求項２４〜２５に記載のシステムの１つ以上を具体化し、配置し、若しくはサポートする；
集積回路（ＩＣ）デバイス；
【請求項２７】
前記ＩＣは、プロセッサ、プログラム可能論理回路、マイクロコントローラ、フィールド・プログラマブル・ゲート・アレイ、または、特定用途向けＩＣの少なくとも１つを備える；
請求項２６のＩＣデバイス。
【請求項２８】
１つ以上のプロセッサで実行されると、前記１つ以上のプロセッサに：
請求項１〜２３の１つ以上に記載の方法の少なくとも１つの工程を行うようにさせ；
請求項２４〜２５の１つ以上に記載のシステムの少なくとも１つを構成しもしくはプログラムさせ；または、
請求項２６〜２７に記載されたＩＣデバイスの少なくとも１つを構成しもしくはプログラムさせる；
コード化された命令を備える；
コンピュータ可読記憶装置。
【国際調査報告】
2011511489.tif 000040
2011511489.tif 000041