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