(57)【特許請求の範囲】
【請求項１】
ビデオのシグネチャを発見する方法であって、
前記ビデオのフレームＮを複数のセルに分割するステップと、
フレームＮの各セルのビデオ属性を計算するステップと、
前記ビデオのフレームＮ＋１を前記複数のセルに分割するステップと、
フレームＮ＋１の各セルのビデオ属性を計算するステップと、
前記ビデオのフレームＮ−１を複数のセルに分割するステップと、
フレームＮ−１の各セルのビデオ属性を計算するステップと、
前記複数のセルの内各セルについて、前記フレームＮのビデオ属性と前記フレームＮ＋１のビデオ属性との間の差を含む、フレームＮとフレームＮ＋１間の差分メトリックを計算するステップと、
前記複数のセルの内各セルについて、前記フレームＮのビデオ属性と前記フレームＮ−１のビデオ属性との間の差を含む、フレームＮとフレームＮ−１間の差分メトリックを計算するステップと、
フレームＮとフレームＮ＋１間の前記差分メトリックが第１閾値を超過し、フレームＮとフレームＮ−１間の前記差分メトリックが第２閾値を超過しないのに応じて、フレームＮおよびフレームＮ＋１の一方または双方からの情報を含むビデオ・シグネチャを生成するステップと、
を含み、
前記複数のセルがＭ個のセルを含み、フレーム毎のＭ次元ベクトルが、前記複数のＭ個のセルの各々について前記ビデオ属性を含み、
前記ビデオ・シグネチャの生成が、フレームＮの前記Ｍ次元ベクトルをフレームＮ＋１の前記Ｍ次元ベクトルと連結することを含む、方法。
【請求項２】
請求項１記載の方法において、フレームＮとフレームＮ＋１間の前記差分メトリックを計算するステップが、フレームＮの前記Ｍ次元ベクトルとフレームＮ＋１の前記Ｍ次元ベクトル間のユークリッド距離を計算するステップを含む、方法。
【請求項３】
請求項１記載の方法において、前記ビデオ属性が当該セルの平均輝度である、方法。
【請求項４】
請求項１記載の方法において、前記ビデオ属性が、当該フレームの全てのセルの平均輝度に対して正規化した当該セルの平均輝度である、方法。
【請求項５】
請求項１記載の方法において、前記ビデオ・シグネチャが、フレームＮ＋１の前記ビデオ属性の各々と連結されたフレームＮの前記ビデオ属性の各々を含む、方法。
【請求項６】
請求項１記載の方法において、前記ビデオのフレームＮを前記複数のセルに分割するステップが、前記フレームＮを４×４格子のセルに分割するステップを含む、方法。
【請求項７】
請求項１記載の方法において、フレームＮ＋１はフレームＮの直後であり、フレームＮ−１はフレームＮの直前である、方法。
【請求項８】
請求項１記載の方法において、フレームＮ−１をＭ個のセルに分割し、フレームＮ−１のＭ次元ベクトルが、各セルについての前記ビデオ属性を含み、フレームＮとフレームＮ−１間の前記差分メトリックを計算するステップが、フレームＮの前記Ｍ次元ベクトルとフレームＮ−１の前記Ｍ次元ベクトル間のユークリッド距離を計算するステップを含む、方法。
【請求項９】
請求項１記載の方法であって、タイムスタンプを前記ビデオ・シグネチャに関連付けるステップを含む、方法。
【請求項１０】
請求項１記載の方法であって、前記第１閾値および前記第２閾値が等しい、方法。
【請求項１１】
ビデオのシグネチャを生成する方法であって、
前記ビデオのフレームＮをＭ個のセルの格子に分割するステップであって、フレームＮの各セルについての平均輝度値を含む、ステップと、
前記ビデオのフレームＮ＋１をＭ個のセルのグリッドに分割するステップであって、フレームＮ＋１の各セルについての平均輝度値を含む、ステップと、
前記ビデオのフレームＮ−１をＭ個のセルのグリッドに分割するステップであって、フレームＮ−１の各セルについての平均輝度値を含む、ステップと、
フレームＮ、フレームＮ＋１およびフレームＮ−１の各々のＭ次元ベクトルを計算するステップであって、前記Ｍ次元ベクトルが、その異なる次元毎に、当該フレームとは異なるセルの平均輝度値を含む、ステップと、
前記フレームＮのＭ次元ベクトルと前記フレームＮ＋１のＭ次元ベクトル間のユークリッド距離を計算するステップと、
前記フレームＮのＭ次元ベクトルと前記フレームＮ−１のＭ次元ベクトル間のユークリッド距離を計算するステップと、
フレームＮとフレームＮ＋１間の前記ユークリッド距離が第１閾値を超過し、且つ、フレームＮとフレームＮ−１間の前記ユークリッド距離が第２閾値を超過しないことに応じて、フレームＮ＋１の前記Ｍ次元ベクトルと連結されたフレームＮの前記Ｍ次元ベクトルを含むビデオ・シグネチャを生成するステップと
を含む、方法。
【請求項１２】
請求項１１記載の方法において、１つのフレームの各セルについての前記平均輝度値が、当該フレームの全てのセルについての平均輝度に対して正規化される、方法。
【請求項１３】
請求項１１記載の方法において、前記Ｍ個のセルの格子が４×４格子である、方法。
【請求項１４】
請求項１１記載の方法において、更に、繰り返し後続のフレームに進み、前記ビデオ内の追加のシグネチャを検索するステップを含む、方法。
【請求項１５】
請求項１１記載の方法において、タイムスタンプを前記ビデオ・シグネチャに関連付けるステップを含む、方法。
【請求項１６】
論理サブシステムによって実行可能な命令を保持するデータ保持サブシステムであって、
ビデオ内にある一連の３つの連続フレームを繰り返し検査して、場面変化を求め、各前記検査が、
前記ビデオのフレームＮをＭ個のセルを含む格子に分割し、
フレームＮのＭ次元ベクトルを計算し、前記Ｍ次元ベクトルが、該Ｍ次元ベクトルの異なる次元毎に、フレームＮとは異なるセルの平均輝度値を含み、
前記ビデオのフレームＮ＋１を、Ｍ個のセルを含む格子に分割し、
フレームＮ＋１のＭ次元ベクトルを計算し、前記Ｍ次元ベクトルが、該Ｍ次元ベクトルの異なる次元毎に、フレームＮ＋１とは異なるセルの平均輝度値を含み、
前記ビデオのフレームＮ−１を、Ｍ個のセルを含む格子に分割し、
フレームＮ−１のＭ次元ベクトルを計算し、前記Ｍ次元ベクトルが、該Ｍ次元ベクトルの異なる次元毎に、フレームＮ−１とは異なるセルの平均輝度値を含み、
フレームＮの前記Ｍ次元ベクトルとフレームＮ＋１の前記Ｍ次元ベクトル間のユークリッド距離を計算し、
フレームＮとフレームＮ＋１間の前記ユークリッド距離が第１閾値を超過する場合に、前記フレームＮの前記Ｍ次元ベクトルとフレームＮ−１の前記Ｍ次元ベクトル間のユークリッド距離を計算し、
フレームＮとフレームＮ−１間の前記ユークリッド距離が第２閾値を超過しないことに応じて、フレームＮ＋１の前記Ｍ次元ベクトルと連結されたフレームＮの前記Ｍ次元ベクトルを含むビデオ・シグネチャを生成する
ことを含む、データ保持サブシステム。
【請求項１７】
請求項１６記載のデータ保持サブシステムにおいて、１つのフレームの各セルについての前記平均輝度値が、当該フレームの全てのセルについての平均輝度に対して正規化される、データ保持サブシステム。
【請求項１８】
請求項１６記載のデータ保持サブシステムにおいて、タイムスタンプを前記ビデオ・シグネチャに関連付けることを含む、データ保持サブシステム。
【請求項１９】
請求項１６記載のデータ保持サブシステムにおいて、前記格子が４×４格子である、データ保持サブシステム。
【発明の詳細な説明】
【従来技術】
【０００１】
[0001]  メタデーターのような識別情報は、ディジタル・ビデオ・コンテンツには含まれないことが多い。その結果、視聴者が名称、製作年、コンテンツのジャンル、あるいは彼または彼女が満足のいく視聴体験のために望むかもしれない他の情報を特定できないことが多い。
【発明の概要】
【０００２】
[0002]  この摘要は、詳細な説明の章において以下で更に説明する概念から選択したものを簡略化された形式で紹介するために、設けられている。この摘要は、特許請求する主題の主要な特徴や必須の特徴を特定することを意図するのではなく、特許請求する主題の範囲を限定するために使用されることを意図するのでもない。更に、特許請求する主題は、本開示のいずれの部分に記されるいずれの欠点を解決する実施態様にも、そして全ての欠点を解決する実施態様にも限定されない。
【発明が解決しようとする課題】
【０００３】
ビデオ・シグネチャを発見する方法を提供する。
【課題を解決するための手段】
【０００４】
この方法は、ビデオのフレームＮ、フレームＮ＋１、およびＮ−１の各々を複数のセルに分割し、各フレームのセル毎にビデオ属性を計算するステップを備えている。フレームＮおよびＮ＋１、ならびにＮおよびＮ−１の間で、各フレームのビデオ属性に基づいて差分メトリック(difference metric)を計算し、この差分メトリックを閾値と比較する。フレームＮおよびＮ＋１の差分メトリックが第１閾値を超過し、フレームＮおよびＮ−１の差分メトリックが第２閾値を超過しない場合、フレームＮおよびフレームＮ＋１からの情報をビデオ・シグネチャとして用いる。
【図面の簡単な説明】
【０００５】
【図１】図１は、本発明の一実施形態にしたがって、ビデオ・ストリームのシグネチャを発見する方法を示す流れ図である。
【図２】図２は、本明細書において開示する一実施形態による、ビデオおよび付随する輝度値からのフレームを模式的に示す。
【図３】図３は、基準シグネチャを検索インデックス・データーベースに入力する実施形態例を示す流れ図である。
【図４】図４は、クライアント・シグネチャを検索インデックスに入力する実施形態例を示す流れ図である。
【図５】図５は、本明細書において開示する一実施形態を実行するための非限定的な計算デバイスを模式的に示す。
【発明を実施するための形態】
【０００６】
[0008]  ディジタル・ビデオのような、外部識別情報を欠くメディア・コンテンツの再生では、満足のいく視聴体験のためには、視聴者がそのビデオの名称、それが製作された日付、および他の情報を必要とする場合があるので、問題を生ずることがある。未知のビデオについての識別情報を突き止めるために、ビデオ内における場面変化(shot change)を特定することによってビデオ・シグネチャを生成することができる。場面変化は、ビデオの２つの連続するフレームＮおよびＮ＋１間における画像情報の大きな変化、それに加えてフレームＮと直前のフレームＮ−１との間における画像情報の小さな変化によって、定めることができる。次いで、場面変化からの情報を用いて、ビデオ・シグネチャを生成することができる。ビデオ・シグネチャは、同じビデオの異なるバージョンにおいて容易に再生可能であるとよい。
【０００７】
[0009]  このようなビデオ・シグネチャは、基準ビデオのライブラリに対するビデオ・シグネチャ、およびこのような基準ビデオ毎に識別情報（例えば、メタデーター）を含むビデオ・シグネチャ・データーベースと比較することができる。一致が見いだされた場合、一致した基準ビデオからの外部識別情報を未知のビデオに適用することができる。実施形態の中には、検査されるシグネチャと基準シグネチャとの間におけるユークリッド距離を用いて、一致が存在するか否か判断するとよい場合がある。実施形態の中には、このようなユークリッド距離がゼロでなければいけない場合があり、更に他の実施形態では、小さな差が許容される場合もある。
【０００８】
[0010]  図１は、本開示の一実施形態にしたがって、ビデオ・シグネチャを発見する方法１００を表す流れ図を示す。方法１００は、ビデオ再生および／またはビデオ・ストリーミングが可能な計算デバイスによって実行することができる。計算デバイスの例には、デスクトップ・コンピューター、ラップトップ・コンピューター、移動体計算デバイス、およびＴＶセット・トップ・ボックスが含まれるが、これらに限定されるのではない。計算デバイスは、更に、ビデオ・ストリームを受信するためおよび／またはビデオ・シグネチャ・データーベースにアクセスするために、ネットワークを通じて他の計算デバイスに接続することもできる。これについては以下で更に詳しく説明する。計算デバイスについてのこれ以上の詳細は、図５を参照して説明する。
【０００９】
[0011]  １０２において、方法１００は、ビデオ内部にあるフレームを複数のセルに分割するステップを含む。一連のフレームＮ、フレームＮ＋１、およびフレームＮ−１の各フレームをＭ個のセルに分割する。一例では、Ｍ個のセルは、４対４（４×４）の格子に配列された、１６個の等しいサイズのセルを含むことができる。他の例では、Ｍ個のセルは、５×５の格子に配列された２５個の等しいサイズのセルを含むことができる。いずれの数のセルをいずれの配列にしても、本開示の範囲内に該当するものとする。
【００１０】
[0012]   １０４においてセル毎のビデオ属性を計算する。実施形態の中には、ビデオ属性が、そのセル内における画素毎の輝度値の平均をとることによって計算した、そのセルについての平均輝度(average luminance)である場合がある。実施形態の中には、ビデオ属性が、そのフレームの全てのセルについての平均輝度に対して正規化した、そのセルについての平均輝度であるとよい場合がある。各セルの輝度の格付け順序(rank order)、平均カラー値等というような、他の適した属性を用いることもできる。
【００１１】
[0013]  １０６において、フレームＮとフレームＮ＋１との間における第１差分メトリックを計算する。一例として、差分メトリックは、フレームＮについて計算したベクトルとフレームＮ＋１について計算したベクトルとの間のユークリッド距離とすることができる。この差分メトリックを計算するために、１０８においてフレームＮおよびフレームＮ＋１の各々について、Ｍ次元ベクトルを決定する。フレーム毎のＭ次元ベクトルは、異なる次元毎に、そのフレームからの異なるセルのビデオ属性を含む。
【００１２】
[0014]  例えば、図２は、１６個のセル（即ち、セルＮ１、Ｎ２、．．．、Ｎ１６）を含む４×４格子に分割されたビデオのフレームＮを示す。更に、図２の表２０４は、フレームＮのセル毎に輝度値を示す。セル毎に、そのセルの各画素についての輝度値から、平均輝度を計算する。この例では、輝度は、０から１までの目盛りによって表され、０は輝度がなく（即ち、セルは真っ黒であり、光が放出されない）、１は最大輝度である（即ち、セルは真っ白であり、画素が放出できる最大量の光が放出されている）。例えば、セルＮ１は０．２の輝度値を有する。Ｍ次元ベクトルは、分割したフレームの１６個のセルの各々についての輝度に基づく１６次元ベクトルを含むことができる。例えば、フレームＮは、以下からなる１６次元ベクトルを有する。
【００１３】
【数１】
0005980311.tif 000002
【００１４】
一方、フレームＮ＋１は、輝度値の表２０６に基づき、以下からなる１６次元ベクトルを有する。
【００１５】
【数２】
0005980311.tif 000003
【００１６】
図１に戻って、１１０において、方法１００は、これらのベクトル間におけるユークリッド距離を計算するステップを含む。例えば、図２において、図２のフレームＮとフレームＮ＋１との間のユークリッド距離は、以下の式を用いて計算することができる。
【００１７】
【数３】
0005980311.tif 000004
【００１８】
ここで、ｐは、フレームＮのベクトル、ｑはフレームＮ＋１のベクトル、そして、ベクトルは１６次元からなるので、ｎ＝１６となる。したがって、図２のフレームＮとフレームＮ＋１との間のユークリッド距離は、約１．２１となる。
【００１９】
[0015]  再び図１を参照すると、１１２において、フレームＮとフレームＮ−１との間で第２の差分メトリックを計算する。１０６において計算した差分メトリックと同様に、１１４において、フレームＮおよびフレームＮ−１の各々について、Ｍ次元ベクトルを決定し、これらのベクトルは、１１６において第２のユークリッド距離を決定するときに用いられる。
【００２０】
[0016]  １１８において、フレームＮおよびＮ＋１の間で計算した第１差分メトリックを、第１閾値と比較する。第１差分メトリックが第１閾値よりも大きい場合、本方法は１２０に進む。閾値よりも大きくない場合、本方法は１２８に進む。１２０において、第２差分メトリックを第２閾値と比較する。第２差分メトリックが第２閾値よりも小さい場合、本方法は１２２に進み、閾値よりも小さくない場合、本方法は１２８に進む。第１および第２差分メトリックを比較するための第１および第２閾値は同様でもよい。あるいは、２つの閾値は異なってもよい。これらの閾値は、経験的に、またはいずれかの適したメカニズムによって決定すればよい。
【００２１】
[0017]  フレームＮ−１について図２に示すフレーム例を参照すると、表２０２における輝度値に基づく１６次元ベクトルは、フレームＮのベクトルと同じとなる。これは、これらのフレームが同じ画像を表すからである。したがって、前述した同じ式を用いてユークリッド距離を計算すると、フレームＮおよびＮ−１の間では、距離が０となる。
【００２２】
[0018]  これらのフレームが場面変化を構成するか否か判断するために、計算したユークリッド距離を、各々、閾値と比較することができる。この例では、第１および第２閾値は等しく、経験的に１に等しく決められている。つまり、フレームＮからフレームＮ＋１までの距離は、ΔＮ→Ｎ＋１＝１．２１であり、これは第１閾値の１よりも大きい。フレームＮからフレームＮ−１までの距離は、ΔＮ→Ｎ−１＝０であり、この場合同じく１である第２閾値よりも小さい。第１距離は閾値よりも大きく、第２距離は閾値よりも大きくないので、場面変化が特定される。
【００２３】
[0019]  図１の１２２において、フレームＮおよびフレームＮ＋１の一方または両方からの情報を、ビデオ・シグネチャとして含める。１２４において、フレームＮのベクトルをフレームＮ＋１のベクトルと連結して、シグネチャを生成する。この実施形態では、フレームＮおよびフレームＮ＋１の輝度値に基づく、３２次元ベクトルである。１２６において、場面変化が起こるビデオの始点に対する時間を示すタイムスタンプと、シグネチャを関連付ける。次いで、シグネチャを所定のシグネチャのデーターベースに入力する(submit)ことができ、および／またはシグネチャを検索インデックスに入力して検索し、一致する基準シグネチャを求める。例えば、ビデオが識別情報を含む既知のビデオである場合、データーベースを検索して未知のビデオとの一致を求めるときというような、後の時点において用いるために、シグネチャをその識別情報と共に基準ビデオ・シグネチャ・データーベースに出力することができる。あるいは、ビデオが、識別情報を含まない未知のビデオである場合、生成したシグネチャを検索インデックスに入力し、既知の基準ビデオ内に含まれる一致するシグネチャを基準ビデオ・シグネチャ・データーベースから検索することができる。
【００２４】
[0020]  １２８において、ビデオ内で他のシグネチャを特定するために検査を続けなければならないと判断した場合、方法１００は続いて繰り返し後続のフレームを検査することができる。追加の検査を継続すべきか判断するためには、事実上あらゆる判断基準を用いることができる。例えば、このような検査は、ビデオの終端に達していなければ、またはユーザーが検査を終了することを示さなければ、継続することができる。検査を継続する場合、本方法は１３０において１フレーム進め、方法１００の先頭に戻る。加えて、第１または第２差分メトリックのいずれかが、１１８および１２０において、閾値に対するそのそれぞれの条件を満たさない場合、１フレーム進めることができ、本方法は繰り返し後続のフレームを検査することができる。尚、後続の検査に対するステップの一部は、以前の検査から繰り返さなくてもよい場合もあることは理解されてしかるべきである。例えば、検査したフレームの１つが既に分割されていて、そのフレームに対してＭ次元マトリクスが求められている場合、このような分割および計算を繰り返す必要はない。
【００２５】
[0021]  一方、検査を継続すべきでないと判断した場合（例えば、ビデオにおける全てのシグネチャを識別し終えている場合）、本方法は終了する。
[0022]  尚、方法１００は、記載した順序で実行する必要はないことは理解されてしかるべきである。例えば、フレームＮとフレームＮ−１との間の差分メトリックは、フレームＮとフレームＮ＋１との間の差分メトリックの計算の前に、後に、または同時に計算してもよい。同様に、第１差分メトリックを閾値と比較するのは、第２差分メトリックの閾値との比較の前、後、または同時でもよい。
【００２６】
[0023]  等しいサイズのセルの格子の平均輝度値を用いることによって、場面変化は、ビデオに操作が行われた後でも、特定することができる。例えば、インターネットを通じて配信されるビデオでは、コントラスト、明るさ等を元のビデオ・ソースから変更するのは極普通である。フレーム全体についての平均輝度に正規化されたセル毎の平均輝度を利用することによって、相対的輝度の差を考慮に入れることができる。更に、場面変化の識別は、ビデオのタイミングには関係ないので、速度を上げたりまたは下げたりしたビデオでも特定することができる。最後に、ビデオのクリップが少なくとも１つの場面変化を含む限り、このクリップも識別することができる。
【００２７】
[0024]  場面変化を特定しシグネチャを作成するプロセスは、識別情報を含むビデオ・コンテンツ、および識別情報を含まないビデオ・コンテンツに対しても実行することができる。既知のビデオからのビデオ・シグネチャは、基準データーベースにおけるそのビデオと関連付けることができる。このようなデーターベースを検索する一方法例は、ローカル鋭敏型ハッシュ(locality sensitive hashing)を含む。この方法では、各基準シグネチャに、ハッシュ・コードと称するコードを付与し、各ハッシュ・コードをハッシュ表のバケット(bucket)に分与する。未知のビデオ・シグネチャ、またはクライアント・シグネチャにもハッシュ・コードを付与する。クライアント・シグネチャが分与されるバケットは、クライアント・シグネチャと同様の参照シグネチャのみを相応に含む。これらから、ユークリッド距離のような差分メトリックを、クライアント・シグネチャと基準シグネチャとの間で計算することができる。
【００２８】
[0025]  基準ビデオ・シグネチャにハッシュ・コードを生成する方法例３００について、図３を参照しながら説明する。３０２において、方法３００は、ｎ個で１組のランダム・ベクトル（ｖ１，ｖ２，．．．ｖｎ）を生成するステップを含む。これらの成分は、独立であり、同一の分布に従う正規ランダム変数(identically distributed normal random variable)である。ｎ個のランダム・ベクトルを１回生成することができ、３０４において、前述の１組を用いて、生成したシグネチャ毎にハッシュ・コードを決定することができる。以下の非限定的な例について、４×４格子に分割したフレームに対応する３２次元ベクトルを参照しながら説明する。
【００２９】
[0026]  ３０６において、ハッシュＨｉをランダム・ベクトル毎に決定する。各Ｈｉは、以下の式を用いて計算することができる。
【００３０】
【数４】
0005980311.tif 000005
【００３１】
ここで、Ｓは３２次元基準シグネチャであり、ｖｉは３２次元ランダム・ベクトルであり、Ｂはバケット・サイズであり、これらは経験的に決定することもできる。Ｂが大きい程信頼性が高い検索結果を得ることができるが、ハッシュ・バケットのサイズが増大し、したがって、そのバケット内にあるシグネチャの数が増大することのために、そのバケット内において検索を行うのに必要な時間長が長くなる。３０８において、次に、ハッシュを二進に変換しハッシュ・コードを得る。Ｈｉをｉ＝１，２，．．．ｎについて決定し、次いで３１０において、全ての二進に変換し、連結してスーパー・ハッシュ・コードＨを得る。方法３００は、３１２において、各スーパー・ハッシュ・コードにインデックスを付けて、シグネチャが発生するビデオからのタイムスタップ、ビデオの名称等のようなタグと共に、基準ハッシュ表のバケットに入れるステップを含む。３１４において、ハッシュすべき基準シグネチャが未だ他にもある場合、本プロセス自体を繰り返す。
【００３２】
[0027]  図４は、未知のシグネチャ、またはクライアント・シグネチャを検索インデックスに入力して、一致する基準シグネチャを発見する方法４００の一実施形態を表す流れ図を示す。方法４００は、４０２において、クライアント・シグネチャに対してクエリー・ハッシュ・コードを決定するステップを含む。図３を参照して説明した方法と同様に、４０６において、クライアント・シグネチャ、ランダム・ベクトル（４０４において、３０２で生成した１組から引き出す）、およびバケット・サイズに基づいて、その組のランダム・ベクトル毎に、ハッシュを決定する。４０８において各ハッシュ・コードを二進に変換し、４１０において全ての二進ハッシュ・コードを連結して、クライアント・シグネチャに対するクエリー・スーパー・ハッシュ・コードＨ’を生成する。クエリー・スーパー・ハッシュ・コードＨ’を、基準ハッシュ表のバケットに割り当て、４１２において、そのバケットに格納されている全ての基準ハッシュを戻す。４１４において、クライアント・シグネチャとバケットにおける各基準シグネチャとの間のユークリッド距離のような差分メトリックを計算することができる。４１６において、閾値よりも小さいユークリッド距離を有する全ての基準シグネチャを、一致として戻す。４１８において一致が存在しない場合、本方法は４２４に進む。１つよりも多い一致が４２０において存在する場合、そのシグネチャは、コマーシャルのような共通コンテンツから派生したと見なすことができ、または低品質のシグネチャであると見なすことができ、したがって、本方法は４２４に進む。４１８および４２０において、１つの一致のみが存在すると判断された場合、クライアント・シグネチャおよび基準シグネチャが同じビデオからである確率が高い。この場合、４２２においてクライアント・ビデオを基準ビデオとして特定することができ、名称、日付け等のような、この基準ビデオに随伴する情報をクライアント・ビデオに追加することができる。４２４において、方法４００は、ビデオ内でシグネチャを検索して他の一致を求め続けることが必要であるか否か判断する。例えば、最初に一致を発見することができなかった場合、または多数の一致が発見された場合、ビデオ内で追加のクライアント・シグネチャに対する一致を求め続けることが必要なこともある。検索を継続すべきであると判断した場合、方法４００は４２６においてビデオにおける次のシグネチャに進み、方法４００の開始に戻る。
【００３３】
[0028]  加えて、クライアント・シグネチャと基準シグネチャとの間の差分メトリックを超える一致の精度を高めることができる。これは、ビデオ内における１つよりも多いクライアント・シグネチャが、そのビデオからの基準シグネチャと一致することを検証することによって、遂行することができる。更に、既知のビデオと未知のビデオとの間に、多数の一致するシグネチャが発見された場合、基準ビデオにおける２つのシグネチャからのタイムスタンプ間の差と、クライアント・ビデオの同じ２つのシグネチャのタイムスタップ間の差との相関を取ることによって、精度を更に検証することができる。図１に関して先に説明したように、タイムスタンプをビデオ・シグネチャと関連付けることができる。クライアント・ビデオ・コンテンツは、基準ビデオと比較して、変更されていることもあるので、絶対時間相関付け(absolute time correlation)を用いるのは精度が高い検証方法ではない場合もある。何故なら、クライアント・ビデオを短縮することや、または余分なビデオ情報を含むことがあるからである。しかしながら、２つのタイムスタンプ間の差を用いると、精度高い相関付けを行うことができる。例えば、基準ビデオの第１ビデオ・シグネチャをタイムスタンプ１：３５と関連付けることができ、そのビデオの第２シグネチャを１：５０と関連付けることができる。この例では、２つの間の差は０：１５である。クライアント・ビデオが、２：１５のタイムスタンプを有する基準シグネチャと一致するシグネチャと、２：３０のタイムスタンプを有する第２基準シグネチャと一致する第２シグネチャとを有する場合、一致が正確である可能性は高い。何故なら、２つの一致するシグネチャがあり、これらのシグネチャのタイムスタップ間の差が同じであるからである。
【００３４】
[0029]  実施形態の中には、以上で説明した方法およびプロセスを、１つ以上のコンピューターを含む計算システムに繋げることができる場合がある。具体的には、本明細書において説明した方法およびプロセスは、コンピューター・アプリケーション、コンピューター・サービス、コンピューターＡＰＩ、コンピューター・ライブラリー、および／または他のコンピューター・プログラム生産物として実現することができる。
【００３５】
[0030]  図５は、以上で説明した方法およびプロセスの１つ以上を実行することができる、非限定的な計算システム５０２を模式的に示す。計算システム５０２は、簡素化された形態で示されている。尚、本開示の範囲から逸脱することなく、事実上あらゆるコンピューター・アーキテクチャーを使用できることは言うまでもない。異なる実施形態では、計算システム５０２は、メインフレーム・コンピューター、サーバー・コンピューター、デスクトップ・コンピューター、ラップトップ・コンピューター、タブレット・コンピューター、家庭用娯楽コンピューター、ネットワーク計算デバイス、移動体計算デバイス、移動体通信デバイス、ゲーミング・デバイス等の形態をなすこともできる。
【００３６】
[0031]  計算システム５０２は、ロジック・サブシステム５０４とデーター保持サブシステム５０６とを含む。計算システム５０２は、任意に、ディスプレイ・サブシステム５０８、通信サブシステム５１０、および／または図５には示されていない他のコンポーネントも含むことができる。また、任意に、計算システム５０２は、例えば、キーボード、マウス、ゲーム・コントローラー、カメラ、マイクロフォン、および／またはタッチ・スクリーンのような、ユーザー入力デバイス５１２も含むことができる。
【００３７】
[0032]  計算システム５０２は、サーバー５１４のような遠隔計算デバイスと、ネットワーク５１６を通じて通信するように構成することができる。計算システム５０２と同様、サーバー５１４も論理サブシステム５１８とデーター保持サブシステム５２０とを含む。サーバー５１４は、ユーザーが視聴するために、ビデオ・ストリームを計算システム５０２に送ることができる。ビデオ・ストリームに識別情報が欠けている場合、図１および図２を参照して説明したように、ビデオ・ストリームを検索してビデオ・シグネチャを求めることができる。更に、サーバー５１４または他のサーバーは、基準ビデオを検索してビデオ・シグネチャを求めることができ、タグ付けされた基準シグネチャを格納するために、基準シグネチャ・データーベース５２２を利用することもできる。あるいは、基準シグネチャ・データーベース５２４を、サーバーから離れて格納することもでき、サーバーはネットワークを通じてこのデーターベースにアクセスすることができる。
【００３８】
[0033]  ハッシュ表の分散型の性質のために、サーバー５１４の役割を分散型サーバー・ネットワークに分担させるとよい。この場合、負荷均衡部がある。負荷均衡部は、計算システム５０２と通信し、着信するシグネチャ照合要求に対するハッシュ値に応じて、数個のサーバーの内１つにシグネチャ照合を委任する。各サーバーは、データーベースの内、ハッシュ表からの一定のハッシュ・バケットに対応する部分集合をホストする。任意に、重複がある可能性もある。その場合、各サーバーがハッシュ・バケットを保持するが、ハッシュ表全体が分散システム全域にわたって示されるように、各バケットはあるサーバーによって保持される。
【００３９】
[0034]  論理サブシステム５０４は、１つ以上の命令を実行するように構成されている１つ以上の物理デバイスを含むことができる。例えば、論理サブシステムは、１つ以上のアプリケーション、サービス、プログラム、ルーチン、ライブラリー、オブジェクト、コンポーネント、データー構造、または他の論理的構造体の一部である１つ以上の命令を実行するように構成することができる。このような命令は、タスクを実行するため、データー型を実装するため、１つ以上のデバイスの状態を変換するため、またはそれ以外で所望の結果に到達するために実現することができる。
【００４０】
[0035]  論理サブシステムは、ソフトウェア命令を実行するように構成されている１つ以上のプロセッサーを含むことができる。加えてまたは代わりに、論理サブシステムは、ハードウェアまたはファームウェア命令を実行するように構成されている１つ以上のハードウェアまたはファームウェア論理機械を含むこともできる。論理サブシステムのプロセッサーは１つのコアまたはマルチコアであってもよく、そこで実行されるプログラムは、並列処理または分散処理に合わせて構成することができる。論理サブシステムは、任意に、２つ以上のデバイスにわたって分散されている個別のコンポーネントを含むこともあり、これらのデバイスは、離れて配置されること、および／または協調処理(coordinated processing)を可能にするように構成することができる。論理サブシステムの１つ以上の態様は、クラウド計算構成に構成され、離れてアクセス可能なネットワーク接続計算デバイスによって、仮想化および実行することができる。
【００４１】
[0036]  データー保持サブシステム５０６は、１つ以上の物理的、非一時的デバイスを含むことができる。これらのデバイスは、本明細書において説明した方法およびプロセスを実現するために、データーおよび／または論理サブシステムによって実行可能な命令を保持するように構成されている。このような方法およびプロセスを実現するとき、データー保持サブシステム５０６の状態を転換することができる（例えば、異なるデーターを保持するため）。
【００４２】
[0037]  データー保持サブシステム５０６は、リムーバブル媒体および／または内蔵媒体を含むことができる。データー保持サブシステム５０６は、とりわけ、光メモリー・デバイス（例えば、ＣＤ、ＤＶＤ、ＨＤ−ＤＶＤ、ブルー・レイ・ディスク等）、半導体メモリー・デバイス（例えば、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ等）、および／または磁気メモリー・デバイス（例えば、ハード・ディスク・ドライブ、フロッピー（登録商標）・ディスク・ドライブ、テープ・ドライブ、ＭＲＡＭ等）を含むことができる。データー保持サブシステム５０６は、以下の特性の内１つ以上を有するデバイスを含むことができる。揮発性、不揮発性、ダイナミック、スタティック、リード／ライト、リード専用、ランダム・アクセス、順次アクセス、位置アドレス可能、ファイル・アドレス可能、およびコンテンツ・アドレス可能。実施態様の中には、論理サブシステム５０４およびデーター保持サブシステム５０６を、特定用途集積回路またはチップ上システムのような、１つ以上の共通デバイスに統合できる場合もある。
【００４３】
[0038]  また、図５は、リムーバブル・コンピューター読み取り可能記憶媒体５２６の形態としたデーター保持サブシステムの態様も示す。これは、データーおよび／または本明細書において説明した方法およびプロセスを実現するために実行可能な命令を格納および／または転送するために用いることができる。リムーバブル・コンピューター読み取り可能記憶媒体５２６は、とりわけ、ＣＤ、ＤＶＤ、ＨＤ−ＤＶＤ、ブルー・レイ・ディスク、ＥＥＰＲＯＭ、および／またはフロッピー（登録商標）・ディスクの形態をなすことができる。
【００４４】
[0039]  尚、データー保持サブシステム５０６は、１つ以上の物理的、非一時的デバイスを含むことは認められてしかるべきである。対照的に、実施形態の中には、本明細書において説明した命令の態様を、一時的に、純粋な信号（例えば、電磁信号、光信号等）によって伝搬させることができる場合もある。この信号は、物理デバイスによって少なくとも有限の期間保持されることはない。更に、本開示に関するデーターおよび／または他の形態の情報を、純粋な信号によって伝搬させることもできる。
【００４５】
[0040]  「モジュール」、「プログラム」、および「エンジン」という用語は、１つ以上の特定の機能を実行するために実現される計算システム５０２の態様を記述するために用いることができる。場合によっては、このようなモジュール、プログラム、またはエンジンは、データー保持サブシステム５０６によって保持されている命令を実行する論理サブシステム５０４によってインスタンス化することもできる。尚、異なるモジュール、プログラム、および／またはエンジンを異なるアプリケーション、サービス、コード・ブロック、オブジェクト、ルーチン、ＡＰＩ、関数等からインスタンス化してもよいことは言うまでもない。同様に、同じモジュール、プログラム、および／またはエンジンを、異なるアプリケーション、サービス、コード・ブロック、オブジェクト、ルーチン、ＡＰＩ、関数等によってインスタンス化してもよい。「モジュール」、「プログラム」、および「エンジン」という用語は、個々の実行可能ファイル、データー・ファイル、ライブラリー、スクリプト、データーベース・レコード等またはその集合を含むことを意図している。
【００４６】
[0041]  尚、本明細書において用いる場合、「サービス」は、多数のユーザー・セッションに跨がって実行可能であり、１つ以上のシステム・コンポーネント、プログラム、および／またはその他のサービスに利用可能なアプリケーション・プログラムであってもよいことは認められてしかるべきである。実施態様の中には、クライアントからの要求に応答して、サービスがサーバー上で実行できる場合もある。
【００４７】
[0042]  ディスプレイ・サブシステム５０８は、含まれる場合、データー保持サブシステム５０６によって保持されているデーターの視覚的表現を提示するために用いることができる。本明細書において説明した方法およびプロセスが、データー保持サブシステムによって保持されているデーターを変化させると、つまりデーター保持サブシステムの状態を転換させると、ディスプレイ・サブシステム５０８の状態も同様に転換して、基礎となるデーターの変化を視覚的に表すことができる。ディスプレイ・サブシステム５０８は、事実上あらゆるタイプの技術を利用する１つ以上のディスプレイ・デバイスを含むことができる。このようなディスプレイ・デバイスは、共有筐体内において論理サブシステム５０４および／またはデーター保持サブシステム５０６と組み合わせることもでき、あるいはこのようなディスプレイ・デバイスは、周辺ディスプレイ・デバイスであってもよい。
【００４８】
[0043]  通信サブシステム５１０は、含まれる場合、計算システム５０２をサーバー５１４のような１つ以上の他の計算デバイスと通信状態で結合するように構成することができる。通信サブシステム５１０は、１つ以上の異なる通信プロトコルと互換性のある有線通信デバイスおよび／またはワイヤレス通信デバイスを含むことができる。非限定的な例として、通信サブシステムは、ワイヤレス電話ネットワーク、ワイヤレス・ローカル・エリア・ネットワーク、有線ローカル・エリア・ネットワーク、ワイヤレス・ワイド・エリア・ネットワーク、有線ワイド・エリア・ネットワーク等を通じた通信に合わせて構成することができる。実施形態の中には、通信サブシステムによって、インターネットのようなネットワークを通じて、計算システム５０２がメッセージを他のデバイスに送ること、および／または計算システム５０２がメッセージを他のデバイスから受信するが可能になる場合もある。
【００４９】
[0044]  本明細書において説明した構成および／または手法は性質上例示であること、そしてこれらの具体的な実施形態や例を限定的な意味で捕らえてはならないことは言うまでもない。何故なら、多数の変形が可能であるからである。本明細書において説明した具体的なルーチンまたは方法は、あらゆる数の処理方策の内１つ以上を表すことができる。したがって、例示した種々の動作は、例示したシーケンスで、他のシーケンスで、並列で実行してもよく、場合によっては省略してもよい。同様に、以上で説明したプロセスの順序も変更してもよい。
【００５０】
[0045]  本開示の主題は、種々のプロセス、システムおよび構成、ならびにその他の特徴、機能、および／または本明細書において開示した固有性(properties)、更にはそのいずれかおよび全ての均等物の、全ての新規で非自明のコンビネーションおよびサブコンビネーションを含むこととする。
【図１】
0005980311.tif 000006
【図２】
0005980311.tif 000007
【図３】
0005980311.tif 000008
【図４】
0005980311.tif 000009
【図５】
0005980311.tif 000010