JP6891170B2 - ステムリソース利用を最適化するための映像セグメントの将来の視聴予測 - Google Patents

Description

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

[0002]本開示は、メディアシステム（例えば、テレビシステム、コンピュータシステム、またはインターネットに接続することのできる他の電子機器）によって表示されるコンテンツの認識に用いられるシステムリソースの管理を改善することに関する。いくつかの例では、コンテンツが将来の期間にメディアシステム上で表示される尤度を決定するための様々な技術およびシステムが提供される。

[0003]メディアシステム（例えば、テレビシステム、コンピュータシステム、またはインターネットに接続することのできる他の電子機器）は、メディアシステムを視聴するユーザのためのコンテンツを表示することができる。いくつかの例では、メディアシステム上に表示されるコンテンツはメディアシステム、およびメディアシステム上で動作する任意のアプリケーションにとって未知のものでありうる。例えば、メディアシステムは、メディアシステムが与えられたものを何でも表示する場合がある。このような例では、メディアシステムにコンテンツの識別が送信されない場合もある。他の例では、リモートシステムがコンテンツを送信してからメディアシステムがコンテンツを受信するまでの間にコンテンツの識別が失われている場合もある。メディアシステム上で何が表示されているか知らないと、メディアシステム上で当該コンテンツと類似した、または関連性のある追加コンテンツを示す機会が困難になる。

[0004]メディアシステム上に表示されたコンテンツを識別する１つの解決策は、メディアシステム上に表示されたコンテンツを基準コンテンツと照合する照合システムを使用することである。しかし、コンテンツを照合できるためには、照合システムは多数の基準コンテンツを含んでいなければならない。加えて、照合システムが多数の基準コンテンツを有していなければならないのみならず、照合システムが適切な基準コンテンツを有している必要もある。したがって、当技術分野では、照合システムのための基準コンテンツを管理する必要がある。

[0005]照合システムにおけるシステムリソースの改善された管理のための装置、コンピュータプログラム製品、および方法が提供される。例えば、各例では、映像セグメントに関連したデータが保持される持続期間を、映像セグメントの識別された評判を考慮に入れたデータに基づいて管理することによって、システムリソース利用の効率を高めることができる。識別された評判は、映像セグメントを見た視聴者の数、映像セグメントの格付け、ソーシャルメディアから導出されたメトリック、または映像セグメントが視聴される尤度を指示することができる任意の他の要因を考慮に入れるアルゴリズムによって決定することができる。

[0006]いくつかの実施態様では、照合システムにおけるシステムリソースの管理を改善するための装置、コンピュータプログラム製品、および方法が提供される。例えば、方法は、メディアセグメントと関連付けられた基準データセットを受信するステップと、基準データセットを基準データベースに格納するステップとを含むことができる。いくつかの例では、基準データセットをサーバによって受信することができる。サーバは、未確認のデータセットを基準データセットと照合することによって未確認のメディアセグメントを識別するように構成することができる。このような例では、未確認のデータセットを未確認のメディアセグメントと関連付けることができる。いくつかの例では、基準データセットは、メディアセグメントのフレームの画素データまたは音声データを含むことができる。

[0007]本方法は、メディアセグメントの評判を指示する評判データを受信するステップをさらに含むことができる。いくつかの例では、評判データは、メディアセグメントの視聴情報、メディアセグメントの格付け情報、またはリモートソース上の投稿メッセージと関連付けられた情報のうちの少なくとも１つまたは複数を含む。このような例では、投稿メッセージをメディアセグメントと関連付けることができる。いくつかの例では、リモートソース上の投稿メッセージと関連付けられた情報は、リモートソース上の投稿メッセージの数、肯定的な投稿メッセージの数、否定的な投稿メッセージの数、投稿メッセージへの肯定的な指示の数、投稿メッセージの報告の数、または投稿メッセージの閲覧の数のうちの少なくとも１つまたは複数を含むことができる。このような例では、投稿メッセージはメディアセグメントと関連付けられる。いくつかの例では、視聴情報は、メディアセグメントがサーバによって識別された回数を含むことができる。

[0008]本方法は、基準データセットの削除時間を決定するステップをさらに含むことができる。いくつかの例では、削除時間は評判データを用いて決定することができる。本方法は、基準データベースから基準データセットを削除するステップをさらに含むことができる。いくつかの例では、基準データセットは、削除時間が満了した後で削除することができる。いくつかの例では、削除時間を決定するステップは、評判データのうちの２つ以上の値の平均値を計算するステップを含むことができる。このような例では、評判データの各値を重みと関連付けることができる。

[0009]いくつかの実施態様では、本方法は、基準データセットが基準データベースから削除されるときに基準データセットをバックアップデータベースに付加するステップをさらに含むことができる。このような実施態様では、サーバは、未確認のデータセットと一致するデータセットを求めて、基準データベースの後にバックアップデータベースを探索するように構成することができる。

[0010]本開示の特徴、態様、および利点は、添付の図面を参照して以下の説明を読めば最も容易に理解されるであろう。添付の図面において、類似した識別番号は図面全体を通して類似した構成要素または部分を表す。

[0011]下記の図に関連して以下で説明例を詳細に説明する。

メディアシステムによって表示されている映像コンテンツを識別するための照合システムの一例のブロック図である。 未知のデータ点を識別する照合システムの一例を示す図である。 映像キャプチャシステムの一例のブロック図である。 ディスプレイによって提示された映像コンテンツを収集するためのシステムの一例のブロック図である。 リソース利用を最適化するための照合システムの一例を示す図である。 基準データセットを保持すべきかどうか判定するのに用いられるデータの相対重みの一例を示す図である。 照合システムにおけるリソース利用を最適化するためのプロセスの一例を示す流れ図である。 点位置とそれらの周りの経路点とを示す図である。 クエリ点から距離内に位置する点の集合を示す図である。 可能な点の値を示す図である。 指数関数的に増加する幅の環に分割された空間を示す図である。 自己交差経路とクエリ点とを示す図である。 ３つの連続した点位置とそれらの周りの経路点とを示す図である。

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

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

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

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

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

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

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

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

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

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

[0035]本明細書に記載するシステムおよび方法は、ＡＣＲシステムにおけるシステムリソース管理の改善を可能にすることができる。例えば、各例では、映像セグメントに関連したデータが保持される持続期間を、映像セグメントの識別された評判を考慮に入れたデータに基づいて管理することによって、システムリソース利用の効率を高めることができる。識別された評判は、映像セグメントを見た視聴者の数、映像セグメントの格付け、ソーシャルメディアから導出されたメトリック、または映像セグメントが視聴される尤度を指示することができる任意の他の要因を考慮に入れるアルゴリズムによって決定することができる。本明細書の説明では映像セグメントに言及するが、音声セグメントを含む他のメディアセグメントも使用することができる。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[0052]図５に、リソース利用を最適化するための照合システム５００の一例を示す。照合システム５００は、図１に示す照合システム１００に類似したものとすることができる。例えば、照合システム５００は、クライアント機器５１０（クライアント機器１０２と同じ、または類似したものとすることができる）を含むことができる。クライアント機器５１０は、リモートソースから映像セグメントのフレームを受信することができる。いくつかの例では、フレームは放送信号の形態とすることができる。他の例では、フレームは、ネットワーク（例えば、インターネット）を用いてパケットとしてクライアント機器５１０に送信されたデータ（例えば、フレームデータ）の形態とすることができる。いくつかの例では、フレームは、クライアント機器５１０によってディスプレイ上でユーザにフレームを提示するのに用いられる画素値を含むことができる。

[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]本明細書では本出願の説明例を記載したが、本発明の概念は、それ以外にも様々に具体化され、用いられること、および添付の特許請求の範囲は、先行技術による限定を除いて、そうした変形を含むものと解釈すべきであることを理解されたい。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
〔１〕
サーバが、メディアセグメントと関連付けられた基準データセットを受信するステップであって、前記サーバは、未確認のデータセットを前記基準データセットと照合することによって未確認のメディアセグメントを識別するように構成されており、前記未確認のデータセットは前記未確認のメディアセグメントと関連付けられている、基準データセットを受信する前記ステップと、
前記基準データセットを基準データベースに格納するステップと、
前記メディアセグメントの評判を指示する評判データを受信するステップであって、前記評判データは、前記メディアセグメントの視聴情報、前記メディアセグメントの格付け情報、またはリモートソース上の投稿メッセージと関連付けられた情報のうちの少なくとも１つまたは複数を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、評判データを受信する前記ステップと、
前記評判データを用いて決定される前記基準データセットの削除時間を決定するステップと、
前記基準データベースから前記基準データセットを削除するステップであって、前記基準データセットは前記削除時間が満了した後で削除される、前記基準データセットを削除する前記ステップと
を含む、コンピュータ実装方法。
〔２〕
前記基準データセットが前記基準データベースから削除されるときに前記基準データセットをバックアップデータベースに付加するステップであって、前記サーバは、前記未確認のデータセットと一致するデータセットを求めて、前記基準データベースの後に前記バックアップデータベースを探索するように構成されている、前記基準データセットをバックアップデータベースに付加する前記ステップ
をさらに含む、〔１〕に記載のコンピュータ実装方法。
〔３〕
前記基準データセットは、前記メディアセグメントのフレームの画素データまたは音声データを含む、〔１〕に記載のコンピュータ実装方法。
〔４〕
削除時間を決定するステップは、前記評判データのうちの２つ以上の値の平均値を計算するステップを含む、〔１〕に記載のコンピュータ実装方法。
〔５〕
前記評判データの各値は重みと関連付けられている、〔４〕に記載のコンピュータ実装方法。
〔６〕
前記リモートソース上の前記投稿メッセージと関連付けられた前記情報は、前記リモートソース上の投稿メッセージの数、肯定的な前記投稿メッセージの数、否定的な前記投稿メッセージの数、前記投稿メッセージへの肯定的な指示の数、前記投稿メッセージの報告の数、または前記投稿メッセージの閲覧の数のうちの少なくとも１つまたは複数を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、〔１〕に記載のコンピュータ実装方法。
〔７〕
前記視聴情報は、前記メディアセグメントが前記サーバによって識別された回数を含む、〔１〕に記載のコンピュータ実装方法。
〔８〕
１または複数のプロセッサと、
前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに動作を行わせる命令を含む非一時的なコンピュータ可読媒体であって、前記動作は、
サーバが、メディアセグメントと関連付けられた基準データセットを受信する動作であって、前記サーバは、未確認のデータセットを前記基準データセットと照合することによって未確認のメディアセグメントを識別するように構成されており、前記未確認のデータセットは前記未確認のメディアセグメントと関連付けられている、基準データセットを受信する前記動作と、
前記基準データセットを基準データベースに格納する動作と、
前記メディアセグメントの評判を指示する評判データを受信する動作であって、前記評判データは、前記メディアセグメントの視聴情報、前記メディアセグメントの格付け情報、またはリモートソース上の投稿メッセージと関連付けられた情報のうちの少なくとも１つまたは複数を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、評判データを受信する前記動作と、
前記評判データを用いて決定される前記基準データセットの削除時間を決定する動作と、
前記基準データベースから前記基準データセットを削除する動作であって、前記基準データセットは前記削除時間が満了した後で削除される、前記基準データセットを削除する前記動作と
を含む、前記非一時的なコンピュータ可読媒体と
を含む、システム。
〔９〕
前記１または複数のプロセッサによって実行されると、前記１または複数のプロセッサに、
前記基準データセットが前記基準データベースから削除されるときに前記基準データセットをバックアップデータベースに付加する動作であって、前記サーバは、前記未確認のデータセットと一致するデータセットを求めて、前記基準データベースの後に前記バックアップデータベースを探索するように構成されている、前記基準データセットをバックアップデータベースに付加する前記動作
を含む動作を行わせる命令をさらに含む、〔８〕に記載のシステム。
〔１０〕
前記基準データセットは、前記メディアセグメントのフレームの画素データまたは音声データを含む、〔８〕に記載のシステム。
〔１１〕
削除時間を決定する動作は、前記評判データのうちの２つ以上の値の平均値を計算する動作を含む、〔８〕に記載のシステム。
〔１２〕
前記評判データの各値は重みと関連付けられている、〔１１〕に記載のシステム。
〔１３〕
前記リモートソース上の前記投稿メッセージと関連付けられた前記情報は、前記リモートソース上の投稿メッセージの数、肯定的な前記投稿メッセージの数、否定的な前記投稿メッセージの数、前記投稿メッセージへの肯定的な指示の数、前記投稿メッセージの報告の数、または前記投稿メッセージの閲覧の数のうちの少なくとも１つまたは複数を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、〔８〕に記載のシステム。
〔１４〕
前記視聴情報は、前記メディアセグメントが前記サーバによって識別された回数を含む、〔８〕に記載のシステム。
〔１５〕
１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
サーバに、メディアセグメントと関連付けられた基準データセットを受信させる命令であって、前記サーバは、未確認のデータセットを前記基準データセットと照合することに
よって未確認のメディアセグメントを識別するように構成されており、前記未確認のデータセットは前記未確認のメディアセグメントと関連付けられている、基準データセットを受信させる前記命令と、
前記基準データセットを基準データベースに格納させる命令と、
前記メディアセグメントの評判を指示する評判データを受信させる命令であって、前記評判データは、前記メディアセグメントの視聴情報、前記メディアセグメントの格付け情報、またはリモートソース上の投稿メッセージと関連付けられた情報のうちの少なくとも１つまたは複数を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、評判データを受信させる前記命令と、
前記評判データを用いて決定される前記基準データセットの削除時間を決定させる命令と、
前記基準データベースから前記基準データセットを削除させる命令であって、前記基準データセットは前記削除時間が満了した後で削除される、前記基準データセットを削除させる前記命令と
を含む、非一時的な機械可読記憶媒体において有形に具体化されたコンピュータプログラム製品。
〔１６〕
前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
前記基準データセットが前記基準データベースから削除されるときに前記基準データセットをバックアップデータベースに付加させる命令であって、前記サーバは、前記未確認のデータセットと一致するデータセットを求めて、前記基準データベースの後に前記バックアップデータベースを探索するように構成されている、前記基準データセットをバックアップデータベースに付加させる前記命令
をさらに含む、〔１５〕に記載のコンピュータプログラム製品。
〔１７〕
前記基準データセットは、前記メディアセグメントのフレームの画素データまたは音声データを含む、〔１５〕に記載のコンピュータプログラム製品。
〔１８〕
削除時間を決定することは、前記評判データのうちの２つ以上の値の平均値を計算することを含む、〔１５〕に記載のコンピュータプログラム製品。
〔１９〕
前記評判データの各値は重みと関連付けられている、〔１８〕に記載のコンピュータプログラム製品。
〔２０〕
前記リモートソース上の前記投稿メッセージと関連付けられた前記情報は、前記リモートソース上の投稿メッセージの数、肯定的な前記投稿メッセージの数、否定的な前記投稿メッセージの数、前記投稿メッセージへの肯定的な指示の数、前記投稿メッセージの報告の数、または前記投稿メッセージの閲覧の数のうちの少なくとも１つまたは複数を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、〔１５〕に記載のコンピュータプログラム製品。

Claims (14)

1. サーバが、メディアセグメントと関連付けられた基準データセットを受信するステップであって、前記サーバは、未確認のデータセットを前記基準データセットと照合することによって未確認のメディアセグメントを識別するように構成されており、前記未確認のデータセットは前記未確認のメディアセグメントと関連付けられている、基準データセットを受信する前記ステップと、
   前記基準データセットを基準データベースに格納するステップと、
   前記メディアセグメントの評判を指示する評判データを受信するステップであって、前記評判データは、前記メディアセグメントの視聴情報、前記メディアセグメントの格付け情報、またはリモートソース上の投稿メッセージと関連付けられた情報のうちの少なくとも１つまたは複数に関連する値を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、評判データを受信する前記ステップと、ここにおいて、前記評判データの各値は重みに関連付けられており、
   前記基準データセットの削除時間を決定するステップと、ここにおいて、前記削除時間は、前記評判データのうちの２つ以上の値の代表値を計算することによって決定され、前記代表値は、前記評判データの２つ以上の値の平均値、算術平均値または中央値の１つであり、
   前記基準データベースから前記基準データセットを削除するステップであって、前記基準データセットは前記削除時間が満了した後で削除される、前記基準データセットを削除する前記ステップと
   を含む、コンピュータ実装方法。
2. 前記基準データセットが前記基準データベースから削除されるときに前記基準データセットをバックアップデータベースに付加するステップであって、前記サーバは、前記未確認のデータセットと一致するデータセットを求めて、前記基準データベースの後に前記バックアップデータベースを探索するように構成されている、前記基準データセットをバックアップデータベースに付加する前記ステップ
   をさらに含む、請求項１に記載のコンピュータ実装方法。
3. 前記基準データセットは、前記メディアセグメントのフレームの画素データまたは音声データを含む、請求項１に記載のコンピュータ実装方法。
4. 前記リモートソース上の前記投稿メッセージと関連付けられた前記情報は、前記リモートソース上の投稿メッセージの数、肯定的な前記投稿メッセージの数、否定的な前記投稿メッセージの数、前記投稿メッセージへの肯定的な指示の数、前記投稿メッセージの報告の数、または前記投稿メッセージの閲覧の数のうちの少なくとも１つまたは複数を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、請求項１に記載のコンピュータ実装方法。
5. 前記視聴情報は、前記メディアセグメントが前記サーバによって識別された回数を含む、請求項１に記載のコンピュータ実装方法。
6. １つまたは複数のプロセッサと、
   前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに動作を行わせる命令を含む非一時的なコンピュータ可読媒体であって、前記動作は、
   サーバが、メディアセグメントと関連付けられた基準データセットを受信する動作であって、前記サーバは、未確認のデータセットを前記基準データセットと照合することによって未確認のメディアセグメントを識別するように構成されており、前記未確認のデータセットは前記未確認のメディアセグメントと関連付けられている、基準データセットを受信する前記動作と、
   前記基準データセットを基準データベースに格納する動作と、
   前記メディアセグメントの評判を指示する評判データを受信する動作であって、前記評判データは、前記メディアセグメントの視聴情報、前記メディアセグメントの格付け情報、またはリモートソース上の投稿メッセージと関連付けられた情報のうちの少なくとも１つまたは複数に関連する値を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、評判データを受信する前記動作と、ここにおいて、前記評判データの各値は重みに関連付けられており、
   前記基準データセットの削除時間を決定する動作と、ここにおいて、前記削除時間は、前記評判データのうちの２つ以上の値の代表値を計算することによって決定され、前記代表値は、前記評判データの２つ以上の値の平均値、算術平均値または中央値の１つであり、
   前記基準データベースから前記基準データセットを削除する動作であって、前記基準データセットは前記削除時間が満了した後で削除される、前記基準データセットを削除する前記動作と
   を含む、前記非一時的なコンピュータ可読媒体と
   を含む、システム。
7. 前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
   前記基準データセットが前記基準データベースから削除されるときに前記基準データセットをバックアップデータベースに付加する動作であって、前記サーバは、前記未確認のデータセットと一致するデータセットを求めて、前記基準データベースの後に前記バックアップデータベースを探索するように構成されている、前記基準データセットをバックアップデータベースに付加する前記動作
   を含む動作を行わせる命令をさらに含む、請求項６に記載のシステム。
8. 前記基準データセットは、前記メディアセグメントのフレームの画素データまたは音声データを含む、請求項６に記載のシステム。
9. 前記リモートソース上の前記投稿メッセージと関連付けられた前記情報は、前記リモートソース上の投稿メッセージの数、肯定的な前記投稿メッセージの数、否定的な前記投稿メッセージの数、前記投稿メッセージへの肯定的な指示の数、前記投稿メッセージの報告の数、または前記投稿メッセージの閲覧の数のうちの少なくとも１つまたは複数を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、請求項６に記載のシステム。
10. 前記視聴情報は、前記メディアセグメントが前記サーバによって識別された回数を含む、請求項６に記載のシステム。
11. １つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
    サーバに、メディアセグメントと関連付けられた基準データセットを受信させる命令であって、前記サーバは、未確認のデータセットを前記基準データセットと照合することに
    よって未確認のメディアセグメントを識別するように構成されており、前記未確認のデータセットは前記未確認のメディアセグメントと関連付けられている、基準データセットを受信させる前記命令と、
    前記基準データセットを基準データベースに格納させる命令と、
    前記メディアセグメントの評判を指示する評判データを受信させる命令であって、前記評判データは、前記メディアセグメントの視聴情報、前記メディアセグメントの格付け情報、またはリモートソース上の投稿メッセージと関連付けられた情報のうちの少なくとも１つまたは複数に関連する値を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、評判データを受信させる前記命令と、ここにおいて、前記評判データの各値は重みに関連付けられており、
    前記基準データセットの削除時間を決定させる命令と、ここにおいて、前記削除時間は、前記評判データのうちの２つ以上の値の代表値を計算することによって決定され、前記代表値は、前記評判データの２つ以上の値の平均値、算術平均値または中央値の１つであり、
    前記基準データベースから前記基準データセットを削除させる命令であって、前記基準データセットは前記削除時間が満了した後で削除される、前記基準データセットを削除させる前記命令と
    を含む、コンピュータ読み取り可能な記憶媒体。
12. 前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数のプロセッサに、
    前記基準データセットが前記基準データベースから削除されるときに前記基準データセットをバックアップデータベースに付加させる命令であって、前記サーバは、前記未確認のデータセットと一致するデータセットを求めて、前記基準データベースの後に前記バックアップデータベースを探索するように構成されている、前記基準データセットをバックアップデータベースに付加させる前記命令
    をさらに含む、請求項１１に記載のコンピュータ読み取り可能な記憶媒体。
13. 前記基準データセットは、前記メディアセグメントのフレームの画素データまたは音声データを含む、請求項１１に記載のコンピュータ読み取り可能な記憶媒体。
14. 前記リモートソース上の前記投稿メッセージと関連付けられた前記情報は、前記リモートソース上の投稿メッセージの数、肯定的な前記投稿メッセージの数、否定的な前記投稿メッセージの数、前記投稿メッセージへの肯定的な指示の数、前記投稿メッセージの報告の数、または前記投稿メッセージの閲覧の数のうちの少なくとも１つまたは複数を含み、前記投稿メッセージは前記メディアセグメントと関連付けられている、請求項１１に記載のコンピュータ読み取り可能な記憶媒体。

Images