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