JP6763019B2 - メディアセグメント識別効率向上のために探索索引を区分するためのシステムおよび方法 - Google Patents

Description

[0001]関連出願の相互参照
本出願は、参照によりその開示全体が本明細書に組み入れられる、２０１５年７月１６日に出願された米国仮特許出願第６２／１９３３５１号の恩典を主張するものである。

[0002]本出願は、参照によりその開示全体が本明細書に組み入れられる、２００９年５月２９日に出願された米国仮特許出願第６１／１８２３３４号、および２００９年１２月２９日に出願された米国仮特許出願第６１／２９０７１４号の恩典を主張する、２０１０年５月２７日に出願された米国特許出願第１２／７８８７２１号、現在の米国特許第８５９５７８１（Ｂ２）号の継続出願である２０１４年１１月２４日に出願された、米国特許出願第１４／５５１９３３号に関連するものである。

[0003]本開示は、メディアシステム（例えば、テレビシステム、コンピュータシステム、またはインターネットに接続することができる他の電子機器）によって表示されたコンテンツの認識に用いられるシステムリソースの管理を改善することに関する。さらに、本開示は、コンテンツを効果的、効率的に識別することにも関する。例えば、探索索引を、コンテンツの識別効率を向上させるように並列に探索されうるバケットに区分するための様々な技術およびシステムが提供される。

[0004]光ファイバおよびデジタル伝送技術の進歩により、テレビ業界は、チャンネル容量を急速に増加させ、よって、何千以上ものオンデマンド番組のチャンネルに加えて何百ものテレビ番組のチャンネルも提供することができるようになっている。全国規模でテレビ受信機をモニタしている自動コンテンツ認識（ＡＣＲ）システムの観点から見ると、１主要ＤＭＡ当たり１０〜２０のローカルチャンネル（米国ではおおよそ１００）、合計すると何千もの放送チャンネルおよび何万ものオンデマンドコンテンツが存在することに伴う問題はさらに一層難しくなっている。

[0005]本発明の実施形態は一般に、テレビシステムの画面上に表示された映像セグメントまたは任意のソースからの音声セグメントを識別するためのシステムおよび方法と、そのような映像セグメントまたは音声セグメントの識別に基づいてメディアシステムにコンテキスト的ターゲットコンテンツを提供するためのシステムおよびモーションに関するものである。本明細書で用いる場合、「メディアシステム」という用語は、テレビシステム、音声システムなどを含むが、それらに限定されない。本明細書で用いる場合、「テレビシステム」という用語は、ウェブＴＶや接続ＴＶ（「スマートＴＶ」としても知られている）などのテレビ、およびセット・トップ・ボックス（ＳＴＢ）、デジタル・ビデオ・ディスク（ＤＶＤ）・プレーヤ、デジタル・ビデオ・レコーダ（ＤＶＲ）などの、テレビに組み込まれた、またはテレビと同じ場所に置かれる装置を含むが、それらに限定されない。本明細書で用いる場合、「テレビ信号」という用語は、テレビ番組またはコマーシャルの画像成分および音声成分を提供するように（メタデータありまたはなしで）合わせて放送される映像および音声データを表す信号を含む。本明細書で用いる場合、「メタデータ」という用語は、テレビ信号中の映像／音声データに関する、または関連したデータを意味する。

[0006]本発明の実施形態は、スマートＴＶ、ケーブルおよび衛星のセット・トップ・ボックスならびにインターネット接続ネットワーク・メディアプレーヤなどを含むクライアントメディア装置のような未知のソースからのコンテンツ認識の精度向上が得られる自動コンテンツ認識を目的として非常に大量のコンテンツを有利に区分するためのシステムおよび方法を対象とする。本発明はメディアデータのみならず、多次元で同時に探索されなければならない任意の大規模データベースに適用できることが企図されている。

[0007]多数のコンテンツソースの負荷の下では、ある特定の索引が情報のより大規模なコレクションの様々なサブセットである（本明細書では「キュー」とも呼ぶ）コンテンツ識別子の複数の索引の作成によって、フォールスポジティブを最小化し、正しいコンテンツ識別を最大化するタスクを著しく改善することができる。これらのグループ化索引は、一例として、ＴＶ格付けやソーシャルメディア言及によって決定されるテレビ番組の評判などの様々なパラメータを用いて選択することができる。例えば、より評判のよいチャンネル、おそらくは上位１０パーセントを１つの探索索引にグループ化し、残り９０パーセントを別の索引にグループ化することができる。別のグループ化は、ローカル・テレビ・チャンネルだけの第３の索引へのコンテンツの分離であり、さらに、第４の例は、オンデマンドを放送コンテンツから分離してオンデマンド索引にすることであろう。さらに別のコンテンツグループは、商業的に重要とみなされ、別個の探索空間に隔離されることによって有益となるはずのコンテンツから導出することができる。関連したコンテンツの任意の適切な分離を用いて本発明の実施形態をさらに利することができるはずである。

[0008]コンテンツグループに分離され、索引付け（ハッシュ化）されると、その結果は、「空間」として知られ、通称「バケット」と呼ばれる、１６から１００までのいずれかの多次元のベクトル空間になる。バケットは個々に探索され、探索結果は、参照によりその全体が本明細書に組み入れられる、米国特許第８５９５７８１号に記載される経路追跡プロセスに供給される。経路追跡プロセスは、各バケット内の一致するメディアセグメントを見つけようと試み、同時に、または並列に実行することができる。前記各バケットからの候補は重み付けされ、最も近い一致の映像セグメントを選択する、よって、どの映像セグメントがテレビシステムの画面上に表示されているか識別する最終判断が行われる。特に、結果として得られる、現在視聴されている映像セグメントを識別するデータを用いて、ＴＶ視聴者の反応（例えば、宣伝されている製品に関する詳細情報や画面上の俳優の背景情報を要求する）を取り込み、適切に応答することができる。さらに、どの映像セグメントが画面上で表示されているか識別することにより、本発明の中央システムは、様々なデータ分析用途のために現在視聴されているテレビ番組のセンサスを維持することができる。現在の映像セグメントの前記知識の多くの他の用途には、おそらくは、中でも特に、検出されたコマーシャルによる中断の間のより関連性のあるコマーシャルメッセージの置換が含まれるであろう。

[0009]いくつかの実施形態によれば、特定の間隔（例えば１００ミリ秒）を置いて、画面上に表示されている画素データ（または関連付けられた音声データ）のサブセットをサンプリングし、次いで、コンテンツデータベースにおいて類似した画素（または音声）データを見つけることによって映像セグメントが識別される。他の実施形態によれば、映像セグメントと関連付けられた音声データまたは画像データを抽出し、次いで、コンテンツデータベースにおいて類似した音声データまたは画像データを見つけることによって映像セグメントが識別される。別の実施形態によれば、既知の自動音声認識技術を用いて映像セグメントと関連付けられた音声データを処理することによって映像セグメントが識別される。さらに別の実施形態によれば、映像セグメントと関連付けられたメタデータを処理することによって映像セグメントが識別される。

[0010]本発明の実施形態は、インタラクティブ・テレビ・システムにコンテキスト的ターゲットコンテンツを提供するためのシステムおよび方法をさらに対象とする。コンテキストターゲティングは、表示されている映像セグメントの識別のみならず、現在表示されている映像セグメントの特定の部分の再生時間またはオフセット時間に関する決定にも基づくものである。「再生時間」および「オフセット時間」という用語は、本明細書では区別なく用いられ、特定のテレビ番組またはコマーシャルの開始時間など、固定された時点からのオフセットである時間を指す。

[0011]より具体的には、本発明の実施形態は、接続ＴＶ上で何が再生されているか検出し、再生されているものの主題を推論し、それに応じて視聴者とインタラクションすることができる技術を含む。特に、本明細書で開示する技術は、インタラクティブＴＶがインターネットを介してサーバから機能を厳密に引き出す限られた能力を克服し、それによって、コンテンツのビデオオンデマンドバージョンへの即時のアクセスを提供できる能力を含み、利用できる場合に、ユーザにコンテンツの高解像度または３Ｄフォーマットを視聴するオプションを、最初から再生、早送り、一時停止、および巻き戻しできる追加機能と共に提供する新規のビジネスモデルを可能にする。また本発明は、現在のＶｏＤ番組に含まれる一部または全部の広告メッセージを、例示にすぎず、それだけに限らないが、視聴者の位置、人口統計群、もしくは買い物履歴に関連してカスタマイズさせることを可能にし、またはある特定のビジネスモデルをサポートするためにコマーシャルの数もしくは長さを削減させ、もしくは完全に削除させることも可能にする。

[0012]いくつかの実施形態によれば、画面上に表示されている画素データ（または関連付けられた音声データ）のサブセットをサンプリングし、次いで、コンテンツデータベースにおいて類似した画素（または音声）データを見つけることによって映像セグメントが識別され、オフセット時間が決定される。他の実施形態によれば、映像セグメントと関連付けられた音声データまたは画像データを抽出し、次いで、コンテンツデータベースにおいて類似した音声データまたは画像データを見つけることによって映像セグメントが識別され、オフセット時間が決定される。別の実施形態によれば、既知の自動音声認識技術を用いて映像セグメントと関連付けられた音声データを処理することによって映像セグメントが識別され、オフセット時間が決定される。さらに別の実施形態によれば、映像セグメントと関連付けられたメタデータを処理することによって映像セグメントが識別され、オフセット時間が決定される。

[0013]本明細書でより詳細に説明するように、接続ＴＶ上で視聴されている映像セグメントを識別し、任意選択で、オフセット時間を決定するためのシステムは、接続ＴＶをその構成要素とするテレビシステムに位置することができる。代替の実施形態によれば、映像セグメントを識別するためのソフトウェアのある部分はテレビシステム上に位置し、別の部分はインターネットを介してテレビシステムに接続されたサーバ上に位置する。

[0014]本発明の一実施形態によれば、方法が提供される。本方法は、複数の既知のメディアコンテンツを受信するステップを含む。複数の既知のメディアコンテンツは関連付けられた既知のコンテンツ識別子（すなわち、キュー）を有する。本方法は、複数の既知のメディアコンテンツを第１の索引と第２の索引とに区分するステップと、第１の索引を１つまたは複数の第１のバケットに分離するステップとをさらに含む。第１の索引は、第１の索引内の既知のメディアコンテンツと関連付けられている既知のコンテンツ識別子を用いて第１のバケットに分離される。本方法は、第２の索引を１つまたは複数の第２のバケットに分離するステップをさらに含む。第２の索引は、第２の索引内の既知のメディアコンテンツと関連付けられている既知のコンテンツ識別子を用いて第２のバケットに分離される。本方法は、メディアシステムによって表示されている未知のメディアコンテンツに対応する未知のコンテンツ識別子を受信するステップと、未知のコンテンツ識別子を求めて第１のバケットと第２のバケットとを同時に探索するステップとをさらに含む。本方法は、第１のバケットまたは第２のバケットの中から既知のメディアコンテンツを選択するステップをさらに含む。選択された既知のメディアコンテンツは未知のコンテンツ識別子と関連付けられている。本方法は、未知のメディアコンテンツを既知のメディアコンテンツとして識別するステップをさらに含む。本方法は、コンピュータ上で実施することができる。

[0015]本発明の別の実施形態によれば、システムが提供される。本システムは、１つまたは複数のプロセッサを含む。本システムは、１つまたは複数のプロセッサ上で実行されると、１つまたは複数のプロセッサに、上記方法に記載されるステップを含む動作を行わせる命令を含む非一時的な機械可読記憶媒体をさらに含む。

[0016]本発明の別の実施形態によれば、コンピューティング機器の非一時的な機械可読記憶媒体において有形に具体化されたコンピュータプログラム製品が提供される。本コンピュータプログラム製品は、１つまたは複数のデータプロセッサに、上記の方法に記載されたステップを行わせるように構成された命令を含む。

[0017]使用されている用語および表現は限定ではなく説明の用語として使用されており、そのような用語および表現の使用に際して、図示され、説明されている特徴またはそれらの特徴の部分の均等物を除外することは意図されていない。しかし、特許請求されるシステムおよび方法の範囲内で様々な改変が可能であることが認められる。よって、本発明のシステムおよび方法は、例および任意選択の特徴によって具体的に開示されているが、本明細書で開示される概念の改変および変形も当業者によって用いられうること、ならびにそのような改変および変形は添付の特許請求の範囲によって定義されるシステムおよび方法の範囲内であるとみなされることを理解されたい。

[0018]この発明の概要は、特許請求される主題の重要な、または本質的な特徴を識別するためのものではなく、特許請求される主題の範囲を定めるために単独で使用するものでもない。主題は、本特許の明細書全体の適切な部分、任意の、またはすべての図面、および各請求項を参照することによって理解すべきである。

[0019]以上については、他の特徴および実施形態と共に、以下の明細書、特許請求の範囲、および添付の図面を参照すればより明らかになるであろう。

[0020]下記の図面に関連して以下で本発明の例示的実施形態を詳細に説明する。図面において、類似した参照番号は図面全体を通して類似した構成要素または部分を表す。

本発明の実施形態によるメディアシステムによって表示されているメディアコンテンツを識別するための照合システムの一例のブロック図である。 本発明の実施形態による未知のデータ点を識別する照合システムの一例の図である。 本発明の実施形態によるメディア・キャプチャ・システムの一例のブロック図である。 本発明の実施形態によるディスプレイによって提示されたメディアコンテンツを収集するためのシステムの一例のブロック図である。 本発明の実施形態によるキューデータの処理経路を示す図である。 本発明の実施形態による過度にクラスタ化された擬似ランダムプロジェクションを用いてレイアウトされたベクトルマップのグラフプロットである。 本発明の実施形態によるより均一に間隔を置いた擬似ランダムプロジェクションを用いてレイアウトされたベクトルマップのグラフプロットである。 本発明の実施形態によるランダムに生成されたベクトルを中心としないクラスタ化されたキューデータを示す図である。 本発明の実施形態による数学的オフセット関数を用いてランダムに生成されたベクトルを中心とするクラスタ化されたキューデータを示す図である。 本発明の実施形態によって候補一致キューを捜し出すのに用いられる、「バケット」と呼ばれる２つのベクトル間のエリア内の適当な数のキュー点を示すグラフプロットである。 本発明の実施形態によるバケット内の多数のキュー点を示すグラフプロットである。 本発明の実施形態によるメディア照合エンジンに供給される一致候補を求めて探索されるバケットのグラフィック表現である。 本発明の実施形態による、各バケットがメディア照合エンジンに供給する、同時に、または並列に探索することができる異なるサイズのバケットのグラフィック表現である。 本発明の実施形態による、メディアタイプを処理して、別々の出力を生じる個々のメディア照合プロセスによって探索される個々の索引にする、映像キューを処理するためのインタラクティブ・テレビ・システムおよび関連サーバシステムの図である。 本発明の実施形態による、メディアタイプを処理して、別々の出力を生じる個々のメディア照合プロセスによって探索される個々の索引にする、映像キューを処理するための方法の流れ図である。 本発明の実施形態による、メディアタイプを処理して、メディア照合プロセスによって探索される前に組み合わされる個々の索引にする、映像キューを処理するためのインタラクティブ・テレビ・システムおよび関連サーバシステムの図である。 本発明の実施形態による、メディアタイプを処理して、メディア照合プロセスによって探索される前に組み合わされる個々の索引にする、映像キューを処理するための方法の流れ図である。 本発明の実施形態による、メディアタイプを処理して、メディア照合プロセスによって探索される前に個々にタグ付けされ、重み付けされる個々の索引にする、映像キューを処理するためのインタラクティブ・テレビ・システムおよび関連サーバシステムの図である。 本発明の実施形態による、メディアタイプを処理して、メディア照合プロセスによって探索される前に個々にタグ付けされ、重み付けされる個々の索引にする、映像キューを処理するための方法の流れ図である。 本発明の実施形態によるテレビ広告を検出するメディア処理センタの図である。 本発明の実施形態によるテレビ広告を識別するための方法の流れ図である。 本発明の実施形態によるＴＶ広告が置換される広告ブロック（すなわち、広告ポッド）を有する映像セグメントの図である。 本発明の実施形態による映像番組セグメントを検出するメディア処理センタの図である。 本発明の実施形態による、映像番組セグメントを識別し、コンテキスト的関連マルチメディアをオーバレイするための方法の流れ図である。 本発明の実施形態によるオーバレイされたコンテキスト的関連マルチメディアコンテンツを有する映像セグメントの図である。 本発明の実施形態によるオーバレイされたコンテキスト的関連マルチメディアコンテンツありとなしの映像セグメントの図である。 本発明の実施形態による点位置とそれらの周りの経路点とを示す図である。 本発明の実施形態によるクエリ点からある距離内に位置する点の集合を示す図である。 本発明の実施形態による可能な点の値を示す図である。 本発明の実施形態による指数関数的に増加する幅の環に分割された空間を示す図である 本発明の実施形態による自己交差経路とクエリ点とを示す図である。 本発明の実施形態による３つの連続した点位置とそれらの周りの経路点とを示す図である。

[0053]以下の記述では、説明を目的として、本発明の実施形態の十分な理解を提供するために具体的詳細が示されている。しかし、これらの具体的詳細なしでも様々な実施形態が実施されうることは明らかであろう。図および説明は限定のためのものではない。

[0054]以下の説明は、例示的実施形態を提供するものにすぎず、本開示の範囲、適用性、または構成を限定するためのものではない。以下の例示的実施形態の説明はむしろ、当業者に、例示的実施形態の実施可能要件を提供するものである。添付の特許請求の範囲に記載されている本発明の趣旨および範囲を逸脱することなく要素の機能および構成の様々な変更を行いうることを理解されたい。

[0055]以下の説明では実施形態の十分な理解を提供するために具体的詳細が示されている。しかし、実施形態はこれらの具体的詳細なしでも実施されうることが当業者には理解されるであろう。例えば、不必要な詳細で実施形態を不明瞭にしないように、回路、システム、ネットワーク、プロセス、および他の構成要素をブロック図形式の構成要素として示す場合がある。場合によっては、各実施形態を不明瞭にしないように、周知の回路、プロセス、アルゴリズム、構造、および技術を不要な詳細なしで示すこともある。

[0056]また、個々の実施形態を、流れ図、フロー図、データフロー図、構造図、またはブロック図として描かれたプロセスとして記述する場合があることにも留意されたい。流れ図は各動作を順次的なプロセスとして記述している場合もあるが、動作の多くは、並列に、または同時に行うことができる。加えて、動作の順序を並べ替えることもできる。プロセスは、その動作が完了したときに打ち切られるが、図には含まれていない追加のステップを有する可能性もある。プロセスは、方法、関数、プロシージャ、サブルーチン、サブプログラムなどに対応させることができる。プロセスが関数に対応する場合、その打ち切りは呼び出した関数またはメイン関数への関数の戻りに対応させることができる。

[0057]「機械可読記憶媒体」または「コンピュータ可読記憶媒体」という用語には、可搬型または非可搬型の記憶装置、光記憶装置、ならびに（１つまたは複数の）命令および／またはデータを記憶、収容、または担持することができる様々な他の媒体が含まれるが、これらに限定されない。機械可読記憶媒体またはコンピュータ可読記憶媒体には、データを格納することができ、搬送波および／または無線で、または有線接続上で伝搬する一時的な電子信号を含まない非一時的な媒体が含まれる。非一時的な媒体の例には、磁気ディスクや磁気テープ、コンパクトディスク（ＣＤ）やデジタル多用途ディスク（ＤＶＤ）などの光記憶媒体、フラッシュメモリ、メモリまたはメモリデバイスが含まれるが、これらに限定されない。コンピュータプログラム製品には、プロシージャ、関数、サブプログラム、プログラム、ルーチン、サブルーチン、モジュール、ソフトウェアパッケージ、クラス、もしくは命令を表すコードセグメントもしくは機械実行可能命令、または命令、データ構造、もしくはプログラム文の任意の組み合わせが含まれる。コードセグメントは、情報、データ、引数、パラメータ、またはメモリコンテンツを渡し、かつ／または受け取ることによって、別のコードセグメントまたはハードウェア回路に結合されてよい。情報、引数、パラメータ、データ、または他の情報は、メモリ共有、メッセージパッシング、トークンパッシング、ネットワーク伝送、または他の伝送技術を含む任意の適切な手段を用いて、受け渡され、転送され、または伝送されてよい。

[0058]さらに、各実施形態は、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語、またはこれらの任意の組み合わせによって実施されてもよい。ソフトウェア、ファームウェア、ミドルウェア、またはマイクロコードとして実施される場合、必要なタスクを行うプログラムコードまたはコードセグメント（例えば、コンピュータプログラム製品）は、機械可読媒体に格納されてよい。（１つまたは複数の）プロセッサは必要なタスクを行うことができる。

[0059]図のいくつかに示されるシステムは、様々な構成で提供されうる。いくつかの実施形態では、システムは、システムの１つまたは複数の構成要素がクラウド・コンピューティング・システムとして１つまたは複数のネットワークにわたって分散されている分散システムとして構成される。

[0060]光ファイバおよびデジタル伝送技術の進歩により、テレビ業界は、チャンネル容量を急速に増加させ、全国規模で、何千ものテレビ番組のチャンネルおよび何十万ものオンデマンド番組のチャンネルを提供することができるようになっている。何百万ものアクティブなテレビ表示システムをモニタすることと、非常に多くの何千もの放送チャンネルおよび何万ものオンデマンドコンテンツ配信システムを、往々にしてほぼリアルタイムで迅速に識別することを伴う全国的なビジネスモデルをサポートし、これらを商業的に妥当なコンピューティングリソースを利用してサポートすることが、本明細書に記載するシステムおよび方法によって対処するまだ満たされていない課題である。

[0061]さらに詳細に後述するように、本開示のある特定の態様および特徴は、未知のデータ点を１つまたは複数の基準データ点と比較することによって未知の映像セグメントを識別することに関するものである。本明細書に記載するシステムおよび方法は、未知の映像セグメントを識別するのに使用される大規模なデータセットの格納および探索の効率を改善する。例えば、これらのシステムおよび方法は、識別を行うのに必要な大規模なデータセットの密度を低減しつつ、未知のデータセグメントの識別を可能にする。この技術は、大量のデータを収集し、操作する任意のシステムに適用することができる。これらのシステムの実例には、自動化されたコンテンツベースの探索システム（例えば、映像関連アプリケーションや他の適切なアプリケーションの自動コンテンツ認識）、ＭａｐＲｅｄｕｃｅシステム、Ｂｉｇｔａｂｌｅシステム、パターン認識システム、顔認識システム、分類システム、コンピュータ・ビジョン・システム、データ圧縮システム、クラスタ分析、または任意の他の適切なシステムが含まれる。当業者であれば、本明細書に記載する技術は、未知のデータと比較されるデータを格納する任意の他のシステムに適用できることを理解するであろう。自動コンテンツ認識（ＡＣＲ）のコンテキストでは、例えば、これらのシステムおよび方法は、照合システムが未知のデータグループと既知のデータグループとの間の関係を探索し、発見するために格納しなければならないデータ量を削減する。

[0062]限定ではなく例示にすぎないが、本明細書に記載するいくつかの例では、説明のために自動音声および／または映像コンテンツ認識システムを使用している。しかし、その他のシステムも同じ技術を使用できることを当業者は理解するであろう。

[0063]ＡＣＲシステムおよび大量のデータを使用する他のシステムの重要な課題となりうるのは、システムが機能するために必要なデータ量を管理することである。もう１つの課題としては、入ってくるコンテンツを照合するための基準として機能する既知のコンテンツのデータベースを構築、維持する必要が含まれる。このようなデータベースを構築し、維持することは、膨大な量（例えば、何百、何千、またはそれ以上）のコンテンツ（例えば、多くの他の潜在的なコンテンツソースの中でも特に全国配信されるテレビ番組やより一層大量のローカルテレビ放送）を収集し、ダイジェストすることを伴う。ダイジェストは、生データ（例えば、映像や音声）を削減して圧縮された、探索可能なデータにする任意の利用可能な技術を用いて行うことができる。２４時間、週７日間の動作スケジュールと、格納すべきおそらくは２週間分のコンテンツ（例えば、テレビ番組）のスライド窓とがあれば、ＡＣＲを行うのに必要なデータ量を迅速に構築することができる。上述の例示的システムのような、大量のデータを収集し、操作する他のシステムでも類似した課題が提示されうる。

[0064]本明細書に記載する中央自動コンテンツ認識（ＡＣＲ）システムは、リモート・クライアント・テレビ・システム上に現在表示されている映像番組を検出、識別するのに用いられ、ある特定のビジネスモデルをサポートするためにこれをほぼリアルタイムで行うことができる。メディア照合エンジンは、一般にバケットと呼ばれる複数のセグメントに分割されたメディア探索索引（例えば、ハッシュテーブル）を用いる。いくつかの実施形態では、複数の判断要因に基づいて、例えば、全国コンテンツをローカルコンテンツと分離することや、上位１０％の評判のよいコンテンツを残り９０％のあまり評判のよくないコンテンツから分離することや、放送メディアをオンデマンドメディアから分離することなどによって、キューデータ（例えば、コンテンツ識別子）を処理して独立した索引にする。分離されると、クライアント・テレビ・システムまたは他の装置からの未知のキューデータは中央サーバによって各索引に照らして検査される。１つまたは複数の索引の探索を並列に（すなわち、同時に）行うことができる。各索引のルックアップ（すなわち、探索）の結果は、参照によりその全体が本明細書に組み入れられる、米国特許第８５９５７８１（Ｂ２）号の経路追跡システムなどのコンテンツ照合システムに並列に適用することができる。

[0065]より小さいデータセット（すなわち、バケット）ほどより正確な照合結果をもたらし、よって、コンテンツ照合システムの探索効率を高めることができる。

[0066]図１に、未知のコンテンツを識別することができる照合システム１００を示す。いくつかの例では、未知のコンテンツは１つまたは複数の未知のデータ点を含むことができる。そのような例では、照合システム１００は、未知のデータ点を基準データ点と照合して、未知のデータ点と関連付けられた未知の映像セグメントを識別することができる。基準データ点は基準データベース１１６に含めることができる。

[0067]照合システム１００は、クライアント機器１０２と照合サーバ１０４とを含む。クライアント機器１０２は、メディアクライアント１０６と、入力装置１０８と、出力装置１１０と、１つまたは複数のコンテキストアプリケーション１２６とを含む。メディアクライアント１０６（テレビシステム、コンピュータシステム、またはインターネットに接続できる他の電子機器を含むことができる）は、映像番組１２８と関連付けられたデータ（例えば、放送信号、データパケット、他のフレームデータ）を復号することができる。メディアクライアント１０６は、映像の各フレームの復号されたコンテンツを、映像フレームの画素情報の表示またはさらなる処理に備えて映像フレームバッファに入れることができる。クライアント機器１０２は、映像信号を受信し、復号することができる任意の電子復号システムとすることができる。クライアント機器１０２は、映像番組１２８を受信し、映像情報を映像バッファ（図示せず）に格納することができる。クライアント機器１０２は、映像バッファ情報を処理し、図３に関連して以下でより詳細に説明する未知のデータ点（「キュー」と呼ぶことができる）を生成することができる。メディアクライアント１０６は、基準データベース１１６内の基準データ点と比較するために、未知のデータ点を照合サーバ１０４に送信することができる。

[0068]入力装置１０８には、メディアクライアント１０６に要求または他の情報が入力されることを可能にする任意の適切な装置を含むことができる。例えば、入力装置１０８には、キーボード、マウス、音声認識入力装置、無線機器からの（例えば、リモートコントローラ、モバイル機器、他の適切な無線機器からの）無線入力を受信するための無線インターフェース）、または任意の他の適切な入力装置を含むことができる。出力装置１１０には、ディスプレイ、無線機器（例えば、モバイル機器や他の適切な無線機器）に無線出力を送信するための無線インターフェース、プリンタ、または他の適切な出力装置など、情報を提示し、またはそれ以外に出力することができる任意の適切な装置を含むことができる。

[0069]照合システム１００は、最初に既知の映像データソース１１８からデータサンプルを収集することによって映像セグメントを識別するプロセスを開始することができる。例えば、照合サーバ１０４は、様々な映像データソース１１８から基準データベース１１６を構築し、維持するためにデータを収集する。映像データソース１１８には、テレビ番組、映画、または任意の他の適切な映像ソースのメディアプロバイダを含むことができる。映像データソース１１８からの映像データは、無線放送として、ケーブルＴＶチャンネルとして、インターネットからのストリーミングソースとして、また任意の他の映像データソースから提供することができる。いくつかの例では、照合サーバ１０４は、後述するように、映像データソース１１８からの受信映像を、基準データベース１１６において基準映像データ点を生成、収集するように処理することができる。いくつかの例では、映像データソース１１８からの映像番組を基準映像番組インジェストシステム（図示せず）によって処理することができ、基準映像番組インジェストシステムは、基準映像データ点を生成し、それらを格納するために基準データベース１１６に送ることができる。基準データ点は、上述のように、後で未知のデータ点を分析するのに用いられる情報を決定するのに用いることができる。

[0070]照合サーバ１０４は、ある期間（例えば、日数、週数、月数、または任意の他の適切な期間）にわたって受信された映像番組ごとの基準映像データ点を基準データベース１１６に格納することができる。照合サーバ１０４は、（例えば、キューまたはキュー値とも呼ばれる基準データ点を含む）テレビ番組サンプルの基準データベース１１６を構築し、絶えず、または定期的に更新することができる。いくつかの例では、収集されたデータは、周期的な映像フレーム（例えば、５番目ごとの映像フレーム、１０番目ごとの映像フレーム、１５番目ごとの映像フレーム、他の適切な数のフレーム）からサンプリングされた映像情報の圧縮表現である。いくつかの例では、１フレーム当たりのデータのバイト数（例えば、１フレーム当たり２５バイト、５０バイト、７５バイト、１００バイト、または任意の他のバイト数）が番組ソースごとに収集される。２５チャンネル、５０チャンネル、７５チャンネル、１００チャンネル、２００チャンネル、または任意の他の数の番組ソースなど、任意の数の番組ソースを用いて映像を取得することができる。例示のデータ量を用いると、３日間にわたって２４時間に収集される合計データは非常に大きくなる。したがって、実際の基準データ点集合の数を減らすことが、照合サーバ１０４の記憶負荷を低減させる上で有利である。

[0071]メディアクライアント１０６は、照合サーバ１０４の照合エンジン１１２に通信１２２を送信することができる。通信１２２は、照合エンジン１１２が未知のコンテンツを識別することを求める要求を含むことができる。例えば、未知のコンテンツは、１つまたは複数の未知のデータ点を含むことができ、基準データベース１１６は、複数の基準データ点を含むことができる。照合エンジン１１２は、未知のデータ点を基準データベース１１６内の基準データと照合することによって未知のコンテンツを識別することができる。いくつかの例では、未知のコンテンツは、（映像ベースのＡＣＲの場合の）ディスプレイによって提示されている未知の映像データ、（ＭａｐＲｅｄｕｃｅシステム、Ｂｉｇｔａｂｌｅシステム、または他のデータ・ストレージ・システムの場合の）探索クエリ、（顔認識の場合の）未知の顔の画像、（パターン認識の場合の）未知のパターンの画像、または基準データのデータベースと照合することができる任意の他の未知のデータを含むことができる。基準データ点は、映像データソース１１８から受信したデータから導出することができる。例えば、映像データソース１１８から提供された情報からデータ点を抽出することができ、それらのデータ点に索引付けして基準データベース１１６に格納することができる。

[0072]照合エンジン１１２は、候補決定エンジン１１４に、基準データベース１１６から候補データ点を決定するよう求める要求を送信することができる。候補データ点は、未知のデータ点からある決められた距離である基準データ点とすることができる。いくつかの例では、基準データ点と未知のデータ点との距離は、基準データ点の１つまたは複数の画素（例えば、単一の画素、画素群を代表する値（例えば、算術平均値、平均値、中央値、他の値）、または他の適切な数の画素）を、未知のデータ点の１つまたは複数の画素と比較することによって決定することができる。いくつかの例では、基準データ点は、各サンプル位置のところの画素が特定の画素値範囲内にある場合に未知のデータ点からある決められた距離とすることができる。

[0073]ある説明例では、画素の画素値は、（赤緑青（ＲＧＢ）色空間における）赤色値、緑色値、および青色値を含むことができる。このような例では、対応する赤色値、緑色値、および青色値をそれぞれ比較し、各値がある一定の値範囲内（例えば、０〜５値内）にあるようにすることによって、第１の画素（または第１の画素群を表す値）を第２の画素（または第２の画素群を表す値）と比較することができる。例えば、（１）第１の画素の赤色値が第２の画素の赤色値の０〜２５５の値範囲の５値内（プラスまたはマイナス）にあり、（２）第１の画素の緑色値が第２の画素の緑色値の０〜２５５の値範囲の５値内（プラスまたはマイナス）にあり、（３）第１の画素の青色値が第２の画素の青色値の０〜２５５の値範囲の５値内（プラスまたはマイナス）にある場合に、第１の画素を第２の画素と照合することができる。そのような例では、候補データ点は、未知のデータ点に対する近似一致である基準データ点であり、未知のデータ点について（異なるメディアセグメントに関連した）複数の候補データ点が識別されることになる。候補決定エンジン１１４は、候補データ点を照合エンジン１１２に返すことができる。

[0074]ある候補データ点について、照合エンジン１１２は、その候補データ点と関連付けられた、候補データ点の導出元である識別された映像セグメントに割り当てられたビンにトークンを付加することができる。対応するトークンを、識別された候補データ点に対応するすべてのビンに追加することができる。（視聴されている未知のコンテンツに対応する）さらに多くの未知のデータ点がクライアント機器１０２から照合サーバ１０４によって受信される際に、同様の候補データ点決定プロセスを行うことができ、識別された候補データ点に対応するビンにトークンを付加することができる。ビンのうちの１つだけが視聴されている未知の映像コンテンツのセグメントに対応し、その他のビンは、データ点値が類似しているために（例えば、類似した画素色値を有するために）照合されるが、視聴されている実際のセグメントは対応しない候補データ点に対応する。視聴されている未知の映像コンテンツセグメントのビンには、見られていないセグメントの他のビンよりも多くのトークンが割り当てることになる。例えば、より多くの未知のデータ点が受信されると、ビンに対応するより多数の基準データ点が候補データ点として識別され、より多くのトークンがビンに付加されることになる。ビンに特定の数のトークンが含められると、照合エンジン１１２は、ビンと関連付けられた映像セグメントが現在クライアント機器１０２で表示されていると判定することができる映像セグメントは、映像番組全体または映像番組の一部を含むことができる。例えば、映像セグメントは、映像番組、映像番組の場面、映像番組の１つもしくは複数のフレーム、または映像番組の任意の他の部分とすることができる。

[0075]図２に、未知のデータを識別するための照合システム２００の構成要素を示す。例えば、照合エンジン２１２は、既知のコンテンツ（例えば、既知のメディアセグメント、探索対象としてデータベースに格納された情報、既知の顔やパターンなど）のデータベースを用いて未知のコンテンツ（例えば、未知のメディアセグメント、探索クエリ、顔の画像やパターンなど）を識別するための照合プロセスを行うことができる。例えば、照合エンジン２１２は、基準データベース内の基準データ点２０４のうちの基準データ点と照合されるべき未知のデータコンテンツ２０２（「キュー」と呼ぶことができる）を受け取る。未知のデータコンテンツ２０２は、候補決定エンジン２１４が受け取ることもでき、照合エンジン２１２から候補決定エンジン２１４に送ることもできる。候補決定エンジン２１４は、探索プロセスを実行して、基準データベース内の基準データ点２０４を探索することによって候補データ点２０６を識別することができる。一例では、探索プロセスは、（未知のデータコンテンツ２０２の未知の値からある一定の距離である）近傍値の集合を生成する最近傍探索プロセスを含むことができる。候補データ点２０６は、照合プロセスを実行して照合結果２０８を生成するために照合エンジン２１２に入力される。アプリケーションに応じて、照合結果２０８には、ディスプレイによって提示されている映像データ、探索結果、顔認識を用いて判定された顔、パターン認識を用いて判定されたパターン、または他の任意の結果を含むことができる。

[0076]未知のデータ点（例えば、未知のデータコンテンツ２０２）の候補データ点２０６を決定する際に、候補決定エンジン２１４は、未知のデータ点と基準データベース内の基準データ点２０４との距離を決定する。未知のデータ点からある一定の距離である基準データ点は、候補データ点２０６として識別される。いくつかの例では、基準データ点と未知のデータ点との距離を、図１に関連して上述したように、基準データ点の１つまたは複数の画素を未知のデータ点の１つまたは複数の画素と比較することによって決定することができる。いくつかの例では、基準データ点は、各サンプル位置のところの画素が特定の値範囲内にある場合に未知のデータ点からある一定の距離とすることができる。上述したように、候補データ点は、未知のデータ点に対する近似一致である基準データ点であり、近似一致であるため、未知のデータ点について（異なるメディアセグメントに関連した）複数の候補データ点が識別される。候補決定エンジン１１４は、候補データ点を照合エンジン１１２に返すことができる。

[0077]図３に、復号器のメモリバッファ３０２を含む映像インジェスト・キャプチャ・システム４００の一例を示す。復号器は、照合サーバ１０４またはメディアクライアント１０６の一部とすることができる。復号器は、物理的なテレビ表示パネルまたはテレビ表示装置と共に動作せず、またはこれを必要としない場合もある。復号器は、デジタル映像番組を復号し、必要に応じて解読して、テレビ番組の非圧縮ビットマップ表現にすることができる。基準映像データの基準データベース（例えば、基準データベース３１６）を構築するために、照合サーバ１０４は、映像フレームバッファから読み出される映像画素の１つまたは複数の配列を取得することができる。映像画素の配列を映像パッチと呼ぶ。映像パッチは、任意の形状またはパターンとすることができるが、この具体例では、水平方向に１０画素×垂直方向に１０画素を含む、１０×１０画素配列として説明する。また、この例では、映像フレームバッファの境界内に均等に分布している、映像フレームバッファ内から抽出された２５個の画素パッチ位置があるものと仮定する。

[0078]図３には画素パッチ割り振りの例（例えば、画素パッチ３０４）が示されている。上述のように、画素パッチは１０×１０配列などの画素の配列を含むことができる。例えば、画素パッチ３０４は１０×１０の画素配列を含む。画素は、赤色値、緑色値、青色値などの色値を含むことができる。例えば、赤緑青（ＲＧＢ）色値を有する画素３０６が示されている。画素の色値は、色ごとに８ビットの２進値で表すことができる。画素の色を表すのに使用できる他の適切な色値には、輝度および彩度（Ｙ、Ｃｂ、Ｃｒ）の値や任意の他の適切な色値が含まれる。

[0079]各画素パッチの算術平均値（または場合によっては平均値）が取られ、結果として得られたデータレコードが作成され、タイムコード（またはタイムスタンプ）でタグ付けされる。例えば、１０×１０画素パッチ配列ごとに算術平均値が求められ、この場合、２５個の表示バッファ位置当たり２４ビットのデータが１フレーム当たり合計６００ビットの画素情報のために生成される。一例では、画素パッチ３０４の算術平均値が計算され、これが画素パッチ算術平均値３０８によって示されている。ある説明例では、タイムコードは、１９７０年１月１日の午前零時からの総経過時間（何分１秒単位）を表す「エポックタイム」を含むことができる。例えば、画素パッチ算術平均値３０８はタイムコード４１２と共にアセンブルされる。エポックタイムは、例えばＵｎｉｘベースのシステムを含むコンピューティングシステムで受け入れられている規約である。データレコードにはメタデータと呼ばれる映像番組に関する情報が添付される。メタデータは、番組識別子、番組時間、番組長、任意の他の情報など、番組に関する任意の情報を含むことができる。画素パッチの算術平均値、タイムコード、およびメタデータを含むデータレコードは、「データ点」（「キュー」とも呼ばれる）を形成する。データ点３１０は、基準映像データ点の一例である。

[0080]未知の映像セグメントを識別するプロセスは、基準データベースを作成するのと同様のステップから始まる。例えば、図４に、復号器のメモリバッファ４０２を含む映像インジェスト・キャプチャ・システム４００を示す。映像インジェスト・キャプチャ・システム４００は、（例えば、スマートＴＶ、モバイル機器、他のテレビ視聴機器など、インターネット接続テレビモニタ上で）ディスプレイによって提示されたデータを処理するクライアント機器１０２の一部とすることができる。映像インジェスト・キャプチャ・システム４００は、システム３００によって基準映像データ点３１０を作成するために用いられるプロセスと同様の未知の映像データ点４１０を生成するプロセスを利用することができる。一例では、メディアクライアント１０６は、照合サーバ１０４が未知の映像データ点４１０と関連付けられた映像セグメントを識別するように、未知の映像データ点４１０を照合エンジン１１２に送信することができる。

[0081]図４に示すように、映像パッチ４０４は、１０×１０の画素配列を含むことができる。映像パッチ４０４は、ディスプレイによって提示されている映像フレームから抽出することができる。映像フレームから複数のこのような画素パッチを抽出することができる。ある説明例では、映像フレームから２５個のこのような画素パッチが抽出された場合、その結果は７５次元空間内の位置を表す点になる。配列の色値（例えば、ＲＧＢ色値、Ｙ、Ｃｒ、Ｃｂ色値など）ごとに、算術平均値（または平均値）を計算することができる。算術平均画素値からデータレコード（例えば、未知の映像データ点４１０）が形成され、データに現在時刻が添付される。上述の技術を用いて基準データベース１１６からのデータと照合されるように、照合サーバ１０４に１つまたは複数の未知の映像データ点を送信することができる。

[0082]本発明のいくつかの実施形態によれば、探索されるデータのサイズは前記データのより効率的な探索方法を生み出すように低減される。索引を生成するプロセスのブロック図が図５に示されており、図５では、入ってくる、映像フレーム５０１の領域の平均画素値の形態のキューがハッシュ関数５０２によって処理され、データベース５１０に格納される値５０３を生成する。データベース５１０はベクトル５０８とベクトル５０９とによって４つのセクションに分割されている。ハッシュ関数５０２を適用した結果は格納エリアをアドレス指定するのに用いられる。この例では、最上位２ビット５０５が記憶空間（すなわち、ベクトル空間）を決定し、この場合には、左上象限内のビット１０と関連付けられた記憶空間である。残りのビット５０６はその記憶空間の下位区画をアドレス指定する。この例では、下位６ビット５０６は、バケット５０７とも呼ばれる６４の下位区画のうちの１つをアドレス指定する。

[0083]ＡＣＲに適したデータベースをさらに分割するプロセスが図６および図７にさらに示されている。図６には、大規模なメディア・キュー・データベースのアドレス指定での使用に備えてデカルト空間を分割する擬似ランダム生成ベクトルをプロットするためのプロセスが図示されている。一実施形態では、ベクトルはモンテカルロ法で生成される。この例では、擬似ランダムプロセスは、十分均一に分布したベクトル集合をプロットしなかった。これは、ベクトル６０３とベクトル６０４との角度差と比較したベクトル６０１とベクトル６０２との角度差を調べれば明らかである。

[0084]図７では、ベクトル７０３とベクトル７０４との角度差と比較したベクトル７０１とベクトル７０２との角度差を調べれば、ベクトルがかなり均一に分布していることがわかる。一実施形態では、ベクトルはモンテカルロ法で生成される。このプロセスは、当業者には理解されるように、自動的に、または単に観察によって定量化し、測定することができる。ランダムなプロジェクション集合が見つかった後に、プロセスを繰り返す必要はない。

[0085]ＡＣＲシステムの記憶探索空間の準備における後続のステップは、代表的なデータサンプルの選択を中心とするようにアドレス空間を正規化することを伴う。図８に、キューデータのデータセット８０１を代表するベクトル空間に集中していないキューデータのデータセット８０１を示す。探索空間におけるこのデータのオフセットは、ＡＣＲシステムにおいて一致するデータを見つける際の精度の低下をもたらす。したがって、図９に示すように、キューデータ９０１がベクトル空間に集中するようにデータセットの値にプロセスが適用される。

[0086]ＡＣＲのためにキューデータのデータセットを最適化する際の別の考慮事項は、データベースの各バケットで見られるデータ密度を考慮することを伴う。例えば、図１０には、理想的なデータ密度を表す適当な数のデータ項目１００１を含むバケット１００２が示されている。対照的に、図１１には、過多なデータ項目１１０１を含むバケット１１０２を有する別のベクトル空間が示されている。いくつかの実施形態によれば、このプロセスがメディア照合エンジンの一部として用いられる場合、過度に満杯のバケットに遭遇すると、結果の発見は遅延されるが、データが廃棄され、探索が続行される。

[0087]図１２は、すべての基準データ（例えば、映像データキュー）を、１アドレス空間セグメント当たり単一バケット１２０１を伴うアドレス指定方式に格納することを伴うシステムの図である。単一バケットの手法は、メディア照合エンジン１２０２が使用するための候補一致データ（例えば、「被疑点」）を捜し出すための探索空間を提供する。メディアソースの数によっては、多数のバケットが過度に満杯になり、ＡＣＲシステムの精度を低下させ、さらにフォールスポジティブな一致が増加し、または一致を見つける機会を逃す結果になる可能性がある。加えて、照合結果生成の遅延をもたらしうるシステム全体の計算負荷が増大し、ある特定の特徴またはビジネスモデルの機能を低下させ、または無効にさえする可能性もある。

[0088]本発明の実施形態は、望ましくないバケット満杯の発生を最小化するようにデータ格納を最適化する複数の方法を提供する。例えば、本発明の一実施形態の図が図１３に示されている。図１３では、複数のバケット１３０１〜１３０３を用いて、この説明例では、メディアタイプまたは領域的考慮事項によって分離されたデータの下位区画が表されている。この複数バケットの手法も、メディア照合エンジン１３０４が使用するための候補一致データを捜し出すための探索空間を提供する。

[0089]より効率的な格納のためにデータを分離する具体例として、図１４に、ビデオ・オン・デマンド（ＶｏＤ）・コンテンツ・フィード１４０１が、キューを抽出し、キューに索引付けし、結果をデータベース１４０７に格納するインジェストプロセッサ１４０４に供給されるシステムを示す。同様に、主要テレビフィード１４０２も、キューを抽出し、キューに索引付けし、結果をデータベース１４０８に格納するインジェストプロセッサ１４０５に供給される。テレビ・イベント・フィード１４０３は、キューを抽出し、キューに索引付けし、結果をデータベース１４０９に格納するインジェストプロセッサ１４０６に供給される。ＶｏＤコンテンツフィード１４０１、主要テレビフィード１４０２、およびテレビ・イベント・フィード１４０３をまとめて、「既知のコンテンツ」と呼ぶ。テレビ・イベント・フィード１４０３は、例えば、イベントの正確で、適時な検出を必要とするターゲット広告を目的として図１４のシステムによって検出されるべきテレビ広告である。同様に、テレビ・イベント・フィード１４０３は、やはり正確さとリアルタイム応答を必要とするプロセスである、ある特定の番組場面中に表示されるべきである関連付けられたインタラクティブコンテンツを有する番組も含む。

[0090]この例では、各種の番組１４０１〜１４０３が、メディアシステム上で表示されている未知のメディア１４１３と並列に（すなわち、同時に）処理される。しかし、他の実施形態では、番組１４０１〜１４０３が未知のメディア１４１３を受信する前に処理される場合もある。未知のメディア１４１３はキュー・クローニング・エンジン１４１４によって複製される。未知のキュー（すなわち、未知のコンテンツ識別子）はその場合、独立したメディア照合エンジン１４１０〜１４１２に提供される。メディア照合エンジン１４１０〜１４１２は、図１の照合エンジン１１２と同様のものとすることができる。メディア照合エンジン１４１０は未知のキューをＶｏＤコンテンツフィード１４０１と関連付けられたキューと比較する。メディア照合エンジン１４１１は未知のキューを主要テレビフィード１４０２と関連付けられたキューと比較する。メディア照合エンジン１４１２は未知のキューをテレビ・イベント・フィード１４０３と関連付けられたキューと比較する。各メディア照合エンジン１４１０〜１４１２は、１つまたは複数の一致（例えば、１バケットあたり１つの一致）を選択し、それらの一致を結果エンジン１４１５に提供する。結果エンジン１４１５は、図１の結果エンジン１２０と同様のものとすることができる。結果エンジン１４１５は、一致を累積、処理し、最終結果１４１６を決定する。最終結果１４１６は、本明細書でさらに説明するように、データベースに格納され、番組センサスに使用され、かつ／またはコンテキスト的ターゲット情報を提供するのに用いられる。

[0091]図１４のシステムによって用いられる方法を、図１５の流れ図を参照して説明する。ステップ１５０１で、少なくとも１種類の既知のメディアコンテンツが受信される（例えば、ＶｏＤコンテンツフィード１４０１、主要テレビフィード１４０２、テレビ・イベント・フィード１４０３など）。ステップ１５０２で、インジェストプロセッサ１４０４〜１４０６によって生成された既知のメディアコンテンツと関連付けられたキューにハッシュ関数が適用され、既知のキューが索引付けされる。ステップ１５０３で、ハッシュ化されたキュー索引はそれぞれのデータベース１４０７〜１４０９に格納される。

[0092]ステップ１５０４で、未知のメディアコンテンツ１４１３が受信され、そのキューがキュー・クローニング・エンジン１４１４によってコピーされ、未知のキューはメディア照合エンジン１４１０〜１４１２に提供される。ステップ１５０６で、収集された被疑点（すなわち、一致）の数は索引のいずれか（例えば、ＶｏＤコンテンツフィード１４０１、主要テレビフィード１４０２、および／またはテレビ・イベント・フィード１４０３と関連付けられたキューの索引）の閾値より大きいかどうかが判定される。収集された被疑点の数が閾値より大きい場合、それらの被疑点はステップ１５０７で廃棄され、方法はステップ１５０５に戻る。ステップ１５０７は、例えば、多数の被疑点が多数のフォールスポジティブを含むために行われる。収集された被疑点の数が閾値以下である場合には、ステップ１５０８で未知のメディア・コンテンツ・キューと既知のメディア・コンテンツ・キューとの間の照合プロセスが実行され、一致する既知のメディアコンテンツの識別が得られる。ステップ１５１０で、一致する既知のメディアコンテンツの識別に基づいて、イベントがトリガされる（例えば、コンテキスト的ターゲット情報の表示）、統計が集計されるなど、結果が実行される。

[0093]ＡＣＲシステムを最適化する別の例が図１６に示されている。図１６では、ＶｏＤコンテンツフィード１６０１、主要テレビフィード１６０２、およびテレビ・イベント・フィード１６０３は、インジェストプロセッサ１６０４〜１６０６によって別々に処理され（例えば、キューされ、索引付けされ、バケットに分離され）、個々のデータベース１６０７〜１６０９に格納される。図１６の実施形態は、データを独立してさらに処理する代わりに、バケットを独立してアドレス指定し、次いでそれらをバケット・コンバイナ・エンジン１６１０で結合する。一実施形態によれば、バケットが過度に満杯である場合、そのバケットは拒絶され、その他のバケットと結合されない。

[0094]メディアシステムによって表示されている未知のメディア１６１３がメディア照合および結果処理エンジン１６１４に提供される。メディア照合および結果処理エンジン１６１４は、例えば、照合結果１６１５を見つけるために、結合されたバケットから、被疑点を抽出し、経路追跡システムを用いて照合プロセスを行う。メディア照合および結果処理エンジン１６１４は、例えば、図１の照合エンジン１１２および結果エンジン１２０と同様のものとすることができる。図１６の実施形態は、各バケットが満杯かどうか調べられ、所定の閾値を上回る場合に拒絶された後でバケットが結合されるという点で有利である。図１６のシステムは、フィード１６０１〜１６０３の独立したデータグループを用いて、精度の向上および処理要件の低減を達成する。

[0095]図１６のシステムによって用いられる方法を、図１７の流れ図を参照して説明する。ステップ１７０１で、少なくとも１種類の既知のメディアコンテンツが受信される（例えば、ＶｏＤコンテンツフィード１６０１、主要テレビフィード１６０２、テレビ・イベント・フィード１６０３など）。ステップ１７０２で、インジェストプロセッサ１６０４〜１６０６によって生成された既知のメディアコンテンツと関連付けられたキューにハッシュ関数が適用され、既知のキューが索引付けされ、バケット化される。ステップ１７０３で、ハッシュ化されたキュー索引はそれぞれのデータベース１６０７〜１６０９に格納される。ステップ１７０４で、索引はバケット・コンバイナ・エンジン１６１０によって結合される。

[0096]ステップ１７０５で、未知のメディアコンテンツ１６１３が受信され、そのキューがコピーされ、未知のキューはメディア照合エンジン１６１４に提供される。ステップ１７０６で、メディア照合エンジン１６１４は結合されたバケットから被疑点を収集し、ステップ１７０７で既知のキューと未知のキューとの間の照合プロセスを実行して一致を識別する。ステップ１７０８で、一致する既知のメディアコンテンツの識別に基づいて、イベントがトリガされる（例えば、コンテキスト的ターゲット情報の表示）、統計が集計されるなど、結果が実行される。

[0097]本発明の別の実施形態が図１８に示されている。図１８では、ＶｏＤコンテンツフィード１８０１、主要テレビフィード１８０２、およびテレビ・イベント・フィード１８０３は、インジェストプロセッサ１８０４〜１８０６によって別々に処理され（例えば、キューされ、索引付けされ、バケットに分離され）、個々のデータベース１８０７〜１８０９に格納される。本実施形態によれば、各索引は、索引タグ付けおよび重み付けエンジン１８１０〜１８１２によって独立してタグ付けされ、重み付けされる。タグ付けされ、重み付けされ、バケット化されたキューは次いで、バケット・コンバイナ・エンジン１８１０を用いてそれぞれのタグと結合される。一実施形態によれば、バケットが過度に満杯である場合、そのバケットは拒絶され、その他のバケットと結合されない。

[0098]メディアシステムによって表示されている未知のメディア１８１３がメディア照合および結果処理エンジン１８１４に提供される。メディア照合および結果処理エンジン１８１４は、例えば、図１の照合エンジン１１２および結果エンジン１２０と同様のものとすることができる。メディア照合および結果処理エンジン１８１４は、例えば、照合結果１８１５を見つけるために、結合されたバケットから、被疑点を抽出し、経路追跡システムを用いて照合プロセスを行う。結果１８１５はさらに、重み付け関数が索引に適用されているという利点を有する。図１８の実施形態は、各バケットが満杯かどうか調べられ、所定の閾値を上回る場合に拒絶された後でバケットが結合されるという点で有利である。図１８のシステムは、フィード１８０１〜１８０３の独立したデータグループを用いることによって、精度の向上および処理要件の低減を達成する。加えて、照合結果のそれぞれの索引に添付されたタグ情報を評価して、照合結果の肯定的な識別時のアクションの優先順位付けを提供することもできる。

[0099]図１８のシステムによって用いられる方法を、図１９の流れ図を参照して説明する。ステップ１９０１で、少なくとも１種類の既知のメディアコンテンツが受信される（例えば、ＶｏＤコンテンツフィード１８０１、主要テレビフィード１８０２、テレビ・イベント・フィード１８０３など）。ステップ１９０２で、インジェストプロセッサ１８０４〜１８０６によって生成された既知のメディアコンテンツと関連付けられたキューにハッシュ関数が適用され、既知のキューが索引付けされ、バケット化される。ステップ１９０３で、ハッシュ化されたキュー索引はそれぞれのデータベース１８０７〜１８０９に格納される。ステップ１９０４で、索引は索引タグ付けおよび重み付けエンジン１８１０〜１８１２によってタグ付けされ、重み付けされる。ステップ１９０５で、索引はバケット・コンバイナ・エンジン１８１０によって結合される。

[0100]ステップ１９０６で、未知のメディアコンテンツ１８１３が受信され、そのキューがコピーされ、未知のキューはメディア照合エンジン１８１４に提供される。ステップ１９０７で、メディア照合エンジン１８１４は結合されたバケットから被疑点を収集し、ステップ１９０８で既知のキューと未知のキューとの間の照合プロセスを実行して一致を識別する。ステップ１９０９で、イベントがトリガされる（例えば、コンテキスト的ターゲット情報の表示）、統計が集計されるなど、一致する既知のメディアコンテンツの識別に基づいて結果が実行される。

[0101]図２０は、本発明の実施形態によるテレビ広告を検出するメディア処理センタ２０００の図である。メディア処理センタ２０００は、例えば、中央サーバである。メディア処理センタ２０００は、テレビインジェスト２００１で参加コンテンツソースから基準テレビ番組情報を受信する。テレビ番組は、例えばテレビデータベース２００２によって、処理され、格納される。番組は、ケーブルと衛星の両方に基づく多チャンネル映像番組配信事業者（ＭＶＰＤ）によっても、インターネットを介してコンテンツを配信するソースによっても提供されることが企図されている。

[0102]このテレビ広告置換の具体例では、図２０のシステムは、置換の候補であるテレビ広告などの特殊イベントを検出するために高速映像セグメント検出器２００５と併用される第２の基準データベース（すなわち、映像セグメントデータベース２００４）を用いる。これらのイベントはイベントマネージャ２００６によって検出され、イベントマネージャ２００６は候補映像セグメント（例えば、テレビ広告）のリストを維持し、映像セグメントが検出されるとテレビシステム２００７に命令を発する。コンテキスト・イベント・マネージャ２００８は、コマンドでテレビシステム２００７によって実行されるべき命令を受信する。

[0103]テレビクライアント２００９は、表示しているテレビ番組から、映像または音声またはその両方のメディアキューを抽出する。メディアキューはネットワークを介して、メディア処理センタ２０００の映像セグメント照合エンジン２００３に送信される。特殊な映像セグメントとの一致が見つかった場合、現在、その映像セグメントを表示しているすべての登録されたテレビに（例えば、コンテキスト・イベント・マネージャ２００８を介してテレビシステム２００７に）メッセージ２０１１が発せられる。メッセージ２０１１を受信すると、コンテキスト・イベント・マネージャ２００８は、置換されるべきであるテレビ広告の以前に供給されたアドレスを、置換時刻および持続期間と共に受信する。コンテキスト・イベント・マネージャ２００８は次いで、供給開始時刻に２０１２で置換広告データベース２０１０をアドレス指定し、置換広告データベース２０１０は次いでアドレス指定された置換広告２０１３をテレビシステム２００７にストリーミングする。イベントマネージャ２００６によって伝えられる置換期間の終了時に、テレビシステム２００７は、置換シーケンスの開始時に再生されていた元のテレビ番組に再度切り替わる。

[0104]図２０のシステムによって用いられる方法を、図２１の流れ図を参照して説明する。ステップ２１０１で、テレビインジェストが受信され、未知の映像セグメントのメディアキューが抽出される。ステップ２１０２で、未知の映像セグメントのキューは映像セグメントデータベース２１０３から抽出された既知の映像セグメントのキューに照らして検査される。ステップ２１０４で、既知の映像セグメントにおいて一致が見つかったかどうかが判定される。一致が見つからなかった場合、方法はループしてステップ２１０２に戻り、未知の映像セグメントは別の既知の映像セグメントと比較される。一致が見つかった場合、方法はステップ２１０６に進む。

[0105]ステップ２１０６で、一致する既知の映像セグメントと関連付けられた映像セグメント識別子が、広告置換識別子のデータベース２１０５に照らして検査される。ステップ２１０７で、広告置換イベント一致があるかどうか（すなわち、映像セグメント識別子がデータベース２１０５内の識別子と一致するかどうか）が判定される。一致が見つからなかった場合、方法はループしてステップ２１０６に戻り、映像セグメント識別子は別の広告置換識別子と比較される。一致が見つかった場合、方法はステップ２１０８に進む。

[0106]ステップ２１０８で、まもなく放送される置換広告の通知がそれぞれのチャンネルに同調されたすべてのアクティブなテレビシステムに送信される。ステップ２１０９で、テレビシステムは置換広告の放送までのカウントダウンタイマを開始する。ステップ２１１０で、タイムアウトが発生しているかどうかが判定される。タイムアウトが発生していない場合、カウントダウンタイマは続行する。タイムアウトが発生している（すなわち、カウントダウンが満了している）場合、置換広告はステップ２１１１で置換広告サーバまたはデータベース２１１２から引き出される。ステップ２１１３で、テレビシステム上で表示されている映像および／または音声は置換広告に切り替わる。ステップ２１１４で、タイムアウトが発生しているかどうかが判定される。タイムアウトが発生していない場合、置換広告は放送を続行する。タイムアウトが発生している（すなわち、置換広告が終了している）場合、ステップ２１１５で映像および／または音声はテレビシステム上の元の番組に再度切り替わる。

[0107]上述のテレビ広告置換のシステムおよび方法のタイミングをさらに理解するために、図２２に、テレビ広告グループ２２０４（「広告ポッド」２２０４とも呼ぶ）を伴う、メディア処理センタ（例えば、メディア処理センタ２０００）で受信される映像セグメントタイムライン２２０１を示す。広告ポッド２２０４は、様々な持続期間の多数の個々のテレビ広告を含む。映像セグメント２２０１はメディア処理センタ（メディア処理センタ２０００）によって処理され、映像照合基準データベースに付加される。２２０２で３０秒の広告が開始し、その後に長短の広告が続き、次いで、２２０３で１５秒の広告が放送される。２２０５で広告ポッド２２０４は終了し、番組が再開する。

[0108]テレビシステム２００７（例えば、一般家庭にある家庭用テレビ）は、メディア処理センタと同じテレビ番組２２０６を受信する。しかし、テレビ配信ネットワークの構造が原因で、メディア処理センタはテレビ番組を、同じテレビ番組がユーザのテレビ（例えば、テレビシステム２００７）で受信される約４〜５秒前に受信する。この遅延を利用すれば、本発明の実施形態によるメディア処理センタには、追加処理の候補となる任意の特定の映像セグメントを検出し、次いで、時刻２２０８で映像セグメントデータベース２００４にイベントが格納されているかどうか判定するのに十分な時間がある。イベントが格納されている場合には、イベントマネージャ２００６は命令を供給し、適切な場合には、コンテキスト・イベント・マネージャ２００８を介して適格なテレビクライアント（例えば、テレビシステム２００７）に追加メディアを提供することができる。コンテキスト・イベント・マネージャ２００８は次いで、これに応答して時刻２２０７で、置換映像セグメント２２０９ｂをアドレス指定し、元々放送されていた映像セグメント２２０９ａの代わりにテレビシステム２００７上で置換映像セグメントを表示させる。置換映像セグメント２２０９ｂは、メディア処理センタの構内の映像サーバからアドレス指定されてもよく、インターネットに接続された任意のサーバからアドレス指定されてもよい。

[0109]本発明のさらに別の実施形態では、映像セグメントの検出は、追加情報をトリガしてテレビクライアント２３０９内で動作しているプロセスから表示させることができる。図２３に、多くのサービスの中から、例えば、映像フレーム２３０９ｂのキューを既知のコンテンツの既知のキューと比較することによってテレビクライアント２３０９上で表示されている映像セグメントを検出するメディア処理センタ２３００を示す。既知のコンテンツはテレビインジェスト２３０１によって受信され、キューが抽出され、テレビデータベース２３０２に格納される。キューは映像セグメント照合エンジン２３０３によって照合される。次いで照合結果がイベントマネージャ２３０６に適用される。

[0110]一致した映像セグメントの存在下でアクションをトリガするイベントが登録されている場合、例えば、コンテキスト・アセット・データベース２３０４によって格納されている、グラフィック・オーバレイ・ウィンドウの形態のメディアを供給するために、コンテキスト・アセット・マネージャ２３０５がアドレス指定される。次いで、グラフィック・オーバレイ・ウィンドウはある特定のタイミング情報と共に、ネットワーク２３１１を介して、映像セグメントを表示していると検出されている各テレビシステム２３０７のコンテキスト・イベント・マネージャ２３０８に送信される。コンテキスト的関連メディアを受信すると、コンテキスト・イベント・マネージャ２３０８はそのメディアを、例えば、表示エリアの一部分を占有し、通常は現在表示されている映像セグメントの話題に関連している情報を含むオーバレイウィンドウとして表示する。

[0111]図２３のシステムによって用いられる方法を、図２４の流れ図を参照して説明する。ステップ２４０１で、テレビインジェストが受信され、未知の映像セグメントのメディアキューが抽出される。ステップ２４０２で、未知の映像セグメントのキューは映像セグメントデータベース２４０３から抽出された既知の映像セグメントのキューに照らして検査される。ステップ２４０４で、既知の映像セグメントにおいて一致が見つかったかどうかが判定される。一致が見つからなかった場合、方法はループしてステップ２４０２に戻り、未知の映像セグメントは別の既知の映像セグメントと比較される。一致が見つかった場合、方法はステップ２４０６に進む。

[0112]ステップ２４０６で、一致する既知の映像セグメントと関連付けられた映像セグメント識別子が、コンテキスト関連付けメディアのデータベース２４０５に照らして検査される。ステップ２４０７で、コンテキスト的関連メディアイベントの一致があるかどうか（すなわち、映像セグメント識別子がデータベース２４０５内の識別子と一致するかどうか）が判定される。一致が見つからなかった場合、方法はループしてステップ２４０６に戻り、映像セグメント識別子は別のコンテキスト的関連イベント識別子と比較される。一致が見つかった場合、方法はステップ２４０８に進む。

[0113]ステップ２４０８で、まもなく放送される映像セグメントの通知がそれぞれのチャンネルに同調されたすべてのアクティブなテレビシステムに送信される。ステップ２４０９で、テレビシステムは映像セグメントの放送までのカウントダウンタイマを開始する。ステップ２４１０で、タイムアウトが発生しているかどうかが判定される。タイムアウトが発生していない場合、カウントダウンタイマは続行する。タイムアウトが発生している（すなわち、カウンドダウンが満了している）場合、ステップ２４１１で、オーバレイ・メディア・データベース２４１２からのオーバレイメディアがトリガされる。ステップ２４１３で、オーバレイウィンドウが開き、元の番組上に表示される。ステップ２４１４で、タイマ終了時に（例えば、３０秒の終了時に）、またはセグメント変更トリガ時に（例えば、映像セグメントの終了および新しい映像セグメントの開始時に）オーバレイウィンドウが閉じる。

[0114]コンテキスト・メディア・オーバレイ・グラフィックのタイミングが図２５に示されている。テレビ番組チャンネル２５０１がメディア処理センタで受信され、映像セグメントが検出され、基準メディアデータベースに格納される。テレビシステム上でローカルに表示するための関連付けられたコンテキスト的関連メディアを有する映像セグメント２５０２が検出されると、２５０６で、同じテレビ番組チャンネル２５０４を表示している（すなわち、２５０１と２５０４とは同じテレビ番組チャンネルを表す）と検出されているテレビシステムに信号が送られる。テレビシステム上での映像セグメント２の開始時に（すなわち、時刻２５０５ａに）、テレビシステムのローカルプロセッサは、メディア処理センタから受信した命令を実行する。命令は、グラフィック・オーバレイ・ウィンドウ（すなわち、補足的テレビコンテンツ２５０７）を、下にある映像番組に関連した追加情報と共に表示する。補足的テレビコンテンツ２５０７は、映像セグメント２ ２５０５ｂの終了まで表示される。

[0115]図２６の映像フレーム表現で、一実施形態による図２５のタイムラインに基づくアクションを示す。図２６では、映像セグメント２６０１が熱帯の島の場面を表示している。映像セグメント２６０２で、コンテンツ番組編成担当者は、視聴者にその熱帯の島への休暇旅行を予約するための情報を受信するよう勧めるオーバレイウィンドウを表示しようとする。上述のように、映像セグメント２６０２の開始時である時刻２５０５に、テレビシステムのプロセッサは、提供された命令に従って、補足情報２６０４と共にグラフィック・オーバレイ・ウィンドウを表示する。セグメント２５０５ｂの終了時に、テレビシステムのプロセッサへの命令により映像オーバレイウィンドウが除去され、遮られていない映像セグメント２６０３が得られる。

[0116]次に、前述した最近傍および経路追跡技術について詳細に説明する。あいまいなキューを用いた映像送信の追跡の一例が与えられているが、この一般概念は、上述の分野など、任意の分野に適用することができる。

[0117]効率的な映像追跡のための方法を提示する。多数の映像セグメントが与えられる場合、システムは、所与のクエリ映像入力が、どんなセグメントから、どんな時間オフセットで取得されるか識別できなければならない。セグメントとオフセットを併せて位置と呼ぶ。この方法を映像追跡と呼ぶのは、この方法は、一時停止、早送り、巻き戻し、他のセグメントへの急な切り替え、および未知のセグメントへの切り替えを効率的に検出し、適応させることができなければならないからである。ライブ映像を追跡する前に、データベースが処理される。視覚的キュー（少数の画素値）が、１秒の一定比率ごとにフレームから取得され、専用のデータ構造に入れられる（これもリアルタイムで行うことができることに留意されたい）。映像追跡は、入力映像からキューを連続して受信し、その現在位置に関する信頼値または推定値の集合を更新することによって行われる。各キューは推定値と合致し、または合致せず、新しい証拠を反映するよう調整される。この映像位置が真である信頼度が十分に高い場合、映像位置は正しい位置であると想定される。ごく少数の可能な「被疑点」位置を追跡することによって、これを効率的に行うことができる。

[0118]映像追跡のための方法を説明しているが、数学的構造を用いてこの方法を説明し、考察する。この導入部の目的は、読者に２つのドメインを変換するのに必要なツールを提供することである。映像信号は連続するフレームで構成される。各フレームは静止画とみなすことができる。すべてのフレームは画素のラスタである。各画素は、その画素の色の赤、緑、および青（ＲＧＢ）の構成に対応する３つの強度値からなる。本稿の用語では、キューとは、フレーム内の画素のサブセットのＲＧＢ値および対応するタイムスタンプのリストである。キュー内の画素数はフレーム内の画素数よりも大幅に小さく、通常は５〜１５の間である。スカラ値の順序付きリストであるため、キュー値は、実際にはベクトルである。このベクトルを点とも呼ぶ。

[0119]これらの点は高次元であり、通常は１５〜１５０の間であるが、２次元の点と仮定することができる。その証拠に各説明図を２次元プロットとして示す。次に、映像の進行とそれに対応するキュー点を考察する。通常、時間がわずかに変化すると画素値もわずかに変化する。画素点はフレーム間でわずかに「移動している」とみなすことができる。フレーム間でのこれらのわずかな移動に従い、キューは、ビーズが曲がったワイヤ上をたどるように空間内の経路をたどる。

[0120]この例えで言うと、映像追跡では空間内のビーズの位置（キュー点）が受け取られ、ビーズがたどるワイヤ（経路）の部分が探される。これは２つの事実により著しく困難になる。第１に、ビーズはワイヤを正確にたどらず、むしろワイヤからある変化する未知の距離を保つ。第２に、ワイヤはすべて相互に絡み合っている。これらの記述はセクション２で正確に述べられている。以下に記載するアルゴリズムは、これを２つの概念的ステップで行う。キューが受け取られると、アルゴリズムは、キュー点に十分に近いすべての既知の経路上のすべての点を探す。これらを被疑点と呼ぶ。これは、ＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｐｏｉｎｔ Ｌｏｃａｔｉｏｎ ｉｎ Ｅｑｕａｌ Ｂａｌｌｓ（等しいボール内での確率論的点位置決定））アルゴリズムを用いて効率的に行われる。これらの被疑点は履歴データ構造に追加され、各被疑点が真の位置を指示している確率が計算される。このステップは、十分に可能性の低い被疑点位置を除去することも含む。この履歴更新プロセスは、一方ではわずかな履歴だけが保持され、他方では確度の高い位置がすっと削除されないようにする。汎用アルゴリズムはアルゴリズム１で与えられ、図２７に例示されている。

[0121]本明細書では、最初にセクション１でＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｐｏｉｎｔ Ｌｏｃａｔｉｏｎ ｉｎ Ｅｑｕａｌ Ｂａｌｌｓ）アルゴリズムについて説明する。ＰＰＬＥＢアルゴリズムは、アルゴリズム１の第５行を効率的に行うために用いられる。この被疑点の探索を迅速に行える能力は、この方法の適用性にとって非常に重要である。後のセクション２では、第６行および第７行を行うための１つの可能な統計モデルについて説明する。説明するモデルは、このセットアップのための自然な選択である。またモデルをどのようにして非常に効率的に使用できるかも示す。

[0122]セクション１ ＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｐｏｉｎｔ Ｌｏｃａｔｉｏｎ ｉｎ Ｅｑｕａｌ Ｂａｌｌｓ）

[0123]以下のセクションでは、ＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｐｏｉｎｔ Ｌｏｃａｔｉｏｎ ｉｎ Ｅｑｕａｌ Ｂａｌｌｓ）を行うための簡単なアルゴリズムについて説明する。従来のＰＬＥＢ（ｐｏｉｎｔ ｌｏｃａｔｉｏｎ ｉｎ ｅｑｕａｌ ｂａｌｌｓ）では、１Ｒ ｄおよび半径ｒの指定されたボールにおける、ｎ個の点の集合ｘから開始する。アルゴリズムは、効率的なデータ構造を生成するためにＯ（ｐｏｌｙ（ｎ））の前処理時間を与えられる。次いで、クエリ点ｘが与えられた場合、アルゴリズムは、

になるようにすべての点ｘを返す必要がある。

になるような点の集合は、幾何学的には、クエリｘを取り囲む半径ｒのボール内に位置する（図２８参照）。この関係をｘ、ｘに近い、またはｘ、およびｘは近傍であるという。

[0124]ＰＰＬＥＢの問題と最近傍探索の問題とは、学界で大きな注目を集めている２つの類似した問題である。実際、これらの問題は計算幾何学の分野で最初に研究されたものであった。周囲の次元が小さいかまたは一定である場合には多くの異なる方法が要求を満たす。これらの方法は、空間を異なるやり方で区分し、各部分を再帰的に探索する。これらの方法には、ＫＤツリー、カバーツリーなどが含まれる。低次元では非常に効率的であるが、周囲の次元が高い場合、これらの方法は非常に不十分にしか機能しない傾向にある。これは「次元の呪い」として知られている。様々な手法が、次元の呪いを克服しつつこの問題を解決しようと試みている。本明細書で用いるアルゴリズムは、アルゴリズムのより単純で高速なバージョンを使用し、局所性鋭敏型ハッシュを利用することができる。

[0125]セクション１．１ 局所性鋭敏型ハッシュ

[0126]局所性鋭敏型ハッシュの方式では、以下になるようなハッシュ関数Ｈのファミリが考案される。

[0127]言葉で説明すると、ｘとｙがｈによって同じ値にマップされる確率は、ｘとｙとが互いに近い場合には著しく高くなる。

[0128]明確にするために、最初に、すべての入力ベクトルが同じ長さｒ’のものであり、ｒ’＞

である単純化されたシナリオを扱う。後者の条件の理由は後で明らかになる。最初に、ｘとｙの間の角度に応じてｘとｙを分離するランダム関数ｕ∈Ｕを定義する。

を単位球Ｓ^ｄ−１から一様に選ばれたランダムベクトルとし、ｕ（ｘ）＝ｓｉｇｎ（

）とする。Ｐｒ_ｕ−Ｕ（ｕ（ｘ））≠ｕ（ｙ））＝０_ｘ，ｙ／πであることを検証することは容易である。さらに、

であるような円上の任意の点ｘ、ｙ、ｘ’、ｙ’について、０_ｘ’，ｙ≦２０_ｘ，ｙが達成される。ｐを定義して、以下の式が用いられる。

[0129]関数Ｈのファミリは、ｕのｔ個の独立したコピーの外積となるように設定され、すなわちｈ（ｘ）＝［ｕ１（ｘ），．．．，ｕ_ｔ（ｘ）］である。直観的には、ｈ（ｘ）＝ｈ（ｙ）の場合、ｘとｙとが互いに近い可能性が高くなるようにしたい。これを定量化する。最初に、予期されるフォールスポジティブ誤りの数ｎ_ｆｐを計算する。これらは、ｈ（ｘ）＝ｈ（ｙ）であるが、｜｜ｘ−ｙ｜｜＞２ｒの場合である。ｎ_ｆｐが１以下である値ｔが見つかる。すなわち、１は間違っているとは予期されていない。
Ｅ［ｎ_ｆｔ］≦ｎ（１−２ｐ）^ｔ≦１
→ｔ≧ｌｏｇ（１／ｎ）／ｌｏｇ（１−２ｐ）

[0130]次に、ｘとｙとが近傍である場合のｈ（ｘ）＝ｈ（ｙ）の確率を計算する。

[0131]ここでは、２ｐ＜１でなければならず、これにはｒ’＞

が必要であることに留意されたい。これはあまり高い成功確率のようには思われないであろう。確かに、１／

は１／２より著しく小さい。次のセクションでは、どのようにしてこの確率を１／２まで上げるかについて説明する。

[0132]セクション１．２ 点探索アルゴリズム

[0133]各関数ｈは、空間内のすべての点をバケットにマップする。ハッシュ関数ｈに関連する点ｘのバケット関数

をＢ_ｈ（ｘ）≡｛ｘ_ｉ｜ｈ（ｘ_ｉ）＝ｈ（ｘ）｝として定義する。維持されるデータ構造は、バケット関数のｍ＝Ｏ（

）個のインスタンス［Ｂｈ_１，…，Ｂｈ_ｍ］である。点ｘを探索すると、関数は

を返す。前セクションによれば、２つの望ましい結果が生じる。

[0134]言い換えると、少なくとも１／２の確率でｘの各近傍が見つかるが、多くの非近傍を見つける可能性は低い。

[0135]セクション１．３ 異なる半径の入力ベクトルの処理

[0136]前セクションでは、同じ長さ、すなわちｒ’のベクトルを探索することのみを扱った。次に、この構造をビルディングブロックとして用いて異なる半径での探索をどのようにサポートできるかについて説明する。図３０に示すように、空間は指数関数的に増加する幅の環に分割される。Ｒ_ｉと表記されている環ｉは、ｘ_ｉ∈［２ｒ（１＋∈）^ｉ，２ｒ（１＋∈）^ｉ＋１］になるようなすべての点ｘ_ｉを含む。これを行うことで２つの目的が達成される。第１に、ｘ_ｉとｘ_ｊが同じ環に属している場合には、ｘ_ｊ／（１＋∈）≦ｘ_ｉ≦ｘ_ｊ（１＋∈）である。第２に、いかなる探索もせいぜい１／∈のそのような環で行うことができる。さらに、データセット内の最大長ベクトルがｒ’である場合には、システム内の環の総数はＯ（ｌｏｇ（ｒ’／ｒ））である。

[0137]セクション２ 経路追跡問題

[0138]経路追跡問題では、空間内の固定経路が、時点列内の粒子の位置と共に与えられる。粒子、キュー、および点という用語は、区別なく用いられる。アルゴリズムは、経路上の粒子の位置を出力する必要がある。これは以下のいくつかの要因、すなわち、粒子は、経路を近似的にたどるにすぎないこと、経路は不連続であり、何度も自己交差する可能性があること、粒子位置と経路位置の両方が（それぞれに異なる）時点列として与えられること、によってより困難になる。

[0139]この問題は、任意の数の経路上の粒子の追跡をシミュレートできることに留意することが重要である。これは、各経路を連結して１本の長い経路にし、結果として得られる位置を個々の経路上の位置として解釈することによって簡単に行われる。

[0140]より正確には、経路Ｐをパラメトリック曲線

とする。曲線パラメータを時間と呼ぶ。既知である経路上の点は任意の時点ｔ_ｉにおいて与えられ、すなわちｎ対の（ｔ_ｉ，Ｐ（ｔ_ｉ））が与えられる。粒子は経路をたどるが、その位置は図３１に示すように異なる時点において与えられる。さらに、ｍ対の（ｔ’_ｊ，ｘ（ｔ’_ｊ））が与えられ、ｘ（ｔ’_ｊ）は時間ｔ’_ｊにおける粒子の位置である。

[0141]セクション２．１ 尤度推定

[0142]粒子は経路を正確にたどらず、経路は何度も自己交差する可能性があるため、粒子が実際にある経路上の位置を確実に識別することは通常は不可能である。したがって、すべての可能な経路位置上で確率分布が計算される。位置確率の確度が著しく高い場合、粒子位置は既知であると想定される。以下のセクションでは、これを効率的に行う方法について説明する。

[0143]粒子が経路をたどっている場合には、粒子のタイムスタンプとＰ上の対応する点のオフセットとの間の時間差は比較的一定になるはずである。言い換えると、ｘ（ｔ’）が経路上で現在オフセットｔにある場合には、ｘ（ｔ’）はＰ（ｔ）に近いはずである。また、τ秒前には、ｘ（ｔ’）はオフセットｔ−τにあったはずである。よって、ｘ（ｔ’−τ）はＰ（ｔ−τ）に近いはずである（粒子が経路と交差しており、ｘ（ｔ’）がＰ（ｔ）に一時的に近い場合、ｘ（ｔ’−τ）とＰ（ｔ−τ）も近い可能性は低いことに留意されたい）。相対オフセットをΔ＝ｔ−ｔ’と定義する。粒子が経路をたどっている限り、相対オフセットΔは変化しないままであることに留意されたい。すなわち、ｘ（ｔ’）はＰ（ｔ’＋Δ）に近い。

[0144]最尤相対オフセットは、以下を計算することによって得られる。

[0145]言葉で説明すると、最も可能性が高い相対オフセットは、粒子の履歴の可能性が最も高いオフセットである。しかし、この方程式は統計モデルなしでは解くことができない。このモデルは、ｘが経路をどれほど厳密にたどるか、ｘが位置間をジャンプする可能性がどれほど高いか、経路および粒子曲線が測定された点間でどれほど滑らかであるか、を定量化しなければならない。

[0146]
セクション２．２ 時間割引ビニング

[0147]次に、尤度関数を推定するための統計モデルについて説明する。このモデルでは、経路からの粒子の逸脱が標準偏差ａｒで正規分布していると仮定する。またこのモデルでは、任意の所与の時点で、粒子が急に別の経路に切り替わるある非ゼロの確率があるとも仮定する。これは、過去の点の時間による指数割引によって明示される。モデル化の観点から合理的な選択であること以外に、このモデルには効率的に更新可能であるという利点もある。ある一定の時間単位１にわたって、尤度関数を、以下のように定義されるｆに比例するように設定する。

[0148]式中、α＜＜１はスケール係数であり、ζ＞０は、粒子が所与の時間単位において経路上のランダムな位置にジャンプする確率である。

[0149]関数ｆの効率的な更新は、以下の簡単な知見を用いて達成することができる。

[0150]さらに、α＜＜１であるため、｜｜ｘ（ｔ’_ｍ）−Ｐ（ｔ_ｉ）｜｜≧ｒの場合、以下の式が生じる。

[0151]これは尤度関数の重要な特性である。というのは、合計の更新を、経路全体にわたってではなくｘ（ｔ’_ｊ）の近傍にわたってのみ行うことができるようになるからである。Ｓで、｜｜ｘ（ｔ’_ｍ）−Ｐ（ｔ_ｉ）｜｜≧ｒになるような（ｔ_ｉ，Ｐ（ｔ_ｉ））の集合を表す。以下の式が生じる。

[0152]これについては以下のアルゴリズム２．２に記載する。項ｆは、負の整数インデックスも受け取る疎ベクトルとして用いられる。集合Ｓは、経路上のｘ（ｔ_ｉ）のすべての近傍の集合であり、ＰＰＬＥＢアルゴリズムを用いて迅速に計算することができる。ｘ（ｔ_ｉ）の近傍の数がある定数ｎ_ｎｅａｒによって制限される場合には、ベクトルｆの非ゼロの数は一定の係数だけ大きいｎ_ｎｅａｒ／ζによって制限されることを検証することは容易である。アルゴリズムの最終段階は、

がある閾値を上回る場合のδの特定の値を出力することである。

[0153]図３２に、３つの連続した点位置とそれらの周りの経路点とを示す。最下点だけでも中間点だけでも経路の正しい部分を十分に識別できなかったはずであることに留意されたい。しかし、これらの点を併せれば十分に識別できる。最上点を追加すれば、粒子が実際に経路の最終（左）曲線のものである確実性が増す。

[0154]図２８では、ｎ個の（灰色の）点の集合が与えられた場合、アルゴリズムはクエリ点（黒）を与えられ、クエリ点から距離ｒ内にある点の集合（円内の点）を返す。従来の設定では、アルゴリズムはそのようなすべての点を返さなければならない。確率的設定では、そのような各点がある一定の確率でのみ返されるはずである。

[0155]図２９に、ｕ（ｘ_１）、ｕ（ｘ_２）、およびｕ（ｘ）の各値を示す。直感的には、関数ｕは、破線がｘ_１とｘ_２との間を通る場合はｘ_１とｘ_２とに異なる値を与え、そうでない場合は同じ値を与える。破線をランダムな方向に通せば、これが起こる確率は、ｘ_１とｘ_２との角度に正比例するようになる。

[0156]図３０に、環Ｒ_ｉが半径２ｒ（１＋∈）^ｉと２ｒ（１＋∈）^ｉ＋１との間にあるように空間を環に分割することによって、環内の任意の２つのベクトルが最大（１＋∈）因子まで同じ長さであり、任意の探索がせいぜい１／∈環において行われることを確実にできることを示す。

[0157]図３１に、自己交差経路とクエリ点（黒）とを示す。粒子位置の履歴がなければ、粒子が経路上のどこにあるか知ることは不可能であることが例示されている。

[0158]図３２に、３つの連続した点位置とそれらの周りの経路点とを示す。ｘ（ｔ_１）だけでもｘ（ｔ_２）だけでも経路の正しい部分を十分に識別できなかったはずであることに留意されたい。しかし、これらの点を併せれば十分に識別できる。ｘ（ｔ_３）を追加すれば、粒子が実際に経路の最終（左）曲線のものである確実性が増す。

[0159]要約すると、本発明の実施形態は、基準データ（すなわち、既知のメディアコンテンツ）を、独立して、並行して、同時に、または組み合わせて探索することができる複数の基準データベースに分割することによってメディア照合および識別プロセスを改善する。探索プロセスの結果は次いで、最終結果を得るために重み付けし、得点をつけることができる。

[0160]本明細書ではテレビ番組のリアルタイム識別に関連して説明されているが、本明細書に記載するシステムおよび方法は、データセットを好ましいサブセットに区分することによって多次元探索を高度化することができる任意の「ビッグデータ」問題に適用されることが企図されている。さらに、本明細書ではおおむね映像データおよびグラフィック表示に関するものとして説明されているが、本明細書に記載するシステムおよび方法は、音声データおよび可聴表示に関しても同様に使用されることが企図されている。例えば、ある特定の実施形態では置換音声データが提供される。

[0161]具体的な要件に応じて大幅な変更がなされてもよい。例えば、カスタマイズされたハードウェアが使用されてもよく、かつ／または特定の要素がハードウェア、ソフトウェア（アプレットなどのポータブルソフトウェアを含む）、もしくはその両方で実装されてもよい。さらに、他のアクセスまたはネットワーク入力装置／出力装置などのコンピューティング機器への接続が用いられてもよい。

[0162]以上の明細書では、本発明の態様がその具体的実施形態に関連して説明されているが、本発明はそれらだけに限定されないことを当業者は理解するであろう。上述の発明の様々な特徴および態様は、個別に用いられても一緒に用いられてもよいさらに、本明細書の幅広い趣旨および範囲から逸脱することなく、本明細書に記載した以外の任意の数の環境および用途において各実施形態を利用することができる。したがって、本明細書および図面は、限定ではなく例示とみなすべきである。

[0163]以上の説明では、例示を目的として、方法を特定の順序で記載した。別の実施形態では、方法は記載した順序と異なる順序で行われてもよいことを理解されたい。また、上述の方法は、ハードウェア構成要素によって行われてもよく、機械実行可能命令でプログラムされた汎用または専用プロセッサや論理回路などの機械に方法を行わせるのに用いられる機械実行可能命令のシーケンスとして具体化されてもよいことも理解されたい。これらの機械実行可能命令は、ＣＤ−ＲＯＭや他の種類の光ディスク、フロッピーディスケット、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カードや光カード、フラッシュメモリ、または電子命令を格納するのに適した他の種類の機械可読媒体など、１つまたは複数の機械可読媒体に格納されていてよい。あるいは、これらの方法は、ハードウェアとソフトウェアの組み合わせによって行われてもよい。

[0164]構成要素がある特定の動作を行うように構成されているものとして記述される場合、そのような構成は、例えば、その動作を行う電子回路または他のハードウェアを設計することによって、その動作を行うプログラマブル電子回路（例えば、マイクロプロセッサや他の適切な電子回路）をプログラムすることによって、またはそれらの任意の組み合わせによって実現することができる。

[0165]本明細書では本出願の例示的実施形態を記載したが、本発明の概念は、それ以外にも様々に具体化され、用いられること、および添付の特許請求の範囲は、先行技術による限定を除いて、そうした変形を含むものと解釈すべきであることを理解されたい。

Claims (22)

1. １または複数のプロセッサと、
   前記１つまたは複数のプロセッサ上で実行されると、前記１つまたは複数のプロセッサに動作を行わせる命令を含む１つまたは複数の非一時的な機械可読記憶媒体であって、前記動作は、
   関連付けられた既知のコンテンツ識別子を有する複数の既知のメディアコンテンツを受信する動作と、
   前記複数の既知のメディアコンテンツを第１の索引と第２の索引とに区分する動作と、
   前記第１の索引を１つまたは複数の第１のバケットに分離する動作であって、前記第１の索引は、前記第１の索引内の前記既知のメディアコンテンツと関連付けられている前記既知のコンテンツ識別子を用いて第１のバケットに分離される、前記第１の索引を１つまたは複数の第１のバケットに分離する前記動作と、
   前記第２の索引を１つまたは複数の第２のバケットに分離する動作であって、前記第２の索引は、前記第２の索引内の前記既知のメディアコンテンツと関連付けられている前記既知のコンテンツ識別子を用いて第２のバケットに分離される、前記第２の索引を１つまたは複数の第２のバケットに分離する前記動作と、
   メディアシステムによって表示されている未知のメディアコンテンツに対応する未知のコンテンツ識別子を受信する動作と、
   前記未知のコンテンツ識別子を求めて前記第１のバケットと前記第２のバケットとを同時に探索する動作と、
   前記第１のバケットまたは前記第２のバケットの中から既知のメディアコンテンツを選択する動作であって、前記選択された既知のメディアコンテンツは前記未知のコンテンツ識別子と関連付けられている、既知のメディアコンテンツを選択する前記動作と、
   前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別する動作と
   を含む、前記１つまたは複数の非一時的な機械可読記憶媒体と
   を含む、システム。
2. 前記複数の既知のメディアコンテンツは、前記既知のメディアコンテンツのパラメータを用いて前記第１の索引と前記第２の索引とに区分される、請求項１に記載のシステム。
3. 前記動作は、
   前記選択された既知のメディアコンテンツと関連付けられたコンテキスト的ターゲットデータを取得する動作と、
   前記コンテキスト的ターゲットデータを表示のために前記メディアシステムに送信する動作と
   をさらに含む、請求項１に記載のシステム。
4. 前記未知のコンテンツ識別子は、前記未知のメディアコンテンツと関連付けられたメタデータを含む、請求項１に記載のシステム。
5. 前記未知のコンテンツ識別子は、前記未知のメディアコンテンツと関連付けられた画素データを含む、請求項１に記載のシステム。
6. 前記未知のコンテンツ識別子は、前記未知のメディアコンテンツと関連付けられた音声データを含む、請求項１に記載のシステム。
7. 前記未知のコンテンツ識別子を求めて前記第１のバケットと前記第２のバケットとを探索する前記動作は、前記第１のバケット内の前記既知のメディアコンテンツと前記第２のバケット内の前記既知のメディアコンテンツとに音声認識技術を適用する動作を含む、請求項６に記載のシステム。
8. 前記動作は、
   前記未知のコンテンツ識別子を用いて前記選択された既知のメディアコンテンツ内のオフセット時間を決定する動作であって、前記オフセット時間は前記メディアシステムによって表示されている前記未知のメディアコンテンツに対応する、前記選択された既知のメディアコンテンツ内のオフセット時間を決定する前記動作
   をさらに含む、請求項１に記載のシステム。
9. 前記第１の索引を１つまたは複数の第１のバケットに分離する前記動作は、前記第１の索引内の前記既知のメディアコンテンツと関連付けられている前記既知のコンテンツ識別子をハッシュ化する動作を含み、前記第２の索引を１つまたは複数の第２のバケットに分離する前記動作は、前記第２の索引内の前記既知のメディアコンテンツと関連付けられている前記既知のコンテンツ識別子をハッシュ化する動作を含む、請求項１に記載のシステム。
10. 前記動作は、
    前記第１の索引内の前記既知のメディアコンテンツと関連付けられている前記ハッシュ化された既知のコンテンツ識別子を正規化する動作と、
    前記第２の索引内の前記既知のメディアコンテンツと関連付けられている前記ハッシュ化された既知のコンテンツ識別子を正規化する動作と
    をさらに含む、請求項９に記載のシステム。
11. 前記動作は、
    前記１つまたは複数の第１のバケットのうちの第１のバケット内の既知のメディアコンテンツの量が閾値を上回っていると判定する動作と、
    前記第１のバケットを廃棄する動作と
    をさらに含む、請求項１に記載のシステム。
12. 関連付けられた既知のコンテンツ識別子を有する複数の既知のメディアコンテンツを受信するステップと、
    前記複数の既知のメディアコンテンツを第１の索引と第２の索引とに区分するステップと、
    前記第１の索引を１つまたは複数の第１のバケットに分離するステップであって、前記第１の索引は、前記第１の索引内の前記既知のメディアコンテンツと関連付けられている前記既知のコンテンツ識別子を用いて第１のバケットに分離される、前記第１の索引を１つまたは複数の第１のバケットに分離する前記ステップと、
    前記第２の索引を１つまたは複数の第２のバケットに分離するステップであって、前記第２の索引は、前記第２の索引内の前記既知のメディアコンテンツと関連付けられている前記既知のコンテンツ識別子を用いて第２のバケットに分離される、前記第２の索引を１つまたは複数の第２のバケットに分離する前記ステップと、
    メディアシステムによって表示されている未知のメディアコンテンツに対応する未知のコンテンツ識別子を受信するステップと、
    前記未知のコンテンツ識別子を求めて前記第１のバケットと前記第２のバケットとを同時に探索するステップと、
    前記第１のバケットまたは前記第２のバケットの中から既知のメディアコンテンツを選択するステップであって、前記選択された既知のメディアコンテンツは前記未知のコンテンツ識別子と関連付けられている、既知のメディアコンテンツを選択する前記ステップと、
    前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別するステップと
    を含む、方法。
13. 前記複数の既知のメディアコンテンツは、前記既知のメディアコンテンツのパラメータを用いて前記第１の索引と前記第２の索引とに区分される、請求項１２に記載の方法。
14. 前記選択された既知のメディアコンテンツと関連付けられたコンテキスト的ターゲットデータを取得するステップと、
    前記コンテキスト的ターゲットデータを表示のために前記メディアシステムに送信するステップと
    をさらに含む、請求項１２に記載の方法。
15. 前記未知のコンテンツ識別子は、前記未知のメディアコンテンツと関連付けられたメタデータを含む、請求項１２に記載の方法。
16. 前記未知のコンテンツ識別子は、前記未知のメディアコンテンツと関連付けられた画素データを含む、請求項１２に記載の方法。
17. 前記未知のコンテンツ識別子は、前記未知のメディアコンテンツと関連付けられた音声データを含む、請求項１２に記載の方法。
18. 前記未知のコンテンツ識別子を求めて前記第１のバケットと前記第２のバケットとを探索するステップは、前記第１のバケット内の前記既知のメディアコンテンツと前記第２のバケット内の前記既知のメディアコンテンツとに音声認識技術を適用するステップを含む、請求項１７に記載の方法。
19. 前記未知のコンテンツ識別子を用いて前記選択された既知のメディアコンテンツ内のオフセット時間を決定するステップであって、前記オフセット時間は前記メディアシステムによって表示されている前記未知のメディアコンテンツに対応する、前記選択された既知のメディアコンテンツ内のオフセット時間を決定する前記ステップ
    をさらに含む、請求項１２に記載の方法。
20. 前記第１の索引を１つまたは複数の第１のバケットに分離する前記ステップは、前記第１の索引内の前記既知のメディアコンテンツと関連付けられている前記既知のコンテンツ識別子をハッシュ化するステップを含み、前記第２の索引を１つまたは複数の第２のバケットに分離する前記ステップは、前記第２の索引内の前記既知のメディアコンテンツと関連付けられている前記既知のコンテンツ識別子をハッシュ化するステップを含む、請求項１２に記載の方法。
21. 前記第１の索引内の前記既知のメディアコンテンツと関連付けられている前記ハッシュ化された既知のコンテンツ識別子を正規化するステップと、
    前記第２の索引内の前記既知のメディアコンテンツと関連付けられている前記ハッシュ化された既知のコンテンツ識別子を正規化するステップと
    をさらに含む、請求項２０に記載の方法。
22. 前記１つまたは複数の第１のバケットのうちの第１のバケット内の既知のメディアコンテンツの量が閾値を上回っていると判定するステップと、
    前記第１のバケットを廃棄するステップと
    をさらに含む、請求項１２に記載の方法。