(57)【要約】  ある特定の大量のメディア・キュー・データの識別を遅延させることによって自動コンテンツ認識（ＡＣＲ）システムのリソース利用を最適化するためのシステムおよび方法が開示される。メディアの識別の遅延は、例えば、非リアルタイム使用の中でも特に、利用統計の生成や他の非タイムクリティカルなワークフローを目的とするものである。加えて、映像番組の置換、インタラクティブテレビの機会、または他の時間イベントを目的として、メディア・キュー・データのある特定のサブセットのリアルタイム識別も行われる。
2018530081.tif 000002
【特許請求の範囲】
【請求項１】
１または複数のプロセッサと、
前記１つまたは複数のプロセッサ上で実行されると、前記１つまたは複数のプロセッサに動作を行わせる命令を含む１つまたは複数の非一時的な機械可読記憶媒体であって、前記動作は、
関連付けられた既知のコンテンツ識別子を有する複数の既知のメディアコンテンツを受信する動作と、
前記複数の既知のメディアコンテンツと関連付けられた前記既知のコンテンツ識別子を非リアルタイムデータベースに格納する動作と、
関連付けられたコンテキスト的関連データを有する前記複数の既知のメディアコンテンツのサブセットを決定する動作と、
関連付けられたコンテキスト的関連データを有する前記複数の既知のメディアコンテンツの前記サブセットと関連付けられた前記既知のコンテンツ識別子をリアルタイムデータベースに格納する動作と、
メディアシステムによって表示されている未知のメディアコンテンツに対応する未知のコンテンツ識別子を受信する動作と、
前記未知のコンテンツ識別子が、前記リアルタイムデータベース内の前記複数の既知のメディアコンテンツの前記サブセットと関連付けられた既知のコンテンツ識別子に対応するかどうか判定する動作と、
前記リアルタイムデータベースの中から前記対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択する動作と、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応する場合、前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別する動作と、
前記非リアルタイムデータベースの中から、前記未知のコンテンツ識別子に対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択する動作と、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応しない場合、前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別する動作と
を含む、前記１つまたは複数の非一時的な機械可読記憶媒体と
を含む、システム。
【請求項２】
前記動作は、
前記選択された既知のメディアコンテンツと関連付けられた前記コンテキスト的関連データを取得し、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応する場合、前記コンテキスト的関連データの前記メディアシステム上の表示を円滑化する動作
をさらに含む、請求項１に記載のシステム。
【請求項３】
前記動作は、
前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応しない場合、前記選択された既知のメディアコンテンツを用いて統計を計算する動作
をさらに含む、請求項１に記載のシステム。
【請求項４】
前記未知のコンテンツ識別子は、前記メディアシステムによって表示されている前記未知のメディアコンテンツの画素データのサンプルまたは音声データのサンプルのうちの少なくとも１つを含む、請求項１に記載のシステム。
【請求項５】
前記動作は、
前記未知のコンテンツ識別子および前記選択された既知のメディアコンテンツと関連付けられた前記既知のコンテンツ識別子を用いて、前記未知のメディアコンテンツと関連付けられたオフセット時間を決定する動作
をさらに含む、請求項１に記載のシステム。
【請求項６】
前記１つまたは複数のプロセッサおよび前記１つまたは複数の非一時的な機械可読記憶媒体は前記メディアシステムに含まれる、請求項１に記載のシステム。
【請求項７】
前記１つまたは複数のプロセッサおよび前記１つまたは複数の非一時的な機械可読記憶媒体は前記メディアシステムからリモートに位置するサーバに含まれる、請求項１に記載のシステム。
【請求項８】
前記未知のコンテンツ識別子が、前記リアルタイムデータベース内の前記複数の既知のメディアコンテンツの前記サブセットと関連付けられた既知のコンテンツ識別子に対応するかどうか判定する前記動作と、前記リアルタイムデータベースの中から前記対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択する前記動作と、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応する場合、前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別する前記動作とは、リアルタイムで行われる、請求項１に記載のシステム。
【請求項９】
前記非リアルタイムデータベースの中から、前記未知のコンテンツ識別子に対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択する前記動作と、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応しない場合、前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別する前記動作とは、非リアルタイムで行われる、請求項１に記載のシステム。
【請求項１０】
関連付けられた既知のコンテンツ識別子を有する複数の既知のメディアコンテンツを受信するステップと、
前記複数の既知のメディアコンテンツと関連付けられた前記既知のコンテンツ識別子を非リアルタイムデータベースに格納するステップと、
関連付けられたコンテキスト的関連データを有する前記複数の既知のメディアコンテンツのサブセットを決定するステップと、
関連付けられたコンテキスト的関連データを有する前記複数の既知のメディアコンテンツの前記サブセットと関連付けられた前記既知のコンテンツ識別子をリアルタイムデータベースに格納するステップと、
メディアシステムによって表示されている未知のメディアコンテンツに対応する未知のコンテンツ識別子を受信するステップと、
前記未知のコンテンツ識別子が、前記リアルタイムデータベース内の前記複数の既知のメディアコンテンツの前記サブセットと関連付けられた既知のコンテンツ識別子に対応するかどうか判定するステップと、
前記リアルタイムデータベースの中から前記対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択するステップと、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応する場合、前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別するステップと、
前記非リアルタイムデータベースの中から、前記未知のコンテンツ識別子に対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択するステップと、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応しない場合、前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別するステップと
を含む、方法。
【請求項１１】
前記選択された既知のメディアコンテンツと関連付けられた前記コンテキスト的関連データを取得するステップと、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応する場合、前記コンテキスト的関連データの前記メディアシステム上の表示を円滑化するステップと
をさらに含む、請求項１０に記載の方法。
【請求項１２】
前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応しない場合、前記選択された既知のメディアコンテンツを用いて統計を計算するステップ
をさらに含む、請求項１０に記載の方法。
【請求項１３】
前記未知のコンテンツ識別子は、前記メディアシステムによって表示されている前記未知のメディアコンテンツの画素データのサンプルまたは音声データのサンプルのうちの少なくとも１つを含む、請求項１０に記載の方法。
【請求項１４】
前記ステップは、
前記未知のコンテンツ識別子および前記選択された既知のメディアコンテンツと関連付けられた前記既知のコンテンツ識別子を用いて、前記未知のメディアコンテンツと関連付けられたオフセット時間を決定するステップ
をさらに含む、請求項１０に記載の方法。
【請求項１５】
前記方法は、前記メディアシステムに含まれる１つまたは複数のプロセッサおよび１つまたは複数の非一時的な機械可読記憶媒体で実施される、請求項１０に記載の方法。
【請求項１６】
前記方法は、前記メディアシステムからリモートに位置するサーバに含まれる１つまたは複数のプロセッサおよび１つまたは複数の非一時的な機械可読記憶媒体で実施される、請求項１０に記載の方法。
【請求項１７】
前記未知のコンテンツ識別子が、前記リアルタイムデータベース内の前記複数の既知のメディアコンテンツのサブセットと関連付けられた既知のコンテンツ識別子に対応するかどうか判定する前記ステップと、前記リアルタイムデータベースの中から前記対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択する前記ステップと、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応する場合、前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別する前記ステップとは、リアルタイムで行われる、請求項１０に記載の方法。
【請求項１８】
前記非リアルタイムデータベースの中から、前記未知のコンテンツ識別子に対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択する前記ステップと、前記未知のコンテンツ識別子が前記リアルタイムデータベース内の既知のコンテンツ識別子に対応しない場合、前記未知のメディアコンテンツを前記選択された既知のメディアコンテンツとして識別する前記ステップとは、非リアルタイムで行われる、請求項１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
[0001]本出願は、参照によりその開示全体が本明細書に組み入れられる、２０１５年７月１６日に出願された米国仮特許出願第６２／１９３３４５号の恩典を主張するものである。
【０００２】
[0002]本出願は、２００９年５月２９日に出願された米国仮特許出願第６１／１８２３３４号、および２００９年１２月２９日に出願された米国仮特許出願第６１／２９０７１４号の利益を主張するものである、２０１０年５月２７日に出願された米国特許出願第１２／７８８７２１号、現在の米国特許第８５９５７８１（Ｂ２）号の継続出願である、２０１３年１１月２５日に出願された米国特許出願第１４／０８９００３号、現在の米国特許第８８９８７１４号の継続出願である、２０１４年１１月２４日に出願された米国特許出願第１４／５５１９３３号に関連するものであり、これらの出願の開示は、参照によりその全体が本明細書に組み入れられる。
【０００３】
[0003]本開示は、メディアシステム（例えば、テレビシステム、コンピュータシステムまたはインターネットに接続することができる他の電子機器）によって表示されたコンテンツの認識に用いられるシステムリソースの管理を改善することに関する。さらに、本開示は、コンテンツを効果的、効率的に識別することにも関する。例えば、自動コンテンツ認識（ＡＣＲ）テレビ・モニタリング・システムにおける作業負荷管理を改善するための様々な技術およびシステムが提供される。
【背景技術】
【０００４】
[0004]光ファイバおよびデジタル伝送技術の進歩により、テレビ業界は、チャンネル容量を急速に増加させ、ある程度のインタラクティブ・テレビ（ＩＴＶ）・サービスを提供することができるようになっており、これは主にテレビ業界が、各チャンネルのデータ容量の増加を、スマートＴＶおよび／またはセット・トップ・ボックス（ＳＴＢ）または他の機器の形態のコンピュータの処理能力と組み合わせたことによるものである。
【０００５】
[0005]ＩＴＶの技術は、ＴＶシステムが、ワールド・ワイド・ウェブの態様に近似したやり方で双方向情報配信機構として機能することを可能にしようとして開発されてきた。ＩＴＶの特徴は、ユーザが宣伝された製品やサービスを注文したり、ゲーム番組で出場者と対戦したりすることを可能にするなど、様々なマーケティング機能、娯楽機能、および教育機能に適応する。多くの場合、インタラクティブ機能は、ＴＶ放送のために書かれたインタラクティブプログラムを実行するＳＴＢによって制御される。インタラクティブ機能は、多くの場合、ＴＶの画面上に表示され、ユーザがＴＶのリモートコントローラまたはキーボードを介して選択できるアイコンまたはメニューを含む。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
[0006]１つの技法によれば、インタラクティブコンテンツを放送ストリーム（本明細書では「チャンネル／ネットワークフィード」とも呼ぶ）に組み込むことができる。「放送ストリーム」という用語は、放送信号の伝送方法、例えば、アンテナによるものか、衛星によるものか、ケーブルによるものか、それとも任意の他の信号伝送方法によるものかにかかわらず、テレビによって受信される放送信号を指す。インタラクティブコンテンツを放送ストリームに透過的に組み込む１つの方法は、特定の番組の放送ストリームへの１つまたは複数の「トリガ」の挿入である。前記トリガが挿入されている番組コンテンツを、強化型番組コンテンツまたは強化型ＴＶ番組もしくは映像信号と呼ぶこともある。トリガは、ＳＴＢまたはスマートＴＶ内のプロセッサにインタラクティブコンテンツが利用可能であることを通知するのに用いられる。トリガは、利用可能なコンテンツ、およびコンテンツのメモリ位置に関する情報を含むことができる。またトリガは、ユーザに、何らかのアクションを行い、または複数のオプションの中から選択するよう促す、画面上、例えば、画面の下部に表示されるユーザが知覚可能なテキストを含むこともできる。
【０００７】
[0007]接続ＴＶは、視聴者のホームネットワーク（有線または無線）を介してインターネットに接続されたＴＶである。接続ＴＶは、ＧｏｏｇｌｅのＡｎｄｒｏｉｄなどのアプリケーションプラットフォームや、インタラクティブなスマートフォンやタブレット様のアプリケーションが前記ＴＶ上で動作することを可能にする、他の専用プラットフォームを実行することができる。このような接続ＴＶプラットフォームの基本的な共通の特徴は、（１）インターネットへの接続、および（２）ソフトウェアアプリケーションからのグラフィックがＴＶディスプレイ上に重ね合わされ、またはＴＶディスプレイ全体を占有するソフトウェアアプリケーションを実行できることである。
【０００８】
[0008]現在のところ、視聴者に、当該視聴者のためにカスタマイズされた番組またはコマーシャルの機会を提供するという観点から、視聴者がたった今何を見ているか、視聴者が誰であるかに関するメタデータにアクセスできるＴＶは（接続型であれそれ以外であれ）ほとんどない。コンテンツ提供に関する若干の情報がコンテンツ配信パイプラインにおいてビットおよび断片として利用可能であるが、旧来の配信システム上で番組が画面に到達する時までに、映像および音声以外のすべての情報は失われている。
【０００９】
[0009]このような識別情報を、圧縮および伸張に耐えうるような方法で、音声部分または映像部分上のウォーターマークとして娯楽およびコマーシャルコンテンツにおいて符号化しようとする試みがなされているが、このような技術はまだ一般に普及していない。たとえそれらのコードが標準化され、容易に利用可能であり、信頼できるようになったとしても、ある特定のＴＶシステム上で表示されている番組の正確な点を何分の１秒以内の分解能で識別できる能力を有するとは予測されていない。
【００１０】
[0010]その結果、旧来のＴＶ信号配信システムでは、ＴＶセットには、視聴者が現時点においてどんなチャンネルまたは番組を見ているかも、番組が何に関するものかも「わからない」。画面上で視聴者に見えているチャンネルおよび番組は、現在は、往々にして不完全な情報からＳＴＢ上で移植されている。この障壁は、ＴＶコンテンツ配信業界の根本的な構造の結果である。
【００１１】
[0011]本明細書に記載する関連アプリケーションは、現在視聴されているコンテンツをほぼリアルタイムで識別するためのシステムおよび方法に関するものであり、よって、どの時点で、ある特定のコンテキスト的に関連性のある追加的な情報、広告、またはインタラクティブ機会を番組プロバイダが利用できるかを識別することができる。このようなリアルタイムアプリケーションに加えて、これらのアプリケーションは、以前は不可能であった精度および粒度で視聴パターンに関する統計を生成できるシステムおよび方法も教示する。しかし、広告モジュールを置換することや、視聴者に追加的な番組もしくはコマーシャルの提供機会を提供することはほぼリアルタイムで行われる必要があるが、ある特定の番組を識別し、特定のチャンネルの番組またはシステムによって挿入された置換番組の視聴および利用統計を生成することは、さほど時間的制約を受けない。
【００１２】
[0012]よって、本発明の実施形態の目的は、さほどタイムクリティカルではない機能をオフピーク期間に自動的に実行することによってシステムリソース利用の効率を最大化することである。本発明の実施形態は、一般に、テレビシステムの画面上に表示された映像セグメントを識別するためのシステムおよび方法と、そのような映像セグメント識別に基づいてテレビシステムにコンテキスト的ターゲットコンテンツを提供するためのシステムおよび方法とに関するものである。本明細書で用いる場合、「メディアシステム」という用語は、テレビシステム、音声システムなどを含むが、それらに限定されない。本明細書で用いる場合、「テレビシステム」という用語は、ウェブＴＶや接続ＴＶ（「スマートＴＶ」としても知られている）などのテレビ、およびセット・トップ・ボックス（ＳＴＢ）、デジタル・ビデオ・ディスク（ＤＶＤ）・プレーヤ、デジタル・ビデオ・レコーダ（ＤＶＲ）などの、前記テレビに組み込まれた、または前記テレビと同じ場所に置かれる装置を含むが、それらに限定されない。本明細書で用いる場合、「テレビ信号」という用語は、テレビ番組またはコマーシャルの画像成分および音声成分を提供するように（メタデータありまたはなしで）合わせて放送される映像および音声データを表す信号を含む。本明細書で用いる場合、「メタデータ」という用語は、テレビ信号中の映像／音声データに関する、または関連したデータを意味する。
【課題を解決するための手段】
【００１３】
[0013]本発明の実施形態は、どの映像セグメントがテレビシステムの画面上で表示されているか識別するためのシステムおよび方法を対象とする。特に、結果として得られる、現在視聴されている映像セグメントを識別するデータを使用して、ＴＶ視聴者の反応（番組を番組の始めから再開するよう要求しているなど）を取り込み、適切に応答することを可能にし、または関連性のあるコンテンツプロバイダおよび広告主が供給する情報もしくはターゲットを絞ったコマーシャルメッセージの提供をトリガすることができ、よって、ケーブルシステムのネットワーク上で配信される従来のリアルタイム放送環境から、インターネット接続上で配信されるカスタム構成されたビデオオンデマンド（ＶｏＤ）製品へ視聴者のシームレスな切り替えが可能になる。
【００１４】
[0014]いくつかの実施形態によれば、間隔（例えば１００ミリ秒）を置いて、画面上に表示されている画素データ（または関連付けられた音声データ）のサブセットをサンプリングし、次いで、コンテンツデータベースにおいて類似した画素（または音声）データを見つけることによって映像セグメントが識別される。いくつかの実施形態によれば、映像セグメントと関連付けられた音声データまたは画像データを抽出し、次いで、コンテンツデータベースにおいて類似した音声データまたは画像データを見つけることによって映像セグメントが識別される。いくつかの実施形態によれば、既知の自動音声認識技術を用いて映像セグメントと関連付けられた音声データを処理することによって映像セグメントが識別される。いくつかの実施形態によれば、映像セグメントと関連付けられたメタデータを処理することによって映像セグメントが識別される。本明細書で用いる場合、「キュー」または「コンテンツ識別子」は、画素データ、音声データ、画像データ、メタデータ、またはそれらのサンプルもしくはサブセットに対応する。
【００１５】
[0015]本発明の実施形態は、コンテキスト的ターゲットコンテンツをインタラクティブ・テレビ・システムに提供するためのシステムおよび方法をさらに対象とする。コンテキストターゲティングは、表示されている映像セグメントの識別のみならず、現在表示されている映像セグメントの特定の部分の再生時間またはオフセット時間に関する決定にも基づくものである。「再生時間」および「オフセット時間」という用語は、本明細書では、特定のテレビ番組またはコマーシャルの開始時間など、固定された時点からのオフセットである時間を指すのに区別なく用いられる。
【００１６】
[0016]より具体的には、本発明の実施形態は、接続ＴＶ上で何が再生されているか検出し、再生されているものの主題を推論し、それに応じて視聴者とインタラクションすることができる技術を含む。特に、本明細書で開示する実施形態は、インタラクティブＴＶがインターネットを介してサーバから機能を厳密に引き出す限られた能力を克服し、それによって、コンテンツのＶｏＤバージョンへの即時のアクセスを提供できる能力、および利用できる場合に、ユーザにコンテンツの高解像度または３Ｄフォーマットを視聴するオプションを、最初から再生、早送り、一時停止、および巻き戻しできる追加機能と共に提供できる能力を含む新規のビジネスモデルを可能にする。また本発明の実施形態は、現在のＶｏＤ番組に含まれる一部または全部の広告メッセージを、例示にすぎず、それだけに限らないが、視聴者の位置、人口統計群、もしくは買い物履歴に関連してカスタマイズさせることを可能にし、またはある特定のビジネスモデルをサポートするためにコマーシャルの数もしくは長さを削減させ、もしくは完全に削除させることも可能にする。
【００１７】
[0017]いくつかの実施形態によれば、画面上に表示されている画素データ（または関連付けられた音声データ）のサブセットをサンプリングし、次いで、コンテンツデータベースにおいて類似した画素（または音声）データを見つけることによって映像セグメントが識別され、オフセット時間が決定される。いくつかの実施形態によれば、映像セグメントと関連付けられた音声データまたは画像データを抽出し、次いで、コンテンツデータベースにおいて類似した音声データまたは画像データを見つけることによって映像セグメントが識別され、オフセット時間が決定される。いくつかの実施形態によれば、既知の自動音声認識技術を用いて映像セグメントと関連付けられた音声データを処理することによって映像セグメントが識別され、オフセット時間が決定される。いくつかの実施形態によれば、映像セグメントと関連付けられたメタデータを処理することによって映像セグメントが識別され、オフセット時間が決定される。
【００１８】
[0018]本明細書でより詳細に説明されるように、接続ＴＶ上で視聴されている映像セグメントを識別し、任意選択で、オフセット時間を決定するためのシステムは、接続ＴＶをその構成要素とするテレビシステムに位置することができる。いくつかの実施形態によれば、映像セグメントを識別するためのシステムのある部分はテレビシステムに位置し、別の部分はインターネットを介してテレビシステムに接続されたサーバに位置する。
【００１９】
[0019]本発明のいくつかの実施形態では、システムは、累積メディアキューの非リアルタイム検査を、他の処理作業負荷が比較的軽い非ゴールデンタイムなどのより経済的に有利な時間に処理するようにスケジュールすることができる。前記検査の結果は、典型的には、利用データ統計を生成するものであり、よって、クライアントＴＶ上でコンテキスト的関連イベントをトリガするのに必要な処理ほど時間依存的ではない。
【００２０】
[0020]本発明のいくつかの実施形態によれば、方法が提供される。本方法は、複数の既知のメディアコンテンツを受信するステップを含む。複数の既知のメディアコンテンツは、関連付けられた既知のコンテンツ識別子（本明細書では「キュー」とも呼ぶ）を有する。本方法は、複数の既知のメディアコンテンツと関連付けられた既知のコンテンツ識別子を非リアルタイムデータベースに格納するステップをさらに含む。本方法は、関連付けられたコンテキスト的関連データを有する複数の既知のメディアコンテンツのサブセットを決定するステップをさらに含む。本方法は、関連付けられたコンテキスト的関連データを有する複数の既知のメディアコンテンツのサブセットと関連付けられた既知のコンテンツ識別子をリアルタイムデータベースに格納するステップをさらに含む。本方法は、メディアシステムによって表示されている未知のメディアコンテンツに対応する未知のコンテンツ識別子を受信するステップをさらに含む。本方法は、未知のコンテンツ識別子が、リアルタイムデータベース内の複数の既知のメディアコンテンツのサブセットと関連付けられた既知のコンテンツ識別子に対応するかどうか判定するステップをさらに含む。本方法は、リアルタイムデータベースの中から対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択するステップと、未知のコンテンツ識別子がリアルタイムデータベース内の既知のコンテンツ識別子に対応する場合、未知のメディアコンテンツを選択された既知のメディアコンテンツとして識別するステップとをさらに含む。本方法は、非リアルタイムデータベースの中から、未知のコンテンツ識別子に対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択するステップと、未知のコンテンツ識別子がリアルタイムデータベース内の既知のコンテンツ識別子に対応しない場合、未知のメディアコンテンツを選択された既知のメディアコンテンツとして識別するステップとをさらに含む。
【００２１】
[0021]いくつかの実施形態では、本方法は、選択された既知のメディアコンテンツと関連付けられたコンテキスト的関連データを取得するステップと、未知のコンテンツ識別子がリアルタイムデータベース内の既知のコンテンツ識別子に対応する場合、コンテキスト的関連データのメディアシステム上の表示を円滑化するステップとをさらに含む。いくつかの実施形態では、本方法は、未知のコンテンツ識別子がリアルタイムデータベース内の既知のコンテンツ識別子に対応しない場合、選択された既知のメディアコンテンツを用いて統計を計算するステップをさらに含む。いくつかの実施形態では、未知のコンテンツ識別子は、メディアシステムによって表示されている未知のメディアコンテンツの画素データのサンプルまたは音声データのサンプルのうちの少なくとも１つを含む。いくつかの実施形態では、本方法は、未知のコンテンツ識別子および選択された既知のメディアコンテンツと関連付けられた既知のコンテンツ識別子を用いて、未知のメディアコンテンツと関連付けられたオフセット時間を決定するステップをさらに含む。
【００２２】
[0022]いくつかの実施形態では、本方法は、メディアシステムに含まれる１つまたは複数のプロセッサおよび１つまたは複数の非一時的な機械可読記憶媒体で実施される。いくつかの実施形態では、本方法は、メディアシステムからリモートに位置するサーバに含まれる１つまたは複数のプロセッサおよび１つまたは複数の非一時的な機械可読記憶媒体で実施される。いくつかの実施形態では、未知のコンテンツ識別子が、リアルタイムデータベース内の複数の既知のメディアコンテンツのサブセットと関連付けられた既知のコンテンツ識別子に対応するかどうか判定するステップと、リアルタイムデータベースの中から対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択するステップと、未知のコンテンツ識別子がリアルタイムデータベース内の既知のコンテンツ識別子に対応する場合、未知のメディアコンテンツを選択された既知のメディアコンテンツとして識別するステップとは、リアルタイムで行われる。いくつかの実施形態では、非リアルタイムデータベースの中から、未知のコンテンツ識別子に対応する既知のコンテンツ識別子と関連付けられた既知のメディアコンテンツを選択するステップと、未知のコンテンツ識別子がリアルタイムデータベース内の既知のコンテンツ識別子に対応しない場合、未知のメディアコンテンツを選択された既知のメディアコンテンツとして識別するステップとは、非リアルタイムで行われる。
【００２３】
[0023]本発明のいくつかの実施形態によれば、システムが提供される。本システムは、１つまたは複数のプロセッサを含む。本システムは、１つまたは複数のプロセッサ上で実行されると、１つまたは複数のプロセッサに、上記の方法のステップを含む動作を行わせる命令を含む非一時的な機械可読記憶媒体をさらに含む。
【００２４】
[0024]本発明のいくつかの実施形態によれば、コンピューティング機器の非一時的な機械可読記憶媒体において有形に具体化されたコンピュータプログラム製品が提供される。本コンピュータプログラム製品は、１つまたは複数のデータプロセッサに、上記の方法に記載されたステップを行わせるように構成された命令を含む。
【００２５】
[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]この例えで言うと、映像追跡では空間内のビーズの位置（キュー点）が受け取られ、ビーズがたどるワイヤ（経路）の部分が探される。これは２つの事実により著しく困難になる。第１に、ビーズはワイヤを正確にたどらず、むしろワイヤからある変化する未知の距離を保つ。第２に、ワイヤはすべて相互に絡み合っている。これらの記述はセクション２で正確に述べられている。以下に記載するアルゴリズムは、これを２つの概念的ステップで行う。キューが受け取られると、アルゴリズムはキュー点に十分に近いすべての既知の経路上のすべての点を探す。これらを被疑点と呼ぶ。これは、ＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｐｏｉｎｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  Ｅｑｕａｌ  Ｂａｌｌｓ（等しいボール内での確率論的点位置決定））アルゴリズムを用いて効率的に行われる。これらの被疑点は履歴データ構造に追加され、各被疑点が真の位置を指示している確率が計算される。このステップは、十分に可能性の低い被疑点位置を除去することも含む。この履歴更新プロセスは、一方ではわずかな履歴だけが保持され、他方では確度の高い位置がすっと削除されないようにする。汎用アルゴリズムはアルゴリズム１で与えられ、図１０に例示されている。
【表１】
2018530081.tif 000003
【００８７】
[0101]本明細書では、最初にセクション１でＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｐｏｉｎｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  Ｅｑｕａｌ  Ｂａｌｌｓ）アルゴリズムについて説明する。ＰＰＬＥＢアルゴリズムは、アルゴリズム１の第５行を効率的に行うために用いられる。この被疑点の探索を迅速に行える能力は、この方法の適用性にとって非常に重要である。後のセクション２では、第６行および第７行を行うための１つの可能な統計モデルについて説明する。説明するモデルは、このセットアップのための自然な選択である。またモデルをどのようにして非常に効率的に使用できるかも示す。
【００８８】
[0102]セクション１  ＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｐｏｉｎｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  Ｅｑｕａｌ  Ｂａｌｌｓ）
【００８９】
[0103]以下のセクションでは、ＰＰＬＥＢ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｐｏｉｎｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  Ｅｑｕａｌ  Ｂａｌｌｓ）を行うための簡単なアルゴリズムについて説明する。従来のＰＬＥＢ（ｐｏｉｎｔ  ｌｏｃａｔｉｏｎ  ｉｎ  ｅｑｕａｌ  ｂａｌｌｓ）では、１Ｒ  ｄおよび半径ｒの指定されたボールにおける、ｎ個の点ｘの集合から開始する。アルゴリズムは、効率的なデータ構造を生成するためにＯ（ｐｏｌｙ（ｎ））の前処理時間を与えられる。次いで、クエリ点ｘが与えられた場合、アルゴリズムは、
【数１】
2018530081.tif 000004
になるようにすべての点ｘを返す必要がある。
【数２】
2018530081.tif 000005
になるような点の集合は、幾何学的には、クエリｘを取り囲む半径ｒのボール内に位置する（図１１参照）。この関係をｘ、ｘに近い、またはｘ、およびｘは近傍であるという。
【００９０】
[0104]ＰＰＬＥＢの問題と最近傍探索の問題とは、学界で大きな注目を集めている２つの類似した問題である。実際、これらの問題は計算幾何学の分野で最初に研究されたものであった。周囲の次元が小さいかまたは一定である場合には多くの異なる方法が要求を満たす。これらの方法は、空間を異なるやり方で区分し、各部分を再帰的に探索する。これらの方法には、ＫＤツリー、カバーツリーなどが含まれる。低次元では非常に効率的であるが、周囲の次元が高い場合、これらの方法は非常に不十分にしか機能しない傾向にある。これは「次元の呪い」として知られている。様々な手法が、次元の呪いを克服しつつこの問題を解決しようと試みている。本明細書で用いるアルゴリズムは、アルゴリズムのより単純で高速なバージョンを使用し、局所性鋭敏型ハッシュを利用することができる。
【００９１】
[0105]セクション１．１  局所性鋭敏型ハッシュ
【００９２】
[0106]局所性鋭敏型ハッシュの方式では、以下になるようなハッシュ関数Ｈのファミリが考案される。
【数３】
2018530081.tif 000006
【００９３】
[0107]言葉で説明すると、ｘとｙがｈによって同じ値にマップされる確率は、ｘとｙとが互いに近い場合には著しく高くなる。
【００９４】
[0108]明確にするために、最初に、すべての入力ベクトルが同じ長さｒ’のものであり、ｒ’＞
【数４】
2018530081.tif 000007
である単純化されたシナリオを扱う。後者の条件の理由は後で明らかになる。最初に、ｘとｙの間の角度に応じてｘとｙを分離するランダム関数ｕ∈Ｕを定義する。
【数５】
2018530081.tif 000008
を単位球Ｓｄ−１から一様に選ばれたランダムベクトルとし、ｕ（ｘ）＝ｓｉｇｎ（
【数６】
2018530081.tif 000009
）とする。Ｐｒｕ−Ｕ（ｕ（ｘ））≠ｕ（ｙ））＝０ｘ，ｙ／πであることを検証することは容易である。さらに、
【数７】
2018530081.tif 000010
であるような円上の任意の点ｘ、ｙ、ｘ’、ｙ’について、０ｘ’，ｙ≦２０ｘ，ｙが達成される。ｐを定義して、以下の式が用いられる。
【数８】
2018530081.tif 000011
【００９５】
[0109]関数Ｈのファミリは、ｕのｔ個の独立したコピーの外積となるように設定され、すなわちｈ（ｘ）＝［ｕ１（ｘ），．．．，ｕｔ（ｘ）］である。直観的には、ｈ（ｘ）＝ｈ（ｙ）の場合、ｘとｙとが互いに近い可能性が高くなるようにしたい。これを定量化する。最初に、予期されるフォールスポジティブ誤りの数ｎｆｐを計算する。これらは、ｈ（ｘ）＝ｈ（ｙ）であるが、｜｜ｘ−ｙ｜｜＞２ｒの場合である。ｎｆｐが１以下である値ｔが見つかる。すなわち、１は間違っているとは予期されていない。
【数９】
2018530081.tif 000012
【００９６】
[0110]次に、ｘとｙとが近傍である場合のｈ（ｘ）＝ｈ（ｙ）の確率を計算する。
【数１０】
2018530081.tif 000013
【００９７】
[0111]ここでは、２ｐ＜１でなければならず、これにはｒ’＞
【数１１】
2018530081.tif 000014
が必要であることに留意されたい。これはあまり高い成功確率のようには思われないであろう。確かに、１／
【数１２】
2018530081.tif 000015
は１／２より著しく小さい。次のセクションでは、どのようにしてこの確率を１／２まで上げるかについて説明する。
【００９８】
[0112]セクション１．２  点探索アルゴリズム
【００９９】
[0113]各関数ｈは、空間内のすべての点をバケットにマップする。ハッシュ関数ｈに関連する点ｘのバケット関数
【数１３】
2018530081.tif 000016
をＢｈ（ｘ）≡｛ｘｉ｜ｈ（ｘｉ）＝ｈ（ｘ）｝として定義する。維持されるデータ構造は、バケット関数のｍ＝Ｏ（
【数１４】
2018530081.tif 000017
）個のインスタンス［Ｂｈ１，…，Ｂｈｍ］である。点ｘを探索すると、関数は
【数１５】
2018530081.tif 000018
を返す。前セクションによれば、２つの望ましい結果が生じる。
【数１６】
2018530081.tif 000019
【０１００】
[0114]言い換えると、少なくとも１／２の確率でｘの各近傍が見つかるが、多くの非近傍を見つける可能性は低い。
【０１０１】
[0115]セクション１．３  異なる半径の入力ベクトルの処理
【０１０２】
[0116]前セクションでは、同じ長さ、すなわちｒ’のベクトルを探索することのみを扱った。次に、この構造をビルディングブロックとして用いて異なる半径での探索をどのようにサポートできるかについて説明する。図１１に示すように、空間は指数関数的に増加する幅の環に分割される。Ｒｉと表記されている環ｉは、
【数１７】
2018530081.tif 000020
になるようなすべての点ｘｉを含む。これを行うことで２つの目的が達成される。第１に、ｘｉとｘｊが同じ環に属している場合には、
【数１８】
2018530081.tif 000021
である。第２に、いかなる探索もせいぜい１／∈
のそのような環で行うことができる。さらに、データセット内の最大長ベクトルがｒ’である場合には、システム内の環の総数はＯ（ｌｏｇ（ｒ’／ｒ））である。
【０１０３】
[0117]セクション２  経路追跡問題
【０１０４】
[0118]経路追跡問題では、空間内の固定経路が、時点列内の粒子の位置と共に与えられる。粒子、キュー、および点という用語は、区別なく用いられる。アルゴリズムは、経路上の粒子の位置を出力する必要がある。これは以下のいくつかの要因、すなわち、粒子は、経路を近似的にたどるにすぎないこと、経路は不連続であり、何度も自己交差する可能性があること、粒子位置と経路位置の両方が（それぞれに異なる）時点列として与えられること、によってより困難になる。
【０１０５】
[0119]この問題は、任意の数の経路上の粒子の追跡をシミュレートできることに留意することが重要である。これは、各経路を連結して１本の長い経路にし、結果として得られる位置を個々の経路上の位置として解釈することによって簡単に行われる。
【０１０６】
[0120]より正確には、経路Ｐをパラメトリック曲線
【数１９】
2018530081.tif 000022
とする。曲線パラメータを時間と呼ぶ。既知である経路上の点は任意の時点ｔｉにおいて与えられ、すなわちｎ対の（ｔｉ，Ｐ（ｔｉ））が与えられる。粒子は経路をたどるが、その位置は図１２に示すように異なる時点において与えられる。さらに、ｍ対の（ｔ’ｊ，ｘ（ｔ’ｊ））が与えられ、ｘ（ｔ’ｊ）は時間ｔ’ｊにおける粒子の位置である。
【０１０７】
[0121]セクション２．１  尤度推定
【０１０８】
[0122]粒子は経路を正確にたどらず、経路は何度も自己交差する可能性があるため、粒子が実際にある経路上の位置を確実に識別することは通常は不可能である。したがって、すべての可能な経路位置上で確率分布が計算される。位置確率の確度が著しく高い場合、粒子位置は既知であると想定される。以下のセクションでは、これを効率的に行う方法について説明する。
【０１０９】
[0123]
粒子が経路をたどっている場合には、粒子のタイムスタンプとＰ上の対応する点のオフセットとの間の時間差は比較的一定になるはずである。言い換えると、ｘ（ｔ’）が経路上で現在オフセットｔにある場合には、ｘ（ｔ’）はＰ（ｔ）に近いはずである。また、τ秒前には、ｘ（ｔ’）はオフセットｔ−τにあったはずである。よって、ｘ（ｔ’−τ）はＰ（ｔ−τ）に近いはずである（粒子が経路と交差しており、ｘ（ｔ’）がＰ（ｔ）に一時的に近い場合、ｘ（ｔ’−τ）とＰ（ｔ−τ）も近い可能性は低いことに留意されたい）。相対オフセットをΔ＝ｔ−ｔ’と定義する。粒子が経路をたどっている限り、相対オフセットΔは変化しないままであることに留意されたい。すなわち、ｘ（ｔ’）はＰ（ｔ’＋Δ）に近い。
【０１１０】
[0124]最尤相対オフセットは、以下を計算することによって得られる。
【数２０】
2018530081.tif 000023
【０１１１】
[0125]言葉で説明すると、最も可能性が高い相対オフセットは、粒子の履歴の可能性が最も高いオフセットである。しかし、この方程式は統計モデルなしでは解くことができない。このモデルは、ｘが経路をどれほど厳密にたどるか、ｘが位置間をジャンプする可能性がどれほど高いか、経路および粒子曲線が測定された点間でどれほど滑らかであるか、を定量化しなければならない。
【０１１２】
[0126]セクション２．２  時間割引ビニング
【０１１３】
[0127]次に、尤度関数を推定するための統計モデルについて説明する。このモデルでは、経路からの粒子の逸脱が標準偏差ａｒで正規分布していると仮定する。またこのモデルでは、任意の所与の時点で、粒子が急に別の経路に切り替わるある非ゼロの確率があるとも仮定する。これは、過去の点の時間による指数割引によって明示される。モデル化の観点から合理的な選択であること以外に、このモデルには効率的に更新可能であるという利点もある。ある一定の時間単位１にわたって、尤度関数を、以下のように定義されるｆに比例するように設定する。
【数２１】
2018530081.tif 000024
【０１１４】
[0128]
式中、α＜＜１はスケール係数であり、ζ＞０は、粒子が所与の時間単位において経路上のランダムな位置にジャンプする確率である。
【０１１５】
[0129]関数ｆの効率的な更新は、以下の簡単な知見を用いて達成することができる。
【数２２】
2018530081.tif 000025
【０１１６】
[0130]さらに、α＜＜１であるため、｜｜ｘ（ｔ’ｍ）−Ｐ（ｔｉ）｜｜≧ｒ
の場合、以下の式が生じる。
【数２３】
2018530081.tif 000026
【０１１７】
[0131]これは尤度関数の重要な特性である。というのは、合計の更新を、経路全体にわたってではなくｘ（ｔ’ｊ）の近傍にわたってのみ行うことができるようになるからである。Ｓで、｜｜ｘ（ｔ’ｍ）−Ｐ（ｔｉ）｜｜≧ｒになるような（ｔｉ，Ｐ（ｔｉ））の集合を表す。以下の式が生じる。
【数２４】
2018530081.tif 000027
【０１１８】
[0132]これについては以下のアルゴリズム２．２に記載する。項ｆは、負の整数インデックスも受け取る疎ベクトルとして用いられる。集合Ｓは、経路上のｘ（ｔｉ）のすべての近傍の集合であり、ＰＰＬＥＢアルゴリズムを用いて迅速に計算することができる。ｘ（ｔｉ）の近傍の数がある定数ｎｎｅａｒによって制限される場合には、ベクトルｆの非ゼロの数は一定の係数だけ大きいｎｎｅａｒ／ζによって制限されることを検証することは容易である。アルゴリズムの最終段階は、
【数２５】
2018530081.tif 000028
がある閾値を上回る場合のδの特定の値を出力することである。
【表２】
2018530081.tif 000029
【０１１９】
[0133]図１１に、３つの連続した点位置とそれらの周りの経路点を示す。最下点だけでも中間点だけでも経路の正しい部分を十分に識別できなかったはずであることに留意されたい。しかし、これらの点を併せれば十分に識別できる。最上点を追加すれば、粒子が実際に経路の最終（左）曲線のものである確実性が増す。
【０１２０】
[0134]図１２では、ｎ個の（灰色の）点の集合が与えられた場合、アルゴリズムはクエリ点（黒）を与えられ、クエリ点から距離ｒ内にある点の集合（円内の点）を返す。従来の設定では、アルゴリズムはそのようなすべての点を返さなければならない。確率的設定では、そのような各点がある一定の確率でのみ返されるはずである。
【０１２１】
[0135]図１３に、ｕ（ｘ１）、ｕ（ｘ２）、およびｕ（ｘ）の各値を示す。直感的には、関数ｕは、破線がｘ１とｘ２との間を通る場合はｘ１とｘ２とに異なる値を与え、そうでない場合は同じ値を与える。破線をランダムな方向に通せば、これが起こる確率は、ｘ１とｘ２との角度に正比例するようになる。
【０１２２】
[0136]図１４に、環Ｒｉが半径２ｒ（１＋∈）ｉと２ｒ（１＋∈）ｉ＋１との間にあるように空間を環に分割することによって、環内の任意の２つのベクトルが最大（１＋∈）因子まで同じ長さであり、任意の探索がせいぜい１／∈環において行われることを確実にできることを示す。
【０１２３】
[0137]図１５に、自己交差経路とクエリ点（黒）とを示す。粒子位置の履歴がなければ、粒子が経路上のどこにあるか知ることは不可能であることが例示されている。
【０１２４】
[0138]図１５に、３つの連続した点位置とそれらの周りの経路点とを示す。ｘ（ｔ１）だけでもｘ（ｔ２）だけでも経路の正しい部分を十分に識別できなかったはずであることに留意されたい。しかし、これらの点を併せれば十分に識別できる。ｘ（ｔ３）を追加すれば、粒子が実際に経路の最終（左）曲線のものである確実性が増す。
【０１２５】
[0139]本明細書ではおおむね映像データおよびグラフィック表示に関するものとして説明されているが、本明細書に記載するシステムおよび方法は、音声データおよび可聴表示に関しても同様に使用されることが企図されている。
【０１２６】
[0140]具体的な要件に応じて大幅な変更がなされてもよい。例えば、カスタマイズされたハードウェアが使用されてもよく、かつ／または特定の要素がハードウェア、ソフトウェア（アプレットなどのポータブルソフトウェアを含む）、もしくはその両方で実装されてもよい。さらに、他のアクセスまたはネットワーク入力装置／出力装置などのコンピューティング機器への接続が用いられてもよい。
【０１２７】
[0141]以上の明細書では、本発明の態様がその具体的実施形態に関連して説明されているが、本発明はそれらだけに限定されないことを当業者は理解するであろう。上述の発明の様々な特徴および態様は、個別に用いられても一緒に用いられてもよい。さらに、本明細書の幅広い趣旨および範囲から逸脱することなく、本明細書に記載した以外の任意の数の環境および用途において各実施形態を利用することができる。したがって、本明細書および図面は、限定ではなく例示とみなすべきである。
【０１２８】
[0142]以上の説明では、例示を目的として、方法を特定の順序で記載した。別の実施形態では、方法は記載した順序と異なる順序で行われてもよいことを理解されたい。また、上述の方法は、ハードウェア構成要素によって行われてもよく、機械実行可能命令でプログラムされた汎用または専用プロセッサや論理回路などの機械に方法を行わせるのに用いられる機械実行可能命令のシーケンスとして具体化されてもよいことも理解されたい。これらの機械実行可能命令は、ＣＤ−ＲＯＭや他の種類の光ディスク、フロッピーディスケット、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カードや光カード、フラッシュメモリ、または電子命令を格納するのに適した他の種類の機械可読媒体など、１つまたは複数の機械可読媒体に格納されていてよい。あるいは、これらの方法は、ハードウェアとソフトウェアの組み合わせによって行われてもよい。
【０１２９】
[0143]構成要素がある特定の動作を行うように構成されているものとして記述される場合、そのような構成は、例えば、その動作を行う電子回路または他のハードウェアを設計することによって、その動作を行うプログラマブル電子回路（例えば、マイクロプロセッサや他の適切な電子回路）をプログラムすることによって、またはそれらの任意の組み合わせによって実現することができる。
【０１３０】
[0144]本明細書では本出願の例示的実施形態を記載したが、本発明の概念は、それ以外にも様々に具体化され、用いられること、および添付の特許請求の範囲は、先行技術による限定を除いて、そうした変形を含むものと解釈すべきであることを理解されたい。
【図１】
2018530081.tif 000030
【図２】
2018530081.tif 000031
【図３】
2018530081.tif 000032
【図４】
2018530081.tif 000033
【図５】
2018530081.tif 000034
【図６】
2018530081.tif 000035
【図７】
2018530081.tif 000036
【図８】
2018530081.tif 000037
【図９】
2018530081.tif 000038
【図１０】
2018530081.tif 000039
【図１１】
2018530081.tif 000040
【図１２】
2018530081.tif 000041
【図１３】
2018530081.tif 000042
【図１４】
2018530081.tif 000043
【図１５】
2018530081.tif 000044
【国際調査報告】
2018530081.tif 000045
2018530081.tif 000046
2018530081.tif 000047