(57)【要約】  ビデオコンテンツの部分間の一致を検出するシステムおよび方法。一致モジュールが、入力ビデオを表す入力ビデオフィンガープリントと、参照データベース内の参照ビデオを表す一セットの参照フィンガープリントとを受け取る。一致モジュールは、参照フィンガープリントと入力フィンガープリントとを比較して、参照ビデオセットからの候補セグメントのリストを生成する。各候補セグメントは、入力ビデオと一致する可能性がある参照ビデオ中の時間的にローカライズされた部分を含む。そのセグメントを一致セグメントとして、または不一致セグメントとして分類する分類要素が各候補セグメントに適用される。次いで、一致したとして分類されたセグメントに基づいて参照ビデオセットからの参照ビデオの一致部分を識別したという結果が出力される。
2010537585.tif 000002
【特許請求の範囲】
【請求項１】
複製ビデオコンテンツを検出するためにコンピュータによって実行される方法であって、
入力ビデオを表す入力フィンガープリントを受け取るステップと、
参照ビデオセットから候補セグメントリストを生成するステップであって、前記候補セグメントリストは、前記参照ビデオセット内の参照ビデオ中の時間的にローカライズされたセグメントを含む、生成ステップと、
分類要素を用いて、一致候補セグメントまたは不一致候補セグメントの何れかとして、前記候補セグメントリストからの候補セグメントを分類するステップと、
前記候補セグメントの前記分類に基づいて、前記参照ビデオセットから参照ビデオの一致部分を識別する結果を生成するステップと
を具備する方法。
【請求項２】
前記参照ビデオセットから前記候補セグメントリストを生成する前記ステップが、
前記参照ビデオセット内の前記参照ビデオを表す参照フィンガープリントを取得するステップと、
前記入力フィンガープリントと前記参照フィンガープリントとの間の部分一致を識別するステップと、
前記識別した部分一致に基づいて最初の候補参照ビデオセットを決定するステップとを含む、請求項１の方法。
【請求項３】
前記入力フィンガープリントに対する入力サブフィンガープリントセットを取得するステップと、ここで、各入力サブフィンガープリントが入力サブフィンガープリントキーのシーケンスを含み、
前記参照ビデオに対する参照サブフィンガープリントセットを取得するステップと、ここで、各参照サブフィンガープリントが参照サブフィンガープリントキーのシーケンスを含み、
前記参照サブフィンガープリントキーと前記入力サブフィンガープリントキーとの一致に基づいて、前記最初の候補参照ビデオセットを決定するステップと
を更に具備する、請求項２の方法。
【請求項４】
前記参照ビデオと前記入力ビデオとの間の時間的にローカライズされた一致に基づいて各参照ビデオに対する性能指数を決定するステップと、
前記性能指数に基づいて前記最初の候補参照ビデオセットを決定するステップと
を更に具備する、請求項２の方法。
【請求項５】
前記参照ビデオを表す参照サブフィンガープリントを、特徴が最大のものから最小のものまでソート順にソートするステップと、
前記参照サブフィンガープリントの前記ソート順に少なくとも一部基づいて、前記候補セグメントを決定するステップと
を更に具備する、請求項２の方法。
【請求項６】
参照ビデオを表す参照サブフィンガープリントの参照キーを、特徴が最大のものから最小のものまでソート順にソートするステップと、
前記参照キーの前記ソート順に少なくとも一部基づいて、前記候補セグメントを決定するステップと
を更に具備する、請求項２の方法。
【請求項７】
前記入力ビデオを表す入力ビデオサブフィンガープリントと、参照ビデオを表す参照ビデオサブフィンガープリントとの間の時間的に連続する一致を決定するステップと、
前記時間的に連続する一致に基づいて前記候補セグメントリストを決定するステップと
を更に具備する、請求項２の方法。
【請求項８】
前記候補セグメントを分類するステップが、
既知の一致モデルに基づいて、前記参照ビデオと前記候補セグメントとの間の一致品質を示す品質尺度を決定するステップと、
前記品質尺度に基づいて、一致セグメントまたは不一致セグメントとして前記候補セグメントを分類するステップと
を含む、請求項１の方法。
【請求項９】
前記入力フィンガープリントから値の一部を表す入力キーを受け取るステップと、
前記入力キーと一致するキーを有する前記参照ビデオセットから、参照ビデオ中の時間的にローカライズされたセグメントを識別する一つ以上のサブフィンガープリント識別子を得るために、逆引きインデックステーブルに問い合わせるステップと
を更に具備する、請求項１の方法。
【請求項１０】
前記入力キーが入力サブフィンガープリントからの隣接値を含む、請求項９の方法。
【請求項１１】
前記入力キーが入力サブフィンガープリントからの非隣接値を含む、請求項９の方法。
【請求項１２】
前記第１参照キーを含む前記参照ビデオを表す参照サブフィンガープリントが所定の割合を超えたことに応じて、前記逆引きインデックステーブルが、第１参照キーと関係付けて第１レベルブラックリスト識別子コードを格納する、請求項９の方法。
【請求項１３】
前記第１参照キーを含む前記参照ビデオを表す参照サブフィンガープリントが所定数を超えたことに応じて、前記逆引きインデックステーブルが、第１参照キーと関係付けて第２レベルブラックリスト識別子コードを格納する、請求項９の方法。
【請求項１４】
前記候補セグメントリストを生成するステップが、
プレミアムコンテンツを有するとしてラベル付けされた前記参照ビデオセットからプレミアム参照ビデオを決定するステップと、
前記プレミアム参照ビデオの決定に基づいて前記候補セグメントリストを生成するステップと
を含む、請求項１の方法。
【請求項１５】
複製ビデオコンテンツを検出するためのコンピュータプログラムを記憶するコンピュータ読取り可能な記憶媒体であって、コンピュータに、
入力ビデオを表す入力フィンガープリントを受け取る手順と、
参照ビデオセットから候補セグメントリストを生成する手順と、ここで、前記候補セグメントリストは、前記参照ビデオセット内の参照ビデオ中の時間的にローカライズされたセグメントを含み、
分類要素を用いて、一致候補セグメントまたは不一致候補セグメントの何れかとして、前記候補セグメントリストからの候補セグメントを分類する手順と、
前記候補セグメントの前記分類に基づいて、前記参照ビデオセットから参照ビデオ中の一致部分を識別する結果を生成する手順と
を実行させるためのコンピュータプログラムを記憶したコンピュータ読取り可能な記憶媒体。
【請求項１６】
前記参照ビデオセットから前記候補セグメントリストを生成する前記手順が、前記コンピュータに、
前記参照ビデオセット内の前記参照ビデオを表す参照フィンガープリントを取得する手順と、
前記入力フィンガープリントと前記参照フィンガープリントとの間の部分一致を識別する手順と、
前記識別した部分一致に基づいて最初の候補参照ビデオセットを決定する手順と
を実行させることを含む、請求項１５のコンピュータ読取り可能な記憶媒体。
【請求項１７】
前記コンピュータプログラムは、前記コンピュータに、
前記入力フィンガープリントに対する入力サブフィンガープリントセットを取得する手順と、ここで、各入力サブフィンガープリントが入力サブフィンガープリントキーのシーケンスを含み、
前記参照ビデオに対する参照サブフィンガープリントセットを取得する手順と、ここで、各参照サブフィンガープリントが参照サブフィンガープリントキーのシーケンスを含み、
前記参照サブフィンガープリントキーと前記入力サブフィンガープリントキーとの一致に基づいて、前記最初の候補参照ビデオセットを決定する手順と
を更に実行させるものである、請求項１６のコンピュータ読取り可能な記憶媒体。
【請求項１８】
前記コンピュータプログラムは、前記コンピュータに、
前記参照ビデオと前記入力ビデオとの間の時間的にローカライズされた一致に基づいて各参照ビデオに対する性能指数を決定する手順と、
前記性能指数に基づいて前記最初の候補参照ビデオセットを決定する手順と
を更に実行させるものである、請求項１６のコンピュータ読取り可能な記憶媒体。
【請求項１９】
前記コンピュータプログラムは、前記コンピュータに、
前記参照ビデオを表す参照サブフィンガープリントを、特徴が最大のものから最小のものまでソート順にソートする手順と、
前記参照サブフィンガープリントの前記ソート順に少なくとも一部基づいて、前記候補セグメントを決定する手順と
を更に実行させるものである、請求項１６のコンピュータ読取り可能な記憶媒体。
【請求項２０】
前記コンピュータプログラムは、前記コンピュータに、
参照ビデオを表す参照サブフィンガープリントの参照キーを、特徴が最大のものから最小のものまでソート順にソートする手順と、
前記参照キーの前記ソート順に少なくとも一部基づいて、前記候補セグメントを決定する手順と
を更に実行させるものである、請求項１６のコンピュータ読取り可能な記憶媒体。
【請求項２１】
前記コンピュータプログラムは、前記コンピュータに、
前記入力ビデオを表す入力ビデオサブフィンガープリントと、参照ビデオを表す参照ビデオサブフィンガープリントとの間の時間的に連続する一致を決定する手順と、
前記時間的に連続する一致に基づいて前記候補セグメントリストを決定する手順と
を更に実行させるものである、請求項１６のコンピュータ読取り可能な記憶媒体。
【請求項２２】
前記候補セグメントを分類する前記手順が、前記コンピュータに、
既知の一致モデルに基づいて、前記参照ビデオと前記候補セグメントとの間の一致品質を示す品質尺度を決定する手順と、
前記品質尺度に基づいて、一致セグメントまたは不一致セグメントとして前記候補セグメントを分類する手順と
を実行させることを含む、請求項１５のコンピュータ読取り可能な記憶媒体。
【請求項２３】
前記コンピュータプログラムは、前記コンピュータに、
前記入力フィンガープリントから値の一部を表す入力キーを受け取る手順と、
前記入力キーと一致するキーを有する前記参照ビデオセットから、参照ビデオ中の時間的にローカライズされたセグメントを識別する一つ以上のサブフィンガープリント識別子を得るために、逆引きインデックステーブルに問い合わせる手順と
を更に実行させるものである、請求項１５のコンピュータ読取り可能な記憶媒体。
【請求項２４】
前記入力キーが入力サブフィンガープリントからの隣接値を含む、請求項２３のコンピュータ読取り可能な記憶媒体。
【請求項２５】
前記入力キーが入力サブフィンガープリントからの非隣接値を含む、請求項２３のコンピュータ読取り可能な記憶媒体。
【請求項２６】
前記第１参照キーを含む前記参照ビデオを表す参照サブフィンガープリントが所定の割合を超えたことに応じて、前記逆引きインデックステーブルが、第１参照キーと関係付けて第１レベルブラックリスト識別子コードを格納する、請求項２３のコンピュータ読取り可能な記憶媒体。
【請求項２７】
前記第１参照キーを含む前記参照ビデオを表す参照サブフィンガープリントが所定数を超えたことに応じて、前記逆引きインデックステーブルが、第１参照キーと関係付けて第２レベルブラックリスト識別子コードを格納する、請求項２３のコンピュータ読取り可能な記憶媒体。
【請求項２８】
前記候補セグメントリストを生成する前記手順が、前記コンピュータに、
プレミアムコンテンツを有するとしてラベル付けされた前記参照ビデオセットからプレミアム参照ビデオを決定する手順と、
前記プレミアム参照ビデオの決定に基づいて前記候補セグメントリストを生成する手順と
を実行させることを含む、請求項１３のコンピュータ読取り可能な記憶媒体。
【請求項２９】
複製ビデオコンテンツを検出するシステムであって、
入力ビデオを受け取る取込みサーバと、
前記入力ビデオを表す入力フィンガープリントを生成するフィンガープリントモジュールと、
参照ビデオセットを表す参照フィンガープリントを格納する参照データベースと、
前記フィンガープリントモジュールおよび前記参照データベースに接続される一致モジュールであって、前記入力フィンガープリントに基づいて、前記参照ビデオセットから候補セグメントリストを生成するための前記一致モジュールは、一致セグメントまたは不一致セグメントとして前記候補セグメントを分類し、前記候補セグメントの前記分類に基づいて、前記参照ビデオセットから参照ビデオの一致部分を識別する結果を生成する、前記一致モジュールと
を備えるシステム。
【請求項３０】
前記参照データベースが、
前記参照フィンガープリントを格納するフィンガープリントリポジトリであって、各参照フィンガープリントは、前記参照ビデオ中の時間的にローカライズされたセグメントを表す参照サブフィンガープリントのシーケンスを含む、フィンガープリントリポジトリと、
前記参照ビデオの識別子と参照キーとの間のマッピングを格納する逆引きインデックステーブルとを
含み、前記参照キーは、前記参照サブフィンガープリントからの値の特定セットを含む、請求項２９のシステム。
【請求項３１】
前記第１参照キーを含む前記参照サブフィンガープリントが所定の割合を超えたことに応じて、前記逆引きインデックステーブルが、第１参照キーと関係付けて第１レベルブラックリスト識別子コードを格納する、請求項３０のシステム。
【請求項３２】
前記第１参照キーを含む前記参照サブフィンガープリントが所定しきい値を超えたことに応じて、前記逆引きインデックステーブルが、第１参照キーと関係付けて第２レベルブラックリスト識別子コードを格納する、請求項３０のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、ビデオ処理に関し、より詳細には、一致しているビデオコンテンツの検出に関する。
【背景技術】
【０００２】
電子ビデオライブラリには数千あるいは数百万のビデオファイルが収納されていることがあるので、これらのライブラリの管理は著しく困難な業務となる。ビデオホスティングサイトには無許可ビデオを識別するメカニズムが必要である。ファイルによっては、ファイル名やユーザーが提供する他の情報で識別できる場合もあるが、この識別情報は、ビデオを確実に識別するには不正確であるし、また不十分なこともある。ビデオコンテンツを識別するのに人手を使う代替アプローチは、費用がかさむばかりか時間を浪費する。
【０００３】
ビデオ共有サイトが直面する別の問題は、そのサイトに同一ビデオコンテンツの多数のコピーが収納されているかもしれないことである。これでは格納空間が無駄になり、ホストにかなりの出費を強いることになる。第３の問題は、ファイル数が多過ぎるので、ユーザーの利便性を考慮しつつ体系化するのが非常に困難なことである。例えば、検索結果が同一または非常に良く似たビデオの多数のコピーとなってしまい、その結果、ユーザーの選択が混乱してしまう。
【０００４】
上記問題の観点から、ビデオを重複ビデオコンテンツと自動的に比較し、一致させるための技法が必要とされている。
【発明の概要】
【０００５】
本システムおよび方法により複製ビデオコンテンツが検出される。一致モジュールが、入力ビデオを表す入力ビデオフィンガープリントを受け取る。一致モジュールは、参照ビデオセットから候補セグメントのリストを生成する。各候補セグメントは、参照ビデオセット内の参照ビデオ中の時間的にローカライズした部分（局所化若しくは部分限定した箇所）を含む。分類手段は、各候補セグメントに適用されてそのセグメントを一致セグメントまたは不一致セグメントとして分類する。次いで、一致したとして分類されたセグメントに基づいて、参照ビデオセットから参照ビデオの一致部分を識別したという結果が生成される。
【０００６】
一実施形態では、候補セグメントは、参照ビデオセット内の参照ビデオを表す参照フィンガープリントを取得し、入力フィンガープリントと参照フィンガープリントとの間の部分一致を識別することにより決定される。次いで、最初の候補の参照ビデオセットを、識別された部分一致に基づいて決定する。最初の候補の参照ビデオを分析して、入力ビデオセグメントと参照ビデオセグメントとの間の時間的に連続する一致を決定する。次いで、候補セグメントを時間的に連続する一致に基づいて選択する。
【０００７】
本明細書で説明する特徴および利点は、全てを包含しているとは限らず、特に、追加される多くの特徴および利点は、図面、明細書、および特許請求の範囲から当該技術に精通する者には明らかであろう。更に、本明細書で使用する言葉は、原則として可読性と説明目的のために選定されており、本発明の主題を描写し、または制限するよう選定したものではないことに留意されたい。
【図面の簡単な説明】
【０００８】
【図１】入力ビデオと参照ビデオセットとの間の一致を検出するシステムの実施形態である。
【０００９】
【図２】参照ビデオを入力ビデオと一致させるための参照データベースの実施形態である。
【００１０】
【図３】一致するビデオコンテンツを検出する処理の実施形態である。
【００１１】
【図４】入力ビデオとの滞在一致に対する候補ビデオセグメントのリストを生成する処理の実施形態である。
【００１２】
【図５】入力ビデオに対して生成されるＬＳＨキーの複製自由リストを説明するテーブルの実施形態である。
【００１３】
【図６】入力ビデオとの部分一致に基づいて参照ビデオに対する性能指数を決定する技法の実施形態を説明する図である。
【００１４】
【図７】入力ビデオのサブフィンガープリントを順位付ける技法の実施形態を説明する図である。
【００１５】
【図８】ビデオのサブフィンガープリント内のＬＳＨキーを順位付ける技法の実施形態を説明する図である。
【００１６】
【図９】順位付けた入力ビデオのサブフィンガープリントセットに対するＬＳＨルックアップ技法の実施形態を説明する図である。
【００１７】
【図１０】一致を決定するための、入力ビデオのサブフィンガープリントと参照ビデオのサブフィンガープリントとの間のマッピングの実施形態を説明する図である。
【００１８】
【図１１】一致または不一致セグメントとして参照ビデオセグメントを分類する処理の実施形態である。
【００１９】
【図１２】入力ビデオの時間的にローカライズしたブロックと時間にわたる参照ビデオとを一致させる技法の実施形態である。
【発明を実施するための形態】
【００２０】
図は、本発明の各種実施形態を説明するために図示しているに過ぎない。当該技術に精通する者であれば、本明細書で説明する構造および方法の代替の実施形態を、本明細書で説明する発明の原理から逸脱することなく利用できることは、以下の説明から直ちに理解できよう。
【００２１】
入力メディアファイル（例えば、ビデオ、オーディオまたはその両方）が参照メディアファイルセット（例えば、ビデオおよび／またはオーディオクリップのデータベース）内の参照メディアファイルと一致するかどうか、または部分一致するかどうかを判定するシステムおよび方法について説明する。一致検出処理は、一メディアファイル（例えば、２０秒のクリップ）の一部同士の一致を、そのメディアファイルが同一の開始および終了ポイントを持っていなくても、あるいは一致部分の前後のコンテンツが異なる場合でも、検出することができる。更に、低品質のコード変換で生じる標準的な劣化に十分耐えるだけのロバスト性を有するとともに、ある程度の時間尺度の改変（例えば、ビデオを高速または低速で再生）に対するロバスト性を有する。この処理は、「正常検出(True Positive)」（一つ以上の一致メディアファイルがデータベース内にある）と、「正常非検出(True Negative)」（データベース内に対応する一致がない）の両方を正確に分類することができる。時には、この処理は、厳しい時間的制約がある状況（アップロードトラフィックレートを扱うため）、および／または限られたメモリ量を用いる状況でも一致を検出できる。
【００２２】
時間ベースメディア間の一致を検出するシステムの実施形態を図１に示す。ビデオコンテンツ一致の文脈で特定の実施例について説明するが、説明するシステムおよび方法は、オーディオ、画像等の他の種類のメディアコンテンツの一致に使用できるという点に留意されたい。取込みサーバ１０４は、ビデオソースから入力ビデオ１０２を受け取る。ビデオソースは、例えば、ネットワークを通じて取込みサーバ１０４と通信するクライアントコンピュータとすることができる。代替として、ビデオソースは、取込みサーバ１０４に接続して通信するデータベースまたは他の格納装置とすることもできる。例えば、ビデオソースは、ＤＶＤ、ＣＤ−ＲＯＭ、デジタルビデオレコーダ（ＤＶＲ）、ハードディスク、フラッシュメモリ、または他のメモリ等の、ビデオ格納メディアとすることができる。取込みサーバ１０４は、ビデオカメラ等のビデオキャプチャシステムと接続して通信し、ライブビデオコンテンツを受信することもできる。
【００２３】
フィンガープリントモジュール１０６は、取込みサーバ１０４から入力ビデオ１０２を受け取り、入力ビデオ１０２を表す「フィンガープリント」を生成する。フィンガープリントは、例えば、幾つかまたは全てのビデオファイルの空間、時間、および／または構造の特性をコンパクトなフォーマットで表すビットベクトルである。フィンガープリントは、圧縮、復元、ノイズ、フレームレート、開始および停止時間、ソース解像度等によるわずかな変化がフィンガープリントに著しく影響しないような映像コンテンツに基づいて、ビデオを識別する。
【００２４】
一実施形態では、フィンガープリントモジュール１０６は、受け取ったビデオを多数のオーバーラップしたセグメントに分割し、各セグメントに対してサブフィンガープリントが生成される。セグメントは、長さを０．５〜５．０秒とすることが好ましいが、他の長さのセグメントを使用してもよい。従って、各サブフィンガープリントは、時間的にローカライズ（局所化若しくは部分限定）したメディアのセグメントを表す（例えば、ビデオの４秒またはオーディオの１．５秒）。セグメントの開始時間は、固定頻度で離間させる（例えば、ビデオでは０．２５秒毎に１回、またはオーディオでは０．１０秒毎に１回）のが典型的である。例えば、第１サブフィンガープリントが、ビデオの０〜４秒のセグメント上で計算され、第２サブフィンガープリントが、０．２５〜４.２５秒のセグメント上で計算され、第３サブフィンガープリントが、０．５０〜４．５０秒のセグメントに対して計算される等である。各サブフィンガープリントは、そのサブフィンガープリントにより表されるビデオの特定のセグメントを識別するサブフィンガープリント識別子コードにより参照される。例えば、サブフィンガープリント識別子コードには、（ビデオ、オフセット）の対を含めることができる。識別子の「ビデオ」部分は、参照ビデオデータベース内のビデオを一意に識別する（例えば、３２ビット識別子を用いる）。識別子の「オフセット」部分は、ビデオの特定のセグメント（または対応するサブフィンガープリント）を、例えば、セグメントの開始時間を参照するオフセットインデックスにより識別する。例えば、セグメントの開始時間が０．２５秒だけ離れている場合、０秒で開始するセグメントは、オフセットインデックス０を有し、０．２５秒で開始するセグメントは、オフセットインデックス１を有し、０．５０秒で開始するセグメントは、オフセットインデックス２を有する等としてもよい。セグメントは開始時間により直接識別することもできる。完全に順位付けされたサブフィンガープリントのシーケンスは、そのビデオ全体のフィンガープリントを提供する。
【００２５】
一実施形態では、各サブフィンガープリントは、ベクトル値を含み、各値は、限られたサイズのアルファベットによる非順序値をとる（例えば、ベクトルの次元毎に単一バイトへコード化されるが順序は持たない２５６サイズのアルファベット）。例えば、エントロピー符号化を用いて、値の確率分布に基づいて各値を符号化してもよい。サブフィンガープリントをとる空間に対して、ハミング距離計測を適切な距離計測により置換することにより、距離空間への拡張が行われる。非一様にサンプリングされる（フィンガープリントされる）シーケンスへの一般化は、当該技術に精通する者には周知のことであろう。簡明にするために、本説明は一様なサンプリングを仮定し、比較のためにハミング計測を用いた非順序アルファベットを仮定している。
【００２６】
一致モジュール１０８は、入力ビデオ１０２のフィンガープリントを、参照ビデオのセットを表す参照フィンガープリントのいくつかのセットと比較する。参照フィンガープリントは、利用可能な全ての参照ビデオまたはそのサブセットに対してでもよい。場合によって、フィンガープリントは、フィンガープリントの基になる最初の参照ビデオが提供されずに、フィンガープリントソースから提供される。一致モジュール１０８は、入力ビデオ１０２の少なくとも一部と一致する一つ以上の参照ビデオ（または、参照ビデオの一部）を識別する一致結果１１２を出力する。一致を判定する方法について図３を参照して更に詳述する。
【００２７】
参照データベース１２０には、一つ以上のフィンガープリントリポジトリ１２２、および一つ以上の逆引きインデックステーブル１２４が含まれる。フィンガープリントリポジトリ１２２は、参照ビデオのフィンガープリントを格納する。参照フィンガープリントセット内の各サブフィンガープリントは、特定のビデオを識別するサブフィンガープリント識別子により識別され、そのサブフィンガープリントにより表されるビデオセグメントと対応するビデオ内にオフセットされる。オフセットは、セグメントの開始時間値に対する時間オフセット、またはセグメントのシーケンス内の位置を示すインデックス番号とすることができる。
【００２８】
一実施形態では、幾つかの参照ビデオに対するフィンガープリントは、フィンガープリントリポジトリ１２２内で、参照ビデオが「プレミアムコンテンツ」を含むという指示等の、追加メタデータによりマークされてもよい。「プレミアムコンテンツ」としてマークされたビデオは、保護レベルを上げる価値があるビデオであり、後述するように一致処理の間に特別な考慮が払われる。プレミアムコンテンツの指定は、幾つかの異なる因子により決定できる。一実施形態では、どのコンテンツをプレミアムコンテンツとして指定するかはコンテンツ所有者が決定する。例えば、メディア企業は、彼らが所有するビデオの中からある数の「トップ」ビデオを最も関心があるビデオとして選定してもよい。別の実施形態では、プレミアムコンテンツの指定を以前の一致履歴に基づいて決定することができる。例えば、それ以降アップロードされた入力ビデオと一致するコンテンツを有すると以前に決定されたことがある参照ビデオを、プレミアムコンテンツとして自動的に指定してもよい。別の実施形態では、参照ビデオが参照リポジトリ内にあった時間の長さに基づいて、プレミアムコンテンツを指定する。例えば、データベース内にある最初の一ヶ月間だけ、参照をプレミアムとして取り扱うことができ、その後、プレミアムコンテンツの指定をオプションで削除することができる。更に、プレミアムコンテンツの指定をマルチレベルとすることができる。例えば、様々な分析レベルと対応させて、様々なプレミアムコンテンツのレベルを指定することができる。
【００２９】
一実施形態では、参照ビデオのメディアトラック（例えば、オーディオまたはビデオ）毎に別々のフィンガープリントを生成させる。更に、実施形態によっては、メディアトラック毎に多数のフィンガープリントを生成してもよい。例えば、フィンガープリント生成処理が左右ミラーリングを受けやすい場合、ビデオトラック毎に二つのフィンガープリントシーケンスを生成するよう処理を選択してもよい（フィンガープリント処理する前にビデオフレーム内で左／右反転があった場合、第２の方はミラーリングされたフレーム上でフィンガープリント処理を実行する）。トラック（および適用される変換の種類）毎に生成されるフィンガープリントの数は、参照ビデオと関係するメタデータに依存させてもよく、参照ビデオが「プレミアムコンテンツ」としてマークされているかどうかに依存させてもよい。別の実施形態では、ビデオが、様々なチャンネルと対応する多数のオーディオトラックを持っていてもよく、その場合、各オーディオトラックがフィンガープリントを持っていてもよく、または代替として、選択されたオーディオトラックだけが（例えば、ステレオの左と右）フィンガープリントを持っていてもよい。
【００３０】
単一トラックに対して多数のフィンガープリントが生成される場合、そのサブフィンガープリントは、同一のサブフィンガープリント識別子コードに基づいて、メディア種類（例えば、オーディオまたはビデオ）に対する識別子コードおよび多数のフィンガープリント間を明確に区別する区別サブコードと併せて、フィンガープリントリポジトリ１２２に追加される。以下の説明を簡単にするために、トラック種類（例えば、オーディオとビデオ）毎のフィンガープリントが別々のフィンガープリントリポジトリ１２２内に格納されると仮定する。また、簡単にするために、説明する実施例のケースでは、各参照ビデオは単一ビデオトラックと単一オーディオトラックを有し、トラック毎に単一のフィンガープリントを有すると仮定する。
【００３１】
一実施形態では、フィンガープリントリポジトリ１２２のコンテンツに基づいて逆引きインデックステーブル１２４を作成する。リポジトリ１２２が周期的に更新される場合（例えば、ユーザーが新規ビデオをアップロードするとき）、逆引きインデックステーブル１２４は、スケジュール化した間隔で、またはリポジトリコンテンツが変わるたびに更新してもよい。逆引きインデックステーブル１２４では、サブフィンガープリント値（または、「サブフィンガープリントキー」）のサブセットが、リポジトリテーブル１２２内の参照サブフィンガープリントを識別する手段を提供する。各サブフィンガープリントキーは、そのサブフィンガープリントキーを含む参照サブフィンガープリントセットと関係付けて格納される。この逆引きインデックス１２４は、近似最近傍機能性を提供する構造を持っている。
【００３２】
場所依存ハッシュ（location-sensitive hashing：ＬＳＨ）を用いる参照フィンガープリントリポジトリ１２２および逆引きインデックステーブル１２４の実施例について、図２で説明する。参照サブフィンガープリントセットは、参照リポジトリ１２２内の参照ビデオと対応する。各サブフィンガープリントは、ビデオセグメントと関係付けられ、記法Ｘ＠（Ｙ）を用いて識別される。ここで、Ｘはビデオの識別子であり、ＹはビデオＸのセグメントを識別するオフセットインデックスである。サブフィンガープリントセット（Ｘ＠（Ｙ1）．．．Ｘ＠（Ｙn））はビデオＸに対するフィンガープリントを形成する。例えば、図２で、参照ビデオＡに対するフィンガープリントは、サブフィンガープリントＡ＠（０）、Ａ＠（１）．．．等を含む。各サブフィンガープリントは、参照ビデオＡのセグメントと対応し、そのセグメントはオフセットインデックスにより識別される。例えば、Ａ＠（０）は、オフセットインデックス０でのビデオＡのセグメントを表すサブフィンガープリントを識別し、Ａ＠（１）は、オフセットインデックス１でのビデオＡのセグメントを表すサブフィンガープリントを識別する等である。
【００３３】
各サブフィンガープリントは値（各値は、例えばバイトでもよい）のシーケンスを含む。値のシーケンスはＬＳＨバンドの数に分割され、各バンドはサブフィンガープリント内の値のサブセットと対応している。例えば、ＬＳＨバンド０はサブフィンガープリントの最初の４つの値を含み、ＬＳＨバンド１はサブフィンガープリントの次の４つの値を含む等である。一実施形態では、サブフィンガープリントは２５のＬＳＨバンドを含み、それぞれ４バイト値を含む。サブフィンガープリントのＬＳＨバンド内の値のセットは、上記のように、そのサブフィンガープリントに対するＬＳＨバンドキーと対応し、キーを含むサブフィンガープリント識別子と関係付けて逆引きインデックステーブル１２４内に格納される。本明細書では、各サブフィンガープリントバンドキーを「ＬＳＨキー」とも称する。
【００３４】
例えば、サブフィンガープリントＡ＠（０）は、ＬＳＨバンド０内の値（６５、２２、Ａ５、Ｂ１）を持つ。この値セットは、逆引きインデックスＬＳＨテーブル１２４内で、ＬＳＨキー（６５  ２２  Ａ５  Ｂ１  ＋０）により表される。この記法では、＋０はキーがＬＳＨバンド０内にあることを示している。ＬＳＨテーブル１２４は、各ＬＳＨキーを、そのＬＳＨキーを含むリポジトリ１２２内の各サブフィンガープリントにマッピングする。例えば、表は、ＬＳＨキー２３４３４４Ｄ２＋１と関係付けてサブフィンガープリントＡ＠（０）およびＢ＠（０）に対する識別子を格納する。それぞれのサブフィンガープリントがＬＳＨバンド１内に値（２３  ４３  ４４  Ｄ２）を含むからである。注意すべきは、値（１１  ３４  ５５  ５６）が、サブフィンガープリントＢ＠（０）のバンド２、およびサブフィンガープリントＢ＠（１）のバンド１内に現れるという点である。但し、値のシーケンスが、異なるＬＳＨバンド内にあるので、これらは異なるＬＳＨキーと見なされて、逆引きインデックステーブル１２４内では別々にインデックスされる。
【００３５】
代替の実施形態では、ＬＳＨバンドは、説明したように、連続値というより離散した（隣接していない）値のサブセットを含む。ＬＳＨバンドへの値のグループ化は、特定アプリケーションの制約に依存する。別の代替の手法は、完全なサブフィンガープリントから導かれるＬＳＨキーを用いる。例えば、サブフィンガープリントに対するＬＳＨキーは、ランダムではあるがメモリに格納されている分割面（random-but-memorized dividing planes）上への多数の投影からの符号ビットコード、またはサブフィンガープリントの短いシーケンスからの符号ビットコード、または短いサポートウィンドウ内部のサブフィンガープリント入力値の頻度ヒストグラム等の符号ビットコードを計算することにより決定できる。頻度ヒストグラム手法は、キーとして固定ビン頻度カウントを用いることができ、あるいはキーとしてその時間間隔内で最も頻度が高い署名値の値を用いることができる。
【００３６】
他の代替の実施形態では、最近傍機能性は、距離空間としてサブフィンガープリントベクトルで計測されたハミング距離を用いて、例えば、スピルツリー（spill tree）とＭツリー（M tree）等のＬＳＨと異なる技法を用いて提供される。以下の説明では、近似最近傍機能性がその特定データ構造により提供されるという要件はないが、逆引きインデックスをＬＳＨテーブルと称する。
【００３７】
この実施形態では、一致処理で使用されるメモリ量および計算量を制御するために、逆引きインデックステーブル１２４を共通ＬＳＨキーに対して選択的に修正する。特に、このテーブルは、サブフィンガープリント間を弁別するのに有用な縮小尤度（reduced likelihood）を有するＬＳＨキーをマークする構造となっている。この状態は、参照フィンガープリント内部の各ＬＳＨキーの頻度および／または分布についての各種の試験により決定される。
【００３８】
最初の試験はＬＳＨキーの発生頻度に基づく。全参照ビデオの内の予め定義された割合の数を超える参照ビデオが所与のＬＳＨキーを含む場合、そのＬＳＨキーを「第１レベルブラックリスト」キーとしてＬＳＨテーブル１２４内で識別し、そのキーを含むサブフィンガープリント識別子をテーブル１２４から削除する。代わりに、第１レベルブラックリストのキーを示す特別な識別子コードをそのキーと関係付けて、逆引きインデックステーブル１２４内に格納する。例えば、一実施形態では、参照ビデオの５％超がキー（００  ００  ００  ＯＡ＋１）を含む場合、そのキーを、逆引きインデックステーブル１２４内で第１レベルブラックリストキーとして識別し（「ＢＬ１」等の特別な識別子コードをキーと関係付けて格納することによる）、どのサブフィンガープリント識別子もそのキーと関係付けて格納しない。
【００３９】
第１レベルブラックリストの基準を満たしていないが、所与のＬＳＨキーを含むサブフィンガープリントの合計数がまだしきい値を超えている場合、そのＬＳＨキーを逆引きインデックステーブル１２４内で「第２レベルブラックリスト」キーとしてマークし区別する。例えば、１０，０００を超える参照サブフィンガープリントがキー（００  ００  ００  ＯＢ＋２）を含むが、これら１０，０００の参照サブフィンガープリントが全て参照ビデオの１％以内にしか含まれない場合、「第２レベルブラックリスト」を示す特別な識別子がキーと関係付けられて格納される。一実施形態では、第２レベルブラックリストキーを含むサブフィンガープリント識別子の全リストは格納されない。代わりに、ＬＳＨテーブル１２４は、ビデオ識別子のリストだけを格納するが、オフセットインデックスは格納しない（すなわち、特定のセグメントを識別しない）。更に、テーブルには、一致キーを含む各ビデオ内のサブフィンガープリントのカウント数を格納してもよい。例えば、テーブル１２４内で、キー（００  ００  ００  ＯＢ＋２）が第２レベルブラックリストキーとして識別され、「ＢＬ２」等の特別な識別子コードがキーと関係付けられて格納される。ビデオ「Ｇ」に対するフィンガープリントが、一致キー（００  ００  ００  ＯＢ＋２）を含む２６の異なるサブフィンガープリントを有することを示すコード（Ｇ、６）も、そのキーと関係付けられて格納される。一致キーを含むサブフィンガープリントに対する個々のサブフィンガープリント識別子は、個々に格納されない。
【００４０】
ブラックリストを作成せずに追加のＬＳＨテーブルを用いて、プレミアムコンテンツとしてマークされる参照ビデオに対する追加のインデックス化を提供してもよい。これらのテーブルは、主ＬＳＨテーブル内の幾つかのレベルでブラックリスト化されているこれらのＬＳＨキーしか含まず、また、プレミアムコンテンツとしてマークされた参照ビデオしか含まない。更に、これらのテーブルは、ブラックリスト化により逆引きインデックスから完全に無くなってしまうことになる参照ビデオセグメントへのスパースインデックスを含むこともある。一実施形態では、スパースインデックスは、全ての参照ビデオが、重要な時間間隔（例えば、２０秒以下の間隔）あたり少なくとも一回の非ブラックリスト化された逆引きインデックスエントリがあることを保証する。これらのテーブルからのエントリが、あたかもＬＳＨテーブルの主セットから来ているかのように、後述の一致処理に追加される。
フィンガープリント一致
【００４１】
一致処理のために入力ビデオ１０２を受け取ると（例えば、アップロードコンテンツまたは既存のビデオデータベースから）、入力ビデオ１０２は、参照ビデオに適用されるのと同一の処理に従ってフィンガープリント処理される。次いで、一致モジュール１０８は、入力ビデオ１０２のどの部分が（もしあれば）、参照データベース１２０内の参照ビデオの一部に対して一致するかを判定する。一実施形態では、一致モジュール１０８は、図３に示すように、３つのステージの処理に従って一致を判定する。ステージ１では、一致モジュール１０８は、入力ビデオ１０２に対する一致候補の候補リストを参照セットから生成する（３０２）。候補リスト内の各エントリは：（１）候補と一致する可能性がある入力ビデオの部分；（２）候補の参照一致に対するビデオ識別子；および（３）入力ビデオと一致する可能性がある参照ビデオの部分、を示す。例えば、候補リストには、下記の表に示される項目のような結果を含めることができる。
【表１】
2010537585.tif 000003
【００４２】
第２ステージでは、候補リスト内の各候補エントリを、更に評価して（３０４）、一致が正しいか、間違っているかを示すローカルの分類を提供する。この判定は、候補リスト内に示される一致部分内部からの証拠に基づく。
【００４３】
第３ステージでは、残りの一致候補を結合し、不要部分を削除して、時間全体、およびオプションのチャンネル（例えば、オーディオとビデオ）全体で一致を決定して（３０６）、最終的な結果セットを提供する。三つのステージの一致処理の各ステージについて詳述する。
【００４４】
一実施形態では、入力ビデオ１０２が長い場合（例えば、３０分超）、オプションで入力ビデオを事前処理して、入力ビデオを管理できるサイズの「チャプタ」（例えば、３２分）に分割する。チャプタの開始時間と終了時間は、チャプタ間に任意の短いオーバーラップ量（例えば、終了毎に２分）が存在するように定義するのが典型的である。後処理ステップで、最終的な出力結果は互いに「縫って」戻される。例示を簡単にするために、以下の説明では、入力ビデオが管理可能な時間（例えば、３０〜３２分未満）から成っていると仮定している。
ステージ１：候補リスト生成
【００４５】
このステージは、一層考察を深めるために、参照セットから参照セグメントの短いリストを作成する。このステップは、計算量とメモリ使用量を管理する際に有用であり、一致処理を合計データベースサイズから切り離す方法を提供するが、その代わり、真一致のエントリの最大予測数（例えば、３０〜６０エントリ）と同じ速さ以上にはならない。図４でステージ１の例示の処理を説明する。
【００４６】
第１ステップは、入力ビデオ１０２を表す入力サブフィンガープリントの全シーケンス内の随所にあるＬＳＨキーのリストと、逆引きインデックステーブル１２４内のこれらのキーにマッピングされる対応の参照サブフィンガープリント識別子とを決定する（４０２）。このステップ４０２の例示実施形態を図５で説明する。入力ビデオのサブフィンガープリント５０２はそれぞれ、２５のＬＳＨバンドに分割され、各バンドは４バイト値のキーを含む。一実施形態では、同一のＬＳＨバンド内部の複製キーは、説明したように削除される。注意すべきは、異なるＬＳＨバンド内のキーは、それらのキーが同じ値を含んでいたとしても複製であるとは見なされない、という点である。次いで、入力ビデオサブフィンガープリントセット内の一意のＬＳＨキーそれぞれに対応する参照サブフィンガープリント識別子を、ＬＳＨテーブル１２４から取り出す。このステップの出力は、ＬＳＨキーの複製自由リスト５０４と、ＬＳＨテーブル１２４内でＬＳＨキーへマッピングされる各参照サブフィンガープリント識別子とである。ここで、記法Ｚ＠（Ｘ1, Ｘ2, Ｘ3 ．．．Ｘn）の意味は、そのキーが時間オフセットインデックスＸ1, Ｘ2, Ｘ3 ．．．ＸnでビデオＺにあるということである。何れかのキーが第１レベルブラックリストまたは第２レベルブラックリストをもたらす場合、複製自由リスト５０４内にこれを注記する。
【００４７】
次に、考察を続けるために最初の候補ビデオのリストを決定する（４０４）。一実施形態では、既述の複製自由リスト５０４内のサブフィンガープリントの全般的な時間配置を計画し、ビデオの各部分と関係付けられるＬＳＨキーのカウント数を維持することにより、最初の候補ビデオのリストを作成する。次に、参照ビデオサブフィンガープリントキーと、入力ビデオサブフィンガープリントキーとの間の一致頻度を、各参照ビデオの異なる時間ウィンドウの時間経過中に記録できるように、各参照ビデオに対して時間依存一致カウントを作成できる。例として、図６に参照ビデオＤのヒストグラムを示す（もちろん、実際には時間依存一致カウントはメモリ内に格納されるに過ぎず、表示しなくてもよいし、何らかの別の方法で提示しなくてもよい）。説明した実施例では、一致カウント機能は粗く定量化されている（例えば、分解能５秒）。従って、一致カウント機能は、参照ビデオの５秒毎のウィンドウ内に発生する参照ビデオと入力ビデオとの間の一致キーカウント数を維持する。例えば、０〜５秒間の時間ウィンドウ内に、入力ビデオからのキーからなる複製自由リスト５０４内のキーと一致する参照ビデオＤからのサブフィンガープリントキーの５例がある。参照ビデオの５〜１０秒間の時間ウィンドウ内に３つの一致例があり、１０〜１５秒間の時間ウィンドウ内に一例があり、等々である。
【００４８】
次いで、一致カウント数に基づいて参照ビデオ毎に性能指数を求める。次に、プロセスは、この性能指数順のリストの上位から幾つかのビデオを選択して、将来の処理で検討するものだけとする。一実施形態では、性能指数は、入力ビデオの長さ全体の一致カウント数を合計することにより得られ、開始と終了ポイントは性能指数を最大化するよう選択する。例えば、参照ビデオＤでは、一致の合計数は、０〜４５秒間の入力ビデオの長さ全体（４５秒）で合計して性能指数１５を得る。これは一致分布と入力ビデオの長さとの畳み込み積分、それに続く最大値選択：
【数１】
2010537585.tif 000004
として実装することができ、ここで、Ｌは入力ビデオの長さ（例えば４５秒）、ｈ（ｔ）は全体時間での一致カウントである。代替として、性能指数に寄与する前に、参照ビデオの各分割した（quantized）ウィンドウ（例えば、５秒のウィンドウ）が少なくとも幾つかの一致しきい値を持つのを保証し、少なくとも複数のセクション（例えば、３つの５分間のセクション）が非ゼロの寄与をするよう計算を修正する。別の実施形態では、各参照ビデオの第２レベルブラックリストに対する発生率もカウントする。第２レベルブラックリストを持つこれら参照の、削除されたオフセット識別子のカウント数は、非ブラックリスト化され、スキャンされたＬＳＨリスト内に発生するインデックス範囲全体にわたって一様に拡散しているとみることができる。これは実質的に、これらエントリに対するしきい値を下げて、非ゼロの寄与を提供できるようになるであろう。更に別の実施形態では、プレミアムコンテンツを含むとしてマークされている参照ビデオに何らかの追加の優先権が与えられる。例えば、
これらのエントリを最初の候補ビデオリストに加えるためのしきい値を下げることができる（プレミアムとしての指定に基づいて）。
【００４９】
最初の候補ビデオのリストを作成する際の別の代替の手法は、以前に検査されたチャンネル（例えば、別のオーディオトラック）で一致したことを既に観察されている参照に、追加の優先権を与えることである。例えば、プロセスが、入力メディアファイルに対するオーディオチャンネル一致ステップを通るパスを既に完了して、今はビデオチャンネルを検査している場合、そのプロセスは、同一の参照をビデオチャンネル候補リストへ容易に加えることができる。オーディオとビデオチャンネルは対になることが多い（または、一方の小さなグループから少なくとも選択される）ので、オーディオチャンネルが所与の参照と一致するという仮定に合理性がある場合、ビデオチャンネルも一致するという可能性を一層緊密に検査するようプロセスを構成することができる。このチャンネルをまたぐ強化策のために使用される論理は、一致プロセスの制約に依存する。制約があまり厳しくない場合、別のチャンネルで一致した全ての参照を、最初の候補ビデオリストに加えるだけとすることができる。制約によりその簡単な手法が不可能な場合、以前の一致を用いて、最初の候補ビデオリストを作成する際に使用されるしきい値を下げることができる。以前に一致したエントリの全期間にわたってこれらのしきい値を下げることができ、または現在のトラックの同期部分だけ下げることができる。
【００５０】
後続する全ての処理は、最初の候補の参照ビデオリストの一部となる参照ビデオを検討するだけである。次に、入力ビデオを時間的にローカライズしたブロックに分割する（４０６）。一実施形態では、ブロックの長さは、検出しなければならない最短予測の真一致の長さの半分である。例えば、２０秒の長さの短い一致を検出するには、１０秒以下のブロックとすることになる。これらのブロックは、オーバーラップのない１０秒ブロックに入力ビデオを任意に切断して、またはオーバーラップさせた１０秒ブロックに入力ビデオを切断して形成することができる（例えば、入力ビデオの全長にわたって１０秒ウィンドウをスライドさせることによる）。代替として、ブロックは、ビデオまたはオーディオ分析を用いて決定された境界から形成することができる（例えば、カット境界、または分析ベースの境界が広く拡散しすぎている場合に均一な間隔をもつ境界で埋まっている動きの早い境界）。説明を簡単にするために、提示の実施例は、任意に切断されたオーバーラップのない１０秒ブロックを用いている。
【００５１】
上記の決定された最初の候補ビデオリストを検討するだけという制約は、最初の候補ビデオリストを持つ最初の候補ビデオ（例えば、上記の予め選択した処理からのビデオ）のマップ（例えば、ハッシュマップ）を予め常駐させ、他の参照ビデオをそのマップへ更に追加するのを許可しないことにより、実装できる。
【００５２】
入力ビデオの各ブロックは、下記のように別々に処理する。一実施形態では、入力ビデオの現在処理しているブロックのサブフィンガープリントをソートして、どのサブフィンガープリントを最初に処理するかを決定する。一実施形態では、現在のブロック内のサブフィンガープリントのリストの特徴が最大のものから最小のものまで順位付ける（４０８）ように、サブフィンガープリントをソートする。この実施形態では、各入力ビデオサブフィンガープリントと一致するキーを有する最初の候補ビデオリストから参照サブフィンガープリントの合計数がカウントされる。一致が最小のサブフィンガープリントが最初にリストアップされる。例えば、図７は、現在処理されている入力ビデオブロックからの一セットのサブフィンガープリントを示す。一致の数を各入力サブフィンガープリント内のＬＳＨキー毎に示す。例えば、ＬＳＨキー１Ｃ８６５００２＋０は、最初の候補ビデオリスト内のビデオから参照サブフィンガープリントとの一致を４つ有する。一致数を入力サブフィンガープリント毎に合計する。その合計を用いて、最小の一致（特徴最大）から最大の一致（特徴最小）まで入力サブフィンガープリントを順位付ける。
【００５３】
入力サブフィンガープリント内の一つ以上のＬＳＨキーが第２レベルブラックリストとされた場合、サブフィンガープリントに対する一致候補の合計数（ＬＳＨキーリスト内のビデオ全体で合計、または代替として、候補ビデオ全体で合計）をサブフィンガープリントのその部分に対して使用する。サブフィンガープリント内の一つ以上のＬＳＨキーが第１レベルブラックリストとされた場合、入力サブフィンガープリントが関係している候補の参照サブフィンガープリントの数に対して、何らかの大きな値を使用する（例えば、１００×第２レベルブラックリストのしきい値）。
【００５４】
入力ビデオのサブフィンガープリントセットを現在のブロックに対して順位付けると、そのサブフィンガープリントは、特徴最大のサブフィンガープリント（最小一致）で開始されるよう処理される。各サブフィンガープリントの処理は、最初の候補ビデオをマップの上位に予め常駐させる場合を除いて、空の候補マップから開始される。各サブフィンガープリント内では、サブフィンガープリント順位付けに対して行われた上記のことと同じように、ＬＳＨキーも、特徴最大〜最小の並びで順位付けられる（４１０）。例えば、図８に示すように、参照サブフィンガープリント候補との一致数は、サブフィンガープリント内の各ＬＳＨキーに対して決定される。次に、最小一致（特徴最大）を有するキーで開始される順位でキーが処理される。ＬＳＨキーのこの順位を用いて、プロセスは第１ＬＳＨキーで開始され、一致キーを有する参照サブフィンガープリント候補を候補マップへ追加する。例えば、図９に示すように、順位付けした入力ビデオサブフィンガープリントにＬＳＨルックアップを実行する（各サブフィンガープリント内のＬＳＨキーの順位で）。各ルックアップが実行されると、得られたサブフィンガープリント識別子が格納される。一実施形態では、候補（参照サブフィンガープリントと対応する）は、以下の制約に従って候補マップに追加される。
【００５５】
（１）候補は、最初の候補ビデオリストからである。このチェックは、マップを予め常駐させる上記のステップにより明示的に行われる。予め常駐するマップ内にビデオ識別子がある場合、そのビデオ識別子は最初の候補リスト内にあり、プロセスを進めることができる。その場所がマップ内にない場合、候補一致は記録されない。
【００５６】
（２）マップ内の異なる候補の数は、所定のしきい値を超えない。候補数がそのしきい値に達すると、後続のＬＳＨキーは、候補を存在させるための支持を増加させることができるが、新規候補を追加することはできない。繰り返しになるが、プレミアムコンテンツの候補については例外とすることができる。
【００５７】
（３）少なくとも（ｔ−１）の残っている（このサブフィンガープリントからは見えない）許容されるべき新規候補に対するＬＳＨブロックがあり、ここで、ｔはＬＳＨサブフィンガープリントしきい値である（後述）。この残っているＬＳＨブロックカウントは、第２レベルブラックリストとされたＬＳＨブロックを含むが、第１レベルブラックリストのブロックは含まない。
【００５８】
（４）第２レベルブラックリストとされたＬＳＨブロックは、最後に検討され、ビデオ毎にシーン（seen）発生カウントを作成するが、候補ビデオ毎にブラックリスト化されたブロック全体の合計を作成する。
【００５９】
得られる候補マップは、最初の候補ビデオリストからの参照サブフィンガープリント識別子と、現在の入力サブフィンガープリントに一致するオフセットとからなる限定リストを有する。次のステップは、入力ビデオのサブフィンガープリント全体の候補を組み合せて、どの参照とオフセット候補とが入力サブフィンガープリントにより支持されるかを決定する。入力ビデオのサブフィンガープリントと参照サブフィンガープリントの候補との間の一致はそれぞれ、入力ビデオと参照ビデオとの間の一致の特定開始位置を「投票して決める」。開始位置は、入力ビデオへのオフセットを参照ビデオ内の一致位置から減じることにより決定する。例えば、図１０に示すように、オフセット（２）での入力ビデオサブフィンガープリントは、参照サブフィンガープリントＤ＠（３）と一致する。これは開始位置Ｄ＠（２）に対する「投票」を生成する。同様に、入力ビデオのオフセット（３）でのサブフィンガープリントは、参照サブフィンガープリントＤ＠（４）と一致する。この一致も開始位置Ｄ＠（２）に対する投票である。一般に、入力ビデオ内のオフセットＸでのサブフィンガープリントが参照ビデオ内のオフセットＹと一致する場合、これにより、入力ビデオの開始が、Ｙ−Ｘ＋１とした参照ビデオの位置と一致するという推定が支持される。投票は、参照ビデオ毎にサブフィンガープリント全体にわたって蓄積される。この結果は実質的に、単位傾斜線（unit-slope line）に対するハフ変換であり、入力ビデオと参照が一致する可能性のあるタイミングが得られる。
【００６０】
投票は、入力ビデオ内のサブフィンガープリント毎に、同様に処理される。一実施形態では、開始位置に対して少なくともｔの投票を有する参照オフセットは、現在の入力ビデオブロックに対する候補支持を保持する新規候補マップに転送される。このしきい値は、プレミアムコンテンツに対しては選択的に低下させることができる。例えば、プレミアムコンテンツに関わる候補は、非プレミアムコンテンツより低い支持レベルであるとしても、新規の候補マップへ転送できる。このしきい値は、ｔ以上の投票の支持を有する参照候補を余りに多く生成した入力サブフィンガープリントに対しては、より高くなる。各入力サブフィンガープリントに関して、合格するそのサブフィンガープリントからの候補数が所定数未満となるまで、しきい値が上方に調整される。例えば、一実施形態では、４００，０００対の候補が、入力ビデオの１０秒毎に一意に一致する参照または開始オフセットに対応する各候補対により許容される。但し、使用される特定の最大候補数は、本システムの計算の制約とタイミングの制約に大きく依存する。合格する候補は、それらに対する支持を以前の支持に加える（現在の入力ビデオブロック内の以前検討した入力サブフィンガープリントから）ことにより、現在の入力ビデオブロックに対する新規候補マップ内へ転送される。
【００６１】
現在のブロックに対する全てのサブフィンガープリントの検査が終了すると、現在の、以前の、および次のブロックのマップがともに追加され、現在のブロックのマップからの証拠に最大の重み付けが与えられるが、他の２つのブロックのマップは候補を追加でき、または既存の候補に対する支持を増加させることができる。この組合せマップから、処理は、そのマップ上で不鮮明ピーク抽出法（smeared peak picking）（および非極大値抑圧法）を用いて、第２ステージで検討される（ビデオ、オフセット）候補のリストを作成する。不鮮明ピーク抽出法は、単一の候補内の開始時間に対するオフセット全体の単純な畳み込み積分である。例示の実施形態は、可能性のある再生速度変更に対する最大予測時間分散の２倍となる三角幅を持つ三角窓により畳み込むステップを含む。例えば、１０秒のブロックサイズを持つビデオ再生の際に、１０％の速度増加、または速度低下までサポートするには、全三角幅は２秒となる。畳み込みプロセスは、近傍の開始時間オフセットに対する支持があるピークの高さを増大させる。非極大値抑圧法は、このステージの最終候補として選択されたピークを強めて、この不鮮明な時間信号の特徴的な極大値に属させるプロセスである。このプロセスは、信号内の最大極値を探し、その場所（および値）を記録することにより開始される。そして、プロセスは、その最大値までの特定の時間間隔より近い値をゼロに設定する（例えば、１０秒ブロックを用いる場合、５秒分離）。ゼロ設定プロセスは、元の（不鮮明な）関数が単調に減少する限り、時間的に外側、前方および後方へと継続される。不鮮明ピーク抽出法／非極大値抑圧法を用いると、二次元変換が要求するような特別なメモリがなくても、より一般的な傾斜および遮断（slope-and-intercept）のハフ変換の機能性が提供される。ステージ１の出力は、入力ビデオと参照ビデオとの間の一致部分を決定するように更に検討される候補ビデオセグメント（それぞれ参照サブフィンガープリントと対応する）の限定リストである。これに対する極限セットも高いシステム依存性を持つが、１０秒間の入力ブロックあたり１０００候補一致をはるかに下回るようにできるのが普通である。
ステージ２：候補評価
【００６２】
第２ステージ処理は、第１ステージで見つかった候補ビデオセグメントを検討し、一致の一部が正当か、全てが正当か、またはどれも正当でないかを判定する。プロセスは、参照セット内のコピー（全体または一部）の可能性を許容するので、より一般的な説明を提供する（プローブブロックあたりの単一のＹｅｓ／Ｎｏ一致判定の代わりに）。第２ステージ処理は、多くの様々なファイルとの間違った一致がある非記述部分から、時間が僅かにシフトすると同一の参照素材にすら一致が乏しいタイミング依存部分まで、広い範囲のメディアを扱うことができる。
【００６３】
このタスクと、素材のこの範囲とを取り扱うために、候補ビデオセグメント毎に一致品質尺度を作成することにより分類プロセスが開始される。一実施形態では、動的時間ワープ法（ＤＴＷ）が、現在の入力ビデオブロックと参照ビデオとの間の時間をまたいで最良の配置を決定する（１１０２）。ＤＴＷのパラメータは、アプリケーションがサポートしなければならない一致メディア内の時間歪み量により決定される（例えば、多くのアプリケーションでは、約１５％の高速化または低速化）。ＤＴＷの出力から、入力ビデオの個々のサブフィンガープリントと、参照サブフィンガープリントとの間で対となる組合せが決定される。対のセットが評価されて、入力ビデオと参照ビデオとの間の一致ベクトルの記述を生成する（１１０４）。この一致ベクトルに記入する可能性がある例は以下のようになる：
１）対となるサブフィンガープリントベクトル間の累積ハミング距離。
２）対となるベクトルの少なくとも８０％が一致するサブフィンガープリントの割合。
３）対となるベクトルの少なくとも６０％が一致するサブフィンガープリントの割合。
４）対となるベクトルの少なくとも４０％が一致するサブフィンガープリントの割合。
５）対となるベクトルの少なくとも２０％が一致するサブフィンガープリントの割合。
６）復号パスと最小二乗誤差（ＬＳＥ）適合直線復号パスとの間の平均二乗誤差（ＭＳＥ）。
７）ＬＳＥ適合直線復号パスの傾斜。
８）正当なサブフィンガープリントと対になった正当サブフィンガープリントの数、および少なくとも１０％の対となるベクトルの一致。ここで、正当／不当は、フロントエンドのフィンガープリントプロセスの間で使用するある尺度を用いて決定される（例えば、非ブランクまたは非サイレント）。
９）不当なサブフィンガープリントと対になった不当サブフィンガープリントの数。
１０）正当なサブフィンガープリントと対になった不当サブフィンガープリントの数。
１１）第１ステージの候補リスト内でリストに挙げた同一ビデオと、近似的に同一オフセットを持つ近傍プローブブロックの数。
１２）この対が第１ステージの証拠の収集中に受け取った投票の数。
１３）以前検査されたチャンネル上での、この参照との一致の存在、一致の信頼性、および一致のタイミングとオフセットの類似性。
１４）プレミアムとして参照を指定。
１５）このプローブを生成したユーザーのアップロード履歴（例えば、参照セットから以前アップロードしたコンテンツを有する）。
１６）メタデータがプローブと参照コンテンツの両方について利用可能な場合、これらの記述間の類似性（例えば、アンカーテキスト）。
【００６４】
このベクトル記述から品質尺度を決定する（１１０６）。品質尺度の一実施例では、真一致に対するモデルと偽一致に対するモデルとの間の尤度比を用いる。適切モデルは、なかでも、全共分散ガウスモデルまたは対角線分散ガウス混合モデルであろう。代替として、この品質尺度ステップ（１１０６）は、全ての品質尺度をゼロに設定するだけでバイパスさせることができる。
【００６５】
オプションで、現在のブロックに対する全ての第１ステージ候補に対して品質尺度を計算すると、このセットに母集団統計を用いて、非記述セグメントと時間オフセット依存セグメントとの間の区別に役立てることができる。第１ステージ候補リストからの品質尺度の広がりがこれら２つの間で異なると仮定することにより、これを実行できる。例えば、それは、典型的な時間依存コンテンツは幾つかの軸（例えば、復号パスの直線性）上で良く一致するが、他の軸上では一致しない単一の候補対しか持たないけれども、非記述コンテンツは、ある範囲（しきい値超）に一致する多くの候補対を有するということかもしれない。この種の区別には、母集団正規化エントリを持つ一致対の記述を拡張することにより、ある程度の支持を提供できる。これらには以下が含まれる：
１）対に対する品質尺度（正規化せずに）。
２）対の順位であって、格付けにはプローブブロックに対する候補一致の品質尺度を用いる。
３）プローブブロックに対する候補一致の平均品質尺度。
４）プローブブロックに対する候補一致の標準偏差。
５）プローブブロックに対する候補一致の逆標準偏差。
６）プローブブロックに対する候補に関する品質尺度の平均値と標準偏差により正規化された対の品質尺度。
７）プローブブロックに対する候補に関する品質尺度の平均値と標準偏差により正規化された対のランク。
このステップも追加エントリをゼロに設定することにより省略できる。
【００６６】
次いで、この拡張された一致対記述が、真／偽一致対の分類要素への入力として提供される。分類要素を用いて（１１０８）、正当または不当な一致として候補を分類し、一致に対する信頼点数を提供する。分類要素は、ニューラルネットワーク様の構造に基づくか、または線形分類要素に基づく任意の多様な形式とすることができる。分類要素がその対の受け入れを示す場合、それは、信頼点数とともに第３ステージに提供されるリスト内に含まれる。さもなければ削除される。このステージの出力は、正当な一致候補のリストである。
ステージ３：候補組合せおよび剪定
【００６７】
コンテンツによっては、第２ステージ試験に合格する多数の候補、重複コンテンツを含む多数の候補が存在する。これらそれぞれをリストに挙げる代わりに、最終的な候補リストのある長さ制限を超えるものを別々にまたは完全に削除し、一実施形態では、候補リストをより簡潔に、かつより信頼できるようなものに変える。
【００６８】
これは、様々な入力ビデオブロックに一致する参照ビデオ部分を収集し、これらのコンポーネントを単一の組合せ一致に組み込むことにより実施される。例えば、図１２に示すように、入力ビデオと参照ビデオとの間のコンポーネント一致（ブロック１、ブロック２、ブロック３）は、組合せ一致に組み込まれる。剪定ステージに合格するには、例えば、以下のような制約が課される：
１）少なくとも２つの異なる入力ビデオのブロックが、組合せ一致に支持を提供する（ここで入力ビデオブロックと参照ビデオの一部との間の任意の信号対は、一つの組合せ一致しか支持できない）。
２）組合せ一致の平均一致品質が、あるしきい値を超える。
３）入力ビデオと、組合せを支持するブロック全体の参照部分との間の分散が、あるしきい値未満である。
【００６９】
この一致グループ化プロセスを実行する一手法は、特定の時間−場所制限内にある全コンポーネント一致が支持リスト内に置かれる欲張りアルゴリズムである。その全長さのリストが、入力ビデオとコンポーネントブロックを横断する参照ビデオとの間のオフセットの分散が多すぎることを示す場合、異常値（オフセット内の）がその一致から削除され、セットが長さ２未満となるか、または組合せ一致がその試験に合格するまで、そのセットは再考される。組合せ一致がその試験に合格した場合、その組合せ一致の支持を提供する全てのコンポーネント一致には、一致コンテンツとしてフラグが立てられる。更に、一致コンテンツを含むよう組合せ一致の「影」にある他の一致を決定する。組合せ一致の影は、入力ビデオと同一参照ビデオとの間の類似時間支持を有し、二つの間の類似時間オフセットを有するこれらの一致部分である。組合せ一致がその試験に合格しない場合、提案された組合せ一致のシードとして使用されたコンポーネント一致が削除される。次いで、そのリストが空になるまで、縮小され要求されないリスト上で、組合せプロセスが繰り返される。
【００７０】
最終ステージプロセスの一実施形態は、類似形式の一般的な低速運動のシーケンスと一致するのを避けるよう構成される。この問題の例は、「アナウンサの顔（talking head）」のビデオである。ビデオトラックは明るく、かつ鮮明であることが多いが、多くの従来のフィンガープリント法は、暗い背景、暗いスーツのビデオコンテンツを中央寄りの明るい色の顔と区別することができない。例えば、第１対象「ジョージ」の記者会見のビデオトラックは、ジョ−ジによる全ての他の記者会見と類似している（多くのフィンガープリント生成プロセスで使用する詳細レベルまで）ように見え、第２対象「ビル」の何れかの記者会見と酷似させることが容易にできる。従って、従来のフィンガープリントは、残念ながらこれらのビデオ間の一致を示すことができない。ビデオチャンネルのこれらの不正一致は、多くの疑念のある一致を生成しがちであり、オーディオチャンネル間の対応する一致では起きない。従って、両チャンネルをカバーせず、疑念のある一致と支持される一致とのある比率のしきい値を超えるこれらの一致についての、これらの不正一致の報告を避けるために、プロセスは、その一致の信頼性を低下させるか、または信頼性が余りに低ければ、その一致を完全に削除する。こうして、多数のブロック支持を持つ僅かな数の一致だけが作成され、全プロセスから戻される。
一致結果
【００７１】
最終出力は、入力ビデオ（または、入力ビデオの一部）と一致すると決定された参照ビデオ（または参照ビデオの識別した部分）のリストを提供する。この決定は幾つかの目的のために使用できる。第１に、アップロードされた入力ビデオ１０２が、既に参照ビデオセット内のビデオの複製であると一致モジュール１０８が決定した場合、アップロードされた入力ビデオ１０２を、格納空間の節約を目的に廃棄できる。第２に、入力ビデオ１０２を用いて、例えば、著作権保護されたビデオコンテンツを探して、参照ビデオを調べることができる。次いで、これらのビデオにフラグを立てたり、または参照ビデオセットから削除したりすることができる。利点としては、説明したシステムおよび方法は、時間的に厳しい制約があっても、および／または限られたメモリ量を用いたとしても、効率的かつ正確に一致を検出できる。
さらなる代替の実施形態
【００７２】
上記説明のいくつかの部分に、情報に関する操作のアルゴリズムと、記号表現の観点から本発明の特徴とが述べられている。これらのアルゴリズムの説明および表現は、当該分野に精通する者により使用されて、自らの業務内容を当該分野に精通する他の者に最も効率的に伝えるための手段である。これらの操作を、機能的または論理的に説明したが、言うまでもなく、コンピュータープログラムを介して実装される。更に、モジュールまたはコード装置として、これら操作の編成に言及することが、一般性を失わず時には便利であると証明されてもいる。
【００７３】
但し、これらおよび類似の全ての用語は、適切な物理量と関係付けられるべきであり、これらの量に適用される単に便利なラベルに過ぎないということに留意すべきである。ここでの検討から明らかなように、特に記載のない限り、言うまでもなく、全体を通じて、「処理」または「演算」または「計算」または「決定」または「表示」等の用語を使った説明および検討は、コンピューターシステム；または、コンピューターシステムメモリ、レジスタもしくは他のそのような情報格納装置、送信装置もしくはディスプレイ装置内の物理量（電子量）として表されるデータを操作し、変換する類似の電子計算装置；の作用およびプロセスのことを指している。
【００７４】
本発明の特定の態様は、本明細書中でアルゴリズム形式で説明されるプロセスステップと命令を含む。言うまでもなく、本発明のプロセスステップと命令は、ソフトウエア、ファームウエアまたはハードウエアで実施でき、ソフトウエアで実施する場合、リアルタイムネットワーク運営システムにより使用される様々なプラットフォームに常駐させるようダウンロードでき、操作することができる。
【００７５】
本発明は、本明細書中の操作を実行する装置にも関連する。この装置は、要求される目的のために特別に構築してもよく、あるいはコンピュータ内に格納されるコンピュータープログラムにより選択的に活性化または再構成される汎用コンピュータを備えてもよい。このようなコンピュータープログラムは、限定はしないが、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気または光カード、アプリケーション特定集積回路（ＡＳＩＣ）、または電子命令格納に適した任意形式の媒体等のコンピュータで読取り可能な格納媒体に格納してもよく、それぞれは、コンピューターシステムバスに接続される。更に、本明細書で言及したコンピュータは、単一プロセッサを含んでもよく、あるいは、計算能力を増大させるためのマルチプロセッサ設計を利用するアーキテクチャとしてもよい。
【００７６】
本明細書で提示したアルゴリズムおよびディスプレイは、本質的にどれか特定のコンピュータまたは他の装置と関連しては
いない。各種汎用システムを本明細書の教示に従うプログラムにより使用することもでき、または要求される方法ステップを実行するよう更に専用装置を構築すると便利であることが証明できる。多様なこれらのシステムに要求される構造は、上記説明から明らかであろう。更に、本発明の説明は、何らかの特定のプログラミング言葉を参照してはいない。言うまでもなく、本明細書で説明したように、多様なプログラミング言葉を用いて本発明の教示を実装することができ、本発明の可能性と最良態様の開示のために特定の言葉に対する何らかの参照が提供される。
【００７７】
最後に、本明細書で使用している言葉は、原則的に可読性と説明を目的に選定したものであり、本発明の主題を限定したり、範囲を定めたりするためのものではない。従って、本発明の開示は、説明を意図したものであって、本発明の範囲を制限するものではない。
【図１】
2010537585.tif 000005
【図２】
2010537585.tif 000006
【図３】
2010537585.tif 000007
【図４】
2010537585.tif 000008
【図５】
2010537585.tif 000009
【図６】
2010537585.tif 000010
【図７】
2010537585.tif 000011
【図８】
2010537585.tif 000012
【図９】
2010537585.tif 000013
【図１０】
2010537585.tif 000014
【図１１】
2010537585.tif 000015
【図１２】
2010537585.tif 000016
【国際調査報告】
2010537585.tif 000017